Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Спектр числа диагональных трансверсалей в ДЛК утвержден в OEIS: https://oeis.org/A345370
Возьмем ДЛК с минимально известным на данный момент числом диагональных трансверсалей (588) и построим спектр диагональных трансверсалей в его окрестностях. То, что получилось, на картинке внизу слева. Визуально спектр отличается от построенного вчера спектра для ДЛК с максимально известным на данный момент числом диагональных трансверсалей (внизу посредине). В обоих квадратах 108 интеркалятов, что не может быть причиной различия. Спектр диагональных трансверсалей в ДЛК порядка 12 расширен с 13668 до 13677 значений.
Возьмем за основу для построения спектра диагональных трансверсалей ДЛК с максимально известным на данный момент числом диагональных трансверсалей и будем строить для него окрестности из ДЛК, только в отличие от выполненного ранее эксперимента в качестве простого преобразования будем использовать не поворот 1 интеркалята, а поворот 1 цикла (напомню, циклы — одно из обобщений интеркалятов). В таком случае окрестности получаются больше, время вычислительного эксперимента тоже больше (17,5 ч в 1 поток на Core i7 4770), но и результирующий спектр — шире и мощнее (см. самую нижнюю картинку в сравнении с той, которая над ней)! Основное расширение спектра происходит в верхней части в области малотрансверсальных ДЛК (другими методами ДЛК из данной области ранее либо не находились вовсе, либо попадались, но очень редко). Среднетрансверсальных тоже прибавилось, но не настолько много. Среди найденных малотрансверсальных ДЛК есть квадрат
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 6 8 9 7 11 3 10
3 4 10 9 8 1 11 6 5 2 7 0
8 7 1 5 9 11 0 2 6 10 4 3
11 10 6 0 7 9 5 4 3 8 2 1
10 3 11 7 6 8 9 5 4 1 0 2
5 6 4 1 2 0 3 10 11 7 8 9
4 5 3 8 1 2 10 11 9 0 6 7
2 0 9 10 3 4 7 8 1 5 11 6
9 11 5 2 0 7 4 3 10 6 1 8
6 8 7 11 10 3 2 1 0 4 9 5
7 9 8 6 11 10 1 0 2 3 5 4
с 173 диагональными трансверсалями, что позволяет достаточно серьезно усилить верхнее ограничение на минимальное число диагональных трансверсалей в ДЛК: в ряду A287647 было a(12)<=588, стало a(12)<=173. Кроме того у данного квадрата 2240 трансверсалей (тоже новый рекорд: в ряду A287645 было a(12)<=6240, стало a(12)<=2240) и 64 интеркалята. Мощность спектра диагональных трансверсалей ДЛК порядка 12 расширена до 14534 элементов, что составляет почти половину от его ширины, являющейся его теоретической верхней границей.
Эксперимент по подсчету числа ОДЛК для одного интересного ДЛК порядка 12 близок к завершению, вот-вот пойдут хвосты. Дедлайн на вновь выдаваемые задания установлен равным 1 суткам чтобы побыстрее досчитать хвосты и приступить к анализу результатов.
Сформируем выборку из 600 тыс. случайных квадратов Брауна и посмотрим на спектр ее диагональных трансверсалей (см. картинку). Невооруженным глазом видно четное количество диагональных трансверсалей у всех квадратов (по-видимому потому, что квадраты Брауна обладают плоскостной симметрией) и 3 полосы, вокруг которых группируются квадраты. Ни одного дважды Брауна среди них нет, что говорит о том, что последние очень редки. Все известные на данный дважды Брауны были получены либо от анализа ОДЛК в составе большой комбинаторной структуры, либо простыми преобразованиями от уже имеющихся ДЛК/ОДЛК.
Возьмем ДЛК порядка 12, обладающий на данный момент минимальным числом диагональных трансверсалей, и подвергнем его процедуре диагонализации по Брауну. В результате выполненного преобразования получается множество из ДЛК с маленьким числом трансверсалей (от 132 до 258), покрывающих определенную часть соответствующего спектра. Самый маленький ДЛК
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 6 8 10 7 11 9 3
4 5 1 0 6 2 11 8 3 10 7 9
9 11 6 7 10 8 3 2 4 1 0 5
7 10 9 6 8 11 1 3 5 2 4 0
10 9 11 8 7 3 5 4 6 0 2 1
5 6 4 1 2 0 10 11 9 8 3 7
2 0 3 5 1 4 7 9 10 6 11 8
3 4 5 2 0 1 9 6 11 7 8 10
11 3 8 10 9 7 4 0 2 5 1 6
8 7 10 11 3 9 0 5 1 4 6 2
6 8 7 9 11 10 2 1 0 3 5 4
имеет 132 диагональных трансверсали, что позволяет усилить найденное ранее ограничение: в ряду A287647 ограничение a(12)<=173 усилено до a(12)<=132.
В ходе построения окрестностей путем вращения 1 цикла начиная с ДЛК с 27408 диагональными трансверсалями был найден квадрат
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 6 7 11 9 10
2 0 1 5 3 4 7 8 6 10 11 9
6 9 11 7 10 8 3 1 4 0 2 5
9 11 10 6 8 7 4 3 5 1 0 2
11 10 9 8 7 6 5 4 3 2 1 0
5 3 4 1 2 0 11 9 10 7 8 6
4 5 3 11 1 9 2 10 0 8 6 7
3 4 5 2 0 1 10 11 9 6 7 8
10 8 7 0 6 2 9 5 11 4 3 1
7 6 8 9 11 10 1 0 2 3 5 4
8 7 6 10 9 11 0 2 1 5 4 3
у которого 98 диагональных трансверсалей, что позволяет усилить верхнее ограничение в ряду A287647: было a(12)<=132, стало a(12)<=98. Диагонализируя найденный ДЛК, можно построить семейство из 2126 ДЛК, в состав которого входит ДЛК
1 2 0 4 5 3 8 11 9 6 7 10
2 0 3 5 6 4 9 10 1 8 11 7
10 7 11 6 8 9 1 0 4 5 2 3
9 6 8 7 11 10 0 1 3 2 5 4
11 10 7 9 1 8 5 2 6 4 3 0
5 3 4 1 2 0 7 6 11 10 9 8
4 5 6 0 3 2 10 9 7 11 8 1
3 4 5 2 0 1 11 8 10 7 6 9
7 11 10 8 9 6 4 3 5 1 0 2
8 9 1 10 7 11 2 5 0 3 4 6
6 8 9 11 10 7 3 4 2 0 1 5
у которого 74 диагональных трансверсали, что дополнительно усиливает ограничение до a(12)<=74.
В ходе анализа первых результатов диагонализации ДЛК порядка 12 с рекордным на данный момент числом диагональных трансверсалей, равным 28496, был найден ДЛК с 30192 диагональными трансверсалями, что позволяет усилить ограничение с a(12)>=28496 до a(12)>=30192 в ряду https://oeis.org/A287648.
Для исследования свойств спектров ДЛК порядка 12 были сформированы две выборки случайных ДЛК специального типа: симметричных в одной и двух плоскостях, объем выборок — 500 тыс. ДЛК и 11 тыс. ДЛК соответственно (объемы определяются временем вычислительного эксперимента, которое для данных экспериментов без грида составляет около суток на CPU в 1 поток). Для каждой из выборок был построен спектр диагональных трансверсалей (верхние картинки), а также его расширение путем вращения 1 интеркалята (средний ряд картинок) и 1 цикла (нижний ряд картинок). Видно, что спектр симметричных в одной плоскости ДЛК от проделанных простых преобразований расширяется, но не сильно, в то время как спектр дважды симметричных ДЛК получается значительно более широким (у квадратов Брауна, которые исследовались незадолго до этого, аналогичный спектр еще шире). Данная информация полезна в контексте планирования дальнейших экспериментов на грид с целью дальнейшего расширения спектра диагональных трансверсалей, который в настоящее время включает в своем составе 16374 элемента.
Интересной особенностью является то, что в построенных спектрах для симметричных в одной плоскости ДЛК число диагональых трансверсалей всегда кратно 2, а для дважды симметричных ДЛК — 4.
Некоторое время назад в OEIS был добавлен ДЛК порядка 12
0 10 4 6 2 8 9 3 7 5 11 1
11 1 7 5 9 3 2 8 4 6 0 10
4 6 2 8 1 11 10 0 9 3 7 5
7 5 9 3 10 0 1 11 2 8 4 6
3 9 0 10 4 6 7 5 11 1 8 2
8 2 11 1 7 5 4 6 0 10 3 9
2 8 1 11 5 7 6 4 10 0 9 3
9 3 10 0 6 4 5 7 1 11 2 8
5 7 3 9 0 10 11 1 8 2 6 4
6 4 8 2 11 1 0 10 3 9 5 7
1 11 5 7 3 9 8 2 6 4 10 0
10 0 6 4 8 2 3 9 5 7 1 11
имевший рекордное на тот момент число ОДЛК, равное 1 764 493 860. Результат вызвал определенные сомнения (как у меня, так и у редакторов OEIS), т.к. обсчитанные до этого ДЛК имели значительно меньшее число ОДЛК (например, вот тут https://vk.com/wall162891802_1706 анонсирован ДЛК с 357 535 322 ОДЛК). Чтобы развеять сомнения, квадрат было необходимо обсчитать независимо, что и было сделано в проекте. На это потребовалось чуть меньше месяца (вычисления производились с кворумом 2) и почти неделя на досчет хвостов. В результате расчетов получено в точности такое же значение, как и было ранее получено анонимным пользователем. Результат подтвержден, сомнения развеяны, теперь его необходимо попытаться усилить... 