There Are Many Primes

January 8, 2015

tags: analysis, Erdos, Euclid, Factoring, Hillel Furstenberg, Idris Mercer, number theory, prime number theorem, primes, topology

by RJLipton+KWRegan

Various senses of ‘many’ from proofs of the infinitude of primes

2008 Bowen Lectures source

Hillel Furstenberg is entering his 50th years as a professor of mathematics at Hebrew University in Jerusalem. He shared the 2006-07 Wolf Prize with Stephen Smale. He has shown many connections between analysis and combinatorics. One was showing how ergodic theory can prove Endre Szemerédi’s theorem that every positive-density subset of the integers includes arbitrarily-long arithmetic progressions ${[a + bn]}$ . This led to a new multidimensional formulation with Yitzhak Katznelson, and the two later proved positive-density versions of the Hales-Jewett theorem.

Today Ken and I wish to discuss proofs of the infinitude of primes, and what they begin to say about analysis and combinatorics.

We thought of this after viewing an old StackExchange thread on different proofs of the infinitude of primes. The oldest proof is ascribed to Euclid of Alexandria around 300 BCE. The newest one mentioned there was conceived by Furstenberg as an undergraduate in 1955. The visions accompanying these proofs interest us.

The Prime Number theorem is of course a deeper statement. It was first proved by analysis, and its later proof by “elementary” methods was considered a major achievement. Something similar on a vast collaborative scale has recently happened with the density Hales-Jewett theorem. The primes do not have positive density, but Ben Green and Terence Tao still proved they have the property of Szemerédi’s theorem.

As remarked by Pete Clark at the end of his own notes on proofs of infinitely many primes, the frontier has moved to what can be proved generically about sets of density similar to that of the primes. At what density does “many” naturally arise, and what if any extra structure needs to be postulated rather than derived? Let’s try to pick up these issues from the beginning.

Euclidean Proofs

Euclid’s proof appears in his Elements, Book IX, Proposition 20. We all know it, I believe. But here is the main idea. Suppose that

$\displaystyle p_{1},\dots,p_{m}$

are distinct primes. Look at

$\displaystyle N=p_{1}p_{2} \cdots p_{m} + 1.$

Clearly ${N>1}$ and so must have some prime factor, say ${q}$ . But ${q}$ cannot be any ${p_{i}}$ and therefore is a new prime. This shows that there are an infinite number of primes.

There are many variations on this theme. Ernst Kummer in 1878 used

$\displaystyle N=p_{1}p_{2} \cdots p_{m} - 1.$

This affords some small—with all due respect—technical advantage over Euclid’s proof.

The power of this idea is manifest in that it can prove much more than just there are an infinite number of primes. It can prove special cases of Peter Dirichlet’s famous theorem on arithmetic progressions. Let ${a,b}$ be relatively prime positive numbers. Then the progression

$\displaystyle a,\ a+b,\ a+2b,\ a+3b,\ \dots,\$

contains an infinite number of primes. The theorem is so famous that it has been re-proved and discussed many times. It was even recently uploaded to the ArXiv here—in English. I guess if your paper is super important eventually it gets put there even if you are no longer around. Pretty neat.

For example, Euclid’s method can be easily modified to prove:

Theorem 1 There are infinitely many prime numbers of the form ${4n-1}$ .

Let ${p_{1},\dots,p_{m}}$ be all the primes of this form. The key is to define

$\displaystyle N = 4 \prod_{i=1}^{m}p_{i} \ -1.$

The rest of the argument is almost the same as before: no ${p_i}$ divides ${N}$ , and if all other primes were congruent to ${+1}$ mod ${4}$ , then ${N}$ as a product of them would be too. Note the trick was in defining ${N}$ . Many congruences cases can be handled by just defining the “right” integer ${N}$ , but some seem not to work. Can we prove that?

Counting Proofs

There are several of what we would call counting proofs. They show that if there are a finite number of primes, then there are not enough “names” for all integers. Clark’s notes have some examples, and the one by Paul Erdős is also in notes by John Cook. It goes like this: Consider the integers

$\displaystyle 1,\dots,x.$

Suppose that there are only ${m}$ primes. Every integer in this range can be written as ${r^{2}s}$ where ${s}$ is a square-free number. But ${r}$ must be at most ${\sqrt x}$ and clearly there are only ${2^{m}}$ possible values for ${s}$ . This shows that

$\displaystyle \sqrt{x}2^{m} \ge x.$

But this is impossible for ${x}$ large enough. Very neat.

Proofs By Higher Knowledge

One proof, by Lawrence Washington and mentioned by Clark, is just a finite computation that rests on higher knowledge:

$\displaystyle (1 + \sqrt{-5})\cdot(1 - \sqrt{-5}) = 6 = 2\cdot 3.$

But if the ring ${\mathbb{Z}}$ had only finitely many prime ideals then every extension such as ${\mathbb{Z}[\sqrt{-5}]}$ would be a unique factorization domain—contradiction, Q.E.D.

Well not so fast. The “then” part rests on theory about number fields and integer closures and principal ideal domains proved by Richard Dedekind and others.

A common feature of all these proofs is that they rest on properties of factorization that are regarded as intuitive. You have a number ${N}$ where adding or subtracting 1 (or something else) has destroyed the previous product structure, so you have to make inferences about its unknown factors de novo. Is this somehow cheating? Washington’s proof has no “ ${N}$ ” but it would take much care to convince us that the Dedekind theory wasn’t somehow using the infinitude of primes to begin with.

What strikes us as remarkable about Furstenberg’s proof next is that it sublimates the notion of factoring into something else. Arithmetical progressions involve common factors, but those factors are known.

Furstenberg’s Topological Proof

Clark’s notes reproduce Furstenberg’s one-paragraph proof as published in the American Mathematical Monthly; we elide one sentence that made a side remark:

“In this note we would like to offer an elementary ‘topological’ proof of the infinitude of the prime numbers. We introduce a topology into the space of integers ${S}$ , by using the arithmetic progressions (from ${-\infty}$ to ${+\infty}$ ) as a basis. It is not difficult to verify that this actually yields a topological space. […] Each arithmetic progression is closed as well as open, since its complement is the union of other arithmetic progressions (having the same difference). As a result the union of any finite number of arithmetic progressions is closed. Consider now the set ${A = \cup A_p}$ where ${A_p}$ consists of all multiples of ${p}$ , and ${p}$ runs though the set of primes ${\geq 2}$ . The only numbers not belonging to ${A}$ are ${-1}$ and ${1}$ , and since the set ${\{-1, 1\}}$ is clearly not an open set, ${A}$ cannot be closed. Hence ${A}$ is not a finite union of closed sets which proves that there are an infinity of primes.”

This is so compact as to make one wonder about “cheating.” However, as noted in an April 2009 Monthly article by Idris Mercer, one can dispense with topological language and ground the proof even more simply in set theory.

Mercer’s Set-Theory Rendition

