Approximation of plateaued boolean functions by monomial ones

A. V. Ivanov

Prikladnaâ diskretnaâ matematika, no. 1 (2008), pp. 10-14

Résumé

From the Parseval's equation we have that if the squared Walsh transform of the Boolean function takes at most one nonzero value then its Walsh coefficients are equal to $2^{2n-2s}$ for some $s\le n/2$. These functions are called the $2s$-order plateaued functions. In the present paper we consider the aspects of an approximation of the plateaued functions by monomial ones. We use the representation of $n$-variable Boolean functions by polynomials over the field $\mathbb F_{2^n}$. The necessary conditions for the Boolean functions to have the Hamming distance to all bijective monomials taking only three values: $2^{n-1}$, $2^{n-1}\pm 2^{n-s-1}$, are obtained. The non-existence of the functions, satisfying these conditions for such $n$ that $2^n-1$ is prime, is shown.