Generalized Legendre Conjecture (original) (raw)

Generalized Legendre Conjecture:

Is there a prime between _n_s and (n+1)s for s < 2?

Equipped with the functions isPrime(n) and nextPrime(n), we can now easily test hypotheses and conjectures about primes. (A conjecture is a statement we believe to be true but have not proved; when someone eventually proves a conjecture, it becomes a theorem.) Here are some interesting conjectures – all of them apparently true:[Click to show or hide discussion.]
Legendre's conjecture. For each integer n > _N_2 = 0, _there is a prime p between n_2 and (n+1)2.
Here the prime p may be 2, 3, 5, 7,..., i.e. p may be any prime. As far as we know, prime gaps are never big enough to fully contain the interval [_n_2, (n+1)2], so Legendre's conjecture holds, at least up to 18-digit primes. We can safely say so because _the largest gap_between any primes up to 18 digits is only 1442; this gap happens between the primes 804212830686677669 and 804212830686679111. The interval [_n_2, (n+1)2] is wider than 1442 when n > 720, so Legendre's conjecture is not in danger.) Adrien-Marie Legendre was right 200 years ago – but no one has been able to prove this conjecture, as of 2010.

The _n_5/3 conjecture. For each integer n > _N_5/3 = 0, _there is a prime p between n_5/3 and (n+1)5/3.
Here, again, p might be any prime; no prime gaps are big enough to fully contain the interval [_n_5/3, (n+1)5/3]. Exhaustive checks for the first million values of n do not yield counterexamples. Any prime gaps become relatively smaller and smaller, compared to the intervals [_n_5/3, (n+1)5/3] for large n. Therefore, the lower bound for this conjecture is _N_5/3 = 0; the _n_5/3 conjecture appears to be true for all positive integers n. We can consider it verified up to 18-digit primes, or n up to 1012.

The _n_8/5 conjecture. For each integer n > _N_8/5 = 0, _there is a prime p between n_8/5 and (n+1)8/5.
Here, once again, p may be any prime. Exhaustive checks for the first million values of n reveal no counterexamples, while any prime gaps become relatively smaller, compared to the intervals [_n_8/5, (n+1)8/5] for large n. The _n_8/5 conjecture appears to be true for all positive integers n. We can consider it verified up to 18-digit primes, or for n up to 1012.

The _n_3/2 conjecture. For each integer n > _N_3/2 = 1051, _there is a prime p between n_3/2 and (n+1)3/2.
Here, p turns out to be at least 34123. Below that, the intervals [n_3/2, (n+1)3/2] are too small – so small that_prime gaps are occasionally bigger than some intervals [_n_3/2, (n+1)3/2]. For example, the prime gap [31,37] contains the entire interval [103/2, 113/2],the prime gap [89,97] contains the interval [203/2, 213/2], and the prime gap [34061,34123] contains [10513/2, 10523/2].The latter prime gap gives us the greatest counterexample _N_3/2 = 1051 – exhaustive checks for each n from one to ten million reveal no other counterexamples, while any prime gaps become relatively smaller, compared to the intervals [_n_3/2, (n+1)3/2] for large n. Therefore, based on our computational verification – combined with the knowledge of maximal prime gaps up to 18-digit primes – the _n_3/2 conjecture is apparently true for n > _N_3/2 = 1051. We can consider it verified up to 18-digit primes, or for n up to 1012.

The _n_4/3 conjecture. For each integer n > _N_4/3 = 6776941, _there is a prime p between n_4/3 and (n+1)4/3.
Here the prime p is at least 1282463543. Below that, prime gaps are occasionally bigger than some intervals [_n_4/3, (n+1)4/3].For example, the prime gap [7, 11] contains the interval [54/3, 64/3],the prime gap [555142061, 555142307] contains the interval [36166224/3, 36166234/3], and the prime gap [1282463269, 1282463543] contains the interval [67769414/3, 67769424/3].The latter appears to be the largest counterexample. (This has been checked by a computation for each n up to 57000000, as well as a set of known large prime gaps after that. Combining this result with the existing data on maximal prime gaps up to 18-digit primes, we can consider this conjecture to be verified up to at least 18-digit primes.)

