A coloring of a q-ary n-dimensional cube (hypercube) is called perfect if, for every n-tuple x, the collection of the colors of the neighbors of x depends only on the color of x. A Boolean-valued function is called correlation-immune of degree n-m if it takes value 1 the same number of times for each m-dimensional face of the hypercube. Let f=@g^S be a characteristic function of a subset S of hypercube. In the present paper we prove the inequality @r(S)q(cor(f)+1)@?@a(S), where cor(f) is the maximum degree of the correlation immunity of f, @a(S) is the average number of neighbors in the set S for n-tuples in the complement of a set S, and @r(S)=|S|/q^n is the density of the set S. Moreover, the function f 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>2.
['Vladimir N. Potapov']
On perfect 2-colorings of the q-ary n-cube