Opened 10 years ago

Closed 10 years ago

#14217 closed enhancement (fixed)

basic iteration functionality for affine and projective morphisms

Reported by: Ben Hutz Owned by: Ben Hutz
Priority: major Milestone: sage-5.10
Component: algebraic geometry Keywords: iteration, dynamics, projective, affine
Cc: Merged in: sage-5.10.beta3
Authors: Ben Hutz Reviewers: Adam Towsley
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13130 Stopgaps:

Status badges

Description (last modified by Ben Hutz)

This patch implements most of the initial dynamics functionality problems proposed at the 2012 ICERM semester in Complex and Arithmetic dynamics. There are two more patches (not yet open) that follow this one that will complete this functionality.

Building on #13130

  • finishes dividing affine/projective points/polynomial morphisms into ring/field/finite_field classes.
  • implements the following functions

Affine_space:

  • dimension : returns the dimension of the space
  • change_ring: changes the base ring of the space

Affine_polynomial_morphism

  • homogenize: using the embedding An into Pn
  • dynatomic_polynomial: related to preperoidic points, see function description for details
  • nth_iterate: determine the nth iterate of the point
  • nth_iterate_map: determine nth iterate of the map
  • orbit: determine a list of points in the orbit of P by f

for finite fields

  • cyclegraph: the Digraph of orbits over the finite field

Affine point morphism: finite fields

  • _hash_ : hash value of the point
  • orbit_structure: determine the period and preperiod of P by f

Projective space:

  • change_ring: change the base ring of the projective space
  • base_ring: return the base_ring of the projective space
  • coordinate_ring: return the coordinate ring of the projective space

Projective_polynomial:

  • change_ring: change the base ring of the morphism
  • base_ring: return the base_ring of the morphism
  • dynatomic_polynomial: related to preperoidic points, see function description for details
  • nth_iterate: determine the nth iterate of the point
  • nth_iterate_map: determine the map
  • orbit: determine a list of points in the orbit of P by f
  • degree: return the degree of the morphism
  • dehomogenize: dehomogenize to the appropriate affine space
  • is_morphism: determine the coordinate functions of f have any common zeros
  • resultant: for maps on P1, determines the resultant of f[0],f[1]
  • primes_of_bad_reduction: determines primes of bad reduction
  • conjugate: determine the conjugate morphism by the given matrix

for finite fields

  • orbit_structure: determine the period and preperiod of P by f
  • cyclegraph: the Digraph of orbits over the finite field

projective point morphism

  • dehomogenize: dehomogenize the point to the appropriate affine space
  • normalize_coordinates: clear any common factors of coordinates
  • clear_denominators: scale so that each coordinate is in the ring (of the base_ring)

for finite fields

  • _hash_: determine the hash value of a point

Functions that take both maps and points as input are callable in member functions of either class, but duplicated in the lists above

Restructured the schemes directories to have an affine and a projective directory. Moved the appropriate code into those directories from generic.morphism.py, generic.affine_space.py, generic.projective_space.py, generic.homset.py, generic.rational_point.py. The morphism code was also divided into separate files for points and maps. This required changes to the documentation structure as well.

Apply:

Attachments (1)

trac_14217_base_functionality.patch (336.5 KB) - added by Ben Hutz 10 years ago.
basic iteration functionality for affine and projective spaces

Download all attachments as: .zip

Change History (38)

comment:1 Changed 10 years ago by Michelle Manes

All tests passed.

One file didn't have 100% coverage (see below). I will work on testing functionality soon.

michelle-2:sage mmanes$ ../../sage -coverage sage/schemes/generic/algebraic_scheme.py


SCORE sage/schemes/generic/algebraic_scheme.py: 95.0% (57 of 60)

Missing documentation:

  • line 551: def _point_homset(self, *args, kwds)
  • line 554: def _point(self, *args, kwds)
  • line 1513: def _morphism(self, *args, kwds)

