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

[zigzag]

Судя по ответам в теме мой вопрос покажется *детсадовским* Тем не менее прошу помощи в понимании следующего:



Как в этой таблице находятся тождества из последнего столбца как все это соотносится с оператором циклического сдвига. Как определять степени этих операторов? Например почему для n=7 A^8=A^2 и т.д. Прошу объяснить и чем проще тем лучше. Заранее спасибо.

[Sonic86]

zigzag в сообщении #623330 писал(а):

Как в этой таблице находятся тождества из последнего столбца как все это соотносится с оператором циклического сдвига.

По определению так: берут двоичный вектор $x$, вычисляют $A(x), A^2(x),...$. Как только обнаружатся в вычисляемых векторах обнаружатся дубли (пусть их номера $k_a, n_a$), так сразу пишут $A^{n_a}(x)=A^{k_a}(x)$. Среди пар $(k_a,n_a)$ находят максимальную $(k,n)$. Пишут $A^n=A^k$.
На самом деле, эти $n,k$ вычисляются проще, конечно. Частично Арнольд их сам посчитал. Можно и самому посчитать целиком...

[zigzag]

Спасибо за ответ, посоветуйте может что изучить для лучшего понимания? Просто у Арнольда (для меня) слишком размашистый стиль повествования(видимо подразумевается начальная подготовка слушателя). Предположим вы занялись бы изучением всего этого с нуля, с чего бы начали? (уж извините за примитивизм).

Если не сложно проведите хотя бы 1 пример для любого соотношения, что бы я мог понять остальное. А вообще мне нужно разобраться в следующем: http://elementy.ru/lib/430178/430282 включая сложность логарифмов.

[Sonic86]

(длинное ИМХО)

zigzag в сообщении #623376 писал(а):

Предположим вы занялись бы изучением всего этого с нуля, с чего бы начали? (уж извините за примитивизм).

Ну я с нуля и начал (3 курса универа уже были) Я сначала тупо эмпирически считал всякие параметры и эти деревья. Потом взял какую-то книжку (как бы не Лидл Нидеррайтер Конечные поля) и она мне частично помогла - часть вещей я сосчитал сам (с помощью какой-то простой теории чисел (Бухштаба Теория чисел вполне хватило) и формулы включений-исключений), часть опровергается. А последнее Руст дописал. Сейчас вот ничего не помню кроме двух выводов: 1) конструкция не особо интересна (это не область Арнольда, он, видимо, в 1-й раз туда полез). 2) "Сложность" Арнольда к интуитивному понимаю сложности отношения не имеет (интуитивное - это колмогоровское). Т.е. это не сложность, а неведомо что.

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

(ИМХО2)

Зря они, наверное, этот доклад на элементах выложили. Хотя может я чего-то не понимаю. Интересно, конечно...

[zigzag]

Опять скопилось куча примитивных вопросов, если кому не сложно объясните *на пальцах*
ТЕОРЕМА 2. Граф «многочленов» периода n = 2k(2a + 1) является корневым бинарным деревом с 2k этажами, так что содержащая x = 0 компонента графа оператора взятия разностей есть . ЗАМЕЧАНИЕ. Теорему 2 можно сформулировать как описание ядер итераций оператора A,

Эта растущая последовательность векторных подпространств стабилизируется в виде подпространства Ker(AN) = Ker(AN+1) = ... с достаточно большим N. Это «стабильное ядро» мы будем обозначать Ker(A∞).

Мы докажем сейчас, что это векторное пространство над полем имеет размерность 2k:

так что число точек стабильного ядра есть

Эти точки, как мы сейчас докажем, образуют вершины бинарного корневого дерева , о котором идет речь

Вопрос Что такое этот ker и с чем его едят. Правльноли я понимаю ker - *маленькое бинарное дерево* из нуля, для не сложной последовательности, это ядро обрастает новыми ветками при более высокой сложности последовательности (при А в большей степени)

СЛУЧАЙ p = 5, n = 4. Имеем по модулю 5

