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

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

который может быть представлен в виде {(1,1,A), (1,2,B), (1,3,C), (2,1,C), (2,2,A), (2,3,B), (3,1,B), (3,2,C), (3,3,A)}, где первый и второй элемент — позиция элемента в матрице, а третий — значение.

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

Латинские квадраты существуют для любого n , достаточно взять таблицу Кэли группы порядка n , например, ${\displaystyle l_{ij}=(i+j-1){\pmod {n}}}$ .

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

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

В 1700 году латинские квадраты были описаны корейским математиком Чхве Сок Чон , где он сформулировал «задачу о шестиугольной черепахе», полностью эквивалентную «задаче о 36 офицерах», которая будет вновь сформулирована Эйлером через 67 лет.

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

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

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

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

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

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

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

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

В 1925 году Роналд Фишер предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов .

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

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

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

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

${\displaystyle \prod _{k=1}^{n}\left(k!\right)^{n/k}\geq L(n)\geq {\frac {\left(n!\right)^{2n}}{n^{n^{2}}}}}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 . Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида ${\displaystyle f_{a}(x,y)=ax+y}$ при ненулевом a над полем ${\displaystyle \mathrm {GF} (n)}$ . Пример построения полного множества попарно ортогональных латинских квадратов 4-го порядка ( d — корень примитивного многочлена ${\displaystyle x^{2}+x+1}$ над ${\displaystyle \mathrm {GF} (2)}$ ):

