28
$\begingroup$

A positive integer is $B$-smooth if and only if all of its prime divisors are less than or equal to a positive real $B$. For example, the $3$-smooth integers are of the form $2^{a} 3^{b}$ with non-negative exponents $a$ and $b$, and those integers less than or equal to $20$ are $\{1,2,3,4,6,8,9,12,16,18\}$.

In Ramanujan's first letter to G. H. Hardy, Ramanujan emphatically quotes (without proof) his result on the number of $3$-smooth integers less than or equal to $N > 1$, \begin{eqnarray} \frac{\log 2 N \ \log 3N}{2 \log 2 \ \log 3}. \end{eqnarray} This is an amazingly accurate approximation, as it differs from the exact value by less than 3 for the first $2^{1000} \approx 1.07 \times 10^{301}$ integers, as shown by Pillai.

Question: Knowing full well that Ramanujan only gave proofs of his own claims while working in England, I wonder if a proof of this particular estimate appears somewhere in the literature. Is this problem still open? If not, what is a reference discussing its proof?

Thanks!

  • 0
    I take it that this problem is still _wide open_. That is, there is no closed form representation of the exact number of 3-smooth integers as a function of $N$.2011-05-12

3 Answers 3

22

Taking logs, one finds that $2^a 3^b \leq N$ if and only if $a \log 2 + b \log 3 \leq \log N.$ So estimating the number of 3-smooth integers $\leq N$ is the same as estimating the number of integer lattice points in the region $a, b \geq 0, a \log 2 + b \log 3 \leq \log N.$ The standard estimate for the number of integer lattice points in a convex region is the area of the region. In our case the region is a triangle, of area equal to $$\dfrac{1}{2}\dfrac{\log N}{\log 2}\dfrac{\log N}{\log 3},$$ which is close to the estimate you attribute to Ramanujan.

More precisely, the estimate you wrote down is equal to $$\dfrac{1}{2}\dfrac{\log N + \log 2}{\log 2}\dfrac{\log N + \log 3}{\log 3} = \dfrac{1}{2}\left(\dfrac{\log N}{\log 2} + 1\right)\left(\dfrac{\log N}{\log 3} + 1\right).$$ This probably improves the estimate coming from the area, by including correction terms coming from the integer points along the boundary of the region (in particular, the contributions coming from $a = 0$ or $b = 0$).

(The fact that these "boundary" contributions come with a multiplicity of $1/2$ seems similar to other contexts in which one approximates a discrete sum by an area, e.g. in Euler--MacLaurin summation, and perhaps thinking from that point of view would let one get a better handle on the precise estimates.)

  • 3
    You can probably get Ramanujan's estimate by tweaking Pick's theorem.2010-12-31
  • 0
    I understood "tweaking" to mean using integral triangles to understand the area above. I suppose if we generalize Pick's theorem to irrational triangles, it would help.2011-03-25
15

For any reference requirement related to Ramanujan, it is always a good idea to check the series of volumes, titled Ramanujan's notebooks, compiled and annotated by Bruce C. Berndt and others.

This is a special case of Entry 15 in Ramanujan's second notebook, which is about numbers of the form $\displaystyle a^p b^q$.

A reference to this can be found here: Ramanujan's notebooks, Volume 4.

(I suggest you read page 66 onwards)

A snapshot (from the google books link itself):

alt text

This volume talks about the "proof" Ramanujan gave (pages 68 and 69), provides references to Hardy's book (which apparently has a whole chapter on this) and also mentions a paper by Hardy and Littlewood which deals with it.

De Bruijn has considered the number of $y$-smooth numbers in this paper: On the number of positive integer less than x and free of prime factors greater than y.

The number of $y$-smooth numbers $\le x$ is apparently now known in literature as the DeBruijn function: $\psi(x,y)$.

A closely related function is the DeBruijn-Dickman function.

There is also a survey by Hildebrand and Tenenbaum which should be helpful.

10

If $2^a3^b \lt N, a \ln 2 + b \ln 3 \lt \ln N$ or $a+\frac{b \ln 3}{\ln 2}\lt \frac{\ln N}{\ln 2}$. For large $N$, we can ignore +1s, so to count the number less than $N$, we have $$\sum_{i=0}^\frac{\ln N}{\ln 3}\frac{\ln N-i\ln 3}{\ln 2}=\frac{(\ln N)^2}{\ln 2 \ln 3}-\frac{(\ln N)^2}{2\ln 2 \ln 3}$$ which is within a constant of the Ramanujan result.