Proof Let $Q \subseteq 2^\omega $ be the set $Q=\{ z \colon \forall i\ \exists j \geq i\ z(j)=1\}$ . It is easy to see that Q is $\boldsymbol {\Pi }^0_2$ -complete (see, for example, Section 23.A of [Reference Kechris18]). Let $A \subseteq \omega $ be a set of density $d=s \frac {b}{b-1}\in (0,1]$ . From Lemma 3.3 (using, say, y to be the constant $0$ sequence), let $b_0<b_1<\cdots $ be as in the lemma, let $x\in b^\omega $ be in the measure one set as in the statement of the lemma, and let $x'$ be also as in the statement of the lemma. Let $B_j=[b_{j-1},b_j).$

Define $\psi \colon 2^\omega \to b^\omega $ by:

$$ \begin{align*} \psi(z)(k)= \begin{cases} x'(k) &\text{ if } \exists j\ (k\in B_j \wedge z(j)=1)\\ 0 & \text{ otherwise. } \end{cases} \end{align*} $$

If $z \in Q$ , then there are infinitely many j such that $z(j)=1$ and thus $\psi (z)\restriction B_j=x'\restriction B_j$ . From the properties of $x'$ from Lemma 3.3, for any $\epsilon>0$ there is a tail of these j for which

$$ \begin{align*} \forall E \in \mathcal{E}_j\ \frac{1}{|B_j|}| \{ k \in B_j \colon E(\psi(z)(k-j), \dots, \psi(z)(k-1)) \neq \psi(z)(k) \}| \geq s-\epsilon. \end{align*} $$

Thus, for any $E \in \mathcal {E},$ we have that

$$ \begin{align*} \limsup\limits_j \frac{1}{|B_j|}| \{ k \in B_j \colon E(\psi(z)(k-j), \dots, \psi(z)(k-1)) \neq \psi(z)(k) \}| \geq s. \end{align*} $$

Since $\frac {\sum _{i <j}|B_i|}{|B_j|} \to 0$ with j, it follows that ${\beta }^{+} (\psi (z))\geq s$ , so $\psi (z) \in A_4(s)$ .

If $z \notin Q$ , then $\psi (z)(k)$ is $0$ for all large enough k. This gives that ${\beta }^{+}(\psi (z))=0 <s$ , and so $\psi (z) \notin A_4(s)$ .▪

Proof For $x \in 2^\omega $ , we view x as coding the sequence $x_0,x_1,\dots $ in $2^\omega $ where $x_i(j)=x(\langle i,j \rangle )$ . Here $(i,j)\mapsto \langle i,j\rangle $ is a bijection between $\omega \times \omega $ and $\omega $ . We let $P=\{ x \colon \forall i\ \exists j_0\ \forall j \geq j_0\ x_i(j)=0\}$ . It is well-known that P is $\boldsymbol {\Pi }^0_3$ -complete (see Section 23.A of [Reference Kechris18], specifically the set $P_3$ on p. 179).

We define a partition of $\omega $ into disjoint arithmetical sequences as follows. Let $I_0=\{ n\colon n \equiv 0 \mod 2\}$ , be the set of even integers, and, in general, let $I_n=\{ \ell \colon \ell \equiv 2^n -1 \mod 2^{n+1}\}$ . The $\{ I_n\}$ are pairwise disjoint arithmetic progressions, and $\omega =\bigcup _n I_n$ . Note that $\omega -\bigcup _{k \leq m}I_k= \{ \ell \colon \ell \equiv 2^{m+1}-1 \mod 2^{m+1}\}$ . Each $I_n$ is a periodic set with density $\frac {1}{2^{n+1}}$ .

Fix an infinite set $J\subseteq \omega $ such that $\frac {b-1}{b}\left (1-\sum _{i \in J} \frac {1}{2^{i+1}}\right )=s$ (this corresponds to picking a base-2 expansion for $1-s\frac {b}{b-1}$ that has infinitely many 1s). Let $d_i=\frac {1}{2^{i+1}}$ be the density of $I_i$ . Let $B=\bigcup _{i \notin J}I_k$ and let $d_B=1-\sum _{i \in J}\frac {1}{2^{k+1}}=s\frac {b}{b-1}$ be the density of B.

We will take two fast-growing sequences $\{ a_i\}_{i \in \omega }$ and $\{ b_j\}_{j \in \omega }$ of natural numbers (the $a_i$ will grow faster than the $b_j$ ). We will then set $n_{i,j}=a_ib_j$ . Moreover, let $B_{i,j}=[n_{i,j-1},n_{i,j})$ and $m_{i,j}=|B_{i,j} \cap I_i|$ . Note that $\left |m_{i,j}-\frac {1}{2^{i+1}}(n_{i,j}-n_{i,j-1})\right | \leq 1$ .

We first define the $b_j$ . Fix any sequence $\delta _j$ tending to $0$ . Let $f \colon j\to j$ be given by $f(j)=2^{2j^2}$ . Assume $b_0<b_1<\cdots <b_{j-1}$ have been defined. Let $b_j>b_{j-1}$ be large enough so that:

1. (1) $\frac {\sum _{i<j} b_i}{b_j} <\frac {1}{j}$ .

2. (2) $b_j-b_{j-1}> 2 B(\delta _j, \frac {1}{j^2},f(j)),$

where $B(\delta _j, \frac {1}{j^2},f(j))$ is as in Lemma 3.2. Note that if $a_i \geq 2^i$ , then

(2) $$ \begin{align} |I_i \cap [a_i b_{j-1},a_i b_j)| \geq | I_0 \cap [b_{j-1},b_j)|\geq B(\delta_j, \frac{1}{j^2},f(j)). \end{align} $$

We next define the sequence $a_0<a_1<\cdots $ , which will be sufficiently fast growing with respect to the $\{b_j\}$ . Namely, let $a_i>2^i$ be such that for any $j>i$ we have $|\{ i'\colon a_{i'} \leq a_ib_j\} | \leq j$ . We could, for example, take $a_i=\prod _{i'\leq i}b_{i'}$ . Set $n_{i,j}=a_ib_j$ and let $B_{i,j}=[n_{i,j-1},n_{i,j})$ .

Let $W_{i,j}=\{ (i',j')\colon B_{i',j'}\cap B_{i,j}\neq \emptyset \}$ . Let $P_{i,j}=2^{W_{i,j}}$ , which we call the set of $(i,j)$ patterns. Suppose for the moment $i\in \omega $ and $\vec u=(u_{i'})_{i'\neq i}$ are given where $u_{i'} \in b^{I_{i'}}$ . For every j and for every pattern $p \in P_{i,j}$ , we define the sequence $s_{i,j}(\vec u, p)\in b^{B_{i,j} \setminus I_{i}}$ by $s_{i,j}(\vec u, p)(n)=u_{i'}(n)$ if for the unique $(i',j')$ such that $n \in I_{i'} \cap B_{i', j'}$ we have that $p(i',j')=1$ , and $0$ otherwise. The idea is that the pattern p is predicting whether the values $x_{i'}(j')$ are equal to $0$ or $1$ , and in the case of $1$ we are copying the relevant part of $u_{i'}$ (that is, $u_{i'} \restriction B_{i,j}\cap B_{i',j'} \cap I_{i'}$ ) to $s_{i,j}(\vec u, p)$ and otherwise copying $0$ to $B_{i,j}\cap B_{i',j'} \cap I_{i'}$ . If we are given also $z \in b^{I_i}$ , then we let $s^z_{i,j}(\vec u,p)$ agree with $s_{i,j}(\vec u,p)$ on $B_{i,j}\setminus I_i$ , and agree with z on $B_{i,j}\cap I_i$ .

