22
$\begingroup$

I ran across this discussion by Daniel Shanks,

"Is the quadratic reciprocity law a deep theorem?." Solved and Unsolved Problems in Number Theory. Vol. 297. AMS, 2001. p.64ff.

which made me wonder:

Q. Is there a theorem in some formal system whose proofs are known to be necessarily "long" in some sense, perhaps in the Kolmogorov-complexity sense?

I know it has been established that there are relatively "short" theorems that have only enormously "long" proofs (apparently[?] due to Gödel,"On the length of proofs"), but I'm asking if it is known that some particular theorem only has long proofs? (This is in some sense the obverse of the MO compendium, "Quick proofs of hard theorems.")

Obviously this is a naive question!

$\endgroup$
6
  • 8
    $\begingroup$ In fact the function $f(n)$ describing the length of the longest proof (in some reasonably powerful formal system) of a sentence on $n$ letters grows faster than any computable function. Sketch: if it didn't, then exhaustive search would give an algorithm to determine provability, and for a formal system powerful enough to discuss the solvability of the halting problem this is a contradiction. $\endgroup$ Nov 17, 2013 at 2:08
  • 1
    $\begingroup$ Nice question, indeed! As readers, however, guess we shouldn't be fooled by that: we're still under the "1-page bound", I mean there are probably plenty of new & interesting things to be discovered, fitting on 1 page of less, let's try first to have that done! $\endgroup$
    – Richard
    Nov 17, 2013 at 2:28
  • 5
    $\begingroup$ Why does "long" have anything to do with "deep"? $\endgroup$
    – Igor Rivin
    Nov 17, 2013 at 3:53
  • 1
    $\begingroup$ @Igor I would expect a positive correlation between "long" and "deep" but I agree that they are not the same thing. $\endgroup$
    – Derek Holt
    Nov 17, 2013 at 11:44
  • 1
    $\begingroup$ @IgorRivin: In some sense Shanks argues (in the book I cited) that the quadratic reciprocity theorem is deep because the proof is broad, in that it draws on many areas of mathematics not evidently close to the statement of the theorem. $\endgroup$ Nov 17, 2013 at 14:32

2 Answers 2

19
$\begingroup$

There is a body of very interesting work surrounding the proof complexity of various formulations of the well-known pigeon-hole principle, the fact that there is no injective function from a set of size $m$ to a set of size $n$, when $m\gt n$. It turns out that the difficulty of proving this depends on how much bigger $m$ is than $n$, and so we have actually a variety of pigeon-hole principles here:

  • Pigeon-hole principle. There is no injective map $n+1\to n$ for natural numbers $n$.

  • Moderately weak pigeon-hole principle. There is no injection $2n\to n$, for positive natural numbers $n$.

  • Weak pigeon-hole principle. There is no injection from $n^2\to n$ for natural numbers $n>1$.

  • Very weak pigeon-hold principle. There is no injection $\infty\to n$, for any finite $n$.

The principles become easier to prove, of course, as the domain gets larger, and there are shorter proofs when the domain is very large. The paper Proof complexity of pigeon-hole principles by Alexander Rozborov contains many interesting results on the computational proof complexity of these various formulations of the pigeon-hole principle, and in particular of the necessary long lengths of proofs in certain systems. Meanwhile, results of Sam Buss, Polynomial size proofs of the propositional pigeon-hole principle show that there is a dependence on the particular proof system that is adopted, for in certain Frege system one can still obtain polynomial size proofs.

$\endgroup$
1
  • $\begingroup$ I find this remarkable! Thanks, Joel! $\endgroup$ Nov 17, 2013 at 12:49
20
$\begingroup$

If you're willing to accept a contrived statement, then it's not hard to get an explicit example, but this may not be the sort of example you're looking for.

Following Gödel's approach, you can make a statement of the form "I have no formal proof of less than a hundred pages." (More precisely, you should use implicit self reference, along the lines of "There is no formal proof of less than a hundred pages for this string followed by its quotation: 'There is no formal proof of less than a hundred pages for this string followed by its quotation:'")

Assuming your formal system is consistent, this statement cannot be proved in less than a hundred pages. In that case it actually is provable, because you can prove it by enumerating all possible proofs of less than a hundred pages and checking that they don't work. Thus, we have a relatively short theorem that has no short formal proof. Sadly, the theorem is of no intrinsic interest.

Note that the reason it didn't take us a hundred pages to prove the theorem is because we assumed the formal system was consistent. By Gödel's second incompleteness theorem, the system can't prove its own consistency, so this approach is not available within the system. In fact, this argument proves the second incompleteness theorem: if consistency had a short enough proof, then we could carry out this argument to prove the theorem in under a hundred pages. There's nothing special about a hundred pages in this argument, so there can be no proof of consistency at all. This approach to the second incompleteness theorem is fundamentally the same as Gödel's original proof.

Here I've been measuring proofs by length, rather than the Kolmogorov complexity mentioned in the question. That's not a useful measure for proofs, because you can reconstruct the shortest proof of theorem X in system S from little more than X and a proof checker for S (which you apply to do a brute force search for the shortest proof). This means if you fix S, the Kolmogorov complexity of the shortest proof is no more than an additive constant greater than that of the theorem itself.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, Henry, especially for the explanation of why Kolmogorov complexity is not useful in this context. $\endgroup$ Nov 17, 2013 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.