Algorithmically random series

Abstract

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.

Keywords

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

1. Introduction

The concern of this paper is the area of random trigonometric series, an area going back to seminal papers of Paley and Zygmund in the 1930’s, and subsequently having a rich history, with applications to ergodic theory and Brownian motion (see, for instance, Angst and Poly [1], Cohen and Cuny [9], Filip et al. [14], Hill [18], or Salem and Zygmund [31]). The goal of the present paper is to use ideas from the theory of algorithmic randomness, or algorithmic information theory (see Li and Vitanyi [21], Downey and Hirschfeldt [10], or Nies [23]), to examine natural questions which grew from the theory of such series. The area enables us to quantify, or calibrate, the amount of randomness (in the sense of [13]) needed to prove classical theorems involving almost everywhere behaviour. In turn, this allows us to address questions about algorithmic aspects of random series, which so far have been stated informally.

In particular, the original motivation for the present paper was an intriguing comment by Bollobás in the introduction to his book [5], originally in 1985. In this introduction, Bollobás motivates the use of probabilistic ideas in graph theory. He mentioned that earlier probabilistic application had been found in analysis via three famous papers of Paley and Zygmund [25–27]:

“Paley and Zygmund (1930a,b,1932) had investigated random series of functions. One of their results was that if the real numbers $c_{n}$ satisfy $\sum_{n = 0}^{\infty} c_{n}^{2} = \infty$ then $\sum_{n = 0}^{\infty} \pm c_{n} cos n x$ fails to be a Fourier–Lebesgue series for almost all choices of the signs. To exhibit a sequence of signs with this property is surprisingly difficult: indeed there is no algorithm known which constructs an appropriate sequence of signs from any sequence $c_{n}$ with $\sum_{n = 0}^{\infty} c_{n}^{2} = \infty$ .”

An almost identical question can be found in the 1968 version of Kahane’s book (most recently, [19], page 47), on random trigonometric series:

“If $\sum c_{n}^{2} = \infty$ , there exists a choice of signs ± such that $\sum \pm c_{n} cos (n t + φ_{n})$ is not a Fourier–Stieltjes series. A surprising fact is that nobody knows how to construct these signs explicitly, but a random choice works.”

Thus, this natural question is now at least 50 years old.1

¹
Fourier–Stieltjes series are generalisations of usual Fourier series of integrable functions, using the Lebesgue–Stieltjes integrals based on an absolutely continuous function. Thus, the almost-everywhere result is a little stronger when using this notion. This notion, applied to step functions, is used for trigonometric interpolation, see [39, Ch.X].

The first thing we need to do in answering such a question is to understand how to formulate it mathematically. Fortunately, we can use computability theory to do this. The natural tool to use is Turing’s “oracle machine”. A positive solution to Bollobás’s problem would consist of an algorithm which runs on Turing’s idealised machine. On an “input tape” of the machine is written the sequence of reals $⟨ c_{n} ⟩$ . The machine runs indefinitely, and on an “output tape” is gradually written a solution: a sequence $⟨ x_{n} ⟩ \in {- 1, 1}^{\infty}$ such that $\sum x_{n} c_{n} cos n t$ is not a Fourier–Lebesgue series. The main point is that there is a single algorithm which given the input $⟨ c_{n} ⟩$ produces a desired output $⟨ x_{n} ⟩$ . We say that the outputs are uniformly computable from the inputs.

Paradoxically, a positive solution to the Bollobás/Kahane question can be given using the Paley–Zygmund almost everywhere result. Given an instance $⟨ c_{n} ⟩$ of the problem (with $\sum c_{n}^{2} = \infty$ ), we know that the collection of “untypical” $x = ⟨ x_{n} ⟩ \in {- 1, 1}^{\infty}$ , those for which $\sum x_{n} c_{n} cos n t$ is a Fourier–Lebesgue series, is null. The theory of algorithmic randomness allows us to inquire into how effectively null it is. It turns out that the null set in this case is particularly simple.

Computability theory gives us the notion of an enumerable open set (also called an effectively open set). Since we allow non-computable inputs, we give a definition that can be relativised. For the following, a sequence of sets $U_{0}, U_{1}, \dots$ is called nested if $U_{0} \supseteq U_{1} \supseteq U_{2} \supseteq \dots$ .

Definition 1.1.

A name of an open set U is a list $⟨ V_{0}, V_{1}, V_{2}, \dots ⟩$ of basic open sets such that $U = ⋃_{n} V_{n}$ .2

For a closed interval, we can take the basis consisting of rational open intervals; in Cantor space, the basis of clopen sets, each determined by finitely many values.

A name of a sequence of open sets $U_{0}, U_{1}, \dots$ is a sequence consisting of a name of $U_{0}$ , a name of $U_{1}$ , ….

A name of a $G_{δ}$ set G is a name of a nested sequence of open sets $U_{0}, U_{1}, U_{2}, \dots$ such that $G = ⋂_{n} U_{n}$ .

A name of an $F_{σ}$ set is a name of its complement.

Potgieter [28] first studied the complexity of the null sets arising from the Paley–Zygmund theorem. Implicit in his calculations is the following:

Theorem 1.2.

Given $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ with $\sum c_{n}^{2} = \infty$ , we can compute a name of a null $F_{σ}$ set containing all $x \in {- 1, 1}^{\infty}$ for which $\sum x_{n} c_{n} cos (n t + φ_{n})$ is a Fourier–Stieltjes series.

We can then quote a standard result from computability theory:

Fact 1.3.

Given a name of a null $F_{σ}$ set H, we can compute a point $x \notin H$ .

Theorem 1.2 and Fact 1.3 together give a positive answer to Kahane’s question:

Theorem 1.4.

There is an algorithm which, given $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ with $\sum c_{n}^{2} = \infty$ , outputs a sequence $x \in {- 1, 1}^{\infty}$ for which $\sum x_{n} c_{n} cos (n t + φ_{n})$ is not a Fourier–Stieltjes series.

We elaborate on Theorem 1.2 and Fact 1.3 in Section 2.

