Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" 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: 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)]
Affine over a finite field::
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)]
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. """
#***************************************************************************** # Copyright (C) 2010 William Stein, David Kohel, John Cremona, Charlie Turner # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from six.moves import range
from sage.rings.all import ZZ from sage.misc.all import cartesian_product_iterator from sage.schemes.generic.scheme import is_Scheme
def enum_affine_rational_field(X, B): """ 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: 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)]
::
sage: A.<w,x,y,z> = AffineSpace(4, QQ) sage: S = A.subscheme([x^2-y*z+3, w^3+z+y^2]) sage: enum_affine_rational_field(S(QQ), 2) [] sage: enum_affine_rational_field(S(QQ), 3) [(-2, 0, -3, -1)]
::
sage: A.<x,y> = AffineSpace(2, QQ) sage: C = Curve(x^2+y-x) sage: enum_affine_rational_field(C, 10) [(-2, -6), (-1, -2), (0, 0), (1, 0), (2, -2), (3, -6)]
AUTHORS:
- David R. Kohel <kohel@maths.usyd.edu.au>: original version.
- Charlie Turner (06-2010): small adjustments. """ raise TypeError("ambient space must be affine space over the rational field") else: raise TypeError("codomain must be affine space over the rational field")
else: # rational field
def enum_affine_number_field(X, B): """ 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.
INPUT:
- ``X`` - a scheme defined over a number field.
- ``B`` - a real number.
OUTPUT:
- a list containing the affine points of ``X`` of absolute height up to ``B``, sorted.
EXAMPLES::
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), 4) [(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: 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: from sage.schemes.affine.affine_rational_point import enum_affine_number_field sage: enum_affine_number_field(X, 3) [(-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)] """ raise TypeError("ambient space must be affine space over a number field") else: raise TypeError("codomain must be affine space over a number field")
def enum_affine_finite_field(X): r""" 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: 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: from sage.schemes.affine.affine_rational_point import enum_affine_finite_field 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)]
::
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)]
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) """ raise TypeError("ambient space must be affine space over a finite field") else: raise TypeError("codomain must be affine space over a finite field")
|