7
$\begingroup$

All small (rational) primes I've looked at seem to be irreducible elements in the ring $\mathcal{O}_{\mathbb{Q}(\sqrt{577})}$. Often they're irreducible but not prime. And of course $577 = (\sqrt{577})^2$.

Looking at ideals, it's clear that $$\langle 2 \rangle = \left\langle 2, \frac{1}{2} + \frac{\sqrt{577}}{2} \right\rangle^2,$$ $$\langle 3 \rangle = \left\langle 3, \frac{1}{2} - \frac{\sqrt{577}}{2} \right\rangle \left\langle 3, \frac{1}{2} + \frac{\sqrt{577}}{2} \right\rangle,$$ $\langle 5 \rangle$ and $\langle 7 \rangle$ are prime, etc.

It's then not difficult to find failures of unique factorization such as $$12 = 2^2 \times 3 = (-1) \left(\frac{23}{2} - \frac{\sqrt{577}}{2} \right) \left(\frac{23}{2} + \frac{\sqrt{577}}{2} \right).$$

But I can't seem to find a case of principal ideals $\langle a \pm b \sqrt{577} \rangle$, with nonzero $a, b \in \mathbb{Q}$ (either integers or halves of integers, to be precise) having prime norm.

For contrast, observe that in $\mathbb{Z}[\sqrt{15}]$ (not UFD either), we have $\langle 11 \rangle = \langle 2 - \sqrt{15} \rangle \langle 2 + \sqrt{15} \rangle$.

Is this theoretically impossible in $\mathcal{O}_{\mathbb{Q}(\sqrt{577})}$, or have I just not looked far enough?

EDIT: Thanks to quid for editing my question to be more precise in regards to terminology. I am editing the question now because in my non-UFD example I used $24$ when I should have used $12$. It seems no one would have caught that but it was bothering me.

$\endgroup$
  • $\begingroup$ Represented (positive) primes, by the principal form, up to 5000: 283 293 433 541 569 577 719 787 941 1097 1187 1429 1451 1531 1579 1663 1867 2003 2029 2083 2203 2339 2551 2671 2693 2999 3023 3083 3089 3253 3257 3271 3593 3607 3643 3779 3877 4021 4127 4253 4339 4409 4457 4517 4643 4793 4937 $\endgroup$ – Will Jagy Dec 20 '16 at 23:17
9
$\begingroup$

Here is a theoretical approach, which uses a bit of class field theory to show that there will be infinitely many such primes.

Let $H$ be the Hilbert class field of $K=\mathbb Q(\sqrt{577})$, the maximal, everywhere unramified abelian extension of $K$.

Theorem: A prime ideal $\mathfrak p\subset\mathcal O_K$ is principal if and only if it splits completely in $H$.

You are looking for rational primes $p$ which split in in $\mathbb Q(\sqrt{577})$ and such that the prime ideals above $p$ are principal. Hence, the primes you are after (except maybe for the finitely many ramified primes) are exactly the primes which split completely in $H$. The Cebotarev density theorem guarantees that there will be infinitely many such primes.

This argument generalises to any number field $K$: either it is a UFD or there are infinitely many primes which are norms from $K$.


The following Sage code spits out some of the primes you're after ($577$ is missing because it is ramified)

K.<a> = NumberField(x^2 - 577)
L = K.hilbert_class_field('b')

for p in prime_range(15000):    
    splits = false
    for P in L.primes_above(p):
        if P.residue_class_degree() == 1 and P.absolute_ramification_index() == 1: 
            splits = true
            break
    if splits: print p

With output beginning

283 293 433 541 569 719 787 941 1097 1187 1429 1451 1531 1579 1663 1867 2003 2029 
$\endgroup$
  • $\begingroup$ They are just the primes represented by $x^2 - 577 y^2.$ In this case, $-p$ is represented if and only if $p$ is represented. $\endgroup$ – Will Jagy Dec 21 '16 at 1:24
  • 1
    $\begingroup$ @WillJagy Yes indeed. I think it's always nice to see both quadratic form and the ideal theoretic side of the story. I also think it's important to stress that any problem of this type comes down to the splitting of primes in some larger extension, in this case the Hilbert class field. $\endgroup$ – Mathmo123 Dec 21 '16 at 10:58
  • $\begingroup$ In case of interest: John Horton Conway introduced a method ("topograph") which is well suited to finding the positive primes represented by an indefinite form. My version is a single C++ program, it has no .h file. I could email that to you. It is not even very long, under 300 lines. $\endgroup$ – Will Jagy Dec 21 '16 at 17:35
  • $\begingroup$ Well, I put the entire program in a separate answer. Anyone can copy out the program itself, give it the correct file name, compile and then use. There are some extra commands there, in case one takes out the condition that represented numbers be prime, there is a command to display factors; if using that, probably better to go back to one displayed number per line. If altering, best to make a copy under a slightly different filename, which alters the compile command and the line for using it as well. $\endgroup$ – Will Jagy Dec 21 '16 at 17:50
5
$\begingroup$

I should probably add that, as $$ 1 + 24^2 = 577 \equiv 1 \pmod 8, $$ it follows that the integral quadratic forms $$ x^2 + 23 xy - 12 y^2 $$ and $$ x^2 - 577 y^2 $$ represent exactly the same ODD numbers. This includes the odd primes in which you are interested.

prime = x^2 - 577 y^2
prime    283  x  74  y  3
prime    293  x  51  y  2
prime    433  x  289  y  12
prime    541  x  433  y  18
prime    569  x  99  y  4
prime    577  x  577  y  24
prime    719  x  36  y  1
prime    787  x  218  y  9
prime    941  x  57  y  2
prime    1097  x  195  y  8

This argument is elementary: if $$ x(x + 23 y) - 12 y^2 $$ is odd, it means both $x$ and $x+23y$ are odd. However, $x$ being odd means $23 y = x + 23 y - x$ is even, therefore $y$ is even. Write $y = 2 w.$ Now we have $$ x^2 + 46 xw - 48 w^2. $$ Next, take $v = x + 23 w,$ so $x = v - 23 w.$ The result is $$ v^2 - 577 w^2. $$

These are the droids you seek:

jagy@phobeusjunior:~$ ./Conway_Positive_Primes 1 23 -12 5000 577
           1          23         -12   original form 

           1          23         -12   Lagrange-Gauss reduced 



 Represented (positive) primes up to  5000

   283   293   433   541   569   577   719   787   941  1097
  1187  1429  1451  1531  1579  1663  1867  2003  2029  2083
  2203  2339  2551  2671  2693  2999  3023  3083  3089  3253
  3257  3271  3593  3607  3643  3779  3877  4021  4127  4253
  4339  4409  4457  4517  4643  4793  4937

==============================================================

I wrote something about how binary quadratic forms map to number field orders: http://math.blogoverflow.com/2014/08/23/binary-quadratic-forms-over-the-rational-integers-and-class-numbers-of-quadratic-%EF%AC%81elds/

For what it is worth, the class number is $7.$ The principal form also represents $-1.$

577    factored    577

    1.             1          23         -12   cycle length             6
    2.             2          23          -6   cycle length             6
    3.             3          23          -4   cycle length             6
    4.             4          23          -3   cycle length             6
    5.             6          23          -2   cycle length             6
    6.             6          19          -9   cycle length            10
    7.             9          19          -6   cycle length            10

  form class number is   7

================================================================

The ordering above is the way my program displays the forms, very handy for some purposes. To see the group operation using Dirichlet's method for composition, better to make all the middle coefficients 33, although this makes all coefficients positive. The forms are still indefinite. I ought to mention that these forms are not in the same order as before; there is a bijection with $SL_2 \mathbb Z$ equivalence.

 1     33    128
 2     33     64
 4     33     32
 8     33     16
16     33      8
32     33      4
64     33      2

================================================================

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle 1 23 -12

  0  form              1          23         -12


           1           0
           0           1

To Return  
           1           0
           0           1

0  form   1 23 -12   delta  -1     ambiguous  
1  form   -12 1 12   delta  1
2  form   12 23 -1   delta  -23
3  form   -1 23 12   delta  1     ambiguous            -1 composed with form zero  
4  form   12 1 -12   delta  -1
5  form   -12 23 1   delta  23
6  form   1 23 -12


  form   1 x^2  + 23 x y  -12 y^2 

minimum was   1rep   x = 1   y = 0 disc 577 dSqrt 24  M_Ratio  576
Automorph, written on right of Gram matrix:  
-49  -1152
-96  -2257
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
$\endgroup$
  • $\begingroup$ Thanks Will! I suspected as much, but it's great to have real computing power to verify. :) $\endgroup$ – Adam Hughes Dec 20 '16 at 23:41
4
$\begingroup$

The theoretical answer above is correct (although this answer has been edited to be less informative), but one can also give a concrete example. $$(719)=(36+\sqrt{577})(36-\sqrt{577})$$

