I still can't get over the fact that a 17 year old proved the same thing about pseudoprimes. It's like a Gauss-type feat, but happened in our era.

@sk8erJG95

Жыл бұрын

It is impressive, but he's not just any 17-year old. His parents are both number theorists at Bloomington who are Princeton/Harvard-educated, Michael Larsen and Ayelet Lindenstrauss. His uncle is Elon Lindenstrauss, a Fields Medalist who works on applications of Ergodic theory to number theory. His grandpa was also a mathematician that made lots of progress in functional analysis and banach spaces, Joram Lindenstrauss. He has a world of mathematical support and encouragement that most of us couldn't even dream of. I'm glad he's using it well!

@Gaeisok

Жыл бұрын

@@sk8erJG95 interesting! If I had all that support I still wouldn't be able to solve it but ut definitely must have helped him

@lgooch

Жыл бұрын

@@sk8erJG95 wow, that’s very interesting

@r.maelstrom4810

Жыл бұрын

I have looked into his paper. I can't believe it. Not only by the pure and raw computations done, but also due to the very advanced concepts (difficult to grasp for even postgraduate mathematicians) he uses joyfully. High abstract algebra, analytic number theory of very advanced level, topological and group theory... I can't believe it. It's far beyond any math olympic medallist level of math.

@tyrjilvincef9507

Жыл бұрын

@@sk8erJG95 "More mathematical support" And genes tbh.

Hey guys, Justin the editor here, it seems I left in an error meant to be cut at about 14:29 (the correct part starts at 16:47). I'm fixing it with the youtube editor, but it may take some time for the changes to go live. Sorry for the inconvenience!

@actions-speak

Жыл бұрын

Thanks for all your hard work in bringing us so much great math content!

@richardsandmeyer4431

Жыл бұрын

The original implied that square root of 2 is less than 2/3, so it was obvious that something was wrong. Thanks for correcting it.

@matematicacommarcospaulo

Жыл бұрын

Justin.... Could erase part of a video without re-upload it? If yes, teach me how

@deadfish3789

Жыл бұрын

