Skip to content

Fixed Quotient-Basis Pivot Coverage Is Too Rigid

Claim/Theorem

Keep the notation of [[local-quotient-image-span-controls-rank-accumulation.md]]. Fix a qubit cut \(L \sqcup R = Q\) and write

\[ \lambda=\lambda_{M(H)}(L)=\dim\frac{S}{B(L)}. \]

Choose a basis

\[ \mathcal Q_L=(q_1,\dots,q_\lambda) \]

of the quotient \(S/B(L)\). For each local quotient image \(W_v(L)\le S/B(L)\), represent \(W_v(L)\) in the coordinate system \(\mathcal Q_L\) and take its row-reduced echelon basis matrix \(R_v^{\mathcal Q}(L)\). Let

\[ \operatorname{Piv}_{\mathcal Q}(W_v(L)) \]

be the set of pivot columns of that row-reduced matrix, and define the fixed-basis pivot-cover number

\[ \pi_H^{\mathcal Q}(L) := \Big| \bigcup_v \operatorname{Piv}_{\mathcal Q}(W_v(L)) \Big|. \]

Then:

  1. For every fixed quotient basis \(\mathcal Q_L\),
\[ \pi_H^{\mathcal Q}(L)\le \lambda_{M(H)}(L). \]

Indeed, for each pivot column \(j\) in the union, choose one local row whose leading coordinate is \(j\). Distinct leading coordinates give linearly independent quotient vectors, so their number cannot exceed the quotient dimension.

  1. However, fixed-basis pivot coverage is too rigid to explain the small-instance Quantum Tanner evidence. In the natural quotient basis obtained by extending \(B(L)\) with a row basis of \(H\), one can have
\[ \pi_H^{\mathcal Q}(L) \ll \lambda_{M(H)}(L) \]

even when the packed surrogate still saturates the quotient:

\[ \nu_H(L)=\lambda_{M(H)}(L). \]
  1. Therefore a successful quotient-pivot theorem for the Quantum Tanner family cannot be stated merely as "many quotient coordinates appear as local pivot columns in one fixed natural quotient basis." The missing invariant must be basis-robust: it must permit a controlled basis change or triangular elimination across selected local quotient images.

The exact extra invariant now isolated is:

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

for every \(\beta\)-balanced cut \(L\), one can extract from the local quotient images a linearly large family of local quotient vectors that becomes triangular after a construction-controlled change of quotient basis.

This is strictly weaker than fixed-basis pivot coverage and is the first pivot-style statement not already contradicted by the explicit instances below.

Proof sketch:

  1. The inequality \(\pi_H^{\mathcal Q}(L)\le \lambda\) is immediate from the leading-coordinate argument above.
  2. The strict-gap examples are computational: compute the quotient basis \(\mathcal Q_L\), reduce each local image \(W_v(L)\), and count the distinct pivot columns appearing among all local row-reduced bases.
  3. Compare that number to the exact quotient dimension \(\lambda\) and the exact packed surrogate \(\nu_H(L)\) already computed in [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]].

Construction-level evidence on the current low-lambda balanced witnesses in the explicit D_4, D_6, and D_8 Quantum Tanner instances:

  • D_4 / [36,8,3]:
\[ \lambda=5,\qquad \nu=5,\qquad \pi_H^{\mathcal Q}=5. \]

So the natural quotient basis happens to expose all directions on this cut.

  • D_6 / [54,11,4]:
\[ \lambda=12,\qquad \nu=12,\qquad \pi_H^{\mathcal Q}=7. \]

So five quotient directions are missing from the natural local pivot cover even though the local images still admit a direct-sum family spanning the full quotient.

  • D_8 / [72,14,4]:
\[ \lambda=12,\qquad \nu=12,\qquad \pi_H^{\mathcal Q}=11. \]

So even here the natural pivot cover undercounts the full quotient.

The natural-basis pivot multiplicities on these same low-cut witnesses are:

  • D_4: minimum 2, maximum 4, average 3.2;
  • D_6: minimum 0, maximum 16, average 2.92;
  • D_8: minimum 0, maximum 6, average 2.83.

Thus the failure is not lack of local quotient activity, but concentration: some quotient coordinates are reused many times while others are not exposed as leading coordinates at all.

Additional sampled balanced cuts show that this is not confined to one special witness. Using the same natural quotient basis convention, sampled triples

\[ (\lambda,\pi_H^{\mathcal Q},\sigma) \]

include:

  • D_4: (10,9,27), (11,10,26);
  • D_6: (17,11,41), (19,12,46);
  • D_8: (17,14,41).

So the fixed-basis pivot-cover gap appears repeatedly even on small explicit instances.

This sharpens the live frontier:

  • [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]] showed that post-packing collapse is not the main issue on the current low-cut witnesses;
  • the present node shows that an equally natural stronger replacement, fixed-basis local pivot coverage, is already too strong and basis-dependent.

Hence the right missing invariant lies between these two extremes: not arbitrary post-hoc spanning, but not rigid fixed-coordinate pivot coverage either. It must be a basis-robust triangularization or elimination property of the local quotient images.

Dependencies

  • [[packed-quotient-images-already-attain-global-cut-rank-on-small-quantum-tanner-instances.md]]
  • [[local-quotient-image-span-controls-rank-accumulation.md]]
  • [[quantum-tanner-needs-balanced-local-block-rank-accumulation.md]]
  • [[quantum-tanner-local-generator-blowup.md]]
  • [[stabilizer-cut-rank-functional.md]]

Conflicts/Gaps

  • The obstruction is still basis-relative: it rules out one natural quotient-coordinate criterion, not every possible pivot-style criterion.
  • The present node does not yet give a positive basis-robust triangularization theorem; it only isolates the exact reason the naive fixed-basis version fails.
  • The sampled additional cuts are evidence, not exhaustive classification over the small instances.
  • What remains missing is a construction-level mechanism that chooses or controls the quotient basis well enough to make a linear pivot theorem provable.

Sources

  • 10.48550/arXiv.2206.07571
  • 10.48550/arXiv.2508.05095