2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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}$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.