Discrete dynamical systems#

A discrete dynamical system (henceforth DDS) is a pair \((X, \phi)\) of a set \(X\) and a map \(\phi : X \to X\). (This is one of several things known as a “discrete dynamical system” in mathematics.)

This file implements the following classes for discrete dynamical systems:

  • 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. See the doc of this class for further details.

  • FiniteDynamicalSystem: finite discrete dynamical system. This can be instantiated by calling DiscreteDynamicalSystem with the parameter is_finite set to True.

  • 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). This can be instantiated by calling DiscreteDynamicalSystem with the parameter inverse provided.

  • InvertibleFiniteDynamicalSystem: invertible finite discrete dynamical system. This can be instantiated by calling DiscreteDynamicalSystem with the parameter is_finite set to True and the parameter inverse provided.

Todo

  • Implement some more functionality for homomesy and invariance testing: Checking invariance on a sublist; computing the first \(k\) entries of an orbit (useful when orbits can be too large); orbits_iterator (for when there are too many orbits to list); etc.

  • Further examples for non-auto functionality: e.g., infection on a chessboard; Conway’s game of life.

  • Subclasses for DDSes whose ground set is an enumerated set. Should we have those?

  • Implement caching for orbits (can be useful: some DDSes have a complicated evolution that shouldn’t be recomputed every time). Does this require a whole new class?

  • Further functionality for non-invertible DDSes: is_recurrent, recurrent_entries, idempotent_power, etc.

  • Wrap (some of) the cyclic_sieving_phenomenon.py methods (sage.combinat.cyclic_sieving_phenomenon).

  • Interact with sage.dynamics. This requires someone who knows the latter part of the Sage library well.

class sage.dynamics.finite_dynamical_system.DiscreteDynamicalSystem(X, phi, cache_orbits=False, create_tuple=False)[source]#

Bases: SageObject

A discrete dynamical system.

A discrete dynamical system (henceforth DDS) is a pair \((X, \phi)\) of a set \(X\) and a map \(\phi : X \to X\). The set \(X\) is called the ground set of the DDS; the map \(\phi\) is called the evolution of the DDS; the inverse map \(\phi^{-1}\) (when it exists) is called the inverse evolution of the DDS.

The DDS is called finite if \(X\) is finite. The DDS is called invertible if the map \(\phi\) is invertible.

Given a DDS \((X, \phi)\), we can study

  • its orbits (i.e., the lists \((s, \phi(s), \phi^2(s), \phi^3(s), \ldots)\) for \(s \in X\)),

  • its invariants (i.e., maps \(f : X \to Y\) satisfying \(f \circ \phi = f\)),

  • its cycles (i.e., lists \((u_1, u_2, \ldots, u_k)\) of elements of \(X\) such that \(\phi(u_i) = u_{i+1}\) for each \(i \leq k\), where we set \(u_{k+1} = u_1\)),

  • its homomesies (i.e., maps \(h : X \to A\) to a \(\QQ\)-vector space \(A\) such that the average of the values of \(h\) on each cycle is the same),

and various other features. (Some of these require \(X\) to be finite or at least to have finite orbits.)

INPUT:

  • X – set, list, tuple, or another iterable, or None (default: None); the ground set for the DDS. This can be None (in which case Sage will not know the ground set, but can still apply evolution to any elements that are provided to it). Make sure to set the create_tuple argument to True if the X you provide is an iterator or a list, as otherwise your X would be exposed (and thus subject to mutation or exhaustion).

  • phi – function, or callable that acts like a function; the evolution of the DDS.

  • cache_orbits – boolean (default: False); whether or not the orbits should be cached once they are computed. This currently does nothing, as we are not caching orbits yet.

  • create_tuple – boolean (default: False); whether or not the input X should be translated into a tuple. Set this to True to prevent mutation if X is a list, and to prevent exhaustion if X is an iterator.

  • inverse – function, or callable that acts like a function, or boolean or None (default: None); the inverse evolution of the DDS, if the DDS is invertible. Set this to None or False if the DDS is not invertible (or you don’t want Sage to treat it as such). Alternatively, by setting this argument to True, you can signal that the DDS is invertible without providing the inverse evolution. (In this case, Sage will compute the inverse, assuming the orbits to be finite.)

  • is_finite – boolean or None (default: None); whether the DDS is finite. The default option None leaves this to Sage to decide. Only set this to True if you provide the ground set X.

EXAMPLES:

The following discrete dynamical system is neither finite nor invertible:

sage: D = DiscreteDynamicalSystem(NN, lambda x: x + 2)
sage: D.ground_set()
Non negative integer semiring
sage: D.evolution()(5)
7
sage: D.evolution_power(7)(5)
19
sage: D.evolution_power(0)(5)
5

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(NN, lambda x: x + Integer(2))
>>> D.ground_set()
Non negative integer semiring
>>> D.evolution()(Integer(5))
7
>>> D.evolution_power(Integer(7))(Integer(5))
19
>>> D.evolution_power(Integer(0))(Integer(5))
5

The necessity of create_tuple=True:

sage: X = [0, 1, 2, 3, 4]
sage: D_wrong = DiscreteDynamicalSystem(X, lambda x: (x**3) % 5)
sage: D_right = DiscreteDynamicalSystem(X, lambda x: (x**3) % 5, create_tuple=True)
sage: X[4] = 666 # evil
sage: D_wrong.ground_set()
[0, 1, 2, 3, 666]
sage: D_right.ground_set()
(0, 1, 2, 3, 4)

