A Variant of the Euclid-Mullin Sequence Containing Every Prime

Andrew R. Booker^{1} Howard House University of Bristol Queens Avenue Bristol, BS8 1SN United Kingdom

                  andrew.booker@bristol.ac.uk

Abstract

We consider a generalization of Euclid’s proof of the infinitude of primes and show that it leads to variants of the Euclid-Mullin sequence that provably contain every prime number.

1 Introduction

Given a finite set {p_{1}, …, p_{k}} of prime numbers, let p_{k+1} be a prime factor of 1 + p_{1} ⋯ p_{k}. Then, as Euclid showed, p_{k+1} is necessarily distinct from p_{1}, …, p_{k}. Iterating this procedure, we thus obtain an infinite sequence of distinct primes. For instance, beginning with k = 0 (with the convention that the empty product is 1) and choosing p_{k+1} as small as possible at each step, one obtains the Euclid-Mullin sequence, \underline{A000945}. More generally, following Clark [3], we call any sequence resulting from this construction a Euclid sequence with seed {p_{1}, …, p_{k}}.

One of the central questions in this area was posed by Mullin [5] in 1963: Does the Euclid-Mullin sequence contain every prime number? Despite a compelling heuristic argument of Shanks [8] that the answer is yes, even the broader question of whether there is any Euclid sequence containing every prime number remains open. (On the other hand, there are Euclid sequences that provably do not contain every prime. For instance, starting from k = 0 and choosing p_{k+1} as large as possible at each step, one obtains the second Euclid-Mullin sequence, \underline{A000946}, which is known to omit infinitely many primes [1, 6].) Booker and Irvine [2] showed that, for any given seed {p_{1}, …, p_{k}}, the possible Euclid sequences have a natural directed graph structure. Although one can prove many interesting properties of the family of graphs obtained by varying the seed, proving much about any particular graph remains an elusive goal.

1The author was partially supported by EPSRC Grant EP/K034383/1.

In this note, following a suggestion of Wooley, we consider a generalization of Euclid’s construction, in the hope that it will be more amenable to proof. Precisely, if {p_{1}, …, p_{k}} is a set of prime numbers, then for any I ⊆ {1, …, k}, the number N_{I} = ∏_{i∈I} p_{i} + ∏_{i∈{1,...,k}\I} p_{i} is coprime to p_{1} ⋯ p_{k} and has at least one prime factor. Iteratively choosing a set I and a prime p_{k+1} | N_{I}, we obtain an infinite sequence p_{1}, p_{2}, … of distinct prime numbers, as in Euclid’s proof. (Note that Euclid’s construction is the special case in which I = ∅ at each step.)

We call a sequence resulting from this more general construction a generalized Euclid sequence with seed {p_{1}, …, p_{k}}. Our result is that the construction is provably general enough to obtain every prime.

Theorem 1. For any finite set P of prime numbers, there is a generalized Euclid sequence with seed P containing every prime.

One particular generalized Euclid sequence, \underline{A167604}, was defined by Chua, starting with k = 0 and choosing p_{k+1} as small as possible at each step. A natural question, analogous to Mullin’s, is whether Chua’s sequence itself contains every prime. This seems very likely, but difficult to prove, since there is an obstruction that prevents the terms from always appearing in numerical order. Precisely, if n = p_{1} ⋯ p_{k} is the product of the first k terms of Chua’s sequence, then the next term p_{k+1} is the smallest prime factor of ∏_{d|n}(d+n/d); thus,

d^{2} + n ≡ 0 (mod p_{k+1}) for some d, so that (\frac{−n}{p_{k+1}} ) = 1. (Alekseyev has conjectured that p_{k+1} is always the smallest prime satisfying this constraint; see \underline{A167604}.) Given the well-known difficulty of proving good bounds for the gaps between sign changes of a quadratic character, we cannot rule out the possibility that Chua’s sequence is very thin.

We conclude the introduction by mentioning another variant of Euclid’s construction, due to Pomerance [4, §1.1.3]: given a set of primes {p_{1}, …, p_{k}}, let p_{k+1} be a prime that is not one of p_{1}, …, p_{k} and divides a number of the form d + 1 for d | p_{1} ⋯ p_{k}. Then, starting from k = 0 and choosing p_{k+1} as small as possible at each step, one obtains a sequence containing every prime, and in fact p_{k} is the kth smallest prime for k ≥ 5. While our variant is arguably truer in spirit to Euclid’s proof (since it is guaranteed to produce only new primes at each step), Pomerance’s variant has the distinct advantage of exhibiting a specific sequence containing every prime.

2 Proof of Theorem 1

Given a prime number q, let S_{q} ⊆ (ℤ/qℤ)^{×} be the set of residue classes attained by the squarefree, (q − 1)-smooth, positive integers, i.e.,

S_{q} = {d + qℤ : d ∈ ℤ_{>0}, d | ∏_{p<q} p} .

