betaFeedback

WorksMathematics

Threshold existence for random NAE-kk-SAT and random hypergraph 22-colourability

Abstract

The existence of limiting threshold densities for random hypergraph 22-colourability and random NAE-kk-SAT was conjectured in earlier work, including Achlioptas and Moore [RANDOM 2002] and Coja-Oghlan and Panagiotou [STOC 2012]. We prove these conjectures for all k≥3k\geq 3. We also show that αk2−col≤αkNAEα^{\mathrm{2-col}}_k \leq α^{\mathrm{NAE}}_k for each k≥3k\geq 3.

Introduction

For the study of random constraint satisfaction problems (CSPs), one of the starting points was the question of Erdős and Rényi about the chromatic number of a random graph [16]. In the language of random CSPs, fixing the number of colours leads to the question of the qq-colourability threshold. Estimates of the chromatic number are known in many regimes [6, 12, 19], but the existence of a limiting colourability threshold remains open for general qq. One of the explanations regarding why the problem is so difficult comes from statistical mechanics. A heuristic called the cavity method predicts that before the satisfiability threshold, the solution set of a random CSP can undergo several other phase transitions, such as clustering and condensation [20]. Among other things, these transitions help explain the limitations of the second moment method [13, 14], one of the main tools for estimating thresholds in random structures.

A related question is the satisfiability conjecture for random kk-SAT [11]. Here a formula consists of independently sampled clauses, each being a disjunction of kk distinct uniformly chosen variables with independent uniform signs, and an assignment satisfies the formula if it makes at least one literal in every clause true. The conjecture asserts that for each fixed k≥3k \ge3 there is a constant clause density αkSAT\alpha_k^{\mathrm{SAT}} below which such a formula is satisfiable with high probability (whp) and above which it is unsatisfiable whp.

Friedgut’s sharp threshold theorem [17] establishes the existence of a threshold sequence, but does not establish its convergence. Writing Φn,mSAT\Phi_{n,m}^{\mathrm{SAT}} for the random kk-SAT formula described above, for every fixed k≥3k \ge3 there is a sequence αkSAT(n)\alpha_k^{\mathrm{SAT}}(n) such that for every fixed ε>0\varepsilon> 0 and every sequence α=α(n)≥0\alpha= \alpha(n) \ge0,

