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.
Tag: Positive Linear Recurrence Sequences
-
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.