8
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Does this MSE link help math.stackexchange.com/questions/58561/norm-euclidean-rings? $\endgroup$
    – Rob Arthan
    Commented Jun 11, 2019 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$ Commented Jun 12, 2019 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
    Commented Jun 12, 2019 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$ Commented Jun 13, 2019 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$ Commented Jun 22, 2019 at 11:07

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .