<p>If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support.</p>

<p><b>Theorem.</b> Let $H(Y)$ be the <a href="http://en.wikipedia.org/wiki/Entropy_(information_theory)">Shannon entropy</a> of $Y$ and let $F  \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$.</p>

<p><i>Proof.</i> Consider the collision probability of $Y$ (the probability that two independent samples of $Y$ are the same). By <a href="http://en.wikipedia.org/wiki/Discrete_Fourier_transform#The_Plancherel_theorem_and_Parseval.27s_theorem">Parseval's identity</a>,
$$CP(Y) = \sum_y \text{Pr}[Y=y]^2 = 2^{-n} \sum_s \hat{Y}(s)^2 \leq 2^{-n} |F|,$$ as $|\hat{Y}(s)| \leq 1$. On the other hand, $CP(Y) = 2^{-H_2(Y)}$, where $H_2(Y)$ is the <a href="http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#Collision_entropy">Renyi entropy</a> of $Y$. Noting that $H_2(Y) \leq H(Y)$ gives the result. Q.E.D.</p>

<p>If $|F| = \mathrm{poly}(n)$, then $H(Y) = n-O(\log n)$. So, if $Y$ is the output of a pseudorandom generator, the seed length is at least $n-O(\log n)$.</p>

CC BY-SA 3.0
2013-10-23T06:22:04.127Z
I don't follow the reasoning here, especially the last sentence.  Why does the fact that $Y$ has large support mean that it isn't pseudorandom?  Actually, that sounds backwards.  Indeed, I'd expect that any pseudorandom distribution had darn well better have large support, if it is to have any hope of being pseudorandom (if $|S|$ is small, then it's easy to distinguish $Y$ from random, which means the distribution isn't pseudorandom).
D.W.
CC BY-SA 3.0
2013-10-23T13:24:39.130Z
@D.W. I think we often want a much bigger stretch, e.g. we would need to stretch a $\log(n)$-bit seed to an $n$-bit output in order to derandomize BPP (but such generators would have support only of size $n$). So maybe the exact answer is "maybe, if you consider stretching $n-\log(n)$ bits to $n$ bits sufficient, no otherwise".
usul
CC BY-SA 3.0
2013-10-23T14:17:10.097Z
@D.W. $\log |S|$ is a lower bound on the seed length needed to sample $Y$. One wants a pseudorandom distribution to have small seed length and thus small support. The point is that we want $Y$ to `look like' something with large support, whilst actually having sparse support.
Thomas Steinke
CC BY-SA 3.0
2013-10-23T17:25:32.560Z
If the seed length is $\lg n$ bits, then the generator is not pseudorandom: there is a trivial polynomial-time attack to distinguish its output from true random (simply enumerate all seeds to see if the value of $Y$ is attained by any of them, i.e., enumerate its support).
D.W.
CC BY-SA 3.0
2013-10-23T18:03:14.163Z
@D.W. agreed that this was a bad example, mainly because of the efficiently sample-able requirement. I should instead have just said that we would like a PRG to stretch for instance $o(n)$-bit seeds to $n$-bit outputs.
usul
CC BY-SA 3.0
2013-10-23T18:08:36.300Z
@usul, I don't know the literature on derandomization of BPP, but if you have a PRG that stretches by even one bit, then it is trivial to construct a PRG with the sort of stretch you want, simply by iteration.  So, if there exists a PRG that stretches by even one bit, then I'd expect that to be sufficient for your derandomization goals (if any PRG that stretches from $o(n)$ to $n$ bits is sufficient).  Anyway, none of this is specified in the question, so I remain puzzled by the flat "No" answer....
D.W.
CC BY-SA 3.0
2013-10-23T18:56:03.293Z
@D.W. Yes a one-bit stretch is non-trivial. But usually we want the <i>end product</i> to have exponential stretch, which cannot happen with a sparse Fourier spectrum.

Re. derandomizing BPP: You need to be careful with the quantifiers. If I want a PRG that fools n^c-time algorithms, then it suffices to have seed length 2c log n. Enumerating seeds takes n^{2c} time, which is still polynomial, but the algorithm being fooled cannot enumerate all seeds.
Thomas Steinke
CC BY-SA 3.0
2013-10-23T19:01:57.697Z
@D.W. I agree. The question is somewhat vauge. What does "pseudorandom" mean? But _usually_ one wants sparse support, which is ruled out.
Thomas Steinke
CC BY-SA 3.0
2013-10-23T19:02:02.917Z
I guess I'll just say that it you're reading a lot into the question that isn't explicitly stated there.  The question doesn't say the generator has to be good for derandomizing BPP; it doesn't say it's the end product that is desired to have a sparse Fourier spectrum; it doesn't say that an exponential stretch is required.  So, a flat "No" still seems overly strong to me.  I think the real answer is "No, if you want such-and-such additional conditions to hold."
D.W.
CC BY-SA 3.0
2013-10-23T19:31:25.590Z
@D.W. You can ask the asker to clarify what he means by a "pseudorandom distribution". I assumed it implies entropy $o(n)$ and I hope that my answer makes that reasoning clear.
Thomas Steinke
CC BY-SA 3.0
2013-10-23T04:25:00.610Z
2013-10-23T20:17:59.573Z
2013-10-23T20:17:59.573Z
Thomas Steinke
<p>For a distribution X over $\{0,1\}^n$, we can define the Fourier coefficient of the distribution as $\hat{Y}(s)= \textbf{E}_{y\in Y}({\chi_s(y)})$.<br>
The question I have is, do there exist distributions that can be efficiently computed such that at most polynomially many Fourier coefficients are non-zero?</p>

CC BY-SA 3.0
2013-10-23T19:33:02.427Z
Akshay, would you clarify what requirements you have on the pseudorandom distribution?  Do you merely require that the distribution be indistinguishable from a uniformly distributed random variable, by any polynomial-time algorithm?  Do you have any additional requirements, e.g., on the amount of stretch or the size of the seed?
D.W.
CC BY-SA 3.0
2013-10-24T16:33:48.800Z
@D.W. My bad, I actually require the distribution to have a small size. I don't really want it to derandomize BPP but rather constant width branching programs. I have edited the question. Thanks!
Akshay
CC BY-SA 3.0
2013-10-24T17:57:23.407Z
Hmm.  I'm still not sure if I've got the requirements right.  So you don't need the distribution to be pseudorandom?  Do you need the distribution to be efficiently computable, or to have small support?  The body of the question says the former, the title says the latter.  Those two conditions are not equivalent.  For instance, I suspect there are efficiently computable distributions that have polynomially many non-zero Fourier coefficients; but there are not distributions that have polynomially many non-zero Fourier coefficients and that have small support.
D.W.
CC BY-SA 3.0
2013-10-24T23:15:14.303Z
I guess "efficiently computable" is not clear itself.
Sasho Nikolov
CC BY-SA 3.0
2013-10-25T05:16:33.000Z
Usually "pseudorandom distribution" means (i) it approximates the uniform distribution in some sense and (ii) it is statistically far from uniform.

Here (i) is measured in terms of the sparsity of the Fourier transform (uniform has support 1). And I'm interpreting (ii) to mean small seed length.
Thomas Steinke
CC BY-SA 3.0
2013-10-26T05:38:31.463Z
The requirements are like the ones Thomas suggests - That the distribution has a small seed length and sparsity of the Fourier transform indicates the pseudorandom behavior. Thomas's answer was what I was looking for. Do there exist distributions with low entropy such that the have a small support for the Fourier transform.
Akshay
<reference-request><pseudorandomness>
Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support?
Akshay
# Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support?

(Asked by: username_0 on 2013-10-22)

For a distribution X over $\{0,1\}^n$, we can define the Fourier coefficient of the distribution as $\hat{Y}(s)= \textbf{E}\_{y\in Y}({\chi\_s(y)})$.  
The question I have is, do there exist distributions that can be efficiently computed such that at most polynomially many Fourier coefficients are non-zero?

**Tags:** reference-request, pseudorandomness
> **Comments:**
> **username_1**: Akshay, would you clarify what requirements you have on the pseudorandom distribution?  Do you merely require that the distribution be indistinguishable from a uniformly distributed random variable, by any polynomial-time algorithm?  Do you have any additional requirements, e.g., on the amount of stretch or the size of the seed?  
> **username_0**: @D.W. My bad, I actually require the distribution to have a small size. I don't really want it to derandomize BPP but rather constant width branching programs. I have edited the question. Thanks!  
> **username_1**: Hmm.  I'm still not sure if I've got the requirements right.  So you don't need the distribution to be pseudorandom?  Do you need the distribution to be efficiently computable, or to have small support?  The body of the question says the former, the title says the latter.  Those two conditions are not equivalent.  For instance, I suspect there are efficiently computable distributions that have polynomially many non-zero Fourier coefficients; but there are not distributions that have polynomially many non-zero Fourier coefficients and that have small support.  
> **username_2**: I guess "efficiently computable" is not clear itself.  
> **username_3**: Usually "pseudorandom distribution" means (i) it approximates the uniform distribution in some sense and (ii) it is statistically far from uniform.  Here (i) is measured in terms of the sparsity of the Fourier transform (uniform has support 1). And I'm interpreting (ii) to mean small seed length.  
> **username_0**: The requirements are like the ones Thomas suggests - That the distribution has a small seed length and sparsity of the Fourier transform indicates the pseudorandom behavior. Thomas's answer was what I was looking for. Do there exist distributions with low entropy such that the have a small support for the Fourier transform.  

---

## 1 answers

### Answer by username_3 on 2013-10-23. Score: 11 | Accepted answer

If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support.

**Theorem.** Let $H(Y)$ be the [Shannon entropy](http://en.wikipedia.org/wiki/Entropy_(information_theory)) of $Y$ and let $F \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$.

*Proof.* Consider the collision probability of $Y$ (the probability that two independent samples of $Y$ are the same). By [Parseval's identity](http://en.wikipedia.org/wiki/Discrete_Fourier_transform#The_Plancherel_theorem_and_Parseval.27s_theorem),
$$CP(Y) = \sum\_y \text{Pr}[Y=y]^2 = 2^{-n} \sum\_s \hat{Y}(s)^2 \leq 2^{-n} |F|,$$ as $|\hat{Y}(s)| \leq 1$. On the other hand, $CP(Y) = 2^{-H\_2(Y)}$, where $H\_2(Y)$ is the [Renyi entropy](http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#Collision_entropy) of $Y$. Noting that $H\_2(Y) \leq H(Y)$ gives the result. Q.E.D.

If $|F| = \mathrm{poly}(n)$, then $H(Y) = n-O(\log n)$. So, if $Y$ is the output of a pseudorandom generator, the seed length is at least $n-O(\log n)$.

> **Comments:**
> **username_1**: I don't follow the reasoning here, especially the last sentence.  Why does the fact that $Y$ has large support mean that it isn't pseudorandom?  Actually, that sounds backwards.  Indeed, I'd expect that any pseudorandom distribution had darn well better have large support, if it is to have any hope of being pseudorandom (if $|S|$ is small, then it's easy to distinguish $Y$ from random, which means the distribution isn't pseudorandom).  
> **username_4**: @D.W. I think we often want a much bigger stretch, e.g. we would need to stretch a $\log(n)$-bit seed to an $n$-bit output in order to derandomize BPP (but such generators would have support only of size $n$). So maybe the exact answer is "maybe, if you consider stretching $n-\log(n)$ bits to $n$ bits sufficient, no otherwise".  
> **username_3**: @D.W. $\log |S|$ is a lower bound on the seed length needed to sample $Y$. One wants a pseudorandom distribution to have small seed length and thus small support. The point is that we want $Y$ to `look like' something with large support, whilst actually having sparse support.  
> **username_1**: If the seed length is $\lg n$ bits, then the generator is not pseudorandom: there is a trivial polynomial-time attack to distinguish its output from true random (simply enumerate all seeds to see if the value of $Y$ is attained by any of them, i.e., enumerate its support).  
> **username_4**: @D.W. agreed that this was a bad example, mainly because of the efficiently sample-able requirement. I should instead have just said that we would like a PRG to stretch for instance $o(n)$-bit seeds to $n$-bit outputs.  
> **username_1**: @usul, I don't know the literature on derandomization of BPP, but if you have a PRG that stretches by even one bit, then it is trivial to construct a PRG with the sort of stretch you want, simply by iteration.  So, if there exists a PRG that stretches by even one bit, then I'd expect that to be sufficient for your derandomization goals (if any PRG that stretches from $o(n)$ to $n$ bits is sufficient).  Anyway, none of this is specified in the question, so I remain puzzled by the flat "No" answer....  
> **username_3**: @D.W. Yes a one-bit stretch is non-trivial. But usually we want the <i>end product</i> to have exponential stretch, which cannot happen with a sparse Fourier spectrum.  Re. derandomizing BPP: You need to be careful with the quantifiers. If I want a PRG that fools n^c-time algorithms, then it suffices to have seed length 2c log n. Enumerating seeds takes n^{2c} time, which is still polynomial, but the algorithm being fooled cannot enumerate all seeds.  
> **username_3**: @D.W. I agree. The question is somewhat vauge. What does "pseudorandom" mean? But _usually_ one wants sparse support, which is ruled out.  
> **username_1**: I guess I'll just say that it you're reading a lot into the question that isn't explicitly stated there.  The question doesn't say the generator has to be good for derandomizing BPP; it doesn't say it's the end product that is desired to have a sparse Fourier spectrum; it doesn't say that an exponential stretch is required.  So, a flat "No" still seems overly strong to me.  I think the real answer is "No, if you want such-and-such additional conditions to hold."  
> **username_3**: @D.W. You can ask the asker to clarify what he means by a "pseudorandom distribution". I assumed it implies entropy $o(n)$ and I hope that my answer makes that reasoning clear.  

---

