Enumeration functionality for products of projective spaces over fields and finite fields

[sagetrac-gjorgenson]

Implement enumeration functionality for products of projective spaces over fields/finite fields. Some basic class structure will need to be added to enable working specifically with such product spaces.

Also will make points of products of projective spaces hashable to increase the efficiency of the enumeration functionality. There is currently a bug with the hash implementations for points of projective spaces

P2.<x,y,z>=ProjectiveSpace(QQbar,2)
H=End(P2)
f=H([x^2+2*y^2,y^2-2*x^2,z^2])
X=P2.subscheme([x+y])
f.rational_preimages(P2([0,1,1])) # there are equal points, but with different hash values

so this will be addressed here as well. Some examples in projective_morphism need to be updated because of reordering in their outputs from the hash changes.

CC: @bhutz

Component: algebraic geometry

Author: Grayson Jorgenson

Branch/Commit: be82af5

Reviewer: Ben Hutz

Issue created by migration from https://trac.sagemath.org/ticket/19635

[sagetrac-gjorgenson]

Branch: u/gjorgenson/ticket/19635

[sagetrac-git]

Commit: 449d073

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

449d073

19635: FIrst pass at implementation

[bhutz]

Reviewer: Ben Hutz

[bhutz]

comment:5

A few minors things and a few larger things. I think before I do functionality testing some of these coding improvements should be made.

Minor

• You are changing the example in the ring class to give a field point. Perhaps you should change the ring instead of the output so that it is still a ring example

- <class 'sage.schemes.product_projective.point.ProductProjectiveSpaces_point_ring'>
+ <class 'sage.schemes.product_projective.point.ProductProjectiveSpaces_point_field'>

• no ending punctuation on errors
• in both of your brute force point searches you don't need the intermediate variable. You can just have:

for P in X.ambient_space().rational_points():

• remove references to self in doc strings. Instead say things like, this point, or this space.
• there are a number of spacing issues
  • between lists of polys, such as [x^2-y2, z^2-2*w2]
  • between function parameters, such as X.affine_patch(I, True)
  • between coordinates of points
• references need an underscore, [Doyle-Krumm]_

points function

• you should mention that this is computing all points for dimension 0 schemes regardless of base ring.
• output: should be "all points with height at most the bound are returned"
• you might need to .sort() your doctests so that they don't depend on the machine

Major

• with 7.1.beta1 there is a depracation in one of the function you use which causes a number of doctest failures, you should update to the new function.

sage -t --warn-long 56.2 schemes/generic/algebraic_scheme.py  # 1 doctest failed
sage -t --warn-long 56.2 schemes/product_projective/wehlerK3.py  # 1 doctest failed
sage -t --warn-long 56.2 schemes/projective/projective_space.py  # 1 doctest failed
sage -t --warn-long 56.2 schemes/product_projective/space.py  # 1 doctest failed
sage -t --warn-long 56.2 schemes/product_projective/morphism.py  # 1 doctest failed
sage -t --warn-long 56.2 schemes/product_projective/point.py  # 1 doctest failed
sage -t --warn-long 56.2 schemes/product_projective/homset.py  # 1 doctest failed

points function

• your dimension check doesn't actually work in all cases. I'd recommend using improve dimension function for subschemes of projective products #19991 as a dependency and switching to that dimension call.
• You seem to be going to a lot of trouble to generate possible indices for affine patches. Here is something shorter

dims = [n+1 for n in X.ambient_space().dimension_relative_components()]
for I in xmrange(dims):

You should be able to improve the indices creator in points_of_bounded_height and rational_points as well

• You are returning points in the ambient space instead of the scheme. You should just have

points.add(phi(PP))

• hash() - for field, finite_field are exactly the same as for ring. So you don't need these functions as they will inherit, but add their examples to ring.

• The example changes in SchemeMorphism_polynomial_projective_space_field. why did they change? Are these are sorting problem?

• in rationalpoints()
  I don't like that you are generating all the points in all the projective spaces and then generating all possible indices. We can do this more memory efficiently; something like:

P = ProductProjectiveSpaces([1,1,1,2],GF(2))
iters = [ iter(T) for T in P ]
L=[]
for x in iters:
    L.append(next(x)) # put at zero
