Uniqueness of optimal mod 3 polynomials for parity

AbstractTextIn this paper, we completely characterize the quadratic polynomials modulo 3 with the largest (hence “optimal”) correlation with parity. This result is obtained by analysis of the exponential sumS(t,k,n)=12n∑xi∈{1,−1}1⩽i⩽n(∏i=1nxi)ωt(x1,x2,…,xn)+k(x1,x2,…,xn) where t(x1,…,xn) and k(x1,…,xn) are quadratic and linear forms respectively, over Z3[x1,…,xn], and ω=e2πi/3 is the primitive cube root of unity. In Green (2004) [7], it was shown that |S(t,k,n)|⩽(32)⌈n/2⌉, where this upper bound is tight. In this paper, we show that the polynomials achieving this bound are unique up to permutations and constant factors. We also prove that if |S(t,k,n)|<(32)⌈n/2⌉, then |S(t,k,n)|⩽32(32)⌈n/2⌉. This verifies two conjectures made in Dueñez et al. (2006) [5] for the special case of quadratic polynomials in Z3.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=mBoJrn1DuOM