Статьи о латинских квадратах

Message boards : Science : Статьи о латинских квадратах
Message board moderation

To post messages, you must log in.

Previous · 1 · 2 · 3 · 4 · Next

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5413 - Posted: 1 Apr 2020, 4:44:32 UTC
Last modified: 1 Apr 2020, 7:17:44 UTC

Ссылка
E. I. Vatutin, About the number of SODLS of order 10 (in Russian)
у меня не действует, потому что сайт на поддерживает мой браузер.
Может быть, по этой ссылке можно как-то увидеть все SODLS 10-го порядка.

Кстати, Ватутин добавил количество SODLS 10-го порядка в OEIS совсем недавно
a(10) from Eduard I. Vatutin, Mar 14 2020

Ну, если он это количество посчитал, значит, и все ДЛК у него имеются.
Хотя... ХЗ :)
Квадратов довольно много, может, просто посчитал, но квадраты не сохранил (?)
Очень плохо, если так.
Результат должен быть подтверждён независимым исследователем.
А для проверки квадраты-то нужны.
ID: 5413 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5414 - Posted: 1 Apr 2020, 5:07:20 UTC
Last modified: 1 Apr 2020, 6:01:33 UTC

Ох ... (самоцензура; произнесла мысленно)

Оказывается Ватутин уже "нашёл" и число главных классов SODLS 10-го порядка!!!
Смотрим последовательность https://oeis.org/A329685
A329685 Number of main classes of self-orthogonal diagonal Latin squares of order n.
1, 0, 0, 1, 1, 0, 2, 8, 470, 30534

Однако у Белышева другой результат, он писал на форуме boinc.ru:
Написал программу. Было найдено 30534 SODLS, из них существенно различных 30502.

То есть, главных классов должно быть 30502, а не 30534.

Вот поэтому я и говорю о подтверждении выше означенного результата общего количества нормализованных SODLS 10-го порядка.
Где тут правильно с главными классами? У Ватутина или у Белышева?
Да, Белышев нашёл 30534 SODLS 10-го порядка, но канонизация этих SODLS дала только 30502 КФ. Это и есть количество главных классов.
По Ватутину главных классов 30534; значит, Белышев не все главные классы нашёл???
Скорее всего, Белышев всё правильно нашёл, это Ватутин неправильно "перенашёл".

Следует выяснить, как правильно и исправить ошибку в OEIS, если она имеет место.

А проверить-то элементарно! Ватутин предоставляет найденные им 30534 существенно различных SODLS 10-го порядка (уж эти-то ДЛК у него точно должны быть); эти ДЛК надо канонизировать и получить правильный результат.
Почти уверена, что этот результат будет совпадать с результатом Белышева.

Плохо, что в OEIS не требуют прикреплять результаты.
Там же есть такая возможность! Сама в OEIS создала десятки последовательностей. Результаты прикрепляются в файле a.file
ID: 5414 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5415 - Posted: 1 Apr 2020, 6:00:44 UTC

Напомню, что Белышев свои результаты выложил на Яндекс.Диск.

Здесь 30502 КФ SODLS (то есть как раз главные классы)
https://yadi.sk/d/OiKwfw2b3Gan9x

А вот здесь 30534 SODLS, найденные им
https://yadi.sk/d/l4Fus2cp3GTqe2

Не эти ли 30534 SODLS Ватутин выдал за главные классы???
Проверить очень просто!
ID: 5415 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5416 - Posted: 1 Apr 2020, 9:47:36 UTC
Last modified: 10 Apr 2020, 17:22:05 UTC

Снова цитата из моей статьи
Как я понимаю из последовательности OEIS, для порядка 10 имеется 234,501,120 нормализованных SODLS.
Подтверждение этого результата в других источниках я не встречала.
Интересно: а что даёт канонизатор для этих 234,501,120 нормализованных SODLS 10-го порядка?
Выше приведены все КФ SODLS 10-го порядка, найденные Белышевым (30502 КФ).
Вот и надо проверить. Если 234,501,120 нормализованных SODLS 10-го порядка – это правильно найдено, то канонизация этих ДЛК должна дать 30502 КФ SODLS.
Если это не получится именно так, то: либо количество SODLS 234,501,120 неправильное, либо 30502 КФ SODLS – не все.
К сожалению, проверить это по данным последовательности невозможно, потому что есть количество, но нет самих SODLS.

