Skip to content

Connected Size-2 Multi-Parallel Family Escapes Modular-Plus-Fan Cone

Claim/Theorem

Let M_t be the size-2 connected multi-parallel family from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], and write

\[ f_t(x):=\lambda_{M_t}(L_x), \qquad x\in\{0,1\}^{2t+1}. \]

Then for every t\ge 3, the Boolean function f_t does not lie in the cone generated by modular Boolean functions together with Boolean upper and lower fans in the sense of Živný-Cohen-Jeavons, Definition 5.

Equivalently, for every connected member of the size-2 family there is no decomposition

\[ f_t = m+\sum_j \lambda_j \phi_j, \qquad \lambda_j\ge 0, \]

with m modular and each \phi_j a Boolean upper or lower fan.

This is a derived exact family theorem.

  1. By [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]], the size-2 family has the explicit form

    \[ f_t(x) = \sum_{i=1}^t \mathbf 1[a_i\ne b_i] + u\,\mathbf 1[\exists i:\ (a_i,b_i)=(0,0)] + (1-u)\,\mathbf 1[\exists i:\ (a_i,b_i)=(1,1)]. \]

  2. For the first connected case t=3, exhaustive enumeration of Boolean fans from Živný-Cohen-Jeavons, Definition 5 gives:

    • 14948 distinct 7-ary upper fans;
    • 14948 distinct 7-ary lower fans.

  3. There is an exact integer Farkas certificate y\in\{-1,0,1\}^{128} with support 100 such that:

    • y\cdot m=0 for every modular 7-ary Boolean function m;
    • y\cdot \phi\ge 0 for every 7-ary Boolean upper or lower fan \phi;
    • y\cdot f_3=-10.

    Hence f_3 does not lie in the modular-plus-fan cone.

  4. For every t>3, pin the extra parallel classes to split states

    \[ (a_i,b_i)=(1,0) \qquad \text{for } i=4,\dots,t. \]

    Then each pinned class contributes exactly 1 to the split count and contributes nothing to the 00 or 11 witness terms, so

    \[ f_t\big|_{(a_i,b_i)=(1,0)\ \forall i\ge 4} = f_3+(t-3). \]

  5. Restricting a modular Boolean function to a face of the Boolean cube keeps it modular. Restricting a Boolean upper or lower fan to such a face again yields a Boolean upper fan, a Boolean lower fan, or a modular constant term, by direct inspection of Definition 5 and Example 7 after deleting the fixed coordinate.

  6. Therefore modular-plus-fan membership descends under the above pinning. If some f_t with t>3 lay in the modular-plus-fan cone, then f_3 would also lie in that cone after restriction and subtraction of the modular constant (t-3), contradiction.

So the whole connected size-2 family escapes the modular-plus-fan constructive closure.

Consequences for the current frontier:

  • the first connected post-threshold family already lies beyond the constructive closure that succeeded for all 5-qubit stabilizer functions;
  • any positive hidden-vertex theorem on this family must use expressible binary-submodular objects beyond the modular-plus-fan cone;
  • this is a genuine family-level strengthening of the previous witness-level constructive barriers.

Dependencies

  • [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
  • [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]]
  • [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]]
  • [[fixed-prefix-state-construction-route-for-size-2-multi-parallel-family-fails-at-transition-and-readout-submodularity.md]]

Conflicts/Gaps

  • This node does not prove that the connected size-2 family is not ordinarily hidden-vertex representable.
  • It closes only the modular-plus-fan constructive route on that family.
  • More global hidden-vertex realizations using binary-submodular objects beyond the fan cone remain open.

Sources

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