Владимир Арнольд

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

Я буду рассказывать про теорию самого общего математического объекта, который только есть. Я его называю для простоты «монадой» по Лейбницу и объясню сейчас вам, что это такое.

Значит, монада. Это самый простой математический объект, какой только можно придумать.

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

Во-первых. Чтобы понять монаду, мы будем ее изображать в виде графа. Значит, граф монады строится таким образом: берется конечное множество точек. Это множество монада отображает в себя, то есть для каждой точки x из этого множества монада переводит ее в какую-то точку y — есть Аx, отображение M в себя. Так вот, соединим каждую точку x стрелочкой с той точкой, в которую она отображается. Вот y, например, вот эта точка, тоже куда-то отображается. Например, сама в себя. А эта точка отображается, например, вот в эту. Ну, еще осталось тут указать, куда эта точка, ну, например, вот сюда.

Вот монада из четырех точек, и нарисован граф этой монады. Вот как он устроен. Это определение первое, поэтому самое простое понятие. Это вам не суперструна. Это просто.

Теперь рассмотрим теорему первую, простейшую.

Теорема: «Граф каждой монады — разбивается на связные компоненты».

Вот эта монада связная — одна компонента только. А может быть, тут рядом имеются еще какие-то точки — в этом же множестве М — и монада их тоже переводит друг в друга. Тогда будет несколько компонент связности.

Теорема: «В каждой компоненте связности монады обязательно имеется цикл».

Компоненты без цикла не бывает. Доказательство: множество точек конечное, поэтому, если мы выйдем и пойдем по стрелочкам, будем идти, идти, идти, когда-нибудь вернемся в точку, где уже были раньше. Потому что их конечное число. Тогда от первого посещения этой точки до второго будет цикл. Конец доказательства.

Второе утверждение: «В компоненте не может быть двух циклов».

Доказательство: если бы в какой-нибудь компоненте было два цикла — между ними была бы связь, тоже из стрелок как-то состоящая. И тогда где-то посередине связи была бы точка, из которой можно идти по стрелкам и к одному циклу, и к другому. А ведь тут же отображение: из каждой точки выходит только одна стрелка — приходить может много, а выходит только одна. Поэтому связь между двумя циклами невозможна. Не бывает связи между двумя циклами. Цикл только один.

Итак, как же устроена монада?

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

Вот у нас имеется какая-то деятельность, мы что-то решаем, какие-то задачи, какие-то объекты исследуем. Среди этих объектов бывают объекты простые, а бывают объекты сложные. Как различать, какие объекты простые, а какие сложные? Что такое сложность объекта? Конечно, этой задачей много занимались. Например, в теории алгоритмов имеются алгоритмически разрешимые проблемы и алгоритмически неразрешимые, имеется понятие алгоритмической сложности. Но дело в том, что во всех этих теориях рассматриваются бесконечные наборы и рассматривается сложность задач, у которых бесконечное число возможностей. И говорится, что какая-нибудь такая задача, ну, скажем, проблема Ферма (x^n + y^n = z^n)... Вот можно поставить вопрос: разрешима ли она алгоритмически, есть ли алгоритм, который будет решением. Так это значит вот что: ведь если n фиксированное, если x, y, z фиксированные, то проверить, так это или не так, всегда можно, это легко. Задача возникает из-за того, что нету ограничения, что система не ограниченная — бывают очень большие x, y и z, и узнать надо про все сразу, про всё бесконечное множество надо сразу узнать. А я хочу сложность определять не для бесконечных задач, а для конечных.

Вот пусть имеется некоторый конечный объект. Например, программа, скажем. Сложная она или простая? Я сейчас придам точный математический смысл — при помощи монад — понятию «сложности задачи». Я взял самую простую задачу, самый простой объект из математических объектов — последовательность нулей и единиц. Вот, значит, возьмем — бинарные последовательности это называется — возможно брать языки любые, последовательности любые, символы любых алфавитов. Ну я возьму самый простой алфавит, в котором всего есть 0 и 1 и ничего другого. И вот последовательность — это есть несколько нулей и несколько единиц, записанных подряд. Вот: 001001. Вот последовательность длины шесть, из шести элементов. Значит, я их буду писать так. Вот это я буду обозначать x, первый ноль — это x1, который равен нулю, вот это x2, вот это вот xn — тогда последовательность длины n. В моем примере n равно шести. Спрашивается: вот эта последовательность (видно, что довольно простенькая — 001001), а бывает последовательность... — вот видите там есть последовательность 010101 — она простенькая, — а вторая последовательность 010011 — она уже ... не так легко продолжать, не так легко догадаться, как она написана, по какому принципу. Но можно до любого n, конечно, такие вещи делать, и мы и будем так делать.

