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

[maxal]

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

я утверждаю, что в этом случае эта простая последовательность самая сложная

Можно увидеть доказательство? А заодно и аналитическую формулу для ее периода?

[Руст]

По поводу доказательства приведу несколько лемм, которые легко сможет доказать каждый.
1. Функция f(x) представляется в виде dg(x) тогда и только тогда, когда f(x) имеет чётное количество единиц (доказывается путём интегрирования).
2. Пусть n нечётное число. Любая функция с чётным числом единиц принадлежит циклу, с нечётным на одном шаге от цикла.
Доказывается интегрированием и тем, что при интегрировании 2 возможных способа выбора константы интегрирования дают две функции f и g взаимодополняющие, т.е f(x)+g(x)=1. Поэтому, одна из них имеет чётное количество единиц и дальше может быть проинтегрировано.
3. Весь процесс определяется разложением n на взаимно простые множители, являющиеся степенями простых чисел.
Представляем кольцо вычетов по модулю n в виде произведения колец вычетов по модулю степеней простых сомножителей, а функции f соответствующие функции по модулю сомножителей. Тогда все операции над функциями соответствуют операциям над соответствующими функциями в сомножителях.
Поэтому, количество шагов до периода равна максимуму количества шагов в сомножителях (для нечётной как уже указали он не больше 1 и последнее имеет место только в случае нечётного количества единиц, для чётной равно показателю двойки).
Поэтому, период определяется как НОК периодов по сомножителям, являющимся степенями нечётных простых чисел.
4. Для $n=p^k,p>2$ период T(n) равен $T(n)=T(p)p^m,2^{p-1}=1+p^ls,m=k-l $
5. Для нечётного простого числа р период для последовательности из нулей и 1 равен $T(p)=2^{c(p)}-1$, где с(р) минимальное число для которого выражение T(p) делится на р.
Доказывается тем, что вторая производная последовательности из нулей и 1 состоит из двух 1 идущих подряд.

[maxal]

Рустем, а как доказать, что этот период максимально возможный среди всех последовательностей длины n?

[maxal]

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

4. Для $n=p^k,p>2$ период T(n) равен $T(n)=T(p)p^m,2^{p-1}=1+p^ls,m=k-l $
5. Для нечётного простого числа р период для последовательности из нулей и 1 равен $T(p)=2^{c(p)}-1$, где с(р) минимальное число для которого выражение T(p) делится на р.

Что-то не сходится с численными результатами (A038553). Вот, например, для $n=9=3^2$ максимальный период равен 63, а по формуле выше получаем: $T(3)=2^2-1=3$, $l=1$, $m=1$ и, наконец, $T(3^2)=T(3) 3^1=9$.

Кроме того, из указанной выше формулы следует, что $T(n)$ всегда является нечетным, но это опять противоречит действительности, так как для четных n, за исключением степеней 2-ки, максимальный период является четным числом.

[Руст]

Да, в пунктах 4 и 5 высказал глупости. Для чётных $n=2^km$, m нечётное из за того, что нет числа d: $2^d=1(mod 2^k)$ не выполняется свойство
(1) $T(mn)=lcm(T(m),T(n)),(m,n)=1$.
В этом случае $T(2^km)=2^kT(m)$.
Для $n=p^k$ можно доказать (как указано выше) только то, что $T(n)|2^{c(n)}-1$ где с(n) минимальное число, когда это выражение делится на n.
А для взаимно простых нечётных формула (1) верна в силу 2.
Если честно меня это не интересует, по той причине, что это не сложность последовательности, а свойство числа n. Как я уже указал, для нечётных n последовательность из нулей и 1 самая "сложная по Арнольду".

[Руст]

То, что эта последовательность самая сложная по Арнольду следует из того, что она попадает в один цикл с $(T+1)T^lg_0(x)=T^lg(x)$. Так как любая функция f(x) с чётным количеством единиц представляется в виде $f(x)=\sum_i T^i g(x)$, то из $(T+1)^mg(x)=g(x)$ следует, что
$(T+1)^mf(x)=(T+1)^m\sum_i T^i g(x)=f(x)$,
т.е. период любой функции является периодом последовательности из 0 и 1 (для нечётного n).

[maxal]

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

Да, в пунктах 4 и 5 высказал глупости. Для чётных $n=2^km$, m нечётное из за того, что нет числа d: $2^d=1(mod 2^k)$ не выполняется свойство
(1) $T(mn)=lcm(T(m),T(n)),(m,n)=1$.
В этом случае $T(2^km)=2^kT(m)$.

Но сюда не вписывается случай $m=1$, когда $T(2^k)=1$. Где загвоздка?

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

Для $n=p^k$ можно доказать (как указано выше) только то, что $T(n)|2^{c(n)}-1$ где с(n) минимальное число, когда это выражение делится на n.

Да, это верно. Арнольд также утверждает, что $n\mid T(n)$ для $n\leq 21$, а для $n=23$ это не так, якобы потому что $T(23)$ является степенью 2-ки без единицы. Интересно, можно ли этому придать строгий вид типа такого:
Для нечетного $n$, $n|T(n)$, за исключением случая, когда $T(n)+1$ является степенью 2-ки ?

А вообще интересно было бы все-таки найти аналитическое выражение для $T(n)$.

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

А для взаимно простых нечётных формула (1) верна в силу 2.
Если честно меня это не интересует, по той причине, что это не сложность последовательности, а свойство числа n. Как я уже указал, для нечётных n последовательность из нулей и 1 самая "сложная по Арнольду".

