Monomial Boolean functions with large high-order nonlinearities (Q6204170)

The \emph{nonlinearity} of a Boolean function \(f\colon \mathbb{F}_2^n \to \mathbb{F}_2\) is the distance from \(f\) to the closest linear function. More generally, the \(d\)-order nonlinearity of \(f\) is its distance to the closest degree \(d\) (or less) function. Here \emph{degree} is the degree of the unique multilinear \(\mathbb{F}_2\)-polynomial representing \(f\), and a function is \emph{linear} if it has degree at most~\(1\). A random function is highly nonlinear. It is more challenging to exhibit explicit functions which have high nonlinearity. One class of functions which can be used to that end is \emph{monomial (Boolean) functions}. In these functions, the input is interepreted as an element of the finite field \(\mathbb{F}_{2^n}\), and the function is the trace of a monomial, that is, the function has the form \(f(x) = \operatorname{tr}(\lambda x^d)\) for some \(\lambda \in \mathbb{F}_{2^n}\) and \(d \in \mathbb{Z}\); here \emph{trace} has its usual definition from algebraic number theory. In this paper, the authors give lower bounds on the high nonlinearity of several monomial functions: \begin{enumerate} \item[1.] Second-order nonlinearity of \(\operatorname{tr}(x^7)\). \item[2.] Second-order nonlinearity of \(\operatorname{tr}(x^{2^r+3})\), where \(n = 2r\). \\ This should be compared to an identical lower bound for \(\operatorname{tr}(x^{2^{r+1}+3})\), proved in [\textit{H. Yan} and \textit{D. Tang}, Discrete Math. 343, No. 5, Article ID 111698, 11 p. (2020; Zbl 1468.94977)]. \item[3.] Third-order nonlinearity of \(\operatorname{tr}(x^{15})\). \item[4.] \(r\)-order nonlinearity of \(\operatorname{tr}(x^{2^{r+1}-1})\). \item[5.] \(r\)-order nonlinearity of \(\operatorname{tr}(x^{2^n-2})\). \end{enumerate} All bounds are proved using the method of \textit{C. Carlet} [IEEE Trans. Inf. Theory 54, No. 3, 1262--1272 (2008; Zbl 1192.94145)]. The bounds on second-order nonlinearity match the best known lower bounds on any explicit function.