RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2025 Number 68, Pages 16–28 (Mi pdm870)

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



© Steklov Math. Inst. of RAS, 2025