Approximation of Boolean functions by monomial functions

A. S. Kuz'min ; V. T. Markov ; A. A. Nechaev ; A. B. Shishkov

Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 9-29

Résumé

Every Boolean function of $n$ variables is identified with a function $F\colon Q\to P$, where $Q=\mathit{GF}(2^n)$, $P=\mathit{GF}(2)$. A. Youssef and G. Gong showed that for $n=2\lambda$ there exist functions $F$ which have equally bad approximations not only by linear functions (that is, by functions $\operatorname{tr}(\mu x)$, where $\mu\in Q^*$ and $\operatorname{tr}\colon Q\to P$ is the trace function), but also by proper monomial functions (functions $\operatorname{tr}(\mu x^\delta)$, where $(\delta, 2^n-1)=1$). Such functions $F$ were called hyper-bent functions (HB functions, HBF), and for any $n=2\lambda$ a non-empty class of HBF having the property $F(0)=0$ was constructed. This class consists of the functions $F(x)=G(x^{2^\lambda-1})$ such that the equation $F(x)=1$ has exactly $(2^\lambda-1)2^{\lambda-1}$ solutions in $Q$. In the present paper, we give some essential restrictions on the parameters of an arbitrary HBF showing that the class of HBF is far less than that of bent functions. In particular, we show that any HBF is a bent function having the degree of nonlinearity $\lambda$, and for some $n$ (for instance, if $\lambda>2$ and $2^\lambda-1$ is prime, or $\lambda\in \{4,9,25,27\}$) the class of HBF is exhausted by the functions $F(x)=G(x^{2^\lambda-1})$ described by A. Youssef and G. Gong. For $n=4$, in addition to 10 HBF listed above there exist 18 more HBF with property $F(0)=0$. The question of whether there exist other hyper-bent functions for $n>4$ remains open. This research was supported by the Russian Foundation for Basic Research, grants 05–01–01048, 05–01–01018, and the program of the President of the Russian Federation for support of the leading scientific schools, grants 1910.2003.1, 2358.2003.9.