Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It's well known that there are no non-constant polynomials with integer coefficients whose values at integer points are primes. Could this result be generalized to the case of prime powers?

The question is whether there exists a polynomial $p(x) \in \mathbb{Z}[x]$ with degree at least one such that for all $x \in \mathbb{Z}$ $|p(x)|$ is prime power.

share|improve this question
add comment

2 Answers

up vote 9 down vote accepted

With integer coefficients the answer is surely no: let $f(x)\in\mathbb{Z}[x]$ a degree $d$ polynomial, and let $a\in \mathbb{Z}$ be such that $f(a)\neq0,1,-1$. Then there exist a prime $p$ such that $f(a)=0 \mod p$. Now consider the sequence $x_n=f(a+np)$. Since $x_n=0\mod p$, by the assumption on the values of $f$, we must have $x_n=p^{\alpha_n}$ for some positive integer $\alpha_n$. Moreover, since $x_n$ is definitely strictly increasing (it is no loss of generality assuming the leading coefficient of $f$ is positive), then so is $\alpha_n$. Therefore $p^{\alpha_n}$ has at least an exponential behaviour. But $x_n=O(n^d)$.

For rational coefficients I don't know, but I expect a negative answer in that case, too.

share|improve this answer
    
Ciao Domenico! For rational coefficients, essentially the same argument goes through. Indeed, if the prime $p$ does not appear in any denominator, then no change is needed. Otherwise, you multiply through by an appropriate power of $p$ and repeat the same argument to the resulting polynomial. –  damiano Aug 12 '10 at 12:34
    
Ciao Damiano, ben trovato su MO! Very neat observation that when $p$ does not apper in denominators no change is needed. But I'm not sure on your handling of the "$p$ appears in denominators" case. Namely, if I do not mistakenly read through your lines, you're suggesting to rplace $f(x)$ with $g(x)=p^k\,f(x)$ for a suitable $k$. But then the hypothesis $g(x)$ only takes prime powers as its values could not be satisfied. Rather I think the argument is saved by considering the sequence $x_n=f(a+np^k)$ instead. –  domenico fiorenza Aug 12 '10 at 13:01
    
I was too brief! Here's what I meant. First, if there are inf'ly many primes dividing values of $f$, then the argument works, since at least one of these primes doesn't divide one of the den's. Thus, there are only fin'ly many primes dividing the values of $f$, let $r$ be the number of such possible prime factors. Choose one and clear that denominator. The values of the resulting $f$ are products of (at most) two primes, so that up to $x^d$ there are (roughly) fewer than $rd^2\log^2(x)$ possible values of $f$. Since we need roughly $x$ values in this range, the growth rates are incompatible! –  damiano Aug 12 '10 at 13:25
    
It seems that one can prove that a polynomial with rational coefficients whose values are only divisible by a fixed set of primes is necessarily constant. This fact and the argument you wrote should do the trick, as I tried to explain in my comment. –  damiano Aug 12 '10 at 13:27
1  
Let $f$ be a pol with integer coeffs and suppose that there are fin'ly many primes $p_1,\ldots,p_r$ such that every prime dividing a value of $f$ appears among $p_1,\ldots,p_r$. Then $f$ is constant. Otherwise, there would be of the order of $n$ distinct values for $f(1),\ldots,f(n)$, but there are only of the order of $\log^r(n)$ possible values of $f$, since the exponent of each prime $p_1,\ldots,p_r$ is bounded above by (roughly) $\log_2(n^{\deg(f)})$. As $n$ grows, we run out of choices for the values of $f$! Note that this is also a consequence of the Chebotarev Density Thm. –  damiano Aug 12 '10 at 14:44
show 3 more comments

Actually you can prove a lot more.

Theorem

For any non-constant polynomial $p(x)\in\mathbb{Z}[x]$ and any positive integer $k$ there is an integer $n$ such that $p(n)$ is divisible by at least $k$ distinct primes.

Proof

If we prove that there exist integers $n_1,\ldots,n_k$ and distinct primes $p_1,\ldots,p_k$ such that $p(n_i)\equiv 0 \bmod{p_i}$ then we are done, because there exists an $n$ such that $n\equiv n_i\bmod{p_i}$ by the Chinese Remainder Theorem, and any such $n$ satisfies $f(n)\equiv f(n_i)\equiv 0 \bmod{p_i}$, as desired.

Now by contradiction suppose that $p$ is only divisible by the primes $p_1,\ldots,p_l$, $l\le k-1$. Since we have that $p(0)\neq 0$, let $p(0)=\pm p_1^{\alpha_1}\ldots p_l^{\alpha_l}$, $x\equiv 0\bmod{p_1^{\alpha_1+1}\ldots p_l^{\alpha_l+1}}$.

Then $p(x)\equiv p(0)\bmod{p_i^{\alpha_i+1}}$, $1\leq l\leq k-1$, so that the greatest power of $p_i$ that divides $p(x)$ is $p_i^{\alpha_i}$.

But by hypothesis $p(x)$ is only divisible by the $p_i$, so we conclude that $p(x)=\pm p(0)$. Using the pigeonhole principle and the fact that a non-constant polynomial can only assume a value a finite amount of times this is a contradiction, as desired.

share|improve this answer
    
In the case when values of the polynomial are only divisible by $p_1,\dots,p_l$, the possibility that $p(0) = 0$ does not occur. –  KConrad Aug 12 '10 at 18:26
    
Oh, of course! Thanks :P –  Jorge Miranda Aug 12 '10 at 18:52
    
Moreover, it's not really a Chinese remainder theorem argument. If $p(0) = 0$ then $p(n)$ is div. by $n$ for all $n$ so the result is clear. If $p(0)$ is not $0$ and we factor $p(0)$ as you do above (if $p(0)$ is 1 or $-1$ use any fake factorization with exponents all 0), then your argument shows there has to be some $x$ a multiple of $p_1^{\alpha_1+1}\cdots{p_l}^{\alpha_l+1}$ such that $p(x)$ is not $\pm p(0)$ and that $p(x)$ has to be divisible by a prime other than $p_1,\dots,p_l$. That gives you $p_{l+1}$. (Essentially I'm turning the contradiction into a direct recursive argument.) –  KConrad Aug 12 '10 at 21:11
add comment

Your Answer

 
discard

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.