Number of roots of a quadratic form over GF(2)

Question

If $Q(x) = x^T A x$ with $x \in GF(2)^n$ and $A \in GF(2)^{n \times n}$, is there a way to find how many roots $Q(x)$ has based on any properties of $A$ (e.g., rank, etc.)?

Answer 1

(I assume you mean roots over $\mathbb{F}_2$.) This was done by Carlitz in the paper "Gauss sums over finite fields of order $2^n$" (Acta Arith. 15, 247-265 (1969)).

Let $r \ge 1$ be the rank of $A$ (which we shall also call the rank of $Q$). We say that $A$ is nonsingular, or that $Q$ is nondegenerate, if $r=n$.

Carlitz showed that the number of zeros is $2^{n-1}$ when $r$ is odd, and is $2^{n-1} \pm 2^{n-\frac{r}{2}-1}$ when $r$ is even. The sign genuinely depends on $Q$.

Below are the details. Let us first suppose that $A$ is nonsingular. If $n$ is odd there are $2^{n-1}$ zeros. See equation (5.9)' in Carlitz with $q=2$, itself a special case of his Theorem 9. This is proved using the fact, that Carlitz attributes to Dickson, that $Q$ must be equivalent to the quadratic form $\sum_{i=1}^{(n-1)/2} x_{2i-1}x_{2i}+x_n^2$. This is related to the comment of Fedor Petrov. We say $Q_1$ and $Q_2$ are equivalent if $Q_1(Mx)=Q_2(x)$ for some nonsingular $M$ over $\mathbb{F}_2$.

If $n$ is even there are two cases. We say that $Q$ has type $\tau=1$ if it is equivalent to the quadratic form $\sum_{i=1}^{n/2}x_{2i-1}x_{2i}$. We say that it has type $\tau=-1$ if it is equivalent to the quadratic form $\sum_{i=1}^{(n-2)/2}x_{2i-1}x_{2i} + x_{n-1}^2+x_{n-1}x_n+x_n^2$. When $n$ is even, any nonsingular quadratic form over $\mathbb{F}_2$ in $n$ variables is equivalent to exactly one of these two (this is due to Dickson as well).

The result when $n$ is even is that the number of zeros of $Q$ is $$2^{n-1} + 2^{\frac{n}{2}-1}\tau,$$ see equation (5.7)' in Carlitz with $q=2$, itself a special case of his Theorem 8. This is again proved using Dickson's result.

Carlitz proved these results by computing the exponential sum $\sum_{(x_1,\ldots,x_n)\in \mathbb{F}_2^n}(-1)^{Q(x_1,\ldots,x_n)}$. This is a good idea because this is a Fourier coefficient of the distribution of $Q$, and it behaves well with respect to convolution, and we already represent $Q$ as a sum of smaller 'independent' quadratic forms, thanks to Dickson's results.

To treat singular $A$, just transform $A$ into an appropriate form - this is explained in page 255 of Carlitz. In detail, let $r$ be the rank of $A$. Then one can prove that $Q(x)$ is equivalent to $Q_2(x_1,\ldots,x_r)$ for some nondegenerate $Q_2$. If $r$ is odd, the number of zeros of $Q(x)$ is $2^{n-r}$ (coming from the variables $x_{r+1},\ldots,x_n$ not influencing the value of $Q_2$) times $2^{r-1}$ (the number of zeros of $Q_2(x)$ as in the odd case), so $2^{n-1}$ zeros in total. If $r$ is even, the number of zeros is $2^{n-r}$ times $(2^{r-1}+2^{\frac{r}{2}-1}\tau)$, so $2^{n-1}+2^{n-\frac{r}{2}-1}\tau$ zeros in total. Here $\tau$ is the type of $Q_2$.

For nonsingular $A$, these results also appear as Theorems 6.30 and 6.32 in the book "Finite Fields" by Lidl and Niederreiter (2nd edition).