Skip to content

Full Rank-Order Closure Reduces To Pattern Upset Lattice

Claim/Theorem

For the reconstructed f_3 certificate from [[f3-fan-certificate-passes-necessary-multimorphism-tests-but-not-operation-lift.md]], the meet/join closure generated by the seven observed positive-support columns is not the full 2^50 Boolean lattice. It is exactly the upset lattice of the realized 7-bit support-pattern poset.

More generally, let P be the positive support of a signed certificate and let

\[ A_j=\{p\in P:p_j=1\} \]

be the observed domain columns. Each support point p has a pattern

\[ \alpha(p)=(\mathbf 1[p\in A_1],\ldots,\mathbf 1[p\in A_m])\in\{0,1\}^m. \]

The closure generated from the A_j by finite unions and intersections is canonically isomorphic to the family of upsets of the realized pattern set R_P=\{\alpha(p):p\in P\}, ordered by coordinatewise comparison.

For the current f_3 certificate:

  • |P|=50;
  • all 50 positive support patterns are distinct;
  • the exact domain closure size is 2,849,631;
  • the old 3001 cutoff was only an artifact of naive subset enumeration.

The same representation gives:

  • six-qubit control domain closure size 35,664;
  • toy submodularity control domain closure size 4.

Proof

Every expression in the generators A_j using only union and intersection is a positive monotone Boolean formula in the m pattern bits. Therefore its truth set on R_P is an upset.

Conversely, if U\subseteq R_P is an upset and M is the antichain of its minimal elements, then

\[ U=\bigcup_{\alpha\in M}\{\beta\in R_P:\alpha\le\beta\}. \]

For a fixed minimal pattern \alpha, the principal upset \{\beta:\alpha\le\beta\} is represented by

\[ \bigcap_{j:\alpha_j=1} A_j. \]

Taking the union over M realizes U. Hence the closure is exactly the upset lattice of the realized pattern poset.

This is the exact closure object computed by docs/project_QEM-QEC/tmp/scripts/route_d_full_rank_order_extension.py.

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

  • This node computes the exact domain closure object; it does not decide whether a rank-preserving order-preserving extension exists.
  • The codomain image of a closure element is not required to lie in the analogous codomain pattern closure, so the output-pattern closure size is diagnostic only.
  • The result compresses the closure from 2^50 to a finite 2,849,631-element lattice, but the full extension problem still has one monotone label function per negative support point.

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