Małe kwadraty łacińskie i quasigrupy

Kwadraty łacińskie i quasigrupy są równoważnymi obiektami matematycznymi, chociaż pierwszy ma charakter kombinatoryczny , podczas gdy drugi jest bardziej algebraiczny . Poniższe zestawienie uwzględni przykłady niektórych bardzo małych rzędów , którymi jest długość boku kwadratu lub liczba elementów w równoważnej quasigrupie.

Równoważność

Biorąc pod uwagę quasigrupę $Q$ z $n$ elementami, jej tablica Cayleya (prawie powszechnie nazywana tabliczką mnożenia ) jest tablicą $(n + 1) \times (n + 1)$ zawierającą granice; górny rząd nagłówków kolumn i lewa kolumna nagłówków wierszy. Usunięcie granic pozostawia $n \times n$ tablica, która jest kwadratem łacińskim. Proces ten można odwrócić, zaczynając od kwadratu łacińskiego, wprowadzając graniczący wiersz i kolumnę, aby uzyskać tabliczkę mnożenia quasigrupy. Chociaż istnieje całkowita dowolność w sposobie wyznaczania granic, quasigrupy uzyskane w wyniku różnych wyborów są czasami równoważne w znaczeniu podanym poniżej.

Izotopia i izomorfizm

Dwa kwadraty łacińskie $L$ ₁ i $L$ ₂ o rozmiarze $n$ są izotopowe , jeśli istnieją trzy bijekcje z wierszy, kolumn i symboli $L$ _{1 odpowiednio} na wiersze, kolumny i symbole $L$ ₂ , które odwzorowują $L$ ₁ na $L$ ₂ . Izotopia jest relacją równoważności , a klasy równoważności nazywane są klasami izotopów .

Istnieje silniejsza forma równoważności. Dwa kwadraty łacińskie $L$ ₁ i $L$ ₂ o boku $n$ ze wspólnym zestawem symboli $S$ , który jest również zestawem indeksów dla wierszy i kolumn każdego kwadratu, są izomorficzne, jeśli istnieje bijekcja $g: S \to S$ taka, że $g (L 1 (ja, j)) = L 2 (sol (ja), sol (j))$ dla wszystkich $ja$ , $j$ w $S.$ _ Alternatywnym sposobem zdefiniowania izomorficznych kwadratów łacińskich jest stwierdzenie, że para izotopowych kwadratów łacińskich jest izomorficzna, jeśli trzy bijekcje użyte do wykazania, że są one izotopowe, są w rzeczywistości równe. Izomorfizm jest również relacją równoważności, a jej klasy równoważności nazywane są klasami izomorfizmu .

Alternatywną reprezentacją kwadratu łacińskiego jest tablica ortogonalna . Dla kwadratu łacińskiego rzędu $n$ jest to macierz $n$ ² × 3 z kolumnami oznaczonymi $r$ , $c$ i $s$ , której wiersze odpowiadają pojedynczej pozycji kwadratu łacińskiego, a mianowicie wierszowi pozycji, kolumnie pozycji i symbol w pozycji. Tak więc dla rzędu trzech kwadratów łacińskich,

1	2	3
2	3	1
3	1	2

tablica ortogonalna jest dana wzorem:

$R$	$C$	$S$
1	1	1
1	2	2
1	3	3
2	1	2
2	2	3
2	3	1
3	1	3
3	2	1
3	3	2

Warunkiem, aby macierz o odpowiedniej wielkości reprezentowała kwadrat łaciński, jest to, że dla dowolnych dwóch kolumn $n 2$ uporządkowanych par określonych przez wiersze w tych kolumnach to wszystkie pary ( $i, j$ ) z 1 ≤ $i, j \leq n$ , raz każda .

Ta właściwość nie jest tracona przez permutację trzech kolumn (ale nie etykiet), więc uzyskuje się inną tablicę ortogonalną (a tym samym kolejny kwadrat łaciński). Na przykład permutacja pierwszych dwóch kolumn, która odpowiada transpozycji kwadratu (z uwzględnieniem jego głównej przekątnej), daje inny kwadrat łaciński, który może, ale nie musi, być izotopowy w stosunku do oryginału. W tym przypadku, jeśli quasigrupa odpowiadająca temu kwadratowi łacińskiemu spełnia prawo przemienności , nowy kwadrat łaciński jest taki sam jak pierwotny. W sumie istnieje sześć możliwości, w tym „nic nie robić”, co daje co najwyżej sześć łacińskich kwadratów zwanych koniugatami (również parastrofy ) pierwotnego placu.