1.1. Algorithmic randomness

Algorithmic randomness ([10,21,23]) seeks to give meaning to randomness of individual sequences. We say that a point x in a computable measure space is random if it passes all “appropriately computable tests” for randomness. The idea is that if only a specified kind of computable testing processes are available to us, then we cannot distinguish x from one classically chosen at random. For the reader unfamiliar with these concepts, we refer to Downey and Hirschfeldt [11,12] for recent surveys, aimed at a lay audience, expositing these ideas. For our purposes, to give this a formal meaning, a notion of randomness is determined by specifying a countable collection of null sets; a point is then declared to be random if it belongs to none of these null sets. For example:

Definition 1.5 (Kurtz [20], Wang [37]).

A set A is Kurtz null if it is contained in a null $F_{σ}$ set which has a computable name.

A point is Kurtz random if it is not an element of any Kurtz null set.

Since there are only countably many algorithms, there are only countably many computable names of $F_{σ}$ sets. It follows that almost every point is Kurtz random. Since we allow noncomputable instances $⟨ c_{n} ⟩$ of theorems such as Paley and Zygmund’s, we can use the relativised notion of randomness as well:

Definition 1.6.
Let y be an element of Baire space $ω^{ω}$ .3
³
The point y is often referred to as an “oracle” in a computation. For our purposes, y will usually be a code for a sequence $⟨ c_{n} ⟩$ . Instead of Baire space we could take any other 0-dimensional computable topological space, for example Cantor space.

A set A is y-Kurtz null (or Kurtz null relative to y) if it is contained in a null $F_{σ}$ set which has a y-computable name.

A point is y-Kurtz random (or Kurtz random relative to y) if it is not an element of any y-Kurtz null set.

Again, for all y, almost every x is Kurtz random relative to y. With this terminology, a consequence of Theorem 1.2 is:
Theorem 1.7.
Let $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ be sequences of real numbers with $\sum c_{n}^{2} = \infty$ . If $x \in {- 1, 1}^{\infty}$ is Kurtz random relative to $(⟨ c_{n} ⟩, ⟨ φ_{n} ⟩)$ , then $\sum x_{n} c_{n} cos (n t + φ_{n})$ is not a Fourier–Stieltjes series.

A different selection of naming of null sets results in possibly different notions of randomness. For example, the most commonly used notion of randomness is named after Martin-Löf [22]:
Definition 1.8.
An ML-name of a null $G_{δ}$ set G is a name of a sequence $⟨ U_{n} ⟩$ of open sets satisfying $G = ⋂_{n} U_{n}$ and $μ (U_{n}) ⩽ 2^{- n}$ .4
⁴
Implicit in the definition here is that we are working with a computable measure space $(X, μ)$ . We will only need three examples of these, so do not give a general definition.

We can then similarly define the notion of an ML-null set (being contained in a set with a computable ML-name), ML-randomness (not an element of any ML-null set), and the relativised version when an oracle y is present. This notion of randomness is strictly stronger than Kurtz’s (Kurtz [20]). Given a name of a null $F_{σ}$ set, we can computably produce an ML-name of the same set. Hence, every Kurtz null set is ML-null, and so, every ML-random point is Kurtz random. The converse fails. The distance between these notion is so large, that it is reflected in the non-effective theory: there is a null set which is not contained in a null $F_{σ}$ set (whereas every null set is contained in a null $G_{δ}$ set). This is witnessed computably, in that there is an ML-null set which is not Kurtz null, and indeed, we can find a point in an ML-null set which avoids all Kurtz null sets (See Downey and Hirschfeldt [10], Ch.7, for instance).

We remark that Potgieter’s statement of Theorem 1.7 ([28, Thm.4.1]) refers only to ML-randomness. However, the “computable avoidance” property of Kurtz null sets (Fact 1.3) fails for ML-null sets. In fact, there is a single ML-null set which contains all computable points. Thus, ML-null sets do not suffice to answer Kahane’s question.
1.2. Rademacher series

The Paley–Zygmund theorems were motivated by questions of Rademacher, who, along with Steinhaus [35], seem to be the original people to study random series. Quite aside from their intrinsic interest, random trigonometric series arise quite naturally in, for example, Brownian motion, and random noise in image processing (see for example [14]). Since the seminal Paley–Zygmund papers, the area has flowered into a significant area of analysis (see, for example, [6]).

Rademacher [30] studied the series $\sum x_{n} c_{n}$ , for a given sequence of reals $⟨ c_{n} ⟩$ and randomly chosen $x_{n} \in {- 1, 1}$ . Such a series is called a Rademacher series. Rademacher’s insight was that the convergence or divergence of the random Rademacher series depended on the sum $\sum_{n = 0}^{\infty} c_{n}^{2}$ :

Theorem 1.9 ([30]).

Let $⟨ c_{n} ⟩$ be a sequence of real numbers.

If $\sum c_{n}^{2} = \infty$ then $\sum x_{n} c_{n}$ diverges for almost all $x \in {- 1, 1}^{\infty}$ .

If $\sum c_{n}^{2} < \infty$ then $\sum x_{n} c_{n}$ converges for almost all $x \in {- 1, 1}^{\infty}$ .

Clearly, if $\sum c_{n}^{2} = \infty$ , then choosing $x_{n}$ so as to make $x_{n} c_{n} > 0$ will cause divergence of the Rademacher series. Nevertheless, it seems an interesting project to understand the level of algorithmic randomness needed for convergence/divergence of Rademacher series. To give an answer in the convergent case, we use the following notion of randomness which lies between Kurtz and Martin-Löf randomness:

Definition 1.10.
A Schnorr name of a null $G_{δ}$ set G is a name of a nested sequence $⟨ U_{n} ⟩$ of open sets such that $G = ⋂_{n} U_{n}$ and $μ (U_{n}) = 2^{- n}$ .

