Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
17  
Don't be so quick in closing this question. The estimate in Eric's answer is quite non-trivial. –  Felipe Voloch Oct 5 '12 at 17:42
9  
Isn't being an elementary, simple, difficult question motivation enough? –  Will Sawin Oct 6 '12 at 5:13
3  
Which of those three adjectives is immediately obvious? –  François G. Dorais Oct 6 '12 at 6:56
8  
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' –  quid Oct 6 '12 at 8:52
3  
Seems to be a duplicate of mathoverflow.net/questions/31663/… –  Gerry Myerson Apr 28 at 23:39

3 Answers 3

up vote 56 down vote accepted

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

share|improve this answer
    
Presumably $n=N$. –  Felipe Voloch Oct 5 '12 at 17:40
    
@Felipe: Fixed, thank you. –  Eric Naslund Oct 6 '12 at 1:12
10  
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 6 '12 at 4:44
2  
@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 6 '12 at 8:08
1  
@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 8:03

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

share|improve this answer
1  
This is Kevin P. Costello's comment: mathoverflow.net/questions/108912/… –  Eric Naslund Aug 14 at 14:20
    
ops, indeed, I have to be more careful –  Fedor Petrov Aug 14 at 14:27
    
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 at 14:33

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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