# Chebotarev density theorem for $k$-almost primes

Consider a finite Galois extension $L$ of $\mathbb Q$, of Galois group $G$. Let $k \geq 1$ be a fixed integer. Let $D$ be a subset of $G^k$ invariant by conjugation and by the natural action of the symmetric group $S_k$ on $G^k$.

Let $A=A(L,D)$ be the set of all integers $n$ which are products of $k$ primes $n=p_1\dots p_k$ (variant: $k$ distinct primes) such that $(Frob_{p_1},\dots,Frob_{p_k}) \in D.$

(Here $Frob_p$ is a Frobenius at $p$ in $G$, assuming $p$ is unramified in $L$. if one of the $p_i$ is ramified, by convention say that $n$ is not in $A$.)

Let $A(x)$ be the number of integers $n<x$ in $A$.

Is there a known equivalent for $A(x)$ when $x$ goes to infinity?

Note that the case $k=1$ is Chebotarev's density theorem. In this case, $A(x) \sim \frac{|D|}{|G|} x/\log x$. In the general case, I would expect $$A(x) \sim c x/\log x \frac{(\log \log x)^{k-1}}{(k-1)!},$$ with a constant $c$ between $0$ and $1$ depending of $D$, $G$ (and perhaps only of $|D|$, $|G|$), based on the case $k=1$ and the case $D=G^k$, where $A$ is the set of all $k$-almost primes and the desired equivalent is a classical theorem of Landau. Because of these illustrious limit cases, I would not be surprised if this question was dealt with somewhere in the literature. But I couldn't find where.

I would already be interested in the case where $G$ is abelian. In this case the question takes a more classical form, which I explicit in case some readers are uncomfortable with Chebotarev. We can assume that $G=(\mathbb Z/a\mathbb Z)^\ast$. Then $D$ is a subset of $G^k$ invariant by permutation of the coordinates. The set $A$ is then the set of integers $n=p_1\dots p_k$ such that $(p_1 \pmod{a},\dots,p_k \pmod{a})$ is in $D$, and the question is still to find an equivalent for the number $A(x)$ of such integers $n$ which are $\leq x$.

Edit: I have made some computations in the simplest non trivial abelian case. This is the case $k=2$, and $L=Q(i)$ so that $G={1,-1}$ and $Frob_p$ for an odd $p$ is just $p \mod{4}$. You have $3$ basic subsets $D$ of $G^2$ invariant by $S_2$ which are $D_1 = \{(1,1)\}$, $D_0=\{(1,-1),(-1,1)\}$, $D_{-1}=\{(-1,-1)\}$. The corresponding sets of integers are the sets $$A_1=\{2-\text{almost primes } n=pq,\ \ p\equiv q \equiv 1 \pmod{4}\}$$ $$A_0 =\{2-\text{almost primes } n,\ \ n\equiv -1 \pmod{4}\}$$ $$A_{-1}=\{2-\text{almost primes } n=pq,\ \ p\equiv q \equiv -1 \pmod{4} \}.$$ I strongly expect in this case that the $A_{-1},A_1,A_0$ take respectively a proportion $1/4,1/4,1/2$ (or $|D|/|G|^2$) of all $2$-almost primes. If true, this is probably not to hard to prove by the method indicated by Lucia in comment. However, I have not been able to "see this" in the computation. For $x=10^7$, for instance, those proportions are $0.300,0.200,0.500$; for $x=5 \cdot 10^7$, they are $0.292,0.500,0.208$. I think the domination of products of two primes congruent to $-1$ above the products of two primes congruent to $1$ is well explained by the "primes race": the advantage of primes congruent to $-1$ among small primes is felt even more for the product of two primes. But this has discouraged me of making more computations to guess the correct value of the constant $c$...

• If $k$ is fixed and small, you can obtain such a result using Chebotarev and partial summation (painful but standard). If you are interested in $k$ maybe being large, one would have to work out the analog of Selberg's work. Also one can adapt the answer I gave to the problem of counting $k$-almost primes up to $x$ in order to get precise asymptotic formulae (e.g. on GRH). – Lucia Feb 7 '14 at 18:26
• @Lucia. I am interested in $k$ large. Actually the real thing I need is somewhat different: I have a fixed $G$, and a family of sets $D_k \subset G^k$ for all $k$, hence a set $A_k$ of integers for all $k$ as in the question, and I am interested in the density of the set $A=\cup_k A_k$. I shied away of asking this general question, restraining myself to the individual $A_k$, even though I know that it will be far from easy to deduce, if at all possible, to deduce a result for $A$ from results from the $A_k$. If you know of a more direct route to $A$, I'm very interested. – Joël Feb 7 '14 at 20:13
• Also, one reason to ask the question for a fixed $k$ is that it is possible that it has a simple answer, like: "yes, your expected equivalent for $A(x)$ is true with this value for the constant $c$", perhaps even the naive $c=|D|/|G|^k$; or "no; your formula is not true for any value of $c$". – Joël Feb 7 '14 at 20:15
• @Lucia: great answer! (--- though it seems to have been deleted now.) But what is the Selberg-Delange method? Pardon my ignorance! I just couldn't find a decent reference when Googling. – alpoge Feb 8 '14 at 0:49
• @alpoge: Thanks; I deleted my answer as I realized that Joel's question had an extra subtlety. This is now addressed in the answer below. For the Selberg-Delange method see Tenenbaum's book on analytic and probabilistic number theory; or Selberg's original paper (Note on a result of L.G. Sathe). – Lucia Feb 8 '14 at 1:28

