Infinitely many primes via generating functions

A few years ago I discovered an amusing proof of Euclid’s theorem that there are infinitely many primes which I thought I’d record here for posterity. (I subsequently learned that a similar argument appears in this paper by Paul Pollack.)

To motivate the proof, and illustrate its working in an (admittedly silly) special case, suppose that there were just two prime numbers, called p and q. Then by the fundamental theorem of arithmetic (i.e., unique factorization into primes) we would have the following identity between generating functions:

$\sum_{n=2}^\infty z^n = \sum_{k=1}^\infty z^{kp} + \sum_{k=1}^\infty z^{kq} - \sum_{k=1}^\infty z^{kpq}.$

Indeed, there is precisely one term $z^n$ for each integer $n \geq 2$ on the left-hand side, and the same is true for the right-hand side (consider separately the cases where $p \mid n$ but $q \nmid n$ , $q \mid n$ but $p \nmid n$ , and $pq \mid n$ ). Using the formula for the sum of a geometric series, we can rewrite our formula as an identity between complex-analytic functions valid on the open unit disc ${\mathbb D} = \{z \in {\mathbb C} \; : \; |z|<1 \}$ :

$\frac{z^2}{1-z} = \frac{z^p}{1-z^p} + \frac{z^q}{1-z^q} - \frac{z^{pq}}{1-z^{pq}}.$

This is impossible, however, as we see by letting $z$ approach a primitive $pq^{\rm th}$ root of unity, since each term stays bounded except for $\frac{z^{pq}}{1-z^{pq}}$ , which tends to infinity.

This argument readily generalizes to any number of prime factors:

Theorem (Euclid): There are infinitely many prime numbers.

Proof: Suppose there were just finitely many primes $p_1,\ldots,p_k$ . Then by the fundamental theorem of arithmetic and the principle of inclusion-exclusion, we would have the following identity between analytic functions on ${\mathbb D}$ :

$\frac{z^2}{1-z} = z^{p_1} / (1 - z^{p_1}) + \cdots + z^{p_k} / (1 - z^{p_k}) - z^{p_1 p_2} / (1 - z^{p_1 p_2}) - \cdots$

$\cdots + (-1)^{k+1} z^{p_1 p_2 ... p_k} / (1 - z^{p_1 p_2 ... p_k}).$

If we now let $N=p_1 p_2 ... p_k$ and let $\zeta= e^{2\pi i / N}$ be a primitive $N^{\rm th}$ root of unity, the final term on the right-hand side goes to infinity as $z$ approaches $\zeta$ , while all the other terms approach a finite limit, a contradiction. Q.E.D.

I think there may be some pedagogical merit to this proof as an illustration of the use of generating functions, the principle of inclusion-exclusion, and summing geometric series. However, as with any “new” approach to a well-known theorem with many known proofs, one should also ask whether the method itself is of any general mathematical interest. I will make two quick “sales pitches” for the utility of this approach (and if you’re not convinced, that’s fine — I’m not in this for the money anyway).

First of all (and this was how I discovered the argument in the first place), a similar method yields a well-known theorem about “covering congruences” which as far as I know does not (as opposed to Euclid’s theorem) have a substantially simpler proof. The theorem is the following:

Theorem (Mirsky-Newman, formerly a conjecture of Erdös): If the positive integers are partitioned into a finite number of arithmetic progressions $S_1,\ldots,S_k$ with $S_i = \{ a_i, a_i + d_i, a_i + 2d_i, \ldots, \}$ and $d_i \geq 2$ for all $i$ , then the maximum of $d_1,\ldots,d_k$ must occur at least twice.

Proof: Since $S_1,\ldots,S_k$ partitions the set of positive integers, we have $\sum_{n=1}^\infty z^n = \sum_{n \in S_1} z^n + \cdots + \sum_{n \in S_k} z^n.$ Thus we have the following relation between analytic functions on ${\mathbb D}$ : $\frac{z}{1-z} = \frac{z^{a_1}}{1-z^{d_1}} + \cdots + \frac{z^{a_k}}{1-z^{d_k}}.$

Suppose that $d_j = \max \{ d_1,\ldots,d_k \} > d_i$ for $i\neq j$ and let $\zeta = e^{2\pi i / d_j}$ be a primitive $d_j^{\rm th}$ root of unity. Then as $z$ approaches $\zeta$ , the term $\frac{z^{a_j}}{1-z^{d_j}}$ approaches infinity while all other terms approach a finite limit, a contradiction. Q.E.D.