Но вот спрашивается: в каком точном смысле вторая последовательность сложнее первой?

Монады дают ответ на этот вопрос, и вот какой ответ: рассмотрим все последовательности длины n из символов 0 1. Таких последовательностей будет 2^n штук. 2^6, например, длины 6, как у меня тут, — 64 последовательности.

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

Вот, например, если последовательности длины 2 — 00, 01, 10, 11 - можно говорить, что это квадрат: четыре вершины квадрата. - а можно говорить, что это векторное пространство размерности 2 над остатками от деления на 2.

Вот арифметика по модулю 2, значит... Плоскость там имеет всего четыре точки. Вот эти четыре точки здесь и есть. Вот точно так же в общем случае, значит, если у нас длина n, то это куб в n-мерном пространстве. Если n равно трем (длина 3), то это будет восемь точек, и они образуют кубик вот такой. Так, хорошо.

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

А придумал этот способ Ньютон, который уже рассматривал ту задачу, о которой я буду рассказывать. Задача у него была такая: дана функция, и нужно определить, простая она или сложная, как написать формулу для этой функции.

Ну вот, например, можно считать, что здесь у меня написано как последовательность, но можно считать,что x — это функция, xi — это функция от i. Значит, это функция, которая определена на дискретном множестве из n точек, конечном множестве от единицы до n и принимает значения либо 0, либо 1 в этих точках.

Как Ньютон исследовал функции, как он исследовал, например, многочлен — функция или нет, — как он это делал?

Он предложил: надо рассмотреть разности у этой функции. Вот как Ньютон это делал. Определение у Ньютона было такое: вот если какая-то последовательность есть — вот, скажем, давайте возьмем эту самую 001001, да — то образуем новую последовательность таким образом: возьмем разности соседей в исходной последовательности, первые разности возьмем. Причем это остатки от деления на 2, и мы разности вычитания будем брать по модулю 2.

0 минус 0... Сколько? Ноль. 1 минус 0? Сколько, Митрофанушка? Один! 0 минус 1? Тоже один. По модулю 2. 0 минус 0? Ноль. 1 минус 0? Один. Но чтобы получить последовательность длины 6, а не 5, я буду считать, что после последнего элемента опять идет первый, чтобы она была как бы периодическая такая. Тогда не будет меняться длина. Значит, после этой единицы идет как бы этот ноль, поэтому получится опять единица. Вот из этой последовательности получилась вот такая вот последовательность, а можно брать следующую разность и так далее.

Так вот. Ньютон заметил: если функция была константа (000000 или 111111), то первые разности будут нули. А если первые разности будут константа, то функция будет многочлен первой степени. А если вторые разности константа, то не больше второй. И так далее. Ну да. У второй вторые разности константа. А третьи нули.

Так вот. Определим оператор А, который действует на последовательность x и определяет последовательность y по такой формуле: yi = xi+1 – xi.

Разности я вам показал, а вот формула для них. Вот и всё. Это операция Ньютона. Мы получили отображение из нашего куба, из множества вот этих самых... Куб наш (M мы его обозначим) — это множество вершин — это, значит последовательности длины n, у которых элементы 0 и 1. И операция: каждой такой последовательности сопоставляем новую — вот операция А. Получается отображение в себя.

Раз получили отображение в себя, то, значит, есть монада. Есть монада, есть граф. Есть граф, есть циклы и деревья. И вот в терминах этих геометрий, этих монад, и будет дано сейчас определение сложности.

Так вот. Я обещал эксперимент — вот он будет сейчас. Дано число n, найти граф монады операции Ньютона. Какая будет картинка?

Давайте мы начнем вот с чего. Возьмем n = 3 и просчитаем всё явно. Если n = 3, то точек всего восемь. И для восьми-то точек мы сумеем посчитать разности? Последовательность длины всего 3 — это проще, чем в этом примере, но давайте посмотрим. Какие бывают последовательности нулей и единиц длины 3? Какие последовательности? Вот бывает последовательность 000. Бывают другие длины три? Бывают. Еще какие? 001? Вот. И возьмем еще... ноль...

Знаете, я-то буду вот что считать. Я буду считать, что у меня тут ученые слушатели, которые знакомы с компьютерами и, значит, с бинарными числами и могут считать: такая последовательность — это просто двоичная запись числа в двоичной системе цифрами. Там две цифры только — 0 и 1. Значит, вот это вот двоичная запись числа ноль. А вот это двоичная запись какого числа? Один. А поэтому мы возьмем число 2 и его тоже запишем. Как записывается? 010. А теперь возьмем число 3 и его запишем. Как число 3 двоично записать? 011. Бывает еще 4. Четыре — 100. Бывает 5. Пять... что? Я что-нибудь неправильно написал? Хорошо!

Теперь давайте считать разности. У последовательности 000 какие разности? Она же сама! Значит, 0 переходит в себя. Вот мы уже начали наш граф строить. У последовательности 001 какие разности? 011. Теперь, это где стоит? Вот он. У последовательности 010 разности 110. Это где? Шестерка. Так. 011 — разности: 101... 101 — пятерка. Так, теперь здесь. 110 — шестерка. И дальше... Что? Из шестерки: 011. 011 — где это? Вот, тройка. И из семерки три нуля. Пятерка: 110 — 110, шестерка. Из четырех? 101... 101 — где это? 101 — пятерка, вот. Правильно, спасибо! Вот, совсем как со школьниками.

Так вот, получается... Получается граф этой монады, который у меня вон там нарисован. Там-то у меня правильно нарисовано. Значит, мы видим: компонент две — один цикл длины 3, а другой цикл длины единица. Цикл длины 3 я обозначаю символом O3, цикл длины единица я обозначаю символом O1.

Теперь деревья, которые к этим аттракторам стремятся. Там они длины единица, видите, вот здесь... Этот самый цикл — это кто? Цикл образует 3, 5... Три... Что, 3, 5, 6, да? Вот, возьмем 3, 5, 6. 3, 5, 6, 3 — вот цикл. Да. Но в тройку входят кроме шестерки еще единицы. И так повсюду. Значит, вот эта компонента — она вот такая: просто треугольник, который цикл, и он притягивает — каждая его вершина — притягивает еще дерево, которое из двух вершин всего, очень коротенькое такое. Росток такого дерева, вот так. Вот. Хорошо!

Значит, вот мы проделали этот эксперимент. Решение задачи, о которой я говорил, дальнейшее при других n совершенно такое же. Только вместо восьми точек здесь будет 2^n точек. Вот. И, знаете, я, как маленький, стал делать n равное 4, 5... и дошел до 12-ти. При двенадцати число точек будет два в двенадцатой степени, то есть четыре тысячи. И, значит, они у меня еще уместились, эти точки, на одном листе. И поэтому я мог нарисовать этот граф. А при 13-ти они у меня уже на одном листе не умещались, и поэтому я его не сумел нарисовать, и поэтому я уже не посчитал до конца.

Вот. Вот, значит, здесь вы видите n равное двум — очень простенький ответ: там О1 T4, то есть имеется такое вот дерево высоты четыре... T4 — это дерево из четырех вершин, вот такое. Значит, мне потребуется такое понятие — бинарное дерево. Бинарное дерево — это дерево, у которого в каждой точке ветвления две ветки расходятся. Вот. И при этом они так до самого верхнего этажа, а на верхнем этаже они... Ну, значит, T4 — это такое дерево. У него 4 вершины — вот они. И вот они устроены таким образом. Ну, при этом, так как он аттрактор, еще имеется цикл. Вот он притягивается к циклу, и T4 — это вот такое вот дерево, которое вот так просто устроено. Ну, а T8 — это, соответственно, будет еще в каждую из этих вершин тоже по две. Тогда их станет 8. 16 — еще больше. И так далее. T2 в степени n — это значит, будет соответствующее число n этажей. Так вот, в этой таблице — там и указано — оказывается, странным образом, все компоненты имеют такой вид: каждая компонента оснащена лесом из деревьев, и деревья всех вершин компоненты, всех вершин — циклы у деревьев все одинаковые. И притом бинарные всегда. Там загадочное число, какое именно бинарное, из каких именно вершин. Вот, например, если длина последовательности n равна 11, то здесь цикл длиной 341. А если n равно восьми, то дерево T256 — это бинарное дерево высоты 8. Значит, восьмиэтажный дом такой вот расцвел. Вот так вот, оказывается.

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

