relocate dynamical systems code from sage/schemes to sage/dynamics

[bhutz]

the majority of the code for working with arithmetical dynamical systems is in the respective morphism files in the sage/schemes folder. This is not very intuitive and as the code grows this is becoming increasing less ideal.

This ticket proposes creating a sage/dynamics/arithmetic_dynamics folder to house the dynamical systems code. This includes creating a class to distinguish between SchemeMorphism_polynomials which happen to be endomorphisms and those which should be treated dynamical systems. I consider this extra class as the negative effect of moving the code.

There are really two main reasons for this move.

• the dynamical systems functionality is extensive enough that it should be separated from the schemes functionality. There is already a sage/dynamics folders so it makes sense to put it there.

• creating a dynamical system under the new structure is much easier and intuitive for the user

CC: @sagetrac-xander-faber @tscrim

Component: dynamics

Keywords: sd87, days88, IMA coding sprints

Author: Ben Hutz, Xander Faber

Branch/Commit: 2eecc68

Reviewer: Travis Scrimshaw

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

[bhutz]

comment:1

I've acheived an initial move of the code that achieves 'all tests pass', so I figured that was a good place to commit and get another set of eyes on this.

There remains much clean-up to be done. A few things I haven't done yet

• do we need to specify domain=P to get point iteration to work? What works and what doesn't with the domains

• is .as_scheme_morphism and .as_dynamical_system a performance hit (and excess object creation in memory)? If so, what's a better way to deal with this (basically the parent of a dynamical system is the endomorphism ring of schemes which creates a schememorphism...)

• dynamicalsystems_generic defaults to affine which probably should be projective

• some more intelligence in the creation functions

---

New commits:

b4d0965

23497: relocate arithmetic dynamics code: initial version

[bhutz]

Branch: u/bhutz/arith_dyn

[bhutz]

Author: Ben Hutz

[bhutz]

Commit: b4d0965

[ff6c1784-dcc8-4050-b8c3-9ca94a3a005a]

Changed branch from u/bhutz/arith_dyn to u/xander.faber/arith_dyn

[ff6c1784-dcc8-4050-b8c3-9ca94a3a005a]

Changed commit from b4d0965 to 4950fcc

[ff6c1784-dcc8-4050-b8c3-9ca94a3a005a]

New commits:

0a40209	Fixed a docstring in morphism.py
f6827d0	AffineSpace now accepts a univariate polynomial ring and constructs A^1
586f17f	Improved dynamical system constructors in generic_ds module
4950fcc	Streamlined dynamical system class init's after pushing hard work to the constructors in generic_ds module

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4950fcc to b9327f8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a018703	Fixed a coercion bug in the affine morphism constructor
4650eb3	Improved consistency and type checking in class constructors
b9327f8	Fixed argument handling in special class inits for efficiency

[bhutz]

Changed branch from u/xander.faber/arith_dyn to u/bhutz/arith_dyn

[bhutz]

comment:6

I consider this ready for a review now.

When we are happy with this new functionality, then we'll need to merge in the following tickets which will conflict: #23234, #23333, #23334. So don't mark it positive-reivew even if it is ready.

---

New commits:

f9f291c	23497: reinstate doctests for deprecated functions
ae729ce	23497: tests, docs, and init updates to generic_ds.py
296dccd	23497: finish other dynamics files and all docs

[bhutz]

Changed commit from b9327f8 to 296dccd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2c604d0

Merge branch 8.1.beta0 into t/23497/arith_dyn

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 296dccd to 2c604d0

[ff6c1784-dcc8-4050-b8c3-9ca94a3a005a]

comment:8

Build succeeds, as do all doctests. I walked through the documentation and some examples of the new constructors ... looks pretty solid.

[fchapoton]

comment:9

The branch is red above, meaning that it does not apply on the latest beta (8.1.b1).

[bhutz]

comment:10

Yes, I'm aware. This probably also conflicts with a number of tickets currently positive-review. I plan to do all that merging today now that the functionality for this ticket is stable.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ba22abd

Merge branch 8.1.beta1 into t/23497/arith_dyn

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2c604d0 to ba22abd

[bhutz]

comment:12

All the tickets I was concerned about conflicting were already in 8.1.beta1, so this is ready now that I've resolved the conflict.

[fchapoton]

comment:13

does not apply

[tscrim]

comment:14

If you do one more rebase, I will quickly review it (so hopefully there will not be another conflict).

[tscrim]

Reviewer: Travis Scrimshaw

[bhutz]

comment:15

great, thanks. I was going to do this today as soon as I finish the rebase for a different ticket.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

79378c3

Merge branch 8.1.beta3 into t/23497/arith_dyn

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ba22abd to 79378c3

[bhutz]

Changed author from Ben Hutz to Ben Hutz, Xander Faber

[bhutz]

comment:17

merge conflict fixed

---

New commits:

79378c3

Merge branch 8.1.beta3 into t/23497/arith_dyn

[tscrim]

comment:18

Comments. I'm sorry if some of this is coming from old code already in Sage, but this might be a good time to clean it if it does.

Can you explain a little more about what is in the description about the extra class and why it is necessary? I don't really know this code/math so much to fully understand.

Indentation here:

.. [FH2015]     \J. A. de Faria, B. Hutz. Combinatorics of Cycle Lengths on
            Wehler K3 Surfaces over finite fields. New Zealand Journal
            of Mathematics 45 (2015), 19–31.

Do you want to worry about backwards compatibility with imports?

-class DynamicalSystem_affine_ring(SchemeMorphism_polynomial_affine_space,\
-                             DynamicalSystem_generic):
+class DynamicalSystem_affine_ring(SchemeMorphism_polynomial_affine_space,
+                                  DynamicalSystem_generic):

and similar; in particular, you do not need the \.

     INPUT:

-    - ``polys_or_rat_fncts`` -- a list of ``n`` polynomials or rational
-      functions, all of which should have the same parent.
+      functions, all of which should have the same parent
-
-    - ``domain`` -- an affine scheme embedded in `\mathbb{A}^n`.
+    - ``domain`` -- an affine scheme embedded in `\mathbb{A}^n`

     def __init__(self, polys_or_rat_fncts, domain):
         r"""
         The Python constructor.

         See :class:`DynamicalSystem_generic` for details.
-
-        INPUT:
-
-        - ``polys_or_rat_fncts`` -- a list of polynomials or rational functions.
-
-        - ``domain`` -- the domain of the map to be constructed.
-
-        OUTPUT:
-
-        - :class:`DynamicalSystem_affine`.

         INPUT:

-        - ``n`` -- a tuple of nonnegative integers. If ``n`` is an integer,
-          then the two values of the tuple are assumed to be the same.
+        - ``n`` -- a tuple of nonnegative integers; if ``n`` is an integer,
+          then the two values of the tuple are assumed to be the same

and similar changes.

+Return the ``n``-th iterate of self.
-Return the ``n``-th iterate of ``self``.

-       INPUT: ``n`` - a positive integer.
+       INPUT:
+
+       - ``n`` -- a positive integer

In, e.g., orbit, do not use self as a latex variable. Instead say something like, "let X be a dynamical system."

Returns -> Return and similar for one-line descriptions.

You are using a number of different formats for the OUTPUT:. I think you should at least be consistent, if not match the Sage coding conventions.

Remove is_DynamicalSystem because the isinstance already does what you want.

This is done in a number of other files.

from sage.categories.fields import Fields
_Fields = Fields()

Although I guess since module is lazily imported, it is not such a big deal. However, I would be happy to see not making this perma-instance issue worse, but not a strict requirement for a positive review.

-    Return a dynamical system on a projective scheme
+    Return a dynamical system on a projective scheme.

+    We can define dynamical systems on P^1 by giving a polynomial or
-    We can define dynamical systems on `P^1` by giving a polynomial or
     rational function::

Missing a doctest:

class DynamicalSystem_generic(SchemeMorphism_polynomial):
    def __init__(self, polys_or_rat_fncts, domain):

-        REFERENCES: [Hutz2015]_, [MoPa1994]_
+        REFERENCES:
+
+        - [Hutz2015]_
+        - [MoPa1994]_

             sage: dyn.parent()
             Symbolic Ring
-       """
+        """
         if self.domain().ngens() > 2:
             raise TypeError("does not make sense in dimension >1")

Error messages should start with a lower case and not end with a period/full stop.

-        - ``N`` -- iterate to use for approximation (optional - default: 3).
-
-        - ``prec`` -- real precision to use when computing root (optional - default: 53).
+        - ``N`` -- (default: 3) iterate to use for approximation
+        - ``prec`` -- (default: 53) real precision to use when computing root

(The extra whitespace can be added back in; that is your preference.)

             sage: RSA768 = 123018668453011775513049495838496272077285356959533479219732245215\
-                1726400507263657518745202199786469389956474942774063845925192557326303453731548\
-                2685079170261221429134616704292143116022212404792747377940806653514195974598569\
-                02143413
             ....: 1726400507263657518745202199786469389956474942774063845925192557326303453731548\
             ....: 2685079170261221429134616704292143116022212404792747377940806653514195974598569\
             ....: 02143413

Deindent:

        ALGORITHM:

            Uses a Nullstellensatz argument to compute the constant.
            For details: see [Hutz2015]_.

        ALGORITHM:
            Calls ``self.possible_periods()`` modulo all primes of good reduction in range
            ``prime_bound``. Returns the intersection of those lists.

In a number of those functions that you now are deprecating, they are not calling the new functions, correct? I think they should simply call those functions they say they are being deprecated in favor of. Some of them do this, but not all of them I believe.

There might be more comments later, but this is what I have for now on my first pass.

[tscrim]

Changed keywords from sd87 to sd87, days88, IMA coding sprints

[bhutz]

comment:19

responding to a couple of the questions:

• the only thing new here is the dynamicalsystem class and the structure needed to create that class. The functionality within the new class is all relocated code. All the deprecated functions in schemes should essentially just call the new functions. I'd recommend not trying to review every single line of the relocated code for the member functions, but am happy to do any clean-up needed as you come across it.

• There are really two main reasons for this move.

  • the dynamical systems functionality is extensive enough that it should be separated from the schemes functionality. There is already a sage/dynamics folders so it makes sense to put it there.
  • creating a dynamical system under the new structure is much easier and intuitive for the user

[bhutz]

Description changed:

--- 
+++ 
@@ -1,3 +1,11 @@
 the majority of the code for working with arithmetical dynamical systems is in the respective morphism files in the sage/schemes folder. This is not very intuitive and as the code grows this is becoming increasing less ideal.

 This ticket proposes creating a sage/dynamics/arithmetic_dynamics folder to house the dynamical systems code. This includes creating a class to distinguish between SchemeMorphism_polynomials which happen to be endomorphisms and those which should be treated dynamical systems. I consider this extra class as the negative effect of moving the code.
+
+
+There are really two main reasons for this move.
+
+- the dynamical systems functionality is extensive enough that it should be separated from the schemes functionality.  There is already a sage/dynamics folders so it makes sense to put it there.
+
+- creating a dynamical system under the new structure is much easier and intuitive for the user
+

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 79378c3 to 80ff2e6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

80ff2e6

23497: some fixes from review

[bhutz]

comment:21

I fixed most of those and have some discussion for the others.

• Note sure what you mean with the _Fields() import. I was told a couple years ago that it really should be done this way. Has that changed? What are the arguments for and against?

• the INPUT and OUTPUT consistently end in a '.' throughout the dynamical systems and schemes files, so I've left that consistent. However, the developer's guide does seem to give examples without ending in a period.

• For the INPUT you are suggesting the default be moved to the beginning on the description. Right now dynamical systems and schemes are consistently the other way. The conventions seem only to mention that the default value should be specified, not where.

• I'm not sure what you mean for the OUTPUT consistency. Yes, the OUTPUT description is formatted differently based on what makes the most sense for the OUTPUT of the functions, but they all match the conventions in the developer's guide.

• I disagree with removing is_DynamicalSystem. isinstance only works after you import the DynamicalSystem_generic class. With the distinction between endomorphisms and dynamical systems, it is important for the user to have an easy check for what they are working with.

• I couldn't find any instances of whether the error had capital or ending punctuation. Where did you see that?

So, the big open issue I see is whether to go through dynamical systems and schemes and change all the INPUT/OUTPUT formatting. What do you think?

---

New commits:

80ff2e6

23497: some fixes from review

[bhutz]

comment:22

to answer the other question. No, I'm not worried about backwards compatibility. I think keeping the old functionality working through deprecation is sufficient.

[tscrim]

comment:23

Replying to @bhutz:

• Note sure what you mean with the _Fields() import. I was told a couple years ago that it really should be done this way. Has that changed? What are the arguments for and against?

You create a _Fields object in the global namespace, not an import, so it essentially becomes permanent in memory (although it is not a true memory leak). That is the argument against it. The argument for is that you might be creating the Fields() category frequently, which can slow things down. However, this only occurs when creating objects, so I would rather just replace _Fields with Fields(). Actually, IIRC, you can just do containment checking by X in Fields (without creating/getting an instance object).

The comment about the lazy import is that this is not done on startup, but only when you create one of these dynamical system objects.

• the INPUT and OUTPUT consistently end in a '.' throughout the dynamical systems and schemes files, so I've left that consistent. However, the developer's guide does seem to give examples without ending in a period.

The convention is without periods and this is what most of Sage does.

• For the INPUT you are suggesting the default be moved to the beginning on the description. Right now dynamical systems and schemes are consistently the other way. The conventions seem only to mention that the default value should be specified, not where.

I believe what most of Sage does is put it first, and this is what I do with all of my code that I write and request when I review. However I don't strongly care.

• I'm not sure what you mean for the OUTPUT consistency. Yes, the OUTPUT description is formatted differently based on what makes the most sense for the OUTPUT of the functions, but they all match the conventions in the developer's guide.

Here are some of the styles used:

OUTPUT: some output

OUTPUT: some output.

OUTPUT:

- A full sentence.

OUTPUT:

A full sentence.

OUTPUT:

- a short description

• I disagree with removing is_DynamicalSystem. isinstance only works after you import the DynamicalSystem_generic class. With the distinction between endomorphisms and dynamical systems, it is important for the user to have an easy check for what they are working with.

Almost none of the is_* methods are imported into the global namespace. In fact, there are 2 (is_field is a little special). So is_DynamicalSystem should not be imported, and hence someone will have to import something anyways. Moreover, if someone wants to know the class that they are working with, then they really should be checking the appropriate class if they don't want to rely on ducktyping or trusting the user.

• I couldn't find any instances of whether the error had capital or ending punctuation. Where did you see that?

Hmmm...I might have mixed up tickets or misremembered the Symbolic Ring errors.

So, the big open issue I see is whether to go through dynamical systems and schemes and change all the INPUT/OUTPUT formatting. What do you think?

I wasn't sure how much you were actually adding versus copying over. Thank you for clarifying that. I am okay with letting it pass because it is how it was, but it would be nice to start converting it to the new version. I can do this with a reviewer change too.

[bhutz]

comment:24

I'll remove the global _Fields().

I'm still not 100% convinced that is_DynamicalSystem is not needed. Here is my thought process in some more detail: One of the big issues we struggled with on this ticket is how to differentiate between an endomorphism of a space and a dynamical system on a space without creating a category of schemes whose arrows are dynamical systems instead of scheme morphisms. Let's say

f = End(P)

g = DynamicalSystem(...) # on P

Then f.parent() == g.parent() is true. So without is_DynSys the only way to tell the difference is to check the class or see what member functions are available. There are simple conversion functions; e.g. f.as_dynamicalsystem(). Looking at the global is* namespace, there are 21 functions currently. (The two is_ProductProjectiveSpaces is_ProjectiveSpace seem out of place and perhaps should be removed from the global name space as part of the schemes clean-up.) To me, it is a question of will a standard user need this function or not. A power user writing their own code should be able to do imports, but a standard user should not have to import something they need. I am having some trouble coming up with a realistic scenario where a standard user absolutely needs is_DynSys. Let me think about it some more.

For the INPUT/OUTPUT formatting: Updating the files in sage/dynamical systems/arithmetic dynamics/ is certainly a reasonable request as they are created here and I can do that (probably later today). I think I'd prefer updating the sage/schemes/ files on a different ticket.

[tscrim]

comment:25

Replying to @bhutz:

I'll remove the global _Fields().

If this slows things down, feel free to leave it in. Like I said, it's not a big issue because this module lazily imported.

I'm still not 100% convinced that is_DynamicalSystem is not needed. Here is my thought process in some more detail: One of the big issues we struggled with on this ticket is how to differentiate between an endomorphism of a space and a dynamical system on a space without creating a category of schemes whose arrows are dynamical systems instead of scheme morphisms. Let's say

f = End(P)

g = DynamicalSystem(...) # on P

Then f.parent() == g.parent() is true. So without is_DynSys the only way to tell the difference is to check the class or see what member functions are available. There are simple conversion functions; e.g. f.as_dynamicalsystem(). Looking at the global is* namespace, there are 21 functions currently. (The two is_ProductProjectiveSpaces is_ProjectiveSpace seem out of place and perhaps should be removed from the global name space as part of the schemes clean-up.) To me, it is a question of will a standard user need this function or not. A power user writing their own code should be able to do imports, but a standard user should not have to import something they need. I am having some trouble coming up with a realistic scenario where a standard user absolutely needs is_DynSys. Let me think about it some more.

I think most people will first try:

if isinstance(X, DynamicalSystem):
    pass

which, of course, will be False because DynamicalSystem is a function. What I usually do for constructors that mimic ABCs is to actually fuse the two and use __classcall__. I really like this idiom as it better associates the (abstract) class and the constructor. So I would rename DynamicalSystem_generic to DynamicalSystem, which then has a __classcall_private__ (which you would also need to set the metaclass to be ClasscallMetaclass AFAICS) that constructs the appropriate subclass.

However, this problem is no different than other homsets that have different elements/morphisms that use different subclasses. I doubt a standard user will be writing code that mixes the two or needs to differentiate the two classes based upon what you've told me as they would be working solely in the dynamical system perspective if that is what they want (especially since it is a subclass).

For the INPUT/OUTPUT formatting: Updating the files in sage/dynamical systems/arithmetic dynamics/ is certainly a reasonable request as they are created here and I can do that (probably later today). I think I'd prefer updating the sage/schemes/ files on a different ticket.

Sounds good to me. Let me know if you want me to do it as well.

[bhutz]

comment:26

I've done the INPUT/OUTPUT formatting, but I'm having trouble with the classcall_private. I was able to get it to work for dynamicalsystems_generic since the classcall function is basically just deciding if it is affine or projective and then calling the appropriate class constructor.

I was trying to also do DS_affine and DS_projective the same way. However, I can't seem to get from the _classcall_private_ function over to the _init_ function. Some of the examples I found in Sage seem to have a secondary class so that classcall_private calls the constructor of the subclass. I guess I could do the same here, but is this really how it should work? I'd end up with

dynamcalsystem_affine (with _classcall_private_) which would then call the constructor for one of the subclasses DS_affine_ring, DS_affine_field, or DS_affine_finite_field. In other words, basically a dummy higher class to have _classcall_private_ which calls the actual class constructors. It seems like I'm not understanding how this should all work.

Do you know how _classcall_private_ should interact with init?

[tscrim]

comment:27

So __clascall_private__ takes input and then it will be passed up with a super(Foo, cls).__classcall__(cls, args) call (as in other examples, e.g., Partition). This then calls the __init__ with these methods. (Just incase you are unaware, this needs to be an @staticmethod.) However, if you want to delegate to, e.g., a subclass (but it really can be anything), you do return Foo(bar).

Maybe a more standard example that just standardizes input would be algebras/yokonuma_hecke_algebra.py (note that the metaclass is set because it is a subclass of UniqueRepresentation).

[tscrim]

comment:28

I can do this tomorrow morning when I wake up if you want.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 80ff2e6 to cc50108

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

fdf7265	23497: doc formatting INPUT/OUTPUT
cc50108	23497: use __classcall_private__

[bhutz]

comment:30

I tried that first as that is what most instances are doing, but I get an AttributeError that super doesn't have a classcall. If you could take a look that would be appreciated.

I've pushed the INPUT/OUTPUT clean-up as well as setting up the changes needed to use _classcallprivate. It currently has the super().classcall() where I think it should go. If you can get that initialization to work and push that back up, I'll go through and fix any remaining issues since I couldn't really test as it is now.

[tscrim]

comment:31

Okay, I've fix up the classcall. It didn't have a superclass that actually implemented the __classcall__, so you have to explicitly have to use typecall. I forgot about that, sorry. I also made it through the doc and code and did a bunch of cleanup and more micro-optimizations I know.

If my changes look good, then positive review.

---

New commits:

4bbdcde	Fixing things with __classcall_private__.
7408d79	Cleaning up the doc and improving the code.

[tscrim]

Changed commit from cc50108 to 7408d79

[tscrim]

Changed branch from u/bhutz/arith_dyn to u/tscrim/arith_dyn-23497

[bhutz]

Changed branch from u/tscrim/arith_dyn-23497 to u/bhutz/arith_dyn-23497

[bhutz]

Changed commit from 7408d79 to d00cea2