Problems involving arithmetic progressions

Problems involving arithmetic progressions are of interest in number theory,cite journal|author=Samuel S. Wagstaff, Jr.|authorlink=
url=
title=Some Questions About Arithmetic Progressions
journal=The American Mathematical Monthly
volume=86|issue=7|pages=579–582|year=1979
doi=10.2307/2320590] combinatorics, and computer science, both from theoretical and applied points of view.

Largest progression-free subsets

Find the cardinality (denoted by "A"_"k"("m")) of the largest subset of [0,1,...,"m" − 1] which contains no progression of "k" distinct terms. The elements of the forbidden progressions are not required to be consecutive.

For example, "A"₄(10) = 8, because [0,1,2,4,5,7,8,9] has no arithmetic progressions of length 4, while all 9-element subsets of [0,1,...9] have one. Paul Erdős set a $1000 prize for a question related to this number, collected by Szemeredi for what has become known as Szemerédi's theorem.

Arithmetic progressions from prime numbers

Szemerédi's theorem states that a set of natural numbers of non-zero upper asymptotic density contains finite arithmetic progressions, of any arbitrary length "k".

Erdős made a more general conjecture from which it would follow that :"The sequence of primes numbers contains arithmetic progressions of any length."

This result was proven by Ben Green and Terence Tao in 2004 and is now known as the Green-Tao theorem.

See also Dirichlet's theorem on arithmetic progressions.

As of 2008, the longest known arithmetic progression of primes has length 25: [Jens Kruse Andersen, [http://hjem.get2net.dk/jka/math/aprecords.htm "Primes in Arithmetic Progression Records"] . Retrieved on 2008-05-17.] :6171054912832631 + 366384·23#·n, for n = 0 to 24. (23# = 223092870)

As of 2007, the longest known arithmetic progression of "consecutive" primes has length 10. It was found in 1998 [H. Dubner; T. Forbes; N. Lygeros; M. Mizony; H. Nelson; P. Zimmermann, " [Ten consecutive primes in arithmetic progression"] , Math. Comp. 71 (2002), 1323-1328. ] [ [http://members.aon.at/toplicm/cp09.html the Nine and Ten Primes Project] ] The progression starts with a 93-digit number

:100 99697 24697 14247 63778 66555 87969 84032 95093 24689:19004 18036 03417 75890 43417 03348 88215 90672 29719

and has the period of 210.

Primes in arithmetic progressions

The prime number theorem for arithmetic progressions deals with the asymptotic distribution of prime numbers in an arithmetic progression.

Covering by and partitioning into arithmetic progressions

*Find minimal "l_n" such that any set of "n" residues modulo "p" can be covered by an arithmetic progression of the length "l_n". [cite journal
author=Vsevolod F. Lev
title=Simultaneous approximations and covering by arithmetic progressions
doi=10.1006/jcta.1999.3034
year=2000
journal=Journal of Combinatorial Theory Series A
volume=92
pages=103]
*For a given set "S" of integers find the minimal number of arithmitic progressions that cover "S"
*For a given set "S" of integers find the minimal number of nonoverlapping arithmitic progressions that cover "S"
*Find the number of ways to partition [1,..n] into arithmetic progressions. [ [http://www.research.att.com/~njas/sequences/A053732 A053732] , The On-Line Encyclopedia of Integer Sequences]
*Find the number of ways to partition [1,..n] into arithmetic progressions of length at least 2with the same period. [ [http://www.research.att.com/~njas/sequences/A072255 A072255] , The On-Line Encyclopedia of Integer Sequences]
* See also Covering system

ee also

*Arithmetic combinatorics

References