Mówi się, że dwa kwadraty łacińskie są paratopowe , również izotopowe klasy głównej , jeśli jeden z nich jest izotopowy z koniugatem drugiego. Jest to również relacja równoważności, z klasami równoważności zwanymi klasami głównymi , gatunkami lub klasami paratopii . Każda klasa główna zawiera do sześciu klas izotopów.

Klasa główna to rozłączna suma klas izotopów, a klasa izotopów to rozłączna suma klas izomorfizmu.

Kwazigrupy izotopowe

Niech $(Q,\circ)$ i $(R,*)$ będą dwiema quasigrupami. Uporządkowaną trójkę $(f, g, h)$ bijekcji z $na$ R $nazywamy$ izotopizmem ( $Q, \circ)$ na $(R,*)$ jeśli x $f (x) * g (y) = h (Q \circ y)$ dla wszystkich $x, y$ w $G$ . O takich quasigrupach mówi się, że są izotopowe .

Jeśli w powyższej definicji $f = g = h$ to mówimy, że quasi-grupy są izomorficzne .

Inaczej niż w przypadku kwadratów łacińskich, gdy dwie quasigrupy izotopowe są reprezentowane przez tablice Cayleya (obramowane kwadraty łacińskie), permutacje $f$ i $g$ działają tylko na nagłówkach granicznych i nie przesuwają kolumn ani wierszy, podczas gdy $h$ działa na korpusie tabeli .

Permutacja wierszy i kolumn tabeli Cayleya (w tym nagłówków) nie zmienia quasigrupy, którą definiuje, jednak kwadrat łaciński powiązany z tą tabelą zostanie permutowany na izotopowy kwadrat łaciński. Zatem normalizacja tabeli Cayleya (umieszczenie nagłówków granicznych w jakimś ustalonym z góry określonym porządku poprzez permutację wierszy i kolumn, w tym nagłówków) zachowuje klasę izotopową powiązanego kwadratu łacińskiego. Ponadto, jeśli dwie znormalizowane tablice Cayleya reprezentują izomorficzne quasigrupy, to powiązane z nimi kwadraty łacińskie są również izomorficzne. Stąd liczba odrębnych quasigrup danego rzędu jest liczbą klas izomorfizmu kwadratów łacińskich tego rzędu.

Notacja

Zestaw symboli użytych w kwadracie łacińskim (lub quasigrupie) jest dowolny, a poszczególne symbole nie mają żadnego znaczenia, nawet jeśli mogą mieć znaczenie w innych kontekstach. Tak więc, ponieważ najczęściej używa się zestawów symboli ${1,2, ... , n$ } lub ${0,1, ... , n - 1$ }, należy pamiętać, że te symbole nie mają znaczenia liczbowego. Aby podkreślić ten punkt, małe kwadraty łacińskie czasami używają liter alfabetu jako zestawu symboli.

Liczenie kwadratów łacińskich

Ponieważ kwadrat łaciński jest obiektem kombinatorycznym, zestaw symboli użyty do zapisania kwadratu jest nieistotny. Zatem jako kwadraty łacińskie należy je traktować tak samo:

{\ Displaystyle {\ rozpocząć {macierz} a & b \\ b & a \ koniec {macierz}}}

i

{\ Displaystyle {\ początek {macierz} 1 i 2 \\ 2 i 1 \ koniec {macierz}}.}

Podobnie i z tego samego powodu

{\ Displaystyle {\ rozpocząć {macierz} b & a \\ a & b \ koniec {macierz}}}

i

{\ Displaystyle {\ rozpocząć {macierz} 1 i 2 \\ 2 i 1 \ koniec {macierzy}}}

należy uważać za to samo. Zatem,

{\ Displaystyle {\ rozpocząć {macierz} a & b \\ b & a \ koniec {macierz}}}

\ rozpocząć {macierz} b & a \\ a & b \ koniec {macierz}}}

{

nie mogą być traktowane jako różne kwadraty łacińskie.

Ten intuicyjny argument można uściślić. Kwadraty łacińskie

}}

{\ Displaystyle {\ rozpocząć {macierz} b & a \\ a&b \ koniec {macierz}}, }

i

