Problems & Puzzles: Conjectures

If we define d_n as : d_n = p_n+1 - p_n, is easy to see that d₁=1 and d_n=even for n>1.

Now, it’s believed that "for n>1, dn=2 infinitely often" (Ref. 2, p. 19). This is the "Twin prime Conjecture", which can be paraphrased this way : "There are infinite consecutive primes differing by 2".

SOLUTION

Mr Liu Fengsui has sent (3/9/01) an argument that proves - according to him - the well known and named "k-tuple conjecture" 

This conjecture can be expressed the following way (see 1, 2 & 3):

• "Any admissible constellation of primes occurs infinitely often". 

Therefore, if this the Mr Liu's argument is correct then also the Twin Primes conjecture has been proved.

As you soon will discover this argument is close related to the Liu's approach to the prime numbers definition, approach that has been exposed in detail in the Problem 37 of these pages.

What follows is Mr Liu's argument. I should strongly point out that the most that Mr. Liu wants is to receive some criticism about this his work, through these pages or direct via his email below.

***

On the prime k-tuple conjecture
China, Liu Fengsui
Email: fengsuil@yahoo.com.cn 


In this paper we constructed a second order arithmetic P(N), Given a recursive formula

Tn which approximates the set of prime k-tuples and show its pattern occurs infinitely

often.



After all we give some operations.

Let A = <a1, a2,...,ai,...,an> be the finite set of natural numbers. 

If A = <a1,a2,...,ai,...,an> , B = <b1,b2,...,bj,...bm>, 

We define A + B = <a1+b1,a2+b1,...,ai+bj,...,a[n-1]+bm, an+bm>, 

A * B = <a1*b1,a2*b1,...,ai*bj,...,a[n-1]*bm, an*bm>. 

A \ B be the subtraction of sets.

We define the solution of the system of congruencies 

X = <a1,a2,...,ai,...,an> mod a, 

X = <b1,b2,...,bj,...bm> mod b 

be X = D = <d[1,1],d[2,1],...,d[i,j],...,d[n-1,m],d[n,m]> mod ab. 

where x = d[i, j] mod ab is the solution of the system of congruencies 

x = ai mod a , x = bj mod b. 

We identify the set <a> which has only one element with the number a

<a> = a.

So,we had defined a second order arithmetic

< P(N),+,*,<, 0,1>

where N is the set of natural numbers and P(N) is the power set of N.


We shall show the prime k-tuple conjecture of the first order

arithmetic <N,+,*, <,0,1> In the second order arithmetic <P(N),+,*,<,0,1>.

The prime k-tuple conjecture states that every admissible pattern for a prime 

constellation occurs infinitely often. ( the prime glossary).

To describe easily, we discuss the conjecture: 

There are infinity a such that

x^2 - x + a

all are prime for x = 0,1,2,...,k.

We use R(k,a) denote that x^2 -x + a all are prime for x = 0,1,2,...k.

and say this a be a solution.


Let pn be n-th prime , P0 = 2. 

For random prime pi > 2, we consider the set 

Bi = {a: pi | x^2 - x + a for some 0<=x<=k } 

= {a: x^2 -x + a = 0 mod pi for some 0<=x<=k }. 

By (pi +1 - x)^2 - (pi +1 -x ) = (pi + 1 -x)*(pi - x) = x^2 - x mod pi, it is easy to prove 

that, in the congruence x^2 -x + a = 0 mod pi , when x runs through the complete

system mod pi , a runs through the classes of residues <0,-2,-6,...,(pi+1)/2 - 

((pi+1)^2)/4> mod pi. Thus the set Bi are the classes of residues: 

Bi = <0,-2,-6,..., (pi+1)/2 - ((pi+1)^2)/4> mod pi , (pi+1)/2<= k. 

Bi = <0,-2,-6,..., k - k^2> mod pi, (pi+1)/2 > k. 

For example, let k = 4 , the first few terms of the sets Bi are 

B1 = <0,-2> = <0,1> mod 3, 

B2 =<0,-2,-6> =<0,3,4> mod 5, 

B3 = <0,-2,-6,-12> = <0,5,1,2> mod 7, 

B4 = < 0,-2,-6,-12> = <0,9,5,10> mod 11. 

Let m[n+1] = p0*p1*...*pn, from the set of all odd numbers X = <1> 

mod 2 we cancel the classes B1,B2,...,Bn successively, and obtain the

class T[n+1] mod m[n+1] such that 

T[n+1] = {a: x^2 - x + a =/= 0 mod pi, for x = 0,1,2,...,k and 

pi = p1,p2,...,pn}. 

Then the recursive formula of T[n+1], which is the set of non- negative 

representatives mod m{n+1] is as follows: 

T1 = <1>, 

T[n+1] = (<Tn + mn * <0,1,2,...,pn-1>) \ Dn 

where X = Dn mod m[n+1] is the solution of the system of congruencies 

X = Tn mod mn, 

X = Bn mod pn. 

For example, let k = 4 , the first few terms of T[n+1] are 

T1 = <1>, 

T2 = (<1>+<0,2,4>) \ <1,3> = <5>, 

T3 = (<5> + <0,6,12,18,24>) \ <5,23,25> = <11,17>, 

T4 = (<11,17>+,0,30,60,...,180>) \ <47,71,77,107,131,,161,191> 

= <11,17,41,101,137,167>. 

Given random integer k>1, take an integer s such that 

(ps+1)/2<= k < (p[s+1]+1)/2, 

then the number of all elements of the set T[n+1] is 

| T[n+1] | = (p1-1)/2 * (p2-1)/2 *...*(p[s+1]-k) *...*(pn-k). 

From the recursive formula Tn ,obviously the criterion of prime k-tuples is 

R(k,a) iff a = pn = min Tn > k-1.

Where min Tn is the smallest number of the set Tn. 

This criterion R(k ,a) recursively enumerate all prime k-tuples.

This algorithm is a second order version of the Eratosthenes sieve. At n-step, we had 

computed all solutions R(k,a) , a < pn. In set Tn, if t belongs Tn and k^2 - k 

+ t < pn^2 then t is a solution R(k,t). As n larger enough , almost all

elements of set Tn are solutions. If a > pn is a solution then a belongs the

set Tn mod mn. So that the recursive formula Tn approximates all solutions.


As an elementary result of recursive formula Tn ,we obtain another solution

for the Conjecture 17. ( http://www.primepuzzles.net/conjectures/conj_017.htm )

Let (pn+1)/2 <= k, let A = min Dn, | Dn | = | Tn |*(pn+1), then 

SPD(T,A) = pn for x = b. Where min Dn is the smallest number of the set Dn.



We can design a program and compute some exactly solutions of R(k,a). But with our 

computer we can never 'touch' entire set of R(k,a) and can never know if they are 

infinite.



Now let us see the result without actually "running the program" from theory.

We consider the limit of the sequences of sets T1,T2,...,Tn,......, as the  classes of

residues, there is include relation N > T1 > T2 >......> Tn>......., thus there is the Lim Tn.

As n goes to infinity, we canceled all classes B1,B2,...,Bi,......, we  will obtain what 

result? It is easy to prove lim Tn is empty ,since that when  we canceled all classes

B1,B2,...,Bi,... to sift the solution R(k,a) , we removed the solution R(k,a) also by

pn = a and pn | a. To show the infinity first we consider the non empty set. We modified 

the set Bi to be Bj:


Bi = {a: pi | x^2 - x + a for some 0<=x<=k but pi =/= k^2 - k +a} 

= {a:x^2 -x + a = 0 mod pi for some 0<=x<=k but pi =/= k^2 -k +a}. 

As n goes to infinity we canceled all classes B1,B2,...,Bj,......, since lim | Tn | is infinite 

then lim Tn is not empty . 


Now we try prove the pattern R(k,a) , k < 41 occurs infinitely often.


Proof: Suppose that the number of patterns R(k,a) is finite, then there is a maximum 

number a0 such that for all a > a0 R(k,a) is false. From the set of all  natural numbers we

cancel the classes B1,B3,...,Bi,...,Br successively, and obtain the class Tr such that a0 = 

mim Tr = pr, then for all j>=r in the class Tj there is not any a such that R(k,a) ,and for

all a > a0 there is  not any a such that R(k,a).


From the class Tr we continue cancel the set B[r+1],...,Bj,......Now as n

goes to infinity, lim | Tn | is infinite and lim Tn is not empty . Take 

number e belongs lim Tn then x^2 - x + e does not contain any prime pi or pj 

as factor except itself for x = 0,1,2,......,k thus R(k,e) is true by 

definition and e > a0. This is a contradiction so we have proved that The

pattern R(k,a) , k < 41 occurs infinitely often. #



Change the sets Bi, we can prove the infinity of various patterns with above 

method. Example, the primes in arithmetic sequence ax+b, (a,b)=1.

Give pi, except pi | a, let Bi = {x: ax+b = 0 mod pi}, then

| Tn | =( p1-1)*...*(pn-1), but pi | a. Iterate above proof ,we obtained the

Dirichlets Theorem again.



Now we find the admissible or necessary condition of infinity by above method. 


1). lim | Tn | is infinite, so that the k is a constant.

