Fluctuations of the satisfiability transition
Add independent random clauses to a Boolean formula until the formula becomes unsatisfiable. How much does the number of clauses at this first failure vary from one sample to another? For every fixed clause size k ≥ 4 k \ge4 k ≥ 4 n n n n n n n n n n log n n \log n n log n
A proper k k k is a disjunction of literals on k k k k ≥ 3 k \ge3 k ≥ 3 n ≥ k n \ge k n ≥ k C 1 , C 2 , … C_1,C_2,\ldots C 1 , C 2 , … 2 k ( n k ) 2^k\binom{n}{k} 2 k ( k n ) n n n
F m = C 1 ∧ ⋯ ∧ C m , F 0 = t r u e , H n = min { m ≥ 1 : F m is unsatisfiable } . F_m = C_1 \wedge\cdots\wedge C_m,\qquad F_0 = \mathrm{true},\qquad H_n = \min\{m \ge1 : F_m\text{ is unsatisfiable}\}. F m = C 1 ∧ ⋯ ∧ C m , F 0 = true , H n = min { m ≥ 1 : F m is unsatisfiable } . For a fixed B > 0 B > 0 B > 0 T n , B = min { H n , ⌊ B n ⌋ } T_{n,B} = \min\{H_n,\lfloor Bn\rfloor\} T n , B = min { H n , ⌊ B n ⌋} 1 − 2 − k 1 - 2^{-k} 1 − 2 − k
Pr ( H n > m ) ≤ 2 n ( 1 − 2 − k ) m . \Pr(H_n > m) \le2^n(1-2^{-k})^m. Pr ( H n > m ) ≤ 2 n ( 1 − 2 − k ) m . Thus H n H_n H n
Theorem 1.1. Fix an integer k ≥ 3 k \ge3 k ≥ 3
ℓ k ( n ) = { log ( e n ) , k = 3 , 1 , k ≥ 4 , U k = log 2 − log ( 1 − 2 − k ) . \ell_k(n) =
\begin{cases}
\log(en), & k = 3,\\
1, & k \ge4,
\end{cases}
\qquad
U_k = \frac{\log2}{-\log(1-2^{-k})}. ℓ k ( n ) = { log ( e n ) , 1 , k = 3 , k ≥ 4 , U k = − log ( 1 − 2 − k ) log 2 . There are constants C k , c k > 0 C_k,c_k > 0 C k , c k > 0
Var ( H n ) ≤ C k n ℓ k ( n ) ( n ≥ k ) , Var ( H n ) ≥ c k n for all sufficiently large n . \operatorname{Var}(H_n) \le C_k n\ell_k(n)\quad(n \ge k),\qquad\operatorname{Var}(H_n) \ge c_k n\quad\text{for all sufficiently large }n. Var ( H n ) ≤ C k n ℓ k ( n ) ( n ≥ k ) , Var ( H n ) ≥ c k n for all sufficiently large n . For every fixed $B > 0 there is C k , B < ∞ C_{k,B} < \infty C k , B < ∞
Var ( T n , B ) ≤ C k , B n ℓ k ( n ) ( n ≥ k ) . \operatorname{Var}(T_{n,B}) \le C_{k,B}n\ell_k(n)\quad(n \ge k). Var ( T n , B ) ≤ C k , B n ℓ k ( n ) ( n ≥ k ) . If B > U k B > U_k B > U k Var ( T n , B ) ≥ c k n \operatorname{Var}(T_{n,B}) \ge c_k n Var ( T n , B ) ≥ c k n for all sufficiently large n n n k k k B B B
All constants concern fixed k k k L n = O ( n ) L_n = O(n) L n = O ( n ) Pr ( H n > L n − 1 ) ≤ 1 / 4 \Pr(H_n > L_n - 1) \le1/4 Pr ( H n > L n − 1 ) ≤ 1/4 B > U k B > U_k B > U k [17 ] closes it and proves Var ( H n ) = Θ ( n ) \operatorname{Var}(H_n) = \Theta(n) Var ( H n ) = Θ ( n )
The identity Pr ( F m is satisfiable ) = Pr ( H n > m ) \Pr(F_m\text{ is satisfiable}) = \Pr(H_n > m) Pr ( F m is satisfiable ) = Pr ( H n > m ) η \eta η 1 − η 1-\eta 1 − η 0 < η < 1 / 2 0 < \eta< 1/2 0 < η < 1/2 O k , η ( n ℓ k ( n ) ) O_{k,\eta}(\sqrt{n\ell_k(n)}) O k , η ( n ℓ k ( n ) )
Pr ( ∣ H n − E H n ∣ ≥ t n ℓ k ( n ) ) ≤ C k t − 2 ( t > 0 ) . \Pr\left(\lvert H_n-\mathbb{E}H_n\rvert\ge t\sqrt{n\ell_k(n)}\right) \le C_k t^{-2} \qquad(t>0). Pr ( ∣ H n − E H n ∣ ≥ t n ℓ k ( n ) ) ≤ C k t − 2 ( t > 0 ) . This is concentration about the finite-size expectation. The limiting threshold α k \alpha_k α k [16 ] , Theorem 1.1 identifies lim n E H n / n \lim_n \mathbb{E}H_n/n lim n E H n / n E H n − α k n \mathbb{E}H_n-\alpha_k n E H n − α k n k = 3 k=3 k = 3 [15 ] , Theorem 1.1 proves that the limiting threshold α 3 \alpha_3 α 3
Earlier work and the new estimate
The location and the width of a threshold are different questions. [12 ] proved a sharp threshold sequence for each fixed clause size, without asserting convergence of that sequence. [2 ] used a weighted second moment to locate the threshold within O ( k ) O(k) O ( k ) 2 k log 2 2^k\log2 2 k log 2 k k k [7 ] proved the predicted limiting threshold for all sufficiently large k k k [6 ] , Corollary 1.2, made public on October 5, 2026, establishes the satisfiability conjecture for every fixed k ≥ 3 k \ge3 k ≥ 3 [16 ] , Theorem 1.1 establishes a limiting location for every fixed k ≥ 3 k \ge3 k ≥ 3 O k ( n 1 + 2 / k ) O_k(n^{1+2/k}) O k ( n 1 + 2/ k ) min ( H n − 1 , 2 k + 1 n ) \min(H_n-1,2^{k+1}n) min ( H n − 1 , 2 k + 1 n ) [16 ] , Proposition 3.3.
For transition width, [18 ] proved an Ω k ( n ) \Omega_k(\sqrt{n}) Ω k ( n ) [5 ] , Corollaries 7.10–7.11, proves an O k , η ( n / log n ) O_{k,\eta}(n/\log n) O k , η ( n / log n ) k ≥ 3 k \ge3 k ≥ 3 O k , η ( n 1 / 2 + 1 / k ) O_{k,\eta}(n^{1/2+1/k}) O k , η ( n 1/2 + 1/ k ) O k ( n 1 + 2 / k ) O_k(n^{1+2/k}) O k ( n 1 + 2/ k ) [6 ] , Theorems 1.1 and 1.3; the renewed estimate, together with the Abbe–Montanari criterion, yields the limiting-threshold theorem credited above. The upper bounds here sharpen these fluctuation estimates. For k = 3 k=3 k = 3 [17 ] further removes the logarithmic loss in this paper’s upper bound.
Our upper bound uses the coordinate-omission form of the Efron–Stein inequality [4 , 8 ] . Deleting one clause leaves its k k k k k k k − 1 k-1 k − 1 k k k [12 ] , Lemma 5.7; sequential conditioning on a residual assignment set is developed in Carenini [5 ] , Theorem 4.3 and Lemma 6.1. We prove a block estimate uniform in the number of variables and the block length. It also covers assignment sets that no single k k k
The main improvement comes after this replacement step. Instead of bounding the number of clauses incident to the deleted clause’s variables by a logarithmic cutoff, we retain that number as a random parameter. Its fixed moments are bounded. The proof must therefore use the incidence count without destroying the independence of the shorter-clause tests or of future ordinary clauses. Conditioning on the incidence pattern through the cap achieves both. Collisions involving two of the deleted clause’s variables are paid for by joint incidence and collision moments.
The route through the upper bound
Write L = ⌊ B n ⌋ L = \lfloor Bn \rfloor L = ⌊ B n ⌋ C i C_i C i D i D_i D i
Var ( T n , B ) ≤ ∑ i = 1 L E D i 2 . \operatorname{Var}(T_{n,B}) \le\sum_{i=1}^{L} \mathbb{E}D_i^2. Var ( T n , B ) ≤ i = 1 ∑ L E D i 2 . The delay D i D_i D i C i C_i C i D i 2 D_i^2 D i 2
Here is the shorter-clause estimate used for that purpose. A collection of clauses kills S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u S S S q d ( S ) q_d(S) q d ( S ) d d d ( k − 1 ) (k-1) ( k − 1 ) S S S τ k ( S ) \tau_k(S) τ k ( S ) k k k u ≥ k u \ge k u ≥ k d ≥ 1 d \ge1 d ≥ 1 β = k / ( k − 1 ) \beta= k/(k-1) β = k / ( k − 1 )
τ k ( S ) q d ( S ) β ≤ C k d β . \tau_k(S)q_d(S)^\beta\le C_k d^\beta. τ k ( S ) q d ( S ) β ≤ C k d β . This estimate holds for every assignment set, with no lower cutoff on q d ( S ) q_d(S) q d ( S )
Section 3 connects this statement to clause deletion. Call the variables of C i C_i C i C i C_i C i S m S_m S m C i C_i C i k k k ( k − 1 ) (k-1) ( k − 1 ) C i C_i C i k k k S m S_m S m
Conditional on the exposed incidence pattern, let Z Z Z d = max { 1 , Z } d = \max\{1,Z\} d = max { 1 , Z } q d ( S m ) ≥ a q_d(S_m) \ge a q d ( S m ) ≥ a q = q d ( S m ) q = q_d(S_m) q = q d ( S m ) k k k q k q^k q k q − β q^{-\beta} q − β q k − β q^{k-\beta} q k − β a a a a − β a^{-\beta} a − β
∫ a k − 2 β − 1 d a . \int a^{k-2\beta-1}\,da. ∫ a k − 2 β − 1 d a . At k = 3 k=3 k = 3 k = 2 β k=2\beta k = 2 β k ≥ 4 k \ge4 k ≥ 4 k > 2 β k > 2\beta k > 2 β
Section 5 removes a sufficiently late cap and records the exact first-unsatisfiable and last-satisfiable endpoint identities. Section 6 proves the lower bound, completing the variance theorem. Section 7 specializes the cap constants to three clauses and transfers the proper-clause concentration to the Poisson clause law used in the threshold companion. After that main argument, Appendix A determines the limits of the two estimates for arbitrary assignment sets. Appendix B compares proper-clause models at different sizes, and Appendix C gives a second three-clause proof based on prefix exposure and incidence truncation.
Survival of a set of assignments
The deletion argument will leave a set of assignments that must pass random tests of length k − 1 k-1 k − 1 k k k [12 ] (Lemma 5.7).
Fix integers k ≥ 3 k \ge3 k ≥ 3 u ≥ k u \ge k u ≥ k
r = k − 1 , β = k k − 1 . r = k - 1, \qquad\beta= \frac{k}{k-1}. r = k − 1 , β = k − 1 k . A proper s s s 1 ≤ s ≤ u 1 \le s \le u 1 ≤ s ≤ u s s s u u u S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u S S S d , g d,g d , g
q d ( S ) = P ( d proper r -clauses kill S ) , R g ( S ) = P ( g proper k -clauses kill S ) . q_d(S) = \mathbb{P}(d\text{ proper }r\text{-clauses kill }S), \qquad R_g(S) = \mathbb{P}(g\text{ proper }k\text{-clauses kill }S). q d ( S ) = P ( d proper r -clauses kill S ) , R g ( S ) = P ( g proper k -clauses kill S ) . For a nonempty set, q 0 ( S ) = R 0 ( S ) = 0 q_0(S) = R_0(S) = 0 q 0 ( S ) = R 0 ( S ) = 0 H k ( S ) H_k(S) H k ( S ) k k k
H k ( ∅ ) = 0 , τ k ( S ) = E H k ( S ) . H_k(\varnothing) = 0, \qquad\tau_k(S) = \mathbb{E}H_k(S). H k ( ∅ ) = 0 , τ k ( S ) = E H k ( S ) . These expectations are finite: for every integer m ≥ 0 m \ge0 m ≥ 0
P ( H k ( S ) > m ) ≤ ∣ S ∣ ( 1 − 2 − k ) m ≤ 2 u exp ( − 2 − k m ) . (1) \mathbb{P}(H_k(S) > m) \le|S|(1-2^{-k})^m \le2^u\exp(-2^{-k}m). \tag*{(1)} P ( H k ( S ) > m ) ≤ ∣ S ∣ ( 1 − 2 − k ) m ≤ 2 u exp ( − 2 − k m ) . (1) Indeed, each fixed assignment survives each independent clause with probability 1 − 2 − k 1-2^{-k} 1 − 2 − k
Replacing one shorter clause
For a nonempty set S S S S S S b b b s s s S S S
h s ( S ) = ( b ) s 2 s ( u ) s , 1 ≤ s ≤ u . (2) h_s(S) = \frac{(b)_s}{2^s(u)_s}, \qquad1 \le s \le u. \tag*{(2)} h s ( S ) = 2 s ( u ) s ( b ) s , 1 ≤ s ≤ u . (2) where ( a ) s = a ( a − 1 ) ⋯ ( a − s + 1 ) (a)_s = a(a-1)\cdots(a-s+1) ( a ) s = a ( a − 1 ) ⋯ ( a − s + 1 ) a < s a < s a < s S S S S S S
Write h = h r ( S ) h = h_r(S) h = h r ( S ) 0 ≤ h ≤ 2 − r ≤ 1 / 4 0 \le h \le2^{-r} \le1/4 0 ≤ h ≤ 2 − r ≤ 1/4 b ≥ k b \ge k b ≥ k
h k ( S ) = h b − r 2 ( u − r ) ≥ 1 k h β . (3) h_k(S) = h\frac{b-r}{2(u-r)} \ge\frac{1}{k}h^\beta. \tag*{(3)} h k ( S ) = h 2 ( u − r ) b − r ≥ k 1 h β . (3) In fact b − r ≥ b / k b-r \ge b/k b − r ≥ b / k u − r ≤ u u-r \le u u − r ≤ u
h = 1 2 r ∏ j = 0 r − 1 b − j u − j ≤ ( b 2 u ) r . h=\frac{1}{2^r}\prod_{j=0}^{r-1}\frac{b-j}{u-j}\le\left(\frac{b}{2u}\right)^r. h = 2 r 1 j = 0 ∏ r − 1 u − j b − j ≤ ( 2 u b ) r . Substituting these bounds into the equality proves (3) . Its hypothesis matters. For the cylinder whose first r r r
h k ( S ) = 0 , h r ( S ) = 1 2 r ( u r ) > 0. (4) h_k(S)=0,\qquad h_r(S)=\frac{1}{2^r\binom{u}{r}}>0. \tag*{(4)} h k ( S ) = 0 , h r ( S ) = 2 r ( r u ) 1 > 0. (4) No single k k k
Lemma 2.1 (One-clause replacement). For an integer k ≥ 3 k \ge3 k ≥ 3
K k = ( 2 k ( k − 1 ) ) k − 1 . K_k=\left(2^k(k-1)\right)^{k-1}. K k = ( 2 k ( k − 1 ) ) k − 1 . For every integer u ≥ k u \ge k u ≥ k S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^u S ⊆ { 0 , 1 } u g ≥ 1 g \ge1 g ≥ 1
R g ( S ) ≥ q 1 ( S ) − K k g − ( k − 1 ) . R_g(S)\ge q_1(S)-K_kg^{-(k-1)}. R g ( S ) ≥ q 1 ( S ) − K k g − ( k − 1 ) . Proof. For S = ∅ S=\varnothing S = ∅ S S S b , r , h b,r,h b , r , h S S S
R g ( S ) ≥ 1 − ( 1 − h k ( S ) ) g ≥ 1 − e − g h k ( S ) . R_g(S)\ge1-(1-h_k(S))^g\ge1-e^{-gh_k(S)}. R g ( S ) ≥ 1 − ( 1 − h k ( S ) ) g ≥ 1 − e − g h k ( S ) . First assume b ≥ k b\ge k b ≥ k ( g / k ) h 1 / r ≥ 2 (g/k)h^{1/r}\ge2 ( g / k ) h 1/ r ≥ 2 (3) gives g h k ( S ) ≥ 2 h gh_k(S)\ge2h g h k ( S ) ≥ 2 h
R g ( S ) ≥ 1 − e − 2 h ≥ h . R_g(S)\ge1-e^{-2h}\ge h. R g ( S ) ≥ 1 − e − 2 h ≥ h . For the last inequality, 1 − e − 2 h − h 1-e^{-2h}-h 1 − e − 2 h − h h = 0 h=0 h = 0 [ 0 , 1 / 4 ] [0,1/4] [ 0 , 1/4 ] ( g / k ) h 1 / r < 2 (g/k)h^{1/r}<2 ( g / k ) h 1/ r < 2
h < ( 2 k ) r g − r ≤ K k g − r , h<(2k)^r g^{-r}\le K_kg^{-r}, h < ( 2 k ) r g − r ≤ K k g − r , because 2 k ≤ 2 k ( k − 1 ) 2k\le2^k(k-1) 2 k ≤ 2 k ( k − 1 ) R g ( S ) R_g(S) R g ( S )
If b < r b<r b < r h = 0 h=0 h = 0 b = r b=r b = r (2) gives
h = 1 2 r ( u r ) ≤ ( r 2 u ) r . h=\frac{1}{2^r\binom{u}{r}}\le\left(\frac{r}{2u}\right)^r. h = 2 r ( r u ) 1 ≤ ( 2 u r ) r . When g < 2 k + 1 u g<2^{k+1}u g < 2 k + 1 u ( 2 k r / g ) r = K k g − r (2^kr/g)^r=K_kg^{-r} ( 2 k r / g ) r = K k g − r g ≥ 2 k + 1 u g\ge2^{k+1}u g ≥ 2 k + 1 u (1) to the full cube:
R g ( S ) ≥ 1 − exp ( ( log 2 − 2 ) u ) ≥ 1 − e − u > 1 4 ≥ h . R_g(S)\ge1-\exp((\log2-2)u)\ge1-e^{-u}>\frac14\ge h. R g ( S ) ≥ 1 − exp (( log 2 − 2 ) u ) ≥ 1 − e − u > 4 1 ≥ h . Here u ≥ k ≥ 3 u\ge k\ge3 u ≥ k ≥ 3 h k ( S ) = 0 h_k(S)=0 h k ( S ) = 0
Several tests and the expected lifetime
Replacing tests one at a time requires a bound for arbitrary residual sets: conditioning on the other clauses need not leave a set with any special description. The sequential conditioning follows the replacement argument of Carenini [5 ] ; the uniform additive block estimate in Lemma 2.1 takes the place of the cutoff-dependent comparison of single-clause killing probabilities in [5 ] ; the exceptional case b = k − 1 b=k-1 b = k − 1 h k h_k h k h r h_r h r
Lemma 2.2 (Sequential replacement). For integers k ≥ 3 k \ge3 k ≥ 3 u ≥ k u \ge k u ≥ k S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u d , g ≥ 1 d,g \ge1 d , g ≥ 1
R d g ( S ) ≥ q d ( S ) − d K k g − ( k − 1 ) . R_{dg}(S) \ge q_d(S)-dK_k g^{-(k-1)}. R d g ( S ) ≥ q d ( S ) − d K k g − ( k − 1 ) . Proof. Choose independent proper r r r Q 1 , … , Q d Q_1,\ldots,Q_d Q 1 , … , Q d G 1 , … , G d G_1,\ldots,G_d G 1 , … , G d g g g k k k p j p_j p j G 1 , … , G j , Q j + 1 , … , Q d G_1,\ldots,G_j,Q_{j+1},\ldots,Q_d G 1 , … , G j , Q j + 1 , … , Q d S S S 0 ≤ j ≤ d 0 \le j \le d 0 ≤ j ≤ d
For the replacement at index j j j G 1 , … , G j − 1 , Q j + 1 , … , Q d G_1,\ldots,G_{j-1},Q_{j+1},\ldots,Q_d G 1 , … , G j − 1 , Q j + 1 , … , Q d S ′ S' S ′ S S S Q j Q_j Q j G j G_j G j q 1 ( S ′ ) q_1(S') q 1 ( S ′ ) R g ( S ′ ) R_g(S') R g ( S ′ ) S ′ = ∅ S'=\varnothing S ′ = ∅ p j ≥ p j − 1 − K k g − r p_j \ge p_{j-1}-K_k g^{-r} p j ≥ p j − 1 − K k g − r j = 1 j=1 j = 1 d d d p 0 = q d ( S ) p_0=q_d(S) p 0 = q d ( S ) p d = R d g ( S ) p_d=R_{dg}(S) p d = R d g ( S )
Proposition 2.3 (Lifetime from shorter-clause killing). For an integer k ≥ 3 k \ge3 k ≥ 3
β = k k − 1 , K k = ( 2 k ( k − 1 ) ) k − 1 , C k = 4 ( 2 K k ) 1 / ( k − 1 ) . \beta=\frac{k}{k-1}, \qquad K_k=\left(2^k(k-1)\right)^{k-1}, \qquad C_k=4(2K_k)^{1/(k-1)}. β = k − 1 k , K k = ( 2 k ( k − 1 ) ) k − 1 , C k = 4 ( 2 K k ) 1/ ( k − 1 ) . For every integer u ≥ k u \ge k u ≥ k S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u d ≥ 1 d \ge1 d ≥ 1
τ k ( S ) q d ( S ) β ≤ C k d β . (5) \tau_k(S)q_d(S)^\beta\le C_k d^\beta. \tag*{(5)} τ k ( S ) q d ( S ) β ≤ C k d β . (5) Consequently, for nonempty S S S 0 < a ≤ q d ( S ) 0<a\le q_d(S) 0 < a ≤ q d ( S )
τ k ( S ) ≤ C k d β a − β . \tau_k(S) \le C_k d^\beta a^{-\beta}. τ k ( S ) ≤ C k d β a − β . There is no upper restriction on d d d
Proof. For the empty set the lifetime is zero. If S ≠ ∅ S\ne\varnothing S = ∅ q d ( S ) = 0 q_d(S)=0 q d ( S ) = 0 (5) is zero, since the lifetime is finite. Otherwise put q = q d ( S ) > 0 q=q_d(S)>0 q = q d ( S ) > 0
g = ⌈ ( 2 K k d q ) 1 / ( k − 1 ) ⌉ . g=\left\lceil\left(\frac{2K_kd}{q}\right)^{1/(k-1)}\right\rceil. g = ⌈ ( q 2 K k d ) 1/ ( k − 1 ) ⌉ . Sequential replacement gives R d g ( S ) ≥ q / 2 R_{dg}(S)\ge q/2 R d g ( S ) ≥ q /2 k k k d g dg d g original set S S S q / 2 q/2 q /2 2 / q 2/q 2/ q S S S
τ k ( S ) ≤ 2 d g q . \tau_k(S)\le\frac{2dg}{q}. τ k ( S ) ≤ q 2 d g . The quantity inside the ceiling is at least one, so g g g
τ k ( S ) ≤ 4 ( 2 K k ) 1 / ( k − 1 ) ( d q ) 1 + 1 / ( k − 1 ) = C k d β q − β . \tau_k(S) \le4(2K_k)^{1/(k-1)}\left(\frac{d}{q}\right)^{1+1/(k-1)} = C_k d^\beta q^{-\beta}. τ k ( S ) ≤ 4 ( 2 K k ) 1/ ( k − 1 ) ( q d ) 1 + 1/ ( k − 1 ) = C k d β q − β . This proves the product bound and then the stated level bound.
These inequalities also hold conditionally for a set S S S S S S
Clause omission and root tests
We now turn the lifetime estimate into a bound for the effect of deleting one clause. Its variables provide tests of the assignments that remain after deletion. We expose the incidence pattern through the whole cap, so that the number of tests is known, while keeping both their contents and the future ordinary clauses independent. The tests bound the probability of a deletion event; the ordinary clauses bound its remaining duration.
Fix an integer k ≥ 3 k \ge3 k ≥ 3 B > 0 B > 0 B > 0 n ≥ 2 k n \ge2k n ≥ 2 k L = ⌊ B n ⌋ L = \lfloor Bn\rfloor L = ⌊ B n ⌋ L ≥ 1 L \ge1 L ≥ 1 C 1 , C 2 , … C_1,C_2,\ldots C 1 , C 2 , … k k k n n n H H H T = min { H , L } T = \min\{H,L\} T = min { H , L } 1 ≤ i ≤ L 1 \le i \le L 1 ≤ i ≤ L
B m ( i ) = ⋀ 1 ≤ j ≤ m j ≠ i C j , T ( i ) = min { inf { m ≥ 0 : B m ( i ) ∉ S A T } , L } , D i = T ( i ) − T . B_m^{(i)} = \bigwedge_{\substack{1 \le j \le m\\j\ne i}} C_j,\qquad
T^{(i)} = \min\left\{\inf\{m \ge0 : B_m^{(i)} \notin\mathrm{SAT}\},L\right\},\qquad
D_i = T^{(i)} - T. B m ( i ) = 1 ≤ j ≤ m j = i ⋀ C j , T ( i ) = min { inf { m ≥ 0 : B m ( i ) ∈ / SAT } , L } , D i = T ( i ) − T . The infimum is over integers and inf ∅ = ∞ \inf\varnothing= \infty inf ∅ = ∞ C i C_i C i D i ≥ 0 D_i \ge0 D i ≥ 0 T ( i ) T^{(i)} T ( i ) L L L C i C_i C i
Lemma 3.1 (Coordinate omission). For the independent clause process above,
Var ( T ) ≤ ∑ i = 1 L E D i 2 . (6) \operatorname{Var}(T) \le\sum_{i=1}^{L} \mathbb{E}D_i^2. \tag*{(6)} Var ( T ) ≤ i = 1 ∑ L E D i 2 . (6) Proof. This is the coordinate-omission form of the Efron–Stein method [8 ] , recorded in [4 ] , equation (3.6). Here is a direct martingale proof. Let H j = σ ( C 1 , … , C j ) \mathcal{H}_j = \sigma(C_1,\ldots,C_j) H j = σ ( C 1 , … , C j ) H 0 \mathcal{H}_0 H 0
M i = E [ T ∣ H i ] − E [ T ∣ H i − 1 ] . M_i = \mathbb{E}[T \mid\mathcal{H}_i] - \mathbb{E}[T \mid\mathcal{H}_{i-1}]. M i = E [ T ∣ H i ] − E [ T ∣ H i − 1 ] . Since T ( i ) T^{(i)} T ( i ) C i C_i C i E [ T ( i ) ∣ H i ] = E [ T ( i ) ∣ H i − 1 ] \mathbb{E}[T^{(i)} \mid\mathcal{H}_i] = \mathbb{E}[T^{(i)} \mid\mathcal{H}_{i-1}] E [ T ( i ) ∣ H i ] = E [ T ( i ) ∣ H i − 1 ] X i = T − T ( i ) X_i = T - T^{(i)} X i = T − T ( i )
M i = E [ X i ∣ H i ] − E [ X i ∣ H i − 1 ] . M_i = \mathbb{E}[X_i \mid\mathcal{H}_i] - \mathbb{E}[X_i \mid\mathcal{H}_{i-1}]. M i = E [ X i ∣ H i ] − E [ X i ∣ H i − 1 ] . The tower property gives
E M i 2 = E ( E [ X i ∣ H i ] ) 2 − E ( E [ X i ∣ H i − 1 ] ) 2 ≤ E X i 2 = E D i 2 , \mathbb{E}M_i^2 = \mathbb{E}\left(\mathbb{E}[X_i \mid\mathcal{H}_i]\right)^2 - \mathbb{E}\left(\mathbb{E}[X_i \mid\mathcal{H}_{i-1}]\right)^2 \le\mathbb{E}X_i^2 = \mathbb{E}D_i^2, E M i 2 = E ( E [ X i ∣ H i ] ) 2 − E ( E [ X i ∣ H i − 1 ] ) 2 ≤ E X i 2 = E D i 2 , where the inequality uses conditional Jensen. The martingale differences are orthogonal and T T T H L \mathcal{H}_L H L
What the two filtrations reveal
Fix i i i C i C_i C i R R R k k k t ∈ { 0 , 1 } R t \in\{0,1\}^{R} t ∈ { 0 , 1 } R C i C_i C i u = n − k ≥ k u=n-k \ge k u = n − k ≥ k B m = B m ( i ) B_m=B_m^{(i)} B m = B m ( i )
For i ≤ m ≤ L i \le m \le L i ≤ m ≤ L
A m = { B m ∈ S A T , B m ∧ C i ∉ S A T } = { T ≤ m < T ( i ) } . (7) A_m=\{B_m\in\mathrm{SAT},\ B_m\wedge C_i\notin\mathrm{SAT}\}=\{T\le m<T^{(i)}\}. \tag*{(7)} A m = { B m ∈ SAT , B m ∧ C i ∈ / SAT } = { T ≤ m < T ( i ) } . (7) On this event every solution of B m B_m B m t t t i i i
D i = ∑ m = i L − 1 1 A m . (8) D_i=\sum_{m=i}^{L-1}\mathbf{1}_{A_m}. \tag*{(8)} D i = m = i ∑ L − 1 1 A m . (8) In particular D L = 0 D_L=0 D L = 0 L − 1 L-1 L − 1 L L L
For i ≤ m ≤ L i \le m \le L i ≤ m ≤ L S m ⊆ { 0 , 1 } u S_m\subseteq\{0,1\}^{u} S m ⊆ { 0 , 1 } u B m B_m B m t t t m m m m < L m<L m < L A m A_m A m S m S_m S m
The root type of a clause records the subset of its variables in R R R ordinary if that subset is empty. It is a test clause if the subset contains exactly one root and its literal is true at t t t O O O Q Q Q { 1 , … , L } ∖ { i } \{1,\ldots,L\}\setminus\{i\} { 1 , … , L } ∖ { i }
Reveal the root type at every such index through L L L { 1 , … , L } ∖ ( { i } ∪ O ∪ Q ) \{1,\ldots,L\}\setminus(\{i\}\cup O\cup Q) { 1 , … , L } ∖ ({ i } ∪ O ∪ Q ) E \mathcal{E} E O O O Q Q Q
Z = # { j ≤ L : j ≠ i , C j meets R } , V = # { j ≤ L : j ≠ i , C j meets at least two roots } , d = max { 1 , Z } \begin{aligned}
Z&=\#\{j\le L:j\ne i,\ C_j\text{ meets }R\},\\
V&=\#\{j\le L:j\ne i,\ C_j\text{ meets at least two roots}\},\qquad d=\max\{1,Z\}
\end{aligned} Z V = # { j ≤ L : j = i , C j meets R } , = # { j ≤ L : j = i , C j meets at least two roots } , d = max { 1 , Z } are E \mathcal{E} E V V V collision . The ordinary clauses and the nonroot parts of test clauses have not yet been revealed.
Lemma 3.2 (Conditional product law). Conditional on E \mathcal{E} E O O O k k k u u u Q Q Q ( k − 1 ) (k-1) ( k − 1 )
Proof. For a prescribed root type with h h h 2 k − h ( u k − h ) 2^{k-h}\binom{u}{k-h} 2 k − h ( k − h u ) k k k O O O Q Q Q O ∪ Q O\cup Q O ∪ Q k k k O O O k − 1 k-1 k − 1 Q Q Q □ \square □
A test clause is already true under t t t S m S_m S m S m S_m S m
G m = σ ( E , C j : j ∈ O , j ≤ m ) . \mathcal{G}_m=\sigma(\mathcal{E},C_j:j\in O,\ j\le m). G m = σ ( E , C j : j ∈ O , j ≤ m ) . We will bound the probability of A m A_m A m S m S_m S m A m A_m A m A m A_m A m
F m ∗ = σ ( G m , nonroot parts of C j : j ∈ Q , j ≤ m ) . \mathcal{F}^{*}_{m}=\sigma(\mathcal{G}_{m},\ \text{nonroot parts of }C_j:j\in Q,\ j\le m). F m ∗ = σ ( G m , nonroot parts of C j : j ∈ Q , j ≤ m ) . The full baseline prefix B m B_m B m A m A_m A m F m ∗ \mathcal{F}^{*}_{m} F m ∗ G m \mathcal{G}_m G m k k k
Flipping a root gives an independent test
Recall that q d ( S ) q_d(S) q d ( S ) d d d ( k − 1 ) (k-1) ( k − 1 ) S S S d = max { 1 , Z } d=\max\{1,Z\} d = max { 1 , Z } E \mathcal{E} E
β = k k − 1 , q m = q d ( S m ) . \beta=\frac{k}{k-1},\qquad q_m=q_d(S_m). β = k − 1 k , q m = q d ( S m ) . For j ∈ R j\in R j ∈ R I j , m I_{j,m} I j , m m m m j j j s j , m = ∣ I j , m ∣ s_{j,m}=|I_{j,m}| s j , m = ∣ I j , m ∣ s j , m ≤ Z ≤ d s_{j,m}\le Z\le d s j , m ≤ Z ≤ d J m ⊆ R J_m\subseteq R J m ⊆ R j j j m m m t t t j j j
∣ J m ∣ ≥ k − V . |J_m|\ge k-V. ∣ J m ∣ ≥ k − V . The index sets and counts in this paragraph are E \mathcal{E} E
Lemma 3.3 (Root-flip tests). For i ≤ m < L i\le m<L i ≤ m < L { ∣ J m ∣ ≥ 1 } \{|J_m|\ge1\} { ∣ J m ∣ ≥ 1 }
P ( A m ∣ G m ) ≤ 1 { S m ≠ ∅ } q m ∣ J m ∣ . (9) \mathbb{P}(A_m\mid\mathcal{G}_m)\le\mathbf{1}_{\{S_m\ne\varnothing\}}q_m^{|J_m|}. \tag*{(9)} P ( A m ∣ G m ) ≤ 1 { S m = ∅ } q m ∣ J m ∣ . (9) Proof. Suppose A m A_m A m j ∈ J m j\in J_m j ∈ J m I j , m I_{j,m} I j , m S m S_m S m x ∈ S m x\in S_m x ∈ S m x x x t t t j j j B m B_m B m
A clause with no true root literal under t t t ( t , x ) (t,x) ( t , x ) B m B_m B m j j j t t t j ∈ J m j\in J_m j ∈ J m I j , m I_{j,m} I j , m x x x B m B_m B m t t t A m A_m A m
Conditional on G m \mathcal{G}_m G m ( k − 1 ) (k-1) ( k − 1 ) S m S_m S m s j , m ≤ d s_{j,m}\le d s j , m ≤ d q s j , m ( S m ) ≤ q d ( S m ) q_{s_{j,m}}(S_m)\le q_d(S_m) q s j , m ( S m ) ≤ q d ( S m ) s j , m = 0 s_{j,m}=0 s j , m = 0 J m J_m J m q m ∣ J m ∣ q_m^{|J_m|} q m ∣ J m ∣ A m A_m A m S m ≠ ∅ S_m\ne\varnothing S m = ∅ □ \square □
The proof has kept the actual incidence count d d d
From ordinary clauses to chronological duration
For this comparison, keep the actual schedule and ordinary clauses through L L L L L L k k k u u u
For i ≤ m < L i \le m < L i ≤ m < L S m ≠ ∅ S_m \ne\varnothing S m = ∅ K m K_m K m m m m S m S_m S m U m U_m U m m m m K m = U m = 0 K_m = U_m = 0 K m = U m = 0 S m = ∅ S_m = \varnothing S m = ∅
E [ K m ∣ F m ∗ ] = E [ K m ∣ G m ] = τ k ( S m ) . (10) \mathbb{E}[K_m \mid\mathcal{F}_m^*] = \mathbb{E}[K_m \mid\mathcal{G}_m] = \tau_k(S_m). \tag*{(10)} E [ K m ∣ F m ∗ ] = E [ K m ∣ G m ] = τ k ( S m ) . (10) There are at most Z Z Z m m m L L L i i i m m m
U m ≤ K m + Z , E [ U m ∣ F m ∗ ] ≤ τ k ( S m ) + Z , E [ U m ∣ G m ] ≤ τ k ( S m ) + Z . (11) U_m \le K_m + Z,\qquad\mathbb{E}[U_m \mid\mathcal{F}_m^*] \le\tau_k(S_m) + Z,\qquad\mathbb{E}[U_m \mid\mathcal{G}_m] \le\tau_k(S_m) + Z. \tag*{(11)} U m ≤ K m + Z , E [ U m ∣ F m ∗ ] ≤ τ k ( S m ) + Z , E [ U m ∣ G m ] ≤ τ k ( S m ) + Z . (11) The continuation makes these statements valid even when no pre-cap ordinary clause completes the kill.
Lemma 3.4 (Weighted deletion delay). Let
W m = min { L , τ k ( S m ) + Z } . W_m = \min\{L,\tau_k(S_m) + Z\}. W m = min { L , τ k ( S m ) + Z } . This is G m \mathcal{G}_m G m i ≤ m < L i \le m < L i ≤ m < L A m A_m A m
E [ ∑ ℓ = m + 1 L − 1 1 A ℓ ∣ F m ∗ ] ≤ W m . (12) \mathbb{E}\left[\left.\sum_{\ell=m+1}^{L-1}\mathbf{1}_{A_\ell}\right|\mathcal{F}_m^*\right] \le W_m. \tag*{(12)} E [ ℓ = m + 1 ∑ L − 1 1 A ℓ F m ∗ ] ≤ W m . (12) Consequently
E [ D i 2 ∣ E ] ≤ 3 ∑ m = i L − 1 E [ 1 A m W m ∣ E ] . (13) \mathbb{E}[D_i^2 \mid\mathcal{E}] \le3\sum_{m=i}^{L-1}\mathbb{E}[\mathbf{1}_{A_m}W_m \mid\mathcal{E}]. \tag*{(13)} E [ D i 2 ∣ E ] ≤ 3 m = i ∑ L − 1 E [ 1 A m W m ∣ E ] . (13) Proof. On A m A_m A m B ℓ B_\ell B ℓ t t t S m S_m S m L L L U m U_m U m L L L (11) gives (12) .
On A m A_m A m S m S_m S m τ k ( S m ) ≥ 1 \tau_k(S_m) \ge1 τ k ( S m ) ≥ 1 W m ≥ 1 W_m \ge1 W m ≥ 1 (8) . For each cross term condition on the earlier F m ∗ \mathcal{F}_m^* F m ∗ A m A_m A m
E [ D i 2 ∣ E ] = ∑ m = i L − 1 E [ 1 A m ∣ E ] + 2 ∑ m = i L − 1 E [ 1 A m E [ ∑ ℓ = m + 1 L − 1 1 A ℓ ∣ F m ∗ ] | E ] ≤ ∑ m = i L − 1 E [ 1 A m ( 1 + 2 W m ) ∣ E ] ≤ 3 ∑ m = i L − 1 E [ 1 A m W m ∣ E ] . \begin{aligned}
\mathbb{E}[D_i^2 \mid\mathcal{E}]
&= \sum_{m=i}^{L-1}\mathbb{E}[\mathbf{1}_{A_m}\mid\mathcal{E}]\\
&\quad+ 2\sum_{m=i}^{L-1}\mathbb{E}\left[\mathbf{1}_{A_m}\mathbb{E}\left[\left.\sum_{\ell=m+1}^{L-1}\mathbf{1}_{A_\ell}\right|\mathcal{F}_m^*\right]\middle|\mathcal{E}\right]\\
&\le\sum_{m=i}^{L-1}\mathbb{E}[\mathbf{1}_{A_m}(1+2W_m)\mid\mathcal{E}]\\
&\le3\sum_{m=i}^{L-1}\mathbb{E}[\mathbf{1}_{A_m}W_m\mid\mathcal{E}].
\end{aligned} E [ D i 2 ∣ E ] = m = i ∑ L − 1 E [ 1 A m ∣ E ] + 2 m = i ∑ L − 1 E [ 1 A m E [ ℓ = m + 1 ∑ L − 1 1 A ℓ F m ∗ ] E ] ≤ m = i ∑ L − 1 E [ 1 A m ( 1 + 2 W m ) ∣ E ] ≤ 3 m = i ∑ L − 1 E [ 1 A m W m ∣ E ] . Both the root-test probability and the remaining duration are now controlled by the same set S m S_m S m q d ( S m ) q_d(S_m) q d ( S m )
Occupation and incidence moments
Keep the deleted index i i i C i C_i C i E \mathcal{E} E q m = q d ( S m ) q_m=q_d(S_m) q m = q d ( S m )
In this section C k C_k C k k k k β = k / ( k − 1 ) \beta=k/(k-1) β = k / ( k − 1 ) d = max { 1 , Z } d=\max\{1,Z\} d = max { 1 , Z } W m = min { L , τ k ( S m ) + Z } W_m=\min\{L,\tau_k(S_m)+Z\} W m = min { L , τ k ( S m ) + Z } S m ≠ ∅ S_m\ne\varnothing S m = ∅
W m q m β ≤ C k d β . W_m q_m^\beta\le C_k d^\beta. W m q m β ≤ C k d β . Indeed, Proposition 2.3 bounds τ k ( S m ) q m β \tau_k(S_m)q_m^\beta τ k ( S m ) q m β d β d^\beta d β
Z q m β ≤ Z ≤ d ≤ d β . Zq_m^\beta\le Z\le d\le d^\beta. Z q m β ≤ Z ≤ d ≤ d β . The product bound remains valid when q m = 0 q_m=0 q m = 0
Time spent above a level
Lemma 4.1 (Conditional occupation). There is a constant C k ≥ 1 C_k\ge1 C k ≥ 1 0 < a ≤ 1 0<a\le1 0 < a ≤ 1
∑ m = i L − 1 P ( S m ≠ ∅ , q m ≥ a ∣ E ) ≤ min { L , C k d β a − β } . (14) \sum_{m=i}^{L-1}\mathbb{P}(S_m\ne\varnothing,\ q_m\ge a\mid\mathcal{E})\le\min\{L,C_kd^\beta a^{-\beta}\}. \tag*{(14)} m = i ∑ L − 1 P ( S m = ∅ , q m ≥ a ∣ E ) ≤ min { L , C k d β a − β } . (14) Proof. Define
N a = ∑ m = i L − 1 1 { S m ≠ ∅ , q m ≥ a } , N_a=\sum_{m=i}^{L-1}\mathbf{1}_{\{S_m\ne\varnothing,\ q_m\ge a\}}, N a = m = i ∑ L − 1 1 { S m = ∅ , q m ≥ a } , and let σ a \sigma_a σ a N a N_a N a ∞ \infty ∞ d d d E \mathcal{E} E S m S_m S m G m \mathcal{G}_m G m { σ a = m } ∈ G m \{\sigma_a=m\}\in\mathcal{G}_m { σ a = m } ∈ G m
On { σ a = m } \{\sigma_a=m\} { σ a = m } m m m U m U_m U m S m S_m S m m + U m m+U_m m + U m L L L S ℓ S_\ell S ℓ S m S_m S m m , … , m + U m − 1 m,\ldots,m+U_m-1 m , … , m + U m − 1 L L L
N a ≤ U m on { σ a = m } . N_a\le U_m\quad\text{on }\{\sigma_a=m\}. N a ≤ U m on { σ a = m } . The first eligible index is included in these U m U_m U m
On { σ a = m } \{\sigma_a=m\} { σ a = m } (11) give
E [ U m ∣ G m ] ≤ τ k ( S m ) + Z ≤ C k d β a − β , \mathbb{E}[U_m\mid\mathcal{G}_m]\le\tau_k(S_m)+Z\le C_kd^\beta a^{-\beta}, E [ U m ∣ G m ] ≤ τ k ( S m ) + Z ≤ C k d β a − β , after increasing C k C_k C k q m ≥ a q_m \ge a q m ≥ a Z ≤ d ≤ d β a − β Z \le d \le d^\beta a^{-\beta} Z ≤ d ≤ d β a − β
E [ N a ∣ E ] ≤ ∑ m = i L − 1 E [ 1 { σ a = m } E [ U m ∣ G m ] ∣ E ] ≤ C k d β a − β ∑ m = i L − 1 P ( σ a = m ∣ E ) ≤ C k d β a − β . \begin{aligned}
\mathbb{E}[N_a \mid\mathcal{E}] \le\sum_{m=i}^{L-1} \mathbb{E}\left[\mathbf{1}_{\{\sigma_a=m\}}\mathbb{E}[U_m \mid\mathcal{G}_m] \mid\mathcal{E}\right] \\
&\le C_k d^\beta a^{-\beta}\sum_{m=i}^{L-1}\mathbb{P}(\sigma_a=m\mid\mathcal{E}) \le C_k d^\beta a^{-\beta}.
\end{aligned} E [ N a ∣ E ] ≤ m = i ∑ L − 1 E [ 1 { σ a = m } E [ U m ∣ G m ] ∣ E ] ≤ C k d β a − β m = i ∑ L − 1 P ( σ a = m ∣ E ) ≤ C k d β a − β . Also N a ≤ L N_a \le L N a ≤ L
Only the first visit to the level is stopped on. All later eligible indices are charged to the remaining lifetime of the same nested set. This is why the argument needs fresh future ordinary contents under G m \mathcal{G}_m G m E \mathcal{E} E
To apply the occupation bound to the squared deletion delay, first consider an environment with V = 0 V=0 V = 0 k k k q m k q_m^k q m k (13) . On a nonempty S m S_m S m (4.1) gives
W m q m k = ( W m q m β ) q m k − β ≤ C k d β q m k − β . W_m q_m^k=(W_m q_m^\beta)q_m^{k-\beta}\le C_kd^\beta q_m^{k-\beta}. W m q m k = ( W m q m β ) q m k − β ≤ C k d β q m k − β . The remaining occupation sum has exponent
γ = k − β = k ( k − 2 ) k − 1 . \gamma=k-\beta=\frac{k(k-2)}{k-1}. γ = k − β = k − 1 k ( k − 2 ) . The lifetime estimate has controlled the remaining deletion duration; Lemma 4.1 contributes a second lifetime factor a − β a^{-\beta} a − β a a a a γ − β − 1 a^{\gamma-\beta-1} a γ − β − 1 γ − β = k ( k − 3 ) / ( k − 1 ) \gamma-\beta=k(k-3)/(k-1) γ − β = k ( k − 3 ) / ( k − 1 ) k = 3 k=3 k = 3
Lemma 4.2 (Integrated occupation). For L ≥ 1 L\ge1 L ≥ 1
∑ m = i L − 1 E [ 1 { S m ≠ ∅ } q m γ ∣ E ] ≤ { C k d β ( 1 + log L ) , k = 3 , C k d β , k ≥ 4. (15) \sum_{m=i}^{L-1}\mathbb{E}\left[\mathbf{1}_{\{S_m\ne\varnothing\}}q_m^\gamma\mid\mathcal{E}\right]\le
\begin{cases}
C_kd^\beta(1+\log L), & k=3,\\
C_kd^\beta, & k\ge4.
\end{cases} \tag*{(15)} m = i ∑ L − 1 E [ 1 { S m = ∅ } q m γ ∣ E ] ≤ { C k d β ( 1 + log L ) , C k d β , k = 3 , k ≥ 4. (15) Proof. Since 0 ≤ q m ≤ 1 0\le q_m\le1 0 ≤ q m ≤ 1
∑ m = i L − 1 E [ 1 { S m ≠ ∅ } q m γ ∣ E ] = ∫ 0 1 γ a γ − 1 ∑ m = i L − 1 P ( S m ≠ ∅ , q m ≥ a ∣ E ) d a ≤ ∫ 0 1 γ a γ − 1 min { L , A a − β } d a , A = C k d β ≥ 1. (16) \begin{aligned}
\sum_{m=i}^{L-1}\mathbb{E}\left[\mathbf{1}_{\{S_m\ne\varnothing\}}q_m^\gamma\mid\mathcal{E}\right]
=\int_0^1\gamma a^{\gamma-1}\sum_{m=i}^{L-1}\mathbb{P}(S_m\ne\varnothing,\ q_m\ge a\mid\mathcal{E})\,da \\
&\le\int_0^1\gamma a^{\gamma-1}\min\{L,Aa^{-\beta}\}\,da,\qquad A=C_kd^\beta\ge1. \tag*{(16)}
\end{aligned} m = i ∑ L − 1 E [ 1 { S m = ∅ } q m γ ∣ E ] = ∫ 0 1 γ a γ − 1 m = i ∑ L − 1 P ( S m = ∅ , q m ≥ a ∣ E ) d a ≤ ∫ 0 1 γ a γ − 1 min { L , A a − β } d a , A = C k d β ≥ 1. (16) The terms are nonnegative, so the interchange of conditional expectation, the finite sum, and integration is valid.
For k ≥ 4 k\ge4 k ≥ 4 γ > β \gamma>\beta γ > β A a − β Aa^{-\beta} A a − β
∫ 0 1 γ a γ − 1 min { L , A a − β } d a ≤ γ A γ − β . \int_0^1\gamma a^{\gamma-1}\min\{L,Aa^{-\beta}\}\,da\le\frac{\gamma A}{\gamma-\beta}. ∫ 0 1 γ a γ − 1 min { L , A a − β } d a ≤ γ − β γ A . This is a constant times A A A k k k k = 3 k = 3 k = 3 γ = β = 3 / 2 \gamma= \beta= 3/2 γ = β = 3/2 A ≥ L A \ge L A ≥ L L ≤ A L \le A L ≤ A A < L A < L A < L a ∗ = ( A / L ) 1 / β a_* = (A/L)^{1/\beta} a ∗ = ( A / L ) 1/ β L a ∗ β = A L a_*^\beta= A L a ∗ β = A
β A ∫ a ∗ 1 d a a = A log ( L / A ) . \beta A \int_{a_*}^{1} \frac{d a}{a} = A \log(L/A). β A ∫ a ∗ 1 a d a = A log ( L / A ) . Thus the integral is at most A [ 1 + log + ( L / A ) ] ≤ A ( 1 + log L ) A[1 + \log_+(L/A)] \le A(1 + \log L) A [ 1 + log + ( L / A )] ≤ A ( 1 + log L ) log + x = max { log x , 0 } \log_+ x = \max\{\log x, 0\} log + x = max { log x , 0 }
The cost of collisions
The number V V V E \mathcal{E} E k k k
Proposition 4.3 (Conditional squared delay). For L ≥ 1 L \ge1 L ≥ 1
h k ( L ) = { 1 + log L , k = 3 , 1 , k ≥ 4. h_k(L) =
\begin{cases}
1 + \log L, & k = 3,\\
1, & k \ge4.
\end{cases} h k ( L ) = { 1 + log L , 1 , k = 3 , k ≥ 4. Then, almost surely,
E [ D i 2 ∣ E ] ≤ C k d 2 β h k ( L ) 1 { V = 0 } + C k L d β 1 { V = 1 } + L 2 1 { V ≥ 2 } . (17) \mathbb{E}[D_i^2 \mid\mathcal{E}] \le C_k d^{2\beta} h_k(L) 1_{\{V=0\}} + C_k L d^\beta1_{\{V=1\}} + L^2 1_{\{V\ge2\}}. \tag*{(17)} E [ D i 2 ∣ E ] ≤ C k d 2 β h k ( L ) 1 { V = 0 } + C k L d β 1 { V = 1 } + L 2 1 { V ≥ 2 } . (17) Proof. Because W m W_m W m G m \mathcal{G}_m G m 1 ≤ j ≤ k 1 \le j \le k 1 ≤ j ≤ k E \mathcal{E} E { ∣ J m ∣ ≥ j } \{|J_m| \ge j\} { ∣ J m ∣ ≥ j }
E [ 1 A m W m ∣ E ] ≤ E [ 1 { S m ≠ ∅ } W m q m j ∣ E ] . \mathbb{E}[1_{A_m} W_m \mid\mathcal{E}] \le\mathbb{E}[1_{\{S_m \ne\varnothing\}} W_m q_m^j \mid\mathcal{E}]. E [ 1 A m W m ∣ E ] ≤ E [ 1 { S m = ∅ } W m q m j ∣ E ] . Here we used q m ≤ 1 q_m \le1 q m ≤ 1 j j j V = 0 V = 0 V = 0 j = k j = k j = k W m q m k ≤ C k d β q m γ W_m q_m^k \le C_k d^\beta q_m^\gamma W m q m k ≤ C k d β q m γ (13) and applying integrated occupation gives C k d 2 β h k ( L ) C_k d^{2\beta} h_k(L) C k d 2 β h k ( L )
If V = 1 V = 1 V = 1 k − 1 k - 1 k − 1 (3.5) . Since k − 1 ≥ β k - 1 \ge\beta k − 1 ≥ β k ≥ 3 k \ge3 k ≥ 3
1 { S m ≠ ∅ } W m q m k − 1 ≤ C k d β . 1_{\{S_m \ne\varnothing\}} W_m q_m^{k-1} \le C_k d^\beta. 1 { S m = ∅ } W m q m k − 1 ≤ C k d β . Use this bound at each of the at most L L L (13) . It gives C k L d β C_k L d^\beta C k L d β V ≥ 2 V \ge2 V ≥ 2 0 ≤ D i ≤ L 0 \le D_i \le L 0 ≤ D i ≤ L D i 2 ≤ L 2 D_i^2 \le L^2 D i 2 ≤ L 2
The one-collision contribution contains d β d^\beta d β
Joint moments of incidences and collisions
Lemma 4.4 (Weighted root counts). Fix integers k ≥ 3 k \ge3 k ≥ 3 n ≥ 2 k n \ge2k n ≥ 2 k B > 0 B > 0 B > 0 k k k M M M k k k n n n M M M M ≤ B n M \le Bn M ≤ B n Z Z Z V V V d = max { 1 , Z } d = \max\{1,Z\} d = max { 1 , Z } p ≥ 0 p \ge0 p ≥ 0
E d p ≤ C k , B , p . (18) \mathbb{E}d^p \le C_{k,B,p}. \tag*{(18)} E d p ≤ C k , B , p . (18) For every fixed positive integer r r r
E [ d p 1 { V ≥ r } ] ≤ C k , B , p , r n − r . (19) \mathbb{E}[d^{p}\mathbf{1}_{\{V\ge r\}}]\le C_{k,B,p,r}n^{-r}. \tag*{(19)} E [ d p 1 { V ≥ r } ] ≤ C k , B , p , r n − r . (19) Proof. For one clause, let I I I J J J p 1 = P ( I = 1 ) p_1=\mathbb{P}(I=1) p 1 = P ( I = 1 ) p 2 = P ( J = 1 ) p_2=\mathbb{P}(J=1) p 2 = P ( J = 1 )
p 1 ≤ k 2 n , p 2 ≤ ( k 2 ) k ( k − 1 ) n ( n − 1 ) ≤ k 2 ( k − 1 ) 2 n 2 . p_1\le\frac{k^2}{n},\qquad p_2\le\binom{k}{2}\frac{k(k-1)}{n(n-1)}\le\frac{k^2(k-1)^2}{n^2}. p 1 ≤ n k 2 , p 2 ≤ ( 2 k ) n ( n − 1 ) k ( k − 1 ) ≤ n 2 k 2 ( k − 1 ) 2 . Thus Z ∼ Bin ( M , p 1 ) Z\sim\operatorname{Bin}(M,p_1) Z ∼ Bin ( M , p 1 )
E e Z = ( 1 + p 1 ( e − 1 ) ) M ≤ exp ( B k 2 ( e − 1 ) ) . \mathbb{E}e^Z=(1+p_1(e-1))^M\le\exp(Bk^2(e-1)). E e Z = ( 1 + p 1 ( e − 1 ) ) M ≤ exp ( B k 2 ( e − 1 )) . For K p = sup x > 0 max { 1 , x } p e − x < ∞ K_p=\sup_{x>0}\max\{1,x\}^p e^{-x}<\infty K p = sup x > 0 max { 1 , x } p e − x < ∞ d p ≤ K p e Z d^p\le K_p e^Z d p ≤ K p e Z (18) .
For the collision bound, retain the dependence between Z Z Z V V V ( a ) r = a ( a − 1 ) ⋯ ( a − r + 1 ) (a)_r=a(a-1)\cdots(a-r+1) ( a ) r = a ( a − 1 ) ⋯ ( a − r + 1 ) f f f 1 ≤ r ≤ M 1\le r\le M 1 ≤ r ≤ M
E [ f ( Z ) ( V ) r ] = ( M ) r p 2 r E f ( r + X ) , X ∼ Bin ( M − r , p 1 ) . (20) \mathbb{E}[f(Z)(V)_r]=(M)_r p_2^r\mathbb{E}f(r+X),\qquad X\sim\operatorname{Bin}(M-r,p_1). \tag*{(20)} E [ f ( Z ) ( V ) r ] = ( M ) r p 2 r E f ( r + X ) , X ∼ Bin ( M − r , p 1 ) . (20) To prove the identity, expand ( V ) r (V)_r ( V ) r r r r p 2 r p_2^r p 2 r M − r M-r M − r p 1 p_1 p 1
Since 1 { V ≥ r } ≤ ( V ) r / r ! \mathbf{1}_{\{V\ge r\}}\le(V)_r/r! 1 { V ≥ r } ≤ ( V ) r / r ! f ( x ) = max { 1 , x } p f(x)=\max\{1,x\}^p f ( x ) = max { 1 , x } p (20) :
E [ d p 1 { V ≥ r } ] ≤ ( M ) r p 2 r r ! E max { 1 , r + X } p ≤ ( M ) r p 2 r r ! K p e r exp ( B k 2 ( e − 1 ) ) ≤ C k , B , p , r n − r . \begin{aligned}
\mathbb{E}[d^p\mathbf{1}_{\{V\ge r\}}]\le\frac{(M)_r p_2^r}{r!}\mathbb{E}\max\{1,r+X\}^p \\
&\le\frac{(M)_r p_2^r}{r!}K_p e^r\exp(Bk^2(e-1))\le C_{k,B,p,r}n^{-r}.
\end{aligned} E [ d p 1 { V ≥ r } ] ≤ r ! ( M ) r p 2 r E max { 1 , r + X } p ≤ r ! ( M ) r p 2 r K p e r exp ( B k 2 ( e − 1 )) ≤ C k , B , p , r n − r . The last inequality uses M ≤ B n M\le Bn M ≤ B n (4.8) . If r > M r>M r > M M = 0 M=0 M = 0 p = 0 p=0 p = 0
These moments are taken with the deleted clause fixed and the other clauses still random. Once E \mathcal{E} E Z Z Z V V V E \mathcal{E} E
Completing the capped upper bound
Proof of the capped upper bound in Theorem 1.1. Suppose first that n ≥ 2 k n\ge2k n ≥ 2 k L ≥ 1 L\ge1 L ≥ 1 C i C_i C i L − 1 ≤ B n L-1\le Bn L − 1 ≤ B n (17) over E \mathcal{E} E p = 2 β p=2\beta p = 2 β (18) and ( p , r ) = ( β , 1 ) , ( 0 , 2 ) (p,r)=(\beta,1),(0,2) ( p , r ) = ( β , 1 ) , ( 0 , 2 ) (19) , gives
E [ D i 2 ∣ C i ] ≤ C k h k ( L ) E [ d 2 β ∣ C i ] + C k L E [ d β 1 { V = 1 } ∣ C i ] + L 2 P ( V ≥ 2 ∣ C i ) ≤ C k , B h k ( L ) + C k , B L n − 1 + C k , B L 2 n − 2 ≤ C k , B h k ( L ) . \begin{aligned}
\mathbb{E}[D_i^2\mid C_i]\le C_k h_k(L)\mathbb{E}[d^{2\beta}\mid C_i]+C_kL\mathbb{E}[d^\beta\mathbf{1}_{\{V=1\}}\mid C_i]+L^2\mathbb{P}(V\ge2\mid C_i) \\
&\le C_{k,B}h_k(L)+C_{k,B}Ln^{-1}+C_{k,B}L^2n^{-2} \\
&\le C_{k,B}h_k(L).
\end{aligned} E [ D i 2 ∣ C i ] ≤ C k h k ( L ) E [ d 2 β ∣ C i ] + C k L E [ d β 1 { V = 1 } ∣ C i ] + L 2 P ( V ≥ 2 ∣ C i ) ≤ C k , B h k ( L ) + C k , B L n − 1 + C k , B L 2 n − 2 ≤ C k , B h k ( L ) . The constants are uniform in i i i C i C_i C i
Var ( T ) ≤ ∑ i = 1 L E D i 2 ≤ C k , B L h k ( L ) . \operatorname{Var}(T)\le\sum_{i=1}^{L}\mathbb{E}D_i^2\le C_{k,B}Lh_k(L). Var ( T ) ≤ i = 1 ∑ L E D i 2 ≤ C k , B L h k ( L ) . Since L ≤ B n L \le Bn L ≤ B n
C k , B n ℓ k ( n ) , ℓ k ( n ) = { log ( e n ) , k = 3 , 1 , k ≥ 4. C_{k,B}n\ell_k(n), \qquad\ell_k(n)=
\begin{cases}
\log(en), & k=3,\\
1, & k\ge4.
\end{cases} C k , B n ℓ k ( n ) , ℓ k ( n ) = { log ( e n ) , 1 , k = 3 , k ≥ 4. For k = 3 k=3 k = 3 1 + log L ≤ C B log ( e n ) 1+\log L \le C_B\log(en) 1 + log L ≤ C B log ( e n ) L ≥ 1 L\ge1 L ≥ 1 L = 0 L=0 L = 0 k ≤ n < 2 k k\le n<2k k ≤ n < 2 k 0 ≤ T ≤ ⌊ B n ⌋ 0\le T\le\lfloor Bn\rfloor 0 ≤ T ≤ ⌊ B n ⌋ B B B n ≥ k n\ge k n ≥ k
Caps, uncapped times, and finite-size means
The capped upper bound uses only finitely many clause coordinates. We now choose a sufficiently late cap and remove it, compare the first-unsatisfiable and last-satisfiable conventions with their exact endpoint corrections, and identify the limiting normalized means. The lower estimate, which requires a different input, is proved in Section 6.
Exact cap comparisons
Fix k ≥ 3 k\ge3 k ≥ 3 q k = 1 − 2 − k q_k=1-2^{-k} q k = 1 − 2 − k P n ( m ) = P ( H n > m ) P_n(m)=\mathbb{P}(H_n>m) P n ( m ) = P ( H n > m ) F n , m = F m F_{n,m}=F_m F n , m = F m m m m q k m q_k^m q k m
P n ( m ) ≤ min { 1 , 2 n q k m } ( m ∈ Z ≥ 0 ) . (21) P_n(m)\le\min\{1,2^nq_k^m\}\qquad(m\in\mathbb{Z}_{\ge0}). \tag*{(21)} P n ( m ) ≤ min { 1 , 2 n q k m } ( m ∈ Z ≥ 0 ) . (21) In particular, H n H_n H n a ≥ 1 a\ge1 a ≥ 1 b ≥ 0 b\ge0 b ≥ 0
X a = min { H n , a } , V b = min { H n − 1 , b } . X_a=\min\{H_n,a\},\qquad V_b=\min\{H_n-1,b\}. X a = min { H n , a } , V b = min { H n − 1 , b } . These have the exact prefix identities
P n ( m ) = P ( X a > m ) ( 0 ≤ m < a ) , P n ( m ) = P ( V b ≥ m ) ( 0 ≤ m ≤ b ) . (22) P_n(m)=\mathbb{P}(X_a>m)\quad(0\le m<a),\qquad P_n(m)=\mathbb{P}(V_b\ge m)\quad(0\le m\le b). \tag*{(22)} P n ( m ) = P ( X a > m ) ( 0 ≤ m < a ) , P n ( m ) = P ( V b ≥ m ) ( 0 ≤ m ≤ b ) . (22) All clause counts in these identities are integers.
Proposition 5.1 (Finite and infinite cap comparisons). For b ≥ a b\ge a b ≥ a R a , b = V b − X a + 1 R_{a,b}=V_b-X_a+1 R a , b = V b − X a + 1 D a = H n − X a D_a=H_n-X_a D a = H n − X a
R a , b = ∑ m = a b 1 { H n > m } , 0 ≤ R a , b ≤ ( b − a + 1 ) 1 { H n > a } , (23) R_{a,b}=\sum_{m=a}^{b}\mathbf{1}_{\{H_n>m\}},\qquad
0\le R_{a,b}\le(b-a+1)\mathbf{1}_{\{H_n>a\}}, \tag*{(23)} R a , b = m = a ∑ b 1 { H n > m } , 0 ≤ R a , b ≤ ( b − a + 1 ) 1 { H n > a } , (23) D a = ( H n − a ) + . (24) D_a=(H_n-a)_+. \tag*{(24)} D a = ( H n − a ) + . (24) For either Z = R a , b Z=R_{a,b} Z = R a , b Z = D a Z=D_a Z = D a ξ n , a = 2 n q k a \xi_{n,a}=2^nq_k^a ξ n , a = 2 n q k a
E Z ≤ 2 k ξ n , a , E Z 2 ≤ ( 2 2 k + 1 − 2 k ) ξ n , a . (25) \mathbb{E}Z\le2^k\xi_{n,a},\qquad
\mathbb{E}Z^2\le(2^{2k+1}-2^k)\xi_{n,a}. \tag*{(25)} E Z ≤ 2 k ξ n , a , E Z 2 ≤ ( 2 2 k + 1 − 2 k ) ξ n , a . (25) If X = V b X=V_b X = V b X = H n X=H_n X = H n
0 ≤ Var ( X ) − Var ( X a ) ≤ 2 k 1 + q k ξ n , a 1 / 2 , (26) 0\le\sqrt{\operatorname{Var}(X)}-\sqrt{\operatorname{Var}(X_a)}
\le2^k\sqrt{1+q_k}\,\xi_{n,a}^{1/2}, \tag*{(26)} 0 ≤ Var ( X ) − Var ( X a ) ≤ 2 k 1 + q k ξ n , a 1/2 , (26) 0 ≤ Var ( X ) − Var ( X a ) ≤ [ 2 a 2 k + 2 2 k + 1 − 2 k ] ξ n , a . (27) 0\le\operatorname{Var}(X)-\operatorname{Var}(X_a)
\le[2a\,2^k+2^{2k+1}-2^k]\xi_{n,a}. \tag*{(27)} 0 ≤ Var ( X ) − Var ( X a ) ≤ [ 2 a 2 k + 2 2 k + 1 − 2 k ] ξ n , a . (27) The mean identities are E V b = E X a − 1 + E R a , b \mathbb{E}V_b=\mathbb{E}X_a-1+\mathbb{E}R_{a,b} E V b = E X a − 1 + E R a , b E H n = E X a + E D a \mathbb{E}H_n=\mathbb{E}X_a+\mathbb{E}D_a E H n = E X a + E D a
Proof. The finite identity follows by considering H n ≤ a H_n \le a H n ≤ a H n > a H_n > a H n > a R a , b = min { ( H n − a ) + , b − a + 1 } R_{a,b} = \min\{(H_n-a)_+, b-a+1\} R a , b = min {( H n − a ) + , b − a + 1 }
P ( D a > r ) = P n ( a + r ) ≤ ξ n , a q k r . \mathbb{P}(D_a > r) = P_n(a+r) \le\xi_{n,a}q_k^r. P ( D a > r ) = P n ( a + r ) ≤ ξ n , a q k r . The integer tail-sum identities yield
E D a = ∑ r = 0 ∞ P n ( a + r ) ≤ ξ n , a 1 − q k , \mathbb{E}D_a = \sum_{r=0}^{\infty} P_n(a+r) \le\frac{\xi_{n,a}}{1-q_k}, E D a = r = 0 ∑ ∞ P n ( a + r ) ≤ 1 − q k ξ n , a , E D a 2 = ∑ r = 0 ∞ ( 2 r + 1 ) P n ( a + r ) ≤ 1 + q k ( 1 − q k ) 2 ξ n , a . \mathbb{E}D_a^2 = \sum_{r=0}^{\infty} (2r+1)P_n(a+r) \le\frac{1+q_k}{(1-q_k)^2}\xi_{n,a}. E D a 2 = r = 0 ∑ ∞ ( 2 r + 1 ) P n ( a + r ) ≤ ( 1 − q k ) 2 1 + q k ξ n , a . For R a , b R_{a,b} R a , b r = b − a r=b-a r = b − a X a Z = a Z X_aZ=aZ X a Z = a Z
Cov ( X a , Z ) = ( a − E X a ) E Z ≥ 0. \operatorname{Cov}(X_a,Z)=(a-\mathbb{E}X_a)\mathbb{E}Z \ge0. Cov ( X a , Z ) = ( a − E X a ) E Z ≥ 0. The constant shift in the finite-cap identity does not affect variance. Thus
Var ( X ) − Var ( X a ) = 2 ( a − E X a ) E Z + Var ( Z ) ≥ 0. \operatorname{Var}(X)-\operatorname{Var}(X_a)=2(a-\mathbb{E}X_a)\mathbb{E}Z+\operatorname{Var}(Z)\ge0. Var ( X ) − Var ( X a ) = 2 ( a − E X a ) E Z + Var ( Z ) ≥ 0. Using (25) proves (27) . The triangle inequality for centered variables in L 2 L^2 L 2
∣ Var ( X ) − Var ( X a ) ∣ ≤ Var ( Z ) ≤ E Z 2 , \left|\sqrt{\operatorname{Var}(X)}-\sqrt{\operatorname{Var}(X_a)}\right| \le\sqrt{\operatorname{Var}(Z)} \le\sqrt{\mathbb{E}Z^2}, Var ( X ) − Var ( X a ) ≤ Var ( Z ) ≤ E Z 2 , which proves (26) .
Recall the first-moment cap density
U k = log 2 − log q k . (28) U_k=\frac{\log2}{-\log q_k}. \tag*{(28)} U k = − log q k log 2 . (28) For any fixed B > U k B>U_k B > U k ρ k , B = 2 q k B < 1 \rho_{k,B}=2q_k^B<1 ρ k , B = 2 q k B < 1 a = ⌊ B n ⌋ a=\lfloor Bn\rfloor a = ⌊ B n ⌋
ξ n , a = q k ⌊ B n ⌋ − B n ρ k , B n ≤ q k − 1 ρ k , B n . (29) \xi_{n,a}=q_k^{\lfloor Bn\rfloor-Bn}\rho_{k,B}^n\le q_k^{-1}\rho_{k,B}^n. \tag*{(29)} ξ n , a = q k ⌊ B n ⌋ − B n ρ k , B n ≤ q k − 1 ρ k , B n . (29) The factor q k − 1 q_k^{-1} q k − 1 B = U k B=U_k B = U k B = 2 k + 1 B=2^{k+1} B = 2 k + 1 k ≥ 3 k\ge3 k ≥ 3
Corollary 5.2 (Uncapped variance and finite-size concentration). For independent uniform proper clauses with fixed k ≥ 3 k\ge3 k ≥ 3
Var ( H n ) = { O ( n log n ) , k = 3 , O k ( n ) , k ≥ 4. (30) \operatorname{Var}(H_n)=
\begin{cases}
O(n\log n), & k=3,\\
O_k(n), & k\ge4.
\end{cases} \tag*{(30)} Var ( H n ) = { O ( n log n ) , O k ( n ) , k = 3 , k ≥ 4. (30) The same upper bounds hold for the uncapped last satisfiable index H n − 1 H_n-1 H n − 1 B > 0 B>0 B > 0 min { H n − 1 , ⌊ B n ⌋ } \min\{H_n-1,\lfloor Bn\rfloor\} min { H n − 1 , ⌊ B n ⌋} s k ( n ) = n ℓ k ( n ) s_k(n)=\sqrt{n\ell_k(n)} s k ( n ) = n ℓ k ( n ) ℓ k \ell_k ℓ k T n , B T_{n,B} T n , B C C C k k k B B B
P ( ∣ X − E X ∣ ≥ t s k ( n ) ) ≤ C t − 2 ( t > 0 ) (31) \mathbb{P}(|X-\mathbb{E}X|\ge ts_k(n))\le Ct^{-2}\qquad(t>0) \tag*{(31)} P ( ∣ X − E X ∣ ≥ t s k ( n )) ≤ C t − 2 ( t > 0 ) (31) for all sufficiently large n n n
Proof. Choose a fixed B > U k B > U_k B > U k X a = T n , B X_a = T_{n,B} X a = T n , B a = ⌊ B n ⌋ a = \lfloor Bn \rfloor a = ⌊ B n ⌋ (27) and (29) transfer its bound to H n H_n H n O k , B ( n ρ k , B n ) O_{k,B}(n\rho_{k,B}^n) O k , B ( n ρ k , B n ) Y Y Y Y ′ Y' Y ′ f f f
Var ( f ( Y ) ) = 1 2 E ( f ( Y ) − f ( Y ′ ) ) 2 ≤ 1 2 E ( Y − Y ′ ) 2 = Var ( Y ) . \operatorname{Var}(f(Y)) = \frac{1}{2}\mathbb{E}(f(Y)-f(Y'))^2 \le\frac{1}{2}\mathbb{E}(Y-Y')^2 = \operatorname{Var}(Y). Var ( f ( Y )) = 2 1 E ( f ( Y ) − f ( Y ′ ) ) 2 ≤ 2 1 E ( Y − Y ′ ) 2 = Var ( Y ) . Apply this to f ( y ) = min { y , ⌊ B n ⌋ } f(y) = \min\{y,\lfloor Bn \rfloor\} f ( y ) = min { y , ⌊ B n ⌋} Y = H n − 1 Y = H_n - 1 Y = H n − 1 (31) . Increasing the upper-bound constants covers the finitely many remaining n ≥ k n \ge k n ≥ k
The mean correction is more precise than its normalized limiting effect: for a = ⌊ B n ⌋ a = \lfloor Bn \rfloor a = ⌊ B n ⌋ B > U k B > U_k B > U k
0 ≤ E H n − E T n , B n ≤ 2 k q k − 1 n ρ k , B n . (32) 0 \le\frac{\mathbb{E}H_n-\mathbb{E}T_{n,B}}{n} \le\frac{2^k q_k^{-1}}{n}\rho_{k,B}^n. \tag*{(32)} 0 ≤ n E H n − E T n , B ≤ n 2 k q k − 1 ρ k , B n . (32) Theorem 1.1 of [16 ] gives a unique positive finite threshold α k \alpha_k α k
E H n n ⟶ α k , E T n , B n ⟶ α k ( B > U k ) . (33) \frac{\mathbb{E}H_n}{n} \longrightarrow\alpha_k,\qquad\frac{\mathbb{E}T_{n,B}}{n} \longrightarrow\alpha_k \quad(B > U_k). \tag*{(33)} n E H n ⟶ α k , n E T n , B ⟶ α k ( B > U k ) . (33) Here is the explicit expectation argument. Take b = 2 k + 1 n b = 2^{k+1}n b = 2 k + 1 n min { H n − 1 , b } / n → α k \min\{H_n-1,b\}/n \to\alpha_k min { H n − 1 , b } / n → α k α k ≤ U k < 2 k + 1 \alpha_k \le U_k < 2^{k+1} α k ≤ U k < 2 k + 1 X b X_b X b H n H_n H n (32) handles the remaining caps. The same conclusion holds for last-satisfiable caps of density B > U k B > U_k B > U k E H n − α k n \mathbb{E}H_n-\alpha_k n E H n − α k n (31) is centered at each finite-size expectation.
Quantile separation and the variance lower bound
The remaining part of Theorem 1.1 is a linear lower bound. We use a width theorem for the proper-clause model and convert it into a second-moment estimate. Keeping the two integer quantiles explicit makes the argument valid when the hitting-time law has atoms.
An elementary sparse-prefix estimate will also supply the positive lower bounds on finite-size means in Appendices B and C. We record it before turning to the quantile argument.
Lemma 6.1 (A sparse satisfiable prefix). For every real 0 < c < e − 2 0 < c < e^{-2} 0 < c < e − 2 k ≥ 3 k \ge3 k ≥ 3 n ≥ k n \ge k n ≥ k j = ⌊ c n ⌋ j = \lfloor cn \rfloor j = ⌊ c n ⌋
1 − P n ( j ) ≤ e c n 2 ∑ t = 1 ∞ t 2 ( e 2 c ) t = O c ( n − 2 ) . 1-P_n(j) \le\frac{ec}{n^2}\sum_{t=1}^{\infty} t^2(e^2c)^t = O_c(n^{-2}). 1 − P n ( j ) ≤ n 2 ec t = 1 ∑ ∞ t 2 ( e 2 c ) t = O c ( n − 2 ) . Proof. Form the bipartite incidence graph between the j j j n n n [9 ] , Section 8. By Hall’s theorem [14 ] , failure of such a matching implies that some set of t t t t + 1 t+1 t + 1 k k k t t t ( t k ) / ( n k ) ≤ ( t / n ) k \binom{t}{k}/\binom{n}{k} \le(t/n)^k ( k t ) / ( k n ) ≤ ( t / n ) k t < k t<k t < k k ≥ 3 k \ge3 k ≥ 3 j ≤ c n j \le cn j ≤ c n ( a b ) ≤ ( e a / b ) b \binom{a}{b} \le(ea/b)^b ( b a ) ≤ ( e a / b ) b
1 − P n ( j ) ≤ ∑ 1 ≤ t ≤ n t + 1 ≤ j ( n t ) ( j t + 1 ) ( t / n ) k ( t + 1 ) ≤ ∑ t = 1 n e c ( e 2 c ) t ( t / n ) t + 2 ≤ e c n 2 ∑ t = 1 ∞ t 2 ( e 2 c ) t . \begin{aligned}
1-P_n(j) \le\sum_{\substack{1\le t\le n\\t+1\le j}} \binom{n}{t}\binom{j}{t+1}(t/n)^{k(t+1)} \\
&\le\sum_{t=1}^{n} ec(e^2c)^t(t/n)^{t+2} \le\frac{ec}{n^2}\sum_{t=1}^{\infty}t^2(e^2c)^t.
\end{aligned} 1 − P n ( j ) ≤ 1 ≤ t ≤ n t + 1 ≤ j ∑ ( t n ) ( t + 1 j ) ( t / n ) k ( t + 1 ) ≤ t = 1 ∑ n ec ( e 2 c ) t ( t / n ) t + 2 ≤ n 2 ec t = 1 ∑ ∞ t 2 ( e 2 c ) t . The final series is finite because e 2 c < 1 e^2c<1 e 2 c < 1
Wilson’s Corollary 4 [18 ] applies to independent uniform proper k k k 3 / 4 3/4 3/4 1 / 4 1/4 1/4 k ≥ 3 k\ge3 k ≥ 3 d k > 0 d_k>0 d k > 0 n k n_k n k n ≥ n k n\ge n_k n ≥ n k
P n ( m 1 ) ≥ 3 4 , P n ( m 2 ) ≤ 1 4 ⟹ m 2 − m 1 ≥ d k n (34) P_n(m_1)\ge\frac{3}{4},\quad P_n(m_2)\le\frac{1}{4}\quad\Longrightarrow\quad m_2-m_1\ge d_k\sqrt{n} \tag*{(34)} P n ( m 1 ) ≥ 4 3 , P n ( m 2 ) ≤ 4 1 ⟹ m 2 − m 1 ≥ d k n (34) The constants may depend on k k k
Proposition 6.2 (Linear variance lower bound). Let L n L_n L n O ( n ) O(n) O ( n ) P n ( L n − 1 ) ≤ 1 / 4 P_n(L_n-1)\le1/4 P n ( L n − 1 ) ≤ 1/4 n n n
Var ( min { H n , L n } ) ≥ c k n \operatorname{Var}(\min\{H_n,L_n\})\ge c_kn Var ( min { H n , L n }) ≥ c k n for all sufficiently large n n n c k > 0 c_k>0 c k > 0 B > U k B>U_k B > U k k ≥ 4 k\ge4 k ≥ 4
Var ( H n ) = Θ k ( n ) , Var ( T n , B ) = Θ k , B ( n ) , Var ( min { H n − 1 , ⌊ B n ⌋ } ) = Θ k , B ( n ) . (35) \operatorname{Var}(H_n)=\Theta_k(n),\qquad\operatorname{Var}(T_{n,B})=\Theta_{k,B}(n),\qquad\operatorname{Var}(\min\{H_n-1,\lfloor Bn\rfloor\})=\Theta_{k,B}(n). \tag*{(35)} Var ( H n ) = Θ k ( n ) , Var ( T n , B ) = Θ k , B ( n ) , Var ( min { H n − 1 , ⌊ B n ⌋}) = Θ k , B ( n ) . (35) For k = 3 k=3 k = 3 n n n n log n n\log n n log n
Proof. Write X = min { H n , L n } X=\min\{H_n,L_n\} X = min { H n , L n } G ( j ) = P ( X ≤ j ) G(j)=\mathbb{P}(X\le j) G ( j ) = P ( X ≤ j )
a = min { j : G ( j ) ≥ 1 / 4 } , b = min { j : G ( j ) ≥ 3 / 4 } . a=\min\{j:G(j)\ge1/4\},\qquad b=\min\{j:G(j)\ge3/4\}. a = min { j : G ( j ) ≥ 1/4 } , b = min { j : G ( j ) ≥ 3/4 } . The cap hypothesis gives b ≤ L n − 1 b\le L_n-1 b ≤ L n − 1 a − 1 a-1 a − 1 b b b
P n ( a − 1 ) = 1 − G ( a − 1 ) > 3 / 4 , P n ( b ) = 1 − G ( b ) ≤ 1 / 4. P_n(a-1)=1-G(a-1)>3/4,\qquad P_n(b)=1-G(b)\le1/4. P n ( a − 1 ) = 1 − G ( a − 1 ) > 3/4 , P n ( b ) = 1 − G ( b ) ≤ 1/4. Applying (34) to the endpoint probabilities above gives b − a ≥ d k n − 1 b-a\ge d_k\sqrt{n}-1 b − a ≥ d k n − 1
P ( X ≤ a ) ≥ 1 4 , P ( X ≥ b ) = 1 − G ( b − 1 ) > 1 4 . \mathbb{P}(X\le a)\ge\frac{1}{4},\qquad\mathbb{P}(X\ge b)=1-G(b-1)>\frac{1}{4}. P ( X ≤ a ) ≥ 4 1 , P ( X ≥ b ) = 1 − G ( b − 1 ) > 4 1 . For an independent copy X ′ X' X ′ { X ≤ a , X ′ ≥ b } \{X\le a,X'\ge b\} { X ≤ a , X ′ ≥ b } { X ′ ≤ a , X ≥ b } \{X'\le a,X\ge b\} { X ′ ≤ a , X ≥ b } 1 / 16 1/16 1/16 b > a b>a b > a
Var ( X ) = 1 2 E ( X − X ′ ) 2 ≥ ( b − a ) 2 16 ≥ d k 2 64 n \operatorname{Var}(X)=\frac{1}{2}\mathbb{E}(X-X')^2\ge\frac{(b-a)^2}{16}\ge\frac{d_k^2}{64}n Var ( X ) = 2 1 E ( X − X ′ ) 2 ≥ 16 ( b − a ) 2 ≥ 64 d k 2 n for sufficiently large n n n L n = ⌊ B n ⌋ L_n = \lfloor Bn\rfloor L n = ⌊ B n ⌋ B > U k B > U_k B > U k
P n ( L n − 1 ) ≤ q k − 2 ρ k , B n = o ( 1 ) P_n(L_n-1) \le q_k^{-2}\rho_{k,B}^n = o(1) P n ( L n − 1 ) ≤ q k − 2 ρ k , B n = o ( 1 ) by (5.1). The capped upper bounds proved above give the matching upper bounds. The exact identity
min { H n − 1 , L n } = min { H n , L n + 1 } − 1 \min\{H_n-1,L_n\}=\min\{H_n,L_n+1\}-1 min { H n − 1 , L n } = min { H n , L n + 1 } − 1 proves the lower bound for last satisfiability, since its required condition is P n ( L n ) ≤ 1 / 4 P_n(L_n)\le1/4 P n ( L n ) ≤ 1/4 Var ( H n ) ≥ Var ( min { H n , L n } ) \operatorname{Var}(H_n)\ge\operatorname{Var}(\min\{H_n,L_n\}) Var ( H n ) ≥ Var ( min { H n , L n })
Three-clause cap and Poisson refinements
At clause size three, the cap identities connect the first-unsatisfiable statistic used in the variance proof to the last-satisfiable statistics used in the threshold companion [16 ] . We give their exact constants, then transfer concentration to the companion’s auxiliary Poisson clause law, which allows repeated variables within a clause. The Poisson density interval and the cap on the hitting time play different roles and can be chosen independently. For k = 3 k=3 k = 3
T = min { H n , 10 n } , W = min { H n − 1 , 10 n } , V = min { H n − 1 , 16 n } . T=\min\{H_n,10n\},\qquad W=\min\{H_n-1,10n\},\qquad V=\min\{H_n-1,16n\}. T = min { H n , 10 n } , W = min { H n − 1 , 10 n } , V = min { H n − 1 , 16 n } . With ρ = 2 ( 7 / 8 ) 10 < 1 \rho=2(7/8)^{10}<1 ρ = 2 ( 7/8 ) 10 < 1
W = T − 1 + 1 { F n , 10 n ∈ S A T } . (36) W=T-1+\mathbf{1}_{\{F_{n,10n}\in\mathrm{SAT}\}}. \tag*{(36)} W = T − 1 + 1 { F n , 10 n ∈ SAT } . (36) V = T − 1 + R , 0 ≤ R ≤ ( 6 n + 1 ) 1 { F n , 10 n ∈ S A T } . (37) V=T-1+R,\qquad0\le R\le(6n+1)\mathbf{1}_{\{F_{n,10n}\in\mathrm{SAT}\}}. \tag*{(37)} V = T − 1 + R , 0 ≤ R ≤ ( 6 n + 1 ) 1 { F n , 10 n ∈ SAT } . (37) Consequently 0 ≤ E V − ( E T − 1 ) ≤ ( 6 n + 1 ) ρ n 0\le\mathbb{E}V-(\mathbb{E}T-1)\le(6n+1)\rho^n 0 ≤ E V − ( E T − 1 ) ≤ ( 6 n + 1 ) ρ n ∣ Var ( V ) − Var ( T ) ∣ ≤ ( 6 n + 1 ) ρ n / 2 \left|\sqrt{\operatorname{Var}(V)}-\sqrt{\operatorname{Var}(T)}\right|\le(6n+1)\rho^{n/2} Var ( V ) − Var ( T ) ≤ ( 6 n + 1 ) ρ n /2
E R ≤ 8 ρ n , E R 2 ≤ 120 ρ n , 0 ≤ Var ( V ) − Var ( T ) ≤ ( 160 n + 120 ) ρ n . \mathbb{E}R\le8\rho^n,\qquad\mathbb{E}R^2\le120\rho^n,\qquad0\le\operatorname{Var}(V)-\operatorname{Var}(T)\le(160n+120)\rho^n. E R ≤ 8 ρ n , E R 2 ≤ 120 ρ n , 0 ≤ Var ( V ) − Var ( T ) ≤ ( 160 n + 120 ) ρ n . The pathwise inequality W ≤ 6 n + 4 n 1 { H n > 6 n } W\le6n+4n\mathbf{1}_{\{H_n>6n\}} W ≤ 6 n + 4 n 1 { H n > 6 n } σ = 2 ( 7 / 8 ) 6 < 1 \sigma=2(7/8)^6<1 σ = 2 ( 7/8 ) 6 < 1
E W n ≤ 6 + 4 σ n = 6 + o ( 1 ) . (38) \frac{\mathbb{E}W}{n}\le6+4\sigma^n=6+o(1). \tag*{(38)} n E W ≤ 6 + 4 σ n = 6 + o ( 1 ) . (38) The survival-sum bound E H n ≤ 6 n + 8 σ n \mathbb{E}H_n\le6n+8\sigma^n E H n ≤ 6 n + 8 σ n 6 + o ( 1 ) 6+o(1) 6 + o ( 1 ) T T T V V V n n n
On the density interval 0 ≤ c ≤ 8 0\le c\le8 0 ≤ c ≤ 8 s n ( c ) s_n(c) s n ( c ) Pois ( c n ) \operatorname{Pois}(cn) Pois ( c n )
ϑ n = ( n ) 3 n 3 = 1 − 3 n + 2 n 2 . \vartheta_n=\frac{(n)_3}{n^3}=1-\frac{3}{n}+\frac{2}{n^2}. ϑ n = n 3 ( n ) 3 = 1 − n 3 + n 2 2 . Poisson thinning gives independent proper and repeated-variable clause collections. The proper count J J J Pois ( c n ϑ n ) \operatorname{Pois}(cn\vartheta_n) Pois ( c n ϑ n )
c n ( 1 − ϑ n ) = c ( 3 − 2 / n ) ≤ 24 ( 0 ≤ c ≤ 8 ) . cn(1-\vartheta_n)=c(3-2/n)\le24 \qquad(0\le c\le8). c n ( 1 − ϑ n ) = c ( 3 − 2/ n ) ≤ 24 ( 0 ≤ c ≤ 8 ) . Requiring no repeated-variable clauses for a lower bound, and deleting them for an upper bound, gives
e − 24 E P n ( J ) ≤ s n ( c ) ≤ E P n ( J ) , c n − 24 ≤ E J ≤ c n , Var ( J ) ≤ 8 n . (39) e^{-24}\mathbb{E}P_n(J)\le s_n(c)\le\mathbb{E}P_n(J),\qquad cn-24\le\mathbb{E}J\le cn,\qquad\operatorname{Var}(J)\le8n. \tag*{(39)} e − 24 E P n ( J ) ≤ s n ( c ) ≤ E P n ( J ) , c n − 24 ≤ E J ≤ c n , Var ( J ) ≤ 8 n . (39) Set ω n = E W / n \omega_n=\mathbb{E}W/n ω n = E W / n P ( ∣ W − n ω n ∣ ≥ n 11 / 12 ) = O ( n − 1 / 6 ) \mathbb{P}(|W-n\omega_n|\ge n^{11/12})=O(n^{-1/6}) P ( ∣ W − n ω n ∣ ≥ n 11/12 ) = O ( n − 1/6 ) J J J (39) therefore yield, uniformly for c ∈ [ 0 , 8 ] c\in[0,8] c ∈ [ 0 , 8 ]
c ≤ ω n − 2 n − 1 / 12 ⟹ s n ( c ) ≥ e − 24 / 2 , (40) c\le\omega_n-2n^{-1/12}\quad\Longrightarrow\quad s_n(c)\ge e^{-24}/2, \tag*{(40)} c ≤ ω n − 2 n − 1/12 ⟹ s n ( c ) ≥ e − 24 /2 , (40) c ≥ ω n + 2 n − 1 / 12 ⟹ s n ( c ) = O ( n − 1 / 6 ) . (41) c\ge\omega_n+2n^{-1/12}\quad\Longrightarrow\quad s_n(c)=O(n^{-1/6}). \tag*{(41)} c ≥ ω n + 2 n − 1/12 ⟹ s n ( c ) = O ( n − 1/6 ) . (41) Indeed, in the lower case E J ≤ n ω n − 2 n 11 / 12 \mathbb{E}J\le n\omega_n-2n^{11/12} E J ≤ n ω n − 2 n 11/12 J ≤ n ω n − n 11 / 12 J\le n\omega_n-n^{11/12} J ≤ n ω n − n 11/12 O ( n − 5 / 6 ) O(n^{-5/6}) O ( n − 5/6 ) E J ≥ n ω n + 2 n 11 / 12 − 24 \mathbb{E}J\ge n\omega_n+2n^{11/12}-24 E J ≥ n ω n + 2 n 11/12 − 24 10 n 10n 10 n ⌈ n ω n + n 11 / 12 ⌉ < 10 n \lceil n\omega_n+n^{11/12}\rceil<10n ⌈ n ω n + n 11/12 ⌉ < 10 n (38) . These statements use the last-SAT cap 10 n 10n 10 n 8 8 8 e − 24 / 2 e^{-24}/2 e − 24 /2 λ \lambda λ D D D [16 ] . Specializing it to k = 3 k=3 k = 3 λ = D = 16 \lambda=D=16 λ = D = 16 V V V E V / n \mathbb{E}V/n E V / n c ∈ [ 0 , 16 ] c\in[0,16] c ∈ [ 0 , 16 ] 48 48 48 e − 48 / 2 e^{-48}/2 e − 48 /2
A Sharpness for arbitrary assignment sets
For each fixed integer k ≥ 3 k\ge3 k ≥ 3 k / ( k − 1 ) k/(k-1) k / ( k − 1 ) k − 1 k-1 k − 1
Write r = k − 1 r=k-1 r = k − 1 s s s u u u s s s q 1 ( S ) q_1(S) q 1 ( S ) r r r S S S R t ( S ) R_t(S) R t ( S ) t t t k k k S S S τ k ( S ) = E H k ( S ) \tau_k(S)=\mathbb{E}H_k(S) τ k ( S ) = E H k ( S ) S S S H k ( S ) H_k(S) H k ( S ) t t t t t t k k k S S S H k ( ∅ ) = 0 H_k(\varnothing)=0 H k ( ∅ ) = 0
For integers u ≥ b ≥ k u\ge b\ge k u ≥ b ≥ k
S u , b = { x ∈ { 0 , 1 } u : x 1 = ⋯ = x b = 0 } . S_{u,b}=\{x\in\{0,1\}^u:x_1=\cdots=x_b=0\}. S u , b = { x ∈ { 0 , 1 } u : x 1 = ⋯ = x b = 0 } . Its first b b b h s ( S u , b ) h_s(S_{u,b}) h s ( S u , b ) s s s (2) reads
h s ( S u , b ) = ( b s ) 2 s ( u s ) ( 1 ≤ s ≤ u ) , q 1 ( S u , b ) = h r ( S u , b ) . (42) h_s(S_{u,b})=\frac{\binom{b}{s}}{2^s\binom{u}{s}}\quad(1\le s\le u),\qquad q_1(S_{u,b})=h_r(S_{u,b}). \tag*{(42)} h s ( S u , b ) = 2 s ( s u ) ( s b ) ( 1 ≤ s ≤ u ) , q 1 ( S u , b ) = h r ( S u , b ) . (42) where ( a ) s = a ( a − 1 ) ⋯ ( a − s + 1 ) (a)_s = a(a-1)\cdots(a-s+1) ( a ) s = a ( a − 1 ) ⋯ ( a − s + 1 )
h k ( S u , b ) q 1 ( S u , b ) = b − r 2 ( u − r ) . \frac{h_k(S_{u,b})}{q_1(S_{u,b})} = \frac{b-r}{2(u-r)}. q 1 ( S u , b ) h k ( S u , b ) = 2 ( u − r ) b − r . For every integer t ≥ 1 t \ge1 t ≥ 1
1 − ( 1 − h k ( S u , b ) ) t ≤ R t ( S u , b ) ≤ t h k ( S u , b ) + ( t 2 ) k 2 u . (43) 1-(1-h_k(S_{u,b}))^t \le R_t(S_{u,b}) \le th_k(S_{u,b})+\binom{t}{2}\frac{k^2}{u}. \tag*{(43)} 1 − ( 1 − h k ( S u , b ) ) t ≤ R t ( S u , b ) ≤ t h k ( S u , b ) + ( 2 t ) u k 2 . (43) The lower bound records the independent chances that a single clause kills the whole subcube. To prove the upper bound, restrict all t t t S u , b S_{u,b} S u , b ( k / u ) 2 (k/u)^2 ( k / u ) 2 u − b u-b u − b k 2 / u k^2/u k 2 / u (43) .
Proposition A.1 (Optimality of the lifetime exponent). Fix an integer k ≥ 3 k \ge3 k ≥ 3 β = k / ( k − 1 ) \beta= k/(k-1) β = k / ( k − 1 ) γ < β \gamma< \beta γ < β D , A > 0 D,A > 0 D , A > 0 u ≥ k u \ge k u ≥ k S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^u S ⊆ { 0 , 1 } u
q 1 ( S ) ≥ A u − ( k − 1 ) , τ k ( S ) > D q 1 ( S ) − γ . q_1(S) \ge Au^{-(k-1)}, \qquad\tau_k(S) > Dq_1(S)^{-\gamma}. q 1 ( S ) ≥ A u − ( k − 1 ) , τ k ( S ) > D q 1 ( S ) − γ . Consequently, the killing-probability exponent β \beta β u − ( k − 1 ) u^{-(k-1)} u − ( k − 1 )
Proof. Let the integer N ≥ 2 N \ge2 N ≥ 2
u = N 2 k + 1 , b = N 2 k , S = S u , b . u=N^{2k+1}, \qquad b=N^{2k}, \qquad S=S_{u,b}. u = N 2 k + 1 , b = N 2 k , S = S u , b . Since k k k b / u = N − 1 b/u=N^{-1} b / u = N − 1 (42) gives
a N : = q 1 ( S ) ∼ 2 − r N − r , h N : = h k ( S ) ∼ 2 − k N − k . a_N := q_1(S) \sim2^{-r}N^{-r}, \qquad h_N := h_k(S) \sim2^{-k}N^{-k}. a N := q 1 ( S ) ∼ 2 − r N − r , h N := h k ( S ) ∼ 2 − k N − k . Choose t N = ⌊ 1 / ( 4 h N ) ⌋ t_N=\lfloor1/(4h_N)\rfloor t N = ⌊ 1/ ( 4 h N )⌋ N N N t N = Θ k ( N k ) t_N=\Theta_k(N^k) t N = Θ k ( N k ) t N t_N t N H k ( S ) > t N H_k(S)>t_N H k ( S ) > t N (43) yields
P ( H k ( S ) > t N ) = 1 − R t N ( S ) ≥ 1 − t N h N − ( t N 2 ) k 2 u ≥ 3 4 − o ( 1 ) . (44) \mathbb{P}(H_k(S)>t_N)=1-R_{t_N}(S)\ge1-t_Nh_N-\binom{t_N}{2}\frac{k^2}{u}\ge\frac{3}{4}-o(1). \tag*{(44)} P ( H k ( S ) > t N ) = 1 − R t N ( S ) ≥ 1 − t N h N − ( 2 t N ) u k 2 ≥ 4 3 − o ( 1 ) . (44) Here t N h N ≤ 1 / 4 t_Nh_N\le1/4 t N h N ≤ 1/4 t N 2 / u = O k ( N − 1 ) t_N^2/u=O_k(N^{-1}) t N 2 / u = O k ( N − 1 )
τ k ( S ) ≥ t N P ( H k ( S ) > t N ) = Ω k ( N k ) . \tau_k(S)\ge t_N\mathbb{P}(H_k(S)>t_N)=\Omega_k(N^k). τ k ( S ) ≥ t N P ( H k ( S ) > t N ) = Ω k ( N k ) . For the reverse bound, let J J J S S S S S S J J J J J J h N > 0 h_N>0 h N > 0
τ k ( S ) ≤ E J = h N − 1 = O k ( N k ) . \tau_k(S)\le\mathbb{E}J=h_N^{-1}=O_k(N^k). τ k ( S ) ≤ E J = h N − 1 = O k ( N k ) . Thus
τ k ( S ) = Θ k ( N k ) = Θ k ( a N − β ) . \tau_k(S) = \Theta_k(N^k) = \Theta_k(a_N^{-\beta}). τ k ( S ) = Θ k ( N k ) = Θ k ( a N − β ) . For each fixed γ < β \gamma< \beta γ < β τ k ( S ) / a N − γ \tau_k(S)/a_N^{-\gamma} τ k ( S ) / a N − γ k − r γ > 0 k-r\gamma> 0 k − r γ > 0
a N u r ∼ 2 − r N 2 k r = 2 − r b r ⟶ ∞ . a_N u^r \sim2^{-r}N^{2kr} = 2^{-r}b^r \longrightarrow\infty. a N u r ∼ 2 − r N 2 k r = 2 − r b r ⟶ ∞. For all sufficiently large N N N D D D A A A u u u
Proposition A.2 (Optimality of the block-error exponent). Fix an integer k ≥ 3 k \ge3 k ≥ 3 g ≥ 2 g \ge2 g ≥ 2 S g ⊆ { 0 , 1 } u g S_g \subseteq\{0,1\}^{u_g} S g ⊆ { 0 , 1 } u g u g ≥ k u_g \ge k u g ≥ k
q 1 ( S g ) − R g ( S g ) ∼ 2 − k g − ( k − 1 ) ( g → ∞ ) . q_1(S_g) - R_g(S_g) \sim2^{-k}g^{-(k-1)}
\qquad(g \to\infty). q 1 ( S g ) − R g ( S g ) ∼ 2 − k g − ( k − 1 ) ( g → ∞ ) . In particular, no error o ( g − ( k − 1 ) ) o(g^{-(k-1)}) o ( g − ( k − 1 ) ) u u u Lemma 2.1.
Proof. For every integer g ≥ 2 g \ge2 g ≥ 2
u g = g k + 2 , b g = g k + 1 , S g = S u g , b g , u_g = g^{k+2}, \qquad b_g = g^{k+1}, \qquad S_g = S_{u_g,b_g}, u g = g k + 2 , b g = g k + 1 , S g = S u g , b g , and abbreviate a g = q 1 ( S g ) a_g = q_1(S_g) a g = q 1 ( S g ) h g = h k ( S g ) h_g = h_k(S_g) h g = h k ( S g ) (42) and (A.2) give
a g ∼ 2 − r g − r , g h g a g = g ( b g − r ) 2 ( u g − r ) ⟶ 1 2 . a_g \sim2^{-r}g^{-r}, \qquad\frac{gh_g}{a_g} = \frac{g(b_g-r)}{2(u_g-r)} \longrightarrow\frac{1}{2}. a g ∼ 2 − r g − r , a g g h g = 2 ( u g − r ) g ( b g − r ) ⟶ 2 1 . The upper bound in (43) , and the two-term inclusion–exclusion lower bound for the independent individual killing events, give
g h g − ( g 2 ) h g 2 ≤ R g ( S g ) ≤ g h g + ( g 2 ) k 2 u g . gh_g-\binom{g}{2}h_g^2 \le R_g(S_g) \le gh_g+\binom{g}{2}\frac{k^2}{u_g}. g h g − ( 2 g ) h g 2 ≤ R g ( S g ) ≤ g h g + ( 2 g ) u g k 2 . The collision error is O k ( g − k ) = o ( a g ) O_k(g^{-k}) = o(a_g) O k ( g − k ) = o ( a g ) h g = Θ k ( g − k ) h_g = \Theta_k(g^{-k}) h g = Θ k ( g − k ) O k ( g − 2 ( k − 1 ) ) = o ( a g ) O_k(g^{-2(k-1)}) = o(a_g) O k ( g − 2 ( k − 1 ) ) = o ( a g )
R g ( S g ) = g h g + o ( a g ) , q 1 ( S g ) − R g ( S g ) = ( 1 2 + o ( 1 ) ) a g ∼ 2 − k g − r . R_g(S_g) = gh_g + o(a_g), \qquad q_1(S_g)-R_g(S_g) = \left(\frac{1}{2}+o(1)\right)a_g \sim2^{-k}g^{-r}. R g ( S g ) = g h g + o ( a g ) , q 1 ( S g ) − R g ( S g ) = ( 2 1 + o ( 1 ) ) a g ∼ 2 − k g − r . This is the stated asymptotic.
These constructions delimit estimates uniform over arbitrary assignment sets. They leave open stronger lifetime estimates for classes of sets with additional structure, and variance arguments using information beyond the killing probability. In particular, they do not show that the logarithm in the three-clause variance upper bound is necessary.
Comparing finite-size centers with proper clauses
The variance estimate controls fluctuations at one size. We now compare the corresponding centers at different sizes, using proper clauses at every step. The comparison keeps the weights of the two variable blocks; this is what makes its error uniform even when one block is much larger than the other. Once these probability comparisons are established, the deterministic balanced-comparison lemma of the threshold companion turns them into convergence. This gives a second route to convergence from a concentration estimate, without using the companion’s limiting-threshold theorem as Section 5 does. The theorem below takes concentration as an input, so it also applies to the independent, weaker variance proof in Appendix C.
Interpolation between a system and independent parts appears in the thermodynamic-limit work of Guerra and Toninelli [13 ] and the diluted-system work of Franz and Leone [10 ] and Franz, Leone, and Toninelli [11 ] . Those works concern free energies under their respective model hypotheses; they provide methodological context for the size comparison. The one-clause interpolation here uses frozen variables, as in the satisfiability interpolation of Bayati, Gamarnik, and Tetali [3 ] , Section 4, Proposition 2. Their clause law samples variable tuples with replacement. Here the clauses have distinct variables, so the exact killing probabilities contain falling factorials. We control the resulting error locally before summing it over the trials.
For fixed k ≥ 3 k \ge3 k ≥ 3 n ≥ k n \ge k n ≥ k H n H_n H n k k k n n n P n ( j ) = P ( H n > j ) P_n(j) = \mathbb{P}(H_n > j) P n ( j ) = P ( H n > j ) j ≥ 0 j \ge0 j ≥ 0 B > 0 B > 0 B > 0
L n = ⌊ B n ⌋ , T n = min { H n , L n } , μ n = E T n , e n = μ n / n . L_n = \lfloor Bn \rfloor,\qquad T_n = \min\{H_n,L_n\},\qquad\mu_n = \mathbb{E}T_n,\qquad e_n = \mu_n/n. L n = ⌊ B n ⌋ , T n = min { H n , L n } , μ n = E T n , e n = μ n / n . The endpoint for this first-unsatisfiable convention is strict:
P n ( j ) = P ( T n > j ) ( 0 ≤ j < L n ) . (45) P_n(j) = \mathbb{P}(T_n > j)\qquad(0 \le j < L_n). \tag*{(45)} P n ( j ) = P ( T n > j ) ( 0 ≤ j < L n ) . (45) At j = L n j = L_n j = L n P n ( L n ) P_n(L_n) P n ( L n ) (45) .
Theorem B.1 (Proper-clause center comparison from concentration). Fix k ≥ 3 k \ge3 k ≥ 3 B > 0 B > 0 B > 0 . S u p p o s e t h a t t h e r e a r e c o n s t a n t s $ 0 < a ≤ A < B . Suppose that there are constants \$0 < a \le A < B . S u pp ose t ha tt h er e a r eco n s t an t s $0 < a ≤ A < B η n ≥ 0 \eta_n \ge0 η n ≥ 0 n n n
a ≤ e n ≤ A , P ( ∣ T n − μ n ∣ ≥ n 1 − δ ) ≤ η n . (46) a \le e_n \le A,\qquad\mathbb{P}\left(\lvert T_n-\mu_n\rvert\ge n^{1-\delta}\right) \le\eta_n. \tag*{(46)} a ≤ e n ≤ A , P ( ∣ T n − μ n ∣ ≥ n 1 − δ ) ≤ η n . (46) Then there is a finite constant K ≥ 0 K \ge0 K ≥ 0 n = min { n 1 , n 2 } n = \min\{n_1,n_2\} n = min { n 1 , n 2 } n 1 / n 2 n_1/n_2 n 1 / n 2
e n 1 + n 2 ≥ min { e n 1 , e n 2 } − K n − δ , (47) e_{n_1+n_2} \ge\min\{e_{n_1},e_{n_2}\} - K n^{-\delta}, \tag*{(47)} e n 1 + n 2 ≥ min { e n 1 , e n 2 } − K n − δ , (47) and, for all sufficiently large n n n
e n + 1 ≥ e n − K n − δ . (48) e_{n+1} \ge e_n - K n^{-\delta}. \tag*{(48)} e n + 1 ≥ e n − K n − δ . (48) Moreover e n e_n e n α ∈ [ a , A ] \alpha\in[a,A] α ∈ [ a , A ]
P n ( ⌊ c n ⌋ ) ⟶ { 1 , 0 ≤ c < α , 0 , c > α . (49) P_n(\lfloor cn\rfloor) \longrightarrow
\begin{cases}
1, & 0 \le c < \alpha,\\
0, & c > \alpha.
\end{cases} \tag*{(49)} P n (⌊ c n ⌋) ⟶ { 1 , 0 , 0 ≤ c < α , c > α . (49) For every sufficiently large s s s N ≥ s 2 N \ge s^2 N ≥ s 2
e N ≥ e s − K ( 1 + B δ ) s − δ , B δ = ( 3 / 2 ) δ 1 − ( 2 / 3 ) δ . e_N \ge e_s - K(1+B_\delta)s^{-\delta}, \qquad B_\delta= \frac{(3/2)^\delta}{1-(2/3)^\delta}. e N ≥ e s − K ( 1 + B δ ) s − δ , B δ = 1 − ( 2/3 ) δ ( 3/2 ) δ . The theorem allows an arbitrary vanishing concentration error; it does not require a specified polynomial rate. In particular, Chebyshev’s inequality supplies eq:B.2 whenever
Var ( T n ) = o ( n 2 − 2 δ ) . (50) \operatorname{Var}(T_n)=o(n^{2-2\delta}). \tag*{(50)} Var ( T n ) = o ( n 2 − 2 δ ) . (50) The proof uses concentration twice: to make the two local formulas likely to be satisfiable, and to turn a likely satisfiable diluted formula back into a lower bound for the center at the combined size.
Local clauses and diluted global clauses
Lemma B.2 (Proper-clause trial comparison). Partition N = n 1 + n 2 N=n_1+n_2 N = n 1 + n 2 n 1 , n 2 ≥ k n_1,n_2 \ge k n 1 , n 2 ≥ k w j = n j / N w_j=n_j/N w j = n j / N n = min { n 1 , n 2 } n=\min\{n_1,n_2\} n = min { n 1 , n 2 } M ≥ 0 M \ge0 M ≥ 0 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 M M M j j j w j w_j w j k k k M M M k k k N N N 1 − ε 1-\varepsilon 1 − ε Q l o c Q_{\mathrm{loc}} Q loc Q d i l Q_{\mathrm{dil}} Q dil
Q d i l ≥ Q l o c − C k M ε − k ∑ j = 1 2 w j n j k , C k = [ k ( k − 1 ) ] k 2 k . (51) Q_{\mathrm{dil}} \ge Q_{\mathrm{loc}}-C_kM\varepsilon^{-k}\sum_{j=1}^{2}\frac{w_j}{n_j^k}, \qquad C_k=\frac{[k(k-1)]^k}{2^k}. \tag*{(51)} Q dil ≥ Q loc − C k M ε − k j = 1 ∑ 2 n j k w j , C k = 2 k [ k ( k − 1 ) ] k . (51) Q d i l ≥ Q l o c − C k M ε k n k . (52) Q_{\mathrm{dil}} \ge Q_{\mathrm{loc}}-\frac{C_kM}{\varepsilon^k n^k}. \tag*{(52)} Q dil ≥ Q loc − ε k n k C k M . (52) For N = n + 1 N=n+1 N = n + 1 n ≥ k n \ge k n ≥ k
Q d i l ≥ Q l o c − D k M ε k n k , D k = k 2 k 2 k . (53) Q_{\mathrm{dil}} \ge Q_{\mathrm{loc}}-\frac{D_kM}{\varepsilon^k n^k}, \qquad D_k=\frac{k^{2k}}{2^k}. \tag*{(53)} Q dil ≥ Q loc − ε k n k D k M , D k = 2 k k 2 k . (53) These statements impose no restriction on a block-size ratio.
Proof. Condition on every trial except the one being replaced. If the residual formula is unsatisfiable, both conditional satisfiability probabilities are zero. Otherwise let S S S S S S v ≥ k v \ge k v ≥ k b b b k k k S S S
h k ( b , v ) = ( b ) k 2 k ( v ) k . h_k(b,v)=\frac{(b)_k}{2^k(v)_k}. h k ( b , v ) = 2 k ( v ) k ( b ) k . Indeed, each of the selected variables must be frozen and each sign must oppose its frozen value. With x = b / v x=b/v x = b / v y + = max { y , 0 } y_+=\max\{y,0\} y + = max { y , 0 }
( x − k − 1 v ) + k 2 k ≤ h k ( b , v ) ≤ x k 2 k . (54) \frac{\left(x-\frac{k-1}{v}\right)_+^k}{2^k}\le h_k(b,v)\le\frac{x^k}{2^k}. \tag*{(54)} 2 k ( x − v k − 1 ) + k ≤ h k ( b , v ) ≤ 2 k x k . (54) For b ≥ k b \ge k b ≥ k ( b − r ) / ( v − r ) (b-r)/(v-r) ( b − r ) / ( v − r ) 0 ≤ r < k 0 \le r<k 0 ≤ r < k b / v b/v b / v ( b − k + 1 ) / v (b-k+1)/v ( b − k + 1 ) / v b < k b<k b < k
Let β j \beta_j β j j j j S S S (54) , the killing probability of a nondiluted global clause is at most
2 − k ( ∑ j w j β j ) k ≤ 2 − k ∑ j w j β j k . 2^{-k}\left(\sum_j w_j\beta_j\right)^k \le2^{-k}\sum_j w_j\beta_j^k. 2 − k ( j ∑ w j β j ) k ≤ 2 − k j ∑ w j β j k . whereas the local killing probability is at least 2 − k ∑ j w j ( β j − ( k − 1 ) / n j ) + k 2^{-k}\sum_j w_j\left(\beta_j-(k-1)/n_j\right)_+^k 2 − k ∑ j w j ( β j − ( k − 1 ) / n j ) + k β j ≥ k ( k − 1 ) / ( ε n j ) \beta_j \ge k(k-1)/(\varepsilon n_j) β j ≥ k ( k − 1 ) / ( ε n j )
( β j − k − 1 n j ) + k ≥ ( 1 − ε / k ) k β j k ≥ ( 1 − ε ) β j k . \left(\beta_j-\frac{k-1}{n_j}\right)_+^k \ge(1-\varepsilon/k)^k\beta_j^k \ge(1-\varepsilon)\beta_j^k. ( β j − n j k − 1 ) + k ≥ ( 1 − ε / k ) k β j k ≥ ( 1 − ε ) β j k . Below that threshold, β j k ≤ [ k ( k − 1 ) ] k / ( ε k n j k ) \beta_j^k \le[k(k-1)]^k/(\varepsilon^k n_j^k) β j k ≤ [ k ( k − 1 ) ] k / ( ε k n j k ) C k ε − k ∑ j w j / n j k C_k\varepsilon^{-k}\sum_j w_j/n_j^k C k ε − k ∑ j w j / n j k (51) . Since n j ≥ n n_j\ge n n j ≥ n w 1 + w 2 = 1 w_1+w_2=1 w 1 + w 2 = 1
For neighboring sizes, let b b b n n n x ∈ { 0 , 1 } x\in\{0,1\} x ∈ { 0 , 1 } γ = ( b + x ) / ( n + 1 ) \gamma=(b+x)/(n+1) γ = ( b + x ) / ( n + 1 ) b / n ≥ γ − 1 / ( n + 1 ) b/n\ge\gamma-1/(n+1) b / n ≥ γ − 1/ ( n + 1 ) 2 − k ( γ − k / n ) + k 2^{-k}(\gamma-k/n)_+^k 2 − k ( γ − k / n ) + k 2 − k γ k 2^{-k}\gamma^k 2 − k γ k γ = k 2 / ( ε n ) \gamma=k^2/(\varepsilon n) γ = k 2 / ( ε n ) D k / ( ε k n k ) D_k/(\varepsilon^k n^k) D k / ( ε k n k ) (53) .
At k = 3 k=3 k = 3 C 3 = 27 C_3=27 C 3 = 27 D 3 = 729 / 8 D_3=729/8 D 3 = 729/8
From a random clause count to a center
We first record the integer step needed in both center comparisons. From eq:B.2 and eq:B.1 , for every integer 0 ≤ j < L n 0\le j<L_n 0 ≤ j < L n n n n
j ≤ μ n − n 1 − δ ⟹ P n ( j ) ≥ 1 − η n , j ≥ μ n + n 1 − δ ⟹ P n ( j ) ≤ η n . (55) \begin{aligned}
j\le\mu_n-n^{1-\delta} &\Longrightarrow P_n(j)\ge1-\eta_n,\\
j\ge\mu_n+n^{1-\delta} &\Longrightarrow P_n(j)\le\eta_n. \tag*{(55)}
\end{aligned} j ≤ μ n − n 1 − δ j ≥ μ n + n 1 − δ ⟹ P n ( j ) ≥ 1 − η n , ⟹ P n ( j ) ≤ η n . (55) Because η n → 0 \eta_n\to0 η n → 0 η ‾ n = sup v ≥ n η v \overline{\eta}_n=\sup_{v\ge n}\eta_v η n = sup v ≥ n η v
Suppose, for a fixed a 0 > 0 a_0>0 a 0 > 0 a 0 N ≤ M ≤ A N a_0N\le M\le AN a 0 N ≤ M ≤ A N 0 < ε ≤ 1 / 2 0<\varepsilon\le1/2 0 < ε ≤ 1/2 Q d i l ≥ 1 − ζ Q_{\mathrm{dil}}\ge1-\zeta Q dil ≥ 1 − ζ J ∼ Bin ( M , 1 − ε ) J\sim\operatorname{Bin}(M,1-\varepsilon) J ∼ Bin ( M , 1 − ε ) J J J Q d i l = E P N ( J ) Q_{\mathrm{dil}}=\mathbb{E}P_N(J) Q dil = E P N ( J )
j = ⌈ ( 1 − ε ) M − N 1 − δ ⌉ . j=\left\lceil(1-\varepsilon)M-N^{1-\delta}\right\rceil. j = ⌈ ( 1 − ε ) M − N 1 − δ ⌉ . For all sufficiently large N N N M M M j ≥ 0 j\ge0 j ≥ 0 j ≤ M ≤ A N < L N j\le M\le AN<L_N j ≤ M ≤ A N < L N A < B A<B A < B Var ( J ) ≤ A N \operatorname{Var}(J)\le AN Var ( J ) ≤ A N
P ( J < j ) ≤ A N − 1 + 2 δ , Q d i l ≤ P N ( j ) + P ( J < j ) . \mathbb{P}(J<j)\le AN^{-1+2\delta},\qquad Q_{\mathrm{dil}}\le P_N(j)+\mathbb{P}(J<j). P ( J < j ) ≤ A N − 1 + 2 δ , Q dil ≤ P N ( j ) + P ( J < j ) . The second inequality uses monotonicity of P N P_N P N ζ + A N − 1 + 2 δ + η N < 1 \zeta+ AN^{-1+2\delta} + \eta_N < 1 ζ + A N − 1 + 2 δ + η N < 1 (55) forces j < μ N + N 1 − δ j < \mu_N + N^{1-\delta} j < μ N + N 1 − δ j j j
e N > ( 1 − ε ) M N − 2 N − δ − N − 1 ≥ ( 1 − ε ) M N − 3 N − δ . (56) e_N > \frac{(1-\varepsilon)M}{N} - 2N^{-\delta} - N^{-1} \ge\frac{(1-\varepsilon)M}{N} - 3N^{-\delta}. \tag*{(56)} e N > N ( 1 − ε ) M − 2 N − δ − N − 1 ≥ N ( 1 − ε ) M − 3 N − δ . (56) We will apply this implication with all three errors tending to zero.
Proof of Theorem B.1. For the two-block comparison, put N = n 1 + n 2 N=n_1+n_2 N = n 1 + n 2 n = min { n 1 , n 2 } n=\min\{n_1,n_2\} n = min { n 1 , n 2 } e ∗ = min { e n 1 , e n 2 } e_*=\min\{e_{n_1},e_{n_2}\} e ∗ = min { e n 1 , e n 2 }
ε = n − δ , M = ⌊ ( e ∗ − 2 ε ) N ⌋ . \varepsilon=n^{-\delta}, \qquad M=\left\lfloor(e_*-2\varepsilon)N\right\rfloor. ε = n − δ , M = ⌊ ( e ∗ − 2 ε ) N ⌋ . For sufficiently large n n n ( a / 4 ) N ≤ M ≤ A N (a/4)N \le M \le AN ( a /4 ) N ≤ M ≤ A N ε ≤ 1 / 2 \varepsilon\le1/2 ε ≤ 1/2 X j X_j X j j j j
E X j = M n j / N ≤ μ n j − 2 ε n j ≤ μ n j − 2 n j 1 − δ , Var ( X j ) ≤ A n j . \mathbb{E}X_j = Mn_j/N \le\mu_{n_j}-2\varepsilon n_j \le\mu_{n_j}-2n_j^{1-\delta}, \qquad\operatorname{Var}(X_j) \le An_j. E X j = M n j / N ≤ μ n j − 2 ε n j ≤ μ n j − 2 n j 1 − δ , Var ( X j ) ≤ A n j . Thus P ( X j > μ n j − n j 1 − δ ) ≤ A n j − 1 + 2 δ \mathbb{P}(X_j>\mu_{n_j}-n_j^{1-\delta}) \le An_j^{-1+2\delta} P ( X j > μ n j − n j 1 − δ ) ≤ A n j − 1 + 2 δ X j ≤ μ n j − n j 1 − δ X_j\le\mu_{n_j}-n_j^{1-\delta} X j ≤ μ n j − n j 1 − δ L n j L_{n_j} L n j n j n_j n j μ n j ≤ A n j \mu_{n_j}\le An_j μ n j ≤ A n j A < B A<B A < B (55) and a union bound therefore give
Q l o c ≥ 1 − ∑ j = 1 2 ( A n j − 1 + 2 δ + η n j ) . Q_{\mathrm{loc}} \ge1-\sum_{j=1}^{2}\left(An_j^{-1+2\delta}+\eta_{n_j}\right). Q loc ≥ 1 − j = 1 ∑ 2 ( A n j − 1 + 2 δ + η n j ) . The right-hand error is at most 2 A n − 1 + 2 δ + 2 η ‾ n 2An^{-1+2\delta}+2\overline{\eta}_n 2 A n − 1 + 2 δ + 2 η n n n n
The weighted replacement loss has the same uniformity:
C k M ε − k ∑ j w j n j k = C k M N ε − k ∑ j n j 1 − k ≤ 2 A C k n 1 − k + k δ = o ( 1 ) . (57) C_kM\varepsilon^{-k}\sum_j\frac{w_j}{n_j^k}
=C_k\frac{M}{N}\varepsilon^{-k}\sum_j n_j^{1-k}
\le2AC_kn^{1-k+k\delta}=o(1). \tag*{(57)} C k M ε − k j ∑ n j k w j = C k N M ε − k j ∑ n j 1 − k ≤ 2 A C k n 1 − k + k δ = o ( 1 ) . (57) Here 1 − k + k δ < 0 1-k+k\delta<0 1 − k + k δ < 0 k ≥ 3 k\ge3 k ≥ 3 δ < 1 / 2 \delta<1/2 δ < 1/2 N N N N / n N/n N / n eq:B.2 therefore gives Q d i l ≥ 1 − ζ n Q_{\mathrm{dil}}\ge1-\zeta_n Q dil ≥ 1 − ζ n ζ n → 0 \zeta_n\to0 ζ n → 0 N ≥ 2 n N\ge2n N ≥ 2 n N N N η N ≤ η ‾ n \eta_N\le\overline{\eta}_n η N ≤ η n (56) , and keeping the floor in M M M
e N ≥ ( 1 − ε ) ( e ∗ − 2 ε − N − 1 ) − 3 N − δ ≥ e ∗ − K n − δ , e_N\ge(1-\varepsilon)(e_*-2\varepsilon-N^{-1})-3N^{-\delta}\ge e_*-Kn^{-\delta}, e N ≥ ( 1 − ε ) ( e ∗ − 2 ε − N − 1 ) − 3 N − δ ≥ e ∗ − K n − δ , where the last inequality uses e ∗ ≤ A e_*\le A e ∗ ≤ A N ≥ n N\ge n N ≥ n δ < 1 \delta<1 δ < 1 eq:B.3 for arbitrary size ratios.
For the neighboring comparison take N = n + 1 N=n+1 N = n + 1 ε = n − δ \varepsilon=n^{-\delta} ε = n − δ M = ⌊ μ n − 2 n 1 − δ ⌋ M=\lfloor\mu_n-2n^{1-\delta}\rfloor M = ⌊ μ n − 2 n 1 − δ ⌋ n n n ( a / 4 ) N ≤ M ≤ A N (a/4)N\le M\le AN ( a /4 ) N ≤ M ≤ A N n n n n n n M M M Q l o c ≥ 1 − η n Q_{\mathrm{loc}}\ge1-\eta_n Q loc ≥ 1 − η n (55) . The neighboring replacement loss is
D k M ε k n k = O k , A ( n 1 − k + k δ ) = o ( 1 ) . \frac{D_kM}{\varepsilon^k n^k}=O_{k,A}(n^{1-k+k\delta})=o(1). ε k n k D k M = O k , A ( n 1 − k + k δ ) = o ( 1 ) . Equation (56) now gives
e n + 1 ≥ ( 1 − ε ) n e n − 2 n 1 − δ − 1 n + 1 − 3 ( n + 1 ) − δ ≥ e n − K n − δ . e_{n+1} \ge(1-\varepsilon)\frac{ne_n-2n^{1-\delta}-1}{n+1}-3(n+1)^{-\delta} \ge e_n-Kn^{-\delta}. e n + 1 ≥ ( 1 − ε ) n + 1 n e n − 2 n 1 − δ − 1 − 3 ( n + 1 ) − δ ≥ e n − K n − δ . For the last step, use e n ≤ A e_n \le A e n ≤ A 1 − ( 1 − ε ) n / ( n + 1 ) ≤ ε + 1 / ( n + 1 ) 1-(1-\varepsilon)n/(n+1) \le\varepsilon+1/(n+1) 1 − ( 1 − ε ) n / ( n + 1 ) ≤ ε + 1/ ( n + 1 ) eq:B.4 .
It remains to explain the deterministic step and check its inputs. The geometric summation of errors parallels Abbe and Montanari’s approximate sum-superadditivity argument [1 ] (arXiv version, Lemma 8 and Remark 3). The required minimum comparison is the threshold companion’s Lemma 5.4 (“Balanced comparisons”) [16 ] . For an integer n 0 ≥ 1 n_0 \ge1 n 0 ≥ 1 ( u n ) n ≥ n 0 (u_n)_{n\ge n_0} ( u n ) n ≥ n 0
u r + s ≥ min { u r , u s } − K min ( r , s ) − δ for 1 / 3 ≤ r / s ≤ 3 , u s + 1 ≥ u s − K s − δ , u_{r+s} \ge\min\{u_r,u_s\}-K\min(r,s)^{-\delta}\quad\text{for }1/3\le r/s\le3,\qquad u_{s+1}\ge u_s-Ks^{-\delta}, u r + s ≥ min { u r , u s } − K min ( r , s ) − δ for 1/3 ≤ r / s ≤ 3 , u s + 1 ≥ u s − K s − δ , for all r , s ≥ n 0 r,s \ge n_0 r , s ≥ n 0 s ≥ n 0 s \ge n_0 s ≥ n 0 K ≥ 0 K \ge0 K ≥ 0 δ > 0 \delta> 0 δ > 0 s ≥ max { n 0 , 2 } s \ge\max\{n_0,2\} s ≥ max { n 0 , 2 } N ≥ s N \ge s N ≥ s u N ≥ u s − K ( 1 + B δ ) s − δ u_N \ge u_s-K(1+B_\delta)s^{-\delta} u N ≥ u s − K ( 1 + B δ ) s − δ B δ B_\delta B δ s s s s + 1 s+1 s + 1 n 0 n_0 n 0 eq:B.2 , the comparable-size part of eq:B.3 , and eq:B.4 verify every hypothesis with u n = e n u_n=e_n u n = e n (B.6) and convergence to some α ∈ [ a , A ] \alpha\in[a,A] α ∈ [ a , A ]
For 0 ≤ c < α 0 \le c < \alpha 0 ≤ c < α ⌊ c n ⌋ ≤ μ n − n 1 − δ \lfloor cn\rfloor\le\mu_n-n^{1-\delta} ⌊ c n ⌋ ≤ μ n − n 1 − δ ⌊ c n ⌋ < L n \lfloor cn\rfloor< L_n ⌊ c n ⌋ < L n α < c < B \alpha<c<B α < c < B μ n + n 1 − δ ≤ ⌊ c n ⌋ < L n \mu_n+n^{1-\delta}\le\lfloor cn\rfloor<L_n μ n + n 1 − δ ≤ ⌊ c n ⌋ < L n n 1 − δ + 1 n^{1-\delta}+1 n 1 − δ + 1 (55) . Since α ≤ A < B \alpha\le A < B α ≤ A < B d ∈ ( A , B ) d \in(A,B) d ∈ ( A , B ) d d d c ≥ B c \ge B c ≥ B eq:B.5 .
The comparison (B.6) is one-sided. It proves convergence of the finite-size means, but gives no two-sided estimate for μ n − α n \mu_n-\alpha n μ n − α n
For the main application put B k = 2 k + 1 B_k=2^{k+1} B k = 2 k + 1 B = B k B=B_k B = B k k = 3 k=3 k = 3 B = 10 B=10 B = 10 q k = 1 − 2 − k q_k=1-2^{-k} q k = 1 − 2 − k P n ( j ) ≤ 2 n q k j P_n(j)\le2^nq_k^{j} P n ( j ) ≤ 2 n q k j d d d
E H n = ∑ j = 0 ∞ P n ( j ) ≤ d n + 2 k ( 2 d q k ) n . (58) \mathbb{E}H_n=\sum_{j=0}^{\infty}P_n(j)\le dn+2^k(2dq_k)^n. \tag*{(58)} E H n = j = 0 ∑ ∞ P n ( j ) ≤ d n + 2 k ( 2 d q k ) n . (58) For d = 2 k d=2^k d = 2 k 2 q k 2 k < 2 / e < 1 2q_k^{2^k}<2/e<1 2 q k 2 k < 2/ e < 1 k = 3 k=3 k = 3 d = 6 d=6 d = 6 2 ( 7 / 8 ) 6 < 1 2(7/8)^6<1 2 ( 7/8 ) 6 < 1 T n ≤ H n T_n\le H_n T n ≤ H n
e n ≤ A k < B , A k = { 7 , k = 3 , 2 k + 1 , k ≥ 4. (59) e_n\le A_k<B,\qquad A_k=\begin{cases}7,&k=3,\\2^k+1,&k\ge4.\end{cases} \tag*{(59)} e n ≤ A k < B , A k = { 7 , 2 k + 1 , k = 3 , k ≥ 4. (59) For the positive anchor, fix 0 < c < min { e − 2 , B } 0<c<\min\{e^{-2},B\} 0 < c < min { e − 2 , B } j = ⌊ c n ⌋ j=\lfloor cn\rfloor j = ⌊ c n ⌋ P n ( j ) = 1 − O c ( n − 2 ) P_n(j)=1-O_c(n^{-2}) P n ( j ) = 1 − O c ( n − 2 ) c < B c<B c < B j < L n j<L_n j < L n n n n μ n ≥ j P n ( j ) = c n − o ( n ) \mu_n\ge jP_n(j)=cn-o(n) μ n ≥ j P n ( j ) = c n − o ( n ) c 0 = c / 2 c_0=c/2 c 0 = c /2
c 0 ≤ e n ≤ A k < B for all sufficiently large n . (60) c_0\le e_n\le A_k<B\qquad\text{for all sufficiently large }n. \tag*{(60)} c 0 ≤ e n ≤ A k < B for all sufficiently large n . (60) The capped variance theorem gives
Var ( T n ) n 2 − 2 δ = { O ( n − 1 + 2 δ log n ) , k = 3 , O k ( n − 1 + 2 δ ) , k ≥ 4. \frac{\operatorname{Var}(T_n)}{n^{2-2\delta}} =
\begin{cases}
O(n^{-1+2\delta}\log n), & k=3,\\
O_k(n^{-1+2\delta}), & k\ge4.
\end{cases} n 2 − 2 δ Var ( T n ) = { O ( n − 1 + 2 δ log n ) , O k ( n − 1 + 2 δ ) , k = 3 , k ≥ 4. which tends to zero for every fixed 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 a = c 0 a=c_0 a = c 0 A = A k A=A_k A = A k α k \alpha_k α k [16 ] , Theorem 1.1: if the two limits differed, a density strictly between them would be assigned opposite limiting probabilities. In particular, the proper-clause comparisons (B.3)–(B.4) hold for every such fixed δ \delta δ
The weaker polynomial variance estimate of the threshold companion [16 ] , Proposition 3.3 can be used as a separate input. For a = B k n a=B_kn a = B k n b = a b=a b = a
min { H n − 1 , a } = min { H n , a } − 1 + 1 { H n > a } . \min\{H_n-1,a\}=\min\{H_n,a\}-1+\mathbf{1}_{\{H_n>a\}}. min { H n − 1 , a } = min { H n , a } − 1 + 1 { H n > a } . That proposition gives Var ( min { H n , a } ) ≤ Var ( min { H n − 1 , a } ) \operatorname{Var}(\min\{H_n,a\})\le\operatorname{Var}(\min\{H_n-1,a\}) Var ( min { H n , a }) ≤ Var ( min { H n − 1 , a }) O k ( n 1 + 2 / k ) O_k(n^{1+2/k}) O k ( n 1 + 2/ k ) 0 < δ < ( k − 2 ) / ( 2 k ) 0<\delta<(k-2)/(2k) 0 < δ < ( k − 2 ) / ( 2 k ) δ = ( k − 2 ) / ( 4 k ) \delta=(k-2)/(4k) δ = ( k − 2 ) / ( 4 k ) δ < 1 / 2 \delta<1/2 δ < 1/2
A three-clause proof using prefix exposure
We give a second variance estimate for three-clause formulas, revealing clause types only through the current prefix. The argument truncates the number of clauses testing each variable of an omitted clause at ⌈ log n ⌉ \lceil\log n\rceil ⌈ log n ⌉ O ( n log 4 n ) O(n\log^4 n) O ( n log 4 n ) O ( n log n ) O(n\log n) O ( n log n ) u u u g g g 64 ( g − 2 + u − 2 ) 64(g^{-2}+u^{-2}) 64 ( g − 2 + u − 2 )
Throughout this section, C 1 , C 2 , … C_1,C_2,\ldots C 1 , C 2 , … n ≥ 3 n\ge3 n ≥ 3 H n H_n H n
L = 10 n , T n = min { H n , L } , m n = E T n . L=10n,\qquad T_n=\min\{H_n,L\},\qquad m_n=\mathbb{E}T_n. L = 10 n , T n = min { H n , L } , m n = E T n . Theorem C.1 (Variance from prefix exposure). There is an absolute constant C C C n ≥ 3 n\ge3 n ≥ 3
Var ( T n ) ≤ C n ( log n ) 4 . \operatorname{Var}(T_n)\le Cn(\log n)^4. Var ( T n ) ≤ C n ( log n ) 4 . Consequently, for every t > 0 t>0 t > 0
P ( ∣ T n − m n ∣ ≥ t n ( log n ) 2 ) ≤ C t − 2 . \mathbb{P}\left(\lvert T_n-m_n\rvert\ge t\sqrt{n}(\log n)^2\right)\le Ct^{-2}. P ( ∣ T n − m n ∣ ≥ t n ( log n ) 2 ) ≤ C t − 2 . The proof has two uses of the same lifetime estimate. It bounds the remaining duration of a deletion event and the total time spent at a given level of the probability of killing the surviving assignments. Three independent root-flip tests connect those two bounds.
Replacing pairs by triples on a finite variable set
For an integer u ≥ 3 u \ge3 u ≥ 3 S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u kills S S S S S S r r r 2 r ( u r ) 2^{r}\binom{u}{r} 2 r ( r u ) r r r d ≥ 1 d \ge1 d ≥ 1 q d ( S ) q_d(S) q d ( S ) d d d S S S τ ( S ) \tau(S) τ ( S ) S S S τ ( ∅ ) = 0 \tau(\varnothing)=0 τ ( ∅ ) = 0 S S S m m m ∣ S ∣ ( 7 / 8 ) m |S|(7/8)^m ∣ S ∣ ( 7/8 ) m
Replacing a shorter constraint by native clauses has a qualitative predecessor in Friedgut’s half-cube argument [12 ] (Lemma 5.7). The residual-set conditioning used below is the averaged replacement method of Carenini [5 ] (Theorem 4.3, Lemma 6.1, and Corollary 6.2); the following bound supplies the finite-variable pair-to-triple estimate needed here.
Lemma C.2 (One-pair replacement). For every integer u ≥ 3 u \ge3 u ≥ 3 S ⊆ { 0 , 1 } u S \subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u g ≥ 1 g \ge1 g ≥ 1 g g g u u u
P ( the g triples kill S ) ≥ q 1 ( S ) − 64 ( g − 2 + u − 2 ) . (61) \mathbb{P}(\text{the }g\text{ triples kill }S) \ge q_1(S)-64(g^{-2}+u^{-2}). \tag*{(61)} P ( the g triples kill S ) ≥ q 1 ( S ) − 64 ( g − 2 + u − 2 ) . (61) Proof. If S = ∅ S=\varnothing S = ∅ S ≠ ∅ S\ne\varnothing S = ∅ b b b S S S S S S b b b r r r
h r = ( b r ) 2 r ( u r ) , r = 2 , 3 , h_r=\frac{\binom{b}{r}}{2^r\binom{u}{r}},\qquad r=2,3, h r = 2 r ( r u ) ( r b ) , r = 2 , 3 , where ( x ) r = x ( x − 1 ) ⋯ ( x − r + 1 ) (x)_r=x(x-1)\cdots(x-r+1) ( x ) r = x ( x − 1 ) ⋯ ( x − r + 1 ) ( b ) r = 0 (b)_r=0 ( b ) r = 0 0 ≤ b < r 0\le b<r 0 ≤ b < r b ≥ 3 b\ge3 b ≥ 3
h 3 h 2 3 / 2 = b − 2 b ( b − 1 ) u ( u − 1 ) u − 2 ≥ 1 4 . \frac{h_3}{h_2^{3/2}}=\frac{b-2}{\sqrt{b(b-1)}}\frac{\sqrt{u(u-1)}}{u-2}\ge\frac{1}{4}. h 2 3/2 h 3 = b ( b − 1 ) b − 2 u − 2 u ( u − 1 ) ≥ 4 1 . Indeed, the first factor is at least ( b − 2 ) / b ≥ 1 / 3 (b-2)/b\ge1/3 ( b − 2 ) / b ≥ 1/3
Put h = h 2 ≤ 1 / 4 h=h_2\le1/4 h = h 2 ≤ 1/4 S S S S S S 1 − ( 1 − h 3 ) g ≥ 1 − e − g h 3 1-(1-h_3)^g\ge1-e^{-gh_3} 1 − ( 1 − h 3 ) g ≥ 1 − e − g h 3 b ≥ 3 b\ge3 b ≥ 3 ( g / 4 ) h ≥ 2 (g/4)\sqrt{h}\ge2 ( g /4 ) h ≥ 2 g h 3 ≥ 2 h gh_3\ge2h g h 3 ≥ 2 h 1 − e − 2 h ≥ h 1-e^{-2h}\ge h 1 − e − 2 h ≥ h 1 − e − 2 h − h 1-e^{-2h}-h 1 − e − 2 h − h [ 0 , 1 / 4 ] [0,1/4] [ 0 , 1/4 ] b ≥ 3 b\ge3 b ≥ 3 h ≤ 64 g − 2 h\le64g^{-2} h ≤ 64 g − 2
If b < 3 b<3 b < 3
h ≤ 1 2 u ( u − 1 ) ≤ u − 2 . h\le\frac{1}{2u(u-1)}\le u^{-2}. h ≤ 2 u ( u − 1 ) 1 ≤ u − 2 . The nonnegativity of the block killing probability now proves (61) in every case. □ \square □
Remark C.3. For k = 3 k=3 k = 3 2.1 2.1 2.1 256 g − 2 256g^{-2} 256 g − 2 64 ( g − 2 + u − 2 ) 64(g^{-2}+u^{-2}) 64 ( g − 2 + u − 2 ) g < 3 u g<\sqrt{3}u g < 3 u g > 3 u g>\sqrt{3}u g > 3 u g = 3 u g=\sqrt{3}u g = 3 u
Proposition C.4 (Lifetime above the finite-variable cutoff). *Let K = 64 K=64 K = 64 K 1 K_1 K 1 u ≥ 3 u\ge3 u ≥ 3 S ⊆ { 0 , 1 } u S\subseteq\{0,1\}^{u} S ⊆ { 0 , 1 } u d ≥ 1 d\ge1 d ≥ 1 a a a 4 K d / u 2 ≤ a ≤ 1 4Kd/u^2\le a\le1 4 K d / u 2 ≤ a ≤ 1
q d ( S ) ≥ a ⟹ τ ( S ) ≤ K 1 d 3 / 2 a − 3 / 2 . q_d(S)\ge a\quad\Longrightarrow\quad\tau(S)\le K_1d^{3/2}a^{-3/2}. q d ( S ) ≥ a ⟹ τ ( S ) ≤ K 1 d 3/2 a − 3/2 . Proof. Replace d d d g g g S ′ ⊆ S S' \subseteq S S ′ ⊆ S K ( g − 2 + u − 2 ) K(g^{-2}+u^{-2}) K ( g − 2 + u − 2 )
P ( d g independent uniform proper three-clauses kill S ) ≥ q d ( S ) − K d ( g − 2 + u − 2 ) . (62) \mathbb{P}(dg\text{ independent uniform proper three-clauses kill }S) \ge q_d(S)-Kd(g^{-2}+u^{-2}). \tag*{(62)} P ( d g independent uniform proper three-clauses kill S ) ≥ q d ( S ) − K d ( g − 2 + u − 2 ) . (62) Choose g = ⌈ 4 K d / a ⌉ g=\lceil\sqrt{4Kd/a}\rceil g = ⌈ 4 K d / a ⌉ K d / g 2 Kd/g^2 K d / g 2 K d / u 2 Kd/u^2 K d / u 2 a / 4 a/4 a /4 d g dg d g S S S a / 2 a/2 a /2 2 / a 2/a 2/ a S S S
τ ( S ) ≤ 2 d g a ≤ 8 K d 3 / 2 a − 3 / 2 , \tau(S) \le\frac{2dg}{a} \le8\sqrt{K}\,d^{3/2}a^{-3/2}, τ ( S ) ≤ a 2 d g ≤ 8 K d 3/2 a − 3/2 , where g ≤ 2 4 K d / a g \le2\sqrt{4Kd/a} g ≤ 2 4 K d / a d ≥ 1 d \ge1 d ≥ 1 a ≤ 1 a \le1 a ≤ 1 K 1 = 64 K_1=64 K 1 = 64
A deleted clause and an unexposed future
We now apply the lifetime estimate to the delay caused by omitting one clause. We first assume n n n n ≥ 6 n \ge6 n ≥ 6 1 ≤ i ≤ L 1 \le i \le L 1 ≤ i ≤ L m ≥ 0 m \ge0 m ≥ 0
B m ( i ) = ⋀ 1 ≤ j ≤ m j ≠ i C j , T ( i ) = min { inf { m ∈ Z ≥ 0 : B m ( i ) ∉ S A T } , L } , D i = T ( i ) − T n , B_m^{(i)}=\bigwedge_{\substack{1\le j\le m\\j\ne i}} C_j,\qquad T^{(i)}=\min\{\inf\{m\in\mathbb{Z}_{\ge0}:B_m^{(i)}\notin\mathrm{SAT}\},L\},\qquad D_i=T^{(i)}-T_n, B m ( i ) = 1 ≤ j ≤ m j = i ⋀ C j , T ( i ) = min { inf { m ∈ Z ≥ 0 : B m ( i ) ∈ / SAT } , L } , D i = T ( i ) − T n , with inf ∅ = ∞ \inf\varnothing=\infty inf ∅ = ∞ D i ≥ 0 D_i\ge0 D i ≥ 0 T ( i ) T^{(i)} T ( i ) C i C_i C i
Var ( T n ) ≤ ∑ i = 1 L E D i 2 . (63) \operatorname{Var}(T_n)\le\sum_{i=1}^{L}\mathbb{E}D_i^2. \tag*{(63)} Var ( T n ) ≤ i = 1 ∑ L E D i 2 . (63) Its martingale proof applies to precisely these index-preserving deletions and to the cap L = 10 n L=10n L = 10 n i i i C i C_i C i i i i R R R C i C_i C i t ∈ { 0 , 1 } R t\in\{0,1\}^{R} t ∈ { 0 , 1 } R C i C_i C i u = n − 3 u=n-3 u = n − 3 B m = B m ( i ) B_m=B_m^{(i)} B m = B m ( i ) F m = σ ( C j : 1 ≤ j ≤ m , j ≠ i ) \mathcal{F}_m=\sigma(C_j:1\le j\le m,\ j\ne i) F m = σ ( C j : 1 ≤ j ≤ m , j = i ) u ≥ 3 u\ge3 u ≥ 3
For i ≤ m < L i\le m<L i ≤ m < L
A m = { T n ≤ m < T ( i ) } = { B m ∈ S A T , B m ∧ C i ∉ S A T } . (64) A_m=\{T_n\le m<T^{(i)}\}=\{B_m\in\mathrm{SAT},\ B_m\land C_i\notin\mathrm{SAT}\}. \tag*{(64)} A m = { T n ≤ m < T ( i ) } = { B m ∈ SAT , B m ∧ C i ∈ / SAT } . (64) On A m A_m A m B m B_m B m t t t i i i
D i = ∑ m = i L − 1 1 { A m } . (65) D_i=\sum_{m=i}^{L-1}\mathbf{1}_{\{A_m\}}. \tag*{(65)} D i = m = i ∑ L − 1 1 { A m } . (65) In particular D L = 0 D_L=0 D L = 0 m ≥ i m \ge i m ≥ i S m ⊂ { 0 , 1 } u S_m \subset\{0,1\}^u S m ⊂ { 0 , 1 } u B m B_m B m t t t F m \mathcal{F}_m F m A m A_m A m
A clause is ordinary if it uses only nonroots. A fresh clause is ordinary with probability
p 0 = ( u 3 ) ( n 3 ) , p_0=\frac{\binom{u}{3}}{\binom{n}{3}}, p 0 = ( 3 n ) ( 3 u ) , which is bounded below by a positive absolute constant for sufficiently large n n n U m U_m U m m m m S m S_m S m U m = 0 U_m=0 U m = 0 S m = ∅ S_m=\varnothing S m = ∅ L L L F m \mathcal{F}_m F m 1 / p 0 1/p_0 1/ p 0
E [ U m ∣ F m ] = τ ( S m ) p 0 . (66) \mathbb{E}[U_m\mid\mathcal{F}_m]=\frac{\tau(S_m)}{p_0}. \tag*{(66)} E [ U m ∣ F m ] = p 0 τ ( S m ) . (66) The assertion uses the fact that only the prefix has been revealed; for m ≥ i m\ge i m ≥ i m m m C i C_i C i
Lemma C.5 (Remaining deletion time). Set W m = min { L , τ ( S m ) / p 0 } W_m=\min\{L,\tau(S_m)/p_0\} W m = min { L , τ ( S m ) / p 0 } i ≤ m < L i\le m<L i ≤ m < L A m A_m A m
E [ ∑ ℓ = m + 1 L − 1 1 { A ℓ } ∣ F m ] ≤ W m . \mathbb{E}\left[\left.\sum_{\ell=m+1}^{L-1}\mathbf{1}_{\{A_\ell\}}\right|\mathcal{F}_m\right]\le W_m. E [ ℓ = m + 1 ∑ L − 1 1 { A ℓ } F m ] ≤ W m . Consequently,
E D i 2 ≤ 3 ∑ m = i L − 1 E [ 1 { A m } W m ] . (67) \mathbb{E}D_i^2\le3\sum_{m=i}^{L-1}\mathbb{E}\left[\mathbf{1}_{\{A_m\}}W_m\right]. \tag*{(67)} E D i 2 ≤ 3 m = i ∑ L − 1 E [ 1 { A m } W m ] . (67) Proof. On A m A_m A m B ℓ B_\ell B ℓ t t t S m S_m S m S m S_m S m A ℓ A_\ell A ℓ ℓ ≥ m + U m \ell\ge m+U_m ℓ ≥ m + U m U m U_m U m L L L min { E [ U m ∣ F m ] , L } \min\{\mathbb{E}[U_m\mid\mathcal{F}_m],L\} min { E [ U m ∣ F m ] , L } (66) proves the first assertion.
On A m A_m A m S m S_m S m W m ≥ 1 W_m\ge1 W m ≥ 1 (65) , conditioning each cross term on its earlier history, and using the first assertion gives
E D i 2 = ∑ m E 1 { A m } + 2 ∑ m E [ 1 { A m } E [ ∑ ℓ = m + 1 L − 1 1 { A ℓ } ∣ F m ] ] ≤ ∑ m E [ 1 { A m } ( 1 + 2 W m ) ] ≤ 3 ∑ m E [ 1 { A m } W m ] , \begin{aligned}
\mathbb{E}D_i^2
&=\sum_m\mathbb{E}\mathbf{1}_{\{A_m\}}+
2\sum_m\mathbb{E}\left[\mathbf{1}_{\{A_m\}}\mathbb{E}\left[\left.\sum_{\ell=m+1}^{L-1}\mathbf{1}_{\{A_\ell\}}\right|\mathcal{F}_m\right]\right]\\
&\le\sum_m\mathbb{E}\left[\mathbf{1}_{\{A_m\}}(1+2W_m)\right]
\le3\sum_m\mathbb{E}\left[\mathbf{1}_{\{A_m\}}W_m\right],
\end{aligned} E D i 2 = m ∑ E 1 { A m } + 2 m ∑ E [ 1 { A m } E [ ℓ = m + 1 ∑ L − 1 1 { A ℓ } F m ] ] ≤ m ∑ E [ 1 { A m } ( 1 + 2 W m ) ] ≤ 3 m ∑ E [ 1 { A m } W m ] , where every outer sum runs from m = i m=i m = i L − 1 L-1 L − 1
The three root-flip tests
The weight in (67) is determined by the surviving set. To estimate the accompanying deletion probability, we hide the parts of clauses that are already satisfied at the fixed root values. They will test whether a root can be flipped.
The type of a baseline clause through index m m m j ∈ R j \in R j ∈ R I j , m I_{j,m} I j , m i i i m m m j j j t t t s j , m = ∣ I j , m ∣ s_{j,m} = \lvert I_{j,m}\rvert s j , m = ∣ I j , m ∣ collision , and let v m v_m v m m m m J m ⊆ R J_m \subseteq R J m ⊆ R j j j m m m t t t j j j
∣ J m ∣ ≥ 3 − v m . (68) \lvert J_m\rvert\ge3-v_m. \tag*{(68)} ∣ J m ∣ ≥ 3 − v m . (68) Let G m \mathcal{G}_m G m m m m ⋃ j ∈ R I j , m \bigcup_{j\in R} I_{j,m} ⋃ j ∈ R I j , m G m ⊆ F m \mathcal{G}_m \subseteq\mathcal{F}_m G m ⊆ F m t t t S m S_m S m S m S_m S m J m J_m J m s j , m s_{j,m} s j , m v m v_m v m W m W_m W m G m \mathcal{G}_m G m G m \mathcal{G}_m G m u u u
Put
d = ⌈ log n ⌉ , q m = q d ( S m ) . d=\lceil\log n\rceil,\qquad q_m=q_d(S_m). d = ⌈ log n ⌉ , q m = q d ( S m ) . Lemma C.6 (Root-flip tests under prefix conditioning). For every i ≤ m < L i\le m<L i ≤ m < L G m \mathcal{G}_m G m { max j ∈ R s j , m ≤ d , ∣ J m ∣ ≥ 1 } \{\max_{j\in R}s_{j,m}\le d,\ \lvert J_m\rvert\ge1\} { max j ∈ R s j , m ≤ d , ∣ J m ∣ ≥ 1 }
P ( A m ∣ G m ) ≤ 1 { S m ≠ ∅ } q m ∣ J m ∣ . (69) \mathbb{P}(A_m\mid\mathcal{G}_m)\le\mathbf{1}_{\{S_m\ne\varnothing\}}q_m^{\lvert J_m\rvert}. \tag*{(69)} P ( A m ∣ G m ) ≤ 1 { S m = ∅ } q m ∣ J m ∣ . (69) Proof. If A m A_m A m j ∈ J m j\in J_m j ∈ J m I j , m I_{j,m} I j , m S m S_m S m S m S_m S m t t t j j j j j j j j j j ∈ J m j\in J_m j ∈ J m I j , m I_{j,m} I j , m B m B_m B m t t t (64) .
The required killing events for different j j j S m S_m S m d d d q d ( S m ) = q m q_d(S_m)=q_m q d ( S m ) = q m S m ≠ ∅ S_m\ne\varnothing S m = ∅ (69) .
Truncating incidence counts and summing occupation
It remains to sum the right side of (67) . The tests make deletion unlikely when q m q_m q m
Lemma C.7 (Prefix incidence counts). Uniformly in i ≤ m < L i\le m<L i ≤ m < L C i C_i C i
P ( max j ∈ R s j , m > d ) = O ( n − 4 ) , (70) \mathbb{P}\left(\max_{j\in R}s_{j,m}>d\right)=O(n^{-4}), \tag*{(70)} P ( j ∈ R max s j , m > d ) = O ( n − 4 ) , (70) P ( v m ≥ 1 ) = O ( n − 1 ) , P ( v m ≥ 2 ) = O ( n − 2 ) . (71) \mathbb{P}(v_m\ge1)=O(n^{-1}),\qquad\mathbb{P}(v_m\ge2)=O(n^{-2}). \tag*{(71)} P ( v m ≥ 1 ) = O ( n − 1 ) , P ( v m ≥ 2 ) = O ( n − 2 ) . (71) Proof. A baseline clause contains a specified root with probability 3 / n 3/n 3/ n s j , m s_{j,m} s j , m d d d L = 10 n L=10n L = 10 n
P ( max j ∈ R s j , m > d ) ≤ 3 ( L d ) ( 3 / n ) d ≤ 3 ( 30 e / d ) d = O ( n − 4 ) . (72) \mathbb{P}\left(\max_{j\in R}s_{j,m}>d\right)\le3\binom{L}{d}(3/n)^d\le3(30e/d)^d=O(n^{-4}). \tag*{(72)} P ( j ∈ R max s j , m > d ) ≤ 3 ( d L ) ( 3/ n ) d ≤ 3 ( 30 e / d ) d = O ( n − 4 ) . (72) The final bound holds for sufficiently large n n n d = ⌈ log n ⌉ d=\lceil\log n\rceil d = ⌈ log n ⌉ log d → ∞ \log d\to\infty log d → ∞
A trial contains any specified pair of roots with probability 6 / [ n ( n − 1 ) ] 6/[n(n-1)] 6/ [ n ( n − 1 )] 18 / [ n ( n − 1 ) ] 18/[n(n-1)] 18/ [ n ( n − 1 )] L L L P ( v m ≥ 1 ) = O ( n − 1 ) \mathbb{P}(v_m\ge1)=O(n^{-1}) P ( v m ≥ 1 ) = O ( n − 1 ) P ( v m ≥ 2 ) ≤ ( L 2 ) O ( n − 4 ) = O ( n − 2 ) \mathbb{P}(v_m\ge2)\le\binom{L}{2}O(n^{-4})=O(n^{-2}) P ( v m ≥ 2 ) ≤ ( 2 L ) O ( n − 4 ) = O ( n − 2 )
With K = 64 K=64 K = 64
a 0 = 4 K d u 2 = 256 d ( n − 3 ) 2 . (73) a_0=\frac{4Kd}{u^2}=\frac{256d}{(n-3)^2}. \tag*{(73)} a 0 = u 2 4 K d = ( n − 3 ) 2 256 d . (73) For sufficiently large n n n a 0 < 1 a_0<1 a 0 < 1 S m ≠ ∅ S_m\ne\varnothing S m = ∅
W m q m 3 / 2 ≤ C d 3 / 2 . (74) \mathcal{W}_m q_m^{3/2}\le Cd^{3/2}. \tag*{(74)} W m q m 3/2 ≤ C d 3/2 . (74) For q m ≥ a 0 q_m\ge a_0 q m ≥ a 0 a = q m a=q_m a = q m W m ≤ τ ( S m ) / p 0 \mathcal{W}_m\le\tau(S_m)/p_0 W m ≤ τ ( S m ) / p 0 q m < a 0 q_m<a_0 q m < a 0 q m = 0 q_m=0 q m = 0 W m ≤ L \mathcal{W}_m\le L W m ≤ L
L a 0 3 / 2 = 10 n ( 256 d ( n − 3 ) 2 ) 3 / 2 = O ( d 3 / 2 n − 2 ) ≤ C d 3 / 2 . (75) La_0^{3/2}=10n\left(\frac{256d}{(n-3)^2}\right)^{3/2}=O(d^{3/2}n^{-2})\le Cd^{3/2}. \tag*{(75)} L a 0 3/2 = 10 n ( ( n − 3 ) 2 256 d ) 3/2 = O ( d 3/2 n − 2 ) ≤ C d 3/2 . (75) Lemma C.8 (Reduction to occupation). For all sufficiently large n n n i i i C i C_i C i
E D i 2 ≤ C ( 1 + d 3 / 2 ) + C d 3 / 2 ∑ m = i L − 1 E [ 1 { S m ≠ ∅ } q m 3 / 2 ] . (76) \mathbb{E}D_i^2\le C(1+d^{3/2})+Cd^{3/2}\sum_{m=i}^{L-1}\mathbb{E}\left[1_{\{S_m\ne\varnothing\}}q_m^{3/2}\right]. \tag*{(76)} E D i 2 ≤ C ( 1 + d 3/2 ) + C d 3/2 m = i ∑ L − 1 E [ 1 { S m = ∅ } q m 3/2 ] . (76) Proof. In (67) , the terms on { max j s j , m > d } ∪ { v m ≥ 2 } \{\max_j s_{j,m}>d\}\cup\{v_m\ge2\} { max j s j , m > d } ∪ { v m ≥ 2 }
L ∑ m = i L − 1 [ P ( max j s j , m > d ) + P ( v m ≥ 2 ) ] = O ( L 2 ( n − 4 + n − 2 ) ) = O ( 1 ) . L\sum_{m=i}^{L-1}\left[\mathbb{P}(\max_j s_{j,m}>d)+\mathbb{P}(v_m\ge2)\right]=O\left(L^2(n^{-4}+n^{-2})\right)=O(1). L m = i ∑ L − 1 [ P ( j max s j , m > d ) + P ( v m ≥ 2 ) ] = O ( L 2 ( n − 4 + n − 2 ) ) = O ( 1 ) . For every remaining term, the restrictions, W m \mathcal{W}_m W m S m S_m S m G m \mathcal{G}_m G m v m = 1 v_m=1 v m = 1 ∣ J m ∣ ≥ 2 |J_m|\ge2 ∣ J m ∣ ≥ 2 G m \mathcal{G}_m G m 1 { S m ≠ ∅ } W m q m 2 1_{\{S_m\ne\varnothing\}}\mathcal{W}_m q_m^2 1 { S m = ∅ } W m q m 2 (74) and q m ≤ 1 q_m\le1 q m ≤ 1 C d 3 / 2 Cd^{3/2} C d 3/2
C d 3 / 2 ∑ m = i L − 1 P ( v m = 1 ) = O ( d 3 / 2 ) . Cd^{3/2}\sum_{m=i}^{L-1}\mathbb{P}(v_m=1)=O(d^{3/2}). C d 3/2 m = i ∑ L − 1 P ( v m = 1 ) = O ( d 3/2 ) . No independence between v m v_m v m
If v m = 0 v_m=0 v m = 0 (74) ,
1 { S m ≠ ∅ } W m q m 3 ≤ C d 3 / 2 1 { S m ≠ ∅ } q m 3 / 2 . 1_{\{S_m\ne\varnothing\}}\mathcal{W}_m q_m^3\le Cd^{3/2}1_{\{S_m\ne\varnothing\}}q_m^{3/2}. 1 { S m = ∅ } W m q m 3 ≤ C d 3/2 1 { S m = ∅ } q m 3/2 . We may now discard the incidence restrictions. Summing the three cases and absorbing the factor three from (67) proves (76) .
We next bound how long the decreasing sets S m S_m S m
Lemma C.9 (Occupation above a level). For all sufficiently large n n n a 0 ≤ a ≤ 1 a_0 \le a \le1 a 0 ≤ a ≤ 1
∑ m = i L − 1 P ( S m ≠ ∅ , q m ≥ a ) ≤ C d 3 / 2 a − 3 / 2 . (77) \sum_{m=i}^{L-1} \mathbb{P}(S_m \ne\varnothing,\ q_m \ge a) \le C d^{3/2}a^{-3/2}. \tag*{(77)} m = i ∑ L − 1 P ( S m = ∅ , q m ≥ a ) ≤ C d 3/2 a − 3/2 . (77) For 0 < a < a 0 0 < a < a_0 0 < a < a 0 L L L
Proof. Let σ a \sigma_a σ a { i , … , L − 1 } \{i,\ldots,L-1\} { i , … , L − 1 } S m ≠ ∅ S_m \ne\varnothing S m = ∅ q m ≥ a q_m \ge a q m ≥ a σ a = ∞ \sigma_a=\infty σ a = ∞ F m \mathcal{F}_m F m q d q_d q d { σ a = m } \{\sigma_a=m\} { σ a = m } m m m S ℓ = ∅ S_\ell=\varnothing S ℓ = ∅ ℓ ≥ m + U m \ell\ge m+U_m ℓ ≥ m + U m S m S_m S m S ℓ S_\ell S ℓ S m S_m S m U m U_m U m m m m
For a ≥ a 0 a \ge a_0 a ≥ a 0 { σ a = m } \{\sigma_a=m\} { σ a = m } F m \mathcal{F}_m F m
E [ 1 { σ a = m } U m ] = E [ 1 { σ a = m } τ ( S m ) p 0 ] ≤ C d 3 / 2 a − 3 / 2 P ( σ a = m ) . \mathbb{E}\left[1_{\{\sigma_a=m\}}U_m\right]
=
\mathbb{E}\left[1_{\{\sigma_a=m\}}\frac{\tau(S_m)}{p_0}\right]
\le C d^{3/2}a^{-3/2}\mathbb{P}(\sigma_a=m). E [ 1 { σ a = m } U m ] = E [ 1 { σ a = m } p 0 τ ( S m ) ] ≤ C d 3/2 a − 3/2 P ( σ a = m ) . Summing over the disjoint first-visit events proves (77) . This conditioning is legitimate because m ≥ i m \ge i m ≥ i m m m L L L □ \square □
Proof of Theorem C.1. For 0 ≤ q ≤ 1 0 \le q \le1 0 ≤ q ≤ 1 q 3 / 2 = ∫ 0 1 3 2 a 1 / 2 1 { q ≥ a } d a q^{3/2}=\int_0^1 \frac{3}{2}a^{1/2}1_{\{q\ge a\}}\,da q 3/2 = ∫ 0 1 2 3 a 1/2 1 { q ≥ a } d a
∑ m = i L − 1 E [ 1 { S m ≠ ∅ } q m 3 / 2 ] = ∫ 0 1 3 2 a 1 / 2 ∑ m = i L − 1 P ( S m ≠ ∅ , q m ≥ a ) d a ≤ L a 0 3 / 2 + C d 3 / 2 ∫ a 0 1 d a a ≤ C d 3 / 2 log n . \begin{aligned}
\sum_{m=i}^{L-1}\mathbb{E}\left[1_{\{S_m\ne\varnothing\}}q_m^{3/2}\right]
=
\int_0^1 \frac{3}{2}a^{1/2}\sum_{m=i}^{L-1}\mathbb{P}(S_m\ne\varnothing,q_m\ge a)\,da \\
&\le La_0^{3/2}+Cd^{3/2}\int_{a_0}^1\frac{da}{a}
\le Cd^{3/2}\log n.
\end{aligned} m = i ∑ L − 1 E [ 1 { S m = ∅ } q m 3/2 ] = ∫ 0 1 2 3 a 1/2 m = i ∑ L − 1 P ( S m = ∅ , q m ≥ a ) d a ≤ L a 0 3/2 + C d 3/2 ∫ a 0 1 a d a ≤ C d 3/2 log n . The final step uses (75) and log ( 1 / a 0 ) ≤ 2 log n \log(1/a_0)\le2\log n log ( 1/ a 0 ) ≤ 2 log n a 0 ≥ n − 2 a_0\ge n^{-2} a 0 ≥ n − 2
E D i 2 ≤ C ( 1 + d 3 / 2 ) + C d 3 log n ≤ C ( log n ) 4 . (78) \mathbb{E}D_i^2\le C(1+d^{3/2})+Cd^3\log n\le C(\log n)^4. \tag*{(78)} E D i 2 ≤ C ( 1 + d 3/2 ) + C d 3 log n ≤ C ( log n ) 4 . (78) Average over C i C_i C i (78) in (63) . This gives Var ( T n ) ≤ C n ( log n ) 4 \operatorname{Var}(T_n)\le Cn(\log n)^4 Var ( T n ) ≤ C n ( log n ) 4 n n n C C C n ≥ 3 n\ge3 n ≥ 3 0 ≤ T n ≤ 10 n 0\le T_n\le10n 0 ≤ T n ≤ 10 n
For every fixed 0 < η < 1 / 2 0<\eta<1/2 0 < η < 1/2 η \eta η 1 − η 1-\eta 1 − η T n T_n T n O η ( n log 2 n ) O_\eta(\sqrt{n}\log^2 n) O η ( n log 2 n ) m n m_n m n m n m_n m n
Cap changes and the center comparison
The prefix proof supplies a second concentration input for Theorem B.1. That theorem assumes a concentration bound and proves the center comparisons independently of how the bound is obtained. We apply it here using the variance bound of Theorem C.1, together with the cap identities already proved in Section 7. Put
W n = min { H n − 1 , 10 n } , V n = min { H n − 1 , 16 n } , e n = E T n n , P n ( j ) = P ( H n > j ) . W_n=\min\{H_n-1,10n\},\qquad V_n=\min\{H_n-1,16n\},\qquad e_n=\frac{\mathbb{E}T_n}{n},\qquad P_n(j)=\mathbb{P}(H_n>j). W n = min { H n − 1 , 10 n } , V n = min { H n − 1 , 16 n } , e n = n E T n , P n ( j ) = P ( H n > j ) . Corollary C.10. The variance and tail bounds of Theorem C.1 hold also for W n W_n W n V n V_n V n e n → α 3 e_n\to\alpha_3 e n → α 3 c ≥ 0 c\ge0 c ≥ 0 c ≠ α 3 c\ne\alpha_3 c = α 3
P n ( ⌊ c n ⌋ ) ⟶ { 1 , c < α 3 , 0 , c > α 3 . P_n(\lfloor cn\rfloor)\longrightarrow
\begin{cases}
1, & c<\alpha_3,\\
0, & c>\alpha_3.
\end{cases} P n (⌊ c n ⌋) ⟶ { 1 , 0 , c < α 3 , c > α 3 . There is an absolute constant C C C n = min { n 1 , n 2 } n=\min\{n_1,n_2\} n = min { n 1 , n 2 } max { n 1 , n 2 } ≤ 3 n \max\{n_1,n_2\}\le3n max { n 1 , n 2 } ≤ 3 n n n n
e n 1 + n 2 ≥ min { e n 1 , e n 2 } − C n − 1 / 4 , e n + 1 ≥ e n − C n − 1 / 4 . (79) e_{n_1+n_2}\ge\min\{e_{n_1},e_{n_2}\}-Cn^{-1/4},\qquad e_{n+1}\ge e_n-Cn^{-1/4}. \tag*{(79)} e n 1 + n 2 ≥ min { e n 1 , e n 2 } − C n − 1/4 , e n + 1 ≥ e n − C n − 1/4 . (79) Proof. Set ρ = 2 ( 7 / 8 ) 10 < 1 \rho=2(7/8)^{10}<1 ρ = 2 ( 7/8 ) 10 < 1 T = T n T=T_n T = T n W = W n W=W_n W = W n V = V n V=V_n V = V n (36) –(37) show that the mean corrections from m n − 1 m_n-1 m n − 1 ρ n \rho^n ρ n ( 6 n + 1 ) ρ n (6n+1)\rho^n ( 6 n + 1 ) ρ n ρ n / 2 \rho^{n/2} ρ n /2 ( 6 n + 1 ) ρ n / 2 (6n+1)\rho^{n/2} ( 6 n + 1 ) ρ n /2
For the center claim, choose a fixed 0 < c < e − 2 0<c<e^{-2} 0 < c < e − 2 j = ⌊ c n ⌋ j=\lfloor cn\rfloor j = ⌊ c n ⌋ E T n ≥ j P n ( j ) = c n − o ( n ) \mathbb{E}T_n\ge jP_n(j)=cn-o(n) E T n ≥ j P n ( j ) = c n − o ( n ) (58) with k = 3 k=3 k = 3 E T n ≤ E H n ≤ 6 n + 8 [ 2 ( 7 / 8 ) 6 ] n \mathbb{E}T_n\le\mathbb{E}H_n\le6n+8[2(7/8)^6]^n E T n ≤ E H n ≤ 6 n + 8 [ 2 ( 7/8 ) 6 ] n c 0 ≤ e n ≤ 7 < 10 c_0\le e_n\le7<10 c 0 ≤ e n ≤ 7 < 10 c 0 > 0 c_0>0 c 0 > 0 P n ( j ) = P ( T n > j ) P_n(j)=\mathbb{P}(T_n>j) P n ( j ) = P ( T n > j ) 0 ≤ j < 10 n 0\le j<10n 0 ≤ j < 10 n P n ( j ) = P ( W n ≥ j ) P_n(j)=\mathbb{P}(W_n\ge j) P n ( j ) = P ( W n ≥ j ) j = 10 n j=10n j = 10 n
P ( ∣ T n − m n ∣ ≥ n 3 / 4 ) ≤ η n , η n = C ( log n ) 4 n ⟶ 0. (80) \mathbb{P}(|T_n-m_n|\ge n^{3/4})\le\eta_n,\qquad\eta_n=C\frac{(\log n)^4}{\sqrt n}\longrightarrow0. \tag*{(80)} P ( ∣ T n − m n ∣ ≥ n 3/4 ) ≤ η n , η n = C n ( log n ) 4 ⟶ 0. (80) Apply Theorem B.1 with k = 3 k=3 k = 3 B = 10 B=10 B = 10 a = c 0 a=c_0 a = c 0 A = 7 A=7 A = 7 δ = 1 / 4 \delta=1/4 δ = 1/4 (79) , in particular for the stated comparable sizes, and convergence with the proper strict-side limits. Uniqueness identifies the limit with α 3 \alpha_3 α 3 [16 ] , Theorem 1.1. The one-sided estimate (B.6) also gives, for every sufficiently large s s s N ≥ s 2 N\ge s^2 N ≥ s 2
e N ≥ e s − C ′ s − 1 / 4 . e_N\ge e_s-C's^{-1/4}. e N ≥ e s − C ′ s − 1/4 . □
For the comparable-size consequence, the coarser trial comparison gives a concrete error bound. With N = n 1 + n 2 N=n_1+n_2 N = n 1 + n 2 n = min ( n 1 , n 2 ) n=\min(n_1,n_2) n = min ( n 1 , n 2 ) e ∗ = min ( e n 1 , e n 2 ) e_*=\min(e_{n_1},e_{n_2}) e ∗ = min ( e n 1 , e n 2 ) ε = n − 1 / 4 \varepsilon=n^{-1/4} ε = n − 1/4 M = ⌊ ( e ∗ − 2 ε ) N ⌋ M=\lfloor(e_*-2\varepsilon)N\rfloor M = ⌊( e ∗ − 2 ε ) N ⌋ ( c 0 / 4 ) N ≤ M ≤ 7 N (c_0/4)N \le M \le7N ( c 0 /4 ) N ≤ M ≤ 7 N n n n C 3 = 27 C_3 = 27 C 3 = 27 N ≤ 4 n N \le4n N ≤ 4 n
27 M ε 3 n 3 ≤ 27 ⋅ 7 ⋅ 4 n n 9 / 4 = 756 n − 5 / 4 . (81) \frac{27M}{\varepsilon^3 n^3} \le\frac{27\cdot7\cdot4n}{n^{9/4}} = 756n^{-5/4}. \tag*{(81)} ε 3 n 3 27 M ≤ n 9/4 27 ⋅ 7 ⋅ 4 n = 756 n − 5/4 . (81) The restriction max ( n 1 , n 2 ) ≤ 3 n \max(n_1,n_2) \le3n max ( n 1 , n 2 ) ≤ 3 n N = n + 1 N = n + 1 N = n + 1 M = ⌊ m n − 2 n 3 / 4 ⌋ M = \lfloor mn - 2n^{3/4}\rfloor M = ⌊ mn − 2 n 3/4 ⌋ D 3 = 729 / 8 D_3 = 729/8 D 3 = 729/8 ( 729 / 8 ) M / ( ε 3 n 3 ) = O ( n − 5 / 4 ) (729/8)M/(\varepsilon^3n^3) = O(n^{-5/4}) ( 729/8 ) M / ( ε 3 n 3 ) = O ( n − 5/4 ) j = ⌊ ( 1 − ε ) M − N 3 / 4 ⌋ j = \lfloor(1-\varepsilon)M - N^{3/4}\rfloor j = ⌊( 1 − ε ) M − N 3/4 ⌋ n n n 10 N 10N 10 N
The deviation bounds above are about each statistic’s finite-size mean. The comparison inequalities are one-sided and do not give a two-sided rate for e n − α 3 e_n-\alpha_3 e n − α 3
References 