Н. Макарова

 

 

ГРУППЫ ВЗАИМНО ОРТОГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ

 

Mutually Orthogonal Latin Squares (MOLS)

 

Часть III

 

Данная страница является продолжением страницы

http://www.natalimak1.narog.ru/grolk1.htm

 

 

В журнале “Discrete Mathematics 140 (1995) 291 - 294” есть статья (автор M. Wojtas), в которой даётся ссылка [1] на статью (автор A. E. Brouwer). В этой статье в 1979 году было опубликовано количество взаимно ортогональных латинских квадратов для порядков до 10000 включительно. После этого данная таблица значений много раз изменялась по мере того, как математики находили новые ортогональные латинские квадраты.

В предыдущей части настоящей статьи приведён фрагмент современной таблицы, найденной мной в Интернете. Эта таблица содержит максимальные количества взаимно ортогональных латинских квадратов для порядков от 2 до 499.

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

Здесь будет рассказано о группах MOLS для порядков от 21 до 30.

Покажу фрагмент указанной выше таблицы значений для данной группы порядков (рис. 1):

 

 

Рис. 1

 

Начну с порядка 21. Как видно из таблицы, максимальное количество MOLS данного порядка равно 5. Мне эта группа неизвестна.

Для данного порядка работает метод составных квадратов. Этим методом можно построить пару ОЛК.

Кроме того, я могу получить пару ОЛК 21-го порядка путём разложения на два ортогональных латинских квадрата какого-нибудь идеального магического квадрата данного порядка, построенного методом качелей, аналогично тому, как это было сделано для квадратов 15-го порядка.

Установлена определённая связь между методом качелей и методом латинских квадратов, что позволяет легко строить пару ОЛК для тех магических квадратов, которые строятся методом качелей. В статье http://www.natalimak1.narod.ru/kachlat.htm показано построение пары ОЛК 21-го порядка на основании этой связи двух методов. На рис. 2 вы видите первый латинский квадрат из этой пары (скопирован из указанной статьи).

 

 

Рис. 2

 

Второй латинский квадрат в этой паре ОЛК получается из первого отражением относительно горизонтальной оси симметрии, точно так же, как в случае с ортогональными латинскими квадратами 15-го порядка. Однако не исключено, что и здесь возможно другое построение второго латинского квадрата ортогонального первому, как это было совсем недавно установлено для квадратов 15-го порядка. Возможно, я ещё вернусь к этому вопросу.

 

Для порядка 22 легко построить пары ОЛК по известному алгоритму для серии порядков n = 10(mod 12). Этот алгоритм известен очень давно (см., например, книгу Д. Райзера “Комбинаторная математика”).

Группу из трёх MOLS 22-го порядка мне удалось найти в статье “Three mutually orthogonal idempotent Latin squares of orders 22 and 26” (R.J.R. Abel и другие). Эти квадраты были показаны мной в цикле статей “Новые аспекты метода латинских квадратов”. Кстати, судя по названию статьи, в ней говорится и о взаимно ортогональных квадратах 26-го порядка, однако эти квадраты не приводятся, возможно, рассказывается, как они строятся. Я не разбиралась в тексте статьи, а взяла из статьи готовые латинские квадраты 22-го порядка.

 

Для порядка 23 всё очень просто, так как этот порядок является простым числом. Группа MOLS данного порядка содержит 22 латинских квадрата. Все квадраты группы легко построить вручную. Можно сделать это и в пакете математических программ Maple [надо использовать команду MOLS(23,1,22)].

 

Порядок 24 относится к группе порядков, для которых работает метод составных квадратов, поэтому легко составить пару ОЛК данного порядка. Кроме того, я разработала алгоритм составления пары ОЛК для порядков серии n = 6k, k>1.  Порядок 24 относится к данной серии порядков.

В  статье http://www.natalimak1.narod.ru/aspekty6.htm показано построение пары ОЛК 24-го порядка с помощью этого алгоритма (см. рис. 23 - 24 в указанной статье). Не буду дублировать эту пару ОЛК.

Как видно из таблицы на рис. 1, Q(24) = 5, значит, найдена группа из пяти взаимно ортогональных латинских квадратов порядка 24. Мне неизвестна эта группа. О построении этой группы рассказывается в журнале “Discrete Mathematics 140 (1995) 291 - 294”, но я не разобралась в этом построении.

 

Порядок 25 очень хорош. Во-первых, для этого порядка работает метод составных квадратов. Во-вторых, этот порядок является степенью простого числа 5. Значит, для этого порядка группа MOLS полная и состоит из 24 квадратов. Эту группу можно построить в пакете Maple, применив команду MOLS(5,2,24). Наконец, порядок 25 нечётный и не кратен 3, поэтому латинские квадраты для данного порядка составляются так же, как для порядков, являющихся простым числом: с помощью циклического сдвига строк с постоянным шагом. При этом в первой строке каждого латинского квадрата группы стоит тождественная перестановка чисел 0, 1, 2, … 24. Покажу первые три квадрата группы (рис. 3 – 5) и последний квадрат (рис. 6). В квадрате № 3 раскраской показан циклический сдвиг строк.

 