From Claim 4.3, we have that $|P_{i,j}| \leq 2^{2 j^2}$ for large enough j. Since we used $f(j)=2^{2 j^2}$ in the definition of the $b_j$ , it follows from equation (2) and Lemma 3.3 (where the A of Lemma 3.3 is the set $I_i$ ) that for every $\vec u=(u_{i'})_{i'\neq i}$ we have that for almost all $z \in b^{I_i}$ and all $E\in \mathcal {E}$ (say $E\in \mathcal {E}_k$ ) that for all large enough j that

(3) $$ \begin{align} \forall p \in P_{i,j}\ & \forall t \in b^{[0, n_{i,j-1})}\ \Big| \Big\{ \ell \in I_i\cap B_{i,j} \colon \nonumber\\ & E(t ^{\smallfrown} s^z_{i,j}(\vec u, p)) \restriction [\ell-k,\ell-1])\neq s^z_{i,j}(\vec u,p)(\ell) \Big\} \Big| \geq |I_i\cap B_{i,j}| \left( \frac{b-1}{b} - \delta_j \right). \end{align} $$

From Fubini’s theorem, it follows that there is a measure one set $M_i$ of $u \in b^\omega $ (which we identify with a sequence $(u_i)_{i \in \omega }$ , where $u_i \in b^{I_i}$ ) such that for all $u \in M_i$ equation (3) holds with $z=u_i$ .

Let $M=\bigcap _i M_i$ . Let $u \in M$ , and we again identify u with the sequence $(u_i)_i$ where $u_i \in b^{I_i}$ . We may also assume each $u_i$ is normal. The $u_i$ are now fixed for the remainder of the argument.

We now define the continuous map $\psi \colon 2^\omega \to b^\omega $ , which will be the reduction from P to $A_3(s)$ . Let $x \in 2^\omega $ code the $x_i$ , where $x_i(j)=x(\langle i,j\rangle )$ . We define $\psi (x)$ , which we identify with the sequence $(\psi (x)_i)_{i\in \omega }$ , where $\psi (x)_i \in b^{I_i}$ , by:

$$ \begin{align*} \psi(x)_i(k)=\begin{cases} u_i(k) & \text{ if } k \in I_i\ \text{ and } i \notin J \\ u_i(k) & \text{ if } k\in I_i,\ k \in B_{i,j},\ \text{ and }x_{i^{-}}(j)=1, \text{ where }i\text{ is the}\\ & \quad i^{-}\text{th element of }J\\ 0 & \text{ otherwise. } \end{cases} \end{align*} $$

The map $\psi $ is clearly continuous. We show that $x \in P$ iff ${\beta }^{+}(\psi (x))\leq s$ . Suppose first that $x \in P$ , so $\forall i\ \exists j_0\ \forall j \geq j_0\ x_i(j)=0$ . Then, for all $i \in J$ we have that for large enough $k \in I_i$ that $\psi (x)(k)=0$ . The $E \in \mathcal {E}$ (of width $1$ ), which constantly outputs $0,$ will then correctly compute $\psi (x)(k)$ for all sufficiently large $k \in I_i$ whenever $i \in J$ . For $i \notin J$ , we have that $\lim _{n\to \infty } \frac {1}{n} |\{ k <n \colon (k \in I_i) \wedge E(\psi (x) \restriction [k-1,k-1])\neq \psi (x)(k)\}|= \frac {1}{2^{i+1}}\frac {b-1}{b}$ . From this, it follows that $\lim _{n \to \infty } \frac {1}{n} |\{ k <n \colon E(\psi (x)\restriction [k-1,k-1])\neq \psi (x)(k)\}|= \frac {b-1}{b}\sum _{i \notin J} \frac {1}{2^{i+1}}=s$ . So, ${\beta }^{+}(\psi (x)) \leq s$ and so $\psi (x)\in A_3(s)$ .

Suppose next that $x \notin P$ . Let $i_0$ be least such that there are infinitely many j such that $x_{i_0}(j)=1$ . Let $E\in \mathcal {E}$ , say $E\in \mathcal {E}_k$ . If $i \notin J$ , then for $\ell \in I_i$ we have $\psi (x)_i(\ell )=u_i(\ell )$ . Since $u\in M \subseteq M_i,$ we have from equation (3) that for large enough j that

(4) $$ \begin{align} \Big| \Big\{ \ell \in I_i \cap B_{i,j} \colon E(\psi(x) \restriction [\ell-k,\ell-1])\neq \psi(x)(\ell) \Big\} \Big| \geq |I_i \cap B_{i,j}| \left( \frac{b-1}{b} - \delta_j \right). \end{align} $$

We use here the fact that for each j there is a $p\in P_{i,j}$ such that $s_{i,j}(\vec u,p)= \psi (x)\restriction B_{i,j}\setminus I_i$ . Thus,

$$ \begin{align*} \lim\limits_{n\to \infty} \frac{1}{n} |\{ \ell \in [0,n)\cap I_i \colon E(\psi(x) \restriction [\ell-k,\ell-1])\neq \psi(x)(\ell)\}|\geq \frac{1}{2^{i+1}} \frac{b-1}{b}. \end{align*} $$

Let $i^+_0$ be the $i_0$ th element of J. For large enough j such that $x_i(j)=1$ we likewise have equation (4) for $i=i_0^+$ . Thus, along the subsequence of j with $x_{i}(j)=1$ we have that

$$ \begin{align*} \lim\limits_{n\to \infty} \frac{1}{n} |\{ \ell \in [0,n) \colon E(\psi(x) \restriction [\ell-k,\ell-1])\neq \psi(x)(\ell)\}|\geq (\sum\limits_{i \notin J}\frac{1}{2^{i+1}}+ \frac{1}{2^{i_0^++1}}) \frac{b-1}{b}. \end{align*} $$

Since $(\sum _{i \notin J}\frac {1}{2^{i+1}})\frac {b-1}{b}=s$ we have that $\beta ^+(\psi (x))>s$ , so $\psi (x)\notin A_3(s)$ .

Proof Let $0 \leq s < \frac {b-1}{b}$ . For each $i\in \mathbb {N}$ pick a probability vector $(p_{i,0}, \ldots , p_{i,b-1})$ such that $1 - \max _d p_{i,d} = 1 - p_{i,0} = s+ \frac {1- s-1/b}{i}$ and construct real numbers $u_i$ such that for any k and $b_1,\dots , b_k\in b^k$

$$ \begin{align*}\lim\limits_n \frac{I(u_i,b_1 \cdots b_k,n)}{n} = \prod\limits_{j=1}^k p_{i,b_j}, \end{align*} $$

