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
    
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 5 '12 at 13:12
12  
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
6  
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
5  
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
show 3 more comments

2 Answers

up vote 39 down vote accepted

This question is known as the multiplication table problem, and was originally posed by Erdos in 1955. Erdos 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\ :\ 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
6  
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
1  
@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
    
@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
add comment

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

share|improve this answer
add comment

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.