betaFeedback

WorksMathematics

Orders in the Euclidean Court

Abstract

Following Johnson, Queen, and Sevilla, we call an order O\mathcal{O} in a number field KK \textsf{generalized Euclidean} if for all α,β∈Oα,β\in \mathcal{O} with β≠0β\ne 0 for which αO+βOα\mathcal{O}+β\mathcal{O} is a principal ideal of O\mathcal{O}, there are γ,ρ∈Oγ, ρ\in \mathcal{O} with α=βγ+ρα=βγ+ ρ and ∣NK/Q(ρ)∣<∣NK/Q(β)∣|N_{K/\mathbb{Q}}(ρ)| < |N_{K/\mathbb{Q}}(β)|. We prove that only finitely many quadratic orders are generalized Euclidean. Additionally, assuming GRH, we show that for each fixed d>1d > 1 there are only finitely many integers mm for which Td−mT^d-m is irreducible over Q\mathbb{Q} and Z[m1/d]=Z[T]/(Td−m)\mathbb{Z}[m^{1/d}] = \mathbb{Z}[T]/(T^d-m) is generalized Euclidean. When dd is even, we can remove the assumption of GRH.

Introduction

Let KK be a number field with ring of integers OK\mathcal{O}_K. One calls OK\mathcal{O}_K norm-Euclidean if, for every pair of α,β∈OK\alpha,\beta\in\mathcal{O}_K with β≠0\beta\ne0, there are γ,ρ∈OK\gamma,\rho\in\mathcal{O}_K for which

α=βγ+ρand∣NK/Q(ρ)∣<∣NK/Q(β)∣.(1)\alpha=\beta\gamma+\rho\qquad\text{and}\qquad\lvert N_{K/\mathbb{Q}}(\rho)\rvert< \lvert N_{K/\mathbb{Q}}(\beta)\rvert. \tag*{(1)}

If OK\mathcal{O}_K is norm-Euclidean, then every pair of α,β∈OK\alpha,\beta\in\mathcal{O}_K has a gcd δ∈OK\delta\in\mathcal{O}_K that can be determined, in principle, by the Euclidean algorithm. As explained in a first algebra course, it follows that OK\mathcal{O}_K 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 O\mathcal{O} generalized Euclidean if for all α,β∈O\alpha,\beta\in\mathcal{O} with β≠0\beta\ne0 and (α,β)(\alpha,\beta) principal, there exists γ,ρ∈O\gamma,\rho\in\mathcal{O} satisfying (1). In other words, if the gcd of α\alpha and β\beta 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 Q(d)\mathbb{Q}(\sqrt{d}) when d≡1(mod4)d \equiv1 \pmod{4}. 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 Z[−3]\mathbb{Z}[\sqrt{-3}], which is nonmaximal with respect to the field K:=Q(−3)K := \mathbb{Q}(\sqrt{-3}).

Lacking a reference, we prove here that Z[−3]\mathbb{Z}[\sqrt{-3}] is generalized Euclidean. Let α,β∈Z[−3]\alpha,\beta\in\mathbb{Z}[\sqrt{-3}] with β≠0\beta\ne0, and write α/β=U+V−3\alpha/\beta= U+V\sqrt{-3} with U,V∈QU,V \in\mathbb{Q}. Let u,vu,v be the integers nearest to U,VU,V, rounding down when the distance to the nearest integer is precisely 12\frac{1}{2}. Let γ=u+v−3\gamma=u+v\sqrt{-3} and define ρ\rho by (1). Then NK/Q(ρ)=NK/Q(β)((U−u)2+3(V−v)2)<NK/Q(β)N_{K/\mathbb{Q}}(\rho)=N_{K/\mathbb{Q}}(\beta)((U-u)^2+3(V-v)^2)<N_{K/\mathbb{Q}}(\beta), unless U=u+12U=u+\frac{1}{2} and V=v+12V=v+\frac{1}{2}. (We omit absolute value signs around our norms, since norms from Q(−3)\mathbb{Q}(\sqrt{-3}) are nonnegative.) So to show Z[−3]\mathbb{Z}[\sqrt{-3}] is generalized Euclidean, it is enough to show that I:=(α,β)I:=(\alpha,\beta) is nonprincipal in this exceptional case. When this case arises, 2α=2βγ+(1+−3)β2\alpha=2\beta\gamma+(1+\sqrt{-3})\beta, so that

2I=(2α,2β)=(2β,(1+−3)β)=β(2,1+−3).2I=(2\alpha,2\beta)=(2\beta,(1+\sqrt{-3})\beta)=\beta(2,1+\sqrt{-3}).