Ну вот, например. Последний столбец в этой таблице, в каждом месте последний столбец — это компонента специального вида. Цикл длины один, вот как здесь, вот как у этого дерева. И к нему привязано бинарное дерево и ничего другого. Просто бинарное дерево, у которого нижняя вершина переходит сама в себя. Никакого большого цикла там нету.

Теорема: такая компонента есть при любом n и точки вершины x, которые ей принадлежат, — не какие попало, а это очень интересные точки. А вот что это такое: они и только они являются многочленами. Функция x, которую мы исследуем, для которой мы строили дерево, является многочленом, если и только если эта точка в графе попадает на эту последнюю часть, вот на это дерево.

Отсюда следует, что многочлены — вовсе не все функции. Вот, например, при n равном двум все функции многочлены, при n равном трем — нет, при n равном четырем все функции многочлены, при n равном пяти — нет, и так далее.

Мы изучаем пространство функций, функциональное пространство. Но, в отличие от анализа обычного, здесь у нас конечное число точек в этом функциональном пространстве. И мы изучаем комбинаторику этого функционального пространства из конечного числа точек. В нем есть дифференциальные уравнения, синусы, косинусы, экспоненты... А мы сейчас изучаем многочлены.

Многочлены — это последний столбец, причем интересно: этот последний столбец будет единственным столбцом в каких случаях? Посмотрите: при n равном двум, четырем, восьми... Вот здесь написано, сколько компонент. Одна компонента — когда? Когда n равно двум, четырем, восьми...

Ну, дальше у меня тут нету таких случаев, но если посчитать дальше, то в 16-ти. И школьники уже догадывались, и уже в этот момент начинали кричать — в отличие от нобелевских лауреатов, которым я читал тоже такую лекцию, которые ничего не понимали, — но школьники сразу замечали: компонента только одна, если и только если n — степень двойки. Если число n — степень двойки, то все функции — многочлены. Это кольцо многочленов. Все функции — многочлены для функции на конечном числе точек тогда и только тогда, когда число точек — степень двойки.

Ну вот. Причем сколько там многочленов — тоже можно посчитать, раз только одна компонента. А в других случаях получаются тоже интересные наблюдения, но я не буду уж перечислять — тут много есть интересных открытий, которые кто захочет, тот сделает сам.

Одно из открытий, которое я сделал, глядя на это таблицу. Смотрите. Для каждого n имеется самый длинный цикл. Если n = 10, то самый длинный цикл — длины 30. Если n = 9, то самый длинный цикл длины 63. Если n = 13, то самый длинный цикл имеет длину 819. Спрашивается: какая длина у самого длинного цикла? Ответ: длина самого длинного цикла делится на n. Вот если 10, то 30 — делится, и в частном получается 3. Если 9, то 63 — делится, и в частном получается 7. А какие частные? 3, 7... — что это за числа? Школьники догадались. Математика — это экспериментальная наука: можно глядеть на эксперимент и получать ответы. Ответ: частное будет степень двойки без единицы. 7 — это два в кубе без единицы, 3 — это два в квадрате. Даже если вот возьмете там подальше там 819, тоже будет верно — надо разделить только на 13. Это долго, но если вы разделите, то будет 63.

Это всё верно не всегда, а неверный пример нашли мои ученики на компьютере. Оказывается, если n = 23, то это неверно. Если n = 23, оказывается, беда вот в чём. Оказывается, если n = 23, то самый длинный цикл очень длинный, но длина этого цикла уже сама степень двойки минус единица, и делить на n не надо. Она уже степень двойки без единицы - 2047.

Вот таблица этих самых делений. Вот периоды самые короткие выписаны здесь. При больших n, не только при тех 12-ти, которые я посчитал сам, но и при тех, которые посчитали мои ученики. Вот здесь вот имеется число 23, которое дает период самого короткого цикла 2047. 2047 — если его поделить на n, которое 23, оно делится на 23. Но получится 89, которое ни к какой степени двойки не имеет никакого отношения. Так беда здесь в том, что число 2047 само равно 2048 без единицы. А 2048 — это степень двойки.

