Problem 2

For a polynomial

P

and a positive integer

n

, define

P_n

as the number of positive integer pairs

(a,b)

such that

a<b\le n

and

|P(a)|-|P(b)|

is divisible by

n

. Determine all polynomials

P

with integer coefficients such that

P_n\le2021

for all positive integers

n

Step 2 of 6: Key lemma: no two of the first n values collide mod n

Previous step Next step

\text{Lemma: } P(1),P(2),\ldots,P(n)\ \text{pairwise distinct}\pmod n

Detailed analysis

Because replacing P by its negative does not change the counts, assume P is positive for all sufficiently large positive arguments. If two of the first n values have the same remainder modulo n, choose A so that the corresponding values at arguments an+y and an+z are positive for every a at least A, then choose k larger than 2A plus 2021. The resulting 2(k−A) values all lie in the k residue classes modulo kn that reduce to the same remainder modulo n. Counting collisions among these classes gives at least k−2A, hence more than 2021, pairs with equal residues modulo kn. Their distinct positive arguments are below kn, contradicting the bound. Therefore the first n values are pairwise distinct modulo n.