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

[Macavity]

Я рассмотрел некоторые симметрии, которые возникают в циклах и мне показалось это интересным. В конечном счете, я сформировал несколько гипотез, которые вероятно не очень обосновыны, но...

maxal писал(а):

Macavity писал(а):

Лучше ее переделать, а заодно переформулировать гипотезу:
Если для некоторого N (простое число) полный многочлен кольца раскладывается в L неразложимых многочленов, то область целостности кольца деформируется (уменьшается) и в ней появляется циклические автоморфизмы длины N (при автоморфизме цикл отображается не всебя, а другой цикл из цепочки N циклов той же длины) и имеет место формула
{(2^{N-1}-1)/K} – 2^L+2 = 0 mod N.

Здесь минимальным контрпримером является $N=3$. В этом случае $L=1$, $K=3$.

...для N=3 я проверил - выполняются

Для примера возьмем N равным, скажем, 3
Цикл состоит из цепочек (или многочленов кольца): 011, 101, 110.
Теперь для N=5: 00011, 00101, 01111, ..., 11110.
Заметим, что в первом случае количество коефициентов (или единичек в цепочке) одинаково для всех элементов цикла, а во втором - нет. Гипотезы.

Гипотеза 1. Если N простое числа Мерсена (простое число вида 2^k-1), то всегда существуют циклы с одинаковым числом единиц в цепочках цикла. При этом, количество единиц в каждой цепочке такого цикла равно (N+1)/2. Других циклов с одинаковым количеством единиц для таких N не существует.

проверено для N=3,7,31.
Можно попробовать наоборот.

Гипотеза 2. Если для некоторого N существуют циклы с одинаковым числом единиц и это число в точности равно (N+1)/2 (и только), то N - простое число Мерсена.

Замечено, что при росте N количество таких циклов увеличивается. Для 3, 7, 31 это соответственно 1, 2, 6 (всегда меньше или равно (N+1)/4).

Гипотеза 3. Если N это простое число, но не число Мерсена, то таких циклов не существкует.
N=5,11,13,17 и т.д.

Гипотеза 4. Если N не является простым числом и среди простых делителей N нет простых чисел Мерсена, то таких циклов не существует.

Гипотеза 4. Если N не является простым числом и среди простых делителей N есть простые числа Мерсена, то таких циклы существуют, среди них встречаются периодические, соответствующие делителям Мерсена.

Проверено для N меньших 32, вроде выполняются. Хотя, конечно это очень мало. Ближайший претендент на опровержение, вероятно, N=127.

[Руст]

Гипотеза 1 и 4 легко доказать. Вообще у чисел вида $N=2^k-1$ (не обязательно простых даже для к) длина максимального периода равна N. Соответственно с учётом этого можно получить контрпримеры для гипотез 2 и 3.

[Macavity]

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

Гипотеза 1 и 4 легко доказать. Вообще у чисел вида $N=2^k-1$ (не обязательно простых даже для к) длина максимального периода равна N. Соответственно с учётом этого можно получить контрпримеры для гипотез 2 и 3.

Что касается гипотезы 2, то мне сейчас кажется, что первый реальный претендент на опровержение это N=2^{11}-1=2047 (степень простая, но число не простое).
В опровержимости гипотезы 3 у меня есть сомнения.

На самом деле, я провел некоторые исследования этих многочленов, результаты изложу на следующей неделе, после того как проверю случай N=2047.

[Macavity]

Гипотеза 1. Если N простое числа Мерсена (простое число вида 2^k-1), то всегда существуют циклы с одинаковым числом единиц в цепочках цикла. При этом, количество единиц в каждой цепочке такого цикла равно (N+1)/2. Других циклов с одинаковым количеством единиц для таких N не существует.

Например - N=3 (или многочленов кольца): 011, 101, 110.
Или в виде многочленов - x+1, x^2+1, x^2+x

Это простой пример, но если n-простое число Мерсена и достаточно велико, то вид у этих многочленов значительно сложнее. Ниже я опишу вид и свойства таких многочленов.

Рассмотрим задачу циклических путей на дискретном k-мерном бинарном кубе. То есть каждая вершина куба имеет координату {(a_0,a_1,...,a_{k-1})}, где {a_i} может быть 0 или1. Движение от вершины к вешине осуществляется по закону {(a_0,a_1,...,a_{k-1})} \to {(x, a_0,a_1,...,a_{k-2})}, где x равно 0 или1.
Задача: начать с вершины (1,1,...,1) и двигаясь по указанному закону обойти все вершины, не заходя в начало координат (0,0,...0), вернуться в (1,1,...,1), пройдя каждую вершину по одному разу.

Необходимо определить количество таких путей для тех k, где N=2^k-1 простое число Мерсена, и собственно сами пути.

Примеры путей:
k=2,
(1,1)
(0,1)
(1,0)
(1,1)

Выделенные цифры можно записать так
101
или в виде многочлена 1*x^2+0*x^1+1*x^0

k=3,
(1,1,1)
(0,1,1)
(0,0,1)
(1,0,0)
(0,1,0)
(1,0,1)
(1,1,0)
(1,1,1)
запись в виде цепочки - 1101001 или в виде многочлена
1*x^6+1*x^5+0*x^4+1*x^3+0*x^2+0*x^1+1*x^0
Дальше, чтобы не запутаться, я буду называть такие пути BCP-путями, а такие многочлены BCP-многочленами (BCP - binary cube path).
На самом деле каждый путь это не один путь, а 2^k-1 BCP-путей, если движение начинать не с вершины с единичными координатами, а с других вершин, находящихся на пути. При этом получается 2^k-1 BCP-многочленов, отличающихся друг от друга вращением коефициентов.

Например - k=2
многочлены - x+1, x^2+1, x^2+x

Эти BCP-многочлены полностью соответствуют цепочкам-многочленам, рассмотренным в гипотезе. Так, для случая k=3, существует еще один BCP-путь, которому соответсвует еще один цикл многочленов в исходном кольце - x^6+x^5+x^2+1.
Далее рассмотрим свойства BCP-многочленов когда N-простое число Мерсена.

[Macavity]

Как было замечено выше один BCP-путь это на самом деле 2^k-1 путей, а один BCP-многочлен - это 2^k-1 многочленов. Я не буду это доказывать, но если эти 2^k-1 многочленам дополнить многочленом, у которого все коеффициенты нулевые, то мы получим группу многочленов по операции сложения исходного кольца многочленов, которая изоморфна группе из цепочек k-битов по сложению по модулю 2.
Пример для k=2
x^2+x \to 11
x^2+1 \to 10
x+1 \to 01
0 \to 0

скажем (x^2+x) + (x+1) = x^2+1 \to (11) \oplus (01) = (10)

В общем, этот факт связан с тем, что какие k подряд идущих коеффициентов в BCP-многочленах не взять, то для всех многочленов там будет различная комбинация нулей-единичек, а общееи количество многочленов 2^k-1 плюс нулевой.

Теперь можно доказать, что если N - простое число Мерсена, то BCP-многочлены одного BCP-пути составляют (1+x)-цикл в исходном кольце многочленов.
Если f(x) - BCP-многочлен, то и x*f(x) - тоже BCP-многочлен (умножение рассматривается как умножение в исходном кольце многочленов). И тогда в силу групповых свойств f(x)+xf(x) тоже BCP-многочлен.
То есть
f(x)+xf(x)=(1+x)f(x)
То есть если f(x) - BCP-многочлен и N-простое число, то и (1+x)f(x) тоже BCP-многочлен и BCP-многочлены составляют (1+x)-цикл в исходном кольце многочленов.

Пусть теперь f(x)=\sum\limits_{i=0}^{N-1}a_i*x^i и g(x)=\sum\limits_{i=0}^{N-1}b_i*x^i оба BCP-многочлены одного BCP-пути, тогда
f(x)*g(x)=(\sum\limits_{i=0}^{N-1}a_i*x^i )*(\sum\limits_{i=0}^{N-1}b_i*x^i)
f(x)*g(x)=\sum\limits_{i=0}^{N-1}a_i*x^i *(g(x))
И опять же из-за тех же групповых свойств данное произведение является BCP-многочленом и принадлежит (1+x) циклу.
Так же просто доказывается (если N-простое число), что среди (1+x) цикла есть единица по умножению и для каждого f(x) существует f^{-1}(x). То есть BCP-цикл это группа по умножению.
Чтобы не быть голословным -
N=3
единица - x^2+x,
то есть
(x^2+x)*(x+1)=x+1 и
(x^2+x)*(x^2+1)=x^2+1
для двух циклов при n=3, единицей являются многочлены
x^6+x^5+x^3+1и
x^4+x^2+x+1
Таким образом эти циклы дополненные нулевым многочленом представляют собой вложенные поля (с собственной единицей) по отношению к исходному кольцу многочленов.

