Numbers divisible by the square of their largest prime factor

Solution 1:

What follows is self contained proof that $$f(x)=\sum_{\begin{array}{c} n\leq x\\ n\in A \end{array}}1 \ll x e^{-c\sqrt{\log x}}.$$ If you work more carefully with the friable integers, you can recover Erdős' result.

Proof. We may write $$\sum_{\begin{array}{c} n\leq x\\ n\in A \end{array}}1=\sum_{\begin{array}{c} np^{2}\leq x\\ n\in S(p) \end{array}}1 = \sum_{p\leq\sqrt{x}}\sum_{\begin{array}{c} n\leq x/p^{2}\\ n\in S(p) \end{array}}1$$ where $S(y)=\left\{ n:\ P(n)\leq y\right\}$ is the set of $y$-friable integers. Notice that $$ \sum_{p\leq\sqrt{x}}\sum_{\begin{array}{c} n\leq x/p^{2}\\ n\in S(p) \end{array}}1 \leq x\sum_{B\leq p}\frac{1}{p^{2}}+\sum_{\begin{array}{c} n\leq x\\ P(n)\leq B \end{array}}1.\ \ \ \ \ \ \ \ \ \ (1)$$ The first term is $\leq\frac{x}{B}$, and the second term may be bounded using Rankin's Trick, which we will now use. Let $\sigma>0$, and notice that $$\sum_{n:\ P(n)\leq B}1\leq\sum_{\begin{array}{c} n=1\\ P(n)\leq B \end{array}}^{\infty}\left(\frac{x}{n}\right)^{\sigma}=x^{\sigma}\prod_{p}\left(1-\frac{1}{p^{\sigma}}\right)^{-1}.$$ For $\sigma=1-\frac{1}{\log B},$ the above is $$\ll xe^{-\frac{\log x}{\log y}}\exp\left(e\sum_{p\leq B}\frac{1}{p}\right)\ll xe^{-\frac{\log x}{\log B}}\left(\log B\right)^{e}.$$ Setting $B=e^{\sqrt{\log x}},$ it follows that $$\sum_{\begin{array}{c} n\leq x\\ n\in A \end{array}}1\ll xe^{-\sqrt{\log x}},$$ and the result is proven.

Remark: Erdős' result may be recovered in the following manner: First, to obtain the extra $\sqrt{\log \log x}$ in the upper bound, you need a bound of the form $$\Psi(x,y)=\sum_{\begin{array}{c} n\leq x\\ P(n)\leq y \end{array}}1 \ll x u^{-(1+o(1))u}$$ where $u=\frac{\log x}{\log y},$ rather than Rankin's trick. Now, the asymptotic can be obtain by bounding the second term in equation $(1)$, and noticing that the first term will provide us with our main term.

Solution 2:

If $n\in A$ then $n$ is divisible by $p(n)^2$, so that $n$ cannot divide $P(n)!$. Hence it is enough to show that $S(x)=\{n \le x \mid n \nmid p(n)!\}$ satisfies $|S(x)|=o(x)$ for $x\to \infty$. This was shown by I. Kastanas, The smallest factorial that is a multiple of $n$ (solution to problem 6674), Amer. Math. Monthly 101 (1994), p.179. On the other hand, already some of the arguments Erdős gives for (1) are already enough to conclude (2), but since the question says "without use (1)", the other way seems better.