Pseudo-Boolean functions valued on hypershere

Abstract

Fixing some ordering on the domain of real-valued functions of n Boolean variables (i. e. pseudo-Boolean functions) we can identify these functions (or rather tables of their values) with vectors in the Euclidean space R 2 n of dimension 2 n . From a perspective of the Boolean function theory the integer-valued pseudo-Boolean functions are of special interest. It is due to the fact that the Walsh–Hadamard transform of a Boolean function gives the integer-valued pseudo-Boolean function that identically corresponds to the Boolean function. If we represent such pseudo-Boolean functions by points of Euclidean space then all of them appear to be placed on the (2n−1)-dimensional sphere with radius 2 n . Previously the mapping of the n-variables Boolean function set on the Euclidean hypersphere in R 2 n was already studied. This paper represents an attempt to extend the results obtained in those settings to the subset of pseudo-Boolean functions corresponding to the points on the hypersphere. In particular, we consider new concepts of curvature and nonlinearity of such pseudo-Boolean functions. We set relations between them and express curvature value via some metric parameters related to the described geometric representation of the pseudo-Boolean functions. One of the aims of this investigation is to work out an approach to bounding maximum nonlinearity of Boolean functions with odd number of variables.