Problems involving

arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

s are of interest in

number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

, and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, 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 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 has no arithmetic progressions of length 4, while all 9-element subsets of have one.

Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...

set a $1000 prize for a question related to this number, collected by

Endre Szemerédi Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science a ...

for what has become known as

Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''-ter ...

Arithmetic progressions from prime numbers

states that a set of

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

s 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 Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...

in 2004 and is now known as the

Green–Tao theorem In number theory, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, for every natural number ''k'', there exist arith ...

. See also

Dirichlet's theorem on arithmetic progressions In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers ''a'' and ''d'', there are infinitely many primes of the form ''a'' + ''nd'', where ''n'' is als ...

. , the longest known arithmetic progression of primes has length 27: :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. 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. Source about Erdős-Turán Conjecture of 1936: *P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.

Primes in arithmetic progressions

The prime number theorem for arithmetic progressions deals with the

asymptotic In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...

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''. *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 into arithmetic progressions. *Find the number of ways to partition 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 In mathematics, a covering system (also called a complete residue system) is a collection :\ of finitely many residue classes a_i(\mathrm\ ) = \ whose union contains every integer. Examples and definitions The notion of covering system was i ...

Notes

Mathematical series Unsolved problems in number theory