Обобщённая арифметическая прогрессия

Обобщённая арифметическая прогрессия — множество чисел или элементов произвольной группы $G$$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 <!--\; \dots \; -->,d_k,n_1,\dots <!--\; \dots \; -->,n_k$$d_{1},\dots ,d_{k},n_{1},\dots ,n_{k}$.

Связанная терминологияПравить

Прогрессия называется собственной, если все числа вида $a+\underset{i=1}{\overset{k}{\sum <!--\; \sum \; -->}}{\mathrm{\lambda <!--\; \lambda \; -->}}_i{d}_i$$a+\sum \limits _{i=1}^{k}{\lambda _{i}d_{i}}$  различны, то есть она содержит $n_1\cdot <!--\; \cdot \; -->\dots <!--\; \dots \; -->\cdot <!--\; \cdot \; -->n_k$$n_{1}\cdot \ldots \cdot n_{k}$  элементов.

Рангом (или размерностью) прогрессии называется количество слагаемых в представлении каждого элемента (в обозначениях выше число $k$$k$ ).

При $n_1=\cdots <!--\; \cdots \; -->=n_k=2$$n_{1}=\dots =n_{k}=2$  обобщённую арифметическую прогрессию также называют $d$$d$ -мерным кубом (поскольку в него существует линейное отображения из ${\left\{0,1\right\}}^d$$\left\lbrace {0,1}\right\rbrace ^{d}$ ).

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

Область использованияПравить

Обобщённые арифметические прогрессии представляют собой конструкцию менее структурированную чем обычная арифметическая прогрессия, но тем не менее всё же имеющую нетривиальную структуру (когда размер прогрессии велик, а ранг мал). Это делает их удобным инструментом для изучения и обобщения теорем арифметической комбинаторики, связанных с выводом структуры из численных характеристик множества, таких как аддитивная энергия, коэффициент удвоения и т. д.

Некоторые структурные теоремы аддитивной комбинаторики доказывают существование обобщённой арифметической прогрессии достаточно малого ранга и большого размера в достаточно упорядоченных множествах или возможность покрытия такого множества обобщённой арифметической прогрессий небольшого ранга и небольшого же (ограниченного некоторой формулой от размера множества) размера.

Обобщённые арифметиеские прогрессии могут использоваться для доказательства теоремы Рота.

Вообще доказать присутствие во множестве обобщённых арифметических прогрессий, исходя из каких-то известных фактов об этом множестве, часто легче, чем доказать присутствие обычных арифметических прогрессий.

См. такжеПравить

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

ЛитератураПравить

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