Generalized arithmetic progression

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

a+mb+nc+\cdots

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

0\leq m\leq M

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

More generally, let

L(C;P)

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

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

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

A subset of $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

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

This article is issued from Wikipedia - version of the 6/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Generalized arithmetic progression

See also

References