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

The question is in the title, but employs some private terminology, so I had better explain.

Let $R$ be an integral domain with fraction field $K$, and write $R^{\bullet}$ for $R \setminus \{0\}$. For my purposes here, a norm on $R$ will be a function $| \ |: R^{\bullet} \rightarrow \mathbb{Z}^+$ such that for all $x,y \in R^{\bullet}$, $|xy| = |x||y|$ and $|x| = 1$ iff $x \in R^{\times}$. Also put $|0| = 0$.

[Edit: I forgot to mention that the norm map extends uniquely to a group homomorphism $K^{\bullet} \rightarrow \mathbb{Q}^{> 0}$.]

The norm is Euclidean if for all $x \in K \setminus R$, there exists $y \in R$ such that $|x-y| < 1$.

Now let $q(x) = q(x_1,\ldots,x_n)$ be a (nondegenerate) quadratic form over $R$, which I mean in the relatively naive sense of just an element $R[x_1,\ldots,x_n]$ which is homogeneous of degree $2$. Supposing that a norm $| \ |$ on $R$ has been fixed, I say that the quadratic form $q$ is Euclidean if for all $x \in K^n \setminus R^n$, there exists $y \in R^n$ such that $0 < |q(x-y)| < 1$.

(If $q$ is anistropic, then $x \in K^n \setminus R^n$, $y \in R^n$ implies that $x-y \neq 0$, so $|q(x-y)| \neq 0$, and the condition simplifies to $|q(x-y)| < 1$.)

As an example, the sum of $n$ squares form is Euclidean over $\mathbb{Z}$ iff $1 \leq n \leq 3$.

It is easy to see that the ring $R$ (with its fixed norm) is Euclidean iff the quadratic form $q(x) = x^2$ is Euclidean (iff the quadratic form $q(x,y) = xy$ is Euclidean), so the concept of a Euclidean quadratic form is indeed some kind of generalization of that of a Euclidean ring.

Conversely, the following is an obvious question that I have not been able to answer.

Suppose that a normed ring $R$ admits some Euclidean quadratic form $q$. Is $R$ then necessarily a Euclidean domain? In other words, can there be any Euclidean quadratic forms if $q(x) = x^2$ is not Euclidean?

If the answer happens to be "no", I would of course like to know more: can this happen with an anisotropic form $q$? What can one say about a ring $R$ which admits a Euclidean quadratic form?

I have some suspicions that a domain which admits a Euclidean quadratic form is at least a PID. Indeed, let $q$ be a quadratic form over $R$. By an $R$-linear change of variables we may write it as $a_1 x_1^2 + \sum_{j=2}^n a_{1j} x_1 x_j + \sum_{i=2}^n \sum_{j=1}^n a_{ij} x_i x_j$ with $a_1 \neq 0$. Then if I take my vector $x$ to be $(x_1,0,\ldots,0)$ for $x_1 \in K \setminus R$, then the Euclidean condition implies the following: there exist $y_1,z \in R$ such that $|a(x_1-y_1)^2 - z| < 1$. This is reminiscent of the Dedekind-Hasse property for a norm which is known to imply that $R$ is a PID. In fact, it is much stronger in that the $a \in R$ is fixed (and the $z$ is not arbitrary either). Unfortunately in place of an arbitrary element $x$ of $K$ we have a certain square, so this does not match up with the Dedekind-Hasse criterion...but it seems to me somewhat unlikely that a domain which is not a PID would satisfy it.

For more information on Euclidean forms, please feel free to consult

Added: a new draft which takes into account comments of J. Hanke and F. Lemmermeyer is available at

I warn that the new Section 2.1 showing that (primitive) binary Euclidean forms correspond to Euclidean ideal classes in quadratic orders in the sense of Lenstra -- as pointed out by Franz Lemmermeyer in his answer -- is rather miserably written at the moment, but at least it's there.

-

Following Pete's request, I give the following as a second answer.