są izotopowe na kilka sposobów. Niech ( $a, b$ ) będzie permutacją inwolucyjną na zbiorze $S = {a, b$ }, wysyłającą $a$ do $b$ i $b$ do $a$ . Wtedy izotop ${(a, b), id, id$ } zamieni dwa wiersze pierwszego kwadratu, dając drugi kwadrat ( $id$ jest permutacją tożsamości). Ale, ${id, (a, b), id$ }, który zamienia dwie kolumny, jest również izotopem, podobnie jak ${id, id, (a, b)$ }, który zamienia dwa symbole. Jednak ${(a, b), (a, b), (a, b)$ } jest również izotopem między dwoma kwadratami, więc ta para kwadratów jest izomorficzna.

Zredukowane kwadraty

Znalezienie klasy izomorfizmu danego kwadratu łacińskiego może być trudnym problemem obliczeniowym dla kwadratów dużego rzędu. Aby nieco zmniejszyć problem, kwadrat łaciński można zawsze umieścić w standardowej formie znanej jako kwadrat zredukowany . Skrócony kwadrat ma elementy w górnym rzędzie zapisane w jakimś naturalnym porządku zestawu symboli (na przykład liczby całkowite w porządku rosnącym lub litery w porządku alfabetycznym). Wpisy w lewej kolumnie są umieszczane w tej samej kolejności. Ponieważ można to zrobić za pomocą permutacji wierszy i kolumn, każdy kwadrat łaciński jest izotopowy z kwadratem zredukowanym. Zatem każda klasa izotopów musi zawierać zredukowany kwadrat łaciński, jednak kwadrat łaciński może mieć więcej niż jeden zredukowany kwadrat, który jest z nim izotopowy. W rzeczywistości w danej klasie izomorfizmu może istnieć więcej niż jeden zredukowany kwadrat.

Na przykład zredukowane kwadraty łacińskie rzędu czwartego,

{\ Displaystyle {\ rozpocząć {macierz} 1 i 2 i 3 i 4 \\ 2 i 4 i 1 i 3 \\ 3 i 1 i 4 i 2 \\ 4 i 3 i 2 i 1 \ koniec {macierz}}}

i

{\ Displaystyle {\ początek {macierz} 1 i 2 i 3 i 4 \\ 2 i 1 i 4 i 3 \\ 3 i 4 i 2 i 1 \\ 4 i 3 i 1 i 2 \ koniec {macierz}}}

oba należą do klasy izomorfizmu, która zawiera również zredukowany kwadrat

{\ Displaystyle {\ rozpocząć {macierz} 1 i 2 i 3 i 4 \\ 2 i 3 i 4 i 1 \\ 3 i 4 i 1 i 2 \\ 4 i 1 i 2 i 3 \ koniec {macierz}}.}

Można to pokazać odpowiednio za pomocą izomorfizmów {(3,4), (3,4), (3,4)} i {(2,3), (2,3), (2,3)}.

Ponieważ klasy izotopów są rozłączne, liczba zredukowanych kwadratów łacińskich daje górną granicę liczby klas izotopów. Ponadto całkowita liczba kwadratów łacińskich wynosi $n!(n - 1)!$ razy liczba zredukowanych kwadratów.

Normalizuj tablicę Cayleya quasigrupy w taki sam sposób, jak zredukowany kwadrat łaciński. Wtedy quasigrupa powiązana ze zredukowanym kwadratem łacińskim ma (dwustronny) element tożsamości (mianowicie pierwszy element wśród nagłówków wierszy). Quasigrupa o dwustronnej tożsamości nazywana jest pętlą . Niektóre, ale nie wszystkie, pętle są grupami. Aby być grupą, musi obowiązywać również prawo asocjacyjne.

Niezmienniki izotopowe

Liczba różnych podstruktur w kwadracie łacińskim może być przydatna w odróżnianiu ich od siebie. Niektóre z tych zliczeń są takie same dla każdego izotopu kwadratu łacińskiego i są określane jako niezmienniki izotopów. Jednym z takich niezmienników jest liczba podkwadratów 2 × 2, zwanych interkalacjami . Innym jest całkowita liczba przekrojów , zbiór $n$ pozycji w łacińskim kwadracie rzędu $n$ , po jednym w każdym wierszu i po jednym w każdej kolumnie, które nie zawierają dwukrotnie żadnego elementu. Kwadraty łacińskie o różnych wartościach dla tych zliczeń muszą należeć do różnych klas izotopów. Liczba interkalatów jest również niezmiennikiem klasy głównej.

Zamówienie 1

Dla rzędu pierwszego istnieje tylko jeden kwadrat łaciński z symbolem 1 i jedna quasigrupa z podstawowym zbiorem {1}; jest to grupa, trywialna grupa .

Zamówienie 2

Jest tylko jeden zredukowany kwadrat łaciński rzędu drugiego (i tylko dwa w sumie), a mianowicie

