Expand Messages
• Dear Dr. Diaconis.: (cc. Primenumbers@yahoogroups.com) According to a number theory book I have (Andrews, Dover, I believe), the number of shuffles (what Herb
Message 1 of 1 , Sep 29 7:25 PM
According to a number theory book I have (Andrews,
Dover, I believe), the number of shuffles (what Herb
Conn calls "in-shuffles", i.e. per Herb "If top and
bottom cards remain on top and bottom, it is called an
out-stack, out-deal, or out-shuffle. If top and
bottom cards become adjacent at the center of the
deck, it is called an in-stack, in-deal, or
in-shuffle.") needed to return the cards to the
original positions is identical to the order of a MOD
p (least exponent of a for which a^e is congruent to 1
MOD p); where the numbers of cards is p+1. Herb Conn
(his letter to be sent in the regular mail);
independently confirmed these results matching Table
48 in Beiler's Recreations in Number Theory, Dover.
Herb's chart is simply a 90deg. rotation of Beiler's
chart; for example, Herb has a vertical list comprised
of Number of Cards, then : in-shuffle. For 52 cards,
the result is 52. We see this in Beiler's chart #48
where you add 1 to the number of cards, getting the
heading 53 at top, a prime. Then look under the result
for a=2 and it's 52 (2 is a primitive root of 53). My
conjecture is that for a generalized card shuffling
operation, analogous results apply where a 3-shuffle =
alternate 3rd card, 4th - alternate 4th card, etc; and
that such results match Beiler's whole chart. If this
is true, then for p=53, cards = 52; we look down the
column for the least of the least exponents (Beiler
has 2 through 100); and it's 4, for a=23,30,76 and 83;
but 52 has 2 and 53 has "1" (trivial). At any rate, a
proof was provided by Phil Carmody, posted on
Primenumbers that the relationship between a 2 shuffle
and a 4 shuffle is that when the least exponent for
base 2 is even, the least exponent for base 4 is 1/2
that of 2. But when the least exponent for base 2 is
odd, base 4 has the same result. Example: for a 2
shuffle, there are 52 cards and we use n+1 = 53.
Beiler's chart has least exponent (order of 2, MOD
p=53) is 52, but this is even so it's 26 for base 4.
Next, there's an interface between this topic and
cyclic polynomials relating to chaos and polygons. An
abstract of the article by Dr. Jay Kappraff and
myself may be seen by entering "Polygons and Chaos"
into Google. It comes up first on the list. I'm
sending you a copy of the paper in the mail but will
summarize (briefly), some salient features. :There are
4 sets of polymonials governing the cycle lengths or
(more typically, "order of a, MOD p"); as with a=2 p =
53 for card shuffling.; and another set is for
cyclotomic n-gons, referred to as nth cyclotomic
polynomial. The Lucas polys are one such set L1 = x,
L2 = x^2-2, L3 = x^3-3x, L4= x^4-4x^2+2, etc where
coeff. sums are the Lucas numbers; but we are
literally "dealing" with base 2 so the corresponding
poly is x^2 - 2. Seeds for Lucas Polys are 2 Cos
2Pi/N, N is odd. Exercise..take any such seed, perform
iterations and you will get a result shown in Beiler's
chart, thus isomorphic with generalized
card-shuffling; (and my conjecture for generalized
shuffles besides "2"). However, there's one small
rule: for nth poly, the least exponent applies to n^2
(then we can get the result for a=2 from the
previously mentioned rule that if least exponent is
odd, the result is the same for 2 and 2^2; while if
the least exponent is even, the result for 4 is 1/2
that for base 2. Example: for p=7, under a=2,
Beiler's chart shows "3" for base 2, since 2^3 is
congruent to 1 MOD 7, while the least exponent for 4
is also 3. The rule: nth poly applies to n^2 base.
Example In the Lucas set, 2nd poly is x^2-2, seed 2
Cos 2Pi/N, so for p=7, the result is 3, while for p=11
(10cards), base 2 exponent is 10 while it's 5 for base
4. For 52 cards, (p=53), base 2 has 52 while it's 26
for base 4. Thus, for the 53-gon, Lucas set, the poly
is x^2-2 and you would get a p-adic cycle length of
26. But there are 3 other sets of polys. Regardless
of which set you use, the results match Beiler's
chart: (and thus, I propose, a generalized
card-shuffling outcome). The other sets, 2nd poly
(thus, base 4); are: Chebyshev: T2 = 2x^2-1, seeds Cos
2Pi/N, Conn#1 = 4x(1-x) seed Sin^2 2Pi/N, and Conn#2:
2x/(1-x^2), seed Tan 2Pi/N. Sincerely, Gary W.