Теперь вот из вычислений я показываю пример одной из компонент. Значит, есть длина 6 — цикл длины 6, вот он. И у него деревья оказываются T4 — значит, деревья из 4-х вершин к нему привязаны. Но я изображаю эти последовательности двоичными числами. Я, например, там пишу 29 или 40, там, написано. Но это имеется в виду последовательность из 4-х нулей и единиц, которая в двоичной записи будет давать это вот. Так вот. Эта последовательность чисел — вот я их посчитал просто, до 12-ти я всё посчитал просто — там не такие уж длинные вычисления, — я всё посчитал эти графы, получил замечательные картинки, и так далее.

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

Определение: последовательность называется более сложной, если она принадлежит циклу, который имеет большую длину. А если две последовательности имеют циклы одинаковой длины, то сложнее та, которая дальше от цикла. Которая на дереве на высоких ветках. Вот определение сложности.

После этого мы можем действительно реально конечные последовательности — вот например мой вот пример: вот эта последовательность, в которой там были нули и единицы, которые были выписаны. И мы увидим: вот те, которые нам интуитивно кажутся простыми, оказываются действительно в этом смысле строго простые. А те, которые нам кажутся сложными, действительно этому интуитивному понятию сложности совершенно соответствуют.

Хотя, насколько я знаю, до меня в математике не было никакого другого определения, так что нельзя было сравнивать такие вещи. А вот теперь можно, вот я объяснил, как. Геометрия монад позволяет узнавать, какая последовательность сложная, а какая простая.

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

Утверждение. Я не называю его теоремой, а причина тут такая: я ее не сумел доказать. Я уверен, что она верна. Но я ее проверил в нескольких сотнях случаев. Какое же это доказательство? Но все-таки. Итак, утверждение: самая сложная функция — логарифм. Вот идут константы, потом многочлены малых степеней, потом многочлены более высоких степеней... Можно было бы строить тригонометрию, синусы, спецфункции, можно было бы строить весь анализ тут. Это всё можно сделать. Но логарифм оказывается сложнее всего. Причина мне совершенно непонятна, я этого не предвидел. Но просто посчитал, какая сложность логарифма, — оказалось, что он самый сложный. Вернее, не совсем так. Он либо самый сложный, либо _почти_ самый сложный.

Но прежде всего надо определить, что такое логарифм.

Итак. Мы хотим определить функцию... Аргумент у нас i — это номер члена последовательности. Но как определить логарифм i — ведь это не будет число бинарное? Чтобы это было число, остаток от деления на два надо. Как же это сделать? И вот что я придумал.

Мне нужны теории остатков и теории геометрических прогрессий. Я буду рассматривать остатки по модулю p, а p будет у меня для примера 13 — простое число. Вот. А геометрическую прогрессию я возьму такую: 2^a. a равняется 1, 2 и так далее. Ну, можно даже с нуля начинать, но я предпочитаю с единицы. Вот. Так вот у этих чисел — степеней двойки — надо брать остатки от деления на 13. Что это будет за последовательность? Смотрите.

При a равном единице какое число? 2. Так. Остаток от деления на 13? 2. Теперь при a равном двойке. 4. Остаток от деления на 13? 4. Восемь. Остаток от деления на 13? 8. Следующее? Три. Потому что дважды 8 это 16, а остаток от деления 16 на 13 — это 3. 3 на 2? 6. 6 на 2? 12. 12 на 2? 11, правильно. 12 это минус 1, поэтому 12 на 2 будет —2. А —2 по модулю 13 — это 11. 11 на 2? —4, то есть 9. 9 на 2 — 18, то есть 5. 5 на 2 — 10, 10 на 2 — 20, то есть 7, 7 на 2 — 14, то есть 1. 1 на 2 — 2

Так вот, заметьте: двойка получилась опять. Мы с нее начинали и к ней пришли.

Вывод: эта последовательность периодическая. И притом, какой у нее период, посчитайте. Смотрите: на какой раз получилась двойка? И так будет всегда, период будет p-1

Ферма доказал, что p минус один — всегда период. Ну, это, может, не наименьший период... В данном случае это наименьший период, но, во всяком случае, всегда есть такое число, для которого период будет p минус один.

