An application of Shoenfield’s absoluteness theorem

to the theory of uniform distribution

Martin Goldstern

October 1992/January 1993

ABSTRACT. Theorem: If C is a Polish probability space, W ⊆ ω^{ω} × C a Borel set whose sections W_{x} (x ∈ ω^{ω}) have measure one and are decreasing (x ≤ x′ → W_{x} ⊇ W_{x′}), then the set ⋂_{x} W_{x} has measure one. We give two proofs of this theorem: one in the language of set theory, the other in the language of probability theory, and we apply the theorem to a question on completely uniformly distributed sequences.

Shoenfield’s absoluteness theorem and uniform distribution

Supported by DFG grant Ko 490/7-1 Introduction.

The law of large numbers implies that almost every infinite sequence in {0, 1} is uniformly distributed, i.e., for almost all t ∈ ^{ω}2 we have lim_{n→∞} D(t, n) = 0, where 2 = {0, 1}, ω = \{0, 1, 2, …\}, and the “discrepancy” D is defined by D(t, n) = 2 · |\frac{|\{i<n:t(i)=0\}|}{n} − \frac{1}{2} |, and “almost all” refers to the product measure on ^{ω}2 induced by the equidistributed measure on \{0, 1\}, i.e., μ(\{0\}) = μ(\{1\}) = \frac{1}{2}. A similar argument shows that for all k, almost all sequences are k-uniformly distributed, i.e., for all k, for almost all t ∈ ^{ω}2 we have lim_{n→∞} D_{k}(t, n) = 0, where

D_{k}(t, n) := 2^{k} · max_{w∈^{k}2} |\frac{|\{i < n : (t(i), …, t(i + k − 1)) = w\}|}{n} − \frac{1}{2^{k}} |

Since the measure is countably additive, we can switch the quantifiers “for all k” and “for almost all t” and get:

for almost all t ∈ ^{ω}2, for all k, t is k-uniformly distributed

If we replace the constant k by a function s ∈ ^{ω}ω we are led to the following concept: A sequence t ∈ ^{ω}2 is called s-uniformly distributed, if lim_{n→∞} D_{s(n)}(t, n) = 0. Let R_{s} be the set of s-uniformly distributed sequences. It is easy to see that s must not grow faster than log n (in this paper, log always means the logarithm to the base 2) if the set R_{s} should be nonempty. Flajolet-Kirschenhofer-Tichy and Grill determined the exact bound for s below which still almost all sequences are s-uniformly distributed:

1. Theorem ([2], [4]): μ(R_{s}) = 1 iff φ_{s} → ∞, where φ_{s}(n) = ⌊log n − log log n − s(n)⌋. See also [3] for a generalization of this result.

Now let

R = ⋂_{s} R_{s}

where s ranges over all functions with φ_{s} → ∞. Since R is an uncountable intersection of measure one sets, it is a priori not clear if R has measure one, or indeed if R can be nonempty. We will show below that R must have measure 1. That is, as in the remark about kuniformly distributed, we can again switch quantifiers and get

2. Theorem: For almost all t ∈ ^{ω}2, for all s for which φ_{s} → ∞ we have: t is s-uniformly distributed.

We will give two proofs of this theorem: One for logicians, using the technique of forcing and Shoenfield’s absoluteness theorem for Σ_{2}^{1}-sets, and the second for those mathematicians who are more familiar with the language of probability theory. Here we use von Neumann’s theorem that Borel sets can be uniformized by measurable functions.

