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



Question about polynomials with coefficients in Z
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$.


