have identical Fourier spectra up to coefficients of order $\alpha n,$ which is another way of stating (\[eqn:mu\_s-equivalence\]).

Reduction to a Univariate Problem {#sec:univariate-reduction}
=================================

Recall from the Introduction that the crux of our proof is to establish the existence of a halfspace $f\colon\zoon\to\moo$ that requires a rational function of degree $\Theta(n)$ for pointwise approximation within $1/3.$ The purpose of this section is to reduce this task, for a suitably chosen random halfspace, to a univariate problem. The univariate problem pertains to the uniform approximation of the sign function on the set $\{\pm1,\pm2,\pm3,\dots,\pm2^{\Theta(n)}\}$ and has been solved in previous work. Key to this univariate reduction will be the construction of probability distributions in the previous two sections.

\[thm:univariate-reduction-symm\] Put $k=\lfloor\alpha n\rfloor,$ where $\alpha>0$ is the absolute constant from Theorem . Choose $w_1,w_2,\dots,w_n$ uniformly at random from $\{0,1,\dots,2^{k+1}-1\}.$ Define $f\colon\zoon\times\{0,1,2,\dots,n\}\to\moo$ by $$\begin{aligned}
f(x,t) = \sign \left( \frac12 + \sum_{i=1}^n w_ix_i - 2^{k+1}t\right).\end{aligned}$$ Then with probability at least $1-\e^{-n/3}$ over the choice of $w_1,w_2,\dots,w_n,$ one has $$\begin{aligned}
R^+(f,d)\geq R^+(\{{\pm1,\pm2,\pm 3,\dots,\pm2^k}\},d), && d=0,1,\dots,k.\end{aligned}$$

For $s={\pm1,\pm2,\pm 3,\dots,\pm2^k},$ define $X_s\subseteq\zoon$ by (\[eqn:X\_s\]). Then by Theorem \[thm:mu\_s-constructed\], with probability at least $1-\e^{-n/3}$ there is a distribution $\mu_s$ on $X_s$ for each $s$ such that $$\begin{aligned}
\label{eqn:mu_s-equivalence-restated}
