On degree-$3$ and $(n-4)$-correlation-immune perfect colorings of $n$-cubes

Abstract

A perfect $k$-coloring of the Boolean hypercube $Q_n$ is a function from the set of binary words of length $n$ onto a $k$-set of colors such that for any colors $i$ and $j$ every word of color $i$ has exactly $S(i,j)$ neighbors (at Hamming distance $1$) of color $j$, where the coefficient $S(i,j)$ depends only on $i$ and $j$ but not on the particular choice of the word. The $k$-by-$k$ table of all coefficients $S(i,j)$ is called the quotient matrix. We characterize perfect colorings of $Q_n$ of degree at most $3$, that is, with quotient matrix whose all eigenvalues are not less than $n-6$, or, equivalently, such that every color corresponds to a Boolean function represented by a polynomial of degree at most $3$ over $R$. Additionally, we characterize $(n-4)$-correlation-immune perfect colorings of $Q_n$, whose all colors correspond to $(n-4)$-correlation-immune Boolean functions, or, equivalently, all non-main (different from $n$) eigenvalues of the quotient matrix are not greater than $6-n$. Keywords: perfect coloring, equitable partition, resilient function, correlation-immune function.

arXiv comment28pp. V2: revised, accepted version

References in corpus (6)

• On weight distributions of perfect colorings and completely regular codes
• On the OA(1536,13,2,7) and related orthogonal arrays
• The extended 1-perfect trades in small hypercubes
• Cameron-Liebler line classes in $\mathrm{PG}(3,5)$
• On multifold packings of radius-1 balls in Hamming graphs
• Degree 2 Boolean Functions on Grassmann Graphs