Opened 5 years ago

Closed 5 years ago

#14217 closed enhancement (fixed)

basic iteration functionality for affine and projective morphisms

Reported by: bhutz Owned by: bhutz
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:

Description (last modified by bhutz)

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 bhutz 5 years ago.
basic iteration functionality for affine and projective spaces

Download all attachments as: .zip

Change History (38)

comment:1 Changed 5 years ago by mmanes

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 5 years ago by chapoton

  • Dependencies changed from 13130 to #13130
  • Description modified (diff)

comment:3 Changed 5 years ago by chapoton

  • You should write
    INPUT:
    

and

OUTPUT:

with only a single :

  • You should write
    EXAMPLES::
    

using capital letters.

comment:4 Changed 5 years ago by bhutz

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 5 years ago by bhutz

  • Description modified (diff)

comment:6 Changed 5 years ago by chapoton

There are now several "OTUPUT:: "

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

comment:7 Changed 5 years ago by 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 5 years ago by 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 5 years ago by bhutz

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 5 years ago by bhutz

  • Description modified (diff)
  • Status changed from new to needs_review

comment:11 Changed 5 years ago by chapoton

for the bot:

apply trac_14217_base_functionality.patch

comment:12 Changed 5 years ago by 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 5 years ago by atowsley

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.

Last edited 5 years ago by atowsley (previous) (diff)

comment:14 Changed 5 years ago by bhutz

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 5 years ago by 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 5 years ago by bhutz

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 5 years ago by 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 5 years ago by chapoton

This needs to be rebased, see the bot report

comment:19 Changed 5 years ago by bhutz

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

comment:20 Changed 5 years ago by bhutz

for the bot:

apply trac_14217_base_functionality.patch

comment:21 Changed 5 years ago by bhutz

for the bot:

apply trac_14217_base_functionality.patch

comment:22 Changed 5 years ago by bhutz

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 5 years ago by bhutz (previous) (diff)

comment:23 Changed 5 years ago by bhutz

for the bot:

apply trac_14217_base_functionality.patch

comment:24 Changed 5 years ago by chapoton

apply trac_14217_base_functionality.patch

comment:25 Changed 5 years ago by atowsley

  • Reviewers set to atowsley
  • Status changed from needs_review to positive_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 5 years ago by jdemeyer

  • Status changed from positive_review to needs_info

atowsley: write your real name as Reviewer.

bhutz: your patch needs a proper commit message.

comment:27 Changed 5 years ago by atowsley

  • Reviewers changed from atowsley to Adam Towsley
  • Status changed from needs_info to needs_review

comment:28 Changed 5 years ago by atowsley

  • Status changed from needs_review to positive_review

comment:29 Changed 5 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to except

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

except StandardError:

comment:30 Changed 5 years ago by bhutz

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 5 years ago by bhutz

  • Status changed from needs_work to needs_review

Changed 5 years ago by bhutz

basic iteration functionality for affine and projective spaces

comment:32 Changed 5 years ago by atowsley

  • Status changed from needs_review to positive_review

comment:33 Changed 5 years ago by jdemeyer

  • Work issues except deleted

comment:34 follow-up: Changed 5 years ago by bhutz

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 5 years ago by 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 5 years ago by jdemeyer

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 5 years ago by jdemeyer

  • Merged in set to sage-5.10.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.