Finite-space dynamical systems

Question

This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ elements, and consider an arbitrary map $f:X\to X$. This is a dynamical system: one can iterate $f$ and look at what happens.

Of course, it is in some sense trivial: there are a certain number of periodic orbits (including fixed points), and all other points are attracted to exactly one of these periodic orbits. But I am convinced that behind this triviality, there are interesting questions that may not have been considered much.

I know one instance of an interesting question that has been asked, by Misiurewicz: it is about discretizations of the logistic map. The same kind of question can be asked for other continuous-space dynamical systems, of course, but the logistic map seems to have the good amount of simplicity and complicated behavior to make it a reasonable first case to consider (I am not implying that the conjecture stated there should be easy!).

My first sub-question is reasonably precise:

Is there any case of finite-state dynamical systems which have been considered in the literature, other than numerical simulation of continuous-state dynamical systems?

Of course, theoretical results on such numerical simulations would also be of interest to me, though I am even more interested in knowing what one can say interesting in general about finite-state dynamical systems. My second sub-question is less focused.

Can one deduce global dynamical properties of a finite-state dynamical system (number of periodic orbits, length of periodic orbits, size of their basin of attraction) from local properties (let us call a property local if it is defined for subsets of $X$ of at most $k$ elements, and can be checked by iterating at most $k$ times the map $f$, with $k$ independent of $n$). Non-trivial inequalities would be of course very good.

As an intermediate case, we could look at semi-local properties where $k$ is allowed to grow with $n$, but very slowly.

Last, I would also be interested in the typical behavior of a random finite-state dynamical system:

What can be said about the dynamical quantities ((number of periodic orbits, length of periodic orbits, size of their basin of attraction) of a finite-state dynamical system on $n$ points, drawn uniformly among all maps?

Added in edit: a relevant paper appeared today : Random cyclic dynamical systems by Michał Adamaszek, Henry Adams, Francis Motta, where randomness is on a subset of the phase space (there, the circle) where a continuous dynamical system (there, a rotation) is to be approximated. An applications to computational topology is given.

Answer 1

In algebraic geometry, in the sixties, Weil proposed to look at the action of the Frobenius automorphism on a variety over a finite field, and apply a Lefschetz formula in some suitable cohomology, in order to study the property of the zeta function associated to the variety (the so called Weil conjectures). The program was carried by Grothendieck and Deligne who were each awarded with a Fields medal for their work.

So reduction mod p of algebraic systems gives you interesting examples of "finite" dynamical systems, and the Frobenius automorphism appears only after reduction. I am sure that there are many people on MO that can provide more details, and perhaps discuss more recent developments, on that subject.

There is of course a strong parallel with dynamical zeta functions and their rationality in the field of hyperbolic dynamical systems.

EDIT: I guess that reduction mod p is also a motivation for studying p-adic dynamics. I think there was some attempt to show that the Mandlebrot set is locally connected by iterating the quadratic map over the p-adic numbers.

Answer 2

Pollard-rho factorization is based on the dynamics of polynomials on the congruence classes mod $p$.

If you iterate a polynomial $f$ with integer coefficients mod $pq$, where the factorization is unknown, this is equivalent to iterating the polynomial mod $p$ and mod $q$. If you can find $m,n$ so that $f^m(x_0) \equiv f^n(x_0) \mod p$ while $f^m(x_0) \not\equiv f^n(x_0) \mod q$, then $\operatorname{GCD}(f^m(x_0)-f^n(x_0),pq)=p$. Iterating polynomials mod $pq$ is fast and so is finding the greatest common divisor using Euclid's algorithm. So, it is of interest to find the typical cycle lengths of iterated polynomials mod $p$ and mod $q$. These are heuristically modeled as more general random functions on finite sets, and this produces good but nonrigorous estimates of the running time.

See Flajolet and Sedgewick, Analytic Combinatorics, pp. 129-132.

Answer 3

There's been a lot of work in recent years on the orbit structure of polynomials and/or rational maps acting on points of varieties (especially $\mathbb P^1$) over finite fields. One gets a directed graph of points, where $x$ is connected to $y$ if $y=f(x)$. Natural questions include: (1) How many distinct components are there in the graph? (2) How many points are in the largest components? (3) How many points are in the largest cycles? (4) What is the proportion of periodic points to strictly preperiodic (i.e, not periodic) points? ...

For example, you might be interested in the paper:

Rafe Jones, Iterated Galois towers, their associated martingales, and the $p$-adic Mandelbrot set, Compos. Math. 143 (2007), 1108-1126.

He proves that as $c$ ranges over $\mathbb F_{p^n}$, then for most $c$ values, the critical point $0$ of $f_c(x)=x^2+c$ has a strictly preperiodic orbit. (By "most" values, I mean that as $n\to\infty$, the proportion goes to 1.) The proof is highly non-trivial. A motivation for this work is that it is related to $p$-adic hyperbolicity of orbits.

Another direction of study for dynamics over finite fields (or more generally, finite rings) is the whole area of permutation polynomials. See https://en.wikipedia.org/wiki/Permutation_polynomial.

Concerning your last question, there are some conjectures (and some very weak estimates) for averages over families of maps in a paper of mine: Variation of periods modulo $p$ in arithmetic dynamics, New York J. Math. 14 (2008), 601-616.

There's a long'ish list of papers on arithmetic dynamics at http://math.brown.edu/~jhs/ADSBIB.pdf. You'll find lots of references there to dynamics over finite fields (although also many papers on dynamics over number fields and $p$-adic fields).

Finally, I'll mention that my answer to this MO question is relevant and has some further references: Conjectures on iterated polynomial maps on finite fields

Answer 4

Not all interesting examples come from algebraic geometry and number theory -- your questions are fairly natural in many other settings. For instance, Conway's game of life qualifies as an answer to your first question. It is well-studied and exhibits all sorts of crazy behavior. Could you answer the second question even for this well-studied dynamical system? (I'm honestly not sure).

