Answer to a 150-Year-Old Math Conundrum Brings More Mystery
wired.com
wired.com
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.
Nonconstructive proofs of existence in rare, outside of logic classes. Most branches of undergrad math aren't interested in mere existence
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.
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.
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.
Step 1 is the specific example. You say:
1. Assume there is no prime number larger than p_n.
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.
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.
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.
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.
this version is nonconstructive: assume you have all primes -> multiply, add one -> contradiction
this version is constructive: you have n primes -> multiply plus one is always a new prime
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.
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?
Not so sure about that. I'd also dispute that they are inherently more difficult (assume X doesn't exist... )
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.
* 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.
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.
[0] https://en.wikipedia.org/wiki/Low-density_parity-check_code#...
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.
Incidentally, it turns out there is a deep connection between coding (i.e., the present analogy) and designs (the OP), see http://www.ces.clemson.edu/~keyj/psfiles/booktoc.html, and the follow-up article http://www.ces.clemson.edu/~keyj/Key/dccupdateb.pdf, especially chapter 7.
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.
Solution at top, so scroll to the bottom first.
There are practical applications. :)