А тогда мы напишем вот как. Если a в степени l равняется k (по модулю p) то мы l назовем логарифмом числа k. Это довольно обычно, если кто встречал где-нибудь логарифмы, в школе когда-нибудь... Так и определяется — по модулю a, ну, логарифмы с основанием a. Но. Это число — l — определено по модулю периода, по модулю p минус 1. Поэтому это число l само является остатком от деления на p минус 1. Вот. А k — остаток от деления на p. Стало быть, у каждого остатка от деления на p имеется логарифм. Вот он определен. Но этот логарифм сам является остатком от деления на p минус 1. Вот беда. А мы хотим, чтобы логарифм имел значения только 0 и 1. А тогда мы сделаем так. Мы это число по модулю p минус 1... Если p было нечетным — простое число, — то p минус 1 будет четным. Поэтому по модулю p минус 1 можно привести по модулю 2. И посмотреть, четное или нечетное число l. Если число l четное, то скажем, что логарифм, приведенный по модулю 2, равен нулю. А если нечетное, то единице. И это и есть определение логарифма. Арифметический логарифм определяется таким способом. Арифметический логарифм числа равен нулю, если это число является основанием в четной степени (для остатков), а единице — в противном случае.

Для последовательности длины не любой, а p минус 1 мы определили. Двоичные логарифмы определяются вот этим правилом. Между прочим, для знающих теорию чисел, надо сказать, еще это и так можно определить: если вычет k — квадратичный вычет, то 0, а если невычет, то 1, и поэтому этот логарифм был давно известен в теории чисел — называется символом Лежандра.

Так вот. Возьмем теперь этот логарифм и в каждом случае, для каждого нашего n, которое есть p-1, посчитаем его. Вот если взять n равное шести, которое 7—1, то логарифм можно посчитать, и логарифм (вот он написан здесь, вот этот логарифм) — когда мы его посчитаем здесь (надо посчитать значения: логарифм единицы, логарифм двойки, логарифм тройки) — будет последовательность, а эту последовательность можно записать как двоичное число. А это двоичное число можно посчитать, и оно равно в этом случае одиннадцать.

А теперь 11 занимает в нашей диаграмме какое-то место. А вот какое место. Наша диаграмма: цикл длины 6, на котором растет лес из деревьев T4. А 11 — это верхняя вершина на цикле T4. А длиннее циклов не бывает при этом значении n. Следовательно, 11 (вот эта точка) — самая сложная точка нашей монады. А это значит, логарифм в этом случае — это двоичный логарифм — самая сложная функция. Вот я вам провел доказательство... Но это в частном случае

Вот здесь, например, написаны другие значения, которые тоже... n равно четырем, p равно пяти. Тогда, оказывается, логарифм соответствует целому числу 6, двоичное разложение 6-ти дает. А дерево здесь вот какое. Видите: цикл длины один и дерево — это будет дерево, какое там, — T16. О1 значит T16.

Но 6 — оказывается, длиннее нету в этом случае — цикл самый длинный. Но логарифм — не самая высокая вершина. На единицу отстоит. И в других примерах у меня так же. Для всех примеров, в которых я считал, логарифм либо самая высокая вершина, он всегда принадлежит самому длинному циклу, и при этом вершина оказывается либо самой высокой, либо предшествующей. Почти самая высокая. Вот здесь, в этом случае, константа двойка, или 13 — они еще сложнее, чем логарифм, но чуть-чуть сложнее.

Я не знаю, что это за функции, надо посмотреть, может быть это какой-нибудь там x логарифм x или что-нибудь в этом роде... или единица делить на логарифм может даже оказаться... Но... не знаю. Вот дальше у меня показан там... еще один пример я показал — логарифм для p равного 11-ти, то есть n равного 10-ти... логарифм соответствует... функция логарифма соответствует числу 285, цикл имеет длину 30, и вот я некоторый кусок этого цикла выписал, из каких чисел он состоит, и видно... И в этом случае логарифм оказывается самой далекой вершиной, на самом длинном цикле, тоже как и в предыдущем случае. Вот я объяснил.

А теперь я уже кончаю доклад, но хочу еще показать несколько интересных вещей. Значит, оказывается, сложность этого логарифма связана с очень странным и загадочным явлением природы. Это явление встречается в разных науках под разными названиями — эргодическая теория, теория хаоса... И вот здесь тоже... Дело вот в чем. Рассмотрим вот, скажем, нашу геометрическую прогрессию, которую мы тут выписывали (а я уже стер ее, но она была), и посмотрим. Какие-то эти остатки как-то там распределены. Как они распределены?