{\ Displaystyle {\ początek {macierz} 1 i 2 \\ 2 i 1 \ koniec {macierz}}.}

Ponieważ istnieje tylko jeden zredukowany kwadrat tego rzędu, istnieje tylko jedna klasa izotopów. W rzeczywistości ta klasa izotopów jest również klasą izomorfizmu ( pokazana powyżej ).

Ponieważ istnieje tylko jedna klasa izomorfizmu kwadratów łacińskich, istnieje tylko jedna quasigrupa rzędu drugiego (do izomorfizmu) i jest to grupa zwykle oznaczana przez ℤ / 2 ℤ , grupa cykliczna rzędu drugiego.

Zamówienie 3

Jest też tylko jeden zredukowany kwadrat łaciński rzędu trzeciego (z 12),

{\ Displaystyle {\ początek {macierz} 1 i 2 i 3 \\ 2 i 3 i 1 \\ 3 i 1 i 2 \ koniec {macierz}}.}

Zatem istnieje tylko jedna klasa izotopów. Jednak ta klasa izotopów jest połączeniem pięciu klas izomorfizmu.

Trzy z pięciu klas izomorfizmu zawierają po trzy kwadraty łacińskie, jedna zawiera dwa, a jedna zawiera tylko jeden. Zredukowany kwadrat należy do klasy izomorfizmu z trzema elementami, więc odpowiednia quasigrupa jest pętlą, w rzeczywistości jest to grupa ℤ / 3 ℤ , grupa cykliczna rzędu trzeciego. Kwadrat łaciński reprezentujący każdą z tych klas izomorfizmu jest określony przez (liczba poniżej każdej to liczba kwadratów w odpowiedniej klasie izomorfizmu):

{\ Displaystyle {\ rozpocząć {macierz} 1 i 2 i 3 \\ 2 i 3 i 1 \\ 3 i 1 i 2 \\& (3) i koniec {macierz}} \ qquad \ qquad {\ rozpocząć {macierz} 2 i 3 i 1 \\ 1 i 2 i 3 \\ 3 i 1 i 2 \\& ( 3)&\end{macierz}}\qquad \qquad {\begin{macierz}2&1&3\\3&2&1\\1&3&2\\&(3)\end{macierz}}\qquad \qquad {\begin{macierz}3&2&1\ \2&1&3\\1&3&2\\&(2)&\end{macierz}}\qquad \qquad {\begin{macierz}1&3&2\\3&2&1\\2&1&3\\&(1)&\end{macierz}}.}

Zamówienie 4

Istnieją cztery zredukowane kwadraty łacińskie rzędu czterech (z 576 kwadratów). To są:

\ qquad {\begin{macierz}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\end{macierz}}\qquad {\begin{macierz}1&2&3&4\\2&4&1&3\\3&1&4&2\\4&3&2&1\end{macierz}}.}

Ostatnie trzy z nich są izomorficzne ( patrz wyżej ). Istnieją dwie główne klasy, dwie klasy izotopów i 35 klas izomorfizmu. Spośród 35 quasigrup tylko dwie są pętlami i faktycznie są to grupy. Pierwszemu kwadratowi powyżej odpowiada grupa czterech Kleina , podczas gdy dowolnemu z pozostałych trzech kwadratów odpowiada grupa cykliczna ℤ / 4 ℤ . Pierwszy kwadrat ma osiem poprzecznych i 12 interkalacji, podczas gdy każdy z pozostałych nie ma poprzecznych i cztery interkalacje.

Klasa izomorfizmu grupy czterech Kleina ma czterech członków, podczas gdy klasa izomorfizmu grupy cyklicznej ma 12 członków. Spośród 576 kwadratów łacińskich 288 to rozwiązania Sudoku w wersji 4×4 , czasami nazywanej Shi Doku [1] .

Zamówienie 5

Spośród 161 280 kwadratów łacińskich rzędu piątego jest 56 kwadratów zredukowanych. Istnieją dwie główne klasy i tylko dwie klasy izotopów, ale 1411 klas izomorfizmu. Istnieje sześć klas izomorfizmu, które zawierają zredukowane kwadraty, to znaczy istnieje sześć pętli, z których tylko jedna jest grupą, grupą cykliczną rzędu piątego.

Poniżej znajdują się dwa zredukowane kwadraty łacińskie rzędu piątego, po jednym z każdej klasy izotopów.

