9
$\begingroup$

Assume that $K$ is a number field such that $\mathcal{O}_K$ is a norm-Euclidean ring. I am looking for an efficient algorithm that given an element $x\in K$, find an integer $y\in\mathcal{O}_K$ that is closest to $x$ with respect to the norm, i.e. $N(x-y)$ is minimum (at most the Euclidean minimum $m(K)$).

For $K=\mathbb{Q}[i]$ and $\mathcal{O}_K=\mathbb{Z}[i]$ is the Gaussian ring, it is easy by rounding, i.e., for $x=a+ib\in K$, then $y=a'+ib'$ with $a'$ and $b'$ are the integers nearest to $a$ and $b$ respectively. In this case the Euclidean minimum is $m(K)=\frac{1}{2}$, i.e. $N(x-y)\leq\frac{1}{2}$.

For Eisenstein ring $\mathbb{Z}[w]$ where $w^2+w+1=0$, then for given $x=a+bw\in \mathbb{Q}(w)$, the norm is $N(x)= a^2+b^2-ab$ and it is known that $m(K) =\frac{1}{3}$ and rounding does not work as in the case of Gaussian integers. A naive approach can be done as follows: $$N(x-y)= (a-a')^2+(b-b')^2-(a-a')(b-b')=(a-a'-\frac{b-b'}{2})^2 + \frac{3}{4}(b-b')^2$$ and let $b'$ is the rounding of $b$, then $a'$ is the rounding of $a-\frac{b-b'}{2}$, but what we obtain is that $N(x-y)$ is upper-bounded by $\frac{7}{16}$, not $m(K)=\frac{1}{3}$ as desired.

Could anyone please give me some references for such algorithms for Euclidean rings?

Many thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ For imaginary quadratic fields, the following MO question is relevant: mathoverflow.net/questions/59395/… $\endgroup$ – François Brunault Jun 9 '18 at 11:27
  • 1
    $\begingroup$ A variant of this problem for an arbitrary number field $K$ of signature $(r_1,r_2)$ consists in finding the nearest algebraic integer $x \in \mathcal{O}_K$ relative to the canonical embedding of $K$ into $\mathbb{R}^{r_1} \times \mathbb{C}^{r_2}$. In the case $K$ is norm-euclidean, I don't know whether these two settings give the same nearest algebraic integer. $\endgroup$ – François Brunault Jun 9 '18 at 11:37
5
$\begingroup$

For in depth information I would suggest the well regarded survey The Euclidean Algorithm in Algebraic Number Fields by Franz Lemmermeyer.

There are a fair number of known norm Euclidean rings $\mathcal{O}_K$, though not a huge number. Only a few are commonly encountered so I would ask which ones you really care about and suggest looking at those specifically.

Let me start with some specifics and then make some general remarks.

COMPLEX QUADRADIC NORM-EUCLIDEAN RINGS

There are exactly five of these, they come from $\mathbb{Q}[\sqrt{-m}]$ for $m=1,2,3,7,11.$ In the first two cases the ring has basis $\{1,\sqrt{-m}\}$ and embedded in $\mathbb{C}$ is tiled by recatangles. For those two your natural rounding works. For the other three a convenient basis is any two of $\{1,\frac{-1+\sqrt{-m}}2\,\frac{1+\sqrt{-m}}2\}.$ Here is the picture for your case of $m=-3.$

enter image description here

The small dot is $$2\frac6{13}-\frac5{13}\omega=2\frac{11}{13}-\frac5{13}\alpha=2\frac{6}{13}\alpha-2\frac{11}{13}\omega.$$ Naive rounding takes it to to $2,3$ and $2\alpha-3\omega=2-\omega$ respectively. However the actual tiling makes it clear where the closest thing is. The cases $m=-7,-11$ are similar but there is not the rotational symmetry.

In these cases $x+y\sqrt{-m}$ has norm $|x^2+my^2|$ so can't be small unless both $x$ and $y$ are, this is why the naive rounding is almost optimal.


