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.