CS Paper Radar

The covering radius of RM(1,9) is precisely 242

Xiang-Dong Hou, Evelyn Sabo, Freeman Slaughter

cs.IT math.CO ·submitted 2026-10-15 16:33 UTC · v1
code/data

Abstract

Let $\text{RM}(r,n)$ be the $r$th order Reed-Mullet code of length $2^n$, and let $ρ(r,n)$ denote its covering radius. It is known that $242\leρ(1,9)\le 244$, and the determination of $ρ(1,9)$ is a long-standing open question. We give a computer-assisted proof that $ρ(1,9)=242$, leveraging the classification of the $349$ orbits in $\text{RM}(3,9)/\text{RM}(2,9)$ under $\text{GL}(9,2)$ [1,3]. The notebook to verify the computer search portion, Verify_RM(1,9).ipynb, contains all data and recomputes each check, and may be found in the repository https://github.com/FreemanSlaughter/Covering-Radius.

Comment
9 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes

cs.IT math.CO ·2026-08-31 ·Maosheng Xiong, Chi Hoi Yip, Ferdinando Zullo
theoryhighly cited similarity 0.61
Abstract

Fix integers $e\ge2$ and $r\ge1$. In this paper we study the $r$-th generalized covering radius $ρ_r\left(BCH(e,m)\right)$ of the binary primitive $e$-error-correcting BCH code $BCH(e,m)$. By using an algebraic-geometric reformulation of the covering problem together with an explicit Lang-Weil estimate, we prove that \[ρ_r\bigl(\BCH(e,m)\bigr)\le(r+1)e-1\] for all sufficiently large $m$. For $e\ge7$, this improves a recent result of Belinsky--Zabokritskiy. Our proof gives a substantially simpler geometric approach to this upper bound. In particular it implies that \[ρ_2\bigl(BCH(e,m)\bigr)=3e-1\] for all sufficiently large $m$. Previously it was only known that \[ρ_2\bigl(\BCH(e,m)\bigr) \in \left\{3e-1,3e\right\}\] for all sufficiently large $m$.

0.44

Further results on binary linear covering codes and saturating sets in projective spaces

cs.IT math.CO ·2026-09-13 ·Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco, Stephen Wu
similarity 0.61
Abstract · 33 pages

The binary length function $\ell_2(r,R)$ is the smallest length of a binary linear code with codimension (redundancy) $r$ and covering radius $R$. Let $s_2(N,ρ)$ be the smallest size of a $ρ$-saturating set in the binary projective space $\mathrm{PG}(N,2)$. It is known that the binary length function satisfies $\ell_2(r,R)=s_2(r-1,R-1)$. We obtain the following new upper bounds on $\ell_2(r,R)$, improving the previously known upper bounds by $Δ(r,R)$: $R=2,r=2t\ge28$, and $r=10,18,20$, $\ell_2(r,2)=s_2(r-1,1)\le51\cdot2^{r/2-5}-1,Δ(r,2)=2^{r/2-5}$; $R=3,r=3t-1\ge41$ and $r=26$, $\ell_2(r,3)=s_2(r-1,2)\le818\cdot2^{(r-26)/3}-1$, $Δ(41,3)=63,Δ(r,3)=2^{(r-26)/3}$ if $r\ge44$. To obtain these bounds, we construct new infinite code families, using distinct versions of the $q^m$-concatenating constructions of covering codes, including new versions proposed in this paper. We also obtain new useful partitions of column sets of parity check matrices of some codes. The new code families provide the asymptotic covering-density bounds $\overlineμ(2)\le2601/2048<1.27002$, $\overlineμ(3)\le1.35935$, improving the previously known bounds and giving rise to the new upper bounds $f(2)\le2601/2048<1.27002$, $f(3)\le1.35935$ on the constants $f(2),f(3)$ of the Green's Open Problem 40.

0.17

The Covering Radius of the Reed--Muller Code RM(1,9) is 242

cs.IT ·2026-10-13 ·Qichun Wang, Yueying Lou, Zifan Wang
similarity 0.59
Abstract

What is the covering radius of the Reed--Muller code RM(1,9) ? This is a long-standing open problem in cryptography and coding theory. In this paper, we resolve this problem, and prove that the covering radius of RM(1,9) is 242. We exclude nonlinearity 244 by obtaining a cubic Boolean function achieving a sharp Walsh $\ell^1$ bound. Its equality cases reduce either to an impossible cubic hyperplane restriction or to two homogeneous cubic forms in the Brier--Langevin classification. To exclude nonlinearity 243, we deduce the inequality ${\Vert W_g\Vert }_{1}+2|W_g(0)|\le 10368$, and then reduce either to a spectrum bounded by 24 or to the same expression to be at least 10496.

