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

Re: [PrimeNumbers] Digest Number 2692

Expand Messages
  • Kermit Rose
    ... I intuitively felt that the cyclotomic polynomial for n, Phi(n) = (x-k1)(x-k2). . . (x-k_m) mod n where m is the number of positive integers
    Message 1 of 3 , May 10, 2009
    • 0 Attachment
      primenumbers@yahoogroups.com wrote:
      > ________________________________________
      > ________________________________________________________________________
      > 3a. Re: Cyclotomic polynomial puzzles
      > Posted by: "Phil Carmody" thefatphil@... thefatphil
      > Date: Sun May 10, 2009 3:09 am ((PDT))
      >
      >
      >
      >> --- On Sat, 5/9/09, Phil Carmody <thefatphil@...>
      >>
      >>> 3a) Can you categorise p,q,r such that Phi(pqr) only has
      >>> coefficients in {-1,0,1}?
      >>> b) Can you find a bigger pqr with that property than
      >>> anyone else?
      >>>
      >
      > For largest-smallest, lets place a stake in the ground at p=29 with
      > n = 29*31*5393 = 4848307
      >
      > It appears that swift evaluation of cyclotomic polynomials is the hard part - it requires large quantities of both CPU power and RAM. I wonder if there's a way using modular arithmetic, or even p-adic arithmetic to reduce the quantity of computation or storage.
      >
      > Phil
      >
      >
      >

      I intuitively felt that the cyclotomic polynomial for n,

      Phi(n) = (x-k1)(x-k2). . . (x-k_m) mod n

      where m is the number of positive integers < n, which are relatively
      prime to n,
      and the k1,k2,...k_m

      are the m positive integers < n, that are relatively prime to n.


      My intuition was not focused enough for me to see why I thought this.

      I do not know why I expected that the coefficients of the cyclotomic
      polynomial for n,
      would never be greater than or equal to n.


      David, can you give me a proof of this equation?

      If this characterization of Phi(n) is true, for all n,

      then using it, the difficulty of calculating the cyclotomic polynomial
      is of approximately the same
      order as the difficulty of calculating the integers relatively prime to n.


      Kermit
    • David Broadhurst
      ... You need to set k_r = exp(2*Pi*I*r/n) and remove the mod n . For example, with n = 4, we get Phi(4) = (x - I)*(x + I) = x^2 + 1 which is not equivalent to
      Message 2 of 3 , May 10, 2009
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        Kermit Rose <kermit@...> wrote:

        > Phi(n) = (x-k1)(x-k2). . . (x-k_m) mod n
        > where m is the number of positive integers < n,
        > which are relatively prime to n, and the k1,k2,...k_m
        > are the m positive integers < n, that are relatively prime to n.

        You need to set
        k_r = exp(2*Pi*I*r/n)
        and remove the "mod n".

        For example, with n = 4, we get

        Phi(4) = (x - I)*(x + I) = x^2 + 1

        which is not equivalent to your "modular construction"

        print(lift((x-Mod(1,4))*(x-Mod(3,4))))
        x^2 + 3

        since 1 and 3 are inequivalent modulo 4.

        David
      • Maximilian Hasler
        ... For the case at hand (order 3), it might be interesting, though, to use Phi_n(x)=product_(d|n)(1-x^(n/d))^mu(d) or maybe
        Message 3 of 3 , May 10, 2009
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote:
          > You need to set k_r = exp(2*Pi*I*r/n) and remove the "mod n".
          > For example, with n = 4, we get
          > Phi(4) = (x - I)*(x + I) = x^2 + 1
          > which is not equivalent to your "modular construction"
          > since 1 and 3 are inequivalent modulo 4.

          For the case at hand (order 3), it might be interesting, though, to use

          Phi_n(x)=product_(d|n)(1-x^(n/d))^mu(d)

          or maybe

          phi(n)=exp(sumdiv(n,d,moebius(d)*log(1-x^(n/d)+O(x^eulerphi(n)))))

          (Dealing with the terms in an appropriate order, has anyone an idea for a significant "non-flat rejection criterion" ?)

          Maximilian

          (PARI)
          phi(n)=my(d=divisors(n));prod(i=1,#d,(1-x^(n/d))^moebius(d[i]))
        Your message has been successfully submitted and would be delivered to recipients shortly.