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

Лемма (обратное неравенство Коши-Буняковского-Шварца, шорт-лист IMO 1995 A2). Если a,b,c — неотрицательные целые числа и ab-c² неотрицательно, то существуют два вектора x,y с целыми координатами (одной и той же, может быть большой, размерности) такие, что a,b — квадраты их норм, а c — их скалярное произведение. Иначе говоря: если квадратный трёхчлен f(t)=at²+2ct+b неотрицателен на вещественной оси, то его можно представить как сумму квадратов линейных [аффинных, если вам так нравится - ФП] функций с целыми коэффициентами:

f(t) =sum (x_i t+y_i)²

Доказательство леммы. Предположим противное и возьмём контрпример с минимальным c. Если min(a,b,c)=c, то

f(t)=c(t+1)²+(a-c)t²+(b-c) 1² —

искомое представление. Если, скажем, c>a, то возьмем трёхчлен f(t-1), то есть тройку (a, b-2c+a, c-a), по минимальности c она уже не является контрпримером, а из представления в нужном виде трёхчлена f(t-1) получается представление f(t) сдвигом буквы t на 1.

Теперь

Рождественская теорема Ферма. Если p=4k+1 простое, то p есть сумма двух квадратов целых чисел.

Доказательство. При некоторм целом c число p делит c²+1 (простое доказательство: иначе остатки от 2 до 4k-1 по модулю p разбиваются на четвёрки вида (y, - y, 1/y,-1/y)):

ap=c²+1.

Используя лемму, находим векторы x,y с x²=a, y²=p, c=xy=sum(x_i y_i). Возьмем любой индекс i, для которого y_i≠0. Обозначим x_i=X, y_i=Y. Имеем

1-(pX²+aY²-2cXY)=(a-X²)(p-Y²)-(c-XY)²⩾0

(это КБШ для векторов x, y без i-ой координаты).

Умножая на p и подставляя ap=c²+1 в левую часть, получаем
p-(pX-cY)²-Y²⩾0, но левая часть кратна p (и меньше p, так как Y≠0), поэтому она равна 0.

Для натурального числа m определим f(m) как наименьшую возможную степень многочлена с целыми неотрицательными коэффициентами, который приводим, но его значение в точке m - простое число. Тогда

lim f(m)/m=π.

via Hiroki Tokuyama

Умер Сергей Маркелов.

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

Летом 1998 года я ездил под Гамбург на Летнюю конференцию турнира городов. Это такое мероприятие, на котором школьники вникают в некоторый сюжет и размышляют о нём типа не как на олимпиадах, а как взрослые. Мне повезло, что на той конференции был замечательный сюжет, предложенный С. М., но представленный не им, а Михаилом Вялым — о том, что во многих утверждениях евклидовой геометрии можно заменить окружности на параболы с вертикальной осью (случайный пример: если на сторонах треугольника ABC отметить точки A₁, B₁, C₁, то окружности параболы с вертикальными осями AB₁C₁, BA₁C₁, CA₁B₁ имеют общую точку). Мы занимались им с Сергеем Тихомировым и довольно много всего про это поняли, но, кажется, полностью это до сих пор понятно не вполне. Вот наша работа для питерской книжки с С. Т., написанная по следам той конфы.

Проверьте свою интуицию (опрос постом выше).

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

(a) как обычно в волейболе: подача переходит к противнику, когда подающая команда проигрывает очко;

(b) подачи просто чередуются: Пифагорейцы - Вольтерьянцы - Пифагорейцы - Вольтерьянцы и т. д.

решение про волейбол (статистику сами видите, честно говоря, я ожидал другого)

В варианте (b) можно считать, что пифагорейцы подают 100 раз, а вольтерьянцы 99 раз (если матч закончился раньше, пусть всё равно доподают). В варианте (а) пифагорейцы к окончанию матча подали не больше чем 100 раз (поскольку когда они подают 101-й раз, это значит, что они уже набрали 100 очков), аналогично, вольтерьянцы - не более 99 раз. Так что пусть они играют после того, как одна из команд набрала 100 очков, до тех пор, пока пифагорейцы не подадут 100 раз, а вольтерьянцы 99, и мы включим в список розыгрышей, по которым подводится итог, ровно упомянутые 100+99=199 розыгрышей.

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

