Cascade-free sequences, dispersion index, and state avoidance for stateful digit-wise operations

Daniel Andreas Moj

arxiv: 2604.02542 · v1 · submitted 2026-04-02 · 🧮 math.CO

Cascade-free sequences, dispersion index, and state avoidance for stateful digit-wise operations

Daniel Andreas Moj This is my paper

Pith reviewed 2026-05-13 20:22 UTC · model grok-4.3

classification 🧮 math.CO

keywords cascade-free sequencesGEN/PROP/KILL decompositionChebyshev polynomialsdigit-wise additiondigit-wise doublingdispersion indexstate avoidancetransfer matrix

0 comments

The pith

Cascade-free sequence counts for stateful digit-wise operations depend only on alphabet size N and d = |GEN| · |PROP|, satisfying the recurrence a(L) = N a(L-1) - d a(L-2) and expressible via scaled Chebyshev polynomials.

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

The paper shows that counting sequences without cascades in binary stateful digit-wise operations can be unified under a transfer matrix approach. For operations admitting a GEN/PROP/KILL decomposition, the number of such sequences of length L is fixed by just the base size N and the product d of the generator and propagator cardinalities. This produces the linear recurrence a(L) = N a(L-1) - d a(L-2), whose solution is a scaled Chebyshev polynomial of the second kind. Applications to addition and doubling in base p give closed relations, such as the carry count being p to the L times the doubling count for odd primes, and a Fibonacci link for base-3 doubling. The work also tracks how state dispersion behaves with input distribution and extends the method to larger state spaces by avoiding certain states.

Core claim

For any binary stateful digit-wise operation with a GEN/PROP/KILL decomposition, the number of cascade-free sequences of length L depends on only two parameters, the alphabet size N and d = |GEN| · |PROP|. The count satisfies the recurrence a(L) = N a(L-1) - d a(L-2) and equals a scaled Chebyshev polynomial of the second kind with parameter x = N/(2√d) ≥ 1. This is instantiated for digit-wise addition and doubling, yielding a_carry(L) = p^L a_dbl(L) for odd primes p, and a_dbl(L) = F(2L+2) for p=3.

What carries the argument

The GEN/PROP/KILL decomposition of state transitions, which collapses the transfer matrix dependence to the two scalars N and d = |GEN| · |PROP|.

If this is right

For digit-wise addition and doubling the same recurrence applies, with the exact scaling a_carry(L) = p^L a_dbl(L) when p is an odd prime.
The dispersion index of state occupancy reaches the Poisson value 1 at input mean 1/3 for symmetric generator-killer sizes.
For base 3 the doubling cascade-free count equals the even-indexed Fibonacci numbers.
State avoidance reduces the effective state space dimension to s-1 while the Chebyshev form continues to hold when |S|=3.

Where Pith is reading between the lines

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

This unification may extend to other digit operations such as subtraction or multiplication if they admit analogous decompositions.
The appearance of Chebyshev polynomials suggests possible ties to random walk or orthogonal polynomial enumerations in adjacent combinatorial problems.
The dispersion analysis implies that base-3 arithmetic exhibits Poisson-like state fluctuations at a specific load point.
The finite-L transition point μ*(L) approaching 1/3 could be tested by direct computation for moderate L.

Load-bearing premise

That the state transitions of the digit-wise operation permit a GEN/PROP/KILL decomposition free of extra constraints that would change the two-parameter recurrence.

What would settle it

An explicit binary stateful digit-wise operation with a GEN/PROP/KILL decomposition whose cascade-free sequence counts violate the recurrence a(L) = N a(L-1) - d a(L-2) for some N and d.

read the original abstract

We show that cascade-free counting from carry theory is a special case of a general transfer matrix construction. For any binary stateful digit-wise operation with GEN/PROP/KILL decomposition, the number of cascade-free sequences of length $L$ depends on only two parameters: the alphabet size $N$ and the product $d = |\text{GEN}| \cdot |\text{PROP}|$. The resulting sequence satisfies $a(L) = N a(L-1) - d a(L-2)$ and equals a scaled Chebyshev polynomial of the second kind with coupling parameter $x = N/(2\sqrt{d}) \geq 1$. We instantiate this for digit-wise addition and doubling in base $p$. For odd primes the exact relation $a_{\text{carry}}(L) = p^L a_{\text{dbl}}(L)$ holds. For $p = 3$ the cascade-free doubling count equals the Fibonacci bisection $F(2L+2)$ via $U_L(3/2) = F(2L+2)$ (OEIS A001906); we are not aware of this interpretation in the existing literature. We analyse the dispersion index $D = \text{Var}(\nu)/E[\nu]$ of the state count for uniformly distributed inputs. For symmetric chains ($g = k$) the Poisson transition $D_\infty = 1$ occurs at $\mu = 1/3$, corresponding to base 3 where the Fibonacci bisection appears. The finite Poisson transition point $\mu^*(L)$ decreases strictly to $1/3$ with rate $1/(6L) + O(1/L^2)$. We generalise to state spaces $|S| > 2$ via state avoidance. The restricted transfer matrix has dimension $s-1$; the Chebyshev representation persists for $|S| = 3$.

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.

