We know from Rolletschek's work that the Euclidean algorithm of $\mathbb{Z}[i]$ is polynomial. Indeed, let $n$ be the maximum number of steps in the Euclidean algorithm applied to $u,v \in\mathbb{Z}[i]$ such that $\mid v\mid \leq\mid u\mid \leq N, N\in\mathbb{N}$. We have $n=1.0526\log_{2}(N)+M$, where $-1\leq M\leq 2$.

My question is if there is any Euclidean real quadratic ring for which the Euclidean algorithm is polynomial?

  • $\begingroup$ Is there any Euclidean ring for which the Euclidean algorithm is NOT polynomial? $\endgroup$ Mar 19 '16 at 3:13

$\mathbb{Z}[\sqrt{2}]$ is such a ring.

First, let us recall a simple algorithm that suffices to give a smaller remainder in this ring:

If $a,b,c,d \in \mathbb{Z}$, then $\frac{a+b\sqrt{2}}{c+d\sqrt{2}} \in \mathbb{Q}(\sqrt{2})$. Write $\frac{a+b\sqrt{2}}{c+d\sqrt{2}} = (n_{1}+r_{1}) + (n_{2}+r_{2})\sqrt{2}$, where $n_{1}, n_{2} \in \mathbb{Z}$, $r_{1}, r_{2} \in \mathbb{Q}$, and $|r_{1}|, |r_{2}| \leq \frac{1}{2}$. Then $|r_{1}^{2}-2r_{2}^{2}| \leq |r_{1}|^{2} + 2|r_{2}|^{2} \leq \frac{3}{4}$, so it is always possible to divide in $\mathbb{Z}(\sqrt{2})$ and get a remainder whose norm is at most $\frac{3}{4}$ times the norm of the element you divided by.

Then such a bound for the number of divisions (starting with dividing $u$ by $v$) is given by $\frac{\log_{2} |N(v)|}{2-\log_{2}3}$, where $N$ denotes the $\mathbb{Z}[\sqrt{2}]$ norm. If you want a bound in terms of another norm, it's probably not hard to relate it to this bound.

  • $\begingroup$ In fact, since $-2r_{2}^{2} \leq 0 \leq r_{1}^{2}$, we have $|r_{1}^{2}-2r_{2}^{2}| \leq \max(r_{1}^{2}, 2r_{2}^{2}) \leq \frac{1}{2}$. This enables the bound to be improved to $\log_{2} |N(v)|$. $\endgroup$ Mar 17 '16 at 17:25
  • $\begingroup$ excuse-me for the dumb question, and in other euclidean rings, is the $gcd$ much harder to compute, or much simpler ? $\endgroup$
    – reuns
    Mar 17 '16 at 18:49
  • $\begingroup$ Thank you David Harden, could you give me the reference for this result? $\endgroup$
    – M.Souf
    Mar 17 '16 at 19:24
  • $\begingroup$ This should have much sharper results: H. Davenport, Indefinite Binary Quadratic Forms, and Euclid's Algorithm in Real Quadratic Fields, Proc. London Math. Soc., (1951) s2-53 (1): 65-82 $\endgroup$ Mar 18 '16 at 18:26
  • $\begingroup$ Davenport's paper contains especially the proof that there are finitely many Norm-Euclidean quadratic real rings, he didn't prove more than that I think. In fact, this question seems to be open when we look at the end of Rolletschek's paper (On the Number of Divisions of the Euclidean Algorithm Applied to Gaussian Integers) which is published 35 years after the Davenport's one. $\endgroup$
    – M.Souf
    Mar 18 '16 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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