Skip to content

Route D Count Decomposition Now Requires Higher-Arity Toggle Generator

Claim/Theorem

After the monotone count-decomposition closure cycle, the Route-D operation-lift frontier is not closed, but it is narrower: the next theorem-level target is a higher-arity conservative generator class capable of deciding the coordinate-0 toggle boundary from [[f3-count-decomposition-is-coordinate-zero-toggle-boundary.md]].

The strongest supported statement is:

The current f_3 certificate survives all interval/Hall, forced-propagation, critical ILP/LP, principal-filter, ordinary meet/join, independent interval-fill, and rank-greedy extension tests on the full 2,849,631-element closure; deciding the certificate now requires either a full column-generation dual certificate or a finite higher-arity generator basis for monotone count decompositions.

The exact generator target is no longer generic. It should have:

  • arity at least 3 beyond ordinary binary meet/join sorting;
  • operation type: conservative Hamming-nonincreasing Boolean operations whose coordinate label functions are arbitrary upsets of L_P;
  • validity test: verify the candidate operations against \Gamma_{\mathrm{sub},2} using the Zivny-Cohen-Jeavons conservative Hamming-nonincreasing criterion from Theorem 14;
  • application test: decide whether the generated rank-preserving monotone count maps realize the coordinate-0 toggle boundary while preserving generators 1,\ldots,6.

The replacement-certificate route does not currently dominate this target. The bound-1, bound-2, bound-3, and bound-4 strict-Hamming searches found feasible continuous relaxations, but the integer searches did not solve within their configured limits, and the ordinary meet/join decomposition LP remains infeasible. Thus no stronger integer certificate has replaced the present y.

The constructive nonseparable hidden-energy route remains secondary. The count-decomposition obstruction route has not failed theorem-level; it has only reached an exact higher-arity generator problem.

Dependencies

  • [[f3-count-decomposition-is-coordinate-zero-toggle-boundary.md]]
  • [[monotone-count-decomposition-is-column-generation-not-single-flow.md]]
  • [[route-d-full-rank-order-frontier-is-monotone-count-decomposition.md]]
  • [[strict-hamming-replacement-and-meet-join-decomposition-do-not-close-certificate-lift.md]]
  • [[beyond-fan-cone-construction-requires-nonseparable-selected-threshold-energy.md]]

Conflicts/Gaps

  • The monotone count-decomposition instance remains unresolved.
  • No finite higher-arity generator basis is currently known for the relevant conservative Hamming-nonincreasing operations.
  • No proof shows that the column-generation formulation is integral or admits a small complete dual family.
  • The nonseparable construction route is not refuted; it is only not promoted by this run.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • local computation: docs/project_QEM-QEC/tmp/certificates/monotone_count_decomposition_report.json
  • local computation: docs/project_QEM-QEC/tmp/certificates/certificate_replacement_report.json
  • local computation: docs/project_QEM-QEC/tmp/certificates/certificate_replacement_bound3_report.json
  • local computation: docs/project_QEM-QEC/tmp/certificates/certificate_replacement_bound4_report.json
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_monotone_count_decomposition.py