Earlier work and the new estimate

The location and the width of a threshold are different questions. Friedgut (Friedgut 1999, Theorem 1.3) proved a sharp threshold sequence for each fixed clause size, without asserting convergence of that sequence. Achlioptas and Peres (Achlioptas and Peres 2004, Theorems 1–2) used a weighted second moment to locate the threshold within \(O(k)\) of \(2^k\log2\) as \(k\) grows. Ding, Sly, and Sun (Ding et al. 2022, Theorem 1) proved the predicted limiting threshold for all sufficiently large \(k\). Carenini’s paper (Carenini 2026a, Corollary 1.2), made public on October 5, 2026, establishes the satisfiability conjecture for every fixed \(k\ge3\). We credit Carenini with priority for the resolution of the satisfiability conjecture. The companion (OpenAI 2026a, Theorem 1.1) establishes a limiting location for every fixed \(k\ge3\); its independent forcing argument gives the variance bound \(O_k(n^{1+2/k})\) for the capped last-satisfiable prefix \(\min(H_n-1,2^{k+1}n)\) (OpenAI 2026a, Proposition 3.3).

For transition width, Wilson (Wilson 2002, Corollary 4) proved an \(\Omega_k(\sqrt n)\) separation of central quantiles in the independent proper-clause model. We convert that separation into the variance lower bound, keeping the integer endpoints so the argument allows atoms. Carenini (Carenini 2026b, Corollaries 7.10–7.11) proves an \(O_{k,\eta}(n/\log n)\) window upper bound for fixed \(k\ge3\), including proper independent clauses. Her subsequent paper gives the polynomial window bound \(O_{k,\eta}(n^{1/2+1/k})\) and the hitting-time variance bound \(O_k(n^{1+2/k})\) (Carenini 2026a, Theorems 1.1 and 1.3); the window 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\), the companion (OpenAI 2026c) further removes the logarithmic loss in this paper’s upper bound.

Our upper bound uses the coordinate-omission form of the Efron–Stein inequality (Efron and Stein 1981; Boucheron et al. 2005). Deleting one clause leaves its \(k\) variables available for root-flip tests of the remaining solutions. When no other clause meets two of these variables, the \(k\) tests are independent and use clauses of length \(k-1\); we account separately for such collisions. A set of assignments that is easily killed by those shorter clauses must also have a short expected lifetime under \(k\)-clauses. The replacement of a shorter constraint by a block of native clauses has a qualitative predecessor in Friedgut’s half-cube argument (Friedgut 1999, Lemma 5.7); sequential conditioning on a residual assignment set is developed in Carenini (Carenini 2026b, 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\)-clause can kill.

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=\lfloor Bn\rfloor\). If deleting \(C_i\) while preserving the other clause indices delays the capped first failure by \(D_i\), then \[\mathop{\mathrm{Var}}(T_{n,B})\le\sum_{i=1}^{L}\mathbb ED_i^2.\] The delay \(D_i\) counts the prefixes at which restoring \(C_i\) destroys satisfiability, so \(D_i^2\) counts ordered pairs of such prefixes. The problem is to control this occupation time.

Here is the shorter-clause estimate used for that purpose. A collection of clauses kills \(S\subseteq\{0,1\}^u\) if no member of \(S\) satisfies every clause. Let \(q_d(S)\) be the probability that \(d\) independent proper \((k-1)\)-clauses kill \(S\), and let \(\tau_k(S)\) be the expected number of independent proper \(k\)-clauses through its first kill. For \(u\ge k\), \(d\ge1\), and \(\beta=k/(k-1)\), we prove in Section 2 that \[\tau_k(S)q_d(S)^\beta\le C_kd^\beta.\] This estimate holds for every assignment set, with no lower cutoff on \(q_d(S)\).

Section 3 connects this statement to clause deletion. Call the variables of \(C_i\) its roots, and fix them to the unique values that falsify \(C_i\). Let \(S_m\) be the nonroot parts of solutions of the prefix with \(C_i\) omitted and the roots fixed this way. A clause disjoint from the roots is an ordinary \(k\)-clause on the nonroots. A clause meeting one root and satisfied by that root hides a \((k-1)\)-clause: its nonroot part becomes a constraint when that root is flipped. If restoring \(C_i\) destroys satisfiability, each allowed root flip must fail. In the absence of collisions this gives \(k\) independent tests killing \(S_m\).

Conditional on the exposed incidence pattern, let \(Z\) be the number of clauses meeting the roots and put \(d=\max\{1,Z\}\). The lifetime estimate bounds both the expected remaining duration of a deletion event and the total time spent at levels \(q_d(S_m)\ge a\). Write \(q=q_d(S_m)\). The \(k\) independent tests contribute \(q^k\), while the expected remaining duration costs a factor \(q^{-\beta}\). Integrating the resulting \(q^{k-\beta}\) over time costs a second lifetime factor: the expected occupation above level \(a\) is bounded by a constant times \(a^{-\beta}\). The near-zero part of the resulting integral is therefore \[\int a^{\,k-2\beta-1}\,da.\] At \(k=3\), \(k=2\beta\) and the finite cap produces a logarithm; for \(k\ge4\), \(k>2\beta\) and the integral is bounded. Section 4 then averages the root counts and proves the capped upper bound. Exponential tails remove a sufficiently late cap. Wilson’s quantile bound supplies the separate lower-bound argument.

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 8 determines the limits of the two estimates for arbitrary assignment sets. Appendix 9 compares proper-clause models at different sizes, and Appendix 10 gives a second three-clause proof based on prefix exposure and incidence truncation.

Replacing one shorter clause

For a nonempty set \(S\), a coordinate is frozen if every member of \(S\) has the same value there. If \(b\) coordinates are frozen, the probability that one proper \(s\)-clause kills \(S\) is \[ h_s(S)=\frac{(b)_s}{2^s(u)_s},\qquad 1\le s\le u, \tag{3}\] where \((a)_s=a(a-1)\cdots(a-s+1)\), with value zero for a nonnegative integer \(a<s\). To kill \(S\), every literal of the clause must be false for every assignment in \(S\). Its variables must therefore be frozen, and each sign must oppose their common values. This characterizes the killing clauses and proves the formula.

Write \(h=h_r(S)\). Then \(0\le h\le2^{-r}\le1/4\). If \(b\ge k\), \[ h_k(S)=h\frac{b-r}{2(u-r)}\ge\frac1k h^\beta. \tag{4}\] In fact \(b-r\ge b/k\), \(u-r\le u\), and \[h=\frac1{2^r}\prod_{j=0}^{r-1}\frac{b-j}{u-j} \le \left(\frac b{2u}\right)^r.\] Substituting these bounds into the equality proves (4). Its hypothesis matters. For the cylinder whose first \(r\) coordinates are fixed to zero, \[ h_k(S)=0,\qquad h_r(S)=\frac1{2^r\binom ur}>0. \tag{5}\] No single \(k\)-clause kills this set. A sufficiently long block can still do so through the joint effect of its clauses.

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 (Carenini 2026b, Theorem 4.3). The uniform additive block estimate in Lemma 2 takes the place of the cutoff-dependent comparison of single-clause killing probabilities in (Carenini 2026b, Lemma 6.1); the exceptional case \(b=k-1\) above rules out a cutoff-free positive power lower bound for \(h_k\) in terms of \(h_r\).

These inequalities also hold conditionally for a set \(S\) measurable with respect to an exposed history, provided the comparison clauses remain independent of that history. Apply the deterministic-set inequality at each realization of \(S\). In particular, sequential replacement conditions only on other independent clause positions; it does not condition the fresh clauses on a satisfiability event.

What the two filtrations reveal

Fix \(i\) and condition on a value of \(C_i\). Until the end of Section 4, probabilities and expectations refer to this conditional law. The bounds will be uniform in the fixed clause. Its set \(R\) of \(k\) variables will be called the roots, and \(t\in\{0,1\}^{R}\) is their unique assignment falsifying \(C_i\). There are \(u=n-k\ge k\) remaining variables. Write \(B_m=B_m^{(i)}\).

