Gilbert-Varshamov Bound

The Gilbert-Varshamov bound is an existence bound for error-correcting codes with prescribed minimum Hamming distance. For integers and , if is the largest size of a -ary length- code of minimum Hamming distance at least , then

(1)

where is the number of words in a radius- Hamming ball. The greedy construction chooses a codeword and removes all words at Hamming distance less than , then repeats. The Gilbert bound and its linear code refinement provide the classical asymptotic rate (Gilbert 1952, Varshamov 1957). Here is the -ary entropy function.

Fix a prime power and , and put , where is the floor function. Yuan and Zhu (2026) proved that, for all sufficiently large , a -ary linear code of minimum Hamming distance at least exists with size

(2)

where denotes big-omega notation. This improves the finite-length existence bound by a factor of order , but does not change the leading asymptotic rate or supply an efficient explicit construction.

For stabilizer codes, Yuan and Zhu (2026) obtained a corresponding factor- improvement under and the additional restriction . For , a -ary stabilizer code with parameters , , exists for sufficiently large when

(3)

where depends only on and . Here is the dimension of the associated symplectic self-orthogonal linear code, while is the number of logical -level systems.