Мы наконец узнали, насколько большим должен быть набор чисел, чтобы он гарантированно содержал закономерность, называемую «полиномиальной прогрессией».
Некоторые закономерности в математике настолько редки, что их можно искать всю жизнь и не найти.
Другие случаются так часто, что их невозможно избежать.
Новый доказательство , представлено Сара Пилус из Оксфордского университета, показывает, что один числовой шаблон особенно важного типа по существу неизбежен: он гарантированно появится в любом достаточно большом наборе чисел, независимо от того, как они выбраны.
«Этим моделям свойственна некая нерушимость», — сказал Теренс Тао из Калифорнийского университета в Лос-Анджелесе.
Доказательство Пилюса касается последовательности чисел, называемой «полиномиальной прогрессией».
Их легко создать — вы сможете сделать свою собственную в кратчайшие сроки — и они охватывают связь между сложением и умножением чисел.
На протяжении десятилетий математики знали, что когда набор (или «набор») чисел небольшой, то есть когда он содержит относительно мало чисел, он может вообще не содержать никаких полиномиальных прогрессий.
Они также знали, что по мере роста набора оно в конечном итоге проходит определенный порог, после которого оно уже содержит такое количество чисел, что там обязательно встретится одна из этих последовательностей.
Это как тарелка супа с буквами из теста: чем больше у вас букв, тем больше у вас шансов составить из них слова.
Но до работы Пилюса математики не знали, что такое этот порог.
Ее доказательство дает ответ на этот вопрос — точная формула, определяющая, насколько большим должно быть множество, чтобы гарантированно содержать определенные полиномиальные прогрессии.
А до этого у математиков были лишь смутные представления о том, что среди целых чисел (1, 2, 3 и т. д.) существуют полиномиальные прогрессии.
Теперь они точно знают, где их искать.
Ищем шаблоны
Чтобы визуализировать эти закономерности, рассмотрим один из них, немного более простой, чем тот, с которым работал Пилус.Начнем с числа 2 и добавим три: 2, 5, 8, 11, 14 и т. д. Этот шаблон — начиная с одного числа и добавляя еще одно — называется «арифметической прогрессией».
Это одна из наиболее изученных и частых прогрессий в математике.
Что касается частоты появления арифметической прогрессии среди целых чисел, необходимо понимать две вещи.
Доказал один из них Эндре Семереди в 1975 году.
Сначала, сказал он, выберите длину своей арифметической прогрессии.
Это может быть шаблон с четырьмя членами (2, 5, 8, 11), или семью (14, 17, 20, 23, 26, 29, 32), или вообще с любым числом.
После этого он доказывает, что как только набор чисел достигнет определенного размера (который он не смог определить), обязательно возникнет арифметическая прогрессия этой длины.
Таким образом, он укрепил идею о том, что в достаточно больших наборах чисел где-то обязательно есть закономерность.
«Семереди, по сути, сказал, что полный хаос невозможен.
Какой бы набор вы ни взяли, в него всегда сможет втиснуться какая-нибудь конструкция», — сказал Бен Грин из Оксфорда.
Однако теорема Семереди ничего не говорит о том, насколько большим должен быть набор чисел, чтобы эти закономерности стали неизбежными.
Он просто сказал, что для арифметической прогрессии любой выбранной длины обязательно существует набор чисел неизвестного размера, который ее содержит. Более двух десятилетий спустя математики определили этот размер, доказав таким образом второй фундаментальный факт о законах арифметики.
В 2001 Тимоти Гауэрс из Кембриджского университета доказал что если вы хотите гарантированно найти, скажем, арифметическую прогрессию из пяти слагаемых, вам нужен набор чисел хотя бы определенного размера - и определить, какого размера он будет (точный размер описать сложно, эта формула включает огромные экспоненциальные числа).
Чтобы понять, что сделал Гауэрс, нужно понять, что имеют в виду математики, когда говорят о «размере» набора чисел и идее «достаточно большого размера».
Сначала выберите интервал на числовой прямой, скажем, от 1 до 1000 или что-то более случайное, например от 17 до 1016. Начало и конец интервала не имеют значения, важна только его длина.
Затем определите долю чисел из этого интервала, которую вы хотите добавить в набор.
Например, если вы создадите набор из 100 чисел от 1 до 1000, то размер вашего набора будет составлять 10% от интервала.
Доказательство Гауэрса работает независимо от того, как вы выбираете числа из этого множества.
Вы можете взять первые 100 нечетных чисел от 1 до 1000, первые 100 чисел, оканчивающихся на 6, или даже 100 случайных чисел.
И Гауэрс доказал, что независимо от метода, как только множество займет достаточно большое пространство (не обязательно 10%) в достаточно длинном интервале, в нем неизбежно появится арифметическая прогрессия из пяти членов.
То же самое он доказал для арифметической прогрессии любой длины.
«После Гауэрса мы знаем, что если мне дана арифметическая прогрессия любой длины, то любое подмножество» чисел любого заданного размера обязательно будет содержать эту прогрессию, — сказал Пилус.
Работа Пилус аналогична работе Гауэрс, только она сосредоточилась на полиномиальных прогрессиях.
В арифметической прогрессии мы выбираем одно начальное число и добавляем к нему другое.
В полиномиальной прогрессии, которую изучал Пилус, вы выбираете начальное значение и добавляете к нему степени другого числа.
Например: 2, 2 + 3 1 , 2 + 3 2 , 2 + 3 3 , 2 + 3 4 .
То есть 2, 5, 11, 29, 83. В ее прогрессии тоже было всего по одному термину для каждой степени – это требование упрощает работу с ними.
Эти полиномиальные прогрессии тесно связаны с такой важной закономерностью, как геометрическая прогрессия, которая образуется путем возведения числа в постоянно возрастающую степень: 3 1 , 3 2 , 3 3 , 3 4 ,.
Они естественным образом появляются во многих областях математики и физики и очаровывают математиков на протяжении нескольких тысячелетий.
Геометрические прогрессии менее распространены даже в больших наборах чисел, но если вы немного подправите их — скажем, добавив константу к каждому члену — вы получите полиномиальную прогрессию.
Но кажется, что они появляются повсюду.
«Можно создавать большие наборы чисел, не содержащие геометрической прогрессии.
Но если вы дадите себе немного свободы и сдвинете геометрическую прогрессию, создав полиномиальную прогрессию, то большие множества будут просто вынуждены их содержать, сказал он.
Шон Прендивилль из Ланкастерского университета, который работал с Пилусом над полиномиальными прогрессиями.
В 1996 году Виталий Бергельсон И Александр Лейбман доказал, что когда множество достигает достаточно большого размера, там должны появиться полиномиальные прогрессии — это был полиномиальный эквивалент работы Семереди.
Однако математики понятия не имели, насколько большим должно быть «достаточно большое» множество.
Пилюс ответил на этот вопрос контринтуитивным образом – задумавшись о том, какими свойствами должен обладать набор чисел, чтобы в нем не было таких закономерностей.
Борьба с шаблонами с шаблонами
Пилус хотел определить, насколько большим должен быть набор — какой процент чисел в интервале он должен содержать — чтобы гарантировать, что он будет содержать заданную полиномиальную прогрессию.Для этого она представила все способы, с помощью которых набор чисел может избежать прогрессии, а затем доказала, что за пределами определенного размера даже самые гениальные из этих стратегий не работают. Это задание можно рассматривать как соревнование.
Допустим, кто-то просит вас создать набор, содержащий половину чисел от 1 до 1000. Вы выиграете, если набор не будет содержать первые четыре члена полиномиальной прогрессии.
Как бы вы выбрали цифры? 
Сара Пилус из Оксфордского университета
Вы можете инстинктивно попытаться выбрать числа наугад. Но этот инстинкт будет неправильным.
«Большинство наборов находятся в середине нормальное распределение .
Они содержат среднее количество полиномиальных прогрессий», — сказал Прендивиль.
И это среднее значение гораздо больше требуемого от вас нуля.
Это как если бы вы выбрали случайного человека из всего населения планеты и получили человека, рост которого близок к среднему.
Если ваша цель — найти более редкий экземпляр высотой более 2 м, вам нужно будет быть более сосредоточенным в поисках.
Таким образом, чтобы выиграть соревнование по выбору чисел, вам нужен более организованный способ решить, какие числа включить в ваш набор из 500. Например, вы можете заметить, что, если вы выбираете только четные числа, вы можете исключить вероятность того, что набор будет содержат полиномиальные прогрессии, содержащие нечетные числа.
Прогресс! Естественно, таким образом вы увеличиваете вероятность того, что ваш набор будет содержать полиномиальные прогрессии, состоящие из четных чисел.
Однако суть в том, что, придумав структурированный способ выбора 500 чисел, можно исключить возможность найти в наборе конкретную полиномиальную прогрессию.
Другими словами, вам нужно следовать шаблону, чтобы избежать шаблона.
Пилус решил доказать, что по достижении определенного размера даже очень умело составленные множества все равно должны будут включать полиномиальные прогрессии.
По сути, она хотела определить критическую точку, в которой каждый раз, когда вы избегаете включения полиномиальных прогрессий одного типа, вы в конечном итоге получаете полиномиальные прогрессии другого типа - как в случае с четными и нечетными числами.
Для этого ей нужно было найти способ количественной оценки структуризации набора.
Измерение структуры
До публикации работы Пилюса многие математики пытались понять, когда именно в наборе чисел появляются полиномиальные прогрессии.Многие очень успешные математики делали это, но ни один из них не смог добиться большого прогресса в определении размера множества, которого оно должно достичь, чтобы содержать полиномиальные прогрессии различной длины.
Главным препятствием для них было то, что математики понятия не имели, как именно можно охарактеризовать структуры, чтобы избежать появления полиномиальных прогрессий.
Для этого существовал один потенциальный метод, но когда Пилус начал работать в этой области, его нельзя было применить к вопросам, касающимся полиномиальных прогрессий.
Этот метод возник в статье Гауэрса 2001 года об арифметических прогрессиях.
Гауэрс создал тест, назвав его «нормой Гауэрса», который обнаруживает структуры определенного вида в наборе чисел.
Тест выдает одно число, которое определяет степень структуры набора, то есть численно показывает, насколько далеко набор отошел от простого набора случайных чисел.
«Понятие «набор кажется случайным» не имеет четкого определения с математической точки зрения», — сказал Грин.
Гауэрс нашел способ дать количественную оценку этой концепции.
Набор может быть более или менее структурированным.
Наборы, содержащие случайные числа, не имеют структуры и поэтому, скорее всего, содержат числовые шаблоны.
Такие множества имеют низкую норму Гауэрса.
Множества, содержащие только нечетные числа или только числа, делящиеся на 10, имеют элементарную структуру.
Легко доказать, что при превышении определенного размера в наборах столь простой структуры также будут появляться различные закономерности.
Сложнее всего работать с наборами очень сложных конструкций.
Они могут выглядеть случайными, но в то же время быть построены по какому-то очень хитрому правилу.
Их норма Гауэрса высока, и они дают наилучшие шансы систематически избегать шаблонов по мере увеличения размера набора.
Поскольку Гауэрс использовал эти методы для ответа на вопросы, связанные с арифметическими прогрессиями, их нельзя было применить к вопросам, связанным с полиномиальными прогрессиями.
Арифметические прогрессии имеют равные интервалы, а числа в полиномиальных прогрессиях скачут очень активно.
Нормы Гауэрса были так же полезны для изучения полиномиальных прогрессий, как триммер для травы для удаления старой краски с дома: идея аналогичная, хотя и не совсем подходящая для этой работы.
В новом доказательстве Пилус использовал основную идею нормы Гауэрса, чтобы создать новый способ анализа структур, связанных с полиномиальными прогрессиями.
Она использовала технику понижения, чтобы доказать, что при работе с интересующими ее полиномиальными прогрессиями стоит беспокоиться только о простых структурах с низкой нормой Гауэрса.
Дело в том, что полиномиальные прогрессии настолько сильно меняются от одного члена к другому, что неизбежно преодолевают более слабые числовые барьеры — подобно слону, прорывающемуся через витрины и выбегающему из посудной лавки.
Формулу Пилюса сложно описать простыми словами.
Он включает в себя двойной логарифм длины начального интервала, из которого вы выбираете числа для своего набора.
Минимальный размер, который она обнаружит, не обязательно будет наименьшим из возможных — будущие исследования могут обнаружить, что истинный порог еще ниже.
Но до появления ее доказательства у математиков вообще не было количественного понимания возникновения гарантии наличия полиномиальных прогрессий.
«Она была первой, кто показал, насколько большим должен быть размер декораций», — сказал Прендивиль.
Доказательство Пилюса количественно отвечает на один вопрос, связанный с полиномиальными прогрессиями.
Теперь математики используют его в надежде ответить на другой вопрос — о том, когда полиномиальные прогрессии появляются в множествах, целиком состоящих из простых чисел, важнейших чисел в математике, упорно сопротивляющихся какой-либо последовательности.
Пока не появилось это доказательство, математики понятия не имели, как подойти к этому вопросу.
«Я надеюсь, что некоторые аргументы из моей работы можно будет применить к области простых чисел», — сказал Пилус.
Теги: #Научно-популярные #математика #множества #полиномы #арифметические прогрессии #геометрические прогрессии #полиномиальные прогрессии
-
Пятница. Программистский Бред 4.3
19 Oct, 24 -
Amazon Kindle 3 – Гарантийная Замена/Возврат
19 Oct, 24 -
Crm Продажи За Час
19 Oct, 24 -
Сайт Для Школы
19 Oct, 24 -
Ответ На Приглашение Друга.
19 Oct, 24 -
Databoom: Создавайте Приложения – Поддержим
19 Oct, 24