@@richardsandmeyer4431 Does it? How? I suppose the splitting makes no sense when sqrt(2n)>2n/3, which occurs when n2048, so it isn't actually relevant. I hope the entire segment isn't being removed - while obviously wrong (the product of primes needn't be greater since some may appear more than once in (2n n), it needs replacing with something, since the board is much fuller at 16:47 than 14:29.

@ybn9861

Жыл бұрын

is there a fixed version now?

There's a big error in this proof. You've missed a whole step by using an incorrect inequality at 14:20. 2n choose n is not necessarily at most the product of primes up to 2n, because primes can have exponents bigger than 1 in the factorisation. For example, 10 choose 5 is divisible by 2^2 and 3^2. A correct proof would use Legendre's formula to say that the exponent of a prime p dividing 2n choose n is at most log_p(2n). This way, you can bound each prime *power* in the factorisation by p^(log_p(2n)) = 2n. But in the incorrect proof you gave, you simple said each prime has exponent at most 1 (which is untrue) and then simply used the very weak bound that p

@Bazzzzz93

Жыл бұрын

Yes

@Neodynium.the_permanent_magnet

Жыл бұрын

See the comment from Justin Bliss below...

@Mmmm1ch43l

Жыл бұрын

@@Neodynium.the_permanent_magnet but the comment doesn't address this issue at all?

@monishrules6580

Ай бұрын

I was confused on that

Chebyshev said it, And I say it again, There is always a prime Between n and 2n. - Erdos

@theimperator1327

Ай бұрын

A misattribution, he never said it.

At 18:15, you can do slightly better and show that 2n choose n is greater or equal to 4^n/(2n) [consider the 2n-th row of Pascal's triangle, which sums to 4^n, add separately the first and last ones and compare the central binomial to all other terms]. In the last inequality at 18:54, which will lead to contradiction, the factor 2n+1 is then replaced by 2n. To conclude, let 2n=u^2. The inequality becomes 2^((u^2)/3) 800 (instead of your 2048). Same trick as you use for the first 800 integers. [In fact u>=31 and n>480]

Erdos came up with this proof when he was 19!

@boristerbeek319

Жыл бұрын

That's quite old actually 😛

@bjornfeuerbacher5514

Жыл бұрын

Erdos got more than 121 000 000 000 000 000 years old? :O ;)

I don't get 14:03. Shouldn't a number be _greater_ or equal to the product of primes that divide it, as some of the primes can appear in the factorisation multiple times?

@matteobianchi2038

Жыл бұрын

I was thinking the same thing

@saroshadenwalla398

Жыл бұрын

So what he should have written at that point is that 2nCn is equal to the product of p^R over primes less than or equal to 2n/3 where R is the highest power of p that divides 2n. Then if p>(2n)^0.5 there is at most one power of p that divides 2nCn, and for any prime p, p^R is less than or equal to 2n. So the product of p^R over p less than or equal to 2n/3 is then split into two products of p^R for p less than or equal to (2n)^0.5 and for p>(2n)^0.5. The first product can be upper bounded by (2n)^((2n)^0.5) and the second product can be upper bounded by the product of p for p less than or equal to 2n/3.

@stanleydodds9

Жыл бұрын

Yeah, he actually made quite a big mistake here, and there's a whole other part of the proof that needs to be done to show the inequality. What you actually want to do here is use Legendre's formula to show that the exponent of p in the factorisation of 2n choose n is at most log_p(2n), but this is definitely non-trivial and what he wrote is incorrect (some primes definitely do appear multiple times). If you do this correctly though, then you can say that 2n choose n is at most the product of p to the power of this maximum exponent, log_p(2n), for all primes p in the range. Then you can see that p^(log_p(2n)) = 2n, so each of these prime power terms is at most 2n, which is what he writes next. Then you can continue following the proof.

@jaddaj5881

Жыл бұрын

I was looking in the comments because I had the same question

@pratikdash10

Жыл бұрын

Ah !! I'm not alone :D. Also, don't understand how sqrt(2)*n is less than 2n/3.

@1:00 - Since 4^n is a power of 2, and any product that includes an odd number is not a power of 2, that product will be less than 4^n if it's less than or equal to 4^n

14:20 how is the central binomial coefficient less than the product of all primes that divides it? Isn't it that 2n choose n contains all primes that divide it as a factor ad the opposite must be true?

I was looking for this proof thank you!

12:13 Justin did not have that formula on the screen. Is it in the description?

don't wory he forgot to add the exponents in the left product 1

It seems the binomial (2n,n) thing follows Kummer theorem. Great video!

8:13 Damn it Michael, making me do the leg work to follow along :) Prove that Choose(2k+1,k) =1 I see why 4 is used as the bound now... lim { (4k+6)/(k+2) } = 4

@DarinBrownSJDCMath

Жыл бұрын

Look at Pascal's triangle -- the sum of the entries in row (2k + 1) is 2^(2k + 1) = 2 * 4^k, so half the sum is 4^k.

@15:13: Maybe I'm missing something here, but what's the point of breaking the product into two parts and then upper-bounding one of the parts by the original product? Notice the term in red is exactly the left-hand side of the inequality. Doesn't the lemma give prod_{p

@deadfish3789

Жыл бұрын

The original inequality (2n n)

Totally love your white-boarding and tutorial style of teaching. It makes me yearn to go back to schoo. Gripes: this result if obviously very appealing. But thinking of the lemmas is hard. Why one earth (or how) does one figure out the right lemmas to go after? I realize theorem construction is hard, but some pointers will be useful.

21:40

