tags: ,

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.

Examples

${\bullet }$Szemerédi’s Theorem: Endre Szemerédi proved that for a given density ${\delta>0}$ and a ${k}$, there exists an ${N}$ such that every subset of ${\{1, \ldots, N\}}$ of size ${\delta N}$ contains a ${k}$-progression. That is, it contains integers ${a}$ and ${d>0}$ so that .

$\displaystyle a, a+d, a+2d, \ldots, a+(k-1)d$

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.

${\bullet }$Wiles’ Theorem: Andrew Wiles proved, as we all know, that Fermat’s Last Theorem is actually a theorem. That

$\displaystyle x^{p} + y^{p} + z^{p} = 0$

for an odd prime ${p}$ implies that ${xyz=0}$. 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.

${\bullet }$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.

Open Problems

What are some other examples of the Tang effect in mathematics and theory?

May 9, 2011 11:02 pm

Godel’s arithmetization of language in his incompleteness paper, Cohen’s forcing, Friedberg and Muchnik’s priority method, and quite a number of techniques in cryptography.

2. May 10, 2011 4:45 am

One of my favorite examples is the lambda calculus, which Alonzo Church introduced while investigating the foundations of mathematics. His foundations of mathematics were found to be inconsistent, but the lambda calculus lives on.

May 10, 2011 8:56 am

Yang,

Very neat example. Lambda does indeed live on.

May 10, 2011 3:54 pm

However because of its origins, lambda calculus carries a particular notation and focus taylored to laying the foundations of mathematics, rather than the foundations of computation/programming.

In a sense, to refer to a previous entry in this blog, lambda calculus notation stronlgy shapes our thinking on that matter and not necessarily for the better.

3. May 10, 2011 8:13 am

I can see why you mention Turing’s Theorem as an example of the Tang effect. Nevertheless, contrary to Szemerédi’s Theorem, you cannot say for Turing’s that you “can think of no paper that uses this theorem to prove something”. I would call it the weak Tang effect: the proof is at least as important as the result. Of course, a Tang effect is also a weak Tang effect with my definition.

May 10, 2011 8:14 am

Tang is better than Orange Juice.

May 10, 2011 2:16 pm

Sir — This is a difficult proposition to defend. I submit that it is self evident that Tang is inferior to Orange Juice in nutritional content, and therefore, your claim necessarily rests on an argument that Tang has a more pleasing taste. But this is an argument that you cannot make in good faith. Orange Juice plainly has a fuller, more satisfying taste and mouth feel, to Tang’s synthetic, one note sugar flavor.

May 10, 2011 5:11 pm

Of course, Green and Tao’s result proving the existence of arbitrarily long arithmetic progressions of primes uses Szemeredi’s theorem (Green and Tao’s result might also carry some Tang effect; I recall Trevisan and Reingold discovered applications of Green and Tao’s methods to complexity theory and another paper had an application to a computationally bounded version of differential privacy). Of course, the statement of Green and Tao’s result is very close to the statement of Szemeredi’s theorem, so the application of the theorem is not quite surprising.

I would put Lovasz’s exact bound on the Shannon capacity of the 5-cycle in this category. How many people *really* care about the Shannon capacity of one small graph? But how many care about the Lovasz theta function and even more so about the application of SDP to combinatorics and computer science?

6. May 11, 2011 6:42 am

This “Tang” essay is a natural partner to one of the most popular Gödel’s Lost Letter and P=NP essays, namely “Are Quantum Impossibility Proofs Possible?” … also known as “the one about the burning arrow.”

Contemplating these two essays side-by-side, we are naturally led to wonder, whether it ever happens, that the bitter water of practical applications first is sweetened by the Tang of ingenious mathematics, and then the Tang itself evolves into a “burning arrow” of transformational mathematics?

Definitely this evolution does happen. A vivid example from this history of mathematics is described in Hans Samelson’s recent AMM article “Differential Forms, the Early Days; or the Stories of Deahna’s Theorem and of Volterra’s Theorem” (2001). Samelson’s article describes vividly how the “bitter water” of Maxwell’s early experiments in electricity evolved first into the “Tang” of Stoke’s theorem and the Poincar\'{e} Lemma, then into the “burning arrow” of de Rham cohomology.

But historically, it seems that mathematical Tang-to-arrow transformations do not happen fast; typically these transformations have required a full century (or more).

And this stately pace is good news for today’s young researchers in complexity theory. Because it means that with regard to complex systems, there is substantial reason for hope that our understanding is still at the early Tang stage, so that we can look forward to many future decades of tough-to-imagine progress.

The recurring theme of optimism regarding the future of mathematics, which is present implicitly in almost all posts, is (for me) one of the most enjoyable aspects of Gödel’s Lost Letter and P=NP.

May 13, 2011 12:59 pm

Tang is the pronunciation of sugar in Chinese.

8. May 15, 2011 1:46 pm

One of my favorite examples is the introduction by Alon, Karp, Peleg and West
of low-stretch spanning trees. The paper was about the k-server problem.
I don’t think anyone uses the results on the k-server problem. But, low-stretch trees
were the inspiration for many major algorithmic developments. They inspired
Bartal’s approximation of graphs by distributions of trees, and its later optimization
by Fakcharoenphol, Kunal and Rao. This also inspired Racke’s approximations
of graphs by trees. These have been incredibly useful tools in the design of approximation
algorithms.

Boman and Hendrickson observed that they are also very useful for solving systems
of linear equations, and they are now the basis for the amazingly fast Laplacian
equations solvers of Koutis, Miller and Peng.

• June 28, 2011 11:50 am

Dan, your post was terrifically interesting and inspiring for our UW Quantum Systems Engineering (QSE) Group. In the context of QSE enterprises, SDD systems have a natural interpretation in geometric dynamics, namely, they describe the symplectic transformation that “lifts” the (gradient) one-forms of Hamiltonian potentials to the tangent vectors of simulation trajectories. At first impression, the Laplacian preconditioners that Koutis, Miller and Peng describe appear to provide a key element for blazing-fast dynamical simulations of large-scale classical, quantum, and hybrid spin systems … so thank you for this wonderfully interesting pointer!

9. June 22, 2012 10:18 am

You actually make it seem so easy together with your presentation however I in finding this matter to be actually something that I believe I’d never understand. It kind of feels too complicated and very wide for me. I’m taking a look forward on your next post, I will try to get the cling of it!