For \(i\le m<L\), define the deletion event \[ A_m=\{B_m\in\mathrm{SAT},\ B_m\wedge C_i\notin\mathrm{SAT}\} =\{T\le m<T^{(i)}\}. \tag{12}\] On this event every solution of \(B_m\) has root values \(t\). The two prefix processes agree before \(i\), and hence \[ D_i=\sum_{m=i}^{L-1}\mathbf1_{A_m}. \tag{13}\] In particular \(D_L=0\): the displayed sum is then empty. The upper endpoint is \(L-1\) because both failure times have already been stopped at \(L\).

For \(i\le m\le L\), define \(S_m\subseteq\{0,1\}^{u}\) to be the nonroot restrictions of solutions of \(B_m\) with root values \(t\). The sets are defined on every outcome and decrease with \(m\); for \(m<L\), \(A_m\) implies that \(S_m\) is nonempty. We need to reveal this set while retaining independent randomness to test whether one of its assignments allows a root to be flipped.

The root type of a clause records the subset of its variables in \(R\) and the signs of their literals. A clause is 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\). Let \(O\) and \(Q\) be the ordinary and test indices among \(\{1,\ldots,L\}\setminus\{i\}\).

Reveal the root type at every such index through \(L\). At indices in \(\{1,\ldots,L\}\setminus(\{i\}\cup O\cup Q)\), also reveal the complete signed nonroot part. Let \(\mathcal E\) be the sigma-field generated by this static information. Thus \(O,Q\) and the counts \[ \begin{split} 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{split} \tag{14}\] are \(\mathcal E\)-measurable. We call a clause counted by \(V\) a collision. The ordinary clauses and the nonroot parts of test clauses have not yet been revealed.

A test clause is already true under \(t\), so its nonroot part imposes no condition on \(S_m\). Consequently \(S_m\) is measurable with respect to \[\mathcal G_m =\sigma\bigl(\mathcal E,\ C_j:j\in O,\ j\le m\bigr).\] We will bound the probability of \(A_m\) under this filtration, which knows \(S_m\) but leaves the test parts hidden. To bound the remaining duration on \(A_m\), we also need to know whether \(A_m\) has occurred. For that purpose, enlarge the filtration by revealing the past test parts: \[\mathcal F_m^* =\sigma\bigl(\mathcal G_m,\ \text{nonroot parts of }C_j:j\in Q,\ j\le m\bigr).\] The full baseline prefix \(B_m\), and thus \(A_m\), is \(\mathcal F_m^*\)-measurable. Under \(\mathcal G_m\), the past test parts remain independent with their original conditional laws. Under either filtration, the future ordinary clauses remain independent uniform proper \(k\)-clauses. Both assertions follow from Lemma 6. The static information includes future nonordinary data, but it includes no future ordinary contents.

Flipping a root gives an independent test

Recall that \(q_d(S)\) is the probability that \(d\) independent proper \((k-1)\)-clauses kill \(S\). Here \(d=\max\{1,Z\}\) is already known under \(\mathcal E\). Put \[\beta=\frac{k}{k-1},\qquad q_m=q_d(S_m).\] For \(j\in R\), let \(\mathcal I_{j,m}\) be the test indices through \(m\) whose root is \(j\), and put \(s_{j,m}=|\mathcal I_{j,m}|\). Then \(s_{j,m}\le Z\le d\). Let \(J_m\subseteq R\) consist of roots \(j\) for which no collision through \(m\) has exactly one root literal true under \(t\), at root \(j\). A collision can exclude at most one root, so \[ |J_m|\ge k-V. \tag{15}\] The index sets and counts in this paragraph are \(\mathcal E\)-measurable.

The proof has kept the actual incidence count \(d\), rather than discarding environments where it exceeds a chosen cutoff. We next bound duration with that same parameter; its moments will be averaged only after all conditional estimates have been proved.

From ordinary clauses to chronological duration

For this comparison, keep the actual schedule and ordinary clauses through \(L\). At every index after \(L\), append an auxiliary independent uniform proper \(k\)-clause on the \(u\) nonroots. The continuation is independent of the entire original process.

