Цитата: evatutin от 26.07.2022, 16:35

Обобщенные симметрии ОДЛК порядков 7-8 в парастрофических срезах

Ранее (см. https://vk.com/wall162891802_2053) были построены списки симметрий для ОДЛК порядков 4 и 5. Расширим их на бОльшие размерности. Возьмем списки КФ ОДЛК и построим по ним множества симметрий. Для порядка 7 эта процедура выполняется за несколько секунд, порядок 8 требует чуть более часа вычислительного времени. В результате получаются списки из 73 и 3522 симметрий соответственно, что само по себе здорово, но есть небольшое сомнение в том, что данные списки являются исчерпывающими.

С целью подтверждения сомнения выполним простейшее преобразование: транспонируем все КФы в списках с последующей нормализацией и произведем поиск симметрий повторно. (Идея выполнения транспонирования вызвана тем, что некоторые картинки расположения симметрий в парастрофических срезах получились не симметричным относительно главной диагонали, а это значит, что если исходный квадрат обладает симметрией (x,y), то его транспонированный изоморф должен обладать симметрией (y,x). Это правило применимо не ко всем срезам, т.к. для некоторых из них "нижний треугольник" одного из срезов будет симметричен "верхнему треугольнику" другого, но в общем и целом оно вполне работоспособно и применимо для подтверждения сомнения). В результате получаются списки из 83 и 3747 симметрий соответственно, что подтверждает сомнение.

Не получится ли расширить списки путем выполнения остальных эквивалентных преобразований? Для каждой КФ построим соответствующий ей класс изоморфизма путем применения всех возможных комбинаций преобразований M1 x M2 x {транспонирования, сдвиги, повороты, отражения}, для полученных (исчерпывающих) списков КФ ОДЛК выполним поиск симметрий. В результате для порядка N=7 получен список из 145 симметрий, что явно больше найденных ранее 73 и 83 симметрий. Для порядка N=8 данная процедура уже будет достаточно долгой и может быть выполнена в перспективе в проекте...

Таким образом, можно сделать вывод о том, что для построения исчерпывающих списков симметрий для выбранной размерности необходимо работать с исходными нормализованными ДЛК, а не с их КФ'ами.

Ну и напоследок... Заметим, что для N=1 единственный ДЛК обладает шестью обобщенными симметриями (по одной тривиальной в каждом из парастрофических срезов). Для порядков N=2 и N=3 ДЛК не существуют, а значит ни ОДЛК, ни обобщенных симметрий для последних нет. Для N=6 ОДЛК не существуют, поэтому для этой размерности обобщенных симметрий нет (по крайней мере для ОДЛК). Объединяя полученную информацию, получаем следующий числовой ряд — число обобщенных симметрий ОДЛК порядков 1-8 в парастрофических срезах:

6, 0, 0, 76, 44, 0, 145, >=3747

Полученный ряд не представлен в OEIS и планируется в добавлению по мере подтверждения серии текущих правок. Для порядка N=8 точное значение может быть получено в рамках сравнительно небольшого вычислительного эксперимента. Для порядков N=9 и N=10 аналогичные вычислительные эксперименты потребуют как минимум нескольких лет расчетов на грид.

Полученные списки симметрий для порядков 7 и 8 могут быть найдены тут:

* http://evatutin.narod.ru/dls_gen_symms/n7_odls_symmetries_list.html
* http://evatutin.narod.ru/dls_gen_symms/n8_odls_symmetries_list.html

PS. Напомню, что понимание того, как расположены обобщенные симметрии для выбранной размерности N позволяет находить соответствующие им редкие ДЛК. Например, для порядка N=10 это позволило как минимум найти множество редких комбинаторных структур (см. http://evatutin.narod.ru/evatutin_ls_all_structs_rus.pdf), наиболее интересные места уже пройдены, но поиск в настоящее время не окончен и активно продолжается в проекте RakeSearch. На перспективу дальнейших исследований есть подозрение, что у подобных редких ДЛК могут быть и другие интересные свойства...

Цитата: evatutin от 28.07.2022, 12:03

Вслед за https://vk.com/wall162891802_2057 выполним поиск обобщенных симметрий в ОДЛК (без парастрофических преобразований), в результате чего получится следующий новый числовой ряд — число обобщенных симметрий в ОДЛК порядка N:

1, 0, 0, 10, 7, 0, 8, a(8)>=74, a(9)>=41

Значения для a(8) и a(9) получены по спискам КФ ОДЛК путем применения к ним комбинации преобразований транспонирования и отражения по горизонтали, для чего потребовалось 5 минут и 9,5 часов работы Core i7 4770 в один поток соответственно. В перспективе для данных размерностей надо бы полностью развернуть главные классы, но для этого потребуются существенно бОльшие вычислительные затраты, расчет в перспективе будем выполнять в проекте...

Возьмем разработанные ранее полнопереборные генераторы ДЛК заданного порядка, с их помощью получим все множества ДЛК, по которым построим исчерпывающие списки обобщенных симметрий. В результате для порядков N<=7 получаются следующие два новых числовых ряда:

* число обобщенных симметрий в ДЛК порядка N: 1, 0, 0, 10, 8, 12, 12
* число обобщенных симметрий в парастрофических срезах в ДЛК порядка N: 6, 0, 0, 76, 74, 199, 861

Для расширения полученных числовых рядов на бОльшие размерности необходим грид.

Ссылки на все полученные списки обобщенных симметрий могут быть найдены на моей страничке, полученные новые числовые ряды планируются к добавлению в OEIS по мере подтверждения текущих правок.

Цитата: evatutin от 31.07.2022, 12:25

В результате обработки первого миллиона КФ ОДЛК порядка 10 получен первый набросок множества обобщенных симметрий для ОДЛК данной размерности:

 

http://evatutin.narod.ru/odls_gen_symms/n10_odls_symmetries_list.html

 

На это потребовалось 2,7 суток работы Core i7 4770 в 1 поток, всего обнаружено 27 разновидностей обобщенных симметрий и 2853 обобщенных симметрии в парастрофических срезах. Построение множества симметрий продолжается...

PS. Напомню, что разведка обобщенных симметрий на предмет обнаружения редких комбинаторных структур в настоящее время выполняется в проекте RakeSearch (https://rake.boincfast.ru/rakesearch/), подпроект Generalized symmetries in parastrophic slices for DLS of order 10. До обработки этих КФ ОДЛК мы еще не добрались, они пойдут позже, а находок (кодов симметрий) уже довольно много, что не может не радовать.

Цитата: evatutin от 16.08.2022, 17:45

Разведка ОДЛК порядка 10 и образуемых ими комбинаторных структур в 3-м парастрофическом срезе завершена. Первый рисунок показывает найденное число двушек (комбинаторных структур типа "линия-2"), второй — найденные типы комбинаторных структур, интересные места отмечены зеленым. Напомню, как был организован эксперимент. Для каждой точки, определяемой кодами симметрий отталкиваясь от мультимножеств длин циклов в перестановках Px и Py, описывающих обобщенную симметрию, сперва выполнялась разведка. Для этого для каждой точки производилась обработка 10 тыс. WU'шек для удаления M=80 и такого же количества для удаления M=70 (опять таки напомню, что число M обозначает число ячеек формируемого ДЛК, которое заполняется с учетом правил симметрии, остальные заполняются произвольным образом). Если при этом было найдено что-то интересное (редкие комбинаторные структуры или большое число двушек), то для данной точки производилась более детальная обработка для удалений M in {50, 60, 70, 80} по 100 тыс. WU'шек для каждого. В результате эксперимента был найден ряд интересных комбинаторных редких структур, но все они оказались повторными и были расположены в ожидаемых местах с кодами симметрий (1,16), (1,31), (4,16), (4,31), (16,31), (31,31) (в их составе присутствуют циклы длины 2, т.е. соответствующие им квадраты частично собраны из интеркалятов). Кроме того, для кода (27,27) было найдено несколько повторных 1-КФных однушек (редкий тип), а также линия-4 и трешка (они являются относительно редкими и большого интереса не представляют, т.к. попадаются и при обычном случайном переборе пространства квадратов). Впереди нас ждет обработка еще четырех парастрофических срезов.

PS. Немногочисленные найденные неповторные ОДЛК интересны еще и тем, что они могут содержать редкие коды симметрий, не включенные в формируемую в настоящее время коллекцию (см. http://evatutin.narod.ru/odls_gen_symms/n10_odls_symmetries_list.html). Формирование данной коллекции в настоящее время выполняется на моей машине в 1 поток, на данный момент обработано 4 порции ОДЛК из 10, найдено 27 типов обобщенных симметрий и 2860 типов обобщенных симметрий в парастрофических срезах.

Цитата: Шмяка от 18.08.2022, 23:41

"...число M обозначает число ячеек формуируемого ДЛК..." --- и так мало чё понимяу (кроме того что мы насчитали нечто полезное-интересное) но на этом слове я вообще капитально споткнулась

Цитата: evatutin от 21.08.2022, 10:05

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

Цитата: evatutin от 22.08.2022, 12:25

В подпроекте Generalized symmetries in parastrophic slices for DLS of order 10 проекта RakeSearch (https://rake.boincfast.ru/rakesearch/) в тестовом режиме запущен новый эксперимент, целью которого является продолжение разведки ОДЛК порядка 10 в окрестностях обобщенных симметрий в парастрофических срезах. Напомню, что до этого были обработаны срезы 1 и 3, впереди еще 4 среза, сейчас в обработку добавлен срез номер 2. Отличий данного эксперимента от предыдущих несколько.

1. WU'шки данного эксперимента укрупнены: примерно 100 WU'шек прошлого эксперимента равны одной WU'шке текущего.
2. Улучшена обработка окрестностей симметрий, где очень мало ДЛК (в них потенциально можно найти что-то редкое и интересное).
3. Есть прогресс, линейный, чекпоинтов нет, время счета WU'шки около 1 часа, иногда чуть больше, иногда чуть меньше, что определяется свойствами окрестности (числом ДЛК и сложностью их формирования). Есть подозрение, что время обработки некоторых окрестностей может быть раз в 10 больше, но это в теории, посмотрим, что будет на практике, пока таковых не попалось.

Сейчас в обработке находятся первые 10 симметрий с кодами 2-(0,0) ... 2-(0,9), ведутся логи, в принципе почти все работает. После завершения расчета текущей партии WU'шек ведение логов будет убрано, расчет пойдет в боевом режиме. До этого при обработке срезов 1 и 3 WU'шки были маленькие и их было много из-за того, что изначально планировалась разведка на удалениях M=50 и M=60, от которой позже было принято решение оказаться за ненадобностью (вычислительного времени требуется много, выход интересных редких КФ ОДЛК не сильно отличается от обычного случайного поиска или поиска по линейкам), сейчас для разведки остались только удаления M=70 и M=80. Меньшее число WU'шек сильно экономит время на их генерацию и постобработку, что позволит снять нагрузку и с сервера проекта, и с винтов на моих машинах, и разгрузить меня лично :), т.к. за этим процессом надо следить. Для обработки результатов написан новый постобработчик, который во многом автоматизирует данную процедуру (сперва было не совсем понятно, что и где надо смотреть, потом, когда стало понятно, не было времени, сейчас звезды наконец сошлись и все идеи воплощены в коде). Самое главное, что при работе проекта с несколькими подпроектами (или, что почти то же самое, но со стороны кранчера: счете нескольких проектов параллельно) маленьким WU'шкам достается мало вычислительного времени, что здорово растягивает срок данного эксперимента (срез номер 3 мы считали около 2 лет). С большими WU'шками дело должно пойти быстрее, правда другие подпроекты немного лишатся вычислительных мощностей...

По итогам эксперимента ожидается перечень редких комбинаторных структур из ОДЛК порядка 10 (полный перечень см. тут: http://evatutin.narod.ru/evatutin_ls_all_structs_rus.pdf, новых не было очень давно со времен анализа окрестностей 1-(1,31) и 1-(4,31)). Кроме того, также по результатам эксперимента ожидается пополнение перечня обобщенных симметрий в ОДЛК, который формируется в настоящее время в один поток на моей машине. На данный момент найдено 27 различных типов обобщенных симметрий и 2862 типа в парастрофических срезах (см. http://evatutin.narod.ru/odls_gen_symms/n10_odls_symmetries_list.html), обработаны 6 партий КФ ОДЛК из 10, обработка идет со скоростью примерно 3 суток на одну партию. Известные обобщенные симметрии в обрабатываемом 2-м срезе в настоящее время выглядят так, как показано на рисунке. Считаем...

Цитата: Шмяка от 22.08.2022, 23:08

об интеркалятах и трансверсалях поведано. и даже понято. )))

 

а что такое парастрофический срез?

Цитата: evatutin от 23.08.2022, 11:22

Цитата: Шмяка от 22.08.2022, 23:08

а что такое парастрофический срез?

Тут все довольно просто и понятно непосредственно из названия :). Латинский квадрат — это множество ячеек, заполненное значениями по некоторым правилам. Каждая ячейка имеет координаты x[i], y[i], в ней стоит значение v[i]. Например, для квадрата

0 2 3 1
3 1 0 2
1 3 2 0
2 0 1 3

верхняя левая ячейка имеет координаты x=0, y=0, в ней стоит значение v=0; под ней находится ячейка x=1, y=0, в ней значение v=3 и т.д. Т.е. фактически латинский квадрат образован из N^2 троек [x[i],y[i],v[i]]. А теперь самое главное... Парастрофические преобразования — это когда мы меняем порядок значений в тройке [x,y,v]. Для этого нужно получить все перестановки из 3 элементов, которых, как известно, 3! = 6. Соответственно и парастрофических преобразований тоже 6. Простейшее и наиболее понятное — замена [x,y,v] на [y,x,v], что эквивалентно транспонированию квадрата (строки и столбцы поменялись местами). Если v не остается на месте, то тут наглядную аналогию я дать затрудняюсь, но главное то, что на выходе получается корректный латинский квадрат (правда не всегда диагональный). Соответственно что получается: если мы имеем некоторое исходное множество квадратов, то каждый из них можно переделать в любой из 6 срезов. С позиции диагональных латинских квадратов после переделки квадрат получается другой (из другого главного класса, например, с другими числом диагональных трансверсалей), но его свойства похожи на исходный.

Ну а симметрия у нас описывается как некоторое соответствие между ячейками квадрата (как в шутку говорят некоторые физики и математики: что-то сделали и все осталось на месте :). Исторически мы шли так: нашли в публикациях плоскостную симметрию (отразили квадрат по горизонтали, нормализовали и получили тот же квадрат), потом из геометрических соображений вспомнили про симметрию относительно точки (центра квадрата), а потом сделали обобщение описания симметрии через перестановки:

x' = Px[x]

y' = Py[y]

v' = Pv[v]

Это симметрия без парастрофий. А дальше в приведенные формулы можно добавить одно из парастрофических преобразований и получить описание симметрии в одном из парастрофических срезов. Квадраты с симметриями являются довольно редкими и обладают рядом интересных свойств, почему и производится данный эксперимент. Доступно объяснил?

PS. Латинский квадрат — это на самом деле объект трехмерный, не плоский, хотя мы его привыкли рисовать именно плоским, как матрицу с числами. Каждый парастрофический срез можно представлять себе как одну из 6 возможных проекций трехмерного квадрата на двумерную плоскость. У меня была мысль попробовать изобразить это графически, но пока руки не дошли. Тут надо вспомнить OpenGL и попытаться это закодить...