Algorithmic Randomness and Fourier Analysis

Abstract

Suppose 1 < p < ∞. Carleson’s Theorem states that the Fourier series of any function in L^p[−π, π] converges almost everywhere. We show that the Schnorr random points are precisely those that satisfy this theorem for every f ∈ L^p[−π, π] given natural computability conditions on f and p.

1 Introduction

Recent discoveries have shown that algorithmic randomness has a very natural connection with classical analysis. Many theorems in analysis have the form “For almost every x, …”; the set of points for which the central claim of the theorem fails for a given choice of parameters is called an exceptional set of the theorem. For example, one of Lebesgue’s differentiation theorems states that if f is a monotone function on [0,1], then f is differentiable almost everywhere. In this case, for each monotone function f on [0,1], the set of points at which f is not differentiable is an exceptional set. On the other hand, every natural randomness notion is characterized by a conull class of points. This suggests it is possible to characterize the points that satisfy a particular theorem in analysis in terms of a randomness notion. Put another way, it may be the case that exceptional sets of a theorem can be used to characterize a standard notion of randomness.

To date, results of this nature have been discovered in ergodic theory [4, 19, 20, 22, 26, 36, 51], differentiability [5, 7, 21, 27, 36, 40, 43], Brownian motion [1, 2, 18], and other topics in analysis [3, 9, 46]. In this paper, we add Fourier series to this list by considering Carleson’s Theorem. The original version of this theorem was proven in 1966 by L. Carleson for L² functions [10]; we will consider an extension of this theorem to L^p functions for p > 1 that is due to Hunt but still generally referred to as Carleson’s Theorem [28]. Throughout this paper we only consider the complex version of L^p[−π, π]; that is, we work in the space of all measurable $f : [-\pi , \pi ] \rightarrow \mathbb {C}$ so that ${\int }_{-\pi }^{\pi } |f(t)|^{p}\ dt < \infty$.

Carleson’s Theorem

Suppose 1 < p < ∞.If f is a function inL^p[−π, π],then the Fourier series of f converges to f almost everywhere.

Suppose 1 < p < ∞. It is well known that the Fourier series of any f ∈ L^p[−π, π] converges to f in the L^p-norm. It follows that if the Fourier series of f ∈ L^p[−π, π] converges almost everywhere, then it converges to f almost everywhere.

We consider Carleson’s Theorem in the context of computable analysis and demonstrate the points that satisfy this theorem are precisely the Schnorr random points via the following two theorems.

Theorem 1.1

Supposep > 1 is a computable real. Ift₀ ∈ [−π, π] is Schnorr random and f is a computable vector inL^p[−π, π],then the Fourier series for f converges att₀.

Theorem 1.2

Ift₀ ∈ [−π, π] is not Schnorr random, then there is a computablefunction$f : [-\pi , \pi ] \rightarrow \mathbb {C}$whoseFourier series diverges att₀.

It is well known that when p ≥ 1 is a computable real, there are incomputable functions in L^p[−π, π] that are nevertheless computable as vectors, e.g., step functions. Thus, Theorem 1.2 is considerably stronger than the converse of Theorem 1.1. To the best of our knowledge, Theorems 1.1 and 1.2 yield the first characterization of a randomness notion via a theorem of Fourier analysis. The proofs reveal some interesting and sometimes surprising connections between topics from algorithmic randomness such as Schnorr integral tests and topics from classical analysis such as analytic and harmonic function theory. In particular, our proof of Theorem 1.1 combines Miyabe’s integral tests with an inequality due to Fefferman and thereby sidesteps the surely arduous task of effectivizing a classical proof of Carleson’s Theorem.

The paper is organized as follows. In Section 2, we present the necessary background. Sections 3 and 4 contain the proofs of Theorems 1.1 and 1.2, respectively. In Sections 5 and 6 we give two variations of Theorem 1.1. The first variation characterizes the values to which the Fourier series converges. The second variation addresses the Fejér-Lebesgue Theorem which is similar to Carleson’s Theorem, but also applies to the L¹ case. Section 7 contains a broader analysis of our results.

2 Background and Preliminaries

We begin with the necessary topics from analysis and then discuss computable analysis and algorithmic randomness. We assume the reader is familiar with classical computability in discrete settings as expounded in [12, 41, 42, 47].

2.1 Fourier Analysis

We begin with some notation. For all $n \in \mathbb {Z}$ and t ∈ [−π, π], let e_n(t) = e^int. For all $n \in \mathbb {Z}$ and f ∈ L¹[−π, π], let

$$c_{n}(f) = \frac{1}{2\pi} {\int}_{-\pi}^{\pi} f(t) e^{-i n t} dt. $$

For all f ∈ L¹[−π, π] and all $N \in \mathbb {N}$, let

$$S_{N}(f) = \sum\limits_{n = -N}^{N} c_{n}(f) e_{n}. $$

That is, S_N(f) is the (N + 1)^st partial sum of the Fourier series of f. We say that f ∈ L¹[−π, π] is analytic if c_n(f) = 0 whenever n < 0.

In C. Fefferman’s proof of Carleson’s Theorem, he showed that when 1 < p < ∞, there is a constant C so that

$$\left\| \sup_{N} |S_{N}(f)| \right\|_{1} \leq C \| f \|_{p} $$

for all f ∈ L^p[−π, π] [15, 16]. We can (and do) assume that C is a positive integer. The operator f↦supN|S_N(f)| is known as the Carleson operator. This estimate will be a key component of the proof of Theorem 1.1.

Let $E = \{e_{n}\ :\ n \in \mathbb {Z}\}$. A trigonometric polynomial is a function in the linear span of E. If p is a trigonometric polynomial, then the degree of p is the smallest $d \in \mathbb {N}$ so that S_d(p) = p.

2.2 Complex Analysis

We now summarize the required information on analytic and harmonic functions, in particular harmonic measure. This material will be used exclusively in Section 4 (the proof of Theorem 1.2). More expansive treatments of analytic and harmonic functions can be found in [11] and [38]; the material on harmonic functions is drawn from [24].

Suppose $U \subseteq \mathbb {C}$ is open and connected. Recall that a function $f : U \rightarrow \mathbb {C}$ is analytic if it has a power series expansion at each point of U; equivalently, if f is differentiable at each z₀ ∈ U in the sense that

$$\lim_{z \rightarrow z_{0}} \frac{f(z) - f(z_{0})}{z - z_{0}} $$

exists.

Let $\mathbb {D}$ denote the open unit disk, and let λ denote Lebesgue measure on the unit circle. The points on the unit circle are called the unimodular points. When f is analytic on $\mathbb {D}$, let

$$a_{n}(f) = \frac{f^{(n)}(0)}{n!} $$

for all $n \in \mathbb {N}$. That is, a_n(f) is the (n + 1)^st coefficient of the MacLaurin series of f. Thus,

$$f(z) = \sum\limits_{n = 0}^{\infty} a_{n}(f) z^{n} $$

for all $z \in \mathbb {D}$.

Now we turn our attention to harmonic functions. Again, let U be a subset of the plane that is open and connected. Recall that a function $u : U \rightarrow \mathbb {R}$ is harmonic if it is twice continuously differentiable and satisfies Laplace’s equation

$$\frac{\partial^{2} u}{\partial x^{2}} + \frac{\partial^{2} u}{\partial y^{2}} = 0. $$

