Six proofs of the infinity of primes 个 Let S=(s1,s2,s3,...)be a sequence of integers.We say that .S is almost injective if every value occurs at most c times for some con- stant c, .Sis ofsubexponentialgrowthifs2m forall n,wheref:N In place of 2 we could take any is a function with→0. other base larger than 1;for example, log2n leads to the same class Theorem.If the sequence S =(s1,s2,s3,...)is almost injective and of of sequences. subexponential growth,then the set Ps of primes that divide some member of S is infinite. Proof.We may assume that f(n)is monotonely increasing.Otherwise, replace f(n)by F(n)=maxisn f(i);you can easily check that with this F(n)the sequence S again satisfies the subexponential growth condition. Let us suppose for a contradiction that Ps (p1,...,Pk}is finite.For n∈N,let sn=enp1…p,with En∈{1,0，-1}a≥0， where the ai=ai(n)depend on n.(For sn =0 we can put oi=0 for all i.)Then 2a++os≤lsnl≤22o）for≠0， and thus by taking the binary logarithm 0≤a≤a1+…+ak≤2fm）forl≤i≤k. Hence there are not more than 2f()+1 different possible values for each ;=ai(n).Since f is monotone,this gives a first estimate #{distincts≠0forn≤N}≤(2fW+1)k≤2W)+)k On the other hand,since S is almost injective only c terms in the sequence can be equal to 0,and each nonzero absolute value can occur at most 2c times,so we get the lower estimate N-c #{distinct≠0forn≤Ny≥2c Altogether,this gives N-c ≤2kf(W)+1) 2c Taking again the logarithm with base 2 on both sides,we obtain log2(N-c)-log2(2c)<k(f(N)+1)for all N. This,however,is plainly false for large N,as k and c are constants,so goes to i for while goes to 0. ▣
Six proofs of the infinity of primes 7 Let S = (s1, s2, s3,...) be a sequence of integers. We say that • S is almost injective if every value occurs at most c times for some constant c, • S is of subexponential growth if |sn| ≤ 22f(n) for all n, where f: N → R+ is a function with f(n) log2n → 0. In place of 2 we could take any other base larger than 1; for example, |sn| ≤ eef(n) leads to the same class of sequences. Theorem. If the sequence S = (s1, s2, s3,...) is almost injective and of subexponential growth, then the set PS of primes that divide some member of S is infinite. Proof. We may assume that f(n) is monotonely increasing. Otherwise, replace f(n) by F(n) = maxi≤n f(i); you can easily check that with this F(n) the sequence S again satisfies the subexponential growth condition. Let us suppose for a contradiction that PS = {p1,...,pk} is finite. For n ∈ N, let sn = εnpα1 1 ··· pαk k , with εn ∈ {1, 0, −1}, αi ≥ 0, where the αi = αi(n) depend on n. (For sn = 0 we can put αi = 0 for all i.) Then 2α1+···+αk ≤ |sn| ≤ 22f(n) for sn = 0, and thus by taking the binary logarithm 0 ≤ αi ≤ α1 + ··· + αk ≤ 2f(n) for 1 ≤ i ≤ k. Hence there are not more than 2f(n) + 1 different possible values for each αi = αi(n). Since f is monotone, this gives a first estimate #{distinct |sn| = 0 for n ≤ N} ≤ (2f(N) + 1)k ≤ 2(f(N)+1)k. On the other hand, since S is almost injective only c terms in the sequence can be equal to 0, and each nonzero absolute value can occur at most 2c times, so we get the lower estimate #{distinct |sn| = 0 for n ≤ N} ≥ N − c 2c . Altogether, this gives N − c 2c ≤ 2k(f(N)+1). Taking again the logarithm with base 2 on both sides, we obtain log2(N − c) − log2(2c) ≤ k (f(N) + 1) for all N. This, however, is plainly false for large N, as k and c are constants, so log2(N−c) log2N goes to 1 for N → ∞, while f(N) log2N goes to 0.
8 Six proofs of the infinity of primes Can one relax the conditions?At least neither of them is superfluous. That we need the "almost injective"condition can be seen from sequences S like (2,2,2,...)or (1,2,2,4,4,4,4,8,...),which satisfy the growth condition,while Ps =[2}is finite. As for the subexponential growth condition,let us remark that it cannot be weakened toa requirement of the formfor a fixed To see this,one analyzes the sequence of all numbers of the formpp arranged in increasing order,where p1,...,Pk are fixed primes and k is large.This sequence S grows roughly like withwhileP log2n is finite by construction. References [1]B.ARTMANN:Euclid-The Creation of Mathematics,Springer-Verlag,New York 1999 [2]C.ELSHOLTZ:Prime divisors of thin sequences,Amer.Math.Monthly 119 (2012).331-333. [3]P.ERDOs:Uber die ReiheMathematica.Zutphen B7(1938).1-2. [4]L.EULER:Introductio in Analysin Infinitorum,Tomus Primus,Lausanne 1748;Opera Omnia,Ser.1,Vol.8. [5]H.FURSTENBERG:On the infinitude of primes,Amer.Math.Monthly 62 (1955).353. [6]I.SCHUR:Uber die Existenz unendlich vieler Primzahlen in einigen speziellen arithmetischen Progressionen,Sitzungsberichte der Berliner Math. Gesellschaft 11(1912),40-50
8 Six proofs of the infinity of primes Can one relax the conditions? At least neither of them is superfluous. That we need the “almost injective” condition can be seen from sequences S like (2, 2, 2,...) or (1, 2, 2, 4, 4, 4, 4, 8,...), which satisfy the growth condition, while PS = {2} is finite. As for the subexponential growth condition, let us remark that it cannot be weakened to a requirement of the form f(n) log2n ≤ ε for a fixed ε > 0. To see this, one analyzes the sequence of all numbers of the form pα1 1 ··· pαk k arranged in increasing order, where p1,...,pk are fixed primes and k is large. This sequence S grows roughly like 22f(n) with f(n) log2n ≈ 1 k , while PS is finite by construction. References [1] B. ARTMANN: Euclid — The Creation of Mathematics, Springer-Verlag, New York 1999. [2] C. ELSHOLTZ: Prime divisors of thin sequences, Amer. Math. Monthly 119 (2012), 331-333. [3] P. ERDOS˝ : Über die Reihe 1 p , Mathematica, Zutphen B 7 (1938), 1-2. [4] L. EULER: Introductio in Analysin Infinitorum, Tomus Primus, Lausanne 1748; Opera Omnia, Ser. 1, Vol. 8. [5] H. FÜRSTENBERG: On the infinitude of primes, Amer. Math. Monthly 62 (1955), 353. [6] I. SCHUR: Über die Existenz unendlich vieler Primzahlen in einigen speziellen arithmetischen Progressionen, Sitzungsberichte der Berliner Math. Gesellschaft 11 (1912), 40-50.
Bertrand's postulate Chapter 2 We have seen that the sequence of prime numbers 2,3,5,7,...is infinite. To see that the size of its gaps is not bounded,let N:=2.3.5...p denote the product of all prime numbers that are smaller than k+2,and note that none of the k numbers N+2,N+3,N+4,..,N+k,N+(k+1) is prime,since for 2 <i<k+1 we know that i has a prime factor that is smaller than k +2,and this factor also divides N,and hence also N+i. With this recipe,we find,for example,for k =10 that none of the ten numbers 2312,2313,2314,..,2321 is prime. But there are also upper bounds for the gaps in the sequence of prime num- bers.A famous bound states that"the gap to the next prime cannot be larger than the number we start our search at."This is known as Bertrand's pos- tulate,since it was conjectured and verified empirically for n 3 000000 by Joseph Bertrand.It was first proved for all n by Pafnuty Chebyshev in 1850.A much simpler proof was given by the Indian genius Ramanujan. Joseph Bertrand Our Book Proof is by Paul Erdos:it is taken from Erdos'first published paper,which appeared in 1932,when Erdos was 19. Bertrand's postulate Beweis eines Satzes von Tschebyschef For every n 1,there is some prime number p with n<p 2n. Veo尺Edie Budapes dessen es awischen einer maturlichen Zal und ihrer nweifachem stts wenigatens eine Priezan gibt,liegen in der Literatur mchrese Beweise vor.Als eintachsten kann man ohee Zwrael den Reweis von RAMANJAN)hereichoen.In seinem Werk Varlesungen fber Proof.We will estimate the size of the binomial coefficient(care- Zahlemtheorie (Leiprig.1927).Band I,S.66-68 gibt Herr LANDAD einen betonders einfachen Beweis fuir einen Satz uber die Anzahl fully enough to see that if it didn't have any prime factors in the range der Primzanlen unter einer gegebenen Grenze,aus welchem un- mitsibar olgt.da gtcigneles g awischen einer eatrlichem n<p≤2n,then it would be“too small..”Our argument is in five steps. (1)We first prove Bertrand's postulate for n 511.For this one does not f need to check 511 cases:it suffices (this is "Landau's trick")to check that g der dem LANDAUsche印Bewe山unde liegen tchen Satzes telangen ksen,der wie mir scheint-an Ein- nchkeit picht hinter dea HAMAnschen Beweis steht.(iriechische 2,3,5,7,13,23,43,83,163,317,521 luchstben sollen im Folgenden durclwegs positive.lateinische Buchstabem nattrliche Zahten bezcichren:dle Berelchnung p ist far Primaahlen vorbehalten. 1.Der Binomialkocthizient is a sequence of prime numbers,where each is smaller than twice the pre- vious one.Hence every interval fy n<y<2n),with n 511,contains -器 one of these 11 primes. M.Aigner,G.M.Ziegler,Proofs from THE BOOK,DOI 10.1007/978-3-662-44205-0_2, @Springer-Verlag Berlin Heidelberg 2014
Bertrand’s postulate Chapter 2 Joseph Bertrand We have seen that the sequence of prime numbers 2, 3, 5, 7,... is infinite. To see that the size of its gaps is not bounded, let N := 2 · 3 · 5 ··· p denote the product of all prime numbers that are smaller than k + 2, and note that none of the k numbers N + 2, N + 3, N + 4,...,N + k, N + (k + 1) is prime, since for 2 ≤ i ≤ k + 1 we know that i has a prime factor that is smaller than k + 2, and this factor also divides N, and hence also N + i. With this recipe, we find, for example, for k = 10 that none of the ten numbers 2312, 2313, 2314,..., 2321 is prime. But there are also upper bounds for the gaps in the sequence of prime numbers. A famous bound states that “the gap to the next prime cannot be larger than the number we start our search at.” This is known as Bertrand’s postulate, since it was conjectured and verified empirically for n < 3 000 000 by Joseph Bertrand. It was first proved for all n by Pafnuty Chebyshev in 1850. A much simpler proof was given by the Indian genius Ramanujan. Our Book Proof is by Paul Erdos: it is taken from Erd ˝ os’ first published ˝ paper, which appeared in 1932, when Erdos was 19. ˝ Bertrand’s postulate For every n ≥ 1, there is some prime number p with n<p ≤ 2n. Proof. We will estimate the size of the binomial coefficient 2n n carefully enough to see that if it didn’t have any prime factors in the range n<p ≤ 2n, then it would be “too small.” Our argument is in five steps. (1) We first prove Bertrand’s postulate for n ≤ 511. For this one does not need to check 511 cases: it suffices (this is “Landau’s trick”) to check that 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 521 is a sequence of prime numbers, where each is smaller than twice the previous one. Hence every interval {y : n<y ≤ 2n}, with n ≤ 511, contains one of these 11 primes. M. Aigner, G.M. Ziegler, Proofs from THE BOOK, DOI 10.1007/978-3-662-44205-0_2, © Springer-Verlag Berlin Heidelberg 2014
10 Bertrand's postulate (2)Next we prove that Πp≤4- for all realx≥2， (1) . p≤x m叶以 where our notation-here and in the following-is meant to imply that 陈 the product is taken over all prime numbers p x.The proof that we present for this fact uses induction on the number of these primes.It is 1 not from Erdos'original paper,but it is also due to Erdos(see the margin). and it is a true Book Proof.First we note that if g is the largest prime with m2s乙m1 g≤x,then 1<领Π次 Πp=Πpand 49-1≤4r-1. p≤x Thus it suffices to check(1)for the case where z=g is a prime number.For q=2 we get“2≤4，”so we proceed to consider odd primes q=2m+1. (Here we may assume,by induction,that(1)is valid for all integers x in the set {2,3,...,2m}.)For g=2m +1 we split the product and compute g≤("） 4m22m=42m All the pieces of this"one-line computation"are easy to see.In fact, Πp≤4m p≤m+1 holds by induction.The inequality Π p≤ 2m+1 m m+1<p≤2m+1 follows from the observation that ()is an integer.where the primes that we consider all are factors of the numerator(2m +1)!,but not of the denominator m!(m +1)!.Finally Legendre's theorem ≤22m The number n!contains the prime holds since factor p exactly are two (equal!)summands that appear in times. Proof.Exactly of the factors m+1 of n!=1.2.3...n are divisible by 9- p.which accounts for p-factors. Next,L÷」of the factors of nare (3)From Legendre's theorem(see the box)we get that (con- even divisible by p2,which accounts tains the prime factor p exactly for the next÷」prime factors p of n!,etc. ◇ (-)
10 Bertrand’s postulate (2) Next we prove that p≤x p ≤ 4x−1 for all real x ≥ 2, (1) where our notation — here and in the following — is meant to imply that the product is taken over all prime numbers p ≤ x. The proof that we present for this fact uses induction on the number of these primes. It is not from Erdos’ original paper, but it is also due to Erd ˝ os (see the margin), ˝ and it is a true Book Proof. First we note that if q is the largest prime with q ≤ x, then p≤x p = p≤q p and 4q−1 ≤ 4x−1. Thus it suffices to check (1) for the case where x = q is a prime number. For q = 2 we get “2 ≤ 4,” so we proceed to consider odd primes q = 2m + 1. (Here we may assume, by induction, that (1) is valid for all integers x in the set {2, 3,..., 2m}.) For q = 2m + 1 we split the product and compute p≤2m+1 p = p≤m+1 p · m+1<p≤2m+1 p ≤ 4m 2m + 1 m ≤ 4m22m = 42m. All the pieces of this “one-line computation” are easy to see. In fact, p≤m+1 p ≤ 4m holds by induction. The inequality m+1<p≤2m+1 p ≤ 2m + 1 m follows from the observation that 2m+1 m = (2m+1)! m!(m+1)! is an integer, where the primes that we consider all are factors of the numerator (2m + 1)!, but not of the denominator m!(m + 1)!. Finally 2m + 1 m ≤ 22m holds since 2m + 1 m and 2m + 1 m + 1 Legendre’s theorem The number n! contains the prime factor p exactly k≥1 n pk times. Proof. Exactly n p of the factors of n!=1 · 2 · 3 ··· n are divisible by p, which accounts for n p p-factors. Next, n p2 of the factors of n! are even divisible by p2, which accounts for the next n p2 prime factors p of n!, etc. are two (equal!) summands that appear in 2 m+1 k=0 2m + 1 k = 22m+1. (3) From Legendre’s theorem (see the box) we get that 2n n = (2n)! n!n! contains the prime factor p exactly k≥1 2n pk − 2 n pk
Bertrand's postulate 11 times.Here each summand is at most 1,since it satisfies ）=2 and it is an integer.Furthermore the summands vanish whenever p>2n. Thus(contains p exactly max{r:p'≤2n} times.Hence the largest power ofp that divides (is not larger than 2n. In particular,primes p2n appear at most once in () Furthermore-and this,according to Erdos,is the key fact for his proof Examples such as -primes p that satisfy<p<n do not divide (m)at all!Indeed, (9)=23.52.717.1923 3p>2 n implies(forn≥3，and hence p≥3)that p and2 p are the only (a)=23.33.52.171923 multiplesofp that appear as factors themtoofwhile we get (9)=24.32.517.19.23.29 two p-factors in the denominator. illustrate that"very small"prime factors (4)Now we are ready to estimate ()benefitting from a suggestion by p <V2n can appear as higher powers Raimund Seidel,which nicely improves Erdos'original argument.For in ()"small"primes with v2n< n>3,using an estimate from page 14 for the lower bound,we get p n appear at most once,while factors in the gap with in<p n 2n ≤Π2m·Πp·Πn don't appear at all. n P≤V②m V2n<p≤tn n<p≤2n Now,there are no more than v2n primes in the first factor;hence using(1) for the second factor and letting P(n)denote the number of primes between n and 2n we get 2元<(《2m))·(4n）-(2nPa, 4 that is, 4营<(2n)v2m+1+P(m) (2) (5)Taking the logarithm to base 2,the last inequality is turned into 2n P(n)>31og2(2m) -(V2m+1). (3) It remains to verify that the right-hand side of(3)is positive for n large enough.We show that this is the case for n =29=512 (actually,it holds from n =468 onward).By writing 2n-1 =(V2n-1)(V2n +1)and cancelling the (V2n+1)-factor it suffices to show v2n-1>31og2(2n) forn≥29. (4) For n =29,(4)becomes 31 30,and comparing the derivatives (W丘-1y=zamd(3log2xy=左we see that丘-1 grOws faster than 3og for)75 and thus certainly for0 1024. ▣
Bertrand’s postulate 11 times. Here each summand is at most 1, since it satisfies 2n pk − 2 n pk < 2n pk − 2 n pk − 1 = 2, and it is an integer. Furthermore the summands vanish whenever pk > 2n. Thus 2n n contains p exactly k≥1 2n pk − 2 n pk ≤ max{r : pr ≤ 2n} times. Hence the largest power of p that divides 2n n is not larger than 2n. In particular, primes p > √2n appear at most once in 2n n . Furthermore — and this, according to Erdos, is the key fact for his proof ˝ — primes p that satisfy 2 3n<p ≤ n do not divide 2n n at all! Indeed, Examples such as 26 13 = 23 · 52 · 7 · 17 · 19 · 23 28 14 = 23 · 33 · 52 · 17 · 19 · 23 30 15 = 24 · 32 · 5 · 17 · 19 · 23 · 29 illustrate that “very small” prime factors p < √2n can appear as higher powers in 2n n , “small” primes with √2n < p ≤ 2 3n appear at most once, while factors in the gap with 2 3n<p ≤ n don’t appear at all. 3p > 2n implies (for n ≥ 3, and hence p ≥ 3) that p and 2p are the only multiples of p that appear as factors in the numerator of (2n)! n!n! , while we get two p-factors in the denominator. (4) Now we are ready to estimate 2n n , benefitting from a suggestion by Raimund Seidel, which nicely improves Erdos’ original argument. For ˝ n ≥ 3, using an estimate from page 14 for the lower bound, we get 4n 2n ≤ 2n n ≤ p≤√2n 2n · √2n<p≤ 2 3 n p · n<p≤2n p. Now, there are no more than √2n primes in the first factor; hence using (1) for the second factor and letting P(n) denote the number of primes between n and 2n we get 4n 2n < (2n) √2n · 4 2 3 n · (2n) P (n) , that is, 4 n 3 < (2n) √2n+1+P (n) . (2) (5) Taking the logarithm to base 2, the last inequality is turned into P(n) > 2n 3 log2(2n) − ( √ 2n + 1). (3) It remains to verify that the right-hand side of (3) is positive for n large enough. We show that this is the case for n = 29 = 512 (actually, it holds from n = 468 onward). By writing 2n − 1=(√2n − 1)(√ 2n + 1) and cancelling the ( √ 2n + 1)-factor it suffices to show √ 2n − 1 > 3 log2(2n) for n ≥ 29. (4) For n = 29, (4) becomes 31 > 30, and comparing the derivatives ( √x − 1) = 1 2 √ 1 x and (3 log2 x) = 3 log 2 1 x we see that √x − 1 grows faster than 3 log2 x for x > ( 6 log 2 )2 ≈ 75 and thus certainly for x ≥ 210 = 1024.