Thinking In Structure

Tag: PLRS

  • Automaton Minimization andCanonical Reduction for PLRS Numeration

    Download Paper (pdf)

    Abstract

    Canonical positive linear recurrence numeration systems admit multiple coefficient presentations generating the same legality language. Paper III showed that every such presentation belongs to a unique equivalence class determined by an intrinsic periodic boundary sequence and that each class possesses a distinguished canonical reduction of minimal order.
    In this paper we give an automata-theoretic interpretation of canonical reduction. To every coefficient presentation we associate a deterministic threshold-reset automaton accepting exactly its legality language. We prove that the natural automaton of every presentation minimizes to the natural automaton of the canonical reduction.
    Consequently the minimal deterministic automaton of the legality language is uniquely determined by the canonical reduction, and the canonical order is exactly the number of live Myhill–Nerode classes of the legality language.
    Thus canonical reduction is identified with automaton minimization, providing an intrinsic automata-theoretic characterization independent of recurrence order.

  • Intrinsic Boundary Sequences, Canonical Presentations, and Language Invariance in Canonical Positive Linear Recurrence Numeration

    Download paper (pdf)

    Abstract

    Canonical positive linear recurrence numeration systems may admit multiple coefficient presentations that generate the same place-value sequence. Paper I established that every such equivalence class has a unique canonical reduction of minimal order. Paper II showed that every presentation determines the same infinite periodic maximal boundary word and asked whether this boundary word is sufficient to reconstruct the canonical reduction. In this paper, we identify the intrinsic object underlying both theories. For every place-value sequence (Hₙ), we define an infinite sequence e = (eᵢ)ᵢ≥1 through the triangular valuation identity Hₙ₊₁ − 1 = ∑ᵢ₌₁ⁿ eᵢHₙ₊₁₋ᵢ. We prove that every coefficient presentation generating (Hₙ) is uniquely determined by a period of this intrinsic sequence, while the canonical reduction is recovered by taking its primitive period. This resolves the reconstruction problem posed in Paper II. The identification also yields a complete classification of coefficient presentations: every period of the intrinsic sequence gives a valid presentation, and every valid presentation arises in this way. Thus, the periods of e are in exact bijection with the presentations generating (Hₙ). We then establish a general lift-invariance theorem showing that every iterated lift of the canonical reduction generates exactly the same legality language. Consequently, any two coefficient presentations producing the same place-value sequence define identical languages of legal representations. Although their recursive legality decompositions may differ, their accepted languages coincide. The trilogy therefore culminates in a complete hierarchy of intrinsic structure: the coefficient vector, maximal boundary word, and legality language are all determined by the place-value sequence itself.

  • Boundary Maps and Carry Costs in Canonical Positive Linear Recurrence Numeration Systems

    Download paper (pdf)

    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.

  • Canonical Reduction and Inverse Reconstruction in PLRS Numer-ation

    Download paper (pdf)

    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

    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.