Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: evatutin от 21.03.2023, 15:01Спектры числа обобщенных симметрий в ОДЛК
Ранее нами была составлена коллекция типов обобщенных симметрий в ДЛК и ОДЛК, в результате чего в OEIS было добавлено 4 новых числовых ряда и сейчас в проекте RakeSearch один из подпроектов ищет ОДЛК порядка 10 как раз во 2-м парастрофическом срезе обобщенных симметрий. Между тем открытым остался вопрос о том, сколькими симметриями может обладать конкретный квадрат и ряд связанных с ним смежных вопросов (например, вопрос, поднятый в свое время whitefox'ом и связанный с вложенностью обобщенных симметрий, где частично его выводы подтвердились, а частично — нет). Изначально было принято решение ограничиться вычислением членов числового ряда, соответствующего квадратам с максимально возможным числом обобщенных симметрий, однако в процессе счета стало понятно, что и спектры тоже получаются достаточно интересными, а это значит, что попутно стоит посчитать и их (тем более, что это не сильно сложнее в вычислительном плане). Для этого была взята построенная ранее коллекция ОДЛК, по ней был осуществлен поиск, в результате которого получены следующие новые числовые ряды, не представленные в OEIS.
1, 0, 0, 96, 100, 0, 2, 2, 1, 1, 1, 1 — минимальное число обобщенных симметрий в ОДЛК порядка N (скорее всего далее ряд будет состоять из одних единиц)
1, 0, 0, 96, 100, 0, 294, 10752, 3888, a(10) >= 40, a(11) >= 1210, a(12) >= 16 — максимальное число обобщенных симметрий в ОДЛК порядка N
1, 0, 0, 1, 1, 0, 4, 15, 18, a(10) >= 7, a(11) >= 5, a(12) >= 5 — мощность спектра числа обобщенных симметрий в ОДЛК порядка NЭксперименты для порядков N <= 7 выполняются мгновенно, для размерности N=8 потребовалось 11 минут в 1 поток на Core i7 4770, для размерности N=9 — 2,5 часа, для размерности N=10 — 113 часов. ОДЛК размерностей N=11 и N=12 обработать на одной машине уже проблематично, ввиду чего соответствующие расчеты были запущены в однопоточном режиме на сутки, полученные предварительные результаты представлены выше, в дальнейшем расчеты могут быть продолжены в проекте.
Ну и в заключении стоит привести пару интересных спектров:
N=9 - {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 27, 36, 48, 54, 72, 108, 486, 3888}, 18 элементов, полный спектр
N=12 - {1, 2, 4, 8, 16}, 5 элементов, аппроксимация спектра
Видно, что спектр для размерности N=12 образован только степенями двойки, что достаточно интересно и неожиданно (по крайней мере на данный момент, возможно при более детальном анализе ситуация изменится и спектр будет расширен на другие значения, не равные 2^k). Для размерности N=9 в спектре присутствуют вполне определенные значения, для которых возможно существует аналитическая формула...
Спектры числа обобщенных симметрий в ОДЛК
Ранее нами была составлена коллекция типов обобщенных симметрий в ДЛК и ОДЛК, в результате чего в OEIS было добавлено 4 новых числовых ряда и сейчас в проекте RakeSearch один из подпроектов ищет ОДЛК порядка 10 как раз во 2-м парастрофическом срезе обобщенных симметрий. Между тем открытым остался вопрос о том, сколькими симметриями может обладать конкретный квадрат и ряд связанных с ним смежных вопросов (например, вопрос, поднятый в свое время whitefox'ом и связанный с вложенностью обобщенных симметрий, где частично его выводы подтвердились, а частично — нет). Изначально было принято решение ограничиться вычислением членов числового ряда, соответствующего квадратам с максимально возможным числом обобщенных симметрий, однако в процессе счета стало понятно, что и спектры тоже получаются достаточно интересными, а это значит, что попутно стоит посчитать и их (тем более, что это не сильно сложнее в вычислительном плане). Для этого была взята построенная ранее коллекция ОДЛК, по ней был осуществлен поиск, в результате которого получены следующие новые числовые ряды, не представленные в OEIS.
1, 0, 0, 96, 100, 0, 2, 2, 1, 1, 1, 1 — минимальное число обобщенных симметрий в ОДЛК порядка N (скорее всего далее ряд будет состоять из одних единиц)
1, 0, 0, 96, 100, 0, 294, 10752, 3888, a(10) >= 40, a(11) >= 1210, a(12) >= 16 — максимальное число обобщенных симметрий в ОДЛК порядка N
1, 0, 0, 1, 1, 0, 4, 15, 18, a(10) >= 7, a(11) >= 5, a(12) >= 5 — мощность спектра числа обобщенных симметрий в ОДЛК порядка N
Эксперименты для порядков N <= 7 выполняются мгновенно, для размерности N=8 потребовалось 11 минут в 1 поток на Core i7 4770, для размерности N=9 — 2,5 часа, для размерности N=10 — 113 часов. ОДЛК размерностей N=11 и N=12 обработать на одной машине уже проблематично, ввиду чего соответствующие расчеты были запущены в однопоточном режиме на сутки, полученные предварительные результаты представлены выше, в дальнейшем расчеты могут быть продолжены в проекте.
Ну и в заключении стоит привести пару интересных спектров:
N=9 - {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 27, 36, 48, 54, 72, 108, 486, 3888}, 18 элементов, полный спектр
N=12 - {1, 2, 4, 8, 16}, 5 элементов, аппроксимация спектра
Видно, что спектр для размерности N=12 образован только степенями двойки, что достаточно интересно и неожиданно (по крайней мере на данный момент, возможно при более детальном анализе ситуация изменится и спектр будет расширен на другие значения, не равные 2^k). Для размерности N=9 в спектре присутствуют вполне определенные значения, для которых возможно существует аналитическая формула...
Цитата: evatutin от 21.03.2023, 21:35Спектры числа обобщенных симметрий в ДЛК порядка 1-8
Вслед за спектрами ОДЛК (см. https://vk.com/wall162891802_2252) произведем построение спектров числа обобщенных симметрий в ДЛК. Для этого при подходе "в лоб" необходимо сформировать все ДЛК заданного порядка N с использованием метода полного перебора, найти число обобщенных симметрий в каждом ДЛК и сформировать соответствующие спектры и числовые ряды. Для порядков N<=6 данная процедура выполняется практически мгновенно, для порядка N=7 на ее выполнение требуется около 1 минуты вычислительного времени процессора Core i7 4770 в 1 поток. Для порядка N=8 такой подход уже не сработает ввиду очень большого числа ДЛК, поэтому потребуется хитрить. Прежде всего, необходимо отметить, что число обобщенных симметрий является инвариантом главного класса ДЛК. Перестановки Px, Py и Pv могут измениться в зависимости от комбинации примененных M-преобразований, а вот число описываемых ими симметрий останется прежним, что позволяет вести обработку по одному квадрату из каждого главного класса с использованием разработанного ранее генератора КФ (см. недавно вышедшую статью про него: http://evatutin.narod.ru/evatutin_dls_scf_gen.pdf). При такой организации вычислительный эксперимент потребовал 1,5 часа вычислительного времени Core i7 4770 в 1 поток и был успешно завершен. В результате получены следующие числовые ряды:
1, 0, 0, 96, 12, 24, 1, 1, 1, 1, 1, 1 — минимальное число обобщенных симметрий в ДЛК порядка N
1, 0, 0, 96, 100, 24, 294, 10752, a(9) >= 3888, a(10) >= 40, a(11) >= 1210, a(12) >= 16 — максимальное число обобщенных симметрий в ДЛК порядка N
1, 0, 0, 1, 2, 1, 9, 22, a(9) >= 18, a(10) >= 7, a(11) >= 5, a(12) >= 5 — мощность спектра числа обобщенных симметрий в ДЛК порядка NВсе числовые ряды являются новыми и не присутствуют в OEIS. Расширение полученных рядов на размерности N=9 в перспективе возможно в проекте. Для порядков N >= 10 формирование верхних и нижних оценок на соответствующие члены в составе полученных числовых рядов возможно в перспективе с использованием генераторов ДЛК с обобщенными симметриями.
PS. Члены a(9)-a(12) для первого ряда и нижние ограничения на аналогичные члены двух последующих рядов взяты из предыдущей серии вычислительных экспериментов по ОДЛК ввиду того, что ОДЛК — это подмножество ДЛК. В перспективе данные нижние ограничения могут быть усилены.
Спектры числа обобщенных симметрий в ДЛК порядка 1-8
Вслед за спектрами ОДЛК (см. https://vk.com/wall162891802_2252) произведем построение спектров числа обобщенных симметрий в ДЛК. Для этого при подходе "в лоб" необходимо сформировать все ДЛК заданного порядка N с использованием метода полного перебора, найти число обобщенных симметрий в каждом ДЛК и сформировать соответствующие спектры и числовые ряды. Для порядков N<=6 данная процедура выполняется практически мгновенно, для порядка N=7 на ее выполнение требуется около 1 минуты вычислительного времени процессора Core i7 4770 в 1 поток. Для порядка N=8 такой подход уже не сработает ввиду очень большого числа ДЛК, поэтому потребуется хитрить. Прежде всего, необходимо отметить, что число обобщенных симметрий является инвариантом главного класса ДЛК. Перестановки Px, Py и Pv могут измениться в зависимости от комбинации примененных M-преобразований, а вот число описываемых ими симметрий останется прежним, что позволяет вести обработку по одному квадрату из каждого главного класса с использованием разработанного ранее генератора КФ (см. недавно вышедшую статью про него: http://evatutin.narod.ru/evatutin_dls_scf_gen.pdf). При такой организации вычислительный эксперимент потребовал 1,5 часа вычислительного времени Core i7 4770 в 1 поток и был успешно завершен. В результате получены следующие числовые ряды:
1, 0, 0, 96, 12, 24, 1, 1, 1, 1, 1, 1 — минимальное число обобщенных симметрий в ДЛК порядка N
1, 0, 0, 96, 100, 24, 294, 10752, a(9) >= 3888, a(10) >= 40, a(11) >= 1210, a(12) >= 16 — максимальное число обобщенных симметрий в ДЛК порядка N
1, 0, 0, 1, 2, 1, 9, 22, a(9) >= 18, a(10) >= 7, a(11) >= 5, a(12) >= 5 — мощность спектра числа обобщенных симметрий в ДЛК порядка N
Все числовые ряды являются новыми и не присутствуют в OEIS. Расширение полученных рядов на размерности N=9 в перспективе возможно в проекте. Для порядков N >= 10 формирование верхних и нижних оценок на соответствующие члены в составе полученных числовых рядов возможно в перспективе с использованием генераторов ДЛК с обобщенными симметриями.
PS. Члены a(9)-a(12) для первого ряда и нижние ограничения на аналогичные члены двух последующих рядов взяты из предыдущей серии вычислительных экспериментов по ОДЛК ввиду того, что ОДЛК — это подмножество ДЛК. В перспективе данные нижние ограничения могут быть усилены.