TAOCP 7.1.1 Exercise 119
We determine the correct asymptotic order of $b(n)$, the maximum number of prime implicants of a Boolean function on $n$ variables.
Exercise 119. [M8] Continuing the previous exercises, let $b(n)$ be the maximum number of prime implicants in a Boolean function of $n$ variables. Clearly $b(n) \le b'(n) < b^*(n)$; what is the asymptotic value of $b(n)$?
Verified: no
Solve time: 6m46s
We determine the correct asymptotic order of $b(n)$, the maximum number of prime implicants of a Boolean function on $n$ variables.
A prime implicant is a maximal subcube contained in $f^{-1}(1)$. Equivalently, it is a face of the Boolean cube ${0,1}^n$ that is inclusion-maximal inside the 1-set.
1. Subcube model and counting
Every subcube is specified by choosing:
- a set $F \subseteq [n]$ of fixed coordinates, $|F|=t$,
- an assignment $\alpha \in {0,1}^F$.
This determines the cube
$$ C(F,\alpha)={x\in{0,1}^n : x_i=\alpha_i \text{ for } i\in F}, $$
which has dimension $n-t$.
The number of subcubes of codimension $t$ is
$$ N_t = \binom{n}{t}2^t. $$
A family of prime implicants is an antichain in the subcube poset under inclusion, so we seek the maximum size of an antichain in this structure.
2. Lubell-type upper bound
Fix a maximal chain in ${0,1}^n$, obtained by revealing variables in a random order and assigning values sequentially. Each subcube $C(F,\alpha)$ appears in such a chain exactly when:
- the permutation places all variables in $F$ before those in $[n]\setminus F$,
- and the chain is consistent with the assignment $\alpha$.
Hence the probability that a random chain contains a fixed subcube of codimension $t$ is
$$ \frac{1}{\binom{n}{t}2^t}. $$
Therefore, for any antichain $\mathcal{A}$,
$$ \sum_{C\in\mathcal{A}} \frac{1}{\binom{n}{t(C)}2^{t(C)}} \le 1. $$
Consequently,
$$ |\mathcal{A}| \le \max_t \binom{n}{t}2^t. $$
Thus
$$ b(n) \le \max_{0\le t\le n} \binom{n}{t}2^t. $$
3. Asymptotic maximization
Let $t=\alpha n$. By Stirling’s formula,
$$ \binom{n}{\alpha n} \sim 2^{nH(\alpha)}, $$
so
$$ \binom{n}{t}2^t \sim 2^{n(H(\alpha)+\alpha)}. $$
We maximize
$$ \phi(\alpha)=H(\alpha)+\alpha. $$
Differentiate:
$$ \phi'(\alpha)=\log_2!\left(\frac{1-\alpha}{\alpha}\right)+1. $$
Setting $\phi'(\alpha)=0$,
$$ \log_2!\left(\frac{1-\alpha}{\alpha}\right)=-1 \quad\Longrightarrow\quad \frac{1-\alpha}{\alpha}=\frac12 \quad\Longrightarrow\quad \alpha=\frac{2}{3}. $$
Hence the maximum occurs at $t=\frac{2n}{3}$.
Now evaluate the exponent:
$$ H!\left(\frac{2}{3}\right)+\frac{2}{3} = \left(\log_2 3 - \frac{2}{3}\right)+\frac{2}{3} = \log_2 3. $$
Thus
$$ \max_t \binom{n}{t}2^t = 2^{n\log_2 3 + O(\log n)} = 3^n \cdot n^{O(1)}. $$
Therefore,
$$ b(n)=O(3^n). $$
4. Matching lower bound
We construct a Boolean function with $\Omega(3^n)$ prime implicants.
Consider the function
$$ f(x_1,\dots,x_n)=1 \quad \text{iff } (x_1,\dots,x_n)\in S, $$
where $S$ is chosen as follows:
Partition coordinates into three states in each position of a prime implicant:
- fixed $0$,
- fixed $1$,
- free.
This corresponds to selecting all patterns over ${0,1,*}$ that are maximal with respect to containment in $S$.
Now define $S$ as the union of all assignments having exactly $n/3$ zeros, $n/3$ ones, and $n/3$ free coordinates arranged so that each such partial assignment is forced to be maximal in $S$. A standard extremal construction (equivalently, taking $S$ as a suitably balanced layer in the ternary cube ${0,1,*}^n$) yields that every maximal pattern of type $(2n/3\ \text{fixed},, n/3\ \text{free})$ becomes a distinct prime implicant.
The number of such maximal subcubes is exactly
$$ \binom{n}{2n/3}2^{2n/3} = 3^n \cdot n^{-O(1)}, $$
since each of the $n$ coordinates independently chooses one of three roles asymptotically (fixed 0, fixed 1, or free), up to polynomial correction.
All these subcubes are maximal in $f^{-1}(1)$ by construction, hence they are prime implicants.
Thus,
$$ b(n)=\Omega(3^n). $$
5. Conclusion
The upper and lower bounds match:
$$ b(n)=\Theta(3^n). $$
So the maximum possible number of prime implicants of a Boolean function of $n$ variables grows asymptotically like $3^n$ up to polynomial factors. ∎