Covering radius of reed-muller code RM 3 8 determined exactly
The Covering Radius of the Reed--Muller Code \texorpdfstring{$\RM(3,8)$}{RM(3,8)} is 56
Information Theory
Summary
This paper solves a specific problem in coding theory by precisely determining a key property called the covering radius of the Reed--Muller code with certain parameters. The authors use advanced mathematical techniques to separate cases and analyze structures within the code to prove their result. Their work formalizes and confirms the maximum distance any data point can be from encoded messages for this type of code. They also provide detailed proofs and computational verification to support their findings.
What this means in practice
- •For error correction engineers: Determine exact error correction boundaries for Reed–Muller codes improving communication system designs.
- •For cryptography protocol designers: Use precise nonlinearity measures of functions to evaluate cryptographic primitives based on Reed–Muller codes.
A theory result. No direct application yet.
Authors
Zhihang Zhao, Yansheng Wu
Abstract
We prove that the covering radius of the third-order Reed--Muller code in eight variables is fifty-six. The proof separates even- and odd-weight inputs by moment-controlled slicing. On the even side, a transport invariant on quadratic-label stars and consistency of singleton restrictions give a compatible cubic correction. On the odd side, symmetry of the third moment yields a covariance-rank obstruction. Its rank-two exception is a quartic plus three points of a two-plane; the zero-second-moment case is a prescribed-point perturbation of a quintic. We prove that every such point perturbation has third-order nonlinearity at most fifty-five by a marked derivative identity and complete restriction-code covers. Consequently the maximum among exact-degree-eight functions is fifty-five. The structural reductions are proved analytically, and complete finite certificates verify the explicitly stated local covering and compatibility assertions. The matching lower bound follows from the published quartic relative radius.