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

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

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

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

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

${\displaystyle Q+Q+Q+Q={\mathbb {N} }}$

і виводив оцінку для квадрата її модуля: Оцінка цієї суми виходила суто комбінаторно зі властивостей виразу ${\displaystyle x^{2}-y^{2}}$ при заміні змінної ${\displaystyle x=y+h}$^[2]. Таким чином, мультимножина різниць давала інформацію про структуру множини самих квадратичних лишків. У адитивній комбінаториці діє схожий підхід, коли вже множина, а не мультимножина різниць (або сум, добутків тощо) елементів із заданої множини дає інформацію про структуру цієї множини. Такий перехід — від мультимножини до множини — пов'язаний із переходом від кількості розв'язків того чи іншого рівняння (наприклад, ${\displaystyle a_{1}+b_{1}=a_{2}+b_{2},a_{i}\in A,b_{i}\in B}$) до подання чисел у тому чи іншому вигляді (наприклад, у вигляді ${\displaystyle a+b,a\in A,b\in B}$), який у принципі характерний для методу тригонометричних сум.

Окремим фундаментом для розвитку нової науки про поелементні суми множин (множини сум ${\displaystyle A+B=\left\lbrace {a+b:a\in A,b\in B}\right\rbrace }$) стала доведена Григорієм Фрейманом^[ru] теорема про будову множин з малим подвоєнням (тобто множин, множина сум двох елементів яких має малий розмір, або простіше кажучи, суми елементів із яких часто збігаються)^[3].

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

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

Питання подання чисел у вигляді суми елементів із небагатьох даних множин математики розглядали ще з давніх часів. Класичними прикладами є задачі подаваності будь-якого числа сумою чотирьох квадратів (теорема Лагранжа про чотири квадрати) або будь-якого парного числа, більшого від трьох, сумою двох простих (проблема Гольдбаха). Якщо позначити через ${\displaystyle Q=\left\lbrace {0}\right\rbrace \cup \left\lbrace {n^{2}:n\in {\mathbb {N} }}\right\rbrace }$ множину всіх квадратів невід'ємних чисел, то в термінах адитивної комбінаторики (див. розділ з позначеннями нижче) теорему Лагранжа можна записати як

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

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

${\displaystyle S(a)=\sum \limits _{x=0}^{p-1}{e^{2\pi {\frac {ax^{2}}{p}}i}}}$

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

${\displaystyle |S(a)|^{2}=\sum \limits _{x,y}{e^{2\pi {\frac {a(x^{2}-y^{2})}{p}}i}}}$

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

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

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

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

${\displaystyle A+B=\left\lbrace {a+b:a\in A,b\in B}\right\rbrace }$

для скінченних множин ${\displaystyle A,B\in \mathrm {G} }$, де ${\displaystyle (\mathrm {G} ,+)}$ — група. Розмір такої множини визначається структурою ${\displaystyle A}$ і ${\displaystyle B}$ відносно операції ${\displaystyle +}$. Якщо ${\displaystyle A}$ і ${\displaystyle B}$ — арифметичні прогресії, то ${\displaystyle |A+B|}$ мала. А якщо, наприклад, ${\displaystyle A,B\in {\mathbb {Z} }_{n}}$ вибрано випадково за схемою Бернуллі, то ${\displaystyle |A+B|}$ дуже велика. Проміжні випадки між зазначеними двома якраз і становлять адитивно-комбінаторний інтерес.

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

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

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