2).The set of solutions is admissible non-empty, or at least there is one non 
trivial solution. 


It is no meaning to discuss if infinite for empty, to extend above method to  empty, we

discuss the situation that the set of solutions is empty. Assume the  set of solutions

R(k,a) is empty, we select a disjunctive proposition:

There is no any solution a > a0 or there is no solution a <= a0.


Assume the disjoint "there is no solution a > a0" , run a proof, if we do not obtain

contradiction, we can not prove anything, if we obtain a contradiction, then we have

proved the disjoint " there is no solution a <= a0" is true, namely we have proved the 

set of solutions is empty.


There is an Euler's formula x ^ 2 - x + 41 all are primes for x = 0,1,2,...,40. So that, for k

< 41 , at least there is one non trivial solution R(k,a), by above proof, we have known 

that the pattern R(k,a) , k < 41 occurs infinitely often. For k >= 41, we do not know if

there is a number a such that x ^ 2 - x + a all are primes for x = 0,1,2,...,k, we do not

know if they are infinite. If we find one solution, then they are infinite.  

This is incredible! In less than one week this noble Conjecture has received an attack by two flanks. Now (12/9/01) it is the Alan Tyte's turn.

Alan has constructed an analytical proof that shows that there are more twins in the range (q, q^2) than in the range (p, p^2) being q the following prime to p. But if this is rigorously true then it's also true than in each new range we have at least one more twin primes. Being the quantity of primes infinite, this also means that the number of twin primes is infinite.

The most surprising fact is that - as you will discover soon - both attacks uses as background for the reasoning, the Eratosthenes sieving machine...

This is the Tyte's proof in detail:

A proof that there are an infinite number of twin primes
by Alan Tyte

Notation 1

• Let P be the set of odd positive integers > 1, i.e. P = {3, 5,7,9, . . . . . }
• Let m represent a composite integer.
• Let u represent an integer whose status is currently undetermined, that is an integer which has not yet been shown to be composite by casting out a prime of which it is a multiple and which thus may, or may not, be a prime.
• Let a triple be a sub-set of P consisting of three consecutive odd integers, starting with a multiple of 3 ( e.g. triples are {3 5 7} ; {9 11 13}, etc.)

Lemma 1

After casting out all multiples of 3 , each triple in P , subsequent to the triple containing 3 , has format muu (the triple {3 5 7} has format uuu ).

Proof : follows from definitions.

After casting out multiples of 3 , P consists of an infinite set of triples beyond {3 5 7}, each of which contains a possible twin prime. As each further prime is cast out, a proportion of the u integers become m integers and the number of possible twin primes decreases.

Lemma 2

As further primes are cast out, a triple may have one of four formats : mmm, mum , mmu or muu . Proof : follows from definitions.

Examples:

• After casting out 3 and 5, the triple {21 23 25} has become mum.
• After casting out 3, 5, 7 and 11, the triple {117 119 121} has become mmm .

Notation 2