Хм...
Кажется, я знаю, как Ватутин посчитал общее количество нормализованных SODLS 10-го порядка.
Он взял количество главных классов (которое у него равно 30534) и умножил это количество на 15360/2=7680.

Теперь осталось доказать, что количество главных классов у Ватутина правильное.
А если это не так, и количество главных классов равно 30502 (как у Белышева), тогда и общее количество нормализованных SODLS тоже неправильное.
В этом случае общее количество нормализованных SODLS равно
30502*7680=234255360

Ну, и на десерт: я совсем не уверена, что каждый главный класс SODLS 10-го порядка содержит ровно 7680 нормализованных SODLS.
Вероятно, Ватутин это доказал, но мне доказательство неведомо.

Для SODLS 9-го порядка это точно не так.
Каждый класс эквивалентности ДЛК 9-го порядка содержит 1536 ДЛК.
Если их все нормализовать (в каждом главном классе), будут ли они все различны (в данном классе)?
В каких-то классах - да, будут, но не во всех.
Количество главных классов SODLS 9-го порядка равно 470, а общее количество нормализованных SODLS равно 224832.
Это число не совпадает с числом 470*768.
Сильно подозреваю, что для SODLS 10-го порядка будет так же.
ID: 5416 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5417 - Posted: 1 Apr 2020, 9:49:58 UTC
Last modified: 6 Apr 2020, 18:02:56 UTC

Всё это надо выяснить.
Поскольку не могу написать вопрос в OEIS, написала письмо Максу Алексееву (редактору OEIS).
Жду ответ.

PS. Пока тишина, Макс не ответил.
Запостила вопрос и на форуме boinc.ru, поближе к автору последовательности OEIS.
Надеюсь, что это поможет уточнить результат и исправить его, если он неправильный.
ID: 5417 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5424 - Posted: 6 Apr 2020, 18:14:30 UTC
Last modified: 7 Apr 2020, 5:39:53 UTC

Наткнулась на просторах Интернета на статью:

Beley.pdf
Это документ с сайта http://mit.spbau.ru

О ВЫЧИСЛИТЕЛЬНОМ ПОИСКЕ КВАЗИОРТОГОНАЛЬНЫХ СИСТЕМ
ЛАТИНСКИХ КВАДРАТОВ, БЛИЗКИХ К ОРТОГОНАЛЬНЫМ СИСТЕМАМ
Белей Е.Г.
Институт математики, экономики и информатики
Иркутского государственного университета.

Abstract.
Работа посвящена исследованию возможностей применения современных алгоритмов вычислительной логики к задачам поиска комбинаторных структур. Конкретно, рассматривается известная открытая комбинаторная задача о существовании тройки попарно ортогональных латинских квадратов 10-го порядка. Предлагается схема поиска такой тройки в форме итеративной процедуры, на каждой итерации которой строятся т.н. квазиортогональные системы. Вводится специальная характеристика близости квазиортогональной системы кортогональной, называемая индексом ортогональности.
Искомая ортогональная тройка латинских квадратов порядка 10, если она существует, является квазиортогональной системой с индексом ортогональности 100. В работе построены семейства квазиортогональных систем с индексом ортогональности до 80 включительно. Для этой цели использованы алгоритмы решения задачи о булевой выполнимости (SAT).

Нигде не нашла год опубликования этой статьи.
Но в списке приведённых статей есть такая статья
[30] Zaikin, O., Kochemazov, S., Semenov, A.: SAT-based search for systems of diagonal latin squares in
volunteer computing project sat@home // In Proc. of 39th International Convention on Information
and Communication Technology, Electronics and Microelectronics, MIPRO 2016, Opatija, Croatia, May
30 - June 3, 2016 pp. 277–281.

Следовательно, исходная статья написана не раньше 2016 г. (по моей логике).

Хорошо известные нам псевдотройки в рассматриваемой статье названы квазиортогональными системами.
Цитирую
В работе построены семейства квазиортогональных систем с индексом ортогональности до 80 включительно.

Я нашла псевдотройку с характеристикой ортогональности 82 в 2016-2017 гг. (точно не помню, но это можно посмотреть на форуме Math Help Planet в теме "Ортогональные латинские квадраты 10-го порядка".
14 ноября 2018 г. мной найдена псевдотройка с характеристикой ортогональности 88. Это мой личный рекорд; возможно, что и рекорд российский.
ID: 5424 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5425 - Posted: 6 Apr 2020, 18:26:21 UTC
Last modified: 7 Apr 2020, 5:48:57 UTC

Вот моя рекордная псевдотройка ЛК 10-го порядка с характеристикой ортогональности 88

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

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

Это в формате программы Беляева, с помощью которой я и искала псевдотройки.
Здесь мы видим, что исходный ЛК псевдотройки имеет всего два ортогональных соквадрата (sq=2).
А алгоритм поиска исходного ЛК - в симметрии (27,27,27).
После того, как Белышев описал симметрию (27,27,27), я сразу же увидела, что рекордная псевдотройка с характеристикой ортогональности 91 (мировой рекорд) обладает этой симметрией.
Ну, и далее начала проверять все ЛК с данной симметрией.
Был получен результат - псевдотройка с характеристикой ортогональности 88.
Исходный ЛК данной псевдотройки уникален, то есть он не изоморфен исходному ЛК псевдотройки с характеристикой ортогональности 91.

Другой формат псевдотройки с характеристикой ортогональности 88, это тоже формат программы Беляева

1 cm=88
 0 2 3 1 8 9 7 5 6 4
 6 1 9 2 4 3 5 7 0 8
 4 3 2 7 6 5 1 9 8 0
 5 8 1 3 2 4 6 0 7 9
 1 4 6 9 7 0 3 8 2 5
 2 7 5 4 1 8 0 6 9 3
 3 5 8 6 0 2 9 1 4 7
 7 0 4 8 9 6 2 3 5 1
 8 9 0 5 3 7 4 2 1 6
 9 6 7 0 5 1 8 4 3 2

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

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

Интересно: все три ЛК псевдотройки обладают симметрией (27,27,27).
И не только такая симметрия у этих ЛК!
Вот что выдаёт программа поиска симметрий find_symm_3.0 (Белышев)

Поиск симметрий ЛК10 версия 3.0

Обработано ЛК: 3
Время работы : 0.015 сек

Введите код симметрии: all

Квадратов с симметрией (27,27,27) найдено: 3 они записаны в файл symm_27_27_27.txt
Квадратов с симметрией (1,1,8)+ найдено: 1 они записаны в файл symm_1_1_8p.txt
Квадратов с симметрией (1,27,28)+ найдено: 1 они записаны в файл symm_1_27_28p.txt
ID: 5425 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5426 - Posted: 6 Apr 2020, 19:03:18 UTC
Last modified: 7 Apr 2020, 19:21:12 UTC

Сейчас бродила в поиске статей о ЛК в Яндексе.
Вот что увидела

Предлагаю вашему вниманию свою статью «Системы из N попарно ортогональных диагональных латинских квадратов 10-го порядка с полной ортогональностью (N-1) пар». Статья на русском языке, написана в октябре 2016 г.
Скачать статью здесь https://yadi.sk/i/S417t0IpwnP6r

Посмотрела эту тему; кажется, данной статьи здесь нет. Если пропустила, пусть будет ещё раз.
Спасибо Яндексу, что проиндексировал статью, вот и мне напомнил :)

Итак, смотрите предлагаемую статью. Она написана давно (в 2016 г.), можно сказать, на заре поиска ОДЛК 10-го порядка трансверсальным методом.
Ещё не было BOINC-проектов ОДЛК и ODLK1; данные для анализа взяты из наших с Белышевым экспериментов.

PS. Проверила ссылку; статья на Яндекс.Диске лежит.
Интересно:
Информация о файле

Имя: Системы из N попарно ортогональных диагональных латинских квадратов 10.pdf
Размер: 613 КБ
Изменён: 13.10.2016 20:44
Просмотры: 494
Скачан: 20 раз

