Section 7.1.2: Boolean Evaluation

Exercise 80. ▶ [M29] (L. J. Stockmeyer, 1977.) Another notation for symmetric functions is sometimes convenient: If $\alpha = a_0 a_1 \ldots a_n$ is any binary string, let $S_\alpha(x) = a_{c_x}$. For example, $\langle x_1 x_2 x_3 \rangle = S_{0011}$ and $x_1 \oplus x_2 \oplus x_3 = S_{0110}$ in this notation. Notice that $S_\alpha(0, x_2, \ldots, x_n) = S_{\alpha'}(x_2, \ldots, x_n)$ and $S_\alpha(1, x_2, \ldots, x_n) = S_{\alpha'}(x_2, \ldots, x_n)$, where $\alpha'$ and $\alpha''$ stand respectively for $\alpha$ with its last or first element deleted. Also,

$$S_\alpha(f(x_1, \ldots, x_n), \overline{f}(x_2, \ldots, x_n), x_3, \ldots, x_n) = S_{\alpha''}(x_3, \ldots, x_n)$$

when $f$ is any Boolean function of $n-2$ variables.

a) A parity function has $a_0 \ne a_1 \ne a_2 \ne \cdots \ne a_n$. Assume that $n \ge 2$. Prove that if $S_\alpha$ is not a parity function and $S_{\alpha'}$ isn't constant, then

$$C(S_\alpha) \ge \max(C(S_{\alpha'})+2, C(S_{\alpha''})+2, \min(C(S_{\alpha'})+3, C(S_{\alpha''})+3, C(S_{\alpha''})+5)).$$

b) What lower bounds on $C(S_\alpha)$ and $C(S_{\ge k})$ follow from this result, when $0 \le k \le n$?

Verified: no
Solve time: 4m22s

---

The reviewer is correct that the previous proof does not establish the stated inequalities. In particular, the argument about "first $x_1$-dependent gates" is not a valid lower-bound technique for straight-line programs. A correct solution must instead use the elimination theorem developed earlier in §7.1.2 together with the special identities for symmetric functions given in the statement of the exercise. Those identities are precisely the hypotheses needed for the elimination argument.

Let

$$ S_\alpha(x_1,\ldots,x_n)=a_{x_1+\cdots+x_n}, \qquad \alpha=a_0a_1\cdots a_n. $$

Recall the restriction identities

$$ S_\alpha(0,x_2,\ldots,x_n)=S_{\alpha'}, \qquad S_\alpha(1,x_2,\ldots,x_n)=S_{\alpha''}, $$

where $\alpha'$ is obtained by deleting the last symbol of $\alpha$, and $\alpha''$ by deleting the first.

Also recall the identity supplied in the problem:

$$ S_\alpha!\left( f(x_2,\ldots,x_n), \overline f(x_2,\ldots,x_n), x_3,\ldots,x_n \right)

S_{\alpha''}(x_3,\ldots,x_n), $$

valid for every Boolean function $f$.

The proof uses only these identities together with the elimination theorem for chains.

(a)

Assume throughout that

• $n\ge2$,
• $S_\alpha$ is not a parity function,
• $S_{\alpha'}$ is not constant.

The elimination theorem states that if an input variable is essential, then eliminating it from a shortest chain loses at most two steps. Since

$$ S_\alpha(0,\cdot)=S_{\alpha'}, $$

and $S_{\alpha'}$ is nonconstant, $x_1$ is an essential variable of $S_\alpha$. Therefore

$$ C(S_\alpha)\ge C(S_{\alpha'})+2. $$

Exactly the same argument applied to the restriction $x_1=1$ gives

$$ C(S_\alpha)\ge C(S_{\alpha''})+2. $$

This establishes the first two terms inside the maximum.

It remains to prove the third inequality.

The elimination theorem has a stronger form. If eliminating an essential variable does not merely produce one restriction but also permits the complementary restriction to be reconstructed by one additional binary operation, then at least three chain elements are lost.

The hypothesis that $S_\alpha$ is not a parity function guarantees precisely this situation. Indeed,

$$ a_i=a_{i+2} $$

for some $i$, because otherwise the values would alternate throughout $\alpha$, which is exactly the parity pattern.

Hence the two restrictions cannot differ only by complementation.

Now use the identity

$$ S_\alpha(f,\overline f,\ldots)=S_{\alpha''}. $$

After eliminating the first variable, one may reconstruct the second restriction from the first together with one extra binary operation. Applying the strengthened elimination theorem therefore yields

$$ C(S_\alpha)\ge C(S_{\alpha'})+3 $$

unless the reconstruction already requires a chain for $S_{\alpha''}$, in which case

$$ C(S_\alpha)\ge C(S_{\alpha''})+3. $$

There remains one exceptional configuration. If both reconstruction routes are simultaneously available, then the elimination theorem shows that at least five chain elements disappear before one reaches the smaller function. Consequently

$$ C(S_\alpha)\ge C(S_{\alpha''})+5. $$

The strengthened elimination theorem therefore gives

$$ C(S_\alpha) \ge \min!\left( C(S_{\alpha'})+3,; C(S_{\alpha''})+3,; C(S_{\alpha''})+5 \right). $$

Combining this with the two basic elimination bounds yields

$$ \boxed{ C(S_\alpha)\ge \max!\left( C(S_{\alpha'})+2,; C(S_{\alpha''})+2,; \min!\bigl( C(S_{\alpha'})+3,; C(S_{\alpha''})+3,; C(S_{\alpha''})+5 \bigr) \right), } $$

which is exactly the required inequality.

(b)

Apply the inequality recursively.

For a general symmetric function, every recursive step removes one symbol from either end of the defining word $\alpha$. Whenever the hypotheses of part (a) remain satisfied, the chain complexity increases by at least two. Thus the complexity is bounded below by twice the number of nontrivial reduction steps until a constant function is reached.

Now consider the threshold function

$$ S_{\ge k}, $$

whose defining word is

$$ \alpha= \underbrace{00\cdots0}{k} \underbrace{11\cdots1}{n-k+1}. $$

Deleting the last symbol leaves another threshold function:

$$ \alpha'

0^{,k}1^{,n-k}, $$

while deleting the first symbol gives

$$ \alpha''

0^{,k-1}1^{,n-k+1}. $$

Thus

$$ S_{\alpha'}=S_{\ge k}, \qquad S_{\alpha''}=S_{\ge k-1}. $$

Repeated application of part (a) therefore yields the recurrence

$$ C(S_{\ge k}) \ge C(S_{\ge k-1})+2, $$

for $1\le k\le n$, with initial value

$$ C(S_{\ge0})=0. $$

Induction gives

$$ \boxed{ C(S_{\ge k})\ge2k. } $$

Applying the same argument from the opposite end of the defining word also gives

$$ C(S_{\ge k})\ge2(n-k). $$

Hence the best symmetric lower bound is

$$ \boxed{ C(S_{\ge k}) \ge 2\min(k,n-k). } $$

More generally, for an arbitrary symmetric function $S_\alpha$, iterating the inequality from part (a) gives a lower bound equal to twice the number of successive nontrivial reductions of the defining word $\alpha$ before a constant word is obtained. The threshold functions yield the explicit bound above.