rational preperiodic points for projective morphisms #14219

bhutz · 2013-03-03T18:35:02Z

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:

attachment: trac_14219_rational_preperiodic.patch

Depends on #14218

Component: algebraic geometry

Keywords: dynamics, sage-days55

Author: Ben Hutz

Reviewer: Vincent Delecroix, Adam Towsley

Merged: sage-5.13.beta4

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

fchapoton · 2013-03-06T12:50:20Z

comment:1

Attachment: rational_preperiodic.patch.gz

fchapoton · 2013-03-06T12:50:35Z

Changed dependencies from 14128 to #14128

fchapoton · 2013-03-06T12:51:55Z

Changed dependencies from #14128 to #14218

bhutz · 2013-04-15T16:26:27Z

comment:5

Finished cleaning it up. Ready for review.

Changed the milestone to something more realistic.

fchapoton · 2013-05-07T20:05:37Z

comment:6

apply trac_14219_rational_preperiodic.patch

fchapoton · 2013-05-23T19:52:03Z

comment:7

There is one doctest missing.

fchapoton · 2013-05-23T19:52:03Z

Work Issues: doctest missing

fchapoton · 2013-05-23T19:52:03Z

Changed keywords from none to dynamics

bhutz · 2013-08-23T22:55:16Z

comment:9

Fixed the missing doctest.

This passes all tests on my machine for sage 5.11.

bhutz · 2013-08-23T22:55:16Z

Changed work issues from doctest missing to none

bhutz · 2013-08-23T22:56:49Z

comment:10

apply trac_14219_rational_preperiodic.patch

bhutz · 2013-09-04T16:37:18Z

comment:11

apply trac_14219_rational_preperiodic.patch

bhutz · 2013-10-20T13:02:07Z

comment:12

apply trac_14219_rational_preperiodic.patch

bhutz · 2013-10-21T17:35:22Z

comment:13

apply trac_14219_rational_preperiodic.patch

videlec · 2013-11-07T19:46:05Z

optimize the root order computation over finite fields

videlec · 2013-11-07T19:46:33Z

comment:14

Attachment: trac_14219-optimize_root_order_computation.patch.gz

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 attachment: trac_14219-optimize_root_order_computation.patch proposes a much direct version with, as a consequence, a little bit of speedup.

bhutz · 2013-11-08T15:55:02Z

Changed keywords from dynamics to dynamics, sage-days55

bhutz · 2013-11-08T15:55:02Z

Reviewer: Vincent Delecroix

bhutz · 2013-11-08T15:55:02Z

comment:16

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.

videlec · 2013-11-08T21:20:08Z

comment:17

To be modified in projective_morphism.py

trailing whitespaces in at lines 1663, 1754, 1954, 1971, 1982, 1985, 1992, 1998, 2085, 2106, 2158, 2169, 2221, 2257, 2273, 2317, 2352,
why do you use Hom(P,P) instead of End(P) ?
problem of upper case/lower case at line 1746 (Periods instead of periods)
prefer (line 1743-1746)

return sorted(periods)

instead of

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

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

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

bhutz · 2013-11-08T23:01:32Z

comment:18

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

sagetrac-atowsley · 2013-11-10T16:41:39Z

comment:20

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

sagetrac-atowsley · 2013-11-10T17:30:01Z

comment:21

Here are a few more comments:

Please remove debugging code from lines 1865-1968.
It would be helpful to have some more comments to the code for the Henzel lifting to make it easier to read.
Use is_endomorphism() where possible. Lines 2044, 2138, and 2199.
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.
Line 2145 the set 'preperiodic' as the name is misleading. Maybe 'all_preimages' would be better?
More comments on the Groebner basis code would be nice.
You should consider caching the functions rational_preperiodic_points and rational_periodic_points.

bhutz · 2013-11-10T18:12:29Z

comment:22

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

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.

bhutz · 2013-11-10T18:13:07Z

changes made

sagetrac-atowsley · 2013-11-12T15:34:11Z

Changed reviewer from Vincent Delecroix to Vincent Delecroix, Adam Towsley

sagetrac-atowsley · 2013-11-12T15:34:11Z

comment:23

Attachment: trac_14219_rational_preperiodic.patch.gz

All tests passed. Everything looks good.

jdemeyer · 2013-11-22T15:49:05Z

Merged: sage-5.13.beta4

