How sparse can a signal and its Fourier transform be?

Tao’s prime-order uncertainty principle turns a question about exact zeros into a sharp theorem. Seven positions are enough to see what it means.

Math Referee editorial

Put seven complex numbers around a circle. One description records their values at the seven positions; another records their discrete Fourier coefficients, measuring the seven cyclic frequency modes. How many entries can vanish in both descriptions?

Terence Tao’s An uncertainty principle for cyclic groups of prime order gives an exact answer. We follow arXiv version 6, dated 22 July 2004. Here, support means the positions where a function is nonzero. Tiny but nonzero values still count: this is a theorem about exact zeros.

A sharp trade-off

For a prime $p$, take a nonzero function $f:\mathbb Z/p\mathbb Z\to\mathbb C$, with Fourier transform

$$\widehat f(\xi)=\frac1p\sum_{x=0}^{p-1}f(x)e^{-2\pi i x\xi/p}.$$

Then

$$|\operatorname{supp}(f)|+|\operatorname{supp}(\widehat f)|\ge p+1.$$

The hypotheses matter: the function is complex-valued, is not identically zero, and lives on a cyclic group of prime order.

The result also describes every possible pair of support sets. Given nonempty $A,B\subseteq\mathbb Z/p\mathbb Z$ with $|A|+|B|\ge p+1$, some function has spatial support exactly $A$ and Fourier support exactly $B$. Sharpness therefore goes beyond finding one equality example: every permitted arrangement of occupied positions and frequencies occurs. This is the converse in Theorem 1.1 of the paper.

Seven positions, two examples

For $p=7$, let $\delta_0$ be $1$ at position $0$ and zero elsewhere. Its Fourier transform is $1/7$ at every frequency. The support sizes are $1$ and $7$, meeting the bound $1+7=8$.

Now take $f=\delta_0-\delta_1$. Only two spatial positions are occupied, and

$$\widehat f(\xi)=\frac{1-e^{-2\pi i\xi/7}}7.$$

This vanishes precisely at $\xi=0$. The support sizes are therefore $2$ and $6$, again adding to $8$.

Support of delta zero minus delta one on seven positions: positions zero and one are nonzero; frequencies one through six are nonzero. All other entries are zero.

Cancellation removes one frequency; the theorem says a nonzero signal occupying two positions cannot remove any more. By comparison, the general finite-group product bound would only require at least four nonzero Fourier coefficients.

Primality is essential. On eight positions, put $1$ at positions $0$ and $4$ and zero elsewhere. Its transform is $(1+(-1)^\xi)/8$, so only the four even frequencies remain. The support sum is $2+4=6$, ruling out an analogous universal lower bound of $9$. The subgroup structure at composite sizes allows this pattern.

Why a matrix controls the zeros

The proof’s key ingredient is a strong property of the prime Fourier matrix: every square submatrix has nonzero determinant.

Suppose $f$ occupies $s$ positions and its transform vanishes at $s$ chosen frequencies. Its nonzero values then solve a square, invertible homogeneous linear system, forcing them all to vanish. This contradiction allows at most $s-1$ zero frequencies, leaving at least $p-s+1$ nonzero ones. The paper establishes the determinant property using cyclotomic integers and a Vandermonde calculation; see Lemmas 1.2–1.3 and Corollary 1.4.

There is also a polynomial interpretation. Form a polynomial whose coefficient vector is $f$. Its values at the $p$th roots of unity are $p$ times the Fourier coefficients. Consequently, a complex polynomial with $k+1$ nonzero terms and distinct exponents between $0$ and $p-1$ has at most $k$ distinct zeros among those roots of unity. This says nothing about its other complex zeros or their multiplicities.

What the review checked

The public archive review supports the main theorem and its two applications after two local formula corrections: a missing sign in the determinant calculation and a final max/min reversal in the Cauchy–Davenport argument. Neither changes the intended conclusions.

The review combines model assessments with limited source checks. It is not a formal proof certificate, and independent human grading remains pending. The attributed higher-dimensional extension and its external source remain outside its checked scope. This article draws on the public review dated 15 October 2026, whose eight responses are available in the archive.

The reading guide and dependency graph follow the argument from the cyclotomic lemma through Fourier minors to the uncertainty theorem and its applications. The separate panel page records the corrections and limits. Together, they make it possible to inspect both the mathematics and exactly what was checked.

Cite this spotlight

If this spotlight informs your work, please cite it.

Igor Rivin. How sparse can a signal and its Fourier transform be?. Math Referee, .

Download .bib
View BibTeX
@misc{rivin2026spotlight-how-sparse-can-a-signal-be,
  author = {Rivin, Igor},
  title = {{How sparse can a signal and its Fourier transform be?}},
  year = {2026},
  month = {November},
  date = {2026-11-18},
  howpublished = {Math Referee},
  url = {https://mathreferee.dimensionreducers.ai/spotlight/how-sparse-can-a-signal-be/},
  note = {Paper Spotlight}
}

Take a closer look at your paper.

Explore the public reports, then join the waitlist for our invitation-only research preview. Joining is free; reviews are paid.

Join the preview waitlist