Skip to content

Tail-Conditioned Toggle-Interface 3-Sorter Is Next Generator-Basis Target

Claim/Theorem

If the sparse column-generation route remains unresolved, the smallest concrete higher-arity generator class now worth testing is the finite class of tail-conditioned toggle-interface 3-sorters.

The class has arity 3. Its intended operation form is:

  • preserve the six-bit tail coordinates 1,\ldots,6;
  • act on coordinate 0 by a rank-sorting rule on triples;
  • allow tail-dependent cyclic tie-breaking compatible with the visible order-3 coordinate symmetry;
  • specialize to ordinary meet/join sorting when only two inputs are used and no coordinate-0 tie-breaking table is active.

The validity test is finite: enumerate the candidate operation tables on the realized 50 tail states and verify that the induced subset map is rank-preserving and order-preserving. By Zivny-Cohen-Jeavons Theorem 14, this is exactly the conservative Hamming-nonincreasing test for \Gamma_{\mathrm{sub},2}.

The boundary test is also finite: for each orbit-compatible tie-breaking table, compute the induced boundary-compatible monotone label-upsets and test whether their conic or integer closure realizes the coordinate-0 toggle count equations.

This target is sharper than saying "higher-arity generators" generically. It uses the new facts that:

  • the f_3 support has exactly 50 realized six-bit tails;
  • no realized tail appears with both coordinate-0 values;
  • the preserved-coordinate boundary is the source of the non-transport coupling;
  • the visible coordinate symmetry has order 3.

Dependencies

  • [[coordinate-zero-toggle-is-not-single-interface-transport.md]]
  • [[toggle-branch-price-sparse-dual-formulation.md]]
  • [[route-d-count-decomposition-now-requires-higher-arity-toggle-generator.md]]
  • [[strict-hamming-replacement-and-meet-join-decomposition-do-not-close-certificate-lift.md]]

Conflicts/Gaps

  • This is a concrete generator-basis target, not a proved complete basis.
  • The missing theorem is completeness: no current source proves that tail-conditioned 3-sorters generate every boundary-compatible monotone count decomposition.
  • Replacement-certificate search should remain secondary until this or another concrete generator class supplies an integer branch worth targeting.

Sources

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