CS Paper Radar

Discrete-time polynomial systems with inputs and outputs: structure, reachability, observability, and minimal realizations

Eduardo D. Sontag

eess.SY math.OC ·submitted 2026-09-29 00:29 UTC · v1

Abstract

We study the realization problem for discrete-time input/output polynomial systems. These are formalized using tools from commutative algebra and algebraic geometry as systems whose state spaces are algebraic varieties, or more abstractly the set of k-points of an affine k-scheme, where k is an arbitrary infinite field. The input/output behaviors of such systems are described by "polynomial response maps" in which outputs are polynomial functions of past inputs. The main results show that every polynomial response map admits a canonical (quasi-reachable and algebraically observable) realization, which is unique up to isomorphism. The key to the approach is to linearize dynamics by considering a "dual" system in which states are functions defined on states. Finite dimensionality of the canonical realization, and its polynomiality, are characterized in terms of the space, algebra, and field of observables of the map, as well as in terms of algebraic input/output difference equations, and by a Jacobian rank criterion. A particular subclass consists of the maps that we call "bounded," defined by the property that their degree in the past inputs is uniformly bounded. Bounded maps are shown to be finitely realizable if and only if they are realizable by finite-dimensional state-affine systems, whose theory in turn reduces to that of rational formal power series. We also study the lattice of quasi-reachable realizations of a given map, including normal realizations. This work is an update of the PhD thesis written by the author in 1976; connections to recent work are briefly discussed in the last section.

Closest papers

Nearest neighbours by meaning across the whole index.

Controllability of polynomial systems is undecidable and not recursively enumerable

cs.CC math.OCeess.SY ·2026-10-19 ·Jun Liu, Ivan O. Shevchenko
theory similarity 0.64
Abstract

Sontag conjectured in 1988 that global controllability of polynomial control systems with rational coefficients is undecidable, but that the controllable systems form a recursively enumerable set. We prove the first part of the conjecture and disprove the second. For every homogeneous polynomial vector field $F$ of odd degree with rational coefficients, we construct an explicit polynomial control system $Σ_F$, with one more state than $F$, that is globally controllable if and only if the origin is \emph{not} globally asymptotically stable for $\dot x=F(x)$. By a recent result, the homogeneous polynomial vector fields with a globally asymptotically stable origin form a set that is recursively enumerable but not decidable. Consequently, global controllability of polynomial systems is undecidable, and the controllable polynomial systems are not recursively enumerable. The same conclusions hold for systems of the form $\dotξ=f(ξ)+Bu$ with a polynomial drift and a constant input matrix.

0.27

Approximate Polynomial Satisfiability is in the Counting Hierarchy

cs.CC ·2026-09-30 ·Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
theory similarity 0.61
Abstract

The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.

0.53

Solving polynomial equations over partial discrete dynamical systems

cs.DM ·2026-09-30 ·Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge
similarity 0.59
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.

0.34

PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems

cs.CC ·2026-10-19 ·Manon Blanc
theory similarity 0.59
Abstract

Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.

0.29

New bounds for the support of input-output equations in differential-algebraic systems

cs.SC math.AG ·2026-09-03 ·Gabriela Jeronimo, Leonardo Lanciano
theory similarity 0.57
Abstract · 26 pages

Given a polynomial dynamical system $\mathbf{x}'=\mathbf{f}(\mathbf{x},\mathbf{u})$ together with an observation function $y=g(\mathbf{x},\mathbf{u})$, where $\mathbf{x}=(x_1,\ldots,x_n)$, $\mathbf{u}=(u_1,\ldots,u_m)$ and $y$ are differential variables, and $\mathbf{f}=(f_1,\ldots,f_n)$, $g$ are polynomials with coefficients in a differential field, we study the problem of determining a minimal polynomial differential equation satisfied by the inputs $\mathbf{u}$ and the output $y$ which follows as a differential consequence of the system. We provide a characterization of a finite superset of the set of monomials appearing with non-zero coefficients in this input-output equation. Specifically, we establish an upper bound for the degree of the minimal polynomial and a family of inequalities that define a polytope containing its Newton polytope. These results extend recent work by Mukhina and Pogudin for systems with constant parameters, and enable the use of evaluation-interpolation techniques for the efficient computation of such eliminant polynomials.

