Good Codes Admit Logarithmic-Width Lean Decomposition¶

Claim/Theorem¶

Let \(C\) be an [n,k,d] binary linear code and let \(M_C\) be its associated binary matroid. Then \(M_C\) admits a lean tree-decomposition of width

\[ \Omega\!\left(\frac{k(d-1)}{n\log n}\right). \]

In particular, every asymptotically good code family admits a lean tree-decomposition of width Omega(n/log n).

Proof chain on the graph:

[[good-codes-have-logarithmic-matroid-treewidth.md]] gives

\[ \operatorname{tw}(M_C)\in \Omega\!\left(\frac{k(d-1)}{n\log n}\right). \]

[[every-matroid-admits-optimal-lean-tree-decomposition.md]] upgrades an optimal tree-decomposition of width \(\operatorname{tw}(M_C)\) to a lean one at the same width.
[[lean-matroid-bag-gives-rank-connected-set.md]] then shows that every bag in such a decomposition is already a rank-connected set.

So the intrinsic frontier is now concentrated very sharply:

large width is present in the original code matroid,
it can be represented inside an optimal lean decomposition,
every bag is already a local connectivity object,

and the missing theorem is specifically a concentration theorem saying that some bag has sufficiently large rank, or that the same width can be converted into a dense connected set or a hardware-balanced displayed cut.

Dependencies¶

[[good-codes-have-logarithmic-matroid-treewidth.md]]
[[every-matroid-admits-optimal-lean-tree-decomposition.md]]
[[lean-matroid-bag-gives-rank-connected-set.md]]

Conflicts/Gaps¶

The theorem does not guarantee that any bag has rank Omega(n/log n). That is now the exact missing quantitative step in this route.
Even if one bag had large rank, Conjecture 3 would still need either density or a hardware-alignment bridge to turn that bag-local object into a balanced-cut lower bound.

Sources¶

10.48550/arXiv.0805.2199
10.48550/arXiv.0711.1383
10.1016/j.ejc.2006.06.005
10.1016/j.jctb.2017.12.001