There is extensive literature on "graph dynamical systems" (that precise phrase brings up plenty on google). These systems subsume all finite cellular automata and are completely prescribed by the following data:

1. an underlying graph $G$ on $n$ ordered vertices,
2. a finite set $K$ (often $\{0,1\}$),
3. for each vertex $v$, a state $x_v \in K$,
4. for each vertex $v$, a function $f_v:K^{|v|} \to K$ where $|v|$ is the number of neighbors of $v$ in $G$.

All this yields an obvious dynamical system on $K^n$: given $(x_1,\ldots, x_n)$, assign the $x_i$ as states to the $n$ ordered vertices, apply your $f_v$ to the old states (making sure you choose neighbor vertices in order), get new states, and so on. You could encode some pretty terrible dynamics here, so I'm not sure what "sufficient conditions" on $k$-fold iterates would help you extract any global properties.

Answer 5

For positive integer $n$, let $F_n$ be the set of all fractions $m/n$ with $0<m\le n$ and $\gcd(m,n)=1$, and consider the function given by letting $f(m/n)$ be the fractional part of $n/m$. Well, I guess it's not quite a dynamical system, since eventually you get to $f(1/1)=0$, and $0$ is not in the domain. But if you ignore that little glitch, then what we have is the way to generate the continued fraction expansion of $m/n$, and questions about the length of the expansion (the number of iterations needed to get to $1/1$) are of great interest.

Answer 6

For your last question, you can consult the book of B. Bollobás Random graphs (paragraph XIV.5). You will find many properties of random maps of finite sets, for instance, for a random map of a set with $q$ elements, the average number of periodic orbits is asymptotically $\log q$. Some heuristic works have been made to compare the dynamics of the discretization of some dynamics with such random maps (e.g. P. Diamond, et al, « Collapsing effects in numerical simulation of a class of chaotic dynamical systems and random mappings with a single attracting centre », Phys. D 86 (1995), no. 4, p. 559–571, or T. Miernowski, « Discrétisations des homéomorphismes du cercle », Ergodic Theory Dynam. Systems 26 (2006), no. 6, p. 1867–1903.)

