Contents

Introduction

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

A hypothetical proof of the Goldbach conjecture

We begin with the following.

Proposition

Let $n \geq 6$ be an even integer, and let $k \geq 1$ be an integer such that $p_{k} \leq n - 3$. Let $H$ be a proposition, dependent on $k$ and on a subset $S$ with at least $k$ elements of the set of odd integers $m$ such that $3 \leq m \leq n-3$, with the following properties.

1. We have that $H$ holds for all possible $S$ when $k=1$.

2. If $H$ holds for $S$ with respect to $k$, then there is an $s \in S$ and a prime $p$ such that $p \mid s$ and $p \geq p_{k}$.

3. If $H$ holds for $S$ with respect to $k$, then there do not exist distinct elements $s$ and $s'$ of $S$ such that $p_{k-1} \mid s$ and $p_{k-1} \mid s'$.

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

Then there is an $s \in S$ and a prime $p$ such that $p \mid s$ and $p \geq p_{k}$.

Proof

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

Suppose that $k \gt 1$. By induction with respect to $S'$ and $k-1$, and by 2., there is an $s' \in S'$ and a prime $p'$ such that $p' \mid s'$ and $p' \geq p_{k-1}$.

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

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

We deduce from Proposition that the following holds.

Corollary

Let $n \geq 6$ be an even integer. Let $k \geq 1$ be an integer such that $p_{k} \leq n - 3$. Suppose that there is a hypothesis $H$ which satisfies the conditions of Proposition for $S = \{ n - p_{i} \mid 1 \leq i \leq k \}$ with respect to $k$. Then either there is an integer $1 \leq i \leq k$ such that $n - p_{i}$ is prime, or there is a prime $p$ such that $p_{k} \lt p \leq n - 3$.

Proof

By Proposition , there is an $s \in S$ and a prime $p$ such that $p \mid s$ and $p \geq p_{k}$.

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

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

Theorem

Let $n \geq 6$ be an even integer. Let $m \geq 1$ be the largest integer such that $p_{m} \leq n - 3$. Suppose that there is a hypothesis $H$ which, for all $1 \leq k \leq m$, satisfies the conditions of Proposition for $S = \{ n - p_{i} \mid 1 \leq i \leq k \}$. Then there is a prime $p \leq n - 3$ such that $n - p$ is prime.

Proof

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

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

Remark

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

Remark

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

Moreover, the properties 1., 2., and 3. which are required of $H$ 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_{k-1} \mid s$ and $p_{k-1} \mid s'$, then since $s \neq s'$, the difference between $s$ and $s'$ is at least $2p_{k-1}$. By Bertrand's postulate, we have that $2p_{k-1} \gt p_{k}$. But since $max(S) - min(S) \leq p_{k}$ and both $s$ and $s'$ belong to $S$, the difference between $s$ and $s'$ is in fact less than or equal to $p_{k}$, and we have a contradiction.

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

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 $k \geq 1$, let $O_{k}$ be the set of odd integers which are greater than or equal to $3$ and less than or equal to $p_{k}$. We denote the number of elements of $O_{k}$ by $\left| O_{k} \right|$.

Lemma

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

Proof

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

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

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

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

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

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

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

Proposition

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

Proof

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

Remark

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

Proposition

Let $k \geq 2$ be an integer. Then $p_{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 $S$ in Proposition be required to satisfy that $max(S) - min(S) \leq p_{k} -3$ and that all elements of $S$ are composite, even though for small $k$ this condition is strong enough.

Remark

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

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

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

A catalogue of small cases

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

Proposition

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

Proof

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

Proposition

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

Proof

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

Proposition

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

Proof

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

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

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

Proposition

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

Proof

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

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

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

Proposition

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

Proof

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

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

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

Suppose now that two of the elements of $S'$ are divisible by $5$. If $s'$ is divisible by either $3$ or $7$, then the two elements of $S'$ which are divisible by $5$ are both powers of $5$. But then the difference between the two powers of $5$ is at least $20$, which contradicts the fact that $max(S) - min(S) \leq 10$.

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

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

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

We conclude that if no element of $S$ is prime, then either $s'$ or one of the elements of $S'$ is divisible by a prime $p$ such that $p \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.