P	U	S	Č	P	S	N
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

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.

Sadržaj

1 Ortogonalni latinski kvadrati

2 Konačne projektivne ravnine

Slika 1: Fanova ravnina – projektivna ravnina reda

$2$ .

3 Rezultati iz teorije brojeva

4 Bruck–Ryserov teorem

5 Poopćenje

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

$\leftrightarrow$ pravac 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

$1$ –

$1$ 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 (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