ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

A Proposed Proof for Legendre's Conjecture

Updated on May 16, 2013

Disclaimer

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 x2 and (x+1)2. 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.

Overview of Argument

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.

Sequence Divisibility Problem

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


n-Slot Form

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>


Ascending Prime Order Form

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.

Properties of Ascending Prime Order Form

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

Legendre's Conjecture

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 x2 and (x+1)2

Proof:

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

(2) It follows then that every integer in the sequence x2 + 1, x2 + 2, ..., x2 + 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) = x2 + 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 x2+1, x2+2, ..., x2 + 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

Comments

    0 of 8192 characters used
    Post Comment

    • profile image

      S. R. 

      4 years ago

      You should sent the arguments of your problem to http://www.math.stackexchange.com for a solution.

    • tussin profile image

      I'M BANNED Y'ALL!!!!!!!!!! 

      5 years ago from Behind You

      This is very cool Larry and I like your elegant approach. Regarding your disclaimer, I think I found another counterexample less than n=22. If you take n=12, you have n+1 = 13 which is prime, but you can find a solution to the sequence divisibility problem with the sequence

      2, 5,2, 3, 2, 7, 2, 11, 2, 3 ,2, 5

      This corresponds to the 12 consecutive integers 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125.

      Hope you work out the kinks!

    • larryfreeman profile imageAUTHOR

      larryfreeman 

      7 years ago from Fremont, CA

      Math hurts even more when you make a mistake...that you find... after you publish it.

    • Ren Chin profile image

      Ren Chin 

      7 years ago

      math hurts

    • larryfreeman profile imageAUTHOR

      larryfreeman 

      7 years ago from Fremont, CA

      I didn't realize that you had an interest in math.

      I figured that I would write up on HubPages before I sent it out for review. The responses were very positive even if they found the flaw pretty quick. :-)

      I am working on a revised argument now.

    • Simone Smith profile image

      Simone Haruko Smith 

      7 years ago from San Francisco

      Wow, I'm pretty terrible with proofs, but this made for an interesting read. I appreciate the way you've broken down and explained your profess. Very cool!

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, hubpages.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://hubpages.com/privacy-policy#gdpr

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)