Exact leading coefficient of maxcode_L even L
Informal Conjecture on exact asymptotics of maxcode_L for even L · arXiv:1710.10663
Status open medium confidence
The source paper (Theorem 2) already established the lower bound $\mathrm{maxcode}_L(\varepsilon) \geq c_L\varepsilon^{-1}+O(1)$ for even $L$; the conjecture asks whether the matching upper bound also has leading constant $c_L$. A 2023/2025 follow-up by Resch, Yuan, and Zhang (arXiv:2309.01800, ITCS 2025) proves tight $\Theta(1/\varepsilon)$ bounds for list-decodable and list-recoverable zero-rate codes over general alphabets with unspecified constants, extending the Alon--Bukh--Polyanskiy framework but not addressing the exact leading constant $c_L$ for the binary even-$L$ case. No paper in the indexed literature appears to resolve the exact-constant question.
Cited literature (1)
-
Proves matching upper and lower bounds of $\Theta_{q,\ell,L}(1/\varepsilon)$ for zero-rate list-decodable and list-recoverable codes over general alphabets, generalising Alon--Bukh--Polyanskiy to $q\geq 3$ and arbitrary list sizes, but the constants absorbed in $\Theta_{q,\ell,L}$ are not identified as $c_L$ for the binary even-$L$ case.
Reviewer notes. The closest follow-up, Resch--Yuan--Zhang (arXiv:2309.01800), proves tight-order bounds for general alphabets but does not pin down the exact binary constant $c_L=2^{-\lfloor L/2\rfloor}\binom{L}{\lfloor L/2\rfloor}$ for even $L$. The specific conjecture on the exact leading coefficient appears to remain open in the published literature as of May 2026.
Context
Theorem 2 establishes the two-sided bound $c_L \varepsilon^{-1} + O(1) \leq \mathrm{maxcode}_L(\varepsilon) = O(\varepsilon^{-1})$ for every even $L \geq 2$, where $c_L = 2^{-\lfloor L/2 \rfloor}\binom{L}{\lfloor L/2 \rfloor}$ comes from Theorem 1. The authors conjecture that the lower bound is tight up to an additive constant, i.e., that the exact leading coefficient is $c_L$.
Notes. Stated as 'We believe that in fact …' in prose immediately after Theorem 2; no labelled theorem environment. PDF source — math notation may be garbled.
Source paper
List-decodable zero-rate codes
Noga Alon, Boris Bukh, Yury Polyanskiy · 2018-05-14
https://arxiv.org/abs/1710.10663
PDF source