When u is harmonic on $\mathbb {D}$, let $\tilde {u}$ denote the harmonic conjugate of u that maps 0 to 0. That is, $\tilde {u}$ is the harmonic function on $\mathbb {D}$ so that $\tilde {u}(0) = 0$ and so that u and $\tilde {u}$ satisfy the Cauchy-Riemann equations:

$$\frac{\partial u}{\partial x} = \frac{\partial \tilde{u}}{\partial y}\ \ \ \frac{\partial u}{\partial y} = - \frac{\partial \tilde{u}}{\partial x}. $$

Let $\hat {u} = u + i \tilde {u}$. Thus, $\hat {u}$ is analytic and is called the analytic extension of u.

When U is a relatively open subset of the unit circle, there is a harmonic function u on the unit disk so that whenever $\zeta \in \partial \mathbb {D}$ is not a boundary point of U, $\lim _{z \rightarrow \zeta } u(z) = \chi _{U}(\zeta )$ (where χ_A denotes the characteristic function of A); let $\omega (z, U, \mathbb {D}) = u(z)$. If we fix $z \in \mathbb {D}$, then $\omega (z, \cdot , \mathbb {D})$ extends to a Borel probability measure on the unit circle. Accordingly, the quantity $\omega (z, B, \mathbb {D})$ is called the harmonic measure ofBatz. Moreover, $\omega (0, B, \mathbb {D}) = (2\pi )^{-1}\lambda (B)$ [24].

An explicit formula for the harmonic measure of an open arc on the unit circle can be obtained as follows. Let Log denote the principal branch of the complex logarithm. That is,

$$\operatorname{Log}(z) = {{\int}_{1}^{z}} \frac{1}{\zeta} d\zeta $$

for all points z that do not lie on the negative real axis. Let Arg = Im(Log). Suppose A = {e^i𝜃 : 𝜃₁ < 𝜃 < 𝜃₂} where − π < 𝜃₁ < 𝜃₂ < π. Then

$$\omega(z, A, \mathbb{D}) = \frac{1}{\pi} \operatorname{Arg}\left( \frac{z - e^{i \theta_{2}}}{z - e^{i \theta_{1}}}\right) - \frac{1}{2\pi}(\theta_{2} - \theta_{1}). $$

(See Exercise 1 on p. 26 of [24].) It follows that

$$\begin{array}{@{}rcl@{}} \tilde{\omega}(z, A, \mathbb{D}) & = & \frac{1}{\pi} \ln\left| \frac{z - e^{i \theta_{2}}}{z - e^{i \theta_{1}}} \right|\text{ and} \end{array} $$

(2.1)

$$\begin{array}{@{}rcl@{}} \hat{\omega}(z, A, \mathbb{D}) & = & \frac{1}{\pi i} \operatorname{Log}\left( \frac{z - e^{i \theta_{2}}}{z - e^{i \theta_{1}}} \right) - \frac{1}{2\pi} (\theta_{2} - \theta_{1}). \end{array} $$

(2.2)

2.3 Computable Analysis

We now use the classical concepts of computability in a discrete setting to define the concept of computability in a continuous setting.

A complex number z is computable if there is an algorithm that, given a nonnegative integer k as input, computes a rational point q so that |q − z| < 2^−k. A sequence $\{a_{n}\}_{n \in \mathbb {Z}}$ of points in the plane is computable if there is an algorithm that, given an $n \in \mathbb {Z}$ and a $k \in \mathbb {N}$ as input, computes a rational point q so that |a_n − q| < 2^−k.

Let us call a trigonometric polynomial τrational if each of its coefficients is a rational point.

Definition 2.1

Suppose p ≥ 1 is a computable real and suppose f ∈ L^p[−π, π]. Then f is a computable vector ofL^p[−π, π] if there is an algorithm that, given $k \in \mathbb {N}$ as input, computes a rational polynomial τ so that ∥f − τ∥_p < 2^−k.

In other words, a vector f ∈ L^p[−π, π] is computable if it is possible to compute arbitrarily good approximations of f by rational trigonometric polynomials.

The next proposition states the fundamental computability results we shall need about vectors in L^p[−π, π].

Proposition 2.2

Supposep ≥ 1 is acomputable real andf ∈ L^p[−π, π].

• (1) If f is a computable vector, then∥f∥_pand$\{c_{n}(f)\}_{n \in \mathbb {Z}}$arecomputable.

• (2) Ifp = 2,then f is a computable vector if both∥f∥₂and$\{c_{n}(f)\}_{n \in \mathbb {Z}}$arecomputable.

Proof 1

Suppose τ is a rational trigonometric polynomial. The L^p-norm of τ can be computed directly from τ. Since |∥f∥_p −∥τ∥_p|≤∥f − τ∥_p, it follows that ∥f∥_p is computable. We also have

$$\begin{array}{@{}rcl@{}} |c_{n}(f) - c_{n}(\tau)|^{p} & =& \left| {\int}_{-\pi}^{\pi} (f(\theta) - \tau(\theta))e^{i n \theta}\frac{d\theta}{2\pi} \right|^{p} \\ & \leq& \left( {\int}_{-\pi}^{\pi} |f(\theta) - \tau(\theta)| \frac{d\theta}{2\pi}\right)^{p}\\ & \leq& {\int}_{-\pi}^{\pi} \left|f(\theta) - \tau(\theta)\right|^{p}\frac{d\theta}{2\pi}=\| f - \tau \|_{p}^{p}, \end{array} $$

where the last step is by Jensen’s Inequality. It follows that $\{c_{n}(f)\}_{n \in \mathbb {Z}}$ is computable.

Now suppose p = 2 and suppose $\{c_{n}(f)\}_{n \in \mathbb {Z}}$ and ∥f∥₂ are computable. Since $\| f \|_{2}^{2} = {\sum }_{n \in \mathbb {Z}} |c_{n}(f)|^{2}$ and $\| f - S_{N}(f) \|_{2}^{2} = {\sum }_{|n| > N} |c_{n}(f)|^{2}$, it follows that f is a computable vector in L²[−π, π]. □

The following corollary shows that the computability of a vector in L^p[−π, π] is distinct from the computability of its Fourier coefficients.

Corollary 2.3

There is an incomputable vectorf ∈ L²[−π, π] so that$\{c_{n}(f)\}_{n \in \mathbb {Z}}$iscomputable.

Proof 2

Let $\{r_{n}\}_{n \in \mathbb {N}}$ be any computable sequence of positive rational numbers so that ${\sum }_{n = 0}^{\infty } {r_{n}^{2}}$ is incomputable. (The existence of such a sequence follows from the constructions of E. Specker [49].) Set $f = {\sum }_{n = 0}^{\infty } r_{n} e_{n}$. Then $\| f \|_{2}^{2} = {\sum }_{n = 0}^{\infty } {r_{n}^{2}}$ is incomputable. Thus, by Proposition 2.2, f is incomputable. □

We now discuss computability of planar sets and functions. A comprehensive treatment of the computability of functions and sets in continuous settings can be found in [52]; the reader may also see [6, 25, 32, 33, 44, 50], and [8]. To begin, an interval is rational if its endpoints are rational numbers. An open (closed) rational rectangle is a Cartesian product of open (closed) rational intervals.

A subset of the plane U is computably open if it is open and the set of all closed rational rectangles that are included in U is computably enumerable. On the other hand, an open subset X of the real line is computably open if the set of all closed rational intervals that are included in X is computably open. A sequence of open sets of reals $\{U_{n}\}_{n \in \mathbb {N}}$ is computable if U_n is computably open uniformly in n; that is, if there is an algorithm that, given any $n \in \mathbb {N}$ as input, produces an algorithm that enumerates the closed rational intervals included in U_n.