A similar proof strategy can be used to prove the following generalization of Euclid’s theorem. For the statement, recall that the Möbius function $\mu$ is defined by $\mu(n)=(-1)^k$ if $n$ is the product of $k$ distinct primes (so in particular $\mu(1)=1$ ) and $\mu(n)=0$ if $n$ is divisible by the square of a prime. Given a function $f : {\mathbb N} \to {\mathbb C}$ , define its Möbius transform to be $\check{f} := \sum_{d \mid n} \mu(n/d) f(d).$ The Möbius inversion formula is the assertion that the inverse to the Möbius transform is given by the Dirichlet transform $\hat{f} := \sum_{d \mid n} f(d).$

Theorem (Pollack): For a nonzero function $f : {\mathbb N} \to {\mathbb C}$ , the support of $f$ and $\check{f}$ cannot both be finite.

Euclid’s theorem follows immediately from the special case where $f$ is the function defined by $f(1)=1$ and $f(n)=0$ for $n\geq 2$ , whose Möbius transform $\check{f}$ is equal to $\mu$ .

Sketch of proof (see Pollack’s paper cited above for additional details): Suppose for the sake of contradiction that both $f$ and $\check{f}$ have finite support. Then $F(z) := \sum_{n=1}^\infty f(n)z^n$ is a polynomial. On the other hand, for $z \in {\mathbb D}$ the Möbius inversion formula tells us that

$F(z) = \sum_{n=1}^\infty \left( \sum_{d \mid n} \check{f}(d) \right) z^n = \sum_{d=1}^\infty \check{f}(d) \frac{z^d}{1-z^d}.$

Since $f$ is not identically zero, neither is $\check{f}$ (by Möbius inversion). Let $N$ be the largest positive integer such that $\check{f}(N) \neq 0$ and let $\zeta = e^{2\pi i / N}$ be a primitive $N^{\rm th}$ root of unity. Then as $z$ approaches $\zeta$ , the right-hand size of the above identity approaches infinity while the left-hand side approaches a finite limit, a contradiction. Q.E.D.

Note that Pollack’s theorem bears a formal resemblance to the Heisenberg uncertainty principle from quantum mechanics, which in its simplest mathematical form says that a nonzero function and its Fourier transform cannot both be compactly supported.

Concluding observations:

Pollack’s theorem is generalized in this paper by Pollack and Sanna.
For more references on covering congruences and the Mirsky-Newman theorem, see for example this Wikipedia page.
For compilations of many different known proofs of Euclid’s theorem, see for example this survey by Andrew Granville.

4 thoughts on “Infinitely many primes via generating functions”

hc says:

August 16, 2019 at 3:17 am

Can one transform this kind of proof back to zeta function in some way – i.e. is this fundamentally a different proof?

For example for infinitude of primes, looking at residue at $z = 1$ recovers one classical proof by noting that $\prod_p \left(1 – \frac{1}{p}\right) \neq 0$ if number of primes is finite.

Thanks!

- Matt Baker says:
  
  August 16, 2019 at 10:42 am
  
  That’s a good question. This doesn’t quite answer your question, but Andrew Granville did point out the following:
  
  “If you write m = p_1..p_k then your identity in the proof of Euclid’s Theorem is
  
  sum_{d|m} mu(d)z^d/(1-z^d} = z
  If we multiply through by 1-z^m, and let z–>1 then we get
  phi(m)=sum_{d|m} mu(d) m/d = 0
  
  This is another way to say that the number of residue classes coprime to m must be 0 if m is divisible by all of the primes, which is obvious since it must have a factor in common with every integer in {m+1,…2m}.”
  
  - hc says:
    
    August 16, 2019 at 4:30 pm
    
    Just a continuation of what I said earlier, unfortunately I can’t tell if this is wishful thinking since this is far outside of the realm of things I understand.
    
    In quantum groups, people work with $q$-series (which is thought of as q-deformation of universal enveloping algebra of some groups). If we replace $z$ above by $q$, looking at limiting behavior as $q \to 1$ or another root of unity (like you did) seems to be something they do a lot. I wonder if there is a quantum-group-interpretation of what’s happening here.
  - Matt Baker says:
    
    August 16, 2019 at 7:40 pm
    
    I know nothing about this, unfortunately!

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Infinitely many primes via generating functions

4 thoughts on “Infinitely many primes via generating functions”

Leave a Reply Cancel reply

Share this:

Like this:

Related

4 thoughts on “Infinitely many primes via generating functions”

Leave a Reply Cancel reply