Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 10 min ago
PreprintCC BY 4.0arXiv

The Covering Radius of the Reed--Muller Code RM(1,9) is 242

  • Qichun Wang
  • Yueying Lou
  • Zifan Wang
Open at sourcePDFDOICite

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 ℓ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 ‖ Wg‖ 1+2|Wg(0)|≤ 10368, and then reduce either to a spectrum bounded by 24 or to the same expression to be at least 10496.

Related

  1. The Covering Radius of the Reed--Muller Code \texorpdfstring{RM(3,8)}{RM(3,8)} is 56
    Zhihang Zhao, Yansheng Wu
    arXivPreprintCC BY-NC-SA 4.0Full textGeneral mathematicsarXiv
  2. The covering radius of the first-order Reed-Muller code in nine variables is 242
    Yi Li
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. The Projective Reed-Muller Code from Quartic Curves in the Projective Plane
    Xu Zhuang
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  4. Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric
    Zhihao Zhu, Haojie Gu, Jun Zhang +1
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Common zeros of homogeneous polynomials and the weight hierarchy of projective Reed-Muller codes
    Rodrigo San-José
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{wang2026covering,
  title = {{The Covering Radius of the Reed--Muller Code RM(1,9) is 242}},
  author = {Qichun Wang and Yueying Lou and Zifan Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17871},
  eprint = {2610.17871},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17871},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Covering Radius of the Reed--Muller Code RM(1,9) is 242
AU  - Qichun Wang
AU  - Yueying Lou
AU  - Zifan Wang
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17871
UR  - https://arxiv.org/abs/2610.17871
AB  - 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 ℓ^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 ‖ W_g‖ _1+2|W_g(0)|≤ 10368, and then reduce either to a spectrum bounded by 24 or to the same expression to be at least 10496.
ER  -