Abstract: It is known that the order of correlation immunity of a nonconstant unbalanced Boolean function in n variables cannot exceed 2n/3-1; moreover, it is 2n/3-1 if and only if the function corresponds to an equitable 2-partition of the n-cube with an eigenvalue -n/3 of the quotient matrix. The known series of such functions have proportion 1:3, 3:5, or 7:9 of the number of ones and zeros. We prove that if a nonconstant unbalanced Boolean function attains the correlation-immunity bound and has ratio C:B of the number of ones and zeros, then CB is divisible by 3. In particular, this proves the nonexistence of equitable partitions for an infinite series of putative quotient matrices. We also establish that there are exactly 2 equivalence classes of the equitable partitions of the 12-cube with quotient matrix [[3,9],[7,5]] and 16 classes, with [[0,12],[4,8]]. These parameters correspond to the Boolean functions in 12 variables with correlation immunity 7 and proportion 7:9 and 1:3, respectively (the case 3:5 remains unsolved). This also implies the characterization of the orthogonal arrays OA(1024,12,2,7) and OA(512,11,2,6).

Cite: Krotov D.S. , Vorob'ev K.V.
On unbalanced Boolean functions with best correlation immunity
Electronic Journal of Combinatorics. 2020. V.27. N1. P1.45 :1-24. DOI: 10.37236/8557 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Mar 6, 2019
Accepted:	Feb 3, 2020
Published online:	Feb 21, 2020

Identifiers:

Web of science:	WOS:000521457200002
Scopus:	2-s2.0-85079845425
Elibrary:	43249465
OpenAlex:	W3102415219

Citing:

DB	Citing
Web of science	6
Scopus	9
Elibrary	3
OpenAlex	7

Altmetrics: