Richard Williamson
Observations on prime divisors of odd integers in a range

Contents

Introduction

This page collects together some unpublished little observations in elementary number theory. Throughout, we denote by p ip_{i} the ii-th odd prime.

A hypothetical proof of the Goldbach conjecture

We begin with the following.

Proposition

Let n6n \geq 6 be an even integer, and let k1k \geq 1 be an integer such that p kn3p_{k} \leq n - 3. Let HH be a proposition, dependent on kk and on a subset SS with at least kk elements of the set of odd integers mm such that 3mn33 \leq m \leq n-3, with the following properties.

  1. We have that HH holds for all possible SS when k=1k=1.

  2. If HH holds for SS with respect to kk, then there is an sSs \in S and a prime pp such that psp \mid s and pp kp \geq p_{k}.

  3. If HH holds for SS with respect to kk, then there do not exist distinct elements ss and ss' of SS such that p k1sp_{k-1} \mid s and p k1sp_{k-1} \mid s'.

  4. Suppose that HH holds for SS with respect to kk, and that there is a subset SS' of SS such that HH holds with respect to k1k-1 for SS'. Let ss' be the element of SS' which we obtain from 1. Then HH holds for S{s}S \setminus \{ s' \}.

Then there is an sSs \in S and a prime pp such that psp \mid s and pp kp \geq p_{k}.

Proof

We proceed by induction on kk. That the theorem holds when k=1k=1 follows immediately from 1. and 2.

Suppose that k>1k \gt 1. By induction with respect to SS' and k1k-1, and by 2., there is an sSs' \in S' and a prime pp' such that psp' \mid s' and pp k1p' \geq p_{k-1}.

By 4., we have that HH holds for S=S{s}S'' = S \setminus \{ s' \} with respect to k1k-1. By induction and 2., there is an sSs'' \in S'' and a prime pp'' such that psp'' \mid s'' and pp k1p'' \geq p_{k-1}.

By 3., it is impossible that p=p=p k1p' = p'' = p_{k-1}. Thus either pp k1p' \geq p_{k-1} or pp k1p'' \geq p_{k-1}, and the proposition holds.

We deduce from Proposition that the following holds.

Corollary

Let n6n \geq 6 be an even integer. Let k1k \geq 1 be an integer such that p kn3p_{k} \leq n - 3. Suppose that there is a hypothesis HH which satisfies the conditions of Proposition for S={np i1ik}S = \{ n - p_{i} \mid 1 \leq i \leq k \} with respect to kk. Then either there is an integer 1ik1 \leq i \leq k such that np in - p_{i} is prime, or there is a prime pp such that p k<pn3p_{k} \lt p \leq n - 3.

Proof

By Proposition , there is an sSs \in S and a prime pp such that psp \mid s and pp kp \geq p_{k}.

If ss is prime, then the corollary holds. Otherwise, we have that s3p k>2p ks \geq 3p_{k} \gt 2p_{k}. By Bertrand's postulate, we have that 2p k>p k+12p_{k} \gt p_{k+1}. Thus we have that p k+1<sn3p_{k+1} \lt s \leq n - 3. Since p k+1>p kp_{k + 1} \gt p_{k}, we conclude that the corollary holds, taking pp to be p k+1p_{k+1}.

From Corollary we obtain the following, which is the (strong) Goldbach conjecture.

Theorem

Let n6n \geq 6 be an even integer. Let m1m \geq 1 be the largest integer such that p mn3p_{m} \leq n - 3. Suppose that there is a hypothesis HH which, for all 1km1 \leq k \leq m, satisfies the conditions of Proposition for S={np i1ik}S = \{ n - p_{i} \mid 1 \leq i \leq k \}. Then there is a prime pn3p \leq n - 3 such that npn - p is prime.

Proof

Since there are only finitely many primes less than or equal to n3n-3, the theorem follows immediately from repeatedly applying Corollary .

We now make a few observations with regard to finding a hypothesis HH with the necessary properties.

Remark

The condition that n6n \geq 6 is not important. Since the Goldbach conjecture is readily checked for small nn, one can impose a higher lower bound on nn as needed.

Remark

Let HH be the hypothesis that max(S)min(S)p kmax(S) - min(S) \leq p_{k}. Corollary and Theorem then hold.

Moreover, the properties 1., 2., and 3. which are required of HH all hold. In the case of 1. and 2., this is clear.

In the case of 3., a proof of this is as follows. If p k1sp_{k-1} \mid s and p k1sp_{k-1} \mid s', then since sss \neq s', the difference between ss and ss' is at least 2p k12p_{k-1}. By Bertrand's postulate, we have that 2p k1>p k2p_{k-1} \gt p_{k}. But since max(S)min(S)p kmax(S) - min(S) \leq p_{k} and both ss and ss' belong to SS, the difference between ss and ss' is in fact less than or equal to p kp_{k}, and we have a contradiction.

However, there does not seem to be an obvious way to find a subset SS' of SS such that 4. holds for this choice of HH. For certain SS, including those used in Corollary and Theorem , one could take SS' to be S{min(S)}S \setminus \{ min(S) \}. Then HH is satisfied for SS', and thus one obtains an sSs' \in S' and a prime pp such that psp \mid s' and pp k1p \geq p_{k-1}. But then in general S{s}S \setminus \{ s' \} will not satisfy HH.

Some observations on the primes

As a preliminary to the following section, we make a few simple (and unconditional) observations about the primes.

Given an integer k1k \geq 1, let O kO_{k} be the set of odd integers which are greater than or equal to 33 and less than or equal to p kp_{k}. We denote the number of elements of O kO_{k} by |O k|\left| O_{k} \right|.

Lemma

Let k1k \geq 1 be an integer such that |O k|>2k+2\left| O_{k} \right| \gt 2k+2 elements. Then |O k|>2k\left| O_{k'} \right| \gt 2k' elements for any kkk' \geq k.

Proof

By assumption, we have that the lemma holds when k=kk'= k.

Suppose now that for some kkk' \geq k, we have that |O(k)|>2k+2\left| O(k') \right| \gt 2k' + 2, and that |O(k)|>2k\left| O(k'') \right| \gt 2k'' for all kkkk \leq k'' \leq k'.

If p k+1p k+2p_{k'+1} \neq p_{k'} + 2, then |O k+1||O k|\left| O_{k' + 1} \right| \geq \left| O_{k'} \right|.

Suppose that p k+1=p k+2p_{k'+1} = p_{k'} + 2. Then we must have that p k+4p_{k'} + 4 is divisible by 33. Suppose that it is also divisible by 55 and 77. Then p k+4p_{k'} + 4, p k+10p_{k'} + 10 (divisible by 33), p k+14p_{k'} + 14 (divisible by 55), p k+16p_{k'} + 16 (divisible by 33), and p k+18p_{k'} + 18 (divisible by 77) are all not prime. Hence |O k+5||O k|+10\left| O_{k' + 5} \right| \geq \left| O_{k'} \right| + 10 and, for all integers 1i41 \leq i \leq 4, we have that |O k+i||O k|+2i2\left| O_{k' + i} \right| \geq \left| O_{k'} \right| + 2i - 2.

Suppose instead that p k+4p_{k} + 4 is divisible by 33 and 55, but not by 77. Then p k+4p_{k'} + 4, p k+10p_{k'} + 10 (divisible by 33), p k+12p_{k'} + 12 (divisible by 77), and p k+14p_{k'} + 14 (divisible by 55) are all not prime. Hence |O k+4||O k|+8\left| O_{k' + 4} \right| \geq \left| O_{k'} \right| + 8 and, for all integers 1i31 \leq i \leq 3, we have that |O k+i||O k|+2i2\left| O_{k' + i} \right| \geq \left| O_{k'} \right| + 2i - 2.

Suppose instead now that p k+4p_{k} + 4 is divisible by 33, but not by 55. Then p k+4p_{k'} + 4, p k+8p_{k'} + 8 (divisible by 55), and p k+10p_{k'} + 10 (divisible by 33) are all not prime. Hence |O k+3||O k|+6\left| O_{k' + 3} \right| \geq \left| O_{k'} \right| + 6 and, for all integers 1i21 \leq i \leq 2, we have that |O k+i||O k|+2i1\left| O_{k' + i} \right| \geq \left| O_{k'} \right| + 2i - 1.

We have demonstrated that in all these cases, there is an l>kl \gt k' such that |O(l)|>2l+2\left| O(l) \right| \gt 2l + 2, and such that |O(l)|>2l\left| O(l') \right| \gt 2l' for all kllk' \leq l' \leq l. The lemma follows immediately by induction.

Proposition

Let k29k \geq 29 be an integer. Then |O(k)|>2k\left| O(k) \right| \gt 2k.

Proof

When k=29k=29, one can calculate that |O(k)|>2k\left| O(k) \right| \gt 2k. When k=30k=30, one can calculate that |O(k)|>2k+2\left| O(k) \right| \gt 2k + 2. The proposition follows immediately from this by Lemma .

Remark

One can check that |O(k)|2k\left| O(k) \right| \leq 2k for all integers 1k<291 \leq k \lt 29, so that Proposition is sharp.

Proposition

Let k2k \geq 2 be an integer. Then p 2k>2p kp_{2k} \gt 2p_{k}.

Proof

Legendre-sieve like argument, together with calculation of the small cases. TODO: write out fully.

A negative result

The following shows that it is not enough to ask that SS in Proposition be required to satisfy that max(S)min(S)p k3max(S) - min(S) \leq p_{k} -3 and that all elements of SS are composite, even though for small kk this condition is strong enough.

Remark

Let k=17k = 17, so that p k=61p_{k} = 61. Let

S={63,65,69,75,77,81,85,87,91,93,95,99,105,111,115,117,119}. S = \{ 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119 \}.

Then SS has 17 elements, and all of the integers in SS are composite, but none has a prime factor greater than or equal to p 17p_{17}, indeed none has a prime factor greater than or equal to p 10=37p_{10} = 37.

A catalogue of small cases

We shall attempt to prove Theorem when kk is small, proceeding case by case. There is no obvious way to use a computer to help, so we proceed by hand.

Proposition

Let SS be any set with exactly one element ss which is an odd integer. Then either ss is prime, or ss is composite and there is a prime pp such that psp \mid s and pp 1=3p \geq p_{1} = 3.

Proof

Clear, since every odd integer has at least one odd prime divisor.

Proposition

Let SS be any set with exactly two elements s 1s_{1} and s 2s_{2} which are consecutive odd integers. Then either one of the two elements ss of SS is prime, or one of the two elements ss of SS is composite and there is a prime pp such that psp \mid s and pp 2=5p \geq p_{2} = 5.

Proof

Suppose that neither s 1s_{1} nor s 2s_{2} is prime. If the proposition does not hold, then both s 1s_{1} and s 2s_{2} are powers of 33. But then the difference between s 1s_{1} and s 2s_{2} is at least 66, which contradicts the fact that s 1s_{1} and s 2s_{2} are consecutive. We conclude that the proposition holds.

Proposition

Let SS be any set with exactly three elements s 1<s 2<s 3s_{1} \lt s_{2} \lt s_{3}, and suppose that max(S)min(S)p 3p 1=73=4max(S) - min(S) \leq p_{3} - p_{1} = 7 - 3 = 4. Then either one of the elements of SS is prime, or one of the elements ss of SS is composite and there is a prime pp such that psp \mid s and pp 3=7p \geq p_{3} = 7.

Proof

The hypothesis that max(S)min(S)4max(S) - min(S) \leq 4 implies that s 1s_{1}, s 2s_{2}, and s 3s_{3} are consecutive odd integers. By Proposition , at least one of s 1s_{1} and s 2s_{2}, let us denote it by ss, is divisible by a prime pp such that pp 2p \geq p_{2}.

We cannot have that both of the elements of S{s}S \setminus \{ s \} are powers of 33, for then the difference between them is at least 66, which contradicts the fact that max(S)min(S)4max(S) - min(S) \leq 4. Hence at least one of the elements, let us denote it by ss', of S{s}S \setminus \{ s \} is divisible by a prime pp 2p' \geq p_{2}.

We cannot have that p=p=p 2p = p' = p_{2}, for then the difference between ss and ss' is at least 1010, which contradicts the fact that max(S)min(S)4max(S) - min(S) \leq 4. We conclude that either pp 3p \geq p_{3} or pp 3p' \geq p_{3}, as required.

Proposition

Let SS be any set with exactly four elements s 1<<s 4s_{1} \lt \cdots \lt s_{4} and with a subset S 3S_{3} which satisfies the hypotheses of Proposition . Suppose that max(S)min(S)p 4p 1=113=8max(S) - min(S) \leq p_{4} - p_{1} = 11 - 3 = 8. Then either one of the elements of SS is prime, or one of the elements ss of SS is composite and there is a prime pp such that psp \mid s and pp 4=11p \geq p_{4} = 11.

Proof

By Proposition , there is an element ss' of S 3S_{3} which is either prime, in which case the proposition holds, or which is composite and for which there is a prime pp' such that psp' \mid s' and pp 3p' \geq p_{3}.

Since max(S)min(S)8max(S) - min(S) \leq 8, at most one of the three elements of S=S{s}S' = S \setminus \{ s' \} is divisible by 55. If two of the elements of SS' are powers of 33, these powers must be 3 13^{1} and 3 23^{2}, for otherwise the difference between them is at least 1818. Thus, if there is no prime pp 3p'' \geq p_{3} such that pp'' divides one of the elements of SS', the only possibility is that S={3,5,9}S' = \{ 3, 5, 9 \}, in which case the proposition holds (since 33 is prime, or alternatively since 55 is prime).

Otherwise, there is a prime pp 3p'' \geq p_{3} such that pp'' divides one of the elements, say ss'', of SS'. We cannot have that p=p=p 3p' = p'' = p_{3}, for then the difference between ss' and ss'' is at least 1414, which contradicts the fact that max(S)min(S)8max(S) - min(S) \leq 8. We conclude that either pp 4p' \geq p_{4} or pp 4p'' \geq p_{4}, as required.

Proposition

Let SS be any set with exactly five elements s 1<<s 5s_{1} \lt \cdots \lt s_{5}, and with a subset S 4S_{4} which satisfies the hypotheses of Proposition . Suppose that max(S)min(S)p 5p 1=133=10max(S) - min(S) \leq p_{5} - p_{1} = 13 - 3 = 10. Then either one of the elements of SS is prime, or one of the elements ss of SS is composite and there is a prime pp such that psp \mid s and pp 5=13p \geq p_{5} = 13.

Proof

By Proposition , there is an element ss' of S 4S_{4} which is either prime, in which case the proposition holds, or which is composite and for which there is a prime pp' such that psp' \mid s' and pp 4p' \geq p_{4}.

Since max(S)min(S)10max(S) - min(S) \leq 10, at most one of the four elements of S=S{s}S' = S \setminus \{ s' \} is divisible by 77, at most two are divisible by 55, and at most two are divisible by 33.

If at most one of the elements of SS' is divisible by 55, then at least two of the elements of SS' are powers of 33. We cannot have that the two powers of 33 are both of the form 3 a3^{a} for a2a \geq 2, for then the difference between them is at least 1818, which contradicts the fact that max(S)min(S)10max(S) - min(S) \leq 10. Hence the two powers are 3 13^{1} and 3 23^{2}. But then S={3,5,7,9}S' = \{ 3, 5, 7, 9 \}, in which case the proposition holds (since, for instance, 33 is prime).

Suppose now that two of the elements of SS' are divisible by 55. If ss' is divisible by either 33 or 77, then the two elements of SS' which are divisible by 55 are both powers of 55. But then the difference between the two powers of 55 is at least 2020, which contradicts the fact that max(S)min(S)10max(S) - min(S) \leq 10.

Hence ss' must be a power of 1111. Any power of 1111 is congruent to 11 modulo 55. Since max(S)min(S)10max(S) - min(S) \leq 10, the only possibility if two elements of SS' are divisible by 55 is that both min(S)min(S) and max(S)max(S) are divisible by 55. Then since ss' is congruent to 11 modulo 55, we must have that s=min(S)+6s' = min(S) + 6.

If only one element of SS' is divisible by 33, then the two elements of SS' which are divisible of 55 are powers of 55. As we have already seen, this cannot be the case. We deduce that two elements of SS' are divisible by 33.

The only possibility, since min(S)+6min(S) + 6 is a power of 1111, and since min(S)min(S) and max(S)max(S) are not both powers of 55 and thus 33 must divide either min(S)min(S) or max(S)max(S), is then that max(S)max(S) is divisible both by 33 and by 55, and that min(S)+4min(S) + 4 is a power of 33. But if ss' is not prime, so that min(S)+6=11 amin(S) + 6 = 11^{a} for some a2a \geq 2, then min(S)+6min(S) + 6 is congruent to 11 modulo 33. But since min(S)+4min(S) + 4 is congruent to 00 modulo 33, this is impossible.

We conclude that if no element of SS is prime, then either ss' or one of the elements of SS' is divisible by a prime pp such that p>11p \gt 11, as required.

Last revised on October 22, 2018 at 14:25:40. See the history of this page for a list of all contributions to it.