An approximate converse of discrete uncertainty principle

2011-12-11T22:26:26Z

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

I want it to be true (for my application) :)
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?

Answer by Terry Tao for An approximate converse of discrete uncertainty principle

2011-12-12T05:13:12Z

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

An approximate converse of discrete uncertainty principle - MathOverflow

An approximate converse of discrete uncertainty principle

Answer by Terry Tao for An approximate converse of discrete uncertainty principle