– avagy miért nem lehetünk tetszőlegesen hanyagok?
Bevezetés: Egy 10 dolláros sejtés útja
A lefedőkongruenciák elmélete Erdős Pál egyik legkedvesebb kutatási területe volt. A történet 1950-ben kezdődött, amikor Erdős egy Romanov által felvetett problémát vizsgált: létezik-e pozitív sűrűségű halmaza azoknak az egészeknek, amelyek nem állnak elő \(p + 2^k\) alakban? Erdős válasza igen volt, és a bizonyításhoz egy olyan konstrukciót használt, ahol minden egész számot lefedett néhány kongruenciaosztállyal, melyek modulusai különbözőek és 1-nél nagyobbak voltak.
Definíció. Kongruenciák egy véges \(\mathcal{M} = \{a_i \pmod{m_i}\}_{i=1}^k\) halmazát lefedőrendszernek nevezzük, ha minden egész szám teljesíti legalább az egyik kongruenciát. A rendszer nem-triviális, ha a modulusok egynél nagyobbak és különböznek (\(1 < m_1 < m_2 < \dots < m_k)\).
Ekkor született meg a kérdés, amely évtizedekig lázban tartotta a számelmélészeket: létezik-e lefedőrendszer tetszőlegesen nagy legkisebb modulussal (\(m_1\))? Erdős annyira bízott a válaszban, hogy kezdetben 10, majd később 1000 dollárt ajánlott a megoldásért. Meggyőződése volt, hogy \(m_1\) bármilyen nagy lehet.
Évtizedekig csak szerény előrelépések történtek. A 2000-es évek elején a valószínűségi módszerek, különösen a Lovász-lokális lemma hozott új reményt. A lemma lényege, hogy ha „rossz” események (például, hogy egy szám fedetlen marad) csak gyengén függenek össze, akkor van esély a lefedésre. Azonban a teljes sikerre 2015-ig várni kellett.
Bob Hough [4] alapjaiban rázta meg a területet, amikor bebizonyította az ellenkezőjét annak, amit Erdős hitt: \(m_1\) nem nőhet minden határon túl. Hough iteratív szitálási eljárása megmutatta, hogy minden lefedőrendszerben \(m_1\) korlátos (\(m_1 \le 10^{16}\)). Ezt a korlátot Balister, Bollobás, Morris, Sahasrabudhe és Tiba [1] 2022-ben a Lovász-lokális lemma finomításával szorították le a ma is érvényes \(616\,000\)-re.
De mi történik a sorban következő modulussal? Megteheti-e egy lefedőrendszer, hogy \(m_1\) értékét alacsonyan tartja (például \(m_1=2\)), miközben \(m_2\) értékét a végtelenbe tolja? Bár a szakirodalom [5, 2] már megválaszolta a kérdést az általános j-edik modulusra is, és Cummings, Filaseta, valamint Trifonov [2] egy elegáns, rövid és elemi indukciós bizonyítást is adnak a probléma általános esetére, de az absztrakciós szint esetenként próbára teheti a témával ismerkedő olvasót.
Ebben a jegyzetben egy elemi, mindössze egyoldalas bizonyítást adunk \(m_2\) korlátosságára. Megközelítésünk elkerüli a komplex szitaelméleti apparátust, helyette a struktúra belső ellentmondásaira és a lefedőrendszerek önhasonlóságára épít.
A bizonyítás
Tegyük fel indirekt, hogy a második modulus, \(m_2\), tetszőlegesen nagy lehet. Legyen \(C_1\) az első modulus ismert felső korlátja (pl. \(616\,000\)). Tekintsük az összes olyan \(\mathcal{M} = \{a_i \pmod{m_i}\}_{i=1}^k\) lefedőrendszert, amelyre \(m_2 > C_1^2\). Mivel \(m_1 \le C_1\), ezért véges sok választásunk van \(m_1\) értékére. Válasszunk egy olyan rendszert, amelyben \(m_1\) értéke maximális az adott feltételek mellett. A modulusok nagyságrendi sorrendjéről feltehető, hogy \(m_1<m_2<m_3<\dots<m_k\).
Használjuk ki az indirekt feltevést egy segédrendszer konstrukciójához! Eszerint létezik egy \(\mathcal{T} = \{b_s \pmod{T_s}\}_{s=1}^v\) lefedőrendszer, ahol a második modulus, \(T_2\) tetszőlegesen nagy. Válasszuk \(T_2\)-t úgy, hogy teljesüljön a \[\displaystyle T_2 > \frac{m_k}{m_1} \] egyenlőtlenség, ahol \(m_k\) az eredeti \(\mathcal{M}\) rendszerünk legnagyobb modulusa.
Cseréljük le \(\mathcal{M}\) első tagját, az \(a_1 \pmod{m_1}\) kongruenciát a \(\mathcal{T}\) rendszer segítségével az alábbi kongruencia-halmazra: \[\displaystyle \{a_1 + b_s m_1 \pmod{m_1 T_s} : 1 \le s \le v\} \] Az új rendszer (\(\mathcal{M}’\)) szintén lefedőrendszer lesz. Az új modulusok halmaza: \[ \mathcal{M}_{mod} = \{m_2, m_3, \dots, m_k\} \cup \{m_1 T_1, m_1 T_2, \dots, m_1 T_v\}. \]
Bebizonyítjuk, hogy az új modulusok egyértelműen különböznek. Mivel \(T_1 > 1\), ezért \(m_1 T_1 > m_1\). Vizsgáljuk meg az új modulusok sorrendjét:
1. \(m_1 T_1 < m_1 T_2\), és választásunk szerint \(m_1 T_2 > m_k\).
2. Mivel \(m_1 \le C_1\) és \(T_1\) egy lefedőrendszer első modulusa (tehát \(T_1 \le C_1\)), így \(m_1 T_1 \le C_1^2 < m_2\). Ezáltal a modulusok sorrendje: \[\displaystyle m_1T_1<m_2<m_3<\dots<m_k<m_1T_2<m_1T_3<\dots<m_1T_v. \]
Ez azt jelenti, hogy az új rendszerben a legkisebb modulus \(m_1′ = m_1 T_1\). Mivel \(m_2′ = m_2 > C_1^2\), az új \(\mathcal{M}’\) rendszer teljesíti a kezdeti kritériumokat. Azonban \(m_1′ = m_1 T_1 > m_1\) közvetlenül ellentmond \(m_1\) maximalitásának az eredeti rendszerben.\(\Box\)
Hivatkozások
[1] P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe, M. Tiba, On the Erdős covering problem: the density of the uncovered set, Invent. Math. 228 (2022), 377–414.
[2] M. Cummings, M. Filaseta, O. Trifonov, An upper bound for the minimum modulus in a covering system with squarefree moduli, Acta Math. Hung. 175(1) (2025), 1–25.
[3] P. Erdős, On integers of the form \(2^k + p\) and some related problems, Summa Brasil. Math., 2 (1950), 113–123.
[4] B. Hough, Solution of the minimum modulus problem for covering systems, Ann. Math. (2) 181 (1) (2015), 361–382.
[5] J. Klein, D. Koukoulopoulos, S. Lemieux, On the \(j\)-th smallest modulus of a covering system with distinct moduli, Int. J. Number Theory 20 (2024), 471–479.
Gyarmati Katalin
ELTE Algebra és Számelmélet Tanszék
