Take the 2-minute tour ×
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|improve this question
add comment

2 Answers 2

up vote 13 down vote accepted

Yes.

P. Erdõs: On the multiplicative representation of integers, Israel J. Math. 2 (1964), 251--261 (see: http://www.renyi.hu/~p_erdos/1964-20.pdf )

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|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? –  Andres Caicedo Dec 17 '10 at 23:20
add comment

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

share|improve this answer
5  
Welcome, Dr. Nathanson. –  Andres Caicedo Dec 18 '10 at 2:46
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.