Linear Variance of the Random 3-SAT Hitting Time

Introduction

Fix an integer $n \ge3$. A proper 3-clause is a disjunction of three literals on distinct variables among $x_1,\ldots,x_n$. Let $C_1,C_2,\ldots$ be independent clauses, each uniform among the $8\binom{n}{3}$ proper 3-clauses. Thus the signs are fair and independent, and whole clauses may repeat. Write

where $F_0$ is the empty, satisfiable formula. The random variable $H_n$ records the location of the satisfiability transition in the clause process.

Theorem 1.1. There is an absolute constant $C<\infty$ such that

There are also absolute constants $c>0$ and $n_0$ such that $\operatorname{Var}(H_n)\ge cn$ for $n\ge n_0$. In particular, $\operatorname{Var}(H_n)=\Theta(n)$ as $n\to\infty$.

The new assertion is the upper bound. We give its proof in full. The lower bound follows from Wilson’s quantitative separation of satisfiability levels [7] [Corollary 4]; Section 5 includes the short deduction, with the integer endpoints treated explicitly.

Context and contribution

Friedgut proved sharpness of the random $k$-SAT threshold for every fixed $k\ge2$ [5] [Theorem 1.3]. Quantifying the width of that transition is a finer problem. Wilson showed that, for $k\ge3$, a fixed decrease in the satisfiability probability requires at least a constant times $\sqrt{n}$ additional clauses [7]. More recently, Carenini obtained an $O(n/\log n)$ central clause-window bound for fixed $k\ge3$, including independently sampled proper constraints [3] [Corollaries 7.10–7.11]. Her subsequent paper [2] [Theorems 1.1 and 1.3, Corollary 1.2], made public on October 5, 2026, proves for every fixed $k\ge3$ a central window bound $O_{k,\eta}(n^{1/2+1/k})$ at each fixed $0<\eta<1/2$ and a hitting-time variance bound $O_k(n^{1+2/k})$. Together with the Abbe–Montanari criterion, her result establishes the limiting satisfiability threshold for every fixed $k \ge3$. We credit Carenini with priority for the resolution of the satisfiability conjecture. The present paper concerns the sharper fluctuation question for three-literal clauses.

A bound on a fixed central window alone does not control the variance, which also depends on the tails. In the other direction, Theorem 1.1 and Wilson’s lower bound show that the clause window over which satisfiability drops from $1-\eta$ to $\eta$ has order $\sqrt{n}$ for every fixed $0 < \eta< 1/2$; see Corollary 5.2.

The companion preprint Variance of the Random $k$-SAT Hitting Time [6] develops a clause-omission and root-test framework. It proves variance $\Theta_k(n)$ for every fixed $k \ge4$ and an upper bound $O(n \log n)$ for $k=3$. Our argument uses that framework, which we reprove here, and replaces its critical occupation estimate in the three-literal case. The companion has broader general-$k$ and capped formulations; the present paper concerns the uncapped proper 3-clause process defined above.

The new ingredient is a family of potentials for an arbitrary set $S$ of Boolean assignments. Let $q_j(S)$ be the probability that $j$ independent random proper 2-clauses leave no assignment in $S$, and put

The potential increases when $S$ shrinks and is bounded by $d$. Section 2 proves that $q_d(S)^{3/2}$, for nonempty $S$, is controlled by the expected increment of $P_d$ under a random 3-clause, up to a small error. Summing those increments gives a direct bound on the accumulated values of $q_d^{3/2}$. This is the step that removes the logarithmic loss.

Here is how the potential enters the variance proof. For $n \ge6$, cap $H_n$ at $10n$ and let $D_i$ be the delay caused by omitting the clause at index $i$, without renumbering later clauses. The coordinate-omission form of the Efron–Stein inequality bounds the capped variance by $\sum_i \mathbb{E}D_i^2$ [4, 1]. Fixing the omitted clause singles out its three variables as roots. If that clause is pivotal, every remaining solution has the unique root assignment that falsifies it. Flipping each root gives an independent family of necessary tests on the nonroot solution set, except when another clause meets two or more roots. Section 3 constructs this exposure and proves the test bound.

Let $d$ be the larger of $1$ and the number of clauses other than $C_i$ among the first $10n$ that meet a root. At a given index, let $S$ be the nonroot solution set of the omitted-clause prefix with the roots fixed to their falsifying assignment, and write $p=q_d(S)$. With no collisions, the three test families each have at most $d$ clauses and give a pivotality bound $p^3$. For $p>0$, the potential gives a conditional remaining-duration bound $O(d^{3/2}p^{-3/2})$ and bounds the conditional expected sum of $p^{3/2}$, while $S$ is nonempty, by $O(d^{3/2})$. The identity $3-3/2=3/2$ thus yields a conditional squared-delay bound $O(d^3)$. The root-incidence count $d$ has bounded moments uniformly in $n$. Section 4 carries out this calculation and averages the rare collision cases, obtaining $\mathbb{E}D_i^2=O(1)$ uniformly in $i$. Finally, Section 5 removes the cap using an elementary first-moment tail bound and proves the matching lower bound.

Throughout, a random proper $a$-clause on a specified variable set is uniform over the clauses using $a$ distinct variables and independent fair signs. Independent collections are sampled with replacement. All unspecified constants are absolute.

A potential for killing assignment sets

We first work on $u \ge3$ variables, independently of the clause process. The aim is to bound a power of a short-clause killing probability by the drift of a bounded, monotone potential. For $S \subseteq\{0,1\}^{u}$ and a clause $C$, let

For $j \ge0$, define $q_j(S)$ as the probability that $j$ independent random proper $2$-clauses kill $S$, meaning that no member of $S$ satisfies them all. In particular,

The quantity $q_j(S)$ is nondecreasing both in $j$ and when $S$ shrinks. Set $\beta= 3/2$ for the rest of the paper.

Lemma 2.1 (One-clause comparison). For a nonempty assignment set $S$, let $h_a(S)$ be the probability that one random proper $a$-clause kills $S$, for $a = 2,3$. Then

Proof. A coordinate is frozen if it is constant throughout $S$. Let $b$ be the number of frozen coordinates. A clause kills all of $S$ exactly when all its variables are frozen and each literal has the falsifying sign. Consequently,

where $(t)_a = t(t-1)\cdots(t-a+1)$, with value zero for integers $0 \le t < a$. Since $b \le u$,

For $b \ge3$ we also have

which proves $h_2(S)^{3/2} \le3h_3(S)$ in this case. For $b \le1$ the left side is zero. For $b = 2$ it is $[2u(u-1)]^{-3/2} \le u^{-3}$, proving (2.1).

The error term accounts for sets with exactly two frozen coordinates: a 2-clause can kill such a set, whereas a proper 3-clause cannot. The following lemma turns the one-clause comparison into the potential estimate needed along a decreasing sequence of assignment sets.

Lemma 2.2 (Potential drift). For every integer $d \ge1$, put

Then $0 \le P_d(S) \le d$, and $P_d$ is nondecreasing when $S$ shrinks. If $C$ is an independent random proper 3-clause on the $u$ variables, then

Proof. Fix $j \ge0$, and let $Y$ be the subset of $S$ surviving $j$ independent random proper 2-clauses. Adding one more such clause gives

Adding instead the independent 3-clause $C$ gives

Indeed, in either order of adding the clauses, the increase in killing probability is precisely the probability that the old surviving set is nonempty and the final clause kills it. Products with the indicators in these formulas are defined to be zero when $Y$ is empty. Jensen’s inequality and Lemma 2.1 imply

For nonempty $S$, the nonnegative successive differences telescope to $q_d(S)$, because $q_0(S)=0$. Thus the power-sum inequality yields

and summing the preceding bound proves (2.2). For empty $S$, its left side is zero and its right side is nonnegative. The bounds and monotonicity of $P_d$ follow directly from those of $q_j$.

Clause deletion and independent root tests

We now reduce the variance bound to a uniform squared-delay estimate. The root exposure and root-flip tests in this section follow the clause-omission framework of [6], Section 3; all details needed here are included.

Assume $n \ge6$, set $L=10n$, and let $T=\min(H_n,L)$. For $1\le i\le L$, omit $C_i$ while retaining the original indices:

Let $T^{(i)}$ be the first index at which this omitted-clause process is unsatisfiable, capped at $L$, and set $D_i=T^{(i)}-T\ge0$. Both capped variables are functions of the first $L$ clauses, and $T^{(i)}$ does not depend on $C_i$.

