The shortest vector is a polynomial with two full fibres

A lattice with a rotation of prime order $p$ fixing no vector lives in $p - 1$ dimensions, for the reason the degrees that name the restriction gives, and the most symmetric ones are the ideals $(1 - \zeta)^k$ of the cyclotomic integers, Craig’s lattices, with the trace form, the fixed points of the fold a seven-fold lattice lives on a folded torus found. At seventeen the densest power of 1 − ζ moves found that for the first four powers at 17, 19 and 23 the minimum is exactly $2kp$, the bound Craig proved in 1976. With the minimum known and the determinant a power of $p$, each density became a formula, and the competition between powers became one inequality: the next power wins while $(1 + 1/k)^{(p-1)/2}$ exceeds $p$. The inequality predicted that the fourth power would win at twenty-three, before that lattice was computed, and it did.

That essay ended on the assumption the rule rests on. The bound had been checked only at three primes and only for the low powers, by shortest-vector searches in sixteen to twenty-two dimensions. The rule’s next predictions, the fourth power at 29 and 31 and the fifth at 37, would need the same searches in twenty-eight, thirty and thirty-six dimensions, and it called them harder than anything run here. They are not needed. The question has an exact translation into the field of $p$ elements, where it is a question about polynomials, and in that form every power at all three primes can be settled.

From a lattice to a list of residues #

An element of the cyclotomic integers can be written as $x = \sum_i c_i \zeta^i$ with one whole number $c_i$ for each residue $i$ modulo $p$, and the list is unique up to adding the same number to every entry, because $1 + \zeta + \dots + \zeta^{p-1} = 0$. The trace form sums the squared absolute values of $x$ over all $p - 1$ complex embeddings, and by Parseval’s identity, the finite cousin of the sum that turns a lattice into its dual, turning a sum over frequencies into a sum over positions, that sum is $p \sum c_i^2 - (\sum c_i)^2$.

Membership in $(1 - \zeta)^k$ is also a statement about the list. Reducing modulo $1 - \zeta$ sends $\zeta$ to one, so $x$ lies in $(1 - \zeta)$ exactly when $\sum c_i$ is divisible by $p$; shifting the whole list then makes the sum zero, and the trace form becomes $p \sum c_i^2$. For higher powers, $x$ lies in $(1 - \zeta)^k$ exactly when the first $k$ Taylor coefficients of the polynomial $\sum c_i t^i$ at $t = 1$ vanish modulo $p$, which for $k < p$ is the same as the vanishing of the power sums $\sum c_i i^j$ modulo $p$ for $j = 0, 1, \dots, k - 1$. So the minimum of $(1 - \zeta)^k$ is $p$ times the least $\sum c_i^2$ over integer lists on the residues whose first $k$ power sums vanish modulo $p$. No real number appears anywhere.

Craig’s bound, from Newton’s identities #

Split a list $c$ into its positive part and its negative part: two multisets of residues, $P$ and $N$, each residue repeated as often as its entry. The sum condition makes them the same size $r$, and the power-sum conditions say that $P$ and $N$ have the same power sums to order $k - 1$. Newton’s identities convert power sums into the coefficients of the polynomial whose roots they are, so the polynomials $\prod_{a \in P}(t - a)$ and $\prod_{b \in N}(t - b)$, both of degree $r$, agree in their top $k$ coefficients. The identities can be used over the field of $p$ elements because $r$ and $k$ are less than $p$, so the integers they divide by are invertible there.

If $r$ were smaller than $k$, the two polynomials would agree entirely, so $P$ and $N$ would be the same multiset and the list would be zero. So $r \ge k$, and $\sum c_i^2$, which is at least the total size $|P| + |N|$, is at least $2k$. That is Craig’s bound, and Newton’s identities are the whole proof. Equality needs $r = k$ with every entry plus or minus one: two disjoint sets of $k$ residues whose polynomials differ only in the constant term. Put differently, a polynomial $f$ of degree $k$, with $f(t) = 0$ on one set and $f(t) =$ some other constant on the second. The bound is attained exactly when some polynomial of degree $k$ over the field takes two different values $k$ times each.

The figure at the head of this essay draws one. Over the field of seventeen elements the product $t(t-1)(t-2)(t-3)$ vanishes at nought, one, two and three, and takes one other value at four other points. Those two sets of four have equal first, second and third power sums modulo seventeen, and the list with $+1$ on one and $-1$ on the other is a vector of $(1 - \zeta)^4$ of squared length $8 \cdot 17$, the bound. The sixteen-dimensional search that established that minimum found it by exploring a sixteen-dimensional ellipsoid. Here it is a row of seventeen numbers.

Two cosets of the roots of unity #

For some powers the polynomial can be written down without a search. If $d$ divides $p - 1$, the $d$-th roots of unity in the field form a subgroup of $d$ elements, and so does each of its cosets, the subgroup multiplied by a fixed non-zero residue. The polynomial whose roots are a coset $\alpha \mu_d$ is $t^d - \alpha^d$. Two different cosets give $t^d - \alpha^d$ and $t^d - \beta^d$, which differ by a constant. So the bound is attained at every proper divisor $d$ of $p - 1$, wherever in the cycle that divisor sits. At nineteen that includes $k = 6$, which is past the middle of a cycle of nine; at thirty-one it includes $k = 10$, in a cycle of fifteen; at thirty-seven, $k = 9$ and $k = 12$ in a cycle of eighteen.

That construction has a limiting case that turns out to matter. When $d = (p-1)/2$, the subgroup is the squares modulo $p$, the quadratic residues, and the other coset is the non-squares. Their polynomials are $t^{(p-1)/2} - 1$ and $t^{(p-1)/2} + 1$. The list with $+1$ on the squares and $-1$ on the non-squares, which is the Legendre symbol, therefore lies in every $(1 - \zeta)^k$ with $k \le (p-1)/2$, with squared length $p - 1$.

Every power at six primes #

For the powers not covered by a divisor, the search for two full fibres is direct. For small $k$ it runs over the sets $P$ of $k$ residues, normalised by the affine maps $t \mapsto ut + s$ (which preserve the property) to contain nought and one, computes the polynomial’s value at every residue, and asks whether some non-zero value is taken $k$ times. For $k$ near half of $p$ the sets are large and the complement is small, so the search runs instead over the complement $Q$ of $P$ and $N$: since every residue is a root of $t^p - t$, the product of the two polynomials is $(t^p - t)$ divided by $Q$’s polynomial, and that quotient plus a constant must be a perfect square.

Where the bound fails, its minimum is found by a separate route. The lists satisfying the power-sum conditions form an integer lattice of dimension $p - 1$, with the integer form $p \sum c_i^2 - (\sum c_i)^2$, and a Fincke–Pohst enumeration on its reduced basis, with the radius shrinking each time a shorter vector turns up, finds the exact minimum in seconds. The form is integral and every vector reported is rechecked exactly, so no tolerance enters. The two routes are independent, one combinatorial and one geometric, and they agree at every one of the sixty-seven powers where both apply: the minimum is $2k$ exactly where the search finds two full fibres.

The table is the result. At every prime the bound holds through the middle of the cycle: to $k = 4$ at 17, 6 at 19 and 23, 7 at 29, 8 at 31 and 9 at 37. Past that it fails, except at divisors of $p - 1$, and the exceptions are where the earlier essay’s description, that the bound fails past the middle of each cycle, needs correcting: at thirty-one the tenth power reaches the bound although the ninth does not, and at thirty-seven the twelfth does although the tenth and eleventh do not. Position in the cycle is not what decides; the existence of a polynomial with two full fibres is, and a divisor of $p - 1$ always supplies one.

Above the bound the minimum climbs, and then it stops. At 29 the minima in units of $p$ run 20, 24, 28, 28, 28, 28 for the eighth to the thirteenth powers; at 31, 20, 20, 30, 30, 30, 30; at 37, 24, 24, 24, 36, 36, 36, 36, 36. The ceiling is always $p - 1$: the Legendre symbol’s vector lies in every power to the middle of the cycle and beyond, and once the bound has climbed past its length nothing shorter exists. The same ceiling appears at the primes the earlier essays computed: sixteen for the sixth and seventh powers at seventeen, eighteen for the seventh and eighth at nineteen, twenty-two for the eighth to tenth at twenty-three.

What a shortest vector looks like above the bound #

The reading by polynomials does not stop at the bound, and one example shows how it continues. At twenty-nine the eighth power is the first that misses: the search visits 296,010 sets of eight residues containing nought and one, and no polynomial of degree eight has two full fibres. So no list of sixteen entries of plus and minus one lies in the ideal, and the minimum is at least $18 \cdot 29$. The exact search puts it at $20 \cdot 29$, and the shape of a shortest vector says why eighteen is impossible and twenty is not.

A vector of squared length twenty can be built from two multisets of eight residues each, each containing one repeated residue: a list with one entry of $+2$, one of $-2$, six of $+1$ and six of $-1$, whose squares add to $4 + 4 + 6 + 6$. The search above the bound finds one with the repeated residue at nought, the other residues of the positive side at one, two, three, seventeen, twenty-four and twenty-seven, and the negative side at five, six, seven, fourteen, nineteen, twenty and a repeated sixteen. In polynomial terms that is a polynomial of degree eight with a double root at nought, whose value at another point is reached by a fibre that also has a double point. Both fibres are complete counted with multiplicity, and the polynomials still differ by a constant. A double root costs two units of length instead of one, so the next possible length above the bound is two units more, and at the eighth power at twenty-nine it is the length that occurs.

The same reading explains the levels the minima climb through. Above the bound a shortest vector either uses multisets larger than $k$, whose polynomials may differ in more than the constant term, or multisets of size $k$ with repeated points. Each step up in length buys one of those freedoms, and the minimum is the first length at which the freedom is enough. At the ceiling, the quadratic residues need neither: two disjoint sets of size $(p-1)/2$ whose polynomials differ by a constant, which reaches every power to the middle of the cycle at the price of their size.

The minima the lattice searches found #

The reduction is checked against the computation it replaces. The earlier essays found the special members’ densities at seventeen and nineteen by shortest-vector searches on real Gram matrices in sixteen and eighteen dimensions, and those densities imply each minimum. The power-sum minima agree with them at every power: the bound for the first four powers at both primes and the fifth and sixth at nineteen, and above it 12, 16 and 16 at seventeen and 18 and 18 at nineteen. Those last four were found there by a search that had to compute each power at a representative near the middle of the cycle because the weights of the powers themselves spanned four orders of magnitude. Here they come from lists of small integers.

Four, four and five #

With every minimum known exactly, the densest power at each prime is no longer a prediction. It is the fourth at twenty-nine, the fourth at thirty-one and the fifth at thirty-seven, as the rule predicted, and in each case the winner is a power where the bound is attained, so the formula for its density is exact. The earlier essay named the one way the rule could fail: a power above the bound, whose density exceeds the formula’s, overtaking the predicted peak. The nearest any comes is the eighth power at twenty-nine, with minimum $20p$ where the formula assumed $16p$; its density rises by a factor of $(20/16)^{14}$, about twenty-three, and still reaches only about half of the fourth power’s. Past the middle of the cycle the formula falls by orders of magnitude a step, far faster than the climbing minimum can repair.

The full sequence of densest powers from seven to thirty-seven is now 2, 2, 2, 3, 3, 4, 4, 4, 5, every term computed and every term what the inequality says. The peak keeps moving roughly as $(p-1)/(2\log p)$, the estimate the earlier essay derived, the far end of a story that starts with the densest lattice in the plane, and the evidence that the bound stays attained at the peak now covers three more primes and every power at each.

Why the divisors, and why the middle #

The two families of attained powers have different reasons, and the table shows both. The divisors of $p - 1$ are attained for an algebraic reason that has nothing to do with size: the cosets of a multiplicative subgroup. The powers below the middle are attained for a counting reason. A polynomial of degree $k$ takes a given value at $k$ distinct points with probability about $1/k!$ for a random choice, so a random polynomial has about $p/k!$ full fibres, and there are $p^{k-1}$ polynomials to choose from once the constant term is set aside. Two full fibres in one polynomial are plentiful while $k$ is small against $p$ and vanish as $k$ approaches $p/2$, where the two fibres would have to fill most of the field. Where the counting runs out the divisors remain, which is why the table’s pattern is a solid block followed by isolated cells at the divisors.

That reading is a heuristic, not a theorem, and it is not what settles any entry. Every shaded cell has its pair of fibres, found and checkable, and every unshaded cell has its minimum from an exhaustive search.

What the pictures cannot show #

The figures draw residues and polynomials. They cannot show the lattice in which the minimum is a length, a lattice of up to thirty-six dimensions whose shortest vectors are the pairs of fibres drawn here. Nor do they show how many shortest vectors there are, the kissing numbers thirteen-fold, and nothing is its own dual and the essays after it counted in orbits, or how the lengths of all the other vectors are distributed, the theta series how many vectors of each length counts. A pair of fibres can be found by search, but counting all of them, which is what the kissing number of a power at the bound amounts to, is a different and larger enumeration, and it has not been made at the new primes.

Who found the pieces #

Newton’s identities between power sums and elementary symmetric functions are from the 1660s. Craig introduced the lattices and their bound in 1976, and Conway and Sloane’s book tabulates them. The question of two sets with equal power sums up to some order is the Prouhet–Tarry–Escott problem when asked over the integers, studied since the eighteenth century and still open in general; the version here, over a field of prime order, is the same question with a modulus, and it is much easier, as the table shows. The reduction of the minimum to that question, the coset construction at the divisors of $p - 1$, the ceiling set by the quadratic residues, and the exact minima at 29, 31 and 37 are what this essay adds. The shortest vector, and where it stops being easy is the reminder that the general problem is hard; these lattices have enough arithmetic in them to avoid it.

What the computation must refuse #

The refused claim is the description the earlier essay gave from three primes: that the bound is attained up to the middle of each cycle and not beyond. At nineteen the fifth and sixth powers, both past the middle of a cycle of nine, attain it, and at thirty-one and thirty-seven isolated powers far past the middle do, at the divisors of $p - 1$.

Still open: how many shortest vectors #

At the bound, every shortest vector of $(1 - \zeta)^k$ is a pair of disjoint $k$-sets with equal power sums to order $k - 1$, so the kissing number is twice the number of such pairs. For the second power that is the number of pairs $\{a, b\}$, $\{c, d\}$ with $a + b = c + d$, which explains the earlier essay’s count of orbits as pairs among the $(p-1)/2$; for the third power it counts triples with equal sums and equal sums of squares, and the earlier essay found that number, 32 orbits at seventeen, unexplained. It is now the number of cubic polynomials over the field of seventeen elements with two full fibres, divided by the symmetry. Whether that has a closed form, a character sum of the kind that counts points on curves, and whether it explains why the third power’s kissing numbers grow as they do, has not been worked out.