[Macavity]

Теперь возьмем и умножим многочлен цикла на произвольный многочлен исходного кольца. В результате по тем же соображениям, что были указаны выше, получим многочлен цикла.
Это означает, что каждый такой цикл, дополненный нулевым многочленом является идеалом исходного кольца многочленов. Причем, любой многочлен цикла является базисом такого идеала (так как все остальные многочлены цикла могут быть получены умножением этого многочлена на x^i или (1+x)^i, где i пробегает значения от 1 до N-1.
Перемножим два многочлена, принадлежащие двум таким различным циклам. С одной стороны должны получить многочлен первого идеала, а с другой второго. Но циклы не пересекаются по многочленам, следовательно в результате перемножения получим многочлен, принадлежащий обоим идеалам, то есть 0 (нулевой многочлен). Итак, перемножая многочлены различных BCP-циклов, получаем 0.
Пример.
для N=7 (k=3)
(x^6+x^5+x^3+1)*(x^4+x^2+x+1)=0

К сожалению, искать такие многочлены с помощью поиска BCP-путей неблагодарное занятие. Если выбросить начало координат двоичного куба, куда BCP-путь не заходит, то получится задача нахождения Гамильтонова цикла, а она как известно NP-полная. Другое дело, что матрица инцидентности имеет довольно регулярный вид, но как по ней искать BCP-циклы, это надо еще понять.
И еще замечу, что если из BCP-пути выбрасывать не нулевую вершину, а единичную, то в результате будут получаться многочлены, лежащии на деревьях, указанных циклов.

[Руст]

Как я уже говорил гипотеза 1 верна не только для чисел Мерсена. Пусть $n=2^{2k+1}-1, \ p(x)=x^{2^{k+1}}+x^2+1$. Тогда $p(x)^{2^k}-p(x)=x^2(x^n+1)$ Следовательно для многочлена $q(x)=\frac{x^n+1}{p(x)}=\frac{p(x)^{2^k-1}-1}{x^2}$, имеющего (n+1)/2 единиц, указанное вами свойство выполняется.

[Macavity]

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

Как я уже говорил гипотеза 1 верна не только для чисел Мерсена. Пусть $n=2^{2k+1}-1, \ p(x)=x^{2^{k+1}}+x^2+1$. Тогда $p(x)^{2^k}-p(x)=x(x^n+1)$ Следовательно для многочлена $q(x)=\frac{x^n+1}{p(x)}=\frac{p(x)^{2^k-1}-1}{x}$, имеющего (n+1)/2 единиц, указанное вами свойство выполняется.

Наверное, я чего-то не понимаю в Ваших выкладках.
Возьмем k=1.
Тогда n=2^{2*1+1}-1=7 p(x)=x^4+x^2+1

p(x)^{2^k}-p(x)=x^8+x^4+1-x^4-x^2-1=x^8+x^2=x^2(x^6+1)

x(x^n+1) не получается.
Ну и q(x) тоже странный.
Может что-то не так умножаю?

[Руст]

Моя цель была указать конкретный вид такого ингочлена q(x). Это получается, если найдётся такое m, что $x^mq(x)=(x+1)^aq(x)(mod \ x^n+1)$. Тогда количество единиц при действии оператора "дифференцирования" х+1 не меняется у начального многочлена q(x). Когда $n=2^k-1$ и k чётное, это легко сделать с а=1, а для нечётного k, включающего числа Мерсена я не нашёл а=1 и взял а=2 (через два шага выполняется свойство (x^2+1)=(x+1)^2). Надеюсь идея понятна и сами сможете это проделать.
Я подозреваю, что это свойство верно и для некоторых делителей чисел вида $2^k-1$.

[Macavity]

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

Моя цель была указать конкретный вид такого ингочлена q(x). Это получается, если найдётся такое m, что $x^mq(x)=(x+1)^aq(x)(mod \ x^n+1)$. Тогда количество единиц при действии оператора "дифференцирования" х+1 не меняется у начального многочлена q(x). Когда $n=2^k-1$ и k чётное, это легко сделать с а=1, а для нечётного k, включающего числа Мерсена я не нашёл а=1 и взял а=2 (через два шага выполняется свойство (x^2+1)=(x+1)^2). Надеюсь идея понятна и сами сможете это проделать.

Ага... А я уже думал в каком это Вы кольце умножаете...

В принципе, я что-то такое считал для n=7 и на моих многочленах у меня получалось a=2 и a=4.

Думаю, что гипотезу 2 Вы опровергли. Если честно, то я проверял, только для циклов длины n. Однако, недавно я обнаружил, что для N=15, существуют такие многочлены на циклах длины 3. Что опровергает гипотезу 2.

А если ее поправить.

Гипотеза 2'. Если для некоторого N существуют циклы длины не менее N с одинаковым числом единиц и это число единиц в точности равно (N+1)/2(и только), то N - простое число Мерсена.

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

Я подозреваю, что это свойство верно и для некоторых делителей чисел вида $2^k-1$.

Я тоже подозреваю. Но для циклов длины N это только подозрение.

[Руст]

В принципе а=2 или 4 особой роли не играет, так как оно взаимно просто как с n, так и с периодом, в нашем случае совпадающем с n. Т.е. при выполнении этого условия начиная с последовательности q(x), весь цикл, количество единиц не изменится.

[Sonic86]

Здрасте!
Как хорошо, что это тема уже есть!
Из того, что тут не было, могу только сказать, что $T(n)$ делит порядок группы обратимых элементов по умножению в $\mathbb{Z}_2[x]/(x^n-1)$, который вычисляется по формуле включений исключений. $x^n-1$ сначала раскладывается в произведение круговых многочленов $\Phi_d(x)$ в $\mathbb{Z}[x]$, а круговые многочлены степени $d$ раскладываются на $\frac{\phi(d)}{P_d(2)}$ многочленов одинаковой степени, где $P_d(2)$ - порядок числа $2$ по модулю $d$.
$n=2^an_1$ $g(x)=\frac{x^n-1}{(x-1)^{2^a}} = p_1^{a_1}(x)...p_s^{a_s}(x)$ - разложение на простые, то мощность группы обратимых элементов равна $2^{n-2^a}\prod\limits_{1 \leq j \leq s}(1- \frac{1}{2^{deg(p_j(x))}})$. Ее и делит $T(n)$.

-- Пт дек 11, 2009 11:15:02 --

И еще вопрос, пока над ним не думал...
Мы получили, что для $1+x$ период равен $T$, причем $n|T$. Есть ли какие-либо другие такие многочлены $a(x)$, у который период $T_a$ также делится на $n$ для любого $n$.

[Sonic86]

Посмотрел еще статью про Ducci games. В принципе могу сказать, что вместо числа различных длин циклов брать число $e=2^s$, где $s$ - число различных простых делителей многочлена $g(x)=\frac{x^n-1}{(x-1)^{2^a}}$. То есть $e=2^s$ - это просто число классов элементов элементов в $\mathbb{Z}_2[x]/(x^n-1)$, делящихся строго на $d(x)$ (или число идеалов в этом кольце). Лишь иногда чисто случайно длины циклов в разных классах совпадают (например для $n=7$), по-моему их проще считать различными.

-- Пт дек 11, 2009 13:05:02 --

Sonic86 писал(а):

Есть ли какие-либо другие такие многочлены $a(x)$, у который период $T$ также делится на $n$ для любого $n$.

Например для $a(x)=1+x+x^2$ и $n$ не кратного $3$ видимо тоже $n|T_{a(x)}$

[Xaositect]

Руст в сообщении #30401 писал(а):

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

Выскажу свою точку зрения на эту тему.
"Сложность по Арнольду" характеризует не конечные последовательности, а периодические.
Для четного $n$ последователность $(01\dots 01)^\omega = (01)^\omega$ простая, для нечетных же $(01\dots 010)^\omega$ вполне может считаться достаточно сложной для порождения.

[Утундрий]

Единственно, что мне в этом не нравится - это то, что вот например число я могу предтавить в двоичной и троичной форме, но относительные сложности по Арнольду одной и той же пары чисел будут зависеть от выбранного основания. Конечно, можно говорить, что в таком представлении это разные последовательности... но все равно - неприятно. Как "цифровка". Помните такую штуковину, возникающую из "вопроса" счастливый ли данный трамвайный билет?