Possibly wrong (function name doesn't occur in doctests):

  • line 528: def _homset(self, *args, kwds)

comment:2 Changed 10 years ago by Frédéric Chapoton

Dependencies: 13130#13130
Description: modified (diff)

comment:3 Changed 10 years ago by Frédéric Chapoton

  • You should write
    INPUT:
    

and

OUTPUT:

with only a single :

  • You should write
    EXAMPLES::
    

using capital letters.

comment:4 Changed 10 years ago by Ben Hutz

I've updated the documentation to fix the issues in #13130 and the coverage issues from Michelle's comments above and renamed the patch to have the trac number in it.

comment:5 Changed 10 years ago by Ben Hutz

Description: modified (diff)

comment:6 Changed 10 years ago by Frédéric Chapoton

There are now several "OTUPUT:: "

Please build the documentation (sage -docbuild reference html) and check the html file obtained.

comment:7 Changed 10 years ago by Frédéric Chapoton

In my opinion, the INPUT whith None are not very useful and should be removed.

There is also at least one INPUT: Npne.

Another typo : Every points is preperiodic

There should be only one : after ALGORITHM

For how to write the doc, you may have a look at http://www.sagemath.org/doc/developer/conventions.html

comment:8 Changed 10 years ago by Frédéric Chapoton

Found some typos:

  • homoenize
  • coordiante (several times)
  • coordiantes (several times)
  • generatred
  • dehomgenize

For arxiv references, you may use the syntax :arxiv:`1210.6246`

You should write

.. TODO::

One suggestion of shorter (equivalent) code for the hash function of points over finite fields

p = self.codomain().base_ring().order() 
N = self.codomain().ambient_space().dimension_relative() 
return sum(hash(self[i])*p**i for i in range(N+1))

I suggest (but this is optional) to use the Python3 syntax for the raise statements:

raise ValueError("can not dehomogenize at 0 coordinate")

comment:9 Changed 10 years ago by Ben Hutz

Made the changes suggested above. However, the :arxiv: syntax was not accepted.

Restructured the schemes directories to have an affine and a projective directory. Moved the appropriate code into those directories from generic.morphism.py, generic.affine_space.py, generic.projective_space.py, generic.homset.py, generic.rational_point.py. The morphism code was also divided into separate files for points and maps. This required changes to the documentation structure as well.

I consider this ready for review now.

comment:10 Changed 10 years ago by Ben Hutz

Description: modified (diff)
Status: newneeds_review

comment:11 Changed 10 years ago by Frédéric Chapoton

for the bot:

apply trac_14217_base_functionality.patch

comment:12 Changed 10 years ago by Frédéric Chapoton

two remarks

  • the patch is now too big to be displayed inside trac. While not a true problem, this does not make the review easy. The idea of moving many things around may rather have been the subject of its own ticket in my opinion. But let's forget about that for now.
  • it needs to be rebased on a more recent sage, see the bot report.

comment:13 Changed 10 years ago by Adam Towsley

It passed the long test. Other than that I found two functionality issues and a documentation issue.

The documentation issue: There should be examples for dynatomic polynomials when the base ring is a polynomial ring.

The functionality issues: 1) The dynatomic polynomial function doesn't work when the base ring is a polynomial ring over a function field.

2) The dynatomic polynomial function doesn't work when the base ring is GF(p)[t] or QQ[t] and the map is not isotrivial. (for example f = x2 + 3 works, but f = x2 + t doesn't). However isotrivial maps in ZZ[t], RR[t], and CC[t] seem to work.

Version 0, edited 10 years ago by Adam Towsley (next)

comment:14 Changed 10 years ago by Ben Hutz

The documentation is added (and also to orbit() and nth_iterate())

Issue (1) is fixed by returning NotImplementedError?

For (2), I'm not sure what you mean by "not works". It works fine for me. Yes, it doesn't do the division so it returns a rational function, but it is the correct rational function.

Also, I noticed there is a patchbot error on the ticket. The bot seems to be trying to apply bot patches, when it should only be applying the second. I thought this ticket is clearly marked for "apply", what else needs to be done?

comment:15 Changed 10 years ago by Frédéric Chapoton

The apply statement in the description field is not used by the bot

Instructions for the bot must be given in comments as follows :

apply trac_14217_base_functionality.patch

comment:16 Changed 10 years ago by Ben Hutz

Comment 11 already has that type of apply statement, but according to the log error, the bot was still trying to apply both attachments.

