Skip to content

Source All-Arity Expressive Power Stops Before Fan-Certificate Lift

Claim/Theorem

Let f_t be the size-2 connected multi-parallel-circuit cut-rank function from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], so f_t has arity 2t+1 and t\ge 3.

The currently loaded primary-source expressive-power package does not yet convert the fan-cone obstruction from [[connected-size-2-multi-parallel-family-escapes-modular-plus-fan-cone.md]] into ordinary hidden-vertex nonexpressibility for f_t.

More precisely:

  1. Zivny-Cohen-Jeavons prove that every Boolean fan is expressible by binary submodular functions, so fan-cone membership is a sufficient positive construction route in all arities.

  2. Their Theorem 16 gives the exact arity-4 equivalence

    \[ f\in\langle\Gamma_{\mathrm{sub},2}\rangle \iff F_{\mathrm{sep}}\in\operatorname{Mul}(\{f\}) \iff f\in\operatorname{Cone}(\Gamma_{\mathrm{fans},4}). \]

  3. Their Conjecture 20 proposes the all-arity extension

    \[ \Gamma_{\mathrm{sub},k}\cap \langle\Gamma_{\mathrm{sub},2}\rangle = \operatorname{Cone}(\Gamma_{\mathrm{fans},k}) \qquad\text{for all }k, \]

    but the source records it as a conjecture, not as a theorem.

  4. Iwamasa's Boolean network-representability framework confirms that classical Boolean network representability is still exactly \langle\Gamma_{\mathrm{sub},2}\rangle, and its generalized Boolean network classes add only monotone escape cases. Since nonzero stabilizer cut-rank functions are symmetric and vanish on both \emptyset and the full set, that generalized Boolean framework does not supply a larger positive class or a new all-arity negative invariant here.

  5. The weighted-polymorphism machinery in Iwamasa is an abstract closure theorem. It does not provide an explicit all-arity weighted-polymorphism basis for Boolean \Gamma_{\mathrm{sub},2} strong enough to separate f_t.

Applying these source theorems to the present family gives the exact stop point:

  • f_t satisfies the direct higher-arity F_{\mathrm{sep}} test by [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]];
  • f_t lies outside the modular-plus-fan cone by [[connected-size-2-multi-parallel-family-escapes-modular-plus-fan-cone.md]];
  • for the first connected case t=3, the arity is 7, so Theorem 16 does not apply;
  • the already positive four-ary and mixed pinned-shadow tests do not supply a closure-preserving reduction to the arity-4 theorem.

Therefore the exact missing specialization theorem on the obstruction side is a fan-certificate-to-weighted-polymorphism lift:

Convert the existing fan-cone separating certificate for f_3 into a weighted-polymorphism or multimorphism certificate valid for every function in \langle\Gamma_{\mathrm{sub},2}\rangle, or prove an equivalent family-specific instance of Conjecture 20 for the size-2 connected multi-parallel family.

This is a source-grounded obstruction-side closure statement, not a new nonexpressibility theorem.

Dependencies

  • [[higher-arity-theorem16-would-close-negative-side-on-connected-size-2-family.md]]
  • [[connected-size-2-multi-parallel-family-escapes-modular-plus-fan-cone.md]]
  • [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]]
  • [[boolean-network-generalization-adds-no-nonmonotone-power-for-stabilizer-cut-rank.md]]
  • [[every-four-ary-pinning-minor-of-m222-is-one-hidden-representable.md]]
  • [[pinned-five-ary-shadows-of-m222-obstruct-one-hidden-realizability.md]]

Conflicts/Gaps

  • Blocker classification for the Theorem-16 / Conjecture-20 route: (i) the all-arity characterization is conjectural in the source, and (iv) the graph has no theorem converting fan-cone escape into the invariant language of weighted polymorphisms or multimorphisms.
  • Iwamasa's stronger non-Boolean or generalized-domain machinery has the wrong hypothesis class for this Boolean stabilizer cut-rank problem unless it first yields an explicit Boolean all-arity separator for \langle\Gamma_{\mathrm{sub},2}\rangle.
  • This node does not rule out a beyond-fan-cone hidden-vertex construction. It only says the current source package cannot yet prove such a construction impossible.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • 10.48550/arXiv.2109.14599