Pinned Five-Ary Shadows Of M222 Obstruct One-Hidden Realizability¶

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 write

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

Consider 5-ary pinning minors of f_{2,2,2} obtained by keeping any 5 visible coordinates and fixing the remaining 2 to constants in {0,1}.

Then the first exact low-auxiliary obstruction already appears on these genuinely global shadows:

up to permutation of the 5 visible coordinates, the 84 pinned 5-ary minors collapse to 10 canonical truth tables;
exactly 7 of these 10 canonical classes are not representable by a quadratic binary-submodular energy with one auxiliary bit;
consequently f_{2,2,2} itself is not representable with one auxiliary bit.

In particular, the representative pinned shadow obtained by keeping

\[ (u,a_1,b_1,a_2,b_2) \]

and pinning

\[ (a_3,b_3)=(0,0) \]

has no one-hidden-bit realization.

Equivalently: the first exact low-auxiliary obstruction for M_{2,2,2} appears already on pinned 5-ary shadows, even though [[every-four-ary-pinning-minor-of-m222-is-one-hidden-representable.md]] shows that every pinned 4-ary shadow is still one-hidden representable.

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), \]

where q is quadratic in the visible coordinates and \ell is affine. Minimizing over h gives

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

So one-hidden representability is equivalent to existence of a quadratic visible part q and an affine negative-branch mask

\[ B=\{y\in\{0,1\}^5:\ell(y)<0\}. \]
Any strict affine threshold subset of \{0,1\}^5 has an integer witnessing affine form

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

with

\[ |\lambda_i|\le 216 \]

for all i, and with

\[ \ell(y)\le -1 \ \text{on } B, \qquad \ell(y)\ge 0 \ \text{off } B. \]

Indeed, after scaling any strict separator to margin 1, choose a basic feasible solution of the resulting linear system. It is determined by 6 tight inequalities in the 6 affine coefficients. The corresponding 6\times 6 matrix has entries in {0,\pm 1}, so Hadamard gives determinant at most

\[ 6^{6/2}=216. \]

Cramer's rule then yields an integer witness with the stated coordinate bound.
For any pinned 5-ary shadow g, this turns one-hidden representability into an exact MILP with:
- 16 continuous coefficients for the quadratic visible part q,
- 6 integer affine coefficients \lambda_0,\dots,\lambda_5 in [-216,216],
- 32 branch binaries selecting whether each visible assignment lies in B.
The visible quadratic coefficients are constrained by \beta_{ij}\le 0, and the hidden-visible coefficients by \lambda_i\le 0 for i\ge 1.
Since every pinned 5-ary shadow takes values in {0,1,2,3}, and every affine witness from step 3 satisfies

\[ |\ell(y)|\le 6\cdot 216=1296, \]

one has

\[ |q(y)|\le 1299. \]

By Möbius inversion on the 5-cube, every coefficient of q is therefore bounded in absolute value by

\[ 32\cdot 1299 = 41568. \]

Hence the resulting MILP is exact.
There are

\[ \binom{7}{5}\cdot 2^2 = 84 \]

pinned 5-ary minors of f_{2,2,2}.
Up to permutation of the 5 visible coordinates, these 84 minors collapse to 10 canonical truth tables.
Solving the exact one-hidden MILP for each canonical class yields:
- 3 feasible classes,
- 7 infeasible classes.
So one-hidden representability already fails on pinned 5-ary shadows.
For the representative shadow with visible coordinates (u,a_1,b_1,a_2,b_2) and pinned (a_3,b_3)=(0,0), the explicit formula is

\[ g(u,a_1,b_1,a_2,b_2) = \mathbf 1[a_1\ne b_1] +\mathbf 1[a_2\ne b_2] +u +(1-u)\,\mathbf 1[(a_1,b_1)=(1,1)\ \vee\ (a_2,b_2)=(1,1)]. \]

Its exact one-hidden MILP is infeasible.
If f_{2,2,2} had a one-hidden realization, then every pinned minor would inherit one by fixing visible coordinates in that same gadget. Therefore infeasibility of any pinned 5-ary shadow proves that f_{2,2,2} itself has no one-hidden realization.

Consequences for the current frontier:

the exact one-hidden boundary is now pinned down: 4-ary pinning shadows are all positive, but 5-ary pinning shadows already contain obstructions;
this is an unbounded k<=1 impossibility theorem for M_{2,2,2}, not a coefficient-box search artifact;
the case of 2 hidden bits remains open, as does a fully less-symmetric k>=3 realization of the full connected witness.

Dependencies¶

[[every-four-ary-pinning-minor-of-m222-is-one-hidden-representable.md]]
[[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
[[smallest-connected-multi-parallel-circuit-member-has-no-1-or-2-auxiliary-realization-in-large-coefficient-box.md]]

Conflicts/Gaps¶

This node proves only an unbounded k<=1 impossibility theorem for M_{2,2,2}.
It does not settle whether some pinned 5-ary shadow, or f_{2,2,2} itself, is representable with 2 hidden bits.
It also does not rule out a fully less-symmetric realization with 3 or more hidden bits.
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