Problems involvingarithmetic progressions are of interest innumber theory,^[1]combinatorics, andcomputer science, both from theoretical and applied points of view.

Find thecardinality (denoted byA_k(m)) of the largest subset of {1, 2, ..., m} which contains no progression ofk 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 andPál Turán posed a question related to this number^[2] and Erdős set a $1000 prize for an answer to it. The prize was collected byEndre Szemerédi for a solution published in 1975, what has become known asSzemerédi's theorem.

Szemerédi's theorem states that a set ofnatural numbers of non-zeroupper asymptotic density contains finite arithmetic progressions, of any arbitrary lengthk.

Erdős madea more general conjecture from which it would follow that

The sequence of primes numbers contains arithmetic progressions of any length.

This result was proven byBen Green andTerence Tao in 2004 and is now known as theGreen–Tao theorem.^[3]

See alsoDirichlet's theorem on arithmetic progressions.

As of 2020^[update], the longest known arithmetic progression of primes has length 27:^[4]

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

As of 2011, the longest known arithmetic progression ofconsecutive primes has length 10. It was found in 1998.^[5][6] 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 theasymptotic distribution of prime numbers in an arithmetic progression.

• Find minimall_n such that any set ofn residues modulop can be covered by an arithmetic progression of the lengthl_n.^[7]
• For a given setS of integers find the minimal number of arithmetic progressions that coverS
• For a given setS of integers find the minimal number of nonoverlapping arithmetic progressions that coverS
• Find the number of ways to partition {1, ..., n} into arithmetic progressions.^[8]
• Find the number of ways to partition {1, ..., n} into arithmetic progressions of length at least 2 with the same period.^[9]
• See alsoCovering system

• Arithmetic combinatorics
• PrimeGrid

• Series (mathematics)
• Unsolved problems in number theory

• Articles with short description
• Short description matches Wikidata
• Articles containing potentially dated statements from 2020
• All articles containing potentially dated statements