Kwadraty grecko-łacińskie i płaszczyzny rzutowe

Drogi Czytelniku, spróbuj wskazać jakieś nieprzeciętne cechy poniższych dwóch układów liczb, wpisanych w tablice o wymiarach $5\times 5.$ $$\begin{array}{|ccccc|}\hline 1& 2& 3& 4& 5\\ 2& 3& 4& 5& 1\\ 3& 4& 5& 1& 2\\ 4& 5& 1& 2& 3\\ 5& 1& 2& 3& 4\\ \hline\end{array}\begin{array}{|ccccc|}\hline 1& 4& 2& 5& 3\\ 2& 5& 3& 1& 4\\ 3& 1& 4& 2& 5\\ 4& 2& 5& 3& 1\\ 5& 3& 1& 4& 2\\ \hline\end{array}$$ W obu przypadkach umieszczono liczby od 1 do 5, każda pojawia się pięciokrotnie – ciężko to jednak uznać za ,,nieprzeciętne cechy”. Istotniejsze jest to, że w każdym wierszu i każdej kolumnie pojawia się pełen zestaw liczb od 1 do 5. Dzięki temu oba układy zasługują na miano kwadratów łacińskich. Najistotniejszym zaś jest dla nas to, co ukazuje się naszym oczom po sparowaniu liczb stojących w odpowiednich polach tych tablic. $$\begin{array}{|ccccc|}\hline (1,1)& (2,4)& (3,2)& (4,5)& (5,3)\\ (2,2)& (3,5)& (4,3)& (5,1)& (1,4)\\ (3,3)& (4,1)& (5,4)& (1,2)& (2,5)\\ (4,4)& (5,2)& (1,5)& (2,3)& (3,1)\\ (5,5)& (1,3)& (2,1)& (3,4)& (4,2)\\ \hline\end{array}$$ Okazuje się, że otrzymany kwadrat ma niezwykłą cechę – w każdym polu znajduje się unikalna para $(x,y),$ gdzie $x$ oraz $y$ są liczbami z zakresu od $1$ do $5.$ W takiej sytuacji mówimy, że dwa kwadraty łacińskie są wzajemnie ortogonalne (krótko: ortogonalne), a połączony z nich kwadrat nazywamy kwadratem grecko-łacińskim.

Historia badania kwadratów grecko-łacińskich sięga Leonharda Eulera. Jeśli wierzyć przekazom, w drugiej połowie XVIII wieku caryca Katarzyna Wielka przesłała uczonemu następujący problem, zwany współcześnie problemem $36$ oficerów:

Ustawić $36$ oficerów z $6$ różnych pułków tak, aby stali w kwadracie, i tak, aby w każdej linii (zarówno poziomej, jak i pionowej) było $6$ oficerów różnych stopni i różnych pułków.

Innymi słowy, caryca poprosiła Eulera o skonstruowanie kwadratu grecko-łacińskiego o wymiarach $6\times 6.$ Uczony nie potrafił rozwiązać tego problemu, ale udało mu się odkryć ogólną metodę konstrukcji kwadratów grecko-łacińskich rzędu $n,$ gdy $n$ jest nieparzyste lub jest podzielne przez $4.$ W swoich rozumowaniach do oznaczania elementów z pierwszego kwadratu Euler używał liter alfabetu łacińskiego, a do drugiego – greckiego, i podobno stąd wzięła się nazwa kwadrat grecko-łaciński.

Euler postawił również hipotezę, że jeśli $n=4k+2,$ to kwadrat takiego rzędu nie istnieje, co łatwo uzasadnić dla $k=0.$ Przypadek $k=2,$ czyli problem 36 oficerów, czekał na rozwiązanie aż do początku XX wieku, kiedy to Gaston Tarry udowodnił, że faktycznie problem ten nie ma rozwiązania [1]. W pełnej ogólności hipoteza Eulera czekała jeszcze pół wieku, zanim została całkowicie rozstrzygnięta. W $1959$ roku trójka matematyków – Raj Bose, Ernest Parker i Sharadchandra Shrikhande – wykazała, że hipoteza Eulera jest fałszywa dla wszystkich $k\ge 3$ [2].

