Define $\pi_{n,a}(x)$ as the number of primes $p$ less than $x$ such that $p\equiv a\bmod n$ for coprime $n,a$. This function can be asymptotically approximated by $$\pi_{n,a}(x)=\frac{\operatorname{Li}(x)}{\varphi(n)}$$

This allows for the conclusion that, as $x$ tends to infinity, $\pi_{4,1}(x)\sim\pi_{4,3}(x)$. In other words, there are as many primes congruent to $1 \bmod 4$ as there are congruent to $3 \bmod 4$. Can this theorem be extended to prime gaps? In other words, can it (or any other theorem, for that matter) be used to describe the distribution or density of prime gaps in specific residue classes?

Update: Let $\gamma_{n,a}(x)$ denote the number of prime gaps $g=p_i-p_{i-1}$ for $p_i\leq x$ such that $g\equiv a \bmod n$. It is quite straightforward to show that, as $x$ tends to infinity, $\gamma_{6,2}(x)\sim\gamma_{6,4}(x)$ and $\gamma_{4,0}(x)\sim\gamma_{4,2}(x)$. However, I am unable to properly estimate $\gamma_{6,0}(x)$ (unlike $\pi_{n,a}$, it seems that $\gamma_{n,a}$ does depend on $a$), or any other value of $a$ and $n$ for that matter.

  • 1
    $\begingroup$ Looking at $\pi_{n,a}(x)$ for each $a$ is not very different to looking at $\sum_{m < x} \chi(m) \Lambda(m) = A x + O(1)-\sum_\rho \frac{x^\rho}{\rho}$ for each Dirichlet character $\chi$ modulo $n$, where $\rho$ are the non-trivial zeros of $L(s,\chi)$, and $A = 0$ if $\chi$ is not the trivial character $\endgroup$
    – reuns
    Jun 2, 2017 at 21:23
  • 1
    $\begingroup$ Do you have a paper or resource I could look at? I can't seem to find anything related with a simple search $\endgroup$
    – Romain S
    Jun 2, 2017 at 21:33
  • 1
    $\begingroup$ Maybe I take a day to digest, and get back to you then. $\endgroup$
    – user56983
    Aug 11, 2017 at 1:02
  • 1
    $\begingroup$ @VincentGranville This is an old question, and from what I've gathered from my education over the past couple years, the answer is probably still "unsure". This kind of prime gap question tends to require more serious analytic number theory to yield a satisfactory answer (as reuns alluded to in his or her comment)... Nevertheless, it's still quite interesting to think about! Moral of the story: I should learn more serious number theory, and then might have a hope at understanding what's really going on here. $\endgroup$
    – Romain S
    Jul 14, 2020 at 15:18
  • 1
    $\begingroup$ @Romain: thank you. See my new question related to this topic, at mathoverflow.net/questions/365626/… $\endgroup$ Jul 14, 2020 at 17:12

1 Answer 1


This is probably best suited to using the more elementary technique of setting up a set of compound arithmetic progressions, which is a class of arithmetic progressions where both the residue and the modulus are linear forms in $(\mathbb{Z}^+)^{\mathbb{Z}^+}$. Apostol gives a touching exposition on Dirichlet characters, but I'm not going to use them. Davenport's Multiplicative Number Theory is another inspiring work, but his is analytical, where this draws from topology and makes inferences to the analytical.

However, we can make reasonable descriptions of observable phenomena without too much speculation and appreciate along the way the artistry that makes some areas of mathematics quite inviting. Note that Dirichlet's Theorem applies only to those residue classes where the residue and the modulus are relatively prime.

Definition of a Compound Arithmetic Progression. Let $A,M \in (\mathbb{Z}^+)^{\mathbb{Z}^+}$ be linear forms, and $[a]_m^+ = \{ a \pmod{m}\} \cap [a+m, \infty)$ such that $[A]_M^+ = \bigcup_{x\in \mathbb{Z}^+}{[ax+b]^+_{cx+d}}$ is a compound arithmetic progression (CAP) when both $A$ and $M$ share a common dependent variable. If $0 \le ax + b < cx + d : \forall x\in \mathbb{Z}^+$, then $[A]^+_M$ is a least compound arithmetic progression and $n \in [A]^+_M \implies n \equiv ax+b \pmod{cx+d}$.

Matrix Form of a Compound Arithmetic Progression. If $T$ is a CAP, then the matrix representation is defined as $M(T) := \begin{pmatrix} -a & n-b \\ c & d \end{pmatrix}$

Then $det(M(T)) := -ad - c(n-b) = -c(n-b) -ad$, and $-det(M(T)) = c(n-b) + ad$.

