### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ANALYTIC NUMBER THEORY I MATH 782

GPA 3.51

### View Full Document

## 31

## 0

## Popular in Course

## Popular in Mathematics (M)

This 61 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 782 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/229544/math-782-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for ANALYTIC NUMBER THEORY I

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Math 782 Analytic Number Theory Instructor s N0tes Analytic Versus Elementary o Terminology Analytic Number Theory makes use of Complex Analysis and Elemen tary Number Theory does not but it isn7t so simple to distinguish 0 Writing an integer as a sum of two squares This is the rst of a few examples of how Complex Analysis can be used to answer a question seemingly unrelated to it if a and b are sums of 2 squares why must ab be also 0 Coverings A covering of the integers is a system of congruences x E a mod 7 such that every integer satisfies at least one of these congruences A perfect covering is one in which each integer satisfies exactly one of the congruences Suppose we have a nite perfect covering of the integers with each modulus m gt 1 Show that the largest modulus occurs twice Use that 1 T 2quot for lt 1 3 where 1 lt m1 3 m2 3 3 mr and 0 S a lt 7 Suppose that mpl 31 mr Then the right hand side and not the left hand side gets large in absolute value as 2 approaches exp27rimr The contradiction implies mpl mr 0 Preliminaries on exponentials The following are useful formulas n71 V 0 f k 0 E 6227rkn 7 10 n if k 0 16i2wk9d6i2weik9dg 0 0 27139 0 1 ifk0 o Putnam Problem A 6 1985 If 1916 a0 1115 1me is a polynomial with real coef cients a then set Ppac a8 a 1 Let at 32 710 2 Find with proof a polynomial 910 with real coef cients such that 90 1 and ii Pfx Pgx for all positive integers n There are perhaps better ways to do this problem but we use what we just learned to establish 1 Ppac 0 p e2quoti9p e ZWiQ d6 Note that at 3x 1ac 2 That 910 62 5x 1 33c 12x 1 provides a solution follows from These notes are from a course taught by Michael Filaseta in the Fall of 1996 P WOW 0 A Geometric Problem Let R be a rectangle and suppose R can be expressed as a union of rectangles R with edges parallel to R and common points only along these edges Suppose each R has at least one edge of integer length Then R itself must have an edge of integer length Let R be positioned so that it is in the first quadrant of the icy plane with an edge on each of the x and y axes Let B have bottom left hand corner uj 1 and let 0g and j be the horizontal and vertical dimensions of B respectively Observe that w39Y I 1 I ert 52mti0 ltgt YEZ w 27139 One uses that one of a and is an integer for each j and that 627riwy dac dy Ze2m39my dac dy R 31 R to obtain the desired result Homework 1 a If a and b are integers which can each be expressed in the form 2 5242 for some integers x and y explain why it is possible to express ab in this form as well b Determine whether the following is true ifa and b are integers and ab can be ezrpressed in the form 2 5242 with x and y integers then either a or b can be as well Either prove the result or give a counterexample 2 Putnam Problem A 5 1985 For m a positive integer define 27r m cos x cos2x cos3x cosmx die 0 a Use one of the preliminary results above yes you must to get credit for the problem to determine with proof for which integers m with l S m S 10 we have m 31 0 Hint Use that cosx eigc e im2 b Generalize part a In other words determine which positive integers m are such that m 31 0 The answer should be in the form m 31 0 if and only if m E u mod v where v is an integer and u is a list of integers Justify your answer Elementary Aspects o The Fundamental Theorem of Arithmetic the atoms of which the matter called integers is made are primes 0 There are infinitely many primes Give three proofs Euclid7s ii 22 l is divisible by a prime gt 2 and iii Hpltl 7 lpZ 1 7r26 an irrational number 0 Explain the notion of rearranging the terms of a series as well as the following lemmas about absolute convergence Lemma 1 If the terms of an absolutely converging series 221 an with an E C are rearranged then the value of the series remains unchanged On the other hand if the series 221 an with an E R converges but not absolutely then any real value can be obtained from an appropriate rearrangement of the series Use the example of the alternating harmonic series 22171WHn to illustrate the second half of the lemma and to give the first half more meaning For the first half let S 221 an and let 221 a be a rearrangement of it Let 6 gt 0 Fix no such that Z gtm lanl lt e Let N be suf ciently large so that the terms a1 am appear among al aN Then M2 475 Z lanllta 1 ngtno n The first part of the lemma follows Lemma 2 The product of two L t The product of 221 an and 221 b is 222 on where on akbnk The result follows since 2772 lcnl is an increasing function of N bounded above by cwwcyging series waveyes absolutely s Elba In fact 21 21 lakbll converges Lemma 2 is of interest but is not really needed in what follows Homework 1 Let f ZHZ gt gt C We say that the iterated series f ffltmngtfffltmmgt 711 m 711 m1 H 4 converges if for each positive integer n the series 21 fm n converges and if N 00 lt w exists The value of this limit is called the value of the iterated series We say that the double series 2 Wm H 1 nltoo 1 mltltxgt converges if there is an S such that for every 8 gt 0 there exists a K K6 such that if N and M are positive integers 2 K then N M Z fmn 75 lt5 711 m1 The number S is called the value of the double series Suppose the double series is ab solutely convergent in other words that Z lfmnl converges Prove that 1 nltltxgt 1 mltoo 2 rm ZZ mm and ZZ mm n1m1 1gnltoo m1 711 1 mltltxgt each of converges and that their three values are equal 0 Euler7s product identity namely 71 oo 1 1 lt17 E forsgtl p p5 711 5 Let Px denote the product above restricted to primes p S x Use Lemma 1 to show The identity follows 0 First proof that 2p 11 diverges Assume not Fix N such that Z 1 lt 12 Then pgtN HHV 1giltz f pgN pgtN 711 for any M gt 0 This is a contradiction the left hand side is nite o Logarithms and H11 7 17 Suppose that 0 S 1 lt 12 This condition implies S M8 kll gk M8 k 2 a 3 2a 3 an a H to a H 2 We use k log17 x 7 3 for lt 1 actually for 71 S x lt1 M8 a l l 1 Observe that N N N log H17 an Zlog17 an 2 72 17 711 711 711 The left hand side is decreasing so that if 221 1 converges then so does Hf 7 an The inequality log Hg11 7 an S 7 2771 1 implies that if H11 7 an converges then so does 221 17 1 1 Th t39 t 17 lt o e es ima e Hp m p710g11 Use 71 m Hlt17l 2 12 ldtlogac P n 1 5 pgm 711 0 Second proof that 2p 11 diverges Let Pltxgt 7 upglt17lt1pgtgt1 and so 7 2911 Then by ltgt logPacSE where 0 E 2Zi2 2 1 p w The result follows since Px 2 log at Note we have found a good lower bound for Zpgm 111 o A noteworthy example The product Hp1 7 119 and 221 are related if you expand the product and rearrange the terms you get the sum The value of the product is 0 and the value of the sum is 0 however it is considerably harder to show the latter It is equivalent to the Prime Number Theorem 0 The notation 7116 and a proof that limmmoo 0 Show that in fact 7116 lt 015 log logic for some constant C by using the sieve of Er atosthenes Discuss sieves in general Homework 1 a Modify the previous argument to show that almost all positive integers n have a prime factor 3 log n More precisely and moreover show that Mn 3 x n does not have a prime factor 3 log is bounded above by 015 log logic for some constant C Hint Most n S x which do not have a prime factor 3 logn also do not have a prime factor 3 log b Suppose wn is any function defined for n E Z which tends to infinity with n Prove that hm S x n has a prime factor 3 7 mace x 1 2 Give the analysis details to the second half of the proof of Lemma 1 The Functions Mac 1920 and 11ac and Chebyshev s Estimate logic 0 Define 1916 Zlogp and LJ Z logp Z logp P90 pm w p w o The limit connection with possibly infinite limits Theorem The following hold lim inf M liminf dim liminf W mace m oo mace and 19 l hm SUP E lim sup via hm sup 35 Og mace 3 mace More generally 239fo is such that limnnoo at 00 and any of the limits limnnoo 19xnacm limnnoo xnacm limnnoo 7rxnlogxnacn ezrz39sts then they all ezm39st and are equal Comment This theorem follows fairly quickly from the fact that limmnoo 0 and Abel summation to be discussed momentarily Proof of Theorem We show that for every 8 gt 0 and for at suf ciently large ac 2 06 7raclog 01 S y S lt 7rlogx 1 6 from which the theorem follows The second inequality is obvious The last inequality is a consequence of logic lt 16 pg logp logp 7 Zlogac 7raclogx p w For the first inequality suppose as we may that e lt 1 and take in 1 7 6 From vltmgtzlogp2 Z logywlogxgtltvrltxgt7vrltxwgtgt pgm mwltp m we deduce that q 1 1 it 2 w7ric ogx 7 w ogx x x gol w and the first inequality follows 0 Chebyshev7s Theorem in a weaker form Theorem Ifx is su iciently large then 069 3 lt7riclt278 3 g lo log it Lemma Let n be a positive integer and let be a prime Then the non negative integer k for which pk exactly divides n is n n P 1 F Proof of Theorem Let N Let hp denote the integer k such that pk exactly divides n N From the Lemma we deduce that tie 1amp1 The upper limit of summation could be replaced by log 2nlog Observe that 210 7 2M is 0 or 1 depending respectively on whether it is such that lt 12 or not It follows that hp 3 log 2nlogp Using 115 Zpgm log 300ng logp and that N mpg ka we deduce that logN S 112n Since N is the largest coe icient in ac 12 to see this use that WWI 111 we deduce that N lt 22 and ii 2n 1N gt 22 We are interested in ii for the moment which implies a lower bound on log N We deduce from the above that k l 3 12n 2 2n log 2 7 log2n 1 For x gt 2 and n ac2 we obtain 115 2 12n gt ac 7 2 log 2 7 logx 1 Dividing by it we deduce that liminfmmoo 2 log2 gt 069 The previous theorem now implies the lower bound in Chebyshev7s theorem The upper bound can be obtained by using H ltp 2 p S N and to deduce that 19211 7 1911 2 log 3 logN lt 211 log 2 nltp 2n Let x gt 1 and denote by m the non negative integer for which 27 lt x S 27quot Letting n l 2 4 2 above and summing we obtain 1910 3 mm in 1921 7 192j lt 2m2log2 lt 4 log 2ac 30 It follows that limsupm oo S 4log2 lt 278 The upper bound in Chebyshev7s theorem now follows from the previous theorem 0 Why did Chebyshev care Chebyshev was interested in proving Bertrand7s hypothesis that for every positive inte ger 11 there is a prime in the interval 11211 He did this by obtaining a stronger version of his theorem than we have stated here He showed that 092 36 lt lt111 77 logic logic for at suf ciently large It follows that for n suf ciently large 2n n 2 7 gt092 7111 gt0 M n Mn log2n logn which establishes Bertrand7s hypothesis when n is suf ciently large To complete the proof of Bertrand7s hypothesis one can determine what suf ciently large77 means here and then check the hypothesis directly for the n which are not suf ciently large Homework 1 a Using the ideas above and Chebyshev7s theorem as we have established it find a constant c as small as you can such that for every 8 gt 0 and for at suf ciently large depending on 6 there is a prime in the interval at c b Find a constant c as small as you can such that for every 8 gt 0 and for at suf ciently large depending on 6 there are at least 3 primes in the interval at c 2 a Show that for n suf ciently large the nth prime is 3 2n log n b Show that for n suf ciently large the nth prime is 2 nlog 3 Explain why the Chebyshev estimates established here imply that there are positive constants 01 and 02 such that 01i lt 7rac lt 02i for all x 2 2 logic logic More Background Material 0 Abel7s Summation Formula Theorem For a function a with domain Z set Aac Zak Suppose f is a kgm function with a continuous derivative on the interval uv where 0 lt u lt v Then 2 WWW Avfv Aufu UAfd Proof Clearly the left hand side is not changed by replacing it With and v With One checks that the same is true of the right hand side It therefore su ices to consider it and v to be integers Observe that an An 7 An 7 1 The theorem follows from 11 Z acorn Z AnAn1fn ultn v nu1 v71 MM 7 Altugtfltu 1gte Z W 1gte fltngtgtAltngt nu1 v71 n1 Avfv e Aufu e 2 AW it dx Homework 1 Let A be a set of positive integers and let Aac a E A a S Suppose that there is a constant c gt 0 such that 1 Z gt clog logic for all x su iciently large aEA a Prove that given any t gt 0 there is an x 2 t for Which gt can 2logx AW Note that I did not say that for all x 2 t the last inequality holds 10 2 Let n denote an arbitrary positive integer Recall that 3 foralleR m x2 at gt0 el a Using gt0 show that n gt ne b Let ac n l in and show that the first 2n 2 terms are each 3 n l nl Also show that the remaining terms sum to a number lt n l nl c Use b to show that n lt MQn 3 6n1 n 1n1 d Modify the above to show that n lt 2lt e 3 a Let n be a positive integer Using Abel summation prove that Zlogknlogn7 mdoc k1 1 in b Using a and the inequality 3 ac prove that n gt ne n1 e d Which upper bound on n is better when n is large the one given in 2d or the c Do a similar argument to show that n lt one given in 3c Explain o Derivatives of Sums and Sums of Derivatives Theorem Let 21 be a sequence of dt erenttoble functions such that 221 fnx converges for at gt 0 and C15 221 converges uniformly for at gt to Then Fac ezm39sts and Fac C15 for at gt 0 Proof Let 6 gt 0 Let FNx 2771 fnx and GNx 2771 There is an N0 N0e such that if M 2 N0 and at is any real number gt 0 then lGMac fowl lt Let N and M be 2 N0 Then low 7 oMu lt for all t gt to Fix at gt 0 Then there is a 6 6Mx 6 015 7 0 such that if lt 6 then FM h 7 FM 7 GMW lt Fix lt 6 Since FN 7 FM is differentiable on x0 00 we deduce from the Mean Value Theorem that there is a t between at and at h such that FN h 7 FM h 7 FNW 7 FM 7 hFzvt 7 FMU hGNt 7 GMt We deduce that 7 h h lt wlm This is true independent of the choice of N 2 N0 so by letting N tend to in nity we obtain Fac h 7 i FMx h 7 FMx h h Nlm Combining the first third and fifth of the above displayed inequalities we obtain that Fx h 7 h 7 ac lt6 It follows that Fac exists and Fac C15 as desired Further Elementary Results 0 Comment on this material Following classical lines we show shortly that if limmnoo 7rxlog exists then it is l The approach below is of some interest in itself but we note if the goal is simply to establish this information about limmnoo 7rxlog 3015 there is an easier way One can skip the next two sections and go to Merten7s formulas Then this result on limmnoo 7rxlog follows as a consequence of Merten7s formulas and an application of Abel summation see the third homework problem below 0 The function 3 and its derivative We use Euler7s identity discussed earlier and define the Riemann zeta function to be 00 71 5Znis lt1il forsgt1 721 p We will also use the von Mangoldt function n which is defined to be logp if n pk for some prime p and some positive integer k and to be 0 otherwise In particular LJ Z gm Observe that for s gt 1 logCs7Zlog 17 2f W By taking derivatives on both sides of this first equation and recalling the preliminary results above we deduce that Cs p slogp logp 0 M as p 1712 s 2 Z 12 By Abel summation we now deduce that 768 800 via doc for 5 gt1 1 51 0 1f limmmoo Mac logicac exists it is 1 Theorem liminf W S 1 3 lim sup 7rlt10g ma 9 700 at Lemma lims 71Cs 1 and hm8 7126 71 5H1 5H1 Proof of Lemma For the first limit use that 1 1 1 1 s doc lt lt 1 doc s 7 1 1 5 2 n5 1 5 5 7 1 711 For the second use an integration by parts to obtain 00 logn logic 1 7 7 E 7 7 C 8 7 711 5 x1 8 d E s 712 E where S 1 Proof of Theorem Let fs 7CsCs The lemma implies that limsn1s 7 1fs exists and is 1 1t su ices to show S 1 S limsup 90700 am we lim inf 700 Assume the first inequality is incorrect Then there is a K gt 1 and an 0 such that if x 2 0 then gt K Hence for 5 gt1 fss100 wdgt8 mo des wgdslmo wd epi x5 1 x5 5 7 1 Multiplying through by s 7 1 and letting s 7 1 we obtain a contradiction 1n the same manner one handles the possibility that lt L lt 1 for x 2 x6 0 Merten7s Formulas The following results are due to Merten A 1 w t Z logxO1 Z 0gp 1ogx01 dtaogmon ngm n pgm p 1 t ZlloglogAOllogx and H Pgmp pgm 1 B 1 7 N p logic where A and B are constants Discuss what these results mean the notation Observe that for any positive integer m For m 2 l we easily deduce that mlogm 2 logmi 2 mlogm 7 m Also 10 m 10s pl logltmxgt 7 Z 1ogp 2 mm 7 Z W M pgm j0 ngm nltm where we have used that 11m Z ltm An Dividing through by m we obtain 7 Z w logm 01 ngm The first of Merten7s formulas now follows consider replacing x with The second formula follows from the first by observing 0 logp 7 log 2p pi 723199971 13972 is a convergent series The third formula follows from the first by using Abel summation take an An and ft 115 and using that 1Z1x 015 by Chebyshev7s estimates The fourth formula follows from the second by Abel summation take 11 logpp an 0 otherwise and ft llog t The fifth formula is left as a homework problem Homework 1 We showed that if 713111 is a sequence tending to infinity and limnmoo or limnmoo 7rz log gunac exists then they both do and are equal Show that this follows from Abel summation you may also use limmmoo 0 but this is not necessary P logl 7 x as discussed earlier You will want to take advantage of another of Merten7s formulas l B 2 Prove the formula H l 7 7 1 above Hints Use the Maclaurin series for ogac p w 14 3 Use the fourth formula of Merten above and Abel summation to give an alternative proof of the result at logic lim inf 7r logic mace at 7r 3 l S limsup mace Complex Preliminaries o Analytic functions on a region Q non empty open and connected The derivative of fz exists on 9 All the derivatives of fz exist on Q The function at iy Mac y ivy is such that u and v satisfy the Cauchy Riemann equations in 9 u v an u 7 1 810 8y By 810 The function fz may be represented as a power series at each point in Q o The ldentity Theorem If S Q Q has an accumulation point in Q and f and g are analytic functions for which fz 92 for all z E S then f E g on Q o Weierstrass7 Theorem a version of it Let 2c 5 denote an analytic function in Q for each x 2 1 Suppose as x approaches infinity fms converges uniformly to fs on every compact subset of 9 Then fs is analytic in Q and f s converges uniformly to fs on every compact subset of Q Homework 1 Fix 039 E R Let C be a compact set in the region Res gt 039 Prove that there is a 0 gt 039 such that O is in the region Res gt 0 The Riemann Zeta Function in the Complex Plane 0 The function 3 in the right half plane The definition 3 221 1115 is well defined for s 0 it 0 and 15 real with 039 gt 1 and defines an analytic function in this region here we interpret n5 as 651 where log refers to the principal branch of the logarithm lt converges uniformly for 039 2 00 gt 1 By Abel summation with an l and ft 1155 we deduce that 1 1 Z l 7s u1du forUgtl 7111quot 571 1 715 m it By considering Weierstrass7 Theorem with fms 5 31 du we deduce that the right 1 u hand side is analytic for 039 gt 0 except for a pole with residue 1 at s 1 By the Identity Theorem the right hand side is the only possible continuation of 5 to the right half plane as a meromorphic function The Riemann zeta function 5 refers to the right hand side above when 039 gt 0 71 l Euler7s identity 5 H l 7 holds for o gt 1 Observe that for o gt 1 p5 p measnoesaa p w p w It follows that the absolute value of the product in Euler7s identity is bounded below by lo In particular 5 is non zero for o gt 1 Homework 1 Look at our argument for Euler7s identity given for real 5 gt 1 Explain how to modify it to show the identity holds for o gt 1 as stated above 0 The Riemann Hypothesis with 5 defined as above 5 0 gt o 12 discuss some partial results that are known and implications such as on the gap problem for primes o The line 0 1 Theorem Ift7 0 then lit 0 Lemma 1 log Relog Lemma 2 3 4cos6 cos26 21 cos 62 2 0 Proof of Theorem From Lemma 1 for o gt 1 0 1 00 an 00 an 1 R l R R t1 og was elt ogcltsgtgt 2p A W 21 7121 no coslt 0g where an lm if n pm for some prime p and an 0 otherwise Hence log l3o4o ito i2t Z a 3 4 cost log n cos2t log 7 711 The definition of an and Lemma 2 imply that the right hand side is 2 0 It follows that for o gt 1 1 will 4 W 7 1CltUgtl3 lClt0 mm lC3UgtC4ltU mm mm 2 71 Assume lit 0 witht 31 0 We let I approach 1 from the right above We have already shown 0 7 lo approaches 1 also clear from the analytic continuation formulation of 5 Observe that o ito 7 l approaches 1 it Thus taking a limit of the left hand side above we obtain ll itl4ll i2t On the right hand side the limit approaches infinity Thus we obtain a contradiction establishing the theorem 16 Proof of the Prime Number Theorem 0 The Prime Number Theorem was first established independently by Hadamard and de la Vall e Poussin in 1896 It is the following 1 Theorem lim m Homework 1 Let p denote the nth prime Using the Prime Number Theorem prove that p71 hm new n logn 2 Let 8 gt 0 Using the Prime Number Theorem prove that there is an 0 x06 such that 60 s c lt H p lt calmc for all it 2 0 p w 3 Let p denote the jth prime and suppose that a1 a2 am are positive integers lf pr is the largest prime factor of a1a2 am then we can factor each ak as ak 1113 Where each ejk 2 0 j1 The least common multiple of the integers a1a2am denoted lcma1a2 am satisfies 7 lcma1a2am 1 1ij where f maxejk 1 k S j1 Let c denote a constant Using the Prime Number Theorem prove that li ngtltxgt mlcml2ni 0 ifcgtl e0 7 oo ifcltl o For the proof of the Prime Number Theorem we will make use of previous material together with the following result the Wiener lkehara Theorem Theorem Let Aac be a non negative non decreasing function of ac de ned for it E 0 0oo Suppose that the integral Axe die converges for o gt 1 to a function fs 0 which is analytic for o 2 l ezrcept for a simple pole at s l with residue 1 Then lim e mAQc l ac Comment To prove the lemma one can consider the double integral of ftac This integral is finite and this justifies such an interchange Lemma 2 Let fs be analytic on o Res 2 1 hence in an open region containing such s Let a and b be real numbers with a lt b Then as w 7 0 fl 77 wiy converges uniformly to fl 77 iy for y E a b Proof Write fx 77 iy uxy 77 ivicy Since f is anaytic on o 2 1 each of u and v has continuous partial derivatives for gay with it 2 1 Let M be a bound on use xy and vmxy in the set 1 2 gtlt a b Then with z liy and 0 S w 3 l the Mean Value Theorem gives lflt2 w 7 flt2gtl lult1 w 7 ult1ygt lvlt1 w 7 my 2wM The lemma follows Lemma 3 Let a and b be real numbers with a lt b Let htw ab gtlt 000 7 C be a continuous function such that htw converges to ht0 uniformly fort 6 ab Then b b 1113 htwdt ht0dt Proof Fix 6 gt 0 Choose 6 gt 0 such that if 0 S w lt 6 and t E 1 b then lhtw 7 ht 0 lt eb 7 1 Then abhtwdt7 abht0dt K View 7 we dt lt e The result follows Lemma 4 Let f R 7 R be a non negative function for which fac die ezrists Then 0 lim 000 fice mc die Ooo fac doc w7gt0 00 15 Proof Let 6 gt 0 Fix t gt 0 such that fac die lt 54 Let I fac doc Fix 6 gt 0 t 0 lt e S 1 Then e htht39f0lt 6th 17 suc a1 iwlt en 2I1 Ooo fxe wm die 7 Ooo fac die The result follows 15 oo 321 10 fxdic2t fxdaclte Lemma 5 Let f R 7 R be a non negative function for which lim fice mc die w7gt0 0 ezrists Then lim fice mc dic fxdac w7gt0 0 0 Homework 1 Prove Lemma 5 Do not assume fac die exists 0 We will use the following weak version of the Riemann Lebesgue Lemma Lemma 6 Let a and b be real numbers with a lt b Let f ab 7 C be such that i f ezrists everywhere in 1 b and b ii ft dt is nite b Then lim fteiytdt0 9700 a Comment Observe that ii holds if f is continuous on 1 b This will be the case for our use of the lemma Proof Integration by parts gives 39 b ezyt b b I fteiytdtft fteiytdt gtin Thus b b The result follows We will also make use of 00 2 Lemma 7 g dac 7r 00 at There is no real need to discuss the proof as the value of the integral will not come into play only its existence will which is clear 0 A Proof of the Wiener lkehara Theorem Set B Axe m It follows that g 7 L1 MBx 7 1e 1 c die for 039 gt1 0 8 Define 93 to be the left hand side By the conditions on f we deduce that g is analytic for 039 21 Fix 8 gt 0 and let ht 91 5 it Fix A gt 0 Then ht1i gyw dt 7 Z lt 7 g5iytOOOB 7 le 5itm dab dt We justify that for 039 gt 1 we can interchange the order of integration by using Lemma 1 We consider 5 l 52 and x gt 0 Observe that fs Aue usdu 2 e usdu M 0 90 Thus B 141306 c S sfseE2m It follows that where O sfs 1 Lemma 1 now justifies the interchange of the order of integration A direct calculation gives l 2gt 17 6iy7mt Sin2y 7 2 2A 2 My 902 We deduce that 2A 00 2 fan OF 72A hltt1i geiyt dt 0 30071gt67m81nkf29 2gtgtdm 20 Since 95 is analytic for 039 2 l we deduce from Lemma 2 that ht see its de nition converges uniformly to 91 115 for t E 72A2A as 8 approaches 0 from the right It follows from Lemma 3 that lim 2A 111 1 eiytd12A g111 1 eiytd1 570 72A 2A 72A 2A By Lemma 4 oo 2 7 00 2 7 Ag 39 2 lim e mw dag w dac Sm U d so 0 y 7 m2 0 My 7 352 7 02 Since B is non negative Lemma 5 and now give 0 7 sin2y 7 7 0 sin2y 7 713517 0 Bace deO dac M 1 sin2 1 LBQ X We let 8 7 0 in Next we let y tend to infinity Observe that 2A 11 1 W iytdt7O 11 1t mam 11 1 t 211111 ng 1 2A6 12A9 1 2A6 09 1 2A6 and we can apply Lemma 6 to each of the integrals on the right From this and Lemma 7 we obtain M v sinZU gt11 yleO70ltBy7x v2 dv7r Explain why intuitively implies we are through Let a be such that 0 lt a lt Ay Since AW Bace c is non decreasing we get for 7a S v S a that ey7ltaAgtBy S 59UABy S eyltaAgtBy r 72 72alt 73 lt 2 2aA Blty Ae 732 AB y e We now deduce from and the fact that B is non negative that 00 so that a 2 a 39 2 C ZQA lim sup 39 g d hm SUPB y 2 372 1A sm2 U dv 9700 7a U yam A 7a U a 2 S limsup B y 7 3 sm2 0 d1 3 7139 9700 7a A U 21 The above holds for any positive a and A Letting a A and letting A tend to in nity gives that limsupm ooBQc S 1 To nish the proof we show liminfmmoo B 2 1 Observe that lim supm ooBQc S 1 implies B S c for some constant c and all x 2 0 We take a xA again and use that W U sinZU l39 39f B 7 d W gale70 9 Ow 7 sinZU sin20 a v sinZU Sc dv dv liminf B 247 dv x v2 a 02 yeoo 7a A 02 7112 00 2 a 392 SlIl U SlIl U SlIl U lt d d 2 139 39fB d 70 42 v2 v 1222 W 2 v The theorem follows now by letting A tend to infinity Intermission 0 Question Are there infinitely many primes whose decimal representation contains the digit 9 Answer Yes Theorem Given any block of digits d1d2 1 base b 2 2 there exist in nitely many primes whose base b representation contains the block of digits We will specialize our arguments to the original question concerning the digit 9 We give three proofs that infinitely many such primes exist One proof will use the main result of what is to come one will use the main result of where we have been and the other won7t use much Each of the arguments easily generalizes to give the above theorem Before continuing we note that it is unknown whether or not there exist infinitely many primes whose decimal representation does not contain the digit 9 Actually it is known but no proof exists 0 What is to come The next main goal for the course is to establish Dirichlet7s theorem that if a and b are relatively prime integers with a gt 0 then there are infinitely many primes of the form an i b Observe that with a 10 and b 9 we can deduce that there are infinitely many primes whose decimal representation contains in fact ends with 9 Note that the more general theorem stated above can be done the same way by considering b d1d2 dn gtlt 10 1 0 Where we have been We could instead use the Prime Number Theorem as follows Lemma Let E gt 0 Then there is an 0 x06 such that ifac 2 0 then the interval at x 615 contains a prime Before proving the lemma observe that it implies what we want by taking 8 19 and x 9 gtlt 10k 2 0 In fact a similar argument shows there are infinitely many primes whose decimal representation begins with any given block of digits Proof We may suppose that 8 S l and do so Mom the Prime Number Theorem there is an 3 68 such that if x 2 3 then 1 8 at lt lt 15 at 10 logx W16 10 logic 22 Thus at 2 3 implies gt15 E716 x gt sac i xlog2 782 7T 35 ac 7T 35 7 10 log2x 10 logic 7 log2x logaclog2x 5 logic where the last term on the right is a bound on the contribution from the parts involving 510 We deduce that if x is suf ciently large the interval at x 615 contains a prime 0 An elementary argument Let 111112 be the positive integers in increasing order whose decimal representations do not contain the digit 9 Then for N 2 l 71klt10N m j1 10j 1gnklt10j 31 It follows that the partial sums of 221 lnk form a bounded increasing sequence and hence the series converges Since the sum of the reciprocals of the primes diverges it follows that there are infinitely many primes not among the numbers nk Hence there exist infinitely many primes whose decimal representation contains the digit 9 Homework 1 An open problem of Erdo39s is to show that if 111 is an arbitrary infinite sequence of integers such that l S 11 lt 12 lt 13 lt and ii l1j diverges then there exist arbitrarily long arithmetic progressions among the 1 v More precisely given a positive integer N one can find N distinct 1 in an arithmetic progression If true this would imply there are arbitrarily long arithmetic progressions among the primes something which as yet is unknown One approach to resolving the problem might be to consider a sequence 1 21 satisfying and having no N term arithmetic progression and to show that 2111j must then converge If one can show this is true regardless of the value of N 2 1 then the problem of Erdo39s would be resolved The case N l and N 2 are not interesting Deal with the following special case with N 3 Begin with 11 l and 12 2 Let 13 be as small as possible so that no 3 term arithmetic progression occurs among the 1 then selected We get 13 4 Choose 14 now as small as possible avoiding again 3 term arithmetic progressions Then 14 5 Continue in this way The next few 1j7s are 10 ll 13 and 14 Prove that l1j converges Hint Think base 3 Algebraic Preliminaries o A group is a set G of objects together with a binary operation satisfying i If 1 and b are in G then so is 1 b ii If 1 b and c are in G then 1 b c 1 b 0 iii There is an element 6 of G such that 1 e e 1 1 for every 1 E G iv For every 1 E G there is a b E G such that 1 b b 1 6 An abelian group is a group G such that 1 b b 1 for all 1 and b in G A group is finite if G is finite We will simply use 1b to denote 1 b and refer to the binary operation as multiplication unless noted otherwise 23 0 Examples The set of integers under addtion the set of non zero rational numbers under multiplication and the reduced residue system modulo 11 under multiplication are all abelian groups Another example is given by Cj 0 S j S n 71 where C 627W and the binary operation is multiplication Yet another example is given by 151 152 3 under composition where the b are defined multiplicatively on the elements of CC2 C4 where C 62Wi7 with 1C C 2C C2 and 3C C4 Finally consider the multiplicative mappings from the reduced residue system modulo 7 to Cj 0 S j S 5 where C 62mm show that these mappings form a finite abelian group under multiplication o A simple theorem on finite groups We will use the fact that if a is an element of a finite abelian group G then alGl e where e is the identity element in G Give a proof Note that the same is true for any finite group 0 A theorem on finite abelian groups Theorem Let H be a subgroup ofa nite abelian group G Let a E G and let k be the minimal positive integer for which a E H Let Hajbb H0jltk Then H is a subgroup ofG and lHl Proof Let 1 and ajb be elements of H with 0 S ij lt k and b and b in H lf 0 S ij lt k then bb E H implies aiajbb aijbb E H lf ij 2 k then 0 S ij7k lt k In this case akbb E H implies aiajbb aij kakbb E H Thus H is closed under multiplication One also checks that the inverse of ail is ak im kb l E H note that if i 0 then 1 E H Q H The other group properties of H are easily determined to hold and thus H is a subgroup of G To prove lHl lel it suf ces to show that if 1 171 then i j Assume otherwise we suppose as we may that i gt j Then ai j Mr1 E H contradicts the minimality condition on k The contradiction completes the proof Characters 0 The definition A character X of a finite abelian group G is a multiplicative complex valued function not identically zero defined on the group Thus if a and b are elements of the group then Xab XaXb 0 Properties of characters i If e is the identity element of G and X any character then Xe 1 This follows from two observations First Xe 31 0 otherwise Xa XaXe 0 for all a E G contradicting the requirement in the definition that X is not identically zero Next Xe X6Xe and we can deduce from our first observation that Xe 1 ii If lGl n then Xa is an nth root of unity for every 1 E G This follows from X01 XWG X 1 iii For every 1 E G Xa 31 0 See iv lf lGl n then there are exactly 11 distinct characters de ned on G Let H1 c where c is the identity element of G Thus H1 is a subgroup of G If G 31 H1 we apply the theorem of the previous section on groups to construct a new subgroup H2 of G Note that H2 will be a cyclic subgroup of G generated by an element a different from c in G How a 31 6 is chosen doesn7t matter If G 31 H2 then we again apply the theorem to obtain a new subgroup H3 of G We continue defining for i 2 l as long as G 31 Hi the subgroup Hi1 agb b E Hi0 S j lt where ai Z H1 and ki is the minimal positive integer for which a 6 Hi We show by induction on i that the number of distinct characters on HZ is The result will then follow We deduce from that there is precisely one character defined on H1 6 Suppose there are precisely different characters defined on HZ for some i 2 1 If G Hi then we are done as there are no more subgroups to consider Otherwise we wish to show that there are precisely lHZHl different characters defined on Hi Observe that any character on Hi is necessarily a character when restricted to HZ make use of i or iii We finish the argument by showing that each character X of HZ extends to exactly ki different characters on Hi Fix X Observe first that the definition of Hi and the multiplicativity of X imply that X will be defined on Hi once the value of XaZ is determined On the other hand the value of XaZki Xa i is known since a E Call this number 7 Then XaZ must be one of the ki distinct kith roots of y This shows that there are at most ki different extensions of X to Hi On the other hand defining XaZ to be such a kith root of y is easily shown to produce an extension of X to Hi This completes the proof v If a E G and a 31 6 then there is a character X defined on G such that Xa 31 1 In our construction of the HZ above we take H2 ltagt The order of a given in the argument there is M The construction gives a character X of H2 such that Xa is an arbitrary klth root of unity We choose a klth root of unity other than 1 This character extends to a character of G with the desired property vi The characters of G form a finite abelian group under multiplication lf X1 and X2 are two characters defined on G then X X1X2 means Xa X1aX2a for every a in G One checks directly that X is a multiplicative complex valued function which is not identically zero hence the product of two characters is itself a character Associativity and commutitivity follow from the same properties for multiplication in the set of complex numbers The identity element called the principal character is defined by Xa l for every a E G and this is easily checked One also checks that if X is a character then so is X defined by Xa Xa 1 and that X is the inverse of X From iv we now deduce that the characters form a finite abelian group We note that the group G and the group of characters defined on G are isomorphic we do not need this fact and so do not bother with the details of an explanation vii The following holds 0 if X is not principal 2 W1 G 39f 39 39 39 1 aEG l l 1 X ls principa Observe that in the case that X is principal the result is trivial If X is not the principal 25 character then there is a b E G such that xb 31 1 The proof follows by multiplying the sum say S by xb and using that ab a E G G Thus xbS S so that S 0 viii The following holds 0 if a 31 e beda lGl ifa e If a e the result follows from iv If a 31 e then by v there is a character X such that xa 31 1 If the sum above is S we obtain xaS S and the result follows along the same lines as vii o Dirichlet characters A Dirichlet character X is a character on the reduced residue system modulo 11 extended to the complete system modulo n by defining xa 0 whenever a and n are not relatively prime 0 Examples of Dirichlet characters Discuss the two Dirichlet characters modulo 6 the four Dirichlet characters modulo 8 and the twelve Dirichlet characters modulo 36 by making Dirichlet character tables in the first two cases and explaining how to go about doing the same in the latter by defining x5 to be a sixth root of unity and x35 to be i1 Homework 1 a Make a Dirichlet character table of the eight characters modulo 15 b Make a Dirichlet character table of the eight characters modulo 20 Dirichlet Series 0 The definition A Dirichlet series is a series of the form 221 anns where an and 5 denote complex numbers we interpret n5 as eSIOg where log refers to the principal branch of the logarithm 0 Preliminary results Theorem 1 Fix 6 E 0 7r2 If the series 221 anns converges for s so 6 C then it converges uniformly in s l args 7 sol S 6 Proof By considering b7 ann so so that 221 anns 221 bnns so we see that it suf ces to prove the theorem in the case that so 0 Thus 221 1 converges and its partial sums form a Cauchy sequence Fix 6 gt 0 Consider a positive integer M such that lZMlt ltmanl ltefor allac 2M We definie 117 ier gtM and 1 0 ier M Let N gt M We apply Abel summation with Ax Z ltm 1 and at it s to obtain N A ANfN 7 AMfM s die M an s Mltn N n The definition of Aac implies that lt e for all x 2 M We write 5 039 it and obtain N N N A A l l l dx 2535 dx lti M its M M at 039 M 7 N 7 s1 d 26 Note that 1lt lsl lt l o 7 cos l39 From gt0 we deduce easily that an Allle Allle 45 lt lt n5 oM 7 o cos l Mltn N Therefore the partial sums of 221 anns form a Cauchy sequence and hence the series converges The above inequality in fact implies uniform convergence Theorem 2 If 221 anns converges for s s0 00 i150 then it converges in the half plane s o it with o gt 00 Furthermore in this case the convergence is uniform on every compact subset of the half plane with o gt 00 The proof of Theorem 2 is clear given Theorem 1 The smallest value of 00 is called the abscissa of convergence for the Dirichlet series Observe that if 00 is the abscissa of convergence for a Dirichlet series 221 anns and if 00 is finite then the series converges if U Res gt 00 and diverges if o lt 00 What happens on the line 0 00 is unclear It should be noted that 00 could be 00 or foo with for example an n and an lnl respectively Theorem 3 Let 00 be the abscissa of convergence for the Dirichlet series 221 anns Then the series represents an analytic function in the half plane o gt 00 and its derivatives can be computed by termwise differentiation In the complex preliminaries section of the notes we introduced a theorem of Weierstrass By considering f3c s Z ltm an n5 and applying Theorem 2 the above result follows Theorem 4 Let 0 E R Suppose 221 anns and 221 bnns both converge for o gt o and that they are equal on some non empty open set in this half plane Then an b7 for all n 2 1 Proof Let 0 an 7 bn The conditions in the theorem Theorem 3 and the Identity Theorem imply that 221 cnns is identically 0 in the half plane o gt 0 We wish to prove that on 0 for all n 2 1 Assume otherwise and let M be minimal with CM 31 0 Fix for the moment 0 gt 0 Observe that 221 cnnquot converges so that lcnlnquot lt l for n suf ciently large say 11 2 N 2 M 2 Now for u gt 0 lcnln 7u lt 111 for n 2 N We obtain from 22 cnn 7u 0 that 00 N71 00 chl lcnl l l O MUM Z naug M1Uu Z W Z g M w nM1 nM1 nN for some constant C Multiplying through by Mau and letting it tend to infinity gives a contradiction and establishes the theorem Part I of the Proof of Dirichlet s Theorem X 715 o The Dirichlet series LsX 2 where X denotes a character modulo a positive integer m converges for 039 gt X is not the principal character To see this observe that property vii of characters easily implies l Z ltm is bounded as x goes to infinity An application of Abel summation now shows that Ls X converges for 039 gt 0 It is easy to see that LsX diverges for 039 lt 0 It follows that 0 is the abscissa of convergence In particular Ls X is analytic in the region 039 gt 0 o The connection between Ls X and 5 when X is the principal character First for an arbitrary Dirichlet character X a proof similar to that done before gives L8X1 17 Xlgfil foragt 1 For the principal character X0 modulo m we obtain Llt8agtltogtHlt1 gtrpIltI tlHlt1ltltsgt plm plm It follows that LsX0 is analytic for 039 gt 0 except for a simple pole at s l with residue npmlt17lt1pgtgt o For every Dirichlet character X Ls X 31 0 for 039 gt 1 A proof similar to that given for the analogous result for 3 can be used here 0 The logarithm of Ls X For an arbitrary Dirichlet character X modulo m we define k wLsX Z for 039 gt1 p k 1 p HMS The right hand side is what we would obtain from using the Maclaurin series for logl 7 x with the product formulation of Ls X if we incorrectly assume log2122 log 21 log 22 for complex numbers 21 and 22 Locally w behaves like the logarithm of Ls X but globally it may not correspond to any branch of the logarithm In particular since for the principal branch of the logarithm logl 7 z 72 7 222 7 233 7 for lt 1 it follows that exp7z722272337 l 72 for lt 1 so that 00 71 XltPk W expltZZ ksHl7 s forUgtl pg 171 W pgm p Thus exp wLsX LsX for 039 gt 1 28 Observe that w is de ned as a Dirichlet series which is analytic for 039 gt 1 In particular it is differentiable and we have by taking derivatives above that d Lsm L f 1 dslt m Lm or a gt Hence for fixed 5 039 gt 1 and c gt 039 we obtain C U u X ltgt wltLltsxgtgt e du logLltcxgt Homework 1 a Let X be a character on a group G Let X be the function de ned by Xg w the complex conjugate of Xg Prove that X is a character on the group G b Let Ls X be the Dirichlet L series corresponding to a Dirichlet character X Inodulo a positive integer m Let X0 denote the principal character Inodulo m Recall that Ls X is analytic for 039 gt 0 if X 31 X0 and that LsX0 is analytic for 039 gt 0 except for a simple pole at s 1 Suppose HMLX 7g 0 where the product is over all Dirichlet characters X Inodulo m Also suppose X is a character for which Xa 31 i1 for some integer 1 Explain why LlX 31 0 Part II of the Proof of Dirichlet s Theorem 0 We will show in the next section that LlX 31 0 if X is a non principal Dirichlet character We use this fact for the remainder of this section to show how Dirichlet7s theorem on prirnes in an arithmetic progression follows Observe that from above for X a non principal character we deduce from the fact that Ls X and Ls X are analytic for 039 gt 0 and LlX 31 0 that wLsX rernains bounded as s a 1 0 The proof of Dirichlet7s Theorem assurning Ll X 31 0 if X is a non principal Dirich let character Let a and m be integers with m gt 1 the case m l is trivial and gcdam 1 We prove there are infinitely many prirnes p E a mod m by showing that the sum of the reciprocals of such prirnes diverges Let b E Z with ab E 1 mod Observe that baa E 1 mod m if and only if x E a mod Consider the Dirichlet characters Inodulo m and let 7 2 1 denote the number of them By property viii of characters it follows that Zxltpb 7 ipra Inod m 0 otherwise We consider 5 039 gt 1 and define E by p5 w wltLltsxgtgt Z W E so that mm A simple estimate gives that S 1 From we obtain for some E bounded in absolute value by 7 that Er Z isEC pEa mod m ZxltbgtwltLltsxgtgt 2w 2 E Z W P We now let 3 a 1 and observe that each term in the sum on the left remains bounded except for the summand involving the principal character and this summand increases in absolute value to infinity This implies that the right hand side must increase in absolute value to infinity so that the sum of the reciprocals of the primes p E a mod m diverges Part III of the Proof of Dirichlet s Theorem 0 We begin With some preliminaries Lemma 1 Suppose f is analytic in a region 9 containing a point 20 Suppose the disk D z l2 7 20 lt 7 Where 7 gt 0 is in 9 Then the series 2203 converges in D to f The lemma asserts that f is equal to its Taylor series representation about 20 in any open disk centered at 20 that is contained in Q We omit the proof of this lemma but use it to establish the following result of Landau discuss the connection With 3 as an example to help clarify the theorem Theorem 1 Let fs be analytic for 039 Res gt 0 Suppose that there is a Dirichlet series 2 anns With abscissa of convergence 00 that equals fs for 039 gt max000 If 711 an 2 0 for every n 2 1 then 00 S 0 Proof Assume 00 gt 0 Since fs is analytic for 039 gt 0 fs can be represented as a Taylor series about 00 1 that by Lemma 1 converges in a disk of radius gt 1 0 0 centered at 00 1 For k a positive integer the Dirichlet series representation of fs gives US feta 1 1ao 11 711 30 Thus inside this disk 00 k 039 1 fs Z8001k 110 39 7 0 8001k 0 an7lognk Tkzw kl 31 711 Fix 5 u 6 002 00 in the disk Then the double sum converges and since the terms are non negative it converges absolutely We may therefore rearrange the order of the summations to obtain that 00 an 00 10 771110ng 00 171 711 071 00 a fuZ 0022 6lt1o gtlt1ggt 711 711 kl n1 70 nu k0 711 711 This is impossible as u is to the left of the abscissa of convergence for 221 anns The theorem follows 0 Lemma 2 If a Dirichlet series E anns converges for s so then the series converges 711 absolutely for Res gt Reso 1 Proof Let 00 Reso and consider 5 01t with 039 gt 00 1 Convergence at so implies that limnmoo law71001 0 Thus law71001 lt 1 for n suf ciently large Since 039 gt 00 1 it follows by comparison with 201171 7 00 that 221 anns 221 annoons ao converges absolutely The product of two Dirichlet series 221 anns and 221 bnns is defined to be the Dirichlet series 221 cnns where an Zkl 1ka here k and X represent positive integers 1f the Dirichlet series involving an and 1 both converge for s 039 it with 039 gt 00 then they converge absolutely for 039 gt 00 1 by Lemma 2 It follows that the Dirichlet series representing their product will converge absolutely for 039 gt 00 1 The product will therefore converge in this same region we view the product then as converging in a possibly smaller region then the initial two Dirichlet series Observe also that if we consider 221 ann5k for k any positive integer and expanding this product in the obvious way it is easy to see that independent of k the resulting series converges in fact absolutely for 039 gt 00 1 Note that the values of a series representing the product of two Dirichlet series is in fact equal to the product of the values of the two Dirichlet series if the series involved converge absolutely Homework 1 Prove that 82 00 711 101 s for 039 gt 1 where dn denotes the number of positive 71 integer divisors of n 31 as cltsgt 1 Zdw Ad log n Hint Write down the series representation for 9 2 Recall that we showed 7 Go A 2 E for s gt 1 Explain why this implies that S 3 Prove that 71 2175 5 M8 71Cs for s Uit with 039 gt 0 and s 31 1 l l H n Hint It may help to consider the case 039 gt 1 first but don7t forget to address the case 039 gt 0 0 We are now ready to complete the proof of Dirichlet7s Theorem As we saw before we need only justify the following Theorem 2 Ex is not the principal character modulo an integer m gt 1 then L1X 31 0 Proof Recalling the definition of wLs x from the previous section Part ll of the Proof of Dirichlet7s Theorem we define for 039 gt 1 00 k Qltsgt ZwltLltsxgtgt Z Z X ka1p where the sum on X is over all characters modulo m The right hand side converges absolutely for 039 gt 1 so that we can rearrange the order of summation Let 7 denote the number of characters modulo m Then by making the inner sum be over X and using property viii of Dirichlet characters we deduce that 00 7 an kpks 711 5 628 7 p 1 kltoo pkEl mod m where an rk if n pk E 1 mod m k E Z and an 0 otherwise This last series converges absolutely for 039 gt 1 Let d be such that ad E 1 mod m for every integer u with gcdu m 1 so we may take d 7 m but we needn7t be this precise Then an rd whenever n pd and p l m It follows that the Dirichlet series 221 anns does not converge for s ld use that the sum of the reciprocals of the primes diverges and that each an 2 0 Hence the abscissa of convergence for 221 anns is in ld 1 Now consider Q82 Qs3 1 eQlt5gt1 628 2 3 The powers of Qs are themselves Dirichlet series and each power converges absolutely for 039 gt 1 since each an 2 0 Also 11 0 implies that any given lns appears as a 32 term with a non zero coef cient for only nitely many of the powers of Qs Since the expression on the right hand side above converges for 039 gt 1 we obtain that the terms on the right hand side can be rearranged to form a Dirichlet series representation for fs that converges for 039 gt 1 This Dirichlet series will contain non negative coef cients and the coef cient of 1115 will be at least an Since the Dirichlet series 221 anns does not converge for s ld it follows that neither does the Dirichlet series representing fs Thus this Dirichlet series has abscissa of convergence 00 2 ld Recall that ewL57X Ls x The definition of Qs implies that for 039 gt l 1 e69 Hum X Assume there is a non principal character 6 such that LlX 0 Then by considering the Taylor series for LsX about 1 we deduce that LsX s 7 lgs for some analytic function 98 Recall that if X0 is the principal character Ls X0 is analytic for 039 gt 0 except for a simple pole at 1 It follows that LsXL3X0 can be viewed as an analytic function in the region 039 gt 0 Therefore we can view fs as being analytic for 039 gt 0 But then fs is an analytic function for 039 gt 0 which for 039 gt 00 can be represented by a Dirichlet series with non negative coef cients and with a positive abscissa of convergence This contradicts Theorem 1 completing the proof Homework 1 A stronger version of Dirichlet7s Theorem and the Prime Nurnber Theorern is as follows Theorem Let a and m be integers with m 2 l and gcda m 1 Let 1416 HP 3 21 2 a mod Then there are positive constants 01 and 02 such that for all x 2 2 1 9 dt Aac 7 lt Clace C 10 W71 2 logt In the theorem m denotes the number of positive integers k S m with gcdk m l 9 dt x 2 logt logic 10g235 by parts and express the resulting integral as a sum of two integrals one with limits of integration from V to b Show that e CQVIOgm lt rithrns of both sides c Using the theorem above show that there is a constant 0 for which a Show that 516 for at suf ciently large Suggestion lntegrate 1 1 2 for at suf ciently large Hint Compare the loga og at at 2 for at suf ciently large AW 7 mbg lt Olog 36 33 d Using the theorem above or c show that there is a constant C for which 1 2 for x su iciently large og at We 7 logic 2 Using lc and Abel summation prove that 1 1 7 lo lo xE Z M g g p w pEa mod m where S O for some constant C The Pure Brun Sieve o A quick review Recall that we showed that Mac is small compared to x by estimating the size of Azx S x pln gt p gt P1P2 We e i al ed e esi 8 e Azac S H l 7 2quotZ p z We began with the identity Azac at 1 p1ltp2gz by removing the brackets of the greatest integer function and estimating the resulting error This is the basic idea of the Sieve of Eratosthenes In this section we give an alternative approach to bounding Az x called the Pure Brun Sieve Unlike most of the material in this course the approach here is elementary o A first estimate To find an upper bound on Az x we first prove that at at gtk A z x S x 7 7 H w H 2t m piz where k is any positive integer For this purpose define anl7Zl Z 17 Z 1 sz P1ltP2 Z P1ltP2ltquot39ltP2k z pl 171mln pun mm 9 l P1P239HP2k p1ltP2 Z P1ltP2ltmltP2k Z To prove gt0 it su ices to show that t 1 if pin gt p gt 2 an is 2 0 otherw1se 34 use that Azac S Z ltm an and interchange summations The first part is obvious for if every prime factor of n is gt 2 then all the sums in the definition of an are empty and only the term 1 is non zero in this definition Now suppose n pill p Tm where the pj are distinct primes S 2 each of 7 61 6T are positive integers and every prime factor of m is gt 2 It follows that M an1 i7m2rk where we interpret as 0 is b gt a To show that an 2 0 consider three cases 7 3 2k ii 2k lt 7 3 4k and iii 7 gt 4k Case is dealt with by using 1 7 1V 0 to show an 0 For Case ii use 171V 0 to obtain a 7 241 7 242 7 2 1 7 2k12 243 7 2k14 20 For Case iii use directly to show that an 2 l by again grouping the binomial coef cients in pairs 0 Modifying the above The above can be used to obtain an upper bound for Mac that is smaller than the estimate we made with the Sieve of Eratosthenes However our real goal is to find an upper bound for 7raac 3 211 and 11 1 are primes H where a is any xed positive integer which we will take to be even for obvious reasons We define AZ S x plnm a gt p gt Observe that for any 2 2 l 7raac S Azx 2 Thus we seek a good estimate for Az We use that AZa E 2 047mm ngm 32 Z 1 Z Z 1 ngm pgz nltm p1ltP2 Z 7 ngm pW agt P1P2 W agt 7 Z Z l P1ltP2ltltp2k z 71 P1P2quot39P2kl a We fix momentarily z 2 a so that if pla then 1 S 2 For a given 1 S 2 we consider two possibilities pla and p l a If pla then the number of n S x for which plum a is acp which is within 1 of xvp lf pl 1 then the number of n S x for which plum a is within 35 2 of 2acp In general if 191 pu are distinct primes dividing a and pu1 puu are distinct primes not dividing a then the number of n S x for which 1101 a is divisible by plpg puu is within 2 of Tat11192 puu this can be seen by using the Chinese Remainder Theorem and considering the number of such 11 in a complete system of residues modulo plpg puu It follows that x 210 A z x lt x 7 7 lt gt g p g p ILZ ILZ pla Pia x 210 410 Z Z Z P1ltp2 z p1p2 p1ltp2 z p1p2 p1ltp2 z p1p2 P1P2la Pila7P2ia Plia7P2ia 22km Z E1 P1 quot PZk P1ltP2ltltp2k z Plia77p2kia l 2 H 17 H 17 E1E2 P lt P pla Piz pla where 7W 7W 2k 7W E lt l 2 4 2 1 7 lt 1 lt 2 2k 2k 22 22k 2 2k 3712 lt12 m 6 7rz and 2k1 2k2 E2 S 2 x 2 x P1P2 39 39 39P2k1 P1P2 39 39 P2k2 p1ltP2ltmltp2k1 Z p1ltp2ltmltp2k2 Z We now find a bound for this last expression on the right to bound E2 as follows 00 1 2 u 00 1 u E2395 2 Z Sac Z Hlt2loglogz201 u2k1 pgz p u2k1 where 01 is some appropriate constant Using 6 20 ujji 2 uuui and choosing k 6 log log 2 we obtain 00 26 log logz 2601 u 00 l u x x E lt lt lt 2 i in Z lt u i in Z 2 22k doggy u2k1 u2k1 for z su iciently large We also have E1 S 627TZ2k S Zl2loglogz 36 for z su iciently large We now choose 2 xl2410g10gm and consider at su iciently large to deduce that 1 2 Azx g g l 7 H l 7 E pSz p a where S aclog 5 Observe that for some constants 02 and 03 depending on a H 111 H 1120 g 1 g pl sz pgz pla Hence we deduce the Theorem Let a be any xed positive integer Then for at suf ciently large aw S Clogac2 log log 302 for some constant 0 depending on a 0 Twin primes A twin prime is a prime which differs from another prime by 2 Thus the twin primes are 3 5 7 ll l3 17 19 29 31 It is unknown whether or not there are infinitely many twin primes Brun introduced what is now called the pure Brun sieve to establish that the sum of the reciprocals of the twin primes converges Since 7r2x can be used to bound the number of twin primes up to x 71392ac is not precisely the number of these twin primes but clearly this number is S 27rgac for x 2 1 one can use the previous theorem and Abel summation to estimate the sum of the reciprocals of the twin primes This shows the sum converges Homework 1 Let 1 denote the nth prime a Explain why the Prime Number Theorem implies that lim suppn1 7 p7 00 b Recall that we showed that we Gag Mloglogx for some constant C where 7raac S x n and n a are primel Use this to prove that for every positive integer k hmsupmin19n1 PmPn2 Pn1 Pnk 7pnk71 OO 71700 Note that this would follow from part a if min were replaced by max the problem is to figure out how to handle the min situation Math 782 Analytic Number Theory Instructor s N0tes Analytic Versus Elementary o Terminology Analytic Number Theory makes use of Complex Analysis and Elemen tary Number Theory does not but it isn7t so simple to distinguish 0 Writing an integer as a sum of two squares This is the rst of a few examples of how Complex Analysis can be used to answer a question seemingly unrelated to it if a and b are sums of 2 squares why must ab be also 0 Coverings A covering of the integers is a system of congruences x E a mod 7 such that every integer satisfies at least one of these congruences A perfect covering is one in which each integer satisfies exactly one of the congruences Suppose we have a nite perfect covering of the integers with each modulus m gt 1 Show that the largest modulus occurs twice Use that 1 T 2quot for lt 1 3 where 1 lt m1 3 m2 3 3 mr and 0 S a lt 7 Suppose that mpl 31 mr Then the right hand side and not the left hand side gets large in absolute value as 2 approaches exp27rimr The contradiction implies mpl mr 0 Preliminaries on exponentials The following are useful formulas n71 V 0 f k 0 E 6227rkn 7 10 n if k 0 16i2wk9d6i2weik9dg 0 0 27139 0 1 ifk0 o Putnam Problem A 6 1985 If 1916 a0 1115 1me is a polynomial with real coef cients a then set Ppac a8 a 1 Let at 32 710 2 Find with proof a polynomial 910 with real coef cients such that 90 1 and ii Pfx Pgx for all positive integers n There are perhaps better ways to do this problem but we use what we just learned to establish 1 Ppac 0 p e2quoti9p e ZWiQ d6 Note that at 3x 1ac 2 That 910 62 5x 1 33c 12x 1 provides a solution follows from These notes are from a course taught by Michael Filaseta in the Fall of 1996 P WOW 0 A Geometric Problem Let R be a rectangle and suppose R can be expressed as a union of rectangles R with edges parallel to R and common points only along these edges Suppose each R has at least one edge of integer length Then R itself must have an edge of integer length Let R be positioned so that it is in the first quadrant of the icy plane with an edge on each of the x and y axes Let B have bottom left hand corner uj 1 and let 0g and j be the horizontal and vertical dimensions of B respectively Observe that w39Y I 1 I ert 52mti0 ltgt YEZ w 27139 One uses that one of a and is an integer for each j and that 627riwy dac dy Ze2m39my dac dy R 31 R to obtain the desired result Homework 1 a If a and b are integers which can each be expressed in the form 2 5242 for some integers x and y explain why it is possible to express ab in this form as well b Determine whether the following is true ifa and b are integers and ab can be ezrpressed in the form 2 5242 with x and y integers then either a or b can be as well Either prove the result or give a counterexample 2 Putnam Problem A 5 1985 For m a positive integer define 27r m cos x cos2x cos3x cosmx die 0 a Use one of the preliminary results above yes you must to get credit for the problem to determine with proof for which integers m with l S m S 10 we have m 31 0 Hint Use that cosx eigc e im2 b Generalize part a In other words determine which positive integers m are such that m 31 0 The answer should be in the form m 31 0 if and only if m E u mod v where v is an integer and u is a list of integers Justify your answer Elementary Aspects o The Fundamental Theorem of Arithmetic the atoms of which the matter called integers is made are primes 0 There are infinitely many primes Give three proofs Euclid7s ii 22 l is divisible by a prime gt 2 and iii Hpltl 7 lpZ 1 7r26 an irrational number 0 Explain the notion of rearranging the terms of a series as well as the following lemmas about absolute convergence Lemma 1 If the terms of an absolutely converging series 221 an with an E C are rearranged then the value of the series remains unchanged On the other hand if the series 221 an with an E R converges but not absolutely then any real value can be obtained from an appropriate rearrangement of the series Use the example of the alternating harmonic series 22171WHn to illustrate the second half of the lemma and to give the first half more meaning For the first half let S 221 an and let 221 a be a rearrangement of it Let 6 gt 0 Fix no such that Z gtm lanl lt e Let N be suf ciently large so that the terms a1 am appear among al aN Then M2 475 Z lanllta 1 ngtno n The first part of the lemma follows Lemma 2 The product of two L t The product of 221 an and 221 b is 222 on where on akbnk The result follows since 2772 lcnl is an increasing function of N bounded above by cwwcyging series waveyes absolutely s Elba In fact 21 21 lakbll converges Lemma 2 is of interest but is not really needed in what follows Homework 1 Let f ZHZ gt gt C We say that the iterated series f ffltmngtfffltmmgt 711 m 711 m1 H 4 converges if for each positive integer n the series 21 fm n converges and if N 00 lt w exists The value of this limit is called the value of the iterated series We say that the double series 2 Wm H 1 nltoo 1 mltltxgt converges if there is an S such that for every 8 gt 0 there exists a K K6 such that if N and M are positive integers 2 K then N M Z fmn 75 lt5 711 m1 The number S is called the value of the double series Suppose the double series is ab solutely convergent in other words that Z lfmnl converges Prove that 1 nltltxgt 1 mltoo 2 rm ZZ mm and ZZ mm n1m1 1gnltoo m1 711 1 mltltxgt each of converges and that their three values are equal 0 Euler7s product identity namely 71 oo 1 1 lt17 E forsgtl p p5 711 5 Let Px denote the product above restricted to primes p S x Use Lemma 1 to show The identity follows 0 First proof that 2p 11 diverges Assume not Fix N such that Z 1 lt 12 Then pgtN HHV 1giltz f pgN pgtN 711 for any M gt 0 This is a contradiction the left hand side is nite o Logarithms and H11 7 17 Suppose that 0 S 1 lt 12 This condition implies S M8 kll gk M8 k 2 a 3 2a 3 an a H to a H 2 We use k log17 x 7 3 for lt 1 actually for 71 S x lt1 M8 a l l 1 Observe that N N N log H17 an Zlog17 an 2 72 17 711 711 711 The left hand side is decreasing so that if 221 1 converges then so does Hf 7 an The inequality log Hg11 7 an S 7 2771 1 implies that if H11 7 an converges then so does 221 17 1 1 Th t39 t 17 lt o e es ima e Hp m p710g11 Use 71 m Hlt17l 2 12 ldtlogac P n 1 5 pgm 711 0 Second proof that 2p 11 diverges Let Pltxgt 7 upglt17lt1pgtgt1 and so 7 2911 Then by ltgt logPacSE where 0 E 2Zi2 2 1 p w The result follows since Px 2 log at Note we have found a good lower bound for Zpgm 111 o A noteworthy example The product Hp1 7 119 and 221 are related if you expand the product and rearrange the terms you get the sum The value of the product is 0 and the value of the sum is 0 however it is considerably harder to show the latter It is equivalent to the Prime Number Theorem 0 The notation 7116 and a proof that limmmoo 0 Show that in fact 7116 lt 015 log logic for some constant C by using the sieve of Er atosthenes Discuss sieves in general Homework 1 a Modify the previous argument to show that almost all positive integers n have a prime factor 3 log n More precisely and moreover show that Mn 3 x n does not have a prime factor 3 log is bounded above by 015 log logic for some constant C Hint Most n S x which do not have a prime factor 3 logn also do not have a prime factor 3 log b Suppose wn is any function defined for n E Z which tends to infinity with n Prove that hm S x n has a prime factor 3 7 mace x 1 2 Give the analysis details to the second half of the proof of Lemma 1 The Functions Mac 1920 and 11ac and Chebyshev s Estimate logic 0 Define 1916 Zlogp and LJ Z logp Z logp P90 pm w p w o The limit connection with possibly infinite limits Theorem The following hold lim inf M liminf dim liminf W mace m oo mace and 19 l hm SUP E lim sup via hm sup 35 Og mace 3 mace More generally 239fo is such that limnnoo at 00 and any of the limits limnnoo 19xnacm limnnoo xnacm limnnoo 7rxnlogxnacn ezrz39sts then they all ezm39st and are equal Comment This theorem follows fairly quickly from the fact that limmnoo 0 and Abel summation to be discussed momentarily Proof of Theorem We show that for every 8 gt 0 and for at suf ciently large ac 2 06 7raclog 01 S y S lt 7rlogx 1 6 from which the theorem follows The second inequality is obvious The last inequality is a consequence of logic lt 16 pg logp logp 7 Zlogac 7raclogx p w For the first inequality suppose as we may that e lt 1 and take in 1 7 6 From vltmgtzlogp2 Z logywlogxgtltvrltxgt7vrltxwgtgt pgm mwltp m we deduce that q 1 1 it 2 w7ric ogx 7 w ogx x x gol w and the first inequality follows 0 Chebyshev7s Theorem in a weaker form Theorem Ifx is su iciently large then 069 3 lt7riclt278 3 g lo log it Lemma Let n be a positive integer and let be a prime Then the non negative integer k for which pk exactly divides n is n n P 1 F Proof of Theorem Let N Let hp denote the integer k such that pk exactly divides n N From the Lemma we deduce that tie 1amp1 The upper limit of summation could be replaced by log 2nlog Observe that 210 7 2M is 0 or 1 depending respectively on whether it is such that lt 12 or not It follows that hp 3 log 2nlogp Using 115 Zpgm log 300ng logp and that N mpg ka we deduce that logN S 112n Since N is the largest coe icient in ac 12 to see this use that WWI 111 we deduce that N lt 22 and ii 2n 1N gt 22 We are interested in ii for the moment which implies a lower bound on log N We deduce from the above that k l 3 12n 2 2n log 2 7 log2n 1 For x gt 2 and n ac2 we obtain 115 2 12n gt ac 7 2 log 2 7 logx 1 Dividing by it we deduce that liminfmmoo 2 log2 gt 069 The previous theorem now implies the lower bound in Chebyshev7s theorem The upper bound can be obtained by using H ltp 2 p S N and to deduce that 19211 7 1911 2 log 3 logN lt 211 log 2 nltp 2n Let x gt 1 and denote by m the non negative integer for which 27 lt x S 27quot Letting n l 2 4 2 above and summing we obtain 1910 3 mm in 1921 7 192j lt 2m2log2 lt 4 log 2ac 30 It follows that limsupm oo S 4log2 lt 278 The upper bound in Chebyshev7s theorem now follows from the previous theorem 0 Why did Chebyshev care Chebyshev was interested in proving Bertrand7s hypothesis that for every positive inte ger 11 there is a prime in the interval 11211 He did this by obtaining a stronger version of his theorem than we have stated here He showed that 092 36 lt lt111 77 logic logic for at suf ciently large It follows that for n suf ciently large 2n n 2 7 gt092 7111 gt0 M n Mn log2n logn which establishes Bertrand7s hypothesis when n is suf ciently large To complete the proof of Bertrand7s hypothesis one can determine what suf ciently large77 means here and then check the hypothesis directly for the n which are not suf ciently large Homework 1 a Using the ideas above and Chebyshev7s theorem as we have established it find a constant c as small as you can such that for every 8 gt 0 and for at suf ciently large depending on 6 there is a prime in the interval at c b Find a constant c as small as you can such that for every 8 gt 0 and for at suf ciently large depending on 6 there are at least 3 primes in the interval at c 2 a Show that for n suf ciently large the nth prime is 3 2n log n b Show that for n suf ciently large the nth prime is 2 nlog 3 Explain why the Chebyshev estimates established here imply that there are positive constants 01 and 02 such that 01i lt 7rac lt 02i for all x 2 2 logic logic More Background Material 0 Abel7s Summation Formula Theorem For a function a with domain Z set Aac Zak Suppose f is a kgm function with a continuous derivative on the interval uv where 0 lt u lt v Then 2 WWW Avfv Aufu UAfd Proof Clearly the left hand side is not changed by replacing it With and v With One checks that the same is true of the right hand side It therefore su ices to consider it and v to be integers Observe that an An 7 An 7 1 The theorem follows from 11 Z acorn Z AnAn1fn ultn v nu1 v71 MM 7 Altugtfltu 1gte Z W 1gte fltngtgtAltngt nu1 v71 n1 Avfv e Aufu e 2 AW it dx Homework 1 Let A be a set of positive integers and let Aac a E A a S Suppose that there is a constant c gt 0 such that 1 Z gt clog logic for all x su iciently large aEA a Prove that given any t gt 0 there is an x 2 t for Which gt can 2logx AW Note that I did not say that for all x 2 t the last inequality holds 10 2 Let n denote an arbitrary positive integer Recall that 3 foralleR m x2 at gt0 el a Using gt0 show that n gt ne b Let ac n l in and show that the first 2n 2 terms are each 3 n l nl Also show that the remaining terms sum to a number lt n l nl c Use b to show that n lt MQn 3 6n1 n 1n1 d Modify the above to show that n lt 2lt e 3 a Let n be a positive integer Using Abel summation prove that Zlogknlogn7 mdoc k1 1 in b Using a and the inequality 3 ac prove that n gt ne n1 e d Which upper bound on n is better when n is large the one given in 2d or the c Do a similar argument to show that n lt one given in 3c Explain o Derivatives of Sums and Sums of Derivatives Theorem Let 21 be a sequence of dt erenttoble functions such that 221 fnx converges for at gt 0 and C15 221 converges uniformly for at gt to Then Fac ezm39sts and Fac C15 for at gt 0 Proof Let 6 gt 0 Let FNx 2771 fnx and GNx 2771 There is an N0 N0e such that if M 2 N0 and at is any real number gt 0 then lGMac fowl lt Let N and M be 2 N0 Then low 7 oMu lt for all t gt to Fix at gt 0 Then there is a 6 6Mx 6 015 7 0 such that if lt 6 then FM h 7 FM 7 GMW lt Fix lt 6 Since FN 7 FM is differentiable on x0 00 we deduce from the Mean Value Theorem that there is a t between at and at h such that FN h 7 FM h 7 FNW 7 FM 7 hFzvt 7 FMU hGNt 7 GMt We deduce that 7 h h lt wlm This is true independent of the choice of N 2 N0 so by letting N tend to in nity we obtain Fac h 7 i FMx h 7 FMx h h Nlm Combining the first third and fifth of the above displayed inequalities we obtain that Fx h 7 h 7 ac lt6 It follows that Fac exists and Fac C15 as desired Further Elementary Results 0 Comment on this material Following classical lines we show shortly that if limmnoo 7rxlog exists then it is l The approach below is of some interest in itself but we note if the goal is simply to establish this information about limmnoo 7rxlog 3015 there is an easier way One can skip the next two sections and go to Merten7s formulas Then this result on limmnoo 7rxlog follows as a consequence of Merten7s formulas and an application of Abel summation see the third homework problem below 0 The function 3 and its derivative We use Euler7s identity discussed earlier and define the Riemann zeta function to be 00 71 5Znis lt1il forsgt1 721 p We will also use the von Mangoldt function n which is defined to be logp if n pk for some prime p and some positive integer k and to be 0 otherwise In particular LJ Z gm Observe that for s gt 1 logCs7Zlog 17 2f W By taking derivatives on both sides of this first equation and recalling the preliminary results above we deduce that Cs p slogp logp 0 M as p 1712 s 2 Z 12 By Abel summation we now deduce that 768 800 via doc for 5 gt1 1 51 0 1f limmmoo Mac logicac exists it is 1 Theorem liminf W S 1 3 lim sup 7rlt10g ma 9 700 at Lemma lims 71Cs 1 and hm8 7126 71 5H1 5H1 Proof of Lemma For the first limit use that 1 1 1 1 s doc lt lt 1 doc s 7 1 1 5 2 n5 1 5 5 7 1 711 For the second use an integration by parts to obtain 00 logn logic 1 7 7 E 7 7 C 8 7 711 5 x1 8 d E s 712 E where S 1 Proof of Theorem Let fs 7CsCs The lemma implies that limsn1s 7 1fs exists and is 1 1t su ices to show S 1 S limsup 90700 am we lim inf 700 Assume the first inequality is incorrect Then there is a K gt 1 and an 0 such that if x 2 0 then gt K Hence for 5 gt1 fss100 wdgt8 mo des wgdslmo wd epi x5 1 x5 5 7 1 Multiplying through by s 7 1 and letting s 7 1 we obtain a contradiction 1n the same manner one handles the possibility that lt L lt 1 for x 2 x6 0 Merten7s Formulas The following results are due to Merten A 1 w t Z logxO1 Z 0gp 1ogx01 dtaogmon ngm n pgm p 1 t ZlloglogAOllogx and H Pgmp pgm 1 B 1 7 N p logic where A and B are constants Discuss what these results mean the notation Observe that for any positive integer m For m 2 l we easily deduce that mlogm 2 logmi 2 mlogm 7 m Also 10 m 10s pl logltmxgt 7 Z 1ogp 2 mm 7 Z W M pgm j0 ngm nltm where we have used that 11m Z ltm An Dividing through by m we obtain 7 Z w logm 01 ngm The first of Merten7s formulas now follows consider replacing x with The second formula follows from the first by observing 0 logp 7 log 2p pi 723199971 13972 is a convergent series The third formula follows from the first by using Abel summation take an An and ft 115 and using that 1Z1x 015 by Chebyshev7s estimates The fourth formula follows from the second by Abel summation take 11 logpp an 0 otherwise and ft llog t The fifth formula is left as a homework problem Homework 1 We showed that if 713111 is a sequence tending to infinity and limnmoo or limnmoo 7rz log gunac exists then they both do and are equal Show that this follows from Abel summation you may also use limmmoo 0 but this is not necessary P logl 7 x as discussed earlier You will want to take advantage of another of Merten7s formulas l B 2 Prove the formula H l 7 7 1 above Hints Use the Maclaurin series for ogac p w 14 3 Use the fourth formula of Merten above and Abel summation to give an alternative proof of the result at logic lim inf 7r logic mace at 7r 3 l S limsup mace Complex Preliminaries o Analytic functions on a region Q non empty open and connected The derivative of fz exists on 9 All the derivatives of fz exist on Q The function at iy Mac y ivy is such that u and v satisfy the Cauchy Riemann equations in 9 u v an u 7 1 810 8y By 810 The function fz may be represented as a power series at each point in Q o The ldentity Theorem If S Q Q has an accumulation point in Q and f and g are analytic functions for which fz 92 for all z E S then f E g on Q o Weierstrass7 Theorem a version of it Let 2c 5 denote an analytic function in Q for each x 2 1 Suppose as x approaches infinity fms converges uniformly to fs on every compact subset of 9 Then fs is analytic in Q and f s converges uniformly to fs on every compact subset of Q Homework 1 Fix 039 E R Let C be a compact set in the region Res gt 039 Prove that there is a 0 gt 039 such that O is in the region Res gt 0 The Riemann Zeta Function in the Complex Plane 0 The function 3 in the right half plane The definition 3 221 1115 is well defined for s 0 it 0 and 15 real with 039 gt 1 and defines an analytic function in this region here we interpret n5 as 651 where log refers to the principal branch of the logarithm lt converges uniformly for 039 2 00 gt 1 By Abel summation with an l and ft 1155 we deduce that 1 1 Z l 7s u1du forUgtl 7111quot 571 1 715 m it By considering Weierstrass7 Theorem with fms 5 31 du we deduce that the right 1 u hand side is analytic for 039 gt 0 except for a pole with residue 1 at s 1 By the Identity Theorem the right hand side is the only possible continuation of 5 to the right half plane as a meromorphic function The Riemann zeta function 5 refers to the right hand side above when 039 gt 0 71 l Euler7s identity 5 H l 7 holds for o gt 1 Observe that for o gt 1 p5 p measnoesaa p w p w It follows that the absolute value of the product in Euler7s identity is bounded below by lo In particular 5 is non zero for o gt 1 Homework 1 Look at our argument for Euler7s identity given for real 5 gt 1 Explain how to modify it to show the identity holds for o gt 1 as stated above 0 The Riemann Hypothesis with 5 defined as above 5 0 gt o 12 discuss some partial results that are known and implications such as on the gap problem for primes o The line 0 1 Theorem Ift7 0 then lit 0 Lemma 1 log Relog Lemma 2 3 4cos6 cos26 21 cos 62 2 0 Proof of Theorem From Lemma 1 for o gt 1 0 1 00 an 00 an 1 R l R R t1 og was elt ogcltsgtgt 2p A W 21 7121 no coslt 0g where an lm if n pm for some prime p and an 0 otherwise Hence log l3o4o ito i2t Z a 3 4 cost log n cos2t log 7 711 The definition of an and Lemma 2 imply that the right hand side is 2 0 It follows that for o gt 1 1 will 4 W 7 1CltUgtl3 lClt0 mm lC3UgtC4ltU mm mm 2 71 Assume lit 0 witht 31 0 We let I approach 1 from the right above We have already shown 0 7 lo approaches 1 also clear from the analytic continuation formulation of 5 Observe that o ito 7 l approaches 1 it Thus taking a limit of the left hand side above we obtain ll itl4ll i2t On the right hand side the limit approaches infinity Thus we obtain a contradiction establishing the theorem 16 Proof of the Prime Number Theorem 0 The Prime Number Theorem was first established independently by Hadamard and de la Vall e Poussin in 1896 It is the following 1 Theorem lim m Homework 1 Let p denote the nth prime Using the Prime Number Theorem prove that p71 hm new n logn 2 Let 8 gt 0 Using the Prime Number Theorem prove that there is an 0 x06 such that 60 s c lt H p lt calmc for all it 2 0 p w 3 Let p denote the jth prime and suppose that a1 a2 am are positive integers lf pr is the largest prime factor of a1a2 am then we can factor each ak as ak 1113 Where each ejk 2 0 j1 The least common multiple of the integers a1a2am denoted lcma1a2 am satisfies 7 lcma1a2am 1 1ij where f maxejk 1 k S j1 Let c denote a constant Using the Prime Number Theorem prove that li ngtltxgt mlcml2ni 0 ifcgtl e0 7 oo ifcltl o For the proof of the Prime Number Theorem we will make use of previous material together with the following result the Wiener lkehara Theorem Theorem Let Aac be a non negative non decreasing function of ac de ned for it E 0 0oo Suppose that the integral Axe die converges for o gt 1 to a function fs 0 which is analytic for o 2 l ezrcept for a simple pole at s l with residue 1 Then lim e mAQc l ac Comment To prove the lemma one can consider the double integral of ftac This integral is finite and this justifies such an interchange Lemma 2 Let fs be analytic on o Res 2 1 hence in an open region containing such s Let a and b be real numbers with a lt b Then as w 7 0 fl 77 wiy converges uniformly to fl 77 iy for y E a b Proof Write fx 77 iy uxy 77 ivicy Since f is anaytic on o 2 1 each of u and v has continuous partial derivatives for gay with it 2 1 Let M be a bound on use xy and vmxy in the set 1 2 gtlt a b Then with z liy and 0 S w 3 l the Mean Value Theorem gives lflt2 w 7 flt2gtl lult1 w 7 ult1ygt lvlt1 w 7 my 2wM The lemma follows Lemma 3 Let a and b be real numbers with a lt b Let htw ab gtlt 000 7 C be a continuous function such that htw converges to ht0 uniformly fort 6 ab Then b b 1113 htwdt ht0dt Proof Fix 6 gt 0 Choose 6 gt 0 such that if 0 S w lt 6 and t E 1 b then lhtw 7 ht 0 lt eb 7 1 Then abhtwdt7 abht0dt K View 7 we dt lt e The result follows Lemma 4 Let f R 7 R be a non negative function for which fac die ezrists Then 0 lim 000 fice mc die Ooo fac doc w7gt0 00 15 Proof Let 6 gt 0 Fix t gt 0 such that fac die lt 54 Let I fac doc Fix 6 gt 0 t 0 lt e S 1 Then e htht39f0lt 6th 17 suc a1 iwlt en 2I1 Ooo fxe wm die 7 Ooo fac die The result follows 15 oo 321 10 fxdic2t fxdaclte Lemma 5 Let f R 7 R be a non negative function for which lim fice mc die w7gt0 0 ezrists Then lim fice mc dic fxdac w7gt0 0 0 Homework 1 Prove Lemma 5 Do not assume fac die exists 0 We will use the following weak version of the Riemann Lebesgue Lemma Lemma 6 Let a and b be real numbers with a lt b Let f ab 7 C be such that i f ezrists everywhere in 1 b and b ii ft dt is nite b Then lim fteiytdt0 9700 a Comment Observe that ii holds if f is continuous on 1 b This will be the case for our use of the lemma Proof Integration by parts gives 39 b ezyt b b I fteiytdtft fteiytdt gtin Thus b b The result follows We will also make use of 00 2 Lemma 7 g dac 7r 00 at There is no real need to discuss the proof as the value of the integral will not come into play only its existence will which is clear 0 A Proof of the Wiener lkehara Theorem Set B Axe m It follows that g 7 L1 MBx 7 1e 1 c die for 039 gt1 0 8 Define 93 to be the left hand side By the conditions on f we deduce that g is analytic for 039 21 Fix 8 gt 0 and let ht 91 5 it Fix A gt 0 Then ht1i gyw dt 7 Z lt 7 g5iytOOOB 7 le 5itm dab dt We justify that for 039 gt 1 we can interchange the order of integration by using Lemma 1 We consider 5 l 52 and x gt 0 Observe that fs Aue usdu 2 e usdu M 0 90 Thus B 141306 c S sfseE2m It follows that where O sfs 1 Lemma 1 now justifies the interchange of the order of integration A direct calculation gives l 2gt 17 6iy7mt Sin2y 7 2 2A 2 My 902 We deduce that 2A 00 2 fan OF 72A hltt1i geiyt dt 0 30071gt67m81nkf29 2gtgtdm 20 Since 95 is analytic for 039 2 l we deduce from Lemma 2 that ht see its de nition converges uniformly to 91 115 for t E 72A2A as 8 approaches 0 from the right It follows from Lemma 3 that lim 2A 111 1 eiytd12A g111 1 eiytd1 570 72A 2A 72A 2A By Lemma 4 oo 2 7 00 2 7 Ag 39 2 lim e mw dag w dac Sm U d so 0 y 7 m2 0 My 7 352 7 02 Since B is non negative Lemma 5 and now give 0 7 sin2y 7 7 0 sin2y 7 713517 0 Bace deO dac M 1 sin2 1 LBQ X We let 8 7 0 in Next we let y tend to infinity Observe that 2A 11 1 W iytdt7O 11 1t mam 11 1 t 211111 ng 1 2A6 12A9 1 2A6 09 1 2A6 and we can apply Lemma 6 to each of the integrals on the right From this and Lemma 7 we obtain M v sinZU gt11 yleO70ltBy7x v2 dv7r Explain why intuitively implies we are through Let a be such that 0 lt a lt Ay Since AW Bace c is non decreasing we get for 7a S v S a that ey7ltaAgtBy S 59UABy S eyltaAgtBy r 72 72alt 73 lt 2 2aA Blty Ae 732 AB y e We now deduce from and the fact that B is non negative that 00 so that a 2 a 39 2 C ZQA lim sup 39 g d hm SUPB y 2 372 1A sm2 U dv 9700 7a U yam A 7a U a 2 S limsup B y 7 3 sm2 0 d1 3 7139 9700 7a A U 21 The above holds for any positive a and A Letting a A and letting A tend to in nity gives that limsupm ooBQc S 1 To nish the proof we show liminfmmoo B 2 1 Observe that lim supm ooBQc S 1 implies B S c for some constant c and all x 2 0 We take a xA again and use that W U sinZU l39 39f B 7 d W gale70 9 Ow 7 sinZU sin20 a v sinZU Sc dv dv liminf B 247 dv x v2 a 02 yeoo 7a A 02 7112 00 2 a 392 SlIl U SlIl U SlIl U lt d d 2 139 39fB d 70 42 v2 v 1222 W 2 v The theorem follows now by letting A tend to infinity Intermission 0 Question Are there infinitely many primes whose decimal representation contains the digit 9 Answer Yes Theorem Given any block of digits d1d2 1 base b 2 2 there exist in nitely many primes whose base b representation contains the block of digits We will specialize our arguments to the original question concerning the digit 9 We give three proofs that infinitely many such primes exist One proof will use the main result of what is to come one will use the main result of where we have been and the other won7t use much Each of the arguments easily generalizes to give the above theorem Before continuing we note that it is unknown whether or not there exist infinitely many primes whose decimal representation does not contain the digit 9 Actually it is known but no proof exists 0 What is to come The next main goal for the course is to establish Dirichlet7s theorem that if a and b are relatively prime integers with a gt 0 then there are infinitely many primes of the form an i b Observe that with a 10 and b 9 we can deduce that there are infinitely many primes whose decimal representation contains in fact ends with 9 Note that the more general theorem stated above can be done the same way by considering b d1d2 dn gtlt 10 1 0 Where we have been We could instead use the Prime Number Theorem as follows Lemma Let E gt 0 Then there is an 0 x06 such that ifac 2 0 then the interval at x 615 contains a prime Before proving the lemma observe that it implies what we want by taking 8 19 and x 9 gtlt 10k 2 0 In fact a similar argument shows there are infinitely many primes whose decimal representation begins with any given block of digits Proof We may suppose that 8 S l and do so Mom the Prime Number Theorem there is an 3 68 such that if x 2 3 then 1 8 at lt lt 15 at 10 logx W16 10 logic 22 Thus at 2 3 implies gt15 E716 x gt sac i xlog2 782 7T 35 ac 7T 35 7 10 log2x 10 logic 7 log2x logaclog2x 5 logic where the last term on the right is a bound on the contribution from the parts involving 510 We deduce that if x is suf ciently large the interval at x 615 contains a prime 0 An elementary argument Let 111112 be the positive integers in increasing order whose decimal representations do not contain the digit 9 Then for N 2 l 71klt10N m j1 10j 1gnklt10j 31 It follows that the partial sums of 221 lnk form a bounded increasing sequence and hence the series converges Since the sum of the reciprocals of the primes diverges it follows that there are infinitely many primes not among the numbers nk Hence there exist infinitely many primes whose decimal representation contains the digit 9 Homework 1 An open problem of Erdo39s is to show that if 111 is an arbitrary infinite sequence of integers such that l S 11 lt 12 lt 13 lt and ii l1j diverges then there exist arbitrarily long arithmetic progressions among the 1 v More precisely given a positive integer N one can find N distinct 1 in an arithmetic progression If true this would imply there are arbitrarily long arithmetic progressions among the primes something which as yet is unknown One approach to resolving the problem might be to consider a sequence 1 21 satisfying and having no N term arithmetic progression and to show that 2111j must then converge If one can show this is true regardless of the value of N 2 1 then the problem of Erdo39s would be resolved The case N l and N 2 are not interesting Deal with the following special case with N 3 Begin with 11 l and 12 2 Let 13 be as small as possible so that no 3 term arithmetic progression occurs among the 1 then selected We get 13 4 Choose 14 now as small as possible avoiding again 3 term arithmetic progressions Then 14 5 Continue in this way The next few 1j7s are 10 ll 13 and 14 Prove that l1j converges Hint Think base 3 Algebraic Preliminaries o A group is a set G of objects together with a binary operation satisfying i If 1 and b are in G then so is 1 b ii If 1 b and c are in G then 1 b c 1 b 0 iii There is an element 6 of G such that 1 e e 1 1 for every 1 E G iv For every 1 E G there is a b E G such that 1 b b 1 6 An abelian group is a group G such that 1 b b 1 for all 1 and b in G A group is finite if G is finite We will simply use 1b to denote 1 b and refer to the binary operation as multiplication unless noted otherwise 23 0 Examples The set of integers under addtion the set of non zero rational numbers under multiplication and the reduced residue system modulo 11 under multiplication are all abelian groups Another example is given by Cj 0 S j S n 71 where C 627W and the binary operation is multiplication Yet another example is given by 151 152 3 under composition where the b are defined multiplicatively on the elements of CC2 C4 where C 62Wi7 with 1C C 2C C2 and 3C C4 Finally consider the multiplicative mappings from the reduced residue system modulo 7 to Cj 0 S j S 5 where C 62mm show that these mappings form a finite abelian group under multiplication o A simple theorem on finite groups We will use the fact that if a is an element of a finite abelian group G then alGl e where e is the identity element in G Give a proof Note that the same is true for any finite group 0 A theorem on finite abelian groups Theorem Let H be a subgroup ofa nite abelian group G Let a E G and let k be the minimal positive integer for which a E H Let Hajbb H0jltk Then H is a subgroup ofG and lHl Proof Let 1 and ajb be elements of H with 0 S ij lt k and b and b in H lf 0 S ij lt k then bb E H implies aiajbb aijbb E H lf ij 2 k then 0 S ij7k lt k In this case akbb E H implies aiajbb aij kakbb E H Thus H is closed under multiplication One also checks that the inverse of ail is ak im kb l E H note that if i 0 then 1 E H Q H The other group properties of H are easily determined to hold and thus H is a subgroup of G To prove lHl lel it suf ces to show that if 1 171 then i j Assume otherwise we suppose as we may that i gt j Then ai j Mr1 E H contradicts the minimality condition on k The contradiction completes the proof Characters 0 The definition A character X of a finite abelian group G is a multiplicative complex valued function not identically zero defined on the group Thus if a and b are elements of the group then Xab XaXb 0 Properties of characters i If e is the identity element of G and X any character then Xe 1 This follows from two observations First Xe 31 0 otherwise Xa XaXe 0 for all a E G contradicting the requirement in the definition that X is not identically zero Next Xe X6Xe and we can deduce from our first observation that Xe 1 ii If lGl n then Xa is an nth root of unity for every 1 E G This follows from X01 XWG X 1 iii For every 1 E G Xa 31 0 See iv lf lGl n then there are exactly 11 distinct characters de ned on G Let H1 c where c is the identity element of G Thus H1 is a subgroup of G If G 31 H1 we apply the theorem of the previous section on groups to construct a new subgroup H2 of G Note that H2 will be a cyclic subgroup of G generated by an element a different from c in G How a 31 6 is chosen doesn7t matter If G 31 H2 then we again apply the theorem to obtain a new subgroup H3 of G We continue defining for i 2 l as long as G 31 Hi the subgroup Hi1 agb b E Hi0 S j lt where ai Z H1 and ki is the minimal positive integer for which a 6 Hi We show by induction on i that the number of distinct characters on HZ is The result will then follow We deduce from that there is precisely one character defined on H1 6 Suppose there are precisely different characters defined on HZ for some i 2 1 If G Hi then we are done as there are no more subgroups to consider Otherwise we wish to show that there are precisely lHZHl different characters defined on Hi Observe that any character on Hi is necessarily a character when restricted to HZ make use of i or iii We finish the argument by showing that each character X of HZ extends to exactly ki different characters on Hi Fix X Observe first that the definition of Hi and the multiplicativity of X imply that X will be defined on Hi once the value of XaZ is determined On the other hand the value of XaZki Xa i is known since a E Call this number 7 Then XaZ must be one of the ki distinct kith roots of y This shows that there are at most ki different extensions of X to Hi On the other hand defining XaZ to be such a kith root of y is easily shown to produce an extension of X to Hi This completes the proof v If a E G and a 31 6 then there is a character X defined on G such that Xa 31 1 In our construction of the HZ above we take H2 ltagt The order of a given in the argument there is M The construction gives a character X of H2 such that Xa is an arbitrary klth root of unity We choose a klth root of unity other than 1 This character extends to a character of G with the desired property vi The characters of G form a finite abelian group under multiplication lf X1 and X2 are two characters defined on G then X X1X2 means Xa X1aX2a for every a in G One checks directly that X is a multiplicative complex valued function which is not identically zero hence the product of two characters is itself a character Associativity and commutitivity follow from the same properties for multiplication in the set of complex numbers The identity element called the principal character is defined by Xa l for every a E G and this is easily checked One also checks that if X is a character then so is X defined by Xa Xa 1 and that X is the inverse of X From iv we now deduce that the characters form a finite abelian group We note that the group G and the group of characters defined on G are isomorphic we do not need this fact and so do not bother with the details of an explanation vii The following holds 0 if X is not principal 2 W1 G 39f 39 39 39 1 aEG l l 1 X ls principa Observe that in the case that X is principal the result is trivial If X is not the principal

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.