Section 7.1.1: Boolean Basics

Exercise 110. [M23] [M23] A Boolean function is called regular if $x \le y$ implies that $f(x) \le f(y)$ for all vectors $x$ and $y$, where $\le$ is the majorization relation in exercise 109. Prove or disprove the following statements:

a) Every regular function is monotone.

b) If $f$ is a threshold function (75) for which $w_1 \ge w_2 \ge \cdots \ge w_n$, then $f$ is regular.

c) If $f$ is an $s(s_1, s_2, \ldots, s_n)$ threshold function, then $s_1 \ge s_2 \ge \cdots \ge s_n$ implies that $f$ is regular.

d) Suppose $f$ is a pure majority function, namely a threshold function of the form (86) with $a = b = 0$. Then $s_1 \ge s_2 \ge \cdots \ge s_n$ implies that $w_1 \ge w_2 \ge \cdots \ge w_n$.

Verified: no
Solve time: 6m48s

---

Let $x \le y$ denote the majorization order of Exercise 109. Thus for binary vectors $x=(x_1,\ldots,x_n)$ and $y=(y_1,\ldots,y_n)$,

$$ x\le y $$

means that

$$ \sum_{i=1}^{k}x_i\le \sum_{i=1}^{k}y_i \qquad (1\le k\le n). $$

A Boolean function $f$ is regular if

$$ x\le y \implies f(x)\le f(y). $$

We examine each statement.

(a) Every regular function is monotone

This statement is true.

Suppose $f$ is regular, and suppose

$$ x_i\le y_i \qquad (1\le i\le n). $$

Then for every $k$,

$$ \sum_{i=1}^{k}x_i\le \sum_{i=1}^{k}y_i, $$

hence $x\le y$ in the majorization order.

By regularity,

$$ f(x)\le f(y). $$

But this is exactly the definition of a monotone Boolean function. Therefore every regular function is monotone.

$$ \boxed{\text{(a) True}} $$

(b) If $f$ is a threshold function (75) for which $w_1\ge w_2\ge\cdots\ge w_n$, then $f$ is regular

This statement is true.

Let

$$ f(x)=\Bigl[\sum_{i=1}^{n} w_i x_i \ge t\Bigr], $$

with

$$ w_1\ge w_2\ge\cdots\ge w_n. $$

Assume $x\le y$. Define

$$ D_k=\sum_{i=1}^{k}(y_i-x_i). $$

Since $x\le y$, we have $D_k\ge0$ for all $k$.

Put $w_{n+1}=0$. By summation by parts,

$$ \sum_{i=1}^{n}w_i(y_i-x_i)

\sum_{k=1}^{n}(w_k-w_{k+1})D_k . $$

Since

$$ w_k-w_{k+1}\ge0 $$

and

$$ D_k\ge0, $$

every term on the right-hand side is nonnegative. Therefore

$$ \sum_{i=1}^{n}w_i y_i \ge \sum_{i=1}^{n}w_i x_i . $$

Hence

$$ f(x)=1 $$

implies

$$ \sum_{i=1}^{n}w_i x_i\ge t, $$

which in turn implies

$$ \sum_{i=1}^{n}w_i y_i\ge t. $$

Thus $f(y)=1$. Therefore

$$ x\le y \implies f(x)\le f(y), $$

so $f$ is regular.

$$ \boxed{\text{(b) True}} $$

(c) If $f$ is an $s(s_1,\ldots,s_n)$ threshold function, then $s_1\ge s_2\ge\cdots\ge s_n$ implies that $f$ is regular

This statement is true.

The point that must be justified is the role of the $s_i$. In Knuth's notation, an $s(s_1,\ldots,s_n)$ threshold function is defined by comparing the linear form determined by the coefficients $s_i$. Thus the value of $f(x)$ depends only on the quantity

$$ \sum_{i=1}^{n}s_i x_i $$

and the threshold specified in the definition of the $s$-representation.

Assume

$$ s_1\ge s_2\ge\cdots\ge s_n. $$

Let $x\le y$, and define

$$ D_k=\sum_{i=1}^{k}(y_i-x_i)\ge0. $$

Exactly as in part (b),

$$ \sum_{i=1}^{n}s_i(y_i-x_i)

\sum_{k=1}^{n}(s_k-s_{k+1})D_k, $$

where $s_{n+1}=0$.

Because

$$ s_k-s_{k+1}\ge0 $$

and $D_k\ge0$, it follows that

$$ \sum_{i=1}^{n}s_i y_i \ge \sum_{i=1}^{n}s_i x_i. $$

Therefore whenever $x\le y$, the linear form defining the $s$-threshold function cannot decrease. Since the decision rule for an $s(s_1,\ldots,s_n)$ threshold function is monotone in that linear form, it follows that

$$ f(x)\le f(y). $$

Hence $f$ is regular.

$$ \boxed{\text{(c) True}} $$

(d) Suppose $f$ is a pure majority function, namely a threshold function of the form (86) with $a=b=0$. Then $s_1\ge s_2\ge\cdots\ge s_n$ implies that $w_1\ge w_2\ge\cdots\ge w_n$

This statement is false.

For pure majority functions, formula (86) expresses $f$ in terms of the coefficients $s_i$, while formula (75) gives a threshold representation with coefficients $w_i$. The statement asserts that ordering of the $s_i$ forces the same ordering of the $w_i$.

However, threshold representations are generally far from unique. The same Boolean function can admit many distinct threshold representations with different weight vectors. Therefore an ordering property of one particular $s$-representation cannot automatically force the same ordering for all threshold weight vectors $w_i$.

A counterexample is obtained from the two-variable majority function

$$ f(x_1,x_2)=x_1\lor x_2 . $$

This is a pure majority function. It has an $s$-representation with

$$ s_1=s_2=1, $$

so certainly

$$ s_1\ge s_2. $$

But the same function has the threshold representation

$$ f(x_1,x_2)

\Bigl[,x_1+2x_2\ge1,\Bigr]. $$

Here

$$ w_1=1,\qquad w_2=2, $$

so

$$ w_1<w_2. $$

Thus the conclusion

$$ w_1\ge w_2 $$

fails, even though

$$ s_1\ge s_2. $$

Therefore the implication asserted in (d) is not valid.

$$ \boxed{\text{(d) False}} $$

Combining the four parts:

$$ \boxed{\text{(a) True,\qquad (b) True,\qquad (c) True,\qquad (d) False.}} $$