一般化算術数列

数学における多重算術数列, 一般化算術数列（いっぱんかさんじゅつすうれつ、英: generalized arithmetic progression）または多次元算術数列は、自然数からなる有限多重数列であって、各変数に対応する成分がどれも算術数列（公差はそれぞれで異なってよい）となるものを言う。そのような多重数列全体の成す集合を線型集合 (linear set) とも呼ぶ。

例えば、初項 $17$ に $3$ の倍数または $5$ の倍数を繰り返し加えたものは多重算術数列を成す。式で書けば、 $c, d 1, d 2, \dots$ は自然数の定数として、 $k 1, k 2, \dots$ は適当な範囲 $0 \leq k i < n i (\prod i n i =: n)$ を動く自然数変数とするとき、

x_{k_{1},k_{2},\dotsc ,k_{j}}:=c+k_{1}d_{1}+k_{2}d_{2}+\cdots +k_{j}d_{j}

が有限多重算術数列である。取りうる添字の数 $j$ をこの多重数列の次元 (dimension) と言う。

より一般に、集合 $L = L (C; P)$ は

x=(x_{k_{1},k_{2},\dotsc ,k_{j}});\;x_{k_{1},k_{2},\dotsc ,k_{j}}=c+\sum _{i=1}^{j}k_{i}d_{i}\quad (c\in C;\;d_{i}\in P,\,k_{i}\in \mathbb {N} )

なる形の $N n$ の元 $x$ 全体の成す集合とする。 $L$ が線型集合であるとは、 $C$ がただ一つの元からなり、かつ $P$ が有限となるときに言う。

$N n$ の部分集合が半線型集合 (semilinear set) であるとは、それが有限個の線型集合の交わりに書けるときに言う。半線型集合の全体はちょうどプレスバーガー算術における定義可能 (definable) な集合の全体に一致する^[1]。

参考文献

^ 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

外部リンク

multidimensional arithmetic progression - PlanetMath.（英語）
Generalized arithmetic progressions in OEIS Wiki

[1] Ginsburg, Seymour; Spanier, Edwin Henry (1966). “Semigroups, Presburger Formulas, and Languages”. Pacific Journal of Mathematics 16: 285–296.

[1]

関連項目

参考文献

外部リンク