On perfect 2-colorings of the qq-ary nn-cube

A coloring of a qq-ary nn-dimensional cube (hypercube) is called perfect if, for every nn-tuple xx, the collection of the colors of the neighbors of xx depends only on the color of xx. A Boolean-valued function is called correlation-immune of degree n−mn−m if it takes value 11 the same number of times for each mm-dimensional face of the hypercube. Let f=χSf=χS be a characteristic function of a subset SS of hypercube. In the present paper we prove the inequality ρ(S)q(cor(f)+1)≤α(S), where cor(f) is the maximum degree of the correlation immunity of ff, α(S)α(S) is the average number of neighbors in the set SS for nn-tuples in the complement of a set SS, and ρ(S)=|S|/qnρ(S)=|S|/qn is the density of the set SS. Moreover, the function ff is a perfect coloring if and only if we have an equality in the formula above. Also, we find a new lower bound for the cardinality of components of a perfect coloring and a 1-perfect code in the case q>2q>2.