Problem B. 5293. (January 2023)
B. 5293. Let \(\displaystyle p\) denote a prime number. What is the largest number of polynomials with integer coefficients such that there are no pairs of polynomials such that the value of their difference is divisible by \(\displaystyle p^2\) at every integer?
Proposed by P.\(\displaystyle \,\)P. Pach, Budapest
(6 pont)
Deadline expired on February 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Megmutatjuk, hogy a válasz \(\displaystyle p^{3p}\).
Legyen \(\displaystyle f(x)=a_nx^n+\dots+a_2x^2+a_1x+a_0\) egy egész együtthatós polinom. Tekintsük \(\displaystyle f(x_0+kp)\)-t modulo \(\displaystyle p^2\) (egyelőre \(\displaystyle x_0\) és \(\displaystyle k\) bármely egész lehet). Ehhez először meghatározzuk \(\displaystyle (x_0+kp)^t\) értékét a binomiális tétel felhasználásával \(\displaystyle t>0\) esetén:
\(\displaystyle (x_0+kp)^t\equiv x_0^t+tkpx_0^{t-1} \pmod{p^2},\)
hiszen a további tagokban \(\displaystyle p\) kitevője már legalább 2. Ha pedig \(\displaystyle t=0\), akkor \(\displaystyle (x_0+kp)^t=x_0^t\), második tag ekkor nincs. Ezek alapján
| \(\displaystyle f(x_0+kp)=\sum\limits_{t=0}^n a_t(x_0+kp)^t\equiv \sum\limits_{t=0}^n a_tx_0^t+kp\sum\limits_{t=1}^n ta_tx_0^{t-1} \equiv f(x_0)+kpf'(x_0) \pmod {p^2}, \) | \(\displaystyle {(*)}\) |
ahol
\(\displaystyle f'(x_0):=\sum\limits_{t=1}^n ta_tx_0^{t-1}.\)
(Formálisan \(\displaystyle f'\) éppen \(\displaystyle f\) deriváltja, de most nem \(\displaystyle \mathbb{R}\to \mathbb{R}\) függvényként tekintünk rá.)
A \(\displaystyle (*)\) kongruenciából már látható, hogy ha előírjuk \(\displaystyle f(x_0) \pmod{p^2}\) és \(\displaystyle f'(x_0)\pmod {p}\) értékét \(\displaystyle x_0=0,1,\dots,p-1\) esetén, az már meghatározza \(\displaystyle f(x_0+kp)\pmod {p^2}\) értékét minden \(\displaystyle k\)-ra (és minden \(\displaystyle 0\leq x_0\leq p-1\)-re), vagyis minden egész \(\displaystyle x\) helyen meghatározza \(\displaystyle f(x) \pmod{p^2}\) értékét. Ez azt jelenti, hogy ha valamely \(\displaystyle f_1\) és \(\displaystyle f_2\) polinomok különbsége nem osztható \(\displaystyle p^2\)-tel minden egész helyen, akkor az \(\displaystyle f_1(x_0) \pmod{p^2}\) és \(\displaystyle f_1'(x_0)\pmod {p}\) értékek sorozata nem lehet ugyanaz, mint az \(\displaystyle f_2(x_0) \pmod{p^2}\) és \(\displaystyle f_2'(x_0)\pmod {p}\) értékek sorozata (\(\displaystyle 0\leq x_0\leq p-1\)-re). A maradékok ilyen sorozata \(\displaystyle (p^2)^pp^p=p^{3p}\)-féle lehet, így ennél több polinom biztosan nem adható meg.
Az is világos, hogy ha az \(\displaystyle f_1\) és \(\displaystyle f_2\) polinomokra a maradékok fenti (\(\displaystyle 2p\) hosszú) sorozata nem egyezik meg, akkor különbségük nem lehet minden egész helyen \(\displaystyle p^2\)-tel osztható. Ha ugyanis
\(\displaystyle f_1(x_0)+kpf_1'(x_0)\equiv f_2(x_0)+kpf_2'(x_0) \pmod {p^2}\)
minden \(\displaystyle 0\leq x_0\leq p-1\) és \(\displaystyle k\in \mathbb{Z}\) esetén, akkor \(\displaystyle k=0\) választás alapján \(\displaystyle f_1(x_0)\equiv f_2(x_0) \pmod{p^2}\) minden \(\displaystyle 0\leq x_0\leq p-1\)-re, és így \(\displaystyle k=1\) szerint \(\displaystyle pf'_1(x_0)\equiv pf'_2(x_0)\pmod{p^2}\), amiből \(\displaystyle f'_1(x_0)\equiv f'_2(x_0)\pmod{p}\), szintén minden \(\displaystyle 0\leq x_0\leq p-1\) mellett.
Ahhoz, hogy belássuk, megadható \(\displaystyle p^{3p}\) darab polinom megfelelő módon, elég megmutatni, hogy az \(\displaystyle a_i,b_i\) maradékok tetszőleges sorozata esetén van olyan \(\displaystyle f\) polinom, melyre \(\displaystyle f(i)\equiv a_i \pmod{p^2}\) és \(\displaystyle f'(i)\equiv b_i \pmod {p}\) teljesül minden \(\displaystyle i=0,1,\dots,p-1\) esetén.
Keressük \(\displaystyle f\)-et az alábbi alakban:
\(\displaystyle f(x)=\sum\limits_{i=0}^{p-1}Q_i(x)R_i(x),\)
ahol
\(\displaystyle Q_i(x)=c_i(x-i)+d_i\)
és
\(\displaystyle R_i(x)=\prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (x-j)^2.\)
Legyen \(\displaystyle 0\leq i \leq p-1\) tetszőleges. Tekintsük először \(\displaystyle f(i) \pmod{p^2}\) értékét. Az \(\displaystyle f\)-et adó \(\displaystyle p\)-tagú összegben egyetlen kivételtől eltekintve mindegyik szorzatban szerepel az \(\displaystyle (x-i)^2\) tényező, így ezek a tagok \(\displaystyle p^2\)-tel oszthatók. Így
\(\displaystyle f(i)\equiv Q_i(i)R_i(i)\equiv d_i\prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (i-j)^2\pmod {p^2}.\)
Mivel a \(\displaystyle \prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (i-j)^2\) szorzat nem osztható \(\displaystyle p\)-vel, ezért \(\displaystyle d_i\) alkalmas megválasztásával elérhető, hogy
\(\displaystyle f(i)\equiv d_i\prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (i-j)^2\equiv a_i\pmod {p^2}\)
legyen. Ha ugyanis \(\displaystyle d_i\) helyére egy (mod \(\displaystyle p^2\)) teljes maradékrendszert helyettesítünk, akkor a szorzat is egy teljes maradékrendszert alkot mod \(\displaystyle p^2\), hiszen \(\displaystyle p\nmid v\) esetén \(\displaystyle u_1v\equiv u_2v\pmod {p^2}\) pontosan akkor teljesül, ha \(\displaystyle u_1\equiv u_2\pmod {p^2}\). Rögzítsük tehát \(\displaystyle d_i\) értékét úgy, hogy \(\displaystyle f(i)\equiv a_i\pmod {p^2}\) legyen.
Térjünk rá \(\displaystyle f'(i) \pmod{p}\) értékére. Korábban már megjegyeztük, hogy \(\displaystyle f'\) éppen \(\displaystyle f\) deriváltja. A derivált tulajdonságai alapján egy összeg deriváltja az összeadandók deriváltjának összege, továbbá, ha egy polinomnak egy szám legalább kétszeres gyöke, akkor a deriváltjának is gyöke. Ezért
\(\displaystyle f'(i)=\sum\limits_{j=0}^{p-1} \left(Q_j'(i)R_j(i)+Q_j(i)R_j'(i)\right)=Q_i'(i)R_i(i)+Q_i(i)R_i'(i)=c_iR_i(i)+d_iR_i'(i),\)
hiszen \(\displaystyle j\ne i\) esetén \(\displaystyle R_j(i)=R'_j(i)=0\).
Mivel \(\displaystyle R_i(i)\not\equiv 0\pmod {p}\), ezért \(\displaystyle c_i\) megválasztható úgy, hogy \(\displaystyle f'(i)\equiv b_i\pmod {p}\) legyen. (Egy mod \(\displaystyle p\) teljes maradékrendszert helyettesítve \(\displaystyle c_i\) helyére \(\displaystyle c_iR_i(i)\), és így \(\displaystyle c_iR_i(i)+d_iR'_i(i)\) is egy-egy mod \(\displaystyle p\) teljes maradékrendszeren fut végig.) Tehát valóban minden \(\displaystyle 2p\) hosszú maradéksorozathoz megadható megfelelő polinom.
Ezzel igazoltuk, hogy legfeljebb \(\displaystyle p^{3p}\) darab polinom adható meg a feltételeknek megfelelően (és ennyi valóban meg is adható.)
Statistics:
12 students sent a solution. 6 points: Csonka Illés, Czirják Márton Pál, Szakács Ábel, Varga Boldizsár. 5 points: Fülöp Csilla, Wiener Anna. 1 point: 2 students. 0 point: 3 students.
Problems in Mathematics of KöMaL, January 2023