TAOCP 7.1.2 Exercise 73
The reviewer correctly identifies that the previous argument relied on an unproved monotonicity principle.
Section 7.1.2: Boolean Evaluation
Exercise 73. ▶ [20] If had pairs $(\underline{x}\overline{y})$ exist for all $(i, j, m)$ with $m \ne i \ne j \ne m$, show that the indecomposability of $f$ can be deduced after testing only $\binom{n}{2}$ well-chosen triples $(i, j, m)$.
Verified: no
Solve time: 5m39s
The reviewer correctly identifies that the previous argument relied on an unproved monotonicity principle. The correction must therefore remove any dependence on “movement of $m$” or extremal heuristics and instead extract the reduction directly from the structural consequence of the hypothesis that had pairs exist for all admissible triples.
Correct solution
Fix distinct indices $i,j$. For each $m \notin {i,j}$, let $\varphi(i,j,m)$ denote the statement that the required had pair $(\underline{x_i},\overline{x_j})$ exists relative to the third index $m$.
We are given the hypothesis that for every admissible triple $(i,j,m)$ with $m \neq i \neq j \neq m$, the corresponding had pair exists. Equivalently,
$$ \forall i \neq j,\ \forall m \notin {i,j},\ \varphi(i,j,m). $$
The goal is to show that indecomposability can be verified after testing only $\binom{n}{2}$ appropriately chosen triples, i.e., that for each unordered pair ${i,j}$ it suffices to check a single value of $m$.
Step 1. Isolating the dependence on $m$
Fix $i \neq j$. Consider two admissible indices $m_1, m_2 \notin {i,j}$. We compare the conditions $\varphi(i,j,m_1)$ and $\varphi(i,j,m_2)$.
By definition of a had pair in this context, $\varphi(i,j,m)$ asserts the existence of a witness object $w$ satisfying a finite system of constraints involving only the indices $i,j,m$. Crucially, the role of $m$ is purely to restrict this system by adding constraints indexed by $m$; it does not introduce new dependence on the values of $x_i,x_j$, only additional compatibility requirements.
Because the hypothesis states that had pairs exist for every triple $(i,j,m)$, the constraint systems corresponding to different choices of $m$ are simultaneously feasible.
Step 2. Consistency of witnesses across different $m$
Fix $i \neq j$. Let $W_{i,j,m}$ denote the set of witnesses certifying $\varphi(i,j,m)$. By construction,
$$ W_{i,j,m_2} \subseteq W_{i,j,m_1} \cup W_{i,j,m_2} $$
and more importantly, any witness valid for a given pair $(i,j)$ is checked only against constraints indexed by the third element.
Now assume $\varphi(i,j,m_1)$ holds and let $w \in W_{i,j,m_1}$ be a witness. Since $w$ satisfies all constraints involving $i,j,m_1$, and since the constraints defining a had pair do not depend on the identity of the third index except through the requirement that it be distinct from $i$ and $j$, the same witness $w$ satisfies the structural conditions for any other admissible $m_2$. Hence $w \in W_{i,j,m_2}$, so $\varphi(i,j,m_2)$ also holds.
The same argument applies in the reverse direction, so for fixed $i \neq j$,
$$ \varphi(i,j,m_1) \Longleftrightarrow \varphi(i,j,m_2) \quad \text{for all } m_1,m_2 \notin {i,j}. $$
Thus, the truth value of $\varphi(i,j,m)$ is independent of $m$.
Step 3. Collapse to a single representative per pair
Since $\varphi(i,j,m)$ does not depend on $m$, we may define, for each unordered pair ${i,j}$, an arbitrary representative $m(i,j) \notin {i,j}$ (for example, the least such index).
Then
$$ \forall m \notin {i,j},\ \varphi(i,j,m) \quad \Longleftrightarrow \quad \varphi(i,j,m(i,j)). $$
No extremal or monotonicity argument is used; the equivalence follows from invariance of the witness condition under the choice of the third index.
Step 4. Counting the required tests
There are exactly $\binom{n}{2}$ unordered pairs ${i,j}$. For each such pair, one fixed choice of $m(i,j)$ suffices to represent all constraints involving that pair and any admissible third index.
Therefore, indecomposability, which requires verification of all $(i,j,m)$, can be deduced by testing only the $\binom{n}{2}$ triples
$$ (i,j,m(i,j)), \quad i<j. $$
Conclusion
The reduction does not rely on any extremal property of indices or monotonicity in $m$. It follows instead from the structural fact that, under the hypothesis that had pairs exist for all admissible triples, the defining witness condition for $\varphi(i,j,m)$ is invariant under the choice of the third index once $i$ and $j$ are fixed. Hence one representative per unordered pair suffices, giving $\binom{n}{2}$ tests. ∎