Generalized arithmetic progression

In mathematics, a multiple arithmetic progression, generalized arithmetic progression or a semilinear set, is a generalization of an arithmetic progression equipped with multiple common differences. Whereas a linear set is generated by a single common difference, (example: the arithmetic progression $3,7,11,15\dots$ has common difference 4), a semilinear set can be generated by multiple common differences (example: the sequence $17,20,22,23,25,26,27,28,29\dots$ is not an arithmetic progression but is instead generated by starting with 17 and adding either 3 or 5, thus allowing multiple common differences to generate it).

Formally, a linear subset (or arithmetic progression) of $\mathbb {N} ^{d}$ is an infinite sequence of the form $\mathbf {v} ,\mathbf {v} +\mathbf {v} ',\mathbf {v} +2\mathbf {v} ',\mathbf {v} +3\mathbf {v} ',\cdots$, where $\mathbf {v}$ and $\mathbf {v} '$ are fixed vectors in $\mathbb {N} ^{d}$, called the initial vector and common difference respectively. A subset of $\mathbb {N} ^{d}$ is said to be semilinear if it is of the form $\left\{\mathbf {v} +\sum _{i=1}^{i=m}k_{i}\mathbf {v} _{i}\,\colon \,k_{1},\dots ,k_{m}\in \mathbb {N} \right\}$, where $m$ is some integer and $\mathbf {v} ,\mathbf {v} _{1},\dots ,\mathbf {v} _{m}$ are fixed vectors in $\mathbb {N} ^{d}$.

The semilinear sets are exactly the sets definable in Presburger arithmetic.

See also

• Freiman's theorem

References

• 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.