Suppose for a contradiction that II is principal, say I=(δ)I=(\delta). Then 2I=(2δ)2I=(2\delta), β∣2δ\beta\mid2\delta, and J:=(2,1+−3)=(2δ/β)J:=(2,1+\sqrt{-3})=(2\delta/\beta) is principal. But it is straightforward to check that JJ is nonprincipal. For instance, 22 and 1+−31+\sqrt{-3} are nonassociate irreducibles in Z[−3]\mathbb{Z}[\sqrt{-3}], so that JJ could not be generated by anything other than a unit. But every element of JJ has even norm, and so 1∉J1\notin J.

We may also consider more general orders. Fix an integer d≥2d\ge2. If mm is an integer for which the polynomial Fd,m(T):=Td−mF_{d,m}(T):=T^d-m is irreducible over Q\mathbb{Q}, we let Kd,m=Q(m1/d)K_{d,m}=\mathbb{Q}(m^{1/d}) and Od,m:=Z[m1/d]\mathcal{O}_{d,m}:=\mathbb{Z}[m^{1/d}]. Then Od,m\mathcal{O}_{d,m} is an order inside the number field Kd,mK_{d,m}; we will refer to Od,m\mathcal{O}_{d,m} as a pure order of degree dd.

Theorem 2. Fix an even positive integer dd. There are finitely many pure orders of degree dd that are generalized Euclidean.

Theorem 3. Assume GRH. For any fixed integer d≥2d\ge2, there are finitely many pure orders of degree dd that are generalized Euclidean.

One might be interested in comparing Theorems 2 and 3 with results of Egami (see [1]) for the fields Q(m1/p)\mathbb{Q}(m^{1/p}), pp prime. However, the notion of Q(m1/p)\mathbb{Q}(m^{1/p}) 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 d≥2d \ge2. Let Od,m\mathcal{O}_{d,m} be a pure order of degree dd. Suppose there are positive integers a,ba,b with

∣m∣=a+b,|m| = a + b,

where

(i) gcd⁡(a,m)=1\gcd(a,m) = 1,

(ii) aa is a ddth power modulo mm,

(iii) neither aa nor −b-b has the form NKd,m/Q(α)N_{K_{d,m}/\mathbb{Q}}(\alpha) for any α∈Od,m\alpha\in\mathcal{O}_{d,m}.

Then Od,m\mathcal{O}_{d,m} is not generalized Euclidean.

Recall that to each quadratic order O\mathcal{O} there is associated a unique integer DD for which either

O={a+bD:a,b∈Z}(2)\mathcal{O} = \{a + b\sqrt{D} : a,b \in\mathbb{Z}\} \tag*{(2)}

or

O={12(a+bD):a,b∈Z,a≡b(mod2)}.(3)\mathcal{O} = \left\{\frac{1}{2}(a + b\sqrt{D}) : a,b \in\mathbb{Z}, a \equiv b \pmod{2}\right\}. \tag*{(3)}

The first case occurs when the order discriminant Δ\Delta is a multiple of 44, in which case D=Δ/4D = \Delta/4, and the second case when Δ≡1(mod4)\Delta\equiv1 \pmod{4}, in which case D=ΔD = \Delta. In both cases, DD is not a perfect square.

Proposition 5 (Heilbronn’s criterion for quadratic orders). Let O\mathcal{O} be an order in a quadratic field KK, and let D∈ZD \in\mathbb{Z} be such that (2) or (3) holds. Suppose there are positive integers a,ba,b with

∣D∣=a+b,|D| = a + b,

where

(i) gcd⁡(a,D)=1\gcd(a,D) = 1,

(ii) aa is a square modulo DD,

(iii) neither aa nor −b-b has the form NQ(D)/Q(α)N_{\mathbb{Q}(\sqrt{D})/\mathbb{Q}}(\alpha) for any α∈O\alpha\in\mathcal{O}.

Then O\mathcal{O} is not generalized Euclidean.

Proposition 5 does not quite follow from Proposition 4; when D≡1(mod4)D \equiv1 \pmod{4}, the corresponding order O\mathcal{O} is not O2,m\mathcal{O}_{2,m} for any mm.

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 d≥2d \ge2, and let Od,m\mathcal{O}_{d,m} be a pure order of degree dd. Let N~(x0,…,xd−1)\widetilde{N}(x_0,\ldots,x_{d-1}) be the norm form associated to the Q\mathbb{Q}-basis 1,m1/d,…,m(d−1)/d1,m^{1/d},\ldots,m^{(d-1)/d} of Kd,mK_{d,m}. That is, N~(x0,…,xd−1)\widetilde{N}(x_0,\ldots,x_{d-1}) is the polynomial in x0,…,xd−1x_0,\ldots,x_{d-1} defined by