Утверждение состоит в том, что вот этот логарифм или, наоборот, геометрическая прогрессия, обратная функция, — распределены их значения, вообще значения, хаотическим образом. Оказывается... нарисуем график для обычных картинок... ну там вот есть какая-нибудь функция... ну или там логарифм... вот он имеет какой-нибудь гладкий график вот... в обычном случае... А в нашей арифметической задаче оттого что мы берем остатки от всего этого, то оказывается, получается функция, у которой график ведет себя вот так. Безобразный график получается, хаотический. Он не непрерывный, конечно, это конечное число точек, это облако точек некоторое. Но если нарисовать этот график аккуратно, то есть одна точка здесь, одна здесь, получается случайный набор точек на плоскости.

В каком смысле он случайный? Это надо определять. Что такое случайность, что такое случайный набор... Все это можно сделать, проверить, посчитать... Я вот занимался когда-то с Яковом Борисовичем Зельдовичем случайностью распределения галактик и скопления галактик во Вселенной и применял потом здесь, в этой задаче, те же самые критерии, при помощи которых определяли, случайно галактики распределены или нет, можно и к этим точкам. Удовлетворяют всем критериям, по которым Зельдович считал, что галактики случайно в какой-то области распределены... Так и здесь: те же самые критерии можно применить, и получается, что это случайные точки.

Так вот теперь спрашивается: а где брать случайные точки вообще? В криптографии очень нужны случайные точки — для того чтобы код делать случайный... И как их получать? И вот я сейчас хочу рассказать... эта теория, про которую я здесь рассказываю, в частности дает некоторые очень странные алгоритмы построения случайных последовательностей.

Я придумал такие алгоритмы для разных других задач, но все-таки использовал такие два алгоритма. Один алгоритм я взял такой: я взял список академиков Национальной академии наук США и других академий, в которых я состою, значит тоже брал. И брал списки телефонных номеров по алфавитному списку академиков, и брал средние цифры телефонного номера, чтобы не учитывать, что там какой-нибудь там... нули в конце или там какой-нибудь 192 в начале, чтобы не попадали одинаковые, чтобы, несмотря на то, где они там, в Гарварде или в Принстоне, чтобы этот Гарвард не влиял. Получается последовательность, которая, как и галактики, как и эти вычеты, удовлетворяет всем распределениям случайности.

А я сделал еще... второй опыт я сделал такой. Я взял и мимо нашего Математического института имени Стеклова проходящие номера машин списал. Значит, взял несколько сотен машин, списал номера, а потом взял и обработал теми же методами. Опять получается.

Я пробовал некоторые другие вещи — они НЕ получаются. Я знаю, какие последовательности случайные, какие нет. Не все случайные. Но вот одна случайная мне очень нравится, и про нее я хочу сказать вам несколько слов. Она сейчас там уже вот видна. Это даже не последовательность, а это случайные перестановки. Мне нужно было для некоторых целей знать, как выглядит случайная перестановка n элементов.

Так вот, таблицы случайных перестановок доставляет теория полей Галуа. Это как раз перестановки, которые происходят от геометрических прогрессий в полях Галуа, которые ровно такие же, как и здесь. То, что я рассказывал — когда берутся остатки от деления на p — то это как раз поле Галуа и есть. Но поля Галуа всегда имеют число элементов p в какой-нибудь степени. Бывает из p элементов, где p — простое число, p^2, p^3 и так далее. Вот если брать из p^2 элементов, то получится перестановка p^2 чисел, и она записывается заполнением таблицы размером p x p... Вот у меня нарисовано слева, там, где p равно пяти, 25 клеточек, и в них вписаны числа от единицы до 25. Но на самом деле, до 24-х, и еще бесконечность там есть по некоторым причинам (не хочу рассказывать, это связано с теорией полей Галуа, которую обычно как-то скрывают - даже в учебниках по полям Галуа вы этого не найдете.)

Но если посчитать, это сделать — что, конечно, тоже можно выполнить — то получается заполнение такой шахматной доски номерами. Но можно было бы занумеровать, как на шахматной доске, цифрами и буквами или цифрами подряд, а здесь заполнение получается совершенно нерегулярное. Смотрите, у меня там отмечены места, где стоят образующие поле Галуа. Но это не важно, не важно, что там красным, надо смотреть на все заполнения. Вот там...

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

Значит, вот эта наука, о которой я рассказывал, она дает вот такие самые разнообразные странные приложения, отчасти экспериментальные, отчасти доказанные.

В заключение я сделал еще одну картинку специально для сегодняшнего доклада. Я не останавливался на рассказанной вам теории бинарных последовательностей, а решил проделать то же самое с тернарными, специально для сегодняшнего доклада. Тернарные — это значит, что остатки не от деления на 2, 0 и 1, как в компьютере, а на 3. Можно любое число брать было бы, но я поленился брать для любого. А для 3-х просчитал.

