When we say “perfect shuffle,” it means to cut the deck in half, then interleave the cards from the two halves. There are actually two choices here, depending on which card we put on top. We can send card 0 to 0, card 26 to 1, card 1 to 2, …, card 25 to 50, card 51 to 51 (we’ll call this Shuffle 1), or we can send card 26 to 0, card 0 to 1, card 27 to 2, …, card 51 to 50, card 25 to 51 (we’ll call this Shuffle 2). Shuffle 1 is what we deal with, because the statement doesn’t work for Shuffle 2. But note that Shuffle 2 is just Shuffle 1 followed by exchanges of pairs.

So, the effect of shuffling on the first half of the deck (\(n \in \{ 0, \dots ,25 \}\)) is to send card \(n\) to \(2n\). Notice that a perfect shuffle looks the same if we flip the deck around, so the effect on the second half of the deck (\(n \in \{26, \dots ,51 \}\)) is to send card \(n\) to \(R(2R(n))\), where \(R(n) = 51-n\) is the operation that gives the reversed index of card \(n\).

Immediately, we see that 8 shuffles works because \(2^8 n \equiv n\ (mod\ 51)\), and

The last statement is because if \((2^s -1) n \equiv 0\ (mod\ d-1)\) for \(n=1\), then it must be true for all \(n>1\). (The case \(n=0\) is trivial.)

There are more interesting observations. If \(s\) shuffles brings a deck to its original order, then surely \(ks\) shuffles does that, too. And indeed, if \(d-1\) divides \(2^s – 1\), then it also divides \(2^{ks} – 1\), which factors as \((2^s – 1)(2^{(k-1)s} + 2^{(k-2)s} + \cdots + 2^s + 1)\).

In another observation, we can explicitly write the card position after \(s\) shuffles as

\(2(\dots 2(2n – 51 b_1(n)) – 51 b_2(n) \dots) – 51 b_s(n)\ \ \ \ (*)\)

where \(b_i(n)\) is an indicator bit that is 1 if, entering the \(i\)th shuffle, the card is in the second half of the deck, and 0 otherwise.

Expanding \((*)\), we get \(2^s n – 51 (2^{s-1} b_1(n) + 2^{s-2} b_2(n) \cdots 2^1 b_{s-1}(n) + 2^0 b_s(n)) \)

Now, define \(b(n) \equiv 2^{s-1} b_1(n) + 2^{s-2} b_2(n) \cdots 2^1 b_{s-1}(n) + 2^0 b_s(n)\). Clearly, \(\overline{b_1(n) b_2(n) \dots b_s(n)}\) is the binary expansion of \(b(n)\).

So \(s\) shuffles brings the deck back to its original order if and only if \(2^s n – 51 b(n) = n\) for all \(n\), i.e. \(b(n) = \frac{2^s – 1}{51}n\). But we know that 51 divides \(2^s – 1\) in our example, so \(\frac{2^s – 1}{51}\) is an integer, and in general

In the case of \(s=8\) and \(d=52\), \(b(1) = 5\).

Now we can also find the minimum number of shuffles to return various deck sizes to identity, by looking at the factors of \(2^s-1\):

etc…

Of course, every deck of size \(d\) can be returned to its original order in some number of shuffles: at most \(d!\) (and if fewer, then the number of shuffles divides \(d!\)), this is because the automorphism group of \(d\) elements is at most size \(d!\). This knowledge is of no practical utility, since \(d!\) is huge, but it does imply that any odd positive integer \(d-1\) divides \(2^{d!} – 1\). And, it highlights the fact that some deck sizes are very special: any \(d\) that is a power of 2 only takes \(\log d\) shuffles, surely; but especially 52, for such a large deck size that isn’t a power of 2, the fact that it only takes 8 shuffles is quite amazing.

I do wonder if there are any “bad” deck sizes \(d\) that do take up to \(d!\) shuffles to return to the original order. A search of the factors of Mersenne numbers may be in order.

First there was a seminar (which I missed) with this kind of description

How grid cell neurons encode rat position

Recently it was discovered that neurons in an area of the cortex (called dMEC) of rats, fire on every vertex of a regular triangular lattice that tiles 2-d space. These so-called “grid cells” efficiently encode rat position in a system that can be shown is analogous to a residue number system (RNS). By interpreting measured dMEC properties within an RNS framework, we can estimate the amount of position information stored within dMEC, and show how an RNS-like scheme is particularly well-suited to store and update positional information.

That tipped me off to this really amazing paper:
Microstructure of a spatial map in the entorhinal cortex by Hafting, Fyhn, Molden, Moser, and Moser.

It turns out, through experiments on rats, that in the “dorsocaudal medial entorhinal cortex” are a collection of neurons called “grid cells” that together ingeniously encode a coordinate chart for the rat to do internal path integration. The neurons respond when the rat is in certain positions in a standard environment — so what, you say. But no, if you plot the rat positions in the environment at which one particular neuron responds, the positions form a hexagonal lattice!

What?

Neighboring cells have slightly shifted lattices for their positions of response, and there are other cells whose associated lattices are at a different angles or scales.

What good is this? Well, it implies a structurally coded representation of position. Suppose you had to encode a discretized 1D position, so a number between 1 and something, let’s say 15. You can use a sparse representation, which is to say, one neuron dedicated to respond to each of the 15 positions. You can use a binary code, and that would take 4 bits; the way to implement it might be a neuron that responds to positions 1-7, another one to positions 8-15, yet another one for positions 1-3, 8-11, another one for positions 4-7, 12-15, etc. That would take a total of 8 neurons. That’s pretty much an efficient representation. The way that it works in the dMEC is more like one neuron encodes all positions that are 1 (mod 3), another for 2 (mod 3), another for 0 (mod 3), another for 1 (mod 5), one for 2 (mod 5), and so on, for a total of 8 neurons again. These eight neurons repond to points on a lattice of distance 3 or a lattice of distance 5, and the response is narrowly confined. This is what the original seminar meant by residue number system encoding. The same extends to 2D, with the consequence that only on the order of log-of-the-number-of-positions neurons are needed, instead of on the order of the-number-of-positions, are needed to code a position. The advantage of a residue code over a binary (or n-ary) code is the possibility of using neural devices that have fairly similar properties (modulus 3, 5, etc.), instead of ones whose modulus scaling must bridge exponentially larger gaps (2, 4, 8, etc.).

This is about the most elegant representation of a coordinate chart that one can think of. Even decoding seems easy: just sum all the responses onto an unfolded chart — the hippocampus if I understand correclty, and choose the tallest peak.

There is a bit more complexity than described above, since the responses are not discretized in space, but are functions over a continuous space, and the residue arithmetic is not over a discrete set, either. I can’t find any experimental data on how responses of different dMEC neurons actually correlate, so how the coding works exactly is still speculation. But I can imagine this being much like random binning, and nested lattice Wyner-Ziv distributed rate-distortion coding. In fact, those are the first things that came to mind. With even a little bit of angular variance or half-phase lattice dithering, a small number of lattices would already be able to code for position with very low distortion by emulating random binning. I don’t think multiple rotated lattices of different scales (but non-nested) have been considered as a model for distributed rate-distortion coding. If properly chosen, the decoding complexity ought not to be that high. There is something to learn from the brain.