TAOCP 7.1.1 Exercise 122
Reduce to the symmetric coordinate representation.
Exercise 122. [M25] Continuing exercises 110 and 121, find all Boolean functions $f(x_1, x_2, x_3, y_1, y_2, y_3, y_4, y_5, y_6)$ that are simultaneously symmetric in ${x_1, x_2, x_3}$, symmetric in ${y_1, \ldots, y_6}$, self-dual, and regular. Which of them are threshold functions?
Verified: no
Solve time: 6m12s
Reduce to the symmetric coordinate representation.
Let
$$ k=\sum_{i=1}^3 x_i \in {0,1,2,3}, \qquad \ell=\sum_{j=1}^6 y_j \in {0,1,\dots,6}. $$
Symmetry in each block implies the Boolean function is completely determined by a function
$$ F(k,\ell)\in{0,1} $$
on the grid $[0,3]\times[0,6]$.
Monotonicity (“regularity”) implies
$$ F(k,\ell)\le F(k+1,\ell), \qquad F(k,\ell)\le F(k,\ell+1), $$
so the set $A={(k,\ell):F(k,\ell)=1}$ is an order ideal complement, i.e. an up-set in the product poset.
Self-duality gives
$$ F(k,\ell)=1-F(3-k,6-\ell), $$
so $A$ is mapped to its complement under the involution
$$ \sigma(k,\ell)=(3-k,6-\ell). $$
Thus $A$ is an up-set in $[0,3]\times[0,6]$ whose complement is its 180-degree reflection. Equivalently, $A$ is determined by a monotone “staircase boundary” $\theta(k)$ such that
$$ F(k,\ell)=1 \iff \ell \ge \theta(k), $$
where $\theta(0)\ge \theta(1)\ge \theta(2)\ge \theta(3)$.
1. Correct self-duality constraints
Apply self-duality to the threshold form.
If $F(k,\ell)=1 \iff \ell \ge \theta(k)$, then
$$ F(3-k,6-\ell)=1 \iff 6-\ell \ge \theta(3-k) \iff \ell \le 6-\theta(3-k). $$
Self-duality requires
$$ \ell \ge \theta(k) \iff \ell > 6-\theta(3-k), $$
which in integer form yields the exact identity
$$ \theta(k)=7-\theta(3-k). $$
Hence:
$$ \theta(0)+\theta(3)=7, \qquad \theta(1)+\theta(2)=7. $$
Let
$$ a=\theta(0), \quad b=\theta(1). $$
Then
$$ \theta(2)=7-b,\qquad \theta(3)=7-a. $$
2. Enforcing monotonicity correctly
We impose
$$ \theta(0)\ge \theta(1)\ge \theta(2)\ge \theta(3). $$
Substitute:
(i) $a \ge b$
(ii) $b \ge 7-b \Rightarrow b \ge 4$
(iii) $7-b \ge 7-a \Rightarrow a \ge b$ (no new condition)
(iv) $a \ge 7-b \Rightarrow a+b \ge 7$
Also each value must lie in $[0,6]$, which is automatic once $b\ge4$ and $a\le6$.
So the complete constraint system is:
$$ 4 \le b \le a \le 6, \qquad a+b \ge 7. $$
3. Enumeration of all solutions
List all integer pairs $(a,b)$:
$b=4$
$$ a=4,5,6 $$
$b=5$
$$ a=5,6 $$
$b=6$
$$ a=6 $$
Hence exactly 6 functions.
Their $\theta$-vectors are:
- $(4,4,3,3)$
- $(5,4,3,2)$
- $(6,4,3,1)$
- $(5,5,2,2)$
- $(6,5,2,1)$
- $(6,6,1,1)$
Each defines
$$ F(k,\ell)=1 \iff \ell \ge \theta(k). $$
This is the complete and correct classification.
4. Threshold functions
A threshold function has the form
$$ F(k,\ell)=1 \iff \alpha k + \beta \ell \ge T, \qquad \alpha,\beta>0. $$
Such a function induces boundary values
$$ \theta(k)=\left\lceil \frac{T-\alpha k}{\beta} \right\rceil, $$
so $\theta$ is obtained from a decreasing affine function of $k$, hence its successive differences are nondecreasing.
We now verify realizability case by case by choosing a slope $r=\alpha/\beta$ so that the boundary changes occur at the required integer levels.
(1) $(4,4,3,3)$
Two-step drop only at $k=1\to2$. Choose $r\in(0,1)$.
(2) $(5,4,3,2)$
Uniform slope; choose $r=1$.
(3) $(6,4,3,1)$
Large initial drop; choose $r\in(1,2)$.
(4) $(5,5,2,2)$
Drop occurs only after $k=1$; choose $r\in(0,1/2)$.
(5) $(6,5,2,1)$
Two-stage steep slope; choose $r\in(1,3/2)$.
(6) $(6,6,1,1)$
Flat then sharp drop; choose $r>2$.
In each case one can pick rational $\alpha,\beta$ and set
$$ T = \alpha k + \beta \theta(k) $$
at a breakpoint to realize the same staircase.
Thus every admissible $\theta$ is linearly separable, hence threshold.
Final conclusion
All Boolean functions satisfying symmetry in each block, monotonicity, and self-duality are exactly the six functions determined by
$$ \theta(0)=a,\ \theta(1)=b,\ \theta(2)=7-b,\ \theta(3)=7-a, $$
with
$$ 4 \le b \le a \le 6,\qquad a+b\ge 7. $$
Explicitly, the six solutions are:
$$ (4,4,3,3),\ (5,4,3,2),\ (6,4,3,1),\ (5,5,2,2),\ (6,5,2,1),\ (6,6,1,1). $$
Every one of these is a threshold function, and no others exist.