Взаимно ортогональные латинские квадраты

В комбинаторной математике два латинских квадрата одинакового размера ( порядка ) называются ортогональными, если при наложении друг на друга все упорядоченные парные элементы в позициях различны. Набор латинских квадратов одного порядка, все пары которых ортогональны, называется набором взаимно ортогональных латинских квадратов . Это понятие ортогональности в комбинаторике ^{[ сломанный якорь ]} тесно связано с концепцией блокировки в статистике , которая гарантирует, что независимые переменные действительно независимы, без каких-либо скрытых мешающих корреляций. Таким образом, «ортогональный» является синонимом «независимого» в том смысле, что знание значения одной переменной не дает дополнительной информации о вероятном значении другой переменной.

Устаревший термин для пары ортогональных латинских квадратов — греко-латинский квадрат , встречающийся в более старой литературе.

Греко-латинские квадраты

Греко -латинский квадрат или квадрат Эйлера или пара ортогональных латинских квадратов порядка $n$ над двумя множествами $S$ и $T$ (которые могут быть одинаковыми), каждый из которых состоит из $n$ символов, представляет собой $n \times n$ расположение ячеек размером , каждая из которых содержит упорядоченная пара $(s, t)$ , где $s$ находится в $S$ и $t$ находится в $T$ , такая, что каждая строка и каждый столбец содержат каждый элемент $S$ и каждый элемент $T$ ровно один раз, и что никакие две ячейки не содержат одну и ту же упорядоченную пару.

Греко-латинские квадраты (пары ортогональных латинских квадратов)
Заказ 3
Заказ 4
Заказать 5

Расположение $s$ -координат по отдельности (которые можно рассматривать как латинские символы) и $t$ -координат (греческих символов) образует латинский квадрат . Таким образом, греко-латинский квадрат можно разложить на два ортогональных латинских квадрата. Ортогональность здесь означает, что каждая пара $(s, t)$ из декартова произведения $S \times T$ встречается ровно один раз.

Ортогональные латинские квадраты подробно изучались Леонардом Эйлером , который взял за два набора $S = {A, B, C,...$ }, первые $n$ заглавных букв латинского алфавита , и $T = {α, β, γ, ...$ }, первые $n$ строчных букв греческого алфавита — отсюда и название греко-латинского квадрата.

Существование

Когда греко-латинский квадрат рассматривается как пара ортогональных латинских квадратов, говорят, что каждый из латинских квадратов имеет ортогональную пару . В произвольном латинском квадрате набор позиций, по одной в каждой строке и по одной в каждом столбце, все записи которых различны, называется трансверсалью этого квадрата. ^{[ 1 ]} Рассмотрим один символ в греко-латинском квадрате. Все позиции, содержащие этот символ, должны находиться в разных строках и столбцах, и, кроме того, все другие символы в этих позициях должны быть разными. Следовательно, если рассматривать пару латинских квадратов, позиции, содержащие один символ в первом квадрате, соответствуют трансверсали во втором квадрате (и наоборот).

Данный латинский квадрат порядка n обладает ортогональным матом тогда и только тогда, когда он имеет n непересекающихся трансверсалей. ^{[ 2 ]}

Таблица Кэли (без границ) любой группы нечетного порядка образует латинский квадрат, имеющий ортогональный мат. ^{[ 2 ]}

Таким образом, греко-латинские квадраты существуют для всех нечетных порядков, поскольку существуют группы этих порядков. Говорят, что такие греко-латинские квадраты основаны на группах .

Эйлер смог построить греко-латинские квадраты порядков, кратных четырем. ^{[ 2 ]} и, похоже, знал о следующем результате.

Никакие греко-латинские квадраты, основанные на группе, не могут существовать, если порядок нечетно кратен двум (то есть равен 4 $k$ + 2 для некоторого положительного целого числа $k$ ). ^{[ 3 ]}

История

Хотя он и получил признание за свою оригинальную математическую трактовку предмета, ортогональные латинские квадраты появились еще до Эйлера. В виде старинной головоломки с игральными картами . ^{[ 4 ]} Конструкция набора 4х4 была опубликована Жаком Озанамом в 1725 году. ^{[ 5 ]} Задача заключалась в том, чтобы взять все тузы, короли, дамы и валеты из стандартной колоды карт и расположить их в сетке 4х4 так, чтобы в каждой строке и каждом столбце содержались все четыре масти, а также по одной масти каждого номинала. Эта проблема имеет несколько решений.

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

По словам Мартина Гарднера , который представил этот вариант задачи в своей колонке «Математические игры» в ноябре 1959 года , ^{[ 6 ]} ошибочно указала, что число различных решений равно 72 Роуз Болл . не нашла правильное значение 144 Эта ошибка сохранялась в течение многих лет, пока Кэтлин Оллереншоу . Каждое из 144 решений имеет восемь отражений и вращений, что в общей сложности дает 1152 решения. Решения 144×8 можно разделить на следующие два класса эквивалентности :

Решение	Нормальная форма
Решение №1	А♠ К♥ Q♦ J♣ Q♣ J♦ А♥ К♠ J♥ Q♠ К♣ А♦ К♦ А♣ Дж♠ Q♥
Решение № 2	А♠ К♥ Q♦ J♣ J♦ Q♣ К♠ А♥ К♣ А♦ Дж♥ Q♠ Q♥ J♠ А♣ К♦