${\displaystyle {\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 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

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

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

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

Латинский квадрат называется диагональным, если в дополнение к требованиям уникальности элементов в строках и столбцах, свойственным для латинского квадрата, добавляются требования уникальности элементов на главной и побочной диагоналях . Аналитическая оценка числа диагональных латинских квадратов неизвестна, их число для размерностей N<10 было определено в 2016 г. в проекте добровольных распределённых вычислений Gerasim@Home (последовательность в OEIS и последовательность в OEIS ). Для диагональных латинских квадратов, как и для просто латинских, возможно построение ортогональных пар, часть из которых (порядка 9 и 10) была найдена в проекте добровольных распределённых вычислений SAT@home с использованием SAT-подхода . В настоящее время поиск пар ортогональных диагональных латинских квадратов 10-го порядка производится в проекте добровольных распределённых вычислений Gerasim@Home с использованием трансверсалей , а также в BOINC -проектах ODLK и ODLK1 . 25 апреля 2018 г. найден диагональный латинский квадрат 10-го порядка, имеющий 10 ортогональных диагональных латинских квадратов . Это максимальное известное количество ортогональных диагональных квадратов у диагонального латинского квадрата 10-го порядка (последовательность в OEIS ). Открытой математической проблемой является существование тройки попарно ортогональных диагональных латинских квадратов порядка 10 (на текущий момент наилучшим приближением к её решению является тройка квадратов, в которой две пары квадратов ортогональны, а третья частично ортогональна в 74 ячейках ).

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

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

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

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

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

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

• Оценка максимального числа трансверсалей в латинском квадрате n -го порядка
• Характеризация латинских подквадратов в таблице умножения луп Муфанг
• Оценка плотности частичного квадрата, удовлетворяющего свойству Блэкберна
• Вычисление максимального t(n) , при котором 2 ^t(n) делит величину L ( n )

Применение

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

Применение в криптографии. Протокол с нулевым разглашением

В настоящее время латинские квадраты активно применяются для реализации протоколов с нулевым разглашением. В частности для генерации MAC .
Пусть q ={1,2,…, n }. Для данного латинского квадрата

${\displaystyle LS={\begin{bmatrix}l_{1,1}&...&l_{1,q}\\.&...&.\\l_{q,1}&...&l_{q,q}\\\end{bmatrix}}}$

b = q/2 варианты LS изотопные друг другу.

Предположим, пользователи ${\displaystyle (u_{1},u_{2},...,u_{k})}$ образуют сеть. ${\displaystyle u_{i}}$ имеет публичный ключ ${\displaystyle L_{u}i}$ и ${\displaystyle L'_{u}i}$ (обозначим два изотопных Латинских квадрата порядка n) и секретный ключ ${\displaystyle I_{u}i}$ (обозначим изотопизм ${\displaystyle L_{u}i}$ над ${\displaystyle L'_{u}i}$ ). ${\displaystyle u_{i}}$ хочет доказать подлинность ${\displaystyle u_{j}}$ , но он не хочет раскрывать секретный ключ ( Доказательство с нулевым разглашением ).

1. ${\displaystyle u_{i}}$ случайным образом переставляет ${\displaystyle L_{u}i}$ и получает другой латинский квадрат Н
2. ${\displaystyle u_{i}}$ отправляет Н к ${\displaystyle u_{j}}$
3. ${\displaystyle u_{j}}$ просит ${\displaystyle u_{i}}$ либо:
— доказать что Н и ${\displaystyle L'_{u}i}$ изотопны
— доказать что Н и ${\displaystyle L_{u}i}$ изотопны
4. ${\displaystyle u_{i}}$ выполняет просьбу. Он или
— доказывает что Н и ${\displaystyle L'_{u}i}$ изотопны
— доказывает что Н и ${\displaystyle L_{u}i}$ изотопны
5. ${\displaystyle u_{i}}$ и ${\displaystyle u_{j}}$ повторяют шаги 1-4 n раз

Ниже приведён псевдокод для посчёта Хеш-функции

for k from 1 to q do
    begin
        d_k=1;
    end
for i from 1 to q do
    begin
    for j from 1 to q do
        begin
        for k from 1 to b do
            begin
                 d_l_ji=m_ij*d_l_ji;
            end
        end
    end

Хеш-сумма получится в векторе D=[ ${\displaystyle d_{1},...,d_{n}}$ ]
Пример использования:
Пусть q =8, b =4

${\displaystyle LS={\begin{bmatrix}1&7&3&8&5&6&4&2\\2&5&4&6&7&8&3&1\\3&8&1&7&6&5&2&4\\4&6&2&5&8&7&1&3\\7&1&8&3&4&2&5&6\\8&3&7&1&2&4&6&5\\5&2&6&4&3&1&7&8\\6&4&5&2&1&3&8&7\\\end{bmatrix}}}$

${\displaystyle LS^{1}={\begin{bmatrix}7&1&8&3&4&2&5&6\\5&2&6&4&3&1&7&8\\1&7&3&8&5&6&4&2\\3&8&1&7&6&5&2&4\\8&3&7&1&4&4&6&5\\6&4&5&2&1&3&8&7\\2&5&4&6&7&8&3&1\\4&6&2&5&8&7&1&3\\\end{bmatrix}}}$ ${\displaystyle LS^{2}={\begin{bmatrix}8&3&7&1&2&4&6&5\\4&6&2&5&8&7&1&3\\5&2&6&4&3&1&7&8\\1&7&3&8&5&6&4&2\\7&1&8&3&4&2&5&6\\3&8&1&7&6&5&2&4\\6&4&5&2&1&3&8&7\\2&5&4&6&3&8&3&1\\\end{bmatrix}}}$

и

${\displaystyle LS^{3}={\begin{bmatrix}1&7&3&8&5&6&4&2\\3&8&1&7&6&5&2&4\\7&1&8&3&4&2&5&6\\5&2&6&4&3&1&7&8\\2&5&4&6&7&8&3&1\\4&6&2&5&8&7&1&3\\8&3&7&1&2&4&6&5\\6&4&5&2&1&3&8&7\\\end{bmatrix}}}$ ${\displaystyle LS^{4}={\begin{bmatrix}4&6&2&5&8&7&1&3\\2&5&4&6&7&8&3&1\\6&4&5&2&1&3&8&7\\8&3&7&1&2&4&6&5\\3&8&1&7&6&5&2&4\\1&7&3&8&5&6&4&2\\5&2&6&4&3&1&7&8\\7&1&8&3&4&2&5&6\\\end{bmatrix}}}$

Предположим что передаётся следующее сообщение:

${\displaystyle M={\begin{bmatrix}3&2&5&4&1&2&1&6\\7&8&4&5&2&3&3&1\\4&8&6&7&5&4&3&2\\1&4&5&7&8&6&6&6\\7&1&2&8&7&3&4&5\\7&8&1&1&8&2&6&5\\3&4&8&1&2&3&7&6\\2&4&5&3&3&6&8&7\\\end{bmatrix}}}$

Перемещения строк для получения матриц с ${\displaystyle LS^{1}}$ до ${\displaystyle LS^{4}}$
${\displaystyle RP^{1}={\begin{bmatrix}5&7&1&3&6&8&2&4\\\end{bmatrix}}}$
${\displaystyle RP^{2}={\begin{bmatrix}6&4&7&1&5&3&8&2\\\end{bmatrix}}}$
${\displaystyle RP^{3}={\begin{bmatrix}1&3&5&7&2&4&6&8\\\end{bmatrix}}}$
${\displaystyle RP^{4}={\begin{bmatrix}4&2&8&6&3&1&7&5\\\end{bmatrix}}}$

Зададим вектор ${\displaystyle D={\begin{bmatrix}1&1&1&1&1&1&1&1\\\end{bmatrix}}}$
И будем считать хеш по алгоритму приведённому выше:
Получим ${\displaystyle D={\begin{bmatrix}1&7&5&4&4&5&8&1\\\end{bmatrix}}}$

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

Схема с разделением секрета, в которой ключом является латинский квадрат ${\displaystyle L}$ порядка ${\displaystyle n}$ . Латинский квадрат держится в секрете. Между тем порядок латинского квадрата публикуется для всех. Разделение секрета основано на частичных латинских квадратах ${\displaystyle S}$ ={ ${\displaystyle A_{i}}$ | ${\displaystyle A_{i}}$ критические множества ${\displaystyle L}$ }. Объединение может быть составлено из всех возможных критических множеств L или из множества критических множеств. Количество критических множеств зависит от порядка латинского квадрата и числа участников, участвующих в схеме.
Протокол:
Выбирается латинский квадрат L. Порядок n разглашается, но сам латинский квадрат остаётся в секрете и используется как ключ.
Множество S объединение критических множеств L.
Каждый участник получает долю (i, j, k) .
Когда участники собираются вместе они могут соединить свои части вместе и восстановить квадрат L.
Пример:
Выделим три частичных квадрата: ${\displaystyle C_{1},C_{2},C_{3}}$

${\displaystyle {\begin{bmatrix}0&.&.\\.&2&.\\.&.&.\\\end{bmatrix}}\quad \quad {\begin{bmatrix}.&.&.\\.&2&.\\.&.&1\\\end{bmatrix}}\quad \quad {\begin{bmatrix}0&.&.\\.&.&.\\.&.&1\\\end{bmatrix}}}$

И целый квадрат L

Мы можем легко убедиться, что все частные латинские квадраты ${\displaystyle C_{1}}$ , ${\displaystyle C_{2}}$ , ${\displaystyle C_{3}}$ являются критическими множествами. Они могут быть однозначно расширены до полного латинского квадрата L. Это уникальное свойство теряется если любой элемент любого частичного латинского квадрата ${\displaystyle C_{1}}$ , ${\displaystyle C_{2}}$ , ${\displaystyle C_{3}}$ удаляется.
Пусть ${\displaystyle S}$ объединение трёх критических наборов ${\displaystyle C_{1}}$ , ${\displaystyle C_{2}}$ , ${\displaystyle C_{3}}$ . Тогда ${\displaystyle S}$ = ${\displaystyle {(1,1,1),(2,2,3),(3,3,2)}}$ .
Мы распространяем трём участникам части ${\displaystyle S}$ . Любые два участника могут восстановить полный латинский квадрат.
Полученный выше простой пример может быть расширен до общего случая.
В 1979 латинский квадрат был предложен в качестве хорошего кандидата для использования в секретных схемах распределения. Однако, Есть определённые ограничения для его применения, как описано ниже.
1) Сразу после распределения частей критического множества, частичная информация будет доступна любой несанкционированной группе. Это означает, что есть высокий шанс для любой несанкционированной группе, чтобы выяснить остальные части методом проб и ошибок. Таким образом, предложенная схема не идеальна.
2) Схема не является гибкой. В данном случае это просто схема расщепления секрета.
Хеширование
Если мы хотим, использовать хеш-сумму для хранения фиксированного секретного квадрата, например, латинского квадрата порядка 10, мы должны хранить 81 номер (последнюю строку и столбец хранить не обязательно). Четыре бита могут быть использованы для хранения ряда, так что нам понадобится 324 бит. В этом случае, мы можем выбрать SHA-384 или SHA-512 . Если нам нужно использовать SHA-256 , мы можем проступить следующим образом. 10 бит будем использовать для представления 3-го номера. Таким образом, мы сначала использовали 250 бит для представления 75 чисел, а затем следующие 4 бита для представления одного номера. В общей сложности, мы можем хранить 76 номеров. Зафиксируем частичный латинский квадрат в следующем формате. Выберем латинский квадрат порядка 10, который можно восстановить однозначно, удалив записи, как показано в таблице. Компромиссом здесь является то, что небольшой процент латинских квадратов порядка 10, не могут быть восстановлены однозначно и, следовательно, не могут быть выбран в качестве секрета.

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

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

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

См. также

• Магический квадрат
• Судоку
• SAT@home проект распределённых вычислений, занимающийся поиском ортогональных пар латинских квадратов 9 и 10 порядка.

Примечания

Литература

• Холл М. Комбинаторика, пер. с англ. М., 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 .
• Большакова Н. С. // Вестник МГТУ. — 2005. — Т. 8 , № 1 . — С. 170—173 .

Ссылки

• Н. Макарова. .
• Н. Макарова. .