## Is a “non-analytic” proof of Dirichlet’s theorem on primes known or possible?

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.

-
I'm puzzled by 'finitary analytic machinery' and how you quantify 'amount of analysis.' Do you have a specific idea in mind or are you looking for suggestions? – François G. Dorais Mar 1 2010 at 2:27
On the other hand, you could ask for a purely algebraic proof of the Cebotarev density theorem, e.g. a proof which does not (in some sense) distinguish between the number field and function field cases. As with so many things in mathematics, Bjorn Poonen would be a good person to ask about this. – Pete L. Clark Mar 1 2010 at 3:21
Selberg's proof just rubs me the wrong way; unlike the Galois-theoretic proof of FTA I linked to above, I do not get a good sense of where the "essence" of the analytic argument lies. I guess a good way to quantify "essence" is, as you say, to ask for a uniform proof of the Chebotarev density theorem. – Qiaochu Yuan Mar 1 2010 at 3:34
Can you give us an example illustrating your question 1? To fix ideas, let's consider the progression 2 mod 5, for which the Euclid-style proofs do not exist. What is a sequence a_n which solves your question 1 in this example? Since you're asking whether one can always find an efficiently constructed sequence, I'd first like to see you produce just one that is not in the spirit of the Euclid proofs. – KConrad Mar 1 2010 at 3:55
Using only Selberg's symmetry formula and elementary divisor sum manipulations, one can show that the primes mod q are either equidistributed in the coprime classes, or equidistributed in half of coprime residues corresponding to where some quadratic character $\chi$ equals 1. This is the best one can do without importing somewhere a proof that $L(1,\chi) \neq 0$, which seems to require some nontrivial machinery at some point. This is discussed in this paper of Granville: ams.org/mathscinet-getitem?mr=1220462 – Terry Tao Nov 28 2011 at 4:59

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.

-

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 There he shows that a commonly believed conjecture implies a generalization of Murty's result to a broader type of Euclidean proof.

-
 @Noah: Dear Noah, the link which you mention doesn't seem to work. Could you please rectify the link – Chandrasekhar May 6 at 11:44 @Chandrasekhar: Fixed. – Noah Snyder May 8 at 15:35