Interested Article - Арифметическая комбинаторика

Арифметическая комбинаторика — междисциплинарная область математики, изучающая зависимость между структурами, образуемыми в поле (реже — в кольце ) операцией сложения и операцией умножения.

Подход к понятию структуры здесь аналогичен аддитивной комбинаторике и базируется в основном на размере множества сумм (или произведений), аддитивной (или мультипликативной) энергии и различных их комбинациях. В качестве поля обычно рассматриваются вещественные или рациональные числа ( , ) и вычеты по простому модулю ( ).

Неоднозначность терминологии и предмет статьи

Аддитивная и арифметическая комбинаторика — молодые, активно развивающиеся науки. Их методы и способы постановки задач очень похожи, поэтому, как правило, аддитивную комбинаторику считают частью арифметической. В этой статье описаны только темы, содержащие в том или ином виде обе операции поля или обратные к ним, то есть которые не относятся к чисто аддитивной комбинаторике (хотя последняя составляет довольно значительную часть арифметической).

Кроме того, здесь не затрагиваются вопросы об аддитивно-комбинаторных свойствах мультипликативных подгрупп и связанных с ними множеств, поскольку, хотя их определение и связано с умножением, но их мультипликативная структура жёстко зафиксироана, а комбинаторная составляющая этой науки предполагает ту или иную общность относительно степени структурированности (хотя бы с параметром, выступающим в роли константы).

Мотивация

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

Из этого следует, что комбинирование этих операций также влечёт разрастание: если , то

,

а добавление в конечного числа элементов влияет на рост лишь несущественно. Поскольку теорема сумм-произведений доказана лишь в слабой форме (далёкой от гипотезы), некоторые учёные стали интересоваться получением утверждений такого рода, которые следовали бы из более сильных форм гипотезы, чем доказанные, а впоследствии — в целом изучением соотношения между результатами разных комбинаций двух операций поля.

Например, гипотеза Эрдёша — Семереди о суммах-произведениях гласит, что

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

Задачи и результаты

В этом разделе для описания результатов используется общепринятые записи (пояснение приведено в O-нотации ):

  • означает, что
  • означает, что

Рациональные выражения

Постановка вопроса

Пусть рациональным выражением над множествами называется любая комбинация арифметических операций ( ) между ними. Под операцией здесь имеется в виду применение по принципу множества сумм:

Например, следующие множества являются рациональными выражениями над :

  • сами множества ;
  • — рациональное выражение над ;
  • .

По аналогии с аддитивной энергией, которая часто используется для оценки множества сумм, бывает удобно рассматривать число решений симметричного уравнения с рациональным выражением. Например,

Существенную часть проблематики арифметической комбинаторики можно выразить следующей постановкой вопроса.

Пусть — некоторое поле (либо бесконечное, либо достаточно большое из заданного семейства конечных), — рациональные выражения, причём хотя бы в одном из них используется или и хотя бы в одном или .

Пусть также для некоторых и множеств выполнены соотношения

Вопрос

Как при ограничено множество возможных значений в зависимости от ?

Примечание

Если поле конечное, то набор уместно дополнить параметром , где .

Например, гипотеза о суммах-произведениях утверждает, что если , , , то (здесь ).

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

Некоторые результаты

Об обобщении сумм и произведений:

;
;

Об обобщении энергий:

  • для любого если , то , причём при

Сдвиги

Постановка вопроса

Идея оценки рациональных выражений, объединяющих разные операции, исходит из того, что применение ко множеству аддитивной операции лишает его мультипликативной структуры. Этот же принцип можно расширить на случай, когда множество изменяется не сложной комбинаторной операцией поэлементного сложения, а обычным аддитивным сдвигом — прибавлением ко всем элементам множества одного числа. Ожидается, что от этого мультипликативная структура множества должна в большинстве случаев меняться (например, что если , то для некоторого при всех или почти всех ).

Вопрос

Как при фиксированном (но произвольном) зависят друг от друга мультипликативные свойства (размер множества произведений и мультипликативная энергия) множеств . А также каковы совместные мультипликативные свойства множеств при различных (например, существуют ли нетрвииальные оценки на )?