0.44

On the Existence of Complete Coverings of Lee Spheres

cs.IT ·2026-10-26 ·Jing Zhang, Yue Zhou
theory similarity 0.57
Abstract

Every perfect $r$-error-correcting Lee code in $\mathbb{Z}^n$ induces a finite configuration around each codeword: a family of pairwise disjoint radius-$r$ Lee spheres, all disjoint from the central sphere, that covers every lattice point at Lee distance $r+1$ from the codeword. We call such a configuration a complete covering. Under projection onto a suitable Cartesian product of cycles, a complete covering corresponds to an optimal local structure in the sense of Špacapan. The existence of a complete covering is necessary but, in general, not sufficient for the existence of a perfect Lee code, as our construction for $(n,r)=(3,2)$ shows. We prove that no complete covering exists whenever $n\ge 8$ and $r^2+\lfloor 25r/34\rfloor-3\ge 2n$. For the corresponding Cartesian products of cycles, this strengthens Špacapan's nonexistence theorem by replacing the linear radius condition $r\ge n$ with a threshold of order $\sqrt{2n}$. We also obtain an improved large-radius nonexistence bound for perfect Lee codes, strengthening the bound of Horak and Kim. Furthermore, we show that, for every $\varepsilon>0$, no complete covering exists when $n\ge 3$, $r$ is sufficiently large, and $r^2+(2/\mathrm{e}-\varepsilon)r\ge 2n$. On the positive side, we use near-optimal ternary constant-weight codes to construct almost complete coverings whose pairwise disjoint shadows cover a $1-o(1)$ proportion of the first outer Lee shell as the dimension tends to infinity, for every fixed radius.

0.11

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.57
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Covering 1024 syndromes with 50 columns

cs.IT math.CO ·2026-08-26 ·Stephen Wu
code/data similarity 0.56
Abstract · 8 pages. Code and verifiers at https://github.com/wustep/maths, pin problems/covering/share/2026-08-24/ at commit 736a38f

We exhibit a binary linear $[50,40]_2$ code of covering radius $2$, so $\ell_2(10,2)\le 50$, one column below the Kaikkonen--Rosendahl length $51$ that has stood since 2003 and that still seeds the $R=2$ family of Davydov--Marcugini--Pambianco (arXiv:2511.02542). The new matrix admits a $(2,0)$-partition into ten blocks, so Construction $\mathrm{QM}_2^2$ propagates it to exhaustively verified codes of lengths $815$ and $1631$ at $r=18$ and $r=20$, and to the family $n=51\cdot 2^{r/2-5}-1$ of asymptotic density $2601/2048$. The matrices, verifiers, and source are at https://github.com/wustep/maths, pin problems/covering/share/2026-08-24/ at commit 736a38f.

0.64

On Nearly-Perfect Covering Codes Beyond Radius One

cs.IT math.CO ·2026-08-12 ·Gabriel Sac Himelfarb, Moshe Schwartz
theory similarity 0.56
Abstract · 26 pages

We study (binary) nearly-perfect covering codes, which are codes that attain the Van Wee bound with equality. They act as the covering counterparts to nearly-perfect error-correcting codes, which attain the Johnson bound with equality. These codes have been completely classified for covering radius $R=1$. We prove that no code with $R\geq 2$ can attain the original Van Wee bound with equality, since it omits the dependence on the minimum distance of the code. We refine the bound to account for the minimum distance and show some nearly-perfect covering codes. By proving some structural properties of such codes, we prove all nearly-perfect covering codes with $R=2,3$ must be equivalent to the codes we showed. We also prove that for any $R\geq 3$, there are at most a finite number of nearly-perfect covering codes.

0.38

Identifying codes of Archimedean grids

cs.DM math.CO ·2026-10-23 ·Rudini Sampaio
theory similarity 0.55
Abstract

An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap C$ are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be $1/4$ for the triangular grid and $7/20$ for the square grid, whereas for the hexagonal grid the problem is still open, between $5/12$ and $53/126$. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is $2/3$ for the truncated hexagonal grid, $3/7$ for the truncated square grid, and $1/3$ for the trihexagonal (kagome) grid, the elongated triangular grid and the snub hexagonal grid. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between $3/7$ and $13/30$ for the truncated trihexagonal grid, between $1/3$ and $11/30$ for the rhombitrihexagonal grid, and between $2/7$ and $9/28$ for the snub square grid. As a by-product, we prove that every identifying code of a cubic graph with the slow growth property in which every vertex lies on exactly one triangle (resp. $4$-cycle) has density at least $2/3$ (resp. $3/7$).

0.34