Lemma 3.1 (Coordinate omission). The capped hitting time satisfies

Proof. This is the coordinate-omission form of the Efron–Stein inequality; see [1 Section 3.2, Equation (3.6)]. For completeness, write $\mathcal{F}_i=\sigma(C_1,\ldots,C_i)$ and $\Delta_iX=\mathbb{E}[X\mid\mathcal{F}_i]-\mathbb{E}[X\mid\mathcal{F}_{i-1}]$. Independence and the omission of $C_i$ give $\Delta_iT^{(i)}=0$, so $\Delta_iT=-\Delta_iD_i$. Orthogonality of conditional-expectation projections implies $\mathbb{E}(\Delta_iD_i)^2\le\mathbb{E}D_i^2$. Summing the orthogonal martingale differences of $T$ proves (3.1).

The exposure and its two filtrations

Fix $i$ and condition on the value of $C_i$ until further notice. All probabilities and expectations in this section and in Section 4, until the final averaging step, are in this conditional law. Write $B_m = B_m^{(i)}$. Call the three variables of $C_i$ the roots, denote their set by $R$, and let $w \in\{0,1\}^{R}$ be the unique root assignment falsifying $C_i$. There are $u=n-3\ge3$ nonroot variables.

For $i\le m<L$, define

The processes agree before $i$, so

For $i\le m\le L$, let $S_m\subseteq\{0,1\}^{u}$ consist of the nonroot assignments that, together with $w$, satisfy $B_m$. The sets $S_m$ decrease with $m$. On $A_m$, the set $S_m$ is nonempty, and every solution of $B_m$ has root assignment $w$.

We will retain two independent sources of randomness: clauses driving the evolution of $S_m$, and clauses testing possible root flips. For every index $j\le L$ other than $i$, first reveal the subset of $R$ met by $C_j$ and all signs on that subset. Classify the index as follows:

• An ordinary clause meets no root; leave all its contents hidden.

• A test clause meets exactly one root, whose literal is true under $w$; leave its two nonroot literals hidden.

• For every other clause, reveal all its remaining contents.

Let $\mathcal{E}$ be the sigma-field of this exposure, including the information at future indices. Let $Z$ count the exposed indices meeting at least one root, and let $V$ count those meeting at least two roots. The latter clauses are called collisions. Set $d=\max\{1,Z\}$. The counts $Z,V,d$ and the complete schedule of clause types are $\mathcal{E}$-measurable.

Conditional on $\mathcal{E}$, the hidden ordinary clauses are independent uniform proper 3-clauses on the nonroots, and the hidden nonroot parts of the test clauses are independent uniform proper 2-clauses there. These two collections are also independent of each other. To see this, condition first on the root subset and its signs separately at each index. Every permitted signed nonroot part remains equiprobable, and the original product law across indices is preserved. Revealing the remaining contents at the other indices does not change the law of the hidden coordinates.

For $i\le m\le L$, define

The set $S_m$ is $\mathcal{G}_m$-measurable: all test clauses are already true under $w$, whatever their nonroot parts. The event $A_m$ is $\mathcal{H}_m$-measurable, because this larger sigma-field knows all clauses of $B_m$. Future ordinary contents remain fresh given $\mathcal{H}_m$. Finally, put

The quantity $p_m$ is $\mathcal{G}_m$-measurable and nondecreasing in $m$. Keeping the tests out of $\mathcal{G}_m$ will allow us to estimate pivotality after using $\mathcal{H}_m$ to estimate the remaining duration.

Necessary tests for root flips

Lemma 3.2 (Root-test bound). For $i \le m < L$, conditional on $\mathcal{G}_m$,

Proof. Call a root $x$ available at time $m$ if no collision through index $m$, excluding $i$, has its literal on $x$ as the unique root literal true under $w$. A collision excludes at most one root, so at least $3-V$ roots are available. Availability is $\mathcal{E}$-measurable.

For an available root $x$, the nonroot parts of its test clauses through $m$ must kill $S_m$ on $A_m$. Otherwise, take $z \in S_m$ satisfying all these parts and flip only $x$ in the assignment $(w,z)$. Every clause of $B_m$ remains satisfied. A clause with no true root literal under $w$ already has a satisfied nonroot literal, which is unchanged. A clause with a true root literal other than the one on $x$ keeps that literal. Finally, a clause whose unique true root literal is on $x$ cannot be a collision, by availability; it is therefore a test clause for $x$, and $z$ satisfies its nonroot part. The flipped assignment also satisfies $C_i$, contradicting $A_m$.

Given $\mathcal{G}_m$, the test families for distinct roots remain independent collections of random proper 2-clauses, independent of $S_m$. Each family has at most $Z \le d$ members, so its probability of killing $S_m$ is at most $q_d(S_m)=p_m$. On $V=0$ all three roots are available; on $V=1$ at least two are. Taking these necessary independent events proves the two inequalities, including the cases $p_m=0$ or $S_m=\varnothing$.

Occupation and squared deletion delays

We continue with $i$ and $C_i$ fixed. Our goal is $\mathbb{E}D_i^2=O(1)$, uniformly in the value of the fixed clause. The root tests bound the chance that a delay is present; the potential will bound how long that delay can continue.

Lemma 4.1 (Conditional occupation estimate). With $K=7$, for every $i \le m < L$,

Proof. Suppose $s+1$ is ordinary, a fact known under $\mathcal{E}$. Then $S_{s+1}=S_s[C_{s+1}]$, and $C_{s+1}$ is still a uniform proper 3-clause on the nonroots given $\mathcal{H}_s$. Lemma 2.2 gives

Condition on $\mathcal{H}_m$ and sum over such $s$. Every potential increment is nonnegative, even at nonordinary steps. Thus, pathwise,

The tower property therefore bounds the contribution of the ordinary steps by $3d^\beta+Ld^\beta u^{-3}$. There are at most $Z$ remaining steps: all indices $s+1$ in question exceed $i$, and every nonordinary index meets a root. Each remaining summand is at most one. Since $Z \le d \le d^\beta$, $u=n-3 \ge n/2$, and $n \ge6$, the full sum is bounded by

Corollary 4.2 (Remaining duration). For $i\le m<L$,

In particular, $W_m$ is measurable with respect to the smaller sigma-field $\mathcal{G}_m$.

Proof. For $s\ge m$, we have $p_s\ge p_m$, and $A_s$ implies $S_s\ne\varnothing$. If $p_m>0$, divide (8) by $p_m^\beta$. The count is always at most $L$, giving both the minimum and the case $p_m=0$. Measurability follows from that of $d$ and $p_m$.

The two estimates now have the compatible conditioning we need: the duration estimate knows whether $A_m$ has occurred, while its upper bound $W_m$ does not reveal the test parts. We can therefore multiply it by the independent-test probability from Lemma 3.2.

Proposition 4.3 (Squared delay conditional on the exposure). For every $1\le i\le L$,

Proof. For $i=L$ we have $D_i=0$. Otherwise, (5) implies

First condition on $\mathcal{H}_m$, where $A_m$ is known, and apply Corollary 4.2. Then condition on $\mathcal{G}_m$, where $W_m$ is known. Conditioning both estimates down to $\mathcal{E}$ gives

On $V=0$, Lemma 3.2 bounds the product inside by

This remains valid for $p_m=0$, because the conditional probability then vanishes. Lemma 4.1 with $m=i$, conditioned further down to $\mathcal{E}$, bounds the sum in (11) by $2K^2d^{2\beta}=2K^2d^3$. On $V=1$, the same product is at most $Kd^\beta p_m^{2-\beta}\le Kd^\beta$ when $p_m>0$, and is zero when $p_m=0$. There are at most $L$ terms. Finally, on $V\ge2$ use $D_i\le L$. The cases are $\mathcal{E}$-measurable, proving (10).

Averaging the collision costs

It remains to average the three terms of (10). Although one collision costs a factor $L$ and two collisions cost $L^2$, their probabilities are correspondingly small.

Lemma 4.4 (Root-incidence moments). Uniformly in $n \ge6$, $i$, and the fixed value of $C_i$,

Proof. Each of the other $L-1$ independent clauses meets a specified root with probability $3/n$, and contains a specified pair of roots with probability $6/[n(n-1)]$. Union bounds over the three roots and their three pairs give incidence and collision probabilities satisfying

The incidence count $Z$ is binomial, so

This uniformly bounded exponential moment gives $\mathbb{E}d^3 = O(1)$.

For each $j \ne i$ with $j \le L$, let $J_j$ be the event that $C_j$ is a collision. Bound $\mathbf{1}_{\{V\ge1\}}$ by $\sum_{j\ne i}\mathbf{1}_{J_j}$. Conditional on $J_j$, the count $Z$ is one plus a binomial variable with $L-2$ trials and success probability $p_{\mathrm{hit}}$; all other clauses retain their original law. Its exponential moment, and hence $\mathbb{E}[d^{3/2}\mid J_j]$, is bounded uniformly. Therefore

Finally, independence at different indices gives

$\square$

Combining Proposition 4.3 and Lemma 4.4, and using $L=10n$, proves $\mathbb{E}D_i^2=O(1)$ in the law conditional on $C_i$, with a constant independent of its value. We may now remove that conditioning. Lemma 3.1 gives

This completes the deletion argument. No information about the location of the satisfiability threshold was needed.

The uncapped hitting time and the lower bound

Removing the cap

For a fixed assignment, each independent clause is satisfied with probability $7/8$. A union bound over the $2^n$ assignments gives, for every $n\ge3$ and integer $m\ge0$,

In particular $H_n$ is finite almost surely and has a finite second moment. For $n \ge6$, write $T = \min\{H_n,L\}$ as before. The integer-valued tail-sum formula yields

Here $\sum_{j\ge0}(2j+1)r^j=(1+r)/(1-r)^2=120$ for $r=7/8$, and $2(7/8)^{10}<1$. Since

Equations (13) and (15) give the upper bound in Theorem 1.1 for $n\ge6$. For $3\le n<6$, the same tail bound gives $\mathbb{E}H_n^2\le120\cdot2^n$, so enlarging the absolute constant covers these finitely many sizes.

Wilson's separation theorem

Define the survival function and its integer level locations by

These locations are finite by (14) and positive because $s_n(0)=1$. We use the following consequence of Wilson's theorem for the independent proper-clause model with replacement.

Theorem 5.1 (Wilson [7], Corollary 4). Fix $1>p_1>p_2>0$. There is a constant $a(p_1,p_2)>0$ such that, for all sufficiently large $n$, if integers $m_1,m_2$ satisfy $s_n(m_1)\ge p_1$ and $s_n(m_2)\le p_2$, then

Take $a_n=r_n(3/4)$ and $b_n=r_n(1/4)$. Minimality gives $s_n(a_n-1)>3/4$, whereas $s_n(b_n)\le1/4$. Theorem 5.1, applied at $a_n-1$ and $b_n$, therefore implies $b_n-a_n+1\ge a(3/4,1/4)\sqrt{n}$. Thus

for an absolute $c_0>0$ and all sufficiently large $n$. Moreover,

Let $H'_n$ be an independent copy of $H_n$. The two events $\{H_n\le a_n,H'_n\ge b_n\}$ and $\{H'_n\le a_n,H_n\ge b_n\}$ are disjoint for large $n$, each has probability at least $1/16$, and on each $|H_n-H'_n|\ge b_n-a_n$. Consequently,

This completes the proof of Theorem 1.1.

Corollary 5.2 (Fixed central windows). For every fixed $0<\eta<1/2$,

Proof. The lower bound follows from Theorem 5.1 at $r_n(1-\eta)-1$ and $r_n(\eta)$, absorbing the additive one. For the upper bound, put $\mu_n=\mathbb{E}H_n$ and choose $t=(2Cn/\eta)^{1/2}$, with $C$ from Theorem 1.1. Chebyshev’s inequality gives $\mathbb{P}(|H_n-\mu_n|\ge t)\le\eta/2$. For every nonnegative integer $m\le\mu_n-t$ this implies $s_n(m)\ge1-\eta/2>1-\eta$, whereas at $m=\lceil\mu_n+t\rceil$ it implies $s_n(m)\le\eta/2<\eta$. Hence $r_n(1-\eta)>\mu_n-t$ and $r_n(\eta)\le\lceil\mu_n+t\rceil$, proving the upper bound. If $\mu_n-t<0$, the first inequality follows instead from $r_n(1-\eta)\ge0$.

The variance bound controls fluctuations around the finite-size mean $\mathbb{E}H_n$. Neither the proof nor Corollary 5.2 requires a limiting value of $\mathbb{E}H_n/n$ or a limiting distribution for the centered hitting time.