Problem A. 815. (January 2022)

A. 815. Let \(\displaystyle q\) be a monic polynomial with integer coefficients. Prove that there exists a constant \(\displaystyle C\) depending only on polynomial \(\displaystyle q\) such that for an arbitrary prime number \(\displaystyle p\) and an arbitrary positive integer \(\displaystyle N\le p\) the congruence \(\displaystyle n! \equiv q(n) \pmod{p}\) has at most \(\displaystyle CN^{2/3}\) solutions among any \(\displaystyle N\) consecutive integers.

Submitted by Navid Safaei, Iran

(7 pont)

Deadline expired on February 10, 2022.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Először belátjuk a következő lemmát:

Lemma: Álljon a \(\displaystyle H\) halmaz \(\displaystyle N\) egymást követő egész számból: \(\displaystyle H=\{k,k+1,...,k+N-1\}\). Legyen \(\displaystyle S\) a \(\displaystyle H\) tetszőleges részhalmaza és legyen \(\displaystyle \alpha=(|S|-1)/N\). Ekkor létezik egy olyan \(\displaystyle 1\le d \le 2/\alpha\) egész szám, melyre legalább \(\displaystyle N\alpha^2/4\) megoldása van az \(\displaystyle y-x=d\) egyenletnek az \(\displaystyle S\) halmazon.

Bizonyítás: Tekintsük \(\displaystyle S\) egymást követő elemei között a különbséget (és rendeljük hozzá a kisebb elemhez). Legfeljebb \(\displaystyle N\alpha/2\) esetben lehet a különbség nagyobb, mint \(\displaystyle 2/\alpha\). Tehát legalább \(\displaystyle N\alpha/2\) olyan eleme van \(\displaystyle |S|\)-nek, amikor a különbség kisebb, mint \(\displaystyle 2/\alpha\). A skatulya-elv miatt tehát lesz egy különbség, amely legalább \(\displaystyle N\alpha/2\cdot \alpha/2=N\alpha^2/4\) esetben fellép.

Legyen most \(\displaystyle S\) az \(\displaystyle n! \equiv q(n) \pmod{p}\) megoldásainak halmaza a \(\displaystyle H=\{k,k+1,...,k+N-1\}\) halmazon. A fenti lemma miatt van olyan \(\displaystyle 1\le d \le 2/\alpha\), hogy az \(\displaystyle S\) legalább \(\displaystyle N\alpha^2/4\) darab \(\displaystyle a\) elemére \(\displaystyle a+d\) is \(\displaystyle S\)-beli. Ez viszont azt jelenti, hogy

\(\displaystyle q(a)(a+1)(a+2)...(a+d)\equiv q(a+d)\pmod{p}. \)

Vegyük észre, hogy itt a \(\displaystyle q(x)(x+1)...(x+d)-q(x+d)\) polinom gyökeiről van szó. A polinom nem azonosan 0 mod \(\displaystyle p\). Jól ismert tétel, hogy mod \(\displaystyle p\) tekintve a polinomokat is igaz az, hogy legfeljebb annyi gyöke lehet mod \(\displaystyle p\), mint amennyi a foka, ami pedig \(\displaystyle \deg q+d\le \deg q+2/\alpha\). Tehát

\(\displaystyle \deg q+2/\alpha\ge N\alpha^2/4. \)

Innen pedig egyszerű átrendezéssel (és alkalmas, csak \(\displaystyle q\) fokától függő \(\displaystyle C\)-vel)

\(\displaystyle N\alpha^3\le 4\alpha \deg q + 8\le 4\deg q+ 8=C^3. \)

Ezzel pedig (ha S legalább két elemből áll) \(\displaystyle |S|=1+\alpha N\le 2CN^{-1/3}\cdot N=2CN^{2/3}\), és ez volt a bizonyítandó.

Statistics:

1 student sent a solution.
1 point:	1 student.

Problems in Mathematics of KöMaL, January 2022