rationalPoints -- Find the rational points on a variety

Synopsis

Usage:

rationalPoints I

rationalPoints(F, I)
Inputs:
- I, an ideal, viewed as an affine variety; an affine variety / a projective variety can also be used
- F, the coefficient field; if not specified then it is taken to be the field of definition of I
Optional inputs:
- Amount => a Boolean value, default value false, whether to only compute the number of rational points.
- Projective => a Boolean value, default value false, whether to treat the ideal as a homogeneous ideal and consider the corresponding projective variety
- Split => a Boolean value, default value false, whether to compute all rational points over the splitting field, works only if I is 0-dimensional (ignored if F is specified)
- Verbose => a Boolean value, default value false, whether to print the polynomials computed that do not split in the coefficient field (if Split is set to true, it will instead print information when a field extension is performed)
- Bound => a number, default value null, over a number field, specify the upper bound of the multiplicative height for the points to enumerate
- KeepAll => a Boolean value, default value false, whether to keep the rational points found with height exceeding the bound
Outputs:
- Either a list of points, or the number of such points if Amount is set to true. In the affine case each point is represented by a list of coordinates, and in the projective case each point is an instance of the type ProjectivePoint.

Description

This method takes in an ideal I and returns a list of rational points on the variety defined by the ideal. The algorithm uses brute force plus some elimination. Options are available for different use cases.

Over finite fields

Over a finite field (ZZ/p or GF q), the ideal can have arbitrary dimension. By default it will be regarded as an affine variety.

i1 : R = ZZ/5[x,y,z]; I = ideal(x^3-y*z, x+y);

o2 : Ideal of R

i3 : rationalPoints I

o3 = {{0, 0, 0}, {0, 0, 1}, {-2, 2, 1}, {2, -2, 1}, {0, 0, 2}, {0, 0, -2},
     ------------------------------------------------------------------------
     {0, 0, -1}, {-1, 1, -1}, {1, -1, -1}}

o3 : List

i4 : #rationalPoints Spec(R/I)

o4 = 9

i5 : #rationalPoints_(GF 25) I

o5 = 49

To consider projective varieties, one can use the option Projective=>true or pass directly a projective variety. In this case, the rational points are given in homogeneous coordinates. The first non-zero coordinate will be normalized to 1.

For example we can take the twisted cubic, which is a smooth rational curve so it has q+1 points over a finite field of q elements.

i6 : ZZ/5[x,y,z,w]; I = ideal "xz-y2,xw-yz,yw-z2";

              ZZ
o7 : Ideal of --[x..z, w]
               5

i8 : rationalPoints(I, Projective => true)

o8 = {(1 : 0 : 0 : 0), (1 : 1 : 1 : 1), (1 : -2 : -1 : 2), (1 : 2 : -1 : -2),
     ------------------------------------------------------------------------
     (1 : -1 : 1 : -1), (0 : 0 : 0 : 1)}

o8 : List

i9 : #rationalPoints variety I

o9 = 6

i10 : #rationalPoints_(GF 25) variety I

o10 = 26

If only the number of rational points is needed, set Amount to true can sometimes speed up the computation.

i11 : ZZ/101[u_0..u_10]; f = sum toList(u_0..u_10); I = ideal f

o13 = ideal(u  + u  + u  + u  + u  + u  + u  + u  + u  + u  + u  )
             0    1    2    3    4    5    6    7    8    9    10

                ZZ
o13 : Ideal of ---[u ..u  ]
               101  0   10

i14 : time rationalPoints(I, Amount => true)
 -- used 0.00527728s (cpu); 0.00580084s (thread); 0s (gc)

o14 = 110462212541120451001

Over number fields

Over a number field one can use the option Bound to specify a maximal multiplicative height given by $(x_0:\dots:x_n)\mapsto \prod_{v}\max_i|x_i|_v ^{d_v/d}$ (this is also available as a method globalHeight).

i15 : QQ[x,y,z]; I = homogenize(ideal(y^2-x*(x-1)*(x-2)*(x-5)*(x-6)), z);

o16 : Ideal of QQ[x..z]

i17 : rationalPoints(variety I, Bound=>12)

                             1            1             1            1       
o17 = {(1 : 0 : 1), (1 : 0 : -), (1 : 2 : -), (1 : -2 : -), (1 : 0 : -), (1 :
                             2            3             3            5       
      -----------------------------------------------------------------------
          1
      0 : -), (0 : 1 : 0), (0 : 0 : 1)}
          6

o17 : List

i18 : globalHeight \ oo

o18 = {1, 2, 6, 6, 5, 6, 1, 1}

o18 : List

During the enumeration, sometimes there are rational points found with height exceeding the bound. These are cast away by default. Use KeepAll=>true to keep such points (this will also avoid the heavy task of computing the height function, especially over number fields other than QQ).

i19 : rationalPoints(variety I, Bound=>12, KeepAll=>true)

                             1            1             1            1       
o19 = {(1 : 0 : 1), (1 : 0 : -), (1 : 2 : -), (1 : -2 : -), (1 : 0 : -), (1 :
                             2            3             3            5       
      -----------------------------------------------------------------------
          1              1               1
      0 : -), (1 : 12 : --), (1 : -12 : --), (0 : 1 : 0), (0 : 0 : 1)}
          6             10              10

o19 : List

i20 : globalHeight \ oo

o20 = {1, 2, 6, 6, 5, 6, 120, 120, 1, 1}

o20 : List

In the affine case, the height function is used on individual coordinates, so for example {2,1/2} will be considered as of height 2 instead of 4.

i21 : QQ[x,y]; rationalPoints(ideal(x-2), Bound=>2)

                                                       1       1
o22 = {{2, -2}, {2, -1}, {2, 0}, {2, 1}, {2, 2}, {2, - -}, {2, -}}
                                                       2       2

o22 : List

Zero-dimensional ideals

For a 0-dimensional ideal, all the rational points can be found, including those in the splitting field. Set the option Verbose to true will print the polynomials found not splitting in the coefficient field, and set Split to true will automatically make field extensions and compute all the points over the splitting field. The information on the splitting field can either be printed using Verbose=>true, or be retrieved from any coordinate of the points. One can refer to extField and baseChange for the methods used in handling field extensions.

i23 : R = QQ[x,y]; I = ideal(x^2+y^2-1,x^3+y^3-1);

o24 : Ideal of R

i25 : rationalPoints(I, Verbose => true)
-- the following polynomials do not split
   -- 2*x^2+4*x+3

o25 = {{1, 0}, {0, 1}}

o25 : List

i26 : rationalPoints(I, Verbose => true, Split => true)
-- base change to the field QQ[a]/(a^2+2)

                          1       1         1         1
o26 = {{1, 0}, {0, 1}, {- -a - 1, -a - 1}, {-a - 1, - -a - 1}}
                          2       2         2         2

o26 : List

i27 : ring \ first oo

        QQ[a]     QQ[a]
o27 = {------[], ------[]}
        2         2
       a  + 2    a  + 2

o27 : List

Note that the computations over number fields of large degree are slow. In such cases it might be better to switch to a large finite field where the program runs much faster. One could also use numerical algorithms implemented in the packages EigenSolver (which uses the same strategy of elimination) and NumericalAlgebraicGeometry (which uses homotopy continuation).

The next example computes the 31 nodes on a Togliatti surface. Over characteristic 0 the splitting field has degree 8 over QQ, so the computation isn't so heavy.

i28 : F = toField(QQ[q]/(q^4-10*q^2+20)); R = F[x,y,z,w];

i30 : I = ideal "64(x-w)(x4-4x3w-10x2y2-4x2w2+16xw3-20xy2w+5y4+16w4-20y2w2)-5q(2z-qw)(4(x2+y2-z2)+(1+3(5-q2))w2)2";

o30 : Ideal of R

i31 : nodes = I + ideal jacobian I;

o31 : Ideal of R

i32 : time rationalPoints(variety nodes, Split=>true, Verbose=>true);
-- base change to the field QQ[a]/(a^8-8*a^6+19*a^4-12*a^2+1)
 -- used 1.69576s (cpu); 1.53592s (thread); 0s (gc)

i33 : #oo

o33 = 31

Still it runs a lot faster when reduced to a positive characteristic.

i34 : nodes' = baseChange_32003 nodes;

o34 : Ideal of GF 1048969271299456081[x..z, w]

i35 : time #rationalPoints(variety nodes', Split=>true, Verbose=>true)
 -- used 0.447028s (cpu); 0.357899s (thread); 0s (gc)

o35 = 31

Caveat

For a number field other than QQ, the enumeration of elements with bounded height depends on an algorithm by Doyle–Krumm, which is currently only implemented in Sage.

Ways to use rationalPoints :

rationalPoints(Ideal)
rationalPoints(Ring,Ideal)

For the programmer

The object rationalPoints is a method function with options.