Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I read in an article of Erdős ("Extremal problems in number theory") that he had a proof of the multiplicative version of the Erdős-Turán conjecture. The statement of this theorem is

Let $a_1 < a_2 < \cdots$ and denote by $g(n)$ the number of solutions to $n=a_ia_j$. Then $g(n)>0$ for all $n>n_0$ implies $$\limsup_{n\to \infty} \ g(n)=\infty.$$

He also claims that this follows under the weaker assumption: let $A(x)=\sum_{a_i < x} 1$. Assume that for every $k$ we have $$\limsup_{x\to \infty} \ A(x)\left(x\left(\frac{\log\log x}{\log x}\right) ^k \right)^{-1}=\infty$$ than the same conclusion follows. However he also says that the proofs are difficult and haven't been published yet.

Since that article is from 1965 I am assuming he must have published something about this theorem afterward, but I don't have a reference. I have seen a proof of the first statement before (not by Erdős), but not the second one. Does anyone know if these proofs were published, simplified or generalized?

share|cite|improve this question

2 Answers 2

up vote 13 down vote accepted


P. Erdõs: On the multiplicative representation of integers, Israel J. Math. 2 (1964), 251--261 (see: )

A somewhat different proof is given in:

Nešetřil, Rödl, Two proofs in combinatorial number theory. Proc. Amer. Math. Soc. 93 (1985), no. 1, 185–188.

share|cite|improve this answer
Thanks! Now I'm wondering why he said he hadn't published these proofs in an article he published a couple of months later.. :) –  Gjergji Zaimi Dec 17 '10 at 23:08
Maybe he wrote the IJM paper as a consequence of the other article? –  Andrés Caicedo Dec 17 '10 at 23:20

There is a generalization of Erdos' theorem in my paper "Multiplicative representations of integers," Israel Journal of Mathematics 57 (1987), 129--136.

share|cite|improve this answer
Welcome, Dr. Nathanson. –  Andrés Caicedo Dec 18 '10 at 2:46

Your Answer


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.