>>> from sage.all import *
>>> X = [Integer(0), Integer(1), Integer(2), Integer(3), Integer(4)]
>>> D_wrong = DiscreteDynamicalSystem(X, lambda x: (x**Integer(3)) % Integer(5))
>>> D_right = DiscreteDynamicalSystem(X, lambda x: (x**Integer(3)) % Integer(5), create_tuple=True)
>>> X[Integer(4)] = Integer(666) # evil
>>> D_wrong.ground_set()
[0, 1, 2, 3, 666]
>>> D_right.ground_set()
(0, 1, 2, 3, 4)

Here is an invertible (but infinite) discrete dynamical system whose orbits are finite:

sage: D = DiscreteDynamicalSystem(NN, lambda x: (x + 2 if x % 6 < 4 else x - 4), inverse=True)
sage: D.ground_set()
Non negative integer semiring
sage: D.evolution()(5)
1
sage: D.evolution()(1)
3
sage: D.evolution()(3)
5
sage: D.evolution_power(2)(5)
3
sage: D.evolution_power(3)(5)
5
sage: D.evolution_power(-2)(5)
1
sage: D.inverse_evolution()(4)
2
sage: D.orbit(3)
[3, 5, 1]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(NN, lambda x: (x + Integer(2) if x % Integer(6) < Integer(4) else x - Integer(4)), inverse=True)
>>> D.ground_set()
Non negative integer semiring
>>> D.evolution()(Integer(5))
1
>>> D.evolution()(Integer(1))
3
>>> D.evolution()(Integer(3))
5
>>> D.evolution_power(Integer(2))(Integer(5))
3
>>> D.evolution_power(Integer(3))(Integer(5))
5
>>> D.evolution_power(-Integer(2))(Integer(5))
1
>>> D.inverse_evolution()(Integer(4))
2
>>> D.orbit(Integer(3))
[3, 5, 1]

Setting the inverse parameter to None or False would give the same system without the functionality that relies on invertibility:

sage: D = DiscreteDynamicalSystem(NN, lambda x: (x + 2 if x % 6 < 4 else x - 4), inverse=False)
sage: D.ground_set()
Non negative integer semiring
sage: D.evolution()(5)
1
sage: D.inverse_evolution()(4)
Traceback (most recent call last):
...
AttributeError: 'DiscreteDynamicalSystem' object has no attribute 'inverse_evolution'...
sage: D.orbit(3)
[3, 5, 1]

sage: D = DiscreteDynamicalSystem(NN, lambda x: (x + 2 if x % 6 < 4 else x - 4), inverse=None)
sage: D.ground_set()
Non negative integer semiring
sage: D.evolution()(5)
1
sage: D.inverse_evolution()(4)
Traceback (most recent call last):
...
AttributeError: 'DiscreteDynamicalSystem' object has no attribute 'inverse_evolution'...
sage: D.orbit(3)
[3, 5, 1]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(NN, lambda x: (x + Integer(2) if x % Integer(6) < Integer(4) else x - Integer(4)), inverse=False)
>>> D.ground_set()
Non negative integer semiring
>>> D.evolution()(Integer(5))
1
>>> D.inverse_evolution()(Integer(4))
Traceback (most recent call last):
...
AttributeError: 'DiscreteDynamicalSystem' object has no attribute 'inverse_evolution'...
>>> D.orbit(Integer(3))
[3, 5, 1]

>>> D = DiscreteDynamicalSystem(NN, lambda x: (x + Integer(2) if x % Integer(6) < Integer(4) else x - Integer(4)), inverse=None)
>>> D.ground_set()
Non negative integer semiring
>>> D.evolution()(Integer(5))
1
>>> D.inverse_evolution()(Integer(4))
Traceback (most recent call last):
...
AttributeError: 'DiscreteDynamicalSystem' object has no attribute 'inverse_evolution'...
>>> D.orbit(Integer(3))
[3, 5, 1]

Next, let us try out a finite non-invertible DDS:

sage: D = DiscreteDynamicalSystem(tuple(range(13)), lambda x: (x**2) % 13)
sage: D.ground_set()
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
sage: D.evolution()(4)
3
sage: D.orbit(4)
[4, 3, 9]
sage: D.orbit(1)
[1]
sage: D.orbit(3)
[3, 9]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(13))), lambda x: (x**Integer(2)) % Integer(13))
>>> D.ground_set()
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
>>> D.evolution()(Integer(4))
3
>>> D.orbit(Integer(4))
[4, 3, 9]
>>> D.orbit(Integer(1))
[1]
>>> D.orbit(Integer(3))
[3, 9]

Note that the finiteness is automatically being inferred here, since the (finite) tuple tuple(range(13)) has been provided as the ground set.

Finally, here is a finite invertible DDS:

sage: X = cartesian_product([[0, 1]]*8)
sage: Y = [s for s in X if sum(s) == 4]
sage: rot = lambda s : s[1:] + (s[0],)
sage: D = DiscreteDynamicalSystem(Y, rot, inverse=True)
sage: D.evolution()((0, 1, 1, 0, 1, 0, 0, 1))
(1, 1, 0, 1, 0, 0, 1, 0)
sage: D.inverse_evolution()((0, 1, 1, 0, 1, 0, 0, 1))
(1, 0, 1, 1, 0, 1, 0, 0)
sage: sorted(D.orbit_lengths())
[2, 4, 8, 8, 8, 8, 8, 8, 8, 8]