As above, we obtain the notions of Schnorr null sets and Schnorr random points. From a name of a null $F_{σ}$ set we can compute a Schnorr name for the set; every Schnorr name of a null set is also an ML-name. Hence ML randomness implies Schnorr randomness implies Kurtz randomness. Unlike with Kurtz, the difference between ML- and Schnorr randomness cannot be expressed classically: both ML-null and Schnorr null sets are types of null $G_{δ}$ sets. Here, the difference is purely computational. A Schnorr name tells us what $μ (U_{n})$ is, while an ML-name witholds that information: we only get an upper bound.

The following holds:
Theorem 1.11.
Let $⟨ c_{n} ⟩$ be a sequence of real numbers and let $x = ⟨ x_{n} ⟩ \in {- 1, 1}^{\infty}$ .
If $\sum c_{n}^{2} = \infty$ and x is Kurtz random relative to $⟨ c_{n} ⟩$ then $\sum x_{n} c_{n}$ diverges.

If $\sum c_{n}^{2} < \infty$ and x is Schnorr random relative to $(⟨ c_{n} ⟩, \sum c_{n}^{2})$ then $\sum x_{n} c_{n}$ converges.

Part (b) was first shown by Ongay-Valverde and Tveite [24]. Potgieter [28] showed that ML-randomness suffices for both cases. In Section 3 we give simplified proofs of both parts.

Note that for part (b), to compute a Schnorr name for the appropriate null set, the information required is not only the sequence $⟨ c_{n} ⟩$ , but also, the value of the sum $\sum c_{n}^{2}$ . In Section 3 we also enquire what happens if this information is not supplied: there, we show that a notion of randomness stronger than Martin-Löf’s suffices. We also consider the question of a “reversal” – is it possible that some level of randomness not only suffices but is actually required?
1.3. Pointwise convergence

Paley and Zygmund also considered pointwise convergence of trigonometric series. They showed:

Theorem 1.12.
Let $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ be a sequences of real numbers.
If $\sum c_{n}^{2} < \infty$ , then for almost all $x \in {- 1, 1}^{\infty}$ , $\sum x_{n} c_{n} cos (n t + φ_{n})$ converges for almost all $t \in [0, 2 π]$ .

If $\sum c_{n}^{2} = \infty$ , then for almost all $x \in {- 1, 1}^{\infty}$ , $\sum x_{n} c_{n} cos (n t + φ_{n})$ diverges for almost all $t \in [0, 2 π]$ .

In Section 4 we study the effective content of these theorems.
1.4. Preliminaries

We follow standard notation and terminology for computability and randomness; standard references are [10,23,33]. We use λ to denote Lebesgue measure on $[0, 2 π]$ . We use μ to denote the “fair-coin” measure on Cantor space, or in general, a computable measure on a space. The spaces we will use are $([0, 2 π], λ)$ ; $({- 1, 1}^{\infty}, μ)$ ; and their product.

We have not given formal details about the coding of real numbers and sequences of real numbers into objects that can be manipulated by Turing machines (usually, elements of Cantor space). The reason is that for our purposes, it makes no difference what particular coding we use. Turing, for example, used binary expansions to define computable real numbers [36]. A more modern approach uses fast-converging Cauchy sequences of rational numbers (see for example [29,38]). It is recognised as a more versatile approach, for example, because it makes addition of real numbers computable.5

⁵
In the correction to [36], Turing realised that binary expansions were a poor model, and essentially used Cauchy sequences. However, in this seminal work he only considered functions acting on the computable reals, whereas the modern “type 2” approach considers realitivised computations, and so functions defined on all reals.

However, for the purposes of convergence or divergence of random series, small perturbations are immaterial. For example, if

| c_{n} - d_{n} | ⩽ 2^{- n}

, then for all

x \in {- 1, 1}^{\infty}

\sum x_{n} c_{n}

converges if and only if

\sum x_{n} d_{n}

converges; this is because

\sum 2^{- n}

converges absolutely. A similar phenomenon holds for being a Fourier–Stieltjes series. Hence, when manipulating an oracle such as a sequence

⟨ c_{n} ⟩

of real numbers, we may assume that we are actually working with a rational approximation of the input. For instance, we can consider the input series

{c_{n} | n \in N}

to consist of rationals represented by some simple coding.

2. Fourier–Stieltjes series

We give a proof of Theorem 1.2.

Proof of Theorem 1.2.
We are given $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ . For each finite binary string $τ = (τ_{0}, τ_{1}, \dots, τ_{m}) \in {- 1, 1}^{m + 1}$ , let the corresponding Fejér sum be $\begin{matrix} σ_{τ} (t) = \sum_{n ⩽ m} (1 - \frac{n}{m}) τ_{n} c_{n} cos (n t + φ_{n}) . \end{matrix}$ This is a continuous function on $[0, 2 π]$ and the functions $σ_{τ}$ for $τ \in {- 1, 1}^{< \infty}$ are uniformly computable relative to $(⟨ c_{n} ⟩, ⟨ φ_{n} ⟩)$ . By [19, Chap.5,Prop.1] (who refers to [39]), for all $x \in {- 1, 1}^{\infty}$ , $\sum x_{n} c_{n} cos (n t + φ_{n})$ is Fourier–Stieltjes if and only if $\begin{matrix} sup_{m} ‖ σ_{x ↾ m} ‖_{1} < \infty, \end{matrix}$ where recall that $‖ f ‖_{1} = \int_{0}^{2 π} | f (t) | d t$ . By [29, Ch.0,Thm.5], the values $‖ σ_{τ} ‖_{1}$ are uniformly computable relative to the data. For each K, let $\begin{matrix} C_{K} = {x \in {- 1, 1}^{\infty} : (\forall m) ‖ σ_{x ↾ m} ‖_{1} ⩽ K} . \end{matrix}$ Then each $C_{K}$ is closed, effectively so given the data. The required $F_{σ}$ set is thus $⋃_{K} C_{K}$ ; this set is null by the classical result that under the assumption, $\sum x_{n} c_{n} cos (n t + φ_{n})$ is not Fourier–Stieltjes for almost all x (see [19, Ch.5,Prop.6]).6
⁶
We remark that Potgieter [28, Thm.4.1] follows the same argument. However, he skips the fact that integration of functions is computable, and as a result his sets $B_{K}$ (the intended complements of our sets $C_{K}$ ) may be too large: having some Riemann sum being greater than K does not ensure that the integral is greater than K; we need to make use of the fact that the functions are uniformly continuous (as a family of functions) to obtain error bounds for the Riemann sums, as is done in [29].

□

For completeness, we provide a proof of Fact 1.3.
Proof of Fact 1.3.
We are given a name of $H = ⋃_{n} F_{n}$ , where each $F_{n}$ is closed and null. We construct a point $x \notin H$ by open approximations. For simplicity, we consider the case that the underlying space is Cantor space ${0, 1}^{\infty}$ . In that case we construct x by specifying ever-longer initial segments of x. We define a sequence $⟨ τ_{n} ⟩$ , starting with $τ_{- 1}$ being the empty string. Given $τ_{n - 1}$ , we let $τ_{n}$ be a proper extension of $τ_{n - 1}$ such that $[τ_{n}] \cap F_{n} = \emptyset$ . This we can do because the name of $F_{n}$ allows us to enumerate the clopen subsets of the complement of $F_{n}$ ; the fact that this complement is co-null implies that it is dense, i.e., every clopen set contains a clopen set disjoint from $F_{n}$ . We let $x = ⋃_{n} τ_{n}$ be the unique point in the intersection of the clopen sets $[τ_{n}]$ . □

We remark that a stronger result holds: Schnorr null sets have the same “computable escaping” property. Here the idea is that since we know $μ (U_{n})$ (where $G = ⋂_{n} U_{n}$ is the null set named), and since we know that $μ (U_{1}) < 1$ , we can construct a point $x \notin U_{1}$ (and so not in G) by keeping $μ (U_{1} | (x ↾ n)) < 1$ for all initial segments $x ↾ n$ of x (here $μ (U | τ)$ denotes the conditional measure). Finding some i such that $μ (U_{1} | (x ↾ n) \hat{} i) < 1$ can be done since we know $μ (U_{1})$ .
3. Rademacher series

3.1. Divergence of Rademacher series

If $\sum c_{n}^{2} = \infty$ then for almost all $x \in {- 1, 1}^{\infty}$ , $\sum x_{n} c_{n}$ diverges. Theorem 1.11(a) says that Kurtz randomness is sufficient. It follows from the following:

Proposition 3.1.
Given $⟨ c_{n} ⟩$ for which $\sum c_{n}^{2} = \infty$ we can (uniformly) compute a name of a null $F_{σ}$ set containing all $x \in {- 1, 1}^{\infty}$ for which $\sum x_{n} c_{n}$ converges.

Following [28, Thm.3.4], we make use of the following Paley–Zygmund inequality (see [19, Ch.3,Thm.3]): for any natural N and sequence of reals $a_{0}, a_{1}, \dots, a_{N - 1}$ , if $\sum_{n < N} a_{n}^{2} > 1 / 4$ then $\begin{matrix} (1) & P {τ \in {- 1, 1}^{N} : | \sum_{n < N} τ_{n} a_{n} | > \frac{1}{2}} > \frac{1}{6}, \end{matrix}$ where $P$ denotes the fair-coin probability measure on ${- 1, 1}^{N}$ . Proof.
Given $⟨ c_{n} ⟩$ with $\sum c_{n}^{2} = \infty$ we can compute a partition of $N$ into intervals $I_{0} < I_{1} < \dots$ (so $min I_{k + 1} = max I_{k} + 1$ ), with each interval $I_{i}$ sufficiently long so that $\begin{matrix} \sum_{n \in I_{i}} c_{n}^{2} > \frac{1}{4} . \end{matrix}$ For each i let $\begin{matrix} C_{i} = {x \in {- 1, 1}^{\infty} : (\forall j ⩾ i) | \sum_{n \in I_{j}} x_{n} c_{n} | ⩽ \frac{1}{2}} . \end{matrix}$ Then each $C_{i}$ is closed and null (it is the product of infinitely many independent clopen sets, each with measure at most $1 / 6$ ). Hence, $H = ⋃_{i} C_{i}$ is a null $F_{σ}$ set with $⟨ c_{n} ⟩$ -computable name, that contains every x for which $\sum x_{n} c_{n}$ converges. □

3.2. Convergence of Rademacher series

For convergence, we use the following Kolmogorov equality (see for example [19, Ch.3,Thm.1]): for any N, sequence of real numbers ${⟨ a_{n} ⟩}_{n < N}$ and any $ε > 0$ , $\begin{matrix} (2) & P {τ \in {- 1, 1}^{N} : max_{m < N} | \sum_{n ⩽ m} τ_{n} a_{n} | > ε} ⩽ \frac{1}{ε^{2}} \sum_{n < N} a_{n}^{2} . \end{matrix}$ The inequality holds for $N = \infty$ as well, in which case we need of course to replace max with sup. With the triangle inequality, we can deduce the following: $\begin{matrix} (3) & P {τ \in {- 1, 1}^{N} : max_{k ⩽ m < N} | \sum_{n = k}^{m} τ_{n} a_{n} | > ε} ⩽ \frac{4}{ε^{2}} \sum_{n < N} a_{n}^{2} . \end{matrix}$ (In fact, the proof of Kolmogorov’s inequality gives the bound $\sum a_{n}^{2} / ε^{2}$ .)

Toward building Schnorr null sets, we use the following:

Fact 3.2.
Given both a name of a nested sequence $⟨ U_{n} ⟩$ of open sets such that $μ (U_{n}) \to 0$ , and the sequence $⟨ μ (U_{n}) ⟩$ , we can compute a Schnorr name of $⋂_{n} U_{n}$ .
Proof.
We enumerate the components $⟨ V_{n} ⟩$ of a Schnorr name inductively. We start with $V_{0}$ being the entire space. For $n > 0$ , given the algorithm for $V_{n - 1}$ , we search for $m = m (n)$ sufficiently large so that $μ (U_{m}) < 2^{- n}$ . We declare that $U_{m (n)} \subseteq V_{n}$ . Once we have enumerated $U_{m}$ up to some small ε of measure, we can add some parts of $V_{n - 1}$ not currently in $V_{n}$ so that the total measure enumerated into $V_{n}$ is $2^{- n} - ε$ . □

