Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
10. Теорема Ван дер Вардена об арифметической прогрессии Теорема Ван дер Вардена об арифметической прогрессии имеет интересную историю. Боде высказал следующую ги- потезу. (А) Если натуральные числа разбиты каким-то образом на два класса, то для любого натурального числа водном из этих классов найдётся арифметическая прогрессия длины l те. данному классу принадлежат числа, a + d, a + 2d, . . . , a + (l − 1)d при некоторых a и Эта гипотеза быстро стала известной. Её пытались доказать многие математики. Но доказать эту гипотезу оказалось нелегко. Первые существенные результаты получили известные математики Э. Артин и О. Шрайер. Сначала Шрайер показал, что гипотеза Боде эквивалентна следующему утверждению. (Б) Для любого натурального числа l существует такое натуральное число N(l), что если числа 1, 2, . . . , N(l) разбиты на два класса, то один из этих классов содержит арифметическую прогрессию длины l. 590 Дополнение Затем Артин показал, что утверждение (Б) эквивалентно следующему утверждению. (В) Для любых натуральных l и k существует такое натуральное число N(l, k), что если числа 1, 2, . . . , N(l, разбиты на k классов, то один из этих классов содержит арифметическую прогрессию длины Утверждение (А) очевидным образом следует из (В. Но, как оказалось, доказывать удобнее всего именно утверждение (В, используя двойную индукцию пои по l. Такое довольно сложное доказательство как рази придумал Ван дер Варден в 1927 г. Разбиение множества на k классов можно наглядно представить как раскраску в k цветов. В таком случае утверждение (В) формулируется следующим образом. (В ′ ) Для любых натуральных l и k существует такое натуральное число N(l, k), что если числа 1, 2, . . . , N(l, раскрашены в k цветов, то найдётся одноцветная арифметическая прогрессия длины Впоследствии появились как новые доказательства теоремы Ван дер Вардена, такие обобщения. Мы обсудим одно существенное обобщение этой теоремы, доказательство которого сравнительно несложно. Это доказательство принадлежит П. Андерсону.* Рассмотрим в мерном пространстве множество точек, координаты которых — целые неотрицательные числа. Будем называть это множество решёткой, а точки этого множества будем называть точками решётки. Т е орем а Пусть S — конечное множество точек решётки. Тогда для любой раскраски точек решётки в цветов существует такое натуральное число a и такой вектор v с целыми неотрицательными координатами, что P. G. A n d e r s o n. A generalization of Baudet’s conjecture (Van der Waerden’s theorem) // Amer. Math. Monthly. 1976. V. 83. P. 359––361. ** Если читатель плохо знаком с понятием многомерного пространства или же совсем незнаком с этим понятием, то он может считать, что = 2 или 3; теорема Ван дер Вардена имеет дело с n = 1. 10. Теорема Ван дер Вардена 591 множество aS + v те. образ S при гомотетии с коэффициентом a и сдвиге на вектор v) одноцветное. При этом для числа a и для координат вектора v можно указать оценки, зависящие только от множества S и числа Замечание. Теорема Ван дер Вардена получается при n = 1 и S = {1, 2, . . . , При доказательстве теоремы удобно рассматривать куб со стороной N, состоящий из всех точек решётки с координатами от 0 до N −1. Этот куб мы обозначим K N ; он состоит из точек решётки, где n — размерность пространства. Утверждение теоремы для множества S можно сформулировать следующим образом. (A S ) Существует такое натуральное число N, зависящее от количества цветов k, что при любой раскраске точек куба в k цветов этот куб содержит одноцветное множество вида aS + План доказательства теоремы следующий. Если S состоит из одной точки, то утверждение (A S ) очевидно. Поэтому достаточно доказать, что если w — точка решётки, не входящая в S, то из утверждения (A S ) следует утверждение, где S ∪ w — множество, полученное из S добавлением точки w. Для доказательства этого нам потребуется следующее вспомогательное утверждение для каждого натурального числа Существует такое натуральное число N p , что для любой раскраски куба в k цветов найдутся натуральные числа a 1 , . . . , и вектор v с неотрицательными целыми координатами, для которых каждое из множеств (a 1 + . . . + a p )w + v, T 1 = a 1 S + (a 2 + . . . + a p )w + v, T 2 = (a 1 + a 2 )S + (a 3 + . . . + a p )w + v, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . T p = (a 1 + . . . + a p )S + одноцветное 592 Дополнение Дальнейшее доказательство состоит из двух шагов. Ш а г 1. Если утверждение (A S ) верно, то при всех натуральных верно утверждение Докажем сначала утверждение (C S,w,p ) при p = 1. В этом случае нужно доказать, что в некотором кубе существуют одноцветные множества a 1 w + v и a 1 S + v. Из свойства) следует, что в кубе существует одноцветное множество. Поэтому можно положить a 1 = a и расширить куб до куба так, чтобы для любой точки v куба точка aw + v лежала в кубе Теперь нужно доказать, что если верны утверждения) и (C S,w,p ), то верно и утверждение (C S,w,p+1 ). Это доказательство использует одну важную идею, на которую опиралось и первоначальное доказательство Ван дер Варде- на. Пусть задана раскраска решётки в k цветов. Сопоставим точке v куб v + K N . Этот куб состоит из точек, поэтому всего возможно различных раскрасок точек такого куба в k цветов. Сопоставим этим раскраскам новые цвета в количестве и окрасим такими цветами каждую точку в соответствии с раскраской куба v + K N . Теперь цветов будет гораздо больше, но новая раскраска обладает следующим свойством новый цвет точек u и v одинаков тогда и только тогда, когда старый цвет точек u + x и v + x одинаков для всех точек x куба K N , те. кубы u + и v + одинаково раскрашены в старой раскраске. Будем называть новую раскраску индуцированной; она зависит от исходной раскраски и от размера куба Пусть верны утверждения (A S ) и (C S,w,p ). Тогда существует такое натуральное число N p , что для любой раскраски куба в k цветов найдутся натуральные числа, . . . , и вектор v, для которых каждое из множеств, T 1 , . . . , одноцветное. Рассмотрим индуцированную раскраску в k ′ = цветов, соответствующую кубу Доказанное выше утверждение (C S,w,1 ) можно применить к этой раскраске. В результате получим, что существует куб 10. Теорема Ван дер Вардена 593 K N ′ , содержащий одноцветные (в индуцированной раскраске) множества a ′ w + и a ′ S + v ′ . Одноцветность в индуцированной раскраске множества a ′ S + означает, что вис- ходной раскраске кубы K N p + a ′ s + одинаково раскрашены для всех точек s множества S. Каждый из этих одинаково раскрашенных кубов содержит одноцветные множества+ a ′ s + v ′ , q = 0, 1, . . . , p, причём цвет этих множеств не зависит от s. Таким образом, получаем одноцветные множества a ′ S + T q + Добавив к ним одноцветное множество T ′ 0 = a ′ w + T 0 + получим требуемый набор одноцветных множеств (a ′ + a 1 + . . . + a p )w + v ′′ , T ′ 1 = a ′ S + (a 1 + a 2 + . . . + a p )w + v ′′ , T ′ p+1 = (a ′ + a 1 + . . . + a p )S + где v ′′ = v + Шаг. Если утверждение (C S,w,p ) верно при всех натуральных, то верно утверждение Мы воспользуемся лишь тем, что утверждение верно при p = k, где k — количество цветов. В таком случае получаем одноцветные множества T 0 , T 1 , . . . , T k . Этих множеств больше, чем цветов, поэтому у двух из них цвета одинаковые. Пусть, например, цвета множеств и T q , где < q, одинаковые. Напомним, что+ . . . + a r −1 )S + (a r + . . . + a q −1 )w + (a q + . . . + a p )w + v, T q =(a 1 + . . . + a r −1 )S + (a r + . . . + a q −1 )S + (a q + . . . + a p )w + Положим a ′ = a r + . . . + и (a 1 + . . . + a r −1 )s + (a q + . . . + a p )w + где s — некоторая точка множества S. Тогда a ′ (S ∪ w) + одноцветное множество требуемого вида Дополнение. Происхождение математических терминов Алгебра — в русском языке с 1717 г. Происходит от немецкого Algebra, которое, в свою очередь, имеет арабское происхождение. Арабский математик Мухаммед ибн Муса ал-Хорезми (787––ок. 850), уроженец Хивы, написал книгу под названием «Хисаб ал-джабр ва-л-мукабала» (Исчисление восполнения и противопоставления. Значительная часть этой книги была посвящена решению уравнений. Для решения уравнений ал-Хорезми применял две основные операции: ал-джабр восполнение) и ал-мукабала противопоставление. Операция ал-джабр заключалась в избавлении от членов со знаком минус водной части уравнения посредством добавления к обеим частям уравнения одного итого же члена. Операция ал-мукабала заключалась в сокращении равных членов в обеих частях уравнения. Словом ал-джабр вскоре стали называть все арабские трактаты на эту тему. Затем это слово распространилось на всю теорию уравнений. В таком виде оно пришло в Европу в XIV в. В течение долгого времени алгебра как рази была теорией уравнений. Алгоритм — латинизированный вариант имени арабского математика ал-Хорезми (787––ок. 850). В средневековой Европе алгоритмом назывались десятичная система счисления и способы вычисления в ней, поскольку именно благодаря латинскому переводу трактата ал-Хорезми Книга о сложении и вычитании на основе индийского исчисления в Европе познакомились с десятичной системой счисления. Десятичную систему счисления ал-Хорезми заимствовал у индийских математиков, что и видно из названия его трактата. Анализ — от латинского analysis, которое происходит от греческого слова, означающего разложение, растворение». Арифметика — от греческого arithmos (число. В греческом языке так называли только натуральные числа и положительные рациональные числа. Важнейший древнегре- 11. Происхождение математических терминов 595 ческий трактат о свойствах натуральных и рациональных чисел назывался Арифметика и книга о многоугольных числах. Его автором был Диофант. Иррациональные числа — от латинского irrationalis (неразумный. Первоначально в греческом языке использовался термин arretos, который одновременно означал иррациональный, невыразимый в числах и «священный, тайный». Вероятно, это сыграло роль в возникновении легенды, согласно которой математик Гиппас из пифагорейской школы погиб в море из-за того, что нечестиво разгласил непосвящённым учение об иррациональных величинах, которое зародилось в пифагорейской школе и хранилось в строгой тайне. Затем появился термина после него — alogos, калькой которого и является латинское Катет — от греческого kathetos (перпендикуляр). Квадрат — от латинского quadratum (четырёхугольник). Куб — от латинского cubus, которое происходит из греческого языка. Первоначально означало игральная кость». Линия — от латинского слова linea, которое означает «льняная» (имеется ввиду льняная нить). Математика — от греческого mathematike, которое, в свою очередь, происходит от слова mathema (наука. На происхождение этого термина большое влияние оказала философская школа пифагорейцев. Пифагорейцы делились на «математиков» и «акусматиков». Акусматики не обучались наукам им давали лишь устные наставления — «акусмы» (от akustikos — слуховой. Математики же обучались науками занимались доказательствами. Пирамида — от греческого слова pyramis, которым греки называли египетские пирамиды. В свою очередь, греческое слово происходит от древнеегипетского слова «пурама», которым называли пирамиды сами египтяне. Призма — от греческого слова prisma, которое означает «опиленная» (имелось ввиду опиленное бревно 596 Дополнение Пропорция — от латинского proportio; так Цицерон пе- ревёл греческий термин Платона analogia (аналогия). Радиус — от латинского radius (радиус, луч). Расстояние — калька французского Ромб — от латинского rombus, которое происходит из греческого языка и означает бубен. Раньше бубны имели не круглую форму, а форму квадрата или ромба. Сфера — от греческого слова sphaira, которое означает «мяч». Точка — от тыкать, ткнуть. Аналогично латинское punctum (точка) происходит отколю. От этих латинских слов происходят русские слова пункт, пункция, пунктуация. В греческом языке первоначально использовался термин semeion (знак, признак, которому соответствует латинское signum. (Именно такой термин употреблял Евклид) Позднее, соврем н Аристотеля, получил распространение термин stigma (укол, которому как рази соответствует латинское Трапеция — от латинского слова trapezium, которое происходит из греческого языка и означает столик. От этого же корня происходит слово трапеза, которое по-гречески означает «стол». Фигура — в русском языке с 1701 г. Происходит из латинского figura от fingo (образовывать, давать форму). В греческом языке использовался термин schema (наружный вид, образ, форма. От этого греческого слова происходит русское «схема». Цилиндр — от латинского слова cylindrus, которое происходит из греческого языка и означает валик, каток УКАЗАТЕЛЬ ИМЁН Абель Н. Х. 285, 571, 576 Артин Э. 546, 589 Безу Э. 125 Берж К. Бернулли И. 497 Бине Ж. Боде П. Ж. А. Больцано Б. 294 Бюдан Ф. 435 Валлис Дж. Ван дер Варден Б. Л. 589 Вандермонд АТ. 179 Варинг Э. 18, Вейерштрасс К. 294 Венн Дж. 532 Виет Ф. Вильсон Дж. Галуа Э. 285, Гаусс К. Ф. 296, 404–406, 436, 438, 496, 549 Гёльдер О. Гильберт Д. 544, 545 Горнер У. де Гуа Ж. П. де Морган А. Декарт Р. дель Ферро С. 285 Дэвенпорт Г. Евклид 43, 49, 203, 402, 437, 485, 549 Золотарёв Е. И. 405 Йенсен И. Кантор Г. 534 Кардано Дж. 285 Карлсон Ф. 387 Касселс Дж. 546 Каталан Э. Ш. Коши О. Л. 17, 97, 98, 294, 295, 337 Кронекер Л. 465, 579 Кэли А. Лагранж Ж. Л. 66, 129, 286, 336, 403, 408, Лейбниц Г. В. 364 Лиувилль Ж. Лобачевский НИ. 472 Лопиталь Г. ФА. Люка Э. 436 Маклорен К. Марков А. А. 162 Мейсон Р. 584 Мёбиус А. Ф. 403 Минковский Г. 102 Моцкин Т. 544 Муавр А. 276, 550 Мюрхед Р. Ньютон И. 130, 334, 340, 364, 440 Пелль Дж. 161, 200, 486, 589 Пфистер А. 546 Рамануджан С. 75, 210, 441 Ролль М. 335 Руффини П. 285, 571 Руше Э. 434 Стирлинг Дж. 387 Тарталья Н. Тейлор Б. 341 Уитни Х. 564 Фарей Дж. Ферма П. 335, 399, 464, 546, 584, Феррари Л. Фибоначчи 201, Фурье Ж. Б. Ж. Холл Ф. Чебышев ПЛ. 410, 442 Шевалле К. 402 Шрайер О. Штурм Ж. Ш. Ф. 436 Эйзенштейн Ф. ГМ, Эйлер Л. 182, 270, 287, 388, 400, 402, 403, 410, 464, 485, 498, 511, 546 Эллисон У. 546 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ d-ичная запись числа 259 А Абеля теорема абсолютно сходящееся бесконечное произведение аксиома фундирования алгебраическая функция алгебраическое число 444 — — вполне вещественное 445 — — целое алгоритм Евклида 43, 203, 437, 485 — Кронекера амплитуда гиперболическая 325 ареакосинус гиперболический 325 ареакотангенс гиперболический 325 ареасинус гиперболический 325 ареатангенс гиперболический 325 арифметики основная теорема 43 ассоциативное кольцо ассоциативность астроида 367, 518 Б безопасности парабола 518 Безу теорема Бернулли многочлены 497 — числа бесконечное произведение абсолютно сходящееся 389 — — сходящееся 388 Бине формула биномиальный коэффициент 178 Больцано––Вейерштрасса теорема 294 В Валлиса формула 365 Вандермонда свёртка вариация функции на отрезке 314 Варинга формула 18, Вейерштрасса теорема 294, 312 Венна диаграмма верхняя интегральная сумма вершина графа взаимно однозначное отображение простые числа 49 Виета теорема Вильсона теорема вогнутая функция возрастающая последовательность вполне вещественное алгебраическое число вторая производная вторые разности выпуклая функция выражение числа в квадратных радикалах 556 Предметный указатель 599 вырожденная критическая точка вычет квадратичный 403 |