Współcześnie wiemy już zatem, że dla $n\notin \{1,2,6\}$ istnieją dwa wzajemnie ortogonalne kwadraty łacińskie rzędu $n.$ A czy może ich być więcej? Jak najbardziej – spójrzmy od razu na przykład $4$ wzajemnie ortogonalnych kwadratów łacińskich piątego rzędu. $$\begin{array}{|ccccc|}\hline (1,1,1,1)& (2,2,2,2)& (3,3,3,3)& (4,4,4,4)& (5,5,5,5)\\ (2,3,5,4)& (3,4,1,5)& (4,5,2,1)& (5,1,3,2)& (1,2,4,3)\\ (3,5,4,2)& (4,1,5,3)& (5,2,1,4)& (1,3,2,5)& (2,4,3,1)\\ (4,2,3,5)& (5,3,4,1)& (1,4,5,2)& (2,5,1,3)& (3,1,2,4)\\ (5,4,2,3)& (1,5,3,4)& (2,1,4,5)& (3,2,5,1)& (4,3,1,2)\\ \hline\end{array}$$ W podanej tabeli dowolnie wybrane dwie spośród $4$ współrzędnych (wybieramy takie same współrzędne z każdej czwórki liczb) tworzą nowy kwadrat, który jest klasycznym kwadratem grecko-łacińskim. Okazuje się, że piątego kwadratu łacińskiego już nie znajdziemy, gdyż zachodzi następujące

Twierdzenie. Istnieje co najwyżej $n-1$ wzajemnie ortogonalnych kwadratów łacińskich rzędu $n.$

Dowód. Zauważmy najpierw, że wzajemna ortogonalność jest zachowana przez permutacje (tzn. przenumerowania) liczb w dowolnym kwadracie. Korzystając z tego spostrzeżenia, możemy bez straty ogólności założyć, że w każdym kwadracie pierwszy wiersz jest postaci $1,\dots ,n.$ Zauważmy, że w każdym z kwadratów na drugim miejscu pierwszej kolumny znajduje się liczba większa od 1 (gdyż są to kwadraty łacińskie). Ponadto muszą to być różne liczby, inaczej zaprzeczylibyśmy wzajemnej ortogonalności. Istotnie, gdyby w pewnych dwóch kwadratach w tym miejscu znajdowała się ta sama liczba $a,$ to w połączeniu tych kwadratów dostalibyśmy w tym miejscu parę $(a,a),$ która pojawiła się już w pierwszym wierszu. Te dwie obserwacje dowodzą, że wzajemnie ortogonalnych kwadratów może być co najwyżej $n-1.$◻

Niech teraz $n$ będzie liczbą pierwszą.

