# Erdős conjecture on arithmetic progressions

Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics (not to be confused with the Erdős–Turán conjecture on additive bases). It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.

Formally, the conjecture states that if

$\sum_{n\in A} \frac{1}{n} = \infty$

then A contains arithmetic progressions of any given length. (Sets satisfying the hypothesis are called large sets.)

## History

In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions.[1] This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem.

In a 1976 talk titled "To the memory of my lifelong friend and collaborator Paul Turán," Paul Erdős offered a prize of US$3000 for a proof of this conjecture.[2] The problem is currently worth US$5000.[3]

## Progress and related results

 Does every large set contain arbitrarily long arithmetic progressions?

Erdős' conjecture on arithmetic progressions can be viewed as a stronger version of Szemerédi's theorem. Because the sum of the reciprocals of the primes diverges, the Green–Tao theorem on arithmetic progressions is a special case of the conjecture.

Even the weaker claim that A must contain at least one arithmetic progression of length 3 is open. The strongest related result is due to Sanders.[4]

The converse of the conjecture is not true. For example, the set {1, 10, 11, 100, 101, 102, 1000, 1001, 1002, 1003, 10000, ...} contains arithmetic progressions of every finite length, but the sum of the reciprocals of its elements converges.