= 
  {\begin{cases}
  -1, &x<0, \\
  0,  &x=0, \\
  1, &x>0.
  \end{cases}}\end{aligned}$$ The complement of a set $S$ is denoted $\overline S.$ We denote the symmetric difference of sets $S$ and $T$ by $S\oplus T = (S\cap \overline T) \cup (\overline S
\cap T).$ For a finite set $X,$ the symbol $\Pcal(X)$ denotes the family of all $2^{\abs{X}}$ subsets of $X.$ For functions $f,g\colon X\to\Re$ on a finite set $X,$ we use the notation $$\begin{aligned}
\langle f, g\rangle = \frac1{\abs X} \sum_{x\in X} f(x) g(x).\end{aligned}$$ We let $\log x$ stand for the logarithm of $x$ to the base $2.$ The binary entropy function $H\colon[0,1]\to[0,1]$ is given by $H(p) = -p\log p -
(1-p)\log (1-p)$ and is strictly increasing on $[0,1/2].$ The following bound is well known [@jukna01extremal p. 283]: $$\begin{aligned}
\sum_{i=0}^k {n\choose i} \leq 2^{H(k/n)n}, &&
k=0,1,2,\dots,\lfloor n/2\rfloor.
\label{eqn:entropy-bound}\end{aligned}$$ For elements $x,y$ of a given set, we use the Kronecker delta $$\begin{aligned}
\delta_{x,y}
={\begin{cases} 1, & x=y, \\
          0, &x\ne y.
\end{cases}}\end{aligned}$$ The symbol $P_k$ stands for the family of all univariate real polynomials of degree up to $k.$ The majority function $\MAJ_n\colon\zoon\to\moo$ has the usual definition: $$\begin{aligned}
\MAJ_n(x)
={\begin{cases}-1,     & x_1+x_2+\cdots+x_n > n/2, \\
         1,     & \text{otherwise}.\end{cases}}\end{aligned}$$

Fourier transform. {#fourier-transform. 