3. Notation: ω is the set of natural numbers. 2 = {0, 1}. ωω is the Baire space ( = all functions from ω to ω) with the usual metric and topology. The variable x always ranges over elements of ^{ω}ω. This spaces is naturally ordered by x_{1} ≤ x_{2} ⇔ ∀n x_{1}(n) ≤ x_{2}(n). ω↗ω is the set of sequences which diverge to infinity, a subspace of ^{ω}ω. The variable y always ranges over elements of ω↗ω. Let C be any perfect Polish space (i.e., complete metric separable) with a complete probability measure μ (i.e., μ is σ-additive, all Borel sets are measurable, and all subsets of measure zero sets are measurable). The reader may think of C = ^{ω}2, the set of all functions from ω to 2. The variable t always ranges over C. Analytic sets (also called Σ_{1}^{1} sets) are those subsets of C which can be obtained as projections of Borel sets in C ×^{ω}ω (or equivalently, are a continuous image of ω^{ω}). A subset of C is coanalytic or Π_{1}^{1} iff its complement is analytic. (All propositions below will remain true if “Σ_{1}^{1}” and “Π_{1}^{1}” are replaced by “Borel”.) It is well known that all analytic sets are measurable. ([6], see also [7, 2H.8]) All facts from descriptive set theory that we use here can be found in Moschovakis book [7]. For facts and references about forcing consult [5].

4. Acknowledgement: Thanks to Reinhard Winkler for interesting dicussions about random numbers.

The main lemma and its application

5. Main Lemma: Assume that for each y ∈ ω↗ω we have a set U_{y} ⊆ C such that (A) The set {(y, t) : y ∈ ω↗ω, t ∈ U_{y}} is a Π_{1}^{1} subset of ⊆ ω↗ω × C. (B) For all y ∈ ω↗ω, μ(U_{y}) = 1 (C) If y ≤ y′ (that means ∀n y(n) ≤ y′(n)), then U_{y} ⊆ U_{y′}

Then μ(⋂_{y∈ω↗ω} U_{y}) = 1.

We will actually not prove the lemma itself, but an equivalent version:

6. Lemma: Assume that for each x ∈ ^{ω}ω we have a set W_{x} ⊆ C such that (A’) The set {(x, t) : x ∈ ^{ω}ω, t ∈ W_{x}} is a Π_{1}^{1} set ⊆ ^{ω}ω × C. (B’) For all x ∈ ^{ω}ω, μ(W_{x}) = 1 (C’) If x ≤ x′, then W_{x} ⊇ W_{x′} Then μ(⋂_{x∈^{ω}ω} W_{x}) = 1.

Proof that lemma 6 implies lemma 5: For every unbounded x ∈ ^{ω}ω we define its “inverse” function x^{∗} ∈ ω↗ω by

x^{∗}(n) = min{m : x(m) ≥ n}

Now given a family (U_{y} : y ∈ ω↗ω) let W_{x} := U_{x^{∗}} for all unbounded x ∈ ^{ω}ω, and W_{x} = C otherwise. We claim ⋂_{y} U_{y} = ⋂_{x} W_{x}. The inclusion “⊆” is clear. For the converse inclusion, it is enough to see

∀y ∈ ω↗ω ∃x ∈ ^{ω}ω : x^{∗} ≤ y

Given y ∈ ω↗ω, we can find a sequence x which increases so fast that for all n, x(y(n)) ≥ n, e.g., x(m) := max{k : y(k) ≤ m}. So x^{∗}(n) = min{i : x(i) ≥ n} ≤ y(n). Hence ⋂_{x} W_{x} = ⋂_{y} U_{y} has measure 1.

7. Application: let C = ^{ω}2 with the usual product measure. Let s range over functions in ^{ω}ω satisfying φ_{s} ≥ 0 and φ_{s} → ∞, where φ_{s} = ⌊log n − log log n − s(n)⌋. Let R_{s} be the set of s-uniformly distributed sequences in 2^{ω}, and let R := ⋂_{s} R_{s}. It is easy to check that s ≤ s′ implies R_{s′} ⊆ R_{s}, and φ_{φ_{s}} = s. For each function y ∈ ω↗ω let

