Узагальнена арифметична прогресія

Узага́льнена арифмети́чна прогре́сія — послідовність чисел або елементів довільної групи ${\displaystyle G}$, подавана у вигляді

${\displaystyle \left\lbrace {a+\sum \limits _{i=1}^{k}{\lambda _{i}d_{i}}\$ :\ 0\leq \lambda _{i}<n_{i},\ i=1,\dots ,k}\right\rbrace }

для деяких ${\displaystyle d_{1},\dots ,d_{k},n_{1},\dots ,n_{k}}$^[1].

Пов'язана термінологія

Прогресію називають власною, якщо всі числа вигляду ${\displaystyle a+\sum \limits _{i=1}^{k}{\lambda _{i}d_{i}}}$ різні, тобто вона містить ${\displaystyle n_{1}\cdot \ldots \cdot n_{k}}$ елементів.

Рангом (або розмірністю) прогресії називають кількість доданків у поданні кожного елемента (в позначеннях вище — число ${\displaystyle k}$).

При ${\displaystyle n_{1}=\dots =n_{k}=2}$ узагальнену арифметичну прогресію також називають^[2] ${\displaystyle d}$-вимірним кубом (оскільки в нього існує лінійне відображення з ${\displaystyle \left\lbrace {0,1}\right\rbrace ^{d}}$).

При ${\displaystyle k=1}$ множина являє собою звичайну арифметичну прогресію.

Галузь використання

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

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

Узагальнені арифметичні прогресії можна використати для доведення теореми Рота^[4].

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

Див. також

• Адитивна комбінаторика
• Теорема Фреймана

Примітки

1. OEIS Wiki, «Generalized arithmetic progressions». Архів оригіналу за 11 травня 2018. Процитовано 8 травня 2018.
2. W. T. Gowers, «A new proof of Szemeredi’s theorem», 2001. Архів оригіналу за 11 травня 2018. Процитовано 8 травня 2018.
3. Математическая лаборатория имени П. Л. Чебышева, курс Харальда Хельфготта «Путешествие по современным областям анализа и теории чисел», лекция 2
4. Грэхем, 1984, с. 29—33.

Література

• Рональд Грэхем. Начала теории Рамсея. — М. : Мир, 1984.