Thinking In Structure

Tag: carry propagation

  • Boundary Layers and Inverse Reconstruction in Canonical Multi-Gap PLRS Numeration

    Download paper (pdf)

    Abstract

    We study carry propagation in a family of canonical positive linear recurrence sequence (PLRS) numeration systems whose coefficient vectors consist of alternating blocks of k ones and
    prescribed zero runs. We first derive the exact combinatorial structure of maximal legal words directly from the recursive legality definition. This yields an explicit periodic maximal word, an
    exact description of the exceptional carry fibres, exact fibre offsets, and the universal identity that the mean carry length is identically two for every member of the family.
    Using the associated generating functions, we develop a complete asymptotic expansion for the variance of the carry length. The expansion naturally decomposes into primitive travelling boundary layers determined by the coefficient signature and exponentially smaller corrections
    arising from perturbations of the dominant characteristic root. The first moment is shown to be universal, while the higher-order asymptotic boundary layers contain sufficient information to reconstruct the defining coefficient signature, as proved in Section 10.
    Finally, we prove an inverse reconstruction theorem. After separating the universal root contribution from the primitive boundary layers, the coefficient signature is recovered recursively from the asymptotic expansion of the variance. This establishes that the asymptotic carry statistics uniquely determine the underlying multi-gap PLRS family.

  • Boundary Maps and Travelling Carry Layers in Binary Positive Linear Recurrence Numeration

    Download pdf

    Abstract

    We study Hamming carry propagation under incrementation in a one-parameter family of binary positive linear recurrence numeration systems. For integers k ≥ 2 and 1 ≤ a < k, the defining coefficient vector is

    ck,a = (1, …, 1, 0, …, 0, 1),

    with k − a initial 1s and a − 1 zeros. This family interpolates between the canonical k-bonacci recurrence and systems whose maximal legal representations contain longer zero blocks.

    The principal object is the boundary carry map, which assigns to each maximal legal suffix the number of digits changed when that suffix is reset during incrementation. We show that this map possesses exceptional fibres of cardinality a + 1, producing isolated spikes in the limiting carry distribution. The limiting law is obtained as the pushforward of an explicit geometric distribution under the boundary map:

    pk,a(r) = (1 − q) ΣDk,a(m)=r qm,

    where q ∈ (0,1) is the reciprocal of the dominant characteristic root.

    Despite the presence of boundary collisions, the limiting mean Hamming carry length satisfies the exact identity

    μk,a = 2

    for every member of the family. An exact closed-form variance formula is likewise proved for every admissible pair (k, a), by two independent derivations in Section 10 and Appendix B. Its fixed-a asymptotic expansion as k → ∞ is developed and proved in Section 11, including rigorous error control at every fixed boundary coordinate.

    The travelling boundary layer found previously for canonical k-bonacci numeration is shown to arise from the non-injectivity of the boundary carry map. The parameter a provides explicit control over both the location and the amplitude of this phenomenon.

    The results identify boundary-map geometry, rather than the recurrence relation alone, as the mechanism governing higher-order carry statistics. The structural theory, exact finite carry recurrence, exact mean and exact variance are proved in full for every admissible pair (k, a), together with the fixed-a asymptotic consequences of these formulas.

  • Boundary Layers in the Carry Distribution of Canonical k-bonacci Numeration

    Download paper (pdf)

    Author: Paul Higham
    Date: 24 July 2026
    Status: Preprint

    This paper studies how carries propagate when adding one in canonical k-bonacci numeration systems. Although these systems become increasingly similar to ordinary binary arithmetic as k grows, the convergence is surprisingly subtle. The paper derives the exact limiting carry distribution, proves that the mean carry length is exactly two for every k, and identifies a travelling boundary layer that governs the leading deviation from binary behaviour.

    Abstract

    Canonical k-bonacci numeration represents integers by binary words avoiding a forbidden block of k consecutive ones. As k increases, this restriction becomes progressively weaker, suggesting that the associated arithmetic should approach ordinary binary arithmetic. In this paper we investigate the distribution of carry lengths arising when one is added to a uniformly chosen integer.

    We derive an exact recurrence for the carry spectrum by exploiting the recursive decomposition of the admissible language. This recurrence yields rational generating functions whose common characteristic polynomial is that of the k-bonacci recurrence. Explicit formulae for the limiting carry probabilities are obtained from the dominant pole.

    We show that the carry distribution admits two distinct first-order asymptotic corrections. For every fixed carry length, the probabilities differ from the binary distribution by a diffuse bulk correction. In addition, a moving boundary layer centred at carry length k contributes a correction concentrated in a narrow window whose rescaled profile converges to an explicit geometric limit.

    The interaction between these two structures determines the asymptotic moments of the carry distribution. In particular, we prove that the limiting mean carry length is exactly 2 for every k ≥ 2, and derive the leading asymptotic behaviour of the variance. Thus the dominant deviation from binary arithmetic is generated by the first boundary layer, while the bulk contributes only a lower-order correction. The analysis suggests a general framework in which local statistics of recursive numeration systems are governed by homogeneous recurrences together with boundary forcing arising from the recursive decomposition of the underlying language.

    Current version: July 2026. Comments and corrections are welcome.