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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

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