Véges geometria

A véges geometria a matematikának a véges sok pontból építkező geometriai rendszerekkel foglalkozó része (neve ellenére inkább a kombinatorika és a diszkrét matematika, mint a geometria részeként szokás tárgyalni). Véges geometriáknak nevezik a tanulmányozott matematikai struktúrákat is. A véges geometriai problémák általában absztrakt algebrai és lineáris algebrai fogalmakhoz és megoldási módszerekhez vezetnek.

Az euklideszi geometria nem véges geometria, mert axiómái megkövetelik, hogy bármely két pont között legyen pont, így végtelen sok pontból építkezik. Habár a véges projektív síkok a legtöbbet tanulmányozott véges geometriák, egy véges geometria akárhány, de véges dimenziós lehet, és teljesítheti akár az euklideszi, akár a hiperbolikus párhuzamossági axiómát is, de akár egyiket sem.

Véges geometriák definiálhatók véges testek fölötti vektorterekként, vagy lehetnek kombinatorikai konstrukciók. Például a magasabb dimenziós projektív terek a Desargues-tétel miatt csak test fölötti, Galois-geometriák lehetnek. Mivel a Desargues-tétel csak magasabb dimenzióban bizonyítható, ezért nincs kizárva olyan projektív síkok létezése, amiken a tétel nem teljesül; és valóban léteznek is ilyen projektív síkok például 9²+9+1=91 ponton. Ezek a síkok nem Galois-síkok.

Síkok

Rend

A véges projektív és affin síkok minden egyenesére ugyanannyi pont illeszkedik. A vektorterekként definiálható, testre épített projektív síkoknál ez a szám q+1, ahol is a q prímhatvány a test méretét jelöli. Ezért a véges projektív síkok rendje definíció szerint eggyel kisebb, mint az egy egyenesen levő pontok száma. A projektív síkokból származtatható véges affin síkok rendje viszont megegyezik az illeszkedő egyenesek, mint ponthalmazok méretével.

Az eddig ismert projektív síkok és a belőlük származtatott affin síkok mind prímhatvány rendűek, de jelenlegi ismereteink szerint nem zárható ki, hogy vannak más síkok is. Néhány szám, mint a 6 vagy a 14 kizárható, de még mindig lehetnek például 12 vagy 18 rendű projektív síkok. A Bruck–Ryser-tétel szerint ugyanis, ha egy nem prímhatvány pozitív egész 4k+1 vagy 4k+2 alakú, és nem írható fel két négyzetszám összegeként, akkor nincs n rendű projektív sík. Más tételek újabb számokat zárnak ki. A 10-ről gépi támogatással látták be, hogy nem lehet projektív sík rendje.

Egy másik hasonlóan fontos kérdés, hogy vannak-e nem testre épített véges prím rendű projektív síkok. Kis prímekre ez az eshetőség kizárható; nagy prímekre nincs a Bruck–Ryser-tételhez hasonló eredmény. Még a 11 sem zárható ki.

Affin síkok

Másodrendű affin sík. Az azonos színű egyenesek párhuzamosak

Harmadrendű affin sík 9 ponttal és 12 egyenessel

Egy véges affin sík egy X véges nem üres ponthalmaz, aminek egyes nem üres ponthalmazai egyenesek. Emellett teljesülnek még a következő axiómák:

• Minden pontpárra egy, és csak egy egyenes illeszkedik
• Ha adva van egy l egyenes, és egy rajta kívül fekvő p pont, akkor egyértelműen van egy l-t nem metsző egyenes, ami átmegy a p ponton
• Van négy olyan pont, amik közül egyik hármas sem illeszkedik egy egyenesre

Ez az utolsó axióma az elfajult esetek kizárására való.

A legegyszerűbb affin sík a mindössze négy pontból álló másodrendű affin sík. Mivel a négy pont közül semelyik három sincs egy egyenesen, bármely pontpár meghatároz egy egyenest, így a sík hat egyenest tartalmaz. A sík ábrázolható tetraéderként, aminek csúcsai a sík pontjai, és nem metsző élei párhuzamosak, vagy egy olyan négyzetként, aminek nemcsak az oldalai, hanem az átlói is párhuzamosak. Általában, egy n-edrendű véges affin sík n² pontot és n²+n egyenest tartalmaz.

Projektív síkok

A Fano-sík

Dualitás a Fano-síkon: pontok és egyenesek megfeleltetése

Egy véges projektív sík egy X véges nem üres ponthalmaz, aminek egyes nem üres ponthalmazai egyenesek. Emellett teljesülnek még a következő axiómák:

• Bármely két ponthoz egyértelműen van egy egyenes, ami mindkettőre illeszkedik
• Bármely két egyeneshez egyértelműen van egy pont, ami mindkettőre illeszkedik
• Van négy olyan pont, amik közül egyik hármas sem illeszkedik egy egyenesre

Ez az utolsó axióma az elfajult esetek kizárására való.

Az első két axióma hasonló, csak az egyenesek és a pontok szerepe cserélődik fel benne. Habár a harmadik axióma nem önduális, mégis teljesül a dualitás elve, hogy ha egy állítás csak egyenesek és pontok illeszkedéséről szól, akkor az igazságértéke ugyanaz marad, ha felcseréljük az egyenes és a pont szót. A dualitás elve még azokon a (nem testre épített) síkokon is teljesül, amik nem önduálisak.

A legkisebb projektív sík a hét pontból álló Fano-sík, ami éppen a másodrendű projektív sík. Ha bármely egyenesét pontjaival együtt eltávolítjuk, akkor másodrendű affin sík marad. Általában, egy n-edrendű projektív sík n²+n+1 pontot és ugyanennyi egyenest tartalmaz; minden egyenes n+1 pontból áll, és minden ponton n+1 egyenes megy át.

Az illeszkedéstartó, és pontot pontba vivő transzformációkat projektív transzformációknak vagy kollineációnak nevezik. A Fano-sík kollineációcsoportja egy 168 elemű csoport, ami izomorf PSL(2,7)-tel, PSL(3,2)-vel és GL(3,2)-vel.

Hiperbolikus síkok

Az affin és a projektív párhuzamossági axiómák mellett felvethető az a kérdés is, hogy vannak-e olyan véges síkok, amiken egy adott egyeneshez egy adott ponton át több párhuzamos is húzható. Ehhez az adott ponton átmenő egyeneseket két osztályba soroljuk aszerint, hogy metszik-e az adott egyeneseket. A következőkben a metsző egyenesek számát m, a nem metszőkét n fogja jelölni. Ha ezek a számok minden pont-egyenes párra ugyanazok, akkor a véges hiperbolikus sík reguláris, de létezhetnek nem reguláris hiperbolikus síkok is. A reguláris hiperbolikus síkok jellemezhetők az m és az n paraméterekkel; röviden <m,n> síkoknak nevezik őket.

Az <m,n> síkokat több szerző így axiomatizálja:

• Két pontra egyértelműen illeszkedik egyenes
• Minden egyeneshez van olyan pont, ami nem illeszkedik rá
• Minden nem illeszkedő egyenes-pont párra n olyan egyenes van, ami átmegy az adott ponton, és metszi az adott egyenest
• Van m pontú egyenes, ahol is m pozitív

Ezek az axiómák azonban nem zárják ki az elfajult alakzatokat, például a teljes ötszöget, vagy a K(2,2,2) gráfot.

Kárteszi Ferenc egy olyan axiómarendszert ajánl, ami kizárja ezeket az eseteket:

• Minden pontpárhoz van egy rá illeszkedő egyenes
• Minden nem illeszkedő egyenes-pont párra a pontra illeszkedő metsző, illetve nem metsző egyenesek száma rendre m és n
• Van háromszög, azaz van három nem egy egyenesre illeszkedő pont
• (m-1)²>n>2

A legkisebb példa a <3,3>-sík, ami 13 pontot és 26 egyenest tartalmaz. Általában, a véges hiperbolikus síkra (m+n)(m-1)+1 pont és (m+n)[(m+n)(m-1)+1]/m illeszkedik, ahol is n(n-1) osztható m-mel. Így a két paraméter nem független egymástól.

A legkisebb véges reguláris hiperbolikus sík illeszkedéstáblája:

--            --            --
  --            --          --
    --            --        --

       --            --     --
         --            --   --
           --            -- --

  ----               --       
--  --                 --     
----                     --

--       ----                 
    -- --  --                 
  --   ----

--                -- --       
  --              --   --     
    --        ----       --

--     --       --            
  --       -- --              
    --   --     --

       --     --       --     
         --          --  --   
           --   ----

       --         --     --   
         --   --  --          
           --        ----

              ----   --        
                --     ----   

Nevezetes alakzatok

• A Desargues-konfiguráció:

legyen D pont, és menjen át rajta a c₁, c₂ és c₃ egyenes. Ezeken az egyeneseken vegyük fel rendre az A₁, az A₂ és az A₃ pontokat, valamint a B₁, a B₂ és a B₃ pontokat. Legyen a C₃ pont az A₁A₂ és a B₁B₂ egyenes metszéspontja, a C₂ az A₂A₃ és a B₂B₃ egyenesé, valamint a C₁ az A₁A₃ és a B₁B₃ egyeneseké.

