Skip to content

Low-Order Gluing Does Not Explain High Intrinsic Width

Claim/Theorem

Low-order binary-code or matroid gluing by 1-sums, 2-sums, and nonminimal 3-sums is exactly the constant-connectivity regime, and therefore cannot be the load-bearing positive mechanism for the compiler-native Conjecture-3 frontier.

More precisely:

  1. exact 2-separations are exactly 2-sums, equivalently cuts with
\[ \chi_L(\mathcal S)=1; \]
  1. nonminimal exact 3-separations are exactly 3-sums or dual 3-sums, equivalently cuts with
\[ \chi_L(\mathcal S)=2; \]
  1. if a binary matroid has large branchwidth, then after peeling away all such low-order gluing artifacts one still obtains a weakly 4-connected minor of comparable width, so the genuinely hard regime begins only once these \chi=1,2 decompositions are gone.

Therefore any positive hidden-vertex theorem based only on closing the threshold-lift class under 2-sum, 3-sum, or other low-order gluing operations would still remain trapped in the constant-connectivity zone. Such a theorem would not materially advance the compiler-native routing frontier, whose unresolved part starts only after passing beyond these low-order decomposition interfaces.

This is a derived obstruction statement.

  1. By [[exact-2-separation-is-2-sum.md]], an exact 2-separation is equivalent to a 2-sum decomposition, and by [[cross-cut-stabilizer-rank-rank-formula.md]] this is exactly the cut-rank \chi=1 case.
  2. By [[nonminimal-exact-3-separation-is-3-sum.md]], a nonminimal exact 3-separation is equivalent to a 3-sum or dual 3-sum decomposition, again translating under [[cross-cut-stabilizer-rank-rank-formula.md]] to the cut-rank \chi=2 case.
  3. By [[internally-4-connected-forces-cut-rank-at-least-three.md]], once one excludes these low-order exact decompositions, every nonminimal cut already lies in the next regime
\[ \chi_L(\mathcal S)\ge 3. \]

So the unresolved structural problem begins strictly above the 2-sum/3-sum level. 4. By [[large-tangle-yields-weakly-4-connected-minor.md]], any matroid of branchwidth at least k>=4 has a weakly 4-connected minor of branchwidth at least k. Thus large intrinsic width can be concentrated after stripping away low-order separations. 5. In particular, by [[good-codes-have-weakly-4-connected-log-branchwidth-minor.md]], every asymptotically good code already has a weakly 4-connected minor with branchwidth \Omega(n/\log n). So even in the good-code regime, the asymptotically meaningful width is not created by recursive 1-/2-/3-sum assembly; it survives after those decomposition artifacts are removed. 6. Therefore low-order gluing can at best explain how to assemble hidden-vertex representable pieces across constant-order interfaces. It cannot by itself explain the high-width core that must ultimately feed any routing-style lower bound.

Consequences for the current frontier:

  • the new direct-sum theorem in [[direct-sums-of-threshold-lift-pieces-stay-hidden-vertex-representable.md]] is a real positive extension, but it is still only 1-sum closure;
  • extending hidden-vertex representability to 2-sums or 3-sums would still only cover the \chi=1,2 interface regime already classified by the graph;
  • any substantive advance toward compiler-native routing lower bounds must therefore come from the connectivity->=3 core, not from more elaborate low-order sum bookkeeping.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[exact-2-separation-is-2-sum.md]]
  • [[nonminimal-exact-3-separation-is-3-sum.md]]
  • [[internally-4-connected-forces-cut-rank-at-least-three.md]]
  • [[large-tangle-yields-weakly-4-connected-minor.md]]
  • [[good-codes-have-weakly-4-connected-log-branchwidth-minor.md]]
  • [[direct-sums-of-threshold-lift-pieces-stay-hidden-vertex-representable.md]]

Conflicts/Gaps

  • This node is an obstruction to the usefulness of low-order gluing for the frontier, not an impossibility theorem for hidden-vertex representability under 2-sums or 3-sums themselves.
  • The argument uses branchwidth and weakly 4-connected minors to isolate where the interesting regime begins; it does not yet produce a linear balanced-cut-rank theorem for that core.
  • The node therefore sharpens the target of the next search but does not close the routing-style CD(T_n,G) gap.

Sources

  • 10.48550/arXiv.2109.14599
  • Kashyap 2008 preprint: A Decomposition Theory for Binary Linear Codes
  • 10.1016/j.jctb.2007.10.008
  • 10.37236/12467
  • 10.48550/arXiv.0805.2199