5
$\begingroup$

As Ben suggested in my earlier question on the subject, I looked at Artin's proof that $\left|\cdot\right|^2$ is a "size function" which makes $\mathbb Z [i]$ into a Euclidean domain. To quote page 398:

We divide the complex number b by a: $b=aw$, where $w=x+yi$ a complex number, not necessarily a Gauss integer. The we choose the nearest Gauss integer point $(m,n)$ to $(x,y)$, writing $x=m+x_0,y=n+y_0$, where m,n are integers and $x_0,y_0$ real numbers such that $-1/2\leq x_0,y_0<1/2$. Then $(m+ni)a$ is the required point of $Ra$. For, $\left|x_0 + y_0i\right|^2<1/2$ and $|b-(m+ni)a|^2=|a(x_0+y_0i)|^2<\frac{1}{2}|a|^2$.

I have two questions:

  1. I assume he's using the notation $\left|a+bi\right|=\sqrt{a^2 + b^2}$. If so, it seems like $\left|x_0 + y_0i\right|^2<1/2$ is not always true since $\left|(-1/2)+(-1/2)i\right|^2=1/2$
  2. He never uses the identity $i^2=-1$, so it seems like this proof could be expanded to all rings $\mathbb Z[x]/(x^2 + a)$, or indeed anything which has a vectorspace-like structure like $\mathbb Z^2$. But I remember hearing that $\mathbb Z[\sqrt{-5}]$ is not Euclidean - why does this proof fail for $x^2 = -5$?

EDIT: $\sqrt{-5}\approx 2.2i$ so we can write for example $3i \approx 1.3\sqrt{-5}$. By my understanding, $y_0=.3$ here and the norm $|0+.3|=0^2+.3^2$ is less than one. Furthermore, every $x_0,y_0$ is less than $1/2$, so this norm will always be less than 1, which is all we need.

Why doesn't this show that $\mathbb Z[\sqrt{-5}]$ is Euclidean?

  • 7
    For (1): The norm in number theory is different. For Gaussian integers it is $a^2+b^2$. If one took the square root, norm would be usually irrational, and people in number theory are very rational.2011-07-21
  • 2
    For(2): If you look at the ring $\mathbf{Z}[\sqrt{-5}]$, then the imaginary parts of the elements of the ring are integer multiples of $\sqrt5$ as opposed to (rational) integers as here. Therefore the `error' term $y_0$ may be as large as $\sqrt{5}/2>1$, and this approach to getting a Euclidean algorithm fails.2011-07-21
  • 2
    I looked at the actual passage! Artin is using $|x+yi|$ in its standard complex variable sense, and there is a typo as pointed out by the OP. There is no problem, we don't need $\lt 1/2$ anyway to push through the Gaussian version of the Division Algorithm, $\lt 1$ is good enough. But earlier comment still (mostly) stands.2011-07-21
  • 0
    @Jyrki: but isn't $y_0=y-\lfloor y \rfloor$ (or $\lceil y \rceil - y$) and hence always less than one?2011-07-21
  • 0
    @Xodarap: In that case you are trying to find a point of the form $m+in\sqrt{5}$ that is as close to $w=x+iy$ as possible. The error will be $y_0=y-\sqrt5\lfloor(y/\sqrt5)\rfloor$ or $y_0=\sqrt5 \lceil(y/\sqrt5)\rceil-y$. All depending whether the integer $n$ is below or above $y/\sqrt5$.2011-07-21
  • 0
    @Jyrki: As an example: $6i=(1.2)5i$. I thought $y_0=.2$ - you are saying $y_0 = (.2)5i$?2011-07-21
  • 0
    @Xodarap: No. If $w=6i$, then the closest element of the ring $\mathbf{Z}[\sqrt{-5}]$ is $3\sqrt5 i$, so $y_0=(3\sqrt{5}-6)$. You are no longer looking for the closest Gaussian integer.2011-07-21
  • 0
    @Xodarap: It is possible that we are normalizing things differently. I am looking at the usual distance from an arbitrary complex number $w$ to the closest point of the ring. Look at Paul's answer, too. His normalization along the imaginary axis (if you fix his typo and think in terms of $\sqrt{-5}$) is different from mine in the sense that he scales it differently. But he compensates for this difference by studying the correct norm $|a+b\sqrt{-5}|^2=a^2+5b^2$, so in the end Paul and I get the same results.2011-07-21
  • 0
    @Jyrki: could you look at my edit?2011-07-21
  • 0
    @Xodarap: $|x_0+y_0\sqrt{-5}|^2=x_0^2+5y_0^2$. If here $x_0=y_0=0.5$, then $x_0^2+5y_0^2=1.25>1$. See the answer by Paul Garrett.2011-07-21
  • 0
    @Jyrki: I'm defining the norm differently than Paul. Artin places no restrictions on the norm function, so it seems like this is a legitimate thing to do.2011-07-21
  • 1
    Without saying "because $\mathbf{Z}[\sqrt{-5}]$ does not have unique factorization" it seems like it would be very hard to show that there is no norm. If you just want to show that $N(a + b\sqrt{-5}) = a^2 + 5b^2$ is not a norm, I think we can do something for you.2011-07-21
  • 1
    @Xodarap: Artin does place one important restriction on the norm: the norm should be multiplicative. IOW for all complex numbers $w,z\in\mathbf{C}$ you should have $|zw|=|z|\cdot |w|$. This is used in the equation $|a(x_0+iy_0)|^2=|a|^2|x_0+iy_0|^2\le\frac12|a|^2$. You **MUST** use the norm $|x+y\sqrt{-5}|=x^2+5y^2$. Otherwise the norm is not multiplicative. I don't have access to the text, but whatever the 'size'-function is called, surely it must be multiplicative.2011-07-21
  • 1
    @Jyrki It doesn't seem like he requires it, at least in the first edition.2011-07-21
  • 0
    Jyrki, @Dylan: Thanks! I guess my question could've been phrased better but I think I understand now.2011-07-21
  • 0
    If we write $N(x+iy)$ instead of $|x+iy|^2$ for any which function we please, how do we deduce $$N(a(x_0+iy_0))=N(a)N(x_0+iy_0)\le \frac12 N(a)$$ without $N$ being multiplicative???? The equality here. That is a key to the argument, surely.2011-07-21
  • 0
    But sorry about contributing to the confusion. I should have asked for Xodarap's definition of $|\cdot|$ to start with, because that's were the differences were coming from.2011-07-21
  • 1
    @Xodarap: Looks like you're taken care of, but I'll add 2 things: 1) The geometry at the heart of Artin's proof: a unit square is completely covered by unit discs centered at its corners; the multiples of (a+bi) form a square lattice; every Gaussian integer is in one of the squares, so it is less than |a+bi| away from one of the corners, i.e. from a multiple of a+bi. On the other hand, if you put unit discs at the corners of a 1 by $\sqrt{5}$ rectangle, they leave a little patch in the middle uncovered, and it is precisely this patch that jams up the proof.2011-07-22
  • 0
    And 2) working through the rest of Artin Ch. 11 is really going to put this all in perspective. Esp. sections 6 and 7, but if you have time to work through the whole chapter you will feel like you understand all of this very deeply. (This was my experience.)2011-07-22
  • 0
    @Ben: Ah cool! "if you put unit discs at the corners of a 1 by $\sqrt{5}$ rectangle, they leave a little patch in the middle uncovered" - this is a very intuitive way of understanding it.2011-07-22
  • 0
    Related: https://math.stackexchange.com/questions/233582018-11-25

1 Answers 1

3

Whatever the normalizations, the requirement of "Euclidean" is that the remainder is strictly smaller than the divisor. Thus, in the highlighted paragraph above, the necessary conclusion is simply that the norm of the leftoever be strictly smaller than the divisor, not than half the size of the divisor.

In the case of $\mathbb Z[\sqrt{5}]$, the analogous leftover $a+b\sqrt{5}$ again has $|a|,|b|\le 1/2$, but the usual complex absolute value, squared or not, is $(1/2)^2+5(1/2)^2=6/4>1$. Taking a square root or squaring or not... does not affect the crucial issue of whether it's $<1$ or not.

Some examples of computations about Euclidean-ness of rings of alg integers are in my notes , and many other places on the internet, I'm sure.

Edit: in response to further query... in $\mathbb Z[\sqrt{-5}]$, the leftovers are $a+b\sqrt{-5}$ with $|a|,|b|\le 1/2$. The norm (-squared) is $a^2+5b^2\le (1/4)+5(1/4)=6/4>1$. In the "EDIT" in the query, yes, there is a particular example where the norm is $<1$. Ok, but that doesn't imply that all leftovers are $<1$. Yes, every $x_0,y_0$ are at most $1/2$ in size, but that's without the "5"! $|x_0+y_0\sqrt{-5}|^2=x_0^2+5y_0^2$.

  • 0
    Could you look at my edit? I still don't think I understand.2011-07-21
  • 0
    Nevermind, I think the problem was that I didn't realize $|ab|$ must be $|a||b|$.2011-07-21
  • 0
    Ah. Indeed! ...2011-07-21