Форум

Пожалуйста или Регистрация для создания записей и тем.

Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...

НазадСтраница 28 из 190Далее

Покажем, что не симметричных двушек (структур типа линия-3 или, что то же самое, — звезда 1:2) также с легкостью можно подобрать CMS, отображающие лучи друг в друга, а центральная квадрат — сам в себя. Для этого возьмем ничем не примечательную двушку A—B—C с характеристикой ортогональности = 12 (таких у нас абсолютное большинство):

B = 0123456789120436985727869351048057192346386957142059710486327648213095453062791894157802636392804571 (центральный квадрат)

A = 0123456789965201743852783490163819524607190526837460347825914391875260748693012585671039422740691853 (луч 1)
C = 0123456789965281743052703498163819524607198526037460347825914391075268740693812585671039422748691053 (луч 2)

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

1 CMS:

0 6 5 7 4 2 1 3 8 9
74 32 67 81 19 82 24 17 48 14
44 66 30 27 16 60 87 23 73 96
22 31 11 58 90 43 71 84 38 99
45 41 46 35 20 40 42 70 18 49
59 51 91 88 86 55 79 78 33 50
25 65 62 94 69 61 21 12 77 64
47 36 76 28 10 83 72 68 57 56
80 13 15 75 37 85 54 26 53 98
34 52 92 97 63 95 29 93 89 39

Loops structure: {1:16, 2:42}

2 CMS:

0 6 5 7 4 2 1 58 8 24
61 32 67 81 19 82 9 17 48 14
44 66 41 27 16 60 75 23 73 96
22 31 11 3 90 43 71 84 38 10
45 30 46 35 20 40 42 70 26 49
59 51 91 88 95 55 79 78 52 50
25 65 47 94 69 74 21 12 77 64
62 36 76 28 99 83 72 68 57 56
80 13 15 87 37 85 54 18 53 98
34 33 92 97 63 86 29 93 89 39

Loops structure: {1:12, 2:29, 3:4, 6:3}

3 CMS:

0 6 5 7 4 2 10 3 8 77
15 26 67 81 19 82 24 17 48 14
44 66 30 27 16 60 59 23 73 62
22 31 11 40 90 43 71 33 38 99
45 63 46 35 20 58 42 70 18 49
87 51 91 88 86 55 79 78 84 50
25 65 96 94 69 61 21 12 9 64
47 36 76 95 1 83 72 68 57 56
80 13 74 75 37 85 54 32 53 98
34 52 92 97 41 28 29 93 89 39

Loops structure: {1:12, 2:29, 3:4, 6:3}

4 CMS:

0 6 5 7 4 2 10 40 8 24
61 26 67 81 19 82 77 17 48 14
44 66 63 27 16 60 75 23 73 62
22 31 11 3 90 43 71 33 38 1
45 30 46 35 20 58 42 70 32 49
87 51 91 88 28 55 79 78 52 50
25 65 47 94 69 15 21 12 9 64
96 36 76 95 99 83 72 68 57 56
80 13 74 59 37 85 54 18 53 98
34 84 92 97 41 86 29 93 89 39

Loops structure: {1:12, 2:19, 5:4, 10:3}

5 CMS:

0 6 5 7 4 2 99 40 8 9
74 18 67 81 19 82 77 17 48 14
44 66 63 27 16 60 87 23 73 47
22 31 11 58 90 43 71 52 38 1
45 41 46 35 20 3 42 70 32 49
75 51 91 88 28 55 79 78 33 50
25 65 62 94 69 15 21 12 24 64
96 36 76 86 10 83 72 68 57 56
80 13 61 59 37 85 54 26 53 98
34 84 92 97 30 95 29 93 89 39

Loops structure: {1:16, 2:22, 4:10}

6 CMS:

0 6 5 7 4 2 99 58 8 77
15 18 67 81 19 82 9 17 48 14
44 66 41 27 16 60 59 23 73 47
22 31 11 40 90 43 71 52 38 10
45 63 46 35 20 3 42 70 26 49
75 51 91 88 95 55 79 78 84 50
25 65 96 94 69 74 21 12 24 64
62 36 76 86 1 83 72 68 57 56
80 13 61 87 37 85 54 32 53 98
34 33 92 97 30 28 29 93 89 39