For everyone who is wondering about the missing steps at 14:30, here they are. Since we know that there is no prime p>2n/3 in the product (2n,n), we have (2n,n)=\prod_{p

@deadfish3789

Жыл бұрын

I think you've overcomplicated it for the first product. All you need to point out is that obviously p^(k_p)

@digxx

Жыл бұрын

@@deadfish3789 Why is p^(k_p) a factor of 2n? Don't we just know the info about (2n,n)? I mean, p^{k_p} is, by definition, a factor of (2n,n), so how should it divide 2n in general. Or do you mean (2n)! ?

Thanks good explication

Super impressive teaching sir....from our country India we appreciate you the most over others lectures

Happy Birthday, Erdős!

I don't see how the product of the primes could ever be equal to 4^n, as for n>2, 3 would be a factor, thus it couldn't be any power of 4.

Thank you... that's was a bit of a marathon to get to the "good place to stop".

8:20 You don't need induction to prove, just realize that 2k+1 choose k = 2k+1 choose k+1 and the sum of those two

4:22 Then shouldn't you suppose that k is greater or equal to 2 so it holds everytime ?

I’m pretty sure I had watched a video where he used this postulate perhaps in a math contest but I can’t really remember it. Can anyone here send the link??

Could you proof that there is prime n^3

14:39 Isn't 2n/3 less than sqrt(2)*n? Why are we breaking up the product like this?

@bjornfeuerbacher5514

Жыл бұрын

Note the correction starting at about 16:45.

Michael, can you explain how Ramanujan did his proof and Ramanujan primes?

Given the examples and the proof could we conclude Product of primes less or equal n

@BrollyyLSSJ

Жыл бұрын

I don't see the reason really. You can easily get rid of the equals sign, since 4^n is never a primorial for n >= 2.

@MarsAnonymous

Жыл бұрын

Maybe the lemma was originally meant to be for all n >= 0? In this case, the product of all primes less then or equal to 0 is actually exactly 4^0 = 1. For n = 1, the product is strictly less than 4^n, and remains so.

@YoutubeBS

Жыл бұрын

Actually, this product is ≤4^(n-1)

8:44 Can someone explain why we needed to prove it strictly using mathematical induction? Why wasn't the first case enough?

@schweinmachtbree1013

Жыл бұрын

If you're asking why the first of the two inductive steps wasn't enough, it's because the first inductive step shows that n ⇒ n+1 for n odd while the second inductive step shows that n ⇒ n+1 for n even, so we need both to account for all values of n

it's soo cool, i wish we had more math computations in my contry(Algeria) so that we could learn if kind of tricks...even teacher in my college don't know about this postulate.i think i should go to another Country to finish my studies XD

Interesting, which is the lowest n>3 such that between n and 2n exists only one prime

This is the 3rd video I've seen attempting to explain the proof. I'm clueless as always. At 16:52, how do you show the inequality doesn't hold for n>2048. Also, does that imply there are NO primes p from 2

@thesecondderivative8967

Жыл бұрын

I think brute force... I haven't tried it yet though.

@deadfish3789

Жыл бұрын

You can't do brute force - there are infinitely many integers above 2048. However, I'm having a lot of trouble proving it. I've proven it for n=2048, and am trying to show that the sequence a_n = (2n+1)(2n)^sqrt(2n)/4^(n/3) is decreasing by showing a_n/a_{n+1} (2^5+2^3)2^6+39 > 39(2^6+1). Then 4^2048/3 = 2^(2^12/3) > 2^(13(2^6+1)) > 2^(12(2^6+1))+2^(12(2^6)) = 2^(12(2^6))(2^12+1) = (2*2048)^sqrt(2*2048)(2*2048+1) as required. The proof said that if all the prime factors are at most 2n/3, then n=2048, then there is at least one prime >2n/3. There may still be some prime factors 2

why do we break into parts the product in 14:30? Can't we just write that by lemma this product is < than 4^(2n/3)?

As others have stated, there seem to be a step missing at around 14:53 and you can sense it's missing something because when you break the product down you actually end having the left hand side lower than (2n)^{\sqrt{2n}} but you say the right hand side is lower than the original product?! you just end up with the extra (2n)^{\sqrt{2n}} factor for no reason. your inequality would end up be 4^{n/3} \leqslant 2n+1 which is false from 6 upward, a lot less work to do than to check up to 2048. The extra work probably comes from the initial inequality that doesn't hold because of prime exponents bigger than 1.

@digxx

Жыл бұрын

That's because (2n,n)

@danteruizampolini6319

Жыл бұрын

yeah exactly what i was wondering lol

So we have a hint of one of the questions in 2048 maths challenges

12:11 wheres the formula

@khoozu7802

Жыл бұрын

It is called Legendre's formula which is the exponent of prime p in n!

For every natural number n there is prime number p such that n

4:53 you say 2k is not prime, then include 2k-1 as if it were to be prime, but it might not be, eg: k=13

I always check the comments for errors in the video before watching.

14:30 - 16:48 seems to be a false version of the next part...

Can you remake this video with a correct proof? As many in the comments say there are mistakes and I’m very confused here

seems like these product less than e^n

Fascinating topic, even if others smarter than me have picked a few holes in your proof. I won't criticise you for not attempting the correct pronunciation of Bertrand since I can't do it myself. The French R is impossible.

I think it can be explain better

There's a small error in the first induction step of the lemma - for k =1, 2k is prime, so Prod(p

@saroshadenwalla398

Жыл бұрын

He already covered the case k=1 in the base case when he looked at n=2 and 3. So in the inductive step you can take k>1

@BrollyyLSSJ

Жыл бұрын

You're right, the induction hypothesis for this step should've specified k > 1, not k >= 1.

Erdös' classic proof. It's a beauty.

How would anyone come up with this proof? Number theory is hard.

@jacoboribilik3253

Жыл бұрын

Thinking constantly about it, talent, trial&error and a bunch of practice.

This proof skips too many skips for me to follow it.

Bertrand's *_postulate_* seems like a misnomer. Wikipedia says "Bertrand's postulate is a theorem" I was taught to make a large distinction between a postulate and a theorem. Wiktionary says a postulate is "Something assumed without proof as being self-evident or generally accepted." The wiki article says it started out as a *_conjecture_* in 1845 by Joseph Bertrand. So it seems it never was a "postulate." The wiki article continues: "His conjecture was completely proved by Chebyshev ... in 1852" So after it was proved, it still wasn't a "postulate." The name Bertrand's *_postulate_* seems to continue more than a century of imprecise language. Not that this channel can fix this problem that seems to be a tradition: I was surprised at 0:55 that this video would embark on a *_proof_* of the *_postulate_* .

@MyOneFiftiethOfADollar

Жыл бұрын

Words are our servants, not our masters. Except maybe in your world.

@artsmith1347

Жыл бұрын

@@MyOneFiftiethOfADollar Mathematics prides itself on precision of language, except maybe unless the name Bertrand is "more equal than others." There doesn't seem to be an "Euler's postulate." Perhaps Euler was too busy producing results to be self-aggrandizing.

@sk8erJG95

Жыл бұрын

Postulate is the correct term because of how Bertrand used it. You can find his paper "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme." on Wikipedia. He was proving another theorem and assumed there was a prime between n/2 and n-2 to do so. Hence, he used it as a postulate. A specific quote from the paper: "The lower limit that we have just given, according to M. Cauchy, for our numbers of values ​​of a function, is not higher than one can find. Except for four-letter functions that can have only two values, the indices of an n-letter function can never be both greater than 2 and less than n. To prove this proposition, I will assume as a fact that, for any number n greater than 6, there always exists a prime number, at least, between n-2 and n/2. this proposition is true for all numbers less than 6 million, and there is every reason to believe that it is true generally" Hence, when Chebyshev proved this a few years later, he described it as "Bertrand's Postulate".

@artsmith1347

Жыл бұрын

@@sk8erJG95 Thank you for the good info. My conclusion is that we can blame Chebyshev -- and those who didn't dare to to correct Chebyshev's mischaracterization -- for the sloppy language. Though no one knew it at the time, it was to become a theorem. " 'I will assume as a fact' --for my present purpose" was properly stated to be an assumption.

@DarinBrownSJDCMath

Жыл бұрын

Culture and tradition sometimes trump precision.

asnwer=2p

Isn't √2·n > n > ⅔n though? @14:55?

@bjornfeuerbacher5514

Жыл бұрын

Yes, that part was false. The correction starts at about 16:45.

@GirishManjunathMusic

Жыл бұрын

@@bjornfeuerbacher5514 yea I noticed.

Between 4 and 8, there are two: 5 and 7, but then between 5 and 10 there is only one: 7. When is last time there is only one prime between 𝑛 and 2𝑛, or are there infinitely many?