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

For any positive integer q≥ 2 and any real number δ∈(0,1), let αq(n,δ n) denote the maximum size of a subset of Zqⁿ with minimum Hamming distance at least δ n, where Zq=\0,1,,q-1\ and n. The asymptotic rate function is defined by Rq(δ) = n→∞1/nlogqαq(n,δ n). The famous q-ary asymptotic Gilbert-Varshamov bound, obtained in the 1950s, states that \[ R_q(δ) ≥ 1 - δlog_q(q-1)-δlog_q1/δ-(1-δ)log_q1/1-δ {def}{=}R_GV(δ,q) \] for all positive integers q≥ 2 and 0<δ<1-q⁻¹. In the case that q is an even power of a prime with q≥ 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. The further investigation in algebraic geometry codes has shown that the q-ary Gilbert-Varshamov bound can also be improved in the case that q is an odd power of a prime but not a prime with $q > 125$. However, it remains a long-standing open problem whether the q-ary Gilbert-Varshamov bound would be tight for those infinitely many integers q which is a prime, except for Fermat primes not less than 257, and which is a generic positive integer not being a prime power. In this paper, we prove that the q-ary Gilbert-Varshamov bound can be improved for all but finitely many positive integers q≥ 2. It is shown that Rq(1/2) > RGV(1/2,q) for all integers q > exp(29). Furthermore, we show that the growth of the rate function Rq(δ) for δ∈(0,1) fixed and q growing large has a nontrivial lower bound. These new lower bounds are achieved by using codes from geometry of numbers introduced by Lenstra in the 1980s.