Владимир Игоревич Арнольд,
Математический институт им. В. А. Стеклова, Москва

Доклад в Московском математическом обществе

Последовательность 001 001 001 001 проще, чем последовательность 01 001 0111 001. Ниже описана формальная математическая теория, придающая этому интуитивно понятному утверждению точный смысл.

Пусть x — последовательность из n нулей и единиц, x = (x1, ..., xn), xj  . Множество M всех 2n таких последовательностей есть множество вершин n-мерного куба. Оно является также n-мерным векторным пространством над полем  из двух элементов: M = .

Для анализа сложности функции x  M мы последуем идее Ньютона и рассмотрим ее первые разности, определив линейный оператор

A : M → M, y = Ax

формулой yj = xj+1  xj. Чтобы разностей получилось n, мы определим xn+1 как x1, т. е. будем считать нашу последовательность x циклической (так, что функция x со значениями xj в точках j будет периодической, с периодом n). Изложенная ниже геометрическая теория доставляет информацию о жордановой нормальной форме этого оператора A над полем .

Отображение A конечного множества M в себя задается графом с 2n вершинами x. Из каждой вершины x в этом графе выходит ровно одно ребро, оно ведет в Ax.

ПРИМЕР. При n = 3 граф имеет 8 вершин и 8 ребер, A(0, 0, 0) = (0, 0, 0), A(1, 1, 1) = (0, 0, 0), A(1, 0, 0) = (1, 0, 1), A(0, 1, 0) = (1, 1, 0), A(0, 0, 1) = (0, 1, 1), A(1, 1, 0) = (0, 1, 1), A(1, 0, 1) = (1, 1, 0), A(0, 1, 1) = (1, 0, 1).

Обозначая последовательность x = (x1, ..., xn) числом в двоичной записи

X = x12n–1 + x22n–2 + ... + xn · 1,

мы записываем предыдущий граф в виде графа с вершинами

являющимися вычетами по модулю 2n = 8. При n = 3 этот граф состоит из двух компонент связности,

Мы будем обозначать символом Om цикл из m циклически соединенных вершин. Знаком T2n будет обозначаться бинарное дерево из 2n вершин:

Знаком (Om  T) будем обозначать цикл из m вершин, оснащенный лесом из m корневых деревьев T, корнями которых являются вершины цикла Om (эти корневые деревья предполагаются состоящими из ориентированных направлениями к корням ребер):

Граф (Om  T2n) имеет, таким образом, m2n вершин.

Граф оператора взятия разностей A : M → M разбивается на компоненты связности. Например, для n = 3 он состоит из двух компонент, (O1  T2) и (O3  T2), изображенных выше.

ТЕОРЕМА 1. Каждая компонента связности графа любого отображения конечного множества в себя имеет цикл, и притом только один.

ДОКАЗАТЕЛЬСТВО. Конечность множества образов x, A(x), A2(x), A3(x), ... влечет существование повторения Ap(x) = Aq(x), а потому существование цикла периода p – q.

Если бы в одной связной компоненте было бы два цикла, то на соединяющей их цепочке ребер (x, ..., w) из какой-либо промежуточной вершины выходило бы два ориентированных ребра — одно к одному, а другое — к другому циклу. Теорема 1 доказана.

Прямые вычисления графов операторов взятия разностей A :  →  при n ≤ 12 приводит к следующим ответам (в наиболее сложном случае n = 12 приходится соединять всего 4096 вершин, и рисунок умещается на одной странице):

ПРИМЕР. Общее число вершин компонент графа с n = 11 есть (3 · 341 + 1)2 = 211.

В графе «соотношение» выписаны алгебраические тождества, получаемые следующим путем. Обозначим через δ :  →  оператор циклического сдвига последовательности: если δx = y, то yj = xj–1 (где x–1 означает xn, поскольку последовательности предполагаются циклически замкнутыми).

Очевидно, линейный оператор δ удовлетворяет тождеству δn = 1. Оператор взятия разностей A связан с ним соотношением A = δ + 1 (для вычетов по модулю 2 разность совпадает с суммой).

Из этих соотношений легко вытекают «соотношения» таблицы. Например, для n = 3 мы находим последовательно:

A = 1 + δA2 = 1 + 2δ + δ2 = 1 + δ2A3 = 1 + δ + δ2 + δ3 = 1 + δ + δ2 + 1 = δ + δ2A4 = δ + δ2 + δ2 + δ3 = δ + 2δ2 + 1 = 1 + δ = A.

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

В качестве меры сложности последовательности или функции мы будем использовать геометрические свойства графа операции взятия разностей A и положение вершины x в этом графе.

А именно, мы будем считать объект x более сложным, если длина цикла содержащей его компоненты графа больше. В пределах компонент с циклами данной длины вершины будут считаться тем более сложными, чем дальше они удалены от цикла.

Следующие примеры объясняют этот выбор понятия сложности рецептом Ньютона исследования эмпирических последовательностей значений функций. Самые простые функции — это константы x = 0 и x = 1. В этом случае период равен 1, а расстояние до цикла равно 0 в первом и 1 во втором случае (так что константа 0 проще константы 1).

Если функция x — многочлен степени меньше d, то для нее Adx = 0, так что вершина x принадлежит области притяжения аттрактора 0 периода 1.

