Let $f(x)$ be a monic polynomial of degree $2023$ with positive integer coefficients. Show that for any sufficiently large integer $N$ and any prime number $p>2023N$, the product \[f(1)f(2)\dots f(N)\]is at most $\binom{2023}{2}$ times divisible by $p$. Proposed by Ashwin Sah
Problem
Source: German TST 2023, Test 4, Problem 3
Tags: algebra, polynomial, number theory, prime numbers, algebra proposed
16.07.2023 03:01
What if P(1) is a root?
16.07.2023 10:22
Sorry, I missed the condition that the coefficients are positive integers.
20.07.2024 01:45
This problem is beautiful. I tried it last year, struggled a lot, and came up with something sketchy and handwavy. Now I'm back with a polished solution. Let $f(x)=a_{2023}x^{2023}+\cdots+a_0$. I am going to prove that for each $0 \leq m \leq 2022$ there are at most $m$ roots of $f(x)$ modulo $p^{2023-m}$ in $[1,N]$, which is enough. We will need two key lemmas. Lemma 1: Let $P(x)$ be an integer polynomial of degree $d$ with at least $d+1$ roots modulo $p^k$ in $[1,p]$ for some $k \geq 1$. Then $p^k$ divides each of its coefficients. Proof: We use induction. The base case of $k=1$ is equivalent to the well-known fact that polynomials in $\mathbb{F}_p$ have number of roots at most their degree. For the inductive step, realize that by hypothesis we must have $p^{k-1}$ dividing each of its coefficients. Then dividing out $p^{k-1}$ everywhere we are left with the statement for $k=1$ which is also true. $\blacksquare$ Lemma 2: Let $k \geq 1, n \geq 0$ be integers and consider the remainder upon division of $x^{k-1+n}$ by $(x-r_1)\ldots(x-r_k)$. The coefficient of $x^{k-1}$ in this remainder is $\sum_{e_1+\cdots+e_k=n} \prod_i r_i^{e_i}$, where each $e_i$ is nonnegative. Proof: Let $\sigma_j$ denote the $j$-th elementary symmetric sum of the $r_i$, so for $j>k$ we have $\sigma_j=0$. We use induction on $n$ with $k$ fixed. The base case of $n=0$ is obvious. By subtracting $x^{n-1}(x-r_1)\ldots(x-r_k)$ we are left with $\sum_{i=1}^n (-1)^{i-1} \sigma_i x^{k+n-1-i}$ plus possibly some lower degree terms we don't care about. By inductive hypothesis this now equals $$\sum_{i=1}^n (-1)^{i-1}\sigma_i \sum_{e_1+\cdots+e_k=n-i} \prod_i r_i^{e_i}.$$Every term in this expansion has degree $n$ in $r_i$. For each $(e_1,\ldots,e_k)$ such that $e_1+\cdots+e_k=n$ we count the number of times $\prod_i r_i^{e_i}$ is included in the above expression. Suppose that there are $t$ nonzero terms in this tuple; then it gets included $\sum_{i=1}^t (-1)^{i-1}\binom{t}{i}$ times, which equals $1$ by the binomial theorem as desired. $\blacksquare$ Now suppose that $f(x)$ has at least $m+1$ roots $r_1,\ldots,r_{m+1} \in [1,N]$ modulo $p^{2023-m}$ for some $0 \leq m \leq 2022$. Consider the remainder of $f(x)$ upon division by $(x-r_1)\ldots(x-r_{m+1})$, which also has $m+1$ roots modulo $p^{2023-m}$. By our lemma applied to each term in $f(x)$, this remainder will have leading coefficient equal to $$\sum_{d=0}^{2023-m} a_{2023-d}\sum_{e_1+\cdots+e_{m+1}=2023-m-d}\prod_i r_i^{e_i}.$$This is equal to the sum of $\binom{2023}{m}$ (by "stars and bars") degree $2023-m$ monomials in $r_i$, plus some positive-coefficient terms of degree at most $2022-m$. Since each $r_i$ is in $[1,N]$, the leading coefficient is thus positive and bounded above by $\binom{2023}{m}N^{2023-m}+CN^{2022-m}$ for some $C$ independent of $N$. For $0 \leq m \leq 2021$ it follows that the leading coefficient is in $\left(0,p^{2023-m}\right) \supset \left(0,2023^{2023-m}N^{2023-m}\right)$ when $N$ is large enough independently of $p$, which proves the desired result. We now have to deal with the edge case of $m=2022$. Here the leading coefficient of the remainder will be $r_1+\cdots+r_{2023}+a_{2022}$. To obtain a contradiction, it suffices to prove that each $r_i$ is less than $\frac{p-a_{2022}}{2023}$ for all large enough $p$. Suppose that for some fixed integer $1 \leq c \leq a_{k-1}$ there were infinitely many $p \equiv c \pmod{2023}$ such that $p \mid f\left(\frac{p-c}{2023}\right)$, so $2023 \nmid c$. Then $p \mid 2023^{2023}f\left(\frac{p-c}{2023}\right)$ as well. The RHS is an integer polynomial, so it must have constant term $0$, i.e. $x \mid f\left(\frac{x-c}{2023}\right)$ identically. Then by plugging in $x=0$ we have $f\left(-\frac{c}{2023}\right)=0$, but $-\frac{c}{2023}$ is a rational non-integer which contradicts the rational root theorem, as desired. This finishes the problem. $\blacksquare$
13.01.2025 06:33
Here's progress that gives an upper bound of $\tbinom{2024}{2}$. I'm not sure if this can be improved to the desired bound. We claim that for $k=1,2,\dots,2023$, at most $k$ of $f(1)$, $f(2)$, $\dots$, $f(N)$ are divisible by $p^{2024-k}$, which suffices. Assume FTSOC that there are distinct integers $x_1<x_2<\dots<x_{k+1}$ in $[1,N]$ such that $p^{2024-k} \mid f(x_1),f(x_2),\dots,f(x_{k+1})$. Define $f_0(x)=f(x)$ and \[f_i(x)=\frac{f_{i-1}(x)-f_{i-1}(x_i)}{x-x_i}\]for $i=1,2,\dots,k$. We can inductively show that $f_i(x)$ is a polynomial with degree $2023-i$ and $p^{2024-k} \mid f_i(x_j)$ for $j>i$. Plugging in $i=k$ and $j=k+1$ gives a size contradiction for sufficiently large $p$. $\blacksquare$ Edit: This doesn't work yet. For this to work, we also need to bound the coefficients of $f_k(x)$ by something not dependent on $p$. I'm pretty sure this is possible, but I don't want to write it up.