# 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 th power cannot be written as the sum of fewer than nontrivial powers for .

Leon Lander and Thomas Parkin used a computer to solve the problem for and found a counterexample. Here is their whole paper:

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 case. He showed that

where

In 1988, Roger Frye found the smallest counterexample based on Elkies’ ideas:

## Gems

Note that always has the integer roots , which are distinct when . And

is solvable in integers by , , , among many other possibilities.

That is,

has four distinct integer roots in pairs and .

Going from degree to , we can solve

with , , and . These induce , , , and , again giving -many distinct integer roots.

Can we do this with for

There had been a conjecture—indeed, a claimed proof—of “no,” but Dominic Symes found an example—or counterexample:

This gives distinct roots , as you can verify. Andrew Bremner found two infinite families of solutions.

Can we take it a step further to degree with and ? Nobody knows. This is related to Stephen Smale’s Fourth Problem which we just blogged about.

Namely, the left-hand sides are straight-line programs of length . If there are distinct integer zeroes, this violates the conjecture .

A degree- polynomial with distinct integer roots and a short straight-line program is called a gem by Bernd Borchert, Pierre McKenzie, and Klaus Reinhardt.

They give -gems for up to , but skipping . See Borchert’s project page for more, including relevance to factoring.

## 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 . The interaction can be short, or have short rounds. Still, the proof that it is a proof can be long.

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 can fit into 140 characters. Then I tweet back and you verify .

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.”