Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.02542 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917382410207232 |
|---|---|
| author | Moj, Daniel Andreas |
| author_facet | Moj, Daniel Andreas |
| contents | 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}(ν)/E[ν]$ of the state count for uniformly distributed inputs. For symmetric chains ($g = k$) the Poisson transition $D_\infty = 1$ occurs at $μ= 1/3$, corresponding to base 3 where the Fibonacci bisection appears. The finite Poisson transition point $μ^*(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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02542 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Cascade-free sequences, dispersion index, and state avoidance for stateful digit-wise operations Moj, Daniel Andreas Combinatorics 11A63, 05A15 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}(ν)/E[ν]$ of the state count for uniformly distributed inputs. For symmetric chains ($g = k$) the Poisson transition $D_\infty = 1$ occurs at $μ= 1/3$, corresponding to base 3 where the Fibonacci bisection appears. The finite Poisson transition point $μ^*(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$. |
| title | Cascade-free sequences, dispersion index, and state avoidance for stateful digit-wise operations |
| topic | Combinatorics 11A63, 05A15 |
| url | https://arxiv.org/abs/2604.02542 |