Problems involving arithmetic progressions
In progress
Problems involving arithmetic progressions are of interest in number theory,[1] combinatorics, and computer science, both from theoretical and applied points of view.
Largest progression-free subsets
Find the cardinality (denoted by Ak(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, A4(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 Erdos set a $1000 prize for a question related to this number, collected by Szemeredi for what has become known as Szemerédi's theorem.
Primes in arithmetic progression
The 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. Earlier Erdos and Turan [3] made a a more general conjecture from which it would follow that
- the sequence of prime numbers contains arithmetic progressions of any length.
The latter result was proven in 2004 as the Green-Tao theorem.
See also Dirichlet's theorem on arithmetic progressions.
It is known that there are infinitely many arithmetic progression triplets of primes.[1]
As of 2007, the longest arithmetic progression of primes has length 24: [4]
As of 2007, the longest arithmetic progression of consecutive primes has length 10. It was found in 1998 [5][6] The progression starts with a 92-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.
References
- ^ a b Samuel S. Wagstaff, Jr. (1979). "Some Questions About Arithmetic Progressions". The American Mathematical Monthly. 86 (7): 579–582. doi:10.2307/2320590.
- ^ "Prime Arithmetic Progression", a MathWorld articlearticle
- ^ Paul Erdős, Paul Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261--264.
- ^ Jens Kruse Andersen, Primes in Arithmetic Progression Records
- ^ H. Dubner; T. Forbes; N. Lygeros; M. Mizony; H. Nelson; P. Zimmermann, "[Ten consecutive primes in arithmetic progression"], Math. Comp. 71 (2002), 1323-1328.
- ^ the Nine and Ten Primes Project