CoCalc -- rational

GitHub Repository: sagemath/sagelib
Path: blob/master/sage/schemes/generic/rational_point.py
⁴⁰⁶⁹ views
1
r"""
2
Enumeration of rational points on affine and projective schemes
3

4
Naive algorithms for enumerating rational points over `\QQ` or finite fields
5
over for general schemes.
6

7
.. WARNING::
8

9
    Incorrect results and infinite loops may occur if using a wrong function.
10
    (For instance using an affine function for a projective scheme or a finite
11
    field function for a scheme defined over an infinite field.)
12

13
EXAMPLES:
14

15
Projective, over `\QQ`::
16

17
    sage: from sage.schemes.generic.rational_point import enum_projective_rational_field
18
    sage: P.<X,Y,Z> = ProjectiveSpace(2,QQ)
19
    sage: C = P.subscheme([X+Y-Z])
20
    sage: enum_projective_rational_field(C,3)
21
    [(-2 : 3 : 1), (-1 : 1 : 0), (-1 : 2 : 1), (-1/2 : 3/2 : 1),
22
     (0 : 1 : 1), (1/3 : 2/3 : 1), (1/2 : 1/2 : 1), (2/3 : 1/3 : 1),
23
     (1 : 0 : 1), (3/2 : -1/2 : 1), (2 : -1 : 1), (3 : -2 : 1)]
24

25
Affine, over `\QQ`::
26
    
27
    sage: from sage.schemes.generic.rational_point import enum_affine_rational_field
28
    sage: A.<x,y,z> = AffineSpace(3,QQ)
29
    sage: S = A.subscheme([2*x-3*y])
30
    sage: enum_affine_rational_field(S,2)
31
    [(0, 0, -2), (0, 0, -1), (0, 0, -1/2), (0, 0, 0),
32
     (0, 0, 1/2), (0, 0, 1), (0, 0, 2)]
33

34
Projective over a finite field::
35

36
    sage: from sage.schemes.generic.rational_point import enum_projective_finite_field
37
    sage: E = EllipticCurve('72').change_ring(GF(19))
38
    sage: enum_projective_finite_field(E)
39
    [(0 : 1 : 0), (1 : 0 : 1), (3 : 0 : 1), (4 : 9 : 1), (4 : 10 : 1),
40
     (6 : 6 : 1), (6 : 13 : 1), (7 : 6 : 1), (7 : 13 : 1), (9 : 4 : 1),
41
     (9 : 15 : 1), (12 : 8 : 1), (12 : 11 : 1), (13 : 8 : 1), (13 : 11 : 1),
42
     (14 : 3 : 1), (14 : 16 : 1), (15 : 0 : 1), (16 : 9 : 1), (16 : 10 : 1),
43
     (17 : 7 : 1), (17 : 12 : 1), (18 : 9 : 1), (18 : 10 : 1)]
44

45
Affine over a finite field::
46

47
    sage: from sage.schemes.generic.rational_point import enum_affine_finite_field
48
    sage: A.<w,x,y,z> = AffineSpace(4,GF(2))
49
    sage: enum_affine_finite_field(A(GF(2)))
50
    [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0),
51
     (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1),
52
     (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0),
53
     (1, 1, 1, 1)]
54

55
AUTHORS:
56

57
- David R. Kohel <[email protected]>: original version.
58

59
- John Cremona and Charlie Turner <[email protected]> (06-2010):
60
  improvements to clarity and documentation.
61
"""
62

63

64
#*******************************************************************************
65
#  Copyright (C) 2010 William Stein, David Kohel, John Cremona, Charlie Turner
66
#  Distributed under the terms of the GNU General Public License (GPL)
67
#                  http://www.gnu.org/licenses/
68
#*******************************************************************************
69

70

71
from sage.rings.arith import gcd
72
from sage.rings.all import ZZ
73
from sage.misc.all import srange, cartesian_product_iterator
74
from sage.schemes.all import is_Scheme
75

