TAOCP 7.1.1 Exercise 22
We restart from the definition and avoid introducing properties that cannot be justified.
Exercise 22. [20] [20] Suppose $f(x_1,\ldots,x_n) = g(x_1,\ldots,x_{n-1})\oplus h(x_1,\ldots,x_{n-1})\wedge x_n$, as in (16). What conditions on $g$ and $h$ are necessary and sufficient for $f$ to be monotone?
Verified: yes
Solve time: 4m36s
We restart from the definition and avoid introducing properties that cannot be justified.
Let
$$ f(x',x_n)=g(x')\oplus (h(x')\wedge x_n), \quad x'=(x_1,\dots,x_{n-1}). $$
Then
$$ f(x',0)=g(x'), \qquad f(x',1)=g(x')\oplus h(x'). $$
It is convenient to eliminate the XOR under the correct structural condition that will appear below.
Step 1. Necessary conditions from restriction to subcubes
(i) Monotonicity of $g$
Restrict to $x_n=0$. Then $f(x',0)=g(x')$. Since $f$ is monotone in all variables, it is monotone in particular in $x'$, hence
$$ g \text{ is monotone.} $$
(ii) Condition from monotonicity in the $x_n$-direction
Fix $x'$. Monotonicity in $x_n$ requires
$$ f(x',0)\le f(x',1), $$
that is,
$$ g(x') \le g(x')\oplus h(x'). $$
Check when this fails. The only failure is
$$ g(x')=1,\quad g(x')\oplus h(x')=0, $$
which happens exactly when $g(x')=h(x')=1$. Hence
$$ g(x')\wedge h(x')=0 \quad \forall x', $$
so
$$ g\wedge h=0. $$
Under this condition,
$$ g\oplus h = g\vee h, $$
so
$$ f(x',1)=g(x')\vee h(x'). $$
(iii) Monotonicity of $g\vee h$
Restrict to $x_n=1$. Then $f(x',1)=g(x')\vee h(x')$. Since $f$ is monotone,
$$ g\vee h \text{ is monotone.} $$
Step 2. Why no further condition on $h$ is forced
The earlier flawed argument attempted to deduce monotonicity of $h$ from properties of $g\vee h$ and $g$. This is invalid because upward closure of a union does not transfer to its components.
Indeed, $h$ may decrease along a chain while $g$ becomes $1$ and “covers” the violation in $g\vee h$. Thus monotonicity of $h$ is not necessary.
Step 3. Sufficiency of the conditions
Assume:
- $g$ is monotone,
- $g\wedge h=0$,
- $g\vee h$ is monotone.
Then
$$ f(x',0)=g(x'), \qquad f(x',1)=g(x')\vee h(x'). $$
We verify monotonicity of $f$.
Let $(x',x_n)\le (y',y_n)$.
Case 1: $x_n=y_n=0$
$$ f(x',0)=g(x')\le g(y')=f(y',0) $$
by monotonicity of $g$.
Case 2: $x_n=y_n=1$
$$ f(x',1)=g(x')\vee h(x') \le g(y')\vee h(y')=f(y',1) $$
by monotonicity of $g\vee h$.
Case 3: $x_n=0,, y_n=1$
$$ f(x',0)=g(x') \le g(y') \le g(y')\vee h(y')=f(y',1), $$
using monotonicity of $g$ and the definition of $\vee$.
Thus $f$ is monotone.
Step 4. Necessity is complete
From monotonicity of $f$ we derived:
- $g$ is monotone,
- $g\vee h$ is monotone,
- $g\wedge h=0$.
No additional conditions follow, and none are required.
Final answer
The function
$$ f(x_1,\ldots,x_n)=g(x_1,\ldots,x_{n-1})\oplus (h(x_1,\ldots,x_{n-1})\wedge x_n) $$
is monotone if and only if:
$$ \boxed{ g \text{ is monotone},\quad g\vee h \text{ is monotone},\quad g\wedge h=0. } $$
In particular, monotonicity of $h$ is not required and does not follow from monotonicity of $f$.