57

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

Qfwfq
  • 22,715
Kamalakshya
  • 887
  • I accidentally closed this a second ago. This cleared one vote to close that I will provide if this gets enough closing votes. – François G. Dorais Oct 05 '12 at 13:12
  • 24
    Don't be so quick in closing this question. The estimate in Eric's answer is quite non-trivial. – Felipe Voloch Oct 05 '12 at 17:42
  • I was going to close as soon as the count reached 4, but I will interpret Felipe's comment as a request not to do this. – François G. Dorais Oct 06 '12 at 02:13
  • I can't know for sure but I contend that the votes to close were due to the lack of background in the question. The OP should pay attention to this but also other users since many have the ability to edit the question to add some background and motivation when necessary. – François G. Dorais Oct 06 '12 at 02:16
  • 17
    Isn't being an elementary, simple, difficult question motivation enough? – Will Sawin Oct 06 '12 at 05:13
  • 4
    Which of those three adjectives is immediately obvious? – François G. Dorais Oct 06 '12 at 06:56
  • 14
    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' –  Oct 06 '12 at 08:52
  • What one could say perhaps for background is that since the sumset of the set (1,..., n) is very small standard heuristics dictate that the productset should be large (indeed by a classical conjecture at least Omega(n^(2-eps))). Of course O(n^2) is trvial. But everything significantly beyond that seems non-obvious. –  Oct 06 '12 at 09:01
  • 5
    Seems to be a duplicate of http://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table – Gerry Myerson Apr 28 '15 at 23:39
  • 4
    I suspect that at least some of the original down-voters thought (as did I at first) that the question was asking just for the size of the Cartesian product of ${1,\ldots,n}$ with itself. It's much harder with "$\times$" meaning setwise integer multiplication . . . – Noam D. Elkies Aug 14 '15 at 19:11

3 Answers3

74

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

Community
  • 1
Eric Naslund
  • 11,255
  • Presumably $n=N$. – Felipe Voloch Oct 05 '12 at 17:40
  • 18
    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. – Kevin P. Costello Oct 06 '12 at 04:44
  • 3
    @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? – Jernej Oct 06 '12 at 08:08
  • 2
    @jernej: There's a very nice small book by Mark Kac about the number of prime factors of integers. Otherwise, try Hardy and Wright. – Anthony Quas Jun 25 '13 at 08:03
  • @FedorPetrov: Thank you for the correction - it is now fixed. – Eric Naslund Aug 14 '15 at 13:10
  • Excuse me, but what does $\asymp$ denote here? That the quotient of the two quantities tends to $1$ as $N \to \infty$? – David Zhang Aug 14 '15 at 18:17
  • 1
    @DavidZhang: It means that it is both $\ll$ and $\gg$. (The symbol $\sim$ means that the quotient tends to $1$) – Eric Naslund Aug 14 '15 at 19:04
15

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\}$

Fedor Petrov
  • 102,548
  • 2
    This is Kevin P. Costello's comment: http://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-cdots-n-times-1-cdots-n/108939#comment280680_108939 – Eric Naslund Aug 14 '15 at 14:20
  • ops, indeed, I have to be more careful – Fedor Petrov Aug 14 '15 at 14:27
  • 3
    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. – Fedor Petrov Aug 14 '15 at 14:33
11

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

Peter Mueller
  • 20,764