0.30

On Lie-Algebraic Conditions for Finite-Dimensional Koopman Bilinear Embeddings of Control-Affine Systems

eess.SY math.OC ·2026-11-16 ·Natsuki Katayama, Yoshihiko Susuki
similarity 0.57
Abstract · 8 pages, 0 figure

Koopman bilinear representations for control-affine systems have attracted considerable attention. In this paper, we investigate, from a Lie-algebraic perspective, conditions under which a control-affine system admits a finite-dimensional Koopman bilinear embedding. Specifically, we focus on the Lie algebra generated by the drift and control vector fields. First, we show that the finite-dimensionality of the generated Lie algebra is a necessary condition for the existence of a Koopman bilinear embedding. Next, when the generated Lie algebra contains a nonzero nilpotent ideal, we derive a sufficient condition for the existence of such an embedding. Finally, through an example of a quadratic polynomial system, we demonstrate that the finite-dimensionality of the generated Lie algebra imposes strong restrictions on the vector fields, suggesting that exact finite-dimensional Koopman bilinear embeddings may be nongeneric.

0.31

A Model-Theoretic Formalization of AlKhwaremis ilm alfaraid

cs.LO cs.CL ·2026-10-24 ·Elnaserledinellah Mahmoud Abdelwahab
similarity 0.57
Abstract · 27 pages, 1 figure

This paper presents a model theoretic and computational formalization of AlKhwarizmis treatment of inheritance within the framework of Computational Fiqh. We first show that every inheritance configuration in a specified class is representable as a finite system of rational linear equalities and inequalities, and that such systems are decided exactly by Fourier Motzkin elimination over Q. We then define the fixed dimensional inheritance structure Vd with distinguished claimant coordinates, and prove that every admissible rational linear coordinate realization is isomorphic to Vd, this establishes the algebraic representation as canonical within that class. The complete first order theory Td of Vd is shown to be complete by construction and is explicitly distinguished from the decidability of the inheritance relevant fragment. The methodological principle is then related to a broader formalization of closed Fiqh domains via exhaustive case generation, Horn clause axiomatization, and terminating deduction, yielding domain relative computational completeness.

0.26

Hitting sets From Derivations: Waring Rank and Noncommutative ABPs

cs.CC ·2026-09-28 ·Shubham Bhardwaj, Foram Lakhani, Partha Mukhopadhyay, Ramprasad Saptharishi, Pratik Shastri +1 more
similarity 0.56
Abstract

We give an explicit hitting set of size $\operatorname{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero (or large enough). In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. The proof extends to the setting of noncommutative ABPs and provides a polynomial sized hitting set (of matrices) for the class of noncommututive polynomials that can be computed by polynomial sized noncommutative ABPs (this was also one of the results reported by Open AI~\cite{OpenAI26} in their release on 6 Oct 2026). The main technical insight is the construction of a ``formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura \cite{Moura_2004} in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: A subset of the stewards obtained a weaker statement (hitting sets for polynomials with bounded partial derivative space) during conversations \cite{astra_proof} with OpenAI GPT-6 Astra. Extensions of this idea to the broader class of noncommutative ABPs were obtained by the other stewards (via further conversations with Astra), prior to OpenAI's dump on 6 Oct 2026. The proofs presented in this writeup is a rewriting (in the authors' words) of the proofs for both settings obtained by the models in a form that we believe is understandable to researchers. Although the proof is technically identical to OpenAI's release, we believe this exposition is self-contained, simpler, and more valuable to the community. The absurdity of the situation is not lost on us.

0.56