# An approximate converse of discrete uncertainty principle

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?

-
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

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.