I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then $$ \frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1 $$ if and only if $S=0^n$ and is $0$ otherwise. Suppose I replace the exponent from a degree-1 term to a degree-2 or degree-k term, do we know how these character sums behave? For example, do we know bounds on the quantity $$ \frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{x^t A x} $$ (where $A\in \mathbb{F}_2^{n\times n}$ upper triangular matrix) or in more generality we have $\frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{f_k(x)}$ where $f_k$ is a degree-k multilinear polynomial in $x_1,\ldots,x_n$? Any reference would be appreciated if such bounds/exact expressions are known
1 Answer
This is related to higher-order Fourier analysis.
A classical result of Dickson ("Dickson's lemma") states that up to a change of basis, any quadratic form over $\mathit{GF}(2)$ is of the form $$ x_1 x_2 + \cdots + x_{2r-1} x_{2r} + a x_{2r+1} + b, $$ for some $a,b \in \mathit{GF}(2)$, where $r$ is known as the rank. In your case, $r$ is half the rank of $A + A^T$, and $b = 0$. The quantity you are interested in is known as the bias, and can be easily computed at this point: $$ \mathbb{E}[(-1)^{x_1 x_2 + \cdots + x_{2r-1} x_{2r} + a x_{2r+1} + b}] = \prod_{i=1}^r \mathbb{E}[(-1)^{x_{2i-1} x_{2i}}] \mathbb{E}[(-1)^{ax_{2r+1}}] \mathbb{E}[(-1)^b]. $$ Now $\mathbb{E}[(-1)^{x_{2i-1} x_{2i}}] = \frac{1}{4} \cdot (-1) + \frac{3}{4} \cdot (1) = \frac{1}{2}$ and $\mathbb{E}[(-1)^{x_{2r+1}}] = 0$.
Therefore:
- If $a = 1$ then the bias is $0$.
- If $a = 0$ and $b = 0$ then the bias is $2^{-r}$.
- If $a = 0$ and $b = 1$ then the bias is $-2^{-r}$.
