A Proposed Proof for Legendre's Conjecture

Status: Lemma 3 is wrong and therefore Theorem 4 is also wrong. For example, the Sequence Divisibility Problem is solvable for n=22 (1->2, 2->5, 4->3, 6->7, 8->11, 14->13, 18->17) but there is no solution for n=22 with Ascending Prime Order Form.

It may be possible to weaken Lemma 3 and Theorem 4 and still prove the Legendre Conjecture. If I am able to do this, I will update the status to this hub.

Legendre's conjecture is the claim that there is always a prime number between x² and (x+1)². It was first proposed by the mathematician Adrien-Marie Legendre.

In what follows, I present my attempt at a proof. To be clear, there is most likely a fatal error in the proof. A problem does not stay unsolved since the 1800's unless it is unbelievably hard. When problems like this one find their solution, it usually involves a major breakthrough by a major mathematical talent. In recent years, Fermat's Last Theorem and Poincare's Conjecture have both been solved. In both of these cases, the solution was historically important and the mathematicians behind these proofs were two of the most brilliant mathematicians of recent times.

I can make no such claim regarding my argument. It does not involve anything more than elementary number theory. If my argument is valid, it would suggest that mathematicians have missed a very simple argument based on Bertrand's Postulate. This is highly unlikely. The only claim I can make is that I haven't yet found the flaw.

To everyone who reads through this, if you have any question about my argument, please feel free to raise them in the comments. If you can suggest ways to simplify the argument or to use more standard terminology, please let me know. Any questions or corrections are greatly appreciated.

As soon as someone finds the flaw, I will update this hub. I am hopeful that at the very least, the I have made will be interesting to beginners in number theory.

The basic approach is to generalize Legendre's Conjecture to a more general mathematical question which I call the Sequence Divisibility Problem (see Definition 1 below):

Find a sequence of n consecutive integers where each integer in the sequence is divisible by at least one prime p ≤ n.

I will argue that a solution to this problem does not exist if n+1 is a prime. For example, I will attempt to show that if n=4, n=6, n=10, etc., then there is no solution to the Sequence Divisibility Problem.

Finally, I will show that this claim if true proves that Legendre's Conjecture is true.

I divide up the argument that follows into the following sections:

1. Sequence Divisibility Problem
2. n-Slot Form
3. Ascending Prime Order Form
4. Properties of Ascending Prime Order Form
5. Legendre's Conjecture

I apologize in advance for the unusualness of the n-Slot Form and Ascending Prime Order Form. I am not familiar where these types of ideas have been presented in the mathematical literature so I invented my own names. If anyone knows of a more standard mathematical formulation for the same idea, please let me know in the comments and I will update this proposed proof.

The main argument for Legendre Conjecture focuses on what I am calling the Sequence Divisibility Problem. There may very well be an established mathematical term for this and I will change this section if someone has a suggestion.

In the mean time, here's a definition:

Definition 1: Sequence Divisibility Problem

Problem Statement: Is it possible to find a sequence of n consecutive integers where each integer in the sequence is divisible by at least one prime p where p ≤ n

Definition 2: Representation of a sequence of n consecutive integers in terms of x

By convention, I will specify the sequence in terms of a starting integer x so that we the sequence of n consecutive integers consists of x+1, x+2, ..., x+n.

In the argument that follows, x can be any integer, n is the length of the sequence in question, and the first integer in the sequence is x+1 and the last integer in the sequence is x+n.

To make these two definitions clearer, I will provide three examples of sequence divisibility problems.

Example 1: Sequence Divisibility Problem for n=3

In this case, the sequence consists of x+1, x+2, x+3. The challenge is to find a value of x where all three integers in the sequence are divisible by 2 or 3.

The solution is to pick an x+2 which is odd and divisible by 3. For example, if x+2=21, we find that x=19 is a solution to the sequence divisibility problem for n=3.

In this case, x+1, x+2, x+3 is 20, 21, 22 and sure enough all 3 integers are divisible by 2 or 3.

Example 2: Sequence Divisibility Problem for n=8

One solution that works is x+1 is even, x+2 is divisible by 3, x+4 is divisible by 5, and x+6 is divisible by 7. In this case, we can see that 2 divides x+1, x+3, x+5, and x+7; 3 divides x+2, x+8, 5 divides x+4, 7 divides x+6.

Now, let's find a value of x that satisfies these requirements:

x + 1 ≡ 0 (mod 2)

x + 1 ≡ -1 (mod 3)

x + 1 ≡ -3 (mod 5)

x + 1 ≡ -5 (mod 7)

