1
$\begingroup$

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)$?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Apr 18, 2013 at 17:31
  • 5
    $\begingroup$ This is an exact duplicate of: mathoverflow.net/questions/108912/… $\endgroup$
    – Eric Naslund
    Commented Apr 18, 2013 at 17:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – user9072
    Commented Apr 18, 2013 at 17:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – user9072
    Commented Apr 18, 2013 at 18:25
  • 3
    $\begingroup$ 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 $\endgroup$
    – Douglas Zare
    Commented Apr 18, 2013 at 18:30

0

Reset to default