>>> from sage.all import *
>>> X = cartesian_product([[Integer(0), Integer(1)]]*Integer(8))
>>> Y = [s for s in X if sum(s) == Integer(4)]
>>> rot = lambda s : s[Integer(1):] + (s[Integer(0)],)
>>> D = DiscreteDynamicalSystem(Y, rot, inverse=True)
>>> D.evolution()((Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 1, 0, 1, 0, 0, 1, 0)
>>> D.inverse_evolution()((Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 0, 1, 1, 0, 1, 0, 0)
>>> sorted(D.orbit_lengths())
[2, 4, 8, 8, 8, 8, 8, 8, 8, 8]

We could have just as well provided its inverse explicitly:

sage: rot7 = lambda s: (s[-1],) + s[:-1]
sage: D = DiscreteDynamicalSystem(Y, rot, inverse=rot7)
sage: D.evolution()((0, 1, 1, 0, 1, 0, 0, 1))
(1, 1, 0, 1, 0, 0, 1, 0)
sage: D.inverse_evolution()((0, 1, 1, 0, 1, 0, 0, 1))
(1, 0, 1, 1, 0, 1, 0, 0)

>>> from sage.all import *
>>> rot7 = lambda s: (s[-Integer(1)],) + s[:-Integer(1)]
>>> D = DiscreteDynamicalSystem(Y, rot, inverse=rot7)
>>> D.evolution()((Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 1, 0, 1, 0, 0, 1, 0)
>>> D.inverse_evolution()((Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 0, 1, 1, 0, 1, 0, 0)
evolution()[source]#

Return the evolution of self.

EXAMPLES:

sage: D = DiscreteDynamicalSystem([1, 3, 4], lambda x: (3 if x == 4 else 1), create_tuple=True)
sage: ev = D.evolution()
sage: ev(1)
1
sage: ev(4)
3

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem([Integer(1), Integer(3), Integer(4)], lambda x: (Integer(3) if x == Integer(4) else Integer(1)), create_tuple=True)
>>> ev = D.evolution()
>>> ev(Integer(1))
1
>>> ev(Integer(4))
3
evolution_power(n)[source]#

Return the \(n\)-th power (with respect to composition) of the evolution of self.

This requires \(n\) to be a nonnegative integer.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(range(10), lambda x: (x + 3) % 10, create_tuple=True)
sage: ev3 = D.evolution_power(3)
sage: ev3(1)
0
sage: ev3(2)
1
sage: ev0 = D.evolution_power(0)
sage: ev0(1)
1
sage: ev0(2)
2
sage: D.evolution_power(-1)
Traceback (most recent call last):
...
ValueError: the n-th power of evolution is only defined for nonnegative integers n

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(range(Integer(10)), lambda x: (x + Integer(3)) % Integer(10), create_tuple=True)
>>> ev3 = D.evolution_power(Integer(3))
>>> ev3(Integer(1))
0
>>> ev3(Integer(2))
1
>>> ev0 = D.evolution_power(Integer(0))
>>> ev0(Integer(1))
1
>>> ev0(Integer(2))
2
>>> D.evolution_power(-Integer(1))
Traceback (most recent call last):
...
ValueError: the n-th power of evolution is only defined for nonnegative integers n
ground_set()[source]#

Return the ground set of self.

This will return None if no ground set was provided in the construction of self.

Warning

Unless self has been constructed with the create_tuple parameter set to True, this method will return whatever ground set was provided to the constructor. In particular, if a list was provided, then this precise list will be returned; mutating this list will then corrupt self.

EXAMPLES:

sage: D = DiscreteDynamicalSystem([1, 3, 4], lambda x: (3 if x == 4 else 1), create_tuple=True)
sage: D.ground_set()
(1, 3, 4)

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem([Integer(1), Integer(3), Integer(4)], lambda x: (Integer(3) if x == Integer(4) else Integer(1)), create_tuple=True)
>>> D.ground_set()
(1, 3, 4)
is_homomesic(h, average=None, find_average=False, elements=None)[source]#

Check if h (a map from the ground set of self to a \(\QQ\)-vector space) is homomesic with respect to self.

If the optional argument average is provided, then this also checks that the averages are equal to average.

If the optional argument find_average is set to True, then this method returns the average of h in case h is homomesic (instead of returning True).

If the optional argument elements (an iterable of elements of the ground set of self) is provided, then this method only checks homomesy for the cycles in the orbits of the elements given in the list elements. Note that elements must be provided if the ground set of self is infinite (or cannot be iterated through for any other reason), since there is no way to check all the cycles in this case.

This method will fail to terminate if any element of elements has an infinite orbit.

Let us recall the definition of homomesy: Let \((X, \phi)\) be a DDS. A cycle of \((X, \phi)\) is a finite list \(u = (u_1, u_2, \ldots, u_k)\) of elements of \(X\) such that \(\phi(u_i) = u_{i+1}\) for each \(i \leq k\), where we set \(u_{k+1} = u_1\). Note that any element of \(X\) whose orbit is finite has a cycle in its orbit. Now, let \(h\) be a map from \(X\) to a \(\QQ\)-vector space \(A\). If \(u = (u_1, u_2, \ldots, u_k)\) is any cycle of \((X, \phi)\), then the average of \(h\) on this cycle is defined to be the element \((h(u_1) + h(u_2) + \cdots + h(u_k)) / k\) of \(A\). We say that \(h\) is homomesic (with respect to the DDS \((X, \phi)\)) if and only if the averages of \(h\) on all cycles of \((X, \phi)\) are equal.

EXAMPLES:

sage: W = Words(2, 5)
sage: F = DiscreteDynamicalSystem(W, lambda x: x[1:] + Word([x[0]]), is_finite=True, inverse=True)
sage: F.is_homomesic(lambda w: sum(w))
False
sage: F.is_homomesic(lambda w: 1, average=1)
True
sage: F.is_homomesic(lambda w: 1, average=0)
False
sage: F.is_homomesic(lambda w: 1)
True
sage: F.is_homomesic(lambda w: 1, find_average=True)
1
sage: F.is_homomesic(lambda w: w[0] - w[1], average=0)
True
sage: F.is_homomesic(lambda w: w[0] - w[1], find_average=True)
0

>>> from sage.all import *
>>> W = Words(Integer(2), Integer(5))
>>> F = DiscreteDynamicalSystem(W, lambda x: x[Integer(1):] + Word([x[Integer(0)]]), is_finite=True, inverse=True)
>>> F.is_homomesic(lambda w: sum(w))
False
>>> F.is_homomesic(lambda w: Integer(1), average=Integer(1))
True
>>> F.is_homomesic(lambda w: Integer(1), average=Integer(0))
False
>>> F.is_homomesic(lambda w: Integer(1))
True
>>> F.is_homomesic(lambda w: Integer(1), find_average=True)
1
>>> F.is_homomesic(lambda w: w[Integer(0)] - w[Integer(1)], average=Integer(0))
True
>>> F.is_homomesic(lambda w: w[Integer(0)] - w[Integer(1)], find_average=True)
0

Now, let us check homomesy restricted to specific cycles:

sage: F = finite_dynamical_systems.bitstring_rotation(7)
sage: descents = lambda x: sum(1 for i in range(6) if x[i] > x[i+1])
sage: F.is_homomesic(descents)
False
sage: F.is_homomesic(descents, elements=[(1, 0, 1, 0, 0, 0, 0), (1, 0, 0, 1, 0, 0, 0)])
True
sage: F.is_homomesic(descents, elements=[(1, 0, 1, 0, 0, 0, 0), (1, 1, 0, 0, 0, 0, 0)])
False
sage: F.is_homomesic(descents, elements=[(1, 0, 1, 0, 0, 0, 0)])
True
sage: F.is_homomesic(descents, elements=[])
True

>>> from sage.all import *
>>> F = finite_dynamical_systems.bitstring_rotation(Integer(7))
>>> descents = lambda x: sum(Integer(1) for i in range(Integer(6)) if x[i] > x[i+Integer(1)])
>>> F.is_homomesic(descents)
False
>>> F.is_homomesic(descents, elements=[(Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)), (Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0))])
True
>>> F.is_homomesic(descents, elements=[(Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)), (Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0))])
False
>>> F.is_homomesic(descents, elements=[(Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0))])
True
>>> F.is_homomesic(descents, elements=[])
True