Некоторые результаты

  • если при простом , то:
  • , где при

Многочлены

Постановка вопроса

Идея комбинирования сложения и умножения естественным образом приводит к рассмотрению многочленов , то есть таких же рациональных выражений, но в которых одна переменная может появляться несколько раз (и тем самым оказывать более сложное влияние на структуру получающегося множества). Оказывается, в этом случае для обеспечения безусловного роста не обязательно использовать три копии множества (как в выражении ), а достаточно подобрать нужный полином от двух переменных. Впервые такое свойство заметил Бургейн для многочлена .

Также, по аналогии с теоремой сумм-произведений, изучаются оценки снизу на для произвольных многочленов .

Некоторые результаты

Первый результат Бургейна: если . Тогда для некоторого верно, что

При сравнении и большое значение имеет вырожденность многочлена . Если он вырожден, то есть представим в виде , где — многочлены и , то обе суммы могут оказаться малыми если — арифметическая прогрессия, ведь . Поэтому результаты формулируются только для невырожденных многочленов:

  • если , то
  • если , то

Матричное умножение

Свойства

Существуют результаты о множествах произведений набора матриц из той или иной матричной подгруппы (например, или группы Гейзенберга ). Строго говоря, эти результаты касаются одной групповой операции ( матричного умножения ), так что их можно отнести к аддитивной комбинаторике . Но слияние внутри определения этой операции и сложения, и умножения элементов , а также возникающая из этого некоммутативность делают её свойства очень нетипичными по сравнению с обычными групповыми операциями, вроде сложения вещественных чисел.

Например, множество матриц часто может возрастать от произведения на самого себя при очень простых условиях (большом размере, ограничении на отдельные элементы или отличии от подгрупп).

Некоторые результаты

Большинство результатов о матричных группах, когда они касаются произвольных наборов матриц, анализирует велличину , а не . Это не случайность, а техническая необходимость, связанная с некоммутативностью.

  • если , то для множества матриц (оно лежит в группе Гейзенберга) верно, что , где
  • пусть порождает всю группу и . Тогда
  • (для других групп возможна аналогичная оценка, зависящая от размерности её представлений )
  • если и , то структура сильно связана с подгруппами (эта связь может быть выражена в терминах )

Приложения

Аналитические методы изучения роста в группе и группах Шевале можно использовать для вывода специальной формы гипотезы Зарембы .

См. также