If $n \in T$, $$n \equiv ax+b \pmod{cx+d} \implies n = ax+b + y(cx+d) $$ $$ n = cxy + ax + dy + b \implies n-b=cxy+ax+dy$$ $$ c(n-b) = c^2 xy+acx+dcy $$ $$ (cy+a)(cx+d) = c^2 xy + acy +dcx + ad $$ $$ c(n-b) = (cy+a)(cx+d) - ad $$ $$ -det( M(T)) = c(n-b) + ad = (cy+a)(cx+d) $$

Because $-det(M(T))$ is a linear form when $n$ is allowed to range over the positive integers and $\{a,b,c,d\} \in \mathbb{Z}^4$ is fixed, $T$ possesses the isomorphism $$ T \cong [a]^+_c \otimes [d]^+_c $$ where $\otimes$ indicates the direct product (where a set is formed by multiplying each element of one set by each element of the other set) and $a$, $d$ are the commutative residues. [see Rose, H.E. A Course in Number Theory for previous usage of $\otimes$] [see Lang, Serge for his treatment of Möbius Transformations in Complex Analysis which is useful as well, for the algebraically similar structure $PGL(2,\mathbb{C})$]

Next we describe a structure in terms of terms of the above that joins pairwise the $\mod{c}$ characters ${ \chi_a, \chi_d }$ when we only know the value of the product $\chi_{ad} = \chi_a \chi_d$. However, if $G$ is a multiplicative group of characters, the group does not possess prime elements and the set of possible values of $\chi_{ad} \in G$ is precisely $G$. (Kowalski and Iwaniec: Analytic Number Theory.)

Definition of Composite Topology in an Arithmetic Progression. First, if we want to find something out about the one-dimensional structure of the primes in an arithmetic progression, then we can use the type defined above to give a syntactical context. We begin by choosing the product $ad < c$ such that $(ad, c) = 1$ and $ad \in (\mathbb{Z}/c \mathbb{Z})^*$, the group closed under multiplication.

Restricting ourselves to the the positive least residues, we can collect the direct products of the residue classes $a_i d_i \equiv ad \equiv r \pmod{c}$

Let $T_i \cong [a_i]^+_{c} \otimes [d_i]^+_{c}$ and define $a_i, d_i$ so that $\cup T_i = [ad]_c \setminus (\mathbb{P} \cap [ad]_c)$

For example, we can dissect $[3]^+_5$ using this technique. The pairs of residue classes $\mod 5$ whose product is $3$ is given by

$$ [1]_5 \otimes [3]_5, [2]_5 \otimes [4]_5 $$

Which is great, because we can use the direct products above and group theory to know which elements of the arithmetic progression are prime and which are not prime, without using SOE, because each composite number in the arithmetic progression falls within one of the direct products listed above, and the following relationship is described.

$$[3]_5 \setminus (\mathbb{P} \cap [3]_5) = \bigcup\{ [1] \otimes [3], [2] \otimes [4]\}_{\pmod{5}} $$

Putting the direct products into the form required by the definition of the composite topology of an arithmetic progression, such that $\cup T_i = [ad]_c \setminus (\mathbb{P} \cap [ad]_c)$, we observe the following, when we wrap from residue classes into arithmetic progressions:

$$ [3]_5 \setminus (\mathbb{P} \cap [3]_5) = \bigcup\{ [1]^+ \otimes [-2]^+, [-3]^+ \otimes [-1]^+\}_{\pmod{5}} $$

This is because we need to include the integers in the open interval $(1, c)$ as part of the determination, so that the infima of each arithmetic progression is a positive least residue $\mod{5}$

Then if $a_i$ is allowed to range over the multiplicative group $(\mathbb{Z}/c\mathbb{Z})^*$ and $d_i \equiv \bar{a_i} r \pmod{c}$, $$ k \in \bigcup_{a_i \in (\mathbb{Z}/c\mathbb{Z})^*} {T_i} \implies ck+r \in [r]^+_c \setminus \mathbb{P} : r \in (\mathbb{Z}/c\mathbb{Z})^*$$

Determining the Translation Scalars, $b_i$, of the Compound Arithmetic Progressions, $T_i$

This is the final unknown coordinate in $\{a_i, b_i, c, d_i\} \in \mathbb{Z}^4$. $c$ is the principal modulus of each compound arithmetic progression, since in the above derivation $d_i$ varied with $a_i$ as $c$ was held constant.

From the matrix form of a Compound Arithmetic Progression, we have that:

$$ -det( M(T)) = c(n-b) + ad = (cy+a)(cx+d) $$

is implied by:

$$n = cxy+ax+dy+b$$

