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

Possible Duplicate:
Number of elements in the set {1,…,n}*{1,..,n}

Writing $[n]$ for the set $\lbrace1,2,...,n\rbrace$, let $P_n$ denote the product set $[n].[n]$, i.e. $$ P_n = \lbrace ab : a,b \in [n]\rbrace .$$

Since the set $[n]$ is quite far from looking like a geometric progression, one would suspect that the set $P_n$ is quite large. Let $$ c_n = \frac{|P_n|}{n^2} .$$

I was hoping to find out what the asymptotics are for $c_n$; I suspect the answer is well known to additive combinatorialists. In particular, is $c_n$ bounded away from $0$ or is it $o(1)$?

share|improve this question

marked as duplicate by Eric Naslund, Douglas Zare, Anthony Quas, Suvrit, Goldstern Apr 18 '13 at 20:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
This is well researched by Erdos and others; it is the number of distinct values in the corresponding multplication table. You might start with mathoverflow.net/questions/31663/… . Gerhard "Ask Me About System Design" Paseman, 2013.04.18 –  Gerhard Paseman Apr 18 '13 at 17:31
5  
This is an exact duplicate of: mathoverflow.net/questions/108912/… –  Eric Naslund Apr 18 '13 at 17:44
1  
@Eric Naslund: so it is a an exact duplicate of an almost duplicate ;-) I knew I saw this somewhere not that long ago (and indeed the first thing I did was to search the site but somehow this did not turn up). Now, that not even the reference is new, I will delete the answer. –  quid Apr 18 '13 at 17:53
1  
@bn: yes, if I understand you right. You will have n/log n prime numbers and all their products (except for symmetry) will be distinct, yielding already a lower bound of n^2/ (2(log n)^2) for the number of products. –  quid Apr 18 '13 at 18:25
3  
To look something like this up, you might compute a few values, then put them into the Online Encyclopedia of Integer Sequences. oeis.org/A027424 –  Douglas Zare Apr 18 '13 at 18:30