Gilbert–Varshamov Bound for Codes in <i>L</i>₁ Metric Using Multivariate Analytic Combinatorics

Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert-Varshamov lower bound on the rate of optimal codes in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$L_{1}$ </tex-math></inline-formula> metric. Several different code spaces are analyzed, including the simplex and the hypercube in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathbb {Z}}^{n}$ </tex-math></inline-formula>, all of which are inspired by concrete data storage and transmission models such as the permutation channel, the repetition channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc.