← 研踪 PaperTrailarXiv:2611.16447 · v1
A $Θ(n)$-Multiplicative Improvement of the Gilbert-Varshamov Bound for Linear and Quantum Codes
首次提交 2026-11-12 16:01
版本更新 2026-11-12 16:01
雷达观测 2026-11-13 14:15
摘要
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 $Θ(\sqrt 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^2$ satisfying $H_{q^2}(δ)<1/2$. Thus, the same $Θ(n)$ finite length improvement is applicable to both general linear structure and symplectic self-orthogonality.
作者备注：20 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-12 16:01 · 最新观测版本
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 $Θ(\sqrt 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^2$ satisfying $H_{q^2}(δ)<1/2$. Thus, the same $Θ(n)$ finite length improvement is applicable to both general linear structure and symplectic self-orthogonality.
查看此版本解读 →查看此版本原文 ↗