N~(x0,x1,…,xd−1)=∏σ:Kd,m↪C(x0+x1σ(m1/d)+⋯+xd−1σ(m(d−1)/d)).\widetilde{N}(x_0,x_1,\ldots,x_{d-1})=\prod_{\sigma:K_{d,m}\hookrightarrow\mathbb{C}}\left(x_0+x_1\sigma(m^{1/d})+\cdots+x_{d-1}\sigma(m^{(d-1)/d})\right).

where σ\sigma runs over all the embeddings of Kd,mK_{d,m} into C\mathbb{C}. Then N~(x0,…,xd−1)∈x0d+mZ[x0,…,xd−1]\widetilde{N}(x_0,\ldots,x_{d-1})\in x_0^d+m\mathbb{Z}[x_0,\ldots,x_{d-1}].

Proof. Define a polynomial N~(x,t)\widetilde{N}(\mathbf{x},\mathbf{t}) in indeterminates x=x0,…,xd−1\mathbf{x}=x_0,\ldots,x_{d-1} and t=t0,…,td−1\mathbf{t}=t_0,\ldots,t_{d-1} by setting

N~(x,t):=∏j=0d−1(x0+x1tj+x2tj2+⋯+xd−1tjd−1).\widetilde{N}(\mathbf{x},\mathbf{t}):=\prod_{j=0}^{d-1}(x_0+x_1t_j+x_2t_j^2+\cdots+x_{d-1}t_j^{d-1}).

Then N~(x,t)\widetilde{N}(\mathbf{x},\mathbf{t}) can be viewed as a polynomial in t\mathbf{t} over Z[x]\mathbb{Z}[\mathbf{x}], symmetric with respect to the tjt_j. By the fundamental theorem of symmetric polynomials, N~(x,t)\widetilde{N}(\mathbf{x},\mathbf{t}) is a polynomial, with Z[x]\mathbb{Z}[\mathbf{x}] coefficients, in the elementary symmetric functions of the tjt_j.

Continuing, we introduce a new indeterminate ZZ, and we let ωj:=exp⁡(2πij/d)\omega_j:=\exp(2\pi i j/d). Replacing each tjt_j by ωjZ\omega_jZ, we conclude from our work in the last paragraph that

N~(x,Z):=∏j=0d−1(x0+x1ωjZ+x2ωj2Z2+⋯+xd−1ωjd−1Zd−1)(4)\widetilde{N}(\mathbf{x},Z):=\prod_{j=0}^{d-1}(x_0+x_1\omega_jZ+x_2\omega_j^2Z^2+\cdots+x_{d-1}\omega_j^{d-1}Z^{d-1}) \tag*{(4)}

is a polynomial over Z[x]\mathbb{Z}[\mathbf{x}] in the elementary symmetric functions of the ωjZ\omega_jZ. These elementary symmetric functions all vanish, except for the last one (the ddth), which is ±Zd\pm Z^d; this can be read off from the formal expansion ∏j=0d−1(T−ωjZ)=Td−Zd\prod_{j=0}^{d-1}(T-\omega_jZ)=T^d-Z^d. We conclude that N~(x,Z)\widetilde{N}(\mathbf{x},Z) is a polynomial in x0,…,xd−1x_0,\ldots,x_{d-1} and ZdZ^d, with integer coefficients. Setting Z=0Z=0 in (4), we deduce that

N~(x,Z)=x0d+ZdQfor some Q∈Z[x,Zd].\widetilde{N}(\mathbf{x},Z)=x_0^d+Z^dQ\quad\text{for some }Q\in\mathbb{Z}[\mathbf{x},Z^d].

To finish, it remains only to observe that

N~(x0,x1,…,xd−1)=N~(x,m1/d),\widetilde{N}(x_0,x_1,\ldots,x_{d-1})=\widetilde{N}(\mathbf{x},m^{1/d}),

so that

N~(x0,x1,…,xd−1)∈x0d+mZ[x0,…,xd−1],\widetilde{N}(x_0,x_1,\ldots,x_{d-1})\in x_0^d+m\mathbb{Z}[x_0,\ldots,x_{d-1}],

as claimed. □

Proof of Proposition 4. It is convenient to abbreviate Od,m\mathcal{O}_{d,m} to O\mathcal{O} throughout the proof, and to write NN in place of NKd,m/QN_{K_{d,m}/\mathbb{Q}}. Suppose for a contradiction that O\mathcal{O} is generalized Euclidean. Using conditions (i) and (ii), we may choose A∈ZA\in\mathbb{Z} with AA coprime to mm and Ad≡a(modmZ)A^d\equiv a\pmod{m\mathbb{Z}}. Since

AO+m1/dO⊇AZ+mZ=Z,A\mathcal{O}+m^{1/d}\mathcal{O}\supseteq A\mathbb{Z}+m\mathbb{Z}=\mathbb{Z},

the O\mathcal{O}-ideal generated by AA and m1/dm^{1/d} is all of O\mathcal{O}, and in particular is principal. As O\mathcal{O} is generalized Euclidean, there is an α∈O\alpha\in\mathcal{O} with A≡α(modm1/dO)A \equiv\alpha\pmod{m^{1/d}\mathcal{O}} and ∣N(α)∣<∣N(m1/d)∣=∣m∣\lvert N(\alpha)\rvert< \lvert N(m^{1/d})\rvert= \lvert m\rvert. Write

α=A0+A1m1/d+⋯+Ad−1m(d−1)/d.\alpha= A_0 + A_1m^{1/d} + \cdots+ A_{d-1}m^{(d-1)/d}.

Then A≡α≡A0(modm1/dO)A \equiv\alpha\equiv A_0 \pmod{m^{1/d}\mathcal{O}}, so that (A−A0)/m1/d∈O(A-A_0)/m^{1/d} \in\mathcal{O}. But

A−A0m1/d=A−A0mm(d−1)/d;\frac{A-A_0}{m^{1/d}} = \frac{A-A_0}{m}m^{(d-1)/d};

as O=Z[m1/d]\mathcal{O} = \mathbb{Z}[m^{1/d}], for the final displayed expression to land in O\mathcal{O} requires that (A−A0)/m∈Z(A-A_0)/m \in\mathbb{Z}. Hence, A0≡A(modm)A_0 \equiv A \pmod m. By Lemma 6,

N(α)=N~(A0,…,Ad−1)≡A0d≡Ad≡a(modmZ).\begin{aligned} N(\alpha) &= \widetilde{N}(A_0,\ldots,A_{d-1})\\ &\equiv A_0^d \equiv A^d \equiv a \pmod{m\mathbb{Z}}. \end{aligned}

We have 0<a<∣m∣0<a<\lvert m\rvert and ∣N(α)∣<∣m∣\lvert N(\alpha)\rvert<\lvert m\rvert. If 0≤N(α)<∣m∣0\leq N(\alpha)<\lvert m\rvert, then the congruence N(α)≡a(modmZ)N(\alpha)\equiv a\pmod{m\mathbb{Z}} forces a=N(α)a=N(\alpha). Similarly, if −∣m∣<N(α)≤0-\lvert m\rvert<N(\alpha)\leq0, then −b=a−∣m∣=N(α)-b=a-\lvert m\rvert=N(\alpha). 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 A∈ZA\in\mathbb{Z}, gcd⁡(A,D)=1\gcd(A,D)=1, with A2≡a(modD)A^2\equiv a\pmod D. Then AO+DO⊇AZ+DZ=ZA\mathcal{O}+\sqrt{D}\mathcal{O}\supseteq A\mathbb{Z}+D\mathbb{Z}=\mathbb{Z}. Hence, A,DA,\sqrt{D} generate the unit ideal of O\mathcal{O}. Thus, assuming O\mathcal{O} is generalized Euclidean, there is an α∈O\alpha\in\mathcal{O} with A≡α(modDO)A\equiv\alpha\pmod{\sqrt{D}\mathcal{O}} and ∣N(α)∣<∣N(D)∣=∣D∣\lvert N(\alpha)\rvert<\lvert N(\sqrt{D})\rvert=\lvert D\rvert, where NN denotes the norm NQ(D)/QN_{\mathbb{Q}(\sqrt{D})/\mathbb{Q}}.

Let σ\sigma denote the nontrivial automorphism of Q(D)\mathbb{Q}(\sqrt{D}). Since σ\sigma carries DO\sqrt{D}\mathcal{O} into DO\sqrt{D}\mathcal{O}, the congruence

A≡α(modDO)A\equiv\alpha\pmod{\sqrt{D}\mathcal{O}}

implies

A≡σ(α)(modDO).A\equiv\sigma(\alpha)\pmod{\sqrt{D}\mathcal{O}}.

Thus, A2≡ασ(α)≡N(α)(modDO)A^2\equiv\alpha\sigma(\alpha)\equiv N(\alpha)\pmod{\sqrt{D}\mathcal{O}}, and

A2−N(α)D=A2−N(α)DD∈O.\frac{A^2-N(\alpha)}{\sqrt{D}}=\frac{A^2-N(\alpha)}{D}\sqrt{D}\in\mathcal{O}.

Regardless of whether we are in case (2) or (3), this last containment forces (A2−N(α))/D∈Z(A^2-N(\alpha))/D\in\mathbb{Z}. Hence,

a≡A2≡N(α)(modDZ).a\equiv A^2\equiv N(\alpha)\pmod{D\mathbb{Z}}.

Reasoning as in Proposition 4, we deduce from ∣N(α)∣<∣D∣\lvert N(\alpha)\rvert<\lvert D\rvert that either N(α)=aN(\alpha)=a or N(α)=−bN(\alpha)=-b, contradicting (iii). □

