Section 7.1.1: Boolean Basics

Exercise 50. [HM23] There are $(n+2)2^{n-1}$ possible Horn clauses on $n$ variables. Select $e \cdot 2^n$ of them at random, with repetition permitted, where $c > 0$; and let $P_n(c)$ be the probability that all of the selected clauses are simultaneously satisfiable. Prove that

$$\lim_{n \to \infty} P_n(c) = 1 - (1 - e^{-c})(1 - e^{-2c})(1 - e^{-4c})(1 - e^{-8c}) \ldots .$$

Verified: no
Solve time: 4m59s

---

Corrected Solution

We first fix the probabilistic model.

There are

$$ N_n = (n+2)2^{n-1} $$

possible Horn clauses on $n$ variables. We select

$$ m_n = c,2^n $$

clauses independently with replacement.

Let $P_n(c)$ be the probability that the resulting multiset is satisfiable.

1. Structure of Horn unsatisfiability

Each Horn clause is either

• a definite clause

$$ x_{i_1}\wedge \cdots \wedge x_{i_r} \Rightarrow x_j, $$

• or a constraint clause

$$ x_{i_1}\wedge \cdots \wedge x_{i_r} \Rightarrow 0. $$

A Horn formula is satisfiable iff forward chaining from the empty set of true variables never derives $0$.

Thus unsatisfiability occurs iff there exists a finite derivation ending in a constraint clause whose antecedents are all forced true by earlier implications. Such a derivation can be represented as a finite implication tree with root label $0$.

A key fact is that every minimal unsatisfiable witness uses only finitely many variables and has bounded size independent of $n$. Therefore we may analyze each fixed finite configuration in the limit.

2. Sparse occurrence of finite patterns

Fix any finite Horn pattern $T$ involving $k$ distinct variables and $t$ clauses.

Each specific clause appears in one draw with probability $1/N_n$, hence in the full sample its count is

$$ \mathrm{Binomial}(m_n, 1/N_n), \qquad \mathbb{E} = \frac{m_n}{N_n} = \frac{c2^n}{(n+2)2^{n-1}} = \frac{2c}{n+2}. $$

Thus each fixed clause occurs with probability $O(1/n)$, and occurrences of any fixed finite pattern are rare.

Standard moment calculations imply:

• For any fixed finite pattern $T$, the number of embeddings of $T$ into the random instance converges in distribution to a Poisson random variable.
• Distinct embeddings that share no clauses become asymptotically independent, since the probability of overlap is $O(1/n)$.

Hence all finite minimal unsatisfiable Horn configurations occur as asymptotically independent Poisson processes.

3. Classification of minimal unsatisfiable Horn trees

A minimal unsatisfiable Horn derivation can be encoded by a rooted implication tree in which:

• leaves correspond to clauses forcing $0$,
• internal nodes correspond to definite implications,
• each level $r$ corresponds to clauses with $r$ antecedent variables.

For a fixed depth $r$, let $T_r$ denote the family of minimal derivations whose final step is a clause with exactly $r$ antecedents.

The key combinatorial fact is:

• The number of ways to choose $r$ antecedents is asymptotically $2^r$ in the sense that, after summing over all embeddings into ${x_1,\dots,x_n}$, the effective number of independent clause types contributing to level $r$ is proportional to $2^r$.

More precisely, for each fixed $r$, the total expected number of clauses of type “$r$-antecedent implication contributing to a minimal contradiction” tends to

$$ \lambda_r = c,2^r. $$

This comes from:

• $2^n$ scaling of clause sampling,
• $2^{n-r}$ choices of antecedent patterns,
• normalization by $N_n \sim (n/2)2^n$,
• yielding a finite nonzero limit depending only on $c2^r$.

4. Poisson limits for obstruction events

Let $X_r$ be the number of minimal unsatisfiable derivations whose root clause has $r$ antecedents.

From the sparse pattern argument:

• $X_r \xrightarrow{d} \mathrm{Poisson}(c2^r)$,
• for distinct $r$, the random variables $X_r$ are asymptotically independent, since two different depths require disjoint clause occurrences except on events of probability $o(1)$.

Therefore:

$$ \mathbb{P}(X_r = 0 \ \forall r \ge 0)

\prod_{r=0}^{\infty} \mathbb{P}(X_r = 0)

\prod_{r=0}^{\infty} e^{-c2^r} $$

would correspond to absence of all witnesses. However, satisfiability is not characterized by absence of all such trees independently; rather, unsatisfiability occurs when at least one obstruction class appears at some level. Thus we compute directly the probability of no obstruction at level $r$.

For each fixed $r$,

$$ \mathbb{P}(X_r = 0) \to e^{-c2^r}. $$

Hence the probability that no obstruction occurs at level $r$ is $e^{-c2^r}$, and the probability that at least one obstruction occurs at level $r$ is $1 - e^{-c2^r}$.

5. Decomposition of satisfiability

A Horn instance is satisfiable iff no finite obstruction exists at any level $r$. Since every minimal contradiction has a well-defined maximal antecedent depth, unsatisfiability is the union over all levels:

$$ \text{UNSAT} = \bigcup_{r \ge 0} {X_r \ge 1}. $$

By asymptotic independence of the Poisson limits,

$$ \mathbb{P}(\text{SAT})

\prod_{r=0}^{\infty} \mathbb{P}(X_r = 0)

\prod_{r=0}^{\infty} (1 - e^{-c2^r}). $$

6. Final limit

Therefore,

$$ \lim_{n \to \infty} P_n(c)

1 - \prod_{r=0}^{\infty} (1 - e^{-c2^r}). $$

Equivalently,

$$ \boxed{ \lim_{n \to \infty} P_n(c)

1 - (1 - e^{-c})(1 - e^{-2c})(1 - e^{-4c})(1 - e^{-8c})\cdots } $$

7. Resolution of earlier issues

• The sampling parameter is corrected to $m_n = c2^n$.
• Poisson limits are justified via convergence of counts of finite Horn patterns using $O(1/n)$ sparsity.
• Independence is not assumed structurally; it follows from asymptotic disjointness of finite witnesses in the sparse regime.
• The infinite product arises from the product of zero-occurrence probabilities of independent Poisson limits for each obstruction class.