On the divisibility properties and nonlinearity of resilient functions

Sarkar and Maitra have recently shown that, given any m-resilient function S on F-2(n), the Hamming distance between f and any affine function on F-2( n) is divisible by 2(m+1). We obtain a better divisibility bound, involving n, m and the algebraic degree d of the function. Smaller is d and/or m, st ronger is our improvement. We show that our divisibility bound is tight for every positive n, every non-negative m less than or equal to n - 2 and eve ry positive d less than or equal to n - m - 1. We deduce a bound on the non linearity of resilient functions involving n, m and d. This bound improves upon that obtained (independently) by Maitra and Sarkar and by Tarannikov. We finally show that the same bound stands in the more general framework of m-th order correlation-immune functions, for sufficiently large m. (C) 200 0 Academie des sciences/Editions scientifiques et medicales Elsevier SAS.