Suppose X is a compact subset of the plane. A minimal cover of X is a finite sequence of open rational rectangles (R₀,…, R_m) so that $X \subseteq \bigcup _{j} R_{j}$ and so that X ∩ R_j≠∅ for all j ≤ m. We say that X is computably compact if the set of all minimal covers of X is computably enumerable.

Suppose f is a function that maps complex numbers to complex numbers. We say that f is computable if there is an algorithm P that satisfies the following three criteria.

• Approximation: Whenever P is given an open rational rectangle as input, it either does not halt or produces an open rational rectangle as output. (Here, the input rectangle is regarded as an approximation of some z ∈dom(f) and the output rectangle is regarded as an approximation of f (z).)

• Correctness: Whenever P halts on an open rational rectangle R, the rectangle it outputs contains f (z) for each z ∈ R ∩ dom(f).

• Convergence: Suppose U is a neighborhood of a point z ∈ dom(f) and that V is a neighborhood of f (z). Then, there is an open rational rectangle R such that R contains z, R is included in U, and when R is put into P, P produces a rational rectangle that is included in V.

For example, sin, cos, and exp are computable as can be seen by considering their power series expansions and the bounds on the convergence of these series that can be obtained from Taylor’s Theorem. A consequence of this definition is that computable functions on the complex plane must be continuous.

A sequence of functions $\{f_{n}\}_{n \in \mathbb {N}}$ of a complex variable is computable if it is computable uniformly in n; that is, there is an algorithm that given any $n \in \mathbb {N}$ as input produces an algorithm that computes f_n.

It is well known that integration is a computable functional on C[0,1]. It follows that when f is a computable analytic function on the unit disk, the sequence $\{a_{n}(f)\}_{n \in \mathbb {N}}$ of Maclaurin coefficients is computable uniformly in f. It also follows that Log is computable.

A modulus of convergence for a sequence $\{a_{n}\}_{n \in \mathbb {N}}$ of points in a complete metric space (X, d) is a function $g : \mathbb {N} \rightarrow \mathbb {N}$ so that d (a_m, a_n) < 2^−k whenever m, n ≥ g (k). Thus, a sequence of points in a complete metric space converges if and only if it has a modulus of convergence. Suppose p ≥ 1 is computable. If $\{f_{n}\}_{n \in \mathbb {N}}$ is a computable and convergent sequence of vectors in L^p[−π, π], then $\lim _{n} f_{n}$ is a computable vector if and only if $\{f_{n}\}_{n \in \mathbb {N}}$ has a computable modulus of convergence.

Suppose f is a uniformly continuous computable function that maps complex numbers to complex numbers. A modulus of uniform continuity for f is a function $m : \mathbb {N} \rightarrow \mathbb {N}$ so that |f (z₀) − f (z₁)| < 2^−k whenever z₀, z₁ ∈ dom(f) and |z₀ − z₁|≤ 2^{−m (k)}. If the domain of f is computably compact, then f has a computable modulus of uniform continuity.

Suppose $\{a_{n}\}_{n \in \mathbb {N}}$ is a sequence of complex numbers so that ${\sum }_{n = 0}^{\infty } a_{n} z^{n}$ converges whenever |z| < 1, and suppose G is a compact subset of the unit disk. A modulus of uniform convergence for this series on G is a function $m : \mathbb {N} \rightarrow \mathbb {N}$ so that $\left | {\sum }_{n = m(k)}^{\infty } a_{n} z^{n}\right | < 2^{-k}$ whenever z ∈ G and $k \in \mathbb {N}$. If the sequence $\{a_{n}\}_{n \in \mathbb {N}}$ is computable and if G is computably compact, then the series ${\sum }_{n = 0}^{\infty } a_{n} z^{n}$ has a computable modulus of uniform convergence on G.

We note that when p ≥ 1 is a computable real and f ∈ L^p[−π, π], there are two senses in which f can be “computable”: as a vector and as a function. These fail to coincide. By definition, a computable function is continuous. However, there are discontinuous functions in L¹[−π, π] that are computable as vectors; e.g., the greatest integer function. Moreover, there are continuous functions in L¹[−π, π] that are computable as vectors but not as functions.

Lastly, a lower semicomputable function is a function T : [−π, π] → [0, ∞] that is the sum of a computable sequence of nonnegative real-valued functions.

2.4 Algorithmic Randomness

There are three different approaches to defining the concept of randomness formally. The one we will find useful for this paper is the measure-theoretic one: A random point in a given probability space is said to be random if it avoids all null classes generated in a certain way by computably enumerable functions. Thus, for any reasonable randomness notion, the class of random points is conull. For a general introduction to algorithmic randomness, see [14] or [39].

While the most-studied randomness notion is Martin-Löf randomness, a weaker notion, Schnorr randomness, lies at the heart of our paper. Schnorr randomness, like most other randomness notions, was originally defined in the Cantor space 2^ω with Lebesgue measure [48]; however, the definition is easily adaptable to any computable measure space, in particular [−π, π] with the Lebesgue measure μ.

Definition 2.4

A Schnorr test is a computable sequence $\{ V_{n}\}_{n \in \mathbb {N}}$ of open sets of reals so that μ (V_n) ≤ 2⁻ⁿ for all n and so that the sequence $\{\mu (V_{n})\}_{n \in \mathbb {N}}$ is computable. A real number x is said to be Schnorr random if for every Schnorr test $\{ V_{n}\}_{n \in \mathbb {N}}$, $x\not \in \bigcap _{n} V_{n}$.

There are many other characterizations of Schnorr randomness, such as a complexity-based characterization [13] and a martingale characterization [48]. In this paper, we will use an integral test characterization due to Miyabe [35] which is rooted in computable analysis.

Definition 2.5

A Schnorr integral test is a lower semicomputable function T : [−π, π] → [0, ∞] so that ${\int }_{-\pi }^{\pi } T\ d\mu$ is a computable real.

Thus, if T is a Schnorr integral test, then T (x) is finite for almost every x ∈ [−π, π]. Miyabe’s characterization states that x ∈ [−π, π] is Schnorr random if and only if T (x) < ∞ for every Schnorr integral test T.

3 Proof of Theorem 1.1

Our proof of Theorem 1.1 is based on the following definition and lemmas.

Definition 3.1

Suppose $\{f_{n}\}_{n \in \mathbb {N}}$ is a sequence of functions on [−π, π]. A function $\eta : \mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N}$ is a modulus of almost-everywhere convergence for $\{f_{n}\}_{n \in \mathbb {N}}$ if

$$\mu(\{t \in [-\pi, \pi]\ :\ \exists M,N \geq \eta(k,m)\ |f_{N}(t) - f_{M}(t)| \geq 2^{-k}\}) < 2^{-m} $$

for all k and m.

Thus, every sequence of functions on [−π, π] that converges almost everywhere has a modulus of almost-everywhere convergence. Our goal, as stated in the following lemma, is to show that the sequence of partial sums for the Fourier series of a computable vector in L^p[−π, π] has a computable modulus of almost-everywhere convergence.

Lemma 3.2

Supposep is a computable real so thatp > 1,and suppose f is a computable vector inL^p[−π, π].Then,$\{S_{N}(f)\}_{N \in \mathbb {N}}$hasa computable modulus of almost-everywhere convergence.

With this lemma in hand, Theorem 1.1 follows from the next lemma.

Lemma 3.3

Assume$\{f_{n}\}_{n \in \mathbb {N}}$isa uniformly computable sequence of functions on[−π, π] for which there is a computable modulusof almost-everywhere convergence. Then, thesequence$\{f_{n}\}_{n \in \mathbb {N}}$convergesat every Schnorr random real.

Generalizations of Lemma 3.3 can be found in Galatolo, Hoyrup, and Rojas [23, Thm. 1] and well as Rute [46, Lemma 3.19 on p. 41]. Our proof is new. Theorem 1.1 follows by applying Lemma 3.3 to the sequence of partial sums of f.

Proof 3 (Proof of Lemma 3.2)

We compute $\eta : \mathbb {N}^{2} \rightarrow \mathbb {N}$ as follows. Let $k,m \in \mathbb {N}$ be given as input. Compute a rational trigonometric polynomial τ_{k, m} so that ∥f − τ_{k, m}∥_p ≤ 2^{−(m + k+ 3)}C^− 1 where C is as in Fefferman’s inequality. Then define η (k, m) to be the degree of τ_{k, m}.

By definition, η is computable. We now show that it is a modulus of almost-everywhere convergence. We begin with some notation. Let g ∈ L^p[−π, π]. Set

$$E_{k, N_{0}}(g) = \{t \in [-\pi, \pi]\ :\ \exists M, N \geq N_{0}\ |S_{M}(g)(t) - S_{N}(g)(t)| \geq 2^{-k}\}. $$

Thus, we aim to show that μ (E_{k, η (k, m)}(f)) < 2^−m. For each $k \in \mathbb {N}$, let

$$\hat{E}_{k}(g) = \{t \in [-\pi, \pi]\ :\ \sup_{N} |S_{N}(g)(t)| > 2^{-k}\}. $$

It follows that $E_{k, N_{0}}(g) \subseteq \hat {E}_{k + 2}(g)$.

We claim that E_{k, η (k, m)}(f) ⊆ E_{k, η (k, m)}(f − τ_{k, m}). We see that if M, N ≥ η (k, m), then

$$\begin{array}{@{}rcl@{}} |S_{M}(f)(t) - S_{N}(f)(t)| & \leq & |S_{M}(f - \tau_{k,m})(t) - S_{N}(f - \tau_{k,m})(t)| + |S_{M}(\tau_{k,m})(t)\\ &&- S_{N}(\tau_{k,m})(t)|\\ & = & |S_{M}(f - \tau_{k,m})(t) - S_{N}(f - \tau_{k,m})(t)|. \end{array} $$

Thus, E_{k, η (k, m)}(f) ⊆ E_{k, η (k, m)}(f − τ_{k, m}).

It now follows that $E_{k, \eta (k,m)}(f) \subseteq \hat {E}_{k + 2}(f - \tau _{k,m})$. We complete the proof by showing that $\mu (\hat {E}_{k + 2}(f - \tau _{k,m})) < 2^{-m}$. By Fefferman’s Inequality and the definition of τ_{k, m},

$$\left\| \sup_{N}|S_{N}(f - \tau_{k,m})| \right\|_{1} \leq 2^{-(m + k + 3)}. $$

Thus, by Chebyshev’s Inequality,

$$\mu(\hat{E}_{k + 2}(f - \tau_{k,m})) \leq 2^{-(m + k + 3)}2^{k + 2} = 2^{-(m + 1)} < 2^{-m}. $$

Hence, $\mu (\hat {E}_{k + 2}(f - \tau _{k,m})) < 2^{-m}$. □

Proof 4 (Proof of Lemma 3.3)

We apply Miyabe’s characterization of Schnorr randomness. We begin by defining a Schnorr integral test as follows. Let η be a computable modulus of almost-everywhere convergence for $\{f_{n}\}_{n \in \mathbb {N}}$, and abbreviate η (k, k) by N_k. For each $k \in \mathbb {N}$ and each t ∈ [−π, π] define

$$g_{k}(t) = \min\left\{1,\ \ \max \{|f_{M}(t) - f_{N}(t))| : N_{k} < M,N \leq N_{k + 1}\}\right\}. $$

The sequence $\{g_{k}\}_{k \in \mathbb {N}}$ is computable. Set $T = {\sum }_{k = 0}^{\infty } g_{k}$.

We now show that T is a Schnorr integral test. By construction, T is lower semicomputable. Therefore, it suffices to show that ${\int }_{-\pi }^{\pi } T d\mu$ is a computable real. To this end, let $m \in \mathbb {N}$ be given. Since g_k is computable uniformly in k, it is possible to compute a rational number q so that $|{\sum }_{k = 0}^{m + 6} \int g_{k} d\mu - q| < 2^{-(m + 1)}$. We claim that $|{\int }_{-\pi }^{\pi } T d\mu - q| < 2^{-m}$. By the Monotone Convergence Theorem,

$${\int}_{-\pi}^{\pi} T\ d\mu = \sum\limits_{k = 0}^{\infty} {\int}_{-\pi}^{\pi} g_{k}\ d\mu. $$

Since g_k ≤ 1 and μ{t : g_k(t) ≥ 2^−k}≤ 2^−k, we have

$$\begin{array}{@{}rcl@{}} {\int}_{-\pi}^{\pi} g_{k}(t) dt &\leq& 2^{-k} \cdot \mu(\{t : g(t) < 2^{-k}\}) + 1 \cdot \mu(\{t : g(t) \geq 2^{-k}\}) \\ &\leq& 2^{-k}\cdot 2\pi + 1\cdot 2^{-k} \leq 2^{-k + 4}. \end{array} $$

Thus, ${\int }_{-\pi }^{\pi } T\ d\mu - {\sum }_{k = 0}^{m + 6} \int g_{k} d\mu < 2^{-(m + 1)}$, and we then have $|{\int }_{-\pi }^{\pi } T\ d\mu - q| < 2^{-m}$. Hence, ${\int }_{-\pi }^{\pi } T\ d\mu$ is a computable real.

Finally, we show that T (t₀) = ∞ whenever $\{f_{n}(t_{0})\}_{n \in \mathbb {N}}$ diverges. This will complete the proof of the lemma. Suppose $\{f_{n}(t_{0})\}_{n \in \mathbb {N}}$ diverges. Then there exists $k_{0} \in \mathbb {N}$ so that for every n, we can find M, N ≥ n such that $|f_{M}(t_{0}) - f_{N}(t_{0})| \geq 2^{-k_{0}}$. It thus suffices to show that ${\sum }_{k = k_{1}}^{\infty } g_{k}(t_{0}) \geq 2^{-k_{0}}$ for all $k_{1} \in \mathbb {N}$. So, let $k_{1} \in \mathbb {N}$. Without loss of generality, suppose g_k < 1 whenever k ≥ k₁. By the choice of k₀, there exist M and N so that $N_{k_{1}} < M < N$ and $|f_{M}(t_{0}) - f_{N}(t_{0})| \geq 2^{-k_{0}}$. By forming a telescoping sum and applying the triangle inequality we obtain

$$|f_{M}(t_{0}) - f_{N}(t_{0})| \leq \sum\limits_{k = k_{1}}^{\infty} g_{k}(t_{0}). $$

Thus T (t₀) = ∞, and the proof is complete. □

4 Proof of Theorem 1.2

Our proof of Theorem 1.2 is based on an idea for a construction which is sketched in [29]. Herein, we will use the material on harmonic functions discussed in Section 2 to carefully complete this sketch and provide an effective version of the construction. We divide our work into the following three lemmas.

Lemma 4.1

