Enumeration of rational points on affine schemes#

Naive algorithms for enumerating rational points over \(\QQ\) or finite fields over for general schemes.

Warning

Incorrect results and infinite loops may occur if using a wrong function.

(For instance using an affine function for a projective scheme or a finite field function for a scheme defined over an infinite field.)

EXAMPLES:

Affine, over \(\QQ\):

Sage

sage: from sage.schemes.affine.affine_rational_point import enum_affine_rational_field
sage: A.<x,y,z> = AffineSpace(3, QQ)
sage: S = A.subscheme([2*x - 3*y])
sage: enum_affine_rational_field(S, 2)
[(0, 0, -2), (0, 0, -1), (0, 0, -1/2), (0, 0, 0),
 (0, 0, 1/2), (0, 0, 1), (0, 0, 2)]

Python

>>> from sage.all import *
>>> from sage.schemes.affine.affine_rational_point import enum_affine_rational_field
>>> A = AffineSpace(Integer(3), QQ, names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> S = A.subscheme([Integer(2)*x - Integer(3)*y])
>>> enum_affine_rational_field(S, Integer(2))
[(0, 0, -2), (0, 0, -1), (0, 0, -1/2), (0, 0, 0),
 (0, 0, 1/2), (0, 0, 1), (0, 0, 2)]

Affine over a finite field:

Sage

sage: from sage.schemes.affine.affine_rational_point import enum_affine_finite_field
sage: A.<w,x,y,z> = AffineSpace(4, GF(2))
sage: enum_affine_finite_field(A(GF(2)))
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0),
 (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1),
 (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0),
 (1, 1, 1, 1)]

Python

>>> from sage.all import *
>>> from sage.schemes.affine.affine_rational_point import enum_affine_finite_field
>>> A = AffineSpace(Integer(4), GF(Integer(2)), names=('w', 'x', 'y', 'z',)); (w, x, y, z,) = A._first_ngens(4)
>>> enum_affine_finite_field(A(GF(Integer(2))))
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0),
 (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1),
 (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0),
 (1, 1, 1, 1)]

AUTHORS:

David R. Kohel <kohel@maths.usyd.edu.au>: original version.
John Cremona and Charlie Turner <charlotteturner@gmail.com> (06-2010): improvements to clarity and documentation.

sage.schemes.affine.affine_rational_point.enum_affine_finite_field(X)[source]#

Enumerates affine points on scheme X defined over a finite field.

INPUT:

X – a scheme defined over a finite field or a set of abstract rational points of such a scheme.

OUTPUT:

a list containing the affine points of X over the finite field, sorted.

EXAMPLES:

Sage

sage: from sage.schemes.affine.affine_rational_point import enum_affine_finite_field
sage: F = GF(7)
sage: A.<w,x,y,z> = AffineSpace(4, F)
sage: C = A.subscheme([w^2 + x + 4, y*z*x - 6, z*y + w*x])
sage: enum_affine_finite_field(C(F))
[]
sage: C = A.subscheme([w^2 + x + 4, y*z*x - 6])
sage: enum_affine_finite_field(C(F))
[(0, 3, 1, 2), (0, 3, 2, 1), (0, 3, 3, 3), (0, 3, 4, 4), (0, 3, 5, 6),
 (0, 3, 6, 5), (1, 2, 1, 3), (1, 2, 2, 5), (1, 2, 3, 1), (1, 2, 4, 6),
 (1, 2, 5, 2), (1, 2, 6, 4), (2, 6, 1, 1), (2, 6, 2, 4), (2, 6, 3, 5),
 (2, 6, 4, 2), (2, 6, 5, 3), (2, 6, 6, 6), (3, 1, 1, 6), (3, 1, 2, 3),
 (3, 1, 3, 2), (3, 1, 4, 5), (3, 1, 5, 4), (3, 1, 6, 1), (4, 1, 1, 6),
 (4, 1, 2, 3), (4, 1, 3, 2), (4, 1, 4, 5), (4, 1, 5, 4), (4, 1, 6, 1),
 (5, 6, 1, 1), (5, 6, 2, 4), (5, 6, 3, 5), (5, 6, 4, 2), (5, 6, 5, 3),
 (5, 6, 6, 6), (6, 2, 1, 3), (6, 2, 2, 5), (6, 2, 3, 1), (6, 2, 4, 6),
 (6, 2, 5, 2), (6, 2, 6, 4)]