2^1 ≡ 2, 2^2 ≡ 4, 2^3 ≡ 3, 2^4 ≡ 1.

Поэтому log21 = 4, log22 = 1, log23 = 3, log24 = 2. Итак, арифметический логарифм есть последовательность l = (0, 1, 1, 0), L = 6.

Единственная компонента (O1 T16) графа оператора A для n = 4 есть бинарное корневое дерево (многочленов степени меньше 4), которое в X-обозначениях имеет вид

Вопрос как получаются логарифмы из 3 стоки, и почему они такие *не правильные*, и вообще буду признателен если кто-то доходчиво объяснит, что за хитрый *арифметический* логарифм использует арнольд .

ПРИМЕР. Числа сочетаний , t ≥ 2 образуют, после приведения по модулю 2, последовательность (1, 1, 0, 0, 1, 1, 0, 0, ...) периода 4. Коэффициенты этого «многочлена»

— не целые, а рациональные числа, но все значения в целых точках целые.

Из теории Ньютона следует, что кольцо всех таких «многочленов» представляет собой компоненту связности (корневое дерево) цикла x = 0 периода 1 в .

Эти деревья «многочленов» периода n приведены для n ≤ 12 в виде последнего слагаемого суммы компонент: (O1 T4) при n = 2, (O1 T2) при n = 3, ..., (O1 T16) при n = 12.

вопрос как получаются эти сочетания?

[Sonic86]

Давайте так: Вы, согласно правилам форума, оформляете формулы ТеХом (пока есть возможность), а я Вам отвечаю

[zigzag]

вот как-то так?
Опять скопилось куча примитивных вопросов, если кому не сложно объясните *на пальцах*
ТЕОРЕМА 2. Граф «многочленов» периода n = 2k(2a + 1) является корневым бинарным деревом с 2k этажами, так что содержащая x = 0 компонента графа оператора взятия разностей есть . ЗАМЕЧАНИЕ. Теорему 2 можно сформулировать как описание ядер итераций оператора A,

Эта растущая последовательность векторных подпространств стабилизируется в виде подпространства Ker($A^n$) = Ker($A^{n+1}$) = ... с достаточно большим N. Это «стабильное ядро» мы будем обозначать Ker($A^\infty$).

Мы докажем сейчас, что это векторное пространство над полем имеет размерность 2k:

так что число точек стабильного ядра есть

Эти точки, как мы сейчас докажем, образуют вершины бинарного корневого дерева , о котором идет речь

Вопрос Что такое этот ker и с чем его едят. Правльноли я понимаю ker - *маленькое бинарное дерево* из нуля, для не сложной последовательности, это ядро обрастает новыми ветками при более высокой сложности последовательности (при А в большей степени)

СЛУЧАЙ p = 5, n = 4. Имеем по модулю 5
$2^1$ ≡2
$2^2$ ≡4
$2^3$ ≡3
$2^4$ ≡1
Поэтому
$log_2 1 = 4$
$log_2 2 = 1$
$log_2 3 = 3$
$log_2 4 = 2$.
Итак, арифметический логарифм есть последовательность l = (0, 1, 1, 0), L = 6.

Единственная компонента (O1 T16) графа оператора A для n = 4 есть бинарное корневое дерево (многочленов степени меньше 4), которое в X-обозначениях имеет вид

Вопрос как получаются логарифмы из 3 стоки, и почему они такие *не правильные*, и вообще буду признателен если кто-то доходчиво объяснит, что за хитрый *арифметический* логарифм использует арнольд .

ПРИМЕР. Числа сочетаний , t ≥ 2 образуют, после приведения по модулю 2, последовательность (1, 1, 0, 0, 1, 1, 0, 0, ...) периода 4. Коэффициенты этого «многочлена»

— не целые, а рациональные числа, но все значения в целых точках целые.

Из теории Ньютона следует, что кольцо всех таких «многочленов» представляет собой компоненту связности (корневое дерево) цикла x = 0 периода 1 в .

