SCHNORR RANDOMNESS AND THE LEBESGUE DIFFERENTIATION THEOREM

NOOPUR PATHAK, CRISTÓBAL ROJAS, AND STEPHEN G. SIMPSON

Abstract. We exhibit a close correspondence between L_{1}-computable functions and Schnorr tests. Using this correspondence, we prove that a point x ∈ [0, 1]^{d} is Schnorr random if and only if the Lebesgue Differentiation Theorem holds at x for all L_{1}-computable functions f ∈ L_{1}([0, 1]^{d}).

1. Introduction

Throughout mathematics there are many measure-theoretic theorems of the form “property P holds for almost all x.” An important component of the theory of algorithmic randomness has been to prove that random points satisfy such theorems.

Recently, there has been interest in the converse problem, namely, to characterize notions of randomness in terms of classical theorems which hold almost everywhere. An example of such a classical theorem is the Birkhoff Ergodic Theorem.

Theorem 1.1 (Birkhoff’s Ergodic Theorem). Given a probability space (X, μ), an ergodic^{1} transformation T : X → X, and a function f ∈ L_{1}(X, μ), we have

(1)  lim_{n→∞} \frac{1}{n} ∑_{i<n} f(T^{i}(x)) = ∫ f dμ

for almost all x ∈ X.

A connection between Birkhoff’s theorem and algorithmic randomness appeared in [16], where it was shown (see also [9]) that (1) holds for every L_{1}-computable function f and every Martin-Löf random point x.

In ergodic theory, a point x is called typical^{2} for a given transformation T if (1) holds for every bounded continuous function f. In [7], a characterization of Schnorr randomness in terms of dynamical typicalness was given. Here we state a slightly improved version, obtained using a result from [1] (see also [8]) which concerns the computability of the rate of convergence of ergodic averages.

Date: First draft: July 22, 2008. This draft: May 21, 2014.

2010 Mathematics Subject Classification. 03D32,26A24.

The research of Pathak, Rojas and Simpson was partially supported by NSF grant DMS-0652637 as part of a U.S. National Science Foundation Focused Research Group project on algorithmic randomness. In addition, the authors thank John Clemens for detailed comments on a draft of this paper.

1A transformation T : X → X is said to be ergodic (with respect to a probability measure μ on X) if for every measurable set A satisfying T^{−1}(A) = A either μ(A) = 1 or μ(A) = 0.

2The set of typical points has full measure. We remark that, if in the definition of typical point we relax the functions f to be integrable only (or even characteristic functions of measurable sets), then the resulting set of typical points would be empty.

Theorem 1.2. ([1], [8]) Let X be a computable probability space. A point x ∈ X is Schnorr random if and only if x is typical for every computable ergodic transformation T : X → X.

The question of whether a similar characterization would hold for Martin-Löf randomness was raised. A positive answer to this question was given independently by Franklin, Greenberg, Miller, and Ng [6] and Bienvenu, Day, Hoyrup, Mezhirov and Shen [2], who proved the following.

Theorem 1.3 ([6], [2]). Let X be a computable probability space, and let T : X → X be a computable ergodic transformation. Then, a point x ∈ X is Martin-Löf random if and only if

lim_{n→∞} \frac{1}{n} ∑_{i<n} χ_{A}(T^{i}(x)) = μ(A).

for all effectively closed sets A.

Similarly but in a somewhat different direction, Brattka, Miller and Nies [3] have obtained some interesting equivalences between randomness and differentiability.

Theorem 1.4 ([3]). For x ∈ [0, 1] we have

(1) x is computably random if and only if every nondecreasing computable function f : [0, 1] → ℝ is differentiable at x.

(2) x is Martin-Löf random if and only if every computable function f : [0, 1] → ℝ of bounded variation is differentiable at x.

(3) x is weakly 2-random if and only if every almost everywhere differentiable computable function f : [0, 1] → ℝ is differentiable at x.

We now turn to the subject of the present paper, an analysis of the Lebesgue Differentiation Theorem. The classical theorem reads as follows.

Theorem 1.5 (Lebesgue Differentiation Theorem). For each f ∈ L_{1}([0, 1]^{d}) we have

(2)  f(x) = lim_{Q→x} \frac{∫_{Q} fdμ}{μ(Q)}

for almost all x ∈ [0, 1]^{d}. The limit is taken over all cubes Q containing x as the diameter of Q tends to 0.

In [14] it was shown that, for each f ∈ L_{1}([0, 1]^{d}) which is L_{1}-computable in the sense of Definition 2.6 below, the equation (2) holds for all x ∈ [0, 1]^{d} which are random in the sense of Martin-Löf. At the end of [14], the question of the converse was posed. The purpose of the present paper is to answer this question by sharpening the results of [14]. Roughly speaking, our main result is as follows:

Theorem 1.6. A point x ∈ [0, 1]^{d} is Schnorr random if and only if (2) holds for all L_{1}-computable functions f ∈ L_{1}([0, 1]^{d}).

In other words, the Lebesgue Differentiation Theorem characterizes Schnorr randomness. Moreover, our proof of Theorem 1.6 establishes certain relationships between Schnorr tests and L_{1}-computable functions. In Lemma 3.15 below we associate to each L_{1}-computable function f ∈ L_{1}([0, 1]^{d}) a Schnorr test such that (2) holds for all x ∈ [0, 1]^{d} which pass the test. Consequently, by Theorem 3.16 below, (2) holds for all Schnorr random x. In Lemma 3.14 we obtain a computationally motivated estimate of the rate of convergence in (2). In Theorem 4.7 below, we associate to each Schnorr test an L_{1}-computable f ∈ L_{1}([0, 1]^{d}) such that for all x ∈ [0, 1]^{d} which fail the test, the limit in (2) does not exist. Combining these results, we have a close correspondence between L_{1}-computable functions and Schnorr tests.

Methodologically, our proofs are perhaps somewhat novel. In verifying our Schnorr tests, we use Tarski’s quantifier elimination theorem for the real number system (see Lemma 3.3 below) as well as some ideas from computable measure theory [12, 15] (see Lemmas 2.12 and 3.5 below). So far as we know, this is the first time that quantifier elimination has been applied in randomness theory.

2. Preliminary definitions and notation

Notation 2.1. Fix a positive integer d, the dimension. We consider real-valued, Lebesgue measurable functions f and Lebesgue measure μ on the unit cube [0, 1]^{d} in d-dimensional Euclidean space. The L_{1}-norm is defined by

∥f∥_{1} = ∫_{[0,1]^{d}} |f| = ∫_{x∈[0,1]^{d}} |f(x)| dμ(x) .

Recall that L_{1}([0, 1]^{d}) is the space of all f such that ∥f∥_{1} is finite. Moreover, for all f, g ∈ L_{1}([0, 1]^{d}) we have ∥f − g∥_{1} = 0 if and only if μ({x | f(x) ≠ g(x)}) = 0.

Notation 2.2. We use Q as a variable ranging over cubes in [0, 1]^{d}. Thus Q denotes a set of the form

(3)  Q = {⟨x_{1}, …, x_{d}⟩ | |x_{i} − a_{i}| ≤ r for all i = 1, …, d}

where a_{1}, …, a_{d}, r are real numbers with 0 ≤ a_{i} − r < a_{i} + r ≤ 1. If a_{1}, …, a_{d}, r are rational, we say that Q is a rational cube. Throughout this paper, letters such as i, j, k, l, m, n, … range over the natural numbers.

Remark 2.3. The classical Lebesgue Differentiation Theorem (see for instance [17]) reads as follows. Given f ∈ L_{1}([0, 1]^{d}) we can find a set S depending on f such that μ(S) = 0 and

f(x) = lim_{Q→x} \frac{∫_{Q} fdμ}{μ(Q)}

for all x ∉ S. The limit is taken over all cubes Q containing x as the diameter of Q tends to 0.

Definition 2.4. A finite step function is a function of the form

f(x) = ∑_{i=1}^{k} c_{i}χ_{Q_{i}}(x)

where χ_{Q_{i}} is the characteristic function of a cube Q_{i} in [0, 1]^{d}. If c_{1}, …, c_{k} and Q_{1}, …, Q_{k} are rational we say that f is a finite rational step function.

Remark 2.5. It is well known that, given f ∈ L_{1}([0, 1]^{d}) and ϵ > 0, we can find a polynomial f_{ϵ} with rational coefficients such that ∥f − f_{ϵ}∥_{1} < ϵ. Such polynomials are describable by finite strings of symbols which are amenable to computation. In the following definition and throughout this paper, we view such polynomials as computable approximations of f. Moreover, instead of rational polynomials, we could equally well use finite rational step functions.

Definition 2.6. A function f ∈ L_{1}([0, 1]^{d}) is said to be L_{1}-computable if there exists a computable sequence of polynomials with rational coefficients, denoted f_{n}, such that

(4)  ∥f − f_{n}∥_{1} ≤ \frac{1}{2^{n}}

for all n. Equivalently, f ∈ L_{1}([0, 1]^{d}) is L_{1}-computable if and only if there exists a computable sequence of finite rational step functions f_{n} such that (4) holds.

Remark 2.7. The idea behind Definition 2.6 is that we are endowing L_{1}([0, 1]^{d}) with the structure of a computable metric space. The L_{1}-computable functions are then the computable points of that space. For more on the theory of computable metric spaces, see [12, §2.4].

Definition 2.8.

(1) An open ball in [0, 1]^{d} is a set of the form

B(a, r) = {x ∈ [0, 1]^{d} | |x − a| < r}

where a = ⟨a_{1}, …, a_{d}⟩ ∈ [0, 1]^{d} and |x − a| denotes Euclidean distance. If a_{1}, …, a_{d}, r are rational, we say that B(a, r) is a rational open ball or a basic open set. Note that rational open balls, like polynomials with rational coefficients amd finite rational step functions, are amenable to computation.

(2) A set U ⊆ [0, 1]^{d} is said to be Σ_{1}^{0} if

U = ⋃_{i=0}^{∞} B(a_{i}, r_{i})

where B(a_{i}, r_{i}), i = 0, 1, … is a computable sequence of rational balls. A Σ_{1}^{0} set is also known as an effectively open set, because it is the union of a computable sequence of basic open sets.

(3) A sequence of sets U_{n} ⊆ [0, 1]^{d}, n = 0, 1, 2, … is uniformly Σ_{1}^{0} if

U_{n} = ⋃_{i=0}^{∞} B(a_{n,i}, r_{n,i})

for all n, where B(a_{n,i}, r_{n,i}), n = 0, 1, 2, …, i = 0, 1, 2, … is a computable double sequence of rational balls.

(4) A set P ⊆ [0, 1]^{d} is effectively closed or Π_{1}^{0} if its complement is effectively open.

The next two definitions can be found in [13, §3.1]. See also [5].

Definition 2.9. A Martin-Löf test is a uniformly Σ_{1}^{0} sequence of sets U_{n} ⊆ [0, 1]^{d}, n = 0, 1, 2, … such that μ(U_{n}) ≤ 1/2^{n} for all n. A point x ∈ [0, 1]^{d} is said to pass the test if x ∉ ⋂_{n=0}^{∞} U_{n}. We say that x is Martin-Löf random if it passes every Martin-Löf test.

Definition 2.10. A Schnorr test is a Martin-Löf test U_{n}, n = 0, 1, 2, … such that μ(U_{n}) is uniformly computable for all n. We say that x is Schnorr random if it passes every Schnorr test.

Remark 2.11. In [14] it was shown that if x is Martin-Löf random, the Lebesgue Differentiation Theorem holds at x for all L_{1}-computable functions. We now prove, in Section 3 below, that the same result holds if x is Schnorr random. The converse is proved in Section 4.

In order to construct Schnorr tests, we shall use the following lemma.

Lemma 2.12. Let U, V ⊆ [0, 1]^{d} be Σ_{1}^{0} sets. Then U ∩V and U ∪V are Σ_{1}^{0} sets. If in addition μ(U) and μ(V) are computable real numbers, then μ(U ∩V) and μ(U ∪V) are computable real numbers. Moreover, these statements hold uniformly.

Proof. A proof can be found in [15, Lemma 2.3.1.2]. See also [12]. □

Remark 2.13. Given a Martin-Löf test or a Schnorr test U_{n}, n = 0, 1, 2, …, we may safely assume (by taking intersections and applying Lemma 2.12) that U_{n+1} ⊆ U_{n} holds for all n.

3. Schnorr points are Lebesgue for L_{1}-computable functions

Thr purpose of this section is to prove Theorem 3.16. Essentially, Theorem 3.16 says that the Lebesgue Differentiation Theorem 1.5 holds for all Schnorr random points x ∈ [0, 1]^{d} and all L_{1}-computable functions f ∈ L_{1}([0, 1]^{d}).

Remark 3.1. The key lemmas in this section are Lemmas 3.6 and 3.13. The idea of these lemmas is to associate Schnorr tests V_{k} and V_{k}^{∗} to each L_{1}-computable function f. The V_{k}’s insure the existence of the limit f̂(x) = lim_{n→∞} f_{n}(x), and the V_{k}^{∗}’s insure that x is a Lebesgue point for f. In order to construct the V_{k}’s and the V_{k}^{∗}’s, we employ the method of effective quantifier elimination as embodied in the following well known theorem, due originally to Tarski.

Theorem 3.2. The theory of real closed ordered fields is complete, decidable, and admits elimination of quantifiers.

Proof. See for instance [10, Theorem 8.4.4, page 385]. □

Lemma 3.3. Let S be a set in the d-dimensional unit cube [0, 1]^{d} such that S is first-order definable over the real number system. Then, the d-dimensional Lebesgue measure of S is a computable real number. Moreover, this holds uniformly in the given first-order definition of S.

Proof. We use the following well known fact: given a non-zero polynomial f ∈ ℤ[x_{1}, …, x_{d}], the set {x ∈ [0, 1]^{d} | f(x) = 0} is of measure 0. Now, given a firstorder definition of a set S in [0, 1]^{d} as above, apply effective quantifier elimination to obtain a quantifier-free definition of S. Let f_{1}, ..., f_{n} ∈ ℤ[x_{1}, …, x_{d}] be a list of the nonzero polynomials which occur in the quantifier-free definition of S. For each i = 1, ..., n let

\begin{aligned}U_{i} & = & \{x ∈ [0, 1]^{d} | f_{i}(x) > 0\}, \\ V_{i} & = & \{x ∈ [0, 1]^{d} | f_{i}(x) < 0\}, \\ C_{i} & = & \{x ∈ [0, 1]^{d} | f_{i}(x) = 0\}. \end{aligned}

Then each C_{i} is of measure 0. Thus [0, 1]^{d} is the disjoint union of a set of measure 0 plus at most 2^{n}-many sets of the form W_{1} ∩ ⋯ ∩ W_{n} where each W_{i} is either U_{i} or V_{i}. Moreover, each of the sets W_{1} ∩ ⋯ ∩ W_{n} is effectively open, and S and [0, 1]^{d} \ S may be written as the union of some of these sets plus a set of measure 0. Since the measure of an effectively open set is left recursively enumerable, it follows that the measure of S is recursive, i.e., computable. The same argument holds uniformly. □

The following simple lemma is extremely useful in probability theory.

Lemma 3.4 (Chebyshev Inequality). Given f ∈ L_{1} and ϵ > 0, let

S(f, ϵ) = {x | |f(x)| > ϵ} .

Then μ(S(f, ϵ)) ≤ ∥f∥_{1}/ϵ.

Proof. We have ∥f∥_{1} = ∫ |f|dμ ≥ ∫_{S(f,ϵ)} |f|dμ ≥ ϵμ(S(f, ϵ)). □

Lemma 3.5. Let U = ⋃_{n=1}^{∞} U_{n} where U_{n} is uniformly Σ_{1}^{0} and μ(U_{n}) is uniformly computable and μ(U_{n}) ≤ 1/2^{n} for all n. Then U is Σ_{1}^{0} and μ(U) is computable. Moreover, this holds uniformly.

Proof. For all n ∈ ℕ we have U_{n} = ⋃_{k=1}^{∞} B_{nk} where B_{nk}, k = 0, 1, 2, …, is a computable sequence of rational balls. Thus, by diagonalization, we can write U as the union of a computable sequence of rational balls. Thus U is Σ_{1}^{0}. By Lemma 2.12 ⋃_{n=1}^{k} U_{n} is Σ_{1}^{0} and has computable measure uniformly in k. In addition, μ(⋃_{n=k}^{∞} U_{n}) ≤ 1/2^{k−1}. Thus, letting c_{k} = μ(⋃_{n=1}^{k} U_{n}), we have a computable sequence of real numbers which effectively approximates μ(U). □

Lemma 3.6 (see [4, Proposition 4.1]). Let f ∈ L_{1}([0, 1]^{d}) be L_{1}-computable with polynomial approximations f_{n} as in Definition 2.6. Then, we can find a uniformly Σ_{1}^{0} sequence of sets V_{k}, k = 0, 1, 2, …, such that the following statements hold:

(1) μ(V_{k}) ≤ (2 + \sqrt{2})/2^{k−1}.

(2) The sequence μ(V_{k}), k = 1, 2, … is uniformly computable.

(3) For all x ∉ V_{k} and n ≥ k we have

|f_{i}(x) − f_{2n}(x)| ≤ \frac{2 + \sqrt{2}}{2^{n}}

for all i ≥ 2n.

Proof. Let V_{k} = ⋃_{i=2k}^{∞} S_{i} where S_{i} = S(f_{i} − f_{i+1}, 1/2^{i/2}). By Lemma 3.4 we have

μ(V_{k}) ≤ ∑_{i=2k}^{∞} μ(S_{i}) ≤ ∑_{i=2k}^{∞} 2^{i/2}∥f_{i} − f_{i+1}∥_{1} ≤ ∑_{i=2k}^{∞} 2^{i/2}·\frac{2}{2^{i}} ≤ ∑_{i=2k}^{∞} \frac{2}{2^{i/2}} = \frac{2(2 + \sqrt{2})}{2^{k}}.

Moreover, as in [14], V_{k} is uniformly Σ_{1}^{0}.

We claim that that μ(V_{k}) is uniformly computable. By Lemma 3.4 we have μ(S_{i}) ≤ 1/2^{i/2}, so by Lemma 3.5 it suffices to show that μ(S_{i}) is uniformly computable. But S_{i} is uniformly first-order definable, so by Lemma 3.3 S_{i} has computable measure uniformly in i. This proves our claim.

Finally, for all x ∉ V_{k} and n ≥ k and i ≥ 2n we have

