Algorithmically random series

Article type: Research Article

Authors: Downey, Rodney G.^{a; *} | Greenberg, Noam^b | Tanggara, Andrew^c

Affiliations: [a] School of Mathematics and Statistics, Victoria University of Wellington, NZ | [b] School of Mathematics and Statistics, Victoria University of Wellington, NZ | [c] Centre for Quantum Technologies, National University of Singapore, Singapore

Correspondence: [*] Corresponding author. [email protected].

Abstract: Rademacher (Mathematische Annalen 87 (1922) 112–138), Steinhaus (Mathematische Zeitschrift 31 (1930) 408–416) and Paley and Zygmund (Mathematical Proceedings of the Cambridge Philosophical Society 26 (1930) 337–257, Mathematical Proceedings of the Cambridge Philosophical Society 26 (1930) 458–474, Mathematical Proceedings of the Cambridge Philosophical Society 28 (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.

Keywords: Algorithmic randomness, random trigonometric series, Schnorr randomness, Kurtz randomness, Martin-Löf randomness, Payley–Zygmund series, Rademacher series

DOI: 10.3233/COM-220433

Journal: Computability, vol. Pre-press, no. Pre-press, pp. 1-13, 2023