The Covering Radius of the Reed-Muller Code RM(m-4, m) in RM(m-3, m)

We present methods for computing the distance from a Boolean polynomial on m variables of degree m - 3 (i.e., a member of the Reed-Muller code RM(m - 3, m)) to the space of lower-degree polynomials (RM(m - 4, m)). The methods give verifiable certificates for both the lower and upper bounds on this distance. By applying these methods to representative lists of polynomials, we show that the covering radius of RM(4, 8) in RM(5, 8) is 26 and the covering radius of RM(5, 9) in RM(6, 9) is between 28 and 32 inclusive, and we get improved lower bounds for higher m. We also apply our methods to various polynomials in the literature, thereby improving the known bounds on the distance from 2-resilient polynomials to RM(m - 4, m).

Automated summary

This paper presents methods for calculating the distance between a Boolean polynomial and lower-degree polynomials. The methods provide verifiable certificates for the lower and upper bounds of this distance. By applying these methods to different polynomial lists, the paper shows that RM(4, 8) has a covering radius of 26 in RM(5, 8), and the covering radius of RM(5, 9) in RM(6, 9) is between 28 and 32 inclusive. The paper also improves the known upper bounds on the distance from 2-resilient polynomials to RM(m - 4, m) by applying the methods to various polynomials in the literature.