Generalized arithmetic progression: Difference between revisions
m alignment of punctuation |
m Dating maintenance tags: {{Refimprove}} {{Context}} {{Technical}} |
||
(30 intermediate revisions by 23 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Type of numeric sequence}} |
|||
{{Cleanup-rewrite|date=May 2009}} |
|||
{{multipleissues| |
|||
{{technical|date=June 2024}} |
|||
{{refimprove|date=June 2024}} |
|||
{{context|date=June 2024}}}} |
|||
In [[mathematics]], a '''multiple arithmetic progression''', '''generalized arithmetic progression''', or ''k''-'''dimensional arithmetic progression''', is a set of [[integer]]s 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 |
|||
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]] <math>17, 20, 22, 23, 25, 26, 27, 28, 29, \dots</math> 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'' + ''mb'' + ''nc'' + ... |
|||
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== |
|||
where ''a'', ''b'', ''c'' and so on are fixed, and ''m'', ''n'' and so on are confined to some ranges |
|||
A '''finite generalized arithmetic progression''', or sometimes just '''generalized arithmetic progression (GAP)''', of dimension ''d'' is defined to be a [[set (mathematics)|set]] of the form |
|||
:<math>\{ x_0 + \ell_1x_1 + \cdots + \ell_dx_d : 0 \le \ell_1< L_1, \ldots, 0 \le \ell_d < L_d \}</math> |
|||
where <math>x_0,x_1,\dots,x_d,L_1,\dots,L_d\in\mathbb{Z}</math>. The product <math>L_1L_2\cdots L_d</math> 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 <math>\mathbb{Z}</math>. This projection is [[injective]] if and only if the generalized arithmetic progression is proper. |
|||
==Semilinear sets== |
|||
:0 ≤ ''m'' ≤ ''M'', |
|||
Formally, an arithmetic progression of <math>\mathbb{N}^d</math> is an infinite sequence of the form <math>\mathbf{v},\mathbf{v} + \mathbf{v}',\mathbf{v} + 2\mathbf{v}',\mathbf{v} + 3\mathbf{v}',\ldots</math>, where <math>\mathbf{v}</math> and <math>\mathbf{v}'</math> are fixed vectors in <math>\mathbb{N}^d</math>, called the initial vector and common difference respectively. A subset of <math>\mathbb{N}^d</math> is said to be '''linear''' if it is of the form |
|||
:<math>\left\{\mathbf{v} + \sum_{i=1}^m k_i\mathbf{v}_i \,\colon\, k_1,\dots,k_m\in \mathbb{N}\right\},</math> |
|||
where <math>m</math> is some [[integer]] and <math>\mathbf{v},\mathbf{v}_1,\dots,\mathbf{v}_m</math> are fixed vectors in <math>\mathbb{N}^d</math>. A subset of <math>\mathbb{N}^d</math> is said to be '''semilinear''' if it is a finite [[union (set theory)|union]] of linear sets. |
|||
The semilinear sets are exactly the sets definable in [[Presburger arithmetic]].<ref>{{cite journal|last1=Ginsburg|first1=Seymour|last2=Spanier|first2=Edwin Henry|title=Semigroups, Presburger Formulas, and Languages|journal=Pacific Journal of Mathematics|date=1966|volume=16| issue=2 |pages=285–296| doi=10.2140/pjm.1966.16.285 |doi-access=free}}</ref> |
|||
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. |
|||
==See also== |
|||
More generally, let |
|||
* [[Freiman's theorem]] |
|||
==References== |
|||
:<math>L(C;P)</math> |
|||
{{Reflist}} |
|||
*{{cite book| last=Nathanson | first=Melvyn B. | year=1996 | title=Additive Number Theory: Inverse Problems and Geometry of Sumsets | volume=165 | series=[[Graduate Texts in Mathematics]] | publisher=Springer | isbn=0-387-94655-1 | zbl=0859.11003 }} |
|||
be the set of all elements <math>x</math> in <math>N^n</math> of the form |
|||
:<math>x = c_0 + \sum_{i=1}^m k_i x_i,</math> |
|||
with <math>c_0</math> in <math>C</math>, <math>x_1, \ldots, x_m</math> in <math>P</math>, and <math>k_1, \ldots, k_m</math> in <math>N</math>. <math>L</math> is said to be a ''linear set'' if <math>C</math> consists of exactly one element, and <math>P</math> is finite. |
|||
A subset of <math>N_n</math> is said to be '''semilinear'''{{anchor|semilinear set}} if it is a finite union of linear sets. |
|||
{{DEFAULTSORT:Generalized Arithmetic Progression}} |
|||
[[Category:Algebra]] |
[[Category:Algebra]] |
||
[[Category:Articles lacking sources (Erik9bot)]] |
|||
[[Category:Combinatorics]] |
[[Category:Combinatorics]] |
||
[[Category:Arithmetic series]] |
Latest revision as of 01:47, 8 June 2024
![]() | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
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 is not an arithmetic progression, but is instead generated by starting with 17 and adding either 3 oder 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
[edit]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
[edit]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
[edit]References
[edit]- ^ Ginsburg, Seymour; Spanier, Edwin Henry (1966). "Semigroups, Presburger Formulas, and Languages". Pacific Journal of Mathematics. 16 (2): 285–296. doi:10.2140/pjm.1966.16.285.
- Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer. ISBN 0-387-94655-1. Zbl 0859.11003.