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

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

Expand Messages
  • sleephound
    Primes of the form X^2+Y^2 are of the form 4n+1, Primes of the form X^2+2Y^2 are of the form 8n+1 or 8n+1. Some other examples of quadratic forms yielding
    Message 1 of 12 , Jul 5 7:51 AM
    • 0 Attachment
      Primes of the form X^2+Y^2 are of the form 4n+1, Primes of the form
      X^2+2Y^2 are of the form 8n+1 or 8n+1. Some other examples of
      quadratic forms yielding primes of linear form are listed here:

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

      Primes of the form X^2+11Y^2 begin 47, 53, 103, 163, 199. There
      doesn't appear to be a linear form that separates these primes into
      two groups - I've checked through 4000. Is there some simple rule
      that characterizes these primes? Is there a simple rule for when a
      linear characterization exists?
    • Mark Underwood
      I find this all very interesting, it is new to me. What specifically caught my attention was the linear representation of primes generated by the equation x^2
      Message 2 of 12 , Jul 5 10:56 PM
      • 0 Attachment
        I find this all very interesting, it is new to me. What specifically
        caught my attention was the linear representation of primes generated
        by the equation x^2 + p*y^2, where p is prime. The nature of the
        linear representation is not always the same from prime to prime. Is
        there are rule as Sleephound queried, I'm not sure.

        Below are the representations for p=2, p=3, p=5, p=7 and p=11. The
        p=11 result is courtesy of Sleephound's data, not Wolfram's site.


        From the Wolfram site,

        For p=2 :

        All primes that can be expressed as x^2 + 2y^2 can also be
        represented as 8n+1 or 8n+3. Conversely, if I understand it
        correctly, all primes of the form 8n+1 or 8n+3 can be expressed as
        x^2 + 2y^2.

        All primes that can be expressed as x^2 - 2y^2 can also be
        represented as 8n+1 or 8n+7.

        Observation: There is partial intersection between the two groups.
        One quarter of the primes are not represented at all, that is primes
        of the form 8n + 5.

        For p=3:

        All primes that can be expressed as x^2 + 3y^2 can also be
        represented as 6n+1.

        All primes that can be expressed as x^2 - 3y^2 can also be
        represented as 12n+1.

        Observation: One group is entirely a subset of the other. One half of
        the primes are not represented, that is primes of the form 6n-1.


        For p=5:

        All primes that can be expressed as x^2 + 5y^2 can be also be
        represented as 20n+1 or 20n+9.

        All primes that can be expressed as x^2 - 5y^2 can also be
        represented as 10n+1 or 10n+9.

        Observation: One group is entirely a subset of the other. One half of
        the primes are not represented, that is primes of the form 10n+3 and
        10n+7.

        For p=7:

        All primes that can be expressed as x^2 + 7y^2 can also be
        represented as 14n+1 or 14n+9 or 14n+25.

        All primes that can be expressed as x^2 - 7y^2 can also be
        represented as 28n+1 or 28n+9 or 28n+25.

        Observation: One group is entirely a subset of the other. One half of
        the primes are not represented, that is primes of the form 14n+3 and
        14n+5 and 14n+9.

        For p=11:

        All primes that can be expressed as x^2 + 11y^2 can also be
        represented as 22n+1, 22n+3, 22n+5, 22n+9 or 22n + 15. But the
        converse is not true; not all primes of the form 22n+1, 22n+3, 22n+9
        or 22n+15 can be written as x^2 + 11y^2.

        All primes that can be expressed as x^2 - 11y^2 can be also
        represented as 22n+1 or 22n+3 or 22n+9 or 22n+15. But again, I don't
        think the converse is true.

        Observation: I'm not sure if the two groups overlap even though they
        have the same linear representation. And the fact that the converse
        is not true in this cases sets it apart from the earlier primes. I
        wonder if all the rest of the primes after 11 (13,17,19 ...) are like
        11 in this regard?


        Final Note:

        Also, I noticed from Wolfram's table that all primes of the form x^2
        + y^2 can be written as 4n+1, and (I am supposing) the converse is
        true, all primes of the form 4n+1 can be written as x^2 + y^2. That
        is half the primes. And as we know all of the primes can be written
        as x^2 - y^2.

        It seems that no expression x^2 - by^2 combined with x^2 + by^2 will
        yield all the primes, except of course when b = 1. But it appears
        that the combined *three* expressions, x^2 + y^2, x^2 + 2y^2 and x^2 -
        2y^2 will yield all the primes since they cover all the
        possibilities: 8n+1, 8n+3, 8n+5 and 8n+7. I doubt that any other
        combination of three will yield all the primes. Wait, could it be
        that no combination of four will yield all the primes, even if up to
        two of the above three expressions are used? Further, no combination
        of 5, or 6, or 7 or ....?

        Mark





        --- In primenumbers@yahoogroups.com, "sleephound" <sleephound@y...>
        wrote:
        > Primes of the form X^2+Y^2 are of the form 4n+1, Primes of the form
        > X^2+2Y^2 are of the form 8n+1 or 8n+1. Some other examples of
        > quadratic forms yielding primes of linear form are listed here:
        >
        > http://mathworld.wolfram.com/PrimeRepresentation.html
        >
        > Primes of the form X^2+11Y^2 begin 47, 53, 103, 163, 199. There
        > doesn't appear to be a linear form that separates these primes into
        > two groups - I've checked through 4000. Is there some simple rule
        > that characterizes these primes? Is there a simple rule for when a
        > linear characterization exists?
      • mikeoakes2@aol.com
        In a message dated 06/07/03 06:57:13 GMT Daylight Time, ... In fact, the fraction of primes p congruent to 1 or 3 or 5 or 9 or 15 mod 22 which can be so
        Message 3 of 12 , Jul 6 5:19 AM
        • 0 Attachment
          In a message dated 06/07/03 06:57:13 GMT Daylight Time,
          mark.underwood@... writes:


          > For p=11:
          >
          > All primes that can be expressed as x^2 + 11y^2 can also be
          > represented as 22n+1, 22n+3, 22n+5, 22n+9 or 22n + 15. But the
          > converse is not true; not all primes of the form 22n+1, 22n+3, 22n+9
          > or 22n+15 can be written as x^2 + 11y^2.
          >

          In fact, the fraction of primes p congruent to 1 or 3 or 5 or 9 or 15 mod 22
          which can be so expressed is certainly 1/3.

          Experimental evidence:-
          p_max fraction
          1000 0.29762
          10000 0.3271
          100000 0.32840
          1000000 0.33270
          10000000 0.33283
          100000000 0.33322
          (execution time 35 GHz-mins.)

          Theoretical evidence:-
          David Cox's "Primes of the Form x^2 + ny^2" (Wiley, 1989) proves the following
          Theorem 9.2: Let n > 0 be an integer. Then there is a monic irreducible
          polynomial f(x) of degree h(-4n) such that if an odd prime p divides neither n nor
          the discriminant of f(x) then
          p = x^2 + ny^2 iff
          (-n|p) = 1 and f(x) = 0 mod p has an integer solution.

          [In the above, (-n|p) = is the Legendre symbol, and h(-4n) is the class
          number of the quadratic field Q(sqrt(-4n)).]

          Now (-11|p) = 1 precisely for the above set of 5 residues.

          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
          it's reasonable to assume that it has a root mod p for 1 in 3 values of p, by
          analogy with cubic residuocity.

          > All primes that can be expressed as x^2 - 11y^2 can be also
          > represented as 22n+1 or 22n+3 or 22n+9 or 22n+15. But again, I don't
          > think the converse is true.
          >

          This case is much easier:-
          p = x^2 - 11y^2 iff p = 1 or 5 or 9 or 25 or 37 mod 44.

          Mike Oakes



          [Non-text portions of this message have been removed]
        • mikeoakes2@aol.com
          ... 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
          Message 4 of 12 , Jul 6 9:44 AM
          • 0 Attachment
            > 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]
          • 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 5 of 12 , Jul 6 1:12 PM
            • 0 Attachment
              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 6 of 12 , Jul 6 2:29 PM
              • 0 Attachment
                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 7 of 12 , Jul 6 6:08 PM
                • 0 Attachment
                  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 8 of 12 , Jul 6 8:22 PM
                  • 0 Attachment
                    --- 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 9 of 12 , Jul 7 1:23 AM
                    • 0 Attachment
                      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 10 of 12 , Jul 7 1:31 AM
                      • 0 Attachment
                        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 11 of 12 , Jul 7 6:13 PM
                        • 0 Attachment
                          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 12 of 12 , Jul 8 1:04 AM
                          • 0 Attachment
                            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.