#19635 closed enhancement (fixed)

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

Reported by: gjorgenson Owned by:
Priority: minor Milestone: sage-7.3
Component: algebraic geometry Keywords:
Cc: bhutz Merged in:
Authors: Grayson Jorgenson Reviewers: Ben Hutz
Report Upstream: N/A Work issues:
Branch: be82af5 (Commits) Commit: be82af546be820168c9b464e273fb32cfc8dbe16
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (21)

comment:1 Changed 22 months ago by gjorgenson

  • Branch set to u/gjorgenson/ticket/19635

comment:2 Changed 20 months ago by gjorgenson

  • Description modified (diff)
  • Milestone changed from sage-6.10 to sage-7.1
  • Summary changed from Products of projective spaces over fields and finite fields to Enumeration functionality for products of projective spaces over fields and finite fields

comment:3 Changed 20 months ago by git

  • Commit set to 449d0738bfd0d9e85deea38f5ff94cdf1356e745

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

449d07319635: FIrst pass at implementation

comment:4 Changed 20 months ago by gjorgenson

  • Status changed from new to needs_review

comment:5 Changed 20 months ago by bhutz

  • Reviewers set to Ben Hutz
  • Status changed from needs_review to needs_work

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 [x2-y2, z2-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 #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.

comment:6 Changed 20 months ago by bhutz

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_

comment:7 Changed 17 months ago by git

  • Commit changed from 449d0738bfd0d9e85deea38f5ff94cdf1356e745 to edfad27dd51435adf0d65e6e7e6c005c78ed7993

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

954bc2619635: First round of changes from review.
83169cd19635: Merge branch 'master' into u/gjorgenson/ticket/19635
edfad2719635: Other changes from review.

comment:8 Changed 17 months ago by gjorgenson

  • Milestone changed from sage-7.1 to sage-7.3
  • Status changed from needs_work to needs_review

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.

comment:9 follow-up: Changed 17 months ago by vdelecroix

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

def rational_points(self):
    return list(self)

comment:10 Changed 17 months ago by git

  • Commit changed from edfad27dd51435adf0d65e6e7e6c005c78ed7993 to 266218f68838ce9449a4f549fb16f6990e0bd5af

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

266218f19635: improved rational_points function

comment:11 in reply to: ↑ 9 Changed 17 months ago by gjorgenson

Replying to vdelecroix:

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.

comment:12 Changed 17 months ago by bhutz

  • Status changed from needs_review to needs_work

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

comment:13 Changed 17 months ago by git

  • Commit changed from 266218f68838ce9449a4f549fb16f6990e0bd5af to 94c689bd21966bab1057f22d8dab1eeaec85314e

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

94c689b19635: Changes from second review

comment:14 Changed 17 months ago by gjorgenson

  • Status changed from needs_work to needs_review

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.

comment:15 Changed 17 months ago by bhutz

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

comment:16 Changed 17 months ago by gjorgenson

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.

comment:17 Changed 17 months ago by bhutz

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)

comment:18 Changed 17 months ago by git

  • Commit changed from 94c689bd21966bab1057f22d8dab1eeaec85314e to be82af546be820168c9b464e273fb32cfc8dbe16

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

be82af519635: Minor documentation and spacing fixes.

comment:19 Changed 17 months ago by gjorgenson

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

comment:20 Changed 16 months ago by bhutz

  • Status changed from needs_review to positive_review

comment:21 Changed 16 months ago by vbraun

  • Branch changed from u/gjorgenson/ticket/19635 to be82af546be820168c9b464e273fb32cfc8dbe16
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.