Source-linked AI summary
Solving polynomial equations over partial discrete dynamical systems
Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge
TL;DR
The paper studies polynomial equations over partial systems and develops structural results about their algebra. It proves that no finite forest is cancellable in the relevant pseudo-semiring and transfers polynomial-time solvability from FDDS equations to a specified class of partial-system equations.
Problem
The paper examines polynomial equations over partial systems and the algebraic properties needed to understand their solutions.
Source: §2.2 · p. 6, §3 · p. 10Method
The authors reduce a class of partial-system equations to finite-forest equations, using an existing polynomial-time algorithm and a reconstruction step where possible.
Source: §3 · p. 10, §3.2 · p. 13Results
A polynomial-time algorithm for the corresponding FDDS equations yields one for equations with coefficients extended by finite forests and a right-hand side whose T-part is the FDDS.
Source: §3 · p. 10Takeaways & Limitations
No finite forest is cancellable in the pseudo-semiring of finite forests under disjoint union and direct product.
Source: §2.2 · p. 8Restricting to the finite-forest pseudo-semiring can exclude solutions whose partial-system unrolls involve cycles.
Source: §3.2 · p. 17
Abstract
from arXiv · showhide
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.
1 Preliminaries
The preliminaries represent finite deterministic systems as functional digraphs and introduce unrolls and their algebraic operations. They also review prior results on polynomial equations, injectivity, and solving over these structures.
1 Preliminaries
- An FDDS is a set of states with a total transition function, whose graph decomposes into components with a unique limit cycle and attached trees.Components without attached trees are cycles; those with a cycle of length one are dendrons.Source: §1 · p. 1
- Prior work established that FDDS with disjoint union and direct product form a commutative semiring, and studied polynomial equations with a fixed right-hand side.The general solving problem is undecidable, while fixing the right-hand side places the decision problem in NP.Source: §1 · p. 2
- An unroll replaces each cycle vertex with an infinite branch and periodically attaches the finite trees rooted at cycle vertices.Unroll trees have a product defined by pairing vertices at equal depths; the product depth equals that of the shallower factor.Source: §1 · p. 2
- Unrolls form a commutative semiring, and the unroll map preserves addition and multiplication; finite forests with these operations form a pseudo-semiring.Unroll trees are cancellable, and equations between unrolls of dendrons can be solved by cutting at a suitable depth.Source: §1 · p. 2
- All univariate polynomials over unrolls are injective; for a polynomial over FDDS, injectivity holds if and only if some nonconstant coefficient contains a dendron.Source: §1 · p. 3
- Prior work gives polynomial-time algorithms for equations over finite forests and for certain equations involving unrolls [6].The cited results also characterize injective polynomials over FDDS [6].Source: §1 · p. 3
2 Algebraic properties of partial systems
This section develops algebraic properties of partial systems, including their super-semiring structure, the ideal of finite forests, and the unique prime. It also presents unroll-based results on forest algebra and characterizes cancellation and polynomial injectivity using dendrons.
2 Algebraic properties of partial systems
- Finite forests form an ideal of the partial-system semiring, and their sum-and-product structure is a pseudo-semiring without a multiplicative identity.The cycle-containing components define a homomorphism to the full-system semiring; forests are closed under addition and multiplication.Source: §2 · p. 3
2.1 Prime elements of partial systems
- The isolated point without a loop is the unique prime element of the partial-system semiring, but it is not irreducible.Its idempotence makes it a product of two non-invertible elements.Source: §2.1 · pp. 4–5
2.2 Injectivity of polynomials over partial systems
- The partial-system unroll is an isomorphism from finite forests under direct product to their unrolls under tree product, and it is a morphism on partial systems.For finite forests A and B, the unroll of A × B equals the tree product of their unrolls.Source: §2.2 · pp. 6, 7, 9
- No finite forest is cancelable, and any cancelable partial system must contain a dendron; for finite forests, product equality holds exactly when the factors’ cuts at depth d(A) agree.Distinct finite forests with equal cuts at the relevant depth yield equal products, establishing the non-cancellation result.Source: §2.2 · p. 8
- A partial system is cancelable if and only if it contains a dendron.The proof uses the nonempty tree set of a system containing a dendron to establish cancellation.Source: §2.2 · p. 10
- A polynomial over partial systems is injective if and only if some positive-degree coefficient contains a dendron.When such a coefficient exists, the proof uses tree and unroll information to show equal polynomial outputs imply equal inputs.Source: §2.2 · p. 10
- Without a dendron in any positive-degree coefficient, the polynomial is non-injective, using either finite-forest inputs or equal-size permutations from.In the finite-forest case, the proof compares C1 + C1 with C2; otherwise it uses permutations of the same size from.Source: §2.2 · p. 10
3 Solving 𝑃(𝑋) = 𝐵for partial systems
This section studies polynomial solving over partial systems, reducing cases with a cyclic coefficient to solving over FDDS and giving a polynomial-time algorithm when all coefficients are finite forests. It also characterizes finite forests that are depth-d unrolls of finite forests and gives a polynomial-time solution when the stated conditions hold.
3 Solving 𝑃(𝑋) = 𝐵for partial systems
- A polynomial-time solver for equations over FDDS yields one for partial-system equations formed by adding finite forests to the polynomial coefficients and target.The target B′ must satisfy 𝖳(B′) = B.Source: §3 · p. 10, §3.1 · p. 11
- A constant term A₀ can be subtracted from both sides when it is a submultiset of B; otherwise, no solution exists.The section therefore proceeds with polynomials without a constant term.Source: §3 · p. 10
3.1 Solving 𝑃(𝑋) = 𝐵when some coefficient has a nonzero total part
- With a cycle-containing coefficient, all solutions have the same finite-forest part, which can be constructed in polynomial time whenever a solution exists.The construction solves equations over truncated partial-system unrolls, including the full-part unrolls, then extracts the finite-forest part.Source: §3.1 · pp. 10–11
3.2 Solving 𝑃(𝑋) = 𝐵when all coefficients are finite forests
- When all coefficients are finite forests, solving 𝑃(𝐗) = 𝐁 takes polynomial time in the combined sizes of the coefficients and target.If a solution exists, the target is also a finite forest.Source: §3.2 · pp. 12, 13, 16
- A depth-at-most-d finite forest F is the depth-d cut of a partial-system unroll exactly when 𝒟(F) is a submultiset of 𝒞_{d−1}(F).Algorithm 3.46 reconstructs a partial system by gluing trees onto matching upper parts, and runs in polynomial time.Source: §3.2 · pp. 14, 16
- For FDDS, the corresponding cut-unroll criterion is the stronger equality 𝒟(F) = 𝒞_{d−1}(F).Source: §3.2 · p. 17
- Algorithm 3.46 solves these equations in (ℙ, +, ×), but not when restricted to (𝔽𝑓, +, ×), because a finite forest may unroll a cyclic partial system without unrolling any forest.A path of depth at least 1 can roll into a fixed point, but is not the unroll of a tree.Source: §3.2 · p. 17
- The gluing graph represents each tree by lower and upper ports joined when labels match; a gluing plan yields a partial-system unroll and is acyclic exactly when the resulting system is a forest.The graph has one vertex per tree in the forest.Source: §3.2 · pp. 17–18
- Realizability holds exactly when upper parts ℋ are a submultiset of lower parts ℬ, some lower labels have excess multiplicity, and every gluing-graph vertex reaches an excess-label vertex.The excess labels are lower-part labels whose multiplicity in ℬ exceeds their multiplicity in ℋ.Source: §3.2 · p. 17
- When the three conditions hold, arc swaps produce an acyclic gluing plan in at most |G|² iterations, giving a polynomial-time construction of a forest solution.The algorithm returns an acyclic gluing plan if and only if one exists.Source: §3.2 · pp. 19–20