Abstract
The companion paper established that carry depth under incrementation in canonical positive linear
recurrence numeration systems (PLRS) converges to a geometric distribution determined by the
Perron root of the defining recurrence. The present paper studies the arithmetic cost of those
carries.
A new structural theorem is proved showing that the lexicographically maximal legal words form
the prefixes of a single infinite periodic word
P∞,
P =c1c2···cL−1(cL −1),
for every canonical coefficient vector c = (c1,…,cL). Combined with the canonical successor
decomposition established in the companion paper, this shows that every additive carry statistic is
obtained by evaluating an explicit periodic boundary map on the carry depth.
A general pushforward theorem is established for periodic boundary maps, reducing the limiting
distribution of every additive carry statistic to the geometric carry-depth law. Two natural statistics
are then studied in detail: Hamming carry cost, which counts the number of digit positions changed
by incrementation, and digit-magnitude (ℓ1) carry cost, which records the total digit mass erased
during the carry.
Exact limiting distributions, rational generating functions, and reconstruction procedures are
obtained for both statistics. The Hamming carry law determines the complete support sequence
1
of the maximal periodic boundary word, while the digit-magnitude law determines the complete
infinite boundary word itself. Whether this always determines the canonical reduction of the defining
recurrence in the sense of the companion paper is identified as an open problem. A simple identity
derived from the characteristic equation yields the universal expectation
E[Cℓ1] = 2
for every canonical PLRS, extending the classical mean-two phenomenon beyond the binary setting.
Together with the companion paper, these results separate the probabilistic geometry of carry
propagation from its deterministic arithmetic boundary structure.
Category: Research
-
Boundary Maps and Carry Costs in Canonical Positive Linear Recurrence Numeration Systems
-
Canonical Reduction and Inverse Reconstruction in PLRS Numer-ation
Abstract
We study the inverse problem for carry propagation in canonical positive linear recurrence sequence (PLRS) numeration systems: given only the histogram of carry depths arising from incrementation, can the underlying recurrence be recovered? We develop a purely combinatorial description of carry propagation, derived entirely from the recursive legality definition and independent of any numerical valuation. The legal words of each width form a rooted ordered tree with canonical minimal and
maximal extensions at every node; these identify the immediate lexicographic successor of any legal word, which we then show coincides with arithmetic incrementation once the valuation map
is introduced. Carry depth is shown to correspond not to a disjoint partition of legal words, as a naive count might suggest, but to a family of nested tail classes that biject with legal prefixes via a
maximum-cylinder construction; exact-depth counts are recovered as first differences of these tails.
We then address reconstruction directly, and show by explicit counterexample — the coefficient vectors (2) and (1, 2), which generate an identical sequence of place values — that the histogram does not determine the defining coefficient vector uniquely. We identify the correct invariant, the canonical reduction (the presentation of least admissible order generating the observed sequence), and prove that the carry histogram determines this reduction exactly, recovering the original coefficient vector whenever it is already reduced.The four principal contributions are:
(i) a fully combinatorial account of carry propagation via the tree structure of legal words;
(ii) the prefix-cylinder tail identity governing carry-depth statistics;
(iii) the identification and proof of the canonical-reduction phenomenon, including the non-uniqueness example; and (iv) a deterministic, finite reconstruction procedure recovering the canonical reduction from carry data.
(iv) a deterministic, finite reconstruction procedure recovering the canonical reduction from carry data.
-
Boundary Layers and Inverse Reconstruction in Canonical Multi-Gap PLRS Numeration
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
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
Author: Paul Higham
Date: 24 July 2026
Status: PreprintThis 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.