SODA Conference 2023 Conference Paper
Nonlinear codes exceeding the Gilbert-Varshamov and Tsfasman-Vlăduţ-Zink bounds
- Shu Liu 0004
- Tingyi Wu
- Chaoping Xing
The Gilbert-Varshamov (GV for short) bound has been a benchmark for good Hamming-metric codes. It was even conjectured by some coding theorists that the asymptotic Gilbert-Varshamov bound is tight. The GV bound had remained to be the best asymptotic lower bound for thirty years before it was broken by the Tsfasman-Vlăduţ-Zink bound via algebraic geometry codes. The discovery of algebraic geometry codes by Goppa was a breakthrough in coding theory. After another twenty years, no any improvements on the Tsfasman-Vlăduţ-Zink bound took place before the work by Xing-Elkies [14, 15, 1, 2] in the early of 2000 via tools from algebraic geometry. By using the similar ideas as in [14, 15, 9], some further improvements were given in [7, 17]. Since then, no further progress on asymptotic lower bounds has been made. The main result of this paper is to show that all previous asymptotic lower bounds can be improved in an interval. We present two types of constructions of Hamming-metric codes. Both constructions involve algebraic geometry and need insights on applications of algebraic geometry to coding theory. In order to obtain good codes, one construction requires a larger number of positive divisors of fixed degree, while other construction requires a smaller number of positive divisors of fixed degree. As a result, no matter how large the number of positive divisors of fixed degree is, we can always obtain codes with good parameters. It turns out that all previous asymptotic lower bounds are improved.