|f_{i}(x) − f_{2n}(x)| ≤ ∑_{l=2n}^{i−1} |f_{l}(x) − f_{l+1}(x)|

≤ ∑_{l=2n}^{∞} |f_{l}(x) − f_{l+1}(x)|

≤ ∑_{l=2n}^{∞} \frac{1}{2^{l/2}}

= \frac{2 + \sqrt{2}}{2^{n}}

and this completes the proof. □

Lemma 3.7 (see [4, Remark 4.3]). Let f ∈ L_{1}([0, 1]^{d}) be L_{1}-computable with polynomial approximations f_{n} as in Definition 2.6. Then lim_{n→∞} f_{n}(x) exists for all Schnorr random x.

Proof. Let x ∈ [0, 1]^{d} be Schnorr random. The sets V_{k} of Lemma 3.6 form a Schnorr test. Since x is Schnorr random, we can find k such that x ∉ V_{k}. Moreover, for all x ∉ V_{k} and n ≥ k we have |f_{i}(x) − f_{2n}(x)| ≤ (2 + \sqrt{2})/2^{n} for all i ≥ 2n. Thus f_{n}(x) converges uniformly for all x ∉ V_{k}. In particular lim_{n→∞} f_{n}(x) exists. □

Definition 3.8. Given an L_{1}-computable function f ∈ L_{1}([0, 1]^{d}), define

