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 callingDiscreteDynamicalSystem
with the parameteris_finite
set toTrue
.InvertibleDiscreteDynamicalSystem
: invertible discrete dynamical system. This implements aninverse_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 callingDiscreteDynamicalSystem
with the parameterinverse
provided.InvertibleFiniteDynamicalSystem
: invertible finite discrete dynamical system. This can be instantiated by callingDiscreteDynamicalSystem
with the parameteris_finite
set toTrue
and the parameterinverse
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)¶
Bases:
sage.structure.sage_object.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\). This set \(X\) is called the ground set of the DDS, while the map \(\phi\) is called the evolution of the DDS.
A discrete dynamical system (short: 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.) Thus, a DDS is the same as an endomorphism of a set. The DDS is said to be finite if \(X\) is finite. The DDS is said to be invertible if the map \(\phi\) is invertible. 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.
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, orNone
(default:None
); the ground set for the DDS. Tthis can beNone
(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 thecreate_tuple
argument toTrue
if theX
you provide is an iterator or a list, as otherwise yourX
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 inputX
should be translated into a tuple. Set this toTrue
to prevent mutation ifX
is a list, and to prevent exhaustion ifX
is an iterator.inverse
– function, or callable that acts like a function, or boolean orNone
(default:None
); the inverse evolution of the DDS, if the DDS is invertible. Set this toNone
orFalse
if the DDS is not invertible (or you don’t want Sage to treat it as such). Alternatively, by setting this argument toTrue
, 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 orNone
(default:None
); whether the DDS is finite. The default optionNone
leaves this to Sage to decide. Only set this toTrue
if you provide the ground setX
.
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
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)
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]
Setting the
inverse
parameter toNone
orFalse
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]
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]
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]
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)
- evolution()¶
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
- evolution_power(n)¶
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
- ground_set()¶
Return the ground set of
self
.This will return
None
if no ground set was provided in the construction ofself
.Warning
Unless
self
has been constructed with thecreate_tuple
parameter set toTrue
, 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 corruptself
.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)
- is_homomesic(h, average=None, find_average=False, elements=None)¶
Check if
h
(a map from the ground set ofself
to a \(\QQ\)-vector space) is homomesic with respect toself
.If the optional argument
average
is provided, then this also checks that the averages are equal toaverage
.If the optional argument
find_average
is set toTrue
, then this method returns the average ofh
in caseh
is homomesic (instead of returningTrue
).If the optional argument
elements
(an iterable of elements of the ground set ofself
) is provided, then this method only checks homomesy for the cycles in the orbits of the elements given in the listelements
. Note thatelements
must be provided if the ground set ofself
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
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
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
- orbit(x, preperiod=False)¶
Return the orbit of the element
x
of the ground set ofself
under the evolution \(\phi\) ofself
.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 toTrue
, then this method returns a pair(o, k)
, whereo
is the orbit ofself
, 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” ofx
, 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]
- class sage.dynamics.finite_dynamical_system.FiniteDynamicalSystem(X, phi, cache_orbits=False, create_tuple=False)¶
Bases:
sage.dynamics.finite_dynamical_system.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)
- cycles()¶
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]]
- is_invariant(f)¶
Check if
f
is an invariant ofself
.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
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
- class sage.dynamics.finite_dynamical_system.InvertibleDiscreteDynamicalSystem(X, phi, inverse=None, cache_orbits=False, create_tuple=False)¶
Bases:
sage.dynamics.finite_dynamical_system.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, orNone
; the ground set for the DDS. This can beNone
in case of aDiscreteDynamicalSystem
or aInvertibleDiscreteDynamicalSystem
. Make sure to set thecreate_tuple
argument toTrue
if you provide an iterator or a list forX
, 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 inputX
should be translated into a tuple (set this toTrue
to prevent mutation ifX
is a list, and to prevent exhaustion ifX
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
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)
- evolution_power(n)¶
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
- inverse_evolution()¶
Return the inverse evolution of
self
(as a map from the ground set ofself
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
- inverse_evolution_default(x)¶
Return the inverse evolution of
self
, applied to the elementx
of the ground set ofself
.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
- orbit(x, preperiod=False)¶
Return the orbit of the element
x
of the ground set ofself
.This orbit is a list beginning with
x
and ending with the last element untilx
reappears. Ifx
never reappears, then this will not terminate!If the optional argument
preperiod
is set toTrue
, then this method returns a pair(o, k)
, whereo
is the orbit ofself
, 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 DDSself
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)
- verify_inverse_evolution(x=None)¶
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 elementx
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
- class sage.dynamics.finite_dynamical_system.InvertibleFiniteDynamicalSystem(X, phi, inverse=None, cache_orbits=False, create_tuple=False)¶
Bases:
sage.dynamics.finite_dynamical_system.InvertibleDiscreteDynamicalSystem
,sage.dynamics.finite_dynamical_system.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]
- cycles()¶
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 ofself
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]]
- orbit_lengths()¶
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]
- orbits()¶
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]]