Skip to content

Nonminimal Exact 3-Separation Is 3-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 4. \]

If \((J,J^c)\) is an exact \(3\)-separation of \(C\), equivalently

\[ \lambda_C(J)=2, \]

then there exist codes \(C_1\) and \(C_2\) such that

\[ C \cong C_1 \oplus_3 C_2, \]

and likewise the same conclusion holds with the dual \(3\)-sum operation \(\bar\oplus_3\).

If, in addition, \(C\) is \(3\)-connected, then the components \(C_1\) and \(C_2\) are equivalent to proper minors of \(C\).

So nonminimal exact cut rank 2 is exactly low-order code decomposition: it is a \(3\)-sum or dual \(3\)-sum across that cut.

Via [[cross-cut-stabilizer-rank-rank-formula.md]], the same interpretation applies to a stabilizer space \(\mathcal S\) with kernel code \(C=\ker H\):

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

on a nonminimal cut is exactly the low-order interface case governed by \(3\)-sum decomposition.

Dependencies

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

Conflicts/Gaps

  • The theorem requires a nonminimal cut, i.e. both sides of the partition have size at least 4.
  • Without the additional 3-connectedness assumption, the decomposition still exists but the components need not be proper minors of the original code.
  • As with [[exact-2-separation-is-2-sum.md]], this settles only the constant-order end of the connectivity problem. It does not address the linear lower bound needed for Conjecture 3.

Sources

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