Coprimes to all finite subsets of N contain infinite twin pairs

I am not certain whether this is a mathematically significant result, but it seems fascinating to me, and quite relevant to the twin prime conjecture when I happened to find a proof for it.

The rough idea is that if co-primes to 2 give us the odds, and co-primes to 2,3 give us the pattern 6n-1,6n+1 which is in some essence closer to the sequence of primes than the sequence of odds, then co-primes to 2,3,5 are an even better approximation to the sequence of primes, co-primes to 2,3,5,7 yet even better and so on. I use mathematical induction on these primes to show that coprimes to any such sequence of primes 2, 3, … , p contain infinite twin pairs. That is, there are infinite numbers n of the sort that both n and n+2 are coprimes to 2, 3, … , p. Then, I strengthen this result to show this applies to coprimes to any finite subset of N, rather than just the co-primes to the sequence 2, 3, … p.

If you think the idea is worthwhile, please take a read of the paper below, and let me know what you think. Writing feedback is welcome too :)

The paper

Latex pdf if reading it here is hard : https://drive.google.com/file/d/1B0FfxXiyoeZhPTznf0kERK07f2s0hIsV/view?usp=sharing

Abstract

This paper introduces a modified form of Eratosthenes' sieve, which can be used to reason about patterns in co-primes to arbitary sets of numbers. For demonstration, I present proof of a weaker form of the twin prime conjecture, which says that for all primes $p$, primes $2...p$ have infinite twin co-primes. In other words, the set of co-primes to the numbers $2...p$, contains infinite pairs of numbers which differ by $2$. The proof presented below can be modified in small ways to prove similar results about other kinds of patterns, such as primes at distance of $4$, $6$, $8$ and so on. First, the modifications to the sieve are introduced, and then a proof by mathematical induction is presented.

Introduction

I modify Eratosthenes' sieve in 2 ways, and then present a proof by induction of the statement in the abstract. First, I remove the upper bound from the sieve. That is, while Eratosthenes' sieve starts with the range $2 \ldots k$ for some $k$, the modified sieve starts with the set ${2,3,4,5,6 \ldots }$ with no maximum value. The sieving process remains the same. Sieving for multiples of $2$ from the starting set gives ${2,3,5,7,9\ldots}$ and further sieving for multiples of $3$ gives ${2,3,5,7,11,\ldots, 25, \ldots}$.

Secondly, I change the notation. Rather than using set notation as in the paragraph above, I use an infinite-length bit string. The $k^{\text{th}}$ bit in the bit string is $1$ if the number $k+1$ exists in the set and $0$ otherwise. Call this the indicator bit for the number $k+1$. Thus, the set ${2,3,4,5,6\ldots}$ becomes $111111\ldots$ in this notation, the set ${2,3,5,7,9,11 \ldots}$ becomes $1101010101\ldots$, and both can be written more compactly as $\overline{1}$ and $1\overline{10}$ respectively. Table 1 shows how the sieving process in the modified sieve looks like.

Finally, the proof relies on a way to find the next pattern from the table 1 given the previous. For brevity, I define the part of the string under the bar in a pattern $P$ as the \textit{bar} of $P$, and the part before the bar as the \textit{prefix} of $P$. The non zero bits in the prefix of $P$ are indicator bits of primes whose multiples have been removed from $P$'s set form. The indicator bits for these multiples must then be a $0$. To generate the next pattern from $P$, we shift the first non-zero bit from $P$'s bar to its prefix. This bit is the indicator bit of the next prime $p$ we want to sieve multiples of. We set every $p^\text{th}$ bit after this indicator bit to a $0$. Since these are the indicator bits for the multiples of p, this is equivalent to removing these multiples from the set representation of $P$. Shifting the indicator bit of $p$ from bar to prefix is done by identifying the position of the bit, expanding the pattern to expanded form, taking the part upto the identified bit to be the prefix, and finally taking the remaining string and adding a bar in it over the repeating chunk. For example, to shift 3 bits from bar to prefix in $X\overline{00101}$, write the pattern in the expanded form $\text{X001010010100101...}$, and taking $\text{X001}$ to be the prefix, introduce the bar in the remaining string $\text{0100101001...}$ by identifying the repeating pattern $\text{01001}$. This obtains $\text{X001 01001}$ Alternatively, it could be viewed as moving the first 3 bits $001$ outside the bar, and rotating the pattern inside, $00101$ counterclockwise by 3 bits to obtain $01001$, as if in a tape dispenser.

