The third power's shortest vectors lie on a conic

The shortest vector is a polynomial with two full fibres moved a question out of high-dimensional geometry and into arithmetic. Craig’s lattices are the ideals $(1 - \zeta)^k$ of the cyclotomic integers, where $\zeta$ is a primitive $p$-th root of unity, and they live in $p - 1$ dimensions, the fewest the degrees that name the restriction allow for a rotation of order $p$. Craig proved in 1976 that the squared length of their shortest vectors is at least $2kp$. The earlier essay showed that the bound is reached exactly when some polynomial of degree $k$ over the field of $p$ elements takes one value at $k$ points and another value at $k$ other points. Each such pair of sets, with $+1$ on one and $-1$ on the other, is a shortest vector.

That settled where the minimum is. It left a count open. How many shortest vectors does a lattice have when it sits at the bound? The number is the kissing number, the first count in the lattice’s list of vectors of each length. Searches in twelve to eighteen dimensions had found these numbers for a few primes, and the earlier essays had reported them in orbits under the rotation: thirty-two orbits for the third power at seventeen, for instance, with nothing to explain why thirty-two. Now each shortest vector is a pair of sets, and counting them is a problem about polynomials over a finite field. For the third power that problem is about a conic, and a conic over a finite field has a number of points everyone knows.

Counting fibres instead of vectors #

The first step is to make the count manageable. A shortest vector of $(1 - \zeta)^k$ at the bound is an unordered pair of disjoint $k$-element sets of residues whose power sums agree up to order $k - 1$. Equivalently, the two sets are two full fibres of one monic polynomial $f$ of degree $k$: two values $c$ and $c'$ such that $f - c$ and $f - c'$ each split into $k$ distinct linear factors. The polynomials that agree in every coefficient but the constant have the same fibres, so the constant can be dropped.

The next coefficient can be dropped too. Replacing $t$ by $t + s$ changes the coefficient of $t^{k-1}$ by $ks$, which runs through every residue as $s$ does, so every monic polynomial is a translate of exactly one with that coefficient zero, and each such polynomial stands for $p$ translates with the same fibre structure. Multiplying a vector of the lattice by $\zeta$ shifts every residue by one, which is exactly this translation. So the number of orbits of shortest vectors under the rotation is a sum over the polynomials with no constant and no $t^{k-1}$ term: for each, count its full fibres $n$, and add up the number of ways to choose two of them, $n(n-1)/2$.

For the second power this is immediate. The only polynomial is $t^2$, whose full fibres are the pairs $\{a, -a\}$, one for each non-zero square, $(p-1)/2$ of them. Any two make a shortest vector, so the count is $(p-1)(p-3)/8$ orbits, which reproduces every second-power kissing number the lattice searches found: 220 at eleven, 390 at thirteen, 952 at seventeen and 1,368 at nineteen, each equal to $2p$ times the formula. For the third power the polynomials are $t^3 + \beta t$, one for each residue $\beta$, and the question is how many full fibres each one has.

A full fibre is six points on a conic #

Suppose $\{x, y, z\}$ is a full fibre of $t^3 + \beta t$: three distinct residues where the polynomial takes the same value. Then they are the three roots of one cubic $t^3 + \beta t - c$, so their sum is zero and the sum of their pairwise products is $\beta$. Putting $z = -x - y$ into the second condition gives $xy - (x + y)^2 = \beta$, that is,

$$x^2 + xy + y^2 = -\beta.$$

Conversely, any point $(x, y)$ on that curve gives three residues $x$, $y$ and $-x-y$ with the right sum and the right pairwise products, and if they are distinct they are a full fibre. Each fibre appears as six points, one for each order in which its three roots can be listed as $(x, y)$. So the full fibres of $t^3 + \beta t$ are the points of a conic, with the points where two roots coincide taken out, divided by six.

The number of points on such a conic is classical. For $\beta$ not zero, $x^2 + xy + y^2 = -\beta$ has $p - \varepsilon$ solutions, where $\varepsilon$ is $+1$ if $-3$ is a square modulo $p$ and $-1$ if it is not. That is the same as $p \equiv 1$ or $2$ modulo three. The points to remove lie on three lines, $x = y$, $y = z$ and $z = x$. On the first, the equation becomes $3x^2 = -\beta$, which has two solutions or none according to whether $-3\beta$ is a square. The other two lines give the same count. So

$$n(\beta) = \frac{p - \varepsilon - 3 - 3\left(\frac{-3\beta}{p}\right)}{6},$$

where the bracket is the Legendre symbol, $+1$ for a square and $-1$ for a non-square. At $\beta = 0$ the polynomial is $t^3$, whose full fibres are the cosets of the cube roots of unity: $(p-1)/3$ of them when three divides $p - 1$, and none otherwise.

The figure shows what the formula says: away from zero there are only two values, and the Legendre symbol picks one. Half the non-zero $\beta$ make $-3\beta$ a square and half do not, so the sum of $n(n-1)/2$ is a sum of two terms, each multiplied by $(p-1)/2$, plus the term from $\beta = 0$. Writing it out and simplifying gives a closed formula for the number of orbits of shortest vectors of $(1 - \zeta)^3$:

$$\frac{(p-1)(p-5)^2}{72} \ \text{ for } p \equiv 5 \pmod 6, \qquad \frac{(p-1)(p^2 - 10p + 33)}{72} \ \text{ for } p \equiv 1 \pmod 6.$$

At seventeen, the first formula gives sixteen times twelve squared over seventy-two, which is thirty-two.

Thirty-two, and three searches #

The formula has to agree with three independent things, and it does. First, a direct count: every $3$-element subset of residues is listed, grouped by its sum and sum of squares, and disjoint pairs within each group are counted. That brute-force count equals the formula at every prime from seven to thirty-one, and the sum over fibres, which is much faster, equals it at every prime to 199. Second, each individual $n(\beta)$ is compared with the conic’s prediction at every $\beta$ for three primes, so the formula is right term by term and not only in total.

Third, and most important, the lattice searches. Thirteen-fold, and nothing is its own dual and the essays after it computed the shortest vectors of these lattices directly, by searching in twelve, sixteen and eighteen dimensions for the vectors of minimum length and counting them. The third power has 312 shortest vectors at thirteen, 1,088 at seventeen and 1,938 at nineteen. Each is $2p$ times the formula, the factor $p$ for the rotation and the factor two for a vector and its negative: $2 \times 13 \times 12$, $2 \times 17 \times 32$ and $2 \times 19 \times 51$. The thirty-two that at seventeen the densest power of 1 − ζ moves reported as a bare number is $16 \times 12^2 / 72$.

So the kissing number of $(1 - \zeta)^3$ is $2p$ times a polynomial in $p$ of degree three, with one of two forms chosen by $p$ modulo six. For large $p$ it grows like $p^4/36$, against a dimension of $p - 1$. The lattice searches that found 1,938 shortest vectors in eighteen dimensions would need to run in a thousand dimensions to find the count at $p = 1{,}009$. The formula gives it at once: about $2.8 \times 10^{10}$.

Where the conic came from #

The appearance of a conic is not a lucky accident of three. A polynomial’s full fibre is a configuration of $k$ roots with prescribed symmetric functions, and those conditions cut out a curve, or a higher-dimensional variety, over the finite field. Counting fibres means counting points on it. For $k = 2$ the variety is a line, the pairs $\{a, -a\}$. For $k = 3$, after the translation removes one root’s freedom, two conditions on three roots leave a curve in the plane of degree two, and a curve of degree two over a finite field has a number of points that is a simple function of $p$ and one Legendre symbol. That is why the third power’s count is a polynomial, with a choice depending only on $p$ modulo six.

There is one more connection, and it explains the $\beta = 0$ term. The earlier essay found shortest vectors for free whenever $d$ divides $p - 1$: two cosets of the $d$-th roots of unity have polynomials $t^d - \alpha^d$ and $t^d - \beta^d$, which differ by a constant. At $d = 3$ those are exactly the full fibres of $t^3$, the $\beta = 0$ term here. So the coset construction is one point of the conic’s family, the point where the conic degenerates, and the conic counts everything the cosets miss. At thirteen, the cosets give $\binom{4}{2} = 6$ of the twelve orbits and the non-degenerate conics give the other six.

Nothing in the argument uses more than the structure of the field of $p$ elements, and the lattice reappears only at the end, in the factor $2p$. It is the same shape of argument as the sum that turns a lattice into its dual: a count of lattice vectors converted into a count over a finite group, where it becomes exact.

Fewer still, under every symmetry #

The rotation is not the only symmetry these lattices have. A seven-fold lattice lives on a folded torus found that the Galois automorphisms, which send $\zeta$ to $\zeta^a$ for each non-zero residue $a$, act on the whole family of cyclotomic lattices, and on Craig’s lattices they are symmetries: $(1 - \zeta)^k$ goes to $(1 - \zeta^a)^k$, which is the same ideal. On residues an automorphism multiplies every residue by $a$, and the rotation adds one. Together they are every affine map $t \mapsto at + b$, $p(p-1)$ of them, and they carry shortest vectors to shortest vectors.

Under all of them the count collapses, and it collapses to something simpler than the formula above. At seventeen the thirty-two orbits under the rotation fall into three. At nineteen the fifty-one fall into six; at thirty-seven the 516 fall into twenty-one; at seventy-three the 4,632 fall into seventy-eight. The numbers are the triangular numbers: at every prime from seven to seventy-three, the count is $m(m+1)/2$ with $m$ the whole part of $(p-1)/6$.

Part of the reason is visible in the polynomials. Multiplying $t$ by $a$ turns $t^3 + \beta t$ into a multiple of $t^3 + a^{-2}\beta t$, so the scaling moves $\beta$ through its whole class of squares or non-squares. Up to symmetry there are then only three polynomials, one with $\beta$ a square, one with $\beta$ a non-square and $t^3$ itself, and what remains of the group fixes each: the map $t \mapsto -t$, which sends the fibre at value $c$ to the fibre at $-c$. So the orbits are pairs of fibres of three polynomials, up to one reflection. That explains why the count grows like $p^2$ and not like $p^3$. It does not by itself explain why the answer is exactly triangular at every prime, and that exactness is an observation, checked prime by prime to seventy-three, rather than a theorem derived here.

The geometric meaning is sharper than the arithmetic. Two shortest vectors in the same orbit under the full group are images of each other under a symmetry of the lattice, so their surroundings are identical. The third power at seventeen, a sixteen-dimensional lattice with 1,088 shortest vectors, has only three kinds of them. A lattice whose shortest vectors are all of one kind is called transitive on them, and the root lattices are the standard examples; these lattices are not, but they come close for small primes, at one kind for seven and eleven. The shortest vector, and where it stops being easy is a reminder that in general nothing about a lattice’s shortest vectors is cheap to find. Here even their kinds are counted by a formula.

The fourth power at half the primes #

The fourth power is the natural test of whether this is a pattern or a coincidence. Its fibres are those of $t^4 + \beta t^2 + \gamma t$, one polynomial for each pair $\beta$, $\gamma$, and a full fibre is four roots with zero sum and prescribed second and third symmetric functions. Three conditions on four roots, less the translation, leave a curve that is no longer a conic. So there is no reason to expect a polynomial count, and the computation, made for every prime to 503, gives a surprising answer: it is a polynomial at exactly half the primes.

At every prime congruent to five or seven modulo eight, the number of orbits is

$$\frac{p^4 - 22p^3 + 192p^2 + c_1 p + c_0}{1152},$$

with the pair $(c_1, c_0)$ depending on $p$ modulo 24: $(-626, 455)$ for $p \equiv 5$, $(-682, 511)$ for $p \equiv 7$, $(-754, 583)$ for $p \equiv 13$ and $(-554, 383)$ for $p \equiv 23$. Each was fitted on the primes of its class below 503, a dozen of them each, with five unknowns, so seven or so primes per class were predicted rather than fitted; then the formula was checked at 613 and 647, which lie beyond the data, and held exactly. It also reproduces the fourth power’s kissing numbers from the lattice searches, $78$ at thirteen and $1{,}368$ at nineteen, and the computed count gives $476$ at seventeen.

The primes congruent to five or seven modulo eight are the primes at which $-2$ is not a square. In the language of number fields, they are the primes that stay prime in the field obtained by adjoining $\sqrt{-2}$ to the rationals. The other primes, congruent to one or three modulo eight, split there, and each can be written as $p = x^2 + 2y^2$ in essentially one way. At those primes the count is not a polynomial in $p$.

At the primes congruent to one modulo 24 the count is a polynomial in $p$ and $x$ together:

$$1152 \times \text{orbits} = p^4 - 22p^3 + 192p^2 + 7598p - 496817 - 8592x^2 - 24x^4.$$

It was fitted on nine primes with five unknowns, and confirmed afterwards at 577 and 601. At the primes congruent to three modulo eight, and at those congruent to seventeen modulo 24, no formula of this shape fits. A polynomial in $p$ and in $x$, its square, cube and fourth power, with the sign of $x$ normalised in two different ways, was tried in each class and fails by thousands.

This pattern has a known shape. An elliptic curve whose endomorphisms include multiplication by $\sqrt{-2}$ has exactly $p + 1$ points over the field of $p$ elements at every prime inert in that field, and $p + 1 - a$ points at a split prime, where $a = \pm 2x$ for $p = x^2 + 2y^2$. Point counts built from such a curve are polynomials in $p$ at the inert primes and depend on $x$ at the split ones. That is what the fourth power’s count does. The curve itself has not been identified here, and the classes where no formula fits suggest that more than one curve, or one of higher genus, is involved. The statement that can be made is narrower: the fourth power’s count behaves at the inert primes the way a curve with that complex multiplication would make it behave.

What the pictures cannot show #

The figures draw residues, conics and counts. They cannot show the lattice, a body of dimension $p - 1$ in which these pairs of sets are the shortest vectors and the counts are kissing numbers. Nor can they show what the counts say about packing. The kissing number of a lattice is the number of spheres touching each one in the packing it defines, and the third power’s kissing number growing like $p^4/36$ is modest beside the best packings known in those dimensions. These lattices are interesting for their symmetry and their arithmetic, and their density is reached by a different power, as the densest eleven-fold lattice and the essays after it showed.

Above the bound none of this applies. Where $(1 - \zeta)^k$ does not reach $2kp$, its shortest vectors are pairs of multisets with repeated residues, and the count is a different problem. The formulas here are counts at the bound, and they presuppose that the bound is reached, which for the third power holds from $p = 7$ on.

Who found the pieces #

Craig defined the lattices and proved their bound in 1976. Counting the points of a conic over a finite field goes back to Gauss and Jacobi’s work on cyclotomy and the sums named after Jacobi, and the Legendre symbol is from 1798. That supersingular primes of an elliptic curve with complex multiplication are exactly the inert ones is Deuring’s theorem of 1941. The reduction of the kissing number to a count of full fibres, the conic and its closed formula, the agreement with the lattice searches, and the observation that the fourth power is a polynomial at the primes inert in the field of $\sqrt{-2}$ are what this essay adds.

What the count must refuse #

The count has independent checks at every level. Brute force over sets and the sum over fibres are different computations of the same number. The per-$\beta$ comparison tests the conic’s formula before it is summed. The lattice searches are a third route, through geometry rather than arithmetic, and they were made earlier, with no formula in view. The claim that one quartic in $p$ counts the fourth power everywhere is put to the computation at three split primes and refused.

Still open: the curve behind the fourth power #

The fourth power’s count is a polynomial at the primes inert in the field of $\sqrt{-2}$, a formula in $x$ at some split primes, and something not yet described at the others. The obvious next step is to find the curve. Three conditions on four roots, with the translation removed, define a curve over the integers, and its point counts modulo $p$ should be the fourth power’s count once the degenerate fibres are removed, exactly as the conic’s were for the third. Writing that curve down, reducing it to a standard form, and reading off its complex multiplication would turn an observation at some ninety primes into a theorem, and would say what the classes congruent to three modulo eight are waiting for. For the fifth power the variety has dimension two, and whether its count is a polynomial anywhere is not known here.