Conjecture on the average number of punctures for GRS covering

Let C{\mathcal C} be an [n,k,d]q[n,k,d]_q generalized Reed–Solomon (GRS) code, and let GRS-cover\operatorname{GRS\text{-}cover} denote the covering algorithm. The average number of punctures is the expected number of coordinates punctured before the algorithm succeeds in returning a codeword within the covering radius.

Puncture-count conjecture. For an [n,k,d]q[n,k,d]_q GRS code, the average number of punctures needed for GRS-cover\operatorname{GRS\text{-}cover} to succeed in returning a codeword within the covering radius is less than

\begin{cases} c_1(d-1) & \text{when } \operatorname{GRS\text{-}decode \text{ is a unique decoder},\\ c_2 & \text{when } \operatorname{GRS\text{-}decode}=\operatorname{GS} \text{ is the list decoder}, \end{cases}

for some positive constants c1<1c_1<1 and c2c_2.

The source later states that the first part does not hold in general; the second part remains unresolved there. Thus this combined conjecture is refuted, with its list-decoder component still open.

Sources & referencesView supporting material

Primary source

Samin Riasat and Hessam Mahdavifar, “Covering in Hamming and Grassmann Spaces: New Bounds and Reed–Solomon-Based Constructions”, arXiv:2512.22911 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.