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 $\texttt{https://github.com/FreemanSlaughter/Covering-Radius}$.