10419
Немного математики каждый день // для обратной связи: cme.chnl@gmail.com (интересным вещам по теме канала всегда рады; за деньги или за «обмен ссылками» ничего не публикуем)
https://wolffund.org.il/noga-alon/ & https://wolffund.org.il/adi-shamir/
премию Вольфа 2024 года по математике получают Нога Алон (за фундаментальный вклад в комбинаторику и теоретическую информатику) и Ади Шамир (за фундаментальный вклад в математическую криптографию)
Какие еще есть доказательства теоремы Монжа?
Ну, во-первых, есть стандартное доказательство с теоремой Менелая. Я бы даже сказал, что теорема Монжа это и есть теорема Менелая.
Во-вторых, есть доказательство с композицией гомотетий. Если композиция трех гомотетий является тождественным преобразованием, то центры лежат на одной прямой. Как это понять? Надо проследить, например, за центром первой гомотетии. Если центры гомотетий не лежат на одной прямой, то он не имеет шансов вернуться назад в исходное положение.
В-третьих, есть замечательное доказательство от Григория Мерзона с линейными функциями. Обозначим центры окружностей A, B, C, их радиусы — a, b, c. Пускай [B,C] — линейная функция на плоскости, которая в точках B и C равна 0, а в точке A равна 1 (в частности, [B,C]=0 — уравнение линии центров этих окружностей). Аналогично определим функции [C,A] и [A,B].
Тогда a[B,C]+b[C,A]+c[A,B]=0 — уравнение прямой, на которой лежат нужные три точки.
В-четвертых, есть доказательство с моделью Пуанкаре плоскости Лобачевского. Вкратце, если радиусы (в смысле модели) первой и второй окружностей равны, и второй и третьей равны, то и радиусы первой и третей окружностей равны. А движение, переводящее равные окружности друг в друга это как раз гомотетия с центром на абсолюте.
В-пятых, есть доказательство Акопяна из вчерашнего поста.
А в-шестых, предлагаю такое доказательство с помощью масс. Пусть опять центры окружностей A, B, C, их радиусы — a, b, c. Поставим в точку A массу b-c, в точку B массу c-a, и в точку C массу a-b. Сумма масс равна нулю, центра масс нет, но есть утверждение, которое я называю лемма о диполе
Предположим дана система материальных точек с нулевой суммой масс. Ее разбили на две группы двумя способами. При первом разбиении образовалось две группы с ненулевыми суммами, при этом группа с положительной суммой масс имеет центром точку X+, а группа с отрицательной суммой масс имеет центром точку X-. При втором разбиении аналогично получаются точки Y+ и Y-. Тогда X-X+ и Y-Y+ параллельны - дипольная ось.
Василий РОГОВ. Семинар КТ. Воскресенье, 7 июля
✅ Биарифметическая и биалгебраическая геометрия
Алгебраическая теория чисел изучает алгебраические числа — числа, задаваемые как корни многочленов с рациональными коэффициентами. Алгебраическая геометрия изучает алгебраические многообразия — геометрические объекты, задаваемые как множества общих нулей систем многочленов от нескольких переменных. Эти две науки последние сто лет развиваются параллельно, и между объектами их изучения было найдено много глубоких аналогий.
Однако, не все числа являются алгебраическими. Самые известные не алгебраические (“трансцендентные”) числа это е и \pi. Более того, теорема Линдеманна-Вейерштрасса утверждает что такая фундаментальная операция как взятие экспоненты “очень не алгебраична”: экспонента алгебраического числа почти всегда трансцендентна.
Мы обсудим теорему Линдеманна-Вейерштрасса, а также ее геометрический аналог: когда “экспонента алгебраического многообразия” алгебраична? Оказывается, на этот вопрос есть очень красивый ответ, который имеет свой аналог в теории чисел. Этот ответ приведет нас к философии “биалгебраической геометрии”, сформулированной Бруно Клинглером, Эммануэлем Ульмо и Андреем Яфаевым в 2015 году. Если хватит времени, я расскажу немного о том, какие новые идеи эта философия привнесла в алгебраическую геометрию и теорию Ходжа в последние десять лет.
Для понимания большей части доклада достаточно не бояться слов “комплексные числа” и “экспонента”.
Из блога Скотта Ааронсона я узнал сегодня, что мы теперь точно знаем значение BB(5) - функции Busy Beaver на 5 состояниях. Это одновременно тривиальная и захватывающая новость. Это что-то, про что я не был уверен, что будет известно в течение моей жизни - хотя полагал вероятным.
Что такое Busy Beaver? Попробую вкратце объяснить.
В информатике есть понятие "машина Тьюринга". Это не настоящая физическая машина из транзисторов, а теоретическая модель. Представьте себе бесконечную ленту, состоящую из ячеек, в каждой из которых может быть записано '0' или '1' (в общем случае можно и больше разных символов, но достаточно двух). Изначально на ленте везде написано '0', и над одной из ячеек находится головка чтения-записи, которая может находиться в одном из нескольких состояний (представьте себе переключатель, который может быть в положении A,B,C или D - это пример 4 состояний). За один шаг головка машины смотрит, что написано на ячейке, над которой она сейчас находится, а потом справляется в "таблице переходов". В таблице написано, например: если ты в состоянии A и видишь 0, то перейди в состояние B, напиши 1, и сдвинься вправо. И так на любую комбинацию "состояние-что я вижу" есть рецепт: в какое состояние перейти, что написать, 0 или 1, и куда сдвинуться, влево или вправо. Потом машина делает следующий шаг по таким же правилам. И так далее, пока она не войдет в состояние, которое заранее считается "конечным", например D, и тогда она останавливается.
В принципе такая модель может выполнять все, что мы считаем "алгоритмом" и поручаем компьютерам. Внутри вашего компьютера (или телефона) есть процессор, который понимает только нули и единицы. И хотя он работает сразу с многими нулями/единицами одновременно, и выполняет сложные программы, все, что он делает, в принципе можно смоделировать как машину Тьюринга (с очень большим числом состояний). Такая машина может получать входные данные не с клавиатуры, а записанные заранее на ее ленте, и выдавать результат не на экране, а тоже на своей ленте. Ученые используют эту модель в основном для того, чтобы доказывать, какие задачи компьютер не может выполнить никогда даже в принципе, или какие алгоритмы принципиально намного быстрее или медленнее других.
В 1962 году венгерско-американский математик Тибор Радо задал следующий вопрос. Обычно для того, чтобы сделать что-нибудь "интересное" машиной Тьюринга, нужно много состояний. Состояния играют роль внутренней логики алгоритма, позволяют машине "помнить", где она находится внутри сложного алгоритма, что она уже выяснила, итд. Но давайте для любого N посмотрим на все возможные машины (т.е. разные таблицы перехода) из N состояний, и что они делают с пустой лентой (все нули). Одни программы быстро остановятся, войдя в состояние остановки; другие войдут в бесконечный цикл, или уйдут "в бесконечность" без цикла - например, будут писать 1, двигаясь все дальше и дальше по бесконечной ленте без возврата. Но есть какая-то машина, которая в конце концов остановится, но после наибольшего числа шагов по сравнению со всеми остальными из N состояний. Такая машина-чемпион называется Busy Beaver. Сколько шагов она сделает перед тем, как остановится, для данного N?
https://old.kvantik.com/art/files/pdf/2013-10.6-9.pdf
сегодня пусть здесь будет статья Сергея Дориченко про чётность («Квантик» №10 за 2013 год)
https://youtu.be/yZsVgnM-PQw
«Современная экономика немыслима без серьезного математического аппарата. В 2012 году Ллойд Шепли получил Нобелевскую премию за статью, написанную 50 лет назад. Он исследовал проблему распределения абитуриентов по колледжам (…) Премию Шепли разделил с Элвином Ротом, который на практике применил его теорию в области дизайна экономических механизмов (…)»
вот про такую лекцию Андрея Бремзена (1975–2021) напомним (Малый ШАД, 15.02.2014)
в качестве картинок по выходным: как посчитать сумму 1+2x+3x²+4x³+… (уже зная сумму геометрической прогрессии)
// R.B.Nelsen. Proofs Without Words III
У Владимира Игоревича была такая задача (мне казалось -- нерешенная). Может ли "фальшивое" четырехмерное пространство быть пространством траекторий полиномиального векторного поля?
Понимать это надо так: берем какую-нибудь нестандартную гладкую структуру на R^4. Домножим теперь это гладкое многообразие W на прямую -- W \times R. Результат диффеоморфен R^5, т.к. на R^5 нет нестандартных гладких структур. Может ли так случиться, что найдется такой диффеоморфизм W \times R с R^5, что прямые w \times R он переведет в траектории полиномиального векторного поля?
https://math.ru/lib/files/pdf/Lyapunov/Lyapunov_2011.pdf
напомним заодно про такую книгу об А.А.Ляпунове (вышедшую в 2011 году к 100-летию с его рождения)
#математика
В нашем новом ролике «Выбор стратегии и принцип минимакса» речь идёт о такой игре:
Каждый из двух игроков заранее выкладывает столбик из монет, причём кладёт каждую из монет орлом или решкой вверх по своему усмотрению. Затем игроки последовательно снимают верхние монеты и предъявляют их друг другу. Первый играет на совпадение: если на столе оказываются два орла, он получает 9 рублей, а если две решки — 1 рубль. Второй играет на различие: если на столе оказываются орёл и решка или решка и орёл, игрок получает по 5 рублей. Каждый из игроков не знает о замысле соперника и оказывается в ситуации неопределённости.
И спрашивается, какую стратегию нужно выбирать игрокам, чтобы их выигрыш был максимальным или хотя бы проигрыш минимальным?
Попробуйте выбрать правильную сторону в этой игре! А ещё вы увидите в ролике красивую модель этой задачи из палочек и ниточек.
картинка на тему
«Что больше: 1⋅22+2⋅21+3⋅20+...+22⋅1 или 2²+4²+6²+...+22²?»
(из статьи А.Заславского в Квантике №6 за 2024 год)
B. F. Wyman. What is a Reciprocity Law? (AMM, 1972)
https://www.jstor.org/stable/2317083
очень хороший исторический обзор про броуновское движение
английский перевод https://arxiv.org/abs/0705.1951v1
c французского оригинала http://www.bourbaphy.fr/duplantier2.pdf
https://youtu.be/S75VTAGKQpk
John Conway proves that 91 is the smallest number which looks prime but isn't
Владимир ШАРИЧ. Семинар КТ. Воскресенье, 16 июня
✅ От клякс на клетчатой бумаге к суммам двух квадратов
Рождественская теорема Ферма, она же теорема Ферма о двух квадратах, она же теорема Ферма-Эйлера довольно известна: каждое простое число вида 4к+1 можно представить в виде суммы двух точных квадратов. Например, 5=1+4, 13=4+9, 41=16+25, 123456761 — сумма квадратов 1856 и10995.
Также известно много доказательств, в основном алгебраических. Из всех (известных докладчику) доказательств выделяется одно, довольно хитро использующее некоторые [несложные] результаты из комбинаторной геометрии. Его-то мы и расскажем.
Лекция доступна школьникам начиная с 9 класса.
https://arxiv.org/abs/2306.15099
А.Г.Хованский про центр масс в т.ч. для систем с нулевой суммарной массой (в этом случае он является не массивной точкой, а “диполем”)
в качестве картинок по выходным — Möbius Ship (Tim Hawkinson)
Читать полностью…
Для очень малого числа состояний, 1-2-3, легко перебрать все возможные машины и посмотреть, что они делают, слишком примитивными они являются. Для 4 состояний максимальное число шагов перед остановкой равно 107, и это доказали в 1983 году. Однако уже 5 состояний позволяют сделать хитрые машины, про которые нелегко понять, они делают что-то бесконечное, или все-таки остановятся рано или поздно. С 1990 года есть кандидат - машина, которая останавливается после 47 миллионов шагов - но чтобы доказать, что она чемпион, нужно перебрать все возможные машины из 5 состояний, а их 16 триллионов! Проблема в том, что нет универсального метода определить, остановится данная машина или нет (это как раз "проблема остановки", которую принципиально невозможно решить с помощью алгоритма). Можно либо запускать ее на симуляторе, желательно очень оптимизированном, делающим миллионы шагов в секунду, и ждать, пока она остановится, либо искать математическое доказательство того, что никогда не остановится - а его надо искать для каждого сложного случая отдельно. К началу 2000-х осталось только около 40 сложных случаев - машин, которые скорее всего никогда не останавливаются, но доказать это пока не могли. В принципе могло бы оказаться и так, что одна из них "моделирует" сложную математическую проблему. Скажем, есть машина из 23 состояний, которая останавливается только если неверна знаменитая гипотеза Гольдбаха, которую никто не может доказать уже несколько сотен лет. Но 5 состояний все же настолько мало, что такое казалось маловероятным. И вот, после нескольких лет усердной работы фанатов этой проблемы в последние годы, им удалось избавиться от всех сложных случаев, и доказать то, что все подозревали - что кандидат 1990 года и есть чемпион. Все технические подробности - на сайте bbchallenge.org!
Проблема Busy Beaver - странная, любопытная штука. С одной стороны, не очень ясно, зачем ей заниматься. Найти общую формулу или метод для любого N невозможно в принципе. Ответ для N=5 никакой конкретной пользы ни для чего не приносит. Ответ для N=6 скорее всего останется недоступен для человечества за все время его существования. Более того, то, как именно сформулирована задача (какое из нескольких определений простой машины Тьюринга используется, например) "все меняет" в смысле ответа и его доступности нашим усилиям, так что задача в любом случае довольно "искусственно" выглядит. И все равно есть что-то притягательное в ней для горстки программистов и математиков, которые продолжали активно работать над ней все эти годы.
Я это хорошо понимаю, потому что много лет назад внес свой крохотный вклад в этот сизифов труд. Тогда был свежий и многообещающий кандидат в ряды Busy Beaver из 6 состояний, который останавливался после 8 квадриллионов шагов (квадриллион это миллион миллиардов), но этот факт еще никто не подтвердил независимо от первооткрывателя этой машины (столько шагов невозможно было запустить "напрямую" симулятором, надо было придумать и написать специальную программу, которая использует логику этой конкретной машины). Я помню, что написал такую программу, подтвердил результат и послал первооткрывателю, но не мог вспомнить сегодня, когда это сделал, думал, что где-то в начале 2000-х. Но потом нашел упоминание, которое все еще лежит на сайте этого человека: "No 2 has been verified independently by Anatoly Vorobey <mellon@pobox.com>
at 20 Sep 1997. He was the first to detect that the original number of steps were one too large (corrected above)."
Я уже 20 лет не пользуюсь этим мейлом. Я забыл, что поправил на 1 количество шагов этого кандидата. Сам кандидат три года спустя был заменен другим, гораздо более крутым по числу шагов, а потом снова и снова - тот кандидат, что есть сейчас, останавливается после невообразимо огромного числа шагов, это число не записать обычными цифрами, не хватит атомов во Вселенной. Но все равно приятно.
BB(5) = 47,176,870
Давным-давно барон Мюнхгаузен свои владения обнёс забором и нарисовал на карте. Барон забыл, входит ли в его владения деревня Гаузеновка. Он смог найти лишь обрывок карты (см. рис.), на который попали его дом, деревня Гаузеновка и часть забора, проходящая по этому участку. Выясните, входит ли деревня во владения барона.
// вот такая, например, задача, обсуждается в статье выше
https://math.spbu.ru/Euler/pages/14_2_panin.htm
(старое) интервью И.А.Панина про школьные и студенческие годы и проч.
теорема Райдемейстера: если один и тот же узел двумя способами изображён на плоскости, то одну диаграмму можно перевести в другую за несколько движений Райдемейстера (+ шевелением диаграммы, т.е. планарными изотопиями)
Проще всего придумать и "формализовать" комбинаторно-топологическое доказательство: приблизить узел ломаной, а его объемлющую изотопию разбить на элементарные операции типа "заменили отрезок на два отрезка".
Но хочется порассуждать "гладко", в терминах общего положения. Это красивее, но нужно владеть соответствующей техникой; её формализовали сильно позже, чем "триангулированный" подход. В тексте
https://arxiv.org/abs/2406.18203
рассказывается, как устроено гладкое доказательство и какая там нужна теорема трансверсальности (спойлер: без струй не обойтись). Инструменты, которые стоит освоить
#чётамнаархиве
"Традиционно утверждается, что большинство результатов, которые формулируются в элементарных [математических] курсах, следует сопровождать полными доказательствами. Такая точка зрения представляется нам безнадежно устаревшей, нереалистичной и лицемерной."
Из статьи Вавилова/Халина/Юркова. "НЕБЕСА ПАДАЮТ: МАТЕМАТИКА ДЛЯ НЕМАТЕМАТИКОВ"
"Что нас больше всего раздражает в жрецах так называемой “элементарной математики”, так это их крючкотворство и мелочный педантизм. Нам, воспитанным профессиональными математиками, все их дебаты кажутся совершенно лишенными смысла и крайне искусственными."
"В действительности дело обстоит следующим образом. Наличие или отсутствие доказательств никак не влияет на доверие студентов к самим результатам. Мы думаем, что основная роль доказательств в лекциях и учебниках для нематематиков состоит в следующем:
∙ Убедить студента в том, что он правильно понимает формулировку.
∙ Уточнить смысл результата и его связь с другими результатами.
При обучении профессиональных математиков доказательства могут иметь и другие функции:
∙ Отработать общие приемы математических рассуждений (индукция, редукция, разбиение на случаи, общее положение, специализация, …) и стандартную технику в какой-либо конкретной области.
∙ Выработать привычку и вкус к точным рассуждениям как таковым, а также тренировать привычку сразу отличать предположения, свидетельства и догадки от твердо установленных фактов.
∙ Как говорят в Кембридже, to illustrate some of the tedium."
И много примеров как компьютерную алгебру можно применять.
https://biblio.mccme.ru/node/248210
https://biblio.mccme.ru/node/248211
https://biblio.mccme.ru/node/248212
в «Математической книге» появились в продаже учебные пособия М.А.Волчкевича по геометрии для 7, 8, 9 кл.
Первая в СССР система французско-русского машинного перевода
В 1950-е годы гуманитарии и математики объединились, чтобы заниматься машинным переводом. Именно с этого берёт начало сфера автоматической обработки естественного языка (Natural Language Processing). За 70 лет с тех пор методы машинного перевода радикально поменялись несколько раз, но как работали самые первые системы? Вспоминаем историю системы французско-русского перевода из 50-х гг., описываем принцип работы алгоритма (он состоял из 17 программ) и сравниваем его с современными моделями.
Кратко: о чем статья?
В середине 1950-х А. А. Ляпунов, математик и один из основоположников кибернетики в СССР, собрал группу для работы над машинным переводом (МП). Он считал, что МП — задача преимущественно математико-кибернетическая, а не лингвистическая (глядя на современные системы можно сказать, что Ляпунов был прав). За полтора года им удалось с нуля получить первые результаты автоматического перевода с французского языка на русский.
Чтобы облегчить задачу, были выбраны тексты из области математики: в них ограниченный набор слов, конструкции не слишком разнообразны, отсутствует игра слов
Самым главным «ключом» к переводу стало составление двух словарей. В первый включили 1200 основ слов: частотных в математических текстах, служебных и дополнительных терминов. Второй словарь, специальный, насчитывал 250 оборотов, которые нельзя перевести дословно. Французские и русские слова сопровождались морфологическими, техническими и другим важными для перевода указаниями (например, о наличии омонимов).
Проблема этой системы была в ограниченности: словари нуждались в доработке. Алгоритм можно было расширять, но система плохо распространялась на новый материал и сложные случаи. Зато сама постановка задачи создать машинный перевод вскрыла пробелы в лингвистическом знании: структура языка была недостаточно изучена и описана. Это стало толчком для появления математической и структурной лингвистики.
Подробности о работе над переводом и его итогах, а также сравнение машинного перевода 1950-х с современным найдете в полной версии материала.
Время чтения: 9 минут.
🤖 «Системный Блокъ» @sysblok
https://www.math.uni-bonn.de/people/scholze/Condensed.pdf
Peter Scholze. Lectures on Condensed Mathematics
ранее на близкие темы: /channel/cme_channel/2252
Читать полностью…
Сегодня задача-картинка из Квантика, которая меня когда-то удивила:
Вырежьте в листе бумаги отверстие диаметром 8 см. А теперь просуньте сквозь него компакт-диск диаметром 12 см. Бумагу можно мять, но нельзя рвать. Как такое возможно?
http://mi.mathnet.ru/umn9882
достаточно недавний обзор по гипотезе Новикова // via @sweet_homotopy
ранее на близкие темы: /channel/cme_channel/2971
Читать полностью…
https://www.helenfriel.com/heres-looking-at-euclid
уже писали про издание Бирна «Начал» Евклида — а вот Helen Friel складывает из бумаги 3д-версии иллюстраций из этой книги