Over the top

I was having fun browsing the 3D Printing marketplace Shapeways, and then I stumbled across this 17 \times 17 \times 17 Rubik’s Cube by Oskar van Deventer and my brain exploded a little bit.


Van Deventer has designed an impressive collection of cube-like puzzles which can only be made by 3D printing.

I have an older puzzle by him called Topsy Turvy mounted on the wall in my office. This one isn’t 3D printed, but it requires lasers to carefully etch the paths so that the numbered coins can stack perfectly until the very end, and then cascade to make a particular permutation. To me it is not interesting as a puzzle at all (and frankly neither is the 17^3 cube), but I like Topsy Turvy as mathematical art, and especially as a “faithful embedding” of the Mathieu group M12 in physical space.

Increasing public access to federally funded research

65,000 people signed a petition to increase public access to the results of federally funded research, and the White House agreed with them.

A memorandum has been issued telling alL the major federal agencies to make plans for making publicly funded research freely available on the internet within 12 months of publication.

This seems like a big step in the right direction. It will be interesting to see what form the NSF’s plan takes, and how the big publishers respond.

Glimpses of Benoît B. Mandelbrot

The AMS Notices has an article this month with personal recollections about Mandelbrot; mathematical recollections will be saved for another article. He comes across as deeply curious and knowledgeable about almost every subject imaginable.

He was sometimes known for being “strangely vain”, but it is hard to not have the impression that this was the defense mechanism of someone who worked in solitude and obscurity for so many years before his ideas were finally recognized as important.

Mandelbrot gave the closing address of the 2006 International Congress of Mathematicians. He congratulated Werner on his Fields Medal, and suggested that this was the third time a mathematician had won a Fields Medal for proving one of his conjectures.

Yoccoz won a Fields Medal, I believe in part for proving a big piece of the conjecture that the Mandelbrot set is locally connected. Apparently the full conjecture is still open. I don’t know enough about the subject to know if this was something that Mandelbrot originally conjectured though.

Also I wonder who he had in mind as the third Fields Medalist? Does anyone know?

A poetic quote from the article, by Michael Frame:

Years ago, when asked if he was a mathematician, a physicist, or an economist, Benoît replied that he was a storyteller. After Benoît died, I saw another interpretation of his answer. By emphasizing how an object grows, a fractal description of the object is a story. Twists and turns of a snowflake in a cloud, rough waves sculpting a jagged coastline, my lungs growing before I was born, the spread of galaxies throughout the deep dark of space. These share something? Benoît told us they have similar stories. Benoît told us science should tell more stories.

Abel prize for Szemerédi

Hungarian mathematician Endre Szemerédi has been awarded the Abel Prize.

Here is a nice interview with him, translated to English by Zsuzsanna Dancso. (Original in Hungarian here.)

I think Szemerédi’s sense of humor comes across well in the interview.

Interviewer: In 2008, when you were awarded the Rolf Shock prize, you commented that in your opinion the Fields medal, the Wolf Prize, and the Abel Prize were the three most prestigious prizes in mathematics. Did you expect to get one of these back then?

Szemerédi: I would like to modify my opinion — now I only regard the Fields medal and the Wolf prize as the most prestigious.

Is Benford’s law really less true now than ever?

Jialan Wang, an assistant professor of finance at Washington University, has posted a fascinating note about the observable departure from Benford’s law over time. I am trying to imagine any other explanation of this other than widespread fraud (or as she puts it more tactfully, “decreased reliability of accounting data).

Please chime in with your own alternate explanations in the comments.

In search of a counterexample to the Lovász conjecture

It is a celebrated result of John Dixon, (The probability of generating the symmetric group, (subscription) Math. Z. 110 (1969), 199–205.) that if one choose two random permutations in the symmetric group S_n, uniformly (i.e. each with probability 1 / n!), and independently, the probability that the two permutations generate the whole group tends to 3/4 as n \to \infty. It is clear that this probability will never be greater than 3/4, since there is a 1/4 probability that the two permutations will both be even, in which case you could only generate, at most, the alternating group. Interestingly enough, Dixon’s paper covers this possibility, and he actually shows that the probability that two permutations generate the alternating group tends to 1/4 as n \to \infty.

Equivalently, if two random elements x, y of the alternating group A_n are chosen uniformly and randomly, the probability that they generate the group tends to 1 as n \to \infty. This leads me to my question — what is the probability that the 4-regular Cayley graph with generators x, y , x^{-1}, y^{-1} is not Hamiltonian, as n \to \infty?

Showing that this probability is bounded away from 0 would provide a counterexample for a notorious problem about vertex-transitive graphs. So we might expect that this is hard. But is it even possible that it is true, or is there some obvious reason that such graphs will tend to be Hamiltonian?

Another approach in the same spirit would be computational rather than asymptotic. Suppose we look at thousands of random Cayley graphs on the alternating groups A_5 and A_6, for example. It is straightforward to check that they are connected. Is it within reach for a cleverly designed algorithm on modern computers to conclusively rule out Hamiltonicity for a 4-regular graph on 60 or 360 vertices? I would also be happy with a computer-aided proof that the conjecture is false.

Historical note: It is called the Lovász conjecture, even though he just asked the question (and perhaps conjectured the other way). I am under the impression that some prominent people in this field have felt that the answer should be no. In particular Babai does not believe it.

Analyzing card shuffling machines

Diaconis, Fulman, and Holmes have uploaded a preprint titled, “Analysis of Casino Shelf Shuffling Machines.” The paper provides a brief overview of the venerable history of mixing time of card shuffling, all the way back to early results by Markov and Poincaré, and their main point is to analyze a model of shuffle that had not been studied previously. What I found most interesting, though, was their account of successfully convincing people in the business of making card shuffling machines that their machines weren’t adequately mixing up the cards. They gave the manufacturers one mathematical argument, based on total variation distance, that they didn’t accept, and then another argument, based on a card guessing game, that they did.

I’ll describe the card guessing game. I flip through a deck of 52 cards, one card at a time, and before I flip a card you try to guess what it will be. Let’s say you have a perfect memory for every card that’s already been flipped, so you obviously won’t guess those. On the other hand, if the cards are in a truly random order to start out, you obviously don’t have any better strategy than to guess uniformly among the remaining cards. An easy analysis gives that your best possible expected number of correct guesses is {1 \over 52} + {1 \over 51} + \dots + { 1 \over 1} \approx 4.5. On the other hand, the authors described a strategy (conjectured to be best possible) that allows one to guess an average of 9.5 cards correctly, on a totally ordered deck run through the shelf shuffling machine only once. This suggests strongly that the cards are not sufficiently random.

This analysis convinced the company to have the shelf shuffling machine make two passes through the deck, rather than one as they had initially hoped. The president of the company told them that “We are not pleased with your conclusions, but we believe them and that’s what we hired you for.”

Mathematical Zen

In 1974 Frank Harary and Ronald C. Read published a paper with the incredible title, “Is the null-graph a pointless concept?

The abstract reads as follows.

The graph with no points and no lines is discussed critically. Arguments for and against its official admittance as a graph are presented. This is accompanied by an extensive survey of the literature. Paradoxical properties of the null-graph are noted. No conclusion is reached.