points=[P(L)]
j = 0
while j < P.num_components():
    try:
        L[j] = next(iters[j])
        points.append(copy(P(L)))
        j = 0
    except StopIteration:
        iters[j] = iter(P[j])  # reset
        L[j] = next(iters[j]) # put at zero
        j += 1

speaking of which. I'd like to see this as an _iter_ function in addition to a rational_points function.

[bhutz]

comment:6

The need to use copy() in the iterator was bothering me and this seems to be a more endemic problem. If you initialize a point with a list of points and change an element of that list, it changes the point. This does not seem like desired behavior as it does not behave like that for regular projective points.

P=ProjectiveSpace(1,QQ,'x')
P2=ProjectiveSpace(1,QQ,'y')
PP=P2.cartesian_product(P)
Q=P(1,1)
Q2=P2(0,1)
M=[Q2,Q]
QQ=PP(M);print QQ
M[0]=P2([1,1]);print QQ

Consequently, I think the copy needs to be somewhere in _init_

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

954bc26	19635: First round of changes from review.
83169cd	19635: Merge branch 'master' into u/gjorgenson/ticket/19635
edfad27	19635: Other changes from review.

[sagetrac-git]

Changed commit from 449d073 to edfad27

[sagetrac-gjorgenson]

comment:8

Okay I think I addressed the issues from the review and this should be ready for another look-over.

I added an __iter__ function for product spaces over finite fields making them iterable, but this broke a line in the dimension function for products in algebraic_scheme.py. In particular something like for PS in PP will now yield points instead of the component spaces of PP.

I'm not exactly sure why the output of some of the projective morphism examples got rearranged, but it definitely happened when I changed the hash function. I think it might be related to the use of set().

I also tried to address the copy issue for the __iter__ and rational_points functions. Just adding polys = copy(polys) to the first line of the __init__ function for points of products of projective spaces seems to fix the issue. However, I think a list of projective space points is just a list of references to the actual point objects, so applying copy to such a list just copies the references but not the objects themselves. So this fix does not protect against modification of the original objects:

P1=ProjectiveSpace(1,QQ,'x')
P2=ProjectiveSpace(1,QQ,'y')
PP=P1.cartesian_product(P2)
Q1=P1(0,1)
Q2=P2(1,1)
M=[Q1,Q2]
pt=PP(M)
print pt
M[0]._coords[0] = 1
print pt

Also, copy for projective space points seems to be too shallow:

P.<x,y,z> = ProjectiveSpace(QQ,2)
pt1 = P(1,2,3)
pt2 = copy(pt1)
print pt2
pt1._coords[0] = 7
print pt2

I'm not sure whether this really is an issue, but if it is, maybe we could override __copy__ for projective points.

[videlec]

comment:9

Why did you duplicate the code in __iter__ and rational_points? You can simply do

def rational_points(self):
    return list(self)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

266218f

19635: improved rational_points function

[sagetrac-git]

Changed commit from edfad27 to 266218f

[sagetrac-gjorgenson]

comment:11

Replying to @videlec:

Why did you duplicate the code in __iter__ and rational_points? You can simply do

def rational_points(self):
    return list(self)

I wasn't thinking; list(self) should have the same efficiency and is much cleaner. I also added the ability to find the rational points over extensions of the base field.

[bhutz]

comment:12

Much improved. Still a couple things.

1. I agree that _copy_ is not a fault of your code. This is a more general schemes issue

E=EllipticCurve([0,0,0,0,1])
T=E(0,1)
S=copy(T)
T._coords[1]=-1
T,S
((0 : -1 : 1), (0 : -1 : 1))

What you are doing is in line with everything else, so will be resolved when the more general generic/point copy is resolved.

2. hmmm...yes, a natural consequence of the point iterator is that iterating over the components with that simple loop no longer works. However, I think it is import to preserve a way to iterate over the components without resorting to accessing private data with ._components. I suggest a simple PP.components() function that returns ._components.

3. This documentation for rational_points() does not look right

rational points on the affine space of this space

4. base extension for rational_points() doesn't seem to work

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1],QQ)
X = PP.subscheme([u^3-v^3, s^2-t^2,])
X.dimension()
X.rational_points(bound=2,F= CyclotomicField(3,'z'))

versus

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1], CyclotomicField(3,'z'))
X = PP.subscheme([u^3-v^3, s^2-t^2,])
X.dimension()
X.rational_points()

or the same for QQbar...

5. shouldn't this work too

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1],GF(3))
X = PP.subscheme([u^3-v^3, s^2-t^2,])
X.dimension()
X.rational_points()

or

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1],GF(3))
X = PP.subscheme([u^3-v^3, s^2-t^2,])
X.dimension()
X.rational_points(F=GF(9,'z'))

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

94c689b

19635: Changes from second review

[sagetrac-git]

Changed commit from 266218f to 94c689b

[sagetrac-gjorgenson]

comment:14

I think I've resolved everything from the review, but I don't know whether my changes are really the right ways to address the issues in 4) and 5).

For the base extension issues in 4), the problem actually seemed to be from rational_points in algebraic_scheme.py for subschemes. The same issue can be seen with projective spaces:

P.<u,v> = ProjectiveSpace(CyclotomicField(3,'z'),1)
X = P.subscheme([u^3-v^3])
X.rational_points()

vs

P.<u,v> = ProjectiveSpace(QQ,1)
X = P.subscheme([u^3-v^3])
X.rational_points(F=CyclotomicField(3,'z'))

This seemed to be happening because of line 1520 of algebraic_scheme.py which sets X = self(F), but the codomain of the resulting homset is still the original subscheme, and not one over the extension. I tried changing this to X = self.base_extend(F)(F) so that the codomain is defined over the extension. Is this what we actually want in order to find the rational points over the extension?

The issue in 5) seemed to be related to a coercion problem. There is some coercion in place when initializing projective points from lists, but not for initializing points of products of projective spaces. Things like

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1],GF(3))
X = PP.subscheme([u^3-v^3, s^2-t^2,])
l = [QQ(1) for k in range(4)]
Q = X(l)

don't work. The problem causing the issues with finite fields seemed to come from this, though I don't know why a list of rational numbers is being used to initialize a point. I think this list came about from __fast_eval for affine morphisms. I added something similar to what's done for projective points, and this seemed to fix the problem.

[bhutz]

comment:15

I think the fix for 4 is the right thing to do. I don't fully understand what issue you are describing for (5). _fast_eval will only be called for evaluation maps and there are no maps here. I see the issue you are pointing out in the example above, and you've fixed that issue. Could you explain where this list of rational numbers is showing up in the code in my examples (4)?

[sagetrac-gjorgenson]

comment:16

The coercion problem comes up in the example

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1],GF(3))
X = PP.subscheme([u^3-v^3, s^2-t^2,])
X.dimension()
X.rational_points()

when using the affine morphisms corresponding to the affine patches used for finding points. In particular, a rational number list shows up when evaluating one of the affine morphisms at the rational points from the corresponding patch. The following traces some of the code in rational_points for the above example to capture when the list shows up:

PP.<u,v,s,t> = ProductProjectiveSpaces([1,1],GF(3))
X = PP.subscheme([u^3-v^3, s^2-t^2,])
X = X(GF(3)).codomain()
[Y,phi] = X.affine_patch([0,0], True)
x = Y.rational_points()[0]
# expanding out what happens in phi(x):
print [x._coords[i].parent() for i in range(len(x._coords))] # coordinates are finite field elements
P = phi._fast_eval(x._coords)
print [P[i].parent() for i in range(len(P))] # resulting coordinates are rational field elements
print phi.codomain().point(P, True) # this then breaks without the coercion implemented in last commit

Adding the coercion got around the issue, but I'm not sure why _fast_eval gives a list of rational numbers here.

[bhutz]

comment:17

ok. _fast_eval is returning a list defined over a ring based on what will be most quickly computed. Then the coordinates are coerced when it is made into a point. However, for subschemes, check_satisfies_equations was being called before the coordinates were coerced, causing the error. So your fix does solve the problem, by coercing first.

The functionality checkouts to me. There are just a couple very minor things:

• functions needs one line desctiption and then more details. There are several where the docs start with a paragraph.

• wrap the super long imports (see other files for examples)

• needs space before ZZ.

sage: P.<x,y,z,w> = ProductProjectiveSpaces([1,1],ZZ)

[sagetrac-git]

Changed commit from 94c689b to be82af5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

be82af5

19635: Minor documentation and spacing fixes.

[sagetrac-gjorgenson]

comment:19

Thanks. I also removed a couple lines in homset.py that are no longer used with the new dimension check in place.

[vbraun]

Changed branch from u/gjorgenson/ticket/19635 to be82af5