Problems involving arithmetic progression

Arithmetic progression

In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...

s are of interest in number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, combinatorics

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

, and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, 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 {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. Paul Erdős

Paul Erdos

Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...

 set a $1000 prize for a question related to this number, collected by Endre Szemerédi

Endre Szemerédi

Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...

 for what has become known as Szemerédi's theorem

Szemerédi's theorem

In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...

.

Arithmetic progressions from prime numbers

Szemerédi's theorem

Szemerédi's theorem

In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...

 states that a set of natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

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

Ben Green (mathematician)

Ben Joseph Green FRS is a British mathematician, specializing in combinatorics and number theory. He is the Herchel Smith Professor of Pure Mathematics at the University of Cambridge.- Early years :...

 and Terence Tao

Terence Tao

Terence Chi-Shen Tao FRS is an Australian mathematician working primarily on harmonic analysis, partial differential equations, combinatorics, analytic number theory and representation theory...

 in 2004 and is now known as the Green–Tao theorem.

See also Dirichlet's theorem on arithmetic progressions

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 ≥ 0. In other words, there are infinitely many primes which are...

.

, the longest known arithmetic progression of primes has length 26:

43142746595714191 + 23681770·23#·n, for n = 0 to 25. (23# = 223092870

Primorial

In mathematics, and more particularly in number theory, primorial is a function from natural numbers to natural numbers similar to the factorial function, but rather than multiplying successive positive integers, only successive prime numbers are multiplied...

)

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.

Primes in arithmetic progressions

The prime number theorem for arithmetic progressions deals with the asymptotic

Asymptotic analysis

In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

 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 {1, ..., n} into arithmetic progressions.
• Find the number of ways to partition {1, ..., n} into arithmetic progressions of length at least 2 with the same period.
• See also Covering system