Correlation does imply correlation...

XKCD: Correlation.

...he said, unhelpfully.

Interview Question

The Two Bowling Ball Problem

This is just a name that search algorithm, right?

How green was my valley

Try to quantify that, if you dare. Otherwise, check out this review for How round is your circle? Where Engineering and Mathematics Meet.

Let's start with the book's title, which is connected to the problem of how to determine whether a roundish object is exactly round, to a certain tolerance. This turns out to be much trickier than one would expect. For a start, there are the curves of constant width (such as the Reuleaux triangle, which is made by drawing three 60-degree arcs of a circle centered at the vertices of an equilateral triangle). Because one can make such curves with many bumps, a device that just checks several diameters for equality can be fooled. The authors describe various ways in which one might try to confirm roundness, but they all have drawbacks, and when it comes to the definitive answer, Bryant and Sangwin admit that it takes very complicated machinery to perform a proper check (basically by rotating the given object around an axis).

Click on through for more.

Ah, that explains it

The source of many problems, it would seem.

Paperchase

Folding a sheet of paper 12 times is now unimpossible.

The hardest logic puzzle ever

The so-called hardest logic puzzle ever; replete with exploding god-heads.

pi vs e

Pi is wrong. e for Euler is still cool.

Which reminds me of some optics department wisdom:

"Pi and e: You see them everywhere, but they're not good looking numbers."
Sean Bentley

"And so, ignoring all significant digits, the ratio is 1."
Tom Brown

Tipping Point

Can't Knock It Down
Julie J. Rehmeyer

Eventually, Domokos and Várkonyi managed to prove mathematically that for any flat shape, there are at least two stable balance points and at least two unstable balance points.

Next, the pair began to investigate whether all three-dimensional shapes have at least two stable and two unstable balance points. They tried to generalize their two-dimensional proof to higher dimensions, but it didn't hold up. Therefore, it seemed possible that a self-righting three-dimensional object could exist. Such a shape would have only one stable and one unstable balance point.

They looked for objects in nature that might have such a property. While Domokos was on his honeymoon in Greece, he tested 2,000 pebbles to see if he could find one that would right itself, but none did. "Why he is still married, that is another thing," Várkonyi says. "You need a special woman for this."

I wonder about the stability of marriages to mathematicians. All of the number theorists I have met have been significantly eccentric, but married none the less.

Noise is the Medium and the Message

I was in Lenox, MA for a few days to give a talk at a MURI workshop. Aside from the lovely New England countryside, which on Tuesday and Wednesday looked just like the photo above, I got to see a talk about single pixel cameras using compressive imaging with L1 norm reconstruction. This is all based on the work of Terry Tau and Emmanuel Candes. Tau is the the youngest guy ever to win a Fields Medal. Apparently he's quite smrt.

So Whitaker-Shannon says that you can perfectly reconstruct a Nyquist sampled-bandwidth limited signal. Okay, everyone knows that, but it turns out Shannon was way too pessimistic - almost nothing is band-limited; Almost everything is sparse, which is to say that the entropy of the universe is low. Anyone who reads blogs knows that. And if it doesn't seem so now, everything is sparse in the right set of basis functions, and for nearly everything the right set of basis-functions turns out to be noise. Weird.

To apply this to imaging, take some binary noise and line it up into a grid; it would look like an empty cross-word puzzle. Take a same-sized image, like the one above, and multiply them together, pixel by pixel, so that you get an image where half the pixels have been set to zero. Then add up all their values into a single number. Write that down. Then start over with a new noise pattern, which is your second basis function, and turn the image into a second number by projecting it onto the basis function. For an image with N pixels, do this about K=(0.05 to 0.20)*N times. Send your friend the K values, and he can asymmptotically reconstruct the image with 99% fidelity using The Magic of the L1 Norm (you can get MATLAB code there if you want to play yourself). At this point, all I can say is that it's magic, but the fundamental insight is that things are sparse, and so there going to be room to maneuver here. The signal is almost never pathological.

The great thing is that you can turn brute force O(n^3) problems into ~O(n log n) problems; A savings of nearly n^2. In an age of cheap CCD cameras, the imaging application turns out to be useful for imaging in non-visible wavelengths, like IR, Gamma Ray, and THz, where silicon doesn't do you a lot of good. Or perhaps you want to take gigapixel+ images using megapixel camera.

This turns out to be similar to one-time pad code-breaking. The low entropy of secret messages induces statistical similarities into the encrypted message.

Anyway, very cool.

The Axiom of Choice

Fun thing to think about for today: The Axiom of Choice. Math is a lot like Perry Mason - he gets you in the witness stand, and asks you if you like chocolate. It goes like this

1. You answer.
2. ???
3. You confess to the murder: "I'm not stupid! Could a dumb person have killed her like I did?!"

We are the Hamilton Burgers of reality [1]. Again, it starts innocently enough:

Let X be a set of non-empty sets. Then we can choose a single member from each set in X.

Which sounds fairly dry, but hang with me here. For one thing, the axiom says nothing about how to choose each element; It only says that it is possible to do so. It's easy to see this with finite sets or well-ordered sets (e.g., the positive integers), but the axiom also applies to sets like the real numbers, which are uncountably infinite and not well ordered (see the article for details) . This means that we accept the existence of a function, called the choice function, that we may have no idea of how to implement. And so?

