and define $f\colon\zoon\to\zoo$ by $$\begin{aligned}
f(x)=1\qquad\Leftrightarrow\qquad \sum_{i=0}^k 2^i\sum_{j\in
S_i} x_j\equiv s \pmod{2^{k+1}}.
\label{eqn:f-modular}\end{aligned}$$ Then with probability at least $1-(k+1)2^{-n+H(\epsilon)n+2\zeta n}$ over the choice of $S_0,S_1,\dots,S_k,$ one has $$\begin{aligned}
&\ABS{\hat f(T) - \frac{\delta_{T,{\varnothing}}}{2^{k+1}}} \leq
2^{-\zeta n}, 
        &&\abs{T}\leq \epsilon n.
        \label{eqn:f-low-order}\end{aligned}$$

In view of the modular counting in (\[eqn:f-modular\]), one may assume that $0\leq s<2^{k+1}$ and therefore $s=\sum_{i=0}^k 2^ib_i$ for some $b_0,b_1,\dots,b_k\in\zoo.$ The proof of the lemma is by induction on $k$ for a fixed $s.$

The base case $k=0$ corresponds to $f(x) = \frac12 + \frac12(-1)^{b_0}\chi_{S_0}(x).$ One obtains (\[eqn:f-low-order\]) by conditioning on the event $|S_0|>\epsilon n,$ which in view of (\[eqn:entropy-bound\]) occurs with probability no smaller than $1-2^{-n + H(\epsilon)n}.$

We now consider the inductive step. Define $f'\colon\zoon\to\zoo$ by $$\begin{aligned}
f'(x)=1
  \qquad\Leftrightarrow\qquad 
\sum_{i=0}^{k-1} 2^i\sum_{j\in S_i} x_j\equiv 
\sum_{i=0}^{k-1} 2^ib_i\pmod{2^{k}}.\end{aligned}$$ Let $E_1$ be the event, over the choice of $S_0,\dots,S_{k-1},$ that $\abs{\widehat
{f'}(T)-2^{-k}\delta_{T,{\varnothing}}} \leq
2^{-\zeta n}$ for $\abs{T}\leq \epsilon n.$ By the inductive hypothesis, $$\begin{aligned}
\Prob[E_1] \geq 1-k2^{-n+H(\epsilon)n + 2\zeta n}.
\label{eqn:inductive-assumption}\end{aligned}$$ Let $E_2$ be the event, over the choice of $S_0,\dots,S_k,$ that $\abs{\hat f(T) - \frac12 \widehat{f'}(T)}
\leq 2^{-\zeta n-1}$ for $\abs{T}\leq \epsilon n.$ In this terminology, it suffices to show that $$\begin{aligned}
\Prob[E_1\wedge E_2] \geq 1- (k+1)2^{-n+H(\epsilon)n +2\zeta n}.
\label{eqn:claim-rephrased}\end{aligned}$$ Observe 