Legendre's Conjecture is PROBABLY TRUE, and here's why
Vložit
- čas přidán 7. 09. 2024
- don't write in the newspapers that I said that this is a proof of legendres conjecture because it's NOT a proof of legendres conjecture. It's not. besides, what if the proof of legendres conjecture is the friends we made along the way?
🌟Support the channel🌟
Patreon: / michaelpennmath
Merch: teespring.com/...
My amazon shop: www.amazon.com...
🟢 Discord: / discord
🌟my other channels🌟
mathmajor: / @mathmajor
pennpav podcast: / @thepennpavpodcast7878
🌟My Links🌟
Personal Website: www.michael-pen...
Instagram: / melp2718
Twitter: / michaelpennmath
Randolph College Math: www.randolphcol...
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
🌟How I make Thumbnails🌟
Canva: partner.canva....
Color Pallet: coolors.co/?re...
🌟Suggest a problem🌟
forms.gle/ea7P...
2:27 I haven't laughed out loud to a video in a long time. This was priceless.
I'm glad you liked it. I had A LOT of fun making it lol
-Stephanie
MP Editor
it was funny but no so unexpected... he didn't say "a good time to stop". 😁
I gotta agree... caught me off guard and made me laugh out loud and my daughters were wondering what happened...!
Yep, got a big "What?!" out of me!
It's such a joy to see these comments lol
-Stephanie
MP Editor
Me, always a fan of your thumbnails!
Thank you! That means a lot coming from you. Huge fan of yours. Michael speaks highly of you. Thanks for all your awesome content!
-Stephanie
MP Editor
Michael Penn seems to have struck the right balance between mathematical rigour and entertainment.
Also the content on the MathMajor channel is invaluable.
Much appreciated.
All of it.
Not only is the conjecture that there is at least one prime p between n² and (n+1)² almost certainly true, but the stronger statement that there are at least ⌊√n⌋ primes between n² and (n+1)² is also apparently almost certainly true. (E.g. n=4, there are at least 2 primes between 16 and 25. n=100, there are at least 10 primes between 100² and 101², etc). Which just goes to show how frustrating it is we can't even seem to formally prove there is at least one prime in that range!
When you say almost certain. Do you mean in the probabilistic sense (i.e. probability 1 but not guaranteed), or in the same sense as this video, or are those 2 the same
@@fahrenheit2101 It's basically the same argument as in the video, except that instead of just 1 you're using that ⌊√n⌋ is always less than (n+1)² /ln((n+1)² - n² /ln(n² ) for n>2. And experimentally you can check the number of primes in that gap is greater than ⌊√n⌋ for basically any n you care to calculate.
By putting the x inside the logarithm at 12:10 you actually get the limit for 1/e, which is kinda cool. (and perfectly matches the -1 result you get)
The descriptions get better with each video
12:55 Shouldn't there be a (x+1)² in the denominator when taking the derivative of the rational function inside the natural log? It doesn't change the result of the limit though.
Yes.
It seems really odd to me that n
consider bertrands postulate for n = k^2, i.e. there is some prime between k^2 and 2k^2.
since (k+1)^2 < 2k^2 for k>2, legendres conjecture is more restrictive.
another way to think about it is that Bertrand's postulate is equivalent to the statement:
"the ratio of consecutive primes is always less than 2"
But the ratio of consecutive squares drops below 2 very quickly.
4/1 > 2
9/4 > 2
16/9 < 2
25/16 < 2
...
The n
what about this: try to calculate the "chance" p(n) that between any consecutive squares n^2, (n+1)^2 is no prime, based on the prime number theorem.
the chance for a number x to not be prime is
((lnx)^2 - lnx + 1) / (lnx)^2
or approximately for large x
1-1/lnx
x does not vary much between to squares. Which leads to the approximation
p(n) ~ (1-1/ln(n))^(2n)
p(n) ~ exp(-2n/ln(n))
And the chance to always get at least one prime is
P = Product(1-p(n)) for n from N to inf. Where N is the smallest number we have not checked.
P ~ 1 - sum(exp(-2n/ln(n)))
setting N=1000 gives ~1 - 10^-125
and N=10 gives 0.99956
Since it is tested up to even much higher numbers than 100, the chance that the conjecture will fail is way smaller than 10^-125. Based on this rough estimate.
On Legendre's conjecture as you write it: There is no prime p with 1^2 < p < (1 + 1)^2, so n should satisfy n > 1 for this to work.
I've spent too much time around CS folks... "oh, since we're only looking at n large, ln(n+1) and ln(n) are pretty much the same, the n² cancels out and we're left with O(n/ln(n)) which grows without bound because n grows faster than ln(n) and yes that should be Theta(n/ln(n)) but this isn't freshman year complexity theory."
The caution is definitely warranted. The same PNT heuristic would imply there is a prime between n < p < n + ln(n) ^ (1+ε) for any ε > 0 however even for ε = 1/2 fails around the larger prime gaps for e.g. p = 887, 1357201, 436273009, 42652618343. Something more than the PNT is needed here.
The editing gets better and better in each video!
Hi Michael. I am so glad that I found your channels. Thank you so much for all your work!
I get that τ(n) = ( n + 1 )**2 - n**2 ≈ л(n): or the number of primes between successive squares is roughly the number of primes up to N. I also find prime pairs turning up between successive squares.
2:29 this caught me off guard 😂
You know it wasn't the real ending because he didn't say it was a good place to stop.
@@Sgrunterundt yeah but it's still funny nontheless
Shhh don’t give it away. ;)
-Stephanie
MP Editor
We don't want "n-action", we want action
I was thinking you will show that the series sum 1/p diverges, while series sum 1/n^2 converges. This implies that there are much more primes than squares, but again it tells virtually nothing about distribution of primes among specific integers
how do you prove that the sum 1/p diverges?
@@taraszablotskyi1479 en.m.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
@@taraszablotskyi1479
-You can use the integral test: because the integral -*-∫[1,∞] 1/x dx-*- diverges, the sum -*-Σ[n=1,∞] 1/n-*- also diverges. If you want to learn more search for “harmonic series” or “integral test”- oops wait p means prime not natural number duh
Thought he was going to prove it at the end. But then realized the obvious.
What a chad move it would be to prove it on a CZcams video.
and casually like this lol
-Stephanie
MP Editor
“Know a mentat by his red stained lips”-or his producer’s love of maxing out the saturation.
This is not good enough. The expected number of primes between n^2 and (n+1)^2 is (2 n /log(n)), but you only need ONE counterexample, so you need to know the variance, the distribution, and the probability of being out on the tail. Assuming it's Gaussian, you get your result (and it is Gaussian). But you need to do that. The algebraic manipulations in this video aren't useful or important, just write down "The density of primes is 1/ln(n), so there are 2n/ln(n) primes between n^2 and (n+1)^2 for large n, on average.
Error perceived at 12:40 when applying the quotient rule. The denominator should be (x+1)^2 , instead of x^2, IMHO .
I'd only conclude that the conjecture is good if the probability for each n to satisfy the conjecture, assuming a Poisson distribution, converged to 1 fast enough for the product of all those probabilities to remain high given the numbers we've already checked
14:24
You are too fast
"two times ten to the nine" is a perfectly normal way to spell "two billion" right?
in metric or imperial ?
yeah
Are you referring to the part of the video at 3 times ten to the one minutes?
it's a physicist's way
@@colinbrash The video is only one point five times ten to the one minutes, how did you get to three times ten to the one minutes?
Is 2 the smallest power a that we conjecture n^a < p < (n+1)^a holds?
For sufficiently large n, I would suspect it holds for all a>1, right?
The largest prime gap up to n is expected to be of order ( log n)^2. This would imply that any a>1 works for n large enough. It is known that a=3 works for large enough n.
Ewing's Conjecture: For any two functions f and g, someone has conjectured that for any natural number n there is a prime between f(n) and g(n).
Since (n+1)^2-n^2 = 2n+1, a more general conjecture would be whether there is a prime p st. n < p < 3n+1 for all n. Does that not hold? I mean, is there a counterexample to that.
This is true, bertrand postulate says that there exists a prime p such that n
@@Lucashallal Doesn't bertrand postulate imply Legendre's Conjecture?
What you concluded in your comment is that legendre conjecture is equivalent to the conjecture that there exists a prime such that x
And with x=n^2 it is harder to solve than with x=n
@@Lucashallal Oh yea, you are right. Basically, in the Legendre's conjecture, the window size is sqrt of the number. So my generalization of the conjecture should have been "for all n there is a prime p st n
Stephanie having a lot of fun
13:54 Wouldn't it be enough to state that the blue box is > 0 and thus will not trend towards -∞ ?
Your videos are awesome :)
Lol :) 2:30 i really thought its a quick up-drill fools video :)
Legendre is one of those names that are just really fun to say
Does this prove there are at most finitely many counterexamples?
Why do you prove the number of values goes to infinity, instead of just proving it's always greater than 1? Is it because taking a limit to infinity is easier, and skips the values where the prime counting function is less accurate? Or is because having an infinite number of expected primes gives a 0% chance of there not being a prime?
Neither, but closer to the latter. This expected value stuff is all approximate and doesnt *prove* anything. It just gives a good idea of what to expect. If you expect 1 prime in that range, then thats not the same as saying that there will always be at least or exactly 1 in the range. Hell if the limit was just 2 I wouldnt be confident at all. Its not a lower bound - just a rough estimate. However if it tends to infinity, then the more and more we check, the less and less likely we are to find an exception, which is far more comforting.
For conjectures that have ultimately been disproven, what’s the biggest number that confirmed the conjecture? In other words, does the fact that Legendre’s conjecture been confirmed up to 2*10^9 give us any confidence that it’s true?
Ultimately, no example can give you confidence in the result. Just like this "expected number" proof, it's a heuristic. The fact that some false conjectures hold for 10^10 examples has no bearing on the truth of other conjectures that have been checked up to 10^10. No matter what, checking examples will always be an infinitesimal proportion of ALL values, whether you check 10 or 10^100.
Mertens' conjecture on Mobius function has been disproven but no explicit counterexample is known.
The Polya "conjecture" (no longer a conjecture) was originally disproven with a counterexample that was not found exactly, but estimated to be of the order 1.8 * 10^361. A smaller counterexample was later found of 906,150,257.
@@williamrutherford553 "Ultimately, no example can give you confidence in the result."
I don't agree. I think examples can give you *some* confidence though certainly never *full* confidence.
This isn't really a meaningful measure. For example, one can generate (admittedly, artificial) conjectures of the form "every root of this polynomial is prime", where the roots of the polynomial are the first n primes, plus some larger composite number. Each of these conjectures is false, but would seem true if you only checked numbers up to the nth prime, which can be made arbitrarily large.
Has there been any progress on the Conjecture lately? Is it likely it will be proven?
Don’t see the problem. If Bertrand I correct then
n
I'm not sure that I trust an argument based on an expectation value when there's an infinite number of trials.
It seems to me that such an asymptotic argument only suggests that the conjecture is true for almost all n. There could easily be a finite number of exceptions.
2*10^9 doesn't sound that much tbh... Indeed it sounds like a pretty small number. That made me curious to set up some code to see, how long it actually takes to run up to this number.
I'm guessing he means n = 2x10^9, so n^2 would be on the order of 10^18. Which is an accomplishment. (EDIT: I accidentally had 81. I need more sleep)
@@soranuareane 18, not 81
@@felixmoore6781 Thank you. Corrected.
x sure is continuous-looking, I gotta agree.
You’re not fooling anyone with a fake video ending without saying “and that’s a good place to stop” 😂
Is the title a reference to Hbomberguy's video titles or just a coincidence?
nailed it. yes.
-Stephanie
MP Editor
2*10^9 isn't really a large number, why is it so low for this conjecture
Isnt it? I thought that was in and around the limits of reaonable computing power.
Can we make a conclusion from the limit shown in the video, that there is a number N such that for all n > N the conjecture is true?
Great explanation of why this conjecture is likely true. Why can’t it be considered as a proof? It’s already verified for numbers upto billions and with this argument it’s valid for large n.
There very well could be some counter example for numbers we've not checked. You have to be able to show it conclusively for all n.
-Stephanie
MP Editor
The biggest number ever conceived of is small because infinite is just that much bigger. You can never test enough cases to make something true for all natural numbers.
I remember hearing this fact put to me this way: "The largest possible number you can think of is as far from infinity as is the number 1". My mind melted. Granted I was fresh into college when I heard it put this way.
-Stephanie
MP Editor
This argument does not guarantee that it's valid for very large n, it suggests that it is. It also doesn't specify the size of this "very large n", which could be very far away from 2*10⁹, making it possible for there to be a counterexample in the middle.
As a very trivial demonstration, consider the conjecture “All natural numbers are less than 10^100”. Obviously it’s very easy to disprove, but it’s also clearly true for nearly a googol values which is much more than the 2 billion in Legendre’s conjecture.
Some very inefficient python code for finding these primes :)
n = int(input('Please write your number: '))
print('Primes in between n^2 and (n+1)^2 are: ')
prime_count = 0
for x in range(n**2+1, (n+1)**2):
isprime = True
for b in range(2, x):
if x % b == 0:
isprime = False
else:
pass
if isprime:
prime_count += 1
print(x)
print('The total number of primes is:', prime_count)
Look into the sieve of Eratosthenes, very efficient and easy to implement
@@frankjohnson123 Also memory-intensive for large n though...
Some easy optimisations to help you out.
Once you confirm that 2 and 3 are not factors, you can have two loops, one that starts from 5 and increments by 6, and one that starts from 7 and increments by 6. This is because you only need to check prime factors, and all primes are either 2, 3 or 6x +/- 1. This will reduce the speed to about 1/3 of it's current.
Also, once you hit the isprime = False line, you can then break out. Further iterations will not do anything. The amount that this reduces it by ia lot harder to guess.
@@landsgevaer it’s only O(n) in memory before optimizations, very worth it until you start getting into the billions. If you’re pushing it that far there are some variants which are < sqrt(n).
@@frankjohnson123 The sieve is great to determine lots of primes, but is inefficient if you only want to determine the primality of one number. That is because the sieve essentially is a double nested loop, whereas you only need a single one.
The sqrt(n) is indeed easy to achieve, just stop checking for divisors at sqrt(n).
Your joke very 🥲, but i like :)
excellent
Lagendre congecture for any gender
Is Legrands conjecture proved?
If it were, it would not be a conjecture, it would be a theorem.
Apart from the fact that his name is Legendre, if you asked this question you understood literally zero of this video.
Sir can i contact you for this, I have something to share
My favorite conjecture on this subject is
en.wikipedia.org/wiki/Firoozbakht%27s_conjecture
This came up in some research I was doing, before I even knew it was a named conjecture.
(p(n+1))^n < (p(n))^(n+1) for all n
It is true because Not Legendre's is false: ¿there exists an n at N so that for every p at P, p=(n+1)^2?
¿What n? ¿n=1? No, because p>=(1+1)^2 =4 for any p at P excepts p=2 and p=3. And also 2>1^2 and 3>1^2.
¿Any other bigger n? Sure not... there are indeed more exceptions.
So not n: Not Legendre's is false, and it stays that Legendre's is True.