Skonstruujemy $n-1$ wzajemnie ortogonalnych kwadratów łacińskich rzędu $n$: niech element stojący w $i$-tym wierszu $j$-tej kolumny $r$-tego kwadratu (oznaczanego jako $L_r$) będzie równy $L_r(i,j)=(i+rj)\mathrm{mod}n,$ przy czym $i,j,r\in {\mathbb{Z}}_n$ oraz $r\ne 0.$ Dla przykładu, jeśli przyjmiemy $n=5,$ otrzymamy poniższe kwadraty łacińskie. $$\begin{array}{|ccccc|}\hline 0& 1& 2& 3& 4\\ 1& 2& 3& 4& 0\\ 2& 3& 4& 0& 1\\ 3& 4& 0& 1& 2\\ 4& 0& 1& 2& 3\\ \hline\end{array}\begin{array}{|ccccc|}\hline 0& 2& 4& 1& 3\\ 1& 3& 0& 2& 4\\ 2& 4& 1& 3& 0\\ 3& 0& 2& 4& 1\\ 4& 1& 3& 0& 2\\ \hline\end{array}\begin{array}{|ccccc|}\hline 0& 3& 1& 4& 2\\ 1& 4& 2& 0& 3\\ 2& 0& 3& 1& 4\\ 3& 1& 4& 2& 0\\ 4& 2& 0& 3& 1\\ \hline\end{array}\begin{array}{|ccccc|}\hline 0& 4& 3& 2& 1\\ 1& 0& 4& 3& 2\\ 2& 1& 0& 4& 3\\ 3& 2& 1& 0& 4\\ 4& 3& 2& 1& 0\\ \hline\end{array}$$ Okazuje się, że tak skonstruowane kwadraty są wzajemnie ortogonalne! Załóżmy bowiem, że kwadraty $L_{r_1}$ oraz $L_{r_2}$ ($r_1\ne r_2$) nie są ortogonalne, tzn. po połączeniu na pewnych dwóch różnych miejscach: $(i_1,j_1)$ oraz $(i_2,j_2),$ mają tę samą wartość. Oznacza to, że $$\begin{array}{rl}{i}_1+r_1{j}_1& \equiv i_2+r_1{j}_2(\mathrm{mod}n),\\ i_1+r_2{j}_1& \equiv i_2+r_2{j}_2(\mathrm{mod}n).\end{array}$$ Po odjęciu tych kongruencji stronami uzyskamy $(r_1-r_2)j_1\equiv (r_1-r_2)j_2,$ a zatem $n\mid (r_1-r_2)(j_1-j_2).$ Skoro $r_1\ne r_2$ oraz $n$ jest liczbą pierwszą, dostajemy $n\mid (j_1-j_2),$ czyli $j_1\equiv j_2(\mathrm{mod}n),$ a stąd i z pierwszej równości wyżej dostajemy $i_1\equiv i_2(\mathrm{mod}n),$ co przeczy założeniu, że $(i_1,j_1)$ oraz $(i_2,j_2)$ były różnymi miejscami.

Spróbujmy wyabstrahować te własności zbioru reszt z dzielenia przez $n,$ które pozwoliły nam przeprowadzić powyższą konstrukcję. Na tych resztach wykonywaliśmy działania dodawania, odejmowania i mnożenia. Ponadto – w sposób niejawny – dokonywaliśmy dzielenia, kiedy z równości $(r_1-r_2)j_1\equiv (r_1-r_2)j_2$ wnioskowaliśmy $j_1\equiv j_2,$ i tu istotne było założenie o pierwszości $n.$ Strukturę, w której te operacje zachowują się tak, jak jesteśmy do tego przyzwyczajeni, nazywamy ciałem. W 1893 roku Eliakim Moore udowodnił, że na skończonym zbiorze można wprowadzić strukturę ciała wtedy i tylko wtedy, gdy liczba jego elementów jest potęgą liczby pierwszej – i w takim wypadku wiadomo, jak taką strukturę wprowadzić. Oznacza to, że dla $n$ będących potęgą liczby pierwszej potrafimy w analogiczny do powyższego sposób skonstruować $n-1$ wzajemnie ortogonalnych kwadratów rzędu $n$ oraz, że dla $n$ niebędących potęgą liczby pierwszej ta konstrukcja nie działa. Nie oznacza to oczywiście, że nie ma innego sposobu…ale takiego matematycy nie znają. A bardzo chcieliby poznać (lub udowodnić, że go nie ma), gdyż pozornie niewinne ,,pełne” układy wzajemnie ortogonalnych kwadratów łacińskich to tak naprawdę inne oblicze obiektu bardzo w matematyce zakorzenionego – skończonej płaszczyzny rzutowej. Wyjaśnieniu tego związku poświęcona będzie dalsza część artykułu.

Skończona płaszczyzna rzutowa to zbiór $X$ wraz z niepustym zbiorem $L$ złożonym z podzbiorów $X$ (elementy $L$ nazywamy prostymi, a elementy $X$ punktami) o następujących własnościach, naśladujących zależności między ,,klasycznymi” prostymi i punktami na płaszczyźnie:

• dla każdej pary różnych punktów istnieje dokładnie jedna prosta zawierająca oba punkty,

• przecięcie (tzn. część wspólna) dwóch różnych prostych zawiera dokładnie jeden punkt,