• Let A represent a triple of format mmm, B of format mum, C of format mmu and D of format muu .
• Let t be the number of triples in a pattern repeat (see Lemma 3 below).
• Let a be the count of A triples in a pattern repeat; similarly b for B , c for C and d for D so that t = a + b + c + d.
• Let p be any prime > 3 Let q be the next greater prime to p ( e.g. if p = 7 then q = 11 or if p = 59 then q = 61).

Lemma 3

After multiples of p are cast out, starting with the first triple beyond that containing p , there will be a pattern of As, Bs, Cs and Ds which repeats infinitely. The number of triples in the pattern, t , will be the product of all the primes from 5 up to and including p .

After multiples of q are cast out, the pattern length is t . q triples.

Proof:

Initially after casting out multiples of 3 there is one triple in the pattern repeat, i.e. a D . There are 6 integers effectively spanned by each triple if even numbers are included. Since 5 is prime to 6, multiples of 5 will only occur at the same position within those 6 integers every 5th triple. Hence there will be 5 triples in the pattern repeat after casting out multiples of 5. Similarly, since 7 is prime to the new effective pattern span of 30 integers, there will be 5 x 7 triples in the pattern repeat after casting out multiples of 7 . As each new prime is prime to the existing pattern length, the lemma follows.

Example: After casting out 5 and 7, Lemma 3 predicts a pattern repeat of 35 triples as shown below :

9 11 13, D
15 17 19, D
21 23 25, B
27 29 31, D
33 35 37, C
39 41 43, D
45 47 49, B
51 53 55, B
57 59 61, D
63 65 67, C
69 71 73, D
75 77 79, C
81 83 85, B
87 89 91, B
93 95 97, C
99 101 103, D
105 107 109, D
111 113 115, B
117 119 121, C
123 125 127, C
129 131 133, B
135 137 139, D
141 143 145, B
147 149 151, D
153 155 157, C
159 161 163, C
165 167 169, D
171 173 175, B
177 179 181, D
183 185 187, C
189 191 193, D
195 197 199, D
201 203 205, A
207 209 211, D
213 215 217, A

then pattern restarts:

219 221 223, D
225 227 229, D
231 233 235, B
237 239 241, D
243 245 247, C
249 251 253, D
255 257 259, B
261 263 265, B
etcetera

Lemma 4

When multiples of q are cast out:

1 / q of what were Ds in the t . q triples of the new pattern repeat become Bs
1 / q of the Ds become Cs
1 / q of the Bs become As and
1 / q of the Cs become As.

The counts in each pattern repeat after casting out multiples of q is thus:

for Ds is d.( q - 2 )
for Cs it is c . ( q - 1 ) + d
for Bs it is b . ( q - 1 ) + d
for As it is a . q + b + c

And

d.( q - 2 ) + c.( q - 1 ) + d + b.( q - 1 ) + d + a.q + b + c = (a + b + c + d).q = t.q

Proof:

This is similar to that for Lemma 3 . The new pattern consists of q sets of pattern length t . If, for example, the nth integer in the first of set of length t is a multiple of q , then in none of the remaining q - 1 sets can the nth integer be a multiple of q , since q is prime to t ; i.e. 1 / q of the nth integers in each set are multiples of q . If a multiple of q is already known to be a multiple of a smaller prime, then the triple's format is unchanged ; e.g. once an A, always an A . Only one u in any triple can change to an m as odd multiple of q are separated by 2q . Hence the only changes possible are from D to B or C , and, from B or C to A . If the nth triple in the first set is changed from a D to a C , an identical change cannot occur to the nth triple in any other set of the q sets; in one other set the nth triple will be changed from a D to a B . 

Examples:

After multiples of 3 are cast out, then a = 0 , b = 0, c = 0, d = 1 and t = 1

9 11 13 pattern restarts 15 17 19 pattern restarts 21 23 25 etc. (D) (D) (D)

When casting out multiples of 5, a => 0 x 5 + 0 + 0 = 0 b => 0 x (5 - 1) + 1 = 1 c => 0 x (5 - 1) + 1 = 1 d => 1 x (5 - 2) = 3 t => 1 x 5 = 5.

