The semiring of dynamical systems

28 June 2020

This is a post about something I’m working on at the moment, the semiring of finite, discrete time dynamical systems [1]. Here’s a picture to get you interested, a portion of the multiplication table of dynamical systems (everyone loves this️).

Here, a dynamical system $(A,f)$ is just a finite set $A$ of states (including $\varnothing$) with a state transition function $f \colon A \to A$ (any function will do). Each such dynamical system consists of one or more limit cycles with oriented trees having the points of those cycles as their roots.

You can define operations on dynamical systems (modulo isomorphism) and obtain a commutative semiring $(\mathbf{D},+,×)$.

The sum $+$ is defined as $(A,f) + (B,g) = (A⊎B, f+g)$ where $(f+g)(x) = f(x)$ if $x ∈ A$ and $(f+g)(x) = g(x)$ if $x ∈ B$. The empty dynamical system $0_{\mathbf{D}} = (\varnothing, \varnothing)$ is the identity of $+$.

The product $×$ is $(A,f) × (B,g) = (A×B, f×g)$ where $(f×g)(x,y) = (f(x),g(y))$. The dynamical system with one point $1_{\mathbf{D}} = (\{x\},\mathrm{id})$ is the identity of $×$.

In terms of graphs of the dynamics $(V,E) = (A, \{ (x,f(x)) : x ∈ A \})$, the sum is disjoint union and the product is the tensor (or Kronecker) product.

$(\mathbf{D},+,×)$ has the natural numbers $(ℕ,+,×)$ as a subsemiring. It’s the image of the injective homomorphism $ϕ: ℕ → \mathbf{D}$ defined as $ϕ(n) =$ the dynamical system consisting of exactly n fixed points. These behave as expected with respect to the others, e.g., $ϕ(n) × A = \underbrace{A + ⋯ + A}_{n \text{ times}}$.

$(\mathbf{D},+,×)$ is quite complex as a semiring. There are infinitely many elements with multiple factorisations into irreducibles, the smallest one being $C₂+C₂ = (C₂)² = 2C₂$, where $C₂$ is the cycle of length two (see the table above). We don’t know yet which are its prime elements, or if any exists at all.

