An infinite class of counterexamples to a conjecture concerning nonlinear resilient functions (Q1895965): Difference between revisions

Let \(1\leq k\leq n\) be integers and \(f: \{0,1\}^n\to \{0,1 \}^k\) be a function with \(n\) input bits and \(k\) output bits. Let \(t\leq n\) be an integer. Then \(f\) is said to be \((n,k,t)\)-resilient iff for every \(t\)-subset \(\{i_1, \dots, i_t\} \subseteq \{1, \dots, n\}\) for every choice of \(z_j\in \{0,1\}\) \((0\leq j\leq t)\) and for every \((y_1, \dots, y_k)\in \{0,1\}^k\) we have \[ p(f (x_1, \dots, x_n)= (y_1, \dots, y_k)\mid x_{i_j}= z_j,\;1\leq j\leq t)= {\textstyle {1\over 2^k}}. \] The \((n,k,t)\)-resilient function is linear if \(f(\vec x)= \vec x M\) for some \(n\times k\) binary matrix \(M\). The main constructions for resilient functions are based on the following connection with linear error-correcting codes: the existence of an \([n,k, d]\) code is equivalent to the existence of a linear \((n,k, d-1)\)-resilient function. The authors give a new proof of this theorem. It has been conjectured that if a resilient function exists, then a linear function with the same parameters exists. The authors construct infinite classes of nonlinear resilient functions from the Kerdock and Preparata nonlinear codes. Thus the aforementioned conjecture is disproved.