In
mathematics, a generalized arithmetic progression (or multiple arithmetic progression) is a generalization of an
arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
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
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
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.
Arithmetic Progression:-"There exit a common different that is d that we add to the previous term in output it is called arithmetic progression
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
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
and
are fixed vectors in
. A subset of
is said to be semilinear if it is a finite
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
of linear sets.
The semilinear sets are exactly the sets definable in
Presburger arithmetic
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omit ...
.
See also
*
Freiman's theorem
In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if , A+A, /, A, is small, then A can be contained in a small generalized arithmetic p ...
References
*
{{DEFAULTSORT:Generalized Arithmetic Progression
Algebra
Combinatorics