9 11 13, 15 17 19, 21 23 25, 27 29 31, 33 35 37, pattern restarts 39 41 43, 45 47 49, 51 53 55, etc. (D D B D C) (D D B...)

When casting out multiples of 7, a => 0 x 5 + 1 + 1 = 2 b => 1 x (7 - 1) + 3 = 9 c => 1 x (7 - 1) + 3 = 9 d => 3 x (7 - 2) = 15 t => 5 x 7 = 35. See list of triples in Lemma 3

More examples:

Repeating these iterations gives : after casting out multiples of 19 a = 336410 b = 450765 c = 450765 d = 378675 t = 1616615 ( these figures were verified by an actual count) after casting out multiples of 29 a = 271120850 b = 296226315 c = b d = 214708725 t = 1078282205 Although the counts rapidly reach huge numbers as further primes are cast out, they are finite and calculable.

Corollaries to Lemma 4

After multiples of p are cast out, the proportion of Ds in the infinite set of triples beyond the triple containing p is d / t . The ratio d / t applies exactly over any set of t consecutive triples. Over sets of less than t triples it is the average proportion.

After multiples of q are cast out, the proportion of Ds in the infinite set of triples beyond the triple containing q is d . (q - 2) / t . q

Lemma 5

When casting out all multiples of p , the format of all triples less than the triple containing p ^2 cannot be affected. Any Ds between p and its square are triples containing twin primes. 

Proof:

When casting out multiples of p , all multiples of p less than p ^2 will have been found when casting out smaller primes.

Example:

All odd multiples of 7 less than 49 are also multiples of 3 or 5.

Proof that there are an infinite number of twin primes:

It will be sufficient, by Lemma 5, to show that there are always Ds between a prime and its square. We have shown that there are Ds between 5 and 25 and between 7 and 49. We now show that there are more Ds between q and q ^2 than there are between p and p ^2 , in fact as primes get larger there are more and more twin primes between a prime and its square.

Let Np be the number of Ds between p and p ^2.
Let Nq be the number of Ds between q and q ^ 2.

From Lemma 4, the proportion of Ds in the pattern repeat after casting out multiples of p is d / t .

The number of triples between p and p ^2 is the integral part of ( p ^2 - p) / 6 = p . (p -1 ) / 6 .

Hence, on average:

Np = [ p.(p - 1 ) / 6 ] x [ d / t ] = d.p.(p -1) / ( 6 . t )

From Lemma 4 , the proportion of Ds in the pattern repeat after casting out multiples of q is ( d . (q - 2) ) / ( t .q ) The number of triples between q and q ^2 is the integral part of ( q ^2 - q) / 6 = q .(q -1 ) / 6

Hence, on average:

Nq = [ q.(q -1 ) / 6 ] x [ ( d.(q - 2) ) / ( t.q )] = d.(q -1).( q - 2) / ( 6.t )

Now q >= p + 2 , therefore (q -1) . ( q - 2) > p . (p -1)

Hence Nq > Np .

Conclusion:

Since this (Nq>Np)  means that there are always new twin primes between a prime and its square, and since there are an infinite number of primes, there must be an infinite number of twin primes.

Examples of counts of twin primes between a prime and its square obtained from actual counts:

Between 5 and 25 there are 2 twin primes, i.e. 11 13 and 17 19 . Between 101 and 101 x 101, there are 201 twin primes. Between 199 and 199 x 199 , there are 574 twin primes. Between 293 and 293 x 293 , there are 1056 twin primes.

***

And my question: Is this proof correct or is it flawed?

***

Regarding the Tyte's proof I have received three enthusiastic comments-contributions, pointing out that while the averaging step made by Alan is questionable, maybe this approach shows where to look for in the solution of this Conjecture. These first three comments are from Chris Nash, Fabrice Marchant and Leadhyena Inrandomtan:

"About Alan Tyte's proof : all the beginning up to "Lemma 5" is right but there are 2 errors in the end of the proof, after each "Hence, on the average :" because we do not know the way our beloved Ds are spanned : no reason to be sure they are put at the same rate between x and x^2 than between a whole pattern. However, I think the idea of the proof with As, Bs ... is great and I'll try to work in the way of Alan." (F. Marchant)