Для каждого из двух решений можно получить 24×24 = 576 решений путем независимой перестановки четырех мастей и четырех номиналов. Никакая перестановка не превратит два решения друг в друга, поскольку масти и номиналы различны.

Проблема тридцати шести офицеров

Задача, подобная описанной выше карточной задаче, циркулировала в Санкт-Петербурге в конце 1700-х годов, и, согласно фольклору, Екатерина Великая попросила Эйлера решить ее, поскольку он в то время проживал при ее дворе. ^{[ 7 ]} Эта задача известна как проблема тридцати шести офицеров . ^{[ 8 ]} и Эйлер представил это следующим образом: ^{[ 9 ]}^{[ 10 ]}

Очень любопытный вопрос, который в течение некоторого времени занимал изобретательность многих людей, привлек меня к следующим исследованиям, которые, по-видимому, открывают новую область анализа, в частности изучение комбинаций. Речь идет о том, чтобы набрать 36 офицеров из 6 разных полков так, чтобы они были выстроены в квадрат так, чтобы в каждой линии (и горизонтальной, и вертикальной) было по 6 офицеров разных чинов и разных полков.
— Леонард Эйлер

Гипотеза и опровержение Эйлера

Эйлеру не удалось решить эту задачу, но в этой работе он продемонстрировал методы построения греко-латинских квадратов, где $n$ нечетно или кратно 4. Заметив, что не существует квадрата второго порядка и будучи неспособным построить квадрат шестого порядка, он предположил, что что их не существует для любого нечетно четного числа $n \equiv 2 (mod 4).$ Несуществование квадратов шестого порядка было подтверждено в 1901 году Гастоном Тарри посредством исчерпывающего доказательства . ^{[ 11 ]}^{[ 12 ]} Однако гипотеза Эйлера не могла быть решена до конца 1950-х годов, но эта проблема привела к важным работам в области комбинаторики . ^{[ 13 ]}

В 1959 году Р. К. Бозе и С. С. Шрикханде построили несколько контрпримеров (названных спойлерами Эйлера ) 22-го порядка, используя математические идеи. ^{[ 14 ]} Затем Э.Т. Паркер нашел контрпример порядка 10, используя часовой компьютерный поиск на военном компьютере UNIVAC 1206 , работая в подразделении UNIVAC компании Remington Rand (это была одна из первых задач комбинаторики, решенных на цифровом компьютере ).

В апреле 1959 года Паркер, Бозе и Шрикханде представили свою статью, показывающую, что гипотеза Эйлера неверна для всех $n \geq 7.$ ^{[ 15 ]} Таким образом, греко-латинские квадраты существуют для всех порядков $n > 1,$ кроме $n = 2, 6.$ В выпуске журнала Scientific American за ноябрь 1959 года Мартин Гарднер опубликовал этот результат. ^{[ 6 ]} На обложке — опровержение гипотезы Эйлера размером 10 × 10.

Проблема тридцати шести запутанных офицеров

Расширения взаимно ортогональных латинских квадратов в квантовую область изучаются с 2017 года. ^{[ 17 ]} В этих конструкциях вместо уникальности символов элементы массива представляют собой квантовые состояния, которые должны быть ортогональны друг другу в строках и столбцах. В 2021 году индийско-польская группа физиков (Ратер, Бурхардт, Брузда, Райчел-Миельдзиоч, Лакшминараян и Жичковский ) обнаружила массив квантовых состояний, который представляет собой пример взаимно ортогональных квантовых латинских квадратов размера 6; или, что то же самое, группа из 36 запутанных офицеров. ^{[ 16 ]}^{[ 18 ]}^{[ 19 ]} Эта установка решает обобщение проблемы 36 офицеров Эйлера, а также предоставляет новый код обнаружения квантовых ошибок , позволяющий кодировать 6-уровневую систему в три 6-уровневую систему, удостоверяющую возникновение одной ошибки.

Примеры взаимно ортогональных латинских квадратов (MOLS)

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

Например, набор MOLS(4) определяется следующим образом: ^{[ 20 ]}

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

И набор МОЛС(5): ^{[ 21 ]}

{\begin{matrix}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\end{matrix}}\qquad {\begin{matrix}1&2&3&4&5\\3&4&5&1&2\\5&1&2&3&4\\2&3&4&5&1\\4&5&1&2&3\end{matrix}}\qquad {\begin{matrix}1&2&3&4&5\\5&1&2&3&4\\4&5&1&2&3\\3&4&5&1&2\\2&3&4&5&1\end{matrix}}\qquad {\begin{matrix}1&2&3&4&5\\4&5&1&2&3\\2&3&4&5&1\\5&1&2&3&4\\3&4&5&1&2\end{matrix}}.

Хотя можно представить MOLS в «составной» матричной форме, подобной, например, греко-латинским квадратам:

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

для приведенного выше примера MOLS(5) более типично компактно представлять MOLS в виде ортогонального массива (см. ниже ). ^{[ 22 ]}

В примерах MOLS, приведенных до сих пор, для каждого квадрата использовался один и тот же алфавит (набор символов), но в этом нет необходимости, как показывают греко-латинские квадраты. Фактически, для каждого квадрата набора MOLS можно использовать совершенно разные наборы символов. Например,

