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

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$?