Is a "non-analytic" proof of Dirichlet's theorem on primes known or possible?

Question

It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} \}$ must lie in certain arithmetic progressions, with a finite number of exceptions. This is because any nonconstant polynomial must have infinitely many distinct prime divisors, which one can prove in a manner imitating Euclid's proof of the infinitude of the primes. For example, taking $p(x) = \Phi_n(x)$, we can prove Dirichlet's theorem for primes congruent to $1 \bmod n$. It is known (see, for example, this paper of K. Conrad) that this is possible precisely for the primes congruent to $a \bmod n$ where $a^2 \equiv 1 \bmod n$.

However, the result about polynomials having infinitely many prime divisors has the following generalization: any sequence $a_n$ of integers which is eventually monotonically increasing and which grows slower than $O(2^{\sqrt[k]{n}})$ for every positive integer $k$ has infinitely many distinct prime divisors. In particular, any sequence of polynomial growth (not necessarily a polynomial itself) has this property.

Question 1: Given an arithmetic progression $a \bmod n, (a, n) = 1$ such that $a^2 \not \equiv 1 \bmod n$, is it ever still possible to efficiently construct a monotonically increasing sequence of positive integers satisfying the above growth condition such that, with finitely many exceptions, the prime divisors of any element of the sequence are congruent to $a \bmod n$? ("Efficiently" rules out answers like "the positive integers divisible by primes congruent to $a \bmod n$," since I do not think it is possible to write down this sequence efficiently. On the other hand, evaluating a polynomial is very efficient.) The idea is that such a sequence immediately gives a proof of Dirichlet's theorem for primes congruent to $a \bmod n$ generalizing the Euclid-style proofs.

Question 2: If the above is not possible, are there any known techniques for proving Dirichlet's theorem or at least some of the special cases not covered above without resorting to the usual analytic machinery? For example, Selberg published an "elementary" proof in 1949, but it relies on the "elementary" proof of the prime number theorem, which to me is "finitary analytic machinery." What is the absolute minimum amount of analysis necessary to produce a proof? (Edit: In response to a suggestion in the comments, one way to describe the kind of answer I'm looking for is that it would generalize to a proof of Chebotarev's density theorem that shows very clearly where the distinction between the number field and function field cases is; aside from some "essential" analytic argument there should be no difference between the two.)

This question is inspired at least in part by the following observation: Dirichlet's theorem is equivalent to the seemingly weaker statement that for every progression $a \bmod n, (a, n) = 1$ there exists at least one prime congruent to $a \bmod n$. The reason is that if there exists some such prime $a_1$, then letting $n_1$ be the smallest multiple of $n$ greater than $a_1$, there exists a prime congruent to $a_1 + n \bmod n_1$, and so forth.

Answer 1

The question whether there are infinitely many primes in some coprime residue class mod m is stronger than asking whether there are infinitely many primes with given inertia index in the field of mth roots of unity, which is a special case of Chebotarev's density. The possibility of elementary proofs of the latter was discussed, as you know, over here.

It seems that Dirichlet's technique is perfectly natural for this kind of questions. Before he started using Euler's ideas on zeta functions, he played around with Legendre's approach (Legendre had tried to prove the result in his 2nd edition of his Théorie des nombres since he had used special cases in his "proof" of the quadratic reciprocity law), but without success.

Another attempt at giving an "elementary" proof was made by Italo Zignago:

• J. Zignago, Intorno ad un teorema di aritmetica (Italian), Annali di Mat. 21 (1893), 47-55

His proof was, however, incorrect.

BTW, question 1 goes back to the correspondence of Euler and Goldbach; they tried (in vain) to find a sequence of numbers divisible only by primes of the form $4n+3$. Eventually, Euler convinced himself that quadratic forms $x^2 + my^2$ won't do.

Answer 2

For more on Murty's result that the usual elementary approach is doomed to failure look at Paul Pollack's paper Hypothesis H and an impossibility theorem of Ram Murty (Wayback Machine). There he shows that a commonly believed conjecture implies a generalization of Murty's result to a broader type of Euclidean proof.

Answer 3

I was struggling to find an elementary proof of Dirichlet's theorem using another interesting technique. I came finally to a proof from an entirely different direction but as I found out Erdos came first before many years. The proof is not well known (I never understood why no one mentions it!) and it uses Chebyshev type estimates. Here is the proof: http://kam.mff.cuni.cz/~klazar/ln_antcII.pdf (Wayback Machine) I hope this will be helpful!

We are looking for prime numbers of the form $a+nm$, $(a,m)=1,n=1,2,\dots$.

The general plan is: $n!$ divides the product of $n$ consecutive terms of the arithmetic progression $a+m,a+2m,\dots,a+nm$ with $(a,m)=1$ (if we disregard the factor of $n!$ which includes divisors of $m$)

For example, consider the progression $1+3m$:

$4\cdot7\cdot10\cdot13\cdot16\cdot19\cdot22$ is divided by $7!/3^2$ (The factor that we "disregard" is $3^2$)

It is easy to prove in analog with Legendre's Lemma on binomial coefficients, that the highest power of a prime $p$ which divides $\frac{(a+m)\cdot(a+2m)\cdots(a+nm)}{n!}$ does not exceed $a+nm$.

The problem is that such a prime $p$ could not be of the form that is wanted. For example turning back to $\frac{4\cdot7\cdot10\cdot13\cdot16\cdot19\cdot22}{7!/3^2}$ we find 11 as a divisor which is a prime of the form $2+3m$.

We wish to simplify the unwanted primes from the "big" fraction which Erdos calls $Pn(a,m)$. In order to do this we divide $Pn(a,m)$ with a fraction of the same kind but from another progression $a'+nm$ with $(a',m)=(a,m)=1$.

(The "other" progression for $1+3m$ is $2+3m$ since 1 and 2 are the only numbers coprime to 3 and less than 3).

But we find that in $Pn(a,m)$ every prime of the form $a'+km$ which is greater than $n$ exists exactly once, so (and here is the big idea) dividing $Pn(a,m)$ with $P(n/h)(a',m)$ ($h$ is the number with the property $a'h=a \pmod m$ ) every prime of the form $a'+km$ which is greater than $n$ cancels.

Continuing like this you can cancel every unuseful prime that exceeds $n$ and have only "small" unuseful primes whose product is significantly smaller than $Pn(a,m)$.

With this, you prove that primes of the form $a+nm$ have a product which tends to infinity and so they are infinite.

I hope this is helpful.

(note) We use $h$ because the smallest term of the progression $a+nm$ that is divided by a prime $p$ of the form $a'+km$ is the term $a+km=h\cdot p$.

Answer 4

I like the approach of looking for a sequence of integers with prime divisors that are guaranteed to be in a certain arithmetic progression. One can try taking the iterates of a polynomial, starting with an integer. For example use $x^2-2x+2$ starting with 3, and you get the sequence 3,5,17,.. and you can show that any prime divisor of the kth term is $\equiv 1 \mod 2^k$ (not what was requested but a good start). I have no idea how to generalize this to get any new example, like $2 \mod 5$, but I find it intriguing. One might also try to iterate using $x^2+c$ (or any rational function) and look at the prime factors of the numerator. The Galois theory of such iterates perhaps suggests one won't escape the limitations of the "Euclidean proofs"