# Polynomials which always assume perfect power values

Let $f(x)$ be a non-constant polynomial with integer coefficients. It is a well-known result that if $f(n)$ is a square for all integers $n$, then $f$ must in fact be the square of a polynomial (see, for example: http://www.mast.queensu.ca/~murty/poly2.pdf).

My question is the following. Suppose that $\deg f = d$, and suppose that for every integer $n$, we have that $f(n)$ is a perfect $k$-th power for some $k_n > 1$ dividing $d$. I want to emphasize that $k_n$ is allowed to depend on $n$. For instance, it could be the case that $f$ is of degree $6$ and $f(2) = 2^3$ while $f(3) = 3^2$, and $f(n)$ is either a square or a cube (or both) for every $n$.

Can we conclude that $f$ is a perfect $m$-th power, for some $m > 1$ dividing $d$?

• Yes, of course. See Davenport, Lewis, Schinzel, Polynomials of certain special type, Acta Arithmetica IX, 1964 - or Schinzel's collected works. – Vesselin Dimitrov Nov 30 '15 at 3:44
• I saw the paper which states your claim in the first paragraph, but that is not what I wanted to know about. I apologize for the vagueness of the original question. – Stanley Yao Xiao Nov 30 '15 at 3:48
• OK, then there is a $k > 1$ (dividing $d$ as you require) which works for infinitely many $n$ - and you may apply Siegel's theorem (finiteness of integral points of an irrational affine algebraic curve - in this case, the components of $y^k = f(x)$), with the conclusion that $f$ is a $k$-th power. If you want a more "elementary" proof, my best guess is the DLS argument applies just as well in your situation. – Vesselin Dimitrov Nov 30 '15 at 3:56
• @VesselinDimitrov Thanks, that argument is perfectly fine for me! – Stanley Yao Xiao Nov 30 '15 at 4:04
• Why the downvote? The question seems reasonable to me. – David Zhang Nov 30 '15 at 8:06

Here is a more elementary argument than that of nfcd23. It only assumes that $f(n)$ is a $k$th power for some $k$ depending on $n$, which need not be assumed to divide $d$. Over $\mathbf{C}$, write

$$f(x) = C \prod (x - \alpha_i)^{r_i},$$

where the $\alpha_i$ are distinct. By Cebotarev, (or more simply, by Frobenius), we may find infinitely many primes $p$ such that $p$ splits completely in $K = \mathbf{Q}(\alpha_i)$, and in addition, $p$ is prime to both $C$ and the difference $\alpha_i - \alpha_j$ of any pair of distinct roots. (The last two conditions hold automatically for all but finitely many primes.)

For each root $\alpha_i$, choose a prime $p_i$ of this form. Then choose an integer $n$ (using the Chinese Remainder Theorem) such that:

$$\text{n is congruent to \alpha_i modulo p_i but not modulo p^2_i.}$$

This ensures that the $p_i$-adic valuation of $f(n)$ is $r_i$ for each $i$, because that is the valuation of $(n - \alpha_i)^{r_i}$, and by assumption, $p_i$ does not divide any of the other terms. If $f(n)$ is a perfect $k$th power, this implies that the greatest common divisor $r$ of all the $r_i$ must be divisible by $k$, and hence equal to $mk$ where $k > 1$. But that implies that $f(x) = A g(x)^{mk}$ for some $g(x)$. Once again letting $x = n$ and noting that $f(n)$ is a $k$th power, we deduce that $A = B^k$, and so

$$f(x) = B^k g(x)^{mk} = (B g(x)^m)^k.$$

• It's not clear to me if this argument is more elementary because it uses $L$ functions, but I'm glad you solved the more general version. – Will Sawin Nov 30 '15 at 8:58
• @WillSawin: This proof is much more elementary after noting that it is not necessary to use Cebotarev (or Frobenius) here: Let $F(x)\in\mathbb Z[x]$ be the minimal polynomial of an integral primitive element of the splitting field of $f(x)$. Then for any prime $p$ dividing $F(m)$ for some integer $m$ for which $F(x)$ is separable modulo $p$ we get that $F(x)$ factors into linears modulo $p$, and so does $f(x)$. Running through $m\in\mathbb Z$, we get infinitely primes of the required form. – Peter Mueller Nov 30 '15 at 10:35

Here is an argument avoiding Siegel's theorem (and also seemingly different from the DLS argument to which Dimitrov refers, as the main tool I will use is Weil's RH for absolutely irreducible curves whereas DLS use arguments based on Hilbert irreducibility).

