# Is there an “analytical” version of Tao's uncertainty principle?

Let $p$ be a prime. For $f: \mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{C}$ let its Fourier transform be:

$$\hat f(n) = \frac{1}{\sqrt{p}}\sum_{x \in \mathbb{Z}/p \mathbb{Z}} f(x)\, e\left(\frac{-xn}{p}\right)$$

Terence Tao proves in "An uncertainty principle for cyclic groups of prime order" that for $f: \mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{C}$ one has:

$$|S_1| + |S_2|\ge p+1$$

If $f$ is supported in $S_1$ and $\hat f$ is supported in $S_2$. This is much stronger than the traditional bound:

$$|S_1||S_2| \ge p$$

Can we prove an approximate version of this inequality, say, in which we lower bound

$$|S_1| + |S_2|$$

assuming only that $S_1$ and $S_2$ contain most of the mass of $f$ and $\hat f$ (rather than all of the mass)?

The proof of the lower bound to $|S_1||S_2|$ is "only analytical", so it caries over under this weaker assumption, but Tao's lower bound for $|S_1|+|S_2|$ relies strongly on algebra, in that it is important that $f$ and $\hat f$ are exactly $0$ outside the support, so the proof doesn't immediately carry over.

Is there such an approximate version of Tao's uncertainty principle?

For a concrete case, if the Fourier transform is normalized so that $\sum |f(x)|^2 = \sum |\hat f(x)|^2 = 1$, can we rule out the possibility that $\sum_{x \in S_1} |f(x)|^2 > 1-\epsilon$, and $\sum_{x\in S_2} |\hat f(x)|^2 > 1-\epsilon$ with $|S_1|, |S_2| < \epsilon p$?

For the applications that I am interested I need something quite weaker, but I couldn't really find a counter-example to the above possibility.

No. One just has to apply the standard example showing the classical uncertainty principle is sharp:

Let $f(a) = \sum_{n \in \mathbb Z} e^{- \pi ( a+pn)^2 / p}$. Then $\hat{f}$ is proportional to $f$.

But $1-\epsilon$ of its mass is contained in an interval of width something like $O ( \sqrt{ p \log (1/\epsilon)})$, which is much smaller than $\epsilon p$.

• Thanks, I am not familiar with this example do you have a source in mind where this example is discussed? – Rodrigo Apr 17 '18 at 10:16
• @Rodrigo It's just a Gaussian distribution, which I have made periodic in $p$ by summing over $n$. – Will Sawin Apr 17 '18 at 11:12
• I see now considering only the major contribution that this function disproves the question, but I can't seem to find a proof that it is exactly proportional to its Fourier transform – Rodrigo Apr 17 '18 at 11:28
• @Rodrigo I think it follows from the Poisson summation formula. You end up with $\hat{f}(b) = \sum_{ a\in \mathbb Z} e^{ - \pi a^2/ p + 2 \pi i ab/p}$ and then you can express that sum as a sum over the real Fourier transform of $e^{ - \pi a^2/ p + 2 \pi i ab/p}$, which is known, which should give you the main contribution and the other contributions. – Will Sawin Apr 17 '18 at 11:58
• @Rodrigo: See Figure 1 here: arxiv.org/abs/1504.01014 – Dustin G. Mixon Apr 18 '18 at 0:10

One does not need Gaussians in the finite case, just take $f$ to be the indicator function of the interval $[-(n-1),n-1]\subset\mathbb F_p$. A simple computation gives $$|\hat f(x)| = \frac1{\sqrt p} \frac{|\sin\pi(2n-1)x/p|}{|\sin\pi(x/p)|} < \frac1{2\sqrt p\|x/p\|},$$ where $\|x/p\|$ is the distance to $x/p$ from the nearest integer. As a result, $$\sum_{x=m}^{p-m} |\hat f(x)|^2 \le \frac p{2m} = \frac p{2mn} \sum_{x=0}^{p-1} |\hat f(x)|^2.$$ Taking, say, $m,n\approx\sqrt{\varepsilon^{-1}p}$, you have both $f$ and $\hat f$ concentrated on intervals of length about $2\sqrt{\varepsilon^{-1}p}$.

A historical point worth clarification. The inequality $|{\rm supp}\, f|+|{\rm supp}\,\hat f|\ge p+1$ was in fact proved first by Andras Biro, who has contributed it as a problem to the 1998 Schweitzer competition (Problem 3). Bearing in mind that Tao's paper appeared in 2005, I think it would be most reasonable to call it the Biro-Tao inequality.

The counterexample to Biro–Tao uncertainty principle for a non-prime $p = k \times l$ is a vector $f$ given by $f(x) = \sqrt{k}$ if $x$ is a multiple of $k$ and $f(x) = 0$ otherwise. Then it is easy to see that $\hat{f}(x) = \sqrt{l}$ if $x$ is a multiple of $l$ and $\hat{f}(x) = 0$ otherwise. Taking $k = l$ large enough produces a counterexample to your claim: all of the mass of $f$ and $\hat{f}$ is contained in a set of cardinality $k = \sqrt{p}$.