Injective and pseudo-injective polynomial equations: From permutations to dynamical systems
This work provides incremental algorithmic improvements for researchers in dynamical systems and algebra, advancing the solution of polynomial equations in FDDS.
The paper tackles the problem of solving polynomial equations in finite discrete-time dynamical systems (FDDS) by proposing two polynomial algorithms for division and computing k-th roots under connectivity constraints, enabling efficient solutions to equations like AX^k=B for connected systems.
Finite discrete-time dynamical systems (FDDS) model phenomena that evolve deterministically in discrete time. It is possible to define sum and product operations on these systems (disjoint union and direct product, respectively), giving a commutative semiring. This algebraic structure led to several works employing polynomial equations to model hypotheses on phenomena modelled using FDDS. To solve these equations, algorithms for performing division and computing $k$-th roots are needed. In this paper, we propose two polynomial algorithms for these tasks, under the condition that the result is a connected FDDS. These algorithms exploit the notion of unroll of a FDDS, an alternative representation based on a forest of infinite trees constructed by computing the transition function of the system backwards. This ultimately leads to an efficient solution to equations of the type $AX^k=B$ for connected $X$ and some generalisations. These results are some of the important final steps for solving more general polynomial equations on FDDS.