Главная страница
Навигация по странице:

  • Анализ

  • Иррациональные числа

  • Квадрат

  • Призма

  • Радиус

  • Сфера

  • Цилиндр

  • Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В


    Скачать 3.28 Mb.
    НазваниеУчебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
    Дата16.10.2022
    Размер3.28 Mb.
    Формат файлаpdf
    Имя файлаalgebra.pdf
    ТипУчебное пособие
    #736986
    страница70 из 71
    1   ...   63   64   65   66   67   68   69   70   71
    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
    1   ...   63   64   65   66   67   68   69   70   71


    написать администратору сайта