kombinatorika

Ortogonalni latinski kvadrati i konačne projektivne ravnine

 
Rafael Mrđen,
student na PMF-Matematičkom odjelu
e-mail: rafaelmrdjen@gmail.com

Sažetak
U ovom članku uvodi se pojam latinskog kvadrata, njegove ortogonalnosti, te konačne projektivne ravnine (s kombinatornog aspekta). Navode se i dokazuju neka njihova osnovna svojstva i veze. Dokazuje se dovoljan uvjet egzistencije konačne projektivne ravnine zadanog reda. Najjači rezultat koji se dokazuje jest Bruck-Ryserov teorem, koji daje neke nužne uvjete na red konačne projektivne ravnine. Na kraju, kratko i informativno daje se uvid u generalizaciju.




1Ortogonalni latinski kvadrati

Tijekom povijesti latinski su kvadrati bili dio zabavne matematike. Međutim, u jednom su trenu matematičari uvidjeli netrivijalnost kombinatornih problema koji proizilaze iz razmatranja o latinskim kvadratima, kao i primjenu u drugim granama matematike. Mi ćemo razviti teoriju latinskih kvadrata u mjeri koja nam je potrebna da uspostavimo vezu s konačnim projektivnim ravninama.

Definicija. Kažemo da je kvadratna matrica A reda n \in \mathbb{N} latinski kvadrat ako vrijedi:
\bullet Elementi matrice A su elementi nekog n-članog skupa1\lbrace a_{1},a_{2},\ldots,a_{n}\rbrace;
\bullet U svakom retku matrice A, svaki a_{i}, i=1,2,\ldots{},n nalazi se na točno jednom mjestu;
\bullet U svakom stupcu matrice A, svaki a_{i}, i=1,2,\ldots{},n nalazi se na točno jednom mjestu.

Primjer 1. Vrlo je lako provjeriti da su matrice
M := \left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array} \right) \quad \text{i} \quad N := \left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{array} \right)
latinski kvadrati reda 3.


Općeniti latinski kvadrati neće nam biti posebno zanimljivi, ali hoće familije latinskih kvadrata istog reda koje imaju sljedeće svojstvo:

Definicija. Za latinske kvadrate A_{1}=\Big(a_{ij}^{(1)}\Big)_{ij} i A_{2}=\Big(a_{ij}^{(2)}\Big)_{ij} reda n kažemo da su ortogonalni ako skup2
\Big\lbrace \Big(a_{ij}^{(1)},a_{ij}^{(2)}\Big) \ : \ i,j=1,2,\ldots{},n \Big\rbrace
sadržava n^{2} različitih uređenih parova. Očito je ekvivalentno zahtijevati da je
\Big(a_{i_{1}j_{1}}^{(1)},a_{i_{1}j_{1}}^{(2)}\Big) \neq \Big(a_{i_{2}j_{2}}^{(1)},a_{i_{2}j_{2}}^{(2)}\Big), \text{ čim je } i_{1} \neq i_{2} \text{ ili } j_{1} \neq j_{2}.
Kažemo da je skup \lbrace A_{1},A_{2},\ldots,A_{t}\rbrace latinskih kvadrata istog reda ortogonalan ako su svaka dva različita elementa tog skupa ortogonalna.

Napomena. Uz ortogonalne latinske kvadrate veže se jedna poznata Eulerova hipoteza: Ako je n \equiv 2 \pmod{4}, tada ne postoje ortogonalni latinski kvadrati reda n. Pokazalo se poslije da je hipoteza pogrešna, točnije, da postoje ortogonalni latinski kvadrati reda n za n \in \mathbb{N} \setminus \lbrace 2,6\rbrace. Više o tome vidi u [2], str. 151.–152.

Propozicija 2. Neka je S=\lbrace A_{1},A_{2},\ldots,A_{t}\rbrace ortogonalan skup latinskih kvadrata, reda n \geq 3. Tada je t \leq n-1.

Dokaz. Budući da nam je bitan samo raspored elemenata u latinskom kvadratu, a ne svojstva samih elemenata, možemo bez smanjenja općenitosti svakom posebno preimenovati elemente; time nećemo pokvariti ni definicijska svojstva latinskog kvadrata, niti ortogonalnost s drugim latinskim kvadratima, naravno, uz uvjet da različitim elementima pridružimo različito ime. Svakom latinskom kvadratu A_{i} \in S preimenujmo prvi redak u (1 \ 2 \ \ldots \ n). Budući da se u prvom retku od A_{i} nalazi svaki element (točno jednom), time su jedinstveno određena imena elemenata u svim preostalim retcima od A_{i}. Dakle, možemo smatrati da su
A_{1}= \left(\begin{array}{cccc}1 & 2 & \ldots & n \\ \vdots & \vdots & \vdots & \vdots \end{array}\right), \quad A_{2}= \left(\begin{array}{cccc}1 & 2 & \ldots & n \\ \vdots & \vdots & \vdots & \vdots \end{array}\right), \quad \ldots
\ldots, \quad A_{t}= \left(\begin{array}{cccc}1 & 2 & \ldots & n \\ \vdots & \vdots & \vdots & \vdots \end{array}\right).
Promotrimo koji brojevi mogu biti na mjestu (2,1) u tim matricama. Tu ne može biti 1, jer su te matrice latinski kvadrati. Također, zbog međusobne ortogonalnosti, ti brojevi očito moraju biti različiti za različite matrice, kojih ima t. Brojevi su iz skupa \lbrace 2,3,\ldots,n\rbrace, pa slijedi t \leq n-1, tj. tvrdnja teorema.
\ \blacksquare

Napomena. Gornji dokaz možemo provesti i u slučaju n=2, te zaključiti da ne postoje dva različita ortogonalna latinska kvadrata reda 2.

