×

zbMATH — the first resource for mathematics

Algorithmic randomness and Fourier analysis. (English) Zbl 07074495
Summary: Suppose \(1 < p < \infty\). Carleson’s Theorem states that the Fourier series of any function in \(L^p[-\pi, \pi]\) converges almost everywhere. We show that the Schnorr random points are precisely those that satisfy this theorem for every \(f \in L^p[-\pi, \pi]\) given natural computability conditions on \(f\) and \(p\).
MSC:
03D32 Algorithmic randomness and dimension
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, K.; Bienvenu, L.; Slaman, TA, On zeros of Martin-Löf random Brownian motion, J. Log. Anal., 6, paper 9, 34, (2014) · Zbl 1346.03044
[2] Asarin, EA; Pokrovskiı̆, AV, Application of Kolmogorov complexity to the analysis of the dynamics of controllable systems, Avtomat. i Telemekh., 1, 25-33, (1986)
[3] Avigad, J., Uniform distribution and algorithmic randomness, J. Symb. Log., 78, 334-344, (2013) · Zbl 1275.03133
[4] Bienvenu, L.; Day, AR; Hoyrup, M.; Mezhirov, I.; Shen, A., A constructive version of Birkhoff’s ergodic theorem for Martin-Löf random points, Inf. Comput., 210, 21-30, (2012) · Zbl 1257.03067
[5] Bienvenu, L.; Hölzl, R.; Miller, JS; Nies, A., Denjoy, Demuth and density, J. Math. Log., 14, 1450004, 35, (2014) · Zbl 1338.03088
[6] Brattka, V., Weihrauch, K.: Computability on subsets of Euclidean space. I. Closed and compact subsets, vol. 219. In: Computability and Complexity in Analysis (Castle Dagstuhl, 1997), pp 65-93 (1999) · Zbl 0916.68042
[7] Brattka, V.; Miller, JS; Nies, A., Randomness and differentiability, Trans. Am. Math. Soc., 368, 581-605, (2016) · Zbl 1402.03062
[8] Braverman, M.; Cook, S., Computing over the reals: foundations for scientific computing, Not. Am. Math. Soc., 53, 318-329, (2006) · Zbl 1092.68038
[9] Calvert, W.; Franklin, JNY, Genericity and UD-random reals, J. Log. Anal., 7, paper 4, 10, (2015) · Zbl 1322.03032
[10] Carleson, L., On convergence and growth of partial sums of Fourier series, Acta Math., 116, 135-157, (1966) · Zbl 0144.06402
[11] Conway, J.B: Functions of One Complex Variable I, Volume 11 of Graduate Texts in Mathematics, 2nd edn. Springer, Berlin (1978)
[12] Cooper, S.B.: Computability Theory. Chapman & Hall/CRC, Boca Raton (2004) · Zbl 1041.03001
[13] Downey, RG; Griffiths, EJ, Schnorr randomness, J. Symb. Log., 69, 533-554, (2004) · Zbl 1072.03025
[14] Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Springer, Berlin (2010) · Zbl 1221.68005
[15] Fefferman, C., Pointwise convergence of Fourier series, Ann. of Math. (2), 98, 551-571, (1973) · Zbl 0268.42009
[16] Fefferman, CL, Erratum: “Pointwise convergence of Fourier series” [Ann. of Math. (2) 98 (1973), no. 3, 551-571; MR0340926 (49 #5676)], Ann. Math. (2), 146, 239, (1997)
[17] Fejér, L., Sur les fonctions bornées et intégrables, C. R. Acad. Sci. Paris, 131, 984-987, (1900) · JFM 31.0400.01
[18] Fouché, WL, The descriptive complexity of Brownian motion, Adv. Math., 155, 317-343, (2000) · Zbl 0971.68077
[19] Franklin, JNY; Greenberg, N.; Miller, JS; Ng, KM, Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets, Proc. Am. Math. Soc., 140, 3623-3628, (2012) · Zbl 1298.03103
[20] Franklin, JNY; Towsner, H., Randomness and non-ergodic systems, Mosc. Math. J., 14, 711-744, (2014) · Zbl 1335.03039
[21] Freer, C.; Kjos-Hanssen, B.; Nies, A.; Stephan, F., Algorithmic aspects of Lipschitz functions, Computability, 3, 45-61, (2014) · Zbl 1408.03031
[22] Gács, P.; Hoyrup, M.; Rojas, C., Randomness on computable probability spaces—a dynamical point of view, Theory Comput. Syst., 48, 465-485, (2011) · Zbl 1238.68069
[23] Galatolo, S., Hoyrup, M., Rojas, C.: Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems. In: Zheng, X., Zhong, N. (eds.) Proceedings Seventh International Conference on Computability and Complexity in Analysis, Zhenjiang, China, 21-25th June 2010, volume 24 of Electronic Proceedings in Theoretical Computer Science, pp. 7-18. Open Publishing Association (2010)
[24] Garnett, J.B., Marshall, D.E.: Harmonic Measure, New Mathematical Monographs, vol 2. Cambridge University Press, Cambridge (2005)
[25] Grzegorczyk, A., On the definitions of computable real continuous functions, Fund. Math., 44, 61-71, (1957) · Zbl 0079.24801
[26] Hoyrup, M., Computability of the ergodic decomposition, Ann. Pure Appl. Logic, 164, 542-549, (2013) · Zbl 1271.03063
[27] Hoyrup, M., Rojas, C.: Applications of effective probability theory to Martin-Löf randomness. In: Automata, Languages and Programming. Part I, volume 5555 of Lecture Notes in Computer Science, pp 549-561. Springer, Berlin (2009) · Zbl 1248.03066
[28] Hunt, R.A: On the convergence of Fourier series. In: Orthogonal Expansions and Their Continuous Analogues (Proc. Conf., Edwardsville, Ill., 1967), pp 235-255. Southern Illinois University Press, Carbondale (1968)
[29] Kahane, J-P; Katznelson, Y., Sur les ensembles de divergence des séries trigonométriques, Studia Math., 26, 305-306, (1966) · Zbl 0143.28901
[30] Katznelson, Y., Sur les ensembles de divergence des séries trigonométriques, Studia Math., 26, 301-304, (1966) · Zbl 0143.28804
[31] Kolmogorov, AN, Une série de Fourier-Lebegue divergente presque partout, Fund. Math. Fund. Math. Fund. Math., 4, 324-328, (1923)
[32] Lacombe, D., Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. I, C. R. Acad. Sci. Paris, 240, 2478-2480, (1955) · Zbl 0065.00201
[33] Lacombe, D., Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris, 241, 13-14, 151-153, (1955) · Zbl 0066.26101
[34] Lebesgue, H., Recherches sur la convergence des séries de fourier, Math. Ann., 61, 251-280, (1905) · JFM 36.0330.01
[35] Miyabe, K., L1-computability, layerwise computability and Solovay reducibility, Computability, 2, 15-29, (2013) · Zbl 1315.03073
[36] Miyabe, K., Nies, A., Zhang, J.: “Universal” Schnorr tests, In progress
[37] Moser, P., On the convergence of Fourier series of computable Lebesgue integrable functions, MLQ Math. Log. Q., 56, 461-469, (2010) · Zbl 1201.03057
[38] Nehari, Z.: Conformal Mapping. McGraw-Hill Book Co., Inc., New York (1952) · Zbl 0048.31503
[39] Nies, A.: Computability and Randomness. Clarendon Press, Oxford (2009) · Zbl 1169.03034
[40] Nies, A.: Differentiability of polynomial time computable functions. In: 31st International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 25, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp 602-613 (2014) · Zbl 1359.03032
[41] Odifreddi, P.: Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, no. 125. North-Holland, Amsterdam (1989)
[42] Odifreddi, P.: Classical Recursion Theory, Volume ii. Studies in Logic and the Foundations of Mathematics, no. 143. North-Holland, Amsterdam (1999)
[43] Pathak, N.; Rojas, C.; Simpson, SG, Schnorr randomness and the Lebesgue differentiation theorem, Proc. Am. Math. Soc., 142, 335-349, (2014) · Zbl 1307.03027
[44] Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer, Berlin (1989) · Zbl 0678.03027
[45] Rettinger, R.; Weihrauch, K., Products of effective topological spaces and a uniformly computable Tychonoff theorem, Log. Methods Comput. Sci., 9, 4:14, 21, (2013) · Zbl 1315.03120
[46] Rute, J.: Topics in algorithmic randomness and computable analysis. PhD thesis, Carnegie Mellon University, August 2013. Available at http://repository.cmu.edu/dissertations/260/
[47] Soare, R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, Berlin (1987)
[48] Schnorr, C.-P.: Zufälligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, vol. 218. Springer, Heidelberg (1971) · Zbl 0232.60001
[49] Specker, E., Nicht konstruktiv beweisbare Sätze der Analysis, J. Symb. Log., 14, 145-158, (1949) · Zbl 0033.34102
[50] Turing, AM, On computable numbers, with an application to the Entscheidungsproblem. A Correction, Proc. London, Math. Soc., S2-43, 544, (1937) · Zbl 0018.19304
[51] V’yugin, VV, Effective convergence in probability, and an ergodic theorem for individual random sequences, Teor. Veroyatnost. i Primenen., 42, 35-50, (1997) · Zbl 0917.60039
[52] Weihrauch, K.: Computable Analysis, Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.