Asymptotic estimation of $A_n$

Let $A_n$ represent the number of integers that can be written as the product of two element of $[[1,n]]$.

I am looking for an asymptotic estimation of $A_n$.

First, I think it’s a good start to look at the exponent $\alpha$ such that :

$$A_n = o(n^\alpha)$$

I think we have : $2 \leq \alpha $. To prove this lower bound we use the fact that the number of primer numbers $\leq n$ is about $ \frac{n}{\log n}$. Hence we have the trivial lower bound (assuming $n$ is big enough) :

$$ \binom{ E(\frac{n}{\log n})}{2} = o(n^2)$$

Now is it possible to get a good asymptotic for $A_n$ and not just this lower bound ? Is what I’ve done so far correct ?

Thank you !

Solution 1:

Edit: The following is a better lower estimate.

A lower estimate here is for positive $x$, $$ \sum_{m, n\leq x} \frac1{\tau(mn)} $$ where $\tau(n)=\sum_{d|n}1$ is the number of divisors of $n$. This is because $\tau(mn)$ counts all possible choice of positive integers $d, k$ with $dk=mn$, not just the ones with $d\leq x, k\leq x$.

Such estimate can be given through Selberg & Delange Method. The method is shown in Tenenbaum's book Introduction to Analytic and Probabilistic Number Theory (Chapter 5, 6).

The following is in Page 207 Theorem 8 of Tenenbaum's book.

Theorem

Let $$ h=\prod_p \sqrt{p(p-1)}\log\left(1-\frac1p\right)^{-1}. $$ Then uniformly for $x\geq 2$, $d\geq 1$, we have $$ \sum_{n\leq x} \frac 1{\tau(nd)}=\frac{hx}{\sqrt{\pi\log x}}\left(g(d)+O\left( \frac{(3/4)^{w(d)}}{\log x}\right)\right) $$ where $g$ is an arithmetic function satisfying $$ \sum_{d\leq x} g(d)=\frac x{h\sqrt{\pi\log x}}\left(1+O\left(\frac1{\log x}\right)\right). $$

Applying this theorem on the estimate, we obtain $$ \begin{align} \sum_{m,n\leq x} \frac1{\tau(mn)} &=\frac{hx}{\sqrt{\pi\log x}}\left(\frac x{h\sqrt{\pi\log x}}+O\left(\frac x{\log^{3/2} x}\right)+O\left(\frac{\sum_{d\leq x}(3/4)^{w(d)}}{\log x} \right)\right)\\ &=\frac{hx}{\sqrt{\pi\log x}}\left(\frac x{h\sqrt{\pi\log x}}+O\left(\frac x{\log^{3/2} x}\right)+O\left(\frac{x\log^{-1/4}x}{\log x} \right)\right)\\ &=\frac{x^2}{\pi \log x}+O\left(\frac {x^2}{\log^{7/4} x}\right) \end{align}. $$

Solution 2:

The exact asymptotic isn’t known, but Kevin Ford astutely worked out the exact order of magnitude, not too long ago. So the only unknown is the constant in front (or perhaps even whether such a constant exists).

From the answer at https://math.stackexchange.com/a/1336590/30402, the value of $A_N$ satisfies upper and lower bounds of the form

$$ A_N \asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}. $$