As with divergence, Theorem 1.11(b) follows from:
Proposition 3.3.
Given $⟨ c_{n} ⟩$ for which $\sum c_{n}^{2} < \infty$ , and the value of that sum, we can (uniformly) compute a Schnorr name of a null set containing all $x \in {- 1, 1}^{\infty}$ for which $\sum x_{n} c_{n}$ diverges.
Proof.
Given $⟨ c_{n} ⟩$ and $\sum c_{n}^{2}$ , we can compute a partition of $N$ into intervals $I_{0} < I_{1} < \dots$ such that for all $k ⩾ 1$ , $\sum_{n \in I_{k}} c_{n}^{2} < 2^{- 3 k - 2}$ , and so by the extended Kolmogorov inequality (3), $μ (A_{k}) ⩽ 2^{- k}$ , where $\begin{matrix} A_{k} = {x \in {- 1, 1}^{\infty} : max_{J \subseteq I_{k}} | \sum_{n \in J} x_{n} c_{n} | > 2^{- k}}, \end{matrix}$ where the quantification is over all sub-intervals $J \subseteq I_{k}$ . We may assume that the numbers $c_{n}$ are given, uniformly, as rational numbers, rather than computable numbers: if $| d_{n} - c_{n} | ⩽ 2^{- n}$ then for all x, $\sum x_{n} c_{n}$ and $\sum x_{n} d_{n}$ behave in the same way. As a result, we may assume that the sets $A_{k}$ are given as (computable) clopen sets, uniformly in k, given $⟨ c_{n} ⟩$ and $\sum c_{n}^{2}$ .

Let $U_{m} = ⋃_{k > m} A_{k}$ . A name of $⟨ U_{m} ⟩$ can be obtained computably given the data, and $μ (U_{m})$ is computable as well given the data (the set $U_{m, s} = ⋃_{k = m + 1}^{s} A_{k}$ is a clopen set approximating $U_{m}$ to within $2^{- s}$ ). If $x \in {- 1, 1}^{\infty}$ and $\sum x_{n} c_{n}$ diverges then $x \in A_{k}$ for infinitely many k, so $x \in ⋂_{m} U_{m}$ . □
Remark 3.4.
Potgieter [28, Thm.3.2] uses, for each $ε > 0$ , the intersection of the sets $V_{m} = {x : {sup}_{k ⩾ m} | \sum_{n = m}^{k} x_{n} c_{n} | > ε}$ . Using Kolmogorov’s inequality, we can compute a bound on the measure of each $V_{m}$ , and so Potgieter shows that every ML-random x makes $\sum x_{n} c_{n}$ converge. It is not clear how to compute the measure of $V_{m}$ though, so the proof does not give Schnorr randomness. Further, note that this argument does not give a single ML-null (relative to $⟨ c_{n} ⟩$ ) set which captures all “deviant” x’s making $\sum x_{n} c_{n}$ diverge; rather, for each $ε > 0$ , we have an ML-null set $G_{ε}$ , and their union captures all such x’s. In the Schnorr context also, this reminds us that Proposition 3.3 is stronger than Theorem 1.11(b); to prove the latter, we could use infinitely many null sets rather than just one. The union of infinitely many Schnorr null sets may fail to be Schnorr null because it has worse descriptive complexity: it is $G_{δ σ}$ (or $Σ_{3}^{0}$ in the notation of computability/set theory). In terms of convergence, this emphasises that the null set given by Proposition 3.3 captures some x for which $\sum x_{n} c_{n}$ converges (the set of diverging x is again $Σ_{3}^{0}$ , not $G_{δ}$ ). The proof shows that if x is Schnorr random relative to $⟨ c_{n} ⟩$ , then not only does $\sum x_{n} c_{n}$ converge, but we can put an effective upper bound on how quickly this convergence happens.

We also remark that Ongay-Valverde and Tveite [24, Lem.6.7] claim to prove Theorem 1.11(b). They use sophisticated machinery developped by Rute in an unpublished manuscript, rather than directly producing Schnorr null sets. However, it appears that they only prove convergence of a subsequence of the partial sums $\sum_{n ⩽ k} x_{n} c_{n}$ .

What if we are given a sequence $⟨ c_{n} ⟩$ with $\sum c_{n}^{2} < \infty$ , but we are not told what the sum is? We conjecture that Schnorr randomness will not suffice in this case. For an upper bound, we use a notion of randomness slightly stronger than ML-randomness. The following definition uses the notion of a left-c.e. (or lower semicomputable) real number: one which is approximable from below, as a limit of an increasing computable sequence of rational numbers; but which may fail to be computable itself. We use the notion of OW-randomness, first defined in [2].
Definition 3.5.
An OW-null set is a set contained in an intersection $⋂_{n} U_{n}$ , where $⟨ U_{n} ⟩$ is a nested sequence of uniformly enumerable open sets such that for some left-c.e. real α and some increasing computable rational approximation $⟨ α_{n} ⟩$ of α, we have $μ (U_{n}) ⩽ α - α_{n}$ for all n. A real is OW-random if it is a member of no OW-null set.

