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

<p>Rearranging and recalling again the choice of <span class="math-container">$t$</span> in (3) yields
<span class="math-container">$$
 \lvert\operatorname{supp} D \rvert\geq  \Omega\!\left(\frac{n}{\varepsilon^{2}\log(1/\varepsilon)} \right) \tag{6}
$$</span>
as claimed.</p>

CC BY-SA 4.0
2019-01-02T16:24:36.317Z
Sorry for not accepting for a long time. Thank you!
user621824
CC BY-SA 4.0
2019-01-02T16:25:10.623Z
@user621824 No problem at all. Glad this helped.
Clement C.
CC BY-SA 4.0
2018-12-30T20:57:13.553Z
2019-01-02T10:46:35.773Z
2019-01-02T10:46:35.773Z
Clement C.
<p>Let <span class="math-container">$D$</span> be an <span class="math-container">$\epsilon$</span>-biased distribution we want to show that
<span class="math-container">$$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$</span>
I know that there are some proofs for this but I am intrested in the following particular way.</p>

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

<p>Now if we define a distribution <span class="math-container">$D^{(t)}=D\circledast\cdots\circledast D$</span> (<span class="math-container">$t$</span> times) we can use some Fourier analysis and combinatorics to show that</p>

<ol>
<li><span class="math-container">$D^{(t)}$</span> is <span class="math-container">$\epsilon^t$</span>-biased.</li>
<li><span class="math-container">$|\text{Supp}(D^{(t)})|\leq\binom{|\text{Supp}(D)|+t}{t}$</span></li>
</ol>

<p>We can also show that for every <span class="math-container">$\delta$</span>-biased distribution <span class="math-container">$Z$</span> we have <span class="math-container">$\lVert Z\rVert_2^2\leq\delta^2+2^{-n}$</span> 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 <span class="math-container">$|\text{Supp}(D^{(t)})|$</span> and then choose <span class="math-container">$t$</span> accordingly to get the desired bound.</p>

<p>However, the only bound I can get for <span class="math-container">$|\text{Supp}(D^{(t)})|$</span> is 
<span class="math-container">$$|\text{Supp}(D^{(t)})|\geq\sqrt{\frac{1}{\epsilon^{2t}+2^{-n}}}$$</span>
And I don't see how that helps... </p>

CC BY-SA 4.0
2018-12-29T21:29:04.820Z
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?..
Aryeh
CC BY-SA 4.0
2018-12-30T07:43:02.007Z
@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.
user621824
CC BY-SA 4.0
2018-12-30T09:04:39.447Z
@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.
Clement C.
<derandomization><fourier-analysis>
Lower bound on the support size of an $\epsilon$-biased distribution
user621824
# Lower bound on the support size of an $\epsilon$-biased distribution

(Asked by: username_0 on 2018-12-27)

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...

**Tags:** derandomization, fourier-analysis
> **Comments:**
> **username_1**: 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?..  
> **username_0**: @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.  
> **username_2**: @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.  

---

## 1 answers

### Answer by username_2 on 2018-12-30. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Sorry for not accepting for a long time. Thank you!  
> **username_2**: @user621824 No problem at all. Glad this helped.  

---

