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. Most rátérünk az olimpiai feladatban szereplő rács vizsgálatára. Rögzítsünk egész számpárokat (), ahol és relatív prímek. Adott esetén legyen az az egész elemű, sorból és oszlopból álló mátrix, amelyben az -edik sor -edik eleme és az oszlopai által generált csoport.
4.1. Az determinánsosztóinak meghatározása. Fölhasználjuk az egész együtthatós többváltozós polinomok számelméletét. Az alábbiak a [3] könyv második és harmadik fejezetéből megérthetők, különös tekintettel a 3.4. szakaszra.
4.1. tétel. A polinomjai között igaz a számelmélet alaptétele, azaz minden nullától és egységtől különböző polinom sorrendtől és egységszerestől eltekintve egyértelműen bontható irreducibilisek szorzatára. A prím és irreducibilis polinomok ugyanazok, és csak egység. A -beli prímszámok prímek -ben is.
Egy polinom akkor primitív, ha együtthatóinak közös osztója csak egység lehet. Egy elsőfokú polinom nem feltétlenül irreducibilis, például -ben nem az, hiszen a fölbontásban egyik tényező sem egység. Ha azonban primitív is, akkor már irreducibilis lesz, és egyben prímtulajdonságú. Ez akkor is igaz, ha az együtthatói nem egész számok, hanem egész együtthatós, akár többváltozós polinomok.
4.2. következmény. A -beli polinom irreducibilis abban az esetben, ha páronként különböző. Két ilyen polinom különböző négyelemű indexhalmazok esetében biztosan nem egymás egységszerese.
4.3. lemma. Legyen a -as mátrixban az -edik sor -edik eleme . Ekkor .
Bizonyítás. Képzeljük először azt, hogy és változók, így a determináns elemei -beli polinomok. Emeljünk ki a determináns -edik sorából -et mindegyik -re (ez megtehető, mert ). Az eredmény egy Vandermonde-determináns lesz az generátorokkal, melynek értéke . A nevezőkkel szorozva az állítást kapjuk. Így azonosságot kaptunk. Ha az és helyébe bármilyen számokat (sőt polinomokat, akár maradékosztályokat) helyettesítünk, az egyenlőség e helyettesítés után is érvényben fog maradni. (Még akkor is, ha valamelyik helyébe nullát írunk.)
4.4. állítás. Ha , akkor az mátrix -adik determinánsosztója | | az értékétől függetlenül. (Ha , akkor , mint üres szorzat).
Bizonyítás. Legyen az mátrix -adik determinánsosztója. Azt fogjuk megmutatni, hogy a és számok egymás osztói. A bizonyításához legyenek és változók (). Egészítsük ki az mátrixot úgy, hogy az utolsó sora maradjon az, ami eredetileg volt, az első sorában pedig az -edik sor -edik eleme legyen . A kapott négyzetes mátrix determinánsát a 4.3. lemma segítségével számíthatjuk ki. Az így adódó szorzatot bontsuk három részre: , ahol
A Laplace-kifejtés (2.1. tétel) miatt a determináns értéke fölírható az mátrix -as aldeterminánsainak olyan lineáris kombinációjaként, amelynek együtthatói -ből valók. Ezért -ben a szám osztója a szorzatnak. Tegyük föl indirekt, hogy van olyan prímszám, melynek -beli kitevője nagyobb, mint a -beli kitevője. Mivel -ben igaz a számelmélet alaptétele, és ebben is prímszám (4.1. tétel), ezért . Tehát vagy , vagy alkalmas -re. Ez azonban lehetetlen, mert és relatív prímek, és így mindkét polinom primitív. Tehát tényleg . A fordított oszthatósághoz azt kell igazolnunk, hogy osztója -nak, ha az egy tetszőleges -as részmátrixa. Vegyünk föl , változókat (), és írjuk föl az mátrixot, valamint a és számokat is helyett -vel és helyett -vel (azaz képzeljünk az és számok helyébe változókat). Nyilván elegendő az oszthatóságot ebben az esetben igazolni. Rögzített mellett legyen , és írjuk föl Laplace-kifejtését (2.1. tétel) arra az esetre, amikor a soroknak a kételemű indexhalmazát vesszük. Azt kapjuk, hogy előáll az -edik és -edik sorból képzett kétszer kettes aldeterminánsok lineáris kombinációjaként. Ezek a kétszer kettes aldeterminánsok mind oszthatók -vel: ha a két oszlopindex , akkor | | és az szabály miatt . Így . Beláttuk tehát, hogy osztható az mindegyikével. Ezek a polinomok azonban páronként relatív prímek a 4.2. következmény miatt. A számelmélet alaptétele miatt e polinomok szorzata, ami , szintén osztója -nak.
4.5. feladat. Számítsuk ki összes determinánsosztóját.
Útmutatás. Az és a relatív prímek, ezért . Ha , akkor vegyük egy elemű részhalmazát, és álljon az mátrix az ennek megfelelő soraiból. A 4.4. lemma miatt az mátrix -es aldeterminánsainak legnagyobb közös osztója azon számok szorzata, amelyekre és . Az összes -es aldetermináns legnagyobb közös osztója tehát ezeknek a számoknak a legnagyobb közös osztója. Így sem függ az választásától.
4.2. Redukció prímhatvány modulusra. Egy vektort hívjunk -sel oszthatónak, ha mindegyik komponense osztható -sel. Az -sel osztható vektorok halmazát jelölje . Azt mondjuk, hogy egy csoport tartalmazza a vektort , ha fölírható egy -sel osztható és egy -beli vektor összegeként, azaz .
4.6. lemma. Legyen egy csoport, és , relatív prím egészek. Ha tartalmazza -t és , akkor tartalmazza is.
Bizonyítás. Legyen , ahol és . Mivel , van olyan , hogy . Ekkor .
Ha indexe -ban , akkor a 3.5. feladat szerint minden -val osztható vektor eleme -nak. Ha tehát be akarjuk látni, hogy , akkor elegendő megmutatni, hogy a index minden prímhatvány-osztója esetén benne van -ban .
4.3. Az olimpiai feladat megoldása. Ha valamilyen esetén, akkor, mivel és , valamint és relatív prímek, csak az lehetséges, hogy és egyenlők vagy ellentettek. Az első esetben elhagyható. A második esetben szintén, ha az kitevőt párosnak választjuk (erre majd ügyelünk). Ezért a továbbiakban föltesszük, hogy soha nem nulla, és azt is, hogy . Az által generált ekkor rács, hiszen a -adik determinánsosztó a 4.4. állításban definiált szám, ami nem nulla. Az indexe tehát , az -től függetlenül.
4.7. lemma. Legyen , ahol prím és . Tegyük föl, hogy az szám osztható -val, és nagyobb vagy egyenlő, mint és . Ekkor tartalmazza a konstans vektort .
Bizonyítás. Ha , akkor az Euler‐Fermat-tétel és miatt . Ha , akkor miatt . Ugyanez igaz a számokra is. Vegyük első, középső és utolsó oszlopát (van középső, mert páros). Mindegyikben csak és szerepelhet , és a középső oszlop a két szélső szorzata . Egy sor két szélső eleme nem lehet egyszerre nulla, mert és relatív prímek. Ezért a két szélső oszlop összegéből a középsőt kivonva konstans -et kapunk .
Az előző szakasz eredményeivel kombinálva, ha elég nagy, és teljesül minden prímhatvány-osztójára, akkor a konstans vektor -ben van.
4.8. feladat. Igazoljuk, hogy és vektorait komponensenként összeszorozva -beli vektorokat kapunk, így az rácsok periodikusan ismétlődnek .
Útmutatás. Ha a konstans vektor -ben van, akkor . Mivel az indexük ugyanaz a szám, meg is egyeznek.
4.4. Az rács vektorai. Most is föltesszük, hogy (amikor ). Ha , akkor indexe , így a vektorainak -ad részét tartalmazza (ez pontos értelmet kap, ha egy nagy gömb vektorait tekintjük).
4.9. feladat. Mutassuk meg, hogy ha , akkor , mert -nek van két egyenlő sora. Általánosítsuk ezt helyett általános prím modulusra.
Útmutatás. Ha prím, akkor a osztás esetén elvégezhető , azaz van olyan egész, hogy . Ha , akkor , mert és relatív prímek, ilyenkor legyen a szimbólum. Ez tehát -re lehetőség . Ha is , akkor . Mivel és egyszerre nem lehetséges, az és törtek egyike biztosan értelmes , és ha mindkettő az, akkor ugyanaz az értékük , ha pedig valamelyik nem értelmes, akkor a számlálója és nevezője is nulla . Így mindig és . Ezért az mátrix -edik sora az -edik sor -szerese . Ugyanez tehát vektorainak megfelelő koordinátáira is igaz, vagyis ha , akkor . (A vett mátrix rangja a különböző vett törtek száma, hiszen ha olyan sort vesszünk, melyekre páronként különböznek , akkor ennek a részmátrixnak az -edik determinánsosztója nem osztható -vel a 4.5. feladat miatt.)
Ha , akkor a legnagyobb modulus, melyre nézve és egyenlő. Az az szorzó, melyre és az képlettel kapható, ahol (van ilyen , , mert és relatív prímek). Legyen esetén .
4.10. feladat. Nyilván és . Készítsünk egy olyan bázist -ben az és komponensenkénti szorzásával a feladat alapján, ahol a vektorok háromszögmátrixot alkotnak ().
Útmutatás. Legyen . A vektor -edik koordinátája nulla, ezért a -edik bázisvektor elkészítéséhez tekintsük a (komponensenkénti) szorzatát. Ennek az első koordinátája nulla. Ahhoz, hogy -be jussunk, szorozzunk még -nel. A főátlóban álló elemek szorzata , mert és a főátló -edik eleme . Így a vektoraink függetlenek, és az általuk generált rács indexe . De indexe is , ezért bázist kaptunk.
Ha az előző feladatban kapott háromszögmátrix , akkor pontosan akkor van -ben, ha a lineáris egyenletrendszer (egyértelmű) megoldása egész számokból áll. Ezt az egyenletrendszert föntről lefelé haladva könnyű megoldani. A inverzével szorozva . Ez oszthatósági feltétel, ahol a bal oldalon mindig áll, mert egész elemű. Az első ezek közül automatikusan teljesül, mert első sorának első eleme .
4.11. példa. Legyenek a megadott párok , és . Ekkor esetén az összes egyenlő, , , , , mindegyik , és pontosan akkor van -ben, ha és .
Zárásként belátjuk Peter McMullen egy gyönyörű tételét. Mostantól kicsit nagyobb tudást föltételezünk lineáris algebrából (például euklideszi tér, ortogonális kiegészítő altér). Legyenek lineárisan független vektorok és az általuk generált altér. Ebben egész együtthatós lineáris kombinációi egy rangú rácsot alkotnak. Ez tehát nem az egész -nak rácsa, hanem csak a altérnek.
5.1. állítás. Jelölje a mátrix -es aldeterminánsainak négyzetösszegét . Ekkor a rács alap-parallelotópjának térfogata .
Bizonyítás. Föltehető, hogy . Legyen ortonormált bázis a által generált altér ortogonális kiegészítő alterében (ezek egy ,,kockát'' feszítenek ki), és . Geometriai megfontolásokból kapjuk, hogy abszolút értéke a által generált rács alap-parallelotópjának térfogata. Az mátrix két diagonális blokkból áll, és a többi eleme nulla. A második blokk a -es egységmátrix. Az első, -es blokkot jelölje . Ekkor . Alkalmazzuk a Cauchy‐Binet-formulát (2.2. tétel) az szorzatra és az első sorra/oszlopra. Ekkor adódik.
Ha rács -ban és altér -ban, akkor -be -nek kevés vektora is eshet. Például az egyenes nem tartalmaz egész koordinátájú pontot az origón kívül. Nevezzük -t racionális altérnek, ha generálható racionális koordinátájú vektorokkal. Racionális vektorok egy családja pontosan akkor független fölött, ha fölött az. Ha a racionális altér -dimenziós, akkor ortogonális komplementerének dimenziója -ban , és így az -ban vett ortogonális kiegészítő is racionális altér. Továbbá -ben van független vektor, hiszen egy racionális vektort alkalmas nem nulla egésszel megszorozva egész vektort kapunk. Ezért rács -ben.
5.2. definíció. Egy csoport elemének -beli magassága a legnagyobb olyan egész, amivel elosztható úgy, hogy -ben maradjunk. Ha , akkor ez a komponenseinek legnagyobb közös osztója. Tehát akkor primitív, ha magassága -ban . A részcsoport tiszta -ban, ha a vektorok magassága ugyanaz -ben, mint -ban. (Ez a 3.9. következmény pontjában szereplő feltétel.)
5.3. lemma. Ha racionális altér -ban, akkor tiszta részrácsa -nak.
Bizonyítás. Valóban, ha és , akkor (hiszen zárt az számmal való szorzásra), és így .
5.4. tétel (McMullen, [4]). Legyen racionális altér -ban. Ha és , akkor és alap-parallelotópjának térfogata megegyezik.
Bizonyítás. Legyen és (az és esetben térfogatát -nek tekintve igaz az állítás). Vegyük -nek egy és -nek egy bázisát. Ezek együtt bázist alkotnak -ban, hiszen (de -ban általában nem). Az 5.3. lemma és a 3.9. következmény miatt a mátrix -edik determinánsosztója . Az analóg állítás érvényes esetében is. Tekintsük a mátrix első oszlopa szerinti Laplace-kifejtését, ahol az első oszlophoz, az utolsó oszlophoz tartozó aldeterminánsok, a megfelelő előjelek, és . Legyen és . Ekkor és skaláris szorzata a mátrix determinánsa (aminek abszolút értéke a által generált rács alap-parallelotópjának térfogata, azaz indexe). Jelölje és az , illetve rácsok alap-parallelotópjának térfogatát. Az 5.1. állítás miatt a vektor komponenseinek négyzetösszege, hiszen a négyzetre emelés után az előjelek már nem számítanak, és ugyanez áll -re és -re is. Mivel e két rács ortogonális, . Ez azt jelenti, hogy a és vektorokra fölírt Cauchy-egyenlőtlenségben egyenlőség áll. Ezért és egymás skalárszorosai. Ez a skalár szükségképpen racionális szám, azaz alkalmas és nem nulla egészekre . De a mátrix -edik determinánsosztója , ezért (és hasonlóan is) primitív vektorok. Tehát , és így .
6. Appendix: Vetítések és alkalmazásaik Az alábbi feladatokban a mátrixok normálalakja helyett geometriai módszerekkel igazolunk korábbi állításokat. Szó lesz egy számelméleti alkalmazásról is. Fő eszközünk a vetítés. Ha az és egyenesek az origóban metszik egymást, akkor az -re való irányú vetítés az a leképezés, amely a sík minden pontjához az egyenes azon pontját rendeli, melyre párhuzamos -vel. Ha és alterek, és minden eleme egyértelműen fölírható egy -beli és egy -beli vektor összegeként, akkor azt mondjuk, hogy a és alterek direkt összege, jele . Az egyértelműség feltétele, hogy csak a nullvektorból álljon. A bázisok nyelvén ez azt jelenti, hogy van olyan bázis -ban, és bázis -ben, hogy ezek együtt bázist alkotnak -ban. Hasonlóan értelmezzük azt is, amikor az és csoportok direkt összege, azaz . Ha , ahol és , akkor az a leképezés, amely -hez -t rendeli, az -nak az -ra való vetítése a irányban. Ha , akkor , vagyis a vetítés ,,kinullázza'' az utolsó koordinátát.
6.1. feladat. Legyen , ahol egy fölött -dimenziós racionális altér. Igazoljuk, hogy pontosan akkor racionális altér, ha -nak az -ra vett irányú vetületében nincs -nél több fölött független vektor.
Útmutatás. Legyen racionális bázis -ban és maximális számú, fölött független racionális vektor -ben. Ha , akkor van olyan , ami fölött független -től. Ekkor vetülete független fölött -től.
6.2. feladat. Igazoljuk, hogy ha független fölött, akkor az általuk generált csoport nem diszkrét, ezért nem is rács.
Útmutatás. Föltehető ( szerinti indukcióval), hogy független fölött, legyen az általuk generált rács és az általuk kifeszített parallelotóp. Tekintsük az vektorokat ( egész), és mindegyiket toljuk vissza -be a megfelelő elemével. A kapott pontok mind különbözők függetlensége miatt.
6.3. feladat. Igazoljuk, hogy minden irracionális szám egész többszöröseinek törtrészei sűrűn helyezkednek el -ben (azaz minden rész-intervallumban van törtrész).
Útmutatás. Az előző feladat és esetén azt adja, hogy -ben végtelen sok ilyen törtrész van. Ezért minden -ra lesz kettő -nál közelebb egymáshoz. A megfelelő egész szorzókat kivonva olyan törtrészt kapunk, ami a nullához van -nál közelebb. Minden hosszú intervallumba beleesik ennek valamelyik többese.
Sokkal erősebb állítás is igazolható Minkowski rácsokról szóló tétele segítségével: ha irracionális, akkor van végtelen sok olyan tört, melyek bármelyike -tól kevesebb, mint -tel tér el (lásd [2], 8.2. szakasz). Kronecker approximációs tétele arra ad feltételt, hogy egész többesei -ben alkossanak sűrű halmazt.
6.4. feladat. Tegyük föl, hogy racionális altér és a -nak az -ra vett irányú vetülete. Mutassuk meg, hogy pontosan akkor rács -ban, ha is racionális altér.
Útmutatás. Ha racionális altér, racionális bázis -ban és racionális bázis -ben, akkor írjuk föl ezekkel egy bázisát. Ha az együtthatók közös nevezője , akkor minden vektor -ra eső vetületének -szerese benne van a generálta csoportban. Így diszkrét, és nyilván fölött generálja az alteret. Megfordítás: 6.1. és 6.2.
6.5. feladat. Mutassuk meg a normálalak használata nélkül, hogy a következményben -ből következik .
Útmutatás. A szerint valamely független által generált csoport tiszta -ban. Legyen racionális bázisa -nak, a által generált valós altér, és a által generált valós altér. A 6.4. feladat miatt -nak az -ra vett irányú vetülete rács -ban, legyenek olyan vektorok, melyek vetülete bázis -ben. Ekkor minden esetén vannak olyan egészek, hogy . Tehát fölírható racionális együtthatós lineáris kombinációjaként, és ezért alkalmas egészre . Mivel tiszta, és ezért bázis -ban.
6.6. feladat. Legyen rács, bázis -ban, a által generált, a által generált valós altér. Vetítsük -t -ra irányából. Igazoljuk, hogy ha , akkor a vetület , és .
Útmutatás. A vektor vetülete -ra . Ha , akkor miatt , azaz a vetület része -nak.
6.7. feladat. Legyen rács, nem nulla vektor és a -re merőleges -beli vektorok halmaza. Vetítsük -t merőlegesen a egyenesére. Mutassuk meg, hogy van legrövidebb nem nulla vetület, és ha vetülete egy ilyen legrövidebb vektor, akkor , ahol a egész többszöröseinek halmaza.
Útmutatás. Az vektor -re eső vetületének hossza az skaláris szorzat osztva hosszával. Mivel egész, ezért a vetületek között tényleg van legrövidebb. Tehát vetülete rács a egyenesén, és ezért minden vektor vetülete egész számszorosa. Ha vetülete , akkor merőleges -re, és ezért -ben van.
6.8. feladat. Legyen primitív vektor -ban és a -re ortogonális egész vektorok halmaza. Bizonyítsuk be, hogy hossza megegyezik alap-parallelotópjának térfogatával. (Ez McMullen tételének speciális esete.)
Útmutatás. Mivel primitív, van olyan vektor, melynek -vel vett skaláris szorzata (oldjuk meg a lineáris diofantoszi egyenletet). Az előző feladatot a rácsra alkalmazva azt kapjuk, hogy és generálják -t, azaz egy alap-parallelotópja -vel együtt egy térfogatú parallelotópot feszít ki. Ennek alapja , magassága pedig a vektor irányú vetületének hossza, ami hosszának reciproka.
6.9. feladat. Igazoljuk, hogy a háromdimenziós térben minden egész vektor előáll két egész vektor vektoriális szorzataként.
Útmutatás. Föltehető, hogy primitív, alkalmazzuk az előző feladatot. Második, elemi megoldás: ha -at akarjuk és vektoriális szorzataként előállítani, akkor legyen . Föltehető, hogy ; ha , akkor és megfelelő.
6.10. feladat. Mutassuk meg a normálalak fölhasználása nélkül, hogy ha rács, akkor van olyan bázisa -nak, hogy alkalmas egészekre bázis -ben.
Útmutatás. Vegyünk egy olyan vektort, melynek -beli magassága a lehető legkisebb. Ekkor primitív, így van olyan , melynek -vel vett skaláris szorzata . Jelölje a -re merőleges egész vektorok halmazát. A 6.8. feladatban használt gondolatmenet miatt és generálja -t, és ha vetülete egyenesére , akkor a merőleges vetülete egyenesére a egész többeseiből áll. Vetítsük a rácsot is merőlegesen egyenesére, és a vetület legrövidebb vektorát jelölje . Ha vetülete , akkor a 6.7. feladat miatt -t generálja és . Az magassága -ban legyen , föltevésünk szerint . Az vektort egyenesére vetítve többszörösét kapjuk, ezért . Mivel vetülete , ezért . Ez csak úgy lehetséges, ha . Vagyis találtunk egy olyan vektort, amelyre és generálja -t, és és generálja -t. Vegyünk egy bázist -ben, és írjuk föl ebben elemeit is (ilyen átkoordinátázást használtunk a 3.11. feladatban). Az átkoordinátázás után -ből lesz. Alkalmazzunk szerinti indukciót, ekkor van olyan bázis -ben, hogy bázis -ben. Legyen és . Az alábbi feladat többszöri alkalmazásával elérhetjük az oszthatóságot.
6.11. feladat. Tegyük föl, hogy bázis a rácsban és bázis a rácsban. Legyen az és legnagyobb közös osztója, pedig a legkisebb közös többszörösük. Válasszunk olyan és egészeket, melyekre , legyen és . Mutassuk meg, hogy bázis -ben és bázis -ben.
[4] | Peter McMullen: Determinants of lattices induced by rational subspaces, Bull. London Math. Soc., 16 (1984), 275‐277. |
|
|