The idea again is that the intersection is a $G_{δ}$ set with a computable name, but in this case we cannot compute $μ (U_{n})$ , and may not even have any computable upper bound on that measure. Rather, the fact that $μ (U_{n}) \to 0$ is witnessed by the fact that the approximation $α_{n} \to α$ converges. Computably, at very late stages s, we discover that the sets $U_{n}$ for $n < s$ are “allowed to grow” by a large amount (much larger than $2^{- s}$ ). This “amount of growing” eventually goes to 0, but we cannot tell computably how quickly. Proposition 3.6.
Let $⟨ c_{n} ⟩$ be such that $\sum c_{n}^{2} < \infty$ . If $x \in {- 1, 1}^{\infty}$ is OW-random relative to $⟨ c_{n} ⟩$ , then $\sum x_{n} c_{n}$ converges.
Proof.
The simpler proof by Potgieter, discussed in Remark 3.4, works. For each $ε > 0$ and m, let $\begin{matrix} U_{m}^{ε} = {x \in {- 1, 1}^{\infty} : sup_{k ⩾ m} | \sum_{n = m}^{k} x_{n} c_{n} | > ε} . \end{matrix}$ These sets are uniformly effectively open given $⟨ c_{n} ⟩$ . Let $α_{ε} = \frac{1}{ε^{2}} \sum_{n} c_{n}^{2}$ and $α_{ε, m} = \frac{1}{ε^{2}} \sum_{n < m} c_{n}^{2}$ . Then $⟨ α_{ε, m} ⟩$ is an increasing approximation of $α_{ε}$ , and by Kolmogorov’s inequality (2), $μ (U_{m}^{ε}) ⩽ α_{ε} - α_{ε, m}$ , hence $⋂_{m} U_{m}^{ε}$ is OW-null relative to $⟨ c_{n} ⟩$ . If x is OW-random relative to $⟨ c_{n} ⟩$ , then $x \notin ⋃_{ε > 0} ⋂_{m} U_{m}^{ε}$ ; this shows that $\sum x_{n} c_{n}$ converges. □

3.3. Lower bounds

The upper bounds proved in this section raise the natural question: is randomness necessary for typical behaviour for Rademacher series? Here we have in mind results in the literature which characterise notions of randomness using almost-everywhere theorems of analysis, for example:

Theorem 3.7 (Bratkka, Miller, Nies [8]).

A point $x \in [0, 1]$ is ML-random if and only if every computable function $f : [0, 1] \to R$ of bounded variation is differentiable at x.

This is the effective version of Lebesgue’s theorem that every function of bounded variation is differentiable almost everywhere. Similarly, the following is the effective version of Birkhoff’s ergodic theorem:

Theorem 3.8 (Gács, Hoyrup, Rojas [15]).

Let $(X, μ)$ be a computable measure space, and let $T : X \to X$ be computable and ergodic. A point $x \in X$ is Schnorr random if and only if for every computable function $f : X \to R$ , $\begin{matrix} lim_{n \to \infty} \frac{1}{n} \sum_{i < n} f (T^{i} x) = \int f d μ . \end{matrix}$

Is it possible, for example, that Theorem 1.11(a) characterises Kurtz randomness? To show that, a natural approach would be to take a Kurtz null set A and somehow produce a computable sequence $⟨ c_{n} ⟩$ with $\sum c_{n}^{2} = \infty$ and $\sum x_{n} c_{n}$ convergent for all $x \in A$ . Currently, such a “reversal” is not known, and it is suspected that typicality with respect to convergence and divergence of Rademacher series is in fact a new phenomenon in computability theory, not equivalent to any known randomness notion. We have the following partial converse.

Proposition 3.9.
Suppose that $P \subset {- 1, 1}^{\infty}$ is effectively closed, and that there is a computable tree $T \subset {- 1, 1}^{< \infty}$ such that $P = [T]$ and for all n, T contains fewer than ${log}_{2} n$ many strings of length n. Then there is a computable sequence $⟨ c_{n} ⟩$ such that $\sum c_{n}^{2} = \infty$ , but $\sum x_{n} c_{n}$ converges for all $x \in P$ .

Such an effectively closed set must be null, as ${log}_{2} n / 2^{n} \to 0$ , and so (as is necessary) no $x \in P$ is Kurtz random. We note that the very small effectively closed sets of [3] have this property.
Proof.
Let $I_{k} = [2^{k}, 2^{k + 1})$ . For each k, since there are at most k strings of length $2^{k + 1}$ in T, there is some $n_{k} \in I_{k}$ such that $τ_{n_{k}}$ is a constant value $i_{k}$ for all $τ \in T$ of length $2^{k + 1}$ . We let $c_{n_{k}} = {(- 1)}^{k} i_{k} / \sqrt{k}$ and $c_{n} = 0$ if $n \neq n_{k}$ for all k. □

The following lower bound is also weaker than randomness. A sequence $x \in {- 1, 1}^{\infty}$ is bi-immune if neither ${n : x_{n} = 1}$ nor its complement ${n : x_{n} = - 1}$ contain an infinite computable set (equivalently, an infinite computably enumerable set). All Kurtz random sequences are bi-immune.
Proposition 3.10.
If x is not bi-immune then there is a computable sequence $⟨ c_{n} ⟩$ with $\sum c_{n}^{2} = \infty$ but $\sum x_{n} c_{n}$ converges.
Proof.
Let A be an infinite computable set such that either $x_{n} = 1$ for all $n \in A$ , or $x_{n} = - 1$ for all $n \in A$ . Let $n_{1}, n_{2}, \dots$ be the increasing enumeration of the elements of A. Let $c_{n_{k}} = {(- 1)}^{k} / \sqrt{k}$ ; if $n \neq n_{k}$ for any k let $c_{n} = 0$ . □

A similar approach in both cases (say setting $c_{n_{k}} = 1 / k$ ) also shows atypicality with respect to convergence: for all x in P as in Proposition 3.9, and all x which are not bi-immune, we can find a computable $⟨ c_{n} ⟩$ with $\sum c_{n}^{2} < \infty$ and computable, but $\sum x_{n} c_{n}$ divergent.
4. Pointwise convergence and divergence of trigonometric series

Paley and Zygmund studied the pointwise convergence and divergence of random trigonometric series. As mentioned, they showed, for example, that if $\sum c_{n}^{2} = \infty$ then for almost all $x \in {- 1, 1}^{\infty}$ , $\sum x_{n} c_{n} cos (n t + φ_{n})$ diverges for almost all $t \in [0, 2 π]$ . The first natural question in the effective realm is to ask, how much randomness of x ensures that $\sum x_{n} c_{n} cos (n t + φ_{n})$ diverges almost everywhere. This was addressed by Potgieter [28, Lem.4.1], stating that ML-randomness suffices. While being a little opaque, his proof seems to extend to Kurtz randomness.

We can refine the question by asking not only for almost everywhere divergence, but also, what level of randomness of t ensures this divergence. This leads us to consider randomness in the product space ${- 1, 1}^{\infty} \times [0, 2 π]$ , which is defined as expected, using the product measure $μ \times λ$ .

Theorem 4.1.
Let $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ be sequences of real numbers, and suppose that $\sum c_{n}^{2} = \infty$ . If $(x, t) \in {- 1, 1}^{\infty} \times [0, 2 π]$ is Schnorr random relative to $(⟨ c_{n} ⟩, ⟨ φ_{n} ⟩)$ then $\sum x_{n} c_{n} cos (n t + φ_{n})$ diverges.

We do not know as yet whether Kurtz randomness suffices. We note that this theorem implies that if x is Schnorr random then $\sum x_{n} c_{n} cos (n t + φ_{n})$ diverges almost everywhere.
Proof.
For brevity, let $ξ_{n} (t) = cos (n t + φ_{n})$ . By [19, Ch.5,Prop.4], for almost all $t \in [0, 2 π]$ , $\sum ξ_{n}^{2} (t) = \infty$ . The set R of t for which this fails is $F_{σ}$ , with a name computable in the data $(⟨ c_{n} ⟩, ⟨ φ_{n} ⟩)$ , and so, if $t \in [0, 2 π]$ is Kurtz random relative to the data then $t \notin R$ .

Let $Φ : {0, 1}^{ω} \to [0, 2 π]$ be the stretching by a factor of $2 π$ of the usual binary representation of reals in the unit interval: formally, $Φ (y) = 2 π \sum_{n ⩾ 0} y_{n} 2^{- (n + 1)}$ . For each finite binary string $σ \in {0, 1}^{< \infty}$ , we let $[[σ]] = Φ [σ]$ be the image under Φ of the clopen set $[σ]$ ; it is a closed interval of length $2 π 2^{- | σ |}$ , where $| σ |$ denotes the length of σ.

For each σ and $m ⩽ | σ |$ we can compute ${min}_{t \in [[σ]]} ξ_{m}^{2} (t)$ : these functions are uniformly computable (given the data $(⟨ c_{n} ⟩, ⟨ φ_{n} ⟩)$ ), and as continuous functions on these closed intervals obtain minima; these minima are uniformly computable, see [29, Ch.0,Thm.7]. Based on these minima, we can inductively (on σ) compute intervals $I_{0, σ} < I_{1, σ} < \dots < I_{k (σ), σ}$ which for each σ partition an initial segment of $N$ , and have the following properties:
For all σ, all $k ⩽ k (σ)$ and all $t \in [[σ]]$ , $\sum_{n \in I_{k, σ}} ξ_{n}^{2} (t) > 1 / 4$ ;

If $σ ≼ τ$ (τ extends σ) then $k (σ) ⩽ k (τ)$ and for all $k ⩽ k (σ)$ , $I_{k, σ} = I_{k, τ}$ ;

If $t = Φ (y)$ and $t \notin R$ (so $\sum ξ_{n}^{2} (t) = \infty$ ) then ${lim}_{n} k (y ↾ n) = \infty$ .

Now, for each pair $m ⩽ N$ , let $\begin{matrix} C_{[m, N]} = {(x, Φ (y)) : (\exists σ ≺ y) k (σ) ⩾ N & (\forall k \in [m, N]) | \sum_{n \in I_{k, σ}} x_{n} ξ_{n} (t) | ⩽ \frac{1}{2}} . \end{matrix}$

Each $C_{[m, N]}$ is open (with name uniformly computable in the data), the $(μ \times λ)$ -measure of $C_{[m, N]}$ is bounded by ${(1 / 6)}^{N - m}$ (using (1)), and this measure is uniformly computable from the data. Hence, for each m, $⋂_{N} C_{[m, N]}$ is Schnorr null relative to the data.

Suppose that $(x, t)$ is Schnorr random relative to the data. Then t is Schnorr random, hence Kurtz random, so $t \notin R$ , and t is not a “binary rational” $2 π k 2^{- n}$ of the interval $[0, 2 π]$ , i.e., $y = Φ^{- 1} (t)$ is well-defined, and $k (y ↾ n) \to \infty$ . This, together with $(x, t) \notin ⋃_{m} ⋂_{N} C_{[m, N]}$ implies the divergence of $\sum x_{n} ξ_{n} (t)$ . □

For convergence, the situation is much simpler. Theorem 4.2.
Let $⟨ c_{n} ⟩$ and $⟨ φ_{n} ⟩$ be sequences of real numbers, and suppose that $\sum c_{n}^{2} < \infty$ . If $(x, t) \in {- 1, 1}^{\infty} \times [0, 2 π]$ is Schnorr random relative to $(⟨ c_{n} ⟩, ⟨ φ_{n} ⟩, \sum c_{n}^{2})$ then $\sum x_{n} c_{n} cos (n t + φ_{n})$ converges.
Proof.
Define $ξ_{n}$ as above. The main point is that since $| cos (n t + φ_{n}) | ⩽ 1$ , for all $t \in [0, 2 π]$ we have $\sum ξ_{n}^{2} (t) < \infty$ , indeed these are uniformly bounded by $\sum c_{n}^{2}$ . Hence, we can apply the proof of Proposition 3.3. We define the intervals $I_{0} < I_{1} < \dots$ in the same way, and unlike the previous proof, they do not depend on t. The sets $\begin{matrix} A_{k} = {(x, t) : max_{J \subseteq I_{k}} | \sum_{n \in J} x_{n} ξ_{n} (t) | > 2^{- k}} \end{matrix}$ are open and have $(μ \times λ)$ -measue bounded by $2^{- k}$ (by Fubini’s theorem). The rest of the proof follows that of Proposition 3.3. □

