June 26 - August 12, 2014

A logical proof of the Twin-Prime Conjecture

"There are infinitely many primes p such that p + 2 is also prime."

Or, you could say it this way:

"There are infinitely many semiprimes of the form X²-1."

I provide the following "starter proofs", with the knowledge that they are not formal or complete.

• A proof by logic

• A poof by induction

• A proof by algorithm

And, last but not least,

• A "Euclidean Proof"

All these attempted proofs share a statement of arithmetic fact, as follows:

If X² - 1 is semiprime then X - 1 and X + 1 are its prime factors.

To unpack the meaning of this:

If X² - 1 is semiprime

(12 * 12) - 1 = 143

then X - 1 and X + 1 are its prime factors

11, 13

That is, P and P + 2.

Dear Reader, if you understand the arithmetic, please continue....

A logical proof begins with two sentences:

Statement 1
A natural number N of form X^2-1 where X>3 can be expressed as the product of two factors: X-1 and X+1.

Statement 2
Of the infinite set of Ns of a form X^2-1, there is an infinite subset for which X-1 and X+1 are prime factors.

The first argument is an arithmetic property that does not require elaboration. It states that there is an infinite set of square numbers minus one that are the product of two factors, composite or prime.

The second argument states that there is an infinite subset of square numbers minus one that are the product of two prime factors (semiprime).
 
The second argument is correct using the following logic: Of the set of X^2-1 there is a subset for which both factors are prime. (To be clear, X-1 and X+1 can also be composite - one or the other or both.) It is proved by the Infinitude of Primes and the Fundamental Theorem of Arithmetic. Using axiomatic set theory, both the set and the subset must be infinite.

I know, I know: Statement 1 appears to be banal, and Statement 2 seems to be wishful-thinking.

What if I added a third statement just to be perfectly clear about how simple the distribution of twin primes is?

Statement 3
All Ps and P+2s are of the form - and only of the form - described in Statement 1.

However, I have learned that academic mathematicians need more proof than commonsense logic can provide. This is because they are concerned about infinity. I will therefore attempt to prove in my naive fashion Statement 2 by induction and Statement 3 by algorithm.

The algorithms are interesting because they reveal the obvious truth that finding twin primes, by virtue of their multiplicative products (semiprimes) having a single position in relation to perfect squares and the quadratic interval, is subpolynomial (nearly linear actually).

This is followed by what I like to think is my best attempt so far: a proof in the style of Euclid's proof of the infinitude of primes. I do this in the forlorn hope that it will spur a truly mathematical mind to find the simple solution to this problem, rather than the most complicated and obscure!

First published July 19, 2014 with subsequent revisions

To prove Statement 2, begin with the following elaboration of Statement 1:

If a natural number of the form X^2-1 is greater than (X-1)^2 / 2 by a prime and less than (X+1)^2 / 2 by a prime then X-1 and X+1 are twin primes.

What does this really mean?

i.
If a natural number N of the form X^2-1 is an odd number, there exists an even-number difference with the previous square number ("perfect square").

ii.
There is an infinitude of such Ns.

iii.
All prime numbers can be expressed as half an even number.

iv.
All prime numbers can be expressed as half the difference between an odd N of the form X^2-1 and the previous perfect square.