For \(i\le m<L\) and \(S_m\ne\varnothing\), let \(K_m\) be the number of ordinary clauses strictly after \(m\), including the first one that completes the killing of the original set \(S_m\). Use the continuation if necessary. Let \(U_m\) be the number of chronological indices after \(m\) through that killing index. Set \(K_m=U_m=0\) if \(S_m=\varnothing\). The conditional product law and the independent continuation give \[ \mathbb E[K_m\mid\mathcal F_m^*] =\mathbb E[K_m\mid\mathcal G_m]=\tau_k(S_m). \tag{17}\] There are at most \(Z\) nonordinary indices between \(m\) and the kill: every one occurs before or at \(L\), and the deleted index \(i\) is not after \(m\). Thus, pathwise, \[ 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{18}\] The continuation makes these statements valid even when no pre-cap ordinary clause completes the kill.

Both the root-test probability and the remaining duration are now controlled by the same set \(S_m\). We still have to bound how long that set can spend at each level of \(q_d(S_m)\), and then average the incidence counts.

Time spent above a level

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 \(\mathcal G_m\), even though \(\mathcal E\) has already exposed future nonordinary data.

To apply the occupation bound to the squared deletion delay, first consider an environment with \(V=0\). All \(k\) root tests are then available. Lemma 7 supplies the factor \(q_m^k\) in the weighted-delay bound (20). On a nonempty \(S_m\), (21) gives \[W_mq_m^k=(W_mq_m^\beta)q_m^{k-\beta} \le C_kd^\beta q_m^{k-\beta}.\] The remaining occupation sum has exponent \[\gamma=k-\beta=\frac{k(k-2)}{k-1}.\] The lifetime estimate has controlled the remaining deletion duration; Lemma 9 contributes a second lifetime factor \(a^{-\beta}\) by bounding the time spent above level \(a\). The resulting layer-cake integral contains \(a^{\gamma-\beta-1}\). Its integrability at zero is determined by \(\gamma-\beta=k(k-3)/(k-1)\), which is zero exactly at \(k=3\).

The cost of collisions

The number \(V\) of collisions through the whole cap is fixed under \(\mathcal E\). With no collisions all \(k\) root tests are available. One collision may remove one test; two or more collisions will be handled by the deterministic cap.

The one-collision contribution contains \(d^\beta\). Its average therefore needs the joint distribution of incidences and collisions, not just an upper bound on the probability of a collision.

Joint moments of incidences and collisions

These moments are taken with the deleted clause fixed and the other clauses still random. Once \(\mathcal E\) is fixed, \(Z\) and \(V\) are known; their rarity returns only when we average over \(\mathcal E\).

Completing the capped upper bound

Exact cap comparisons

Fix \(k\ge3\), put \(q_k=1-2^{-k}\), and write \(P_n(m)=\mathbb P(H_n>m)\). We also write \(F_{n,m}=F_m\) when displaying the number of variables. Each assignment survives \(m\) independent proper clauses with probability \(q_k^m\). The expected number of surviving assignments therefore gives \[ P_n(m)\le \min\{1,2^nq_k^m\}\qquad(m\in\mathbb Z_{\ge0}). \tag{30}\] In particular, \(H_n\) is almost surely finite and has finite moments of every order. For integer caps \(a\ge1\) and \(b\ge0\), define \[X_a=\min\{H_n,a\},\qquad V_b=\min\{H_n-1,b\}.\] These have the exact prefix identities \[ 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{31}\] All clause counts in these identities are integers.

Recall the first-moment cap density \[ U_k=\frac{\log2}{-\log q_k}. \tag{37}\] For any fixed \(B>U_k\), let \(\rho_{k,B}=2q_k^B<1\). The cap \(a=\lfloor Bn\rfloor\) satisfies \[ \xi_{n,a}=q_k^{\lfloor Bn\rfloor-Bn}\rho_{k,B}^n \le q_k^{-1}\rho_{k,B}^n. \tag{38}\] The factor \(q_k^{-1}\) accounts for the floor; a ceiling cap needs no such factor. Equality \(B=U_k\) does not give exponential decay by this argument. In particular, \(B=2^{k+1}\) is sufficient for every fixed \(k\ge3\).

The mean correction is more precise than its normalized limiting effect: for \(a=\lfloor Bn\rfloor\) with \(B>U_k\), \[ 0\le\frac{\mathbb EH_n-\mathbb ET_{n,B}}n \le\frac{2^kq_k^{-1}}n\rho_{k,B}^n. \tag{41}\] Theorem 1.1 of (OpenAI 2026a) gives a unique positive finite threshold \(\alpha_k\) in exactly this proper-clause model. It also implies \[ \frac{\mathbb EH_n}{n}\longrightarrow\alpha_k, \qquad \frac{\mathbb ET_{n,B}}n\longrightarrow\alpha_k \quad(B>U_k). \tag{42}\] Here is the explicit expectation argument. Take \(b=2^{k+1}n\). The theorem and monotonicity imply \(\min\{H_n-1,b\}/n\to\alpha_k\) in probability; the first-moment bound implies \(\alpha_k\le U_k<2^{k+1}\). The bounded statistic therefore converges in mean. Proposition 13 first compares it with \(X_b\), then with \(H_n\); the errors after the one-index shift are exponentially small. Equation (41) handles the remaining caps. The same conclusion holds for last-satisfiable caps of density \(B>U_k\). These limits give no rate for \(\mathbb EH_n-\alpha_k n\) or for the corresponding capped bias. The concentration in (40) is centered at each finite-size expectation.

A center theorem with an explicit concentration input

For fixed \(k\ge3\) and \(n\ge k\), let \(H_n\) be the index of the first unsatisfiable prefix of independent uniform proper \(k\)-clauses on \(n\) variables, and write \(P_n(j)=\mathbb P(H_n>j)\) for integers \(j\ge0\). Fix a real \(B>0\) and set \[L_n=\lfloor Bn\rfloor,\qquad T_n=\min\{H_n,L_n\},\qquad \mu_n=\mathbb ET_n,\qquad e_n=\mu_n/n.\] The endpoint for this first-unsatisfiable convention is strict: \[ P_n(j)=\mathbb P(T_n>j)\qquad(0\le j<L_n). \tag{57}\] At \(j=L_n\), the probability on the right is zero, whereas \(P_n(L_n)\) need not vanish. All statements below use only indices strictly below the cap when applying (57).

The theorem allows an arbitrary vanishing concentration error; it does not require a specified polynomial rate. In particular, Chebyshev’s inequality supplies (58) whenever \[ \mathop{\mathrm{Var}}(T_n)=o\bigl(n^{2-2\delta}\bigr). \tag{63}\] 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

At \(k=3\) the constants are exactly \(C_3=27\) and \(D_3=729/8\). The stronger weighted bound will be used for unequal blocks. The coarser bound remains useful when the block sizes are known to be comparable.

From a random clause count to a center

We first record the integer step needed in both center comparisons. From (58) and (57), for every integer \(0\le j<L_n\) and all sufficiently large \(n\), \[ \begin{aligned} j\le\mu_n-n^{1-\delta}&\quad\Longrightarrow\quad P_n(j)\ge1-\eta_n,\\ j\ge\mu_n+n^{1-\delta}&\quad\Longrightarrow\quad P_n(j)\le\eta_n. \end{aligned} \tag{68}\] Because \(\eta_n\to0\), its tail supremum \(\overline\eta_n=\sup_{v\ge n}\eta_v\) also tends to zero. This will provide uniformity when one block is arbitrarily larger than the other.

Suppose, for a fixed \(a_0>0\), that \(a_0N\le M\le AN\), \(0<\varepsilon\le1/2\), and \(Q_{\mathrm{dil}}\ge1-\zeta\). The number of inserted clauses is \(J\sim\operatorname{Bin}(M,1-\varepsilon)\). Conditional on \(J\), the inserted clauses have exactly the independent proper-clause law, so \(Q_{\mathrm{dil}}=\mathbb EP_N(J)\). Put \[j=\left\lfloor(1-\varepsilon)M-N^{1-\delta}\right\rfloor.\] For all sufficiently large \(N\), the lower bound on \(M\) gives \(j\ge0\), and \(j\le M\le AN<L_N\) because \(A<B\). Also \(\mathop{\mathrm{Var}}(J)\le AN\), whence \[\mathbb P(J<j)\le A N^{-1+2\delta},\qquad Q_{\mathrm{dil}}\le P_N(j)+\mathbb P(J<j).\] The second inequality uses monotonicity of \(P_N\). If \(\zeta+AN^{-1+2\delta}+\eta_N<1\), the upper implication in (68) forces \(j<\mu_N+N^{1-\delta}\). The floor in the definition of \(j\) then gives \[ e_N>\frac{(1-\varepsilon)M}{N}-2N^{-\delta}-N^{-1} \ge\frac{(1-\varepsilon)M}{N}-3N^{-\delta}. \tag{69}\] We will apply this implication with all three errors tending to zero.

