I feel like this question has been asked here before, but I'm not finding it.

In an imaginary quadratic integer domain, it is very easy to round algebraic numbers to algebraic integers. For example, there are four choices for rounding $$\frac{1}{2} + \frac{\sqrt{-5}}{2},$$ three of which are suitable for attempting the Euclidean GCD algorithm. Likewise for $$\frac{7}{2} + \sqrt{-3}.$$

But in real quadratic integer domains, the possibilities seem endless. For example, what do you make of $$\frac{7}{2} + \sqrt{3}?$$ It's approximately $5.232$, so it seems logical to try $5$ and $6$ as rounds. But given an arbitrary integer $a$, we could probably always be able to choose an integer $b$ such that $q = a + b \sqrt{3}$ is within half a unit interval of $5.232$. How do you choose the right number $q$? Or is a choice impossible if you don't know the dividend and divisor?

EDIT: To clarify, this is not about what the integers of a given $\mathbb{Q}(\sqrt{d})$ are, I already know that. Nor is it about whether the Euclidean algorithm even works in such a domain.

This is about how to divide one number in $\mathbb{Q}(\sqrt{d})$ by another in that same domain, and, when $d$ is positive and the division is not an algebraic integer, how to choose one algebraic integer to round it to, from among seemingly infinitely many choices.

If, for whatever reason, that algebraic integer turns out to be unsuitable, how then to choose another? And how to know when to give up? These questions are very simple when $d$ is negative and I can answer them. But when $d$ is positive, I really don't know what to do.

  • $\begingroup$ Does this MSE link help math.stackexchange.com/questions/58561/norm-euclidean-rings? $\endgroup$ – Rob Arthan Jun 11 at 21:47
  • 4
    $\begingroup$ @Rob As someone who answered the question you're linking, I have to say that I seriously doubt it helps Bob in any way. For example, calculate $\gcd(7 + 2 \sqrt 3, 2)$. A look at norms readily tells us the answer is 1. But since Bob already knows this is a Euclidean domain, he seems to want to go through the steps of the Euclidean algorithm. Dividing the norm 37 number by the norm 4 number, he gets 5.23205080..., which he rounds to 5. Then $7 + 2 \sqrt 3 = 2 \times 5 + (-3 + 2 \sqrt 3)$. But $N(-3 + 2 \sqrt 3) = -3$. Huh, actually not bad. Nearest rational integer won't always work, though. $\endgroup$ – Robert Soupe Jun 12 at 15:07
  • 2
    $\begingroup$ @RobertSoupe The pair I was actually looking at was $(13 + 9 \sqrt{3}, 2 + 2 \sqrt{3})$. Then $13 + 9 \sqrt{3} = (10 + 10 \sqrt{3}) + (3 + 9 \sqrt{3})$, so clearly $5$ is not an appropriate rounding of $7/2 + sqrt{3}$. $\endgroup$ – Bob Happ Jun 12 at 21:36
  • 2
    $\begingroup$ Actually, $13 + 9 \sqrt 3 = 10 + 10 \sqrt 3 + 3 - \sqrt 3$, so the remainder actually has a norm of 6, not $-234$. But I'm still sure there is an example in this ring where the nearest integer fails to produce a suitable remainder. $\endgroup$ – Robert Soupe Jun 13 at 4:35
  • 1
    $\begingroup$ In your last paragraph, you say "If, for whatever reason, that algebraic integer turns out to be unsuitable", you mean unsuitable for what ? $\endgroup$ – Ewan Delanoy Jun 22 at 11:07

In $\mathbb{Q}[\sqrt{3}]$ the correct approximation is the following:

For $a+b\sqrt{3}\in\mathbb{Q}[\sqrt{3}]$ choose $e,f\in\mathbb{Z}$ such that $|a-e|\le \frac 12$ and $|b-f|\le \frac 12$. Then $$ N((a+b\sqrt{3})-(e+f\sqrt{3}))=N((a-e)+(b-f)\sqrt{3})=|(a-e)^2-3(b-f)^2|\le \frac 34. $$ The function $N$ is defined on $\mathbb{Q}[\sqrt{3}]$ by $$ N(a+b\sqrt{3})=|a^2-3b^2|, $$ and is the correct way to measure "distance" in $\mathbb{Q}[\sqrt{3}]$. This function is multiplicative and maps $\mathbb{Z}[\sqrt{3}]$ to $\mathbb{Z}$. The units in $\mathbb{Z}[\sqrt{3}]$ are precisely the elements $x\in \mathbb{Z}[\sqrt{3}]$ such that $N(x)=1$. This function is also used in order to prove that $\mathbb{Z}[\sqrt{3}]$ is an Euclidean Domain. For other quadratic extensions this Norm function can also be defined, but the approximation may be not so good (in $\mathbb{Q}[\sqrt{d}]$ this yields an approximation up to $\frac d4$).

Given $a+b\sqrt{3}$, one can even choose $(e,f)\in\mathbb{Z}^2$, such that $|a-e|\le 1$ and $|b-f|\le 1$ and $N((a+b\sqrt{3})-(e+f\sqrt{3}))\le \frac 12$.

On the other hand, the chosen element satisfies $|(a+b\sqrt{3})-(e+f\sqrt{3})|\le \frac{1+\sqrt{3}}{2}\approx 1.36$, and although one can always choose $e\in\mathbb{Z}$ such that $|(a+b\sqrt{3})-e|\le\frac 12$, in that case one cannot control the size of $N((a+b\sqrt{3})-e)$. For example, if we approximate $$ -\frac 34+\frac{19}4\sqrt{3}\approx 7.5 $$ by $e=7$ or $e=8$, then we obtain $$ N((a+b\sqrt{3})-e)=N\left(-\frac{31}4+\frac{19}4\sqrt{3}\right)= \left|\left(\frac{31}4\right)^2-3\left(\frac{19}4\right)^2\right| =7.625 $$ or $$ N((a+b\sqrt{3})-e)=N\left(-\frac{35}4+\frac{19}4\sqrt{3}\right)= \left(\frac{35}4\right)^2-3\left(\frac{19}4\right)^2 =8.875 $$ In this case the correct approximation is $e+f\sqrt{3}=-1+5\sqrt{3}$, and then $$ N((a+b\sqrt{3})-(e+f\sqrt{3}))=N\left(\frac{1}4-\frac{1}4\sqrt{3}\right)=\frac18, $$ and we even have $|(a+b\sqrt{3})-(e+f\sqrt{3})|\approx 0.183$.


On the other hand, if you want to ignore the function $N$, then you can approximate any real number $r$ with some element in $\mathbb{Z}[\sqrt{3}]$ to any desired precision, since $\mathbb{Z}[\sqrt{3}]$ is dense in $\mathbb{R}$. This means, for any number $r\in \mathbb{R}$ and any $\varepsilon>0$, you can find an element $a+b\sqrt{3}\in\mathbb{Z}[\sqrt{3}]$ such that $$ |(a+b\sqrt{3})-r|<\varepsilon. $$ There is no canonical choice for $a$ and $b$, but one could construct algorithms that give you a unique answer, for example, since $q=\sqrt{3}-1$ satisfies $\frac 12<q<1$, you can approximate any positive real number $R<1$ with $\sum_{i\in \mathbb{N}}q^{n_i}$ with $n_i$ an increasing sequence of integers, such that $\lim_{N\to\infty}\sum_{i=0}^{N}q^{n_i}=R$. You have to define inductively $n_{N+1}$ as the minimal $n$ such that $$ q^n<R-\sum_{i=0}^{N}q^{n_i}. $$


If I'm understanding this correctly, it is not only necessary to know not only what the dividend and divisor are, but also what is being used for the Euclidean function. Or I suppose we can just assume it's absolute value of the norm.

In $\textbf{Z}$, there are only two choices to round to, floor and ceiling. In the ring of $\textbf{Q}(\sqrt{d})$ with $d$ negative, there are only four choices, unless you choose some exotic norm function.

But with $d$ positive, as you already know, there seem to be infinitely many choices. But knowing what the Euclidean function is, we have some guidance. For example, with $$\frac{7 + 2 \sqrt{3}}{2},$$ we can view the choice of $5$ as $5 + 0 \sqrt{3}$, that is, for $x = \alpha + \beta \sqrt{3}$, $\beta = 0$. The choices for $\beta = \pm 1$ are $7 - \sqrt{3}$ and $4 + \sqrt{3}$, which give us $qm = 8 + 12 \sqrt{3}$ and $14 + 10 \sqrt{3}$, corresponding to remainders $r = 5 - 3 \sqrt{3}$ and $-1 - \sqrt{3}$. The norms of the remainders get progressively larger, and though there are more choices, it's still a finite set.


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.