YouI will try to convince you that no Euclidean proof can possibly show that there are looking for the notion ofinfinitely many primes which are divisions$2 \mod 5$. After giving some definitions, I will explain what I will actually show:
Let $G$ be a finite group. Let $g$ be an element of $G$, with order $n$. We define an equivalence relation on $G$ by $g \sim h$ if there exists $f \in G$ and an integer $k$ withthe $\mathrm{GCD}(k,n)=1$ such that(cyclic) subgroups generated by $f g^k f^{-1} = h$.$g$ and by (Exercise: this is an equivalence relation$h$ are conjugate.) The equivalence classes for this relation are called divisionsdivisions. NoteObserve that this is a coarsermap of groups always respects this equivalence relation than. A more precise (but not yet precise) claim is:
Consider any Euclidean proof that there are infinitely many primes in some subset $S$ of
$\mathbb{Z}/N^*$. Then the set $S$ contains a complete division.
Since $\mathbb{Z}/N^*$ is abelian, the conjugacy classespart of the definition of abelianness doesn't come directly into this theorem, but it will arise in the proof.
My answerSo, what is a Euclidean proof? Well, at some step in the proof, I must build a prime $p$ and say "$p$ has the property $P$, and therefore $p$ is in $S$." In every Euclidean proof I have seen, $P$ is one of two things: For
(1) There is a number $S \subseteq (\mathbb{Z}/N)^*$$M$ such that $M$ is not in some subgroup $G$ of $(\mathbb{Z}/N)^*$. So $M$ has a prime divisor which is not in $G$, and we can provechoose $p$ to be that prime factor. So an allowable step in a Euclidean-proof is showing that there are infinitely many primes not in some subgroup $G$ of $(\mathbb{Z}/N)^*$
(2) Some polynomial $f(X)$ factors in a particular way modulo $p$, by "Euclidean" meansand therefore $f$ lies in some class modulo $N$. (Generally, the observation is that $f$ has a root modulo $p$, but I'll allow more general things like $f$ has a quadratic factor" as well. For a polynomial $f$ of degree $n$, and a partition $\lambda$ of $n$, let $D(f, \lambda)$ be the set of primes such that the irreducible factors of $f$ have degrees $(\lambda_1 \lambda_2, \ldots, \lambda_r)$. And let $D(f, \lambda, N)$ be the image of $D(f, \lambda)$ modulo $N$. So an allowable step in an Euclidean-proof will be showing that there are infinitely many primes in some union of $p \in S$ if$D(f, \lambda, N)$'s.
So, what I will actually be proving is
Any subgroup $G$ of $(\mathbb{Z}/N)^*$, and any $D(f, n, \lambda)$ in $(\mathbb{Z}/N)^*$, is a
union of divisions.
So, suppose that $S$ is a set which does not contain any division, and only iflet $T$ be disjoint from $S$ contains, but contain an element representing every division class in $S$. If we have a divisonEuclidean proof, it will construct some prime $p$. We may know that $p$ is not in various subgroups of the abelian group $(\mathbb{Z}/N)^*$, or that $p$ is in some union of $D(f, \lambda, N)$'s. But that information can't distinguish whether $p$ is in $S$ or in $T$, so our proof can't show that $p$ is in $S$.
Of courseOK, sincemy last boxed claim is a precise statement. Let's prove it.
It is easy to see that a subgroup of $(\mathbb{Z}/N)^*$ is a union of divisions (since we are in an abelian group, the conjugationconjugacy part of the definition of division is irrelevant). I include it because I planThe complement of a subgroup is likewise such a union.
The interesting thing is $D(f, \lambda, N)$. Let $K$ be a Galois field where $f$ and $x^N-1$ both split. Let $G$ be the corresponding Galois group, so $G$ comes equipped with a map to tell$(\mathbb{Z}/N)^* \cong \mathrm{Gal}(\mathbb{Q}(\zeta_N)/\mathbb{Q})$.
Now, as you probably know, for $p$ a more general storyprime unramified in $K$, the factorization of $f$ modulo $p$ is determined by the Frobenius conjugacy class of $p$ in $G$. ForWhat you may or may not know is that it is actually determined by the division class of $(\mathbb{Z}/13)^*$$p$! (For example, $x^5-1$ has the divisionssame factorization modulo primes which are
$$\{1 \} \cup \{ 2,6,7,11 \} \cup \{ 3, 9 \} \cup \{ 4, 10 \} \cup \{ 5,8 \} \cup \{ 12 \}.$$ $2 \mod 5$ and primes which are $3 \mod 5$.) To see this, just look at the recipe for reading the factorization off from the Frobenius class. It may or may not help to prove the following lemma: If $g \sim h$, and $X$ is a set with a $G$ action, then there is an order preserving bijection between the $g$ and the $h$ orbits in $X$.
I will presentSo, the possible Frobenius classes in $G$ of primes in $D(f, \lambda)$ are unions of divisions (I am implicitly using the Cebotarov density theorem here). But then $D(f, \lambda, N)$ is just the projection to $(\mathbb{Z}/N)^*$ of the possible Frobenius classes in $G$ of primes in $D(f, \lambda)$. Since maps of groups take divisions to divisions, this shows that $D(f, \lambda, N)$ is a Euclidean proofunion of divisions.
Frobenius's density Theorem states that there are infinitely many primes with Frobenius in eachevery division. I will then show(And, more precisely, that certain kindstheir Dirichlet density is the size of arguments cannot distinguish two primes in the same division. I want to make divided by the point thatorder of $G$.) It is significantly easier than Cebatarov's, while presenting this proof forusing only the material from a general $(S, N)$ involves Galoisfirst course in algebraic number theory, presenting for and a particular $S$first course in analytic number theory.
Cebatarov's density theorem is the "union" of Frobenius's and $N$ does notDirichlet's theorems. Therefore,What I will run this argument both asam suggesting is that Euclidean methods, at best, can only get at their intersection.
I would explain it to a professional mathematician and asam not sure whether or not I would present it tothink Euclidean proofs can get that far. If you think they can, give me a PROMYS student who wanted to proveEuclidean proof that there wereare infinitely many primes congruent to $2$ orwhich are in $4$ modulo$\{ 3, 5 \}$ mod $7$.
For the professional: Let I can show infinitely many in $K = \mathbb{Q}(\zeta_7)$$\{ 3,5,6 \}$, theand infinitely many in $7$th cyclotomic field. So$\{ 2,3,4,5 \}$, but I can't get the Galois group of $K/\mathbb{Q}$ is $intersection.