$\endgroup$
  • $\begingroup$ Represented (positive) primes, by the principal form, up to 5000: 283 293 433 541 569 577 719 787 941 1097 1187 1429 1451 1531 1579 1663 1867 2003 2029 2083 2203 2339 2551 2671 2693 2999 3023 3083 3089 3253 3257 3271 3593 3607 3643 3779 3877 4021 4127 4253 4339 4409 4457 4517 4643 4793 4937 $\endgroup$ – Will Jagy Dec 20 '16 at 23:10
  • $\begingroup$ Hey Rene, which part of my answer has made it less informative in your opinion, I think each iteration has only added more clarity to the best of my ability to judge. $\endgroup$ – Adam Hughes Dec 20 '16 at 23:37
  • $\begingroup$ @AdamHughes At first you talked about density theorems. But now I don't see that much is being said. $\endgroup$ – Rene Schipperus Dec 20 '16 at 23:42
  • $\begingroup$ @ReneSchipperus I see yes, but you'll note the revised version adheres to the same principal since we know squares take up half of the residue classes and the principal ideals take up $1/7$ of the ideal classes, it's still inherently a density result, just stated more precisely. $\endgroup$ – Adam Hughes Dec 20 '16 at 23:43
  • $\begingroup$ @AdamHughes I see, well I thought the original was clearer. I personally have a preference for concise answers. $\endgroup$ – Rene Schipperus Dec 20 '16 at 23:45
3
$\begingroup$

I looked, my program for showing the positive primes represented by an indefinite form is actually quite short. I will put a brief demonstration run below, then the full program. The method is due to John Horton Conway, in chapter one of his little book The Sensual Quadratic Form. Another book was very helpful with the diagram ("topograph"), John Stillwell, Elements of Number Theory, especially pages 38-39, 90-100.

Worth emphasis: at first glance, the problem of finding the numbers with small absolute value represented by an indefinite quadratic form seems messy, we cannot just bound the variables. Conway's topograph method turns the picture around; there is a "river" along which the values of the form repeat forever. Then, the farther we move away from the river, the larger the absolute values get. One side of the river is numbers (primitively) represented. It turns out to be a finite set of rooted trees, where the roots are locations on the river. Values of the form are not at the graph vertices or the edges, rather values are in the spaces in between edges. Each space off the river has a "level" away from the river, compared with the values along the river itself. At each level, we get a value with the minimum (absolute value) for that level. Once we do enough layers for that minimum to exceed the bound we wanted, we are done. Deterministic and definitive.

jagy@phobeusjunior:~$ g++  -o     Conway_Positive_Primes     Conway_Positive_Primes.cc  -lm
In file included from /usr/include/c++/4.8/backward/strstream:51:0,
                 from Conway_Positive_Primes.cc:12:
/usr/include/c++/4.8/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp]
 #warning \
  ^
jagy@phobeusjunior:~$ ./Conway_Positive_Primes  1 1 -2  50  13
           1           1          -2   original form 

square discriminant  9

jagy@phobeusjunior:~$ ./Conway_Positive_Primes  1 1 -3  50  13
           1           1          -3   original form 

           1           3          -1   Lagrange-Gauss reduced 



 Represented (positive) primes up to  50

     3    13    17    23    29    43

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=   
 these are the collection of remainders when dividing by   13

      0      3      4     10



 Represented (positive) primes up to  50  and value mod    13

           1           1          -3   original form 

jagy@phobeusjunior:~$ 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <strstream>


using namespace std;




//  this file is named     Conway_Positive_Primes.cc 
//  main writing   June 2014


// to compile
//        g++  -o     Conway_Positive_Primes     Conway_Positive_Primes.cc  -lm




void insert_primitive_reps(unsigned int a, unsigned int h, unsigned int b, unsigned int M,  set<unsigned int>  *setPtr)
{
 // cout << setw(12) << a  << setw(12) << h  << setw(12) << b << "   insert_primitive_reps"    << endl;
  if ( a <= M )
  {
    (*setPtr).insert(a);
    if ( b <= M )
    {
      (*setPtr).insert(b);
      if ( a <= M - b && h <= M - a - b)
      {
        if( a <= M - a - h ) insert_primitive_reps(a, h + 2 * a, a + b + h, M, setPtr);
        if( b <= M - b - h ) insert_primitive_reps(a + b + h, h + 2 * b,b, M, setPtr);
         // comment: once a+b+h <= M, min(2a+h, 2b+h) <= M
      }  // if a + b + h
    } // if  b
  } // if a

} // end insert_primitive_rep



int IntSqrt(int i)
{
  // cerr << "called intsqrt  with   " << i << endl;
  if ( i <= 0 ) return 0;
  else if ( i <= 3) return 1;
  else if ( i >= 2147395600) return 46340;
  else
  {
    float r;
    r = 1.0 * i;
    r = sqrt(r);
    int root = (int) ceil(r);
    while ( root * root   <= i ) ++root;
    while ( root * root   > i ) --root;
    return  root ;
  }
}


string stringify(int x)
 {
   ostringstream o;
   o << x  ;
   return o.str();
 }


string Factored(unsigned int i)
{
  string fac;
  fac = " = ";
  int p = 2;
 unsigned int temp = i;
  if (temp < 0 )
  {
    temp *= -1;
    fac += " -1 * ";
  }

  if ( 1 == temp) fac += " 1 ";
  if ( temp > 1)
  {
    int primefac = 0;
    while( temp > 1 && p * p <= temp)
    {
      if (temp % p == 0)
      {
        ++primefac;
        if (primefac > 1) fac += " * ";
         fac += stringify( p) ;
        temp /= p;
        int exponent = 1;
        while (temp % p == 0)
        {
          temp /= p;
          ++exponent;
        } // while p is fac
        if ( exponent > 1)
        {
          fac += "^" ;
          fac += stringify( exponent) ;
        }
      }  // if p is factor
      ++p;
    } // while p
    if (temp > 1 && primefac >= 1) fac += " * ";
    if (temp > 1 ) fac += stringify( temp)  ;
  } // temp > 1
  return fac;
} // Factored


int PrimeQ(int i)
{
  if ( i < 0 ) i *= -1;
  if ( i <= 3) return 1;
  else
  {
    int boo = 1;
    int j = 2;

    while (boo && j * j   <= i )
    {
      if ( i %  j  == 0) boo = 0;
      ++j;
    }
    return boo;
  }
}


int main(int argc, char *argv[])
{
  if ( argc != 6) cout << "Usage: ./Conway_Positive_Primes A B C      Bound    Modulus " << endl;
  else {



  int a,b,c, discr;
     int N,M;
    a = atoi(argv[1]);
        b = atoi(argv[2]);
    c = atoi(argv[3]);
   M = atoi(argv[4]);
     N = atoi(argv[5]);
 cout << setw(12) << atoi(argv[1])  << setw(12) << atoi(argv[2])  << setw(12) << atoi(argv[3]) << "   original form " << endl    << endl;
      int d = b * b - 4 * a * c ;
      int droot = IntSqrt(d) ;
      if ( d <= 0) cout << "nonpositive discriminant  " << d << endl << endl;
       if (d == droot * droot) cout << "square discriminant  " << d << endl << endl;

      if (d > 0 && d != droot * droot)
      {



      int aa,bb,cc;
      while ( a <= 0 || c >= 0 || b <= abs(a+c) )
      {
        int delta, cAbs;
       cAbs = c;
        if (cAbs < 0) cAbs *= -1;

       delta =   (b + droot)/( 2 * cAbs)  ;
  if (c < 0) delta *= -1;
     aa = c ; bb = 2 * c * delta - b ; cc =  c * delta * delta - b * delta + a ;
       a = aa; b = bb; c = cc;
       } // while not reduced with a > 0


  cout << setw(12) << a  << setw(12) << b  << setw(12) << c << "   Lagrange-Gauss reduced " << endl    << endl;


        int a_old = a;
        int b_old = b;
        int c_old = c;

        int goon = 1;


set<unsigned int>  S;





        while (goon )
        {


         int newval = a+b+c;

          if ( newval > 0 )
          {
       //      cout << setw(65) << b + 2 * a << endl;
             insert_primitive_reps(a, b + 2 * a,newval ,M,  &S); // note ampersand
             b+= 2 * c ;

             a = newval;

           } // newval > 0
         else if ( newval < 0 )
          {
     //        cout << setw(5) << -1 * ( b + 2 * c) << endl;

             b+= 2 * a ;
             c = newval;

           } // newval < 0


         goon = (a != a_old)  || (b != b_old)  || (c != c_old)  ;

        } // while goon


  cout << endl << endl << " Represented (positive) primes up to  " << M << endl << endl;
 set<unsigned int> mods ;

 int rount = 0;
 set<unsigned int>::iterator iterU;
 for(iterU = S.begin() ;   iterU != S.end() ; ++iterU)
    {

      unsigned int p = *iterU;
     if ( p > 1 && PrimeQ(p) )
      {
       cout << setw(6) << p ;
       ++rount;
       if (rount % 10 == 0 ) cout << endl;
     // cout << setw(12) << p << setw(12) << p %  N << endl ;
      mods.insert( p % N);


      } // if prime
    }

  int count = 0;
  cout << endl << endl;
  cout << "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=   " << endl;
  cout<< " these are the collection of remainders when dividing by   " << N << endl << endl;
 for(iterU = mods.begin() ;   iterU != mods.end() ; ++iterU )
  {
    int    u = *iterU ;
    ++count;
    {
      cout << setw(7) << u  ;
      if (0 == count % 10) cout << endl;
    }
  } // for iterU

  cout << endl << endl;




  cout << endl << endl << " Represented (positive) primes up to  " << M <<  "  and value mod    " << N << endl << endl;
 cout << setw(12) << atoi(argv[1])  << setw(12) << atoi(argv[2])  << setw(12) << atoi(argv[3]) << "   original form " << endl    << endl;
       } // not square


    } // else argc
    return 0 ;
}    //  end of program


