58
$\begingroup$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?

Improve this question
$\endgroup$
10
  • 24
    $\begingroup$ Don't be so quick in closing this question. The estimate in Eric's answer is quite non-trivial. $\endgroup$
    – Felipe Voloch
    Commented Oct 5, 2012 at 17:42
  • 17
    $\begingroup$ Isn't being an elementary, simple, difficult question motivation enough? $\endgroup$
    – Will Sawin
    Commented Oct 6, 2012 at 5:13
  • 4
    $\begingroup$ Which of those three adjectives is immediately obvious? $\endgroup$
    – François G. Dorais
    Commented Oct 6, 2012 at 6:56
  • 14
    $\begingroup$ I upvoted Voloch's comment yet not the question. I agree this is not an optimal example how to write an MO question, but it is a quite precise mathematical question; what saves it for me is the second question, asking specifically for o(n^2), giving a quite clear idea what type of estimates the OP is after. Also it is tagged very well. And searching for it in the literature without a starting point could be tricky. That it is not easy can be tested by trying to solve it. And (legitimately) the only motivation might well be 'it seems like a natural problem and I could not do it' $\endgroup$
    – user9072
    Commented Oct 6, 2012 at 8:52
  • 5
    $\begingroup$ Seems to be a duplicate of mathoverflow.net/questions/31663/… $\endgroup$
    – Gerry Myerson
    Commented Apr 28, 2015 at 23:39

3 Answers 3

Reset to default
75
$\begingroup$

This question is known as the multiplication table problem, and was originally posed by Erdős in 1955. Erdős proved that $|A_n|=o(n^2)$, and this was sharpened by Tenenbaum in 1984. In 2008, Ford gave the exact magnitude and proved that $$\left|\lbrace a\cdot b:\ a,b\leq N\rbrace\right|\asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}},$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}.$$

In 2010 Koukoulopoulos gave multidimensional generalizations of Ford's result, proving that $$\left|\lbrace a_1\cdots a_{k+1}\ :\ a_i\leq N \text{ for all } \ i\rbrace\right|\asymp \frac{N^{k+1}}{(\log N)^{c_k}(\log\log N)^{3/2}},$$ where $$c_{k}=\int_{1}^{\frac{k}{\log(k+1)}}\log x\text{d}x=\frac{\log(k+1)+k\log\left(k\right)-k\log\log(k+1)-k}{\log(k+1)}.$$

Some references:

  • Ford 2008: The distribution of integers with a divisor in a given interval. arXiv link

  • Koukoulopoulos 2010: Localized Factorization of Integers. arXiv link

  • Koukoulopoulos 2012: On the number of integers in a generalized multiplication table. arXiv link

Remark: The dates used above refer to the publication dates (not necessarily the date posted to the arXiv).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Presumably $n=N$. $\endgroup$
    – Felipe Voloch
    Commented Oct 5, 2012 at 17:40
  • 18
    $\begingroup$ If all you're looking to show is $o(n^2)$, then I believe Erdos' original argument can get you there somewhat faster. As a very rough sketch, the idea is: 1. By a result of Hardy and Ramnujan, almost all integers between $1$ and $n$ have roughly $\ln \ln (n^2)=\ln \ln n+O(1)$ prime factors. 2. Almost all pairs $(x,y)$ have approximately $2\ln \ln n$ prime factors dividing $xy$ (since $x$ and $y$ usually won't share many factors). 3. Since most products lie in only a small subset of $\{1,…,n^2\}$ (the numbers having an unusually large number of factors), most of the rest must remain uncovered. $\endgroup$
    – Kevin P. Costello
    Commented Oct 6, 2012 at 4:44
  • 3
    $\begingroup$ @Kevin P. Costello Do you happen to know a book or survey paper covering these types of results as the one of Hardy and Ramanujan about almost all integers and their prime factors? $\endgroup$
    – Jernej
    Commented Oct 6, 2012 at 8:08
  • 2
    $\begingroup$ @jernej: There's a very nice small book by Mark Kac about the number of prime factors of integers. Otherwise, try Hardy and Wright. $\endgroup$
    – Anthony Quas
    Commented Jun 25, 2013 at 8:03
  • 1
    $\begingroup$ @DavidZhang: It means that it is both $\ll$ and $\gg$. (The symbol $\sim$ means that the quotient tends to $1$) $\endgroup$
    – Eric Naslund
    Commented Aug 14, 2015 at 19:04
15
$\begingroup$

Let me give here an answer with a quick argument why it is $o(n^2)$. I do not know whether it is the same as Erdős original proof. UPD: it really is, and is mentioned above in a comment by Kevin P. Costello.

Most numbers from 1 to $n$ have $\log \log n (1+o(1))$ prime divisors (counted with multiplicity) by Erdős-Kac theorem. Then most their products have $2\log \log n (1+o(1))$ prime factors, while most numbers from 1 to $n^2$ have again $\log \log n (1+o(1))$ prime factors. It proves that products of two numbers from 1 to $n$ are rare in $\{1,2,\dots,n^2\}$

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This is Kevin P. Costello's comment: mathoverflow.net/questions/108912/… $\endgroup$
    – Eric Naslund
    Commented Aug 14, 2015 at 14:20
  • $\begingroup$ ops, indeed, I have to be more careful $\endgroup$
    – Fedor Petrov
    Commented Aug 14, 2015 at 14:27
  • 3
    $\begingroup$ But let me leave it here, as it is easier to see an answer than a comment and it has micro-advantage by counting the number of prime divisors with multiplicity, which makes this function satisfying $f(xy)=f(x)+f(y)$ without errors. $\endgroup$
    – Fedor Petrov
    Commented Aug 14, 2015 at 14:33
11
$\begingroup$

The answer is yes, for further infos see the references given at the On-Line Encyclopedia of Integer Sequences.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .