Skip to content

Full Closure Hall And Critical ILP Do Not Refute F3 Operation Extension

Claim/Theorem

The full rank-order closure diagnostics do not refute operation extension for the current f_3 certificate.

Using the exact pattern-upset closure from [[full-rank-order-closure-reduces-to-pattern-upset-lattice.md]], the script docs/project_QEM-QEC/tmp/scripts/route_d_full_rank_order_extension.py scanned every one of the 2,849,631 domain closure elements for the interval/Hall obstruction forced by the fixed generator values.

For f_3:

  • interval violations found: 0;
  • forced-propagation contradictions found: 0;
  • minimum interval slack: 0;
  • zero lower-slack elements: 65;
  • zero upper-slack elements: 65;
  • forced-one antichain total: 75;
  • forced-zero antichain total: 75.

The induced critical-subposet problem has 123 closure elements. Both the binary ILP and its fractional LP relaxation solve optimally:

  • binary ILP variables: 6150;
  • binary ILP monotonicity constraints: 222500;
  • binary ILP status: Optimal;
  • fractional LP status: Optimal.

This is a genuine strengthening beyond pairwise closure: it uses all closure elements for the interval/Hall scan and all zero-slack forced elements for the critical ILP.

The controls calibrate the test:

  • the toy submodularity control has closure size 4 and solves optimally;
  • the six-qubit representable control has domain closure size 35,664, but its fan certificate fails the forced-propagation test and the critical binary/fractional programs are infeasible.

The six-qubit failure is not a contradiction. It means the six-qubit fan certificate does not lift to this operation-level invariant, which is exactly what [[fan-cone-certificates-are-not-hidden-vertex-invariants.md]] predicts for a known hidden-vertex-representable function.

Therefore the current full-closure diagnostics are nontrivial and correctly reject at least one cone-specific certificate, but they still do not decide the f_3 certificate.

Dependencies

  • [[full-rank-order-closure-reduces-to-pattern-upset-lattice.md]]
  • [[f3-certificate-passes-pairwise-rank-order-extension-but-not-full-closure.md]]
  • [[fan-cone-certificates-are-not-hidden-vertex-invariants.md]]
  • [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]]

Conflicts/Gaps

  • The critical-subposet ILP is a necessary restriction, not the full monotone label-function problem.
  • No operation map is extracted for f_3.
  • No infeasibility certificate is found for f_3.
  • The result narrows the obstruction side to a larger monotone count-decomposition problem rather than closing it.

Sources

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