MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Here's an idea, but I'd have to open a book in analytic number theory to push it further. Consider a polynomial f of degree (at most) n such that p(f)=g(n). You didn't say it, but surely meant to imply that we're supposed to be assuming f is non-zero. So this f is non-zero. Now consider f(2). This number cannot vanish, because the leading term beats all the other terms put together. However f(2) is clearly less than 2^{n+1}. This already gives a non-trivial bound for g(n), because it shows that 2^{n+1} is an upper bound for the "product of all prime powers <= g(n)". What does that tell us? – Kevin Buzzard Jan 21 '10 at 14:20
OK so I opened the analytic number theory book, and this argument gives (if I got it right) that g(n)=O(n.log(2)). So not as strong as you want. – Kevin Buzzard Jan 21 '10 at 14:28
Fp[x] has unique prime factorization, so if a polynomial is 0 everywhere mod p, then its reduction mod p must be a multiple of x(x-1)(x-2)...(x-p+1) = x^p-x which has degree p. That means results on the density of primes tell you g(n) can't be much more than n. – Douglas Zare Jan 21 '10 at 14:56
"g(n) can't be much more than n". Just to point out that log(2)<1 so my argument also gives this. – Kevin Buzzard Jan 21 '10 at 16:30
Here's what may be a (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
up vote 20 down vote accepted

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

share|cite|improve this answer
I need time to undrestand it. Actually, number theory is a topic of next year in my university. :) – ilyaraz Jan 22 '10 at 8:07
What is a prime number theorem? – ilyaraz Jan 22 '10 at 8:11
As far as I understand in your sum $q$ is also prime. Is it right? – ilyaraz Jan 22 '10 at 8:31
The Prime Number Theorem tells you that the number of primes up to x is asymptotically x/log x. Yes, q is assumed to be prime. Poonen's very nice proof shows that primes q greater than sqrt(n) which divide all values of f tell you complex zeros of f, primitive (q-1)st roots of unity. Then there can't be too many primes, o(n^(1/2 + epsilon)), since more would mean there would be too many distinct complex zeros of f. The prime number theorem shows that asymptotically, there would be too many primes between p(f) and sqrt(n) if p(f) were much larger than sqrt(n). – Douglas Zare Jan 22 '10 at 12:57
Thank you for your explanations. – ilyaraz Jan 22 '10 at 21:47

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.

share|cite|improve this answer
As David remarked, his argument can be refined. Here is one such refinement: Let G be (Z/LZ)^y, where L=lcm(1,...,y), and let g_i=(0^i,...,(y-1)^i). Since log L = (1+o(1)) y, this leads to the lower bound g'(n) >= ((log 2)^{1/2} - o(1)) n^{1/2}, which is pretty close to my upper bound. – Bjorn Poonen Jan 24 '10 at 1:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.