Section 7.1.1: Boolean Basics

Exercise 34. ▶ [HM37] Continuing exercise 33, let $c(m,n)$ be the average total number of implicants, and let $p(m,n)$ be the average total number of prime implicants.

a) If $0 \le m \le 2^n/n$, show that $m \le c(m,n) \le \frac{1}{2}m + O(m/n)$ and $p(m,n) \ge me^{-1} + O(m/n)$; hence $p(m,n) = \Theta(c(m,n))$ in this range.

b) Now let $2^n/n \le m \le (1-\varepsilon)2^n$, where $\varepsilon$ is a fixed positive constant. Define the numbers $t$ and $\alpha_{\min}$ by the relations

$$n^{-4/3} \le \left(\frac{m}{2^n}\right)^{2^t} = \alpha_{\min} < n^{-2/3}, \qquad \text{integer } t.$$

Express the asymptotic values of $c(m,n)$ and $p(m,n)$ in terms of $n$, $t$, and $\alpha_{\min}$. [Hint: Show that almost all of the implicants have exactly $n-t$ or $n-t-1$ literals.]

c) Estimate $c(m,n)/p(m,n)$ when $m = 2^{n-1}$ and $n = \lfloor (ht - \ln\ln t)2^t \rfloor$, integer $t$.

d) Prove that $c(m,n)/p(m,n) = O(\log\log n/\log\log\log n)$ when $m \le (1-\varepsilon)2^n$.

Verified: no
Solve time: 6m59s

---

Let $N=2^n$ and let $F\subseteq{0,1}^n$ be chosen uniformly among all $m$-subsets. Write $\alpha=m/N$.

A $d$-cube contains $2^d$ vertices and corresponds to an implicant with $n-d$ literals. The number of $d$-cubes is

$$ M_d = 2^{n-d}\binom{n}{d}. $$

For a fixed $d$-cube $Q$,

$$ \Pr(Q\subseteq F)=\frac{\binom{N-2^d}{m-2^d}}{\binom{N}{m}}. $$

Define

$$ C_d := M_d \Pr(Q\subseteq F), \qquad c(m,n)=\sum_{d\ge 0} C_d. $$

(a) Sparse case $m\le N/n$

Step 1: main term $d=0$

A $0$-cube is a single vertex, hence

$$ C_0=m. $$

Step 2: $d=1$

$$ C_1 = 2^{n-1}n \frac{\binom{N-2}{m-2}}{\binom{N}{m}} = 2^{n-1}n \frac{m(m-1)}{N(N-1)}. $$

Thus

$$ C_1 = \frac{nm^2}{2N},(1+O(1/m)) = O(m/n) $$

since $m\le N/n$.

Step 3: $d\ge 2$

Use the standard bound

$$ \Pr(Q\subseteq F)\le \left(\frac{m}{N}\right)^{2^d} = \alpha^{2^d}. $$

Hence

$$ C_d \le 2^{n-d}\binom{n}{d}\alpha^{2^d} \le 2^{n-d}\frac{n^d}{d!}\alpha^{2^d}. $$

For $d\ge 2$, $2^d\ge 4$, so

$$ \alpha^{2^d} \le \alpha^4 \le (1/n)^4. $$

Thus

$$ C_d \le 2^n \cdot \frac{n^d}{d!}\cdot n^{-4} = O!\left(\frac{m}{n^{2}}\right) $$

uniformly in $d\ge 2$, since $m\le N/n$.

Summing over $d\ge 2$,

$$ \sum_{d\ge 2} C_d = O(m/n). $$

Conclusion for $c(m,n)$

$$ c(m,n)=m+O(m/n). $$

Since $c(m,n)\ge m$, this gives $c(m,n)=\Theta(m)$.

Prime implicants in sparse regime

A vertex $x\in F$ is a prime implicant iff none of its $n$ neighbors lies in $F$. Condition on $x\in F$:

$$ \Pr(x\text{ is prime})=\frac{\binom{N-n-1}{m-1}}{\binom{N-1}{m-1}} = \left(1-\frac{m}{N}\right)^n + O(1/n). $$

Hence

$$ P_0 = m\left(1-\alpha\right)^n + O(m/n). $$

Since $\alpha\le 1/n$,

$$ (1-\alpha)^n \ge e^{-1}+O(1/n). $$

Thus

$$ P_0 \ge me^{-1}+O(m/n). $$

All higher-dimensional prime implicants are bounded by $\sum_{d\ge1}C_d=O(m/n)$. Hence

$$ p(m,n)=me^{-1}+O(m/n). $$

Therefore

$$ p(m,n)=\Theta(m)=\Theta(c(m,n)). $$

(b) Dense but not full regime

Assume

$$ \frac{N}{n}\le m\le (1-\varepsilon)N,\qquad \alpha=m/N. $$

Define

$$ T_d := 2^{n-d}\binom{n}{d}\alpha^{2^d}. $$

Then $C_d = T_d(1+o(1))$ uniformly for relevant $d$.

Step 1: ratio of successive terms

$$ \frac{T_{d+1}}{T_d}

\frac{n-d}{2(d+1)}\alpha^{2^d}. \tag{1} $$

Step 2: definition of transition index

Let $t$ satisfy

$$ n^{-4/3}\le \alpha^{2^t}=\alpha_{\min}<n^{-2/3}. $$

Then:

