Skip to content

Exact 2-Separation Is 2-Sum Decomposition

Claim/Theorem

Let \(C\) be a binary linear code on coordinate set \(I\), and let

\[ I = J \sqcup J^c \]

with

\[ \min\{|J|,|J^c|\}\ge 2. \]

Then the following are equivalent:

  1. \((J,J^c)\) is an exact \(2\)-separation of \(C\).
  2. The code connectivity across the cut is
\[ \lambda_C(J)=1. \]
  1. There exist codes \(C_1\) and \(C_2\), each equivalent to proper minors of \(C\), such that
\[ C \cong C_1 \oplus_2 C_2. \]

So exact cut rank 1 is not just a weak interface. It is exactly a binary-code \(2\)-sum decomposition into proper minors.

Via [[cross-cut-stabilizer-rank-rank-formula.md]], the same statement can be rewritten for a stabilizer space \(\mathcal S\) represented by a full-row-rank matrix \(H\) with kernel \(C=\ker H\):

\[ \chi_J(\mathcal S)=1 \]

is equivalent to an exact \(2\)-separation of the associated binary code and hence to a \(2\)-sum decomposition.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]

Conflicts/Gaps

  • This theorem is exact and low-order. It does not address cuts with \(\lambda_C(J)\ge 2\).
  • It concerns the binary code associated with a chosen stabilizer matrix. Turning it into a statement about arbitrary compilers still requires [[stabilizer-cut-rank-functional.md]].
  • Excluding \(2\)-sums only yields the constant lower bound \(\chi_J(\mathcal S)\ge 2\), which is far weaker than the linear connectivity sought in Conjecture 3.

Sources

  • Kashyap 2008 preprint: A Decomposition Theory for Binary Linear Codes