Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 USAMO Problems/Problem 3"

(Standardized)
(→‎Solution)
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
  
−
{{solution}}
+
Let <math>f(x)</math> be a non-constant polynomial in <math>x</math> of degree <math>d</math> with
 +
integer coefficients, suppose further that no prime divides all the
 +
coefficients of <math>f</math> (otherwise consider the polynomial obtained by
 +
dividing <math>f</math> by the gcd of its coefficients). We further ``normalize''
 +
<math>f</math> by multiplying by <math>-1</math>, if necessary, to ensure that the
 +
leading coefficient (of <math>x^d</math>) is positive.
 +
 
 +
Let <math>g(n) = f(n^2)</math>, then <math>g(n)</math> is a polynomial of degree <math>2</math> or
 +
more and <math>g(n) = g(-n)</math>. Let <math>g_1, \ldots, g_k</math> be the factorization
 +
of <math>g</math> into irreducible factors with positive leading coefficients.
 +
Such a factorization is unique. Let <math>d(g_i)</math> denote the degree of
 +
<math>g_i</math>. Since <math>g(-n) = g(n)</math> the factors <math>g_i</math> are either even
 +
functions of <math>n</math> or come in pairs <math>(g_i, h_i)</math> with <math>g_i(-n) =
 +
(-1)^{d(g_i)} h_i(n)</math>.
 +
 
 +
Let <math>P(0) = \infty</math>, <math>P(\pm 1) = 1</math>. For any other integer <math>m</math> let
 +
<math>P(m)</math> be the largest prime factor of <math>m</math>.
 +
 
 +
Suppose that for some finite constant <math>C</math> and all <math>n \ge 0</math> we have
 +
<math>P(g(n)) - 2n < C</math>. Since the polynomials <math>g_i</math> divide <math>g</math>, the
 +
same must be true for each of the irreducible polynomials <math>g_i</math>. A
 +
theorem of T.~Nagell implies that if <math>d(g_i) \ge 2</math> the ratio
 +
<math>P(g_i(n))/n</math> takes arbitrarily large values for <math>n</math> sufficiently
 +
large. Since in our case the <math>P(g_i(n))/n</math> is asymptotically bounded above
 +
by <math>2</math> for large <math>n</math>, we conclude that all the irreducible
 +
factors <math>g_i</math> are linear. Since linear polynomials are not even
 +
functions of <math>n</math>, they must occur in pairs <math>g_i(n) = a_in + b_i</math>,
 +
<math>h_i(n) = a_in - b_i</math>. Without loss of generality, <math>b_i \ge 0</math>.
 +
Since the coefficients of <math>f</math> are relatively prime, so are <math>a_i</math>
 +
and <math>b_i</math>, and since <math>P(0) = \infty</math>, neither polynomial can have
 +
any positive integer roots, so <math>a_i > 1</math> and thus <math>b_i > 0</math>.
 +
 
 +
On the other hand, by Dirichlet's theorem, <math>a_i \le 2</math>, since
 +
otherwise the sequence <math>a_in + b_i</math> would yield infinitely many
 +
prime values with <math>P(g_i(n)) = a_in + b_i \ge 3n.</math> So <math>a_i = 2</math> and
 +
therefore <math>b_i</math> is a positive odd integer. Setting <math>b_i = 2c_i +
 +
1</math>, clearly <math>P(g_i(n)) - 2n < 2c_i + 2</math>.  Since this holds for each
 +
factor <math>g_i</math>, it is true for the product <math>g</math> of all the factors
 +
with the bound determined by the factor with the largest value of
 +
<math>c_i</math>.
 +
 
 +
Therefore, for suitable non-negative integers <math>c_i</math>, <math>g(n)</math> is a
 +
product of polynomials of the form <math>4n^2 - (2c_i + 1)^2</math>.  Now,
 +
since <math>g(n) = f(n^2)</math>, we conclude that <math>f(n)</math> is a product of
 +
polynomials of the form <math>4n - (2c_i + 1)^2</math>.
 +
 
 +
Since we restricted ourselves to non-constat polynomials with
 +
relatively prime coefficients, we can now relax this condition and
 +
admit a possibly empty list of <math>k \ge 0</math> irreducible factors as
 +
well as an arbitrary non-zero integer multiple <math>M</math>. Thus for a
 +
suitable non-zero integer <math>M</math> and a possibly empty set of <math>k</math>
 +
non-negative integers <math>c_i</math>, we have:
 +
<cmath>f(n) = M \cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)</cmath>
  
 
== See Also ==
 
== See Also ==

Revision as of 23:46, 25 March 2010

Problem

For integral $\displaystyle m$, let $\displaystyle p(m)$ be the greatest prime divisor of $\displaystyle m$. By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$. Find all polynomials $\displaystyle 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$.)

Solution

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$ takes arbitrarily large values for $n$ sufficiently large. 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 positive 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 polynomials of the form $4n - (2c_i + 1)^2$.

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

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_USAMO_Problems/Problem_3&oldid=34004"