Generalized arithmetic progression

A finite generalized arithmetic progression, or sometimes just generalized arithmetic progression (GAP), of dimension d is defined to be a set of the form

${\displaystyle \{x_{0}+l_{1}x_{1}+\cdots +l_{d}x_{d}:0\leq l_{1}<L_{1},\ldots ,0\leq l_{d}<L_{d}\}}$

where ${\displaystyle x_{0},x_{1},\dots ,x_{d},L_{1},\dots ,L_{d}\in \mathbb {Z} }$. The product ${\displaystyle L_{1}L_{2}\cdots L_{d}}$ is called the size of the generalized arithmetic progression; the cardinality of the set can differ from the size if some elements of the set have multiple representations. If the cardinality equals the size, the progression is called proper. Generalized arithmetic progressions can be thought of as a projection of a higher dimensional grid into ${\displaystyle \mathbb {Z} }$. This projection is injective if and only if the generalized arithmetic progression is proper.

Formally, an arithmetic progression of ${\displaystyle \mathbb {N} ^{d}}$ is an infinite sequence of the form ${\displaystyle \mathbf {v} ,\mathbf {v} +\mathbf {v} ',\mathbf {v} +2\mathbf {v} ',\mathbf {v} +3\mathbf {v} ',\ldots }$, where ${\displaystyle \mathbf {v} }$ and ${\displaystyle \mathbf {v} '}$ are fixed vectors in ${\displaystyle \mathbb {N} ^{d}}$, called the initial vector and common difference respectively. A subset of ${\displaystyle \mathbb {N} ^{d}}$ is said to be linear if it is of the form

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

where ${\displaystyle m}$ is some integer and ${\displaystyle \mathbf {v} ,\mathbf {v} _{1},\dots ,\mathbf {v} _{m}}$ are fixed vectors in ${\displaystyle \mathbb {N} ^{d}}$. A subset of ${\displaystyle \mathbb {N} ^{d}}$ is said to be semilinear if it is a finite union of linear sets.

The semilinear sets are exactly the sets definable in Presburger arithmetic.[1]

• Freiman's theorem

• Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer. ISBN 0-387-94655-1. Zbl 0859.11003.