To solve for $b$ we use the test point $n_0 = c + a + d$ given by letting both $x,y \in {1}$ and $b = 0$. Then we have $n$ as a function of the ordered pair $(x,y)$.

In the example, we had two direct products. For $\{[1]^+\otimes[-2]^+\}_{\pmod{5}}$:

$$(c+a)(c+d) = (6)(3) = 18$$

Subtracting $ad = -2 \equiv 3\pmod{5}$, we observe that $n-b = 4$. So if we want to look at the structure of the composite numbers in this residue class, we use $b=0$, so that the point $n = 4$ corresponds to the determinant form for $18$, and since $18$ was the infimum of the direct product $[1]^+_5 \otimes [-2]^+_5$, then through isomorphism, $n = 4$ should correspond to the infimum of the compound arithmetic progression, which is observed when $b = 0$.

Therefore the compound arithmetic progression, $$M^{-1}\begin{pmatrix} -1 & n \\ 5 & -2 \end{pmatrix} = M^{-1}\begin{pmatrix} 2 & n \\ 5 & 1 \end{pmatrix}$$ is contained by the composite topology of $3\pmod{5}$.

And for $\{[-1]^+ \otimes [-3]^+ \}_{\pmod{5}}$, observe that $x,y \in {1}$ implies

$$ (c+a)(c+d) = (4)(2) = 8 $$

and subtracting $ad = (-1)(-3) = 3$ we obtain that if $b = 0$, the infimum is $n = 1$ for the compound arithmetic progression, and then

$$M^{-1}\begin{pmatrix} 1 & n \\ 5 & -3 \end{pmatrix} = M^{-1}\begin{pmatrix} 3 & n \\ 5 & -1 \end{pmatrix}$$

is contained by the composite topology of $3\pmod{5}$.

So if you wanted to look at the gaps between the primes in an arithmetic progression, you could set up the composite topology, where the composite topology of the residue class ${3 \pmod{5}}$ is:

$$\bigcup\{ [1]^+ \otimes [-2]^+, [-1]^+ \otimes [-3]^+ \}_{\pmod{5}} \cong $$ $$ M^{-1}\begin{pmatrix} 1 & n \\ 5 & 2 \end{pmatrix} \cup M^{-1}\begin{pmatrix} 3 & n \\ 5 & -1 \end{pmatrix} = $$ $$ \bigcup_z\{ [z+1]^+_{(5z-2)}\} \cup \bigcup_z\{ [z-1]^+_{(5z-3)}\}$$

We have in the above the set of numbers $n$ for which $E(n) := 5n+3$ is composite, so that it follows:

$$ K:= \mathbb{Z}^+ \setminus \bigcup\{ M^{-1}\begin{pmatrix}1 & n \\ 5 & 2 \end{pmatrix} ,M^{-1}\begin{pmatrix} 3 & n \\ 5 & -1 \end{pmatrix} \}$$

where the isomorphic compound arithmetic progressions are implied by the direct product and represent the set of $k \in K$ for which $E(k)$, the linear form $5k + 3$ in $(\mathbb{Z^+})^{(\mathbb{Z^+})}$ has a range of $\{3 \pmod{5}\} \cap \mathbb{P}$.

And it was possible to find a pattern of inclusion, exclusion or neglect in this set by defining the sieve in terms of compound arithmetic progressions for any specific k-tuple that fits into a residue class whose modulus is shared with the principal modulus of the compound arithmetic progression.

Supposing we looked for a gap of 10; use $\{p, p+10\} \subset \mathbb{P} \cap \{3\pmod{5}\} $ To illustrate:
$$\{3,13\},\{13,23\},\{43,53\}$... $$ $$ K := {0, 1, 4, ...} \cap \mathbb{Z}^+ $$

The first thing we observe is $\{p,p+10\} \rightarrow_{E^{-1}} \{k,k+2\}$. If both $k$, and $k+2$ are in $K$, then $\{E(k), E(k)+10\} \subset \mathbb{P} \cap \{ 3 \pmod 5\}$. Adjusting the translation scalar allows the sieve mobility and we arrive at the representation below:

$$ n' \in K \oplus 2 \implies n' = n+2 $$ by the definition of $\oplus$, which indicates

$$ K \oplus 2 := \mathbb{Z}^+ \setminus \bigcup\{ M^{-1}\begin{pmatrix}1 & n+2 \\ 5 & 2 \end{pmatrix} ,M^{-1}\begin{pmatrix} 3 & n+2 \\ 5 & -1 \end{pmatrix} \}$$

and with a trivial application of De Morgan's Laws

