MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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
up vote 15 down vote accepted

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.

share|cite|improve this answer
    
@Fedor Petrov: $P$ is multilinear. – Seva May 18 at 16:03
    
Ah, sorry, I see now. – Fedor Petrov May 18 at 16:12

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

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.

share|cite|improve this answer
    
Very nice indeed! – Seva May 19 at 10:12

Your Answer

 
discard

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.