Bounds on the Zero-Error List-Decoding Capacity of the q/(q – 1) Channel
Siddharth Bhandari, Jaikumar Radhakrishnan · IEEE Transactions on Information Theory · 2021
Let$\mathcal {X}= \{x_{1},x_{2},\ldots, x_{q}\}$and let$n(m,q,\ell)$be the smallest$n$for which there is a code$C \subseteq \mathcal {X} ^{n}$of$m$elements such that for every list$w_{1}, w_{2}, \ldots, w_{\ell +1}$of distinct codewords from$C$, there is a coordinate$j \in [n]$such that$\{w_{1}[j], w_{2}[j], \ldots, w_{\ell +1}[j]\} = \mathcal {X}$. We show that there is a constant$A>0$such that for$\epsilon q^{5}$), we have$n(m,q, \lceil \epsilon q\ln {q}\rceil) \geq \exp {(Aq^{1-5\epsilon })}\log _{2}{m}$. This bound has consequences for the zero-error list-decoding capacity of the$q/(q-1)$channel studied by Elias (1988). Our result implies that for$A$and$\epsilon $as above, the zero-error list-decoding capacity of the$q/(q-1)$channel with list-size$\epsilon q\ln {q}$is at most$\exp (-Aq^{1-5\epsilon })$, that is, it falls exponentially as$q$increases. This confirms a conjecture of Chakrabortyet al.(2006).