## 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

## Repository Citation

Green, Frederic and Roy, Amitabha, "Uniqueness of optimal mod 3 polynomials for parity" (2010). *Computer Science*. 53.

https://commons.clarku.edu/faculty_computer_sciences/53

## APA Citation

?