Skip to content

Strict Hamming Replacement And Meet-Join Decomposition Do Not Close Certificate Lift

Claim/Theorem

The replacement-certificate and weighted-decomposition fallback in docs/project_QEM-QEC/tmp/scripts/route_d_certificate_replacement.py sharpens but does not close the certificate-lift route.

The original f_3 certificate has:

  • coefficient set {-1,0,1};
  • support 100;
  • target dot value -10;
  • minimum pairwise Hamming defect 0.

The strict replacement search imposed the same modular and fan-cone constraints, plus strict pairwise Hamming margin at least 1.

Results:

  • the continuous relaxation in coefficient box [-1,1] is feasible, with objective approximately -9 and minimum raw Hamming defect 1;
  • the continuous relaxation in coefficient box [-2,2] is feasible, with objective approximately -19 and minimum raw Hamming defect approximately 1;
  • the corresponding integer MILPs in boxes [-1,1] and [-2,2] did not solve within the configured limit.

Therefore the linear fan/Hamming system itself does not explain why the original certificate fails to lift: fractional strict-margin certificates exist. The remaining obstruction is integrality, full operation extension, or the absence of the right weighted-polymorphism generator class.

The finite weighted-decomposition test also rules out the simplest pool. The script generated all 6069 ordinary meet/join submodularity inequality vectors on the seven visible variables and solved

\[ y=\sum_i \lambda_i g_i,\qquad \lambda_i\ge 0. \]

That LP is infeasible. This is consistent with the fact that f_3 itself is submodular, so no nonnegative combination of ordinary meet/join submodularity inequalities can certify y\cdot f_3<0.

Thus the current certificate cannot be explained by the meet/join pool alone, but the full weighted-polymorphism route remains open because Zivny-Cohen-Jeavons Theorem 14 permits all conservative Hamming-nonincreasing operations, not only the binary meet/join multimorphism.

Dependencies

  • [[conservative-hamming-operation-extension-is-rank-order-lattice-extension.md]]
  • [[f3-certificate-passes-pairwise-rank-order-extension-but-not-full-closure.md]]
  • [[certificate-lift-frontier-is-operation-extension-not-cone-duality.md]]

Conflicts/Gaps

  • The integer strict-margin replacement searches timed out; they are not infeasibility proofs.
  • The meet/join decomposition LP is only a finite pool test. It does not rule out decomposition into higher-arity conservative Hamming-nonincreasing operation inequalities.
  • Fractional strict-margin feasibility suggests that a better certificate may exist, but the current run did not produce an integer replacement certificate.

Sources

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