On the structure and numbers of higher order correlation-immune functions

It is proved by means of a Ramsey-like technique that for each positive integer k there exists a minimal nonnegative integer p´(k) that any n-k th order correlation-immune function of n binary input variables, f≠const, depends nonlinearly on at most p´(k) inputs. It is proved that the number of n-k th order correlation-immune functions of n binary input variables, k=const, n→∞, is polynomial. For k=1, 2, 3 the exact formulas for the numbers of such functions are obtained