Twin Prime Conjecture: Proof Proposal
To those who are reading this, I would like to ask you to not act on the impulse of immediately dismissing this article as nonsensical due to its bold title and simple delivery, as I would like to challenge you to walk through the argument with me and try to understand it. For this, I would like to thank you in advance!
DISCLAIMER: Twin prime conjecture is an open problem in mathematics. This article is a proposal of proof.
Elaboration: https://kirill-novik.medium.com/the-infinitude-of-twin-primes-using-chatgpt-and-coq-e067b9e4c14e
A Few Words on Motivation
In recent times, as everybody was staying home due to lockdown and, as a result, were taking on many new hobbies and projects, I also picked an interesting project.
On YouTube, I stumbled upon a video about deceptively simple unsolved math problems, and I would probably forget about it shortly after I watched it if it weren’t for the problem called Twin-Prime Conjecture. The reason it caught my attention was simple, I have a twin myself, and, somehow, this fact contributed to my interest.
The conjecture asserts that there are infinitely many twin primes or pairs of primes that differ by 2.
I started playing casually with the problem at first, and then it really got to me. As I started thinking more and more, certain argumentation was taking shape that has gradually become more and more convincing to me. Up to the point where now, after I have gotten some feedback, I’m ready to present it here.
To give you some notion about my background, I have a degree in Computer Science and Molecular Biology and currently doing my masters in Computer Science. I have familiarity with mathematical analysis from both the University and from studying on my own.
Introduction
Prerequisite: Euclid’s Proof and Sieve of Eratosthenes
Number theory is a very complicated subject, except maybe for the very foundational aspects of it. As an example, Euclid’s Proof and Sieve of Eratosthenes are very straightforward arguments.
I have been wondering why there is no known Euclid’s proof using Sieve of Eratosthenes. I am still unable to find the reason for that, but as I was playing with primes, I did just that — I carried out proof like the following.
Definition 1 Sieve
Sieve is a function from a set A of some natural numbers onto the set B of all natural numbers excluding both 1 and the multiples of the numbers in set A.
Examples:
S({2}) = {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, … }
S({3}) = {2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, … }
S({2, 3}) = {2, 3, 5, 7, 11, 13, … }
For illustration purposes, here is an example of how a sieve can be written in Python:
def sieve(A, N): return list(filter( lambda n: all([n % a != 0 for a in A]), N[1:] ))
Definition 2: Sifting Process
The set of all prime numbers is what remains after we apply sieves consecutively according to the following rule.
First, we start with A = {2}, take the first element of S({2}) that is not in set A, which will be 3, and add it to set A, so it becomes {2,3}.
Then, we take the first element of S({2, 3}) that is not in the set A, which will be 5, and add it to set A, so it becomes {2, 3, 5}.
Let’s denote this process as sifting process function SP:
For illustration purposes, here is an example of sifting process written in Python:
def sifting_process(n, sieve, A = [2], num = 100): N = list(range(1,num)) next_A = A while n > 0 and len(N) > 1: N = sieve(next_A, N) next_A.append(N[0]) n -= 1return next_A
Euclid’s Proof
Now, to prove that there exist infinitely many primes using the definition of the sieve function I need to show that no matter how big n gets, the size (the cardinality of B) will remain infinite (ℵ_0), meaning that there are always infinite unsifted elements no matter how much sifting we do.
Step 1, SP(1), where A = {2} will give a set without the multiples of 2. Analytically, we can show that it must not be empty because it will contain 2+1=3 because it cannot be divided without remainder by 2, and also that, in fact, any natural number of form 2n+1, since natural numbers are closed under multiplication and addition, of which there is an infinite number, also cannot be divided without remainder.
SP(2)=S({2, 3}) will give a set that will contain 2*3+1, which cannot be divided without a remainder by 2 or 3, and there also will be infinitely many numbers of form 6n+1.
NOTE: Important to note, that 6n+1 are not guaranteed to be the only numbers that will remain, but they still serve as an analytical guarantee that there will be infinitely many numbers in the resulting set.
Now, let’s say that this process works up till SP(k)=S({2, 3, …, p_k}), where the next step SP(k+1) will not result in a set with infinitely many numbers.
This will still give us a set with infinite numbers because we obtained an infinite set from SP(k) and we can show that we are still guaranteed that there will remain infinitely many numbers of the form:
Therefore, we can conclude that there will always remain numbers, no matter how far in the sifting process we get.
As I was carrying out this proof, I noticed that not only n*p1*…*p_n+1 is guaranteed to be inside the resulting set, but also the n*p1*…*p_n — 1, which was very exciting, as it lead me to the next part.
Twin-Prime Conjecture Proof
The conjecture asserts that there are infinitely many twin primes, or pairs of primes that differ by 2.
There is an interesting observation, if you noticed that after sieving out all multiples of 2 and 3 with S({2, 3}), the numbers remaining in the resulting set will be of the form 2*3n±1 or 6n±1, which fit the description of the twin primes. However, many of those numbers will get removed as we sift further, so not all values of n will give us twin primes. However, it is very important to remember the result of the sieve S({2, 3}) = { 2, 3, 6n±1 }
To clarify, because we are looking at multiples of 2 and 3 we only need to consider ranges in multiples of 6 like so:
- Keep 6n+1:
(6n+1)/2and(6n+1)/3give a remainder - Remove 6n+2:
(6n+2)/2don’t give a remainder - Remove 6n+3:
(6n+3)/3don’t give a remainder - Remove 6n+4:
(6n+4)/2don’t give a remainder - Keep 6n+5:
(6n+5)/2and(6n+5)/3give remainder - Remove 6n+6:
(6n+6)/2don’t give a remainder
The same is true in the reverse direction. Note, that we don’t include 6n+5 as it can be rewritten as 6n + 6 – 1 = 6(n+1)-1.
Now, our task is to prove that as we are performing the sifting process, for each step of the process there will remain infinitely many results of the form:
Step 1, SP(2)=S({2, 3}) will give a set that will contain 2*3+1, which cannot be divided without a remainder by 2 or 3, and there will also be infinitely many numbers of the form 2*3n+1, but so is true of 2*3n–1, so there will be infinitely many numbers of the form 2*3n±1, which fit the form of twin primes.
SP(3)=S({2, 3, 5}) will give a set that will contain 2*3*5+1, which cannot be divided without a remainder by 2 or 3 or 5, and there will also be infinitely many numbers of the form 2*3*5n+1, but so is true of 2*3*5n–1, so there will be infinitely many numbers of the form 6*5n±1, which fit the form of twin primes.
Now, let’s say that this process works up till SP(k)=S({2, 3, …, p_k}), where the next step SP(k+1) will not result in a set with infinitely many numbers.
Will give us infinitely many numbers of the form:
These numbers, of which there are infinitely many, fit the form of twin primes.
Therefore, we can conclude that there will always remain numbers that fit the definition of the twin primes, no matter how far in the sifting process we get.
I argue that this shows that sifting process will always keep infinitely many twin primes thus proving the conjecture.
Further Clarifications
From experience, I see that people have difficulty understanding induction and sets with infinite elements.
What makes it difficult for some, is to understand that n*p1*p2*…*p_n±1 serve only as an analytical guarantee of the fact that these numbers won’t get sifted out and there will be infinitely many of them, however, they are not how we would compute the prime twins and some may get sifted out as the process carries on.
This dissonance between computation and analytics for some is the reason why it is hard to understand this argument. For example, in Euclid’s proof set A would accumulate all of the prime numbers as we carry out the process indefinitely, so it is very clear that the result will be set A containing the “actual” primes. Once the argument reaches twin primes, many get confused that twin primes don’t get accumulated in the set A in a form where it is easy to count them.
I would argue that this computation is not necessary at all in the proof, however, in the hope to make things clearer, I will go ahead and bridge this gap.
As I already mentioned the set of S({2, 3}) will give us { 2, 3, 6n±1 }, if we remove 2 and 3, it will be just { 6n±1 }.
Let us now define a function that will convert natural numbers like so:
What this allows us to do is to now make a new type of sieve that will take natural numbers, sieve them, and return numbers that will represent intervals that we can then transform using F.
The sieving function now is different, although it does exactly the same thing as S under the hood. It now takes each element in A and goes through every element in the natural numbers removing the multiples of 6n-1 and 6n+1, where n belongs to A.
Let’s call it Twin Sieve. It can be written in Python like so (FYI, it is very computationally inefficient in this form but easy to follow):
def twin_sieve(A, N): return list(filter( lambda n: all([ (6*n+1)%(6*a+1) != 0 and (6*n+1)%(6*a-1) != 0 and (6*n-1)%(6*a+1) != 0 and (6*n-1)%(6*a-1) != 0 for a in range(1, A[-1]+1) ]), N ))
The reason why we remove all multiples of all numbers up to the largest in A is such.
First interval contains 6–1=5, 6+1=7, or F(1)[0] and F(1)[1].
Twin sieve TS({1}) is guaranteed to have infinitely many elements because n*6*F(1)[0]*F(1)[1]±1 (note this can be rewritten in the form n*k*(product_of_consecutive_primes)±1, where k is a product of numbers that should be sieved via SP, but we keep them for convenience of the argument) cannot be divided by any prime number obtained so far. We take the next element that didn’t get sieved. In this case, it is 2.
Twin sieve TS({1, 2}) is guaranteed to have infinitely many elements because n*6*F(1)[0]*F(1)[1]*F(2)[0]*F(2)[1]±1 (note this can be rewritten in the form n*k*(product_of_consecutive_primes)±1, where k is a product of numbers that should be sieved via SP, but we keep them for convenience of the argument) cannot be divided by any prime number obtained so far. We take the next element that didn’t get sieved. In this case, it is 3.
Twin sieve TS({1, 2, 3}) is guaranteed to have infinitely many elements because n*6*F(1)[0]*F(1)[1]*F(2)[0]*F(2)[1]*F(3)[0]*F(3)[1]±1 (note this can be rewritten in the form n*k*(product_of_consecutive_primes)±1, where k is a product of numbers that should be sieved via SP, but we keep them for convenience of the argument) cannot be divided by any prime number obtained so far. We take the next element that didn’t get sieved. In this case, it is 5 because 4 is sieved out.
We can follow the same argument as in Euclid’s proof, and we will see that it will always contain infinitely many for each step n*k*(product_of_cosecutive_primes)±1. And set A will keep growing, as we are guaranteed to add one element to it out of infinitely many.
This is a more computational way of looking at the proof, and I hope it clarifies the proof to those not comfortable with the analytical guarantee in the first part.
Conclusion
I hope that the argument made sense to you and I would like to thank you for going through the whole thing.
I firmly believe that this is correct proof, and would love to get feedback.
I have been thinking a lot about why this hasn’t been proven before, and I suspect nobody seriously considers Euclid’s argument or the Sieve of Eratosthenes in modern number theory. However, I really don’t know.
