Supplementary material. Reproducibility archive: 10.5281/zenodo.23593788 .
Introduction and main results
Changing a finite initial block in a nested recurrence changes which parts of the past are read, not merely the first few values. Here this mechanism produces an explicit family Q p Q_p Q p , indexed by integers p ≥ 2 p \ge2 p ≥ 2 , with any prescribed odd number 2 p − 1 2p-1 2 p − 1 of signed excursions per natural scale. All members use the same recurrence; the parameter enters only through the initial block. Their elementary excursions have a common Gaussian limit, while their arrangement, finite transitions, and upper value multiplicities depend on the parameter.
The family and its global structure
Write
n p = { 8 , p = 2 , 6 p − 6 , p ≥ 3. n_p =
\begin{cases}
8, & p=2,\\
6p-6, & p\ge3.
\end{cases} n p = { 8 , 6 p − 6 , p = 2 , p ≥ 3.
We prescribe every value Q p ( n ) Q_p(n) Q p ( n ) for 1 ≤ n < n p 1 \le n < n_p 1 ≤ n < n p and then apply
Q p ( n ) = Q p ( n − Q p ( n − 1 ) ) + Q p ( n − Q p ( n − 2 ) ) − ( − 1 ) n , n ≥ n p . (1) Q_p(n)=Q_p\left(n-Q_p(n-1)\right)+Q_p\left(n-Q_p(n-2)\right)-(-1)^n,\qquad n\ge n_p. \tag*{(1)} Q p ( n ) = Q p ( n − Q p ( n − 1 ) ) + Q p ( n − Q p ( n − 2 ) ) − ( − 1 ) n , n ≥ n p . (1)
For p = 2 p=2 p = 2 the prescribed block is ( 1 , 1 , 3 , 3 , 3 , 3 , 5 ) (1,1,3,3,3,3,5) ( 1 , 1 , 3 , 3 , 3 , 3 , 5 ) . The three-arch member Q 2 Q_2 Q 2 is recorded in the On-Line Encyclopedia of Integer Sequences as A401334 [10 ] . For p ≥ 3 p\ge3 p ≥ 3 , put m = ⌈ n / 2 ⌉ m=\lceil n/2\rceil m = ⌈ n /2 ⌉ and prescribe, for 1 ≤ n ≤ 6 p − 7 1\le n\le6p-7 1 ≤ n ≤ 6 p − 7 ,
Q p ( n ) = { 2 min ( m − 1 , p − 1 ) + 1 , m < p + 2 , 2 p + 2 ⌈ ( m − p − 2 ) / 2 ⌉ + 1 , m ≥ p + 2 , n odd , 2 p + 2 ⌊ ( m − p − 2 ) / 2 ⌋ + 1 , m ≥ p + 2 , n even . (2) Q_p(n)=
\begin{cases}
2\min(m-1,p-1)+1, & m<p+2,\\
2p+2\left\lceil(m-p-2)/2\right\rceil+1, & m\ge p+2,\ n\text{ odd},\\
2p+2\left\lfloor(m-p-2)/2\right\rfloor+1, & m\ge p+2,\ n\text{ even}.
\end{cases} \tag*{(2)} Q p ( n ) = ⎩ ⎨ ⎧ 2 min ( m − 1 , p − 1 ) + 1 , 2 p + 2 ⌈ ( m − p − 2 ) /2 ⌉ + 1 , 2 p + 2 ⌊ ( m − p − 2 ) /2 ⌋ + 1 , m < p + 2 , m ≥ p + 2 , n odd , m ≥ p + 2 , n even . (2)
The entire block is part of the definition: the recurrence must not be applied before n p n_p n p . Each recursive argument must belong to { 1 , … , n − 1 } \{1,\ldots,n-1\} { 1 , … , n − 1 } ; no values at zero or at negative indices are supplied.
Theorem 1.1 (Global odd-arch family). For every integer p ≥ 2 p\ge2 p ≥ 2 , the initial block above and (1) determine a unique sequence for all positive indices. All values are odd, and
1 ≤ Q p ( n ) ≤ n , Q p ( n + 2 ) − Q p ( n ) ∈ { 0 , 2 } ( n ≥ 1 ) . (3) 1\le Q_p(n)\le n,\qquad Q_p(n+2)-Q_p(n)\in\{0,2\}\qquad(n\ge1). \tag*{(3)} 1 ≤ Q p ( n ) ≤ n , Q p ( n + 2 ) − Q p ( n ) ∈ { 0 , 2 } ( n ≥ 1 ) . (3) Each parity subsequence assumes every positive odd value, each only finitely often. The independently constructed block words satisfy
U p , k = ( A k A ‾ k + 1 ) p − 1 A k + 2 ( k ≥ 2 ) , (4) U_{p,k}=(A_k\overline{A}_{k+1})^{p-1}A_{k+2}\qquad(k\ge2), \tag*{(4)} U p , k = ( A k A k + 1 ) p − 1 A k + 2 ( k ≥ 2 ) , (4) where the primitive Dyck words A k A_k A k are defined in (9) and have length ℓ k = ( 2 k + 2 ( − 1 ) k ) / 3 \ell_k=(2^k+2(-1)^k)/3 ℓ k = ( 2 k + 2 ( − 1 ) k ) /3 . A bar is bitwise complementation, not reversal. Consequently each natural block has exactly 2 p − 1 2p-1 2 p − 1 primitive signed excursions, with asymptotic relative lengths 1 , 2 , … , 1 , 2 , 4 1,2,\ldots,1,2,4 1 , 2 , … , 1 , 2 , 4 .
The proof in § 3 constructs the words and two slow cores before checking any nested identity. In particular, existence is not assumed in order to establish the block structure. The first three members are the three-, five-, and seven-arch sequences Q 2 Q_2 Q 2 , Q 3 Q_3 Q 3 , Q 4 Q_4 Q 4 :
Table 3.
Shape, finite transitions, frequencies, and summation
The common elementary profile is
J ( x ) = φ ( Φ − 1 ( x ) ) , 0 < x < 1 , J ( 0 ) = J ( 1 ) = 0 , J(x)=\varphi\left(\Phi^{-1}(x)\right),\qquad0<x<1,\qquad J(0)=J(1)=0, J ( x ) = φ ( Φ − 1 ( x ) ) , 0 < x < 1 , J ( 0 ) = J ( 1 ) = 0 ,
where φ \varphi φ and Φ \Phi Φ are the standard normal density and distribution function. § 4 proves uniform convergence of the normalized elementary heights. § 5 combines these limits at the exact block positions and obtains an explicit standard dyadic profile P p P_p P p . For each fixed p p p and index parity r r r ,
( − 1 ) j + r p j ( Q p ( n ) n − 1 2 ) ⟶ P p ( n / 2 j ) (-1)^{j+rp}\sqrt{j}\left(\frac{Q_p(n)}{n}-\frac{1}{2}\right)\longrightarrow P_p(n/2^j) ( − 1 ) j + r p j ( n Q p ( n ) − 2 1 ) ⟶ P p ( n / 2 j )
uniformly on 2 j ≤ n ≤ 2 j + 1 2^j\le n\le2^{j+1} 2 j ≤ n ≤ 2 j + 1 along that parity, in the precise sampling convention of Theorem 5.1 . There are exactly 2 p − 1 2p-1 2 p − 1 limiting sign transitions. The sharp envelope is
lim sup n → ∞ log 2 n ∣ Q p ( n ) n − 1 2 ∣ = Λ p = b p 2 , b p ( 3 p − 1 2 + Φ ( − b p ) ) = φ ( b p ) , \limsup_{n\to\infty}\sqrt{\log_2 n}\left|\frac{Q_p(n)}{n}-\frac{1}{2}\right|=\Lambda_p=\frac{b_p}{2},\qquad b_p\left(\frac{3p-1}{2}+\Phi(-b_p)\right)=\varphi(b_p), n → ∞ lim sup log 2 n n Q p ( n ) − 2 1 = Λ p = 2 b p , b p ( 2 3 p − 1 + Φ ( − b p ) ) = φ ( b p ) ,
with a unique positive root b p b_p b p . In particular, Λ p ∼ 1 / ( 3 p 2 π ) \Lambda_p\sim1/(3p\sqrt{2\pi}) Λ p ∼ 1/ ( 3 p 2 π ) as p → ∞ p\to\infty p → ∞ . This last assertion concerns the constants after the fixed-p p p limit; no simultaneous limit in p p p and n n n is asserted.
The finite structure contains more information than the profile alone. § 6 gives exact finite zero and crossing tables. For p ≥ 3 p\ge3 p ≥ 3 and j ≥ p + ⌊ log 2 p ⌋ + 10 j\ge p+\lfloor\log_2p\rfloor+10 j ≥ p + ⌊ log 2 p ⌋ + 10 , the j j j -th standard block has exactly 2 p − 1 2p-1 2 p − 1 even-index zeros, all transverse. The four/six-zero alternation at p = 2 p=2 p = 2 is a genuine exceptional feature, not a universal rule.
For ν p ( v ) = # { n ≥ 1 : Q p ( n ) = v } \nu_p(v)=\#\{n\ge1:Q_p(n)=v\} ν p ( v ) = # { n ≥ 1 : Q p ( n ) = v } , define
D p , j ( z ) = ∑ u = 2 j 2 j + 1 − 1 z ν p ( 2 u + 1 ) . D_{p,j}(z)=\sum_{u=2^j}^{2^{j+1}-1}z^{\nu_p(2u+1)}. D p , j ( z ) = u = 2 j ∑ 2 j + 1 − 1 z ν p ( 2 u + 1 ) .
§ 7 derives both the ordered frequency words and their histograms. The normalized limit is always z 3 / ( 2 − z ) z^3/(2-z) z 3 / ( 2 − z ) , but the finite upper tail changes with p p p . With d = ⌊ log 2 p ⌋ d=\lfloor\log_2p\rfloor d = ⌊ log 2 p ⌋ , the exact moments on j ≥ d + 2 j\ge d+2 j ≥ d + 2 are
E X p , j = 4 − 2 − j , Var ( X p , j ) = 2 − ( 2 ( j − d ) + 4 p − 5 ) 2 − j − 4 − j . \mathbb{E}X_{p,j}=4-2^{-j},\qquad\operatorname{Var}(X_{p,j})=2-\left(2(j-d)+4p-5\right)2^{-j}-4^{-j}. E X p , j = 4 − 2 − j , Var ( X p , j ) = 2 − ( 2 ( j − d ) + 4 p − 5 ) 2 − j − 4 − j .
Theorem 7.5 gives all coefficients, split according to whether p p p is a power of two. The following results determine exact total-variation distances and every location of the two highest multiplicities. A worked p = 3 p=3 p = 3 example makes the join correction and the dyadic cuts explicit before the general histogram formulas.
Finally, § 8 proves an exact telescoping identity and, with C p = 2 ( 3 p + 1 ) / 3 C_p=2(3p+1)/3 C p = 2 ( 3 p + 1 ) /3 ,
∑ n ≤ N Q p ( n ) = N 2 4 + N 2 log 2 N + N Ψ p ( { log 2 ( N / C p ) } ) + O p ( N log N ) . \sum_{n\le N}Q_p(n)=\frac{N^2}{4}+\frac{N}{2}\log_2N+N\Psi_p(\{\log_2(N/C_p)\})+O_p\left(\frac{N}{\sqrt{\log N}}\right). n ≤ N ∑ Q p ( n ) = 4 N 2 + 2 N log 2 N + N Ψ p ({ log 2 ( N / C p )}) + O p ( log N N ) .
where Ψ p ( θ ) = p − 1 − 1 2 log 2 C p − θ 2 − 2 − θ \Psi_p(\theta)=p-1-\frac{1}{2}\log_2C_p-\frac{\theta}{2}-2^{-\theta} Ψ p ( θ ) = p − 1 − 2 1 log 2 C p − 2 θ − 2 − θ on [ 0 , 1 ] [0,1] [ 0 , 1 ] , extended continuously with period one. Thus the logarithmic bias and the periodic shape are shared by the family, while the phase scale and vertical constant are explicit functions of p p p .
Context and organization
Hofstadter introduced the unperturbed Q Q Q -recursion in Gödel, Escher, Bach [4 ] . For related nested recurrences, explicit combinatorial descriptions have often supplied the missing control of the self-referential arguments. Tanny [11 ] analyzed a monotone relative; Balamohan, Kuznetsov, and Tanny [1 ] obtained a complete description of another variant through its generations and value frequencies. Tree representations provide a further source of exact solutions [5 ] . These examples suggest looking for a finite combinatorial evolution behind the numerical sequence.
The original parity-perturbed recursion was introduced by the present author [6 ] and is recorded as OEIS A394051 [9 ] . It starts with ( 1 , 1 ) (1,1) ( 1 , 1 ) and adds + ( − 1 ) n +(-1)^n + ( − 1 ) n to the two nested terms. Cloitre [3 ] proved its global definedness and the optimal error order n / log n n/\sqrt{\log n} n / log n by an exact-fit interleaving construction, binary heights, and canonical plane forests. The same framework led to a dyadic frequency law [6 ] . A subsequent analysis of the associated two-variable zeta function identified a periodic summatory term and a weak Gaussian limit for a distinguished family of layers [7 ] .
A related delayed perturbation admits uniform Gaussian profiles through nonlinear averaging and smooth comparison functions [8 ] . Here the elementary lengths alternate between 2 L + 2 2L+2 2 L + 2 and 2 L − 2 2L-2 2 L − 2 . An exact change of coordinates removes both the length correction and the additive height term, allowing that comparison method to treat the two maps within one identity.
Our construction uses Cloitre’s exact-fit framework. In particular, the tape counters and height additivity come from [3 Definition 2.3 and Lemmas 2.4–2.5] , and the parked-head verification follows [3 Lemmas 3.3–3.4] . On Dyck inputs, S + S_+ S + agrees with Cloitre’s transform T T T ; if P = 0 R 1 P=0R1 P = 0 R 1 is primitive Dyck, then S − ( P ) = T ( R ) S_-(P)=T(R) S − ( P ) = T ( R ) [3 Section 4.1] . The elementary excursions are inherited. The contribution here is their repeated signed-pair organization, its explicit finite seeds and block positions, and the resulting parameter-dependent shape, crossing, frequency, and summation laws. § 9 gives the exact identification with the original word family and separates the inherited tools from these results.
The main text develops the general parameter p p p throughout. Appendix § 11 records the detailed p = 2 p=2 p = 2 formulas, including its exceptional tangencies, pure valuation histogram, and worked finite crossing example. This retains the three-arch model as an explicit specialization rather than as a prerequisite for the familial construction.
Figure 1. The three explicit limiting standard-block profiles for p = 2 , 3 , 4 p=2,3,4 p = 2 , 3 , 4 . The same elementary Gaussian function produces distinct arrangements and different sharp amplitudes.
Causal word maps and elementary excursions
For a binary word P P P of length L L L , let o P ( t ) o_P(t) o P ( t ) and z P ( t ) z_P(t) z P ( t ) count ones and zeros in its prefix of length t t t , and let
h P ( t ) = z P ( t ) − o P ( t ) , 0 ≤ t ≤ L . h_P(t)=z_P(t)-o_P(t), \qquad0\leq t\leq L. h P ( t ) = z P ( t ) − o P ( t ) , 0 ≤ t ≤ L .
Positions in words are indexed from zero. A word is balanced when it has equally many zeros and ones. It is a primitive Dyck word when it is balanced and h P ( t ) > 0 h_P(t)>0 h P ( t ) > 0 at every integer 0 < t < L 0<t<L 0 < t < L . A bar denotes bitwise complementation, not reversal.
The following strict machine is the exact-fit case of [3 Definition 2.3] . No exhausted-tape fallback is needed for the words used here.
Definition 2.1 (Strict interleaving and the two maps). The machine I 0 ( X , Y ) \mathcal{I}_0(X,Y) I 0 ( X , Y ) starts in state zero. In state zero it reads and emits the next symbol of X X X ; in state one it does the same with Y Y Y . The emitted bit is the next state. The machine stops when both tapes have been consumed. Reading a designated tape which is already empty before that time is a failure: there is no fallback rule. For a balanced word beginning in zero and ending in one, define
S + ( P ) = I 0 ( 0 P 1 , P ) , S − ( P ) = I 0 ( P , P [ 1 : − 1 ] ) . (5) S_+(P)=\mathcal{I}_0(0P1,P),\qquad S_-(P)=\mathcal{I}_0(P,P[1:-1]). \tag*{(5)} S + ( P ) = I 0 ( 0 P 1 , P ) , S − ( P ) = I 0 ( P , P [ 1 : − 1 ]) . (5) Here P [ 1 : − 1 ] P[1:-1] P [ 1 : − 1 ] deletes its initial zero and final one. The first map also applies to the balanced seeds ( 10 ) p − 1 01 (10)^{p-1}01 ( 10 ) p − 1 01 for p ≥ 2 p\geq2 p ≥ 2 ; the exceptional seed 1001 is the case p = 2 p=2 p = 2 .
Lemma 2.2 (Causality and primitive excursions). Both maps in (5) are defined, balanced, begin in zero and end in one. Their lengths are 2 L + 2 2L+2 2 L + 2 and 2 L − 2 2L-2 2 L − 2 , respectively. Both preserve primitive Dyck words. The map S + S_+ S + is also defined on any balanced word ending in one, regardless of its first symbol.
Proof. After a nonempty output prefix let i , j i,j i , j be the tape counters, z , o z,o z , o the output counts, and c c c the last bit. Counting the states before successive reads, as in [3 Lemma 2.5] , gives
i = z + c , j = o − c . (6) i=z+c,\qquad j=o-c. \tag*{(6)} i = z + c , j = o − c . (6)
For S + S_{+} S + , the total number of zeros and of ones is L + 1 L+1 L + 1 . A request to read an exhausted zero tape would have i = L + 2 i=L+2 i = L + 2 , c = 0 c=0 c = 0 , forcing too many zeros. An exhausted one tape with j = L j=L j = L , c = 1 c=1 c = 1 forces o = L + 1 o=L+1 o = L + 1 : all ones have been consumed. Since the zero tape ends in one, that tape must then also be exhausted. This is the legitimate stopping state. For S − S_{-} S − , replace these tape lengths by L L L , L − 2 L-2 L − 2 and the total counts by L − 1 L-1 L − 1 ; the same argument applies. Equation (6) at completion forces the final bit to be one. The first bit is zero.
For S + S_{+} S + the prefix height, while 1 ≤ i ≤ L + 1 1 \le i \le L+1 1 ≤ i ≤ L + 1 , is 1 + h P ( i − 1 ) + h P ( j ) > 0 1+h_P(i-1)+h_P(j)>0 1 + h P ( i − 1 ) + h P ( j ) > 0 if P P P is Dyck. If the zero tape has already finished, all zeros have been emitted, and the height equals the number of remaining output symbols. It is positive until completion. For S − S_{-} S − the height is
h P ( i ) + h P ( j + 1 ) − 1. h_P(i)+h_P(j+1)-1. h P ( i ) + h P ( j + 1 ) − 1.
Before the zero tape finishes, 1 ≤ i < L 1 \le i < L 1 ≤ i < L and 1 ≤ j + 1 ≤ L − 1 1 \le j+1 \le L-1 1 ≤ j + 1 ≤ L − 1 ; primitivity makes both parent heights at least one. After it finishes, the same remaining-length argument applies. This proves primitivity.
Let α i \alpha_i α i be the number of zeros immediately preceding the i i i -th one, back to the previous one or the word’s beginning. Let β i \beta_i β i be the number of ones after the i i i -th zero, up to the next zero or the end. The gaps may be zero. A balanced word of length 2 p 2p 2 p has p p p zeros and therefore p p p gaps of each kind.
Lemma 2.3 (Run expansions and symmetry). Let P P P be a balanced binary word of length 2 p 2p 2 p , beginning in zero and ending in one. For p ≥ 1 p \ge1 p ≥ 1 ,
S + ( P ) = 0 α 1 + 1 1 ( ∏ i = 1 p − 1 0 α i + 1 + 1 1 β i + 1 ) 01 β p + 1 . (7) S_{+}(P)=0^{\alpha_1+1}1\left(\prod_{i=1}^{p-1}0^{\alpha_{i+1}+1}1^{\beta_{i+1}}\right)01^{\beta_p+1}. \tag*{(7)} S + ( P ) = 0 α 1 + 1 1 ( i = 1 ∏ p − 1 0 α i + 1 + 1 1 β i + 1 ) 0 1 β p + 1 . (7) For p ≥ 2 p \ge2 p ≥ 2 ,
S − ( P ) = 0 α 1 1 β 1 + 1 ( ∏ i = 2 p − 1 0 α i + 1 1 β i + 1 ) 0 α p + 1 1 β p . (8) S_{-}(P)=0^{\alpha_1}1^{\beta_1+1}\left(\prod_{i=2}^{p-1}0^{\alpha_i+1}1^{\beta_i+1}\right)0^{\alpha_p+1}1^{\beta_p}. \tag*{(8)} S − ( P ) = 0 α 1 1 β 1 + 1 ( i = 2 ∏ p − 1 0 α i + 1 1 β i + 1 ) 0 α p + 1 1 β p . (8) For P = 01 P=01 P = 01 , one has S − ( P ) = 01 S_{-}(P)=01 S − ( P ) = 01 . If P P P equals its reverse-complement, both outputs do too. The initial zero-run and terminal one-run both gain one symbol under S + S_{+} S + and retain their lengths under S − S_{-} S − .
Proof. This is the two-map form of the gap transport in [3 Lemma 4.1] . A zero emitted from the one tape starts a new zero-run, and the zero tape then emits its next zero gap followed by the one ending that gap. The one tape continues the corresponding one-run. Tracking the two initializations and the tape ends gives the displayed expansions. Reverse-complement symmetry of P P P is equivalent to α i = β p + 1 − i \alpha_i=\beta_{p+1-i} α i = β p + 1 − i . The displayed run lengths then match in reverse order with zeros and ones exchanged. The outer-run statements follow from the first and last factors.
Define the elementary words and their lengths by
A 2 = 01 , A k + 1 = { S + ( A k ) , k odd , S − ( A k ) , k even , ℓ k = ∣ A k ∣ = 2 k + 2 ( − 1 ) k 3 ( k ≥ 2 ) . (9) A_2=01,\qquad A_{k+1}=\begin{cases}S_{+}(A_k),& k\ \text{odd},\\ S_{-}(A_k),& k\ \text{even},\end{cases}\qquad\ell_k=|A_k|=\frac{2^k+2(-1)^k}{3}\quad(k\ge2). \tag*{(9)} A 2 = 01 , A k + 1 = { S + ( A k ) , S − ( A k ) , k odd , k even , ℓ k = ∣ A k ∣ = 3 2 k + 2 ( − 1 ) k ( k ≥ 2 ) . (9)
Thus A 3 = 01 A_3=01 A 3 = 01 , A 4 = 001011 A_4=001011 A 4 = 001011 , and A 5 = 0010011011 A_5=0010011011 A 5 = 0010011011 . The length formula follows from ℓ k + 1 = 2 ℓ k − 2 ( − 1 ) k \ell_{k+1}=2\ell_k-2(-1)^k ℓ k + 1 = 2 ℓ k − 2 ( − 1 ) k . All A k A_k A k are primitive and reverse-complement symmetric. Their initial zero-run and terminal one-run have length ⌈ k / 2 ⌉ \lceil k/2\rceil ⌈ k /2 ⌉ .
Lemma 2.4 (Concatenation transport). For balanced words P P P , R R R , S S S beginning in zero and ending in one,
S + ( P R ‾ S ) = S + ( P ) S − ( R ) ‾ S + ( S ) , (10) S_{+}(P\overline{R}S)=S_{+}(P)\,\overline{S_{-}(R)}\,S_{+}(S), \tag*{(10)} S + ( P R S ) = S + ( P ) S − ( R ) S + ( S ) , (10) S − ( P R ‾ S ) = S − ( P ) S + ( R ) ‾ S − ( S ) . (11) S_{-}(P\overline{R}S)=S_{-}(P)\,\overline{S_{+}(R)}\,S_{-}(S). \tag*{(11)} S − ( P R S ) = S − ( P ) S + ( R ) S − ( S ) . (11)
Proof. In (10) , the first output segment uses 0 P 1 0P1 0 P 1 from the zero tape and P P P from the one tape. The terminal one on the first tape is borrowed from the first bit of R ‾ \overline{R} R . The state is now one. Complementing the output and exchanging the roles of the tapes makes the next segment exactly S − ( R ) ‾ \overline{S_{-}(R)} S − ( R ) : the two consumed pieces are R R R and its interior. This leaves the last zero of R ‾ \overline{R} R on the original zero tape. The state returns to zero and the remaining tapes are 0 S 1 0S1 0 S 1 , S S S , giving S + ( S ) S_{+}(S) S + ( S ) .
For (11) , the first segment consumes P P P and the interior of P P P , leaving its terminal one on the one tape. In state one, complementation and tape exchange give S + ( R ) S_{+}(R) S + ( R ) ; its extra terminal one is borrowed from the complement of the initial zero of S S S . The remaining original tapes are S S S , S [ 1 : − 1 ] S[1:-1] S [ 1 : − 1 ] in state zero. All segment computations are causal by Lemma 2.2 , so these concatenations also verify the strict reading convention at each join.
Construction and global existence of the family
Block positions and independent cores
Fix an integer p ≥ 2 p \ge2 p ≥ 2 and set
c p = 3 p + 1 , C p = 2 c p 3 , U p , 1 = ( 10 ) p − 1 01 , c_p=3p+1,\qquad C_p=\frac{2c_p}{3},\qquad U_{p,1}=(10)^{p-1}01, c p = 3 p + 1 , C p = 3 2 c p , U p , 1 = ( 10 ) p − 1 01 ,
L p , k = c p 2 k + 2 ( − 1 ) k 3 , a p , k = c p 2 k − 3 − ( − 1 ) k 6 , L_{p,k}=\frac{c_p2^k+2(-1)^k}{3},\qquad a_{p,k}=\frac{c_p2^k-3-(-1)^k}{6}, L p , k = 3 c p 2 k + 2 ( − 1 ) k , a p , k = 6 c p 2 k − 3 − ( − 1 ) k ,
d p , k = p − 2 + ⌊ k − 1 2 ⌋ , s p , k = 2 a p , k − d p , k . (12) d_{p,k}=p-2+\left\lfloor\frac{k-1}{2}\right\rfloor,\qquad s_{p,k}=2a_{p,k}-d_{p,k}. \tag*{(12)} d p , k = p − 2 + ⌊ 2 k − 1 ⌋ , s p , k = 2 a p , k − d p , k . (12)
Advance U p , k U_{p,k} U p , k by S + S_{+} S + for odd k k k and by S − S_{-} S − for even k k k . The two cores are first defined independently of any nested recursion:
F p ( m ) = G p ( m ) = min ( m − 1 , p − 1 ) ( 1 ≤ m < p + 2 ) . F_p(m)=G_p(m)=\min(m-1,p-1)\qquad(1\le m<p+2). F p ( m ) = G p ( m ) = min ( m − 1 , p − 1 ) ( 1 ≤ m < p + 2 ) .
On the k k k -th block, with o = o U p , k o=o_{U_{p,k}} o = o U p , k and z = z U p , k z=z_{U_{p,k}} z = z U p , k , put
F p ( s p , k + t ) = a p , k + o ( t ) , G p ( s p , k + t ) = a p , k + z ( t ) k odd , 0 ≤ t ≤ L p , k , F p ( s p , k + t ) = a p , k + z ( t ) , G p ( s p , k + t ) = a p , k + o ( t + 1 ) k even , 0 ≤ t < L p , k . (13) \begin{aligned}
F_p(s_{p,k}+t)&=a_{p,k}+o(t),\qquad G_p(s_{p,k}+t)=a_{p,k}+z(t)
&& k\ \text{odd},\quad0\le t\le L_{p,k},\\
F_p(s_{p,k}+t)&=a_{p,k}+z(t),\qquad G_p(s_{p,k}+t)=a_{p,k}+o(t+1)
&& k\ \text{even},\quad0\le t<L_{p,k}. \tag*{(13)}
\end{aligned} F p ( s p , k + t ) F p ( s p , k + t ) = a p , k + o ( t ) , G p ( s p , k + t ) = a p , k + z ( t ) = a p , k + z ( t ) , G p ( s p , k + t ) = a p , k + o ( t + 1 ) k odd , 0 ≤ t ≤ L p , k , k even , 0 ≤ t < L p , k . (13)
Finally define
Q p ( 2 m − 1 ) = 2 F p ( m ) + 1 , Q p ( 2 m ) = 2 G p ( m ) + 1. (14) Q_p(2m-1)=2F_p(m)+1,\qquad Q_p(2m)=2G_p(m)+1. \tag*{(14)} Q p ( 2 m − 1 ) = 2 F p ( m ) + 1 , Q p ( 2 m ) = 2 G p ( m ) + 1. (14)
The case p = 2 p=2 p = 2 is the three-arch sequence detailed in Appendix § 11 .
The initial word is balanced and ends in one. Its first plus transform is causal by Lemma 2.2 ; all later words begin in zero and end in one, so both maps remain causal. The definitions satisfy
a p , k + 1 = a p , k + L p , k / 2 , s p , k + 1 − s p , k = L p , k − 1 { k e v e n } , s p , k − a p , k = s p , k − 1 ( k ≥ 2 ) . (15) a_{p,k+1}=a_{p,k}+L_{p,k}/2,
\qquad
s_{p,k+1}-s_{p,k}=L_{p,k}-\mathbf{1}_{\{k\ \mathrm{even}\}},
\qquad
s_{p,k}-a_{p,k}=s_{p,k-1}\qquad(k\ge2). \tag*{(15)} a p , k + 1 = a p , k + L p , k /2 , s p , k + 1 − s p , k = L p , k − 1 { k even } , s p , k − a p , k = s p , k − 1 ( k ≥ 2 ) . (15)
Consequently the two core definitions agree at shared endpoints. At s p , 1 = p + 2 s_{p,1}=p+2 s p , 1 = p + 2 both cores rise from p − 1 p-1 p − 1 to p p p . All subsequent increments are zero or one. The cores are unbounded and satisfy
0 ≤ F p ( m ) , G p ( m ) ≤ m − 1 ( m ≥ 1 ) , 1 ≤ F p ( m ) , G p ( m ) ≤ m − 2 ( m ≥ p + 1 ) . (16) 0\le F_p(m),G_p(m)\le m-1\qquad(m\ge1),
\qquad
1\le F_p(m),G_p(m)\le m-2\qquad(m\ge p+1). \tag*{(16)} 0 ≤ F p ( m ) , G p ( m ) ≤ m − 1 ( m ≥ 1 ) , 1 ≤ F p ( m ) , G p ( m ) ≤ m − 2 ( m ≥ p + 1 ) . (16)
The second upper bound follows from the repeated value p − 1 p-1 p − 1 at m = p , p + 1 m=p,p+1 m = p , p + 1 and the unit-step property. No nested recursion has been used.
Exact coupled recursions
Proposition 3.1 (Coupled identities on every subsequent block). For every p ≥ 2 p\ge2 p ≥ 2 and m > s p , 2 = 3 p + 2 m>s_{p,2}=3p+2 m > s p , 2 = 3 p + 2 , the word-defined cores satisfy
F p ( m ) = G p ( m − G p ( m − 1 ) − 1 ) + G p ( m − F p ( m − 1 ) − 1 ) + 1 , (17) F_p(m)=G_p\bigl(m-G_p(m-1)-1\bigr)+G_p\bigl(m-F_p(m-1)-1\bigr)+1, \tag*{(17)} F p ( m ) = G p ( m − G p ( m − 1 ) − 1 ) + G p ( m − F p ( m − 1 ) − 1 ) + 1 , (17)
G p ( m ) = F p ( m − F p ( m ) ) + F p ( m − G p ( m − 1 ) ) . (18) G_p(m)=F_p\bigl(m-F_p(m)\bigr)+F_p\bigl(m-G_p(m-1)\bigr). \tag*{(18)} G p ( m ) = F p ( m − F p ( m ) ) + F p ( m − G p ( m − 1 ) ) . (18)
All arguments lie in { 1 , … , m − 1 } \{1,\ldots,m-1\} { 1 , … , m − 1 } .
Proof. Fix p p p and suppress it temporarily in F , G , U k , a k , s k , L k F,G,U_k,a_k,s_k,L_k F , G , U k , a k , s k , L k . The bounds in (16) put the two arguments in (3.7) in [ 2 , m − 2 ] [2,m-2] [ 2 , m − 2 ] and those in (3.8) in [ 2 , m − 1 ] [2,m-1] [ 2 , m − 1 ] and [ 3 , m − 1 ] [3,m-1] [ 3 , m − 1 ] , respectively. We verify the identities on s k < m ≤ s k + 1 s_k<m\le s_{k+1} s k < m ≤ s k + 1 for every k ≥ 2 k\ge2 k ≥ 2 , assigning a shared endpoint to its left block. Both core formulas equal a k + 1 a_{k+1} a k + 1 at that endpoint, so this convention agrees with their independent definition.
Here is the precise parked-head observation used below, in the form of [3 Lemmas 3.3–3.4] . Suppose that o − , z − o_-,z_- o − , z − are the counts before the t t t -th output, with t ≥ 1 t\ge1 t ≥ 1 . The counters immediately after that output are
i = z − + 1 , j = o − . (19) i=z_-+1,\qquad j=o_-. \tag*{(19)} i = z − + 1 , j = o − . (19)
Indeed, (6) gives the counters before the read; the read increments i i i if the old state is zero and j j j if it is one. This also holds for t = 1 t=1 t = 1 , when both counters and the old state are zero. If the new output bit is one, the last symbol consumed from the zero tape is one: it either produced this output or initiated the current succession of reads from the one tape. During those reads the zero tape remains parked at that symbol.
In the following table, s ′ = s k − 1 s'=s_{k-1} s ′ = s k − 1 , and the entries are the inner arguments minus s ′ s' s ′ . We abbreviate the child prefix counts by o = o ( t ) o=o(t) o = o ( t ) , z = z ( t ) z=z(t) z = z ( t ) , o − = o ( t − 1 ) o_-=o(t-1) o − = o ( t − 1 ) , and z − = z ( t − 1 ) z_-=z(t-1) z − = z ( t − 1 ) .
Table 4.
We verify both the values and the domains in each row.
Odd k ≥ 3 k \ge3 k ≥ 3 . Let P = U k − 1 P = U_{k-1} P = U k − 1 , ℓ = ∣ P ∣ \ell= |P| ℓ = ∣ P ∣ , and b P ( u ) = o P ( u ) b_P(u) = o_P(u) b P ( u ) = o P ( u ) for 0 ≤ u ≤ ℓ 0 \le u \le\ell 0 ≤ u ≤ ℓ . The parent base is b = ( ℓ − 2 ) / 2 b = (\ell- 2)/2 b = ( ℓ − 2 ) /2 , the child base is a k = ℓ − 1 a_k = \ell- 1 a k = ℓ − 1 , and s k − a k = s ′ s_k - a_k = s' s k − a k = s ′ . The child is S − ( P ) S_-(P) S − ( P ) , of length 2 ℓ − 2 2\ell- 2 2 ℓ − 2 , and the range to be checked is
m = s k + t , 1 ≤ t ≤ 2 ℓ − 2. m = s_k + t, \qquad1 \le t \le2\ell- 2. m = s k + t , 1 ≤ t ≤ 2 ℓ − 2.
The parent begins in zero, so the ones in a prefix of length j j j of its interior number b P ( j + 1 ) b_P(j + 1) b P ( j + 1 ) . Counting the ones read from the two tapes using (19) gives
o ( t ) = b P ( z − + 1 ) + b P ( o − + 1 ) . (20) o(t) = b_P(z_- + 1) + b_P(o_- + 1). \tag*{(20)} o ( t ) = b P ( z − + 1 ) + b P ( o − + 1 ) . (20)
On the parent even block,
G ( s ′ + u ) = b + b P ( u + 1 ) , F ( s ′ + u ) = b + u − b P ( u ) ( 0 ≤ u ≤ ℓ − 1 ) . G(s' + u) = b + b_P(u + 1), \qquad F(s' + u) = b + u - b_P(u) \qquad(0 \le u \le\ell- 1). G ( s ′ + u ) = b + b P ( u + 1 ) , F ( s ′ + u ) = b + u − b P ( u ) ( 0 ≤ u ≤ ℓ − 1 ) .
The first row of the table and (20) show that the right side of (17) equals 2 b + o ( t ) + 1 = a k + o ( t ) = F ( m ) 2b + o(t) + 1 = a_k + o(t) = F(m) 2 b + o ( t ) + 1 = a k + o ( t ) = F ( m ) .
For (18) , the required identity is
b P ( z ) + b P ( o − + 1 ) = o − . (21) b_P(z) + b_P(o_- + 1) = o_-. \tag*{(21)} b P ( z ) + b P ( o − + 1 ) = o − . (21)
If the t t t -th output is zero, then z = z − + 1 z = z_- + 1 z = z − + 1 and o ( t ) = o − o(t) = o_- o ( t ) = o − , so this is exactly (20) . If the output is one, then z = z − z = z_- z = z − and o ( t ) = o − + 1 o(t) = o_- + 1 o ( t ) = o − + 1 . The parked-head observation says that P [ z ] = 1 P[z] = 1 P [ z ] = 1 , with zero-based indexing; hence b P ( z + 1 ) − b P ( z ) = 1 b_P(z + 1) - b_P(z) = 1 b P ( z + 1 ) − b P ( z ) = 1 . Subtracting this one from (20) proves (21) . The parent F F F -formula now gives
F ( s ′ + z ) + F ( s ′ + o − + 1 ) = 2 b + z + o − + 1 − o − = a k + z = G ( m ) . F(s' + z) + F(s' + o_- + 1) = 2b + z + o_- + 1 - o_- = a_k + z = G(m). F ( s ′ + z ) + F ( s ′ + o − + 1 ) = 2 b + z + o − + 1 − o − = a k + z = G ( m ) .
All these uses of the parent formulas lie in their stated domains. Since the child has ℓ − 1 \ell- 1 ℓ − 1 zeros and ends in one, 0 ≤ o − ≤ ℓ − 2 0 \le o_- \le\ell- 2 0 ≤ o − ≤ ℓ − 2 and 0 ≤ z − , z ≤ ℓ − 1 0 \le z_-, z \le\ell- 1 0 ≤ z − , z ≤ ℓ − 1 . Thus the four parent coordinates belong to [ 0 , ℓ − 1 ] [0,\ell- 1] [ 0 , ℓ − 1 ] . At t = 1 t = 1 t = 1 , the two argument pairs are ( 0 , 0 ) (0,0) ( 0 , 0 ) and ( 1 , 1 ) (1,1) ( 1 , 1 ) ; at t = 2 ℓ − 2 t = 2\ell- 2 t = 2 ℓ − 2 , they are ( ℓ − 2 , ℓ − 1 ) (\ell- 2,\ell- 1) ( ℓ − 2 , ℓ − 1 ) and ( ℓ − 1 , ℓ − 1 ) (\ell- 1,\ell- 1) ( ℓ − 1 , ℓ − 1 ) . In particular the right endpoint of the parent block is included, and no value beyond it is used.
Even k ≥ 2 k \ge2 k ≥ 2 . The parent P = U k − 1 P = U_{k-1} P = U k − 1 now has length ℓ \ell ℓ , base b = ℓ / 2 b = \ell/2 b = ℓ /2 , and block length ℓ \ell ℓ . The child base is a k = ℓ a_k = \ell a k = ℓ , and s = s k = s ′ + ℓ s = s_k = s' + \ell s = s k = s ′ + ℓ . Its word S + ( P ) S_+(P) S + ( P ) has length 2 ℓ + 2 2\ell+ 2 2 ℓ + 2 , but its core block has length 2 ℓ + 1 2\ell+ 1 2 ℓ + 1 . Consequently we must check
m = s + t , 1 ≤ t ≤ 2 ℓ + 1. m = s + t, \qquad1 \le t \le2\ell+ 1. m = s + t , 1 ≤ t ≤ 2 ℓ + 1.
Define an auxiliary prefix count only at the additional tape position:
b ^ P ( u ) = b P ( u ) ( 0 ≤ u ≤ ℓ ) , b ^ P ( ℓ + 1 ) = b P ( ℓ ) + 1. \widehat{b}_P(u) = b_P(u) \quad(0 \le u \le\ell), \qquad\widehat{b}_P(\ell+ 1) = b_P(\ell) + 1. b P ( u ) = b P ( u ) ( 0 ≤ u ≤ ℓ ) , b P ( ℓ + 1 ) = b P ( ℓ ) + 1.
This is the count for the parent with its appended terminal one; it does not extend the sequence to any undefined index. For every 1 ≤ v ≤ 2 ℓ + 2 1 \le v \le2\ell+ 2 1 ≤ v ≤ 2 ℓ + 2 , counting ones in the prefixes of 0 P 1 0P1 0 P 1 and P P P using (19) gives
o ( v ) = b ^ P ( z ( v − 1 ) ) + b P ( o ( v − 1 ) ) . (22) o(v) = \widehat{b}_P(z(v - 1)) + b_P(o(v - 1)). \tag*{(22)} o ( v ) = b P ( z ( v − 1 )) + b P ( o ( v − 1 )) . (22)
The parent formulas are
F ( s ′ + u ) = b + b P ( u ) , G ( s ′ + u ) = b + u − b P ( u ) ( 0 ≤ u ≤ ℓ ) . F(s' + u) = b + b_P(u), \qquad G(s' + u) = b + u - b_P(u) \qquad(0 \le u \le\ell). F ( s ′ + u ) = b + b P ( u ) , G ( s ′ + u ) = b + u − b P ( u ) ( 0 ≤ u ≤ ℓ ) .
For the F F F -identity we use
b P ( z − 1 ) + b P ( o − ) = o − . (23) b_P(z-1)+b_P(o_-)=o_-. \tag*{(23)} b P ( z − 1 ) + b P ( o − ) = o − . (23)
If the t t t -th output is zero, this follows from (22) because z − 1 = z − z-1=z_- z − 1 = z − and o ( t ) = o − o(t)=o_- o ( t ) = o − . If it is one, the last consumed symbol of 0 P 1 0P1 0 P 1 , at position z z z , is one. For z ≤ ℓ z\le\ell z ≤ ℓ this says b P ( z ) − b P ( z − 1 ) = 1 b_P(z)-b_P(z-1)=1 b P ( z ) − b P ( z − 1 ) = 1 ; for z = ℓ + 1 z=\ell+1 z = ℓ + 1 it is the appended one and says b ^ P ( ℓ + 1 ) − b P ( ℓ ) = 1 \widehat{b}_P(\ell+1)-b_P(\ell)=1 b P ( ℓ + 1 ) − b P ( ℓ ) = 1 . Subtracting that one from (22) again gives (23) . It follows that
G ( s ′ + z − 1 ) + G ( s ′ + o − ) + 1 = ℓ + z + o − − b P ( z − 1 ) − b P ( o − ) = ℓ + z = F ( m ) . G(s'+z-1)+G(s'+o_-)+1=\ell+z+o_- -b_P(z-1)-b_P(o_-)=\ell+z=F(m). G ( s ′ + z − 1 ) + G ( s ′ + o − ) + 1 = ℓ + z + o − − b P ( z − 1 ) − b P ( o − ) = ℓ + z = F ( m ) .
Here 1 ≤ z ≤ ℓ + 1 1\le z\le\ell+1 1 ≤ z ≤ ℓ + 1 and 0 ≤ o − ≤ ℓ 0\le o_-\le\ell 0 ≤ o − ≤ ℓ , so both parent coordinates lie in [ 0 , ℓ ] [0,\ell] [ 0 , ℓ ] .
For the G G G -identity, 0 ≤ o ( t ) ≤ ℓ 0\le o(t)\le\ell 0 ≤ o ( t ) ≤ ℓ because t t t is a proper prefix of a word ending in one. The other coordinate z ( t ) z(t) z ( t ) may equal ℓ + 1 \ell+1 ℓ + 1 . At that single additional parent coordinate, the word definition in the child block, whose first bit is zero, gives
F ( s ′ + ℓ + 1 ) = F ( s + 1 ) = ℓ + 1 = b + b ^ P ( ℓ + 1 ) . (24) F(s'+\ell+1)=F(s+1)=\ell+1=b+\widehat{b}_P(\ell+1). \tag*{(24)} F ( s ′ + ℓ + 1 ) = F ( s + 1 ) = ℓ + 1 = b + b P ( ℓ + 1 ) . (24)
Thus F ( s ′ + u ) = b + b ^ P ( u ) F(s'+u)=b+\widehat{b}_P(u) F ( s ′ + u ) = b + b P ( u ) holds also for u = ℓ + 1 u=\ell+1 u = ℓ + 1 . There is no appeal to the recursion being proved: both sides of (24) are already fixed by the word construction. Moreover, the extra point is used only if z ( t ) = ℓ + 1 z(t)=\ell+1 z ( t ) = ℓ + 1 , which implies t ≥ ℓ + 1 > 1 t\ge\ell+1>1 t ≥ ℓ + 1 > 1 ; it is therefore strictly earlier than the current index s + t s+t s + t . Equation (22) at v = t + 1 v=t+1 v = t + 1 now gives
F ( s ′ + o ( t ) ) + F ( s ′ + z ( t ) ) = ℓ + b P ( o ( t ) ) + b ^ P ( z ( t ) ) = ℓ + o ( t + 1 ) = G ( m ) . F(s'+o(t))+F(s'+z(t))=\ell+b_P(o(t))+\widehat{b}_P(z(t))=\ell+o(t+1)=G(m). F ( s ′ + o ( t )) + F ( s ′ + z ( t )) = ℓ + b P ( o ( t )) + b P ( z ( t )) = ℓ + o ( t + 1 ) = G ( m ) .
At t = 1 t=1 t = 1 , the argument pairs are ( 0 , 0 ) (0,0) ( 0 , 0 ) and ( 0 , 1 ) (0,1) ( 0 , 1 ) . At t = 2 ℓ + 1 t=2\ell+1 t = 2 ℓ + 1 , they are ( ℓ , ℓ − 1 ) (\ell,\ell-1) ( ℓ , ℓ − 1 ) and ( ℓ , ℓ + 1 ) (\ell,\ell+1) ( ℓ , ℓ + 1 ) : the terminal run of S + ( P ) S_+(P) S + ( P ) contains at least two ones. At this final point, (22) is used at the full child length v = 2 ℓ + 2 v=2\ell+2 v = 2 ℓ + 2 , where it remains valid. The argument also covers k = 2 k=2 k = 2 : its parent ( 10 ) p − 1 01 (10)^{p-1}01 ( 10 ) p − 1 01 need not begin in zero for any of the even-case identities. This completes the verification at every index.
Proof of the global family theorem
Proof of Theorem 1.1. The balanced initial word ends in one, so its first plus transform is causal by Lemma 2.2 . Subsequent words begin in zero and end in one; both maps remain causal. Direct tape tracing, valid for any number of copies of 10 10 10 , gives
U p , 2 = ( 0110 ) p − 1 001011. U_{p,2}=(0110)^{p-1}001011. U p , 2 = ( 0110 ) p − 1 001011.
Repeated use of Lemma 2.4 proves (4) . The complemented factors advance by the opposite map, exactly as required by the parity of their level. Primitivity of the elementary factors gives the excursion count. Their lengths give L p , k L_{p,k} L p , k in (12) .
The core construction and (16) establish positivity, oddness, the bound by n n n , and the two-step law after reconstruction. Each core is unbounded, nondecreasing, and has unit steps, so it assumes every nonnegative value finitely often. At odd and even sequence indices, substitution of (14) in the nested recursion is respectively (17) and (18) . Proposition 3.1 therefore proves the recurrence for n > 6 p + 4 n>6p+4 n > 6 p + 4 . The reconstructed values satisfy 1 ≤ Q p ( n ) ≤ n 1\le Q_p(n)\le n 1 ≤ Q p ( n ) ≤ n , which makes every recursive argument positive and strictly backward.
It remains to justify the shorter seeds. Formula (2) follows from the prefix of ( 10 ) p − 1 01 (10)^{p-1}01 ( 10 ) p − 1 01 . For p ≥ 3 p\ge3 p ≥ 3 the following eleven substitutions verify all missing indices n = 6 p + b n=6p+b n = 6 p + b ; both arguments are listed relative to 2 p 2p 2 p and the result relative to 4 p 4p 4 p : All entries follow from the two explicitly known initial words. The needed small argument values are Q p ( 2 p + a ) = 2 p − 3 Q_p(2p+a)=2p-3 Q p ( 2 p + a ) = 2 p − 3 for a = − 3 , − 2 a=-3,-2 a = − 3 , − 2 , 2 p − 1 2p-1 2 p − 1 for a = − 1 , 0 , 1 , 2 a=-1,0,1,2 a = − 1 , 0 , 1 , 2 , and 2 p + 1 2p+1 2 p + 1 for a = 3 , 4 a=3,4 a = 3 , 4 . Every argument is positive and smaller than n n n . For p = 2 p=2 p = 2 , the remaining initial identities are the following direct substitutions in the independently defined cores:
Table 5.
Table 6.
They verify all sequence indices 8 ≤ n ≤ 16 8\le n\le16 8 ≤ n ≤ 16 ; the general block proof handles every later one. The independently constructed sequence satisfies the prescribed recurrence, and strong induction proves uniqueness.
Proposition 3.2 (Exact symmetric mode). For m = s p , k + t m=s_{p,k}+t m = s p , k + t in the corresponding core block,
F p ( m ) + G p ( m ) − m = d p , k + 1 { k e v e n } U p , k [ t ] . (25) F_p(m)+G_p(m)-m=d_{p,k}+\mathbf{1}_{\{k\ \mathrm{even}\}}U_{p,k}[t]. \tag*{(25)} F p ( m ) + G p ( m ) − m = d p , k + 1 { k even } U p , k [ t ] . (25) Thus Q p ( 2 m − 1 ) + Q p ( 2 m ) = 2 m + O p ( log m ) Q_p(2m-1)+Q_p(2m)=2m+O_p(\log m) Q p ( 2 m − 1 ) + Q p ( 2 m ) = 2 m + O p ( log m ) and
( Q p ( 2 m − 1 ) 2 m − 1 − 1 2 ) + ( Q p ( 2 m ) 2 m − 1 2 ) = O p ( log m m ) . (26) \left(\frac{Q_p(2m-1)}{2m-1}-\frac{1}{2}\right)+\left(\frac{Q_p(2m)}{2m}-\frac{1}{2}\right)=O_p\left(\frac{\log m}{m}\right). \tag*{(26)} ( 2 m − 1 Q p ( 2 m − 1 ) − 2 1 ) + ( 2 m Q p ( 2 m ) − 2 1 ) = O p ( m log m ) . (26)
Proof. Use o ( t ) + z ( t ) = t o(t)+z(t)=t o ( t ) + z ( t ) = t and o ( t + 1 ) = o ( t ) + U p , k [ t ] o(t+1)=o(t)+U_{p,k}[t] o ( t + 1 ) = o ( t ) + U p , k [ t ] in (13) –(3.3). Since s p , k ≍ p 2 k s_{p,k}\asymp_p2^k s p , k ≍ p 2 k , the offset is O p ( log m ) O_p(\log m) O p ( log m ) . Replacing the odd denominator by 2 m 2m 2 m costs O ( 1 / m ) O(1/m) O ( 1/ m ) because Q p ( 2 m − 1 ) ≤ 2 m − 1 Q_p(2m-1)\le2m-1 Q p ( 2 m − 1 ) ≤ 2 m − 1 .
The elementary Gaussian profile
Let φ \varphi φ and Φ \Phi Φ be the standard normal density and distribution function, and define
J ( x ) = φ ( Φ − 1 ( x ) ) ( 0 < x < 1 ) , J ( 0 ) = J ( 1 ) = 0. (27) J(x)=\varphi\left(\Phi^{-1}(x)\right)\quad(0<x<1),\qquad J(0)=J(1)=0. \tag*{(27)} J ( x ) = φ ( Φ − 1 ( x ) ) ( 0 < x < 1 ) , J ( 0 ) = J ( 1 ) = 0. (27)
It is a quantile-coordinate profile, not a Gaussian density in x x x . Elementary differentiation gives
J ′ ( x ) = − Φ − 1 ( x ) , J ( x ) J ′ ′ ( x ) = − 1. (28) J'(x)=-\Phi^{-1}(x),\qquad J(x)J''(x)=-1. \tag*{(28)} J ′ ( x ) = − Φ − 1 ( x ) , J ( x ) J ′′ ( x ) = − 1. (28)
The function is symmetric, strictly positive inside the interval, strictly concave, and maximized at 1 / 2 1/2 1/2 .
Theorem 4.1 (Uniform elementary-arch limit). With linear interpolation of integer-prefix heights,
sup 0 ≤ x ≤ 1 ∣ k ℓ k h A k ( ℓ k x ) − J ( x ) ∣ ⟶ 0. (29) \sup_{0 \le x \le1} \left| \frac{\sqrt{k}}{\ell_k} h_{A_k}(\ell_k x) - J(x) \right| \longrightarrow0. \tag*{(29)} 0 ≤ x ≤ 1 sup ℓ k k h A k ( ℓ k x ) − J ( x ) ⟶ 0. (29) In particular,
max t h A k ( t ) ∼ ℓ k 2 π k . (30) \max_t h_{A_k}(t) \sim\frac{\ell_k}{\sqrt{2\pi k}}. \tag*{(30)} t max h A k ( t ) ∼ 2 π k ℓ k . (30) All maximizing positions, divided by ℓ k \ell_k ℓ k , tend to 1 / 2 1/2 1/2 .
The ± 2 \pm2 ± 2 changes in word length must not be dropped silently. A small exact coordinate adjustment removes them and the additive height term simultaneously.
An exact shifted-height identity
Put
B k = 2 k 3 , ε k = ( − 1 ) k 3 , ℓ k = B k + 2 ε k , v k ( x ) = h A k ( B k x + ε k ) − ε k B k . (31) B_k = \frac{2^k}{3}, \qquad\varepsilon_k = \frac{(-1)^k}{3}, \qquad\ell_k = B_k + 2\varepsilon_k, \qquad v_k(x) = \frac{h_{A_k}(B_k x + \varepsilon_k) - \varepsilon_k}{B_k}. \tag*{(31)} B k = 3 2 k , ε k = 3 ( − 1 ) k , ℓ k = B k + 2 ε k , v k ( x ) = B k h A k ( B k x + ε k ) − ε k . (31)
When needed, extend a height linearly by h ( t ) = t h(t)=t h ( t ) = t just to the left of zero and by h ( t ) = ℓ k − t h(t)=\ell_k-t h ( t ) = ℓ k − t just to the right of ℓ k \ell_k ℓ k . Then v k v_k v k is defined on [ 0 , 1 ] [0,1] [ 0 , 1 ] , is nonnegative and 1 1 1 -Lipschitz, and satisfies v k ( 0 ) = v k ( 1 ) = 0 v_k(0)=v_k(1)=0 v k ( 0 ) = v k ( 1 ) = 0 . We also retain its actual word grid
G k = { ( t − ε k ) / B k : 0 ≤ t ≤ ℓ k , t ∈ Z } , \mathcal{G}_k = \{(t-\varepsilon_k)/B_k: 0 \le t \le\ell_k,\ t \in\mathbb{Z}\}, G k = {( t − ε k ) / B k : 0 ≤ t ≤ ℓ k , t ∈ Z } ,
which extends a distance 2 − k 2^{-k} 2 − k beyond [ 0 , 1 ] [0,1] [ 0 , 1 ] when k k k is even. At such external grid points v k v_k v k is negative of magnitude 2 − k 2^{-k} 2 − k .
Lemma 4.2 (Exact two-head identity). At a nonempty output prefix of the map from A k A_k A k to A k + 1 A_{k+1} A k + 1 , let x ∈ G k + 1 x \in\mathcal{G}_{k+1} x ∈ G k + 1 be its coordinate, y = v k + 1 ( x ) y=v_{k+1}(x) y = v k + 1 ( x ) , and c c c its last bit. Then
y = v k ( x + y + δ ) + v k ( x − y − δ ) 2 , δ = 2 c − 1 − ε k 2 B k , ∣ δ ∣ ≤ 2 1 − k . (32) y = \frac{v_k(x+y+\delta)+v_k(x-y-\delta)}{2}, \qquad\delta= \frac{2c-1-\varepsilon_k}{2B_k}, \qquad|\delta| \le2^{1-k}. \tag*{(32)} y = 2 v k ( x + y + δ ) + v k ( x − y − δ ) , δ = 2 B k 2 c − 1 − ε k , ∣ δ ∣ ≤ 2 1 − k . (32) The parent arguments are shifted word-grid points, with the single possible extra terminal point inherited from S + S_+ S + . If a parent argument is outside [ 0 , 1 ] [0,1] [ 0 , 1 ] , the output satisfies y = 1 − x y=1-x y = 1 − x . The zero-length and complete-prefix boundary cases are linear pieces with y = x y=x y = x or y = 1 − x y=1-x y = 1 − x when their coordinates lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Proof. Write H H H for the raw output height and t t t for its prefix length. For S + S_+ S + let r = i − 1 r=i-1 r = i − 1 , u = j u=j u = j ; for S − S_- S − let r = i r=i r = i , u = j + 1 u=j+1 u = j + 1 . With σ = ( − 1 ) k + 1 \sigma=(-1)^{k+1} σ = ( − 1 ) k + 1 , the tape heights give
H = h A k ( r ) + h A k ( u ) + σ , r + u = t − σ , r − u = H + 2 c − 1. H=h_{A_k}(r)+h_{A_k}(u)+\sigma,\qquad r+u=t-\sigma,\qquad r-u=H+2c-1. H = h A k ( r ) + h A k ( u ) + σ , r + u = t − σ , r − u = H + 2 c − 1.
For the extra terminal prefix in S + S_+ S + , set h A k ( ℓ k + 1 ) = − 1 h_{A_k}(\ell_k+1)=-1 h A k ( ℓ k + 1 ) = − 1 . Since σ = − 3 ε k \sigma=-3\varepsilon_k σ = − 3 ε k , ε k + 1 = − ε k \varepsilon_{k+1}=-\varepsilon_k ε k + 1 = − ε k , and B k + 1 = 2 B k B_{k+1}=2B_k B k + 1 = 2 B k , substitution in (31) gives (32) exactly.
No left external parent occurs at a nonempty prefix: for S − S_- S − , r , u ≥ 1 r,u \ge1 r , u ≥ 1 , whereas for S + S_+ S + , r , u ≥ 0 r,u \ge0 r , u ≥ 0 and ε k < 0 \varepsilon_k<0 ε k < 0 . Writing B = B k B=B_k B = B k and ℓ = ℓ k \ell=\ell_k ℓ = ℓ k , the complete list of right external parents is
Table 4.7.
The other parent u u u lies in the internal shifted grid. In either row the head identities give ℓ − u = h A k ( u ) + 2 c − 2 \ell-u=h_{A_k}(u)+2c-2 ℓ − u = h A k ( u ) + 2 c − 2 . Since h A k ( u ) ≤ ℓ − u h_{A_k}(u)\le\ell-u h A k ( u ) ≤ ℓ − u , they force c = 1 c=1 c = 1 and h A k ( u ) = ℓ − u h_{A_k}(u)=\ell-u h A k ( u ) = ℓ − u . Thus all remaining symbols on the other tape are ones, and H = ℓ k + 1 − t H=\ell_{k+1}-t H = ℓ k + 1 − t , or y = 1 − x y=1-x y = 1 − x . The empty and complete output prefixes belong to [ 0 , 1 ] [0,1] [ 0 , 1 ] exactly when k k k is even; their ( x , y ) (x,y) ( x , y ) coordinates are respectively
( 1 6 B , 1 6 B ) , ( 1 − 1 6 B , 1 6 B ) . (33) \left(\frac{1}{6B},\frac{1}{6B}\right),\qquad\left(1-\frac{1}{6B},\frac{1}{6B}\right). \tag*{(33)} ( 6 B 1 , 6 B 1 ) , ( 1 − 6 B 1 , 6 B 1 ) . (33)
For odd k k k the corresponding coordinates are outside [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Upper and positive lower barriers
Lemma 4.3 (Coarse upper bound). There is an absolute constant C C C such that
0 ≤ v k ( x ) ≤ C k ( 0 ≤ x ≤ 1 ) . (34) 0\le v_k(x)\le\frac{C}{\sqrt{k}}\qquad(0\le x\le1). \tag*{(34)} 0 ≤ v k ( x ) ≤ k C ( 0 ≤ x ≤ 1 ) . (34) Proof. Use the quadratic q ( x ) = 1 + x ( 1 − x ) q(x)=1+x(1-x) q ( x ) = 1 + x ( 1 − x ) and amplitudes b 4 = 1 b_4=1 b 4 = 1 , b k + 1 = b k / ( 1 + b k 2 / 32 ) b_{k+1}=b_k/(1+b_k^2/32) b k + 1 = b k / ( 1 + b k 2 /32 ) . We prove v k ≤ b k q v_k\le b_kq v k ≤ b k q on the shifted grids. The initial bound holds because v 4 ≤ 1 / 2 v_4\le1/2 v 4 ≤ 1/2 on [ 0 , 1 ] [0,1] [ 0 , 1 ] , while the external grid values are negative. Also
b k + 1 − 2 − b k − 2 = 1 16 + b k 2 1024 , b_{k+1}^{-2}-b_k^{-2}=\frac{1}{16}+\frac{b_k^2}{1024}, b k + 1 − 2 − b k − 2 = 16 1 + 1024 b k 2 , so b k ≍ k − 1 / 2 b_k\asymp k^{-1/2} b k ≍ k − 1/2 , and 2 1 − k ≤ b k / 4 2^{1-k}\le b_k/4 2 1 − k ≤ b k /4 for k ≥ 4 k\ge4 k ≥ 4 .
Suppose the next bound fails at an internal output grid point. Write b = b k b=b_k b = b k , b ′ = b k + 1 b'=b_{k+1} b ′ = b k + 1 . The grid lies within 2 − k − 1 2^{-k-1} 2 − k − 1 of [ 0 , 1 ] [0,1] [ 0 , 1 ] , so q ≥ 0.9 q\ge0.9 q ≥ 0.9 there. Then y > b ′ q ( x ) > 0.87 b y>b'q(x)>0.87b y > b ′ q ( x ) > 0.87 b , hence ∣ y + δ ∣ > b / 2 |y+\delta|>b/2 ∣ y + δ ∣ > b /2 . The exact quadratic average and (32) give
y ≤ b { q ( x ) − ( y + δ ) 2 } < b q ( x ) − b 3 / 4 < b ′ q ( x ) , y\le b\{q(x)-(y+\delta)^2\}<bq(x)-b^3/4<b'q(x), y ≤ b { q ( x ) − ( y + δ ) 2 } < b q ( x ) − b 3 /4 < b ′ q ( x ) , since q ( x ) ≤ 5 / 4 q(x)\le5/4 q ( x ) ≤ 5/4 and b − b ′ ≤ b 3 / 32 b-b'\le b^3/32 b − b ′ ≤ b 3 /32 . The extra terminal parent value is negative and satisfies the same upper comparison; q q q is positive on all points in question. The output boundary points have height O ( 2 − k ) O(2^{-k}) O ( 2 − k ) and satisfy the bound directly. Interpolation adds at most O ( 2 − k ) O(2^{-k}) O ( 2 − k ) , proving (4.9).
Lemma 4.4 (Positive sine barrier). Let b 6 = 1 / 64 b_6=1/64 b 6 = 1/64 and
b k + 1 = b k cos ( π ( b k + 2 1 − k ) ) , k ≥ 6. (35) b_{k+1}=b_k\cos\left(\pi\left(b_k+2^{1-k}\right)\right),\qquad k\ge6. \tag*{(35)} b k + 1 = b k cos ( π ( b k + 2 1 − k ) ) , k ≥ 6. (35) At every point x ∈ G k ∩ [ 0 , 1 ] x\in G_k\cap[0,1] x ∈ G k ∩ [ 0 , 1 ] ,
v k ( x ) ≥ b k sin ( π x ) , k b k ⟶ 1 / π . (36) v_k(x)\ge b_k\sin(\pi x),\qquad\sqrt{k}\,b_k\longrightarrow1/\pi. \tag*{(36)} v k ( x ) ≥ b k sin ( π x ) , k b k ⟶ 1/ π . (36) Proof. At level six, each internal raw height is at least one; after the shift its normalized height is at least 1 / 32 1/32 1/32 . Thus the initial grid bound holds. The amplitudes stay positive and decrease, with b k + 2 1 − k < 1 / 8 b_k+2^{1-k}<1/8 b k + 2 1 − k < 1/8 . A failure 0 ≤ y < b k + 1 sin ( π x ) 0\le y<b_{k+1}\sin(\pi x) 0 ≤ y < b k + 1 sin ( π x ) at the next grid point, when both parents lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , contradicts the sine addition formula:
y ≥ b k sin ( π x ) cos ( π ( y + δ ) ) ≥ b k sin ( π x ) cos ( π ( b k + 2 1 − k ) ) . y\ge b_k\sin(\pi x)\cos(\pi(y+\delta))\ge b_k\sin(\pi x)\cos\left(\pi\left(b_k+2^{1-k}\right)\right). y ≥ b k sin ( π x ) cos ( π ( y + δ )) ≥ b k sin ( π x ) cos ( π ( b k + 2 1 − k ) ) . If a parent lies outside, Lemma 4.2 gives y = 1 − x ≥ sin ( π x ) / π y=1-x\ge\sin(\pi x)/\pi y = 1 − x ≥ sin ( π x ) / π , excluding a failure. The linear boundary cases are treated by the same inequality and its reflection.
For the asymptotic let c k = b k − 2 c_k=b_k^{-2} c k = b k − 2 . The amplitudes tend to zero, since a positive limit in (35) would give a fixed strict contraction. Moreover
c k + 1 − c k = c k tan 2 ( π ( b k + 2 1 − k ) ) ≤ 8 π 2 ( 1 + c k 4 1 − k ) . c_{k+1}-c_k=c_k\tan^2\left(\pi\left(b_k+2^{1-k}\right)\right)\le8\pi^2\left(1+c_k4^{1-k}\right). c k + 1 − c k = c k tan 2 ( π ( b k + 2 1 − k ) ) ≤ 8 π 2 ( 1 + c k 4 1 − k ) . Iteration, using convergence of the corresponding infinite product, gives c k = O ( k ) c_k=O(k) c k = O ( k ) . Hence 2 1 − k / b k → 0 2^{1-k}/b_k\to0 2 1 − k / b k → 0 and the exact difference tends to π 2 \pi^2 π 2 . Averaging yields c k / k → π 2 c_k/k\to\pi^2 c k / k → π 2 .
Gaussian comparison and uniform convergence
Lemma 4.5 (Smooth comparison functions). There are smooth functions of the following two types arbitrarily close to J J J , uniformly on [ 0 , 1 ] [0,1] [ 0 , 1 ] . For the upper type, f > 0 f>0 f > 0 on a neighborhood of [ 0 , 1 ] [0,1] [ 0 , 1 ] and f f ′ ′ = − 1 ff^{\prime\prime}=-1 f f ′′ = − 1 . For the lower type, f f f is concave, negative at both endpoints, positive on a central interval compactly contained in ( 0 , 1 ) (0,1) ( 0 , 1 ) , and f f ′ ′ ≥ − 1 ff^{\prime\prime}\ge-1 f f ′′ ≥ − 1 wherever f > 0 f>0 f > 0 ; it is affine near its two zeros. For the lower type it is the positive part f + f_{+} f + which approximates J J J .
Proof. Upper functions are f η ( x ) = ( 1 + 2 η ) J ( ( x + η ) / ( 1 + 2 η ) ) f_{\eta}(x)=(1+2\eta)J((x+\eta)/(1+2\eta)) f η ( x ) = ( 1 + 2 η ) J (( x + η ) / ( 1 + 2 η )) , η > 0 \eta>0 η > 0 . For lower functions fix 0 < A < 1 / 2 π 0<A<1/\sqrt{2\pi} 0 < A < 1/ 2 π and a smooth g η g_{\eta} g η which is zero for v ≤ η v\le\eta v ≤ η , equals 1 / v 1/v 1/ v for v ≥ 2 η v\ge2\eta v ≥ 2 η , and satisfies 0 ≤ g η ( v ) ≤ 1 / v 0\le g_{\eta}(v)\le1/v 0 ≤ g η ( v ) ≤ 1/ v when v > 0 v>0 v > 0 . Solve symmetrically
f ′ ′ = − g η ( f ) , f ( 1 / 2 ) = A , f ′ ( 1 / 2 ) = 0 , f^{\prime\prime}=-g_{\eta}(f),\qquad f(1/2)=A,\qquad f^{\prime}(1/2)=0, f ′′ = − g η ( f ) , f ( 1/2 ) = A , f ′ ( 1/2 ) = 0 ,
and continue affinely once f ≤ η f\le\eta f ≤ η . Above height 2 η 2\eta 2 η this agrees with the solution of f f ′ ′ = − 1 ff^{\prime\prime}=-1 f f ′′ = − 1 of central height A A A . That solution has half-width A π / 2 A\sqrt{\pi/2} A π /2 , since ∣ f ′ ∣ = 2 log ( A / f ) |f^{\prime}|=\sqrt{2\log(A/f)} ∣ f ′ ∣ = 2 log ( A / f ) and
∫ 0 A ( 2 log ( A / v ) ) − 1 / 2 d v = A π / 2 . \int_{0}^{A}(2\log(A/v))^{-1/2}\,dv=A\sqrt{\pi/2}. ∫ 0 A ( 2 log ( A / v ) ) − 1/2 d v = A π /2 .
The remaining time from height 2 η 2\eta 2 η to zero is at most 2 η / 2 log ( A / ( 2 η ) ) 2\eta/\sqrt{2\log(A/(2\eta))} 2 η / 2 log ( A / ( 2 η )) . Thus the zeros lie inside ( 0 , 1 ) (0,1) ( 0 , 1 ) for small η \eta η . The positive part differs by at most 2 η 2\eta 2 η from the compactly supported Gaussian-quantile arch of height A A A . Let A A A tend upward to 1 / 2 π 1/\sqrt{2\pi} 1/ 2 π and then η \eta η tend to zero.
Lemma 4.6 (One-step comparison). Fix an upper-type function f f f and γ > 1 \gamma>1 γ > 1 , or a lower-type function f f f and 0 < γ < 1 0<\gamma<1 0 < γ < 1 . There is D 0 = D 0 ( f , γ ) ≥ 4 D_{0}=D_{0}(f,\gamma)\ge4 D 0 = D 0 ( f , γ ) ≥ 4 such that, whenever D ≥ D 0 D\ge D_{0} D ≥ D 0 and B k ≥ D 3 B_{k}\ge D^{3} B k ≥ D 3 , the corresponding implication holds on the internal shifted grids:
v k ≤ γ f D ⟹ v k + 1 ≤ γ f D + 1 (upper type) , (37) v_k\le\frac{\gamma f}{\sqrt{D}}\quad\Longrightarrow\quad v_{k+1}\le\frac{\gamma f}{\sqrt{D+1}}
\qquad\text{(upper type)}, \tag*{(37)} v k ≤ D γ f ⟹ v k + 1 ≤ D + 1 γ f (upper type) , (37) v k ≥ γ f D ⟹ v k + 1 ≥ γ f D + 1 (lower type) . (38) v_k\ge\frac{\gamma f}{\sqrt{D}}\quad\Longrightarrow\quad v_{k+1}\ge\frac{\gamma f}{\sqrt{D+1}}
\qquad\text{(lower type)}. \tag*{(38)} v k ≥ D γ f ⟹ v k + 1 ≥ D + 1 γ f (lower type) . (38) Here the parent inequality is assumed on G k ∩ [ 0 , 1 ] \mathcal{G}_k\cap[0,1] G k ∩ [ 0 , 1 ] , and the conclusion is on G k + 1 ∩ [ 0 , 1 ] \mathcal{G}_{k+1}\cap[0,1] G k + 1 ∩ [ 0 , 1 ] .
Proof. Put B = B k B=B_k B = B k , a = γ D − 1 / 2 a=\gamma D^{-1/2} a = γ D − 1/2 , b = γ ( D + 1 ) − 1 / 2 b=\gamma(D+1)^{-1/2} b = γ ( D + 1 ) − 1/2 , and g = ∣ γ 2 − 1 ∣ > 0 g=|\gamma^2-1|>0 g = ∣ γ 2 − 1∣ > 0 . We use the explicit scale comparison
b a − ( 1 − b 2 2 ) = γ 2 − 1 2 D + ε D , ∣ ε D ∣ ≤ C γ D 2 , C γ = g + 1 2 , D ≥ 4. (39) \frac{b}{a}-\left(1-\frac{b^2}{2}\right)=\frac{\gamma^2-1}{2D}+\varepsilon_D,\qquad|\varepsilon_D|\le\frac{C_{\gamma}}{D^2},\qquad C_{\gamma}=\frac{g+1}{2},\qquad D\ge4. \tag*{(39)} a b − ( 1 − 2 b 2 ) = 2 D γ 2 − 1 + ε D , ∣ ε D ∣ ≤ D 2 C γ , C γ = 2 g + 1 , D ≥ 4. (39)
Indeed, with s = ( D + 1 ) − 1 s=(D+1)^{-1} s = ( D + 1 ) − 1 , Taylor’s theorem gives
∣ 1 − s − 1 + s 2 ∣ ≤ s 2 8 ( 1 − s ) 3 / 2 ≤ s 2 4 , \left|\sqrt{1-s}-1+\frac{s}{2}\right|\le\frac{s^2}{8(1-s)^{3/2}}\le\frac{s^2}{4}, 1 − s − 1 + 2 s ≤ 8 ( 1 − s ) 3/2 s 2 ≤ 4 s 2 ,
and replacing ( D + 1 ) − 1 (D+1)^{-1} ( D + 1 ) − 1 by D − 1 D^{-1} D − 1 gives the displayed estimate.
For a nonempty output prefix write y = v k + 1 ( x ) y=v_{k+1}(x) y = v k + 1 ( x ) and d = y + δ d=y+\delta d = y + δ , where ∣ δ ∣ ≤ B − 1 |\delta|\le B^{-1} ∣ δ ∣ ≤ B − 1 by Lemma 4.2. Thus y y y is the mean of the two parent values at x ± d x\pm d x ± d . The constants below depend only on f f f , γ \gamma γ , and are uniform in D D D , B B B , x x x , and the choice of word map.
For clarity, the Taylor estimate used in both directions is
f ( x + d ) + f ( x − d ) 2 = f ( x ) + 1 2 f ′ ′ ( x ) d 2 + R ( x , d ) , ∣ R ( x , d ) ∣ ≤ d 4 24 max ∣ z − x ∣ ≤ ∣ d ∣ ∣ f ( 4 ) ( z ) ∣ . (40) \frac{f(x+d)+f(x-d)}{2}=f(x)+\frac{1}{2}f^{\prime\prime}(x)d^2+R(x,d),\qquad|R(x,d)|\le\frac{d^4}{24}\max_{|z-x|\le|d|}|f^{(4)}(z)|. \tag*{(40)} 2 f ( x + d ) + f ( x − d ) = f ( x ) + 2 1 f ′′ ( x ) d 2 + R ( x , d ) , ∣ R ( x , d ) ∣ ≤ 24 d 4 ∣ z − x ∣ ≤ ∣ d ∣ max ∣ f ( 4 ) ( z ) ∣. (40)
It follows by applying fourth-order remainder bounds separately at x + d x+d x + d and x − d x-d x − d ; the odd terms cancel. The whole sampling segment lies in I I I in the upper case and in [ 0 , 1 ] [0,1] [ 0 , 1 ] in the lower case considered below.
For an upper comparison choose a compact interval I I I in the positive neighborhood on which f f ′ ′ = − 1 ff''=-1 f f ′′ = − 1 , with [ 0 , 1 ] [0,1] [ 0 , 1 ] in its interior, and put
m = min I f > 0 , M = max I f , B 4 = max I ∣ f ( 4 ) ∣ . m=\min_{I} f>0,\qquad M=\max_{I} f,\qquad B_4=\max_{I}|f^{(4)}|. m = I min f > 0 , M = I max f , B 4 = I max ∣ f ( 4 ) ∣.
All possible parent arguments lie within B − 1 B^{-1} B − 1 of [ 0 , 1 ] [0,1] [ 0 , 1 ] . Increase a preliminary threshold D g e o m ≥ 4 D_{\mathrm{geom}}\ge4 D geom ≥ 4 so that these arguments lie in I I I for D ≥ D g e o m D\ge D_{\mathrm{geom}} D ≥ D geom and B ≥ D 3 B\ge D^3 B ≥ D 3 . Every external parent value is negative, including the additional terminal value of S + S_+ S + , so it automatically satisfies the upper comparison. The parent inequality therefore gives 0 ≤ y ≤ a M 0\le y\le aM 0 ≤ y ≤ a M . The symmetric Taylor expansion has remainder at most B 4 d 4 / 24 B_4d^4/24 B 4 d 4 /24 . At a putative failure y > b f ( x ) y>bf(x) y > b f ( x ) we have
d 2 ≥ b 2 f ( x ) 2 − 2 a M B , ∣ d ∣ ≤ γ M + 1 D . d^2\ge b^2f(x)^2-\frac{2aM}{B},\qquad|d|\le\frac{\gamma M+1}{\sqrt{D}}. d 2 ≥ b 2 f ( x ) 2 − B 2 a M , ∣ d ∣ ≤ D γ M + 1 .
Since f ′ ′ = − 1 / f f''=-1/f f ′′ = − 1/ f , it follows that
y ≤ a f ( x ) ( 1 − b 2 2 + E + ) , y\le af(x)\left(1-\frac{b^2}{2}+E_+\right), y ≤ a f ( x ) ( 1 − 2 b 2 + E + ) ,
0 ≤ E + ≤ γ M m 2 D B + B 4 ( γ M + 1 ) 4 24 m D 2 ≤ C + D 2 , 0\le E_+\le\frac{\gamma M}{m^2\sqrt{D}B}+\frac{B_4(\gamma M+1)^4}{24mD^2}\le\frac{C_+}{D^2}, 0 ≤ E + ≤ m 2 D B γ M + 24 m D 2 B 4 ( γ M + 1 ) 4 ≤ D 2 C + ,
C + = γ M m 2 + B 4 ( γ M + 1 ) 4 24 m . C_+=\frac{\gamma M}{m^2}+\frac{B_4(\gamma M+1)^4}{24m}. C + = m 2 γ M + 24 m B 4 ( γ M + 1 ) 4 .
Choose D 0 ≥ D g e o m D_0\ge D_{\mathrm{geom}} D 0 ≥ D geom also so that D 0 ≥ 4 ( C + + C γ ) / g D_0\ge4(C_++C_\gamma)/g D 0 ≥ 4 ( C + + C γ ) / g . Equation (39) then gives
1 − b 2 2 + E + ≤ b a − g 4 D , 1-\frac{b^2}{2}+E_+\le\frac{b}{a}-\frac{g}{4D}, 1 − 2 b 2 + E + ≤ a b − 4 D g ,
contradicting y > b f ( x ) y>bf(x) y > b f ( x ) .
For a lower comparison a failure can occur only where f ( x ) > 0 f(x)>0 f ( x ) > 0 , since v k + 1 ≥ 0 v_{k+1}\ge0 v k + 1 ≥ 0 on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Let ( p , q ) ⋐ ( 0 , 1 ) (p,q)\Subset(0,1) ( p , q ) ⋐ ( 0 , 1 ) be the positive set of f f f , and set M = max [ 0 , 1 ] f + M=\max_{[0,1]}f_+ M = max [ 0 , 1 ] f + . If a parent lies outside [ 0 , 1 ] [0,1] [ 0 , 1 ] , Lemma 4.2 gives y = 1 − x ≥ 1 − q y=1-x\ge1-q y = 1 − x ≥ 1 − q , exceeding b M bM b M after increasing D g e o m D_{\mathrm{geom}} D geom . Thus a lower failure can involve only internal parent points.
Choose disjoint affine neighborhoods of the two zeros of f f f , and then choose ρ > 0 \rho>0 ρ > 0 so that the compact set
K ρ = { x ∈ [ 0 , 1 ] : 0 ≤ f ( x ) ≤ ρ } K_\rho=\{x\in[0,1]:0\le f(x)\le\rho\} K ρ = { x ∈ [ 0 , 1 ] : 0 ≤ f ( x ) ≤ ρ }
lies in the interior of their union. Let η > 0 \eta>0 η > 0 be its distance from the complement of that union. Increase D g e o m D_{\mathrm{geom}} D geom until b ρ + B − 1 < η b\rho+B^{-1}<\eta b ρ + B − 1 < η . If a putative failure has 0 < f ( x ) ≤ ρ 0<f(x)\le\rho 0 < f ( x ) ≤ ρ , then ∣ d ∣ ≤ b ρ + B − 1 < η |d|\le b\rho+B^{-1}<\eta ∣ d ∣ ≤ b ρ + B − 1 < η , so the entire sampling segment lies in the same affine neighborhood. Its exact average is f ( x ) f(x) f ( x ) , giving y ≥ a f ( x ) > b f ( x ) y\ge af(x)>bf(x) y ≥ a f ( x ) > b f ( x ) , a contradiction. This includes sampling across a zero and requires no division by a vanishing function.
It remains to consider f ( x ) ≥ ρ f(x)\ge\rho f ( x ) ≥ ρ . Set B j = max [ 0 , 1 ] ∣ f ( j ) ∣ B_j=\max_{[0,1]}|f^{(j)}| B j = max [ 0 , 1 ] ∣ f ( j ) ∣ for j = 2 , 4 j=2,4 j = 2 , 4 . Now
d 2 ≤ b 2 f ( x ) 2 + 2 b M B + B − 2 , ∣ d ∣ ≤ γ M + 1 D . d^2\le b^2f(x)^2+\frac{2bM}{B}+B^{-2},\qquad|d|\le\frac{\gamma M+1}{\sqrt{D}}. d 2 ≤ b 2 f ( x ) 2 + B 2 b M + B − 2 , ∣ d ∣ ≤ D γ M + 1 .
Using f ′ ′ ≤ 0 f'' \le0 f ′′ ≤ 0 and f f ′ ′ ≥ − 1 ff'' \ge-1 f f ′′ ≥ − 1 , symmetric Taylor expansion gives
y ≥ a f ( x ) ( 1 − b 2 2 − E − ) , y \ge af(x)\left(1-\frac{b^2}{2}-E_-\right), y ≥ a f ( x ) ( 1 − 2 b 2 − E − ) ,
0 ≤ E − ≤ B 2 ρ ( γ M D B + 1 2 B 2 ) + B 4 ( γ M + 1 ) 4 24 ρ D 2 ≤ C − D 2 , 0 \le E_- \le\frac{B_2}{\rho}\left(\frac{\gamma M}{\sqrt{D}B}+\frac{1}{2B^2}\right)+\frac{B_4(\gamma M+1)^4}{24\rho D^2}\le\frac{C_-}{D^2}, 0 ≤ E − ≤ ρ B 2 ( D B γ M + 2 B 2 1 ) + 24 ρ D 2 B 4 ( γ M + 1 ) 4 ≤ D 2 C − ,
C − = B 2 ( γ M + 1 / 2 ) ρ + B 4 ( γ M + 1 ) 4 24 ρ . C_-=\frac{B_2(\gamma M+1/2)}{\rho}+\frac{B_4(\gamma M+1)^4}{24\rho}. C − = ρ B 2 ( γ M + 1/2 ) + 24 ρ B 4 ( γ M + 1 ) 4 .
Choose D 0 ≥ D g e o m D_0 \ge D_{\mathrm{geom}} D 0 ≥ D geom also so that D 0 ≥ 4 ( C − + C γ ) / g D_0 \ge4(C_-+C_\gamma)/g D 0 ≥ 4 ( C − + C γ ) / g . Since γ 2 − 1 = − g \gamma^2-1=-g γ 2 − 1 = − g , Equation (39) gives
1 − b 2 2 − E − ≥ b a + g 4 D , 1-\frac{b^2}{2}-E_- \ge\frac{b}{a}+\frac{g}{4D}, 1 − 2 b 2 − E − ≥ a b + 4 D g ,
again contradicting the proposed failure.
Finally, the only internal empty or complete prefixes are the two points in (33) . For the upper comparison their height satisfies
1 6 B ≤ 1 6 D 3 ≤ γ m D + 1 ≤ b f ( x ) \frac{1}{6B}\le\frac{1}{6D^3}\le\frac{\gamma m}{\sqrt{D+1}}\le bf(x) 6 B 1 ≤ 6 D 3 1 ≤ D + 1 γ m ≤ b f ( x )
after a fixed increase of D g e o m D_{\mathrm{geom}} D geom . For the lower comparison choose ε 0 > 0 \varepsilon_0>0 ε 0 > 0 such that f < 0 f<0 f < 0 on [ 0 , ε 0 ] ∪ [ 1 − ε 0 , 1 ] [0,\varepsilon_0]\cup[1-\varepsilon_0,1] [ 0 , ε 0 ] ∪ [ 1 − ε 0 , 1 ] ; it suffices that ( 6 D 3 ) − 1 ≤ ε 0 (6D^3)^{-1}\le\varepsilon_0 ( 6 D 3 ) − 1 ≤ ε 0 . All geometric choices above are uniform: if τ = dist ( [ 0 , 1 ] , R ∖ I ) > 0 \tau=\operatorname{dist}([0,1],\mathbb{R}\setminus I)>0 τ = dist ([ 0 , 1 ] , R ∖ I ) > 0 , it is enough in the upper case to require D − 3 < τ D^{-3}<\tau D − 3 < τ and the displayed endpoint inequality. In the lower case the other requirements follow from
γ M D < 1 − q , γ ρ D + D − 3 < η . \frac{\gamma M}{\sqrt{D}}<1-q,\qquad\frac{\gamma\rho}{\sqrt{D}}+D^{-3}<\eta. D γ M < 1 − q , D γ ρ + D − 3 < η .
These are finitely many conditions involving only the fixed function f f f and multiplier γ \gamma γ . Together with D 0 ≥ 4 ( C ± + C γ ) / g D_0\ge4(C_\pm+C_\gamma)/g D 0 ≥ 4 ( C ± + C γ ) / g , they specify a threshold independent of k k k , B B B , and the output point. This completes both implications on the stated internal grids.
Proof of Theorem 4.1 . Fix upper and lower functions f + , f − f^+,f^- f + , f − and parameters γ + > 1 \gamma_+>1 γ + > 1 and 0 < γ − < 1 0<\gamma_-<1 0 < γ − < 1 . We first initialize the comparisons at one sufficiently large level K K K .
By Lemma 4.3 , v K ≤ C 0 / K v_K\le C_0/\sqrt{K} v K ≤ C 0 / K on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Choose a fixed c > 0 c>0 c > 0 so small that γ + min [ 0 , 1 ] f + / c ≥ C 0 \gamma_+\min_{[0,1]}f^+/\sqrt{c}\ge C_0 γ + min [ 0 , 1 ] f + / c ≥ C 0 . Then the upper comparison holds with D + = c K D_+=cK D + = cK . For the lower comparison, the positive support of f − f^- f − is a compact subinterval of ( 0 , 1 ) (0,1) ( 0 , 1 ) , so
R = max x : f − ( x ) > 0 f − ( x ) sin ( π x ) < ∞ . R=\max_{x:f^-(x)>0}\frac{f^-(x)}{\sin(\pi x)}<\infty. R = x : f − ( x ) > 0 max sin ( π x ) f − ( x ) < ∞.
Lemma 4.4 gives v K ≥ c 0 sin ( π x ) / K v_K\ge c_0\sin(\pi x)/\sqrt{K} v K ≥ c 0 sin ( π x ) / K on the internal grid for some fixed c 0 > 0 c_0>0 c 0 > 0 and all large K K K . Choose a fixed C > 0 C>0 C > 0 with γ − R / C ≤ c 0 \gamma_-R/\sqrt{C}\le c_0 γ − R / C ≤ c 0 . The lower comparison then holds with D − = C K D_-=CK D − = C K ; where f − ≤ 0 f^-\le0 f − ≤ 0 it follows from v K ≥ 0 v_K\ge0 v K ≥ 0 .
Choose K K K large enough that both D ± ≥ D 0 D_\pm\ge D_0 D ± ≥ D 0 and B K ≥ max ( D + 3 , D − 3 ) B_K\ge\max(D_+^3,D_-^3) B K ≥ max ( D + 3 , D − 3 ) . These inequalities persist under iteration: B k B_k B k doubles while D D D increases by one, and 2 D 3 ≥ ( D + 1 ) 3 2D^3\ge(D+1)^3 2 D 3 ≥ ( D + 1 ) 3 for D ≥ 4 D\ge4 D ≥ 4 . Thus Lemma 4.6 propagates the two bounds, with time parameters D ± + k − K D_\pm+k-K D ± + k − K . Since
k D ± + k − K ⟶ 1 , \frac{\sqrt{k}}{\sqrt{D_\pm+k-K}}\longrightarrow1, D ± + k − K k ⟶ 1 ,
the limiting lower and upper bounds are γ − ( f − ) + \gamma_-(f^-)_+ γ − ( f − ) + and γ + f + \gamma_+f^+ γ + f + uniformly on the internal grids. Let the approximants tend uniformly to J J J and the two multipliers tend to one. The grid spacing is B k − 1 B_k^{-1} B k − 1 , and the omitted endpoint intervals have length at most B k − 1 B_k^{-1} B k − 1 . The 1-Lipschitz property and v k ( 0 ) = v k ( 1 ) = 0 v_k(0)=v_k(1)=0 v k ( 0 ) = v k ( 1 ) = 0 therefore extend the convergence uniformly to [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Finally, B k / ℓ k = 1 + O ( 2 − k ) B_k/\ell_k=1+O(2^{-k}) B k / ℓ k = 1 + O ( 2 − k ) . In normalized coordinates the horizontal and vertical shifts in (31) are both O ( 2 − k ) O(2^{-k}) O ( 2 − k ) ; the height function is 1-Lipschitz. These changes vanish after multiplication by k \sqrt{k} k , and yield (29) . Uniform convergence and the unique strict maximum of J J J imply both (30) and convergence of every maximizing position to 1 / 2 1/2 1/2 .
Corollary 4.7 (Height moments). For each fixed real q > 0 q>0 q > 0 ,
k q / 2 ℓ k q + 1 ∑ t = 0 ℓ k − 1 h A k ( t ) q ⟶ ( 2 π ) − q / 2 q + 1 . \frac{k^{q/2}}{\ell_k^{q+1}}\sum_{t=0}^{\ell_k-1}h_{A_k}(t)^q \longrightarrow\frac{(2\pi)^{-q/2}}{\sqrt{q+1}}. ℓ k q + 1 k q /2 t = 0 ∑ ℓ k − 1 h A k ( t ) q ⟶ q + 1 ( 2 π ) − q /2 . Proof. Uniform convergence reduces the assertion to a Riemann integral. The substitution x = Φ ( z ) x=\Phi(z) x = Φ ( z ) gives ∫ 0 1 J ( x ) q d x = ∫ R φ ( z ) q + 1 d z \int_0^1 J(x)^q\,\mathrm{d}x=\int_{\mathbb{R}}\varphi(z)^{q+1}\,\mathrm{d}z ∫ 0 1 J ( x ) q d x = ∫ R φ ( z ) q + 1 d z , which has the stated value.
Figure 2. Computed elementary-arch profiles and the proved limit. Finite-level ripples remain visible. The normalization is specified in Theorem 4.1 ; no fitted amplitude or horizontal shift is used.
Family profiles and sharp fluctuations
For the standard-block statements, let
N j , r ( t ) = 2 ⌊ 2 j t − r 2 ⌋ + r , r ∈ { 0 , 1 } , 1 ≤ t ≤ 2. N_{j,r}(t)=2\left\lfloor\frac{2^jt-r}{2}\right\rfloor+r,\qquad r\in\{0,1\},\qquad1\le t\le2. N j , r ( t ) = 2 ⌊ 2 2 j t − r ⌋ + r , r ∈ { 0 , 1 } , 1 ≤ t ≤ 2.
This samples the specified parity within two indices of 2 j t 2^jt 2 j t .
The elementary words A k A_k A k are the same for every p p p . Define the continuous signed height profile H p \mathcal{H}_p H p on [ 0 , c p ] [0,c_p] [ 0 , c p ] by
H p ( x ) = { J ( x − 3 i ) , 3 i ≤ x ≤ 3 i + 1 , 0 ≤ i ≤ p − 2 , − 2 J ( ( x − 3 i − 1 ) / 2 ) , 3 i + 1 ≤ x ≤ 3 i + 3 , 0 ≤ i ≤ p − 2 , 4 J ( ( x − 3 p + 3 ) / 4 ) , 3 p − 3 ≤ x ≤ c p . (41) \mathcal{H}_p(x)=
\begin{cases}
J(x-3i), & 3i\le x\le3i+1,\quad0\le i\le p-2,\\
-2J((x-3i-1)/2), & 3i+1\le x\le3i+3,\quad0\le i\le p-2,\\
4J((x-3p+3)/4), & 3p-3\le x\le c_p.
\end{cases} \tag*{(41)} H p ( x ) = ⎩ ⎨ ⎧ J ( x − 3 i ) , − 2 J (( x − 3 i − 1 ) /2 ) , 4 J (( x − 3 p + 3 ) /4 ) , 3 i ≤ x ≤ 3 i + 1 , 0 ≤ i ≤ p − 2 , 3 i + 1 ≤ x ≤ 3 i + 3 , 0 ≤ i ≤ p − 2 , 3 p − 3 ≤ x ≤ c p . (41)
Joining formulas agree at their endpoints.
Theorem 5.1 (Uniform family profiles). Fix p ≥ 2 p\ge2 p ≥ 2 . With B k = 2 k / 3 B_k=2^k/3 B k = 2 k /3 , linear interpolation and the harmless zero continuation over a missing endpoint interval of length O ( 1 ) O(1) O ( 1 ) ,
k B k h U p , k ( B k x ) ⟶ H p ( x ) uniformly on [ 0 , c p ] . (42) \frac{\sqrt{k}}{B_k}h_{U_{p,k}}(B_kx)\longrightarrow\mathcal{H}_p(x)\quad\text{uniformly on }[0,c_p]. \tag*{(42)} B k k h U p , k ( B k x ) ⟶ H p ( x ) uniformly on [ 0 , c p ] . (42) For indices of parity r r r whose core coordinate satisfies m = s p , k + B k x + O ( 1 ) m=s_{p,k}+B_kx+O(1) m = s p , k + B k x + O ( 1 ) within the k k k -th macro block,
( − 1 ) k + r + 1 k ( Q p ( n ) n − 1 2 ) ⟶ H p ( x ) 2 ( c p + x ) (43) (-1)^{k+r+1}\sqrt{k}\left(\frac{Q_p(n)}{n}-\frac{1}{2}\right)\longrightarrow\frac{\mathcal{H}_p(x)}{2(c_p+x)} \tag*{(43)} ( − 1 ) k + r + 1 k ( n Q p ( n ) − 2 1 ) ⟶ 2 ( c p + x ) H p ( x ) (43) uniformly in the normalized block coordinate, with endpoints taken from the actual core block. On standard dyadic blocks let
λ p ( t ) = ⌊ log 2 ( t / C p ) ⌋ , x p ( t ) = 3 2 − λ p ( t ) − 1 t − c p ( 1 ≤ t ≤ 2 ) . \lambda_p(t)=\left\lfloor\log_2(t/C_p)\right\rfloor,\qquad x_p(t)=3\,2^{-\lambda_p(t)-1}t-c_p\qquad(1\le t\le2). λ p ( t ) = ⌊ log 2 ( t / C p ) ⌋ , x p ( t ) = 3 2 − λ p ( t ) − 1 t − c p ( 1 ≤ t ≤ 2 ) . Then the complete limiting ratio profile is
P p ( t ) = ( − 1 ) λ p ( t ) + 1 H p ( x p ( t ) ) 2 ( c p + x p ( t ) ) , (44) P_p(t)=(-1)^{\lambda_p(t)+1}\frac{\mathcal{H}_p(x_p(t))}{2(c_p+x_p(t))}, \tag*{(44)} P p ( t ) = ( − 1 ) λ p ( t ) + 1 2 ( c p + x p ( t )) H p ( x p ( t )) , (44) and for r = 0 , 1 r=0,1 r = 0 , 1 ,
sup 1 ≤ t ≤ 2 ∣ ( − 1 ) j + r j ( Q p ( N j , r ( t ) ) N j , r ( t ) − 1 2 ) − P p ( t ) ∣ ⟶ 0. (45) \sup_{1\le t\le2}\left|(-1)^{j+r}\sqrt{j}\left(\frac{Q_p(N_{j,r}(t))}{N_{j,r}(t)}-\frac{1}{2}\right)-P_p(t)\right|\longrightarrow0. \tag*{(45)} 1 ≤ t ≤ 2 sup ( − 1 ) j + r j ( N j , r ( t ) Q p ( N j , r ( t )) − 2 1 ) − P p ( t ) ⟶ 0. (45) The formula at a macro boundary is independent of which side is chosen. The profile has exactly 2 p − 1 2p-1 2 p − 1 zeros in ( 1 , 2 ) (1,2) ( 1 , 2 ) , all sign transitions. Writing mant 2 ( y ) = y / 2 ⌊ log 2 y ⌋ \operatorname{mant}_2(y)=y/2^{\lfloor\log_2 y\rfloor} mant 2 ( y ) = y / 2 ⌊ l o g 2 y ⌋ , their set is
Z p = { mant 2 ( 2 3 ( c p + 3 i + s ) ) : 0 ≤ i ≤ p − 2 , s = 0 , 1 } ∪ { mant 2 ( 2 3 ( 6 p − 2 ) ) } . (46) Z_p=
\left\{\operatorname{mant}_2\left(\frac{2}{3}(c_p+3i+s)\right):0\le i\le p-2,\ s=0,1\right\}
\cup
\left\{\operatorname{mant}_2\left(\frac{2}{3}(6p-2)\right)\right\}. \tag*{(46)} Z p = { mant 2 ( 3 2 ( c p + 3 i + s ) ) : 0 ≤ i ≤ p − 2 , s = 0 , 1 } ∪ { mant 2 ( 3 2 ( 6 p − 2 ) ) } . (46)
Proof. Each factor in (4) is an A k + s A_{k+s} A k + s with s ∈ { 0 , 1 , 2 } s\in\{0,1,2\} s ∈ { 0 , 1 , 2 } . Its length divided by B k B_k B k tends to 2 s 2^s 2 s , and k / k + s → 1 \sqrt{k}/\sqrt{k+s}\to1 k / k + s → 1 . Theorem 4.1 , the finite number of factors for fixed p p p , and the vanishing of J J J at the endpoints prove (42) . Length and joining corrections are O p ( 1 ) O_p(1) O p ( 1 ) before normalization; Lipschitz heights make their effect O p ( k 2 − k ) O_p(\sqrt{k}2^{-k}) O p ( k 2 − k ) .
The two core formulas give, uniformly in a macro block,
Q p ( n ) n − 1 2 = ( − 1 ) k + r + 1 2 m h U p , k ( m − s p , k ) + O p ( k 2 − k ) . \frac{Q_p(n)}{n}-\frac{1}{2}
=\frac{(-1)^{k+r+1}}{2m}h_{U_{p,k}}(m-s_{p,k})+O_p(k2^{-k}). n Q p ( n ) − 2 1 = 2 m ( − 1 ) k + r + 1 h U p , k ( m − s p , k ) + O p ( k 2 − k ) .
Also s p , k = c p B k + O p ( k ) s_{p,k}=c_pB_k+O_p(k) s p , k = c p B k + O p ( k ) . This proves (43) . For a standard block the macro level is k = j + λ p ( t ) k=j+\lambda_p(t) k = j + λ p ( t ) away from an O p ( j 2 − j ) O_p(j2^{-j}) O p ( j 2 − j ) neighborhood of a boundary. The normalized core coordinate tends to x p ( t ) x_p(t) x p ( t ) . The sign in (44) is exactly the product of the natural and standard parity compensations. Uniformity across the small boundary intervals follows from the endpoint zeros of H p \mathcal{H}_p H p .
The full set of limiting beginnings of elementary excursions is γ 2 k \gamma2^k γ 2 k , where γ \gamma γ ranges over the unnormalized constants in (46) . They all lie in [ C p , 2 C p ) [C_p,2C_p) [ C p , 2 C p ) , are distinct, and none is a power of two: their numerator before division by three is not divisible by three. Thus their binary mantissas are distinct and lie strictly between one and two. Their number is 2 p − 1 2p-1 2 p − 1 . The signs alternate at internal joins; at a macro join the level parity changes. Positivity of J J J proves that there are no further limiting zeros.
Corollary 5.2 (Moments and sharp parameter-dependent fluctuations). For every fixed p ≥ 2 p \ge2 p ≥ 2 ,
Q p ( n ) = n / 2 + O p ( n / log n ) . Q_p(n)=n/2+O_p(n/\sqrt{\log n}). Q p ( n ) = n /2 + O p ( n / log n ) . Let b p > 0 b_p>0 b p > 0 be the unique root of
b p ( 3 p − 1 2 + Φ ( − b p ) ) = φ ( b p ) . (47) b_p\left(\frac{3p-1}{2}+\Phi(-b_p)\right)=\varphi(b_p). \tag*{(47)} b p ( 2 3 p − 1 + Φ ( − b p ) ) = φ ( b p ) . (47) Then
lim sup n → ∞ log 2 n ∣ Q p ( n ) n − 1 2 ∣ = Λ p = b p 2 . (48) \limsup_{n\to\infty}\sqrt{\log_2 n}\left|\frac{Q_p(n)}{n}-\frac{1}{2}\right|=\Lambda_p=\frac{b_p}{2}. \tag*{(48)} n → ∞ lim sup log 2 n n Q p ( n ) − 2 1 = Λ p = 2 b p . (48) The signed extremes are ± Λ p \pm\Lambda_p ± Λ p . The largest excursion is always the final factor A k + 2 A_{k+2} A k + 2 , with maximizing local coordinate x ∗ = Φ ( − b p ) x_*=\Phi(-b_p) x ∗ = Φ ( − b p ) . The constants decrease strictly with p p p , and
Λ p ∼ 1 3 p 2 π ( p → ∞ ) . (49) \Lambda_p\sim\frac{1}{3p\sqrt{2\pi}}\qquad(p\to\infty). \tag*{(49)} Λ p ∼ 3 p 2 π 1 ( p → ∞ ) . (49) The raw absolute macro-height maximum and all of its maximizing positions t k t_k t k satisfy
max t ∣ h U p , k ( t ) ∣ ∼ 4 B k 2 π k , t k L p , k ⟶ 3 p − 1 3 p + 1 . \max_t\lvert h_{U_{p,k}}(t)\rvert\sim\frac{4B_k}{\sqrt{2\pi k}},\qquad\frac{t_k}{L_{p,k}}\longrightarrow\frac{3p-1}{3p+1}. t max ∣ h U p , k ( t )∣ ∼ 2 π k 4 B k , L p , k t k ⟶ 3 p + 1 3 p − 1 . This maximum concerns raw word height, not the relative error; the latter has the different local maximizer x ∗ x_* x ∗ above. For each fixed real q > 0 q>0 q > 0 , the absolute macro-height moment is
k q / 2 L p , k q + 1 ∑ t = 0 L p , k − 1 ∣ h U p , k ( t ) ∣ q ⟶ ( p − 1 ) ( 1 + 2 q + 1 ) + 4 q + 1 C p q + 1 ( 2 π ) − q / 2 q + 1 . (50) \frac{k^{q/2}}{L_{p,k}^{q+1}}\sum_{t=0}^{L_{p,k}-1}\lvert h_{U_{p,k}}(t)\rvert^q\longrightarrow\frac{(p-1)(1+2^{q+1})+4^{q+1}}{C_p^{q+1}}\frac{(2\pi)^{-q/2}}{\sqrt{q+1}}. \tag*{(50)} L p , k q + 1 k q /2 t = 0 ∑ L p , k − 1 ∣ h U p , k ( t ) ∣ q ⟶ C p q + 1 ( p − 1 ) ( 1 + 2 q + 1 ) + 4 q + 1 q + 1 ( 2 π ) − q /2 . (50)
Proof. Uniform profiles imply the order bound. On a factor of width w w w , the limiting absolute ratio error is J ( x ) / ( 2 ( α + x ) ) J(x)/(2(\alpha+x)) J ( x ) / ( 2 ( α + x )) , where α \alpha α is its starting core coordinate divided by its width. The possible parameters are
c p + 3 i , c p + 3 i + 1 2 ( 0 ≤ i ≤ p − 2 ) , 6 p − 2 4 . c_p+3i,\qquad\frac{c_p+3i+1}{2}\quad(0\le i\le p-2),\qquad\frac{6p-2}{4}. c p + 3 i , 2 c p + 3 i + 1 ( 0 ≤ i ≤ p − 2 ) , 4 6 p − 2 .
The last is strictly the smallest. For fixed α \alpha α , the derivative numerator of J ( x ) / ( 2 ( α + x ) ) J(x)/(2(\alpha+x)) J ( x ) / ( 2 ( α + x )) is ( α + x ) J ′ ( x ) − J ( x ) (\alpha+x)J'(x)-J(x) ( α + x ) J ′ ( x ) − J ( x ) ; its derivative is ( α + x ) J ′ ′ ( x ) < 0 (\alpha+x)J''(x)<0 ( α + x ) J ′′ ( x ) < 0 , and it crosses zero once. Writing x ∗ = Φ ( − b p ) x_*=\Phi(-b_p) x ∗ = Φ ( − b p ) and using J ′ ( x ∗ ) = b p J'(x_*)=b_p J ′ ( x ∗ ) = b p gives (47) ; at that point the maximum is b p / 2 b_p/2 b p /2 . Each index parity supplies the opposite sign. This proves (48) . The root equation’s derivative in b b b is ( 3 p − 1 ) / 2 + Φ ( − b ) > 0 (3p-1)/2+\Phi(-b)>0 ( 3 p − 1 ) /2 + Φ ( − b ) > 0 . Increasing p p p therefore decreases its root strictly. As p → ∞ p\to\infty p → ∞ , b p → 0 b_p\to0 b p → 0 and the root equation gives b p ∼ 2 φ ( 0 ) / ( 3 p ) b_p\sim2\varphi(0)/(3p) b p ∼ 2 φ ( 0 ) / ( 3 p ) . The raw maximum follows because the final width-four factor has strictly greater limiting absolute height than any width-one or width-two factor; its local maximizing coordinate tends to 1 / 2 1/2 1/2 . For (50) , sum the elementary moment formula of Corollary 4.7 over the factors. Their widths are 1 , 2 , … , 1 , 2 , 4 1,2,\ldots,1,2,4 1 , 2 , … , 1 , 2 , 4 in units of B k B_k B k ; a width w w w contributes w q + 1 ∫ 0 1 J ( x ) q d x w^{q+1}\int_0^1J(x)^q\,dx w q + 1 ∫ 0 1 J ( x ) q d x .
These are numerical evaluations of (47) , not fitted amplitudes. Q 3 Q_3 Q 3 and Q 4 Q_4 Q 4 have the transition sets reported by (46) ; in increasing order they are
Z 3 = { 13 / 12 , 7 / 6 , 4 / 3 , 5 / 3 , 11 / 6 } , Z_3 = \{13/12, 7/6, 4/3, 5/3, 11/6\}, Z 3 = { 13/12 , 7/6 , 4/3 , 5/3 , 11/6 } ,
Z 4 = { 13 / 12 , 7 / 6 , 4 / 3 , 17 / 12 , 19 / 12 , 5 / 3 , 11 / 6 } . Z_4 = \{13/12, 7/6, 4/3, 17/12, 19/12, 5/3, 11/6\}. Z 4 = { 13/12 , 7/6 , 4/3 , 17/12 , 19/12 , 5/3 , 11/6 } .
Figure 3. The five-arch sequence Q 3 Q_3 Q 3 : directly computed, unaveraged even-parity profiles and the explicit p = 3 p = 3 p = 3 limit (44) , without fitted parameters. The sign and j \sqrt{j} j factors are prescribed, not fitted.
Figure 4 records the raw parity-split error terms for Q 3 Q_3 Q 3 and Q 4 Q_4 Q 4 on a logarithmic scale. It complements the compensated limit plots by showing the self-similar oscillations before averaging or sign correction.
Figure 4. Logarithmically sampled raw error terms Q p ( n ) / n − 1 / 2 Q_p(n)/n-1/2 Q p ( n ) / n − 1/2 for Q 3 Q_3 Q 3 and Q 4 Q_4 Q 4 , separated by parity. These plots visualize the five- and seven-transition oscillatory patterns directly in the unaveraged data.
Figure 5. Root-defined sharp error constants and their large-parameter asymptotic. The approximation in p p p is separate from the fixed-p p p limit as the sequence index tends to infinity.
Exact finite-level transitions
Low heights of the common elementary words
The Gaussian limit controls macroscopic signs but not all finite zeros. The following two lemmas determine the short end intervals containing all relevant low heights, independently of any convergence rate.
Lemma 6.1 (All low heights of an elementary word). Let k ≥ 8 k \ge8 k ≥ 8 , λ = ⌊ k / 2 ⌋ \lambda= \lfloor k/2 \rfloor λ = ⌊ k /2 ⌋ , and L = ℓ k L = \ell_k L = ℓ k . For integer 0 ≤ t ≤ λ + 4 0 \le t \le\lambda+ 4 0 ≤ t ≤ λ + 4 ,
h A k ( t ) = g λ ( t ) : = { t , 0 ≤ t ≤ λ , t − 2 , λ + 1 ≤ t ≤ λ + 4. (51) h_{A_k}(t) = g_\lambda(t) := \begin{cases} t, & 0 \le t \le\lambda, \\ t - 2, & \lambda+ 1 \le t \le\lambda+ 4. \end{cases} \tag*{(51)} h A k ( t ) = g λ ( t ) := { t , t − 2 , 0 ≤ t ≤ λ , λ + 1 ≤ t ≤ λ + 4. (51) The same formula holds at the other end by reflection: h A k ( L − t ) = g λ ( t ) h_{A_k}(L-t) = g_\lambda(t) h A k ( L − t ) = g λ ( t ) . Every remaining height satisfies
h A k ( t ) ≥ λ + 3 ( λ + 5 ≤ t ≤ L − λ − 5 ) . (52) h_{A_k}(t) \ge\lambda+ 3 \qquad(\lambda+ 5 \le t \le L - \lambda- 5). \tag*{(52)} h A k ( t ) ≥ λ + 3 ( λ + 5 ≤ t ≤ L − λ − 5 ) . (52) Thus these two short end intervals contain all positions of height at most λ + 2 \lambda+ 2 λ + 2 .
Proof. For the finite base, A 8 A_8 A 8 is the concatenation of the following two strings:
0000100000100010110010000100010110010111011 0010001011001011101111011001011101111101111.
Its length is 86, its first nine heights are 0, 1, 2, 3, 4, 3, 4, 5, 6, and its minimum on 9 ≤ t ≤ 77 9 \le t \le77 9 ≤ t ≤ 77 is 7. This verifies the assertion at level eight.
Suppose it holds at level k k k . Write σ = 1 \sigma= 1 σ = 1 for S + S_+ S + and σ = − 1 \sigma= -1 σ = − 1 for S − S_- S − , so that the child length is L ′ = 2 L + 2 σ L' = 2L + 2\sigma L ′ = 2 L + 2 σ . The child initial zero-run has length λ ′ = λ + 1 \lambda' = \lambda+ 1 λ ′ = λ + 1 for S + S_+ S + and λ ′ = λ \lambda' = \lambda λ ′ = λ for S − S_- S − . The run expansions show that this is followed by one single 1 and at least three zeros. Indeed, the parent has an initial zero-run of length at least four, followed by one 1 and at least three zeros; the next zero gap increases by one. This proves (51) for the child. Reverse-complement symmetry gives its reflected version.
It remains to exclude other low heights. Let an output prefix have length t t t and height H ≤ λ ′ + 2 H \le\lambda' + 2 H ≤ λ ′ + 2 . By symmetry assume 0 ≤ t ≤ L ′ / 2 0 \le t \le L'/2 0 ≤ t ≤ L ′ /2 ; the empty prefix is harmless. If the zero tape has finished, the height is L ′ − t L' - t L ′ − t , which cannot be this small in the chosen half. Otherwise the raw reading-head identity in the proof of Lemma 4.2 supplies parent positions r r r , u u u with
H = h A k ( r ) + h A k ( u ) + σ , r + u = t − σ , r − u = H + 2 c − 1 , (53) H = h_{A_k}(r) + h_{A_k}(u) + \sigma,\qquad r + u = t - \sigma,\qquad r - u = H + 2c - 1, \tag*{(53)} H = h A k ( r ) + h A k ( u ) + σ , r + u = t − σ , r − u = H + 2 c − 1 , (53)
where c ∈ { 0 , 1 } c \in\{0,1\} c ∈ { 0 , 1 } is the last output bit. For S − S_- S − both positions are strictly internal, so both parent heights are at least one. For S + S_+ S + the ordinary parent heights are nonnegative. Consequently, if either parent height were at least λ + 3 \lambda+ 3 λ + 3 , then H > λ ′ + 2 H > \lambda' + 2 H > λ ′ + 2 in either case. Both positions must therefore lie in the parent’s two end intervals from the induction hypothesis.
They cannot be in opposite end intervals: their distance would be at least L − 2 ( λ + 4 ) > λ + 4 L - 2(\lambda+ 4) > \lambda+ 4 L − 2 ( λ + 4 ) > λ + 4 , whereas ∣ r − u ∣ ≤ H + 1 ≤ λ + 4 \lvert r - u \rvert\le H + 1 \le\lambda+ 4 ∣ r − u ∣ ≤ H + 1 ≤ λ + 4 . Here L > 3 λ + 12 L > 3\lambda+ 12 L > 3 λ + 12 holds at k = 8 k = 8 k = 8 and persists under the length recursion. Nor can both positions be in the right end interval, since r + u ≤ L + 1 r + u \le L + 1 r + u ≤ L + 1 but then r + u ≥ 2 L − 2 λ − 8 > L + 1 r + u \ge2L - 2\lambda- 8 > L + 1 r + u ≥ 2 L − 2 λ − 8 > L + 1 . Thus both lie in [ 0 , λ + 4 ] [0,\lambda+ 4] [ 0 , λ + 4 ] .
Put b = 1 { r > λ } + 1 { u > λ } b = 1_{\{r>\lambda\}} + 1_{\{u>\lambda\}} b = 1 { r > λ } + 1 { u > λ } . Equations (51) and (53) imply
H = t − 2 b , u = b − c + ( 1 − σ ) / 2 ≤ 3. H = t - 2b,\qquad u = b - c + (1-\sigma)/2 \le3. H = t − 2 b , u = b − c + ( 1 − σ ) /2 ≤ 3.
Since λ ≥ 4 \lambda\ge4 λ ≥ 4 , the position u u u contributes zero to b b b ; therefore b ≤ 1 b \le1 b ≤ 1 . The assumed height bound now forces t ≤ λ ′ + 4 t \le\lambda' + 4 t ≤ λ ′ + 4 . This excludes all low heights outside the claimed end intervals and completes the induction.
Uniform extra-depth control and the crossing formulas
A fixed parameter changes the height thresholds by a constant. The low-height lemma must therefore be strengthened before the finite crossing formulas can be transferred.
Lemma 6.2 (Low heights to any fixed extra depth). Let c ≥ 2 c \ge2 c ≥ 2 be an integer and k ≥ c + 6 k \ge c+6 k ≥ c + 6 . Set λ = ⌊ k / 2 ⌋ \lambda= \lfloor k/2 \rfloor λ = ⌊ k /2 ⌋ , L = ℓ k L = \ell_k L = ℓ k . At integer positions 0 ≤ t ≤ λ + c + 2 0 \le t \le\lambda+ c + 2 0 ≤ t ≤ λ + c + 2 ,
h A k ( t ) = { t , t ≤ λ , t − 2 , λ + 1 ≤ t ≤ λ + c + 2. (54) h_{A_k}(t) =
\begin{cases}
t, & t \le\lambda, \\
t-2, & \lambda+1 \le t \le\lambda+c+2.
\end{cases} \tag*{(54)} h A k ( t ) = { t , t − 2 , t ≤ λ , λ + 1 ≤ t ≤ λ + c + 2. (54) The reflected formula holds at the other end, and every other height is at least λ + c + 1 \lambda+c+1 λ + c + 1 . These end intervals therefore contain all heights at most λ + c \lambda+c λ + c .
Proof. The case c = 2 c=2 c = 2 is Lemma Lemma 6.1 . For every k ≥ 4 k \ge4 k ≥ 4 the first three constant runs of A k A_k A k are
0 ⌊ k / 2 ⌋ 1 0 k − 3 . 0^{\lfloor k/2 \rfloor}1\,0^{k-3}. 0 ⌊ k /2 ⌋ 1 0 k − 3 .
This holds for A 4 = 001011 A_4 = 001011 A 4 = 001011 and follows by induction from the two run expansions: the first run changes as stated in Lemma 2.3 , the intervening one stays single, and the next zero-run gains one. Thus (54) is already exact in its stated end intervals. It remains to exclude other low positions.
Induct on c ≥ 3 c \ge3 c ≥ 3 , using the assertion at depth c − 1 c-1 c − 1 for the parent word A k − 1 A_{k-1} A k − 1 . Write μ = ⌊ ( k − 1 ) / 2 ⌋ \mu= \lfloor(k-1)/2 \rfloor μ = ⌊( k − 1 ) /2 ⌋ and let σ = 1 \sigma=1 σ = 1 for the plus map, − 1 -1 − 1 for the minus map. By symmetry take an output prefix in the left half. If the zero tape has finished, its height is its remaining length and exceeds the proposed threshold. Otherwise the ordinary head positions satisfy
H = h ( r ) + h ( u ) + σ , r + u = t − σ , r − u = H + 2 χ − 1 , H = h(r) + h(u) + \sigma,\qquad r+u=t-\sigma,\qquad r-u=H+2\chi-1, H = h ( r ) + h ( u ) + σ , r + u = t − σ , r − u = H + 2 χ − 1 ,
where χ ∈ { 0 , 1 } \chi\in\{0,1\} χ ∈ { 0 , 1 } is the last bit. In the minus case both parent positions are strictly internal. Since H > 0 H>0 H > 0 at an internal child prefix, these identities also give r ≥ u r \ge u r ≥ u .
Suppose H ≤ λ + c H \le\lambda+c H ≤ λ + c . If both parent heights are at most μ + c − 1 \mu+c-1 μ + c − 1 , the induction hypothesis puts their positions in the parent’s two end intervals. They cannot be in opposite ends, because their distance would exceed H + 1 H+1 H + 1 , nor can both be in the right end, because r + u ≤ ℓ k − 1 + 1 r+u \le\ell_{k-1}+1 r + u ≤ ℓ k − 1 + 1 . The needed inequalities follow from ℓ k − 1 > 3 ( μ + c + 2 ) \ell_{k-1}>3(\mu+c+2) ℓ k − 1 > 3 ( μ + c + 2 ) for k ≥ c + 6 k \ge c+6 k ≥ c + 6 , c ≥ 3 c \ge3 c ≥ 3 . Hence both positions are in the left end interval.
If one parent height is at least μ + c \mu+c μ + c , the other is zero in the plus case or at most one in the minus case. In the plus case this forces the smaller position u = 0 u=0 u = 0 ; the alternatives at the right end contradict the left-half sum bound. In the minus case it forces u = 1 u=1 u = 1 : by the induction hypothesis the only parent positions of height one are 1 , ℓ k − 1 − 1 1,\ell_{k-1}-1 1 , ℓ k − 1 − 1 , and again the right-end alternative is excluded. The head-distance bound now puts both positions in [ 0 , μ + c + 2 ] [0,\mu+c+2] [ 0 , μ + c + 2 ] . Their heights are given by the leading-run formula, including its last possible extra position.
In either case let b = 1 { r > μ } + 1 { u > μ } b=\mathbf{1}_{\{r>\mu\}}+\mathbf{1}_{\{u>\mu\}} b = 1 { r > μ } + 1 { u > μ } . The leading-run formula implies H = t − 2 b H=t-2b H = t − 2 b , and the head identities give u = b − χ + ( 1 − σ ) / 2 ≤ 3 u=b-\chi+(1-\sigma)/2 \le3 u = b − χ + ( 1 − σ ) /2 ≤ 3 . Since μ ≥ 4 \mu\ge4 μ ≥ 4 , the smaller position cannot contribute to b b b ; thus b ≤ 1 b \le1 b ≤ 1 . It follows that t ≤ λ + c + 2 t \le\lambda+c+2 t ≤ λ + c + 2 . Reflection completes the exclusion and the induction.
For an elementary factor of U p , k U_{p,k} U p , k , denote its beginning in the core index by B B B , its elementary level by l l l , and its sign by ε \varepsilon ε . The complete list of factors is
B l ε s p , k + i 2 k k + 1 ( 0 ≤ i ≤ p − 2 ) s p , k + i 2 k + ℓ k k + 1 − 1 ( 0 ≤ i ≤ p − 2 ) s p , k + ( p − 1 ) 2 k k + 2 + 1 (55) \begin{array}{c|c|c}
B & l & \varepsilon\\
s_{p,k}+i2^k & k & +1\quad(0\le i\le p-2) \\
s_{p,k}+i2^k+\ell_k & k+1 & -1\quad(0\le i\le p-2) \\
s_{p,k}+(p-1)2^k & k+2 & +1 \tag*{(55)}
\end{array} B s p , k + i 2 k s p , k + i 2 k + ℓ k s p , k + ( p − 1 ) 2 k l k k + 1 k + 2 ε + 1 ( 0 ≤ i ≤ p − 2 ) − 1 ( 0 ≤ i ≤ p − 2 ) + 1 (55)
Theorem 6.3 (All finite zeros and crossings for the higher members). Fix p ≥ 3 p\ge3 p ≥ 3 , put d = ⌊ log 2 p ⌋ d=\lfloor\log_2 p\rfloor d = ⌊ log 2 p ⌋ , and take j ≥ J p : = p + d + 10 j\ge J_p:=p+d+10 j ≥ J p := p + d + 10 . All zeros Q p ( n ) − n / 2 = 0 Q_p(n)-n/2=0 Q p ( n ) − n /2 = 0 on 2 j ≤ n < 2 j + 1 2^j\le n<2^{j+1} 2 j ≤ n < 2 j + 1 are obtained from the following table, retaining only the indices in that block. Write D = d p , k D=d_{p,k} D = d p , k .
There are no zeros on the other factors. For odd-parity sign changes, use positive factors at odd k k k and negative factors at even k k k . The left indices of the two crossing pairs ( n , n + 2 ) (n,n+2) ( n , n + 2 ) on such a factor are exactly
n = 2 ( B + D + 3 ) − 1 , n = 2 ( B + ℓ l − D − 4 ) − 1. (56) n=2(B+D+3)-1,\qquad n=2(B+\ell_l-D-4)-1. \tag*{(56)} n = 2 ( B + D + 3 ) − 1 , n = 2 ( B + ℓ l − D − 4 ) − 1. (56) There are exactly 2 p − 1 2p-1 2 p − 1 even zeros and exactly 2 p − 1 2p-1 2 p − 1 sign changes on each parity subsequence in every such standard block. Every even zero is transverse; there are no tangencies. Thus the four/six-zero alternation of Theorem A.5 is special to p = 2 p=2 p = 2 . All these indices are within distance 2 j + 4 p + 16 2j+4p+16 2 j + 4 p + 16 of one of the centers 2 z 2^z 2 z , z ∈ Z p z\in\mathbb{Z}_p z ∈ Z p . The normalized transition-window order O p ( 2 j − 2 ) O_p(2^{j-2}) O p ( 2 j − 2 ) is sharp.
Proof. The exact error identities on a signed elementary factor are
Q p ( 2 m ) − m = { D + 1 + ε h A l ( m − B ) , k odd , D + 2 − ε h A l ( m − B + 1 ) , k even . Q_p(2m)-m=
\begin{cases}
D+1+\varepsilon h_{A_l}(m-B), & k\text{ odd},\\
D+2-\varepsilon h_{A_l}(m-B+1), & k\text{ even}.
\end{cases} Q p ( 2 m ) − m = { D + 1 + ε h A l ( m − B ) , D + 2 − ε h A l ( m − B + 1 ) , k odd , k even .
Q p ( 2 m − 1 ) − ( 2 m − 1 ) / 2 = { D + 3 / 2 − ε h A l ( m − B ) , k odd , D + 3 / 2 + ε h A l ( m − B ) , k even . Q_p(2m-1)-(2m-1)/2=
\begin{cases}
D+3/2-\varepsilon h_{A_l}(m-B), & k\text{ odd},\\
D+3/2+\varepsilon h_{A_l}(m-B), & k\text{ even}.
\end{cases} Q p ( 2 m − 1 ) − ( 2 m − 1 ) /2 = { D + 3/2 − ε h A l ( m − B ) , D + 3/2 + ε h A l ( m − B ) , k odd , k even .
At factor joins, heights zero or one give the consistent adjacent core formulas; all roots below occur strictly inside a factor. Let λ = ⌊ l / 2 ⌋ \lambda=\lfloor l/2\rfloor λ = ⌊ l /2 ⌋ . On a factor selected for an even zero, its required height exceeds λ \lambda λ by p − 2 p-2 p − 2 or p − 1 p-1 p − 1 . For p ≥ 3 p\ge3 p ≥ 3 this is positive. Lemma 6.2, with extra depth c = p c=p c = p , therefore gives exactly the two height positions T + 2 T+2 T + 2 , ℓ l − T − 2 \ell_l-T-2 ℓ l − T − 2 for the required integer height T T T . The one-position shift at even macro levels gives the two rows of the table. The required half-integer height for an odd crossing is D + 3 / 2 D+3/2 D + 3/2 ; its increasing and decreasing crossing positions are D + 3 D+3 D + 3 , ℓ l − D − 4 \ell_l-D-4 ℓ l − D − 4 , giving (56) .
The macro levels intersecting the standard block are j − d − 2 j-d-2 j − d − 2 and j − d − 1 j-d-1 j − d − 1 , up to their exact displaced boundary. In particular all relevant elementary levels exceed p + 6 p+6 p + 6 under j ≥ J p j\ge J_p j ≥ J p . The low-height lemma applies everywhere needed. At each join exactly one adjacent factor has negative error in its interior, for each parity. All even hits are above the small local minimum at height λ − 1 \lambda-1 λ − 1 , so they are transverse. Consequently each join supplies one zero and one crossing to the respective parity subsequence, with no additional ones in the interiors. For an explicit separation argument, the numbers in Z p \mathbb{Z}_p Z p have a common denominator 3 ⋅ 2 d + 1 3 \cdot2^{d+1} 3 ⋅ 2 d + 1 and none is one or two. Thus their mutual distances and their distances to the standard-block ends are at least 1 / ( 3 ⋅ 2 d + 1 ) 1/(3 \cdot2^{d+1}) 1/ ( 3 ⋅ 2 d + 1 ) . From (12) and the bounded corrections in ℓ l \ell_l ℓ l , every tabulated index is within 2 j + 4 p + 16 2j+4p+16 2 j + 4 p + 16 of its ideal join. The inequality
2 j − d − 1 / 3 > 2 ( 2 j + 4 p + 16 ) 2^{j-d-1}/3 > 2(2j+4p+16) 2 j − d − 1 /3 > 2 ( 2 j + 4 p + 16 )
holds at j = J p j=J_p j = J p for p ≥ 3 p \ge3 p ≥ 3 and persists with j j j . Thus the neighborhoods are disjoint and inside the standard block; there are exactly 2 p − 1 2p-1 2 p − 1 of them by Theorem 5.1. Finally a right crossing at the end of a negative elementary factor has displacement − 2 k + O p ( 1 ) -2k+O_p(1) − 2 k + O p ( 1 ) from its limiting endpoint. Since j = k + O p ( 1 ) j=k+O_p(1) j = k + O p ( 1 ) , a uniform o p ( j 2 ) o_p(j^2) o p ( j 2 ) window is impossible.
The threshold J p J_p J p is deliberately sufficient, not asserted to be minimal. The displayed coordinate tables are exact formulas in powers, floors, and p p p ; they require neither numerical root searches nor a quantitative Gaussian-convergence rate.
Ordered frequencies and parameter-dependent dyadic laws
Let ν p ( v ) = # { n ≥ 1 : Q p ( n ) = v } \nu_p(v)=\#\{n \ge1: Q_p(n)=v\} ν p ( v ) = # { n ≥ 1 : Q p ( n ) = v } . These are multiplicities in the complete infinite sequence, finite by Theorem 1.1. A natural value block is { 2 u + 1 : a p , k ≤ u < a p , k + 1 } \{2u+1:a_{p,k} \le u < a_{p,k+1}\} { 2 u + 1 : a p , k ≤ u < a p , k + 1 } . We first retain the order of its frequencies; a histogram alone would not determine a cut through a dyadic value interval.
Plateaus and elementary frequency words
Write L F p ( u ) = # { m : F p ( m ) = u } L_{F_p}(u)=\#\{m:F_p(m)=u\} L F p ( u ) = # { m : F p ( m ) = u } and define L G p L_{G_p} L G p likewise. Then ν p ( 2 u + 1 ) = L F p ( u ) + L G p ( u ) \nu_p(2u+1)=L_{F_p}(u)+L_{G_p}(u) ν p ( 2 u + 1 ) = L F p ( u ) + L G p ( u ) . For U p , k U_{p,k} U p , k let α i , β i \alpha_i,\beta_i α i , β i be the gap lists defined in § 2 , and put β 0 = 0 \beta_0=0 β 0 = 0 . The outer runs of U p , k U_{p,k} U p , k , for k ≥ 2 k \ge2 k ≥ 2 , have lengths ⌊ k / 2 ⌋ \lfloor k/2 \rfloor ⌊ k /2 ⌋ and ⌊ k / 2 ⌋ + 1 \lfloor k/2 \rfloor+1 ⌊ k /2 ⌋ + 1 , independently of p p p . This follows from U p , 2 = ( 0110 ) p − 1 001011 U_{p,2}=(0110)^{p-1}001011 U p , 2 = ( 0110 ) p − 1 001011 and Lemma 2.3.
Lemma 7.1 (Interior and boundary local times). For every p ≥ 2 p \ge2 p ≥ 2 , k ≥ 2 k \ge2 k ≥ 2 , and 2 ≤ i ≤ L p , k / 2 2 \le i \le L_{p,k}/2 2 ≤ i ≤ L p , k /2 ,
ν p ( 2 ( a p , k + i − 1 ) + 1 ) = 2 + α i + β i − 1 . (57) \nu_p(2(a_{p,k}+i-1)+1)=2+\alpha_i+\beta_{i-1}. \tag*{(57)} ν p ( 2 ( a p , k + i − 1 ) + 1 ) = 2 + α i + β i − 1 . (57) At the initial level, ν p ( 2 a p , k + 1 ) = k + 1 \nu_p(2a_{p,k}+1)=k+1 ν p ( 2 a p , k + 1 ) = k + 1 .
Proof. On an odd block F p F_p F p counts ones and G p G_p G p counts zeros. An interior plateau contributes one plus the corresponding zero gap and one plus the preceding one gap. On an even block the roles exchange; the one-position shift in G p G_p G p leaves complete interior plateau lengths unchanged. Only the initial level can extend into the preceding block. For k = 2 r + 1 k=2r+1 k = 2 r + 1 its F p F_p F p plateau has r + 1 r+1 r + 1 points on each side, with the shared endpoint counted once, hence length k k k ; the other plateau has length one. For k = 2 r k=2r k = 2 r the G p G_p G p plateau has r + 1 r+1 r + 1 and r r r points, again with one overlap, hence length k k k ; its partner has length one. The case k = 2 k=2 k = 2 uses the terminal one-run of length one in U p , 1 U_{p,1} U p , 1 . This proves the boundary formula. The clock offset p − 2 p-2 p − 2 changes no plateau length.
Lemma 7.2 (Disjoint gap supports). For every elementary word A k A_k A k , k ≥ 2 k \ge2 k ≥ 2 , exactly one of α i , β i − 1 \alpha_i,\beta_{i-1} α i , β i − 1 is positive at each 1 ≤ i ≤ ℓ k / 2 1 \le i \le\ell_k/2 1 ≤ i ≤ ℓ k /2 .
Proof. We prove the property for an output of either map; the words A 2 = A 3 = 01 A_2=A_3=01 A 2 = A 3 = 01 verify the initial cases. For a parent P P P of length 2 p 2p 2 p , let pos ( 0 j ) \operatorname{pos}(0_j) pos ( 0 j ) and pos ( 1 j ) \operatorname{pos}(1_j) pos ( 1 j ) be its zero-based symbol positions. In S + ( P ) S_+(P) S + ( P ) , the positive α \alpha α gaps occur at index 1 and at 2 + pos ( 0 j ) 2+\operatorname{pos}(0_j) 2 + pos ( 0 j ) , while the positive β i − 1 \beta_{i-1} β i − 1 gaps occur at 2 + pos ( 1 j ) 2+\operatorname{pos}(1_j) 2 + pos ( 1 j ) . The final output one-run gives an additional index 2 p + 2 2p+2 2 p + 2 , outside the range 1 ≤ i ≤ 2 p + 1 1\le i\le2p+1 1 ≤ i ≤ 2 p + 1 . The listed supports partition that range. For S − ( P ) S_-(P) S − ( P ) the two supports are 1 + pos ( 0 j ) 1+\operatorname{pos}(0_j) 1 + pos ( 0 j ) and 1 + pos ( 1 j ) 1+\operatorname{pos}(1_j) 1 + pos ( 1 j ) , with the terminal index 2 p 2p 2 p omitted from 1 ≤ i ≤ 2 p − 1 1\le i\le2p-1 1 ≤ i ≤ 2 p − 1 . All indicated run lengths are positive by (2.3)–(2.4). The exceptional parent 01 is checked directly.
For the elementary word A k A_k A k write
q k = ℓ k / 2 = 2 k − 1 + ( − 1 ) k 3 , λ k = ⌊ k / 2 ⌋ . q_k=\ell_k/2=\frac{2^{k-1}+(-1)^k}{3},\qquad\lambda_k=\lfloor k/2\rfloor. q k = ℓ k /2 = 3 2 k − 1 + ( − 1 ) k , λ k = ⌊ k /2 ⌋ .
This elementary semilength q k q_k q k is independent of the family parameter. Let α i ( k ) , β i ( k ) \alpha_i^{(k)},\beta_i^{(k)} α i ( k ) , β i ( k ) be the two gap lists of A k A_k A k , with β 0 ( k ) = 0 \beta_0^{(k)}=0 β 0 ( k ) = 0 . Define an integer word V k \mathbf{V}_k V k of length q k q_k q k by
V k [ 1 ] = k + 1 , V k [ i ] = 2 + α i ( k ) + β i − 1 ( k ) ( 2 ≤ i ≤ q k ) . (58) \mathbf{V}_k[1]=k+1,\qquad\mathbf{V}_k[i]=2+\alpha_i^{(k)}+\beta_{i-1}^{(k)}\qquad(2\le i\le q_k). \tag*{(58)} V k [ 1 ] = k + 1 , V k [ i ] = 2 + α i ( k ) + β i − 1 ( k ) ( 2 ≤ i ≤ q k ) . (58)
These integer words are indexed from one, unlike the binary words. The number q k q_k q k is odd. Consequently the symmetry below lets us write
V k = ( k + 1 ) R k rev ( R k ) , ∣ R k ∣ = ( q k − 1 ) / 2. (59) \mathbf{V}_k=(k+1)\mathbf{R}_k\operatorname{rev}(\mathbf{R}_k),\qquad|\mathbf{R}_k|=(q_k-1)/2. \tag*{(59)} V k = ( k + 1 ) R k rev ( R k ) , ∣ R k ∣ = ( q k − 1 ) /2. (59)
The operation rev \operatorname{rev} rev reverses an integer word; it is not bitwise complementation. A half-word may be empty.
Lemma 7.3 (Elementary frequency symmetry and polynomial). Every V k \mathbf{V}_k V k has the form (59) . Define
B k ( z ) = ∑ i = 1 q k z V k [ i ] . B_k(z)=\sum_{i=1}^{q_k}z^{\mathbf{V}_k[i]}. B k ( z ) = i = 1 ∑ q k z V k [ i ] . Then
B 2 ( z ) = z 3 , B k + 1 ( z ) = z B k ( z ) + ( q k − ( − 1 ) k ) z 3 ( k ≥ 2 ) . (60) B_2(z)=z^3,\qquad B_{k+1}(z)=zB_k(z)+(q_k-(-1)^k)z^3\qquad(k\ge2). \tag*{(60)} B 2 ( z ) = z 3 , B k + 1 ( z ) = z B k ( z ) + ( q k − ( − 1 ) k ) z 3 ( k ≥ 2 ) . (60) Its leading coefficient is one, at degree k + 1 k+1 k + 1 , and its coefficient at degree k k k is zero.
Proof. Reverse-complement symmetry of A k A_k A k gives β i − 1 ( k ) = α q k + 2 − i ( k ) \beta_{i-1}^{(k)}=\alpha_{q_k+2-i}^{(k)} β i − 1 ( k ) = α q k + 2 − i ( k ) for 2 ≤ i ≤ q k 2\le i\le q_k 2 ≤ i ≤ q k . Thus the entries with indices 2 , … , q k 2,\ldots,q_k 2 , … , q k form a palindrome of even length, proving (59) .
For the polynomial statement let T k ∘ ( z ) T_k^\circ(z) T k ∘ ( z ) enumerate all constant runs of A k A_k A k , counting both symbols. The run expansions and the disjoint-support proof of Lemma 7.2, applied now to A k A_k A k , show that
B k ( z ) = z 2 T k ∘ ( z ) − 2 z λ k + 2 + z k + 1 . (61) B_k(z)=z^2T_k^\circ(z)-2z^{\lambda_k+2}+z^{k+1}. \tag*{(61)} B k ( z ) = z 2 T k ∘ ( z ) − 2 z λ k + 2 + z k + 1 . (61) The two subtracted terms are the omitted final one-run and the first zero-run, whose frequency is replaced by k + 1 k+1 k + 1 . The initial words A 2 = A 3 = 01 A_2=A_3=01 A 2 = A 3 = 01 satisfy the same identity directly. The number of constant runs is q k + 1 q_k+1 q k + 1 . The run expansions give
T k + 1 ∘ ( z ) = { z T k ∘ ( z ) + ( q k + 1 ) z , k odd , z T k ∘ ( z ) + ( q k − 1 ) z + 2 ( 1 − z ) z λ k , k even . T_{k+1}^\circ(z)=
\begin{cases}
zT_k^\circ(z)+(q_k+1)z, & k\ \text{odd},\\
zT_k^\circ(z)+(q_k-1)z+2(1-z)z^{\lambda_k}, & k\ \text{even}.
\end{cases} T k + 1 ∘ ( z ) = { z T k ∘ ( z ) + ( q k + 1 ) z , z T k ∘ ( z ) + ( q k − 1 ) z + 2 ( 1 − z ) z λ k , k odd , k even . For A 2 = 01 A_2=01 A 2 = 01 the second formula is checked separately; it remains valid. Substitution in (61) proves (60) . The leading coefficient and the missing next coefficient follow by induction, beginning with B 2 = z 3 B_2=z^3 B 2 = z 3 and B 3 = z 4 B_3=z^4 B 3 = z 4 .
Ordered natural frequencies: the repeated-join correction
Use the elementary integer frequency words V k \mathbf{V}_k V k , their palindromic tails R k \mathbf{R}_k R k , and polynomials B k ( z ) B_k(z) B k ( z ) of Lemma 7.3 . Let V ~ k \widetilde{\mathbf{V}}_k V k be obtained by increasing only the first entry of V k \mathbf{V}_k V k from k + 1 k+1 k + 1 to k + 2 k+2 k + 2 . This distinction is essential at the new repeated-pair joins.
Theorem 7.4 (Ordered family frequencies). For every p ≥ 2 p \ge2 p ≥ 2 and k ≥ 2 k \ge2 k ≥ 2 , the ordered frequencies on a p , k ≤ u < a p , k + 1 a_{p,k} \le u < a_{p,k+1} a p , k ≤ u < a p , k + 1 are exactly
V k V k + 1 ( V ~ k V k + 1 ) p − 2 V k + 2 . (62) \mathbf{V}_k\mathbf{V}_{k+1}(\widetilde{\mathbf{V}}_k\mathbf{V}_{k+1})^{p-2}\mathbf{V}_{k+2}. \tag*{(62)} V k V k + 1 ( V k V k + 1 ) p − 2 V k + 2 . (62) Consequently their polynomial is
P p , k ( z ) = ( p − 1 ) ( B k ( z ) + B k + 1 ( z ) ) + B k + 2 ( z ) + ( p − 2 ) ( z k + 2 − z k + 1 ) . (63) P_{p,k}(z)=(p-1)(B_k(z)+B_{k+1}(z))+B_{k+2}(z)+(p-2)(z^{k+2}-z^{k+1}). \tag*{(63)} P p , k ( z ) = ( p − 1 ) ( B k ( z ) + B k + 1 ( z )) + B k + 2 ( z ) + ( p − 2 ) ( z k + 2 − z k + 1 ) . (63) If v p , k = a p , k + 1 − a p , k = L p , k / 2 v_{p,k}=a_{p,k+1}-a_{p,k}=L_{p,k}/2 v p , k = a p , k + 1 − a p , k = L p , k /2 , then
P p , 2 ( z ) = 3 z 3 + ( 2 p − 3 ) z 4 + z 5 P p , k + 1 ( z ) = z P p , k ( z ) + ( v p , k − ( − 1 ) k ) z 3 ( k ≥ 2 ) . (64) \begin{aligned}
P_{p,2}(z)&=3z^3+(2p-3)z^4+z^5\\
P_{p,k+1}(z)&=zP_{p,k}(z)+(v_{p,k}-(-1)^k)z^3 \qquad(k\ge2). \tag*{(64)}
\end{aligned} P p , 2 ( z ) P p , k + 1 ( z ) = 3 z 3 + ( 2 p − 3 ) z 4 + z 5 = z P p , k ( z ) + ( v p , k − ( − 1 ) k ) z 3 ( k ≥ 2 ) . (64) The separate initial block has P p , 1 ( z ) = z 3 + ( p − 1 ) z 4 P_{p,1}(z)=z^3+(p-1)z^4 P p , 1 ( z ) = z 3 + ( p − 1 ) z 4 ; its step to k = 2 k=2 k = 2 must not be inferred from the displayed recursion. For every k ≥ 1 k\ge1 k ≥ 1 the total multiplicity on that block is
4 v p , k − 3 + ( − 1 ) k 2 . 4v_{p,k}-\frac{3+(-1)^k}{2}. 4 v p , k − 2 3 + ( − 1 ) k . For k ≥ 2 k\ge2 k ≥ 2 the largest multiplicity is k + 3 k+3 k + 3 , attained once, and
P p , k ( z ) v p , k ⟶ z 3 2 − z \frac{P_{p,k}(z)}{v_{p,k}}\longrightarrow\frac{z^3}{2-z} v p , k P p , k ( z ) ⟶ 2 − z z 3 in coefficient ℓ 1 \ell^1 ℓ 1 norm, with error O p ( k 2 − k ) O_p(k2^{-k}) O p ( k 2 − k ) .
In particular the limiting mean and variance are four and two.
Proof. By Lemma 7.1 , a complete interior plateau has frequency 2 + α i + β i − 1 2+\alpha_i+\beta_{i-1} 2 + α i + β i − 1 . The constant p − 2 p-2 p − 2 in the clock does not change plateau lengths. The first frequency at a macro boundary is still k + 1 k+1 k + 1 , because the initial and final constant runs of U p , k U_{p,k} U p , k have lengths ⌊ k / 2 ⌋ \lfloor k/2\rfloor ⌊ k /2 ⌋ and ⌊ k / 2 ⌋ + 1 \lfloor k/2\rfloor+1 ⌊ k /2 ⌋ + 1 independently of p p p . Their two-block overlap is included in Lemma 7.1 , also for k = 2 k=2 k = 2 .
At a join from A k A_k A k to A k + 1 A_{k+1} A k + 1 the frequency of the joining level is 2 + ⌊ k / 2 ⌋ + ⌊ ( k + 1 ) / 2 ⌋ = k + 2 2+\lfloor k/2\rfloor+\lfloor(k+1)/2\rfloor=k+2 2 + ⌊ k /2 ⌋ + ⌊( k + 1 ) /2 ⌋ = k + 2 . The reverse join to another A k A_k A k gives the same k + 2 k+2 k + 2 , not k + 1 k+1 k + 1 ; this is the changed first entry in V ~ k \widetilde{\mathbf{V}}_k V k . At the final join to A k + 2 A_{k+2} A k + 2 it is k + 3 k+3 k + 3 . All remaining entries are the corresponding unchanged elementary frequencies, also on a complemented factor because its two gap contributions exchange without reversing value order. This proves (62) and its polynomial.
Insert the scalar elementary recurrence (60) in (63) . The additional monomials advance by multiplication by z z z , and the new z 3 z^3 z 3 coefficient is v p , k − ( − 1 ) k v_{p,k}-(-1)^k v p , k − ( − 1 ) k . Directly B 2 = z 3 B_2=z^3 B 2 = z 3 , B 3 = z 4 B_3=z^4 B 3 = z 4 , B 4 = z 5 + 2 z 3 B_4=z^5+2z^3 B 4 = z 5 + 2 z 3 , giving the stated initial polynomial. Reading the first word separately gives P p , 1 P_{p,1} P p , 1 . Differentiation of (64) , starting at k = 2 k=2 k = 2 , proves the mass formula; k = 1 k=1 k = 1 is immediate from its explicit polynomial. The maximal degree and its coefficient follow from (63) : only B k + 2 B_{k+2} B k + 2 has degree k + 3 k+3 k + 3 . For completeness, put G ( z ) = z 3 / ( 2 − z ) G(z)=z^3/(2-z) G ( z ) = z 3 / ( 2 − z ) and E k = P p , k − v p , k G E_k=P_{p,k}-v_{p,k}G E k = P p , k − v p , k G . Since v p , k + 1 = 2 v p , k − ( − 1 ) k v_{p,k+1}=2v_{p,k}-(-1)^k v p , k + 1 = 2 v p , k − ( − 1 ) k ,
E k + 1 = z E k + ( − 1 ) k ( G − z 3 ) . E_{k+1}=zE_k+(-1)^k(G-z^3). E k + 1 = z E k + ( − 1 ) k ( G − z 3 ) .
The coefficient norm of G − z 3 G-z^3 G − z 3 is one, so ∥ E k ∥ 1 = O p ( k ) \lVert E_k\rVert_1=O_p(k) ∥ E k ∥ 1 = O p ( k ) . Division by v p , k ≍ 2 k v_{p,k}\asymp2^k v p , k ≍ 2 k proves the stated rate. To pass to the first two moments, on degrees at most k + 3 k+3 k + 3 multiply the coefficient error by at most ( k + 3 ) 2 (k+3)^2 ( k + 3 ) 2 ; the remaining geometric tail has second moment O ( k 2 2 − k ) O(k^2 2^{-k}) O ( k 2 2 − k ) . Both moments therefore converge to G ′ ( 1 ) = 4 G'(1)=4 G ′ ( 1 ) = 4 and G ′ ′ ( 1 ) + G ′ ( 1 ) − G ′ ( 1 ) 2 = 2 G''(1)+G'(1)-G'(1)^2=2 G ′′ ( 1 ) + G ′ ( 1 ) − G ′ ( 1 ) 2 = 2 .
Worked example: p = 3 p=3 p = 3 , a repeated join, and a dyadic cut
This example separates three operations: forming a signed binary word, recording its ordered multiplicities, and cutting at a power of two. For p = 3 p=3 p = 3 and elementary level k = 4 k=4 k = 4 ,
U 3 , 4 = A 4 A ‾ 5 A 4 A ‾ 5 A 6 , ( ℓ 4 , ℓ 5 , ℓ 6 ) = ( 6 , 10 , 22 ) . U_{3,4}=A_4\overline{A}_5A_4\overline{A}_5A_6,\qquad(\ell_4,\ell_5,\ell_6)=(6,10,22). U 3 , 4 = A 4 A 5 A 4 A 5 A 6 , ( ℓ 4 , ℓ 5 , ℓ 6 ) = ( 6 , 10 , 22 ) .
Its natural value-index block is 26 ≤ u < 53 26\le u<53 26 ≤ u < 53 , since a 3 , 4 = 26 a_{3,4}=26 a 3 , 4 = 26 and a 3 , 5 = 53 a_{3,5}=53 a 3 , 5 = 53 . The elementary frequency words are
V 4 = ( 5 , 3 , 3 ) , V 5 = ( 6 , 4 , 3 , 3 , 4 ) , V_4=(5,3,3),\qquad V_5=(6,4,3,3,4), V 4 = ( 5 , 3 , 3 ) , V 5 = ( 6 , 4 , 3 , 3 , 4 ) ,
V 6 = ( 7 , 5 , 3 , 3 , 4 , 3 , 3 , 4 , 3 , 3 , 5 ) . V_6=(7,5,3,3,4,3,3,4,3,3,5). V 6 = ( 7 , 5 , 3 , 3 , 4 , 3 , 3 , 4 , 3 , 3 , 5 ) .
The first A 4 A_4 A 4 contributes V 4 V_4 V 4 , but the second contributes V ~ 4 = ( 6 , 3 , 3 ) \widetilde V_4=(6,3,3) V 4 = ( 6 , 3 , 3 ) , not ( 5 , 3 , 3 ) (5,3,3) ( 5 , 3 , 3 ) . Indeed its preceding factor is A ‾ 5 \overline{A}_5 A 5 , and the two runs at this reverse join have lengths λ 5 = 2 \lambda_5=2 λ 5 = 2 and λ 4 = 2 \lambda_4=2 λ 4 = 2 . The joining multiplicity is 2 + 2 + 2 = 6 2+2+2=6 2 + 2 + 2 = 6 rather than the distinguished first entry 5 5 5 of V 4 V_4 V 4 . The complete natural frequency word is therefore
V 4 V 5 ( 6 , 3 , 3 ) V 5 V 6 . V_4V_5(6,3,3)V_5V_6. V 4 V 5 ( 6 , 3 , 3 ) V 5 V 6 .
The five factor beginnings are u = 26 , 29 , 34 , 37 , 42 u=26,29,34,37,42 u = 26 , 29 , 34 , 37 , 42 . Their first frequencies are 5 , 6 , 6 , 6 , 7 5,6,6,6,7 5 , 6 , 6 , 6 , 7 , respectively. In particular the extra join changes the multiplicity of the actual value 2 ⋅ 34 + 1 = 69 2\cdot34+1=69 2 ⋅ 34 + 1 = 69 from the uncorrected prediction 5 5 5 to 6 6 6 . Taking a histogram gives
P 3 , 4 ( z ) = 14 z 3 + 6 z 4 + 3 z 5 + 3 z 6 + z 7 . P_{3,4}(z)=14z^3+6z^4+3z^5+3z^6+z^7. P 3 , 4 ( z ) = 14 z 3 + 6 z 4 + 3 z 5 + 3 z 6 + z 7 .
Now cut at the pure dyadic endpoints 32 32 32 and 64 64 64 , so j = 5 j=5 j = 5 . Here d = 1 d=1 d = 1 , b = 2 b=2 b = 2 , k = 4 k=4 k = 4 , and the two integers in the nonpower case are t = 2 b − p = 1 t=2b-p=1 t = 2 b − p = 1 and u = 2 p − 2 b − 1 = 1 u=2p-2b-1=1 u = 2 p − 2 b − 1 = 1 . The lower cut lies in the first V 5 V_5 V 5 , starting at 29 29 29 : its distance is 32 − 29 = 3 = ( q 5 + 1 ) / 2 32-29=3=(q_5+1)/2 32 − 29 = 3 = ( q 5 + 1 ) /2 . As V 5 = 6 ( 4 , 3 ) ( 3 , 4 ) V_5=6(4,3)(3,4) V 5 = 6 ( 4 , 3 ) ( 3 , 4 ) , the retained suffix is rev ( R 5 ) = ( 3 , 4 ) \operatorname{rev}(R_5)=(3,4) rev ( R 5 ) = ( 3 , 4 ) . In the next natural block, V 6 V_6 V 6 starts at 58 58 58 , and 64 − 58 = 6 = ( q 6 + 1 ) / 2 64-58=6=(q_6+1)/2 64 − 58 = 6 = ( q 6 + 1 ) /2 ; thus the retained prefix is 7 R 6 = ( 7 , 5 , 3 , 3 , 4 , 3 ) 7R_6=(7,5,3,3,4,3) 7 R 6 = ( 7 , 5 , 3 , 3 , 4 , 3 ) . Equation (68) becomes the explicit concatenation
( 3 , 4 ) V ~ 4 V 5 V 6 V 5 ( 7 , 5 , 3 , 3 , 4 , 3 ) . (3,4)\,\widetilde V_4V_5V_6V_5(7,5,3,3,4,3). ( 3 , 4 ) V 4 V 5 V 6 V 5 ( 7 , 5 , 3 , 3 , 4 , 3 ) .
Its 32 entries have histogram
D 3 , 5 ( z ) = 16 z 3 + 8 z 4 + 3 z 5 + 3 z 6 + 2 z 7 . D_{3,5}(z)=16z^3+8z^4+3z^5+3z^6+2z^7. D 3 , 5 ( z ) = 16 z 3 + 8 z 4 + 3 z 5 + 3 z 6 + 2 z 7 .
The two maximal multiplicities, both seven, occur at u = 42 , 58 u=42,58 u = 42 , 58 ; the three second-largest multiplicities, all six, occur at u = 34 , 37 , 53 u=34,37,53 u = 34 , 37 , 53 . These positions distinguish the ordered result from its histogram. The mean is 4 − 2 − 5 4-2^{-5} 4 − 2 − 5 , the variance is 1567 / 1024 1567/1024 1567/1024 , and the total-variation distance from z 3 / ( 2 − z ) z^3/(2-z) z 3 / ( 2 − z ) is 1 / 16 1/16 1/16 , as given by Corollary 7.6 .
Closed formulas on pure dyadic value blocks
Define
D p , j ( z ) = ∑ u = 2 j 2 j + 1 − 1 z ν p ( 2 u + 1 ) , d = ⌊ log 2 p ⌋ , b = 2 d , k = j − d . D_{p,j}(z)=\sum_{u=2^j}^{2^{j+1}-1}z^{\nu_p(2u+1)},\qquad d=\lfloor\log_2 p\rfloor,\quad b=2^d,\quad k=j-d. D p , j ( z ) = u = 2 j ∑ 2 j + 1 − 1 z ν p ( 2 u + 1 ) , d = ⌊ log 2 p ⌋ , b = 2 d , k = j − d .
The following formulas cover every sufficiently large dyadic value block for each p p p , with an explicit threshold j ≥ d + 2 j\ge d+2 j ≥ d + 2 . The smaller, finitely many blocks are fixed by the initial construction.
Theorem 7.5 (Parameter-dependent pure dyadic histograms). For j ≥ d + 2 j\ge d+2 j ≥ d + 2 , if p = b p=b p = b is a power of two, then
D p , j ( z ) = ∑ r = 3 k + 1 2 j + 2 − r z r + 2 z k + 2 + ( 2 p − 3 ) z k + 3 + z k + 4 . (65) D_{p,j}(z)=\sum_{r=3}^{k+1}2^{j+2-r}z^r+2z^{k+2}+(2p-3)z^{k+3}+z^{k+4}. \tag*{(65)} D p , j ( z ) = r = 3 ∑ k + 1 2 j + 2 − r z r + 2 z k + 2 + ( 2 p − 3 ) z k + 3 + z k + 4 . (65) If b < p < 2 b b<p<2b b < p < 2 b , then
D p , j ( z ) = ∑ r = 3 k 2 j + 2 − r z r + ( 4 b − 2 p + 1 ) z k + 1 D_{p,j}(z)=\sum_{r=3}^{k}2^{j+2-r}z^r+(4b-2p+1)z^{k+1} D p , j ( z ) = r = 3 ∑ k 2 j + 2 − r z r + ( 4 b − 2 p + 1 ) z k + 1 + ( 4 p − 4 b − 1 ) z k + 2 + ( 4 b − 2 p ) z k + 3 . (66) \qquad+(4p-4b-1)z^{k+2}+(4b-2p)z^{k+3}. \tag*{(66)} + ( 4 p − 4 b − 1 ) z k + 2 + ( 4 b − 2 p ) z k + 3 . (66) An empty sum is zero. All displayed coefficients are positive integers. For each fixed p p p , the normalized law tends to G ( z ) = z 3 / ( 2 − z ) G(z)=z^3/(2-z) G ( z ) = z 3 / ( 2 − z ) . For every p > 2 p>2 p > 2 , however, its finite histogram differs from { 3 + ν 2 ( a ) : 1 ≤ a ≤ 2 j } \{3+\nu_2(a):1\le a\le2^j\} { 3 + ν 2 ( a ) : 1 ≤ a ≤ 2 j } on all blocks in the stated range.
Proof. The lower cut 2 j 2^j 2 j lies in macro block k = j − d k=j-d k = j − d , since c p < 6 b < 2 c p c_p<6b<2c_p c p < 6 b < 2 c p . There are two possible geometries.
If p = b p=b p = b , the cut bisects the final word V k + 2 \mathbf{V}_{k+2} V k + 2 , in the sense that it follows its distinguished first entry and its first palindromic half. The retained suffix is rev ( R k + 2 ) \operatorname{rev}(\mathbf{R}_{k+2}) rev ( R k + 2 ) . The upper cut is in the corresponding factor of the next macro block, retaining its first entry and first half. Thus the full ordered word is
rev ( R k + 2 ) V k + 1 V k + 2 ( V ~ k + 1 V k + 2 ) p − 2 ( k + 4 ) R k + 3 . (67) \operatorname{rev}(\mathbf{R}_{k+2})\mathbf{V}_{k+1}\mathbf{V}_{k+2}(\widetilde{\mathbf{V}}_{k+1}\mathbf{V}_{k+2})^{p-2}(k+4)\mathbf{R}_{k+3}. \tag*{(67)} rev ( R k + 2 ) V k + 1 V k + 2 ( V k + 1 V k + 2 ) p − 2 ( k + 4 ) R k + 3 . (67)
This includes exactly the three-word case at p = 2 p=2 p = 2 .
If p > b p>b p > b , put t = 2 b − p ≥ 1 t=2b-p\ge1 t = 2 b − p ≥ 1 , u = 2 p − 2 b − 1 ≥ 1 u=2p-2b-1\ge1 u = 2 p − 2 b − 1 ≥ 1 . The lower cut is in the t t t -th complemented factor, of level k + 1 k+1 k + 1 . Its exact starting value index is
a p , k + ( t − 1 ) 2 k − 1 + ℓ k / 2 = ( 6 b − 1 ) 2 k − 3 + ( − 1 ) k 6 . a_{p,k}+(t-1)2^{k-1}+\ell_k/2=\frac{(6b-1)2^k-3+(-1)^k}{6}. a p , k + ( t − 1 ) 2 k − 1 + ℓ k /2 = 6 ( 6 b − 1 ) 2 k − 3 + ( − 1 ) k .
Its distance to 2 j 2^j 2 j is ( q k + 1 + 1 ) / 2 (q_{k+1}+1)/2 ( q k + 1 + 1 ) /2 , where q ℓ = ℓ ℓ / 2 q_\ell=\ell_\ell/2 q ℓ = ℓ ℓ /2 . This is precisely the same palindromic half-cut, not an asymptotic cut. The whole ordered word is
rev ( R k + 1 ) ( V ~ k V k + 1 ) u V k + 2 \operatorname{rev}(\mathbf{R}_{k+1})(\widetilde{\mathbf{V}}_k\mathbf{V}_{k+1})^u\mathbf{V}_{k+2} rev ( R k + 1 ) ( V k V k + 1 ) u V k + 2
V k + 1 ( V k + 2 V ~ k + 1 ) t − 1 ( k + 3 ) R k + 2 . (68) \mathbf{V}_{k+1}(\mathbf{V}_{k+2}\widetilde{\mathbf{V}}_{k+1})^{t-1}(k+3)\mathbf{R}_{k+2}. \tag*{(68)} V k + 1 ( V k + 2 V k + 1 ) t − 1 ( k + 3 ) R k + 2 . (68)
For the power case the analogous distance is ( q k + 2 + 1 ) / 2 (q_{k+2}+1)/2 ( q k + 2 + 1 ) /2 . These exact distances prove both ordered statements, including endpoint placement and every distinguished-entry correction.
The polynomial of R l \mathbf{R}_l R l is ( B l − z l + 1 ) / 2 (\mathcal{B}_l-z^{l+1})/2 ( B l − z l + 1 ) /2 . Hence (67) gives
D p , j = ( p − 1 ) B k + 1 + ( p − 1 2 ) B k + 2 + 1 2 B k + 3 − ( p − 2 ) z k + 2 + ( p − 5 2 ) z k + 3 + 1 2 z k + 4 , (69) D_{p,j}=(p-1)\mathcal{B}_{k+1}+\left(p-\frac{1}{2}\right)\mathcal{B}_{k+2}+\frac{1}{2}\mathcal{B}_{k+3}-(p-2)z^{k+2}+\left(p-\frac{5}{2}\right)z^{k+3}+\frac{1}{2}z^{k+4}, \tag*{(69)} D p , j = ( p − 1 ) B k + 1 + ( p − 2 1 ) B k + 2 + 2 1 B k + 3 − ( p − 2 ) z k + 2 + ( p − 2 5 ) z k + 3 + 2 1 z k + 4 , (69)
whereas (68) gives
D p , j = u B k + ( p − 1 2 ) B k + 1 + ( t + 1 2 ) B k + 2 − u z k + 1 + ( u − t + 1 2 ) z k + 2 + ( t − 1 2 ) z k + 3 . (70) D_{p,j}=u\mathcal{B}_k+\left(p-\frac{1}{2}\right)\mathcal{B}_{k+1}+\left(t+\frac{1}{2}\right)\mathcal{B}_{k+2}-uz^{k+1}+\left(u-t+\frac{1}{2}\right)z^{k+2}+\left(t-\frac{1}{2}\right)z^{k+3}. \tag*{(70)} D p , j = u B k + ( p − 2 1 ) B k + 1 + ( t + 2 1 ) B k + 2 − u z k + 1 + ( u − t + 2 1 ) z k + 2 + ( t − 2 1 ) z k + 3 . (70)
One may simplify them using the exact rational expression
B l ( z ) = 2 l z 3 6 ( 2 − z ) + 2 ( − 1 ) l z 3 3 ( z + 1 ) + z l + 2 ( z − 1 ) ( z − 2 ) ( z + 1 ) ( l ≥ 2 ) . (71) \mathcal{B}_l(z)=\frac{2^l z^3}{6(2-z)}+\frac{2(-1)^l z^3}{3(z+1)}+\frac{z^{l+2}(z-1)}{(z-2)(z+1)}\qquad(l\ge2). \tag*{(71)} B l ( z ) = 6 ( 2 − z ) 2 l z 3 + 3 ( z + 1 ) 2 ( − 1 ) l z 3 + ( z − 2 ) ( z + 1 ) z l + 2 ( z − 1 ) ( l ≥ 2 ) . (71)
This identity follows from B 2 = z 3 \mathcal{B}_2=z^3 B 2 = z 3 and (60) ; its apparent poles cancel because the left side is a polynomial. In both combinations the alternating term cancels. The coefficients remaining at the last three degrees are precisely those in (65) or (66) ; all lower coefficients are 2 j + 2 − r 2^{j+2-r} 2 j + 2 − r . This proves the formulas. Their coefficients sum to 2 j 2^j 2 j , and their tail discrepancy from 2 j G 2^jG 2 j G has bounded coefficient norm for fixed p p p , proving convergence. For p > 2 p>2 p > 2 their maximal degree is strictly below j + 3 j+3 j + 3 , so the original shifted-valuation histogram is not equal to them.
For example, in their respective stated ranges,
D 3 , j = D 2 , j − z j + z j + 1 + z j + 2 − z j + 3 , (72) D_{3,j}=D_{2,j}-z^j+z^{j+1}+z^{j+2}-z^{j+3}, \tag*{(72)} D 3 , j = D 2 , j − z j + z j + 1 + z j + 2 − z j + 3 , (72)
D 4 , j = D 2 , j − 2 z j + 3 z j + 1 − z j + 3 . (73) D_{4,j}=D_{2,j}-2z^j+3z^{j+1}-z^{j+3}. \tag*{(73)} D 4 , j = D 2 , j − 2 z j + 3 z j + 1 − z j + 3 . (73)
Thus Q 3 Q_3 Q 3 and Q 4 Q_4 Q 4 preserve every sufficiently low multiplicity count exactly, but redistribute the top of the histogram. Treating them as unchanged copies of Theorem A.8 would be incorrect.
Corollary 7.6 (Exact moments, distance, and cumulative count). Choose u u u uniformly from [ 2 j , 2 j + 1 ) [2^j,2^{j+1}) [ 2 j , 2 j + 1 ) , with j ≥ d + 2 j\ge d+2 j ≥ d + 2 , and set X p , j = ν p ( 2 u + 1 ) X_{p,j}=\nu_p(2u+1) X p , j = ν p ( 2 u + 1 ) . Then
E X p , j = 4 − 2 − j , (74) \mathbb{E}X_{p,j}=4-2^{-j}, \tag*{(74)} E X p , j = 4 − 2 − j , (74) Var ( X p , j ) = 2 − ( 2 ( j − d ) + 4 p − 5 ) 2 − j − 4 − j . (75) \operatorname{Var}(X_{p,j})=2-\left(2(j-d)+4p-5\right)2^{-j}-4^{-j}. \tag*{(75)} Var ( X p , j ) = 2 − ( 2 ( j − d ) + 4 p − 5 ) 2 − j − 4 − j . (75) The total-variation distance to the geometric limit is exactly
d T V ( X p , j , G ) = T p 2 − j , T p = { 3 p 2 − 3 + ( 1 − p / 4 ) + , p = b , ( 4 p − 5 b − 1 ) + + ( 7 b / 2 − 2 p ) + , b < p < 2 b , (76) d_{\mathrm{TV}}(X_{p,j},G)=T_p2^{-j},\qquad T_p=
\begin{cases}
\frac{3p}{2}-3+(1-p/4)_+, & p=b,\\
(4p-5b-1)_++(7b/2-2p)_+, & b<p<2b,
\end{cases} \tag*{(76)} d TV ( X p , j , G ) = T p 2 − j , T p = { 2 3 p − 3 + ( 1 − p /4 ) + , ( 4 p − 5 b − 1 ) + + ( 7 b /2 − 2 p ) + , p = b , b < p < 2 b , (76) where x + = max ( x , 0 ) x_+=\max(x,0) x + = max ( x , 0 ) . The coefficient ℓ 1 \ell^1 ℓ 1 distance is twice this number. Also the count over the entire infinite sequence is
# { n ≥ 1 : Q p ( n ) < 2 j + 1 } = 2 j + 2 − j + d + 2 − 2 p . (77) \#\{n\ge1:Q_p(n)<2^{j+1}\}=2^{j+2}-j+d+2-2p. \tag*{(77)} # { n ≥ 1 : Q p ( n ) < 2 j + 1 } = 2 j + 2 − j + d + 2 − 2 p . (77) This does not assert that the counted indices form an initial interval.
Proof. Differentiation of the finite polynomials yields E X = 4 − 2 − j \operatorname{E}X=4-2^{-j} E X = 4 − 2 − j and E X 2 = 18 − ( 2 k + 4 p + 3 ) 2 − j \operatorname{E}X^2=18-(2k+4p+3)2^{-j} E X 2 = 18 − ( 2 k + 4 p + 3 ) 2 − j , proving the variance. For completeness, in the nonpower case the nonzero leading coefficients of D p , j − 2 j G D_{p,j}-2^jG D p , j − 2 j G , at degrees k + 1 k+1 k + 1 , k + 2 k+2 k + 2 , k + 3 k+3 k + 3 , are
− ( 2 p − 2 b − 1 ) , 4 p − 5 b − 1 , 7 b / 2 − 2 p . -(2p-2b-1),\qquad4p-5b-1,\qquad7b/2-2p. − ( 2 p − 2 b − 1 ) , 4 p − 5 b − 1 , 7 b /2 − 2 p .
All remaining coefficients are a negative geometric tail. In the power case the corresponding coefficients at k + 2 k+2 k + 2 , k + 3 k+3 k + 3 , k + 4 k+4 k + 4 are
2 − p , 3 p / 2 − 3 , 1 − p / 4 , 2-p,\qquad3p/2-3,\qquad1-p/4, 2 − p , 3 p /2 − 3 , 1 − p /4 ,
again followed by a negative tail. Their positive mass divided by 2 j 2^j 2 j gives (76) exactly. For the cumulative formula, the initial values u = 0 , … , p − 2 u=0,\ldots,p-2 u = 0 , … , p − 2 have multiplicity two and u = p − 1 u=p-1 u = p − 1 has multiplicity four. Up to the beginning a p , k a_{p,k} a p , k , sum these 2 p + 2 2p+2 2 p + 2 occurrences and the complete natural-block masses in Theorem 7.4. At the lower pure-dyadic cut, add the complete elementary words and the first palindromic half identified in the preceding proof. The required elementary masses are
B l ′ ( 1 ) = 4 q l − 1 + ( − 1 ) l 2 , first-half mass = B l ′ ( 1 ) + l + 1 2 . B'_l(1)=4q_l-\frac{1+(-1)^l}{2},\qquad\text{first-half mass}=\frac{B'_l(1)+l+1}{2}. B l ′ ( 1 ) = 4 q l − 2 1 + ( − 1 ) l , first-half mass = 2 B l ′ ( 1 ) + l + 1 .
each tilde word adds one. In the power case the partial contribution is
( p − 1 ) ( B k ′ ( 1 ) + B k + 1 ′ ( 1 ) ) + ( p − 2 ) + B k + 2 ′ ( 1 ) + k + 3 2 , (p-1)(B'_k(1)+B'_{k+1}(1))+(p-2)+\frac{B'_{k+2}(1)+k+3}{2}, ( p − 1 ) ( B k ′ ( 1 ) + B k + 1 ′ ( 1 )) + ( p − 2 ) + 2 B k + 2 ′ ( 1 ) + k + 3 ,
and in the nonpower case it is
t B k ′ ( 1 ) + ( t − 1 ) B k + 1 ′ ( 1 ) + ( t − 1 ) + B k + 1 ′ ( 1 ) + k + 2 2 . tB'_k(1)+(t-1)B'_{k+1}(1)+(t-1)+\frac{B'_{k+1}(1)+k+2}{2}. t B k ′ ( 1 ) + ( t − 1 ) B k + 1 ′ ( 1 ) + ( t − 1 ) + 2 B k + 1 ′ ( 1 ) + k + 2 .
Substitution of q l q_l q l , a p , k a_{p,k} a p , k and j = k + d j=k+d j = k + d in either expression, including the complete preceding masses, gives 4 ⋅ 2 j − k + 2 − 2 p 4\cdot2^j-k+2-2p 4 ⋅ 2 j − k + 2 − 2 p , which is (77) .
Proposition 7.7 (All locations of the two largest multiplicities). Continue to assume j ≥ d + 2 j\ge d+2 j ≥ d + 2 , k = j − d k=j-d k = j − d . If p = b p=b p = b , the maximum is k + 4 k+4 k + 4 , attained only at
u = a p , k + 1 + ( p − 1 ) 2 k . u=a_{p,k+1}+(p-1)2^k. u = a p , k + 1 + ( p − 1 ) 2 k . The next largest multiplicity k + 3 k+3 k + 3 occurs at exactly
a p , k + 1 + i 2 k ( 1 ≤ i ≤ p − 2 ) , a_{p,k+1}+i2^k\qquad(1\le i\le p-2), a p , k + 1 + i 2 k ( 1 ≤ i ≤ p − 2 ) , a p , k + 1 + i 2 k + q k + 1 ( 0 ≤ i ≤ p − 2 ) . a_{p,k+1}+i2^k+q_{k+1}\qquad(0\le i\le p-2). a p , k + 1 + i 2 k + q k + 1 ( 0 ≤ i ≤ p − 2 ) . Its count is 2 p − 3 2p-3 2 p − 3 . If p > b p>b p > b , put t = 2 b − p t=2b-p t = 2 b − p . The maximum k + 3 k+3 k + 3 occurs exactly at
a p , k + ( p − 1 ) 2 k − 1 , a_{p,k}+(p-1)2^{k-1}, a p , k + ( p − 1 ) 2 k − 1 , a p , k + 1 + i 2 k ( 1 ≤ i ≤ t − 1 ) , a_{p,k+1}+i2^k\qquad(1\le i\le t-1), a p , k + 1 + i 2 k ( 1 ≤ i ≤ t − 1 ) , a p , k + 1 + i 2 k + q k + 1 ( 0 ≤ i ≤ t − 1 ) . a_{p,k+1}+i2^k+q_{k+1}\qquad(0\le i\le t-1). a p , k + 1 + i 2 k + q k + 1 ( 0 ≤ i ≤ t − 1 ) . There are 2 t = 4 b − 2 p 2t=4b-2p 2 t = 4 b − 2 p maximizers. The next largest multiplicity k + 2 k+2 k + 2 occurs at a p , k + 1 a_{p,k+1} a p , k + 1 and at
a p , k + i 2 k − 1 , a p , k + i 2 k − 1 + q k ( t ≤ i ≤ p − 2 ) . a_{p,k}+i2^{k-1},\qquad a_{p,k}+i2^{k-1}+q_k\qquad(t\le i\le p-2). a p , k + i 2 k − 1 , a p , k + i 2 k − 1 + q k ( t ≤ i ≤ p − 2 ) . Its count is 4 p − 4 b − 1 4p-4b-1 4 p − 4 b − 1 . Every position listed is a value index u u u ; the corresponding actual value is 2 u + 1 2u+1 2 u + 1 .
Proof. The only entry l + 1 l+1 l + 1 of V l V_l V l is its first; none of its remaining entries equals l l l . In a tilde word the first entry is l + 2 l+2 l + 2 , while the remaining entries stay unchanged. Read these positions in the exact ordered words (67) and (68) and translate each factor beginning to its value coordinate. The displayed lists exhaust all occurrences; their cardinalities agree with the top two coefficients of the finite histogram formulas.
Figure 6. Exact top multiplicities on the same pure dyadic value block j = 12 j=12 j = 12 , for p = 2 , 3 , 4 p=2,3,4 p = 2 , 3 , 4 . The low part of the histogram agrees; the largest multiplicities do not. In particular the Q 3 Q_3 Q 3 maximum is attained twice, whereas the Q 4 Q_4 Q 4 maximum is attained once.
Exact summation and the periodic linear term
Put S p ( N ) = ∑ n = 1 N Q p ( n ) S_p(N)=\sum_{n=1}^{N}Q_p(n) S p ( N ) = ∑ n = 1 N Q p ( n ) and E p ( N ) = S p ( N ) − N ( N + 1 ) / 4 \mathcal{E}_p(N)=S_p(N)-N(N+1)/4 E p ( N ) = S p ( N ) − N ( N + 1 ) /4 .
Theorem 8.1 (Parameter-dependent exact summation). Let M ≥ p + 2 M\ge p+2 M ≥ p + 2 and choose K K K by s p , K ≤ M < s p , K + 1 s_{p,K}\le M<s_{p,K+1} s p , K ≤ M < s p , K + 1 . With T = M − s p , K + 1 T=M-s_{p,K}+1 T = M − s p , K + 1 ,
E p ( 2 M ) = ( K + 2 p − 5 2 ) ( M + 1 ) − ∑ k = 1 K s p , k + 3 2 − p 2 − ⌊ K − 1 2 ⌋ 1 { K e v e n } h U p , K ( T ) . (78) \mathcal{E}_p(2M)=(K+2p-\frac{5}{2})(M+1)-\sum_{k=1}^{K}s_{p,k}+\frac{3}{2}-p^2-\left\lfloor\frac{K-1}{2}\right\rfloor\mathbf{1}_{\{K\ \mathrm{even}\}}hU_{p,K}(T). \tag*{(78)} E p ( 2 M ) = ( K + 2 p − 2 5 ) ( M + 1 ) − k = 1 ∑ K s p , k + 2 3 − p 2 − ⌊ 2 K − 1 ⌋ 1 { K even } h U p , K ( T ) . (78) where
∑ k = 1 K s p , k = C p 3 ( 2 K + 1 − 2 ) − ( p − 1 ) K − ( − 1 ) K − 1 6 − ⌊ ( K − 1 ) 2 4 ⌋ . (79) \sum_{k=1}^{K}s_{p,k}=\frac{C_p}{3}(2^{K+1}-2)-(p-1)K-\frac{(-1)^K-1}{6}-\left\lfloor\frac{(K-1)^2}{4}\right\rfloor. \tag*{(79)} k = 1 ∑ K s p , k = 3 C p ( 2 K + 1 − 2 ) − ( p − 1 ) K − 6 ( − 1 ) K − 1 − ⌊ 4 ( K − 1 ) 2 ⌋ . (79) Define Ψ p \Psi_p Ψ p by continuous one-periodic extension of
Ψ p ( θ ) = p − 1 − 1 2 log 2 C p − θ 2 − 2 − θ ( 0 ≤ θ ≤ 1 ) . (80) \Psi_p(\theta)=p-1-\frac{1}{2}\log_2 C_p-\frac{\theta}{2}-2^{-\theta}\qquad(0\le\theta\le1). \tag*{(80)} Ψ p ( θ ) = p − 1 − 2 1 log 2 C p − 2 θ − 2 − θ ( 0 ≤ θ ≤ 1 ) . (80) Then for all integer N → ∞ N\to\infty N → ∞ ,
S p ( N ) = N 2 4 + N 2 log 2 N + N Ψ p ( { log 2 ( N / C p ) } ) + O p ( N log N ) . (81) S_p(N)=\frac{N^2}{4}+\frac{N}{2}\log_2N+N\Psi_p(\{\log_2(N/C_p)\})+O_p\left(\frac{N}{\sqrt{\log N}}\right). \tag*{(81)} S p ( N ) = 4 N 2 + 2 N log 2 N + N Ψ p ({ log 2 ( N / C p )}) + O p ( log N N ) . (81)
At even cutoffs, retaining the exact last height refines this to
S p ( N ) = N 2 4 + N 2 log 2 N + N Ψ p ( { log 2 ( N / C p ) } ) − 1 { K e v e n } h U p , K ( T ) + O p ( ( log N ) 2 ) . (82) S_p(N) = \frac{N^2}{4} + \frac{N}{2}\log_2 N + N\Psi_p(\{\log_2(N/C_p)\}) - 1_{\{K\ {\rm even}\}}h_{U_{p,K}}(T) + O_p((\log N)^2). \tag*{(82)} S p ( N ) = 4 N 2 + 2 N log 2 N + N Ψ p ({ log 2 ( N / C p )}) − 1 { K even } h U p , K ( T ) + O p (( log N ) 2 ) . (82)
Thus the coefficient of N log 2 N N\log_2 N N log 2 N remains 1 / 2 1/2 1/2 , independently of p p p , and the periodic shape is universal up to its explicit vertical constant and phase scale. The improved O p ( ( log N ) 2 ) O_p((\log N)^2) O p (( log N ) 2 ) remainder on odd macro levels survives for every parameter.
Proof. The symmetric mode is
F p ( m ) + G p ( m ) − m = d p , k + 1 { k e v e n } U p , k [ t ] ( m = s p , k + t ) . F_p(m) + G_p(m) - m = d_{p,k} + 1_{\{k\ {\rm even}\}}U_{p,k}[t] \qquad(m = s_{p,k} + t). F p ( m ) + G p ( m ) − m = d p , k + 1 { k even } U p , k [ t ] ( m = s p , k + t ) .
Consequently the contribution of a parity pair to ε p \varepsilon_p ε p is k + 2 p − 5 / 2 k+2p-5/2 k + 2 p − 5/2 on odd macro levels and k + 2 p − 5 / 2 − ( h ( t + 1 ) − h ( t ) ) k+2p-5/2-(h(t+1)-h(t)) k + 2 p − 5/2 − ( h ( t + 1 ) − h ( t )) on even ones. The first p + 1 p+1 p + 1 pairs have total error
∑ m = 1 p ( 2 m − 3 / 2 ) + ( 2 p − 7 / 2 ) = p 2 + 3 p 2 − 7 2 . \sum_{m=1}^{p}(2m-3/2)+(2p-7/2)=p^2+\frac{3p}{2}-\frac{7}{2}. m = 1 ∑ p ( 2 m − 3/2 ) + ( 2 p − 7/2 ) = p 2 + 2 3 p − 2 7 .
An entire even macro block subtracts one height unit, since its last retained prefix has height one. Sum the half-open macro blocks and telescope their clock differences. The resulting constant is
p 2 + 3 p 2 − 7 2 − ( 2 p − 5 2 ) ( p + 2 ) = 3 2 − p 2 , p^2+\frac{3p}{2}-\frac{7}{2}-(2p-\frac{5}{2})(p+2)=\frac{3}{2}-p^2, p 2 + 2 3 p − 2 7 − ( 2 p − 2 5 ) ( p + 2 ) = 2 3 − p 2 ,
which proves (78) . Summing (12) proves (79) .
Uniformly on the last macro block, ∣ h U p , K ∣ = O p ( 2 K / K ) |h_{U_{p,K}}|=O_p(2^K/\sqrt{K}) ∣ h U p , K ∣ = O p ( 2 K / K ) . Thus for N = 2 M N=2^M N = 2 M ,
ε p ( 2 M ) = M ( K + 2 p − 5 2 ) − c p 3 2 K + 1 + O p ( K 2 + 2 K / K ) . \varepsilon_p(2^M)=M(K+2p-\frac{5}{2})-\frac{c_p}{3}2^{K+1}+O_p(K^2+2^K/\sqrt{K}). ε p ( 2 M ) = M ( K + 2 p − 2 5 ) − 3 c p 2 K + 1 + O p ( K 2 + 2 K / K ) .
The actual clock differs from ( c p / 3 ) 2 K (c_p/3)2^K ( c p /3 ) 2 K by O p ( K ) O_p(K) O p ( K ) . Replacing its level by ⌊ log 2 ( N / C p ) ⌋ \lfloor\log_2(N/C_p)\rfloor ⌊ log 2 ( N / C p )⌋ changes this main expression by only O p ( K ) O_p(K) O p ( K ) in the possible short displaced boundary intervals. Set θ = { log 2 ( N / C p ) } \theta=\{\log_2(N/C_p)\} θ = { log 2 ( N / C p )} and use ( c p / 3 ) 2 K 0 + 1 = N 2 − θ (c_p/3)2^{K_0+1}=N2^{-\theta} ( c p /3 ) 2 K 0 + 1 = N 2 − θ . Adding N ( N + 1 ) / 4 N(N+1)/4 N ( N + 1 ) /4 gives (81) ; keeping the height gives (82) . The periodic function has equal endpoint values and is Lipschitz. For odd N N N , add its last term to the formula at N − 1 N-1 N − 1 and use the pointwise growth bound. The leading increment is N / 2 + O p ( log N ) N/2+O_p(\log N) N /2 + O p ( log N ) , and the periodic term changes by O p ( 1 ) O_p(1) O p ( 1 ) ; the stated error follows.
Figure 7. The Q 3 Q_3 Q 3 summatory residual compared with Ψ 3 \Psi_3 Ψ 3 . Odd macro levels lose the last-height term entirely; even levels retain it. These data use exact cumulative sums of the directly computed sequence.
Comparison with the original perturbation
The elementary words are related to those in Cloitre’s analysis of A394051 [3 Section 2.3 and Lemma 4.3] . In that notation the positive step word starts with P 0 = 001011 P_0 = 001011 P 0 = 001011 , and the two word laws are
N r = I 1 ( P r [ 2 : ] , P r [ : − 1 ] ) , P r + 1 = I 0 ( 00 N r 1 , 0 N r ) . N_r = \mathcal{I}_1(P_r[2:], P_r[:-1]), \qquad P_{r+1} = \mathcal{I}_0(00N_r1, 0N_r). N r = I 1 ( P r [ 2 : ] , P r [ : − 1 ]) , P r + 1 = I 0 ( 00 N r 1 , 0 N r ) .
For words in this family the designated tapes do not require a fallback. The family construction and proofs do not assume the existence of the original sequence or an asymptotic theorem about it.
The identification is
A 2 r + 4 = P r , A 2 r + 5 = 0 N r ( r ≥ 0 ) . (83) A_{2r+4} = P_r, \qquad A_{2r+5} = 0N_r \qquad(r \ge0). \tag*{(83)} A 2 r + 4 = P r , A 2 r + 5 = 0 N r ( r ≥ 0 ) . (83)
Indeed A 4 = P 0 A_4 = P_0 A 4 = P 0 . When P P P begins with two zeros, deleting the first output zero from S − ( P ) S_-(P) S − ( P ) gives I 1 ( P [ 2 : ] , P [ : − 1 ] ) \mathcal{I}_1(P[2:], P[:-1]) I 1 ( P [ 2 : ] , P [ : − 1 ]) : after its first zero the latter machine has the same state and remaining tapes as the former after its first two zeros. All even A k A_k A k , k ≥ 4 k \ge4 k ≥ 4 , begin with at least two zeros. Also S + ( 0 N ) = I 0 ( 00 N 1 , 0 N ) S_+(0N) = \mathcal{I}_0(00N1, 0N) S + ( 0 N ) = I 0 ( 00 N 1 , 0 N ) . Induction proves (83) from the cited word laws.
Equation (83) identifies the inherited elementary excursions exactly. The exact-fit interleaving, tape counters, height additivity, and parked-head mechanism are likewise tools from Cloitre’s work [3 ] . The structural result here is the full orbit U p , k = ( A k A k + 1 ) p − 1 A k + 2 U_{p,k} = (A_kA_{k+1})^{p-1}A_{k+2} U p , k = ( A k A k + 1 ) p − 1 A k + 2 together with the parameter-dependent clock s p , k s_{p,k} s p , k and core reconstruction in § 3 . The proof checks the prescribed nested recurrence at every index. This does not follow merely from the presence of the same elementary excursions in the original model.
The analytic method also has a specific antecedent. Uniform profiles for the delayed perturbation were proved using nonlinear averaging and smooth comparison functions [8 ] . Here Lemma 4.2 supplies an exact shifted identity for the alternating maps of lengths 2 L + 2 2L + 2 2 L + 2 and 2 L − 2 2L - 2 2 L − 2 , and Lemma 4.6 proves a uniform comparison through their boundary cases. The resulting Gaussian limit, combined with the new block placement, gives every profile (44) and its sharp constant Λ p \Lambda_p Λ p . The four-piece profile (A.7) is the specialization at p = 2 p=2 p = 2 . The exact finite zeros and crossings in Theorem 6.3 and the exceptional case in Theorem A.5 require the separate low-height analysis and are not consequences of uniform convergence alone.
For p = 2 p=2 p = 2 , the pure dyadic frequency histogram in Theorem A.8 is exactly the same shifted-valuation multiset as in the original perturbation’s frequency law [6 ] , using each model’s own value-index convention. This does not identify their order: the Q 2 \mathbb{Q}_2 Q 2 block u = 4 , 5 , 6 , 7 u=4,5,6,7 u = 4 , 5 , 6 , 7 has frequencies ( 3 , 4 , 5 , 3 ) (3,4,5,3) ( 3 , 4 , 5 , 3 ) , whereas the original s = 4 , 5 , 6 , 7 s=4,5,6,7 s = 4 , 5 , 6 , 7 block, indexed by values 2 s − 1 2s-1 2 s − 1 , has frequencies ( 3 , 3 , 5 , 4 ) (3,3,5,4) ( 3 , 3 , 5 , 4 ) . The exact equality of histograms is therefore compatible with different ordered frequency words and different arch arrangements. The ordered factorization (62) , specialized in (A.20), retains the boundary corrections and the exact cuts through the palindromic tails. It proves the valuation histogram for Q 2 \mathbb{Q}_2 Q 2 without transferring it from the original model. For every p > 2 p>2 p > 2 , Theorem 7.5 shows explicitly how the upper finite histogram differs, despite the common limiting law.
Finally, logarithmic summatory bias and periodic linear terms already occur for the original perturbation [7 ] . § 8 supplies the exact telescoping identity for every clock s p , k s_{p,k} s p , k , the explicit function Ψ p \Psi_p Ψ p , and the parity-dependent height remainder (82) . These formulas distinguish the two models even where their frequency histograms agree.
Reproducibility and further questions
The reproducibility archive [12 ] accompanies the full family, including the three-arch specialization. It contains independent direct and word-based generators, the exact formulas, machine-readable audit reports, and the data and scripts for all figures. The principal family implementation is family.py; audit_family.py regenerates report_family_verification.json. The earlier three-arch verification programs and reports are retained with their own documentation. The archive’s audit guide records each program’s scope, parameter ranges, tested endpoints, and report provenance, rather than repeating the full program catalogue here.
The family report compares every term of the two constructions for 23 parameter choices: p = 2 , … , 9 p=2,\ldots,9 p = 2 , … , 9 through 2 23 2^{23} 2 23 terms each, and 15 additional parameters through 2 19 2^{19} 2 19 terms each. It checks the word factorization, range and two-step bounds, complete natural and pure dyadic frequency blocks, extreme locations, and every even summatory cutoff in those runs. Transition tables are checked only on complete blocks that lie in their stated theorem range. The report explicitly distinguishes larger parameters whose sufficient transition threshold lies beyond the finite run. The low-height and elementary Gaussian identities have separate word-level audits. The proofs, not the finite checks, establish the assertions for arbitrary indices and parameters; sampled figure errors are numerical diagnostics, not uniform bounds.
An effective rate of convergence to the elementary Gaussian profile remains to be determined. A second-order interior expansion would clarify the visible finite-level differences. The fixed-p p p results do not give an expansion uniform in a parameter growing with n n n . Nor do they classify all seeds producing finite signed concatenations: the theorem concerns the explicit repeated-pair family. Its common geometric frequency limit and different finite upper tails show why a histogram alone cannot recover the underlying ordered dynamics.
The three-arch member Q 2 Q_2 Q 2
This appendix records the explicit formulas and finite examples for p = 2 p=2 p = 2 . Only here we abbreviate Q 2 Q_2 Q 2 , F 2 F_2 F 2 , G 2 G_2 G 2 , U 2 , k U_{2,k} U 2 , k , L 2 , k L_{2,k} L 2 , k , a 2 , k a_{2,k} a 2 , k , d 2 , k d_{2,k} d 2 , k , s 2 , k s_{2,k} s 2 , k by Q Q Q , F F F , G G G , U k U_k U k , L k L_k L k , a k a_k a k , d k d_k d k , s k s_k s k , and put p k = L k / 2 p_k=L_k/2 p k = L k /2 . All general inputs and their proofs appear in the main text.
Initial block and three-word organization
( Q ( 1 ) , … , Q ( 7 ) ) = ( 1 , 1 , 3 , 3 , 3 , 3 , 5 ) , Q ( n ) = Q ( n − Q ( n − 1 ) ) + Q ( n − Q ( n − 2 ) ) − ( − 1 ) n ( n ≥ 8 ) . (84) \begin{aligned}
(Q(1),\ldots,Q(7))&=(1,1,3,3,3,3,5),\\
Q(n)&=Q\left(n-Q(n-1)\right)+Q\left(n-Q(n-2)\right)-(-1)^n\qquad(n\ge8). \tag*{(84)}
\end{aligned} ( Q ( 1 ) , … , Q ( 7 )) Q ( n ) = ( 1 , 1 , 3 , 3 , 3 , 3 , 5 ) , = Q ( n − Q ( n − 1 ) ) + Q ( n − Q ( n − 2 ) ) − ( − 1 ) n ( n ≥ 8 ) . (84)
The first terms are
1 , 1 , 3 , 3 , 3 , 3 , 5 , 5 , 7 , 5 , 7 , 7 , 7 , 9 , 9 , 9 , 11 , 11 , 11 , 13 , … 1,1,3,3,3,3,5,5,7,5,7,7,7,9,9,9,11,11,11,13,\ldots 1 , 1 , 3 , 3 , 3 , 3 , 5 , 5 , 7 , 5 , 7 , 7 , 7 , 9 , 9 , 9 , 11 , 11 , 11 , 13 , … .
Theorem 1.1 and Corollary 5.2 give
1 ≤ Q ( n ) ≤ n , Q ( n + 2 ) − Q ( n ) ∈ { 0 , 2 } , (85) 1\le Q(n)\le n,\qquad Q(n+2)-Q(n)\in\{0,2\}, \tag*{(85)} 1 ≤ Q ( n ) ≤ n , Q ( n + 2 ) − Q ( n ) ∈ { 0 , 2 } , (85)
Q ( n ) = n / 2 + O ( n / log n ) , (86) Q(n)=n/2+O\left(n/\sqrt{\log n}\right), \tag*{(86)} Q ( n ) = n /2 + O ( n / log n ) , (86)
with a sharp error order. Every positive odd value is assumed finitely often. Here the skeleton is
a k = 7 ⋅ 2 k − 3 − ( − 1 ) k 6 , d k = ⌊ k − 1 2 ⌋ , s k = 2 a k − d k . (87) a_k=\frac{7\cdot2^k-3-(-1)^k}{6},\qquad d_k=\left\lfloor\frac{k-1}{2}\right\rfloor,\qquad s_k=2a_k-d_k. \tag*{(87)} a k = 6 7 ⋅ 2 k − 3 − ( − 1 ) k , d k = ⌊ 2 k − 1 ⌋ , s k = 2 a k − d k . (87)
The first boundaries are 4 , 8 , 17 , 35 , 72 , 146 , 295 4,8,17,35,72,146,295 4 , 8 , 17 , 35 , 72 , 146 , 295 . The specialized core formulas (13) –(3.3) and reconstruction (14) will be used throughout.
Figure 8. The directly computed ratio errors, separated by index parity, through n = 2 24 n=2^{24} n = 2 24 . The horizontal axis is logarithmic. Several distinct excursions occur during each unit interval of this axis; the alternating sign convention is made explicit in Theorem A.2 .
Theorem A.1 (Exact three-word decomposition). For every k ≥ 2 k \ge2 k ≥ 2 ,
U k = A k A ‾ k + 1 A k + 2 . (88) U_k=A_k\overline{A}_{k+1}A_{k+2}. \tag*{(88)} U k = A k A k + 1 A k + 2 . (88) Consequently h U k h_{U_k} h U k vanishes exactly at the four integer positions
0 , ℓ k , ℓ k + ℓ k + 1 = 2 k , L k . (89) 0,\qquad\ell_k,\qquad\ell_k+\ell_{k+1}=2^k,\qquad L_k. \tag*{(89)} 0 , ℓ k , ℓ k + ℓ k + 1 = 2 k , L k . (89) It is positive, negative, and positive in the three open subintervals. The three lengths have asymptotic ratio 1 : 2 : 4 1:2:4 1 : 2 : 4 .
Proof. Specialize (4) at p = 2 p=2 p = 2 and use the primitivity of each A k A_k A k and ℓ k + ℓ k + 1 = 2 k \ell_k+\ell_{k+1}=2^k ℓ k + ℓ k + 1 = 2 k . □
Figure 9. The three factors of U 10 U_{10} U 10 displayed separately. Their normalized joining positions tend to 1 / 7 1/7 1/7 and 3 / 7 3/7 3/7 . Each elementary excursion is exactly symmetric, although the whole signed concatenation is not symmetric.
The explicit four-piece profile and envelope
For 1 ≤ t ≤ 2 1 \le t \le2 1 ≤ t ≤ 2 , define
P ( t ) = { 1 6 t J ( 3 t − 5 / 2 ) , 1 ≤ t ≤ 7 / 6 , − 1 12 t J ( 6 t − 7 ) , 7 / 6 ≤ t ≤ 4 / 3 , 1 6 t J ( 3 t − 4 ) , 4 / 3 ≤ t ≤ 5 / 3 , − 1 3 t J ( ( 3 t − 5 ) / 2 ) , 5 / 3 ≤ t ≤ 2. (90) \mathcal{P}(t)=
\begin{cases}
\frac{1}{6t}J(3t-5/2), & 1 \le t \le7/6,\\
-\frac{1}{12t}J(6t-7), & 7/6 \le t \le4/3,\\
\frac{1}{6t}J(3t-4), & 4/3 \le t \le5/3,\\
-\frac{1}{3t}J((3t-5)/2), & 5/3 \le t \le2.
\end{cases} \tag*{(90)} P ( t ) = ⎩ ⎨ ⎧ 6 t 1 J ( 3 t − 5/2 ) , − 12 t 1 J ( 6 t − 7 ) , 6 t 1 J ( 3 t − 4 ) , − 3 t 1 J (( 3 t − 5 ) /2 ) , 1 ≤ t ≤ 7/6 , 7/6 ≤ t ≤ 4/3 , 4/3 ≤ t ≤ 5/3 , 5/3 ≤ t ≤ 2. (90)
The formulas agree at each joining point. We use the parity sampling convention from § 5 .
Theorem A.2 (Standard dyadic profile). For each r ∈ { 0 , 1 } r \in\{0,1\} r ∈ { 0 , 1 } ,
sup 1 ≤ t ≤ 2 ∣ ( − 1 ) j + r j ( Q ( N j , r ( t ) ) N j , r ( t ) − 1 2 ) − P ( t ) ∣ ⟶ 0. (91) \sup_{1\le t\le2}\left|(-1)^{j+r}\sqrt{j}\left(\frac{Q(N_{j,r}(t))}{N_{j,r}(t)}-\frac{1}{2}\right)-\mathcal{P}(t)\right|\longrightarrow0. \tag*{(91)} 1 ≤ t ≤ 2 sup ( − 1 ) j + r j ( N j , r ( t ) Q ( N j , r ( t )) − 2 1 ) − P ( t ) ⟶ 0. (91)
The limiting profile has precisely the three zeros
7 6 , 4 3 , 5 3 , (92) \frac{7}{6}, \quad\frac{4}{3}, \quad\frac{5}{3}, \tag*{(92)} 6 7 , 3 4 , 3 5 , (92)
and signs + + + , − - − , + + + , − - − on the four complementary intervals. For each parity, all finite-level zeros and sign changes are confined to neighbourhoods of these three positions whose normalized widths tend to zero. Each neighborhood contains a sign change for all sufficiently large levels.
Proof. The core formulas and the unit-step bounds imply, uniformly in a macro block and with n = 2 m n=2m n = 2 m or 2 m − 1 2m-1 2 m − 1 ,
Q ( n ) n − 1 2 = ( − 1 ) k + r + 1 2 m h U k ( m − s k ) + O ( k / 2 k ) , (93) \frac{Q(n)}{n}-\frac{1}{2}=\frac{(-1)^{k+r+1}}{2m}h_{U_k}(m-s_k)+O(k/2^k), \tag*{(93)} n Q ( n ) − 2 1 = 2 m ( − 1 ) k + r + 1 h U k ( m − s k ) + O ( k / 2 k ) , (93)
where r = n m o d 2 r=n\bmod2 r = n mod 2 . On even macro levels the shifted bit in G G G adds only a bounded error; using n = 2 m − 1 n=2m-1 n = 2 m − 1 rather than 2 m 2m 2 m does the same.
The natural macro boundaries satisfy 2 s k = ( 14 / 3 ) 2 k + O ( k ) 2s_k=(14/3)2^k+O(k) 2 s k = ( 14/3 ) 2 k + O ( k ) . The factorization (A.5) gives the following four elementary arcs intersecting a standard block. The endpoints in this table are limiting positions in the coordinate t = n / 2 j t=n/2^j t = n / 2 j .
Table 7.
Signs include the compensation ( − 1 ) j + r (-1)^{j+r} ( − 1 ) j + r . An elementary arc of limiting horizontal width w w w , starting at b b b , contributes ± w J ( ( t − b ) / w ) / ( 2 t ) \pm wJ((t-b)/w)/(2t) ± w J (( t − b ) / w ) / ( 2 t ) by Theorem 4.1 and (A.10). This is precisely (A.7). All actual boundaries differ from their tabulated positions by O ( j 2 − j ) O(j2^{-j}) O ( j 2 − j ) . Uniform elementary convergence, J ( 0 ) = J ( 1 ) = 0 J(0)=J(1)=0 J ( 0 ) = J ( 1 ) = 0 , and the O ( j / 2 j ) O(j/2^j) O ( j / 2 j ) reconstruction error give uniform convergence through those boundary neighborhoods as well.
Strict positivity of J J J in ( 0 , 1 ) (0,1) ( 0 , 1 ) proves the sign and zero statements. Uniform convergence excludes sign changes on compact subintervals away from the three limiting zeros. Opposite signs on either side of each zero guarantee at least one change nearby. This does not assert an exactly three-crossing count at a finite level. □ \square □
Remark A.3 (Three transitions, not a factor-three renormalization). The evolution doubles the elementary lengths at each level, up to bounded corrections. The three transition points arise from concatenating three different dyadic generations. They do not describe a triadic scaling law.
Theorem A.4 (Sharp relative-error envelope). Let b ∗ > 0 b_\ast>0 b ∗ > 0 be the unique positive solution of
b ∗ ( 5 2 + Φ ( − b ∗ ) ) = φ ( b ∗ ) . (94) b_\ast\left(\frac{5}{2}+\Phi(-b_\ast)\right)=\varphi(b_\ast). \tag*{(94)} b ∗ ( 2 5 + Φ ( − b ∗ ) ) = φ ( b ∗ ) . (94) Then
lim sup n → ∞ log 2 n ∣ Q ( n ) n − 1 2 ∣ = Λ M : = b ∗ 2 = 0.067088003576 … (95) \limsup_{n\to\infty}\sqrt{\log_2 n}\left|\frac{Q(n)}{n}-\frac{1}{2}\right|=\Lambda_M:=\frac{b_\ast}{2}=0.067088003576\ldots \tag*{(95)} n → ∞ lim sup log 2 n n Q ( n ) − 2 1 = Λ M := 2 b ∗ = 0.067088003576 … (95) The corresponding signed limsup and liminf are Λ M \Lambda_M Λ M and − Λ M -\Lambda_M − Λ M .
Figure 10. Even-index profiles on three standard dyadic blocks and the explicit limit (A.7). Only the prescribed sign and j \sqrt{j} j normalization are applied. In particular, the three vertical reference lines have not been fitted to the data.
Proof. In one complete macro block, the start position of each elementary arc divided by its own length tends respectively to 7, 4, and 5 / 2 5/2 5/2 . Equation (A.10) and Theorem 4.1 therefore reduce the envelope to the largest of
max 0 ≤ x ≤ 1 J ( x ) 2 ( α + x ) , α ∈ { 7 , 4 , 5 / 2 } . \max_{0\le x\le1}\frac{J(x)}{2(\alpha+x)}, \qquad\alpha\in\{7,4,5/2\}. 0 ≤ x ≤ 1 max 2 ( α + x ) J ( x ) , α ∈ { 7 , 4 , 5/2 } .
The expression decreases strictly with α \alpha α , so the third arc wins. The derivative numerator ( α + x ) J ′ ( x ) − J ( x ) (\alpha+x)J'(x)-J(x) ( α + x ) J ′ ( x ) − J ( x ) decreases strictly, with derivative ( α + x ) J ′ ′ ( x ) < 0 (\alpha+x)J''(x)<0 ( α + x ) J ′′ ( x ) < 0 , and crosses zero once. Writing x ∗ = Φ ( − b ∗ ) x_*=\Phi(-b_*) x ∗ = Φ ( − b ∗ ) gives (A.11); at that point the maximum equals b ∗ / 2 b_*/2 b ∗ /2 . The left side minus the right side of (A.11) has derivative 5 / 2 + Φ ( − b ) > 0 5/2+\Phi(-b)>0 5/2 + Φ ( − b ) > 0 , is negative at zero, and eventually positive. This proves uniqueness. Opposite parity signs give both signed extremes. Numerically,
x ∗ = 0.446631698928 … , 5 / 3 + ( 2 / 3 ) x ∗ = 1.964421132618 … . x_* = 0.446631698928\ldots,\qquad5/3+(2/3)x_* = 1.964421132618\ldots. x ∗ = 0.446631698928 … , 5/3 + ( 2/3 ) x ∗ = 1.964421132618 … .
The second number is the maximizing location on the last arc in a standard block. Finally log 2 n = j + O ( 1 ) \log_2 n=j+O(1) log 2 n = j + O ( 1 ) on that block, so its square root may replace j \sqrt{j} j in the limiting envelope.
Equations (A.8) and (A.12) give the explicit three-arch specialization of the general profile and envelope theorems. In particular, the error cannot be improved to o ( n / log n ) o(n/\sqrt{\log n}) o ( n / log n ) .
All finite zeros, tangencies, and crossings
Theorem A.5 (Every finite zero and every odd-parity crossing). For a standard block 2 j ≤ n < 2 j + 1 2^j\le n<2^{j+1} 2 j ≤ n < 2 j + 1 , j ≥ 10 j\ge10 j ≥ 10 , put
c j , 1 = 7 6 2 j , c j , 2 = 4 3 2 j , c j , 3 = 5 3 2 j . c_{j,1}=\frac{7}{6}2^j,\qquad c_{j,2}=\frac{4}{3}2^j,\qquad c_{j,3}=\frac{5}{3}2^j. c j , 1 = 6 7 2 j , c j , 2 = 3 4 2 j , c j , 3 = 3 5 2 j .
All solutions of Q ( n ) = n / 2 Q(n)=n/2 Q ( n ) = n /2 in this block are the even integers c j , i + δ c_{j,i}+\delta c j , i + δ , with offsets in the following table:
In particular, there are exactly four zeros when j j j is even and six when j j j is odd. No odd index can be an exact zero.
On the odd subsequence, there are exactly three sign changes of Q ( n ) − n / 2 Q(n)-n/2 Q ( n ) − n /2 . They occur between n n n and n + 2 n+2 n + 2 , where the left endpoint is n = c j , i + η j , i n=c_{j,i}+\eta_{j,i} n = c j , i + η j , i and
Every displayed index is an integer of its stated parity. On the even subsequence there are also exactly three sign changes when zeros are deleted before counting changes; some of its additional zeros are tangencies rather than sign changes.
Proof. Write m = s k + t m=s_k+t m = s k + t , d = d k d=d_k d = d k , and h = h U k h=h_{U_k} h = h U k . The core reconstruction gives the exact identities
Q ( 2 m ) − m = { d + 1 + h ( t ) , k odd , d + 2 − h ( t + 1 ) , k even . (96) Q(2m)-m=
\begin{cases}
d+1+h(t), & k\text{ odd},\\
d+2-h(t+1), & k\text{ even}.
\end{cases} \tag*{(96)} Q ( 2 m ) − m = { d + 1 + h ( t ) , d + 2 − h ( t + 1 ) , k odd , k even . (96)
Q ( 2 m − 1 ) − ( 2 m − 1 ) / 2 = { d + 3 / 2 − h ( t ) , k odd , d + 3 / 2 + h ( t ) , k even . (97) Q(2m-1)-(2m-1)/2=
\begin{cases}
d+3/2-h(t), & k\text{ odd},\\
d+3/2+h(t), & k\text{ even}.
\end{cases} \tag*{(97)} Q ( 2 m − 1 ) − ( 2 m − 1 ) /2 = { d + 3/2 − h ( t ) , d + 3/2 + h ( t ) , k odd , k even . (97)
For the even-level formula use 2 U k [ t ] = 1 + h ( t ) − h ( t + 1 ) 2U_k[t]=1+h(t)-h(t+1) 2 U k [ t ] = 1 + h ( t ) − h ( t + 1 ) . We assign a common endpoint to the block on its right; the formulas agree there. An odd index cannot be a zero, since Q ( n ) Q(n) Q ( n ) is integral and n / 2 n/2 n /2 is then a half-integer.
For an elementary word with initial run length λ \lambda λ , the low-height lemma gives the following complete lists:
It also determines all crossings of the half-integer thresholds used below. The upward crossings of λ + 1 / 2 \lambda+1/2 λ + 1/2 and λ + 3 / 2 \lambda+3/2 λ + 3/2 have left endpoints λ + 2 \lambda+2 λ + 2 and λ + 3 \lambda+3 λ + 3 , respectively; their downward counterparts have left endpoints ℓ − λ − 3 \ell-\lambda-3 ℓ − λ − 3 and ℓ − λ − 4 \ell-\lambda-4 ℓ − λ − 4 . There are no other crossings of these thresholds: the middle heights are at least λ + 3 \lambda+3 λ + 3 .
Here is the full coordinate calculation. Set r = ⌊ ( j − 2 ) / 2 ⌋ r=\lfloor(j-2)/2\rfloor r = ⌊( j − 2 ) /2 ⌋ . The four elementary factors meeting the standard block have core-coordinate beginnings
In the next two tables, ( X , q ) (X,q) ( X , q ) denotes the core index m = B x + q m=Bx+q m = B x + q . The entries in the first table are exactly the even-index zeros, with n = 2 m n=2m n = 2 m :
caption:
:::
For odd indices, the entries below give the left member n = 2 m − 1 n=2m-1 n = 2 m − 1 of the pair n , n + 2 n,n+2 n , n + 2 across which the sign changes:
caption:
:::
To obtain these tables, on an odd macro level apply the even-error identity only to the negative middle excursion, at height d + 1 d+1 d + 1 . On an even macro level apply it to the positive first and third excursions, at height d + 2 d+2 d + 2 , remembering the shift from t t t to t + 1 t+1 t + 1 . For the odd-error identity, positive excursions on odd macro levels and negative excursions on even macro levels cross height d + 3 / 2 d+3/2 d + 3/2 . The complete low-height lists above then give every displayed entry.
Substituting the explicit formulas for s k s_k s k and ℓ k \ell_k ℓ k converts these core coordinates into the two offset tables in the statement. For example, for even j j j the first even zero is
2 ( s j − 2 + r + 2 ) = 7 6 2 j + 10 3 . 2(s_{j-2}+r+2)=\frac{7}{6}2^j+\frac{10}{3}. 2 ( s j − 2 + r + 2 ) = 6 7 2 j + 3 10 .
while the first odd crossing has left endpoint
2 ( s j − 3 + 2 j − 3 + ℓ j − 1 − r − 3 ) − 1 = 7 6 2 j − 2 j − 11 3 . 2(s_{j-3}+2^{j-3}+\ell_{j-1}-r-3)-1=\frac{7}{6}2^j-2^j-\frac{11}{3}. 2 ( s j − 3 + 2 j − 3 + ℓ j − 1 − r − 3 ) − 1 = 6 7 2 j − 2 j − 3 11 .
The exact same substitutions in the remaining explicitly listed coordinates give the other offsets without an asymptotic argument.
All elementary levels used here are at least eight when j ≥ 10 j\ge10 j ≥ 10 . The initial point of the standard block lies strictly inside factor I, and its final point strictly inside factor IV, beyond the short end intervals adjacent to the three intervening joins. These assertions follow directly from the displayed beginnings and lengths; the distance to the nearest excluded end is of order 2 j 2^j 2 j , whereas each relevant end interval has length at most j / 2 + 4 j/2+4 j /2 + 4 . For an explicit uniform separation, 2 j / 6 > 4 j + 16 2^j/6>4j+16 2 j /6 > 4 j + 16 holds at j = 10 j=10 j = 10 and persists on increasing j j j . Thus all the listed crossings lie in the standard block, the three groups are disjoint, and no omitted outer endpoint contributes a zero or crossing.
Finally, the local pattern g λ g_\lambda g λ distinguishes tangencies from genuine changes on the even subsequence. At height λ \lambda λ , the first hit λ \lambda λ is followed by a return to λ − 1 \lambda-1 λ − 1 , whereas the second hit λ + 2 \lambda+2 λ + 2 is followed by heights greater than λ \lambda λ ; reflection gives the other end. At height λ + 1 \lambda+1 λ + 1 there is a single transverse hit at each end. Consequently deleting the zeros leaves exactly one sign change near each of the three centers. The low-height lemma excludes any further one.
A worked example: the block 1024 ≤ n < 2048 1024\le n<2048 1024 ≤ n < 2048 . For j = 10 j=10 j = 10 , the three limiting centers are
c 10 , 1 = 3584 3 , c 10 , 2 = 4096 3 , c 10 , 3 = 5120 3 . c_{10,1}=\frac{3584}{3},\qquad c_{10,2}=\frac{4096}{3},\qquad c_{10,3}=\frac{5120}{3}. c 10 , 1 = 3 3584 , c 10 , 2 = 3 4096 , c 10 , 3 = 3 5120 .
The exact word coordinates retain the small offsets that these centers do not record. Here r = 4 r=4 r = 4 , d 7 = d 8 = 3 d_7=d_8=3 d 7 = d 8 = 3 , and
s 7 = 295 , s 8 = 593 , ℓ 8 = 86 , ℓ 9 = 170 , ℓ 10 = 342. s_7=295,\quad s_8=593,\quad\ell_8=86,\quad\ell_9=170,\quad\ell_{10}=342. s 7 = 295 , s 8 = 593 , ℓ 8 = 86 , ℓ 9 = 170 , ℓ 10 = 342.
Thus the four factors in the proof of Theorem A.5 start at core indices
B I = 423 , B I I = 593 , B I I I = 679 , B I V = 849. B_{\mathrm{I}}=423,\quad B_{\mathrm{II}}=593,\quad B_{\mathrm{III}}=679,\quad B_{\mathrm{IV}}=849. B I = 423 , B II = 593 , B III = 679 , B IV = 849.
They are respectively A 9 A_9 A 9 , A 8 A_8 A 8 , A ‾ 9 \overline{A}_9 A 9 , and A 10 A_{10} A 10 . Write E ( n ) = Q ( n ) − n / 2 E(n)=Q(n)-n/2 E ( n ) = Q ( n ) − n /2 .
On factors II and IV, the even-error formula is E ( 2 m ) = 5 − h U 8 ( m − s 8 + 1 ) E(2m)=5-h_{U_8}(m-s_8+1) E ( 2 m ) = 5 − h U 8 ( m − s 8 + 1 ) . In factor II it vanishes at local coordinates q = 6 , 78 q=6,78 q = 6 , 78 : the two prefix positions are q + 1 = 7 , 79 q+1=7,79 q + 1 = 7 , 79 , and
h A 8 ( 7 ) = h A 8 ( 86 − 7 ) = g 4 ( 7 ) = 5. h_{A_8}(7)=h_{A_8}(86-7)=g_4(7)=5. h A 8 ( 7 ) = h A 8 ( 86 − 7 ) = g 4 ( 7 ) = 5.
In factor IV it vanishes at q = 4 , 6 q=4,6 q = 4 , 6 , since
h A 10 ( 5 ) = g 5 ( 5 ) = 5 , h A 10 ( 7 ) = g 5 ( 7 ) = 5. h_{A_{10}}(5)=g_5(5)=5,\qquad h_{A_{10}}(7)=g_5(7)=5. h A 10 ( 5 ) = g 5 ( 5 ) = 5 , h A 10 ( 7 ) = g 5 ( 7 ) = 5.
The other end of factor IV is beyond this standard block. Factor I has E ( 2 m ) = 4 + h A 9 ( q ) > 0 E(2m)=4+h_{A_9}(q)>0 E ( 2 m ) = 4 + h A 9 ( q ) > 0 , and factor III has E ( 2 m ) = 5 + h A 9 ( q + 1 ) > 0 E(2m)=5+h_{A_9}(q+1)>0 E ( 2 m ) = 5 + h A 9 ( q + 1 ) > 0 . The low-height lemma therefore leaves exactly the following four zeros. The adjacent values distinguish a tangency from a genuine crossing:
Table 1.
For example, the first zero is 2 ( 593 + 6 ) = 1198 = c 10 , 1 + 10 / 3 2(593+6)=1198=c_{10,1}+10/3 2 ( 593 + 6 ) = 1198 = c 10 , 1 + 10/3 . The remaining offsets are − 70 / 3 -70/3 − 70/3 at c 10 , 2 c_{10,2} c 10 , 2 and − 2 / 3 , 10 / 3 -2/3,10/3 − 2/3 , 10/3 at c 10 , 3 c_{10,3} c 10 , 3 . In particular, the two zeros near the third center produce only one sign change after zeros are deleted.
For odd indices in factor I, the exact error is 9 / 2 − h A 9 ( q ) 9/2-h_{A_9}(q) 9/2 − h A 9 ( q ) . The reflected low heights at q = 163 , 164 q=163,164 q = 163 , 164 are 5, 4, so the crossing occurs between 2 ( 423 + 163 ) − 1 = 1171 2(423+163)-1=1171 2 ( 423 + 163 ) − 1 = 1171 and 1173. In factor III the exact error is again 9 / 2 − h A 9 ( q ) 9/2-h_{A_9}(q) 9/2 − h A 9 ( q ) , now because the factor is complemented and the macro level is even. The pairs of local coordinates (6, 7) and (163, 164) have heights (4, 5) and (5, 4), respectively. Thus
Table 2.
These are the three odd-parity crossings. The left-endpoint offsets are − 71 / 3 -71/3 − 71/3 , 11 / 3 11/3 11/3 , and − 71 / 3 -71/3 − 71/3 , respectively, as predicted by the theorem. The archive also checks every value through n = 2048 n=2048 n = 2048 by direct recursion and, independently, by word reconstruction; both calculations give the values in these tables.
Corollary A.6 (An optimal logarithmic transition window). All zeros and parity-separated sign transitions in the j j j -th standard block lie in the union of the intervals
∣ n − c j , i ∣ ≤ 2 j + 8 , i = 1 , 2 , 3 , j ≥ 10. (98) \lvert n-c_{j,i}\rvert\le2j+8,\qquad i=1,2,3,\quad j\ge10. \tag*{(98)} ∣ n − c j , i ∣ ≤ 2 j + 8 , i = 1 , 2 , 3 , j ≥ 10. (98) Thus their distance from the limiting positions in the coordinate n / 2 j n/2^j n / 2 j is O ( j 2 − j ) = O ( ( log n ) / n ) O(j2^{-j})=O((\log n)/n) O ( j 2 − j ) = O (( log n ) / n ) . This order cannot uniformly be replaced by o ( j 2 − j ) o(j2^{-j}) o ( j 2 − j ) , as the offsets − 2 j + O ( 1 ) -2j+O(1) − 2 j + O ( 1 ) in Theorem A.5 show.
Natural and pure dyadic frequency blocks
Write ν ( v ) = # { n ≥ 1 : Q ( n ) = v } \nu(v)=\#\{n\ge1: Q(n)=v\} ν ( v ) = # { n ≥ 1 : Q ( n ) = v } ; the subscript in ν 2 ( b ) \nu_2(b) ν 2 ( b ) below instead denotes the two-adic valuation. Put V k = { 2 u + 1 : a k ≤ u < a k + 1 } V_k=\{2u+1:a_k\le u<a_{k+1}\} V k = { 2 u + 1 : a k ≤ u < a k + 1 } and F k ( z ) = ∑ u = a k a k + 1 − 1 z ν ( 2 u + 1 ) F_k(z)=\sum_{u=a_k}^{a_{k+1}-1}z^{\nu(2u+1)} F k ( z ) = ∑ u = a k a k + 1 − 1 z ν ( 2 u + 1 ) .
Theorem A.7 (Complete-block multiplicity recursion). Every coefficient of F k F_k F k is determined by
F 1 ( z ) = z 3 + z 4 , F k + 1 ( z ) = z F k ( z ) + ( p k − ( − 1 ) k ) z 3 ( k ≥ 1 ) . (99) F_1(z)=z^3+z^4,\qquad F_{k+1}(z)=zF_k(z)+(p_k-(-1)^k)z^3\qquad(k\ge1). \tag*{(99)} F 1 ( z ) = z 3 + z 4 , F k + 1 ( z ) = z F k ( z ) + ( p k − ( − 1 ) k ) z 3 ( k ≥ 1 ) . (99) Consequently
F k ( z ) p k ⟶ G ( z ) = z 3 2 − z (100) \frac{F_k(z)}{p_k}\longrightarrow G(z)=\frac{z^3}{2-z} \tag*{(100)} p k F k ( z ) ⟶ G ( z ) = 2 − z z 3 (100) in coefficient ℓ 1 \ell^1 ℓ 1 norm with error O ( k 2 − k ) O(k2^{-k}) O ( k 2 − k ) . The limiting distribution has mean 4 and variance 2; the complete block means and variances converge to these values. For every k ≥ 1 k\ge1 k ≥ 1 ,
∑ v ∈ V k ν ( v ) = 4 p k − 3 + ( − 1 ) k 2 , (101) \sum_{v\in V_k}\nu(v)=4p_k-\frac{3+(-1)^k}{2}, \tag*{(101)} v ∈ V k ∑ ν ( v ) = 4 p k − 2 3 + ( − 1 ) k , (101) max v ∈ V k ν ( v ) = k + 3. (102) \max_{v\in V_k}\nu(v)=k+3. \tag*{(102)} v ∈ V k max ν ( v ) = k + 3. (102) In particular, the multiplicities are unbounded but are O ( log v ) O(\log v) O ( log v ) .
Proof. Specialize Theorem 7.4 at p = 2 p=2 p = 2 . Here the explicit first step also satisfies the same polynomial recursion: F 1 = z 3 + z 4 F_1=z^3+z^4 F 1 = z 3 + z 4 and F 2 = 3 z 3 + z 4 + z 5 F_2=3z^3+z^4+z^5 F 2 = 3 z 3 + z 4 + z 5 . All stated masses, degrees, and convergence estimates follow.
The ordered natural-block statement becomes
( ν ( 2 u + 1 ) ) u = a k a k + 1 − 1 = V k V k + 1 V k + 2 . (103) \left(\nu(2u+1)\right)_{u=a_k}^{a_{k+1}-1}=V_kV_{k+1}V_{k+2}. \tag*{(103)} ( ν ( 2 u + 1 ) ) u = a k a k + 1 − 1 = V k V k + 1 V k + 2 . (103)
There is no repeated-pair join and hence no tilde correction.
Theorem A.8 (Pure dyadic value blocks). For every j ≥ 1 j\ge1 j ≥ 1 , as multisets,
{ ν ( 2 u + 1 ) : 2 j ≤ u < 2 j + 1 } = { 3 + ν 2 ( b ) : 1 ≤ b ≤ 2 j } , (104) \{\nu(2u+1):2^j\le u<2^{j+1}\}=\{3+\nu_2(b):1\le b\le2^j\}, \tag*{(104)} { ν ( 2 u + 1 ) : 2 j ≤ u < 2 j + 1 } = { 3 + ν 2 ( b ) : 1 ≤ b ≤ 2 j } , (104) where ν 2 \nu_2 ν 2 is the exponent of two dividing a positive integer. Equivalently, the exact polynomial is
D j ( z ) : = ∑ u = 2 j 2 j + 1 − 1 z ν ( 2 u + 1 ) = ∑ h = 0 j − 1 2 j − h − 1 z h + 3 + z j + 3 . (105) D_j(z):=\sum_{u=2^j}^{2^{j+1}-1}z^{\nu(2u+1)}
=\sum_{h=0}^{j-1}2^{j-h-1}z^{h+3}+z^{j+3}. \tag*{(105)} D j ( z ) := u = 2 j ∑ 2 j + 1 − 1 z ν ( 2 u + 1 ) = h = 0 ∑ j − 1 2 j − h − 1 z h + 3 + z j + 3 . (105) More precisely, the ordered frequency word on this block is, for j ≥ 2 j\ge2 j ≥ 2 ,
rev ( R j + 1 ) V j V j + 1 ( j + 3 ) R j + 2 . (106) \operatorname{rev}(R_{j+1})V_jV_{j+1}(j+3)R_{j+2}. \tag*{(106)} rev ( R j + 1 ) V j V j + 1 ( j + 3 ) R j + 2 . (106)
Proof. For j ≥ 3 j\ge3 j ≥ 3 the lower cut 2 j 2^j 2 j lies in the last elementary frequency factor of the preceding macro block. That factor is V j + 1 V_{j+1} V j + 1 and starts at
b j = a j − 1 + q j − 1 + q j = 5 ⋅ 2 j − 3 + ( − 1 ) j 6 . b_j=a_{j-1}+q_{j-1}+q_j=\frac{5\cdot2^j-3+(-1)^j}{6}. b j = a j − 1 + q j − 1 + q j = 6 5 ⋅ 2 j − 3 + ( − 1 ) j .
Since
2 j = b j + q j + 1 + 1 2 , (107) 2^j=b_j+\frac{q_{j+1}+1}{2}, \tag*{(107)} 2 j = b j + 2 q j + 1 + 1 , (107)
its retained suffix is exactly rev ( R j + 1 ) \operatorname{rev}(R_{j+1}) rev ( R j + 1 ) . The next macro block contributes the whole words V j V_j V j and V j + 1 V_{j+1} V j + 1 . Applying (A.24) at the upper endpoint shows that the final retained prefix is ( j + 3 ) R j + 2 (j+3)R_{j+2} ( j + 3 ) R j + 2 . This proves (A.23); its j = 2 j=2 j = 2 instance is the direct word ( 3 , 4 , 5 , 3 ) (3,4,5,3) ( 3 , 4 , 5 , 3 ) .
The polynomial of R k R_k R k is ( B k ( z ) − z k + 1 ) / 2 (B_k(z)-z^{k+1})/2 ( B k ( z ) − z k + 1 ) /2 . Hence, for j ≥ 2 j\ge2 j ≥ 2 ,
2 D j = 2 B j + 3 B j + 1 + B j + 2 − z j + 2 + z j + 3 . (108) 2D_j=2B_j+3B_{j+1}+B_{j+2}-z^{j+2}+z^{j+3}. \tag*{(108)} 2 D j = 2 B j + 3 B j + 1 + B j + 2 − z j + 2 + z j + 3 . (108)
Write e = ( − 1 ) j e=(-1)^j e = ( − 1 ) j . From q j + 1 = 2 q j − e q_{j+1}=2q_j-e q j + 1 = 2 q j − e and q j + 2 = 4 q j − e q_{j+2}=4q_j-e q j + 2 = 4 q j − e , the non-shifted terms when advancing the three elementary polynomials sum to
( q j − e ) + 3 2 ( q j + 1 + e ) + 1 2 ( q j + 2 − e ) = 6 q j − 2 e = 2 j . (q_j-e)+\frac{3}{2}(q_{j+1}+e)+\frac{1}{2}(q_{j+2}-e)=6q_j-2e=2^j. ( q j − e ) + 2 3 ( q j + 1 + e ) + 2 1 ( q j + 2 − e ) = 6 q j − 2 e = 2 j .
The two displayed monomial corrections in (A.25) simply shift by z z z . We therefore obtain
D j + 1 ( z ) = z D j ( z ) + 2 j z 3 . (109) D_{j+1}(z)=zD_j(z)+2^jz^3. \tag*{(109)} D j + 1 ( z ) = z D j ( z ) + 2 j z 3 . (109)
The direct base D 1 = z 3 + z 4 D_1=z^3+z^4 D 1 = z 3 + z 4 also gives D 2 = 2 z 3 + z 4 + z 5 D_2=2z^3+z^4+z^5 D 2 = 2 z 3 + z 4 + z 5 by the same rule. Solving this scalar recursion proves (A.22) and therefore (A.21). No block-mass or hitting-time assumption is used in the proof.
The proof of Theorem A.8 depends on the locations of the cuts through the palindromic tails. The natural-block polynomial alone does not determine these cuts. The valuation law describes the multiset; it does not assert the pointwise formula ν ( 2 u + 1 ) = 3 + ν 2 ( u ) \nu(2u+1)=3+\nu_2(u) ν ( 2 u + 1 ) = 3 + ν 2 ( u ) .
Corollary A.9 (Exact moments, convergence rate, and cumulative count). Choose a value uniformly from { 2 u + 1 : 2 j ≤ u < 2 j + 1 } \{2u+1:2^j\le u<2^{j+1}\} { 2 u + 1 : 2 j ≤ u < 2 j + 1 } , j ≥ 1 j\ge1 j ≥ 1 , and let X j X_j X j be its total multiplicity in Q Q Q . Then
E X j = 4 − 2 − j , (110) \mathbb{E}X_j=4-2^{-j}, \tag*{(110)} E X j = 4 − 2 − j , (110) Var ( X j ) = 2 − ( 2 j + 1 ) 2 − j − 4 − j . (111) \operatorname{Var}(X_j)=2-(2j+1)2^{-j}-4^{-j}. \tag*{(111)} Var ( X j ) = 2 − ( 2 j + 1 ) 2 − j − 4 − j . (111) Its law has coefficient ℓ 1 \ell^1 ℓ 1 distance exactly 2 − j 2^{-j} 2 − j from G ( z ) = z 3 / ( 2 − z ) G(z)=z^3/(2-z) G ( z ) = z 3 / ( 2 − z ) , and total-variation distance exactly 2 − j − 1 2^{-j-1} 2 − j − 1 . Also
# { n ≥ 1 : Q ( n ) < 2 j + 1 } = 2 j + 2 − j − 1. (112) \#\{n\ge1:Q(n)<2^{j+1}\}=2^{j+2}-j-1. \tag*{(112)} # { n ≥ 1 : Q ( n ) < 2 j + 1 } = 2 j + 2 − j − 1. (112) This is a count over the whole infinite sequence, not a claim that the counted indices form an initial interval.
Proof. The distribution of X j − 3 X_j-3 X j − 3 is that of a geometric random variable with probabilities 2 − h − 1 2^{-h-1} 2 − h − 1 at h ≥ 0 h\ge0 h ≥ 0 , truncated by replacing every value at least j j j by j j j . Its first two moments, or differentiation of (A.22), give (A.27)–(A.28). At multiplicity j + 3 j+3 j + 3 there is an excess probability 2 − j − 1 2^{-j-1} 2 − j − 1 ; the removed tail has that same mass. This proves the two distances. The exact block mass is 4 ⋅ 2 j − 1 4\cdot2^j-1 4 ⋅ 2 j − 1 . Finally ν ( 1 ) = 2 \nu(1)=2 ν ( 1 ) = 2 and ν ( 3 ) = 4 \nu(3)=4 ν ( 3 ) = 4 ; summing those two exceptions and all blocks below 2 j 2^j 2 j proves (A.29).
Proposition A.10 (Locations of the two largest multiplicities). On 2 j ≤ u < 2 j + 1 2^j\le u<2^{j+1} 2 j ≤ u < 2 j + 1 , j ≥ 1 j\ge1 j ≥ 1 , the largest multiplicity j + 3 j+3 j + 3 occurs at the unique value index
u = ⌊ 5 ⋅ 2 j 3 ⌋ . (113) u=\left\lfloor\frac{5\cdot2^j}{3}\right\rfloor. \tag*{(113)} u = ⌊ 3 5 ⋅ 2 j ⌋ . (113) The second largest multiplicity j + 2 j+2 j + 2 occurs uniquely at u = ⌊ 4 ⋅ 2 j / 3 ⌋ u=\lfloor4\cdot2^j/3\rfloor u = ⌊ 4 ⋅ 2 j /3 ⌋ .
Proof. By Lemma 7.3 , the only entry k + 1 k+1 k + 1 in V k \mathbf{V}_k V k is its first, and none of its entries equals k k k . Thus in (A.23) the two largest entries are the first entry of V j + 1 \mathbf{V}_{j+1} V j + 1 and the displayed j + 3 j+3 j + 3 . Their positions in the macro block are
a j + q j = ⌊ 4 ⋅ 2 j 3 ⌋ , a j + q j + q j + 1 = ⌊ 5 ⋅ 2 j 3 ⌋ . a_j+q_j=\left\lfloor\frac{4\cdot2^j}{3}\right\rfloor,\qquad a_j+q_j+q_{j+1}=\left\lfloor\frac{5\cdot2^j}{3}\right\rfloor. a j + q j = ⌊ 3 4 ⋅ 2 j ⌋ , a j + q j + q j + 1 = ⌊ 3 5 ⋅ 2 j ⌋ .
This proves the claim for j ≥ 2 j\ge2 j ≥ 2 ; the block j = 1 j=1 j = 1 is immediate.
Figure 11. Ordered multiplicities in a pure dyadic value-index block. The histogram is exactly the shifted valuation law of Theorem A.8 , but the order is not the ruler order. The two marked locations are the exact maximizers specified in Proposition A.10 . Here the horizontal variable is a value index u u u , not the sequence index n n n , and j = 10 j=10 j = 10 . The labels at the two marked points give their multiplicities.
Exact summation in the three-arch case
The large, opposite-parity oscillations do not average to zero exactly. The symmetric core mode determines a smaller systematic drift. It also allows all complete macro blocks to be summed without evaluating their individual heights.
Let
S ( N ) = ∑ n = 1 N Q ( n ) , E ( N ) = S ( N ) − N ( N + 1 ) 4 . S(N)=\sum_{n=1}^{N}Q(n),\qquad\mathcal{E}(N)=S(N)-\frac{N(N+1)}{4}. S ( N ) = n = 1 ∑ N Q ( n ) , E ( N ) = S ( N ) − 4 N ( N + 1 ) .
The subtraction in E \mathcal{E} E is the exact sum of the comparison terms n / 2 n/2 n /2 .
Theorem A.11 (An exact telescoping formula). Let M ≥ 4 M\ge4 M ≥ 4 , and let K K K be the unique integer for which s K ≤ M < s K + 1 s_K\le M<s_{K+1} s K ≤ M < s K + 1 . Put T = M − s K + 1 T=M-s_K+1 T = M − s K + 1 . Then
E ( 2 M ) = ( K + 3 2 ) ( M + 1 ) − ∑ k = 1 K s k − 5 2 − d K − 1 { K e v e n } h U K ( T ) . (114) \mathcal{E}(2M)=\left(K+\frac{3}{2}\right)(M+1)-\sum_{k=1}^{K}s_k-\frac{5}{2}-d_K-\mathbf{1}_{\{K\ \mathrm{even}\}}h_{U_K}(T). \tag*{(114)} E ( 2 M ) = ( K + 2 3 ) ( M + 1 ) − k = 1 ∑ K s k − 2 5 − d K − 1 { K even } h U K ( T ) . (114)
The sum of the boundary positions is itself explicit:
∑ k = 1 K s k = 7 3 ( 2 K + 1 − 2 ) − K − ( − 1 ) K − 1 6 − ⌊ ( K − 1 ) 2 4 ⌋ . (115) \sum_{k=1}^{K} s_k = \frac{7}{3}(2^{K+1}-2)-K-\frac{(-1)^K-1}{6}-\left\lfloor\frac{(K-1)^2}{4}\right\rfloor. \tag*{(115)} k = 1 ∑ K s k = 3 7 ( 2 K + 1 − 2 ) − K − 6 ( − 1 ) K − 1 − ⌊ 4 ( K − 1 ) 2 ⌋ . (115)
Thus only one height of the final, incomplete word is needed beyond powers, floors, and elementary arithmetic. When K K K is odd, even that height term is absent.
Proof. For m = s k + t m=s_k+t m = s k + t the exact symmetric-mode formula gives the contribution of the pair 2 m − 1 , 2 m 2m-1,2m 2 m − 1 , 2 m to E \mathcal{E} E as
2 ( F ( m ) + G ( m ) − m ) + 5 2 = { k + 3 / 2 , k odd , k + 3 / 2 − ( h U k ( t + 1 ) − h U k ( t ) ) , k even . 2\bigl(F(m)+G(m)-m\bigr)+\frac{5}{2}=
\begin{cases}
k+3/2, & k\ \text{odd},\\
k+3/2-\bigl(h_{U_k}(t+1)-h_{U_k}(t)\bigr), & k\ \text{even}.
\end{cases} 2 ( F ( m ) + G ( m ) − m ) + 2 5 = { k + 3/2 , k + 3/2 − ( h U k ( t + 1 ) − h U k ( t ) ) , k odd , k even .
The first three pairs contribute 7 / 2 7/2 7/2 in total. Assign each macro block the half-open index interval [ s k , s k + 1 ) [s_k,s_{k+1}) [ s k , s k + 1 ) . A completed odd block therefore contributes ( k + 3 / 2 ) ( s k + 1 − s k ) (k+3/2)(s_{k+1}-s_k) ( k + 3/2 ) ( s k + 1 − s k ) . For an even block, its length is L k − 1 L_k-1 L k − 1 and h U k ( L k − 1 ) = 1 h_{U_k}(L_k-1)=1 h U k ( L k − 1 ) = 1 , because its final bit is one. Its contribution is ( k + 3 / 2 ) ( s k + 1 − s k ) − 1 (k+3/2)(s_{k+1}-s_k)-1 ( k + 3/2 ) ( s k + 1 − s k ) − 1 . The unfinished block contributes ( K + 3 / 2 ) T (K+3/2)T ( K + 3/2 ) T minus the height term in (A.31). There are d K d_K d K completed even blocks. Telescoping the terms involving s k + 1 − s k s_{k+1}-s_k s k + 1 − s k , with s 1 = 4 s_1=4 s 1 = 4 , proves (A.31). Finally substitute (A.4) and use
∑ k = 1 K ( − 1 ) k = ( − 1 ) K − 1 2 , ∑ k = 1 K ⌊ k − 1 2 ⌋ = ⌊ ( K − 1 ) 2 4 ⌋ \sum_{k=1}^{K}(-1)^k=\frac{(-1)^K-1}{2},
\qquad
\sum_{k=1}^{K}\left\lfloor\frac{k-1}{2}\right\rfloor=\left\lfloor\frac{(K-1)^2}{4}\right\rfloor k = 1 ∑ K ( − 1 ) k = 2 ( − 1 ) K − 1 , k = 1 ∑ K ⌊ 2 k − 1 ⌋ = ⌊ 4 ( K − 1 ) 2 ⌋
to obtain (A.32).
Theorem A.12 (A periodic linear term in the summatory asymptotic). Put C = 14 / 3 C=14/3 C = 14/3 , and let Ψ \Psi Ψ be the continuous one-periodic function whose values on 0 ≤ θ ≤ 1 0\leq\theta\leq1 0 ≤ θ ≤ 1 are
Ψ ( θ ) = 1 − 1 2 log 2 C − θ 2 − 2 − θ . (116) \Psi(\theta)=1-\frac{1}{2}\log_2 C-\frac{\theta}{2}-2^{-\theta}. \tag*{(116)} Ψ ( θ ) = 1 − 2 1 log 2 C − 2 θ − 2 − θ . (116) Its two endpoint values agree. As N → ∞ N\to\infty N → ∞ through all integers,
S ( N ) = N 2 4 + N 2 log 2 N + N Ψ ( { log 2 ( N / C ) } ) + O ( N log N ) . (117) S(N)=\frac{N^2}{4}+\frac{N}{2}\log_2N+N\Psi\bigl(\{\log_2(N/C)\}\bigr)+O\left(\frac{N}{\sqrt{\log N}}\right). \tag*{(117)} S ( N ) = 4 N 2 + 2 N log 2 N + N Ψ ( { log 2 ( N / C )} ) + O ( log N N ) . (117) Here { x } = x − ⌊ x ⌋ \{x\}=x-\lfloor x\rfloor { x } = x − ⌊ x ⌋ denotes the fractional part. In particular, the cancellation of the large parity oscillations leaves a positive bias of order N log N N\log N N log N , with leading coefficient 1 / 2 1/2 1/2 when the logarithm has base two.
Proof. First let N = 2 M N=2M N = 2 M . By the three-word factorization and the elementary height bound, uniformly on the K K K -th macro block, ∣ h U K ∣ = O ( 2 K / K ) |h_{U_K}|=O(2^K/\sqrt{K}) ∣ h U K ∣ = O ( 2 K / K ) . Equations (A.31)–(A.32) yield
E ( 2 M ) = M ( K + 3 / 2 ) − 7 3 2 K + 1 + O ( K 2 + 2 K K ) . (118) \mathcal{E}(2M)=M(K+3/2)-\frac{7}{3}2^{K+1}+O\left(K^2+\frac{2^K}{\sqrt{K}}\right). \tag*{(118)} E ( 2 M ) = M ( K + 3/2 ) − 3 7 2 K + 1 + O ( K 2 + K 2 K ) . (118)
Put b k = ( 7 / 3 ) 2 k b_k=(7/3)2^k b k = ( 7/3 ) 2 k . The exact boundary formula is
s k = b k − e k , e k = 1 + ( − 1 ) k 3 + ⌊ k − 1 2 ⌋ > 0. s_k=b_k-e_k,\qquad e_k=1+\frac{(-1)^k}{3}+\left\lfloor\frac{k-1}{2}\right\rfloor>0. s k = b k − e k , e k = 1 + 3 ( − 1 ) k + ⌊ 2 k − 1 ⌋ > 0.
Let K 0 = ⌊ log 2 ( M / ( 7 / 3 ) ) ⌋ K_0=\left\lfloor\log_2(M/(7/3))\right\rfloor K 0 = ⌊ log 2 ( M / ( 7/3 )) ⌋ . For all sufficiently large M M M , either K = K 0 K=K_0 K = K 0 or K = K 0 + 1 K=K_0+1 K = K 0 + 1 : the first inequality follows from s K 0 < b K 0 ≤ M s_{K_0}<b_{K_0}\le M s K 0 < b K 0 ≤ M , and s K 0 + 2 > b K 0 + 1 > M s_{K_0+2}>b_{K_0+1}>M s K 0 + 2 > b K 0 + 1 > M gives the second. If K = K 0 + 1 K=K_0+1 K = K 0 + 1 , then
b K − e K ≤ M < b K , ∣ M − b K ∣ ≤ e K = O ( K ) . b_K-e_K\le M<b_K,\qquad|M-b_K|\le e_K=O(K). b K − e K ≤ M < b K , ∣ M − b K ∣ ≤ e K = O ( K ) .
The difference between the main terms of (A.35) at K K K and at K 0 K_0 K 0 is exactly M − b K M-b_K M − b K . Replacing K K K by K 0 K_0 K 0 therefore costs only O ( K ) O(K) O ( K ) , uniformly across the short intervals between the actual and ideal dyadic boundaries.
Set θ = { log 2 ( N / C ) } \theta=\{\log_2(N/C)\} θ = { log 2 ( N / C )} , so K 0 = log 2 N − log 2 C − θ K_0=\log_2N-\log_2C-\theta K 0 = log 2 N − log 2 C − θ and ( 7 / 3 ) 2 K 0 + 1 = N 2 − θ (7/3)2^{K_0+1}=N2^{-\theta} ( 7/3 ) 2 K 0 + 1 = N 2 − θ . Substituting these in (A.35) and adding N ( N + 1 ) / 4 N(N+1)/4 N ( N + 1 ) /4 gives (A.34). The formula (A.33) has equal values at zero and one, so its periodic extension is continuous and Lipschitz. For an odd N N N add its last term to the formula at N − 1 N-1 N − 1 and use Q ( N ) = N / 2 + O ( N / log N ) Q(N)=N/2+O(N/\sqrt{\log N}) Q ( N ) = N /2 + O ( N / log N ) . The smooth main terms change by N / 2 + O ( log N ) N/2+O(\log N) N /2 + O ( log N ) , and the periodic term by O ( 1 ) O(1) O ( 1 ) . This proves the same estimate for odd N N N .
Remark A.13 (The finite-level remainder and macro-level parity). For even N = 2 M N=2M N = 2 M , retain the actual level K K K and T = M − s K + 1 T=M-s_K+1 T = M − s K + 1 from Theorem A.11 , and put θ = { log 2 ( N / ( 14 / 3 ) ) } \theta=\{\log_2(N/(14/3))\} θ = { log 2 ( N / ( 14/3 ))} . The same calculation, with the final height kept instead of bounded, gives the uniform refinement
S ( N ) − N 2 / 4 − ( N / 2 ) log 2 N N = Ψ ( θ ) − 1 { K e v e n } h U K ( T ) N + O ( ( log N ) 2 N ) . (119) \frac{S(N)-N^2/4-(N/2)\log_2N}{N}
=\Psi(\theta)-\mathbf{1}_{\{K\ {\rm even}\}}\frac{h_{U_K}(T)}{N}+O\left(\frac{(\log N)^2}{N}\right). \tag*{(119)} N S ( N ) − N 2 /4 − ( N /2 ) log 2 N = Ψ ( θ ) − 1 { K even } N h U K ( T ) + O ( N ( log N ) 2 ) . (119)
Thus odd macro levels have a remainder O ( ( log N ) 2 ) O((\log N)^2) O (( log N ) 2 ) before normalization. At even macro levels the signed word height produces a larger, visibly oscillatory discrepancy of order at most 1 / log N 1/\sqrt{\log N} 1/ log N after normalization. Both tend uniformly to zero; their markedly different finite-level appearance does not require a different periodic limiting function.
Figure 12. The normalized summatory residual and the periodic term Ψ \Psi Ψ . The phase is sampled at even sequence indices N ≈ ( 14 / 3 ) 2 K 2 θ N\approx(14/3)2^{K^2\theta} N ≈ ( 14/3 ) 2 K 2 θ . The even scales K = 16 , 18 , 20 K=16,18,20 K = 16 , 18 , 20 show the signed height correction in (A.36). On the odd scale K = 21 K=21 K = 21 it is absent except in the short boundary intervals where the actual macro level differs from K K K ; the agreement with Ψ \Psi Ψ is consequently much closer. The actual and ideal boundaries differ by O ( K ) O(K) O ( K ) indices.
Acknowledgments The author thanks Benoît Cloitre for his work on the exact-fit interleaving framework, which provides the combinatorial foundation for the word constructions used here.
AI-Disclosure The author used OpenAI’s ChatGPT for help in language editing, LaTeX restructuring, mathematical explorations, and the preparation of verification scripts. All mathematical statements, proofs, computations, references, and the final presentation were independently verified by the author, who assumes full responsibility for the content.