//  g++  -o     Conway_Positive_Primes     Conway_Positive_Primes.cc  -lm

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$\endgroup$
2
$\begingroup$

I honestly don't believe it, but I don't have the means to simulate a bunch of tries at the moment. Here is a good reason to believe you need to try harder though: in order to be a norm $p$ must be a quadratic residue mod $577$. But this gives it about a 50/50 shot a priori. Combine that with the fact that this field has class number $7$ and if you assume (possibly not true, but heuristically) these two facts are independent you only get $1/14$ chance any given prime should be both a residue and a factor represents a principal ideal class. I don't know of any major theorems on the subject without more research, but I would try harder to find some if you're really vested in it, I would bet most anything it's just that you've picked a ring with a rather large class number.


The "blah" part of this is that this field has class number $7$ (in fact it is the smallest $d>0$ so that $\Bbb Q(\sqrt{d})$ has class number $7$.) If it were a UFD it would be easy, since you can use Dirichlet's theorem on infinitely many primes in arithmetic progressions to find $p\equiv 1\mod 577$. Then $p$ would be a norm in the integer ring by Quadratic Reciprocity, which of course means $p = a^2+ab-144b^2$ for some $a,b\in\Bbb Z$, so the ideal $\left(a+b{1+\sqrt{577}\over 2}\right)$ would have prime norm, hence be prime itself and manifestly principal.

Also note that, in theory you would just need $p\equiv a\mod 577$ with $a$ a quadratic residue, but since I don't know any off the top of my head for such a large modulus, I chose $1\mod 577$ which means the prime must be at least $2\cdot 577+1=1155$ to fit this prescription.

$\endgroup$
  • $\begingroup$ Represented (positive) primes, by the principal form, up to 5000: 283 293 433 541 569 577 719 787 941 1097 1187 1429 1451 1531 1579 1663 1867 2003 2029 2083 2203 2339 2551 2671 2693 2999 3023 3083 3089 3253 3257 3271 3593 3607 3643 3779 3877 4021 4127 4253 4339 4409 4457 4517 4643 4793 4937 $\endgroup$ – Will Jagy Dec 20 '16 at 23:13
  • $\begingroup$ I feel like this answer is more of an elaborate comment, given that it doesn't actually answer whether or not such primes actually exist. The "major theorem" on the subject is class field theory, which governs when a prime ideal of a number field $K$ is principal in terms of its Hilbert class field. Heuristics then become completely precise, and a simple sage algorithm spits out the list of primes. See my answer $\endgroup$ – Mathmo123 Dec 21 '16 at 0:44
  • $\begingroup$ @Mathmo123 you are correct, that was my intent since the character limit was in place on comments. This is, I believe, standard practice. $\endgroup$ – Adam Hughes Dec 21 '16 at 0:46
  • $\begingroup$ @AdamHughes I wasn't aware that was the practice - good to know! In any case, your heuristic argument does turn out to be correct. $\endgroup$ – Mathmo123 Dec 21 '16 at 0:47
  • 1
    $\begingroup$ @Mathmo123 if you cut off your prime set at a large enough $x$, then density $p$ implies an asymptotically close probability to $p$. The issue here is that the independence assumption is unjustified, hence the "heuristic." It fits the facts of not hitting a reasonable set of primes at low values, however. My goal was to urge the op to test some larger primes as I had confidence solutions would emerge. $\endgroup$ – Adam Hughes Dec 21 '16 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.