Let $S$ be a non-empty finite set of primes (e.g., the primes factors of $d$) and consider $f \in \mathbf{Z}[X]$ that is not an $e$th power in $\mathbf{Z}[X]$ (equivalently, in $\mathbf{\mathbf{Q}}[X]$) for each $e \in S$. An elementary argument with the monic multiple of $f$ shows that for each of the primes $e \in S$ the polynomial $f$ either (i) is not an $e$th power in $\overline{\mathbf{Q}}[X]$ or (ii) is of the form $c h^e$ for some monic $h$ with $c$ the leading coefficient of $f$. If there is any integer $n$ away from zeros of $f$ such that $f(n)$ is an $e$th power for some $e$ as in case (ii) then $c$ is an $e$th power and hence so is $f$. Thus, we can assume for our purposes that case (ii) never occurs.

Since each $e\in S$ is prime, it follows that the polynomial $Y^e - f(X)$ is irreducible in $\overline{\mathbf{Q}}[X,Y]$ (as it is the same to be irreducible in $\overline{\mathbf{Q}}(X)[Y]$, for which $f$ not being an $e$th power in $\overline{\mathbf{Q}}(X)$ is equivalent to the irreducibility property since $e$ is prime). We conclude that $Y^e - f(X)$ is absolutely irreducible over $\mathbf{Q}$ for every $e \in S$. Hence, for all large primes $p$, $Y^e - f(X)$ is absolutely irreducible over $\mathbf{F}_p$ too. (Recall that "absolute irreducibility" is inherited under reduction modulo all but finitely many primes, whereas ordinary irreducibility is not.) In what follows, only consider such $p$ (moreover big enough so that $f \bmod p$ has the same degree as $f$).

These curves $Y^e - f(X) = 0$ for varying $e \in S$ (if $\#S > 1$) have finite overlap in characteristic 0, so they are pairwise disjoint up to uniformly bounded error in characteristic $p$ for large $p$. Hence, the solution set $V_p$ to $h \equiv 0 \bmod p$ is the "disjoint" (up to bounded amount) union of the solutions sets to the individual curves $C_{e,p} := \{y^e - f(x) = 0\}$. There are at most $d := \deg(f)$ values $x \in \mathbf{F}_p$ where $f$ vanishes mod $p$, over which there is only one point $(x,0)$ in $V_p$. Ignoring those at most $d$ points, as well as the uniformly bounded overlaps sets for distinct $e$'s just mentioned, every other fiber of $V_p$ over the $x$-line $\mathbf{F}_p$ lies in exactly one of the curves $C_{e,p}$.

Consider $p \equiv 1 \bmod e$ for all $e \in S$. The fibers for $C_{e,p}$ have size $e$ (away from zeros of $f$ in $\mathbf{F}_p$). As $p$ grows, $\#C_{e,p}(\mathbf{F}_p) \sim p$ for each $e \in S$, by RH, so the image of $C_{e,p}$ in $\mathbf{F}_p$ consists of $\sim p/e$ points as $p$ grows.

Varying through all $e \in S$, if $V_p$ actually hits the entire $x$-line for all such large $p$ (say even up to a bounded amount as such $p$ grows) we would get $\sum_{e \in S} 1/e = 1$ (equality on the nose, not just approximation). But the $e$'s are pairwise distinct primes, so no such equality is possible (look at it $e_0$-adically for one $e_0 \in S$).

Thus, for (many) large $p$ the projection $x: V_p \rightarrow \mathbf{F}_p$ is not surjective, so if $n \in \mathbf{Z}$ represents a mod-$p$ residue class not in the image then for every $e \in S$ the congruence $y^e \equiv f(n) \bmod p$ has no solution, so certainly for every $e \in S$ the integer $f(n)$ is not an $e$th power in $\mathbf{Z}$ as well.

QED