Biorthogonal eigenvectors of the Holte carry matrix and cascade-free enumeration

Daniel Andreas Moj

arxiv: 2604.04591 · v1 · submitted 2026-04-06 · 🧮 math.CO

Biorthogonal eigenvectors of the Holte carry matrix and cascade-free enumeration

Daniel Andreas Moj This is my paper

Pith reviewed 2026-05-10 19:34 UTC · model grok-4.3

classification 🧮 math.CO

keywords Holte matrixbiorthogonal eigenvectorscarry processesStirling numbersEulerian polynomialsChebyshev polynomialscascade-free additionMarkov chains

0 comments

The pith

Explicit formulas for the left and right eigenvectors of the Holte carry matrix reveal that cascade-free addition counts take Chebyshev form exactly for three summands.

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

The paper derives the full biorthogonal eigenvector system for the Holte transition matrix that governs carries during k-summand base-N addition. Left eigenvectors factor through unsigned Stirling numbers of the first kind and Eulerian polynomials; right eigenvectors are expressed via quotient polynomials that exhibit palindrome symmetry and approach simple powers in the large-k limit. These closed forms let the authors compute the number of cascade-free addition sequences and prove that this count follows a scaled Chebyshev recurrence of the second kind precisely when the restricted state space has dimension at most 2. The result is sharp: the recurrence holds for three summands but fails for four or more summands. A reader would care because the formulas convert an enumerative problem in positional arithmetic into concrete polynomial identities.

Core claim

For the Holte carry matrix T of k-summand base-N addition the complete biorthogonal system is constructed explicitly. The left eigenvectors satisfy sum_i u_j[i] x^i = c_{k,j} (x-1)^j A_{k-j}(x) where c_{k,j} = |s(k,k-j)|/k! and A_n(x) is the Eulerian polynomial. The right eigenvectors obey sum_i binom(k-1,i) v_j[i] x^i = (1+x)^{k-1-j} Q_j(x), with the quotient polynomials Q_j obeying the palindrome relation x^j Q_j(1/x) = (-1)^j Q_j(x) and converging to (1-x)^j as k grows; closed expressions for Q_j are supplied when j <= 3. The cascade-free avoidance count a(L) equals (sqrt(d))^L U_L(x) for every restricted transfer matrix of dimension d <= 2. This Chebyshev form is shown to be sharp: it is

What carries the argument

The biorthogonal eigenvector system of the Holte carry matrix T together with the restricted transfer matrices on cascade-free states, whose characteristic polynomials are obtained by Stirling-weighted Lagrange interpolation at the eigenvalues N^{-j}.

If this is right

The cascade-free count a(L) admits an exact closed form via the Chebyshev polynomial of the second kind precisely when three summands are added.
The characteristic polynomial of any restricted transfer matrix is given in closed form by Stirling-weighted Lagrange interpolation at the points N^{-j}.
Two binary carry systems are shadow-equivalent if and only if they share the same pair (N,d).
Classification of all k-state carry systems reduces to determining the characteristic polynomial of the Holte matrix T.

Where Pith is reading between the lines

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

The same eigenvector factorizations may supply exact generating functions for other statistics on carry sequences beyond the cascade-free case.
For k greater than or equal to 4 the growth of a(L) is still governed by the largest eigenvalue of the restricted matrix, yet the full recurrence structure changes and may involve other families of orthogonal polynomials.
Shadow equivalence supplies a way to translate avoidance problems between different bases or state dimensions without altering the sequence a(L).

Load-bearing premise

Oscillatory matrix theory guarantees that all spectral residues of the restricted transfer matrix are nonzero, so its characteristic polynomial is fixed exactly by Stirling-weighted Lagrange interpolation at the Holte eigenvalues.

What would settle it

Compute the cascade-free avoidance sequence a(L) explicitly for k=4 and increasing L; if the sequence fails to satisfy the three-term linear recurrence satisfied by scaled Chebyshev polynomials of the second kind, the sharpness claim is false.

Figures

Figures reproduced from arXiv: 2604.04591 by Daniel Andreas Moj.

**Figure 2.** Figure 2: The moduli space Ω of shadow-equivalence classes for binary carry chains ( [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

read the original abstract

For $k$-summand base-$N$ addition, the carry process is a Markov chain on $\{0,\ldots,k-1\}$ whose transition matrix--the Holte matrix $T$--has eigenvalues $\{N^{-j}\}_{j=0}^{k-1}$, all simple and independent of $N$. We give the complete biorthogonal eigenvector system. The left eigenvectors factor as $\sum_i u_j[i] x^i = c_{k,j} (x-1)^j A_{k-j}(x)$, where $c_{k,j} = |s(k,k-j)|/k!$ involves unsigned Stirling numbers and $A_n(x)$ is the Eulerian polynomial. The right eigenvectors satisfy $\sum_i \binom{k-1}{i} v_j[i] x^i = (1+x)^{k-1-j} Q_j(x)$, where the quotient polynomials $Q_j$ have palindrome symmetry $x^j Q_j(1/x) = (-1)^j Q_j(x)$ and converge to $(1-x)^j$ as $k \to \infty$; for $j \le 3$, we give explicit closed forms in terms of $k$. The cascade-free avoidance count satisfies $a(L) = (\sqrt{d})^L U_L(x)$ (Chebyshev polynomial of the second kind) whenever the restricted transfer matrix has dimension $d \le 2$; we prove this is sharp: for $k$-summand addition, Chebyshev form holds for $k = 3$ and fails for $k \ge 4$. The proof uses oscillatory matrix theory to establish non-vanishing of all spectral residues. The characteristic polynomial of the restricted transfer matrix is determined in closed form by a Stirling-weighted Lagrange interpolation at the Holte eigenvalues. Two systems with binary carry state spaces are shadow-equivalent if and only if they share the pair $(N, d)$. The general classification for $k$-state systems reduces to the characteristic polynomial of $T$.

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 gives clean closed-form biorthogonal eigenvectors for the Holte matrix via Stirling and Eulerian factors, plus a sharpness proof that Chebyshev form for cascade-free counts holds only at k=3.

read the letter

The main contribution is the explicit biorthogonal eigenvector system for the Holte carry matrix. Left eigenvectors factor as a Stirling-scaled (x-1)^j times an Eulerian polynomial, and the right eigenvectors come with a generating function that has built-in palindrome symmetry and explicit low-j formulas. The second piece is the result that the cascade-free avoidance count is given by a scaled Chebyshev polynomial of the second kind only when the restricted matrix has dimension at most 2, with a proof that this is sharp: it works for k=3 and fails for k greater than or equal to 4. Both results are stated cleanly and build directly on the known simple eigenvalues of the full Holte matrix. The interpolation approach for the restricted characteristic polynomial and the appeal to oscillatory matrix theory to guarantee nonzero residues are the technical steps that make the sharpness claim go through. The formulas look reproducible from the given expressions, and the combinatorial polynomials involved are standard, so the algebraic part feels solid. The soft spot is whether the restriction to cascade-free states actually preserves the total nonnegativity or sign pattern that oscillatory theory requires. If the restricted matrix loses that property, the non-vanishing of residues would need separate justification rather than following from the general theory. The paper claims to handle this, but the argument would be stronger with an explicit check that the principal minors or the relevant sign conditions survive the restriction. The interpolation step also assumes the restricted matrix shares enough structure with the full Holte matrix for the Lagrange form to match the determinant exactly; that needs to be verified rather than assumed from the unrestricted case. Readers working on Markov chains for addition algorithms or on restricted combinatorial enumeration will get direct use from the eigenvector formulas and the classification remark about shadow-equivalent systems. The work is narrow but technically precise, so it belongs in a combinatorics or discrete math journal rather than a broad venue. It deserves a serious referee to check the details on the restricted matrix and the interpolation equality. I would send it out for review with those two points flagged for the authors to clarify.

Referee Report

2 major / 2 minor

Summary. The paper determines the complete biorthogonal eigenvector system for the Holte carry matrix T of the k-summand base-N addition Markov chain, whose eigenvalues are the simple roots {N^{-j}}_{j=0}^{k-1}. Left eigenvectors are expressed as c_{k,j} (x-1)^j A_{k-j}(x) with c_{k,j} built from unsigned Stirling numbers of the first kind and A_n the Eulerian polynomial; right eigenvectors involve palindromic quotient polynomials Q_j(x) that converge to (1-x)^j. For cascade-free avoidance the counting sequence a(L) is shown to equal (sqrt(d))^L U_L(x) (Chebyshev of the second kind) when the restricted transfer matrix has dimension d ≤ 2; the authors prove this form is sharp, holding exactly for k=3 and failing for k ≥ 4, by invoking oscillatory matrix theory to obtain non-vanishing residues and determining the restricted characteristic polynomial via Stirling-weighted Lagrange interpolation at the Holte eigenvalues. Two binary-carry systems are shadow-equivalent precisely when they share the pair (N,d).

Significance. If the central derivations hold, the explicit eigenvector formulas and the sharp classification of when cascade-free counts admit a Chebyshev closed form constitute a concrete advance in the spectral combinatorics of carry processes. The paper supplies parameter-free closed forms (Stirling-Eulerian for left vectors, explicit Q_j for j ≤ 3) and a falsifiable sharpness statement, both of which are strengths. The reduction of the general k-state classification to the characteristic polynomial of T is also a useful structural observation.

major comments (2)

[section deriving the cascade-free avoidance count and its sharpness] Proof of the sharpness claim (Chebyshev form only for k=3): the argument invokes oscillatory matrix theory to guarantee that all spectral residues of the restricted transfer matrix M are nonzero. The restriction to cascade-free states may destroy the sign pattern or principal-minor positivity required by the standard oscillatory hypotheses; an explicit verification that M remains oscillatory (or satisfies an equivalent total-nonnegativity condition) is needed before the non-vanishing conclusion can be drawn.
[section on the characteristic polynomial of the restricted transfer matrix] Determination of the characteristic polynomial of the restricted matrix: the manuscript asserts that this polynomial is exactly the unique degree-d interpolant obtained by Stirling-weighted Lagrange interpolation at the k Holte points {N^{-j}}. While interpolation produces a candidate, it equals det(λI-M) only if additional structural agreement survives the restriction; the paper must exhibit this agreement (for example by showing that the restricted matrix shares the same Newton identities or generating function as the unrestricted case) rather than assuming it follows automatically from the interpolation.

minor comments (2)

[statement of the left eigenvectors] The Eulerian polynomial A_n(x) is used without an explicit definition or reference in the left-eigenvector formula; a one-line reminder of its standard generating function would improve readability.
[discussion of right eigenvectors] The convergence statement for the quotient polynomials Q_j(x) as k → ∞ is stated but not quantified; a rate or explicit error term would strengthen the asymptotic claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive major comments, which help clarify the application of oscillatory matrix theory and the justification for the characteristic polynomial. We address each point below and have revised the manuscript to incorporate explicit verifications.

read point-by-point responses

Referee: Proof of the sharpness claim (Chebyshev form only for k=3): the argument invokes oscillatory matrix theory to guarantee that all spectral residues of the restricted transfer matrix M are nonzero. The restriction to cascade-free states may destroy the sign pattern or principal-minor positivity required by the standard oscillatory hypotheses; an explicit verification that M remains oscillatory (or satisfies an equivalent total-nonnegativity condition) is needed before the non-vanishing conclusion can be drawn.

Authors: We agree that an explicit check is required to confirm the hypotheses of oscillatory matrix theory survive the restriction. For the cascade-free state spaces with d ≤ 2 (the cases where the Chebyshev form is claimed), the allowed states form an initial segment of the state space. Direct computation shows that the restricted matrix M inherits the checkerboard sign pattern and positive principal minors from the original Holte matrix T. In the revised manuscript we have inserted a short lemma verifying these properties by explicit enumeration of the 1×1 and 2×2 principal minors for d=1 and d=2; this justifies the non-vanishing of all residues and thereby the sharpness statement for k=3. revision: yes
Referee: Determination of the characteristic polynomial of the restricted matrix: the manuscript asserts that this polynomial is exactly the unique degree-d interpolant obtained by Stirling-weighted Lagrange interpolation at the k Holte points {N^{-j}}. While interpolation produces a candidate, it equals det(λI-M) only if additional structural agreement survives the restriction; the paper must exhibit this agreement (for example by showing that the restricted matrix shares the same Newton identities or generating function as the unrestricted case) rather than assuming it follows automatically from the interpolation.

Authors: We thank the referee for requiring this additional justification. The equality holds because the cascade-free restriction corresponds to a combinatorial truncation whose power-sum moments (via the Stirling-weighted generating function) coincide with those of the full Holte matrix at the interpolation nodes N^{-j}. Consequently the Newton-Girard identities for the restricted characteristic polynomial match those satisfied by the Lagrange interpolant. The revised section now contains a short derivation of this moment agreement, confirming that the interpolant is indeed det(λI-M). revision: yes

Circularity Check

0 steps flagged

No circularity in the derivation chain

full rationale

The paper derives the complete biorthogonal eigenvector system for the Holte matrix from its known simple eigenvalues {N^{-j}} using standard linear algebra, expressing the left eigenvectors via unsigned Stirling numbers and Eulerian polynomials, and the right eigenvectors via explicit quotient polynomials with stated symmetries. The cascade-free avoidance count is shown to equal a scaled Chebyshev polynomial of the second kind for restricted transfer matrices of dimension d ≤ 2, with sharpness for k=3 established by invoking oscillatory matrix theory for non-vanishing residues and determining the characteristic polynomial via Stirling-weighted Lagrange interpolation at the given Holte eigenvalues. These steps rely on external combinatorial objects and matrix theory without any reduction of results to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivations remain self-contained against independent benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard linear algebra and known combinatorial identities rather than new postulates; the central contributions are explicit constructions and a sharpness proof.

axioms (2)

domain assumption The Holte matrix T has eigenvalues {N^{-j}}_{j=0}^{k-1}, all simple and independent of N.
Taken as given from the definition of the carry process Markov chain on {0,...,k-1}.
standard math Unsigned Stirling numbers of the first kind and Eulerian polynomials satisfy the factorization properties used for left eigenvectors.
Standard combinatorial objects whose algebraic properties are invoked without proof.

pith-pipeline@v0.9.0 · 5667 in / 1491 out tokens · 67423 ms · 2026-05-10T19:34:49.174713+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

[1]

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

Moj, D.A.: Cascade-free sequences, dispersion index, and state avoidance for stateful digit- wise operations. Preprint, arXiv:2604.02542 [math.CO] (2026).https://doi.org/10.48550/ arXiv.2604.02542

work page internal anchor Pith review Pith/arXiv arXiv 2026
[2]

Holte, J.M.: Carries, combinatorics, and an amazing matrix. Amer. Math. Monthly 104, 138– 149 (1997).https://doi.org/10.2307/2974981

work page doi:10.2307/2974981 1997
[3]

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

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

Comtet, L.: Advanced Combinatorics. D. Reidel, Dordrecht (1974).https://doi.org/10. 1007/978-94-010-2196-8

work page 1974
[5]

AMS Chelsea (2002).https://doi.org/10.1090/chel/345

Gantmacher, F.R., Krein, M.G.: Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, revised ed. AMS Chelsea (2002).https://doi.org/10.1090/chel/345

work page doi:10.1090/chel/345 2002
[6]

Diaconis, P., Fulman, J.: Carries, shuffling, and an amazing matrix. Amer. Math. Monthly 119, 32–39 (2012).https://doi.org/10.4169/amer.math.monthly.119.01.032

work page doi:10.4169/amer.math.monthly.119.01.032 2012
[7]

Diaconis, P., Fulman, J.: Foulkes characters, Eulerian idempotents, and an amazing matrix. J. Algebraic Combin. 36, 425–440 (2012).https://doi.org/10.1007/s10801-012-0343-7

work page doi:10.1007/s10801-012-0343-7 2012
[8]

Discrete Math

Foulkes, H.O.: Eulerian numbers, Newcomb’s problem and representations of symmetric groups. Discrete Math. 30, 3–49 (1980).https://doi.org/10.1016/0012-365X(80)90061-8

work page doi:10.1016/0012-365x(80)90061-8 1980
[9]

Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and an amazing matrix. Adv. in Appl. Math. 48, 528–534 (2012).https://doi.org/10.1016/j.aam.2011.11.008

work page doi:10.1016/j.aam.2011.11.008 2012
[10]

2: Seminumerical Algorithms, 3rd ed

Knuth, D.E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley (1997)

work page 1997
[11]

Wiley-Interscience (2001).https: //doi.org/10.1002/9781118033067

Koshy, T.: Fibonacci and Lucas Numbers with Applications. Wiley-Interscience (2001).https: //doi.org/10.1002/9781118033067

work page doi:10.1002/9781118033067 2001
[12]

Chapman & Hall/CRC (2003)

Mason, J.C., Handscomb, D.C.: Chebyshev Polynomials. Chapman & Hall/CRC (2003). https://doi.org/10.1201/9781420036114

work page doi:10.1201/9781420036114 2003
[13]

Accessed 6 April 2026

Sloane, N.J.A., et al.: The On-Line Encyclopedia of Integer Sequences, published electronically athttps://oeis.org(2025). Accessed 6 April 2026

work page 2025
[14]

Stanley, R.P.: Enumerative Combinatorics, Vol. 1. Cambridge Univ. Press (1997).https: //doi.org/10.1017/CBO9780511805967 22

work page doi:10.1017/cbo9780511805967 1997

[1] [1]

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

Moj, D.A.: Cascade-free sequences, dispersion index, and state avoidance for stateful digit- wise operations. Preprint, arXiv:2604.02542 [math.CO] (2026).https://doi.org/10.48550/ arXiv.2604.02542

work page internal anchor Pith review Pith/arXiv arXiv 2026

[2] [2]

Holte, J.M.: Carries, combinatorics, and an amazing matrix. Amer. Math. Monthly 104, 138– 149 (1997).https://doi.org/10.2307/2974981

work page doi:10.2307/2974981 1997

[3] [3]

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

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

[4] [4]

Comtet, L.: Advanced Combinatorics. D. Reidel, Dordrecht (1974).https://doi.org/10. 1007/978-94-010-2196-8

work page 1974

[5] [5]

AMS Chelsea (2002).https://doi.org/10.1090/chel/345

Gantmacher, F.R., Krein, M.G.: Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, revised ed. AMS Chelsea (2002).https://doi.org/10.1090/chel/345

work page doi:10.1090/chel/345 2002

[6] [6]

Diaconis, P., Fulman, J.: Carries, shuffling, and an amazing matrix. Amer. Math. Monthly 119, 32–39 (2012).https://doi.org/10.4169/amer.math.monthly.119.01.032

work page doi:10.4169/amer.math.monthly.119.01.032 2012

[7] [7]

Diaconis, P., Fulman, J.: Foulkes characters, Eulerian idempotents, and an amazing matrix. J. Algebraic Combin. 36, 425–440 (2012).https://doi.org/10.1007/s10801-012-0343-7

work page doi:10.1007/s10801-012-0343-7 2012

[8] [8]

Discrete Math

Foulkes, H.O.: Eulerian numbers, Newcomb’s problem and representations of symmetric groups. Discrete Math. 30, 3–49 (1980).https://doi.org/10.1016/0012-365X(80)90061-8

work page doi:10.1016/0012-365x(80)90061-8 1980

[9] [9]

Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and an amazing matrix. Adv. in Appl. Math. 48, 528–534 (2012).https://doi.org/10.1016/j.aam.2011.11.008

work page doi:10.1016/j.aam.2011.11.008 2012

[10] [10]

2: Seminumerical Algorithms, 3rd ed

Knuth, D.E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley (1997)

work page 1997

[11] [11]

Wiley-Interscience (2001).https: //doi.org/10.1002/9781118033067

Koshy, T.: Fibonacci and Lucas Numbers with Applications. Wiley-Interscience (2001).https: //doi.org/10.1002/9781118033067

work page doi:10.1002/9781118033067 2001

[12] [12]

Chapman & Hall/CRC (2003)

Mason, J.C., Handscomb, D.C.: Chebyshev Polynomials. Chapman & Hall/CRC (2003). https://doi.org/10.1201/9781420036114

work page doi:10.1201/9781420036114 2003

[13] [13]

Accessed 6 April 2026

Sloane, N.J.A., et al.: The On-Line Encyclopedia of Integer Sequences, published electronically athttps://oeis.org(2025). Accessed 6 April 2026

work page 2025

[14] [14]

Stanley, R.P.: Enumerative Combinatorics, Vol. 1. Cambridge Univ. Press (1997).https: //doi.org/10.1017/CBO9780511805967 22

work page doi:10.1017/cbo9780511805967 1997