The Tang Effect and Theorems
Side-effects and the Tang Effect
William Mitchell was a food scientist who invented the orange-flavored drink called Tang. He also invented other foods such as Cool Whip—an artificial type of whipped cream—and Pop Rocks—an “exploding” candy.
Today I want to talk about theorems, proofs of theorems, and how they relate to Tang.
There is an effect that I will call the Tang Effect. Sometimes a great endeavor creates a side-effect that becomes more important than the endeavor itself—that is the Tang Effect. In mathematics and theory some theorems solve long-standing open problems, while some do not. Most of the time the proof of a theorem uses methods that are already known, but the proof can still be clever and hard to discover. Some of the time, however, the proof of the theorem contains a method, a trick, a lemma, that is more important than the theorem itself. Importance is measured by how useful the method, trick, lemma is to other researchers—whether the method can be used to solve other problems.
The urban legend is that Tang is a perfect example of the Tang Effect. It is not. The great endeavor was the early NASA space program, which eventually put men on the moon. The legend goes that Tang was one of the side-effects that NASA created as part of the US space program. Unfortunately this is not exactly correct. Tang existed before the space program. It is an orange powder that when added to water creates an orange flavored drink. Not my favorite cup of tea—I vastly prefer real OJ.
What happened is that Tang had its sales skyrocket (OK, bad pun) when Tang was used on John Glenn’s Mercury flight and on subsequent Gemini missions. Apparently the water on board the space capsules was safe for the astronauts to drink, yet had an unpleasant flavor, so it was Tang to the rescue. Add a bit of the Tang powder to the water and the drink was quite palatable. One outcome, besides increased sales, was the belief that one of the side-effects of the space program was Tang. There are of course many valid and more-important space technology spinoffs, but still I like the name “Tang Effect,” so I hope that is okay.
Let’s look at some mathematical examples of this effect.
Szemerédi’s Theorem: Endre Szemerédi proved that for a given density and a , there exists an such that every subset of of size contains a -progression. That is, it contains integers and so that .
are all in the set. This theorem was a breakthrough of the first magnitude, and is an amazing milestone in the theory of combinatorics. But I would argue, with all due respect, that the proof is more important than the result. I can think of no paper that uses this theorem to prove something—they must exist, but I am unaware of them. I do know of hundreds, if not thousands, of papers that use a key idea from the paper. This is of course the famous Szemerédi Regularity Lemma. This is a perfect example of the Tang effect.
Wiles’ Theorem: Andrew Wiles proved, as we all know, that Fermat’s Last Theorem is actually a theorem. That
for an odd prime implies that . This theorem solved a 350 year old problem, is again a breakthrough result, and is amazing. Again, with due respect, I believe that it too is an example of the Tang effect: the methods Wiles used are perhaps more important than the actual result that a particular Diophantine Equation has no solutions. His proof opened the door for number theorists to prove the full Taniyama-Shimura-Weil conjecture, among other things. Wiles “only” needed a special case of the conjecture in his proof.
Recall what Carl Gauss said in reply to an attempt in 1816 to get him to work on Fermat’s Last Theorem:
I confess that Fermat’s Theorem as an isolated proposition has very little interest for me, because I could easily lay down a multitude of such propositions, which one could neither prove nor dispose of.
I have been told that one reason that Wiles was so excited to work on Fermat was precisely that it had been connected with the Taniyama-Shimura-Weil conjecture. This meant that even one solution to the equation would destroy the conjecture. It was no longer as Gauss said “an isolated proposition,” and so it was extremely important to find a proof. Moreover such a proof almost had to light up a whole area of number theory. Which it did.
Turing’s Theorem: Alan Turing proved that the halting problem is undecidable. There is no uniform procedure—-that is, no algorithm that always halts and gives a yes/no answer—that can decide whether any computation will or will not halt. The result is again a breakthrough and an amazing achievement. But again, in my opinion, this is another example of the Tang effect: the theorem is less important than the proof. The proof introduced the notion of a Turing Machine, and the application of Cantor’s idea of diagonalization in computation theory. The first notion is the cornerstone of all modern complexity theory. Where would we be without this beautiful model of computation? The second is still the basis of lower bound efforts against uniform complexity classes, not to mention that it sometimes applies even to non-uniform circuit families.
Finding The Tang
One further comment is that in major new results, sometimes the proof does not make it easy to see the Tang effect, or even state the “tangy” new result clearly. The proof may have many lemmas, where parts—not all—are potential Tangs. Most of the lemmas may only useful for the proof at hand. So finding the Tang in a long complex argument may be difficult: it may not even exist. But the reward for discovering the “Tang” can be enormous, and can yield a powerful new tool that even the author(s) of the original proof may not have realized was there.
What are some other examples of the Tang effect in mathematics and theory?