One of the main ingredients in the proof of Theorem 1 is that S_{q} is large, so that if q is the smallest prime not yet attained in p_{1}, …, p_{k}, then there is a significant chance that q is a prime factor of d + n/d for some d | n = p_{1} ⋯ p_{k}. From computation for small q, it seems likely that S_{q} = (ℤ/qℤ)^{×} for all q ∉ {5, 7}. We are not aware of a proof of this, but it turns out that the following weaker approximation is sufficient for our purposes:

Lemma 2. For any prime q, #S_{q} > \frac{1}{2}(q − 1).

Proof. For squarefree positive integers d ≤ q − 1, the residue classes d + qℤ are distinct and contained in S_{q}. By [7], the number of such d is at least \frac{53}{88}(q − 1) > \frac{1}{2}(q − 1).

In addition, we need one further input from algebraic geometry:

Lemma 3. Let q be an odd prime number and a ∈ (ℤ/qℤ)^{×}.

(i) If q ≠ 5 or q = 5 and a ≠ 3 + 5ℤ then there exists x ∈ (ℤ/qℤ)^{×} such that (\frac{x+a/x}{q}) ≠ 1.

(ii) If q ∉ \{7, 13\} then there exists x ∈ (ℤ/qℤ)^{×} such that (\frac{x^{6}+a}{q}) ≠ 1.

Proof. We consider the sum

∑_{x∈(ℤ/qℤ)^{×}} (\frac{x + a/x}{q}) = ∑_{x∈(ℤ/qℤ)^{×}} (\frac{x(x^{2} + a)}{q}) .

For q ≥ 3, x(x^{2} + a) has no repeated zeros in ℤ/qℤ, so that

{(x, y) ∈ (ℤ/qℤ)^{2} : y^{2} = x(x^{2} + a)}

are the affine points of an elliptic curve. For any fixed x ∈ ℤ/qℤ, the number of y ∈ ℤ/qℤ such that y^{2} = x(x^{2} + a) is 1 + (\frac{x(x^{2}+a)}{q}). In addition, the curve has one point at infinity, so by the Hasse bound, we have

1 + ∑_{x∈ℤ/qℤ} (1 + (\frac{x(x^{2} + a)}{q})) ≤ q + 1 + 2\sqrt{q},

whence

∑_{x∈(ℤ/qℤ)^{×}} (\frac{x(x^{2} + a)}{q}) ≤ 2\sqrt{q}.

This last estimate is less than q−1 provided that q ≥ 7, and we check the claim for q ∈ {3, 5} directly.

Similarly, for q ≥ 5, x^{6} + a has no repeated zeros in ℤ/qℤ, so that

{(x, y) ∈ (ℤ/qℤ)^{2} : y^{2} = x^{6} + a}

are the affine points of a genus 2 curve. The curve has two points at infinity, so by the Weil bound, we have

2 + ∑_{x∈ℤ/qℤ} (1 + (\frac{x^{6} + a}{q})) ≤ q + 1 + 4\sqrt{q},

whence

∑_{x∈(ℤ/qℤ)^{×}} (\frac{x^{6} + a}{q}) ≤ 4\sqrt{q} − 1 − (\frac{a}{q}) ≤ 4\sqrt{q}.

This last estimate is less than q − 1 provided that q ≥ 19, and we check the claim for q ∈ {3, 5, 11, 17} directly.

Theorem 1 follows by induction from the following proposition.

Proposition 4. Let P be a finite set of prime numbers and q the smallest prime not contained in P. Then there is a generalized Euclid sequence with seed P that contains q.

Proof. Suppose that P = {p_{1}, …, p_{k}}, and put n = p_{1} ⋯ p_{k}. If q = 2 then n + 1 is even, so we may choose 2 as the next term, p_{k+1}. Hence we may assume that q is odd.

Put

S = {d + qℤ : d ∈ ℤ_{>0}, d | n} ⊆ (ℤ/qℤ)^{×},

and note that S ⊇ S_{q}. Suppose first that S = (ℤ/qℤ)^{×}. If (\frac{−n}{q}) = 1 then it follows that there is a d | n such that d + n/d ≡ 0 (mod q), so we can choose q as the next term. On the other hand, if (\frac{−n}{q}) = −1 then by Lemma 3(i) we may choose d | n such that (\frac{d+n/d}{q}) = −1, provided that q ≠ 5 or n ≢ 3 (mod 5). For this choice of d there must be a prime p | (d+n/d) such that (\frac{p}{q}) = −1. Choosing this p as the next term, we replace n by n′ = pn, so that

(\frac{−n′}{q} ) = 1, and we may then follow this by q, as above. For q = 5 and n ≡ 3 (mod 5) we choose d = 1; since n + 1 ≡ −1 (mod 5) there is a prime p | (n + 1) with p ≢ 1 (mod 5), and replacing n by pn gives a different residue with which we can carry out the proof above.

Now suppose that S ≠ (ℤ/qℤ)^{×}. We seek to enlarge S by continuing the sequence, i.e., we choose p = p_{k+1} from

T = {p : p prime and p | (d + n/d) for some d | n},

