nt.number theory - Question about polynomials with coefficients in Z

The point of this answer is to point out that Kevin Costello's heuristic can be made rigorous. For any positive $epsilon$, if $y=O(n^{1/2-epsilon})$ then such a polynomial exists for large $n$.

Lemma: Let $G$ be a finite abelian group and let $g_1$, $g_2$, ..., $g_n$ be elements of $G$. If $2^n > |G|$ then there are integers $epsilon_i in { -1, 0, 1 }$, not all zero, such that $sum epsilon_i g_i =0$.

Proof: Consider the $2^n$ sums $sum a_i g_i$ with $a_i in { 0, 1 }$. By the pigeonhole principle, two of these are equal. Subtracting them, we get the claimed relation. QED

Now, consider the abelian group
$$G:=bigoplus_{k=1}^y (mathbb{Z}/k)^{oplus k}.$$
Let $g_i$ be the element of $G$ whose $k$-th component is $(0^i, 1^i, 2^i, 3^i, ldots, (k-1)^i)$, for $i=0$, $1$, ..., $n$. The order of $G$ is $exp( sum k log k) = exp( O(y^2 log y))$. So, if $y=O(n^{1/2-epsilon})$, then $2^{n+1} > |G|$ and the lemma tells us that there are $epsilon_i$ such that $sum epsilon_i g_i=0$. Then $sum epsilon_i x^i$ is the required polynomial.

There is a lot of slack in this argument, but Bjorn's argument shows that we can't improve the exponent of $n$ by tightening it.