Python

>>> from sage.all import *
>>> from sage.schemes.affine.affine_rational_point import enum_affine_finite_field
>>> F = GF(Integer(7))
>>> A = AffineSpace(Integer(4), F, names=('w', 'x', 'y', 'z',)); (w, x, y, z,) = A._first_ngens(4)
>>> C = A.subscheme([w**Integer(2) + x + Integer(4), y*z*x - Integer(6), z*y + w*x])
>>> enum_affine_finite_field(C(F))
[]
>>> C = A.subscheme([w**Integer(2) + x + Integer(4), y*z*x - Integer(6)])
>>> enum_affine_finite_field(C(F))
[(0, 3, 1, 2), (0, 3, 2, 1), (0, 3, 3, 3), (0, 3, 4, 4), (0, 3, 5, 6),
 (0, 3, 6, 5), (1, 2, 1, 3), (1, 2, 2, 5), (1, 2, 3, 1), (1, 2, 4, 6),
 (1, 2, 5, 2), (1, 2, 6, 4), (2, 6, 1, 1), (2, 6, 2, 4), (2, 6, 3, 5),
 (2, 6, 4, 2), (2, 6, 5, 3), (2, 6, 6, 6), (3, 1, 1, 6), (3, 1, 2, 3),
 (3, 1, 3, 2), (3, 1, 4, 5), (3, 1, 5, 4), (3, 1, 6, 1), (4, 1, 1, 6),
 (4, 1, 2, 3), (4, 1, 3, 2), (4, 1, 4, 5), (4, 1, 5, 4), (4, 1, 6, 1),
 (5, 6, 1, 1), (5, 6, 2, 4), (5, 6, 3, 5), (5, 6, 4, 2), (5, 6, 5, 3),
 (5, 6, 6, 6), (6, 2, 1, 3), (6, 2, 2, 5), (6, 2, 3, 1), (6, 2, 4, 6),
 (6, 2, 5, 2), (6, 2, 6, 4)]

Sage

sage: A.<x,y,z> = AffineSpace(3, GF(3))
sage: S = A.subscheme(x + y)
sage: enum_affine_finite_field(S)
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2),
 (2, 1, 0), (2, 1, 1), (2, 1, 2)]

Python

>>> from sage.all import *
>>> A = AffineSpace(Integer(3), GF(Integer(3)), names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> S = A.subscheme(x + y)
>>> enum_affine_finite_field(S)
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2),
 (2, 1, 0), (2, 1, 1), (2, 1, 2)]

ALGORITHM:

Checks all points in affine space to see if they lie on X.

Warning

If X is defined over an infinite field, this code will not finish!

AUTHORS:

John Cremona and Charlie Turner (06-2010)

sage.schemes.affine.affine_rational_point.enum_affine_number_field(X, **kwds)[source]#

Enumerates affine points on scheme X defined over a number field. Simply checks all of the points of absolute height up to B and adds those that are on the scheme to the list.

This algorithm computes 2 lists: L containing elements x in \(K\) such that H_k(x) <= B, and a list L’ containing elements x in \(K\) that, due to floating point issues, may be slightly larger then the bound. This can be controlled by lowering the tolerance.

ALGORITHM:

This is an implementation of the revised algorithm (Algorithm 4) in [DK2013]. Algorithm 5 is used for imaginary quadratic fields.

INPUT:

kwds:

bound – a real number
tolerance – a rational number in (0,1] used in doyle-krumm algorithm-4
precision – the precision to use for computing the elements of bounded height of number fields.