I'll prove a more general result from which the Chebotarev question will follow. Let $P_1$, $\ldots$, $P_r$ be disjoint subsets of the primes such that the asymptotic formula $$\sum_{\substack{{p\le x}\\ {p\in P_j}}} 1 \sim \alpha_j \frac{x}{\log x}$$ holds with some $\alpha_j >0$. Let $N_k=N(k;a_1,\ldots,a_r)$ denote the set of integers that are products of $k$ primes with exactly $a_j$ of these primes chosen from the set $P_j$. Thus $a_1+\ldots+a_r=k$ and let's assume that all $a_j \ge 1$.
I claim that for fixed $k$ and as $x\to \infty$ $$\sum_{\substack {{n\le x}\\ {n\in N_k}}} 1 \sim k\prod_{j=1}^{r} \frac{\alpha_j^{a_j}}{(a_j)!} \frac{x}{(\log x)} (\log \log x)^{k-1}$$ The argument that follows is standard. The case $k=1$ follows from our assumption, and now suppose that $k\ge 2$.
Put $z=x^{1/\log \log x}$ and note that by partial summation $$\sum_{p\in P_j, p\le z} \frac{1}{p} \sim \alpha_j \log \log z \sim \alpha_j \log \log x$$ while $$\sum_{p \in P_j, z< p \le x} \frac{1}{p} \sim \alpha_j \log \log \log x.$$ Now suppose $n=p_1\cdots p_k$ is an element of $N(k;a_1,\ldots,a_r)$. We distinguish two cases: when the largest prime factor of $n$ is bigger than $z$ but all the other prime factors are smaller than $z$, and when the two largest prime factors of $n$ are both larger than $z$. (Of course there is also the case when all prime factors of $n$ are smaller than $z$, but this is clearly negligible.) The first case will be the main term and the second case will be a slightly smaller error.
Let's look at the first case. Suppose the largest prime factor (say $p$) of $n$ lies in the set $P_j$, so that the product of the smaller primes, say $m$, lies in $N(k-1;a_1,\ldots,a_{j}-1,\ldots,a_r)$. These terms give, upon summing over the last prime $p$, (note that as $m\le z^{k-1}$ we have $\log x \sim \log (x/m)$)
$$\sim \sum_{\substack{{m\in N(k-1;\ldots)} \\ {p|m\implies p\le z}} } \frac{\alpha_j x}{m \log (x/m)} \sim \frac{\alpha_j x}{\log x} \prod_{t=1, t\neq j}^{r} \frac{1}{a_t!} \Big(\sum_{p\le z, p\in P_t} \frac 1p\Big)^{a_t} \frac{1}{(a_j-1)!} \Big(\sum_{p\le z, p\in P_j}\frac 1p\Big)^{a_j-1}.$$ This is $$\sim a_j \prod_{t=1}^{r} \frac{\alpha_t^{a_t}}{a_t!} \frac{x}{\log x} (\log \log x)^{k-1}$$ and summing it over $j$ from $1$ to $r$ gives the claimed asymptotic.
Now for the second case. The sum over the largest prime $p$ gives a quantity bounded by (let $m$ be the product of the remaining primes and note that $m\le x^{(k-1)/k}$) $$\frac{x/m}{\log (x/m)} \ll \frac{x}{m \log x}.$$ Now sum this over the possible values of $m$, keeping in mind that $m$ has $k-1$ prime factors, and the largest prime factor of $m$ is assumed to lie in $[z,x]$.
Thus these terms are bounded by $$\ll \frac{x}{\log x} \Big(\sum_{p\le x} \frac{1}{p} \Big)^{k-2} \Big(\sum_{z< p\le x} \frac{1}{p}\Big) \ll \frac{x}{(\log x)} (\log \log x)^{k-2} (\log \log \log x).$$
Application to the Chebotarev question. Suppose $C_1$, $\ldots$, $C_r$ are distinct conjugacy classes in $G$. Suppose each element of the set $D$ (which is a $k$-tuple) consists of $a_1$ entries from $C_1$, $a_2$ entries from $C_2$, $\ldots$, $a_r$ entries from $C_r$. A little combinatorics shows that the size of the set $D$ (assumed to be conjugation and permutation invariant) is $$|D| = k!\prod_{j=1}^{r} \frac{|C_j|^{a_j}}{a_j!}.$$ In our work above take $P_j$ to be the primes $p$ for which Frobenius lies in the class $C_j$. Then by Chebotarev our assumed asymptotic for the primes in $P_j$ holds with $\alpha_j=|C_j|/|G|$. It follows that the number of integers in the original question is $$\sim \frac{|D|}{|G|^k} \frac{x}{\log x} \frac{(\log \log x)^{k-1}}{(k-1)!}.$$ This answers the Chebotarev question (assuming I got my combinatorics right) at least when $k$ is fixed. When $k$ grows, one has to do more work, but the Selberg-Delange method should work in this case with some effort; note here that one needs to use the structure of sets of Chebotarev primes, rather than just an arbitrary subset of the primes as above.