And here is a non-invertible finite dynamical system:

sage: F = finite_dynamical_systems.one_line([9, 1, 1, 6, 5, 4, 5, 5, 1])
sage: F.is_homomesic(lambda i: i)
True
sage: F.is_homomesic(lambda i: i % 2)
False
sage: F.is_homomesic(lambda i: i % 2, elements=[2, 9, 7])
True
sage: F.is_homomesic(lambda i: i % 2, elements=[2, 9, 4])
False
sage: F.is_homomesic(lambda i: i % 2, elements=[2, 9, 5, 7, 8, 2])
True

>>> from sage.all import *
>>> F = finite_dynamical_systems.one_line([Integer(9), Integer(1), Integer(1), Integer(6), Integer(5), Integer(4), Integer(5), Integer(5), Integer(1)])
>>> F.is_homomesic(lambda i: i)
True
>>> F.is_homomesic(lambda i: i % Integer(2))
False
>>> F.is_homomesic(lambda i: i % Integer(2), elements=[Integer(2), Integer(9), Integer(7)])
True
>>> F.is_homomesic(lambda i: i % Integer(2), elements=[Integer(2), Integer(9), Integer(4)])
False
>>> F.is_homomesic(lambda i: i % Integer(2), elements=[Integer(2), Integer(9), Integer(5), Integer(7), Integer(8), Integer(2)])
True
orbit(x, preperiod=False)[source]#

Return the orbit of the element x of the ground set of self under the evolution \(\phi\) of self.

This orbit is a list beginning with x and ending with the last element that is not a repetition of a previous element. If the orbit is infinite, then this method does not terminate!

If the optional argument preperiod is set to True, then this method returns a pair (o, k), where o is the orbit of self, while \(k\) is the smallest nonnegative integer such that \(\phi^k(x) \in \left\{ \phi^i(x) \mid i > k \right\}\).

The orbit of the element x is also called the “rho” of x, due to its shape when it is depicted as a directed graph.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(11)), lambda x: (x ** 2) % 11)
sage: D.orbit(6)
[6, 3, 9, 4, 5]
sage: D.orbit(6, preperiod=True)
([6, 3, 9, 4, 5], 1)
sage: D.orbit(3)
[3, 9, 4, 5]
sage: D.orbit(3, preperiod=True)
([3, 9, 4, 5], 0)
sage: D.orbit(9)
[9, 4, 5, 3]
sage: D.orbit(0)
[0]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(11))), lambda x: (x ** Integer(2)) % Integer(11))
>>> D.orbit(Integer(6))
[6, 3, 9, 4, 5]
>>> D.orbit(Integer(6), preperiod=True)
([6, 3, 9, 4, 5], 1)
>>> D.orbit(Integer(3))
[3, 9, 4, 5]
>>> D.orbit(Integer(3), preperiod=True)
([3, 9, 4, 5], 0)
>>> D.orbit(Integer(9))
[9, 4, 5, 3]
>>> D.orbit(Integer(0))
[0]
class sage.dynamics.finite_dynamical_system.FiniteDynamicalSystem(X, phi, cache_orbits=False, create_tuple=False)[source]#

Bases: DiscreteDynamicalSystem