И вот что у меня получилось — там нарисовано, какие монады получаются, если брать остатки от деления на 3. Значит, вместо бинарных деревьев получаются тернарные. Многочлены образуют тернарное дерево, которое есть всегда. И там теоремы делимости, которые были, тоже имеют аналоги свои... Но я не всё рассказываю, что там просчитал. Здесь забавные такие разбиения этих монад... Вместо куба там будет более сложный такой многогранник, у которого число вершин не 2n, а 3n, где n — это длина последовательности.

И вот я очень удивился, когда заканчивал уже вычисления и вычислял для n равного семи. Последовательности длины 7, тернарные последовательности длины 7 какую имеют монаду? И вот это последнее, что я вам хочу показать. Это удивительный результат. А именно: обнаружилась совершенно удивительная связь этой теории, при n равном семи и при тернарных последовательностях, с астрономией. А эту связь вы сейчас увидите. Значит, 3 в степени 7 — это число точек монады, число вершин, мы сейчас будем граф рисовать с таким числом вершин.

Что такое 3 в степени 7? Не много, не много. Когда я учился в школе, то нас заставляли это решать в уме и говорить сразу, а кто не говорил, тому двойку. Да. 3 в степени 7 — это 3 умножить на 3 в степени 6. А 3 в степени 6 — это 27 в квадрате, или 9 в кубе. Между прочим, 9 в кубе легче всего посчитать. Потому что 9 в квадрате — 81, умножить на 9 — 729.

Мало кто замечает, что эта формула имеет огромное астрономическое значение, а я заметил и сейчас вам расскажу.

Смотрите: самая простая последовательность длины 7 — это 7 нулей. Ну я ее обозначаю «ноль». Ноль, конечно, переходит в себя. Последовательность разностей из нуля будет ноль. А кто в него еще переходит, какое дерево навешано на этот цикл длины 1? У какой еще функции, кроме нуля, разности 0? Это константа. А какие бывают константы? Нет.... Это же тернарные последовательности. Только две константы — единица и двойка. Ну, 0, конечно, тоже. Они переходят в 0, в 0 переходят три точки. Ноль, единица и двойка. Поэтому тернарное дерево. Спрашивается: а в единицу кто переходит? Многочлены там первой степени...

Но смотрите, в чём дело. Надо по разностям найти функцию, у которой такие разности. Единица. Эта операция называется интегрирование. Но интегрировать константу очень опасно. Потому что получится суммирование (обратная операция к разности). Получится, что интеграл по всему циклу будет 7. Но это тернарные, по модулю 3. Значит, если 7, если была единичка, будет 7, а 7 это 1, по модулю 3. Один. А это значит, что последовательность периодической быть не могла. Потому что через периода она прирастает на единицу. Линейная функция не бывает периодической. А это значит, что никакого другого элемента, кроме единицы и двойки чистой, в ноль не переходит. Дерево только вот такое. А из этого следует, что у всех циклов дерево только вот такое. Это легко уже доказать. Поэтому каждая компонента имеет число элементов, которое делится на 3. Поэтому сумма всех длин всех циклов — 729.

Все компоненты имеют вид: дерево T3, навешанное на цикл ОN. И сумма этих N — 729. Но одна из компонент — вот она — это компонента нуля. Это цикл длины единица. Поэтому, если брать сумму по n, которые не равны единице, — остальные компоненты — то будет 728. А спрашивается: как разбить на слагаемые? Какие же там циклы? Ну я посчитал вручную, надо сказать, может быть, и можно это догадаться как-нибудь, но я до сих пор не умею хорошо догадываться. Я только, когда такая трудная задача, надо 300 чисел рассмотреть, я их просто все выписываю. Я выписал и получил: компонент две. Оказывается, компонент две и они одинаковые. Имеется два одинаковых цикла, сумма длин которых 728. Трудный вопрос: какая длина каждого цикла? Какая длина каждого цикла? 728 надо разделить пополам. Значит, длина каждого цикла будет 728 пополам — равняется 364.

А теперь мы обращаемся к астрономии. Мы получили длину года без високосного дня. А теперь мы обращаемся к моей теореме. Длина цикла делится на длину последовательности. А длина последовательности была 7. Значит, получаем вывод: 364 делится на 7