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 so that for any points in the unit square for some reordering of the points into the value of
is bounded by , where is the usual Eucildean norm of the point . That is if , then
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 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.”
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?