The cap H H H is valid by static transfer at the fixed depth r δ ( d ) r_\delta(d) r δ ( d ) :
the squared transfer and burn-in factors cost at most e 2 δ e^{2\delta} e 2 δ .
The third δ \delta δ leaves room for integer rounding and increasing the
fixed burn-in constants. The coefficient bound is simultaneous on the
whole class, hence the cap may be retained at later stages.
Throughout the proof take minima also with the fixed bound
C 2 t 2 ( x ) 1 / 3 C_2t_2(x)^{1/3} C 2 t 2 ( x ) 1/3 on squared coefficients supplied by the first
height-reduction stage. This ensures the growth hypothesis g 0 ( x ) ≤ C x 1 / 3 g_0(x)\le Cx^{1/3} g 0 ( x ) ≤ C x 1/3 .
Here are the elementary bounds needed for both initialization and
coefficient return. For fixed constants C , p C,p C , p ,
V ( C ϵ − p ) ≤ V ( ϵ − 1 ) + b ( C , p ) 4 − m . (E3) V(C\epsilon^{-p})\le V(\epsilon^{-1})+b(C,p)4^{-m}. \tag{E3} V ( C ϵ − p ) ≤ V ( ϵ − 1 ) + b ( C , p ) 4 − m . ( E3 ) For the maximum defining W ^ \widehat W W , this follows by taking the
maximum with its constant branch. Also V V V is 4 − m − 1 4^{-m-1} 4 − m − 1 -Lipschitz.
For Y = C k ( Q s ) 2 Y=C_k(Qs)^2 Y = C k ( Q s ) 2 , h = t ( Q ) h=t(Q) h = t ( Q ) and y = log ( s ) / Q y=\log(s)/Q y = log ( s ) / Q , the tower definition
gives
t ( X X ) ≤ h + B h , t ( Y ) ≤ h + B h + y . (E4) t(X^X)\le h+B_h,\qquad t(Y)\le h+B_h+y. \tag{E4} t ( X X ) ≤ h + B h , t ( Y ) ≤ h + B h + y . ( E4 ) Indeed log ( Y + 2 ) ≤ C Q ( 1 + y ) \log(Y+2)\le C Q(1+y) log ( Y + 2 ) ≤ CQ ( 1 + y ) ; the product bound for the remaining
iterated logarithms gives t ( Y ) ≤ t ( Q ) + C + t ( 1 + y ) − 3 t(Y)\le t(Q)+C+t(1+y)-3 t ( Y ) ≤ t ( Q ) + C + t ( 1 + y ) − 3 ,
and t ( 1 + y ) ≤ y + 4 t(1+y)\le y+4 t ( 1 + y ) ≤ y + 4 . The self-power bound follows by applying the
same argument to log ( X X ) = X log X \log(X^X)=X\log X log ( X X ) = X log X .
Choose C h = C ( 1 + S ∗ ) 2 C_h=C(1+S_*)^2 C h = C ( 1 + S ∗ ) 2 with a sufficiently large universal C C C ,
and call a height high if
h ≥ C h R δ ϵ − 5 h\ge C_hR_\delta\epsilon^{-5} h ≥ C h R δ ϵ − 5 .
At low heights (E4) implies
r δ ( Y ) ≤ C ( ϵ − 17 + y ) , r δ ( X X ) ≤ C ϵ − 17 . (E5) r_\delta(Y)\le C(\epsilon^{-17}+y),\qquad
r_\delta(X^X)\le C\epsilon^{-17}. \tag{E5} r δ ( Y ) ≤ C ( ϵ − 17 + y ) , r δ ( X X ) ≤ C ϵ − 17 . ( E5 ) Combining (E3), Lipschitz continuity, and D ∗ ≥ 5 D_*\ge5 D ∗ ≥ 5 gives
e − y [ V ( r δ ( Y ) ) + S ] 1 / 3 ≤ D ∗ 1 / 3 , (E6) e^{-y}[V(r_\delta(Y))+S]^{1/3}\le D_*^{1/3}, \tag{E6} e − y [ V ( r δ ( Y )) + S ] 1/3 ≤ D ∗ 1/3 , ( E6 ) provided b ∗ b_* b ∗ absorbs the fixed constants in (E3).
More explicitly, split (E5) into C ϵ − 17 + C r ′ y C\epsilon^{-17}+C_r'y C ϵ − 17 + C r ′ y ,
use (E3) on the first term, and Lipschitz continuity on the second.
This gives V ( r δ ( Y ) ) + S ≤ D ∗ + C r ′ 4 − m − 1 y V(r_\delta(Y))+S\le D_*+C_r'4^{-m-1}y V ( r δ ( Y )) + S ≤ D ∗ + C r ′ 4 − m − 1 y .
Choose b ∗ b_* b ∗ above the constant required by (E3), and also so that
D ∗ ≥ C r ′ 4 − m / 12 D_*\ge C_r'4^{-m}/12 D ∗ ≥ C r ′ 4 − m /12 for every m m m . Then
log ( 1 + C r ′ 4 − m y / ( 4 D ∗ ) ) / 3 − y ≤ 0 \log(1+C_r'4^{-m}y/(4D_*))/3-y\le0 log ( 1 + C r ′ 4 − m y / ( 4 D ∗ )) /3 − y ≤ 0 .
The constant in (E5) is polynomial in C h C_h C h , while the fixed-power
allowance (E3) is at most C log ( e + C h ) C\log(e+C_h) C log ( e + C h ) : this follows by counting
the additional ordinary logarithms needed to remove a fixed factor
and applying the 4 − m 4^{-m} 4 − m contraction. Thus all these choices permit
b ∗ ≤ C log ( e + S ∗ ) b_*\le C\log(e+S_*) b ∗ ≤ C log ( e + S ∗ ) .
Thus (E6) has coefficient exactly one; no fixed multiplicative loss
is introduced. The analogous estimate at X X X^X X X follows with y = 0 y=0 y = 0 .
We first initialize j = 1 j=1 j = 1 . Use the original cap H H H , and all earlier
caps if present, as the working coefficient majorant. At high heights,
r δ ( Y ) ≤ C ( h + ϵ − 1 + y ) r_\delta(Y)\le C(h+\epsilon^{-1}+y) r δ ( Y ) ≤ C ( h + ϵ − 1 + y ) and
V ( r δ ( Y ) ) + S ≤ h + y V(r_\delta(Y))+S\le h+y V ( r δ ( Y )) + S ≤ h + y after increasing C h C_h C h .
To justify this also for W ^ \widehat W W , note its constant branch
t ˉ ( δ − 1 ) \bar t(\delta^{-1}) t ˉ ( δ − 1 ) is smaller than h / 4 h/4 h /4 here. For the nonconstant
branch, W m ≤ t ˉ ≤ t + 1 W_m\le\bar t\le t+1 W m ≤ t ˉ ≤ t + 1 and
t ( C ( h + ϵ − 1 + y ) ) ≤ t ( C ′ ( h + ϵ − 1 ) ) + t ( 1 + y ) + C t(C(h+\epsilon^{-1}+y))\le t(C'(h+\epsilon^{-1}))+t(1+y)+C t ( C ( h + ϵ − 1 + y )) ≤ t ( C ′ ( h + ϵ − 1 )) + t ( 1 + y ) + C ;
its first term plus the fixed S ∗ S_* S ∗ and constants is at most h / 2 h/2 h /2 .
For 0 ≤ y ≤ 1 0\le y\le1 0 ≤ y ≤ 1 use the same slack to get a bound by h h h ;
for y ≥ 1 y\ge1 y ≥ 1 use t ( 1 + y ) ≤ y + 4 t(1+y)\le y+4 t ( 1 + y ) ≤ y + 4 . Then
e − y ( h + y ) 1 / 3 ≤ h 1 / 3 e^{-y}(h+y)^{1/3}\le h^{1/3} e − y ( h + y ) 1/3 ≤ h 1/3 . The same argument applies to X X X^X X X .
At low heights use (E6). Consequently the two dynamic bounds (D1)
hold with M = e 16 δ A max { t ( Q ) , D ∗ } 1 / 3 M=e^{16\delta}A\max\{t(Q),D_*\}^{1/3} M = e 16 δ A max { t ( Q ) , D ∗ } 1/3 .
The starting depth r 0 ( Q ) r_0(Q) r 0 ( Q ) is treated in exactly these two ranges:
high heights give V ( r 0 ) + S ≤ h V(r_0)+S\le h V ( r 0 ) + S ≤ h , and low heights give
V ( r 0 ) + S ≤ D ∗ V(r_0)+S\le D_* V ( r 0 ) + S ≤ D ∗ . Thus (E1) supplies (D2).
The newest floor is also covered: with
Ξ = ⌈ 4 C d e g δ − 1 ⌈ C c u t ϵ − 2 ⌉ ⌉ \Xi=\lceil4C_{\rm deg}\delta^{-1}\lceil C_{\rm cut}\epsilon^{-2}\rceil\rceil Ξ = ⌈ 4 C deg δ − 1 ⌈ C cut ϵ − 2 ⌉⌉ ,
we have r δ ( Ξ ) ≤ C ϵ − 12 r_\delta(\Xi)\le C\epsilon^{-12} r δ ( Ξ ) ≤ C ϵ − 12 and hence
( 1 + δ ) H ( Ξ ) 2 ≤ e 4 δ A D ∗ 1 / 3 . (E7) (1+\delta)H(\Xi)^2\le e^{4\delta}A D_*^{1/3}. \tag{E7} ( 1 + δ ) H ( Ξ ) 2 ≤ e 4 δ A D ∗ 1/3 . ( E7 ) Older floors are covered by hypothesis. So is the original-seed floor.
The constant C 0 C_0 C 0 itself is covered by A 0 A_0 A 0 . This proves the floor
part of (D1). The near-unit depth lemma gives (E2) for j = 1 j=1 j = 1 .
Now suppose (E2) proved for a given j j j . Write
A ′ = e 16 δ + 24 ϵ j A A'=e^{16\delta+24\epsilon j}A A ′ = e 16 δ + 24 ϵ j A and
P j ( x ) = max { t j ( x ) , D ∗ } 1 / 3 P_j(x)=\max\{t_j(x),D_*\}^{1/3} P j ( x ) = max { t j ( x ) , D ∗ } 1/3 . Define
r ϵ ( x ) = max { R δ , ⌈ C r t ( x ) ⌉ + ⌈ D r / ϵ ⌉ } , k ϵ ( x ) = least odd integer at least max { Q ϵ , ϵ − 1 log ( r ϵ ( x ) + 1 ) } . r_\epsilon(x)=\max\{R_\delta,\lceil C_rt(x)\rceil+
\lceil D_r/\epsilon\rceil\},
\quad k_\epsilon(x)=\text{least odd integer at least }
\max\{Q_\epsilon,\epsilon^{-1}\log(r_\epsilon(x)+1)\}. r ϵ ( x ) = max { R δ , ⌈ C r t ( x )⌉ + ⌈ D r / ϵ ⌉} , k ϵ ( x ) = least odd integer at least max { Q ϵ , ϵ − 1 log ( r ϵ ( x ) + 1 )} . With universal large D r , C r D_r,C_r D r , C r , one has
r ϵ ( x ) ≥ r 0 ( k ϵ ( x ) ) r_\epsilon(x)\ge r_0(k_\epsilon(x)) r ϵ ( x ) ≥ r 0 ( k ϵ ( x )) .
Indeed R δ R_\delta R δ is included, the logarithmic part of k ϵ k_\epsilon k ϵ
has height at most C log ( r ϵ + 2 ) C\log(r_\epsilon+2) C log ( r ϵ + 2 ) , and the Q ϵ Q_\epsilon Q ϵ
part has height O ( log ( ϵ − 1 + 2 ) ) O(\log(\epsilon^{-1}+2)) O ( log ( ϵ − 1 + 2 )) ; both fit below
r ϵ / 2 C b r_\epsilon/2C_b r ϵ /2 C b after the fixed burn-in increase.
Apply the known profile at this order and depth and then static
transfer. The order factor, squared burn-in factor and squared
transfer factor cost at most e 3 ϵ e^{3\epsilon} e 3 ϵ in total, and therefore
g 0 ( x ) : = min { G ∗ ( x ) 2 , C 2 t 2 ( x ) 1 / 3 , H l ( x ) 2 , e 5 ϵ A ′ P j ( k ϵ ( x ) ) } (E8) g_0(x):=\min\{G_*(x)^2,C_2t_2(x)^{1/3},H_l(x)^2,
e^{5\epsilon}A'P_j(k_\epsilon(x))\}
\tag{E8} g 0 ( x ) := min { G ∗ ( x ) 2 , C 2 t 2 ( x ) 1/3 , H l ( x ) 2 , e 5 ϵ A ′ P j ( k ϵ ( x ))} ( E8 ) is a valid nondecreasing squared coefficient majorant. The minimum
includes every retained H l H_l H l and the newest H H H .
Set M = A ′ P j + 1 ( Q ) M=A'P_{j+1}(Q) M = A ′ P j + 1 ( Q ) . At high heights,
k ϵ ( X X ) ≤ h k_\epsilon(X^X)\le h k ϵ ( X X ) ≤ h , and for the cutoff
k ϵ ( Y ) ≤ h k_\epsilon(Y)\le h k ϵ ( Y ) ≤ h when y ≤ 1 y\le1 y ≤ 1 ; when y ≥ 1 y\ge1 y ≥ 1 ,
k ϵ ( Y ) ≤ h / 2 + 2 + y / ( ϵ h ) ≤ h + y ≤ h ( 1 + y ) . k_\epsilon(Y)\le h/2+2+y/(\epsilon h)\le h+y\le h(1+y). k ϵ ( Y ) ≤ h /2 + 2 + y / ( ϵ h ) ≤ h + y ≤ h ( 1 + y ) . These follow from k ϵ ( x ) ≤ Q ϵ + 3 + ϵ − 1 log [ C ( R δ + t ( x ) + ϵ − 1 ) ] k_\epsilon(x)\le Q_\epsilon+3+
\epsilon^{-1}\log[C(R_\delta+t(x)+\epsilon^{-1})] k ϵ ( x ) ≤ Q ϵ + 3 + ϵ − 1 log [ C ( R δ + t ( x ) + ϵ − 1 )] and the
choice h ≥ C h R δ ϵ − 5 h\ge C_hR_\delta\epsilon^{-5} h ≥ C h R δ ϵ − 5 . The same logarithmic
bound at y = 0 y=0 y = 0 is at most h / 2 h/2 h /2 ; its increment is at most
y / ( ϵ h ) y/(\epsilon h) y / ( ϵ h ) , with at most two for odd rounding.
The iterated-height product estimate used here follows directly
from the tower thresholds. For x 1 , x 2 ≥ 1 x_1,x_2\ge1 x 1 , x 2 ≥ 1 set
n = max { t ( x 1 ) , t ( x 2 ) } ≥ 3 n=\max\{t(x_1),t(x_2)\}\ge3 n = max { t ( x 1 ) , t ( x 2 )} ≥ 3 and E = E n − 1 E=E_{n-1} E = E n − 1 .
Then x l ≤ E − 2 x_l\le E-2 x l ≤ E − 2 , and both x 1 + x 2 x_1+x_2 x 1 + x 2 and x 1 x 2 x_1x_2 x 1 x 2 are at most
e E − 2 = E n − 2 e^E-2=E_n-2 e E − 2 = E n − 2 ; indeed 2 ( E − 2 ) 2(E-2) 2 ( E − 2 ) and ( E − 2 ) 2 (E-2)^2 ( E − 2 ) 2 are below that
quantity for E ≥ e e E\ge e^e E ≥ e e . Thus
t ( x 1 + x 2 ) , t ( x 1 x 2 ) ≤ n + 1 ≤ t ( x 1 ) + t ( x 2 ) t(x_1+x_2),t(x_1x_2)\le n+1\le t(x_1)+t(x_2) t ( x 1 + x 2 ) , t ( x 1 x 2 ) ≤ n + 1 ≤ t ( x 1 ) + t ( x 2 ) .
Apply the sum bound successively to the product bound to obtain
t j ( x 1 x 2 ) ≤ t j ( x 1 ) + t j ( x 2 ) t_j(x_1x_2)\le t_j(x_1)+t_j(x_2) t j ( x 1 x 2 ) ≤ t j ( x 1 ) + t j ( x 2 ) for every j ≥ 1 j\ge1 j ≥ 1 .
For y ≥ 1 y\ge1 y ≥ 1 , the already proved t ( n ) ≤ n t(n)\le n t ( n ) ≤ n on integers n ≥ 3 n\ge3 n ≥ 3
gives t j ( 1 + y ) ≤ t ( 1 + y ) ≤ y + 4 ≤ 5 y t_j(1+y)\le t(1+y)\le y+4\le5y t j ( 1 + y ) ≤ t ( 1 + y ) ≤ y + 4 ≤ 5 y .
Consequently t j ( k ϵ ( Y ) ) ≤ t j ( h ) + 5 y t_j(k_\epsilon(Y))\le t_j(h)+5y t j ( k ϵ ( Y )) ≤ t j ( h ) + 5 y , as required.
Since max { t j ( h ) , D ∗ } ≥ 5 \max\{t_j(h),D_*\}\ge5 max { t j ( h ) , D ∗ } ≥ 5 , multiplication by e − y e^{-y} e − y
after taking cube roots removes this additive 5 y 5y 5 y exactly.
Thus (E8) proves both dynamic inequalities (D1) at high heights.
At low heights use the retained newest cap and (E6), whose cost
e 3 δ A e^{3\delta}A e 3 δ A is smaller than A ′ A' A ′ . The floor proof (E7) is unchanged.
It remains to initialize the new depth induction; a coefficient bound
alone would not do this. At high heights apply the preceding stage
at order k = k ϵ ( x 0 ) k=k_\epsilon(x_0) k = k ϵ ( x 0 ) with x 0 x_0 x 0 any argument of height h h h
and choose its logarithmic order using r 0 ( Q ) r_0(Q) r 0 ( Q ) directly:
k k k is the least odd integer at least
max { Q ϵ , ϵ − 1 log ( r 0 ( Q ) + 1 ) } \max\{Q_\epsilon,\epsilon^{-1}\log(r_0(Q)+1)\} max { Q ϵ , ϵ − 1 log ( r 0 ( Q ) + 1 )} .
Then k ≤ h k\le h k ≤ h , r 0 ( k ) ≤ r 0 ( Q ) r_0(k)\le r_0(Q) r 0 ( k ) ≤ r 0 ( Q ) , and its order factor is at most
e ϵ e^\epsilon e ϵ . This supplies (D2) with the new M M M .
At low heights the original profile (E1) and (E3) supply it instead.
The near-unit depth lemma costs e 21 ϵ e^{21\epsilon} e 21 ϵ , covered by the
next e 24 ϵ e^{24\epsilon} e 24 ϵ . Finite induction on j j j proves (E2).