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

Question

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

http://www.math.rwth-aachen.de/~nebe/pl.html

and

http://www.math.rwth-aachen.de/~nebe/papers/CR.pdf

One of Pete's relevant questions is

Must a ring which admits a Euclidean quadratic form be Euclidean?

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).

Answer 1

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$.

Answer 2

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.