76
def enum_projective_rational_field(X,B):
77
    r"""
78
    Enumerates projective, rational points on scheme ``X`` of height up to
79
    bound ``B``.
80
    
81
    INPUT:
82
    
83
    - ``X`` -  a scheme or set of abstract rational points of a scheme;
84
    - ``B`` -  a positive integer bound.
85

86
    OUTPUT:
87

88
    - a list containing the projective points of ``X`` of height up to ``B``,
89
      sorted.
90

91
    EXAMPLES::
92

93
        sage: P.<X,Y,Z> = ProjectiveSpace(2,QQ)
94
        sage: C = P.subscheme([X+Y-Z])
95
        sage: from sage.schemes.generic.rational_point import enum_projective_rational_field
96
        sage: enum_projective_rational_field(C(QQ),6)
97
        [(-5 : 6 : 1), (-4 : 5 : 1), (-3 : 4 : 1), (-2 : 3 : 1),
98
         (-3/2 : 5/2 : 1), (-1 : 1 : 0), (-1 : 2 : 1), (-2/3 : 5/3 : 1),
99
         (-1/2 : 3/2 : 1), (-1/3 : 4/3 : 1), (-1/4 : 5/4 : 1),
100
         (-1/5 : 6/5 : 1), (0 : 1 : 1), (1/6 : 5/6 : 1), (1/5 : 4/5 : 1),
101
         (1/4 : 3/4 : 1), (1/3 : 2/3 : 1), (2/5 : 3/5 : 1), (1/2 : 1/2 : 1),
102
         (3/5 : 2/5 : 1), (2/3 : 1/3 : 1), (3/4 : 1/4 : 1), (4/5 : 1/5 : 1),
103
         (5/6 : 1/6 : 1), (1 : 0 : 1), (6/5 : -1/5 : 1), (5/4 : -1/4 : 1),
104
         (4/3 : -1/3 : 1), (3/2 : -1/2 : 1), (5/3 : -2/3 : 1), (2 : -1 : 1),
105
         (5/2 : -3/2 : 1), (3 : -2 : 1), (4 : -3 : 1), (5 : -4 : 1),
106
         (6 : -5 : 1)]
107
        sage: enum_projective_rational_field(C,6) == enum_projective_rational_field(C(QQ),6)
108
        True
109

110
    ::
111
    
112
        sage: P3.<W,X,Y,Z> = ProjectiveSpace(3,QQ)
113
        sage: enum_projective_rational_field(P3,1)
114
        [(-1 : -1 : -1 : 1), (-1 : -1 : 0 : 1), (-1 : -1 : 1 : 0), (-1 : -1 : 1 : 1), 
115
        (-1 : 0 : -1 : 1), (-1 : 0 : 0 : 1), (-1 : 0 : 1 : 0), (-1 : 0 : 1 : 1), 
116
        (-1 : 1 : -1 : 1), (-1 : 1 : 0 : 0), (-1 : 1 : 0 : 1), (-1 : 1 : 1 : 0), 
117
        (-1 : 1 : 1 : 1), (0 : -1 : -1 : 1), (0 : -1 : 0 : 1), (0 : -1 : 1 : 0),
118
        (0 : -1 : 1 : 1), (0 : 0 : -1 : 1), (0 : 0 : 0 : 1), (0 : 0 : 1 : 0), 
119
        (0 : 0 : 1 : 1), (0 : 1 : -1 : 1), (0 : 1 : 0 : 0), (0 : 1 : 0 : 1), 
120
        (0 : 1 : 1 : 0), (0 : 1 : 1 : 1), (1 : -1 : -1 : 1), (1 : -1 : 0 : 1), 
121
        (1 : -1 : 1 : 0), (1 : -1 : 1 : 1), (1 : 0 : -1 : 1), (1 : 0 : 0 : 0),
122
        (1 : 0 : 0 : 1), (1 : 0 : 1 : 0), (1 : 0 : 1 : 1), (1 : 1 : -1 : 1),
123
        (1 : 1 : 0 : 0), (1 : 1 : 0 : 1), (1 : 1 : 1 : 0), (1 : 1 : 1 : 1)]
124

125
    ALGORITHM: 
126

127
    We just check all possible projective points in correct dimension
128
    of projective space to see if they lie on ``X``.
129

130
    AUTHORS: 
131

132
    - John Cremona and Charlie Turner (06-2010)
133
    """
134
    if is_Scheme(X):
135
        X = X(X.base_ring())
136
    n = X.codomain().ambient_space().ngens()
137
    zero = (0,) * n
138
    pts = []
139
    for c in cartesian_product_iterator([srange(-B,B+1) for _ in range(n)]):
140
        if gcd(c) == 1 and c > zero:
141
            try:
142
                pts.append(X(c))
143
            except TypeError:
144
                pass
145
    pts.sort()
146
    return pts
147

