Loading ...
Sorry, an error occurred while loading the content.

p-adic card shuffling cycles

Expand Messages
  • jiva jivazz
    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, 2002
    • 0 Attachment
      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
      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.

      Do you Yahoo!?
      New DSL Internet Access from SBC & Yahoo!
    Your message has been successfully submitted and would be delivered to recipients shortly.