A note on a conjecture concerning symmetric resilient functions (Q5896692)

Let \(n\geq m\geq 1\) be integers, \(f: \{0,1\}^ n\to \{0,1\}^ m\), and \(t\leq n\). A function \(f\) is said to be \((n,m,t)\)-resilient if for every \(t\)-subset \(\{i_ 1,\dots,i_ t\}\subset \{1,\dots,n\}\), for every choice of \(z_ j\in\{0,1\}\), \(1\leq j\leq t\), and for every \((y_ 1,\dots,y_ m)\in \{0,1\}^ m\) the number \[ \bigl|\bigl\{(x_ 1,\dots,x_ n):\;f(x_ 1,\dots,x_ n)=(y_ 1,\dots,y_ m),\;x_ j=z_ j,\;1\leq j\leq t\bigr\}\bigr| \] is equal to \(2^{n-m}\). A function \(f\) is called symmetric if for every permutation \(p\) on \(\{1,\dots,n\}\) we have \(f(x_ 1,\dots,x_ n)= f(x_{p(1)},\dots,x_{p(n)})\). So, for any symmetric Boolean function \(f\) \((m=1)\) exists a function \(g: \{0,1,\dots,n\}\to \{0,1\}\) such that \(f(x_ 1,\dots,x_ n)= g(w(x_ 1,\dots,x_ n))\), where \(w(x_ 1,\dots,x_ n)\) is the Hamming weight of the \(n\)-tuple \((x_ 1,\dots,x_ n)\). In 1985 B. Chor et al. conjectured that the only \((n,1,1)\)-resilient symmetric Boolean functions are the exclusive - or of all \(n\) variables and its negation. In the present note the authors disprove the above conjecture by the following elegant construction: let \(r>2\) be an even number, \(n=r^ 2-2\), \(k=(r-2)(r+1)/2\), define a function \(h: \{0,1,\dots,n\}\to \{0,1\}\) as follows (for \(i\not\in \{k,k+1,n-k,n-k+1\}\)) \(h(i)=0\) if \(i\) is even and \(h(i)=1\) if \(i\) is odd; if \(i\in\{k,k+1,n-k,n-k+1\}\), then let \(h(i)=0\) if \(i\) is odd and \(h(i)=1\) if \(i\) is even. Theorem. The symmetric Boolean function \(f(x_ 1,\dots,x_ n)=h(w(x))\) is an \((n,1,2)\)-resilient function.