2006 USAMO Problems/Problem 3

Problem

(Titu Andreescu, Gabriel Dospinescu) For integral $m$ , let $p(m)$ be the greatest prime divisor of $m$ . By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$ . Find all polynomials $f$ with integer coefficients such that the sequence $\{ p(f(n^2))-2n) \}_{n\ge 0}$ is bounded above. (In particular, this requires $f(n^2)\neq 0$ for $n\ge 0$ .)

Solutions

Solution 1

Let $f(x)$ be a non-constant polynomial in $x$ of degree $d$ with integer coefficients, suppose further that no prime divides all the coefficients of $f$ (otherwise consider the polynomial obtained by dividing $f$ by the gcd of its coefficients). We further normalize $f$ by multiplying by $-1$ , if necessary, to ensure that the leading coefficient (of $x^d$ ) is positive.

Let $g(n) = f(n^2)$ , then $g(n)$ is a polynomial of degree $2$ or more and $g(n) = g(-n)$ . Let $g_1, \ldots, g_k$ be the factorization of $g$ into irreducible factors with positive leading coefficients. Such a factorization is unique. Let $d(g_i)$ denote the degree of $g_i$ . Since $g(-n) = g(n)$ the factors $g_i$ are either even functions of $n$ or come in pairs $(g_i, h_i)$ with $g_i(-n) = (-1)^{d(g_i)} h_i(n)$ .

Let $P(0) = \infty$ , $P(\pm 1) = 1$ . For any other integer $m$ let $P(m)$ be the largest prime factor of $m$ .

Suppose that for some finite constant $C$ and all $n \ge 0$ we have $P(g(n)) - 2n < C$ . Since the polynomials $g_i$ divide $g$ , the same must be true for each of the irreducible polynomials $g_i$ .

A theorem of T. Nagell implies that if $d(g_i) \ge 2$ the ratio $P(g_i(n))/n$ is unbounded for large values of $n$ . Since in our case the $P(g_i(n))/n$ is asymptotically bounded above by $2$ for large $n$ , we conclude that all the irreducible factors $g_i$ are linear. Since linear polynomials are not even functions of $n$ , they must occur in pairs $g_i(n) = a_in + b_i$ , $h_i(n) = a_in - b_i$ . Without loss of generality, $b_i \ge 0$ . Since the coefficients of $f$ are relatively prime, so are $a_i$ and $b_i$ , and since $P(0) = \infty$ , neither polynomial can have any non-negative integer roots, so $a_i > 1$ and thus $b_i > 0$ .

On the other hand, by Dirichlet's theorem, $a_i \le 2$ , since otherwise the sequence $a_in + b_i$ would yield infinitely many prime values with $P(g_i(n)) = a_in + b_i \ge 3n.$ So $a_i = 2$ and therefore $b_i$ is a positive odd integer. Setting $b_i = 2c_i + 1$ , clearly $P(g_i(n)) - 2n < 2c_i + 2$ . Since this holds for each factor $g_i$ , it is true for the product $g$ of all the factors with the bound determined by the factor with the largest value of $c_i$ .

Therefore, for suitable non-negative integers $c_i$ , $g(n)$ is a product of polynomials of the form $4n^2 - (2c_i + 1)^2$ . Now, since $g(n) = f(n^2)$ , we conclude that $f(n)$ is a product of linear factors of the form $4n - (2c_i + 1)^2$ .

Since we restricted ourselves to non-constant polynomials with relatively prime coefficients, we can now relax this condition and admit a possibly empty list of linear factors as well as an arbitrary non-zero integer multiple $M$ . Thus for a suitable non-zero integer $M$ and $k \ge 0$ non-negative integers $c_i$ , we have: $f(n) = M \cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)$

Solution 2

