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.
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
Then
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
This vanishes precisely at $\xi=0$. The support sizes are therefore $2$ and $6$, again adding to $8$.
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.