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$...

  • 1
    $\begingroup$ 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). $\endgroup$
    – Lucia
    Feb 7, 2014 at 18:26
  • $\begingroup$ @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. $\endgroup$
    – Joël
    Feb 7, 2014 at 20:13
  • $\begingroup$ 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$". $\endgroup$
    – Joël
    Feb 7, 2014 at 20:15
  • $\begingroup$ @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. $\endgroup$
    – alpoge
    Feb 8, 2014 at 0:49
  • 1
    $\begingroup$ @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). $\endgroup$
    – Lucia
    Feb 8, 2014 at 1:28

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.