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 an arithmetic progression is generated by a single common difference, a generalized arithmetic progression can be generated by multiple common differences. For example, the sequence 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.

## Finite 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

where . The product 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 . This projection is injective if and only if the generalized arithmetic progression is proper.

## Semilinear sets

Formally, an arithmetic progression of is an infinite sequence of the form , where and are fixed vectors in , called the initial vector and common difference respectively. A subset of is said to be **linear** if it is of the form

where is some integer and are fixed vectors in . A subset of 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]}

## See also

## References

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

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