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.

Thanks in advance


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

  • $\begingroup$ Thanks, I am not familiar with this example do you have a source in mind where this example is discussed? $\endgroup$ – Rodrigo Apr 17 '18 at 10:16
  • 2
    $\begingroup$ @Rodrigo It's just a Gaussian distribution, which I have made periodic in $p$ by summing over $n$. $\endgroup$ – Will Sawin Apr 17 '18 at 11:12
  • $\begingroup$ 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 $\endgroup$ – Rodrigo Apr 17 '18 at 11:28
  • 3
    $\begingroup$ @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. $\endgroup$ – Will Sawin Apr 17 '18 at 11:58
  • 1
    $\begingroup$ @Rodrigo: See Figure 1 here: arxiv.org/abs/1504.01014 $\endgroup$ – 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}$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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