Исследования свойств латинских квадратов
Без учёта "холостяков" программа LsEdit выдаёт примеры ДЛК для 36 схем ОДЛК. Канонические имена эти ДЛК вместе с соответствующими компонентами ортогональности приведены ниже в порядке перечисления схем ОДЛК в программе LsEdit (от None symmetric once до Stingray).
2) aFmsrPJHKCnqKo4Z7Lvrbz6eK -> #36
3) FmT689WLk3CTvvY6pJB3gPnut -> #10
4) 3jWHkJAk25ybG1mvzGfDG2rG1 -> #29
5) 64iVV9NCnE6DsmJz7MsrgpqBf -> #11
6) Jggf6rLRdCw6i4uAp4saVkSmn -> #19
7) 1Hg9FXBiRB6n4quyCQDR3DXf1 -> #18
3N2dJS6TjKmGiuHUs3Z7E3mxZ -> #389) G2fpBZWgMGvCK6LGFCF8S7fb5 -> #37
10) 3soRrGbsrD5HUifU85zN26oJP -> #31
11) 61yzSP1Hn3H1dyufxSeb3HqUU -> #20
12) RruqQiAiw3NkyHj2NNg82RYXk -> #9
13) Tc428wyf93y5gDUg766nJQiHV -> #8
14) 3jWKcedU6JqeMkLo6PNHgzMiE -> #27
15) 5tUqqVuGzBQ6AKRinDNpAi33J -> #6
16) A843rBb2hD4pJ5wV44oDTSAJ3 -> #5
17) 3tkr2aiuHE9is7BrD7EtCtPhC -> #25
18) AD5tvGqFTGRHPyLEsDvykeKdZ -> #3
19) 1h9VXz9ciDjtHW3Y1S2cXb8nS -> #2
20) 1Hg8z7c2n1NNonniqLpHKvHBA -> #24
21) H1ixpc8i97pghpiyWJAVGWpYw -> #23
22) UZ96gRAftFCFyCxVs5NBhGe8q -> #22
23) 3smTUk1nX1bCMNkWpMufgjcZ2 -> #30
24) 1kEzwCRL81YFg3ew7KnQJZCF9 -> #32
25) 2y8DEukBP1wCWpd97PVUNUquv -> #21
26) C8TGSGHfkGUP7CPDm5G5REQpp -> #33
27) C2ds6UbFCRd9Ljn54NGumRZUK -> #12
28) 3yzRVoaTbDdQNwoeXS2AivxzZ -> #28
29) 9xNXmH1Fs6V6gMPo64JkJTW76 -> #7
30) 326vS8mTDE7HSsy6987cin2Gr -> #13
31) 7dbjnoF1nCwuD9VkaGVLCzrPp -> #14
32) C2rKQUwX8Co4Tkx33L4Z98mDQ -> #17
33) H2nef6Sbj3fnkQYxp5zzW1Vrh -> #26
34) 1h9VXz9ciEGw1LSrZS2cWivFY -> #4
35) BtkjJxPg2ETb5LtfX5G1jfa6B -> #15
36) 8g2uBZp4JMBEVhK6bHHWquCuh -> #16
Отсутствуют схемы ОДЛК для КО #34, #35, #39 с представителями:
7U5Y1Xf7a6PwX2G6NGdQ6QwLM
1AFh9aUzTEbGKBM2e9XPedUaS
9s6RSEssP2EVc7dTUKbEVdBRZ
Первый распознаётся программой LsEdit как Rhombus-4(4 CFs), то есть этой схеме ОДЛК соответствуют как минимум две компоненты ортогональности — #30 и #34. С каноническими матрицами смежности:
|0 0 1 1|
|0 0 1 1|
|2 2 0 0|
|2 2 0 0|
|0 0 0 2|
|0 0 0 2|
|0 0 0 2|
|1 1 2 0|
Второй распознаётся как Loop-4(2 CFs), то есть и этой схеме ОДЛК соответствуют как минимум две компоненты ортогональности — #35 и #37. С каноническими матрицами смежности:
|0 2|
|2 0|
|1 1|
|1 1|
Третий можно было бы распознать как Rhombus-4(3 CFs), но такой схемы LsEdit не знает.
Итак, 39 компонент ортогональности получаются редукцией (возможно нулевой) 24 основных схем ОДЛК:
Line-3 -> #10, #29
Line-4 -> #11, #19
Line-5 -> #18
Loop-4 -> #20, #31, #35, #37, #38
Star-3 -> #9
Star-4 -> #8, #27
Star-5 -> #6
Star-6 -> #5, #25
Star-7 -> #3
Star-8 -> #2, #24
Star-10 -> #23
Rhombus-3 -> #22
Rhombus-4 -> #21, #30, #32, #34, #39
Rhombus-5 -> #33
Fish -> #12, #28
Cross -> #7
Flyer -> #13
Tree -> #14
Venus -> #17
Dedalus-8 -> #4
Dedalus-10 -> #26
Robot -> #15
Stingray -> #16
Так как в статье "Список комбинаторных структур из ДЛК порядка 10 на множестве отношения ортогональности" нет схем ОДЛК соответствующих КО #34, #35 и #39, то нужны следующие три примечания.
1) Цикл-4(2 КФ) распадается на два подвида:
рис. 1, например, 2nceygR79Mnc7sdUzShDkxSUi
рис. 2, например, 1AFh9aUzTEbGKBM2e9XPedUaS
2) Ромб-4(4 КФ) распадается на два подвида:
рис. 3, например, 1En4LSm2aHq5inc9DQCni3r2E
рис. 4, например, 7U5Y1Xf7a6PwX2G6NGdQ6QwLM
3) Новый вид Ромб-4(3 КФ):
рис. 5, единственный пример — 9s6RSEssP2EVc7dTUKbEVdBRZ
В качестве стандартного представителя симметрии (1,1,1)+ возьмём автоморфизм:
*T 0123456789 0123456789 0123456789
Тем самым задача перечисления ЛК10, обладающих симметрией (1,1,1)+, сводится к задаче перечисления ЛК10 симметричных относительно главной диагонали (обычно, именно такие ЛК и называются симметричными).
Очевидно, что всякий элемент главной диагональ должен быть представлен на ней чётным числом экземпляров. В самом деле, все элементы стоящие вне главной диагонали разбиваются на пары ввиду симметрии, то есть вне главной диагонали имеется чётное число элементов каждого вида. А так как имеется ровно 10 элементов каждого вида, то и на главной диагонали стоит чётное их число.
Поэтому все симметричные ЛК10 делятся на семь типов в зависимости от состава главной диагонали:
1) 10 одинаковых элементов;
2) 2,8;
3) 4,6;
4) 2,2,6;
5) 2,4,4;
6) 2,2,2,4;
7) 2,2,2,2,2.
Тип 1 содержит 396 существенно различных ЛК. Из них 98 имеют чистые симметрий, то есть они уже были проверены раньше при проверке соответствующих чистых симметрий. Оставшиеся 298 ЛК имеют группу автоморфизмов порядка два, с единственным нетривиальным автоморфизмом — транспонированием. Марьяжных ДЛК они не имеют.
Тут меня попросили прокомментировать пост
https://boinc.progger.info/odlk/forum_thread.php?id=130&postid=4844
Сразу замечу, что утверждение:
Как я понимаю, это оценка количества вариантов заполнения 9 строк СН ДЛК.
Количество вариантов заполнения 10 строк по идее должно быть таким же, потому что при заполненных 9 строках квадрата вариант заполнения 10-й строки всего один.
неверно. В действительности, 9-строчных заполнений больше чем 10-строчных, так как не всякое 9-строчное заполнение может быть расширено до 10-строчного, но если такое расширение возможно, то, действительно, вариант расширения только один. Убедиться в этом можно "поигравшись" с программой counter_var_row, приведённой в третьем посте данной темы.
Следовательно, число СН ДЛК линейки 51 можно оценить числом 1,548e+18, а число нормализованных ДЛК линейки 51 — числом 1,189e+21. Число же КФ ДЛК линейки 51 можно оценить числом 7,74e+16.
Выполним подобную оценку для всех 67 линеек ДЛК10 при размере выборки 10000. Результат под спойлером:
- первая колонка — номер линейки;
- вторая колонка — оценка числа СНДЛК;
- третья колонка — оценка числа нормализованных ДЛК;
- четвёртая колонка — оценка нижней границы числа главных классов ДЛК.
2 1.511E+018 1.161E+022 7.556E+017
3 1.217E+018 1.169E+021 7.609E+016
4 2.568E+018 9.862E+021 6.421E+017
5 2.567E+018 9.857E+021 6.417E+017
6 2.428E+018 1.865E+021 1.214E+017
7 2.212E+018 8.493E+021 5.529E+017
8 2.384E+018 9.156E+021 5.961E+017
9 2.217E+018 1.703E+022 1.108E+018
10 1.917E+018 7.36E+021 4.792E+017
11 2.548E+018 9.783E+021 6.369E+017
12 2.538E+018 9.746E+021 6.345E+017
13 2.505E+018 9.617E+021 6.261E+017
14 2.289E+018 1.758E+022 1.144E+018
15 1.251E+018 4.002E+020 2.605E+016
16 1.506E+018 1.157E+022 7.532E+017
17 2.499E+018 1.919E+022 1.25E+018
18 2.668E+018 1.024E+022 6.67E+017
19 1.294E+018 9.938E+021 6.47E+017
20 1.475E+018 1.133E+022 7.374E+017
21 2.404E+018 1.846E+022 1.202E+018
22 2.163E+018 8.305E+021 5.407E+017
23 2.205E+018 1.693E+022 1.102E+018
24 2.31E+018 1.774E+022 1.155E+018
25 2.368E+018 9.095E+021 5.921E+017
26 2.476E+018 1.901E+022 1.238E+018
27 2.675E+018 1.027E+022 6.688E+017
28 2.426E+018 1.863E+022 1.213E+018
29 2.473E+018 1.899E+022 1.236E+018
30 2.426E+018 1.863E+022 1.213E+018
31 2.494E+018 1.916E+022 1.247E+018
32 2.406E+018 9.238E+021 6.014E+017
33 2.406E+018 9.237E+021 6.014E+017
34 2.325E+018 8.926E+021 5.811E+017
35 2.346E+018 9.009E+021 5.865E+017
36 2.894E+018 9.262E+020 6.03E+016
37 2.841E+018 2.727E+021 1.775E+017
38 1.203E+018 3.851E+020 2.507E+016
39 1.416E+018 1.088E+022 7.082E+017
40 2.506E+018 9.621E+021 6.264E+017
41 2.555E+018 1.962E+022 1.277E+018
42 2.561E+018 9.836E+021 6.404E+017
43 3.066E+018 2.355E+022 1.533E+018
44 3.025E+018 2.323E+022 1.512E+018
45 3.103E+018 2.383E+022 1.552E+018
46 3.059E+018 2.349E+022 1.53E+018
47 2.645E+018 2.032E+022 1.323E+018
48 1.981E+018 1.522E+022 9.907E+017
49 1.533E+018 5.885E+021 3.832E+017
50 2.569E+018 3.946E+021 2.569E+017
51 1.511E+018 1.161E+021 7.557E+016
52 2.245E+018 8.619E+021 5.611E+017
53 1.332E+018 5.114E+021 3.329E+017
54 2.34E+018 1.797E+022 1.17E+018
55 2.278E+018 1.75E+022 1.139E+018
56 1.744E+018 1.34E+022 8.721E+017
57 1.531E+018 2.352E+022 1.531E+018
58 2.25E+018 3.456E+022 2.25E+018
59 2.41E+018 3.701E+022 2.41E+018
60 2.433E+018 3.737E+022 2.433E+018
61 2.082E+018 3.197E+022 2.082E+018
62 2.429E+018 3.73E+022 2.429E+018
63 2.392E+018 3.674E+022 2.392E+018
64 2.454E+018 1.885E+022 1.227E+018
65 2.498E+018 3.838E+022 2.498E+018
66 1.548E+018 2.377E+022 1.548E+018
67 2.43E+018 1.866E+022 1.215E+018
--------------------------------------------------
Всего: 1.496E+020 9.932E+023 6.466E+019
Так как почти все ДЛК имеют тривиальную группу автоморфизмов, то число главных классов ДЛК весьма близко к оценке нижней границе. Например, для порядка 9 имеется 5056994653507584 нормализованных ДЛК, поэтому нижняя граница числа главных классов ДЛК9 равна 3292314227544, что составляет 99,9996% от точного их числа (3292326155394).
Следовательно, число главных классов ДЛК10 (число КФ) можно оценить числом 6,47e+19.
Кто бы еще оценил, сколько будет считать проект ODLK1? Точность ответа не важна - возраст земли меньше.
Про TBEG вообще мрак. Взята одна линейка (51), а на выходе все, причем в каждой линейке получается больше, чем в исходной.
TBEG — это что?
Понятно. Там в новостях опубликовано следующее сообщение:
PADLS TOTAL rule 51 experiment results
Over three months, more than 700,000 unique CFs ODLS were found in the project
Из него следует, что для полного завершения проекта потребуется порядка 27 миллиардов лет.
Учитываешь, 700,000 unique CFs ODLS - это из всех линеек, а для 51 линейки намного намного меньше.
Так в начале ноября из пол лимона 51 линейки было 2636 штук.
Но это уже никакого значения не имеет.