We can now use the Chinese Remainder Theorem to find x+1. Let y=2*3*5*7=210.

x+1 = 2*70*1 + 2*42*3 + 2*30*4 = 632

So x = 631 and the sequence of 8 consecutive integers is 632, 633, 634, 635, 636, 637, 638, 639.

We can see that 2 divides 632, 634, 636, 638, 3 divides 633, 639, 5 divides 635, and 7 divides 637.

Example 3: Sequence Divisibility Problem for n=4

In this case, the Sequence Divisibility Problem is not solvable. In other words, there is no sequence of 4 consecutive numbers where each integer is divisible by 2 or 3.

To establish this point, I present my first lemma:

Lemma 1: The Sequence Divisibility Problem for n=4 has no solution

Proof:

(1) Let x+1, x+2, x+3, x+4 be a sequence of consecutive integers..

(2) If x+1 is even, then 2 divides x+1 and x+3. but 3 cannot divide both x+2 and x+4 so there is no solution.

(3) If x+1 is odd, then 2 divides x+2 and x+4 but 3 cannot divide both x+1 and x+3 so there is no solution.

QED

In dealing with the Sequence Divisibility Problem, I have found that it is useful to have a notation for representing possible solutions to the problem.

I call my notation n-Slot Form and here is my definition:

Definition 3: n-Slot Form

This is a list of n slots that lists the smallest prime that divides the number at that relative position. So slot 1 corresponds to x+1, slot 2 corresponds to x+2 and so on up until the nth slot which corresponds to x+n. n-Slot Form can be used to represent a solution or can be used to represent an attempt. In the case of failed attempt, at least one of the slots will be marked empty.

I hope that the use of this form will become clearer as I provide 3 examples of its use.

Example 4: n-Slot Form for a solution to the Sequence Divisibility Problem for n=3

The 3-slot list that solves this problem is:

1. 2
2. 3
3. 2

We can see that 2 divides x+1 and x+3 while 3 divides x+2.

Example 5: n-Slot Form for a solution to the Sequence Divisibility Problem for n=8

An 8-slot list that solves this problem is:

1. 2
2. 3
3. 2
4. 5
5. 2
6. 7
7. 2
8. 3

In this list we can see that slot 5 is divisible by 2 and 3 but only 2 is listed. As a convention, only the lower prime 2 is listed.

Once an n-Slot Form is shown to solve a Sequence Divisibility Problem, it can readily be solved to find the value of x using the Chinese Remainder Theorem as demonstrated by Example 2 above.

Example 6: n-Slot Form for an attempt to the Sequence Divisibility Problem for n=4

Since the Sequence Divisibility Problem for n=4 doesn't have a solution (see Lemma 1 above), it follows that all we can do is list out a failed attempt. In this way, the n-Slot Form can be used to check whether an attempt was successful or not.

For example, consider this n-Slot Form which is a failed attempt:

1. 2
2. 3
3. 2
4. <none>

In thinking about the n-Slot Form, I have found particular variation of this form which is especially useful in analyzing the Sequence Divisibility Problem. I call this variation: Ascending Prime Order Form.

In general, I have found that Ascending Prime Order Form can be built rather easily in most cases and that in doing so, it is possible to find a solution. I provide a definition of Ascending Prime Order Form and then I present an algorithm for building it for a given n.

Definition 4: Ascending Prime Order Form

A n-Slot Form is in Ascending Prime Order Form is the first appearance of a prime is in ascending prime order. For example, slot 1 has 2, slot 2 has 3, and the 5 appears for the first time before 7 and so on.

Example 6: An Ascending Prime Order Form for n=8

I will show 8-Slot Forms for solving the Sequence Divisibility Problem for n=8.

First, I show an example that is not in Ascending Prime Order Form:

1. 2
2. 3
3. 2
4. 7
5. 2
6. 5
7. 2
8. 3

As you can see, the first appearance of 7 in slot 4 appear before the first appearance of 5 in slot 6. In Ascending Prime Order Form, each smaller prime appears for the first time before all bigger primes.

We can put the above solution into Ascending Prime Order Form by switching slot 4 and slot 6. For example, this 8-Slot Form is in Ascending Prime Order:

1. 2
2. 3
3. 2
4. 5
5. 2
6. 7
7. 2
8. 3

One of the major benefits of the Ascending Prime Order Form is how easy to build this form for a given sequence of consecutive integers to determine if it represents a solution.

Here is the algorithm for building an n-Slot Form in Ascending Prime Order Form:

Algorithm 1: Ascending Prime Order Method for Solving a Sequence Divisibilty Problem for n.

(1) Start out with n empty slots

(2) Place a 2 in the first slot and a 2 in every other slot after that. So that there is 2 after each odd slot.

(3) Place a 3 in the second slot and a 3 in every 6 slots after that. So, the next slot filled will be slot 8 and after that slot 14 and so on.

(4) Proceed in a similar way for each prime p ≤ n. Place the first instance of the prime p in slot p-1. Now place a p every 2*p where there is not already a prime in a slot.

(5) If after you are done with all the primes, there is no empty slot, then you have found a solution. If there is no empty slots, then there is no solution that is in Ascending Prime Form.

In what follows, I will show that if there is no solution in Ascending Prime Order Form, then there is no solution. So, that the algorithm above represents a solution to the Sequence Divisibility Problem for all n.

Now, I will show that the Ascending Prime Order algorithm is a solution to the Sequence Divisibility Problem.

Lemma 2: In ascending prime form, the first slot filled by a prime p is p-1

Proof:

(1) For 2, slot 1 is filled.

(2) For 3, slot 2 is filled.

(3) Assume that this is true for all primes up to some p ≥ 3

(4) So for each prime v ≤ p, it follows that the first slot is v-1.

(5) To complete the proof, I need to show that the next prime q will fill slot q-1.

(6) If a slot is odd, 2 will fill the slot so we only need to consider even slots.

(7) I will now show that all slots less than q-1 are filled with a prime smaller than q and at q-1 the slot is not filled by any other prime.

(8) Assume that a slot c is less than q-1 and c is even.

(9) We know that c+1 is not a prime since the next prime is q.

(10) Then there exists a prime v ≤ p that divides c+1. Further if w = (c+1)/v, it follows that w is greater than 1.

(11) By assumption this prime fills slot v-1 so v divides x+v-1. Further, it follows that v divides x+v-1 + wv = x + v - 1 + (c+1) = x + v + c which means that v also fills slot c.

(12) Assume that slot c = q-1.

(13) Assume that there exists a prime v ≤ p that divides x+c so that is already filled.

(14) Then it follows that v divides x + v - 1 and v divides x+c.

(15) But in this case v divides (x + c) - (x + v - 1) = c - v + 1 which is only true if v divides c+1 = q which is impossible since q is a prime by assumption.

QED

Lemma 3: If the Sequence Divisibility Problem is solvable, then it is solvable by the Ascending Prime Order Method

Proof:

(1) Assume that we have an n-Slot Form that represents a solution to the Sequence Divisibility Problem for n. (see Definition 3 above)

(2) We can assume that the solution is not in Ascending Prime Form.

(3) Assume that 2 is not in slot 1 for this solution.

(4) Then there exists another n-Slot Form solution where 2 is in slot 1 since:

(a) In solution where 2 is not in slot 1, 2 is either in an even slot or an odd slot.

(b) Let c be the first slot with 2.

(c) If c is odd, then we can move 2 to slot 1 and put 2 in all odd slots. There are no empty slots since if any of the displaced primes was in any other slot, they are still there. All the odd slots now have 2 in them instead of the other prime.

(d) If c is even, then move all primes in odd slots 1 down to an even slot and move 2 to slot 1.

(e) There are no empty slots after this change in (d). This can be proven. Assume that there was an empty slot after this change. It will be in an even slot since all odd slots have a 2 in them. But if there is an empty slot, then previously there was an empty slot in the odd since the prime that would have divided the slot above it will now divide it. But this is impossible since we had assumed a solution so there are no empty slots after this change.

(5) If 2 is the first slot but 3 is not in the second slot, then there exists a solution where 2 is in the first slot and 3 is in the second slot since:

(a) The argument here is similar to the argument used in step 4.

(b) The 3 is either in a slot that is congruent to 0 modulo 6, congruent to 2 modulo 6, or congruent to 4 modulo 6.

We know it's in an even slot since by assumption 2 is in all odd slots.

(c) If 3 is in a slot that is congruent to 2 modulo 6, then we can move 3 to slot 2 and put 3's in all slots that are congruent to 2 modulo 6. There are no empty slots since if any of the displaced primes was in any other slot, they are still there. All the slots congruent to 2 modulo 6 now have 3 in them instead of the other prime.

(d) If 3 is in a slot that is congruent to 0 modulo 6, then we move all primes in slots that are congruent to 2 modulo 6 down 4 slots and move 3 to slot 2. We can assume that there are no empty slots. There are no empty slots 2 modulo 6 since they will all have 3's in them. The only other change was in a slot congruent to 0 modulo 6. But if there is a hole now, then there must have been a hole previously in a slot congruent to 2 modulo 6 which is impossible since we assumed we had a solution.

