Theorem 43, upper bound (EPI-8, proof) #
The three stages of DoubleShrinkingStages are composed by the Markov property at fixed times
(notYet_add_le), splitting the extra rounds r into thirds. The failure probabilities per
phase are polynomially small in n, which gives the paper's tail O(n^{A' - α' r}); the
number of double exponential phases is J = ⌊log_ℓ (β ln n / (2 D₀))⌋ ≤ log_ℓ ln n, and the
factor 2^J of the phase calculus is a power of n.
Real powers of n #
The number of double exponential phases, J = ⌊log_ℓ (β ln n / (2 D₀))⌋: the last target
ε_J lies between n^{-β} and n^{-β/(2ℓ)}, and J ≤ log_ℓ ln n.
Three stages in sequence, the extra rounds r split into thirds.
Theorem 43 for one value of n, given the constants of the three stages: after
K + J + r rounds, with J ≤ ⌈log_ℓ ln n⌉, the tail is at most
(2^K + 2) n^{max A₂ 1 + 2ω/3 - (ω/3) r}.
Theorem 43, tail, in the main case g > 0, α > 0.