Thinking In Structure

Category: Research

  • Global Carry Realization in Canonical PLRS Numeration

    Download paper (pdf)

    Let P = e1 ⋯ eL be the primitive maximal boundary block of a canonical positive linear recurrence sequence (PLRS) numeration system. Earlier local carry theory determines individual successor depths but not which such depths can occur consecutively. We solve this global realization problem.

    For each maximal-orbit phase i and width m, the state carry words satisfy

    Wi(m) = (W0(m−1)(m − 1))ei+1 Wi+1(m−1).

    If u is a finite depth word with M = max u, then

    u is globally realizable ⇔ u ∈ Fact(W0(M+L)).

    Thus realization has an exact bounded-width criterion, although the corresponding root carry word may be exponential in that width.

    The same recursion yields a generalized ruler word with exact renormalization and a countable-alphabet substitution structure. At matched scale, phase-containment recursions connect global realization to the anti-Lyndon criterion: P is anti-Lyndon exactly when the root phase already contains every matched-scale carry factor at every depth.

    For non-anti-Lyndon boundaries we identify the exact first failure depth and distinguish immediately visible local defects from globally masked witnesses.

  • Local Dynamics and Periodic Lifts of Carry Depths in Canonical PLRS Numeration

    Download paper (pdf)

    For a canonical positive linear recurrence numeration system with threshold-reset legality automaton and maximal boundary block

    P = p1···pL,

    we give an exact local grammar for the reset-depth sequence produced by lexicographic succession. Every positive reset depth determines its predecessor’s branch-point state and depth exactly (Theorem A); every carry-depth excursion collapses to depth 0 in at most L deterministic steps (Theorem B); and every realized excursion skeleton admits every periodic lift of its initial depth, with width increased accordingly, and with no gaps (Theorem C).

    Together these give an exact decomposition of the carry-depth sequence into a finite deterministic skeleton and an unbounded periodic lift parameter. We further show that carry-depth structure depends critically on which of two natural residual-state conventions is used: the source-word residual state is exactly depth-determined,

    σ(w) = qT(w) mod L,

    while the branch-point state is maximally mixed,

    R*t = B   for every   t ≥ 0.

    We apply this grammar to state-dependent carry-cost decoders, obtaining an exact single-edge observability criterion, exact backward resolving radii throughout the deterministic predecessor chain, including its first forced depth-zero endpoint, and a sharp characterization of the multivalued obstruction that governs that endpoint’s own predecessor.

  • Rank-Positional Threshold Languages: ResetStructure, Census Rigidity, and Finite Reconstruction

    Download paper (pdf)

    Let L be a prefix-closed language over a finite ordered digit alphabet, and assume that at every reachable residual the legal next digits form an initial interval

    {0, 1, …, d(q)}.

    Write

    Cn = |L ∩ Σn|,   C0 = 1,

    and let Rn(w) be the zero-based lexicographic rank of w ∈ L ∩ Σn. We call L rank-positional if

    Rn(a1···an) = ∑j=1n ajCn−j

    for every legal word. Thus the language’s own width census supplies its positional place values.

    Viewed from abstract numeration theory, this is a restricted form of the broader positionality problem: when does a language whose numerical values are defined by enumeration admit a genuine positional realization? Here the basis is not arbitrary; it is determined intrinsically by the language itself through its width census. Under the threshold hypothesis, we give a complete characterization of this census-positional class.

    We prove that the fixed-width rank identity is equivalent to a local reset condition: every strict-deficiency successor has the same continuation census as the root, and in the accessible minimal automaton every such transition returns literally to the root. Hence every regular rank-positional threshold language has a root-reset lollipop automaton whose live states form one maximal-transition orbit.

    The maximal thresholds define an intrinsic boundary

    e = e1e2···.

    Its tails classify residual states, regularity is equivalent to eventual periodicity, and a boundary with minimal preperiod t and primitive period p yields exactly t + p live states. The same boundary is the length inventory of a canonical prefix-free reset code, giving

    L = B(e)*P(e)

    and

    Cn = 1 + ∑i=1n eiCn−i.

    This relation is triangular, so the census determines the boundary, the minimal automaton, and the complete language.

    For regular systems we prove an optimal finite rigidity theorem: if two systems have s and s′ live states, equality of

    C0, …, Cs+s′−1

    forces equality of the languages, and the bound is sharp for every pair (s, s′). We also determine the exact order of the minimal homogeneous linear recurrence satisfied by the census:

    r = t + p − deg gcd(B, Sp),

    where B is the periodic boundary polynomial and

    Sp = 1 + z + ··· + zp−1.

    Thus the gap between automaton-state complexity and scalar recurrence complexity is an explicit cyclotomic defect.

    The threshold hypothesis is sharp: without it, rank-positional languages can have distinct residuals with identical continuation-count sequences. Purely periodic and self-admissible boundaries recover, respectively, PLRS and beta/Bertrand specializations of the general boundary theory.

    The paper therefore gives a complete intrinsic solution to the census-positional threshold case of the general positionality problem for regular-language numeration, while leaving the unrestricted positionality problem open.

  • Intrinsic Recognition of Canonical PLRS Legality Automata

    Download paper (pdf)

    Paper IV showed that every presentation of a canonical positive linear recurrence sequence (PLRS) numeration system determines a threshold-reset automaton, and that this automaton minimizes
    to the threshold-reset automaton of the canonical reduction. Left open there was the converse recognition problem: given an arbitrary minimal deterministic automaton over an ordered digit
    alphabet, with no numeration system attached to it in advance, when is it the legality automaton of some canonical PLRS, and how is the coefficient vector recovered? We answer this completely.
    We give five intrinsic structural conditions on a pointed DFA — a unique absorbing rejecting sink, a cyclic threshold-reset structure with a common restart state, coincidence of the initial and
    restart states, an initial-positivity condition, and closure of the threshold orbit of the restart state — and prove that a minimal DFA satisfies them if and only if it is the legality automaton of a canonical PLRS. The coefficient vector is then recovered uniquely and constructively from the transition table. We further prove, as an independent proposition, that minimality of such an
    abstract cyclic threshold-reset automaton is equivalent to primitivity of its threshold-boundary word. Closely related threshold automata occur in Parry and Bertrand numeration, while classical work characterizes regularity of representation languages starting from a given numeration system.
    The direction here is converse and PLRS-specific: the only input is the pointed minimal DFA, from which PLRS realizability and the unique canonical coefficient vector are decided. Sharpness
    examples show that the principal structural hypotheses cannot be omitted or replaced by several natural weaker conditions.

  • Endpoint Decomposition and an Anti-Lyndon Aperiodicity Criterion for PLRS Numeration

    Download paper (pdf)
    Download supplementary code (zip)

    Canonical positive linear recurrence sequence numeration systems admit a natural deterministic threshold-reset automaton for their legality languages. Paper IV showed that, after minimization, every presentation of a fixed system yields the automaton of the canonical reduction. The present paper studies the internal transition structure of that canonical automaton. We introduce anchored deficient-block languages and prove a Generalized Endpoint Decomposition describing every live computation from an arbitrary starting state as either a forced threshold march or an anchored first reset followed by a universal restart grammar. We then identify an exact aperiodicity criterion. If

    P=c1c2···cL−1(cL−1)P = c1c2 · · · cL−1(cL − 1)

    is the primitive maximal boundary block of the canonical reduction, then the canonical threshold-
    reset automaton is aperiodic if and only if PP is lexicographically maximal among its nontrivial cyclic rotations, equivalently, if and only if PP is anti-Lyndon. The forward implication follows from a total
    order on live states induced by the rotations of P∞P ∞, under which every digit acts monotonically. For the converse, the least rotation exceeding P∞P ∞ yields an explicit word whose induced transformation has a nontrivial periodic orbit. Since the canonical automaton is minimal over its finite natural digit alphabet, this is also equivalent to star-freeness of the legality language. Exhaustive computations for all canonical reductions of order at most six with coefficients at most four agree exactly with the
    theorem and recover the previously observed cycle families as concrete manifestations of the same restart structure.

  • Reconstruction of Ordered Prefix Languages from Coarsened Carry Traces

    Download paper (pdf)

    This paper develops an exact inverse theory for ordered carry traces on zero-prolongable prefix languages. It asks how much of an underlying legality language can be reconstructed when the reset depth between consecutive legal words is observed only through a possibly noninjective numerical decoder.

    The paper proves that every strict jump of the decoder reveals a complete ordered cylinder partition. Across all widths, the carry traces determine exactly the language’s \(g\)-decimated ancestry system, where

    \[ g=\gcd\{r\geq 1:D(r)>D(r-1)\}. \]

    The complete ordered prefix tree is therefore universally reconstructible precisely when \(g=1\). Under gap-free branching, the traces also reconstruct the labelled language.

    A visibility graph associated with the decoder gives the exact finite observation horizon required for reconstruction:

    \[ H_D^*(M)= \begin{cases} M, & M\leq g,\\[2mm] M-g+\rho_D, & M\geq g+1. \end{cases} \]

    Matching lower bounds show that this horizon is optimal, even for binary gap-free languages. In the important first-jump case \(D(1)>D(0)\), one has \(g=\rho_D=1\), so traces through width \(M\) recover the language through depth \(M\) with no additional look-ahead.

    The paper also examines hidden state-dependent carry costs, explains why the depth-only assumption is substantive, and identifies uniform cross-state separation as a sufficient condition for extending part of the reconstruction theory.

  • Finite-Sample Reconstruction from Carry Propagation in Canonical Beta Numeration

    Download paper (pdf)

    This paper develops a finite-sample reconstruction theory for carry propagation in canonical β\beta-numeration. Building on the exact inverse results of Paper V, it asks how much of the canonical decoder can be recovered when only finitely many carry observations are available. The analysis isolates a geometric decoder model in which a geometric reset depth is observed through a monotone additive decoder. Within this model, the paper proves deterministic reconstruction from finite exact spectra, a quantitative rigidity theorem for the inverse map, and a certified nearest-neighbour algorithm that recovers the first mmm decoder digits with probability at least 1−δ1-\delta from Oq ⁣(q−mlog⁡(m/δ))O_q\!\left(q^{-m}\log(m/\delta)\right) observations. A matching information-theoretic lower bound shows that the exponential dependence on reconstruction depth is unavoidable. The paper also explains how finite-prefix recovery yields complete reconstruction for bounded Parry systems and presents numerical experiments confirming both the q−mq^{-m} scaling and the necessity of certification.

  • Exact Carry-Propagation Distributions and Boundary Reconstruction in Canonical Beta Numeration

    Download paper (pdf)

    Carry propagation is one of the most familiar features of positional arithmetic. When a number is incremented, a terminal block of digits may have to be rewritten. In ordinary decimal notation this occurs, for example, when 999 becomes 1000. Similar behaviour arises in more general numeration systems, but the length and cost of the resulting carry depend on the structure of the admissible digit representations.

    This paper develops an exact finite-width distributional and inverse theory of carry propagation in canonical greedy beta numeration. It builds on the established language-tree and odometer approaches to successor propagation, using the specific structure of the canonical beta boundary to obtain complete finite-width laws rather than only aggregate or limiting results.

    The key beta-specific property is that a carry resets an initial prefix of the canonical boundary. Combined with exact counting of maximal admissible suffixes, this yields the complete finite-width distribution of carry-propagation lengths and shows that the limiting distribution is a shifted geometric law determined by the base.

    The paper also proves exact distribution and moment formulas for two measures of carry cost: the number of digit positions changed and the total magnitude of the digit changes. In particular, the expected digit-magnitude cost at width m is exactly

    2 − 1/Uβ(m),

    which converges to the universal limiting mean of 2.

    The most distinctive part of the paper reverses the usual direction of the problem. Instead of starting with a numeration system and calculating its carry behaviour, it asks what can be recovered from the carry distribution itself. The limiting Hamming-cost distribution determines which digits of the canonical boundary are positive, while the digit-magnitude distribution reconstructs the complete boundary sequence. Within the canonical greedy model, the observable carry statistics therefore determine the underlying canonical boundary.

    The theory does not require the boundary to be periodic. For Parry systems, where the boundary is eventually periodic, the limiting probability generating functions reduce to explicit rational forms. Worked examples include decimal, Fibonacci and Tribonacci numeration, together with a non-simple Parry system.

  • Automaton Minimization and Canonical 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)
    Download verification package (zip)

    Abstract

    Canonical positive linear recurrence numeration systems may admit multiple coefficient presentations that generate the same place-value sequence. For every place-value sequence (Hn), we define an intrinsic sequence e = (ei)i≥1 through the triangular valuation identities

    Hn+1 − 1 = ∑i=1n eiHn+1−i.

    We prove that this intrinsic sequence coincides with the periodic maximal boundary sequence associated with any coefficient presentation of (Hn). This yields an exact classification of equivalent presentations: a positive integer r is the order of a coefficient presentation if and only if r is a period of e, and the corresponding presentation is uniquely

    (e1, …, er−1, er + 1).

    In particular, the canonical reduction is recovered from the primitive period of e.

    The main structural consequence is language invariance. Although equivalent coefficient presentations generally define different recursive legality grammars and may have different breakpoint decompositions, we prove that they generate exactly the same language of legal representations. Every equivalent presentation is an iterated lift of the canonical reduction, and a general lift-invariance theorem shows that these lifts preserve the accepted language.

    Thus the place-value sequence determines the intrinsic boundary sequence, the complete family of equivalent coefficient presentations, the canonical reduction, and the associated legality language. The paper also resolves the boundary-to-canonical-reduction reconstruction question arising from the preceding carry-theoretic analysis.