***

"I would like to bring this up in a forum... I feel that his proof is almost correct, I have but one unfortunate problem with it. I do feel that the first person to reconcile this slight over assumption will clench this problem once and for all...

I verify all of Alan Tyte's proof up to and including lemma 4. Keep in mind however that up to this point the lemmas only deal with the unidentified letters in the sequence of triples produced. It is in lemma 5 that he attempts to make the jump to prime numbers. And he does correctly state that after casting out the p's that all 'unidentified's that represent numbers under p^2 in the pattern repeat represent primes. It is the distribution that concerns me.

Alan Tyte states that the proportion of Ds in the pattern repeat after casting out multiples of p is d/t. This is where I disagree. If the pattern of letters follows with the pattern of the primes, they would share the same distribution, IE pi(x) approaches n/log(n) as n approaches infinity, as stated in the prime number theorem. Since the pattern repeat models a pattern that does not follow a UNIFORM distribution, assuming that a segment of the pattern has the same proportion is illegal under the laws of statistics.

It may seem like a technical point; however the problem becomes paramount. If we took the proportion of primes to the natural numbers as the size of the subset extended to the size of the natural numbers, the proportion would approach lim n->inf of 1/log(n) or 0. If this type of previously mentioned assumption were allowed, we could say that for any segment of the natural numbers that it contained no primes, because it would have the same proportion of primes to naturals, IE 0.

As I said before, this proof can be fixed, but I'm not sure how. I would agree with his numbers; I do think that the proportion of twin primes to all primes increases with the size of the segment from n to n^2. I don't have the statistical expertise to handle the manipulation of a logarithmic distribution, which I believe that the twin primes follows. I think that Tyte is on a goldmine of analysis, and I would even conjecture that these patterns could be analyzed for not just p,p+2 but also p,p+4 and other possibilities... (Leadhyena Inrandomtan)

***

Mr. John Washburn as a critical note (8/3/2002) to the Liu Fengsui's proof, that ends with a happy ending phrase "I thinks that this problem is repairable":

***

This is the Mr. Liu's answer (28/302) to Mr. Washburn:

I thank Mr. John Washburn very much for his kind comment and points the flaw.

I welcome anyone comment my proof or point any flaw.

New I post my opinion,please Mr. John Washburn bear with it.

 

The essence of the flaw pointed by Mr. John Washburn is sentence:

 

Liu Fengsui must also prove the minimal member of Tn is less than (Pn+1)^2 - 2.

 

I think, perhaps, Mr. John Washburn misunderstanded my criterion of prime k-tuples

            R(k,a) iff a = pn = min Tn > k-1.
to be

 

            R(k,a) iff a = min Tn > k-1.

 

Perhaps,Mr. John Washburn misunderstanded my lim of set sequences Tn  Lim Tn to be every Tn.

 

Perhaps, it is Mr. John Washburn own some difficults or approach.

 

If the sentence is repaired to be an existence sentence:

 

             exist a Tn such that minimal member of Tn is less than (Pn+1)^2 - 2.

 

It is right, and Liu Fengsui has proved it.Otherwise,obviously, it is false.

 

I wish Mr. John Washburn can articulate the flaw better.If I misunderstanded the idea

of Mr. John Washburn , please criticize .

***

Mr Liu Fengshui wrote (4/7/04):

"

When 6th WSEAS International Conference on APPLIED MATHEMATICS
(August 17-19, 2004, Corfu, GREECE) call paper, I tried submit my paper "On the prime k-tuple conjecture".
  

May 13, 2004, I received the reply:

"We have now the first results from our reviewers. Based on the review of at least 2 independent reviewers, we are glad to inform you that your paper has been accepted. Also, your paper has been selected in the CATEGORY A' of the papers.
That means: publication in the Conference Proceedings as well as in WSEAS Journals--- WSEAS Transactions on mathematics."

The main reviews: this paper is an original work, we do not find error

in the proof twin prime conjecture and so on, publish it."