• Щільність множини ${\displaystyle A\subset {\mathbb {G} }}$ для скінченної групи ${\displaystyle {\mathbb {G} }}$ — величина ${\displaystyle {\frac {|A|}{|{\mathbb {G} }|}}}$ або закон її асимптотичного зростання зі зростанням розміру ${\displaystyle {\mathbb {G} }}$, а для нескінченних ${\displaystyle {\mathbb {G} }}$ — асимптотична щільність (або закон розподілу) ${\displaystyle A}$ в ${\displaystyle {\mathbb {G} }}$;
• УАП (від «узагальнена арифметична прогресія») — наявність у множині великих арифметичних прогресій, нетривіальних узагальнених арифметичних прогресій чи їх великих частин, а також, навпаки, можливість покрити множину (чи її більшу частину) невеликою арифметичною прогресією;
• ${\displaystyle A_{1}+\dots +A_{k}}$ — розмір та будова множини сум (а також різниць та комбінацій сум та різниць) — зокрема, можливість подати будь-який елемент групи як суму заданої кількості елементів даної множини;
• ${\displaystyle X=A_{1}+\dots +A_{k}}$ — подаваність множини або великої її частини як множини сум (а також різниць і комбінацій сум і різниць) чисел з невеликої кількості множин, тобто розв'язність рівняння множин ${\displaystyle X=A_{1}+\dots +A_{k}}$ для заданої ${\displaystyle X}$, можливо, навіть за певних умов на ${\displaystyle A_{1},\dots ,A_{k}}$ (наприклад, ${\displaystyle A_{1}=\dots =A_{k}}$), де ${\displaystyle +}$ означає суму Мінковського;
• коефіцієнти Фур'є маються на увазі для характеристичної функції множини і функцій, що визначаються через неї, а також їх статистика — різного роду норми, кількість елементів із великим значенням і структура їх множини;
• ЧРР (від «число розв'язків рівняння») — число розв'язків різних лінійних рівнянь (зокрема, адитивна енергія) або систем рівнянь, у яких змінні набувають значень із заданих множин, а також співвідношення кількості їх розв'язків.

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

• ${\displaystyle {\widehat {A}}}$ — коефіцієнт Фур'є характеристичної функції множини ${\displaystyle A}$,
• ${\displaystyle E(A,B)}$ — адитивна енергія,
• ${\displaystyle \rho _{A}(x)=\mathbf {1} _{A}(x)-{\frac {|A|}{|{\mathbb {G} }|}}}$ — таку функцію називають балансовою функцією множини ${\displaystyle A\in {\mathbb {G} }}$, оскільки ${\displaystyle \sum \limits _{x\in {\mathbb {G} }}{\rho _{A}(x)}=0}$.

	Щільність	УАП	${\displaystyle A_{1}+\dots +A_{k}}$	${\displaystyle X=A_{1}+\dots +A_{k}}$	Коефіцієнти Фур'є	ЧРР
Щільність
УАП	Теорема Семереді
${\displaystyle A_{1}+\dots +A_{k}}$	Нерівність Шнірельмана, Теорема Фюрстенберга — Шаркозі[en]	Теорема Фреймана[en]
${\displaystyle X=A_{1}+\dots +A_{k}}$		${\displaystyle A+B}$ при великих ${\displaystyle |A|}$ і ${\displaystyle |B|}$ містять довгу а. п.[7][8]	Нерівність Плюннеке ― Ружі
Коефіцієнти Фур'є	Принцип невизначеності[9]	Якщо ${\displaystyle A\subset {\mathbb {Z} }_{N}}$, ${\displaystyle ||{\widehat {\rho _{A}}}||_{\infty }}$ мала, то ${\displaystyle A}$ містить а. п. довжини 3[10]	Якщо ${\displaystyle ||{\widehat {A}}||_{\infty }}$ і ${\displaystyle ||{\widehat {B}}||_{\infty }}$ малі, то ${\displaystyle |A+B|}$ велика
ЧРР	Теорема Рота	Якщо ${\displaystyle A}$ — а. п., то ${\displaystyle E(A,A)\geq \Omega (|A|^{3})}$	${\displaystyle |A|^{2}|B|^{2}\geq |A+B|E(A,B)}$[11]	Зі співвідношень адитивних енергій можна зробити висновки про структуру множини[12]	Якщо ${\displaystyle A,B\in {\mathbb {Z} }_{N}}$, то ${\displaystyle E(A,B)=\sum \limits _{r=0}^{N-1}{|{\widehat {A}}(r)|^{2}|{\widehat {B}}(r)|^{2}}}$

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

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

Скінченну множину ${\displaystyle A=\left\lbrace {a_{1}\leq \dots \leq a_{n}}\right\rbrace }$ дійсних чисел називають опуклою послідовністю (або опуклою множиною), якщо ${\displaystyle a_{i+1}-a_{i}<a_{i+2}-a_{i+1}}$ для ${\displaystyle i=1,\dots ,n-2}$, тобто якщо ${\displaystyle A}$ є образом відрізка ${\displaystyle \left\lbrace {1,\dots ,n}\right\rbrace }$ для деякої строго опуклої функції^[13]. Властивості таких множин широко вивчає адитивна комбінаторика^{[14][15][16][17]}. Це поняття не слід плутати з опуклою множиною у звичному значенні.

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

Майже періодична функція — функція ${\displaystyle f}$ така, що норма ${\displaystyle ||f(x+t)-f(x)||_{p}}$ досить мала для деякого ${\displaystyle p}$ і для всіх ${\displaystyle t\in T}$, де ${\displaystyle T}$ — деяка множина (наприклад, множина Бора). На таких множинах побудовано одне з доведень теореми Рота^[19].

Множина великих тригонометричних сум (іноді називана спектром) множини ${\displaystyle A\subset {\mathbb {Z} }_{p}}$ — множина лишків ${\displaystyle r}$, для яких сума ${\displaystyle \sum \limits _{a\in A}{e_{p}(ar)}}$ (коефіцієнт Фур'є) має великий модуль^[20].

Дисоціативна множина ${\displaystyle A}$ — множина, для якої лінійні комбінації ${\displaystyle \sum \limits _{a\in A}{\varepsilon _{a}a}=0}$ рівні нулю, де ${\displaystyle \forall a\in A:\varepsilon _{a}\in \left\lbrace {-1,0,1}\right\rbrace }$, тільки коли всі ${\displaystyle \varepsilon _{a}}$ рівні нулю. Зокрема, це означає, що суми елементів із двох різних підмножин завжди різні^[20]. Дисоціативність можна розглядати як аналог лінійної незалежності над ${\displaystyle \left\lbrace {-1,0,1}\right\rbrace }$.

Звичайно, попри існування потужних та складних методів вивчення теорем адитивної комбінаторики, деякі прийоми та задачі допускають елементарний опис. Із нерівності Коші ${\displaystyle \left({\sum \limits _{i=1}^{n}{a_{i}}}\right)^{2}\leq n\sum \limits _{i=1}^{n}{{a_{i}}^{2}}}$ виводяться властивості адитивної енергії, що застосовуються майже повсюдно. Загалом за елементарного підходу часто аналізують число розв'язків тих чи інших рівнянь. Також часто застосовують аргумент середнього^[en] — наприклад, при розкладанні числа розв'язків рівняння на суму числа розв'язків за того чи іншого значення окремої змінної^[21].

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

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

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

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

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

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

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

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

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

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

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

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

• теорему Семереді — Троттера з комбінаторної геометрії (особливо в питаннях, що стосуються опуклих множин)^[16][13][17];
• геометрія чисел^[34];
• теорія представлень симетричних груп^[en][35];
• теорія власних чисел (може використовуватися для виведення нерівності між кількістю розв'язків деяких систем лінійних рівнянь^[36]).

• Пал Ердеш
• Григорій Фрейман^[ru]
• Імре Ружа^[en]
• Ендре Семереді
• Вільям Гауерс
• Бен Ґрін^[en]
• Теренс Тао
• Роджер Гіз-Браун^[en]
• Жан Бурген
• Том Сандерс^[en]
• Гілель Фюрстенберг^[en]
• Сергій Конягін^[ru]
• Ілля Шкредов^[ru]

• Сума Мінковського
• Арифметична комбінаторика

• Грэхем, Рональд. Начала теории Рамсея. — М. : Мир, 1984. — ISBN 5-09-002630-0.
• М. З. Гараев. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка // Успехи математических наук. — 2010. — Вып. 4. — С. 5—66.
• И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях // Успехи математических наук. — 2006. — Вып. 6. — С. 111—179.
• И. Д. Шкредов. Анализ Фурье в комбинаторной теории чисел // Успехи математических наук. — 2010. — Вып. 3. — С. 127—184.
• Terence Tao, Ву Ха Ван^[en]. Additive combinatorics. — Cambridge University Press. — 2006. — ISBN 0-511-24530-0.
• Imre Ruzsa. Sumsets and structure.
• Фрейман, Григорий Абелевич. Начала структурной теории множеств. — Типография "Татполиграф". — 1966.
• И. М. Гельфанд, Ю. В. Линник. Элементарные методы в аналитической теории чисел. — М. — Физматгиз, 1962.
• И. М. Виноградов. Метод тригонометрических сумм в теории чисел. — Издательство "Наука", 1971.