Upper bounds on nonlinearity of correlation immune Booleanfunctions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 1(11).

It is known that n l ( f ) A 2n - i - 2m for thenonlinearity n l ( f ) of any Boolean function f with n variables and with the correlationimmunity order m. We prove that for all n a 512 and 0 < m < n - 1, except two cases:m = 2s, n = 2s + 1 + 1 and m = 2S + 1, n = 2s + 1 + 2 for s a 0, this bound can be improvedup to n l ( f ) a 2 n - i - 2m+1. Besides, we have checked this result for n < 512, 0 < m < n - 1using computer.