Rational series

Relative degree for rational series

Relative degree asks how long a rational series is forced to stay inside an initial $a$ -corridor before a $b$ -transition can become nonzero. A finite reachable continuation space turns that infinite-language condition into exact linear algebra.

FPRD-RS-D01 · definition

Problem and input model

The posted problem fixes the binary alphabet $\Sigma=\{a,b\}$ . Let $f:\Sigma^*\to\mathbb Q$ be represented by rational matrices and vectors

$f(w)=\lambda M_w\gamma,\qquad M_{uv}=M_uM_v.$

Write $A=M_a$ and $B=M_b$ . A relative degree is an integer $r\ge0$ such that

$\operatorname{supp}(f)\subseteq a^r\Sigma^*\qquad\text{and}\qquad f(a^rb)\ne0.$

The algorithm below takes the linear representation itself as input. Converting another description of a rational series into that representation is a separate computational cost.

No shorter prefix may stop or turn through $b$ , while the boundary word $a^rb$ must be visible. If degree zero is permitted, support containment is vacuous and only $f(b)\ne0$ remains.

Worked example

The dimension bound can be sharp

Take

$\lambda=(1,0),\qquad \gamma=\binom01,\qquad A=\begin{pmatrix}0&1\\0&1\end{pmatrix},\qquad B=\begin{pmatrix}0&0\\0&1\end{pmatrix}.$

This is the characteristic series of $a\Sigma^*$ : the first $a$ enters an accepting state, and both letters then preserve it. Its relative degree is $r=1$ . The representation has $d=2$ , so the strict bound $r<d$ cannot be improved uniformly.

FPRD-RS-L01 · lemma

A finite safe-row criterion

Compute the reachable column space

$V=\operatorname{span}\{M_x\gamma:x\in\Sigma^*\}.$

It is the least subspace containing $\gamma$ and invariant under every letter matrix. Define the safe row space

$W=\{p:p\gamma=0\text{ and }pBv=0\text{ for every }v\in V\}.$

This is a finite summary of all continuations. Every possible suffix contributes a column in $V$ ; a row belongs to $W$ exactly when stopping there and every continuation after taking $b$ are all invisible.

Lemma. The support condition $\operatorname{supp}(f)\subseteq a^r\Sigma^*$ holds exactly when $\lambda A^k\in W$ for every $0\le k<r$ .

Proof. For a row $p=\lambda A^k$ , the equation $p\gamma=0$ excludes the word $a^k$ . The condition $pBV=0$ excludes every word whose first deviation at that position is $b$ , because every remaining suffix contributes a vector in $V$ . These are precisely the forbidden words under the two-letter convention of the problem. The same argument read backwards proves the converse. ∎

FPRD-RS-T01 · theorem

The relative degree is below the dimension

Theorem. If a $d$ -dimensional representation has a relative degree, then $r<d$ .

Proof. Put $v_k=\lambda A^k$ . The lemma gives $v_0,\ldots,v_{r-1}\in W$ , whereas $v_rB\gamma=f(a^rb)\ne0$ implies $v_r\notin W$ . If a first linear dependence occurred at an index $j\le r$ , the $A$ -stable Krylov span generated by $v_0,\ldots,v_{j-1}$ would contain every later row, including $v_r$ . All its generators lie in the linear space $W$ , a contradiction. Thus $v_0,\ldots,v_r$ are independent and $r+1\le d$ . ∎

FPRD-RS-T02 · algorithm

A polynomial-time decision procedure

Compute a column basis $C$ of $V$ by invariant-space saturation.
Initialize $v=\lambda$ and mark every earlier row safe.
For $r=0,\ldots,d-1$ , return $r$ exactly when all earlier rows were safe and $vB\gamma\ne0$ .
Before advancing to $vA$ , update safety by testing $v\gamma=0$ and $vBC=0$ .

The lemma proves the support test and the dimension theorem proves that the search is complete. Exact rational linear algebra gives deterministic polynomial time in the bit size of the supplied representation.

Uniqueness

Two different degrees cannot satisfy the definition. If $r<s$ , the support condition for $s$ forces $f(a^rb)=0$ , contradicting the witness condition for $r$ .

Reported finite corroboration

The originating run artifact reports 100,000 exact-arithmetic random representations of dimensions one through four, with no mismatch between the algorithm and direct residual-zeroness tests. The checker and certificate are absent from the available durable and public record. This is therefore a reported computational finding, not reproducible evidence used to mature the theorem. The proof above carries the result.

FPRD-RS-C03 · exhaustive finite certificate

A reproducible replacement for the missing experiment

A new exact checker enumerates every one- and two-dimensional representation whose entries lie in $\{-1,0,1\}$ . For each representation it compares the Krylov algorithm with a separate definition-level oracle that tests every candidate $r<d$ and every suffix word of length below $d$ .

Dimension	Representations	Degree 0	Degree 1
1	81	24	—
2	531,441	290,304	5,568

Across all 531,522 representations there are no mismatches and no nonunique candidate sets. This is a complete result only for the displayed finite domain; the proof remains responsible for arbitrary dimension and rational input.

Checker · Certificate

Scope and sources

The alphabet is exactly $\{a,b\}$ , as in the posted problem.
The polynomial-time claim is for an explicit rational linear representation.
The representation dimension is a positive integer; minimality is not assumed.
The convention here allows degree zero.

The binary hypothesis is essential to the displayed formula for $W$ . Over $\{a,b,c\}$ , take $\lambda=(1,0)$ , $\gamma=(0,1)^{\mathsf T}$ , $A=C=\bigl(\begin{smallmatrix}0&1\\0&0\end{smallmatrix}\bigr)$ , and $B=\bigl(\begin{smallmatrix}0&0\\0&1\end{smallmatrix}\bigr)$ . Then the $B$ -only safety test passes below degree one and $f(ab)=1$ , but $f(c)=1$ . For a larger alphabet, the definition of $W$ must include one annihilation condition for every letter other than $a$ .

Problem source. Relative degree for rational series, contributed by Lorenzo Clemente to Automata Exchange on 1 July 2025. The standard equivalence between rational series, recognizable series, linear representations, and weighted automata is described by Jean Berstel and Christophe Reutenauer in Noncommutative Rational Series with Applications, Chapter 1, Cambridge University Press (2010), pp. 3–28, DOI 10.1017/CBO9780511760860.002. The FPRD derivation is preserved in fprd-automata-exchange-run-003-relative-degree-rational-series-2026-08-25.md.

Independent hostile audit · Audit output