Some remarks on the infinitude of primes
September 2, 2009 by Qiaochu Yuan
I have at least four planned posts left in the series on symmetric functions, but unfortunately I’ll be very busy for the next two weeks. In the meantime, here are some thoughts on the primes.
Euclid’s proof of the infinitude of the primes is often held up as a shining example of mathematical proof. (Whether this reputation is deserved is a matter of opinion.) Euler’s proof via the zeta function is also classic. An even showier proof by Furstenburg is phrased in the language of topology. Today I’d like to share my personal favorite proof and discuss one of its possible consequences.
Special cases of Dirichlet’s theorem
Euclid’s proof generalizes to certain special cases of Dirichlet’s theorem. The general recipe is as follows. First, one finds an integer polynomial 
with the property that its integer values, with finitely many exceptions, are only divisible by primes in some congruence class. For example, the polynomial 
is only divisible by primes congruent to 
. Then one uses the following result.
Theorem: The set of primes dividing the integer values of an integer polynomial is infinite.
The standard proof of this result is a generalization of Euclid’s proof: if 
(which we can assume WLOG), we suppose that there are finitely many such primes 
and considers 
. After dividing out by 
, we obtain a number coprime to 
; contradiction. (Edit, 2/21/22: As Alexander Stasinski says in the comments, we need to do a little more work here to make sure that is not equal to 
or 
. Every way I can think of to do this is slightly inelegant but we can, for example, instead consider 
, which can only be equal to or for finitely many values of 
, and pick not equal to any such value.)
One obtains Euclid’s result with 
and Dirichlet’s theorem for primes congruent to 
using the cyclotomic polynomials 
; I’ve written about this proof in an old post. A paper of Conrad discusses the generalization of this method to primes congruent to 
where 
; it is known that one can do no better by this method.
Polynomials are not important
The limitation of this method is that is required to be a polynomial, and the reason I no longer like the above proof is that the highly “algebraic” method does not suggest the following generalization at all.
Theorem: Let 
be a strictly increasing sequence of positive integers which grows slower than ![2^{ \sqrt[k]{n} }](https://s0.wp.com/latex.php?latex=2%5E%7B+%5Csqrt%5Bk%5D%7Bn%7D+%7D&bg=ffffff&fg=333333&s=0&c=20201002)
for every 
(in particular, any sequence of polynomial growth rate). Then the set of primes dividing some is infinite.
Proof. We prove the following more precise converse: any strictly increasing sequence of positive integers divisible by at most distinct primes 
grows at least as fast as .
But this is almost obvious. Let 
denote the number of numbers of the form 
less than or equal to 
. Clearly any such number must satisfy
and it follows that 
. In particular, 
for every . (This is not the strongest bound, but it’s enough.) It follows that
.
This is equivalent to the claim we wanted to prove. (Note that if is required to be strictly increasing we get an honest inequality ![a_n \ge 2^{ \sqrt[k]{n} }](https://s0.wp.com/latex.php?latex=a_n+%5Cge+2%5E%7B+%5Csqrt%5Bk%5D%7Bn%7D+%7D&bg=ffffff&fg=333333&s=0&c=20201002)
; otherwise, we can still say ![\liminf_{n \to \infty} \frac{a_n}{2^{ \sqrt[k]{n} } } \ge 1](https://s0.wp.com/latex.php?latex=%5Climinf_%7Bn+%5Cto+%5Cinfty%7D+%5Cfrac%7Ba_n%7D%7B2%5E%7B+%5Csqrt%5Bk%5D%7Bn%7D+%7D+%7D+%5Cge+1&bg=ffffff&fg=333333&s=0&c=20201002)
.)
I find this proof the best motivated out of any of the proofs I know, especially because ultimately it reduces to simple counting. It is also constructive in the sense that a failure to satisfy the above inequality for some 
(for a strictly increasing sequence) implies that you have already hit at least prime factors.
Motivated by the above result, a positive solution to the following problem would imply a proof of Dirichlet’s theorem that totally avoids the machinery of zeta functions.
Problem: Explicitly describe a sequence growing slower than for every that is divisible, with finitely many exceptions, only by primes in a specified arithmetic progression.
Of course we already know by the strong form of Dirichlet’s theorem that this is true of the sequence consisting precisely of the numbers divisible by primes in a specified arithmetic progression. But this is a “high-complexity” sequence whereas, say, the integer values of a cyclotomic polynomial 
are “low-complexity.” In the spirit of Polymath4 what would be nice is a sequence describable in polynomial time, but as long as the proof that both of the above conditions are met is elementary it really doesn’t matter. Ideally would be some perturbation of a polynomial, so the first condition would be trivial to verify. I have no idea how one would go about constructing such a sequence.
Like this:
Like Loading...
Related
Annoying Precision 
Regarding the two-sentence proof that “The set of primes dividing the integer values of an integer polynomial is infinite.”, you need some further steps, because you need to make sure the number you get that’s coprime to $p_1…p_n$ is not a unit. (One way is to assume WLOG that the leading coeff is positive, so that $P$ evaluated at some multiple of $P(0)p_1…p_n$ is bigger than $1$).
Thanks, you’re right; we also need to make sure it’s not equal to
, and I’m not sure your leading coefficient argument works, but I edited in an argument.
[…] ещё Евклидом, но новые доказательства придумывают и сейчас. Попробуем и […]
So it’s later, and I still haven’t commented, but I have a good reason for that, namely that I was kind of wrong. But only kind of.
Still, here’s the basic idea, The “natural,” “combinatorial” way to do the hard step in Dirichlet’s proof is to say, well, the primes are pseudorandom, and then apply quadratic reciprocity, and the result falls out pretty much immediately. (I think. At least I convinced myself that this is true earlier.) The problem is that (a), the primes aren’t (AFAIK) known to be pseudorandom in any sufficiently strong sense for this argument to go through, and (b) Any such notion of pseudorandomness would very likely imply immediately that the primes are uniformly distributed in
!
I have a hunch that this isn’t just necessary, but is basically sufficient: in order to do the hard step, you have to show that the primes are (at least in a weak sense) pseudorandom. And this is certainly beyond the reach of counting arguments, and I don’t see an obvious way to do something like that without appealing to complex or Fourier analysis.
Uh, I should have interchanged “sufficient” and “necessary” there. Sorry for the confusion.
Whoops. The link in my last comment wasn’t specific enough. I was referring to Exercise 1.3.6.
That proof is due to Zagier, if I’m not mistaken. But it seems like David’s suggestion requires much more careful counting than the technique can provide, although I agree that it’s very nice. (But until someone motivates the definition of the permutation, I won’t really believe the proof.)
Yeah, it’s Zagier’s, unless we’ve both seen the same misattribution.
I suspect the permutation isn’t really that motivated; it’s entirely likely that it’s an ad-hoc construction, “built to order” for this problem — finite group theory has all sorts of things like that. I haven’t sat down and tried to do it, but I have a hunch that if you sat down and tried to construct an involution with exactly one fixed point, that definition might just be the first one to pop out.
I have some thoughts on the main post, but they’re nebulous and would just be embarrassing if I posted them now. Will likely comment later.
I wonder if the technique of this exercise from Dixon & Mortimer could be useful for David Speyer’s suggestion:
http://books.google.com/books?id=UPxu21ijF6IC&lpg=PP1&dq=dixon%20and%20mortimer&pg=PA7#v=onepage&q=&f=false
This is probably my favorite application of elementary group theory to number theory, so I think it would be really cool if it found a nice application. Unfortunately, I’ve never seen it used except for this one exercise.
Two comments, one pessimistic, one optimistic:
1 (pessimistic) Have you seen Keith Conrad’s expository note on which cases of Dirichlet’s theorem can be approached by elementary techniques? I find it very convincing. In particular, he argues that it should be very hard to distinguished primes which are 2 modulo 5 from those which are 3 modulo 5 by any elementary method. Unfortunately, Keith’s website seems to be down right now, but googling “Keith Conrad” should get it for you when it comes back up.
It is my (not very informed) belief that any proof of Dirichlet’s theorem has to involve Fourier analysis on
.
2 (optimistic) Suppose you allow me Fourier analysis on finite groups, and elementary estimates for sums, but NOT complex analysis or algebraic number theory. Then the hardest step in Dirichlet’s proof is to establish that, for any nonsquare integer D, D is a quadratic residue for at least half the primes. It is easy to establish that D is a quadratic residue infinitely often, by looking at the polynomial x^2-D, but we need the stronger result.
There are several ways to prove this. One of them is to look at the values of the polynomial x^2 – D y^2 and apply exactly the sort of argument you are using. I’ve never seen the details carried out without complex analysis and algebraic number theory, but I wouldn’t be surprised if it could be done.
The following is inspired by Fuerstenberg’s proof: We argue about periodic sets of integers. The intersection of two periodic sets is periodic, and the set of integers prime to a given p is periodic. If there were only finitely many primes the set {-1, 1} would be periodic.
I would call this a rephrasing of Furstenburg’s proof, and while it is a nice intuition it doesn’t seem to generalize readily to any special cases of Dirichlet’s theorem.