Data Loading...
Introduction Flipbook PDF
THE EUCLIDEAN ALGORITHM FOR NUMBER FIELDS AND PRIMITIVE ROOTS M. R. MURTY AND K. L. PETERSEN 1. Introduction In 1927 Art
100 Views
37 Downloads
FLIP PDF 209.47KB
THE EUCLIDEAN ALGORITHM FOR NUMBER FIELDS AND PRIMITIVE ROOTS M. R. MURTY AND K. L. PETERSEN
1. Introduction In 1927 Artin formulated his famous conjecture about primitive roots. Artin’s Primitive Root Conjecture. If a is not -1 or a square then there are infinitely many primes p such that a is a primitive root modulo p. In fact, for an explicit constant A(a) Artin conjectured that the number of primes p ≤ x such that a is a primitive root modulo p is ∼ A(a)x/ log x. Assuming the generalized Riemann hypothesis (GRH), Hooley proved this conjecture in 1967. In 1983 Gupta and M. R. Murty [3] proved without any hypothesis that there are infinitely many values of a which satisfy the conjecture. This was refined by Gupta, M.R. Murty and V.K. Murty [4] and later by Heath-Brown [7]. Heath-Brown’s refinement implies that the conjecture fails for at most two prime values of a. Despite this, the conjecture is not known to hold for a single value of a. A connection between a number field version of this conjecture and the Euclidean algorithm was first touched on by Samuel [15] who applied a criterion of Motzkin to quadratic fields. An integral domain R is Euclidean if there exists a map φ : R − {0} → N such that given any a, b ∈ R there exist q and r so that a = bq +r with either r = 0 or φ(r) < φ(b). Any such R is a principal ideal domain (PID). It is a beautiful result of Weinberger’s [16] that assuming the GRH this condition is sufficient when OK is the ring of integers of any number field K other than an imaginary quadratic. That is, he proved the following conjecture conditionally. Conjecture 1.1. If K is a number field other than an imaginary quadratic, the ring of integers OK is Euclidean if and only if it is a PID. For an integral domain R, define the set A0 = {0} and inductively define the sets An to be the set of all r ∈ R such that every residue class modulo r has a representative in Am for some m < n. Motzkin’s criterion is that R is Euclidean if and only if ∞ [ R= An . n=0
The set A1 is the unit group, R× , of R and A2 consists of those r ∈ R such that the unit group surjects the non-zero residue classes modulo r. There are √only nine imaginary quadratic number fields whose integer rings are PIDs. These are the integer rings of Q( −d) for d = 1, 2, 3, 7, 11, 19, 43, 67, 163. Motzkin used this criterion to prove that of these nine imaginary quadratic fields, only for the first five is the ring of integers Euclidean, and for these the absolute value of the norm map serves as the function φ. We call such fields norm Euclidean. Samuel’s work made the prediction that real quadratic number fields whose ring of integers are PIDs are all Euclidean (but not necessarily norm Euclidean). Weinberger’s work built upon these ideas and the work of Hooley. Harper refined Motzkin’s criterion. For a prime ideal p ⊂ OK , let ϕp be the reduction modulo p map. Harper showed the following [5].
1991 Mathematics Subject Classification. 11A07, 11N36. Key words and phrases. Primitive Roots, Euclidean Algorithm, Large Sieve.
1
2
M. R. MURTY AND K. L. PETERSEN
× Harper’s Criterion. Let B be the set of all prime ideals p of OK such that ϕp (OK ) = ϕp (OK )× and let B(x) be those p ∈ B such that NK/Q (p) ≤ x. If OK is a PID and x |B(x)| (log x)2 then OK is Euclidean. √ Harper [5] used a more robust version of this criterion to show that Z[ 14] is Euclidean. The integer ring √ Z[ 14] was known to be a PID and known not to be norm Euclidean. Weinberger’s theorem, as echoed in Harper’s theorem shows a direct connection between the Euclidean condition and primitive roots. The generalization of Artin’s primitive root conjecture to number fields relevant to the Euclidean algorithm problem is the following.
Conjecture 1.2. Let K be a number field other than Q or an imaginary quadratic. Then there are infinitely × many prime ideals p in OK such that ϕp (OK ) = ϕp (OK )× . Harper and M.R. Murty [6] used Harper’s criterion to show that Conjecture 1.2 holds for K Galois of unit rank at least four. M.R. Murty and Petersen [11] showed that Conjecture 1.2 holds for those K, even with the additional restriction that NK/Q (p) ≡ a (mod b) for any (a, b) = 1 if K ∩ Q(ζb ) = Q. This generalization has applications to hyperbolic geometry (see [14]). The main goal of this paper is to remove the Galois condition. We prove the following. Theorem 1.3. Let K be a number field. If the unit rank of K is at least 4 and there is a subfield M < K such that K/M is Galois with group G of order at least 4, then there are x/(log x)2 prime ideals p in OK × such that ϕp (OK ) surjects ϕp (OK )× . The theorem below follows immediately using Harper’s criterion. Theorem 1.4. For K as in Theorem 1.3, OK is a PID if and only if OK is Euclidean. We show in §5 that the following corollary can be deduced from the methods used in the proof of Theorem 1.3. Corollary 1.5. If K is a totally real number field of degree at least five and K has a proper subfield M such that K/M is Galois, then K satisfies Conjecture 1.1 and Conjecture 1.2. These results do not address small degree number fields, number fields K that are not Galois over any number fields M , and small degree extensions of these fields. In the spirit of Gupta and M.R. Murty’s result, Narkiewicz [13] proved that at most two real quadratic number fields fail to satisfy Conjecture 1.1. Moreover, he proved that Conjecture 1.1 fails for at most two Galois cubic extensions. Narkiewicz’s results follow from his work [12] proving that Conjecture 1.2 fails for at most two real abelian number fields. He proves that if such an exceptional field exists it is cubic and there is only one exception, or there are at most two quadratic exceptions. The main tool in the proof of Theorem 1.3 is the lower bound sieve in the form given by Iwaniec [8]. We use the generalized Riemann hypothesis on the average proven by M.R. Murty and Petersen [10] to control the error term in the sieve. The sieve allows us to find many rational primes p lying under a split prime ideal p ⊂ OK such that p − 1 has only necessary small divisors (e.g. 2) and very large divisors. The image ϕp (OK ) has order p − 1, and we construct a conjugacy class in which the small divisors of such p − 1 do not × × divide the index (p − 1)/ϕp (OK ). Therefore, if ϕp (OK ) does not surject ϕp (OK )× the index is large, so that × the order of ϕp (OK ) is small. The remainder of the proof is a counting argument. First, in §2 we review the lower bound sieve, and apply it to our situation in §3. After that, we prove Theorem 1.3 in §4. Finally, we make some concluding remarks in §5. 2. The lower bound sieve Let L/M be a Galois extensions of number fields with group G, and let C be a conjugacy class in G. For an unramified prime ideal p of M , let σL/M (p) denote the conjugacy class of the Frobenius element. The lower bound sieve estimates the number of prime ideals p in M with σL/M (p) = C. Our reference for the lower bound sieve is [2].
THE EUCLIDEAN ALGORITHM FOR NUMBER FIELDS AND PRIMITIVE ROOTS
3
Let z ≥ 2 be a real parameter, and define A to be a finite Y sequence of integers (depending on the parameter p, define z), and P a sequence of rational primes. With P (z) = p w ≥ 2, −1 Y ω(p) log z A 1− < 1+ . p log w log w w≤p x 2η − . For p lying over such p, the index × [ϕp (OK )× : ϕp (OK )] is small. We will use a counting argument to show that there are ‘few’ p associated to such small indices. The goal of this section is to prove the following estimate for |T (x)|. Proposition 3.1. There is a positive constant D so that x x |T (x)| = D +O . 2 (log x) (log x)3 Before employing the sieve, we require a lemma that will enable us to handle the small divisors of p − 1. We will do so by constructing a conjugacy class in a Galois extension of M containing K. For a rational prime ` define the number field K` by adjoining the `th roots of elements of a set of representatives of × × ` OK /(OK ) to K. The extension of number fields K` /K is Galois. Let L be the compositum of all K` as ` varies over the prime divisors of tK . The intersection of all K` for ` dividing tK is K and the extension
4
M. R. MURTY AND K. L. PETERSEN
L/K is an abelian radical extension. Therefore L/M is Galois. Let G = Gal(L/M ) and G` = Gal(K` /M ). Let H ∼ = Gal(L/K), so that with N = Gal(K/M ) we have G/H = N . For each `, define H` ∼ = Gal(L/K` ) and N` ∼ = K` /K so that H/H` = N` . Lemma 3.2. There is a conjugacy class C ⊂ G such that if p is an unramified prime ideal in M then σp (L/M ) = C exactly for those p which are split in K and not split in any K` . Furthermore, if A < N is an abelian subgroup then A lifts to an abelian subgroup of G with the property that G ∩ C 6= ∅. Proof. A prime ideal p ⊂ K splits completely in K` if σp (K` /K) = 1 ∈ N` . Since N` = H/H` this condition lifts to the subgroup H` < H. That is, p ⊂ K splits completely in K` if σp (L/K) ∈ H` . Therefore, to ensure that p does not split completely in K` for any ` it is enough to require that σp (L/K) is in H − ∪H` . Such conjugacy classes exist if H 6= H` since H is abelian. If H = H` the condition is satisfied by choosing a non-identity conjugacy class. A prime ideal p ⊂ M splits completely in K if σp (K/M ) = 1 ∈ N . This condition lifts to H < G. That is, σp (L/M ) ∈ H corresponds to the condition that p splits completely in K. To combine the requirements, it suffices to show that there is a conjugacy class in H that is not in ∪H` . Such a conjugacy class exists unless H = H` for some (necessarily the only `). As mentioned above, if H = H` we can choose any non-identity conjugacy class of H. This is the desired conjugacy class C ⊂ G. The final statement follows because G/H = N with H abelian.
Now we employ the lower bound sieve. Let L, K, and M be as above. Let C be the conjugacy class prescribed in Lemma 3.2. Consider the sequence P consisting of the rational primes which do not divide tK , and the set A = {pn − 1 ≤ x : pn = NM/Q (p), σL/M (p) = C} 1
with z = x 2η − . Note that |S(A, P, z)| is the set consisting of the values pn − 1 = NM/Q (p) − 1 where σL/M (p) = C for an unramified prime ideal p of M with the additional conditions that pn − 1 is not divisible by any prime up to z other than those prime divisors of tK . x x Lemma 3.3. There is a positive constant D such that |S(A, P, z)| ≥ D + O . (log x)2 (log x)3 Proof. In the lower bound sieve, Z is a quantity which approximates A and ω(p) p Z approximates Ap . By |C| |C| li(x) ˇ the Cebotarev density theorem A ∼ li(x) and Ap ∼ . Therefore, we wish to choose ω(p) with |G|
ω(p) p Z
(∗)
∼
|C| li(x) |G| φ(p) ,
so that
ω(p) p
∼
|G| φ(p)
1 p−1 .
We choose Z = li(x) and ω(p) = 1 so that Y Y ω(p) −1 1 −1 1− = 1− . p p
w≤p 1. The number of such x, |SI (x)|, is bounded by the number of prime ideals p in M lying over some p such that NM/Q (p) = pn ≤ x with n > 1. This is, in turn, bounded by [M : Q] times the number of rational prime powers pn ≤ x with n > 1. If pn ≤ x, upon taking logarithms, n log p ≤ log x, so n ≤ log x. There 1 1 are at most x 2 squares of primes less than x and for each higher order power n > 2 there are at most x n associated prime powers. Therefore X 1 1 1 1 x 2 + O(x 3 log x) x 2 . pn ≤x n>1
This term is absorbed in the error, so we can assume that p in M lying over p is split. By construction of the conjugacy class C, if p in M is counted in S(A, P, z) and q in K lies over p, then q splits completely over Q. As a result, we may assume that p lies under a split prime in K. Let p be a prime ideal in OK and G ∼ = ϕp (OK )× be the cyclic group with presentation G = hg : g p−1 = 1i. Let ` be a rational prime dividing p − 1. The map ψ` : G → G defined by g 7→ g ` has kernel consisting of the `th roots of the identity, of which all ` are in G since ` divides the order of G. Therefore the elements of G which are `th roots are a subgroup, H of G of index `. × × If ` divides tK and also divides the index ϕp (OK )× /ϕp (OK ) then as G is cyclic, ϕp (OK ) < H. Therefore, × th every element of ϕp (OK ) has all ` roots in G. By definition K` is K adjoined with the `th roots of a set of × × ` representatives for (OK )/(OK ) . If q ⊂ K` lies over p then (OK` /q)× is generated by the `th roots of some × elements of (OK /p). By the above, these are all in H < G. Therefore q must split completely.
However, by construction all prime ideals q in M lying over p so that σL/M (q) = C do not split completely in OK` . Restricting to primes p in K lying over p which are split with σL/M (q) = C for q in M lying over × p, we can assume that if ` divides tK , then ` does not divide the index [ϕp (OK )× : ϕp (OK )]. Therefore, for these primes p for any p in OK lying over p we may assume that p splits completely and that if ` is a prime 1 × divisor of (p − 1)/ϕp (OK ), then ` > x 2η − . 4. Proof of the main theorem We will use the following estimate from Gupta and M.R. Murty [3]. Lemma 4.1 (Gupta-Murty). Let S be a multiplicative set in OK , p a prime ideal in OK coprime to the elements of S, and let r denote the rank of S. Then #{p ⊂ OK : |ϕp (S)| ≤ Y } Y
r+1 r
.
Proof of Theorem 1.3. Consider p ∈ T (x) with the prime ideal p in OK lying over p. If the prime ` divides 1 × the index of ϕp (OK ) in ϕp (OK )× then ` > x 2η − by Proposition 3.1. For these primes, the index [ϕp (OK )× : 1 × × ϕp (OK )] is either 1 or is greater than x 2η − . Consequently, if the index is not one, the order of ϕp (OK ) is 1 1 1− 2η + 1− 2η + less than x . Choosing Y = x in Lemma 4.1, we see that 1
1
× #{p ⊂ OK : |ϕp (OK )| ≤ x1− 2η + } (x1− 2η + ) 2
×
r+1 r
× ϕp (OK )]
There are x/(log x) primes p in T (x) where the index [ϕp (OK ) : 1 x (1− 2η +) r+1 r O(x )=o . (log x)2
. is one when
This occurs when 2η < r + 1. We have M ⊂ K ⊂ K` ⊂ L and a conjugacy class C in G = Gal(L/M ). We wish to rephrase this in terms of M and K alone. Let N = Gal(K/M ) and A < N an abelian subgroup. By Lemma 3.2, A lifts to an abelian subgroup of G satisfying A ∩ C 6= ∅. Therefore, the fixed field of A is the same as the fixed field
THE EUCLIDEAN ALGORITHM FOR NUMBER FIELDS AND PRIMITIVE ROOTS
7
of the lift. Let E be this field. We have η = max{nE − 2, 2} where nE = [E : Q]. If this maximum is 2, then the inequality is satisfied when r > 3. It suffices to consider the case when η = nE − 2. Let I = [K : E] so that nE = nK /I. With r1 and r2 being the number of real and complex places of K, so that nK = r1 + 2r2 and r = r1 + r2 − 1, the inequality is r1 1 − I2 + r2 1 − I4 > −3. This is certainly satisfied when I ≥ 4. It suffices to consider the case when I = [K : E] ≤ 3. With N = Gal(K/M ), if |N | has a prime divisor which is at least 5, by Sylow theory, there is an abelian subgroup A < N with |A| > 4, and we can use the above. As a result, we need only consider the case where |N | = 2a 3b . Likewise if a, b ≥ 2 there is an abelian subgroup of order at least 4. Therefore, it remains to deal with the cases where |N | = 1, 2, 3 or |N | = 6 is not abelian. A non-abelian group of order 6 is necessarily dihedral, and Artin’s holomorphy conjecture is known to hold for these groups. By Theorem 3.4 the inequality is satisfied in this case as well. Using Harper’s Criterion, Theorem 1.4 immediately follows. 5. Concluding remarks If K is a totally real field, we can be more specific. In this case, the inequality 2η < r + 1 in the proof of Theorem 1.3 reduces to r1 (1 − I2 ) > −3 and is satisfied when I > 1. As a result, the theorem holds for all real K if r > 3 and there is some M 6= K such that K/M is Galois. If r = r1 − 1 ≤ 3 the index [K : Q] is at most four. This is the statement of Corollary 1.5. The authors plan to address fields of small degree in future work. References [1] David A. Clark and M. Ram Murty. The Euclidean algorithm for Galois extensions of Q. J. Reine Angew. Math., 459:151– 162, 1995. [2] Alina Carmen Cojocaru and M. Ram Murty. An introduction to sieve methods and their applications, volume 66 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2006. [3] Rajiv Gupta and M. Ram Murty. A remark on Artin’s conjecture. Invent. Math., 78(1):127–130, 1984. [4] Rajiv Gupta, M. Ram Murty, and V. Kumar Murty. The Euclidean algorithm for S-integers. In Number theory (Montreal, Que., 1985), volume√7 of CMS Conf. Proc., pages 189–201. Amer. Math. Soc., Providence, RI, 1987. [5] Malcolm Harper. Z[ 14] is Euclidean. Canad. J. Math., 56(1):55–70, 2004. [6] Malcolm Harper and M. Ram Murty. Euclidean rings of algebraic integers. Canad. J. Math., 56(1):71–76, 2004. [7] D. R. Heath-Brown. Artin’s conjecture for primitive roots. Quart. J. Math. Oxford Ser. (2), 37(145):27–38, 1986. [8] Henryk Iwaniec. Rosser’s sieve. Acta Arith., 36(2):171–202, 1980. [9] M. Ram Murty. Problems in analytic number theory, volume 206 of Graduate Texts in Mathematics. Springer, New York, second edition, 2008. Readings in Mathematics. [10] M. Ram Murty and Kathleen L. Petersen. A Bombieri-Vinogradov theorem for all number fields. submitted for publication. [11] M. Ram Murty and Kathleen L. Petersen. The generalized Artin conjecture and arithmetic orbifolds. In Groups and symmetries, volume 47 of CRM Proc. Lecture Notes, pages 259–265. Amer. Math. Soc., Providence, RI, 2009. [12] W. Narkiewicz. Units in residue classes. Arch. Math. (Basel), 51(3):238–241, 1988. [13] Wladyslaw Narkiewicz. Euclidean algorithm in small abelian fields. Funct. Approx. Comment. Math., 37(, part 2):337–340, 2007. [14] Kathleen L. Petersen. Counting cusps of subgroups of PSL2 (OK ). Proc. Amer. Math. Soc., 136(7):2387–2393, 2008. [15] Pierre Samuel. About Euclidean rings. J. Algebra, 19:282–301, 1971. [16] Peter J. Weinberger. On Euclidean rings of algebraic integers. In Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972), pages 321–332. Amer. Math. Soc., Providence, R. I., 1973.
8
M. R. MURTY AND K. L. PETERSEN
M.Ram Murty Department of Mathematics and Statistics Queen’s University Kingston, ON K7L 3N6, Canada email: [email protected] Kathleen L. Petersen Department of Mathematics Florida State University Tallahassee, FL 32303, USA email: [email protected]