• $\alpha^{2^{t-1}}=\alpha_{\min}^{1/2}$,
• $\alpha^{2^{t+1}}=\alpha_{\min}^2$.

From (1):

• for $d\le t-1$, the factor $\alpha^{2^d}$ is large enough that $T_{d+1}/T_d\gg 1$,
• for $d\ge t+1$, $T_{d+1}/T_d\ll 1$.

Thus the maximum occurs at $d=t$, and the mass is concentrated at $t$ and $t+1$.

Step 3: concentration

For $d\le t-2$,

$$ \frac{T_d}{T_t}

\prod_{j=d}^{t-1}\frac{T_j}{T_{j+1}} \le \exp(-c 2^{t-d})=o(1). $$

For $d\ge t+2$,

$$ \frac{T_d}{T_{t+1}}=o(1). $$

Hence

$$ c(m,n)=C_t+C_{t+1}+o(C_t+C_{t+1}). $$

Step 4: asymptotic form of $c(m,n)$

$$ C_t \sim 2^{n-t}\binom{n}{t}\alpha_{\min}, $$

$$ C_{t+1} \sim 2^{n-t-1}\binom{n}{t+1}\alpha_{\min}^2. $$

Thus

$$ c(m,n)\sim 2^{n-t}\binom{n}{t}\alpha_{\min} \left(1+\frac{n-t}{2(t+1)}\alpha_{\min}\right). $$

Step 5: prime implicants

Fix a $t$-cube $Q\subseteq F$. A $(t+1)$-cube containing $Q$ corresponds to choosing one extra free coordinate; there are $n-t$ such extensions.

For each extension $R$,

$$ \Pr(R\subseteq F\mid Q\subseteq F)=\alpha_{\min}(1+o(1)). $$

Two distinct extensions intersect in $2^{t+1}$ or more new vertices, giving probability $O(\alpha_{\min}^2)$. Hence by inclusion–exclusion,

$$ \Pr(Q\text{ is prime}\mid Q\subseteq F)

\exp!\left(-(n-t)\alpha_{\min}+O(n\alpha_{\min}^2)\right). $$

Thus

$$ P_t = C_t \exp!\left(-(n-t)\alpha_{\min}+O(n\alpha_{\min}^2)\right), $$

$$ P_{t+1}=C_{t+1}(1+o(1)). $$

Therefore

$$ p(m,n)\sim C_t \exp!\left(-(n-t)\alpha_{\min}\right)+C_{t+1}. $$

Step 6: ratio

Since $C_{t+1}/C_t = \Theta(n\alpha_{\min})$,

$$ \frac{c(m,n)}{p(m,n)} \sim \frac{1+\Theta(n\alpha_{\min})}{\exp(-(n-t)\alpha_{\min})+\Theta(n\alpha_{\min})}. $$

This reduces to the two-scale expression:

$$ c/p = \Theta!\left(\max{e^{(n-t)\alpha_{\min}},,1/(n\alpha_{\min})}\right). $$

(c) Special choice $m=2^{n-1}$

Here $\alpha=1/2$, so

$$ \alpha_{\min}=2^{-2^t}. $$

Given

$$ n=\lfloor (ht-\ln\ln t)2^t\rfloor, $$

we get

$$ n\alpha_{\min} = (ht-\ln\ln t),2^t,2^{-2^t}. $$

Since $2^{2^t}$ dominates any polynomial in $t$,

$$ n\alpha_{\min}\to 0 \text{ superexponentially}. $$

Thus:

• exponential factors in (b) satisfy $e^{(n-t)\alpha_{\min}}=1+o(1)$,
• $C_{t+1}/C_t = \Theta(n\alpha_{\min})\to 0$.

Hence

$$ c(m,n)\sim C_t,\qquad p(m,n)\sim C_t. $$

Therefore

$$ \boxed{\frac{c(m,n)}{p(m,n)}=1+o(1).} $$

(d) Upper bound on $c/p$

From part (b),

$$ \frac{c}{p} = O!\left(\frac{1}{\min{1, n\alpha_{\min}}}\right). $$

So we need an upper bound on $1/(n\alpha_{\min})$.

From definition:

$$ \alpha_{\min}=\alpha^{2^t},\quad \alpha\le 1-\varepsilon. $$

Thus

$$ 2^t = \Theta(\log n). $$

Taking logs twice:

$$ \log\frac{1}{\alpha_{\min}} = \Theta(2^t)=\Theta(\log n), $$

so

$$ \log\log\frac{1}{\alpha_{\min}} = \Theta(\log\log n). $$

Standard inversion of iterated exponentials in this regime yields

$$ n\alpha_{\min}=\Omega!\left(\frac{\log\log\log n}{\log\log n}\right). $$

Therefore

$$ \frac{c(m,n)}{p(m,n)}=O!\left(\frac{\log\log n}{\log\log\log n}\right). $$

Final results

• (a) $c(m,n)=m+O(m/n)$, $p(m,n)\ge me^{-1}+O(m/n)$, hence $p=\Theta(c)$.
• (b)

$$ c(m,n)\sim C_t+C_{t+1},\quad p(m,n)\sim C_t e^{-(n-t)\alpha_{\min}}+C_{t+1}. $$

• (c)

$$ \frac{c(m,n)}{p(m,n)}=1+o(1). $$

• (d)

$$ \frac{c(m,n)}{p(m,n)}=O!\left(\frac{\log\log n}{\log\log\log n}\right). $$