(задачу подглядел в фб)

Теперь комментарии как во всех нормальных группах, а не с этим ботом! А старые посты уже не перевести в этот режим?

Всегда любил каплинги (они же спаривающие меры, они же многозначные отображения, они же полиморфизмы, они же планы перевозок и пр.) Идея в том, что для сравнения вероятностей двух событий надо умно реализовать их на одном вероятностном пространстве. Простой пример: красим каждую грань многогранника с вероятностью p независимо от остальных. Тогда вероятность того, что есть три попарно смежные покрашенные грани, возрастает с ростом p. Доказательство: пусть лучше каждая грань выбирает число от 0 до 1, и мы красим её, если число меньше p. Тогда наши события при разных p просто вложены друг в друга, и монотонность очевидна.

Лёша Куликов обратил внимание на свежую работу на эту тему.

Пусть n человек рассаживаются по k автобусам, выбирая, в который автобус сесть, равномерно и независимо. Рассмотрим вероятность p(k) того, что кто-то окажется единственным в своём автобусе (n считаем постоянным, а k переменным).

Теорема. p(k) возрастает по k при данном n.

Доказательство. Сравним p(k+1) и p(k). Можно считать, что дело обстоит так: сначала люди рассаживаются по k+1 автобусу, потом автобус семёрка ломается и люди оттуда рассаживаются по остальным. Нас интересуют вероятности двух событий: A - что до поломки был одинокий пассажир, B - что он есть после поломки и пересаживания. Сравним события A\B и B\A. Как могло произойти событие B\A? Скажем, Вася пересел из семёрки в пустую тройку, причём до поломки одиноких не было. Но до поломки могло быть так, что Вася - единственный в семёрке, потому что остальные, выбравшие семёрку, выбирали бы тройку (а всё остальное как было), а потом Вася пересел в тройку. В этом случае происходит A\B, и это имеет ту же вероятность.

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

(но дальше не продолжить, потому что там 0)

Сочинил десять лет назад, сейчас, поди, роботы лучше справляются.

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

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

Прочитал на MO интересное доказательство того, что R³ не является квадратом топологического пространства.

На пространстве R³×R³ гомеоморфизм f:(x, y) →(y, x) не является композиционным квадратом никакого гомеоморфизма — потому что меняет ориентацию. С другой стороны, для пространства вида Y=X×X гомеоморфизм f:(x, y) →(y, x) на Y×Y является квадратом: если обозначить x=(a, b), y=(c, d) для a, b, c, d из X, то f есть квадрат отображения (a, b, c, d) → (b, c, d, a).

На Всеросе была предложена такая задача (автор Ю. А. Хромин):

куб составлен из n³ единичных кубиков. В них надо написать числа 0,1 так, чтобы сумма восьми чисел в любом кубе со стороной 2 была не больше 4, и при таких ограничениях общая сумма была максимально возможной.

Задача решается, например, по индукции (так почти все участники, решившие задачу, и делали).

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

в кубиках параллелепипеда 1000×2000×3000 расставляются числа 0,1, 2, 3. Расстановка допустимая, если сумма 343 чисел в любом кубе со стороной 7 не больше 800. Найдите наибольшую сумму чисел в допустимой расстановке.

Далее подход Артура объясняется на этом примере.


Давайте сделаем произвольную допустимую расстановку X 7-периодичной в данном направлении (по вертикали, скажем) — сохраняя допустимость и не уменьшая сумму чисел. Разобьём всё на двумерные горизонтальные слои и выберем 7 подряд идущих слоёв с наибольшей суммой. Пусть общая сумма в выбранных слоях это s. Рассмотрим расстановку Y, которая в выбранных 7 слоях совпадает с X, но 7-периодична по вертикали. Ясно, что она тоже допустима. Докажем, что сумма чисел в Y не меньше, чем в X. Достаточно доказать это отдельно для слоёв ниже выбранных и выше выбранных. Слои ниже выбранных разобьём на семёрки, начиная с нижнего, верхняя семёрка будет, возможно, пересекаться с выбранными слоями. В каждой семёрке сумма в X не больше, чем s, а в Y — ровно s. Значит, сумма в Y ниже выбранных слоёв не больше, чем в X (сумма в части выбранных слоёв сократилась: они одинаковы в X и в Y). То же сверху от выбранных.