Now that we have shifted the $p^\text{th}$ bit to the prefix, giving us the string $P'$ we need to set every next $p^\text{th}$ bit in the bar of $P'$ to a 0. This is the same as taking a bitwise \& of bar of $P'$ with the string $\overline{111\ldots10}$ with p repeating bits, after which we obtain the next pattern to $P$ in the sieving process.

This is shown in diagram 1.

Repeating the patterns $\infty$ times is not necessary for this. If the bar of $P'$ has $l$ bits, repeating to get $pl$ bits in both the strings is sufficient. The bar of the resultant pattern will have $pl$ bits after this process. In fact, any lesser number of repeats will not work. In the start, for the pattern $\overline{1}$, $l=1$, and $p=2$. The next value of $p$ is $3$, and $l$ gets as its value the $\text{LCM}(l_\text{prev}, p_\text{prev})$, which is just $l_\text{prev} \cdot p_\text{prev}$. We keep going this way, and obtain the following general pattern.

\begin{equation}

l_n = l_{\text{n-1}} \cdot p_{\text{n-1}}, l_0 = 1

\end{equation}

\begin{equation}

p_n = \text{prime after } p_{\text{n-1}}, p_0 = 2

\end{equation}

Proof by induction

Base case : Sieve of 2, $1\overline{10}$ has infinite occurrences of `101'.

Induction hypothesis : Sieve of $p^\text{th}$ prime has $\infty$ occurrences of `101'.

Inductive step :

Say the next prime after $p$ is $k$. To get the next pattern after $P$, we need to set the bits indicating the multiples of $k$ in $P$ to $0$. Going by the procedure stated earlier, we rotate $P$ to get the bit at position $k$ outside the bar, obtaining $P'$.

Now, we generate a bit string $S=\overline{111\ldots10}$ of $k$ repeating bits, and we'll be taking the bitwise \& of S and bar of $P'$ to get the bar of the next string. To get S and bar of $P'$ to be the same length before taking bitwise \&, we repeat S as many times as the length of bar of $P'$, which is $2*3*5*...*p^\text{th} prime$ according to equations (1) and (2). Similarly, we repeat the bar of $P'$ as many times as the length of S, which is $k$. Whatever twins the bar of $P'$ already had are repeated $k$ times with it. I'll finish by showing that only one prime of its $k$ copies is destroyed in the process of taking bitwise \&, which means that only two repeats of twins can be destroyed.

Theorem : If a bit is removed once, its copy is not removed

Proof by contradiction. Say both the bit and its copy are removed, and these copies are at distance $al$ where $0<a<k$. If the bits were at positions $x$ and $y$, $x \equiv y \pmod k \Rightarrow (x-y) \pmod k = 0 \Rightarrow a*2*3*5*\ldots (p^\text{th}$ prime$) \pmod k=0$, which is impossible, since all multiplicands on the LHS are coprime to $k$.

By the theorem, of $k$ twin copies, only 2 can be destroyed. Thus, the sieve of $(p+1)^\text{th}$ prime has twins in its bar.

Conclusion

This concludes the proof by induction that Eratosthenes' sieve, when modified as described, can prove a weaker form of the twin prime conjecture. Further work could attempt to strengthen this result or connect it to the original conjecture. Certain stronger corollaries immediately follow with little difficulty, such as the stronger statement "coprimes to any set of numbers contain infinite pairs differing by 2". This follows simply from that sieving multiples of any set of numbers can be reduced to sieving the multiples of their prime factors, and that these prime factors can be well sorted. Further, this sorted set of prime numbers is but a subset of 2 ... p where p is the greatest prime in the sorted set, and coprimes to 2...p contain twins, so coprimes to any subset of these should contain twins too.

Coprimes to all finite subsets of N contain infinite twin pairs

Coprimes to all finite subsets of N contain infinite twin pairs

Topics

DOI