The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048
2026-07-02 • Information Theory
Information Theory
AI summaryⓘ
The authors calculate how many codewords of different weights appear in a specific Reed–Muller code called RM(3,11), which is important in error correction. They use a method based on grouping certain functions called Boolean cubic forms and study properties of these forms to organize their calculations. In doing so, they also find exact values related to how well simpler codes can approximate more complex ones, improving known limits on these differences. Moreover, they perform additional tests showing a new, smaller upper bound for a related approximation measure in a higher-order case.
Reed–Muller codeWeight distributionBoolean cubic formsGL(10,2) groupCovering radiusNonlinearityCode lengthCoset weight enumeratorsHyperplane restriction
Authors
Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta
Abstract
We compute the weight distribution of the third-order Reed--Muller code RM(3,11) of length 2048. The weight enumerator is assembled from the coset weight enumerators of f+RM(2,10), evaluated for representatives of all 3691560 nonzero GL(10,2)-orbits of Boolean cubic forms in ten variables. The computation rests on a structural theorem: a nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension. The same pass determines the second-order nonlinearity of every cubic form: the relative covering radius of RM(2,10) in RM(3,10) is 408, attained on 179 orbits. This raises the best known lower bound on the covering radius of RM(2,10) from 400 to 408. A complementary heuristic search shows that the relative covering radius of RM(6,10) in RM(7,10) is at most 32, improving the previous bound of 50.