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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.

This is well researched by Erdos and others; it is the number of distinct values in the corresponding multplication table. You might start with… . Gerhard "Ask Me About System Design" Paseman, 2013.04.18 – Gerhard Paseman Apr 18 '13 at 17:31
This is an exact duplicate of:… – Eric Naslund Apr 18 '13 at 17:44
@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
@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
To look something like this up, you might compute a few values, then put them into the Online Encyclopedia of Integer Sequences. – Douglas Zare Apr 18 '13 at 18:30