An Amazing Result
When is a math result amazing?
James Randi is a famous magician whose stage name is The Amazing Randi. Since retiring he has focused on the debunking of those who claim paranormal abilities. If you cannot solve any of the million dollar Clay Prizes—who can?—then another way to get a million is to show Randi that you have paranormal abilities.
Today I want to talk about a math result that is called amazing.
I am not sure what the exact definition of an amazing mathematical result should be. The result in question is called amazing by Devdatt Dubhashi and Alessandro Panconesi who are authors of the beautiful book: Concentration of Measure for the Analysis of Randomized Algorithms. I will not argue with them, since in their entire book there are no other results that are called amazing. Yet their book does indeed contain many pretty cool results, perhaps some amazing ones.
I do know what the definition of an amazing talk is: have Randi give a talk. In twenty years at Princeton I heard many many talks, of all kinds: students, faculty, visitors, job candidates, and others. Some talks were good, some were great, some were, let’s stop there; but only the talk by Randi was truly amazing.
A Magic Talk Without Magic
I did mention wanting to tell about Randi’s talk here. Though it happened years ago I still recall it in detail—it was brilliant. If you have a chance to hear Randi speak do not miss it.
My favorite part of his talk was a tale of debunking those who believe in dowsing rods. These rods are supposed to be able to detect various materials. The “dowser” holds the “Y” shaped rods, and the rods are suppose to pull you toward the required material: some find water, some find gold, some find other materials.
Randi told us that someone, I will call him X, hired Randi to help test those who claimed to have dowsing rods that could detect gold. A twenty-five thousand dollars prize was funded by X to anyone who could pass Randi’s test. It is unclear why someone with a gold-finding rod would need the prize money, but that is another matter.
The big day came and a small group of applicants arrived at a school gymnasium that Randi and X had reserved for the testing. Randi had four empty identical cardboard shoe boxes and one large bar of pure gold. Randi created a simple protocol: he would place the gold in one of the shoe boxes, which were then placed in various parts of the gym, far from each other. Candidate dowsers would be brought singly into the room—they were in another room while the gold was hidden—and they would then use their rods to select a box. The box would be opened, and they were successful if the gold was in the box. This was repeated a number of times with each candidate, trying to locate the hidden gold.
Not surprisingly, all the candidates did about as well as expected: they each found the gold about one chance in four—nothing special.
OK, With Some Magic
The last candidate failed like the others but seemed to Randi to be very upset. Randi asked him what was wrong, and the candidate said that his rod always worked extremely well and he could not see what was wrong today. Randi smiled to us and said the poor fellow did not look exactly like someone who could easily find gold, but perhaps that should not be held against him.
Randi suggested to this candidate that they might do an informal trial. So Randi placed three of the shoe boxes on a table and took the remaining box and placed the gold bar in that box. He then placed that box down in a corner of the gym, and asked the candidate to see if the rod worked when the gold was in a corner—perhaps corners of the room were more difficult. No, the candidate used his rod and it sharply pointed and led him right to the correct box in the corner. Randi then moved the box to the middle of the room, and said perhaps the middle of the room is hard. No, again the candidate’s rod very quickly located the box. Randi moved the box around the room several times, and each time the rod worked perfectly.
Finally, Randi asked the candidate to pick up the shoe box and move it to another location. You know what happens when you pick up something you think is heavy, yet is very light. It tends to fly up into the air. This is what happened: the box tumbled into the air and fell to the ground and opened. There was no gold bar in the box. There never had been a gold bar in that box during all the successful detections. Randi smiled and looked at the candidate and said, “where is the gold?”
Of course the whole point is Randi never placed the gold in the box during this last trial experiment—he is after all a magician. The dowsing rod was detecting gold in an empty box, each time. The twenty-five thousand dollars of X was safe.
The Amazing Result
The amazing result is that there is an absolute constant 
is bounded by 
Is this amazing? I was surprised when I first saw the result, but “amazing” I am not sure. It does have a very simple proof, which I will present next. But think about it first if you wish too. Perhaps if you think about it and get stuck, that will make the result more amazing.
The Proof
The proof is quite simple once you think about it in the right manner. Define a cohomology structure on all finite sets of points in the unit square in the obvious manner. Then note that this cohomology yields a bijection with modular forms that satisfy
Just kidding. The proof is based on a clever argument of Donald Newman, who is known for many clever arguments. I quote from Dubhashi and Panconesi who made the proof an exercise in their book:
- Show that for any set of points in a right-angled triangle, there is a tour that starts at one endpoint A of the hypotenuse, ends at the other endpoint B, and goes through all the points such that the sum of the lengths of the edges is bounded by the square of the hypotenuse. (Hint: Drop a perpendicular to the hypotenuse from the opposite vertex C and use induction.)
- Use (1) to deduce the amazing fact with the constant 4.
Note, when there is only one point it follows from the observation that in an obtuse triangle, the sum of the squared lengths of the smaller sides is less than the squared length of the largest side—thanks to Subruk, Subrahmanyam Kalyanasundaram, for this and other comments.
A small issue is that there is a typo here. The phrase should be “and goes through all the points such that the sum of the squared lengths of the edges is bounded by the square of the hypotenuse.”
Open Problems
Is this an amazing result? What is you favorite amazing result?
Ken notes one general kind of surprising result when a quantity one might have expected to be infinite turns out to be finite. The limit on “sporadic” groups, which completed the classification of finite simple groups, is a big example. Many of these results ultimately come down to limits on solving Diophantine equations. What “Sudden Finiteness” results do you know?
Wait a minute, to see if I got this right. Does that mean that for every n points in the square, I can then find a good reordering and bound that expression by 4?
Jaw. Dropped. Thanks for sharing this result!
I think this use of space-filling curves (which is essentially what you’re doing in your proof) to prove bounds on the sum of squared distances goes back to Snyder and Steele, Math. Oper. Res. 1990 and SoCG 1992 — at least, that’s where I found out about it. Relatedly, the sum of squared lengths of minimum spanning tree edges is always O(1); I think this goes back much farther, to Gilbert and Pollak 1968. But the sum of squared lengths of the edges in the optimal TSP tour may be Ω(log n) — see my paper with Bern in SoCG 1993.
Are you sure that your paper with Bern in SoCG 1993 is amazing result? 😉
Well, if it’s amazing that the sum of squares is O(1), I guess it must be the opposite of amazing to prove that the sum of squares is not O(1).
We need the Amazing Randi to debunk quantum computers. This is an amazing result: bramcohen.livejournal.com/39662.html
Reblogged this on Room 196, Hilbert's Hotel.
Hmm, and it looks like 4 is best possible from considering two points at opposite corners of the unit square, or from 4 points with one at each corner. That is a deeply surprising result.
That’s a very nice little result. The first statement makes it sound more profound than it is, with the business of the universal constant c– replace “universal constant c” with “4” from the beginning, and the result is less amazing, if only very slightly.
“Define a cohomology structure on all finite sets of points in the unit square in the obvious manner.”
This made me loose some minutes googling =)
Dear Ken, can you give the reference to the proof on the limit of “sporadic groups”? It just caught my attention.
Here’s a result of mine I got many years ago that I found surprising:
Consider the difference between the product of n consecutive positive integers and the n-th power of a positive integer where n >= 3. It is reasonable to think (and not too hard to prove) that for any fixed k and n there are only a finite number of cases where this difference is less than k in absolute value. What is surprising is that for any fixed k there are only a finite number of cases where this holds for all n.
In particular, if we write this as x(x+1)…(x+n-1) – y^n = k, I showed that y <= |k| and n < e|k| for a start, and much better results later on.
Another way to say this is that the product of n consecutive integers is almost never close to the n-th power of an integer for all n.
I implemented the algorithm. Here is how the tour looks:
http://people.mokk.bme.hu/~daniel/amazing_path.pdf
Cool! How does that algorithm scale with the size of the triangle? 😀
I find the Beck-Fiala theorem amazing, and it fits the class of “expected to be infinite but is finite” results. The proof is very pretty too. Gil Kalai presents it nicely and gives an application that’s almost as neat: http://gilkalai.wordpress.com/2011/08/28/discrepancy-the-beck-fiala-theorem-and-the-answer-to-test-your-intuition-14/
If you think of the Euclidean traveling salesman problem above in the following way, you’ll see that it really isn’t amazing at all; it’s obviously true:
Suppose the points are not random but on an M x M grid. For instance, suppose that every point has the coordinates (x/M, y/M), where 0<=x,y<=M. Then suppose that one starts at (0,0), travels to the right until one reaches the end, travels up 1/M of a unit, then travels left until one reaches the end, travels up 1/n of a unit, travels to the right….
Then you'll go through every point. The sum of the squares of the distances between the points that you travel will be on the order of the sum of the areas of all of the little squares on the grid, which is bounded by one.
If you let M be large and the n random points have rational coordinates, then this path will go through all of the n random points and be bounded by a constant, so the optimal TSP path must be also bounded by a constant.
It's because we're dealing with the sum of squares instead of the sum of distances that makes this amazing fact true.
This argument isn’t valid for non-random point sets, because the shortest Euclidean traveling salesman path does *not* have constant sum of squares (see my earlier comment above). The amazing path is a different path than the shortest path.
I called it the Euclidean TSP, but it’s not really a Euclidean TSP. I got the names mixed up.
But if you get past that, you’ll see that my argument is valid.
Craig: You are adding auxiliary nodes to the path. You are right that allowing this makes the result trivial. Dick is adding auxiliary nodes too, but there is a big difference: he can drop them later, because the auxiliary nodes are always at acute angles of the path. The triangle inequality is not true in our case in general, but true if the dropped node is at an acute angle. The post was not very clear about this important ingredient of the proof.
Dániel,
I can drop auxiliary nodes in the path I gave too, since the auxiliary nodes are always at right angles of the path.
Graig,
I don’t think you can. You can drop the ones at the U-turns at the sides, but you still need the ones in the middle.
Sorry about misspelling your name, Craig.
Dániel,
Any row that has only auxiliary nodes would be skipped.
> Any row that has only auxiliary nodes would be skipped.
Take a row with only two points, one at each end. With the extra nodes, the row’s contribution is 1/M. Without them, it is 1.
No problem Dániel,
Lots of people used to call me Greg or Graig before a few years ago when Craig’s List came out. Now, it’s strange to me that most people even know how to spell my name.
“Take a row with only two points, one at each end. With the extra nodes, the row’s contribution is 1/M. Without them, it is 1.”
Then there is no reason to go right or left. Just go up. Get it later at the end.
Anyway, I see your point. My argument isn’t specific about what to do about these auxiliary nodes, which could potentially cause problems.
Thank you.
Nice post! My candidate is the residue theorem from complex analysis, which relates path integrals to characteristics of just a few points within the encircled region.
If you are impressed by the residue theorem, then just read about Marden’s Theorem: http://www.maa.org/joma/Volume8/Kalman/index.html
As a fresh-from-the-farm college freshman, I remember being gobsmacked by
Hey, where did the
go! 🙂
And truth to tell, it still gives me a considerable thrill.
“Gobsmacked”? Most of the country thinks that word was just introduced to the USA at tonight’s Oscar ceremony :-).
It is a common word, down our way … We use it interfrastically! 🙂
What about the fact that the volume of a sphere, with radius equal or less than one, approaches zero as we increase the dimension? 😀
Here is an amazing result: the question is how many nonoverlapping d-dimensional simplices you can put in d-dimensional space so that every two simplices has a (d-1)-dimensional intersection. The result by Micha A. Perles is that the number is at most
. (It is conjectured that the true value is 
; this was proved for d=3 by Joseph Zaks who also gave an example that in every dimension 
cannot be improved.)
Here is the proof: Suppose there are m simplices. Consider all n hyperplanes determined by facets of the simplices. For each hyperplane assign arbitrarily a positive side and a negative side.
Now consider a matrix X with rows corresponding to the m simplices and columns corresponding to the n hyperplanes. The (i,j) entry is +1 or -1 if the jth hyperplane contains a facet of the ith simplex which lies in its positive side, or negative side, respectively and 0 otherwise. Every row has d+1 nonzero entries and n-d-1 zeroes. The geometric condition translates to:
(*) For every two rows there is some column where the entries are nonzero and have different sign.
Noy replace X by a matrix Y where each row of X is replaced by
rows in all possible ways to replace the 0s by _1s or -1s. Condition (*) continues to hold.
The new matrix Y has
rows, And because of (*) they are all distinct. So 
is at most 
and therefore 
.
Hasse’s theorem on elliptic curves is amazing, because it makes sense out of something that doesn’t seem to make much sense.
http://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves
Two of my favorite puzzles in this vein are the following:
– If you take the harmonic series and remove the reciprocals of numbers that contain at least one million consecutive nines, the resulting series converges.
– Suppose you have a infinite (perhaps uncountable) set of prisoners, each of whom has a real number written on the back of his uniform (obviously in very fine ink). (A prisoner cannot see his own number, but can see the numbers of the other prisoners.) Each prisoner has to write down (privately, simultaneously) a guess of his own number. There is a strategy that guarantees that almost all of them will guess right.