I already made a community post about it, but I just realised that this video has a HUGE error!!! Luckily not in the material itself, but I claim at 20:56, that the fact that half of the numbers in the number system Zp* are squares, _eventually_ helped 3 researchers win the Gödel prize. Of course this is a massive simplification - that alone doesn't win you a Gödel prize - but I just wanted to get across how knowing group theory can benefit you. Well it turns out their algorithm does not depend on that at all!!! I tried to find out what made me think that and it turns out the book I used as reference (Computational Complexity by Arora & Barak) has an error!!! cs.stackexchange.com/questions/140727/is-quadratic-nonresiduosity-in-textbfnp I also just genuinely and completely misunderstood the prize winning paper. I thought the point was that a certain probability generated from coin tosses was being preserved with this fact. That doesn't make sense at all in hindsight. My toy simplification is now not a simplification anymore but actually misinformation. So my question to you is: What is the best action now? Take the video down and try to come up with a new application? This will take forever. Make a pinned comment but keep the video up? My video makes vixra look smart now. I'd love to know your opinions though before I do anything more stupid.
Pinned comment while you make the fix, hide this video when the fix is completed, and link to it in the description of the new vid. That's what I'd do Or if you wanna move onto new content just leave the pinned comment up and the mistake in, we're thankful for the time and effort you put in and life's too short to keep going back, art is never finished
It’s a small part of the video, leave it up and perhaps add another comment also in the timeline of the video so it’s easier to spot without going to the comment section
I mean if you feel so bad about it maybe just put a small edit on the video stating its misinformation. Pinned comment is still best in my opinion. I want that third vid asap 😅
It's not a big part of the video, even if it is misinformation, so a pinned comment should suffice. That being said, it would be nice if TH-cam had a feature to allow for annotations at that portion of the video-something like ""I made a mistake! Please see the pinned comment for more information." but TH-cam doesn't have annotations anymore. If there's a similar feature, though, it could work just as well.
not everyone looks here, id say change the video to atleast have some big red text saying that this is a mistake to make sure nobody internalizes false info.
Me too.. first time i watched his videos i was in my first year of college jobless and gf less. Now I'm about to finish my degree with both.. took such a long time. Day by day nothing changes but when you look back...
Hey everyone, I had surgery and I'd like to talk about it. 3 years ago I broke my collarbone. I went to the hospital and they fixed it with a metal plate. They then told me that it would take 2 years to heal and, if I notice a bump, that this is the plate and that I shouldn't worry about it. Well 2 years later I had it taken out again, but I still had that bump. I asked them about it and my contact person said that the people from 2 years ago probably forgot to sow back together my ligaments. It turns out that if you rip the ligaments attached to your collarbone, they stop holding it down and it starts to stick out under your skin and suddenly you can do things like touch its underside. Shocks against it suddenly become very painful. WTF, I was wondering why this "metal plate" feels so awful. I couldn't imagine to live with that. I eventually found a new hospital where they proposed to do a ligament transplant. The exact procedure is explained here: www.schulthess-klinik.ch/de/schulterchirurgie-und-ellbogenchirurgie/behandlung/verletzung-des-schultereckgelenks It's in German but at least there is a video. Actually I got only one hole drilled unlike the two in the video. I did the procedure and it took a year of healing and physiotherapy afterwards but my collarbone amazingly is now at its old place. It's not as stable as before and I can still make it somewhat stick out with certain movements like shrugging but by and large I'm amazed with the result. Did any of you tear your collarbone ligament? What operation did you do? Are you happy with the result? Did you encounter any problems? The whole ordeal was pretty exhausting for me, so I would love to hear your story. But now you know why it took so long for me to upload the next video.
yo. I'm really glad to know you're ok. I was not at all aware of this surgery, but I was worried nonetheless. thank you so much for showing up and dropping another amazing video. it really means the world that you're healthy and doing more content. I also hope you enjoyed making the video as much as we're all gonna enjoy watching it. happy holidays!
Mate you probably won't even know me, the same here. But I'm glad you've got through that tough time. It's alright, just 2 years. I'm more happy with you continuing this TH-cam after everything you've gone through. Hope your doing well mate, get better soon! Lots of love.
i was gonna meme about how you took 2 years to drop another video, thank god i read this first hope you get even better and dont ever need to worry about your collarbone ever again
A lot of these comments complain about the timeliness of your video. I just wanted to say I'm glad you finished it, I know these projects are hard. Watching this actually made me notice a connection in one of the projects I've been working on. I'm looking forward to your next video.
Can you believe that I only watched Ep. 1 yesterday?? I found from the comments that it was from 2 years ago. I checked your channel page and didn't find the next part. I didn't give too much thought about the time of next upload. When I first saw this video in my recommandations, I couldn't recognize the thumbnail. According to my memory, I didn't remember seeing it on your channel page. I checked the upload time, and then I realized 😃that this video is new! What a surprise 😄!! I really enjoyed the previous video. You introduced the topic so well! 🤠 Your explanation was so clear and intuitive. You have justified the choice of terms like "neutral" and "inverse" as well as the choice of notations like a^-1. The animations were so smooth and also helped in building the intuition. Even though I am already familiar with group theory from the course I had and also from other videos, I wanted to watch, because I like Math. Your video is definitely different from other ones I have seen. It has a special and unique vibe to it. I am eager 😄 to watch this episode . I am sure it will be astonishing like the previous one, and who knows, perhaps even more. I only came to watch group theory. But I may stay to check out the algorithm to solve the graph theory problem .. I honestly don't quite remember what it was 😅 Let me check the previous video title.. . . Did you change the title and the thumbnail?? Well, maybe this is better. Anyway, I am glad that you kept the icosahedron. Its shape and colors are satisfying 😌to look at. So, this is it. If you reached this point, THANK YOU! 😊 P.S. : This comment 😅got longer than what I planned to.
Glad to see you back as well as hear about your successful recovery! Thanks for the new video and hopefully there are many more to come because your topics and presentation are excellent. Best wishes!
FINALLY. Dropped a banger after 2 whole years. I would watch the multiplication and group theory time and time again always understanding the topic a bit more and hoping when the next one would drop. Thank you so much! Hope this video gets the views it deserves.. a lot of us waited for it
How funny! I was just watching your older videos yesterday, and this gem of a video dropped! I hope you feel better, and keep making videos for this series. As a computer science and Math Student who has taken an introductory Abstract Algebra course, there was still stuff that I learned from this video.
i literally followed a whole group theory and abstract algebra course because of your first video and i can't wait to see the continuation of this series
Thank you Nemean for taking the time and effort to produce such an informative and high quality video ! These 35 minutes of gold made me understand way more than an entire course on this topic at uni. You're very talented at explaining, and I wish I had this video when I was a student. I am pretty sure your work has already done more good in this world than you can imagine, and it will keep doing as more people will see it. If you ever have doubts on wether it is worth continuing to work on these videos, trust me, your skills and efforts have the power to better so many lives and inspire so many people. Legend.
I still remember episode 1 being the first video about group theory I ever saw, and I still remember where I watched it (I was on vacation at the time). Really glad that you continued the series, even if this is now a bit below my level of understanding. And E=m(a²+b²) made me laugh
22:29 For the example on screen, the pattern is powers of two! If _n_ is in _Z_10_ and _m_ in _Z*_11_ then the isomorphism is _[ 2^n mod 11 ] ←→ m._ This makes sense when you think about it, it's just the exponential map example you gave in the video. I think I have a proof, but I'm not an expert in modular arithmetic or group theory so do correct me if I'm wrong! Consider the additive group _Z_N_ and the multiplicative group _Z*_M_ . We'll refer to elements of _Z_N_ with _"n"_ and _Z*_M_ with _"m"_ . Now we'll try to construct an isomorphism with the the exponential with integer base _a_ . We say _m0 = a^n0_ , _m1 = a^n1_ , etc. This gives the following: _m0 · m1 = a^n0 · a^n1 = a^(n0 + n1)_ We define _n0 + n1 =: n2 (mod N)_ and thus, by consistency, we have _m0 · m1 = m2 (mod M)_ . Now suppose _n0 = 1_ and _n1 = N_ . By definition of _Z_N_ , we have _1 + N = 0 (mod N)_ . Then: _a^1 · a^N = a^0 (mod M)_ ⇒ _a · a^N = 1 (mod M)_ Thus, we find that _a^N = a^-1 (mod M)_ . Taking the logarithm on both sides and simplifying: _N = -1 (mod M)_ ⇒ _N + 1 = 0 (mod M)_ Since _M = 0 (mod M)_ by definition, we hence have _N + 1 = M_ . For the isomorphism to work, we also need to ensure that there are enough elements in _Z*_M_ to map to _Z_N_ and vice-versa. Since _Z*_ always excludes _0_ we know that _Z*_M_ can contain at most _M - 1 = N_ elements. We require it to contain _N_ elements, so it must contain the maximum possible. This only happens when _M_ is prime, so that adds an additional primality requirement. Hence we have an isomorphism _Z*_p =~ Z_(p-1)_ via exponentiation with any integer base _a_ . Q·E·D? :D edits: - fixed formatting issues. - mentioned that the base should be an integer. - added the primality requirement for M.
You say roughly in the middle that 1 + N = 0 (mod N), but it actually is = 1. This will eventually be a problem, because you will get N = M (instead of N + 1 = M). Since in general |Z_N| = N and |Z_M*| < M, together with N = M this means that Z_N has more elements than Z_M*. Thus they cannot be isomorphic, because isomorphic groups always have the same number of elements. Respectable try though.
Super cool. As a computer scientist who studied category theory but never really group theory or number theory, I kept spotting hidden category theory in this (e.g. the graphs at 34:35). I'd love to see a followup where you generalise this stuff to category theory!
22:42 the equivalence seems to be log log2(1) = 0 log2(2) = 1 log2(3) = log2(3 + 11 * 23) = log2(256) = 8 log2(4) = 2 log2(5) = log2(5 + 11) = log2(16) = 4 log2(6) = log2(6 + 11 * 46) = log2(512) = 9 log2(7) = log2(7 + 11 * 11) = log2(128) = 7 log2(8) = 3 log2(9) = log2(9 + 11 * 5) = log2(64) = 8 log2(10) = log2(10 + 11 * 2) = log2(32) = 5 the choice of 2 here is arbitrary, and could actually be replaced by any number the inverse obviously works, and this ties back into a particularly useful rewording of fermat's little theorem: a^b mod M = (a mod M)^(b mod phi(M)), where phi(n) = euler's totient function phi(p) where p is a prime = p-1, hence the equivalence holds
The graph isomorphism problem is really fascinating. Are you going to explain McKay's nauty algorithm for it in the next video? The end of this video seemed like you were hinting at that. I'm incredibly hyped. I tried to wrap my head around this algorithm without much group theory background and it's so hard to follow. I needed this stuff for my master thesis, in the end I was very happy I could just use their nauty tool in my program rather than having to implement this algorithm somehow on my own. I was using this for canonicalization of subgraphs in a challenging induced subgraph identification problem. It was very satisfying to piece it together and unwrap the necessary adjustments to "undo" all the morphisms, however in the end the practical benefit of this on random graphs turned out to be nothing. I knew that random graphs after some size almost never have nontrivial automorphisms, but somehow I still hoped that some of the induced subgraphs of the same original (random) graph would have occasionally, and that weeding out such isomorphic duplicates from the search space would boost the performance of my general algorithm. But it turns out this just isn't the case, and even though the computational expense of computing the automorphism groups (and thus a canonical form) of all the searched induced subgraphs was small, the savings in search space reduction that resulted from it is unfortunately even smaller. That's on random graphs however. On graphs with nontrivial automorphism group, applying this reduction is well worth it, though it would probably suffice to break the initial symmetries rather than check continuously throughout the search. For some real world applications, one might expect a certain degree of self-similarity in specific cases that derives from the application, that would make isomorphism reduction for its subgraphs more profitable, who knows.
hey random question, in the 'secure fair random coin flip' segement of the video, why cant the two computers just generate a random number from Z_2 and take the XOR of that (which is like using Z_3^X)? does it have to do with how the numbers are transferred between both users?
Hey, everyone. Here used to be an explanation to what the paper by Goldwasser, Micali and Rackoff actually does, because the coin toss in the video is only a simplification, a very big simplification. But I think I made a huge mistake in my comment. It is said in the paper that computing the so-called Jacobi symbol, that hints whether a number is a square or not, is simple, but actually proving that it is indeed square is not. But then I realised that quadratic reciprocity absolutely gives you an algorithm to do this, when the module (the number in the subscript) is prime. So I reread the paper and it says that the module can be any natural number. It is here where I'm stuck. Doesn't this mean that the proof system in the paper breaks down if the module happens to be prime? I want to note that I was already aware, that I took some liberties when I was focusing only on Zp*, when the proof system works with general modules. The main point I was trying to get across with my explanation is that their proof system uses that the probability of a number being square to be not more than 50% and looking at Zp* is a good idea, because these are the extreme cases. In other modules it is even less than 50% (because of the Chinese remainder theorem, but we haven't seen products of groups in this series yet). I am currently trying to figure out, what I missed, and will update a corrected comment as soon as I can.
@@Nemean well, in either case I was just joking abut how it's a hefty reading (and now I feel like it has grown even bigger :D), but for future reference, I believe it'd be better to just edit in a further development instead of replacing the entire body of the comment.
22:30 the pattern is that Z11* is generated by 2. 1 in Z10 maps to 2, and every element in Z11* is of the form 2^x, where x is the element in the bottom row. so 1 -> 2, 2 -> 2^2=4, 3 -> 2^3=8, 4 -> 2^4=5, etc. this is because 2 is a "primitive root" (generator) of Z11*. it isn't always 2 for Zp*, but the fact that Zp* is isomorphic to Zp-1 is basically equivalent to the idea that Zp* has a generator/primitive root for all p>2. there are actually multiple primitive roots for all p>3, so the isomorphism isn't unique. this is a very difficult result to prove in number theory, but it is very useful.
Great video! Y'know, for a long time I "knew" the fact that Zp with zero omitted is a cyclic group, I remember it coming up in the topic of fast Fourier transform algorithms (it's pretty annoying that they always show you how it works with arrays of length 2ⁿ but any other lengths are left as a 'trivial exercise for the reader' 😂). Anyways, a few months ago I decided I'm not happy with "knowing" this huge fact without seeing a proof, and that was really fascinating. Took me down the rabbit hole of rings and fields. One thing I ignored was automorphisms. And the last part of this video gave me that familiar taste for more! I gotta go read some more now! The fact that Aut(Zn) is congruent to (Zn)× is so obvious and so surprising at the same time! And from what you said about D5, I'm guessing Aut(Dn) is probably (Zn)× × Zn? Also, 13:40 ok I'm really sorry for doing it but when you said cryptography my brain did the DeCaprio as Rick Dalton pointing at the TV meme. You said the final vowel with the swedish i. This is kind of my favorite vowel 😅 Alright, sorry, back to groups
I remember one exercise in linear algebra. We had S_3 and D_6 (or D_3) and the exercise was to compare the two. I roughly wrote that they both have 6 elements and that 4 of those are self-inverse. It seems so obvious to say that they are isomorphic now, but we didn't have isomorphisms until then if I recall correctly. For me, the takeaway is that this term isn't exactly obvious for a newbie.
22:44 the pattern I see has to do with powers of 2 and primes. Edit: can't really imagine it in bigger groups, but it probably it's more correctly restated as powers of primes instead. (which in terms reminds me of something something polynomial(s) (something?) (all I can recall was it was a very powerful tool I had never heard about before xD which was quite strange considering the things you could use it for)
I'm curious. What about stuff like Aut(Aut(Zn))? What happens when you keep chaining? I may have figured out something for the cyclical groups. For instance: Aut(Aut(Z11)) = Aut(Z11*) = Aut(Z10) = Z10* = Z4 Aut(Zn) is isomorphic to Zn*, and if you're lucky Zn* is isomorphic to Zm for some other m. But not always: Aut(Z12) = Z12* = Z2 × Z2 And I can't be bothered to take the automorphism group of that UPDATE: 1) Errata. D5 is not isomorphic to Z5 × Z2. My bad 2) Aut(Z2 × Z2) = D3, apparently. Aut(D3) = D3, wait what Are there any other groups G where Aut(G) = G or is it just D3
From what I know and have seen online it seems that there is no uniform structure to describe iterated automorphisms of cyclic group, not because we are not able to, but because it's just too chaotic. D4 and D6 are also their own automorphism groups, but that's all of the dihedral groups. Other groups would be the symmetric group (expect S2 and S6 interestingly enough!) and the monster group. No full classification of such groups is known as far as I'm aware, probably again because it would be too chaotic.
The fair coin flip problem mentioned in the middle of the video has a much simpler solution: just generate a random bit instead of a random element of Zp*, and replace the multiplication with a simpler XOR operation.
Zp* has nice cryptographic properties that XORing bits doesn't have. The story about coin flips is also way too much "boiled down" to be taken seriously, if I'm being honest.
In their paper (linked in the description) Goldwasser, Micali & Rackoff also need certain cryptographic properties of Zp* that XORing bits doesn't have, for example if you're given a square, there is no known fast method to find square root. With bits this is terribly easy: √0 = 0 and √1 = 1. Otherwise you're right, they are absolutely identical.
The coin toss is a very, very, VERY simplified explanation of the so-called zero-knowledge proofs that the trio invented. In their paper (linked in the description) they also need certain cryptographic properties of Zp* that XORing bits doesn't have, for example if you're given a square, there is no known fast method to find its square root. With bits this is terribly easy: √0 = 0 and √1 = 1.
The isomorphism between Z*_p and Z_{p-1} can't be more easily understood using generating elements. For example, in the case p = 5, both 2 and 3 are generators (taking repeated powers creates the whole group) of Z*_5 in the same way that both 1 and 3 are generators of Z_4 Z*_p = {1, 2, 3, 4} = {2^0, 2^1, 2^3, 2^2} = {3^0, 3^3, 3^1, 3^2}
D3, D4, D6 are their own automorphisms group but that's more of a cute coincidence. In general the dihedral group is never its own aut. group. The symmetric groups Sn (which we haven't covered so far) have the oppsite problem. They are in general their own aut. group, but there is this cute coincidence that S2 and S6 are not.
Good point about D3. The symmetric groups are their own automorphism group because you can beforehand shuffle around the elements that the group permutes, superficially changing the look of each individual permutation but overall you still have a group of permutation. But this shuffling around is exactly what the symmetric group is. The hard part is showing that there are no additional automorphisms, which S6 "accidentally" has. S2 is too small for any of this to happen.
I don't understand it good enough to be able to summarise it in a TH-cam comment, but apparently these extra automorphisms are so exceptional that they at least have their own wikipedia section: en.wikipedia.org/wiki/Automorphisms_of_the_symmetric_and_alternating_groups#%3A%7E%3Atext%3DThe_exceptional_outer_automorphism_of_S%2C-6%26text%3DAmong_symmetric_groups%2C_only_S%2Cby_Otto_H%C3%B6lder_in_1895.?wprov=sfla1
Isnt multiplicative vs additive groups only about notation? Groups are pairs of set + operation after all. In my course we used the * symbol to denote all elements has inverse, however I think that we did not use it strictly only for groups with multiplications
i just looked, cant you go zeta -> geometry -> number theory -> group theory its the reciprocal of a increasing number to a complex number, if the natural numbers can be represented by higher and higher dimensional cubes cant a but of abstraction allow complexs to connect into geometry? then go by the langlands program (somehow) to number theory and use that and group theory to solve? i dont know if anyones tried that before.
I already made a community post about it, but I just realised that this video has a HUGE error!!! Luckily not in the material itself, but I claim at 20:56, that the fact that half of the numbers in the number system Zp* are squares, _eventually_ helped 3 researchers win the Gödel prize. Of course this is a massive simplification - that alone doesn't win you a Gödel prize - but I just wanted to get across how knowing group theory can benefit you.
Well it turns out their algorithm does not depend on that at all!!! I tried to find out what made me think that and it turns out the book I used as reference (Computational Complexity by Arora & Barak) has an error!!!
cs.stackexchange.com/questions/140727/is-quadratic-nonresiduosity-in-textbfnp
I also just genuinely and completely misunderstood the prize winning paper. I thought the point was that a certain probability generated from coin tosses was being preserved with this fact. That doesn't make sense at all in hindsight. My toy simplification is now not a simplification anymore but actually misinformation.
So my question to you is: What is the best action now? Take the video down and try to come up with a new application? This will take forever. Make a pinned comment but keep the video up? My video makes vixra look smart now. I'd love to know your opinions though before I do anything more stupid.
Pinned comment while you make the fix, hide this video when the fix is completed, and link to it in the description of the new vid. That's what I'd do
Or if you wanna move onto new content just leave the pinned comment up and the mistake in, we're thankful for the time and effort you put in and life's too short to keep going back, art is never finished
It’s a small part of the video, leave it up and perhaps add another comment also in the timeline of the video so it’s easier to spot without going to the comment section
I mean if you feel so bad about it maybe just put a small edit on the video stating its misinformation. Pinned comment is still best in my opinion. I want that third vid asap 😅
It's not a big part of the video, even if it is misinformation, so a pinned comment should suffice. That being said, it would be nice if TH-cam had a feature to allow for annotations at that portion of the video-something like ""I made a mistake! Please see the pinned comment for more information." but TH-cam doesn't have annotations anymore. If there's a similar feature, though, it could work just as well.
not everyone looks here, id say change the video to atleast have some big red text saying that this is a mistake to make sure nobody internalizes false info.
it took so long that I managed to both get inspired by your quake video, start, and then nearly finish my CS degree but now he's BACK
Me too.. first time i watched his videos i was in my first year of college jobless and gf less. Now I'm about to finish my degree with both.. took such a long time. Day by day nothing changes but when you look back...
@@sujalgvs987I don't know who you are but that's fucking awesome. Congrats bro!
Hey everyone, I had surgery and I'd like to talk about it.
3 years ago I broke my collarbone. I went to the hospital and they fixed it with a metal plate.
They then told me that it would take 2 years to heal and, if I notice a bump, that this is the plate and that I shouldn't worry about it.
Well 2 years later I had it taken out again, but I still had that bump.
I asked them about it and my contact person said that the people from 2 years ago probably forgot to sow back together my ligaments.
It turns out that if you rip the ligaments attached to your collarbone, they stop holding it down and it starts to stick out under your skin and suddenly you can do things like touch its underside. Shocks against it suddenly become very painful. WTF, I was wondering why this "metal plate" feels so awful. I couldn't imagine to live with that.
I eventually found a new hospital where they proposed to do a ligament transplant.
The exact procedure is explained here:
www.schulthess-klinik.ch/de/schulterchirurgie-und-ellbogenchirurgie/behandlung/verletzung-des-schultereckgelenks
It's in German but at least there is a video. Actually I got only one hole drilled unlike the two in the video.
I did the procedure and it took a year of healing and physiotherapy afterwards but my collarbone amazingly is now at its old place. It's not as stable as before and I can still make it somewhat stick out with certain movements like shrugging but by and large I'm amazed with the result.
Did any of you tear your collarbone ligament? What operation did you do? Are you happy with the result? Did you encounter any problems? The whole ordeal was pretty exhausting for me, so I would love to hear your story. But now you know why it took so long for me to upload the next video.
yo. I'm really glad to know you're ok. I was not at all aware of this surgery, but I was worried nonetheless. thank you so much for showing up and dropping another amazing video. it really means the world that you're healthy and doing more content. I also hope you enjoyed making the video as much as we're all gonna enjoy watching it. happy holidays!
Finally
Mate you probably won't even know me, the same here. But I'm glad you've got through that tough time. It's alright, just 2 years. I'm more happy with you continuing this TH-cam after everything you've gone through. Hope your doing well mate, get better soon! Lots of love.
I'm glad you found a solution. No worries about video delays, this is awesome
i was gonna meme about how you took 2 years to drop another video, thank god i read this first
hope you get even better and dont ever need to worry about your collarbone ever again
It took nearly three years for him to drop another hit.
see the pinned comment
That's about how long it takes to grasp the fundamentals of abstract algebra and group theory 😅
@@jan_kulawa It's not in the pinned comment
baby wake up. group theory part 2 just dropped
In the darkest hour, when the world needed him the most, he returned!
And though his Edutainment career may be small, I believe Nemean can group the world..
A lot of these comments complain about the timeliness of your video.
I just wanted to say I'm glad you finished it, I know these projects are hard.
Watching this actually made me notice a connection in one of the projects I've been working on. I'm looking forward to your next video.
Can you believe that I only watched Ep. 1 yesterday?? I found from the comments that it was from 2 years ago. I checked your channel page and didn't find the next part. I didn't give too much thought about the time of next upload. When I first saw this video in my recommandations, I couldn't recognize the thumbnail. According to my memory, I didn't remember seeing it on your channel page. I checked the upload time, and then I realized 😃that this video is new! What a surprise 😄!!
I really enjoyed the previous video. You introduced the topic so well! 🤠 Your explanation was so clear and intuitive. You have justified the choice of terms like "neutral" and "inverse" as well as the choice of notations like a^-1. The animations were so smooth and also helped in building the intuition. Even though I am already familiar with group theory from the course I had and also from other videos, I wanted to watch, because I like Math. Your video is definitely different from other ones I have seen. It has a special and unique vibe to it.
I am eager 😄 to watch this episode . I am sure it will be astonishing like the previous one, and who knows, perhaps even more. I only came to watch group theory. But I may stay to check out the algorithm to solve the graph theory problem .. I honestly don't quite remember what it was 😅 Let me check the previous video title..
.
.
Did you change the title and the thumbnail?? Well, maybe this is better. Anyway, I am glad that you kept the icosahedron. Its shape and colors are satisfying 😌to look at.
So, this is it. If you reached this point, THANK YOU! 😊
P.S. : This comment 😅got longer than what I planned to.
Glad to see you back as well as hear about your successful recovery! Thanks for the new video and hopefully there are many more to come because your topics and presentation are excellent. Best wishes!
FINALLY. Dropped a banger after 2 whole years. I would watch the multiplication and group theory time and time again always understanding the topic a bit more and hoping when the next one would drop. Thank you so much! Hope this video gets the views it deserves.. a lot of us waited for it
How funny! I was just watching your older videos yesterday, and this gem of a video dropped! I hope you feel better, and keep making videos for this series. As a computer science and Math Student who has taken an introductory Abstract Algebra course, there was still stuff that I learned from this video.
Incredible video!
תודה רבה
My goodness, Christmas came early.
Thank you for the upload Nemean, looking forward for future content.
Love the group theory videos, hope it takes less than 2 years for the next one. It was sad that I completely forgot about this gem of a channel.
Glad to see you back. Well done on your recovery. I hope to see more.
I've never properly covered group theory at university but it's amazing how natural and logical it is.
This is one of the best videos I’ve ever watched on TH-cam period.
i literally followed a whole group theory and abstract algebra course because of your first video and i can't wait to see the continuation of this series
I just rewatched the first episode yesterday, this is crazy timing! Anyways, I wish the best for your health and welcome back!
The come back I did not expect. Really hyped for this. Will watch later!!
i just re-watched part 1 a few days ago!! hyped for this video, thank you for the christmas miracle🙏
Thank you Nemean for taking the time and effort to produce such an informative and high quality video !
These 35 minutes of gold made me understand way more than an entire course on this topic at uni. You're very talented at explaining, and I wish I had this video when I was a student.
I am pretty sure your work has already done more good in this world than you can imagine, and it will keep doing as more people will see it.
If you ever have doubts on wether it is worth continuing to work on these videos, trust me, your skills and efforts have the power to better so many lives and inspire so many people.
Legend.
I'VE BEEN LOOKING FOR THIS VIDEO FOR AGES!!!! Thank you
you're so helpfull for all undergrad students who deeps diver in algebra and science
I still remember episode 1 being the first video about group theory I ever saw, and I still remember where I watched it (I was on vacation at the time).
Really glad that you continued the series, even if this is now a bit below my level of understanding.
And E=m(a²+b²) made me laugh
So glad you are back! Thank you so much for this!
22:29 For the example on screen, the pattern is powers of two! If _n_ is in _Z_10_ and _m_ in _Z*_11_ then the isomorphism is
_[ 2^n mod 11 ] ←→ m._
This makes sense when you think about it, it's just the exponential map example you gave in the video. I think I have a proof, but I'm not an expert in modular arithmetic or group theory so do correct me if I'm wrong!
Consider the additive group _Z_N_ and the multiplicative group _Z*_M_ . We'll refer to elements of _Z_N_ with _"n"_ and _Z*_M_ with _"m"_ . Now we'll try to construct an isomorphism with the the exponential with integer base _a_ .
We say _m0 = a^n0_ , _m1 = a^n1_ , etc. This gives the following:
_m0 · m1 = a^n0 · a^n1 = a^(n0 + n1)_
We define _n0 + n1 =: n2 (mod N)_ and thus, by consistency, we have _m0 · m1 = m2 (mod M)_ .
Now suppose _n0 = 1_ and _n1 = N_ . By definition of _Z_N_ , we have _1 + N = 0 (mod N)_ . Then:
_a^1 · a^N = a^0 (mod M)_ ⇒ _a · a^N = 1 (mod M)_
Thus, we find that _a^N = a^-1 (mod M)_ . Taking the logarithm on both sides and simplifying:
_N = -1 (mod M)_ ⇒ _N + 1 = 0 (mod M)_
Since _M = 0 (mod M)_ by definition, we hence have _N + 1 = M_ .
For the isomorphism to work, we also need to ensure that there are enough elements in _Z*_M_ to map to _Z_N_ and vice-versa. Since _Z*_ always excludes _0_ we know that _Z*_M_ can contain at most _M - 1 = N_ elements. We require it to contain _N_ elements, so it must contain the maximum possible. This only happens when _M_ is prime, so that adds an additional primality requirement.
Hence we have an isomorphism _Z*_p =~ Z_(p-1)_ via exponentiation with any integer base _a_ .
Q·E·D? :D
edits:
- fixed formatting issues.
- mentioned that the base should be an integer.
- added the primality requirement for M.
You say roughly in the middle that 1 + N = 0 (mod N), but it actually is = 1. This will eventually be a problem, because you will get N = M (instead of N + 1 = M). Since in general |Z_N| = N and |Z_M*| < M, together with N = M this means that Z_N has more elements than Z_M*. Thus they cannot be isomorphic, because isomorphic groups always have the same number of elements. Respectable try though.
omg I never knew i would be so happy for someone i never met. i hope you're doing well and continue with the amazing work ❤
HE'S ALIVE
Incredible explanation, fantastic representations and visually amazing. Great job
thank you for coming back!
You’re back, what a legend!
I thought this video would never come! Fantastic explanations, now I want to get a book and read about all this stuff
And when the world needed him the most... he came back
HE RETURNED, WELCOME BACK KING
2 years of waiting, and worth every second.
When the world needed him the most, he returned.
Let's go, new Nemean video just dropped (about group theory no less)
I love the visual style of these videos 😍
Super cool. As a computer scientist who studied category theory but never really group theory or number theory, I kept spotting hidden category theory in this (e.g. the graphs at 34:35). I'd love to see a followup where you generalise this stuff to category theory!
22:42 the equivalence seems to be log
log2(1) = 0
log2(2) = 1
log2(3) = log2(3 + 11 * 23) = log2(256) = 8
log2(4) = 2
log2(5) = log2(5 + 11) = log2(16) = 4
log2(6) = log2(6 + 11 * 46) = log2(512) = 9
log2(7) = log2(7 + 11 * 11) = log2(128) = 7
log2(8) = 3
log2(9) = log2(9 + 11 * 5) = log2(64) = 8
log2(10) = log2(10 + 11 * 2) = log2(32) = 5
the choice of 2 here is arbitrary, and could actually be replaced by any number
the inverse obviously works, and this ties back into a particularly useful rewording of fermat's little theorem:
a^b mod M = (a mod M)^(b mod phi(M)), where phi(n) = euler's totient function
phi(p) where p is a prime = p-1, hence the equivalence holds
Simply beautiful presentation
one of the most important videos in HISTORY and youtube doesnt even notify me WTF
Long waited content is finally here❤
Inspired by this soo much that i am doing my minor project on this topic
I love the series it introduced me to abstract algebra
I've completed 3 semesters of group theory since the last episode...
Still awesome video
The graph isomorphism problem is really fascinating. Are you going to explain McKay's nauty algorithm for it in the next video? The end of this video seemed like you were hinting at that. I'm incredibly hyped. I tried to wrap my head around this algorithm without much group theory background and it's so hard to follow. I needed this stuff for my master thesis, in the end I was very happy I could just use their nauty tool in my program rather than having to implement this algorithm somehow on my own.
I was using this for canonicalization of subgraphs in a challenging induced subgraph identification problem. It was very satisfying to piece it together and unwrap the necessary adjustments to "undo" all the morphisms, however in the end the practical benefit of this on random graphs turned out to be nothing. I knew that random graphs after some size almost never have nontrivial automorphisms, but somehow I still hoped that some of the induced subgraphs of the same original (random) graph would have occasionally, and that weeding out such isomorphic duplicates from the search space would boost the performance of my general algorithm.
But it turns out this just isn't the case, and even though the computational expense of computing the automorphism groups (and thus a canonical form) of all the searched induced subgraphs was small, the savings in search space reduction that resulted from it is unfortunately even smaller.
That's on random graphs however. On graphs with nontrivial automorphism group, applying this reduction is well worth it, though it would probably suffice to break the initial symmetries rather than check continuously throughout the search. For some real world applications, one might expect a certain degree of self-similarity in specific cases that derives from the application, that would make isomorphism reduction for its subgraphs more profitable, who knows.
Oh man thanks, I totally forgot about the nauty algorithm. I have some ideas, but I'm still figuring out, which algorithm I'm going to explain 😅
hey random question, in the 'secure fair random coin flip' segement of the video, why cant the two computers just generate a random number from Z_2 and take the XOR of that (which is like using Z_3^X)? does it have to do with how the numbers are transferred between both users?
Hey, everyone. Here used to be an explanation to what the paper by Goldwasser, Micali and Rackoff actually does, because the coin toss in the video is only a simplification, a very big simplification.
But I think I made a huge mistake in my comment. It is said in the paper that computing the so-called Jacobi symbol, that hints whether a number is a square or not, is simple, but actually proving that it is indeed square is not. But then I realised that quadratic reciprocity absolutely gives you an algorithm to do this, when the module (the number in the subscript) is prime. So I reread the paper and it says that the module can be any natural number. It is here where I'm stuck. Doesn't this mean that the proof system in the paper breaks down if the module happens to be prime?
I want to note that I was already aware, that I took some liberties when I was focusing only on Zp*, when the proof system works with general modules. The main point I was trying to get across with my explanation is that their proof system uses that the probability of a number being square to be not more than 50% and looking at Zp* is a good idea, because these are the extreme cases. In other modules it is even less than 50% (because of the Chinese remainder theorem, but we haven't seen products of groups in this series yet).
I am currently trying to figure out, what I missed, and will update a corrected comment as soon as I can.
@@Nemean Man, I should avoid asking nicely then, so much reading material :D
@@simdimdim I just updated my comment, because I realised I made a mistake that I don't understand how to fix.
@@Nemean well, in either case I was just joking abut how it's a hefty reading (and now I feel like it has grown even bigger :D), but for future reference, I believe it'd be better to just edit in a further development instead of replacing the entire body of the comment.
22:30 the pattern is that Z11* is generated by 2. 1 in Z10 maps to 2, and every element in Z11* is of the form 2^x, where x is the element in the bottom row. so 1 -> 2, 2 -> 2^2=4, 3 -> 2^3=8, 4 -> 2^4=5, etc.
this is because 2 is a "primitive root" (generator) of Z11*. it isn't always 2 for Zp*, but the fact that Zp* is isomorphic to Zp-1 is basically equivalent to the idea that Zp* has a generator/primitive root for all p>2. there are actually multiple primitive roots for all p>3, so the isomorphism isn't unique. this is a very difficult result to prove in number theory, but it is very useful.
Great video! Y'know, for a long time I "knew" the fact that Zp with zero omitted is a cyclic group, I remember it coming up in the topic of fast Fourier transform algorithms (it's pretty annoying that they always show you how it works with arrays of length 2ⁿ but any other lengths are left as a 'trivial exercise for the reader' 😂).
Anyways, a few months ago I decided I'm not happy with "knowing" this huge fact without seeing a proof, and that was really fascinating. Took me down the rabbit hole of rings and fields.
One thing I ignored was automorphisms. And the last part of this video gave me that familiar taste for more! I gotta go read some more now!
The fact that Aut(Zn) is congruent to (Zn)× is so obvious and so surprising at the same time! And from what you said about D5, I'm guessing Aut(Dn) is probably (Zn)× × Zn?
Also, 13:40 ok I'm really sorry for doing it but when you said cryptography my brain did the DeCaprio as Rick Dalton pointing at the TV meme.
You said the final vowel with the swedish i. This is kind of my favorite vowel 😅
Alright, sorry, back to groups
Well guessed, it's actually Zn* ⋉ Zn (so the semidirect product of Zn* acting on Zn with multiplication)
I remember one exercise in linear algebra. We had S_3 and D_6 (or D_3) and the exercise was to compare the two. I roughly wrote that they both have 6 elements and that 4 of those are self-inverse. It seems so obvious to say that they are isomorphic now, but we didn't have isomorphisms until then if I recall correctly. For me, the takeaway is that this term isn't exactly obvious for a newbie.
And when the world needed him the most he returned
NEW NEMEAN DROPPED BABE WAKE TF UP
Jesus christ man, I've waited for the next video so long
He is back, our lisan al gaib is back
He's back!!!
13:34 bro I'm not ready
hey there, I was waiting for the continuation. ty
This video finally made me understand automorphisms!
WOOHOO MORE GROUP THEORY BABY
17:00 Z mod 9 under multiplication may not be a group but it is a monoid which is still a useful structure, especially in computer science.
omg, new Nemean's video
Nice to see your video again!
22:44 the pattern I see has to do with powers of 2 and primes.
Edit: can't really imagine it in bigger groups, but it probably it's more correctly restated as powers of primes instead. (which in terms reminds me of something something polynomial(s) (something?) (all I can recall was it was a very powerful tool I had never heard about before xD which was quite strange considering the things you could use it for)
I'm curious. What about stuff like Aut(Aut(Zn))? What happens when you keep chaining?
I may have figured out something for the cyclical groups. For instance:
Aut(Aut(Z11)) = Aut(Z11*) = Aut(Z10) = Z10* = Z4
Aut(Zn) is isomorphic to Zn*, and if you're lucky Zn* is isomorphic to Zm for some other m. But not always:
Aut(Z12) = Z12* = Z2 × Z2
And I can't be bothered to take the automorphism group of that
UPDATE:
1) Errata. D5 is not isomorphic to Z5 × Z2. My bad
2) Aut(Z2 × Z2) = D3, apparently. Aut(D3) = D3, wait what
Are there any other groups G where Aut(G) = G or is it just D3
From what I know and have seen online it seems that there is no uniform structure to describe iterated automorphisms of cyclic group, not because we are not able to, but because it's just too chaotic.
D4 and D6 are also their own automorphism groups, but that's all of the dihedral groups. Other groups would be the symmetric group (expect S2 and S6 interestingly enough!) and the monster group. No full classification of such groups is known as far as I'm aware, probably again because it would be too chaotic.
The fair coin flip problem mentioned in the middle of the video has a much simpler solution: just generate a random bit instead of a random element of Zp*, and replace the multiplication with a simpler XOR operation.
Zp* has nice cryptographic properties that XORing bits doesn't have. The story about coin flips is also way too much "boiled down" to be taken seriously, if I'm being honest.
@Nemean How is it any different? It's completely equivalent: square = 0, non-square = 1.
In their paper (linked in the description) Goldwasser, Micali & Rackoff also need certain cryptographic properties of Zp* that XORing bits doesn't have, for example if you're given a square, there is no known fast method to find square root. With bits this is terribly easy: √0 = 0 and √1 = 1. Otherwise you're right, they are absolutely identical.
If you write out the elements of Z(p-1) in a circle, Z(p)'s multiplicative inverses look very symmetric!
The king is back
This made my day
22:00 why is this better than each computer sending a single bit and then XORing them?
The coin toss is a very, very, VERY simplified explanation of the so-called zero-knowledge proofs that the trio invented. In their paper (linked in the description) they also need certain cryptographic properties of Zp* that XORing bits doesn't have, for example if you're given a square, there is no known fast method to find its square root. With bits this is terribly easy: √0 = 0 and √1 = 1.
21:18 toin coss
I found the pattern at 23:57! x in the bottom group correlates to (2^x) % 11 in the top group.
IT DROPPED
The isomorphism between Z*_p and Z_{p-1} can't be more easily understood using generating elements. For example, in the case p = 5, both 2 and 3 are generators (taking repeated powers creates the whole group) of Z*_5 in the same way that both 1 and 3 are generators of Z_4
Z*_p = {1, 2, 3, 4} = {2^0, 2^1, 2^3, 2^2} = {3^0, 3^3, 3^1, 3^2}
Er ist zurück!
Christmas came early this year
OMGGG he came backkkk
🔥
Welcome back!
Christmas came early this year!
I find it funny that after 3 years you still didn’t explain how the graph isomorphism algorithm works.
How lucky am I🎉. Just when I need a tutorial, u upload the Ep.2 though u uploaded nothing in the past year
wonderful, elegant, amazing
I knew you'd be back.
What about groups that are their own automorphism group?
I know there's the trivial example of Z_1 but is there any others?
D3, D4, D6 are their own automorphisms group but that's more of a cute coincidence. In general the dihedral group is never its own aut. group. The symmetric groups Sn (which we haven't covered so far) have the oppsite problem. They are in general their own aut. group, but there is this cute coincidence that S2 and S6 are not.
@Nemean I don't think D3 is a coincidence here. D3 is just S3.
Why are symmetric groups their own automorphism groups except for S2 and S6?
Good point about D3. The symmetric groups are their own automorphism group because you can beforehand shuffle around the elements that the group permutes, superficially changing the look of each individual permutation but overall you still have a group of permutation. But this shuffling around is exactly what the symmetric group is. The hard part is showing that there are no additional automorphisms, which S6 "accidentally" has. S2 is too small for any of this to happen.
@Nemean Interesting. What are the extra S6 automorphisms?
I don't understand it good enough to be able to summarise it in a TH-cam comment, but apparently these extra automorphisms are so exceptional that they at least have their own wikipedia section: en.wikipedia.org/wiki/Automorphisms_of_the_symmetric_and_alternating_groups#%3A%7E%3Atext%3DThe_exceptional_outer_automorphism_of_S%2C-6%26text%3DAmong_symmetric_groups%2C_only_S%2Cby_Otto_H%C3%B6lder_in_1895.?wprov=sfla1
What do you use to animate your videos?
Adobe After Effects
@ Thank you! :D
damn i coudn't even remember why i was subscried to you, glad i was tho this video was so good
The LEGEND!
Man can’t wait for part 3 in 2030
That "E = m(a² + b²)"... You must be so happy with yourself...
MERRY CHRISTMAS EVERYBODY!!!!
Isnt multiplicative vs additive groups only about notation? Groups are pairs of set + operation after all. In my course we used the * symbol to denote all elements has inverse, however I think that we did not use it strictly only for groups with multiplications
Bravo! 👍
16:22
im getting it but aint that just the modulus function.
welcome back!!!
How do did you make the animations?
With Adobe After Effects
@Nemean Thank you
Thank You
there is a pattern in the isomorphism between z 11 star and z 10 + it'susing exponentiation. although not obvoius.
i just looked, cant you go zeta -> geometry -> number theory -> group theory
its the reciprocal of a increasing number to a complex number, if the natural numbers can be represented by higher and higher dimensional cubes cant a but of abstraction allow complexs to connect into geometry? then go by the langlands program (somehow) to number theory and use that and group theory to solve?
i dont know if anyones tried that before.
3:04
Isn't this how monad works?