pith. sign in

arxiv: 2502.02360 · v1 · submitted 2025-02-04 · 💻 cs.DM · math.DS

Injectivity of polynomials over finite discrete dynamical systems

Antonio E. Porreca , Marius Rolland This is my paper

Pith reviewed 2026-05-23 04:10 UTC · model grok-4.3

classification 💻 cs.DM math.DS
keywords injectivitypolynomialsfinite discrete systemsdynamical systemscoefficient characterizationpolynomial-time algorithmequation solving
0
0 comments X

The pith

Univariate polynomials are injective over finite sets if and only if their coefficients follow a specific form, which also yields a polynomial-time algorithm for solving the equations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper aims to characterize when univariate polynomials are injective as functions over finite discrete sets in the context of modeling dynamical systems. The decomposition of dynamics using sum for alternative execution and product for synchronous execution leads to polynomial equations, and the focus is on ensuring injectivity for these to represent valid behaviors. A reader would care if they want to analyze or design systems in biology or physics by breaking them into simpler algebraic components. The result provides both a coefficient-based test and an efficient algorithm.

Core claim

We focus on univariate, injective polynomials, giving a characterization in terms of the form of their coefficients and a polynomial-time algorithm for solving the associated equations.

What carries the argument

Characterization of injectivity via the form of coefficients for univariate polynomials over finite sets.

If this is right

  • The injectivity property can be verified directly from the coefficients without evaluating the polynomial at all points.
  • The equations arising from desired behaviors can be solved efficiently.
  • Complex dynamical systems can be decomposed into simpler subsystems while preserving injectivity.
  • Analysis of observable phenomena can be simplified using this algebraic approach.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This could be extended to design systems with specific dynamical properties by solving for coefficients.
  • Similar characterizations might apply to other operations or multivariate polynomials in system modeling.
  • The algorithm could be implemented to automate parts of dynamical system design in engineering contexts.

Load-bearing premise

That alternative and synchronous executions correspond exactly to the sum and product of the polynomials in the model.

What would settle it

An explicit univariate polynomial over a small finite set whose injectivity does not match the predicted coefficient form.

Figures

Figures reproduced from arXiv: 2502.02360 by Antonio E. Porreca, Marius Rolland.

