We prove the covering radius of the third-order Reed-Muller code RM(3,7) is 20, which was known to be between 20 and 23 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 exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. Because a 7-variable Boolean function is the concatenation of two 6-variable Boolean functions, our proof relies on the classification of RM(6,6)/RM(3,6); we classify all 7-variable Boolean functions into 66 types accordingly. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove function of 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 third-order nonlinearity 21 (with the assistance of computers).
翻译:我们证明三阶Reed-Muler 代码RM(3,7)的半径为20,已知在20-23之间。RM(3,7)的半径是所有7种可变布尔函数中最高的三阶非线性。已知存在7种可变布尔函数,但有3级非线性。我们证明,第三阶非线性不能实现21个。因为7级可变布尔函数是两种6种可变布尔函数的交配,我们的证据依赖于RM(6,6)/RM(3,6)的分类;我们将所有7种可变布尔函数都相应地分类为66种。首先,我们证明62种(在66种中)不能具有第三阶非线性21;第二,我们证明其余4种功能可以转换为一种类型(6,10)的功能,如果第三阶非线性为21个;最后,我们将类型(6,10)的功能转换为一种特定形式,并证明以这种形式出现的功能不能达到第3阶非线性21(有协助的计算机)。