f̂(x) = \{ \begin{matrix}lim_{n→∞} f_{n}(x) & if x is Schnorr random, \\ 0 & otherwise. \end{matrix}

where f_{n} is a computable sequence of approximations as in Definition 2.6. The following theorem implies that f̂ does not depend on the choice of f_{n}.

Theorem 3.9.

(1) If f ∈ L_{1}([0, 1]^{d}) is L_{1}-computable, then ∥f − f̂∥_{1} = 0.

(2) Given L_{1}-computable functions f, g ∈ L_{1}([0, 1]^{d}), we have ∥f − g∥_{1} = 0 if and only if f̂(x) = ĝ(x) for all x.

Thus f̂ is a canonical representative of the equivalence class of f modulo the equivalence relation ∥f − g∥_{1} = 0.

Proof. For part 1, suppose ∥f − f̂∥_{1} > 0, i.e., μ({x | |f(x) − f̂(x)| > 0}) > 0. Let ϵ > 0 be so small that μ({x | |f(x) − f̂(x)| > ϵ}) > ϵ. By Lemma 3.6, we have |f̂(x) − f_{2n}(x)| ≤ (2 + \sqrt{2})/2^{n} for all Schnorr random x ∉ V_{n}, where μ(V_{n}) ≤ (2 + \sqrt{2})/2^{n−1}, for all n. It follows that

μ(\{x | |f(x) − f_{2n}(x)| > ϵ − (2 + \sqrt{2})/2^{n}\}) > ϵ − (2 + \sqrt{2})/2^{n−1}

for all n. Thus

∥f − f_{2n}∥_{1} > (ϵ − (2 + \sqrt{2})/2^{n})(ϵ − (2 + \sqrt{2})/2^{n−1})

for all n, contradicting the fact that ∥f − f_{2n}∥_{1} goes to 0 as n goes to infinity.

For part 2, note that f̂(x) = ĝ(x) for all x, implies ∥f − g∥_{1} = ∥f̂− ĝ∥_{1} = 0 in view of part 1. It remains to prove that if ∥f − g∥_{1} = 0 then f̂(x) = ĝ(x) for all x. By the definition of f̂, it suffices to prove f̂(x) = ĝ(x) for all Schnorr random x. Let

W_{k} = {x | (∃n ≥ k) (|f_{2n}(x) − g_{2n}(x)| > 1/2^{n})} = ⋃_{n=k}^{∞} S_{n}

where S_{n} = S(f_{2n}−g_{2n}, 1/2^{n}). Clearly W_{k} is uniformly Σ_{1}^{0}. Moreover, ∥f −g∥_{1} = 0 implies ∥f_{2n} − g_{2n}∥_{1} ≤ 1/2^{2n−1}, so by Lemma 3.4 we have

μ(W_{k}) ≤ ∑_{n=k}^{∞} μ(S_{n}) ≤ ∑_{n=k}^{∞} \frac{2^{n}}{2^{2n−1}} = ∑_{n=k}^{∞} \frac{1}{2^{n−1}} = \frac{1}{2^{k−2}} .

Moreover S_{n} is uniformly first-order definable, hence by Lemma 3.3 μ(S_{n}) is uniformly computable, and by Lemma 3.4 we have μ(S_{n}) ≤ 1/2^{n−1}. Thus by Lemma 3.5 μ(W_{k}) is uniformly computable and the sets W_{k} form a Schnorr test. In particular, if x is Schnorr random we have x ∉ W_{k} for some k, hence |f_{2n}(x) − g_{2n}(x)| ≤ 1/2^{n} for all n ≥ k, hence f̂(x) = ĝ(x). □

Remark 3.10. Part 1 of the above theorem follows from the fact that, for an L_{1}-computable function f, the representative f̂ restricted to Martin-Löf random points, equals the layerwise computable representative [11, Proposition 4.2,Theorem 4.3]. The second part of the above theorem may be viewed as a refinement of [11, Theorem 4.3].

The following lemma is the key ingredient in the classical proof of the Lebesgue Differentiation Theorem.

Lemma 3.11 (Hardy/Littlewood Inequality). We can find a positive constant c depending only on the dimension d such that the following holds. Given f ∈ L_{1}([0, 1]^{d}) and ϵ > 0, let S^{∗}(f, ϵ) be the union of all cubes Q such that

(5)  \frac{∫_{Q} |f|dμ}{μ(Q)} > ϵ

holds. Then μ(S^{∗}(f, ϵ)) ≤ c∥f∥_{1}/ϵ.

Proof. See [14, Lemma 4.5]. □

Remark 3.12. If Q is a cube as in (3), note that ∫_{Q} fdμ and μ(Q) depend continuously on a_{1}, …, a_{d}, r since μ is absolutely continuous. Therefore, it is often possible to restrict attention to rational cubes. For instance, in the classical statements of the Lebesgue Differentiation Theorem and the Hardy/Littlewood Inequality, it makes no difference whether we consider arbitrary cubes or rational cubes. The advantage of rational cubes is that they are amenable to computation.

Lemma 3.13. Let f ∈ L_{1}([0, 1]^{d}) be L_{1}-computable with polynomial approximations f_{n} as in Definition 2.6. Let c be the constant from Lemma 3.11. Then, we can find uniformly Σ_{1}^{0} sets V_{k}^{∗}, k = 1, 2, …, such that the following statements hold:

(1) μ(V_{k}^{∗}) ≤ c\frac{2 + \sqrt{2}}{2^{k−1}}.

(2) The sequence μ(V_{k}^{∗}) is uniformly computable.

(3) For all x ∉ V_{k}^{∗} and n ≥ k we have

\frac{∫_{Q} |f − f_{2n}|dμ}{μ(Q)} ≤ \frac{2 + \sqrt{2}}{2^{n}}

for all Q ∋ x.

Proof. We imitate the proof of Lemma 3.6 replacing the Chebyshev inequality by the Hardy-Littlewood inequality. Let V_{k}^{∗} = ⋃_{i=2k}^{∞} S_{i}^{∗} where S_{i}^{∗} = S^{∗}(f_{i} − f_{i+1}, 1/2^{i/2}). By Remark 3.12 the sets V_{k}^{∗} are uniformly Σ_{1}^{0}. By Lemma 3.11 we have μ(V_{k}^{∗}) ≤ ∑_{i=2k}^{∞} μ(S_{i}^{∗}) ≤ ∑_{i=2k}^{∞} 2^{i/2}c∥f_{i} − f_{i+1}∥_{1} ≤ ∑_{i=2k}^{∞} 1/2^{i/2} = 2c(2 + \sqrt{2})/2^{k}. Moreover, by definition we have

S_{i}^{∗} = \{x ∈ [0, 1]^{d} | (∃Q ∋ x) (\frac{1}{μ(Q)} ∫_{Q} |f_{i} − f_{i+1}| ≥ \frac{1}{2^{i/2}} )\}

where Q ranges over cubes in [0, 1]^{d}. Thus S_{i}^{∗} is first-order definable, so by Lemma 3.3 μ(S_{i}^{∗}) is computable, uniformly in i. Since μ(S_{i}^{∗}) ≤ 2c/2^{i/2} it follows by Lemma 3.5 that μ(V_{k}^{∗}) is computable, uniformly in k.

Suppose now that x ∉ V_{k}^{∗}. Then for all rational cubes Q containing x and all n ≥ k and i ≥ 2n we have

\frac{1}{μ(Q)} ∫_{Q} |f_{i} − f_{i+1}| ≤ \frac{1}{2^{i/2}} .

Thus

\frac{1}{μ(Q)} ∫_{Q} |f − f_{2n}| ≤ ∑_{i=2n}^{∞} \frac{1}{2^{i/2}} ≤ \frac{2 + \sqrt{2}}{2^{n}}

and this completes the proof. □

Lemma 3.14. Let f ∈ L_{1}([0, 1]^{d}) be L_{1}-computable with polynomial approximations f_{n} as in Definition 2.6. Then, we can find a computable sequence of rational numbers D_{n} such that the following holds. For all k and all n ≥ k and all x ∉ V_{k}∪V_{k}^{∗} we have

| lim_{m→∞} f_{m}(x) − \frac{∫_{Q} f}{μ(Q)}| ≤ \frac{2 + \sqrt{2}}{2^{n−1}} + D_{n} · (diameter of Q)

for all Q ∋ x. Here V_{k} and V_{k}^{∗} are as in Lemmas 3.6 and 3.13 respectively. In particular, if x ∈ [0, 1]^{d} is Schnorr random, we have

|f̂(x) − \frac{∫_{Q} f}{μ(Q)}| ≤ \frac{2 + \sqrt{2}}{2^{n−2}} + D_{n} · (diameter of Q).

Proof. Since f_{2n} is a polynomial with rational coefficients, we can compute a positive rational number D_{n} which is an upper bound of the maximum gradient max{|∇f_{2n}(x)| | x ∈ [0, 1]^{d}}. It follows by the Mean Value Theorem that

|f_{2n}(x) − \frac{∫_{Q} f_{2n}}{μ(Q)} | ≤ D_{n} · (diameter of Q)

for all x ∈ Q. By Lemmas 3.6 and 3.13 we have

| lim_{n→∞} f_{n}(x) − f_{2n}(x)| ≤ \frac{2 + \sqrt{2}}{2^{n−1}}

and

|\frac{∫_{Q} f}{μ(Q)} − \frac{∫_{Q} f_{2n}}{μ(Q)} | ≤ \frac{∫_{Q} |f − f_{2n}|}{μ(Q)} ≤ \frac{2 + \sqrt{2}}{2^{n−1}}

for all n ≥ k whenever Q ∋ x ∉ V_{k} ∪ V_{k}^{∗}. Combining these inequalities we obtain the desired conclusion. □

Lemma 3.15. Given an L_{1}-computable function f ∈ L_{1}([0, 1]^{d}) with polynomial approximations f_{n} as in Definition 2.6, there exists a Schnorr test U_{n}, n = 1, 2, … such that for all x ∉ ⋂_{n} U_{n},

lim_{n→∞} f_{n}(x) = lim_{Q→x} \frac{∫_{Q} f}{μ(Q)}

where the limit is taken over all Q ∋ x as the diameter of Q tends to 0.

Proof. This follows from Lemma 3.14. □

Theorem 3.16. Let f ∈ L_{1}([0, 1]^{d}) be L_{1}-computable. Then for all Schnorr random x we have

(6)  f̂(x) = lim_{Q→x} \frac{∫_{Q} f}{μ(Q)}

where the limit is taken over all cubes Q ∋ x as the diameter of Q tends to 0.

Proof. The sets V_{k} and V_{k}^{∗} form Schnorr tests. Hence, for any Schnorr random x ∈ [0, 1]^{d} we can find k such that x ∉ V_{k} ∪ V_{k}^{∗}. Given ϵ > 0 let n ≥ k be so large that

\frac{2 + \sqrt{2}}{2^{n−2}} < \frac{ϵ}{2}

and let D_{n} be as in Lemma 3.14. We then have

|f̂(x) − \frac{∫_{Q} f}{μ(Q)}| < \frac{2 + \sqrt{2}}{2^{n−2}} + \frac{ϵ}{2} < ϵ

for all Q of diameter < ϵ/2D_{n}. This completes the proof. □

Remark 3.17. Lemma 3.15, combined with the fact that every Schnorr test admits computable points passing the test (see for instance [15, Theorem 5.1.0.4]), implies the following interesting observation.

Corollary 3.18. Given a computable sequence of L_{1}-computable functions f_{i} ∈ L_{1}([0, 1]^{d}) with approximating sequences f_{in} as in Definition 2.6, and given an effectively closed set P ⊆ [0, 1]^{d} of computable positive measure, we can effectively find a computable point x ∈ P such that for each i we have

lim_{n→∞} f_{in}(x) = lim_{Q→x} \frac{∫_{Q} f}{μ(Q)}

where the limit is taken over all Q ∋ x as the diameter of Q tends to 0.

Remark 3.19. The classical Lebesgue Differentiation Theorem (see Remark 2.3) follows from Theorem 3.16 by relativization to an arbitrary Turing oracle. Thus, Lemma 3.14 and Theorem 3.16 may be viewed as computationally motivated refinements or generalizations of the Lebesgue Differentiation Theorem. Such results were first obtained by Pathak in [14] which was based on her undergraduate research project performed under Simpson’s supervision.

4. Lebesgue points for L_{1}-computable functions are Schnorr

Remark 4.1. In this section we shall prove a converse to Theorem 3.16. Namely, if x ∈ [0, 1]^{d} is such that the limit in (6) exists for all L_{1}-computable functions f ∈ L_{1}([0, 1]^{d}), then x is random in the sense of Schnorr. In fact, we shall associate a particular f to each Schnorr test, as stated in Lemmas 4.5 and 4.6.

Definition 4.2. Two cubes Q_{1} and Q_{2} are said to be almost disjoint if their intersection is entirely contained in the boundary of Q_{1}.

Lemma 4.3. Let Q_{1}, …, Q_{n} be a finite sequence of pairwise almost disjoint rational cubes, and let R be a rational cube such that R ⊈ Q_{1} ∪ ⋯ ∪ Q_{n}. Then, we can effectively extend Q_{1}, …, Q_{n} to a longer finite sequence of pairwise almost disjoint rational cubes Q_{1}, …, Q_{n}, Q_{n+1}, …, Q_{n+k} such that

Q_{1} ∪ ⋯ ∪ Q_{n} ∪ Q_{n+1} ∪ ⋯ ∪ Q_{n+k} = Q_{1} ∪ ⋯ ∪ Q_{n} ∪ R.

Proof. Let m ∈ ℕ be the common denominator of all of the coordinates of all of the vertices of Q_{1}, …, Q_{n}, R. We can then break up each of these cubes into almost disjoint cubes with edge length 1/m. That is, we can write each of Q_{1}, …, Q_{n}, R as a finite union of pairwise almost disjoint cubes of the form

\{⟨x_{1}, …, x_{d}⟩ | x_{i} ∈ [\frac{l_{i}}{m}, \frac{l_{i} + 1}{m}] , i = 1, …, d\}

where l_{1}, …, l_{d} are natural numbers less than m. Let Q_{n+1}, …, Q_{n+k} be a list of the cubes of this form that are contained in R and not contained in Q_{1}, …, Q_{n}. This gives our desired conclusion. □

Lemma 4.4. Given a nonempty Σ_{1}^{0} set U ⊆ [0, 1]^{d}, we can effectively find a computable sequence of pairwise almost disjoint rational cubes Q_{i} such that U = ⋃_{i=1}^{∞} Q_{i}.

Proof. Let R_{i}, i = 1, 2, … be a computable sequence of rational cubes such that U = ⋃_{i=1}^{∞} R_{i}. We shall refine this to a pairwise almost disjoint sequence. Assume inductively that we have found a pairwise disjoint sequence of rational cubes Q_{1}, …, Q_{n_{k}} such that ⋃_{i=1}^{k} R_{i} = ⋃_{j=1}^{n_{k}} Q_{j}. We may safely assume that R_{k+1} ⊈ ⋃_{i=1}^{k} R_{i}. Apply Lemma 4.3 to effectively find a longer pairwise disjoint sequence of rational cubes Q_{1}, …, Q_{n_{k+1}} with n_{k+1} > n_{k} such that ⋃_{i=1}^{k+1} R_{i} = ⋃_{j=1}^{n_{k+1}} Q_{j}. Letting k go to infinity we obtain a computable sequence of pairwise disjoint rational cubes Q_{j}, j = 1, 2, … such that ⋃_{i=1}^{∞} R_{i} = ⋃_{j=1}^{∞} Q_{j}. □

Lemma 4.5. Given a Schnorr test U_{n}, n = 1, 2, …, we can construct a bounded (in fact 0, 1-valued) L_{1}-computable function f ∈ L_{1}([0, 1]^{d}) such that

lim sup_{Q→x} \frac{∫_{Q} fdμ}{μ(Q)} ≥ \frac{3}{4}  and  lim inf_{Q→x} \frac{∫_{Q} fdμ}{μ(Q)} ≤ \frac{1}{4}

for all x = ⟨x_{1}, …, x_{d}⟩ ∈ ⋂_{n} U_{n} such that x_{1}, …, x_{d} are irrational.

Proof. Let Seq be the set of finite sequences of natural numbers. For σ = ⟨i_{1}, …, i_{n}⟩ ∈ Seq we write |σ| = n = the length of σ. We use ⟨⟩ to denote the empty sequence, i.e., the unique member of Seq of length 0. For σ, τ ∈ Seq let σ^{⌢}τ be their concatenation, i.e., σ followed by τ.

To each σ ∈ Seq we effectively associate a rational cube Q_{σ} by induction on |σ|. We begin with Q_{⟨⟩} = [0, 1]^{d}. Given Q_{σ}, we effectively find an integer n_{σ} so large that μ(Q_{σ} ∩ U_{n_{σ}}) < μ(Q_{σ})/4. Then we apply Lemma 4.4 to effectively obtain a pairwise almost disjoint computable sequence of rational cubes Q_{σ^{⌢}⟨i⟩}, i = 0, 1, 2, … such that

U_{n_{σ}} ∩ (interior of Q_{σ}) = ⋃_{i=0}^{∞} Q_{σ^{⌢}⟨i⟩} .

In this way we construct Q_{σ} for all σ ∈ Seq.

Similarly we assign values to f. For all x ∈ Q_{σ} \ U_{n_{σ}} let

f(x) = \{ \begin{matrix}1 & if |σ| is odd, \\ 0 & if |σ| is even. \end{matrix}

In particular f(x) is defined for all x ∈ [0, 1]^{d} \ ⋂_{n} U_{n}. Since f is 0, 1-valued and μ(⋂_{n} U_{n}) = 0, we clearly have f ∈ L_{1}([0, 1]^{d}).

Now let x = ⟨x_{1}, …, x_{d}⟩ ∈ ⋂_{n} U_{n} be such that x_{1}, …, x_{d} are irrational. Let h : ℕ → ℕ be such that x ∈ Q_{h↾k} for all k. (Note that the existence of h is not guaranteed if even a single coordinate of x is rational, because then x could be on the boundary of a cube Q_{σ}, in which case x ∉ ⋃_{i} Q_{σ^{⌢}⟨i⟩} even though x ∈ Q_{σ} ∩U_{n_{σ}}.) If k is odd we have f = 1 on Q_{h↾k} \ U_{n_{h↾k}}, hence

\frac{1}{μ(Q_{h↾k})} ∫_{Q_{h↾k}} fdμ ≥ \frac{μ(Q_{h↾k} \ U_{n_{h↾k}})}{μ(Q_{h↾k})} > \frac{3}{4}

so lim sup_{Q→x} ∫_{Q} fdμ/μ(Q) ≥ 3/4. If k is even we have f = 0 on Q_{h↾k} \ U_{n_{h↾k}}, hence

\frac{1}{μ(Q_{h↾k})} ∫_{Q_{h↾k}} fdμ ≤ \frac{μ(Q_{h↾k} ∩ U_{n_{h↾k}})}{μ(Q_{h↾k})} < \frac{1}{4}

so lim inf_{Q→x} ∫_{Q} fdμ/μ(Q) ≤ 1/4.

It remains to show that f is L_{1}-computable. We shall construct a computable sequence of finite rational step functions f_{m} which approximates f. In order to construct f_{m}, we shall first construct a finite sequence of integers l_{m,1}, …, l_{m,m}. Assume inductively that we have defined l_{m,1}, …, l_{m,k} where 0 ≤ k < m. Let

T_{m,k} = {⟨i_{1}, …, i_{k}⟩ | 0 ≤ i_{1} ≤ l_{m,1}, …, 0 ≤ i_{k} ≤ l_{m,k}} .

For each σ ∈ T_{m,k} we know that U_{n_{σ}} ∩ (interior of Q_{σ}) = ⋃_{i=0}^{∞} Q_{σ^{⌢}⟨i⟩} and μ(U_{n_{σ}} ∩ Q_{σ}) is effectively computable. Hence, we can effectively find l_{m,k+1} so large that

∑_{σ∈T_{m,k}} μ(W_{σ}) < \frac{1}{2^{m+k}}  where  W_{σ} = U_{n_{σ}} ∩ Q_{σ} \ ⋃_{i=0}^{l_{m,k+1}} Q_{σ^{⌢}⟨i⟩} .

This completes the definition of l_{m,1}, …, l_{m,m}. We now define f_{m} as follows. For all x ∈ (interior of Q_{σ}) \ ⋃_{i=0}^{l_{m,k+1}} Q_{σ^{⌢}⟨i⟩} where σ ∈ T_{m,k} and 0 ≤ k < m, let

f_{m}(x) = \{ \begin{matrix}1 & if |σ| is odd, \\ 0 & if |σ| is even. \end{matrix}

For all other x let f_{m}(x) = 0.

Note that f(x) = f_{m}(x) for all x except possibly when x ∈ W_{σ} for some σ ∈ T_{m,k} and 0 ≤ k < m, or when x ∈ Q_{σ} for some σ such that |σ| = m. We shall use this observation to show that ∥f − f_{m}∥_{1} is small. First, note that

μ( ⋃_{k<m} ⋃_{σ∈T_{m,k}} W_{σ}) < ∑_{k<m} \frac{1}{2^{m+k}} < \frac{1}{2^{m−1}} .

In addition, by construction of the Q_{σ}’s we have

μ(⋃_{i=0}^{∞} Q_{σ^{⌢}⟨i⟩}) < \frac{μ(Q_{σ})}{4}

for each σ, hence by induction on m we have

μ( ⋃_{|σ|=m} Q_{σ}) ≤ \frac{1}{4^{m}}

in view of almost disjointness. Since f and f_{m} are 0, 1-valued, it follows that

∥f − f_{m}∥_{1} < \frac{1}{2^{m−1}} + \frac{1}{4^{m}} < \frac{1}{2^{m−2}}

for all m. Thus f is L_{1}-computable. □

Lemma 4.6. Let x = ⟨x_{1}, …, x_{d}⟩ ∈ [0, 1]^{d} be such that at least one of x_{1}, …, x_{d} is rational. Then, we can construct a bounded (in fact 0, 1-valued) L_{1}-computable function f ∈ L_{1}([0, 1]^{d}) such that

lim sup_{Q→x} \frac{∫_{Q} fdμ}{μ(Q)} ≥ \frac{3}{4}  and  lim inf_{Q→x} \frac{∫_{Q} fdμ}{μ(Q)} ≤ \frac{1}{4}.

Proof. We may safely assume that x_{1} = q is rational. For each n let S_{n} ⊆ [0, 1]^{d} be a slice of [0, 1]^{d} defined by S_{n} = ([q − 1/2^{2n}, q + 1/2^{2n}] ∩ [0, 1]) × [0, 1]^{d−1}. The width of this slice is μ(S_{n}) = μ([q − 1/2^{2n}, q + 1/2^{2n}] ∩ [0, 1]) ≤ 1/2^{2n−1}. Moreover S_{0} = [0, 1]^{d} and x ∈ ⋂_{n} S_{n}. Define f ∈ L_{1}([0, 1]^{d}) by

f(x) = \{ \begin{matrix}1 & if x ∈ S_{n} \ S_{n+1} where n is odd, \\ 0 & if x ∈ S_{n} \ S_{n+1} where n is even. \end{matrix}

Let Q_{n} be a cube such that x ∈ Q_{n} ⊆ S_{n} and the edge length of Q_{n} is equal to the width of S_{n}, so that μ(Q_{n}) = μ(S_{n})^{d}. For odd n we have f = 1 on Q_{n} \ S_{n+1}, hence

\frac{1}{μ(Q_{n})} ∫_{Q_{n}} fdμ ≥ \frac{μ(Q_{n} \ S_{n+1})}{μ(Q_{n})} ≥ \frac{3}{4}

so lim sup_{Q→x} ∫_{Q} fdμ/μ(Q) ≥ 3/4. For even n we have f = 0 on Q_{n} \ S_{n+1}, hence

\frac{1}{μ(Q_{n})} ∫_{Q_{n}} fdμ ≤ \frac{μ(Q_{n} ∩ S_{n+1})}{μ(Q_{n})} ≤ \frac{1}{4}

so lim inf_{Q→x} ∫_{Q} fdμ/μ(Q) ≤ 1/4.

It remains to show that f is L_{1}-computable. Consider a computable sequence of finite rational step functions f_{k} defined by

f_{k}(x) = \{ \begin{matrix}1 & if x ∈ S_{n} \ S_{n+1} where n is odd and n < k, \\ 0 & otherwise. \end{matrix}

Then ∥f − f_{k}∥_{1} ≤ μ(S_{k}) ≤ 1/2^{2k−1} and thus f is L_{1}-computable. □

Theorem 4.7. For all x ∈ [0, 1]^{d} the following are pairwise equivalent. (1) x is Schnorr random.

(2) lim_{Q→x} \frac{∫_{Q} f}{μ(Q)} exists for all L_{1}-computable functions f ∈ L_{1}([0, 1]^{d}).

(3) For all L_{1}-computable functions f ∈ L_{1}([0, 1]^{d}) and approximating sequences f_{n} as in Definition 2.6, we have

lim_{n→∞} f_{n}(x) = lim_{Q→x} \frac{∫_{Q} f}{μ(Q)}

and both limits exist.

Proof. The implication 1 ⇒ 3 has been proved in Theorem 3.16. The implication 3 ⇒ 2 is trivial, and 2 ⇒ 1 is obtained by combining Lemmas 4.5 and 4.6. □

Remark 4.8. Clearly the numbers 1/4 and 3/4 in Lemmas 4.5 and 4.6 are arbitrary and can be replaced by any pair ϵ, 1 − ϵ with 0 < ϵ < 1. Indeed, one can construct a 0, 1-valued L_{1}-computable function f such that lim inf_{Q→x} ∫_{Q} fdμ/μ(Q) = 0 and lim sup_{Q→x} ∫_{Q} fdμ/μ(Q) = 1 for all x ∈ ⋂_{n} U_{n}. Thus for any x ∈ [0, 1]^{d} which is not Schnorr random, the Lebesgue Differentiation Theorem for 0, 1-valued L_{1}- computable functions fails as badly as possible. We thank the referee for pointing this out.

References

1. Jeremy Avigad, Philipp Gerhardy, and Henry Towsner, Local stability of ergodic averages, Transactions of the American Mathematical Society 362 (2010), 261–288. 1, 2

2. Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, and Alexander Shen, A constructive version of Birkhoff’s Ergodic Theorem for Martin-Löf random points, Submitted for publication. ArXiv 1007.5249, 2010. 2

3. Vasco Brattka, Joseph S. Miller, and André Nies, Randomness and differentiability, Transactions of the American Mathematical Society (2014 (estimated)), Preprint, http://arxiv.org/abs/1104.4465v4, 39 pages; to appear in TAMS pending acceptance of revised version. 2

4. Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson, Vitali’s theorem and WWKL, Archive for Mathematical Logic 41 (2002), 191–206. 6, 7

5. Rodney G. Downey and Denis Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer-Verlag, 2010, XXVIII + 855 pages. 4

6. Johanna N. Y. Franklin, Noam Greenberg, Joseph S. Miller, and Keng Meng Ng, Martin-Löf random points satisfy Birkhoff’s Ergodic Theorem for effectively closed sets, Proceedings of the American Mathematical Society 140 (2012), no. 10, 3623–3628. 2

7. Peter Gács, Mathieu Hoyrup, and Cristóbal Rojas., Randomness on computable probability spaces – a dynamical point of view, Theory of Computing Systems, Special Issue, STACS 2009 48 (2011), no. 3, 465 – 485. 1

8. Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas, Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems, Electronic Proceedings in Theoretical Computer Science 24 (2010), 7–18, http://arxiv.org/abs/1006.0392v1. 1, 2

9. Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas., Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Information and Computation 208 (2010), no. 1, 23 – 41. 1

10. Wilfrid Hodges, Model Theory, Encyclopedia of Mathematics and its Applications, no. 42, Cambridge University Press, 1993, XIII + 772 pages. 5

11. Mathieu Hoyrup and Cristóbal Rojas, An application of Martin-Löf randomness to effective probability theory., Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice (Berlin, Heidelberg), CiE ’09, Springer-Verlag, 2009, pp. 260–269. 8

12. Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces., Information and Computation 207 (2009), no. 7, 830–847. 3, 4, 5

13. André Nies, Computability and Randomness, Oxford University Press, 2009, XV + 433 pages. 4

14. Noopur Pathak, A computational aspect of the Lebesgue Differentiation Theorem, Journal of Logic and Analysis 1 (2009), no. 9, 15. 2, 4, 6, 8, 10

15. Cristóbal Rojas, Randomness and ergodic theory: an algorithmic point of view, Ph.D. thesis, École Polytechnique, 2008. 3, 5, 10

16. Vladimir V’yugin., Effective convergence in probability and an ergodic theorem for individual random sequences, SIAM Theory of Probability and Its Applications 42 (1997), no. 1, 39–50. 1

17. Richard L. Wheeden and Antoni Zygmund, Measure and Integral: an Introduction to Real Analysis, Monographs and Textbooks in Pure and Applied Mathematics, no. 43, M. Dekker, New York, 1977, X + 274 pages. 3 Department of Mathematics, Pennsylvania State University, 16802, USA

E-mail address: pathak@math.psu.edu

Departamento de Matemáticas, Universidad Andres Bello, Santiago, Chile

E-mail address: cristobal.rojas@unab.cl

Department of Mathematics, Pennsylvania State University, 16802, USA

E-mail address: simpson@math.psu.edu