Computer Science

Uniqueness of optimal mod 3 polynomials for parity

Document Type

Article

Abstract

Text: In 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) = frac(1, 2n) under(∑, frac(xi ∈ {1, - 1}, 1 ≤ i ≤ n)) (underover(∏, i = 1, n) xi) ω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) | ≤ (frac(sqrt(3), 2))⌈ 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) | < (frac(sqrt(3), 2))⌈ n / 2 ⌉, then | S (t, k, n) | ≤ frac(sqrt(3), 2) (frac(sqrt(3), 2))⌈ n / 2 ⌉. This verifies two conjectures made in Dueñez et al. (2006) [5] for the special case of quadratic polynomials in Z3. Video: For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=mBoJrn1DuOM. © 2009 Elsevier Inc. All rights reserved.

Publication Title

Journal of Number Theory

Publication Date

2010

Volume

130

Issue

4

First Page

961

Last Page

975

ISSN

0022-314X

DOI

10.1016/j.jnt.2009.08.016

Keywords

Boolean circuit complexity, exponential sums, quadratic forms, tight bounds

APA Citation

?

Link to Full Text

Share

COinS