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)]

Sage Live

from sage.schemes.affine.affine_rational_point import enum_affine_rational_field
A.<x,y,z> = AffineSpace(3, QQ)
S = A.subscheme([2*x - 3*y])
enum_affine_rational_field(S, 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)]

Sage Live

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

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 Live

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

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)]

Sage Live

A.<x,y,z> = AffineSpace(3, GF(3))
S = A.subscheme(x + y)
enum_affine_finite_field(S)

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)]

Sage Live

A.<x,y,z> = AffineSpace(3, GF(3))
S = A.subscheme(x + y)
enum_affine_finite_field(S)

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: keyword arguments:

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 Live

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

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 Live

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

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 Live

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

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 Live

A.<x,y,z> = AffineSpace(3, QQ)
from sage.schemes.affine.affine_rational_point import enum_affine_rational_field
enum_affine_rational_field(A(QQ), 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 Live

A.<w,x,y,z> = AffineSpace(4, QQ)
S = A.subscheme([x^2 - y*z + 1, w^3 + z + y^2])
enum_affine_rational_field(S(QQ), 1)
enum_affine_rational_field(S(QQ), 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 Live

A.<w,x,y,z> = AffineSpace(4, QQ)
S = A.subscheme([x^2 - y*z + 1, w^3 + z + y^2])
enum_affine_rational_field(S(QQ), 1)
enum_affine_rational_field(S(QQ), 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)]

Sage Live

A.<x,y> = AffineSpace(2, QQ)
C = Curve(x^2 + y - x)                                                    # needs sage.libs.singular
enum_affine_rational_field(C, 10)         # long time (3 s)               # needs sage.libs.singular

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)]

Sage Live

A.<x,y> = AffineSpace(2, QQ)
C = Curve(x^2 + y - x)                                                    # needs sage.libs.singular
enum_affine_rational_field(C, 10)         # long time (3 s)               # needs sage.libs.singular

AUTHORS:

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