Difference between revisions of "2006 USAMO Problems/Problem 3"
(Standardized) |
(→Solution) |
||
Line 5: | Line 5: | ||
== 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 , let
be the greatest prime divisor of
. By convention, we set
and
. Find all polynomials
with integer coefficients such that the sequence
is bounded above. (In particular, this requires
for
.)
Solution
Let be a non-constant polynomial in
of degree
with
integer coefficients, suppose further that no prime divides all the
coefficients of
(otherwise consider the polynomial obtained by
dividing
by the gcd of its coefficients). We further ``normalize
by multiplying by
, if necessary, to ensure that the
leading coefficient (of
) is positive.
Let , then
is a polynomial of degree
or
more and
. Let
be the factorization
of
into irreducible factors with positive leading coefficients.
Such a factorization is unique. Let
denote the degree of
. Since
the factors
are either even
functions of
or come in pairs
with
.
Let ,
. For any other integer
let
be the largest prime factor of
.
Suppose that for some finite constant and all
we have
. Since the polynomials
divide
, the
same must be true for each of the irreducible polynomials
. A
theorem of T.~Nagell implies that if
the ratio
takes arbitrarily large values for
sufficiently
large. Since in our case the
is asymptotically bounded above
by
for large
, we conclude that all the irreducible
factors
are linear. Since linear polynomials are not even
functions of
, they must occur in pairs
,
. Without loss of generality,
.
Since the coefficients of
are relatively prime, so are
and
, and since
, neither polynomial can have
any positive integer roots, so
and thus
.
On the other hand, by Dirichlet's theorem, , since
otherwise the sequence
would yield infinitely many
prime values with
So
and
therefore
is a positive odd integer. Setting
, clearly
. Since this holds for each
factor
, it is true for the product
of all the factors
with the bound determined by the factor with the largest value of
.
Therefore, for suitable non-negative integers ,
is a
product of polynomials of the form
. Now,
since
, we conclude that
is a product of
polynomials of the form
.
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 irreducible factors as
well as an arbitrary non-zero integer multiple
. Thus for a
suitable non-zero integer
and a possibly empty set of
non-negative integers
, we have: