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 con￾stant 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.