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

Re: Is there a simple form for prmes of X^2+11Y^2?

Expand Messages
  • Mark Underwood
    Thanks Mike. Your findings are starting to go over my head but are very appreciated. I shall have to look into this further. Based on your conclusion that p
    Message 1 of 12 , Jul 6, 2003
      Thanks Mike. Your findings are starting to go over my head but are
      very appreciated. I shall have to look into this further.

      Based on your conclusion that "p = x^2 - 11y^2 iff p = 1 or 5 or 9 or
      25 or 37 mod 44", that would mean it covers 1/4 of the primes, since
      these are 5 of the possible twenty residues mod 44. It turns out then
      that the table at Wolfram's site was never meant to be complete but
      just a small sample.

      I found your data that x^2 + 11y^2 covers 1/3 of the primes very
      interesting. And your finding that

      If p is not 2 or 11, then p = x^2 + 11*y^2 iff
      (i) p = 1 or 3 or 5 or 9 or 15 mod 22, and
      (ii) there is an integer solution x to the equation x^3 - 4*x + 4 = 0
      mod p.

      is simply amazing (and beyond my reach right now!).

      Incidentally, a clever and seasoned veteran in these matters informed
      me via email that the three quadratic forms x^2+y^2, x^2+2y^2 and x^2-
      2y^2 are not unique in their ability to cover all the primes as I had
      supposed. As a hint, he showed that x^2+y^2 and x^2+3y^2 cover the
      12n+1, 12n+5, and 12n+7 residues, leaving only the 12n+11 residue
      uncovered. Then he said there is indeed a quadratic form with a small
      b that does cover all the primes of 12n+11 but left it to me to find
      it (!) I wonder if the b is positive. Another hint was to do a seach
      on Bernstein and Atkin's sieve, which I shall do as time allows.

      Mark



      --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:
      > > So the extra condition is that a cubic polynomial has a root mod
      p; I
      > haven't been > able to determine the polynomial explicitly
      >
      > By searching a subspace of the space of all cubics, I have found a
      suitable
      > one (it is not unique), so can state, finally, the following
      Theorem:-
      >
      > If p is not 2 or 11,
      > then p = x^2 + 11*y^2 iff
      > (i) p = 1 or 3 or 5 or 9 or 15 mod 22, and
      > (ii) there is an integer solution x to the equation x^3 - 4*x + 4 =
      0 mod p.
      >
      > The exclusion of 2 and 11 is because the cubic has discriminant -
      176 =
      > -11*2^4.
      >
      > It's interesting that all the candidate cubics had discriminants =
      0 mod 44.
      >
      > Mike Oakes
      >
      >
      > [Non-text portions of this message have been removed]
    • mikeoakes2@aol.com
      In a message dated 05/07/03 15:52:25 GMT Daylight Time, sleephound@yahoo.com ... For there to be a characterisation of the form p = x^2 + n*y2 iff p = r_1 or
      Message 2 of 12 , Jul 6, 2003
        In a message dated 05/07/03 15:52:25 GMT Daylight Time, sleephound@...
        writes:


        > ? Is there a simple rule for when a
        > linear characterization exists?
        >

        For there to be a characterisation of the form
        "p = x^2 + n*y2 iff p = r_1 or r_2 or .. or r_k mod q"
        it is necessary that the class number h(-4*n) = 1 or 2, since that is the
        degree of the polynomial in the subsidiary condition (see my earlier post).

        [Note: h(-4*n) = 2 is ok because it will give a subsidiary equation of the
        form x^2 - b*x + c = 0 mod p, i.e. (b^2 - 4*c)/4 is to be a quadratic residue
        mod p, which, by Gauss's law of quadratic reciprocity, will be true iff p is a
        quadratic residue or nonresidue mod some integer s, which in turn will give a
        condition of the form p = r_1 or r_2 or .. or r_k mod s.]

        The /only/ values of (square-free) n for which this class number condition
        holds are (again from Cohen, Appendix B):-
        h(-4*n) = 1 for n=1,2,3,7.
        h(-4*n) = 2 for n=5,6,10,13,15,22,37,58.

        This explains why tables like that at
        http://mathworld.wolfram.com/PrimeRepresentation.html
        only have entries which are a subset of these particular values of n.

        Mike Oakes


        [Non-text portions of this message have been removed]
      • Satoshi Tomabechi
        On Sun, 6 Jul 2003 08:19:29 EDT ... Hilbert polynomial of the quadratic field with discriminant -44 is x^3-1122662608*x^2+270413882112*x-653249011576832
        Message 3 of 12 , Jul 6, 2003
          On Sun, 6 Jul 2003 08:19:29 EDT
          mikeoakes2@... wrote:
          > And h(-44) = 3 - see e.g. H.Cohen "A Course in Computational Algebraic Number
          > Theory" (Springer, 1996), Appendix B.
          > So the extra condition is that a cubic polynomial has a root mod p; I haven't
          > been able to determine the polynomial explicitly (this stuff is /hard/), but

          Hilbert polynomial of the quadratic field with discriminant -44 is
          x^3-1122662608*x^2+270413882112*x-653249011576832

          Satoshi Tomabechi
        • sleephound
          ... I ve found two places on the web where I think h(-44)=3 ought to show up, and it isn t in either place: http://mathworld.wolfram.com/ClassNumber.html
          Message 4 of 12 , Jul 6, 2003
            --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:

            > And h(-44) = 3 - see e.g. H.Cohen "A Course in Computational
            >Algebraic Number Theory" (Springer, 1996), Appendix B.

            I've found two places on the web where I think h(-44)=3 ought to show
            up, and it isn't in either place:

            http://mathworld.wolfram.com/ClassNumber.html

            http://www.research.att.com/cgi-bin/access.cgi/as/
            njas/sequences/eisA.cgi?Anum=A006203

            I also see some differences from your list here:

            > h(-4*n) = 1 for n=1,2,3,7.
            > h(-4*n) = 2 for n=5,6,10,13,15,22,37,58.

            12 and 28 don't show up for h(-d)=1.
            60 doesn't show up for h(-d)=2.

            Am I doing something wrong, or so these sources disagree with your
            source?
          • mikeoakes2@aol.com
            In a message dated 07/07/03 04:23:08 GMT Daylight Time, sleephound@yahoo.com ... h(-12) = h(-28) = 1 give n = 3 resp. 7. h(-60) = 2 gives n = 15. Ok? Notice
            Message 5 of 12 , Jul 7, 2003
              In a message dated 07/07/03 04:23:08 GMT Daylight Time, sleephound@...
              writes:


              > I also see some differences from your list here:
              >
              > > h(-4*n) = 1 for n=1,2,3,7.
              > > h(-4*n) = 2 for n=5,6,10,13,15,22,37,58.
              >
              > 12 and 28 don't show up for h(-d)=1.
              > 60 doesn't show up for h(-d)=2.
              >
              > Am I doing something wrong, or so these sources disagree with your
              > source?
              >

              h(-12) = h(-28) = 1 give n = 3 resp. 7.
              h(-60) = 2 gives n = 15.
              Ok?

              Notice that I said "..(squarefree) n...". The list for /all/ n is a bit
              longer:-
              h(-4*n) = 1 for n=1,2,3,4,7.
              h(-4*n) = 2 for n=5,6,8,9,10,12,13,15,16,18,22,25,28,37,58.

              In fact, there's quite a serious error in my earlier claim that
              > it is necessary that the class number h(-4*n) = 1 or 2, since that is the
              > degree of the polynomial in the subsidiary condition

              Further reading has made it clear that not only the great Gauss (1801) but
              even before him the mighty Euler (c. 1750) were in posession of /65/ values of n
              which have a "linear" characterisation of the type we are discussing.
              To the above must be added (using our modern notation of class numbers of
              fields):-
              h(-4*n) = 4 for n=21,24,30,33,40,42,45,48,57,60,70,72,
              78,85,88,93,102,112,130,133,177,190,232,253
              h(-4*n) = 8 for n=105,120,165,168,210,240,273,280,312,330,
              345,357,385,408,462,520,760.
              h(-4*n) = 16 for n=840,1320,1365,1848.
              [These values come from David Cox's superb book.]

              Apparently it has since been proved that there is at most one other value of
              n, but no-one has been able to show whether or not it exists!
              This is one of the deepest and richest areas of number theory, still not
              exhausted by centuries of mining.

              Mike Oakes


              [Non-text portions of this message have been removed]
            • mikeoakes2@aol.com
              In a message dated 07/07/03 02:08:44 GMT Daylight Time, ... Thanks! Can you reduce it? (I m no pari expert) - it ought to be equivalent to my cubic. Mike Oakes
              Message 6 of 12 , Jul 7, 2003
                In a message dated 07/07/03 02:08:44 GMT Daylight Time,
                tomabeti@... writes:


                > Hilbert polynomial of the quadratic field with discriminant -44 is
                > x^3-1122662608*x^2+270413882112*x-653249011576832
                >

                Thanks!
                Can you reduce it? (I'm no pari expert) - it ought to be equivalent to my
                cubic.

                Mike Oakes



                [Non-text portions of this message have been removed]
              • Satoshi Tomabechi
                On Mon, 7 Jul 2003 04:31:45 EDT ... x^3 - x^2 + x + 1 ... It says that two polynomials define the same (class) filed. You can use another Weber polynomial x^3
                Message 7 of 12 , Jul 7, 2003
                  On Mon, 7 Jul 2003 04:31:45 EDT
                  mikeoakes2@... wrote:

                  > > Hilbert polynomial of the quadratic field with discriminant -44 is
                  > > x^3-1122662608*x^2+270413882112*x-653249011576832
                  > >
                  >
                  > Thanks!
                  > Can you reduce it? (I'm no pari expert) - it ought to be equivalent to my
                  > cubic.


                  x^3 - x^2 + x + 1

                  David Broadhurst told me:
                  >? polred(x^3-1122662608*x^2+270413882112*x-653249011576832)
                  >%1 = [x - 1, x^3 - x^2 - x - 1, x^3 - x^2 + x + 1]
                  >so x^3-x^2-x+1 seems to do the same job?
                  It says that two polynomials define the same (class) filed.

                  You can use another Weber polynomial x^3 - 2*x^2 + 2*x - 2,
                  which also defines the same field.

                  Satoshi Tomabechi
                • mikeoakes2@aol.com
                  In a message dated 08/07/03 02:14:47 GMT Daylight Time, ... Thank you. Meanwhile, (pari Grand Master) David Broadhursthas emailed me with ... So that s good !
                  Message 8 of 12 , Jul 8, 2003
                    In a message dated 08/07/03 02:14:47 GMT Daylight Time,
                    tomabeti@... writes:

                    >> Can you reduce it? (I'm no pari expert) - it ought to be equivalent to my
                    >> cubic.
                    >
                    > x^3 - x^2 + x + 1

                    Thank you.
                    Meanwhile, (pari Grand Master) David Broadhursthas emailed me with
                    > henri cohen's "minimal height" form for your d=-44 cubic is
                    > x^3-x^2+x+1

                    So that's good ! - there's complete agreement between your theoretical
                    Hilbert polynomial and my experimentally discovered cubic.

                    Mike Oakes



                    [Non-text portions of this message have been removed]
                  Your message has been successfully submitted and would be delivered to recipients shortly.