Любые два цвета текста, цвета переднего плана, цвета фона и шрифта образуют пару ортогональных латинских квадратов:
фьорды	челюсть	мокрота	Винты	цинковый
цинковый	фьорды	челюсть	мокрота	Винты
Винты	цинковый	фьорды	челюсть	мокрота
мокрота	Винты	цинковый	фьорды	челюсть
челюсть	мокрота	Винты	цинковый	фьорды

представляет собой представление составного примера MOLS (5), приведенного выше, где четыре MOLS имеют следующие алфавиты соответственно:

цвет фона: черный , темно-бордовый , бирюзовый , темно-синий и серебристый.
Цвет переднего плана: белый , красный , салатовый , синий и желтый.
текст: фьорды , челюсть , мокрота , кивиут и цинкки.
семейство шрифтов: с засечками , без засечек , моноширинные , курсивные и slab-serif .

Таким образом, приведенная выше таблица позволяет проверить пять значений в каждом из четырех различных измерений всего за 25 наблюдений вместо 625 (= 5 ⁴) наблюдения, необходимые для полного факторного плана . Поскольку пять слов охватывают все 26 букв алфавита, таблица позволяет рассмотреть каждую букву алфавита в пяти различных шрифтах и цветовых сочетаниях.

Количество взаимно ортогональных латинских квадратов

Свойство взаимной ортогональности набора MOLS не зависит от

Переставляя ряды всех квадратов одновременно,
Переставляя столбцы всех квадратов одновременно, и
Перестановка записей в любом квадрате самостоятельно.

Используя эти операции, любой набор MOLS можно привести к стандартной форме , что означает, что первая строка каждого квадрата идентична и обычно располагается в некотором естественном порядке, и первый столбец одного квадрата также находится в этом порядке. ^{[ 23 ]} Примеры MOLS(4) и MOLS(5) в начале этого раздела приведены в стандартной форме.

Приведя набор MOLS( $n$ ) в стандартную форму и исследовав записи во второй строке и первом столбце каждого квадрата, можно увидеть, что $не более n$ - 1 квадратов. может существовать ^{[ 24 ]} Набор из $n$ − 1 MOLS( $n$ ) называется полным набором MOLS . Известно, что полные множества существуют, когда $n$ — простое число или степень простого числа (см. Конструкцию конечного поля ниже ). Однако количество MOLS, которое может существовать для данного порядка $n,$ неизвестно $для общего n$ и является областью исследований в области комбинаторики .

Проективные плоскости

Набор из $n$ - 1 MOLS( $n$ ) эквивалентен конечной аффинной плоскости порядка $n$ (см. Сети ниже). ^{[ 10 ]} Поскольку каждая конечная аффинная плоскость однозначно продолжается до конечной проективной плоскости того же порядка, эта эквивалентность также может быть выражена через существование этих проективных плоскостей. ^{[ 25 ]}

Как упоминалось выше, полные наборы MOLS( $n$ ) существуют, если $n$ — простое число или степень простого числа, поэтому существуют проективные плоскости таких порядков. О существовании конечных проективных плоскостей другого порядка и, следовательно, полных наборов МОЛС таких порядков не известно. ^{[ 10 ]}

Единственным общим результатом об отсутствии конечных проективных плоскостей является теорема Брука–Райзера , которая гласит, что если проективная плоскость порядка $n$ существует и $n$ ≡ 1 (mod 4) или $n$ ≡ 2 (mod 4), то $n$ должно быть суммой двух (целых) квадратов. ^{[ 26 ]} Это исключает, например, проективные плоскости 6 и 14 порядков, но не гарантирует существование плоскости, когда $n$ удовлетворяет условию. В частности, $n$ = 10 удовлетворяет условиям, но проективной плоскости 10-го порядка не существует, как показал очень долгий компьютерный поиск: ^{[ 27 ]} что, в свою очередь, означает, что не существует девяти МОЛС 10-го порядка.

Никакие другие результаты существования неизвестны. По состоянию на 2020 год ^[update] наименьший порядок, для которого существование полного набора МОЛС не установлено, равен 12. ^{[ 10 ]}

Теорема Макниша

Известно, что минимальное количество MOLS( $n$ ) равно 2 для всех $n,$ за исключением $n$ = 2 или 6, где оно равно 1. Однако можно сказать больше, а именно: ^{[ 28 ]}

Теорема Макнейша : если $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{r}^{\alpha _{r}}$ - это разложение целого числа $n$ на степени различных простых чисел $p_{1},p_{2},\cdots ,p_{r}$ затем

минимальное количество МОЛС(

n

)

\geq {\underset {i}{\operatorname {min} }}\{p_{i}^{\alpha _{i}}-1\}.

Теорема Макниша не дает очень хорошей нижней оценки, например, если $n$ ≡ 2 (mod 4), то есть в простой факторизации есть одна 2, теорема дает нижнюю оценку 1, которая превосходит, если $n$ > 6. С другой стороны, он дает правильное значение, когда $n$ является степенью простого числа.

Для общих составных чисел количество МОЛС неизвестно. Первые несколько значений, начинающиеся с $n$ = 2, 3, 4..., — это 1, 2, 3, 4, 1, 6, 7, 8, ... (последовательность A001438 в OEIS ).

Наименьший случай, для которого точное число MOLS( $n$ ) неизвестно, - это $n$ = 10. Из греко-латинской квадратной конструкции их должно быть не менее двух, а из-за отсутствия проективной плоскости порядка 10 меньше девяти. Однако ни один набор из трех MOLS(10) так и не был обнаружен, хотя многие исследователи пытались его обнаружить. ^{[ 29 ]}

