Sometimes my instinct is to scoff at the practical value of asymptotic existence results like this, but there's a quote in the article that provides a good counterpoint:
Keevash’s result will shift the mindset of mathematicians who are trying to find designs, Colbourn said. “Before, it wasn’t clear whether the focus should be on constructing designs or proving they don’t exist,” he said. “Now at least we know the effort should focus on constructing them.”
I only glanced at the paper, but perhaps this is analogous to Shannon's original proof of existence of codes meeting channel capacity -- which was also a non-constructive, asymptotic result.
That pointed the way for people to start working out channel codes, and after only a few decades of work (say, 1948 to 1993), turbo codes were discovered.
Non-constructive existence proofs are critical in random graph theory, and that in turn is producing all sorts of useful results about what's possible, what's not possible, and what might be possible but it's likely to be hard.
A specific example, I'm working with some people on producing instances of G3C that may lead to a new form of PKC that is expected to be securely based on a known NPC problem. Non- constructive asymptotic existence proofs are critical to proving these instances are difficult.
When doing math proof exercises as an undergrad I found problems of the form "Prove X" or "Disprove X" to be much easier than "Prove or disprove X" despite no noticeable difference in the difficulty of understanding the proof once constructed. I felt that prove/disprove was significantly more than twice as hard, actually. I thought I could trick myself into making it between 1 and 2 times as hard by attempting to force myself to believe the problem was one form or the other for set periods of time, and that did seem to help some, but not nearly to the extent I had hoped.
At undergrad, a successful technique is to assume X exists and try to construct it. As you do so, you either find one or reach a contradiction to every possible class of structure.
Nonconstructive proofs of existence in rare, outside of logic classes. Most branches of undergrad math aren't interested in mere existence
It's a useful technique not just for undergraduates. Here are two famous computer science examples.
* Dana Scott discovered the lattice based model of the λ-calculus while trying to prove that no set theoretic models exist. This put functional programming on the map.
* Volker Strassen found his fast matrix multiplication while trying to show that the traditional O(n^3) is optimal. This might have been the first or one of the first non-trivial and unexpected innovations that came from the then new field of computational complexity.
There are plenty of times in math classes where I've been assured that "Theorem 1 guarantees that there exists a unique solution...", but where this solution is in no sense easily known.
As an example, a maximizer of some convex function over a convex set. Sure, it exists, but constructing it is another matter!
As another example, solutions to differential equations of a given form. The form guarantees a solution exists, but the solution may difficult to pin down.
One more example: Borel sets.
Hmm, now that I'm going: the square root of 2. It is a number that satisfies a simple property, but constructing it is considerably more difficult.
The famous proof that the primes are infinite is a nonconstructive existence proof. And weirdly, it proceeds entirely by trying to construct a new prime. It just fails to do so (well, sort of) while still invalidating the idea of an upper bound.
It is constructive, because it relies on the fact that p_1p_2...p_n + 1 has a prime factor, and to prove this you repeatedly split it into factors until you reach a prime. And so when you consider all the parts of the proof you find that you have in fact constructed another prime.
I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.
There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n.
It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.
1. Assume there is no prime number larger than p_n.
2. Compute the product of all the prime numbers less than or equal to p_n, plus one. Call this number c.
3. By construction, no prime number less than or equal to p_n divides c.
4. But all integers greater than one have one or more prime factors. (This is not proven.)
5. Therefore, since c has no prime factors less than or equal to p_n, it must have one which is not less than or equal to p_n, or in other words c must have a prime factor greater than p_n, which contradicts step (1).
Viewing https://en.wikipedia.org/wiki/Euclid%27s_theorem, I see that Euclid's original proof doesn't involve using all the primes within a certain range ("your collection so far need not contain all primes so far"), so what you've said here does apply to it. However, I also read:
> Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes.
So I don't feel too bad about referring to the proof I gave above as "the famous proof". I didn't call it "the proof that appears in Euclid's Elements".
Since this result is by contradiction, there are several different points where you could choose to observe the contradiction. But you can certainly do it before you actually produce a new prime.
In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails.
The point is that the proof is fairly robust, and yet stating it all completely correctly is actually quite hard. Here is a more correct version:
We know there are at least some primes. For example, 3 is prime. Take any non-empty finite collection of primes. Multiply them all together, and add 1. The result may not be prime, but it is expressible as the product of primes, and hence there is at least one prime that divides it. That prime cannot be one of the primes in our finite collection, and hence any finite collection of primes does not contain them all.
The classic counter-examples used when there are proof with holes are these:
Consider the set of primes { 3, 5 }. Multiply them together and add 1, and all the primes that divide the result are less than the primes you have.
Starting with 2 and then repeatedly getting a new prime by multipying and adding 1 we get 3, then 7, then 43, but 2.3.7.43+1 = 13.139.
Finally, taking known successive primes we get "failure" at: 2.3.5.7.11.13+1 = 59.509
And as an addendum, I've heard this before, but a few days ago Carl Pomerance told me of a joke he heard from Henrik Lenstra. Here's a proof that there are infinitely many composites:
4 is composite, 6 is composite. Suppose by way of contradiction that the set of all composites is finite. Multiply them all together and don't add 1! That's a new composite, hence contradiction. QED.
> In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails.
Why? We know that the largest prime is p_n, and the numbers from 1 to p_n are finite. Each of them might or might not be prime. It's perfectly legitimate to say "multiply together all the primes between 1 and p_n" without knowing which numbers in particular those happen to be. Since I don't know which numbers I multiplied together, I won't know the numeric value of the number produced in step 3, but I certainly do know that by construction, it is not divisible by any prime <= p_n. (Technically, I know this conditional on the lemma "all prime numbers are greater than one.)
The proof I've given doesn't deal with arbitrary sets of primes at all. There is no point in the proof at which you could multiply 3 and 5 and then add one to produce 16. If 5 is the largest prime, the number (implicitly) computed in step 3 is 2⋅3⋅5 + 1 = 31. Iterating from 2 (but why?), you'd compute 3, then 7, then 211, and then something large. And 2⋅3⋅5⋅7⋅11⋅13 + 1 = 30031 = 59⋅509 isn't a counterexample to the proof I've given, because the conclusion is explicitly "the number constructed must have a prime factor greater than p_n", and p_n in this example is 13. 59 and 509 are both greater than 13.
Where does my proof fail? How is yours more correct? You still seem to think that I'm misstating the proof found in the Elements. You can prove things more than one way.
I really don't have time for a complete point-by-point here, I really don't. The proof as you've stated it here is really, really close to being complete and correct. Mostly the problems are where you haven't said something that is, in fact, true, reasonable, and easy to add. The point being that you haven't actually said it.
Step 1 is the specific example. You say:
1. Assume there is no prime number larger than p_n.
But you haven't said that p_1 through p_n are all the primes up to and including p_n. A set that satisfies your step 1 is the set { 7 }. I can read your step 1 and say: OK, I'll assume that { 7 } is the set of all primes.
Then you say:
2. Compute the product of all the prime
numbers less than or equal to p_n,
plus one. Call this number c.
The natural reading of this is to think you're saying that p_1, p_2, p_3, ..., p_n are the primes up to p_n. If not, why have you called it p_n and not simply called it P. Doing so makes it clear that in step 2 you are taking all the primes up to some limit, rather than taking all the primes in a collection of size n, with p_n the maximum element.
This is exacerbated by the fact that the usual proof does start with a specific collection, which is at odds with what you seem to be saying.
You say:
> Since I don't know which numbers
> I multiplied together, I won't
> know the numeric value of the
> number produced in step 3, but
> I certainly do know that by
> construction, it is not divisible
> by any prime <= p_n.
Yes, but only if you use this unexpected interpretation that p_n is simply a limit, and not the largest/last element of an arbitrary set of primes.
So the proof you've given is not exactly the usual proof, it's subtly different. The notation you use brings to mind the usual proof, and creates a confusion about what you're actually saying. The objective of the proof I gave is to avoid those potential mis-interpretations.
Does that make it clear? Perhaps it's important to add that I'm not saying your proof is actually wrong, I'm just saying that if an undergrad produced it I'd be asking for clarification on a few points to see if they really understood it, or if they'd just memorised it and perhaps missed a point, or muddled two formulations.
It is a common simplification of Euclid's proof to convert it to a proof by contradiction. In fact, I believe I was taught this version of the proof in an early undergraduate math class. This version is not constructive, actually the first example of the wikipedia article on constructive proofs points this out:
Euclid's proof is constructive. But a common way of simplifying Euclid's proof postulates that, contrary to the assertion in the theorem, there are only a finite number of them, in which case there is a largest one, denoted n. Then consider the number n! + 1 (1 + the product of the first n numbers). Either this number is prime, or all of its prime factors are greater than n. Without establishing a specific prime number, this proves that one exists that is greater than n, contrary to the original postulate.
As panic pointed out, the nonconstructive proof you outline is valid, but the constructive "proof" is fallacious. You could modify the standard proof to construct a new prime, but that wouldn't be the famous proof. The modification amounts to doing a bunch of extra work after you've already finished the proof.
It's still constructive, you just have to change a word. That you insist on dismissing the method entirely baffles me.
I'm sorry that I didn't remember it off the top of my head.
Factoring is not a huge burden compared to the earlier steps, and also not necessary a lot of the time, especially if your goal is to keep feeding the number back into the system to create numbers made out of new primes.
> Factoring is not a huge burden compared to the earlier steps
I agree with this. My point is just that it's not required for the proof, and usually isn't included -- so the proof is not constructive. You can extend it to be constructive in a very straightforward manner, but you don't have to and you usually don't.
The reason I'm calling this a nonconstructive proof is by analogy to the following proof, often given as an example of a nonconstructive proof:
Theorem: it is possible for an irrational number raised to an irrational power to result in a rational number.
0. For typographic convenience, let r = sqrt(2). r is known to be irrational.
1. r^r might or might not be rational -- who knows?
2a. If r^r is rational, the theorem is proved.
2b. If r^r is not rational, then (r^r)^r is an irrational number raised to an irrational power, but (r^r)^r = r^(r⋅r) = r^2 = 2, which is rational.
3. Therefore, there exists some pair a,b for which the following is true: (I) a and b are both irrational; (II) a^b is rational.
I don't see any way to consider this proof nonconstructive while considering the proof of the inifinitude of the primes that I've described as constructive. Do you?
All of its prime factors are in fact new primes though - the constructive proof just requires you to use the prime factors of all the primes multiplied together, plus one.
From my memory, they used this as a way to balance proof difficulty: for easier proofs, it would be a "prove of disprove", but for harder ones, they would reveal which one you can prove.
> after only a few decades of work (say, 1948 to 1993), turbo codes were discovered.
But LDPC codes were shown by Gallager in 1963[0], and while they were not feasible to implement at the time, saying that the theory waited for turbo code discovery is wrong.
I disagree completely. There is a theory of finding practical codes, and that theory took decades to elucidate.
A practical code must be not just computationally tractable, but also, the channel capacity must be approached quickly as block length increases, and decoding must not blow up for large block lengths. As you can read in Gallager's thesis, this was not known for LDPCs back in 1960.
Even in the mid-90s, when the connection between LDPC's and turbocodes became understood, it took more theoretical work to understand why some codes (those having short cycles) had poor performance -- because decoding them was fragile. (See the excellent http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf).
Similarly to the OP, there may be multiple ways to find designs, but some of the methods or the resulting designs may be clumsy or inefficient.
Large good codes were always known to exist, the crux from when Shannon published his work (I believe) was to actually get good codes that are computationally viable (else you could even use Shannon's random code). LDPC codes were rediscovered only because decoding became viable due increased computational power (w.r.t the 60's) and, crucially, discovery of iterative decoding for them (belief propagation etc).
This reads something like a classic Martin Gardner column -- clear, tantalizing, and presenting a highly technical math topic helpfully for non-specialists. Way to go, Erica Klarreich.
While it is trivial to find a single solution to the problem presented at the end of this article, does anyone have a nice general one? Please share if so.
Keevash’s result will shift the mindset of mathematicians who are trying to find designs, Colbourn said. “Before, it wasn’t clear whether the focus should be on constructing designs or proving they don’t exist,” he said. “Now at least we know the effort should focus on constructing them.”
I only glanced at the paper, but perhaps this is analogous to Shannon's original proof of existence of codes meeting channel capacity -- which was also a non-constructive, asymptotic result.
That pointed the way for people to start working out channel codes, and after only a few decades of work (say, 1948 to 1993), turbo codes were discovered.