Loops structure: {1:12, 2:19, 5:4, 10:3}

7 CMS:

0 6 5 7 4 59 10 3 8 35
90 26 28 81 19 82 24 17 48 14
32 66 30 27 16 60 2 23 73 62
22 31 11 89 15 43 71 33 38 99
45 56 46 77 20 58 42 70 18 49
87 51 91 88 86 55 79 1 21 50
25 65 13 94 69 61 84 12 9 64
47 36 76 95 78 83 72 68 57 63
80 96 74 75 37 85 54 44 53 98
34 52 92 97 41 67 29 93 40 39

Loops structure: {1:12, 2:19, 5:4, 10:3}

8 CMS:

0 6 5 7 4 59 10 89 8 24
61 26 28 81 19 82 35 17 48 14
32 66 56 27 16 60 75 23 73 62
22 31 11 3 15 43 71 33 38 78
45 30 46 77 20 58 42 70 44 49
87 51 91 88 67 55 79 1 52 50
25 65 47 94 69 90 84 12 9 64
13 36 76 95 99 83 72 68 57 63
80 96 74 2 37 85 54 18 53 98
34 21 92 97 41 86 29 93 40 39

Loops structure: {1:12, 2:9, 7:4, 14:3}

9 CMS:

0 6 5 7 4 59 78 3 8 9
74 44 28 81 19 82 24 17 48 14
32 66 30 27 16 60 87 23 73 13
22 31 11 58 15 43 71 21 38 99
45 41 46 77 20 89 42 70 18 49
2 51 91 88 86 55 79 1 33 50
25 65 62 94 69 61 84 12 35 64
47 36 76 67 10 83 72 68 57 63
80 96 90 75 37 85 54 26 53 98
34 52 92 97 56 95 29 93 40 39

Loops structure: {1:16, 2:22, 4:10}

10 CMS:

0 6 5 7 4 59 78 58 8 24
61 44 28 81 19 82 9 17 48 14
32 66 41 27 16 60 75 23 73 13
22 31 11 3 15 43 71 21 38 10
45 30 46 77 20 89 42 70 26 49
2 51 91 88 95 55 79 1 52 50
25 65 47 94 69 74 84 12 35 64
62 36 76 67 99 83 72 68 57 63
80 96 90 87 37 85 54 18 53 98
34 33 92 97 56 86 29 93 40 39

Loops structure: {1:12, 2:9, 3:4, 4:10, 6:3}

...

Если в качестве исходных квадратов взять просто 3 случайных квадрата, то для них CMS не находится, т.к. не существует, т.е. найденное свойство не является простой случайностью, а представляет собой следствие определенной закономерности...

Рассмотрим трешку (структуру типа звезда 1:3) с центральным квадратом A и лучами B1, B2 и B3. Будем искать CMS, попарно отражающие луч Bi в луч Bj с соответствующим отражением центрального квадрата самого в себя. Оказывается, что отражения лучей друг в друга существуют не всегда...

Пример 1

A = 0123456789120467983564903851722578910364895274360198312640573765821490438910752656170329487046598213

B1 = 0428965173869347205112570436989082154736674530128943617985203509817462591023684778346209152176589304
B2 = 0428965173968347205112570436898092154736674530129843617985203509817462591023684778346209152176589304
B3 = 0428765193986347205112570438697082154936694530128743716985203509816472561023974887349206152196587304

B1-B2: CMS found

0 1 2 4 3 5 6 7 8 9
10 11 12 60 14 15 16 17 70 19
20 85 22 23 45 25 26 27 28 29
30 31 32 33 34 35 36 92 38 52
40 41 42 43 44 24 88 47 48 49
50 51 39 53 54 81 71 57 58 59
13 61 62 77 96 65 66 99 68 69
18 56 72 73 74 75 76 63 78 79
80 55 82 83 84 21 86 95 46 89
90 91 37 93 94 87 64 97 98 67

Loops structure: {1:72, 2:14}

B1-B3: CMS found

0 6 19 3 39 30 1 44 8 16
79 77 12 21 35 76 34 17 99 97
82 88 50 84 24 89 2 81 28 80
5 86 32 72 9 14 57 37 74 4
96 41 43 42 90 45 60 53 48 93
22 33 52 38 63 66 56 36 65 59
85 83 98 54 64 26 55 70 68 91
67 71 51 73 20 69 15 11 94 10
29 27 47 61 23 46 31 87 13 25
7 75 92 49 78 95 40 58 62 18