Lemma
There are an infinitude of primes such that P = X^2 +Y^2 (Fermat's theorem on the sums of two squares), and there is an infinitude of primes such that P = X^2 +Y^2 (Pythagorean primes) where X = Y-1.

v.
The Ns of Step IV are of the same form as the subset of the Pythagorean primes where X=Y-1.

vi.
It follows that there are an infinitude of primes of which Step IV and Step V are true.

vii.
Thus, there must be an infinitude of  Ns of the form X^2-1 for which the factors X-1 and X+1 are both prime.

Therefore, "There are infinitely many primes p such that p + 2 is also prime".

First published July 29 (added "A la Fermat" August 12) 2014

To prove Statement 3, begin with the following huge "cheats" for an algorithm:

1. You only need to look at a SINGLE pair of Ns for EACH quadratic interval.
2. This pair can only be in ONE place relative to the square of the even number between them.

From these premises we can demonstrate two distinctive methods: "Trivial division" or "A la Fermat".

VBA Code for Excel:

'''''''''''''''''''''''' 'Twin Prime Calculator 'Trivial factors method '© 2014 Michael M. Ross '''''''''''''''''''''''' 'To Use This VBA Code: '1. Start with an empty Excel worksheet. '2. Paste code into the Visual Basic editor "ThisWorkbook" page. '3. Set min and max values. ' (If min > ~100000: Format first column as Text) 'Notes: '- On Windows runs very fast; on Mac at a handicapped snail's pace. '- Twin primes 3,5 and 5,7 are not calculated. '- Rows are blank if not twin-prime pairs '- Col1=nn, Col2=P, Col3=P+2, Col4=Smallest prime factor of sqrt(nn) Option Explicit Sub TWP() Dim blTp As Boolean Dim ct As Long 'row counter Dim tpct As Long 'twin-prime counter Dim dc As Long 'divisions counter Dim pf As Double 'prime factor Dim nn As Double 'even square - 1 Example: (12*12)-1=143 Dim sqrtN As Double 'even square root + 1 Example: sqrt(144)+1=13 Dim min As Double Dim max As Double min = 5 max = 1000 ct = 1 If ModOp(min, 2) = 0 Then min = min + 1 'an odd number sqrtN = min With Worksheets(1) .Cells.ClearContents .Cells.ClearFormats 'outer loop Do Until sqrtN > max nn = (sqrtN * sqrtN) - (sqrtN * 2) 'nn is an even square -1 'inner loop For pf = 3 To Sqr(sqrtN) Step 2 dc = dc + 1 If ModOp(nn, pf) = 0 Then 'Prime factors of nn are "relatively trivial" unless square of a prime +1 blTp = False Exit For End If blTp = True Next If blTp = True Then .Cells(ct, 1) = Trim$(nn) .Cells(ct, 2) = Trim$(sqrtN - 2) 'Twin prime P .Cells(ct, 3) = Trim$(sqrtN) 'Twin prime P+2 tpct = tpct + 1 Else .Cells(ct, 4) = Trim$(pf) End If ct = ct + 1 sqrtN = sqrtN + 2 DoEvents Loop MsgBox "Twin-prime results for range = " & Trim$(min) & " -> " & Trim$(max) _ + vbNewLine + "Division using n^2-n*2 factors = " _ + Trim$(dc) & vbNewLine & "Twin-prime count = " & Trim$(tpct) End With End Sub 'Remainder (modulus) function Private Function ModOp(v1 As Double, v2 As Double) As Double Dim vr As Double vr = v1 / v2 ModOp = vr - Int(vr) End Function

This algorithm's efficiency exploits the easy factoring of X^2-X*2. A fast primality test can be used when the first factor is not trivial.

'''''''''''''''''''''''' 'Twin Prime Calculator 'A la Fermat method '© 2014 Michael M. Ross '''''''''''''''''''''''' 'To Use This VBA Code: '1. Start with an empty Excel worksheet. '2. Paste code into the Visual Basic editor "ThisWorkbook" page. '3. Set min and max values. ' (If min > ~100000: Format first column as Text) ' On Windows runs very fast; on Mac at a handicapped snail's pace. 'Example: ' X = 28 ' X+1^2 = 841 ' X^2 - 1 = 783 ' 841 - 783 = 58 / 2 ' p1 = 29 ' Y = 32 ' Y-1^2 = 961 ' Y^2 - 1 = 1023 ' 1023 – 961 = 62 / 2 ' p2 = 31 Option Explicit Private Sub twp() Dim n As Double, min As Double, max As Double Dim nn1 As Double, nn2 As Double Dim sn1 As Double, sn2 As Double Dim p1 As Double, p2 As Double Dim tc As Long Dim rw As Long rw = 1 With Worksheets(1) min = 2 max = 1000 If ModOp(min, 2) = 1 Then min = min + 1 'an even number n = min 'That's it - no inner loop Do Until n > max nn1 = (n + 1) * (n + 1) sn1 = (n * n) - 1 p1 = nn1 - sn1 p1 = p1 / 2 ' Can eliminate some trivial cases but fails 5,7 ' If ModOp((nn1 + 1), 10) <> 0 And ModOp((nn1 - 1), 10) <> 0 Then ' n = n + 2 ' GoTo moveon ' End If 'Test potential twin (the smallest n to test) If IsPrime(p1) = False Then n = n + 2 GoTo moveon End If n = n + 4 nn2 = (n - 1) * (n - 1) sn2 = (n * n) - 1 p2 = sn2 - nn2 p2 = p2 / 2 'Test potential twin (the smallest n to test) If IsPrime(p2) = False Then n = n - 2 GoTo moveon End If If p2 - p1 = 2 Then 'Columns .Cells(rw, 1) = Trim$(nn1) ' (X + 1) * (X + 1) .Cells(rw, 2) = Trim$(nn2) ' (Y - 1) * (Y - 1) .Cells(rw, 3) = Trim$(sn1) ' (X * X) - 1 .Cells(rw, 4) = Trim$(sn2) ' (Y * Y) - 1 .Cells(rw, 5) = Trim$(p1) .Cells(rw, 6) = Trim$(p2) tc = tc + 1 End If DoEvents rw = rw + 1 n = n + 2 moveon: If n = 8 Then n = 4 '(exception for consecutive 3,5 and 5,7) Loop MsgBox "Twin-prime results for range = " & Trim$(min) & " -> " & Trim$(max) _ + vbNewLine & "Twin-prime count = " & Trim$(tc) End With End Sub 'Remainder (modulus) function Private Function ModOp(v1 As Double, v2 As Double) As Double Dim vr As Double vr = v1 / v2 ModOp = vr - Int(vr) End Function 'Using this only for demonstration purposes with small twins Private Function IsPrime(pt As Double) As Boolean Dim ap As Double If pt <> 2 Then If ModOp(pt, 2) = 0 Then IsPrime = False Exit Function End If For ap = 2 To Sqr(pt) If ModOp(pt, ap) = 0 Then IsPrime = False Exit Function End If DoEvents Next End If IsPrime = True End Function '''''''''''''''''''''''''''''''''''''''''''''''''''

This algorithm has near-linear scalability - restricted only by the efficiency of a fast primality test, such as Miller-Rabin.

The base case of the proof - the elaborated Statement 1 - says that the X-1 and X+1 factors can be one of the following pairs (and in no particular order):

X-1 is composite, X+1 is prime
X-1 is prime, X+1 is prime
X-1 is prime, X+1 is composite
X-1 is composite, X+1 is composite

The following four successive values of X^2-1 illustrate the four possible combinations of composite and prime, with red being prime numbers:

(X^2)-1	(X-1)^2	(X+1)^2	(X^2)-1 - (X-1)^2	(X+1)^2 - (X^2)-1	X-1	X+1
783	729	841	54	58	27	29
899	841	900	58	62	29	31
1023	961	1089	62	66	31	33
1155	1089	1369	66	70	33	35