Proofs of Theorems 1–3

Theorems 1–3 follow immediately from Propositions 4 and 5 via the following lemmata.

Lemma 7. Let Od,m\mathcal{O}_{d,m} be a pure order of even degree d≥2d \ge2. Provided ∣m∣|m| is sufficiently large, there are positive integers a,ba,b with ∣m∣=a+b|m|=a+b and conditions (i)–(iii) of Proposition 4 satisfied.

Lemma 8. Let O\mathcal{O} be a quadratic order with D∈ZD \in\mathbb{Z} satisfying (2) or (3). Provided ∣D∣|D| is sufficiently large, there are positive integers a,ba,b with ∣D∣=a+b|D|=a+b and conditions (i)–(iii) of Proposition 5 satisfied.

Lemma 9. Assume GRH. Let d≥2d \ge2. For every m∈Zm \in\mathbb{Z} with ∣m∣|m| sufficiently large, there are positive integers a,ba,b with ∣m∣=a+b|m|=a+b 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 ϵ>0\epsilon> 0, there are m0=m0(ϵ)m_0=m_0(\epsilon) and κ=κ(ϵ)>0\kappa=\kappa(\epsilon)>0 for which the following holds. For all m>m0m>m_0 and every nontrivial Dirichlet character χ\chi mod mm, there are more than mκm^\kappa primes q≤m14e+ϵq \le m^{\frac{1}{4\sqrt{e}}+\epsilon} for which χ(q)∉{0,1}\chi(q) \notin\{0,1\}.

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 d,md,m have the meanings of that lemma, K=Kd,mK=K_{d,m} and O=Od,m\mathcal{O}=\mathcal{O}_{d,m}. If we are considering Lemma 8, we take d=2d=2, m=Dm=D, K=Q(D)K=\mathbb{Q}(\sqrt{D}) and O\mathcal{O} the quadratic order appearing in that lemma.

To start with, we produce positive integers aa and bb summing to ∣m∣|m| 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 aa and bb also satisfies condition (iii) of these Propositions.

Let χ\chi be the quadratic character mod 4∣m∣4|m| given by χ(n)=(4mn)\chi(n)=\left(\frac{4m}{n}\right) (the Kronecker symbol), and note that if χ(q)∉{0,1}\chi(q)\notin\{0,1\} for the prime qq, then qq is odd and (mq)=−1\left(\frac{m}{q}\right)=-1. By Proposition 10, it follows that for all ϵ>0\epsilon>0, there is a κ>0\kappa>0 with

#{q≤∣m∣14e+ϵ:q odd prime, (mq)=−1}≥∣m∣κ\#\left\{q\le|m|^{\frac{1}{4\sqrt{e}}+\epsilon}:q\text{ odd prime},\ \left(\frac{m}{q}\right)=-1\right\}\ge|m|^\kappa

whenever mm is sufficiently large in absolute value. Since 4e>64\sqrt{e}>6, we can take, for mm large in absolute value, 2<q1<q2≤∣m∣1/62<q_1<q_2\le|m|^{1/6} with (mq1)=(mq2)=−1\left(\frac{m}{q_1}\right)=\left(\frac{m}{q_2}\right)=-1. (In particular, q1,q2∤mq_1,q_2\nmid m.)

We now proceed to count the number of integers a′,b′a',b' for which

q1a′+q2b′=∣m∣(5)q_1a'+q_2b'=|m| \tag*{(5)}

and for which all of the following hold:

  1. 0<a′<∣m∣q10<a'<\frac{|m|}{q_1};

  1. q1a′q_1a' is a ddth power mod mm with gcd⁡(q1a′,m)=1\gcd(q_1a',m)=1;

  1. q1∤a′q_1\nmid a';

  1. q2∤b′q_2\nmid b'.

If at least one such pair of a′,b′a',b' exist, then conditions (i) and (ii) in Proposition 4 (or Proposition 5) are satisfied by taking a=q1a′,b=q2b′a=q_1a',b=q_2b'.

(5) implies that b′=(∣m∣−q1a′)/q2b'=(|m|-q_1a')/q_2 is entirely determined by a′a'. So we can phrase the problem entirely in terms of counting certain integers a′a'. To ensure b′b' is an integer, we tack on the condition

  1. a′≡∣m∣q1−1(modq2)a'\equiv|m|q_1^{-1}\pmod{q_2}.

Our task then becomes counting all the integers a′a' simultaneously satisfying conditions 1–5, thinking of condition 4 as a′≢∣m∣q1−1(modq22)a'\not\equiv|m|q_1^{-1}\pmod{q_2^2}.

We detect condition 2 using character sums; we have that

