Finite-Orbit Circulant State Core
Implementation & benchmark of arXiv:2607.13442 — Periodicities in the Riordan arrays of polynomials over finite fields
Source paper: Periodicities in the Riordan arrays of polynomials over finite fields arXiv:2607.13442 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace the linear state transition in a small recurrent or state-space module by a circulant matrix acting on a vector over a finite field. The hidden state then has only finitely many possible values and follows an exactly periodic orbit after at most \(q^n\) states, eliminating numerical drift on modular-counting and symbolic-memory tasks. A learned real-valued encoder and decoder can surround the discrete core, while the transition itself is fixed, searched, or trained with a straight-through estimator.
Formulas
Mathematical statement
The paper reduces the periodic block sequence to \(C_k=A^kC_0\), where \(C_0\in\mathbb{F}_q^n\) is the initial periodic coefficient block and \(A=\operatorname{circ}(\vec v_3)\in\mathbb{F}_q^{n\times n}\) is the circulant matrix generated by the coefficient vector \(\vec v_3=(a_0,\ldots,a_{n-1})\) of \(p_3(t)=\sum_{j=0}^{n-1}a_jt^j\). The orbit is \({\cal O}=\{A^kC_0\mid k\in\mathbb{N}_0\}\). Because \(\mathbb{F}_q^n\) is finite, there exist \(0\leq\mu<\nu\leq q^n\) such that \(C_{k+\nu-\mu}=C_k\) for every \(k\geq\mu\); if \(A\) is invertible, the orbit is purely periodic with \(\mu=0\). The neural adaptation uses the recurrence \(s_{k+1}=As_k\pmod q\), optionally with input injection \(Bs_k\) replaced by \(Bu_k\pmod q\).
Implementation notes
(1) Integration point: implement a recurrent/state-space block between an input projection and an output projection. For each sequence input \(u_k\in\mathbb{R}^{d_u}\), maintain a discrete state \(s_k\in\{0,\ldots,q-1\}^n\), and decode it with a learned embedding table or an MLP applied to \([u_k,\operatorname{onehot}(s_k)]\). Use a fixed circulant \(A\) and optional input matrix \(B\). Start with \(q=2,3,5\) and \(n=8\) or \(16\). (2) Pseudocode: initialize s=s0; for each timestep k, compute z=sigmoid(Wu @ u[k] + bu), r=round((q-1)*z) mod q, update s=(A @ s + B @ r) % q, and produce h[k]=readout(concat(u[k],embed(s))). Construct \(A\) from a short coefficient vector \(a\) by cyclically shifting \(a\) across rows, exactly implementing \(A=\operatorname{circ}(\vec v_3)\). During backpropagation use a straight-through estimator for rounding, or initially freeze \(A\) and train only the encoder, decoder, and \(B\). (3) Compute from the paper's mathematics: the modular recurrence, circulant parameter sharing, and finite-orbit guarantee. Empirically estimate the transient \(\mu\) and period \(\ell=\nu-\mu\) by storing visited states until a repeat occurs, and verify \(\ell+\mu\leq q^n\). Search random generators \(a\) and retain matrices with long periods or task-appropriate periods. (4) First experiment: train a tiny sequence model on parity, modular addition, delayed-copy, and periodic-symbol tasks with lengths 128--4096. Compare against a GRU and a diagonal linear state-space model at matched state size and FLOPs. Measure exact accuracy versus sequence length, transition drift, training stability, and inference throughput. Success means near-perfect long-range modular accuracy beyond the training horizon, no numerical degradation at large sequence lengths, and lower recurrent-state memory; failure would be rapid orbit collapse, inadequate state diversity, or optimization instability from the discrete encoder.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.