Задача представляет самостоятельный интерес безотносительно Арнольда и его определения сложности.

[maxal]

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

То, что эта последовательность самая сложная по Арнольду следует из того, что она попадает в один цикл с $(T+1)T^lg_0(x)=T^lg(x)$.

Надо понимать, что $g_0(x)=\delta_{0x}$ (дельта Кронекера)?
А что есть $l$ и $g(x)$ ?

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

Так как любая функция f(x) с чётным количеством единиц представляется в виде $f(x)=\sum_i T^i g(x)$, то из $(T+1)^mg(x)=g(x)$ следует, что
$(T+1)^mf(x)=(T+1)^m\sum_i T^i g(x)=f(x)$,
т.е. период любой функции является периодом последовательности из 0 и 1 (для нечётного n).

Не понял этого заключения. Из последнего равенства всего лишь следует, что период $f(x)$ делит $m$.

[Руст]

Я не утверждал, что n|T(n) для нечётного n, а утверждал, что T(n) делитель числа $2^{c(n)}-1$, где с(n) минимальное число, когда это выражение делится на n. Это разные вещи и я вообще считал эту гипотезу Арнольда глупостью.
При выводе того, что указанная последовательность самая сложная я использовал обозначения: $g(x)=(T+1)g_0(x)$, где $g_0(x)$ дельта функция Кронекера.
В принципе точный период можно вычислить. Для этого надо вычислить разложение на множители числа $2^{c(n)}-1$. Пока до конца не додумал, кажется надо сокращать на те простые делители p, входящие в нечётной степени, для которых не существует d: $p|2^d+1$.
В принципе это вычисляемая функция от n.

[maxal]

Похожа, что замкнутая формула для $T(n)$ науке неизвестна.
Вот статья по теме: A Characterization for the Length of Cycles of the N-Number Ducci Game.

[Руст]

1. Это задача эквивалентно изучению кольца многочленов над Z2 факторизованное по идеалу, порождённому многочленом $x^n-1$. Когда n является степенью двойки $n=2^k$ то, для любого элемента кольца n ая степень равна нулю. Соответствено орбита у всех элементов (получающаяся умножениями на степени 1+T) кончается на нуле.
2. Если $n=2^km$ то кольцо содержит подкольцо изоморфное кольцу многочленов, факторизованное по идеалу, порождённому $x^m-1$ и для любого элемента его $2^k$ ая степень принадлежит этому подкольцу. Соответственно все периоды определяются периодами элементов подкольца возможно умноженные на степени двойки не превосходящие k (умножение не касается только для периода 1). Если $m=\prod_i p_i^{k_i}$ произведение степеней нечётных простых чисел, то подкольцо изоморфно произведению колец факторизованных по идеалам порождённым элементами $x^{m_i}-1,m_i=p_i^{k_i}$. Соответственно все периоды получаются в виде взятия НОК (обычно это приводит к произведениям) периодов сомножителей и степеней двойки. Всего имеется $-k+(1+k)\prod_i(1+k_i)$ периодов. Сами они определяются через максимальные периоды для случая $n=p^k$ с нечётным простым числом.
3.В дальнейшем рассмотрим только этот случай.
Пусть 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 нечётное не простое).

[juna]

sceptic писал(а):

Артамонов Ю.Н. писал(а):

Гипотеза существования односторонних функций более сильная, чем проблема $P\neq{NP}$. - можно поподробнее..

http://www.citforum.ru/security/cryptography/yaschenko/1.html
http://sci-lib.com/books/Ya/yashenko.djvu
http://www.computerra.ru/print/xterra/253871/

[sceptic]

хотелось бы выйти на работы, в которых этот вопрос рассматривался бы более глубоко (увы, научно-популярных и учебных материалов по нему мне недостаточно ).

[Руст]

Осталось определить точное значение максимального периода в случае $n=p^k$ для нечётного простого числа р. Обозначим разложение на неприводимые множители многочлена $(X+1)^n-1=X^{2^d}f_1(X)...f_r(X),n=1+2^dm,m=1(mod 2)$ над Z2. Тогда формула $lcm(2^{deg(f_i(X))}-1)$ дает точное значение максимального периода для этого случая. Остальные случаи нечётных n получается через НОК, а чётные (за исключением степени двойки) умножением на ту степень двойки на которую делится.

[maxal]

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

Осталось определить точное значение максимального периода в случае $n=p^k$ для нечётного простого числа р. Обозначим разложение на неприводимые множители многочлена $(X+1)^n-1=X^{2^d}f_1(X)...f_r(X),n=1+2^dm,m=1(mod 2)$ над Z2. Тогда формула $lcm(2^{deg(f_i(X))}-1)$ дает точное значение максимального периода для этого случая. Остальные случаи нечётных n получается через НОК, а чётные (за исключением степени двойки) умножением на ту степень двойки на которую делится.

Опять не срастается. Например, для n=11 имеем максимальный период 341, а по твоей формуле:
$(X+1)^{11} - 1 = X (X^{10} + X^9 + X^8 + X^7 + X^2 + X + 1)$
и $2^{\deg(f_1)}-1=2^{10}-1=1023.$
Настоящий период 341 является всего лишь делителем 1023.

И, кстати, непонятно, что делать в случае когда в разложении $(X+1)^n - 1$ присутствуют степени полиномов.