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.



Asymptotic lower bound for the number of square free with at least two prime factors
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.


