Латинские квадраты и конечные геометрии

Латинский квадрат — это квадратная таблица, в которой каждый символ встречается один раз в каждой строке и столбце, а конечные геометрии — это высокоструктурированные системы инцидентности на конечном числе точек и прямых.

Definition

Латинский квадрат порядка n — это таблица n на n, заполненная n символами таким образом, что каждый символ встречается ровно один раз в каждой строке и каждом столбце; конечная проективная плоскость — это структура инцидентности точек и прямых, в которой любые две точки лежат на одной уникальной прямой, и любые две прямые пересекаются в одной уникальной точке.

Scope

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

Core questions

• Сколько взаимно ортогональных латинских квадратов данного порядка может существовать?
• Для каких порядков существуют полные наборы ортогональных квадратов, а следовательно, и проективные плоскости?
• Как конечные поля конструируют плоскости и ортогональные квадраты?
• Какие аксиомы инцидентности определяют аффинные и проективные геометрии над конечными множествами?

Key concepts

• Латинский квадрат
• Взаимно ортогональные латинские квадраты
• Трансверсальные схемы и сети
• Конечная проективная плоскость
• Аффинная плоскость
• Поля Галуа (конечные поля)

Key theories

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

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

Опровержение гипотезы Эйлера

Эйлер предполагал, что не существует пары ортогональных латинских квадратов для порядков, сравнимых с 2 по модулю 4; Бозе, Шриханде и Паркер опровергли это в 1960 году для всех таких порядков, кроме 2 и 6.

Clinical relevance

Латинские квадраты обеспечивают экспериментальные планы типа «строка-столбец», которые одновременно контролируют два источника вариации, ортогональные массивы поддерживают факторные эксперименты и тестирование программного обеспечения, а конечные геометрии генерируют коды и схемы.

History

Эйлер изучал ортогональные латинские квадраты в 1782 году в рамках своей задачи о тридцати шести офицерах; его гипотеза оставалась в силе до опровержения в 1960 году Бозе, Шриханде и Паркером, так называемыми «разрушителями Эйлера».

Key figures

• Leonhard Euler
• R. C. Bose
• E. T. Parker

Seminal works

• colbourn2007

Frequently asked questions

Что означает ортогональность двух латинских квадратов?

Когда два квадрата накладываются друг на друга, каждая упорядоченная пара символов встречается ровно один раз, так что квадраты совместно различают каждую ячейку сетки.

Является ли сетка Судоку латинским квадратом?

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