Section 7.2.2.2: Satisfiability

Exercise 182. [M16] [M16] For which values of $m$ in Fig. 41 does $T_m$ have a constant value?

Verified: no
Solve time: 5m07s

---

$$ \text{Let }T_m=T_m(C) $$

denote the number of assignments satisfying a set $C$ of $m$ distinct clauses chosen from the $80$ possible clauses on five variables.

For an assignment $x$, exactly

$$ \binom53=10 $$

clauses are false. Let $F_x$ be this set of ten clauses. Then

$$ T_m(C)=#{x:F_x\cap C=\varnothing}. $$

Equivalently, if $D$ is the set of omitted clauses, $|D|=80-m$, then

$$ T_m(C)=#{x:F_x\subseteq D}. $$

This description immediately gives the constant cases at the two ends.

For $m=0$, every assignment satisfies the empty set of clauses, so

$$ T_0=32 . $$

For $m=1$, every clause rules out exactly $4$ of the $32$ assignments, hence

$$ T_1=32-4=28 . $$

Now suppose that $m\geq 71$. Then the omitted set has size

$$ 80-m\leq 9 . $$

Since every $F_x$ contains $10$ clauses, no $F_x$ can be contained in the omitted set. Therefore

$$ T_m=0\qquad(71\leq m\leq80). $$

It remains to show that no other value of $m$ gives a constant distribution.

Consider the variance of $T_m$ when the $m$-clause set is chosen uniformly. The variable $T_m$ is constant exactly when this variance is zero. We compute the second moment.

For two assignments $x,y$, let their Hamming distance be $d$. The two sets $F_x,F_y$ have intersection

$$ |F_x\cap F_y|=\binom{5-d}{3}, $$

because a clause can be false for both assignments precisely when all three of its variables are among the $5-d$ coordinates on which the assignments agree. Hence

$$ |F_x\cup F_y|

20-\binom{5-d}{3}. $$

The probability that a random set of $m$ clauses avoids both $F_x$ and $F_y$ is therefore

$$ \frac{\binom{80-|F_x\cup F_y|}{m}}{\binom{80}{m}}

\frac{\binom{60+\binom{5-d}{3}}{m}}{\binom{80}{m}} . $$

There are $32\binom5d$ ordered pairs $(x,y)$ at distance $d$. Consequently,

$$ \mathop{\rm E}(T_m^2)

\frac{32}{\binom{80}{m}} \sum_{d=0}^{5} \binom5d \binom{60+\binom{5-d}{3}}{m}. $$

Also,

$$ \mathop{\rm E}(T_m)

32\frac{\binom{70}{m}}{\binom{80}{m}}, $$

because a fixed assignment survives exactly when none of its ten falsifying clauses is chosen.

Substituting these expressions into

$$ \operatorname{Var}(T_m)

\mathop{\rm E}(T_m^2)-\mathop{\rm E}(T_m)^2 $$

gives a finite expression depending only on $m$. Evaluating this expression for

$$ 2\leq m\leq70 $$

shows that it is strictly positive in every case. Thus $T_m$ assumes at least two different values for every such $m$, and its distribution is not constant.

Therefore the complete list of values of $m$ for which $T_m$ is constant is

$$ \boxed{m=0,;1,;\text{and};71\leq m\leq80.} $$