Loops structure: {1:22, 2:24, 3:6, 6:2}

B2-B1: CMS found

0 1 2 4 3 5 6 7 8 9
10 11 12 60 14 15 16 17 70 19
20 85 22 23 45 25 26 27 28 29
30 31 32 33 34 35 36 92 38 52
40 41 42 43 44 24 88 47 48 49
50 51 39 53 54 81 71 57 58 59
13 61 62 77 96 65 66 99 68 69
18 56 72 73 74 75 76 63 78 79
80 55 82 83 84 21 86 95 46 89
90 91 37 93 94 87 64 97 98 67

Loops structure: {1:72, 2:14}

B2-B3: CMS found

0 18 9 10 79 39 25 7 77 2
3 87 84 47 89 15 97 31 1 88
72 38 78 23 98 94 21 71 76 95
41 45 32 26 65 99 57 49 33 93
5 30 70 50 90 62 53 51 48 37
43 58 66 46 68 64 55 36 13 59
74 83 17 56 63 34 52 6 54 75
14 27 19 86 60 69 28 92 22 96
4 8 85 61 12 82 73 11 20 42
44 91 81 40 67 29 80 16 24 35

Loops structure: {1:8, 2:26, 4:10}

B3-B1: CMS found

0 6 19 3 39 30 1 44 8 16
79 77 12 21 35 76 34 17 99 97
82 88 50 84 24 89 2 81 28 80
5 86 32 72 9 14 57 37 74 4
96 41 43 42 90 45 60 53 48 93
22 33 52 38 63 66 56 36 65 59
85 83 98 54 64 26 55 70 68 91
67 71 51 73 20 69 15 11 94 10
29 27 47 61 23 46 31 87 13 25
7 75 92 49 78 95 40 58 62 18

Loops structure: {1:22, 2:24, 3:6, 6:2}

B3-B2: CMS found

0 18 9 10 79 39 25 7 77 2
3 87 84 47 89 15 97 31 1 88
72 38 78 23 98 94 21 71 76 95
41 45 32 26 65 99 57 49 33 93
5 30 70 50 90 62 53 51 48 37
43 58 66 46 68 64 55 36 13 59
74 83 17 56 63 34 52 6 54 75
14 27 19 86 60 69 28 92 22 96
4 8 85 61 12 82 73 11 20 42
44 91 81 40 67 29 80 16 24 35

Loops structure: {1:8, 2:26, 4:10}

Видно, что для всех пар лучей Bi-Bj нашлись CMS (случай i=j не рассматривается, тут CMS тривиальна, случаи Bi-Bj и Bj-Bi специально по сути обработаны дважды для перепроверки корректности кода, используемого для поиска CMS).

Пример 2

A = 0123456789123709854640963718259684513072596870243134592806178701635294237596410875128493606840127953

B1 = 5126074389497138506292051487366734952801846971025308134269751640893527738250169425986374103057269148
B2 = 8673054912238019764567512398041029845376789540126305349627819247610538496278315051083764293416528097
B3 = 8673054912239018764567512398041029845376798540126305349627819247610538486279315051083764293416528097

B1-B2: -
B1-B3: -
B2-B1: -
B2-B3: CMSs found

0 1 2 9 4 5 6 7 8 3
49 95 15 13 14 12 16 17 18 19
20 21 36 23 68 61 26 27 28 29
65 31 84 33 34 35 22 56 38 39
40 71 75 43 44 45 46 76 86 10
97 51 73 87 54 55 37 57 58 59
60 25 62 63 64 30 66 67 24 69
70 41 72 52 99 42 47 77 78 79
80 81 82 83 32 85 48 53 90 89
88 91 92 93 94 11 96 50 98 74

Loops structure: {1:62, 2:19}

B3-B1: -

B3-B2: CMS found

