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

[Руст]

Решил подитожить тему и привести доказательство гипотезы Арнольда. Изложение несколько обобщу.
Пусть K(n,m) кольцо функций на множестве из n элементов со значениями в кольце из m элементов. Пусть q сдвиг влево $q(f(x))=f(x+1)$ (сложение аргумента по модулю n, в то время как сложение функций по модулю m). Рассмотрим действие и орбиты оператора "дифференцирования" d=q-1 на пространстве этих функций. Все пространство функций можно отождествить с пространством полиномов $Z_m[x]/(x^n-1)$. Задавался вопрос обобщения этого оператора. Можно рассматривать любой линейный оператор, однако для конечного множества n представляют интерес только операторы коммутирующие со сдвигом. Все такие операторы являются многочленами от q, степени меньше n. Поэтому, любой полином степени меньше n можно представить в виде полинома от этого оператора, степени меньше (так как полином, по которому факторизуется (q^n-1), так же запишется в виде полинома степени не выше n). Соответственно, это не дает особого обобщения.
Учитывая, что эти кольца являются прямыми произведениями колец по взаимно простым делителям, когда (n,m)=1, т.е.

$$K(n)=\prod_{d_i|n, (d_i,d_j)=1} \prod_{m_l|m,(m_i,m_j)}K(d_i,m_l),$$