• istnieje taki zbiór $4$ punktów, że żadne $3$ spośród nich nie należą do jednej prostej.

Mówimy ponadto, że płaszczyzna rzutowa jest rzędu $n,$ jeśli do każdej prostej należy dokładnie $n+1$ punktów. Można uzasadnić, że wtedy istnieje dokładnie $n^2+n+1$ punktów oraz tyle samo prostych.

Najprostszym przykładem realizującym powyższe aksjomaty jest tak zwana płaszczyzna Fano – jest to układ $7$ punktów oraz $7$ prostych, tworzących płaszczyznę rzędu $2.$ Wizualizacja płaszczyzny Fano została umieszczona na marginesie. Podkreślmy, że w takiej wizualizacji proste (elementy zbioru $L$) nie muszą być proste (w sensie geometrii euklidesowej) – w tym przypadku prosta będąca zbiorem środków boków narysowanego trójkąta równobocznego jest oznaczona jako okrąg (pozostałe sześć prostych to odcinki).

Pokażemy teraz, jak z płaszczyzny rzutowej rzędu $n$ uzyskać $n-1$ wzajemnie ortogonalnych kwadratów łacińskich rzędu $n.$ Zrobimy to na przykładzie $n=3,$ ogólna sytuacja nie różni się istotnie.

Rozpocznijmy od (wcale nietrywialnego) narysowania tej płaszczyzny rzutowej. Na marginesie przedstawionych zostało $13$ punktów w takim układzie, w którym do jednej prostej należą dokładnie $4$ punkty i odwrotnie – każdy punkt należy dokładnie do $4$ prostych. Symbolami  zaznaczone zostały $4$ punkty, z których żadne $3$ nie leżą na jednej prostej. Taki układ punktów i prostych przeniesiemy teraz na konstrukcję kwadratów łacińskich.

Ustalmy dowolnie dwa punkty $X$ i $Y$ (oznaczenia jak na rysunku). Niech $\ell$ będzie prostą, do której należą punkty $X$ i $Y$ (jest to prosta oznaczona przez podwójną linię ). Oznaczmy pozostałe punkty tej prostej przez $Q_k$ ($k\le 2$). Następnie liczbami od 1 do 3 numerujemy wszystkie proste zawierające $X$ i różne od $\ell$; podobnie postępujemy dla punktu $Y.$ Każdy punkt nieleżący na prostej $\ell$ jest wspólny dla dokładnie jednej pary ponumerowanych przed chwilą prostych. Niech $P_{ij}$ będzie punktem wspólnym dla $i$-tej prostej zawierającej punkt $X$ i $j$-tej prostej zawierającej punkt $Y.$

Dla każdego punktu $Q_k$ ($k\le 2$) etykietujemy proste różne od $\ell ,$ zawierające te punkty etykietami $A,$ $B$ i $C.$ Wówczas każdy punkt $P_{ij}$ leży na prostych o różnych etykietach. Konstruujemy teraz dwa kwadraty łacińskie w następujący sposób:

W $i$-tym wierszu i $j$-tej kolumnie $k$-tego kwadratu łacińskiego umieszczamy etykietę prostej łączącej $P_{ij}$ z $Q_k.$

Zgodnie z tym algorytmem otrzymujemy poniższe kwadraty łacińskie i odpowiadający im kwadrat grecko-łaciński. $$\begin{array}{|ccc|}\hline B& C& A\\ A& B& C\\ C& A& B\\ \hline\end{array}\begin{array}{|ccc|}\hline C& A& B\\ A& B& C\\ B& C& A\\ \hline\end{array}\begin{array}{|ccc|}\hline (B,C)& (C,A)& (A,B)\\ (A,A)& (B,B)& (C,C)\\ (C,B)& (A,C)& (B,A)\\ \hline\end{array}$$ Dlaczego w ogólności otrzymane kwadraty są łacińskie? Przypuśćmy, że $k$-ty kwadrat taki nie jest i dla ustalenia uwagi przyjmijmy, że w $i$-tym wierszu powtarza się w nim pewna litera. Oznaczałoby to, że prosta z $Q_k$ oznaczona tą literą ma dwa punkty wspólne z $i$-tą prostą z $X.$ Te proste musiałyby być zatem równe, a to jest sprzeczność.