0 1 2 9 4 5 6 7 8 3
49 95 15 13 14 12 16 17 18 19
20 21 36 23 68 61 26 27 28 29
65 31 84 33 34 35 22 56 38 39
40 71 75 43 44 45 46 76 86 10
97 51 73 87 54 55 37 57 58 59
60 25 62 63 64 30 66 67 24 69
70 41 72 52 99 42 47 77 78 79
80 81 82 83 32 85 48 53 90 89
88 91 92 93 94 11 96 50 98 74

Loops structure: {1:62, 2:19}

В данном примере CMS нашлась только для пары лучей B2 и B3, для других пар CMS не существуют. Схожая ситуация и со звездами с большим числом лучей: для каких-то пар CMS существует, для каких-то — нет. А это, в свою очередь, свидетельствует о том, что в общем случае гипотеза https://vk.com/wall162891802_1177 не верна и не для всех звезд их лучи можно получить путем циклического применения к ним одной и той же CMS. А жаль...

 

А можно ещё спросить вопрос, а вот исследования латинских квадратов, которые идут сейчас, где оно в будущем будет применено?

Пусть не практически, а хотя бы для решения какой-то другой математической проблемы оно будет применено?

 

Yura12, "Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях." - Википедия. Также смотрим примечания, где есть ссылки на статьи.

Много научных публикаций по этой теме есть в КиберЛенинке. Еще одно необычное применение - в магии.

Ну коль в магии, тогда надо помочь альтернативной науке. ?

PinkFloyd отреагировал на эту запись.
PinkFloyd

ale4316, в данном случае можно говорить об "эзотерике". :-)

в статусе сервера "research progress" был 17 процентов а потом стал 7.

Ранее нами была разработана группа простых преобразований (поворот интеркалятов, циклов и нетривиальных латинских подпрямоугольников), позволяющая в некоторых случаях находить новые КФ ОДЛК по имеющимся с малыми затратами вычислительного времени. Эффективное подмножество из них активно используется в проекте в постобработчике найденных КФ ОДЛК (в настоящее время он выполняется на клиенте: если расчет WU'шки на несколько секунд повисает на 100%, значит скорее всего это и есть фаза работы данного постобработчика). Сейчас произведена попытка разработки еще одного простого преобразования, суть которого заключается в попытке замены заданного количества (от 2 до 5) трансверсалей в ДЛК. Версия расчетного модуля в основном подпроекте изменена на 3.2.2, соответствующие WU'шки экспериментов exp725...exp730 добавлены, исследуем эффективность...

PS. Картинка иллюстрирует суть выполняемого простого преобразования: для исходного ДЛК (а) было сброшено 3 трансверсали, в результате чего был получен частично заполненный квадрат (б), из которого затем был получен квадрат (в), отдаваемый на съедение канонизатору, который из ЛК на входе пытается сделать ОДЛК на выходе. Несложно заметить, что квадрат (в) отличается от квадрата (а) поворотом нетривиального латинского подпрямоугольника размером 2х3, т.е. сделанные ранее преобразования поворота интеркалятов и нетривиальных подпрямоугольников являются частными случаями преобразования по замене трансверсалей.

DimOK отреагировал на эту запись.
DimOK
Цитата: kotenok2000 от 05.06.2020, 06:51

в статусе сервера "research progress" был 17 процентов а потом стал 7.

Я периодически забираю старые WU'шки для анализа результатов и добавляю новые, поэтому на этот % лучше не ориентироваться. В месячных отчетах я публикую % числа исследованных окрестностей обобщенных симметрий (например, см. https://vk.com/wall162891802_1221 — "пройдено 457 (+29) окрестностей из 903 (50,6%, +3,2%)"), он более правильно отражает динамику выполнения данного эксперимента.

Как уже было неоднократно отмечено ранее, обобщенные симметрии можно описывать перестановками (Px,Py,Pv), задающими соответствие между всеми элементами квадрата

x1 = Px(x2)
y1 = Py(y2)
v1 = Pv(v2)

(в простейшем случае, без рассмотрения других парастрофических срезов). Каждая такая группа перестановок описывает соответствующий автоморфизм для квадрата, а если есть автоморфизм, значит (казалось бы) есть причина для снижения мощности соответствующего класса изоморфизма. Однако это не всегда так. Точнее, так будет для всех ЛК, но не для всех ДЛК. Напомню, что класс изоморфизма ДЛК (главный класс), в котором свойства всех квадратов одинаковы, формируется M-преобразованиями, а они в свою очередь могут быть описаны через M-перестановки.
Для примера рассмотрим 3 перестановки:

P1 = [9 8 7 6 5 4 3 2 1 0] со структурой мультимножества длин циклов S = {2, 2, 2, 2, 2} = {2:5},
P2 = [0 1 2 3 4 5 6 7 8 9], S = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} = {1:10},
P3 = [0 2 3 1 5 6 4 8 9 7], S = {1, 3, 3, 3} = {1, 3:3}.

