Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
I endorse this question. :) –  Pete L. Clark Sep 27 '10 at 20:06
add comment

2 Answers 2

up vote 5 down vote accepted

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?

share|improve this answer
    
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
add comment

The answer to the last question in Franz Lemmermeyer's answer (so maybe this ought to be a comment?) is yes:

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$

share|improve this answer
    
Thanks you, Bob. –  Will Jagy Sep 28 '10 at 18:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.