Take $R = {\mathbb Z}[\sqrt{34}]$ and $q(x,y) = x^2 - (3+\sqrt{34})xy+2y^2$; observe that the discriminant of $q$ is the fundamental unit $\varepsilon = 35 + 6 \sqrt{34}$ of $R$, and that its square root generates $L = K(\sqrt{2})$ since $2\varepsilon = (6+\sqrt{34})^2$. Then q is Euclidean over $R$ since the ring of integers in $L = K(\sqrt{2})$ is generated over $R$ by the roots of $q$, and since $L$ is Euclidean by results of J.-P. Cerri (see Simachew's A Survey On Euclidean Number Fields). But $R$ is not principal ($L/K$ is an unramified quadratic extensions), so the answer to your question, if I am right, is negative.

-
@Franz: I think in the definition of $q(x,y)$, you want the coefficient of $y^2$ to be $2$. The rest of the construction checks out so far. You seem to be using a mapping from quadratic orders to quadratic forms in a more general setting than I laid out in the paper: here the ground ring $R$ is not a PID. I think this is okay though so long as $S$ (here, the ring of integers of $K$) is a free $R$-module, which is the case here, since a discriminant calculation shows that an $R$-basis is given by $1$, $Z$, where $Z$ is a root of $q(x,1)$. Thanks again! – Pete L. Clark Sep 27 '10 at 4:48
@Franz, cont'd: with your permission, I will include this example in my paper. Your contributions here have reached the point where I am pleased to offer you coauthorship, should you want it: please contact me by email if you are interested. – Pete L. Clark Sep 27 '10 at 4:50
P.S.: Suppose that $R$ is the ring of integers of a number field (with its canonical norm) and admits an anisotropic binary Euclidean quadratic form. Do you (or anyone) have an opinion on whether the class number of $R$ can be larger than $2$? – Pete L. Clark Sep 27 '10 at 4:55
@Pete: corrected, thanks! – Franz Lemmermeyer Sep 28 '10 at 13:24

This is a comment on the manuscript rather than an answer to your question. When I read that ${\mathbb Z}$-Euclidean principal binary quadratic forms correspond to norm-Euclidean quadratic orders, my immediate reaction was the guess that the non-principal forms must correspond to Lenstra's Euclidean ideal classes. This is in fact true, as a simple calculation shows. The nontrivial ideal class in $K = {\mathbb Q}(\sqrt{-5})$ is generated by the prime ideal ${\mathfrak a} = (2,1+\sqrt{-5})$. By definition, this class is Euclidean if for every $\xi \in K$ there is an $\eta \in {\mathfrak a}$ such that $N(\xi - \eta) < N{\mathfrak a} = 2$. The identitiy $2(2x^2 + 2xy + 3y^2) = (2x+y)^2 + 5y^2$ then shows that this is equivalent to the form $2x^2 + 2xy + 3y^2$ being a Euclidean quadratic form over ${\mathbb Z}$. Thus it seems that this form is missing from Houriet's list, and I believe that this is the only form missing.

The known cases of Euclidean ideal classes for real quadratic fields (disc $K = 40, 60, 85$) show that the answer to problem 2 is negative: not every primitive Euclidean form represents $1$; one example is given by $2x^2 - 5y^2$, the nonprincipal form with discriminant $40$.

This does not answer your actual question, but perhaps it shows that one has to be very careful with making conjectures that seem to be plausible in this area.

Edit. Let $R$ be the ring of integers in a number field $K$, and let $S = R[i]$ denote a subring of the ring of integers in $L = K(i)$. I guess it is easy to see that the form $x^2 + y^2$ is Euclidean over $R$ (here and below: with respect to the absolute value of the norm) if and only if $S$ is Euclidean. But $disc\ S = \pm 4 (disc\ R)^2$ shows that if $S$ has class number $1$, then so does $R$ (because the UFD $S$ necessarily is the full ring of integers, so $disc\ L = \pm 4 (disc\ K)^2$). This shows that if $x^2 + y^2$ is Euclidean over $R$, then $R$ is a PID. Something similar clearly goes through for any binary quadratic form over the integers.

The fact that the proof of this special case already uses class field theory indicates that one should not expect a 3-line proof of the general claim that if $R$ admits a Euclidean quadratic form, then $R$ is a PID.

-
Thanks very much, Franz. You've given me a lot to think about. (Note to everyone else: Franz's answer addresses other issues in my manuscript, which are perhaps more natural/important than this question. Nevertheless, this question remains open.) – Pete L. Clark Sep 22 '10 at 17:52

In an odd number of variables it is legitimate to add a final product term and make the polynomial invariant under cyclic permutations, as in seven variables and $$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.

For six or fewer variables we can use one of the easiest constructions, include all mixed terms so that the Gram matrix becomes $$P_6 \; \; = \; \; \left( \begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2}\\\ \frac{1}{2} & 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\\ \frac{1}{2} & \frac{1}{2} & 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 1 & \frac{1}{2} & \frac{1}{2} \\\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 1 & \frac{1}{2} \\\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 1 \end{array} \right) .$$ Then the worst $\vec x$ is either $$\vec x = \left( \frac{3}{7}, \frac{3}{7}, \frac{3}{7} , \frac{3}{7}, \frac{3}{7}, \frac{3}{7} \right)$$ or $$\vec x = \left( \frac{4}{7}, \frac{4}{7}, \frac{4}{7} , \frac{4}{7}, \frac{4}{7}, \frac{4}{7} \right)$$ with Euclidean minimum'' $\frac{6}{7}.$

This construction is much easier to figure out. In dimension $n$ we have determinant $\frac{n +1}{2^n}$ and characteristic polynomial $$\left( \frac{1}{2^n} \right) \left(2 x - (n+1) \right) \left(2 x - 1 \right)^{n-1}.$$ For even $n$ the worst $\vec x$ has either all entries $\frac{n}{2(n + 1)}$ or $\frac{n + 2}{2(n + 1)}$ with a Euclidean minimum of $\frac{n^2 + 2 n}{8 (n+1)}.$ For odd $n$ the worst $\vec x$ has all entries $\frac{1}{2}$ with a Euclidean minimum of $\frac{n+1}{8}.$

-
@Will: this is very interesting, but I don't completely understand how you're computing the Euclidean minima here (nor do I understand how to compute this in general). I'll email you soon for further information. – Pete L. Clark Sep 27 '10 at 4:53