Theoretical Backgrounds of Applied Discrete Mathematics
Curvature of some classes of Boolean functions
A. A. Panpurin MIREA — Russian Technological University, Moscow, Russia
Abstract:
The curvature
$\sigma(f)$ of Boolean function
$f$ is defined as the sum of the absolute values of its Walsh coefficients. In the paper, the curvature of various classes of Boolean functions constructed using superposition, symmetric polynomials and bent functions is investigated. Estimates and exact values have been obtained for the Walsh coefficients, curvature, and nonlinearity of the classes of Boolean functions under consideration. Let
$n$ be an odd number and
$f$ be a Boolean function in
$n$ variables, constructed according to the rule $f(x_1,\ldots, x_{n}) = x_n\varphi_0(x_1,\ldots,x_{n-1})oplus \bar{x}_{n}\varphi_1(x_1,\ldots,x_{n-1})$, where
$\varphi_0,\varphi_1$ are bent functions in
$n-1$ variables. It was shown that for such a function
$\sigma(f) = 2^{(3n-1)/{2}}$. We also examine a function of the form $f=f(x_1,\ldots, x_{n}) = x_nx_{n-1}\varphi(x_1,\ldots, x_{n-2})$ with an odd number of variables, where
$n\geq 6$,
$\varphi$ is a bent function in
$n-2$ variables. For this function $\sigma(f) = (2^{n}-4)2^{(n-2)/{2}}+3\cdot 2^{n-1}-2W_{\varphi}(0,\ldots,0)$, where
$W_{\varphi}(0,\ldots,0)$ is the Walsh coefficient of the function
$\varphi$. Moreover, an inequality is provided that demonstrates the relationship between the curvature and nonlinearity of arbitrary Boolean functions.
Keywords:
Boolean functions, bent functions, curvature of Boolean function, nonlinearity of Boolean function.
UDC:
519.716.32+
512.547
DOI:
10.17223/20710410/68/2