достаточно ограничиваться случаями, когда n и m степени простых чисел и отдельно, когда n делится на простой делитель m. В дальнейшем будем рассматривать только m=p простое и интересоваться длинами орбит оператора d=q-1, которых назвали периодами. Со сложностью функции длина орбиты не имеет ничего общего, и в этом случае, когда n не делится на p, то "самой сложной по Арнольду" будет чередование нулей и единиц. Однако, это имеет некоторый математический интерес. Как изложено выше, максимальный период для $n=p^kn_1, \ p\not|n_1$ равен $p^kT(n_1), \ \frac{q^{n_1}-1}{q-1}|\frac{q^{T(n_1}-1}{q-1}, T(n_1) - min.$
Поэтому, достаточно рассмотреть случай, когда n не делится на р, и даже являющейся степенем простого числа, так как иначе находится как наименьшее общее кратное периодов взаимно простых делителей. Пусть с(n) (n не делится на р) определяется, как порядок числа р, т.е минимальное число, для которого $n|(p^{c(n)}-1)$. Из того, что

$$(q-1)^{p^{c(n)}}=q-1$$

получается, что $T(n)|p^{c(n)}-1$. Когда с(n) чётное и n степень простого числа получаем, что

$$(q-1)^{p^{c(n)/2}}=q^{-n+1}-1=\frac{q-1}{q}\Longrightarrow T(n)|n(p^{c(n)/2}-1).$$

Из того, что оператор сдвига направо выражается через q-1 и инвариантны относительно него только константы, а относительно его степени периодические с таким периодом, получаем, что n|T(n).
Когда с(n) нечётное число, явно выразить оператор сдвига сложно. Докажем эту делимость (гипотеза Арнольда) и для этого случая. Пусть n степень простого числа r и

$$n_1=p^{c(n)}-1,n_2=\frac{n_1}{r^k}, n\not |n_2, g(q)= (q-1)^{n_2}$$

Из того, что $(q^{n_1}-1)|(g(q)^{r^k}-1)$ получаем, что все корни (в соответствующем расширении) являются корнями левой части следует, что g(c) корень из единицы, когда с корень из единицы. Из инвариантности относительно группы Галуа g(F(c))=F(g(c)) получаем, что $g(q)=q^l(f(q^{r^k})$. Из того, что коэффициенты при 1 и $q^{n_2}$ могут отличаться только знаком, получаем что $r^k|n_2$ вопреки выбору n2. Это доказывает гипотезу Арнольда, на самом деле из этого рассуждения получается, что $(q-1)(q-1)^{T(n)/n}=q^l(q-1),(l,n)=1$, т.е. сдвиги функций всегда принадлежат её орбите.
Арнольд ещё высказал гипотезу, что или $T(n)=p^k-1, \ (k=c(n) - odd)$ или
$\frac{T(n)}{n}=p^k-1, (k=c(n)/2, \ c(n) - even)$. Это гипотеза действительно глупая. При малых n, периоды получались равными максимально возможными. Однако,уже для n=37 это не так.

[Macavity]

Я Вас поздравляю. А я так и не додумался, буду смотреть Ваше доказательство.

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

Арнольд ещё высказал гипотезу, что или $T(n)=p^k-1, \ (k=c(n) - odd)$ или
$\frac{T(n)}{n}=p^k-1, (k=c(n)/2, \ c(n) - even)$. Это гипотеза действительно глупая. При малых n, периоды получались равными максимально возможными. Однако,уже для n=37 это не так.

Мне кажется на elementary.ru гипотеза выглядит по другому. Здесь же какое то обобщение. На самом деле инересно, почему в одних случаях верно, а в других нет...

[Руст]

На самом деле максимальный период полностью вычисляется через числа c(n), $t(n)=n(p^{c(n)/2}-1),c(n) - even, t(n)=p^{c(n)}-1.$
По крайней мере для случая, когда c(n) чётное и n степень простого числа (достаточно уметь находить период только для этих случаев), я могу доказать, что период T(n) можеть отличаться только на простые делители t(n), являющиеся делителем n-1.

[Macavity]

Я завершил рассмотрением автоморфизма и хочу продолжить.
Рассмотрим граф, который формируется оператором 1+q.
Для примера возьмем N=7 и рассмотрим следующие строки:
0000011,
0000101,
0001111,
0010001,
0110011
1010101,
1111110,
0000011…
Вообще говоря, это цикл длины 7. Теперь, если рассмотреть граф в целом, то в него войдут вершины со всеми вариантами строк (всего 2^N строк). Заметим, что операция применения оператора 1+q по отношению к любой последовательности единиц ничем не отличается от операции умножения полиномов на кольце полиномов, если рассматривать указанные строки нулей и единиц как коэффициенты при одночленах. Например, последовательность 0110011, может рассматриваться как полином 0*q^6+1*q^5+1*q^4+0*q^3+0*q^2+1*q^1+1*q^0. И произведя умножение этого полинома на 1+q, в результате получится полином с коэффициентами как у следующей цепочки цикла – 1010101 или, что как многочлен выглядит так - q^6+q^4+q^2+1. То есть указанный граф демонстрирует поведение элементов кольца многочленов при умножении их на 1+q (что представляет собой ребро с началом в исходном многочлене и концом в результате умножения). Вероятно, анализируя этот граф можно сделать некоторые заключения о свойствах и поведении элементов данного кольца. Что я и попробую сделать. Рассмотрим делители нуля и область целостности кольца. То есть в силу коммутативности кольца по умножению нас интересуют такие x, которые, будучи умноженные на ненулевой элемент дадут в результате 0. Эти x и будут представлять собой множество делителей нуля (включая сам 0), а остальные элементы (включая 1) входят в область целостности кольца (и представляют собой группу по умножению). Нас интересует как группируются эти два множества на графе. . Во-первых, поскольку (1+q)*(1+q+…+q^{N-2}+q^{N-1})=0 , что очень легко проверяется, то оба эти сомножители являются делителями нуля. Это можно увидеть на графе – второй сомножитель это последовательность из единиц (111….1111) и стрелка от нее уходит в 000….0000, что и означает результат умножения на 1+q. Итак, два элемента найдены. Рассмотрим теперь элементы, принадлежащие циклам. Каждый полином f(q) находящийся на цикле можно представить как другой полином g(q) умноженный на (1+q)^s .
f(q)=g(q)*(1+q)^s.
Рассмотрим умножение f(q) на полный полином (полином со всеми единичными коэффициентами).
f(q) *(1+q+…+q^{N-2}+q^{N-1}) = g(q)*(1+q)^s*(1+q+…+q^{N-2}+q^{N-1})= g(q)*(1+q)^{s-1}*((1+q)*(1+q+…+q^{N-2}+q^{N-1})= g(q)*(1+q)^{s-1}*0=0
Таким образом, каждый элемент цикла является делителем нуля. Осталось рассмотреть элементы, находящиеся на деревьях (их 2^{N-1}-1) и о них пока можно сказать мало. Но каждый из них это претендент на вхождение в область целостности. Ниже, небольшая табличка для простых N:

2 , 2 , 2
3 , 3 , 3
5 , 5 , 5
7 , 49 , 63
11 , 1023 , 1023
13 , 4095 , 4095
17 , 65025 , 65535

Первая строка – N, вторая мощность области целостности кольца многочленов третья это 2^{N-1}-1 (максимальное количество элементов, которые могут быть в области целостности кольца многочленов). В ряде случаев (если продолжить таблицу то это подтвердится) полная идиллия – второй и третий элемент абсолютно совпадают. А вот для N=7 и N=17 второй и третий элемент таблицы различны. Давайте разберемся откуда появляется дефектность области целостности кольца.

Я продолжу ниже в следующем сообщении.

[Руст]

Если умножить полином f(q) с нечётным числом членов, на другой полином с нечётным числом элементов получится полином с нечётным числом элементов, т.е. 0. Поэтому, одним из множителей является всегда полином из цикла, при этом не важно какой брать член из цикла. По сути делители нуля определяются разложением на множителей многочлена $0=q^n+1=(q^k+1)(q^{(l-1)k}+q^{(l-2)k}+..+1$. Так как все многочлены с чётным числом элементов (входящие в цикл) делители нуля, необходимо вычислить только с нечётным числом членов. Они входят в указанного типа разложение и могут быть просчитаны.

[Macavity]

Начнем с N=7 (тем более что это - число Мерсена, хотя это ничего нам не дает). Для начала, обратим внимание, что 63 – 49=14= 2 * 7 (кратно величине цикла). Ладно я не буду тянуть кота за хвост (ведь мой ник Macavity) и объясню. Все дело в полном многочлене –q^6+q^5+q^4+q^3+q^2+q+0, оказывается он раскладывается на два сомножителя – неразложимых многочлена:
q^6+q^5+q^4+q^3+q^2+q+0=(q^3+q^2+1)*(q^3+q+1)
Каждый из многочленов соответствует вершине на графе (не в цикле, а на дереве, так как количество единиц в строках нечетное): первый – 0001101, а второй – 0001011. Поскольку их произведение равно полному многочлену, то каждый из многочленов делит нуль. Соответственно нуль делит соседи деревья, исходящие из того же цикла, из которого растут эти многочлены-строки (на самом деле это связано с циклическим автоморфизмом, о котором я писал в одном из предыдущих сообщениях). Деревья от двух циклов – 2*7 это и есть тот дефект области целостности, о котором писалось выше.

Дальше (для N=17)
65535 - 65025 = 510 = 2*255

Действительно, длина цикла при N=17 равна 255. Действительно, полный многочлен раскладывается на два сомножителя. Если не ошибаюсь, они равны –
q^8+q^5+q^4+q^3+1 и q^8+q^7+q^6+q^4+q^2+q+1.
Дальше практически такие же рассуждения, только для N=7, получаем 9 циклов (7+1+1 с точки зрения автоморфизма), а для N=17 посложнее - 257 циклов (15 циклов автоморфизма по 17 циклов в каждом автоморфизме + 1 +1).
Еще один интересный факт:
НОД(49,63)=7 (длина наибольшего цикла)
НОД(65535, 65025)=255(длина наибольшего цикла)
Это как раз то, на что я надеялся (2^{N-1}-1 должно делится на N и можно доказать, что порядок группы области целостности должен делится на N), рисуя эту таблицу, но оказалось, что работает это редко.
Можно сформулировать гипотезу.
Если для некоторого N (простое число) полный многочлен кольца раскладывается в два неразложимых многочлена, область целостности кольца уменьшается до 2^{N-1}-1-2*K элементов(K – длина наибольшего цикла) и имеет место формула
{(2^{N-1}-1)/K} + 2 = K.
Последняя формула верна и для N=7 и для N=17, но, вероятно, это слишком сильное условие и оно скорее всего в большинстве случаев не выполняется.
Лучше ее переделать, а заодно переформулировать гипотезу:
Если для некоторого N (простое число) полный многочлен кольца раскладывается в L неразложимых многочленов, то область целостности кольца деформируется (уменьшается) и в ней появляется циклические автоморфизмы длины N (при автоморфизме цикл отображается не всебя, а другой цикл из цепочки N циклов той же длины) и имеет место формула
{(2^{N-1}-1)/K} – 2^L+2 = 0 mod N.
Степень двойки появляется так как многочлены-делители могут образовывать циклы, встречаясь в разных мультипликативных комбинациях друг с другом (-2 соответствует полному многочлену и делителю равному 1).
К сожалению (или к счастью), я не смог найти чисел, опровергающих гипотезу. Для простого полного многочлена (L=1) - она очевидна. А для L=2 из подтверждающих – это только 7 и 17 (больше не нашел). Мне бы очень хотелось бы написать, что я нашел замечательное доказательство этой гипотезы, но, здесь, на форуме слишком мало места, чтобы я его привел. Но это тоже будет неправда. То, что я написал в объяснении, вероятно, не может служить доказательством или, по крайней мере, не полное доказательство.

И тут наступило утро и Шахеризада закончила дозволенные речи…

[Руст]

Macavity писал(а):

Начнем с N=7 (тем более что это - число Мерсена, хотя это ничего нам не дает). Для начала, обратим внимание, что 63 – 49=14= 2 * 7 (кратно величине цикла). Ладно я не буду тянуть кота за хвост (ведь мой ник Macavity) и объясню.

Что означает Macavity?

Цитата:

Все дело в полном многочлене –q^6+q^5+q^4+q^3+q^2+q+0, оказывается он раскладывается на два сомножителя – неразложимых многочлена:
q^6+q^5+q^4+q^3+q^2+q+0=(q^3+q^2+1)*(q^3+q+1)

Это тоже самое, о чём я говорил.
$Можно сформулировать гипотезу. <div class= + 2 = K.
Последняя формула верна и для N=7 и для N=17, но, вероятно, это слишком сильное условие и оно скорее всего в большинстве случаев не выполняется.

[Macavity]

Macavity - это кот-бандит из цикла стихотворений одного знаменитого англоязычного поэта (подзабыл его имя) и по этому циклу был сделан знаменитый мюзикл "Кошки".

Приведенный Вами вариант это не окончательная, а усиленная гипотеза, которая скорее всего неверна. Надо смотреть другой вариант (он там ниже по тексту) и знать как раскладывается на множители полный многочлен для N=31.

[Руст]

Я этот пример привёл как кандидат потому, что $0=q^{31}+1=(q+1){q^{30}+...+1}$ имеет два делителя с нечётной степенью: $q^3+1,q^5+1$

[Macavity]

Усиленная гипотеза подразумевает, что
K={2^{{(N-1)}/2}} - 1
А это бывает, вероятно, очень редко...
Хотя бы потому, что должно делиться на N.
Пример посмотрю.

[maxal]

Macavity писал(а):

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

Контрпример дает $N=41$. В этом случае полный многочлен есть произведение двух неприводимых многочленов степени 20, но $K=41943$ и $(2^{40}-1)/K=26214425$.

Macavity писал(а):

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

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

[незваный гость]

Macavity писал(а):

Macavity - это кот-бандит из цикла стихотворений одного знаменитого англоязычного поэта (подзабыл его имя) и по этому циклу был сделан знаменитый мюзикл "Кошки".

T. S. Elliot: Old Possum's Book of Practical Cats

[Macavity]

незваный гость писал(а):

:
T. S. Elliot: Old Possum's Book of Practical Cats

Именно.

[Macavity]

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

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

Этих фактов достаточно, чтобы понять, что указанная последовательность, чередующихся 1 и нулей является самой сложной при нечётных n.

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

Руст.
Я согласен, что для нечетных N, последовательность из нулей и единиц одна из самых сложных. Мне только непонятно, почему Вы называете ее простой.

С точки зрения физики "хорошими и простыми" считаются законы, в которых учтены симметрии окружающего мира и которые, записываются одинаково в различных, например инерционных системах. Симметрии в широком смысле, часто разыскивают и математики, а программисты опираясь на симметрии пишут программы.
Двоичная логарифмическая функция не является конкретной функцией, в том смысле, что при увеличении области определения меняются значения функции, которые были определены на более узкой области определения. Но, в конце концов, вопрос о сложности функции сложен сам по себе и рассматриваемые структуры являются чем-то вроде модели, для исследования сложности.
Эти структуры можно представить как некий "мир" (я говорил, что мне они напоминают урезанный вариант игры Жизнь), в котором действует "фундаментальный закон" - (1+q)*, который и определяет структуру. Но в этом мире есть и симметрии - это N-автоморфизм, о котором я писал, то есть симметрия на циклические сдвиги. Любая цепочка после сдвига попадает на тот же цикл (с тем же расстоянием от цикла, если она не принадлежит циклу) или на соседний цикл (на такое же расстояние). В этом смысле можно говорить о цепочках-функциях изоморфных (свернутых в цикл, где n-я позиция соединена с первой) относительно автоморфизма. "Хорошие и простые" цепочки должны оставаться такими же "хорошими и простыми", чтобы обеспечить симметричность. Цепочка из единиц и нулей теряет всю свою красоту при таких циклических поворотах. В этом смысле она совсем не такая уж и простая.
Физик бы сказал, что она красива только относительно системы связанной с неподвижным эфиром .
Относительно логарифмической функции. В силу ее непериодичности она в большинстве случаев расположена на максимальном цикле (циклы кратные максимальному и "экспортируемые" из циклов, создаваемых делителями максимального содержат периодические цепочки). Есть, конечно и сомнения, например досадный случай для N=17, максимальный цикл имеет длину 255, но есть и три цикла с длиной 85.
Поэтому, это не очевидный факт, что логарифмическая функция-цепочка связана с максимальным циклом.
С другой стороны, если N=4*k+2, то в силу того, что количество квадратичных вычетов, равно количеству квадратичных невычетов следует, что количество единиц нечетное (2*k+1) и следовательно такая цепочка всегда лежит на самой высокой позиции в дереве. Для случая N=4*k можно только с увернностью сказать, что она не лежит на самой высокой позиции дерева (количество единиц четное). А то что она лежит на предпоследней позиции, это еще следует доказывать.

[Руст]

Macavity писал(а):

С другой стороны, если N=4*k+2, то в силу того, что количество квадратичных вычетов, равно количеству квадратичных невычетов следует, что количество единиц нечетное (2*k+1) и следовательно такая цепочка всегда лежит на самой высокой позиции в дереве. Для случая N=4*k можно только с увернностью сказать, что она не лежит на самой высокой позиции дерева (количество единиц четное). А то что она лежит на предпоследней позиции, это еще следует доказывать.

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