This idea first came to my mind a long time ago when I was trying to generalise the application of the division algorithm. All I came up with is the following:
A few days ago, in a Number Theory lecture, we proved that the minimal solution to Pell’s equation generates all solutions. It reminded me of the division algorithm again, so it was time again to try to generalise this, because now I have a few more tools in hand!
Let’s say is a set where the division algorithm applies. We definitely need some sort of partial order in to say that the ‘remainder’ must be ‘less than’ the ‘divisor’. We might want to be closed under some operation (so that we can repeatedly ‘subtract’ the ‘divisor’ from the ‘dividend’) and we also need an inverse operation (i.e. the ‘subtraction’).
So first of all, we need to be a poset. In addition, the closure and inverse operations suggest that we want to be a group. How should the order behave under the group operation? Clearly we want it to be compatible with the operation. We also probably want the inverse of a ‘positive’ element to be ‘negative’, and vice-versa. Do we need the group to be abelian? Maybe, but let’s not impose that condition yet.
So to put our ideas into work, let be a group with a partial order such that for all and . We say that an element is positive if , where is the identity element of . Define the positive cone of to be the set of all positive elements.
Okay now we hopefully have all the necessary definitions in place. Let’s see if we can prove anything using these. The first thing that we want is probably: if , then . This follows easily: , add to both sides and we are done. It works the other way around as well, so in fact we have proved:
Lemma 1. .
That was good. We wanted the inverse of positive elements to be negative and it just followed from the definition. But we want more! So take a non-zero element . By Lemma 1 we can take to be positive without loss of generality. How about adding something to both sides of again? Last time we added . We can add , but that doesn’t change anything. So the only obvious choice left is to add : . Now what? Let’s add again! , i.e. . Combining the last two gives . It follows by induction that for all integers (note: here , times). This looks promising.
What about ‘negative’ elements? Note that by Lemma 1, . Adding to both sides yields , and so on. So we have another nice result:
Lemma 2. for all integers and .
It seems that this is all we can derive from our first principles. So let’s apply more restrictions on . Let be positive with . As in the division algorithm, let’s look at etc. We want this sequence to stop as soon as becomes negative. How do we do this? In other words, we want the set to have a least positive element. Did something just pop up in your mind? A set having a least element must have reminded you of something like… the well-ordering principle! So how about we impose the extra condition that is a well-order on ? Well, that’s clearly absurd, because for any positive the set has no least element. How about least positive element then? In other words, let’s say is well-ordered under .
Now has quite a few nice properties: it is a group under , is an order on preserving , and its positive cone is well-ordered. Let’s see if our ideas work now.
Let be the least non-zero element in and be any non-zero element. Without loss of generality, . Then so . Consider the elements for . We want for some . Can we achieve this? We certainly have for , so we need for some . By Lemma 2 must be greater than . How do we know that exists?
Suppose it doesn’t. Then for all by totality (recall that a well-order is a total order) and Lemma 2. Then , so . Hence , so it has a least element . Then which implies for all , a contradiction.
That was really good! Now we can take the maximal such that . Then . Then ; the left inequality says , and the right inequality says . So and . This is exactly what we wanted.
We have shown that . In fact we can do more. Clearly cannot be finite. Because otherwise must have finite order, i.e. for some positive integer . Then by Lemma 2. So all of these must be equalities (by antisymmetry), i.e. , a contradiction.
So our restrictions have not only worked, we’ve shown that all groups with these properties essentially have the same structure, that of the infinite cyclic group. Let’s give a name: we say that the group is well-ordered if the set is well-ordered under . We have thus proved:
Proposition 1. The only non-trivial well-ordered group is the group of integers (up to isomorphism).
Now we can give one-line proofs of the following facts using our Proposition 1: (here any ordering is under the usual order in )
Corollary 1. The of two natural numbers exists, and is their least positive linear combination.
Proof. For , the additive group is well-ordered, and so is equal to for the least positive element of .
Corollary 2. is a PID.
Proof. Any ideal in is a well-ordered group, and so must be for some .
Corollary 3. If is the least solution to Pell’s equation , then all solutions are given by for .
Proof. The solutions to Pell’s equation form a subgroup of the multiplicative group of units in the ring . Since it is well-ordered, the conclusion follows.
We can even improve Proposition 0 a little:
Corollary 4. If is a subgroup of , then the following are equivalent:
(i) is well-ordered;
(ii) is not dense;
(iii) is cyclic.
Proof. by Proposition 1. is clear. Suppose that is not dense. Then there exist with such that . Then , because . Therefore is the minimal element in , i.e. . Thus .
A consequence of Corollary 4 is:
Note that is dense if and only if it has two –linearly independent elements; therefore must be torsion-free. And since is faithful, must be abelian: , i.e. for all . Thus we get the following nice result:
Proposition 2. If has a faithful one-dimensional real representation, then one of the following holds:
Moreover, if and is finitely generated, then , for some .