Cím:	Rácsok és csoportok 1.
Szerző(k):	Kiss Emil ,  Simányi Nándor
Füzet:	2018/január, 2 - 11. oldal	PDF  |  MathML
Hivatkozás(ok):	2018/március: Rácsok és csoportok 2.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   1. Bevezetés Ez a cikk nem könnyű olvasmány. Meg szeretnénk mutatni, hogy a mélyebb matematikai háttér hogyan segíthet egy probléma elemzésében. Ehhez képet kell adnunk magáról a háttérről, ami nem egyszerű, mert ezek a fogalmak és tételek matematikai érettséget igényelnek, tipikusan az egyetemi tananyagban szerepelnek. Egy olimpiai feladat jó alkalmat kínál az első randevúra, még ha a komolyabb ismerkedés későbbre marad is. A 2017-es Matematikai Diákolimpia hatodik feladata a következő volt.   1.1. feladat. Egy egész számokból álló $\left(x\mathrm{,}y\right)$ rendezett párt primitív rácspontnak nevezünk, ha $x$ és $y$ legnagyobb közös osztója $1$. Ha adott primitív rácspontok egy véges $S$ halmaza, bizonyítsuk be, hogy van olyan $n$ pozitív egész, és vannak olyan $z_0\mathrm{,}{z}_1\mathrm{,}\text{...}\mathrm{,}{z}_n$ egészek, hogy minden $\left(x\mathrm{,}y\right)$ $S$-beli pontra teljesül $\begin{array}{c}{\displaystyle z_0{x}^n+z_1{x}^{n-1}y+z_2{x}^{n-2}{y}^2+\text{...}+z_{n-1}x{y}^{n-1}+z_n{y}^n=1.}\end{array}$   A sokféle lehetséges megközelítés egyike a következő. Legyenek az $S$ halmaz elemei az $\left(a_1\mathrm{,}{b}_1\right)\mathrm{,}\text{...}\mathrm{,}\left(a_k\mathrm{,}{b}_k\right)$ párok. Tekintsük a következő oszlopvektorokat: A kérdés az, hogy előáll-e a konstans $1$ oszlopvektor a ${\text{v}}_0\mathrm{,}\text{...}\mathrm{,}{\text{v}}_n$ vektorok egész együtthatós lineáris kombinációjaként. (Az $n$ számot mi választhatjuk.) Fölmerülnek további kérdések is. Mely $n$ számok lesznek jók? Miért pont a konstans $1$ vektor szerepel a jobb oldalon? Meg tudjuk-e határozni, hogy általában mely vektorok állnak elő ilyen lineáris kombinációként? Előfordulhat-e, hogy az összes egész koordinátájú vektor előáll? Az egész vektorok hány százaléka áll így elő? Ezek a lineáris kombinációk egy rácsot alkotnak. Az alábbiakban algebrai és geometriai módszerekkel is vizsgáljuk majd a hasonló rácsokat, és megválaszoljuk a fenti kérdéseket. Speciálisan a feladat állítását is belátjuk. A rácsokat rengeteg helyen alkalmazzák a matematikában. A legsűrűbb faültetés feladata háromszögráccsal oldható meg. Minkowski rácsgeometriai tételének egy számelméleti alkalmazását mi is fölidézzük a 6. szakaszban. Ugyancsak rácsokat használ a Lenstra‐Lenstra‐Lovász algoritmus (lásd [5]) polinomok szorzatra bontására. A sík rácsairól Erdős Pál és Surányi János [1] könyvében olvashatunk bevezetőt. Köszönetet mondunk Gróf Andreának és Moussong Gábornak értékes tanácsaikért.   2. Az előismeretek összefoglalása Számelméletből Freud Róbert és Gyarmati Edit [3] tankönyvét érdemes tanulmányozni. Feltételezzük, hogy az Olvasó tud bánni kongruenciákkal, ismeri a $\text{mod}m$ számolás fogalmát, az Euler‐Fermat-tételt, és azt a tényt, hogy egész számok legnagyobb közös osztója fölírható e számok egész együtthatós lineáris kombinációjaként.   2.1. Lineáris algebra. Ismertnek tételezzük föl Freud Róbert [2] tankönyvének első fejezetei alapján a valós számok fölötti vektorok, mátrixok és determinánsok alaptulajdonságait (lineáris függetlenség, rang, bázis, előjeles aldeterminánsok, kifejtés és ferde kifejtés, mátrixműveletek, az inverz mátrix képlete, Vandermonde-determináns). A determinánsokra vonatkozó eredmények akkor is érvényesek, ha a determináns elemei nem számok, hanem például polinomok, hiszen minden számolás ugyanaz, és polinomokból törteket is képezhetünk. Ha $p$ prímszám, akkor $\text{mod}p$ számolva is érvényben maradnak a determinánsról tanult állítások. Most determinánsok Laplace-kifejtését, és a Cauchy‐Binet formulákat idézzük föl. A bizonyítások elolvashatók Kiss Emil honlapján1. (Ugyanebben a dokumentumban mátrixok invertálására is található egy gyors, eliminációs eljárás.) Legyen $M$ egy $k\times n$-es mátrix. Az $M$ egy $r\times r$-es aldeterminánsán azt értjük, hogy kiválasztunk $r$ sort és oszlopot, és vesszük az ezek metszéspontjaiban álló elemek alkotta mátrix determinánsát. Ha a sorok, illetve oszlopok indexei $I=\left\{i_1\mathrm{,}\text{...}\mathrm{,}{i}_r\right\}$ és $J=\left\{j_1\mathrm{,}\text{...}\mathrm{,}{j}_r\right\}$, akkor a kapott aldetermináns jele $M_{I\mathrm{,}J}$, a hozzá tartozó előjel $\text{sg}\left(I\mathrm{,}J\right)={\left(-1\right)}^{i_1+\text{...}+i_r+j_1+\text{...}+j_r}$.   2.1. tétel. Legyen $M$ egy $k\times k$-as mátrix. Rögzítsük az $r$ elemű $I\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}k\right\}$ halmazt tetszőlegesen, és jelölje $I\text{'}$ az $I$ komplementumát az $\left\{\mathrm{1,2,}\text{...}\mathrm{,}k\right\}$ halmazra nézve. Ekkor az $M$ determinánsának Laplace-féle kifejtése (ahol az összegzés az oszlopok $r$ elemű $J$ részhalmazaira terjed ki, tehát $\left(\genfrac{}{}{0ex}{}{k}{r}\right)$ tag van): $\begin{array}{c}{\displaystyle \text{det}\left(M\right)=\sum _J^{}\text{sg}\left(I\mathrm{,}J\right)M_{I\mathrm{,}J}{M}_{I\text{'}\mathrm{,}J\text{'}}\mathrm{.}}\end{array}$   2.2. tétel. Legyen az $M$ mátrix $m\times k$-as, az $N$ pedig $k\times n$-es (hogy összeszorozhatóak legyenek) és $K=MN$. Rögzítsük az $r$ elemű $I\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}m\right\}$ és $J\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ részhalmazokat. Ekkor a Cauchy‐Binet-formula a következő $(|S|$ az $S$ elemszáma$):$ $\begin{array}{c}{\displaystyle K_{I\mathrm{,}J}=\sum _{S\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}k\right\}\mathrm{,}|S|=r}^{}{M}_{I\mathrm{,}S}{N}_{S\mathrm{,}J}\mathrm{.}}\end{array}$   2.2. Mátrix normálalakja. A [4] könyv 7.4.5. lemmáját ismertetjük. Legyen $M$ egész elemű mátrix, melynek $k$ sora és $n$ oszlopa van, azaz $M\in {\text{Z}}^{k\times n}$. A következő lépéseket engedjük meg. (1) Egy oszlopból egy másik oszlop egész számszorosának levonása. (2) Két oszlop cseréje. (3) Egy sorból egy másik sor egész számszorosának levonása. (4) Két sor cseréje.   2.3. tétel. A fenti négyféle átalakítás alkalmas sorozatával $M$ a következő normálalakra hozható. A mátrix főátlójában álló $s_1$, $s_2\mathrm{,}\text{...}\mathrm{,}{s}_k$ számok sorban egymás osztói (lehetséges, hogy egy idő után mindegyik nulla), és a mátrix többi eleme nulla. Az $s_i$ számok előjel erejéig egyértelműen meg vannak határozva, és föltehető, hogy $s_i\ge 0$.   Ha $n<k$, akkor legyen $s_{n+1}=\text{...}=s_k=0$, azaz a főátlót kiegészítjük nulla elemekkel. A bizonyítás ki is található, maradékos osztással kell kombinálni a Gauss-eliminációt, és arra törekedni, hogy a mátrix bal fölső sarkába kerülő szám az összes többinek osztója legyen. Az egyértelműségi állítást most bebizonyítjuk.   2.4. definíció. Az $M$ mátrix $m$-edik determinánsosztója az $m\times m$ méretű aldeterminánsainak a legnagyobb (nemnegatív) közös osztója, jele ${\Delta }_m$. Legyen ${\Delta }_0=1$. (Nyilván $M$ (determináns)rangja a legnagyobb olyan $r$, melyre ${\Delta }_r\ne 0$.)   2.5. lemma. Ha $m\le \ell$, akkor ${\Delta }_m\mid {\Delta }_{\ell }$.   Bizonyítás. A Laplace-kifejtés (2.1. tétel) miatt mindegyik $\ell \times \ell$ méretű aldetermináns előáll $m\times m$-es aldeterminánsok egész együtthatós lineáris kombinációjaként.  $\square$   2.6. lemma. A $\mathrm{2.3.}$ tételbeli átalakítások a determinánsosztókon nem változtatnak.   Bizonyítás. A cserére vonatkozó állítás nyilvánvaló. Adjuk az $i$-edik sor $t$-szeresét a $j$-edik sorhoz, az így módosított mátrixot jelölje $M\text{'}$. Csak azok az $m\times m$-es aldeterminánsok változhatnak meg, amelyeken a $j$-edik sor áthalad, de az $i$-edik sor nem. Legyen $N$ ilyen aldeterminánsa $M$-nek, $N\text{'}$ a módosított $M\text{'}$ mátrix megfelelő aldeterminánsa, $K$ pedig az a determináns, amit $N$-ből úgy kapunk, hogy a $j$-edik sorába beírjuk az $M$ mátrix $i$-edik sorának a megfelelő oszlopokba eső részét. A $K$ sorait átrendezhetjük úgy, hogy $M$ egy $m\times m$-es aldeterminánsát kapjuk. Ez maximum előjelváltással jár, tehát ha $\Delta$ jelöli az $M$ mátrix $m$-edik determinánsosztóját, akkor $\Delta \mid \text{det}\left(N\right)\mathrm{,}\text{det}\left(K\right)$. Ezért $\Delta \mid \text{det}\left(N\text{'}\right)=\text{det}\left(N\right)+t\text{det}\left(K\right)$. Beláttuk tehát, hogy az $M\text{'}$ mátrix $m$-edik $\Delta \text{'}$ determinánsosztója többese $\Delta$-nak. Mivel az átalakítást visszafelé végezve ugyanolyan típusú átalakítást kapunk (a $j$-edik sorhoz az $i$-edik sor $-t$-szeresét kell adni ahhoz, hogy $M\text{'}$-ből $M$-et kapjuk), ezért $\Delta =\Delta \text{'}$.  $\square$   Egy normálalakú mátrix $m$-edik determinánsosztója nyilvánvalóan $s_1{s}_2\text{...}{s}_m$. Így $s_m={\Delta }_m/{\Delta }_{m-1}$, ahol ${\Delta }_m$ az eredeti $M$ mátrix $m$-edik determinánsosztója. Ez a képlet működik, amíg ${\Delta }_{m-1}\ne 0$. Ha $r$ a legnagyobb, melyre ${\Delta }_r\ne 0$ (azaz $M$ rangja $r$), akkor a képlet szerint $s_{r+1}=0$, és így $i>r$ esetén is $s_i=0$, hiszen $s_{r+1}\mid s_i$.   3. Rácsok bázisa és indexe   3.1. Két példa. A kockás papíron látható ,,rács'' az egész koordinátájú pontok $A$ halmaza a síkon. Az origóból a rácspontokba mutató vektorok csoportot alkotnak. Ez azt jelenti, hogy bármely két rácsvektor összege és különbsége is benne van a rácsban. A rács diszkrét is: korlátos területre csak véges sok rácspont esik. A ${\text{b}}_1=\left(\mathrm{0,1}\right)$ és ${\text{b}}_2=\left(\mathrm{1,0}\right)$ vektorok bázist alkotnak: mindegyik rácsvektor egyértelműen előáll $z_1{\text{b}}_1+z_2{\text{b}}_2$ alakban, ahol $z_i$ egész számok (azaz a bázisvektorok egész együtthatós lineáris kombinációjaként). Bázist alkotnak a ${\text{c}}_1=\left(\mathrm{1,1}\right)$ és ${\text{c}}_2=\left(\mathrm{0,1}\right)$ vektorok is. Forgassuk el az $A$ rácsot az origó körül $45$ fokkal, és nyújtsuk $\sqrt[]{2}$-szörösére. Ez is egy egész pontokból álló $B$ rács (azaz $B$ részrácsa $A$-nak), azokból a pontokból áll, melyeknek vagy mindkét koordinátája páros, vagy mindkét koordinátája páratlan. $B$ is zárt az összeadásra és a kivonásra, azaz részcsoport $A$-ban. Ha $B$ minden eleméhez hozzáadjuk a $\text{v}=\left(\mathrm{0,1}\right)$ vektort (az így eltolt halmazt jelölje $\text{v}+B$, ez egy mellékosztály $A$-ban $B$ szerint), akkor az $A$-ra vett komplementer halmazt kapjuk, azokat a pontokat, melyeknek egyik koordinátája páros, a másik páratlan. Ha $\text{w}\in B$, akkor $\text{w}+B=B$, tehát $B$ maga is mellékosztály. Az $A$ rács tehát két $B$ szerinti mellékosztály diszjunkt uniója. Azt fogjuk mondani, hogy $B$ indexe $A$-ban $2$. A $B$ rácsban bázist alkot ${\text{d}}_1=\left(\mathrm{1,1}\right)$ és ${\text{d}}_2=\left(\mathrm{1,}-1\right)$, de ${\text{e}}_1=\left(\mathrm{1,1}\right)$ és ${\text{e}}_2=\left(\mathrm{0,2}\right)$ is. Vizsgáljuk meg, hogy e két rácsból hány rácspont esik egy adott területre, mondjuk a $\left(\mathrm{0,0}\right)$, $\left(\mathrm{0,}n\right)$, $\left(n\mathrm{,0}\right)$, $\left(n\mathrm{,}n\right)$ csúcsú négyzetbe. E négyzetet azon $\left({\alpha }_1\mathrm{,}{\alpha }_2\right)$ pontok halmazának képzeljük, melyekre $0\le {\alpha }_1\mathrm{,}{\alpha }_2<n$ (azaz a négy csúcsból pontosan egyet tartalmaz). Az ide eső rácspontok száma tehát $n^2$, ami pontosan a négyzet területe. Ez nem is meglepő, hiszen a nagy négyzetet kiparkettázhatjuk $n^2$ egységnégyzettel (ezeket is úgy képzeljük, hogy a határuknak csak a bal és az alsó része tartozik hozzájuk). Minden ilyen kis négyzetben pontosan egy rácspont van. A parkettázást elvégezhetjük a ${\text{c}}_1$ és ${\text{c}}_2$ vektorok által kifeszített $P$ paralelogramma eltoltjaival is. Ennek a csúcsai $\left(\mathrm{0,0}\right)$, $\left(\mathrm{1,1}\right)$, $\left(\mathrm{0,1}\right)$ és $\left(\mathrm{1,2}\right)$. Ismét úgy tekintjük, hogy $P$ az ${\alpha }_1{\text{c}}_1+{\alpha }_2{\text{c}}_2$ pontok halmaza, ahol $0\le {\alpha }_1\mathrm{,}{\alpha }_2<1$. A $P$ eltoltjai is hézagmentesen lefedik a síkot, és mindegyik eltolt pontosan egy rácspontot tartalmaz. A nagy négyzetből néhol kilógnak azok az eltoltak, amik a határhoz közel vannak, de könnyű látni, hogy a kilógó kis paralelogrammák száma elhanyagolható a többiéhez képest. Azoknak az eltoltaknak a száma, amelyek teljesen a nagy négyzetbe esnek, $n^2$-tel osztva $1$-hez tart, ha $n$ tart a végtelenhez. Ebből következik, hogy a kis paralelogramma területe $1$ (ami persze nyilvánvaló, hiszen alapja és magassága is $1$). Ha a $B$ ráccsal végezzük el ezt a számolást, akkor azt kapjuk, hogy a nagy négyzetben közel $n^2/2$ rácspont van, annak megfelelően, hogy a $\left(\mathrm{0,0}\right)$, $\left(\mathrm{1,1}\right)$ $\left(\mathrm{1,}-1\right)$, $\left(\mathrm{2,0}\right)$ négyzetnek és a $\left(\mathrm{0,0}\right)$, $\left(\mathrm{1,1}\right)$, $\left(\mathrm{0,2}\right)$, $\left(\mathrm{1,3}\right)$ paralelogrammának is $2$ a területe. Mindkét paralelogrammába mindkét $B$ szerinti mellékosztálynak egy-egy pontja esik. A két ,,alap''-paralelogramma területének hányadosa $B$ indexe $A$-ban.   3.2. Alap-parallelotóp. Az eddigi példákat általánosítjuk. Az ${\text{R}}^k$ tér $P$ pontjait azonosítjuk az origóból a $P$-be vezető helyvektorral, azaz ${\text{R}}^k$ oszlopvektoraival. Az ${\text{R}}^k$ összeadásra és kivonásra zárt, nem üres $A$ részhalmazait csoportnak hívjuk (a csoport algebrai fogalma ennél általánosabb). Ha $A$ minden elemének minden valós számszorosát is tartalmazza, akkor neve (valós) altér. Ilyen például egy origón átmenő egyenes vagy sík a térben. Az $A$ diszkrét, ha ${\text{R}}^k$ minden gömbje $A$-nak csak véges sok pontját tartalmazza. Az ${\text{R}}^k$ rácsának az olyan diszkrét csoportokat nevezzük, melyekben van $k$ lineárisan független vektor. Altérre úgy kaphatunk példát, hogy veszünk ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_n$ vektorokat, és tekintjük az összes ${\lambda }_1{\text{v}}_1+\text{...}+{\lambda }_n{\text{v}}_n$ alakú lineáris kombinációk halmazát, ahol ${\lambda }_i$ tetszőleges valós számok; ez a ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_n$ által generált altér. Ha mindegyik ${\lambda }_i$ egész szám, akkor az általuk generált csoportot kapjuk. Ha tehát generált altérről beszélünk, akkor valós együtthatós lineáris kombinációkra gondolunk, ha generált csoportról vagy rácsról, akkor az együtthatók egészek. Ha vektoraink függetlenek is (ekkor szükségképpen $n\le k)$, akkor a kombinációk együtthatói egyértelműen meghatározottak, és az altér, illetve a csoport bázisát kapjuk. A bázis elemszáma az altér dimenziója, illetve a csoport rangja. Belátjuk majd, hogy minden rácsnak van bázisa.   3.1. definíció. Legyenek ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k$ függetlenek. Az általuk kifeszített $P$ parallelotóp az ${\alpha }_1{\text{v}}_1+\text{...}+{\alpha }_k{\text{v}}_k$ alakú pontok halmaza, ahol $1\le i\le k$ esetén $0\le {\alpha }_i<1$. Ez a ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k$ által generált $B$ rács (egyik) alap-parallelotópja. Tehát az alap-parallelotópokat $B$ egy-egy bázisának vektorai feszítik ki.   Magasabb dimenzióban a térfogat fogalmát intuitív módon használjuk. A parallelotópok térfogata alapszor magasság, ahol az alap ,,területe'' az eggyel alacsonyabb dimenziós térfogatot jelenti. A $k$-dimenziós térfogat fogalmának fölépítése történhet determinánsok segítségével, lásd [2], 9.8. szakasz. Mindenképpen igaz a következő.   3.2. tétel. A ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k\in {\text{R}}^k$ vektorok által kifeszített parallelotóp térfogata egyenlő a $\left[{\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k\right]$ mátrix determinánsának abszolút értékével. (E determináns előjele a ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k$ rendszer úgynevezett irányítását adja meg.)   Legyen $P$ a $B$ rács egyik alap-parallelotópja. A $P$-nek a $\text{v}\in B$ vektorokkal vett $\text{v}+P$ eltoltjai hézagmentesen kitöltik az ${\text{R}}^k$ teret. Minden ilyen $\text{v}+P$ eltoltban pontosan egy eleme van $B$-nek: maga a $\text{v}$ vektor. Ezért az előző szakaszban, a konkrét példák esetében látott gondolatmenet általában azt adja, hogy ha veszünk egy $R$ sugarú $G$ gömböt, akkor a $G$ térfogata elosztva a $G$-be eső $B$-beli pontok számával a $P$ parallelotóp térfogatához tart, midőn $R$ tart a végtelenhez. Legyen most $A$ tetszőleges olyan rács, amely $B$-t tartalmazza. Bármely $\text{v}\in B$ esetén a $\text{v}$ vektorral való eltolás az $A$ és $B$ rácsokat önmagukba viszi. Ezért ha a $P$ parallelotópba az $A$ rácsnak $d$ pontja esik (a $d$ véges szám, hiszen $A$ diszkrét), akkor ugyanez igaz mindegyik $\text{v}+P$ eltoltra is. Emiatt ha a fenti $G$ gömb térfogatát a $G$-be eső $A$-beli rácspontok számával osztjuk, akkor ez a hányados a $P$ parallelotóp térfogatának $1/d$-szereséhez tart, midőn $R$ tart a végtelenhez.   3.3. állítás. Ha $\text{u}\mathrm{,}\text{w}\in A$, akkor a $\text{w}+B$ halmazt (az egyik) $B$ szerinti mellékosztálynak hívjuk. Az $\text{u}+B$ és $\text{w}+B$ mellékosztályok vagy egyenlők, vagy diszjunktak; akkor egyenlők, ha $\text{u}-\text{w}\in B$. Ezért $A$ a $B$ szerinti mellékosztályok (diszjunkt) uniója. A mellékosztályok száma a $B$ részcsoport $A$-beli indexe, jele $|A:B|$.   A könnyű bizonyítást az Olvasóra hagyjuk. Az általános, csoportokra vonatkozó eset bizonyítása megtalálható a [4] könyv 4.4. szakaszában. A 3.1. definíció jelöléseit használva $\begin{array}{c}{\displaystyle \text{u}={\gamma }_1{\text{v}}_1+\text{...}+{\gamma }_k{\text{v}}_k\text{és}\text{w}={\delta }_1{\text{v}}_1+\text{...}+{\delta }_k{\text{v}}_k}\end{array}$ akkor esnek ugyanabba a $B$ szerinti mellékosztályba, ha ${\gamma }_i-{\delta }_i$ egészek. Ezért $\text{u}+B$-nek egyetlen $\text{w}$ vektora esik $P$-be: amikor ${\delta }_i$ a ${\gamma }_i$ törtrésze. Azaz $P$ minden $B$ szerinti mellékosztályból pontosan egy vektort tartalmaz, és így $|A:B|=d$. Ha $A$-nak is van bázisa, és így egy $Q$ alap-parallelotópja is, akkor persze $G$ térfogata elosztva a $G$-be eső $A$-beli pontok számával $Q$ térfogatához tart. Ezért beláttuk az alábbi tétel második állítását azzal a föltevéssel, hogy $A$-ban és $B$-ben is van bázis.   3.4. tétel. Minden rácsnak van bázisa. Ha $B$ részrácsa $A$-nak, akkor $B$ indexe $A$-ban a $B$ és $A$ alap-parallelotópjai térfogatának hányadosa (a kisebbik rácsban nagyobb ez a térfogat). Speciálisan $A$ bármely két alap-parallelotópjának a térfogata egyenlő.   Bizonyítás. A tétel első állításának bizonyításához legyen $A$ rács és ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k$ független vektorok $A$-ban. Essen $d$ darab $A$-beli pont a ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k$ által kifeszített $P$ parallelotópba. Ha van ezek között egy $0\ne \text{v}={\alpha }_1{\text{v}}_1+\text{...}+{\alpha }_k{\text{v}}_k$, akkor válasszunk egy olyan $i$ indexet, amelyre ${\alpha }_i\ne 0$. A ${\text{v}}_i$ helyére $\text{v}$-t téve a kapott parallelotóp térfogata kisebb lesz, mint az eredetié volt, annak ${\alpha }_i$-szeresére változik. Ezt érdemes a síkon vagy a térben elképzelni (a magasság ${\alpha }_i$-szeresére csökken), de algebrailag is könnyű megmutatni determinánsok segítségével. Az eljárást folytatva egy olyan vektorrendszert találunk $A$-ban, amelyre már $d=1$, vagyis a $P$-be eső egyetlen $A$-beli pont az origó. De akkor a ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_k$ generálta $B$ rács maga $A$. Valóban, $A$ minden $\text{u}$ eleme beleesik valamelyik $\text{v}+P$ eltoltba, ahol $\text{v}\in B$. Ebben az eltoltban az egyetlen $A$-beli pont az $\text{u}$, ezért $\text{u}=\text{v}\in B$.  $\square$   3.5. feladat. Legyen $d=|A:B|$. Igazoljuk, hogy minden $\text{u}\in A$-ra $d\text{u}\in B$.   Útmutatás. Vegyünk ki mindegyik $B$ szerinti mellékosztályból egy-egy ${\text{u}}_i$ vektort. Ekkor $\text{u}+{\text{u}}_i$ is csupa különböző mellékosztályban van, tehát mindegyik mellékosztályba egy ilyen vektor esik. Ezért ${\text{u}}_1+\text{...}+{\text{u}}_d$ és $\left(\text{u}+{\text{u}}_1\right)+\text{...}+\left(\text{u}+{\text{u}}_d\right)$ ugyanabban a mellékosztályban vannak. Különbségük $d\text{u}$.  $\square$   3.6. feladat. Legyenek $B\subseteq A$ részrácsai ${\text{Z}}^k$-nak. Mutassuk meg, hogy a $|{\text{Z}}^k:A|$ index osztja a $|{\text{Z}}^k:B|$ indexet.   Útmutatás. $B$ alap-parallelotópjának mindegyik eltoltjába $A$-nak $|A:B|$ darab pontja esik. Ezért minden elég nagy gömbben $A$-nak körülbelül $|A:B|$-szer annyi pontja van, mint $B$-nek. Ugyanez $A$ és ${\text{Z}}^k$, valamint $B$ és ${\text{Z}}^k$ viszonylatában is elmondható.  $\square$   Ha az Olvasó e két feladat mélyebb algebrai hátterére kíváncsi, lapozza föl a [4] könyv negyedik fejezetében Lagrange tételét és a faktorcsoport fogalmát.   3.3. Részrács bázisa. A 3.1. szakaszban vizsgált mindkét példában kétféle alap-paralelogrammát láttunk. Választhatunk úgy, hogy a $B$ rács alap-paralelogrammája kiparkettázható legyen az $A$ rács alap-paralelogrammájának eltoltjaival: vegyük $B$-ben a $\left(\mathrm{0,0}\right)$, $\left(\mathrm{1,1}\right)$, $\left(\mathrm{0,2}\right)$, $\left(\mathrm{1,3}\right)$ csúcsú paralelogrammát, $A$-ban pedig ennek az ,,alsó felét'', a $\left(\mathrm{0,0}\right)$, $\left(\mathrm{1,1}\right)$, $\left(\mathrm{0,1}\right)$, $\left(\mathrm{1,2}\right)$ csúcsút. Vagyis $A$-ban a ${\text{c}}_1=\left(\mathrm{1,1}\right)$ és ${\text{c}}_2=\left(\mathrm{0,1}\right)$ bázist, $B$-ben a ${\text{c}}_1$ és $2{\text{c}}_2$ bázist tekintjük. Ebből is azonnal látszik, hogy az $|A:B|$ index $2$. Igen erős tétel, a későbbiek alapja, hogy ezt általában is meg lehet tenni.   3.7. tétel. Ha $B$ részrácsa $A$-nak, akkor választhatunk olyan $P$ és $Q$ alap-parallelotópot $A$-ban, illetve $B$-ben, hogy $P$ eltoltjaival $Q$ kiparkettázható. Azaz van olyan ${\text{c}}_1\mathrm{,}\text{...}\mathrm{,}{\text{c}}_k$ bázisa $A$-nak, hogy alkalmas $s_1\mathrm{,}{s}_2\mathrm{,}\text{...}\mathrm{,}{s}_k$ pozitív egészekre $s_1{\text{c}}_1\mathrm{,}\text{...}\mathrm{,}{s}_k{\text{c}}_k$ bázis $B$-ben. Ekkor $|A:B|=s_1\cdot \text{...}\cdot s_k$. A két bázis úgy is választható, hogy az $s_1\mid s_2\mid \text{...}\mid s_k$ oszthatóság is teljesüljön.   Geometriailag világos, hogy $|A:B|=s_1\cdot \text{...}\cdot s_k$. Az algebrai bizonyításhoz vegyük észre, hogy $x_1{\text{c}}_1+\text{...}+x_k{\text{c}}_k$ és $y_1{\text{c}}_1+\text{...}+y_k{\text{c}}_k$ akkor vannak ugyanabban a mellékosztályban $B$ szerint, ha $x_j\equiv y_j\left(s_j\right)$ minden $j$-re. Ezért mindegyik mellékosztály pontosan egyet tartalmaz azon $z_1{\text{c}}_1+\text{...}+z_k{\text{c}}_k$ vektorok közül, melyekre $0\le z_j<s_j$. A ${\text{c}}_i$ bázis létezését általánosabban bizonyítjuk. Láttuk, hogy $B$-nek van bázisa, azaz $k$ vektorral generálható. Az általánosítás az, hogy több generátort is megengedünk, és azt sem tesszük föl, hogy van közöttük $k$ független. Ha $A$-nak vesszük egy bázisát, akkor $B$ elemeit eleve ezek lineáris kombinációiként írhatjuk föl. Ezért nem veszítünk az általánosságból, ha az $A={\text{Z}}^k$ esetet tekintjük.   3.8. tétel. Legyen ${\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_n\in {\text{Z}}^k$ és $B$ az általuk generált csoport. Hozzuk normálalakra az $M=\left[{\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{v}}_n\right]$ mátrixot a $\mathrm{2.3.}$ tétel értelmében, és jelölje $s_1\mid s_2\mid \text{...}\mid s_k$ a főátlóban szereplő számokat. Tudjuk, hogy az $M$ mátrix $r$-edik determinánsosztója $s_1\cdot \text{...}\cdot s_r$. Ha $M$ rangja $r$, akkor a következők teljesülnek. $\left(1\right)$ Van ${\text{Z}}^k$-nak olyan ${\text{c}}_1\mathrm{,}\text{...}\mathrm{,}{\text{c}}_k$ bázisa, hogy $s_1{\text{c}}_1\mathrm{,}\text{...}\mathrm{,}{s}_r{\text{c}}_r$ bázis $B$-ben. $\left(2\right)$ Ha $r=k$, akkor $B$ rács és $|{\text{Z}}^k:B|=s_1\cdot \text{...}\cdot s_k$.   Bizonyítás. Kiindulunk a $B$ csoport ${\text{w}}_1={\text{v}}_1\mathrm{,}\text{...}\mathrm{,}{\text{w}}_n={\text{v}}_n$ generátorrendszeréből és ${\text{Z}}^k$-nak a ,,szokásos'' ${\text{b}}_1={\text{e}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_k={\text{e}}_k$ bázisából, amelyben az ${\text{e}}_i$ vektor $i$-edik koordinátája $1$, a többi nulla. Az $M$-et normálalakra hozó négyféle lépés során változtatjuk majd a ${\text{w}}_j$ generátorrendszert és a ${\text{b}}_i$ bázist is, úgy, hogy $B$ ne változzon. Egy közbülső állapotban jelölje a mátrix $i$-edik sorának $j$-edik elemét $n_{ij}$. A kinduló állapotban nyilván ${\text{w}}_j=n_{1j}{\text{b}}_1+\text{...}+n_{kj}{\text{b}}_k$. Minden lépés végrehajtása után ezzel a képlettel fogjuk definiálni az új ${\text{w}}_j$ generátorrendszert. Ha kicseréljük a $j$-edik és a $j\text{'}$-edik oszlopot, akkor ${\text{w}}_j$ és ${\text{w}}_{j\text{'}}$ helyet cserél, de $B$ nem változik. Ha az $i$-edik és $i\text{'}$-edik sort cseréljük, de kicseréljük a ${\text{b}}_i$ és ${\text{b}}_{i\text{'}}$ bázisvektorokat is, akkor egyik ${\text{w}}_j$ sem változik, és így $B$ sem. Ha a $j\text{'}$-edik oszlop $t$-szeresét adjuk a $j$-edik oszlophoz, akkor ${\text{w}}_j$ helyén ${\text{w}}_j+t{\text{w}}_{j\text{'}}$ fog állni. Mivel ${\text{w}}_j+t{\text{w}}_{j\text{'}}\in B$, az új vektorok $B$-nek egy részét generálják. De ez az átalakítás megfordítható (az új $j$-edik oszlopból kell kivonni a $j\text{'}$-edik oszlop $t$-szeresét), ezért $B$ most sem változik. Végül adjuk az $i\text{'}$-edik sor $t$-szeresét az $i$-edik sorhoz. Az egyszerűbb tipográfia érdekében legyen $i=1$ és $i\text{'}=2$. Ekkor $\begin{array}{c}{\displaystyle {\text{w}}_j=n_{1j}{\text{b}}_1+n_{2j}{\text{b}}_2+\text{...}+n_{kj}{\text{b}}_k=\left(n_{1j}+t{n}_{2j}\right){\text{b}}_1+n_{2j}\left({\text{b}}_2-t{\text{b}}_1\right)+\text{...}+n_{kj}{\text{b}}_k\mathrm{.}}\end{array}$ Ezért ha ${\text{b}}_2$-t $\left({\text{b}}_2-t{\text{b}}_1\right)$-re változtatjuk, akkor ${\text{w}}_j$ nem változik. Az Olvasóra bízzuk annak ellenőrzését, hogy az így kapott új rendszer is bázis ${\text{Z}}^k$-ban (azaz független, és egész együtthatókkal fölírható vele ${\text{Z}}^k$ minden vektora). A végső állapotban, amikor $M$ normálalakú, legyen ${\text{c}}_i={\text{b}}_i$. Ekkor ${\text{w}}_j=s_j{\text{c}}_j$ ha $j\le k$ és ${\text{w}}_j=\text{0}$, ha $j>k$, és így az $s_j{\text{c}}_j$ vektorok generálják $B$-t. A 2.6. lemma szerint menet közben nem változnak meg a determinánsosztók, és így a rang sem. Tehát az $s_i$ számok közül az első $r$ lesz nem nulla, és így $s_1{\text{c}}_1\mathrm{,}\text{...}\mathrm{,}{s}_r{\text{c}}_r$ függetlenek is.  $\square$   3.9. következmény. Legyenek ${\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r\in {\text{Z}}^k$ lineárisan független vektorok $\left(r\ge 1\right)$ és $B$ az általuk generált csoport. Ekkor az alábbi állítások ekvivalensek. $\left(1\right)$ ${\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r$ kiegészíthető ${\text{Z}}^k$ egy bázisává. $\left(2\right)$ Ha $m\ne 0$ egész, $\text{v}\in {\text{Z}}^k$ és $m\text{v}\in B$, akkor $\text{v}\in B$. $\left(3\right)$ A $\left[{\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r\right]$ mátrix $r$-edik determinánsosztója $1$. $\left(4\right)$ A $\left[{\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r\right]$ mátrix alaptételbeli alakjában a főátló mindegyik eleme $1$. Speciálisan $\text{v}\in {\text{Z}}^k$ pontosan akkor van benne ${\text{Z}}^k$ egy bázisában, ha primitív, azaz a komponenseinek a legnagyobb közös osztója $1$.   Bizonyítás. Tegyük föl, hogy létezik az $\left(1\right)$-ben megkövetelt ${\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_k$ bázis. Ha $\text{v}=z_1{\text{b}}_1+\text{...}+z_k{\text{b}}_k$, akkor $m\text{v}$ pontosan akkor van $B$-ben, ha $z_j=0$ minden $j>r$ indexre. De akkor $\text{v}=z_1{\text{b}}_1+\text{...}+z_r{\text{b}}_r\in B$. Ezért $\left(2\right)$ teljesül. Alkalmazzuk $M=\left[{\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r\right]$-re az előző tételt. Ha a $\left(2\right)$ pontban megadott feltétel teljesül, akkor $s_i{\text{c}}_i\in B$-ből ${\text{c}}_i\in B$, azaz $s_i=1$ következik. Az $r$-edik determinánsosztó $s_1\cdot \text{...}\cdot s_r$, ami pontosan akkor $1$, ha mindegyik $s_i=1$. Végül, ha $i\le r$ esetén $s_i=1$, akkor nemcsak ${\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r$, hanem ${\text{c}}_1\mathrm{,}\text{...}\mathrm{,}{\text{c}}_r$ is bázisa $B$-nek. Tehát ${\text{Z}}^k$ minden eleme ${\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_r\mathrm{,}{\text{c}}_{r+1}\mathrm{,}\text{...}\mathrm{,}{\text{c}}_k$ egész együtthatós lineáris kombinációjaként is fölírható. Ez $k$ vektor, és ezért bázis ${\text{Z}}^k$-ban.  $\square$   3.10. feladat. Igazoljuk a $\mathrm{3.8.}$ tétel segítségével, hogy ha a $B\subseteq {\text{Z}}^k$ rácsban nincs primitív vektor, akkor van olyan $m>1$ egész, amellyel $B$ minden eleme osztható.   3.11. feladat. Mutassuk meg a normálalak fölhasználása nélkül, hogy ha $M\in {\text{Z}}^{k\times n}$ rangja $k$, akkor az $M$ oszlopai által generált rács indexe ${\text{Z}}^k$-ban az $M$ mátrix $k$-adik determinánsosztója.   Útmutatás. Legyen $B$ az $M$ oszlopai által generált rács és ${\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_k$ bázis $B$-ben. Minden $\text{v}\in B$ fölírható $z_1{\text{b}}_1+\text{...}+z_k{\text{b}}_k$ alakban. Jelölje $f\left(\text{v}\right)$ azt az (oszlop)vektort, melynek a $z_i$ számok a komponensei. (Az $f$ egy úgynevezett lineáris leképezés, ami átkoordinátázza $B$ elemeit az új bázis szerint). Nyilván $\text{v}=\left[{\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_k\right]f\left(\text{v}\right)$. Az $M$ oszlopaira $f$-et alkalmazva egy $K$ mátrixot kapunk. Mutassuk meg, hogy az $M$ mátrix $k$-adik $\Delta$ determinánsosztója a $K$ mátrix $k$-adik $D$ determinánsosztójának $|d|$-szerese, ahol $d$ a $\left[{\text{b}}_1\mathrm{,}\text{...}\mathrm{,}{\text{b}}_k\right]$ mátrix determinánsa (vagyis $|d|=|{\text{Z}}^k:B|$). $K$ oszlopai a teljes ${\text{Z}}^k$ rácsot generálják, mert ha $\text{w}={\left[z_1\mathrm{,}\text{...}\mathrm{,}{z}_k\right]}^T\in {\text{Z}}^k$, akkor $\text{v}=z_1{\text{b}}_1+\text{...}+z_k{\text{b}}_k\in B$ fölírható $M$ oszlopai segítségével. Ugyanez $\text{mod}p$ is igaz minden $p$ prímre, és ezért $K$-t $\text{mod}p$ véve rangja szükségképpen $k$. Így van olyan $k\times k$-as aldeterminánsa, ami nem osztható $p$-vel, azaz $p\nmid D$. Tehát $D=1$.  $\square$   A cikk második részében az olimpiai feladat rácsát elemezzük, bemutatjuk Peter McMullen egy tételét ortogonális rácsokról, végül feladatok segítségével lehetőséget kínálunk az Olvasónak arra, hogy néhány eddigi állításra geometriai bizonyítást adjon.   Hivatkozások [1] Erdős Pál, Surányi János: Válogatott fejezetek a számelméletből. Polygon Kiadó, 1996. [2] Freud Róbert: Lineáris Algebra. ELTE Eötvös Kiadó, 2014. www.tankonyvtar.hu/hu/tartalom/tamop425/2011_0001_527_LinearisAlgebra [3] Freud Róbert, Gyarmati Edit: Számelmélet. Nemzeti Tankönyvkiadó, 2006. www.tankonyvtar.hu/hu/tartalom/tamop425/2011_0001_519_Szamelmelet [4] Kiss Emil: Bevezetés az algebrába. TypoTeX Kiadó, 2007. www.tankonyvtar.hu/hu/tartalom/tamop425/2011-0001-526_kiss_emil [5] Radnai András: Rácselmélet alkalmazása a számelméletben, Szakdolgozat, ELTE, 2010. web.cs.elte.hu/blobs/diplomamunkak/bsc_mat/2010/radnai_andras.pdf 1ewkiss.web.elte.hu/wp/wordpress/wp-content/uploads/2014/11/inv_CB_Laplace.pdf.