Обратно, если вершина x притягивается к нулю, т. е. Adx = 0, то функция x — «многочлен» степени меньше d (как доказал Ньютон).

Под «многочленами» здесь понимаются приведенные по модулю 2 функции с целыми значениями

x(t) = a1tr + ... + ar+1,

коэффициенты которых — рациональные числа, а значения, приведенные по модулю 2, образуют последовательность x(1) ≡ x1, x(2) ≡ x2, ... периода n.

ПРИМЕР. Числа сочетаний ,  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.

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

ПРИМЕР. При первых значениях n числа  вершин деревьев оказываются такими:

Последняя строка указывает число «многочленов» периода n (приведенных по модулю два многочленов с рациональными коэффициентами и целыми значениями).

Среди 212 = 4096 функций периода n = 12 кольцу «многочленов» принадлежат всего 16 функций, а при периоде n = 16 все 216 = 65536 16-периодических функций являются «многочленами» (степеней 0, ..., 15).

ЗАМЕЧАНИЕ. Теорему 2 можно сформулировать как описание ядер итераций оператора A,

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

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

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

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

ПРИМЕР. При n = 2 мы получаем k = 1 и дерево (O1 * T22), состоящее из 22 = 4 вершин — «многочленов»

степени меньше 2 от переменной t. Других «многочленов» периода n = 2 не существует.

При n = 12 мы находим k = 2. Стабильное ядро четырхмерно и представляет собой корневое дерево из шестнадцати «многочленов» .

Из 212 = 4096 функций x периода 12 со значениями в  «многочленами» оказываются только эти 16 функций, притягиваемых аттрактором x = 0. Для этих «многочленов» A4x = 0, так что их степени не превосходят 3:

x(t) = a1t3 + a2t2 + a3t + a4.

В качестве базиса четырехмерного векторного пространства «многочленов» периода 12 над  можно взять «многочлены» , доставляющие числа сочетаний из t элементов.

ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 2. Решение разностного уравнения Ax = w относительно неизвестной функции x доставляется операцией «интегрирования»,

xj+1 = xj + wj (j = 1, 2, ...), если x1 задано.

Выбрав начальное условие x1 = 0 (либо x1 = 1), мы последовательно вычисляем все значения xi неизвестной функции.

Единственная трудность состоит в том, что результирующая функция должна иметь период n, т. е. должно выполняться соотношение xn+1 = x1. Поскольку , мы заключаем, что «интегрирование» доставляет искомое решение если и только если число единиц среди значений wj четно.

Например, единственные 2 решения уравнения Ax = 0 доставляются постоянными функциями x = 0 и x = 1, так как w = 0 не принимает значения 1 и число единиц в w = 0 четно.

Итак, ядро KerA =  состоит из двух постоянных функций 0 и 1.

Для вычисления Ker(A2) приходится решать уравнение Ax = 1 ( KerA). Если число n нечетно, то решений нет, т. е. Ker(A2) = KerA, так как число единиц в последовательности в правой части равно n и нечетно. Если же число n четно, то «интегрирование» доставляет последовательность x = (0, 1, 0, 1, 0, 1, ...) при начальном условии x1 = 0 и последовательность x = (1, 0, 1, 0, ...) при начальном условии x1 = 1.

Продолжая в этом случае «интегрирование» повторно, мы последовательно вычисляем всё большие ядра до тех пор, пока в правой части не появится функция w с нечетным числом значений 1 (у которой нет n-периодического «интеграла»).

Основное утверждение теоремы 2 состоит в том, что это препятствие встретится нам одновременно на всех ветвях бинарного корневого дерева последовательных «интегралов».

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

Предположим, что дерево прообразов нуля при r итерациях оператора A содержит цепочку независимых элементов

wr → wr–1 → ... → w2 → w1 → 0,

причем пространство Ker(Ar–1) состоит из 2r–1 функций

Тогда для векторов r-мерного пространства комбинаций

x = λ1w1 + ... + λrwr

мы находим

так что dim Ker(Ar) = r. Итак, зная один элемент wr r-го этажа бинарного дерева «интегралов», мы получаем их полный набор, проектирующийся оператором A в полный набор элементов предыдущего этажа. В каждый элемент r–1-го этажа проектируются два элемента x r-го этажа. Действительно, выбор λ1 = 0 и 1 в x приводит в Ax к одному элементу, поскольку Aw1 = 0.

Остается сосчитать, на каком этаже впервые встретится функция wr с нечетным числом значений 1.

С этой целью мы явно проведем итерированное «интегрирование» функции x ≡ 1 периода n.

Эти интегралы доставляются треугольником Паскаля

Тождество , определяющее треугольник Паскаля, показывает, что разности j-й косой строки образуют предыдущую косую строку (номер j – 1).

Соотношение верно и для вычетов по модулю 2, так что (при фиксированном j).

Поэтому все итерированные «интегралы» (с начальным условием при t = 0) — это приведенные по модулю 2 косые линии треугольника Паскаля, на которых j = 0 для исходной функции , а затем, по мере повторного «интегрирования», ответы w2w3, ... доставляют косые линии с j = 1, 2, ... .

Следовательно, для выяснения того, сколько раз удастся «проинтегрировать» функцию w1 в классе n-периодических функций, остается выяснить, при каких значениях j функция аргумента i будет иметь период n.

