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

Factorial flight of fancy

Expand Messages
  • Phil Carmody
    I m not expecting this to lead anywhere, but I don t think I ve seen these ideas approached from this particular angle before. I suspect almost everything is
    Message 1 of 4 , Jul 14, 2006
    • 0 Attachment
      I'm not expecting this to lead anywhere, but I don't think
      I've seen these ideas approached from this particular angle
      before. I suspect almost everything is trivial and well-known.

      It's long and rambling - print it out and take it with you
      to the thinking room next time you go there!

      I'm looking at vanishing values of n!%q+/-1 for q prime, n<q.

      (Can you tell I've been sieving for factorial primes?)

      So let's fix q, and work in the ring of integers modulo q.
      The process of evaluating n! for each n is a simple iterative
      process, highly regular, and with clearly defined starting
      points and ending points.

      The sequence always starts:
      1!%q == +1

      And it always ends:
      (q-2)! == +1
      (q-1)! == -1
      (c.f. Wilson's theorem)

      I find the 'gentle landing' most appealing, I synaesthetically picture the
      residues as behaving like a quantum packet starting at, and fading to,
      nothing, but having wild perturbations in the middle:

      vvVVVVVvv
      --^|||||||||||||_--
      ^^WWWWW^^

      Very _unlike_ traditional stochastic behaviour due to the gentle landing
      at the end. So perhaps the behaviour of the residues within the superficially
      chaotic area in the middle will have some interesting patterns.

      The first thing to notice is that the pattern of the residues has a
      symmetry to it.

      i! * (q-1-i)! == +/-1

      Therefore if i!+/-1 vanishes modulo q, then so does (q-1-i)!+/-1.

      If one is like me, one is then immediately led to wonder if there are
      primes q for which the exact middle point, ((q-1)/2)!+/-1, vanishes.
      In fact, they aren't rare at all:

      ptest(p)={
      local(pr=1);
      print1("P = "p" :");
      for(i=2,(p-1)/2,
      pr=pr*i%p;
      if(pr==1,print1(" "i"!-1%"p));
      if(pr==p-1,print1(" "i"!+1%"p))
      );
      print(if(pr^2%p==1,"=middle","")
      )
      forprime(pt=5,100,ptest(pt))

      P = 5 :
      P = 7 : 3!+1%7=middle
      P = 11 : 5!+1%11=middle
      P = 13 :
      P = 17 : 5!-1%17
      P = 19 : 9!+1%19=middle
      P = 23 : 4!-1%23 8!-1%23 11!-1%23=middle
      P = 29 : 10!-1%29
      P = 31 : 15!-1%31=middle
      P = 37 :
      P = 41 :
      P = 43 : 21!+1%43=middle
      P = 47 : 23!+1%47=middle
      P = 53 : 15!-1%53
      P = 59 : 15!+1%59 18!-1%59 29!-1%59=middle
      P = 61 : 8!+1%61 16!+1%61 18!+1%61
      P = 67 : 18!+1%67 33!+1%67=middle
      P = 71 : 7!+1%71 9!+1%71 19!+1%71 35!-1%71=middle
      P = 73 : 17!-1%73
      P = 79 : 23!+1%79 39!+1%79=middle
      P = 83 : 13!+1%83 36!+1%83 41!-1%83=middle
      P = 89 : 21!-1%89
      P = 97 : 43!-1%97

      Summarising:
      a) Primes with +1 at the middle: 3,23,31,59,71,83,...
      b) Primes with -1 at the middle: 7,11,19,43,47,67,79,...
      c) Primes without +/-1 at the middle: 5,13,17,29,37,41,53,61,73,89,97,...

      The pattern behind the dichotomy "+/-1 or not" should have been
      detected after only a few terms. Obviously the families q=4n+1 and
      q=4n+3 have different behaviour.

      That might ring 'jacobi(-1,q)' bells, and one is compelled to
      investigate whether square roots of -1 are in any way relevant.

      Changing the above GP script's final print statement to
      if(pr^2%p==1,print("=middle"),print(" ("pr":"(pr^2+1)%p-1")")
      the investigation leads to an instant conclusion:

      P = 5 : (2:-1)
      P = 13 : (5:-1)
      P = 17 : 5!-1%17 (13:-1)
      P = 29 : 10!-1%29 (12:-1)
      P = 37 : (31:-1)
      P = 41 : (9:-1)
      P = 53 : 15!-1%53 (23:-1)
      P = 61 : 8!+1%61 16!+1%61 18!+1%61 (11:-1)
      P = 73 : 17!-1%73 (27:-1)
      P = 89 : 21!-1%89 (34:-1)
      P = 97 : 43!-1%97 (22:-1)

      Quite simply - if a square root of -1 modulo q exists, it is ((q-1)/2)!

      So apparently we've completely tamed the very centre of that quantum
      packet above. It's either +/-1, or sqrt(-1), depeinding on q%4.

      Curiously, this gives us a deterministic way of uniquely specifying
      a 4th root of unity modulo q. That's something we can't do in C,
      as +/-i are indistinguishable due to the field automorphism that
      exists.

      Of course, these numerical curiosities are nothing more than
      observation as presentled. I don't believe proofs that they are
      not just a coincidence should be too hard. In textbook style,
      I should leave them as an exercise for the reader (and of course
      the writer).

      And once that's been done, the open questions remain -

      1) What's the difference between primes in sequences (a) and (b) above?
      They are already on OEIS, but with no explanation:
      http://www.research.att.com/~njas/sequences/A058302
      http://www.research.att.com/~njas/sequences/A055939

      2) Are there other points apart from the very middle and the ends
      where the sequence can be so simply tamed?

      3) Do higher roots of unity occur with any regularity?
      E.g. for sequence (c), where the primes q do have sqrt(-1), does the
      sequence p!%q+/-sqrtmod(-1,q) vanish at any predictable points?
      P = 37 : 3!+/-i%37
      P = 61 : 21!+/-i%61
      P = 89 : 40!+/-i%89
      P = 101 : 7!+/-i%101 12!+/-i%101
      P = 109 : 14!+/-i%109
      P = 113 : 27!+/-i%113
      P = 149 : 16!+/-i%149
      P = 157 : 21!+/-i%157
      P = 173 : 51!+/-i%173
      P = 181 : 58!+/-i%181
      P = 193 : 34!+/-i%193 69!+/-i%193 79!+/-i%193
      P = 197 : 82!+/-i%197
      I don't see a pattern.

      4) Do double factorials (or higher) have similar properties?
      (I suspect that the double might have, but I've not checked any
      values at all.)

      Does anyone else have any insights into these matters?

      Phil

      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]

      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com
    • Dick
      ... Maybe it s the new format, or Mr. Sloane is quick on the draw, but there are explanations (look in the blue bar above the sequence) Primes p such that p |
      Message 2 of 4 , Jul 14, 2006
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:

        > They are already on OEIS, but with no explanation:
        > http://www.research.att.com/~njas/sequences/A058302
        > http://www.research.att.com/~njas/sequences/A055939


        Maybe it's the new format, or Mr. Sloane is quick on the draw, but
        there are explanations (look in the blue bar above the sequence)

        Primes p such that p | ((p-1)/2)! -1
        Primes p such that p | ((p-1)/2)! +1

        respectively. Go figure huh?


        Regards
        Dick Boland
      • Phil Carmody
        ... That s not an explanation, that s the sequence s definition, and at that, precisely the one I gave. Perhaps I should have said explication instead. Phil
        Message 3 of 4 , Jul 14, 2006
        • 0 Attachment
          --- Dick <richard042@...> wrote:
          > --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:
          > > They are already on OEIS, but with no explanation:
          > > http://www.research.att.com/~njas/sequences/A058302
          > > http://www.research.att.com/~njas/sequences/A055939
          >
          > Maybe it's the new format, or Mr. Sloane is quick on the draw, but
          > there are explanations (look in the blue bar above the sequence)
          >
          > Primes p such that p | ((p-1)/2)! -1
          > Primes p such that p | ((p-1)/2)! +1
          >
          > respectively. Go figure huh?

          That's not an explanation, that's the sequence's definition,
          and at that, precisely the one I gave. Perhaps I should have
          said 'explication' instead.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]

          __________________________________________________
          Do You Yahoo!?
          Tired of spam? Yahoo! Mail has the best spam protection around
          http://mail.yahoo.com
        • thefatphil
          ... wrote: [Stuff - just see: http://tech.groups.yahoo.com/group/primenumbers/ message/18206?threaded=1&var=1&l=1 ] On sci.math just now, Gerry Myerson has
          Message 4 of 4 , Jan 16, 2007
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...>
            wrote:

            [Stuff - just see: http://tech.groups.yahoo.com/group/primenumbers/
            message/18206?threaded=1&var=1&l=1 ]

            On sci.math just now, Gerry Myerson has chipped in the following:

            <<<
            It's shown in Niven, Zuckerman, and Montgomery that if p is 1 mod 4
            then ( (p - 1) / 2 ) factorial squared is -1 mod p (p. 54), and
            it's an exercise to show that if p is 3 mod 4 then the quantity is
            plus-or-minus 1 (exercise 2.1.18).

            Maybe something interesting happens with ( (p - 1) / 3 ) factorial,
            for those primes congruent 1 mod 3.
            >>>

            I instantaniously bought Niven, Zuckerman, and Montgomery (huge, not
            petit), and unless anyone else wants to chip in with a review right
            now, I shall do so when it arrives in a month or so.

            G^HMerry unorthodox Christmas to me!

            Phil
          Your message has been successfully submitted and would be delivered to recipients shortly.