One reason that some mathematicians dislike the axiom of choice is that it implies the existence of some bizarre counter-intuitive objects. An example of this is the Banach–Tarski paradox which says in effect that it is possible to "carve up" the 3-dimensional solid unit ball into finitely many pieces and, using only rotation and translation, reassemble the pieces into two balls each with the same volume as the original. Note that the proof, like all proofs involving the axiom of choice, is an existence proof only: it does not tell us how to carve up the unit sphere to make this happen, it simply tells us that it can be done.

Which would be a nice trick, because you wouldn't conserve mass, for instance. The paradox is generally thought to resolve itself because to it's not physically possible to cut a real, atomic object into the necessary pieces - but, it may not be as reassuring as you would hope:

At first glance, the Banach-Tarski result seems to contradict some of our intuition about physics -- e.g., the Law of Conservation of Mass, from classical Newtonian physics. If we assume that the ball has a uniform density, then the Banach-Tarski Paradox seems to say that we can disassemble a one-kilogram ball into pieces and rearrange them to get two one-kilogram balls. But actually, the contradiction can be explained away: Only a set with a defined volume can have a defined mass. A "volume" can be defined for many subsets of R³ --- spheres, cubes, cones, icosahedrons, etc. --- and in fact a "volume" can be defined for nearly any subset of R³ that we can think of. This leads beginners to expect that the notion of "volume" is applicable to every subset of R³. But it's not. In particular, the pieces in the Banach-Tarski decomposition are sets whose volumes cannot be defined.

Which is certainly good news for my investment in Krugerrands [2]... But it still unsettling that this paradox exists. But what about it's negation? Quoting from the Wikipedia article again:

On the other hand, the negation of the axiom of choice is also bizarre. For example, the statement that for any two sets S and T, the cardinality of S is less than or equal to the cardinality of T or the cardinality of T is less than or equal to the cardinality of S is equivalent to the axiom of choice. Put differently, if the axiom of choice is false, then there are sets S and T of incomparable size: neither can be mapped in a one-to-one fashion onto a subset of the other.

This is somewhat more than a curiosity too because many fundamental results are derived using this axiom. You can take an agnostic approach, and that's what many mathematicians choose to do (not unlike quantum mechanics), but it results in that many questions are then undecidable. Undecidable questions are okay, because at the basis of what we consider to be common sesible are many such statements that we accept as true and then move forward to derive more complicated results (trivial and non-trivial[3]). But it seems strange here that even if you assume the statement, either way you have paradoxical results.
--
[1] Random thought - which is more futile: Burger's 10-year prosecutor's losing streak, the Washington Generals million game losing streak versus the Harlem Globetrotters, or the Nazi's on the History Channel?
[2] Actually my long term investment plan is to buy lottery tickets where the take-home value of the jackpot divided by the odds of winning is greater than the cost of a ticket. It could happen.
[3] Any result you've derived is trivial; Anything I haven't is non-trivial.

Nerdicle

Spy plot of the link structure of a small sample of the Web

The World’ s Largest Matrix Computation: Google's PageRank is an eigenvector of a matrix of order 2.7 billion

Imagine surfing the Web, going from page to page by randomly choosing an outgoing link from one page to get to the next. This can lead to dead ends at pages with no outgoing links, or cycles around cliques of interconnected pages. So, a certain fraction of the time, simply choose a random page from anywhere on the Web. This theoretical random walk of the Web is a Markov chain or Markov process. The limiting probability that a dedicated random surfer visits any particular page is its PageRank. A page has high rank if it has links to and from other pages with high rank.

Let W be the set of Web pages that can reached by following a chain of hyperlinks starting from a page at Google and let n be the number of pages in W. The set W actually varies with time, but in May 2002, n was about 2.7 billion. Let G be the n-by-n connectivity matrix of W, that is, g_i,_j is 1 if there is a hyperlink from page i to page j and 0 otherwise. The matrix G is huge, but very sparse; its number of nonzeros is the total number of hyperlinks in the pages in W.

The Seven Deadly Sins

Take the seven deadly sins, and then you can name the (7 2) = 7*6/2 = 21 2nd order deadly sins. Image via the void.

Nerd of the Year To-Do-List

Poincaré Conjecture
Riemann Hypothesis...

And yet Deion Sanders is nowhere mentioned

From this article also known as Prime Time:

Riemann found that certain complex numbers, when plugged into the zeta function, produce the result zero. The few zeros he could calculate lay on a vertical line in the complex plane, and he guessed that, except for a few well-understood cases, all the infinity of zeros should lie exactly on this line.

What does this have to do with the primes? If you plot how many primes exist below a given number (see Diagram above), what you get is a smooth curve with small wiggles added, —that is, the 1/ln(x) rule, plus deviations.

According to Michael Berry of Bristol University, you can think of that pattern of deviations as a wave. Just like a sound wave, it is made up of many frequencies. "And what are the frequencies?" asks Berry. "They're the Riemann zeros. The zeros are harmonies in the music of the primes."

Berry isn't speaking in metaphors. "I've tried to play this music by putting a few thousand primes into my computer," he says "but it's just a horrible cacophony. You'd actually need billions or trillions—someone with a more powerful machine should do it."

There are a few directions I could go here, but behind door number one is the fact that every number theorist I have ever met or known was borderline insane. Furthermore, a few had spent time South of the Border. There is just something about the study whole numbers (and whole numbers only) that self-selects the unbalanced. (Pi springs to mind) The take-home message is that genius is best appreciated from a safe distance.