При достаточно большом $n$ количество МОЛС больше, чем ${\sqrt[{14.8}]{n}}$ , таким образом, для каждого $k$ существует только конечное число $n$ таких, что количество MOLS равно $k$ . ^{[ 30 ]} При этом минимум равен 6 для всех $n$ > 90.

Конечная полевая конструкция

Полный набор MOLS( $q$ ) существует всякий раз, когда $q$ является простым числом или степенью простого числа. Это следует из конструкции, основанной на конечном поле GF ( $q$ ), которое существует только в том случае, если $q$ является простым числом или степенью простого числа. ^{[ 31 ]} Мультипликативная группа GF ( $q$ ) является циклической группой и поэтому имеет генератор λ, что означает, что все ненулевые элементы поля могут быть выражены как различные степени λ. Назовите $q$ элементов GF ( $q$ ) следующим образом:

α ₀ = 0, α ₁ = 1, α ₂ = λ, α ₃ = λ ², ..., α _{$q$ -1} = λ ^{$д$ -2}.

Теперь λ ^{$д$ -1} = 1, а правило произведения в терминах α равно α _$i$ α _$j$ = α _$t$ , где $t$ = $i$ + $j$ -1 (mod $q$ -1). Латинские квадраты строятся следующим образом: ( $i, j$ )-я запись в латинском квадрате L _$r$ (при $r$ ≠ 0) равна L _$r$ ( $i,j$ ) = α _$i$ + α _$r$ α _$j$ , где все операции происходят в ГФ ( $q$ ). В случае, если поле является простым полем ( $q$ = $p$ a prime), где элементы поля представлены обычным способом, как целые числа по модулю $p$ , можно отказаться от приведенного выше соглашения об именовании и упростить правило построения до L _$r$ ( $i,j$ ) = $i$ + $rj$ , где $r$ ≠ 0 и $i$ , $j$ и $r$ являются элементами GF ( $p$ ), и все операции выполняются в GF ( $p$ ). Приведенные выше примеры MOLS(4) и MOLS(5) возникли из этой конструкции, хотя и с изменением алфавита.

Не все комплектации МОЛС возникают из этой конструкции. Проективная плоскость, связанная с полным набором MOLS, полученным в результате этой конструкции поля, представляет собой особый тип — дезаргову проективную плоскость . Существуют недезарговы проективные плоскости и соответствующие им полные множества МОЛС не могут быть получены из конечных полей. ^{[ 32 ]}

Ортогональный массив

Ортогональный массив OA( $k,n$ ) силы два и индекса один представляет собой $n 2 \times k$ Массив $A$ ( $k$ ≥ 2 и $n$ ≥ 1, целые числа) с элементами из набора размера $n$ , такими что в любых двух столбцах $A$ ( сила ) каждая упорядоченная пара символов появляется ровно в одной строке $A$ ( индекс ) . ^{[ 33 ]}

OA( $s$ + 2, $n$ ) эквивалентен $s$ MOLS( $n$ ). ^{[ 33 ]} Например, пример MOLS(4), приведенный выше и повторенный здесь,

{\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\\&L_{1}&&\end{matrix}}\qquad \qquad {\begin{matrix}1&2&3&4\\4&3&2&1\\2&1&4&3\\3&4&1&2\\&L_{2}&&\end{matrix}}\qquad \qquad {\begin{matrix}1&2&3&4\\3&4&1&2\\4&3&2&1\\2&1&4&3\\&L_{3}&&\end{matrix}}

может использоваться для формирования OA(5,4):

р	с	Л ₁	L_Л2	L_Л3
1	1	1	1	1
1	2	2	2	2
1	3	3	3	3
1	4	4	4	4
2	1	2	4	3
2	2	1	3	4
2	3	4	2	1
2	4	3	1	2
3	1	3	2	4
3	2	4	1	3
3	3	1	4	2
3	4	2	3	1
4	1	4	3	2
4	2	3	4	1
4	3	2	1	4
4	4	1	2	3

где записи в столбцах, помеченных r и c, обозначают строку и столбец позиции в квадрате, а остальная часть строки для фиксированных значений r и c заполняется записью в этой позиции в каждом из латинских квадратов. Этот процесс обратим; учитывая OA( $s$ , $n$ ) с $s$ ≥ 3, выберите любые два столбца, которые будут играть роли r и c , а затем заполните латинские квадраты записями в остальных столбцах.

Более общие ортогональные массивы представляют собой обобщения концепции MOLS, такие как взаимно ортогональные латинские кубы.

Сети

(Геометрическая) ( $k,n$ )-сеть — это набор из $n$ ² элементы, называемые точками , и набор из $kn$ подмножеств, называемых линиями или блоками, каждый из которых имеет размер $n$ и обладает свойством, что две отдельные линии пересекаются не более чем в одной точке. Более того, строки можно разбить на $k$ параллельных классов (никакие две их линии не пересекаются), каждый из которых содержит $по n$ строк. ^{[ 34 ]}

( $n$ + 1, $n$ )-сеть — это аффинная плоскость порядка $n$ .

Набор из $k$ MOLS( $n$ ) эквивалентен ( $k$ + 2, $n$ )-сети. ^{[ 10 ]}

