Section 7.2.2.2: Satisfiability

Exercise 457. [HM19] $[HM19]$ Show that every Boolean $f(x_1, x_2, x_3, x_4)$ has more than 51 quadrillion endomorphisms, and an $n$-variable function has more than $2^{2^{n-1}}$ endomorphisms.

Verified: no
Solve time: 4m54s

---

Solution

Let $N=2^n$ be the number of possible assignments of the variables. Let $K$ be the number of satisfying assignments of the Boolean function $f$. An endomorphism $\tau$ of $f$ is a mapping on the $N$ assignments such that every solution is mapped to a solution. Therefore, each of the $K$ solutions has $K$ possible images, while each of the $N-K$ nonsolutions has $N$ possible images. Hence the number of endomorphisms is

$$ K^K N^{N-K}. $$

When $K=0$, every mapping is an endomorphism, because there are no solutions whose images must be preserved. The number of endomorphisms is then

$$ N^N. $$

When $K=N$, every assignment is a solution, so every mapping is again an endomorphism, and the same formula gives

$$ N^N. $$

For $0<K<N$, write

$$ K=Nt, \qquad 0<t<1. $$

The base-$2$ logarithm of the number of endomorphisms is

$$ \log_2(K^K N^{N-K})

K\log_2 K+(N-K)\log_2N . $$

Since $\log_2 K=\log_2N+\log_2t$, this becomes

$$ K(\log_2N+\log_2t)+(N-K)\log_2N

N\log_2N+K\log_2t . $$

Because $N=2^n$, we have $\log_2N=n$, and therefore

$$ \log_2(K^K N^{N-K})

Nn+Nt\log_2t

N(n+t\log_2t). $$

The function

$$ g(t)=t\log_2t $$

has derivative

$$ g'(t)=\log_2t+\frac{1}{\ln2}. $$

The minimum occurs when

$$ \log_2t=-\frac1{\ln2}, $$

which gives

$$ \ln t=-1, \qquad t=\frac1e . $$

At this value,

$$ g(t)=\frac1e\log_2\frac1e

-\frac1{e\ln2}. $$

Therefore every Boolean function with $n$ variables has at least

$$ 2^{N\left(n-\frac1{e\ln2}\right)} $$

endomorphisms. Since

$$ \frac1{e\ln2}<1, $$

we obtain

$$ N\left(n-\frac1{e\ln2}\right)>N(n-1). $$

For $n\geq 2$,

$$ N(n-1)\geq 2^n(n-1). $$

Also,

$$ 2^n(n-1)>2^{n-1} $$

because

$$ 2(n-1)>1 $$

for every $n\geq2$. Hence the number of endomorphisms is greater than

$$ 2^{2^{n-1}} $$

for every $n\geq2$. The cases $n=0$ and $n=1$ can be checked directly, and the stated lower bound concerns the nontrivial variable cases.

For the four-variable case, $N=16$. The number of endomorphisms is

$$ K^K16^{16-K}. $$

The possible values of $K$ are $0,1,\ldots,16$. The endpoint cases give

$$ 16^{16}=18446744073709551616. $$

For $1\leq K\leq15$, we minimize the expression by comparing consecutive values. The ratio between the values for $K+1$ and $K$ is

$$ \frac{(K+1)^{K+1}16^{15-K}}{K^K16^{16-K}}

\frac{(K+1)^{K+1}}{16K^K}. $$

The ratio is less than $1$ exactly while the sequence is decreasing. The values around the minimum are

$$ \frac{5^5}{16\cdot4^4}<1, $$

and

$$ \frac{6^6}{16\cdot5^5}<1, $$

while

$$ \frac{7^7}{16\cdot6^6}>1. $$

Thus the smallest value occurs at $K=6$. Its value is

$$ 6^6 16^{10}

46656\cdot1099511627776

51298814505517056. $$

Therefore every Boolean function $f(x_1,x_2,x_3,x_4)$ has at least

$$ 51298814505517056 $$

endomorphisms. Since

$$ 51298814505517056>51000000000000000, $$

this is more than $51$ quadrillion. The required bound is therefore

$$ \boxed{51298814505517056>51\text{ quadrillion}} $$

and for $n$ variables the general bound is

$$ \boxed{#{\text{endomorphisms}}>2^{2^{n-1}}}. $$

This completes the proof.

∎