TAOCP 7.2.2.2 Exercise 45

Exercise 45. [20] $[20]$ Specify clauses that constrain $(z_1 \ldots z_5)_2$ to be a perfect square.

Verified: yes
Solve time: 14m08s

Solution

Let

$$ N=(z_1z_2z_3z_4z_5)_2, $$

where $z_1$ is the most significant bit and $z_5$ is the least significant bit. The possible values of $N$ are $0\leq N<32$, and the perfect squares in this interval are

$$ 0,\ 1,\ 4,\ 9,\ 16,\ 25. $$

Their binary representations are

$$ 00000,\quad 00001,\quad 00100,\quad 01001,\quad 10000,\quad 11001. $$

A CNF constraint can be obtained by excluding exactly the other binary assignments. The following clauses suffice:

$$ \bar z_4, $$

$$ \bar z_1\vee\bar z_3, $$

$$ \bar z_2\vee\bar z_3, $$

$$ \bar z_2\vee z_5, $$

$$ \bar z_3\vee\bar z_5, $$

and

$$ \bar z_1\vee z_2\vee\bar z_5. $$

Thus define

$$ \begin{aligned} F={}& (\bar z_4) \wedge (\bar z_1\vee\bar z_3) \wedge (\bar z_2\vee\bar z_3) \ &\wedge (\bar z_2\vee z_5) \wedge (\bar z_3\vee\bar z_5) \wedge (\bar z_1\vee z_2\vee\bar z_5). \end{aligned} $$

Every perfect square satisfies these clauses. The first clause holds because every square representation above has $z_4=0$. The second clause forbids only $z_1=z_3=1$, the third forbids only $z_2=z_3=1$, the fourth forbids only $z_2=1,z_5=0$, the fifth forbids only $z_3=z_5=1$, and the sixth forbids only $z_1=1,z_2=0,z_5=1$. None of the six listed square representations has any of these forbidden patterns.

It remains to prove that no other assignments satisfy $F$. Suppose that $F$ is satisfied. The unit clause $\bar z_4$ gives

$$ z_4=0. $$

First consider the case $z_3=1$. The second clause gives

$$ z_1=0, $$

and the third clause gives

$$ z_2=0. $$

The fifth clause gives

$$ z_5=0. $$

Therefore the only satisfying assignment in this case is

$$ 00100, $$

which represents $4$.

Now consider the case $z_3=0$. The fourth clause gives

$$ z_2=0\quad\text{or}\quad z_5=1. $$

If $z_2=1$, then the fourth clause requires

$$ z_5=1. $$

The sixth clause is then automatically satisfied because its second literal $z_2$ is true. Hence both values of $z_1$ are possible, giving the assignments

$$ 01001 $$

and

$$ 11001. $$

These represent $9$ and $25$, respectively.

If $z_2=0$, then the sixth clause becomes

$$ \bar z_1\vee\bar z_5. $$

Therefore the combination $z_1=z_5=1$ is forbidden. The remaining possibilities are

$$ 00000,\quad 00001,\quad 10000. $$

They represent $0$, $1$, and $16$, respectively.

The satisfying assignments of $F$ are therefore exactly

$$ 00000,\quad 00001,\quad 00100,\quad 01001,\quad 10000,\quad 11001, $$

which are precisely the binary representations of the perfect squares less than $32$.

Hence the required clauses are

$$ \boxed{ (\bar z_4)\wedge (\bar z_1\vee\bar z_3)\wedge (\bar z_2\vee\bar z_3)\wedge (\bar z_2\vee z_5)\wedge (\bar z_3\vee\bar z_5)\wedge (\bar z_1\vee z_2\vee\bar z_5) }. $$