where $I(u_i, b_1 \dots b_k,n)$ is the number of $j\leq n-k+1$ such that $u_i\restriction [j,j+k-1]=b_1\cdots b_k$ . In fact, almost all $u_i$ with respect to the probability measure $\mu _i$ on $b^\omega $ determined by $(p_{i,0}, \ldots , p_{i,b-1})$ satisfy this condition. Then, $\beta _{\ell }(u_i) = s + \frac {1-s-1/b}{i}$ for every $\ell $ and the constant $0$ block function $E_0$ is the minimizer of $\inf _{E\in \mathcal {E}_\ell } \limsup _N \beta _E(u_i,N)$ . Let $(a_j)$ be a sufficiently quickly growing sequence of integers with $a_1 = 1$ such that for $1 \leq \ell \leq j$ , $1 \leq i \leq j$ , and for all $n \geq \frac {a_j}{1-1/j}$ we have

$$ \begin{align*} &\left | \beta_{E_0}(u_i,n) - \beta_\ell(u_i) \right | = \left | \beta_{\ell}(u_i,n) - \beta_\ell(u_i) \right | < \frac{1}{j} \end{align*} $$

and

$$ \begin{align*} &\frac{a_{j+1}}{a_j}> j^2. \end{align*} $$

Put $B_j = [a_j, a_{j+1})$ .

We view $x \in 2^\omega $ as coding the sequence $x_0, x_1, \ldots $ in $2^\omega $ where $x_i(j) = x(\langle i,j\rangle )$ . Let P be as in Lemma 4.2. Given $x \in 2^\omega $ , define $m(j) = \min \{j, \min \{i \colon x_i(j) = 1 \} \}$ . Thus, if $x \in P$ then $\lim _j m(j)=\infty $ , and if $x \notin P$ then $\liminf _j m(j)$ is finite.

Define $\psi (x)$ by

$$ \begin{align*}\psi(x)_{{}| B_j}(k)= u_{m(j)}(k - a_j). \end{align*} $$

The map $\psi $ is continuous. We show that $\psi $ is a reduction from P to $A_3(s)$ . Suppose $x \in P$ , so $\lim _{j} m(j) = \infty $ . We have

$$ \begin{align*} & \limsup\limits_{N} \frac{1}{N} |\left \{ k \leq N \colon \psi(x)(k) \neq E_0(\psi(x)(k)) \right \} |\\ & = \limsup\limits_N \frac{1}{N} | \left \{ k \leq N \colon \psi(x)(k) \neq 0 \right \} |\\ & = \limsup\limits_j \sup\limits_{N \in B_j} \sum\limits_{k=1}^{j-1} \frac{1}{N} | \left \{ v \leq | B_k| \colon u_{m(k)}(v) \neq 0 \right \}| + \frac{1}{N} | \left \{ 0 \leq v \leq N-a_j \colon u_{m(j)}(v) \neq 0 \right \}|. \end{align*} $$

Now, for $N \geq a_j$ and $k \leq j-2$

$$ \begin{align*} \frac{1}{N} | \{1 \leq v \leq | B_k| \colon u_{m(k)}(v) \neq 0\} | & \leq \frac{a_{k+1} - a_k}{a_j} \leq \frac{a_{j-1}}{a_j} < \frac{1}{(j-1)^2} \end{align*} $$

and

$$ \begin{align*} \frac{1}{N} | \{1 \leq v \leq |B_{j-1}| : u_{m(j-1)}(v) \neq 0\}| & \leq \frac{a_{j}-a_{j-1}}{N} \left ( \beta_\ell(u_{m(j-1)}) + \frac{1}{j-1} \right ) \\ & \leq \frac{a_j}{N} \left ( \beta_\ell(u_{m(j-1)}) + \frac{1}{j-1} \right ). \end{align*} $$

For $a_j \leq N \leq \frac {a_j}{1-1/j} \leq a_{j+1,} $ we have

$$ \begin{align*} \frac{1}{N} | \left \{ 0 \leq v \leq N-a_j : u_{m(j)}(v) \neq 0 \right \}| \leq \frac{N-a_j}{N} \leq \frac{\frac{a_j}{1-1/j} - a_j}{a_j} = \frac{1}{j-1}. \end{align*} $$

On the other hand, for $\frac {a_j}{1-1/j} \leq N \leq a_{j+1}$

$$ \begin{align*} \frac{1}{N} | \left \{ 0\leq v \leq N-a_j : u_{m(j)}(v) \neq 0 \right \}| &= \frac{N - a_j}{N} \beta_\ell(u_{m(j)},N-a_j)\\ &\leq \frac{N-a_j}{N} \left ( \beta_\ell(u_{m(j)}) + \frac{1}{j} \right ). \end{align*} $$

Thus,

$$ \begin{align*} \lim\limits_\ell \beta^+_\ell(\psi(x)) &\leq \lim\limits_\ell \limsup\limits_j \sup \{t \beta_\ell(u_{m(j-1)}) + (1-t) \beta_\ell(u_{m(j)}) : t \in [0,1]\} \\ & \qquad + \frac{j-1}{(j-1)^2} + \frac{2}{j-1} + \frac{1}{j}\\ & = \lim\limits_\ell \left( s + \limsup\limits_j \max\left \{ \frac{1-s-1/b}{m(j-1)}, \frac{1-s-1/b}{m(j)} \right \}\right) = s. \end{align*} $$

Now, suppose $x \notin P$ . Then, $\liminf _n m(n) = M < \infty $ . Fix $\ell $ and note

$$ \begin{align*} &\inf\limits_{E \in \mathcal{E}_\ell} \limsup\limits_{N} \frac{1}{N} |\left \{ k \leq N : \psi(x)(k) \neq E(\psi(x)(k+1), \ldots, \psi(x)(k+\ell)) \right \}|\\ & = \limsup\limits_j \sup\limits_{N \in B_j} \sum\limits_{k=1}^{j-1} \frac{|B_k|}{N} \beta_\ell(u_{m(k)}, | B_k|) + \frac{N-a_j}{N} \beta_\ell(u_{m(j)}, N-a_j) \\ & \geq \limsup\limits_j \frac{a_{j+1}-a_j}{a_{j+1}} \beta_\ell(u_{m(j)}, a_{j+1} - a_j), \end{align*} $$

which implies

$$ \begin{align*}\lim\limits_\ell \beta^+_{\ell}(\psi(x)) \geq s + \frac{1-s-1/b}{M}> s. \end{align*} $$

▪

Proof We reduce the set $P=\{ x \in 2^\omega \colon \forall i\ \exists j_0\ \forall j\geq j_0\ x_i(j)=0\}$ to $A_2(s)$ . Let $J\subseteq \omega $ be such that $\frac {b-1}{b}\sum _{i\in J} d_i=s$ , where we recall $d_i=\frac {1}{2^{i+1}}$ is the density of $I_i$ . We let the sequences $\{ a_i\}$ , $\{ b_j\}$ be as in Lemma 4.2, except that we impose an additional requirement on $b_j$ :

1. (3) $b_j> (j+1)^2 2^{j+1} B(\delta _{j+1}, \frac {1}{(j+1)^2}, f(j+1)),$

where we recall $f(j)=2^{j^2}$ , and B is as in Lemma 3.2. As in Lemma 4.2, we then let $n_{i,j}=a_i b_j$ , $B_{i,j}=[n_{i,j-1},n_{i,j})$ . We use also the notion of pattern defined in the proof of Lemma 4.2, and specifically the sets $W_{i,j}$ and $P_{i,j}$ .

