Opened 5 years ago

Closed 4 years ago

Last modified 18 months ago

#14219 closed enhancement (fixed)

rational preperiodic points for projective morphisms

Reported by: bhutz Owned by: bhutz
Priority: major Milestone: sage-5.13
Component: algebraic geometry Keywords: dynamics, sage-days55
Cc: Merged in: sage-5.13.beta4
Authors: Ben Hutz Reviewers: Vincent Delecroix, Adam Towsley
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14218 Stopgaps:

Description (last modified by bhutz)

Main algorithms from Hutz, "Determination of all rational preperiodic points for morphisms of PN", submitted

Also includes the last of the ICERM dynamics functionality. Building on #13130, #14217, #14218.

Implements all necessary functionality to determine QQ-rational periodic and preperiodic points for morphism of projective space in any dimension. This includes multipliers, hensel lifting, height difference bound, etc.

Apply:

Attachments (3)

rational_preperiodic.patch (48.6 KB) - added by bhutz 5 years ago.
trac_14219-optimize_root_order_computation.patch (2.6 KB) - added by vdelecroix 4 years ago.
optimize the root order computation over finite fields
trac_14219_rational_preperiodic.patch (50.5 KB) - added by bhutz 4 years ago.
changes made

Download all attachments as: .zip

Change History (29)

Changed 5 years ago by bhutz

comment:1 Changed 5 years ago by chapoton

  • Description modified (diff)

comment:2 Changed 5 years ago by chapoton

  • Dependencies changed from 14128 to #14128

comment:3 Changed 5 years ago by chapoton

  • Dependencies changed from #14128 to #14218

comment:4 Changed 5 years ago by bhutz

  • Description modified (diff)

comment:5 Changed 4 years ago by bhutz

  • Milestone changed from sage-5.9 to sage-5.10
  • Status changed from new to needs_review

Finished cleaning it up. Ready for review.

Changed the milestone to something more realistic.

comment:6 Changed 4 years ago by chapoton

apply trac_14219_rational_preperiodic.patch

comment:7 Changed 4 years ago by chapoton

  • Keywords dynamics added
  • Status changed from needs_review to needs_work
  • Work issues set to doctest missing

There is one doctest missing.

comment:8 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 4 years ago by bhutz

  • Status changed from needs_work to needs_review
  • Work issues doctest missing deleted

Fixed the missing doctest.

This passes all tests on my machine for sage 5.11.

comment:10 Changed 4 years ago by bhutz

apply trac_14219_rational_preperiodic.patch

comment:11 Changed 4 years ago by bhutz

apply trac_14219_rational_preperiodic.patch

comment:12 Changed 4 years ago by bhutz

apply trac_14219_rational_preperiodic.patch

comment:13 Changed 4 years ago by bhutz

apply trac_14219_rational_preperiodic.patch

Changed 4 years ago by vdelecroix

optimize the root order computation over finite fields

comment:14 Changed 4 years ago by vdelecroix

Hi there,

Some quick comments (I am not the person designed to review the mathematics in there):

  • the patch does not apply on sage-5.13.beta2
  • there are many trailing whitescaces that need to be removed
  • the indentation must be 4 spaces wide (it is 3 in many places)
  • sage convention is that CamelCaseConvention is somewhat reserved to classes and it would be better to not use it as variables names (I think this is too much pain to change it right now)
  • in the examples one should use "a = bla()" instead of "a=bla()"

We also discussed a very specific issue in the code (line 2588 to 2601). The trac_14219-optimize_root_order_computation.patch proposes a much direct version with, as a consequence, a little bit of speedup.

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:15 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:16 Changed 4 years ago by bhutz

  • Keywords sage-days55 added
  • Reviewers set to Vincent Delecroix

The change for the eigenvalue computation looks fine, I've folded that into the main patch.

I removed the whitespace and added the spaces around the = signs.

I also adjusted the variable naming as that wasn't too tedious.

I couldn't find any 3 space indents, could you point out where those are.

comment:17 Changed 4 years ago by vdelecroix

To be modified in projective_morphism.py

1) trailing whitespaces in at lines 1663, 1754, 1954, 1971, 1982, 1985, 1992, 1998, 2085, 2106, 2158, 2169, 2221, 2257, 2273, 2317, 2352,

2) why do you use Hom(P,P) instead of End(P) ?

3) problem of upper case/lower case at line 1746 (Periods instead of periods)

4) prefer (line 1743-1746)

