Various Problems on Subproducts of Residue ClassesModulo a PrimebyAmir Hossein ParvardiA 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)August 2019c© Amir Hossein Parvardi, 2019The following individuals certify that they have read, and recommend to the Faculty of Graduate and Postdoctoral Studies for acceptance, a thesis/dissertation entitled: Various problems on subproducts of residue classes modulo a prime submitted by Amir Hossein Parvardi in partial fulfillment of the requirements for the degree of Master of Science in Mathematics Examining Committee: Greg Martin Supervisor Greg Martin Supervisory Committee Member Mike Bennett Supervisory Committee Member Additional Examiner Additional Supervisory Committee Members: Supervisory Committee Member Supervisory Committee Member ii AbstractLet p be a prime number. In [1], Booker and Pomerance find an integer y with 1 < y ≤ p such that allnon-zero residue classes modulo p can be written as a square-free product of positive integers up to y. Letus denote by y(p) the smallest such y. Booker and Pomerance show in their paper that except for p = 5 and7, we have y(p) ≤ y and some better upper bounds were conjectured.Later, Munsch and Shparlinski [7] proved those conjectures with even better localization. Their work wasdone as the same time as ours, but with fairly more complicated methods in the proof. We were seeking tofind a solution for the problem using Po´lya-Vinogradov inequality or at most its improvement, the Burgessbound on character sums. That being said, we removed the condition in the problem that the product hasto be square-free. We proved that for m > p1/(4√e)+o(1), each residue class b of (Z/pZ)× can be writtenas a product of elements of the set {1, 2, . . . ,m} modulo p. In fact, we showed that the number of suchsub-products (congruent to b (mod p)) is asymptotic to 2m/(p− 1).The proofs are based on an identity involving sums of Dirichlet characters modulo p as well as the Burgessinequality on partial character sums. Basically, we use proof by contradiction to state that if the error term(for number of sub-product) is large, then there should be many χ values close to 1, which would result inthe character sum being large, thereby contradicting the Burgess inequality (which essentially says boundsthe character sums).iiiLay SummaryLet p be a prime number and m < p a positive integer. Consider the set A = {1, 2, . . . ,m}. Multiplyingsome elements in this set and taking modulo p gives us an integer in the set {1, 2, . . . , p − 1}. One mightask if it is possible to hit all these p− 1 residue classes by multiplying elements of A. Of course, the answerto this question is negative if m is too small. For instance, if m is too small, it is possible that the largestpossible product, m!, is less than p − 1 and this means we cannot hit p − 1. Hence, it makes sense to askthis modified question: what is the smallest m for which we can hit all the residue classes? This problem,as well as several similar problems, have been studied deeply in the past.We can make the problem more difficult by requiring the products to have disitinct elements of A. Again,we must note that this question is worthy only when m satisfies a lower bound. Using cutting edge resultsin number theory such as Burgess inequality, we can expect a possible lower bound for this problem. In thisproject, our goal is to prove that the expected bound indeed holds, and it is the best we can get consideringthe tools we have in hand. We show that for m > p1/(4√e)+ε (for small ε), every element in {1, 2, . . . , p− 1}will be hit approximately 2m/(p− 1) times by products (mod p) of numbers from {1, 2, . . . ,m} where eachproduct has distinct elemets.One can follow this path further and ask what is the smallest m for which it is possible to hit all non-zeroresiude classes mod p as a product of elements from {1, 2, . . . ,m}, if we require the products not only to havedistinct elements, but to be squarefree as well. Let’s denote by y(p) the smallest such m. This turns out tobe a more complicated question, which was posed by Booker and Pomerance [1]. In fact, we were motivatedby their results (e.g., that y(p) ≤ p for all primes p > 7) to find a better bound for y(p). However, wesoon realized that our usual techniques will not work on this problem. Munsch and Shparlinski [7] happenedto be working on the same problem coincidentally with us, and their proofs using heavy and complicatedcomputational partial character sums convinced us that the problem is far more difficult to be solved withour approach. That being said, we decided to work on the easier version of the problem, which was mentionedin the second paragraph.ivPrefaceThis thesis is an original, unpublished work by Amir Hossein Parvardi, under the supervision of Greg Martinfrom the mathematics department at The University of British Columbia.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 The Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Proof Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 The General Case:Subproducts Congruent to b (mod p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 The Case m > p1/4+ε . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 The Case m > p1/(4√e)+ε . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13A Proof of Proposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14B Proof of Propositions 14 and 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17viList of Figures1.1 Proof strategy: all χ values lie in the 2θ arc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Angle θ and the arc M˙CN in the unit circle in Lemma 11. . . . . . . . . . . . . . . . . . . . 72.2 Angles κj in the proof of Theorem 13. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11viiAcknowledgementsThanks to Professor Greg Martin for his guidance and helpful comments on my thesis. I’m thankful to mylovely wife, Nadia Ghobadipasha, for her full support during my master’s education.viiiChapter 1Introduction1.1 The ProblemsIn this thesis, I will focus on three main problems. The first one is relatively the “easiest” among the three.Problem 1. Let p ≥ 3 be a prime and m < p a positive integer. Does the set {1, 2, . . . ,m} generate allnon-zero residue classes modulo p under multiplication?This problem is rather well-known in the context. We first need to notice that in order to get a positiveanswer for this problem, m cannot be too small. Let us denote by G(p) the smallest m which gives a positiveanswer to Problem 1 for a given p. Also, let n2(p) denote the smallest quadratic non-residue modulo p. Itis then clear that n2(p) ≤ G(p) because otherwise we can write n2(p), which is a non-residue, as a productof smaller numbers (mod p) which are all quadratic resiudes, which is not possible since the product ofquadratic residues modulo p gives a residue.Let us now see how small can n2(p) be. In 1918, Vinogradov [9] established a bound for a more generalfunction of p, nχ(p), which is the smallest n with χ(n) 6= 1, where χ is a non-principal character (mod p).He showed that nχ(p) p1/(2√e)(log p)2 (c.f. [5]). We know from elementary number theory that the Jacobisymbol, which basically represents a number being a quadratic residue or not, is in fact a (real) Dirichletcharacter. If we assume the χ to be the Jacobi symbol mod p, then nχ = n2(p) and we have an upper boundon n2(p).Later, Burgess [2–4] proved better bounds in a series of papers, the strongest of which is stated inProposition 2 (see also [5]). An accessible account of the proof of this proposition can be found in [6,Corollary 9.19].Proposition 2. Let χ be a non-principal character modulo p, and let nχ denote the smallest positive integern such that χ(n) 6= 1. Then, nχ p1/(4√e)+o(1).We will give a full proof to this proposition in Appendix A. We would like to note here that the exponent1/(4√e) arises naturally in the proof and we will see it a lot in the upper bounds we find.Before moving to the new problem, we will mention one more property for G(p): let g(p) be the smallestprimitive root modulo p (which we know exists), then G(p) ≤ g(p) because powers of g(p) generate the fullunit group (mod p). Hence, n2(p) ≤ G(p) ≤ g(p). Pollack [8] proves numerous interesting results on G(p)and g(p).1Let’s move on to the next problem, which is more difficult and was proposed by Booker and Pomerance [1]. This time, we require the product to satisfy some conditions.Problem 3. For a prime p ≥ 3 and integer 1 ≤ m ≤ p, is it possible to write all elements of (Z/pZ)× as asquare-free, m-friable positive integer? How small can m be for this to be possible?Let y(p) be the smallest m for which Problem 3 has a positive answer. Booker and Pomerance show intheir paper that y(p) indeed exists and is at most p for all primes p > 7. In fact, they show that for any suchprime and any a ∈ Z, there is a square-free, p-friable positive integer n ≤ pO(log p) such that n ≡ a (mod p).Munsch and Shparlinski [7] improve this result and show that all residue classes can be represented by apositive square-free integer s ≤ p2+o(1) which is p1/(4√e)+o(1)-friable.When we first started working on this thesis, we tried to solve Problem 3 but we soon realized that itis truly difficult. Fortunately, Munsch and Shparlinski’s paper [7], which is heavily computational and usespartial character sums, was published during the time we were working on the problem and we found outhow difficult Problem 3 really is. That being said, we relaxed the conditions of the problem and made theso-called “medium problem” (if we consider Problems 1 and 3 easy and difficult, respectively) in this context:Problem 4. Let p ≥ 3 be a prime and m > 1 and integer. Given an integer b not divisible by p,1. Is it possible for a sub-product of A = {1, 2, . . . ,m} to be congruent to b modulo p?2. If yes, how many such sub-products exist?Again, the answer to Problem 4 definitely depends on m. In fact, if we choose m too small, the answerto the second question in Problem 4 will be zero. There are a few questions that we might ask here. First,how small can m be? Second, if we choose m large enough, what is the answer to the second question?For the former question, we expect the best lower bound on m to be p1/(4√e)+o(1). One must note that by“the best lower bound,” we mean the best bound assuming our cutting-edge tecnology, which is the Burgessinequality. In fact, the unusual power 1/(4√e) comes into our computations because of Burgess, and if wecan improve Burgess, all our results would be improved. However, improving Burgess is not easy and so theactual best lower bound for this problem is possibly much smaller than p1/(4√e).For m > p1/(4√e)+o(1) we prove that the main term in the answer to Problem 4 is 2m/(p − 1). This isnot unexpected because there are a total of 2m possible products with elements chosen from {1, 2, . . . ,m}and p− 1 non-zero residue classes mod p. This is our main theorem:Theorem 5. Let p be a prime, m and b positive integers with b not divisible by p. Denote by Sm(b) thenumber of sub-products of {1, 2, . . . ,m} which are congruent to b mod p. Then, if m > p1/(4√e)+o(1), for anyreal ε > 0,Sm(b) =2mp− 1 +O(2mp2). (1.1)21.2 Proof StrategiesLet’s consider Problem 4 in a more general form:Problem 6. Let p ≥ 3 be a prime. Given an integer b not divisible by p and a set A = {a1, a2, . . . , ak}(taken mod p), define SA(b) as the number of subproducts (mod p) of A which are congruent to b modulop. Find an estimate for SA(b).The basic main idea for solving Problem 6 is a counting argument using the well-known orthogonalityproperty of Dirichlet characters. As this is a famous fact, we will use it as a lemma here.Lemma 7. Let q > 1 be an integer. For any integer n1φ(q)∑χ (mod q)χ(n) =1, if n ≡ 1 (mod q),0, otherwise.Let us get back to Problem 6. We want b to be a product of elements of A mod p. That is, wewant to find ji ∈ {0, 1}, 1 ≤ i ≤ k, so that b ≡ aj11 aj22 · · · ajkk (mod p). Applying Lemma 7 to n =aj11 aj22 · · · ajkk b−1 (mod p), we find that1p− 1∑χ (mod p)χ(aj11 aj22 · · · ajkk b−1) =1, if b ≡ aj11 aj22 · · · ajkk (mod p),0, otherwise.(1.2)We can use equation (1.2) to count the number of sub-products of A which are congruent to b (mod p). Infact,SA(b) =1p− 11∑j1=01∑j2=0· · ·1∑jk=0∑χ (mod p)χ(aj11 aj22 · · · ajkk b−1)=1p− 1∑χ (mod p)χ(b−1)k∏i=1(1 + χ(ai)) . (1.3)In equation (1.3), the term corresponding to χ = χ0 (the principal character mod p) contributes 2k/(p− 1).In the next chapters of this thesis, we will show that this term is the main term in the expression and thecontribution from other characters can be considered as the error term, as they are smaller.If we now consider the more specific question in Problem 4 where A = {1, 2, . . . ,m}, the above discussiontells us that we are trying to prove the following:∣∣∣∣∣∣∣∣1p− 1∑χ (mod p)χ 6=χ0m∏j=1|1 + χ(j)|∣∣∣∣∣∣∣∣ = o(2mp− 1). (1.4)To prove this, we suppose on the contrary that for some character χ,∏mj=1 |1 + χ(j)| is large, say, 2m/p.Assuming this, we can prove that the number of integers j in {1, 2, . . . ,m} for which |1−χ(j)| > 1/ log log pis log p log log p. When seeing this on a unit circle as in Figure 1.1, one finds that there exists some integerj and real θ > 0 for which χ(n) for all n ∈ {1, 2, . . . ,m} lies in the 2θ arc shown in the figure.This in turn means that the values of χ are close to 1, and so the sum∑1≤j≤m χ(j) would be large.After taking care of the details of the proof, we arrive at the conclusion that for m p1/(4√e)+o(1), thislatter sum is ε y, and this contradicts the Burgess inequality [2].3O ACχ(j)χ(j)θθ|1 + χ(j)||1 + χ(j)||1−χ(j)||1−χ(j)|Figure 1.1: Proof strategy: all χ values lie in the 2θ arc.We will show the proof to equation (1.4) for the special case when m = p − 1. In other words, we willshow thatTheorem 8. For any b not divisible by p,Sp−1(b) =2p−1p− 1 +O(2p−1p2)(1.5)Proof. Using equation (1.3) for A = {1, 2, . . . , p− 1}, we find thatSp−1(b) =1p− 1∣∣∣∣∣∣∑χ (mod p)p−1∏j=1(1 + χ(j))∣∣∣∣∣∣ = 2p−1p− 1 +1p− 1∑χ (mod p)χ 6=χ0p−1∏j=1|1 + χ(j)| . (1.6)To prove equation (1.5), it suffices to show that1p− 1∑χ (mod p)χ 6=χ0p−1∏j=1|1 + χ(j)| 2p−1p2(1.7)4Suppose that χ 6= χ0 is a character of order d. That is, d is the smallest positive integer that χ(n)d = 1 forall integers n with (n, p) = 1. Since we assumed χ is not principal, d > 1. Since the values of χ(n) are alldth roots of unity, and d | p− 1, we can writep−1∏j=1|1 + χ(j)| =∣∣∣∣∣d∏k=1(1 + e(kd))∣∣∣∣∣(p−1)/d, (1.8)where e(x) = e2piix. On the other hand, for all real x,xd − 1 =d∏k=1(x− e (kd)) . (1.9)Plugging x = −1 in equation (1.9) and using equation (1.8), we getp−1∏j=1|1 + χ(j)| = ∣∣(−1)d − 1∣∣(p−1)/d . (1.10)Depending on the parity of d, this isp−1∏j=1|1 + χ(j)| =0, if d ≡ 0 (mod 2),2(p−1)/d, if d ≡ 1 (mod 2).Hence, we can write the left-hand side of equation (1.7) as1p− 1∑χ (mod p)χ 6=χ0p−1∏j=1|1 + χ(j)| = 1p− 1∑d|p−1d oddd>1∑χ (mod p)ord(χ)=d2(p−1)/d 2p−1p2, (1.11)and the proof is complete.5Chapter 2The General Case:Subproducts Congruent to b (mod p)Problem 9. Let p and b be defined as in Problem 6 and suppose thatA = {a1, a2, . . . , ak} = {1, 2, . . . ,m},where m < p. We aim to find an estimate similar to that of equation (1.5) for this case as well. Let Sm(b)be the number of subproducts of {1, 2, . . . ,m} which are congruent to b mod p.We do not really expect Sb(m) to be large (or even positive) when m is too small. So, it is natural toexpect some lower bound on m for Problem 9 to have a positive answer. We will prove that the best lowerbound for m is p1/(4√e)+ε (which happens to be the bound for various other problems in number theory assaid before; cf. e.g., [6, Corollary 9.19]). Here, one should notice that we mean p1/(4√e)+ε is the best lowerbound we can expect to get given certain other known current obstacles – not the best lower bound that istheoretically possible.We first proved the theorem with a weaker bound on m. In fact, we removed the√e in the exponentand found a proof when m > p1/4+ε. Later, we found an interesting proof for the original problem (whenm > p1/(4√e)+ε), but it was different from the previous proof. We are going to provide both proofs here.2.1 The Case m > p1/4+εTheorem 10. For any prime p, real number ε > 0, and integer m > p1/4+ε,Sm(b) =2mp− 1 +O(2mp2), (2.1)with Sm(b) as in Problem 9.The following lemma and the corollary right after it help us in the proof of Theorem 10.Lemma 11. Let p be a prime number, ε > 0 any real number, m an integer with m > p1/4+ε, and0 < θ < pi/2. Also, suppose that t > 1 be a real number such that t > 1/ cos θ + 1. Then, there are at leastm/t integers j ∈ {1, 2, . . . ,m} such that χ(j) lies on the arc M˙CN of the unit circle, as shown in Figure 2.1.6O ACMNθθFigure 2.1: Angle θ and the arc M˙CN in the unit circle in Lemma 11.Proof. Let R(m) and L(m) be the number of values of χ(j) which lie on the arcs M˙AN and M˙CN , respec-tively. Suppose for the sake of contradiction that L(m) < m/t. This means that R(m) > (t− 1)m/t. Notethat <(χ(j)) ≥ cos θ when χ(j) is on the arc M˙AN and χ(j) ≥ −1 for all j. Therefore,< m∑j=1χ(j) ≥ R(m) · cos θ − L(m) > (t− 1)mt· cos θ − mt= m((t− 1) cos θ − 1t). (2.2)By our choice of t in the statement of the lemma (t > 1/ cos θ + 1), the coefficient of m in equation (2.2) ispositive. However, by Burgess [6, Theorem 9.27], we know thatm∑j=1χ(j) = o(m), when m > p1/4+ε, (2.3)which is in contradiction with equation (2.2). You can see a proof of equation (2.3) in Appendix A (followequations (A.10) to (A.13)). The proof is complete.Corollary 12. Choose θ such that cos θ =√2− 1. Also, choose t = 4. Then, for any m > p1/4+ε, at leastm/4 integers j ∈ {1, 2, . . . ,m} have χ(j) on the arc M˙CN .Proof of Theorem 10. The main term, 2m/(p− 1), comes from the principal character (in a similar mannerto equation (1.6)). In fact,Sm(b) =1p− 1∣∣∣∣∣∣∑χ (mod p)m∏j=1(1 + χ(j))∣∣∣∣∣∣ = 2mp− 1 +1p− 1∑χ (mod p)χ 6=χ0m∏j=1|1 + χ(j)| . (2.4)7Choose θ and t in Lemma 11 as given in the corollary. We know that for each j for which χ(j) lies on thearc M˙CN , the maximum value of |1 + χ(j)| is the length of the segment CM , which is equal to√(1 + cos θ)2 + sin2 θ =√2 + 2 cos θ =√2 + 2(√2− 1) = 23/4.For each j such that χ(j) lies on the arc M˙AN , we will use the trivial bound |1 + χ(j)| ≤ 2.Then, since for at least m/4 integers j, χ(j) lies on the arc M˙CN , the product in the error term ism∏j=1|1 + χ(j)| ≤(23/4)m/4︸ ︷︷ ︸Contribution from M˘CN· 23m/4︸ ︷︷ ︸Contribution from M˘AN= 215m/16.Since there are p− 2 non-principal characters modulo p, the second term on the rightmost side of equation(2.4) is1p− 1∑χ mod pχ 6=χ0m∏j=1|1 + χ(j)| ≤ 1p− 1 · (p− 2) · 215m/16 =p− 2p− 1 · 215m/16 ≤ 2mp2.The last step holds sincep− 2p− 1 · 215m/16 ≤ 2mp2⇐⇒ m ≥16 log(p2(p−2)p−1)log 2,which obviously holds because m > p1/4+ε log p.2.2 The Case m > p1/(4√e)+εAs mentioned before, we would like to improve the bound on m in Theorem 10 from m > p1/4+ε tom > p1/(4√e)+ε. In other words, we want to proveTheorem 13. For any prime p, real number ε > 0, and integer m > p1/(4√e)+ε,Sm(b) =2mp− 1 +O(2mp2), (2.5)with Sm(b) as defined in Problem 9.We will prove two propositions which will help us in the proof of Theorem 13. We postpone the proofsof these propositions to Appendix B.Proposition 14. Let k and m be positive integers. If n is an m-friable number that is less than m(k+1)/2,then n can be factored as n = b1b2 · · · bk so that each bj ≤ m.Remark. The exponent (k + 1)/2 is best possible: if n is the product of k + 1 primes each slightly largerthan m1/2, then no such k-way factorization is possible.Proposition 15. Let k and m be positive integers and let ε be a positive real number that is sufficientlysmall in terms of k. If n is an m-friable number such that m(1+ε)k/2 < n < m(k+1)/2, then n can be factoredas n = b1b2 · · · bk′ with k′ ≤ k so that each mε < bj ≤ m.8Remark. The lower bound (1+ε)k/2 is best possible: if m is q times the product of k/2 primes each of whichis very slightly less than m, where q is a prime slightly smaller than mε, then no such k-way factorization ispossible. Note also that we just need (k + 1)/2 larger than e1/2 for our application, so k = 3 suffices.We are ready to prove Theorem 13 right after we prove the following lemmas. Lemma 16 is implicitlyproved in Appendix A but we give a short proof here as well. You can find more details in the appendix.Lemma 16. Let m and y be positive integers such that m ≤ y ≤ m2. Define as usual by ψ(y,m) thenumber of m-friable positive integers up to y. Then,ψ(y,m) = y(1− log log ylogm)+O(ylog y). (2.6)Consequently, the number of non-m-friable positive integers up to y is y log(log y/ logm) +O(y/ log y).Proof. Since m ≤ y ≤ m2, any positive integer n ≤ y has at most one prime factor in (√y, y]. Therefore,ψ(y,m) = y −∑m<p≤y∑n≤yp|n1 = y −∑m<p≤y⌊yp⌋= y − y∑m<p≤y1p+O(pi(y)). (2.7)Using prime number theorem and Mertens’ estimate for∑1/p [6, Theorem 2.7] (also stated in equation(A.5) in Appendix A), we can verify the equation (2.6). The number of non-m-friable positive integers upto y is then y − ψ(y,m) = y log(log y/ logm) +O(y/ log y).Lemma 17. Suppose that∏mj=1 |1 +χ(j)| 2m/p. Let N be the number of integers j ∈ {1, 2, . . . ,m} suchthat |χ(j)− 1| > 1/ log log p. Then, N log p(log log p)2.Proof. By Pythagorean theorem, we know for all integers j that:|1 + χ(j)|2 + |χ(j)− 1|2 = 22.For each integer j with |χ(j)− 1| > 1/ log log p, we thus have|1 + χ(j)| ≤√4− 1(log log p)2= 2− 14(log log p)2+O(1(log log p)2).To avoid the error terms, we can write|1 + χ(j)| ≤ 2− 15(log log p)2for all j with |χ(j)− 1| > 1/ log log p. (2.8)Let us estimate∏mj=1 |1 + χ(j)| now. For integers j such that |χ(j)− 1| > 1/ log log p, we use the inequalityin equation (2.8). For other integers j among {1, 2, . . . ,m} (there are m − N such integers), we use thetrivial bound |1 + χ(j)| ≤ 2. So,m∏j=1|1 + χ(j)| ≤ 2m−N ·(2− 15(log log p)2)N= 2m(1− 110(log log p)2)N. (2.9)Notice thatlog(1− 110(log log p)2)N= N log(1− 110(log log p)2)<−N10(log log p)2. (2.10)9In the last step we have used the fact that log(1 + x) < x for all real x > −1. If N ≥ 11 log p(log log p)2,then by equation (2.10),log(1− 110(log log p)2)N −11 log p(log log p)210(log log p)2=−1110log p = log(1p11/10).This, together with equation (2.9), implies thatm∏j=1|1 + χ(j)| ≤ 2m(1− 110(log log p)2)N 2mp11/10,which, is in contradiction with the assumption of lemma that the product is 2m/p. This means thatN log p(log log p)2.Now we have all the tools for proving Theorem 13.Proof of Theorem 13. We will use the same strategy as in the proof of Theorem 10 but the techniques usedhere are different. The main term is clearly 2m/(p− 1). The error term is also the same as that of Theorem10 (which is the right-most term in equation 2.4). Assume the error term is 2m/p2. This means that forsome non-principal Dirichlet character χ,m∏j=1|1 + χ(j)| 2mp. (2.11)Let m < y ≤ m2 be an integer. Note that<∑n≤yχ(n) = <∑n≤yn is m-friableχ(n) + <∑n≤yn is non-m-friableχ(n)≥ <∑n≤yn is m-friableχ(n)−∑n≤yn is non-m-friable1. (2.12)We will break the first sum in equation (2.12) into three sums by categorizing m-friable positive integers nup to y into three groups:1. n ≤ m3(1+ε)/2. Let’s call the set of numbers in this category A1, so that#A1 ≤ m3(1+ε)/2. (2.13)2. n is divisible by some k > mε such that |χ(k) − 1| > 1/ log log p. We proved in Lemma 17 that thenumber of such n is log p(log log p)2 (note that the condition of the lemma is satisfied since weassumed equation (2.11) in the beginning of the proof). If we denote by A2 the set of such integers,then#A2 ≤∑k>mε|χ(k)−1|>1/ log log pyk≤ ymε· log p(log log p)2. (2.14)10OACMχ(bj)NPκjκj/21loglogp1loglogp|χ(bj )−1|Figure 2.2: Angles κj in the proof of Theorem 13.3. m3(1+ε)/2 < n < m2 and n is not divisible by any k > mε such that |χ(k) − 1| > 1/ log log p. Weknow by Proposition 15 that n can be written as n = b1b2b3, where each bj (1 ≤ j ≤ 3) is either 1or satisfies mε < bj ≤ m. By our assumption, for each 1 ≤ j ≤ 3, we have |χ(bj) − 1| ≤ 1/ log log p.Therefore, according to Figure 2.2, χ(bj) lies on the arc M˙AN , and if we define the angle κj as shownin the diagram, we would have |χ(bj)− 1| = 2 sin(κj/2). Combining this with |χ(bj)− 1| ≤ 1/ log log pgives an upper bound on κj : κj 1/ log log p. This is because when x is in a neighbourhood of zero,arcsinx = x+O(x3). Note that for j = 1, 2, 3, we have χ(bj) = eiκj , thus<χ(n) = < (χ(b1)χ(b2)χ(b3)) = <(ei(κ1+κ2+κ3))= cos(κ1 + κ2 + κ3) cos(3log log p)= 1 +O(1(log log p)2). (2.15)One must notice that in equation (2.15), the inequality comes from the fact that 0 < x < y < pi/2implies cosx > cos y (this is a particular property of the cosine function and does not necessarily holdfor a general function).11The number of integers in the third category, which we call A3, is#A3 ≥ # {n ≤ y : n is m-friable} −#A1 −#A2= y −# {n ≤ y : n is non-m-friable} −#A1 −#A2. (2.16)Combining equations (2.15) and (2.16), we find<∑n∈A3χ(n) ≥(1 +O(1(log log p)2))(y −# {n ≤ y : n is non-m-friable} −#A1 −#A2) . (2.17)From equation (2.12),<∑n≤yχ(n) ≥ <∑n≤yn is m-friableχ(n)−∑n≤yn is not m-friable1= <∑n∈A1χ(n) + <∑n∈A2χ(n) + <∑n∈A3χ(n)−∑n≤yn is non-m-friable1.Using the trivial estimation for the first two sums, we find that above is≥ <∑n∈A3χ(n)−# {n ≤ y : n is non-m-friable} −#A1 −#A2. (2.18)To make equations shorter, let us defineA4 = {n ≤ y : n is non-m-friable} .From Lemma 16 we know that#A4 = y loglog ylogm+O(ylog y). (2.19)From equations (2.17) and (2.18),<∑n≤yχ(n) ≥ y − 2#A4 − 2#A1 − 2#A2 +O(y(log log p)2). (2.20)The numerator in the error term is in fact y −#A4 −#A1 −#A2 but since it is ≤ y, we simply wrote y inthe numerator. Finally, combining equations (2.13), (2.14), (2.19), and (2.20), we find<∑n≤yχ(n) ≥ y(1− 2 log log ylogm)+O(y(log log p)2+m3(1+ε)/2 +ymεlog p(log log p)2 +ylog y). (2.21)(2.13), Now, if we choose y = m√e−ε, the coefficient of y in the main term of equation (2.21) is a positiveconstant. Moreover, the terms inside the big-O are all y by our choice of m. However, we know fromBurgess inequatlity that the charachter sum in equation (2.21) is o(y), which is a contradiction. Hence, ourassumption (equation (2.11)) is false and the proof of Theorem 13 is complete.12Bibliography[1] Andrew R. Booker and Carl Pomerance, Squarefree smooth numbers and Euclidean prime generators, Proc. Amer. Math.Soc. 145 (2017), no. 12, 5035–5042. MR3717934[2] D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR0093504[3] , On character sums and L-series. II, Proc. London Math. Soc. (3) 13 (1963), 524–536. MR0148626[4] , The character sum estimate with r = 3, Journal of the London Mathematical Society s2-33 (1986), no. 2, 219–226.[5] Yuk-Kam Lau and Jie Wu, On the least quadratic non-residue, International Journal of Number Theory 4 (2008), no. 03,423–435.[6] Hugh L. Montgomery and Robert C. Vaughan, Multiplicative number theory. I. Classical theory, Cambridge Studies inAdvanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007. MR2378655[7] Marc Munsch and Igor E Shparlinski, On smooth square-free numbers in arithmetic progressions, arXiv preprintarXiv:1710.04705 (2017).[8] Paul Pollack, The average least quadratic nonresidue modulo m and other variations on a theme of Erdos, J. NumberTheory 132 (2012), no. 6, 1185–1202.[9] I. M. Vinogradov, Sur la distribution des re´sidus et des non-re´sidus des puissances, J. Phys.-Math. Soc. Perm 1 (1918),94–96.13Appendix AProof of Proposition 2In this appendix we establish the proof Proposition 2, the statement of which can be found on page 1. Priorto the proof, we prove a key lemma which contains the heart of the proof.Lemma 18. Let x and y be real numbers with y ≤ x < y2 such that χ(n) = 1 for all 1 ≤ n ≤ y. Then,∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ ≥ x(1− 2 log log xlog y)+O(xlog x). (A.1)Proof. Consider the sum∑n≤x χ(n) and write it as∑n≤xχ(n) =∑n≤xn is y-friableχ(n) +∑n≤xn is not y-friableχ(n). (A.2)In the first sum on the right-hand side of equation (A.2), each y-friable n ≤ x can be factored as n = ∏ki=1 pαiiwith each pi ≤ y and αi ≥ 1. Since χ is multiplicative and χ(pi) = 1 for 1 ≤ i ≤ k, we have χ(n) = 1.Thus, the first sum is ψ(x, y), the number of y-friable positive integers up to x. For the second sum inequation (A.2), note that a positive integer n ≤ x which is not y-friable has a prime divisor p > y andn/p < y. Hence, since χ(n) = χ(n/p)χ(p),∑n≤xn is not y-friableχ(n) =∑y<q≤xχ(q)⌊xq⌋,where q denotes a prime. Therefore,∑n≤xχ(n) = ψ(x, y) +∑y<q≤xχ(q)⌊xq⌋. (A.3)If we use the trivial bound |χ(n)| ≤ 1 for the sum on the righ-hand side of equation (A.3), we observe∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ ≥ ψ(x, y)−∑y<q≤x⌊xq⌋. (A.4)We know that [6, Theorem 2.7] ∑1≤q≤x1q= log log x+ b+O(1log x), (A.5)14where b is a constant. This immediately implies∑y<q≤x1q= loglog xlog y+O(1log x). (A.6)Thus,∑y<q≤x⌊xq⌋=∑y<q≤xxq+O ∑y<q≤x1 = x log log xlog y+O(xlog x). (A.7)We note that in the above equations, the error coming from the sum∑y<q≤x 1 will be in the same as theerror from estimating the sum x∑y<q≤x1q which we evaluated in equation (A.6). Furthermore,ψ(x, y) = bxc −∑y<p≤x∑n≤xp|n1 = x+O(1)−∑y<p≤x⌊xq⌋. (A.8)Combining equations (A.4), (A.7), and (A.8), we get the desired result.Proof of Proposition 2. Let x and y be real numbers satisfying the conditions of Lemma 18. Then,∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ ≥ x(1− 2 log log xlog y)+O(xlog x). (A.9)We know from the Burgess inequality [6, Theorem 9.27] that for any integer r > 2,∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ rx1− 1r p r+14r2 (log p) 12r , (A.10)Choose x = p1/4+ε, where ε < 1/7, and a positive constant c such that r = c/ε is an integer. Then,equation (A.10) becomes∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ cε(p1/4+ε)1− εcpc/ε+14c2/ε2 (log p)ε2c =cε· p 14+ε−ε2( 1c− 14c2 )(log p) ε2c . (A.11)For c > 1/4, the 1c − 14c2 is positive and strictly decreasing as a function of c. Equation (A.11) then implies∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ cε · p 14+ε−ε2( 1c− 14c2 )(log p) ε2c = o(p 14+ε), (A.12)which means ∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ = o(x) for x = p1/4+ε. (A.13)Suppose that y > x1/√e+ε. Taking the logarithm from both sides and dividing by log x, we findlog y/ log x > 1/√e+ ε. Taking the logarithm again,loglog ylog x> log(1√e+ ε)> −12+ ε,15where the last equation holds for our choice of ε by monotonousity. Since log 1/a = − log a, this shows that1− 2 log log xlog y> 1 + 2(−12+ ε)= 2ε,and so, by equation (A.9),∣∣∣∣∣∣∑n≤xχ(n)∣∣∣∣∣∣ ≥ 2εx+O(xlog x) x for y > x1/√e+ε, (A.14)which is in contradiction with equation (A.13). Hence, y ≤ x1/√e+ε and,nχ ≤ y ≤ x1/√e+ε =(p1/4+ε)1/√e+ε= p14√e+ε(14+1√e+ε)< p1/(4√e)+ε.The last inequality holds for ε < 1− 14− 1√e , which means it is also true for ε < 1/7. The proof is complete.16Appendix BProof of Propositions 14 and 15We establish Proposition 14 stated on page 8.Proof of Proposition 14. Let n = p1p2 · · · pr be the factorization of n into prime factors of descending order.That is, p1 ≥ p2 ≥ · · · ≥ pr. Let b1, b2, . . . , bk be positive integers all initially equal to 1. Find the firstbj not exceeding m/pi and multiply it by pi. At the end, we claim the bj form the desired factorization.Algorithm 1 summarizes this process.Algorithm 1 k-way Factorization1: for 1 ≤ i ≤ r do2: for 1 ≤ j ≤ k do3: if pibj ≤ m then4: bj ← pibj ;5: break;6: end if7: end for8: end forWe only need to prove that in the algorithm above, for each pi, there exists some bj such that pibj ≤ m.Assume, for the sake of contradiction, that when running Algorithm 1, there is some p` for which all thenumbers p`b1, p`b2, . . . , p`bk exceed m. Then,b1b2 · · · bk · p` = b1p` · b2p` · · · bkp` · p` · p−k` >mkpk−1`. (B.1)Therefore,m(k+1)/2 ≥ n ≥ b1b2 · · · bkp` > mkpk−1`.This implies m(k−1)/2 < pk−1` or simply√m < p`. Notice that since each bj is initially equal to 1 and eachpi ≤ m, this situation only happens when each bj has been selected in step 3 of the algorithm at least once.This means that each for each j ∈ {1, 2, . . . , k}, we have bj ≥ p` because bj is the product of elements of a17subset of {p1, p2, . . . , p`−1}, and pi ≥ p` for i = 1, . . . , `− 1. But then, since m < √p`,n ≥ b1b2 · · · bkp` ≥ pk+1` > m(k+1)/2,which is a contradiction.We now prove Proposition 15 appearing on page 8.Proof of Proposition 15. The result is obvious for k = 1, so let us assume k ≥ 2. If ε < 1/(k + 2), wehave n < m(k+1)/2 <(m1−ε)(k+2)/2, and by Proposition 14 (with k and m replaced by k + 1 and m1−ε,respectively), we may write n asn = b1b2 · · · bk+1 with bj ≤ m1−ε for 1 ≤ j ≤ k + 1.If there doesn’t exist bi and bj (1 ≤ i, j ≤ k + 1) such that bibj ≤ m, then n > (mk+1)1/2 = m(k+1)/2. Thiscan be verified easily: if k is odd, k+ 1 is even and we can divide bjs into two groups such that the productof any two elements chosen from different groups is > m; if k is even, we can leave out the greatest bj (whichis obviously >√m), and divide the k remaining bjs into two groups and then proceed like the previous case.In both cases, n > (mk+1)1/2 = m(k+1)/2, which is a contradiction. So, such bi, bj exist. Let’s suppose,without loss of generality, that bkbk+1 ≤ m. Define ck = bkbk+1 and cj = bj for 1 ≤ j ≤ k − 1 so thatn = c1c2 · · · ck with ck ≤ m and cj ≤ m1−ε for 1 ≤ j ≤ k − 1. (B.2)Let C be the number of cj (1 ≤ j ≤ k − 1) in equation (B.2) which are ≤ mε. If C = 0, there is nothingto prove and (B.2) gives us the factorization with desired conditions. So, let’s suppose that C is a positiveinteger. If C ≥ k/2,n ≤ m · (mε)C · (m1−ε)k−1−C = m1+εC+(1−ε)(k−1−C)= mk−ε(k−1)−C(1−2ε) ≤ mk−ε(k−1)− k2 (1−2ε)= mk/2+ε ≤ mk/2+εk/2 = m(1+ε)k/2,which is a contradiction (in the last step, we have used k ≥ 2). Therefore, C < k/2. Without loss ofgenerality, suppose that c1, c2, . . . , cC be all cj (1 ≤ j ≤ k − 1) such that cj ≤ mε. Define, for 1 ≤ j ≤ C,dj = cjcC+j , so that by the assumptions in equation (B.2), we havemε < dj ≤ mε ·m1−ε = m. (B.3)Notice that for dj to be well-defined, we need 2C ≤ k, which is implied from C < k/2 since C is an integer.But then, n = d1 · · · dC · c2C+1 · · · ck, which is the product of at most k numbers all of which are in thedesired range (by equations (B.2) and (B.3)).18
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Various problems on subproducts of residue classes...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Various problems on subproducts of residue classes modulo a prime Parvardi, Amir Hossein 2019
pdf
Page Metadata
Item Metadata
Title | Various problems on subproducts of residue classes modulo a prime |
Creator |
Parvardi, Amir Hossein |
Publisher | University of British Columbia |
Date Issued | 2019 |
Description | Let p be a prime number. Booker and Pomerance find an integer y with 1 < y ≤ p such that all non-zero residue classes modulo p can be written as a square-free product of positive integers up to y. Let us denote by y(p) the smallest such y. Booker and Pomerance show in their paper that except for p - 5 and 7, we have y(p) ≤ y and some better upper bounds were conjectured. Later, Munsch and Shparlinski proved those conjectures with even better localization. Their work was done as the same time as ours, but with fairly more complicated methods in the proof. We were seeking to find a solution for the problem using Pólya-Vinogradov inequality or at most its improvement, the Burgess bound on character sums. That being said, we removed the condition in the problem that the product has to be square-free. We proved that for m > p^[1/(4√e+o(1)], each residue class b of (ℤ/pℤ)^× can be written as a product of elements of the set {1, 2,..., m} modulo p. In fact, we showed that the number of such sub-products (congruent to b mod p) is asymptotic to 2^m/(p - 1). The proofs are based on an identity involving sums of Dirichlet characters modulo p as well as the Burgess inequality on partial character sums. Basically, we use proof by contradiction to state that if the error term (for number of sub-product) is large, then there should be many χ values close to 1, which would result in the character sum being large, thereby contradicting the Burgess inequality (which essentially says bounds the character sums). |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2019-08-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0380604 |
URI | http://hdl.handle.net/2429/71451 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2019-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2019_september_parvardi_amirhossein.pdf [ 374.77kB ]
- Metadata
- JSON: 24-1.0380604.json
- JSON-LD: 24-1.0380604-ld.json
- RDF/XML (Pretty): 24-1.0380604-rdf.xml
- RDF/JSON: 24-1.0380604-rdf.json
- Turtle: 24-1.0380604-turtle.txt
- N-Triples: 24-1.0380604-rdf-ntriples.txt
- Original Record: 24-1.0380604-source.json
- Full Text
- 24-1.0380604-fulltext.txt
- Citation
- 24-1.0380604.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-0380604/manifest