Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В проекте Gerasim@Home (http://gerasim.boinc.ru) найден квадрат
6 1 9 10 3 4 0 8 5 7 2
9 7 2 1 0 3 4 5 10 8 6
1 10 6 3 9 0 8 4 7 2 5
7 5 10 8 4 2 9 3 6 1 0
3 4 1 0 8 5 2 10 9 6 7
10 9 4 7 1 8 6 2 0 5 3
5 8 3 6 2 10 1 7 4 0 9
4 2 0 5 6 7 10 9 8 3 1
8 3 5 2 10 6 7 0 1 9 4
2 0 8 9 7 1 5 6 3 4 10
А во время соревнования сервер успешно справлялся ли с нагрузкой?
ДЛК порядка 11
0 1 2 3 4 5 6 7 8 9 10
1 2 3 5 6 9 7 10 0 4 8
7 10 8 0 3 1 5 9 6 2 4
3 5 9 4 10 6 8 0 2 7 1
4 6 7 10 1 8 2 3 9 0 5
5 9 4 6 8 7 0 1 3 10 2
10 8 0 1 5 2 9 4 7 3 6
6 7 10 8 2 0 3 5 4 1 9
8 0 1 2 9 3 4 6 10 5 7
2 3 5 9 7 4 10 8 1 6 0
9 4 6 7 0 10 1 2 5 8 3
который на данный момент держит рекорд по числу диагональных трансверсалей (4828) и трансверсалей общего вида (37851) и является изоморфным одному из циклических квадратов данной размерности 11, имеет еще одну интересную особенность: он входит в состав главного класса мощностью 3072. Прежде всего, это позволяет установить верхнее ограничение на минимальную мощность: a(11) <= 3072 в ряду https://oeis.org/A299783, но не это самое интересное. Интересно другое: данное значение 3072 = 15360 / 5. Т.е. мощность соответствующего главного класса в 5 раз меньше максимально возможной для данной размерности! До этого все нижние оценки (и соответствующие им ДЛК и главные классы) имели мощность, которая меньше максимальной в 2^m раз, т.к. каждая обобщенная M-симметрия уменьшала мощность в 2 раза, если у квадрата m обобщенных M-симметрий, значит мощность уменьшалась в 2*2*...*2 (m раз) = 2^m раз, а тут уменьшение в 5 раз. Весьма интересный и неожиданный результат, над теоретическим объяснением которого надо будет поломать голову на досуге... Есть ли у данного квадрата обобщенные симметрии? Данный вопрос пока открыт... Он ESODLS по нескольким CMS схемам, а вот симметрии...
PS. Аналогичная особенность есть у размерности N=7: максимальная мощность 192, минимальная — 32, 192 / 32 = 6, не степень двойки; и у размерности N=6: 96 / 32 = 3... Для других известных размерностей:
A299783(n) = A299784(n) для 1 <= n <= 5
A299783(6)*3 = A299784(6)
A299783(7)*6 = A299784(7)
A299783(8)*16 = A299784(8)
A299783(9)*32 = A299784(9)
A299783(10)*2 = A299784(10)
A299783(11)*5 = A299784(11)
О соотношении максимальной мощности клик и максимального числа ОДЛК к одному ДЛК
Допустим, для некоторой размерности ДЛК N существует клика мощности X (в примере на рисунке — мощности 6), в которую входит квадрат A. Клика образована 6-ю квадратами A, B1, B2, B3, B4 и B5, каждый из которых имеет как минимум X-1 ОДЛК (в примере — 5 ОДЛК B1, B2, ..., B5). Соответственно, для числовых рядов можно сказать, что если максимальная мощность клики A328873(N) = X, то максимальное число ОДЛК A287695(N) >= X-1. Квадрат A может иметь и другие ОДЛК (на рисунке — C1 и C2), именно поэтому максимальное число ОДЛК >= X-1 (в примере — 7, т.е. >= 5). Указанное свойство позволяет установить следующее неравенство между парой числовых рядов:
A328873(N)-1 <= A287695(N)
Что мы знаем о мощности клик из ДЛК и максимального числа ОДЛК на данный момент:
N | Клики (A328873) | ОДЛК (A287695)
1 | 1 | 1
2 | 0 | 0
3 | 0 | 0
4 | 2 | 1
5 | 2 | 1
6 | 1 | 0
7 | 4 | 3
8 | 6 | 824
9 | 6 | 614
10 | >=2 | >=10
11 | >=8 | >=32462
12 | >=2 | ?
13 | >=10 | ?
14 | >=2 | ?
15 | >=4 | ?
16 | >=14 | ?
17 | >=14 | ?
18 | >=2 | ?
19 | >=16 | ?
20 | >=2 | ?
Для максимального числа ОДЛК порядков N>11 информация в OEIS на данный момент не отражена. Соответственно можно сказать, что в ряду A287695
a(12) >= 1
a(13) >= 9
a(14) >= 1
a(15) >= 3
a(16) >= 13
a(17) >= 13
a(18) >= 1
a(19) >= 15
a(20) >= 1
Эмпирический факт: для всех циклических ДЛК порядка N=11 мощность соответствующих им главных классов равна 1536. Это позволяет сделать вывод о том, что все они обладают обобщенными симметриями, причем несколькими одновременно. Кроме того, в ряду https://oeis.org/A299783 верхнее ограничение на нижнее значение члена a(11) усилено с текущего известного a(11)<=3072 до a(11)<=1536. Пример квадрата ниже:
0 1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 0 1
4 5 6 7 8 9 10 0 1 2 3
6 7 8 9 10 0 1 2 3 4 5
8 9 10 0 1 2 3 4 5 6 7
10 0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 0
3 4 5 6 7 8 9 10 0 1 2
5 6 7 8 9 10 0 1 2 3 4
7 8 9 10 0 1 2 3 4 5 6
9 10 0 1 2 3 4 5 6 7 8
Интересно, а что будет для циклических ДЛК других размерностей...
О минимальной и максимальной мощности главных классов циклических ДЛК порядков 1-16
Циклические ДЛК существуют для некоторых размерностей, оценим мощности соответствующих им главных классов.
N=5, единственная КФ
0 1 2 3 4
2 3 4 0 1
4 0 1 2 3
1 2 3 4 0
3 4 0 1 2
Главный класс мощности 4, мощность равна минимально возможной для данного порядка (см. https://oeis.org/A299783).
N=7, единственная КФ
0 1 2 3 4 5 6
2 3 1 5 6 4 0
5 6 4 0 1 2 3
4 0 6 2 3 1 5
6 2 0 1 5 3 4
1 5 3 4 0 6 2
3 4 5 6 2 0 1
Главный класс мощности 32, мощность минимально возможная
N=11, 2 КФ, мощность главных классов совпадает (см. https://vk.com/wall162891802_1577) и равна 1536, минимальное известное на данный момент значение.
0 1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 0 1
4 5 6 7 8 9 10 0 1 2 3
6 7 8 9 10 0 1 2 3 4 5
8 9 10 0 1 2 3 4 5 6 7
10 0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 0
3 4 5 6 7 8 9 10 0 1 2
5 6 7 8 9 10 0 1 2 3 4
7 8 9 10 0 1 2 3 4 5 6
9 10 0 1 2 3 4 5 6 7 8
А вот для N=13 для разных КФ получаются различные мощности главных классов (время оценки ~ 1 минута в 1 поток на Core i7 4770).
0 1 2 3 4 5 6 7 8 9 10 11 12
2 3 1 4 5 6 7 8 9 11 12 10 0
7 9 8 11 10 12 0 2 1 3 5 4 6
8 11 9 10 12 0 2 1 3 4 6 5 7
1 4 3 5 6 7 8 9 11 10 0 12 2
9 10 11 12 0 2 1 3 4 5 7 6 8
3 5 4 6 7 8 9 11 10 12 2 0 1
11 12 10 0 2 1 3 4 5 6 8 7 9
4 6 5 7 8 9 11 10 12 0 1 2 3
10 0 12 2 1 3 4 5 6 7 9 8 11
12 2 0 1 3 4 5 6 7 8 11 9 10
5 7 6 8 9 11 10 12 0 2 3 1 4
6 8 7 9 11 10 12 0 2 1 4 3 5
15360 ДЛК
0 1 2 3 4 5 6 7 8 9 10 11 12
2 3 4 6 5 7 9 8 10 11 12 0 1
8 0 10 2 12 1 4 3 6 5 9 7 11
10 2 12 4 1 3 5 6 9 7 11 8 0
6 8 9 10 11 0 12 2 4 1 5 3 7
4 6 5 9 7 8 11 10 12 0 1 2 3
9 10 11 12 0 2 1 4 5 3 7 6 8
12 4 1 5 3 6 7 9 11 8 0 10 2
11 12 0 1 2 4 3 5 7 6 8 9 10
5 9 7 11 8 10 0 12 1 2 3 4 6
7 11 8 0 10 12 2 1 3 4 6 5 9
1 5 3 7 6 9 8 11 0 10 2 12 4
3 7 6 8 9 11 10 0 2 12 4 1 5
7680 ДЛК
Для следующей размерности N=17 без использования параллельной вычислительной системы оценку выполнить затруднительно.
Таким образом, установлено новое верхнее ограничение на минимальное значение мощности главного класса для N=13: A299783(13) <= 7680.
Кроме того, получены 2 новых числовых ряда для минимальной и максимальной мощностей главных классов циклических ДЛК, не представленные в OEIS:
* 1, 0, 0, 0, 4, 0, 32, 0, 0, 0, 1536, 0, 7680, 0, 0, 0;
* 1, 0, 0, 0, 4, 0, 32, 0, 0, 0, 1536, 0, 15360, 0, 0, 0.
Или, что то же самое, без нулей на четных позициях:
* 1, 0, 4, 32, 0, 1536, 7680, 0;
* 1, 0, 4, 32, 0, 1536, 15360, 0.
Опять однодневки 
В тестовом подпроекте проекта Gerasim@Home (http://gerasim.boinc.ru) завершен большой эксперимент длительностью более 3 лет, направленный на поиск ОДЛК в окрестностях обобщенных симметрий. Напомню краткую историю исследования вопроса...
1. Сначала поиск ОДЛК порядка 10 проводился просто для фактически случайных ДЛК, его результатом стало нахождение однушек и затем — двушек с низкими характеристиками ортогональности (сокр. ХО, обычно 12, реже 16, еще реже все остальное).
2. Затем группа заинтересованных лиц, в которую я влился в процессе :), обратила внимание на наличие симметрии в ДЛК (которую мы теперь называем плоскостной). Ее начал выбирать citerra, а закончили мы совместно в Gerasim'е (сперва для случайного поиска, а уже потом для полного перебора). В ходе анализа находок оказалось, что они включают в своем составе большое количество интересных комбинаторных структур: четверки, шестерки и восьмерки и пр. (см. http://evatutin.narod.ru/evatutin_co_dls_comb_structs.pdf). Кроме того, в ходе анализа данной симметрии citerra'ой была найдена, а затем мной — перенайдена, псевдотройка с рекордной ХО 74 (квадраты были найдены разные, однако позже удалось показать, что они изоморфны друг другу). Лучше для данного типа квадратов найти не удалось ни в плане комбинаторных структур, ни в плане ХО, но сам подход на базе симметрий показал свою эффективность.
3. Далее, исходя из геометрических аналогий, оказалось, что кроме симметрии относительно прямой еще может существовать симметрия относительно точки (теперь мы называем ее центральной точечной (может быть еще смещенная точечная при повороте квадрата на торе) или просто центральной). Для интересующей нас размерности N=10 она с большой долей вероятности не существует, как и для всех порядков N=4k+2, поэтому ОДЛК от нее найдено не было (хотя они существуют для других порядков N).
4. Далее было построено обобщенное математическое описание симметрий в виде формул вида
x' = f(x, y) = Ax + By + C (mod N)
y' = g(x, y) = Ax + By + C (mod N)
(A, B, C — некоторые целочисленные коэффициенты), с использованием которых удалось найти еще несколько симметрий, получивших название обобщенных, и соответствующих им ОДЛК. В свое время они именовались с использованием обозначений вроде "+-"-симметрия или, позже, через коды вроде (15)-симметрия (см. http://evatutin.narod.ru/evatutin_dls_gen_symms.pdf). В настоящее время данные обозначения утратили свой первоначальный смысл ввиду того, что появилось обобщение обобщенных симметрий :), о нем ниже.
5. В упомянутой выше статье было показано, что приведенные выше формулы для функций f и g могут быть записаны с использованием перестановок P. Далее к работе подключился whitefox и показал, что при задании соответствий в виде
x' = Px[x]
y' = Py[y]
v' = Pv[v]
существенную роль играют не столько сами перестановки, сколько их структура циклов. Для порядка N=10 существует 42 различных мультимножества длин циклов перестановок (что, кстати, совпадает с числом разбиений числа 10 на целочисленные слагаемые, см. https://oeis.org/A000041), что дает 903 комбинации обобщенных симметрий. Не все (и, как показал завершенный эксперимент, далеко не все) из них существуют, однако те, которые существуют, дают интересные редкие комбинаторные структуры (2-КФные двушки и пр.). Теоретически существование некоторых комбинаций обобщенных симметрий порядка N=10 доказал whitefox, однако к великому сожалению его теоретические построения утеряны в результате известного конфликта между НИИСИ и ИППИ и пропажи части оборудования, на котором хранился форум... На данный момент существует призрачная надежда на их восстановление...
6. Однако часть теоретических построений можно независимо подтвердить в эксперименте с окрестностями обобщенных симметрий. В нем с использованием соответствующего генератора ДЛК производилось построение частично обобщенно симметричных квадратов, у которых M ячеек удовлетворяют формулам с использованием перестановок, а остальные достраиваются произвольным образом до получения корректных ДЛК. Первые результаты эксперимента дали множество новых комбинаторных структур (см. http://ceur-ws.org/Vol-2267/282-287-paper-53.pdf), в состав которых входят в том числе ДЛК с рекордным числом ОДЛК, равным 10 (таковых известно два в составе двух различных комбинаторных структур). Для больших M (70 и выше) сразу стало ясно, что там, где существуют интересные обобщенные симметрии с большим числом интересных ОДЛК, в ходе разведки находится большое число двушек, число которых стало некоторым ориентиром, признаком интересности окрестности. В окрестностях обобщенных симметрий, в дополнение к полностью симметричным ДЛК, неоднократно попадались интересные структуры и псевдотройки с высоким значением ХО (не путать с известным коньяком 
для ДЛК, обладающих симметрией лишь частично. В итоге по результатам эксперимента попалось несколько основных точек, давших основную массу интересных ОДЛК, соответствующих им комбинаторных структур и псевдотроек в их составе:
(1,16) — в ходе разведки найдено 1357 двушек, типичное значение для неинтересной окрестности отсутствующей симметрии — 10-30 двушек при тех же условиях исследования окрестности.
(1,31) — 2386 двушек.
(1,41) — 800 двушек. Сама симметрия не существует, а интересные находки в ее окрестности есть! В свое время был интересный диспут с whitefox'ом о том, как может существовать окрестность у того, чего нет... :). Оказывается еще как может и определяется блочной структурой квадрата (2 больших блока, но по 5, или 5 маленьких блоков, но по 2, почти как известная история про раков у А. Райкина :).
(4,31) — 2995 двушек.
Они были исследованы очень тщательно (более 1,5 млн. WU'шек на каждую для различных удалений M) и на данный момент можно утверждать, что все интересное из них выбрано с высокой долей вероятности.
В окрестностях некоторых существующих обобщенных симметрий принципиально интересного найдено не было: есть обобщеная симметрия и на этом все. Примеры таковых симметрий:
(1,42) — 14 двушек.
(2,31) — 25 двушек.
(2,42) — ...
(4,42)
(7,7)
(7,41)
(7,42)
(8,8)
(8,31)
(8,42)
(10,10)
(10,34)
(11,11)
(11,34)
(13,42)
(15,15)
(16,16)
(16,31)
(16,42)
(17,36)
(18,34)
(19,19)
(19,34)
(21,21)
(21,36)
(22,22)
(22,37)
(24,42)
(27,27) — 18 двушек, попались несколько SODLS.
(28,28)
(30,30)
(31,41)
(31,42)
(32,36)
(33,34)
(34,34)
(36,36)
(37,37)
(41,41)
(41,42)
(42,42)
Они были обработаны в первую очередь по просьбе whitefox'а, но принципиально интересного в них найдено не было (за редкими исключениями).
Ну и наконец в составе некоторых окрестностей несуществующих симметрий попались трешки, четверки, линии-4 и циклы-4 — редкие структуры. Примеры ниже:
(6,6) — линия-4.
(12,42) — четверка.
(8,21) — трешка.
Однако более подробный поиск в данных окрестностях больше ничего не интересного не принес. На данный момент есть подозрение, что эти структуры попались просто случайно и не являются каким-либо следствием свойств конкретной окрестности. Чтобы его проверить, далее в тестовом подпроекте запущен и какое-то время будет продолжать случайный поиск по линейкам, чтобы подтвердить либо опровергнуть предположение.
Ну и в заключении о перспективах дальнейших поисков. Искать можно как минимум по нескольким направлениям.
1. Случайный поиск без учета особенностей ДЛК — какое-то время будет его выполнять и смотреть за результатами...
2. Поиск в окрестностях обобщенных симметрий в парастрофических срезах — сейчас выполняется разведка в 3-м срезе на малом удалении от симметрии, основной подпроект, короткие WU'шки для несуществующих симметрий, длинные для существующих.
3. Поиск по схемам соответствия ячеек CMS. То, что было можно выбрать с небольшими затратами вычислительного времени, уже давно выбрано и образует новый тип квадратов, именуемый ESODLS (см. https://oeis.org/A309598). Далее нужно прощупывать разные схемы и искать в них редкие решения. Для этого требуется серьезная оптимизация расчетного кода по образцу генераторов ДЛК на базе вариации порядка заполнения ячеек, вложенных циклов и битовой арифметики, либо другие подходы (например, SAT, что мы с коллегами из Иркутска уже обсуждали и даже кое-что уже пробовали).
Кроме этого с ДЛК и ЛК связан ряд открытых вопросов по части их подсчета и получения новых членов числовых рядов, чем мы тоже планируем заниматься по мере наличия сил и времени. Большой эксперимент завершен, но поиск продолжается...
Эксперимент по исследованию быстровычислимых числовых характеристик ДЛК порядка 11 завершен. До начала эксперимента было известно, что
2991 <= Число трансверсалей <= 37851
279 <= Число диагональных трансверсалей <= 4828
0 <= Число нормализованных ОДЛК <= 32462
0 <= Число интеркалятов <= 94
В ходе эксперимента удалось усилить лишь верхнюю границу минимального числа трансверсалей в ДЛК (с 2991 до 2570)
2570 <= Число трансверсалей <= 37851
279 <= Число диагональных трансверсалей <= 4828
0 <= Число нормализованных ОДЛК <= 32462
0 <= Число интеркалятов <= 94
Всего было проанализировано 16 млрд. ДЛК. Побочным следствием эксперимента являются списки из ~ 5 млн. КФ ОДЛК (на самом деле ОДЛК было найдено больше, но с некоторого момента однушки стали отсеиваться). В настоящий момент производится классификация образуемых ими комбинаторных структур, на что потребуется еще минимум неделя (процесс долгий), пока найдено более 90 различных структур, некоторые из них уже попадались для других размерностей, некоторые являются новыми. Самая большая из них включает в своем составе 28935 КФ ОДЛК и 190112 псевдоребер (ее классификация по сокращенной схеме через КФы заняла 10 часов, построение полного списка ДЛК в ее составе и подсчет количества связей потребует как минимум на 2 порядка больших временнЫх затрат и на данный момент видится нецелесообразным, поэтому из числовых характеристик только число КФов и псевдоребер). Центральная симметрия пересеклась с xSODLS только в этой структуре, в других такого не выявлено. Это, с одной стороны, объясняет относительно малый размер найденных структур, а с другой определяет направления для дальнейшего исследования размерности N=11 (типы ДЛК), к чему мы вернемся позже. Впереди эксперимент для размерности N=12 с тем же генератором...