6
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – damiano
    Aug 12, 2010 at 12:34
  • $\begingroup$ 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. $\endgroup$
    – domenico fiorenza
    Aug 12, 2010 at 13:01
  • $\begingroup$ 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! $\endgroup$
    – damiano
    Aug 12, 2010 at 13:25
  • $\begingroup$ 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. $\endgroup$
    – damiano
    Aug 12, 2010 at 13:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – damiano
    Aug 12, 2010 at 14:44
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – KConrad
    Aug 12, 2010 at 18:26
  • $\begingroup$ 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.) $\endgroup$
    – KConrad
    Aug 12, 2010 at 21:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .