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

$\endgroup$
10
  • 23
    $\begingroup$ Don't be so quick in closing this question. The estimate in Eric's answer is quite non-trivial. $\endgroup$ Oct 5, 2012 at 17:42
  • 16
    $\begingroup$ Isn't being an elementary, simple, difficult question motivation enough? $\endgroup$
    – Will Sawin
    Oct 6, 2012 at 5:13
  • 4
    $\begingroup$ Which of those three adjectives is immediately obvious? $\endgroup$ 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
    Oct 6, 2012 at 8:52
  • 5
    $\begingroup$ Seems to be a duplicate of mathoverflow.net/questions/31663/… $\endgroup$ Apr 28, 2015 at 23:39

3 Answers 3

73
$\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).

$\endgroup$
7
  • $\begingroup$ Presumably $n=N$. $\endgroup$ 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$ 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
    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$ 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$ 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\}$

$\endgroup$
3
  • 2
    $\begingroup$ This is Kevin P. Costello's comment: mathoverflow.net/questions/108912/… $\endgroup$ Aug 14, 2015 at 14:20
  • $\begingroup$ ops, indeed, I have to be more careful $\endgroup$ 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$ 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.