Desk Editor's Note private letter to a colleague

The paper reduces cascade-free sequence counts to a two-parameter recurrence solved by Chebyshev polynomials, with a clean new link to the Fibonacci bisection in the base-3 doubling case.

read the letter

The key takeaway is that cascade-free sequences for these operations are governed by a recurrence depending only on the alphabet size N and the product d of the GEN and PROP cardinalities, giving a(L) = N a(L-1) - d a(L-2) whose solution is a scaled Chebyshev U polynomial. The paper does a good job laying out the transfer-matrix construction and showing how it specializes to addition and doubling. The base-3 doubling count linking to the Fibonacci bisection F(2L+2) via U_L(3/2) is a nice explicit connection, and they note it's new to the literature. The dispersion index part, with the transition to Poisson at mu=1/3 for symmetric cases, is a solid extension that ties the counting to a probabilistic limit. The math follows straightforwardly once the decomposition is set up, and the circularity is low because the recurrence comes from the matrix rather than data fitting. For the odd-prime case, the exact scaling between carry and doubling counts is presented cleanly. A potential soft spot is the assumption that the transfer matrix entries depend only on the sizes |GEN| and |PROP| without additional restrictions from the specific operation; if digit choices have correlations not captured by those, the recurrence could change. The paper claims it works for the cases considered, but explicit matrix entries for addition would help confirm no hidden constraints. This work is for researchers in combinatorics on words or arithmetic sequence counting who want exact formulas rather than asymptotics. It is worth sending to peer review because the central reduction is transparent and the new identification can be checked directly.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that for any binary stateful digit-wise operation admitting a GEN/PROP/KILL decomposition, the number a(L) of cascade-free sequences of length L depends only on alphabet size N and d = |GEN| · |PROP|, satisfying the recurrence a(L) = N a(L-1) - d a(L-2) whose solution is a scaled Chebyshev polynomial of the second kind with parameter x = N/(2√d) ≥ 1. This framework is instantiated for digit-wise addition and doubling in base p (with a_carry(L) = p^L a_dbl(L) for odd primes and a Fibonacci bisection for p=3 doubling), followed by an analysis of the dispersion index D = Var(ν)/E[ν] of state counts (Poisson transition at μ=1/3 for symmetric cases with finite-L correction 1/(6L) + O(1/L^2)) and a generalization to state avoidance for |S| > 2 that preserves the Chebyshev form for |S|=3.

Significance. If the reduction to a two-parameter recurrence holds, the work supplies a unified closed-form treatment of cascade-free enumeration that connects carry theory to transfer matrices and Chebyshev polynomials, yields exact cross-operation relations such as the p^L scaling for odd primes, and provides a novel Fibonacci identification for base-3 doubling. The dispersion-index asymptotics and the |S|=3 state-avoidance extension are concrete extensions that could be useful in automata and digit-system combinatorics.

major comments (2)

[General construction preceding the instantiations] General transfer-matrix construction: the claim that the recurrence depends only on N and d requires that GEN/PROP/KILL transitions impose no operation-specific digit constraints beyond the two cardinalities; the manuscript must exhibit the explicit 2×2 matrix entries (or transition counts) for addition and for doubling to confirm that the characteristic equation remains exactly r² - N r + d = 0 rather than acquiring extra terms from arithmetic rules such as digit-sum thresholds.
[Instantiations for addition and doubling] Instantiation for addition and doubling in base p: the exact relation a_carry(L) = p^L a_dbl(L) for odd primes and the identification a_dbl(L) = F(2L+2) for p=3 are stated as consequences of the framework, yet the concrete values of |GEN| and |PROP| (hence of d) for these operations are not derived or tabulated, leaving the coefficient matching unverified.

minor comments (2)

