# When does $P(a-b)=0$ for $a\ne b$ ensure $P(0)=0$?

Let $n$ be a positive integer. How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a quadratic polynomial in $n$ variables, vanishing at all non-zero points of the sumset $2A:=\{a_1+a_2\colon a_1,a_2\in A\}$, then also $P(0)=0$?

Considering the situation where $P(x_1,\ldots,x_n)=\sum x_ix_j+\sum x_i+1$, and $A$ consists of $0$ and the elements of the standard basis, we see that having $|A|>n$ is not enough. On the other hand, if $|A|>C2^{3n/4}$ with an appropriate absolute constant $C$, then $A$ contains a $3$-dimensional affine subspace, whence $2A$ contains a $3$-dimensional linear subspace, and the assertion is easy to deduce. Where exactly between $n$ and $2^{3n/4}$ lies the truth?

## 1 Answer

Let $A$ be a maximal subset of $F^n_2$ with $P(A+A)\equiv 0$ but $P(0)\neq 0$. By finding a maximal linearly independent subset of $A$, and applying an appropriate linear transformation, we may assume $A$ contains the basis elements $e_1,\ldots,e_k$ and that all other elements of $A$ are linear combinations of these. We may further assume that $P$ is a polynomial in $x_1,\ldots,x_k,$ since we can throw out the other terms without changing our hypotheses. Then using that $P(e_i)=P(e_j)=P(e_i+e_j)=0$ and $P(0)=1$, one can deduce

$P=\sum_{\leq k} x_ix_j+\sum_{\leq k} x_i + 1$.

Finally, if $A$ contained anything besides the basis elements $e_i$ (and possibly zero*), $A+A$ would necessarily contain a non-zero element with either 3 or 0(mod 4) non-zero coordinates, for which $P$ does not vanish. So in fact, $|A|>n+1$ suffices.

*Actually, if $n\equiv 2 (\text{mod }4)$, we need $|A|>n+2$, since we can take the $e_i$'s, $0$, and $(1,1,\ldots,1)$.

• A very nice argument! – Seva Feb 7 '11 at 11:49