A finite discrete dynamical system.

A finite discrete dynamical system (henceforth FDDS) is a pair \((X, \phi)\) of a finite set \(X\) and a map \(\phi : X \to X\). This set \(X\) is called the ground set of the FDDS, while the map \(\phi\) is called the evolution of the FDDS.

The ground set \(X\) should always be provided as an iterable when defining a FiniteDynamicalSystem.

EXAMPLES:

sage: from sage.dynamics.finite_dynamical_system import FiniteDynamicalSystem
sage: D = FiniteDynamicalSystem(tuple(range(11)), lambda x: (x**2) % 11)
sage: D.ground_set()
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
sage: D.evolution()(4)
5
sage: D.orbit(4)
[4, 5, 3, 9]
sage: D.orbit(1)
[1]
sage: D.orbit(2)
[2, 4, 5, 3, 9]

sage: X = cartesian_product([[0, 1]]*8)
sage: Y = [s for s in X if sum(s) == 4]
sage: rot = lambda s : s[1:] + (0,)
sage: D = FiniteDynamicalSystem(Y, rot)
sage: D.evolution()((1, 1, 1, 0, 1, 0, 0, 1))
(1, 1, 0, 1, 0, 0, 1, 0)

>>> from sage.all import *
>>> from sage.dynamics.finite_dynamical_system import FiniteDynamicalSystem
>>> D = FiniteDynamicalSystem(tuple(range(Integer(11))), lambda x: (x**Integer(2)) % Integer(11))
>>> D.ground_set()
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
>>> D.evolution()(Integer(4))
5
>>> D.orbit(Integer(4))
[4, 5, 3, 9]
>>> D.orbit(Integer(1))
[1]
>>> D.orbit(Integer(2))
[2, 4, 5, 3, 9]

>>> X = cartesian_product([[Integer(0), Integer(1)]]*Integer(8))
>>> Y = [s for s in X if sum(s) == Integer(4)]
>>> rot = lambda s : s[Integer(1):] + (Integer(0),)
>>> D = FiniteDynamicalSystem(Y, rot)
>>> D.evolution()((Integer(1), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 1, 0, 1, 0, 0, 1, 0)
cycles()[source]#

Return a list of all cycles of self, up to cyclic rotation.

We recall the definition of cycles: Let \((X, \phi)\) be a DDS. A cycle of \((X, \phi)\) is a finite list \(u = (u_1, u_2, \ldots, u_k)\) of elements of \(X\) such that \(\phi(u_i) = u_{i+1}\) for each \(i \leq k\), where we set \(u_{k+1} = u_1\). Note that any element of \(X\) whose orbit is finite has a cycle in its orbit.

EXAMPLES:

sage: BS = finite_dynamical_systems.bulgarian_solitaire
sage: BS(8).cycles()
[[[4, 3, 1], [3, 3, 2], [3, 2, 2, 1], [4, 2, 1, 1]],
 [[4, 2, 2], [3, 3, 1, 1]]]
sage: BS(6).cycles()
[[[3, 2, 1]]]

sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 2) % 6)
sage: D.cycles()
[[5, 1, 3], [4, 0, 2]]
sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x ** 2) % 6)
sage: D.cycles()
[[1], [4], [3], [0]]
sage: D = DiscreteDynamicalSystem(tuple(range(11)), lambda x: (x ** 2 - 1) % 11)
sage: D.cycles()
[[10, 0], [8], [4]]

sage: F = finite_dynamical_systems.one_line([4, 7, 2, 6, 2, 10, 9, 11, 5, 6, 12, 12, 12, 6])
sage: F.cycles()
[[6, 10], [12], [9, 5, 2, 7]]

>>> from sage.all import *
>>> BS = finite_dynamical_systems.bulgarian_solitaire
>>> BS(Integer(8)).cycles()
[[[4, 3, 1], [3, 3, 2], [3, 2, 2, 1], [4, 2, 1, 1]],
 [[4, 2, 2], [3, 3, 1, 1]]]
>>> BS(Integer(6)).cycles()
[[[3, 2, 1]]]

>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(2)) % Integer(6))
>>> D.cycles()
[[5, 1, 3], [4, 0, 2]]
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x ** Integer(2)) % Integer(6))
>>> D.cycles()
[[1], [4], [3], [0]]
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(11))), lambda x: (x ** Integer(2) - Integer(1)) % Integer(11))
>>> D.cycles()
[[10, 0], [8], [4]]

>>> F = finite_dynamical_systems.one_line([Integer(4), Integer(7), Integer(2), Integer(6), Integer(2), Integer(10), Integer(9), Integer(11), Integer(5), Integer(6), Integer(12), Integer(12), Integer(12), Integer(6)])
>>> F.cycles()
[[6, 10], [12], [9, 5, 2, 7]]
is_invariant(f)[source]#

Check if f is an invariant of self.

Let \((X, \phi)\) be a discrete dynamical system. Let \(Y\) be any set. Let \(f : X \to Y\) be any map. Then, we say that \(f\) is an invariant of \((X, \phi)\) if and only if \(f \circ \phi = f\).

EXAMPLES:

sage: W = Words(2, 5)
sage: F = DiscreteDynamicalSystem(W, lambda x: x[1:] + Word([x[0]]), is_finite=True)
sage: F.is_invariant(lambda w: sum(w))
True
sage: F.is_invariant(lambda w: 1)
True
sage: F.is_invariant(lambda w: w[0] - w[1])
False
sage: F.is_invariant(lambda w: sum(i**2 for i in w))
True