Suppose G is a computably compact subset of the unit circle so thatλ (G) is computable and smaller than 2π.Then there is a computable functionψfrom$\mathbb {D} \cup G$into the horizontal strip$\mathbb {R} \times (-\frac {\pi }{2}, \frac {\pi }{2})$thatis analytic on$\mathbb {D}$andhas the property that$\text {Re}(\psi (\zeta )) \geq -\frac {3}{4} \ln (\lambda (G)(2\pi )^{-1})$for allζ ∈ G.Furthermore, we may chooseψso thatψ(0) = 0.

Lemma 4.2

Suppose G is a computably compact subset of[−π, π] so thatλ (G) is computable and smaller than 2π.Then there is a computable and analytic trigonometric polynomial R sothat$\text {Re}(R(t)) \geq -\frac {1}{2} \ln (\lambda (G)/ (2\pi ))$forallt ∈ Gand so that |Im(R (t))| < πfor allt ∈ [−π, π].Furthermore, we may choose R so thatc₀(R) = 0.

Lemma 4.3

Suppose G is a computably compact subset of[−π, π] so thatλ (G) is computable andsmaller than 2π.Then there is a computable trigonometric polynomialp sothat

$$\sup_{N} |S_{N}(p)(t)| \geq -\frac{1}{4\pi} \ln\left( \frac{\lambda(G)}{2\pi}\right) $$

for all t ∈ G and so that ∥p∥_∞ < 1.

Proof 5 (Proof of Lemma 4.1)

By first applying a rotation if necessary, we can assume that − 1∉G. Set a = λ (G)/(2π). Since G is computably compact, we can compute pairwise disjoint open subarcs of the unit circle A₀,…, A_s so that $G \subseteq \bigcup _{j \leq s} A_{j}$ and so that

$$\frac{\lambda(\bigcup_{j} A_{j})}{2\pi} \leq a^{3/4}. $$

Set $F = \bigcup _{j \leq s} A_{j}$ and set a^′ = λ (F)/(2π). For each $z \in \mathbb {D} \cup G$, let $\phi (x) = \hat {\omega }(z, F, \mathbb {D})$. Thus, ϕ is computable and ϕ is analytic in $\mathbb {D}$. By (2.2), ϕ(0) = a^′. It also follows that Re(ϕ (z)) > 0 for all $z \in \mathbb {D} \cup G$. So, for all $z \in \mathbb {D} \cup G$, set ψ₁(z) = Log(ϕ (z)). Thus, ψ₁(0) = ln(a^′). Set ψ (z) = ψ₁(z) − ln(a^′) for all $z \in \mathbb {D} \cup G$. Hence, ψ₁ and ψ are computable.

Let ζ ∈ G. We claim that $\text {Re}(\psi (\zeta )) \geq -\frac {3}{4} \ln (a)$. We begin by noting that Re(ψ (ζ)) = Re(ψ₁(ζ)) − ln(a^′). By our choice of F, $\ln (a^{\prime }) - \frac {3}{4} \ln (a) \leq 0$. Thus, $\text {Re}(\psi (\zeta )) \geq -\frac {3}{4} \ln (a)$ for all ζ ∈ G.

Since Re(ϕ) > 0, it follows that $|\text {Im}(\psi _{1}(z))| < \frac {\pi }{2}$. However, Im(ψ) = Im(ψ₁) since ln(a^′) is real. □

We note that the proof of Lemma 4.1 is uniform.

Proof 6 (Proof of Lemma 4.2)

Let G^′ = {e^it : t ∈ G}. Thus, G^′ is a computably compact subset of the unit circle and λ (G^′) < 2π. Let ψ be as given by Lemma 4.1.

Let

$$G^{\prime\prime} = \{r \zeta\ :\ 0 \leq r \leq 1\ \wedge\ \zeta \in G^{\prime}\}. $$

It follows that G^″ is computably compact. One way to see this is to first note that by an effective Tychonoff Theorem [45], [0,1] × G^′ is a computably compact subset of $\mathbb {R}^{3}$. Let h (x₀, x₁, x₂) = x₀(x₁ + ix₂). Thus, h is a computable map from $\mathbb {R}^{3}$ into $\mathbb {R}$. Therefore, its image on [0,1] × G^′, which is just G^″, is computably compact.

Thus, ψ is uniformly continuous on G^″ and has a computable modulus of uniform continuity on G^″. This means that we can compute a rational number r₀ ∈ (0,1) so that

$$\text{Re}(\psi(r_{0} \zeta)) \geq -\frac{5}{8} \ln\left( \frac{\lambda(G^{\prime})}{2\pi}\right) $$

for all ζ ∈ G.

We now abbreviate a_n(ψ) by a_n. Let G⁽³⁾ = {r₀ζ : ζ ∈ G^′}. The series ${\sum }_{n = 0}^{\infty } a_{n} z^{n}$ converges uniformly on G⁽³⁾, and we can compute a modulus of uniform convergence for it on G⁽³⁾. It follows that we can compute N so that for all ζ ∈ G^′,

$$\begin{array}{@{}rcl@{}} \text{Re}\left( \sum\limits_{n = 0}^{N} a_{n} {r_{0}^{n}} \zeta^{n}\right) \geq -\frac{1}{2} \ln\left( \frac{\lambda(G^{\prime})}{2\pi}\right)\text{ and} \\ \left|\text{Im}\left( \sum\limits_{n = 0}^{N} a_{n} {r_{0}^{n}} \zeta^{n}\right)\right| < \pi. \end{array} $$

Set $R(t) = {\sum }_{n = 0}^{N} a_{n} {r_{0}^{n}} e^{i n t}$. Since ψ(0) = 0, a₀ = 0 and so c₀(R) = 0. □

We note that the proof of Lemma 4.2 is also uniform.

Proof 7 (Proof of Lemma 4.3)

Let R be as given in Lemma 4.2 and let N = deg(R). Set q = Im(R) and $p = \frac {1}{\pi } e_{-N} \cdot q$.

We claim that $|S_{N}(p)| = \frac {1}{2\pi } |R|$. For convenience, we abbreviate c_n(R) by c_n. Then c_m = 0 when m ≤ 0 and

$$\begin{array}{@{}rcl@{}} q(t) & = & \frac{1}{2i} \left[ \sum\limits_{n = 1}^{N} c_{n} e^{i n t} + \sum\limits_{n = 1}^{N} \overline{(-c_{n})} e^{-int} \right]\text{ and}\\ p(t) & = & \frac{1}{2\pi i} \left[ \sum\limits_{m = 1 - N}^{0} c_{m + N} e^{i nt} + \sum\limits_{m = 1 + N}^{2N} (\overline{-c_{m - N}}) e^{-int}\right]. \end{array} $$

Therefore,

$$S_{N}(p)(t) = e^{-iNt} \frac{1}{2\pi} S_{N}(R)(t). $$

Thus, $|S_{N}(p)| = \frac {1}{2\pi } |R|$.

Therefore,

$$\sup_{N}|S_{N}(p)(t)| \geq - \frac{1}{4\pi} \ln\left( \frac{\mu(G)}{2\pi}\right) $$

for all t ∈ G.

Since |Im(R)| < π, it follows that ∥p∥_∞ < 1. □

Note that the proof of Lemma 4.3 is uniform as well.

Now suppose t₀ is not Schnorr random. Then there is a Schnorr test $\{U_{n}\}_{n \in \mathbb {N}}$ so that $t_{0} \in \bigcap _{n} U_{n}$.

