Exact Optimal Quotient Family Problem Reduces To Linear Matroid Block Packing

Claim/Theorem

Keep the notation of [[local-quotient-image-span-controls-rank-accumulation.md]], [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]], and [[exact-optimal-quotient-families-do-not-share-transferable-shelling-law.md]]. Fix a qubit cut L \sqcup R = Q, let

\[ W_v(L)\le \frac{S}{B(L)} \]

be the local quotient images, and set

\[ d_v:=\dim W_v(L). \]

Choose, for each v, a basis

\[ E_v=\{e_{v,1},\dots,e_{v,d_v}\} \]

of W_v(L), and let

\[ E:=\bigsqcup_v E_v. \]

Represent the vectors in E in any fixed basis of S/B(L), and let M_L be the resulting represented matroid on ground set E.

Then:

1. A block family F is direct-sum,

\[ \sum_{v\in F} W_v(L)\ \text{direct}, \]

if and only if the union of its chosen basis elements

\[ E(F):=\bigsqcup_{v\in F} E_v \]

is independent in M_L.

1. Consequently,

\[ \nu_H(L) = \max\Big\{ \sum_{v\in F} d_v : E(F)\ \text{independent in } M_L \Big\}. \]

So the exact optimal-family problem is already a standard represented-matroid block-packing problem: select whole blocks E_v of weight d_v whose union is independent in M_L.

1. If every nonzero local quotient image has dimension at most 2, then the same problem reduces to weighted linear matroid parity. Indeed, for each v with d_v=1, adjoin one fresh free element f_v and replace the singleton block E_v=\{e_v\} by the pair

\[ P_v:=\{e_v,f_v\}. \]

For each v with d_v=2, keep the pair

\[ P_v:=E_v. \]

In the augmented represented matroid

\[ M_L^+:=M_L\oplus \bigoplus_{d_v=1} U_{1,1}, \]

the family F is direct-sum exactly when

\[ \bigsqcup_{v\in F} P_v \]

is independent in M_L^+. With pair weights w(P_v)=d_v, maximizing the total weight of an independent union of pairs is therefore exactly \nu_H(L).

1. Hence every cut with local quotient dimensions in {0,1,2} yields a weighted linear matroid-parity instance. The current low-lambda explicit Quantum Tanner witnesses satisfy exactly this:

2. D_4: local quotient histogram \{0:4,1:8,2:4\};

3. D_6: \{1:13,2:11\};
4. D_8: \{0:9,1:12,2:11\}.

Therefore the present exact-optimal frontier on those three explicit cuts already reduces to weighted linear matroid parity.

1. This also separates partial resemblance from actual class membership:

2. the full exact optimal-family sets are not the maximum-weight independent sets of any ordinary matroid on the block ground set, because all block weights are positive while [[exact-optimal-quotient-families-do-not-share-transferable-shelling-law.md]] shows that the exact optimal families occupy several different cardinality strata; in a matroid, every maximum-weight independent set with strictly positive weights is a basis and hence has one common cardinality;

3. the exact optimal families are not organized by basis exchange or greedy shelling on the block ground set, by the explicit same-cardinality exchange failures and global max-gain shellability failures already recorded in that node;
4. nevertheless the problem is not unstructured: it already belongs to a standard non-greedy represented-matroid optimization class.

Therefore the exact missing invariant can be sharpened from a vague "new global optimization invariant" to the following structured version:

\[ H_{\mathrm{blk}}(\beta): \]

for every \beta-balanced cut L, the associated represented-matroid block-packing instance has optimum

\[ \nu_H(L)=\Omega(|Q|). \]

If, moreover, all nonzero W_v(L) have dimension at most 2 on the relevant family of cuts, then H_{\mathrm{blk}}(\beta) is exactly a linear lower bound on the optimum of an associated weighted linear matroid-parity instance.

Since always

\[ \nu_H(L)\le \lambda_{M(H)}(L), \]

this would immediately force linear balanced intrinsic cut rank.

Proof:

1. The direct-sum condition

\[ \sum_{v\in F} W_v(L)\ \text{direct} \]

means precisely that the concatenation of any bases of the chosen subspaces is linearly independent in S/B(L). By construction, E(F) is exactly such a concatenation, so F is feasible if and only if E(F) is independent in the represented matroid M_L.

1. The objective contribution of each chosen block is

\[ |E_v|=d_v=\dim W_v(L), \]

so maximizing the total direct-sum dimension is exactly the weighted block-packing objective above. This proves the formula for \nu_H(L).

1. When d_v\in\{1,2\}, adjoining a fresh free element to each singleton block does not create any new dependence among the original quotient vectors. Thus an augmented pair family is independent in M_L^+ if and only if the corresponding original block family is direct-sum in M_L. The weighted parity objective therefore reproduces \nu_H(L) exactly.

2. The low-cut histograms quoted above come from [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]], so those explicit D_4, D_6, and D_8 instances already lie in the parity regime.

3. The final bullets follow from combining the present reduction with the exact-optimal-family evidence already established in [[exact-optimal-quotient-families-do-not-share-transferable-shelling-law.md]].

This refines the frontier exactly:

• previous runs ruled out exchange-friendly and shelling-friendly block rules;
• the present node shows that the exact objective is still a standard matroidal packing problem;
• so the remaining gap is no longer "find any structure at all," but rather "prove a linear lower bound for this represented-matroid block-packing/parity value along balanced Quantum Tanner cuts."

Dependencies

• [[local-quotient-image-span-controls-rank-accumulation.md]]
• [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]]
• [[exact-optimal-quotient-families-do-not-share-transferable-shelling-law.md]]
• [[nu-saturation-yields-adapted-triangular-basis.md]]
• [[stabilizer-cut-rank-functional.md]]

Conflicts/Gaps

• The node gives a structural reduction, not a family-level lower bound. It does not prove \nu_H(L)=\Omega(|Q|) on balanced Quantum Tanner cuts.
• The reduction to weighted linear matroid parity uses the extra hypothesis \dim W_v(L)\le 2; this is verified on the current explicit low-cut witnesses but not yet proved uniformly across the family.
• For higher-dimensional local quotient images, the correct optimization class is the corresponding represented-matroid block-packing generalization, not necessarily ordinary parity.
• So the remaining hard step is still quantitative: prove that the associated block-packing or parity optimum is linear on all balanced cuts of the target family.

Sources

• 10.48550/arXiv.2206.07571
• 10.48550/arXiv.2508.05095
• 10.1016/0095-8956(80)90066-0
• 10.1016/j.dam.2019.09.023