Paper 2026/2245

An improved near-capacity lower bound for Reed-Solomon lists on multiplicative subgroups

Abstract

We give an elementary construction of large Reed-Solomon lists on multiplicative subgroups. For every fixed rational rate $\rho\in(0,1)$, suitable sequences of lengths give lists of size at least $2^{(2-o(1))H(\rho)/\eta}$ at agreement fraction $\rho+\eta$ as $\eta\to0$, where $H$ is binary entropy. This doubles the leading entropy exponent of the antipodal lower bound stated by Arnon, Boneh, and Fenzi, building on the construction of Krachun, Kazanin, and Haböck. If the reduced denominator of $\rho$ is a power of two, the lengths can also be chosen as powers of two. The construction lifts subsets with a prescribed product from a quotient subgroup of size $s$. This fixes a coefficient while losing at most a factor $s$ in the number of subsets. More precisely, for $n=hs$, $h\ge2$, and $1\le m\le s-2$, a code of dimension $\kappa=mh$ on a subgroup of order $n$ has a word with at least $\binom{s-1}{m+1}/s$ codewords at agreement $\kappa+2h-1$. This holds over every field containing the required roots of unity. Consequently, the exponent constant $c_2$ in the universal list-size conjecture of the S-two whitepaper must satisfy $c_2\ge2$.