5. Further lines of investigation

It seems to us that there are many opportunities for further research in this area. To begin, one can follow the rich literature on random series. One can discuss convergence in $L_{p}$ , or convergence to continuous functions (Billard’s theorem, see [19, Ch.5]).

There are other aspects of computability theory which pertain to this topic. One can, for example, ask about the complexity of the collection of $x \in {- 1, 1}^{\infty}$ which display typical behaviour with respect to convergence or divergence of Rademacher series or trigonometric series. This complexity could be measured by the Medvedev or Muchnik lattice of sets of reals (see for example [32,34]); here we would consider typical behaviour with respect to computable series.

A more nuanced approach involves the Weihrauch lattice [7,16]. Here we formulate “problems”, which are binary relations between “instances” and “solutions”. For example, one such problem could be that of Rademacher convergence: an instance is a sequence $⟨ c_{n} ⟩$ (not necessarily computable) such that $\sum c_{n}^{2} < \infty$ ; a solution is any $x \in {- 1, 1}^{\infty}$ which makes $\sum x_{n} c_{n}$ converge. Weihrauch reducibility (along with its strong form) is a tool for comparing the complexity of such problems.

Framing the study in terms of Weihrauch problems is related to that of the Medvedev lattice: every Weihrauch problem is associated with both a “highness class” and a “nonlowness class” in the Medvedev lattice. For example, for the Rademacher convergence problem, the highness class is the collection of oracles computing $x \in {- 1, 1}^{\infty}$ which make every computable instance $⟨ c_{n} ⟩$ converge. The non-lowness class is the collection of oracles computing a series $⟨ c_{n} ⟩$ with no computable solution x.

The same view is related to the study of cardinal characteristics of the continuum in set theory. Indeed, this was the motivation in [24]: Theorem 1.11(b) is used there to build a strong Weihrauch reduction from the “Schnorr capturing” problem to the “rearrangement problem”. This immediately implies two theorems, one in set theory and one in computability: the null covering number $cov (N)$ is bounded by the “rearrangement number” $rr$ (see [4]); every Schnorr random degree is “imperturbable”. In the case of Rademacher convergence, for example, the associated cardinal is the smallest size of a subset $A \subseteq {- 1, 1}^{\infty}$ such that whenever $\sum c_{n}^{2} < \infty$ , there is some $x \in A$ which makes $\sum x_{n} c_{n}$ converge. For a detailed discussion of the connection between (strong) Weihrauch reducibility, cardinal characteristics, and non-lowness notions, see [17].

Footnotes

Acknowledgements

Downey and Greenberg were partially supported by the Marsden Fund of New Zealand. Greenberg was partially supported by a Rutherfod Discovery Fellowship.

References

Angst and

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.

Bienvenu,

Greenberg,

Kučera,

Nies and

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.

Binns, Small

π_{1}^{0}

classes, Archive for Mathematical Logic45(4) (2005), 393–410. doi:10.1007/s00153-005-0319-6.

Blass,

Brendle,

Brian,

J.D.

Hamkins,

Hardy and

P.B.

Larson, The rearrangement number, Trans. Amer. Math. Soc.373(1) (2020), 41–69. doi:10.1090/tran/7881.

Bollobás, Random Graphs, 2nd edn, Cambridge Studies in Advanced Mathematics, Vol. 73, Cambridge University Press, Cambridge, 2001.

Bonami and

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.

Brattka and

Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic76(1) (2011), 143–176. doi:10.2178/jsl/1294170993.

Brattka,

J.S.

Miller and

Nies, Randomness and differentiability, Trans. Amer. Math. Soc.368(1) (2016), 581–605. doi:10.1090/tran/6484.

Cohen and

Cuny, On random almost periodic trigonometric polynomials and applications to ergodic theory, Annals of Probability34 (2006), 39–79.

10.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010.

11.

Downey and

D.R.

Hirschfeldt, Algorithmic randomness, Communications of the ACM62(5) (2019), 70–80. doi:10.1145/3319408.

12.

Downey and

D.R.

Hirschfeldt, Computability and randomness, Notices of the American Mathematical Society66(07) (2019), 1. doi:10.1090/noti1905.

13.

Downey,

D.R.

Hirschfeldt,

Nies and

Terwijn, Calibrating randomness, Bulletin of Symbolic Logic12 (2006), 411–491. doi:10.2178/bsl/1154698741.

14.

Filip,

Javeed and

L.N.

Trefethen, Smooth random functions, random codes, and Gaussian processes, SIAM Review61(1) (2019), 185–205. doi:10.1137/17M1161853.

15.

Gács,

Hoyrup and

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.

Gherardi and

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.

Greenberg,

Kuyper and

Turetsky, Cardinal invariants, non-lowness classes, and Weihrauch reducibility, Computability8(3–4) (2019), 305–346. doi:10.3233/COM-180219.

18.

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.

Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois at Urbana-Champaign, 1981.

21.

Li and

Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer International Publishing, 2019.

22.

Martin-Löf, The definition of random sequences, Information and Control9(6) (1966), 602–619. doi:10.1016/S0019-9958(66)80018-9.

23.

Nies, Computability and Randomness, Oxford University Press, 2012.

24.

Ongay-Valverde and

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

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

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

Zygmund, On some series of functions, (3), Mathematical Proceedings of the Cambridge Philosophical Society28(2) (1932), 190–205. doi:10.1017/S0305004100010860.

28.

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.

Rademacher, Einige sätze über reihen von allgemeinen orthogonalfunktionen, Mathematische Annalen87 (1922), 112–138. doi:10.1007/BF01458040.

31.

Salem and

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.

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.

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.

Wang, Randomness and complexity, PhD thesis, University of Heidelberg, 1996.

38.

Weihrauch, Computable Analysis: An Introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.

39.

Zygmund, Trigonometric Series, Vol. 1, Cambridge University Press, 1959.