WikiSort.ru - Не сортированное

Обобщённая арифметическая прогрессия — множество чисел или элементов произвольной группы ${\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]

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

См. также

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

Примечания

Литература

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