?

Log in

No account? Create an account
красивое доказательство - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

красивое доказательство [дек. 11, 2017|12:59 pm]
Anatoly Vorobey
[Tags|]

(эта запись может быть интересна математикам и сочувствующим)

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

Теорема ван-дер-Вардена говорит следующее. Предположим, мы раскрасили все натуральные числа {1,2,3...} в конечное число цветов. Тогда можно найти сколь угодно длинные арифметические прогрессии одного цвета. Или подробнее: для любого K существуют такие a, d, что числа a, a+d, a+2d, ... a+(K-1)d все одного цвета в данной раскраске.

Теперь предположим, что нам дали какой-то конечный список простых чисел P = {p_1,..., p_n}. Моя цель - доказать, что есть еще какое-то простое число p, которого нет в этом списке. Это докажет, что простых бесконечное число.

Раскрасим все натуральные числа в 2^n (2 в степени n) цветов следующим образом. Цвет числа X - это набор из n нулей или единиц, где на i-м месте стоит четность того порядка, с которым простое число p_i входит в множители X. Например, если список простых начинается {2,3,5,7,11...}, и X = 90 = 2^1 * 3^2 * 5^1, то цвет X будет (1,0,1,0,0....) потому что 2 и 5 входят 1 раз (нечетное число => 1), а 3 входит 2 раза (четное число => 0), а все остальные простые 0 раз. Всего цветов столько же, сколько разных векторов из нулей и единиц длиной n, т.е. 2^n, конечное число. Значит, мы можем применить теорему ван-дер-Вардена, и для любого K, который я дам (пока что я оставляю за собой право его фиксировать), мне гарантирована арифметическая прогрессия a, a+d, a+2d... длиной K, в которой у всех членов одинаковая ЧЕТНОСТЬ порядков всех p_i.

Моя цель теперь - доказать, что я смогу гарантировать, что у первых двух членов прогрессии, a и a+d, одинаковы не только ЧЕТНОСТЬ порядков, но и САМИ порядки, т.е. каждый p_i входит в них в виде множителя одинаковое число раз. Если я это докажу, то теорема доказана - почему? Потому что любое число можно разбить на простые множители. a и a+d разные числа, поэтому их разбивка на простые множители должна как-то различаться. Но если для всех p_i она не различается, то должны быть ЕЩЕ какие-то простые числа кроме p_i. Другими словами можно сказать так: если поделить a и a+d на все простые степени всех p_i, которые в них входят, то раз мы делим на то же самое, должно остаться два РАЗНЫХ числа, одно больше другого; любой простой множитель большего из чисел будет каким-то новым простым, которого нет среди p_i.

Теперь я беру какое-нибудь p_i и хочу доказать, что его порядок в a и a+d одинаковый; для этого я обозначу его порядок в a и его порядок в d через a' и d':

a = p_i^a' * L
d = p_i^d' * M

где L и M не деляется на p_i. Какой в таком случае будет порядок p_i суммы? Легко видеть, что если a' и d' разные числа, то порядок суммы будет меньшим из них; например, если a' меньшее, то p_i^a' можно вынести за скобки, а в скобках останется L + p_i^(d'-a')M, и эта сумма не делится на p_i. Если же порядки a' и d' одинаковые, то не гарантировано, что порядок суммы будет такой же, потому что может случайно получится, что L+M в скобках делится на p_i и добавляет к порядку суммы.

Я хочу гарантировать, что a' < d', т.е. порядок p_i в a, начала прогрессии, меньше порядка p_i в d, ее периода. Тогда в соответствии с вышеказанным порядок p_i в сумме a+d тоже будет a', и будет равенство порядков при a и a+d для всех p_i, что мне и нужно. Как я это гарантирую?

Предположим сначала, что a' > d'. Тогда порядок p_i в сумме a+d будет d'. Мне известно, что a и a+d одного цвета, т.е. ЧЕТНОСТЬ их порядков a' и d' одинаковая, и следовательно они отличаются минимум на 2. Если я возьму достаточно большую длину прогрессии K > p_i, то мне гарантировано также, что a+p_i*d тоже того же цвета, то есть порядок p_i той же четности, что a' и d'. Но это число - сумма чисел с порядками a' и d'+1, где d'+1 меньший, поэтому его порядок равен d'+1, и его четность отличается от d'. Это противоречие.

Осталось разобрать только случай a' = d'. Тогда я рассмотрю числа a (с порядком a') и
a + jd = p_i^a'(L + jM), где j я еще не зафиксировал, но оно меньше длины прогрессии K (которую я еще не выбрал). Порядок a+jd равен a' плюс то, сколько раз p_i входит в сумму L+jM. Поскольку L и M взаимно простые с p_i, я могу (вычисляя по модулю p_i^2) подобрать такое j < p_i^2, чтобы L+jM делилось на p_i, но не на p_i^2, и таким образом добавляла ровно 1 к порядку суммы, и меняла его четность. Это опять противоречие к гарантии, которую дает теорема ван-дер-Вардена.

Для того, чтобы убрать возможность a' > d', мне достаточно было взять K > p_i; для того, чтобы убрать возможность a' = d', мне достаточно было взять K > p_i^2. Значит, выбрав изначально K, большее чем квадрат наибольшего из p_i, я смогу гарантировать a' < d' для всех p_i, и это приведет меня к новому простому числу, что и требовалось доказать.
СсылкаОтветить

Comments:
[User Picture]From: mubarizoruc
2017-12-11 11:46 am
Огромной длины доказательство, которое лень читать. Чем вас не устраивает обычное, простое доказательство через произведение простых чисел + 1
(Ответить) (Thread)
[User Picture]From: avva
2017-12-11 01:58 pm
Всем устраивает. Это просто шутка такая (хотя док-во серьезное).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: enjoy_reading
2017-12-11 11:49 am
Прикольное доказательство! Но честно говоря непонятно, чем оно лучше классического? Тем что не использует основную теорему арифметики? А теорема Ван дер Вардена как доказывается?
(Ответить) (Thread)
[User Picture]From: ilya_dogolazky
2017-12-11 12:11 pm
стандартное доказательство тоже ничего не использует (ни наличия разложения, ни его единственности): возьмём наименьший отличный от единицы делитель того самого числа "произведения всех плюс 1", вот он и будет новым простым. Обычно этот шаг не делают, держа в голове разложение, но оно тут лишнее. А вот как раз в конструкции в постинге требуется разложение, да и сильно опасаюсь, что и единственность его (иначе мутно как-то с раскраской)...
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: rwalk
2017-12-11 12:54 pm
Это пожалуй overkill - теорема ван дер Вардена весьма нетривиальна. А с доказательством Фюрстенберга с использованием нестандартной топологии на множестве целых чисел вы не знакомы? Вот оно действительно "красивое и на удивление несложное".
(Ответить) (Thread)
[User Picture]From: avva
2017-12-11 01:49 pm
Да, но оно как раз, если я верно помню,
тождественно евклидовому, просто скрывает его структуру за топологическими определениями.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: michael_ul
2017-12-11 01:37 pm
А как доказывается теорема ван-дер-Вардена?
(Ответить) (Thread)
[User Picture]From: avva
2017-12-11 01:58 pm
Есть элементарное док-во через индукцию по нескольким индексам (когда утверждение расширяется до "для каждых A,B,C есть такое К, что любая раскраска первых K натуральных чисел в C цветов содержат арифметическую прогрессию длиной A одновременно по B независимых периодов - т.е. a, a+b_1+...b_n, a+2b_1+...+2b_n итд.). Теорема ван-дер-Вардена оказывается частным случаем для B=1. Подробности есть напр. в википедии
https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem
(Ответить) (Parent) (Thread)
[User Picture]From: a_konst
2017-12-11 01:42 pm
Простите, а где красивое доказательство?
(Ответить) (Thread)
[User Picture]From: ivanoff272
2017-12-11 01:50 pm
как обычно, не вместилось на полях
(Ответить) (Parent) (Thread)
[User Picture]From: imfromjasenevo
2017-12-11 02:46 pm
троллинг ок
(Ответить) (Thread)
From: vsvor
2017-12-11 06:09 pm
Забавно. Классика из этой серии - через дзета-функцию.
(Ответить) (Thread)
From: Aleksey Kladov
2017-12-11 06:27 pm
Я в своё время достаточно много времени потратил на изучение МЦНМОшной книжки про Т. Ван дер Вардена, и в итоге понял, почему она работает. С тех пор забыл, конечно, и, как теперь оказалось, совершенно зря :(
(Ответить) (Thread)
From: (Anonymous)
2017-12-11 07:47 pm
Это доказательство должно быть близко программистам. Если всего простых чисел m, то всех чисел от 1 до x имеется не больше, чем (log_2 x)^m (потому что в разложении всякого такого числа на степени простых есть m сомножителей, и все показатели не больше log_2 x). Но (log_2 x)^m = o(x). (Из книжки Шеня и др. про колмогоровскую сложность)
(Ответить) (Thread)
[User Picture]From: livelight
2017-12-11 09:32 pm
Красиво :)
(Ответить) (Parent) (Thread)
[User Picture]From: hyperpov
2017-12-11 10:57 pm
Чисто для коллекции: произведение по всем простым p, сколько бы их там ни было, выражений 1/(1-1/p), как нетрудно понять, равно сумме ряда 1/n, который расходится. Все.
(Ответить) (Thread)
From: (Anonymous)
2017-12-11 11:07 pm
Очень давно читаю ваш журнал и такого рода посты-комментарии от вас меня всегда немного смущают и оставляют двоякое впечатление..

С одной стороны я шутку понял и слегка улыбнулся.

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

Я вот например как-то увидел что Вы в комментарии похвалили серию саузпарка. Решил даже посмотреть ее. Минут через 10 стало понятно что похвала была чистой воды сарказмом, чувствовал себя немного обманутым)

Понятно, что если у шутки приписать большими буквами "ШУТКА", то ничего хорошего не получится, но, тем не менее, заметив за вами такую особенность, призываю помнить что любая шутка с серьезным может быть принята за чистую воду
(Ответить) (Thread)
[User Picture]From: adaptatio
2017-12-13 04:28 pm
А вы знаете доказательство бесконечности числа простых чисел через трансцендентность числа Пи? :)
(Ответить) (Thread)
[User Picture]From: livelight
2017-12-13 07:45 pm
Рассказывайте :)
(Ответить) (Parent) (Thread) (Развернуть)