The Covering Radius of the Reed--Muller Code RM(1,9) is 242
Qichun Wang, Yueying Lou, Zifan Wang
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.