Полюбопытствовали чуть-чуть (494), скачали - совсем почти никто (20).
Весьма малый интерес наблюдаю к данной статье, и не только к данной.
Ну, писать-то всё равно надо. Пусть сейчас не читают, может, позже...
Кто знает...

PS. А, вспомнила...
В начале этой темы была ссылка на данную статью в подписи под сообщениями.
Потом я убрала эту ссылку (один кранчер пожаловался, что вот захожу, мол, на ваш форум, а у меня начинает что-то загружаться с Яндекс...; разумеется, это не может само начать загружаться, на ссылку надо было кликать. Ну да ладно, всё равно убрала, давно уже).
ID: 5426 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5427 - Posted: 6 Apr 2020, 19:08:33 UTC
Last modified: 6 Apr 2020, 19:08:42 UTC

Анонсирую свою новую статью "SOLS и SODLS".
Скоро завершу написание, выложу.
Следите!
ID: 5427 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5429 - Posted: 9 Apr 2020, 10:54:28 UTC

Цитата
Всё это надо выяснить.
Поскольку не могу написать вопрос в OEIS, написала письмо Максу Алексееву (редактору OEIS).
Жду ответ.

PS. Пока тишина, Макс не ответил.
Запостила вопрос и на форуме boinc.ru, поближе к автору последовательности OEIS.
Надеюсь, что это поможет уточнить результат и исправить его, если он неправильный.

Ничего пока не помогло. Письмо Алексееву написано 8 дней назад. Ни ответа, ни привета!
Уточнить результат некому.
Сейчас написала письмо администратору OEIS, больше пока ничего не придумала.
Если и от администратора не будет ответа, придётся клонироваться в OEIS :)

Приведу текст письма администратору OEIS, чтобы не быть голословной

Hello, Neil!

In sequence https://oeis.org/A329685
there is a value a(10) = 30534

I know another result by Belyshev
a(10) = 30502

This result can be seen here.
https://yadi.sk/d/OiKwfw2b3Gan9x

It is necessary to clarify which result is correct.

I have already addressed this question to Max Alekseyev. I have not received an answer.
I hope you resolve this issue.

Natalia Makarova

PS. Unfortunately, I am blocked in OEIS and cannot ask a question there.

Проблема пустяковая, но решать никто не хочет: ни автор последовательности Ватутин, ни редактор OEIS Алексеев.
Всем как бы до лампочки.
Посмотрим, что ответит администратор и ответит ли.
ID: 5429 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5430 - Posted: 9 Apr 2020, 19:41:35 UTC

Уф! Наконец-то я её закончила :)
Статья писалась со скрипом, не знаю - почему.
Может быть, творческий кризис в связи со всеми последними событиями, которые вызвали очень много отрицательных эмоций.
Может быть, потому, что тема сложная - анализ эмпирики и классификация на основе этого анализа.

Ну, в общем, статья "SOLS и SODLS" здесь
https://cloud.mail.ru/public/W9od/3og3hgMzB

Архив содержит
а) статья SOLS.pdf;
б) файл SODLS10plus.txt (33775 КФ ОДЛК);
в) программа Белышева denamer.exe

Архив небольшой, 1,49 Мб.

Уважаемые коллеги и все, кто интересуется данной темой!
Прошу прислать мне отзыв о статье.
Буду признательна за сообщения о замеченных ошибках.
А также сообщите мне, пожалуйста, если вы найдёте контрпример для опровержения моей гипотезы.

К Белышеву
я понимаю, что приведённая мной классификация SODLS 10-го порядка на основе эмпирических данных несовершенна.
Буду очень рада, если вы улучшите эту классификацию, применив мощный теоретический аппарат.
Сообщите мне, пожалуйста, если вы сделаете такую классификацию.
ID: 5430 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5431 - Posted: 9 Apr 2020, 19:53:03 UTC
Last modified: 9 Apr 2020, 19:55:55 UTC

Загрузила архив и на Яндекс.Диск
https://yadi.sk/d/nvdI6TgBrKv72A

Сейчас проверю, как работает.
Вроде всё нормально.

Пишите мне!
ID: 5431 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5432 - Posted: 10 Apr 2020, 4:21:12 UTC
Last modified: 10 Apr 2020, 4:23:36 UTC

Вот с утречка и вспомнила :) что забыла в статье написать...

Francis Gaspalou писал мне:
Please note also that all SODLS of order 4, 5, 7 and 8 are doubly SODLS and it is only for the order 9 that we can make the difference between singly SODLS and doubly SODLS.


И кандидат на последовательность в OEIS - для doubly SODLS до порядка 10 включительно, главные классы
1, 0, 0, 1, 1, 0, 2, 8, 88, 0

Напоминаю: все результаты, кроме последнего, получены Francis Gaspalou.
Я предложила Francis создать эту последовательность; он не хочет, написал, что не является поклонником OEIS.

PS. Здесь, в теме я писала об этом.
Ссылка на эту тему в статье указана.
ID: 5432 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5433 - Posted: 10 Apr 2020, 7:04:58 UTC
Last modified: 10 Apr 2020, 8:15:40 UTC

Прочитала статью в формате pdf (писала я её, конечно, в Ворде).
Заметила одну орфографическую опечатку, но шут с ней.
А это опечатка в ссылках:
30354 SODLS 10-го порядка, найденные А. Белышевым от 121642 SOLS 10-го порядка
https://yadi.sk/d/l4Fus2cp3GTqe2

Должно быть 30534, цифры переставила.
Несколько огрехов с иллюстрациями: обрезаны, но не критично, всё можно понять.
В остальном вроде всё в порядке - на мой авторский взгляд :)

Жду ваших замечаний, господа.
ID: 5433 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5434 - Posted: 10 Apr 2020, 15:57:57 UTC

Обращение к администратору OEIS возымело действие.
Последовательность https://oeis.org/A329685 исправлена Алексеевым.
Прикреплён и файл с 30502 КФ SODLS.
Только Макс не указал автора этого результата - Белышева.
Написала ему просьбу указать автора.
ID: 5434 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5435 - Posted: 10 Apr 2020, 16:49:54 UTC
Last modified: 10 Apr 2020, 17:20:54 UTC

Цитата
Хм...
Кажется, я знаю, как Ватутин посчитал общее количество нормализованных SODLS 10-го порядка.
Он взял количество главных классов (которое у него равно 30534) и умножил это количество на 15360/2=7680.

Теперь осталось доказать, что количество главных классов у Ватутина правильное.
А если это не так, и количество главных классов равно 30502 (как у Белышева), тогда и общее количество нормализованных SODLS тоже неправильное.
В этом случае общее количество нормализованных SODLS равно
30502*7680=234255360

Ну, и на десерт: я совсем не уверена, что каждый главный класс SODLS 10-го порядка содержит ровно 7680 нормализованных SODLS.
Вероятно, Ватутин это доказал, но мне доказательство неведомо.

Так и...?
Что же Ватутин не исправляет связанную последовательность
https://oeis.org/A287761?
Член а(10) теперь будет равен не 234501120.

А там ещё одна связанная последовательность
https://oeis.org/A287762

И всю ли цепочку я проследила?
Вот же... наплодил Ватутин последовательностей, а работать над исправлением ошибок не желает.
Кто-то должен за него это делать.
ID: 5435 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5436 - Posted: 10 Apr 2020, 19:30:38 UTC
Last modified: 10 Apr 2020, 20:30:27 UTC

В последовательности https://oeis.org/A287761
написано
a(i) != A329685(i)*A299784(i)/2 for i=1..9 due to the existence of doubly self-orthogonal diagonal Latin square (DSODLS) and/or generalized symmetries (automorphisms) for some SODLS.
a(10) = A329685(10)*A299784(10)/2 because no DSODLS exist for order n=10 and no SODLS of order n=10 have generalized symmetries (automorphisms).

Размышляю...
Для порядка 10 не существует DSODLS, это верно.
А вот это
... and no SODLS of order n=10 have generalized symmetries (automorphisms).

(перевожу)
... и никакие SODLS порядка n = 10 не имеют обобщенных симметрий (автоморфизмов).

Вообще-то некоторые SODLS 10-го порядка обладают симметрией (27,27,27), как утверждает программа Белышева
Поиск симметрий ЛК10 версия 3.0

