A bound on correlation immunity.
Dmitri G. Fon-Der-Flaass · 2007
Abstract. A new bound on correlation immunity of non-constant unbalanced Boolean functions is proved. The bound is applied to obtain a new necessary condition for existence of a perfect coloring of the hypercube with given parameters. The new bound is stronger than the bounds previously obtained by Bierbrauer and Tarannikov, and is reached on an infinite class of examples. In this note we prove a new bound on correlation immunity of unbalanced Boolean functions. This bound was conjectured by Yu. Tarannikov. Let Ω = {1,..., n}. The powerset H = P(Ω) will be considered as the ndimensional hypercube; two subsets being adjacent iff they differ in exactly one element. For any sets x, y their symmetric difference will be denoted by x + y, and the size of x by |x|. For x, y ∈ H, x ∩ y = ∅, define the set [x] + y = {z ∪ y | z ⊆ x}. This is just a k-dimensional face of the hypercube, where k = |x|. Our main object is the 2n-dimensional linear space V of all real-valued functions on H endowed with the standard inner product 〈f, g 〉 = � f(x)g(x). Also, by x∈H fg we denote the ordinary product of functions. For any subset S ⊆ H, let χS be the characteristic function of S; that is, χS (x) = 1 if x ∈ S, otherwise χS (x) = 0. Definition 1. A function f ∈ V is called correlation immune of degree n − m iff 〈f, χ U 〉 is constant for all m-dimensional faces U ⊆ H. Two special cases of this notion are particularly important and well-studied: correlation immune Boolean functions, and orthogonal arrays (for instance, cf. [6] and Fon-Der-Flaass, D.G., A bound on correlation immunity.