Number Theory – Asymptotic Lower Bound for the Number of Square Free with at Least Two Prime Factors

analytic-number-theoryasymptoticsnt.number-theoryprime-number-theorem

In one of Soundararajan's papers, he claims without proof that it is a standard exercise to show that the number $N(X)$ of positive square-free integers $d \equiv 1 \; \bmod \; 8$ less than $X$, with at least two primes factors all of which is congruent to $\pm1 \; \bmod \; 8$ is asymptotically bounded by $\frac{X}{\sqrt{\log(X)}}$ up to a constant. I am new to techniques in analytical number theory, and I find it hard to see this as a standard exercise. Based on my limited knowledge of such techniques I believe this may follow from some kind of Tauberian theorem. But, I couldn't come up with that sort of proof to the above fact. So I would like to see a standard proof of this fact.

Instead, I did some hand-wavy computations that lead me to a much stronger lower bound $\frac{X}{\sqrt{\log(\log X)}}$ (up to a constant). For simplicity, I present my ideas to just counting those $d$ with the stated properties but with prime factors congruent to $1 \; \bmod \; 8$ only, the general case is a simple extension of the same ideas. There are $M = M(x,r) = \frac{X^{1/r}}{8\log(X^{1/r})} = \frac{rX^{1/r}}{8\log(X)}$ number of primes less than $X^{1/r}$ and congruent to $1 \; \bmod \; 8$. So there are $\binom{M}{r}$ number of such $d<X$. Now summing them from $r = 2$ onwards we have $$N(X) = \sum_{r \geq 2} \binom{M(x,r)}{r} \gg \sum_{r \geq 2} {\left(\frac{rX^{1/r}}{8\log(X)}\right)}^r \frac{1}{r!} \gg X \sum_{r \geq 2} \frac{1}{{(8\log(X))}^r} \frac{r^r}{r!}.$$ And now using Stirling's approximation, $\frac{r^r}{r!} \approx \frac{e^r}{\sqrt{2 \pi r}}$. So $N(X) \gg X \sum_{r \geq 2} {\left(\frac{e}{8\log(X)}\right)}^r r^{-1/2}$, approximating the sum as an integral $$N(X) \gg \int_2^{\infty}a^x x^{-1/2} dx \approx \frac{\Gamma(1/2, -2 \log(a))}{\sqrt{-\log(a)}}\gg> \frac{1}{\sqrt{\log(\log X)}},$$ where $a = \frac{e}{8\log(X)}$. Hence we have the result. (I use "$\gg$" above to hide constants in the inequalities)

Since my method gives a somewhat stronger bound, I am skeptical if there is some flaw in my ideas. Please feel free to comment on what I have done.

Best Answer

Let us introduce a multiplicative function supported on squarefrees by $\alpha(p)=\mathbf{1}_{p \equiv \pm 1 \bmod 8}$. We are interested in $$\sum_{\substack{n \le x\\ n \equiv 1 \bmod 8\\ n \text{ has }\ge 2 \text{ prime factors}}} \alpha(n) \gg \frac{x}{\sqrt{\log x}}.$$ The primes have density $1/\log x = o(1/\sqrt{\log x})$, so we may omit the condition of having at least two primes factors.

Let us, for the moment, forget about the condition $n \equiv 1 \bmod 8$. The sum $\sum_{n \le x} \alpha(n)$ can be estimated by Wirsing's Theorem (the main theorem of 'Das asymptotische Verhalten von Summen über multiplikative Funktionen. II' (Acta Math. Acad. Sci. Hungar. 18 (1967), 411–467), giving $$ \sum_{n \le x} \alpha(n) \sim C\frac{x}{\log x} \prod_{p\le x} \left( 1+ \frac{\alpha(p)}{p}\right) = C\frac{x}{\log x} \prod_{\substack{p\equiv \pm 1 \bmod 8\\ p \le x}} \left( 1+ \frac{1}{p}\right) \sim D \frac{x}{\sqrt{\log x}}$$ for some positive constants $C,D$ depending on $\alpha$. An arithmetic input to these results is $\sum_{p \equiv a \bmod q, \, p \le x} 1/p = \log \log x/\phi(q) + O(1)$ with $q=8$.

A few remarks:

  • One alternative approach is the L-S-D (Landau-Selberg-Delange) method, as suggested by Lucia. Its advantage is that it gives an asymptotic expansion and not only a main term. Tenenbaum's book has good exposition on that. A guided exercise about Landau's original proof, mentioned by Lucia as well, appears in page 187 of Montgomery and Vaughan's book. Granville and Koukoulopoulos have a paper that gives results similar to the L-S-D method, but avoiding complex analysis ('Beyond the LSD method for the partial sums of multiplicative functions ').
  • A second alternative approach, which is elementary but very sophisticated, is Iwaniec's half-dimensional sieve.
  • There might be a simple (and non sieve-theoretic) elementary way to study $\sum_{n \le x} \alpha(n)$; see pages 182-184 of Selberg's Collected Papers, Vol II. There he derives quickly and elementarily a variant of Landau's result on sums of two squares.
  • If you are only interested in upper bounds, you could use a special case of Shiu's Theorem (`A Brun-Titschmarsh theorem for multiplicative functions'), where again the input will be $\sum_{p \le x, \, p \equiv a \bmod q} 1/p$.

Now, let us introduce back the condition $n \equiv 1 \bmod 8$. Let us define a multiplicative Möbius-like function:$$ \widetilde{\mu}(p) = \begin{cases} -1 & p \equiv -1 \bmod 8, \\ 1 & p \equiv 1 \bmod 8, \\ 0 & \text{otherwise.}\end{cases}$$ If $n$ is in the support of $\alpha$, $n \equiv (-1)^{\#\{ p \mid n : p \equiv -1 \bmod 8\}} \bmod 8$, so the condition we need to add is equivalent to $\widetilde{\mu}(n) = 1$. In other words, you are interested in evaluating $$\sum_{n \le x} \alpha(n) \frac{1+\widetilde{\mu}(n)}{2}$$ asymptotically. Since our Möbius-like function is oscillating, we would expect cancellation in $$\sum_{n \le x} \widetilde{\mu}(n)\alpha(n)$$ over the original sum. Such cancellation can be exhibited again by the L-S-D method. However, in the same paper of Wirsing mentioned above, there is a theorem (Satz 1.2.2) guarantying $$\sum_{n \le x} \widetilde{\mu}(n)\alpha(n) = o\left( \sum_{n \le x} \alpha(n)\right).$$ More generally, $\sum_{n \le x} \beta(n)/\sum_{n \le x} \alpha(n)$ can be asymptotically estimated if $\beta$ is dominated by $\alpha$ and $\alpha$ is `nice' enough.

Related Question