The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20
Jinjie Gao, Haibin Kan, Yuan Li, Qichun Wang · IEEE Transactions on Information Theory · 2023
We prove the covering radius of the third-order Reed-Muller code$\mathrm {RM}(3,7)$is 20, which was previously known to be between 20 and 23 (inclusive). The covering radius of$\mathrm {RM}(3,7)$is the maximum third-order nonlinearity among all 7-variable Boolean functions. It was known that there exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. According to the classification of the quotient space of$\mathrm {RM}(6,6)/\mathrm {RM}(3,6)$, we classify all 7-variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove that any function in the remaining 4 types can be transformed into a type (6, 10) function, if its third-order nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve the third-order nonlinearity 21 (with the assistance of computers). By the way, we prove that the affine transformation group over any finite field can be generated by two elements.