Covering radius of nine variable reed muller code determined exactly
The covering radius of the first-order Reed-Muller code in nine variables is 242
Information Theory
Summary
This paper solves a longstanding mathematical problem about a special kind of code used in digital communication and cryptography. It finds the exact maximum distance any binary function with nine inputs can have from the simplest class of linear functions. The authors develop a new proof combining geometry, algebra, and computer-assisted checking to show this maximum distance is 242. This improves understanding of how well these codes cover all possible functions and supports designing better cryptographic tools.
What this means in practice
- •For cryptographic engineers: Use the precise nonlinearity limit of nine-variable functions to design or analyze cryptographic functions resistant to linear approximations.
- •For error correcting code developers: Leverage the exact covering radius of RM(1,9) to optimize code selection for reliable data transmission and decoding strategies.
A theory result. No direct application yet.
Authors
Yi Li
Abstract
We prove that the covering radius of the binary first-order Reed-Muller code RM(1,9) is exactly 242. Equivalently, the maximum nonlinearity of a Boolean function in nine variables is 242. Our proof combines a one-point rigidity theorem with a spectral and computational exclusion of the two larger candidate nonlinearities. We first show that every nine-variable Boolean function of nonlinearity 243 admits a unique one-point modification that raises its nonlinearity to 244: the point to be changed is the vector sum of its support. This part uses exact Walsh-update identities, integer interpolation, rigidity of a quadratic residue, and a sharp Walsh l1 estimate for cubic Boolean functions. To exclude nonlinearity 244, we use Parseval's identity and congruences of integral Walsh coefficients to force an exceptionally restricted spectrum. An associated cubic residue phase must attain the extremal Walsh l1 bound 10240. We eliminate one equality spectrum by hyperplane slicing; the other forces the original Boolean function from the signs of the cubic phase and yields a double-complement-pairing identity for its cubic top part. The classification of alternating trilinear forms over F2, an exact filter of their representatives, and two exhaustive enumerations of 218 quadratic supplements then rule out every remaining candidate. Together with the known construction attaining nonlinearity 242, these arguments establish the asserted covering radius.