ЛЕММА. Если 2k–1 ≤ j < 2k, то наименьший период функции  по i равен 2k.

ПРИМЕР. Приведенный по модулю 2 треугольник Паскаля

показывает при j = (0), (1), (2, 3), (4, 5, 6, 7), 8 периоды (1), (2), (4, 4), (8, 8, 8, 8), 16.

ДОКАЗАТЕЛЬСТВО ЛЕММЫ. Проверим сначала, что число 2k является периодом при j < 2k:

Число есть число монотонно-решеточных путей из O в A. Каждый такой путь пересекает уровень горизонтали i в одной из точек B, для которой расстояние до точки A' равно m, где 0 ≤ m ≤ j < 2k. Числа путей AB и BO суть . Поэтому общее число монотонно-решеточных путей из O в A выражается суммой произведений

Первый сомножитель чётен при 0 < m < 2k, поэтому при j < 2k вся сумма сравнима по модулю два со слагаемым, для которого m = 0:

Итак, число 2k является одним из периодов функции  аргумента i, если j < 2k.

Покажем, что это — наименьший период, если вдобавок 2k–1 ≤ j. Меньший период должен бы быть делителем числа 2k, поэтому мы проверим, что число 2k–1 — не период.

Докажем, что при 2k–1 ≤ i < 2k число сочетаний  четно.

Введем обозначение I = i – 2k–1, так что 0 ≤ I < 2k–1. В этих обозначениях

По формуле ()

где 0 ≤ 2k–1 – m ≤ I, то есть 2k–1 + I ≤ m ≤ 2k–1. Из этих неравенств следует, что 0 < m < 2k. Поэтому биномиальный коэффициент четен, а значит доставляемая формулой () сумма K четна.

С другой стороны, . Поэтому число 2k–1 не является периодом функции по переменной i, когда 2k–1 ≤ j < 2k: при этом условии , .

