Every Four-Ary Pinning Minor Of M222 Is One-Hidden Representable¶

Claim/Theorem¶

Let M_{2,2,2} be the smallest connected member of the multi-parallel-circuit family from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], and let

\[ f_{2,2,2}(x):=\lambda_{M_{2,2,2}}(L_x), \qquad x\in\{0,1\}^7. \]

Fix any 4 visible coordinates and pin the remaining 3 visible coordinates to constants in {0,1}. Let

\[ g:\{0,1\}^4\to\mathbb R \]

be the resulting pinned 4-ary minor of f_{2,2,2}.

Then g is representable by a quadratic binary-submodular energy with one auxiliary bit. Equivalently, for every such g there exist

\[ q(y)=c+\sum_{i=1}^4 \alpha_i y_i+\sum_{1\le i<j\le 4}\beta_{ij}y_i y_j \qquad(\beta_{ij}\le 0) \]

and an affine form

\[ \ell(y)=\lambda_0+\sum_{i=1}^4 \lambda_i y_i \qquad(\lambda_i\le 0) \]

such that

\[ g(y)=q(y)+\min(0,\ell(y)) = \min_{h\in\{0,1\}}\bigl(q(y)+h\,\ell(y)\bigr). \]

So every 4-ary pinning shadow of M_{2,2,2} already lies in the one-hidden-bit subclass of the hidden-vertex graph-cut cone.

This is a derived exact finite theorem.

By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], f_{2,2,2} is the 7-ary cut-rank function of the first connected \chi\ge 3 test family.
A quadratic pseudo-Boolean energy with one hidden bit has the form

\[ E(y,h)=q(y)+h\,\ell(y), \]

because there is only one hidden-visible interaction layer and no nontrivial hidden-hidden term. Minimizing over h gives exactly

\[ \min_{h\in\{0,1\}} E(y,h)=q(y)+\min(0,\ell(y)). \]

Thus one-hidden representability of a 4-ary function is an exact linear-feasibility problem once the negative branch mask

\[ B:=\{y\in\{0,1\}^4:\ell(y)<0\} \]

is fixed.
There are

\[ \binom{7}{4}\cdot 2^3 = 280 \]

4-ary pinning minors of f_{2,2,2}.
Up to permutation of the 4 visible coordinates, these 280 minors collapse to 21 canonical truth tables.
To search for one-hidden realizations, enumerate strict affine negative-branch masks on \{0,1\}^4 by running through all affine forms

\[ \ell(y)=\lambda_0+\sum_{i=1}^4 \lambda_i y_i \]

with integer coefficients in [-5,5]. This yields 1882 distinct branch masks.
For a fixed canonical truth table and a fixed branch mask B, exact one-hidden representability is linear feasibility in the 16 coefficients consisting of:
- 11 coefficients of the quadratic visible part q,
- 5 coefficients of the affine form \ell.
The constraints are:
- equality of g(y) with q(y)+\ell(y) on y\in B,
- equality of g(y) with q(y) on y\notin B,
- submodularity inequalities \beta_{ij}\le 0,
- hidden-visible submodularity inequalities \lambda_i\le 0.
For each of the 21 canonical truth tables, at least one of the 1882 branch masks is feasible.
Permuting visible coordinates preserves one-hidden representability, so every one of the original 280 pinned 4-ary minors is one-hidden representable.

Consequences for the current frontier:

this is strictly stronger than [[smallest-connected-multi-parallel-circuit-member-survives-all-four-ary-exact-minors.md]], which only showed that all 4-ary pinning/minimization minors satisfy the unbounded-auxiliary Sep test;
any impossibility theorem for M_{2,2,2} with 1 or 2 auxiliaries cannot be witnessed after pinning down to 4 visible coordinates;
any low-auxiliary obstruction must therefore be genuinely global, involving at least 5 visible coordinates or a non-pinning mechanism.

Dependencies¶

[[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
[[smallest-connected-multi-parallel-circuit-member-survives-all-four-ary-exact-minors.md]]

Conflicts/Gaps¶

This node does not prove that f_{2,2,2} itself is representable with one hidden bit.
It concerns only 4-ary pinning minors, not the full 7-ary function and not 4-ary minors obtained by minimizing additional visible coordinates.
The theorem therefore sharpens the locality of the obstruction, but does not settle the full connected-family question.
Even a future whole-family positive or negative theorem would still need a separate bridge to routing-style CD(T_n,G) semantics.

Sources¶

10.1016/j.dam.2009.07.001
10.48550/arXiv.2109.14599