jdemeyer · 2013-12-15T08:43:03Z

Changed author from Ben Hutz to Benjamin Hutz

fchapoton · 2016-04-15T20:27:20Z

Changed author from Benjamin Hutz to Ben Hutz

bhutz added this to the sage-5.9 milestone Mar 3, 2013

bhutz added c: algebraic geometry labels Mar 3, 2013

bhutz self-assigned this Mar 3, 2013

This comment has been minimized.

Sign in to view

bhutz added the s: needs review label Apr 15, 2013

bhutz modified the milestones: sage-5.9, sage-5.10 Apr 15, 2013

fchapoton added s: needs work and removed s: needs review labels May 23, 2013

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

bhutz added s: needs review and removed s: needs work labels Aug 23, 2013

videlec added s: needs work and removed s: needs review labels Nov 7, 2013

bhutz added s: needs review and removed s: needs work labels Nov 10, 2013

sagetrac-atowsley mannequin added s: needs work and removed s: needs review labels Nov 10, 2013

sagetrac-atowsley mannequin added s: positive review and removed s: needs work labels Nov 12, 2013

jdemeyer removed the s: positive review label Nov 22, 2013

jdemeyer closed this as completed Nov 22, 2013

bhutz mentioned this issue Apr 15, 2016

Implement minimal model algorithm #15392

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

rational preperiodic points for projective morphisms #14219

rational preperiodic points for projective morphisms #14219

bhutz commented Mar 3, 2013

This comment has been minimized.

fchapoton commented Mar 6, 2013

fchapoton commented Mar 6, 2013

fchapoton commented Mar 6, 2013

This comment has been minimized.

bhutz commented Apr 15, 2013

fchapoton commented May 7, 2013

fchapoton commented May 23, 2013

fchapoton commented May 23, 2013

fchapoton commented May 23, 2013

bhutz commented Aug 23, 2013

bhutz commented Aug 23, 2013

bhutz commented Aug 23, 2013

bhutz commented Sep 4, 2013

bhutz commented Oct 20, 2013

bhutz commented Oct 21, 2013

videlec commented Nov 7, 2013

videlec commented Nov 7, 2013

bhutz commented Nov 8, 2013

bhutz commented Nov 8, 2013

bhutz commented Nov 8, 2013

videlec commented Nov 8, 2013

bhutz commented Nov 8, 2013

sagetrac-atowsley mannequin commented Nov 10, 2013

sagetrac-atowsley mannequin commented Nov 10, 2013

bhutz commented Nov 10, 2013

bhutz commented Nov 10, 2013

sagetrac-atowsley mannequin commented Nov 12, 2013

sagetrac-atowsley mannequin commented Nov 12, 2013

jdemeyer commented Nov 22, 2013

jdemeyer commented Dec 15, 2013

fchapoton commented Apr 15, 2016

rational preperiodic points for projective morphisms #14219

rational preperiodic points for projective morphisms #14219

Comments

bhutz commented Mar 3, 2013

This comment has been minimized.

fchapoton commented Mar 6, 2013

fchapoton commented Mar 6, 2013

fchapoton commented Mar 6, 2013

This comment has been minimized.

bhutz commented Apr 15, 2013

fchapoton commented May 7, 2013

fchapoton commented May 23, 2013

fchapoton commented May 23, 2013

fchapoton commented May 23, 2013

bhutz commented Aug 23, 2013

bhutz commented Aug 23, 2013

bhutz commented Aug 23, 2013

bhutz commented Sep 4, 2013

bhutz commented Oct 20, 2013

bhutz commented Oct 21, 2013

videlec commented Nov 7, 2013

videlec commented Nov 7, 2013

bhutz commented Nov 8, 2013

bhutz commented Nov 8, 2013

bhutz commented Nov 8, 2013

videlec commented Nov 8, 2013

bhutz commented Nov 8, 2013

sagetrac-atowsley mannequin commented Nov 10, 2013

sagetrac-atowsley mannequin commented Nov 10, 2013

bhutz commented Nov 10, 2013

bhutz commented Nov 10, 2013

sagetrac-atowsley mannequin commented Nov 12, 2013

sagetrac-atowsley mannequin commented Nov 12, 2013

jdemeyer commented Nov 22, 2013

jdemeyer commented Dec 15, 2013

fchapoton commented Apr 15, 2016