Dynamics
Theorem 5.16 (Exact recurrences for the three
branches). Fix 𝑛 ≥5. Among
the quotient sums over subsets of {2,…,𝑛 −1}, let 𝐷𝑛 give the largest sum at most 𝑇𝑛 and let 𝐵𝑛 give the smallest sum strictly
greater than 𝑇𝑛. Thus 𝐷𝑛 is the greedy support already
defined. Put
𝑟=rem(𝑛),𝑜=𝑄(𝐵𝑛,2𝑛)−𝑇𝑛,
and define the two correction terms by
𝑝−=∑𝑑∈𝐷𝑛(2𝟏𝑑∣2𝑛+1+𝟏𝑑∣2𝑛+2),𝑝+=∑𝑑∈𝐵𝑛(2𝟏𝑑∣2𝑛+1+𝟏𝑑∣2𝑛+2).
Both
lie in [0,2(𝑛 −2)], since 𝑑 ≥2 cannot divide both consecutive
integers. The next remainder is
rem(𝑛+1)={2𝑛+1−4𝑜−𝑝+,if 4𝑜+𝑝+≤2𝑛+1(U),4𝑟+2𝑛+1−𝑝−,if not U and 4𝑟+2𝑛+1−𝑝−<2𝑛+2+4(M),4𝑟−2𝑛+1−𝑝−−4,otherwise(R).
Consequently, for 𝜆𝑛 =(rem(𝑛) −2𝑛)/2𝑛,
𝜆𝑛+1={−(4𝑜+𝑝+)/2𝑛+1,U,2𝜆𝑛+2−𝑝−/2𝑛+1,M,2𝜆𝑛−(𝑝−+4)/2𝑛+1,R.(III)
Proof. Applying the one-step quotient identity twice gives
𝑞(2𝑛+2,𝑑)=4𝑞(2𝑛,𝑑)+2𝟏𝑑∣2𝑛+1+𝟏𝑑∣2𝑛+2.
The new
capacity is 𝑇𝑛+1 =4𝑇𝑛 +2𝑛+1,
and the new terminal weight, at exponent 𝑛, is 𝑞(2𝑛 +2,𝑛) =2𝑛+2 +4. Write 𝑔 =2𝑛+1. The old quotient sums are
separated by at least 𝑔, so the
corrected sums remain separated by at least 4𝑔 −2(𝑛 −2) >2𝑔 +4. This exceeds the new
terminal weight. The upper word exists: already the terms at 𝑑 =2,3,4 have sum greater than 𝑇𝑛 for 𝑛 ≥5, since 1/3 +1/7 +1/15 =19/35 >1/2 and their total
floor error is less than 3.
Consequently, adding the terminal weight to a lower old word cannot pass
the next corrected old word. Moreover, the increment 𝑇𝑛+1 −4𝑇𝑛 =𝑔 is smaller than this
separation, so no old word beyond the adjacent upper one can fit. It is
therefore enough to compare the two adjacent old words and the terminal
weight. The upper word fits precisely under the condition U; its remainder is then too
small to take the terminal weight. Otherwise the lower word is used, and
comparison with the terminal weight gives M or R. Substitution yields the
displayed formulas. ◻
Only the M and R formulas have the asserted
small correction to a fixed affine map. To rewrite U in that form, let 𝛾𝑛 =𝑟 +𝑜 −2𝑛+1 ≥0 be the excess of
the actual adjacent spacing over its lower bound. Then
𝜆𝑛+1=2𝜆𝑛−2−4𝛾𝑛+𝑝+2𝑛+1(U).
There is no 𝑂(𝑛) bound
on 𝛾𝑛 supplied by the
separation inequality. At 𝑛 =13,
exact calculation gives
𝑟=15147,𝑜=3997,𝑝+=4,𝛾13=2760,rem(14)=392.
Thus 𝜆14 −2𝜆13 +2 = −2761/4096.
In particular, the proposed uniform error bound |𝛿𝑛| ≤(2𝑛 +6)2−𝑛 in a
three-branch signed-digit formula is false already at this row. The
adjacent-spacing term cannot be absorbed into the divisor
correction.
Iterating the R formula
is still legitimate along a run of right branches. Its accumulated
correction and endpoint indices must be retained in a reset estimate.
These exact recurrences do not identify the proposed ceiling 𝐿𝑟 <(𝑟 −3)/2 with a converse to the
conditional reset square-root estimate.