REAL QUADRADIC NORM-EUCLIDEAN RINGS

There are exactly $16$ of these. They come from $\mathbb{Q}[\sqrt{m}]$ for $m=2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73.$

The norm sends $x+y\sqrt{m}$ to $|x^2-my^2|$ so the smallest results may only come from large $x,y.$

Consider the case $m=2$ and a point $B=\frac{p}{q}+\frac{p'}q\sqrt{2} \in \mathbb{Q}[\sqrt{2}].$ Certainly the minimum norm of $A-B$ for $A=s+t\sqrt{2}\in\mathbb{Z}[\sqrt{2}]$ is a positive fraction $\frac{r}{q^2},$ but it might be tricky to find. If we manage to find $r=1,$ that is surely optimal.

For $B=\frac5{11}+\frac{16}{33}\sqrt{2}$ each of $0,1,\sqrt{2}$ and $1+\sqrt{2}$ gives a norm of about $\frac14$. The exact norms are $\frac{287}{1089},\frac{188}{1089},\frac{353}{1089}$ and $\frac{254}{1089}$ respectively. There are only two results that good for $A=x+y\sqrt{2}$ with $-2000 \leq x \leq 2000.$ However they are $A=-37-26\sqrt{2}$ and $A=-13+10\sqrt{2}$ both giving a norm (for the difference) of $\frac{56}{1089}.$ I suspect that is closest but don't actually know.

Often one of the four obvious choices is as good as any other choice, and few cases I found are as extreme as this one.


COMMENTS

I like the question but wonder about the motivation. One motivation might be to compute $\gcd(a,b)$ efficiently with the Euclidean algorithm.

For example in $\mathbb{Z}$ the move is $\gcd(a,b)\rightarrow \gcd(b,r)$ where $a=bq+r$ and $0 \lt r \lt b.$ It is known that in a certain sense the worst case is consecutive Fibonacci numbers. For example $$(55,34) \rightarrow (34,21) \rightarrow(21,13) \rightarrow (13,8) \rightarrow(8,5) \rightarrow (5,3) \rightarrow(3,2) \rightarrow(2,1)$$ is $7$ moves.

However, $\gcd(b,r)=\gcd(b,b-r)$ and the second seems likely to be more efficient when it is smaller. Hence:

$$(55,34) \rightarrow(34,13) \rightarrow(13,5) \rightarrow(5,2) \rightarrow(2,1)$$ is only $4$ moves. Essentially we rounded $\frac{55}{34}$ up to the nearest integer $2$ and wrote $55=34\cdot 2-13$ instead of $55=34 \cdot 1 +21.$

Before going on I'll note that there is sometimes no loss in using the larger of the two remainders, The remainder $13$ is quite a bit smaller that $21$ but an equally short computation is

$$(55,34) \rightarrow(34,21) \rightarrow(21,8) \rightarrow(8,3) \rightarrow(3,1).$$

I rather suspect that it is never better to use the larger of $r,b-r$ but I have no proof.

If we were trying to find $\gcd(r+s\sqrt{2},t+u\sqrt{2})$ we would go to $\gcd(t+u\sqrt{2},v+w\sqrt{2})$ where $v+w\sqrt{2}=r+s\sqrt{2} -(a+b\sqrt{2})(t+u\sqrt{2})$ and $a+b\sqrt{2} \in \mathbb{Z}[\sqrt{2}]$ somehow chosen to be close to $\alpha+\beta\sqrt{2}=\frac{r+s\sqrt{2}}{t+u\sqrt{2}}\in \mathbb{Q}[\sqrt{2}].$ Could we get less iterations by working hard to make $v+w\sqrt{2}$ have a very small norm relative to $|r^2-2s^2|$, perhaps at the cost of $v,w$ being larger than any of $r,s,t,u?$ It isn't clear. It could be worse. The naive approach does make $v,w$ smaller than $r,s,t,u$ and the norm at each stage is an integer no more than $\frac14$ the previous norm. So the easy to compute naive approximation does give exponential convergence.

$\endgroup$

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.