$$ K \cap \{ K \oplus 2 \} = $$ $$ \mathbb{Z}^+ \setminus \bigcup\{ M^{-1}\begin{pmatrix}1 & n \\ 5 & 2 \end{pmatrix}, M^{-1}\begin{pmatrix} 3 & n \\ 5 & -1 \end{pmatrix}, M^{-1}\begin{pmatrix}1 & n+2 \\ 5 & 2 \end{pmatrix}, M^{-1}\begin{pmatrix} 3 & n+2 \\ 5 & -1 \end{pmatrix} \} $$

That represents the set of numbers for which $\{E(k), E(k)+10\} \subset \mathbb{P}$,which has some set-theoretical properties that can be studied and proven, but to get the estimate for the asymptotic of that set, we have to be able to determine the general estimate for the asymptotic of any compound arithmetic progression and the elements of the $\delta$-ring the class forms under intersection.

Estimating a compound arithmetic progression depends on using $\pi_k(N)$, the counting function for $k$-almost primes less than $N$. Estimating an intersection composed of compound arithmetic progressions requires the use of the product of the determinants and similarly depends on an accurate estimate for $\pi_k(N)$ or usage of the actual value.

Because we know that through projection onto an arithmetic progression through the linear form $E(n)$, for any element $n$ of a compound arithmetic progression, $E(n)$ has at least two prime factors $p_a \equiv a \pmod{c}$ and $p_d \equiv d \pmod{c}$.

If we make an estimate of how many elements are in a direct product isomorphic to a compound arithmetic progression contained as an element of a composite topology as defined above, then an argument can be made for the following (unverified) expression:

$$ \text{card}\{T \cap (0,n]\} \sim \sum_{k=2}^{\infty} {\frac{\pi_k(cn)}{\varphi(c)^k}\sum_{j=0}^{k}{\tau_{j}(a)\tau_{k-j}(d)}} $$

Where $\tau_k$ is defined as the $k$-fold divisor function for the multiplicative group $\pmod{c}$, and $\pi_k$ is defined as the counting function for the $k$-almost primes. (see: Asymptotic Density of k-almost Primes)

Still, to be able to do any serious mathematical acrobatics with compound arithmetic progressions and composite topologies in arithmetic progressions, then the intersections must be studied as well. Though, this is less difficult than one might imagine.

If $n \in \bigcap T_i$, where the $T_i$ are compound arithmetic progressions (not necessarily in a composite topology) sharing a principal modulus and having $a_i, d_i \in (\mathbb{Z}/c\mathbb{z})^*$, then we have $n \in T_i: \forall i \in I$, the bounded, closed interval of positive integers, with infimum $1$. $T_i \cong [a_i]^+_c \otimes [d_i]^+_c$ implies that for intersections, the product of the determinants is an element of the direct product $$\prod_i\bigg(-det(M(T_i))\bigg) \in \bigotimes_{i} \bigg( [a_i]^+_c \otimes [d_i]^+_c\bigg)$$

and as a result we have the following:

$$ \text{card}\{\bigcap{T_i} \cap (0,n]\} \sim \sum_{k=2\sup I}^{\infty} {\frac{\pi_k(cn)}{\varphi(c)^k}\sum_{\sum_i{j_{2i-1} + j_{2i}}=k}{\prod_i \tau_{j_{2i-1}}(a_i)\tau_{j_{2i}}(d_i)}} $$

when $j$ is an array of positive integers corresponding to the arithmetic progressions in the direct products, isomorphic to each $T_i$. The product of the determinants is not, in general, an order preserving map, thus no claim is made about isomorphism with the intersections of compound arithmetic progressions.

  • $\begingroup$ Do you realize what you wrote doesn't mean anything ? The prime number theorem in arithmetic progressions is a consequence of $\sum_{n \equiv 1 \bmod q} \Lambda(n) n^{-s}$ having the same properties as $\frac{\zeta'(s)}{\zeta(s)}$ $\endgroup$
    – reuns
    Aug 8, 2017 at 16:00
  • $\begingroup$ Well, I do believe OP was asking about something much deeper than just arithmetic progressions and given some revision, I can write about a more exact answer based on the structure of the composite numbers, using less popular methods. $\endgroup$
    – user56983
    Aug 10, 2017 at 15:49
  • 3
    $\begingroup$ The OP probably didn't know where the results about prime gaps come from, and asked about its generalization in arithmetic progressions. The answer is that the results about distributions of primes and prime gaps come from L-functions (zero-free regions and distributions of the non-trivial zeros), and they generalize naturally to arithmetic progressions thanks to Dirichlet characters. $\endgroup$
    – reuns
    Aug 10, 2017 at 16:15
  • $\begingroup$ That is a very commonplace approach. $\endgroup$
    – user56983
    Aug 10, 2017 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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