$\alpha>0$ be sufficiently small. We will assume throughout the proof that $n\geq 1/\alpha,$ the theorem being trivial otherwise. Set $\epsilon=2\alpha,$ $\zeta=1/5,$ and $k=\lfloor \alpha n\rfloor$ in Theorem \[thm:RESHETO\]. Then with probability at least $1-\e^{-n/3}$ over the choice of $w_1,w_2,\dots,w_n,$ one has $$\begin{aligned}
&\ABS{\hat f_s(T) - \frac{\delta_{T,{\varnothing}}}{2^{\lfloor \alpha
n\rfloor+1}}} \leq
2^{-n/5}, 
        &&\abs{T}\leq 2\alpha n,\quad s\in\ZZ,
        \label{eqn:f_s-guarantee}\end{aligned}$$ where $f_s\colon\zoon\to\zoo$ is given by $f_s(x)=1\Leftrightarrow x\in X_s.$ It follows that for each $s,$ $$\begin{aligned}
\label{eqn:X_s-size}
\abs{X_s} = 2^n\hat f_s({\varnothing}) \geq
2^n(2^{-\lfloor\alpha n\rfloor-1}-2^{-n/5}).\end{aligned}$$

For $f,g\colon\zoon\to\Re,$ we will write $\langle f,g\rangle_{X_s} = \abs{X_s}^{-1}\sum_{x\in X_s}f(x)g(x).$ Let $\Scal\subset\Pcal(\oneton)$ be the system of nonempty subsets of at most $\alpha n$ elements. Fix any $T\in \Scal.$ Then for each $s,$ $$\begin{aligned}
\sum_{\substack{S\in\Scal\\S\ne T}} \abs{\langle \chi_S,\chi_T\rangle_{X_s}}
=\frac{2^{n}}{\abs{X_s}}
   \sum_{\substack{S\in\Scal\\S\ne T}} \abs{\hat f_s(S\oplus T)}
\leq \frac{2^{n}}{\abs{X_s}} \cdot\abs{\Scal}\, 2^{-n/5} <\frac12,
\label{eqn:cross-correlations}\end{aligned}$$ where the final two inequalities follow from (\[eqn:entropy-bound\]), (\[eqn:f\_s-guarantee\]), and (\[eqn:X\_s-size\]). Similarly, for each $s,$ $$\begin{aligned}
\sum_{S\in\Scal} \abs{\langle f_s,\chi_S\rangle_{X_s}}
=\frac{2^{n}}{\abs{X_s}}
   \sum_{S\in\Scal} \abs{\hat f_s(S)}
\leq \frac{2^{n}}{\abs{X_s}} \cdot\abs{\Scal}\, 2^{-n/5} <\frac12.
\label{eqn:correlations-with-f_s}\end{aligned}$$ In view of (\[eqn:cross-correlations\]) and (\[eqn:correlations-with-f\_s\]), Theorem \[thm:distribution-by-inversion\] provides a distribution $\mu_s$ on $\zoon$ that is supported on $X_s$ and obeys $\hat\mu_s(S) = 0$ for $S\in\Scal.$ Since $\mu_s$ is a probability distribution, we additionally have $\hat\mu_s({\varnothing})=2^{-n}$ for all $s.$ In particular, the distributions $\mu_s$ 