Сложность по Арнольду

[Руст]

Обозначим для такого n многочлен $f_n(x)=\frac{(X+1)^n-1}{X}$. Максимальный период T(n) определяется как минимальное значение из условия, что $f_n(x)|X^{T(n)}-1$.
Разлагая этот многочлен на неприводимые, получаем, что T(n) должен быть делителем приведённого ранее выражения. Я считал, что здесь точное равенство, похоже ошибся. Правда не проверил делимость $(X^{10}+X^9+X^8+X^7+X^2+X+1)|(X^{341}-1)$.

[maxal]

Руст писал(а):

Обозначим для такого n многочлен $f_n(x)=\frac{(X+1)^n-1}{X}$. Максимальный период T(n) определяется как минимальное значение из условия, что $f_n(x)|X^{T(n)}-1$.

В таком виде это в точности утверждение Corollary 2.2 в статье A Characterization for the Length of Cycles of the N-Number Ducci Game.

[Руст]

Да это почти тавтология. К сожалению более легко вычисляемую формулу не удастся получить. Просто раскладывая f_n(x) на неприводимые множители, надо искать делители числа $T_i|2^{deg(f_i(X)}-1$ и найти среди них минимальный $f_i(X)|X^{T_i}-1$. Потом вычислить НОК этих чисел.

[Macavity]

Я читал в этом форуме об ошибках Арнольда. На самом деле он не нуждается в защите как ученый (так же, как, например, Джоконда имеет право сама выбирать кому нравиться, а кому нет).

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

Например:
Гипотеза том, что частное от деления наибольшего периода на величину n оказывается уменьшенной на 1 степенью двойки, к сожалению, неверна. Причем, в более раннем документе, где расчитываются циклы для n<=12 все кажется правильным. В более позднем, появляется исключение для n=23 (здесь уже расчет сделан для n<=28).
Если бы расчет был сделан для больших значений, то оказалось бы, что
для n=37: (период +1)= 3233097+1=2*11*179*821
период /37 +1= 87382=2*43691
Аналогично для n=47 и n=49.
Это уже совершенно неверно. Но это не есть "Сложность по Арнольду", это есть "Математический эксперимент по Арнольду". И это нормально "по Арнольду", а если не нравится, то спорьте о взаимоотношении математики и физике и как это взаимоотношение понимает Арнольд.

[Macavity]

Мне интересно другое, почему был выбран оператор именно такого вида и именно из него получались все построения. Лично мне, это все больше напомнило вариации на тему игры Конвея (верное имя?) "Жизнь". Только одномерный, замкнутый случай.
Ну хорошо, за базу взят оператор вращения вправо на 1 и сложение с исходным.
А почему вращать не влево?
Циклическое вращение влево на один разряд, это вращение вправо на n-1. И тогда, получаем для изоморфного случая с вращением влево оператор
A=1+q^n^-^1
Заметим, что логорифмическая функция будет все равно находится на том же уровне дерева максимального цикла, что и в исходном случае.

А почему бы не рассмотреть оператор общего вида - полином от q с коэффициэнтами 0 или 1?

[Macavity]

Руст.

Можно уточнить?

Руст писал(а):

Пусть c(n) означает минимальное число, для которого $X(n)=2^{c(n)}-1$ делится на n. Тогда максимальный период является делителем этого числа. В случае, когда c(n) чётное число некоторая степень от 1+T сводится к простому сдвигу и поэтому T(n) делится на n. Когда n является степенью простого числа Мерсена так же легко показать, что n|T(n). Первое число n, не являющиеся степенью числа Мерсена и c(n) нечётное это n=23. Однако и в этом случае период делится на n. Кандидатом для случая, когда n не делит T(n) является n=71 (с(n)=35=5*7 нечётное не простое).

Правильно ли я понял, что, по Вашему мнению, существуют такие простые n, для которых максимальный цикл не делится на n? И следовательно на n делится количество максимальных циклов?

И второй вопрос.
Фактически, Ваши формулы показывают, что надо взять все простые делители от 2^{n-1}-1 в разных комбинациях проверить путем перемножения является ли результат такого перемножения циклом для степени 1+T и наименьшее число-претендент и будет таким циклом? Или что-то не так?

[Руст]

1. Поняли правильно. Есть случаи (указанные выше), когда можно доказать делимость T(n) на n. Для других случаев я не вижу причины, почему T(n) должен делиться на n.
2. Не так. Выше приведены формулы вычисления и некоторые свойства делимости.

[Macavity]

Спасибо за ответ.

Руст писал(а):

1. Поняли правильно. Есть случаи (указанные выше), когда можно доказать делимость T(n) на n. Для других случаев я не вижу причины, почему T(n) должен делиться на n.

Не видите причин, пока это не доказано в общем случае

Руст писал(а):

2. Не так. Выше приведены формулы вычисления и некоторые свойства делимости.

Не все понял, пересмотрю.
Вы не против, если и я изложу свои дилетанские соображения по данной теме?
Прокомментируете где я прав, где нет?

[Руст]

Изложите конечно. Только я уже многое успел позабыть и потерять интерес к этой проблеме. Для интереса можно было бы посчитать максимальный период для n=71, который является делителем числа: $2^{35}-1=31*71*127*122921.$

[maxal]

Руст писал(а):

Для интереса можно было бы посчитать максимальный период для n=71, который является делителем числа: $2^{35}-1=31*71*127*122921.$

Период равен $2^{35}-1=34359738367$.

[Руст]

Вчера ночью проверил, что для всех простых n меньше 65536 максимальный период делится на n. Похоже это гипотеза верна. Только я не могу это доказать для простых n=7(mod 8), не являющихся степенями простых чисел Мерсена.

[Macavity]

Руст писал(а):

Изложите конечно.

Это скорее мой взгляд на проблему.

Я хочу переформулировать гипотезы о длине максимального цикла. Изначально гипотезы звучат примерно так:
Гипотеза Арнольда. Размер максимального цикла структуры кратен N.
Гипотеза Руста. Существует такое N(простое число), что размер максимального цикла структуры не кратен N.
Сама по себе структура представляет собой направленный граф, в котором вершины – это различные последовательности длины N, состоящие из 1 и 0, а дуги – определяются действием оператора 1+q (где q – циклический сдвиг влево, а ‘+’ – сложение по модулю 2). То есть исходная цепочка складывается по модулю 2 со сдвинутой циклически на одну позицию влево. Получается граф специфического вида – циклы и присоединенные к циклам одинаковые по глубине двоичные деревья.
Теперь рассмотрим действие оператора циклического сдвига (q) на граф. Это взаимнооднозначное отображение, отображающее вершины в вершины, а ребра в ребра. Например, вершина 10111011 из которой выходит ребро в вершину 11001100 (действие оператора 1+q), отобразится в вершину 01110111 из которой выходит ребро в вершину 10011001 (и это тоже действие оператора 1+q). Таким образом, циклический сдвиг действует как автоморфизм графа, созданного оператором 1+q. Последовательное применение такого автоморфизма образует группу автоморфизмов на данном графе. Действительно, чтобы получить исходный граф надо сделать N сдвигов. Если рассмотреть, такие цепочки как 00…001, 00…010, 00…100,…,01…000,10…000 и опять 00…001, то становится ясным, что порядок группы таких автоморфизмов равен N (и для простого N у группы нет подгрупп размерности отличной от 1). При этом q является образующим элементом группы. Действие автоморфизма на этом графе следующее, он отображает двоичные деревья в двоичные деревья, а циклы либо в сами себя, либо в циклы такой же длины. Это означает, что под действием группы автоморфизмов для простого N, цикл отображается либо постоянно сам в себя, изображая некоторое вращение, либо последовательно переходит по кругу в другие циклы такой же длины.
Это видно на примере, когда N=7, в этом случае количество циклов равно 9. При этом, два из них отображаются сами в себя, остальные 7 переходят в друг друга, проходя по очереди все оставшиеся 6 циклов и возвращаясь в себя.
Гипотезы можно переформулировать.
Гипотеза Арнольда. Для любого N всегда существует хотя бы один цикл максимальной длины, который описанный автоморфизм отображает сам в себя.
Гипотеза Руста. Существует такое N(простое число), что ни один из циклов не переходит сам в себя при автоморфизме (а отображается в другие циклы).

[Руст]

Это ничего не даёт. Из этого то, что можно использовать, я уже использовал. Например, если минимальный период с(n) (n - нечётное,с(n) - минимальное число, для которого $n|(2^{c(n)}-1)$) чётное число, то

$$(q+1)^{2^{c(n)/2}}=q^{-1}(1+q)$$

. Из этого я заключил, что степени 1+q содержит подгруппу сдвигов на q (естественно порядка n), а следовательно длина цикла делится на n. В частности, когда n простое число вида 3 или 5 по модулю 8, то 2 не является квадратичным вычетом, поэтому c(n) чётное и для них n делит максимальный период. Как уже написал, я проверил все случаи, когда это число нечётное n простое меньше 65536, и здесь период делится на n.

[Macavity]

Руст писал(а):

Это ничего не даёт. Из этого то, что можно использовать, я уже использовал. Например, если минимальный период с(n) (n - нечётное,с(n) - минимальное число, для которого $n|(2^{c(n)}-1)$) чётное число, то

$$(q+1)^{2^{c(n)/2}}=q^{-1}(1+q)$$

. Из этого я заключил, что степени 1+q содержит подгруппу сдвигов на q (естественно порядка n), а следовательно длина цикла делится на n. В частности, когда n простое число вида 3 или 5 по модулю 8, то 2 не является квадратичным вычетом, поэтому c(n) чётное и для них n делит максимальный период. Как уже написал, я проверил все случаи, когда это число нечётное n простое меньше 65536, и здесь период делится на n.

По крайней мере, у меня вроде нет ошибки в рассуждениях. Это уже хорошо. На самом деле я просто хочу, чтобы то, что обсуждается в этом форуме, было понятно таким же чечако как я.
Все-таки кажется, что продолжая мои рассуждения можно опровергнуть гипотезу Руста. Но что-то я пока не соображу. Надо подумать...

До понедельника.

[Руст]

Сейчас, после достаточного вычислительного эксперимента, я скорее верю гипотезе Арнольда. Если доказать это для всех простых, то получиться и доказательство для всех n (отчасти это изложено выше). Для случая, когда c(n) нечётно трудно явно получить выражение операции сдвига. Есть ещё подход, связанный с представлением простого числа n в двоичной записи

$$n=1+2^{k_1}+..+2^{k_s}$$

. Тогда

$$(q+1)^n=q^{2^{k_1}}[(q+1)^m-q^m)+q^{-2^{k_1}}((q+1)^m-1)],m=n-2^{k_1}$$

Все степени делятся на первый множитель, и если удастся получить выражение через степень 1+q для выражения в скобке, то оператор сдвига присутствует, а следовательно порядок делится на n. Вроде это удается расширением n до $n|n_1=2^{c(n)}-1$ и рассматривая последовательности из n элементов, как последовательности с большим числом элементов с периодом n. Так как на расширенное число можно доказать по аналогии с числами Мерсена.