arXiv preprint ·
The covering radius of the first-order Reed-Muller code in nine variables is 242
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Number Theory
Cyclotomic polynomials with trinomial irreducible factors over finite fields
Explicit permutations of $(\mathbb{Z}/4\mathbb{Z})^m$ with uniformly bounded differential uniformity
Good rational functions up to degree six
Lattice moments and quantum designs
Finding Integer Roots of Polynomials in Nearly Optimal Time
Get the few papers worth your time in Number Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.