1

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

Community
  • 1
user31074
  • 21
  • 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 http://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table . 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: http://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-n1-n/108939#108939 – 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. –  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. –  Apr 18 '13 at 18:25
  • Oh dear, I was trying to edit my comment and ended up deleting it.

    @everyone: Thanks for all the references.

    @quid: Thank you, that sort of estimate will suffice for my purposes.

    To those wondering, I'd asked if there were any obvious ways of lower bounding $c_n$.

     – user31074 Apr 18 '13 at 18:29
  • 3
    To look something like this up, you might compute a few values, then put them into the Online Encyclopedia of Integer Sequences. http://oeis.org/A027424 – Douglas Zare Apr 18 '13 at 18:30
  • Reposting a link mentioned in a previous comment so that it appears in the "Linked" questions list: Distinct numbers in multiplication table – The Amplitwist May 18 '23 at 15:50

0 Answers0