# Is the square of the covering radius of an integral lattice/quadratic form always rational?

This is one of many observations from Pete L. Clark's questions on "Euclidean" quadratic forms. I sent Pete many positive integral forms that obeyed his condition. In turn, his condition turns out to be what Conway, Sloane, and in particular Gabriele Nebe refer to as "covering radius less than $\sqrt 2,$" see

and

One of Pete's relevant questions is

My own observations, confirmed by Pete with the Magma command CoveringRadius, are that the square of the covering radius is rational, and the denominator can always be taken to be a small power of 2 times the determinant of the lattice. Also the power of 2 seems to depend merely on the dimension.

So, that is the question, is the squared covering radius always rational with denominator a (dimension-dependent) power of 2 times the determinant of the lattice?

(note that it may be necessary to have the fraction not be in lowest terms to see the denominator as requested.)

(Also, Pete considers indefinite forms, other rings, etc. The covering radius stuff is for positive forms over the rational integers, which, except for the occasional annoying power of 2, are often called lattices. Not my fault).

-
@Will: thanks for following up on this. – Pete L. Clark Jul 4 '11 at 4:01
Hi, Pete. I believe I'm going to put the class number one problem as a question, those get more attention than comments. Keith Conrad did give me a solid improvement on the one idea I had, but that falls through. Meanwhile, Jonathan Hanke already has a list of all the "maximal" integral lattices of class number one. My desire is to get Jonathan's (eventually) complete list and, one way or another, find the covering radius for all (or all with small diagonal coefficients) – Will Jagy Jul 4 '11 at 4:09
@Will: okay, sounds good. You might want to refer to $\S 4.4$ of math.uga.edu/~pete/ADCFormsI.pdf. – Pete L. Clark Jul 4 '11 at 4:14

Yes, the square $R^2$ of the covering radius is always rational; and in small dimensions its denominator is always a factor of $2^{n+1} \Delta$ where $\Delta$ is the lattice discriminant, but possibly not for all $n$.

[I see that David Speyer just posted a very similar answer...]

A point $P$ at maximal distance $R$ from a lattice $L \subset {\bf R}^n$ is at distance $R$ from some $n+1$ lattice points $P_1, P_2,\ldots,P_{n+1}$ whose convex hull contains $P$ (proof: find $P_i$ by induction on $i$, using the fact that $P$ is a local maximum of the distance from a point to $L$). Fix some choice of the $P_i$. Then the simplex spanned by them has circumcenter $P$ and circumradius $r$. There's a formula (see below) for the circumradius of a simplex, generalizing the familiar $R=abc/4K$ of triangle geometry, of the form $R^2 = N/D$, where $N$ is a determinant formed from the squares of the side-lengths, and $D = 2^n (n! V)^2$ with $V$ being the volume of the simplex. Since $(n!V)^2$ is the covolume of the lattice $L' \subset L$ generated by the $n$ vectors $P_i-P_{n+1}$ ($i=1,\ldots,n$), this gives what you want — provided $L' = L$.

Now in small dimensions $L'$ is always all of $L$, but in higher dimensions I suspect there may be counterexamples — and if $[L:L']$ is odd then $L$, or a lattice sufficiently close to some large scaling of $L$, will be a counterexample to your conjecture. Note that in such a counterexample the covering radius $R'$ of $L'$ must exceed $R$, because the complement of $L$ in $L'$ is outside the union of translates of $L'$ by a radius-$R$ ball whereas $R'$ is the smallest radius of a ball whose translates by $L'$ cover ${\bf R}^n$.

As for the formula $R^2 = N/D$: it follows from the formula $(n! V)^2 = \pm \det M$ where $M$ is the symmetric matrix of order $n+2$ with 0's on the diagonal, 1's on the last row and column, and $(i,j)$ entry $|P_i-P_j|^2$ for $i,j \leq n+1$. Now apply this formula to the degenerate simplex in ${\bf R}^{n+1}$ formed by the $P_i$ together with $P$. This volume is zero. Let $M_+$ be the resulting matrix, of order $n+3$. Subtract $R^2$ times the bottom row from the $(n+2)$nd row, and then subtract $R^2$ times the last column from the next-to-ast column. This gives $\det M_+ = -2R^2 \det M - \det M_0$, where $M_0$ is the minor of $M$ obtained by deleting the last row and column. Now solve for $R^2$ and we're done.

For $n=2$, the determinant of $M_0$ has only two nonzero terms, both equal $(abc)^2$, and we recover $4KR=abc$ where $K$ is the area. For $n=3$ there's still a nice description of $\det M_0$: it's proportional to the square of the area of the tetrahedron's Ptolemy triangle! That is, of the triangle of side lengths $|P_1-P_2| |P_3 - P_4|$, $|P_1-P_3| |P_4-P_2|$, $|P_1-P_4| |P_2-P_3|$ that exists thanks to the Ptolemy inequality. It follows that $6VR$ is the area of that triangle. For $n\geq 4$ there doesn't seem to be such a simple description of $\det M_0$ except for its appearance in the formula for $R$.