Квадрат № 1

 

 

Рис. 3

 

Квадрат № 2

 

 

Рис. 4

 

Квадрат № 3

 

 

Рис. 5

 

Квадрат № 24

 

 

Рис. 6

 

В группе только два не диагональных латинских квадрата – квадрат № 1 и квадрат № 24. Все остальные квадраты диагональные.

 

Группа MOLS 26-го порядка, состоящая из четырёх квадратов, мне неизвестна. Для данного порядка у меня нет даже пары ОЛК. Этот порядок входит в серию порядков n = 2(mod 6), для которой я не знаю алгоритм составления пар ОЛК. К этой же серии порядков относятся порядки 14 и 20. Для порядка 20 я могу составить пары ОЛК методом составных квадратов, а вот порядок 14 тоже пока не имеет у меня даже пары ОЛК. Вся данная серия порядков – белое пятно.

 

Порядок 27 является степенью простого числа 3. Группа MOLS данного порядка полная и состоит из 26 латинских квадратов. Группу можно составить в пакете Maple, применив команду MOLS(3,3,26). Приведу здесь первые четыре квадрата из группы, полученной в Maple (рис. 7 – 10). Интересно отметить, что первые два квадрата группы составлены методом составных квадратов.

 

Квадрат № 1

 

 

Рис. 7

 

Квадрат № 2

 

 

Рис. 8

 

Квадрат № 3

 

 

Рис. 9

 

Квадрат № 4

 

 

Рис. 10

 

Предлагаю читателям проанализировать приведённые латинские квадраты и продолжить составление данной группы MOLS. Осталось построить 22 латинских квадрата. Если не получится самостоятельно, обратитесь к пакету Maple, в этом пакете вы сможете получить всю группу MOLS 27-го порядка, состоящую из 26 латинских квадратов. Кстати, пакет Maple не единственный пакет, умеющий составлять группы MOLS. На форуме указан ещё один пакет, кажется, GAVA (не помню точно название; смотрите тему “Магические квадраты” на форуме: http://dxdy.ru/topic12959.html ), который умеет составлять группы MOLS. Более того, в отличие от Maple, данный пакет может составлять пары ортогональных латинских квадратов порядков, не являющихся простым числом или степенью простого числа. Это такие порядки, для которых работает метод составных квадратов. Например, на форуме приведена пара ОЛК 20-го порядка, составленная в данном пакете.

 

Перехожу к порядку 28. Из таблицы на рис. 1 видно, что Q(28) = 5. Я могу составить группу из трёх взаимно ортогональных латинских квадратов 28-го порядка методом составных квадратов. Группа из пяти MOLS 28-го порядка мне неизвестна.

В статье http://www.natalimak1.narod.ru/aspekty5.htm показано составление пары диагональных ОЛК 28-го порядка методом составных квадратов.

Кроме того, порядок 28 относится к серии порядков n = 4(mod 6), для которой разработан алгоритм составления пар ОЛК. Продублирую пару ОЛК, построенную по этому алгоритму, из статьи http://www.natalimak1.narod.ru/aspekty4.htm (рис. 11 - 12).

 

Первый латинский квадрат 28-го порядка

 

 

Рис. 11

 

Второй латинский квадрат 28-го порядка

 

 

Рис. 12

 

Для порядка 29, как уже понимают читатели, всё просто, этот порядок является простым числом. Группа MOLS данного порядка полная и состоит из 28 латинских квадратов.

 

Наконец, последний порядок в рассматриваемой группе – 30. В таблице на рис. 1 видим, что Q(30) = 4. Эта группа мне неизвестна. Для данного порядка работает метод составных квадратов, с помощью которого можно легко составить пары ОЛК.

 

ЗАКЛЮЧЕНИЕ

 

В рассмотренной группе порядков от 21 до 30 абсолютное белое пятно – квадраты порядка 26. Для латинских квадратов этого порядка у меня нет даже пары ОЛК. Все неизвестные группы MOLS в рассмотренной группе порядков приведены ниже.

 

·        n = 21, группа MOLS из 5 квадратов;

·        n = 24, группа MOLS из 5 квадратов;

·        n = 26, группа MOLS из 4 квадратов;

·        n = 28, группа MOLS из 5 квадратов;

·        n = 30, группа MOLS из 4 квадратов.

 

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

 

Продолжение будет здесь:

 

http://www.natalimak1.narod.ru/grolk3.htm

 

 

4 – 5 февраля 2009 г.

г. Саратов

 

       Пишите мне!

Приглашаю всех на форум!

На главную страницу