The Covering Radius of the Third-Order Reed-Muller Codes RM(3,7) is 20

We prove the covering radius of the third-order Reed-Muller code RM(3,7) is 20, which is known to be between 20 and 22 (inclusive) previously. The covering radius of RM(3, 7) is the maximum third-order nonlinearity among all 7-variable Boolean functions. It was known that there exists 7-variable Boolean function with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. Our proof relies on a classification result of RM(6,6) modulo RM(3,6) under affine transformations; by applying a sequence of third-order nonlinearity invariant transformations, we show all the potential Boolean functions with nonlinearity 21 can be transformed into certain "canonical forms", which greatly reduces the search space. As such, we are able to complete the proof with the assistance of a computer.