Из доказанного выделенного выше утверждения следует, что число 2k–1 не является периодом ни при каком j ≥ 2k–1 (ведь если бы число 2k–1 было периодом, то и число 2k'–1, где k' > k, было бы периодом, вопреки выделенному утверждению с нужным k' вместо k).

Теорема 2 вытекает из доказанных утверждений следующим образом. Если n = 2k(2a + 1), то построение бинарного дерева Ker(Ar), описанного выше, будет успешным до тех пор, пока «j-кратные интегралы» от w ≡ 1 будут оставаться n—периодическими функциями от аргумента i.

Из доказанных сравнений видно, что наименьший период указанной функции переменной i равен 2r при 2r–1 ≤ j < 2r. Чтобы эта функция была n—периодической, нужно, чтобы число n = 2k(2a + 1) делилось на наименьший период, т. е. чтобы r ≤ k. Стало быть, стабильное ядро есть , что и доказывает теорему 2.

ТЕОРЕМА 3. Дерево, притягиваемое каждой точкой каждого цикла графа оператора взятия разностей A :  → , изоморфно дереву, притягиваемому точкой x = 0 (т. е. бинарному дереву  компоненты теоремы 2).

ЗАМЕЧАНИЕ 1. В частности, оснащение циклов всех компонент графа лесами аттракторов однородно: все оснащающие цикл корневые деревья одинаковы и всякая компонента графа имеет вид , когда n = 2k(2a + 1).

ЗАМЕЧАНИЕ 2. Число всех вершин всех циклов графа является степенью двойки: по теореме 3,

ПРИМЕР. При n = 11 мы получаем k = 0 и на четырех циклах 3 · 341 + 1 = 1024 = 211–1 вершин.

При n = 12 = 22 · 3 имеем k = 2, 2k = 4, n – 2k = 8. Число вершин всех 24 циклов таблицы есть

20 · 12 + 2 · 6 + 1 · 3 + 1 · 1 = 256 = 28.

ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 3. Объединение всех циклов есть векторное подпространство, к которому стабилизируется убывающая последовательность образов

Обозначая этот «стабильный образ» через Im(A), мы видим, что

что и доказывает утверждение замечания 2.

Для доказательства теоремы 3 заметим, что для любого линейного оператора L : V → W решения неоднородного уравнения являются аффинными подпространствами, параллельными ядру оператора:

L–1(w) = v + KerL, если Lw = v.

Для каждой точки x цикла 

C : ... → w2 → w1 → x → ...

графа оператора взятия разностей мы находим прообразы, являющиеся аффинными подпространствами

A–1x = w1 + KerA,

A–1sx = ws + Ker(As),

откуда видно, что весь бассейн, притягиваемый циклом C, расслоен на аффинные подпространства

В этом смысле мы можем ввести на бассейне цикла C  Om координаты и y  Ker(A). Действие оператора A записывается в этих координатах так:

A(sy) = ((s – 1), Ay).

Иными словами, на прямом произведении оператор действует перекошенным образом, причем подграф графа оператора взятия разностей на бассейне цикла Cm (т. е. компонента связности этого цикла в полном графе) изоморфен произведению , если n = 2k(2a + 1).

ПРИМЕР. Перекошенное действие изображено ниже (для m = 5, k = 1) двойными стрелками:

В этом примере A(w2z) = (w1y), A(w1y) = (x, 0), A2(w2z) = x.

Мы описали таким образом изоморфизм притягиваемого корнем x  C дерева стандартному бинарному дереву Ker(A), чем теорема 3 и доказана (вместе с замечанием 1 об однородности оснащения циклов лесами, составляющими их бассейны).

ЗАМЕЧАНИЕ. Аналогичное утверждение об однородности было доказано ранее [1] для операции x → x2 в произвольной конечной группе. Я не знаю общего результата, содержащего теорему 3 вместе с этим фактом теории конечных групп.

Таблица подсказывает много других общих утверждений, кроме доказанных выше теорем 2 и 3. Например, наибольшая из длин циклов компонент Om графа оператора взятия разностей делится (в каждом из рассмотренных в таблице случаев) на n.

ПРИМЕР. При n = 11 получается удивительный факт 341 = 11 · 31, опровергающий древне-китайскую гипотезу, согласно которой 2u – 2 делится на u только при простых u.

Делимость при простых u есть утверждение малой теоремы Ферма, число u = 341 является первым (наименьшим) контрпримером к попытке обращения этой теоремы Ферма.

ЗАМЕЧАНИЕ. Делимость на n наибольшего периода m > 1 цикла Om может объясняться симметрией δ порядка n, действующей на всём графе операции взятия разностей A = 1 + δ ввиду коммутирования  = δA.

Однако я не нашел ни объяснения тому факту, что частное от деления наибольшего периода m > 1 на величину n оказывается уменьшенной на 1 степенью двойки, m/n = 2q(n) – 1, ни разумной гипотезы о величине числа q(n): по таблице при n ≤ 12 имеем

Упомянутая выше делимость числа 2341 – 2 на 341 вытекает из делимости периода m = 341 на n = 11 так:

25 ≡ –1(11), 25 ≡ 1(31).

Поэтому 210 ≡ 1(11) и 210 ≡ 1(31), так что 231 ≡ 2(11), 231 ≡ 2(31), 211 ≡ 2(11), 211 ≡ 2(31). Значит по модулю 31 имеем 2341 ≡ (211)31 ≡ 231 ≡ 2 и по модулю 11 имеем 2341 ≡ (231)11 ≡ 211 ≡ 2.

Поэтому число 2341 – 2 делится и на 31, и на 11, а значит делится и на 341.

ЗАМЕЧАНИЕ. Если наибольший (при данном n) период есть m, то периоды m' > 1 остальных циклов таблицы с этим n являются делителями длины m длиннейшего цикла.

Частные m/m' в большинстве случаев (например, при n = 12) являются степенями двойки, но для n = 9 таблица дает m/m' = 63/3 = 21, поэтому я не решаюсь формулировать общих гипотез об этих частных (целочисленность которых уже не очевидна).

Все эти вопросы касаются, естественно, жордановых нормальных форм линейных операторов A в конечных векторных пространствах.

ПРИМЕР. Определим при n = p – 1, где p простое, специальную арифметически-логарифмическую функцию l   со значениями (при k = 1, 2, ..., n)

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

Для упрощения записи орбит мы будем считать последовательность x = (x1, ..., xn  бинарной записью числа X = x12n–1 + x22n–2 + ... + xn.

Ниже для p = 3, 5, 7, 11 и 13 (т. е. n = 2, 4, 6, 10, 12) приведены компоненты связности арифметического логарифма l.

СЛУЧАЙ p = 3, n = 2. Имеем log21 = 0, log22 = 1, поэтому l = (0, 1), L = 0 · 2 + 1 = 1.

Единственная компонента (O1  T4) имеет (в обозначениях X) вид

.

Арифметический логарифм L = 1 — самая сложная точка графа (наиболее удаленная от цикла).

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

21 ≡ 2, 22 ≡ 4, 23 ≡ 3, 24 ≡ 1.

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

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

Обведенная кружком вершина L является почти самой сложной точкой графа (расстояние до цикла почти максимально).

СЛУЧАЙ p = 7, n = 6. Вычисления, аналогичные приведенным выше (для логарифмов по основанию первообразного вычета, например для log3) проводят к арифметическому логарифму L = 11. Его компонента графа, O6  T4 — самая сложная (см. таблицу), и орбита точки L состоит, в X-обозначениях, из следующих вершин:

Таким образом, логарифмическая вершина L = 11 — самая сложная точка графа (она наиболее удалена от цикла и принадлежит наибольшей компоненте графа).

СЛУЧАЙ p = 11, n = 10. Здесь вычет 2 первообразен, и поэтому годятся двоичные логарифмы. Геометрическая прогрессия вычетов степеней двойки по модулю 11 доставляет последовательность (2, 4, 8, 5, 10, 9, 7, 3, 6, 1). Следовательно, арифметический логарифм есть функция l = (0, 1, 0, 0, 0, 1, 1, 1, 0, 1), так что L = 256 + 16 + 8 + 4 + 1 = 285.

Его компонента графа, O30  T4 — самая сложная при n = 10. Орбита арифметического логарифма L = 285 состоит из следующих 32 точек (в X-обозначениях):

Логарифм L имеет максимальную сложность среди всех функций периода n = 10: вершина принадлежит наибольшей компоненте и наиболее удалена от цикла.

СЛУЧАЙ p = 13, n = 12. Вычет 2 (mod 13) первообразен, геометрическая прогрессия степеней двойки доставляет арифметические логарифмы вычетов k = 1, 2, ... 12 равные

log2k = (12, 1, 4, 2, 9, 5, 11, 3, 8, 10, 7, 6),

т. е.

l = (0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0),

откуда L = 1266. Эта вершина принадлежит наибольшей компоненте графа, имеющей вид (O12  T16). Орбита логарифмической функции L состоит из следующих 15 вершин:

Логарифмическая функция L оказывается почти наиболее сложной среди всех 4096 функций периода 12 со значениями 0 и 1: вершина L принадлежит наибольшей компоненте связности и расположена на одном из деревьев ее леса на почти максимальном удалении от корня.

Список литературы

[1] В. И. Арнольд, Топология и статистика арифметических и алгебраических формул, Успехи математических наук 58 (2003), № 4, 3–28 (особенно §6, с. 15–18).


37
Показать комментарии (37)
Свернуть комментарии (37)

  • vitar  | 30.05.2006 | 08:49 Ответить
    Уважаемые организаторы!

    А планируется ли опубликовать видеозаписи лекцмй 13 мая?
    Ответить
    • editor > vitar | 30.05.2006 | 16:25 Ответить
      Планируется, и уже довольно давно :-). Дело в том, что обработка видеозаписи и приведение ее к приемлемому для публикации в интернете размеру заняла у организаторов трансляции неожиданно много времени. Обещают к завтрашнему дню закончить.
      Ответить
      • gav > editor | 19.06.2006 | 21:30 Ответить
        А можно как-нибудь приобрести видеозапись в более хорошем качестве?
        Ответить
  • ringel  | 13.08.2006 | 19:27 Ответить
    А чем лучше проигрывать эти видеозаписи? Windows Media Player выдает ошибку
    Ответить
    • pterik > ringel | 15.08.2007 | 13:17 Ответить
      mov файлы - это "родной" формат для пакета QuickTime.
      http://www.apple.com/quicktime/
      Прямая ссылка на инсталятор:
      http://appldnld.apple.com.edgesuite.net/content.info.apple.com/QuickTime/061-2915.20070710.pO94c/QuickTimeInstaller.exe
      Ответить
  • irakly  | 17.09.2006 | 15:05 Ответить
    Все-таки логарифм - не самая сложная функция. Для p=17, n=2^4 логарифм L=11892 - многочлен 13-й степени, а не 16-й. Т.е., разности обращаются в нуль на 13-м шаге. Это даже вручную можно сосчитать (правда, я считал на компьютере).
    Ответить
    • Эд > irakly | 18.01.2007 | 19:51 Ответить
      А как насчет всех p mod4=3. Для всех таких простых p чисел меньших 100 логарифм не просто почти самая сложная сложная, а самая сложная.
      Я не смог найти опровергающего примера и при некоторых p>100 (хотя для исходной гипотезы Арнольда кроме p=17 есть еще 4 простых числа меньших 100, для которых она неверна). Неужели такие совпадения - случайность?
      Ответить
    • pterik > irakly | 15.08.2007 | 13:31 Ответить
      А по моему академик прав, и для этого не нужно брать в руки калькулятор.
      Для логарифмов, рассматриваемых в лекции, существует непрямая аналогия с "обычными" логарифмами, например с натуральными логарифмами.
      Производная любой порядка от натурального логарифма не обращается в константу. Как следствие, при стремлении к бесконечности логарифм растёт медленее, чем любая степенная функция. Наверное именно с этим фактом и связана сложность логарифмов.
      Ответить
  • irakly  | 17.09.2006 | 21:05 Ответить
    Как указано в статье, последовательности с нечетным числом единиц нельзя "проинтегрировать", т.е. они являются самыми сложными в своей компоненте связности. Пусть n=2^k, l=(1,0,0,0,0,0...) последовательность, в которой первый элемент 1, а остальные нули. Т.к. компонента связности всего одна, оказывается, что такая последовательноость будет "самой сложной". Даже случайная последовательность из 65536 знаков, из которых 32768 единиц, оказывается "проще". Кажется, это не очень соответствует интуитивному понятию сложности... Похоже, открытие Владимира Игоревича придется-таки закрыть. Впрочем, идея все равно интересная. Хочу еще посоревноваться с учениками В.И. и рассчитать структуру графа хотя бы до n=50. Может, обнаружится что-то интересное?
    Ответить
    • avmorkot > irakly | 26.12.2006 | 10:18 Ответить
      Определение сложности конечных последовательностей можно попытаться модифицировать. (Может быть, это уже кто-нибудь сделал?) Например, так.

      Пусть нужно узнать сложность последовательности a. В соответствии с определением В.И. Арнольда для каждой последовательности введем параметр s ("локальная сложность"), в пространстве последовательностей с метрикой r(x,y)=СУММА по i от 1 до n (модуль(x_i-y_i)) рассмотрим шар с центром в a и каким-нибудь радиусом (может быть, зависящим от n), усредним s по этому шару и то, что получится, назовем сложностью последовательности a.
      Ответить
  • grigus  | 01.02.2007 | 16:02 Ответить
    Оператор взятия разностей циклических слов можно рассматривать как клеточный автомат.Таким автоматам посвящены сайт и книга
    A New Kind of Science.
    Там должны быть графы и таблицы, подобные приведенным в докладе.
    Последние версии Mathematica позволяют проводить эксперименты с cellular automata.
    Ответить
  • relax  | 15.04.2007 | 22:48 Ответить
    Интересно отметить, как стоятся здесь графы: в одной и той же точке можно оказаться из нескольких точек, зато есть только один путь, которым можно уйти из определённой точки. Это напоминает то, как Пригожин поясняет необратимость времени в системах, стремящихся к равновесию: к одному и тому же исходу ведёт множество отличных друг от друга начальных условий.
    После просмотра доклада пришёл в голову аналог кубика Рубика:

    "Связные компоненты" графа этой штуки или циклические движения, можно получить вращениями вокруг перпендикуляров к трём плоскостям, отсекающим треугольники на каждой её грани, а "деревья" можно прилепить на место выпуклых пятиугольников с вершинами этой фигуры. А можно и соединить две такие штуковины, предварительно удалив у каждой по выпуклому пятиугольнику с вершиной, тогда получатся две связанные "связаные компоненты".
    Ответить
    • relax > relax | 15.04.2007 | 22:50 Ответить
      собственно штуковина:
      http://taip.nm.ru/Rubik.jpg
      Ответить
  • int  | 02.01.2008 | 02:28 Ответить
    Я хоть и не матеметик, а про логарифмы ничего не понял, пожет со второго раза пойму, т.к. по видео не очень понятно, но вообще очень интересно.
    Ответить
    • int > int | 02.01.2008 | 02:30 Ответить
      Попробую программу про перестановки написать, это элементпрно.

      Я считаю сложность ещё можно определять простотой сжатия информации, например вместо 1111111111111111111111 можно написать N единиц.

      Немного в сторону, например иногда номера телефонов пишут не 232 22 32 а
      232 2 232, но они не учитывают то, что не они одни такие и получается что нужно запоминать ещё и формат записи.
      Ответить
  • almir  | 23.02.2008 | 18:41 Ответить
    Уважаемый Владимир Игоревич!
    Я недавно познакомился с Вашим интервью "АКАДЕМИК В. И. АРНОЛЬД:ПУТЕШЕСТВИЕ В ХАОСЕ", выступлением в Государственной Думе и публичной лекцией.
    К моему большому удовольствию Ваши идеи о школьном обучении учащихся мне очень близки и понятны.
    Моё внимание, в частности, привлекли к себе Ваши две теоремы.
    Теорема 1. 'В каждой компоненте связности монады обязательно имеется цикл'.
    Доказательство. Множество точек конечное, поэтому, если мы выйдем и пойдём по стрелочкам, будем идти, идти, идти, когда-нибудь вернёмся в точку, где уже были раньше. Потому что их конечное число. Тогда от первого посещения этой точки до второго будет цикл. Конец доказательства.
    Математический цикл, о котором речь идёт в Вашей теореме и в её доказательстве, может быть описан, по-моему, значительно полнее и детальнее.
    Определённое время существования цикла в неопределённом пространстве подразделяется на 7 этапов: детство, юность, молодость, зрелость, старость, дряхлость и пора конца существования, смыкающегося с началом нового цикла. Шесть этапов (без последнего седьмого) цикла развития логического понятия были описаны Гегелем в малой 'Логике'. Три формы трёх этапов цикла (единичность, особенность, всеобщность) приходятся на развитие 'предварительного' понятия. Следующие три формы трёх этапов цикла (всеобщность, особенность, единичность) приходятся на развитие понятия как такового.
    Монада американского учёного-путешественника Уильяма Морриса Дэвиса (1850-1934) имеет форму закона развития рельефа Земли, названного им 'географическим циклом', который включает в себя шесть аналогичных форм без седьмой. Общие принципы идеального цикла Дэвис распространил на карстовый рельеф, пустынный рельеф, горноледниковый рельеф и рельеф морских берегов.
    Используя Вашу терминологию, могу сказать, что цикл, имеющийся в каждой компоненте связности монады, мною рассматривается в определённости цикла колебаний маятника часов с гирей, типа ходиков. Аналогичных примеров - не перечесть.
    Теорема 2. 'В компоненте связанности монады не может быть двух циклов'.
    Не стану цитировать Ваше доказательство теоремы, так как она привлекла к себе моё внимание не своим доказательством.
    Из неё, по-моему, можно сделать вывод о том, что 'В обязательных двух компонентах связанности монады обязательно имеются два цикла'.
    К двум циклам может иметь непосредственное отношение интерпретация Дирака к своей теореме спина электрона. Из его теоремы следует, что электрон-позитронная пара в качестве двух компонентов связанности монады имеют два значения.
    Дело в том, что электрон и позитрон, не изменяя своей внутренней энергии, взаимодействуют друг с другом и с внешней средой. Они поглощают рассеянную энергию внешней среды, изменяют её форму и обмениваются энергией внешней среды между собой Затем они вторично изменяют форму внешней среды и, наконец, излучают её в рассеянной форме во внешнёю среду.
    Аналогами монады Г. В. Лейбница и В. И. Арнольда могут быть правое и левое полушарие мозга человека, напольные самозаводящиеся часы в Амстердамском музее и другие. Всех - не перечесть.
    Таким образом, энергия внешней среды проходит через электрон-позитронную пару в двух прямо противоположных направлениях в виде двух различных по величине порций-квантов. Чтобы электрон-позитронная пара повернулась на 360 и вернулась в прежнее положение, её электрону и позитрону нужно, каждому в отдельности, повернуться на 720.
    С уважением, Миргородский Александр Илларионович.
    www.mirgorodsky.ru
    Ответить
  • edictum  | 29.09.2008 | 00:11 Ответить
    Может я ошибаюсь, но в году вроде 365, а не 364 дней, без високосного.
    Так что, похоже к астрономии это имеет весьма отдаленное отношение.
    Ответить
    • klein0 > edictum | 11.10.2008 | 05:31 Ответить
      Владимир Игоревич Арнольд: Я выписал и получил: компонент две. Оказывается, компонент две, они одинаковые. Имеется два одинаковых цикла, сумма длин которых 728. Трудный вопрос: какая длина каждого цикла? Какая длина каждого цикла? 728 надо разделить пополам. Значит, длина каждого цикла будет 728 пополам - равняется 364. А теперь мы, во-первых, обращаемся к астрономии. Мы получили длину года без високосного дня. А теперь мы обращаемся к моей теореме. Длина цикла делится на длину последовательности. А длина последовательности была 7. Значит, получаем вывод: 364 делится на 7. А теперь делим: 364 разделить на 7 - что получается? Ну, мои школьники умели. Сколько? 52 - число недель в году. А это равняется: 13 умножить на 4. Следовательно: 364 - год - состоит из 13 месяцев, лунных, по 28 дней в каждом. Что и требовалось доказать.

      edictum: Может я ошибаюсь, но в году вроде 365, а не 364 дней, без високосного. Так что, похоже к астрономии это имеет весьма отдаленное отношение.

      to edictum:

      - Да, ошибаетесь. :)) При создании "Земли + людей" не удалось замкнуть 3 цикла (слишком много параметров должно было быть сбалансировано, поэтому теория и практика немного различаются) - поэтому год 365, а не 364, у женщин месячные циклы, а человек должен спать.

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

      Привет! :))
      Ответить
    • drusha15 > edictum | 25.09.2012 | 04:51 Ответить
      edictum, а когда и какого Петрика смущало несоответствие реальности (результатов наблюдений, опытов) его теории? Реальность в этом случае отметается, а теория возводится в догму. Рецепт прост.
      Ответить
  • Jammer  | 28.10.2008 | 11:52 Ответить
    Из статьи вынес только одно, математика - жестокая мозговая патология :)))
    Ответить
    • drusha15 > Jammer | 25.09.2012 | 04:59 Ответить
      Вы такой же вывод могли бы сделать про физику, послушав лекцию какого-нибудь Петрика. Однако, это не так. Так и здесь - не надо всех математиков под одну гребёнку. Среди них есть люди, совершающие великие прорывы, которые потом исследователи в других дисциплинах с успехом применяют. Не судите всех по одному.

      Кстати, может у него другие работы есть, более применимые. Эйнштейн тоже много в чём ошибался, однако ценим мы его не за его ошибки.
      Ответить
  • клетка  | 26.02.2009 | 20:29 Ответить
    Красив ученый , великая работа , но .... не все учел , а многое не знал . Что сразу не понравилось ? Монада . Неземное на земле не создать , но понять бы надо . Как живет дерево ? ПЕРИОДАМИ . А где они ? А как живет человечество ? Периодами . Неверна и бинарность у дерева - она прерогатива высших существ разумности особой - только их . В каждом из нас встроены эти самые бинары-труженики , ведущие отсчет нашего земного времени с отсчетом его в космическое наше время - вечное времене . Мы - вечны своим основным видом космических существ . Мы - не тела . Мы - в нем -урановоэнерговыстроенное .

    Могла бы добавить немного и о логарифмах и их состояниях во всем живом и во всей природе . А их антипод? Выяснили ли роль корня ? Там диво , что за роль . Людмила Белик
    Ответить
    • me123 > клетка | 15.01.2010 | 22:47 Ответить
      согласен с вами, клетка. о муравьях не подумал академик, а ведь мы муравьи, куда умнее клеток, мы даже по логарифмической линейке бегать можем взад и вперёд.
      Ответить
  • oxydan  | 04.06.2009 | 20:57 Ответить
    Ув. Владимир Игоревич!
    У меня не сходится с Вами случай n=12.
    Получается A^16=A^4, а не A^16=A^2
    Я воспользовался тем, что отображение A = x^2+x, которым Вы оперируете это линейный полином над простым полем характеристики 2 и оперировал с матрицей, которая представляет отображение A. Можно идти с другой стороны - по произвольной монаде построить полином над конечным полем, только степень полинома становится экспоненциально большой..
    Ответить
    • oxydan > oxydan | 07.06.2009 | 15:46 Ответить
      Виноват.. в Докладе в Московском математическом обществе такой ошибки нет..
      Ответить
  • Andrey_97  | 25.08.2009 | 02:10 Ответить
    Владимир Игоревич! Какую литературу Вы порекомендуете? Как относитесь к трудам, например, Акилова, Л.В. Канторовича?
    Ответить
  • velix  | 16.11.2009 | 03:23 Ответить
    Были приведены примеры "хорошо случайных" последовательностей (номера проезжающих автомобилей), но только вскользь упомянуты неслучайные.
    В частности, мне интересно, если дать человеку задание произнести вслух последовательность нулей и единиц (или что то еще сделать по возможности случайно и хаотично) будет ли это случайным в смысле, изложенным в лекции?
    Вдруг это будет косвенный метод определения мозговых отклонений? (типа того что нормальный человек выдает обычно неслучайные последовательности, больной - случайные)
    Ответить
  • me123  | 15.01.2010 | 22:40 Ответить
    самое замечательное в статье то, что никакого отношения к сложности ""сложность"-по арнольду" не имеет. а всё остальное, конечно, верно - переливание из пустого в порожнее. ха-ха-ха. хотя, некоторым детям, конечно сложно бывает...
    у меня тоже есть "me123-гипотеза": 0 сложнее 1.(или, наоборот).
    Ответить
    • drusha15 > me123 | 25.09.2012 | 04:46 Ответить
      - это у Вас аж две гипотезы - прямая и обратная. Можно учереждать премию тому, кто первым докажет. А Вы уже вошли в анналы истории математики, сформулировав эти гипотезы.
      Ответить
  • дядюшка Ро  | 16.12.2010 | 20:37 Ответить
    А, что будет если в степени числа поставить 3 миллиарда?.. Кстати, такое число фигурирует где-то в моих генах... Я бы хотел его найти на числовой оси, но нет оснований. Одни желания...(дядюшка Ро)
    Ответить
  • дядюшка Ро  | 17.12.2010 | 11:19 Ответить
    А я тоже так делал. Еще в школе... Интересно... Брал 10 миллиардов лет, переводил в секунды и извлекал корень кубического числа. Получал полмиллиона секунд. Как раз неделя, что в библии записана.
    Ответить
  • guryan  | 19.10.2011 | 19:17 Ответить
    Господи боже, теперь я понял, почему наука в глубоком кризисе. Вы же заменили физическую реальность математическими закорючками и пытаетесь высосать из нее какие-то истины. Математика - это даже не наука и нет в ней никаких истин. Это просто язык описания, и довольно примитивный. А языком можно описать и реальный предмет и написать фантастический рассказ. Я могу вам математически точно показать, что железный лом при нагреве до 1 миллиона градусов Цельсия, удлинится на 50 сантиметров. Ну и как это соотносится с реальностью? Утверждения ученых о падении материи самой на себя при гравитационном коллапсе, по степени идиотизма может конкурировать только с росказнями барона Мюнхгаузена о вытаскивании самого себя за волосы из болота. Природа намного проще,господа, чем вы тут напридумывали... не училась она никакой математике...
    Ответить
    • drusha15 > guryan | 25.09.2012 | 04:40 Ответить
      Не согласен только с тем, что математика "примитивный" язык описания. Язык как язык, местами даже очень сложный. Очень полезный, когда мы пытаемся количественные характеристики изучить.

      Но вот в таком применении, как в этой лекции... Хмм. Это "вычисление числа зверя" просто какое-то.
      Ответить
      • guryan > drusha15 | 22.10.2012 | 13:14 Ответить
        Математика полезна, когда нужно посчитать тугрики, площадь коттеджика или могилки. http://yadi.sk/d/MSViP5Jr01MAs
        Ответить
    • Мерзкая Бабайка > guryan | 25.11.2012 | 11:06 Ответить
      Математика - это действительно довольно "примитивный" язык описания, но лучшего ничего пока не придумано. Математика имеет дело с конструкциями априори, и именно по этому язык становиться сложен. А вообще в истории математики попеременно появлялись то "решатели" такие как Арнольд (Лежандр, Лопиталь, Кеплер, Колмогоров), и "обобщатели" - Галлилео, Лагранж, Гаусс. Поэтому здесь нет ничего сверхъестественного - это просто дальнейшее развитие науки.
      Ответить
  • drusha15  | 25.09.2012 | 04:31 Ответить
    Петрик просто отдыхает, а средневековые алхимики и астрологи с завистью кусают себе локти.

    Особенно понравился последний пассаж про нумерологию и длину года в днях. ;-)
    Ответить
  • роткив  | 16.07.2013 | 13:13 Ответить
    математику, как инструмент мне кажется не все достаточно полно понимают в её динамике развития по соответствию физических действий и построений в микромире,который в данной ситуатции для нас просто закрыт.а приложить к нему математику в данном классическом варианте, это опять же просто утонуть в прикладных комбинационных поисковых алгоритмах. в микромире на эти классические прилагаемые действия ответы разные.поэтому физика сейчас гуляющая,которая даёт вам лишь возможность в преобразовании летать только на горелках.не надо сейчас научной энтропии, надо переходить на другой уровень полной физической взаимосвязи с окружающим нас мире. ущербно для нас-да,улыбаться придётся по программе.без понимания самого элементарного действия-движения,не поймёте эволюционную строительную роль двух его сторон-то есть базовую парность в выявлении,в них показателей асимметрии.математику надо оживлять и уходить от классики механических машин.
    Ответить
Написать комментарий
Элементы

© 2005-2017 «Элементы»