A $Θ(n)$-Multiplicative Improvement of the Gilbert-Varshamov Bound for Linear and Quantum Codes

The Gilbert-Varshamov (GV) bound is a fundamental benchmark for the existence of error-correcting codes. For non-linear q-ary codes of code length n, its finite length form is known to admit a multiplicative improvement of order $Θ(n)$. In contrast, for q-ary linear codes of arbitrary rates, the best previously known general improvement was only of order Θ(√ n). This leaves open whether the algebraic constraint of linearity inherently prevents a linear-order refinement. We show that it does not. For every fixed prime power q and relative distance $0<δ<1-1/q$, we obtain a $Θ(n)$-multiplicative improvement of the GV bound for q-ary linear codes of arbitrary rate, matching the corresponding result for nonlinear codes. Our proof is based on a simple change of viewpoint. Rather than requiring the initial random linear construction to contain no low-weight vectors, we allow $O(n)$ low-weight points, show that they are independent in the underlying projective space, and then eliminate all of them simultaneously at the cost of a single dimension. The key probabilistic ingredient is an exponential bound on nontrivial linear dependencies among low-weight vectors. We further show that this approach can be extended to quantum codes despite the symplectic self-orthogonality constraint. We obtain a $Θ(n)$-multiplicative improvement of the quantum GV bound for every fixed 0<δ<1-1/q² satisfying Hq²(δ)<1/2. Thus, the same $Θ(n)$ finite length improvement is applicable to both general linear structure and symplectic self-orthogonality.