Uniqueness of optimal mod 3 polynomials for parity (Q962998)

The correlation of two Boolean functions \(f, g : \{0, 1\}^n \rightarrow \{0, 1\}\), defined as \[ C (f, g) = 2^{-n} \sum_{(x_1, \dots, x_n) \in \{0, 1\}^n} (-1)^{f (x_1, \dots, x_n) + g (x_1, \dots, x_n)}, \] is a measure of the statistical closeness of these functions over the input domain. This paper concerns the case in which \(f\) is the parity function \(f (x_1, \dots, x_n) = \sum_{i = 1}^n x_i \pmod{2}\), and where \(g\) is computed by a polynomial \(p \in \mathbb{Z}_m [x_1, \dots, x_n]\) such that \(g (x_1, \dots, x_n) = 1\) if and only if \(p (x_1, \dots, x_n) \not\equiv 0 \pmod{m}\). In 2004, \textit{F. Green} [J. Comput. Syst. Sci. 69, No. 1, 28--44 (2004; Zbl 1064.68043)] studied the correlation expressed as the exponential sum \[ S (t, k, n) = \frac{1}{2^n} \sum_{\substack{ x_i \in {1, -1} \\ 1 \leq i \leq n}} \left(\prod_{i = 1}^n x_i\right) \omega^{t (x_1, x_2, \dots, x_n) + k (x_1, x_2, \dots, x_n)}, \] where \(\omega = e^{2 \pi i / m}\) is the primitive \(m\)-th root of unity for odd \(m\), and \(t (x_1, x_2, \dots, x_n)\) and \(k (x_1, x_2, \dots, x_n)\) are quadratic and linear forms, respectively, over \(\mathbb{Z}_3 [x_1, \dots, x_n]\). He showed that \[ |S (t, k, n)| \leq (\sqrt{3}/2)^{\lceil n / 2\rceil}. \] This upper bound is tight and was subsequently generalized dramatically, by \textit{J. Bourgain} [C. R., Math., Acad. Sci. Paris 340, No. 9, 627--631 (2005; Zbl 1112.11038)], to polynomials with degree at most \(O (\log n)\) and arbitrary odd moduli \(m\). In their paper of 2006 [J. Number Theory 116, No. 1, 168--199 (2006; Zbl 1162.11044)], \textit{E. Dueñez, S. J. Miller, A. Roy} and \textit{H. Straubing} conjectured that if \(t\) was quadratic, then \[ |S _m (t, k, n)| \leq \left(\cos \left(\frac{\pi}{2 m}\right)\right)^{\lceil n / 2\rceil}. \] The polynomials \[ c \left(\sum_{i = 1}^{n / 2} \pm x_{2i - 1} x_{2i}\right) \quad \text{if \(n\) is even}, \] and \[ \pm c x_1 + \sum_{i = 1}^{(n - 1)/2} \pm c x_{2i + 1} x_{2i} \quad \text{if \(n\) is odd}, \] where \(c = \lfloor (m + 1) / 4 \rfloor\), achieve this bound. Dueñez \textit{et al.} further conjectured that these were the unique polynomials that gave the maximum norm (up to permutations of variables or constant terms). They verified this conjecture for up to \(n = 10\) variables for arbitrary odd \(m\) and showed that, for all \(n\), the bound holds for a special class of quadratic polynomials in \(\mathbb{Z}_m\). Their investigation led to the conjecture that if \(t, k\) were such that \(S (t, k, n)\) was submaximal, then \(S_m (t, k, n) \leq \cos (\pi/ (2 m)) \cdot B_{m, n}\), where \(B_{m,n} = (\cos (\pi / (2m)))^{\lceil n / 2\rceil}\) is the maximum possible norm. In this paper, the authors prove the above conjectures of Dueñez \textit{et al.} for the special case when \(m = 3\). Their main result can be summarized as follows: Let \(n \geq 1\). Then \(|S_3 (t, k, n)| = B_{3,n} = (\sqrt{3}/2)^{\lceil n / 2\rceil}\) if and only if \[ t(x) + k(x) = \begin{cases} \alpha + \sum_{i = 1}^{n / 2} \pm x_{\pi (2i - 1)} x_{\pi (2i)}, &\text{if \(n\) is even,} \\ \alpha \pm x_{\pi (1)} + \sum_{i = 1}^{(n - 1) / 2} \pm x_{\pi (2i + 1)} x_{\pi (2i)}, &\text{if \(n\) is odd,} \end{cases} \] where \(\alpha \in \mathbb{Z}_3\) and \(\pi\) is some permutation of the variables. Furthermore, if \(|S (t, k, n)| < B_{3,n}\), then \(S (t, k, n)| \leq (\sqrt{3}/2) \cdot B_{3,n}\).