Обработано ЛК: 30502
Время работы : 2.062 сек

Введите код симметрии: all

Квадратов с симметрией (27,27,27) найдено: 16 они записаны в файл symm_27_27_27.txt

Других обобщённых симметрий не обнаружено у SODLS 10-го порядка.
Хотя это очень специфическая симметрия, тем не менее, говорить, что никакие SODLS 10-го порядка не имеют обобщённых симметрий, нельзя.

В общем, вопрос о количестве нормализованных SODLS 10-го порядка в каждом главном классе для меня пока остаётся открытым.
Я не вижу, откуда следует, что это количество для каждого класса равно 15360/2=7680.
Может быть, оно и так. Но мне нужно доказательство этого утверждения.
ID: 5436 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5437 - Posted: 10 Apr 2020, 19:50:53 UTC
Last modified: 10 Apr 2020, 19:55:45 UTC

Взяла первый из списка SODLS, обладающий симметрией (27,27,27)

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

И вот какие автоморфизмы
** 0123456789 0123456789 0123456789 -> (1,1,1)
** 5481392760 9327068154 8540672139 -> (27,27,27)
** 9364108725 4721985360 3768214509 -> (27,27,27)

Всё правильно: симметрией обладает, автоморфизмов аж два (не считая тождественного).

Главный класс, содержащий показанный SODLS, содержит 15360 различных нормализованных ДЛК и 7680 нормализованных SODLS.

Но будет ли так для всех главных классов???
ID: 5437 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5445 - Posted: 12 Apr 2020, 18:26:43 UTC
Last modified: 12 Apr 2020, 19:34:17 UTC

Вот ещё одна связанная последовательность OEIS
https://oeis.org/A299784

A299784 Maximal size of main class for diagonal Latin squares of order n with first row 1..n.
1, 0, 0, 2, 4, 96, 192, 1536, 1536, 15360

Прежде всего обратите внимание: это максимальный размер главных классов.
То есть, в главном классе ДЛК 10-го порядка может быть максимально 15360 изоморфных ДЛК с фиксированной первой строкой (то бишь - нормализованных).
Но может быть и меньше, так надо понимать?
Ну, вот и я о том же выше писала.

Теперь рассмотрим статью

E. Vatutin, A. Belyshev, S. Kochemazov, O. Zaikin, N. Nikitina
Enumeration of Isotopy Classes of Diagonal Latin Squares of Small Order Using Volunteer Computing

Статью смотрю здесь
https://link.springer.com/chapter/10.1007%2F978-3-030-05807-4_49

Abstract
The paper is devoted to discovering new features of diagonal Latin squares of small order. We present an algorithm, based on a special kind of transformations, that constructs a canonical form of a given diagonal Latin square. Each canonical form corresponds to one isotopy class of diagonal Latin squares. The algorithm was implemented and used to enumerate the isotopy classes of diagonal Latin squares of order at most 8. For order 8 the computational experiment was conducted in a volunteer computing project. The algorithm was also used to estimate how long it would take to enumerate the isotopy classes of diagonal Latin squares of order 9 in the same volunteer computing project.


Перевожу в Гугле:

Статья посвящена открытию новых особенностей диагональных латинских квадратов малого порядка. Мы представляем алгоритм, основанный на специальном виде преобразований, который строит каноническую форму заданного диагонального латинского квадрата. Каждая каноническая форма соответствует одному изотопическому классу диагональных латинских квадратов. Алгоритм был реализован и использовался для перечисления изотопических классов диагональных латинских квадратов порядка не более 8. Для порядка 8 вычислительный эксперимент проводился в проекте для добровольных вычислений. Алгоритм также использовался для оценки того, сколько времени потребуется, чтобы перечислить изотопические классы диагональных латинских квадратов порядка 9 в том же вычислительном проекте для добровольцев.

Чтобы найти вот эти числа
1, 0, 0, 2, 4, 96, 192, 1536, 1536, 15360
был задействован проект добровольных вычислений.
Это круто!
Ещё более круто: "открытию новых особенностей диагональных латинских квадратов малого порядка".
Это "открытие" было опубликовано в книге Ю. В. Чебракова "Магические квадраты. Теория чисел, Алгебра, Комбинаторный анализ" (С. - Петербург, 1995).
"Специальный вид преобразований", который представляют авторы статьи, это так называемые М-преобразования (в терминологии Ю. В. Чебракова).
Белышев прекрасно знает, как в самом начале нашего с ним сотрудничества мы (независимо друг от друга) установили, что в каждом классе эквивалентности ДЛК 10-го порядка может быть 15360 изоморфных ДЛК.
[Знают об этом и другие авторы статьи, потому что я писала это на форуме boinc.ru. Жалко, что форум сдох, а то цитату бы привела.]
Именно отсюда и произошла каноническая форма (КФ) ДЛК.
Находится каноническая форма ДЛК очень просто: сначала находим все 15360 изоморфов данного ДЛК, применяя те самые М-преобразования плюс основные преобразования. Затем нормализуем все найденные изоморфы.
Наконец, выбираем среди нормализованных изоморфов наименьший ДЛК в лексикографическом порядке. Это и будет КФ данного ДЛК.

Белышев реализовал этот алгоритм сразу же, как были определены все изоморфы ДЛК 10-го порядка.
Для других порядков всё совершенно аналогично.
И для чего же здесь был задействован проект добровольных вычислений?
Всё это можно вычислить даже на калькуляторе!
И при чём здесь все остальные авторы, кроме Белышева? Они что в этой статье писали? Что вычисляли?
У меня нет слов, одни непечатные восклицания.

Далее, смотрим на количества
1, 0, 0, 2, 4, 96, 192, 1536, 1536, 15360

a(7) - a(10) сомнений не вызывают, это правильные значения.
Для членов a(4) - a(6) у меня большие сомнения в их правильности.
Необходимо уточнить и исправить, если эти члены неправильные.

Белышеву прежде всего надо озаботиться уточнением этих результатов.
Ссылка в последовательности OEIS https://oeis.org/A299784 дана как раз на эту статью, соавтором (точнее: автором!) которой он является.

На господина Ватутина в плане уточнения и исправления нет никаких надежд.
Он, похоже, ничего исправлять вообще не собирается.
Я выше указала две связанные последовательности
https://oeis.org/A287761
https://oeis.org/A287762
которые необходимо исправить в связи с уже исправленной ошибкой в последовательности https://oeis.org/A329685.
Пока в этих последовательностях никто исправления не начинал вводить.
ID: 5445 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13606
Credit: 0
RAC: 0
Message 5446 - Posted: 12 Apr 2020, 19:06:26 UTC
Last modified: 12 Apr 2020, 20:31:51 UTC

Согласно таблице количества М-преобразований, приведённой в указанной выше книге Ю. В. Чебракова (стр. 67),
a(4) - a(6) должны иметь следующие значения

a(4)=32
a(5)=32
a(6)=192

В последовательности OEIS https://oeis.org/A299784 имеем
a(4)=2
Главный класс ДЛК 4-го порядка может иметь максимально всего два нормализованных изоморфа???
Что-то я сильно сомневаюсь в этом.

В книге Ю. В. Чебракова приведены 4 варианта квадрата 4-го порядка, полученные М-преобразованиями.
Ну, и умножаем ещё на 8 (основные преобразования). Итого: 32 изоморфа.

Завтра проверю для этого ДЛК 4-го порядка

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

Напишу 4 варианта квадратов, полученных М-преобразованиями по Чебракову, потом нормализую, потом применю основные преобразования, снова нормализую.
Вдруг после всех этих преобразований останется всего два различных нормализованных ДЛК (???)

Проверить надо также значения членов последовательности для порядков 5 и 6.
И для порядка 8 засомневалась уже :)

У ДЛК 4-го порядка сплошные симметрии, визуально уже вижу, завтра всё распишу подробно.
А у ДЛК 8-го порядка не будет таких симметрий?
ID: 5446 · Rating: 0 · rate: Rate + / Rate - Report as offensive
Previous · 1 · 2 · 3 · 4 · Next

Message boards : Science : Статьи о латинских квадратах


©2024 (C) Progger