Эти деревья «многочленов» периода n приведены для n ≤ 12 в виде последнего слагаемого суммы компонент: (O1 T4) при n = 2, (O1 T2) при n = 3, ..., (O1 T16) при n = 12.

вопрос как получаются эти сочетания?

[Sonic86]

Ну ладно. Но вообще формулы следует набирать ТеХом.

(формулы)

формулу обрамляют знаками доллара целиком - так красивее. Наводите мышкой на формулы - появится хинт с их кодом.
Степени и индексы пишутся так: $A_{123}^{456}$
Перед логарифмом ставим слэш:

\log

$\log$

zigzag в сообщении #631314 писал(а):

Что такое этот ker и с чем его едят.

Вообще если $A$ - линейный оператор в пространстве $L$, то его ядро $\ker A$ по определению $=\{x\in L: A(x)=0\}$ - множество векторов, образ которых - нулевой вектор. Ядро является подпространством $L$. В данном случае конечно

zigzag в сообщении #631314 писал(а):

ker - *маленькое бинарное дерево* из нуля

zigzag в сообщении #631314 писал(а):

как получаются логарифмы из 3 стоки

Ну просто по определению. Абстрактно, если $a^x=b$, то пишут $x=\log_a b$ (это если игнорировать множество, из которого берутся элементы и существование логарифма. Но в данном случае с этим дела обстоят хорошо). Соответственно, если $2^1,2^2,2^3,2^4\equiv 2,4,3,1 \pmod 5$, то пишут (подразумевая логарифм в $\mathbb{Z}_5$), что $\log _2 2=1, \log _2 4 = 2, \log _2 3=3$ и т.п.

zigzag в сообщении #631314 писал(а):

вообще буду признателен если кто-то доходчиво объяснит, что за хитрый *арифметический* логарифм использует арнольд

Они в книжке Бухштаба называются индексами. Вообще есть такое кольцо классов вычетов $\langle\mathbb{Z}_p,+,\cdot\rangle$. Грубо говоря, это множество чисел от $0$ до $p-1$ с обычным сложением и умножение, но с тем условием, что после каждого сложения умножения результат заменяется его остатком от деления на $p$. Почитать про это - теорию сравнений + что-то про конечные абелевы группы.

zigzag в сообщении #631314 писал(а):

вопрос как получаются эти сочетания?

Имеются ввиду биномиальные коэффициенты $C_n^t, t=0,1,2$ по модулю. (если не вру)

[Den is]

$n=47$ - это число Софи Жермен для $n=23$. А периоды для $n=47$ и $n=49$ чему равны, никто не вычислял? Интересно было бы узнать отклонения от гипотезы Арнольда еще дальше $n<100$?

Deggial: формулы и термы оформляйте $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Пока я формулы поправил сам.

[maxal]

Если кому-то интересно, то я обновил и дополнил многими членами последовательности, связанные с "сложностью Арнольда" и "отображением Дуччи":
A038553 (длина максимального цикла)
A111944 (количество различных длин циклов)
A135547 (количество циклов)

-- Sat Oct 12, 2013 16:21:55 --

maxal в сообщении #24232 писал(а):

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

Имелась в виду, конечно, гипотеза:
Для нечетного $n$, $T(n)$=A038553(n) или $\frac{T(n)}{n}$ является степенью 2-ки без единицы?

Но эта гипотеза неверна - контрпримерами являются $n$ равные:
37, 95, 101, 111, 197, 199, 203, ...
Для $n=37$, имеем $T(n)=3233097$ и соответственно $\frac{T(n)}{n} = 87381$ -- и ни одно из этих чисел не является степенью 2-ки без единицы.

-- Sat Oct 12, 2013 16:23:03 --

Den is в сообщении #772925 писал(а):

$n=47$ - это число Софи Жермен для $n=23$. А периоды для $n=47$ и $n=49$ чему равны, никто не вычислял? Интересно было бы узнать отклонения от гипотезы Арнольда еще дальше $n<100$?

См. A038553