As in Lemma 4.2, for each $i \in \omega $ there is a $\mu $ measure one set $M_i$ of $u \in b^\omega $ such that for cofinitely many j, all $E\in \mathcal {E}_k$ , where $k \leq j$ , all $t \in b^{[0,n_{j-1})}$ , and all patterns $p \in P_{i,j}$ , if we define $s(i,j,p,u)\in b^{B_{i,j}}$ by

$$ \begin{align*} s(i,j,p,u)(k)= \begin{cases} u(k) & \text{ if } \exists i', j' \in W_{i,j}\ (P(i',j')=1 \wedge k \in (I_{i'}\cap B_{i,j}\cap B_{i',j'})) \\ 0 & \text{ otherwise,} \end{cases} \end{align*} $$

then if $s'=t{\kern-1pt}^{\smallfrown } s(i,j,p,u),$ we have that for all $c \in [n_{i,j-1},n_{i,j})$ with $|I_i \cap [n_{i,j-1},c) \geq B(\delta _j,\frac {1}{j^2}, f(j))$ that

(5) $$ \begin{align} | \{ \ell \in [n_{i,j-1},c) \cap I_{i}& \colon E(s'(\ell-k),\dots,s'(\ell-1))\neq s'(\ell) \}| \nonumber\\ & \geq |I_i\cap [n_{i,j-1},c) | \left( \frac{b-1}{b} -\delta_j\right). \end{align} $$

We fix $u \in b^\omega $ in all of the measure one sets $M_i$ . We define $\psi \colon 2^\omega \to b^\omega $ by:

$$ \begin{align*} \psi(x)(k)=\begin{cases} u(k) & \text{ if } \exists i,j\ (i \in J \wedge j>0 \wedge k \in (B_{i,j} \cap I_i) \wedge x_{i^{-}}(j)=0) \text{ where }\\ & \quad i\text{ is the }i^{-}\text{th element of }J\\ 0 & \text{ otherwise. } \end{cases} \end{align*} $$

We show $\psi $ is a reduction from P to $A_2(s)$ . We again identify $u \in b^\omega $ with a sequence $(u_i)_{i\in \omega }$ where $u_i \in b^{I_i}$ and likewise identify $\psi (x)\in b^\omega $ with a sequence $(\psi (x)_i)_{i \in \omega }$ .

If $x \notin P$ , then there is an $i_0$ such that for infinitely many j we have $x_{i_0}(j)=1$ . Let $i_0^+$ be the $i_0$ th element of J. We may assume that u is such that for every i that $\lim _{n \to \infty } \frac {1}{n} |\{ \ell \in I_i\cap [0,n) \colon u(\ell )=0 \} | =\frac {d_i}{b}$ and $\lim _{n \to \infty } \frac {1}{n} |\{ \ell \in [0,n) \colon u(\ell )=0 \} | =\frac {1}{b}$ . Note that since $\psi (x)_i$ is obtained from $u_i,$ by changing certain digits to a $0$ , the constant $0$ block function $E_0$ will have no more errors along $I_i$ for $\psi (x)_i$ than for $u_i$ . It follows that

$$ \begin{align*} \lim\limits_{n} \frac{1}{n} |\{ \ell \in [0,n) \setminus I_{i^+_0} \colon E_0([\ell-1,\ell-1]) \neq \psi(x)(\ell) \} \leq \left(\frac{b-1}{b} \right) \sum\limits_{\substack{i\in J\\ i\neq i^+_0}} d_i. \end{align*} $$

On the other hand, for any j such that $x_{i_0}(j)=1,$ we have that $E_0$ has no errors in $B_{i^+_0,j}\cap I_{i^+_0}$ , and so

$$ \begin{align*} \liminf\limits_{n} \frac{1}{n} |\{ \ell \in [0,n) \cap I_{i^+_0} \colon E_0([\ell-1,\ell-1]) \neq \psi(x)(\ell) \}| =0. \end{align*} $$

From these two facts it follows that

$$ \begin{align*} {\beta}^{-}(\psi(x)) \leq \sum\limits_{\substack{i\neq i^+_0\\ i \in J}}d_i \frac{b-1}{b}< \sum\limits_{i\in J} d_i\frac{b-1}{b}=s. \end{align*} $$

Thus, $\psi (x) \notin A_2(s)$ .

Suppose next that $x \in P$ . Let $E\in \mathcal {E}$ , say $E\in \mathcal {E}_k$ . Let $i \in J$ . Then, from equation (5) and the fact that $x_i(j)=0$ for all large enough j, and any $c\in [n_{i,j-1},n_j)$ with $|I_i \cap [n_{i,j-1},c)| \geq B(\delta _j,\frac {1}{j^2},f(j))$ that

(6) $$ \begin{align} | \{ \ell \in I_i \cap [n_{i,j-1},c) \colon E(\psi(x)\restriction [\ell-k,\ell-1]) &\neq \psi(x)(\ell) \}|\nonumber\\& \geq |I_i \cap [n_{i,j-1},c)| \left( \frac{b-1}{b}-\delta_{j} \right) . \end{align} $$

In particular, for large enough $j,$ we have

$$ \begin{align*} | \{ \ell \in I_i \cap [n_{i,j-2},n_{j-1}) & \colon E(\psi(x)\restriction [\ell-k,\ell-1]) \neq \psi(x)(\ell) \} \\ & \geq |I_i \cap [n_{i,j-2},n_{i,j-1})|\left( \frac{b-1}{b}-\delta_{j-1} \right) . \end{align*} $$

Suppose now that j is sufficiently large (in particular $i<j$ ) and $c \in [n_{i,j-1},n_{i,j})$ . Let

$$ \begin{align*} e=| \{ \ell \in I_i \cap [n_{i,j-2},n_{i,j-1}) \colon E(\psi(x)\restriction [\ell-k,\ell-1]) \neq \psi(x)(\ell) \}| \end{align*} $$

and

$$ \begin{align*} e_c=| \{ \ell \in I_i \cap [n_{i,j-1},c) \colon E(\psi(x)\restriction [\ell-k,\ell-1]) \neq \psi(x)(\ell) \}|. \end{align*} $$

If $c < n_{i,j-1}+2^j B(\delta _j,\frac {1}{j^2},\delta _j)$ , then from Assumption 3 for $b_{j-1}$ we have that

$$ \begin{align*} \frac{c-n_{i,j-1}}{e}\leq \frac{2^j B(\delta_j,\frac{1}{j^2},\delta_j)} {\frac{1}{2^i}(n_{i,j-1}-n_{i,j-2})\frac{b-1}{2b}} \leq 2^{i+2}\frac{b}{b-1} \frac{2^j B(\delta_j,\frac{1}{j^2},\delta_j)}{b_{j-1}} \leq 2^{i+2}\frac{b}{b-1} \frac{1}{j^2}, \end{align*} $$

which tends to $0$ with j. It follows that

(7) $$ \begin{align} | \{ \ell \in I_i \cap [0,c) & \colon E(\psi(x)\restriction [\ell-k,\ell-1]) \neq \psi(x)(\ell) \}| \nonumber\\ & \geq \frac{c}{2^i} \left( \frac{b-1}{b}-\delta_{j}- 2^{i+2}\frac{b}{b-1} \frac{1}{j^2}\right) . \end{align} $$

Note here that we can ignore the contribution from $\ell <n_{j-2}$ by the growth assumption on the $b_j$ .

Suppose next that $c \geq n_{i,j-1}+2^j B(\delta _j,\frac {1}{j^2},\delta _j)$ . Then,

$$ \begin{align*} |I_i \cap [n_{i,j-1},c)|\geq \frac{1}{2^i} 2^j B(\delta_j,\frac{1}{j^2},\delta_j) \geq B(\delta_j,\frac{1}{j^2},\delta_j). \end{align*} $$

Thus, equation (6) applies. So, $e_c \geq |I_i \cap [n_{i,j-1},c)| \left ( \frac {b-1}{b}-\delta _{j} \right ) $ . Since we also have $e \geq |I_i \cap [n_{i,j-2},n_{i,j-1})|\left ( \frac {b-1}{b}-\delta _{j-1} \right )$ , we have that

(8) $$ \begin{align} | \{ \ell \in I_i\cap [n_{i,j-2},c) & \colon E(\psi(x)\restriction [\ell-k,\ell-1]) \neq \psi(x)(\ell) \}| \nonumber\\ & \geq \frac{c-n_{i,j-2}}{2^i} \left( \frac{b-1}{b} -\max\{ \delta_{j-1},\delta_j\} \right). \end{align} $$

In either case, from equations (7) and (8), we have that

$$ \begin{align*} | \{ \ell \in I_i\cap [0,c) \colon E(\psi(x)\restriction [\ell-k,\ell-1]) \neq \psi(x)(\ell) \}| \geq \frac{1}{2^i} \left( \frac{b-1}{b} -\eta_j \right). \end{align*} $$

for large enough c, where $\eta _j$ tends to $0$ .

This gives that ${\beta }^{-}(\psi (x)) \geq (\sum _{i \in J} d_i) (\frac {b-1}{b})=s$ , and so $\psi (x) \in A_2(s)$ .▪

Proof Fix $s \in [0,\frac {b-1}{b})$ . Let $R=\{ x \in (2^\omega )^3 \colon \forall i\ \exists j_0\ \forall j \geq j_0\ \exists k\ x(i,j,k)=0\}$ . R is a $\boldsymbol {\Pi }^0_4$ -complete set (see Exercises 23.2 and 23.3 on p. 180 of [Reference Kechris18]). Therefore, it suffices to reduce R to $A_1(s)$ . Let $J\subseteq \omega $ be such that $s=\frac {b-1}{b} \left (1-\sum _{i \in J}\frac {1}{2^{i+1}}\right )$ . Let the $I_i$ partition $\omega $ as before, so $d(I_i)=\frac {1}{2^{i+1}}$ .

We will define a fast-growing sequence $b_0<b_1<\cdots $ , and we will also let $B_n=[b_n,b_{n+1})$ . Each n codes a triple $n=\langle i_n,j_n,t_n\rangle $ , where $i_n,j_n,t_n\leq n$ . We will also define a certain sufficiently fast-growing function $g \colon \omega \to \omega $ (this will be the map $j \mapsto p(j,\frac {1}{j})$ of Claim 4.7). Also as in the proof of Lemma 4.2, we will fix a particular $u \in 2^\omega $ from a certain $\mu $ measure one set, which will guide the construction of the reduction map $\psi $ . The construction will be similar to that of Lemma 4.2, the main difference being that, at some points of the construction, instead of copying $0$ s to parts of the block $B_n$ we will copy a portion of u repeated with period $g(j_n)$ . In the following claims, the set A is where we intend to copy u, and the set B is where we intend to copy the periodic truncation of u (this is defined right before Claim 4.7). The idea is that if $E\in \mathcal {E}_j$ and if p is the period of the sequence copied to B, then if p is large compared to $j,$ the noise with respect to E will increase as if we copied random bits to B, while if p is small compared to j, the noise will not increase (at least this will be the behavior for almost all $u\in b^\omega $ ). This will give us the freedom we need to construct the reduction map. The following claims make these statements precise.

Our first claim, Claim 4.6, says that copying a periodic sequence to the B part will not increase the upper noise $\beta ^+$ (for almost all u).

Proof Let u be normal in base b. Let $\epsilon>0$ . Consider sequences $s \in b^{np}$ for some integer n. For large enough n, the probability that a sequence $s' \in b^{A\cap np}$ will have the property that $A'=\{ i \in A \cap np\colon s'(i)=s'(i-p)\}$ has size at least $\frac {d_Apn}{b}(1-\frac {\epsilon }{3})$ is at least $1-\frac {\epsilon }{3}$ . This is because, as in the proof of Lemma 3.1, this set is in bijection with the set of $s' \in b^{A\cap np}$ such that $\{ i \in A \cap np\colon s'(i)=0\}$ has size at least $\frac {d_Apn}{b}(1-\frac {\epsilon }{3})$ . We call such an $s'$ good. Since u is normal in base $b^{d_Apn}$ , it follows that for large enough N that the number of $k \leq N$ such that $u \restriction (A\cap [kpn,(k+1)pn) )$ is good is at least $N(1-\frac {\epsilon }{2})$ . For such N we have that

$$ \begin{align*} | \{ i \in A\cap p n N & \colon u(i)=u(i-p)\}| \geq N\left(1-\frac{\epsilon}{2}\right)\left(\frac{d_Apn}{b}\right)\left(1-\frac{\epsilon}{3}\right) \\ & \geq \left(\frac{d_ApnN}{b}\right) (1-\epsilon). \end{align*} $$

Let $E\in \mathcal {E}_{p}$ be the block function such that $E(s)=s(0)$ , so E is simply guessing that $x(n)$ will be $x(n-p)$ . It follows that if $\bar {u} \in b^\omega $ is normal, then for large enough N we have that

$$ \begin{align*} | \{ i \leq pnN \colon \bar{u}(i) = E(\bar{u}(i-p),\dots, \bar{u}(i-1)) \} | & \geq \left(\frac{d_ApnN}{b}\right) (1-\epsilon) + d_B pn N \\ & =pnN \left(\frac{d_A}{b}(1-\epsilon)+d_B\right). \end{align*} $$

Thus, ${\beta }^{+}_E(\bar {u})\leq 1-\left (\frac {d_A}{b}(1-\epsilon )+d_B\right )= d_A\frac {b-1}{b}+d_C +\epsilon \frac {d_A}{b}$ . Since $\epsilon $ was arbitrary, ${\beta }^{+}_E(\bar {u})\leq d_A \frac {b-1}{b} +d_C$ . ▪

For $u \in b^\omega $ and $k,p\in \omega $ , we define $\bar {u}(k,p)$ by $\bar {u}(k,p)(m)= u(m)$ for $m <k$ , and for $m \geq k$ we set $\bar {u}(k,p)(m)=u(m-k \mod p)$ . Thus, after the first k digits of u, we repeat the digits of u periodically with period p. In particular, $\bar {u}(0,p)$ is the periodic truncation of u to period p.

The next claim states that when the period p is sufficiently large compared to the width $j_0$ of the block function E (that is, $E\in E_{j_0}$ ), then using the periodic truncation with period p on B will not have much effect as compared to copying u there.

Claim 4.7 Let $j_0\in \omega $ , $\epsilon ,\epsilon '> 0$ . Then, there is a $p=p(j_0,\epsilon ) \in \omega ,$ which is a power of $2$ and an $\eta =\eta (p,\epsilon ')$ such that if $A, B, C \subseteq \omega $ are disjoint and of period p with densities $d_A$ , $d_B$ , $d_C,$ respectively, and with $\omega =A\cup B \cup C$ , then for any $n=p\ell \geq \eta $ , we have that $\frac {|H|}{b^{(A\cup B)\cap [0,n]}} \geq 1-\epsilon '$ , where H is the set of $u \in b^{(A\cup b)\cap [0,n)}$ such that for any $u_c \in b^{C\cap [0, n]}$ if $u' \in b^n$ is defined by

$$ \begin{align*} u'(i) =\begin{cases} u(i) & \text{ if } i \in A \\ \bar{u}(0,p) & \text{ if } i \in B \\ u_c(i) & \text{ if } i \in C \end{cases} \end{align*} $$

then for any $E\in \mathcal {E}_{j_0}$ , we have

(*) $$ \begin{align*} \forall k \in [\eta,n]\ \, \Big [ \frac{1}{k} |\{ i \leq k & \colon E(u'(i-j_0),\dots,u'(i-1)) \neq u'(i)\}| \\ & \geq (d_A+d_B)\frac{b-1}{b}(1 -\epsilon)-j_0 d_C \Big ]. \end{align*} $$

Furthermore, this holds for all $p' \geq p$ .

Proof Fix $j_0$ , $E\in \mathcal {E}_{j_0}$ , $\epsilon>0$ . It suffices to show that for large enough $p \in \omega $ , and $\omega =A \cup B \cup C$ , a disjoint union with $A,B,C$ having period p, and $u_c\in b^C$ , that the probability a $u \in b^{(A\cup B)\cap [0,n]}$ satisfies $(*)$ tends to $1$ with n.

Given $u \in b^{(A\cup B)\cap [0,n]}$ , let $u''\in b^{[0,n]}$ be defined as $u'$ above except we put $u''(i)=0$ for $i\in C \cap [0,n]$ . The counting argument of Lemma 3.1 shows that as p grows, with probability approaching $1$ in choosing $u \restriction ((A\cup B) \cap [0,p])$ we have that

(**) $$ \begin{align*} \frac{1}{p} | \{ i \leq p \colon E(u''(i-j_0),\dots,u''(i-1)) \neq u''(i)\} | \geq (d_A+d_B)\frac{b-1}{b}\left(1-\frac{\epsilon}{2}\right). \end{align*} $$

From the finite version of Fubini, it follows that for any $\delta>0$ that for large enough $p;$ that with probability at least $1-\delta $ in choosing $u_b=u\restriction (B\cap [0,p]);$ that for probability of at least $1-\delta $ in choosing $u_a=u\restriction (A\cap [0,p]),$ we have that if $u''$ is defined from $u_a$ and $u_b$ , then $(**)$ holds.

Choose $u_b$ in this set of measure at least $1-\delta $ . Let G be the set of $u_a=u\restriction (A\cap [0,p])$ such that if $u''=u_a \cup u_b\cup u_c$ (with $u_c=0$ ) then u satisfies $(**)$ . Therefore, G has measure at least $1-\delta $ . From the law of large numbers, we have the probability that a $u \in b^\omega $ has the property that for all $k\geq 1$

$$ \begin{align*} | \{k' \leq k \colon u \restriction (A\cap [k'p ,(k'+1)p)) \in G\} | \geq k\left(1-\frac{\epsilon}{2}\right) \end{align*} $$

is at least $1-h(\delta )$ , where $h(\delta )\to 0$ as $\delta \to 0$ . We choose $\delta < \frac {\epsilon }{2}$ small enough so that $h(\delta )< \frac {\epsilon }{2}$ . It follows that for all $n=\ell p \geq p$ that with probability at least $1-\delta $ , $u_b \in b^{B\cap [0,p)}$ has the property that with probability at least $1-h(\delta )$ , $u_a=u\restriction (A\cap [0,n)$ has the property that if $u''\in b^{[0,n)}$ is formed from $u_a$ , $u_b$ , $u_c=0$ as above, then for all $k'\leq \ell $

(9) $$ \begin{align} | \{ i \leq k'p\colon & E(u''(i-j_0),\dots,u''(i-1)) \neq u''(i)\}| \nonumber\\ & \geq k'p \left(1-\frac{\epsilon}{2}\right)(d_A+d_B)\left( \frac{b-1}{b}\right) \left( 1-\frac{\epsilon}{2}\right) \nonumber\\ & \geq k'p (d_A+d_B)\left( \frac{b-1}{b}\right) (1-\epsilon). \end{align} $$

Since $\delta , h(\delta )<\frac {\epsilon }{2}$ it follows that for any $n=\ell p \geq p$ that with probability at least $1-\epsilon $ , $u \in [0,n)$ has the property that if $u''$ is obtained from u and $u_c$ as above, then for all $k'\leq \ell $ we have that equation (9) holds. If we set $\eta (p,\epsilon )=\frac {p}{\epsilon }$ , then we get the inequality of equation (9) where we replace $i\leq k'p$ with $i\leq k$ , for any $k \in [\eta ,n]$ (and replacing $\epsilon $ with $2\epsilon $ ).

Consider then $u' \in b^{[0,n)}$ , which is defined as $u''$ except we use the given $u_c$ instead of the $0$ function. We have that $E(u''(i-j_0),\dots ,u''(i-1))$ and $E(u'(i-j_0),\dots ,u'(i-1))$ can only disagree if $C\cap [i-j_0,i) \neq \emptyset $ . Thus, there can be at most $d_C n j_0$ many $i \in [0,n)$ where such a disagreement occurs. The inequality of the claim then follows. ▪

The next claim handles the general case where we do not necessarily have that the width of E is small compared to the period p.

Claim 4.8 For every $m, \epsilon , \epsilon '$ there is an $\eta =\eta (m,\epsilon ,\epsilon ')$ such that for any $i_0, j_0, m_0\leq m$ , and any $1\leq p \leq m$ , for all large enough n we have that if $ A=\bigcup _{\substack {i \notin J\\ i \leq m_0}}I_i \cup \bigcup _{\substack {i> i_0\\ i \leq m_0}} I_i$ , $ B=\bigcup _{\substack {i\leq i_0\\ i \in J}}I_i$ , and $C=\omega \setminus (A\cup B)$ , then $\frac {|H|}{b^n} \geq (1-\epsilon ')$ , where H is the set of $u \in b^n$ such that if

$$ \begin{align*} u'(i) =\begin{cases} u(i) & \text{ if } i \in A\cup C \\ \bar{u}(0,p) & \text{ if } i \in B \end{cases} \end{align*} $$

then for any $E\in \mathcal {E}_{j_0}$ we have

$$ \begin{align*} \forall k \in [\eta,n]\ \, \Big [ \frac{1}{k} |\{ i \leq k & \colon E(u'(i-j_0),\dots,u'(i-1)) \neq u'(i)\}| \\ & \geq d_A\left(\frac{b-1}{b}\right)(1 -\epsilon) \Big ]. \end{align*} $$

Putting Claims 4.7 and 4.8 together gives the following claim. Let $b_0<b_1<\cdots <b_n <\cdots $ be a sufficiently fast-growing sequence of powers of $2$ (exactly how fast the sequence needs to grow will be specified below).

Claim 4.9 For almost all $u \in b^\omega ,$ we have the following. For any $j_0$ and $E\in \mathcal {E}_{j_0}$ , for all large enough n we have that if $[b_n,b_{n+1})=A\cup B$ , a disjoint union of sets of period $\leq 2^n$ , where $ A=[b_n, b_{n+1}) \cap (\bigcup _{i \notin J} I_i \cup \bigcup _{i> i_0} I_i)$ and $ B=[b_n\cap b_{n+1}) \cap (\bigcup _{\substack {i\leq i_0\\ i \in J}}I_i)$ for some $i_0\leq n$ , and if $j \leq n$ and $p=p(j,\frac {1}{j})$ , $\eta \geq \eta (p,\frac {1}{n^4})$ are as in Claim 4.7, and $\eta \geq \eta (n,\frac {1}{j},\frac {1}{n^4})$ as in Claim 4.8, then if $u'$ is defined as in Claim 4.8, then we have:

(1) (large j case) If $j \geq j_0$ then

$$ \begin{align*} \forall k \in [b_n+\eta,b_{n+1}]\ \, \Big [ \frac{1}{k-b_n} \, | \{ i \in [b_n,k) & \colon E(u'(i-j_0),\dots,u'(i-1)) \neq u'(i)\} | \\ & \geq (d_A+d_B)\left(\frac{b-1}{b}\right)\left(1-\frac{1}{j}\right) - \frac{j}{2^n} \Big ]. \end{align*} $$

(2) (general case)

$$ \begin{align*} \forall k \in [b_n+\eta,b_{n+1}] \ \, \Big [ \frac{1}{k-b_n} |\{ i \in [b_n,k) & \colon E(u'(i-j_0),\dots,u'(i-1)) \neq u'(i)\} | \\ & \geq d_A\left(\frac{b-1}{b}\right)\left(1-\frac{1}{n}\right) \Big ]. \end{align*} $$

where $d_A$ , $d_B$ are the densities of A, B in $[b_n,b_{n+1})$ .

We now fix $u \in 2^\omega $ in the measure one set described in Claim 4.9, and in the measure one sets of Claim 4.6 for all possible choices of $A,B,C$ (there are countably many choices for these sets). We also fix the fast-growing sequence $b_0<b_1<\cdots <b_n<b_{n+1}<\cdots $ . As we said in Claim 4.9, we take $b_{n+1}>b_n+\eta _n$ , where $\eta _n$ is the maximum of $\eta (p,\frac {1}{n^4})$ , where $p=p(n,\frac {1}{n})$ , from Claim 4.7 and $\eta (n, \frac {1}{n},\frac {1}{n^4})$ from Claim 4.8.

Claim 4.9 then gives the following property of u and the $b_n$ .

$(\dagger )$ : For any $j_0$ , $E\in \mathcal {E}_{j_0}$ , for all large enough n if $[b_n,b_{n+1})=A\cup B$ where $A=[b_n,b_{n+1}) \cap (\bigcup _{i \notin J} I_i \bigcup _{\substack {i\in J\\ i>i_0}} I_i)$ , $B=[b_n,b_{n+1})\cap (\bigcup _{\substack {i \in J\\ i \leq i_0}} I_i)$ where $i_0 \leq n$ , then for any $j \leq n$ if $p=p(j,\frac {1}{j})$ (as in Claim 4.7) and $u'$ is defined from u and p as in Claim 4.8, then if we set

$$ \begin{align*} d=\frac{1}{k-b_n} |\{ i \in [b_n,k) \colon E(u'(i-j_0),\dots,u'(i-1)) \neq u'(i)\} | \end{align*} $$

then for $b_n+\eta _n\leq k \leq b_{n+1,}$ we have:

1. (1) If $j \geq j_0$ then $d\geq (d_A+d_B)\left (\frac {b-1}{b}\right )\left (1-\frac {1}{j}\right )- \frac {j}{2^n}$ .

2. (2) $d\geq d_A\left (\frac {b-1}{b}\right )\left (1-\frac {1}{n}\right )$ .

We now return to the proof of Lemma 4.5.

Given $x \in 2^{\omega ^3}$ , we define a function $h(x)\colon \omega ^3 \to \omega ^3$ as follows. We let $h(x)(i,j,0)$ be $(1,j+1,0)$ if $x(i',j,0)=0$ for all $i' \leq i$ . Otherwise, set $h(x)(i,j,0)=(0,j,1)$ . In general, we define (in the following, $(a,b,c)_i$ denotes the ith element of the tuple, so $(a,b,c)_0=a$ , etc.)

$$ \begin{align*} h(x)(i,j,t)= \begin{cases} (1, (h(x)(i,j,t-1)))_1+1,0) & \text{ if } \\ {} \qquad {} \forall i'\leq i\ \exists t' \leq t\ x(i',(h(x)(i,j,t-1))_1,t')=0 & \\ (0, (h(x)(i,j,t-1))_1,(h(x)(i,j,t-1))_2+1) & \text{ otherwise.} \end{cases} \end{align*} $$

The function h does the following. The input i sets the “width” of the search, that is, it will search over $(x)_{i'}$ for $i' \leq i$ . The input j sets the initial start of the search, in that the search will begin by considering the values $x(i',j,0)$ , for $i'\leq i$ . The search checks to see if all of these are equal to $0$ . If so, it will output $(h(x)(i,j,0))_0=1$ , denoting a successful search, and then replace j with $j+1$ and begin a new search at the values $x(i,j+1,0)$ . The output $(h(x)(i,j,0))_1$ records the new value $j+1$ , and the output $(h(x)(i,j,0))_2$ records the new “height” of the search, which will, in this case, is set back to $0$ . If not all the values $x(i',j,0)$ are $0$ , then the j value remains the same and we increment the height of the search. This means we will search the values of $x(i',j,k')$ where $i'\leq i$ , j is the current value of $(h(x)(i,j,t))_1$ , and $k'\leq (h(x)(i,j,t))_2$ , which is the current height. For a given j, we keep incrementing the height k and see if $\forall i'\leq i\ \exists k'\leq k\ x(i',j,k')=0$ . If so, the search is successful, and we then increment j to $j+1$ and reset the height k to $0$ . Otherwise, we continue to increment the height k and continue the search.

The search is attempting to verify, step by step, that

$$ \begin{align*} \forall i'\leq i\ \forall j' \geq j\ \exists k'\ x(i',j',k')=0. \end{align*} $$

If this condition holds for some $i,j$ , then $(h(x)(i,j,t))_1$ will tend to $\infty $ with t. If this condition fails for $i,j$ , then for $j'$ the least integer $\geq j$ such that $\neg \forall i' \leq i\ \exists k\ x(i',j',k)=0$ we have that $(h(x)(i,j,t))_1$ will be equal to $j'$ for all large enough t (the search will “get stuck” at $j'$ ).

Recall that $\{ b_n\}$ is a sufficiently fast-growing sequence, so that u and the $\{ b_n\}$ satisfy Claims 4.6 and 4.9. As before, we let $B_n=[b_n,b_{n+1})$ . We view n as coding a triple of integers, which we write as $(i_n,j_n,t_n)$ , and we assume this coding is reasonable in that $i_n,j_n,t_n \leq n$ for all n. We define the map $\psi \colon 2^{\omega ^3} \to 2^\omega $ as follows. Let $x \in 2^{\omega ^3}$ . Recall $I_i$ are the pairwise disjoint arithmetical sequences of Lemma 4.2, so $I_i$ has density $\frac {1}{2^{i+1}}$ . Moreover, $J \subseteq \omega $ is such that $\frac {b-1}{b}(1-\sum _{i \in J} \frac {1}{2^{i+1}})=s$ . For $i \notin J$ , we will just copy u to $I_i$ . It remains to specify $\psi (x)(m)$ for $m \in I_i$ where $i\in J$ .

We show that $\psi $ is a reduction from the $\boldsymbol {\Pi }^0_4$ set R to the set

$$ \begin{align*} A_1(s)=\{ z \in b^\omega \colon {\beta}^{-}(z) \leq s\}. \end{align*} $$

First assume that $x \in R$ . Fix $\epsilon>0$ . Let $i_0$ be large enough so that

$$ \begin{align*} \frac{b-1}{b} (\sum\limits_{\substack{i \notin J\\ i\leq i_0}} d_n)+ \sum\limits_{i>i_0}d_n <s+\frac{\epsilon}{2}, \end{align*} $$

where $d_i=\frac {1}{2^{i+1}}$ is the density of $I_i$ . Let $j_0$ be large enough so that $\forall i\leq i_0\ \forall j \geq j_0\ \exists k\ x(i,j,k)=0$ . We can do this as $x \in R$ . Let $S \subseteq \omega $ be given by

$$ \begin{align*} n \in S \Leftrightarrow (i_n=i_0 \wedge j_n=j_0) \wedge ( (h(x)(i_n,j_n,t_n))_0=1), \end{align*} $$

that is, the $(i_n,j_n)$ search at step $t_n$ is successful, and $i_n=i_0$ , $j_n=j_0$ . From the definition of $j_0$ and the properties of $h(x),$ we have that S is infinite (that is, there are infinitely many t such that $(h(x)(i_0,j_0,t))_0=1$ ). For any $n \in S$ , $i \leq i_0$ in J, and $m \in B_n \cap I_i$ , we have that $\psi (x)(m)=\bar {u}(b_n, p(j_0, \frac {1}{j_0}))$ . It follows from Claim 4.6, and the fact that the $b_n$ grow sufficiently fast, that there is an $E\in \mathcal {E}$ (with say $E\in \mathcal {E}_r$ ) such that for all large enough $n \in S$ we have that

$$ \begin{align*} & \frac{1}{|B_n|} |\{ m \in B_n \colon E(\psi(x)(m-r),\dots,\psi(x)(m-1))\neq \psi(x)(m) \} | \\ & \qquad\leq \frac{b-1}{b}(1-\sum\limits_{\substack{i\in J\\ i \leq i_0}} d_n)+ \frac{\epsilon}{2} <s+\epsilon. \end{align*} $$

Since $\epsilon>0$ was arbitrary, we have that ${\beta }^{-}(\psi (x)) \leq s$ , that is, $\psi (x)\in A_1$ .

Assume next that $x \notin R$ . Let $i^*$ be least so that $\forall j\ \exists j' \geq j\ \forall k\ x(i^*,j',k)=1$ . So, for any j, $(h(x)(i^*,j,t))_1$ has a limiting value $j' \geq j$ as t goes to infinity (i.e., the width $i^*$ search starting at j will always gets stuck). Note that if $i>i^*$ , then $(h(x)(i,j,t))_1$ will reach its limiting value at or before when $(h(x)(i^*,j,t))_1$ does, that is, the $h(x)(i,j,t)$ search will get stuck at or before when $h(x)(i^*,j,t)$ gets stuck. So, for all j we have that for all sufficiently large n with $i_n \geq i^*$ and $j_n=j$ , that $(h(x)(i_n,j_n,t_n))_0=0$ (unsuccessful search at step $t_n$ ).

Consider $\psi (x)\restriction I_i$ where $i\geq i^*$ . Therefore, for each $j,$ we have that for all large enough n with $j_n=j$ that either $i_n < i$ , in which case $\psi (x)\restriction (B_n \cap I_i)= u\restriction (B_n \cap I_{i})$ , or else $i_n \geq i$ , in which case (since $(h(i_n,j,t_n))_0=0$ ) we also have that $\psi (x)\restriction (B_n \cap I_{i})=u\restriction (B_n \cap I_{i})$ . Thus, for any j we have that for large enough n that $\psi (x)\restriction (B_n \cap I_{i})$ is either of the form $u\restriction (B_n \cap I_{i})$ or else of the form $\bar {u}(b_n,p)$ where $p>j$ . That is, the periods p used in truncating u in the block $B_n$ go to infinity with n.

It follows from $(\dagger )$ (where the $i_0$ there is the current $i_n$ ) that for any $\epsilon>0$ and any $E\in \mathcal {E}$ (with, say $E\in \mathcal {E}_{j^*}$ ) that for all large enough n that in either case, $i_n <i^*$ or $i_n \geq i^*$ (in which case $j_n \geq j^*$ for large enough n), we have that for all k with $b_n+\eta _n \leq k \leq b_{n+1}$ that if

$$ \begin{align*} d=\frac{1}{k-b_n} |\{ m \in [b_n,k) \colon E(\psi(x)(m-j^*),\dots,\psi(x)(m-1)) \neq \psi(x)(m)\} | \end{align*} $$

then

$$ \begin{align*} d & \geq \left( \frac{b-1}{b} \right) \min \left\{ \left(1-\frac{1}{j}-\frac{j}{2^n}\right), \left(1-\frac{1}{n}\right)\left(\sum\limits_{i\notin J} \frac{1}{2^{i+1}} +\sum\limits_{\substack{i \in J\\ i>i^*}} \frac{1}{2^{i+1}}\right) \right\} \end{align*} $$

for any j and all large enough n. For any $\epsilon>0,$ we have for all large enough n that

$$ \begin{align*}d \geq \left( \frac{b-1}{b}\right) \left(\sum\limits_{i\notin J} \frac{1}{2^{i+1}} +\sum\limits_{\substack{i \in J\\ i>i^*}} \frac{1}{2^{i+1}}\right)-\epsilon \geq (s-\epsilon)+ \left(\frac{b-1}{b}\right)\sum\limits_{\substack{i \in J\\ i>i^*}} \frac{1}{2^{i+1}}.\end{align*} $$

We may assume also that the $b_n$ grows sufficiently fast so that $\frac {\sum _{m<n} b_m}{b_n} \to 0$ as $n \to \infty $ . Recall that we also have that $\frac {\eta _n}{b_n}\to 0$ . It follows that for large enough n we have that the above inequality for d holds also for $d'$ where

$$ \begin{align*} d'=\frac{1}{k} |\{ m \in [0,k) \colon E(\psi(x)(m-j^*),\dots,\psi(x)(m-1)) \neq \psi(x)(m)\} | \end{align*} $$

for all large enough k. Thus, ${\beta }^{-}(\psi (x)) \geq s+ (\frac {b-1}{b})(\sum _{\substack {i \in J\\ i>i^*}} \frac {1}{2^{i+1}})$ , and so $\psi (x) \notin A_1(s)$ .