# sum of Boolean characters larger degree

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

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$$.
• 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}$$.