P(Φn,⌊αn⌋SAT is satisfiable)→{1,if 0≤α<αkSAT(n)⋅(1−ε);0,if α>αkSAT(n)⋅(1+ε),\mathbb{P}\left(\Phi_{n,\lfloor\alpha n\rfloor}^{\mathrm{SAT}}\text{ is satisfiable}\right) \to\begin{cases} 1, & \text{if } 0 \le\alpha< \alpha_k^{\mathrm{SAT}}(n)\cdot(1-\varepsilon); \\ 0, & \text{if } \alpha> \alpha_k^{\mathrm{SAT}}(n)\cdot(1+\varepsilon), \end{cases}

as nn goes to infinity, provided the corresponding inequality holds for all sufficiently large nn. Similar sharp threshold results also hold for graph colourability [3] and for hypergraph 2-colourability and NAE-kk-SAT [18]. However, sharpness alone does not imply that the threshold sequences converge as n→∞n \to\infty.

For random 2-SAT the threshold density is known to be α2SAT=1\alpha_2^{\mathrm{SAT}}=1 [11]. For larger clause sizes, Ding, Sly and Sun [15] proved the satisfiability conjecture for all sufficiently large kk and identified the threshold with the value predicted by the cavity method. Recently, Carenini established an O(n/log⁡n)O(n/\log n) scaling window [9], and then improved it to O(n1/2+1/k)O(n^{1/2+1/k}) [10]. These bounds count the number of random clauses one needs to add to decrease the satisfiability probability from 1−η1-\eta to η\eta for any fixed 0<η<1/20 < \eta< 1/2. Combined with the Abbe–Montanari interpolation criterion [1], the latter estimate proves the existence of a limiting threshold for every fixed k≥3k \ge3 without identifying its value. An alternative proof later appeared in a manuscript by OpenAI [21]. It combines polynomial concentration for the last satisfiable index with an interpolation method to prove convergence directly, without using the Abbe–Montanari criterion.

For random hypergraph 2-colourability and random NAE-kk-SAT, the existence of limiting threshold densities was conjectured in [4, 13]. Let αk2-col(n)\alpha_k^{2\text{-col}}(n) and αkNAE(n)\alpha_k^{\mathrm{NAE}}(n) denote the corresponding sharp threshold sequences. For all sufficiently large kk and nn, the bound of Coja-Oghlan and Zdeborová [14] and the first moment method give

2k−1ln⁡2−ln⁡2−ok(1)≤αk2-col(n)≤2k−1ln⁡2−ln⁡22+ok(1).2^{k-1}\ln2-\ln2-o_k(1)\le\alpha_k^{2\text{-col}}(n)\le2^{k-1}\ln2-\frac{\ln2}{2}+o_k(1).

For NAE-kk-SAT, Coja-Oghlan and Panagiotou [13] obtained the sharper estimate

αkNAE(n)=2k−1ln⁡2−ln⁡22−14+ok(1).(1)\alpha_k^{\mathrm{NAE}}(n)=2^{k-1}\ln2-\frac{\ln2}{2}-\frac{1}{4}+o_k(1). \tag*{(1)}

Here the errors tend to zero as k→∞k\to\infty uniformly for sufficiently large nn, but these estimates do not establish convergence in nn for any fixed kk. Coja-Oghlan and Panagiotou also observe that the results of [14] carry over to NAE-kk-SAT, and it is natural to expect the same asymptotic threshold for hypergraph 2-colourability. More recently, Carenini [9] proved O(n/log⁡n)O(n/\log n) scaling windows for both models, again leaving the convergence question open.

In this paper we prove that the limiting densities exist in both models for every fixed k≥3k\ge3. For n≥kn\ge k, let Hn,mH_{n,m} be the random kk-uniform hypergraph obtained by sampling mm edges independently and uniformly with replacement from the kk-subsets of its vertex set. A NAE-clause is satisfied if its literal values are not all equal. We represent Hn,mH_{n,m} by a NAE-formula Φn,m+\Phi^+_{n,m} with all signs positive, so the formula is satisfiable precisely when the hypergraph is 2-colourable. Let Φn,m±\Phi^\pm_{n,m} be the corresponding random NAE-kk-SAT formula with independent uniform signs. Vertices correspond to variables, edges to clauses and colourings to assignments. In particular, variables within each clause are distinct, while clauses may repeat. We write SAT for the set of satisfiable NAE-formulas, and in statements concerning both models, αk⋆\alpha_k^\star denotes αk2-col\alpha_k^{2\text{-col}} for ⋆=+\star=+ and αkNAE\alpha_k^{\mathrm{NAE}} for ⋆=±\star=\pm.

Theorem 1.1. For every fixed k≥3k\ge3 there exist constants αk2-col\alpha_k^{2\text{-col}} and αkNAE\alpha_k^{\mathrm{NAE}} such that for each ⋆∈{+,±}\star\in\{+,\pm\} and m=⌊cn⌋m=\lfloor cn\rfloor,

lim⁡n→∞P(Φn,m⋆∈SAT)={1,0≤c<αk⋆;0,c>αk⋆.\lim_{n\to\infty}\mathbb{P}\left(\Phi^\star_{n,m}\in\mathrm{SAT}\right)= \begin{cases} 1, & 0\le c<\alpha_k^\star;\\ 0, & c>\alpha_k^\star. \end{cases}

Our second result compares the two thresholds for every clause size.

Theorem 1.2. In the setup of Theorem 1.1, αk2-col≤αkNAE\alpha_k^{2\text{-col}}\le\alpha_k^{\mathrm{NAE}}.

Combining Theorem 1.2 with Eq. (1) gives the following upper bound for the random hypergraph 2-colourability threshold.

Corollary 1.3.

αk2-col≤2k−1ln⁡2−ln⁡22−14+ok(1).\alpha_k^{2\text{-col}}\le2^{k-1}\ln2-\frac{\ln2}{2}-\frac{1}{4}+o_k(1).

The proof of Theorem 1.1 follows the approach developed for random kk-SAT in [21]. For ⋆∈{+,±}\star\in\{+,\pm\}, add corresponding clauses one by one, and let

ξn⋆=inf⁡{m≥1:Φn,m⋆∉SAT},τn⋆=min⁡{ξn⋆−1,2kn}.\xi_n^\star=\inf\{m\ge1:\Phi_{n,m}^\star\notin\mathrm{SAT}\},\qquad \tau_n^\star=\min\{\xi_n^\star-1,2^k n\}.

Thus τn⋆\tau_n^\star is the last satisfiable index, capped at 2kn2^k n.

We first show that for k≥3k\ge3, τn⋆\tau_n^\star is within n19/20n^{19/20} of its expectation with probability polynomially close to 1. A Poisson interpolation then compares satisfiability probabilities of the random formula on disjoint sets of variables with the random formula on their union, which is similar to the approach of Bayati, Gamarnik and Tetali [7]. Together, these estimates imply that Eτn⋆/n\mathbb{E}\tau_n^\star/n converges.

The main novelty concerns the symmetry of the considered CSPs. For NAE-satisfiability, flipping all variable values preserves a solution. Thus no variable has the same value in all solutions, and the argument based on frozen variables does not apply directly. Instead, we group variables according to whether their relative values are fixed across all solutions. These equivalence classes are used to determine exactly the probability that an additional clause destroys every solution, which yields both the clause replacement estimate needed for concentration, and the convexity inequality needed for the interpolation. Interpolating between models with positive and randomly signed clauses also gives Theorem 1.2.

Declaration of AI use

Declaration of AI use. ChatGPT was used to assist with proofreading, presentation and checking proofs. It also suggested using a similar interpolation argument to establish Theorem 1.2.

Preliminaries

Throughout, the clauses are sampled independently with replacement. Within each proper clause, variables are distinct and uniformly sampled, and assignments take values in {0,1}\{0,1\}. A clause is satisfied if its literal values are not all equal.

Equivalence classes and clause addition

Let Φ\Phi be any satisfiable NAE-formula on a variable set VV of size NN, with arbitrary signs and clause lengths. Write S(Φ)\mathcal{S}(\Phi) for its set of satisfying assignments. Define

x∼y⟺σ(x)⊕σ(y) is constant over σ∈S(Φ).x \sim y \quad\Longleftrightarrow\quad\sigma(x) \oplus\sigma(y)\text{ is constant over }\sigma\in\mathcal{S}(\Phi).

Transitivity follows from σ(x)⊕σ(z)=(σ(x)⊕σ(y))⊕(σ(y)⊕σ(z))\sigma(x) \oplus\sigma(z) = (\sigma(x) \oplus\sigma(y)) \oplus(\sigma(y) \oplus\sigma(z)), and reflexivity and symmetry are immediate. Denote its equivalence classes by O1,…,OJ\mathcal{O}_1,\ldots,\mathcal{O}_J. Fix σ∗∈S(Φ)\sigma_* \in\mathcal{S}(\Phi) and put

Oj,a={y∈Oj:σ∗(y)=a},a∈{0,1}.\mathcal{O}_{j,a} = \{y \in\mathcal{O}_j : \sigma_*(y) = a\},\qquad a \in\{0,1\}.

Within each part of one class the variables are equal in every solution, and variables in opposite parts of one class are opposite in every solution. Choosing another σ∗\sigma_* can only interchange the two parts of each class. For 2≤r≤N2 \le r \le N, let qr+(Φ)q_r^+(\Phi) and qr±(Φ)q_r^{\pm}(\Phi) be the probabilities that adding a uniformly random rr-clause on distinct variables makes Φ\Phi unsatisfiable, with all signs being positive or independent and uniformly random respectively. Write q^r+(Φ)\widehat{q}_r^+(\Phi) and q^r±(Φ)\widehat{q}_r^{\pm}(\Phi) when the variables are instead sampled independently with replacement. For an unsatisfiable Φ\Phi we set all four quantities to zero.

Lemma 2.1. For satisfiable Φ\Phi and 2≤r≤N2 \le r \le N,

qr±(Φ)=21−r∑j(∣Oj∣)r(N)r,qr+(Φ)=∑j∑a=01(∣Oj,a∣)r(N)r.(2)q_r^{\pm}(\Phi)=2^{1-r}\sum_j\frac{\left(|\mathcal{O}_j|\right)_r}{(N)_r},\qquad q_r^+(\Phi)=\sum_j\sum_{a=0}^{1}\frac{\left(|\mathcal{O}_{j,a}|\right)_r}{(N)_r}. \tag*{(2)}

For sampling with replacement and r≥2r \ge2,

q^r±(Φ)=21−r∑j(∣Oj∣N)r,q^r+(Φ)=∑j∑a=01(∣Oj,a∣N)r.(3)\widehat{q}_r^{\pm}(\Phi)=2^{1-r}\sum_j\left(\frac{|\mathcal{O}_j|}{N}\right)^r,\qquad\widehat{q}_r^+(\Phi)=\sum_j\sum_{a=0}^{1}\left(\frac{|\mathcal{O}_{j,a}|}{N}\right)^r. \tag*{(3)}

Here (u)r=u(u−1)⋯(u−r+1)(u)_r=u(u-1)\cdots(u-r+1).

Proof. A new clause destroys every solution precisely when its literal values are equal in every solution. For random signs this requires all its variables to lie in one class Oj\mathcal{O}_j, and conditional on such a choice of variables, exactly two of the 2r2^r sign configurations have this property. This remains true with repeated variables, since signs are sampled independently for each literal. For positive signs the variables must all lie in one part Oj,a\mathcal{O}_{j,a} of one class. □

The next lemma compares the probabilities of destroying all solutions by clauses of consecutive lengths.

Lemma 2.2. Let 2≤r<N2 \le r < N and let Φ\Phi be a satisfiable NAE-formula on NN variables, with arbitrary signs and clause lengths. For ⋆∈{+,±}\star\in\{+,\pm\} put q=qr⋆(Φ)q=q_r^\star(\Phi). Then

qr+1⋆(Φ)≥qr/(r−1)−r−1N−rq.q_{r+1}^\star(\Phi)\ge q^{r/(r-1)}-\frac{r-1}{N-r}q.

Proof. For ⋆=±\star=\pm, let Si=∣Oi∣S_i=|\mathcal{O}_i|, with i∈[J]i\in[J]. For ⋆=+\star=+, let Si=∣Oj,a∣S_i=|\mathcal{O}_{j,a}|, where i=(j,a)i=(j,a) ranges over the pairs in [J]×{0,1}[J]\times\{0,1\}. Put aℓ±=21−ℓa_\ell^{\pm}=2^{1-\ell} and aℓ+=1a_\ell^+=1. By Lemma 2.1,

qℓ⋆(Φ)=aℓ⋆∑i(Si)ℓ(N)ℓ.q_\ell^\star(\Phi)=a_\ell^\star\sum_i\frac{(S_i)_\ell}{(N)_\ell}.

Set yi=(Si−1)r−1/(N−1)r−1y_i=(S_i-1)_{r-1}/(N-1)_{r-1} for Si≥rS_i\ge r, and yi=0y_i=0 for Si<rS_i<r. Then

∑iSiN=1,∑iSiNyi=qar⋆,qr+1⋆(Φ)=ar+1⋆∑iSiNyiSi−rN−r.(4)\sum_i\frac{S_i}{N}=1,\qquad\sum_i\frac{S_i}{N}y_i=\frac{q}{a_r^\star},\qquad q_{r+1}^\star(\Phi)=a_{r+1}^\star\sum_i\frac{S_i}{N}y_i\frac{S_i-r}{N-r}. \tag*{(4)}

For Si≥rS_i\ge r we have yi≤((Si−1)/(N−1))r−1y_i\le((S_i-1)/(N-1))^{r-1}, and for Si<rS_i<r we have yi=0y_i=0. Thus, in either case,

yi(Si−r)≥(N−1)yir/(r−1)−(r−1)yi.(5)y_i(S_i-r)\ge(N-1)y_i^{r/(r-1)}-(r-1)y_i. \tag*{(5)}

Applying convexity of x↦xr/(r−1)x \mapsto x^{r/(r-1)} and using (4)–(5) yields

qr+1⋆(Φ)≥ar+1⋆N−1N−r(qar⋆)r/(r−1)−ar+1⋆ar⋆r−1N−rq≥qr/(r−1)−r−1N−rq.\begin{aligned} q_{r+1}^{\star}(\Phi) \ge a_{r+1}^{\star} \frac{N-1}{N-r} \left(\frac{q}{a_{r}^{\star}}\right)^{r/(r-1)}-\frac{a_{r+1}^{\star}}{a_{r}^{\star}}\frac{r-1}{N-r}q \\ &\ge q^{r/(r-1)}-\frac{r-1}{N-r}q. \end{aligned}

where the last step uses (ar+1⋆/ar⋆)r/(r−1)=1(a_{r+1}^{\star}/a_{r}^{\star})^{r/(r-1)}=1 and ar+1⋆/ar⋆≤1a_{r+1}^{\star}/a_{r}^{\star}\le1.

Forced variables

We call a variable xx forced if Φ\Phi is satisfiable and flipping xx in any satisfying assignment makes that assignment unsatisfying. Let b(Φ)b(\Phi) be the number of forced variables, with b(Φ)=0b(\Phi)=0 for unsatisfiable Φ\Phi. Every variable in a class of size at least two is forced. Consequently, for 2≤r≤N2\le r\le N and ⋆∈{+,±}\star\in\{+,\pm\} Lemma 2.1 implies

qr⋆(Φ)≤(b(Φ))r(N)r≤(b(Φ)N)r.(6)q_{r}^{\star}(\Phi)\le\frac{(b(\Phi))_{r}}{(N)_{r}}\le\left(\frac{b(\Phi)}{N}\right)^{r}. \tag*{(6)}

Finally, the following bounds keep the expected last satisfiable index away from zero and the cap.

Proposition 2.3. For every fixed k≥3k\ge3, as n→∞n\to\infty,

1.5−on(1)≤Eτn+n≤2kln⁡2+on(1),1.5-o_n(1)\le\frac{\mathbb{E}\tau_n^{+}}{n}\le2^k\ln2+o_n(1),
1.514−on(1)≤Eτn±n≤2kln⁡2+on(1).1.514-o_n(1)\le\frac{\mathbb{E}\tau_n^{\pm}}{n}\le2^k\ln2+o_n(1).

Proof. For either model, a fixed assignment violates a random clause with probability at least 21−k−Ok(1/n)2^{1-k}-O_k(1/n). Thus the first moment bound gives

P(Φn,⌊2kln⁡2⋅n⌋⋆∈SAT)≤exp⁡(−nln⁡2+Ok(1)),⋆∈{+,±}.\mathbb{P}\left(\Phi_{n,\lfloor2^k\ln2\cdot n\rfloor}^{\star}\in\mathrm{SAT}\right)\le\exp(-n\ln2+O_k(1)),\qquad\star\in\{+,\pm\}.

Since τn⋆≤2kn\tau_n^{\star}\le2^k n, this implies the upper bounds. For the lower bounds, extending each clause of a random NAE-3-SAT formula by k−3k-3 uniformly chosen distinct variables outside the original clause, with independent uniform signs, preserves satisfiability and produces the NAE-kk-SAT formula. The same construction with positive signs applies to hypergraph 2-colourability. The bounds therefore follow from the results for NAE-3-SAT [2] and 3-uniform hypergraph 2-colourability [5]$. □

Variance and concentration

We begin with the NAE version of the clause replacement argument from [21 Lemma 2.1]. We use the equivalence classes from § 2.1, rather than frozen variables of ordinary SAT.

Proposition 3.1. Fix k≥3k\ge3. There is n0≥k+1n_0\ge k+1 such that the following holds for every n≥n0n\ge n_0. Let Φ\Phi be any NAE-formula on n−1n-1 variables, with arbitrary signs and clause lengths. For ⋆∈{+,±}\star\in\{+,\pm\}, let h⋆h^{\star} be a uniformly random (k−1)(k-1)-clause and let h1⋆,…,hg⋆h_1^{\star},\ldots,h_g^{\star} be independent uniformly random kk-clauses, all on distinct variables within each clause, with signs of type ⋆\star, independent of one another. Then

P(Φ∪{h1⋆,…,hg⋆}∉SAT)≥P(Φ∪{h⋆}∉SAT)−ε,(7)\mathbb{P}\left(\Phi\cup\{h_1^{\star},\ldots,h_g^{\star}\}\notin\mathrm{SAT}\right)\ge\mathbb{P}\left(\Phi\cup\{h^{\star}\}\notin\mathrm{SAT}\right)-\varepsilon, \tag*{(7)}

where ε=n−(k−2)/(k−1)\varepsilon=n^{-(k-2)/(k-1)}, g=⌈kn1/(k−1)⌉g=\left\lceil kn^{1/(k-1)}\right\rceil.

Proof. The assertion is immediate if Φ\Phi is unsatisfiable. Otherwise put q=qk−1⋆(Φ)q=q_{k-1}^{\star}(\Phi). It suffices to consider q>εq>\varepsilon. By Lemma 2.2, qk⋆(Φ)≥q(k−1)/(k−2)−(k−2)q/(n−k)q_k^{\star}(\Phi)\ge q^{(k-1)/(k-2)}-(k-2)q/(n-k). Since q>n−(k−2)/(k−1)q>n^{-(k-2)/(k-1)}, for all sufficiently large nn, uniformly in Φ\Phi,

gqk⋆(Φ)q≥g(n−1/(k−1)−k−2n−k)≥2.\frac{gq_k^{\star}(\Phi)}{q}\ge g\left(n^{-1/(k-1)}-\frac{k-2}{n-k}\right)\ge2.

Independence of the new clauses implies

P(Φ∪{h1⋆,…,hg⋆}∉SAT)≥1−(1−qk⋆(Φ))g≥1−e−gqk⋆(Φ)≥1−e−2q.\mathbb{P}\left(\Phi\cup\{h_1^{\star},\ldots,h_g^{\star}\}\notin\mathrm{SAT}\right)\ge1-\left(1-q_k^{\star}(\Phi)\right)^g\ge1-e^{-gq_k^{\star}(\Phi)}\ge1-e^{-2q}.

If q≤1/2q\le1/2, then 1−e−2q≥q1-e^{-2q}\ge q, which proves the claim. If q>1/2q>1/2, Lemma 2.2 bounds qk⋆(Φ)q_k^{\star}(\Phi) away from zero uniformly in Φ\Phi. Thus e−gqk⋆(Φ)≤εe^{-gq_k^{\star}(\Phi)}\le\varepsilon for sufficiently large nn, which gives a probability at least 1−ε≥q−ε1-\varepsilon\ge q-\varepsilon. □

Using Proposition 3.1 we control the total expected number of forced variables along the clause process.

Proposition 3.2. Fix k≥3k \ge3 and λ>0\lambda> 0. For every integer 0≤M≤λn0 \le M \le\lambda n and either ⋆∈{+,±}\star\in\{+,\pm\},

∑j=0MEb(Φn,j⋆)n=Ok,λ(n1/(k−1)).\sum_{j=0}^{M} \mathbb{E}\frac{b(\Phi_{n,j}^{\star})}{n}=O_{k,\lambda}\left(n^{1/(k-1)}\right).

Proof. By symmetry, the jj-th summand is the probability that Φn,j⋆\Phi_{n,j}^{\star} is satisfiable and xnx_n is forced. The number ζ\zeta of clauses containing xnx_n has distribution Bin⁡(j,k/n)\operatorname{Bin}(j,k/n). Delete these clauses to obtain Φ′\Phi', and erase the literal on xnx_n from each deleted clause to obtain h1,…,hζh_1,\ldots,h_\zeta. Conditional on the incidence positions, Φ′\Phi' consists of j−ζj-\zeta independent uniform kk-clauses on the remaining n−1n-1 variables. The hth_t are independent uniform (k−1)(k-1)-clauses on these variables, independent of Φ′\Phi', with signs of type ⋆\star. If xnx_n is forced, then

Φ′∈SAT⁡,Φ′∪{h1,…,hζ}∉SAT⁡.\Phi' \in\operatorname{SAT}, \qquad\Phi' \cup\{h_1,\ldots,h_\zeta\} \notin\operatorname{SAT}.

Put P(m)=P(Φn−1,m⋆∈SAT⁡)P(m)=\mathbb{P}(\Phi_{n-1,m}^{\star}\in\operatorname{SAT}) and use gg and ε\varepsilon from Proposition 3.1. Conditional on ζ=d\zeta=d and the incidence positions, replace each hth_t by gg fresh kk-clauses. At each replacement, condition on all other clauses and apply Proposition 3.1. The total error is at most dεd\varepsilon, and subtracting the probability that Φ′\Phi' is itself unsatisfiable gives

P(xn is forced∣ incidence positions)≤P(j−d)−P(j−d+dg)+dε.\mathbb{P}(x_n\text{ is forced}\mid\text{ incidence positions})\le P(j-d)-P(j-d+dg)+d\varepsilon.

For 0≤d≤j≤M0\le d\le j\le M, we have P(ζ=d)≤(kM/n)d/d!\mathbb{P}(\zeta=d)\le(kM/n)^d/d!, and

∑j=dM(P(j−d)−P(j−d+dg))≤dg,\sum_{j=d}^{M}\bigl(P(j-d)-P(j-d+dg)\bigr)\le dg,

where the sum telescopes and PP is nonincreasing. Averaging the error with Eζ=kj/n\mathbb{E}\zeta=kj/n, we obtain

∑j=0MEb(Φn,j⋆)n≤g∑d≥0d(kM/n)dd!+ε∑j=0Mkjn\sum_{j=0}^{M}\mathbb{E}\frac{b(\Phi_{n,j}^{\star})}{n} \le g\sum_{d\ge0}\frac{d(kM/n)^d}{d!} +\varepsilon\sum_{j=0}^{M}\frac{kj}{n}
=kMnekM/ng+kM(M+1)2nε=Ok,λ(n1/(k−1)).=\frac{kM}{n}e^{kM/n}g+\frac{kM(M+1)}{2n}\varepsilon =O_{k,\lambda}\left(n^{1/(k-1)}\right).

Fix an integer M≥1M\ge1 and ⋆∈{+,±}\star\in\{+,\pm\}. Write C1⋆,…,CM⋆C_1^\star,\ldots,C_M^\star for the independent clauses of Φn,M⋆\Phi_{n,M}^\star and set

τn⋆(M)=max⁡{0≤m≤M:Φn,m⋆∈SAT⁡}.\tau_n^\star(M)=\max\{0\le m\le M:\Phi_{n,m}^\star\in\operatorname{SAT}\}.

For 1≤i≤M1\le i\le M, let Φm,−i⋆\Phi_{m,-i}^\star be the formula Φn,m⋆\Phi_{n,m}^\star with the clause at position ii removed if i≤mi\le m. Set

τn,−i⋆(M)=max⁡{0≤m≤M:Φm,−i⋆∈SAT⁡}.\tau_{n,-i}^\star(M)=\max\{0\le m\le M:\Phi_{m,-i}^\star\in\operatorname{SAT}\}.

In particular, τn,−i⋆(M)≥τn⋆(M)\tau_{n,-i}^\star(M)\ge\tau_n^\star(M), and τn,−i⋆(M)\tau_{n,-i}^\star(M) is independent of Ci⋆C_i^\star.

Proposition 3.3. For ⋆∈{+,±}\star\in\{+,\pm\},

Var⁡(τn⋆(M))≤∑i=1ME(τn,−i⋆(M)−τn⋆(M))2.\operatorname{Var}(\tau_n^\star(M))\le\sum_{i=1}^{M}\mathbb{E}\left(\tau_{n,-i}^\star(M)-\tau_n^\star(M)\right)^2.

Proof. Apply Eq. (3.6) with Z=τn⋆(M)Z=\tau_n^\star(M) and Zi=τn,−i⋆(M)Z_i=\tau_{n,-i}^\star(M). □\square

Proposition 3.4. For every 1≤i≤M1\le i\le M and either ⋆∈{+,±}\star\in\{+,\pm\},

E(τn,−i⋆(M)−τn⋆(M))2≤2∑m=iMEmin⁡{Mqk⋆(Φm,−i⋆),1}.\mathbb{E}\left(\tau_{n,-i}^\star(M)-\tau_n^\star(M)\right)^2\le2\sum_{m=i}^{M}\mathbb{E}\min\{Mq_k^\star(\Phi_{m,-i}^\star),1\}.

Proof. The proof of [21 Lemma 3.2] applies with killing probability qk⋆q_k^\star, as it only uses independence of the clauses and monotonicity of satisfiability under clause addition. □\square

Lemma 3.5. For fixed k≥3k\ge3, λ>0\lambda>0, integers 1≤M≤λn1\le M\le\lambda n and ⋆∈{+,±}\star\in\{+,\pm\},

Var⁡(τn⋆(M))=Ok,λ(n1+1/k+1/(k−1)).\operatorname{Var}(\tau_n^\star(M))=O_{k,\lambda}\left(n^{1+1/k+1/(k-1)}\right).

Proof. By (6),

min⁡{Mak⋆(Φm,−i⋆),1}≤M1/kb(Φm,−i⋆)n.\min\left\{M a_k^\star\left(\Phi_{m,-i}^\star\right),1\right\}\le M^{1/k}\frac{b\left(\Phi_{m,-i}^\star\right)}{n}.

For m≥im\ge i, Φm,−i⋆\Phi_{m,-i}^\star has the same distribution as Φn,m−1⋆\Phi_{n,m-1}^\star. Thus Propositions 3.2–3.4 yield

Var⁡(τn⋆(M))≤2M1/k∑i=1M∑m=iME[b(Φn,m−1⋆)n]\operatorname{Var}\left(\tau_n^\star(M)\right)\le2M^{1/k}\sum_{i=1}^{M}\sum_{m=i}^{M}\mathbb{E}\left[\frac{b\left(\Phi_{n,m-1}^\star\right)}{n}\right]
≤2M1+1/k∑j=0M−1E[b(Φn,j⋆)n]=Ok,λ(n1+1/k+1/(k−1)).\le2M^{1+1/k}\sum_{j=0}^{M-1}\mathbb{E}\left[\frac{b\left(\Phi_{n,j}^\star\right)}{n}\right]=O_{k,\lambda}\left(n^{1+1/k+1/(k-1)}\right).

Corollary 3.6. Under the assumptions of Lemma 3.5, for either ⋆∈{+,±}\star\in\{+,\pm\},

P(∣τn⋆(M)−Eτn⋆(M)∣≥n19/20)=Ok,λ(n−1/15).\mathbb{P}\left(\left|\tau_n^\star(M)-\mathbb{E}\tau_n^\star(M)\right|\ge n^{19/20}\right)=O_{k,\lambda}\left(n^{-1/15}\right).

Proof. Apply Chebyshev’s inequality and use 1+1/k+1/(k−1)≤11/61+1/k+1/(k-1)\le11/6 for k≥3k\ge3. □

From concentration to convergence

We now use the concentration bound to prove that the normalized expectations converge. For λ>0\lambda>0 and ⋆∈{+,±}\star\in\{+,\pm\}, put

Mn,λ=⌊λn⌋,τn,λ⋆=min⁡{ξn⋆−1,Mn,λ},μn,λ⋆=Eτn,λ⋆n.M_{n,\lambda}=\lfloor\lambda n\rfloor,\qquad\tau_{n,\lambda}^\star=\min\left\{\xi_n^\star-1,M_{n,\lambda}\right\},\qquad\mu_{n,\lambda}^\star=\frac{\mathbb{E}\tau_{n,\lambda}^\star}{n}.

Thus τn,λ⋆=τn⋆(Mn,λ)\tau_{n,\lambda}^\star=\tau_n^\star(M_{n,\lambda}), and τn,2λ⋆=τn⋆\tau_{n,2\lambda}^\star=\tau_n^\star.

Theorem 4.1. Fix an integer k≥3k\ge3, λ>0\lambda>0 and ⋆∈{+,±}\star\in\{+,\pm\}. Suppose there exist

0<a≤b<λ,0<δ<1/2,γ>0,0≤K<+∞0<a\le b<\lambda,\qquad0<\delta<1/2,\qquad\gamma>0,\qquad0\le K<+\infty

such that for all sufficiently large nn,

a≤μn,λ⋆≤b,(8)a\le\mu_{n,\lambda}^\star\le b, \tag*{(8)}
P(∣τn,λ⋆−nμn,λ⋆∣≥n1−δ)≤Kn−γ.(9)\mathbb{P}\left(\left|\tau_{n,\lambda}^\star-n\mu_{n,\lambda}^\star\right|\ge n^{1-\delta}\right)\le Kn^{-\gamma}. \tag*{(9)}

Then μn,λ⋆\mu_{n,\lambda}^\star converges to αk⋆∈[a,b]\alpha_k^\star\in[a,b], and

lim⁡n→∞P(τn,λ⋆≥⌊cn⌋)={1,0≤c<αk⋆,0,c>αk⋆.\lim_{n\to\infty}\mathbb{P}\left(\tau_{n,\lambda}^\star\ge\lfloor cn\rfloor\right)= \begin{cases} 1, & 0\le c<\alpha_k^\star,\\ 0, & c>\alpha_k^\star. \end{cases}

Poissonian model

Fix k≥3k\ge3. For n≥1n\ge1 and c≥0c\ge0, let Ψn,cn+\Psi_{n,cn}^+ be the NAE-formula with Po⁡(cn)\operatorname{Po}(cn) independent positive clauses, each formed by sampling kk variables independently and uniformly from the nn variables. Thus repetitions within clauses are allowed. Define Ψn,cn±\Psi_{n,cn}^{\pm} in the same way, with independent uniform signs for each literal. For ⋆∈{+,±}\star\in\{+,\pm\}, write sn⋆(c)=P(Ψn,cn⋆∈SAT)s_n^\star(c)=\mathbb{P}(\Psi_{n,cn}^\star\in\mathrm{SAT}).

Lemma 4.2. For any n1,n2∈Nn_1,n_2\in\mathbb{N}, n=n1+n2n=n_1+n_2, c≥0c\ge0 and ⋆∈{+,±}\star\in\{+,\pm\},

sn⋆(c)≥sn1⋆(c)⋅sn2⋆(c).s_n^\star(c)\ge s_{n_1}^\star(c)\cdot s_{n_2}^\star(c).

Proof. We use a Poisson version of the combinatorial interpolation of [7 Proposition 2], as in [21 Lemma 5.2], with the killing probabilities from Lemma 2.1. Fix ⋆∈{+,±}\star\in\{+,\pm\} and partition the variable set VV into V1,V2V_1,V_2 of sizes n1,n2n_1,n_2. At time t∈[0,1]t\in[0,1], sample independent numbers of global and local clauses

ξ∼Po⁡(cnt),ξ1∼Po⁡(cn1(1−t)),ξ2∼Po⁡(cn2(1−t)).\xi\sim\operatorname{Po}(cnt),\qquad\xi_1\sim\operatorname{Po}(cn_1(1-t)),\qquad\xi_2\sim\operatorname{Po}(cn_2(1-t)).

Each clause has kk independently chosen variables from VV, V1V_1 or V2V_2 respectively, and signs of type ⋆\star. Let Ψt⋆\Psi_t^\star be their union and f⋆(t)=P(Ψt⋆∈SAT)f^\star(t)=\mathbb{P}(\Psi_t^\star\in\mathrm{SAT}). Then

f⋆(0)=sn1⋆(c)sn2⋆(c),f⋆(1)=sn⋆(c).f^\star(0)=s_{n_1}^\star(c)s_{n_2}^\star(c),\qquad f^\star(1)=s_n^\star(c).

For each satisfiable realization of Ψ⋆\Psi^\star, take the classes and parts from § 2.1. A clause confined to VhV_h therefore uses the intersections Oj∩Vh\mathcal{O}_j\cap V_h (or Oj,a∩Vh\mathcal{O}_{j,a}\cap V_h) for h=1,2h=1,2. The Poisson add-one identity says that differentiation with respect to a clause family’s mean gives the expected change in the satisfiability indicator upon adding one clause, and this change is minus its killing probability. Therefore, Lemma 2.1 gives

∂f±(t)∂t=cn21−kE[1{Ψt±∈SAT}∑j(∑h=12nhn(∣Oj∩Vh∣nh)k−(∣Oj∣n)k)]≥0.\frac{\partial f^{\pm}(t)}{\partial t}=cn^{2^{1-k}}\mathbb{E}\left[\mathbf{1}_{\{\Psi_t^{\pm}\in\mathrm{SAT}\}}\sum_j\left(\sum_{h=1}^{2}\frac{n_h}{n}\left(\frac{|\mathcal{O}_j\cap V_h|}{n_h}\right)^k-\left(\frac{|\mathcal{O}_j|}{n}\right)^k\right)\right]\geq0.

Indeed, due to convexity,

(∣Oj∣n)k=(∑h=12nhn∣Oj∩Vh∣nh)k≤∑h=12nhn(∣Oj∩Vh∣nh)k.\left(\frac{|\mathcal{O}_j|}{n}\right)^k=\left(\sum_{h=1}^{2}\frac{n_h}{n}\frac{|\mathcal{O}_j\cap V_h|}{n_h}\right)^k\leq\sum_{h=1}^{2}\frac{n_h}{n}\left(\frac{|\mathcal{O}_j\cap V_h|}{n_h}\right)^k.

For positive clauses, Lemma 2.1 gives

∂f+(t)∂t=cnE[1{Ψt+∈SAT}∑j=1J∑a=01(∑h=12nhn(∣Oj,a∩Vh∣nh)k−(∣Oj,a∣n)k)]≥0.\frac{\partial f^{+}(t)}{\partial t}=cn\mathbb{E}\left[\mathbf{1}_{\{\Psi_t^{+}\in\mathrm{SAT}\}}\sum_{j=1}^{J}\sum_{a=0}^{1}\left(\sum_{h=1}^{2}\frac{n_h}{n}\left(\frac{|\mathcal{O}_{j,a}\cap V_h|}{n_h}\right)^k-\left(\frac{|\mathcal{O}_{j,a}|}{n}\right)^k\right)\right]\geq0.

Integrating over tt proves both inequalities. □

From the Poisson model to proper clauses

We next transfer the concentration bounds to the Poisson model. Fix ⋆∈{+,±}\star\in\{+,\pm\} and parameters k,λ,a,b,δ,γ,Kk,\lambda,a,b,\delta,\gamma,K from the hypothesis of Theorem 4.1.

Lemma 4.3. Fix k≥3k\geq3 and D≥0D\geq0. For n≥kn\geq k and 0≤c≤D0\leq c\leq D, put θn=(n)k/nk\theta_n=(n)_k/n^k and let ζ∼Po⁡(cnθn)\zeta\sim\operatorname{Po}(cn\theta_n). For either ⋆∈{+,±}\star\in\{+,\pm\},

e−D(k2)P(Φn,ζ⋆∈SAT)≤sn⋆(c)≤P(Φn,ζ⋆∈SAT).(10)e^{-D\binom{k}{2}}\mathbb{P}(\Phi^\star_{n,\zeta}\in\mathrm{SAT})\leq s_n^\star(c)\leq\mathbb{P}(\Phi^\star_{n,\zeta}\in\mathrm{SAT}). \tag*{(10)}

Moreover, cn−D(k2)≤Eζ≤cncn-D\binom{k}{2}\leq\mathbb{E}\zeta\leq cn and Var⁡ζ≤Dn\operatorname{Var}\zeta\leq Dn. All bounds are uniform over c∈[0,D]c\in[0,D].

Proof. Apply the marked Poisson thinning argument of [21 Lemma 5.3]. The numbers of clauses with distinct variables and with a repetition are independent with laws

ζ∼Po⁡(cnθn),η∼Po⁡(cn(1−θn)).\zeta\sim\operatorname{Po}(cn\theta_n),\qquad\eta\sim\operatorname{Po}(cn(1-\theta_n)).

Conditional on ζ\zeta and η\eta, the two clause families are independent, and any clause with distinct variables is a uniformly random set of size kk with signs of type ⋆\star. Thus the proper family Ψ′⋆\Psi^{\prime\star} has the law Φn,ζ⋆\Phi^\star_{n,\zeta} in either model. With Ψ⋆\Psi^\star denoting the full formula,

{Ψ′⋆∈SAT}∩{η=0}⊆{Ψ⋆∈SAT}⊆{Ψ′⋆∈SAT}.(11)\{\Psi^{\prime\star}\in\mathrm{SAT}\}\cap\{\eta=0\}\subseteq\{\Psi^\star\in\mathrm{SAT}\}\subseteq\{\Psi^{\prime\star}\in\mathrm{SAT}\}. \tag*{(11)}

Independence and P(η=0)=e−cn(1−θn)≥e−D(k2)\mathbb{P}(\eta=0)=e^{-cn(1-\theta_n)}\geq e^{-D\binom{k}{2}} give the two inequalities. The moment bounds follow from Eζ=Var⁡ζ=cnθn\mathbb{E}\zeta=\operatorname{Var}\zeta=cn\theta_n. □

Lemma 4.4. Assume (8)–(9) and fix D>bD>b. For all sufficiently large nn, uniformly over 0≤c≤D0\leq c\leq D,

c≤μn,λ⋆−2n−δ⟹sn⋆(c)≥12e−D(k2),(12)c\leq\mu^\star_{n,\lambda}-2n^{-\delta}\quad\Longrightarrow\quad s_n^\star(c)\geq\frac{1}{2}e^{-D\binom{k}{2}}, \tag*{(12)}
c≥μn,λ⋆+2n−δ⟹sn⋆(c)=O(n−γ+n−(1−2δ)).(13)c\geq\mu^\star_{n,\lambda}+2n^{-\delta}\quad\Longrightarrow\quad s_n^\star(c)=O\left(n^{-\gamma}+n^{-(1-2\delta)}\right). \tag*{(13)}

Proof. Take ζ\zeta from Lemma 4.3 independently of the randomness inside clauses. By Chebyshev’s inequality and (9),

∣ζ−cn∣≤12n1−δ,∣τn,λ⋆−nμn,λ⋆∣<n1−δ|\zeta-cn|\leq\frac{1}{2}n^{1-\delta},\qquad|\tau^\star_{n,\lambda}-n\mu^\star_{n,\lambda}|<n^{1-\delta}

except on an event of probability O(n−γ+n−(1−2δ))O(n^{-\gamma}+n^{-(1-2\delta)}) uniformly for c∈[0,D]c\in[0,D]. If c≤μn,λ⋆−2n−δc\leq\mu^\star_{n,\lambda}-2n^{-\delta}, these inequalities yield

ζ≤cn+12n1−δ≤nμn,λ⋆−32n1−δ<τn,λ⋆≤ξn⋆−1.\zeta\leq cn+\frac{1}{2}n^{1-\delta}\leq n\mu^\star_{n,\lambda}-\frac{3}{2}n^{1-\delta}<\tau^\star_{n,\lambda}\leq\xi^\star_n-1.

Thus Φn,ζ⋆\Phi^\star_{n,\zeta} is satisfiable outside the exceptional event, and (10) implies (12) for nn large enough.

Conversely, if c≥μn,λ⋆+2n−δc \ge\mu^\star_{n,\lambda}+2n^{-\delta}, then

ζ≥cn−12n1−δ≥nμn,λ⋆+32n1−δ>τn,λ⋆\zeta\ge cn-\frac{1}{2}n^{1-\delta}\ge n\mu^\star_{n,\lambda}+\frac{3}{2}n^{1-\delta}>\tau^\star_{n,\lambda}

with probability 1−O(n−γ+n−(1−2δ))1-O(n^{-\gamma}+n^{-(1-2\delta)}). Outside the exceptional event, τn,λ⋆<bn+n1−δ<Mn,λ\tau^\star_{n,\lambda}<bn+n^{1-\delta}<M_{n,\lambda} for large nn, hence τn,λ⋆=ξn⋆−1\tau^\star_{n,\lambda}=\xi^\star_n-1, so Φn,ζ\Phi_{n,\zeta} is unsatisfiable. The upper bound in (10) now yields (13).

Fix D>bD>b. The next lemma compares the expected threshold locations at different sizes.

Lemma 4.5. For all sufficiently large r,sr,s,

μr+s,λ⋆≥min⁡{μr,λ⋆,μs,λ⋆}−4min⁡{r,s}−δ,(14)\mu^\star_{r+s,\lambda}\ge\min\{\mu^\star_{r,\lambda},\mu^\star_{s,\lambda}\}-4\min\{r,s\}^{-\delta}, \tag*{(14)}
μs+1,λ⋆≥μs,λ⋆−4s−δ.(15)\mu^\star_{s+1,\lambda}\ge\mu^\star_{s,\lambda}-4s^{-\delta}. \tag*{(15)}

Proof. Choose c=min⁡{μr,λ⋆,μs,λ⋆}−2min⁡{r,s}−δc=\min\{\mu^\star_{r,\lambda},\mu^\star_{s,\lambda}\}-2\min\{r,s\}^{-\delta}. For large r,sr,s it lies in [0,b][0,b]. By (12) and Lemma 4.2,

sr+s⋆(c)≥sr⋆(c)ss⋆(c)≥14e−2D(k2).s^\star_{r+s}(c)\ge s^\star_r(c)s^\star_s(c)\ge\frac{1}{4}e^{-2D\binom{k}{2}}.

(13) therefore implies c<μr+s,λ⋆+2(r+s)−δc<\mu^\star_{r+s,\lambda}+2(r+s)^{-\delta} for large r+sr+s, proving (14).

For (15), take c=μs,λ⋆−2s−δc=\mu^\star_{s,\lambda}-2s^{-\delta}. The one-variable formula is empty with probability e−ce^{-c}, so s1⋆(c)≥e−c≥e−Ds^\star_1(c)\ge e^{-c}\ge e^{-D}. Thus Lemma 4.2 and (12) imply that ss+1⋆(c)≥ss⋆(c)s1⋆(c)≥12e−D(1+(k2))s^\star_{s+1}(c)\ge s^\star_s(c)s^\star_1(c)\ge\frac{1}{2}e^{-D(1+\binom{k}{2})}, which is bounded away from zero. Applying (13) once more yields μs+1,λ⋆>c−2(s+1)−δ≥μs,λ⋆−4s−δ\mu^\star_{s+1,\lambda}>c-2(s+1)^{-\delta}\ge\mu^\star_{s,\lambda}-4s^{-\delta}.

Convergence

Lemma 4.6. Let (un)n∈N(u_n)_{n\in\mathbb{N}} be a bounded real-valued sequence. Suppose there exist 0≤A<+∞0\le A<+\infty and β>0\beta>0, such that for large enough r,sr,s with 1/3≤r/s≤31/3\le r/s\le3,

ur+s≥min⁡{ur,us}−Amin⁡{r,s}−β,u_{r+s}\ge\min\{u_r,u_s\}-A\min\{r,s\}^{-\beta},
us+1≥us−As−β.u_{s+1}\ge u_s-As^{-\beta}.

Then unu_n converges.

Proof. This is [21], Lemma 5.4.

Proof of Theorem 4.1

Proof of Theorem 4.1. Apply Lemma 4.6 to the sequence μn,λ⋆\mu^\star_{n,\lambda} from Lemma 4.5, with A=4A=4 and β=δ\beta=\delta. This gives μn,λ⋆→αk⋆∈[a,b]\mu^\star_{n,\lambda}\to\alpha^\star_k\in[a,b]. For fixed 0≤c<αk⋆0\le c<\alpha^\star_k, the gap μn,λ⋆−c\mu^\star_{n,\lambda}-c is bounded away from zero for large nn, so (9) implies τn,λ⋆≥⌊cn⌋\tau^\star_{n,\lambda}\ge\lfloor cn\rfloor whp. For fixed c>αk⋆c>\alpha^\star_k, (9) instead gives P(τn,λ⋆≥⌊cn⌋)→0\mathbb{P}(\tau^\star_{n,\lambda}\ge\lfloor cn\rfloor)\to0, completing the proof.

Proof of Theorem 1.1

Proof of Theorem 1.1. Take λ=2k\lambda=2^k. By Proposition 2.3, condition (8) holds with a=1a=1 and b=2k−1b=2^k-1. Corollary 3.6 gives (9) with δ=1/20\delta=1/20 and γ=1/15\gamma=1/15, thus Theorem 4.1 can be applied. For c<λc<\lambda and large nn, the events {Φn,⌊cn⌋⋆∈SAT}\{\Phi^\star_{n,\lfloor cn\rfloor}\in\mathrm{SAT}\} and {τn,λ⋆≥⌊cn⌋}\{\tau^\star_{n,\lambda}\ge\lfloor cn\rfloor\} coincide, and for c≥λc\ge\lambda we use monotonicity of the property {Φn,⌊cn⌋⋆∈SAT}\{\Phi^\star_{n,\lfloor cn\rfloor}\in\mathrm{SAT}\}.

Threshold comparison

In this section we prove Theorem 1.2. For c≥0c\ge0 and t∈[0,1]t\in[0,1], let Ψn,cn(t)\Psi^{(t)}_{n,cn} be the random formula consisting of ξ+∼Po⁡(cnt)\xi^+\sim\operatorname{Po}(cnt) positive clauses and ξ±∼Po⁡(cn(1−t))\xi^\pm\sim\operatorname{Po}(cn(1-t)) signed clauses, with ξ+\xi^+ and ξ±\xi^\pm being independent. Each clause samples its kk variables independently and uniformly, with repetitions allowed, and signs in all ξ±\xi^\pm clauses are independent and uniformly random.

For each satisfiable Φ\Phi, use the classes Oj\mathcal{O}_j and parts Oj,a\mathcal{O}_{j,a} from Section 2.1. By Lemma 2.1,

q^k+(Φ)=∑j∑a=11(∣Oj,a∣n)k,q^k±(Φ)=21−k∑j(∣Oj∣n)k,\widehat{q}_k^+(\Phi)=\sum_j\sum_{a=1}^{1}\left(\frac{|\mathcal{O}_{j,a}|}{n}\right)^k,\qquad \widehat{q}_k^\pm(\Phi)=2^{1-k}\sum_j\left(\frac{|\mathcal{O}_j|}{n}\right)^k,

and convexity implies q^k+(Φ)≥q^k±(Φ)\widehat{q}_k^+(\Phi)\ge\widehat{q}_k^\pm(\Phi) for k≥3k\ge3.

Writing fn(t,c)=P(Ψn,cn(t)∈SAT)f_n(t,c)=\mathbb{P}(\Psi^{(t)}_{n,cn}\in\mathrm{SAT}), the same Poisson add-one identity as in Lemma 4.2 yields

∂fn(t,c)∂t=cnE[1{Ψn,cn(t)∈SAT}(q^k+(Ψn,cn(t))−q^k±(Ψn,cn(t)))]≤0.\frac{\partial f_n(t,c)}{\partial t} =cn\mathbb{E}\left[\mathbf{1}_{\{\Psi^{(t)}_{n,cn}\in\mathrm{SAT}\}}\left(\widehat{q}_k^+(\Psi^{(t)}_{n,cn})-\widehat{q}_k^\pm(\Psi^{(t)}_{n,cn})\right)\right]\le0.

Hence sn+(c)≤sn±(c)s_n^{+}(c) \le s_n^{\pm}(c) for every nn and c≥0c \ge0. Suppose that for some kk, αkNAE<c<αk2-col\alpha_k^{\mathrm{NAE}} < c < \alpha_k^{2\text{-col}}. Theorem 1.1, Poisson concentration and monotonicity imply that the distinct-variable formula with ζ∼Po⁡(cnθn)\zeta\sim\operatorname{Po}(cn\theta_n) positive clauses is satisfiable with probability tending to one, while the corresponding signed formula is satisfiable with probability tending to zero. Here θn=(n)k/nk\theta_n = (n)_k/n^k and ζ/n\zeta/n converges in probability to cc. Furthermore, the coupling from Lemma 4.3 implies that sn+(c)s_n^{+}(c) is bounded away from zero, and that sn±(c)→0s_n^{\pm}(c) \to0, which leads to a contradiction. Thus αk2-col≤αkNAE\alpha_k^{2\text{-col}} \le\alpha_k^{\mathrm{NAE}}.

Pavel Zakharov, [email protected], Bielefeld University, Faculty of Mathematics, Universitätsstrasse 25, 33615 Bielefeld, Germany.

References

  1. [1]E. Abbe, A. Montanari: On the Concentration of the Number of Solutions of Random Satisfiability Formulas. Random Structures & Algorithms 45 (2014) 362–382.arxiv.org/abs/1006.3786
  2. [2]D. Achlioptas, A. Chvátal, G. Istrate, C. Moore: The Phase Transition in 1-in-k SAT and NAE 3-SAT. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001) 721–722.DOI
  3. [3]D. Achlioptas, E. Friedgut: A Sharp Threshold for k-Colorability. Random Structures & Algorithms 14 (1999) 63–70.
  4. [4]D. Achlioptas, C. Moore: On the 2-Colorability of Random Hypergraphs. Randomization and Approximation Techniques in Computer Science (2002) 78–90.arxiv.org/abs/2011.04809
  5. [5]D. Achlioptas, C. Moore: Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. SIAM Journal on Computing 36 (2006) 740–762.
  6. [6]D. Achlioptas, A. Naor: The Two Possible Values of the Chromatic Number of a Random Graph. Annals of Mathematics 162 (2005) 1335–1351.
  7. [7]M. Bayati, D. Gamarnik, P. Tetali: Combinatorial Approach to the Interpolation Method and Scaling Limits in Sparse Random Graphs. Annals of Probability 41 (2013) 4080–4115.
  8. [9]G. Carenini: The Scaling Window of Random k-SAT. arXiv:2609.26222 (2026).
  9. [10]G. Carenini: A Polynomial Scaling Window for Random k-SAT and a Proof of the Satisfiability Conjecture. Electronic Colloquium on Computational Complexity, Report No. 229 (2026).
  10. [11]V. Chvátal, B. Reed: Mick Gets Some (the Odds Are on His Side). Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992) 620–627.
  11. [12]A. Coja-Oghlan, M. Isaev, M. Kang, P. Zakharov: The Chromatic Number of a Random Graph with o(n^{3/2}) Edges. arXiv:2610.33678 (2026).
  12. [13]A. Coja-Oghlan, K. Panagiotou: Catching the k-NAESAT Threshold. Proceedings of the 44th Annual ACM Symposium on the Theory of Computing (2012) 899–908.
  13. [14]A. Coja-Oghlan, L. Zdeborová: The Condensation Transition in Random Hypergraph 2-Coloring. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (2012) 241–250.
  14. [15]J. Ding, A. Sly, N. Sun: Proof of the Satisfiability Conjecture for Large k. Annals of Mathematics 196 (2022) 1–388.
  15. [16]P. Erdős, A. Rényi: On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960) 17–61.
  16. [17]E. Friedgut, with an appendix by J. Bourgain: Sharp Thresholds of Graph Properties, and the k-SAT Problem. Journal of the American Mathematical Society 12 (1999) 1017–1054.DOI
  17. [18]E. Friedgut: Hunting for Sharp Thresholds. Random Structures & Algorithms 26 (2005) 37–51.DOI
  18. [19]A. Heckel: The Chromatic Number of Dense Random Graphs. Random Structures & Algorithms 53 (2018) 140–182.DOI
  19. [20]F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, L. Zdeborová: Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems. Proceedings of the National Academy of Sciences 104 (2007) 10318–10323.pubmed.ncbi.nlm.nih.gov/17567754
  20. [21]OpenAI: A Limiting Satisfiability Threshold for Every Fixed Clause Size. preprint (2026).DOI

Paper details

vlnc:W_6swds7p6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents