mathtabletalks (archive)

15 August 2019

М

11:33

Математические байки

Начнём, пожалуй :)

Victor Kleptsyn

М

11:33

Математические байки

Вчера из доклада Бунимовича узнал о забавной игре.
Пусть много раз подкидывается честная монетка, а игроки выбирают (разные) слова из "О" и "Р" (орёл и решка). Чьё слово выпало первым, тот выиграл.

Victor Kleptsyn

М

11:34

Математические байки

Понятно, что если первый игрок сказал "О", а второй "Р", то монетку потребуется подкинуть только один раз, и шансы на выигрыш у игроков одинаковые.

Victor Kleptsyn

М

11:34

Математические байки

А что, если слова более длинные?

Victor Kleptsyn

М

11:36

Математические байки

Оказывается, что игра получается нетранзитивной, и какого-либо "самого лучшего слова" нет. А именно — пусть слова должны быть одинаковой длины n, не меньшей трёх, и сначала первый игрок говорит своё слово, а потом второй выбирает своё.

Victor Kleptsyn

М

11:37

Математические байки

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

Victor Kleptsyn

М

11:37

Математические байки

Пример: пусть первый игрок называет ООО.

Victor Kleptsyn

М

11:38

Математические байки

Ответ второго — РОО, и его вероятность выигрыша — 7/8(!).

Victor Kleptsyn

М

11:38

Математические байки

Действительно, первый тогда может выиграть _только_ если на первых трёх подбрасываниях выпадут три орла.

Victor Kleptsyn

М

11:39

Математические байки

Если этого не произошло — то выпала хотя бы одна решка, и дальше второй всегда выиграет за шаг до того, как у первого будет хотя бы шанс выкинуть третьего орла

Victor Kleptsyn

М

11:39

Математические байки

(В первый раз, когда выпадут два орла подряд, перед ними должна быть решка — иначе это не первый раз — и вот второй и выиграл)

Victor Kleptsyn

М

11:40

Математические байки

Так вот — игра как "камень-ножницы-бумага", на любое слово первого у второго есть выгодный ответ.

Victor Kleptsyn

М

11:42

Математические байки

Называется она "Penney's game" (https://en.wikipedia.org/wiki/Penney%27s_game ), а формулу для отношения вероятностей выигрыша игроков придумал Конвей.

Victor Kleptsyn

М

12:56

Математические байки

Формула, кстати, очень интересная.

Victor Kleptsyn

М

12:57

Математические байки

Сначала для пары слов A, B (пусть пока одинаковой длины) сделаем следующее: напишем B под A, будем сдвигать его на 1 вправо на каждом шаге, и будем писать 1, если на пересечении они совпадают, а 0, если нет.

Victor Kleptsyn

М

12:57

Математические байки

Например: A=РООР, B=ОРОР.
РООР
ОРОР
не совпадают — пишем 0.

Victor Kleptsyn

М

12:57

Математические байки

РООР
-ОРОР
на пересечении не совпадают — пишем 0.

Victor Kleptsyn

М

12:58

Математические байки

РООР
--ОРОР
А вот теперь совпадают, ОР=ОР, пишем 1

Victor Kleptsyn

М

12:58

Математические байки

РООР
---ОРОР
опять не совпадают, пишем 0

Victor Kleptsyn

М

12:58

Математические байки

Получается 0010. А теперь интерпретируем это как двоичную запись числа — и полученное число обозначим как (A,B). То есть мы только что посчитали, что
(РООР, ОРОР) = 2.

Victor Kleptsyn

М

12:59

Математические байки

Формула Конвея:

Victor Kleptsyn

М

12:59

Математические байки

шансы на победу у слов B и A относятся, как
(A,A)-(A,B) к (B,B)-(B,A).

Victor Kleptsyn

М

13:00

Математические байки

Например, для A=ООО, B=РОО, легко посчитать, что
(A,A)={111}_2 = 7,

Victor Kleptsyn

М

13:00

Математические байки

(A,B)={000}_2= 0,

Victor Kleptsyn

М

13:00

Математические байки

(B,A)={011}_2= 3,

Victor Kleptsyn

М

13:00

Математические байки

(B,B)={100}_2 = 4.

Victor Kleptsyn

М

13:01

Математические байки

Получаем
(7-0):(4-3) = 7:1,
как мы уже видели в самом начале.

Victor Kleptsyn

М

13:01

Математические байки

Victor Kleptsyn

М

13:11

Математические байки

Иллюстрация из статьи Мартина Гарднера "On the paradoxical situations that arise from nontransitive relations" в колонке "Mathematical Games", Scientific American, октябрь 1974

Victor Kleptsyn

М

13:11

Математические байки

(а H и T тут — от английских Head и Tail)

Victor Kleptsyn

М

15:05

Математические байки

Картинка из той же статьи — как играть для слов длины 3 (красным выделены оптимальные ответы):

Victor Kleptsyn

М

15:05

Математические байки

Victor Kleptsyn

М

17:16

Математические байки

Ну и прекрасная цитата из той же статьи Гарднера —

Victor Kleptsyn

М

17:16

Математические байки

Photo

283x65

Victor Kleptsyn

М

18:37

Математические байки

Да — возвращаясь к началу, Бунимович занимается динамическими системами и бильярдами. Скажем, одна из известных систем — "стадион Бунимовича":
https://blogs.ams.org/visualinsight/2016/11/15/bunimovich-stadium/

Victor Kleptsyn

М

18:37

Математические байки

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

Victor Kleptsyn

М

18:37

Математические байки

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

Victor Kleptsyn

М

18:43

Математические байки

Так вот — почему же Бунимович эту игру вспомнил? Дело в том, что для динамических систем один из стандартных инструментов это кодирование точки — сопоставление ей последовательности символов.

Victor Kleptsyn

М

18:44

Математические байки

Один из самых основных примеров — это отображение F:x->{2x} отрезка [0,1] в себя.

Victor Kleptsyn

М

18:50

Математические байки

Оно хаотично: если взять две точки очень близко друг к другу, и начать применять F — то на каждой итерации расстояния между точками будут удваиваться. (Тут удобнее вместо отрезка рассмотреть окружность, склеив 0 и 1 — тогда отображение становится непрерывным, и удваивающим угол; кстати, если нарисовать эту окружность на комплексной плоскости — взять z=exp(2 \pi i x), — то получающееся отображение это просто z->z^2. Но туда мы не пойдём...)

Victor Kleptsyn

М

18:52

Математические байки

Так вот — давайте разобьём отрезок на две части, I_0=[0,1/2) и I_1=[1/2,1). И сопоставим точке x последовательность нулей и единиц: на n-м месте поставим то, в какой интервал попадает F^n(x).

Victor Kleptsyn

М

18:52

Математические байки

Если в I_0, то 0, если в I_1, то 1.

Victor Kleptsyn

М

19:09

Математические байки

Совершенно общее утверждение при таком подходе: одно применение F приводит к сдвигу кодирующей последовательности на один символ влево.

Victor Kleptsyn

М

19:10

Математические байки

А в нашем случае всё ещё лучше:
- кодирование точки x это её двоичная запись
- если выбрать точку x равномерно на [0,1], то символы из кодирующей последовательности получаются как подбрасывания независимых честных монеток

Victor Kleptsyn

М

19:14

Математические байки

А, например, выпадение 0,1,0 на n,n+1,n+2-ых подбрасываниях превращается в "F^n(x) между точками с двоичными записями {0,010}_2 и {0,011}_2 — то есть на полуинтервале [1/4, 3/8)".

Victor Kleptsyn

М

19:16

Математические байки

Соответственно, игра Penney превращается в размещение "лунок": сначала один, потом второй игрок размещают лунки-отрезки длиной по 1/2^k; начальная точка выбирается равномерно случайно, и итерируется отображением F. В чью лунку она попадёт первой, тот победил.

Victor Kleptsyn

М

19:18

Математические байки

Бунимович, правда, использовал немного другое отображение, "tent map" — F(x)=|2x-1|.

Victor Kleptsyn

М

19:18

Математические байки

Victor Kleptsyn

М

19:19

Математические байки

Но кодирование к этому отображению можно применить совершенно так же, просто дословно с теми же I_0 и I_1.

Victor Kleptsyn

М

19:21

Математические байки

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

Victor Kleptsyn

М

19:22

Математические байки

Но на этом месте я, пожалуй, прекращу дозволенные речи. :)

Victor Kleptsyn

16 August 2019

М

12:13

Математические байки

В Bedlewo сегодня завершается конференция "2020 Vision for the dynamics" (https://www.impan.pl/en/activities/banach-center/conferences/19-vision2020 ), посвящённая памяти А. Б. Катка (https://ru.wikipedia.org/wiki/Каток,_Анатолий_Борисович ). И мне хотелось поделиться ещё парой фотографий с докладов:

Victor Kleptsyn

М

12:13

Математические байки

С доклада Е. А. Робинсона-младшего (https://blogs.gwu.edu/robinson/ ) :

Victor Kleptsyn

М

12:13

Математические байки

Victor Kleptsyn

М

12:13

Математические байки

Victor Kleptsyn

М

12:16

Математические байки

Как раз та самая подстановка Фибоначчи, о которой в Дубне рассказывал А. П. Веселов: ( https://vk.com/videos-65937233?z=video-65937233_456239054%2Fclub65937233%2Fpl_-65937233_-2 / https://mccme.ru/dubna/2019/courses/veselov.html )

Victor Kleptsyn

М

12:17

Математические байки

Victor Kleptsyn

М

12:20

Математические байки

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

Victor Kleptsyn

М

12:23

Математические байки

А вот эта — из лекции Марка Полликотта (https://warwick.ac.uk/fac/sci/maths/people/staff/mark_pollicott/p1/ ) —

Victor Kleptsyn

М

12:23

Математические байки

Victor Kleptsyn

М

12:24

Математические байки

На фотографии можно узнать аффинное динамически определённое канторово множество. И, конечно, простейший пример — стандартное КМ:

Victor Kleptsyn

М

12:24

Математические байки

Victor Kleptsyn

М

12:34

Математические байки

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

Victor Kleptsyn

М

12:36

Математические байки

Конечно, сразу возникает вопрос, что такое "размерность" — и если отвечать строго, то нужно сказать, что это _хаусдорфова размерность_:
если есть покрытие множества X (бесконечным) объединением шаров радиусов r_j, то его d-мерным объёмом называется сумма ряда из (r_j)^d.
Хаусдорфова размерность множества — инфимум таких d, для которых существуют покрытия со сколь угодно малым d-мерным объёмом.

Victor Kleptsyn

М

12:37

Математические байки

(Пара слов об этом написана в конце дубнинской брошюры Ильяшенко — https://www.mccme.ru/dubna/books/pdf/ilyashenko-attr.pdf )

Victor Kleptsyn

М

12:41

Математические байки

Но можно пока о строгом определении не задумываться и подменить вопрос: зафиксировать большое n и посмотреть на те точки, у которых среди первых n цифр доля единиц уже (примерно) p. Например, у которых единиц ровно m=[pn].
Это будет объединение скольки-то отрезков длины 2^(-n) — если мы совсем зафиксировали число единиц, то их количество это биномиальный коэффициент C_n^m.

Victor Kleptsyn

М

12:44

Математические байки

Соответственно, если мы думаем в терминах размерности — то правильно посмотреть, как какая степень от размера растёт количество этих отрезков. (Отрезок покрывается сотней отрезков длины 1/100, квадрат — 100^2 квадратов со стороной 1/100, d-мерный куб — 100^d кубиками со стороной 1/100.)

Victor Kleptsyn

М

12:45

Математические байки

То есть нужно посмотреть на отношение
log_2 (C_n^m) / n

Victor Kleptsyn

М

12:47

Математические байки

Формула Стирлинга (потрясающе полезная, которую надо помнить обязательно) говорит, что
n! ~ \sqrt{2 \pi n} (n/e)^n.

Victor Kleptsyn

М

13:05

Математические байки

Нам тут понадобится только последний сомножитель, экспоненциальный (всё остальное слишком медленное относительно логарифма). Ну и в выражении
C_n^m = n!/(m! (n-m)!)
степени e в числителе и знаменателе сокращаются, и остаётся от экспоненциальной части только
(n/m)^m (n/(n-m))^(n-m).

Victor Kleptsyn

М

13:06

Математические байки

Если прологарифмировать, поделить на n и сказать, что m~np, то получается примерно
(1/n) log_2 C_n^m ~ -p log_2 p - (1-p) log_2 (1-p).

Victor Kleptsyn

М

13:07

Математические байки

С одной стороны, вот она размерность. Мы её и правда нашли (хотя, конечно, всё вышесказанное нужно делать честно, а не как я сейчас).

Victor Kleptsyn

М

13:13

Математические байки

И этим занимался Безикович — тот самый, который решил задачу Какейя о развороте отрезка: что есть (невыпуклая) фигура сколь угодно малой площади, внутри которой можно развернуть отрезок.

Victor Kleptsyn

М

13:13

Математические байки

Victor Kleptsyn

М

13:16

Математические байки

(У Марка на слайде в знаменателе логарифм 3, а не логарифм 2 — потому что он вместо отрезка работает с канторовым множеством: его точки тоже можно закодировать 0 и 1, или 0 и 2 — просто взяв троичную запись.)

Victor Kleptsyn

М

13:19

Математические байки

In reply to this message

(Да, в качестве отступления в сторону — об этой задаче и конструкции можно прочитать в Кванте —
http://kvant.mccme.ru/1973/04/o_vrashchenii_otrezka.htm )

Victor Kleptsyn

М

13:20

Математические байки

In reply to this message

Так вот — с другой стороны, тут появляется выражение (-p log p), которое кому-то может быть знакомо из физики, а кому-то из информатики.

Victor Kleptsyn

М

13:34

Математические байки

И мне в этом месте хочется сказать слова "энтропия Шеннона".
Представим себе, что на Марсе у нас стоит марсоход, и каждую секунду что-то измеряет. Например, ловит космические лучи — таким образом, разные измерения независимы друг от друга. Но шанс, что что-то прилетит, очень маленький, поэтому таблица из 0 и 1 (не прилетело/прилетело) состоит в основном из нулей, вероятность p единицы очень маленькая.
Как нам передать результаты наблюдений на Землю?

Victor Kleptsyn

М

13:35

Математические байки

Можно, конечно, так и передать, нулями и единицами, но странно забивать канал нулями.

Victor Kleptsyn

М

13:37

Математические байки

Так вот — при большом числе наблюдений нам понадобится примерно (-p log p - (1-p) log (1-p)) бит в расчёте на одно измерение, чтобы (честно) передать результаты.

Victor Kleptsyn

М

13:39

Математические байки

Проще всего это сделать так — если мы провели n измерений, то сначала передаём m — число единиц. На это нам нужно log_2(n) бит, что по сравнению с n — копейки.

Victor Kleptsyn

М

13:43

Математические байки

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

Victor Kleptsyn

М

13:43

Математические байки

Остаётся передать номер — что мы и сделаем.

Victor Kleptsyn

18 August 2019

М

12:46

Математические байки

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

Victor Kleptsyn

М

12:46

Математические байки

То есть
n!/((m_1)!*...*(m_k)!)

Victor Kleptsyn

М

12:48

Математические байки

Опять применив формулу Стирлинга и посмотрев на экспоненциальную часть, мы получим произведение (n/m_i)^(m_i), и его логарифм будет равен
n * (-\sum p_i log p_i).

Victor Kleptsyn

М

12:48

Математические байки

Вот мы и получили знаменитую формулу для энтропии — число бит для передачи результата в расчёте на один эксперимент (или, по-другому, какая пропускная способность канала нам нужна):
H = - \sum_i p_i \log p_i.

Victor Kleptsyn

М

12:49

Математические байки

Для аккуратности — если говорить о битах, то логарифм нужно брать двоичным, а в динамических системах и в физике его обычно берут натуральным.

Victor Kleptsyn

М

12:50

Математические байки

In reply to this message

Ещё на эту формулу можно посмотреть так: это математическое ожидание ( = результат усреднения) логарифма вероятности того исхода, которое у нас в результате одного эксперимента получается.

Victor Kleptsyn

М

12:54

Математические байки

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

Victor Kleptsyn

М

12:55

Математические байки

В какой-то из популярных книжек (ещё времён, когда телефоны были проводными) мне попадалось сравнение
"Если Вы снимете трубку звонящего телефона и услышите "Алло!", Вы не удивитесь. Гораздо больше Вы удивитесь, если Вас вместо этого ударит током."

Victor Kleptsyn

М

14:31

Математические байки

In reply to this message

==
Ну и возвращаясь к докладу Марка Полликотта (а то я про Безиковича и долю единиц рассказал, а про центральный сюжет ещё нет).

Victor Kleptsyn

М

14:31

Математические байки

Там тоже обсуждалась хаусдорфова размерность, но не точек с данной долей 0 и 1, а точек с данной скоростью растяжения для того отображения T, которое канторово множество порождает.

Victor Kleptsyn

М

14:32

Математические байки

По-хорошему, про скорость растяжения произносятся слова "показатель Ляпунова" (которые для современной теории динамических систем одни из основных).

Victor Kleptsyn

М

14:32

Математические байки

А именно — это предел
lim_n (1/n) ln (T^n)'(x):

Victor Kleptsyn

М

14:33

Математические байки

Victor Kleptsyn

М

14:34

Математические байки

Чуть более подробно — вот пусть у нас есть динамическая система, то есть отображение T, которое мы итерируем (можно сказать, что оно сопоставляет текущему состоянию системы её состояние через одну секунду).

Victor Kleptsyn

М

14:35

Математические байки

И пусть задана начальное состояние системы — некоторая точка x.

Victor Kleptsyn

М

14:35

Математические байки

Тогда можно посмотреть, с какой скоростью итерации "соседних" с ней точек с её итерациями сближаются/разбегаются.

Victor Kleptsyn

М

14:37

Математические байки

В размерности один — а мы будем считать, что мы работаем на отрезке, — это просто значит, что мы берём производную n-й итерации T^n в точке x:

Victor Kleptsyn

М

14:37

Математические байки

(T^n)'(x) = T'(T^{n-1}(x)) * ... * T'(T(x)) * T'(x).

Victor Kleptsyn

М

14:37

Математические байки

Теперь, чтобы сказать, "какое изменение приходится [в среднем] на одну итерацию", можно было бы извлечь корень n-й степени.

Victor Kleptsyn

М

14:38

Математические байки

Но с корнями и произведениями очень неудобно работать. Поэтому от такого "среднего геометрического производных по орбите" берут логарифм — рассматривают
(1/n) log (T^n)'(x) = (1/n) \sum_{j=0}^{n-1} (log T')(T^j(x)).

Victor Kleptsyn

М

14:39

Математические байки

(Да, "орбита" — это как раз последовательность итераций начальной точки: x, T(x), T^2(x), ...)

Victor Kleptsyn

М

14:40

Математические байки

In reply to this message

И переходят к пределу при n, стремящемся к бесконечности. Вот этот предел (который появляется на слайде выше) и называется показателем Ляпунова (отображения T в точке x).

Victor Kleptsyn

М

14:40

Математические байки

В том случае, когда отображение T — кусочно-аффинное, порождающее канторово множество, производная у него на каждом отрезке области определения постоянна. Так что получается действительно почти "доля единиц" в кодировании точки, только чуть-чуть подкрученная.

Victor Kleptsyn

М

14:42

Математические байки

Скажем, для самого стандартного канторова множества показатель Ляпунова будет просто log 3 в любой точке x, потому что производная T равна 3 везде. А вот если у нас два отрезка, [0,1/a] и [1-1/b,1], то у нас будет
(log a)*(доля итераций, попадающих в первый отрезок) + (log b)*(доля итераций, попадающих во второй).

Victor Kleptsyn

М

14:42

Математические байки

Victor Kleptsyn

М

14:43

Математические байки

(Я не хочу лезть в более конкретные детали или писать формулы; в конце концов, это должна быть сложная, но всё-таки байка!)

Victor Kleptsyn

М

14:44

Математические байки

Так вот, из общей логики "есть естественный объект, давайте его исследовать" — можно смотреть на то, как устроено множество точек с заданным показателем Ляпунова. В частности, можно спросить, какая у него размерность. И как устроена функция "размерность в зависимости от показателя Ляпунова".

Victor Kleptsyn

М

14:47

Математические байки

Эту функцию исследовал Howie Weiss. Он доказал (в определённых условиях, которые я не формулирую!) её аналитичность — и сказал, что она должна быть выпуклой.

Victor Kleptsyn

М

14:48

Математические байки

Victor Kleptsyn

М

14:48

Математические байки

Только вот выпуклость оказалась неправдой: J. Kiwi и G. Iommi нашли контрпример.

Victor Kleptsyn

М

14:48

Математические байки

In reply to this message

Оказалось, что достаточно взять кусочно-аффинное растягивающее отображение из двух интервалов.

Victor Kleptsyn

М

14:49

Математические байки

Victor Kleptsyn

М

14:52

Математические байки

И если длины кусочков сильно разные (если отношение их логарифмов большое) — то функция уже не выпуклая:

Victor Kleptsyn

М

14:52

Математические байки

Victor Kleptsyn

М

14:54

Математические байки

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

Victor Kleptsyn

М

14:55

Математические байки

Ответ: свежая теорема Оливера Дженкинсона, Марка Полликотта и Полины Вытновой, которой Марк завершил доклад, говорит, что точек перегиба действительно может быть сколь угодно много.

Victor Kleptsyn

М

14:55

Математические байки

Victor Kleptsyn

М

15:11

Математические байки

Только аффинно-растягивающихся кусочков нужно брать уже не два, а сильно больше.

Victor Kleptsyn

М

15:11

Математические байки

Да, а название для таких отображений — cookie cutters, "формочки для печенья" — придумал замечательный математик Дэннис Салливан ( https://ru.wikipedia.org/wiki/Салливан,_Деннис )

Victor Kleptsyn

М

15:11

Математические байки

Victor Kleptsyn

М

15:12

Математические байки

Ну и на этом месте, кажется, эту байку правильно завершить.

Victor Kleptsyn

М

17:56

Математические байки

===
Поскольку рассказ выше получился явно сложным — в дополнение к нему, байка о формуле Стирлинга (раз уж я её упомянул) и формуле суммирования Эйлера-Маклорена. Точнее, начало байки (ибо там рассказывать можно много).

Victor Kleptsyn

М

17:56

Математические байки

Вот у нас есть n!. Это произведение 1*2*...*n.

Victor Kleptsyn

М

17:57

Математические байки

Формула Стирлинга его оценивает — причём делает это асимптотически точно, отношение n! к \sqrt{2\pi n}*(n/e)^n стремится к 1 с ростом n.

Victor Kleptsyn

М

17:57

Математические байки

Как такую оценку можно получить?

Victor Kleptsyn

М

17:58

Математические байки

Есть очень хороший рефлекс: "видишь длинное произведение — прологарифмируй!".

Victor Kleptsyn

М

17:58

Математические байки

Потому что логарифм превращает произведение в сумму, а с суммой работать значительно проще.

Victor Kleptsyn

М

17:58

Математические байки

Применив его — мы видим, что мы хотим понять, как себя ведёт
ln n! = ln 1 + ln 2 + ... + ln n.

Victor Kleptsyn

М

17:59

Математические байки

И уже сразу видно, что она напоминает интегральную сумму Римана для интеграла от логарифма:

Victor Kleptsyn

М

18:01

Математические байки

Victor Kleptsyn

М

18:03

Математические байки

А какая у логарифма первообразная? Поскольку логарифм меняется чем дальше, тем медленнее, естественно взять x*(ln x) в качестве первого приближения; но
[x*(ln x)]'= ln x + x*[(ln x)'] = ln x +1,
так что нужно первообразную лишней единицы вычесть — получается (x*ln x -x)

Victor Kleptsyn

М

18:04

Математические байки

(Конечно, это называется "взять интеграл по частям", но тут эта выкладка ещё и естественно мотивируется.)

Victor Kleptsyn

М

18:10

Математические байки

А (n*ln n -n) — это и есть логарифм от "экспоненциальной части" (n/e)^n.
То есть первую часть формулы Стирлинга мы уже поймали!

Victor Kleptsyn

М

18:12

Математические байки

In reply to this message

На самом деле — удобнее откладывать прямоугольники в другую сторону, чтобы интеграл был действительно до x=n, то есть чтобы ln k был площадью прямоугольника высоты ln k на основании [k-1,k], тогда картинка получится чуть-чуть другая:

Victor Kleptsyn

М

18:12

Математические байки

Victor Kleptsyn

М

18:13

Математические байки

Закрашенная область — то, что мы хотим получить. А площадь под (красным) графиком логарифма — то, что уже посчитали.

Victor Kleptsyn

М

18:13

Математические байки

А насколько мы промахнулись?

Victor Kleptsyn

М

18:17

Математические байки

Понятно, насколько — на сумму площадей криволинейных треугольников:

Victor Kleptsyn

М

18:17

Математические байки

Victor Kleptsyn

М

18:17

Математические байки

А чему она примерно равна?

Victor Kleptsyn

М

18:18

Математические байки

Естественно, сумме площадей таких же, но прямолинейных треугольников.

Victor Kleptsyn

М

18:19

Математические байки

У всех этих прямолинейных треугольников горизонтальные катеты равны 1. Поэтому сумма их площадей это половина суммы вертикальных катетов.

Victor Kleptsyn

М

18:20

Математические байки

А поскольку каждый катет это приращение логарифма — то сумма вертикальных катетов получается телескопическая, и даёт просто ln n.

Victor Kleptsyn

М

18:21

Математические байки

Ну и (ln n)/2 — это не что иное, как логарифм корня из n. Того самого корня из n, который стоит в формуле Стирлинга.

Victor Kleptsyn

М

18:22

Математические байки

(Да, на всякий случай — то, что мы сейчас проделали, для численных приближений интеграла называлось бы переходом от формулы прямоугольников к формуле трапеций.)

Victor Kleptsyn

М

18:23

Математические байки

Так вот — мы сейчас вытащили почти всю формулу Стирлинга, кроме константы \sqrt{2\pi}.

Victor Kleptsyn

М

18:25

Математические байки

На самом деле — мы уже можем доказать, что эта константа _есть_.

Victor Kleptsyn

М

18:27

Математические байки

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

Victor Kleptsyn

М

18:30

Математические байки

Если площадь криволинейного треугольника убывала как (1/n) — ибо за него отвечает первая производная логарифма — то площадь сегмента уже будет убывать как (1/n^2), ибо ему соответствует вторая производная, а (ln x)'' = -1/x^2.

Victor Kleptsyn

М

18:32

Математические байки

А ряд из обратных квадратов уже сходится. И значит, последовательность "ошибок"
(ln n!) - ( n ln n - n + ln \sqrt{n})
будет фундаментальной — её приращения и есть площади сегментов.

Victor Kleptsyn

М

18:34

Математические байки

А раз так, то она сходится — и её предел это и есть логарифм той константы, на которую нам остаётся домножить.

Victor Kleptsyn

М

18:35

Математические байки

То есть для какого-то A будет выполнено
ln n! ~ A sqrt{n} (n/e)^n,
только мы пока что не знаем, что A= \sqrt{2\pi}.

Victor Kleptsyn

М

18:46

Математические байки

На самом деле, техника, которую мы сейчас применили, это частный случай формулы суммирования Эйлера-Маклорена. А именно — если у нас есть какая-то "хорошая" функция f, и мы хотим понять, как себя будет вести сумма
f(1)+f(2)+...+f(n)
с ростом n.

Victor Kleptsyn

М

18:49

Математические байки

Если провести всё те же рассуждения (и зайти чуть дальше) — то в качестве первого приближения возникнет первообразная F(n), потом к ней добавится (1/2)*f(n), потом с каким-то коэффициентом добавится производная f', и так далее.

Victor Kleptsyn

М

18:55

Математические байки

Причём коэффициенты не зависят от того, у какой именно функции f мы складываем значения, мы всегда получим выражение вида
F(n)+ (1/2) f(n) + (1/12) f'(n) + ... .

Victor Kleptsyn

М

18:57

Математические байки

Если очередная производная f начинает убывать достаточно быстро, чтобы ряд из поправок начал сходиться — можно сказать, что сумма будет устроена как приближение плюс неизвестная нам константа.

Victor Kleptsyn

М

19:01

Математические байки

Но асимптотику можно писать и дальше — собственно, ровно так получается приближение для суммы гармонического ряда,
1+(1/2)+...+(1/n) = ln n + \gamma + (1/2)* (1/n) + o(1/n),
где \gamma — постоянная Эйлера.

Victor Kleptsyn

М

19:05

Математические байки

И ровно поэтому в формуле Стирлинга, если n! нужно приблизить ещё точнее, нужно домножить правую часть на exp(1/12n) — или на (1+ 1/12n), с точностью до O(1/n^2) это одно и то же. Потому что вот он коэффициент (1/12) для производной, и вот она производная логарифма, (ln x)'=1/x.

Victor Kleptsyn

М

19:06

Математические байки

А ещё очень естественное действие — применить всё это к самым простым функциям, которые бывают, к степеням.

Victor Kleptsyn

М

19:10

Математические байки

И получится сумма степеней — которую для небольших степеней все видели; скажем, для суммы первых степеней —
1+2+...+n=n(n+1)/2 = n^2/2 + n/2 = F(n) + (1/2) f(n).

Victor Kleptsyn

М

19:15

Математические байки

Для суммы квадратов — есть формула n(n+1)(2n+1)/6, а если раскрыть скобки, получится
n^3/3 + n^2/2 + n/6 = F(n) + (1/2)f(n) + (1/12)f'(n)

Victor Kleptsyn

М

19:24

Математические байки

Вообще про суммы степеней есть очень хороший текст Г. Мерзона в "Мат. просвещении" — http://mi.mathnet.ru/mp882 —
а мне хочется сказать ещё пару слов про сумму _обратных_ степеней.

Victor Kleptsyn

М

19:28

Математические байки

Была знаменитая базельская проблема — найти, чему равна сумма ряда из обратных квадратов,
1+1/4+1/9+...

Victor Kleptsyn

М

19:28

Математические байки

Её решил Эйлер, найдя известный сейчас ответ \pi^2/6

Victor Kleptsyn

М

19:31

Математические байки

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

Victor Kleptsyn

М

19:37

Математические байки

И можно сразу понять, что "напрямую" это сделать не получилось бы. Потому что сумма "хвоста" ряда из обратных квадратов убывает как (1/n). То есть, чтобы добыть эти шесть верных знаков, надо было бы просуммировать миллион слагаемых — вручную!

Victor Kleptsyn

М

19:39

Математические байки

Но — если мы уже знаем, насколько промахнёмся, то почему бы не исправить эту ошибку?

Victor Kleptsyn

М

19:40

Математические байки

Почему бы не сказать, что отбросив "хвост", сумму 1/m^2 при m>=n, мы примерно промахнёмся на первообразную от 1/x^2?

Victor Kleptsyn

М

19:41

Математические байки

А потом поправить это приближение, учтя, насколько 1/m^2 отличается от интеграла от 1/x^2 на отрезке [m,m+1].

Victor Kleptsyn

М

19:44

Математические байки

И это, конечно, та же самая техника, что мы видели выше.

Victor Kleptsyn

М

19:46

Математические байки

Уже если учесть только (1/n) как первое приближение для суммы
f(n+1)+f(n+2)+...,
где f(x)=1/x^2,
то мы получим для суммы всего ряда приближение
f(1)+...+f(n)+1/n,
с ошибкой, убывающей, как (1/n^2).

Victor Kleptsyn

М

19:49

Математические байки

Если перейти к формуле треугольников — ошибка будет убывать как (1/n^3), и шесть знаков уже становятся достижимы: теперь хватит n=100. (Не думаю, что сложение сотни дробей вручную может кого-то воодушевить, но по крайней мере, задача перешла из категории "невозможно" в категорию "муторно, но если очень надо..."). А можно ведь учесть ещё пару производных...

Victor Kleptsyn

М

19:58

Математические байки

Насколько я понимаю, Эйлер действовал _не_ так. Он (я тут ссылаюсь на книгу W. Dunham, "Euler: The Master of Us All" — по-хорошему, надо было бы поднять первоисточники, но я этого ещё не сделал) красивым интегрированием выяснил, что вместо просто суммы обратных квадратов можно взять сумму ряда
\sum_n 1/(n^2 * 2^(n-1)) —
и добавить к нему (ln 2)^2.

Victor Kleptsyn

М

19:59

Математические байки

Victor Kleptsyn

М

20:04

Математические байки

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

Victor Kleptsyn

М

20:04

Математические байки

Что Эйлер и сделал.

Victor Kleptsyn

М

20:07

Математические байки

Но — для этого нужно было придумать тот ход с интегрированием. И для этого тогда надо было быть Эйлером.

Victor Kleptsyn

М

20:07

Математические байки

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

Victor Kleptsyn

М

20:08

Математические байки

С большими трудозатратами, быть может, но — делалась, а не стояла непреодолимой стеной.

Victor Kleptsyn

М

20:09

Математические байки

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

Victor Kleptsyn

24 August 2019

М

15:59

Математические байки

Продолжим, пожалуй?

Victor Kleptsyn

М

15:59

Математические байки

В прошлый раз мы закончили с формулой Стирлинга на том, что n!~A \sqrt{n} (n/e)^n — но мы ещё не знаем, что A это корень из 2π.

Victor Kleptsyn

М

15:59

Математические байки

Так вот — оказывается, что корень из 2π, который в формуле Стирлинга в числителе, это "тот же самый" корень из 2π, который у нормального распределения (того, что появляется в центральной предельной теореме) в знаменателе. И есть два способа это увидеть.

Victor Kleptsyn

М

16:00

Математические байки

Первый — это заодно и способ саму центральную предельную теорему в простейшем случае увидеть.

Victor Kleptsyn

М

16:00

Математические байки

А именно, давайте зададимся вполне естественным вопросом: если мы подкидываем честную монетку N=2n раз, какие результаты мы будем наблюдать, и с какой вероятностью?

Victor Kleptsyn

М

16:00

Математические байки

Понятно, что наиболее вероятный результат это n орлов и n решек: вероятность из N подбрасываний выкинуть M орлов равна C_N^M / 2^N, а "центральный" биномиальный коэффициент C_{2n}^n самый большой.
А как такая вероятность начинает уменьшаться?

Victor Kleptsyn

М

16:01

Математические байки

Скажем, при 10000 подбрасываний — какие количества орлов естественны, а какие неправдоподобны и должны заставить заподозрить, что монетка гнутая (или ещё что-нибудь не так)?
5025? 5320? 6500?

Victor Kleptsyn

М

16:02

Математические байки

Давайте заметим, что
(C_N^{a+1}) / (C_N^a) = (N-a)/(a+1).
Потому что если в классе из N человек уже выбрано a дежурных, то есть N-a вариантов, как можно назначить (a+1)-го — и каждый набор из (a+1) дежурного получается (a+1) способами.

Victor Kleptsyn

М

16:02

Математические байки

Сравним теперь C_{2n}^n и C_{2n}^{n+k}: второй отличается от первого умножением на
n/(n+1) * (n-1)/(n+2) * ... * (n-k+1)/(n+k).

Victor Kleptsyn

М

16:02

Математические байки

Photo

331x55

Victor Kleptsyn

М

16:03

Математические байки

Получилось произведение k сомножителей.

А как я уже говорил, "видишь длинное произведение — прологарифмируй!"

Victor Kleptsyn

М

16:04

Математические байки

Логарифм отношения этих биномиальных коэффициентов равен сумме логарифмов
ln (1- (2j-1)/(n+j) )
по j от 1 до k.

Victor Kleptsyn

М

16:04

Математические байки

А ln(1+x) примерно равен x. Поэтому будет сумма от
-(2j-1)/(n+j);
да ещё и, если k<<n, то знаменатель можно заменить просто на n. И получается сумма от (2j-1)/n, а сумма нечётных чисел от 1 до (2k-1) это k^2:

Victor Kleptsyn

М

16:05

Математические байки

Victor Kleptsyn

М

16:05

Математические байки

То есть вероятность отклонения на k падает со скоростью e^{-k^2/n}.

Victor Kleptsyn

М

16:06

Математические байки

В частности, характерные отклонения имеют порядок корня из n — и слишком большие отклонения даже такого порядка мы в жизни никогда не увидим (ибо, например, e^{-25}<10^{-10})

Victor Kleptsyn

М

16:07

Математические байки

In reply to this message

Иными словами —

Victor Kleptsyn

М

16:07

Математические байки

Photo

198x41

Victor Kleptsyn

М

16:08

Математические байки

Хорошо, а всё-таки — при чём тут формула Стирлинга?

Victor Kleptsyn

М

16:09

Математические байки

Давайте её применим, чтобы оценить C_{2n}^n.
Неизвестный нам коэффициент A вылезет один раз в числителе — и два раза в знаменателе, так что не сократится:

Victor Kleptsyn

М

16:09

Математические байки

Photo

423x59

Victor Kleptsyn

М

16:11

Математические байки

Соответственно, вероятность получить в 2n подбрасываниях (n+k) орлов примерно равна

Victor Kleptsyn

М

16:11

Математические байки

Photo

261x69

Victor Kleptsyn

М

16:11

Математические байки

А чему равна сумма всех таких вероятностей?

Victor Kleptsyn

М

16:12

Математические байки

С одной стороны, сумма вероятностей равна единице (ну или сумма биномиальных коэффициентов — соответствующей степени двойки).

Victor Kleptsyn

М

16:12

Математические байки

С другой, сумма правых частей, если обозначить x_k = k/\sqrt{n}, оказывается интегральной суммой Римана для интеграла от e^{-x^2}:

Victor Kleptsyn

М

16:12

Математические байки

Photo

380x67

Victor Kleptsyn

М

16:13

Математические байки

И стремится с ростом n она к соответствующему интегралу:

Victor Kleptsyn

М

16:13

Математические байки

Photo

408x69

Victor Kleptsyn

М

16:14

Математические байки

А поскольку предел должен равняться единице — мы (почти) нашли A:

Victor Kleptsyn

М

16:14

Математические байки

Photo

189x65

Victor Kleptsyn

М

16:15

Математические байки

Остаётся посчитать интеграл в правой части. Как мы уже знаем из продекларированного ответа, он должен равняться корню из π.

Victor Kleptsyn

М

16:16

Математические байки

Есть такой неформальный принцип — пи может появиться только как длина окружности, всё, где оно возникает, должно быть как-то с окружностью связано. Пусть опосредованно, пусть не сразу видно — но где-то окружность должна быть закопана.

Victor Kleptsyn

М

16:16

Математические байки

Поэтому корень из пи — штука странная. Гораздо лучше возвести этот интеграл в квадрат:

Victor Kleptsyn

М

16:16

Математические байки

Photo

429x59

Victor Kleptsyn

М

16:16

Математические байки

После чего увидеть, что правая часть инвариантна относительно поворотов — и вот она, _окружность_ направлений!

Victor Kleptsyn

М

16:18

Математические байки

Переход в полярные координаты, или (на школьно/физическом уровне строгости) нарезание плоскости на кольца
r^2 <= x^2+y^2 < (r+dr)^2 )
легко довершит дело — и я оставлю тут это как упражнение.

Victor Kleptsyn

М

16:18

Математические байки

Всё, победа, точное значение A=\sqrt{2\pi} получено!

Victor Kleptsyn

М

16:18

Математические байки

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

Victor Kleptsyn

М

16:21

Математические байки

Хорошая анимированная иллюстрация к тому, что мы увидели —

Victor Kleptsyn

М

16:21

Математические байки

GIF

Victor Kleptsyn

М

16:21

Математические байки

(Источник — https://commons.wikimedia.org/wiki/File:De_moivre-laplace.gif)

Victor Kleptsyn

М

16:23

Математические байки

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

Victor Kleptsyn

М

16:24

Математические байки

У такой суммы будет какое-то среднее значение; и будут отклонения от него.

Victor Kleptsyn

М

16:28

Математические байки

Среднее значение на то и среднее, чтобы в среднем отклонения "в плюс" и "в минус" были одинаковы. Но можно посмотреть на среднеквадратичное отклонение (на дисперсию, для тех, кому знакомо это слово).

Victor Kleptsyn

М

16:31

Математические байки

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

Victor Kleptsyn

М

16:33

Математические байки

Центральная предельная теорема утверждает, что — что бы мы ни складывали исходно, в пределе получится одно и то же, _универсальное_, распределение: гауссовское, или нормальное, распределение.

Victor Kleptsyn

М

16:34

Математические байки

Так вот — мы сейчас увидели, что для случая подбрасывания монетки шанс, что отношение k/sqrt{n} попадёт в какой-то интервал [a,b], можно приблизить как интегральную сумму Римана — которая, в свою очередь, стремится к интегралу:

Victor Kleptsyn

М

16:34

Математические байки

Photo

399x63

Victor Kleptsyn

М

16:37

Математические байки

То есть в пределе тут мы видим распределение, у которого есть "линейная плотность"
1/\sqrt{\pi} * e^{-x^2}.

Victor Kleptsyn

М

16:38

Математические байки

Правда, мы делили отклонение на корень из n, а если посмотреть чуть аккуратнее, то средний квадрат отклонения равен n/2, соответственно, чтобы получить совсем предел "как в ЦПТ", делить надо было на \sqrt{n/2}.

Victor Kleptsyn

М

16:38

Математические байки

Если распределение выше в корень из двух раз растянуть — получится распределение с плотностью

Victor Kleptsyn

М

16:38

Математические байки

Photo

168x52

Victor Kleptsyn

М

16:39

Математические байки

И именно сходимость к распределению с такой плотностью и утверждает центральная предельная теорема.

Victor Kleptsyn

М

18:09

Математические байки

===
В рассуждениях выше уже видно, что A, которое оказывается множителем в формуле Стирлинга, появляется в знаменателе у гауссовой плотности.

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

Victor Kleptsyn

М

18:09

Математические байки

Оказывается, факториал можно представить и интегралом:
n! = \int_0^{\infty} x^n e^{-x} dx.

Victor Kleptsyn

М

18:11

Математические байки

Photo

177x59

Victor Kleptsyn

М

18:11

Математические байки

Собственно, интеграл в правой части называется гамма-функцией — и в него можно подставлять не только целые значения показателя у x:
Г(a) := \int_0^{\infty} x^{a-1} e^{-x} dx;
так что формула выше утверждает, что n!=Г(n+1).

Victor Kleptsyn

М

18:12

Математические байки

Интегрируя по частям, легко проверить, что Г(a+1)=a Г(a), и по индукции проверить, что действительно
Г(n+1)=n!.

Victor Kleptsyn

М

18:12

Математические байки

Так вот — а как бы нам оценить, чему равен этот интеграл?

Victor Kleptsyn

М

18:12

Математические байки

Сначала посмотрим: а где подынтегральная функция f(x)=x^n e^{-x} принимает максимальное значение?

Victor Kleptsyn

М

18:18

Математические байки

Запишем её как exp(g(x)), где
g(x)= ln f(x) = (n ln x - x);

Victor Kleptsyn

М

18:19

Математические байки

тогда мы хотим максимизировать g(x). Её производная равна g'(x)=n/x -1, значит, максимальное значение принимается в точке x_0=n.

Victor Kleptsyn

М

18:19

Математические байки

И равно оно f(n)=(n/e)^n — то есть мы опять поймали экспоненциальную часть приближения.

Victor Kleptsyn

М

18:22

Математические байки

Вынесем его за интеграл; останется интеграл от
exp(g(x)-g(x_0)).

Victor Kleptsyn

М

18:22

Математические байки

Вот как выглядит график подынтегральной функции при n=30:

Victor Kleptsyn

М

18:23

Математические байки

Victor Kleptsyn

М

18:23

Математические байки

Правда, напоминает гауссовский колокол выше?

Victor Kleptsyn

М

18:23

Математические байки

На самом деле — он и есть (чем больше n, тем точнее).

Victor Kleptsyn

М

18:24

Математические байки

Потому что — посмотрим, как ведёт себя функция g(x)-g(n) рядом с точкой x=n, где её значение максимально.

Victor Kleptsyn

М

18:24

Математические байки

Значение, собственно, у неё там обращается в 0 — мы его вычли.

Victor Kleptsyn

М

18:25

Математические байки

Производной тоже нет: это точка максимума.

Victor Kleptsyn

М

18:25

Математические байки

Значит, первый нетривиальный член ряда Тейлора квадратичный;
g''(n) = -1/n,
поэтому

Victor Kleptsyn

М

18:27

Математические байки

Photo

223x55

Victor Kleptsyn

М

18:28

Математические байки

А тогда

Victor Kleptsyn

М

18:29

Математические байки

Photo

213x42

Victor Kleptsyn

М

18:31

Математические байки

На самом деле, приближение выше хорошо работает не только при маленьких y, но при y порядка корня из n — а потом подынтегральная функция уже становится слишком маленькой.

Victor Kleptsyn

М

18:31

Математические байки

Поэтому гамма-функция Г(n) примерно равна произведению (n/e)^n на интеграл от e^{-y^2/2n}.

Victor Kleptsyn

М

18:32

Математические байки

Но e^{-y^2/2n} это почти плотность нормального распределения с дисперсией n — только её ещё нужно поделить на \sqrt{2\pi n}.

Victor Kleptsyn

М

18:32

Математические байки

Поделить — чтобы интеграл был единицей (ибо это полная вероятность).

Victor Kleptsyn

М

18:33

Математические байки

А значит, до деления он и равнялся \sqrt{2\pi n} — вот мы и видим, что у плотности нормального распределения он в знаменателе, а в формуле Стирлинга в качестве множителя.

Victor Kleptsyn

М

18:35

Математические байки

Но всё-таки, а откуда в гамма-функции ЦПТ, почему у нас тот самый гауссов интеграл получился?

Victor Kleptsyn

М

18:36

Математические байки

Ну, почему в числителе минус y^2, понятно: значение мы вычли, линейного слагаемого у ряда Тейлора в точке максимума не бывает, а вторая производная будет отрицательна. Пополам там тоже тейлоровский. А вот почему модуль второй производной оказался равен именно n, а не, скажем, n^2?

Victor Kleptsyn

М

18:38

Математические байки

Давайте возьмём распределение с плотностью e^{-x} на [0;+\infty) — его (логично) называют экспоненциальным распределением.

Victor Kleptsyn

М

18:41

Математические байки

(Кстати, если случайное время до какого-нибудь хорошего события — например, до прихода троллейбуса — распределено именно так, то это бывает грустно. Ведь если мы подождали, скажем, 10 минут, а троллейбус всё ещё не пришёл, то условное распределение того, сколько нам ещё остаётся ждать, ровно такое же.)

Victor Kleptsyn

М

18:42

Математические байки

Так вот — возьмём (n+1) случайную величину с таким распределением, и сложим.

Victor Kleptsyn

М

18:43

Математические байки

Плотность суммы независимых случайных величин это свёртка плотностей:

Victor Kleptsyn

М

18:43

Математические байки

Photo

457x73

Victor Kleptsyn

М

18:44

Математические байки

Но экспоненты в произведении дают e^{-x}, а объём тетраэдра x_1+...+x_{n+1}=x как раз и равен x^n/n!.

Victor Kleptsyn

М

18:46

Математические байки

Поэтому сумма (n+1) такой случайной величины имеет плотность (x^n/n!) e^{-x}.

Victor Kleptsyn

М

18:47

Математические байки

То есть n! в знаменателе — тот самый, который мы приближаем, а x^n e^{-x} — та самая функция, что под интегралом в гамма-функции.

Victor Kleptsyn

М

18:48

Математические байки

Вот почему функция под интегралом превратилась в гауссово распределение — сумма (n+1) величины и должна себя вести как нормальное распределение, это и говорит ЦПТ!

Victor Kleptsyn

М

18:51

Математические байки

И вот почему в приближении там дисперсия n: потому что это сумма ~n одинаково распределённых слагаемых, каждое с дисперсией 1 — а дисперсия складывается.

Victor Kleptsyn

М

18:52

Математические байки

Да, а вообще такие распределения — плотность как у гамма-функции, нормированные на единицу — называют (логично) гамма-распределениями:

Victor Kleptsyn

М

18:53

Математические байки

Photo

206x64

Victor Kleptsyn

М

18:54

Математические байки

И сумма двух величин, распределённых как гамма с параметрами a и b соответственно, оказывается распределённой как гамма с параметром a+b. А мы выше видели частных случай этого — для параметра a=1, который даёт просто экспоненциальное распределение.

Victor Kleptsyn

М

18:55

Математические байки

Ну вот, мы двумя способами и увидели множитель в формуле Стирлинга — а заодно посмотрели на центральную предельную теорему.

Victor Kleptsyn

М

18:56

Математические байки

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

Victor Kleptsyn

7 September 2019

М

20:44

Математические байки

Наверное, многие уже успели увидеть вот эту древнюю таблицу умножения —

Victor Kleptsyn

М

20:44

Математические байки

Н

Непрерывное математическое образование 31.08.2019 11:35:38

в качестве картинки перед новым учебным годом: таблица умножения (via https://vk.com/msu_mechmath)

«Вплоть до конца XVII века на Руси использовалась буквенная система записи цифр. Осуществлять сложные математические расчеты при помощи такой системы было невозможно, но для простых арифметических действий она вполне подходила, что и демонстрирует таблица умножения из рукописи XVII в.»

Victor Kleptsyn

М

20:44

Математические байки

На эту таблицу умножения и впрямь интересно посмотреть.
Во-первых, она начинается с квадратов.
Во-вторых, произведения там только в порядке "большее на меньшее"
В-третьих, и это самое интересное: уже в столбце квадратов мы читаем Д*Д=SI

Victor Kleptsyn

М

20:45

Математические байки

Так вот — SI это "шестнадцать", но первая цифра тут "шесть", а вторая "десять".
То есть и впрямь буквально "шестнадцать".
Ну и, например, З*В=ВI, "двенадцать".
А вот З*Г=КА, "двадцать один", и порядок возвращается к обычному для позиционной записи.

Victor Kleptsyn

М

21:09

Математические байки

===
Сегодняшняя байка — в начальной части скорее широко известная, а в заключительной скорее менее.

Если завращать гиперболу вокруг той её оси симметрии, которая её не пересекает, то получится однополостный гиперболоид. Например, если гипербола задавалась уравнением x^2-z^2=1, и вращаем вокруг оси Oz, то получится поверхность x^2+y^2-z^2=1.

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

Victor Kleptsyn

М

21:11

Математические байки

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

Victor Kleptsyn

М

21:13

Математические байки

На сайте Математических Этюдов есть рассказ об этом,
http://www.etudes.ru/ru/etudes/shukhov-tower/ ,
который я очень советую — в том числе из-за исторических фотографий. Вот одна из них, водонапорной башни на выставке 1896 года:

Victor Kleptsyn

М

21:13

Математические байки

Victor Kleptsyn

М

21:25

Математические байки

Вообще, гиперболических башен построили довольно много; я позволю себе ещё чуть-чуть процитировать сайт Этюдов —

Victor Kleptsyn

М

21:25

Математические байки

Photo

899x90

Victor Kleptsyn

М

21:26

Математические байки

Есть, скажем, гиперболическая обзорная башня в Кобе в Японии —

Victor Kleptsyn

М

21:26

Математические байки

Victor Kleptsyn

М

21:38

Математические байки

Но — самое знаменитое применение этой идеи это Шуховская (радио)башня высотой 150 метров. И тут возникает красивое развитие этой идеи — не надо строить высокие леса: можно собрать башню из гиперболических колец.

Сначала собирается первое. Потом внутри него собирается другое, и "за низ", через блоки наверху первого кольца, поднимается и пристыковывается к верху первого. Потом внутри собирается третье кольцо, и через блоки-"двуноги", которые уже есть наверху второго кольца, поднимается наверх и оно.

Иллюстрации с "Этюдов" —

Victor Kleptsyn

М

21:38

Математические байки

Victor Kleptsyn

М

21:38

Математические байки

Victor Kleptsyn

М

21:38

Математические байки

Victor Kleptsyn

М

21:39

Математические байки

Victor Kleptsyn

М

21:42

Математические байки

Учитывая, что строили её в 1919-1922 годах; сразу после первой мировой войны и революции, и при идущей гражданской — кажется, без этих идей построить башню такой высоты просто бы не получилось.

Victor Kleptsyn

М

22:00

Математические байки

Так вот — давайте вернёмся к математике (а я ещё раз посоветую посмотреть страницу Этюдов об Шуховской башне, там есть ещё нетривиальные подробности).

Я начал с того, что на однополостном гиперболоиде есть два семейства прямых. А откуда мы знаем, что они там есть?

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

Но такую поверхность можно получить, завращав вокруг (вертикальной) оси Oz любую скрещивающуюся с ней прямую L. Одно семейство прямых получится просто из образов L при вращении — а второе при его симметрии относительно любой плоскости, проходящей через ось Oz. Действительно, горизонтальные окружности, заметаемые точками L при вращении, такая симметрия сохраняет — а значит, сохраняет и всю поверхность, и образ семейства прямых это другое семейство прямых.

Victor Kleptsyn

М

22:13

Математические байки

Кстати, с этим же связана выносящая мозг иллюстрация, когда прямой стержень вращается, проезжая через кривую -- гиперболическую -- прорезь:
https://youtu.be/N2exQpSuwi0?t=830

Victor Kleptsyn

М

22:21

Математические байки

Но предположим, что мы хотим это знать именно про однополостный гиперболоид. Можно, например, взять уравнение гиперболоида выше, чуть-чуть его переписать, перенеся x^2 в правую часть —
y^2-z^2=1-x^2,
и сразу увидеть на нём две прямые, проходящие через "самую простую" точку (1,0,0):
x=1, y=±z.
Завращав их, получим оба семейства прямых. А нельзя ли обойтись без вращения?

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

Victor Kleptsyn

М

22:28

Математические байки

И тут есть рассуждение, которое пусть и не совсем строгое, но мне очень нравится: оно объясняет, что "иначе быть не может".
Давайте возьмём любую точку A — и проведём в ней касательную плоскость к гиперболоиду. Посмотрим, по какому множеству она его пересекает.
Для этого выберем на плоскости систему координат (s,t), выразим через них исходные координаты (x,y,z), и подставим результат в уравнение гиперболоида P(x,y,z)=0 — которое есть уравнение второй степени.
Естественно, систему координат на касательной плоскости мы выберем так, чтобы начальная точка A имела координаты (0,0).
Что за уравнение Q(s,t)=0 у нас получится?
Во-первых, оно второй степени. Во-вторых, Q(0,0)=0, потому что точка A была на гиперболоиде. В-третьих, линейных членов там тоже нет — потому что мы на касательной плоскости. Значит, Q(s,t) — это однородный многочлен второй степени.

Victor Kleptsyn

М

22:43

Математические байки

Если он невырожденный (что ещё нужно обосновывать), то с точностью до замены координат это либо сумма квадратов, либо разность. Если сумма квадратов, то пересечение гиперболоида с касательной плоскостью состояло бы только из одно точки A. А чисто геометрически гиперболоид выгнут "в разные стороны", так что ещё пересечения должны быть. "Значит" (кавычки, потому что "под ковёр" заметается слон упитанности большей, чем обычно), это разность квадратов — а тогда она и задаёт две пересекающиеся прямые. Которые лежат в исходном гиперболоиде, ибо это было пересечение с ним!

То есть а) через любую точку гиперболоида проходят две пересекающиеся прямые и
б) у этих прямых есть хорошее геометрическое описание — их высекает проведённая в этой точке касательная плоскость. (Что, постфактум, совершенно очевидно, но то постфактум.)

Ну и, если вспомнить, что сумма квадратов s^2+t^2=0 тоже задаёт две пересекающиеся прямые, только мнимые, s=±it, то можно добавить, что на (комплексифицированной) сфере x^2+y^2+z^2=1 тоже есть прямые, только мнимые, и искать их можно точно так же — пересечением с касательной плоскостью.

Victor Kleptsyn

М

22:55

Математические байки

В качестве ответвления — как раз наличие прямых на поверхностях второго порядка играет в сведении (преобразованиями Чирнгауз[ен]а) любого уравнения пятой степени к уравнению вида y^5+ay+1=0. После чего можно говорить, что "его решение это просто ещё одна функция от одной переменной a, и чем она хуже, чем степени, радикалы, или синус с тангенсом, кроме как исторически?". (И именно поэтому в формулировке 13-й проблемы Гильберта отдельно оговаривались многочлены именно седьмой степени — это первая степень, где оставалось три свободных параметра.)

Victor Kleptsyn

М

22:56

Математические байки

Victor Kleptsyn

М

22:56

Математические байки

Victor Kleptsyn

М

22:57

Математические байки

Но это история не на сейчас... :)

Victor Kleptsyn

21 September 2019

М

21:16

Математические байки

In reply to this message

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

Victor Kleptsyn

М

21:17

Математические байки

Есть несколько стандартных способов решать кубические уравнения. Самый, пожалуй, известный, это сначала сдвигом переменной привести его к виду x^3+px+q=0, после чего заметить, что выражение
x^3+y^3+z^3-3xyz
раскладывается на множители, одним из которых будет (x+y+z).
Остаётся найти такие y и z, чтобы p=-3yz и q=y^3+z^3, а это (по теореме Виета) превращается в квадратное уравнение с корнями y^3 и z^3.

Victor Kleptsyn

М

21:20

Математические байки

Чуть менее известный, но глобально чуть более "правильный", связан с теорией Галуа.

Victor Kleptsyn

М

21:20

Математические байки

Любой симметрический многочлен выражается через элементарные симметрические. Поэтому любой симметрический многочлен от корней полинома выражается через его коэффициенты. Так мы решаем квадратное уравнение — сумма корней x_1+x_2 уже симметрическая, а разность x_1-x_2 при их перестановке меняет знак, так что (x_1-x_2)^2 тоже выражается через коэффициенты исходного уравнения. Остаётся извлечь корень и восстановить x_1 и x_2 по их сумме и разности.

Victor Kleptsyn

М

21:23

Математические байки

Так же, но чуть более сложно решается кубическое уравнение — берутся уже три линейные комбинации корней,
S=x_1+x_2+x_3,
A=x_1+w x_2+ w^2 x_3,
B=x_1+w^2 x_2 + w x_3,
где w=exp(2πi/3) — корень кубический из единицы.

Тогда S уже симметрический, а A и B при циклической перестановке корней умножатся на w и на w^2 соответственно. Поэтому A^3 и B^3 сохраняются при циклической перестановке корней. А транспозиция меняет их местами — то есть они ведут себя как корни квадратного уравнения, коэффициенты которого (равные -(A^3+B^3) и A^3*B^3) являются уже полностью симметрическими многочленами от x_1,x_2,x_3.

Остаётся "открутить всё назад":
-решить квадратное уравнение, чтобы найти A^3 и B^3,
- извлечь кубические корни, найдя A и B,
- и решить систему из трёх линейных уравнений на три неизвестных.

Victor Kleptsyn

М

21:24

Математические байки

И если последить, то здесь как раз возникает последовательность разрешимости группы Sym_3 перестановок трёх корней, и это дорога к теории Галуа — но это меня унесло в сторону, а байка, собственно, и не об этом.

Да, для полноты, пара ссылок —
- Э. Б. Винберг, "Курс алгебры", глава 3, параграф 9, с. 145;
- D. Cox, "Galois theory", chapter 1 "Cubic equations".

Victor Kleptsyn

М

21:24

Математические байки

А хочу я рассказать о третьем, ещё менее популярном способе решать и упрощать уравнения, о преобразованиях Чирнгауза. Да, если что — Чирнгауз вот этот:
http://www-history.mcs.st-andrews.ac.uk/Biographies/Tschirnhaus.html
https://en.wikipedia.org/wiki/Ehrenfried_Walther_von_Tschirnhaus

Victor Kleptsyn

М

21:27

Математические байки

Правда, почему-то преобразования иногда называют Чирнгауза, а иногда Чирнгаузена — см.
http://mathworld.wolfram.com/TschirnhausenTransformation.html или http://mi.mathnet.ru/uzku407 ;
так и в комментариях Витушкина к 13-й проблеме Гильберта:

Victor Kleptsyn

М

21:27

Математические байки

Victor Kleptsyn

М

21:27

Математические байки

И откуда взялось это "ен", я не знаю.

Victor Kleptsyn

М

21:28

Математические байки

Так вот. Пусть у нас есть уравнение P(x)=0 какой-то степени k. И многочлен y=Q(x) меньшей степени.
Тогда можно взять корни x_1,...,x_k многочлена P, и построить новый многочлен R(y) с корнями y_1,...,y_k, получающимися как y_j=Q(x_j).

Victor Kleptsyn

М

21:29

Математические байки

И может быть, новое уравнение R(y)=0 будет проще старого, а тогда, найдя y_j, мы придём к задаче решения уравнений меньшей степени Q(x)=y_j.

Например, так решается квадратное уравнение
x^2+px+q=0:
мы делаем замену y=x+p/2, после чего приходим к более простому уравнению
y^2-(p^2/4 - q)=0,
которое и решаем извлечением квадратного корня — после чего возвращаемся к исходной переменной.

Victor Kleptsyn

М

21:29

Математические байки

Для кубического уравнения линейной заменой можно убить только коэффициент при x^2. Но что, если мы рассмотрим многочлены Q и второй степени тоже?

Оказывается, тогда можно обнулить и коэффициент при x. И получится уравнение y^3+c=0, которое решается простым извлечением кубического корня!

Victor Kleptsyn

М

21:31

Математические байки

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

Victor Kleptsyn

М

21:34

Математические байки

А это то же самое, что попросить, чтобы сумма y_i и сумма квадратов y_i равнялась бы нулю.
Уравнение на сумму — линейное уравнение на коэффициенты, на сумму квадратов — квадратное.

Victor Kleptsyn

М

21:34

Математические байки

Уравнение на сумму — линейное уравнение на коэффициенты, на сумму квадратов — квадратное.
И ещё остаётся одна "неважная" степень свободы: можно все y_i одновременно умножить на константу. Чтобы её убрать, проще всего зафиксировать у многочлена Q какой-нибудь один коэффициент — проще всего сказать, что мы будем искать многочлен y=Q(x) в виде Q(x)=x+b_0+b_2 x^2.
И тогда условие на сумму позволяет линейно выразить b_0 через b_2, а условие на сумму квадратов становится квадратным уравнением на оставшийся неизвестный коэффициент.

Victor Kleptsyn

М

21:35

Математические байки

Решив его — мы сводим исходное уравнение к уравнению вида y^3+c=0, решаем его, и затем "возвращаемся обратно", решая квадратные уравнения Q(x_i)=y_i.

Victor Kleptsyn

М

21:36

Математические байки

===
Если попытаться решить уравнение 4-й степени тем же преобразованием "в лоб", то получится система из линейного уравнения (сумма y_i нулевая), квадратного (сумма квадратов y_i), и кубического (сумма кубов). И если всё выражать "в лоб", то будет уравнение 1*2*3=6-й степени на коэффициенты преобразования. Свести уравнение 4-й степени к уравнению 6-й не выглядит победой...

Victor Kleptsyn

М

21:38

Математические байки

Но можно сделать так — прибить только коэффициенты при y и при y^3. И нахождение такого Q будет только кубическим уравнением, которое мы уже научились решать.
Собственно, раз у нас только два уравнения — хватит даже квадратного многочлена Q,
y=Q(x)= x+ b_0+ b_2 x^2.
Тогда линейное условие позволяет выразить b_0 через b_2, а условие на сумму произведений y_i по три (увы, тут упрощения уже нет, и придётся повозиться) — становится кубическим уравнением на оставшуюся переменную.

Victor Kleptsyn

М

21:38

Математические байки

После такого преобразования, раз мы прибили коэффициенты при y и при y^3 — остаётся биквадратное уравнение!

Victor Kleptsyn

М

21:39

Математические байки

А его уже можно решить — ну и дальше вернуться обратно.

Victor Kleptsyn

М

21:39

Математические байки

===
Для уравнения 5-й степени ничего такого, естественно, не проходит: обнуление коэффициентов при y^4, y^3,..., y^1 это уже уравнения 1, 2, 3, 4 степени соответственно — и в итоге получается уравнение 24-й степени, которое никак не решить.

Victor Kleptsyn

М

21:40

Математические байки

Но можно привести уравнение к виду y^5+ay+1=0.

Действительно: когда мы задаём y=Q(x)=b_4 x^4 + ... + b_1 x + b_0, то у нас пять неизвестных коэффициентов; их можно все одновременно умножать на константу, так что пока зафиксируем, например, b_1=1.
Условие обнуления суммы y_i — линейное условие на коэффициенты. Поэтому остаётся 3 неизвестных коэффициента.

Victor Kleptsyn

М

21:40

Математические байки

Остаётся обнулить сумму квадратов и сумму кубов. Если идти "в лоб", то получится уравнение 6-й степени, с которым не очень-то поработаешь. Но!

Victor Kleptsyn

М

21:41

Математические байки

Условие обнуления суммы квадратов y_i — это квадратичное условие, и мы получаем квадратичную поверхность в пространстве (из трёх ещё неизвестных коэффициентов). Как раз такую, какую мы обсуждали в контексте Шуховской башни.
Так давайте на этой поверхности найдём (комплексную, если надо) прямую, хотя бы одну!

Victor Kleptsyn

М

21:42

Математические байки

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

Victor Kleptsyn

М

21:42

Математические байки

Так что любое уравнение 5 степени можно свести к уравнению вида
y^5+a y + 1=0
(потому что свободный член можно всегда загнать в 1 изменением масштаба).

Victor Kleptsyn

М

21:44

Математические байки

Да, ссылка —
В. В. Прасолов, "Многочлены" (файл книги есть тут —
https://www.mccme.ru/prasolov/ — в списке под номером 11), с. 187.

Victor Kleptsyn

М

21:46

Математические байки

Ну и — можно говорить, что функция y(a) одной переменной "корень уравнения
y^5+ay+1=0
с параметром a" ничем не хуже кучи остальных функций одной переменной (будь то хоть корень, хоть синус, хоть тангенс), кроме того, что она нам в школе не встречалась.

Victor Kleptsyn

М

21:53

Математические байки

И это (а, точнее, аналогичные рассуждения с функциями двух переменных) были мотивировкой 13-й проблемы Гильберта — с совершенно удивительным ответом.
Но про это я напишу чуть позже, а пока я собираюсь вернуться к простой геометрии.
А именно ("в следующей серии") — к вопросу о том, сколько прямых пересекают заданную четвёрку скрещивающихся прямых в трёхмерном пространстве. Оказывается, на этот вопрос можно, естественно, смотреть геометрически — а можно с точки зрения линейной алгебры, где, удивительным образом, возникают собственные вектора. Но это тоже будет в следующей серии — а на сегодня, кажется, настало время прекратить дозволенные речи.

Victor Kleptsyn

15 October 2019

М

19:28

Математические байки

===
Как-то давно я не писал, это надо исправлять. Тем более, что и повод есть — у нас сегодня в Ренне было открытие амфитеатра имени Мариам Мирзахани:
https://irmar.univ-rennes1.fr/actualites/journee-dinauguration-de-lamphitheatre-maryam-mirzakhani
И пару сюжетов мне хочется пересказать.

Victor Kleptsyn

М

19:31

Математические байки

Да, на всякий случай: вот слайд из рассказа Elise Goujard —

Victor Kleptsyn

М

19:31

Математические байки

Victor Kleptsyn

М

19:31

Математические байки

А уже в 2017-м Мирзахани не стало. Рак. :(

Victor Kleptsyn

М

19:32

Математические байки

Так вот — я начну с рассказа Ольги Paris-Ромаскевич:

Victor Kleptsyn

М

19:32

Математические байки

Victor Kleptsyn

М

19:37

Математические байки

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

Victor Kleptsyn

М

19:39

Математические байки

А теперь представим себе, что мы на плоскости взяли паркет, в котором часть плиток с коэффициентом преломления +1 ("воздух"), а другие — с коэффициентом преломления (-1).

Victor Kleptsyn

М

19:39

Математические байки

Victor Kleptsyn

М

19:41

Математические байки

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

Victor Kleptsyn

М

19:42

Математические байки

Victor Kleptsyn

М

19:42

Математические байки

Вот так луч проходит через несколько параллельных границ

Victor Kleptsyn

М

19:43

Математические байки

Victor Kleptsyn

М

19:43

Математические байки

А вот так — лучи могут отражаться вокруг точки, где сходятся шесть правильных треугольников.

Victor Kleptsyn

М

19:44

Математические байки

Собственно, если взять паркет из правильных треугольников или из квадратов, то _все_ траектории замкнутся.

Victor Kleptsyn

М

19:44

Математические байки

Victor Kleptsyn

М

19:47

Математические байки

К такому бильярдный народ совершенно не привычен — а аналогия, которую тут приводила Ольга, это задача двух тел (если энергия достаточно небольшая, чтобы планета не улетела — то орбита будет периодической)

Victor Kleptsyn

М

19:47

Математические байки

Вопрос — а что будет для других паркетов? Например — для паркета из неправильных треугольников?

Victor Kleptsyn

М

19:47

Математические байки

И вот тут начинается интересное.

Victor Kleptsyn

М

19:50

Математические байки

Во-первых, бывают более сложные периодические траектории. И бывают траектории, линейно убегающие на бесконечность — периодичным или даже не-периодичным (с учётом сдвига) образом.

Victor Kleptsyn

М

19:50

Математические байки

Victor Kleptsyn

М

19:52

Математические байки

А может ли траектория быть неограниченной, но не убегать на бесконечность? Улетели на расстояние 100 от начальной точки, преломления её развернули, вернулись, улетели на расстояние 1000, развернулись, вернулись, и так далее?

Victor Kleptsyn

М

19:52

Математические байки

Оказывается, нет, не может!

Victor Kleptsyn

М

19:53

Математические байки

Victor Kleptsyn

М

19:55

Математические байки

Более того, траектория, просто два раза подряд вернувшаяся в один и тот же треугольник, уже обязана оказаться периодической — и зациклиться уже в этот момент. А если траектория периодическая, и её начальное условие чуть-чуть пошевелить (наклонить-сдвинуть), то она останется периодической.

Victor Kleptsyn

М

19:58

Математические байки

И у этого есть очень простое и красивое объяснение. Дело в том, что простейший паркет из одинаковых треугольников можно "сложить" — складывая/отражая относительно каждого ребра.
Если говорить формально, то такое "складывание" это (не-взаимно-однозначное) непрерывное отображение из плоскости в плоскость, которое есть изометрия на каждом отдельном треугольнике, а на любые два соседних его ограничения отличаются на симметрию.

Victor Kleptsyn

М

19:58

Математические байки

Но картинки тут, кажется, понятнее:

Victor Kleptsyn

М

19:58

Математические байки

Victor Kleptsyn

М

19:58

Математические байки

Victor Kleptsyn

М

19:58

Математические байки

Victor Kleptsyn

М

19:59

Математические байки

Victor Kleptsyn

М

20:01

Математические байки

Так вот — магия состоит в том, что при таком складывании отрезки траектории луча переходят на одну и ту же прямую.

Victor Kleptsyn

М

20:03

Математические байки

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

Victor Kleptsyn

М

20:07

Математические байки

(Да, из ответвлений: мне ситуация, когда складывания переводят что-то в одну прямую, напомнила немного мультик "одним разрезом" — http://www.etudes.ru/ru/etudes/fold-cut-problem/ — но может быть, это далёкая ассоциация... Хотя, наверное, не так и безумно далёкая: если складывание уже есть, то разрезав по этой прямой ножницами/гильотиной, мы как раз путь луча и получим)

Victor Kleptsyn

М

20:08

Математические байки

In reply to this message

Вот всё и доказано. И в частности, траектория луча не может самопересечься — что совершенно не так, например, в бильярдах.

Victor Kleptsyn

М

20:09

Математические байки

Но и это ещё не всё. Посмотрим ещё на периодические траектории:

Victor Kleptsyn

М

20:10

Математические байки

Victor Kleptsyn

М

20:11

Математические байки

Каждый раз множество вершин и рёбер, попавших внутрь траектории, образует дерево. Не бывает так, чтобы внутри содержался целый треугольник, куда траектория не заходила бы.
А всегда ли это так?

Victor Kleptsyn

М

20:13

Математические байки

Теорема (Olga Paris-Romaskevich): Да, всегда.

Victor Kleptsyn

М

20:13

Математические байки

Photo

855x76

Victor Kleptsyn

М

20:14

Математические байки

(Отсюда — https://hal.archives-ouvertes.fr/hal-02169195 )

Victor Kleptsyn

М

20:17

Математические байки

Доказательство. Любую траекторию (в частности, периодическую) можно включить в "слоение" плоскости: плоскость-образ после складывания можно нарезать на параллельные прямые, а потом взять полный прообраз этой нарезки. Получаются вот такие красивые картинки:

Victor Kleptsyn

М

20:17

Математические байки

Victor Kleptsyn

М

20:18

Математические байки

Но если есть периодическая траектория — можно её сдвигать "внутрь", пока не получится особая траектория — входящая и выходящая из какой-нибудь из вершин:

Victor Kleptsyn

М

20:18

Математические байки

Victor Kleptsyn

М

20:21

Математические байки

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

Victor Kleptsyn

М

20:22

Математические байки

Так вот — оказывается, что часть теоретически возможных вариантов поведения для цветка запрещена:

Victor Kleptsyn

М

20:22

Математические байки

Victor Kleptsyn

М

20:28

Математические байки

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

Victor Kleptsyn

М

20:29

Математические байки

Victor Kleptsyn

М

20:31

Математические байки

In reply to this message

А, ещё вот такая картинка для определения слоения, кажется, более наглядная:

Victor Kleptsyn

М

20:31

Математические байки

Victor Kleptsyn

М

20:32

Математические байки

In reply to this message

Вот всё и доказано!

Victor Kleptsyn

М

20:34

Математические байки

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

Victor Kleptsyn

М

20:35

Математические байки

Две вещи, которые используются в её доказательстве (и тут я начинаю говорить уже совсем пунктиром):

Victor Kleptsyn

М

20:36

Математические байки

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

Victor Kleptsyn

М

20:36

Математические байки

Victor Kleptsyn

М

20:36

Математические байки

Victor Kleptsyn

М

20:37

Математические байки

Всё ещё получается (особое) слоение — раз на плоскости после складывания они, кроме как в вершине, не пересекались, то и про прообразы то же самое можно сказать.

Victor Kleptsyn

М

20:40

Математические байки

Инструмент второй — символическая динамика: можно записывать/кодировать буквами a,b,c, какие именно стороны треугольников пересекает траектория:

Victor Kleptsyn

М

20:41

Математические байки

Victor Kleptsyn

М

20:41

Математические байки

(А вот — картинка даже для случая четырёхугольника, там уже a,b,c,d)

Victor Kleptsyn

М

20:41

Математические байки

Victor Kleptsyn

М

20:46

Математические байки

Ну вот с их помощью (уже не буду говорить, как) теорему о запрещённых цветках — а через неё и теорему о дереве — Ольга и доказывает.

Victor Kleptsyn

М

20:47

Математические байки

А вот мультфильм с визуализацией этого, который был показан под конец лекции. Теперь вы знаете всё, что там появляется:
https://www.youtube.com/watch?v=t1r1cO1V35I

Victor Kleptsyn

М

20:50

Математические байки

Пара кадров оттуда —

Victor Kleptsyn

М

20:53

Математические байки

Victor Kleptsyn

М

20:54

Математические байки

Victor Kleptsyn

М

20:54

Математические байки

И последний, ещё наглядный, но уже более сложный аккорд — это сложность траекторий.

Victor Kleptsyn

М

21:01

Математические байки

In reply to this message

Вот мы видели периодические и линейно убегающие на бесконечность траектории. А что-нибудь ещё бывает? И насколько сложными бывают периодические траектории? И каким может быть набор всех траекторий для данного треугольного паркета?

Victor Kleptsyn

М

21:02

Математические байки

Всё зависит от того, из каких именно треугольников собран паркет:

Victor Kleptsyn

М

21:02

Математические байки

Victor Kleptsyn

М

21:03

Математические байки

Для некоторых (например, для правильного) — периодичны все траектории.

Victor Kleptsyn

М

21:03

Математические байки

Для некоторых — часть траекторий периодична, а часть убегает на бесконечность с линейной скоростью.

Victor Kleptsyn

М

21:05

Математические байки

(и это как раз типичный случай.)

Victor Kleptsyn

М

21:13

Математические байки

А есть — очень хитрые: для них (почти все) траектории, которые проходят через центр описанной окружности, посещают (либо в прошлом, либо в будущем) все вообще плитки. То есть это убегание на бесконечность, но гораздо более медленное. А не-проходящие — периодичны, но чем ближе траектория к проходящей через центр, тем больше у неё период.
Более того, эти периоды — удвоенные элементы последовательности Трибоначчи (1,1,1,3, следующее = сумма трёх предыдущих, так что получается
1,1,1,3,5,9,17,...).
2*1, правда, не бывает, зато бывает остальное — 2*3=6, 2*5=10,...

Victor Kleptsyn

М

21:13

Математические байки

Victor Kleptsyn

М

21:15

Математические байки

Треугольник для этого должен быть с очень специальными углами — вообще, тут (сейчас скажу, почему) играют углы, а не, например, длины сторон или что-нибудь ещё.

Victor Kleptsyn

М

21:15

Математические байки

Victor Kleptsyn

М

21:23

Математические байки

Уравнение a+a^2+a^3=1 — то самое, которое играет роль во фрактале Рози. Который сам по себе тема для отдельной байки, а пока лишь пара картинок и ссылок...

Victor Kleptsyn

М

21:23

Математические байки

1) https://en.wikipedia.org/wiki/Rauzy_fractal + картинка из Википедии:

Victor Kleptsyn

М

21:23

Математические байки

Victor Kleptsyn

М

21:24

Математические байки

https://www.mccme.ru/dubna/2014/courses/kanel-mitrofanov.htm — связанный с этим курс;

Victor Kleptsyn

М

21:25

Математические байки

https://youtu.be/fMJflV_GUpU?t=231 — а вот и настоящий паркет из дерева...

Victor Kleptsyn

М

21:27

Математические байки

Ну и на сейчас хватит — в общем, красивый самоподобный объект. Так вот, периодические траектории в паркете с тем самым Рози-треугольником, когда они становятся всё больше и больше (начинаясь близко к центру описанной окружности) — становятся похожи на этот самый фрактал Рози!

Victor Kleptsyn

М

21:48

Математические байки

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

Victor Kleptsyn

М

21:57

Математические байки

(И это совсем несложно увидеть, но уже точно не в этот раз...)
Пара картинок в завершение рассказа:

Victor Kleptsyn

М

21:57

Математические байки

Victor Kleptsyn

М

21:58

Математические байки

(перекладывания со сдвигом и переворотом)

Victor Kleptsyn

М

21:58

Математические байки

Теорема о том, что траектория через центр окружности в исключительном бильярде проходит через все плитки:

Victor Kleptsyn

М

21:59

Математические байки

Photo

1042x148

Victor Kleptsyn

М

22:00

Математические байки

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

Victor Kleptsyn

М

22:01

Математические байки

Да, "работа над ошибками" — я поторопился в начале сказать, что для квадратного паркета периодичны все траектории. Это для паркета из правильных треугольников так, а для квадратного, если луч соединяет две противоположные стороны, то он как раз линейно убежит на бесконечность.

Victor Kleptsyn

М

22:06

Математические байки

In reply to this message

Последнее — преобразования перекладывания отрезков это совершенно огромная область (с чем только не связанная). Даже перечислять не буду, а то до завтра не закончу. И индукция Рози (а Рози тот же) как раз оттуда. И похожий на треугольник Серпинского (и даже ему гомеоморфный, но определяемый с помощью проективных отображений) Rauzy gasket, который появлялся в левом верхнем углу на том фото, где описывалось поведение траекторий — оттуда же.

Victor Kleptsyn

М

22:07

Математические байки

Ну и на этом я хочу на сегодня прекратить дозволенные речи...

Victor Kleptsyn

21 October 2019

М

12:33

Математические байки

In reply to this message

Ещё одна байка с прошлого раза — это рассказ Elise Goujard (в тот же день) на "пятиминутке Лебега".
В Ренне раз в неделю есть жанр популярных рассказов коллегам и широкой публике — на пять минут. Буквально — с таймером, тикающим обратным отсчётом от 5:00.

Рассказывают как присутствующим — так и выкладывают в интернет:
https://www.lebesgue.fr/5min
или
https://www.youtube.com/watch?v=184oPJA-CPw&list=PLZ5ZEffH1cUAkodxGDs0SNif_wScXNTU0

Victor Kleptsyn

М

12:35

Математические байки

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

Вопрос: пусть у нас есть комната, ограниченная идеальными зеркалами. Можно ли там поставить точечный источник света так, чтобы в результате комната была освещена целиком? Или, может быть, свечку вообще можно ставить почти куда угодно — ведь свет всё отражается и отражается?

Victor Kleptsyn

М

12:36

Математические байки

Оказывается, что нет — и пример был опубликован в 1958 году отцом и сыном Пенроузами. Контрпример ко второму (более слабому вопросу) это вот такая фигура —

Victor Kleptsyn

М

12:37

Математические байки

Victor Kleptsyn

М

12:38

Математические байки

Верхняя её часть это половина эллипса, а большая ось этого эллипса касается нижней части границы в фокусах — отсекая тем самым отмеченные A и B области.

Victor Kleptsyn

М

12:39

Математические байки

Как мы знаем, луч, вышедший из одного из фокусов, попадает в другой. Поэтому луч, вышедший из отрезка между фокусами (то есть из области A), вернётся тоже на отрезок между ними, уйдя обратно в область A: сравните с лучом, отражающимся в той же точке эллипса и приходящем из одного из фокусов.
Наоборот, луч, приходящий из области B, уйдёт тоже в область B (с другой стороны). Значит, где бы мы ни поставили свечку в области A, она не осветит ничего в области B.

Victor Kleptsyn

М

12:41

Математические байки

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

Victor Kleptsyn

М

12:42

Математические байки

In reply to this message

(Справа на фото можно увидеть траекторию луча, стартовавшую из B — ниже оси она всегда приходит в B)

Victor Kleptsyn

М

12:42

Математические байки

Кстати, если запускать бильярд просто в эллипсе — то луч, продолжая отражаться, всегда будет касаться либо одного и того же софокусного эллипса (пересекая большую ось за фокусами), либо одной и той же софокусной гиперболы (пересекая ось между фокусами). Вот хорошая картинка (отсюда: https://mat-web.upc.edu/people/amadeu.delshams/articles/pebnonli.pdf ) —

Victor Kleptsyn

М

12:43

Математические байки

Victor Kleptsyn

М

12:44

Математические байки

Но вернёмся к исходному вопросу. Пока мы увидели пример, показывающий, что если поставить свечку в область B, то не будет освещена область A, а если в A, то будет темно в области B. То есть куда угодно, и даже почти куда угодно, источник света ставить нельзя. Но ведь если свечку поставить совсем наверху, то оттуда-то мы сможем всё осветить, оттуда и A, и B видно!

Victor Kleptsyn

М

12:44

Математические байки

Давайте доработаем пример — возьмём две его копии, и соединим "туннелем" между областями A.

Victor Kleptsyn

М

12:46

Математические байки

Эту иллюстрацию я взял из "Математического дивертисмента" Фукса-Табачникова (который всячески рекомендую) —

Victor Kleptsyn

М

12:46

Математические байки

Victor Kleptsyn

М

12:50

Математические байки

А вот — из видео Numberphile, где тоже много чего хорошего есть (кстати, в том видео рассказывает Howard Masur!), https://www.youtube.com/watch?v=xhj5er1k6GQ :

Victor Kleptsyn

М

12:50

Математические байки

Victor Kleptsyn

М

12:51

Математические байки

Теперь уже у нас есть B-области и "сверху", и "снизу". И если свеча стоит в верхней полуплоскости — то мы не сможем осветить нижние B-области, а если в нижней — то верхние.

Victor Kleptsyn

М

12:55

Математические байки

Отдельно интересно было посмотреть, где и как пример был опубликован (кстати, смотреть первоисточники это вообще хороший рефлекс — и результат часто бывает интересный; как-нибудь я тут расскажу байку про "человек имеет форму шара"). А именно — вот ссылка:

Victor Kleptsyn

М

12:55

Математические байки

L. Penrose and R. Penrose, Puzzles for Christmas, New Scientist, 25 December (1958), 1580–1581, 1597.

Victor Kleptsyn

М

12:56

Математические байки

И это действительно "Puzzles" с ответами —

Victor Kleptsyn

М

12:56

Математические байки

Victor Kleptsyn

М

12:56

Математические байки

И вот ответ —

Victor Kleptsyn

М

12:56

Математические байки

Victor Kleptsyn

М

13:08

Математические байки

А головоломка по соседству — как Mr Tan может добраться до запутавшегося в ветвях воздушного змея:

Victor Kleptsyn

М

13:08

Математические байки

Victor Kleptsyn

М

13:14

Математические байки

Victor Kleptsyn

М

13:15

Математические байки

Возвращаясь к рассказу Элизы: а что, если бильярд многоугольный? Ведь отражение от прямого зеркала вещь гораздо более понятная.

Victor Kleptsyn

М

13:19

Математические байки

В 1995 году George Tokarsky придумал комнату, где, если поставить свечу в одной конкретной точке — некоторая другая точка не будет освещена. Более того, углы в ней все кратны 45 градусам.
Тут мне хочется процитировать коллег —

Victor Kleptsyn

М

13:20

Математические байки

Н

Непрерывное математическое образование 16.09.2018 15:48:35

В многоугольной комнате с зеркальными стенами поставили точечный источник света. Обязательно ли вся комната освещена?

Примерно 40 лет это был открытый вопрос, а потом в 1995 году G.W.Tokarsky придумал комнату, для которой это не так.

Victor Kleptsyn

М

13:20

Математические байки

Н

Непрерывное математическое образование 16.09.2018 15:48:49

картинка по выходным: комната Токарского (источник света в точке A0 освещает всю комнату, кроме точки A1)

Victor Kleptsyn

М

13:22

Математические байки

Если, скажем, отразить всю комнату относительно самой правой стены, объединить, а стену убрать — то свеча в A0 не сможет осветить уже две точки, A1 и её зеркальный образ.

Victor Kleptsyn

М

13:28

Математические байки

Так вот — допустим, что у исходного многоугольника все углы рационально соизмеримы с развёрнутым (выражаются рациональным числом градусов, или имеют вид p/q * π в радианах).

Victor Kleptsyn

М

13:28

Математические байки

Тогда, как рассказывает Элиза (и Мазур в Numberphile), где бы ни находился точечный источник света, он осветит всю комнату, кроме, быть может, _конечного_ числа точек.

Victor Kleptsyn

М

13:36

Математические байки

И это утверждение следует из "теоремы о волшебной палочке" Эскина и Мирзахани (о которой Антон Зорич пишет тут — https://arxiv.org/abs/1502.05654 ) — но на этом пять минут Элизы истекли, и все пошли пить (традиционный) чай с плюшками.

Victor Kleptsyn

М

13:36

Математические байки

Victor Kleptsyn

22 October 2019

М

13:17

Математические байки

In reply to this message

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

Victor Kleptsyn

М

13:18

Математические байки

Первый — геометрический.
Оставим из четырёх прямых только три, и спросим себя — как устроены те прямые, которые их все пересекают? И что заметает их объединение?

Victor Kleptsyn

М

13:18

Математические байки

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

Victor Kleptsyn

М

13:18

Математические байки

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

Victor Kleptsyn

М

13:19

Математические байки

А нет ли других прямых, которые данные три пересекают?
Нет: ведь три прямые l_1, l_2, l_3 не имеют общих точек (даже на бесконечности — они ведь скрещивающиеся!), значит, любая прямая l, которая их всех пересекает, имеет хотя бы три общих точки с гиперболоидом.

Victor Kleptsyn

М

13:19

Математические байки

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

Victor Kleptsyn

М

13:20

Математические байки

Значит, любая прямая, которая пересекает l_1,l_2,l_3, обязана лежать на проходящем через них гиперболоиде. (И значит, это прямая из второго семейства.)
Остаётся вернуться к вопросу про четыре прямых.

Victor Kleptsyn

М

13:20

Математические байки

Пусть прямая l пересекает l_1,l_2,l_3,l_4; посмотрим, где может лежать точка пересечения P прямой l с l_4.
С одной стороны, P должна быть на гиперболоиде, проходящем через l_1,l_2,l_3 (потому что l лежит там целиком). С другой — P лежит на l_4 по определению.

Victor Kleptsyn

М

13:21

Математические байки

Значит, P это точка пересечения l_4 с этим гиперболоидом.
И каждый вариант точки пересечения даёт свою прямую l. Вот и геометрический ответ — что есть столько прямых, в скольки точках l_4 пересекает соответствующий гиперболоид. Типичным образом их две, как корней у квадратного уравнения (ограничения уравнения гиперболоида на эту прямую) — но они могут комплексными.

Victor Kleptsyn

М

13:21

Математические байки

Второй подход — линейно-алгебраический; но для него мне сначала нужно будет сказать слова «проективная плоскость» и «проективное пространство». Заранее прошу прощения у тех, кто с ними уже хорошо знаком — несколько следующих сообщений можно пролистать, не читая.

Victor Kleptsyn

М

13:22

Математические байки

Решая геометрическую задачу и разбирая случаи, «а что, если эти две прямые не пересекаются, а параллельны», часто бывает удобно сказать, что две параллельные прямые «пересекаются на бесконечности». То есть формально добавить к плоскости «точки на бесконечности», в которых они пересекутся. Таких точек будет по одной на каждое направление; а все вместе они образуют бесконечно удалённую прямую. И когда такое добавление сделано — то, например, любые две различные прямые пересекаются ровно в одной точке. А пополненная плоскость называется проективной.

Victor Kleptsyn

М

13:23

Математические байки

Это хорошо, но неприятно, что точки теперь разделились на «конечные» и «на бесконечности»: в геометрии ведь хорошо то, что все точки равноправны. Так вот, оказывается, есть эквивалентное, но гораздо более «инвариантное» определение.

Victor Kleptsyn

М

13:23

Математические байки

А именно: точка проективной плоскости это, по определению, прямая в трёхмерном пространстве, проходящая через начало координат.

Victor Kleptsyn

М

13:23

Математические байки

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

Victor Kleptsyn

М

13:24

Математические байки

Давайте теперь свяжем эти два подхода. А именно: если мы теперь возьмём плоскость z=1. С одной стороны, это обычная плоскость с обычной геометрией в ней. С другой, большинство прямых через начало координат в R^3 её пересекут в единственной точке — и вот и соответствие между прямыми и точками на плоскости. А те прямые, что плоскости параллельны — и будут бесконечно удалёнными точками.

Victor Kleptsyn

М

13:25

Математические байки

Victor Kleptsyn

М

13:25

Математические байки

(Иллюстрация отсюда —
https://www.mccme.ru/free-books/dubna/lvovski-developables.pdf )

Victor Kleptsyn

М

13:25

Математические байки

И дальше всё продолжается очень естественно. Что такое прямая в проективной геометрии? Это плоскость, проходящая через начало координат. И действительно, почти любая плоскость на плоскости z=1 высечет прямую — а единственная, что ей параллельна, это z=0, и это как раз бесконечно удалённая прямая.

Victor Kleptsyn

М

13:25

Математические байки

Две параллельные прямые (в плоскости z=1) действительно теперь (с точки зрения проективной геометрии) пересекаются в бесконечно удалённой точке — ибо соответствующие плоскости в R^3 пересекаются по прямой, параллельной им и проходящей через начало координат. А это и есть одна из бесконечно удалённых точек.

Victor Kleptsyn

М

13:26

Математические байки

Равноправие точек обеспечивается тем, что можно взять не плоскость z=1, а, к примеру, плоскость x=1 или y=1 (или вообще любую, не проходящую через ноль). И бесконечно удалёнными станут уже другие точки; правда, расстояния и углы такой переход не сохранит.

Victor Kleptsyn

М

13:26

Математические байки

Наконец, проективные преобразования плоскости получаются, если взять линейные преобразования пространства, и посмотреть, как они действуют на множестве прямых в R^3, проходящих через начало координат.

Victor Kleptsyn

М

13:26

Математические байки

Понятно, что это « проективная геометрия в двух словах » — а нормально её можно почитать, например, в Куранте-Робинсоне, см. главу 4: http://ilib.mccme.ru/pdf/kurant.pdf

Victor Kleptsyn

М

13:27

Математические байки

Так вот: давайте рассмотрим уже не проективную плоскость, а проективное пространство; точно так же, это множество прямых, проходящих через начало координат в R^4.
Прямая в проективном пространстве это плоскость в R^4. Две прямые скрещиваются, если соответствующие им плоскости пересекаются только по началу координат. И, наоборот, пересекаются, если у плоскостей есть нетривиальное пересечение.

Victor Kleptsyn

М

13:27

Математические байки

А теперь перейдём к нашей задаче. У нас есть четыре попарно скрещивающиеся прямые в пространстве, то есть четыре плоскости в R^4, любые две из которых пересекаются лишь по началу координат. А до какой степени можно упростить эту картину?

Victor Kleptsyn

М

13:28

Математические байки

Возьмём первые две скрещивающиеся прямые — соответствующие им плоскости можно взять за координатные в R^4: пусть это будут Oxy и Ozt.

Victor Kleptsyn

М

13:29

Математические байки

А третью и четвёртую тогда можно рассматривать, как графики (обратимых) отображений из первой плоскости во вторую. В частности, заменой координат третью плоскость можно сделать « диагональной »: состоящей из векторов вида (u,u) для всех u из R^2. Ну а четвёртая это просто график какого-то линейного отображения.

Victor Kleptsyn

М

13:29

Математические байки

Итого: плоскости приведены к виду множеств всевозможных (u,0), (0,u), (u,u) и (u,Au) соответственно, где A — некоторое отображение.

Victor Kleptsyn

М

13:29

Математические байки

А что такое прямая, пересекающая эти четыре? Это плоскость π, нетривиально пересекающая все эти плоскости. Значит, в ней найдутся вектора вида (u,0) — раз она пересекает первую — и (0,v) — раз пересекает вторую.

Victor Kleptsyn

М

13:30

Математические байки

Тогда это её базис — то есть все вектора π имеют вид (au,bv). Но π должна пересекать третью — "диагональную" — плоскость, значит, там найдётся ненулевой вектор вида (au,bv), для которого au=bv. То есть v= (a/b)u, поэтому v можно заменить на u.

Victor Kleptsyn

М

13:30

Математические байки

Остаётся последнее — π должна пересекать и четвёртую плоскость. Значит, там найдётся вектор вида
(au,bu)=(au, A(au)).

Victor Kleptsyn

М

13:31

Математические байки

Если его сжать в a раз, то получится вектор
(u,(b/a)u) = (u, Au), и значит,
Au=cu, где c=b/a.

Victor Kleptsyn

М

13:32

Математические байки

То есть вектор u линейное преобразование A переводит в пропорциональный себе! А это и есть собственный вектор. Ура!

Victor Kleptsyn

М

13:32

Математические байки

Итак, прямые, пересекающие четыре данных, оказались соответствующими собственным векторам матрицы 2x2.
Да, в качестве рекламы — очень хорошая иллюстрация собственных векторов (для тех, кто с ними ещё не сталкивался) есть тут:
https://youtu.be/PFDu9oVAE-g?t=137

Victor Kleptsyn

М

13:33

Математические байки

А собственных векторов у типичной матрицы 2x2 как раз два — хотя иногда они (как и корни квадратного уравнения) бывают и комплексными.

Victor Kleptsyn

М

13:33

Математические байки

Вот мы и получили линейно-алгебраический взгляд на тот же вопрос!

Victor Kleptsyn

М

13:33

Математические байки

Соседний вопрос — а много ли « существенно различных » четвёрок попарно скрещивающихся прямых в пространстве? Если на них действовать проективными преобразованиями — то как будут устроены инварианты такого действия? Или, может быть, любую четвёрку можно перевести в любую (точно так же, как любую тройку можно перевести в любую даже аффинным преобразованием)?

Victor Kleptsyn

М

13:34

Математические байки

Если посчитать размерности, то сразу видно, что инварианты будут: прямая в R^3 задаётся (локально) 4 числами (например, 2 числа для её направления, задаваемого как точка на сфере, и ещё 2 на координату её пересечения с одной из координатных плоскостей, которой она не параллельна). Так что пространство (или, правильнее сказать, многообразие) четвёрок прямых 4*4=16-мерно.

Victor Kleptsyn

М

13:35

Математические байки

А проективное преобразование это (невырожденное) линейное преобразование R^4 (задающееся 16-ю элементами своей матрицы) — с точностью до умножения на константу (ибо гомотетия прямые не меняет). Поэтому группа проективных преобразований проективного пространства 16-1=15-мерна.

Victor Kleptsyn

М

13:35

Математические байки

15<16, так что минимум один инвариант будет.

Victor Kleptsyn

М

13:35

Математические байки

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

Victor Kleptsyn

М

13:35

Математические байки

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

Victor Kleptsyn

М

13:36

Математические байки

На языке линейной алгебры: когда у нас есть четыре плоскости в R^4, то третью и четвёртую можно рассматривать, как графики отображений из первой во вторую. А тогда их композиционное частное — корректно определённое отображение из первой плоскости в себя. Это, конечно, та самая матрица A выше — просто можно сказать « композиционное частное », а можно — « выбор координат на плоскостях, при котором одно из отображений тождественно ».

Victor Kleptsyn

М

13:36

Математические байки

И отображение A корректно определено — а тогда у него есть инварианты: собственные значения.

Victor Kleptsyn

М

13:36

Математические байки

Так вот, эти два ответа совпадают — двойные отношения точек пересечения как раз и есть собственные значения матрицы A.

Victor Kleptsyn

М

13:38

Математические байки

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

Victor Kleptsyn

М

13:39

Математические байки

А с другой стороны, она и есть двойное отношение, что проверяется совсем мгновенно. Пусть у нас есть прямая, не проходящая через начало координат O, и она пересекает наши четыре прямые в точках A,B,C,D. Если отрезки OA и OB на первой и второй прямых взять за единичные, то прямая OC будет графиком функции умножения на (AC:CB). А прямая OD — умножения на (AD:DB). А их композиционное частное — на частное этих отношений. То есть на двойное отношение.

Victor Kleptsyn

М

13:41

Математические байки

Кстати — бывают ведь ещё нетипичные случаи. Если матрица A оказывается скалярной, это означает, что каждый вектор для неё собственный. И это значит, что все четыре прямые лежат на одном гиперболоиде.

Victor Kleptsyn

М

13:42

Математические байки

А если преобразование A это жорданова клетка — матрица вида (c, 1 \\ 0, c) — то собственный вектор у него только один. И это отвечает случаю, когда четвёртая прямая касается гиперболоида (но не лежит на нём).

Victor Kleptsyn

М

13:44

Математические байки

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

Victor Kleptsyn

М

13:50

Математические байки

Вот такой сюжет; ну и на этом я на сегодня хочу прекратить дозволенные речи.

Victor Kleptsyn

31 October 2019

М

12:58

Математические байки

Две короткие истории про "как посчитать".

Victor Kleptsyn

М

12:58

Математические байки

Допустим, мы хотим диагонализовать матрицу A размера 2x2 — и ищем её собственные вектора.

Victor Kleptsyn

М

12:58

Математические байки

Вот мы нашли собственные значения, λ_1 и λ_2...
... и собираемся решить две системы, чтобы найти собственные вектора. А надо ли это делать?

Victor Kleptsyn

М

12:59

Математические байки

Нет!
Ведь (A-λ_1*Id)(A-λ_2*Id)=0 (aka теорема Гамильтона-Кэли).

Victor Kleptsyn

М

12:59

Математические байки

Значит, собственный вектор с собственным значением λ_1 можно прочитать в (любом) столбце матрицы A-λ_2*Id. И наоборот, собственный вектор с собственным значением λ_2 — в любом столбце матрицы A-λ_1*Id.

Victor Kleptsyn

М

13:00

Математические байки

С матрицами 3x3 такое тоже можно применять, но тут уже вопрос, что кому проще: перемножить две матрицы (A-λ_1*Id)(A-λ_2*Id), чтобы в столбце прочитать собственный вектор, или решить систему (A-λ_3*Id) v =0.

(Помнится, этому трюку нас в своё время научил И. А. Дынников. Давно это было!)

Victor Kleptsyn

М

13:01

Математические байки

Второй трюк — а что, если мы хотим посчитать какую-то функцию от матрицы (скажем, сотую степень, или экспоненту) в исходном базисе. И матрица опять маленькая, 2x2 или 3x3.

Victor Kleptsyn

М

13:02

Математические байки

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

Victor Kleptsyn

М

13:03

Математические байки

Но можно — проще!
Пусть мы хотим найти F(A), где F — многочлен.

Victor Kleptsyn

М

13:03

Математические байки

Поделим F(x) с остатком на характеристический многочлен P(x)=П_j (x-λ_j) матрицы A:
F(x)=P(x)Q(x)+R(x).
Но P(A)=0 (опять теорема Гамильтона-Кэли), значит, F(A)=R(A).

Victor Kleptsyn

М

13:05

Математические байки

При этом остаток R(x) — штука "простая"; скажем, для матрицы размера 2x2 это просто линейный многочлен, R(x)=ax+b, и
F(A)=R(A)=a*A+b*Id.

Victor Kleptsyn

М

13:05

Математические байки

Для матрицы 3x3 — многочлен второй степени, так что R(A) посчитать тоже не очень сложно, знать бы только R(x) как многочлен. Но вот как его найти?

Victor Kleptsyn

М

13:06

Математические байки

А очень просто: если мы делим многочлен F с остатком на P, то значения остатка в корнях P совпадают со значениями F.

Victor Kleptsyn

М

13:08

Математические байки

Поэтому остаток от деления F на P с некратными корнями — это единственный многочлен степени <= deg P -1, у которого в корнях те же значения, что и у F.

Victor Kleptsyn

М

13:08

Математические байки

Иными словами — интерполяционный многочлен Лагранжа.

Victor Kleptsyn

М

13:13

Математические байки

И вот получается алгоритм вычисления F(A): сначала построить интеполяционный многочлен R(x) по известным значениям F(λ_j) в корнях P(x) — собственных значениях λ_j. И потом подставить туда A.

Для матрицы A размера 2x2, нахождение R(x) это проведение прямой по двум точкам, что совсем быстро.

Victor Kleptsyn

М

13:14

Математические байки

Для матрицы размера 3x3 — работы чуть больше (возвести A в квадрат, найти квадратный трёхчлен по трём значениям), но тоже вполне обозримо.

Victor Kleptsyn

М

13:18

Математические байки

А узнал я это в своё время из посвящённого многочленам Лагранжа курса Аскольда Георгиевича Хованского — https://www.mccme.ru/dubna/2006/courses/khovansky.html (а вот тут лежат его записки — https://www.mccme.ru/dubna/2006/notes/newlagrang.pdf )

Victor Kleptsyn

7 November 2019

М

20:27

Математические байки

Математические постеры, которые висят в коридорах факультета математики (https://math.u-bourgogne.fr/ ) в Дижоне:

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:27

Математические байки

Victor Kleptsyn

М

20:29

Математические байки

Не у всех есть глубокое содержание — но смотрятся очень хорошо (и "создают атмосферу").

Victor Kleptsyn

М

20:30

Математические байки

In reply to this message

Тут — стереографическая проекция, и это один из кадров из второй главы фильма Жиса, Йоса и Альвареса "Измерения":
http://dimensions-math.org/Dim_RU.htm

Victor Kleptsyn

М

20:33

Математические байки

Начинается он довольно просто — но потом доходит до правильных многогранников в размерности 4, и до того, как на них можно "посмотреть глазами": сначала "надуть", чтобы они легли на трёхмерную сферу в R^4, а потом сделать стереографическую проекцию, получив картинку в R^3.

Victor Kleptsyn

М

20:38

Математические байки

И про расслоение Хопфа и окружности Вилларсо в конце тоже рассказывают. Я, собственно, ровно оттуда узнал, что если рассечь тор, полученный честным вращением окружности, бикасательной плоскостью —

Victor Kleptsyn

М

20:39

Математические байки

Victor Kleptsyn

М

20:39

Математические байки

то в сечении получатся две пересекающиеся окружности:

Victor Kleptsyn

М

20:39

Математические байки

Victor Kleptsyn

М

20:40

Математические байки

Так что на "торе вращения" есть _четыре_ семейства окружностей: параллели, меридианы, и два семейства окружностей Вилларсо.

Victor Kleptsyn

М

20:47

Математические байки

In reply to this message

Возвращаясь к правильным многогранникам — вот картинки одного из них, 120-гранника:

Victor Kleptsyn

М

20:47

Математические байки

Victor Kleptsyn

М

20:47

Математические байки

Victor Kleptsyn

М

20:50

Математические байки

Собственно, построить проще двойственный к нему, многогранник со 120 вершинами (и 600 гранями). А именно — если взять додекаэдр, то группа его вращений состоит из 60 элементов (любую грань в любую 12 способами, и самосовмещений грани 5 штук, 12*5=60).

Victor Kleptsyn

М

20:51

Математические байки

Кстати, это группа A_5 — и если задаться вопросом, "а почему именно группа перестановок, кого она переставляет", то на него есть удивительно хороший ответ: 5 вписанных кубов.

Victor Kleptsyn

М

20:52

Математические байки

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

Victor Kleptsyn

М

20:53

Математические байки

Рёбра куба в любой грани додекаэдра будут диагоналями — и любая диагональ однозначно достраивается до куба.

Victor Kleptsyn

М

20:54

Математические байки

И вот эти-то пять кубов группа вращений додекаэдра и переставляет.

Victor Kleptsyn

М

20:56

Математические байки

In reply to this message

Так вот — группа вращений додекаэдра состоит из 60 элементов. А группа SO(3) вращений трёхмерного пространства двулистно накрывается группой кватернионов единичной длины (трёхмерное пространство рассматривается как чисто мнимые кватернионы, а сопряжение z->q z q^{-1} сохраняет длины и вещественную ось, значит, оказывается его вращением).

Victor Kleptsyn

М

20:57

Математические байки

Группа кватернионов единичной длины это трёхмерная сфера в H=R^4 — и прообраз группы из 60 элементов это 120 её точек, которые и будут вершинами того самого правильного многогранника.

Victor Kleptsyn

М

21:06

Математические байки

А вообще, о том, как классифицируются все правильные многогранники, рассказано в дубнинской брошюре Е. Смирнова — https://www.mccme.ru/free-books/dubna/smirnov-reflections-v2.pdf .
Собственно, классифицируется-то больше: та же система корней E_8 вещь более важная, чем знание о том, что в размерности выше 4 правильные многогранники только стандартные ("[гипер]тетраэдр", "[гипер]куб" и "[гипер]октаэдр" = "двойственный к [гипер]кубу").

Victor Kleptsyn

М

21:07

Математические байки

Иллюстрация оттуда, объясняющая, при чём тут группы отражений —

Victor Kleptsyn

М

21:07

Математические байки

Victor Kleptsyn

М

21:08

Математические байки

И её "живой аналог" для икосаэдра (за который спасибо М. Панову) —

Victor Kleptsyn

М

21:08

Математические байки

Victor Kleptsyn

М

21:09

Математические байки

(Группа отражений тут чуть меньшая — все зеркала идут по рёбрам — но зато смотрится более красиво и симметрично.)

Victor Kleptsyn

М

21:11

Математические байки

А отражения собраны из одного-единственного исходного треугольника — собственно, как тут:
http://www.etudes.ru/ru/models/football-mirror-icosahedron/

Victor Kleptsyn

М

21:15

Математические байки

In reply to this message

А картинка на этом постере соответствует вот этой статье —
http://www.ams.org/publicoutreach/feature-column/fcarc-lorenz

Victor Kleptsyn

М

21:19

Математические байки

Заслуживающей отдельного рассказа самой по себе – чего стоят одни ролики анимаций, которые к ней "прикручены".

Victor Kleptsyn

М

21:28

Математические байки

Но это будет как-нибудь в другой раз — тут есть красивый рассказ про то, почему пространство решёток на комплексной плоскости это C^2 без кривой {z^2=w^3}, что эта кривая высекает на единичной сфере узел-трилистник, и это именно тот самый трилистник, который появляется на постере, что фундаментальная группа дополнения к нему это группа кос B_3, потому что корни кубического уравнения, и так далее — но это надо писать вдумчиво, так что как-нибудь в другой раз.

Victor Kleptsyn

М

21:31

Математические байки

А чтобы завершить вечер картинок — фреска в UMPA ENS Lyon:

Victor Kleptsyn

М

21:31

Математические байки

Victor Kleptsyn

М

21:31

Математические байки

Она большая, во всю стену (так что слева на фотографии — это дверь), и с кучей математических сюжетов.

Victor Kleptsyn

М

21:32

Математические байки

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

Victor Kleptsyn

М

21:33

Математические байки

А вот что воздушный шар раскрашен под расслоение Хопфа — уже нужно заметить.

Victor Kleptsyn

М

21:48

Математические байки

Солнце (которое, правда, не очень видно) раскрашено под универсальную накрывающую сферы Римана без трёх точек — которая есть диск (а треугольники "с вершинами на абсолюте" переходят в верхнюю и нижнюю полуплоскости, в зависимости от раскраски).
Лента справа завивается дорожкой вихрей Кармана — https://en.wikipedia.org/wiki/K%C3%A1rm%C3%A1n_vortex_street .
А верёвка завязывается в дикий узел (https://en.wikipedia.org/wiki/Wild_knot )

Victor Kleptsyn

М

21:49

Математические байки

Ну и последнее на сегодня — а вот эти постеры висят у нас в Ренне на лестнице:
http://sorciersdesalem.math.cnrs.fr/Posters/posters.html

Victor Kleptsyn

М

21:50

Математические байки

Там сильно больше комментариев — правда, они по-французски...

Victor Kleptsyn

М

21:51

Математические байки

Ну и на этом я рассказ "о красивых картинках", наверное, завершу.

Victor Kleptsyn

8 November 2019

М

14:02

Математические байки

В продолжение темы про узлы — байка про трёхцветные раскраски.

Victor Kleptsyn

М

14:02

Математические байки

Как можно доказывать, что узел (формально, вложение окружности в R^3) нельзя развязать? Или что два узла различны?

Victor Kleptsyn

М

14:03

Математические байки

Самый естественный подход — нужен какой-нибудь инвариант. И почти всегда инвариант строится не по узлу в R^3, а по его диаграмме — "узлу, вид сверху".

Victor Kleptsyn

М

14:03

Математические байки

Вот взятая из Википедии таблица узлов с небольшим числом перекрёстков:

Victor Kleptsyn

М

14:03

Математические байки

Victor Kleptsyn

М

14:04

Математические байки

Так вот, самый простой в определении инвариант — это число правильных трёхцветных раскрасок.

Victor Kleptsyn

М

14:05

Математические байки

А именно, раскрасим диаграмму узла в три цвета (красный, синий, зелёный) — раскрашивая каждую связную компоненту (от одного ныряния "под" перекрёсток до другого) в один цвет.

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

Victor Kleptsyn

М

14:05

Математические байки

Пример: правильная раскраска трилистника (image credit: Wikipedia)

Victor Kleptsyn

М

14:06

Математические байки

Victor Kleptsyn

М

14:07

Математические байки

Теорема. Число правильных раскрасок — инвариант узла.

Victor Kleptsyn

М

14:07

Математические байки

Как такое нужно доказывать? Как обычно: показывать, что в процессе перехода от одного узла к другому он не меняется.

Victor Kleptsyn

М

14:08

Математические байки

Процесс деформации (гомотопии) одного узла в другой с точки зрения диаграмм разбивается на конечное число _движений Редемейстера_:

Victor Kleptsyn

М

14:08

Математические байки

Victor Kleptsyn

М

14:09

Математические байки

(image credit: Wolfram Mathworld, http://mathworld.wolfram.com/ReidemeisterMoves.html )

Victor Kleptsyn

М

14:09

Математические байки

Соответственно, нужно доказать, что каждое такое движение не изменяет числа трёхцветных раскрасок.

Victor Kleptsyn

М

14:09

Математические байки

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

Victor Kleptsyn

М

14:10

Математические байки

Например:

Victor Kleptsyn

М

14:10

Математические байки

Victor Kleptsyn

М

14:11

Математические байки

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

Victor Kleptsyn

М

14:12

Математические байки

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

Victor Kleptsyn

М

14:12

Математические байки

И тут помогает вот какое наблюдение: обозначим наши цвета 0, 1 и 2. Три цвета удовлетворяют условию "все одинаковые или все разные" тогда или только тогда, когда их сумма равна 0 mod 3.

Victor Kleptsyn

М

14:13

Математические байки

Действительно, 0+1+2=0 mod 3, 3x=0 mod 3.

Victor Kleptsyn

М

14:13

Математические байки

(А третий цвет однозначно определяется двумя, так что переход в обратную сторону тоже мгновенный)

Victor Kleptsyn

М

14:13

Математические байки

Соответственно, мы можем работать в поле по модулю 3 — зная, что если два из подошедших к перекрёстку цветов это a и b, то третий это -(a+b).

Victor Kleptsyn

М

14:14

Математические байки

In reply to this message

И теперь уже мгновенно проверяется, что если три подходящих к R3-перестройке сверху (на рисунке выше) цвета это a, b и c (слева направо), то вниз они придут и в том, и в другом случае как
-a+b+c, b и -(a+b).

Victor Kleptsyn

М

14:15

Математические байки

А проверить движения R1 и R2 ещё быстрее.

Victor Kleptsyn

М

14:16

Математические байки

Правда, всё равно остаётся ощущение чуда: почему именно при таких правилах получился инвариант?

Victor Kleptsyn

М

14:16

Математические байки

Оказывается, на это есть хороший ответ — но прежде ещё пара замечаний.
Во-первых, мы между делом обнаружили, что число правильных трёхцветных раскрасок всегда будет степенью тройки. Потому что это число решений системы линейных (однородных) уравнений вида x_i+x_j+x_k=0 (где i,j и k — номера нитей, встречающихся в данном перекрёстке) над полем из трёх элементов.

Victor Kleptsyn

М

14:17

Математические байки

А это 3 в степени размерность пространства решений.

Victor Kleptsyn

М

14:17

Математические байки

Во-вторых, условие "три одинаковых или три разных" встречается ещё в замечательной игре SET:

Victor Kleptsyn

М

14:17

Математические байки

VK

Victor Kleptsyn 19.07.2019 19:59:39

Victor Kleptsyn

М

14:18

Математические байки

Там нужно находить (из выложенных на стол 12) тройки карточек, по каждому из четырёх параметров (цвет, тип закраски, количество, форма) либо все совпадающие, либо все различающиеся. И из-за перевода выше это можно переформулировать как поиск прямых в четырёхмерном пространстве над полем из трёх элементов.
Не то, чтобы это сильно в игре помогало. :)

Victor Kleptsyn

М

14:19

Математические байки

Так вот — а _почему_ число трёхцветных раскрасок это инвариант?
Оказывается, что хоть мы на него смотрели "аддитивно", на него есть и "некоммутативный" взгляд.

Victor Kleptsyn

М

14:25

Математические байки

У узла есть такой естественный инвариант: фундаментальная группа дополнения к нему (https://en.wikipedia.org/wiki/Knot_group )

Victor Kleptsyn

М

14:25

Математические байки

То есть группа петель в R^3\K, в которой произведение это последовательный проход сначала одной петли, потом другой.

Victor Kleptsyn

М

14:27

Математические байки

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

Тогда легко увидеть, что фундаментальная группа порождается петлями вида "спустились к диаграмме, обошли вокруг одной из нитей, поднялись обратно":

Victor Kleptsyn

М

14:28

Математические байки

Victor Kleptsyn

М

14:29

Математические байки

А соотношения приходят из перекрёстков: два обхода "нижних" нитей перекрёстка сопрягаются обходом верхней нити:

Victor Kleptsyn

М

14:29

Математические байки

Victor Kleptsyn

М

14:31

Математические байки

На этом рисунке γ_j=γ_i^{-1} γ_k γ_i:
спускаясь в южный квадрант, мы уходим не сразу в западный, а сначала в восточный (это γ_i), потом в верхний (γ_k), и наконец, в восточный (γ_i^{-1}).

Victor Kleptsyn

М

14:33

Математические байки

Так вот: раз фундаментальная группа G=π_1(R^3\K) это инвариант, то инвариант и всё, что по ней можно построить.
Давайте посчитаем число гомоморфизмов из G в группу перестановок S_3 трёх элементов — но не любых, а таких, чтобы петля-один обход нити переходила бы в транспозицию. (Поскольку все такие обходы сопряжены, то это тоже инвариантное условие.)

Victor Kleptsyn

М

14:35

Математические байки

В S_3 есть три транспозиции: (12), (13) и (23).

Victor Kleptsyn

М

14:36

Математические байки

И это и будут наши три цвета: ведь условие "a^{-1} b a = c" для транспозиций a,b,c из S_3 равносильно условию "либо все три совпадают, либо все три различны".

Victor Kleptsyn

М

14:38

Математические байки

Вот, собственно, и всё — условие на правильность раскраски оказалось условием на гомоморфизм фундаментальной группы в S_3 (что соотношения выполняются). И число правильных раскрасок — это число вот таких гомоморфизмов.

Victor Kleptsyn

М

14:43

Математические байки

Последний комментарий в виде ассоциации — шестая задача отсюда:
http://math.mosolymp.ru/upload/files/2017/khamovniki/10-1/2016.09.26_Vesa.pdf

Victor Kleptsyn

М

14:44

Математические байки

(Не буду объяснять, почему, будет подсказка, но если что, рядом лежат и решения: via http://math.mosolymp.ru/2017_khamovniki_10_1 )

Victor Kleptsyn

М

14:46

Математические байки

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

Victor Kleptsyn

15 November 2019

М

19:27

Математические байки

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

Victor Kleptsyn

М

19:27

Математические байки

Victor Kleptsyn

М

19:27

Математические байки

Victor Kleptsyn

М

19:28

Математические байки

Рассмотрим вот такую группу:

H_4=< a,b,c,d | aba^{-1}=b^2,
bcb^{-1}=c^2,
cdc^{-1}=d^2,
dad^{-1}=a^2 >

Victor Kleptsyn

М

19:28

Математические байки

Собственно, индекс 4 подсказывает, что есть и группа H_n. У неё n образующих — a_1,...,a_n — и n соотношений:
a_i a_{i+1} a_i^{-1} = a_{i+1}^2.

Victor Kleptsyn

М

19:30

Математические байки

Просто группы H_2 и H_3 оказываются тривиальны — а вот группа H_4 уже бесконечна. Что, впрочем, неочевидно, но пока мы в это поверим.

Так вот, с помощью этой группы Хигман в 1951-м построил первый пример бесконечной конечно-порождённой простой группы.

Victor Kleptsyn

М

19:31

Математические байки

А именно, оказывается, что верно вот такое утверждение —

Victor Kleptsyn

М

19:31

Математические байки

Теорема (Хигман, 1951): у группы H_n нет нетривиальных конечных факторов.

Victor Kleptsyn

М

19:31

Математические байки

Забавным образом, эта теорема выводится из малой теоремы Ферма.

Victor Kleptsyn

М

19:32

Математические байки

А именно: пусть у нас есть какой-то конечный фактор фактор одной из групп H_n. Он порождён образами b_i образующих a_i. Давайте докажем, что они все тривиальны.

Victor Kleptsyn

М

19:32

Математические байки

Собственно, раз это фактор — на b_i выполнены те же соотношения, что и раньше на a_i, но в дополнение к ним и ещё какие-то.

Victor Kleptsyn

М

19:32

Математические байки

Во-первых, если тривиален хотя бы один образ b_i, то тривиальны они все — потому что b_i сопрягает b_{i+1} с его квадратом; раз b_i=e, то сопряжение ничего не делает, и b_{i+1}=b_{i+1}^2, и тогда b_{i+1}=e.

Victor Kleptsyn

М

19:33

Математические байки

Во-вторых, пусть теперь они все нетривиальны. Раз мы предположили, что фактор конечный, то это всё — элементы конечного порядка.
То есть у каждого b_i есть свой порядок m_i>1.

Victor Kleptsyn

М

19:33

Математические байки

Мы знаем, что b_i сопрягает b_{i+1} с его квадратом, b_{i+1}^2.
Применив это m_i раз, получаем, что b_{i+1} совпадает со своей 2^{m_i}-й степенью:

Victor Kleptsyn

М

19:34

Математические байки

Photo

595x50

Victor Kleptsyn

М

19:34

Математические байки

То есть
b_{i+1}^{2^{m_i} - 1} = e,
откуда 2^{m_i} - 1 делится на m_{i+1}.

Victor Kleptsyn

М

19:35

Математические байки

Значит, у нас есть n "стоящих по кругу" порядков m_i, и следующий является делителем 2 в степени предыдущий минус один.

Victor Kleptsyn

М

19:35

Математические байки

Остаётся заметить, что из малой теоремы Ферма следует вот такая лемма:
Лемма. Для любого m>1 наименьший простой делитель 2^m-1 строго больше наименьшего простого делителя m.

Victor Kleptsyn

М

19:35

Математические байки

Photo

712x64

Victor Kleptsyn

М

19:36

Математические байки

(Это — из исходного текста Хигмана)

Victor Kleptsyn

М

19:36

Математические байки

Доказательство. Пусть r — наименьший простой делитель 2^m - 1.

Victor Kleptsyn

М

19:36

Математические байки

Тогда по малой теореме Ферма 2^{r-1} сравнимо с 1 по модулю r, и значит (алгоритм Евклида), 2^{НОД(m,r-1)} тоже сравнимо с 1 по модулю r.

Victor Kleptsyn

М

19:37

Математические байки

Если r не строго больше наименьшего простого делителя m, то m и r-1 взаимно просты, то есть НОД выше равен 1. И тогда 2=1 по модулю r => противоречие.

Victor Kleptsyn

М

19:37

Математические байки

Лемма доказана — а теорема из неё выводится мгновенно.

Потому что из неё следует, что у порядков m_i наименьшие простые делители строго возрастают. Но индексы i идут "по кругу" (по модулю n) — а возрастающая последовательность чисел замкнуться не может.

Victor Kleptsyn

М

19:38

Математические байки

Вот мы и получили противоречие — и тем самым доказали, что у H_n нет нетривиальных конечных факторов.

Victor Kleptsyn

М

19:38

Математические байки

In reply to this message

Теорема выше доказана.

Victor Kleptsyn

М

19:38

Математические байки

Остаётся из неё получить простую бесконечную группу.

Victor Kleptsyn

М

19:39

Математические байки

Рассмотрим нормальные подгруппы H_4, не совпадающие с самой H_4. Как минимум одна такая есть — это просто {e}.

Victor Kleptsyn

М

19:40

Математические байки

Возьмём максимальную по включению такую подгруппу G. Такая есть; это можно увидеть стандартной техникой, через лемму Цорна — у любой "башни" вложенных нормальных подгрупп есть "супремум": объединение их всех.
Это тоже нормальная подгруппа, и тоже меньшая H_4 (если она совпадает с H_4, то в неё входят все 4 образующих a,b,c,d — а тогда они входят уже в какую-то из объединяемых подгрупп, противоречие). Значит, есть "максимальный" элемент — искомая максимальная нормальная подгруппа.

(Собственно, точно так же доказывается наличие базиса Гамеля в бесконечномерном линейном пространстве, и так далее — https://ru.wikipedia.org/wiki/Лемма_Цорна )

Victor Kleptsyn

М

19:42

Математические байки

Но можно и совсем "вручную": перенумеровать элементы группы, начать с подгруппы {e}, и для каждого очередного элемента g_k из H_4 смотреть, можно ли его добавить в уже построенную подгруппу так, чтобы она (после добавления всех сопряжённых/обратных/степеней, чтобы остаться нормальной подгруппой) не стала H_4. Если можем — добавляем, нет — оставляем. То, что получится, когда мы пробежим всё H_4 (формально — объединение возрастающей башни подгрупп) и будет искомой.

Victor Kleptsyn

М

19:45

Математические байки

(Вопрос о том, можно ли тут совсем по-честному обойтись без аксиомы выбора, — учитывая, что процедура на каждом шагу однозначная, и совершаем мы только однократный выбор перечисления элементов H_4 — я собираюсь замести под ковёр, ибо речь сейчас не об этом.)

Victor Kleptsyn

М

19:46

Математические байки

Так вот — возьмём (какую-нибудь) максимальную по включению, меньшую H_4, нормальную подгруппу G в группе H_4.
И рассмотрим фактор H_4/G. Это и есть обещанный исторически первый пример бесконечной конечно-порождённой простой группы.

Victor Kleptsyn

М

19:46

Математические байки

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

Во-вторых, она простая: если бы у неё была бы нетривиальная нормальная подгруппа, то её прообраз при факторизации H_4 -> H_4 / G был бы нормальной подгруппой H_4, большей G, а мы предположили, что G максимальная.

Victor Kleptsyn

М

19:46

Математические байки

Всё!

Victor Kleptsyn

М

19:48

Математические байки

Микеле, конечно, рассказывал не [только] об этом — это был лишь кусочек вводной части. А рассказывал он о том, как заставить группу Хигмана H_4 действовать на окружности —

Victor Kleptsyn

М

19:48

Математические байки

Victor Kleptsyn

М

19:49

Математические байки

(Картинка отсюда — http://mtriestino.perso.math.cnrs.fr/Higman.pdf )

Victor Kleptsyn

М

20:11

Математические байки

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

Victor Kleptsyn

М

20:11

Математические байки

А именно: назовём группу "левоупорядочиваемой" (left-orderable), если на ней есть полный порядок "<", инвариантный относительно умножения слева:
f<g <=> hf<hg
(такой порядок называется "левоинвариантным").

Victor Kleptsyn

М

20:12

Математические байки

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

Victor Kleptsyn

М

20:12

Математические байки

Но удивительным образом оказывается, что это связано с динамикой!
А именно — пусть группа G действует преобразованиями прямой, сохраняющими ориентацию. И пусть есть какая-нибудь точка x_0, которую ни один нетривиальный элемент G не оставляет на месте. Тогда это задаёт левоинвариантный порядок — будем говорить, что g<h, если g(x_0)<h(x_0)!

Victor Kleptsyn

М

20:28

Математические байки

Если есть несколько точек x_0,x_1,..., и ни одно преобразование не оставляет их все на месте одновременно — то можно устроить лексикографический левоинвариантный порядок:
g<h, если
* либо g(x_0)<h(x_0),
* либо g(x_0)=h(x_0), но g(x_1)<h(x_1),
* либо g(x_0)=h(x_0), g(x_1)=h(x_1), но g(x_2)<h(x_2),
и так далее.

Victor Kleptsyn

М

20:28

Математические байки

Наконец, взяв счётное всюду плотное множество точек на прямой (например, рациональные) — можно увидеть, что группа Homeo_+(R) вся левоупорядочиваема.
И, в частности, любая группа, которая умеет действовать на R сохраняющими ориентацию гомеоморфизмами так, чтобы никто не действовал тождественно — левоупорядочиваема.

Victor Kleptsyn

М

20:30

Математические байки

На самом деле — если есть счётная группа G и левоинвариантный порядок на ней, то можно заставить её действовать на прямой так, чтобы порядок приходил из орбиты одной конкретной точки. (Это доказывается взятием начальной точку и последовательным построением её орбиты так, чтобы порядок точек был бы соответствующим порядку на группе.)
Так что если на счётной группе левый порядок есть, то он всегда приходит из [какого-то] действия!

Victor Kleptsyn

М

20:30

Математические байки

Victor Kleptsyn

М

20:30

Математические байки

Последнее замечание — одиночные соотношения из групп H_n,
aba^{-1}= b^2,
тоже связаны с действиями — это соотношение на преобразования a(x)=2x и b(x)=x+1.

Victor Kleptsyn

М

20:31

Математические байки

А вообще такие соотношения порождают группы Баумслага-Солитара, https://en.wikipedia.org/wiki/Baumslag–Solitar_group , из которых BS(1,n) это как раз группы, порождённые преобразованиями
x->nx и x->x+1,
и вообще хорошие и понятные — а вот общие BS(m,n) это (IMHO) ужас...

Victor Kleptsyn

М

20:31

Математические байки

Ну и — про порядки на группах и их действия есть недавний текст (под кодовым названием GOD), "Groups, Order and Dynamics" —
https://arxiv.org/pdf/1408.5805.pdf

Victor Kleptsyn

М

20:32

Математические байки

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

Victor Kleptsyn

27 November 2019

М

12:27

Математические байки

Вот такого замечательного доказательства формулы для синуса суммы углов я раньше не видел —

Victor Kleptsyn

М

12:27

Математические байки

Г

Геометрия-канал 22.11.2019 13:35:58

Наглядное доказательство формулы синуса суммы из книжки Ícons of Mathematics #картинка

Victor Kleptsyn

М

12:28

Математические байки

А ещё пользуюсь случаем порекламировать (если вдруг кто ещё не видел) —

Victor Kleptsyn

М

12:28

Математические байки

Н

Непрерывное математическое образование 26.11.2019 21:15:06

http://book.etudes.ru/

Victor Kleptsyn

М

12:28

Математические байки

Н

Непрерывное математическое образование 26.11.2019 22:00:43

ms-books.pdf

1.4 MB

в вышедшем сейчас втором издании мат. составляющей множество новых сюжетов (фактически это новая книга) и некоторые новые разделы

вот, например, «Книжная полка» — большой список книг по математике для самых разных читателей

Victor Kleptsyn

М

12:28

Математические байки

===

Victor Kleptsyn

М

12:28

Математические байки

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

Victor Kleptsyn

М

12:30

Математические байки

Общая канва тут — берётся какой-нибудь комбинаторный объект, и задаются вопросы вроде "а сколько таких объектов заданного большого размера" или "на что похож такой типичный объект". Или — как устроены типичные отклонения от предельного поведения (но это уже следующий уровень сложности).

Victor Kleptsyn

М

12:33

Математические байки

Игрушечный пример — последовательности нулей и единиц. Их 2^n, а в типичной последовательности нулей и единиц примерно поровну. Наконец, отклонение от среднего числа имеет типичный порядок \sqrt{n}, и описывается центральной предельной теоремой — если на \sqrt{n} поделить, то частное ведёт себя (асимптотически) как случайная величина, распределённая по Гауссу.

Victor Kleptsyn

М

12:35

Математические байки

In reply to this message

(Собственно, мы даже это уже в этом канале обсуждали — см. сообщение выше)

Victor Kleptsyn

М

12:37

Математические байки

Чтобы получалась более комбинаторно-геометрическая картинка, можно превратить последовательность 0 и 1 в путь, идущий по квадратной решётке вправо при 0 и вверх при 1. Тогда при большом n путь, скорее всего, будет идти рядом с диагональю.

Victor Kleptsyn

М

12:38

Математические байки

Можно нарисовать картинки — только я разверну решётку на 45 градусов; путь тогда будет идти вправо-вверх и вправо-вниз, а в среднем просто вправо.

Victor Kleptsyn

М

12:38

Математические байки

Вот 30 шагов:

Victor Kleptsyn

М

12:38

Математические байки

Victor Kleptsyn

М

12:39

Математические байки

Вот 100:

Victor Kleptsyn

М

12:39

Математические байки

Victor Kleptsyn

М

12:39

Математические байки

Вот 300 (уже без решётки, иначе она превратится в сплошной чёрный фон):

Victor Kleptsyn

М

12:39

Математические байки

Victor Kleptsyn

М

12:39

Математические байки

Ну и наконец, вот 3000 —

Victor Kleptsyn

М

12:39

Математические байки

Victor Kleptsyn

М

12:40

Математические байки

А вот растянутая в корень из n раз по вертикали картинка — как раз отвечающая на вопрос про поведение типичных отклонений (n=1000):

Victor Kleptsyn

М

12:40

Математические байки

Victor Kleptsyn

М

12:41

Математические байки

Это уже — (одномерное) броуновское движение (а точнее, его график как функции от времени).

Victor Kleptsyn

М

12:42

Математические байки

Пожалуй, самый сейчас известный пример из асимптотической комбинаторики — это ацтекский бриллиант.

Victor Kleptsyn

М

12:48

Математические байки

Вот тут есть рассказ о нём по-французски —
http://images.math.cnrs.fr/Pavages-aleatoires-par-touillage (но с языком можно справиться как Google Translate-ом, так и просто посмотреть на красивые картинки), ему посвящён вот этот математический постер — http://sorciersdesalem.math.cnrs.fr/Posters/PosterCercleArctique.png ; но я про него коротко расскажу с самого начала.

Victor Kleptsyn

М

12:51

Математические байки

А по-русски про него можно подробно прочитать в дубнинской брошюре Е. Смирнова, "Три взгляда на ацтекский бриллиант",
https://www.mccme.ru/free-books/dubna/smirnov-aztec.pdf

Victor Kleptsyn

М

12:52

Математические байки

Так вот, если формально, то ацтекский бриллиант (aztec diamond) это фигура, составленная из квадратиков на квадратной решётке, у которых сумма модулей абсциссы и ординаты центра не превосходит заданной величины (которая называется порядком бриллианта).
В переводе на русский — он выглядит вот так:

Victor Kleptsyn

М

12:52

Математические байки

Victor Kleptsyn

М

12:53

Математические байки

Собственно, вот отсюда происходит название: ацтекский, потому что как пирамиды ацтеков, и diamond, потому что это слово употребляется в значении "ромб" (ну, точнее, тоже квадрат, но повёрнутый на 45 градусов)

Victor Kleptsyn

М

12:54

Математические байки

Так вот, комбинаторный объект, с которым мы тут работаем, это разбиения этого бриллианта на доминошки — на прямоугольники 1x2.

Victor Kleptsyn

М

12:54

Математические байки

Кстати, цитируя коллег —

Victor Kleptsyn

М

12:55

Математические байки

q

qtasep 15.10.2019 18:23:46

Не знаю, когда там ребенка пора начинать учить математике, но современную теорию вероятностей я уже ему показываю (см. например тут https://en.wikipedia.org/wiki/Aztec_diamond - а 3D картинки можно увидеть, например, тут: http://math.mit.edu/~borodin/aztec.html). На русском языке есть обзор Е. Смирнова https://www.mccme.ru/free-books/dubna/smirnov-aztec.pdf

Victor Kleptsyn

М

12:57

Математические байки

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

Victor Kleptsyn

М

12:58

Математические байки

А именно — сначала (как на кружке) наложим на АБ шахматную раскраску:

Victor Kleptsyn

М

12:58

Математические байки

Victor Kleptsyn

М

12:59

Математические байки

Тогда каждая доминошка закрывает одну чёрную и одну белую клетку.

Victor Kleptsyn

М

13:03

Математические байки

Давайте договоримся, что если доминошка от чёрной клетки идёт
- вверх, то мы её красим в жёлтый цвет,
- вниз, то мы её красим в красный цвет,
- вправо, то мы её красим в зелёный цвет,
- влево, то мы её красим в синий цвет:

Victor Kleptsyn

М

13:03

Математические байки

Photo

221x62

Victor Kleptsyn

М

13:04

Математические байки

(В частности, горизонтальные доминошки так оказываются покрашены в "холодные" цвета, а вертикальные в "тёплые")

Victor Kleptsyn

М

13:05

Математические байки

Так вот — давайте посмотрим на то, как выглядит одно разбиение АБ порядка n на доминошки, случайно выбранное из всех возможных вариантов (я, правда, до сих пор не сказал, сколько их).

Victor Kleptsyn

М

13:05

Математические байки

Сначала — n=10:

Victor Kleptsyn

М

13:06

Математические байки

Victor Kleptsyn

М

13:06

Математические байки

И вторая попытка с n=10:

Victor Kleptsyn

М

13:06

Математические байки

Victor Kleptsyn

М

13:06

Математические байки

Теперь n=50:

Victor Kleptsyn

М

13:06

Математические байки

Victor Kleptsyn

М

13:06

Математические байки

И наконец, n=200:

Victor Kleptsyn

М

13:07

Математические байки

Victor Kleptsyn

М

13:11

Математические байки

И вот он, красивый эффект — "теорема о полярном круге": снаружи от вписанной окружности все доминошки оказываются "заморожены".
Её доказали Jockush, Propp и Shor; см. — https://arxiv.org/abs/math/9801068

Victor Kleptsyn

М

13:13

Математические байки

Кстати, у них в работе есть и картинка без раскраски:

Victor Kleptsyn

М

13:13

Математические байки

Victor Kleptsyn

М

13:14

Математические байки

Видно, что без цвета всё гораздо менее наглядно...

Victor Kleptsyn

М

13:16

Математические байки

Возвращаясь к ацтекскому бриллианту — одну красивую картинку мы увидели, но вот что за нею стоит?
Оказывается, что стоит довольно много.

Victor Kleptsyn

М

13:17

Математические байки

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

Victor Kleptsyn

М

13:23

Математические байки

К равновероятному выбору мы ещё вернёмся — а пока посмотрим, сколько их должно быть.

Victor Kleptsyn

М

13:27

Математические байки

Во-первых, сделаем оценку сверху: площадь АБ порядка n равна 2n(n+1); половина её это чёрные клетки, так что их n(n+1). Собственно, если нарисовать первые сколько-то АБ, то это видно "на глаз":

Victor Kleptsyn

М

13:28

Математические байки

Victor Kleptsyn

М

13:29

Математические байки

(picture credit: картинка из статьи в Images de Maths, которую я упоминал выше)

Так вот — разбиение кодируется набором направлений доминошек, закрывающих эти клетки. Значит, всего разбиений не больше, чем
4^{n(n+1)}.

Victor Kleptsyn

М

13:33

Математические байки

Во-вторых, сделаем теперь оценку снизу. В ацтекский бриллиант порядка n=2m-1 (и n=2m) можно вписать честный квадрат размера 2mx2m, "срезав уголки".
Уголки можно разрезать на доминошки просто параллельно линии отреза — а квадрат размера 2mx2m разрезать на m^2 квадратов размера 2x2.

Victor Kleptsyn

М

13:34

Математические байки

Каждый из этих квадратов разрезается на доминошки двумя способами — и вот мы получили оценку снизу как 2^{m^2}, то есть примерно как 2^{n^2/4}.

Victor Kleptsyn

М

13:35

Математические байки

И оценка сверху, и оценка снизу экспоненциальные по площади АБ. То есть естественно ожидать, что асимптотика будет exp(c n^2), где c — некоторая, пока неизвестная нам, константа.

Victor Kleptsyn

М

13:37

Математические байки

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

Victor Kleptsyn

М

13:39

Математические байки

Игрушечный пример — тоже разбиения на доминошки, но прямоугольника 2xn. Упражнение: их количество это (n+1)-е число Фибоначчи.
Учитывая то, как растут числа Фибоначчи — энтропией будет логарифм золотого сечения.

Victor Kleptsyn

М

13:41

Математические байки

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

Victor Kleptsyn

М

13:43

Математические байки

In reply to this message

Кстати, в качестве рекламы — (IMHO, очень хороший) текст Окунькова как раз о статистической физике: http://book.etudes.ru/toc/patternhappen/

Victor Kleptsyn

М

13:47

Математические байки

Но давайте вернёмся к собственно подсчёту разбиений. Ответ про их количество оказывается тоже удивительным (и вдвойне — что получается посчитать их точно, а не только найти асимптотику).

Victor Kleptsyn

М

13:48

Математические байки

Теорема (N. Elkies, G. Kuperberg, M. Larsen, J. Propp): Количество разбиений АБ порядка n равно 2^{n(n+1)/2}.

См.: https://arxiv.org/abs/math/9201305

Victor Kleptsyn

М

13:55

Математические байки

Собственно, трём взглядам на разбиения АБ и трём доказательствам этой теоремы и посвящена брошюра Е. Смирнова, что я упоминал — так что тут я дальше не пойду. Правда, покажу (без объяснения) одну из картинок — про модель "квадратного льда", с которой ацтекский бриллиант оказывается связанным:

Victor Kleptsyn

М

13:55

Математические байки

Victor Kleptsyn

М

13:56

Математические байки

Зато — нам этого ответа уже хватит, чтобы понять, что _угловые_ доминошки действительно должны быть ориентированы так, как предсказывает теорема о полярном круге:

Victor Kleptsyn

М

13:56

Математические байки

Victor Kleptsyn

М

13:57

Математические байки

Действительно, пусть мы закрыли угловую клетку горизонтальной доминошкой:

Victor Kleptsyn

М

13:57

Математические байки

Victor Kleptsyn

М

13:58

Математические байки

Тогда у клетки B остался только один сосед — так что и её придётся закрывать горизонтальной доминошкой:

Victor Kleptsyn

М

13:58

Математические байки

Victor Kleptsyn

М

13:58

Математические байки

А тогда и клетку C, и так далее: пошла "лесенка":

Victor Kleptsyn

М

13:58

Математические байки

Victor Kleptsyn

М

13:59

Математические байки

Более того, такая же лесенка пойдёт и вниз:

Victor Kleptsyn

М

13:59

Математические байки

Victor Kleptsyn

М

13:59

Математические байки

Victor Kleptsyn

М

13:59

Математические байки

Victor Kleptsyn

М

14:01

Математические байки

И в результате остаётся неразбитым опять АБ — но порядка (n-1). А у него разбиений (по той же теореме) 2^{n(n-1)/2}.
То есть _доля_ тех разбиений, где угловая доминошка ориентирована "не как надо", равна
2^{n(n-1)/2} / 2^{n(n+1)/2} = 1/2^n

Victor Kleptsyn

М

14:01

Математические байки

(потому что разница двух треугольных чисел в показателе как раз равна n).

Victor Kleptsyn

М

14:02

Математические байки

Понятно, что начиная с n=10, мы событий столь малой вероятности практически не увидим.

Victor Kleptsyn

М

14:06

Математические байки

Ну и это подсказывает общую точку зрения: мы видим такую картинку, как выше, не потому, что что-либо иное совсем запрещено — а потому, что их просто сильно меньше, чем всех.

Точно так же, как выкинуть 10 орлов из 100 подбрасываний не запрещено — но число способов это сделать сильно-сильно меньше, чем общее число вариантов.

Victor Kleptsyn

М

14:09

Математические байки

И кстати, это же подсказывает, что "наивные" методы построения случайного разбиения не пройдут: нельзя, например, взять какую-нибудь свободную клетку, подкинуть монетку, чтобы решить, куда пойдёт из неё доминошка, и перейти к следующей свободной клетке. Потому что при _равномерном_ выборе разбиения шанс, что доминошка в левом углу вертикальная, должен быть близок к 1. А вовсе не, скажем, 1/2.

Victor Kleptsyn

М

14:13

Математические байки

Более того, это же подсказывает, что нет у нас шансов и выбрать случайное разбиение, сначала перечислив их все: уже для n=10, их количество это
2^{n(n+1)/2} = 2^55, и получается совсем не тот объём информации, который можно хранить на компьютере (учитывая, что каждый ещё и задавать надо, и это не один бит — получается порядок эксабайт(!))...

Victor Kleptsyn

М

14:14

Математические байки

Нет, конечно, я не то, чтобы вру, но сгущаю краски — можно и считать, и генерировать "бегущим профилем", и это сразу нас вернёт в разумные количества. Но до n=200 даже так, "грубой силой", не дотянуться.

Victor Kleptsyn

М

14:30

Математические байки

Так как же можно нарисовать случайное разбиение?
(А картинки выше действительно были выбраны равновероятно среди всех — ну, точнее, равновероятно в пределах точности компьютерного датчика случайных чисел.)
Оказывается, для АБ есть сразу несколько способов это сделать — но прежде, чем их описывать, мне хочется дополнительно мотивировать разбиения на доминошки как объекта изучения.

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

Victor Kleptsyn

М

14:33

Математические байки

Пусть мы разбиваем область на треугольной решётке — скажем, просто большой правильный шестиугольник — на "доминошки"-ромбики из двух соседних треугольников:

Victor Kleptsyn

М

14:33

Математические байки

Victor Kleptsyn

М

14:34

Математические байки

Достаточно раскрасить ромбики в разбиении (а они тут будут трёх возможных направлений, так что красим в три цвета) —

Victor Kleptsyn

М

14:34

Математические байки

Victor Kleptsyn

М

14:35

Математические байки

— и картинка становится "кубиками" в трёхмерном пространстве (собранными в углу комнаты).

Victor Kleptsyn

М

14:45

Математические байки

Тут уже можно и сделать аллюзию на диаграммы Юнга (такие же кубики в углу, но двумерной комнаты, они же число способов разбить число n в сумму натуральных слагаемых без учёта порядка) — и вспомнить формулу МакМагона для подсчёта числа таких "заполнений кубиками" в комнате размера axbxc (мне, опять-таки, вспоминается — другая — брошюра Е. Смирнова, https://www.mccme.ru/free-books/dubna/smirnov-asm.pdf , см. лекцию 3 ) — ну, в общем, я же уже говорил про годовой курс?

Victor Kleptsyn

М

14:45

Математические байки

Но мне из этой картинки хочется вытащить "функцию высоты" и вообще трёхмерный взгляд на неё.

Victor Kleptsyn

М

14:48

Математические байки

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

Victor Kleptsyn

М

14:49

Математические байки

Пусть у нас есть разбиение на ромбики на треугольной решётке. Если в нём есть шестиугольник со стороной 1, разбитый на три ромбика одним способом — можно его переразбить другим. Назовём это "элементарной перестройкой".

Victor Kleptsyn

М

14:50

Математические байки

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

Victor Kleptsyn

М

14:53

Математические байки

"Доказательство". Трёхмерный взгляд позволяет посмотреть на картинку, как просто на добавление/убирание кубика. Будем убирать кубики "от самого верхнего", пока не дойдём от любого исходного разбиения до состояния "пустая комната".

Victor Kleptsyn

М

14:55

Математические байки

От любого состояния дошли до одного и того же, минимального — значит, от любого можно дойти до любого другого.
(Я взял слово "доказательство" в кавычки — потому что это для настоящей комнаты легко сказать, что означает "пустая комната", а так нужно действовать чуть более аккуратно. Но давайте считать, что тут я всё заметаю под ковёр.)

Victor Kleptsyn

М

14:57

Математические байки

То же самое можно сделать и для разбиений (опять таки, областей без дырок) на квадратной решётке — а в качестве элементарной перестройки выступает переразбиение квадрата 2x2.

Victor Kleptsyn

М

15:01

Математические байки

Так вот, возвращаясь к ацтекскому бриллианту. Вообще, картинки, которые я показывал, нарисованы с использованием специфики именно ацтекского бриллианта. А именно, одно из доказательств теоремы о числе разбиений позволяет ещё и по честно-равномерному разбиению АБ порядка (n-1), дополнительно несколько раз подбросив монетку, получить честно-равномерное разбиение АБ порядка n. И завязано это как раз на функцию высоты (которая достраивает картинку до трёхмерной) — рассматриваемую в одном случае в чёрных, а в другом в белых вершинах. Но в эту технику я не пойду, именно потому, что она завязана на конкретику АБ.

Victor Kleptsyn

М

15:02

Математические байки

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

Victor Kleptsyn

М

15:03

Математические байки

А именно: рассмотрим граф, вершинами которого являются _все_ разбиения АБ, а рёбра соединяют разбиения, отличающиеся на элементарную перестройку.

Victor Kleptsyn

М

15:04

Математические байки

Этот граф, конечно, объект чисто абстрактный: для порядка n=100 у него 2^{5050} вершин, что немного многовато.

Victor Kleptsyn

М

15:05

Математические байки

Зато рёбер из каждой вершины выходит не так много — не больше 2n^2=20.000, что вполне компьютерно-реалистично.

Victor Kleptsyn

М

15:05

Математические байки

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

Victor Kleptsyn

М

15:09

Математические байки

Так вот — если так "побродить" достаточно долго, то получается (почти) равновероятное распределение на том, куда мы в принципе можем прийти. И это и есть один из способов генерации случайного разбиения. Но тут нужно быть аккуратным и в том, как генерировать, и в том, когда останавливаться (а ещё есть красивые слова "coupling from the past", которые позволяют гарантировать, что получаемое разбиение совсем честно случайно).

Victor Kleptsyn

М

15:09

Математические байки

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

Victor Kleptsyn

2 December 2019

М

13:20

Математические байки

In reply to this message

Добрался до Лиона, и теперь могу показать кусочки их математической фрески в лучшем качестве:

Victor Kleptsyn

М

13:20

Математические байки

Воздушный шар с расслоением Хопфа —

Victor Kleptsyn

М

13:20

Математические байки

Victor Kleptsyn

М

13:21

Математические байки

Солнце, универсально накрывающее сферу без трёх точек —

Victor Kleptsyn

М

13:21

Математические байки

Victor Kleptsyn

М

13:21

Математические байки

Дикий узел —

Victor Kleptsyn

М

13:22

Математические байки

Victor Kleptsyn

М

13:31

Математические байки

In reply to this message

Кстати — вот одно из совершенно потрясающих рассуждений в комплексном анализе (увы — для тех, кто его уже немного знает), теорема Пикара. Целая (голоморфная на C) функция, не принимающая хотя бы два значения, константа.
Потому что — универсальная накрывающая над C без двух точек это диск. Непрерывное отображение можно поднять до отображения универсальных накрывающих. А универсальная накрывающая над C без двух точек (=над сферой без трёх) это диск.
И если мы начали с целой функции, бьющей в C без двух точек — то получаем отображение из C в диск, то есть ограниченную целую функцию. А ограниченная целая функция — константа.

Victor Kleptsyn

3 December 2019

М

12:51

Математические байки

Часы в чайной комнате UMPA тоже соответствующие —

Victor Kleptsyn

М

12:51

Математические байки

Victor Kleptsyn

М

12:53

Математические байки

In reply to this message

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

Victor Kleptsyn

М

13:00

Математические байки

Вообще, такие процессы называются _цепями Маркова_. "Такие" — это значит, что есть множество состояний, для каждого состояния задано, с какой вероятностью в какое состояние мы переходим, причём эта вероятность зависит только от того, где мы сейчас, но не от того, где мы были раньше. Ну и — чтобы процесс был задан полностью, нужно ещё задать начальное распределение (где и с какой вероятностью мы начинаем; например, можно начать просто в заданной точке).

Victor Kleptsyn

М

13:01

Математические байки

"Игрушечный пример" тут — лягушки, прыгающие между сушей и болотом. Допустим, что лягушка на суше понимает, что ей там плохо, и всегда прыгает в болото. А лягушкам в болоте интересно, что там на суше, и каждая из них решает, остаться там или рискнуть выползти на сушу, с вероятностью 1/2.

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

Victor Kleptsyn

М

13:01

Математические байки

Victor Kleptsyn

М

13:10

Математические байки

Невооружённым глазом видно, что распределение лягушек сошлось к соотношению "2/3 в болоте, 1/3 на суше", которое за один шаг переходит в себя. Такое распределение называется _стационарным_.

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

Victor Kleptsyn

М

13:22

Математические байки

Слово "стационарный" здесь можно читать просто как аналог слова "инвариантный"/"сохраняющийся операцией", но правильнее так: если взять эту меру в качестве уже начального распределения, то процесс получается инвариантен относительно сдвига по времени. И тут могло бы быть ответвление в сторону космологии, Фридмана, стационарных/нестационарных моделей Вселенной и нетривиальности понимания того, что Вселенная может быть нестационарной, но я, боюсь, всё-таки не готов его писать менее пунктирно и при этом не рисковать соврать более допустимого. :)

Victor Kleptsyn

М

13:22

Математические байки

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

Victor Kleptsyn

М

13:24

Математические байки

Действительно: если вероятность каждой вершины v равна d(v)/Z, где Z — сумма степеней всех вершин (то есть удвоенное число рёбер, что, впрочем, неважно), то для каждого ребра за один шаг по нему в каждую из сторон прыгает одна и та же масса "лягушек" — а именно, 1/Z. Значит, в каждой вершине сколько было, столько и осталось.

Victor Kleptsyn

М

13:30

Математические байки

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

Victor Kleptsyn

М

13:32

Математические байки

Но условия проверять нужно — а именно, нужно бороться с двудольностью графа (а то при хождении по кубу, если мы начали в чёрной вершине, то мы каждый чётный ход сможем быть только в чёрной вершине, а не в любой вообще).

Victor Kleptsyn

М

13:37

Математические байки

Починим сразу и то, и другое — добавлением фальшивых рёбер. Пусть мы знаем, что у нас всегда меньше D рёбер. Тогда можно сделать так: кинуть кубик с D гранями — если выпало число от 1 до d, где d степень текущей вершины, то перейти по соответствующему ребру, а если больше, то остаться на месте.

Victor Kleptsyn

М

13:47

Математические байки

Опять-таки, игрушечный пример — 100-мерный куб {0,1}^100. Его вершины — все возможные 2^100 последовательностей 0 и 1, и это совершенно "наш" случай, что все перечислить нельзя.

Конечно, можно просто подкинуть монетку 100 раз (и это как раз пример, аналогичный ацтекскому бриллианту — когда именно для данного графа, из-за его специфики, есть быстрый способ выбрать случайную вершину) — но допустим, что мы это сделать не догадались.

Victor Kleptsyn

М

13:51

Математические байки

Начав в конкретной точке (например, (0,...,0)) — мы на каждом шагу с вероятностью 1/101 переходим по каждому из возможных рёбер, а ещё с вероятностью 1/101 остаёмся на месте. Иными словами, мы либо меняем один из разрядов нашего 100-значного двоичного слова, либо (с небольшой вероятностью) не делаем ничего.

После того, как мы сделаем такое где-нибудь 10000 раз, каждый разряд мы поменяли в среднем около сотни раз. И "ежу понятно" (хотя, конечно, надо доказывать!), что на такой куче "перещёлкиваний" мы получили уже почти-совсем-случайное распределение.

Victor Kleptsyn

М

16:58

Математические байки

Казалось бы, отсюда можно получить уже готовый рецепт генерации (почти) случайного разбиения ацтекского бриллианта. А именно: мы знаем, что граф с вершинами-разбиениями связен относительно перестроек квадратиков. Берём какое-нибудь фиксированное начальное разбиение, например, просто все доминошки ставим вертикально. И на каждом шаге выбираем случайный квадрат 2x2. Если его можно перестроить — перестраиваем. Если нельзя — не трогаем. Как раз получается добавление фальшивых рёбер (ибо теперь у нас из каждой вершины исходит одно и то же их количество — просто многие ведут в неё же).

Victor Kleptsyn

М

16:59

Математические байки

Вот пример такой симуляции (за эти картинки спасибо И. Батманову и К. Люборту):

Victor Kleptsyn

М

17:00

Математические байки

Victor Kleptsyn

М

17:00

Математические байки

первая перестройка —

Victor Kleptsyn

М

17:00

Математические байки

Victor Kleptsyn

М

17:00

Математические байки

вторая —

Victor Kleptsyn

М

17:00

Математические байки

Victor Kleptsyn

М

17:01

Математические байки

третья —

Victor Kleptsyn

М

17:01

Математические байки

Victor Kleptsyn

М

17:01

Математические байки

20-я —

Victor Kleptsyn

М

17:01

Математические байки

Victor Kleptsyn

М

17:02

Математические байки

(кстати, видно, что один из квадратиков "развернулся обратно")

Victor Kleptsyn

М

17:02

Математические байки

Victor Kleptsyn

М

17:02

Математические байки

40-я — пары горизонтальных доминошек посередине уже порождают вертикальные другой чётности

Victor Kleptsyn

М

17:02

Математические байки

Victor Kleptsyn

М

17:03

Математические байки

это уже 100-я — волна перестроек "расползается"

Victor Kleptsyn

М

17:03

Математические байки

Victor Kleptsyn

М

17:03

Математические байки

Это была 500-я

Victor Kleptsyn

М

17:03

Математические байки

1500-я:

Victor Kleptsyn

М

17:03

Математические байки

Victor Kleptsyn

М

17:03

Математические байки

3000-я:

Victor Kleptsyn

М

17:03

Математические байки

Victor Kleptsyn

М

17:03

Математические байки

6000-я:

Victor Kleptsyn

М

17:03

Математические байки

Victor Kleptsyn

М

17:04

Математические байки

И при взгляде на всё это должен появиться вопрос — а когда пора остановиться? _Сколько именно_ нужно ждать, чтобы можно было сказать, что да, мы получили что-то "почти случайное"?

Victor Kleptsyn

М

17:11

Математические байки

Вопрос из этой же серии — а сколько раз нужно перетасовывать колоду, чтобы порядок карт в ней можно было считать случайным? Народ вполне серьёзно этим вопросом занимался — и я тут ограничусь ссылкой на текст Американского Математического Общества:
http://www.ams.org/publicoutreach/feature-column/fcarc-shuffle

Victor Kleptsyn

М

17:15

Математические байки

То, что он может быть сильно нетривиальным, можно увидеть на примере того же многомерного куба. Скажем, понятно, что бессмысленно делать число итераций меньшее, чем диаметр графа — мы тогда просто не сумеем от любой вершины дойти до любой. Но оказывается, что иногда характерное "время перемешивания" (собственно, оно так и называется, "mixing time") — гораздо больше.

Victor Kleptsyn

М

17:16

Математические байки

Давайте возьмём два куба, один 100-мерный, другой 200-мерный. И соединим в них лишь одну вершину одного с одной вершиной другого. (Например, "все единицы" со "всеми единицами".)

Victor Kleptsyn

М

17:23

Математические байки

Тогда случайное блуждание, начавшееся в 100-мерном кубе (например, в точке "все нули"), будет там блуждать как минимум до первого попадания в точку перехода в 200-мерный куб. Соответственно, на временах, заметно меньших 2^100 итераций, мы будем видеть только пренебрежимо малую (2^100 по сравнению с 2^200) долю вершин нашего графа.
(А если 100 в этом примере мало — возьмём 1000, и можно будет написать "за всё время существования Вселенной".)
Ну и, собственно, проблема явно видна — "перешейки". Вопрос только в том, что с ними делать.

Victor Kleptsyn

М

17:33

Математические байки

И ещё два слова я ещё скажу, а пока, в качестве иллюстрации сложности — большая книга, которая так и называется: "Markov chains and mixing times" — https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

Victor Kleptsyn

М

17:33

Математические байки

Victor Kleptsyn

М

17:42

Математические байки

In reply to this message

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

Victor Kleptsyn

М

17:43

Математические байки

Victor Kleptsyn

М

17:43

Математические байки

(Каюсь, не помню, чья это иллюстрация — но не моя. У Кеньона есть похожая, но чуть-чуть в других цветах — http://www.math.brown.edu/~rkenyon/gallery/bppsim.gif )

Victor Kleptsyn

М

17:50

Математические байки

Кстати: можно пытаться брать не равновероятное — а как-то взвешенное распределение. Например, раз уж мы всё равно смотрим на эту картинку как на кубики — зафиксировать объём. Или (что приводит к очень близкому результату) — сказать, что пусть вероятность разбиения (то есть пирамидки из кубиков) пропорциональна параметру q в степени количество кубиков. (И тут опять начинается статистическая физика, exp(-\beta H) и всё такое). И получим мы, вместо теоремы о полярном круге — предельную форму угла кубического монокристалла:

Victor Kleptsyn

М

17:50

Математические байки

Victor Kleptsyn

М

17:51

Математические байки

(Picture credit : A. Okounkov)

Victor Kleptsyn

М

17:59

Математические байки

Обещанные несколько слов:
— Во-первых, у нас тут выше вырисовалась связка (всё связано со всем) "случайное блуждание—время перемешивания—спектр оператора Лапласа—изопериметрическое неравенство".
Ну, почти вырисовалась — ещё нужно сказать, что за случайное блуждание как раз оператор Лапласа и отвечает, а за "бутылочные горлышки" отвечает изопериметрическое неравенство.

Victor Kleptsyn

11 December 2019

М

20:26

Математические байки

In reply to this message

(Прошу прощения — такой большой перерыв не планировался...)
Так вот, во-вторых, тут неподалёку живут слова "концентрация меры".

Victor Kleptsyn

М

20:27

Математические байки

А именно: как совсем широко известно, стомерные арбузы покупать не стоит. Ибо состоят они в основном из кожуры: даже если толщина кожуры это 5% — доля съедобной части в арбузе будет 0.95^100 ~ e^{-5} ~ 0.0067.

Victor Kleptsyn

М

20:27

Математические байки

А вот как чуть менее широко известно, многомерный арбуз состоит в основном из своего экватора. Из какого? Да из любого!

Victor Kleptsyn

М

20:28

Математические байки

А именно — возьмём случайно выбранную точку (x_1,...,x_n) на n-1-мерной единичной сфере.
Посмотрим на первую координату, x_1.
Её модуль — это и есть расстояние до экваториальной сферы, {x_1=0}.

Victor Kleptsyn

М

20:29

Математические байки

Но поскольку сумма квадратов всех n координат равна единице,
x_1^2+...+x_n^2=1,
то "естественно ожидать", что на квадрат каждой координаты в среднем приходится по 1/n. То есть x_1 (который вообще-то принимает значения от -1 до 1) "обычно" будет иметь порядок 1/sqrt{n}.

Victor Kleptsyn

М

20:29

Математические байки

И это таки да правда — и более того, при увеличении n распределение произведения \sqrt{n}*x_1 сходится к гауссову нормальному распределению N(0,1) — тому самому, которое самое замечательное в теории вероятностей, и сходимость к которому утверждает ЦПТ.

Victor Kleptsyn

М

20:38

Математические байки

Наиболее простой способ это увидеть такой. Давайте возьмём n независимых, распределённых как N(0,1) случайных величин \xi_k. Тогда у каждой из них плотность это (1/sqrt{2π}) * exp(-x^2/2), а совместная плотность в R^n — это их произведение, то есть
1/(2π)^{n/2} * exp(-r^2/2), где r^2=x_1^2+...+x_n^2 — радиус.

Victor Kleptsyn

М

20:39

Математические байки

Тогда это распределение сферически симметричное: плотность в R^n у него зависит только от расстояния до начала координат. Значит, если мы спроецируем выбранную таким образом точку на единичную сферу — получится равномерно распределённая точка на сфере. И её первая координата будет равна
x_1=\xi_1/r.

Victor Kleptsyn

М

20:39

Математические байки

Но r^2=x_1^2+...+x_n^2 — это сумма n _независимых_ одинаково распределённых случайных величин. И как нас учит закон больших чисел, r^2/n с очень большой вероятностью близко к математическому ожиданию любой из них — то есть к единице.

Victor Kleptsyn

М

20:40

Математические байки

То есть r это "почти константа \sqrt{n}". Ну а исходная случайная величина \xi_1 была точно N(0,1).
Значит,
\sqrt{n}* x_1 = \xi_1 * (\sqrt{n}/r) —
почти N(0,1), и чем больше n, тем точнее это "почти".

Victor Kleptsyn

М

20:41

Математические байки

Вернёмся теперь к словам "концентрация меры". А именно — пусть на n-мерной единичной сфере задана какая-то 1-липшицева функция f (то есть такая, что |f(x)-f(y)|<|x-y|) — как в примере выше мы рассматривали функцию f(x_1,...,x_n)=x_1.

Victor Kleptsyn

М

20:42

Математические байки

Посмотрим на распределение её значений — на какой доле площади точек сферы она принимает какие значения. Оказывается (и это и есть эффект "концентрации меры"), что в основном эти значения очень сконцентрированы.
А именно — хоть (как, собственно, и для функции x_1) максимальное от минимального может отличаться на 2 (на диаметр сферы), на 95% площади принимаются значения, отличающиеся друг от друга на const/sqrt{n} (и на 99%, и на 99.9%, вопрос только в константе).

Victor Kleptsyn

М

20:43

Математические байки

Так что мера получается сконцентрированной, с характерным разбросом порядка 1/\sqrt{n}.
Более того, функция x_1 оказывается, в каком-то смысле [я тут чуть-чуть привираю — но чуть ниже уточню], "самым разбросанным" примером.

Victor Kleptsyn

М

20:45

Математические байки

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

Victor Kleptsyn

М

20:45

Математические байки

И будем от него отходить вверх и вниз и смотреть, как "ужимаются" области {x: f(x)>a} и {x: f(x)<a} соответственно.

Victor Kleptsyn

М

20:49

Математические байки

Поскольку функция 1-липшицева — скорость ужимания не меньше, чем площадь "поверхности уровня" {f(x)=a}. Потому что если мы возьмём \eps-окрестность этой поверхности — то значения в ней в силу 1-липшицевости не выходят за предел [a-\eps, a+\eps]. Так что при переходе от {f(x)>a} к {f(x)>a+\eps} мы, например, смотрящую "внутрь" часть этой \eps-окрестности теряем, а у неё объём это примерно площадь {f(x)=a}, умноженная на \eps ("площадь основания на высоту").

Victor Kleptsyn

М

20:50

Математические байки

А площадь поверхности {f(x)=a} можно сравнить с отсекаемым ею объёмом {f(x)>a} — и изопериметрическое неравенство скажет, что нельзя отрезать "большой" объём маленькой площадью.

Victor Kleptsyn

М

20:51

Математические байки

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

Victor Kleptsyn

М

20:52

Математические байки

Более того, на самом деле на сфере (что очень естественно) наибольший объём, который можно отрезать данной площадью, это "полярная шапка".

Victor Kleptsyn

М

20:52

Математические байки

Поэтому самое медленное убывание, которое бывает, будет как раз для функции x_1. А для неё мы знаем, что даже она сконцентрирована с разбросом ~1/\sqrt{n}. Ура, победа!

Victor Kleptsyn

М

20:53

Математические байки

[И это как раз то место, где я не сильно, но заметно, привираю, путая расстояния "в R^n" и "по поверхности сферы". Чтобы мои слова стали совсем правдой, нужно брать расстояния по поверхности, произнести слова "риманова метрика", и брать функцию arcsin x_1. Те, кого они не пугают — вот после этого всё совсем почти честно]

Victor Kleptsyn

М

20:56

Математические байки

In reply to this message

С другой стороны, возвращаясь, — хоть рассуждение для разброса мы закончили, вместо явного счёта сказав, что "широта" arcsin x_1 это самая разбросанная функция — вообще-то нам достаточно было бы иметь "хорошее" изопериметрическое неравенство (какое максимальное отношение площади поверхности к ограничиваемому ей объёму). Нужно было только его получить/написать.

Victor Kleptsyn

М

20:56

Математические байки

Константа, которую можно в нём поставить, называется константой Чигера —
https://en.wikipedia.org/wiki/Cheeger_constant#Definition (и, кстати, есть она и для графов — https://ru.wikipedia.org/wiki/Константа_Чигера_(теория_графов) )

Victor Kleptsyn

М

20:56

Математические байки

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

Victor Kleptsyn

13 December 2019

М

19:10

Математические байки

In reply to this message

Кстати. Из всё того же многомерного гауссового распределения хорошо получается формула для площади поверхности единичной сферы (и объёма единичного шара) в n-мерном пространстве.

Victor Kleptsyn

М

19:14

Математические байки

Потому что — давайте рассмотрим его плотность в R^n. Только, для простоты счёта, растянем всё в корень из двойки раз. Тогда плотность по одной координате будет просто e^{-x^2}, делённой (нормировка на интеграл 1) на корень из π.

Victor Kleptsyn

М

19:14

Математические байки

А совместная —
\rho(x_1,\dots,x_n) = \frac{1}{\sqrt{π}^n} \exp(-x_1^2-\dots-x_n^2),

Victor Kleptsyn

М

19:17

Математические байки

Photo

371x58

Victor Kleptsyn

М

19:17

Математические байки

Эта плотность сферически симметрична. И интеграл от неё равен 1 (это же плотность вероятностного распределения). Но давайте его найдём "в сферических координатах" — а точнее, просто порежем всё пространство на "сферические слои".
Если мы возьмём разницу шаров с радиусами r и r+dr, то её объём примерно равен c_n r^{n-1} dr, где c_n — площадь поверхности единичной сферы в R^n.

Victor Kleptsyn

М

19:23

Математические байки

А подынтегральная функция на таком слое равна
π^{-n/2} exp(-r^2). Поэтому интеграл от плотности равен интегралу от c_n r^{n-1}* π^{-n/2} exp(-r^2) dr,

Victor Kleptsyn

М

19:26

Математические байки

Photo

430x54

Victor Kleptsyn

М

19:30

Математические байки

А сделав в этом интеграле замену R=r^2, и вынеся константу, мы получим как раз ту самую гамма-функцию Эйлера, которая обобщает факториал:

Victor Kleptsyn

М

19:30

Математические байки

Photo

414x47

Victor Kleptsyn

М

19:38

Математические байки

Ну вот мы и получили (раз интеграл должен равняться единице), что
c_n Г(n/2) /(2 π^{n/2}) = 1,
откуда
c_n = (2 π^{n/2}) / Г(n/2).

Victor Kleptsyn

М

19:38

Математические байки

Photo

112x54

Victor Kleptsyn

М

19:40

Математические байки

А объём единичного шара, соответственно, в n раз меньше (можно сказать, "потому что пирамида из центра", а можно проинтегрировать r^{n-1} и получить r^n/n):

Victor Kleptsyn

М

19:40

Математические байки

Photo

281x52

Victor Kleptsyn

М

19:42

Математические байки

И вот в этом виде — "π в степени n/2, поделить на n/2 факториал" — я эту формулу когда-то давно узнал, и доказывал индукцией по отдельности для чётных и для нечётных n.
А рассуждение с гауссовой плотностью (объясняющее, почему чётные и нечётные n так хорошо объединились в одну формулу) узнал только гораздо позднее...

Victor Kleptsyn

М

19:54

Математические байки

Ну и в завершение — вспомнил я эту формулу тут совершенно не случайно. Потому что если мы захотим посмотреть, как устроено изопериметрическое неравенство на единичной сфере в R^n — какое наименьшее отношение площади к отсекаемому ею объёму (считая, что отсекается та часть, которая меньше половины сферы), то не очень сложно поверить, что это будет как раз отношением для экватора.

Victor Kleptsyn

М

19:54

Математические байки

А тогда оно равно c_{n-1}/(c_n/2). То есть мы видим отношение гамма-функций в точках, отличающихся на (1/2). Но раз Г(m+1)=mГ(m), то очень естественно ожидать, что отношение Г(m+1/2) и Г(m) будет вести себя, как корень из m.

Victor Kleptsyn

М

19:55

Математические байки

Ну и, соответственно, изопериметрическая константа для n-мерной сферы ведёт себя, как корень из n/2 (ибо там половинный аргумент).

Victor Kleptsyn

М

19:57

Математические байки

In reply to this message

Что как раз и соответствует тому, что x_1 имеет разброс порядка 1/sqrt{n} (у соответствующего дифференциального уравнения решением будет экспонента с изопериметрической константой в показателе).

Victor Kleptsyn

14 December 2019

М

21:09

Математические байки

Начиная рассказ про асимптотическую комбинаторику, я надеялся ацтекский бриллиант проскочить быстро, и перейти к другим красивым картинкам, а в результате там надолго застрял. Так что давайте я волевым решением перейду к другому, менее известному примеру — Random Sorting Networks. А потом вернусь и доскажу остальное.

Итак, Random Sorting Networks. Допустим, что у нас в ряд выстроено n тяжёлых чемоданов. Но мы вдруг обнаружили, что нужно их переставить в обратном порядке. А единственная операция, которая нам доступна, это взять два соседних чемодана, и поменять их местами.

Сколько нам понадобится операций? Несложно видеть, что минимум n(n-1)/2, число беспорядков.
Потому что в лучшем случае каждая операция уменьшает число беспорядков на 1 — ну а отсортировать за такое число действий можно, например, "пузырьком".

Victor Kleptsyn

М

21:10

Математические байки

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

Victor Kleptsyn

М

21:10

Математические байки

Как выбрать равновероятно — отдельная красивая история: их столько же, сколько способов получить диаграмму Юнга в форме равнобедренного прямоугольного треугольника, добавляя к пустой диаграмме по одной клетке за раз. (Это называется Edelman-Greene's bijection.) Но туда мы сейчас не пойдём.

Victor Kleptsyn

М

21:11

Математические байки

Так вот — давайте посмотрим на случайно выбранную сортировку, когда n достаточно большое. Вот, взятый из статьи Angel, Holroyd, Romik, Virag, "Random Sorting Networks" ( https://www.sciencedirect.com/science/article/pii/S0001870807001545 ) пример для n=6:

Victor Kleptsyn

М

21:11

Математические байки

Victor Kleptsyn

М

21:13

Математические байки

Тут выделена траектория, по которой движется чемодан номер 3, и отмечены места, где мы выполняли нашу операцию. Но пока ничего красивого не видно; это потому что n у ещё маленькое!

А вот такая у них получается красивая картина, если взять n=2000, и нарисовать (в соответствующем масштабе по осям) траектории отдельных чемоданов —

Victor Kleptsyn

М

21:13

Математические байки

Victor Kleptsyn

М

21:13

Математические байки

Правда ведь, напоминает синусоиды?

Victor Kleptsyn

М

21:15

Математические байки

А ещё можно посмотреть на то, как будут устроены графики перестановок (при фиксированном моменте времени, какой чемодан на каком месте стоит). Вот, к примеру (опять из той же статьи) график перестановки, которая наблюдается после половины всех операций:

Victor Kleptsyn

М

21:16

Математические байки

Victor Kleptsyn

М

21:17

Математические байки

Явно проглядывает круг — но при этом плотность ближе к краям, так, как если бы это была равномерная мера на сфере в трёхмерном пространстве (x,y,z) — которую спроецировали на плоскость (x,y).

Victor Kleptsyn

М

21:19

Математические байки

А что будет в другие моменты времени? Естественно считать параметром t долю от общего числа N выполненных операций; и вот картинка опять же из их работы —

Victor Kleptsyn

М

21:19

Математические байки

Victor Kleptsyn

М

21:24

Математические байки

Начальный и конечный момент времени это начальное и итоговое расположение чемоданов, у которых графики — прямые. А в промежуточные моменты времени видны эллипсы — а синим показаны полученные уже тогда (11 лет назад, препринт ещё 2006-го — https://arxiv.org/abs/math/0609538v1 ) оценки.

Victor Kleptsyn

М

21:26

Математические байки

In reply to this message

Собственно — вот гипотезы из той работы, как раз это и утверждающие:

Victor Kleptsyn

М

21:27

Математические байки

Victor Kleptsyn

М

21:28

Математические байки

Мера, как при проекции —

Victor Kleptsyn

М

21:28

Математические байки

Victor Kleptsyn

М

21:34

Математические байки

Кстати — если рисовать гистограмму того, сколько операций было произведено в такое-то время в таком-то месте, то тоже получается красивая картина:

Victor Kleptsyn

М

21:34

Математические байки

Victor Kleptsyn

М

21:35

Математические байки

(иллюстрация из всё той же статьи.)
Ну и оттуда же —

Victor Kleptsyn

М

21:36

Математические байки

Victor Kleptsyn

М

21:37

Математические байки

Но ещё интересная история тут — это появление перестановочного многогранника, или пермутоэдра. А именно, давайте посмотрим на обратное отображение после m операций, то есть на набор "на каком месте стоит первый чемодан, на каком второй, ..., как каком n-й".
Это — перестановка, так что в этом векторе каждое из чисел 1,2,...,n встречается по одному разу. При этом одна операция меняет два соседних чемодана — так что какие-то два числа m и m+1 в этом векторе поменяются местами.

Victor Kleptsyn

М

21:38

Математические байки

Victor Kleptsyn

М

21:40

Математические байки

И это — переход из одной перестановки в другую на наименьшее возможное расстояние (корень из двух).

Так вот — выпуклый многогранник, вершины которого это всевозможные перестановки вектора (1,2,...,n), называется пермутоэдром, или перестановочным многогранником. Очевидно, что все эти точки лежат в одной плоскости "сумма координат равна 1+...+n", и на одной сфере "сумма квадратов координат равна 1^2+...+n^2".

Victor Kleptsyn

М

21:41

Математические байки

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

Victor Kleptsyn

16 December 2019

М

17:36

Математические байки

Раз уж всё равно сделана пауза — давайте я расскажу пару коротких баек.

Victor Kleptsyn

М

17:36

Математические байки

Первая — более стандартная, но кажется, не совсем общеизвестная, про чётности перестановок.

Обычно определение чётности перестановки f даётся как чётность числа беспорядков (т.е. пар i<j, для которых f(i)>f(j)) — после чего проверяется, что это же чётность числа транспозиций, в произведение которых f раскладывается.

Victor Kleptsyn

М

17:37

Математические байки

Что можно проверить напрямую (взять транспозицию, посмотреть, какие беспорядки она добавляет, какие убирает, и что чётность в итоге всегда меняется), но это немного муторно.

Victor Kleptsyn

М

17:37

Математические байки

А гораздо проще будет сначала рассмотреть разложение f в произведение не абы каких транспозиций, а только транспозиций соседних элементов (i,i+1).
Тогда умножение на такую транспозицию меняет число беспорядков ровно на 1 — как раз на пару (i,i+1).

Victor Kleptsyn

М

17:38

Математические байки

И поэтому чётность числа беспорядков у f совпадает с чётностью числу транспозиций вида (i,i+1), в произведение которых f раскладывается.

Значит, есть отображение sign(f) из перестановок в {1,-1}, которое корректно определено (ибо определение через беспорядки) и при этом гомоморфизм (ибо определение через чётность числа сомножителей).

Victor Kleptsyn

М

17:39

Математические байки

Остаётся проверить, что любая транспозиция нечётна — что проще всего увидеть, сказав, что любая транспозиция сопряжена транспозиции (1,2):
(i,j)=g*(1,2)*g^{-1},
где g — любая перестановка, такая, что g(i)=1, g(j)=2.

(Кстати: вот понимание, что "сопряжение отображением g это просто замена координат y=g(x)", каюсь, до меня в своё время тоже довольно медленно доходило...)

Ну а в g и в g^{-1} чётность числа транспозиций (i,i+1) одинаковая — так что всего число таких транспозиций в (i,j) нечётно. (Да, конечно, можно просто посчитать беспорядки. Но хотелось рассуждения "без единой выкладки".)

Victor Kleptsyn

М

17:39

Математические байки

Всё!

Victor Kleptsyn

М

17:40

Математические байки

===
Вторая байка — про теорию вероятностей. Вот тут — https://avva.livejournal.com/3242116.html , https://blog.tanyakhovanova.com/2019/11/my-new-favorite-probability-puzzle/ — обсуждается такая задача. Пусть два игрока, Алиса и Боб, одновременно и независимо играют на деньги с одинаковой начальной суммой в $100, каждую минуту ставя по доллару. Но у Алисы вероятность выигрыша 51%, а у Боба 49%. Известно, что в итоге оба разорились (остались без денег и прекратили игру); _при этом условии_ про кого более вероятно, что он разорился первым?

Victor Kleptsyn

М

17:40

Математические байки

Spoiler alert: я собираюсь обсуждать (неожиданный) ответ, если вдруг вы эту задачу не решали, она очень стоит того, чтобы над ней подумать.

Victor Kleptsyn

М

17:41

Математические байки

Ответ — равновероятно. Более того, оказывается, что процесс игры Алисы _при условии_ того, что она в конце концов разоряется, такой же, как процесс игры Боба. И это, мне кажется, удивительно!

Victor Kleptsyn

М

17:41

Математические байки

Давайте посмотрим, как этот процесс устроен. Для начала найдём вероятности r_n того, что Алиса разоряется, имея в начале n долларов.

r_0=1 (ибо тут уже всё).
Достаточно естественно (хотя это и надо доказывать — но мы в это поверим), что r_n<1 при всех n>0: шанс не разориться (а получить асимптотически-линейный рост) у Алисы есть, если у неё ещё осталось, на что играть.

Victor Kleptsyn

М

17:42

Математические байки

Теперь, если Алиса начинает играть с n долларами, её шанс разориться складывается из вероятности выиграть первую ставку и разориться после того, и проиграть и разориться после того:
r_n = p r_{n+1} + q r_{n-1},
где p=0.51 — её вероятность выигрыша.

Victor Kleptsyn

М

17:43

Математические байки

Это — линейное рекуррентное соотношение, и его решениями оказываются линейные комбинации геометрических прогрессий со знаменателями — корнями характеристического уравнения*; в данном случае — это уравнение px^2-x+q=0.

*) когда кратных корней нет; иначе там (в общей науке линейных рекуррентных соотношений) появляются "квазимногочлены" — произведения многочленов на экспоненты.

Victor Kleptsyn

М

17:43

Математические байки

Один корень у этого уравнения — 1, отвечающего решению-константе. Собственно, если бы p было меньше 1/2 (а мы ещё нигде p>1/2 не использовали), то мы этот корень и должны увидеть: вероятность разорения в этом случае — тождественная единица.

Victor Kleptsyn

М

17:44

Математические байки

А второй (например, из теоремы Виета, чтобы долго не считать) x=q/p.

Кстати, в качестве ответвления: случай честной монеты, p=q=1/2, это как раз случай кратного корня, и решения уравнения r_{n+1}-2r_n+r_{n-1}=0 это в точности все арифметические прогрессии. Но поскольку r_n это вероятности, такая арифметическая прогрессия остаётся на [0,1] при всех n>0, а ограниченная арифметическая прогрессия — константа. Значит, r_n=1 — игрок с честной монетой тоже разоряется с вероятностью 1 ("случайное блуждание на прямой возвратно"), и такое рассуждение — один из способов это увидеть.

Victor Kleptsyn

М

17:45

Математические байки

В нашем случае p>1/2 — не очень сложно поверить, что r_n будет стремиться к 0 с ростом n: чем больше у Алисы начальный запас денег, тем меньше её шанс разориться.

Victor Kleptsyn

М

17:45

Математические байки

Но раз r_n=a*1+b*x^n, то a=0, а из r_0=1 тогда следует b=1.
Так что вероятность разорения Алисы — это просто геометрическая прогрессия: r_n=x^n=(q/p)^n.

Victor Kleptsyn

М

17:47

Математические байки

Осталось понять, как при условии "Алиса разорилась" выглядит процесс её игры. Если в какой-то момент у неё n долларов, то шансы перейти в (n+1) и в (n-1) за один шаг равны соответственно p*r_{n+1}/r_n и q*r_{n-1}/r_n (а то, что их сумма равна 1 — это и было наше уравнение).

Victor Kleptsyn

М

17:47

Математические байки

Но у нас геометрическая прогрессия — поэтому r_{n+1}/r_n=x=q/p, а r_{n-1}/r_n=p/q.

Victor Kleptsyn

М

17:47

Математические байки

И поэтому эти вероятности равны
p*(q/p)=q и q*(p/q)=p соответственно — то есть игра Алисы _при условии разорения_ стала игрой Боба!

Victor Kleptsyn

М

17:51

Математические байки

И это хорошее место, чтобы чуть-чуть задуматься, "а почему". А есть ли хорошее объяснение, что вероятность разорения оказалась именно геометрической прогрессией? (Так-то мы сослались на рекуррентные уравнения, формально говоря, задействовав линейную алгебру... а проще можно?)
И ещё — если Алиса начинает с $n, то процесс её игры при условии достижения $0 (разорения) будет таким же, как и при условии достижения любого фиксированного уровня $k с k<n: это та же игра, но Алиса с самого начала откладывает $k "на дорогу домой" и на них не играет. То есть все такие условия приводят к одинаковому условному процессу. А почему?

Victor Kleptsyn

М

18:01

Математические байки

На самом деле это один и тот же вопрос, и на него есть разумный ответ. А именно — с одной стороны, чтобы разориться, Алисе нужно в какой-то момент иметь на руках $(n-1). С другой, после того, как Алиса эту сумму получила, её игра не зависит от того, что было раньше — так что
r_n = (вероятность от $n когда-нибудь достигнуть $n-1) * r_{n-1}.
И если обозначить эту вероятность "отступить на доллар" через x, то вот мы и получаем геометрическую прогрессию.

Victor Kleptsyn

М

18:04

Математические байки

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

Victor Kleptsyn

М

18:04

Математические байки

Ну и на этом я на сегодня прекращаю дозволенные речи.

Victor Kleptsyn

15 January 2020

М

13:32

Математические байки

Запоздалое — с Новым Годом!

Сегодняшняя байка — рассказ о подстановочных словах.
Давайте зададим вот такое отображение F на словах из букв А и Б: заменим одновременно каждую букву А на слово АБ, а каждую букву Б на А.
Например, F(БАА)=ААБАБ.

И будем это отображение итерировать, начав с однобуквенного слова w_1=А: рассмотрим последовательность его образов w_n=F(w_{n-1}).
Что у нас получится?

Victor Kleptsyn

М

13:32

Математические байки

Вот первые несколько образов:
w_1=А
w_2=АБ
w_3=АБА
w_4=АБААБ
w_5=АБААБАБА

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

Это слово
w = АБААБАБААБААБАБААБАБА...
называется словом Фибоначчи.
А что о нём можно сказать?

Victor Kleptsyn

М

13:33

Математические байки

Оказывается, очень много — а пройдя по этой дороге чуть-чуть дальше, можно получить вот такую красивую картинку, фрактал Рози
(picture credit: А. Я. Канель-Белов, И. В. Митрофанов):

Victor Kleptsyn

М

13:33

Математические байки

Victor Kleptsyn

М

13:42

Математические байки

Но это будет итоговая "светлая цель", к которой мы дойдём, а пока давайте начнём с совсем простого: посчитаем буквы. (Почему? Да просто потому, что если вдруг есть непонятный объект, так давайте его измерим, насколько получится, вдруг что интересное найдём.)

Victor Kleptsyn

М

13:42

Математические байки

In reply to this message

Сколько букв в словах w_1, w_2, w_3,...? Посчитав, видимо знакомую нам последовательность
1, 2, 3, 5, 8, ...

А сколько по отдельности букв А и Б?

Victor Kleptsyn

М

13:43

Математические байки

Victor Kleptsyn

М

13:43

Математические байки

Сразу видны числа Фибоначчи; а как бы это доказать?
Мы знаем, что следующее слово продолжает предыдущее, не получится ли что-то увидеть из этого?

Давайте посмотрим, что остаётся, если из нового слова убрать идущее перед ним:

Victor Kleptsyn

М

13:43

Математические байки

Victor Kleptsyn

М

13:43

Математические байки

Невооружённым глазом видно, что остаётся то слово, что было до того. То есть
w_{n+1} = w_n w_{n-1}.

И когда это написано, доказательство тоже мгновенно проводится по индукции, из базы либо АБА= АБ А,
либо даже АБ= А Б с формальным добавлением w_0=Б.

Victor Kleptsyn

М

14:33

Математические байки

In reply to this message

Теперь понятно, почему бесконечное слово называют "словом Фибоначчи": последовательность слов, которая к нему приводит, получается как раз из Фибоначчи-подобного соотношения.

Но давайте продолжим нашу деятельность по счёту букв. А именно, давайте посмотрим, сколько букв А и Б оказывается среди первых k букв слова Фибоначчи — и отметим соответствующую точку на плоскости (по оси абсцисс отложив буквы А, а по оси ординат буквы Б). Получится этакая "змейка": при добавлении одной буквы мы сдвинемся на расстояние 1.

Victor Kleptsyn

М

14:34

Математические байки

Victor Kleptsyn

М

14:41

Математические байки

Сразу кажется, что она очень хорошо "выдерживает направление". Кстати, коэффициент наклона того направления, в котором она идёт (если предположить, что он есть) — золотое сечение, точнее, обратная к нему величина 1/Ф (букв А больше, а традиционно Ф^2=Ф+1).
Потому что отношение последовательных чисел Фибоначчи стремится к золотому сечению, а мы знаем, что в подслове w_n количество букв А и Б это последовательные числа Фибоначчи.

Victor Kleptsyn

М

14:43

Математические байки

Но буквально так мы что-то говорим только про слова w_n — а они становятся всё длиннее и длиннее, и формально мы пока ничего не сказали про подслова длиной между |w_n| и |w_{n+1}|.

Victor Kleptsyn

М

17:16

Математические байки

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

Victor Kleptsyn

М

17:16

Математические байки

Victor Kleptsyn

М

17:17

Математические байки

А прямые, которые её ограничивают — проходят через точки (-1,0) и (0,-1); и вся эта змейка, какой бы длины она не была, не выходит за рамки этой весьма неширокой полосы.

Victor Kleptsyn

М

17:17

Математические байки

Но интереснее другое: давайте точки ещё и раскрасим.

Victor Kleptsyn

М

17:18

Математические байки

Если последняя посчитанная буква А — поставим красную точку, если Б — синюю. Вот, что получится:

Victor Kleptsyn

М

17:18

Математические байки

Victor Kleptsyn

М

17:18

Математические байки

Очень естественно, что красные точки в целом ниже/правее синих. Но что будет, если мы их спроецируем на перпендикулярный отрезок?

Victor Kleptsyn

М

17:18

Математические байки

Victor Kleptsyn

М

17:19

Математические байки

Victor Kleptsyn

М

17:19

Математические байки

Окажется, что проекции красных точек заметают один отрезок, проекции синих другой, и эти отрезки не пересекаются.

Victor Kleptsyn

М

17:20

Математические байки

In reply to this message

Теперь уже можно сказать (хотя пока конструкция "повиснет в воздухе"), откуда берётся фрактал Рози, который мы заявили, как цель.

Victor Kleptsyn

М

17:23

Математические байки

А именно — нужно взять другие правила замен, уже из трёх букв:
A -> AB
B -> AC
C -> A

И точно так же много-много раз их применять к исходному слову из одной буквы А. Все получающиеся слова будут префиксами одного и того же слова Трибоначчи
ABACABA...

Victor Kleptsyn

М

17:24

Математические байки

Если посчитать, сколько по отдельности букв A, B и C из первых k букв слова Трибоначчи — получится "змейка", растущая уже в трёхмерном пространстве:

Victor Kleptsyn

М

17:24

Математические байки

Victor Kleptsyn

М

17:25

Математические байки

И если спроецировать её на перпендикулярную её асимптотическому направлению плоскость, то точки заметут фигуру, которая разделится на проекции красных (А), синих (B) и зелёных (C) точек:

Victor Kleptsyn

М

17:25

Математические байки

Victor Kleptsyn

М

17:25

Математические байки

Вот это и есть тот самый фрактал Рози.

Victor Kleptsyn

М

17:27

Математические байки

То направление, в котором растёт эта змейка — собственное направление матрицы замен
(1 1 1)
(1 0 0)
(0 1 0),
применение которой пересчитывает буквы A, B и C в исходном слове в количество букв в его образе, с собственным значением, большим 1.

Victor Kleptsyn

М

17:29

Математические байки

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

Victor Kleptsyn

М

17:35

Математические байки

Мне остаётся договорить про то, как связано слово Фибоначчи с перекладываниями отрезка и поворотом окружности, но это я сделаю в следующий раз, а пока несколько ссылок:
- записки дубнинского курса о подстановочных словах + картинки: https://www.mccme.ru/dubna/2014/courses/kanel-mitrofanov.htm (ссылки на два PDFа внизу)
- ролик Numberphile примерно об этом же:
https://www.youtube.com/watch?v=fMJflV_GUpU
- дубнинская лекция А. П. Веселова:
http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=24811
- статья М. Л. Концевича в Кванте —
https://kvant.ras.ru/1985/07/ravnomernye_raspolozheniya.htm

Victor Kleptsyn

М

17:36

Математические байки

А на сегодня я на этом прекращаю дозволенные речи...

Victor Kleptsyn

3 February 2020

М

16:03

Математические байки

В прошлый раз я рассказывал о подстановочных словах и о слове Фибоначчи в частности — но совсем не рассказал о связанных с этим квазипериодических паркетах, а это простая и геометрическая история.

Victor Kleptsyn

М

16:03

Математические байки

Давайте проведём в правильном пятиугольнике три диагонали, и посмотрим, какие у нас получатся треугольники:

Victor Kleptsyn

М

16:04

Математические байки

Victor Kleptsyn

М

16:05

Математические байки

Оба треугольника, и красный, и синий — равнобедренные. Если взять короткую сторону за 1, то у синего стороны — это 1,1,Ф, а у красного — Ф,Ф,1, где Ф — золотое сечение.

Victor Kleptsyn

М

16:06

Математические байки

То, что Ф это именно золотое сечение, несложно увидеть из того, что большой треугольник BCD, который они образуют вместе, подобен синему. И получается (из стороны BD) классическое уравнение Ф^2=Ф+1.

Victor Kleptsyn

М

16:08

Математические байки

Но я не стал бы рассказывать столь классические (пару тысяч лет как) вещи, если бы тут не происходило чего-нибудь более интересного. А именно: пока мы из одного красного и одного синего треугольника сделали треугольник, подобный синему с коэффициентом Ф.
Так вот, из двух красных и одного синего треугольника можно сделать треугольник, подобный красному. С тем же самым коэффициентом подобия!

Victor Kleptsyn

М

16:08

Математические байки

Victor Kleptsyn

М

16:10

Математические байки

И увидеть это можно внутри всё того же правильного пятиугольника, проведя ещё одну диагональ (и мысленно сжав всё в Ф раз):

Victor Kleptsyn

М

16:10

Математические байки

Victor Kleptsyn

М

16:10

Математические байки

(Нижний синий треугольник это уже "меньший красный+меньший синий", и добавление ещё одного "меньшего красного" превращает его обратно в красный)

Victor Kleptsyn

М

16:11

Математические байки

Итак, из синих и красных треугольников можно сделать подобные им и в Ф раз большие синие и красные треугольники.

Victor Kleptsyn

М

16:11

Математические байки

А давайте повторять эту процедуру, например, начиная с одного красного треугольника —

Victor Kleptsyn

М

16:13

Математические байки

Victor Kleptsyn

М

16:13

Математические байки

Victor Kleptsyn

М

16:13

Математические байки

Victor Kleptsyn

М

16:14

Математические байки

И раз красный треугольник был в углу своего образа — то каждый следующий образ (по индукции) продолжает предыдущий.

Victor Kleptsyn

М

16:15

Математические байки

In reply to this message

Точно так же, как образы А при итерации подстановочного отображения продолжали друг друга.

Victor Kleptsyn

М

16:16

Математические байки

И точно так же, как из их итераций в пределе получалось бесконечное (вправо) слово — тут мы получим замощение угла в 36 градусов на плоскости:

Victor Kleptsyn

М

16:17

Математические байки

Victor Kleptsyn

М

16:19

Математические байки

А объединив 10 таких углов — получим и разбиение всей плоскости.

Victor Kleptsyn

3 February 2020

М

16:20

Математические байки

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

Victor Kleptsyn

М

16:22

Математические байки

Потому что количество красных и синих треугольников в образе красного или синего треугольника после n замен это пара последовательных чисел Фибоначчи (упражнение: докажите это!)

Victor Kleptsyn

М

16:23

Математические байки

А раз наше замощение режется на красные и синие треугольники — то оно режется и на, скажем, их 5-е образы, в каждом из которых отношение количеств К:С близко к Ф. А если недостаточно близко, то можно резать на 10-е образы, или на 20-е...

Victor Kleptsyn

М

16:23

Математические байки

Поэтому периодичным оно быть не может: Ф иррационально.

Victor Kleptsyn

М

16:25

Математические байки

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

Victor Kleptsyn

М

16:26

Математические байки

Формально — найдётся R, такое, что в любом круге радиуса R найдётся копия n-кратного образа красного треугольника.

Victor Kleptsyn

М

16:30

Математические байки

In reply to this message

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

Victor Kleptsyn

М

16:32

Математические байки

А вот обладающая таким же свойством мозаика Пенроуза (разбиение плоскости на ромбы двух типов, тоже квазипериодичное):

Victor Kleptsyn

М

16:32

Математические байки

Victor Kleptsyn

М

16:33

Математические байки

(picture source: Wikipedia, https://en.wikipedia.org/wiki/Penrose_tiling )

Victor Kleptsyn

М

16:43

Математические байки

Ну и, заговорив о квазипериодичных мозаиках, нельзя не упомянуть квазикристаллы. Есть такая наука — кристаллография. Собственно, занимающаяся изучением кристаллов, и недавно отпразновавшая своё столетие. (Кстати — вот этот небольшой мультфильм, который по этому случаю сделали, мне очень нравится: https://www.youtube.com/watch?v=uqQlwYv8VQI )

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

Victor Kleptsyn

М

16:45

Математические байки

Берём _моно_кристалл; и светим на него рентгеном. Можно считать, что каждый отдельный атом решётки рассеивает падающее излучение (волну) во все стороны. Но. Атомов-то много. И каждый рассеивает во все стороны.

Victor Kleptsyn

М

16:46

Математические байки

Но фаза при этом может сдвинуться:

Victor Kleptsyn

М

16:47

Математические байки

Victor Kleptsyn

М

16:47

Математические байки

(image credit: Wikipedia, https://en.wikipedia.org/wiki/Bragg%27s_law )

Victor Kleptsyn

М

16:51

Математические байки

Поэтому в "большинство" направлений в итоге ничего не уйдёт — если хоть один сдвиг фазы не кратен 2\pi, то все атомы изображают из себя лебедя, рака и щуку, и в сумме дают ноль. (Потому что такой сдвиг между атомами решётки можно повторять снова и снова, на то она и решётка, а тогда среднее должно быть инвариантно относительно соответствующего сдвига фазы, и это может быть только тождественный ноль.)

Victor Kleptsyn

М

16:55

Математические байки

Получается условие, что сдвиги фазы все должны быть кратными 2\pi. И в результате мы получаем на плёнке засвеченные отдельные точки — если аккуратно поразбираться, это пересечение некоторой сферы с двойственной решёткой в сопряжённом пространстве, но я не хочу лезть в такие детали; главное — что мы получаем некоторую картину, по которой можно восстановить исходную решётку, но это действие нетривиальное.

Victor Kleptsyn

М

16:55

Математические байки

Victor Kleptsyn

М

16:56

Математические байки

этот кадр — из мультфильма, что я упоминал; кстати, а вот оттуда же — постановка эксперимента:

Victor Kleptsyn

М

16:56

Математические байки

Victor Kleptsyn

М

17:14

Математические байки

Так вот, в 1982-м Дэн Шехтман обнаружил симметрию 10 порядка в одном из материалов (правда, там вместо ренгена использовались электроны, поэтому нужно говорить чуть более аккуратно и работать с поверхностью — чего я делать не буду; байка, как-никак). Примерно такую (image credit: wikipedia, https://en.wikipedia.org/wiki/Quasicrystal ) :

Victor Kleptsyn

М

17:14

Математические байки

Victor Kleptsyn

М

17:15

Математические байки

Но все кристаллографы знали, что симметрии 10 порядка не бывает. Потому что если у решётки есть такая симметрия R, то для самого короткого вектора v решётки вектор v-R(v) будет тоже принадлежать решётке, и будет ещё короче.

Victor Kleptsyn

М

17:20

Математические байки

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

Victor Kleptsyn

М

17:24

Математические байки

In reply to this message

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

Victor Kleptsyn

М

17:27

Математические байки

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

Victor Kleptsyn

М

17:27

Математические байки

Victor Kleptsyn

М

17:28

Математические байки

С другой разделяющей линией — красные точки теперь сверху:

Victor Kleptsyn

М

17:28

Математические байки

Victor Kleptsyn

М

17:28

Математические байки

In reply to this message

И проекция теперь выглядит не так, как раньше —

Victor Kleptsyn

М

17:29

Математические байки

Victor Kleptsyn

М

17:29

Математические байки

То есть "красный" и "синий" интервалы в проекции поменялись местами.

Victor Kleptsyn

М

17:32

Математические байки

С другой стороны, красные точки при таком изменении раскраски сдвигаются на (1,0), потому что в одном случае мы саму "красящую" букву А считаем, в другом нет, а синие на (0,1).

Victor Kleptsyn

М

17:32

Математические байки

Victor Kleptsyn

М

17:33

Математические байки

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

Victor Kleptsyn

М

17:34

Математические байки

А именно: окружность разбита на красную и синюю дуги с отношением длин Ф:1 —

Victor Kleptsyn

М

17:34

Математические байки

Victor Kleptsyn

М

17:36

Математические байки

Исходно на ней отмечена точка на границе дуг A и B, и каждый шаг она поворачивается на длину дуги B в положительном направлении. Если на k-м шаге она попадает в дугу А, то мы пишем А, а если в дугу B, то пишем B.

Victor Kleptsyn

М

17:42

Математические байки

Всё хорошо, но пока что это описание исключительно "феноменологическое": мы что-то увидели на первых ~30 итерациях, и сделали из этого какие-то (формально — совершенно не доказанные) выводы.

Victor Kleptsyn

М

17:42

Математические байки

Так вот — как раз поворот окружности это штука, к подстановочному правилу очень хорошо привязываемая.

Victor Kleptsyn

М

17:43

Математические байки

Потому что — давайте смотреть не за всеми итерациями начальной точки, а только за теми, когда она попадает на дугу А.

Victor Kleptsyn

М

17:44

Математические байки

Тогда дуга А разобьётся на две поддуги, А' и B'. Где, стартовав из поддуги B', мы сразу остаёмся в дуге A, а из поддуги A' сначала прыгаем в B, а потом в A:

Victor Kleptsyn

М

17:44

Математические байки

Victor Kleptsyn

М

17:46

Математические байки

(То, что мы сейчас делаем, называется в теории динамических систем умными словами "отображение первого возвращения", "башня Какутани", и так далее — но это совершенно неважно.)

Victor Kleptsyn

М

17:47

Математические байки

Так вот — склеив дугу А обратно в окружность, мы увидим на ней опять поворот (получившийся из перекладывания отрезков — дуг А' и B'), а восстановление исходного слова по слову в алфавите A' и B' это как раз наши правила подстановки:
"A' означает АB,
B' означает A"

Victor Kleptsyn

М

17:50

Математические байки

А то, что отношение длин исходных дуг Ф:1, означает, что и отношение длин дуг А' к B' будет Ф:1. Так что картина повторяется снова и снова.

Victor Kleptsyn

М

17:51

Математические байки

In reply to this message

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

Victor Kleptsyn

М

17:53

Математические байки

Ну и на этом, кажется, предыдущее обещание выполнено.

Victor Kleptsyn

М

17:58

Математические байки

Бонусом к сегодняшнему рассказу — несколько фотографий из Warwick University. Который, для простоты навигации, находится в два с половиной раза ближе к Coventry, чем к Warwick-у; не назвали его Coventry University потому, что Coventry University к тому моменту уже был и был достаточно известен.

Victor Kleptsyn

М

18:01

Математические байки

Victor Kleptsyn

М

18:03

Математические байки

Как написано на табличке-подписи,
"Оригинальная доска объявлений семинаров.
Важный исторический артефакт до-цифровой эры,
ок. 1963"

Victor Kleptsyn

М

18:05

Математические байки

Новые семинары можно было вписывать вниз, перематывая бумагу с нижнего рулона на верхний.

Victor Kleptsyn

М

18:07

Математические байки

А вот это — содержимое стоящего рядом шкафа с "интересными объектами":

Victor Kleptsyn

М

18:08

Математические байки

Victor Kleptsyn

М

18:08

Математические байки

Victor Kleptsyn

М

18:08

Математические байки

Victor Kleptsyn

М

18:08

Математические байки

Victor Kleptsyn

М

18:08

Математические байки

Victor Kleptsyn

М

18:18

Математические байки

Ну и — здание, где расположен математический факультет, называется в честь его основателя Zeeman building, и там висит его портрет. Но Zeeman не тот, который эффект Зеемана (тот физик, https://ru.wikipedia.org/wiki/%D0%97%D0%B5%D0%B5%D0%BC%D0%B0%D0%BD,_%D0%9F%D0%B8%D1%82%D0%B5%D1%80 ) — а математик (https://en.wikipedia.org/wiki/Christopher_Zeeman )

Victor Kleptsyn

М

18:18

Математические байки

Victor Kleptsyn

М

18:18

Математические байки

Victor Kleptsyn

М

18:19

Математические байки

Ну и на этой исторической ноте я на сегодня прекращаю дозволенные речи.

Victor Kleptsyn

9 February 2020

М

17:53

Математические байки

Если вдруг кто-то ещё не видел -- потрясающая задача с сегодняшнего матпраздника:

Victor Kleptsyn

М

17:53

Математические байки

Н

Непрерывное математическое образование 09.02.2020 13:49:56

Можно ли разрезать такого «верблюда» на 3 части и сложить из них квадрат? (Задача Ю.Маркелова с сегодняшнего Матпраздника)

Victor Kleptsyn

17 February 2020

М

21:23

Математические байки

In reply to this message

Вдогонку к моему прошлому рассказу — дополнение от коллег:

Victor Kleptsyn

М

21:25

Математические байки

PV

Polina Vytnova 04.02.2020 09:55:06

Под подписью к фотографии Chr. Zeeman - FRS = fellow Royal Society = Академик РАН

Victor Kleptsyn

М

21:25

Математические байки

PV

Polina Vytnova 04.02.2020 09:56:13

Sir is a Royal title, he received a knighthood in the 1991 Birthday Honours for "mathematical excellence and service to British mathematics and mathematics education"

Victor Kleptsyn

М

21:25

Математические байки

PV

Polina Vytnova 04.02.2020 09:56:26

= премия президента 😊

Victor Kleptsyn

М

21:25

Математические байки

PV

Polina Vytnova 04.02.2020 09:59:27

шкаф с объектами создан Saul Schleimer, https://homepages.warwick.ac.uk/~masgar/talks_and_exhibits.html#art

Victor Kleptsyn

М

21:25

Математические байки

PV

Polina Vytnova 04.02.2020 09:59:38

he also holds art exhibitions

Victor Kleptsyn

М

21:25

Математические байки

PV

Polina Vytnova 04.02.2020 09:59:51

(of math objects)

Victor Kleptsyn

М

21:27

Математические байки

In reply to this message

И эту страничку действительно стоит посмотреть — скажем, там лежат очень красивые слайды про квартику Клейна,
https://homepages.warwick.ac.uk/~masgar/Talks/2015-08-29klein_uiuc.pdf

Victor Kleptsyn

М

21:28

Математические байки

(Ту же, про которую недавно писали коллеги)

Victor Kleptsyn

М

21:28

Математические байки

Н

Непрерывное математическое образование 29.12.2019 20:00:34

еще одна картинка про квартику Клейна

Victor Kleptsyn

М

21:29

Математические байки

А ещё — оказывается, каналу "баек" исполнилось уже полгода!

Victor Kleptsyn

М

21:29

Математические байки

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

Victor Kleptsyn

М

21:29

Математические байки

Вот есть одна из первых теорем классической геометрии, что высоты треугольника пересекаются в одной точке. Все её знают.
А будет ли она верна в сферической геометрии? Или (для тех, кто с ней знаком) на плоскости Лобачевского?

Victor Kleptsyn

М

21:31

Математические байки

Оказывается, что — да, будет. На сфере совсем, а на плоскости Лобачевского с одной оговоркой, о которой после.
И у этого факта я знаю два разных объяснения: одно от В. И. Арнольда, и совершенно другое — от А. Г. Хованского.

оглавление (избранные ссылки)