return sorted(periods)

instead of

periods=list(periods)
periods.sort()
return(periods)

5) in method dynatomic_polynomial the argument is called period but is refered in the documentation as n. Moreover the specification of arguments are given too late. In the examples it might be good to check that the dynatomic polynomial actually gives you solution!

sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: H = Hom(P,P)
sage: f = H([x^2+y^2,y^2])
sage: f.dynatomic_polynomial(2)
x^2 + x*y + 2*y^2
sage: K.<c> = NumberField(X^2 + X + 2, 'c')
sage: PP = P.change_ring(K)
sage: ff = f.change_ring(K)
sage: p = PP((c,1))
sage: ff(ff(p)) == p

Here I get troubles with coercions (this is why I defined PP and ff): there should be some canonical coercions as there is for polynomials (this will go in another ticket)

sage: R.<x> = PolynomialRing(QQ,'x')
sage: K.<c> = NumberField(x^2 + 3*x + 1, 'c')
sage: P = x^6 + 3*x + 19
sage: P(c)
-141*c - 36

6) The rational for the choice of putting methods in projective_point.py instead in projective_morphism.py is not at all clear to me. Why orbit, canonical_heights, etc methods of points and not of morphisms ?

7) docbuild troubles [schemes ] /opt/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space_field.rational_periodic_points:4: WARNING: Inline literal start-string without end-string. [schemes ] /opt/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space_field.rational_periodic_points:72: WARNING: Inline strong start-string without end-string. [schemes ] /opt/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism:7: WARNING: Bullet list ends without a blank line; unexpected unindent. [schemes ] /opt/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space_field.rational_preperiodic_points:4: WARNING: Inline literal start-string without end-string. [schemes ] /opt/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism:12: WARNING: Bullet list ends without a blank line; unexpected unindent.

8) I have serious trouble concerning the green function and canonical heights of points (I know that this was implemented in another ticket). In those two methods, there is no care about the fact that there are errors introduced by the fact that the floating points you are working with are with fixed precision. In particular, with floating points, the result of x+y is *not* the sum x + y but only an approximation of it. I really think that it should be reimplemented either using real interval fields (it will make it slower but at least you get a proven answer).

comment:18 Changed 4 years ago by bhutz

fixed: 1,2,3,4,7

5 - is two separate issues for other tickets

6 - since the methods depends on both points I didn't think it mattered. I can see a preference for the code in morphism. If this is a strong preference for Sage users, then open a separate ticket to move this.

8 - also an issue for a separate ticket

comment:19 Changed 4 years ago by bhutz

  • Status changed from needs_work to needs_review

comment:20 Changed 4 years ago by atowsley

  • Status changed from needs_review to needs_work

The multiplier (and multipliermod) functions should have a check that the point P does have period n.

comment:21 Changed 4 years ago by atowsley

Here are a few more comments:

1) Please remove debugging code from lines 1865-1968.

2) It would be helpful to have some more comments to the code for the Henzel lifting to make it easier to read.

3) Use is_endomorphism() where possible. Lines 2044, 2138, and 2199.

4) I think it would be clearer if the rational_preimages and all_rational_preimages were written in that order. That is the reverse of how they appear now.

5) Line 2145 the set 'preperiodic' as the name is misleading. Maybe 'all_preimages' would be better?

6) More comments on the Groebner basis code would be nice.

7) You should consider caching the functions rational_preperiodic_points and rational_periodic_points.

comment:22 Changed 4 years ago by bhutz

Multiplier check added for the (2)-previous comment. I added a parameter to specify whether to do this or not as this function is called many times for rational_periodic and it would be better not to check if you known the input is good.

1,2,3,4,5,6 all done

7) Not possible since the points are rational projective points and they are not hashable (only hashable over finite fields)

I also changed the mrange to xmrange in lift_to_rational to help improve the higher dimension performance.

Last edited 4 years ago by bhutz (previous) (diff)

Changed 4 years ago by bhutz

changes made

comment:23 Changed 4 years ago by atowsley

  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Adam Towsley
  • Status changed from needs_work to positive_review

All tests passed. Everything looks good.

comment:24 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.13.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:25 Changed 4 years ago by jdemeyer

  • Authors changed from Ben Hutz to Benjamin Hutz

comment:26 Changed 18 months ago by chapoton

  • Authors changed from Benjamin Hutz to Ben Hutz
Note: See TracTickets for help on using tickets.