WorksMathematics
Orders in the Euclidean Court
Abstract
Following Johnson, Queen, and Sevilla, we call an order in a number field \textsf{generalized Euclidean} if for all with for which is a principal ideal of , there are with and . We prove that only finitely many quadratic orders are generalized Euclidean. Additionally, assuming GRH, we show that for each fixed there are only finitely many integers for which is irreducible over and is generalized Euclidean. When is even, we can remove the assumption of GRH.
Introduction
Let be a number field with ring of integers . One calls norm-Euclidean if, for every pair of with , there are for which
If is norm-Euclidean, then every pair of has a gcd that can be determined, in principle, by the Euclidean algorithm. As explained in a first algebra course, it follows that is a principal ideal domain and hence also a unique factorization domain.
Here we consider orders in number fields, not just the ring of integers. Moreover, we work with a more general notion, first introduced by Johnson–Queen–Sevilla (for rings of integers in quadratic fields) [6]. We call an order generalized Euclidean if for all with and principal, there exists satisfying (1). In other words, if the gcd of and exists (in a strong form), then it can be determined (in principle) using the Euclidean algorithm (relative to the norm). (To align more with current practice, we should perhaps use the terminology “generalized norm-Euclidean”, but we have chosen to use the shorter “generalized Euclidean”.) A partial classification of quadratic rings of integers that are generalized Euclidean was given in [6 Theorems 1 and 2], but they did not fully treat the case of when . We prove a finiteness theorem for general quadratic orders.
Theorem 1. There are finitely many quadratic orders that are generalized Euclidean.
One might wonder whether we gain anything by considering nonmaximal orders in Theorem 1. Nonmaximal orders can never be Euclidean, as they are never unique factorization domains. However, it is possible for a nonmaximal order to be generalized Euclidean. This is the case, for instance, for , which is nonmaximal with respect to the field .
Lacking a reference, we prove here that is generalized Euclidean. Let with , and write with . Let be the integers nearest to , rounding down when the distance to the nearest integer is precisely . Let and define by (1). Then , unless and . (We omit absolute value signs around our norms, since norms from are nonnegative.) So to show is generalized Euclidean, it is enough to show that is nonprincipal in this exceptional case. When this case arises, , so that
Suppose for a contradiction that is principal, say . Then , , and is principal. But it is straightforward to check that is nonprincipal. For instance, and are nonassociate irreducibles in , so that could not be generated by anything other than a unit. But every element of has even norm, and so .
We may also consider more general orders. Fix an integer . If is an integer for which the polynomial is irreducible over , we let and . Then is an order inside the number field ; we will refer to as a pure order of degree .
Theorem 2. Fix an even positive integer . There are finitely many pure orders of degree that are generalized Euclidean.
Theorem 3. Assume GRH. For any fixed integer , there are finitely many pure orders of degree that are generalized Euclidean.
One might be interested in comparing Theorems 2 and 3 with results of Egami (see [1]) for the fields , prime. However, the notion of containing a norm-Euclidean ideal class, considered by Egami, is different than the notion we consider here, so neither set of results implies the other.
Preparation
At the heart of all our proofs are the following variants of Heilbronn’s criterion for non-Euclideanity. Heilbronn’s criterion was first introduced in [3], but can be considered implicit in earlier work of Erdős and Ko [2]. We remark that it is condition (i) in both Propositions 4 and 5 that allows the stronger conclusion of “not generalized Euclidean” versus “not norm-Euclidean”.
Proposition 4 (Heilbronn’s criterion for pure orders). Suppose . Let be a pure order of degree . Suppose there are positive integers with
where
(i) ,
(ii) is a th power modulo ,
(iii) neither nor has the form for any .
Then is not generalized Euclidean.
Recall that to each quadratic order there is associated a unique integer for which either
or
The first case occurs when the order discriminant is a multiple of , in which case , and the second case when , in which case . In both cases, is not a perfect square.
Proposition 5 (Heilbronn’s criterion for quadratic orders). Let be an order in a quadratic field , and let be such that (2) or (3) holds. Suppose there are positive integers with
where
(i) ,
(ii) is a square modulo ,
(iii) neither nor has the form for any .
Then is not generalized Euclidean.
Proposition 5 does not quite follow from Proposition 4; when , the corresponding order is not for any .
Perhaps the chief novelty in the proofs (and statements) of Propositions 4 and 5 is the lack of any (explicit) reference to ramification. Instead, we phrase the arguments in terms of properties of the corresponding norm forms.
We suspect the following lemma, needed for the proof of Proposition 4, is known to the experts. But lacking a suitable reference, we include the proof here.
Lemma 6. Let , and let be a pure order of degree . Let be the norm form associated to the -basis of . That is, is the polynomial in defined by
where runs over all the embeddings of into . Then .
Proof. Define a polynomial in indeterminates and by setting
Then can be viewed as a polynomial in over , symmetric with respect to the . By the fundamental theorem of symmetric polynomials, is a polynomial, with coefficients, in the elementary symmetric functions of the .
Continuing, we introduce a new indeterminate , and we let . Replacing each by , we conclude from our work in the last paragraph that
is a polynomial over in the elementary symmetric functions of the . These elementary symmetric functions all vanish, except for the last one (the th), which is ; this can be read off from the formal expansion . We conclude that is a polynomial in and , with integer coefficients. Setting in (4), we deduce that
To finish, it remains only to observe that
so that
as claimed. □
Proof of Proposition 4. It is convenient to abbreviate to throughout the proof, and to write in place of . Suppose for a contradiction that is generalized Euclidean. Using conditions (i) and (ii), we may choose with coprime to and . Since
the -ideal generated by and is all of , and in particular is principal. As is generalized Euclidean, there is an with and . Write
Then , so that . But
as , for the final displayed expression to land in requires that . Hence, . By Lemma 6,
We have and . If , then the congruence forces . Similarly, if , then . In either case we contradict our condition (iii). □
Proof of Proposition 5. This is very similar to the proof of Proposition 4, so we only sketch it. Using (i) and (ii), choose , , with . Then . Hence, generate the unit ideal of . Thus, assuming is generalized Euclidean, there is an with and , where denotes the norm .
Let denote the nontrivial automorphism of . Since carries into , the congruence
implies
Thus, , and
Regardless of whether we are in case (2) or (3), this last containment forces . Hence,
Reasoning as in Proposition 4, we deduce from that either or , contradicting (iii). □
Proofs of Theorems 1–3
Theorems 1–3 follow immediately from Propositions 4 and 5 via the following lemmata.
Lemma 7. Let be a pure order of even degree . Provided is sufficiently large, there are positive integers with and conditions (i)–(iii) of Proposition 4 satisfied.
Lemma 8. Let be a quadratic order with satisfying (2) or (3). Provided is sufficiently large, there are positive integers with and conditions (i)–(iii) of Proposition 5 satisfied.
Lemma 9. Assume GRH. Let . For every with sufficiently large, there are positive integers with and conditions (i)–(iii) of Proposition 4 satisfied.
Our proofs of Lemmas 7 and 8 rely on the following result of Pollack [7 Theorem 1.1].
Proposition 10. For each , there are and for which the following holds. For all and every nontrivial Dirichlet character mod , there are more than primes for which .
Proofs of Lemmas 7 and 8. In order to treat both Lemmas in a unified fashion, we adopt the following convention. When Lemma 7 is in view, the letters have the meanings of that lemma, and . If we are considering Lemma 8, we take , , and the quadratic order appearing in that lemma.
To start with, we produce positive integers and summing to and satisfying conditions (i) and (ii) in Proposition 4 (respectively, Proposition 5). At the end of the proof we will see that our particular construction of and also satisfies condition (iii) of these Propositions.
Let be the quadratic character mod given by (the Kronecker symbol), and note that if for the prime , then is odd and . By Proposition 10, it follows that for all , there is a with
whenever is sufficiently large in absolute value. Since , we can take, for large in absolute value, with . (In particular, .)
We now proceed to count the number of integers for which
and for which all of the following hold:
;
is a th power mod with ;
;
.
If at least one such pair of exist, then conditions (i) and (ii) in Proposition 4 (or Proposition 5) are satisfied by taking .
(5) implies that is entirely determined by . So we can phrase the problem entirely in terms of counting certain integers . To ensure is an integer, we tack on the condition
.
Our task then becomes counting all the integers simultaneously satisfying conditions 1–5, thinking of condition 4 as .
We detect condition 2 using character sums; we have that
where is the number of characters mod satisfying .
We use an inclusion-exclusion argument to account for conditions 3 and 4. We thus write our count as
where the sums are taken over all satisfying conditions 1 and 5, but possibly violating conditions 3 and/or 4: here if (and only if) condition 3 is violated, and if (and only if) 4 is violated.
We proceed to estimate the sums . First, we look at the contribution of the nonprincipal characters. A violation of condition 3 means that we have . Similarly, a violation of condition 4 means that condition 5 can be strengthened to . Thus, depending on and , we have by the Chinese Remainder Theorem that each lies in one specific residue class mod , i.e., we can write where lies in an interval of length .
We then write, for each ,
by Pólya–Vinogradov. Here we write for the inverse of mod .
We now look at the contribution of the principal character. We write
Collecting estimates,
Putting everything together, we get that, as , the number of integer solutions to (5) satisfying conditions 1–5 is
Let us estimate the various terms in this expression. Writing for the divisor function, we have (see Theorem 315 in [4] for this last bound on ). Since the multiplicative group mod has a direct product decomposition into at most cyclic groups (see for instance [IR90, Theorem 3, p. 44),
Furthermore, Theorem 327 in [4] ensures that for sufficiently large , we have . Putting these estimates together, keeping in mind that , we see that the main term in the last display exceeds for large , while the contribution of the -terms is smaller than (say). In particular, the displayed expression is positive for all large , allowing us to find our .
Finally we return to proving our choices of and satisfy part (iii) of Propositions 4 and 5. Suppose that , with . We consider the prime factorization of in the Dedekind domain . By our condition 3 above, . Thus, the prime factorization of contains a unique prime ideal lying above ; furthermore, has degree one. Then , with the isomorphism induced by the inclusion of into . Since is a th power in , it is also a th power in and thus in . But is even, and so the stipulation that is a quadratic nonresidue modulo implies that is not a th power modulo . This contradiction establishes that is not a norm in . An entirely analogous argument shows that is not a norm in . Here we use that (by condition 4 above) and that is a quadratic nonresidue modulo . □
We now settle Lemma 9. In view of Lemma 7, we may assume is odd. We make use of the following GRH-conditional version of the Chebotarev density theorem:
Proposition 11. Assume GRH. Let be a finite Galois extension of number fields, and let be the Galois group of . Let be a subset of that is invariant under conjugation. Let denote the number of primes up to whose associated Frobenius conjugacy class is in . Let be the product of the distinct rational primes ramifying in . Then
for some absolute constant .
Proposition 11 is the special case of Serre's [8 eq. (20_R)] where .
Proof of Lemma 9. Let be odd, and let be the least prime dividing . Arguing as in the proof of Lemma 7, it is enough to show that there are two primes , not dividing , modulo which is not a th power.
We let and we consider , the splitting field of the polynomial . As is the normal closure of , every prime ramifying in divides , which in turn divides . Hence: Every prime ramifying in divides . This observation will be useful momentarily when we apply Proposition 11.
Let be a prime not dividing . In order that not be a th power modulo , it is sufficient that the action of the Frobenius conjugacy class associated to , on the roots of , have no fixed points. We let be the (conjugation-invariant) set of fixed-point-free elements of .
The Galois group of is made up of elements for , , determined by the conditions that , . Furthermore, it is straightforward to check that the set defined above is precisely the collection of with . Hence, .
Applying Proposition 11, we conclude that for some constant depending only on . It follows that
It is certainly possible to choose our two primes as long as
We will show this inequality holds for , provided is large enough. As for large , this suffices.
Allowing implied constants to depend on (which is fixed), we have , while . Hence, (6) yields for large . On the other hand, , which is of smaller order. Thus (7) holds whenever is sufficiently large, as desired. □
Acknowledgements. We thank the referee for a careful reading and helpful suggestions.
Department of Mathematics, University of Georgia, Athens, GA 30602
Email address: [email protected]
Department of Mathematics and Statistics, California State University, Chico, Chico, CA 95929
Email address: [email protected]
Department of Mathematics, University of Georgia, Athens, GA 30602
Email address: [email protected]
Department of Mathematics and Computer Science, Lake Forest College, Lake Forest, IL 60045
Email address: [email protected]
References
- [1][Ega84] S. Egami, On finiteness of the numbers of Euclidean fields in some classes of number fields, Tokyo J. Math. 7 (1984), 183–198.
- [2][EK38] P. Erdős and C. Ko, Note on the Euclidean Algorithm, J. London Math. Soc. 13 (1938), 3–8.DOI
- [3][Hei38] H. Heilbronn, On Euclid’s algorithm in real quadratic fields, Proc. Camb. Philos. Soc. 34 (1938), 521–526.DOI
- [4][HW08] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, sixth ed., Oxford University Press, Oxford, 2008.
- [6][JQS85] D. H. Johnson, C. S. Queen, and A. N. Sevilla, Euclidean real quadratic number fields, Arch. Math. (Basel) 44 (1985), 340–347.
- [7][Pol17] P. Pollack, Bounds for the first several prime character nonresidues, Proc. Amer. Math. Soc. 145 (2017), 2815–2826.arxiv.org/abs/1508.05035
- [8][Ser81] J.-P. Serre, Quelques applications du théorème de densité de Chebotarev, Inst. Hautes Études Sci. Publ. Math. (1981), no. 54, 123–201.