Maths Olympiad Prep

Library / /75 of 115

Number theory Difficulty 7.5 National olympiad, round 2 Find the answer

For integral mm, let p(m)p(m) be the greatest prime divisor of m.m. By convention, we set p(±1)=1p(\pm 1) = 1 and p(0)=.p(0) = \infty. Find all polynomials ff with integer coefficients such that the sequence
{p(f(n2))2n}n0 \{p \left( f \left( n^2 \right) \right) - 2n \}_{n \geq 0} is bounded above. (In particular, this requires f(n2)0f \left (n^2 \right ) \neq 0 for n0.n \geq 0.)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider the given polynomials f(x) f(x) with integer coefficients, which need to ensure the sequence
{p(f(n2))2n}n0 \{p(f(n^2)) - 2n\}_{n \geq 0}
is bounded above. Here, p(m) p(m) denotes the greatest prime divisor of m m , with p(±1)=1 p(\pm 1) = 1 and p(0)= p(0) = \infty .

### Step 1: Analyze the Sequence

The requirement that the sequence is bounded above translates to the constraint:
p(f(n2))2n+C p(f(n^2)) \leq 2n + C
for some constant C C and for all n0 n \geq 0 .

### Step 2: Ensure Non-Zero Condition for f(n2) f(n^2)

To ensure that f(n2)0 f(n^2) \neq 0 for all n0 n \geq 0 and that the sequence is bounded, we should consider the structure of f(x) f(x) . The fact that p(f(n2)) p(f(n^2)) is bounded suggests f(n2) f(n^2) cannot have terms that grow too fast relative to the linear function 2n 2n .

### Step 3: Determine the Form of f(x) f(x)

For the condition p(f(n2))2n p(f(n^2)) - 2n to have an upper bound, consider forms of f(x) f(x) where the roots of f(x)=0 f(x) = 0 result in factors that prevent rapid growth:

Suppose f(x) f(x) is of the form:
f(x)=Ti=1m(4xai) f(x) = T \cdot \prod_{i=1}^{m} (4x - a_i)
where T T is an integer constant and ai a_i are integers.

This ensures the polynomial f(n2) f(n^2) takes values such that the greatest prime divisor p(f(n2)) p(f(n^2)) is controlled and cannot exceed 2n 2n by a large margin since each root implies shifts by constants only. The factor 4xai 4x - a_i ensures that for each n n , the polynomial translates into a product of terms that holds the degree growth limited to linear terms after evaluation at n2 n^2 .

### Step 4: Verify Constants and Conditions

- For n n large, each minimum term becomes significant and maintains bounded p(f(n2)) p(f(n^2)) .
- The presence of constant integer T T does not change the growth dynamics relative to linearly growing 2n 2n .

Finally, verify if no greater terms can arise from roots being inherently controlled by this polynomial form. This confirms boundedness of the sequence in line with problem constraints.

Thus, the polynomials f f that satisfy the given conditions are of the form:
f(x)=Ti=1m(4xai) \boxed{f(x) = T \cdot \prod_{i=1}^{m} (4x - a_i)}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.