Partial dynamical systems form semiring with distinct prime elements
Solving polynomial equations over partial discrete dynamical systems
Discrete Mathematics
Summary
The paper looks at mathematical models used to describe systems where things change over time, like populations or planets. Usually, these models assume every state leads to exactly one next state, but real observations might be incomplete. The authors study what happens when some transitions are missing, creating 'partial' systems. They prove that these partial systems still behave in a nice structured way, and they identify unique features compared to the complete systems. This helps understand how certain equations behave when applied to both full and partial systems.
What this means in practice
- •For algorithm designers: Determine when polynomial division algorithms can run efficiently on partial or complete dynamical systems.
- •For computational biologists: Model imperfectly observed biological systems with partial dynamical systems to better reflect missing data scenarios.
A theory result. No direct application yet.
Authors
Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge
Abstract
The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviours. If the conditions are ideal and the number of observations is sufficient, we can represent these phenomena by a dynamical system, also called a functional digraph, that is to say a graph where each node has out-degree exactly one. Up to isomorphism, these dynamical systems, equipped with disjoint union as addition and direct product as multiplication, form a commutative semiring. Several previous studies on this semiring have aimed to establish algebraic properties (primality, injectivity) or complexity results (division, factorisation). However, no work has yet been conducted on graphs derived from imperfect observations that result in missing transitions or nodes, in other words, in cases where each node in the graph has an out-degree of at most one. In this case, we say that the system is partial. In this paper, we show that partial dynamical systems, up to isomorphism and equipped with the same addition and multiplication, still form a commutative semiring. We then characterise the prime elements of this semiring, which differ from those of the semiring of dynamical systems. Finally, we highlight two properties shared by both semirings. First, injective univariate polynomials admit the same characterisation in both. Second, division can be computed in polynomial time for partial dynamical systems if and only if it can be for dynamical systems.