U_{y} = \{ \begin{matrix}R_{φ_{y}} & if y ≤ log − log log \\ 2^{ω} & otherwise \end{matrix}

Now check that all the assumptions of the main lemma are satisfied. If φ_{s} → ∞, then letting y := φ_{s} we have s = φ_{y}, so R_{s} ⊇ R_{φ_{y}} = U_{y}. Hence R = ⋂_{s} R_{s} has measure 1.

8. Remark: Note that the inclusion in lemma 5(C) or lemma 6(C’) cannot be replaced by an “almost” inclusion (modulo measure zero sets or even modulo finite sets): Let F be a Borel isomorphism between ^{ω}ω and C (see [7, 1G4]), and let W_{x} = C − {F (x)}, then ⋂_{x} W_{x} = ∅.

9. Other applications: Almost every metric result in which a o( ) appears can be strenghtened by using lemma 5. For example, Drmota-Winkler showed that

If s(N) = o(\sqrt{N/ log N}), then μ(T_{s}) = 1,

where T_{s} is the set of s-uniformly distributed sequences x ∈ [0, 1]^{ω} (see [1] for definitions and references), and s(N) = o(\sqrt{N/ log N}) means that lim_{N} s(N) /\sqrt{N/ log N} = 0.

Now for y ∈ ω↗ω let s_{y}(N) = ⌊\sqrt{N/ log N}/ y(N)⌋, and let U_{y} = T_{s_{y}}. Applying the lemma we immediately get that

μ(⋂_{s} T_{s}) = 1

where the intersection is taken over all s satisfying s(N) = o(\sqrt{N/ log N}).

Proof of lemma 6 for logicians The set W := {t : ∀x t ∈ W_{x}} is a Π_{1}^{1} set, hence measurable. Assume that μ(W) < 1. So there exists a Borel (G_{δ}) set A with μ(A) < 1 such that W ⊆ A. Note that the statement

(∗) ∀t : [∀x t ∈ W_{x} ⇒ t ∈ A]

is a Π_{2}^{1}-statement, hence absolute between any two transitive universe with the same ordinals ([9], see also [7, 8F10]). Now let r be a random real over the universe V, r ∈ C − A, and work in V [r]. Random forcing is ^{ω}ω-bounding, i.e., we have

∀x ∈ ^{ω}ω ∃x′ ∈ ^{ω}ω ∩ V : x ≤ x′

Since the condition (C’) is also absolute, this implies ∀x ∈ ^{ω}ω ∃x′ ∈ ^{ω}ω ∩ V : W_{x} ⊇ W_{x′}, and so

⋂_{x∈^{ω}ω} W_{x} = ⋂_{x′∈^{ω}ω∩V} W_{x′}

Moreover,

∀x′ ∈ ^{ω}ω ∩ V : r ∈ W_{x′}

(since r is a random real and each W_{x′} contains a Borel set of full measure), so together we get

∀x ∈ ^{ω}ω : r ∈ W_{x}.

Since (∗) holds also in V [r], we get V [r] ⊧ r ∈ A, a contradiction.

Proof of lemma 6 for probabilists Now we repeat our argument in the language of probability theory. Our main tool is von Neumann’s selection theorem ([8], see also [7, 4E9]). We let our probability space be C. We will consider random variables (= measurable functions) T from C into C, and random variables X from C into ^{ω}ω.

10. Definition: Let B ⊆ C ×^{ω}ω. We say that f “uniformizes” B iff (1) f ⊆ B

(2) f is a partial function.

(3) dom(f) = {t : ∃x (t, x) ∈ B}. The von Neumann selection theorem says that every Σ_{1}^{1} set can be uniformized by a measurable function. (Note that the possibly better known Π_{1}^{1} uniformization theorem will in general not yield measurable functions [7, 5A7].) Hence we get:

11. Lemma: Let B ⊆ C×^{ω}ω be a Σ_{1}^{1} set. Assume that ∀t ∈ C ∃x ∈ ^{ω}ω (t, x) ∈ B. Then

(1) ∃Xμ[(I, X) ∈ B] = 1, where I is the identity function from C to C, and X ranges over all random variables in ^{ω}ω.

(2) Moreover, ∀T ∃Xμ[(T, X) ∈ B] = 1. Here, T and X range over random variables in C and ^{ω}ω, respectively.

Proof: (1) — There is a measurable function f ⊆ B with domain C. So for all t ∈ C, (t, f(t)) ∈ B. Let X := f.

(2) — Let f be the function from (1), and let X = f ∘ T.

12. Remark: Those logicians who have not skipped this section will notice that (2) is again Shoenfield’s theorem, since random variables naturally correspond to IB-names of reals (where IB is the random algebra).

We will also need the following easy fact about random variables X : C → ^{ω}ω (which corresponds to the fact that random forcing is ^{ω}ω-bounding):

13. Fact: Let X : C → ^{ω}ω be a random variable. Then there is a family (x_{n} : n ∈ ω) of functions in ^{ω}ω such that

μ[∃n X ≤ x_{n}] = 1

Proof: Call a Borel set A ⊆ C of positive measure “good” if there is a function x_{A} ∈ ^{ω}ω such that A ⊆ [X ≤ x_{A}]. If there are finitely many good sets covering C (up to a measure zero set) then we are done. Otherwise, let (A_{n} : n ∈ ω) be a maximal antichain of good sets, i.e., a maximal family of sets which are

(1) good

(2) pairwise disjoint Such a sequence can be found using Zorn’s lemma. Again, if ⋃_{n} A_{n} covers C up to a measure zero set then we are done. So assume that A := C−⋃_{n} A_{n} has positive measure ε. Define a sequence (k_{n} : n ∈ ω) of natural numbers such that for each n the set [X(n) > k_{n}] has measure < ε/2^{n+3}. Thus, the set [∀n X(n) ≤ k_{n}] ∩ A has measure ≥ ε − ε/4 > 0, contradicting the maximality of the family (A_{n} : n ∈ ω).

14. Second proof of lemma 6: Let I : C → C be the identity function. Clearly, for any x ∈ ^{ω}ω we have μ[I ∈ W_{x}] = μ(W_{x}) = 1. We now claim that the same is still true if we replace x by a random variable X. Indeed, let X be a random variable, X : C → ^{ω}ω. Then we can find a family of functions (x_{n} : n ∈ ω) such that

μ[∃n X ≤ x_{n}] = 1

Using the anti-monotonicity of the family (W_{x} : x ∈ ^{ω}ω) we get

μ[∃n W_{X} ⊇ W_{x_{n}}] = 1

and so: μ[W_{X} ⊇ ⋂_{n} W_{x_{n}}] = 1. Hence

(∗) μ[I ∈ W_{X}] ≥ μ[I ∈ ⋂_{n} W_{x_{n}}] = μ(⋂_{n} W_{x_{n}}) = 1

for all random variables X. So for all X μ[I ∉ W_{X}] = 0, hence by the contrapositive of lemma 11 it is impossible that ∀t ∃x t ∉ W_{x}. Therefore

∃t ∀x t ∈ W_{x}

So the set ⋂_{x} W_{x} is nonempty. Relativizing the above argument to any positive Borel set A we can show that the set A ∩ ⋂_{x} W_{x} is nonempty. Hence W has outer measure 1. As remarked above, W must be measurable, so indeed μ(W) = 1.

References.

[1] M. Drmota and R. Winkler, s(N)-uniform distribution modulo 1.

[2] P. Flajolet, P. Kirschenhofer and R.F. Tichy, Deviations from uniformity in random strings, Probab. Th. Rel. Fields 80 (1988), 139–150.

[3] P. Grabner, Block Distribution in Random Strings, Annales de l’Institut Fourier.

[4] K. Grill, A note on Randomness, Stat. and Probab. Letters.

[5] T. Jech, Multiple forcing, Cambridge Tracts in Mathematics 88, Cambridge 1986.

[6] N. Lusin, Sur la classification de M. Baire, Comptes Rendus Acad. Sci. Paris 164 (1917) 91–94.

[7] Y.N. Moschovakis, Descriptive Set Theory, Studies in Logic and the foundation of Mathematics, vol 100, North-Holland 1980.

[8] J. von Neumann, On rings of operators. Reduction theory. Ann. Math. 50 (1949) 448–451.

[9] J.R. Shoenfield, The problem of predicativity, Essay on the foundation of Mathematics, Magnes Press, Hebrew Univ. Jerusalem (1961) 132–139.

[10] R.F. Tichy, Zur Analyse und Anwendung von Zufallszahlen, Jahrbuch d. Kurt Goedel Ges. 109–116 (1990

[11] R. Winkler, Some remarks on Pseudorandom Sequences.

Martin Goldstern

2. Mathematisches Institut FU Berlin Arnimallee 3 1000 Berlin 33

goldstrn@math.fu-berlin.de