Адитивна комбінаторика

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Адитивна комбінаторика (від англ. addition — додавання) — міждисциплінарна галузь математики, що вивчає взаємозалежність різних кількісних інтерпретацій поняття структурованості[1] групи (як правило, скінченної), а також аналогічні властивості похідних від багатьох структур, що використовуються в цих інтерпретаціях. Крім того, адитивна комбінаторика вивчає структурованість у різних сенсах деяких специфічних множин або класів множин (наприклад, підмножин простих чисел або мультиплікативних підгруп).

Таким чином, основним об'єктом вивчення є скінченні множини, якомога абстрактніші, обмежені іноді лише у своїх розмірах, що уподібнює цю науку з комбінаторикою. Однак, на відміну від комбінаторики, де елементи множин ідентифікуються тільки відмінністю один від одного і належністю до тих чи інших розглянутих множин, в адитивній комбінаториці кожен елемент множини має чітке значення, і між ними з'являються додаткові взаємозв'язки, що випливають із їхніх значень і властивостей операції групи (і, можливо, специфічних законів, притаманних даній групі).

Адитивна комбінаторика тісно пов'язана з арифметичною комбінаторикою, предметом вивчення якої є співвідношення підмножини поля (а не просто групи, як тут) одразу з двома операціями — додаванням та множенням.

Передумови виникнення

[ред. | ред. код]

Адитивна теорія чисел

[ред. | ред. код]

Наочним прикладом є теорема ван дер Вардена — вона каже, що за будь-якого розбиття натуральних чисел на скінченне число класів, хоча б у одному з класів буде наявна арифметична прогресія (будь-якої заданої довжини). При цьому очевидно, що в будь-якому розбитті є клас, щільність чисел у якому більша, ніж в інших, і інтуїтивно здається, що прогресія має міститися в цій множині — адже тут найбільше елементів, тобто найбільше можливостей. Очевидно також, що найбільша множина матиме додатну (ненульову) щільність. Однак довести, що абсолютно будь-яка множина натуральних чисел додатної щільності містить у собі арифметичну прогресію, не виходить просто через теорему ван дер Вардена — за нею прогресія може опинитися в будь-якому класі, навіть найменшому. Для доведення наявності прогресії в будь-якій щільній множині доводиться залучати значно складніші засоби — розв'язання цієї задачі отримало назву теореми Семереді, яку вважають класичним адитивно-комбінаторним результатом.

і виводив оцінку для квадрата її модуля: Оцінка цієї суми виходила суто комбінаторно зі властивостей виразу при заміні змінної [2]. Таким чином, мультимножина різниць давала інформацію про структуру множини самих квадратичних лишків. У адитивній комбінаториці діє схожий підхід, коли вже множина, а не мультимножина різниць (або сум, добутків тощо) елементів із заданої множини дає інформацію про структуру цієї множини. Такий перехід — від мультимножини до множини — пов'язаний із переходом від кількості розв'язків того чи іншого рівняння (наприклад, ) до подання чисел у тому чи іншому вигляді (наприклад, у вигляді ), який у принципі характерний для методу тригонометричних сум.

Окремим фундаментом для розвитку нової науки про поелементні суми множин (множини сум ) стала доведена Григорієм Фрейманом[ru] теорема про будову множин з малим подвоєнням (тобто множин, множина сум двох елементів яких має малий розмір, або простіше кажучи, суми елементів із яких часто збігаються)[3].

Теорія Ремзі

[ред. | ред. код]
Докладніше: Теорія Ремзі

Теорія Ремзі, що виникла в першій половині XX століття, також аналізувала різні уявлення про структурованість. Твердження теорії Ремзі стосуються наявності хоча б малого «острівця» структурності в досить складних (за кількістю елементарних частин) об'єктах[4].

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

Питання подання чисел у вигляді суми елементів із небагатьох даних множин математики розглядали ще з давніх часів. Класичними прикладами є задачі подаваності будь-якого числа сумою чотирьох квадратів (теорема Лагранжа про чотири квадрати) або будь-якого парного числа, більшого від трьох, сумою двох простих (проблема Гольдбаха). Якщо позначити через множину всіх квадратів невід'ємних чисел, то в термінах адитивної комбінаторики (див. розділ з позначеннями нижче) теорему Лагранжа можна записати як

