When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T17:24:01Z http://mathoverflow.net/feeds/question/55300 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55300/when-does-pab0-for-ab-ensure-p00-continued When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.) Seva 2011-02-13T10:38:29Z 2011-04-20T14:22:13Z <p>As a natural (and expectable) extension of <a href="http://mathoverflow.net/questions/54619/when-does-pa-b0-for-a-ne-b-ensure-p00" rel="nofollow">my earlier question</a>:</p> <blockquote> <p>How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a <em>cubic</em> polynomial in $n$ variables over the field $F_2$, vanishing at every non-zero point of the sumset <code>$2A:=\{a_1+a_2\colon a_1,a_2\in A\}$</code>, then also $P(0)=0$? </p> </blockquote> <p>(Here $n$ is a given positive integer, to be thought of as a growing parameter.)</p> <hr> <p>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 <a href="http://mathoverflow.net/questions/54619/when-does-pa-b0-for-a-ne-b-ensure-p00" rel="nofollow">suffices</a> to have $|A|\ge n+3$. In the case where $P$ is cubic, at least $|A|>2n$ is needed: consider, for instance, the set <code>$$A=\{0,e_1,...,e_n,e_1+e_2,...,e_1+e_n\},$$</code> where $e_i$ are the vectors of the standard basis, and the polynomial <code>$$P=\sum_{1&lt;i&lt;j\le n} x_1x_ix_j+\sum_{1\le i&lt;j\le n} x_ix_j+\sum_{1\le i\le n} x_i+1.$$</code> 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.) </p> http://mathoverflow.net/questions/55300/when-does-pab0-for-ab-ensure-p00-continued/56385#56385 Answer by Seva for When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.) Seva 2011-02-23T11:46:47Z 2011-02-23T11:46:47Z <p>Some observations to revive the (non-existing) discussion.</p> <p>Consider the situation where $P\in F_2[x_1,...,x_n]$ is the complete cubic polynomial":</p> <p><code>$$P = \sum_{1\le i&lt;j&lt;k\le n} x_ix_jx_k + \sum_{1\le i&lt;j\le n} x_ix_j + \sum_{1\le i\le n} x_i + 1.$$</code></p> <p>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 <strong>not</strong> divisible by $4$. An example of such a set is <code>$$A = \{ 0, e_1,...,e_n, e_1+e_2,...,e_1+e_n \},$$</code> and it is not clear to me whether one can find substantially larger sets with this property.</p> <p>One can generalize this approach as follows. Fix $k\le\log_2(n+1)$ and consider the polynomial <code>$$P = \sum_{I\subset[n]\colon |I|&lt;2^k} \prod_{i\in I} x_i.$$</code> 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$ <em>can</em> vanish on all non-zero points of the sumset $2A$ for a set $A$ of size <code>$\sum_{0\le i&lt;2^{k-1}} \binom{n}{i}$</code> (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.</p> <p>How close is this construction to the best possible? Is not it true that if $\deg P=d$ and <code>$|A|&gt;\sum_{0\le i\le d/2} \binom ni$</code> (or so), then $P$ cannot vanish on all non-zero points of $2A$ without vanishing at $0$?</p>