Gdyby zaś kwadraty o numerach $k$ i $k^{\prime }$ nie tworzyły kwadratu grecko-łacińskiego, to pewne dwie proste z punktów $Q_k$ i $Q_{k^{\prime }}$ musiałyby przecinać się w dwóch różnych punktach $P_{ij},$ i to też jest sprzeczność.

Co jest również ważne, algorytm można odwrócić i zamienić $n-1$ wzajemnie ortogonalnych kwadratów łacińskich rzędu $n$ na skończoną płaszczyznę rzutową rzędu $n.$ Prawdziwe jest zatem następujące

Twierdzenie: Istnieje $n-1$ wzajemnie ortogonalnych kwadratów łacińskich rzędu $n$ wtedy i tylko wtedy, gdy istnieje skończona płaszczyzna rzutowa rzędu $n.$

Zgodnie z obserwacjami z pierwszej części artykułu oznacza to, że istnieją płaszczyzny rzutowe rzędu $p^k,$ gdzie $p$ jest liczbą pierwszą. Obecnie nie znamy przypadku płaszczyzny rzutowej wymiaru innego niż $p^k,$ przypuszcza się więc, że to stwierdzenie charakteryzuje wszystkie $n,$ dla których odpowiednią płaszczyznę można skonstruować.

Hipoteza: Skończona płaszczyzna rzutowa rzędu $n$ istnieje tylko wtedy, gdy $n$ jest potęgą liczby pierwszej.

Istnieją oczywiście pewne wyniki częściowe. Jednym z nich jest następujący fakt, pochodzący z $1949$ roku.

Twierdzenie (Bruck–Ryser): Jeżeli istnieje płaszczyzna rzutowa rzędu $n$ oraz $n\equiv 1(\mathrm{mod}4)$ lub $n\equiv 2(\mathrm{mod}4),$ to $n$ musi być sumą kwadratów dwóch liczb całkowitych.

Ostatnie twierdzenie wyklucza w szczególności istnienie płaszczyzn rzutowych wymiaru $6$ lub $14,$ ale nie wyklucza istnienia płaszczyzny rzędu $10.$ To ostatnie zostało wykazane metodami komputerowymi w $1991$ roku. Obecnie najmniejsze $n,$ dla którego nie wiemy, czy istnieje odpowiednia płaszczyzna rzutowa, to $n=12.$ Warto przy tej okazji przytoczyć pracę [3], której autorzy – polscy matematycy – przedstawiają elementarny i czysto geometryczny dowód nieistnienia płaszczyzny rzutowej rzędu $6.$

Na koniec wspomnijmy o jeszcze jednym zagadnieniu. Wiemy już, że płaszczyzny rzutowe rzędu $6$ oraz $10$ nie istnieją, wobec tego nie istnieje odpowiednio $5$ i $9$ wzajemnie ortogonalnych kwadratów łacińskich. Można więc postawić pytanie – jeśli nie tyle, to ile maksymalnie można ich znaleźć? W przypadku $n=6$ odpowiedzi dostarcza nam problem $36$ oficerów. Natomiast dla $n=10$ odpowiedź nie jest obecnie znana – wiadomo, że istnieją dwa ortogonalne kwadraty łacińskie rzędu 10 i przypuszcza się, że nie więcej. Wreszcie, dla $n\ge 12$ istnieje co najmniej pięć wzajemnie ortogonalnych kwadratów łacińskich rzędu $n.$

Literatura

[1] G. Tarry, Le Probléme de 36 Officiers, Compte Rendu de l’Association Française pour l’Avancement des Sciences (1901), 170–203.

[2] R.C. Bose, S.S. Shrikhande, E.T. Parker, Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture, Canad. J. Math. 12 (1960), 189–203.

[3] M. Dumnicki, J. Gwoździewicz, J. Szpond, An elementary, geometric proof of the nonexistance of a projective plane of order 6, Contrib. Discrete Math. 15 (2020), 1–9.