Variance of the Random k-SAT Hitting Time

1 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\ge4, we prove that its variance has order n, where n is the number of variables. For three-literal clauses the variance lies between positive constant multiples of n and n\log n.

A proper k-clause is a disjunction of literals on k distinct variables. Fix k\ge3 and n\ge k, and let C_1,C_2,\ldots be independent uniform choices from the 2^k\binom nk proper signed clauses on n variables. Signs are independent and fair; whole clauses may repeat. Put

For a fixed B>0, the capped first failure time is T_{n,B}=\min\{H_n,\lfloor Bn\rfloor\}. Each assignment survives a clause with probability 1-2^{-k}, so

Thus H_n is almost surely finite and has finite moments.

All constants concern fixed k. The lower condition on the cap is substantive: an early cap can stop the process before its random transition. In the proof, it is enough to have integer caps L_n=O(n) with \Pr(H_n>L_n-1)\le1/4 eventually; B>U_k is an explicit sufficient condition. This argument leaves a logarithmic gap for three-literal clauses; the companion paper [17] closes it and proves \Var(H_n)=\Theta(n) for the uncapped proper 3-clause process.

The identity \Pr(F_m\text{ is satisfiable})=\Pr(H_n>m) turns these variance bounds into bounds on the transition window. Between any fixed probability levels \eta and 1-\eta, 0<\eta<1/2, its width is O_{k,\eta}(\sqrt{n\ell_k(n)}). Chebyshev’s inequality also gives

This is concentration about the finite-size expectation. The limiting threshold \alpha_k of [16, Theorem 1.1] identifies \lim_n\EE H_n/n, but supplies no bound on the bias \EE H_n-\alpha_kn at the fluctuation scale above. For k=3, the separate companion [15, Theorem 1.1] proves that the limiting threshold \alpha_3 is a computable real.

1.1 Earlier work and the new estimate

