A footnote to my report on Persi Diaconis’ lecture on Martin Gardner.
Persi challenged us to consider the question: Is there a sharp division between “real” mathematics and “recreational” mathematics, and if so, where does it come?
G. H. Hardy clearly thought that there was. He acknowledges that a chess puzzle is mathematics, but clearly distinguishes it from what he and his colleagues do.
Persi took a different view. Telling his own personal story, he explained how he learned to do a perfect riffle shuffle. This involves taking a pack with an even number of cards, dividing it by a cut into two equal packets, and precisely interleaving them so that cards from the two packets alternate. There are two kinds of perfect shuffles: the out-shuffle leaves the top card of the original pack on top, while the in-shuffle places it second, below the top card from the bottom packet.
Persi explained how, once he had learned how to perform perfect shuffles, he was led naturally to the question of how many shuffles are required to return the cards to their original order. For a regular pack of cards, eight out-shuffles or 52 in-shuffles are required.
Consider the number 52. If we number the cards in their initial order from 1 to 52, the perfect in-shuffle takes card k to position 2k, where the numbers are taken modulo 53: thus, card 1 goes to position 2, and card 27 (the top of the second packet) to position 1. Now it happens that 53 is a prime and 2 is a primitive root mod 53, so that the powers of 2 run through all the non-zero numbers mod 53. This explains why 52 shuffles are required; 252 = 1 (mod 53), but no smaller power satisfies this.
This argument works in general; the order of the perfect in-shuffle of an even number n of cards is the order of 2 mod n+1. So the maximum possible order is n, which is realised if and only if n+1 is a prime and 2 is a primitive root of this prime.
Does this happen infinitely open? The Artin conjecture, one of the biggest unsolved problems in mathematics, asserts that it does. The conjecture is open, but has been proved assuming the generalized Riemann hypothesis, an even bigger unsolved problem.
So “recreational” mathematics leads us directly into something which even Hardy was unable to solve!
A fascinating question which fell outside the remit of the lecture is to determine the structure of the group generated by the two perfect shuffles (as permutations of the cards). This was solved by Persi Diaconis, Ron Graham and Bill Kantor in 1983. The most fascinating item in the list is for n = 24, where the group is an extension of an elementary abelian group of order 211 by the Mathieu group M12.