Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics:

Conjecture: If $A\subset \mathbb{N}$ and $$\sum_{a\in A} \frac{1}{a}$$ diverges, then $A$ contains arbitrarily long arithmetic progressions.

This is often called either "The Erdős-Turán conjecture" or "Erdős's conjecture on arithmetic progressions."

I want to make sure I quote things correctly in my writing, and my main question is, who should this conjecture be attributed to?

I am asking because I find a lot of conflicting pieces of information regarding how it should be referred to. For example, the Wikipedia page and the two Wolfram pages, page A and page B, are in disagreement. Wikipedia seems to be adamant that calling it the Erdős-Turán conjecture is incorrect, however I am skeptical, as it does not seem to be so clear. Also, both of the choices are used in many papers in the literature.

I went back and read the original 1936 paper of Erdős and Turán, "On some sequences of integers." (Math Sci Net MR1574918). In that paper, they conjecture that $r(N)=o(N)$, where $r(N)$ is a maximal subset of $\{1,\dots,N\}$ without 3 term arithmetic progressions. They also mention the (incorrect) conjectures of Szekeres on $k$ term progressions, but other than that, they don't seem to mention any conjectures regarding longer progressions at all.

As far as I can tell, the above conjecture first appears in the 1972 paper of Erdős, "Résultats et problèmes en théorie des nombres." (Math Sci Net MR0396376) This suggests that the conjecture should be named after Erdős, however, I believe that there must some reason why this conjecture has often been attributed to Turán as well. I can't imagine that it would be done for no reason, and it is entirely possible that the reason why credit is given to both Erdős and Turán was not written down, or at least, is not easy to find.

I am hoping someone can shed some light on this, and provide a clearer answer for what to call the above conjecture.

Thanks for your help,

share|improve this question
8  
Technically it should be an en-dash rather than a hyphen. –  Timothy Chow Jun 3 '13 at 20:30
    
@Butch Malahide: Thanks, I edited to put in the hyphen. –  Eric Naslund Jun 3 '13 at 21:36
2  
@Butch Doesn't matter. At least OP got the ő right, which is the most important thing. Copyeditors are happy to nitpick the en-dash thingy and apostrophe+s grammar but can't fix your ö. –  Yuichiro Fujiwara Jun 4 '13 at 15:37
2  
@Butch: The reason for insisting on an en-dash instead of a hyphen is pretty much the same as the reason you gave for connecting the two names in the first place: “the Erdős-Turán conjecture” looks like a conjecture made by one person whose double-barrelled surname is Erdős-Turán. Think Paul du Bois-Reymond. I thus can’t comprehend the double standards that avoiding a space is so important while avoiding a hyphen is “fascism” and “nitpicking”. –  Emil Jeřábek Jun 4 '13 at 16:44
1  
@Butch: Typewriters were not marketed commercially until 1870, and the en dash was around long before that. But since you were already 2,999,999,437 years old when Gutenberg's printing press came into operation, I can see why you might have trouble adapting to these new-fangled inventions. By the way, dashes come in only two sizes; a hyphen is not a dash. –  Timothy Chow Jun 5 '13 at 20:24
show 2 more comments

2 Answers 2

up vote 16 down vote accepted

One of the best places to track these things down is The mathematical coloring book, by Alexander Soifer, Springer 2009. Chapter 35 is on "Monochromatic arithmetic progressions", and section 35.4, "Paul Erdős’s Favorite Conjecture", is on the problem you ask about.

