Lefedőrendszer (számelmélet)

Lefedőrendszer a matematika számelmélet nevű ágában egy olyan kongruenciarendszer, amely tagjai megoldás(halmaz)ainak egyesítése lefedi a természetes (vagy ami ugyanaz, az egész) számok halmazát, azaz minden szám kielégít legalább egy kongruenciát a rendszerből.

A probléma másképpen is megfogalmazható: mivel egy adott kongruencia megoldásai számtani sorozatot alkotnak, lefedőrendszernek számtani sorozatok olyan rendszerét is nevezhetjük, melyek egyesítése a természetes (egész) számok halmaza.

Mellesleg, azért ugyanakkor fedi le a természetes és az egész számokat egy lefedőrendszer, mert ha egy természetes szám megoldása egy kongruenciának, akkor minden vele kongruens szám is megoldás, és ezek közt a negatív számok is ott vannak. Csak ha a természetes számokra építünk a definícióban, egy kongruencia megoldásain mindig nemnegatív számot értsünk, míg ha az egészekre, akkor a megoldásokat az egész számok körében keressük.

A formális definíció lentebb olvasható.

Történetükről

A lefedőrendszer fogalmát Erdős Pál vezette be a 30-as évek elején (első említése írott formában 1950-ből ismert (P. Erdős: On integers of the form 2k + p and some related problems, Summa Brasil. Math. 2 (1950), 113–123.).

Definíció

Egy

${\begin{cases}x_{1}\equiv a_{1}&{\pmod {m_{1}}}\\x_{2}\equiv a_{2}&{\pmod {m_{2}}}\\\ \ \ \ \dots \\x_{n}\equiv a_{n}&{\pmod {m_{n}}}\end{cases}}$

kongruenciarendszert (erősen) lefedőrendszernek nevezünk, ha érvényes a következő három dolog:

1. $n\in \mathbb {N} ^{+}$
2. $1<m_{1}<m_{2}<\dots <m_{n}$
3. $\forall k\in \mathbb {N} :\exists i\in \left\{1,2,\dots ,n\right\}\ :\ \ k\equiv a_{i}{\pmod {m_{i}}}$

A legkisebb, m₁ modulust nevezzük a rendszer kezdőmodulusának.

Megjegyezzük még, hogy a lefedőrendszerek – amint a definícióból látható – nem szimultán kongruenciarendszerek!

A lefedőrendszerek osztályzása

A rendszer számossága szempontjából

Alapértelmezésben egy lefedőrendszer (sőt egy kongruenciarendszer) mindig véges (sok kongruenciából áll), bár megindult a végtelen sok tagú lefedőrendszerek kutatása is (ld. irodalom). Ha mást nem mondunk, kongruenciarendszeren, lefedőrendszeren stb. mindig véges kongruenciarendszert értünk.

A modulusok szempontjából

Meglehetősen egyszerűen kezelhetőek, leírhatóak azok a lefedőrendszerek, melyek minden tagjának ugyanaz a modulusa. Ezért a lefedőrendszereket a modulusok ilyesfajta eloszlása szerint is célszerű osztályozni:

• Inkongruens (szűkebb értelemben vett) egy lefedőrendszer, ha a tagok modulusai mind 1-nél nagyobbak és különbözőek. Ha mást nem mondunk, ezeket értjük lefedőrendszeren (angol nyelvterületen szokás az incongruent és a distinct kifejezések használata is, rövidítés alakban DCS: distinct covering system).
• Újabban vizsgálnak tágabb értelemben vett vagy gyengén lefedőrendszereket is, melyek tagjainak modulusai szintén mind 1-nél nagyobbak, de nem követeljük meg, hogy mind különbözőek legyenek. Ezek legfontosabb alosztályát azon kongruenciarendszerek képezik, melyek modulusainak (esetleg végtelen) reciprokösszege 1 (szaturált rendszerek).

Utóbbiakon kívül még fontosak az olyan lefedőrendszerek, melyek minden modulusa páratlan (páratlan lefedőrendszerek) vagy összetett szám (kompozit fedőrendszerek), vagy négyzetmentes szám (négyzetmentes rendszerek).

A megoldások szempontjából

• Egy kongruenciarendszert idegen rendszernek nevezünk (angolul disjoint), ha minden természetes szám legfeljebb az egyik kongruenciáját elégíti ki.
• Ha egy (nem feltétlenül inkongruens) kongruenciarendszer lefedőrendszer is, azaz minden természetes szám megoldása legalább az egyik tagnak, meg idegen is, így legfeljebb az egyiknek megoldása, akkor minden szám a rendszer pontosan egy kongruenciának megoldása. Az ilyen (tehát idegen) lefedőrendszert pedig egzakt lefedőrendszernek is nevezzük, de előfordul az „idegen lefedőrendszer” (disjoint covering system, DCS) kifejezés is.

Példák

A triviális (gyengén) lefedőrendszer

Triviálisnak mondható konstruálni olyan lefedőrendszereket, melyek nem inkongruensek, azaz a modulusok nem mind különbözőek. Egy ilyen példa:

${\begin{cases}x_{1}\equiv 0&{\pmod {m}}\\x_{2}\equiv 1&{\pmod {m}}\\\ \ \ \ \dots \\x_{m}\equiv m-1&{\pmod {m}}\end{cases}}$

Egy 2 kezdőmodulusú inkongruens lefedőrendszer

Egy ilyen például (Erdős Pál konstruálta ezt is):

${\begin{cases}x_{1}\equiv 0&{\pmod {2}}\\x_{2}\equiv 0&{\pmod {3}}\\x_{3}\equiv 1&{\pmod {4}}\\x_{4}\equiv 1&{\pmod {6}}\\x_{5}\equiv 11&{\pmod {12}}\\\end{cases}}$

A mod(12) maradékosztályok mindegyike megoldása e rendszer valamely tagjának:

• az első kongruenciának a [0],[2],[4],[6],[8],[10] mod(12) osztályok;
• a másodiknak a [0],[3],[6],[9] mod(12) osztályok;
• a harmadiknak az [1], [5], [9] mod(12) osztályok;
• a negyediknek az [1], [7] mod(12) osztályok;
• az ötödiknek a [11] mod(12) osztály.

Az inkongruens lefedőrendszerekről

Ezek vizsgálatát (mint ahogy a lefedő kongruenciarendszerekét is) Erdős Pál kezdte meg. Először azt bizonyította e fogalom segítségével, hogy van olyan végtelen számtani sorozat, aminek tagjai nem állnak elő p+2^k alakban, ahol p prím.

Megoldatlan problémák

Erdős Pál vetette fel a következő, máig megoldatlan problémát: igaz-e, hogy tetszőleges nagy N számhoz létezik olyan inkongruens lefedőrendszer, amely első tagjának modulusa nem kisebb ennél (azaz melyre (N≤m₁)? Pongyolán fogalmazva: léteznek-e tetszőlegesen nagy modulusú inkongruens lefedőrendszerek? A megoldásért 1000 $-t ajánlott fel.

Könnyű olyan példákat készíteni, melyek legkisebb modulusa 2, illetve 3 (Erdős Pál megadott egy példát az utóbbira, ahol a modulusok 120 egyes osztói); és lehetséges olyanokat is, melyek legkisebb modulusa 4 (D. Swift, a modulusok 2880 egyes osztói), illetve lehetséges ez minden N≤20 számra is (S. L. G. Choi, 1971).

Egy újabb probléma, ha az összes modulus páratlanságát is megköveteljük. Erdős Pál és John Selfridge egy (2004-ben még megoldatlan) híres sejtése szerint nincs (1-nél nagyobb kezdőmodulusú) inkongruens lefedőrendszer, melynek minden modulusa páratlan; egyébként ha van, és minden modulus négyzetmentes, akkor a modulusok legkisebb közös többszörösének legalább 22 prímosztója van.

Szintén ismeretlen annak a sejtésnek a bizonyítása, ami szerint létezik csupa különböző, négyzetmentes modulusokból álló lefedő rendszer.

Egzakt (idegen), inkongruens lefedőrendszerek

Erdős sejtése

Szintén Erdős Pál tette közzé az 1950-es években azt a sejtést, hogy egy (legalább 2 kongruenciából álló) (véges) inkongruens lefedőrendszer nem lehet sohasem idegen (azaz nincs véges egzakt inkongruens lefedőrendszer). Tehát nem létezik véges egzakt inkongruens lefedőrendszer. Ezt az állítást Leon Mirsky, Donald Newmann, Harold Davenport, Richard Rado igazolták (megjegyzés: azért kötötte ki hogy legalább két kongruenciából álljon, mert régebben nem követelték meg egy inkongruens rendszertől, hogy kezdőmodulusa 1-nél nagyobb legyen. Ha ezt megtesszük, nem szükséges a „la. 2-tagú” feltétel, mert egy ilyen értelemben vett inkongruens rendszer mindig úgyis legalább két tagból kell hogy álljon; ellenben viszont szükséges kikötni).

Szemléletesen ez azt jelenti, hogy a lefedőrendszerek egzaktsága/idegensége és inkongruenciája – vagyis a megoldások és a modulusok egyértelműsége – „egymás ellen dolgoznak”: ha azt szeretnénk, hogy egy szám legfeljebb egy kongruenciának legyen megoldása, akkor a rendszerben nem lehet túl sok különböző modulus; ha meg különböző modulusokat szeretnénk, akkor a megoldások fognak ismétlődni.

A sejtés egy bizonyítása

Tegyük fel ugyanis, hogy létezik idegen inkongruens lefedőrendszer, legyen ez

${\begin{cases}x_{1}\equiv a_{1}&{\pmod {m_{1}}}\\x_{2}\equiv a_{2}&{\pmod {m_{2}}}\\\ \ \ \ \dots \\x_{n}\equiv a_{n}&{\pmod {m_{n}}}\end{cases}}$

($1<m_{1}<m_{2}<\dots <m_{n}$)

Ha az a_i számok helyére velük mod(m_i) kongruenseket írunk, az illető kongruencia megoldáshalmaza nem változik, és így ezek egyesítése sem. Ezért feltehető, hogy e számokat a legkisebb abszolút értékű pozitív tagú teljes maradékrendszerből választjuk, azaz hogy a_i≤m_i ha 1≤i≤n.

Legyen most t olyan (valós vagy komplex) szám, amelynek abszolút értéke kisebb mint 1! Tudjuk, hogy ez esetben érvényes

$1+t+t^{2}+\dots +t^{j}+\dots =\sum _{j=0}^{\infty }t^{j}={\frac {1}{1-t}}\ \ \ \left(|t|<1\right)$,

minthogy ez a mértani sorokra vonatkozó összegzési képlet. Vagyis a bizonyításhoz a komplex változós hatványsorokat fogjuk használni.

A fenti hatványsor kitevői az összes természetes számok. Feltevésünk szerint mindegyikük megoldása a fenti kongruenciarendszer egyik tagjának (mivel a rendszer fedőrendszer), és csakis az egyiknek (mivel a rendszer idegen). A bal oldal kitevőinek így egy osztályfelbontását kapjuk: minden kitevőt besorolhatunk egy és csak egy csoportba aszerint, hogy melyiket elégíti ki a rendszer tagjai közül. Ha a j kitevő az i-edik kongruenciát elégíti ki, tehát j ≡ a_i mod(m_i), akkor pontosan a j-vel kongruens számok adják e kongruencia többi megoldását (hiszen azok is kongruensek a_i-vel, és így a vele kongruens j-vel is a kongruencia tranzitivitása miatt), a legkisebb ilyen j-vel kongruens szám épp a kongruencia jobb oldalán álló, hiszen feltevésünk szerint ezt a legkisebb abszolút értékű pozitív tagú maradékrendszerből választottuk; tehát a fenti hatványsor felbontható a következő n darab összegre:

$t^{a_{i}}+t^{a_{i}+m_{i}}+t^{a_{i}+2m_{i}}+\dots +t^{a_{i}+zm_{i}}+\dots$ $=$ $\sum _{z=0}^{\infty }t^{a_{i}+zm_{i}}$ $=$ $\sum _{z=0}^{\infty }t^{a_{i}}t^{zm_{i}}$ $=$
$=$ $t^{a_{i}}\sum _{z=0}^{\infty }\left(t^{m_{i}}\right)^{z}$ $=$ ${\frac {1}{1-t^{m_{i}}}}$    ahol    $i\in \left\{1,2,\dots ,n\right\}$

Eszerint

${\frac {1}{1-t}}=\sum _{j=0}^{\infty }t^{j}=\sum _{i=1}^{n}{\frac {1}{1-t^{m_{i}}}}$ ,     (*)

Emlékeztetünk arra, hogy ha feltevéseink igazak, akkor a fenti egyenlőségnek minden, a |t|<1 követelményt teljesítő t∈ℂ komplex számra teljesülnie kell. Egy ellentmondást úgy találunk, hogy választunk egy olyan 1 abszolút értékű komplex számot, amelyhez határértékként tartva, a fenti egyenlő kifejezések határértéke nem lesz egyenlő. Könnyen található olyan komplex szám az ilyenek közt, melyre ez teljesül, mégpedig az „első” m_n-edik egységgyök (vagy általában egy olyan primitív egységgyök, amelynek rendje a kongruenciarendszer legnagyobb modulusa):

$\varepsilon =\cos \left({\frac {2\pi }{m_{n}}}\right)+\mathbf {i} \sin \left({\frac {2\pi }{m_{n}}}\right)$ .

Ha ugyanis t→ε, akkor (*) legbaloldalibb bal oldala tart az ${\frac {1}{1-\varepsilon }}$-hoz, tehát egy véges határértékhez; míg (*) legjobboldalibb jobb oldala egy olyan n-tagú összeg, melynek n-1 db. tagja (i<n) esetén szintén véges számhoz tart (mivel ε-t primitív egységgyöknek vettük, m_n-t pedig a legnagyobb modulusnak, és egy nagy számra nézve primitív egységgyök az összes kisebb számra nézve, a primitivitás definíciójából adódóan, nem egységgyök); de az n-edik tag az ${\frac {1}{1-\varepsilon ^{m_{n}}}}={\frac {1}{1-1}}={\frac {1}{0}}$-hoz, azaz végtelenhez. Tehát erre az ε komplex számra az egyenlőség nem érvényes, holott az kellene hogy legyen, ha a kongruenciarendszer idegen inkongruens lefedőrendszer lenne. Egyszóval ez ellentmondás, és így a rendszer nem idegen, vagy nem inkongruens lefedőrendszer. QED.

Az egzakt/idegen lefedőrendszerekről

A fentebbi eredmények szerint egy lefedőrendszer vagy egzakt, vagy inkongruens, de a kettő egyszerre nem lehet. Az egzakt rendszerek modulusaiban ismétlődés kell hogy legyen.

Š. Znám és M. Newmann egymástól függetlenül belátták továbbá, hogy egy egzakt lefedőrendszer legnagyobb modulusa, m_n, legalább p(m_n)-szer ismétlődik, ahol p(x):Z→N az $x\in \mathbb {Z}$ legkisebb pozitív prímosztóját jelölő számelméleti függvény.

Marc A. Berger, Alexander Felzenbaum és Aviezri Fraenkel teljesen karakterizálta azokat az egzakt rendszereket, melyekben pontosan egyféle ismétlődő modulus van, de az ismétlődések száma (multiplicitás) nem nagyobb kilencnél; M. Zeleke és J. Simpson ezt a leírást folytatta tíz, tizenegy és tizenkettő multiplicitásra.

Általánosítások

1996-ban T. Cochrane és G. Myerson egy újfajta, „kétdimenziós” lefedőrendszer-fogalmat vezetett be. Jelölje H_m(a,b) az ax+by ≡ 0 mod(m) megoldásait, ez tehát Z²-beli számpárok halmaza. A fenti alakú kétismeretlenes kongruenciák egy rendszerét homogén lefedőrendszernek nevezzük, ha a megoldáshalmazok egyesítése Z². Megmutatták továbbá, hogyan lehet egy kompozit inkongruens lefedőrendszerből homogén lefedőrendszert konstruálni. Nem sokkal később Boping Jin és G. Myerson megmutatta, hogy ezzel a konstrukcióval minden homogén lefedőrendszer egy megfelelő kompozit inkongruens lefedőrendszerből származtatható.

Érdekességek

Erdős Pál a lefedőrendszereket kedvenc felfedezései között tartotta számon, mert ezek vetik fel a legérdekesebb problémákat (Perhaps my favorite problem of all concerns covering systems. (Erdős P.: Some of my favorite problems and results, in: The mathematics of Paul Erdős, I, 47–67., Algorithms Combin., 13, Springer, Berlin, 1997., ld. Zhi-Wei Sun: A unified theory of zero-sum problems, subset sums and covers of Z, 4. old.)

Hivatkozások

Irodalom

• Szalay Mihály: Számelmélet. Speciális Matematika Tankönyvek sorozat. Nemzeti Tankönyvkiadó, Typotex, 1998. ISBN 963-9132-25-X .
• Ethan Lewis cikke a végtelen lefedőrendszerekkel kapcsolatos alapkérdésekről (1996) (PDF)
• A témában megjelent cikkek egy jegyzéke Archiválva 2007. szeptember 29-i dátummal a Wayback Machine-ben (PDF)
• Covering systems and their connection to zero-sums Archiválva 2007. szeptember 29-i dátummal a Wayback Machine-ben (Zhi-Wei Sun) (PDF) A lefedőrendszerek és a nullösszeg-problémák kapcsolatáról
• M. Newman: Roots of unity and covering sets. Math. Ann., 191 (1971), 279-282.