Generalizing tools from the Gaussian integers

We would like to construct the mathematical tools we used with the Gaussian integers.  In particular we would like to construct the tools for a division algorithm,

We first need to define , the equivalent of conjugation.

>	phi := x -> subs(sqrt(d)=-sqrt(d),x);

>	phi(a + b*sqrt(d));

Next we want to define a norm:

>	normd := x -> abs(expand(x*phi(x)));

>	normd(a+b*sqrt(d));

We would also like functions for recovering a and b, the rational and irrational parts of a ring element.

>	ratd := x -> (x + phi(x))/2; irratd := x -> (x - phi(x))/(2*sqrt(d));

>	ratd(a+b*sqrt(d)); irratd(a+b*sqrt(d));

Following the pattern used with the Gaussian integers, we want to establish a nearest function.

>	neard := x -> round(rationalize(ratd(x))) + round(rationalize(irratd(x)))*sqrt(d);

>	neard((a+b*sqrt(d))/(x+y*sqrt(d)));

This is enough to define quotients and remainders over these rings.

>	quod := (x,y) -> neard(x/y); remd := (x,y) -> expand(x - y*neard(x/y));

>

The easy cases, d=2 or 3

When d is 2 or 3, the above constructions let us mimic what has we did with the Gaussian integers.  Note that for the Euclidean algorithm to work the remainder needs to be smaller than the divisor.

Lets see that the definitions work.  To do that we need a specific value of d.  We will start with d = 2.

>

d := 2;

We also need to define a u0 and r0 to work with.

>	a :=37 + 29 * sqrt(d);  b := 3 + 5 * sqrt(d); 'norm(a)' = normd(a); 'norm(b)' = normd(b);

Now we find the quatient and the remainder and check the size of the remainder

>	q0 := quod(a, b);   r0 := remd(a, b); `the norm of r0 ` = normd(r0);

Now we repeat the process until we get a remainder of zero

>	q1 := quod(b, r0);   r1 := remd(b, r0); `the norm of r1 ` = normd(r1);

>	q2 := quod(r0, r1);   r2 := remd(r0, r1); `the norm of r2 ` = normd(r2);

The last nonzero remainder is the GCD.

A case where the the division algorithm fails, d=5

The reason the methods developed for the Gaussian integers work so well in the first two cases is that if d is 2 or 3, then the norm of   , whenever the absolute value of both a and b is bounded by   .    (Our divisor and remainder method produces a remainder that is   times the divisor where   is the amount we rounded off to produce our quotient.)  This means that the norm of the remainder is less than the norm of the divisor.  The method breaks down when d = 5.  In that case the norm of     is 1.  One is tempted to see if  is closer to other latice points, but if  and  are odd integers, then the norm of  is always at least 1.

Part of the problem is that  is a unit of Q[ ], so     and       try to act like associates with no remainder.  It is worthwhile noting that in Z[ ] the given norm is Euclidean.

>	d := 5; normd(1/2 + 1/2*sqrt(d));

A case when the division algorithm requires trickery, d=7

Somewhat contrary to intuition, the case of d = 7 is better than when d = 5.  We need to recall that the size of    is    .  This leads to the interesting observation that when,    , the origin may not be the closest point.

The method we have been using to establish the division algorithm is to divide  by  producing  in Q[ ], then round  to , the nearest member of Z[ ], and show that if the norm of   is less than 1, then the remainder is , and this has norm less than the norm of y.  

When d was 2 or 3, we got the ring element closest to  by rounding  and .  When d = 7, we need to be more clever.  Notice that intuitively bigger ring elements can have smaller norms.

>	d := 7; `norm (1/2 + 1/2 sqrt(7)) ` = normd(1/2 + 1/2*sqrt(d)); `norm (3/2 + 1/2 sqrt(7)) ` = normd(3/2 + 1/2*sqrt(d));

This means that  is closer to -1 than to 0.

In general, we need to show that given any  in Q[ ], we can find    in Z[ ] such that the norm of  has norm less than 1.

We first note that it is sufficient by symmetry to consider only the cases when  .

We will show that all such points are within 1 of either (0,0), or (-1, 0).

First consider the points that are within 1 of the origin.  Those are the points in the region containing the origin and bounded by the hyperbolas    and .  In the region we are concerned with, that is the set of points below the curve .

>	plot({.5, sqrt((1 + x^2)/7)}, x = -.1..0.6, y = 0..0.6);

As you can see, that gets most of the region we are concerned with.  We now look at the points within 1 of the point (-1, 0).  In terms of our norm, that is the set of points in the region containing (-1, 0) and bounded by the hyperbolas      and .   Equivalently, it is the set of points between the curves   and    .

>	plot({sqrt((1 + (x+1)^2)/7), sqrt((-1 + (x+1)^2)/7)}, x = -.1..0.6, y = 0..0.6);

Putting the curves together, we see that this takes care of all points except for a single point.

>	plot({sqrt((1 + x^2)/7),  sqrt((1 + (x+1)^2)/7), sqrt((-1 + (x+1)^2)/7)}, x = -.1..0.6, y = 0..0.6);

The only point of concern is the one on the boundary in both cases.  Elementary algebra shows that this point is , but that is not a rational point, and does not have to be considered.

Thus our method of dividing in the associated field and rounding  works, we simply have to round the quotient in the nontrivial fasion described above.