Lefedőrendszer (számelmélet)

A Wikipédiából, a szabad enciklopédiából

Lefedőrendszer, röviden LR 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[szerkesztés | forrásszöveg szerkesztése]

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.).[1]

Definíció[szerkesztés | forrásszöveg szerkesztése]

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}: \exist i \in \left\{ 1,2,\dots ,n \right\} \ : \ \ k \equiv a_{i} \pmod{m_{i}}

A legkisebb, m1 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[szerkesztés | forrásszöveg szerkesztése]

A rendszer számossága szempontjából[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 (ILR), 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[szerkesztés | forrásszöveg szerkesztése]

  • 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 exakt lefedőrendszernek (ELR) is nevezzük, de előfordul az „idegen lefedőrendszer” (disjoint covering system, DCS) kifejezés is.

Példák[szerkesztés | forrásszöveg szerkesztése]

A triviális (gyengén) lefedőrendszer[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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+2k alakban, ahol p prím.

Megoldatlan problémák[szerkesztés | forrásszöveg szerkesztése]

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

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 J. L. 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.[4]

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.

Exakt (idegen), inkongruens lefedőrendszerek[szerkesztés | forrásszöveg szerkesztése]

Erdős sejtése: nem létezik VEILR[szerkesztés | forrásszöveg szerkeszté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 exakt inkongruens lefedőrendszer). Tehát nem létezik VEILR (véges exakt inkongruens lefedőrendszer). Ezt az állítást L. Mirsky, D. Newmann, H. Davenport, R. Rado igazolták[5] (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[szerkesztés | forrásszöveg szerkesztése]

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 ai számok helyére velük mod(mi) 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 ai≤mi 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 ≡ ai mod(mi), akkor pontosan a j-vel kongruens számok adják e kongruencia többi megoldását (hiszen azok is kongruensek ai-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ő” mn-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) + \bold{i} \sin \left( \frac{2 \pi}{m_{n}} \right) .

Ha ugyanis tε, akkor (*) legbaloldalibb baloldala tart az  \frac{1}{1-\varepsilon} -hoz, tehát egy véges határértékhez; míg (*) legjobboldalibb jobboldala 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, mn-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[szerkesztés | forrásszöveg szerkesztése]

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, mn, legalább p(mn)-szer ismétlődik, ahol p(x):ZN az x \in \mathbb Z legkisebb pozitív prímosztóját jelölő számelméleti függvény.[6]

M. A. Berger, A. Felzenbaum és A. 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.[7]

Általánosítások[szerkesztés | forrásszöveg szerkesztése]

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

Érdekességek[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  1. Ld. Zhi-Wei Sun: A unified tbeory of zero-sum problems, subset sums and covers of Z, 4. old.; v. 2007. augusztus 6. 14:30.
  2. 1950-es dolgozatában, címe: On integers of the form 2k+p and some related problems; (Summa Brasil. Math. 2 (1950), 113.-123. o.), ld. még: Filaseta-Ford-Konyagin-Pomerance-Yu: Sieving by Large Integers and covering systems of congruences; (pdf), 4. o.; v. 2007. augusztus 6. 14:32.
  3. Sárközy András: Farewell, Paul. Acta Arithmetica, 81 (Varsó, 1997); (pdf). v.2007. augusztus 6. 15:57.
  4. Somg Guo, Zhi-Wei Sun: On odd covering systems with distinct moduli; 1. o.; v. 2007. augusztus 6. 14:42.
  5. M. Newman: Roots of unity and covering sets, Math. Ann., 191 (1971) 279.-282.; ld. a következő egyetemi jegyzetet: [1] (pdf, 15. o., v. 2007. augusztus 6. 15:06.)
  6. Š. Znám: On exactly covering systems of arithmetical sequences; Math. Ann., 180 (1969), 227.-232. o.;
    M. Newman: Roots of unity and covering systems; Math. Ann. 191 (1971) 279.-282.
  7. Melkamu Zeleke – Jamie Simpson: On disjopint covering systems with precisely one repeated modulus. Appl. Math. 23 (1999), no. 3, 322-332.; ps, v. 2007. augusztus 6.
  8. Cochrane-Myerson: Covering congruences in higher dimensions; Rocky Mountain J. Math., 26 (1996); 77.-81. o.
  9. Scott Jenkin – Jamie Simpson: [Composite covering systems of minimum cardinality]; IntegersElectronic Journal of Combinatorial Number Theory (kombinatorikai e-folyóirat); 3 (2003); (pdf/div/latex); v. 2007. augusztus 6. 15:42.

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • M. Newman: Roots of unity and covering sets. Math. Ann., 191 (1971), 279-282.