The comparison (62) is one-sided. It proves convergence of the finite-size means, but gives no two-sided estimate for \(\mu_n-\alpha n\) on the fluctuation scale of the variance theorem.

Checking the inputs for the variance estimates

For the main application put \(B_k=2^{k+1}\) and take \(B=B_k\); at \(k=3\) we may also take \(B=10\). We verify the anchors without assuming threshold convergence. Let \(q_k=1-2^{-k}\). The assignment first moment gives \(P_n(j)\le2^nq_k^j\), hence, for every positive integer \(d\), \[ \mathbb EH_n=\sum_{j=0}^{\infty}P_n(j) \le dn+2^k(2q_k^d)^n. \tag{71}\] For \(d=2^k\), one has \(2q_k^{2^k}<2/e<1\). For \(k=3\), the sharper choice \(d=6\) satisfies \(2(7/8)^6<1\). Since \(T_n\le H_n\), it follows that eventually \[ e_n\le A_k<B, \qquad A_k=\begin{cases}7,&k=3,\\2^k+1,&k\ge4.\end{cases} \tag{72}\]

For the positive anchor, fix \(0<c<\min\{e^{-2},B\}\) and let \(j=\lfloor cn\rfloor\). Lemma 15 gives \(P_n(j)=1-O_c(n^{-2})\) for the same independent proper-clause model. Since \(c<B\), one has \(j<L_n\) for sufficiently large \(n\). Therefore \(\mu_n\ge jP_n(j)=cn-o(n)\), and with \(c_0=c/2\) we obtain the full anchors \[ c_0\le e_n\le A_k<B \qquad\text{for all sufficiently large }n. \tag{73}\]