Also, the dynamical properties of generic conservative homeomorphisms of compact manifolds of dim $\ge 2$ can be obtained by approximating the homeo by finite maps with a given dynamics. Here, "generic" is taken in the sense of Baire (a property is said to be generic if it is true on a $G_\delta$ dense subset of homeos), and "conservative" means that the homeos are supposed to preserve a given good measure. The main theorem is that such a generic conservative homeo is transitive ; it is an easy consequence of a theorem of approximation of P. Lax and S. Alpern : any conservative homeo is approximated by a cyclic permutation of a reasonable grid on the manifold (see « Approximation of measure preserving transformations », Comm. Pure Appl. Math. 24 (1971), p. 133–135.). You will find more on this subject in "Propriétés dynamiques génériques des homéomorphismes conservatifs" (Ensaios Matemáticos vol. 22, 2012). These results are closely related to what happens for generic automorphisms, as stated by a theorem of S. Alpern (see also « Generic properties of measure preserving homeomorphisms», Ergodic theory -- Proc. Conf., Math. Forschungsinst., Oberwolfach, 1978 --, Lecture Notes in Math., vol. 729, Springer, Berlin, 1979, p. 16–27.).

These results can be used to obtain many results about the dynamics of the discretizations of generic conservative homeos, see for example my paper Dynamical properties of spatial discretizations of a generic homeomorphism.

Answer 7

As Vidit Nanda pointed out in the third answer, cellular automata (on lattices) or generalized cellular automata (GCAs, or graph dynamical systems) provide a large and interesting class of finite dynamical systems such that the global behavior emerges from iterating locally defined transition maps.

I have an interesting GCA model for studying synchronization of coupled oscillators, such as synchronous blinking of fireflies. You can find examples and some global theorems in my recent paper:

Lyu, Hanbaek. "Synchronization of finite-state pulse-coupled oscillators." Physica D: Nonlinear Phenomena 303 (2015): 28-38. (preprint http://arxiv.org/abs/1407.1103)

To give you a quick taste, the 4-color model on a simple graph $G=(V,E)$ is defined as follows:

1) A 4-configuration is mapping $X:V\rightarrow \mathbb{Z}_{4}$

2) Transition map $\tau_{G}:T\mapsto T'$ is defined by \begin{equation} \tau_{G}(X)(v) = \begin{cases} X(v) & \text{if $X(v)\in \{2,3\}$ and $\exists$ a neighbor $u$ of $v$ with $X(u)=1$}\\ X(v)+1 & \text{otherwise} \end{cases} \end{equation}

In words, each vertex is an oscillator with 4 states, and at each iteration, every blinking vertex(i.e., of state 1) inhibits its hasty neighbors (i.e., of state 2 and 3) for one iteration. Similar model can be defined for any period $n$ with blinking state $b(n):=\lfloor \frac{n-1}{2}\rfloor$.

As you have mentioned, every orbit must converge to exactly one periodic orbit. This may seem so trivial that there is nothing left to study, but it is not. There is a one special periodic orbit, called synchrony, where all vertices eventually have the same state. Then the question is the following: what are the conditions for the underlying graph $G$ and the initial configuration $X$ that guarantee the orbit eventually converges to synchrony? Each vertex tries to synchronize with their neighbors by a weak coupling, but yet it is highly unclear if this aggregation of local effort would really lead to global synchronization. I am currently studying this model on $\mathbb{Z}^{2}$.

A related model is the Cyclic Cellular Automata(CCA) invented by David Griffeath. There are some rigorous results on clustering of 3-color CCA on $\mathbb{Z}$ by R. Fisch, where the author uses correspondence between the induced edge particle system and simple random walks to show clustering on a fixed finite interval with high probability. CCA on $\mathbb{Z}^{2}$ generally shows very complicated spiraling behavior, which is relevant to autowaves on excitable medium.