Теперь делаем то же последовательно в двух других направлениях и получаем допустимую расстановку с суммой не меньше чем в исходной, но 7-периодическую по каждой переменной.

Среди таких расстановок найти ту, где сумма наибольшая, несложно: надо раскрасить кубики в 343 цвета в зависимости от остатков координат при делении на 7, в 266 самых популярных цветах расставить тройки, в следующем по популярности цвете расставить 2, в остальных кубиках нули. Получается 14013662520, если я не обсчитался.

немного рекламы

1. Позиция постдоков в институте Эйлера, всеми любимом, по-прежнему весьма привлекательная

Call for Postdocs 2025

The Leonhard Euler International Mathematical Institute in St. Petersburg is seeking postdocs in all areas of Mathematics, Theoretical Computer Science, Mathematical and Theoretical Physics.

Applicants should send their applications to [email protected]

The applications should include:
CV,
List of publications (including preprints, if necessary),
Description of research interests, ideally mentioning possible host or other research contacts in St. Petersburg,
Names, affiliations and contacts of 2-3 people willing to send recommendation letters if asked by the committee,
Any special requirements wrt the dates, etc.

Basic conditions:
Competitive salary starting at 160,000 RUB per month (taxed at 13% for residents and foreigners), which is more than enough for comfort living in St. Petersburg,
The institute partially covers travelling expenses to St. Petersburg of up to 600 Euro,
The institute has some funds for covering participation in conferences that cannot be covered from other sources,
1 or 2 years extendable for another year,
Teaching load is set at 4 academic hours per week,
Flexibility with respect to the starting date, length, specific calendar requirements (such as a leave in the middle).
The Call will remain active throughout the whole year. Preferable starting date is September 1, 2025, earlier or later dates will also be considered.

If you have questions, please do not hesitate to ask them by email.

https://eimi.ru/calls/5883/

2. Позиция постдоков по комбе и около у наших друзей из МФТИ, в целом похоже по условиям

Конкурс академической мобильности: ФПМИ МФТИ предлагает позиции научных сотрудников (постдоков) для молодых исследователей со степенью кандидатов наук!

Конкурс подразумевает трудоустройство на 2 года в одну из лабораторий ФПМИ, например:
- Лабораторию комбинаторных и геометрических структур (CombGeo)
- Лабораторию дискретной и комбинаторной оптимизации

Условия:
- молодой ученый со степенью кандидата наук (до 35 лет) или PhD (до 40 лет)
- не менее трех публикаций за последние 5 лет в рецензируемых журналах, желательно первого и второго квартиля (Q1 и Q2)
- профиль: комбинаторика, геометрия и топология, геометрическая теория групп, дискретная вероятность, а также смежные вопросы теоретической информатики
- готовность взять небольшую преподавательскую нагрузку (1-2 занятия в неделю)

Вознаграждение:
Зарплата состоит из базовой ставки от МФТИ (100к-200к в зависимости от опыта кандидата) + доплата от лаборатории (по результатам собеседования) + доплата за преподавание

Также в случае необходимости предоставляется проживание на кампусе МФТИ в Долгопрудном.

В случае заинтересованности направьте резюме Анастасии: @thesekunda
Дедлайн: 28 мая

кто ставит такую реакцию к постам, это вы минусуете?(((

Пусть a₁ < ... < aₖ — целые неотрицательные числа, t₁, ..., tₖ — ненулевые целые числа, |tᵢ| ≤ 2^{aᵢ} . Положим sᵢ = t₁ + ... + tᵢ. Предположим, что sₖ = 0, но sᵢ ≠ 0 при i < k. Следует ли из этого, что (k−1) + ν₂(t₁...tₖ) ≤ a₁ + ... + aₖ?

(как обычно, ν₂(x) для целого ненулевого числа x обозначает наибольшее целое m, для которого 2ᵐ делит x)

Вы, может, думаете, что я такое нелепое спрашиваю про степени двойки? А это, между прочим, решает гипотезу Стенли про биномиальный коэффициент как виртуальный характер на группе нимберов. Можете придумать доказательство получше, чтобы переносилось на q-случай (есть такой критерий в алгебраической комбинаторике: доказательство хорошее, если доказывает и q-версию).