Ha C₁, C₂ és C₃ egy egyenesre esik, akkor ezek a pontok és egyenesek Desargues-féle konfigurációt alkotnak. Ha ez a szerkesztés minden esetben Desargues-konfigurációt ad, akkor a síkon teljesül a Desargues-tétel. Ez egyben azt is jelenti, hogy a sík testre épült. Fordítva, minden testre épített síkon bizonyítható a Desargues-tétel.

• Egymásba írt ötszögek:

Az A₁A₂A₃...A_n sokszög bele van írva a B₁B₂B₃...B_n sokszögbe, ha az A₁, A₂, A₃, ..., A_n pontok rendre illeszkednek a B₁B₂B₃...B_n sokszög megfelelő oldalaira. Ha a projektív sík elég nagy, akkor vannak rajta olyan ötszögek, amik kölcsönösen egymásba vannak írva

• Részsíkok és blokkoló halmazok:

A részsíkok a Galois-síkokat koordinátázó test résztestjei által koordinátázott pontok halmazai. Részsíkok akkor vannak, ha a test q mérete nem prímszám. Ha q=p^2h, akkor a rajta levő p^h rendű részsíkoknak az a nevezetes tulajdonsága van, hogy nem egyenesek, de a sík minden egyenese átmegy rajtuk. Az ilyen tulajdonságú halmazok a sík nem triviális lefogó, más néven blokkoló halmazai. A véges geometria fontos kérdése az, hogy egy síkon milyen és mekkora blokkoló halmazok léteznek.

• Másodrendű görbék:

Szintén nevezetesek a véges projektív síkok másodfokú egyenletekkel leírható, másodfokú görbéi, más néven oválisai. A nem elfajuló másodrendű görbékről beláthatók azok a megszokott tulajdonságok, hogy nem tartalmaznak egyenest, hogy minden pontjukban két érintőjük van, és hogy minden szelőjük két pontban metszi őket. Páratlan rendű síkokon egyféle másodrendű görbe van, és mérete q+1. Páros rendű síkokon többféle is van, de mindegyik mérete q+2.

Magasabb dimenziós véges terek

A háromdimenziós Fano-tér

A magasabb dimenziós véges terek mind testre épített terek, mivel a legalább háromdimenziós projektív geometriákban bizonyítható a Desargues-tétel. Egy test fölötti háromdimenziós projektív tér a test fölötti négydimenziós vektortérrel azonosítható, ahol:

• a pontok az egydimenziós alterek
• az egyenesek a kétdimenziós alterek
• a síkok a háromdimenziós alterek

Ezek a terek is axiomatizálhatók. A következő axiómarendszer alapfogalomnak tekinti a pontokat és az egyeneseket, de a síkokat és a teret definiálja:

• Illeszkedési axiómák

• Ha A és B pontok, akkor van egyenes, amire illeszkednek
• Ha A és B pontok, akkor a rájuk illeszkedő egyenes egyértelmű
• Ha A, B és C nem illeszkednek egy egyenesre, és E, F különböző pontok úgy, hogy B, C és D egy egyenesre esnek, és C, A és E egy egyenes pontjai, akkor van egy F pont, hogy A, B, F is egy egyenesre illeszkedik, és D, E és F is egy egyenes pontjai.

• Létezési axiómák

• Van legalább egy egyenes
• Minden egyenesen legalább három pont van
• Nincs minden pont egy egyenesen
• Nincs minden pont egy síkon
• Ha S3 háromdimenziós tér, akkor minden pont S3-ban van.

A legkisebb háromdimenziós projektív tér a kételemű test fölötti projektív tér. 15 pontot, 35 egyenest és 15 síkot tartalmaz. Minden sík 7 pontból áll, 7 egyenest tartalmaz, és izomorfak a Fano-síkkal. Minden pont 7 egyenesre illeszkedik, és minden egyenes három pontot tartalmaz. Bármelyik pontpárhoz egyértelműen van rajta átmenő egyenes, és bármely síkpár egy egyenesben metszi egymást. Gino Fano 1892-ben fedezte fel ezt a geometriát.

Általában, bármely pozitív n-re egy n dimenziós tér geometriája n dimenziós geometria. Magasabb dimenziókra a létezési axiómák sora folytatható; például négy dimenzióban: Nincs minden pont egy három-térben, és Ha S4 4 dimenziós tér, akkor minden pont S4-ben van. Ezeknek a tereknek számos elméleti alkalmazásuk van.

A háromdimenziós projektív terekből affin terek is készíthetők egy sík, az egyenesei és pontjai elhagyásával. Hasonlóan, egy n dimenziós projektív tér affin térré alakítható egy (n-1)-dimenziós altér és annak altereinek elhagyásával.

A háromdimenziós projektív tér előáll diszjunkt egyenesek uniójaként. Hasonlóan, egy magasabb dimenziós projektív tér előáll egy bizonyos dimenziójú diszjunkt altereinek uniójaként, ha pontjainak száma osztható az altér pontjainak számával. Ha a tér dimenziója t, az altereké l, akkor q^t+q^t-1+ ... +1 osztható q^l+q^l-2+ ... +1-gyel. A blokkoló halmazokhoz hasonlóan készítenek maximális, azaz nem bővíthető diszjunkt altereket tartalmazó halmazokat is. Ezek az altérhalmazok a maximális befedések. A véges geometria egy ismert kérdése, hogy mekkora lehet egy maximális befedés.

Általánosításuk

A blokkrendszerek a véges geometriák általánosításának tekinthetők. Egy t-(v,k,λ) blokkrendszerben v pont van, a blokkok pontszáma k, és minden t elemű ponthalmazon λ blokk megy át. Például a projektív síkok 2-(n²+n+1,n+1,1)-blokkrendszernek tekinthetők, de az affin síkok is blokkrendszerek, és egyes projektív síkokból bővítéssel újabb blokkrendszerek kaphatók. Így keletkezik például a Möbius-féle körsík. Ezeken kívül még sok más blokkrendszer is létezik.

Kombinatorikai alkalmazások

Kirkman iskoláslány problémája így szól: 15 iskolás lány minden nap öt hármas csoportban sétál. Adjunk meg egy olyan beosztást, amiben bármely két lány heti egy alkalommal kerül össze!

A feladat megoldása kapcsolódik a Fano-térhez. A Fano-térben ugyanis a hármasok egyeneseknek felelnek meg. Minden napra öt egyenes kell, és ez a heti hét nappal szorozva 35; éppen ennyi egyenes van a Fano-térben. A pontok száma 15, és minden pontra 7 egyenesnek kell illeszkednie.

A véges geometriák által az abszolút geometriáról is megtudhatunk valamit. Ha e és f egyenesek, akkor jelölje e x f azt, hogy a két egyenes merőlegesen metszi egymást. Ha pedig g₁, g₂, g₃, g₄ kitérő egyenesek, akkor a g_i és a g_j közös merőlegesét jelölje n_ij. Ha a normáltranszverzálisok léteznek, és n₁₂ x n₃₄, n₁₃ x n₄₂, akkor a harmadik pár is merőleges, vagyis n₁₄ x n₂₃.

Általánosítható a Petersen-gráf is. Jelölje Γ(n,k,l) azt reguláris a gráfot, aminek rendje k, a legkisebb köre l hosszú, és n az ilyen gráfok között a minimális csúcsszám. A véges projektív síkokkal konstruálható olyan gráf, ahol k=n+1, l=6, ha van n-edrendű projektív sík.

Megkonstruálható a legnagyobb élszámú négyszögmentes páros gráf is. Legyen a két pontosztály a projektív sík egyeneseinek, illetve pontjainak osztálya, és jelentsék az élek az illeszkedési relációt. A véges projektív sík axiómái szerint nem létezhet négyszög, mert akkor két pontra két egyenes is illeszkedne. Egy osztályon belül pedig nem létezhet él, mivel az illeszkedés a pont-egyenes rendezetlen párokon értelmezett reláció.

Források

• Kárteszi Ferenc: Bevezetés a véges geometriákba
• Margaret Lynn Batten : Combinatorics of Finite Geometries. Cambridge University Press
• Dembowski: Finite Geometries.
• Lam, C. W. H. (1991), "The Search for a Finite Projective Plane of Order 10", American Mathematical Monthly 98 (4): 305–318, <http://www.cecm.sfu.ca/organics/papers/lam/>
• Eves, Howard. A Survey of Geometry: Volume One. Boston: Allyn and Bacon Inc., 1963.
• Meserve, Bruce E. Fundamental Concepts of Geometry. New York: Dover Publications, 1983.
• Polster, Burkard. Yea Why Try Her Raw Wet Hat: A Tour of Projective the Smallest Space. Volume 21, Number 2, 1999. [1]
• “Problem 31: Kirkman's schoolgirl problem” [2]