Список литературы

  • P. Erdös, E. Szemerédi. (англ.) // Birkhäuser Verlag. — 1983. — P. 213–218 .
  • Oliver Roche-Newton, Imre Z. Ruzsa, Chun-Yen Shen, Ilya D. Shkredov. On the size of the set (англ.) . — 2018. — arXiv : .
  • Oliver Roche-Newton, Ilya D. Shkredov. If is small then is superquadratic (англ.) . — 2019. — arXiv : .
  • Antal Balog. (англ.) // Publicationes mathematicae. — 2011. — Vol. 79 , iss. 3 . — doi : .
  • Ilya D. Shkredov, Dmitrii Zhelezov. (англ.) . — 2016. — arXiv : .
  • Brandon Hanson, Oliver Roche-Newton, Dmitrii Zhelezov. On iterated product sets with shifts (англ.) . — 2018. — arXiv : .
  • Brandon Hanson, Oliver Roche-Newton, Dmitrii Zhelezov. On iterated product sets with shifts II (англ.) . — 2018. — arXiv : .
  • Sophie Stevens, Frank de Zeeuw. (англ.) // Bulletin of the London Mathematical Society. — 2017. — Vol. 49 , iss. 5 . — doi : . — arXiv : .
  • Audie Warren. On Products of Shifts in Arbitrary Fields (англ.) . — 2019. — arXiv : .
  • Antal Balog, Oliver Roche-Newton, Dmitry Zhelezov. (англ.) // The electronic journal of combinatorics. — 2016. — Vol. 24 , iss. 3 . — doi : . — arXiv : .
  • И. Д. Шкредов. // Математический сборник. — 2017. — Т. 208 , вып. 12 . — doi : . — arXiv : .
  • Bryce Kerr, Simon Macourt. Multilinear Exponential Sums With A General Class Of Weights (англ.) . — 2019. — arXiv : .
  • Konstantin I. Olmezov, Aliaksei S. Semchankau, Ilya D. Shkredov. On popular sums and differences of sets with small products (англ.) . — 2019. — arXiv : .
  • Brandon Hanson, Oliver Roche-Newton, Misha Rudnev. Higher convexity and iterated sum sets (англ.) . — 2020. — arXiv : .
  • И. Д. Шкредов. // Труды Московского математического общества. — 2013. — Т. 74 , вып. 1 .
  • J. Bourgain. (англ.) // International Journal of Number Theory. — 2005. — Vol. 1 , iss. 1 . — doi : .
  • Doowon Koh, Hossein Nassajian Mojarrad, Thang Pham, Claudiu Valculescu. (англ.) // Proceedings of the American Mathematical Society. — 2018. — Vol. 146 , iss. 12 . — doi : . — arXiv : .
  • Van Vu. (англ.) // Mathematical Research Letters. — 2007. — Vol. 15 , iss. 2 . — doi : . — arXiv : .
  • Ilya D. Shkredov. Some remarks on products of sets in the Heisenberg group and in the affine group (англ.) . — 2019. — arXiv : .
  • Misha Rudnev, Ilya D. Shkredov. On growth rate in , the affine group and sum-product type implications (англ.) . — 2019. — arXiv : .
  • H. A. Helfgott. Growth in (англ.) . — 2009. — arXiv : .
  • Nikolay Nikolov, László Pyber. (англ.) // Journal of the European Mathematical Society. — 2007. — Vol. 13 , iss. 4 . — doi : . — arXiv : .
  • Nikolay G. Moshchevitin, Ilya D. Shkredov. On a modular form of Zaremba's conjecture (англ.) . — 2019. — arXiv : .
  • Ilya D. Shkredov. Growth in Chevalley groups relatively to parabolic subgroups and some applications (англ.) . — 2020. — arXiv : .

Примечания

  1. Обратное неверно — поскольку слово «аддитивная» образована от англ. addition (сложение), его употреблеие точно не уместно для предмета данной статьи. Например, Грин в на монографию Тао , начиная говорить о теореме сумм-произведений, упоминает, что отклоняется от определения аддитивной комбинаторики («Though I am shyingaway from a definition of additive combinatorics…»).
  2. .
  3. , замечание после теоремы 1.5
  4. Обозначение , используемое здесь и далее, не является общепринятым.
  5. См. пояснение на примере теоремы сумм-произведений в (теорема 1.1 и комментарий сразу после неё)
  6. .
  7. , следствие 2
  8. , подробнее см.
  9. , подробнее см.
  10. .
  11. , предложение 12
  12. , следствие 2.11
  13. Обратное, вообще говоря, неверно: мультипликативный сдвиг может никак не менять аддитивные свойства множества. Если — арифметическая прогрессия и , то для всякого . Но иногда получается использовать похожие идеи — см., например, лемму 2 в , где при доказательстве аналога проблемы Варинга в конечном поле формулируется подобное утверждение в терминах совместной аддитивной энергии о существовании нужного сдвига.
  14. , следствие 10
  15. .
  16. , следствие 5.8
  17. .
  18. , теорема 12
  19. , теорема 4.1
  20. .
  21. Многочлены, так или иначе связанные с ростом множесства в литературе часто называются расширяющими (expanders).
  22. См. раздел 5.2 в
  23. , теорема 2.1 (см. также русскоязычное изложение в , теорема 5.2)
  24. , теорема 1.10
  25. , теорема 1.2
  26. Любой элемент произведения матриц фактически представляет собой многочлен от элементов перемножаемых матриц
  27. См. замечание в в сноске на с. 3, а также тот факт, что неравенство Плюннеке — Ружа в некоммутативных группах имеет специальный вид.
  28. , теорема 2
  29. , теорема 2
  30. См. , предложение 2 и замечание в в начале раздела 1.3.1
  31. , теорема 1.1
  32. .
  33. .
Источник —

Same as Арифметическая комбинаторика