1N∑χd=χ0χ(a)={1if a is a dth power mod m and gcd⁡(a,m)=1;0otherwise,\frac{1}{N}\sum_{\substack{\chi^d=\chi_0}}\chi(a)=\begin{cases}1 & \text{if } a \text{ is a } d\text{th power mod }m\text{ and }\gcd(a,m)=1;\\0 & \text{otherwise,}\end{cases}

where NN is the number of characters χ\chi mod mm satisfying χd=χ0\chi^d=\chi_0.

We use an inclusion-exclusion argument to account for conditions 3 and 4. We thus write our count as

1N∑0≤i,j≤1(−1)i+j∑a′(i,j)∑χd=χ0χ(q1a′)\frac{1}{N}\sum_{0\leq i,j\leq1}(-1)^{i+j}\sum_{a'}^{(i,j)}\sum_{\chi^d=\chi_0}\chi(q_1a')

where the sums ∑a′(i,j)\sum_{a'}^{(i,j)} are taken over all a′a' satisfying conditions 1 and 5, but possibly violating conditions 3 and/or 4: here i=1i=1 if (and only if) condition 3 is violated, and j=1j=1 if (and only if) 4 is violated.

We proceed to estimate the sums ∑a′(i,j)∑χd=χ0χ(q1a′)\sum_{a'}^{(i,j)}\sum_{\chi^d=\chi_0}\chi(q_1a'). First, we look at the contribution of the nonprincipal characters. A violation of condition 3 means that we have a′≡0(modq1)a'\equiv0\pmod{q_1}. Similarly, a violation of condition 4 means that condition 5 can be strengthened to a′≡∣m∣q1−1(modq22)a'\equiv|m|q_1^{-1}\pmod{q_2^2}. Thus, depending on ii and jj, we have by the Chinese Remainder Theorem that each a′a' lies in one specific residue class mod mi,j:=q1iq2j+1m_{i,j}:=q_1^{i}q_2^{j+1}, i.e., we can write a′=ai,j+nmi,ja'=a_{i,j}+nm_{i,j} where nn lies in an interval Ii,jI_{i,j} of length ∣m∣/(q1i+1q2j+1)|m|/(q_1^{i+1}q_2^{j+1}).

We then write, for each χ≠χ0\chi\ne\chi_0,

∑a′(i,j)χ(q1a′)=χ(q1)∑a′(i,j)χ(a′)=χ(q1)∑n∈Ii,jχ(nmi,j+ai,j)=χ(q1)χ(mi,j)∑n∈Ii,jχ(n+ai,jmi,j−1)=O(∣m∣log⁡∣m∣)\begin{aligned} \sum_{a'}^{(i,j)} \chi(q_1a') &= \chi(q_1)\sum_{a'}^{(i,j)}\chi(a') \\ &= \chi(q_1)\sum_{n\in I_{i,j}}\chi(nm_{i,j}+a_{i,j}) \\ &= \chi(q_1)\chi(m_{i,j})\sum_{n\in I_{i,j}}\chi(n+a_{i,j}m_{i,j}^{-1}) \\ &= O\left(\sqrt{|m|}\log|m|\right) \end{aligned}

by Pólya–Vinogradov. Here we write mi,j−1m_{i,j}^{-1} for the inverse of mi,jm_{i,j} mod mm.

We now look at the contribution of the principal character. We write

∑a′(i,j)χ0(q1a′)=∑a′(i,j)χ0(a′)=∑a′(i,j)1gcd⁡(a′,m)=1=∑a′(i,j)∑e∣gcd⁡(a′,m)μ(e)=∑e∣mμ(e)∑a′(i,j)1e∣a′=∑e∣mμ(e)(∣m∣eq1i+1q2j+1+O(1))=φ(∣m∣)q1i+1q2j+1+O(2ω(∣m∣)).\begin{aligned} \sum_{a'}^{(i,j)}\chi_0(q_1a') &= \sum_{a'}^{(i,j)}\chi_0(a') \\ &= \sum_{a'}^{(i,j)}\mathbf{1}_{\gcd(a',m)=1} \\ &= \sum_{a'}^{(i,j)}\sum_{e\mid\gcd(a',m)}\mu(e) \\ &= \sum_{e\mid m}\mu(e)\sum_{a'}^{(i,j)}\mathbf{1}_{e\mid a'} \\ &= \sum_{e\mid m}\mu(e)\left(\frac{|m|}{eq_1^{i+1}q_2^{j+1}}+O(1)\right) \\ &= \frac{\varphi(|m|)}{q_1^{i+1}q_2^{j+1}}+O\left(2^{\omega(|m|)}\right). \end{aligned}

Collecting estimates,

