# Lower bound on the support size of an $\epsilon$-biased distribution

Let $$D$$ be an $$\epsilon$$-biased distribution we want to show that $$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$ I know that there are some proofs for this but I am intrested in the following particular way.

Let $$X,Y$$ be two distributions over $$\{0,1\}^n$$. Consider the "convolution" of distributions $$Z=X\circledast Y$$ to be defined by sampling $$x\sim X$$ and $$y\sim Y$$ independently and outputting $$x\oplus y$$ where $$\oplus$$ is just bit-wise xor.

Now if we define a distribution $$D^{(t)}=D\circledast\cdots\circledast D$$ ($$t$$ times) we can use some Fourier analysis and combinatorics to show that

1. $$D^{(t)}$$ is $$\epsilon^t$$-biased.
2. $$|\text{Supp}(D^{(t)})|\leq\binom{|\text{Supp}(D)|+t}{t}$$

We can also show that for every $$\delta$$-biased distribution $$Z$$ we have $$\lVert Z\rVert_2^2\leq\delta^2+2^{-n}$$ when considering the distribution as a vector of probabilities. Now, I was told that I can use the latter to obtain a lower bound on $$|\text{Supp}(D^{(t)})|$$ and then choose $$t$$ accordingly to get the desired bound.

However, the only bound I can get for $$|\text{Supp}(D^{(t)})|$$ is $$|\text{Supp}(D^{(t)})|\geq\sqrt{\frac{1}{\epsilon^{2t}+2^{-n}}}$$ And I don't see how that helps...

• It's not clear what you're asking. If you're trying to understand an existing result, please cite it. Are you suggesting a novel proof, etc?.. Dec 29 '18 at 21:29
• @Aryeh In some lecture notes by Swastik Kopparty (about Boolean functions and derandomization) I have seen an "exercise" consisting of four parts that asks to prove the "famous" lower bound on the support size of $\epsilon$-biased distribution. The first three parts are described above and I managed to handle with them. At the last part the exercise asks to use the first parts in order to get the lower bound, I do not understand how to do so. I do know that there is a proof not following the above line, but I am interested in the above. Dec 30 '18 at 7:43
• @user621824 OK, first: are you sure about the square root in your RHS? (Note that the $\ell_2$ norm of a distribution over support of size $N$ is lower bounded by $1/\sqrt{N}$; you here have the squared $\ell_2$ norm). Second: set $t$ such that the two terms of the denominator balance. Third: use $\binom{n}{k} \leq (en/k)^k$. This ought to be enough. Dec 30 '18 at 9:04

1. You shouldn't have a square root. Namely, for every $$\delta$$-biased distribution $$Z$$ (using your notation), we have $$\delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\rvert}\tag{1}$$ since the squared $$\ell_2$$ norm of a distribution over support of size $$N$$ is at least that of the uniform distribution on $$N$$ elements, which is $$1/N$$.
2. This gives you, for $$t\geq 1$$ to choose suitably, $$\lvert\operatorname{supp} D^{(t)}\rvert \geq \frac{1}{\varepsilon^{2t}+2^{-n}} \tag{2}$$ since as you have shown $$D^{(t)}$$ is $$\delta$$-biased for $$\delta=\varepsilon^t$$. A natural choice of $$t$$, in view of (2), is the one balancing the denominator, i.e., such that $$\varepsilon^{2t}=2^{-n}$$. This leads to taking $$t \stackrel{\rm def}{=} \frac{n}{2\log(1/\varepsilon)}\tag{3}$$
3. Recalling the standard bound $$\binom{n}{k}\leq \left(\frac{en}{k}\right)^k$$ for $$1\leq k\leq n$$ along with (2), (3), and what you mentioned as 2. in your question, we thus get $$\left(\frac{e(\lvert\operatorname{supp} D \rvert+t)}{t}\right)^t \geq \binom{\lvert\operatorname{supp} D \rvert+t}{t} \geq \frac{1}{\varepsilon^{2t}+2^{-n}} = \frac{1}{2\varepsilon^{2t}} \tag{4}$$ so that $$\frac{e(\lvert\operatorname{supp} D \rvert+t)}{t} \geq \frac{1}{2^{1/t}\varepsilon^{2}} \tag{5}$$
Rearranging and recalling again the choice of $$t$$ in (3) yields $$\lvert\operatorname{supp} D \rvert\geq \Omega\!\left(\frac{n}{\varepsilon^{2}\log(1/\varepsilon)} \right) \tag{6}$$ as claimed.