Section 7.2.2.2: Satisfiability

Exercise 202. [HM21] This exercise amplifies the text's proof of Theorem C when $c > 1$.

a) Explain the right-hand side of Eq. (93).

b) Why does (97) follow from (95), (96), and the stated choices of $t$ and $m$?

Verified: no
Solve time: 4m43s

---

$$ \textbf{Solution.} $$

The proof of Theorem C uses the random variable $X$, the number of $t$-snakes contained in the random formula. The second moment argument requires estimating

$$ \frac{\mathbf E X^2}{(\mathbf E X)^2}. $$

The equations in the text arise from counting pairs of $t$-snakes according to the number of clauses they have in common.

(a)

Equation (93) gives the probability $f(r)$ that $r$ specified clauses occur in the random formula. The right-hand side is

$$ f(r)= \left(\frac{m}{2n(n-1)}\right)^r \left(1+O\left(\frac{r^2}{n}\right) +O\left(\frac{r^m}{m!n^2}\right)\right). $$

The first factor is the main term. There are

$$ 2n(n-1) $$

possible clauses of length $2$, and the random formula consists of $m$ independently chosen clauses. Thus a particular clause is present with probability

$$ \frac{m}{2n(n-1)}. $$

If the $r$ specified clauses are distinct, the probability that all of them occur is approximately the $r$-th power of this probability, giving

$$ \left(\frac{m}{2n(n-1)}\right)^r . $$

The two error terms measure the effect of the fact that the $m$ clauses are sampled without replacement and that the approximation by independent choices is not exact. The term

$$ O\left(\frac{r^2}{n}\right) $$

comes from the interaction among the $r$ specified clauses, while

$$ O\left(\frac{r^m}{m!n^2}\right) $$

accounts for the possibility that the number of clauses is large enough for higher-order corrections in the sampling process to matter.

For the later application $r\leq 4t$ and $t=o(n^{1/2})$, these error terms are small, so the displayed expression gives the needed asymptotic estimate for $f(r)$.

(b)

From (95),

$$ \frac{\mathbf E X^2}{(\mathbf E X)^2}

\sum_{r=0}^{2t} p_r \frac{f(4t-r)}{f(2t)^2}. $$

Using (93), with $r\leq 2t$, the quotient of the $f$-terms is

$$ \frac{f(4t-r)}{f(2t)^2}

\left(\frac{2n(n-1)}{m}\right)^r \left(1+O\left(\frac{t^2}{n}\right)\right). $$

Hence (95) becomes

$$ \frac{\mathbf E X^2}{(\mathbf E X)^2}

\left(1+O\left(\frac{t^2}{n}\right)\right) \sum_{r=0}^{2t} p_r \left(\frac{2n(n-1)}{m}\right)^r . $$

Now choose

$$ t=\lfloor n^{1/5}\rfloor, \qquad m=\lfloor n+n^{5/6}\rfloor . $$

The factor appearing in the last sum satisfies

$$ \frac{2n(n-1)}{m}

2n\frac{n-1}{n+n^{5/6}}, $$

and therefore

$$ \left(\frac{2n(n-1)}{m}\right)^r

(2n)^r \left(\frac{n-1}{n+n^{5/6}}\right)^r . $$

The second factor gives an exponential decay. Indeed,

$$ \frac{n-1}{n+n^{5/6}}

1-\Theta(n^{-1/6}), $$

so

$$ \left(\frac{n-1}{n+n^{5/6}}\right)^r

O(e^{-r n^{-1/6}}). $$

Therefore

$$ p_r \left(\frac{2n(n-1)}{m}\right)^r

(2n)^r p_r,O(e^{-r n^{-1/6}}). $$

We now apply (96).

For $1\leq r<t$, equation (96) gives

$$ (2n)^r p_r=O(t^4/n). $$

Consequently the total contribution from these terms is

$$ O\left(\frac{t^4}{n} \sum_{r=1}^{t}e^{-r n^{-1/6}}\right). $$

The geometric sum is

$$ O(n^{1/6}), $$

so this part is

$$ O\left(\frac{t^4}{n}n^{1/6}\right). $$

Since $t=n^{1/5}+O(1)$,

$$ \frac{t^4}{n}n^{1/6}

n^{4/5-1+1/6}

n^{-1/30}. $$

For $t\leq r<2t$, (96) gives

$$ (2n)^r p_r=O(t), $$

and hence the contribution is bounded by

$$ O\left( t\sum_{r=t}^{2t}e^{-r n^{-1/6}} \right). $$

Because

$$ t n^{-1/6}=n^{1/5-1/6}=n^{1/30}, $$

this is exponentially small:

$$ O\left(t e^{-\Theta(n^{1/30})}\right). $$

Finally, for $r=2t$, equation (96) gives

$$ (2n)^{2t}p_{2t}=O(n), $$

and its contribution is

$$ O\left(n e^{-2t n^{-1/6}}\right)

O\left(n e^{-\Theta(n^{1/30})}\right), $$

which is again negligible.

The error factor from (93) is

$$ O\left(\frac{t^2}{n}\right)

O(n^{2/5-1})

O(n^{-3/5}), $$

which is smaller than $O(n^{-1/30})$. Hence

$$ \frac{\mathbf E X^2}{(\mathbf E X)^2}

1+O(n^{-1/30}). $$

By the second moment principle,

$$ \Pr(X>0) \geq \frac{(\mathbf E X)^2}{\mathbf E X^2}

1-O(n^{-1/30}). $$

Thus the probability that the random formula contains a $t$-snake is

$$ 1-O(n^{-1/30}), $$

and therefore the satisfiability probability satisfies

$$ S_2!\left(\lfloor n+n^{5/6}\rfloor,n\right)

O(n^{-1/30}), $$

which is exactly equation (97).