Approximation of Boolean functions by monomial ones
Алексей Сергеевич Кузьмин, Viktor Timofeevich Markov, Alexander A. Nechaev, Алексей Борисович Шишков · Discrete Mathematics and Applications · 2006
Every Boolean function of n variables is identified with a function F : Q → P , where Q = GF (2 n ), P = GF (2). A. Youssef and G. Gong showed that for n = 2 λ there exist functions F which have equally bad approximations not only by linear functions (that is, by functions tr ( μx ), where μ ∈ Q * and tr: Q → P is the trace function), but also by proper monomial functions (functions tr( μx δ ), where ( δ , 2 n − 1) = 1). Such functions F were called hyper-bent functions ( HB functions, HBF ), and for any n = 2 λ a non-empty class of HBF having the property F (0) = 0 was constructed. This class consists of the functions F ( x ) = such that the equation F ( x ) = 1 has exactly (2 λ − 1)2 λ −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 λ , and for some n (for instance, if λ > 2 and 2 λ − 1 is prime, or λ ∈ {4,9,25,27}) the class of HBF is exhausted by the functions F ( x ) = 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.