A framework for finite dynamics (permutations of finite sets)

[darijgr]

Create a class that takes a finite set and an automorphism (= permutation) as inputs, and computes the orbit sizes and verifies homomesy with respect to any given statistic. Something like that seems to have been envisioned in ticket #18062, but to our knowledge never implemented.

Eventually, we will also want it to check cyclic sieving with respect to any given polynomial.

CC: @sagetrac-troby @sagetrac-sage-combinat

Component: dynamics

Keywords: IMA coding sprint, homomesy, cyclic sieving, permutations, fpsac2019

Author: Darij Grinberg, Tom Roby

Branch/Commit: 3617085

Reviewer: Travis Scrimshaw

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

[darijgr]

comment:2

I realize some of this is done in src/sage/combinat/cyclic_sieving_phenomenon.py. Of course, we'd want more: homomesy checking; finding the orbit of a single point rather than all the orbits.

What is the general opinion about this module? Should we just add to it, or should it be completely refactored?

[tscrim]

comment:3

My approach would be to refactor.

[darijgr]

comment:4

I assume it would be

class DiscreteDynamicalSystem(...):

Do you have any suggestions as to what class should we copypaste to get a reasonable format? What kind of methods would it need? __init__, _repr_, etc.?

[tscrim]

comment:5

You may just want to start crafting your own class without using another as a template. You should do the basic methods of __init__, _repr_, and go from there. I would think about how you want to use an instance of DiscreteDynamicalSystem and work from there. In other words, do test-based programming (write the tests you want it to pass and then fill in the code until it does).

[darijgr]

comment:6

Some work done. The class is functional for what we need -- homomesy checking for dynamical systems with invertible evolution --, but its doc is very bare-bones and it's lacking a lot of bells and whistles. Also, the three examples are "def"-functions rather than subclasses of their own; thus, their "repr" is crap.

---

New commits:

f5e333f

starting a class for finite dynamical systems

[darijgr]

Commit: f5e333f

[darijgr]

Author: Darij Grinberg, Tom Roby

[darijgr]

Branch: public/ticket/24128

[tscrim]

comment:7

I know I had mentioned object to you, but SageObject is actually the better thing to inherit from. Mea culpa. Then you can use _repr_ (and _latex_, _ascii_art_, and _unicode_art_).

Note that if you do self._X = tuple(X), then you force X to be finite.

I would also consider not putting the evolution function in the repr. Things like that can be more trouble than its worth IMO.

I noticed on a quick look: you have FDDS in the DiscreteDynamicalSystem doc.

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

Changed commit from f5e333f to 6389054

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

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

6389054

thanks Travis!

[fchapoton]

comment:9

Missing doctests in combinat/finite_dynamical_system.py: 7 / 15 = 46%

[darijgr]

comment:10

Thank you, but this is nowhere near completion. I'll work on it whenever I have time (which is probably not too often this semester...).

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

Changed commit from 6389054 to eaedd74

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

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

864d7f9	Merge branch 'public/ticket/24128' of trac.sagemath.org:sage into dyn
eaedd74	organize examples in a class discrete_dynamical_systems(); add Striker sweep example

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

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

70b8153	add a few examples
381ddee	intermediate version
9d1853b	refactor hierarchy and add new functionality

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

Changed commit from eaedd74 to 9d1853b

[darijgr]

comment:13

This now has sufficient functionality for anything I personally want to do. Not sure if the class hierarchy is up to Sage standards, though:

- :class:`DiscreteDynamicalSystem`: general discrete dynamical
  system, as above.
  Inherit from this class if the ground set of your DDS is
  infinite or large enough that you want to avoid it getting
  stored as a list.

- :class:`FiniteDynamicalSystem`: finite discrete dynamical
  system.

- :class:`InvertibleDiscreteDynamicalSystem`: invertible
  discrete dynamical system.
  This implements an ``inverse_evolution`` method for `\phi^{-1}`
  (the default implementation simply applies `\phi` over and
  over until the original value is revisited; the last value
  before that is then taken to be the result).

- :class:`InvertibleFiniteDynamicalSystem`: invertible
  finite discrete dynamical system.

(This would perhaps be easier with the category framework, but I don't know it well enough.)

There are a few examples, all of which are implemented as staticmethods on a class class discrete_dynamical_systems().

[darijgr]

Changed keywords from IMA coding sprint, homomesy, cyclic sieving, permutations to IMA coding sprint, homomesy, cyclic sieving, permutations, sage-combinat

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

Changed commit from 9d1853b to 4611d5c

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

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

4611d5c

doc oops

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

Changed commit from 4611d5c to 2782b78

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

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

2782b78

add missing doctests

[darijgr]

comment:16

Little questions:

• Implement _repr_ or __repr__?

• Should the repr function output the evolution function, even when it is going to be a faceless lambda most of the time?

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

Changed commit from 2782b78 to fa612bf

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

fa612bf

add missing doctests

[tscrim]

comment:18

I am not sure if we should get the category framework involved or not. At present, there does not seem to be any benefit to using that machinery. You don't have any parents or elements (granted, your systems could be considered as façade parents). So this seems fine for now. We can always refactor it later as things evolve (your welcome Tom).

I would not have a class discrete_dynamical_systems with @staticmethods. Instead, I would implement a catalog module and have functions there. You then import the catalog file in the global namespace as discrete_dynamical_systems. I would also make them faux-classes in terms of naming (i.e., using CamelCase).

Some things to note:

• You should use _repr_ so you can override this with rename and you are inheriting from SageObject.
• I probably would not add the rule to the output because it will not be so useful.
• .. TODO :: -> .. TODO:: and what follows should be indented.
• You should call the method evolve instead of evolution because you evolve the system, you don't evolution the system. Edit: I misread the code
• I have been doing similar things on #25796 and #25797 and sage/dynamics/cellular_automata/soliton.py. It probably is coming to the point where we should make things have a fairly consistent API and see what we can learn from both.

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

Changed commit from fa612bf to afc1173

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

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

afc1173

documentation and repr

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

Changed commit from afc1173 to 940cfaa

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

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

940cfaa

finding cycles and checking homomesies for non-invertible DDSes

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

Changed commit from 940cfaa to 692bbf8

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

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

692bbf8

improve doc and speed up orbits method

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3fe382f

improve doc and speed up orbits method

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

Changed commit from 692bbf8 to 3fe382f

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

Changed commit from 3fe382f to e5fd928

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e5fd928

improve doc and speed up orbits method

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4c9252b

improve doc and speed up orbits method

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

Changed commit from e5fd928 to 4c9252b

[darijgr]

comment:25

This is now needs_review.

For now, the functionality is fairly shallow (the most complicated algorithm is finding all cycles of a finite DDS); the main use of the module is convenience and examples. There are lots of todos in the doc, some of which I may want to deal with one day.

The file is called sage/combinat/finite_dynamical_system.py because it is mainly meant for use by combinatorialists and because most of the functionality concerns finite DDSes, but I am open to renaming and/or moving it.

[tscrim]

comment:26

I think this should go in the sage/dynamics folder and then be listed in the Discrete dynamics header in the corresponding index.rst file.

I am not sure I agree with putting the important doc at the module level. This makes it really difficult for people using ? to see it. Moreover, if the module level is really short, people will quickly find the class to see the doc when looking at it from the html.

You should put the INPUT: block in the class level doc because it will only get seen by people looking at the source code in the __init__. Same for the EXAMPLES::. A good test to do in __init__ is a TestSuite(Foo).run().

Why do you not automatically force X to be a tuple? Concerned if X is a parent object? Why not test if isinstance(X, Parent): and otherwise (if not also None) force X to be a tuple. I don't see the reason why it should be allowed to stay mutable.

This would be cleaner and faster if you pull out the self.evolution() and self.inverse_evolution() as variables:

            if self.evolution()(self.inverse_evolution()(y)) != y:
                return False
            if self.inverse_evolution()(self.evolution()(y)) != y:

If you change inverse_evolution_default to _inverse, then you only have to do

-        if inverse is None:
-            self._inverse = self.inverse_evolution_default
-        else:
+        if inverse is not None:
            self._inverse = inverse

Again, I think you should have a catalog (module) instead of a class with a bunch of @staticmethods.

[tscrim]

Reviewer: Travis Scrimshaw

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

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

75d2cc3	Merge branch 'public/ticket/24128' of trac.sagemath.org:sage into dyn
7b11c0c	move from sage.combinat to sage.dynamics

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

Changed commit from 4c9252b to 7b11c0c

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

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

28b5a1f

Adding factory `__classcall__` to DiscreteDynamicalSystem.

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

Changed commit from 7b11c0c to 28b5a1f

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

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

5f7d0c4	Merge branch 'public/ticket/24128' of git://trac.sagemath.org/sage into dyn
6434bbf	doc -> class

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

Changed commit from 28b5a1f to 6434bbf

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b06821e

doc -> class

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

Changed commit from 6434bbf to b06821e