Чтобы построить ( $k$ + 2, $n$ )-сеть из $k$ MOLS( $n$ ), представьте MOLS как ортогональный массив OA( $k$ + 2, $n$ ) (см. выше ). Упорядоченные пары записей в каждой строке ортогонального массива в столбцах, обозначенных $r$ и $c$ , будут считаться координатами $n$ ² точки сети. Каждый второй столбец (то есть латинский квадрат) будет использоваться для определения линий в параллельном классе. строк $n$ , определяемых столбцом с меткой L _i, будут обозначаться l _ij . Точки на l _ij будут точками, координаты которых соответствуют строкам, где запись в столбце L _i равна $j$ . Есть два дополнительных параллельных класса, соответствующих $столбцам r$ и $c$ . Линии $r$ _j и $c$ _j состоят из точек, чьи первые координаты $j$ или вторые координаты $j$ соответственно. Эта конструкция обратима. ^{[ 35 ]}

Например, OA(5,4) в приведенном выше разделе можно использовать для построения (5,4)-сети (аффинной плоскости порядка 4). Точки на каждой линии задаются формулой (каждая строка ниже представляет собой параллельный класс линий):

$л$ ₁₁ :	(1,1) (2,2) (3,3) (4,4)	$л$ ₁₂ :	(1,2) (2,1) (3,4) (4,3)	$л$ ₁₃ :	(1,3) (2,4) (3,1) (4,2)	$л$ ₁₄ :	(1,4) (2,3) (3,2) (4,1)
$л$ ₂₁ :	(1,1) (2,4) (3,2) (4,3)	$л$ ₂₂ :	(1,2) (2,3) (3,1) (4,4)	$л$ ₂₃ :	(1,3) (2,2) (3,4) (4,1)	$л$ ₂₄ :	(1,4) (2,1) (3,3) (4,2)
$л$ ₃₁ :	(1,1) (2,3) (3,4) (4,2)	$л$ ₃₂ :	(1,2) (2,4) (3,3) (4,1)	$л$ ₃₃ :	(1,3) (2,1) (3,2) (4,4)	$л$ ₃₄ :	(1,4) (2,2) (3,1) (4,3)
$р$ ₁ :	(1,1) (1,2) (1,3) (1,4)	$р$ ₂ :	(2,1) (2,2) (2,3) (2,4)	$р$ ₃ :	(3,1) (3,2) (3,3) (3,4)	$р$ ₄ :	(4,1) (4,2) (4,3) (4,4)
$с$ ₁ :	(1,1) (2,1) (3,1) (4,1)	$с$ ₂ :	(1,2) (2,2) (3,2) (4,2)	$в$ ₃ :	(1,3) (2,3) (3,3) (4,3)	$с$ ₄ :	(1,4) (2,4) (3,4) (4,4)

Поперечные конструкции

Трансверсальная конструкция с $k$ группами размера $n$ и индекса λ, обозначаемая T[ $k$ , λ; $n$ ], представляет собой тройку ( $X, G, B$ ), где: ^{[ 36 ]}

$X$ — множество $kn$ многообразий;
$G = {G1, но не, G2;,..., Gk в алгебраическом смысле) ,$ } — семейство $kn$ называемых группами образующих разбиение $X$ -множеств (
$B$ — это семейство $k$ -множеств (называемых блоками ) многообразий, такое, что каждое $k$ -множество в $B$ пересекает каждую группу $G i$ ровно в одном многообразии, и любая пара многообразий, принадлежащих разным группам, встречается вместе ровно в λ блоках в $B.$ .

Существование T[ $k$ ,1; $n$ ] конструкция эквивалентна существованию $k$ -2 MOLS( $n$ ). ^{[ 37 ]}

Трансверсальная конструкция T[ $k$ ,1; $n$ ] — структура двойной инцидентности ( $k,n$ )-сети. То есть он имеет $nk$ точек и $n$ ² блоки. Каждая точка находится в $n$ блоках; каждый блок содержит $k$ точек. Точки попадают в $k$ классов (групп) эквивалентности размера $n$ так, что две точки из одной группы не содержатся в блоке, а две точки из разных групп принадлежат ровно одному блоку. ^{[ 38 ]}

Например, используя (5,4)-сеть из предыдущего раздела, мы можем построить трансверсальную схему T[5,1;4]. Блок, связанный с точкой ( $i, j$ ) сети, будет обозначаться $b$ _ij . Точки дизайна получим по следующей схеме: $r$ _i ↔ $i$ , $c$ _j ↔ 5 $j$ и $l$ _ij ↔ 5 $i$ + $j$ . Таким образом, точки дизайна обозначаются целыми числами 1, ..., 20. Блоками дизайна являются:

$б$ ₁₁ :	6 11 16 1 5	$б$ ₂₂ :	6 13 19 2 10	$б$ ₃₃ :	6 14 17 3 15	$б$ ₄₄ :	6 12 18 4 20
$б$ ₁₂ :	7 12 17 1 10	$б$ ₂₁ :	7 14 18 2 5	$б$ ₃₄ :	7 13 16 3 20	$б$ ₄₃ :	7 11 19 4 15
$б$ ₁₃ :	8 13 18 1 15	$б$ ₂₄ :	8 11 17 2 20	$б$ ₃₁ :	8 12 19 3 5	$б$ ₄₂ :	8 14 16 4 10
$б$ ₁₄ :	9 14 19 1 20	$б$ ₂₃ :	9 12 16 2 15	$б$ ₃₂ :	9 11 18 3 10	$б$ ₄₁ :	9 13 17 4 5

Пять «групп» таковы:

6 7 8 9
11 12 13 14
16 17 18 19
1 2 3 4
5 10 15 20

Теория графов

Набор из $k$ MOLS( $n$ ) эквивалентен реберному разбиению полного ( $k$ + 2)-дольного графа K _{n ,..., n} на полные подграфы порядка $k$ + 2. ^{[ 10 ]}

Приложения

Взаимно ортогональные латинские квадраты имеют множество применений. Они используются в качестве отправной точки для построения статистического планирования экспериментов , планирования турниров , а также кодов исправления и обнаружения ошибок . Интерес Эйлера к греко-латинским квадратам возник из-за его желания построить магические квадраты . Французский писатель Жорж Перек построил свой роман 1978 года «Жизнь: Руководство пользователя» вокруг греко-латинского квадрата размером 10×10.

См. также

Примечания

^ В литературе это использовалось под несколькими названиями: направляющая формула (Эйлера), направляющая , 1-перестановка и диагональ , среди других. ( Денес и Кидуэлл, 1974 , стр. 29)
^ Перейти обратно: ^а ^б ^с Денес и Кидуэлл 1974 , с. 155
^ Денес и Кидуэлл 1974 , с. 156
^ Кнут, Дональд (2011), Искусство компьютерного программирования , том. 4A: Комбинаторные алгоритмы, часть 1, Аддисон-Уэсли, стр. xv+883pp, ISBN 978-0-201-03804-0 . Ошибки: [1]
^ Озанам, Жак (1725), Занятия математикой и физикой , т. 1, с. IV, с. 434 , решение представлено на рис. 35
^ Перейти обратно: ^а ^б Гарднер 1966 , стр. 162-172.
^ ван Линт и Уилсон 1993 , стр.251
^ П. А. Мак-Магон (1902). «Магические квадраты и другие задачи на шахматной доске» . Труды Королевского института Великобритании . XVII : 50–63.
^ Эйлер: Исследование нового вида магических квадратов , написанное в 1779 году , опубликованное в 1782 году.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Колборн и Диниц 2007 , с. 162
^ Тарри, Гастон (1900). «Проблема 36 офицеров». Отчет Французской ассоциации содействия развитию науки . 1 . Секретариат Ассоциации: 122–123.
^ Тарри, Гастон (1901). «Проблема 36 офицеров». Отчет Французской ассоциации содействия развитию науки . 2 . Секретариат Ассоциации: 170–203.
^ ван Линт и Уилсон, 1993 , стр.267.
^ Бозе, RC; Шриханде, С.С. (1959), «О ложности гипотезы Эйлера о несуществовании двух ортогональных латинских квадратов порядка 4 t + 2», Proceedings of the National Academy of Sciences USA , 45 (5): 734–737, Бибкод : 1959PNAS...45..734B , doi : 10.1073/пнас.45.5.734 , ПМК 222625 , ПМИД 16590435
^ Бозе, RC; Шрикханде, СС; Паркер, ET (1960), «Дальнейшие результаты построения взаимно ортогональных латинских квадратов и ложность гипотезы Эйлера», Canadian Journal of Mathematics , 12 : 189–203, doi : 10.4153/CJM-1960-016-5 , MR 0122729
^ Перейти обратно: ^а ^б Скорее, Сухайль Ахмад; Бурхардт, Адам; Брузда, Войцех; Райхель-Миельдзёч, Гжегож; Лакшминараян, Арул; Жичковски, Кароль (2022), «Тридцать шесть запутанных офицеров Эйлера: квантовое решение классически невозможной проблемы», Physical Review Letters , 128 (8): 080507, arXiv : 2104.05122 , Bibcode : 2022PhRvL.128h0507R , doi : 10.1103/PhysRevLett.128.080507 , PMID 35275648 , S2CID 236950798
^ Гойенече, Дардо; Раисси, Захра; Ди Мартино, Сара; Жичковски, Кароль (2018), «Запутывание и квантовые комбинаторные модели», Physical Review A , 97 (6): 062326, arXiv : 1708.05946 , Bibcode : 2018PhRvA..97f2326G , doi : 10.1103/PhysRevA.97.062326 , S2CID 51532085
^ Гаристо, Дэн (2022), «243-летняя «невозможная» головоломка Эйлера получила квантовое решение» , журнал Quanta
^ Паппас, Стефани (2022), «Вековая« невозможная »математическая задача решена с помощью странной физики кота Шредингера» , LiveScience
^ Колборн и Диниц 2007 , с. 160
^ Колборн и Диниц 2007 , с. 163
^ Маккей, Мейнерт и Мирволд 2007 , стр. 98
^ Денес и Кидуэлл 1974 , с. 159
^ Денес и Кидуэлл 1974 , стр. 158.
^ Термин «порядок», используемый здесь для MOLS, аффинных плоскостей и проективных плоскостей, определяется по-разному в каждой ситуации, но эти определения скоординированы таким образом, чтобы числовое значение было одинаковым.
^ Брук, Р.Х.; Райзер, Х.Дж. (1949), «Несуществование некоторых конечных проективных плоскостей», Canadian Journal of Mathematics , 1 : 88–93, doi : 10.4153/cjm-1949-009-2 , S2CID 123440808
^ Лам, CWH (1991), «Поиск конечной проективной плоскости порядка 10» , American Mathematical Monthly , 98 (4): 305–318, doi : 10.2307/2323798 , JSTOR 2323798
^ Денес и Кидуэлл 1974 , с. 390
^ Маккей, Мейнерт и Мирволд 2007 , стр. 102.
^ Ленц, Х.; Юнгникель, Д.; Бет, Томас (ноябрь 1999 г.). Теория дизайна Томаса Бета . Кембриджское ядро. дои : 10.1017/cbo9781139507660 . ISBN 9780521772310 . Проверено 06 июля 2019 г.
^ Денес и Кидуэлл 1974 , с. 167
^ Денес и Кидуэлл 1974 , с. 169
^ Перейти обратно: ^а ^б Стинсон 2004 , с. 140
^ Колборн и Диниц 2007 , с. 161
^ Денес и Кидуэлл 1974 , с. 270
^ Улица и улица 1987 , с. 133
^ Улица и улица 1987 , с. 135
^ ван Линт и Уилсон 1993 , стр.257

Ссылки

Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник по комбинаторным планам (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN 978-1-58488-506-1
Денес, Ж.; Кидуэлл, А.Д. (1974), Латинские квадраты и их приложения , Нью-Йорк-Лондон: Academic Press, стр. 547, ISBN 0-12-209350-Х , МР 0351850
Гарднер, Мартин (1966), Новые математические развлечения Мартина Гарднера от Scientific American , Fireside, ISBN 0-671-20913-2
Маккей, Брендан Д .; Мейнерт, Элисон; Мирволд, Венди (2007), «Маленькие латинские квадраты, квазигруппы и петли» (PDF) , Journal of Combinatorial Designs , 15 (2): 98–119, doi : 10.1002/jcd.20105 , S2CID 82321 |doi-broken-date =2020-10-03 | збл=1112.05018 | citeseerx=10.1.1.151.3043}}
Рагхаварао, Дамараджу (1988), Конструкции и комбинаторные проблемы планирования экспериментов (исправленное переиздание издания Wiley 1971 года), Нью-Йорк: Дувр
Рагхаварао, Дамараджу и Пэджетт, Л.В. (2005). Блочные конструкции: анализ, комбинаторика и приложения . Всемирная научная.
Стинсон, Дуглас Р. (2004), Комбинаторные расчеты / конструкции и анализ , Springer, ISBN 978-0-387-95487-5
Стрит, Энн Пенфолд ; Стрит, Дебора Дж. (1987), Комбинаторика экспериментального планирования , Oxford UP [Кларендон], ISBN 0-19-853256-3
ван Линт, Дж. Х.; Уилсон, Р.М. (1993), Курс комбинаторики , издательство Кембриджского университета, ISBN 978-0-521-42260-4

Внешние ссылки

Загадка 36 офицеров Леонарда Эйлера . Архив рубрик AMS (Латинские квадраты на практике и теории II)
Вайсштейн, Эрик В. «Проблема 36-го офицера» . Математический мир .
Работа Эйлера о латинских квадратах и квадратах Эйлера при сходимости
Инструмент Java, который помогает строить греко-латинские квадраты (он не строит их сам по себе) в кратчайшие сроки.
Всё, кроме квадратов: от магических квадратов до судоку
Исторические факты и корреляция с магическими квадратами, приложением Javascript для решения греко-латинских квадратов размером от 1x1 до 10x10 и соответствующим исходным кодом (Javascript в браузере Firefox и мобильных устройствах HTML5)
Грайм, Джеймс. «Квадраты Эйлера» (видео) . Ютуб . Брэйди Харан . Архивировано из оригинала 12 декабря 2021 г. Проверено 9 мая 2020 г.

[1] В литературе это использовалось под несколькими названиями: направляющая формула (Эйлера), направляющая , 1-перестановка и диагональ , среди других. ( Денес и Кидуэлл, 1974 , стр. 29)

[DK155-2] Перейти обратно: ^а ^б ^с Денес и Кидуэлл 1974 , с. 155

[3] Денес и Кидуэлл 1974 , с. 156

[4] Кнут, Дональд (2011), Искусство компьютерного программирования , том. 4A: Комбинаторные алгоритмы, часть 1, Аддисон-Уэсли, стр. xv+883pp, ISBN 978-0-201-03804-0 . Ошибки: [1]

[5] Озанам, Жак (1725), Занятия математикой и физикой , т. 1, с. IV, с. 434 , решение представлено на рис. 35

[Gardner-6] Перейти обратно: ^а ^б Гарднер 1966 , стр. 162-172.

[7] ван Линт и Уилсон 1993 , стр.251

[8] П. А. Мак-Магон (1902). «Магические квадраты и другие задачи на шахматной доске» . Труды Королевского института Великобритании . XVII : 50–63.

[9] Эйлер: Исследование нового вида магических квадратов , написанное в 1779 году , опубликованное в 1782 году.

[CD162-10] Перейти обратно: ^а ^б ^с ^д ^и ^ж Колборн и Диниц 2007 , с. 162

[11] Тарри, Гастон (1900). «Проблема 36 офицеров». Отчет Французской ассоциации содействия развитию науки . 1 . Секретариат Ассоциации: 122–123.

[12] Тарри, Гастон (1901). «Проблема 36 офицеров». Отчет Французской ассоциации содействия развитию науки . 2 . Секретариат Ассоциации: 170–203.

