4. erraticity is Borel

problem

For $x∈𝒞$ and $n≥1$, let $A_n (x)≔∑_{i=0}^(n-1)x_i/n$ be the average of the first $n$ bits of $x$. Call a point $x∈𝒞$ erratic if for every $δ∈[0,1]$, the sequence $(A_n (x))_{n≥1}$ has a subsequence that converges to $δ$. (So an erratic point $x∈𝒞$ is as far from having a well-defined density as possible.) Show that the set of all erratic points is a Borel subset of $𝒞$.

We’ll prove two lemmas characterizing the set of erratic points. Either one suffices for the proof we’re after, but I’m keeping both because they’re interesting in their own right: the first result is simpler, easier to prove, and more general, but weaker; the second is stronger but more specialized and complicated to prove.

lemma

$x∈𝒞$ is erratic iff for all $δ∈[0,1]∩ℚ$, $A_n (x)$ has a subsequence converging to $δ$.

proof

simplify writing let’s call this condition on the right “rational-erratic”. $x$ erratic trivially implies $x$ rational-erratic. We wish to show the converse:

Suppose $x$ is rational-erratic. Fix a $δ∈[0,1]$, and let $(δ_k)_{k∈ℕ}∈[0,1]∩ℚ$ be a sequence converging to $δ$. For each $k$, by rational-erraticity there exists a subsequence $(A_{n_k (i}))_{i∈ℕ}→δ_k$.

Fix $l∈ℕ$. Let $k∈ℕ$ so that $abs(δ_k-δ)≤1/l$, and define > $n(l)∈\{nₖ(i):i∈ℕ\}$ so that:

• $n(l) ≥ n(l-1)$ (indices of subsequence always strictly increasing), and
• $abs(A_n(l)-δ_k)≤1/l$ (convergence to $δ_k$).

Then $abs(A_n(l)-δ)≤2/l$, so $A_n(l)→δ$ as $l→∞$.

lemma

$x∈𝒞$ is erratic iff both of the following hold:

• $A_n (x)$ has a subsequence converging to $0$ and
• $A_n (x)$ has a subsequence converging to $1$.

proof

If $x$ is erratic, then by definition $A_n (x)$ has subsequences converging to $0$ and $1$ each.

Conversely, suppose $A_n (x)$ has a subsequence converging to $0$ and a subsequence converging to $1$.

Let $δ∈[0,1]$ and $ϵ>0$ be arbitrary.

First, choose $M∈ℕ$ so that $A_M (x)≤ϵ$, and take $M$ large enough so that $2/M≤ϵ$. This is possible since $A_n (x)$ has a subsequence converging to $0$, and in fact note that there are infinitely many such choices of $M$.

Observe that for all $n≥M$,

$$\begin{aligned} \left\lvert Aₙ₊₁ (x) - A_n (x) \right\rvert &= abs(1/(n+1) ∑_(i=0)^n x_i - 1/n ∑_(i=0)^(n-1) x*i) \\ &≤ (abs(1/(n+1)-1/n) ∑*(i=0)^(n-1) x_i) + x_n / (n+1) \\ &= (1 / n(n+1) ∑_(i=0)^(n-1) x_i) + x_n / (n+1) \\ &≤ 1 / n + 1 / (n+1) \\ &≤ 2 / n ≤ 2 / M ≤ ϵ. \end{aligned}$$

Next, choose $N∈ℕ$ so that $N≥M$, and $A_N (x)≥1-ϵ$. This is possible since $A_n (x)$ has a subsequence converging to $1$.

We claim that there exists $k∈{M,M+1,M+2,…,N}$ such that $abs(A_k (x)-δ)≤ϵ$. Let $k∈{M,M+1,M+2,…,N}$ be the maximal index satisfying $A_k (x) ≤ δ.$ By maximality we know that either

• $k=N$, or
• $k<N$, and $A_{k+1} (x)>δ$.

In the first case this means $1-ϵ≤A_N (x)≤δ≤1$, so $0≤δ-A_N (x)≤ϵ$. In the second case, we have $A_k (x) ≤ δ < A_{k+1} (x) ≤ A_k (x) + ϵ.$ This also establishes that $0≤δ-A_k (x)≤ϵ$. In both cases we have $abs(A_k (x)-δ)≤ϵ$.

We just showed that for any $δ∈[0,1]$ and any $ϵ>0$, there exist infinitely many $k$ so that $abs(A_k (x)-δ)≤ϵ$.

To see that $x$ is erratic then, fix $δ$ and let $ϵ$ be any sequence decreasing to $0$ to obtain a subsequence of $A_n (x)$ converging to $δ$. ]

Note also that ”$A_n (x)$ has a subsequence converging to $δ$” is equivalent to the statement, “for every $ϵ>0$ and $N∈ℕ$ there exists an $n≥N$ so that $\lvert Aₙ(x)-δ\rvert≤ϵ$”.

Now we have a countable characterization of erraticity:

$$\operatorname{erratic}(x) = ⋀_{δ∈{0,1}} ⋀_{ϵ∈1/ℕ} ⋀_{N∈ℕ} ⋁_{n≥ℕ} \lvert Aₙ(x)-δ\rvert≤ϵ.$$