Primjer 3. Latinski kvadrati M i N iz primjera 1 su ortogonalni, jer njihovom superpozicijom dobivamo skup
\left\lbrace \begin{array}{ccc} (1,1) & (2,2) & (3,3) \\ (2,3) & (3,1) & (1,2) \\ (3,2) & (1,3) & (2,1) \end{array} \right\rbrace
u kojem se nalaze svi mogući uređeni parovi elemenata iz skupa \lbrace 1,2,3\rbrace. Možemo po propoziciji 2 zaključiti da ne postoji ni jedan latinski kvadrat koji bi istovremeno bio ortogonalan s M i N.


Sada kada znamo da postoje ortogonalni latinski kvadrati, te kada imamo gornju među za njihov broj, postavlja se pitanje koliko ih zapravo može biti za zadani red. Odgovor na to općenito nije poznat. Međutim, u nekim posebnim slučajevima ipak možemo primjetiti da se ta gornja međa postiže. To je sadržaj sljedećeg teorema.

Definicija. Ako ortogonalan skup latinskih kvadrata reda n ima n-1 element, kažemo da je taj skup potpun (ili zasićen).

Teorem 4. Neka je n prim-potencija3. Tada postoji potpun skup ortogonalnih latinskih kvadrata reda n.

Dokaz. Za brojeve oblika n=p^{m} postoji konačno (Galoisovo) polje reda n, u oznaci (GF(n),+,\cdot) – vidi [1], str. 280. Neka su svi (međusobno različiti) elementi tog polja sljedeći4: a_{0}=0, a_{1}=1, a_{2}, a_{3}, \ldots, a_{n-1}. Definirajmo matrice
(1)
A_{k}=\Big(a_{ij}^{(k)}\Big)_{i,j=0,1,\ldots{},n-1} \qquad k=1,2,\ldots{},n-1
na sljedeći način:
(2)
a_{ij}^{(k)}:=a_{k} a_{i} + a_{j} \qquad i,j=0,1,\ldots{},n-1 \quad k=1,2,\ldots{},n-1.
Dokažimo da je svaka matrica iz (1) latinski kvadrat. Budući da u našem polju ima n elemenata, kao i mjesta u svakom retku (stupcu) matrice A_{k}, dovoljno je dokazati da se u svakom retku (stupcu) pojavljuju samo različiti elementi. Pretpostavimo da matrica A_{k} u istom retku ima dva ista elementa, tj. neka je a_{ij_{1}}^{(k)}=a_{ij_{2}}^{(k)}. Zbog (2) vrijedi:
a_{k} a_{i}+a_{j_{1}}=a_{k} a_{i} + a_{j_{2}} \quad \Rightarrow \quad a_{j_{1}}=a_{j_{2}} \quad \Rightarrow \quad j_{1}=j_{2},
pa vidimo da ti elementi moraju biti i u istom stupcu. Slično za stupce, pretpostavimo da matrica A_{k} u istom stupcu ima dva ista elementa, tj. a_{i_{1} j}^{(k)}=a_{i_{2} j}^{(k)}. Opet zbog (2) imamo:
a_{k} a_{i_{1}}+a_{j}=a_{k} a_{i_{2}} + a_{j} \quad \Rightarrow \quad a_{k} a_{i_{1}}=a_{k} a_{i_{2}} \quad \Rightarrow \quad a_{k} (a_{i_{1}}-a_{i_{2}})=0.
Sad iskoristimo činjenicu da u polju nema djelitelja nule, te a_{k} \neq 0 (jer je k\gt 0), pa imamo
a_{i_{1}}-a_{i_{2}}=0 \quad \Rightarrow \quad a_{i_{1}}=a_{i_{2}} \quad \Rightarrow \quad i_{1}=i_{2}.
Dakle, matrice (1) su latinski kvadrati (reda n). Dokažimo još da su svaka dva međusobno ortogonalna. Neka su k,k' \in \lbrace 1,2,\ldots,n-1\rbrace međusobno različiti. Uočimo da je tada i a_{k} \neq a_{k'}, tj. a_{k} - a_{k'} \neq 0. Pretpostavimo da za neke i_{1},i_{2},j_{1},j_{2} \in \lbrace 0,1,\ldots,n-1\rbrace vrijedi
\Big(a_{i_{1} j_{1}}^{(k)},a_{i_{1} j_{1}}^{(k')}\Big)=\Big(a_{i_{2} j_{2}}^{(k)},a_{i_{2} j_{2}}^{(k')}\Big).
To povlači a_{i_{1} j_{1}}^{(k)}=a_{i_{2} j_{2}}^{(k)} i a_{i_{1} j_{1}}^{(k')}=a_{i_{2} j_{2}}^{(k')}, iz čega slijede izrazi
(3)
a_{k} a_{i_{1}}+a_{j_{1}}=a_{k} a_{i_{2}}+a_{j_{2}},
(4)
a_{k'} a_{i_{1}}+a_{j_{1}}=a_{k'} a_{i_{2}}+a_{j_{2}}.
Nakon što od (3) oduzmemo (4) te iskoristimo komutativnost, asocijativnost i distributivnost u polju, dobijemo
(a_{k} - a_{k'})a_{i_{1}}=(a_{k} - a_{k'})a_{i_{2}} \quad \Rightarrow \quad (a_{k} - a_{k'})(a_{i_{1}}-a_{i_{2}})=0
\Rightarrow \quad a_{i_{1}}-a_{i_{2}}=0 \quad \Rightarrow \quad a_{i_{1}}=a_{i_{2}} \quad \Rightarrow \quad i_{1}=i_{2}.
Nakon što izraz i_{1}=i_{2} stavimo u (3), trivijalno slijedi i j_{1}=j_{2}, pa su latinski kvadrati A_{k} i A_{k'} ortogonalni (uočimo da to povlači i da su međusobno različiti). Stoga je skup \lbrace A_{1},A_{2},\ldots, A_{n-1}\rbrace ortogonalan te sadržava n-1 različitih elemenata, pa je potpun.
\ \blacksquare


Sljedeći teorem nama je više tehničkog karaktera, iako je značajan i sam za sebe (npr. u teoriji kodiranja).

Teorem 5. Neka su n \geq 3, t \geq 2 prirodni brojevi. Postoji ortogonalan skup od t latinskih kvadrata reda n ako i samo ako postoji matrica tipa (t+2,n^{2}) s elementima iz skupa \lbrace 1,2,\ldots,n\rbrace, koja ima svojstvo da stupci svake podmatrice tipa (2,n^{2}) tvore n^{2} različitih uređenih parova iz skupa \lbrace 1,2,\ldots,n\rbrace, ili ekvivalentno tomu, da se pojavljuju svi mogući uređeni parovi elemenata iz tog skupa.5 Nazovimo to svojstvo (\ast).

Dokaz. Neka su
A_{1}=\Big(a_{ij}^{(1)}\Big)_{ij}, \quad A_{2}=\Big(a_{ij}^{(2)}\Big)_{ij}, \quad \ldots , \quad A_{t}=\Big(a_{ij}^{(t)}\Big)_{ij}
t latinskih kvadrata reda n, takvih da su svaka dva različita međusobno ortogonalna. Neka su, bez smanjenja općenitosti, elementi svih tih latinskih kvadrata iz skupa \lbrace 1,2,\ldots,n\rbrace. Posložimo elemente tih matrica u matricu tipa (t+2,n^{2}) na sljedeći način:
\left(\begin{array}{ccccccccccccc} 1 & 1 & \ldots & 1 & 2 & 2 & \ldots & 2 & \ldots & n & n & \ldots & n \\ 1 & 2 & \ldots & n & 1 & 2 & \ldots & n & \ldots & 1 & 2 & \ldots & n \\ a_{11}^{(1)} & a_{12}^{(1)} & \ldots & a_{1n}^{(1)} & a_{21}^{(1)} & a_{22}^{(1)} & \ldots & a_{2n}^{(1)} & \ldots & a_{n1}^{(1)} & a_{n2}^{(1)} & \ldots & a_{nn}^{(1)} \\ a_{11}^{(2)} & a_{12}^{(2)} & \ldots & a_{1n}^{(2)} & a_{21}^{(2)} & a_{22}^{(2)} & \ldots & a_{2n}^{(2)} & \ldots & a_{n1}^{(2)} & a_{n2}^{(2)} & \ldots & a_{nn}^{(2)} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{11}^{(t)} & a_{12}^{(t)} & \ldots & a_{1n}^{(t)} & a_{21}^{(t)} & a_{22}^{(t)} & \ldots & a_{2n}^{(t)} & \ldots & a_{n1}^{(t)} & a_{n2}^{(t)} & \ldots & a_{nn}^{(t)} \end{array} \right).
Nazovimo tu matricu A. Ako primijetimo da je svaka podmatrica tipa (2,n^{2}) matrice A zapravo kombinacija 2 različita retka matrice A, lako se vidi da joj stupci tvore sve različite uređene parove (njih n^{2}). Naime, za prva dva retka poprilično je jasno. Ako bi i-ti redak (2\lt i \leq t+2) s prvim ili drugim retkom tvorio dva jednaka uređena para, to bi bilo u kontradikciji s činjenicom da je A_{i-2} latinski kvadrat. Ako bi i-ti i j-ti redak (2\lt i\lt j \leq t+2) tvorili dva jednaka uređena para, to bi bilo u kontradikciji s ortogonalnošću latinskih kvadrata A_{i-2} i A_{j-2}. Dakle, matrica A ima i svojstvo (\ast).

Obrnuto, neka je A' matrica tipa (t+2,n^{2}), s elementima iz \lbrace 1,2,\ldots,n\rbrace, koja ima svojstvo (\ast). Primijetimo očitu činjenicu da se svaki broj u svakom retku pojavljuje točno n puta. Naime, ako bi se neki broj k pojavljivao više od n puta u i-tom retku, tada bi tvorio više od n uređenih parova oblika (k,\text{nešto}), u nekoj podmatrici u kojoj se nalazi i-ti redak, pa bi neka dva para morala biti jednaka. Ako bi se pak k pojavljivao manje od n puta, tada bi se neki drugi broj k' morao pojaviti više od n puta, pa provedemo analogno razmatranje za k'. Također primijetimo da se svojstvo (\ast) neće pokvariti pri permutiranju stupaca A', pa možemo pretpostaviti da A' ima prvi redak kao matrica A. Promotrimo početni komad duljine n drugog retka matrice A'. Iznad tog komada nalaze se samo jedinice, pa prvih n stupaca možemo permutirati da nam taj početni komad bude (1 \quad 2 \quad \ldots \quad n), a da se ne promijeni prvi redak. To ponovimo i za sljedeći blok duljine n (ispod dvojki), te analogno sve do kraja drugog retka. Dobili smo da prva dva retka matrice A' izgledaju kao prva dva retka matrice A, te je ostalo sačuvano svojstvo (\ast). Dakle, bez smanjenja općenitosti, neka je A'=A. Sad očito možemo reverzibilnim postupkom (dobivanja matrice A iz skupa \lbrace A_{1},A_{2},\ldots,A_{t}\rbrace) iz matrice A dobiti skup S:=\lbrace A_{1},A_{2},\ldots,A_{t}\rbrace. Lako se vidi kako svojstvo (\ast) i prva dva retka matrice A garantiraju da su matrice A_{1},A_{2},\ldots,A_{t} latinski kvadrati. Jednako je lako vidjeti da svojstvo (\ast) povlači i međusobnu ortogonalnost od A_{i} i A_{j}, za međusobno različite i,j = 1,2,\ldots{},t. Stoga je S ortogonalan skup od t latinskih kvadrata reda n.
\ \blacksquare

Primjer 6. Ortogonalna shema latinskih kvadrata M i N primjera 1 je
\left(\begin{array}{ccccccccc} 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 \\ 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\ 1 & 2 & 3 & 2 & 3 & 1 & 3 & 1 & 2 \\ 1 & 2 & 3 & 3 & 1 & 2 & 2 & 3 & 1 \end{array} \right).

Primjer 7. Dva ortogonalna latinska kvadrata reda 10 (prvi se dobije uzimajući u obzir samo znamenke jedinica brojeva u matrici, a drugi gledajući samo znamenke desetica):
\left(\begin{array}{cccccccccc} 00 & 67 & 58 & 49 & 91 & 83 & 75 & 12 & 24 & 36 \\ 76 & 11 & 07 & 68 & 59 & 92 & 84 & 23 & 35 & 40 \\ 85 & 70 & 22 & 17 & 08 & 69 & 93 & 34 & 46 & 51 \\ 94 & 86 & 71 & 33 & 27 & 18 & 09 & 45 & 50 & 62 \\ 19 & 95 & 80 & 72 & 44 & 37 & 28 & 56 & 61 & 03 \\ 38 & 29 & 96 & 81 & 73 & 55 & 47 & 60 & 02 & 14 \\ 57 & 48 & 39 & 90 & 82 & 74 & 66 & 01 & 13 & 25 \\ 21 & 32 & 43 & 54 & 65 & 06 & 10 & 77 & 88 & 99 \\ 42 & 53 & 64 & 05 & 16 & 20 & 31 & 89 & 97 & 78 \\ 63 & 04 & 15 & 26 & 30 & 41 & 52 & 98 & 79 & 87 \end{array} \right).


Za kraj odjeljka spomenimo da ne postoji „elegantna” matematička teorija uz pomoć koje bi se tražile familije ortogonalnih latinskih kvadrata. Uglavnom se za proučavanje ortogonalnih latinskih kvadrata koriste računalne metode za nalaženje, te asimptotske formule za broj takvih.

2Konačne projektivne ravnine

U ovom odjeljku želimo istaknuti samo kombinatorna svojstva projektivnih ravnina, dok geometrijska svojstva zanemarujemo (npr. ne zanima nas je li neka projektivna ravnina Desarguesova6).

Definicija. (Konačna) projektivna ravnina \Pi (reda n \in \mathbb{N}\setminus \lbrace 1\rbrace) je uređena trojka (\mathcal{T},\mathcal{P},\textbf{I}) nepraznih skupova; elemente skupa \mathcal{T} zovemo točke, skupa \mathcal{P} pravci, a \textbf{I} \subseteq \mathcal{T} \times \mathcal{P} je binarna relacija koju zovemo relacija incidencije (ako je (T,p) \in \textbf{I}, kažemo da točka T leži na pravcu p, ili pak da pravac p prolazi točkom T), te vrijedi7:
(P1) Za svake dvije različite točke postoji jedinstven pravac na kojem obje leže;
(P2) Za svaka dva različita pravca postoji jedinstvena točka kojom oba prolaze;
(P3) Svakom točkom prolazi točno n+1 pravac;
(P4) Na svakom pravcu leži točno n+1 točka.
Za dva različita pravca koja prolaze istom točkom kažemo da se sijeku u toj točki, te je ona sjecište danih pravaca. Za pravac koji prolazi kroz dvije različite točke kažemo da je spojnica tih dviju točaka, tj. da spaja te dvije točke.

Napomena. Primijetimo da je definicija projektivne ravnine simetrična s obzirom na pojmove točka i pravac. Stoga koju god tvrdnju dokažemo, vrijedit će i njoj dualna tvrdnja dobivena zamjenom pojmova točka\leftrightarrowpravac i svih izvedenih pojmova.

Primjer 8. Ako stavimo \mathcal{T}:=\lbrace 1,2,\ldots,7\rbrace i
\mathcal{P}:=\Big\lbrace \lbrace 1,2,3\rbrace ,\lbrace 3,4,5\rbrace ,\lbrace 1,5,6\rbrace ,\lbrace 1,4,7\rbrace ,\lbrace 2,5,7\rbrace ,\lbrace 3,6,7\rbrace ,\lbrace 2,4,6\rbrace \Big\rbrace ,
tada se lako provjeri da je (\mathcal{T},\mathcal{P},\in) projektivna ravnina reda 2, koju zovemo Fanova ravnina. Možemo je predočiti slikom:
Slika 1: Fanova ravnina – projektivna ravnina reda 2.

Propozicija 9. Projektivna ravnina reda n sadržava n^{2}+n+1 točku i isto toliko pravaca.

Dokaz. Neka je P bilo koja točka spomenute projektivne ravnine. Kroz nju (po (P3)) prolazi n+1 različitih pravaca, pri čemu na svakom leži n različitih točaka koje nisu P (po (P4)). Ti se pravci sijeku u P pa nemaju drugih zajedničih točaka (po (P2)). Dakle, imamo 1 + (n+1) \cdot n = n^{2}+n +1 različitih točaka. Ostaje provjeriti ima li preostalih. Ako je Q neka točka različita od P, onda (po (P1)) postoji pravac koji ih spaja. Taj pravac jedan je od onih n+1, pa smo točku Q već uračunali. Dakle, točaka ima n^{2}+n +1, a po prethodnoj napomeni isto toliko ima i pravaca.
\ \blacksquare


Sljedećim teoremom potpuno razotkrivamo vezu između projektivne ravnine reda n i potpunog skupa ortogonalnih latinskih kvadrata reda n. Izlazi da je ta veza 11 korespondencija. Štoviše, u dokazu dajemo efektivan način konstrukcije jedne strukture iz druge. To će, u kombinaciji s rezultatima iz prethodnog odjeljka osigurati neke dovoljne uvjete za egzistenciju projektivnih ravnina.

Teorem 10. Neka je n \geq 3 prirodan broj. Postoji projektivna ravnina reda n ako i samo ako postoji potpun skup ortogonalnih latinskih kvadrata reda n.

Dokaz. Neka je dana projektivna ravnina reda n, te fiksirajmo neki pravac p. Neka su sve (međusobno različite) točke koje leže na pravcu p sljedeće: P_{1},P_{2},\ldots,P_{n+1}. Preostalo je n^{2}+n+1-(n+1)=n^{2} različitih točaka koje ne leže na pravcu p. Neka su sve takve Q_{1},Q_{2},\ldots,Q_{n^{2}}. Kroz svaku točku P_{i} prolazi još n različitih pravaca koji nisu p, pa tim n injektivno pridružimo oznake iz skupa \lbrace 1,2,\ldots,n\rbrace, za i=1\ldots{}n+1 (dakle, dva pravca s istom oznakom ne moraju biti jednaka, dok dva pravca s istom oznakom koja oba prolaze točkom P_{i}, za neki i \in \lbrace 1,2,\ldots,n+1\rbrace moraju biti isti pravac). Definirajmo a_{ij} kao pravac koji je jedinstveno određen točkama P_{i} i Q_{j}, te promotrimo matricu
A := \big( \text{oznaka od } a_{ij}\big)_{i=1,2,\ldots{},n+1,j=1,2,\ldots{},n^{2}}
tipa (n+1,n^{2}). Elementi te matrice očito su iz skupa \lbrace 1,2,\ldots,n\rbrace. Dokažimo da A ima svojstvo (\ast). Ako pretpostavimo da nije tako, tada postoje međusobno različiti i_{1}, i_{2} \in \lbrace 1,2,\ldots,n+1\rbrace i međusobno različiti j_{1}, j_{2} \in \lbrace 1,2,\ldots,n^{2}\rbrace takvi da vrijedi
(\text{oznaka od } a_{i_{1} j_{1}},\ \text{oznaka od } a_{i_{2} j_{1}})=(\text{oznaka od } a_{i_{1} j_{2}}, \ \text{oznaka od } a_{i_{2} j_{2}}).
Izjednačavanjem prvih komponenti uređenih parova dobijemo da je oznaka od a_{i_{1} j_{1}} ista kao i oznaka od a_{i_{1} j_{2}}, za pravce a_{i_{1} j_{1}} i a_{i_{1} j_{2}} koja oba prolaze točkom P_{i_{1}}. Stoga mora biti a_{i_{1} j_{1}} = a_{i_{1} j_{2}}. Potpuno analogno je i a_{i_{2} j_{1}} = a_{i_{2} j_{2}}. Neka je q pravac određen točkama Q_{j_{1}} i Q_{j_{2}}. Vrijedi:
Q_{j_{1}} \ \text{leži na} \ a_{i_{1} j_{1}} = a_{i_{1} j_{2}}, \ Q_{j_{2}} \ \text{leži na} \ a_{i_{1} j_{2}} \ \stackrel{\href{#P1}{(P1)}}{\Rightarrow} \ q=a_{i_{1} j_{2}} \ \Rightarrow \ P_{i_{1}} \ \text{leži na} \ q .
Potpuno analogno vidi se da i P_{i_{2}} leži na q, pa je p=q (po (P1)). To povlači da Q_{j_{1}} leži na p, što je očita kontradikcija. Dakle, matrica A tipa (n+1,n^{2}), s elementima iz skupa \lbrace 1,2,\ldots,n\rbrace, ima svojstvo (\ast). Prema teoremu 5, postoji (n-1)-člani ortogonalan skup latinskih kvadrata reda n, a to je upravo potpuni skup ortogonalnih latinskih kvadrata reda n.

Obrnuto, ako postoji potpuni ortogonalni skup latinskih kvadrata reda n, tada po teoremu 5 postoji matrica A tipa (n+1,n^{2}), s elementima iz \lbrace 1,2,\ldots,n\rbrace, koja ima svojsto (\ast). Stupce matrice A proglasimo točkama Q_{1},Q_{2},\ldots,Q_{n^{2}} (zbog svojstva (\ast) svaka dva stupca su različita), te uvedimo i dodatne točke P_{1},P_{2},\ldots,P_{n+1}. Neka pravac p sadržava točke P_{1},P_{2},\ldots,P_{n+1} i samo te. Uzmimo da pravac p_{ij}, i=1,2,\ldots{},n, j=1,2,\ldots{},n+1 prolazi točkom P_{j}, te onima i samo onima Q_{k} (k=1,2,\ldots{},n^{2}) kojima se u j-tom retku nalazi broj i. Provjerimo da je konstrukcija dobra, tj. da smo zaista dobili projektivnu ravninu (potrebno je provjeriti aksiome (P1)(P4)):
(P1): Za kombinaciju točaka P_{i} i P_{j} (i,j=1,2,\ldots{},n+1, i \neq j) jasno vrijedi – pravac p je jedini koji ih spaja). Također je jasno i za kombinaciju Q_{i} i P_{j} (i=1,2,\ldots{},n^{2}, j=1,2,\ldots{},n+1) – jedino ih spaja pravac p_{kj}, gdje je k broj na mjestu (j,i) matrice A. Za kombinaciju Q_{i} i Q_{j} (i,j=1,2,\ldots{},n^{2}, i \neq j) dovoljno je pokazati da i-ti i j-ti stupac matrice A imaju u točno jednom retku isti broj (reći ćemo da se preklapaju točno jednom). Budući da se svaki broj, u svakom retku matrice A javlja točno n puta, broj svih preklapanja svih stupaca je \binom{n}{2} \cdot n \cdot (n+1). Očito se zbog svojstva (\ast) dva različita stupca mogu preklapati najviše jednom. Ako se neka dva stupca ne preklapaju, tada je
\binom{n^{2}}{2} \gt \binom{n}{2} \cdot n \cdot (n+1) \quad \Rightarrow \quad \frac{n^{2}(n^{2}-1)}{2}\gt \frac{n^{2}(n-1)(n+1)}{2},
što je nemoguće. Dakle, svaka dva stupca preklapaju se točno jednom. Neka se broj k nalazi u stupcima i i j matrice A, u istom retku r. Sada je jasno da je p_{kr} jedini pravac koji spaja točke Q_{i} i Q_{j}.
(P2): Za pravce p i p_{ij} (i=1,2,\ldots{},n, j=1,2,\ldots{},n+1) očito vrijedi, sijeku se samo u točki P_{j}. Također je jasno da je jedina zajednička točka pravaca p_{i_{1} j} i p_{i_{2} j} (i_{1},i_{2}=1,2,\ldots{},n, i_{1} \neq i_{2}, j=1,2,\ldots{},n+1) upravo P_{j}. Sad promotrimo pravce p_{i_{1} j_{1}} i p_{i_{2} j_{2}} (i_{1},i_{2}=1,2,\ldots{},n, j_{1},j_{2}=1,2,\ldots{},n+1, j_{1} \neq j_{2}). Redci j_{1} i j_{2} matrice A (svojstvo (\ast)) tvorit će sve uređene parove iz skupa \lbrace 1,2,\ldots,n\rbrace, pa među ostalim i par (i_{1},i_{2}), i to točno jednom. Zato promatrani pravci imaju jedinstveno sjecište.
(P3): Za točke P_{i} (i=1,2,\ldots{},n+1) očito vrijedi. Međutim, vrijedi i za Q_{j} (j=1,2,\ldots{},n^{2}), jer se u svakom stupcu matrice A nalazi n+1 brojeva.
(P4): Za pravac p očito vrijedi. Pravac p_{ij} (i=1,2,\ldots{},n, j=1,2,\ldots{},n+1) osim P_{j}, sadržava još točno n različitih točaka, jer se u j-tom retku matrice A broj i pojavljuje točno n puta.
Dakle, konstruirali smo projektivnu ravninu, koja je očigledno reda n. Time je teorem potpuno dokazan.
\ \blacksquare


Sada smo se domogli glavnog rezultata ovog odjeljka:

Korolar 11. [Veblen–Bussey] Za svaku prim-potenciju p^{n} postoji projektivna ravnina reda p^{n}.

Dokaz. Za p^{n}=2 imamo Fanovu ravninu. Za ostale prim-potencije egzistencija slijedi direktno iz teorema 4 i teorema 10.
\ \blacksquare


Prirodno se postavlja pitanje vrijedi li obrat korolara 11 (je li red svake konačne projektivne ravnine prim-potencija?). To pitanje i dalje nije riješeno, te je preraslo u tzv. hipotezu o prim-potencijama8, koja kaže da je red svake konačne projektivne ravnine prim-potencija. Rezultat koji bi bio najbliži spomenutoj hipotezi dali su još 1949. godine R. H. Bruck i H. J. Ryser, a mi ćemo ga dokazati. Međutim, bit će nam potrebni neki netrivijalni rezultati iz teorije brojeva.

3Rezultati iz teorije brojeva

Dokazi sljedećih dvaju teorema nisu trivijalni te nemaju direktne veze s našom temom. Stoga ćemo navesti samo iskaze teorema, uz naznaku gdje se ti dokazi mogu pronaći.

Teorem 12. Broj n \in \mathbb{N} može se zapisati u obliku n=k^{2}+m^{2} za neke k,m \in \mathbb{Z} ako i samo ako se u rastavu broja n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja s parnom potencijom.

Dokaz. Vidi [6], str. 43.
\ \blacksquare

Teorem 13. [Lagrange] Za svaki n \in \mathbb{N} postoje x,y,z,w \in \mathbb{Z} takvi da je
n = x^{2}+y^{2}+z^{2}+w^{2}.

Dokaz. Vidi [6], str. 44.–45.
\ \blacksquare

Lema 14. Neka je n \in \mathbb{N} takav da je n=p^{2}+q^{2} za neke p,q \in \mathbb{Q}. Tada postoje m,k \in \mathbb{Z} takvi da je n=m^{2}+k^{2}.

Dokaz. Neka je n=\big(\frac{p_{1}}{q_{1}}\big)^{2}+\big(\frac{p_{2}}{q_{2}}\big)^{2}, gdje su p_{1},p_{2} \in \mathbb{Z}, q_{1},q_{2} \in \mathbb{N}. Slijedi \displaystyle (q_{1}q_{2})^{2} n=p_{1}^{2}+p_{2}^{2}. Po teoremu 12 slijedi da se u prikazu broja (q_{1}q_{2})^{2} n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja s parnom potencijom. U prikazu broja (q_{1}q_{2})^{2} na proste faktore očito se svaki prosti faktor javlja s parnom potencijom. Dakle, u prikazu broja n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja se s parnom potencijom. Po teoremu 12 slijedi da je n=k^{2}+m^{2} za neke k,m \in \mathbb{Z}.
\ \blacksquare

Lema 15. Za brojeve a,b,c,d,x,y,w,z \in \mathbb{R} vrijedi identitet
\begin{align*} (a^{2}+b^{2}+c^{2}+d^{2}) & (x^{2}+y^{2}+z^{2}+w^{2})=\\ = & \ (ax-by-cz-dw)^{2}+(bx+ay-dz+cw)^{2}+\\ & +(cx+dy+az-bw)^{2}+(dx-cy+bz+aw)^{2}. \end{align*}

Dokaz. Trivijalan je posao izmnožiti obje strane i provjeriti jednakost.
\ \blacksquare


Za potrebe sljedećeg dokaza bit će nam zgodna i sljedeća definicija.

Definicija. Reći ćemo da uređena četvorka (x,y,z,w) \in \mathbb{Z}^{4} reprezentira broj t \in \mathbb{Z} ako je t=x^{2}+y^{2}+z^{2}+w^{2}.

4Bruck–Ryserov teorem

Teorem 16. [Bruck–Ryser] Neka je \Pi projektivna ravnina reda n te neka je n \equiv 1 \text{ ili } 2 \pmod{4}. Tada je n=k^{2}+m^{2} za neke k,m \in \mathbb{Z}.

Dokaz. Neka je \Pi projektivna ravnina reda n te neka je n \equiv 1 \text{ ili } 2 \pmod{4}. Po propoziciji 9, ravnina \Pi sadržava n^{2}+n+1=:v točku, i jednako toliko pravaca. Lako je vidjeti da je v+1 \equiv 0 \pmod{4}. Neka su P_{1},P_{2},\ldots,P_{v} točke, a l_{1},l_{2},\ldots,l_{v} pravci ravnine \Pi. Neka su x_{1},x_{2},\ldots,x_{v} varijable s vrijednostima u \mathbb{R}, te označimo
(5)
L_{i}:=\sum_{\lbrace j \ : \ P_{j} \text{ leži na } l_{i}\rbrace } x_{j}, \qquad i=1,2,\ldots,v.
Vrijede identiteti:
(6)
\sum_{i=1}^{v}L_{i}^{2} = 2 \sum_{i=1}^{v}\sum_{j=i+1}^{v}x_{i}x_{j} + (n+1) \sum_{i=1}^{v}x_{i}^{2},
(7)
\sum_{i=1}^{v}L_{i}^{2} = n \sum_{i=1}^{v}x_{i}^{2} + \Big(\sum_{i=1}^{v}x_{i}\Big)^{2}.
Identitet (6) dobijemo tako da nakon kvadriranja identiteta (5) i sumiranja po i=1,2,\ldots,v iskoristimo aksiome (P1) i (P3). Identitet (7) je malo zgodnije zapisan identitet (6). Uvedimo još jednu varijablu x_{v+1} s vrijednošću u \mathbb{R} te pribrojimo nx_{v+1}^{2} u (7). Dobijemo
(8)
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = n \sum_{i=1}^{v+1}x_{i}^{2} + T^{2},
gdje je T:=\sum_{i=1}^{v}x_{i}. Po teoremu 13 postoje nenegativni brojevi a,b,c,d \in \mathbb{Z} takvi da je n=a^{2}+b^{2}+c^{2}+d^{2}. Neka je matrica A_{n} \in M_{4}(\mathbb{R}) dana s
A_{n}:=\left(\begin{array}{rrrr} a & b & c & d \\ -b & a & d & -c \\ -c & -d & a & b \\ -d & c & -b & a \end{array}\right).
Nije teško vidjeti da je \det{}A_{n}=(a^{2}+b^{2}+c^{2}+d^{2})^{2}=n^{2} \neq 0, pa je A_{n} regularna matrica. Ako (x,y,z,w) reprezentira broj t, tada lema 15 povlači da (x,y,z,w)A_{n} reprezentira broj tn. Zato možemo pisati
(9)
n(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2},
gdje je
(10)
(y_{1},y_{2},y_{3},y_{4})=(x_{1},x_{2},x_{3},x_{4})A_{n}.
Sustav (10) možemo napisati u obliku
(x_{1},x_{2},x_{3},x_{4})=(y_{1},y_{2},y_{3},y_{4})A_{n}^{-1}.
Primijetimo da su elementi matrice A_{n}^{-1} iz \mathbb{Q}. Dakle, svaki x_{1},x_{2},x_{3},x_{4} je linearna kombinacija varijabli y_{1},y_{2},y_{3},y_{4} s racionalnim koeficijentima. Te linearne kombinacije zajedno s (9) uvrstimo u (8) te dobijemo
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2} + n \sum_{i=5}^{v+1}x_{i}^{2} + T^{2},
gdje su L_{1},L_{2},\ldots,L_{v},T linearne kombinacije (s racionalnim koeficijentima) varijabli y_{1},y_{2},y_{3},y_{4},x_{5},x_{6},\ldots,x_{v+1}. Isti postupak napravimo i za sljedeću uređenu četvorku (x_{5},x_{6},x_{7},x_{8}), i tako dalje, sve do (x_{v-2},x_{v-1},x_{v},x_{v+1}) jer je v+1 \equiv 0 \pmod{4}. Dobijemo identitet
(11)
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = \sum_{i=1}^{v+1}y_{i}^{2} + T^{2},
gdje su L_{1},L_{2},\ldots,L_{v},x_{v+1},T linearne kombinacije varijabli y_{1},y_{2},\ldots,y_{v+1}. Izraz (11) je valjan za svaku valuaciju varijabli y_{1},y_{2},\ldots,y_{v+1}. Želimo uzeti takav y_{1} da bude y_{1}^{2}=L_{1}^{2}. Kako bismo se uvjerili da je to moguće, promotrimo sljedeća dva slučaja:
\bullet Ako u linearnoj kombinaciji L_{1}, y_{1} dolazi s koeficijentom 1, tada jednadžbu y_{1}=-L_{1} očito možemo riješiti po y_{1}, tj. možemo za y_{1} uzeti neku linearnu kombinaciju varijabli y_{2},y_{3},\ldots,y_{v+1} takvu da je y_{1}^{2}=L_{1}^{2}.
\bullet Ako u linearnoj kombinaciji L_{1}, y_{1} dolazi s koeficijentom različitim od 1, tada možemo analogno izvesti isti zaključak kao u prošlom slučaju, proučavajući jednadžbu y_{1}=L_{1}.
Nakon te supstitucije, identitet (11) sada postaje
\sum_{i=2}^{v}L_{i}^{2} + nx_{v+1}^{2} = \sum_{i=2}^{v+1}y_{i}^{2} + T^{2},
gdje su L_{2},L_{3},\ldots,L_{v},x_{v+1},T linearne kombinacije varijabli y_{2},\ldots,y_{v+1}. Ponavljajući taj postupak (za y_{2},y_{3},\ldots,y_{n} redom), dobijemo identitet
(12)
nx_{v+1}^{2} = y_{v+1}^{2} + T^{2},
gdje su x_{v+1},T linearne kombinacije varijable y_{v+1}. Tada je x_{v+1}=\alpha{}y_{v+1}, T=\beta{}y_{v+1} za neke \alpha, \beta \in \mathbb{Q} (primijetimo da su koeficijenti svih linearnih kombinacija tijekom cijelog dokaza racionalni brojevi – ni jedan korak u dokazu nije za posljedicu imao gubitak racinalnosti koeficijenata). Izaberimo sada y_{v+1}:=1. Sada (12) povlači
n \alpha^{2}=1+\beta^{2} \quad \stackrel{\alpha \neq 0}{\Rightarrow} \quad n=\Big(\frac{1}{\alpha}\Big)^{2}+\Big(\frac{\beta}{\alpha}\Big)^{2}, \quad \frac{1}{\alpha}, \frac{\beta}{\alpha} \in \mathbb{Q}.
Lema 14 povlači da je n=m^{2}+k^{2} za neke m,k \in \mathbb{Z}.
\ \blacksquare

Korolar 17. [Bruck–Ryser, alternativna formulacija] Ako je n prirodan broj za koji vrijedi n \equiv 1 \text{ ili } 2 \pmod{4} i ako nekvadratni dio9 broja n u rastavu na proste faktore sadržava barem jedan prosti faktor p takav da je p \equiv 3 \pmod{4}, tada ne postoji projektivna ravnina reda n.

Dokaz. Pretpostavimo da postoji projektivna ravnina reda n te neka vrijedi n \equiv 1 \text{ ili } 2 \pmod{4}. Tada je po teoremu 16 n=m^{2}+k^{2} za neke m,k \in \mathbb{Z}. Teorem 12 povlači da se u rastavu broja n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja s parnom potencijom. Očito tada nekvadratni dio broja n ne sadržava ni jedan prosti faktor p za koji je p \equiv 3 \pmod{4}. Obratom po kontrapoziciji dobivamo tvrdnju korolara.
\ \blacksquare


Korolar 11 nam kaže da postoje projektivne ravnine redova 2, 3, 4, 5, 7, 8, 9, 11, \ldots{} Korolar 17 nam kaže da ne postoje projektivne ravnine redova 6, 14, 21, 22, \ldots{} Međutim, već za red 10, 12 ili 15 navedeni rezultati ne mogu nam dati odgovor. Može se lako pokazati da postoji beskonačno mnogo prirodnih brojeva za koje navedeni rezultati ne daju odgovor.

Krajem prošlog stoljeća uz pomoć računala je dokazano da ne postoji projektivna ravnina reda 10, dok je pitanje o postojanju projektivne ravnine reda 12 i dalje otvoren problem. Vidi [7].

5Poopćenje

U ovom odjeljku iskazat ćemo poopćenje teorema 16, koje su našli H. J. Ryser i S. Chowla 1950. godine. No prije toga potrebno je definirati nešto općenitiju strukturu od konačne projektivne ravnine. Promatrat ćemo konačne projektivne ravnine s aspekta teorije dizajna.

Definicija. Neka su v,k,\lambda \in \mathbb{N} takvi da je v \geq k \geq 2. Uređen par (X,\mathcal{A}), gdje je \mathcal{A} \subseteq \mathcal{P}(X), zovemo (v,k,\lambda)-balansiran nepotpun blok dizajn (kraće ćemo pisati (v,k,\lambda)-BIBD10), ako vrijedi:
(B1) \text{card}(X)=v;
(B2) Svaki blok (tj. element od \mathcal{A}) sadržava točno k elemenata;
(B3) Svaki neuređeni par različitih elemenata iz X nalazi se u točno \lambda blokova.
Nadalje, kažemo da je (v,k,\lambda)-BIBD simetričan ako je \lambda (v-1)=k^{2}-k.


Sada nije teško vidjeti da je projektivna ravnina reda n zapravo (n^{2}+n+1,n+1,1)-BIBD, uz identifikaciju: pravac \leftrightarrow blok (tj. pravac smatramo skupom točaka koje na njemu leže). Štoviše, projektivna ravnina reda n simetričan je (n^{2}+n+1,n+1,1)-BIBD. Sada smo u mogućnosti iskazati najavljeni teorem:

Teorem 18. [Bruck–Ryser–Chowla] Uzmimo da postoji simetričan (v,k,\lambda)-BIBD. Ako je v paran broj, tada je k- \lambda=w^{2} za neki w \in \mathbb{Z}. Ako je v neparan broj, tada postoje x,y,z \in \mathbb{Z} koji nisu svi nula, tako da vrijedi:
(13)
x^{2}=(k- \lambda)y^{2}+(-1)^{\frac{v-1}{2}} \lambda z^{2}.

Dokaz. Vidi [2], str. 30.–35.
\ \blacksquare


Zašto je teorem 18 općenitiji slučaj teorema 16? Pretpostavimo da postoji projektivna ravnina reda n, tj. da postoji simetričan (n^{2}+n+1,n+1,1)-BIBD, te primijetimo da je n^{2}+n+1 uvijek neparan broj.

Pretpostavimo prvo da je n \equiv 0 \text{ ili } 3 \pmod{4}. Tada se jednakost (13) reducira na jednadžbu x^{2}=ny^{2}+z^{2}, koja uvijek ima netrivijalno rješenje x=z=1, y=0. Dakle, u slučaju n \equiv 0 \text{ ili } 3 \pmod{4} teorem Bruck–Ryser–Chowla ne daje odgovor o (ne)postojanju projektivne ravnine reda n.

Pretpostavimo sada da je n \equiv 1 \text{ ili } 2 \pmod{4}. Tada se jednakost (13) reducira na x^{2}+z^{2}=ny^{2}, pa je (po lemi 14) n=m^{2}+k^{2} za neke m,k \in \mathbb{Z}, što je upravo tvrdnja teorema 16.
Bibliografija
[1] T. W. Hungerford, Algebra, Springer, 2003
[2] D. R. Stinson, Combinatorial desings, construction and analysis, Springer, 2004
[3] S. Radas, Ortogonalni latinski kvadrati, magistarski rad, PMF–Matematički odjel, Sveučilište u Zagrebu, 1988
[4] D. R. Huges, F. C. Piper, Projective planes, Springer, 1973
[5] D. Palman, Projektivna geometrija, Školska knjiga, 1984
[6] A. Dujella, Uvod u teoriju brojeva, skripta, PMF–Matematički odjel, Sveučilište u Zagrebu, http://web.math.hr/~duje/utb/utblink.pdf
[7] C. W. H. Lam, The Search for a Finite Projective Plane of Order 10, The American Mathematical Monthly Volume 98, Issue 4 (str. 305–318), 1991