Skip to content

F3 Fan Certificate Passes Necessary Multimorphism Tests But Not Operation Lift

Claim/Theorem

Let f_3 be the first connected size-2 multi-parallel-circuit function from [[connected-size-2-multi-parallel-family-escapes-modular-plus-fan-cone.md]], with variables ordered

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

The local certificate reconstruction in docs/project_QEM-QEC/tmp/scripts/route_d_certificate_lift.py rebuilds an exact integer fan-cone separating certificate

\[ y\in\{-1,0,1\}^{128} \]

with the following verified properties:

  • 14948 upper fans and 14948 lower fans are enumerated, giving 29895 distinct upper-or-lower fan vectors after overlap;
  • \operatorname{supp}(y)=100;
  • y\cdot m=0 for every modular 7-ary Boolean function m;
  • \min_{\phi\in\Gamma_{\mathrm{fans},7}} y\cdot\phi=0;
  • y\cdot f_3=-10.

The same computation gives the first operation-level diagnostic for the desired certificate lift.

Write P=\{x:y_x=1\} and N=\{x:y_x=-1\}. Then:

  • |P|=|N|=50;
  • the modular balance equations imply that, for each visible coordinate, the number of ones in P equals the number of ones in N;

  • for every pair of visible coordinates i,j,

    \[ \sum_x y_x\,\mathbf 1[x_i\ne x_j]\ge 0, \]

    with minimum pairwise defect 0.

These are exactly the finite necessary checks one obtains by trying to read y as a single multimorphism inequality for \Gamma_{\mathrm{sub},2}: Theorem 14 of Zivny-Cohen-Jeavons says such a multimorphism must be conservative and Hamming-distance non-increasing.

However, these necessary checks do not construct a multimorphism or weighted polymorphism. A genuine lift would still have to supply one of the following:

  • a total operation

    \[ F:\{0,1\}^{50}\to\{0,1\}^{50} \]

    that is conservative and Hamming-distance non-increasing, maps the observed input columns to the observed output columns, and whose induced inequality has coefficient vector y;

  • or a weighted-polymorphism decomposition expressing y as a nonnegative combination of valid multimorphism inequalities for \Gamma_{\mathrm{sub},2}.

The integer certificate itself is not invariant under the full visible symmetry group of f_3; the script finds a 96-element visible symmetry group and reports integer_certificate_invariant = false. Averaging over the group does produce a rational symmetric fan-cone certificate with the same target value -10, because the fan cone and f_3 are symmetry-invariant, but this still remains cone duality rather than an operation-level invariant.

Thus the certificate-lift attempt has made a real partial advance: the f_3 certificate is not killed by the first conservative/Hamming tests, but the live missing object is now an explicit operation-extension or weighted-polymorphism-decomposition theorem.

Dependencies

  • [[connected-size-2-multi-parallel-family-escapes-modular-plus-fan-cone.md]]
  • [[source-all-arity-expressive-power-stops-before-fan-certificate-lift.md]]
  • [[route-d-post-fan-cone-next-target-is-fan-certificate-to-polymorphism-lift.md]]
  • [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]]

Conflicts/Gaps

  • This node does not prove f_3\notin\langle\Gamma_{\mathrm{sub},2}\rangle.
  • The finite checks are necessary for a single conservative Hamming-nonincreasing multimorphism interpretation, not sufficient.
  • The certificate may still fail to extend to a total operation on \{0,1\}^{50} or to decompose as a weighted polymorphism.
  • The symmetry-averaged certificate is rational and cone-valid, but no graph node currently proves that it is a hidden-variable expressibility invariant.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • local computation: docs/project_QEM-QEC/tmp/certificates/f3_certificate_report.json
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_certificate_lift.py