A prime leaves no room for a comb

Write the powers of a root of unity into a table. Row $r$ and column $c$ hold $\zeta^{rc}$, where $\zeta$ is a primitive $n$-th root of unity, and the result is the matrix of the discrete Fourier transform, the most heavily used matrix in applied mathematics. Each entry is an arrow of length one. Now choose some rows and the same number of columns and take the determinant of what they cross. That number is called a minor, and there are a great many of them: nearly $\binom{2n}{n}$ for a table of order $n$.

The question looks routine. Can a minor be exactly nought? At composite order the answer is yes, and the minors that vanish are not rare. At order twelve, about one in six is nought. They come from the arithmetic of the order: rows 0 and 6 agree on the even columns of the table of order twelve, so any minor that uses those two rows and only even columns has two equal rows and is nought for the plainest of reasons.

At a prime, nothing of the kind has ever been found, and nothing ever will be. Sums of roots of unity that add to nothing are controlled by the prime factors of the order, so it would be natural for a prime order to be especially clean. But a minor is a far more complicated combination of arrows than a sum over a polygon, with huge cancellation built into the determinant’s alternating signs, and that none of those cancellations ever comes out perfect is a much stronger statement. It is a theorem of Nikolai Chebotarev, usually dated 1926, and it has been reproved several times since, because people keep needing it and keep being surprised that a proof fits on a page.

Testing a complex number for being exactly nought #

A floating-point computation can suggest that a determinant is nought and cannot prove it. A determinant of unit complex numbers with size around $10^{-14}$ is rounding noise, or it is a very small number; the arithmetic cannot say which. The tests here use a different idea, and it is the same one used in the search for the smallest non-zero sum of roots.

Choose a prime $q$ with $q \equiv 1 \pmod n$. In the integers modulo $q$ there is a number $w$ whose powers behave exactly as the powers of $\zeta$ do: $w^n = 1$ and no smaller power is 1. Multiplication modulo a prime has a generator, which is what guarantees it. Replacing $\zeta$ by $w$ everywhere is a ring homomorphism from the algebraic integers built out of $\zeta$ onto the integers modulo a prime. So a minor that is non-zero modulo $q$ cannot be nought as a complex number, and that one computation, in exact whole-number arithmetic, is a proof. A minor that vanishes modulo $q$ might only be a multiple of $q$ by accident; here such a minor was tested modulo a second prime and then numerically, so that nought means nought.

Only minors that include row 0 and column 0 need testing. Shifting the rows or the columns by a constant multiplies each column or row of a minor by a power of $\zeta$, which multiplies the determinant by a root of unity. So every minor equals one of those through the first row and column, up to a factor that is never nought, and all the others can be skipped. That reduces $\binom{2n}{n}$ to $\binom{2n-2}{n-1}$, which at order twelve is the difference between 2.7 million minors and 705,432.

Each prime row of the table is empty and each composite row is populated, and the populations grow quickly. There is one vanishing minor among the 20 at order four. There are 32 among 252 at order six, 369 among 3,432 at order eight, 894 among 12,870 at order nine, and 124,222 among 705,432 at order twelve, which is 17.6%. At order eleven the table has 184,756 entries, more than at order ten, and not one is nought, against 5,384 at order ten.

A proof that fits on a page #

The census cannot reach beyond small orders, since the number of minors grows like $4^n$. Chebotarev’s theorem covers them all, and its modern proof has a neat shape. It treats $\zeta$ as a variable.

Fix rows $a_1 < \cdots < a_k$ and columns $b_1 < \cdots < b_k$, and let $D(z)$ be the determinant of the table with entries $z^{a_ib_j}$. This is a polynomial in $z$ with whole-number coefficients, and it is what the minor equals at $z = \zeta$. At $z = 1$ every entry is 1, so the table has identical rows and the polynomial vanishes there, and it vanishes to high order. Subtracting rows and dividing out factors of $z - 1$, each of the $k$ columns gives up its share, and one finds that exactly $k(k-1)/2$ factors of $z - 1$ come out. What is left is a polynomial $E(z)$ with whole-number coefficients, and $E(1)$ can be computed exactly:

$$E(1) = \frac{\prod_{i<j}(a_j - a_i)\,\prod_{i<j}(b_j - b_i)}{1!\,2!\cdots(k-1)!}.$$

Here is where the prime enters. Every difference $a_j - a_i$ and $b_j - b_i$ lies strictly between $0$ and $p$, so no factor in the numerator is divisible by $p$, and $E(1)$ is not divisible by $p$. Now suppose the minor vanished, $D(\zeta) = 0$. Since $\zeta \ne 1$, that means $E(\zeta) = 0$. A polynomial with whole-number coefficients that vanishes at a primitive $p$-th root of unity is divisible by the cyclotomic polynomial $1 + z + \cdots + z^{p-1}$, and that polynomial takes the value $p$ at $z = 1$. So $p$ divides $E(1)$. It does not, and the contradiction is the theorem.

At a composite order the argument has no grip, in two places: the differences can share factors with the order, and the cyclotomic polynomial of $n$ takes value 1 at $z = 1$ unless $n$ is a prime power. The zero minors at order twelve come in through that gap.

The proof has a checkable shadow. Multiply a minor by its images under the power maps $\zeta \mapsto \zeta^t$. The result is the norm, a whole number, because it is fixed by every symmetry of the field of roots of unity. The proof says that the factor of $z - 1$ becomes a factor of $\zeta - 1$, whose norm is exactly $p$, and that nothing else contributes a further $p$. So the norm of every minor of size $k$ should contain exactly $k(k-1)/2$ factors of the prime. The figure lists the tests at orders five and seven: at size two every norm at order seven is exactly 7, at size three the norms run from 343 to 2,744, and $2{,}744 = 343 \times 8$. They have the predicted power of 7 and nothing more. A numerically computed norm that was exactly an integer multiple of the wrong power would have broken this, and none did.

The uncertainty principle that follows #

The theorem matters because of what a vanishing minor means. Choose a set $A$ of places for a signal to live on, and suppose its Fourier transform vanishes on a set $B'$. That says a vector supported on $A$ is sent to nought by the rows in $B'$: the submatrix of rows $B'$ and columns $A$ has a non-trivial null vector. If $|B'| \ge |A|$, some square minor inside that submatrix vanishes. At a prime order no minor vanishes, so this cannot happen. A non-zero signal on $a$ places can have a transform vanishing on at most $a - 1$ places.

Write $b$ for the number of places where the transform is not nought. The conclusion is

$$a + b \ge p + 1.$$

Terence Tao stated it this way in 2005. The classical result is David Donoho and Philip Stark’s of 1989, valid for every order $n$, which says that $a \cdot b \ge n$. Those are two very different curves. Take order eleven. Donoho–Stark allows a signal with 3 places and a transform with 4. Tao’s bound says the transform on 3 places needs at least 9.

The figure computes the actual boundary, by asking for every set of places and every set of vanishing rows whether a null vector exists. At order eleven the least transform for 1, 2, …, 11 places is 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. It is exactly Tao’s straight line, so the bound is attained at every point and no improvement is available. At order twelve the list is 12, 6, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, the Donoho–Stark curve rounded up, with exact equality at each divisor.

The reason for the staircase is the comb. A signal that is 1 on the multiples of 3 in the integers modulo 12, and 0 elsewhere, has 4 places, and its transform is 1 at the multiples of 4 and nought elsewhere, 3 places. A subgroup and its annihilator, the two combs, are a pair of sets that are small together, and they are the only reason the product bound is attained. A prime order has no subgroups except the trivial ones, so it has no combs, and Chebotarev’s theorem is the complete and exact form of that observation.

The lower row of the figure is what the theorem looks like at a prime. Three spikes on thirteen places can be arranged however one likes. Their transform has modulus at least 0.77 at every one of the thirteen frequencies for the arrangement shown. This is one example, but the theorem forces the count of non-zero frequencies to be at least 11, whatever the positions and whatever the sizes of the spikes.

The two theorems are one #

There is a surprising connection, and it runs to additive combinatorics. Two sets added modulo a prime proved the Cauchy–Davenport theorem: for subsets $A$ and $B$ of the integers modulo $p$, the sumset satisfies $|A + B| \ge \min(p, |A| + |B| - 1)$. Its usual proofs are about adding sets. It seems to have no connection with determinants of roots of unity.

Tao’s uncertainty principle gives another proof. The idea: Tao’s stronger form shows that, for any choice of sizes with $a + b = p + 1$, signals can be found with exactly the required supports, and those supports can be prescribed in advance on $A$ and in frequency on $B$. Take functions $f$ supported on $A$ and $g$ supported on $B$ whose transforms vanish on carefully chosen sets, multiply them pointwise on the transform side, and $f * g$ lives on $A + B$. Choosing the transform zeros so that the product vanishes on as many frequencies as possible forces the convolution to occupy many places. So $A + B$ is large because a function cannot be small on both sides.

The moral is that Cauchy–Davenport’s right-hand side $|A| + |B| - 1$ and Tao’s $p + 1$ are the same inequality read in different coordinates. Both fail at composite order for exactly the same reason: a subgroup is a set with $|A + A| = |A|$, and a subgroup is a comb. It is the arithmetic of the group, seen once through sums and once through Fourier transforms.

What a prime gives a sparse signal #

The practical consequence is about reconstructing signals from a few frequencies, and at a prime it comes out with no conditions at all. Suppose a signal has at most $s$ non-zero values, in unknown places, and suppose its transform has been measured at any $2s$ frequencies. Then the signal is determined. If two different signals with $s$ spikes gave the same measurements, their difference would have at most $2s$ places and its transform would vanish on $2s$ frequencies, and that contradicts $a + b \ge p + 1$, since the difference’s transform has at most $p - 2s$ non-zero places.

This is what started the subject now called compressed sensing. Emmanuel Candès, Justin Romberg and Tao, in a paper of 2006, began exactly here, from Tao’s prime-order uncertainty principle, and showed that a signal of $s$ spikes could be recovered from a small number of frequencies by an efficient method: minimise the sum of absolute values, subject to matching the measurements. The structure is an old one in coding theory: a polynomial through the gaps describes how the Reed–Solomon code recovers errors in unknown places from the transform of a received word, using the same table of powers over a finite field.

At a composite order, none of this works unconditionally. A comb’s transform is a comb, so a signal could vanish at every frequency measured if the frequencies are unluckily chosen, and it would be indistinguishable from nothing. Practical systems choose frequencies at random to make that vanishingly unlikely, and Candès, Romberg and Tao’s theorem is about that case. The exact statement needs a prime, or an accident; the robust statement needs randomness.

Close to nought, and not at it #

Chebotarev’s theorem says each minor is non-zero, which is a statement about algebra and carries no estimate at all. Numbers near nought in the complex plane can make an exact theorem useless in practice, and the smallest minors do shrink.

At order five every minor examined through the first row and column has modulus at least 1, and that lower bound is exact. At order seven the lowest is 0.868. At order eleven it is 0.316. An algebraic-integer argument, of the kind the smallest sum of roots used, gives a guaranteed lower bound by way of the norm: the product of all the conjugates is at least the power of $p$ that the proof forces, and each conjugate is bounded above by the determinant’s maximum, so no single one can be too small. But that bound falls exponentially in $p$, and real minors at large orders can be small enough to be lost in rounding. Even at modest size, the least minor is a measure of how badly a particular recovery might be conditioned.

So the theorem and the engineering are separated. A prime order guarantees that any $2s$ frequencies determine an $s$-sparse signal, and it does not guarantee that they determine it stably, which is to say that noise in the measurements will not be blown up by a factor of millions. For stable recovery the frequencies should be spread at random, and that is a theorem about most minors rather than all.

Where the census stops #

The census covers every order up to twelve and proves nothing above that, except what the theorem proves. The figures of the frontier go to twelve for the same reason: the number of rows and columns to try grows with two binomial coefficients at once. In each composite case the frontier was found by a search for a rank drop modulo one prime, which can in principle report a false drop, though only the entries with a real comb behind them were ever found, each meeting Donoho–Stark exactly.

The proof sketched above leaves out one computation, the evaluation of $E(1)$, which is the leading term of a determinant of powers, obtained by repeated differentiation. The figures check its consequence on small cases through the norm; they do not derive it. The smallest-minor curves are numerical, computed in double precision, and accurate to many more digits than are displayed but not proved. The connection with Cauchy–Davenport is described and not worked out, and Tao’s paper is where the exact choice of transform zeros is made.

Still open: how few frequencies at composite order #

Chebotarev’s theorem has a precise composite form that has not been settled. For order a product of two primes, or a prime power, which pairs of support sizes exist? The boundary for order twelve in the figure is a staircase determined by the divisors, but it records only sizes. Which pairs $(A, B)$ of actual sets admit a signal is much subtler. Roy Meshulam sharpened the Donoho–Stark bound in 2006 in terms of the divisors, showing that between consecutive divisors the extremal curve is a straight line. A complete description of the realisable supports, not only their sizes, for every composite order is not known.

There is a corresponding question for the prime case that is about size and not existence. How small can the smallest minor of the order-$p$ table be? The norm bound is enormously below what computation suggests, and the sharp rate is unknown. It is the same kind of gap as the sums of a few roots of unity showed, now with many more terms and an alternating structure, and it sits behind every statement about how well a few frequencies can determine a signal without randomness.

The primes have no subgroups #

At a prime order every square minor of the Fourier matrix is non-zero: a polynomial proof shows the minor carries exactly the power of $\zeta - 1$ that the shape of the determinant forces, and no more. So a signal on $a$ places has a transform on at least $p + 1 - a$, the straight line that the census finds at order eleven, in place of the staircase of divisors found at order twelve. The combs that make composite orders behave differently are subgroups, and a prime has none.

Each thing that makes the Fourier transform of a prime order special comes from that single absence. Reconstruction from any $2s$ frequencies is one form of it, and Cauchy–Davenport is another. The order-twelve table, with its 124,222 zero minors, is what those theorems would be up against without it.