Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
7-месячный отчет о результатах поиска КФ ОДЛК порядка 10 в проекте RakeSearch
Итак, с момента прошлого отчета (декабрь 2022) в проекте найдено чуть более чем 1,2 млн. КФ ОДЛК порядка 10, общее количество — немногим более 21 200 000. Среди наиболее интересных находок:
ONCE (A):1 - 571412, where:
2 CFs - 571412
LINE3 (B):1 - 116979, where:
2 CFs - 18735
3 CFs - 98244 (+6270)
LINE3 (B):2 - 67857, 8:1, where:
2 CFs - 18735
3 CFs - 49122 (+3135)
LINE4 (C):1 - 206, where:
2 CFs - 4
4 CFs - 202 (+8)
LINE4 (C):2 - 206, where:
2 CFs - 4
4 CFs - 202 (+8)
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2300, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 696 (+8)
1TO3 (F):1 - 504, where:
4 CFs - 504 (+18)
1TO3 (F):3 - 168, where:
4 CFs - 168 (+6)
1TO4 (G):1 - 1398, where:
3 CFs - 882
5 CFs - 516 (+8)
1TO4 (G):4 - 570, where:
3 CFs - 441
5 CFs - 129 (+2)
1TO5 (k):1 - 10, where:
6 CFs - 10
1TO5 (k):5 - 2, where:
6 CFs - 2
1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18
1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3
1TO7 (h):1 - 7, where:
8 CFs - 7
1TO7 (h):7 - 1, where:
8 CFs - 1
1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16
1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2
RHOMBUS3 (J):2 - 9, where:
5 CFs - 9
RHOMBUS3 (J):3 - 6, where:
5 CFs - 6
RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16
RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8
FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6
FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9
FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3
TREE1 (V):1 - 2, where:
4 CFs - 2
TREE1 (V):2 - 1, where:
4 CFs - 1
TREE1 (V):3 - 1, where:
4 CFs - 1
CROSS (X):1 - 16, where:
6 CFs - 16
CROSS (X):2 - 4, where:
6 CFs - 4
CROSS (X):4 - 4, where:
6 CFs - 4
DAEDALUS10 (i):1 - 6, where:
12 CFs - 6
DAEDALUS10 (i):2 - 4, where:
12 CFs - 4
DAEDALUS10 (i):4 - 1, where:
12 CFs - 1
DAEDALUS10 (i):10 - 1, where:
12 CFs - 1
FLYER (j):1 - 2, where:
8 CFs - 2
FLYER (j):2 - 3, where:
8 CFs - 3
FLYER (j):4 - 3, where:
8 CFs - 3
VENUS (l):1 - 1, where:
5 CFs - 1
VENUS (l):2 - 3, where:
5 CFs - 3
VENUS (l):4 - 1, where:
5 CFs - 1
DAEDALUS8 (m):1 - 2, where:
6 CFs - 2
DAEDALUS8 (m):2 - 2, where:
6 CFs - 2
DAEDALUS8 (m):4 - 1, where:
6 CFs - 1
DAEDALUS8 (m):8 - 1, where:
6 CFs - 1
RHOMBUS5 (n):2 - 4, where:
5 CFs - 4
RHOMBUS5 (n):5 - 1, where:
5 CFs - 1
1TO10 (o):1 - 5, where:
6 CFs - 5
1TO10 (o):10 - 1, where:
6 CFs - 1
ROBOT (p):1 - 4, where:
5 CFs - 4
ROBOT (p):2 - 4, where:
5 CFs - 4
ROBOT (p):4 - 2, where:
5 CFs - 2
STINGRAY (q):1 - 3, where:
5 CFs - 3 (+2)
STINGRAY (q):2 - 9, where:
5 CFs - 9 (+6)
STINGRAY (q):3 - 3, where:
5 CFs - 3 (+2)
Эксперимент по исследованию свойств окрестностей обобщенных симметрий:
* парастрофические срезы 1, 2 и 3: обработка завершена;
* парастрофический срез 4: пройдено 252 окрестности из 1764 (14,2%).
Установлены новые ограничения на мощности, супремумы и инфимумы спектров числа трансверсалей, диагональных трансверсалей, интеркалятов и ОДЛК в ДЛК порядков 11-13, в настоящее время производится обработка порядка 14.
Для построенного ранее спектра числа диагональных трансверсалей в ДЛК порядка 14 в проекте RakeSearch завершено расширение путем вращения 1 цикла. На моей машине в однопоточном режиме для этого потребовалось бы более недели, тут мы уложились менее чем за сутки (считая чистое время счета без подготовки и хвостов). В результате получен спектр со следующими параметрами:
Min value = 46513, max value = 57980, width = 11468, cardinality = 9928, density = 0.87
Опорный спектр незначительно расширился (+20 элементов), новых элементов в интегральный спектр это не принесло.
Второй короткий запуск вычислительного эксперимента, направленный на выяснение вычислительной сложности WU'шек для распределенной диагонализации ДЛК порядка 14, успешно завершен, время счета редко превышает 1 час, что приемлимо. А раз так, то можно переходить к боевым запускам. В рамках первого их них попробуем продиагонализировать топовый по числу трансверсалей (как диагональных, так и общего вида) ДЛК в составе соответствующих спектров. У данного эксперимента две основные цели: наполнение старшей части спектра числа диагональных трансверсалей и попытка усилить нижнее ограничение на член a(14) числового ряда A287648 в OEIS. В настоящее время производится генерация WU'шек (только для одного этого квадрата их будет чуть более чем 180 тысяч!), в ближайшее время они будут запущены в проекте RakeSearch.
В проекте RakeSearch завершен короткий недельный эксперимент, целью которого являлась диагонализация топового известного ДЛК порядка 14 (по числу диагональных трансверсалей и трансверсалей общего вида). Ранее (чуть более чем полтора года назад) данный ДЛК был продиагонализирован лишь частично ввиду того, что тогда еще не был написан код для распределенной диагонализации, теперь же с использованием нового расчетника удалось произвести полную диагонализацию данного ДЛК. Для этого было сформировано чуть более чем 180 тыс. WU'шек со средним временем счета порядка 10 минут (единичные экземпляры с большим числом подходящих пар трансверсалей считались у меня более часа), они были обсчитаны в проекте (параллельно работали еще 2 подпроекта, данному подпроекту досталась лишь часть реальной производительности), постобработаны (для этого пришлось обработать около 8 ГБ результирующих данных), в результате получен спектр со следующими параметрами:
Min value = 431424, max value = 490218, width = 58795, cardinality = 10840, density = 0.18
Как и ожидалось, элементы спектра достаточно компактно расположились в его старшей части, что было ожидаемо и уже наблюдалось ранее, например, для аналогичного топового ДЛК порядка 12 (который, кстати, тоже является квадратом Брауна). Объединяя полученный спектр с уже известным на данный момент, получаем расширение мощности интегрального спектра с 283381 до 292124 элементов. В составе новых элементов спектра присутствует ДЛК
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 0 13 7 8 9 10 11 12
2 3 4 5 6 0 1 12 13 7 8 9 10 11
8 7 13 12 11 10 9 4 3 2 1 0 6 5
10 4 5 6 13 1 2 11 12 0 7 8 9 3
9 8 7 13 12 11 10 3 2 1 0 6 5 4
7 13 12 11 3 9 8 5 4 10 2 1 0 6
5 6 0 1 2 3 4 9 10 11 12 13 7 8
12 11 10 9 8 7 13 0 6 5 4 3 2 1
6 0 1 2 10 4 5 8 9 3 11 12 13 7
11 10 9 8 7 13 12 1 0 6 5 4 3 2
4 5 6 0 1 2 3 10 11 12 13 7 8 9
13 12 11 10 9 8 7 6 5 4 3 2 1 0
3 9 8 7 0 12 11 2 1 13 6 5 4 10
у которого 490218 диагональных трансверсалей, что позволяет усилить известное нижнее ограничение с a(14)>=488792 до a(14)>=490218 в числовом ряду https://oeis.org/A287648. В очередной раз диагонализация показывает себя с лучшей стороны в задаче построения аппроксимаций спектров числа диагональных трансверсалей в ДЛК!
В проекте RakeSearch завершен короткий вычислительный эксперимент, целью которого являлось получение полного списка КФ диагонализированных циклических ДЛК порядка 13. Расчет занял около 2 суток (включая хвосты). В результате постобработки полученных результатов найдено 2933 главных класса диагонализированных циклических ДЛК порядка 13, что позволяет расширить один из числовых рядов (который пока не только не добавлен в OEIS, но еще и толком не анонсирован :). По данному списку КФ произведено построение спектра числа диагональных трансверсалей, в результате чего получен спектр со следующими параметрами:
Min value = 127339, max value = 131106, width = 3768, cardinality = 1001, density = 0.27
Найденная мощность спектра (1001), минимальное (127339) и максимальное (131106) значения опять таки являются членами соответствующих числовых рядов. Благодаря данному спектру возможно теоретически объяснить, из ДЛК какого типа состоит полоска в старшей части спектра числа диагональных трансверсалей в ДЛК порядка 13 (см. верхнюю правую и нижнюю правую картинки во вложении). То же самое справедливо и для спектров нечетных порядков, не кратных 3 (N \in {5, 7, 11, 13}), что наблюдаемо невооруженным глазом на картинке во вложении.
Для проекта RakeSearch разработана новая версия расчетного модуля и 2933 WU'шки к ней с целью запуска нового небольшого вычислительного эксперимента, целью которого является подсчет суммы мощностей главных классов для только что найденных КФ диагонализированных циклических ДЛК. По итогам данного эксперимента нам будут известны еще два числовых значения, являющиеся членами соответствующих числовых рядов. Время счета около 16 минут на Core i7 4770, кворум 2, считаем сразу после добавления в проект, что hoarfrost обещает сделать достаточно оперативно... 
У нас набралось достаточно данных для первых попыток анализа того, как устроены спектры числовых характеристик ДЛК на примере спектров числа диагональных трансверсалей. Для некоторых из них отчетливо видна "полосатая" структура, причем ДЛК, группирующиеся в полосы, скорее всего не случайны и имеют какой-то особый тип. Для некоторых порядков (обычно малых) эти полосы могут сливаться, для других наоборот отстоять друг от друга, но в общем и целом картина не меняется.
Анализируя спектры визуально, несложно заметить, что свойства спектров отличаются для четных и нечетных порядков. Это в общем-то понятно, т.к., например, для четных порядков существуют плоскостно-симметричные ДЛК, а для нечетных — циклические ДЛК; для некоторых порядков существуют центрально-симметричные ДЛК и т.д. Анализ начнем с циклических ДЛК и квадратов, которые получаются из них путем незначительных манипуляций с известными преобразованиями.
Известно, что циклические ЛК существуют для всех нечетных порядков. Для ДЛК к этому добавляется дополнительное условие, что порядок еще и не должен быть кратен трем (см. числовые ряды https://oeis.org/A123565 и https://oeis.org/draft/A007310 в OEIS). Или, что то же самое, порядок N должен давать 1 или 5 в остатке при делении на 6 (почему так, отдельный интересный вопрос). Соответственно, для порядков N, где циклические ДЛК существуют, они являются лидерами как по числу трансверсалей (оно совпадает для всех циклических ДЛК), так и по числу диагональных трансверсалей (в данном случае лидером является один из квадратов для одного из смещений d, остальные так же имеют много трансверсалей, но все же меньше лидера). А раз так, то данный тип квадратов можно поисследовать более внимательно, и при этом оказывается, что им соответствует как минимум 3 числовых ряда, посчитанные нами ранее:
* https://oeis.org/A342998
* https://oeis.org/A342997
* https://oeis.org/A341585
Переставляя строки циклического ДЛК всеми возможными способами, можно получить другой известный тип квадратов, именуемый полуциклическими ДЛК (см. https://oeis.org/A071607). Для них так же можно построить числовые ряды, связанные с числом диагональных трансверсалей:
* 1, 0, 1, 1, 0, 2, 20, 0 — мощность спектра числа диагональных трансверсалей в полуциклических ДЛК
* 1, 0, 5, 27, 0, 4523, 127339, 0 — минимальное число диагональных трансверсалей в полуциклических ДЛК
* 1, 0, 5, 27, 0, 4665, 131106, 0 — максимальное число диагональных трансверсалей в полуциклических ДЛК
Первые два ряда являются новыми и не представлены в OEIS, последний совпадает с максимальным числом диагональных трансверсалей в циклических ДЛК ввиду того, что формально циклические ДЛК по(д?)падают под определение полуциклических.
Известно, что все циклические и полуциклические ДЛК являются пандиагональными (обратное утверждение в общем случае не верно). А раз так, то полуциклические ДЛК можно повертеть на углы, кратные 45 градусам, с целью получения нового множества квадратов, которые будем именовать как повернутые полуциклические ДЛК. Перечисление их количества приводит к получения трех новых числовых рядов, не представленных в OEIS:
* 1, 0, 240, 20160, 0, 319334400, 8481202329600, 0, 11759737747709952000, 21006649099400380416000 — число повернутых полуциклических диагональных латинских квадратов порядка N=2n+1
* 1, 0, 2, 4, 0, 8, 1362, 0, 33062, 172688, 0 — число повернутых полуциклических диагональных латинских квадратов порядка N=2n+1 с фиксированной первой строкой
* 1, 0, 1, 1, 0, 2, 38, 0 — число главных классов повернутых полуциклических диагональных латинских квадратов порядка N=2n+1
Для числа диагональных трансверсалей в повернутых полуциклических ДЛК получаются следующие числовые ряды:
* 1, 0, 5, 27, 0, 4523, 8795, 0 — минимальное число диагональных трансверсалей в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
* 1, 0, 5, 27, 0, 4665, 131106, 0 — максимальное число диагональных трансверсалей в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
Первый числовой ряд является новым, второй совпадает с максимальным числом диагональных трансверсалей в циклических ДЛК по той же причине, что и для полуциклических ДЛК. Визуальный анализ спектра показывает, что значения расположены в двух "полосах": одной из них (старшей) соответствуют повороты полуциклических ДЛК на углы 90*k градусов (при этом свойство полуцикличности сохраняется, т.к. оно инвариантно этому преобразованию), другой (младшей) — повороты на углы 45 + 90*k (см. рис. во вложении, данный тип отмечен красным эллипсом). Для квадратов из "младшей полосы" число трансверсалей общего вида отлично от аналогичного для циклических ДЛК, что позволяет получить еще несколько числовых рядов:
* 1, 0, 1, 1, 0, 1, 6, 0 — мощность спектра числа трансверсалей в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
* 1, 0, 15, 133, 0, 37851, 81926, 0 — минимальное число трансверсалей в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
* 1, 0, 15, 133, 0, 37851, 1030367, 0 — максимальное число трансверсалей в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
Нижний ряд нам уже известен по циклическим ЛК, а вот верхние два являются новыми и не представлены в OEIS. В повернутых на 45+90*k градусов ДЛК появляются интеркаляты (в отличие от циклических ЛК и производных от них, у которых их нет). Соответствующие им новые числовые приведены ниже:
* 1, 0, 1, 1, 0, 1, 4, 0, 7, 15, 0 — мощность спектра числа интеркалятов в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
* 0, 0, 0, 0, 0, 0, 156, 0, 272, 342, 0 — максимальное число интеркалятов в повернутых полуциклических диагональных латинских квадратах порядка N=2n+1
Ну и наконец самое интересное: циклические ЛК любого нечетного порядка N можно подвергнуть процедуре диагонализации с получением на выходе диагонализированных циклических ДЛК (полуциклические ДЛК являются их подмножеством). Они изоморфны циклическим ЛК и друг другу как ЛК, но различны (не изоморфны) между собой как ДЛК. Их перечисление позволяет получить еще 3 новых числовых ряда:
* 1, 0, 480, 161280, 2229534720, 45984153600000 — число диагонализированных циклических диагональных латинских квадратов порядка N=2n+1
* 1, 0, 4, 32, 6144, 1152000 — число диагонализированных циклических диагональных латинских квадратов порядка N=2n+1 с фиксированной первой строкой
* 1, 0, 1, 1, 7, 81, 2933 — число главных классов диагонализированных циклических диагональных латинских квадратов порядка N=2n+1
Для числа диагональных трансверсалей в них получаются следующие новые числовые ряды:
* 1, 0, 1, 1, 7, 66, 1001 — мощность спектра числа диагональных трансверсалей в диагонализированных циклических диагональных латинских квадратах порядка N=2n+1
* 1, 0, 5, 27, 241, 4523, 127339 — минимальное число диагональных трансверсалей в диагонализированных циклических диагональных латинских квадратах порядка N=2n+1
* 1, 0, 5, 27, 269, 4828, 131106 — максимальное число диагональных трансверсалей в диагонализированных циклических диагональных латинских квадратах порядка N=2n+1
Как уже было отмечено сегодня ранее (см. https://vk.com/wall162891802_2441), для нечетных порядков, не кратных 3, квадраты данного типа располагаются в составе "старшей полоски" спектра. Для кратных 3 нечетных порядков (например, для N=9) квадраты данного типа тоже располагаются близко к максимуму в спектре, однако есть другой тип квадратов, в которых диагональных трансверсалей еще больше и который в перспективе надо будет поисследовать более детально...
Полученные результаты представлены сокращенно на картинке во вложении, а также доступны на обновленной версии странички, посвященной свойствами циклических ДЛК и производных от них: http://evatutin.narod.ru/oeis_cyclic_dls.html .
PS. И диаграмма Эйлера вдогонку...
В проекте RakeSearch завершен короткий эксперимент, целью которого являлся подсчет суммы мощностей главных классов для 2933 КФ диагонализированных циклических ДЛК порядка 13. Расчет занял чуть более суток (с учетом ожидания хвостов), мощности главных классов оказались различными (от 7680 до 184320, что говорит о наличии различного количества обобщенных M-симметрий в исследуемых квадратах). По итогам постобработки установлено, что всего существует 525419520 нормализованных диагонализированных циклических ДЛК порядка 13, что позволяет расширить числовой ряд
1, 0, 4, 32, 6144, 1152000
до
1, 0, 4, 32, 6144, 1152000, 525419520
(ряд пока не добавлен в OEIS). Умножая полученное значение на 13!, получаем что общее количество диагонализированных циклических ДЛК порядка 13 составляет 3271798279766016000, что в свою очередь позволяет расширить соответствующий числовой ряд
1, 0, 480, 161280, 2229534720, 45984153600000
до
1, 0, 480, 161280, 2229534720, 45984153600000, 3271798279766016000
В проекте RakeSearch к запуску подготовлен очередной небольшой вычислительный эксперимент, целью которого является построение спектра числа диагональных трансверсалей в полуциклических ДЛК порядка 17. С большой долей вероятности полученные значения займут верхнюю часть одноименного спектра для ДЛК общего вида, который мы будем строить в перспективе (как минимум частично, полностью это практически нереально ввиду его огромной мощности). Кворум 2, дедлайн короткий, время счета ожидается в районе нескольких часов, ожидаем запуска эксперимента hoarfrost'ом и считаем...
PS. Спектр, который мы вот-вот будем считать, отмечен восклицательным знаком
В проекте RakeSearch (https://rake.boincfast.ru/rakesearch/) завершен короткий двухдневный вычислительный эксперимент, целью которого являлось построение спектра числа диагональных трансверсалей в полуциклических ДЛК порядка 17. В результате расчетов для 272 главных классов получен спектр из 271 элемента (значения числа диагональных трансверсалей совпали всего для одной пары ДЛК) со следующими параметрами:
Min value = 204330233, max value = 204995269, width = 665037, cardinality = 271, density = 0.00
Полученные результаты позволяют расширить 2 известных числовых ряда.
1. Мощность спектра числа диагональных трансверсалей в полуциклических ДЛК: 1, 0, 1, 1, 0, 2, 20, 0 -> 1, 0, 1, 1, 0, 2, 20, 0, 271
2. Минимальное число диагональных трансверсалей в полуциклических ДЛК: 1, 0, 5, 27, 0, 4523, 127339, 0 -> 1, 0, 5, 27, 0, 4523, 127339, 0, 204330233
Как и ожидалось, полученные значения компактно расположились в старшей части спектра. Следующим шагом будет аналогичный эксперимент для размерности N=19, который планируется к запуску в проекте в самое ближайшее время (отмечен восклицательным знаком в нижнем правом углу на картинке во вложении).