Skip to content

Natural Orbit-Symmetric Hidden-Vertex Ansatze Fail On M222

Claim/Theorem

Let M_{2,2,2} be the smallest connected member of the multi-parallel-circuit family, and write

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

with visible coordinates ordered as

\[ (u,a_1,b_1,a_2,b_2,a_3,b_3). \]

Consider quadratic pseudo-Boolean energies with all pairwise coefficients nonpositive and all coefficients in [-64,64], restricted to either of the following two symmetry-respecting ansatz classes.

Ansatz A: one hidden bit per parallel class

Use hidden bits (h_1,h_2,h_3). Require invariance under:

  1. permutation of the three classes P_1,P_2,P_3, and
  2. swapping a_i and b_i inside each class.

Then every such energy is determined by 11 orbit coefficients:

\[ 1,\ u,\ x,\ h,\ ux,\ uh,\ xx_{\mathrm{same}},\ xx_{\mathrm{diff}},\ xh_{\mathrm{same}},\ xh_{\mathrm{diff}},\ hh. \]

There is no energy of this form whose hidden minimization equals f_{2,2,2}.

Ansatz B: one global hidden bit plus one hidden bit per class

Use hidden bits (g,h_1,h_2,h_3), where g is distinguished but the triple (h_1,h_2,h_3) transforms with the three classes. Require the same visible symmetry as above, together with permutation symmetry of the three class-labeled hidden bits.

Then every such energy is determined by 15 orbit coefficients:

\[ 1,\ u,\ x,\ g,\ h,\ ux,\ ug,\ uh,\ xx_{\mathrm{same}},\ xx_{\mathrm{diff}},\ xg,\ xh_{\mathrm{same}},\ xh_{\mathrm{diff}},\ gh,\ hh. \]

There is no energy of this form whose hidden minimization equals f_{2,2,2}.

Equivalently: two of the most natural global hidden-vertex constructions that keep the full pair-permutation symmetry of M_{2,2,2} already fail by exact MILP infeasibility.

This is a derived exact bounded-ansatz obstruction.

  1. By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], the target function depends only on the singleton bit u and the three pair states, and is invariant under permuting the three pairs and swapping the two elements inside each pair.
  2. For Ansatz A, the symmetry group collapses every quadratic monomial on (u,a_1,b_1,a_2,b_2,a_3,b_3,h_1,h_2,h_3) to one of the 11 orbit types listed above.
  3. For Ansatz B, adding a distinguished global bit g enlarges the orbit list to the 15 types listed above.
  4. In each ansatz, exact realizability reduces to a mixed-integer linear feasibility problem:
  5. one binary selector chooses the minimizing hidden state for each visible assignment x;
  6. for every visible-hidden pair (x,h), one imposes
\[ E(x,h)\ge f_{2,2,2}(x) \]

and the usual selected-state upper bound

\[ E(x,h)\le f_{2,2,2}(x)+M(1-s_{x,h}). \]
  1. Because all coefficients are restricted to [-64,64], the linearization is exact once a sufficiently large M is chosen. The same finite-box logic as in [[smallest-connected-multi-parallel-circuit-member-has-no-1-or-2-auxiliary-realization-in-large-coefficient-box.md]] applies.
  2. For Ansatz A:
  3. the model has 11 continuous coefficient variables and 128\cdot 8=1024 selector binaries;
  4. HiGHS reports the exact MILP infeasible.
  5. For Ansatz B:
  6. the model has 15 continuous coefficient variables and 128\cdot 16=2048 selector binaries;
  7. HiGHS again reports the exact MILP infeasible.
  8. Therefore neither of these natural orbit-symmetric global hidden-vertex ansatz classes realizes f_{2,2,2}.

Consequences for the current frontier:

  • this closes the first symmetry-respecting global constructive routes beyond the already-failed selector quotient and one-branch-bit local factorization;
  • any positive theorem for M_{2,2,2} must either break these simple orbit-symmetric hidden architectures or use a richer hidden interaction pattern than one per class, even after adding one distinguished global bit;
  • this still does not prove nonexpressibility of M_{2,2,2}, because a successful realization could use a less symmetric or more complicated hidden-variable design.

Dependencies

  • [[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]]
  • [[branch-min-route-for-connected-family-fails-at-local-submodularity.md]]

Conflicts/Gaps

  • This node does not prove that f_{2,2,2} is not hidden-vertex graph-cut representable.
  • It proves only that two natural symmetry-respecting bounded ansatz classes fail exactly.
  • A less symmetric construction, or a more elaborate hidden architecture, remains open.
  • Even a future explicit realization or nonexpressibility theorem for this connected family 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