Латинский квадрат

Лати́нский квадра́т n-го порядка — таблица L=(l_ij) размеров n × n, заполненная n элементами упорядоченного множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:

$\begin{bmatrix} A & B & C \\ C & A & B \\ B & C & A \\ \end{bmatrix}$

В настоящее время в качестве множества M обычно берется множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.^[1]

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли аддитивной группы кольца $\mathbb{Z}_n$: l_ij= (i+j-1) mod n.

История исследований латинских квадратов

Окно в честь Фишера с латинским квадратом 7-го порядка. Кембридж

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

Пары ортогональных латинских квадратов впервые были упомянуты J. Ozanam в 1725 году.^[2] В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.

Эта задача имеет 6192 решения (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера.^[1] Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечетных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

Необходимо разместить 36 офицеров шести различных полков и шести различных воинских званий в каре так, чтобы в каждой колонне и в каждом ряду был ровно один офицер каждого полка и каждого воинского звания.

В 1890 году Кэли вывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в 1708 году).^[3]

В 1900 году гипотеза Эйлера для n = 6 была подтверждена G. Tarry.^[4] Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».

В 1922 году MacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов.^[5] В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.

В 1925 году Fisher предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.^[6]

В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.

В 1959 году Bose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в 1960 году они же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.^[7]

Число латинских квадратов

Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) дает формула

$\prod_{k=1}^n \left(k!\right)^{n/k}\geq L(n)\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}$^[8]

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком на множестве M. Пример нормализованного латинского квадрата:

$\begin{bmatrix} A & B & C \\ B & C & A \\ C & A & B \\ \end{bmatrix}$

Число R(n) нормализованных латинских квадратов n-го порядка в n!(n-1)! раз меньше, чем L(n).

Точные значения величины L(n) известны для n от 1 до 11:^[9]

Число латинских квадратов

n	R(n)	L(n)	Автор и год
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161280	Euler (1782)
6	9408	812851200	Frolov (1890)
7	16942080	61479419904000	Sade (1948)
8	535281401856	108776032459082956800	Wells (1967)
9	377597570964258816	5524751496156892842531225600	Bammel и Rothstein (1975)
10	7580721483160132811489280	9982437658213039871725064756920320000	McKay и Rogoyski (1995)
11	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000	McKay и Wanless (2005)

Отношения эквивалентности на множестве латинских квадратов

Два латинских квадрата называют изотопными, если один из них может быть получен из другого в результате изотопии – композиции из перестановки строк, перестановки столбцов и замены элементов множества M по подстановке из симметрической группы S(M).

Изотопия является отношением эквивалентности, поэтому множество латинских квадратов n-го порядка разбивается на непересекающиеся изотопические классы. Из одного латинского квадрата можно получить с помощью изотопии (n!)³ эквивалентных, но некоторые из них при этом могут совпасть с исходным, это называется автопаратопией. Доля латинских квадратов с нетривиальной группой автопаратопий стремится к нулю с ростом n.^[9]

Латинский квадрат можно рассматривать как ортогональный массив. Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.

Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.^[10]

Число классов эквивалентности

n	Число главных классов	Число изотопических классов
1	1	1
2	1	1
3	1	1
4	2	2
5	2	2
6	12	22
7	147	564
8	283657	1676267
9	19270853541	115618721533
10	34817397894749939	208904371354363006
11	2036029552582883134196099	12216177315369229261482540

Ортогональные латинские квадраты

