Verifying an example in the Geometry of Numbers and Quadratic Forms - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:37:03Z http://mathoverflow.net/feeds/question/40195 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40195/verifying-an-example-in-the-geometry-of-numbers-and-quadratic-forms Verifying an example in the Geometry of Numbers and Quadratic Forms Will Jagy 2010-09-27T19:12:08Z 2010-09-28T14:23:09Z <p>In answer to Pete L. Clark's question <a href="http://mathoverflow.net/questions/39510/" rel="nofollow">http://mathoverflow.net/questions/39510/</a> 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) &lt; 1.$$ </p> <p>[Edit: This is the definition for positive definite integral quadratic forms. --PLC]</p> <p>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.</p> <p>Could someone please try to prove that this example works (and the 6 variable one)? It seems likely that this lies in the field <a href="http://en.wikipedia.org/wiki/Geometry_of_numbers" rel="nofollow">http://en.wikipedia.org/wiki/Geometry_of_numbers</a> but who can say? </p> <p>$$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 &amp; \frac{1}{2} &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; \frac{1}{2}\\ \frac{1}{2} &amp; 1 &amp; \frac{1}{2} &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; \frac{1}{2} &amp; 1 &amp; \frac{1}{2} &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; \frac{1}{2} &amp; 1 &amp; \frac{1}{2} &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; \frac{1}{2} &amp; 1 &amp; \frac{1}{2} &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; \frac{1}{2} &amp; 1 &amp; \frac{1}{2} \\ \frac{1}{2} &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; \frac{1}{2} &amp; 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.</p> <p>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 &lt; 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.$ </p> http://mathoverflow.net/questions/40195/verifying-an-example-in-the-geometry-of-numbers-and-quadratic-forms/40276#40276 Answer by Franz Lemmermeyer for Verifying an example in the Geometry of Numbers and Quadratic Forms Franz Lemmermeyer 2010-09-28T07:29:51Z 2010-09-28T12:55:37Z <p>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$.</p> <p>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| &lt; \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?</p> http://mathoverflow.net/questions/40195/verifying-an-example-in-the-geometry-of-numbers-and-quadratic-forms/40321#40321 Answer by Bob Terrell for Verifying an example in the Geometry of Numbers and Quadratic Forms Bob Terrell 2010-09-28T14:23:09Z 2010-09-28T14:23:09Z <p>The answer to the last question in Franz Lemmermeyer's answer (so maybe this ought to be a comment?) is yes:</p> <p>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$.</p> <p>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$</p>