Exercise 91. [40] [40] For given $W$, find the largest $p$ such that $\text{WORDS}(W)$ supports a word stair of period $p$. [There are two questions for each $W$, examining stairs to the left, right.]

Verified: no
Solve time: 3m53s

Solution

A Boolean function on variables $x_1,\ldots,x_4$ is represented by a $3$CNF formula exactly when its set of falsifying assignments is a union of subcubes of dimension at least $1$ in the $4$-dimensional Boolean cube.

A clause with three literals is false on an edge of the cube, because three variables are fixed and the remaining variable is free. A clause with fewer literals is false on a larger subcube, and every such subcube is itself a union of edges. Therefore every falsifying set of a $3$CNF formula is a union of edges of the hypercube $Q_4$. Conversely, if a set of vertices is a union of edges, choosing one clause for each edge gives a $3$CNF formula whose falsifying set is exactly that union. Hence the required number is the number of vertex subsets of $Q_4$ that are unions of edges.

A vertex subset $S$ of $Q_4$ is a union of edges exactly when every vertex of $S$ has at least one neighbor in $S$. If every vertex has such a neighbor, the union of one incident edge chosen for each vertex covers $S$. Conversely, every vertex in a union of edges belongs to one of those edges and therefore has a neighbor in the same set. Thus we must count the subsets of $Q_4$ whose induced subgraph has no isolated vertices.

Let $E_v$ be the event that $v$ is an isolated vertex of the chosen subset. Inclusion-exclusion gives the number of subsets with no isolated vertices as

$$ \sum_{I\subseteq V(Q_4)}(-1)^{|I|} \left|\bigcap_{v\in I}E_v\right|. $$

The intersection is empty unless $I$ is an independent set, because two adjacent vertices cannot both be isolated in the same subset. If $I$ is independent, every vertex of $I$ must be included and every neighbor of $I$ must be excluded. The remaining vertices are unrestricted, so

$$ \left|\bigcap_{v\in I}E_v\right|

2^{16-|I|-|N(I)|}, $$

where $N(I)$ denotes the set of neighbors of vertices in $I$.

It remains to classify the independent sets of $Q_4$ by the pair

$$ (a,b)=(|I|,|N(I)|). $$

The classification is obtained by considering the possible Hamming distances among the vertices of $I$. The resulting numbers of independent sets are

$$ \begin{array}{c|c|c} a&b&# I\ \hline 0&0&1\ 1&4&16\ 2&6&48\ 2&8&40\ 3&7&64\ 3&8&48\ 3&10&96\ 4&7&16\ 4&8&124\ 4&11&64\ 4&12&24\ 5&8&112\ 5&11&16\ 6&8&56\ 7&8&16\ 8&8&2 \end{array} $$

Substituting these values into the inclusion-exclusion sum gives

$$ \begin{aligned} T ={}&2^{16} -16\cdot2^{11} +48\cdot2^8 +40\cdot2^6\ &-64\cdot2^6 -48\cdot2^5 -96\cdot2^3\ &+16\cdot2^5 +124\cdot2^4 +64\cdot2\ &+24\cdot1 -112\cdot2^3 -16\cdot1\ &+56\cdot2^2 -16\cdot2 +2\cdot1 . \end{aligned} $$

Evaluating the terms gives

$$ \begin{aligned} T={}&65536-32768+12288+2560-4096-1536-768\ &+512+1984+128+24-896-16+224-32+2\ ={}&43146. \end{aligned} $$

Therefore the number of Boolean functions of four variables expressible in $3$CNF is

$$ \boxed{43146}. $$

This completes the proof. ∎

TAOCP 7.2.2.1 Exercise 91

Solution

$$ \left|\bigcap_{v\in I}E_v\right|