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 all every non-zero points 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.)

As a natural (and expectedexpectable) 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, 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$?

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

Trivially

Ultimately, I want to know how large must $A$ be for every given degree $\deg P$. Say, if $P$ had has degree zero, then, trivially, $|A|\ge 2$ would sufficesuffices. 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.)

As a natural (and expected) 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, 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$?

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

Trivially, if $P$ had degree zero, then $|A|\ge 2$ would suffice. 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\}$$ 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$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.)

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

How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a qubiccubic 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$? (Here $n$ is a given positive integer, to be thought of as a growing parameter.)

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

• How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a qubic 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$? (Here $n$ is a given positive integer, to be thought of as a growing parameter.)

Trivially, if $P$ had degree zero, then $|A|\ge 2$ would suffice. 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.)