Skip to content

F3 Certificate Passes Pairwise Rank-Order Extension But Not Full Closure

Claim/Theorem

The finite checker in docs/project_QEM-QEC/tmp/scripts/route_d_operation_extension.py does not refute the reconstructed f_3 certificate as a \Gamma_{\mathrm{sub},2} operation-level obstruction. It sharpens the obstruction side to the full rank-order extension problem.

For the f_3 certificate:

  • the observed seven input-output columns are conservative;
  • all observed pairwise Hamming inequalities hold;
  • the minimum observed pairwise slack is 0;
  • coordinate-permutation extensions are infeasible;
  • nested canonical rank-order extensions are infeasible;
  • the pairwise meet/join rank-order closure ILP is feasible with 51 closure points, 2550 binary variables, and 20700 monotonicity constraints;
  • full meet/join closure exceeds the configured cap, reaching 3001 closure points before completion.

The six-qubit hidden-vertex-representable control behaves similarly:

  • the observed support test passes;
  • the pairwise meet/join rank-order closure ILP is feasible with 38 closure points;
  • full meet/join closure also exceeds the 3000 cap.

The toy meet/join submodularity certificate behaves differently:

  • the direct observed test passes;
  • the nested canonical subclass is feasible;
  • the full closure ILP solves optimally on closure size 4.

Thus the current finite tests preserve the intended calibration:

\[ \text{toy positive case is solved, while } f_3 \text{ and the representable six-qubit control remain indistinguished.} \]

The current f_3 certificate is therefore not killed by any implemented operation-extension necessary condition. The next exact finite task is the full rank-preserving order-preserving extension problem, not another pairwise Hamming check.

Dependencies

  • [[conservative-hamming-operation-extension-is-rank-order-lattice-extension.md]]
  • [[f3-fan-certificate-passes-necessary-multimorphism-tests-but-not-operation-lift.md]]
  • [[fan-cone-certificates-are-not-hidden-vertex-invariants.md]]
  • [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]]

Conflicts/Gaps

  • Pairwise meet/join closure is a sound necessary restriction, not a sufficient total-operation proof.
  • The full closure cap is a computational barrier, not an infeasibility theorem.
  • Because the six-qubit representable control also passes the implemented tests, the present finite checks are not yet hidden-vertex invariants.

Sources

  • 10.1016/j.dam.2009.07.001
  • local computation: docs/project_QEM-QEC/tmp/certificates/operation_extension_report.json
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_operation_extension.py