# Generalized arithmetic progression

Jump to: navigation, search

In mathematics, a multiple arithmetic progression, generalized arithmetic progression, k-dimensional arithmetic progression or a linear set, is a set of integers or tuples of integers constructed as an arithmetic progression is, but allowing several possible differences. So, for example, we start at 17 and may add a multiple of 3 or of 5, repeatedly. In algebraic terms we look at integers

${\displaystyle a+mb+nc+\cdots }$

where ${\displaystyle a,b,c}$ and so on are fixed, and ${\displaystyle m,n}$ and so on are confined to some ranges

${\displaystyle 0\leq m\leq M}$

and so on, for a finite progression. The number  ${\displaystyle k}$, that is the number of permissible differences, is called the dimension of the generalized progression.

More generally, let

${\displaystyle L(C;P)}$

be the set of all elements ${\displaystyle x}$ in ${\displaystyle N^{n}}$ of the form

${\displaystyle x=c_{0}+\sum _{i=1}^{m}k_{i}x_{i},}$

with ${\displaystyle c_{0}}$ in ${\displaystyle C}$, ${\displaystyle x_{1},\ldots ,x_{m}}$ in ${\displaystyle P}$, and ${\displaystyle k_{1},\ldots ,k_{m}}$ in ${\displaystyle N}$. ${\displaystyle L}$ is said to be a linear set if ${\displaystyle C}$ consists of exactly one element, and ${\displaystyle P}$ is finite.

A subset of ${\displaystyle N^{n}}$ 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]

## References

1. ^ Ginsburg, Seymour; Spanier, Edwin Henry (1966). "Semigroups, Presburger Formulas, and Languages". Pacific Journal of Mathematics. 16: 285–296.