Problems involving arithmetic progressions

Find the cardinality (denoted by A_k(m)) of the largest subset of {1, 2, ..., m} 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 {1, 2, 3, 5, 6, 8, 9, 10} has no arithmetic progressions of length 4, while all 9-element subsets of {1, 2, ..., 10} have one.

In 1936, Paul Erdős and Pál Turán posed a question related to this number{{cite journal|author-link1=Paul Erdős|first1=Paul|last1=Erdős|author-link2=Pál Turán|first2=Paul|last2=Turán|title=On some sequences of integers|journal=Journal of the London Mathematical Society|volume=11|issue=4|year=1936|pages=261–264|url=http://www.renyi.hu/~p_erdos/1936-05.pdf|doi=10.1112/jlms/s1-11.4.261|mr=1574918}} and Erdős set a $1000 prize for an answer to it. The prize was collected by Endre Szemerédi for a solution published in 1975, what has become known as Szemerédi's theorem.

{{main|Primes in arithmetic progression}}

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.{{cite journal | arxiv=1403.2957 | title=The Green–Tao theorem: an exposition | first1=David | last1=Conlon | author1link=David Conlon | first2=Jacob | last2=Fox | author2link=Jacob Fox | first3=Yufei | last3=Zhao | mr=3285854 | journal=EMS Surveys in Mathematical Sciences | year=2014 | doi=10.4171/EMSS/6 | volume=1 | issue=2 | pages=249–282 | s2cid=119301206 }}

See also Dirichlet's theorem on arithmetic progressions.

{{As of|2020}}, the longest known arithmetic progression of primes has length 27:Jens Kruse Andersen, [http://primerecords.dk/aprecords.htm Primes in Arithmetic Progression Records]. Retrieved on 2020-08-10.

:224584605939537911 + 81292139·23#·n, for n = 0 to 26. (23# = 223092870)

As of 2011, 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 common difference 210.

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

• 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 over F_p

|doi=10.1006/jcta.1999.3034

|year=2000

|journal=Journal of Combinatorial Theory | series=Series A

|volume=92

|issue=2

|pages=103–118|doi-access=free

}}

• For a given set S of integers find the minimal number of arithmetic progressions that cover S
• For a given set S of integers find the minimal number of nonoverlapping arithmetic progressions that cover S
• Find the number of ways to partition {1, ..., n} into arithmetic progressions.{{Cite OEIS|sequencenumber=A053732|name=Number of ways to partition {1,...,n} into arithmetic progressions of length >= 1}}
• Find the number of ways to partition {1, ..., n} into arithmetic progressions of length at least 2 with the same period.{{Cite OEIS|sequencenumber=A072255|name=Number of ways to partition {1,2,...,n} into arithmetic progressions...}}
• See also Covering system

• Arithmetic combinatorics
• PrimeGrid

Category:Series (mathematics)

Category:Unsolved problems in number theory