[13] ван Линт и Уилсон, 1993 , стр.267.

[14] Бозе, RC; Шриханде, С.С. (1959), «О ложности гипотезы Эйлера о несуществовании двух ортогональных латинских квадратов порядка 4 t + 2», Proceedings of the National Academy of Sciences USA , 45 (5): 734–737, Бибкод : 1959PNAS...45..734B , doi : 10.1073/пнас.45.5.734 , ПМК 222625 , ПМИД 16590435

[15] Бозе, RC; Шрикханде, СС; Паркер, ET (1960), «Дальнейшие результаты построения взаимно ортогональных латинских квадратов и ложность гипотезы Эйлера», Canadian Journal of Mathematics , 12 : 189–203, doi : 10.4153/CJM-1960-016-5 , MR 0122729

[36_entangled_officers-16] Перейти обратно: ^а ^б Скорее, Сухайль Ахмад; Бурхардт, Адам; Брузда, Войцех; Райхель-Миельдзёч, Гжегож; Лакшминараян, Арул; Жичковски, Кароль (2022), «Тридцать шесть запутанных офицеров Эйлера: квантовое решение классически невозможной проблемы», Physical Review Letters , 128 (8): 080507, arXiv : 2104.05122 , Bibcode : 2022PhRvL.128h0507R , doi : 10.1103/PhysRevLett.128.080507 , PMID 35275648 , S2CID 236950798

[17] Гойенече, Дардо; Раисси, Захра; Ди Мартино, Сара; Жичковски, Кароль (2018), «Запутывание и квантовые комбинаторные модели», Physical Review A , 97 (6): 062326, arXiv : 1708.05946 , Bibcode : 2018PhRvA..97f2326G , doi : 10.1103/PhysRevA.97.062326 , S2CID 51532085

[18] Гаристо, Дэн (2022), «243-летняя «невозможная» головоломка Эйлера получила квантовое решение» , журнал Quanta

[19] Паппас, Стефани (2022), «Вековая« невозможная »математическая задача решена с помощью странной физики кота Шредингера» , LiveScience

[CD160-20] Колборн и Диниц 2007 , с. 160

[21] Колборн и Диниц 2007 , с. 163

[22] Маккей, Мейнерт и Мирволд 2007 , стр. 98

[23] Денес и Кидуэлл 1974 , с. 159

[24] Денес и Кидуэлл 1974 , стр. 158.

[25] Термин «порядок», используемый здесь для MOLS, аффинных плоскостей и проективных плоскостей, определяется по-разному в каждой ситуации, но эти определения скоординированы таким образом, чтобы числовое значение было одинаковым.

[26] Брук, Р.Х.; Райзер, Х.Дж. (1949), «Несуществование некоторых конечных проективных плоскостей», Canadian Journal of Mathematics , 1 : 88–93, doi : 10.4153/cjm-1949-009-2 , S2CID 123440808

[27] Лам, CWH (1991), «Поиск конечной проективной плоскости порядка 10» , American Mathematical Monthly , 98 (4): 305–318, doi : 10.2307/2323798 , JSTOR 2323798

[28] Денес и Кидуэлл 1974 , с. 390

[29] Маккей, Мейнерт и Мирволд 2007 , стр. 102.

[30] Ленц, Х.; Юнгникель, Д.; Бет, Томас (ноябрь 1999 г.). Теория дизайна Томаса Бета . Кембриджское ядро. дои : 10.1017/cbo9781139507660 . ISBN 9780521772310 . Проверено 06 июля 2019 г.

[31] Денес и Кидуэлл 1974 , с. 167

[32] Денес и Кидуэлл 1974 , с. 169

[Stinson-33] Перейти обратно: ^а ^б Стинсон 2004 , с. 140

[34] Колборн и Диниц 2007 , с. 161

[35] Денес и Кидуэлл 1974 , с. 270

[36] Улица и улица 1987 , с. 133

[37] Улица и улица 1987 , с. 135

[38] ван Линт и Уилсон 1993 , стр.257

[ 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 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

v т и Планирование экспериментов
Научный метод	Научный эксперимент Статистический дизайн Контроль Внутренняя и внешняя валидность Экспериментальная установка Ослепление Оптимальный дизайн : байесовский Случайное задание Рандомизация Ограниченная рандомизация Репликация против субдискретизации Размер выборки
Уход и блокировка	Уход Размер эффекта Контраст Взаимодействие Сбивающий с толку Ортогональность Блокировка Ковариата Неприятная переменная
Модели и вывод	Линейная регрессия Обычные наименьшие квадраты Байесовский Случайный эффект Смешанная модель Иерархическая модель: Байесианская Дисперсионный анализ (Anova) Теорема Кокрена Манова ( многовариантная ) Анкова ( ковариация ) Сравнить означает Множественное сравнение
Дизайны Полностью рандомизированный	Факториал Дробный факториал Плакетт-Берман Тагучи Методология поверхности реагирования Полиномиальное и рациональное моделирование Бокс – Бенкен Центральный композит Блокировать Обобщенный рандомизированный блочный дизайн (GRBD) Латинская площадь Греко-латинская площадь Ортогональный массив Латинский гиперкуб Проектирование повторяющихся мер Перекрестное исследование Рандомизированное контролируемое исследование Последовательный анализ Последовательный тест отношения вероятностей
Глоссарий Категория Математический портал Статистическая схема Статистические темы