>>> from sage.all import *
>>> W = Words(Integer(2), Integer(5))
>>> F = DiscreteDynamicalSystem(W, lambda x: x[Integer(1):] + Word([x[Integer(0)]]), is_finite=True)
>>> F.is_invariant(lambda w: sum(w))
True
>>> F.is_invariant(lambda w: Integer(1))
True
>>> F.is_invariant(lambda w: w[Integer(0)] - w[Integer(1)])
False
>>> F.is_invariant(lambda w: sum(i**Integer(2) for i in w))
True

Invariants and non-invariants of a permutation:

sage: F = finite_dynamical_systems.permutation([3, 4, 5, 6, 1, 2])
sage: F.is_invariant(lambda i: i % 2)
True
sage: F.is_invariant(lambda i: i % 3)
False
sage: F.is_invariant(lambda i: i > 1)
False
sage: F.is_invariant(lambda i: i % 2 == 0)
True

>>> from sage.all import *
>>> F = finite_dynamical_systems.permutation([Integer(3), Integer(4), Integer(5), Integer(6), Integer(1), Integer(2)])
>>> F.is_invariant(lambda i: i % Integer(2))
True
>>> F.is_invariant(lambda i: i % Integer(3))
False
>>> F.is_invariant(lambda i: i > Integer(1))
False
>>> F.is_invariant(lambda i: i % Integer(2) == Integer(0))
True
class sage.dynamics.finite_dynamical_system.InvertibleDiscreteDynamicalSystem(X, phi, inverse=None, cache_orbits=False, create_tuple=False)[source]#

Bases: DiscreteDynamicalSystem

An invertible discrete dynamical system.

A discrete dynamical system (henceforth DDS) is a pair \((X, \phi)\) of a set \(X\) and a map \(\phi : X \to X\). This set \(X\) is called the ground set of the DDS, while the map \(\phi\) is called the evolution of the DDS. An invertible DDS is a DDS \((X, \phi)\) whose evolution \(\phi\) is invertible. In that case, \(\phi^{-1}\) is called the inverse evolution of the DDS.

See DiscreteDynamicalSystem for details.

INPUT:

  • X – set, list, tuple, or another iterable, or None; the ground set for the DDS. This can be None in case of a DiscreteDynamicalSystem or a InvertibleDiscreteDynamicalSystem. Make sure to set the create_tuple argument to True if you provide an iterator or a list for X, as otherwise the input would be exposed.

  • phi – function, or callable that acts like a function; the evolution of the DDS.

  • inverse – function, or callable that acts like a function; the inverse evolution of the DDS. (A default implementation is implemented when this argument is not provided; but it assumes the orbits to be finite.)

  • cache_orbits – boolean (default: False); whether or not the orbits should be cached once they are computed.

  • create_tuple – boolean (default: False); whether or not the input X should be translated into a tuple (set this to True to prevent mutation if X is a list, and to prevent exhaustion if X is an iterator).

EXAMPLES:

sage: from sage.dynamics.finite_dynamical_system import InvertibleDiscreteDynamicalSystem
sage: D = InvertibleDiscreteDynamicalSystem(NN, lambda x: (x + 2 if x % 4 < 2 else x - 2))
sage: D.ground_set()
Non negative integer semiring
sage: D.evolution()(5)
7
sage: D.evolution()(6)
4
sage: D.evolution()(4)
6
sage: D.inverse_evolution()(4)
6

>>> from sage.all import *
>>> from sage.dynamics.finite_dynamical_system import InvertibleDiscreteDynamicalSystem
>>> D = InvertibleDiscreteDynamicalSystem(NN, lambda x: (x + Integer(2) if x % Integer(4) < Integer(2) else x - Integer(2)))
>>> D.ground_set()
Non negative integer semiring
>>> D.evolution()(Integer(5))
7
>>> D.evolution()(Integer(6))
4
>>> D.evolution()(Integer(4))
6
>>> D.inverse_evolution()(Integer(4))
6

The necessity of create_tuple=True:

sage: X = [0, 1, 2, 3, 4]
sage: D_wrong = InvertibleDiscreteDynamicalSystem(X, lambda x: (x**3) % 5)
sage: D_right = InvertibleDiscreteDynamicalSystem(X, lambda x: (x**3) % 5, create_tuple=True)
sage: X[4] = 666 # evil
sage: D_wrong.ground_set()
[0, 1, 2, 3, 666]
sage: D_right.ground_set()
(0, 1, 2, 3, 4)

>>> from sage.all import *
>>> X = [Integer(0), Integer(1), Integer(2), Integer(3), Integer(4)]
>>> D_wrong = InvertibleDiscreteDynamicalSystem(X, lambda x: (x**Integer(3)) % Integer(5))
>>> D_right = InvertibleDiscreteDynamicalSystem(X, lambda x: (x**Integer(3)) % Integer(5), create_tuple=True)
>>> X[Integer(4)] = Integer(666) # evil
>>> D_wrong.ground_set()
[0, 1, 2, 3, 666]
>>> D_right.ground_set()
(0, 1, 2, 3, 4)
evolution_power(n)[source]#

Return the \(n\)-th power (with respect to composition) of the evolution of self.

This requires \(n\) to be an integer.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(range(10), lambda x: (x + 3) % 10, create_tuple=True, inverse=True)
sage: ev3 = D.evolution_power(3)
sage: ev3(1)
0
sage: ev3(2)
1
sage: ev0 = D.evolution_power(0)
sage: ev0(1)
1
sage: ev0(2)
2
sage: evm1 = D.evolution_power(-1)
sage: evm1(1)
8
sage: evm1(2)
9
sage: evm2 = D.evolution_power(-2)
sage: evm2(1)
5
sage: evm2(2)
6

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(range(Integer(10)), lambda x: (x + Integer(3)) % Integer(10), create_tuple=True, inverse=True)
>>> ev3 = D.evolution_power(Integer(3))
>>> ev3(Integer(1))
0
>>> ev3(Integer(2))
1
>>> ev0 = D.evolution_power(Integer(0))
>>> ev0(Integer(1))
1
>>> ev0(Integer(2))
2
>>> evm1 = D.evolution_power(-Integer(1))
>>> evm1(Integer(1))
8
>>> evm1(Integer(2))
9
>>> evm2 = D.evolution_power(-Integer(2))
>>> evm2(Integer(1))
5
>>> evm2(Integer(2))
6
inverse_evolution()[source]#

Return the inverse evolution of self (as a map from the ground set of self to itself).

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(8)), lambda x: (x + 2) % 8, inverse=True)
sage: D.inverse_evolution()(1)
7
sage: D.inverse_evolution()(3)
1

sage: D = DiscreteDynamicalSystem(ZZ, lambda x: (x + 2) % 8, inverse=True)
sage: D.inverse_evolution()(1)
7
sage: D.inverse_evolution()(3)
1

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(8))), lambda x: (x + Integer(2)) % Integer(8), inverse=True)
>>> D.inverse_evolution()(Integer(1))
7
>>> D.inverse_evolution()(Integer(3))
1

>>> D = DiscreteDynamicalSystem(ZZ, lambda x: (x + Integer(2)) % Integer(8), inverse=True)
>>> D.inverse_evolution()(Integer(1))
7
>>> D.inverse_evolution()(Integer(3))
1
inverse_evolution_default(x)[source]#

Return the inverse evolution of self, applied to the element x of the ground set of self.

This is the default implementation, assuming that the orbit of x is finite.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(8)), lambda x: (x + 2) % 8, inverse=True)
sage: D.inverse_evolution_default(1)
7
sage: D.inverse_evolution_default(3)
1

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(8))), lambda x: (x + Integer(2)) % Integer(8), inverse=True)
>>> D.inverse_evolution_default(Integer(1))
7
>>> D.inverse_evolution_default(Integer(3))
1
orbit(x, preperiod=False)[source]#

Return the orbit of the element x of the ground set of self.

This orbit is a list beginning with x and ending with the last element until x reappears. If x never reappears, then this will not terminate!

If the optional argument preperiod is set to True, then this method returns a pair (o, k), where o is the orbit of self, while \(k\) is the smallest nonnegative integer such that \(\phi^k(x) \in \left\{ \phi^i(x) \mid i > k \right\}\). Note that \(k\) is necessarily \(0\), since the DDS self is invertible!

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(8)), lambda x: (x + 2) % 8, inverse=True)
sage: D.ground_set()
(0, 1, 2, 3, 4, 5, 6, 7)
sage: D.orbit(2)
[2, 4, 6, 0]
sage: D.orbit(5)
[5, 7, 1, 3]
sage: D.orbit(5, preperiod=True)
([5, 7, 1, 3], 0)

sage: D = DiscreteDynamicalSystem(ZZ, lambda x: (x + 2) % 8, inverse=True)
sage: D.ground_set()
Integer Ring
sage: D.orbit(2)
[2, 4, 6, 0]
sage: D.orbit(5)
[5, 7, 1, 3]
sage: D.orbit(5, preperiod=True)
([5, 7, 1, 3], 0)

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(8))), lambda x: (x + Integer(2)) % Integer(8), inverse=True)
>>> D.ground_set()
(0, 1, 2, 3, 4, 5, 6, 7)
>>> D.orbit(Integer(2))
[2, 4, 6, 0]
>>> D.orbit(Integer(5))
[5, 7, 1, 3]
>>> D.orbit(Integer(5), preperiod=True)
([5, 7, 1, 3], 0)

>>> D = DiscreteDynamicalSystem(ZZ, lambda x: (x + Integer(2)) % Integer(8), inverse=True)
>>> D.ground_set()
Integer Ring
>>> D.orbit(Integer(2))
[2, 4, 6, 0]
>>> D.orbit(Integer(5))
[5, 7, 1, 3]
>>> D.orbit(Integer(5), preperiod=True)
([5, 7, 1, 3], 0)
verify_inverse_evolution(x=None)[source]#

Verify that the composition of evolution and inverse evolution on self is the identity (both ways).

The optional argument x, if provided, restricts the testing to the element x only. Otherwise, all elements of the ground set are tested (if they can be enumerated).

This is mostly used to check the correctness of self-implemented inverse evolution methods.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(8)), lambda x: (x + 2) % 8, inverse=True)
sage: D.verify_inverse_evolution()
True
sage: D.verify_inverse_evolution(3)
True
sage: fake_inverse = lambda x: x
sage: D = DiscreteDynamicalSystem(tuple(range(8)), lambda x: (x + 2) % 8, inverse=fake_inverse)
sage: D.verify_inverse_evolution()
False
sage: D.verify_inverse_evolution(3)
False

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(8))), lambda x: (x + Integer(2)) % Integer(8), inverse=True)
>>> D.verify_inverse_evolution()
True
>>> D.verify_inverse_evolution(Integer(3))
True
>>> fake_inverse = lambda x: x
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(8))), lambda x: (x + Integer(2)) % Integer(8), inverse=fake_inverse)
>>> D.verify_inverse_evolution()
False
>>> D.verify_inverse_evolution(Integer(3))
False
class sage.dynamics.finite_dynamical_system.InvertibleFiniteDynamicalSystem(X, phi, inverse=None, cache_orbits=False, create_tuple=False)[source]#

