TOPICS
Search

Generalized Arithmetic Progression


A generalized arithmetic progression of rank d in an Abelian group is a set

 P={x_0+n_1x_1+...+n_dx_d:0<=n_i<L_i},

where L_i are positive integers, the n_i are integers, and the x_i are fixed group elements. It is proper if all product_(i=1)^(d)L_i parameter choices give distinct elements. Rank 1 recovers an arithmetic progression (Tao and Vu 2006).

Generalized arithmetic progressions describe sets with small sumsets. A quantitative form of Freiman's theorem states that a nonempty finite A subset Z with |A-A|<=K|A| is contained in a proper generalized arithmetic progression P of rank at most CK^C and size at most exp(CK^C)|A|, for an absolute constant C (Tao and Vu 2006). These estimates are convenient general bounds, not claims of optimal dependence on K.


See also

Arithmetic Progression, Freiman Isomorphism, Sumset

Explore with Wolfram|Alpha

References

Tao, T. and Vu, V. Additive Combinatorics. Cambridge, England: Cambridge University Press, 2006. https://doi.org/10.1017/CBO9780511755149.

Cite this as:

Weisstein, Eric W. "Generalized Arithmetic Progression." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GeneralizedArithmeticProgression.html

Subject classifications