Short and Tweet
Proofs that are about the length of a tweet.
Jack Dorsey is the creator of Twitter. We thank him for the creation of of tweets, which are of course messages of up to 140 characters in length.
Today Ken and I wish to talk about very short proofs—proofs that could almost fit into a single tweet.
It’s a fun topic, but also touches on a serious one: what is a proof really supposed to do?
These proofs must be hard to find but quick to verify, which is the essential idea of 
Euler’s Example
Let’s look at problems whose solutions fit into a single tweet, or almost.
Trying to generalize Fermat’s Last Theorem, the great Leonhard Euler conjectured that an 
Leon Lander and Thomas Parkin used a computer to solve the problem for 
Note, if they had just sent the answer it would have been:
Writing this as a LaTeX formula would have easily fit into a single Tweet—too bad they did their work 46 years ago.
Two decades later, Noam Elkies found a method to construct an infinite series of counterexamples for the 
where
In 1988, Roger Frye found the smallest counterexample based on Elkies’ ideas:
Gems
Note that 
is solvable in integers by 
That is,
has four distinct integer roots in pairs 
Going from degree 
with 
Can we do this with 
There had been a conjecture—indeed, a claimed proof—of “no,” but Dominic Symes found an example—or counterexample:
This gives distinct roots 
Can we take it a step further to degree 
Namely, the left-hand sides 
A degree-
They give 
Short Proofs and Interaction
Ken and I believe this issue of very short proofs highlights the real reason we prove theorems in mathematics.
A proof is not just a thing that we write out and then feel happy with the knowledge that something is proved. No. A proof must be something that can be understood by others.
To be understood it must be checkable. The above are extreme examples—you can just do the arithmetic. The existence of the proof is what was hard.
In some areas of computer science proofs are viewed in a different way. One area where I hear statements like “the proof is long and boring” is cryptographic protocols.
That some proofs of protocols are tedious is exactly what I do not like about them. I do not trust a long and boring proof, exactly because it is unlikely to be checked by others.
Of course protocols themselves are often proofs, of knowledge or identity or privilege or authority. The individual steps required of the user can be short.
The idea of interaction takes proofs beyond
Even for problems like factoring, interaction can shorten the proof that one has a proof. Suppose I have a long proof of an efficient algorithm. What can I do?
I can say, “Tweet me a number.” Using ASCII for base 128, a 1,024-bit RSA modulus 
With interaction you can’t accuse me of pre-computing results or exploiting holes like Arjen Lenstra’s project. This is a short proof of my proof.
Most protocols cannot self-prove this way because you have to prove security against possible attacks. But there as in math, it’s good to ask how far short proofs can go.
Open Problems
Could there be a very short proof of your favorite open problem? Can we make more proofs like tweets?
Is a post easier to read with Tweet-length paragraphs, sometimes with equations in-between, each giving one idea? Or our usual longer ones?
End Note
We add our congratulations to Leonid Levin, himself known for very short papers, on his 2012 Knuth Prize. Ken heard his lecture at FOCS this past Monday—here is a nice post by Thomas Vidick on it.[21519–>217,519]
21519 should read 217519
Thanks!
I sympathize with much of what you write. However, I do not believe that every “interesting” theorem in CS or mathematics is amenable to a short and elegant proof. For instance, proofs of correctness for non-trivial programs or (cryptographic) protocols might need long proofs and perhaps we should accept this fact. What is boring/tedious is in the eye of the beholder and the import of the correctness proof for a cryptographic protocols might just be that the protocol works.
Aschbacher’s “Highly complex proofs and implications of such proofs” offers an interesting discussion of very long and complicated proofs in mathematics. Here are two excerpts:
“Conventional wisdom says the ideal mathematical proof should be short, simple
and elegant. However, there are now examples of very long, complicated proofs,
and as mathematics continues to mature, more examples are likely to appear.”
“My guess is that we will begin to encounter many more such problems,
theorems, and proofs in the near future. As a result we will need to re-examine
what constitutes a proof, and what constitutes a good proof. Elegance and
simplicity should remain important criteria in judging mathematics, but the
applicability and consequences of a result are also important, and sometimes
these criteria conflict. I believe that some fundamental theorems do not admit
simple elegant treatments, and the proofs of such theorems may of necessity be
long and complicated. Our standards of rigor and beauty must be sufficiently
broad and realistic to allow us to accept and appreciate such results and their
proofs. As mathematicians we will inevitably use such theorems when it is
necessary in the practice our trade; our philosophy and aesthetics should reflect
this reality.”
I recommend reading the essay.
Proof that n^{1/n} -> 1 as n -> oo:
By Bernoulii’s inequality, (1+n^{-1/2})^n >= 1+n^{1/2} > n^{1/2}.
Raising to the 2/n power,
n^{1/n} < (1+n^{-1/2})^2 = 1 + 2n^{-1/2}+n^{-1} < 1 + 3 n^{-1/2}.
q e d
In the view of theorems as a shortcut statements in the different proves, long proves are actually good, when used many times, similar to subroutines in programming. They loose aesthetics, but should be practical.
Two appreciations of tweet-length proofs from Michael Spivak’s well-regarded Calculus on Manifolds: (1965)
Spivak’s remarks find an apt counterpoint in Saunders Mac Lane’s survey article Hamiltonian mechanics and geometry (1970):
Theorems having “trivial” proofs that are founded upon multiple levels of carefully crafted abstraction are emerging (it seems to me) as a hallmark of a 21st century STEM enterprise in which mathematical naturality is appreciated as dual to experimental physicality.
But then John, one needs exponentially many definitions if P!=NP ;), still unreadable.
To some folks (including me) oracles seem intrinsically more mysterious than definitions! 🙂
Is a counterexample really the same as a proof? Or in other words: I guess I’m more impressed by a short proof of a “for all” statement than I am of a “there exists” statement.
About Delta’s question “Is a counterexample really the same as a proof?”: It depends if the value of a theorem being true is the same as the value of a theorem being false. It seems to me, in general, that it is more work to prove a theorem than to find a counterexample, so my answer to the question is “No.”