This paper develops a finite-sample reconstruction theory for carry propagation in canonical -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 m decoder digits with probability at least from 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 scaling and the necessity of certification.
Tag: beta numeration
-
Exact Carry-Propagation Distributions and Boundary Reconstruction in Canonical Beta Numeration
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.