New bounds on the covering radius of the second order Reed-Muller code of length 128

摘要

In 1981, Schatz proved that the covering radius of the binary Reed-Muller code RM(2, 6) is 18. It was previously shown that the covering radius of RM(2, 7) is between 40 and 44. In this paper, we prove that the covering radius of RM(2, 7) is at most 42. As a corollary, we also find new upper bounds for RM(2, n), n =8, 9, 10. Moreover, we give a sufficient and necessary condition for the covering radius of RM(2, 7) to be equal to 42. Using this condition, we prove that the covering radius of RM(2, 7) in RM(4, 7) is exactly 40, and as a by-product, we conclude that the covering radius of RM(2, 7) in the set of 2-resilient Boolean functions is at most 40, which improves the bound given by Borissov et al. (IEEE Trans. Inf. Theory 51(3):1182-1189, 2005).