Conservative Hamming Operation Extension Is Rank-Order Lattice Extension¶

Claim/Theorem¶

Let

\[ F:\{0,1\}^k\to\{0,1\}^k \]

be a Boolean operation, and identify a vector x with the subset X\subseteq[k] of its 1-coordinates. Then F is conservative and Hamming-distance non-increasing if and only if the induced map on the Boolean lattice is:

rank-preserving: |F(X)|=|X| for every X;
order-preserving: X\subseteq Y implies F(X)\subseteq F(Y).

Consequently, the current f_3 fan-certificate operation-extension problem is an exact finite lattice-extension problem.

Let y be the reconstructed certificate from [[f3-fan-certificate-passes-necessary-multimorphism-tests-but-not-operation-lift.md]], and write

\[ P=\{x:y_x=1\},\qquad N=\{x:y_x=-1\}. \]

Since |P|=|N|=50, each visible coordinate of the 7-ary target gives one input column

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

and one output column

\[ B_j=\{n\in N:n_j=1\}\subseteq N. \]

The candidate single-operation lift is therefore exactly:

Does there exist a rank-preserving order-preserving Boolean-lattice map F:2^P\to 2^N with F(A_j)=B_j for all seven visible coordinates?

This is the finite decision problem implemented in docs/project_QEM-QEC/tmp/scripts/route_d_operation_extension.py.

Proof¶

If F is conservative, then it is rank-preserving. If X\subset X\cup\{i\} is a cover relation, Hamming nonincrease gives

\[ d(F(X),F(X\cup\{i\}))\le 1. \]

The two images have ranks differing by one, so the only possible distance is 1, and the smaller-rank image must be contained in the larger-rank image. Thus F preserves every cover relation, hence every inclusion.

Conversely, if F is rank-preserving and order-preserving, then it maps every cover relation to a cover relation. Any two subsets are joined by a shortest Hamming path through cover moves, and the image path has length no larger. Therefore Hamming distance cannot increase.

By Zivny-Cohen-Jeavons Theorem 14, these are exactly the Boolean operations that are multimorphisms of \Gamma_{\mathrm{sub},2}. So the current certificate-lift target can be checked as a lattice-extension feasibility problem on the signed certificate support.

Dependencies¶

[[f3-fan-certificate-passes-necessary-multimorphism-tests-but-not-operation-lift.md]]
[[certificate-lift-frontier-is-operation-extension-not-cone-duality.md]]
[[source-all-arity-expressive-power-stops-before-fan-certificate-lift.md]]

Conflicts/Gaps¶

This node formalizes the exact finite operation-extension model; it does not solve the full extension instance.
The reduction applies to a single-operation multimorphism reading of y. A weighted-polymorphism decomposition could still use a nonnegative combination of several valid operation inequalities.
The lattice map has domain size 2^50, so the finite model is exact but cannot be naively enumerated.

Sources¶

10.1016/j.dam.2009.07.001
local page image: tmp/paper-bundles/zivny-2009/pages/page-0008.png
local script: docs/project_QEM-QEC/tmp/scripts/route_d_operation_extension.py