148
def enum_affine_rational_field(X,B):
149
    """
150
    Enumerates affine rational points on scheme ``X`` (defined over `\QQ`) up
151
    to bound ``B``.
152

153
    INPUT:
154
    
155
    - ``X`` -  a scheme or set of abstract rational points of a scheme;
156
    - ``B`` -  a positive integer bound.
157

158
    OUTPUT:
159

160
    - a list containing the affine points of ``X`` of height up to ``B``,
161
      sorted.
162

163
    EXAMPLES::
164

165
        sage: A.<x,y,z> = AffineSpace(3,QQ)
166
        sage: from sage.schemes.generic.rational_point import enum_affine_rational_field
167
        sage: enum_affine_rational_field(A(QQ),1)
168
        [(-1, -1, -1), (-1, -1, 0), (-1, -1, 1), (-1, 0, -1), (-1, 0, 0), (-1, 0, 1),
169
        (-1, 1, -1), (-1, 1, 0), (-1, 1, 1), (0, -1, -1), (0, -1, 0), (0, -1, 1),
170
        (0, 0, -1), (0, 0, 0), (0, 0, 1), (0, 1, -1), (0, 1, 0), (0, 1, 1), (1, -1, -1),
171
        (1, -1, 0), (1, -1, 1), (1, 0, -1), (1, 0, 0), (1, 0, 1), (1, 1, -1), (1, 1, 0),
172
        (1, 1, 1)]
173

174
    ::
175

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

183
    ::
184

185
        sage: A.<x,y> = AffineSpace(2,QQ)
186
        sage: C = Curve(x^2+y-x)
187
        sage: enum_affine_rational_field(C,10)
188
        [(-2, -6), (-1, -2), (0, 0), (1, 0), (2, -2), (3, -6)]
189

190

191
    AUTHORS:
192

193
    - David R. Kohel <[email protected]>: original version.
194
    
195
    - Charlie Turner (06-2010): small adjustments.
196
    """
197
    if is_Scheme(X):
198
        X = X(X.base_ring())
199
    n = X.codomain().ambient_space().ngens()
200
    if X.value_ring() is ZZ:
201
        Q = [ 1 ]
202
    else: # rational field
203
        Q = range(1, B + 1)
204
    R = [ 0 ] + [ s*k for k in range(1, B+1) for s in [1, -1] ]
205
    pts = []
206
    P = [0] * n
207
    m = ZZ(0)
208
    try:
209
        pts.append(X(P))
210
    except TypeError:
211
        pass
212
    iters = [ iter(R) for _ in range(n) ]
213
    for it in iters:
214
        it.next()
215
    i = 0
216
    while i < n:
217
        try:
218
            a = ZZ(iters[i].next())
219
        except StopIteration:
220
            iters[i] = iter(R) # reset
221
            P[i] = iters[i].next() # reset P[i] to 0 and increment
222
            i += 1
223
            continue
224
        m = m.gcd(a)
225
        P[i] = a
226
        for b in Q:
227
            if m.gcd(b) == 1:
228
                try:
229
                    pts.append(X([ num/b for num in P ]))
230
                except TypeError:
231
                    pass
232
        i = 0
233
        m = ZZ(0)
234
    pts.sort()
235
    return pts
236

237
def enum_projective_finite_field(X):
238
    """
239
    Enumerates projective points on scheme ``X`` defined over a finite field.
240
    
241
    INPUT:
242
    
243
    - ``X`` -  a scheme defined over a finite field or a set of abstract
244
      rational points of such a scheme.
245

246
    OUTPUT: 
247

248
    - a list containing the projective points of ``X`` over the finite field,
249
      sorted.
250

251
    EXAMPLES::
252

253
        sage: F = GF(53)
254
        sage: P.<X,Y,Z> = ProjectiveSpace(2,F)
255
        sage: from sage.schemes.generic.rational_point import enum_projective_finite_field
256
        sage: len(enum_projective_finite_field(P(F)))
257
        2863
258
        sage: 53^2+53+1
259
        2863
260

261
    ::
262

263
        sage: F = GF(9,'a')
264
        sage: P.<X,Y,Z> = ProjectiveSpace(2,F)
265
        sage: C = Curve(X^3-Y^3+Z^2*Y)
266
        sage: enum_projective_finite_field(C(F))
267
        [(0 : 0 : 1), (0 : 1 : 1), (0 : 2 : 1), (1 : 1 : 0), (a + 1 : 2*a : 1),
268
        (a + 1 : 2*a + 1 : 1), (a + 1 : 2*a + 2 : 1), (2*a + 2 : a : 1), 
269
        (2*a + 2 : a + 1 : 1), (2*a + 2 : a + 2 : 1)]
270
        
271
    ::
272

273
        sage: F = GF(5)
274
        sage: P2F.<X,Y,Z> = ProjectiveSpace(2,F)
275
        sage: enum_projective_finite_field(P2F)
276
        [(0 : 0 : 1), (0 : 1 : 0), (0 : 1 : 1), (0 : 2 : 1), (0 : 3 : 1), (0 : 4 : 1),
277
        (1 : 0 : 0), (1 : 0 : 1), (1 : 1 : 0), (1 : 1 : 1), (1 : 2 : 1), (1 : 3 : 1),
278
        (1 : 4 : 1), (2 : 0 : 1), (2 : 1 : 0), (2 : 1 : 1), (2 : 2 : 1), (2 : 3 : 1), 
279
        (2 : 4 : 1), (3 : 0 : 1), (3 : 1 : 0), (3 : 1 : 1), (3 : 2 : 1), (3 : 3 : 1),
280
        (3 : 4 : 1), (4 : 0 : 1), (4 : 1 : 0), (4 : 1 : 1), (4 : 2 : 1), (4 : 3 : 1),
281
        (4 : 4 : 1)]
282

283
    ALGORITHM: 
284

285
    Checks all points in projective space to see if they lie on X.
286

287
    .. WARNING::
288
    
289
        If ``X`` is defined over an infinite field, this code will not finish!
290

291
    AUTHORS:
292
   
293
    - John Cremona and Charlie Turner (06-2010).
294
    """
295
    if is_Scheme(X):
296
        X = X(X.base_ring())
297
    n = X.codomain().ambient_space().ngens()-1
298
    F = X.value_ring()
299
    pts = []
300
    for k in range(n+1):
301
        for c in cartesian_product_iterator([F for _ in range(k)]):
302
            try:
303
                pts.append(X(list(c)+[1]+[0]*(n-k)))
304
            except TypeError:
305
                pass
306
    pts.sort()
307
    return pts
308

309
def enum_affine_finite_field(X):
310
    r"""
311
    Enumerates affine points on scheme ``X`` defined over a finite field.
312
    
313
    INPUT:
314
    
315
    - ``X`` -  a scheme defined over a finite field or a set of abstract
316
      rational points of such a scheme.
317

318
    OUTPUT: 
319

320
    - a list containing the affine points of ``X`` over the finite field,
321
      sorted.
322

323
    EXAMPLES::
324

325
        sage: F = GF(7)
326
        sage: A.<w,x,y,z> = AffineSpace(4,F)
327
        sage: C = A.subscheme([w^2+x+4,y*z*x-6,z*y+w*x])
328
        sage: from sage.schemes.generic.rational_point import enum_affine_finite_field
329
        sage: enum_affine_finite_field(C(F))
330
        []
331
        sage: C = A.subscheme([w^2+x+4,y*z*x-6])        
332
        sage: enum_affine_finite_field(C(F))    
333
        [(0, 3, 1, 2), (0, 3, 2, 1), (0, 3, 3, 3), (0, 3, 4, 4), (0, 3, 5, 6),
334
        (0, 3, 6, 5), (1, 2, 1, 3), (1, 2, 2, 5), (1, 2, 3, 1), (1, 2, 4, 6), 
335
        (1, 2, 5, 2), (1, 2, 6, 4), (2, 6, 1, 1), (2, 6, 2, 4), (2, 6, 3, 5), 
336
        (2, 6, 4, 2), (2, 6, 5, 3), (2, 6, 6, 6), (3, 1, 1, 6), (3, 1, 2, 3), 
337
        (3, 1, 3, 2), (3, 1, 4, 5), (3, 1, 5, 4), (3, 1, 6, 1), (4, 1, 1, 6), 
338
        (4, 1, 2, 3), (4, 1, 3, 2), (4, 1, 4, 5), (4, 1, 5, 4), (4, 1, 6, 1), 
339
        (5, 6, 1, 1), (5, 6, 2, 4), (5, 6, 3, 5), (5, 6, 4, 2), (5, 6, 5, 3), 
340
        (5, 6, 6, 6), (6, 2, 1, 3), (6, 2, 2, 5), (6, 2, 3, 1), (6, 2, 4, 6), 
341
        (6, 2, 5, 2), (6, 2, 6, 4)]
342

343
    ::
344

345
        sage: A.<x,y,z> = AffineSpace(3,GF(3))
346
        sage: S = A.subscheme(x+y)
347
        sage: enum_affine_finite_field(S)
348
        [(0, 0, 0), (0, 0, 1), (0, 0, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2),
349
        (2, 1, 0), (2, 1, 1), (2, 1, 2)]
350
   
351
    ALGORITHM: 
352

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

355
    .. WARNING::
356
    
357
        If ``X`` is defined over an infinite field, this code will not finish!
358

359
    AUTHORS: 
360

361
    - John Cremona and Charlie Turner (06-2010)
362
    """
363
    if is_Scheme(X):
364
        X = X(X.base_ring())
365
    n = X.codomain().ambient_space().ngens()
366
    F = X.value_ring()
367
    pts = []
368
    for c in cartesian_product_iterator([F]*n):
369
        try:
370
            pts.append(X(c))
371
        except:
372
            pass
373
    pts.sort()
374
    return pts
375

376
Product

Resources

Company
