Let’s do the Landau shuffle

Here’s a shuffle I’ve not seen before:

  1. Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
    Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    11 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    then 9 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    then 7 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    then 5 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\
    then 3 cards in the next row:
    \Box\ \Box\ \Box\
    and finally, the remaining 4 cards in the last row:
    \Box\ \Box\ \Box\ \Box\
  2. Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
  3. Finally, reassemble the deck by reversing the order of the placement.

In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.

Now suppose we have a deck of n (distictly labeled) cards, where n>2 is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted S_n and called the symmetric group. The above discussion leads naturally to the following question(s).

Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?

This requires a tiny bit of group theory. You only need to know that any permutation of n symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element g \in S_n, write that element g in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in g as k_1, k_2, \dots , k_m, where k_i>0 are integers forming a partition of n: n = k_1 + k_2 +\dots + k_m. Then the order of g is known to be given by order(g) = LCM(k_1, k_2, ...., k_m), where LCM denotes the least common multiple.

The Landau function g(n) is the function that returns the maximum possible order of an element g \in S_n. Landau introduced this function in a 1903 paper where he also proved the asymptotic relation \lim_{n\to \infty} \frac{\ln(g(n))}{\sqrt{n\ln(n)}}=1.

Example: If n=52 then note 52 = 13+11+9+7+5+3+4 and that LCM(13,11,9,77,5,3,4)=180180.

Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.

def landau_function(n):
L = Partitions(n).list()
lcms = [lcm(P) for P in L]
return max(lcms)

Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):

sage: time landau_function(52)
CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s
Wall time: 1.97 s
180180

Coding Theory and Cryptography

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory

(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

  • Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
  • FISH and I, by W. T. Tutte pdf
  • Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
  • ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
  • The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
  • The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
  • Number Theory and Cryptography (using Maple), by John Cosgrave pdf
  • A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
  • The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
  • Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
  • On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
  • Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
  • Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.


This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.