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?