Problem:
For integral m, let p(m) be the greatest prime divisor of m. By convention, we set p(±1)= 1 and p(0)=∞. Find all polynomials f with integer coefficients such that the sequence
{p(f(n2))−2n}n≥0
is bounded above. (In particular, this requires f(n2)=0 for n≥0.)
Solution:
The polynomial f has the required properties if and only if
f(x)=c(4x−a12)(4x−a22)⋯(4x−ak2)(*)
where a1,a2,…,ak are odd positive integers and c is a nonzero integer. It is straightforward to verify that polynomials given by (∗) have the required property. If p is a prime divisor of f(n2) but not of c, then p∣(2n−aj) or p∣(2n+aj) for some j≤k. Hence
p−2n≤max{a1,a2,…,ak}
The prime divisors of c form a finite set and do affect whether or not the given sequence is bounded above. The rest of the proof is devoted to showing that any f for which
{p(f(n2))−2n}n≥0
is bounded above is given by (*).
Let Z[x] denote the set of all polynomials with integral coefficients. Given f∈Z[x], let P(f) denote the set of those primes that divide at least one of the numbers in the sequence {f(n)}n≥0. The solution is based on the following lemma.
Lemma. If f∈Z[x] is a nonconstant polynomial then P(f) is infinite.
Proof. Repeated use will be made of the following basic fact: if a and b are distinct integers and f∈Z[x], then a−b divides f(a)−f(b). If f(0)=0, then p divides f(p) for every prime p, so P(f) is infinite. If f(0)=1, then every prime divisor p of f(n!) satisfies p>n. Otherwise p divides n !, which in turn divides f(n!)−f(0)=f(n!)−1. This yields p∣1, which is false. Hence f(0)=1 implies that P(f) is infinite. To complete the proof, set g(x)=f(f(0)x)/f(0) and observe that g∈Z[x] and g(0)=1. The preceding argument shows that P(g) is infinite, and it follows that P(f) is infinite.
Suppose f∈Z[x] is nonconstant and there exists a number M such that p(f(n2))−2n≤ M for all n≥0. Application of the lemma to f(x2) shows that there is an infinite sequence of distinct primes {pj} and a corresponding infinite sequence of nonnegative integers {kj} such that {pj f(kj2) for all j≥1.
Consider the sequence {rj} where rj= min {kj(modpj), pj−kj(modpj)}. Then 0≤rj≤(pj−1)/2 and pj∣f(rj2). Hence 2rj+1≤pj≤p(f(rj2))≤M+2rj, so 1≤pj−2rj≤M for all j≥1. It follows that there is an integer a1 such that 1≤a1≤M and a1=pj−2rj for infinitely many j. Let m=degf. Then pj∣4mf((pj−a1)/2)2) and 4mf((x−a1)/2)2)∈Z[x]. Consequently, pj∣f((a1/2)2) for infinitely many j, which shows that (a1/2)2 is a zero of f. Since f(n2)=0 for n≥0,a1 must be odd. Then f(x)=(4x−a12)g(x) where g∈Z[x].(See the note below.) Observe that {p(g(n2)−2n}n≥0 must be bounded above. If g is constant, we are done. If g is nonconstant, the argument can be repeated to show that f is given by (∗).
Note. The step that gives f(x)=(4x−a12)g(x) where g∈Z[x] follows immediately using a lemma of Gauss. The use of such an advanced result can be avoided by first writing f(x)=r(4x−a12)g(x) where r is rational and g∈Z[x]. Then continuation gives f(x)=c(4x−a12)⋯(4x−ak2) where c is rational and the ai are odd. Consideration of the leading coefficient shows that the denominator of c is 2s for some s≥0 and consideration of the constant term shows that the denominator is odd. Hence c is an integer.
This problem was proposed by Titu Andreescu and Gabriel Dospinescu.
The problems on this page are the property of the MAA's American Mathematics Competitions