Furthermore, the majority of elements of $\mathbf{D}$ are irreducible. More precisely, we have $\lim_{n \to \infty} \frac{\text{# reducible dyn. systems of size } n}{\text{# dyn. systems of size } n} = 0$. This was proved by Valentina Dorigatti in her master’s thesis.

You can study a form of (de)composition of dynamical systems by considering polynomial equations. In the following the polynomials are always over $\mathbf{D}[\vec{X}]$ or its subsemiring $ℕ[\vec{X}]$, with many variables $\vec{X} = (X_1,…,X_n)$. The general form of an equation is $p(\vec{X}) = q(\vec{X})$, since you cannot move everything to the left-hand side due to the lack of subtraction.

Each equation $p(\vec{X}) = q(\vec{X})$ over $\mathbf{D}[\vec{X}]$ has an associated equation $p(\vec{X}) = q(\vec{X})$ over $ℕ[\vec{X}]$, obtained by replacing each dynamical system $A$ by its size $|A|$. If $p,q ∈ ℕ[\vec{X}]$ are polynomials over $ℕ$ and $(A_1,…A_n)$ is a solution in $\mathbf{D}$ to $p(\vec{X}) = q(\vec{X})$, then $(|A_1|,|A_2|,…)$ is another solution, this time over the naturals.

So, by searching for solutions in the larger semiring $\mathbf{D}$ we might sometimes find new solutions to equations with natural coefficients, but only if a natural solution already exists. This means that Hilbert’s 10th problem over $\mathbf{D}$ has a negative answer! There is no algorithm for deciding if an equation over $\mathbf{D}[\vec{X}]$ has a solution (much less finding one), otherwise you could use that algorithm for $ℕ[\vec{X}]$ too.

Equations with a constant side like $p(\vec{X}) = A$ with $p ∈ \mathbf{D}[\vec{X}]$ and $A ∈ \mathbf{D}$ are decidable and in $\mathsf{NP}$: since $+$ and $×$ are monotonic with respect to the size of the dynamical systems, the value $|A|$ gives you a bound to the size of the solution, which you can guess and check in polynomial time.

You can do the check in polynomial time because the graphs of the dynamics, being just some cycles with trees going into them, are planar; the graph isomorphism problem for planar graphs is in $\mathsf{L} ⊆ \mathsf{P}$, and actually complete for it.

Unfortunately, deciding if $p(\vec{X}) = A$ has a solution is $\mathsf{NP}$-complete [2]. We can prove it by reduction from One-in-three 3SAT, the problem of finding if a Boolean formula $\varphi$ in ternary conjunctive normal form has a satisfying assignment where exactly one literal per clause is true.

For each variable $X$ of formula $\varphi$ we construct an equation $X + X’ = 1$. Here $X’$ represents the literal $¬X$, and exactly one of $X$ and $X’$ will be $1$, while the other will be $0$. For each clause, e.g., $(X_1 ∨ ¬X_2 ∨ X_3)$, we have an equation $X_1 + X_2’ + X_3 = 1$, which forces exactly one literal to $1$, and the others to $0$.

This gives us a system of $m$ linear equations of the form $p_i(\vec{X}) = 1$. By multiplying all left- and right-hand sides we get $∏_{i=1}^m p_i(\vec{X}) = 1$, which has the same solution as the system of linear equations. This proves the $\mathsf{NP}$-hardness, but only uses the subsemiring $ℕ$ of $\mathbf{D}$.

With a little more work, and thanks to the colleague Florian Bridoux and the research intern Émile Naquin-Touileb I’m currently supervising, we can prove that deciding if a single linear equation over $\mathbf{D}[\vec{X}]$ has solution is $\mathsf{NP}$-complete; this finally exploits its non-natural elements.

With another research intern I supervised, Caroline Gaze-Maillot, we have recently analysed dynamical systems $(A,f)$ more abstractly, in terms of their “profiles” $(|A|_1,|A|_2,…)$, where $|A|_i$ is the number of points at distance $i$ (in terms of number of applications of $f$) from their limit cycle [3]. The term is inspired by the topographic profile of a terrain, and here’s an example of dynamical system having profile $(8, 7, 8, 4)$:

(In case you’re interested, the contour lines in this picture are an approximation, in reverse order of altitude, of those of Mont Puget, a nice mountain which is just a 45 minute walk away from my office in Luminy, Marseille.)

We discovered that the profiles of dynamical systems also form a commutative semiring $(\mathbf{P},+,×)$, with “taking the profile” being a semiring homomorphism $\mathbf{D} → \mathbf{P}$, and this is also complicated stuff, with multiple factorisations, polynomial equations that are undecidable or $\mathsf{NP}$-complete, etc.

Some further work has been done on equations when one is only interested in the asymptotic behaviour of the systems, that is, on the their limit cycles [4].

Shout-out to everyone who worked on this: Florian Bridoux, Alberto Dennunzio, Valentina Dorigatti, Enrico Formenti, Caroline Gaze-Maillot, Maximilien Gadouleau, Luca Manzoni, Luciano Margara, Valentin Montmirail, yours truly, Sara Riva, and Émile Naquin-Touileb.

Bibliography

  1. Dennunzio, A., Dorigatti, V., Formenti, E., Manzoni, L., Porreca, A.E.: Polynomial equations over finite, discrete-time dynamical systems. In: Mauri, G., El Yacoubi, S., Dennunzio, A., Nishinari, K., and Manzoni, L. (eds.) Cellular Automata, 13th International Conference on Cellular Automata for Research and Industry, ACRI 2018. pp. 298–306. Springer (2018). [link] [preprint]
  2. Porreca, A.E.: Composing behaviours in the semiring of dynamical systems. In: International Workshop on Boolean Networks (IWBN 2020) (2020). [link]
  3. Gaze-Maillot, C., Porreca, A.E.: Profiles of dynamical systems and their algebra. arXiv e-prints. (2020). [link] [preprint]
  4. Dennunzio, A., Formenti, E., Margara, L., Montmirail, V., Riva, S.: Solving equations on discrete dynamical systems (extended version). arXiv e-prints. (2019). [link]