14
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ What is a qubic polynomial, or did you mean cubic? $\endgroup$
    – user5810
    Feb 13, 2011 at 10:41
  • $\begingroup$ 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. $\endgroup$ Feb 14, 2011 at 8:22

3 Answers 3

18
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Fedor Petrov: $P$ is multilinear. $\endgroup$
    – Seva
    May 18, 2016 at 16:03
  • $\begingroup$ Ah, sorry, I see now. $\endgroup$ May 18, 2016 at 16:12
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Very nice indeed! $\endgroup$
    – Seva
    May 19, 2016 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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