Skip to content

Subfamily Union-Rank Deficiency Gives Parity Lower Bound

Claim/Theorem

Keep the notation of [[exact-optimal-quotient-family-problem-reduces-to-linear-matroid-block-packing.md]] and [[pairwise-skew-block-statistics-do-not-control-parity-value.md]]. Fix a balanced cut L \sqcup R = Q, let W_v(L) be the local quotient blocks, and for any block subfamily X define

\[ w_H(X;L):=\sum_{v\in X}\dim W_v(L), \]

and

\[ \rho_H(X;L):=\dim\Big(\sum_{v\in X} W_v(L)\Big). \]

Also write

\[ b_H(X;L):=\max_{v\in X}\dim W_v(L). \]

Then every block subfamily X contains a direct-sum subfamily F\subseteq X of total weight at least

\[ w_H(F;L)\ge w_H(X;L)-b_H(X;L)\big(w_H(X;L)-\rho_H(X;L)\big). \]

Consequently,

\[ \nu_H(L)\ge \max_X \Big( w_H(X;L)-b_H(X;L)\big(w_H(X;L)-\rho_H(X;L)\big) \Big). \]

In the parity regime \dim W_v(L)\in\{0,1,2\}, this becomes the explicit Hall/Rado-type deficiency lower bound

\[ \nu_H(L)\ge \max_X \big(2\rho_H(X;L)-w_H(X;L)\big). \]

Therefore any construction-level statement of the form

\[ \rho_H(X;L)\ge \Big(\frac{1}{2}+\varepsilon\Big) w_H(X;L) \]

for some block subfamily X with w_H(X;L)=\Omega(|Q|) immediately implies

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

and hence linear balanced intrinsic cut rank.

Proof:

  1. For a fixed block subfamily X, choose for each v\in X a basis E_v of W_v(L), and let

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

    By [[exact-optimal-quotient-family-problem-reduces-to-linear-matroid-block-packing.md]], the represented quotient matroid on E(X) has

    \[ |E(X)|=w_H(X;L), \qquad r(E(X))=\rho_H(X;L). \]

  2. Let I\subseteq E(X) be a basis of E(X). Then

    \[ |I|=\rho_H(X;L), \qquad |E(X)\setminus I|=w_H(X;L)-\rho_H(X;L). \]

  3. Call a block v\in X good if E_v\subseteq I, and bad otherwise. Every bad block contains at least one deleted element from E(X)\setminus I, so the number of bad blocks is at most

    \[ w_H(X;L)-\rho_H(X;L). \]

    Since each bad block has weight at most b_H(X;L), the total weight of all bad blocks is at most

    \[ b_H(X;L)\big(w_H(X;L)-\rho_H(X;L)\big). \]

  4. Let F\subseteq X be the good blocks. Then

    \[ w_H(F;L)\ge w_H(X;L)-b_H(X;L)\big(w_H(X;L)-\rho_H(X;L)\big). \]

    Moreover,

    \[ \bigsqcup_{v\in F} E_v \subseteq I \]

    is independent, so F is a direct-sum block family. Hence w_H(F;L)\le \nu_H(L), proving the bound.

This gives the first quantitative union-rank criterion on the current parity frontier:

  • it is mathematically sufficient in general;
  • it does not rely on pairwise skewness;
  • it shows that the real missing construction-level object is a large low-deficiency block subfamily.

The current explicit low-cut Quantum Tanner data show exactly why this is still not visible from the present construction-level information:

  • D_4: taking X to be the full visible low-cut block family gives

    \[ w_H(X;L)=\sigma_H(L)=16, \qquad \rho_H(X;L)=\lambda_{M(H)}(L)=5, \]

    so

    \[ 2\rho_H(X;L)-w_H(X;L)=-6. \]

  • D_6: on the current low-cut witness,

    \[ w_H(X;L)=35, \qquad \rho_H(X;L)=12, \]

    so

    \[ 2\rho_H(X;L)-w_H(X;L)=-11. \]

  • D_8: on the current low-cut witness,

    \[ w_H(X;L)=34, \qquad \rho_H(X;L)=12, \]

    so

    \[ 2\rho_H(X;L)-w_H(X;L)=-10. \]

So the full low-cut block families already exhibit a specific higher-order concentration mechanism: their total block weight collapses into fewer than half as many quotient directions. The general deficiency lower bound is therefore numerically trivial on the whole visible family, even though it is exact on the optimized witness subfamilies from [[nu-saturation-yields-adapted-triangular-basis.md]].

This isolates the next missing invariant more sharply than the pairwise-obstruction node:

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

for every \beta-balanced cut L, there is a construction-controlled block subfamily X with

\[ w_H(X;L)=\Omega(|Q|) \]

and

\[ \rho_H(X;L)\ge \Big(\frac{1}{2}+\varepsilon\Big) w_H(X;L) \]

for some fixed \varepsilon>0.

Under H_{\mathrm{def}}(\beta), the parity lower bound above immediately gives \nu_H(L)=\Omega(|Q|).

Dependencies

  • [[exact-optimal-quotient-family-problem-reduces-to-linear-matroid-block-packing.md]]
  • [[pairwise-skew-block-statistics-do-not-control-parity-value.md]]
  • [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]]
  • [[local-quotient-image-span-controls-rank-accumulation.md]]
  • [[nu-saturation-yields-adapted-triangular-basis.md]]

Conflicts/Gaps

  • This node gives a rigorous lower-bound criterion, but not yet a family theorem for Quantum Tanner cuts. It does not show how to find the large low-deficiency subfamily X from the construction.
  • The aggregate low-cut D_4, D_6, and D_8 data show that taking X to be the whole visible block family is far too crude: the resulting deficiency bound is trivial.
  • The exact optimized witness families do satisfy zero-deficiency saturation, but only after exact global optimization; that does not yet amount to a construction-controlled invariant.
  • So the remaining gap is now precise: identify a construction-grounded rule that exposes a large block subfamily with union-rank density strictly above 1/2.

Sources

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