Rademacher (Mathematische Annalen87 (1922) 112–138), Steinhaus (Mathematische Zeitschrift31 (1930) 408–416) and Paley and Zygmund (Mathematical Proceedings of the Cambridge Philosophical Society26 (1930) 337–257, Mathematical Proceedings of the Cambridge Philosophical Society26 (1930) 458–474, Mathematical Proceedings of the Cambridge Philosophical Society28 (1932) 190–205) initiated the extensive study of random series. Using the theory of algorithmic randomness, which is a mix of computability theory and probability theory, we investigate the effective content of some classical theorems. We discuss how this is related to an old question of Kahane and Bollobás. We also discuss how considerations of such algorithmic questions about random series seem to lead to new notions of algorithmic randomness.
J.Angst and G.Poly, Variations on Salem–Zygmund results for random trigonometric polynomials: Application to almost sure nodal asymptotics, Electronic J. Probability26 (2021), 1–36. doi:10.1214/21-EJP716.
2.
L.Bienvenu, N.Greenberg, A.Kučera, A.Nies and D.Turetsky, Coherent randomness tests and computing the K-trivial sets, J. Eur. Math. Soc. (JEMS)18(4) (2016), 773–812. doi:10.4171/JEMS/602.
3.
S.Binns, Small classes, Archive for Mathematical Logic45(4) (2005), 393–410. doi:10.1007/s00153-005-0319-6.
4.
A.Blass, J.Brendle, W.Brian, J.D.Hamkins, M.Hardy and P.B.Larson, The rearrangement number, Trans. Amer. Math. Soc.373(1) (2020), 41–69. doi:10.1090/tran/7881.
5.
B.Bollobás, Random Graphs, 2nd edn, Cambridge Studies in Advanced Mathematics, Vol. 73, Cambridge University Press, Cambridge, 2001.
6.
A.Bonami and J.Peyrière, Introduction to: Proceedings of the conference in honor of Jean-Pierre Kahane (Orsay, 1993). Special issue of The Journal of Fourier Analysis and Applications (1995), 1–6.
7.
V.Brattka and G.Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic76(1) (2011), 143–176. doi:10.2178/jsl/1294170993.
8.
V.Brattka, J.S.Miller and A.Nies, Randomness and differentiability, Trans. Amer. Math. Soc.368(1) (2016), 581–605. doi:10.1090/tran/6484.
9.
G.Cohen and C.Cuny, On random almost periodic trigonometric polynomials and applications to ergodic theory, Annals of Probability34 (2006), 39–79.
10.
R.Downey and D.Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010.
11.
R.Downey and D.R.Hirschfeldt, Algorithmic randomness, Communications of the ACM62(5) (2019), 70–80. doi:10.1145/3319408.
12.
R.Downey and D.R.Hirschfeldt, Computability and randomness, Notices of the American Mathematical Society66(07) (2019), 1. doi:10.1090/noti1905.
13.
R.Downey, D.R.Hirschfeldt, A.Nies and S.Terwijn, Calibrating randomness, Bulletin of Symbolic Logic12 (2006), 411–491. doi:10.2178/bsl/1154698741.
14.
S.Filip, A.Javeed and L.N.Trefethen, Smooth random functions, random codes, and Gaussian processes, SIAM Review61(1) (2019), 185–205. doi:10.1137/17M1161853.
15.
P.Gács, M.Hoyrup and C.Rojas, Randomness on computable probability spaces – a dynamical point of view, Theory Comput. Syst.48(3) (2011), 465–485. doi:10.1007/s00224-010-9263-x.
16.
G.Gherardi and A.Marcone, How incomputable is the separable Hahn–Banach theorem?Notre Dame J. Form. Log.50(4) (2010), 393–425, 2009. doi:10.1215/00294527-2009-018.
17.
N.Greenberg, R.Kuyper and D.Turetsky, Cardinal invariants, non-lowness classes, and Weihrauch reducibility, Computability8(3–4) (2019), 305–346. doi:10.3233/COM-180219.
18.
M.Hill, Convergence of random Fourier series, 2012, REU Paper, University of Chicago.
19.
J.-P.Kahane, Some Random Series of Functions, Cambridge University Press, 2003.
20.
S.Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois at Urbana-Champaign, 1981.
21.
M.Li and P.Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer International Publishing, 2019.
22.
P.Martin-Löf, The definition of random sequences, Information and Control9(6) (1966), 602–619. doi:10.1016/S0019-9958(66)80018-9.
23.
A.Nies, Computability and Randomness, Oxford University Press, 2012.
24.
I.Ongay-Valverde and P.Tveite, Computable analogs of cardinal characteristics: Prediction and rearrangement, Ann. Pure Appl. Logic172(1) (2021), PaperNo.102872, 23.
25.
R.E.A.C.Paley and A.Zygmund, On some series of functions, (1), Mathematical Proceedings of the Cambridge Philosophical Society26(4) (1930), 337–357. doi:10.1017/S0305004100016078.
26.
R.E.A.C.Paley and A.Zygmund, On some series of functions, (2), Mathematical Proceedings of the Cambridge Philosophical Society26(4) (1930), 458–474. doi:10.1017/S0305004100016212.
27.
R.E.A.C.Paley and A.Zygmund, On some series of functions, (3), Mathematical Proceedings of the Cambridge Philosophical Society28(2) (1932), 190–205. doi:10.1017/S0305004100010860.
28.
P.Potgieter, Algorithmically random series and Brownian motion, Annals of Pure and Applied Logic169(11) (2018), 1210–1226. doi:10.1016/j.apal.2018.07.001.
29.
M.B.Pour-El and J.I.Richards, Computability in Analysis and Physics, Cambridge University Press, 2017.
30.
H.Rademacher, Einige sätze über reihen von allgemeinen orthogonalfunktionen, Mathematische Annalen87 (1922), 112–138. doi:10.1007/BF01458040.
31.
R.Salem and A.Zygmund, Some properties of trigonometric series whose terms have random signs, Acta. Math.91 (1954), 245–301. doi:10.1007/BF02393433.
32.
S.G.Simpson, Mass problems and randomness, Bull. Symbolic Logic11(1) (2005), 1–27. doi:10.2178/bsl/1107959497.
33.
R.I.Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.
34.
A.Sorbi, The Medvedev lattice of degrees of difficulty, in: Computability, Enumerability, Unsolvability, London Math. Soc. Lecture Note Ser., Vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 289–312. doi:10.1017/CBO9780511629167.015.
35.
H.Steinhaus, Uber die wahrscheinlichkeit dafur, das der konvergenzkreis einer potenzreihe ihre naturliche grenze ist, Mathematische Zeitschrift31(1) (1930), 408–416. doi:10.1007/BF01246422.
36.
A.M.Turing, On computable numbers with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. (2)42 (1936), 230–265, A correction, 43:544–546.
37.
Y.Wang, Randomness and complexity, PhD thesis, University of Heidelberg, 1996.
38.
K.Weihrauch, Computable Analysis: An Introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.
39.
A.Zygmund, Trigonometric Series, Vol. 1, Cambridge University Press, 1959.