As far as I can tell, the question is sometimes called the Erdős-Turán conjecture for two reasons: First, it extends their older conjecture (now Szemerédi's theorem). Second, it was first popularized in connection to Turán, see below.

Soifer identifies a problem paper in the premier issue of Combinatorica as the first place in print were the conjecture appears with the attached value of $\$3000$: On the combinatorial problems which I would most like to see solved, Combinatorica, 1 (1981), 25–42, submitted Sep. 15, 1979.

Soifer adds that apparently Erdős first offered this amount in a 1976 talk, "To the memory of my lifelong friend and collaborator Paul Turán", in a conference the University of Manitoba, see 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. (Erdős calls it "A very attractive conjecture of mine.")

In Problems and results on combinatorial number theory, II, J. Indian Math. Soc. (N.S.), 40(1–4) (1976), 285–298, he stated the conjecture with an attached prize of $\$2500$. In page 288 of this paper, we read (mildly edited for typos):

$2.$ An old conjecture in number theory states that for every $k$ there are $k$ primes in arithmetic progression. This conjecture would immediately follow if we could prove that for every $k$ and $n\gt n_1(k)$, $r_k (n) \lt \pi (n)$.

Here, as usual, $r_k(n)$ is the size of the largest subset of $\{1,2,\dots,n\}$ without $k$-term progressions.

This method of proof seems very attractive, it tries to prove a difficult property of the primes by just using the facts that the primes are numerous. In some cases I have been successful with this simple minded approach. In this connection I recently formulated the following conjecture for the proof or disproof of which I offer $2500$ dollars:

Let $a_l \lt a_2 \lt\dots$ be an infinite sequence of integers satisfying $\sum\frac1{a_i}=\infty$. Then for every $k$ there are $k$ $a$'s in an arithmetic progression.

(The truth of this conjecture would imply that for every $k$ there are $k$ primes in arithmetic progression). One can put this problem in a finite form as follows: Put $$g_k (n) = \max\sum_{a_i>n}\frac1{a_i},\quad G (k) = \lim_{n=\infty} g_k (n),$$ where the maximum is extended over all sequences $\{a_i\}$ not exceeding $n$ which do not contain an arithmetic progression of $k$ terms. The $2500$ dollar conjecture is equivalent to $G(k) \lt\infty$ for every $k$ (it is not quite trivial to show that $G (k) = \infty$ implies the falseness of the conjecture).

By the way, the prize currently attached to the conjecture is actually $\$5000$. Soifer indicates that the update occurred in the paper Some of my favorite problems and results, in The Mathematics of Paul Erdős, vol. I, Graham, R. L., and Nesetril, J., (eds), 47–67, Springer, Berlin, 1997. (The paper appeared posthumously, and was written in 1996.)

I offer $5000 for a proof (or disproof) of this [problem]. Neither Szemerédi nor Furstenberg’s methods are able to settle this but perhaps the next century will see its resolution.

Soifer then tries to identify when the conjecture was first stated.

I searched for evidence in the ocean of his writings, and found three indicators. First, in a paper submitted on September 7, 1982 to Mathematical Chronicle (now called New Zealand Journal of Mathematics) that appeared the following year [E83.03], Paul writes: "This I conjectured more than forty years ago."

In the same year, 1982, Paul spoke at the Conference on Topics in Analytic Number Theory in Austin, Texas. I read in the proceedings (published in 1985 [E85.34], p. 60): "I conjectured more than 40 years ago that if $a_1 \lt a_2\lt \dots$ is a sequence of integers for which $\sum_{i=1}^\infty \frac1{a_i}=\infty$ then the $a$’s contain arbitrarily long arithmetic progressions."

Thus, both of these publications indicate that the conjecture was posed before 1942. On the other hand, in the 1986 Jinan, China, Conference proceedings (published in 1989 [E89.35]), Paul writes (p. 142): "About 30 years ago I conjectured that if $\sum_{n=1}^\infty 1/{a_n}=\infty$, then the $a$'s contain arbitrarily long arithmetic progressions." This would date the birth of the conjecture to about 1956.

The cited papers are:

  • [E83.03]: Combinatorial problems in geometry, Math. Chronicle 12 (1983), 35–54.
  • [E85.34]: Some solved and unsolved problems of mine in number theory, in Topics in Analytic Number Theory (Austin, Tex., 1982), Univ. Texas Press, Austin, TX, 1985, 59–75.
  • [E89.35]: Some problems and results on combinatorial number theory, in Graph theory and its applications: East and West (Jinan, 1986), Ann. New York Acad. Sci. 576, 132–145, New York Acad. Sci., New York, 1989.

For the finitude of $G_k$, see for example ArxiV:math/0703467.

By the way, the conjecture in the 1972 paper you identify seems to be restricted to $3$-term progressions. Even this version remains open (and carries an attached prize of $\$250$.)

share|improve this answer
1  
BTW, Prof. Alexander Soifer is a member of the MO community: mathoverflow.net/users/13436/alexander-soifer –  J. H. S. Jun 4 '13 at 2:08
    
Why, indeed! Thanks. Hopefully he'll notice this question, he may have further comments to add. –  Andres Caicedo Jun 4 '13 at 3:06
add comment

In the first paragraph of page 233 of [1], we read the following:

Erdős conjectured that the sequence of primes contains arbitrarily long arithmetic progressions and, even more, that every sequence $1\leq a_{1} < a_{2} <... $ with $\sum_{n=1}^{\infty}\frac{1}{a_{n}} = \infty$ contains arbitrarily long arithmetic progressions. He offered $\$3000$ for this conjecture.

Besides, I believe that we can find a possible explanation of how the surname Turán got added in the last paragraph of page 232...

References

[1] B. Bollobás. To Prove and Conjecture: Paul Erdős and His Mathematics. Amer. Math. Monthly 3 (105), 1998.

[2] Alex R. Erdős conjecture on arithmetic progressions. math-overflow

share|improve this answer
6  
For those who are curious, in the last paragraph of page 232, we read, "In 1936, Erdős and Turán conjectured the far-reaching extension of van der Waerden's theorem on arithmetic progressions that if a_1 < a_2 < ... is a sequence of natural numbers such that, for some c > 0, we have a_n < cn for infinitely many values of n, then the sequence contains arbitrarily long arithmetic progressions." –  Timothy Chow Jun 3 '13 at 20:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.