Can they inform computational complexity theory?

Bill Gasarch and Christian Elsholtz both like primes and jokes and graphs and ways of sharing baked goods. Bill is a Professor of Computer Science at the University of Maryland; Elsholtz is an Associate Professor of Mathematics at T.U. Graz in Austria. They recently independently came up with a new proof of the infinitude of the primes.

Composite crop of src1, src2

Today we discuss reasons for being interested in such new proofs.

Bill’s website features his co-written book on the problem of equitably dividing muffins in ways that avoid cutting small pieces, which we covered here. Elsholtz’s website reveals that the final oral component of his Habilitation—the successor to PhD in Germany—was on “fair division of sandwiches and cakes.” We trust that his examiners did not go hungry.

Bill co-writes the blog blog Computational Complexity, which was started by Lance Fortnow in 2002. He posted last week about his new paper titled, “Fermat’s Last Theorem, Schur’s Theorem (in Ramsey Theory), and the Infinitude of the Primes.” Elsholtz’s paper is titled, “Fermat’s Last Theorem Implies Euclid’s Infinitude of Primes” and is discussed in this sprightly interview.

New Proofs

The issue is: How many ways can we prove that there are an infinite number of primes? We have known this fact since Euclid proved it in his Elements—a few years ago in 300 BCE.

There are now many proofs known. A relatively recent cool proof came from Filip Saidak.

UNC Greensboro homepage

It can be viewed in PDF here. Briefly:

Let be the number of distinct primes that divide . A key property is: Let be a positive integer. Since and are consecutive integers, they must be coprime, and hence the number must have . This shows that must be unbounded.

The site Brilliant.org maintains a wiki of proofs. There is also a nice 2013 survey by Lindsey Harrison.

Bill’s paper begins with reference to two other recent proofs: a note by Levent Alpoge and a paper by Andrew Granville. Working separately, they gave novel proofs that the primes are infinite that use Ramsey Theory. Bill’s abstract continues:

In particular, they use Van der Waerden’s Theorem and some number theory. We prove the primes are infinite using an easier theorem from Ramsey Theory, namely Schur’s Theorem, and some number theory.

Alpoge’s paper has had several followups, including a survey by Granville titled, “A panoply of proofs that there are infinitely many primes.” But where does Schur come in?

A Schur Way To Do It

Issai Schur was a giant in Berlin and Bonn for the first four decades of the 20th century. We once did a post titled on, why is everything named after Carl Gauss? Schur is no slouch in that department:

Wikipedia source

There’s more: the highlighted link on “Schur’s theorem” goes to a page of several theorems named for Schur, hence Bill felt the need to disambiguate the one in Ramsey theory. This is simple to state:

Theorem 1 For every partition of the positive integers into finitely many subsets, at least one subset contains integers such that .

The “some number theory” used in both proofs involves cases of Fermat’s Last Theorem (FLT) for particular . But wait—aren’t Schur’s Theorem and cases of FLT stronger theorems than the infinitude of primes? The relevant facts are:

• Schur’s Theorem follows from Ramsey’s Theorem in a way that employs no multiplicative properties of the integers. Namely, let be the number of subsets. Ramsey gives a number such that any -coloring of the edges of the complete graph of on nodes has a monochrome triangle. “Color” each edge of by the label of the subset belongs to. The triangle gives numbers , , and in the same subset, and .
• As remarked directly by Elsholtz, the cases , , and of FLT do not rely on having infinitely many primes.
• Known proofs of the full FLT use the infinitude of primes. This leads to open problems about which other cases, besides multiples of and other known , have proofs that do not require the infinitude of primes.

Their Theorem and Proof

An informal statement of their theorem is:

Theorem 2 In any mathematical structure that models certain simple properties of the integers, if any case of FLT holds then the structure has infinitely many irreducible elements.

For an integral domain, that is equivalent to having infinitely many primes. The main property needed, which Bill calls “atomic,” is that all nonzero elements can be formed by multiplying together powers of irreducible elements (and a unit like if needed), that is,

with each . Such a representation need not be unique like it is in , and the concept does not presuppose having infinitely many irreducibles. Our informal rendition of their proof is lighter on notation but still complete.

Proof: Given , suppose there are only finitely many irreducibles . Every integer can be decomposed as an -th power times a number that has no -th power as a divisor. By the “atomic” hypothesis, the part can always be written as a product of powers of the . Those powers must all be less than . That leaves possible patterns for , and the integers produced by each pattern becomes the partition into subsets. Schur then gives a subset containing a triple . This means

But since , , and are all -th powers, this contradicts the case of FLT.

Both papers have much additional content. Bill’s focuses on the relationships of axioms and logical models resembling the integers. Elsholtz’s has more number theory. This speaks to the lineage of their PhD advisors. Bill was co-advised by Harry Lewis, whom we mentioned recently, and Albert Meyer, a top theorist known for deep connections between machine computations and arithmetical structures. Elsholtz’s PhD advisor, Wolfgang Schwarz, was a student of Carl Siegel, a giant of analytic number theory, whose work on the Riemann Hypothesis has been in recent news that we have not yet had time to appraise.

More New Proofs?

That their theorem shows certain other structures besides the integers must have infinitely many irreducibles is a further reason to care about it. To quote Elsholtz, its flip side informs what must happen in “worlds with only finitely many primes.” In complexity theory we also consider different “worlds,” some in which and other important unknown assertions go one way, others the opposite. We wonder if there is any meeting of worlds to eb found here.

In particular, we wonder: are there are proofs of the infinitude of primes that use complexity theory rather than number theory? The best we can do is unfortunately weak. We can prove for example:

Theorem: If RSA is not breakable in linear time, then the primes are infinite.

This shows that RSA being hard to crack implies that there must be infinitely many primes. But this is a “swiz” in that the notion of linear time is asymptotic in a way that makes this mostly presuppose what it purports to prove.

Wait a minute. We can do a little better. Here is a proof of the infinitude of primes that is more concrete in complexity terms. Look at the numbers that have at most -bit binary representation—denote them by . The relevant abstract properties we need, besides “atomic,” are that all members of are and there are exponentially many of them. Suppose that there are at most primes: . The members of have representations

This shows that each is at most . (Or, if we have an abstract structure in which is allowed, there must be a minimum magnitude , and then each is at most times , for which the argument easily adjusts.) So the cardinality of can be at most

This means that must be unbounded, since has exponential size. This actually proves a stronger lower bound on the density of primes than Euclid’s proof and some of the others.

In fact, this is much the same as Axel Thue’s proof, and the “proof by information theory” on the Brilliant.org wiki linked above.

Open Problems

Can we get other complexity based proofs? Note it is interesting that the above proof uses the concept of binary numbers to get a proof. That concept was discovered long after Euclid, in the 16th and 17th centuries by Thomas Harriot, Juan Lobkowitz, and Gottfried Leibniz among Europeans.

Schur’s Theorem has a version for Pythagorean triples rather than sums. We covered the prodigious instances of SAT that accompany the search for exact bounds on cases of these theorems.