[Dispersion index analysis] The dispersion-index finite-L transition point μ*(L) is asserted to decrease as 1/(6L) + O(1/L²); an explicit expansion or a short derivation of the O(1/L²) coefficient would make the asymptotic statement self-contained.
[Closed-form solution] Notation for the scaled Chebyshev polynomial U_L(x) and the coupling x = N/(2√d) is introduced cleanly, but a parenthetical remark confirming that the representation holds for the boundary case x = 1 would aid readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for explicit verification of the transfer-matrix entries and parameter values. We address each major comment below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

Referee: General transfer-matrix construction: the claim that the recurrence depends only on N and d requires that GEN/PROP/KILL transitions impose no operation-specific digit constraints beyond the two cardinalities; the manuscript must exhibit the explicit 2×2 matrix entries (or transition counts) for addition and for doubling to confirm that the characteristic equation remains exactly r² - N r + d = 0 rather than acquiring extra terms from arithmetic rules such as digit-sum thresholds.

Authors: The general construction in Section 2 already proves that any binary stateful operation admitting a GEN/PROP/KILL decomposition yields a transfer matrix whose characteristic equation is exactly r² - N r + d = 0, because the only nonzero off-diagonal contributions are the cardinalities |GEN| and |PROP|. To make this transparent for the referee's concern, we will add the explicit 2×2 matrices (with entries expressed in terms of N and d) for both digit-wise addition and doubling in the revised version. These matrices contain no extra digit-sum thresholds or operation-specific constraints beyond the two cardinalities, confirming the recurrence holds without modification. revision: yes
Referee: Instantiation for addition and doubling in base p: the exact relation a_carry(L) = p^L a_dbl(L) for odd primes and the identification a_dbl(L) = F(2L+2) for p=3 are stated as consequences of the framework, yet the concrete values of |GEN| and |PROP| (hence of d) for these operations are not derived or tabulated, leaving the coefficient matching unverified.

Authors: We will add a short derivation and table in the revised manuscript that computes the explicit values |GEN| = p-1, |PROP| = 1 (hence d = p-1) for addition and the corresponding values for doubling that produce d = 1 when p = 3. These cardinalities directly yield the claimed scaling a_carry(L) = p^L a_dbl(L) for odd primes and the identification U_L(3/2) = F(2L+2) via the Chebyshev representation, thereby verifying the coefficient matching. revision: yes

Circularity Check

0 steps flagged

Transfer-matrix construction yields recurrence independently of specific operation details beyond cardinalities

full rationale

The paper derives the recurrence a(L) = N a(L-1) - d a(L-2) directly from the transfer matrix whose entries are determined solely by the alphabet size N and the product d = |GEN| · |PROP| under the GEN/PROP/KILL decomposition. This is a standard linear algebra step on the adjacency matrix of the state graph and does not rely on fitting to data or self-referential definitions. The Chebyshev polynomial form is the closed-form solution to this recurrence, and the Fibonacci identification for p=3 is an evaluation of that closed form at the specific parameter value. No load-bearing step reduces to a prior result by the same authors or to a tautological renaming; the derivation is self-contained within the transfer-matrix framework.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central construction rests on the standard theory of transfer matrices for counting paths in a finite-state automaton and on the algebraic solution of linear recurrences; no new entities are postulated and the only parameters are the externally supplied alphabet size N and the derived product d.

axioms (2)

domain assumption The state transitions of any binary stateful digit-wise operation admit a GEN/PROP/KILL decomposition whose only relevant cardinalities are |GEN| and |PROP|.
Invoked in the first paragraph to reduce the transfer matrix to dependence on N and d alone.
standard math The characteristic equation of the two-term recurrence yields the Chebyshev polynomial of the second kind after standard rescaling.
Standard closed-form solution for linear homogeneous recurrences with constant coefficients.

pith-pipeline@v0.9.0 · 5641 in / 1673 out tokens · 47382 ms · 2026-05-13T20:22:51.270308+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Biorthogonal eigenvectors of the Holte carry matrix and cascade-free enumeration
math.CO 2026-04 unverdicted novelty 6.0

The Holte matrix has biorthogonal eigenvectors expressed via Stirling numbers, Eulerian polynomials, and symmetric quotient polynomials, with cascade-free avoidance counts being Chebyshev polynomials exactly for k=3 b...

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · cited by 1 Pith paper

[1]

Billingsley,Probability and Measure, 3rd ed., Wiley, New York, 1995

P. Billingsley,Probability and Measure, 3rd ed., Wiley, New York, 1995

work page 1995
[2]

P. L. ˇCebyˇ s¨ ev, Sur les valeurs limites des int´ egrales,J. Math. Pures Appl. (2)19(1874) 157–160

