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

Узага́льнена арифмети́чна прогре́сія — послідовність чисел або елементів довільної групи $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}$ ^[1].

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

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

Література

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

[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

[FOOTNOTEГрэхем198429—33-4] Грэхем, 1984, с. 29—33.

[1]

[2]

[3]

[4]