×

Approximation of plateaued Boolean functions by monomial ones. (Russian. English summary) Zbl 1448.94311

Summary: 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.

MSC:

94D10 Boolean functions
06E30 Boolean functions