OUTPUT:

a list containing the affine points of X of absolute height up to B, sorted.

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: from sage.schemes.affine.affine_rational_point import enum_affine_number_field
sage: u = QQ['u'].0
sage: K = NumberField(u^2 + 2, 'v')
sage: A.<x,y,z> = AffineSpace(K, 3)
sage: X = A.subscheme([y^2 - x])
sage: enum_affine_number_field(X(K), bound=2**0.5)
[(0, 0, -1), (0, 0, -v), (0, 0, -1/2*v), (0, 0, 0), (0, 0, 1/2*v),
 (0, 0, v), (0, 0, 1), (1, -1, -1), (1, -1, -v), (1, -1, -1/2*v),
 (1, -1, 0), (1, -1, 1/2*v), (1, -1, v), (1, -1, 1), (1, 1, -1),
 (1, 1, -v), (1, 1, -1/2*v), (1, 1, 0), (1, 1, 1/2*v), (1, 1, v), (1, 1, 1)]

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> from sage.schemes.affine.affine_rational_point import enum_affine_number_field
>>> u = QQ['u'].gen(0)
>>> K = NumberField(u**Integer(2) + Integer(2), 'v')
>>> A = AffineSpace(K, Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> X = A.subscheme([y**Integer(2) - x])
>>> enum_affine_number_field(X(K), bound=Integer(2)**RealNumber('0.5'))
[(0, 0, -1), (0, 0, -v), (0, 0, -1/2*v), (0, 0, 0), (0, 0, 1/2*v),
 (0, 0, v), (0, 0, 1), (1, -1, -1), (1, -1, -v), (1, -1, -1/2*v),
 (1, -1, 0), (1, -1, 1/2*v), (1, -1, v), (1, -1, 1), (1, 1, -1),
 (1, 1, -v), (1, 1, -1/2*v), (1, 1, 0), (1, 1, 1/2*v), (1, 1, v), (1, 1, 1)]

Sage

sage: # needs sage.rings.number_field
sage: from sage.schemes.affine.affine_rational_point import enum_affine_number_field
sage: u = QQ['u'].0
sage: K = NumberField(u^2 + 3, 'v')
sage: A.<x,y> = AffineSpace(K, 2)
sage: X = A.subscheme(x - y)
sage: enum_affine_number_field(X, bound=3**0.25)
[(-1, -1), (-1/2*v - 1/2, -1/2*v - 1/2), (1/2*v - 1/2, 1/2*v - 1/2),
 (0, 0), (-1/2*v + 1/2, -1/2*v + 1/2), (1/2*v + 1/2, 1/2*v + 1/2), (1, 1)]

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> from sage.schemes.affine.affine_rational_point import enum_affine_number_field
>>> u = QQ['u'].gen(0)
>>> K = NumberField(u**Integer(2) + Integer(3), 'v')
>>> A = AffineSpace(K, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> X = A.subscheme(x - y)
>>> enum_affine_number_field(X, bound=Integer(3)**RealNumber('0.25'))
[(-1, -1), (-1/2*v - 1/2, -1/2*v - 1/2), (1/2*v - 1/2, 1/2*v - 1/2),
 (0, 0), (-1/2*v + 1/2, -1/2*v + 1/2), (1/2*v + 1/2, 1/2*v + 1/2), (1, 1)]

sage.schemes.affine.affine_rational_point.enum_affine_rational_field(X, B)[source]#

Enumerates affine rational points on scheme X up to bound B.

INPUT:

X – a scheme or set of abstract rational points of a scheme.
B – a positive integer bound.

OUTPUT:

a list containing the affine points of X of height up to B, sorted.

EXAMPLES:

Sage

sage: A.<x,y,z> = AffineSpace(3, QQ)
sage: from sage.schemes.affine.affine_rational_point import enum_affine_rational_field
sage: enum_affine_rational_field(A(QQ), 1)
[(-1, -1, -1), (-1, -1, 0), (-1, -1, 1), (-1, 0, -1), (-1, 0, 0), (-1, 0, 1),
 (-1, 1, -1), (-1, 1, 0), (-1, 1, 1), (0, -1, -1), (0, -1, 0), (0, -1, 1),
 (0, 0, -1), (0, 0, 0), (0, 0, 1), (0, 1, -1), (0, 1, 0), (0, 1, 1), (1, -1, -1),
 (1, -1, 0), (1, -1, 1), (1, 0, -1), (1, 0, 0), (1, 0, 1), (1, 1, -1), (1, 1, 0),
 (1, 1, 1)]

Python

>>> from sage.all import *
>>> A = AffineSpace(Integer(3), QQ, names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> from sage.schemes.affine.affine_rational_point import enum_affine_rational_field
>>> enum_affine_rational_field(A(QQ), Integer(1))
[(-1, -1, -1), (-1, -1, 0), (-1, -1, 1), (-1, 0, -1), (-1, 0, 0), (-1, 0, 1),
 (-1, 1, -1), (-1, 1, 0), (-1, 1, 1), (0, -1, -1), (0, -1, 0), (0, -1, 1),
 (0, 0, -1), (0, 0, 0), (0, 0, 1), (0, 1, -1), (0, 1, 0), (0, 1, 1), (1, -1, -1),
 (1, -1, 0), (1, -1, 1), (1, 0, -1), (1, 0, 0), (1, 0, 1), (1, 1, -1), (1, 1, 0),
 (1, 1, 1)]

Sage

sage: A.<w,x,y,z> = AffineSpace(4, QQ)
sage: S = A.subscheme([x^2 - y*z + 1, w^3 + z + y^2])
sage: enum_affine_rational_field(S(QQ), 1)
[(0, 0, -1, -1)]
sage: enum_affine_rational_field(S(QQ), 2)
[(0, 0, -1, -1), (1, -1, -1, -2), (1, 1, -1, -2)]

Python

>>> from sage.all import *
>>> A = AffineSpace(Integer(4), QQ, names=('w', 'x', 'y', 'z',)); (w, x, y, z,) = A._first_ngens(4)
>>> S = A.subscheme([x**Integer(2) - y*z + Integer(1), w**Integer(3) + z + y**Integer(2)])
>>> enum_affine_rational_field(S(QQ), Integer(1))
[(0, 0, -1, -1)]
>>> enum_affine_rational_field(S(QQ), Integer(2))
[(0, 0, -1, -1), (1, -1, -1, -2), (1, 1, -1, -2)]

Sage

sage: A.<x,y> = AffineSpace(2, QQ)
sage: C = Curve(x^2 + y - x)                                                    # needs sage.libs.singular
sage: enum_affine_rational_field(C, 10)         # long time (3 s)               # needs sage.libs.singular
[(-2, -6), (-1, -2), (-2/3, -10/9), (-1/2, -3/4), (-1/3, -4/9),
 (0, 0), (1/3, 2/9), (1/2, 1/4), (2/3, 2/9), (1, 0),
 (4/3, -4/9), (3/2, -3/4), (5/3, -10/9), (2, -2), (3, -6)]

Python

>>> from sage.all import *
>>> A = AffineSpace(Integer(2), QQ, names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(x**Integer(2) + y - x)                                                    # needs sage.libs.singular
>>> enum_affine_rational_field(C, Integer(10))         # long time (3 s)               # needs sage.libs.singular
[(-2, -6), (-1, -2), (-2/3, -10/9), (-1/2, -3/4), (-1/3, -4/9),
 (0, 0), (1/3, 2/9), (1/2, 1/4), (2/3, 2/9), (1, 0),
 (4/3, -4/9), (3/2, -3/4), (5/3, -10/9), (2, -2), (3, -6)]

AUTHORS:

David R. Kohel <kohel@maths.usyd.edu.au>: original version.
Charlie Turner (06-2010): small adjustments.
Raman Raghukul 2018: updated.