Figure 1
Figure 1. Figure 1: An FDDS A with two connected components (on the left), a finite portion of its unroll U(A) (on the right) and the cut C(U(A), 4) (below the dashed line). A few vertex names are shown in order to highlight their contribution to the unroll. In this semiring, the structure of the product is particularly rich. For example, the semiring is not factorial, i.e., there exist irreducible FDDS A, B, C, D such that A… view at source ↗
Figure 2
Figure 2. Figure 2: The levelwise product of two finite trees. Remark how the depth of the result is given by the minimum depth of the two factors. with vertices V = {(u, v) ∈ V1 × V2 | depth(u) = depth(v)}, where depth(u) is the length of the shortest path between u and the root of its tree, and edges E = {((u, u′ ),(v, v′ )) | (u, v) ∈ E1,(u ′ , v′ ) ∈ E2} ⊆ V 2 (see [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A run of the algorithm for polynomial equations over forests of finite trees [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
read the original abstract

The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviors and, conversely, starting from a desired behavior allows the design of objects exhibiting that behavior in engineering. The decomposition of dynamics into simpler subsystems allows us to simplify this analysis (or design). Here we focus on an algebraic approach to decomposition, based on alternative and synchronous execution as the sum and product operations; this gives rise to polynomial equations (with a constant side). In this article we focus on univariate, injective polynomials, giving a characterization in terms of the form of their coefficients and a polynomial-time algorithm for solving the associated equations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops an algebraic model of finite discrete dynamical systems in which alternative execution is modeled by polynomial sum and synchronous execution by polynomial product, yielding constant-right-hand-side polynomial equations. It specializes to the univariate case and claims a coefficient-based characterization of injectivity together with a polynomial-time algorithm for solving the resulting equations.

Significance. If the coefficient characterization and the claimed polynomial-time algorithm are correct, the work supplies a concrete, algorithmic tool for decomposing and solving equations that arise in the chosen sum-product model of dynamics. This could be useful for analysis or synthesis tasks in discrete dynamical systems, particularly when the modeling framework is accepted.

major comments (2)
  1. [Abstract / §3] The abstract states a characterization 'in terms of the form of their coefficients' but the manuscript provides neither the explicit coefficient conditions nor the proof that these conditions are necessary and sufficient for injectivity over the finite domain; without these the central claim cannot be verified.
  2. [Abstract / §4] No description or complexity analysis of the 'polynomial-time algorithm' is supplied; it is therefore impossible to confirm that the algorithm runs in polynomial time or correctly decides the injectivity equations.
minor comments (2)
  1. [Introduction] The modeling choice (sum = alternative, product = synchronous) is presented without comparison to other standard algebraic or automata-theoretic decompositions; a brief discussion would clarify the framework's scope.
  2. [Preliminaries] Notation for the finite discrete domain and the precise ring or field over which the polynomials are defined should be introduced explicitly at the first use.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their review and for highlighting issues of clarity in the presentation of our main results. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract / §3] The abstract states a characterization 'in terms of the form of their coefficients' but the manuscript provides neither the explicit coefficient conditions nor the proof that these conditions are necessary and sufficient for injectivity over the finite domain; without these the central claim cannot be verified.

    Authors: We agree that the explicit coefficient conditions and the accompanying necessity/sufficiency proof were not stated with sufficient prominence or detail. In the revised manuscript we will add an explicit listing of the coefficient conditions in Section 3 together with a complete, self-contained proof that these conditions are necessary and sufficient for injectivity over the finite domain. revision: yes

  2. Referee: [Abstract / §4] No description or complexity analysis of the 'polynomial-time algorithm' is supplied; it is therefore impossible to confirm that the algorithm runs in polynomial time or correctly decides the injectivity equations.

    Authors: We concur that the algorithm description and its complexity analysis were omitted or insufficiently developed. The revised version will contain a full description of the algorithm in Section 4, including a rigorous argument establishing that it runs in polynomial time and correctly decides the injectivity equations. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives a coefficient-form characterization of univariate injective polynomials together with a polynomial-time solver for the associated equations inside an explicit algebraic model (sum for alternative execution, product for synchronous execution). No load-bearing step reduces by definition or construction to its own inputs, no fitted parameter is relabeled as a prediction, and no uniqueness claim rests on a self-citation chain. The framework is stated as a modeling choice rather than derived from the target result, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, background axioms, or new entities.

pith-pipeline@v0.9.0 · 5625 in / 909 out tokens · 44423 ms · 2026-05-23T04:10:57.974100+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Introduction to random boolean networks

    Carlos Gershenson. Introduction to random boolean networks. arXiv e-prints , 2004

    work page 2004

  2. [2]

    Neural and Automata Networks: Dynamical Behavior and Applications

    Eric Goles and Servet Mart` ınez. Neural and Automata Networks: Dynamical Behavior and Applications . Kluwer Academic Publishers, 1990

    work page 1990

  3. [3]

    Biological Feedback

    Ren´ e Thomas and Richard D’Ari. Biological Feedback. CRC Press, 1990

    work page 1990

  4. [4]

    Boolean formalization of genetic control circuits

    Ren´ e Thomas. Boolean formalization of genetic control circuits. Journal of Theoretical Biology, 42(3):563–585, 1973

    work page 1973

  5. [5]

    Modeling in computational biology and biomedicine

    Gilles Bernot, Jean-Paul Comet, Adrien Richard, Madalena Chaves, Jean-Luc Gouz´ e, and Fr´ ed´ eric Dayan. Modeling in computational biology and biomedicine. In Modeling and Analysis of Gene Regulatory Networks: A Multidisciplinary Endeavor , pages 47–80. Springer, 2012

    work page 2012

  6. [6]

    Reaction systems

    Andrzej Ehrenfeucht and Grzegorz Rozenberg. Reaction systems. Fundamenta Informaticae, 75:263–280, 2007

    work page 2007

  7. [7]

    Graph-theoretical constructions for graph entropy and network coding based communications

    Maximilien Gadouleau and Soren Riis. Graph-theoretical constructions for graph entropy and network coding based communications. IEEE Transactions on Infor- mation Theory, 57(10):6703–6717, 2011

    work page 2011

  8. [8]

    Alberto Dennunzio, Valentina Dorigatti, Enrico Formenti, Luca Manzoni, and Antonio E. Porreca. Polynomial equations over finite, discrete-time dynamical systems. In Cellular Automata, 13th International Conference on Cellular Automata for Research and Industry, ACRI 2018 , volume 11115 of Lecture Notes in Computer Science, pages 298–306. Springer, 2018

    work page 2018

  9. [9]

    Linear time algorithm for isomorphism of planar graphs (preliminary report)

    John E Hopcroft and Jin-Kue Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the sixth annual ACM symposium on Theory of computing , pages 172–184, 1974

    work page 1974

  10. [10]

    Factorisation in the semiring of finite dynamical systems

    ´Emile Naquin and Maximilien Gadouleau. Factorisation in the semiring of finite dynamical systems. Theoretical Computer Science, 998:114509, 2024

    work page 2024

  11. [11]

    Porreca, Sara Riva, and Marius Rolland

    Fran¸ cois Dor´ e, Kevin Perrot, Antonio E. Porreca, Sara Riva, and Marius Rolland. Roots in the semiring of finite deterministic dynamical systems. arXiv e-prints ,

    work page

  12. [12]

    https://arxiv.org/abs/2405.09236

    work page arXiv

  13. [13]

    Handbook of Product Graphs

    Richard Hammack, Wilfried Imrich, and Sandi Klavˇ zar. Handbook of Product Graphs. Discrete Mathematics and Its Applications. CRC Press, second edition, 2011

    work page 2011

  14. [14]

    An algo- rithmic pipeline for solving equations over discrete dynamical systems modelling hypothesis on real phenomena

    Alberto Dennunzio, Enrico Formenti, Luciano Margara, and Sara Riva. An algo- rithmic pipeline for solving equations over discrete dynamical systems modelling hypothesis on real phenomena. Journal of Computational Science , 66:101932, 2023

    work page 2023

  15. [15]

    Antonio E. Porreca. Composing behaviours in the semiring of dynamical systems. In International Workshop on Boolean Networks (IWBN 2020) , 2020. Invited talk, https://doi.org/10.5281/zenodo.3934396

    work page doi:10.5281/zenodo.3934396 2020