красивое доказательство
Dec. 11th, 2017 12:59 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись может быть интересна математикам и сочувствующим)
Прочитал красивое и на удивление несложное доказательство теоремы о том, что есть бесконечно много простых чисел. Доказательств пользуется только одним продвинутым результатом: теоремой ван-дер-Вардена об арифметических прогрессиях, и пользуется ей довольно остроумно. Попробую пересказать тут.
Теорема ван-дер-Вардена говорит следующее. Предположим, мы раскрасили все натуральные числа {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, и это приведет меня к новому простому числу, что и требовалось доказать.
Прочитал красивое и на удивление несложное доказательство теоремы о том, что есть бесконечно много простых чисел. Доказательств пользуется только одним продвинутым результатом: теоремой ван-дер-Вардена об арифметических прогрессиях, и пользуется ей довольно остроумно. Попробую пересказать тут.
Теорема ван-дер-Вардена говорит следующее. Предположим, мы раскрасили все натуральные числа {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, и это приведет меня к новому простому числу, что и требовалось доказать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2017-12-11 11:46 am (UTC)no subject
Date: 2017-12-11 01:58 pm (UTC)no subject
Date: 2017-12-11 07:39 pm (UTC)Вообще количество троллинга и манипулятивных постов в последние годы у вас и впрямь зашкаливает, тут есть один мой собрат-аноним, считающий вас джинсовым манипулятором - так, прям, начинаю задумываться, а не прав ли он... :))
no subject
Date: 2017-12-11 11:49 am (UTC)no subject
Date: 2017-12-11 12:11 pm (UTC)no subject
Date: 2017-12-11 06:59 pm (UTC)no subject
Date: 2017-12-11 08:35 pm (UTC)no subject
Date: 2017-12-11 01:58 pm (UTC)no subject
Date: 2017-12-11 07:02 pm (UTC)no subject
Date: 2017-12-11 12:54 pm (UTC)no subject
Date: 2017-12-11 01:49 pm (UTC)тождественно евклидовому, просто скрывает его структуру за топологическими определениями.
no subject
Date: 2017-12-11 01:49 pm (UTC)no subject
Date: 2017-12-11 02:08 pm (UTC)no subject
Date: 2017-12-11 02:12 pm (UTC)no subject
Date: 2017-12-11 04:05 pm (UTC)no subject
Date: 2017-12-11 08:34 pm (UTC)no subject
Date: 2017-12-12 06:23 am (UTC)no subject
Date: 2017-12-12 07:52 am (UTC)no subject
Date: 2017-12-12 11:28 am (UTC)Множество всех целых чисел, не делящихся на n, можно представить как объединение n-1 арифм. прогрессий. Таким образом, если бы простых чисел было конечное кол-во, то множество целых чисел, не делящихся ни на одно простое, (т.е, {-1,1}) можно было бы представить как пересечение конечного кол-ва объединений конечных кол-в арифм. прогрессий. Следовательно, оно или было бы пустым, или содержало бы арифм. прогрессию. Противоречие.
no subject
Date: 2017-12-12 11:45 am (UTC)Это также показывает связь с стандартным док-вом. Подробное док-во утверждения про "значит содержит арифм. прогрессию" проясняет, что ее период равен p1*...*pn (в общем случае наименьшее общее кратное периодов прогрессий), так что стандартное док-во просто рассматривает конкретный подходящий член этой прогрессии. Мы можем еще больше их сблизить, рассматривая только положительные части прогрессий, и тогда вместо {-1,1} остается только {1}.
no subject
Date: 2017-12-11 01:37 pm (UTC)no subject
Date: 2017-12-11 01:58 pm (UTC)https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem
no subject
Date: 2017-12-11 01:42 pm (UTC)no subject
Date: 2017-12-11 01:50 pm (UTC)no subject
Date: 2017-12-11 01:52 pm (UTC)no subject
Date: 2017-12-11 04:24 pm (UTC)no subject
Date: 2017-12-11 06:03 pm (UTC)no subject
Date: 2017-12-11 02:46 pm (UTC)no subject
Date: 2017-12-11 06:09 pm (UTC)no subject
Date: 2017-12-11 06:27 pm (UTC)no subject
Date: 2017-12-11 07:47 pm (UTC)no subject
Date: 2017-12-11 09:32 pm (UTC)no subject
Date: 2017-12-11 10:57 pm (UTC)no subject
Date: 2017-12-11 11:07 pm (UTC)С одной стороны я шутку понял и слегка улыбнулся.
С другой стороны слооожна.
И никаких пояснений в посте о том что это шутка нету.
И зависает вопрос, сколько шуток такого рода я читая этот журнал принял за чистую монету.
Я вот например как-то увидел что Вы в комментарии похвалили серию саузпарка. Решил даже посмотреть ее. Минут через 10 стало понятно что похвала была чистой воды сарказмом, чувствовал себя немного обманутым)
Понятно, что если у шутки приписать большими буквами "ШУТКА", то ничего хорошего не получится, но, тем не менее, заметив за вами такую особенность, призываю помнить что любая шутка с серьезным может быть принята за чистую воду
no subject
Date: 2017-12-13 04:28 pm (UTC)no subject
Date: 2017-12-13 07:45 pm (UTC)no subject
Date: 2017-12-13 09:18 pm (UTC)Значит произведение по всем простым числам П 1/(1-1/p2) = ∑ 1/n2. Эта сумма как известно равна π2/6. π трансцедентно, значит π2/6 иррационально. Значит произведение П 1/(1-1/p2) не может быть конечным.
no subject
Date: 2017-12-13 09:38 pm (UTC)Особенно переход от первого произведения (с возможно конечным числом множителей, каждый из которых является суммой конечного числа членов) к форме с возможно конечным числом множителей, каждый из которых является суммой бесконечного числа членов.
А для степеней можно использовать тэг sup:
n2