Let ${U}$ be an infinite universe and ${\cal A}$ a family of infinite subsets of ${U}$ such that ${{\cal A}' = {\cal A} \cup \{\emptyset\}}$ is closed under intersection. Also let us suppose ${\cal A}$ is such that for every ${A \in {\cal A}}$ , the set ${U \setminus A}$ is a union of members of ${\cal A}$ . (We will in fact not care whether this union is finite, though it is when ${\cal A}$ is the collection of all arithmetical progressions.)

Fix a nonempty finite subset ${F}$ of ${U}$ . Then, for any ${A_{1},\dots,A_{m}}$ in the family ${\cal A}$ ,

$\displaystyle A_{1} \cup \cdots \cup A_{m} = U \setminus F$

is impossible. For if it were possible, then by taking complements, we would have

$\displaystyle {\bar A_{1}} \cap \dots \cap {\bar A_{m}} = F.$

By hypothesis, each ${{\bar A_{k}}}$ is a union of sets from the family. By the distributive law of ${\cup}$ and ${\cap}$ , we may bring the entire union to the outside, getting

$\displaystyle F = \bigcup_{\lambda} A_\lambda,\quad\mbox{where}\quad A_{\lambda} = A_{\lambda,1} \cap \cdots \cap A_{\lambda,m},\mbox{ each } A_{\lambda,j} \in {\cal A.}$

By the closure hypothesis on ${\cal A}$ , each ${A_{\lambda}}$ is either ${\emptyset}$ or infinite. Hence the whole union cannot be finite, which is a contradiction.

Finally, if there were finitely many primes ${p_1,\dots,p_m}$ , then we would have such an impossible representation with ${F = \{-1,1\}}$ and ${A_j = [0 + p_j n]}$ . ${\Box}$

How elementary is this? Although distributing an infinite union gets into aspects of set theory that are formally more advanced, in fact we don’t need it since ${\bar{A_{j}}}$ equals the finite union ${[1 + p_j n] \cup \cdots \cup [(p_j - 1) + p_j n]}$ . That the intersection of two arithmetical progressions ${[a + bn]}$ and ${[c + dn]}$ is either empty or infinite needs only the finitistic reasoning that if ${x}$ belongs to the intersection then so does ${x + bd}$ (not to mention ${x + \text{lcm}(b,d)}$ ). Hence the lone open-ended inference seems to be that ${F}$ is the complement of the union of the ${A_j}$ . This strikes us as involving only the notion of “prime,” in a way separate from the other uses of “factoring.”

Open Problems

Does our interpretation of Furstenberg’s proof as “more elementary” hold water? Is it a valid hint as to how concrete number-theoretic properties that matter to complexity might be obtained from a (slowly) “rising sea” of knowledge at the juncture of set theory, topology, and abstract algebra?

Can you find some other proofs? On the “silly” or “cheating” side, having finitely many primes would give a polynomial time algorithm for factoring (actually linear time), contradicting the usual cryptography assumption that factoring is hard. We wish there were a more serious connection that something known in complexity theory would be false—the trouble with the above proof is that the cryptography assumption is unproved.

13 Comments leave one →

domotorp permalink

January 9, 2015 3:14 am

My favorite proof is the one with Kolmogorov complexity. You can find it e.g., in section 2 here: http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf

Reply
- Craig permalink
  
  January 9, 2015 11:46 am
  
  I first saw that proof here: http://arxiv.org/pdf/math/0404335.pdf
  
  Reply
  - domotorp permalink
    
    January 11, 2015 2:53 am
    
    It is also in the Li-Vitanyi book, whose first edition is older (though I have only seen the third edition).
unknot permalink

January 9, 2015 12:06 pm

Here’s another variation on Furstenburg’s proof which has always been much more intuitive for me: Call a set $S \subseteq \mathbb Z$ periodic if there is some $n > 0$ such that $S = \{s+n: s \in S\}$ . Clearly, periodic sets are closed under finite union and complement. As in Furstenburg’s proof, consider $A = \cup A_p$ where $A_p$ consists of all multiples of $p$ and $p$ runs through the set of primes. Each $A_p$ is periodic, so if there are only finitely many primes then $A$ is periodic. But $\mathbb Z \setminus A = \{-1, 1\}$ is finite and therefore not periodic, so $A$ is not periodic. Thus there are infinitely many primes.

The periodic sets used in this proof are exactly the clopen sets in Furstenburg’s topology. Rewriting this proof by replacing periodic sets with clopen sets gives something almost identical to Furstenburg’s proof. On the other hand, making this proof more constructive by tracking the periods of periodic sets basically gives you Euclid’s proof: If there are finitely many primes, then $A$ is periodic with period $\prod p$ , so because $1 \not\in A$ it follows that $1 + \prod p \not\in A$ , contradiction.

Reply
Martin permalink

January 9, 2015 3:14 pm

My preferred proof(s) for the infinitude of primes are to exhibit a set of pairwise-coprime numbers that is either infinite (say, Sylvester’s series or the Mersenne numbers) or sufficiently large that a finite set of primes could not factor all of them. Where would these proofs fit into your taxonomy?

Reply
John Sidles permalink

January 9, 2015 3:21 pm

First importantly, please let me express appreciation and thanks for this absolutely wonderful GLL essay.

This essay inspires the reader to rank theorems ((informally) by their number of essentially different proofs. As this essay so ably documents, the infinitude of primes has an exceedingly large proof-rank.

In contrast, Fermat’s Theorem has a much lower proof-rank … as low as unity, perhaps? Perhaps the Poincare Conjecture too?

And complexity theory teaches too (via Chaitin’s theorems) there exists is an infinity of mathematical statements that are true for purely heuristic reasons, and hence have zero proof-rank … like Goldbach conjectures perhaps?

In this vein, Terry Tao’s recent (wonderfully interesting) weblog post “Probabilistic models and heuristics for the primes” can be read as a survey of true statements in number theory that (at least some of which plausibly) have proof-rank zero. Which statements, exactly? That is a very hard decision problem!

It is natural to wonder how whether mathematicians are in danger of exhausting the set of large proof-rank theorems. It’s not pleasant to contemplate a world whose most cherished open problems all have low proof-rank.

From this perspective, we can all appreciate — young researchers especially — what category theorists and geometers have appreciated for the past four decades and more: what’s marvelous (for young researchers especially) about Grothendieck’s “rising tide” style of mathematics is that it generates, not “hard-shelled” theorems of low proof-rank, but “soft-shelled” theorems of high proof-rank.

Conclusion It is reasonable to hope that Grothendieck’s “rising tide” of mathematical understanding is associated to a rising tide of proof diversity.

Reply
Idris Mercer permalink

January 10, 2015 3:47 pm

It’s nice to see my name. Idris Mercer

Reply
Serge permalink

January 12, 2015 11:31 am

Have you noticed that the hard problems are generally hard in two ways? Not only do they possess at most one solution, but whenever their solution gets found it happens to be quite complex. For example, the NP-complete problems have essentially one known solution, and it is exponential. On the other hand the known P problems often have many different solutions, whether polynomial or exponential.

Also, there’s only one known solution to the four-color theorem, to Fermat’s Last Theorem, to the classification of finite groups… and they’re all very long proofs! Meanwhile, there are many short proofs of the infinitude of primes, of the fundamental theorem of algebra, of the quadratic reciprocity law and so on. Of course, that doesn’t rule out there being long proofs as well, together with the short ones.

Let’s say that a problem which appears to be easy is one whose solution space is dense, and that this increases the probability of finding an efficient solution to it…

Reply
johne permalink

January 24, 2015 5:22 pm

Chaitin has an algorithmic information theory proof that is related to the smallest interesting number “paradox” that is equivalent to there being an infinite number of primes.

The more interesting thing to note is Godel numbering of axioms and inference can be based prime numbers and relatively prime rules of inference (though this may not be necessary). One can then show that a finite number of axioms and rules of inference are insufficient to capture all theorems of mathematics since multiplication of the Godel numbers and adding one requires a new prime. (I vaguely remember reading an argument like this back in childhood.) I think this leads to a more beautiful argument as to why the halting problem is true than one based on the diagonal argument that Turing originally used.

Reply
Emi permalink

January 29, 2015 3:48 am

Reblogged this on Pathological Handwaving.

Reply
Jhon Hard permalink

November 22, 2015 8:18 am

All prime number is in the interval:

[30a + (p)] and [42a + (p_{1}]

p = (11;17;23;29)

p_{1} = (13;19;31;37;43)

published in: http://www.hrpub.org/journals/jour_info.php?id=24 Vol 1 (3) 2013

Reply
Jhon Hard permalink

November 25, 2015 12:09 pm

All twin prime is.

always that: [7a + (1;2;3;4:5:6)] \neq 5n

Then:

[5 + 6(7a + (1;2;3;4;5;6)] = p_{n}

and, All [[5 + 6[7a +(1;2;3;4:5:6)]] + 2] / (3;5;7) \neq Z ] = p_{n+2}

Reply
knsam permalink

January 11, 2016 9:42 pm

There is a 1988 theorem of Ram Murty discussing necessary and sufficient criterion for the existence of an Euclidean proof of infinitude of primes in a certain AP. See this later report: http://projecteuclid.org/euclid.facm/1229442627.

Reply

	Héctor Garcia-Molina… on Héctor Garcia-Molina, 1…
	Héctor Garcia-Molina… on Héctor Garcia-Molina, 1…
	Héctor Garcia-Molina… on Lint For Math
	New top story on Hac… on Héctor Garcia-Molina, 1…
	New top story on Hac… on Héctor Garcia-Molina, 1…
	Top story HACKER NEW… on Héctor Garcia-Molina, 1…
	New top story on Hac… on Héctor Garcia-Molina, 1…
	New top story on Hac… on Héctor Garcia-Molina, 1…
	Héctor Garcia-Molina… on Héctor Garcia-Molina, 1…
	New top story on Hac… on Héctor Garcia-Molina, 1…
	New top story on Hac… on Héctor Garcia-Molina, 1…
	New top story on Hac… on Héctor Garcia-Molina, 1…
	Héctor Garcia… on Sorting Out Chess Endgame…
	Héctor Garcia… on Who’s Afraid Of Arrow…
	Héctor Garcia… on Lint For Math

a personal view of the theory of computation

There Are Many Primes

Euclidean Proofs

Counting Proofs

Proofs By Higher Knowledge

Furstenberg’s Topological Proof

Mercer’s Set-Theory Rendition

Open Problems

Leave a Reply to Craig Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

There Are Many Primes

Euclidean Proofs

Counting Proofs

Proofs By Higher Knowledge

Furstenberg’s Topological Proof

Mercer’s Set-Theory Rendition

Open Problems

Share this:

Like this:

Related

Leave a Reply to Craig Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter