Show $\mathbb{Z}[\sqrt{6}]$ is a Euclidean domain

I'm attempting to modify the proof the $\mathbb{Z}[\sqrt{2}]$ is a Euclidean domain to prove a similar result for $\mathbb{Z}[\sqrt{6}]$. The idea is to prove that $\mathbb{Q}[\sqrt{6}]$ is Euclidean which will then give the result for $\mathbb{Z}[\sqrt{6}]$. According to Dummit and Foote's Abstract Algebra this should have norm $d(a+b\sqrt{6})=|a^2-6b^2|$. The result for $\mathbb{Z}[\sqrt{2}]$ relies on the fact that for any element $x$ in $\mathbb{Q}[\sqrt{2}]$ there is an element $x'$ in $\mathbb{Z}[\sqrt{2}]$ with $d(x-x')<1$, which is then used to show that for $x=qy+r$ we have $$ d(r)=d(x-qy)=d\left(y\left(\frac{x}{y}-q\right)\right)=d(y)d\left(\frac{x}{y}-q\right)<d(y) $$ But in this case, I'm having a hard time showing that we can find an element with $d(x-x')<1$ for $x\in\mathbb{Q}[\sqrt{6}], x'\in\mathbb{Z}[\sqrt{6}]$. Consider $x=a+b\sqrt{6}\in\mathbb{Q}[\sqrt{6}]$. The furthest this element can be away from any $x'=a'+b'\sqrt{6}\in\mathbb{Z}[\sqrt{6}]$ is when $|a-a'|=\frac{1}{2}=|b-b'| \Rightarrow$ $$ d(x-x')=\left|\left(\frac{1}{2}\right)^2-6\left(\frac{1}{2}\right)^2\right|=\frac{5}{4}>1 $$ What can I do to get around this issue?

Solution 1:

Alright, this is from the viewpoint of what is called "covering radius" for positive quadratic forms. You have a quadratic form $f(x,y) = x^2 - 6 y^2.$ Now, with any real point $(a,b)$ in the plane, you want to find an integer point $(m,n)$ such that $$|f(a-m, b-n)| < 1. $$

Now, what is the set, centered around $(0,0)$ with $| x^2 - 6 y^2| < 1?$ It is a strange starfish shape with four arms, all along lines of slope $\pm \frac{1}{\sqrt 6}.$ The starfish "centered at" some integer point $(m,n)$ is $$ |(x -m)^2 - 6 (y - n)^2 | < 1. $$

All that is needed to show your inequality is that a finite set of such starfish covers the ordinary unit square with corners at $(0,0),(1,0),(1,1),(0,1).$

Well, the square $0 \leq x \leq 1, \; \; 0 \leq y \leq 1 $ is covered by eight starfish centered at $$ (0,0),(0,1), (1,0),(1,1), (-1,0),(-1,1),(2,0),(2,1). $$ The four starfish centered at the corners of the square itself cover all except a funny curvy diamond shape around $(\frac{1}{2}, \frac{1}{2} ),$ the vertices of the diamond being $$ \left(\frac{1}{2}, \frac{1}{2} \sqrt{\frac{5}{6}} \right), \; \left(\frac{1}{2}, 1 - \frac{1}{2} \sqrt{\frac{5}{6}} \right), \; \left(\frac{1}{\sqrt2}, \frac{1}{2} \right), \; \left( 1 -\frac{1}{\sqrt2}, \frac{1}{2} \right). $$ Next, out of the four remaining squares, the (open) starfish centered at $(-1,0)$ covers the entire closed rectangle $$ \frac{1}{5} \leq x \leq \frac{1}{2}, \; \; \frac{1}{2} \leq y \leq \frac{3}{5}, $$ so you can see that the four final starfish cover the closed rectangle $$ \frac{1}{5} \leq x \leq \frac{4}{5}, \; \; \frac{2}{5} \leq y \leq \frac{3}{5}, $$ thus entirely covering the missing diamond shape.

Earlier I had a solution with $20$ points, this is easier. Still, I suggest you have a computer draw the intersections of these sets with the square I indicate. I did this with a calculator and some graph paper, but I have special eyes.

September 2016: by computer, a bit much. Maybe if I show just the first four starfish, the central diamond that is not yet covered should be more clear

Note that the four boundary curves of the starfish centered at the integer point $(m,n)$ can be parametrized by a variable $t$ as $$ \left( m + \cosh t, \; n + \frac{ \;\sinh t \;}{\sqrt 6} \right), $$ $$ \left( m - \cosh t, \; n + \frac{ \;\sinh t \;}{\sqrt 6} \right), $$ $$ \left( m + \sinh t, \; n + \frac{ \;\cosh t \;}{\sqrt 6} \right), $$ $$ \left( m + \sinh t, \; n - \frac{ \;\cosh t \;}{\sqrt 6} \right). $$

EDITTT: this was first proved by Perron in 1932, with a better method by Oppenheim in 1934. See page 11 in survey.pdf at LEMMERMEYER

Solution 2:

Note that if there is $x'$ in your lattice such that $|a-a'|=\frac12 = |b-b'|$, then there is also another point $x''$ in the lattice such that $|b-b''|=\frac12$ and $|a-a''| = \frac32$. And then $d(x-x'')$ is...

As you see, to get a point in the lattice close to your given $x$, the trick is not to minimise $|a-a'|^2$ and $|b-b'|^2$ separately, but to minimise a suitable weighted difference. Now if you have found a lattice point such that $6|b-b'|^2 <1$, then what you did works just fine, right? If not, then as you have noted, you can find a point such that $1\leq 6|b-b'|^2 \leq \frac64=\frac 32$. Then how do you choose $a$? The first paragraph should give you an idea.

Solution 3:

Decades after leaving college, I had a chance to audit an introductory course in abstract algebra. I find the subject very interesting. But I am not a proper maths student by any stretch of imagination. Please go easy on someone who had ten weeks' learning on the subject. You mathematicians will certainly find my journey way too verbose, but this is a possible thought process of a newbie and a non-mathematician. It might help you to understand and to have some compassion on students who are struggling badly.

Engineers are visual thinkers. Sketches help me a lot. Allow me to recap. An integral domain is said to be a Euclidean domain if there are a well defined norm $N(a) \leq N(ab)$ and a division algorithm $a=qb+r$ such that $N(r)<N(b)$. Just to cover a few definitions. Such division algorithm works in a Euclidean domain $R$ for all $a,b \in R, b \ne 0$, there are a quotient and a reminder $q,r \in R$. For elements in a quadratic integer ring, $a \in R = \{x+y \sqrt{d}:x,y \in \mathbb{Z} \}$ with $d$ square free, a common choice of norm is $N:R \setminus \{0\} \rightarrow \mathbb{Z}_{\geq 0}$ by setting $a \mapsto |x^2-dy^2|$.

As Chris had suggested, to show $\mathbb{Z}[\sqrt{d}]$ a Euclidean domain, direct application of Pythagorean theorem works only for $\mathbb{Z}[\sqrt{-2}], \mathbb{Z}[\sqrt{-1}], \mathbb{Z}[\sqrt{2}]$ and $\mathbb{Z}[\sqrt{3}]$. In the previous statement, discriminant $d \in \mathbb{Z} \setminus \{ 0,1 \}$ is square-free such that it has no repeated prime factors. Equivalently, if $p \in \mathbb{Z}$ and $p^2|d$, then $p^2 = 1$.

Let $\mathbb{Z}[\sqrt{3}]=\{s+t\sqrt{3}: s,t \in \mathbb{Z}\}$ and $\mathbb{Q}[\sqrt{3}]=\{s+t\sqrt{3}: s,t \in \mathbb{Q}\}$. Suppose the nearest quadratic integer in $\mathbb{Z}[\sqrt{3}] \subset \mathbb{Q}[\sqrt{3}]$ from point $a/b \in \mathbb{Q}[\sqrt{3}]$ is point $q=m+n \sqrt{3}$ with $m,n \in \mathbb{Z}$. The horizontal and vertical components of the displacement $r/b=a/b-q$ are $x,y \in \mathbb{Q}$ where $|x| \leq \frac{1}{2}$ and $|y| \leq \frac{1}{2}$. Therefore, the maximum possible value of $N(r/b)=N(x+y\sqrt{3})=|x^2-3y^2| \leq \frac{3}{4} < 1$ and we are done. Note that division algorithm does not insist on uniqueness. If a point $a/b$ sits right at the boundary, there could be be more than one, at most four, points which are the "nearest". An example in $\mathbb{Z}$ is $\frac{7}{2}=3+\frac{1}{2}=4-\frac{1}{2}$.

In $\mathbb{Z}[\sqrt{-1}]$, the norm is simply the square of the usual Euclidean distance between points $q$ and $a/b$, which measures what consider to be the nearest Gaussian integer in this case. But the analogue of physical distances fails as $d$ increases.

Hence, the same approach fails to show $\mathbb{Z}[\sqrt{6}]$ is a Euclidean domain, as s/he had pointed out that $N(r/b)=N(x+y\sqrt{6})=|x^2-6y^2| \leq \frac{3}{2} \nless 1$.

Given that $0 \leq x^2 \leq \frac{1}{4}$, I follow Will Jagy's suggestion and split $0 \leq 6y^2 \leq \frac{3}{2}$ into four cases. It essentially considers two more lattice points as possible quotients $q', q''$, in additional to $q$, to the division algorithm for different values of $y$. I had additional inspiration from math_explorer https://artofproblemsolving.com/community/c1285h1036927. Note that the magic numbers $1$ and $\frac{5}{4}$ were arrived backwards. They will be shown in the cases. In order to make my life easier, I will consider only positive values of $x$ with $0 \leq x \leq \frac{1}{2}$, while allowing both positive and negative values for $y$. If $x$ were negative, similar arguments as the follows apply by switching cases 2 and 3.

Case 1: $0 \leq 6y^2 < 1$. Point $q$ has the coordinates $(m,n)$ and $0 \leq x^2 \leq \frac{1}{4}$ as shown earlier. The maximum possible difference occurs when $x^2=0$ and $6y^2=1^-$. Therefore $|x^2-6y^2|<1$ for all $x,y$ and we are done.

Case 2: $1 \leq 6y^2 < \frac{5}{4}$. Now we consider another lattice point to the right, says point $q'=(m+1,n)$. Using this as the new datum for point $a/b$, the horizontal component is now $-1+x$. Therefore, $\frac{1}{4} \leq (1-x)^2 \leq 1$. The maximum possible difference occurs when $(1-x)^2=\frac{1}{4}$ and $6y^2 = \frac{5}{4}^-$. Therefore $|(1-x)^2-6y^2|<1$ for all $x,y$ and we are done.

Case 3: $\frac{5}{4} < 6y^2 \leq \frac{3}{2}$. Now we consider yet another lattice point to the left, says point $q''=(m-1,n)$. Using this as the new datum for point $a/b$, the horizontal component is now $1+x$. Therefore, $1 \leq (1+x)^2 \leq \frac{9}{4}$. The maximum possible different occurs when $(1+x)^2=\frac{9}{4}$ and $6y^2 = \frac{5}{4}^+$. Therefore $|(1+x)^2-6y^2|<1$ for all $x,y$ and we are done.

Case 4: $6y^2 = \frac{5}{4} \implies y=\sqrt{\frac{5}{24}} \notin \mathbb{Q}$, therefore we can ignore this case.

Additional note for Case 3. At $6y^2 = \frac{3}{2}$, it has a comfortable margin from $(1+x)^2=1$ where $|1-\frac{3}{2}|=\frac{1}{2}<1$. In fact, this approach works for $\mathbb{Z}[\sqrt{7}]$ too, since $|1-\frac{7}{4}|=\frac{3}{4}<1$. However, this approach fails for $\mathbb{Z}[\sqrt{11}]$. Gerry Myerson $\mathbb{Z}[\sqrt{11}]$ is norm-euclidean pointed out that Oppenheim (1934) had a solution by considering more nearby lattice points as candidate point $q$. Now, what I will need to do is to make an attempt on $\mathbb{Z}[\sqrt{19}]$.

Links to bigger images:

Hasse diagram from rng to ED https://i.stack.imgur.com/jUcJX.png

$\mathbb{Z}[\sqrt{3}]$ https://i.stack.imgur.com/q4cli.png

$\mathbb{Z}[\sqrt{6}]$ https://i.stack.imgur.com/9QZuV.png

$q=(m,n)$ https://i.stack.imgur.com/X7WyX.png

$q'=(m+1,n)$ https://i.stack.imgur.com/zy8wL.png

$q''=(m-1,n)$ https://i.stack.imgur.com/Vipwd.png