Generalized arithmetic progression
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a generalized arithmetic progression (or multiple arithmetic progression) 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 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. A semilinear set generalizes this idea to multiple dimensions – it is a set of vectors of integers, rather than a set of integers.
In mathematics, a generalized arithmetic progression (or multiple arithmetic progression) 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 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. A semilinear set generalizes this idea to multiple dimensions – it is a set of vectors of integers, rather than a set of integers.
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 \{ x_0 + \ell_1x_1 + \cdots + \ell_dx_d : 0 \le \ell_1 where x_0,x_1,\dots,x_d,L_1,\dots,L_d\in\mathbb{Z} . The product L_1L_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 \mathbb{Z} . This projection is injective if and only if the generalized arithmetic progression is proper.
Semilinear sets
Generalized arithmetic progressions have a higher-dimensional analogue. A linear subset of \mathbb{N}^d consists of all vectors \mathbf{v} + k_1\mathbf{v}_1 + \cdots + k_m\mathbf{v}_m with k_1,\dots,k_m \in \mathbb{N} , for fixed vectors \mathbf{v},\mathbf{v}_1,\dots,\mathbf{v}_m ; it differs from a generalized arithmetic progression in that the coefficients are unbounded, so the set is infinite unless m = 0 . A semilinear set is a finite union of linear sets; the semilinear sets are exactly the sets definable in Presburger arithmetic.
See also
Freiman's theorem
Notes and references
Bibliography
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373926326 under CC BY-SA 4.0; modifications have been made.