and replace P by P ∪ {p}, n by pn and S by S ∪ pS. We are free to repeat this procedure until either q ∈ T (in which case we may choose q as the next term) or S stabilizes, so that pS ⊆ S for every choice of p ∈ T. If that is the case then it is easy to see that for every s ∈ S, S contains the coset sG, where G ≤ (ℤ/qℤ)^{×} is the subgroup generated by {p + qℤ : p ∈ T }. Thus, S = ⋃_{s∈S} sG is a union of cosets; in particular, #G divides #S.

Next, let H be a subgroup of (ℤ/qℤ)^{×} of index at least 4. For any h ∈ H, the number of d ∈ (ℤ/qℤ)^{×} such that d + n/d = h is at most 2. Hence,

#\{d ∈ (ℤ/qℤ)^{×} : d + n/d ∈ H\} ≤ 2#H ≤ \frac{1}{2}(q − 1).

By Lemma 2, it follows that there exists d | n such that (d + n/d) + qℤ ∉ H. In turn this implies that p + qℤ ∉ H for some p ∈ T.

For any r | (q − 1), consider the subgroup

H_{r} = \{h ∈ (ℤ/qℤ)^{×} : h^{\frac{q−1}{r}} = 1\} = \{x^{r} : x ∈ (ℤ/qℤ)^{×}\},

which has index r in (ℤ/qℤ)^{×}. Let q − 1 = ∏_{i=1}^{m} r_{i}^{e_{i}} be the prime factorization of q − 1. For each r_{i} ≥ 5 we apply the above argument with

H = H_{r_{i}} = {h ∈ (ℤ/qℤ)^{×} : r_{i}^{e_{i}} does not divide the order of h}

to see that G has order divisible by r_{i}^{e_{i}}. For r_{i} ∈ {2, 3} the index of H_{r_{i}} is too small to apply the argument, but we may still apply it to H_{r_{i}^{2}} (when r_{i}^{2} | (q − 1)) to see that G has order divisible by r_{i}^{e_{i}−1}. Thus we find that the index of G in (ℤ/qℤ)^{×} divides 6.

If q ≢ 1 (mod 3) then G has index at most 2, so that \frac{1}{2}(q − 1) | #G | #S; by Lemma 2 it follows that S = (ℤ/qℤ)^{×}, as desired. If q ≡ 1 (mod 3) then we apply the above argument with H = H_{6} to see that there exists p ∈ T such that p^{\frac{q−1}{6}} ≢ 1 (mod q). Since p^{\frac{q−1}{6}} = p^{\frac{q−1}{2}} /p^{\frac{q−1}{3}} , it follows that at least one of H_{2} and H_{3} does not contain p + qℤ. If p + qℤ ∉ H_{3} then again G has index at most 2, and we conclude that S = (ℤ/qℤ)^{×} as above.

Hence, we may assume that p+qℤ ∉ H_{2}, so that G has index dividing 3. If S = (ℤ/qℤ)^{×} then we are finished, so we may assume that G = H_{3} and #S < q − 1. By Lemma 2, we must have #S > #G, and it follows that #S = 2#G = \frac{2}{3}(q − 1). Going through the argument above with H = H_{3}, since d + n/d = h has at most two solutions for fixed h and #S = 2#H_{3}, to avoid concluding that there exists p ∈ T such that p + qℤ ∉ H_{3}, the function d ↦ d + n/d must map S 2–1 onto H_{3}. By the quadratic formula, this means in particular that (\frac{h^{2}−4n}{q}) = 1 for every h ∈ H_{3}, and thus (\frac{x^{6}−4n}{q}) = 1 for every x ∈ (ℤ/qℤ)^{×}. However, that contradicts Lemma 3(ii) for q ∉ {7, 13}, and for q ∈ {7, 13} we verify directly that #S_{q} > \frac{2}{3}(q − 1). This concludes the proof.

3 Acknowledgments

I thank Trevor Wooley and Carl Pomerance for supportive comments.

References

[1] Andrew R. Booker, On Mullin’s second sequence of primes, Integers 12 (2012), 1167– 1177.

[2] Andrew R. Booker and Sean A. Irvine, The Euclid-Mullin graph, J. Number Theory 165 (2016), 30–57.

[3] Pete L. Clark, On Euclid’s proof of the infinitude of primes and generating primes,

   MathOverflow, http://mathoverflow.net/q/4977.

[4] Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, second edition, 2005.

[5] Albert A. Mullin, Recursive function theory, Bull. Amer. Math. Soc. 69 (1963), 737.

[6] Paul Pollack and Enrique Treviño, The primes that Euclid forgot, Amer. Math. Monthly 121 (2014), 433–437.

[7] Kenneth Rogers, The Schnirelmann density of the squarefree integers, Proc. Amer. Math. Soc. 15 (1964), 515–516.

[8] Daniel Shanks, Euclid’s primes, Bull. Inst. Combin. Appl. 1 (1991), 33–36.

2010 Mathematics Subject Classification: Primary 11A41; Secondary 11B83. Keywords: prime number, Euclid-Mullin sequence.

(Concerned with sequences \underline{A000945}, \underline{A000946}, and \underline{A167604}.)

Received May 26 2016; revised versions received June 16 2016; June 17 2016. Published in Journal of Integer Sequences, July 4 2016.

Return to Journal of Integer Sequences home page.