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](https://mathoverflow.net/q/24913/6094).")


Obviously this is a naive question!



Deep theorems and long proofs
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](http://people.cs.uchicago.edu/~razborov/files/php_survey.pdf) 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](http://www.math.ucsd.edu/~sbuss/ResearchWeb/php_PolyFrege/FregePHP.pdf) 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. 