Тригонометричні суми

[ред. | ред. код]

Однак теорія Ремзі розглядає не підмножини, а розбиття даної множини (наприклад, множини ребер графа, натуральних чисел або частини булеана скінченної множини), і результат про структуру має на увазі наявність структурованості в одного з елементів розбиття, і, як правило, незрозуміло в якого. Отже, про якусь окрему підмножину нічого сказати не можна.

У ході розв'язування подібних задач виникали й інші аналогічні, з іншими множинами, але схожими формулюваннями. Усе це сформувало галузь математики, звану адитивною теорією чисел.

Важливим поняттям адитивної комбінаторики є множина сум

Разом з тим, перші результати, які можна за духом віднести до адитивно-комбінаторних, зароджувалися на початку XX століття саме як частина теорії чисел (називаної також комбінаторною теорією чисел)[1]. Таким, наприклад, є метод Шнірельмана для вирішення проблеми Гольдбаха (який Линник також застосував до проблеми Воринга) — він заснований на теоремі Шнірельмана про множину сум чисел із двох довільних множин, про які відома тільки їх щільність[5] (слід зауважити, що при цьому саме специфічне визначення щільності за Шнірельманом, використане в цій теоремі, в адитивній комбінаториці як об'єкт для вивчення не прижилося).

Теорема Фреймана

[ред. | ред. код]

Проте адитивну комбінаторику не варто сприймати як узагальнення чи розвиток адитивної теорії чисел — хоча задачі останньої можна зручно записати в термінах адитивної комбінаторики, та її загальні методи до них, зазвичай, не застосовні. Теорія чисел завжди розглядає множину спеціального вигляду — прості числа, квадрати, інші степені, числа з малою кількістю дільників тощо. Адитивна комбінаторика намагається зрозуміти структуру додавання як таку, вивести якомога загальніші результати.

Питання про суми елементів з тієї чи іншої множини розглядали також Ердеш і Семереді без уведення спеціальної символіки для позначення підсумовування множин[6].

Предмет вивчення

[ред. | ред. код]

Множина сум

[ред. | ред. код]

Ще Гаус, перший дослідник тригонометричних сум, виявив через них зв'язок розподілу всіх можливих різниць чисел із даної множини і самої множини. Досліджуючи квадратичні лишки, Гаус розглядав суму

для скінченних множин , де  — група. Розмір такої множини визначається структурою і відносно операції . Якщо і  — арифметичні прогресії, то мала. А якщо, наприклад, вибрано випадково за схемою Бернуллі, то дуже велика. Проміжні випадки між зазначеними двома якраз і становлять адитивно-комбінаторний інтерес.

Крім того, цікава сама по собі структура множин . Зокрема, станом на 2018 рік немає загальних критеріїв (крім прямого перебору), які дозволяють визначити, чи подається дана множина у вигляді .

Пов'язувані характеристики множин

[ред. | ред. код]

У таблиці нижче наведено теореми та нерівності адитивної комбінаторики, що пов'язують різні характеристики підмножин груп. Твердження, вказане в комірці, пов'язує характеристики, зазначені в її рядку та стовпці. Наведено лише деякі, найвідоміші, з таких теорем.

Для стислості в заголовках використано такі скорочення:

  • Щільність множини для скінченної групи  — величина або закон її асимптотичного зростання зі зростанням розміру , а для нескінченних  — асимптотична щільність (або закон розподілу) в ;
  • УАП (від «узагальнена арифметична прогресія») — наявність у множині великих арифметичних прогресій, нетривіальних узагальнених арифметичних прогресій чи їх великих частин, а також, навпаки, можливість покрити множину (чи її більшу частину) невеликою арифметичною прогресією;
  •  — розмір та будова множини сум (а також різниць та комбінацій сум та різниць) — зокрема, можливість подати будь-який елемент групи як суму заданої кількості елементів даної множини;
  •  — подаваність множини або великої її частини як множини сум (а також різниць і комбінацій сум і різниць) чисел з невеликої кількості множин, тобто розв'язність рівняння множин для заданої , можливо, навіть за певних умов на (наприклад, ), де означає суму Мінковського;
  • коефіцієнти Фур'є маються на увазі для характеристичної функції множини і функцій, що визначаються через неї, а також їх статистика — різного роду норми, кількість елементів із великим значенням і структура їх множини;
  • ЧРР (від «число розв'язків рівняння») — число розв'язків різних лінійних рівнянь (зокрема, адитивна енергія) або систем рівнянь, у яких змінні набувають значень із заданих множин, а також співвідношення кількості їх розв'язків.

Також у комірках використано кілька специфічних позначень:

  •  — коефіцієнт Фур'є характеристичної функції множини ,
  •  — адитивна енергія,
  •  — таку функцію називають балансовою функцією множини , оскільки .
Щільність УАП Коефіцієнти Фур'є ЧРР
Щільність
УАП Теорема Семереді
Нерівність Шнірельмана, Теорема Фюрстенберга — Шаркозі[en] Теорема Фреймана[en]
при великих
і містять довгу а. п.[7][8]
Нерівність Плюннеке ― Ружі
Коефіцієнти Фур'є Принцип невизначеності[9] Якщо , мала, то містить а. п. довжини 3[10] Якщо і малі, то велика
ЧРР Теорема Рота Якщо  — а. п., то [11] Зі співвідношень адитивних енергій можна зробити висновки про структуру множини[12] Якщо , то

Деякі використовувані поняття

[ред. | ред. код]

Норма Гауерса[en] — узагальнення поняття коефіцієнтів Фур'є, придумане Вільямом Гауерсом під час доведення теореми Семереді.

Ізоморфізм Фреймана — відображення з підмножини однієї групи до підмножини іншої, що зберігає відношення рівності сум заданої кількості елементів множини.

Скінченну множину дійсних чисел називають опуклою послідовністю (або опуклою множиною), якщо для , тобто якщо є образом відрізка для деякої строго опуклої функції[13]. Властивості таких множин широко вивчає адитивна комбінаторика[14][15][16][17]. Це поняття не слід плутати з опуклою множиною у звичному значенні.

Множина Бора — структура з малим подвоєнням, яку іноді використовують у доведеннях як ослаблений аналог поняття підпростору[18]. Визначається як множина елементів поля, на яких усі адитивні характери із заданого сімейства мають мале значення. Множини Бора містять у собі великі узагальнені арифметичні прогресії, отже, наявність у множині прогресій іноді доводиться через наявність у ній потрібної множини Бора.

Майже періодична функція — функція така, що норма досить мала для деякого і для всіх , де  — деяка множина (наприклад, множина Бора). На таких множинах побудовано одне з доведень теореми Рота[19].

Множина великих тригонометричних сум (іноді називана спектром) множини  — множина лишків , для яких сума (коефіцієнт Фур'є) має великий модуль[20].

Дисоціативна множина  — множина, для якої лінійні комбінації рівні нулю, де , тільки коли всі рівні нулю. Зокрема, це означає, що суми елементів із двох різних підмножин завжди різні[20]. Дисоціативність можна розглядати як аналог лінійної незалежності над .

Методи вивчення

[ред. | ред. код]

Елементарні методи

[ред. | ред. код]

Звичайно, попри існування потужних та складних методів вивчення теорем адитивної комбінаторики, деякі прийоми та задачі допускають елементарний опис. Із нерівності Коші виводяться властивості адитивної енергії, що застосовуються майже повсюдно. Загалом за елементарного підходу часто аналізують число розв'язків тих чи інших рівнянь. Також часто застосовують аргумент середнього[en] — наприклад, при розкладанні числа розв'язків рівняння на суму числа розв'язків за того чи іншого значення окремої змінної[21].

Елементарними методами можна довести теорему Рота[22] та теорему Коші — Девенпорта[23].

Однак багато доведень, отриманих іншими методами, не мають елементарних аналогів.

Комбінаторні методи

[ред. | ред. код]

Одним із знакових комбінаторних доведень адитивної комбінаторики є перше з доведень теореми Семереді[24] — у ньому Семереді сформулював і використав так звану лему про регулярність, що стосується чистої теорії графів. Аналогії з цією теорією застосовуються і при доведенні особливих версій нерівності Плюннеке — Ружі або оцінок типу Балога — Семереді — Гауерса[25].

Алгебричні методи

[ред. | ред. код]

Алгебраїчні методи в адитивній комбінаториці використовують властивості многочленів, які будуються на основі тих чи інших множин. Степені таких багаточленів, як правило, залежать від розмірів множин, що вивчаються, а множина коренів многочленів може дати ту чи іншу інформацію про суми, перетини тощо початкових множин.

Прикладом засобу для застосування такого методу є комбінаторна теорема про нулі. За допомогою неї можна доводити теорему Коші — Девенпорта та її узагальнення[23].

Інші застосування алгебричного методу можна знайти в доведеннях теореми Рота для деяких груп спеціального виду[26][27][28] або в оцінці розміру перетинів зсувів мультиплікативних підгруп полів і доведенні проблеми Воринга для простого поля (для цього використовується, зокрема, метод Степанова)[29].

Аналітичні методи

[ред. | ред. код]

Основним аналітичним засобом у адитивній комбінаториці є коефіцієнти Фур'є. Це зумовлено тісним зв'язком операції взяття коефіцієнта Фур'є з операцією згортки функцій. Коефіцієнти Фур'є застосовано ще при першому доведенні теореми Рота[30]. Їх узагальненням є норми Гауерса, науку про які також називають аналізом Фур'є вищих порядків[20].

На прикладі коефіцієнтів Фур'є (зокрема їх застосування до доведення теореми Рота) найкраще ілюструється так званий ітеративний аргумент, коли розгляд довільної множини розбивається на два випадки — коли множина не має великих (відносно розміру множини) коефіцієнтів Фур'є і коли має. У першому випадку можна безпосередньо скористатися властивостями коефіцієнтів Фур'є, а в другому — знайти підструктуру множини з більшою щільністю в нескінченній арифметичній прогресії, причому настільки більшою, що кількість таких можливих кроків до досягнення граничної щільності буде обмежена величиною, що залежить від загальної щільності початкової множини. Це виявляє ідею поділу на випадок псевдовипадкової множини та множини з якоюсь глобальною структурою. Така ідея знайшла свій відбиток і в інших методах[1][10].

Інший аналітичний підхід полягає в дослідженні майже періодичності функцій, пов'язаних із характеристичними функціями досліджуваних множин[31].

Ергодичні методи

[ред. | ред. код]

Ергодичний підхід передбачає застосування до задач адитивної комбінаторики результатів із теорії динамічних систем. Вперше цей підхід застосував Гілель Фюрстенберг до теореми Семереді[32], але незабаром виявилося, що він допускає узагальнення на значно ширше коло задач.

Теорія динамічних систем часто дозволяє доводити результати, недоступні для переформулювання іншими методами, але при цьому не здатна дати жодних кількісних оцінок (наприклад, оцінок щільності множини в теоремі Семереді)[33].

Інші методи

[ред. | ред. код]

Адитивна комбінаторика використовує й деякі інші галузі:

Деякі дослідники

[ред. | ред. код]

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. а б в Постнаука, И. Д. Шкредов, «Аддитивная комбинаторика». Архів оригіналу за 18 серпня 2021. Процитовано 11 червня 2018.
  2. Виноградов, 1971.
  3. Фрейман, 1966.
  4. Грэхем, 1984.
  5. Гельфанд, 1962, с. 9—43.
  6. Erdős, Paul; Szemerédi, Endre (1983), On sums and products of integers (PDF), Studies in Pure Mathematics. To the memory of Paul Turán, Basel: Birkhäuser Verlag, с. 213—218, doi:10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, MR 0820223 Источник (PDF). Архів оригіналу (PDF) за 24 травня 2013. Процитовано 11 червня 2018. {{cite web}}: Недійсний |deadurl=unfit (довідка).
  7. Ernie Croot, Izabella Laba, Olof Sisask, "Arithmetic Progressions in Sumsets and L^p-Almost-Periodicity". Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  8. Tom Sanders, "Additive structures in sumsets". Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  9. Terence Tao, "An uncertainty principle for cyclic groups of prime order". Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  10. а б http://www.mathnet.ru/php/seminars.phtml?presentid=3055 Заседания Московского математического общества, 1 марта 2011 г., И. Д. Шкредов, Методы аддитивной комбинаторики
  11. Гараев, 2010, с. 25.
  12. Общеинститутский семинар «Математика и её приложения» Математического института им. В. А. Стеклова РАН, 18.09.14, И. Д. Шкредов, «Структурные теоремы в аддитивной комбинаторике»
  13. а б A. Iosevich, S. Konyagin, M. Rudnev, and V. Ten, «On combinatorial complexity of convex sequences», July 19, 2004. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  14. M. Z. Garaev, «On Lower Bounds for the L1-Norm of Exponential Sums», Mathematical Notes, November 2000, Volume 68, Issue 5-6, pp 713—720. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  15. Imre Z. Ruzsa, Dmitrii Zhelezov, «Convex sequences may have thin additive bases», preprint. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  16. а б Tomasz Schoen, Ilya Shkredov, «On Sumsets of Convex Sets». Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  17. а б Elekes, Nathanson, Ruzsa, «Convexity and sumsets» (PDF). Архів оригіналу (PDF) за 12 червня 2018. Процитовано 11 червня 2018.
  18. Ben Green, «Finite field models in additive combinatorics». Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  19. Tom Sanders, «On Roth’s theorem on progressions», preprint. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  20. а б в Шкредов, 2010.
  21. Гараев, 2010.
  22. Грэхем, 1984, с. 20.
  23. а б Математическая лаборатория имени П. Л. Чебышёва, Курс лекций «Аддитивная комбинаторика», Лекция 1
  24. Szemerédi, Endre (1975), On sets of integers containing no k elements in arithmetic progression (PDF), Acta Arithmetica, 27: 199—245, Zbl 0303.10056, MR0369312 Источник (PDF). Архів оригіналу (PDF) за 10 грудня 2020. Процитовано 11 червня 2018. {{cite web}}: Недійсний |deadurl=unfit (довідка).
  25. Гараев, 2010, с. 18—25.
  26. E. Croot, V. Lev, and P. P. Pach, Progression-free sets in are exponentially small (2016). arXiv preprint 1605.01506. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  27. Доказательство теоремы Рота для групп с малым кручением на arxiv.org. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  28. Изложение доказательства теоремы Рота для на русском языке
  29. И. В. Вьюгин, И. Д. Шкредов, «Об аддитивных сдвигах мультипликативных подгрупп», Матем. сб., 2012, том 203, номер 6, страницы 81-100. Архів оригіналу за 12 червня 2018. Процитовано 11 червня 2018.
  30. Шкредов, 2006, с. 119—124.
  31. И. Д. Шкредова, обзорная лекция «Аналитические методы в аддитивной комбинаторике», лекториум математической лаборатории им. Чебышёва
  32. Yufei Zhao, «Szemer´edi’s Theorem via Ergodic Theory» (PDF). Архів (PDF) оригіналу за 27 лютого 2021. Процитовано 11 червня 2018.
  33. Постнаука, И. Д. Шкредов, «Комбинаторная эргодическая теория»
  34. Imre Ruzsa, «Additive combinatorics and geometry of numbers» (PDF). Архів (PDF) оригіналу за 11 серпня 2017. Процитовано 11 червня 2018.
  35. J.A. Dias da Silva, Y.O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994) 140—146
  36. И. Д. Шкредов, "Несколько новых результатов о старших энергиях". Архів оригіналу за 3 січня 2019. Процитовано 3 січня 2019.

Література

[ред. | ред. код]