The q-ary Gilbert-Varshamov bound can be improved for all but finitely many positive integers q

Abstract

For any positive integer $q\ge 2$ and any real number $\delta \in (0,1)$, let ${\alpha }_q(n,\delta n)$ denote the maximum size of a subset of ${\mathbb{Z}}_q^n$ with minimum Hamming distance at least $\delta n$, where ${\mathbb{Z}}_q=\{0,1,\dots ,q-1\}$ and $n\in \mathbb{N}$. The asymptotic rate function is defined by $R_q(\delta )={\mathrm{limsup}}_{n\to \infty }\frac{1}{n}{\log }_q{\alpha }_q(n,\delta n).$ The famous $q$-ary asymptotic Gilbert-Varshamov bound, obtained in the 1950s, states that \[ R_q(δ) \geq 1 - δ\log_q(q-1)-δ\log_q\frac{1}δ-(1-δ)\log_q\frac{1}{1-δ} \stackrel{\mathrm{def}}{=}R_\mathrm{GV}(δ,q) \] for all positive integers $q\ge 2$ and $0<\delta <1-q^{-1}$. In the case that $q$ is an even power of a prime with $q\ge 49$, the $q$-ary Gilbert-Varshamov bound was firstly improved by using algebraic geometry codes in the works of Tsfasman, Vladut, and Zink and of Ihara in the 1980s. These algebraic geometry codes have been modified to improve the $q$-ary Gilbert-Varshamov bound $R_{\mathrm{GV}}(\delta ,q)$ at a specific tangent point $\delta ={\delta }_0\in (0,1)$ of the curve $R_{\mathrm{GV}}(\delta ,q)$ for each given integer $q\ge 46$. However, the $q$-ary Gilbert-Varshamov bound $R_{\mathrm{GV}}(\delta ,q)$ at $\delta =1/2$, i.e., $R_{\mathrm{GV}}(1/2,q)$, remains the largest known lower bound of $R_q(1/2)$ for infinitely many positive integers $q$ which is a generic prime and which is a generic non-prime-power integer. In this paper, by using codes from geometry of numbers introduced by Lenstra in the 1980s, we prove that the $q$-ary Gilbert-Varshamov bound $R_{\mathrm{GV}}(\delta ,q)$ with $\delta \in (0,1)$ can be improved for all but finitely many positive integers $q$. It is shown that the growth defined by $\eta (\delta )={\mathrm{liminf}}_{q\to \infty }\frac{1}{\log q}\log [1-\delta -R_q(\delta ){]}^{-1}$ for every $\delta \in (0,1)$ has actually a nontrivial lower bound.

35 pages; more relevant and connected works are mentioned and referenced, with a suitable but slight adjustment for presentation in Abstract and Introduction