Два латинских квадрата L=(l_ij) и K=(k_ij) n-го порядка называются ортогональными, если все упорядоченные пары (l_ij,k_ij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:

$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \\ \end{bmatrix} \quad\quad \begin{bmatrix} (1,1) & (2,2) & (3,3)\\ (2,3) & (3,1) & (1,2)\\ (3,2) & (1,3) & (2,1)\\ \end{bmatrix}$

Эйлер называл такие квадраты "полными". В его честь в научной литературе их раньше называли "эйлеровыми" или "греко-латинскими" (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.

Латинский квадрат L n-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей.

Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов n-го порядка. Максимально возможная мощность N(n) такого множества равна n-1, в этом случае множество называется полным.

При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.

Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида f_a(x,y)=ax+y при ненулевом a над полем $\mathrm{GF}(n)$.^[11] Пример построения полного множества попарно ортогональных латинских квадратов 4-ого порядка (d – корень примитивного многочлена x²+x+1 над $\mathrm{GF}(2)$):

$\begin{bmatrix} 0 & 1 & d & d+1\\ 1 & 0 & d+1 & d\\ d & d+1 & 0 & 1\\ d+1 & d & 1 & 0\\ \end{bmatrix} \quad\quad \begin{bmatrix} 0 & 1 & d & d+1\\ d & d+1 & 0 & 1\\ d+1 & d & 1 & 0\\ 1 & 0 & d+1 & d\\ \end{bmatrix} \quad\quad \begin{bmatrix} 0 & 1 & d & d+1\\ d+1 & d & 1 & 0\\ 1 & 0 & d+1 & d\\ d & d+1 & 0 & 1\\ \end{bmatrix}$

Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.

Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Нижние оценки числа N(n)

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	32
N(n)≥			2	3	4		6	7	8	2	10	5	12	3	4	15	16	3	18	4	5	3	22	6	24	4	26	5	28	4	30	31

Построение ортогональных квадратов – сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырех ортоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.^[12]

Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.

Частичные квадраты

Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.

Задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной.

Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причем никакое его подмножество условию однозначности не удовлетворяет.^[13] Мощность C(n) критического множества для квадратов размеров n × n известна для n < 7:

Мощность критического множества

n	1	2	3	4	5	6
С(n)	0	1	3	7	11	18

Нерешенные задачи

Помимо задачи нахождения формулы для величины L(n), имеется большое количество нерешенных задач относительно латинских квадратов. Ряд таких задач был сформулирован на конференции Loops'03:

• Оценка максимального числа трансверсалей в латинском квадрате n-го порядка

• Характеризация латинских подквадратов в таблице умножения луп Муфанг

• Оценка плотности частичного квадрата, удовлетворяющего свойству Блэкберна

• Вычисление максимального t(n), при котором 2^t(n) делит величину L(n)

Применение

Пример использования латинского квадрата в филателии

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.

Игры и головоломки с латинскими квадратами

Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов являются латинскими квадратами 3-го порядка.

Пользуются популярностью также задачи построения латинских квадратов и на их основе магических квадратов, обладающих дополнительными свойствами (например, диагональные квадраты).

См. также

• Ортогональный массив
• Магический квадрат
• Судоку

Примечания

1. ↑ ^{1 2} Euler L. Recherches sur une nouvelle espèce de quarrés magiques. — Middelburg, 1782.
2. ↑ Ozanam J. Récréations mathématiques et physiques. — Paris, 1725.
3. ↑ Cayley A. On Latin Squares // Messenger of mathematics. — 1890. — Т. XIX. — С. 135–137.
4. ↑ Tarry G. Le problème des 36 officiers // Comptes Rendus Assoc. France Av. Sci.. — 1900. — Т. 29, part 2. — С. 170–203.
5. ↑ MacNeish, Harris F. Euler Squares // Annals of Mathematics. — 1922. — Т. 23. — С. 221–227.
6. ↑ Fisher R. A. Statistical methods for research workers. — Edinburg, London: Oliver & Boyd, 1925.
7. ↑ Bose R. C.; Shrikhande S. S. On the falsity of Euler’s conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2 // Proc. Nat. Acad. Sci. U.S.A.. — 1959. — Т. 45. — С. 734–737.
8. ↑ van Lint J. H., Wilson R. M. A Course in Combinatorics. — Cambridge University Press, 1992.
9. ↑ ^{1 2} McKay B. D., Wanless I. M. On the number of Latin Squares // Ann. Combin.. — 2005. — Т. 9. — С. 335-344.
10. ↑ Черемушкин А. В. Почти все латинские квадраты имеют тривиальную группу автострофий // Прикладная дискретная математика. — 2009. — Т. 3(5). — С. 29–32.
11. ↑ Bose R.S. On the applications of the properties of Galois fields to the problems of construction of Hyper-Graeco-Latin squares // Indian J. Stat.. — 1938. — Т. № 3. Part. 4. — С. 323–338.
12. ↑ Dulmage A. L., Johnson D., Mendelsohn N. S. Orthomorphisms of groups and orthogonal Latin squares I // Canad. J. Math.. — 1961. — Т. 13. — С. 356–372.
13. ↑ Nelder J. Critical sets in latin squares // CSIRO Division of Math. and Stats. — 1977. — Т. Newsletter, 38.

Литература

• Холл М. Комбинаторика, пер. с англ. М. 1970.
• Dénes J. H., Keedwell A. D. Latin Squares and their Applications. Budapest. 1974.
• Сачков В. Н. Комбинаторные методы дискретной математики. М. 1977.
• Dénes J. H., Keedwell A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics vol. 46. Academic Press. Amsterdam. 1991.
• Laywine C.F., Mullen G.L. Discrete mathematics using Latin squares. New York. 1998.
• Малых А. Е., Данилова В. И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях // Вестник Пермского Университета. 2010. Вып. 4(4). С. 95-104.
• Тужилин М. Э. Об истории исследований латинских квадратов // Обозрение прикладной и промышленной математики. 2012. Том 19, выпуск 2. С. 226—227.