∑a′(i,j)∑χd=χ0χ(q1a′)=φ(∣m∣)q1i+1q2j+1+O(2ω(∣m∣))+O(N∣m∣log⁡∣m∣).\sum_{a'}^{(i,j)}\sum_{\chi^d=\chi_0}\chi(q_1a')=\frac{\varphi(|m|)}{q_1^{i+1}q_2^{j+1}}+O\left(2^{\omega(|m|)}\right)+O\left(N\sqrt{|m|}\log|m|\right).

Putting everything together, we get that, as ∣m∣→∞|m|\to\infty, the number of integer solutions a,ba,b to (5) satisfying conditions 1–5 is

φ(∣m∣)Nq1q2(1−1q1)(1−1q2)+O(2ω(∣m∣)N)+O(∣m∣log⁡∣m∣).\frac{\varphi(|m|)}{Nq_1q_2}\left(1-\frac{1}{q_1}\right)\left(1-\frac{1}{q_2}\right)+O\left(\frac{2^{\omega(|m|)}}{N}\right)+O\left(\sqrt{|m|}\log|m|\right).

Let us estimate the various terms in this expression. Writing τ\tau for the divisor function, we have 2ω(∣m∣)≤τ(∣m∣)≤∣m∣o(1)2^{\omega(|m|)}\leq\tau(|m|)\leq|m|^{o(1)} (see Theorem 315 in [4] for this last bound on τ\tau). Since the multiplicative group mod mm has a direct product decomposition into at most ω(∣m∣)+1\omega(|m|) + 1 cyclic groups (see for instance [IR90, Theorem 3, p. 44),

N≤d⋅dω(∣m∣)≤d⋅2dω(∣m∣)≤d⋅τ(∣m∣)d≤∣m∣o(1).N \le d \cdot d^{\omega(|m|)} \le d \cdot2^{d\omega(|m|)} \le d \cdot\tau(|m|)^d \le|m|^{o(1)}.

Furthermore, Theorem 327 in [4] ensures that for sufficiently large ∣m∣|m|, we have φ(∣m∣)≥∣m∣0.99\varphi(|m|) \ge|m|^{0.99}. Putting these estimates together, keeping in mind that q1,q2≤∣m∣1/6q_1,q_2 \le|m|^{1/6}, we see that the main term in the last display exceeds m0.6m^{0.6} for large ∣m∣|m|, while the contribution of the OO-terms is smaller than m0.51m^{0.51} (say). In particular, the displayed expression is positive for all large ∣m∣|m|, allowing us to find our a′,b′a',b'.

Finally we return to proving our choices of aa and bb satisfy part (iii) of Propositions 4 and 5. Suppose that a=N(α)a = N(\alpha), with α∈O\alpha\in\mathcal{O}. We consider the prime factorization of αOK\alpha\mathcal{O}_K in the Dedekind domain OK\mathcal{O}_K. By our condition 3 above, q1∥aq_1 \mathrel{\|} a. Thus, the prime factorization of αOK\alpha\mathcal{O}_K contains a unique prime ideal Q1Q_1 lying above q1q_1; furthermore, Q1Q_1 has degree one. Then OK/Q1≅Z/q1Z\mathcal{O}_K/Q_1 \cong\mathbb{Z}/q_1\mathbb{Z}, with the isomorphism induced by the inclusion of Z\mathbb{Z} into OK\mathcal{O}_K. Since m=(m1/d)dm = (m^{1/d})^d is a ddth power in OK\mathcal{O}_K, it is also a ddth power in OK/Q1\mathcal{O}_K/Q_1 and thus in Z/q1Z\mathbb{Z}/q_1\mathbb{Z}. But dd is even, and so the stipulation that mm is a quadratic nonresidue modulo q1q_1 implies that mm is not a ddth power modulo q1q_1. This contradiction establishes that aa is not a norm in O\mathcal{O}. An entirely analogous argument shows that −b-b is not a norm in O\mathcal{O}. Here we use that q2∥bq_2 \mathrel{\|} b (by condition 4 above) and that mm is a quadratic nonresidue modulo q2q_2. □

We now settle Lemma 9. In view of Lemma 7, we may assume dd is odd. We make use of the following GRH-conditional version of the Chebotarev density theorem:

Proposition 11. Assume GRH. Let E/QE/\mathbb{Q} be a finite Galois extension of number fields, and let GG be the Galois group of E/QE/\mathbb{Q}. Let CC be a subset of GG that is invariant under conjugation. Let πC(x)\pi_C(x) denote the number of primes up to xx whose associated Frobenius conjugacy class is in CC. Let PP be the product of the distinct rational primes ramifying in EE. Then

∣πC(x)−∣C∣∣G∣Li⁡(x)∣≤A∣C∣x1/2log⁡([E:Q]Px)\left|\pi_C(x)-\frac{|C|}{|G|}\operatorname{Li}(x)\right| \le A|C|x^{1/2}\log([E:\mathbb{Q}]Px)

for some absolute constant AA.

Proposition 11 is the special case of Serre's [8 eq. (20_R)] where K=QK = \mathbb{Q}.

Proof of Lemma 9. Let d>1d > 1 be odd, and let p>2p > 2 be the least prime dividing dd. Arguing as in the proof of Lemma 7, it is enough to show that there are two primes q1<q2≤∣m∣1/6q_1 < q_2 \le|m|^{1/6}, not dividing mm, modulo which mm is not a ppth power.

We let ζp=e2πi/p\zeta_p = e^{2\pi i/p} and we consider E:=Q(m1/p,ζp)E := \mathbb{Q}(m^{1/p},\zeta_p), the splitting field of the polynomial Tp−mT^p-m. As EE is the normal closure of K:=Q(m1/p)K := \mathbb{Q}(m^{1/p}), every prime ramifying in EE divides disc⁡(K)\operatorname{disc}(K), which in turn divides disc⁡(Tp−m)=(−1)(p−1)/2ppmp−1\operatorname{disc}(T^p-m) = (-1)^{(p-1)/2}p^pm^{p-1}. Hence: Every prime ramifying in EE divides mpmp. This observation will be useful momentarily when we apply Proposition 11.

Let qq be a prime not dividing mpmp. In order that mm not be a ppth power modulo qq, it is sufficient that the action of the Frobenius conjugacy class associated to qq, on the roots of Tp−mT^p-m, have no fixed points. We let CC be the (conjugation-invariant) set of fixed-point-free elements of GG.

The Galois group GG of E/QE/\mathbb{Q} is made up of p(p−1)p(p-1) elements σj,k\sigma_{j,k} for 0≤j≤p−10\le j\le p-1, 1≤k≤p−11\le k\le p-1, determined by the conditions that σj,k(m1/p):=m1/pζpj\sigma_{j,k}(m^{1/p}):=m^{1/p}\zeta_p^j, σj,k(ζp):=ζpk\sigma_{j,k}(\zeta_p):=\zeta_p^k. Furthermore, it is straightforward to check that the set CC defined above is precisely the collection of σj,1\sigma_{j,1} with j≠0j\ne0. Hence, ∣C∣/∣G∣=1/p|C|/|G|=1/p.

Applying Proposition 11, we conclude that ∣πC(x)−1pLi⁡(x)∣≤Adx1/2log⁡∣pmx∣\left|\pi_C(x)-\frac{1}{p}\operatorname{Li}(x)\right|\le A_d x^{1/2}\log|pmx| for some constant AdA_d depending only on dd. It follows that

πC(x)≥1pLi⁡(x)−Adx1/2log⁡∣pmx∣.(6)\pi_C(x)\ge\frac{1}{p}\operatorname{Li}(x)-A_d x^{1/2}\log|pmx|. \tag*{(6)}

It is certainly possible to choose our two primes q1,q2q_1,q_2 as long as

πC(∣m∣1/6)≥2+ω(p∣m∣).(7)\pi_C(|m|^{1/6})\ge2+\omega(p|m|). \tag*{(7)}

We will show this inequality holds for x=(log⁡∣m∣)3x=(\log|m|)^3, provided mm is large enough. As (log⁡∣m∣)3≤∣m∣1/6(\log|m|)^3\le|m|^{1/6} for large ∣m∣|m|, this suffices.

Allowing implied constants to depend on dd (which is fixed), we have Li⁡(x)≫log⁡3∣m∣/log⁡log⁡∣m∣\operatorname{Li}(x)\gg\log^3|m|/\log\log|m|, while x1/2log⁡∣pmx∣≪log⁡5/2∣m∣x^{1/2}\log|pmx|\ll\log^{5/2}|m|. Hence, (6) yields πC(x)≫log⁡3∣m∣/log⁡log⁡∣m∣\pi_C(x)\gg\log^3|m|/\log\log|m| for large ∣m∣|m|. On the other hand, ω(p∣m∣)≪log⁡∣m∣\omega(p|m|)\ll\log|m|, which is of smaller order. Thus (7) holds whenever ∣m∣|m| 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. [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. [2][EK38] P. Erdős and C. Ko, Note on the Euclidean Algorithm, J. London Math. Soc. 13 (1938), 3–8.DOI
  3. [3][Hei38] H. Heilbronn, On Euclid’s algorithm in real quadratic fields, Proc. Camb. Philos. Soc. 34 (1938), 521–526.DOI
  4. [4][HW08] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, sixth ed., Oxford University Press, Oxford, 2008.
  5. [6][JQS85] D. H. Johnson, C. S. Queen, and A. N. Sevilla, Euclidean real quadratic number fields, Arch. Math. (Basel) 44 (1985), 340–347.
  6. [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
  7. [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.

Paper details

vlnc:W_dby4ghy2
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 11

downloads · 4

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents