Question about polynomials with coefficients in Z

Question

Let $f = a_0 + a_1 x + \ldots + a_n x^n$ ($f \ne 0$), where $a_i \in \{-1, 0, 1\}$. Let $p(f)$ be the largest number such that $f(x)$ is divisible by $y$ for any integer $x$ and for any $1 \leq y \leq p(f)$. Let $g(n)=max_f\; p(f)$. Is it true that $g(n) = o(n)$? What is the best upper or lower bound on $g(n)$ can be derived?

For my application it would be great to prove that $g(n) = o(n)$ in order to obtain something non-trivial, or $g(n) = o(n^{2/5})$ in order to improve the best known result. Do you think it is real?

UPD It is an obvious consequence of Bertrand's postulate and Schwartz–Zippel lemma that $g(n) \leq 2n$. Using bruteforce I've got the following values:

$g(10) = 7$, $f = x^{10} + x^8 - x^4 - x^2$.

$g(15) = 10$, $f = x^{15} + x^{13} + x^{12} + x^{11} + x^{10} - x^7 - x^6 - x^5 - x^4 - x^3$.

$g(17) = 10$, $f = x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} - x^8 - x^7 - x^6 - x^5 - x^4 - x^3$.

Answer 1

I'll prove the upper bound $g(n) = O(n^{1/2+o(1)})$, which is essentially best possible if Kevin Costello's heuristics are correct.

Suppose that $q$ is a prime with $q > n^{1/2}+1$. Reducing $f(x)$ modulo $x^{q-1}-1$ in $\mathbb{Z}[x]$ amounts to reducing the exponents modulo $q-1$, so the result is a polynomial $h(x)$ of degree less than $q-1$ whose coefficients are at most $n/(q-1) + 1$ (which is less than $q$) in absolute value. On the other hand, if $q \le p(f)$, then $f(x) \bmod q$ is divisible by $x^q-x$ and hence also by $x^{q-1}-1$, so $h(x) \bmod q$ must be $0$; this is possible only if $h(x)=0$ in $\mathbb{Z}[x]$, which implies that $f(x)$ vanishes at the $\phi(q-1)$ primitive $(q-1)$-th roots of unity. Since $f(x)$ has at most $n$ complex zeros, we get $\sum_{n^{1/2}+1 < q \le p(f)} \phi(q-1) \le n$ (the sum ranges over primes $q$ in the interval). By the prime number theorem and Theorem 327 in Hardy and Wright (which states that $\phi(m)/m^{1-\delta} \to \infty$ for any $\delta>0$), this is a contradiction for sufficiently large $n$ if $p(f)>n^{1/2+\epsilon}$ for a fixed $\epsilon>0$.

EDIT: The more precise bound $\phi(m) \ge (e^{-\gamma} - o(1)) m/\log \log m$ given by Theorem 328 in Hardy and Wright leads to $g(n) \le (e^{\gamma}/2 + o(1)) n^{1/2} \log n \log \log n$.

Answer 2

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.