Поскольку недавно был 200-летний юбилей Чебышева — давайте я чуть-чуть расскажу о простых числах — и про его работы о них.
Среди первых 10 чисел есть 4 простых: 2, 3, 5, 7; среди первых 100 их 25, среди первой тысячи — 168, то есть их доля падает с 0.4 до 0.25 до 0.168 соответственно; и чем дальше, тем меньше эта доля простых становится. Собственно, это (на рукомахательном уровне) вполне логично: им нужно "избежать делимости" на всё большее и большее число меньших простых. А как более точно описать поведение количества простых?
Теорема об асимптотическом распределении простых чисел утверждает, что число π(n) простых, не превосходящих n, ведёт себя асимптотически как n/ln n.
Иными словами, доля простых от 1 до n ведёт себя как 1/ln n; или же можно сказать, что случайно выбранное число от 1 до n оказывается простым с вероятностью 1/ln n.
И доказали эту теорему строго в 1896 году Адамар и де ла Валле-Пуссен.
Началась же её история с предположений Лежандра и Гаусса примерно за сто лет до того; Лежандр, рассматривая таблицы простых чисел, пришёл к приближению вида
n/(A ln n + B ),
где A=1, B=-1.08366; Гаусс просто предположил ответ n/ln n, не публиковал его, но упомянул о нём много позже в письме Энке.
(Тут ещё есть имена — начиная с Дирихле — но я пока остановлюсь с историческими отсылками.) А я же собираюсь поговорить (в том числе) о том, что было посередине: о работах Чебышева "Об определении числа простых чисел, не превосходящих данной величины" (1848) и "О простых числах" (1850).
Обе эти работы есть в его "Избранных математических трудах", но прежде, чем на них посмотреть, давайте немного к поведению простых чисел "приноровимся".
Среди первых 10 чисел есть 4 простых: 2, 3, 5, 7; среди первых 100 их 25, среди первой тысячи — 168, то есть их доля падает с 0.4 до 0.25 до 0.168 соответственно; и чем дальше, тем меньше эта доля простых становится. Собственно, это (на рукомахательном уровне) вполне логично: им нужно "избежать делимости" на всё большее и большее число меньших простых. А как более точно описать поведение количества простых?
Теорема об асимптотическом распределении простых чисел утверждает, что число π(n) простых, не превосходящих n, ведёт себя асимптотически как n/ln n.
Иными словами, доля простых от 1 до n ведёт себя как 1/ln n; или же можно сказать, что случайно выбранное число от 1 до n оказывается простым с вероятностью 1/ln n.
И доказали эту теорему строго в 1896 году Адамар и де ла Валле-Пуссен.
Началась же её история с предположений Лежандра и Гаусса примерно за сто лет до того; Лежандр, рассматривая таблицы простых чисел, пришёл к приближению вида
n/(A ln n + B ),
где A=1, B=-1.08366; Гаусс просто предположил ответ n/ln n, не публиковал его, но упомянул о нём много позже в письме Энке.
(Тут ещё есть имена — начиная с Дирихле — но я пока остановлюсь с историческими отсылками.) А я же собираюсь поговорить (в том числе) о том, что было посередине: о работах Чебышева "Об определении числа простых чисел, не превосходящих данной величины" (1848) и "О простых числах" (1850).
Обе эти работы есть в его "Избранных математических трудах", но прежде, чем на них посмотреть, давайте немного к поведению простых чисел "приноровимся".
Так вот — доля простых, конечно, стремится к 0. Но делает это очень медленно. Как 1/ln n. А натуральный логарифм, с точностью до постоянного множителя в ln 10 ≈ 2.30..., это практически количество цифр в записи числа. Так что, если мы возьмём числа от 1 до 10^{42} — нет, давайте его напишем полностью,
1.000.000.000.000.000.000.000.000.000.000.000.000.000.000,
так вот, в этом интервале простое число примерно каждое сотое (и это с учётом того, что половина из чисел чётная, а из нечётных треть делится на 3!).
Так что число простых уменьшается медленно-медленно, и если достаточное число раз "потыкать" — и, что очень важно, уметь достаточно быстро проверять получающиеся числа на простоту! — то при разумном количестве попыток (в сравнении с количеством цифр) на простое число практически "нельзя не наткнуться".
Собственно, без этого бы не работало шифрование RSA — для него нужно придумать два больших простых числа, причём надо, чтобы их произведение не смог разложить на множители атакующий, располагающий большой вычислительной мощностью. Так что из разумного размера таблиц простых (допустим на секунду, что простых чисел оказалось бы значительно меньше) p и q брать было бы нельзя: атакующий просто взял бы эти же таблицы и перебрал варианты пар чисел в них. А так — можно "потыкать-потыкать в случайные числа нужного размера, пока не наткнёшься на простое".
И кстати — давайте я порекламирую ролик Numberphile про герб Trinity Hall (кстати — это не Trinity College, у Тринити Холла на две сотни лет истории больше!). Там в качестве подарка один из выпускников, J. F. McKee, нашёл простое число, рисующее герб Trinity Hall псевдографикой!
(Кстати, в этом же ролике ещё и совершенно прекрасный Тадаси Токиеда (Tadashi Tokieda), но это уже тема для отдельного рассказа!)
1.000.000.000.000.000.000.000.000.000.000.000.000.000.000,
так вот, в этом интервале простое число примерно каждое сотое (и это с учётом того, что половина из чисел чётная, а из нечётных треть делится на 3!).
Так что число простых уменьшается медленно-медленно, и если достаточное число раз "потыкать" — и, что очень важно, уметь достаточно быстро проверять получающиеся числа на простоту! — то при разумном количестве попыток (в сравнении с количеством цифр) на простое число практически "нельзя не наткнуться".
Собственно, без этого бы не работало шифрование RSA — для него нужно придумать два больших простых числа, причём надо, чтобы их произведение не смог разложить на множители атакующий, располагающий большой вычислительной мощностью. Так что из разумного размера таблиц простых (допустим на секунду, что простых чисел оказалось бы значительно меньше) p и q брать было бы нельзя: атакующий просто взял бы эти же таблицы и перебрал варианты пар чисел в них. А так — можно "потыкать-потыкать в случайные числа нужного размера, пока не наткнёшься на простое".
И кстати — давайте я порекламирую ролик Numberphile про герб Trinity Hall (кстати — это не Trinity College, у Тринити Холла на две сотни лет истории больше!). Там в качестве подарка один из выпускников, J. F. McKee, нашёл простое число, рисующее герб Trinity Hall псевдографикой!
(Кстати, в этом же ролике ещё и совершенно прекрасный Тадаси Токиеда (Tadashi Tokieda), но это уже тема для отдельного рассказа!)
Image credit: Numberphile, "The Trinity Hall Prime"
Математические байки
Поскольку недавно был 200-летний юбилей Чебышева — давайте я чуть-чуть расскажу о простых числах — и про его работы о них. Среди первых 10 чисел есть 4 простых: 2, 3, 5, 7; среди первых 100 их 25, среди первой тысячи — 168, то есть их доля падает с 0.4 до…
Продолжим?
Мы в прошлый раз посмотрели на то, как доля простых чисел от 1 до n с ростом n уменьшается: как 1/ln n, так что, с одной стороны, она стремится к нулю — но с другой, делает это очень медленно (ибо логарифм это практически количество цифр в записи n, только умноженное на ln 10 ≈ 2.3).
Давайте теперь сделаем один шаг в переформулировке асимптотического закона: вместо того, чтобы считать простые числа "поштучно", посчитаем сумму их логарифмов. А именно — рассмотрим функцию
θ(x) = \sum_{p<=x} ln p.
Так вот, эквивалентная форма асимптотического закона распределения простых чисел, это что θ(x)~x. Потому что, опять же, логарифм меняется медленно-медленно. И, например, доля тех чисел от 1 до n, у кого логарифм меньше логарифма n хотя бы на 5% (или на 1%, или вообще на любую фиксированную величину) — стремится к 0 (потому что это 1/n^0.05, или 1/n^0.01, или...), так что ими можно пренебречь. Так что складывать ln p или умножить количество простых на ln n — почти одно и то же.
А в таком виде на это чуть приятнее смотреть. Например, потому что стоит сумма логарифмов простых чисел — то есть логарифм их произведения. Так что θ(n) — это логарифм произведения всех простых чисел, не превосходящих n.
Мы в прошлый раз посмотрели на то, как доля простых чисел от 1 до n с ростом n уменьшается: как 1/ln n, так что, с одной стороны, она стремится к нулю — но с другой, делает это очень медленно (ибо логарифм это практически количество цифр в записи n, только умноженное на ln 10 ≈ 2.3).
Давайте теперь сделаем один шаг в переформулировке асимптотического закона: вместо того, чтобы считать простые числа "поштучно", посчитаем сумму их логарифмов. А именно — рассмотрим функцию
θ(x) = \sum_{p<=x} ln p.
Так вот, эквивалентная форма асимптотического закона распределения простых чисел, это что θ(x)~x. Потому что, опять же, логарифм меняется медленно-медленно. И, например, доля тех чисел от 1 до n, у кого логарифм меньше логарифма n хотя бы на 5% (или на 1%, или вообще на любую фиксированную величину) — стремится к 0 (потому что это 1/n^0.05, или 1/n^0.01, или...), так что ими можно пренебречь. Так что складывать ln p или умножить количество простых на ln n — почти одно и то же.
А в таком виде на это чуть приятнее смотреть. Например, потому что стоит сумма логарифмов простых чисел — то есть логарифм их произведения. Так что θ(n) — это логарифм произведения всех простых чисел, не превосходящих n.
Ещё вместо произведения всех простых, не превосходящих n, можно взять наименьшее общее кратное N всех чисел от 1 до n — и посмотреть на его логарифм. В разложение этого НОКа N в произведение простых все простые, не большие n, попадают — но некоторые в степени, большей 1. А именно — каждое простое p входит в разложение N в той максимальной степени, в которой оно ещё не превосходит n. Поэтому его логарифм можно записать так:
ln N = \sum_{p,k: p^k<=n} ln p
(как раз каждое слагаемое ln p появляется нужное число раз)
Так вот — это и есть то, как определяется функция Чебышева ψ(x):
ψ(x):= \sum_{p,k: p^k<=x} ln p.
И ещё одна эквивалентная переформулировка асимптотического закона распределения простых чисел — это что ψ(x)~x. Потому что разница между ψ(x) и θ(x) в реальности пренебрежимо мала — она складывается только из тех простых p, которые не превосходят квадратного корня из x, а вклад каждого такого p не больше произведения
(ln n/ln p)*ln p = ln n,
то есть всего лишь логарифма ln n — "копеечный".
ln N = \sum_{p,k: p^k<=n} ln p
(как раз каждое слагаемое ln p появляется нужное число раз)
Так вот — это и есть то, как определяется функция Чебышева ψ(x):
ψ(x):= \sum_{p,k: p^k<=x} ln p.
И ещё одна эквивалентная переформулировка асимптотического закона распределения простых чисел — это что ψ(x)~x. Потому что разница между ψ(x) и θ(x) в реальности пренебрежимо мала — она складывается только из тех простых p, которые не превосходят квадратного корня из x, а вклад каждого такого p не больше произведения
(ln n/ln p)*ln p = ln n,
то есть всего лишь логарифма ln n — "копеечный".
Собственно, если вернуться к нашему примеру с n=10^42 —
n= 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000,
то там разница лишь для p<10^21,
p<1.000.000.000.000.000.000.000,
а вклад каждого такого p не больше ln n<100. Так что разница ψ(n)-θ(n) не превосходит
100.000.000.000.000.000.000.000,
что на 19 порядков меньше, чем их предсказываемое асимптотическим законом распределения значение — быть сравнимыми с n.
n= 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000,
то там разница лишь для p<10^21,
p<1.000.000.000.000.000.000.000,
а вклад каждого такого p не больше ln n<100. Так что разница ψ(n)-θ(n) не превосходит
100.000.000.000.000.000.000.000,
что на 19 порядков меньше, чем их предсказываемое асимптотическим законом распределения значение — быть сравнимыми с n.
И давайте я выложу сюда иллюстрацию из статьи "Обманчивая простота простых чисел" М. Королева в "Кванте", No.3 за 2020-й год.
Чтобы проиллюстрировать, что мы идём не совсем не туда — один кусочек из статьи "О простых числах" Чебышева. С одной стороны, формула выглядит довольно жутко (будем честны, я выбрал не самое простое место его статьи) — но с другой, мы уже видим, из каких частей её левая часть состоит, а скоро поймём и откуда тут что берётся.
Forwarded from Непрерывное математическое образование
Николай Николаевич Константинов (02.01.1932–04.07.2021)
выдающийся организатор математического образования, один из создателей системы мат. классов в Москве, Турнира Городов и Турнира Ломоносова…
«Есть знаменитая фраза из письма Пушкина Бенкендорфу, когда он пишет, что “имел на всё сословие литераторов гораздо более влияния, чем министерство, несмотря на неизмеримое неравенство средств”. Примерно то же самое мог бы — с полным правом — сказать Н. Н. Константинов про советское (российское) математическое образование высокого уровня…»
выдающийся организатор математического образования, один из создателей системы мат. классов в Москве, Турнира Городов и Турнира Ломоносова…
«Есть знаменитая фраза из письма Пушкина Бенкендорфу, когда он пишет, что “имел на всё сословие литераторов гораздо более влияния, чем министерство, несмотря на неизмеримое неравенство средств”. Примерно то же самое мог бы — с полным правом — сказать Н. Н. Константинов про советское (российское) математическое образование высокого уровня…»
Forwarded from Непрерывное математическое образование
https://youtu.be/x_g63q72XDQ
в 15:30 планируется трансляция лекции «Как растут кристаллы и кораллы» С.К.Смирнова на ЛШСМ-2021
в 15:30 планируется трансляция лекции «Как растут кристаллы и кораллы» С.К.Смирнова на ЛШСМ-2021
YouTube
С.К.Смирнов. Как растут кристаллы и кораллы (ЛШСМ-2021)
Лекция на XX Летней школе «Современная математика» имени Виталия Арнольда.
https://mccme.ru/dubna/2021/courses/smirnov-lect.html
Ратмино, 20.07.2021.
https://mccme.ru/dubna/2021/courses/smirnov-lect.html
Ратмино, 20.07.2021.
Forwarded from Непрерывное математическое образование
21 июля планируются трансляции двух лекций ЛШСМ-2021
https://youtu.be/5XrVptud7JE
в 11:15 А.П.Веселов. Математика алмазных упаковок
https://youtu.be/CiVhV9mt5fU
в 15:30 И.А.Дынников. Слова Арну-Рози
https://youtu.be/5XrVptud7JE
в 11:15 А.П.Веселов. Математика алмазных упаковок
https://youtu.be/CiVhV9mt5fU
в 15:30 И.А.Дынников. Слова Арну-Рози
Непрерывное математическое образование
21 июля планируются трансляции двух лекций ЛШСМ-2021 https://youtu.be/5XrVptud7JE в 11:15 А.П.Веселов. Математика алмазных упаковок https://youtu.be/CiVhV9mt5fU в 15:30 И.А.Дынников. Слова Арну-Рози
Про Веселова — мне ещё хочется порекламировать (запись) его потрясающей лекции "Магия марковских троек":
http://www.mathnet.ru/present17717
http://www.mathnet.ru/present17717
Математические байки
Photo
А вот комментарий про этот объект (точнее, про его верхнюю поверхность; а сам объект заслуживает отдельного рассказа!).
Forwarded from Непрерывное математическое образование
мы продолжаем
https://youtu.be/AFF5fMpnObk
22.07, 11:15 А.А.Гайфуллин. Гомологические сферы и алгоритмическая неразрешимость в топологии
https://youtu.be/sDlhukK8TH8
22.07, 17:15 Д.О.Орлов. ABC-гипотеза и ее следствия
https://youtu.be/AFF5fMpnObk
22.07, 11:15 А.А.Гайфуллин. Гомологические сферы и алгоритмическая неразрешимость в топологии
https://youtu.be/sDlhukK8TH8
22.07, 17:15 Д.О.Орлов. ABC-гипотеза и ее следствия
Математические байки
Да, тот курс был совершенно замечательный; и вот один из прекрасных результатов оттуда, который я не побоюсь назвать его жемчужиной. Есть такие интересные объекты — изгибаемые многогранники. Представим себе, что у многогранника грани жёсткие, "сделаны из дерева"…
А в дополнение — мне хочется вспомнить (и порекламировать) курс Гайфуллина с ЛШСМ-2018:
https://news.1rj.ru/str/mathtabletalks/2859
https://news.1rj.ru/str/mathtabletalks/2859
Telegram
Математические байки
Так вот, оказывается — и это совместный результат А.А.Гайфуллина и Л.С. Игнащенко 2017 (!) года — что изгибаемый многогранник не просто сохраняет свой объём в процессе изгибания, а любые его два положения в процессе изгибания равносоставлены друг другу: можно…
Forwarded from Непрерывное математическое образование
продолжаются лекции ЛШСМ-2021
https://youtu.be/GgcnKL0sCQQ
25.07, 09:30 В.Ю.Протасов. Замощения пространства и сжатие информации
https://youtu.be/X-rCgR9fPdM
26.07, 17:15 М.А.Цфасман. Алгебраические числа, алгебраические кривые и плотные упаковки шаров
https://youtu.be/B6RM6-P2ors
27.07, 09:30 Л.Д.Беклемишев. Модели и интерпретации
https://youtu.be/iKVxgvaJlGU
27.07, 15:30 С.Я.Житомирская. Электрон на решетке в магнитном поле и арифметические спектральные переходы
https://youtu.be/GgcnKL0sCQQ
25.07, 09:30 В.Ю.Протасов. Замощения пространства и сжатие информации
https://youtu.be/X-rCgR9fPdM
26.07, 17:15 М.А.Цфасман. Алгебраические числа, алгебраические кривые и плотные упаковки шаров
https://youtu.be/B6RM6-P2ors
27.07, 09:30 Л.Д.Беклемишев. Модели и интерпретации
https://youtu.be/iKVxgvaJlGU
27.07, 15:30 С.Я.Житомирская. Электрон на решетке в магнитном поле и арифметические спектральные переходы
Математические байки
Photo
Нерегулярная рубрика "новости ЛШСМ": Thomas Fernique привёз на школу куб.