The location and the width of a threshold are different questions. Friedgut [12, Theorem 1.3] proved a sharp threshold sequence for each fixed clause size, without asserting convergence of that sequence. Achlioptas and Peres [2, 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 [7, Theorem 1] proved the predicted limiting threshold for all sufficiently large k. Carenini’s paper [5, 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 [16, 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) [16, Proposition 3.3].

For transition width, Wilson [18, 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 [6, 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}) [5, 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 [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 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 [12, Lemma 5.7]; sequential conditioning on a residual assignment set is developed in Carenini [6, 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.

1.2 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

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

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

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 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.

2 Survival of a set of assignments

The deletion argument will leave a set of assignments that must pass random tests of length k-1. We need to relate the probability that those tests eliminate the set to its lifetime under clauses of length k. This section proves the relation for every assignment set. Replacing a shorter constraint by a block of clauses of the original length has a qualitative predecessor in Friedgut’s half-cube argument [12, Lemma 5.7].

Fix integers k\ge3 and u\ge k, and put

A proper s-clause, for 1\le s\le u, chooses an s-element subset of the u variables uniformly and then chooses independent fair signs on that subset. Clauses are independent, so a whole clause may occur more than once. A collection of clauses kills S\subseteq\{0,1\}^u when no member of S satisfies every clause in the collection. For nonnegative integers d,g, define

For a nonempty set, q_0(S)=R_0(S)=0. For the empty set these probabilities are one, including when there are zero clauses. Let H_k(S) be the first killing index in an infinite sequence of proper k-clauses, counting the killing clause, and put

These expectations are finite: for every integer m\ge0,

Indeed, each fixed assignment survives each independent clause with probability 1-2^{-k}, and the first inequality is a union bound.

2.1 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

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,

In fact b-r\ge b/k, u-r\le u, and

Substituting these bounds into the equality proves (2.3). Its hypothesis matters. For the cylinder whose first r coordinates are fixed to zero,

No single k-clause kills this set. A sufficiently long block can still do so through the joint effect of its clauses.

2.2 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 [6, Theorem 4.3]. The uniform additive block estimate in Lemma 2.1 takes the place of the cutoff-dependent comparison of single-clause killing probabilities in [6, 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.

3 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\ge3, a real B>0, and n\ge2k. Put L=\lfloor Bn\rfloor, and for now suppose L\ge1. Let C_1,C_2,\ldots be independent uniform proper k-clauses on n variables, let H be the first unsatisfiable prefix index, and put T=\min\{H,L\}. For 1\le i\le L, define

The infimum is over integers and \inf\varnothing=\infty. Deleting C_i retains all other clause indices. It can only delay unsatisfiability, so D_i\ge0; moreover T^{(i)} depends only on the first L clauses other than C_i.

3.1 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

On this event every solution of B_m has root values t. The two prefix processes agree before i, and hence

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

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

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:

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 3.2. The static information includes future nonordinary data, but it includes no future ordinary contents.

3.2 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

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

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.

3.3 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

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,

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.

4 Occupation and incidence moments

Keep the deleted index i, its fixed clause C_i, and the environment \mathcal E of Section 3. We first bound the time spent at each level of the shorter-clause killing probability q_m=q_d(S_m). We then combine that occupation bound with the root tests and average the incidence counts.

In this section C_k denotes a positive constant depending only on the fixed k, which may increase between occurrences. It need not equal the explicit constant in Proposition 2.3. Recall \beta=k/(k-1), d=\max\{1,Z\}, and W_m=\min\{L,\tau_k(S_m)+Z\}. On S_m\ne\varnothing,

Indeed, Proposition 2.3 bounds \tau_k(S_m)q_m^\beta by a constant times d^\beta, and

The product bound remains valid when q_m=0.

4.1 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 3.3 supplies the factor q_m^k in the weighted-delay bound (3.10). On a nonempty S_m, (4.1) gives

The remaining occupation sum has exponent

The lifetime estimate has controlled the remaining deletion duration; Lemma 4.1 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.

4.2 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.

4.3 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.

4.4 Completing the capped upper bound

5 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.

5.1 Exact cap comparisons

Fix k\ge3, put q_k=1-2^{-k}, and write P_n(m)=\PP(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

In particular, H_n is almost surely finite and has finite moments of every order. For integer caps a\ge1 and b\ge0, define

These have the exact prefix identities

All clause counts in these identities are integers.

Recall the first-moment cap density

For any fixed B>U_k, let \rho_{k,B}=2q_k^B<1. The cap a=\lfloor Bn\rfloor satisfies

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,

Theorem 1.1 of [16] gives a unique positive finite threshold \alpha_k in exactly this proper-clause model. It also implies

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 5.1 first compares it with X_b, then with H_n; the errors after the one-index shift are exponentially small. Equation (5.12) handles the remaining caps. The same conclusion holds for last-satisfiable caps of density B>U_k. These limits give no rate for \EE H_n-\alpha_k n or for the corresponding capped bias. The concentration in (5.11) is centered at each finite-size expectation.

6 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.

Wilson’s Corollary 4 [18] applies to independent uniform proper k-clauses sampled with replacement. At the fixed probability levels 3/4 and 1/4, its assertion for every fixed k\ge3 gives constants d_k>0 and n_k such that, for n\ge n_k,

The constants may depend on k. We spell out the conversion from this quantile-width statement to a variance bound, including possible atoms.

7 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, define the three distinct statistics

With \rho=2(7/8)^{10}<1, Proposition 5.1 gives

Consequently 0\le\EE V-(\EE T-1)\le(6n+1)\rho^n and |\sqrt{\Var(V)}-\sqrt{\Var(T)}|\le(6n+1)\rho^{n/2}. The sharper geometric bounds proved above are

The pathwise inequality W\le6n+4n\ind{H_n>6n} and the density-six first moment, with \sigma=2(7/8)^6<1, give

The survival-sum bound \EE H_n\le6n+8\sigma^n proves the same 6+o(1) upper bound for T and V. Their normalized expectations are therefore all at most 7 for sufficiently large n.

On the density interval 0\le c\le8, the three-clause Poisson law gives the following explicit transfer constants. Let s_n(c) be the satisfiability probability for \operatorname{Pois}(cn) clauses, where the three variable choices within each clause are independent uniform choices with replacement and the signs are independent and fair. Internal repetitions and tautologies are allowed in this auxiliary law. The distinct-variable fraction is exactly

Poisson thinning gives independent proper and repeated-variable clause collections. The proper count J has distribution \operatorname{Pois}(cn\vartheta_n), while the other count has mean

Requiring no repeated-variable clauses for a lower bound, and deleting them for an upper bound, gives

Set \omega_n=\EE W/n. The variance upper bound implies, in particular, \PP(|W-n\omega_n|\ge n^{11/12})=O(n^{-1/6}). Chebyshev’s inequality for J and (7.4) therefore yield, uniformly for c\in[0,8],

Indeed, in the lower case \EE J\le n\omega_n-2n^{11/12}, so J\le n\omega_n-n^{11/12} except with probability O(n^{-5/6}). In the upper case \EE J\ge n\omega_n+2n^{11/12}-24, and the opposite deviation has the same bound. Apply concentration at the indicated integer counts; for counts beyond 10n, use monotonicity at \lceil n\omega_n+n^{11/12}\rceil<10n, valid by (7.3). These statements use the last-SAT cap 10n and Poisson density ceiling 8, giving the lower constant e^{-24}/2. The general transfer lemma of the threshold companion permits a cap density \lambda and a separate Poisson density ceiling D, each above a fixed upper bound for the normalized centers [16, Lemma 5.3]. Specializing it to k=3 and \lambda=D=16 uses the last-SAT statistic V, center \EE V/n, and interval c\in[0,16]. In that specialization the repetition bound is 48 and the lower constant is e^{-48}/2.

A Sharpness for arbitrary assignment sets

For each fixed integer k\ge3, two exponents in Section 2 are optimal for estimates uniform over arbitrary assignment sets: the power k/(k-1) of the inverse killing probability in the lifetime bound, and the power k-1 of the inverse block length in the one-clause replacement error. Both examples below use subcubes with many frozen coordinates. A common observation identifies when a block of clauses can kill such a subcube.

Write r=k-1. We retain the proper clause law: a proper s-clause on u coordinates chooses s distinct coordinates uniformly and gives them independent fair signs. Different clauses are independent, with repetition of whole clauses allowed. Recall that q_1(S) is the probability that one proper r-clause kills S, R_t(S) is the probability that t proper k-clauses kill S, and \tau_k(S)=\EE H_k(S). For nonempty S, H_k(S) is the least positive index t for which the first t proper k-clauses jointly kill S; the convention for the empty set is H_k(\varnothing)=0.

For integers u\ge b\ge k, consider the nonempty subcube

Its first b coordinates are frozen and the others are free. If h_s(S_{u,b}) denotes the probability that one proper s-clause kills this subcube, the frozen-coordinate formula (2.2) reads

where (a)_s=a(a-1)\cdots(a-s+1). In particular,

For every integer t\ge1, the same subcube satisfies

The lower bound records the independent chances that a single clause kills the whole subcube. To prove the upper bound, restrict all t clauses to the frozen values. Each restricted clause is already true, is the empty false clause, or is a nonempty clause on free coordinates. If no restricted clause is empty and false, and no two original clauses share a free coordinate, then the remaining nonempty clauses use disjoint sets of variables. Choose one literal in each and set it true, then assign the other free coordinates arbitrarily. The resulting assignment lies in S_{u,b} and satisfies the block. Thus a block can kill the subcube only if an individually killing clause occurs or a pair of clauses shares a free coordinate. For a fixed free coordinate, the probability that both independent proper clauses contain it is (k/u)^2. Summing over the u-b free coordinates bounds the probability for a given pair by k^2/u. A union bound over clauses and pairs proves the upper bound in (A.3).

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.

B 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.

B.1 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)=\PP(H_n>j) for integers j\ge0. Fix a real B>0 and set

The endpoint for this first-unsatisfiable convention is strict:

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 (B.1).

The theorem allows an arbitrary vanishing concentration error; it does not require a specified polynomial rate. In particular, Chebyshev’s inequality supplies (B.2) whenever

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.

B.2 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.

B.3 From a random clause count to a center

We first record the integer step needed in both center comparisons. From (B.2) and (B.1), for every integer 0\le j<L_n and all sufficiently large n,

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}}=\EE P_N(J). Put

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 \Var(J)\le AN, whence

The second inequality uses monotonicity of P_N. If \zeta+AN^{-1+2\delta}+\eta_N<1, the upper implication in (B.12) forces j<\mu_N+N^{1-\delta}. The floor in the definition of j then gives

We will apply this implication with all three errors tending to zero.

The comparison (B.6) 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.

B.4 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,

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

For the positive anchor, fix 0<c<\min\{e^{-2},B\} and let j=\lfloor cn\rfloor. Lemma 6.1 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

The capped variance theorem gives

which tends to zero for every fixed 0<\delta<1/2. Theorem B.1 now applies with a=c_0 and A=A_k. Its strict-side limit is the same \alpha_k as in the threshold companion [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_kn and the same last-SAT cap b=a, the exact identity in Proposition 5.1 is

That proposition gives \Var(\min\{H_n,a\})\le\Var(\min\{H_n-1,a\}). Consequently the companion’s O_k(n^{1+2/k}) bound verifies (B.7) 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.

C 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 \lceil\log n\rceil, and pays separately for clauses meeting two or more of those variables. It gives an O(n\log^4 n) bound. The cube of the incidence cutoff contributes three logarithmic factors; the critical occupation integral contributes the fourth. The main argument in Sections 3–4 instead averages the bounded third moment of the actual incidence count, giving O(n\log n). Comparing the two proofs shows where that improvement enters. The replacement step below also gives a distinct finite-variable estimate: replacing one two-clause on u variables by g three-clauses loses at most 64(g^{-2}+u^{-2}) in killing probability.

Throughout this section, C_1,C_2,\ldots are independent uniform proper three-clauses on n\ge3 variables: a clause uses three distinct variables and independent fair signs, while whole clauses may repeat. Write H_n for the index of the first unsatisfiable prefix and put

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.

C.1 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 [12, Lemma 5.7]. The residual-set conditioning used below is the averaged replacement method of Carenini [6, Theorem 4.3, Lemma 6.1, and Corollary 6.2]; the following bound supplies the finite-variable pair-to-triple estimate needed here.

C.2 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

with \inf\varnothing=\infty. Then D_i\ge0, and T^{(i)} does not use coordinate C_i. The coordinate-omission inequality, Lemma 3.1, gives

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

On A_m, every solution of B_m has root values t. The two processes agree before index i, so

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

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

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.

C.3 The three root-flip tests

The weight in (C.8) 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

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

C.4 Truncating incidence counts and summing occupation

It remains to sum the right side of (C.8). 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

For sufficiently large n, a_0<1. On S_m\ne\varnothing,

For q_m\ge a_0, this follows by applying Proposition C.4 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

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.

C.5 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

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 B.1. The anchors give (c_0/4)N\le M\le7N for large n. Since C_3=27 in Lemma B.2 and N\le4n, (B.9) bounds the loss by

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 (B.13).

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.