work page
[3]

D. R. Cox, P. A. W. Lewis,The Statistical Analysis of Series of Events, Methuen, London, 1966

work page 1966
[4]

Diaconis, J

P. Diaconis, J. Fulman, Carries, shuffling, and symmetric functions,Adv. in Appl. Math. 43(2009) 176–196.https://doi.org/10.1016/j.aam.2009.02.002 18

work page doi:10.1016/j.aam.2009.02.002 2009
[5]

Diaconis, J

P. Diaconis, J. Fulman, Carries, shuffling, and an amazing matrix,Amer. Math. Monthly 116(2009) 788–803.https://doi.org/10.4169/000298909X474864

work page doi:10.4169/000298909x474864 2009
[6]

Fano, Ionization yield of radiations

U. Fano, Ionization yield of radiations. II. The fluctuations of the number of ions,Phys. Rev.72(1947) 26–29.https://doi.org/10.1103/PhysRev.72.26

work page doi:10.1103/physrev.72.26 1947
[7]

I. P. Goulden, D. M. Jackson, An inversion theorem for cluster decompositions of sequences with distinguished subsequences,J. London Math. Soc. (2)20(1979) 567–576.https: //doi.org/10.1112/jlms/s2-20.3.567

work page doi:10.1112/jlms/s2-20.3.567 1979
[8]

J. M. Holte, Carries, combinatorics, and an amazing matrix,Amer. Math. Monthly104 (1997) 138–149.https://doi.org/10.1080/00029890.1997.11990612

work page doi:10.1080/00029890.1997.11990612 1997
[9]

J. G. Kemeny, J. L. Snell,Finite Markov Chains, Springer, New York, 1976

work page 1976
[10]

Koshy,Fibonacci and Lucas Numbers with Applications, 2nd ed., Wiley, Hoboken, 2018

T. Koshy,Fibonacci and Lucas Numbers with Applications, 2nd ed., Wiley, Hoboken, 2018

work page 2018
[11]

E. E. Kummer, ¨Uber die Erg¨ anzungss¨ atze zu den allgemeinen Reciprocit¨ atsgesetzen,J. reine angew. Math.44(1852) 93–146.https://doi.org/10.1515/crll.1852.44.93

work page doi:10.1515/crll.1852.44.93
[12]

D. Lind, B. Marcus,An Introduction to Symbolic Dynamics and Coding, 2nd ed., Cambridge University Press, Cambridge, 2021

work page 2021
[13]

J. C. Mason, D. C. Handscomb,Chebyshev Polynomials, Chapman & Hall/CRC, Boca Ra- ton, 2003

work page 2003
[14]

Nakano, T

F. Nakano, T. Sadahiro, Carry propagation and the Bernoulli distribution,Integers12 (2012) A38.https://doi.org/10.1515/integers-2012-0038

work page doi:10.1515/integers-2012-0038 2012
[15]

OEIS Foundation, Sequence A001906 (Fibonacci bisectionF(2n)),https://oeis.org/ A001906, 2025 (accessed 23 February 2026)

work page 2025
[16]

OEIS Foundation, Sequence A007070,https://oeis.org/A007070, 2025 (accessed 23 February 2026)

work page 2025
[17]

Ribenboim,The New Book of Prime Number Records, 3rd ed., Springer, New York, 1996

P. Ribenboim,The New Book of Prime Number Records, 3rd ed., Springer, New York, 1996

work page 1996
[18]

T. J. Rivlin,Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory, 2nd ed., Wiley, New York, 1990

work page 1990
[19]

Seneta,Non-negative Matrices and Markov Chains, 2nd ed., Springer, New York, 1981

E. Seneta,Non-negative Matrices and Markov Chains, 2nd ed., Springer, New York, 1981

work page 1981
[20]

R. P. Stanley,Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, Cambridge, 2012

work page 2012
[21]

Vajda,Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover, Mineola, 2008

S. Vajda,Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover, Mineola, 2008. A Verification A.1 Exhaustive verification A.2 The casep= 2 Atp= 2 the binary doubling has no PROP digit (2dis even for alld∈ {0,1}, so 2d̸=p−1 = 1). Algebraically, PROP exists for doubling if and only ifpis odd. The coupling parameters diverge: xc...

work page 2008

[1] [1]

Billingsley,Probability and Measure, 3rd ed., Wiley, New York, 1995

P. Billingsley,Probability and Measure, 3rd ed., Wiley, New York, 1995

work page 1995

[2] [2]

P. L. ˇCebyˇ s¨ ev, Sur les valeurs limites des int´ egrales,J. Math. Pures Appl. (2)19(1874) 157–160

work page

[3] [3]

D. R. Cox, P. A. W. Lewis,The Statistical Analysis of Series of Events, Methuen, London, 1966

work page 1966

[4] [4]

Diaconis, J

P. Diaconis, J. Fulman, Carries, shuffling, and symmetric functions,Adv. in Appl. Math. 43(2009) 176–196.https://doi.org/10.1016/j.aam.2009.02.002 18

work page doi:10.1016/j.aam.2009.02.002 2009

[5] [5]

Diaconis, J

P. Diaconis, J. Fulman, Carries, shuffling, and an amazing matrix,Amer. Math. Monthly 116(2009) 788–803.https://doi.org/10.4169/000298909X474864

work page doi:10.4169/000298909x474864 2009

[6] [6]

Fano, Ionization yield of radiations

U. Fano, Ionization yield of radiations. II. The fluctuations of the number of ions,Phys. Rev.72(1947) 26–29.https://doi.org/10.1103/PhysRev.72.26

work page doi:10.1103/physrev.72.26 1947

[7] [7]

I. P. Goulden, D. M. Jackson, An inversion theorem for cluster decompositions of sequences with distinguished subsequences,J. London Math. Soc. (2)20(1979) 567–576.https: //doi.org/10.1112/jlms/s2-20.3.567

work page doi:10.1112/jlms/s2-20.3.567 1979

[8] [8]

J. M. Holte, Carries, combinatorics, and an amazing matrix,Amer. Math. Monthly104 (1997) 138–149.https://doi.org/10.1080/00029890.1997.11990612

work page doi:10.1080/00029890.1997.11990612 1997

[9] [9]

J. G. Kemeny, J. L. Snell,Finite Markov Chains, Springer, New York, 1976

work page 1976

[10] [10]

Koshy,Fibonacci and Lucas Numbers with Applications, 2nd ed., Wiley, Hoboken, 2018

T. Koshy,Fibonacci and Lucas Numbers with Applications, 2nd ed., Wiley, Hoboken, 2018

work page 2018

[11] [11]

E. E. Kummer, ¨Uber die Erg¨ anzungss¨ atze zu den allgemeinen Reciprocit¨ atsgesetzen,J. reine angew. Math.44(1852) 93–146.https://doi.org/10.1515/crll.1852.44.93

work page doi:10.1515/crll.1852.44.93

[12] [12]

D. Lind, B. Marcus,An Introduction to Symbolic Dynamics and Coding, 2nd ed., Cambridge University Press, Cambridge, 2021

work page 2021

[13] [13]

J. C. Mason, D. C. Handscomb,Chebyshev Polynomials, Chapman & Hall/CRC, Boca Ra- ton, 2003

work page 2003

[14] [14]

Nakano, T

F. Nakano, T. Sadahiro, Carry propagation and the Bernoulli distribution,Integers12 (2012) A38.https://doi.org/10.1515/integers-2012-0038

work page doi:10.1515/integers-2012-0038 2012

[15] [15]

OEIS Foundation, Sequence A001906 (Fibonacci bisectionF(2n)),https://oeis.org/ A001906, 2025 (accessed 23 February 2026)

work page 2025

[16] [16]

OEIS Foundation, Sequence A007070,https://oeis.org/A007070, 2025 (accessed 23 February 2026)

work page 2025

[17] [17]

Ribenboim,The New Book of Prime Number Records, 3rd ed., Springer, New York, 1996

P. Ribenboim,The New Book of Prime Number Records, 3rd ed., Springer, New York, 1996

work page 1996

[18] [18]

T. J. Rivlin,Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory, 2nd ed., Wiley, New York, 1990

work page 1990

[19] [19]

Seneta,Non-negative Matrices and Markov Chains, 2nd ed., Springer, New York, 1981

E. Seneta,Non-negative Matrices and Markov Chains, 2nd ed., Springer, New York, 1981

work page 1981

[20] [20]

R. P. Stanley,Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, Cambridge, 2012

work page 2012

[21] [21]

Vajda,Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover, Mineola, 2008

S. Vajda,Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover, Mineola, 2008. A Verification A.1 Exhaustive verification A.2 The casep= 2 Atp= 2 the binary doubling has no PROP digit (2dis even for alld∈ {0,1}, so 2d̸=p−1 = 1). Algebraically, PROP exists for doubling if and only ifpis odd. The coupling parameters diverge: xc...

work page 2008