Paper 2026/2529

The Covering Radius of $\text{RM}(1,9)$ is Precisely $242$

Abstract

Let $\text{RM}(r,n)$ be the $r$th order Reed-Muller code of length $2^n$, and let $\rho(r,n)$ denote its covering radius, so that $\rho(1,n)$ is the largest possible nonlinearity of a Boolean function in $n$ variables. For odd $n$, the value of $\rho(1,n)$ was previously known only for $n\le 7$. It is known that $242\le\rho(1,9)\le 244$, but the exact determination of $\rho(1,9)$ has been a long-standing open question. We give a computer-assisted proof that $\rho(1,9)=242$. We first show that a function of nonlinearity $243$ would yield one of nonlinearity $244$, so it suffices to exclude $244$. Divisibility properties of the Walsh spectrum then attach to any function of nonlinearity $244$ a cubic $p$ whose spectrum attains the sharp bound $\sum\limits_a|W_p(a)|\le 10240$, and the cases of equality take one of two forms. One form is eliminated directly. The other is eliminated by an exhaustive computation that leverages the classification of the $349$ orbits in $\text{RM}(3,9)/\text{RM}(2,9)$ under $\text{GL}(9,2)$, using Langevin's catalog of representatives together with an audit of its completeness, and the enumeration is carried out twice with independent implementations. The notebook to verify the computer search portion, \texttt{Verify\_RM(1,9).ipynb}, contains all data and recomputes each check, and may be found in the repository \url{https://github.com/FreemanSlaughter/Covering-Radius}.