28
C. M. Viallet
3.6 Complexity Analysis: Algebraic Entropy
Explicit calculations of the iterates of maps in the integrable case go much faster
than in the non-integrable case. The reason is that the degree of the iterates grows
slowly (polynomially) in the integrable case and rapidly (exponentially) in the nonintegrable case. This has led to the definition of the algebraic entropy from the
sequence of degrees {d n } of the iterates.
= lim
n→∞
1
n
Log(d n )
(7)
– This limit always exists by the subadditivity of Log(d n ), and is canonical, being
invariant by birational changes of coordinates.
– Vanishing of is the hallmark of integrability.
– The entropy has remarkable arithmetic properties (conjectured to be the Log of
an algebraic integer).
Claim: The entropy is consubstantial with the singularity structure. Indeed going
back to Figs. 3, 4 it is easy to convince oneself that—in the case shown—there
will be a drop of the degree for the third iterate of the map. The equation of the
hypersurface Σ will factor out from the rational expressions of the iterate [38, 41].
The entropy first defined for maps acting on finite dimensional spaces (ordinary
difference equations), has been further generalised to the infinite dimensional case,
allowing to consider semi-discrete equations [32] involving maps over functional
spaces and quad equations as well [42, 43].
3.7 What About Quad Equations?
The point is to define an evolution. Figure 5 shows how this can be done from a
staircase initial condition. The initial condition at time 0 of line (0) determines the
values on line (1) at time 1, line (2) at time 2, and so on.
The evolution after k steps is expressible as a rational fraction in terms of 2k + 1
initial values. Evaluating the degrees of these rational fractions gives a sequence of
degrees {d n }, providing in turn the value of the entropy.
We will not detail the calculation method here, but the asymptotic property which
the entropy measures can most of the time be extracted from a finite piece of the
sequence of degrees. This is a manifestation of the fact that a local property governs
the global behaviour.
Claim: The vanishing of the entropy is a good criterion of integrability for quad
equations as it is for maps.
C. M. Viallet
3.6 Complexity Analysis: Algebraic Entropy
Explicit calculations of the iterates of maps in the integrable case go much faster
than in the non-integrable case. The reason is that the degree of the iterates grows
slowly (polynomially) in the integrable case and rapidly (exponentially) in the nonintegrable case. This has led to the definition of the algebraic entropy from the
sequence of degrees {d n } of the iterates.
= lim
n→∞
1
n
Log(d n )
(7)
– This limit always exists by the subadditivity of Log(d n ), and is canonical, being
invariant by birational changes of coordinates.
– Vanishing of is the hallmark of integrability.
– The entropy has remarkable arithmetic properties (conjectured to be the Log of
an algebraic integer).
Claim: The entropy is consubstantial with the singularity structure. Indeed going
back to Figs. 3, 4 it is easy to convince oneself that—in the case shown—there
will be a drop of the degree for the third iterate of the map. The equation of the
hypersurface Σ will factor out from the rational expressions of the iterate [38, 41].
The entropy first defined for maps acting on finite dimensional spaces (ordinary
difference equations), has been further generalised to the infinite dimensional case,
allowing to consider semi-discrete equations [32] involving maps over functional
spaces and quad equations as well [42, 43].
3.7 What About Quad Equations?
The point is to define an evolution. Figure 5 shows how this can be done from a
staircase initial condition. The initial condition at time 0 of line (0) determines the
values on line (1) at time 1, line (2) at time 2, and so on.
The evolution after k steps is expressible as a rational fraction in terms of 2k + 1
initial values. Evaluating the degrees of these rational fractions gives a sequence of
degrees {d n }, providing in turn the value of the entropy.
We will not detail the calculation method here, but the asymptotic property which
the entropy measures can most of the time be extracted from a finite piece of the
sequence of degrees. This is a manifestation of the fact that a local property governs
the global behaviour.
Claim: The vanishing of the entropy is a good criterion of integrability for quad
equations as it is for maps.