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

  • 1
    $\begingroup$ 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? $\endgroup$ Jan 21 '10 at 14:20
  • $\begingroup$ 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. $\endgroup$ Jan 21 '10 at 14:28
  • $\begingroup$ 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. $\endgroup$ Jan 21 '10 at 14:56
  • $\begingroup$ "g(n) can't be much more than n". Just to point out that log(2)<1 so my argument also gives this. $\endgroup$ Jan 21 '10 at 16:30
  • 5
    $\begingroup$ 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. $\endgroup$ Jan 21 '10 at 22:11

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

  • $\begingroup$ I need time to undrestand it. Actually, number theory is a topic of next year in my university. :) $\endgroup$
    – ilyaraz
    Jan 22 '10 at 8:07
  • $\begingroup$ What is a prime number theorem? $\endgroup$
    – ilyaraz
    Jan 22 '10 at 8:11
  • $\begingroup$ As far as I understand in your sum $q$ is also prime. Is it right? $\endgroup$
    – ilyaraz
    Jan 22 '10 at 8:31
  • $\begingroup$ 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). $\endgroup$ Jan 22 '10 at 12:57

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.

  • 1
    $\begingroup$ 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. $\endgroup$ Jan 24 '10 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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