Lefedőrendszer

A Wikipédiából, a szabad lexikonbó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ó.

Tartalomjegyzék

1 Történetükről
2 Definíció
3 A lefedőrendszerek osztályzása
4 Példák
- 4.1 A triviális (gyengén) lefedőrendszer
- 4.2 Egy 2 kezdőmodulusú inkongruens lefedőrendszer
5 Az inkongruens lefedőrendszerekről
- 5.1 Megoldatlan problémák
- 5.2 Exakt (idegen), inkongruens lefedőrendszerek
  - 5.2.1 Erdős sejtése: nem létezik VEILR
  - 5.2.2 A sejtés egy bizonyítása
6 Érdekességek
7 Irodalom

[szerkesztés] Történetükről

A lefedőrendszer fogalmát Erdős Pál vezette be 1950-ben (P. Erdős: On integers of the form 2k + p and some related problems, Summa Brasil. Math. 2 (1950), 113.–123., ld. Zhi-Wei Sun: A unified tbeory of zero-sum problems, subset sums and covers of Z, 4. old), egy, az inkongruens lefedőrendszerekről szóló dolgozatában.

[szerkesztés] Definíció

Egy

$\begin{cases} x_{1} \equiv a_{1} & \mbox{mod}(m_{1}) \\ x_{2} \equiv a_{2} & \mbox{mod}(m_{1}) \\ \ \ \ \ ... \\ x_{n} \equiv a_{n} & \mbox{mod}(m_{n}) \end{cases}$

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

$n \in \mathbb{N}^{+}$
$1 < m 1 < m 2 < ... < m n$
$\forall k \in \mathbb{N}: \exist i \in \left\{ 1,2,...,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!

[szerkesztés] A lefedőrendszerek osztályzása

[szerkesztés] 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.

[szerkesztés] 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 (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).

[szerkesztés] 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 exakt lefedőrendszernek (ELR) is nevezzük.

[szerkesztés] Példák

[szerkesztés] 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 & \mbox{mod}(m) \\ x_{2} \equiv 1 & \mbox{mod}(m) \\ \ \ \ \ ... \\ x_{m} \equiv m-1 & \mbox{mod}(m) \end{cases}$

[szerkesztés] Egy 2 kezdőmodulusú inkongruens lefedőrendszer

Egy ilyen pl. (Erdős Pál konstruálta ezt is):

$\begin{cases} x_{1} \equiv 0 & \mbox{mod}(2) \\ x_{2} \equiv 0 & \mbox{mod}(3) \\ x_{3} \equiv 1 & \mbox{mod}(4) \\ x_{4} \equiv 1 & \mbox{mod}(6) \\ x_{5} \equiv 11 & \mbox{mod}(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.

[szerkesztés] 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.

[szerkesztés] 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 ILR, 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?

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

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.

[szerkesztés] Exakt (idegen), inkongruens lefedőrendszerek

[szerkesztés] Erdős sejtése: nem létezik VEILR

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 (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).

[szerkesztés] 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} & \mbox{mod}(m_{1}) \\ x_{2} \equiv a_{2} & \mbox{mod}(m_{1}) \\ \ \ \ \ ... \\ x_{n} \equiv a_{n} & \mbox{mod}(m_{n}) \end{cases}$

( $1 < m 1 < m 2 < ... < 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}+...+t^{j}+ ... = \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}}+ ... +t^{a_{i}+zm_{i}}+ ...$ $=$ $\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, ... , 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) + \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, 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.

[szerkesztés] É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.)

[szerkesztés] Irodalom

Szalay Mihály: Számelmélet. Speciális Matematika Tankönyvek sorozat. Nemzeti Tankönyvkiadó, Typotex, 1998. ISBN 963 9132 25 X .
Az inkongruens idegen lefedőrendszerekről szóló tétel bizonyításának forrása (PDF)
Ethan Lewis cikke a végtelen lefedőrendszerekkel kapcsolatos alapkérdésekről (1996) (PDF)
A témában megjelent cikkek egy jegyzéke (PDF)
Páratlan lefedőrendszerekről (Song Guo, Zhi-Wei Sun) (PDF)
Covering systems and their connection to zero-sums (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.

A lap eredeti címe "http://hu.wikipedia.org../../../l/e/f/Lefed%C5%91rendszer.html"

Kategóriák: Számelmélet | Matematikai tételek