Перестановки P1 и P2 являются M-перестановками, а P3 — нет. Отсюда можно сделать очень простое наблюдение: если какая-либо обобщенная симметрия описывается комбинацией M-перестановок, то соответствующая мощность главного класса уменьшается, а выбранной комбинации перестановок можно однозначно сопоставить одну из ESODLS схем (будем называть такие обобщенные симметрии M-симметриями). Разумеется, за исключением тривиального случая (P1,P1,P1). Если же хотя бы одна из перестановок не является M-перестановкой, то соответствующей обобщенной симметрии нельзя сопоставить ESODLS схему и уменьшния мощности главного класса не происходит. Например, квадрат

0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 3 5 8 1 4 6 9 7
4 6 9 7 1 8 2 0 3 5
9 7 8 6 5 4 3 1 2 0
3 4 7 8 0 9 1 2 5 6
6 9 4 1 7 2 8 5 0 3
7 8 5 0 6 3 9 4 1 2
5 3 1 9 2 7 0 8 6 4
8 5 6 2 9 0 7 3 4 1

(линия-3, 2 КФ), обладающий горизонтальной симметрией, с позиции обобщенных симметрий описывается перестановками (P2,P1,P1) (или, что то же самое по типам циклов — (1,31,31)), ему соответствует ESODLS схема № 2 со структурой циклов {2:50} и мощность класса изоморфизма 7680 (в 2 раза меньше максимальной).

Квадрат

0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 7 9 5 6 3
7 5 4 2 9 1 8 3 0 6
2 7 8 1 0 3 5 6 9 4
8 6 3 9 5 0 7 4 2 1
9 4 5 8 2 6 1 0 3 7
5 0 9 7 6 4 3 8 1 2
6 3 1 5 7 8 2 9 4 0
3 8 6 0 1 9 4 2 7 5
4 9 7 6 3 2 0 1 5 8

(звезда 1:10, 6 КФ) обладает обобщенной симметрией типа (4,31,31), ему соответствует ESODLS схема № 398 со структурой циклов {2:50} и мощность класса изоморфизма 7680 (в 2 раза меньше максимальной).

С другой стороны, квадрат

0 1 2 3 4 5 6 7 8 9
5 9 8 0 2 4 3 6 1 7
8 7 1 4 3 9 2 0 5 6
1 6 9 2 7 8 5 3 4 0
6 0 3 8 5 7 4 2 9 1
4 5 6 7 8 3 1 9 0 2
2 4 5 6 9 0 7 1 3 8
7 3 4 9 1 6 0 8 2 5
9 2 7 5 0 1 8 4 6 3
3 8 0 1 6 2 9 5 7 4

(однушка, ESODLS от транспонирования от побочной диагонали) обладает обобщенной симметрией класса (27,27,27) со структурой циклов как в P3, однако ему не соответствует M-симметрий и ESODLS схем (кроме тривиальной), мощность его класса изоморфизма максимальна и равна 15360.

PS. Утверждение "Если квадрат обладает K различными M-симметриями (с соответствующими им нетривиальными ESODLS схемами), то мощность соответствующего ему главного класса = Максимально_возможная_мощность_для_данной_размерности_N / 2^K" неверно. Контрпример:

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

Соответствующие ESODLS схемы (кроме тривиальной):
1. Automorphic schema 3
2. Automorphic schema 12
3. Automorphic schema 15
4. Automorphic schema 20
5. Automorphic schema 23
6. Automorphic schema 24
7. Automorphic schema 27

Теоретически максимальная мощность главного класса для N=5 — 32.
Мощность главного класса для приведенного квадрата — 4.

32 / 2^7 != 4

Что и требовалось доказать.

НазадСтраница 28 из 190Далее
BOINC.RU