The polynomial $f$ has the required properties if and only if $f(x) = c(4x - a_1^2)(4x - a_2^2)\cdots (4x - a_k^2),\qquad\qquad (*)$ where $a_1, a_2, \ldots, a_k$ 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(n^2)$ but not of $c$ , then $p|(2n - a_j)$ or $p|(2n + a_j)$ for some $j\leq k$ . Hence $p - 2n\leq \max\{a_1, a_2, \ldots, a_k\}$ . The prime divisors of $c$ form a finite set and do not 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(n^2)) - 2n\}_{n\geq 0}$ is bounded above is given by $(*)$ .

Let $\mathbb{Z}[x]$ denote the set of all polynomials with integer coefficients. Given $f\in\mathbb{Z}[x]$ , let $\mathcal{P}(f)$ denote the set of those primes that divide at least one of the numbers in the sequence $\{f(n)\}_{n\geq 0}$ . The solution is based on the following lemma.

Lemma. If $f\in\mathbb{Z}[x]$ is a nonconstant polynomial then $\mathcal{P}(f)$ is infinite.

Proof. Repeated use will be made of the following basic fact: if $a$ and $b$ are distinct integers and $f\in\mathbb{Z}[x]$ , then $a - b$ divides $f(a) - f(b)$ . If $f(0) = 0$ , then $p$ divides $f(p)$ for every prime $p$ , so $\mathcal{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 $\mathcal{P}(f)$ is infinite. To complete the proof, set $g(x) = f(f(0)x)/f(0)$ and observe that $g\in\mathcal{Z}[x]$ and $g(0) = 1$ . The preceding argument shows that $\mathcal{P}(g)$ is infinite, and it follows that $\mathcal{P}(f)$ is infinite. $\blacksquare$

Suppose $f\in\mathbb{Z}[x]$ is nonconstant and there exists a number $M$ such that $p(f(n^2)) - 2n\leq M$ for all $n\geq 0$ . Application of the lemma to $f(x^2)$ shows that there is an infinite sequence of distinct primes $\{p_j\}$ and a corresponding infinite sequence of nonnegative integers $\{k_j\}$ such that $p_j|f(k_j)^2$ for all $j\geq 1$ . Consider the sequence $\{r_j\}$ where $r_j = \min\{k_j\pmod{p_j}, p_j - k_j\pmod{p_j}\}$ . Then $0\leq r_j\leq (p_j - 1)/2$ and $p_j|f(r_j)^2$ . Hence $2r_j + 1\leq p_j\leq p(f(r_j^2))\leq M + 2r_j$ , so $1\leq p_j - 2r_\leq M$ for all $j\geq 1$ . It follows that there is an integer $a_1$ such that $1\leq a_1\;leq M$ and $a_1 = p_j - 2r_j$ for infinitely many $j$ . Let $m = \deg f$ . Then $p_j|4^mf(((p_j - a_1)/2)^2)$ and $4^mf(((x - a_1)/2)^2)\in\mathbb{Z}[x]$ . Consequently, $p_j|f((a_1/2)^2)$ for infinitely many $j$ , which shows that $(a_1/2)^2$ is a zero of $f$ . Since $f(n^2)\leq 0$ for $n\geq 0$ , $a_1$ must be odd. Then $f(x) = (4x - a_1)^2g(x)$ , where $g\in\mathbb{Z}[x]$ . (See the note below.) Observe that $\{p(g(n^2)) - 2n\}_{n\geq 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 - a_1^2)g(x)$ where $g\in\mathbb{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 - a_1^2)g(x)$ where $r$ is rational and $g\in\mathbb{Z}[x]$ . Then continuation gives $f(x) = c(4x - a_1^2)\cdots (4x - a_k^2)$ where $c$ is rational and the $a_i$ are odd. Consideration of the leading coefficient shows that the denominator of $c$ is $2^s$ for some $s\geq 0$ and consideration of the constant term shows that the denominator is odd. Hence $c$ is an integer.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2006 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2006 USAMO Problems/Problem 3

Contents

Problem

Solutions

Solution 1

Solution 2

See also