When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)

Question

As a natural (and expectable) extension of my earlier question:

How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, vanishing at every non-zero point of the sumset $2A:=\{a_1+a_2\colon a_1,a_2\in A\}$, then also $P(0)=0$?

(Here $n$ is a given positive integer, to be thought of as a growing parameter.)

---

Ultimately, I want to know how large must $A$ be for every given degree $\deg P$. Say, if $P$ has degree zero, then, trivially, $|A|\ge 2$ suffices. Furthermore, it is easy to see that for $P$ linear, one needs $|A|\ge 3$ (while $|A|\ge 2$ is insufficient). For $P$ quadratic, it suffices to have $|A|\ge n+3$. In the case where $P$ is cubic, at least $|A|>2n$ is needed: consider, for instance, the set $$ A=\{0,e_1,...,e_n,e_1+e_2,...,e_1+e_n\}, $$ where $e_i$ are the vectors of the standard basis, and the polynomial $$ P=\sum_{1<i<j\le n} x_1x_ix_j+\sum_{1\le i<j\le n} x_ix_j+\sum_{1\le i\le n} x_i+1. $$ Must $|A|$ actually be quadratic (or, perhaps, even exponential) in $n$? (If $|A|>2^{7n/8}$, then $A$ contains an affine $4$-dimensional subspace; hence $2A$ contains a linear $4$-dimensional subspace, and the rest follows with a minor effort.)

Answer 1

About three years after posting this question, the answer is now known (although there still can be some room for improvements). Namely, Lemma 1 from a recent joint paper by Ernie Croot, Peter Pach, and myself reads as follows:

Suppose that $n\ge 1$ and $d\ge 0$ are integers, $P$ is a multilinear polynomial in $n$ variables of total degree at most $d$ over a field $\mathbb F$, and $A\subseteq{\mathbb F}^n$ is a set with $|A|>2\sum_{0\le i\le d/2}\binom ni$. If $P(a-b)=0$ for all $a,b\in A$ with $a\ne b$, then also $P(0)=0$.

In particular, for $P$ cubic it suffices to have $|A|\ge 2n+3$ to conclude that $P(0)=0$. This is essentially sharp: an example above shows that at least $|A|\ge 2n+1$ is needed.

Answer 2

Some observations to revive the (non-existing) discussion.

Consider the situation where $P\in F_2[x_1,...,x_n]$ is the ``complete cubic polynomial":

$$ P = \sum_{1\le i<j<k\le n} x_ix_jx_k + \sum_{1\le i<j\le n} x_ix_j + \sum_{1\le i\le n} x_i + 1. $$

We have then $P(x)=1$ if and only if the weight of $x$ is divisible by $4$. Thus, for $P$ to vanish at all non-zero points of the sumset $2A$ it is necessary and sufficient that the Hamming distance between any two points of $A$ be not divisible by $4$. An example of such a set is $$ A = \{ 0, e_1,...,e_n, e_1+e_2,...,e_1+e_n \}, $$ and it is not clear to me whether one can find substantially larger sets with this property.

One can generalize this approach as follows. Fix $k\le\log_2(n+1)$ and consider the polynomial $$ P = \sum_{I\subset[n]\colon |I|<2^k} \prod_{i\in I} x_i. $$ We have $P(x)=1$ if and only if the weight of $x$ is divisible by $2^k$. Hence, $P$ vanishes at all non-zero points of $2A$ iff no distance between two (distinct) points of $A$ is divisible by $2^k$. We can achieve this simply by taking $A$ to be the set of all elements of $F_2^n$ of weight smaller than $2^{k-1}$. This shows that a polynomial of degree $2^k-1$ can vanish on all non-zero points of the sumset $2A$ for a set $A$ of size $\sum_{0\le i<2^{k-1}} \binom{n}{i}$ (without vanishing at $0$). Thus, for instance, there is a degree-$7$ polynomial vanishing at all non-zero points of the sumset of a set with $~n^3$ elements, but not vanishing at $0$, etc.

How close is this construction to the best possible? Is not it true that if $\deg P=d$ and $|A|>\sum_{0\le i\le d/2} \binom ni$ (or so), then $P$ cannot vanish on all non-zero points of $2A$ without vanishing at $0$?

Answer 3

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we have two functions $f,g\in\mathbb F^A$ such that $$\sum_{a\in A} f(a)Q(a)=\sum_{a\in A} g(a)Q(a)=0 \tag{$\ast$} $$ for any polynomial $Q\in\mathbb F[x_1,\ldots,x_n]$ of degree $\deg Q\leqslant d$. Then $$ \sum_{a\in A,b\in A} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $2d+1$. (If $Q$ is a monomial, then our sum factorizes and one of factors is 0.)

Applying this with the polynomial $Q(x,y):=P(x-y)$, where $\deg P\leqslant 2d+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$, we get $$ 0=\sum_{a\in A,b\in A} f(a)g(b)P(a-b)=P(0)\cdot \sum_{a\in A} f(a)g(a). $$ Now if $P(0)\ne 0$, then $\sum_{a\in A} f(a)g(a)=0$ for any two functions $f,g\in\mathbb F^A$ . Then functions $f,g$ satisfying ($\ast$). This condition determines a linear subspace of $\mathbb F^A$ of dimension at least $|A|-\binom{n+d}d$ (or $|A|-\sum_{i\leqslant d} \binom{n}i$, if we consider only multilinear polynomials). We have thus shown that if $P(0,0)\ne 0$, then this is an isotropic subspace (any two vectors are mutually orthogonal.) The maximal dimension of an isotropic subspace is well-studied. It cannot exceed $|A|/2$ by obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension $1$.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.