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

В математике обобщенная арифметическая прогрессия (или множественная арифметическая прогрессия ) представляет собой обобщение арифметической прогрессии, снабженной множеством общих разностей. Тогда как арифметическая прогрессия генерируется одной общей разницей, обобщенная арифметическая прогрессия может быть порождена несколькими общими разностями. Например, последовательность $17,20,22,23,25,26,27,28,29,\dots$ не является арифметической прогрессией, а вместо этого генерируется, начиная с 17 и добавляя либо 3 , либо 5, что позволяет создать несколько общих различий. Полулинейный набор обобщает эту идею на несколько измерений — это набор векторов целых чисел, а не набор целых чисел.

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

Конечная обобщенная арифметическая прогрессия или иногда просто обобщенная арифметическая прогрессия (GAP) размерности d определяется как множество вида

\{x_{0}+\ell _{1}x_{1}+\cdots +\ell _{d}x_{d}:0\leq \ell _{1}<L_{1},\ldots ,0\leq \ell _{d}<L_{d}\}

где $x_{0},x_{1},\dots ,x_{d},L_{1},\dots ,L_{d}\in \mathbb {Z}$ . Продукт $L_{1}L_{2}\cdots L_{d}$ называется размером обобщенной арифметической прогрессии; мощность набора может отличаться от размера , если некоторые элементы набора имеют несколько представлений. Если мощность равна размеру, прогрессия называется правильной . Обобщенные арифметические прогрессии можно рассматривать как проекцию сетки более высокой размерности на $\mathbb {Z}$ . Эта проекция инъективна тогда и только тогда, когда обобщенная арифметическая прогрессия правильная.

Полулинейные множества

Формально это арифметическая прогрессия $\mathbb {N} ^{d}$ представляет собой бесконечную последовательность вида $\mathbf {v} ,\mathbf {v} +\mathbf {v} ',\mathbf {v} +2\mathbf {v} ',\mathbf {v} +3\mathbf {v} ',\ldots$ , где $\mathbf {v}$ и $\mathbf {v} '$ являются фиксированными векторами в $\mathbb {N} ^{d}$ , называемые исходным вектором и общей разностью соответственно. Подмножество $\mathbb {N} ^{d}$ называется линейным, если оно имеет вид

\left\{\mathbf {v} +\sum _{i=1}^{m}k_{i}\mathbf {v} _{i}\,\colon \,k_{1},\dots ,k_{m}\in \mathbb {N} \right\},

где $m$ некоторое целое число и $\mathbf {v} ,\mathbf {v} _{1},\dots ,\mathbf {v} _{m}$ являются фиксированными векторами в $\mathbb {N} ^{d}$ . Подмножество $\mathbb {N} ^{d}$ называется полулинейным, если оно представляет собой конечное объединение линейных множеств.

Полулинейные множества — это в точности те множества, которые можно определить в арифметике Пресбургера . ^[1]

См. также

Теорема Фреймана

Ссылки

^ Гинзбург, Сеймур; Спаниер, Эдвин Генри (1966). «Полугруппы, формулы Пресбургера и языки» . Тихоокеанский математический журнал . 16 (2): 285–296. дои : 10.2140/pjm.1966.16.285 .

Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для аспирантов по математике . Том. 165. Спрингер. ISBN 0-387-94655-1 . Збл 0859.11003 .

[1] Гинзбург, Сеймур; Спаниер, Эдвин Генри (1966). «Полугруппы, формулы Пресбургера и языки» . Тихоокеанский математический журнал . 16 (2): 285–296. дои : 10.2140/pjm.1966.16.285 .

[1]