Economic production quantity

2013-07-17T12:10:14Z

196.15.240.223: /* EPQ Formula */

'''Erdős' conjecture on arithmetic progressions''', often referred to as the '''Erdős–Turán conjecture''' due to Turán's earlier work with Erdős,<ref>http://mathoverflow.net/questions/132648/the-erdos-turan-conjecture-or-the-erdos-conjecture</ref> 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 progression]]s.

Formally, if

::<math> \sum_{n\in A} \frac{1}{n} = \infty </math>

(i.e. ''A'' is a [[small set (combinatorics)|large set]]) then ''A'' contains arithmetic progressions of any given length.

In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive [[natural density]] contains arbitrarily long arithmetic progressions.<ref name="erdos turan">{{citation|authorlink1=Paul Erdős|first1=Paul|last1=Erdős|authorlink2=Paul Turán|first2=Paul|last2=Turán|title=On some sequences of integers|journal=[[Journal of the London Mathematical Society]]|volume=11|issue=4|year=1936|pages=261–264|url=http://www.renyi.hu/~p_erdos/1936-05.pdf|doi=10.1112/jlms/s1-11.4.261}}.</ref> This was proven by [[Szemerédi]] in 1975, and is now known as [[Szemerédi's theorem]]. Erdős' conjecture on arithmetic progressions can be viewed as a stronger version of Szemerédi's theorem, and if this conjecture were proven, it would imply the [[Green–Tao theorem]] on arithmetic progressions in the [[prime number|primes]] since the sum of the reciprocals of the primes diverges.

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.<ref>''Problems in number theory and Combinatorics'', in Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976), ''Congress. Numer.'' XVIII, 35–58, Utilitas Math., Winnipeg, Man., 1977</ref> The problem is currently worth US$5000.<ref>p. 354, Soifer, Alexander (2008); The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators; New York: Springer. ISBN 978-0-387-74640-1</ref>

Even the weaker claim, that ''A'' must contain at least one arithmetic progression of length 3, is open, and the best known bound is due to Tom Sanders.<ref>http://arxiv.org/abs/1011.0104</ref>

The converse of this result is not true, as seen by the set <math>A = \{1,10,11,100,101,102,1000,1001,1002,1003,...\}</math>, the sum of the reciprocals of which converges.

==See also==

* [[Arithmetic combinatorics]]
* [[Green–Tao theorem]]
* [[Szemerédi's theorem]]
* [[Problems involving arithmetic progressions]]

==References==
{{reflist}}
*P. Erdős: [http://www.renyi.hu/~p_erdos/1973-24.pdf Résultats et problèmes en théorie de nombres], ''Séminaire Delange-Pisot-Poitou (14e année: 1972/1973), Théorie des nombres'', Fasc 2., Exp. No. 24, pp. 7,
*P. Erdős and P.Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.
*P. Erdős: Problems in number theory and combinatorics, Proc. Sixth Manitoba Conf. on Num. Math., ''Congress Numer.'' '''XVIII'''(1977), 35–58.
*P. Erdős: On the combinatorial problems which I would most like to see solved, ''Combinatorica'', '''1'''(1981), 28. {{doi|10.1007/BF02579174}}

{{DEFAULTSORT:Erdos conjecture on arithmetic progressions}}
[[Category:Combinatorics]]
[[Category:Conjectures]]

{{numtheory-stub}}

formulasearchengine - User contributions [en]

Economic production quantity