The capped variance theorem gives \[\frac{\mathop{\mathrm{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}\] which tends to zero for every fixed \(0<\delta<1/2\). Theorem 19 now applies with \(a=c_0\) and \(A=A_k\). Its strict-side limit is the same \(\alpha_k\) as in the threshold companion (OpenAI 2026a, 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 (59)–(60) hold for every such fixed \(\delta\).

The weaker polynomial variance estimate of the threshold companion (OpenAI 2026a, Proposition 3.3) can be used as a separate input. For \(a=B_kn\) and the same last-SAT cap \(b=a\), the exact identity in Proposition 13 is \[\min\{H_n-1,a\}=\min\{H_n,a\}-1+\mathbf 1_{\{H_n>a\}}.\] That proposition gives \(\mathop{\mathrm{Var}}(\min\{H_n,a\})\le\mathop{\mathrm{Var}}(\min\{H_n-1,a\})\). Consequently the companion’s \(O_k(n^{1+2/k})\) bound verifies (63) for every \(0<\delta<(k-2)/(2k)\), including the companion’s stated choice \(\delta=(k-2)/(4k)\). This substitution uses the companion’s own variance estimate. The range \(\delta<1/2\) for the local variance bounds is also strict; no endpoint assertion is made.

Replacing pairs by triples on a finite variable set

For an integer \(u\ge3\) and \(S\subseteq\{0,1\}^u\), a collection of clauses kills \(S\) if no member of \(S\) satisfies all of them. A uniform proper \(r\)-clause here is chosen from the \(2^r\binom ur\) signed clauses on \(r\) distinct variables. For an integer \(d\ge1\), let \(q_d(S)\) be the probability that \(d\) independent uniform proper two-clauses kill \(S\). Let \(\tau(S)\) be the expected length of the first prefix of independent uniform proper three-clauses whose conjunction kills \(S\), and set \(\tau(\varnothing)=0\). For nonempty \(S\), this expectation is finite because the probability of survival after \(m\) clauses is at most \(|S|(7/8)^m\).

Replacing a shorter constraint by native clauses has a qualitative predecessor in Friedgut’s half-cube argument (Friedgut 1999, Lemma 5.7). The residual-set conditioning used below is the averaged replacement method of Carenini (Carenini 2026b, Theorem 4.3, Lemma 6.1, and Corollary 6.2); the following bound supplies the finite-variable pair-to-triple estimate needed here.

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\) is sufficiently large, in particular \(n\ge6\); the final constant will cover the remaining sizes. Keep the original clause indices, and for \(1\le i\le L\) and integer \(m\ge0\) put \[B_m^{(i)}=\bigwedge_{\substack{1\le j\le m\\j\ne i}}C_j, \qquad T^{(i)}=\min\bigl\{\inf\{m\in\mathbb Z_{\ge0}: B_m^{(i)}\notin\mathrm{SAT}\},L\bigr\}, \qquad D_i=T^{(i)}-T_n,\] with \(\inf\varnothing=\infty\). Then \(D_i\ge0\), and \(T^{(i)}\) does not use coordinate \(C_i\). The coordinate-omission inequality, Lemma 5, gives \[ \mathop{\mathrm{Var}}(T_n)\le\sum_{i=1}^{L}\mathbb ED_i^2. \tag{77}\] Its martingale proof applies to precisely these index-preserving deletions and to the cap \(L=10n\).

Fix \(i\) and condition on any particular clause \(C_i\). Until the end of the variance proof, probabilities refer to this conditional law; the other clauses remain independent and uniform. We call indices other than \(i\) the baseline indices for this deletion. Let \(R\) be the three variables of \(C_i\), called its roots, and let \(t\in\{0,1\}^{R}\) be their unique values that falsify \(C_i\). Put \(u=n-3\), abbreviate \(B_m=B_m^{(i)}\), and let \(\mathcal F_m=\sigma(C_j:1\le j\le m,\ j\ne i)\) under the conditional law. In particular, \(u\ge3\).

For \(i\le m<L\), define \[ A_m=\{T_n\le m<T^{(i)}\} =\{B_m\in\mathrm{SAT},\ B_m\wedge C_i\notin\mathrm{SAT}\}. \tag{78}\] On \(A_m\), every solution of \(B_m\) has root values \(t\). The two processes agree before index \(i\), so \[ D_i=\sum_{m=i}^{L-1}\mathbf 1_{\{A_m\}}. \tag{79}\] In particular \(D_L=0\). For every \(m\ge i\), let \(S_m\subseteq\{0,1\}^u\) be the nonroot restrictions of solutions of \(B_m\) with root values \(t\). The sets are decreasing, \(\mathcal F_m\)-measurable, and nonempty on \(A_m\).

A clause is ordinary if it uses only nonroots. A fresh clause is ordinary with probability \[p_0=\frac{\binom{u}{3}}{\binom n3},\] which is bounded below by a positive absolute constant for sufficiently large \(n\). Let \(U_m\) be the number of trials after index \(m\), including the last trial, until the ordinary clauses among them kill the original set \(S_m\); put \(U_m=0\) when \(S_m=\varnothing\). These trials may continue past \(L\). Conditional on \(\mathcal F_m\), the future ordinary clauses are independent uniform proper triples on the nonroots. Their arrival gaps, counting the arrival trial, are independent geometric variables of mean \(1/p_0\), independent of the ordinary clauses themselves. Conditioning first on the latter clauses and summing the means of the gaps through their killing time proves \[ \mathbb E[U_m\mid\mathcal F_m]=\frac{\tau(S_m)}{p_0}. \tag{80}\] The assertion uses the fact that only the prefix has been revealed; for \(m\ge i\), all trials after \(m\) remain fresh even after fixing \(C_i\).

The three root-flip tests

The weight in (81) 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\) records the roots it contains and the signs of its root literals. For \(j\in R\), let \(\mathcal I_{j,m}\) be the indices other than \(i\), at most \(m\), whose clause contains exactly root \(j\) and whose root literal is true at \(t\); put \(s_{j,m}=|\mathcal I_{j,m}|\). Call a clause containing at least two roots a collision, and let \(v_m\) count such clauses at baseline indices through \(m\). Finally, let \(J_m\subseteq R\) contain those roots \(j\) for which no collision through \(m\) has exactly one root literal true under \(t\), at root \(j\). A collision can exclude at most one root, hence \[ |J_m|\ge3-v_m. \tag{82}\]

Let \(\mathcal G_m\) reveal all these prefix types and the entire signed nonroot part of every baseline clause through \(m\), except at indices in \(\bigcup_{j\in R}\mathcal I_{j,m}\). Thus \(\mathcal G_m\subseteq\mathcal F_m\). The hidden clauses are already satisfied by their root literal at \(t\), so their nonroot parts do not affect \(S_m\). In particular \(S_m,J_m,s_{j,m},v_m\), and \(\mathcal W_m\) are \(\mathcal G_m\)-measurable. Conditional on \(\mathcal G_m\), the hidden nonroot parts are independent uniform proper two-clauses on the \(u\) nonroots. Indeed, conditioning the independent clauses on their types separately preserves their product law, and revealing nonroot parts at other indices does not change it.

Put \[d=\lceil\log n\rceil,\qquad q_m=q_d(S_m).\]

Truncating incidence counts and summing occupation

It remains to sum the right side of (81). The tests make deletion unlikely when \(q_m\) is small. When it is large, the lifetime estimate limits both the remaining deletion time and the number of indices at that level. We first isolate the rare prefixes for which too many tests or collisions are present.

With \(K=64\), set \[ a_0=\frac{4Kd}{u^2}=\frac{256d}{(n-3)^2}. \tag{87}\] For sufficiently large \(n\), \(a_0<1\). On \(S_m\ne\varnothing\), \[ \mathcal W_m q_m^{3/2}\le C d^{3/2}. \tag{88}\] For \(q_m\ge a_0\), this follows by applying Proposition 24 with \(a=q_m\), and then using \(\mathcal W_m\le\tau(S_m)/p_0\). For \(q_m<a_0\), including \(q_m=0\), use \(\mathcal W_m\le L\) and \[ L a_0^{3/2} =10n\left(\frac{256d}{(n-3)^2}\right)^{3/2} =O(d^{3/2}n^{-2})\le C d^{3/2}. \tag{89}\]

We next bound how long the decreasing sets \(S_m\) can remain nonempty at a given pair-killing level. The first visit to that level determines a set whose future lifetime controls all subsequent visits.

For every fixed \(0<\eta<1/2\), the \(\eta\) and \(1-\eta\) quantiles of \(T_n\) therefore lie within \(O_\eta(\sqrt n\log^2 n)\) of \(m_n\). The probability outside any diverging multiple of this scale tends to zero. These statements use the finite-size mean \(m_n\).

Cap changes and the center comparison

The prefix proof supplies a second concentration input for Theorem 19. 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 21, together with the cap identities already proved in Section 7. Put \[W_n=\min\{H_n-1,10n\},\qquad V_n=\min\{H_n-1,16n\}, \qquad e_n=\frac{\mathbb ET_n}{n},\qquad P_n(j)=\mathbb P(H_n>j).\]

For the comparable-size consequence, the coarser trial comparison gives a concrete error bound. With \(N=n_1+n_2\), \(n=\min(n_1,n_2)\), \(e_*=\min(e_{n_1},e_{n_2})\), set \(\varepsilon=n^{-1/4}\) and \(M=\lfloor(e_*-2\varepsilon)N\rfloor\), as in the proof of Theorem 19. The anchors give \((c_0/4)N\le M\le7N\) for large \(n\). Since \(C_3=27\) in Lemma 20 and \(N\le4n\), (65) bounds the loss by \[ \frac{27M}{\varepsilon^3n^3} \le\frac{27\cdot7\cdot4n}{n^{9/4}} =756n^{-5/4}. \tag{95}\] The restriction \(\max(n_1,n_2)\le3n\) is used only for this numerical bound. For neighboring sizes, set \(N=n+1\) and \(M=\lfloor m_n-2n^{3/4}\rfloor\). The constant \(D_3=729/8\) gives loss \((729/8)M/(\varepsilon^3n^3)=O(n^{-5/4})\). In either case, the count-transfer index \(j=\lfloor(1-\varepsilon)M-N^{3/4}\rfloor\) is nonnegative for large \(n\) and lies strictly below \(10N\), as required in (69).

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-\alpha_3\).