We construct an array of trigonometric polynomials $\{p_{n,k}\}_{n,k \in \mathbb {N}}$ as follows. Since $U_{2^{n}}$ is computably open uniformly in n, we can compute an array of closed rational intervals $\{I_{n,j}\}_{n,j \in \mathbb {N}}$ so that $U_{2^{n}} = \bigcup _{j} I_{n,j}$ and so that $\mu (I_{n,j} \cap I_{n,j^{\prime }}) = 0$ when j≠j^′. We then compute for each $n \in \mathbb {N}$ an increasing sequence m_n,0 < m_n,1 < … so that

$$\mu\left( U_{2^{n}} - \bigcup_{j \leq m_{n,k}} I_{n,j}\right) < 2^{-(2^{n + k + 1})} $$

for all n and k. We define the following sets:

$$\begin{array}{@{}rcl@{}} G_{n,0} & = & \bigcup_{j \leq m_{n,0}} I_{n,j} \cap [-\pi, \pi]\text{ and}\\ G_{n,k} & = & \bigcup_{m_{n,k} < j \leq m_{n,k + 1}} I_{n,j} \cap [-\pi,\pi]. \end{array} $$

It follows that

$$\mu(G_{n,k}) < 2^{-(2^{n+k})} $$

for all n and k.

Now fix n and k. By Lemma 4.3, we can compute a trigonometric polynomial p so that ∥p∥_∞ < 1 and

$$\sup_{N} |S_{N}(p)(t)| > -\frac{1}{4\pi} \ln\left( \frac{\mu(G_{n,k})}{2\pi}\right) $$

for all t ∈ G_{n, k}. Set p_{n, k} = 2^{−(n + k+ 1)}p. It follows that supN|S_N(p_{n, k})(t)| > (8π)^− 1 for all t ∈ G_{n, k}.

We can now compute an array of nonnegative integers $\{r_{n,k}\}_{n,k \in \mathbb {N}}$ so that for each $m \in \mathbb {Z}$, either $c_{m}(e_{r_{n,k}}\cdot p_{n,k})= 0$ or $c_{m}(e_{r_{n^{\prime },k^{\prime }}}\cdot p_{n^{\prime },k^{\prime }})= 0$ whenever (n, k)≠(n^′, k^′) and so that $c_{m}(e_{r_{n,k}}\cdot p_{n,k}) = 0$ whenever m < 〈n, k〉 (where 〈,〉 is the Cantor coding of $\mathbb {N} \times \mathbb {N}$). We set

$$\begin{array}{@{}rcl@{}} f_{n,k} & = & e_{r_{n,k}} \cdot p_{n,k}\text{ and}\\ f & = & \sum\limits_{n,k} f_{n,k}. \end{array} $$

Since ∥p_{n, k}∥_∞ < 2^{−(n + k+ 1)}, it follows that f is computable.

We now show that the Fourier series of f diverges at t₀. It suffices to show that

$$\sup_{M,N} |S_{M}(f)(t_{0}) - S_{N}(f)(t_{0})| > \frac{1}{8 \pi}. $$

Let $N_{0} \in \mathbb {N}$ and choose n so that 〈n,0〉≥ N₀ and k so that t₀ ∈ G_{n, k}. By the construction of $\{r_{n,k}\}_{n,k \in \mathbb {N}}$ there exist M, N^′ so that $f_{n,k} = S_{N^{\prime }}(f) - S_{M}(f)$ and M ≥〈n, k〉≥〈n,0〉. By the construction of p_{n, k}, there exists N so that M ≤ N ≤ N^′ and |S_N(f)(t₀) − S_M(f)(t₀)| > (8π)^− 1.

Thus, the Fourier series for f diverges at t₀.

We note that this construction makes use of all of the conditions of Schnorr randomness. In particular, the construction of m_{n, k} utilizes the computability of μ (U_n) from n.

5 A Strengthening of Theorem 1.1; Convergence to f (t ₀)

Throughout this subsection, p denotes a computable real such that p ≥ 1.

In Theorem 1.1 we showed that S_N(f)(t₀) converges for Schnorr randoms t₀ and computable vectors f ∈ L^p[−π, π]. However, one would like to also say that $\{S_{N}(f)(t_{0})\}_{N \in \mathbb {N}}$ converges to f (t₀). The problem is that f is merely a vector in L^p[−π, π], and so f (t₀) is not well defined. Recall that a vector in L^p[−π, π] is actually an equivalence class of functions under the “equal almost everywhere” relation, and so every complex number is a candidate for the value of f (t₀). Thus, the limit of $\{S_{N}(f)(t_{0})\}_{N \in \mathbb {N}}$ may not be f (t₀) even if t₀ is Schnorr random.¹ However, this problem has a solution via Cauchy names, a standard device in computable analysis.

Definition 5.1

A sequence of rational trigonometric polynomials $\{\tau _{n}\}_{n \in \mathbb {N}}$ is a Cauchy name of a vector f ∈ L^p[−π, π] if $\lim _{n \rightarrow \infty } \| \tau _{n} - f \|_{p} = 0$ and if ∥τ_n − τ_n+ 1∥_p < 2^−(n+ 1) for all $n \in \mathbb {N}$.

Thus, a Cauchy name of a vector in L^p[−π, π] is a name of exactly one such vector (up to almost everywhere equality).

A Cauchy name $\{\tau _{n}\}_{n \in \mathbb {N}}$ of a vector is computable if $\{\tau _{n}\}_{n \in \mathbb {N}}$ is a uniformly computable sequence of rational trigonometric polynomials in the sense that the degree and coefficients of τ_n can be computed from n. It follows that a vector in L^p[−π, π] is computable if and only if it has a computable Cauchy name.

We will show that there is a natural way to use a computable Cauchy name of f ∈ L^p[−π, π] to assign a canonical value to f (t₀) when t₀ is Schnorr random. We will then show that if f is a computable vector in L^p[−π, π], then $\lim _{N \rightarrow \infty } S_{N}(f)(t_{0})$is the canonical value of f (t₀) whenever t₀ is Schnorr random. Our approach is based on the following theorem which effectivizes a well-known result in measure theory; namely, that a convergent sequence in L^p[−π, π] has a subsequence that converges almost everywhere.

Theorem 5.2

Supposef_n ∈ L^p[−π, π] for all$n \in \mathbb {N}$andsuppose g is a computable modulus of convergencefor$\{f_{n}\}_{n \in \mathbb {N}}$.Then,$\eta (k,m) = \lceil \frac {1}{2}(\frac {m + 1}{p} + k + 1)\rceil$definesa modulus of almost-everywhere convergencefor$\{f_{g(2n)}\}_{n \in \mathbb {N}}$.

Proof 8

Set

$$E_{n,r} = \{t \in [-\pi, \pi]\ :\ |f_{g(2n + 1)}(t) - f_{g(2n)}(t)| \geq 2^{-r}\}. $$

Since g is a modulus of convergence for $\{f_{n}\}_{n \in \mathbb {N}}$, $\| f_{g(2n + 1)} - f_{g(2n)} \|_{p}^{p} < 2^{-2np}$. Thus, by Chebychev’s Inequality, μ (E_{n, r}) ≤ 2^{p (r− 2n)}.

Set N₀ = η (k, m). Suppose M, N ≥ N₀ and |f_g(2M)(t) − f_g(2N)(t)|≥ 2^−k. Then

$$2^{-k} \leq \sum\limits_{n = N_{0}}^{\infty} |f_{g(2n + 2)}(t) - f_{g(2n)}(t)|. $$

