Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $f:\mathbb{Z}_n \rightarrow \{0, 1\}$ and let's normalize the Fourier transform $\hat{f}$ so that $\|\hat{f}\|_2 = \|f\|_2$, i.e. $$\hat{f}(\xi) = \frac{1}{\sqrt{n}}\sum_{x \in \mathbb{Z}_n}{f(x)e^{-2\pi i x \xi/n}}$$ Also let $\hbox{supp}(f) = \{x \in \mathbb{Z}_n: f(x) \neq 0\}$.

What I am calling the discrete uncertainty principle is the following statement:

If $|\hbox{supp}(f)| > 0$ then $|\hbox{supp}(f)| \cdot |\hbox{supp}(\hat{f})| \geq n$.

This inequality is tight for the Dirac comb. Also, for $n$ a prime number a much stronger inequality is true: $|\hbox{supp}(f)| + |\hbox{supp}(\hat{f})| \geq n + 1$ (again as long as $f$ is not the constant 0 function).

The uncertainty principle states that if $f$ is is "concentrated" then $\hat{f}$ is "spread-out". I am interested in the existence of a weak converse, i.e. is it true in some approximate sense that if $f$ is very spread out then $\hat{f}$ is fairly concentrated.

Here is a possible theorem statement that I would like to be true:

Let $f:\mathbb{Z}_n \rightarrow \{0, 1\}$ and let $\hat{f}$ be define as above. Is it true that for any $f$ s.t. $\|f\|_2^2 \geq \sqrt{n}$ there exists a set $S \subseteq \mathbb{Z}_n$ s.t. $|S| \leq \sqrt{n}$ and $$\sum_{\xi \in S}{|\hat{f}(\xi)|^2 \geq \|\hat{f}\|_2^2 - \sqrt{n}} = \|f\|_2^2 - \sqrt{n}$$

Note that since the range of $f$ is $\{0, 1\}$, $\hbox{supp}(f) = \|f\|_2^2$. Note also that the condition that $\|f\|_2^2 \geq \sqrt{n}$ is redundant given the error factor of $\sqrt{n}$. On the other hand, some error factor is necessary, given the strong inequality for $n$ a prime number that I mentioned above.

The reasons I have for guessing this statement are that

  1. I want it to be true (for my application) :)

  2. I have checked it by brute-force enumeration for $n \leq 23$.

Is there any statement of this form known? Or is it obviously false?

share|improve this question
If you try the random 0-1-valued function, I think you will find that asymptotically almost surely $\hat f(0) = \|f\|_2^2 \sim n$, but that $|\hat f(\xi)| = O(\log n)$ for all non-zero $\xi$ (by the Chernoff inequality). So this will provide a counterexample to your statement for n large enough. –  Terry Tao Dec 11 '11 at 23:24
... $\hat f(0)$ should be $n^{1/2} \hat f(0)$, with your normalisations. Also, a deterministic counterexample can probably be constructed by setting f to be the indicator function of the quadratic residues, say in the case when n is prime. –  Terry Tao Dec 11 '11 at 23:25
@TerryTao Now I am amazed I didn't try this calculation. Thanks! So, $|\hat{f}(0)| = \sqrt{n}/2 \pm O(\log n)$ and $|\hat{f}(\xi)| = O(\log n)$ for all $\xi \neq 0$ with nonzero probability. So clearly for error factor $\sqrt{n}$ the set $S$ needs to be of size at least $(n - \sqrt{n})/\log n$. –  Sasho Nikolov Dec 12 '11 at 0:17
I can accept this if it's given as an answer. Sorry for asking an uninteresting question. Unless someone sees a way to salvage a statement like this, but right now I don't see a case where the probabilistic counterexample would fail. –  Sasho Nikolov Dec 12 '11 at 0:23
add comment

1 Answer

up vote 7 down vote accepted

(My previous comment, converted to an answer as requested.)

If one sets $f$ to be the random 0-1 valued function, then from the Chernoff inequality one sees that with non-zero probability, one has $\hat f(0) = \sqrt{n}/2 + O(1)$, $\|f\|_2^2 = n/2 + O(\sqrt{n})$ and $\hat f(\xi) = O(\log n)$ for all $\xi \neq 0$, so the Fourier transform is basically maximally dispersed, so there is no concentration at anywhere near the scale suggested.

If $n$ is prime, one can obtain a deterministic version of this example (without the losses of $\log n$) by taking $f$ to be the indicator function of the quadratic residues, and then using Gauss sums.

Informally, "most" functions (drawn from, say, a gaussian measure) will be more or less uniformly spread out in phase space, which implies that the function and its Fourier transform will both be spread out uniformly as well. Concentration (either in physical space or frequency space) is the exception rather than the rule.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.