USAMO 95/4 solution

24th USAMO 1995

Problem 4

a₀, a₁, a₂, ... is an infinite sequence of integers such that a_n - a_m is divisible by n - m for all (unequal) n and m. For some polynomial p(x) we have p(n) > |a_n| for all n. Show that there is a polynomial q(x) such that q(n) = a_n for all n.

Solution

Clearly for any finite N, we can find a polynomial q(n) of degree N such that q(n) = a_n for n = 0, ... , N. Also, once a₀, a₁, ... , a_N are fixed, a_m is somewhat constrained for m > N, because we require a_m to be a₀ mod m, a₁ mod m-1, ... , a_N mod m-N. Put M = lcm(m, m-1, ... , m-N). Then a_m is determined mod M.

We would like to argue that q(m) is known to satisfy the congruences (because m - n divides q(m) - q(n) ), that q(m) and a_m are bounded so that they cannot differ by as much as M and hence must be equal. The snag is that q(x) does not necessarily have integer coeffcients, so it is not necessarily true that m - n divides q(m) - q(n). [The argument is that m - n divides m^k - n^k for any integer k and hence divides q(m) - q(n) for any polynomial with integer coefficients.]

However, the coefficients of q(x) are rational. So let Q be the lcm of the denominators. Then Q q(x) does have integer coefficients and m - n does divide Q( q(m) - q(n) ). So Q q(m) = Q q(0) = Q a₀ = Q a_m mod m, and similarly Q q(m) = Q a_m mod m-1 and so on. Hence Q q(m) = Q a_m mod M.

But we know that |q(m)| < c m^N for some constant c, since q(x) has degree N. Similarly, we know that |a_m| is bounded by a polynomial of degree N and hence |a_m| < c' m^N for some constant c'. Now M certainly exceeds the product of the N+1 numbers m, m-1, ... , m-N divided by the greatest common divisor for each of the N(N+1)/2 pairs (m - i, m - j). But each gcd is at most N, so M is more than c" m^N+1 for some (small) constant c" which does not depend on m. Hence for m ≥ some N' we have M > |Q q(m)| + |Q a_m| and hence q(m) = a_m.

So we have q(m) = a_m for m ≤ N and for m ≥ N'. Suppose N < m < N'. Then for any m' > N' we have that (m' - m) divides Q q(m') - Q q(m) and Q a_m' - Q a_m. So it must divide their difference. But q(m') = a_m', so it divides Q(q(m) - a_m). But we can choose m' so that (m' - m) is prime to Q and larger than (q(m) - a_m). Hence q(m) = a_m. So we have established that q(m) = a_m for all m.

Thanks to Nghi Nguyen for showing that we need Q in the last paragraph also.

24th USAMO 1995