(e) If 3 is in a slot that is congruent to 4 modulo 6, then we move all primes in slots that are congruent to 2 modulo 6 down 2 slots and move 3 to slot 2. There are no empty slots 2 modulo 6 since they will all have 3's in them. The only other change was in a slot congruent to 4 modulo 6. But if there is a hole now, then there must have been a hole previously in a slot congruent to 2 modulo 6 which is impossible since we assumed we had a solution.

(6) If 2 is in slot 1 and 3 is in slot 2 and there is at least one prime not in ascending prime form, then there is a solution that is in ascending prime form since:

(a) Let p be the lowest prime that is not in ascending order.

(b) If p is in a slot congruent to p-1 modulo 2*p, then we can simply move p to slot p-1 and we are done. Again, there is still no empty slot because all slots congruent to p-1 modulo 2*p are filled by p.

(c) If p is not in a slot congruent to p-1 modulo 2*p, then let c be the current slot and let w be the smallest integer such that c + w is congruent to p-1 modulo 2*p.

(d) Now we move all primes in a slot congruent to p-1 modulo 2*p down w slots.

(e) We now move p into the p-1 slot. We can assume that there are no empty slots because all the slots congruent to p-1 modulo 2*p are filled by p or some lower prime and if there is an empty slot congruent to c modulo 2*p, then it follows that there was a slot congruent to p-1 modulo 2*p slot which was not the case.

(f) We can repeat step 6(a) thru 6(e) for all primes that are not in ascending prime form until we have a solution that is in ascending prime form.

(7) In this way, I have shown that is any solution exists, an solutions exists in ascending prime form.

QED

Corollary 3.1: If there is no solution in Ascending Prime Order Form, then there is no solution to the Sequence Divisibility Problem for n.

Proof:

(1) Assume that there is no solution in Ascending Prime Order form for n.

(2) Assume that there is a solution to the Sequence Divisibility for n.

(3) By Lemma 3 above, it follows that there must be an Ascending Prime Order solution.

(4) But this is impossible by the assumption in step 1 so we reject our assumption in step 2.

QED

Theorem 4: If n+1 is a prime, then there is no solution to the Sequence Divisibility Problem for n.

Proof:

(1) n=1 is true because there are no primes less than 2. n=2 is true since 2 can only divide x+1 or x+2 but not both. Lemma 1 above shows that there is no solution for n=4.

(2) Assume that there is no solution to the Sequence Divisibility Problem for n where n+1 is prime up to n ≥ 5.

(3) To complete the proof, we only need to show that q is the next prime after n+1, then this is also true for n=q-1.

(4) Let q be the next prime after n+1.

(5) Assume that there is a solution to the Sequence Divisibility Problem for q-1.

(6) From Lemma 3 above, it follows that there is a solution in Ascending Prime Form.

(7) So we can assume that there is a prime v where v < q and v divides x + q - 1.

(8) By Lemma 2 above, we know that v divides x + v - 1.

(9) But then v also divides (x + q - 1) - (x + v - 1) = q -v but this is impossible since q is a prime.

(10) Therefore, we have a contradiction and we reject our assumption in step #5.

QED

Corollary 4.1: Legendre's Conjecture

For all x, there exists a prime between x² and (x+1)²

Proof:

(1) Assume that Legendre's Conjecture is false and there is no prime greater than x² and less than (x+1)²

(2) It follows then that every integer in the sequence x² + 1, x² + 2, ..., x² + 2x is divisible by a prime v ≤ x since:

(a) Assume that there was an integer c in the sequence that is not divisible by a prime ≤ x.

(b) Then it follows that there are at least two integers a,b where c=ab and a > 1 and b > 1 since c is not a prime.

(c) But then c = ab ≥ (x+1)(x+1) = x² + 2x + 1 which is impossible.

(d) Therefore we reject the assumption in 2a.

(3) From Bertrand's Postulate, we know that for any x, there exists a prime p such that x < p < 2x.

(4) Since p < 2x, it follows from step 2 above that every integer in the sequence x²+1, x²+2, ..., x² + p-1 is divisible by a prime v ≤ p-1 since p is greater than x.

(5) But from Theorem 4 above, we have a contradiction since if this were true then the Sequence Divisibility Problem would be solvable but by Theorem 4 above it is not solvable.

(6) So we reject our assumption in step 1.

QED