MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|cite|improve this question
What is a qubic polynomial, or did you mean cubic? – Ricky Demer Feb 13 '11 at 10:41
Uh, I missed that. Thanks. With respect to this question the effect of the condition is the same (other than the definition of $2A$ otherwise). Thanks. – Sándor Kovács Feb 14 '11 at 8:22

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.