{\ Displaystyle {\ początek {macierz} 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\end {macierz}}\qquad \qquad {\początek {macierz}0&1&2&3&4\\1&0&3&4&2\\2&3&4&0&1\\ 3&4&1&2&0\\ 4&2&0&1&3\end{macierz}}}

Pierwszy kwadrat ma 15 poprzecznych, bez interkalacji i jest nieograniczoną tablicą Cayleya grupy cyklicznej ℤ / 5 ℤ . Drugi kwadrat ma trzy poprzeczne i cztery interkalacje. Reprezentuje pętlę, która nie jest grupą, ponieważ np. 2 + (3 + 4) = 2 + 0 = 2, podczas gdy (2 + 3) + 4 = 0 + 4 = 4, więc prawo asocjacyjne nie trzymać.

Zamówienia od 6 do 10

Liczba kwadratów łacińskich, wraz ze wzrostem kolejności, wykazuje zjawisko znane jako eksplozja kombinatoryczna ; nawet niewielkiemu wzrostowi wielkości odpowiada ogromny wzrost odmian. Podstawowe liczby podano w następnych dwóch tabelach i niewiele ponad to, co tu przedstawiono, jest znane z dokładnością.

Liczba klas izotopów kwadratów łacińskich i kwazigrup (klasy izomorfizmu)
$N$	główne klasy	klasy izotopów	klasy izomorfizmu
6	12	22	1 130 531
7	147	564	12 198 455 835
8	283657	1 676 267	2697818331680661
9	19 270 853 541	115 618 721 533	15 224 734 061 438 247 321 497
10	34 817 397 894 749 939	208 904 371 354 363 006	2 750 892 211 809 150 446 995 735 533 513

Liczby zredukowanych kwadratów łacińskich i pętli o różnych rozmiarach
$N$	zredukowane kwadraty łacińskie o rozmiarze $n$	pętle o rozmiarze $n$
6	9408	109
7	16 942 080	23746
8	535 281 401 856	106 228 849
9	377 597 570 964 258 816	9365022303540
10	7 580 721 483 160 132 811 489 280	20 890 436 195 945 769 617

Historia

Ta relacja podąża za McKayem, Meynertem i Myrvoldem (2007 , s. 100).

Liczenie kwadratów łacińskich ma długą historię, ale opublikowane relacje zawierają wiele błędów. Euler w 1782 r. I Cayley w 1890 r. Znali liczbę zredukowanych kwadratów łacińskich do rzędu pięciu. W 1915 roku MacMahon podszedł do problemu w inny sposób, ale początkowo uzyskał niewłaściwą wartość dla rzędu piątego. M. Frolov w 1890 r. i Tarry w 1901 r. ustalili liczbę zredukowanych kwadratów rzędu sześciu. M. Frołow podał błędną liczbę zredukowanych kwadratów rzędu siódmego. RA Fisher i F. Yates , nieświadomy wcześniejszych prac E. Schönhardta, podał liczbę klas izotopów rzędów do sześciu. W 1939 roku HW Norton znalazł 562 klasy izotopów rzędu siódmego, ale przyznał, że jego metoda jest niekompletna. A. Sade, w 1951 r., ale prywatnie opublikowany wcześniej w 1948 r., i PN Saxena znaleźli więcej klas, aw 1966 r. DA Preece zauważył, że to poprawiło wynik Nortona do 564 klas izotopów. Jednak w 1968 roku JW Brown ogłosił błędną wartość 563, która często się powtarzała. Podał również niewłaściwą liczbę klas izotopów rzędu ósmego. Właściwą liczbę zredukowanych kwadratów rzędu ośmiu odkrył już MB Wells w 1967 r., a numery klas izotopów w 1990 r. G. Kolesova, CWH Lam i L. Thiel. Liczbę kwadratów zredukowanych dla rzędu dziewiątego uzyskali SE Bammel i J. Rothstein, dla rzędu 10 BD McKay i E. Rogoyski, a dla rzędu 11 BD McKay i IM Wanless.

Zobacz też

Lista małych grup

Notatki

Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (wyd. 2), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
Dénes, J.; Keedwell, AD (1974), Kwadraty łacińskie i ich zastosowania , New York-London: Academic Press, s. 547, ISBN 0-12-209350-X , MR 0351850
McKay, Brendan D .; Meynert, Alison; Myrvold, Wendy (2007), „Małe kwadraty łacińskie, quasigrupy i pętle” (PDF) , Journal of Combinatorial Designs , 15 (2): 98–119, CiteSeerX 10.1.1.151.3043 , doi : 10.1002/jcd.20105 , S2CID 82321 , Zbl 1112.05018