2 0. An Infinity of Primes of length r. How many possibilities are there for the values Ψ(s)? We give an upper bound. For each 1 ≤ i ≤ r the value αi must satisfy (0.3) pi αi ≤ s ≤ n. Thus (0.4) αi ≤ logp i n ≤ log2 n. As αi is a nonnegative integer, there are at most 1+log 2 n possibilities for it. With n ≥ 2, the number of possibilities is at most 2 log 2 n. (These kinds of gross upper bounds will appear quite often, and a large part of the art of Asymptopia is knowing when to use them and when not to use them.) Thus the number of possible values of Ψ(s) = (α1,...,αr) is at most 2r(log2 n)r. The vectors (α1,...,αr) uniquely determine s by equation (0.1). We have n different values Ψ(s). We deduce that (0.5) 2r(log 2 n)r ≥ n. The above is all true for any n ≥ 2. But now we apply an asymptotic lens and consider (0.5) asymptotically in n. The left-hand side is a constant times a fixed power of the logarithm function. We know (more on this in §2.4) that any fixed power of ln n grows slower that any fixed positive power of n, so slower than n itself. This means that for n suﬃciently large, (0.5) must fail! We have achieved our reductio ad absurdum, the assumption that the number of primes is finite must be false, and Theorem 0.1 is true. Remark. We do not need the full power of the unique factorization theorem. It suﬃces to know that every s has some representation equation (0.1) as the product of primes to powers. Then for each of the 1 ≤ s ≤ n, select arbitrarily one such representation as Ψ(s). One still has n distinct Ψ(s) and at most 2r(log 2 n)r possible vectors (α1,...,αr). We have worked out this argument in some detail. For those comfortable with asymptotics, especially Definition 2.8 and §2.4, it would go, informally, something like this: there are n values Ψ(s), 1 ≤ s ≤ n and logarithmically many values for each coordinate αi therefore, there are polylog many vectors, but polylog grows more slowly than linearly.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2014 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.