# Verifying an example in the Geometry of Numbers and Quadratic Forms

In answer to Pete L. Clark's question Must a ring which admits a Euclidean quadratic form be Euclidean? on Euclidean quadratic forms, I gave an example in seven variables, repeated below. Pete's Euclidean property is simply that for any point $\vec x \in \mathbf Q^7$ but $\vec x \notin \mathbf Z^7,$ we require that there be at least one $\vec y \in \mathbf Z^7$ such that $$q(\vec x - \vec y) < 1.$$

[Edit: This is the definition for positive definite integral quadratic forms. --PLC]

I think my answer works (and the easier 6 variable one), based on extensive computer calculations, and Pete has been too polite to express much doubt.

Could someone please try to prove that this example works (and the 6 variable one)? It seems likely that this lies in the field http://en.wikipedia.org/wiki/Geometry_of_numbers but who can say?

$$q( \vec x) = x_1^2+ x_1 x_2 + x_2^2 + x_2 x_3 + x_3^2 + x_3 x_4 + x_4^2 + x_4 x_5 + x_5^2 + x_5 x_6 + x_6^2 + x_6 x_7 + x_7^2 + x_7 x_1.$$ This has the Euclidean property, its worst behavior is either when all $x_i = \frac{1}{4}$ or when all $x_i = \frac{3}{4},$ with Euclidean minimum'' equal to $\frac{7}{8}.$ Notice that with $\vec x = \left( \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4} \right),$ the integer lattice points $\vec y$ such that $q( \vec x - \vec y)=\frac{7}{8}$ include $\vec y = \left( 0,0,0,0,0,0,0\right)$ and all seven cyclic permutations (including the identity) of $\vec y = \left( 0,1,0,1,0,1,0\right),$ another seven for $\vec y = \left( 1,0,0,0,0,0,0\right),$ another seven for $\vec y = \left( 1,0,1,0,0,0,0\right),$ finally seven for $\vec y = \left( 1,0,0,1,0,0,0\right),$ a total of 29 lattice points on the ellipsoid, of 128 in the standard unit 7-cube. The Gram matrix for the form is $$Q \; \; = \; \; \left( \begin{array}{ccccccc} 1 & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2}\\\ \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & 0 & 0 \\\ 0 & \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & 0 \\\ 0 & 0 & \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 \\\ 0 & 0 & 0 & \frac{1}{2} & 1 & \frac{1}{2} & 0 \\\ 0 & 0 & 0 & 0 & \frac{1}{2} & 1 & \frac{1}{2} \\\ \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & 1 \end{array} \right) ,$$ which has determinant $\frac{1}{32}$ and characteristic polynomial $$\left( \frac{1}{64} \right) \left(x - 2 \right) \left(8 x^3 - 20 x^2 + 12 x - 1 \right)^2.$$ So the ellipsoids described are not oblate spheroids, there is less symmetry than that.

EDIT. I think it wise to describe what I am completely certain about and what is unclear. What I did is make a cubic grid, where each variable takes on values $\frac{i}{M}$ for $0 \leq i < M.$ So that makes a grid with $M^7$ points. For each point $\vec r$ in the grid, I find the 128 different values of $q(\vec r - \vec y)$ for $\vec y \in \mathbf Z^7$ and all coordinates of $\vec y$ are either 0 or 1. For that point $\vec r,$ I take the smallest of the 128 values. Now, for every $M$ I have tried, and for every $\vec r$ in the grid, this best value out of 128 has never been larger than $\frac{7}{8}.$ Now, using the fact that for any $\vec x \in \mathbf Q^7$ that is not in the grid, there is some point $\vec r$ such that $| \vec r -\vec x | \leq \frac{1}{2 M \sqrt 7},$ I get that I can always find a $\vec y \in \mathbf Z^7$ such that $$g(x-y) \leq \frac{7}{8} + \frac{1}{7 M} + \frac{1}{14 M^2},$$ using Cauchy-Schwarz and the maximum eigenvalue of $Q$ being 2. Anyway, this does not show that the Euclidean minimum is really $\frac{7}{8},$ although I believe it is. What it does show is that the Euclidean minimum is less than 1, as soon as $M \geq 2.$

-
I endorse this question. :) –  Pete L. Clark Sep 27 '10 at 20:06

Consider the form $$Q(x) = 2q(x) = (x_1+x_2)^2 + (x_2+x_3)^2 + \ldots + (x_7+x_1)^2.$$ You have to show that it has Euclidean minimum $\frac74$ attained at $X_1 = x_1+x_2 = \frac12$, ..., $X_7 = x_7 + x_1 = \frac12$, but unfortunately not over the lattice ${\mathbb Z}^7$, where it would be trivial, but over a lattice of index $2$ defined by the condition $y_1 + y_2 + \ldots + y_7 \equiv 0 \bmod 2$. It is clear that $(\frac12, \ldots, \frac12)$ has Euclidean minimum $\frac 74$, and it remains to show that all other points in the fundamental domain of the lattice have a minimum at most $\frac74$.

This is not difficult to see: assume you have the point $(\frac12 + \delta, \frac12 + \varepsilon, ...)$ for small $\delta, \varepsilon \ge 0$. Subtracting the point $(1,1,0,\ldots, 0)$ you will get a point with coordinates $(-\frac12 + \delta, -\frac12 + \varepsilon, ...)$. Repeating this procedure you will eventually reach a point with $|X_2|, \ldots, |X_7| \le \frac12$. If $|X_1| \le\frac12$, we are done. If not, you can make $|X_1| < \frac12$ at the cost of making another coordinate $> \frac12$ in absolute values. If you think about this for a minute you will see that we can always reach a point of the form $$X = \Big(\frac12 + \delta_1, \frac12 - \delta_2, . . . , \frac12 - \delta_7\Big)$$ with $0 \le \delta_j \le \frac12$ and $\delta_1 \le \delta_i$ for all $i > 1$. It remains to show that $q(X) \le \frac74$, which is equivalent to $$\delta_1 - \delta_2 - \ldots - \delta_7 + \delta_1^2 + \ldots + \delta_7^2 \le 0.$$ Does this inequality hold?

-
This is very nice, Franz. The doubling $\pmod 1$ shows why the point with all coordinates $\frac{3}{4}$ and the one with all coordinates $\frac{1}{4}$ work the same way. –  Will Jagy Sep 28 '10 at 18:02
Since each $\delta_j^2\le\frac{1}{2}\delta_j$, you have $-\delta_j+\delta_j^2\le-\frac{1}{2}\delta_j\le-\frac{1}{2}\delta_1$.
Then $\delta_1-\delta_2-\cdots-\delta_7+\delta_1^2+\cdots+\delta_7^2 \le\delta_1+\delta_1^2-\frac{6}{2}\delta_1\le\frac{3-6}{2}\delta_1 \le0$