Skip to content

Route D Full Rank-Order Frontier Is Monotone Count Decomposition

Claim/Theorem

After the full-rank-order closure cycle, the remaining operation-lift problem is no longer best described as a search over 2^50 subsets. It is the following exact finite monotone count-decomposition problem.

Let L_P be the 2,849,631-element upset lattice of the realized positive support-pattern poset from [[full-rank-order-closure-reduces-to-pattern-upset-lattice.md]]. Let B be the 50 negative support patterns. For each \beta\in B, seek a monotone Boolean function

\[ h_\beta:L_P\to\{0,1\} \]

such that:

  1. for every generator A_j,

    \[ h_\beta(A_j)=\beta_j; \]

  2. for every closure element U\in L_P,

    \[ \sum_{\beta\in B} h_\beta(U)=|U|. \]

This is exactly the restriction of the rank-preserving order-preserving extension problem to the full meet/join closure generated by the observed certificate columns.

The run also rules out two weaker continuations.

First, the principal-filter generator class fails. A principal-filter decomposition is the closure-level version of assigning each output label to a single realized input support pattern. It would require equality of the domain and output pattern multisets. The report finds 100 pattern-count mismatches for f_3.

Second, ordinary meet/join submodularity generators remain too weak by [[strict-hamming-replacement-and-meet-join-decomposition-do-not-close-certificate-lift.md]]. The additional bound-3 replacement search does not change this:

  • the strict-Hamming continuous relaxation in [-3,3] is feasible;
  • the corresponding integer search is unresolved within the configured limit;
  • the meet/join decomposition LP remains infeasible.

Therefore the exact next generator class is:

arity-50 conservative Hamming-nonincreasing operations represented on the f_3 closure by monotone Boolean label functions h_\beta, or equivalently integer monotone count decompositions of the closure rank function with the prescribed generator boundary values.

This is the finite generator class that would instantiate the Zivny-Cohen-Jeavons Theorem-14 operation criterion at the current certificate support. It is also the smallest explicit continuation stronger than pairwise Hamming, principal filters, and ordinary meet/join submodularity.

The constructive side remains secondary. The only still-live constructive escape is the unrestricted nonseparable hidden energy from [[beyond-fan-cone-construction-requires-nonseparable-selected-threshold-energy.md]], because this run did not produce an operation-lift obstruction and did not find a replacement certificate that dominates the current one.

Dependencies

  • [[full-closure-hall-and-critical-ilp-do-not-refute-f3-operation-extension.md]]
  • [[strict-hamming-replacement-and-meet-join-decomposition-do-not-close-certificate-lift.md]]
  • [[route-d-operation-extension-frontier-now-reduces-to-full-rank-order-or-new-generator.md]]
  • [[beyond-fan-cone-construction-requires-nonseparable-selected-threshold-energy.md]]

Conflicts/Gaps

  • This node is a compression result, not a proof of operation-lift feasibility or infeasibility.
  • The monotone count-decomposition instance is still large: it has 50 monotone Boolean label functions over a 2,849,631-element closure lattice.
  • A future run must either solve this monotone count-decomposition instance, extract a Hall/duality obstruction for it, or replace the certificate by one that fails earlier.

Sources

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