Bases: InvertibleDiscreteDynamicalSystem, FiniteDynamicalSystem

An invertible finite discrete dynamical system.

A finite discrete dynamical system (henceforth FDDS) is a pair \((X, \phi)\) of a finite set \(X\) and a map \(\phi : X \to X\). This set \(X\) is called the ground set of the FDDS, while the map \(\phi\) is called the evolution of the FDDS. An FDDS \((X, \phi)\) is called invertible if the map \(\phi\) is invertible; in this case, \(\phi^{-1}\) is called the inverse evolution of the FDDS.

The ground set \(X\) should always be provided as an iterable when defining a FiniteDynamicalSystem.

EXAMPLES:

sage: from sage.dynamics.finite_dynamical_system import InvertibleFiniteDynamicalSystem
sage: D = InvertibleFiniteDynamicalSystem(tuple(range(5)), lambda x: (x + 2) % 5)
sage: D.ground_set()
(0, 1, 2, 3, 4)
sage: D.evolution()(4)
1
sage: D.orbits()
[[4, 1, 3, 0, 2]]
sage: D.inverse_evolution()(2)
0
sage: D.inverse_evolution()(1)
4
sage: D.evolution_power(-1)(1)
4
sage: D.evolution_power(-2)(1)
2

sage: X = cartesian_product([[0, 1]]*8)
sage: Y = [s for s in X if sum(s) == 4]
sage: rot = lambda s : s[1:] + (s[0],)
sage: D = InvertibleFiniteDynamicalSystem(Y, rot)
sage: D.evolution()((0, 1, 1, 0, 1, 0, 0, 1))
(1, 1, 0, 1, 0, 0, 1, 0)
sage: D.inverse_evolution()((0, 1, 1, 0, 1, 0, 0, 1))
(1, 0, 1, 1, 0, 1, 0, 0)
sage: sorted(D.orbit_lengths())
[2, 4, 8, 8, 8, 8, 8, 8, 8, 8]

>>> from sage.all import *
>>> from sage.dynamics.finite_dynamical_system import InvertibleFiniteDynamicalSystem
>>> D = InvertibleFiniteDynamicalSystem(tuple(range(Integer(5))), lambda x: (x + Integer(2)) % Integer(5))
>>> D.ground_set()
(0, 1, 2, 3, 4)
>>> D.evolution()(Integer(4))
1
>>> D.orbits()
[[4, 1, 3, 0, 2]]
>>> D.inverse_evolution()(Integer(2))
0
>>> D.inverse_evolution()(Integer(1))
4
>>> D.evolution_power(-Integer(1))(Integer(1))
4
>>> D.evolution_power(-Integer(2))(Integer(1))
2

>>> X = cartesian_product([[Integer(0), Integer(1)]]*Integer(8))
>>> Y = [s for s in X if sum(s) == Integer(4)]
>>> rot = lambda s : s[Integer(1):] + (s[Integer(0)],)
>>> D = InvertibleFiniteDynamicalSystem(Y, rot)
>>> D.evolution()((Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 1, 0, 1, 0, 0, 1, 0)
>>> D.inverse_evolution()((Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)))
(1, 0, 1, 1, 0, 1, 0, 0)
>>> sorted(D.orbit_lengths())
[2, 4, 8, 8, 8, 8, 8, 8, 8, 8]
cycles()[source]#

Return a list of all cycles of self, up to cyclic rotation.

We recall the definition of cycles: Let \((X, \phi)\) be a DDS. A cycle of \((X, \phi)\) is a finite list \(u = (u_1, u_2, \ldots, u_k)\) of elements of \(X\) such that \(\phi(u_i) = u_{i+1}\) for each \(i \leq k\), where we set \(u_{k+1} = u_1\). Note that any element of \(X\) whose orbit is finite has a cycle in its orbit.

Since self is invertible, the cycles of self are the same as its orbits.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 2) % 6, inverse=True)
sage: D.cycles()
[[5, 1, 3], [4, 0, 2]]
sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 3) % 6, inverse=True)
sage: D.cycles()
[[5, 2], [4, 1], [3, 0]]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(2)) % Integer(6), inverse=True)
>>> D.cycles()
[[5, 1, 3], [4, 0, 2]]
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(3)) % Integer(6), inverse=True)
>>> D.cycles()
[[5, 2], [4, 1], [3, 0]]
orbit_lengths()[source]#

Return a list of the lengths of all orbits of self.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 2) % 6, inverse=True)
sage: D.orbit_lengths()
[3, 3]
sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 3) % 6, inverse=True)
sage: D.orbit_lengths()
[2, 2, 2]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(2)) % Integer(6), inverse=True)
>>> D.orbit_lengths()
[3, 3]
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(3)) % Integer(6), inverse=True)
>>> D.orbit_lengths()
[2, 2, 2]
orbits()[source]#

Return a list of all orbits of self, up to cyclic rotation.

EXAMPLES:

sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 2) % 6, inverse=True)
sage: D.orbits()
[[5, 1, 3], [4, 0, 2]]
sage: D = DiscreteDynamicalSystem(tuple(range(6)), lambda x: (x + 3) % 6, inverse=True)
sage: D.orbits()
[[5, 2], [4, 1], [3, 0]]

>>> from sage.all import *
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(2)) % Integer(6), inverse=True)
>>> D.orbits()
[[5, 1, 3], [4, 0, 2]]
>>> D = DiscreteDynamicalSystem(tuple(range(Integer(6))), lambda x: (x + Integer(3)) % Integer(6), inverse=True)
>>> D.orbits()
[[5, 2], [4, 1], [3, 0]]