comment:17 Changed 10 years ago by Frédéric Chapoton

Well, the bot is not very clever, and therefore it is better to repeat the instructions each time you upload a new patch. At the top of the bot page of the ticket, you can see which patches it is going to apply.

comment:18 Changed 10 years ago by Frédéric Chapoton

This needs to be rebased, see the bot report

comment:19 Changed 10 years ago by Ben Hutz

Yes, I was actually just finishing working on it and will shortly upload the new version.

comment:20 Changed 10 years ago by Ben Hutz

for the bot:

apply trac_14217_base_functionality.patch

comment:21 Changed 10 years ago by Ben Hutz

for the bot:

apply trac_14217_base_functionality.patch

comment:22 Changed 10 years ago by Ben Hutz

Rebased for sage.5.10.beta1, but I'm having an issue with the doctest in

sage/doctest/source.py for the function _test_enough_doctests()

It is also getting:

"There are 4 tests in sage/schemes/projective/projective_point.py that are not being run"

As far as I can tell all tests in that file are being run. The documentation on _test_enough_doctests() says that it can sometimes miss count doctest for certain files.

Is this the case here?

This is fixed now: the Abelian variety point tests were not being run.

Last edited 10 years ago by Ben Hutz (previous) (diff)

comment:23 Changed 10 years ago by Ben Hutz

for the bot:

apply trac_14217_base_functionality.patch

comment:24 Changed 10 years ago by Frédéric Chapoton

apply trac_14217_base_functionality.patch

comment:25 Changed 10 years ago by Adam Towsley

Reviewers: atowsley
Status: needs_reviewpositive_review

Checked functionality and documentation.

The doc test for interupt.pyx times out intermittently, though this seems unrelated to the patch. (sage -t --long tests/interrupt.pyx # Time out)

comment:26 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_info

atowsley: write your real name as Reviewer.

bhutz: your patch needs a proper commit message.

comment:27 Changed 10 years ago by Adam Towsley

Reviewers: atowsleyAdam Towsley
Status: needs_infoneeds_review

comment:28 Changed 10 years ago by Adam Towsley

Status: needs_reviewpositive_review

comment:29 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work
Work issues: except

Never use except: without exception. Catch specific exceptions or, if you must, use

except StandardError:

comment:30 Changed 10 years ago by Ben Hutz

There were 4 instances and were changed as follows (and re-tested).

affine_morphism.homogenize(): I made this StandardError? since there are a variety of ways that trying the lcm() can fail and they all should enter the except block

affine_morphism.cycle_graph(): Catches TypeError? when the point is not on the scheme

projective_morphism.conjugate(): Catches the TypeError? when the map is no longer defined over the same ring

projective_morphism.cycle_graph(): Catches TypeError? when the point is not on the scheme

comment:31 Changed 10 years ago by Ben Hutz

Status: needs_workneeds_review

Changed 10 years ago by Ben Hutz

basic iteration functionality for affine and projective spaces

comment:32 Changed 10 years ago by Adam Towsley

Status: needs_reviewpositive_review

comment:33 Changed 10 years ago by Jeroen Demeyer

Work issues: except

comment:34 Changed 10 years ago by Ben Hutz

The last two times the patchbot has tried to apply this patch it has tried to apply it to 5.9. However, I had to rebase the 5.9 version for 5.10.beta1, so it doesn't apply on 5.9 and the patch is failing. Is there a way to tell the bot to apply it to the most recent development release and not the most recent stable release?

comment:35 Changed 10 years ago by Frédéric Chapoton

Well, there is nothing like *the* patchbot. Several people are running a patchbot on their machines, and they run it on the version of sage that they have. They certainly do their best to keep up to date, but one can never be sure. Anyway, your patch has now been tested on a 5.10.beta2

comment:36 in reply to:  34 Changed 10 years ago by Jeroen Demeyer

Replying to bhutz:

Is there a way to tell the bot to apply it to the most recent development release and not the most recent stable release?

No, but what you can do is to explicitly list the dependency in the Dependencies field on the ticket. That will help not only the patchbot, but also reviewers.

comment:37 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.10.beta3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.