Это, конечно, оффтопик для этого канала — но поздравляю всех с первым аппаратом тяжелее атмосферы, аэродинамически поднявшимся в воздух на другой планете!

Формулировка про "тяжелее воздуха" тут точная — в атмосфере Венеры летали (надувавшиеся прямо в атмосфере после торможения) аэростатные зонды советских АМС Вега-1 и Вега-2. А без слова "аэродинамически" формально-верно из-за слова "планета", но всё-таки тогда стоило было бы вспомнить про Луну (откуда взлетали как Apollo, так и советские Луна-16, Луна-20, Луна-24, недавний китайский Чанъэ-5), да и с астероидов тоже были взлёты — можно вспомнить японские Хаябусу и Хаябусу-2, летящий сейчас OSIRIS-REx...

А ещё этот вертолётик несёт на себе микроскопический кусочек ткани с того самого самолёта братьев Райт; жест совершенно символический — но очень красивый.

Кадр из только что закончившейся прямой трансляции NASA : показания альтиметра (взлёт, зависание, посадка) + см. новость N+1.

Момент полёта — https://youtu.be/p1KolyCqICI?t=2524

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

Один популярный пример выглядит так: возьмём квадрат на плоскости и впишем в него круг. Ясно, что круг закроет большую часть площади квадрата. Дальше, возьмём куб и впишем в него шар. Опять же, шар займёт большую часть объёма куба. Но вот в четырёхмерном случае гиперсфера займёт меньше трети объёма гиперкуба, а при дальнейшем повышении размерности отношение их объёмов сходится к нулю. При этом евклидово расстояние от центра n-мерного куба до любого из его 2^n углов растёт как sqrt(n), т.е. неограниченно; а основной объём пространства (т.е., например, основная часть равномерно случайно взятых точек) внутри такого куба оказывается на расстоянии от центра с матожиданием sqrt(n/3) и с убывающей к нулю дисперсией. Короче, n-мерный куб — это очень странное место, с кучей углов и пустым центром.

Другой пример — гипотеза Борсука о возможности разбиения n-мерного тела диаметром 1 на n+1 тел диаметром меньше 1. Она доказана для n<=3 и опровергнута для n>=64. Посредине — томящая неизвестность.

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

Возьмём, скажем, 100-мерное пространство и выберем в нём равномерно случайно из единичного гиперкуба 42 точки. Пронумеруем их в некотором случайном, но фиксированном порядке, от 1 до 42. Какова вероятность, что в нашем пространстве найдётся такая ось, в проекции на которую наши точки выстроятся в нужном порядке? Ответ: больше 99%. Кому интересно, можете посмотреть мой скрипт на питоне, которым это эмпирически можно проверить (работает довольно долго, решает системы линейных неравенств, пересекая полупространства для каждой пары точек).

(+Иллюстрация к поведению куба)

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

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

Спасибо, Федя, Витя и все остальные, кто пишет мне уточнения и комментарии к моим постам :)

===
Один из самых классических объектов в комбинаторике — это число разбиений p(n): сколькими способами число n можно представить в виде суммы натуральных слагаемых, если мы не различаем способы, отличающиеся только порядком слагаемых (или, что то же самое, предполагаем, что слагаемые упорядочены по неубыванию).
Так,
p(1)=1,
p(2)=2 (потому что 2=1+1),
p(3)=3 (потому что 3=2+1=1+1+1),
p(4)=5 (потому что 4=3+1=2+2=2+1+1=1+1+1+1),
p(5)=7 (упражнение),
и так далее.

Разбиению числа n можно сопоставить диаграмму Юнга: фигуру из клеток в первом квадранте, у которой число клеток в k-й строке это k-е слагаемое. Например, вот диаграмма Юнга для разбиения 15=6+5+3+1:

Хорошей замкнутой формулы (как формула Бине для чисел Фибоначчи) для чисел разбиения нет; интересно, что их количество растёт быстрее, чем любой полином, но медленнее, чем экспонента:

Но — если замкнутой формулы нет, то как можно (при желании) вычислять p(n) при большом n? Скажем, если перебор всех
p(100)=190569292
разбиений числа n=100 ещё можно поручить компьютеру, то перебирать все
p(1000)=24061467864032622473692149727991
разбиения числа n=1000 кажется не очень продуктивной идеей.

Один "технический" способ решения этого вопроса — это находить больше. А именно, пусть p_k(n) — число разбиений n в сумму (невозрастающих) слагаемых, которые все не превосходят данного k. Тогда, с одной стороны, p(n)=p_n(n), а с другой — числа p_k(n) уже несложно ищутся рекурсивно, когда мы перебираем варианты для самого большого слагаемого:
p_k(n) = \sum_{j=1}^k p_j(n-j).

Но нас будет интересовать другой способ — оказывается, на сами p(n) тоже есть рекуррентное соотношение, только чуть более сложное! Вот оно:
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-...
(Сумма обрывается, как только аргумент у p становится отрицательным.)

Применение этого равенства — кадр из великолепного видео Mathologer-а "The hardest "What comes next?" (Euler's pentagonal formula)" — которое я очень всем советую.

Как это соотношение можно получить? Беглый взгляд показывает, что это явно что-то нетривиальное.
Поэтому давайте его временно отложим в сторону, и применим к последовательности p(n) стандартный молоток (а точнее, кувалду) комбинаторики — рассмотрим производящую функцию этой последовательности:
P(q):=\sum_{n=0}^{\infty} p(n) q^n.

Если бы мы работали не со всеми разбиениями n, а только с разбиениями в сумму слагаемых, не превосходящих k, то производящая функция развалилась бы в произведение k скобок-сомножителей:

Первая скобка отвечает за единицы, вторая за двойки, и так далее — так что (сгруппировав одинаковые слагаемые) разбиению n, в котором a_1 единиц, a_2 двоек,..., a_k слагаемых, равных k, мы сопоставляем произведение мономов из этих скобок, где q^{1*a_1} взят из первой скобки, q^{2*a_2} из второй, и т. д..
А дальше — каждая скобка "собирается", как сумма геометрической прогрессии.

Если ограничения на величину слагаемых нет — получается уже просто бесконечное произведение:

В скобках — очень забавно, что совсем похоже устроено произведение Эйлера для дзета-функции. Просто роль q^j играет p^{-s}, а по основной теореме арифметики каждое натуральное число ровно одним способом раскладывается в произведение простых, поэтому числители единичные.

Теперь давайте посмотрим на обратный ряд к P(q) — просто формально записав Q(q)=1/P(q).

Из разложения P в произведение мы знаем и разложение Q; давайте раскроем скобки — и пусть c_n это получившиеся коэффициенты.