The _n_5/4 conjecture. For each integer n > _N_5/4 ≥ 50904310155, _there is a prime p between n_5/4 and (n+1)5/4.
Here p needs to be at least 24179270588903. Below that, there are many counterexamples, e.g. the prime gap [7, 11] contains the entire interval [55/4, 65/4],the prime gap [13, 17] contains the entire interval [85/4, 95/4], andthe prime gap [24179270588173, 24179270588903] contains the interval [509043101555/4,509043101565/4]. The latter appears to be the largest counterexample. (Is it in fact the largest? That still needs additional verification; hence the ≥ sign in this conjecture.)

The _n_6/5 conjecture. For each integer n > _N_6/5 ≥ 833954771945899, _there is a prime p between n_6/5 and (n+1)6/5.
In this conjecture, the prime p must be at least 804212830686679111. Below that, there are many counterexamples, e.g. the prime gap [5, 7] contains the interval [46/5, 56/5],the prime gap [7, 11] contains the interval [66/5, 76/5],the prime gap [8775815387922523, 8775815387923457] contains the interval [193229263642546/5, 193229263642556/5],and the prime gap [804212830686677669, 804212830686679111] contains the interval [8339547719458996/5, 8339547719459006/5].The latter is the largest counterexample known to the author, as of May 2011. (Is it in fact the largest? That still needs additional verification; hence the ≥ sign in this conjecture.) To test the _n_6/5 conjecture further, we would need to work with at least 19-digit primes. JavaScript variables cannot store odd integers over 253 = 9007199254740992, so the _n_6/5 conjecture is not easily testable without some library like BigInt.js supporting larger numbers. Thus, JavaScript is less suitable for such tests than languages with better support of extended precision arithmetic.

The above statements are verifiable up to at least 18-digit primes. (The existing knowledge of maximum prime gaps up to low 19-digit numberssimplifies the verification; beyond that, the verification becomes less practical.) These statements suggest the following generalization:
The generalized Legendre conjecture.
(A) There exist infinitely many pairs (s, Ns), 1 < _s_ ≤ 2, _such that for each integer_ _n_ > _N_s _there is a prime between n_s and (n+1)s. (Weak formulation.)(B) For each s > 1, there exists an integer Ns such that for each integer n > _N_s _there is a prime between n_s and (n+1)s. (Strong formulation.)
Discussion. Some of the pairs (s, Ns) are the above special cases:(2,0), (5/3, 0), (8/5, 0), (3/2, 1051), (4/3, 6776941). Ns is a function of s; namely, Ns denotes the greatest counterexample for the _n_s conjecture: if we proceed from small to large n, the last interval [ns, (n+1)_s_] containing no primes happens to occur at n = Ns; and for each n > Ns there is at least one prime between ns and (n+1)s. We readily see that s > 1 is indeed a necessary condition. (A short explanation for a younger reader: should we have s ≤ 1, our intervals [ns, (n+1)s_] would be_way too narrow to contain a prime – or any integer at all, in most cases). Moreover, is it plausible that s > _s_min > 1 should also be satisfied, with a certain lower bound _s_min> 1, in order for Ns to exist? If so, part (A) would still be true, but part (B) would be invalidated for some s very close to 1.

Questions to explore further:
(1) Is Ns a monotonic function of s? (No, it is not – there are counterexamples.)
(2) What the lower bound _s_min might be, for the _n_s conjecture to still make sense? (A tongue-in-cheek guess: less than 1.1. A more serious answer: s > 1 is likely enough; no additional _s_min is needed. Here is a hint.)
(3) How is the _n_s conjecture related to other known conjectures and theorems about the distribution of primes? (The _n_s conjecture follows from the Cramer-Granville conjecture when n is large enough.)

Here is a partial computational verification of special cases of the generalized Legendre conjecture.

Copyright© 2011, Alexei Kourbatov, JavaScripter.net.