FPRD Lab algebra results

Commutative polynomial automata and series

Starting from Problem 25.5, these notes prove an exact algebraic reformulation, give an effective sufficient condition, reconstruct the weighted case, and show why one stronger reduction fails. The general question remains open.

Problem and model

A formal series is a function $f:\Sigma^*\to\mathbb Q$ . It is commutative when its value depends only on the number of occurrences of each input symbol, not their order. The posted question asks whether a polynomial automaton with commutative output always has an equivalent presentation in which every control series is commutative.

We use the Hadamard-automaton presentation from Clemente's 2025 paper. For controls $X_1,\ldots,X_k$ , a letter transition extends to a polynomial-algebra endomorphism, and semantics satisfies

$\delta_a\llbracket\alpha\rrbracket=\llbracket\Delta_a\alpha\rrbracket,\qquad \llbracket\alpha\beta\rrbracket=\llbracket\alpha\rrbracket\odot\llbracket\beta\rrbracket.$

Clemente proves equivalence with polynomial automata up to input reversal: a series is polynomial-automaton recognizable exactly when its reversal is Hadamard-finite. Reversal preserves the Parikh vector, so it also preserves input commutativity.

FPRD-CPA-C02 · proposition

Exact finite-control-algebra equivalence

Call $B$ a finite commutative control algebra when

$B=\mathbb Q[g_1,\ldots,g_m]_{\odot}$ is finitely generated;
$\delta_aB\subseteq B$ for every letter $a$ ; and
every series in $B$ is input-commutative.

Proposition. A commutative polynomial-automaton series $f$ has an equivalent presentation with only commutative control series if and only if $f$ belongs to a finite commutative control algebra.

Proof. If commutative controls $g_1,\ldots,g_m$ are already present, their Hadamard algebra is finitely generated. Transition polynomials make it derivative-stable, and polynomial combinations of commutative series remain commutative.

Conversely, choose finite generators of such an algebra. Express every $\delta_ag_i$ as a polynomial in the generators and use those expressions as the letter transitions. Express the target series as a polynomial in the same generators; add it as the distinguished control if necessary. Evaluation at the empty word supplies the output constants. Reversal transfers the Hadamard presentation back to polynomial automata. ∎

This is an exact reformulation, not a solution: the universal existence of such an algebra is precisely what remains open.

FPRD-CPA-C03 · sufficient condition

Polynomial recovery certificate

For commutative output $f$ , define

$D(f)=\mathbb Q[\delta_uf:u\in\Sigma^*]_{\odot}.$

Proposition. If each control series has an explicit recovery identity

$\llbracket X_i\rrbracket=P_i(\delta_{u_{i1}}f,\ldots,\delta_{u_{it_i}}f),$

then every control series is commutative.

Derivatives preserve commutativity, as do rational linear combinations and Hadamard products. Proposed identities are effectively checkable using the published equality procedure for polynomial/Hadamard automata.

Finite separation of states is weaker. An injective polynomial map need not have a polynomial inverse; for example $t\mapsto(t^2,t^3)$ is injective while $t\notin\mathbb Q[t^2,t^3]$ .

FPRD-CPA-C04 · classical reconstruction

Why the weighted case works

A rational series has a finite-dimensional derivative span. If the output is commutative, choose a basis from its derivatives. Every basis series is commutative and each one-letter derivative is a linear combination of the basis. This constructs the desired weighted automaton directly. The polynomial problem asks whether finite algebraic observability always replaces this finite linear observability.

FPRD-CPA-C05 · counterexample

The factorial derivative algebra need not be finite

Over $\Sigma=\{a,b\}$ , give both letters the same transitions

$X\longmapsto XY,\qquad Y\longmapsto Y+1,\qquad F(X)=F(Y)=1.$

The controls recognise $f(w)=|w|!$ and $g(w)=|w|+1$ , because $\delta_cf=f\odot g$ and $\delta_cg=g+1$ . Both controls are commutative, so this is already a positive presentation.

Counterexample theorem. The derivative Hadamard algebra $D(f)$ is not finitely generated.

Proof sketch with the load-bearing steps. The sequences $f$ and $g$ are algebraically independent: after evaluating a polynomial relation at length $n$ and dividing by the highest factorial power, all lower powers vanish asymptotically, contradicting a nonzero leading polynomial in $n+1$ .

Hence $\mathbb Q[f,g]_{\odot}\cong\mathbb Q[x,y]$ . For a word of length $r$ , $\delta_uf=fP_r(g)$ , where $P_r(y)=y(y+1)\cdots(y+r-1)$ . Thus $D(f)\cong\mathbb Q[xP_r(y):r\ge0]$ . Its degree-one part in $x$ is $x\mathbb Q[y]$ , because the monic rising factorials $P_r$ form a triangular basis of $\mathbb Q[y]$ . If the graded algebra were generated by finitely many elements, replacing those generators by their homogeneous components would still give a finite homogeneous generating set. Its $x$ -degree-one part would then lie in the finite span of the degree-one generators, a contradiction. ∎

The result refutes only the necessity of finite generation of $D(f)$ . The larger algebra $\mathbb Q[f,g]_{\odot}$ is a finite commutative control algebra for the same output. The derivative-algebra failure already occurs over a one-letter alphabet, where input commutativity is automatic; the two-letter presentation is retained because it exercises the nontrivial permutation definition in the originating problem.

Independent finite audit checks the control recurrences, 507 unary and binary derivative identities, and the triangular rising-factorial basis through degree twelve.

Open question

FPRD-CPA-C06 · open

Does every commutative Hadamard-finite series belong to some finitely generated derivative-stable Hadamard algebra contained in the commutative series?

A positive route must construct a finite commutative over-algebra, not necessarily the output's derivative algebra. A negative route needs an invariant of commutative-control presentations and a commutative output that violates it.

Approaches that do not work

Route	Why it fails	Preserved lesson
Generate all output derivatives and invoke Hilbert	Subalgebras of finitely generated algebras need not be finitely generated; the factorial example fails inside the model.	Search for finite commutative over-algebras.
Replace recovery with finite separation	An injective polynomial observation map need not admit polynomial coordinate recovery.	Demand explicit recovery identities.
Cite the 2026 “commutative algebras” result as 25.5	The paper studies commutative product rules and equivalence, not the requested input-order control normalisation.	Keep the two meanings of commutative separate.
Infer commutative controls from commutative output	Hidden or cancelling controls may retain chronology.	Normalisation is the problem; output testing is not.

Sources

Automata Exchange Problem 25.5, contributed by Lorenzo Clemente supplies the exact question and states the weighted case.
Automata Exchange identifies the collection as contributions from the Autobóz community; the Autobóz open-problems page explains that participants present and work on open problems at the annual workshop before agreed problems are made public.
Lorenzo Clemente, “The commutativity problem for effective varieties of formal series, and applications”, 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2025), pp. 804–817, DOI 10.1109/LICS65433.2025.00066; arXiv:2503.21697. It supplies the Hadamard model, Lemma 14's equivalence up to reversal, and decidable equality and commutativity.
Jean Berstel and Christophe Reutenauer, Noncommutative Rational Series with Applications, Chapter 1, Cambridge University Press, 2010, pp. 3–28, DOI 10.1017/CBO9780511760860.002, supplies the classical finite derivative-space characterization used for the weighted case.
Lorenzo Clemente, “Commutative Algebras of Series” , LICS 2026, LIPIcs 380, article 29, pp. 29:1–29:23, DOI 10.4230/LIPIcs.LICS.2026.29, studies commutative product rules and equivalence rather than the input-order normalization asked about in Problem 25.5.