Counting Integers with Restrictions on their Prime FactorsbyJenna DowneyA THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTSFOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)April, 2019c© Jenna Downey, 2019The following individuals certify that they have read, and recommend to the Faculty of Graduate and Post-doctoral Studies for acceptance, a thesis/dissertation entitled:Counting Integers with Restrictions on their Prime Factorssubmitted by Jenna Downey in partial fulfillment of the requirement forthe degree of Master of Sciencein MathematicsExamining Committee:Michael Bennett, MathematicsCo-supervisorGreg Martin, MathematicsCo-supervisoriiAbstractIn this thesis, we examine two problems that, on the surface, seem like pure group theory problems, but turnout to both be problems concerning counting integers with restrictions on their prime factors. Fixing an oddprime number q and a finite abelian q-groupH = Zqα1×Zqα2×· · ·×Zqαj , our first aim is to find a countingfunction,D(H,x), for the number of integers n up to x such thatH is the Sylow q-subgroup of (Z/nZ)×. InChapter 2, we prove that D(H,x) ∼ KHx(log log x)j/(log x)1/(q−1), where KH is a constant dependingon H .The second problem that we examine in this thesis concerns counting the number of n up to x forwhich (Z/nZ)× is cyclic and for which (Z/nZ)× is maximally non-cyclic, where (Z/nZ)× is said to bemaximally non-cyclic if each of its invariant factors is squarefree. In Chapter 3, we prove that the numberof n up to x such that (Z/nZ)× is cyclic is asymptotic to 32x/ log x and that the number of n up to x suchthat (Z/nZ)× is maximally non-cyclic is asymptotic to Cfx/(log x)1−ξ, where ξ is Artin’s constant and Cfis the convergent product,Cf =1514Γ(ξ)limx→∞( ∏p≤xp−1 square-free(1 +1p+1p2)∏p≤x(1− 1p)ξ ).It turns out that both of these problems can be reduced to problems of counting integers with restrictionson their prime factors. This allows the problems to be addressed by classical techniques of analytic numbertheory.iiiLay SummaryIn mathematics, we have structures called groups, which are basically sets of objects which satisfy certaincharacteristics. If q is a prime number, a q-group is a group whose total number of elements is a power of q.A subgroup of a group G is a collection of elements in G who form a smaller group on their own and theSylow q-subgroup of G, is a subgroup which has qk elements, where qk is the largest power of q whichdivides the total number of elements in G.The first goal of this thesis is to fix an odd prime number q and a q-group H , and find a function thatcounts groups whose Sylow q-subgroup is H . The second goal of this thesis is to find functions that countsgroups that are maximally non-cyclic. Note that we define maximally non-cyclic in Chapter 3.ivPrefaceThis thesis is comprised of joint work with Dr. Greg Martin. We plan on submitting our results for publica-tion.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Counting Finite Abelian Groups with a Prescribed Sylow q-Subgroup . . . . . . . . . . . . . . . 32.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Selberg–Delange Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Other Important Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4 Evaluating D0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.5 Evaluating D1(H,x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.6 Evaluating Dk(H,x) for k ≥ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.7 Evaluating D(H,x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 Counting Function for Maximally Non-cyclic Multiplicative Groups . . . . . . . . . . . . . . . . 443.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.2 Useful Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.3 Counting integers n such that Z×n is maximally non-cyclic . . . . . . . . . . . . . . . . . . 554 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59viChapter 1IntroductionProblems concerning counting integers with restrictions on their prime factors has been a topic of interestto number theorists for many years. The study of squarefree integers, as well as friable integers (integerswithout large prime factors), are perfect examples of such problems. Of particular interest, in 1908, Landaupublished a paper [3] in which he investigated the question of counting integers up to x that can be written asthe sum of two squares. Fermat had previously shown that this problem was equivalent to counting integersn that satisfied the following condition: if p is a prime congruent to 3 modulo 4 and r is the largest positiveinteger such that pr divides n, then r is even. Similarly, in 2012, Ford, Luca and Moree published a paper [2]in which they investigated the problem of counting the number of integers n such that φ(n) is not divisibleby q, where q is some fixed prime number. This is equivalent to counting the number of integers n suchthat q2 does not divide n and if p is a prime divisor of n, then p is not congruent to 1 modulo q.Abstract algebra, and in particular, group theory, can be a useful perspective from which to analyze suchproblems. For instance, it turns out that Ford, Luca and Moree’s problem in [2] is equivalent to countingthe integers n up to x for which the Sylow q-subgroup of (Z/nZ)× is trivial. In response to a talk by LeeTroupe in 2017 at the Alberta Number Theory Days, Colin Weir asked if it was possible to count, for a fixedprime q and a fixed finite abelian q-group H , the number of n up to x for which H is the Sylow q-subgroupof (Z/nZ)×. This is the exact question that we will investigate throughout Chapter 2 of this thesis.Let Z×n = (Z/nZ)× be the multiplicative group of integers modulo n. Also, let q be a fixed odd primeand let Gq(n) denote the Sylow q-subgroup of Z×n , that is, the unique subgroup of Z×n of order qk, where qkis the highest power of q that divides φ(n). Note that, throughout Chapter 2, q is always considered tobe this fixed odd prime. Further, let (q;α1, α2, . . . , αj) denote the q-group Zqα1 × Zqα2 × · · · × Zqαj ,where α1, . . . , αj are positive integers, Zqαi is the cyclic group of integers modulo qαi for each i andα1 ≥ α2 ≥ · · · ≥ αj . Given a q-group, (q;α1, α2, . . . , αj), our goal is to count the number of positiveintegers n for which Gq(n) = (q;α1, α2, . . . , αj).1The main result of Chapter 2 is given in the following theorem.Theorem 1.0.1. For a finite abelian q-group H , let D(H,x) = #{n ≤ x : Gq(n) = H}. Suppose that q isan odd prime and that H = (q;α1, α2, . . . , αj). Then,D(H,x) = KH(x(log log x)j(log x)1/(q−1))+O(x(log log x)j−1(log x)1/(q−1)),where KH is a constant that depends on the group H that will be defined in Theorem 2.7.1.In Chapter 3, we shift our focus to a different problem concerning counting integers with restrictions ontheir prime factors. This problem involves cyclic and maximally non-cyclic groups, where a finite abeliangroup is said to be maximally non-cyclic if each of its invariant factors is squarefree. Here, we show that thenumber of n up to x such that Z×n is cyclic is asymptotic to 3/2 · x/ log x. The main result of this Chapter 3is given in the following theorem.Theorem 1.0.2. The number of integers n up to x such that Z×n is maximally non-cyclic is asymptotic toCfx/(log x)1−ξ, whereξ =∏p(1− 1p(p− 1))is Artin’s constant and Cf is the convergent product,Cf =1514Γ(ξ)limx→∞( ∏p≤xp−1 square-free(1 +1p+1p2)∏p≤x(1− 1p)ξ ).2Chapter 2Counting Finite Abelian Groups with aPrescribed Sylow q-Subgroup2.1 SetupIn order to achieve our goal, we will introduce the following useful notation. For a finite abelian q-group Hand a positive integer k, let D(H,x) be defined as in Theorem 1.0.1 and letDk(H,x) = #{n ≤ x : qk ‖ n,Gq(n) = H}, where qk ‖ n denotes that qk | n and qk+1 - n.We will spend most of this chapter evaluating D0((q;α1, . . . , αj), x), since, as we will show in Sections2.5 and 2.6, Dk((q;α1, . . . , αj), x) is closely related to D0((q;α1, . . . , αj), x), for all k ≥ 1. Since thisis the case where q - n, we can write n as the product of primes n = 2βpβ11 pβ22 · · · pβtt where β ≥ 0,β1, β2, . . . , βt > 0 and q 6= pi for each 1 ≤ i ≤ t. Then, we can apply Chinese Remainder Theorem, to getthatZ×n ∼= Z×2β × Z×pβ11 × Z×pβ22× · · · × Z×pβtt∼= Z×2β × Zφ(pβ11 ) × Zφ(pβ22 ) × · · · × Zφ(pβtt )∼= Z×2β × Zpβ1−11 × Zp1−1 × Zpβ2−12 × Zp2−1 × · · · × Zpβt−1t × Zpt−1.Now, note that Z×2βwill be isomorphic to the trivial group if β is 0 or 1, Z2 if β is 2 and Z2β−2 ×Z2 if βis at least 3. So, it follows that Z×2βwill not contribute to the Sylow q-subgroup since for any odd prime q,Gq(n) will be made up of only odd factors and the factorization of Z×2β only contains even factors. Also,note that since q 6= pi for each 1 ≤ i ≤ t, it follows that none of the Zpβi−1i factors will contribute to Gq(n)either. So, it follows that Z×n will have the same Sylow q-subgroup as Zp1−1 × Zp2−1 × · · · × Zpt−1.Thus, we have that Gq(n) = (q;α1, . . . , αj) if and only if the following conditions are satisfied:3• For each αi in {α1, . . . , αj} such that αi 6= αk for all k 6= i, there exists a unique prime divisor pi ofn such that pi ≡ 1 (mod qαi ) and pi 6≡ 1 (mod qαi+1).• If there is a subset {αk, αk+1, . . . , αk+m} of {α1, . . . , αj} such that αk = αk+1 = · · · = αk+m,then, there exists a unique set of m+ 1 distinct primes, {pk, pk+1, . . . , pk+m}, up to relabelling, suchthat if pi is in {pk, pk+1, . . . , pk+m}, then pi ≡ 1 (mod qαi ) and pi 6≡ 1 (mod qαi+1).• For all prime divisors p of n such that p 6= pi for any 1 ≤ i ≤ j, we have that p 6≡ 1 (mod q).Now, by definition of D and Dk, notice that,D((q;α1, . . . , αj), x) = #{n ≤ x : Gq(n) = (q;α1, . . . , αj)}=∞∑k=0Dk((q;α1, . . . , αj), x).Using similar reasoning as above, if qα1+2 divides n, then the Sylow q-subgroup of Z×n will include aZqα1+1 , and thus, will not be (q;α1, . . . , αj). Therefore, we can see that Dk((q;α1, . . . , αj), x) will beequal to zero if k is greater than or equal to α1 + 2 and so,D((q;α1, . . . , αj), x) =α1+1∑k=0Dk((q;α1, . . . , αj), x). (2.1)Before we can say more about D0, we need the following two definitions.Definition 2.1.1. For a nonzero integer x, define νq(x) to be the largest nonnegative integer k such that qkdivides x.Definition 2.1.2 (Conjugate Partition). Let (β1, β2, . . .) be a partition. Then, we define the conjugate par-tition (b1, b2, . . .) of (β1, β2, . . .) to be the partition whose Ferrers diagram is the transpose of the Ferrersdiagram of (β1, β2, . . .). In other words, we define (b1, b2, . . .) to be the conjugate partition of (β1, β2, . . .)if bi = #{k : βk ≥ i} for each natural number i.The following proposition will be very useful in evaluating D0.Proposition 2.1.3. Let H = (q;α1, α2, . . . , αj) . Then,D0(H,x) = CH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-m(t 6=p1,...,pj and t|m)⇒t6≡1 (mod q)1, (2.2)where t is prime. Here,CH =α1−1∏k=11(ak − ak+1)! ,where (a1, . . . , aα1) is the conjugate partition of (α1, . . . , αj).4Proof. First, notice that∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-m(t 6=p1,...,pj and t|m)⇒t6≡1 (mod q)1,counts the number of natural numbers n = p1p2 · · · pjm up to x where p1, . . . , pj are primes and thefollowing two statements hold:• for each i = 1, 2, . . . , j, pi ≡ 1 (mod qαi ) and pi 6≡ 1 (mod qαi+1),• m is an integer not divisible by q such that if t is a prime divisor of m, with t 6= p1, . . . , pj , then qdoes not divide t− 1.Comparing this sum to our above conditions on D0, we can see that the only difference between it and D0,is that, in this sum, we count the ‘good’ n up to x multiple times if the αi are not distinct. So, every time weget a sequence of m repeated α values, we need to multiply by 1/m! to ensure that we only count distinctvalues of n.Notice that for each k = 1, 2, . . ., by definition of conjugate partitions, ak − ak+1 ≥ 0 since{` : α` > k + 1} ⊂ {` : α` > k}. For any k, such that ak − ak+1 is equal to 0 or 1, 1/(ak − ak+1)! = 1,and thus, multiplying the above nested sum by 1/(ak − ak+1)! will have no effect. Now, notice that,ak − ak+1 = m > 1 for some k,m if and only if there is some 1 ≤ i < j such that αi = αi+1 = · · · =αi+m−1 = k + 1. Thus, if we have m repeated α values all equal to k + 1, we need to multiply by1/(ak − ak+1)! = 1/m!.The above proposition follows from here.2.2 Selberg–Delange MethodWe will start by introducing the version of the Selberg–Delange Method given in [5]. In order to do so, wewill first define two important properties of Dirichlet series.Definition 2.2.1 (From [5]). Let z ∈ C, c0 > 0, 0 < δ ≤ 1,M > 0. We say that a Dirichlet series F (s) hasthe property P(z; c0, δ,M) if the Dirichlet seriesG(s; z) := F (s)ζ(s)−z may be continued as a holomorphicfunction for σ ≥ 1− c0/(1 + log+ |τ |), and, in this domain, satisfies the bound |G(s; z)| ≤M(1 + |τ |)1−δ .Note that, for τ > 0, log+ |τ | = max{0, log τ}.Definition 2.2.2 (From [5]). Let z ∈ C, c0 > 0, 0 < δ ≤ 1,M > 0. We say that a Dirichlet seriesF (s) =∑n≥1 ann−s has the property T(z, w; c0, δ,M) if F (s) has property P(z; c0, δ,M) and if thereexists a sequence of non-negative real numbers {bn}∞n=1 such that |an| ≤ bn(n = 1, 2, . . .), and the series∑n≥1 bnn−s satisfies P(w; c0, δ,M) for some complex number w.5Now, we can state a version of the Selberg–Delange method, adapted from Theorem 5.2 of [5], by settingN = 0.Theorem 2.2.3 (Selberg–Delange Method). Let F (s) :=∑n≥1 ann−s be a Dirichlet series that has theproperty T(z, w; c0, δ,M). Then, for x ≥ 3, A > 0, |z| ≤ A, and |w| ≤ A, we have∑n≤xan = x(log x)z−1{G(1; z)Γ(z)+O(Mlog x)},where G is as in Definition 2.2.1 and Γ is the Euler Gamma function.Proof. Let F (s) :=∑n≥1 ann−s be a Dirichlet series that has the property T(z, w; c0, δ,M), x ≥ 3,A > 0, |z| ≤ A, and |w| ≤ A. Then, setting N = 0 in Theorem 5.2 of [5], we get that∑n≤xan = x(log x)z−1{λ0(z)(log x)0+O(MR0(x))}= x(log x)z−1{λ0(z) +O(MR0(x))}.Now, by Equation (5.16) of [5], we have thatR0(x) = e−c1√log x +1log x,where c1 is some positive constant. Then, since e−c1√log x 1/ log x, it follows that R0(x) 1/ log x,and thus, ∑n≤xan = x(log x)z−1{λ0(z) +O(Mlog x)}.Now, by Equation (5.13) in [5], we have thatλ0(z) =1Γ(z)∑h+j=01h!j!G(h)(1; z)γj(z) =G(1; z)γ0(z)Γ(z),where the γj are entire functions of z, that satisfyZ(s; z) =∑j≥01j!γj(z)(s− 1)j ,on the disk |s− 1| < 1 whereZ(s; z) =((s− 1)ζ(s))zs.Then, since Z(1; z) = 1 (p.279 of [5]), we can see that,1 = Z(1; z) =10!γ0(z) = γ0(z).6Therefore, λ0(z) = G(1; z)/Γ(z), and thus,∑n≤xan = x(log x)z−1{G(1; z)Γ(z)+O(Mlog x)}.In this section, our goal is to find an asymptotic formula for the following sum:∑m≤x/p1···pjq-m(t6=p1,...,pj and t|m)⇒t 6≡1 (mod q)1,where t is prime.However, in order to achieve this goal, we will start by using the Selberg Delange theorem to find anasymptotic formula for: ∑n≤xp|n⇒p 6≡1 (mod q)1.First, as setup, letan ={1, if p 6≡ 1 (mod q) for all p | n0, otherwiseand let F (s) :=∑∞n=1 ann−s. Then, since an is a multiplicative function of n, we can write F as an Eulerproduct in the following way: F (s) =∏p 6≡1 (mod q) (1− p−s)−1. Now, let G(s; z) := F (s)ζ(s)−z . In orderto find an asymptotic formula for ∑n≤xp|n⇒p 6≡1 (mod q)1,we need the following series of three propositions.Proposition 2.2.4. Let A(s) = F (s)q−1ζ(s)−(q−1)∏χ (mod q) L(s, χ). Then, A(s) can be analytically con-tinued to σ > 1/2, where σ is the real part of s.Proof. First, we can replace F (s), ζ(s), and L(s, χ) by their Euler products in the definition of A(s) to getA(s) =∏p 6≡1 (mod q)(1− 1ps)−(q−1)∏p(1− 1ps)q−1 ∏χ (mod q)∏p(1− χ(p)ps)−1=∏p≡1 (mod q)(1− 1ps)q−1 ∏χ (mod q)∏p(1− χ(p)ps)−17So, we can write,A(s) =∏pgp(1ps)wheregp(x) ={(1− x)q−1 , if p ≡ 1 (mod q)1 , if p 6≡ 1 (mod q)} ∏χ (mod q)(1− χ(p)x)−1.By the generalized binomial theorem, (1 − x)q−1 = 1 − (q − 1)x + O(x2), and (1 − χ(p)x)−1 =1 + χ(p)x+O(x2). From this, we get that,∏χ (mod q)(1− χ(p)x)−1 =∏χ (mod q)(1 + χ(p)x+O(x2)) = 1 + ∑χ (mod q)χ(p)x+O(x2).By the orthogonality relations for χ, we know that∑χ (mod q)χ(p) ={q − 1, if p ≡ 1 (mod q),0, if p 6≡ 1 (mod q).Thus, ∏χ (mod q)(1− χ(p)x)−1 ={1 + (q − 1)x+O(x2), if p ≡ 1 (mod q),1 +O(x2), if p 6≡ 1 (mod q).So,gp(x) ={1− (q − 1)x+O(x2), if p ≡ 1 (mod q)1, if p 6≡ 1 (mod q)}{1 + (q − 1)x+O(x2), if p ≡ 1 (mod q)1 +O(x2), if p 6≡ 1 (mod q)}= 1 +O(x2),and thus,A(s) =∏p(1 +O(1p2s)), (2.3)which converges for σ > 1/2.Proposition 2.2.5. LetA(s) be defined as in Proposition 2.2.4. Then,G(s, 1−1/(q−1)) can be analyticallycontinued to s = 1.Proof. First, notice that by rearranging the functions in the definition of A(s), we get thatF (s)q−1 = A(s)ζ(s)q−1∏χ (mod q)L(s, χ)−1. (2.4)8Consider L(s, χ0)−1, where χ0 is the principal Dirichlet character modulo q. Notice that we can use alge-braic manipulations to rewrite L(s, χ0)−1 in the following way:L(s, χ0)−1 =∏p(1− χ0(p)ps)=∏p 6=q(1− 1ps)=(1− 1qs)−1∏p(1− 1ps)=(1− 1qs)−1ζ(s)−1. (2.5)Therefore, from equation (2.4), we have thatF (s)q−1 = A(s)ζ(s)q−1(1− 1qs)−1ζ(s)−1∏χ 6=χ0L(s, χ)−1= A(s)ζ(s)q−2(1− 1qs)−1 ∏χ 6=χ0L(s, χ)−1. (2.6)Thus, since G(s; z) = F (s)ζ(s)−z , we have that,G (s; 1− 1/(q − 1)) = F (s)ζ(s)−(q−2)/(q−1)= F (s)(q−1)/(q−1)ζ(s)−(q−2)/(q−1)=(F (s)q−1ζ(s)−(q−2))1/(q−1)=A(s)ζ(s)q−2(1− 1qs)−1 ∏χ 6=χ0L(s, χ)−1ζ(s)−(q−2)1/(q−1)=A(s)(1− 1qs)−1 ∏χ 6=χ0L(s, χ)−11/(q−1) . (2.7)Note that the analytic continuation of G(s; 1− 1/(q − 1)) to s = 1 follows from equations (2.3) and (2.7),since L(1, χ) is non-zero for χ non-principal.Before stating Proposition 2.2.7, we need the following definition.Definition 2.2.6. Let m be an integer and let n be a positive integer such that (m,n) = 1. Then, we say thatk is the order of m modulo n if k is the smallest positive integer such that mk ≡ 1 (mod n).Proposition 2.2.7. For a prime number p, let kp be the order of p modulo q. Then,G(1; 1− 1/(q − 1)) = (1− 1/q)−1/(q−1)∏p 6=qp 6≡1 (mod q)(1− 1/pkp)−1/kp∏χ 6=χ0L(1, χ)−1/(q−1).9Proof. First, from equation (2.6), we get thatA(s) = F (s)q−1ζ(s)−(q−2)(1− 1qs) ∏χ 6=χ0L(s, χ)= (1− 1/qs)∏p 6≡1 (mod q)(1− 1/ps)−(q−1)∏p(1− 1/ps)q−2∏χ 6=χ0(∏p(1− χ(p)/ps)−1).Now, when p ≡ 1 (mod q), the local factor is(1− 1/ps)q−2∏χ 6=χ0(1− χ(p)/ps)−1 = (1− 1/ps)q−2 (1− 1/ps)−(q−2) = 1.Similarly, when p = q, the local factor is(1− 1/ps) (1− 1/ps)−(q−1) (1− 1/ps)q−2∏χ 6=χ0(1− χ(p)/ps)−1 =∏χ 6=χ0(1− 0/ps)−1 = 1.For all other p, the local factor is(1− 1/ps)−(q−1) (1− 1/ps)q−2∏χ 6=χ0(1− χ(p)/ps)−1 = (1− 1/ps)−1∏χ 6=χ0(1− χ(p)/ps)−1=∏χ (mod q)(1− χ(p)/ps)−1 .Now, by the generalized binomial theorem, we have that (1− χ(p)/ps)−1 = 1 + χ(p)/ps +O(1/p2s).So, ∏χ (mod q)(1− χ(p)p−s)−1 = ∏χ (mod q)(1 + χ(p)p−s +O(p−2s))= 1 + ∑χ (mod q)χ(p) p−s +O(p−2s))= 1 +O(p−2s),as expected since A(s) converges for σ > 1/2 by Proposition 2.2.4.Thus, we have thatA(s) =∏p 6=qp 6≡1 (mod q)∏χ (mod q)(1− χ(p)/ps)−1,where A(s) converges for σ > 1/2, and hence,A(1) =∏p 6=qp 6≡1 (mod q)∏χ (mod q)(1− χ(p)/p)−1,10is convergent.Now, we will evaluate the innermost product. First, letting x = 1/p, we get that∏χ (mod q)(1− χ(p)/p)−1 =∏χ (mod q)(1− χ(p)x)−1.For any prime p, let kp be the order of p modulo q. Then, since each kthp root of unity occurs exactly(q − 1)/kp times among the values χ(p) as χ varies over all Dirichlet characters modulo q, we have that∏χ (mod q)(1− χ(p)x)−1 =kp∏j=1(1− e2piij/kpx)−(q−1)/kp .Now, sincexkp − 1 =kp∏j=1(x− e2piij/kp),we have that,1− 1/xkp =kp∏j=1(1− e2piij/kp/x).Thus, replacing x by 1/x, we see that1− xkp =kp∏j=1(1− e2piij/kpx).Thus,kp∏j=1(1− e2piij/kpx)−(q−1)/kp = (1− xkp)−(q−1)/kp .So, it follows that, ∏χ (mod q)(1− χ(p)x)−1 = (1− xkp)−(q−1)/kp ,and thus,A(1) =∏p 6=qp 6≡1 (mod q)(1− 1/pkp)−(q−1)/kp .Now, setting s = 1 inG (s; 1− 1/(q − 1)) =A(s)(1− 1qs)−1 ∏χ 6=χ0L(s, χ)−11/(q−1)11we get thatG (1; 1− 1/(q − 1)) = A(1)1/(q−1) (1− 1/q)−1/(q−1)∏χ 6=χ0L(1, χ)−1/φ(q)= (1− 1/q)−1/(q−1)∏p 6=qp 6≡1 (mod q)(1− 1/pkp)−(q−1)/kp∏χ 6=χ0L(1, χ)−1/(q−1)The following corollary to the Selberg–Delange Theorem gives an asymptotic formula for the desiredsum.Corollary 2.2.8. Let p be a prime number. Then, for x ≥ 3,∑n≤xp|n⇒p 6≡1 (mod q)1 = Bqx(log x)−1/(q−1) +O(x(log x)−1−1/(q−1)),whereBq =G(1; 1− 1/(q − 1))Γ(1− 1/(q − 1)) ,and G(1; 1− 1/(q − 1)) is as in Proposition 2.2.7.Proof. We will start by establishing some of the parameters required for the Selberg–Delange Theorem.First, let z = 1− 1/(q − 1) and recall thatG(s; 1− 1/(q − 1)) = A(s)1/(q−1)(1− 1qs)−1/(q−1) ∏χ 6=χ0L(s, χ)−1/(q−1).Note that A(s) converges for σ > 1/2 and (1− 1/qs)−1/(q−1) is well-defined for σ > 0. Now, from The-orem 11.3 of [4], it follows that if none of the Dirichlet characters χ (mod q) have an exceptional zero, thenthere exists an absolute constant c > 0 such thatL(s, χ) has no zeros in the region σ > 1− c/ log(q(|τ |+ 4)).Note that since log+ |τ | and log(|τ |+4) differ by at most log(5), it follows that there exists a constant c > 0such that L(s, χ) has no zeros in the region σ > 1− c/ log+(q|τ |). Now, since1− c/ log+(q|τ |) = 1− c/ log q1 + log+ |τ |/ log q < 1−c/ log q1 + log+ |τ | ,we have that if L(s, χ) has no zeros in the region σ > 1 − c/ log q1+log+ |τ |/ log q , then, L(s, χ) has no zeros inthe region σ > 1 − c/ log q1+log+ |τ | , and thus,∏χ 6=χ0 L(s, χ)−1/(q−1) will be analytic for σ > 1 − c/ log q1+log+ |τ | .Now, suppose that some Dirichlet character χmodulo q has an exceptional zero, β ∈ R, 1−c/ log+(q|τ |) <β < 1. Then, we have that L(s, χ) has no zeros in the region σ > 1 − (1 − β)/(1 + log+ |τ |). Indeed, ifσ > 1− (1− β)/(1 + log+ |τ |), then 1− β > (1− β)/(1 + log+ |τ |) > 1− σ, and thus, σ > β.12Therefore, putting everything together, we can see that G(s; 1 − 1/(q − 1)) is analytic in the regionσ > 1 − c01+log+ |τ | , where c0 = c/ log q, where c is the constant defined in Theorem 11.3 of [4], if everyDirichlet character χ (mod q) has no exceptional zero, and c0 = 1− β if there is some Dirichlet character χmodulo q such that χ has an exceptional zero β.Now, sinceA(s) converges for σ > 1/2, we have that |A(s)|1/(q−1) 1 in the region σ > 1− c01+log+ |τ | .Similarly, since (1 − 1/qs)−1/(q−1) is well-defined for σ > 0, (1 − 1/qs)−1/(q−1) 1 in the regionσ > 1− c01+log+ |τ | . Therefore, we have that|G(s; 1− 1/(q − 1))| = |A(s)|1/(q−1)∣∣∣∣1− 1qs∣∣∣∣−1/(q−1) ∏χ 6=χ0|L(s, χ)|−1/(q−1) ∏χ 6=χ0|L(s, χ)|−1/(q−1).Now, by Theorem 11.4 of [4], we know that L(s;χ)−1 log(q(|τ |+ 4)). From this, it follows that∏χ 6=χ0|L(s, χ)|−1/(q−1) ∏χ 6=χ0| log(q(|τ |+ 4))|1/(q−1) = | log(q(|τ |+ 4))|1−1/(q−1).Fix > 0. Then, sincelim|τ |→∞log(q(|τ |+ 4))(1 + |τ |) = 0,we have that log(q(|τ |+ 4)) = o((1 + |τ |)), and thus, log(q(|τ |+ 4)) (1 + |τ |).Therefore, we get that|G(s; 1− 1/(q − 1))| ∏χ 6=χ0|L(s, χ)|−1/(q−1) (log(q(|τ |+ 4)))1−1/(q−1) (1 + |τ |)(1−1/(q−1)).Since this is true for arbitrarily small positive values of , it follows that |G(s; 1− 1/(q − 1))| (1 + |τ |)1−δ ,for 0 < δ ≤ 1, and thus that, |G(s; 1− 1/(q − 1))| ≤M(1 + |τ |)1−δ , for some M > 0.So, at this point, we can apply Theorem 2.2.3 with z = 1− 1/(q − 1) to get that, for x ≥ 3,∑n≤xan = x(log x)−1/(q−1){G(1; 1− 1/(q − 1)Γ(1− 1/(q − 1)) +O(Mlog x)}= x(log x)−1/(q−1){Bq +O(1log x)}= Bqx(log x)−1/(q−1) +O(x(log x)−1−1/(q−1)).Therefore, for x ≥ 3,∑n≤xp|n⇒p6≡1 (mod q)1 = Bqx(log x)−1/(q−1) +O(x(log x))−1−1/(q−1).13The following proposition will be useful in evaluating the innermost sum of equation (2.2).Corollary 2.2.9. Let x be a real number and let p1, . . . , pj be distinct prime numbers such that x/p1 · · · pj ≥3 and q 6= pi for any 1 ≤ i ≤ j. Then,∑m≤x/p1···pjq-m(t 6=p1,...,pj and t|m)⇒t6≡1 (mod q)1 = Bqxp1 · · · pj(logxp1 · · · pj)−1/(q−1)(1− 1q) j∏i=1(1− 1pi)−1+O(xp1 · · · pj(logxp1 · · · pj)−1−1/(q−1)),where t is prime.Proof. We will start by rewriting the sum as follows,∑m≤x/p1···pjq-m(t 6=p1,...,pj and t|m)⇒t6≡1 (mod q)1 =∑m≤x/p1···pjbm,wherebm ={1, if q - m and, for t 6= p1, . . . , pj , we have t | m⇒ t 6≡ 1 (mod q),0, otherwise .Define F2(s) =∑∞m=1 bmm−s. Then,F2(s) =∞∑m=1bmm−s =∏r prime(1 +brrs+br2r2s+ · · ·)=j∏i=1(1 +1psi+1p2si+ · · ·) ∏r primer 6=qr 6≡1 (mod q)(1 +1rs+1r2s+ · · ·)=j∏i=1(1− 1psi)−1 ∏r primer 6=qr 6≡1 (mod q)(1− 1rs)−1=(1− 1qs) j∏i=1(1− 1psi)−1 ∏r primer 6≡1 (mod q)(1− 1rs)−1.Now, define G2(s; z) = F2(s)ζ(s)−z . Our next aim is to find an explicit formula for G2. We will start14by defining A2(s) such that F2(s)q−1 = A2(s)ζ(s)q−1∏χ (mod q) L(s, χ)−1. Then,A2(s) = F2(s)q−1ζ(s)−(q−1)∏χ (mod q)L(s, χ)=(1− 1qs)q−1 j∏i=1(1− 1psi)−(q−1) ∏r primer≡1 (mod q)(1− 1rs)q−1 ∏χ (mod q) ∏r prime(1− χ(r)rs)−1=(1− 1qs)q−1 j∏i=1(1− 1psi)−(q−1)A(s),where A(s) is defined as in the proof of Proposition 2.2.4. Thus, since A(s) converges for σ > 1/2, itfollows that A2(s) also converges for σ > 1/2.Now recall from equation (2.5) that L(s, χ0)−1 = ζ(s)−1(1− q−s)−1. Therefore, we have thatF2(s)q−1 = A2(s)ζ(s)q−1ζ(s)−1(1− 1qs)−1 ∏χ 6=χ0L(s, χ)−1=(1− 1qs)q−1 j∏i=1(1− 1psi)−(q−1)A(s)ζ(s)q−2(1− 1qs)−1 ∏χ6=χ0L(s, χ)−1.Then,G2(s; 1− 1/(q − 1)) = F2(s)ζ(s)−(q−2)/(q−1)= (F2(s)(q−1)ζ(s)−(q−2))1/(q−1)=(1− 1qs)q−1 j∏i=1(1− 1psi)−(q−1)A(s)(1− 1qs)−1 ∏χ 6=χ0L(s, χ)−11/(q−1)=(1− 1qs) j∏i=1(1− 1psi)−1G(s; 1− 1/(q − 1)),where G is defined as in Proposition 2.2.7.Then, since x ≥ 3p1 · · · pj , we can apply Theorem 2.2.3 with z = (q − 2)/(q − 1) to get:∑m≤x/p1···pjbm =xp1 · · · pj(logxp1 · · · pj)−1/(q−1)(G2(1; 1− 1/(q − 1))Γ(1− 1/(q − 1)))+O(xp1 · · · pj(logxp1 · · · pj)−1−1/(q−1)).Now, sinceG2(1; 1− 1/(q − 1)) =(1− 1q) j∏i=1(1− 1pi)−1G(1; 1− 1/(q − 1)),15it follows that, ∑m≤x/p1···pjq-mt6=p1,...,pj and t|m⇒t6≡1 (mod q)1= Bqxp1 · · · pj(logxp1 · · · pj)−1/(q−1)(1− 1q) j∏i=1(1− 1pi)−1+O(xp1 · · · pj(logxp1 · · · pj)−1−1/(q−1)).2.3 Other Important ToolsWe will start this section by giving a lemma and a proposition that will be very useful throughout this thesis.Lemma 2.3.1. Let δ > 0. Then, for x > y1+δ ,log xδ log xy.Proof. First, since x > y1+δ , we have that x1/δ > y(1+δ)/δ . Now, notice that we can rewrite x1/δ asfollows:x1/δ = x1/δ+1−1 = x(1+δ)/δ−1 = x(1+δ)/δ/x.So, we have that x(1+δ)/δ/x > y(1+δ)/δ. From here, we get the following biconditional statements:x(1+δ)/δ/x > y(1+δ)/δ ⇐⇒ x < (x/y)(1+δ)/δ.Thus, it follows thatlog(x) <1 + δδlog(xy)δ log(xy).Proposition 2.3.2. Let y be a positive real number. Then, for x > y2,(log xy)−α= (log x)−α +Oα((log x)−1−α log y).Proof. First, we can see that (log xy)−α= (log x− log y)−α= (log x)−α(1− log ylog x)−α.16Now, let f(t) = (1 − t)−α. Then, since f(0) = 1, f is differentiable at t = 0 and f is continuous for|t| ≤ 1/2, it follows that f(t) = 1 + Oα(t) for |t| ≤ 1/2. Since x > y2, we have that log y/ log x < 1/2.So, (1− log ylog x)−α= 1 +Oα(log ylog x).Substituting this back in to our above product, we get that(log xy)−α= (log x)−α(1 +Oα(log ylog x))= (log x)−α +Oα((log x)−1−α log y).The next seven propositions lead to Propositions 2.3.11 and 2.3.12 which will both be useful in evaluatingthe nested sum in equation (2.2).Before stating the next proposition we need the following definition.Definition 2.3.3. Let α be a real number such that α 6∈ N. Then,Hα(z) = −∞∑n=0αn− αzn.Note that, by the ratio test, Hα(z) converges for |z| < 1.Proposition 2.3.4. Let α > 0 such that α 6∈ N and let x > 1. Then, for u in the domain (1, x),∫log(x/u)−α(1u log u)du =Hα(1− log u/ log x)− 1α(log(x/u))α+ C.Proof. We will prove the above proposition by showing thatddu[Hα(1− log u/ log x)− 1α(log(x/u))α]= log(x/u)−α(1u log u).Let z = 1− log u/ log x. Then, z log x = log x− log u = log(x/u), and thus,ddu[Hα(1− log u/ log x)− 1α(log(x/u))α]=ddz[Hα(z)− 1α(z log x)α](dzdu).Since 1 < u < x, we have that 0 < 1 − log u/ log x < 1, and thus, |z| = |1 − log u/ log x| < 1. So, z isin the region of convergence of Hα(z), which allows us to differentiate the infinite sum term by term in the17following computation. Using quotient rule to differentiate the first part, we see thatddz[Hα(z)− 1α(z log x)α]=ddz[−∑∞n=1 αn−αznα(z log x)α]=−α(z log x)α∑∞n=1 nαn−αzn−1 + α2(log x)αzα−1∑∞n=1 αn−αznα2(z log x)2α=−α2(log x)αzα[∑∞n=1nn−αzn−1 −∑∞n=1 αn−αzn−1]α2(z log x)2α=−∑∞n=1 zn−1(z log x)α=−∑∞n=0 zn(z log x)α.Then, since11− z =∞∑n=0zn,we have thatddz[Hα(z)− 1α(z log x)α]= − 1(1− z)(z log x)α .Since z = 1− log u/ log x, we can see thatddz[Hα(z)− 1α(z log x)α]= − 1(log u/ log x)(log(x/u))α= − log x(log u)(log(x/u))α,anddzdu= − 1u log x.Therefore, putting everything together, we get the following:ddu[Hα(1− log u/ log x)− 1α(log(x/u))α+ C]=ddz[Hα(z)− 1α(z log x)α](dzdu)=(− log xlog u(log(x/u))α)(− 1u log x)=1u(log u)(log(x/u))αThus, we have shown thatddu[Hα(1− log u/ log x)− 1α(log(x/u))α+ C]= (log(x/u))−α(1u(log u)),which proves the proposition.18Proposition 2.3.5. Let α > 0 such that α 6∈ N. For y ≥ 9,∫ √y2−log(y/u)−α(1u log u)du =log log y(log y)α +Oα(1(log y)α).Proof. First, by Proposition 2.3.4, we have that∫ √y2−log(y/u)−α(1u log u)du =Hα(1− log ulog y )− 1α(log(y/u))α∣∣∣∣√y2−=Hα(1− log y2 log y)− 1α(12 log y)α − Hα(1− log 2log y)− 1α(log(y/2))α=Hα(12)− 1α2α (log y)α−Hα(1− log 2log y)− 1α(log(y/2))α.We will start by simplifying the minuend of the above subtraction. By definition of Hα, we have thatHα(12)− 1 = −∞∑n=1αn− α(12)n.Now, since 1/2 is inside the region of convergence for Hα(z), we can see that this sum converges. So, wehave that,Hα(12)− 1α 1,and thus,Hα(12)− 1α2α (log y)α= Oα(1(log y)α).Now, we will find an asymptotic formula for the subtrahend. To do this, let z = 1 − log 2/(log y) andconsider Hα(z)− 1− α log(1− z). Rewriting Hα and log(1− z) as sums and simplifying, we get,Hα(z)− 1− α log(1− z) = −∞∑n=1αn− αzn − α∞∑n=1(−1)n+1n(−z)n= −α∞∑n=11n− αzn + α∞∑n=11nzn= α∞∑n=1−αn(n− α)zn= −α2∞∑n=11n(n− α)zn.Since y ≥ 9, we have that |z| = |1− log 2/ log y| < 1, and so,−α2∞∑n=11n(n− α)zn ≤∣∣∣∣∣−α2∞∑n=11n(n− α)zn∣∣∣∣∣ ≤ α2∞∑n=1∣∣∣∣ 1n(n− α)∣∣∣∣α 1.19It follows that,Hα(z)− 1− α log(1− z)α 1,and thus,Hα(1− log 2/ log y)− 1 = α log(log 2/ log y) +Oα(1).Therefore, we have that:Hα(1− log 2log y)− 1α(log(y/2))α=α log(log 2/ log y) +Oα(1)α(log(y/2))α=log log 2− log log y(log(y/2))α+Oα(1(log(y/2))α)= − log log y(log(y/2))α+Oα(1(log(y/2))α).Now, since y ≥ 3 > 21+1/2, we can apply Lemma 2.3.1 to the above error term, to getHα(1− log 2log y)− 1α(log(y/2))α= − log log y(log(y/2))α+Oα(1(log y)α).Also, since y ≥ 9 > 22, we can apply Proposition 2.3.2 to the denominator of the above main term, togetHα(1− log 2log y)− 1α(log(y/2))α= − log log y(log y)α +O(log 2 log log y(log y)1+α)+Oα(1(log y)α)= − log log y(log y)α +O(log log y(log y)1+α)+Oα(1(log y)α)= − log log y(log y)α +Oα(1(log y)α).Putting everything together, we can see that,∫ √y2−log(y/u)−α(1u log u)du =log log y(log y)α +Oα(1(log y)α).Proposition 2.3.6. Let α > 0 such that α 6∈ N, let β ∈ N, and let y ≥ 9. Then,∑p≤√yνq(p−1)=β1p(logyp)−α=log log yqβ (log y)α +Oα(1(log y)α).20Proof. Define M(x) as follows:M(x) =∑p≤xνq(p−1)=β1/p =∑p≤xp≡1 (mod qβ )p 6≡1 (mod qβ+1)1/p=∑p≤xp≡1 (mod q)β1/p−∑p≤xp≡1 (mod qβ+1)1/p.Then, using Mertens’ Theorem [4, Corollary 4.12], we can simplify M(x) as follows:M(x) =(1φ(qβ)− 1φ(qβ+1))log log(x) + cqβ − cqβ+1 +O(1/ log x)=1qβlog log(x) + c+O(1/ log x)where c is a constant depending on qβ . Then, we have that∑p≤√yνq(p−1)=β1p(logyp)−α=∫ √y2−log(yu)−αd(M(u))=∫ √y2−log(yu)−αd(1qβlog log u+ c+O(1log u))=1qβ∫ √y2−log(yu)−α( duu log u)+∫ √y2−log(yu)−αd(O(1log u)).By Proposition 2.3.5, we know that∫ √y2−log(y/u)−α(1u log u)du =log log y(log y)α +Oα(1(log y)α),and thus,∑p≤√yνq(p−1)=β1p(logyp)−α=log log yqβ (log y)α +Oα(1(log y)α)+∫ √y2−log(yu)−αd(O(1log u)).21Now, we will evaluate the remaining integral, using Riemann-Stieltjes integration:∫ √y2−log (y/u)−αd(O(1log u))=(log(yu))−αO(1log u) ∣∣∣∣√y2−−∫ √y2−O(1log u)(−α(log(yu))−α−1(uy)(− yu2))du=(12log y)−αO(2log y)−(log(y2))−αO(1log 2)+O(∫ √y2−log(y/u)−α−1(1u log u)du)= O(1(log y)1+α)+O(1(log (y/2))α)+O(∫ √y2−log(y/u)−α−1(1u log u)du).By Lemma 2.3.1, since y ≥ 9, we have that1log(y/2) 1log y.Therefore, we have that∫ √y2−log (y/u)−αd(O(1log u))= O(1(log y)1+α)+O(1(log y)α)+O(∫ √y2−log(y/u)−α−1(1u log u)du)= O(1(log y)α)+O(∫ √y2−log(y/u)−α−1(1u log u)du).Now, by Proposition 2.3.5, we have that∫ √y2−log(y/u)−α−1(1u log u)du =log log y(log y)1+α +Oα(1(log y)1+α)= Oα(log log y(log y)1+α).Thus, we get that∫ √y2−log (y/u)−αd(O(1log u))= O(1(log y)α)+Oα(log log y(log y)1+α)= Oα(1(log y)α).22Therefore, it follows that∑p≤√yνq(p−1)=β1p(logyp)−α=log log yqβ (log y)α +Oα(1(log y)α).Proposition 2.3.7. Let α > 0 such that α 6∈ N. For y ≥ 9,∫ y/3√ylog(y/u)−α(1u log u)du = O(1(log y)α)+O(1log y).Proof. First, by Proposition 2.3.4, we have that∫ y/3√ylog(y/u)−α(1u log u)du =Hα(1− log ulog y )− 1α(log(y/u))α∣∣∣∣y/3√y=Hα(1− log(y/3)log y)− 1α(log 3)α−Hα(1− log y2 log y)− 1α(12 log y)α=Hα(log 3log y)− 1α(log 3)α− Hα(12)− 1α2α (log y)α. (2.8)As seen in the proof of Proposition 2.3.5,Hα(12)− 1α2α (log y)α= O(1(log y)α).Now, we will simplify the minuend of the right-hand side of equation (2.8). By definition of Hα, wehave thatHα(log 3/ log y)− 1 = −∞∑n=1αn− α(log 3log y)n.Now, since this sum is bounded on the closed disc corresponding to log 3/ log y ≤ 1/2, we have that, fory ≥ 9,Hα(log 3/ log y)− 1 log 3log y 1log y.Putting everything together, we can see that,∫ y/3√ylog(y/u)−α(1u log u)du = O(1(log y)α)+O(1log y).23Proposition 2.3.8. Let α > 0 such that α 6∈ N, let β ∈ N, and let y ≥ 9. Then,∑√y<p≤y/3νq(p−1)=β1p(logyp)−α= O(1(log y)α)+O(1log y).Proof. Define M(x) as in Proposition 2.3.6. Then, we have that∑√y<p≤y/3νq(p−1)=β1p(logyp)−α=∫ y/3√ylog(yu)−αd(M(u))=∫ y/3√ylog(yu)−αd(1qβlog log u+ c+O(1log u))=1qβ∫ y/3√ylog(yu)−α( duu log u)+∫ y/3√ylog(yu)−αd(O(1log u)).By Proposition 2.3.7, we know that∫ y/3√ylog(y/u)−α(1u log u)du = O(1(log y)α)+O(1log y),and thus,∑√y<p≤y/3νq(p−1)=β1p(logyp)−α= O(1(log y)α)+O(1log y)+∫ y/3√ylog(yu)−αd(O(1log u)).Now, we will evaluate the remaining integral, using Riemann-Stieltjes integration:∫ y/3√ylog (y/u)−αd(O(1log u))=(log(yu))−αO(1log u) ∣∣∣∣y/3√y−∫ y/3√yO(1log u)(−α(log(yu))−α−1(uy)(− yu2))du= (log 3)−αO(1log(y/3))−(12log y)−αO(2log y)+O(∫ y/3√ylog(y/u)−α−1(1u log u)du)= O(1log(y/3))+O(1(log y)1+α)+O(∫ √y2−log(y/u)−α−1(1u log u)du).24By Lemma 2.3.1, since y ≥ 9, we have that1log(y/3) 1log(y).Therefore, we have that∫ y/3√ylog (y/u)−αd(O(1log u))= O(1log y)+O(1(log y)1+α)+O(∫ y/3√ylog(y/u)−α−1(1u log u)du)= O(1log y)+O(∫ y/3√ylog(y/u)−α−1(1u log u)du).Now, by Proposition 2.3.7, we have that∫ y/3√ylog(y/u)−α−1(1u log u)du = O(1(log y)1+α)+O(1log y)= O(1log y).So, we get that ∫ y/3√ylog (y/u)−αd(O(1log u))= O(1log y),and thus, ∑√y<p≤y/3νq(p−1)=β1p(logyp)−α= O(1(log y)α)+O(1log y).Proposition 2.3.9. Let α > 0 such that α 6∈ N, let β ∈ N, let y ≥ 9 and let {w1, w2, . . . , wn} be a set ofprimes. Then,∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(logyp)−α=log log yqβ (log y)α +On(1(log y)min{α,1}).Proof. First, notice that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(logyp)−α=∑p≤y/3νq(p−1)=β1p(logyp)−α+O(n∑i=11wi(logywi)−α).25Since, by Lemma 2.3.1 (logywi)−α (log y)−α,we have thatn∑i=11wi(logywi)−αn∑i=11wi(log y)−α = (log y)−αn∑i=11win (log y)−α.Now, to simplify the main term, we can split it up as follows∑p≤y/3νq(p−1)=β1p(logyp)−α=∑p≤√yνq(p−1)=β1p(logyp)−α+∑√y<p≤y/3νq(p−1)=β1p(logyp)−α.From here, we can apply Propositions 2.3.6 and 2.3.8 directly to get that∑p≤y/3νq(p−1)=β1p(logyp)−α=log log yqβ (log y)α +O(1(log y)α)+O(1(log y)α)+O(1log y).Therefore, we have that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(logyp)−α=log log yqβ (log y)α +On(1(log y)min{α,1}).Proposition 2.3.10. Let α > 0 such that α 6∈ N, y ≥ 9, β ∈ N and let {w1, . . . , wn} be a set of primes.Then, ∑p≤y/3p 6=w1,...,wnνq(p−1)=β1p2(log(y/p))−α (log y)−min{α,1}.Proof. In order to prove the proposition, we will split the sum in the following way:∑p≤y/3p 6=w1,...,wnνq(p−1)=β1p2(log(y/p))−α =∑p≤y/3νq(p−1)=β1p2(log(y/p))−α +O(n∑i=11w2i(logywi)−α).Since, by Lemma 2.3.1 (logywi)−α (log y)−α,we have thatn∑i=11w2i(logywi)−αn∑i=11w2i(log y)−α = (log y)−αn∑i=11w2i (log y)−α.26Then, to bound the main term, we will split it up as follows:∑p≤y/3νq(p−1)=β1p2(log(y/p))−α =∑p≤√yνq(p−1)=β1p2(log(y/p))−α +∑√y<p≤y/3νq(p−1)=β1p2(log(y/p))−α.For the first sum on the right-hand side, since we are summing over primes p that are at most√y, we canbound the sum as follows: ∑p≤√yνq(p−1)=β1p2(log(y/p))−α ≤∑p≤√yνq(p−1)=β1p2(log(y/√y))−α=(12log y)−α ∑p≤√yνq(p−1)=β1p2 (log y)−α,since the sum of 1/p2 over all primes p is convergent.Then, we can bound the remaining sum as follows:∑√y<p≤y/3νq(p−1)=β1p2(log(y/p))−α ≤ (pi(y/3)− pi(√y))(1(√y)2)(log(yy/3))−α≤ pi(y/3)(1/y)(log 3)−α y/3log(y/3)(1y) 1log(y/3).Now, since y ≤ 31+1, we can apply Lemma 2.3.1 to get that∑√y<p≤y/3νq(p−1)=β1p2(log(y/p))−α 1/ log y.Thus, we get that∑p≤y/3p 6=w1,...,wnνq(p−1)=β1p2(log(y/p))−α (log y)−α + (log y)−1 (log y)−min{α,1}.The following two propositions will be very useful in evaluating D0.27Proposition 2.3.11. Let α > 0 such that α 6∈ N, let β ∈ N, let y ≥ 9 and let {w1, w2, . . . , wn} be a set ofprimes. Then,∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(logyp)−α(1 +O(1p))=log log yqβ (log y)α +On(1(log y)min{α,1}).Proof. First, notice that we can split the sum as follows,∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(logyp)−α(1 +O(1p))=∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(logyp)−α+O( ∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p2(logyp)−α).Then, we can apply Propositions 2.3.9 and 2.3.10 to get the desired result.Proposition 2.3.12. Let α > 0 such that α 6∈ N, let β, k ∈ N, let y ≥ 9 and let {w1, w2, . . . , wn} be a setof primes. Then,∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(1 +O(1p))((log log(y/p))k(log(y/p))α +O((log log y)k−1(log(y/p))min{α,1}))=(log log y)k+1qβ logα y+On((log log y)k(log y)min{α,1}).Proof. First, we can break the above sum into multiple sums as follows:∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(1 +O(1p))((log log(y/p))k(log(y/p))α +O((log log y)k−1(log(y/p))min{α,1}))=∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log(y/p))kp (log(y/p))α +O( ∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log(y/p))kp2 (log(y/p))α)+O( ∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log y)k−1p(log(y/p))min{α,1}).28We will start by simplifying the error terms. Starting with the first error term, notice that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log(y/p))kp2 (log(y/p))α ∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log y)kp2 (log(y/p))α= (log log y)k∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p2 (log(y/p))α .Then, by Proposition 2.3.10, we get that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p2 (log(y/p))α 1(log y)min{α,1},and thus ∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=βlog log(y/p)p2 (log(y/p))α (log log y)k(log y)min{α,1}.Now, to simplify the second error term, we can apply Proposition 2.3.9 to get that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log y)k−1p(log(y/p))min{α,1}= (log log y)k−1∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(log(y/p))min{α,1} (log log y)k−1 log log y(log y)min{α,1}=(log log y)k(log y)min{α,1}.Now, we will evaluate the main term. First, notice that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log(y/p))kp (log(y/p))α =∑p≤y/3νq(p−1)=β(log log(y/p))kp (log(y/p))α +O(n∑i=1(log log(y/wi))kwi (log(y/wi))α).As shown in the proof of Proposition 2.3.9,n∑i=11wi (log(y/wi))α n (log y)−α,and thus,n∑i=1(log log(y/wi))kwi (log(y/wi))α (log log y)kn∑i=11wi (log(y/wi))α n(log log y)klogα y.29Splitting the remaining sum into two sums, we get that∑p≤y/3νq(p−1)=β(log log(y/p))kp (log(y/p))α =∑p≤√yνq(p−1)=β(log log(y/p))kp (log(y/p))α +∑√y<p≤y/3νq(p−1)=β(log log(y/p))kp (log(y/p))α .Starting with the second sum on the right-hand side of the equation, we can see that∑√y<p≤y/3νq(p−1)=β(log log(y/p))kp (log(y/p))α ≤∑√y<p≤y/3νq(p−1)=β(log log y)kp (log(y/p))α = (log log y)k∑√y<p≤y/3νq(p−1)=β1p (log(y/p))α .Then, applying Proposition 2.3.8, we get that∑√y<p≤y/3νq(p−1)=β1p (log(y/p))α 1(log y)min{α,1},and thus, ∑√y<p≤y/3νq(p−1)=β(log log(y/p))kp (log(y/p))α (log log y)k(log y)min{α,1}.Now, we will focus on the first sum on the right-hand side of the equation. By Proposition 2.3.2, sincey ≥ p2, we have thatlog(y/p) = log y +O(log plog2 y).Furthermore, notice thatlog plog2 y≤ log√ylog2 y 1log y.So, it follows that(log log(y/p))k =(log(log y +O(1log y)))k=(log log y + log(1 +O(1log2 y)))k=(log log y +O(1log2 y))k=k∑j=0(kj)(log log y)k−j(O(1log2 y))j= (log log y)k +k∑j=1(kj)(log log y)k−j(O(1log2 y))j= (log log y)k +k∑j=1O((kj)(log log y)k−jlog2j y).30The largest error term will occur when j is smallest, ie. when j = 1. Thus,(log log(y/p))k = (log log y)k +Ok((log log y)k−1log2 y).Therefore, we have that∑p≤√yνq(p−1)=β(log log(y/p))kp (log(y/p))α =((log log y)k +Ok((log log y)k−1log2 y)) ∑p≤√yνq(p−1)=β1p (log(y/p))α .Then, applying Proposition 2.3.6, we get that∑p≤√yνq(p−1)=β1p (log(y/p))α =log log yqβ (log y)α +O(1(log y)α).Therefore, we get the following∑p≤√yνq(p−1)=β(log log(y/p))kp (log(y/p))α =((log log y)k +Ok((log log y)k−1log2 y))(log log yqβ logα y+O(1logα y))=(log log y)k+1qβ logα y+O((log log y)klogα y)+Ok,q((log log y)k(log y)2+α)=(log log y)k+1qβ logα y+O((log log y)klogα y).Thus, we have shown that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β(log log(y/p))kp (log(y/p))α =(log log y)k+1qβ logα y+O((log log y)k(log y)min{α,1})+On((log log y)klogα y)=(log log y)k+1qβ logα y+On((log log y)k(log y)min{α,1}),and thus, that∑p≤y/3p 6=w1,w2,...,wnνq(p−1)=β1p(1 +O(1p))((log log(y/p))k(log(y/p))α +O((log log y)k−1(log(y/p))min{α,1}))=(log log y)k+1qβ logα y+On((log log y)k(log y)min{α,1}).The final definitions and propositions in this section will be important in order to evaluate multiply nestedsums recursively in the next section.31Definition 2.3.13. For k, α1, . . . , αi ∈ N, defineSq(x; k) =(log log x)k(log x)1/(q−1)+Oq((log log x)k−1(log x)1/(q−1)),and defineSq(x; k;α1, . . . , αi)=∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1)) ∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2(1 +O(1p2))· · ·∑pi≤x/3p1···pi−1pi 6=p1,...,pi−1νq(pi−1)=αi[1pi×(1 +O(1pi))((log log(x/p1 · · · pi))k(log(x/p1 · · · pi))1/(q−1) +Oq((log log(x/p1 · · · pi−1))k−1(log(x/p1 · · · pi))1/(q−1)))].Notice that the expressions Sq(x; k) and Sq(x; k;α1, . . . , αi) are given by asymptotic, not explicit, for-mulas. For instance, when i = 1, applying Proposition 2.3.12, we get thatSq(x; k;α1) =∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))((log log(x/p1))k(log(x/p1))1/(q−1)+Oq((log log x)k−1(log(x/p1))1/(q−1)))=(log log x)kqα1(log x)1/(q−1)+Oq((log log x)k−1(log x)1/(q−1))=1qα1Sq(x; k).Here, we are not claiming that Sq(x; k;α1) is exactly equal to 1qα1 Sq(x; k), but rather that these two expres-sions have identical main terms and error terms of equal magnitude.This observation generalizes to any natural number i, resulting in the following proposition.Proposition 2.3.14. Let Sq be defined as in Definition 2.3.13 and let i, k and α1, . . . , αi be positive integers.Then,Sq(x; k;α1, . . . , αi) =1qαiSq(x; k + 1;α1, . . . , αi−1),where the equals sign signifies that the two expressions have the same main terms and error terms of equalmagnitude.Proof. As defined above,Sq(x; k;α1, . . . , αi)=∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1)) ∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2(1 +O(1p2))· · ·∑pi≤x/3p1···pi−1pi 6=p1,...,pi−1νq(pi−1)=αi[1pi×(1 +O(1pi))((log log(x/p1 · · · pi))k(log(x/p1 · · · pi))1/(q−1) +Oq((log log(x/p1 · · · pi−1))k−1(log(x/p1 · · · pi))1/(q−1)))].32Applying Proposition 2.3.12 to the innermost sum, we get the following:Sq(x; k;α1, . . . , αi)=∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))· · ·∑pi−1≤x/3p1···pi−2pi−1 6=p1,...,pi−2νq(pi−1−1)=αi−1[1pi−1(1 +O(1pi−1))×((log log(x/p1 · · · pi−1))k+1qαi(log(x/p1 · · · pi−1))1/(q−1) +Oq((log log(x/p1 · · · pi−1))k(log(x/p1 · · · pi−1))1/(q−1)))]=1qαi∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))· · ·∑pi−1≤x/3p1···pi−2pi−1 6=p1,...,pi−2νq(pi−1−1)=αi−1[1pi−1(1 +O(1pi−1))×((log log(x/p1 · · · pi−1))k+1(log(x/p1 · · · pi−1))1/(q−1) +Oq((log log(x/p1 · · · pi−2))k(log(x/p1 · · · pi−1))1/(q−1)))],since(log log(x/p1 · · · pi−2pi−1))k(log(x/p1 · · · pi−1))1/(q−1) (log log(x/p1 · · · pi−2))k(log(x/p1 · · · pi−1))1/(q−1) .Definition 2.3.15. Let γ be a positive real number and let α1, . . . , αi be positive integers. Then, defineEq(x, γ;α1, . . . , αi) =∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pi≤x/3p1···pi−1pi 6=p1,...,pi−1νq(pi−1)=αi1pi(logxp1 · · · pi)−γ.Proposition 2.3.16. Let Eq be defined as in Definition 2.3.15. Then,Eq(x; γ;α1, . . . , αi−1, αi)q log log(x)Eq(x; γ;α1, . . . , αi−1).33Proof. Applying Proposition 2.3.9 to the innermost sum of Eq(x; γ;α1, . . . , αi−1, αi), we get:Eq(x; γ;α1, . . . , αi)=∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pi≤x/3p1···pi−1pi 6=p1,...,pi−1νq(pi−1)=αi1pi(logxp1 · · · pi)−γ∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pi−1≤x/3p1···pi−2pi−1 6=p1,...,pi−2νq(pi−1−1)=αi−11pi−1(log log(x/p1 · · · pi−1)qαi(log(x/p1 · · · pi−1))γ)q∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pi−1≤x/3p1···pi−2pi−1 6=p1,...,pi−2νq(pi−1−1)=αi−11pi−1(log log(x/p1 · · · pi−1)(log(x/p1 · · · pi−1))γ)≤∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pi−1≤x/3p1···pi−2pi−1 6=p1,...,pi−2νq(pi−1−1)=αi−11pi−1(log log x(log(x/p1 · · · pi−1))γ)= (log log x)Eq(x; γ;α1, . . . , αi−1).2.4 Evaluating D0Since we can only apply Corollary 2.2.9 if x/p1 · · · pj ≥ 3, we will start by splitting D0 from equation (2.2)into two multiply nested sums such that x/p1 · · · pj ≥ 3 in the first sum and x/p1 · · · pj < 3 in the secondsum. Doing so, we getD0(H,x) = CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-mt 6=p1,...,pj and t|m⇒t 6≡1 (mod q)1+ CH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-mt6=p1,...,pj and t|m⇒t6≡1 (mod q)1. (2.9)The following two propositions will evaluate the first and second sum of equation (2.9) respectively.34Proposition 2.4.1.CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-mt 6=p1,...,pj and t|m⇒t 6≡1 (mod q)1= BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j−1(log x)1/(q−1)).Proof. Throughout this proof, letJ := CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-mt 6=p1,...,pj and t|m⇒t 6≡1 (mod q)1.By Corollary 2.2.9, we get thatJ = CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj[Bqxp1 · · · pj(logxp1 · · · pj)−1/(q−1)×(1− 1q) j∏i=1(1− 1pi)−1+O(xp1 · · · pj(logxp1 · · · pj)−1−1/(q−1))]= BqCHx(1− 1q) ∑p1≤x/3νq(p1−1)=α1· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1p1 · · · pj(logxp1 · · · pj)−1/(q−1) j∏i=1(1− 1pi)−1+O(x∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1p1 · · · pj(logxp1 · · · pj)−1−1/(q−1))Now, since (1− 1pi)−1= 1 +O(1pi),35we have that,J = BqCHx(1− 1q)×∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1p1 · · · pj(logxp1 · · · pj)−1/(q−1) j∏i=1(1 +O(1pi))+O(x∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1p1 · · · pj(logxp1 · · · pj)−1−1/(q−1))= BqCHx(1− 1q) ∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1)) ∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2(1 +O(1p2))· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1/(q−1)(1 +O(1pj))+O(x∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1−1/(q−1)).(2.10)We will start by focusing on the nested sum in the main term. Applying Proposition 2.3.11 to the36innermost sum, we get that:∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1/(q−1)(1 +O(1pj))=∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))· · ·∑pj−1≤x/3p1···pj−2pj−1 6=p1,...,pj−2νq(pj−1−1)=αj−1[1pj−1(1 +O(1pj−1))×(log log(x/p1 · · · pj−1)qαj (log(x/p1 · · · pj−1))1/(q−1) +Oq(1(log(x/p1 · · · pj−1))1/(q−1)))]=1qαj∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))· · ·∑pj−1≤x/3p1···pj−2pj−1 6=p1,...,pj−2νq(pj−1−1)=αj−1[1pj−1(1 +O(1pj−1))×(log log(x/p1 · · · pj−1)(log(x/p1 · · · pj−1))1/(q−1) +Oq(1(log(x/p1 · · · pj−1))1/(q−1)))]. (2.11)Now, it follows that if we apply Proposition 2.3.14 to the nested sum in equation (2.11) j − 1 times, wewill get that∑p1≤x/3νq(p1−1)=α11p1(1 +O(1p1))· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1/(q−1)(1 +O(1pj))=1q∑ji=1 αi(log log x)j(log x)1/(q−1)+Oq((log log x)j−1(log x)1/(q−1)).Thus, from equation (2.10), we have thatJ = BqCHx(1− 1q)(1q∑ji=1 αi(log log x)j(log x)1/(q−1)+Oq((log log x)j−1(log x)1/(q−1)))+O(x∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1−1/(q−1))= BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j−1(log x)1/(q−1))+O(x∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1−1/(q−1)).37Now, we will evaluate the error term. Applying Proposition 2.3.16 to the error term j times, we get thatx∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pj≤x/3p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1pj(logxp1 · · · pj)−1−1/(q−1)q x(log log x)j(log x)1+1/(q−1).Therefore, we have thatJ = BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j−1(log x)1/(q−1))+Oq(x(log log x)j(log x)1+1/(q−1)).Now, since log log x log x, we have that(log log x)j(log log x)j−1 (log x)1+1/(q−1)(log x)1/(q−1),and thus,x(log log x)j(log x)1+1/(q−1) x(log log x)j−1(log x)1/(q−1).So,J = BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j−1(log x)1/(q−1)).Proposition 2.4.2.CH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-mt 6=p1,...,pj and t|m⇒t 6≡1 (mod q)1q x(log log x)j−1log x.Proof. First, notice that, in this sum, x/p1p2 · · · pj < 3 and thus,∑m≤x/p1···pjq-mt 6=p1,...,pj and t|m⇒t6≡1 (mod q)1 ≤ 2.38So, we get thatCH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj∑m≤x/p1···pjq-mt6=p1,...,pj and t|m⇒t 6≡1 (mod q)1≤ CH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj2= 2CH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1Notice that if x/p1 · · · pj−1 < 3, then ∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1 = 0.Therefore, we can assume that x/p1 · · · pj−1 ≥ 3. Similarly, if x/p1 · · · pi−1 < 3 for any i, then∑pi≤x/p1···pi−1pi 6=p1,...,pi−1νq(pi−1)=αi1 = 0.Thus, we have the following equality:2CH∑p1≤xνq(p1−1)=α1∑p2≤x/p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1= 2CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1.39Applying the prime number theorem to the innermost sum, we get that2CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1≤ 2CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj−1≤x/3p1···pj−2pj−1 6=p1,...,pj−2νq(pj−1−1)=αj−1pi(x/p1p2 · · · pj−1)∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑pj−1≤x/3p1···pj−2pj−1 6=p1,...,pj−2νq(pj−1−1)=αj−1x/p1 · · · pj−1log(x/p1 · · · pj−1)= x∑p1≤x/3νq(p1−1)=α11p1∑p2≤x/3p1p2 6=p1νq(p2−1)=α21p2· · ·∑pj−1≤x/3p1···pj−2pj−1 6=p1,...,pj−2νq(pj−1−1)=αj−11pj−1 log(x/p1 · · · pj−1) .Next, we can apply Proposition 2.3.16 j − 1 times, to get that,2CH∑p1≤x/3νq(p1−1)=α1∑p2≤x/3p1p2 6=p1νq(p2−1)=α2· · ·∑x/3p1···pj−1<pj≤x/p1···pj−1pj 6=p1,...,pj−1νq(pj−1)=αj1q x(log log x)j−1log xq x(log log x)j−1(log x)1/(q−1).Therefore, combining Propositions 2.4.1 and 2.4.2, we have shown that,D0(H,x) = BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j−1(log x)1/(q−1)).2.5 Evaluating D1(H, x)First, by definition of D1, we have thatD1((q;α1, . . . , αj), x) = #{n ≤ x : q ‖ n,Gq(n) = (q;α1, . . . , αj)}= #{n ≤ x/q : q - n,Gq(n) = (q;α1, . . . , αj)}= D0((q;α1, . . . , αj), x/q)40So, applying our results from the previous section, we get thatD0(H,x/q) = BqCH(q − 1q1+∑ji=1 αi)x(log log x/q)jq(log x/q)1/(q−1)+Oq(x(log log x/q)j−1q(log x/q)1/(q−1))= BqCH(q − 1q2+∑ji=1 αi)x(log log x/q)j(log x/q)1/(q−1)+Oq(x(log log x)j−1(log x/q)1/(q−1)).As shown in the proof of Proposition 2.3.12,(log log(x/q))j = (log log x)j +Oj((log log x)j−1log2 x).Also, by Proposition 2.3.2, if we suppose that x > q2, then(log x/q)−1/(q−1) = (log x)−1/(q−1) +Oq((log x)−1−1/(q−1)).Therefore,x(log log x/q)j(log x/q)1/(q−1)= x((log log x)j +Oj((log log x)j−1log2 x))((log x)−1/(q−1) +Oq((log x)−1−1/(q−1)))=x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j(log x)1+1/(q−1))+Oj(x(log log x)j−1(log x)2+1/(q−1))=x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j(log x)1+1/(q−1)).Now, since we are assuming that x > q2, we can apply Lemma 2.3.1 to get thatx(log log x)j−1(log x/q)1/(q−1) x(log log x)j−1(log x)1/(q−1).Thus, we have thatD0(H,x/q) = BqCH(q − 1q2+∑ji=1 αi)(x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j(log x)1+1/(q−1)))+Oq(x(log log x)j−1(log x)1/(q−1))= BqCH(q − 1q2+∑ji=1 αi)(x(log log x)j(log x)1/(q−1))+Oq(x(log log x)j−1(log x)1/(q−1)),sincex(log log x)j(log x)1+1/(q−1) x(log log x)j−1(log x)1/(q−1).412.6 Evaluating Dk(H, x) for k ≥ 2In this section, we show that for all k ≥ 2, Dk(H,x) will contribute to the error term of D(H,x).Proposition 2.6.1. Let H = (q;α1, . . . , αj). Then, for k ≥ 2,Dk(H,x)H x(log log x)j−1(log x)1/(q−1).Proof. Let k ≥ 2. Recall, from Section 2.1, that by definition,Dk(H,x) = #{n ≤ x : qk ‖ n,Gq(n) = H}.Notice that we can rewrite the above set as Dk(H,x) = #{n ≤ x/qk : q - n,Gq(qkn) = H}. Now, by theChinese Remainder Theorem, since q is an odd prime and q - n,Z×qkn∼= Z×qk × Z×n ∼= Zφ(qk) × Zφ(n) ∼= Zqk−1 × Zq−1 × Zφ(n).If k − 1 6∈ {α1, α2, . . . , αj}, it follows that Dk(H,x) = 0, and thus, our proposition will be triviallytrue. So, assume that αi = k − 1 for some i ∈ {α1, . . . , αj}. Then, it follows thatDk((q;α1, . . . , αj), x) = #{n ≤ x/qk : q - n,Gq(n) = (q;α1, . . . , αi−1, αi+1, . . . , αj)}= D0((q;α1, . . . , αi−1, αi+1, . . . , αj), x/qk).SinceD0((q;α1, . . . , αj), x) = BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+Oq(x(log log x)j−1(log x)1/(q−1)),we have thatD0((q;α1, . . . , αi−1, αi+1, . . . , αj), x/qk)H x(log log x)j−1(log x)1/(q−1).So, by the above proposition, we can see thatα1+1∑k=2Dk((q;α1, . . . , αj), x)H x(log log x)j−1(log x)1/(q−1).2.7 Evaluating D(H, x)Theorem 2.7.1. Let q be an odd prime, let H = (q;α1, α2, . . . , αj), and for a prime number p, let kp be theorder of p modulo q. Then,D(H,x) = KH(x(log log x)j(log x)1/(q−1))+OH(x(log log x)j−1(log x)1/(q−1)),42whereKH = BqCHEq,whereBq =1Γ(1− 1/(q − 1))((1− 1/q)−1/(q−1)∏p 6=qp 6≡1 (mod q)(1− 1/pkp)−1/kp∏χ 6=χ0L(1, χ)−1/(q−1)),CH =α1−1∏k=11(ak − ak+1)! ,andEq =q2 − 1q2+∑ji=1 αi.Proof. Recall from equation (2.1) thatD((q;α1, . . . , αj), x) =α1+1∑k=0Dk(q;α1, . . . , αj).Inputting the values of Dk found in Sections 2.4, 2.5 and 2.6, we get thatD(H,x) = BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+BqCH(q − 1q2+∑ji=1 αi)(x(log log x)j(log x)1/(q−1))+OH(x(log log x)j−1(log x)1/(q−1))= BqCH(q − 1q1+∑ji=1 αi)x(log log x)j(log x)1/(q−1)(1 +1q)+OH(x(log log x)j−1(log x)1/(q−1))= BqCH(q2 − 1q2+∑ji=1 αi)x(log log x)j(log x)1/(q−1)+OH(x(log log x)j−1(log x)1/(q−1))= KH(x(log log x)j(log x)1/(q−1))+OH(x(log log x)j−1(log x)1/(q−1)).43Chapter 3Counting Function for MaximallyNon-cyclic Multiplicative Groups3.1 SetupRather than focusing on local Sylow subgroups, we now wish to focus on the global structure of a group,and in particular, whether or not a group is cyclic. While not directly related to the problem we have spentthe first part of the thesis solving, the problem that we are about to introduce is of a similar nature. Countingfunctions of the number of integers n up to x such that Z×n is cyclic is a topic that has been well studiedin number theory. Consider, for instance, the following proposition, which can easily be proved using wellknown results.Proposition 3.1.1.#{n ≤ x : Z×n is cyclic} ∼32xlog x.Proof. First, we know that Z×n is cyclic if and only if n = 1, 2, 4, pr or 2pr, where p is an odd prime and ris a positive integer. Then,#{n ≤ x : Z×n is cyclic} = 3 +∑pr≤xp odd1 +∑2pr≤xp odd1= 3 +∑pr≤xp odd1 +∑pr≤x/2p odd1.44Since 2r ≤ x if and only if r ≤ log x/ log 2, we have that∑pr≤xp odd1 =∑pr≤x1 +O(log x),and thus,#{n ≤ x : Z×n is cyclic} = 3 +∑pr≤x1 +∑pr≤x/21 +O(log x).Now, notice that we can rewrite the sum of prime powers up to x as follows,∑pr≤x1 =∑p≤x1 +∑p2≤x1 +∑p3≤x1 + · · ·=∑p≤x1 +∑p≤x1/21 +∑p≤x1/31 + · · ·= pi(x) + pi(x1/2) + pi(x1/3) + · · ·= pi(x) +O(x1/2) +O(x1/2) + · · · ,and similarly, we can rewrite the sum of prime powers up to x/2 as follows,∑pr≤x/21 =∑p≤x/21 +∑p2≤x/21 +∑p3≤x/21 + · · ·=∑p≤x/21 +∑p≤(x/2)1/21 +∑p≤(x/2)1/31 + · · ·= pi(x/2) + pi((x/2)1/2) + pi((x/2)1/3) + · · ·= pi(x/2) +O(x1/2) +O(x1/2) + · · · .If r > log x/ log 2, then for any prime p, pr ≥ 2r > 2log x/ log 2 = x, and thus, we get∑pr≤x1 = pi(x) +log xlog 2O(x1/2) = pi(x) +O(x1/2 log x)and ∑pr≤x/21 = pi(x/2) +log xlog 2O(x1/2) = pi(x/2) +O(x1/2 log x).Now, by the Prime Number Theorem, we have that∑pr≤x1 =xlog x+O(xlog2 x)+O(x1/2 log x)and ∑pr≤x/21 =x/2log(x/2)+O(x/2log2(x/2))+O(x1/2 log x).45If we assume that x > 4, we can apply Lemma 2.3.1 and Proposition 2.3.2 to get that∑pr≤x/21 =x2((log x)−1 +O(log 2log2 x))+O(xlog2 x)+O(x1/2 log x)=x2 log x+O(xlog2 x)+O(x1/2 log x).Thus, so far, we have shown that#{n ≤ x : Z×n is cyclic} = 3 +xlog x+x2 log x+O(xlog2 x)+O(x1/2 log x).Since log3 x x1/2 implies that x1/2 log3 x x, and thus, x1/2 log x x/ log2 x, we have that#{n ≤ x : Z×n is cyclic} =32xlog x+O(xlog2 x).Thus, from here, it follows that#{n ≤ x : Z×n is cyclic} ∼32xlog x.This has led us to ask, what would make a group as non-cyclic as possible? Before we can define this,we need to define the primary decomposition and invariant factor decomposition of a group.Definition 3.1.2 (Primary Decomposition). The primary decomposition of a finite abelian group G is theunique decompositionG ∼= Zk1 × Zk2 × · · · × Zktsuch that k1, k2, . . . , kt are powers of primes.Definition 3.1.3 (Invariant Factor Decomposition). The invariant factor decomposition of a finite abeliangroup G is the unique decompositionG ∼= Zd1 × Zd2 × · · · × Zd`such that d1 | d2 | · · · | d`.Now, we can give the definition of a maximally non-cyclic group.Definition 3.1.4. Let G be a finite abelian group of order m, for some positive integer m. Let the followingbe its invariant factor decomposition:Zd1 × Zd2 × · · · × Zd` ,where d1 | d2 | · · · | d`. Then, we call G maximally non-cyclic if any of the four following equivalentconditions hold:46(1) for any prime q, its Sylow q-subgroup is of the formZq × Zq × · · · × Zq;(2) d` is minimal among all finite abelian groups of order m;(3) dj is squarefree for every 1 ≤ j ≤ `;(4) each factor of the primary decomposition of G is of the form Zp for some prime p.Below is a proof that the four conditions are indeed equivalent.Proof. Let G be a group of order m with invariant factor decomposition,Zd1 × Zd2 × · · · × Zd` ,where d1 | d2 | · · · | d`. Also, let {p1, p2, . . . , ps} be the set of all primes which divide m.(1) =⇒ (4): First, we can write G asG =s⊕i=1Gpiwhere, for each i, Gpi is the Sylow pi-subgroup of G. By condition (1), Gpi is of the form Zpi × · · · × Zpifor every i. Thus, it follows thatG =s⊕i=1mi⊕j=1Zpi ,for some positive integers m1, . . . ,ms. Notice that this must be the primary decomposition of G by defini-tion of primary decomposition, and thus, condition (4) holds.(4) =⇒ (3): Assume condition (4) holds. Then, since we construct the invariant factor decompositionof G by combining factors from the primary decomposition whose orders are relatively prime, and everyfactor from the primary decomposition is, by assumption, of the form Zp for some prime p, it follows thateach dj is squarefree.(3) =⇒ (2): Suppose that condition (3) holds. By construction of the invariant factor decomposition, weknow that d` dividesm and that pi divides d` for each 1 ≤ i ≤ s. Then, since d` is squarefree, it follows thateach pi must divide d` exactly once. Therefore, we must have that d` = p1p2 · · · ps. Now, suppose thatG′ isanother finite abelian group of order m with invariant factor decomposition, Zd′1 × Zd′2 × · · · × Zd′`′ , whered′1 | d′2 | · · · | d′`′ . Then, d′`′ must also be divisible by pi for each i in {1, 2, . . . , s}. So, p1p2 · · · ps | d′`′ ,and thus, d` | d′`′ , which implies that d` ≤ d′`′ . Since G′ was chosen arbitrarily, it follows that d` must beminimal among all finite abelian groups of order m.(2) =⇒ (1): We will argue this implication by contrapositive. Suppose that there exists some primepj , 1 ≤ j ≤ s, such that the Sylow pj-subgroup of G is of the form Zpα1j × Zpα2j × · · · × Zpαkj where471 ≤ α1 ≤ α2 ≤ · · · ≤ αk and αk > 1. Without loss of generality, we can assume that j = 1. Then,pαk1 must divide di for some 1 ≤ i ≤ `. Since d1 | d2 | · · · | d`, it follows that pαk1 divides d`. So,pαk1 p2 · · · ps | d` since pi divides d` for each 1 ≤ i ≤ s. However, from our previous cases, we can see thatit is possible to find a finite abelian group of order m such that d` = p1p2 · · · ps which is clearly a smallerd` than pαk1 p2 · · · ps since αk > 1. Thus, in this case, d` is not minimal among all finite abelian groups oforder m.We remark that these four equivalent conditions imply that l is maximal among all finite abelian groupsof order m, however this implication doesn’t go both ways. For instance, consider the following two finiteabelian groups of order 36: G1 ∼= Z2 × Z18 and G2 ∼= Z6 × Z6. Here, l = 2 for both groups. From theirinvariant factor decompositions, we can see that their primary factor decompositions areG1 ∼= Z2×Z2×Z9and G2 ∼= Z2 × Z2 × Z3 × Z3. Here, it is easy to see that G2 satisfies condition (1) of our definition, butthat G1 does not, since its Sylow 3-subgroup is Z9.Lemma 3.1.5. Let G ∼= G1 × G2 × · · · × Gj , where G,G1, . . . , Gj are finite abelian groups. Then, G ismaximally non-cyclic if and only if G1, . . . , Gj are maximally non-cyclic.Proof. By condition (4) of Definition 3.1.4, G is maximally non-cyclic if and only if each factor of itsprimary decomposition is of the form Zp for some prime p. SinceG andG1×G2×· · ·×Gj are isomorphic,their primary decompositions will be identical. So, each factor of the primary decomposition of G1 ×G2 ×· · ·×Gj will be of the form Zp, and thus, for each 1 ≤ i ≤ j, the primary decomposition ofGi can only havefactors of the form Zp. By condition (4) of Definition 3.1.4, each Gi must be maximally non-cyclic.Our goal throughout the remainder of this chapter is to estimate the counting function for the number ofn up to x such that Z×n is maximally non-cyclic. First, applying Chinese Remainder Theorem to Z×n , we getthatZ×n ∼= Z×2α ⊕⊕pβ‖np oddZ×pβ∼= Z×2α ⊕⊕pβ‖np oddZφ(pβ),where α ≥ 0 is an integer. Note that by Lemma 3.1.5, Z×n will be maximally non-cyclic if and only if Z×2αand Zφ(pβ) for each odd prime p with pβ ‖ n are all maximally non-cyclic.We will start by focusing on the factor corresponding to 2. If α is 0 or 1, then Z×2α will be the trivial48group. Otherwise,Z×2α ∼=Z2, if α = 2Z2 × Z2, if α = 3Z2α−2 × Z2, if α ≥ 4.Notice that condition (1) from Definition 3.1.4 will not be satisfied if α is greater than 3. Thus, it followsthat in order for Z×n to be maximally non-cyclic, we require that 24 does not divide n. Now, let p be an oddprime divisor of n and suppose that pβ ‖ n. Then,Zφ(pβ) ∼=Zp−1, if β = 1Zp × Zp−1, if β = 2Zpβ−1 × Zp−1, if β ≥ 3.Here, we can see that condition (1) from Definition 3.1.4 will not be satisfied if α is greater than 2 or if p−1is divisible by a square. Thus, it follows that in order for Z×n to be maximally non-cyclic, we require that ifp is an odd divisor n, then p3 does not divide n and p− 1 is squarefree. Therefore, we have that#{n ≤ x : Z×n is maximally non-cyclic}= #{n ≤ x : 24 - n, p3 - n for any odd prime p, and p | n⇒ p− 1 is squarefree}.So, we can see that this is another case of counting integers with restrictions on their prime factors.3.2 Useful PropositionsIn order to find a counting function for the number of n up to x such that Z×n is maximally non-cyclic, wefirst need to state and prove some useful propositions.Proposition 3.2.1. For any positive integer n,nφ(n)=∑d|nµ(d)2φ(d).Proof. First, since φ(n) = n∏p|n(1− 1/p), we have thatnφ(n)=nn∏p|n(1− 1/p)=∏p|n(1− 1/p)−1.Notice that n/φ(n) is a multiplicative function since both n and φ(n) are multiplicative functions. Also, wecan see that∑d|nµ(d)2φ(d) is a multiplicative function since it is the divisor sum of a multiplicative function.49Since both n/φ(n) and∑d|nµ(d)2φ(d) are multiplicative functions, showing that they are equal is equivalent tochecking that they agree on powers of primes. So, let q be a prime and let α be a positive integer. Then,qαφ(qα)=∏p|qα(1− 1/p)−1 = (1− 1/q)−1 = qq − 1 ,and ∑d|qαµ(d)2φ(d)= 1 +1q − 1 =qq − 1 .Therefore, from this, it follows that nφ(n) =∑d|nµ(d)2φ(d) for any positive integer n.Proposition 3.2.2. For any real number x,∑n≤xnφ(n)=ζ(2)ζ(3)ζ(6)x+O(x1/2).Proof. First, by Proposition 3.2.1, we have that∑n≤xnφ(n)=∑n≤x∑d|nµ(d)2φ(d).So, by switching the order of summation, we get∑n≤xnφ(n)=∑d≤xµ(d)2φ(d)∑n≤xd|n1 =∑d≤xµ(d)2φ(d)⌊xd⌋.Now, since bx/dc = x/d+O(1), we have that∑n≤xnφ(n)=∑d≤xµ(d)2φ(d)(xd+O(1))= x∑d≤xµ(d)2dφ(d)+O(∑d≤x1φ(d))= x∞∑d=1µ(d)2dφ(d)+O(x∑d>x1dφ(d)+∑d≤x1φ(d)). (3.1)Note that the convergence of the sum in the main term of (3.1) follows from (3.2). Then, since µ(d)2/dφ(d)is a multiplicative function, we can rewrite the coefficients of the main term of (3.1) as an Euler product as50follows,∞∑d=1µ(d)2φ(d)· d−1 =∏p(1 +µ(p)2φ(p)p−1 +µ(p2)2φ(p2)p−2 + · · ·)=∏p(1 +1p− 1p−1 + 0 + 0 + · · ·)=∏p(1 +1p(p− 1))=∏p(p2 − p+ 1p(p− 1)).Now multiplying the numerator and denominator by (p + 1)(p3 − 1) and then dividing the numerator anddenominator by p6, we get the following chain of equalities:∞∑d=1µ(d)2dφ(d)=∏p(p6 − 1p(p2 − 1)(p3 − 1))=∏p(1− 1/p6(1− 1/p2)(1− 1/p3))=∏p(1− p−2)−1∏p(1− p−3)−1∏p(1− p−6)−1.Since the Euler product representation of Riemann’s zeta function is ζ(s) =∏p(1 − p−s)−1, we can seethat ∞∑d=1µ(d)2dφ(d)=ζ(2)ζ(3)ζ(6).Now, we will simplify the error term of (3.1). First, since φ(d) d1− for any positive , taking = 1/2,we get thatx∑d>x1dφ(d) x∑d>x1d3/2 x∫ ∞x1t3/2dt = x(− 2t1/2) ∣∣∣∣∞x= x · 2x1/2 x1/2 (3.2)and ∑d≤x1φ(d)∑d≤x1d1/2∫ x11t1/2dt = 2t1/2∣∣∣∣x1= 2x1/2 − 2 x1/2.Substituting our revised main term and our simplified error term back into (3.1), we get that∑n≤xnφ(n)=ζ(2)ζ(3)ζ(6)x+O(x1/2).51Proposition 3.2.3. For any real number y, ∑n>y1nφ(n) 1y.Proof. First, notice that we can rewrite the above sum as follows,∑n>y1nφ(n)=∑n>ynφ(n)· 1n2.Then, since f(t) = 1/t2 is a continuous function, we can use a Riemann-Stieltjes integral to evaluate theabove sum: ∑n>y1nφ(n)=∫ ∞y1t2d(∑n≤tnφ(n))=1t2∑n≤tnφ(n)∣∣∣∣∞y−∫ ∞y∑n≤tnφ(n)d(1t2)= − 1y2∑n≤ynφ(n)+ 2∫ ∞y1t3∑n≤tnφ(n)dt.Now, since∑n≤xnφ(n) x by Proposition 3.2.2, we have that∑n>y1nφ(n) 1y2· y + 2∫ ∞y1t3· tdt=1y+ 2(−1t) ∣∣∣∣∞y 1y.Definition 3.2.4. Let ξ be Artin’s constant, that is,ξ =∏p(1− 1p(p− 1)).Proposition 3.2.5. Let C be any positive real constant. Then,#{p ≤ x : p− 1 is squarefree} = li(x)ξ +O(x(log x)C/2),where ξ is defined as in Definition 3.2.4 andli(x) =∫ x0dtln t.52Proof. First, notice that,#{p ≤ x : p− 1 is squarefree } =∑p≤x(µ(p− 1))2.Then, since (µ(p− 1))2 = ∑d2|p−1 µ(d) (equation (2.4) on p.36 of [4]), we have that#{p ≤ x : p− 1 is squarefree } =∑p≤x∑d2|p−1µ(d)=∑d2≤x∑p≤xd2|p−1µ(d)=∑d2≤xµ(d)∑p≤xd2|p−11=∑d≤√xµ(d)pi(x; d2, 1).By Corollary 11.21 from [4], for d2 < (log x)C ,pi(x; d2, 1) =li(x)ϕ(d2)+OC(xe−c1√log x),where c1 is a positive constant. So,∑d≤(log x)C/2µ(d)pi(x; d2, 1) =∑d≤(log x)C/2µ(d)(li(x)ϕ(d2)+OC(xe−c1√log x))= li(x)∑d≤(log x)C/2µ(d)ϕ(d2)+OC((log x)C/2xe−c1√log x).Since φ(d2) = dφ(d), we can see that∑d≤(log x)C/2µ(d)ϕ(d2)=∑d≥1µ(d)dφ(d)+O( ∑d>(log x)C/21dφ(d))=∏p(1− 1p(p− 1))+O(1(log x)C/2)= ξ +O(1(log x)C/2).The second equality above is valid due to Proposition 3.2.3. Thus, so far, we have that∑d≤(log x)C/2µ(d)pi(x; d2, 1) = li(x)ξ +O(li(x)(log x)C/2)+OC((log x)C/2xe−c1√log x).53Now, we can use the trivial estimate pi(x; d2, 1) 1 + x/d2, to get that∑(log x)C/2<d≤√xµ(d)pi(x; d2, 1)∑(log x)C/2<d≤√x(1 +xd2)∑(log x)C/2<d≤√x( xd2), since d >√x< x∑(log x)C/2<d(1d2)< x∫ ∞(log x)C/2−11t2dt x(log x)C/2.Thus,∑d≤√xµ(d)pi(x; d2, 1)= li(x)ξ +O(li(x)(log x)C/2)+OC((log x)C/2xe−c1√log x)+O(x(log x)C/2).Now, since lix x/ log x, we have that∑d≤√xµ(d)pi(x; d2, 1)= li(x)ξ +O(x(log x)1+C/2)+OC((log x)C/2xe−c1√log x)+O(x(log x)C/2)= li(x)ξ +O(x(log x)C/2)+OC((log x)C/2xe−c1√log x).Now, sincelimx→∞(log x)Cec1√log x= 0,we have that (log x)C = o(ec1√log x), and thus (log x)C ec1√log x. From here, it follows thatx(log x)C/2ec1√log x x(log x)C/2,and thus, ∑d≤√xµ(d)pi(x; d2, 1) = li(x)ξ +O(x(log x)C/2).54Let A = {p : p− 1 is squarefree}. Then, we can calculate the density d(A) of A as follows:d(A) = limx→∞#{p ≤ x : p− 1 is squarefree }pi(x)Notice that, as stated in the next proposition, d(A) turns out to be Artin’s constant.Proposition 3.2.6. d(A) = ξ, where ξ is as defined in Definition 3.2.4.Proof. First, by Proposition 3.2.5,d(A) = limx→∞li(x)ξ +O(x(log x)C/2)pi(x)= limx→∞(li(x)pi(x)ξ +O(xpi(x)(log x)C/2)).Now, by the Prime Number Theorem, we have thatxpi(x)(log x)C/2 x log xx(log x)C/2= (log x)1−C/2.Let C > 2. Then, 1− C/2 < 0, and so, as x goes to infinity, the above error term goes to 0.Also, by the Prime Number Theorem, we know thatlimx→∞li(x)pi(x)= 1.Therefore, it follows that, d(A) = ξ.3.3 Counting integers n such that Z×n is maximally non-cyclicIn order to prove Proposition 3.3.2, we will need to use the Wirsing-Odoni Method. Below is a statement ofthe method taken directly from [1]:Proposition 3.3.1 (Wirsing Odoni Method). Let f be a multiplicative function. Suppose that there existconstants u and v such that 0 ≤ f(pr) ≤ urv for all primes p and all positive integers r. Suppose also thatthere exist real numbers ω > 0 and 0 < β < 1 such that∑p<Pf(p) = ωPlogP+O(P(logP )1+β)as P →∞. Then the product over all primesCf =1Γ(ω)∏p(1 +f(p)p+f(p2)p2+f(p3)p3+ · · ·)(1− 1p)ξ55converges (hence is positive), and∑n<Nf(n) = CfN(logN)ω−1 +Of (N(logN)ω−1−β)as N →∞.Proposition 3.3.2.#{n ≤ x : Z×n is maximally non-cyclic} ∼ Cfx(log x)1−ξ,where ξ is as defined in Definition 3.2.4 and Cf is the convergent product,Cf =1514Γ(ξ)limx→∞( ∏p≤xp−1 squarefree(1 +1p+1p2)∏p≤x(1− 1p)ξ ).Proof. Recall that, as shown in Section 3.1,#{n ≤ x : Z×n is maximally non-cyclic}= #{n ≤ x : 24 - n, p3 - n for any odd prime p, and p | n⇒ p− 1 is squarefree}.Letf(n) ={1, if 24 - n, p3 - n for any odd prime p and p | n⇒ p− 1 is squarefree,0, otherwise.Then, f is multiplicative and for any prime p and natural number r, 0 ≤ f(pr) ≤ 1 ≤ 2 · r1. Also, byProposition 3.2.5, we have that ∑p≤xf(p) = #{p ≤ x : p− 1 is squarefree}= li(x)ξ +O(x(log x)C/2).Sinceli(x) =xlog x+O(xlog2 x),we get that ∑p≤xf(p) =[xlog x+O(xlog2 x)]ξ +O(x(log x)C/2)=xlog xξ +O(x(log x)min(2,C/2)).56Choosing C > 4, we get that,∑p≤xf(p) = ξxlog x+O(x(log x)2)= ξxlog x+O(x(log x)1+β),where 0 < β < 1. Then, applying Proposition 3.3.1, we get thatCf =1Γ(ξ)∏p(1 +f(p)p+f(p2)p2+f(p3)p3+ · · ·)(1− 1p)ξ=1Γ(ξ)·(1 + 12 +14 +18)(1 + 12 +14) limx→∞( ∏pp−1 squarefree(1 +1p+1p2)∏p(1− 1p)ξ )=1514Γ(ξ)limx→∞( ∏pp−1 squarefree(1 +1p+1p2)∏p(1− 1p)ξ )converges and ∑n≤xf(n) = Cfx(log x)ξ−1 +Of(x(log x)ξ−1−β).The statement of the proposition follows directly from this.57Chapter 4ConclusionTo conclude, throughout this thesis, we have examined multiple counting functions of integers with restric-tions on their prime factors. First, in Chapter 2, we proved that for a fixed odd prime q and a fixed q-groupH = Zqα1 ×Zqα2 ×· · ·×Zqαj , the counting function for the number of n up to x for which H is the Sylowq-subgroup of Z×n isD(H,x) = KH(x(log log x)j(log x)1/(q−1))+OH(x(log log x)j−1(log x)1/(q−1)),where KH is a constant that depends on H . Then, in Chapter 3, we proved that the number of n up to xsuch that Z×n is cyclic is asymptotic to 32x/ log x and that the number of n up to x such that Z×n is maximallynon-cyclic is asymptotic to Cfx/(log x)1−ξ, where ξ is Artin’s constant and Cf is the convergent product,Cf =1514Γ(ξ)limx→∞( ∏p≤xp−1 squarefree(1 +1p+1p2)∏p≤x(1− 1p)ξ ).As a next step, given a fixed finite abelian groupG of orderm, it might be interesting to consider the problemof finding an asymptotic formula for the number of n up to x such that G is not contained in Z×n .58Bibliography[1] Steven Finch, Greg Martin, and Pascal Sebah. Roots of unity and nullity modulo n. Proc. Amer. Math.Soc., 138(8):2729–2743, 2010.[2] Kevin Ford, Florian Luca, and Pieter Moree. Values of the Euler φ-function not divisible by a givenodd prime, and the distribution of Euler-Kronecker constants for cyclotomic fields. Math. Comp.,83(287):1447–1476, 2014.[3] Edmund Landau. U¨ber die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Min-destzahl der zu ihrer additiven Zusammensetzung enforderlichen Quadrate. Arch. der Math. und Phys.,13(3):305–312, 1908.[4] Hugh L. Montgomery and Robert C. Vaughan. Multiplicative number theory. I. Classical theory, vol-ume 97 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge,2007.[5] Ge´rald Tenenbaum. Introduction to analytic and probabilistic number theory, volume 163 of GraduateStudies in Mathematics. American Mathematical Society, Providence, RI, third edition, 2015. Translatedfrom the 2008 French edition by Patrick D. F. Ion.59
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Counting integers with restrictions on their prime...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Counting integers with restrictions on their prime factors Downey, Jenna 2019
pdf
Page Metadata
Item Metadata
Title | Counting integers with restrictions on their prime factors |
Creator |
Downey, Jenna |
Publisher | University of British Columbia |
Date Issued | 2019 |
Description | In this thesis, we examine two problems that, on the surface, seem like pure group theory problems, but turn out to both be problems concerning counting integers with restrictions on their prime factors. Fixing an odd prime number q and a finite abelian q-group H=ℤqᵅ₁×ℤqᵅ₂×⋯×ℤqᵅʲ, our first aim is to find a counting function, D(H,x), for the number of integers n up to x such that H is the Sylow q-subgroup of (ℤ/nℤ)×. In Chapter 2, we prove that D(H,x)∼ K_H x(log log x)ʲ/(log x)⁻¹/⁽q⁻¹⁾, where K_H is a constant depending on H. The second problem that we examine in this thesis concerns counting the number of n up to x for which (ℤ/nℤ)× is cyclic and for which (ℤ/nℤ)× is maximally non-cyclic, where (ℤ/nℤ)× is said to be maximally non-cyclic if each of its invariant factors is squarefree. In Chapter 3, we prove that the number of n up to x such that (ℤ/nℤ)× is cyclic is asymptotic to (3/2)x/log x and that the number of n up to x such that (ℤ/nℤ)× is maximally non-cyclic is asymptotic to C_f x/(log x)¹⁻ξ, where ξ is Artin's constant and C_f is the convergent product, C_f=(15/14Γ(ξ)) limₓ→∞ (∏_p≤ₓ\\{p-₁ square-free} (1+(1/p)+(1/p²)) ∏_p≤ₓ (1-(1/p))^ξ). It turns out that both of these problems can be reduced to problems of counting integers with restrictions on their prime factors. This allows the problems to be addressed by classical techniques of analytic number theory. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2019-06-06 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NoDerivatives 4.0 International |
DOI | 10.14288/1.0379324 |
URI | http://hdl.handle.net/2429/70561 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2019-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2019_may_downey_jenna.pdf [ 395.76kB ]
- Metadata
- JSON: 24-1.0379324.json
- JSON-LD: 24-1.0379324-ld.json
- RDF/XML (Pretty): 24-1.0379324-rdf.xml
- RDF/JSON: 24-1.0379324-rdf.json
- Turtle: 24-1.0379324-turtle.txt
- N-Triples: 24-1.0379324-rdf-ntriples.txt
- Original Record: 24-1.0379324-source.json
- Full Text
- 24-1.0379324-fulltext.txt
- Citation
- 24-1.0379324.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0379324/manifest