-
Thanks, Noam. All examples are in dimension 10 or less. Also, all Pete's examples have class number one, and it is a result of George Leo Watson that this implies dimension no larger than 10. I have been searching for some time for an a priori proof of class number one, no luck. – Will Jagy Jul 4 '11 at 2:33
Oh, and the part about class number one refers to strict inequality, otherwise the Leech lattice would be included. I don't know the number of classes in the genus of the Leech lattice, however it is not one. – Will Jagy Jul 4 '11 at 3:30
The "classes in the genus of the Leech lattice" are the 24 Niemeier lattices, right? – Noam D. Elkies Jul 4 '11 at 4:07
Come to think of it, if $L = E_8$ then for each deep hole $L' = D_8$, so that's already a counterexample to $L'=L$ — though here $[L:L']=2$ so we can't get an extra odd factor in the denominator, and as it happens the covering radius is 1 so there's no denominator at all. [If we construct $E_8$ as the union of $D_8$ with its shift by $(\frac12,\frac12,\ldots,\frac12)$ then all deep holes are equivalent to $(1,0,0,\ldots,0)$.] What happens for the Leech lattice? I don't have a copy of SPLAG handy today... – Noam D. Elkies Jul 4 '11 at 19:48
I sent you an email, I'm holding a copy of the first edition of SPLAG. Let's see, they say the deep holes in the Leech lattice have a one-to-one correspondence with the Niemeier lattices, page 413. In Chapter 23 on the covering radius of the Leech lattice, Theorem 2 says there are 23 inequivalent deep holes in the Leech lattice, these correspond with the other 23 Niemeier lattices. – Will Jagy Jul 4 '11 at 20:55

It's rational. However, I am not sure whether or not the denominator is what you think it is.

Let $\Lambda \subset \mathbb{R}^n$ be your lattice.

The covering radius is the smallest $r$ such that every point of $\mathbb{R}^n$ is within $r$ from some lattice point. Let $w$ be a point whose closest distance to $\Lambda$ is exactly $r$. Let $S$ be the set of points of $\Lambda$ which are $r$ away from $w$.

Lemma: $S$ is not contained in any hyperplane.

Proof: Suppose, to the contrary, that $S$ is contained in the hyperplane $H$. Let $u$ be a normal vector to $H$. If $w$ is not in $H$, let $u$ point to the side of $H$ on which $w$ lies; if $w$ is in $H$, choose the sign of $u$ arbitrarily. Look at the point $w+\epsilon u$ for small positive $\epsilon$. It is more than $r$ away from every point of $S$. However, if $\epsilon$ is small enough, then it is also more than $r$ away from every point in $\Lambda \setminus S$. So $w+\epsilon u$ is not within $r$ of any point of $\Lambda$, contradicting the definition of $r$. QED

Since $S$ is not contained in a hyperplane, we can choose $n+1$ points of $S$ which do not lie in a hyperplane. Without loss of generality, let one of these points be $0$, and call the others $v_1$, $v_2$, ..., $v_n$. I will show that $r^2$ is rational, and its denominator divides $2^{n+1} \Delta$ where $\Delta$ is the determinant of the lattice generated by the $v_i$'s. However, it is not obvious to me that the lattice generated by the $v_i$ is always $\Lambda$. Moreover, I could imagine that it might happen that the $v_i$'s usually generate $\Lambda$, but every once in a very rare while they don't, which would explain why a numerical search wouldn't find this phenomenon. So I am not sure whether the denominator is exactly what you think it is.

Let's finish the proof. Since the $v_i$ form a basis for $\mathbb{R}^n$, let's write $w = \sum a_i v_i$.

Now, $w$ is equidistant from $0$ and from $v_i$, so $w$ lies on the hyperplane $\{ x: \langle v_i, x \rangle = |v_i|^2/2 \}$. In other words, $$\sum_j a_j \langle v_i, v_j \rangle = |v_i|^2/2 \quad (*)$$ For every $i$, $(*)$ gives a linear equation in the $a_i$. The right hand side is a half integer. The matrix $\left( \langle v_i, v_j \rangle \right)$ has determinant $\Delta$, and each entry of this matrix is a half integer. So the inverse matrix has entries whose denominators divide $2^{n-1} \Delta$, and we see that the denominators of the $a_i$ divide $2^n \Delta$.

Then $$r^2 = \langle w,w \rangle = \sum_{i,j} a_{i} a_{j} \langle v_i, v_j \rangle. \quad (**)$$ It is immediately obviously that this is rational.

To get the denominator bound, use $(*)$ to turn $(**)$ into $$\sum_i a_i |v_i|^2/2.$$ As we saw above, $a_i$ has denominator dividing $2^n \Delta$, and $|v_i|^2/2$ is a half integer. So the denominator of $r^2$ divides $2^{n+1} \Delta$, as I promised.

-
Noam Elkies has just posted an extremely similar answer which has $2^{n+1}$ where I had $4$. I'm not sure which of us has the correct power of $2$. – David Speyer Jul 4 '11 at 2:26
Thanks, David. Usually for conjectures I have a vast amount of numerical evidence, plus I have learned the value of being able to test "random" cases rather than hand-picked. In this case, I have under 100 quadratic forms which have a quite definite non-random property (Pete's). It did really jump out at me about the denominators, I wrote my own code for the task in C++ and watched as certain checks were performed. If true, the part about the denominators is very useful. Pete asked me how i did it, in turn I want to know how Magma does it... – Will Jagy Jul 4 '11 at 2:29
You beat me to this by a few minutes... And only because I included the connections with the formulas for the circumradius of a triangle and a tetrahedron :-) \\ $2^{n+1}$ vs. 4: could be we're both right but your argument gives a better bound. For $n=2$ I can reclaim a factor of 2 because $M_0$, being square of odd order, has even determinant. \\ Trivial typo: "immediately obviously" → "immediately obvious". Most likely there's at least one such typo in my own answer. \\ [Is there a way to force line breaks in comments here?] – Noam D. Elkies Jul 4 '11 at 2:30
I just found my error, $2^{n+1}$ is right. Forgot that the matrix entries $\langle v_i, v_j \rangle$ could be half integers, so the adjoint matrix can get denominators from that as well of from the determinant. Editing now. – David Speyer Jul 4 '11 at 2:34
Sadly, there is no way to force line breaks. And thanks for including the geometric discussion in your answer. – David Speyer Jul 4 '11 at 2:37