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

completely non-rigorous) reason you might NOT expect o(n^{2/5}) to hold: For p(f) to be at least k, it suffices for p to satisfy the k^2 equations corresponding to y|f(x) for each y and x between 0 and k. Assuming everything you could possibly want to be true actually is true (the probability each equation is satisfied by a random polynomial is at least 1/k, and satisfying the equations are all independent), then a random p would work with probability at least k^{-k^2}. But there are about 3^n polynomials, so for k much smaller than n^{-1/2} we'd expect a solution. – Kevin P. Costello Jan 21 '10 at 22:11