It follows that $t \in \bigcup _{c = 0}^{\infty } E_{N_{0} + c, k + 1+c}$. But, by the definition of η,

$$\sum\limits_{c = 0}^{\infty} 2^{p(k + 1 + c - 2(N_{0} + c))}\\ < \sum\limits_{c = m + 1}^{\infty} 2^{-c} = 2^{-m}. $$

Thus, $\mu (\bigcup _{c = 0}^{\infty } E_{N_{0} + c, k + 1+c}) < 2^{-m}$. It follows that η is a modulus of almost-everywhere convergence for $\{f_{g(2n)}\}_{n \in \mathbb {N}}$. □

We can now present the following corollary to Lemma 3.3.

Corollary 5.3

If$\{\tau _{n}\}_{n \in \mathbb {N}}$isa computable Cauchy name for a vector inL^p[−π, π] and ift₀ ∈ [−π, π] is Schnorr random, then$\{\tau _{2n}(t_{0})\}_{n \in \mathbb {N}}$converges.

Corollary 5.3 leads to the idea that a Cauchy name for f assigns a value to f (t) for Schnorr random t.

Definition 5.4

If $\{\tau _{n}\}_{n \in \mathbb {N}}$ is a computable Cauchy name for a vector f ∈ L^p[−π, π], and if $\{\tau _{2n}(t)\}_{n \in \mathbb {N}}$ converges to $\alpha \in \mathbb {C}$, then we say $\{\tau _{n}\}_{n \in \mathbb {N}}$assignsthe valueαtof (t).

Thus, if f is a computable vector in L^p[−π, π] and if t₀ is Schnorr random, then a value is assigned to f (t₀) by each computable Cauchy name of f. We now show that the same value is assigned by all computable Cauchy names via the following proposition.

Proposition 5.5

Suppose$\{f_{n}\}_{n \in \mathbb {N}}$and$\{g_{n}\}_{n \in \mathbb {N}}$arecomputable sequence of functions on [−π, π] and that each has a computable modulusof almost-everywhere convergence. Suppose alsothat$\lim _{n \rightarrow \infty } f_{n}(t) - g_{n}(t) = 0$foralmost everyt ∈ [−π, π].Then,$\lim _{n \rightarrow \infty } f_{n}(t_{0}) = \lim _{n \rightarrow \infty } g_{n}(t_{0})$whenevert₀ ∈ [−π, π] is Schnorr random.

Proof 9

Let η₀ be a computable modulus of almost-everywhere convergence for $\{f_{n}\}_{n \in \mathbb {N}}$, and let η₁ be a computable modulus of almost-everywhere convergence for $\{g_{n}\}_{n \in \mathbb {N}}$. Let h_2n = f_n, and let h_2n+ 1 = g_n. Set η (k, m) = η₀(k + 1, m + 2) + η₁(k + 1, m + 2). It follows that η is a computable modulus of almost-everywhere convergence for $\{h_{n}\}_{n \in \mathbb {N}}$. So, if t₀ is Schnorr random, then $\{h_{n}(t_{0})\}_{n \in \mathbb {N}}$ converges, and so $\{f_{n}(t_{0})\}_{n \in \mathbb {N}}$ and $\{g_{n}(t_{0})\}_{n \in \mathbb {N}}$ converge to the same value. □

Definition 5.6

Suppose f is a computable vector in L^p[−π, π]. When t₀ is Schnorr random, the canonical value of f (t₀) is the value assigned to f (t₀) by a computable Cauchy name of f .

By Proposition 5.5, the choice of computable Cauchy name does not matter. Note that if f is continuous, then the canonical value of f (t₀) is in fact f (t₀).

Proposition 5.5 yields an extension of Theorem 1.1.

Corollary 5.7

Supposep > 1 and suppose f is a computable vector inL^p[−π, π].Then,$\{S_{N}(f)(t_{0})\}_{N \in \mathbb {N}}$convergesto the canonical value off (t₀) whenevert₀is Schnorr random.

It should also be remarked that these canonical values are similar to Miyabe’s Schnorr layerwise computable functions from [35].

6 The p = 1 Case; Characterizing Schnorr Randomness via the Fejér-Lebesgue Theorem

Carleson’s Theorem does not hold for vectors in L¹[π, π]. Indeed, Kolmogorov [31] constructed a complex-valued function f in L¹[π, π] for which $\{S_{N}(f)(t)\}_{N \in \mathbb {N}}$ diverges almost everywhere (later improved to “diverges everywhere”). Moser [37] further constructed a computable such f. Nonetheless, Fejér and Lebesgue proved that the Cesáro means of $\{S_{N}(f)\}_{N \in \mathbb {N}}$ converge to f almost everywhere. In this section, we will show that the exceptional set of this theorem also characterizes Schnorr randomness. We begin by reviewing the relevant components of the classical theory. We will then discuss their effective renditions.

Recall that the (N + 1)^st Cesáro mean of a sequence $\{a_{n}\}_{n \in \mathbb {N}}$ is

$$\frac{1}{N + 1} \sum\limits_{n = 0}^{N} a_{n}. $$

If $\{a_{n}\}_{n \in \mathbb {N}}$ converges, then so does the sequence of its Cesáro means and to the same limit. Cesáro means provide a widely-used method for “evaluating divergent series;” e.g., the Cesáro means of the partial sums of ${\sum }_{n = 0}^{\infty } (-1)^{n}$ converge to $\frac {1}{2}$.

Now fix a vector f ∈ L¹[−π, π]. Let σ_N(f) denote the (N + 1)^st Cesáro mean of $\{S_{N}(f)\}_{N \in \mathbb {N}}$. That is,

$$\sigma_{N}(f) = \frac{1}{N + 1} \sum\limits_{M = 0}^{N} S_{M}(f). $$

One can also express σ_N(f) via the convolution

$$ \sigma_{N}(f)(t) = \frac{1}{2\pi}{\int}_{-\pi}^{\pi}f(t-x)F_{N}(x) dx $$

(6.1)

where F_N is the Fejér kernel

$$F_{N}(x)= \frac{1}{N} \frac{\sin^{2}(Nx/2)}{\sin^{2}(x/2)}. $$

Recall that t₀ ∈ [−π, π] is a Lebesgue point of f if

$$\lim_{\epsilon \rightarrow 0^{+}} \frac{1}{2\epsilon} {\int}_{t_{0} - \epsilon}^{t_{0} + \epsilon} |f(t)-f(t_{0})|\ dt = 0. $$

One of Lebesgue’s differentiation theorems states that almost every point in [−π, π] is a Lebesgue point of f. Building on Fejér’s work on Cesáro means of Fourier series, Lebesgue then showed that $\{\sigma _{N}(f)(t_{0})\}_{N \in \mathbb {N}}$ converges to f (t₀) whenever t₀ is a Lebesgue point of f [34]. Fejér also showed that $\{\sigma _{N}(f)\}_{N \in \mathbb {N}}$ converges uniformly if f is continuous and periodic (in the sense that f (π) = f(−π)).

The result of this section can now be stated as follows.

Theorem 6.1

Supposet₀ ∈ [−π, π].Then,t₀is Schnorr random if and only if$\{\sigma _{N}(f)(t_{0})\}_{N \in \mathbb {N}}$convergesto the canonical value off (t₀) whenever f is a computable vector inL¹[−π, π].

Proof 10

Suppose t₀ is Schnorr random, and let f be a computable vector in L¹[−π, π]. Let $\widetilde {f}$ denote the function so that $\widetilde {f}(t)$ equals the canonical value of f (t) when t is Schnorr random and is 0 otherwise. Call $\widetilde {f}$ the canonical version of f . Independently, Pathak, Rojas, and Simpson [43] and Rute [46] showed that every Schnorr random t₀ is a Lebesgue point of $\widetilde {f}$. Since $\widetilde {f}(t) = f(t)$ almost everywhere, $\sigma _{N}(\widetilde {f}) = \sigma _{N}(f)$. Thus, by the Fejér-Lebesgue Theorem, $\{\sigma _{N}(f)(t_{0})\}_{N \in \mathbb {N}}$ converges to the canonical value of f (t₀).

Now, suppose t₀ is not Schnorr random. Then there is a Schnorr integral test T so that T (t₀) = ∞. We claim that T is a computable vector in L¹[−π, π]. Suppose $T = {\sum }_{n = 0}^{\infty } g_{n}$ where $\{g_{n}\}_{n \in \mathbb {N}}$ is a computable sequence of nonnegative functions. By the Monotone Convergence Theorem, $\| T \|_{1} = {\sum }_{n = 0}^{\infty } \| g_{n} \|_{1}$. Let $k \in \mathbb {N}$ be given. Since ∥T∥₁ is computable, from k we can compute a nonnegative integer m so that $\| {\sum }_{n = m + 1}^{\infty } g_{n} \|_{1} < 2^{-(k + 1)}$. Since g_n is computable uniformly in n, we can then compute a trigonometric polynomial τ so that $\| \tau - {\sum }_{n = 0}^{m} g_{n} \|_{1} < 2^{-(k + 1)}$. It follows that ∥T − τ∥₁ < 2^−k.

We now show that $\lim _{N} \sigma _{N}(T)(t_{0}) = \infty$. Set $h_{k} = {\sum }_{n = 0}^{k} g_{k}$. Fix $k \in \mathbb {N}$. Since F_N ≥ 0, it follows from (6.1) that σ_N(T)(t₀) ≥ σ_N(h_k)(t₀). Since h_k is continuous at t₀, t₀ is a Lebesgue point for h_k and so $\lim _{N \rightarrow \infty } \sigma _{N}(h_{k})(t_{0}) = h_{k}(t_{0})$. Thus, $\lim _{N} \sigma _{N}(T)(t_{0}) \geq h_{k}(t_{0})$. It follows that $\lim _{N \rightarrow \infty } \sigma _{N}(f)(t_{0}) = \infty$. □

The forward direction of Theorem 6.1 first appeared in Rute’s dissertation [46, Cor. 4.22 on p. 49]. Note that if $f : [-\pi , \pi ] \rightarrow \mathbb {C}$ is continuous, then every number in [−π, π] is a Lebesgue point of f. Thus, the converse of Theorem 6.1 cannot be made as strong as Theorem 1.2.

The proof of the converse of Theorem 6.1 can easily be adapted to the case where f ∈ L^p[−π, π] and p ≥ 1. In addition, the proof of this direction shows that if T ≥ 0 is a lower semicontinuous and integrable function (possibly with infinite values) and if p ≥ 1, then there is a vector f ∈ L^p[−π, π] so that $\{\sigma _{N}(f)(t)\}_{N \in \mathbb {N}}$ diverges whenever T (t) = ∞. If E is a measure zero subset of [−π, π], then there is a lower semicontinuous and non-negative function T so that ∥T∥₁ < ∞ and so that T (t) = ∞ whenever t ∈ E. We thus obtain the following extension of a result of Katznelson by a simpler proof [30].

Theorem 6.2

Supposep ≥ 1,and suppose E is a measure 0 subset of[−π, π].Then there existsf ∈ L^p[−π, π] so that$\{\sigma _{N}(f)(t)\}_{N \in \mathbb {N}}$divergeswhenevert ∈ E.

7 Conclusion

We have used algorithmic randomness to study an almost-everywhere convergence theorem in analysis. Many of these theorems have already been investigated, including the ergodic theorem [20, 22, 27, 51], the martingale convergence theorem [46], the Lebesgue Differentiation Theorem [43, 46], Rademacher’s Theorem [21], and Lebesgue’s theorem concerning the differentiability of bounded variation functions [7]. This list is not exhaustive and more work needs to be done. In some cases, the resulting randomness notion is Schnorr randomness. In others, it is Martin-Löf randomness or computable randomness.

In this conclusion, we would like to share some intuition about why Carleson’s Theorem characterizes Schnorr randomness and what clues one might look for when investigating similar theorems. Namely, we are interested in almost-everywhere convergence theorems stating that for a family $\mathcal {F}$ of sequences of functions, every sequence $\{f_{n}\}_{n \in \mathbb {N}}$ in the family converges almost everywhere. In Carleson’s Theorem, $\mathcal {F}$ is the family of sequences $\{S_{N}(f)\}_{N \in \mathbb {N}}$ for f ∈ L^p.

The main clue that $\{S_{N}(f)\}_{N \in \mathbb {N}}$ converges on Schnorr randoms is that the pointwise limit of this sequence is computable from the parameter f (indeed the limit is f ). In such cases where the limit is computable, one can usually (at least from our experience) find a computable modulus of almost-everywhere convergence. This allows one to apply Lemma 3.3 or one of its generalizations to show that the sequence $\{f_{n}\}_{n \in \mathbb {N}}$ converges for Schnorr randoms (e.g., Theorem 1.1). In some cases, this rate of convergence follows from well-known quantitative estimates—Fefferman’s Inequality in our case. Moreover, in convergence theorems where the limit is computable, these theorems are usually constructively provable. We conjecture that Carleson’s Theorem is provable in the logical frameworks of Bishop style constructivism and RCA₀.

On the other hand, if we are working with a theorem, such as the ergodic theorem, where the limit of the theorem is not always computable, then it is unlikely that the sequence $\{f_{n}\}_{n \in \mathbb {N}}$ converges for all Schnorr randoms. Instead, one should look into weaker randomness notions, such as Martin-Löf and computable randomness. Nonetheless, convergence on Schnorr randoms can often be recovered by restricting the theorem. For example, with the ergodic theorem, convergence happens on Schnorr randoms if the system is ergodic (or in any case where the limit is computable).

Lastly, “reversals” similar to Theorem 1.2 are usually effective proofs of a stronger result. For example, Miyabe’s characterization of the Schnorr randoms yields proof of the following principle: If E ⊆ [−π, π] is a null set, then there is a lower semicontinuous and integrable function T : [−π, π] → [0, ∞] so that T (t₀) = ∞ whenever t₀ ∈ E. If we relativize Theorem 1.2, then we get Kahane and Katznelson’s result [29] that for every null set E, there is a continuous function f such that $\{S_{N}(f)\}_{N \in \mathbb {N}}$ diverges on E. However, the relativizations of the lemmas in Section 4 strengthen the intermediate results in [29], and we have endeavored to carefully justify many important details. Similarly, if an almost-everywhere convergence theorem characterizes a standard randomness notion, then it usually satisfies the following property: For every null set E there is a sequence $\{f_{n}\}_{n \in \mathbb {N}}$ for which the theorem says $\{f_{n}\}_{n \in \mathbb {N}}$ converges almost everywhere, but $\{f_{n}\}_{n \in \mathbb {N}}$ diverges on E. Not all almost-everywhere theorems satisfy this property. Nonetheless, this property does seem to be satisfied by theorems where the parameters of the theorem are functions in L^p, such as Carleson’s Theorem and the Lebesgue differentiation theorem.