Researchers Use Group Theory to Speed Up Algorithms - Introduction to Groups
Vložit
- čas přidán 1. 05. 2024
- This is the most information-dense introduction to group theory you'll see on this website. If you're a computer scientist like me and have always wondered what group theory is useful for and why it even exists and furthermore don't want to bother spending hours learning the basics, this is the video for you. We cover everything from the basic history of group theory, over how and why subgroups partition groups, to the classification of all groups of prime order.
Babai's talk can be found at: people.cs.uchicago.edu/~laci/2...
0:00 Intro
1:42 Abstract Algebra
4:28 Group Theory
8:01 Z Q Zn Dn
14:29 Proofs
18:58 Subgroups & Cosets
25:31 The Theorem
29:11 Classification of Groups of Prime Order
#SoME2
Here I'll present the solution to my challenges. Because CZcams doesn't have spoiler tags, I'll leave them as a comment to myself.
First the second challenge at 22:34
The only interesting example with groups from this video is in Q*. It generates the elements 1 and -1.
Less interesting examples are in Q* or in Z and Q+. They just generate 1 and 0 respectively.
Now the first challenge at 17:57
This one you can just google haha. I recommend this thread: math.stackexchange.com/questions/616577/any-set-with-associativity-left-identity-left-inverse-is-a-group-fraleigh
And by the way, the two graphs at the beginning are actually the same. They are both instances of the so-called Petersen graph.
You might want to pin this :)
@@Nemean if you had a group of real numbers and modulo 1 addition would every generated subgroup already implicitly include 0 and the inverse element, or would that only hold for rationals?
@@msq7041 You're correct, if I read your comment correctly. Proof for the sake of completeness: If x is rational with denominator d, then adding x to itself d times gives you a whole number, i.e. something = 0 mod 1. If x is irrational, no multiple of x ever gives an integer and so is always ≠ 0 mod 1. This means you have to include 0 (and inverses) explicitly.
For the second challenge, would, say, a 60 degree rotation in the group of all rotations of a circle work?
Bro casually created one of the best group theory intros out there, left a hangclift end and refused to elaborate further (at least a year after)
agreed
This is some 3b1b level education. At some point this channel will blow up.
Indeed. I remember when he posted his first video about Quake 3 algorithm and I was left speachless at the algorithm itself and the amazing way he presented it. I rewatched the video everytime I got it recommend just to be impressed again.
I disagree. This is much better than 3b1b’s stuff, at least his video on groups.
I saw 3b1b’s video on groups, more specifically the monster group, and his approach to explaining groups was like “I’m not gonna give you the hard axioms because that’s so confusing, so I’m gonna give you this vague analogy about symmetries (which admittedly works for one type of group)”.
When working with such a complex yet widely applicable concept like groups, a video like this is much better in my opinion; first giving the hard rules/axioms of groups, and then giving examples.
@@jeper3460 I was a but disappointed not to see the more intuitive cayley graph explanation of lagranges theorem
not with this upload frequency it won’t
It’s already did blow up. Check his first video.
I’m a math major and when I heard “there’s a field called abstract algebra that no one has ever heard of”, my only thought was “ yeah and you want to keep it that way”. My god that class was hard
As a mathematics student who has since then become an AI researcher, I want to say that mathematicians have done the opposite of keeping things from others. It's just that every time a mathematician wants to tell people how amazing mathematics really is ... people run away screaming, "oh no, math ... algebra, eww, oh no!"
There are two types of people. For some of us math is a turn on.
Accurate
so true.
Maths is one of those secrets that protect themselves.
I'm a cs and linguistics student and the maths professors are doing you no favours. My algorithms class is basically applying all that we've learnt in graph and set theory and it's so much more interesting. The math classes are just so theory based and are interesting on the surface but the whole process and approach just aggghhh
this channel is bound to become an example of high-quality, aesthetic, clear math/cs videos, keep it up
*Note to future self*
For the record, I subscribed when the subscriber count was 61.9K.
@@vivvpprof I did when it's 65.6k
@@ShauriePvs Good! This way we can track it if more people relay the number here.
@@vivvpprof 69K (but was subscribed already since the Quake algorithm video, don't know how many subscribers were there then)
74k
It is over 10 years since I looked at any group theory and even then it was only at a fairly basic level. I look forward to seeing your further videos as your style of presentation is great.
Hasn't been 10 years for me, but it might as well be. I don't remember much, and I second that. I think this video is excellent.
This is a fairly basic level
he never gets to the point though ...
5 years for m
Please calm down and just don't do that shit what Évariste Galois has done.
( Yeah, the 31 May 1832 is more than 10 years ago, but there aren't so much black humorous group theory jokes available, yet )
Anyway, for some reality connections, maybe? A book tip: "Group Theory in Physics. An Introduction", by J.F. Cornwell
"Introduction to Symmetry and Group Theory for Chemists", Springer, Arthur M. Lesk
"Symmetries and Group Theory in Particle Physics: An Introduction to Space-Time and Internal Symmetries", Springer, Giovanni Costa, Gianluigi Fogli
"Matrix Groups: An Introduction to Lie Group Theory", Springer, Andrew Baker
Still waiting for part 2 of this amazing series
It's a power series
Bro said I will be back with part two then bailed for 7 months.
I have seen this video first when it was 2 months old.
Don't make us wait any longer, I BEG YOU!
I've been looking my whole life for a series on Group Theory, ever since I guess I heard about 'The Monster'. And now it seems I finally found one that starts from zero, is narrated by a pleasant voice, and has high-quality visuals to illustrate the concepts. Really looking forward to this entire series.
I believe Socratica has some good beginner videos on the subject - though I'm also looking forward to this series. NJ Wildberger might have a lecture series on it too. His videos are here on CZcams and, while he has some funny ideas about infinity, he's a very engaging and clear-spoken teacher.
I was familiar with a lot of what he talked about because I somehow acquired this little book called "Teach Yourself Mathematical Groups" (Bernard, Tony, Neil, Hugh) from my mom (I think a library was getting rid of it?), and worked through something like half of it. You can get it for < $6 on Abe Books, not that it's necessarily the best one. It has a bunch of practice problems with a lot of focus on proofs from what I remember.
exactly! Thanks for reminding me of that. 3b1b?
@@hughcaldwell1034 thanks
@@hughcaldwell1034 wym by funny lol
I have to say that it's unbelievable that you have only four videos and yet I consider this one of the best channels on CZcams.
Bruh, you have to continue this. You are a BOSS educator. Seriously.
As a math major who now works as a programmer, it's really cool to see how my favorite subject relates to the work I do now. Thanks for making this, looking forward to seeing more.
Are you working as a SWE?
@@mango-strawberry yes
Hey I just graduated in theoretical math, and now I'm going into coding. Exactly why I clicked on this video
@@phoenixmandala2836 cool
It's kind of ironic that in the end they didn't circle back to show how groups are used for graphs
This is the most beautifully animated intro to group theory i've ever seen!
I remember I had to learn group theory as a chemistry major to understand molecular symmetry and the nature of chemical bonds. Your video is so well made that I would recommend it to any chemistry major.
Same, just wish I had this video back then lmao
50th like
wow I didn't know that that was required. Thanks!
checking every few weeks to see if second part is published!!! looking forward to it!
Still waiting for part 2 of this series
This is by far the best group theory video I have seen. This is the first one that let me truly understand it from a casual perspective - even 3b1bs videos seemed opaque about the mechanisms of groups. This lays it out so nicely and concretely it’s hard to get lost at all! I cannot WAIT for more. Instant sub
Before this video, the only other video I had seen on group theory was the one 3b1b made about the monster group, and when I first watched that I was mind boggled how we could even go about beginning to prove things about such abstract concepts like symmetry. After watching this video though, I feel like I got a new insight on how proofs could be derived and built on each other that I was really looking for a while ago! I do hope this series continues, as this whole subject seems really captivating, but the internet seems to be sorely lacking in digestible content about it.
Something really fun about group theory is that it shows up where you don't expect it, the picture usually used to describe group theory is a Rubik's cube :
- each action (combination of rotations) is an element of the Rubik's group, composition is applying actions one after the other, so it's closed under composition
- the action "doing nothing" is the neutral
- associativity checks out because applying (A then B) then C is the same as A then (B then C)
- each action has an inverse
I don't know exactly how many actions/configurations are possible on a Rubik's cube, but if you take all the configurations where only 2 opposite sides are being rotated, you notice it's a subgroup containing 16 actions, and you can just tell it's a multiple of 16 using Lagrange's theorem. Isn't that crazy ?
A standard 3x3x3 "Rubik's" cube has over 43 quintillion permutations. And almost 500 billion quintillion "illegal" permutations - arrangements which cannot occur during normal rotations (and which will not result in a "solved" state) - the sort of thing which happens when cheaters physically deconstruct the cube to move pieces or stickers.
There are many algorithms to solve the puzzle. Some are incredibly fast and efficient, but they're all plodding brute-force sorts of approaches, they largely ignore the state of the cubelets and methodically rearrange all the pieces from top to bottom.
No algorithm exists (yet) which can assess the state of all movable cubelets then immediately devise the minimal path towards solution. Likewise, no algorithm exists (yet) which can devise the maximum possible "mixed" state.
My heavily exhausted mind asked "Does rotating the cube without shifting the pieces count as an action?" like it wasn't obvious.
I'm going to take a nap.
@@pwnmeisterage There actually is a way to get an extremely move efficient method, through computers.
We do actually know actually know the most scrambled state, with the number of rotations of the cube being known as “Gods Number”, 20. The minimum value was discovered to be 20, since 20 moves are required to make a “superflip” pattern on the cube, where all edges are flipped in their place. Then, a massive sum of computers checked through all the possible scrambles to confirm that there was no other higher move count state. Although, we still don’t know what percentage of scrambles require an x number of rotations (since the computers code stops looking for a move efficient solution after it gets one in 20 moves, for time efficiency reasons). Although, it is predicted that most scrambles have at least a movecount of 17-18.
There is no such thing as a “perfect method”, you’d need to be a god to be able to figure that out. Computers, however, can get very close, using a very efficient method.
I wouldn’t call the method that we use to speed cube “brute-forcing”. Algorithms for speedcubing are never usually intuitive (except for ~400 3-style algorithms used for extremely advanced blindfolded solving, or when you are inventing new algorithms, you should check out some of the logic for how they work if you are interested). Instead, we rely on muscle memory, otherwise we would have to mentally memorise algorithm in cube notation and convert it to actual rotations. Memorising 43 quintillion 18-19 move algorithms is impossible. Instead, by learning smaller sets, we only need to feasibly 1 algorithm for our first time solve, to maybe close to 150-200 move sets for advanced solvers. Not only that, but you also have to plan out the cross (which you always do intuitively, never with algorithms), and usually predict the next steps in advance before even beginning to turn.
@@techstuff9198 No one replied to your comment weird.
@@yashaswikulshreshtha1588 The answer is "yes", because it counts as a transformation for group theory's purposes.
This man made a clean introduction to abstract algebra. It makes perfect sense.
Beautifully made video, it’s been years since I’ve found a video so captivating. Not only is the editing top notch, the math is explained well too.
This is one of the most eloquently made and beautifully explained math videos I've seen. Great job! I'm looking forward to future videos
Actually, group theory (as well as abstract algebra as a whole) is indeed the most beautiful math subject. Basically, I wasn't a mathematician, I have a bachelor's degree in civil engineering. I came to study math by self a few years ago, driven by curiosity. And I got interacted with abstract algebra 2 years ago. And I feel my mind blown by the beauty of group theory since my first interaction. It makes me cannot stop learning math.
By the way, your presentation is awesome!
You did summarize the abstract algebra course i took for 1 semester really elegantly. I really greatly appreciate your work.
This channel (and video specifically) prove that there are people that are good both in explanation and visualizing them with animation. I learn group theory back then at uni and sadly not gave them too much attention because the lecturer is boring. Listening to this channel explain the characteristics of group it suddenly make sense, especially when you applied them through Integers, Rationals, Cyclic, etc. The animation style is smooth and comforting. Hope you post other video about topics, especially for prospective computer scientists.
I am absolutely amazed and stunned by both the visuals and the didactics. Incredible material, godlike stuff really. Congratulations man, you've got my maximum respect
Beautiful visuals! There's a lot of love and effort put into this. Very clear explanations as well. I'll be waiting for the next one.
I have long considered your video on the fast inverse square root to be one of the very best mathematical videos on all of CZcams. This video definitely lived up to that legacy. Excellent work :)
Your channel is absolutely going to blow up. Great content and gorgeous presentation man
I feel like a super hero who just found a few super weapons that are so revolutionary
Thank you for introducing me to this field and found a great channel in the process
Best explanation I've heard! Thank you for not dumbing it down or overcomplicating so that we actually progress at a decent pace!
The quality of this video is 10/10
As a programmer interested in math this is best introduction to group theory I’ve seen
Group theory: Man makes imaginary nonsense number sets and tries to prove that they're linked
Probably the best introductory explanation of group theory I've seen. You made several things click for me. Hoping to see more of the series!
I feel this video is why mathematicians get so self-absorbed with math itself. In quest to find the solution of the graph isomorphism, I think all of us found great pleasure in the iterative process of finding strange theorems, and in doing so forgot the aim, and in the future videos I hope you keep on doing this.
i loved the end of the video because math is exactly that. you begin wanting to solve a problem, but to do so you have to study or even develop a crazy math theory. then you realize that this theory is interesting by itself, and you can forget about your motivation.
This is one of the best intros to groups I have seen on here in a while, great job!
I hope you finish this series! I've been at the edge of my seat for months!
Im loving these soME2 videos. cant stop watching them
It's been more than 10 years since I studied group theory and I find your video to be highly engaging. Looking forward to the next one!
This is awesome! I've been trying to read Babai's 2020 paper but couldn't wrap my head around the group theory aspects, thank you so much!
I literally cannot wait for the next part of this video. I've watched it days ago and I can't stop thinking about it! Amazing exposition. Thank you.
I’m so glad you put this out there. It summarises the field of group theory very well in an understandable way! Can’t wait to see the followup!
This is the best video I've ever watched.
One of the greatest mathmatical videos I have ever watched on youtube! You are doing an amazing job of introducing true mathematics to the broad audience, and to refresh our knowlegde of it. Keep on the great work! 👍
I love how the video only began to tackle the idea posed in the title. Makes me excited for future videos.
I really admire the way you use those gorgeous visuals to aid understanding.
What a fantastic, well structured, visually pleasing introduction to group theory. This video deserves the highest levels of praise.
Regarding the question at 0:36 - I know a Petersen-Graph when I see one! For my Diploma-thesis in mathematics I developed a program that uses spring-force algorithms to calculate different stable versions of how to draw a graph. The Petersen-Graph was one of my test cases. So that is how I know that these two graphs are in fact isomorphic just by looking at the shapes.
Sounds cool! Is it published?
As an aside, you might be interested in these works as well! They also use a simulation-like method to simplify graphs, but apply it to 2D- and 3D surfaces instead. This allows one to unravel shapes such as complex knots and twisted, nesting tori, and identify the isotopies between them.
czcams.com/video/-uXFYpVumh4/video.html
czcams.com/video/sJgK0jjd6oE/video.html
@@simpleffective186 you should never ask a doctor whether their thesis is published. For mont people it brings PTSD...
[please read this comment as an inocent joke]
Is it enough to say that two shapes are isomorphic if they have equal amounts of nodes that have equal amounts of connections?
@@Copperhell144 I had the same question in mind, please let me know once you know
It is always refreshing and exciting to have an introduction to mathematics by someone from another field. Cool!
Holy jumping, the editing on this is amazing, well done dude
This is a great video on many levels -- clear explanation, animation/visuals, pacing. I've been dabbling with learning group theory for years and this really nailed it!
this video is really good! its got a nice quality and visual aesthetic to it, that I rarely see in most group theory videos, that matches how intuitive the idea of groups ought to be.
This is great. I completely forgot about the graph isomorphism at the beginning until you mentioned it at the end. I hope you go into some of the scarier groups and at least mention the monsters. I tried looking into truly understanding group theory in the past, but the text I found that enumerated all the groups was incredibly dense.
Would be nice to have a link to the lecture mentioned at the start, too!
The lecture is in the description. And yes, my goal is to increase the difficulty in groups as the series goes on. I can mention the monster if you want, but don't expect too many finite simple groups in this series. Personally I'm still working through Wilson's book on them and my god, are they complicated.
Well, I would of really enjoyed having matlab up in the brackground, or what ever tool he used for graphs lmao , but it was not the less a good lecture
@@Nemean i'd personally like to see some of the simple Lie groups, like U(n), SU(n), and/or O(n), mainly because of how they come up in quantum mechanics. a prime example being the gluons, chromodynamics, and SU(3), in that from what i understand each of the eight gluon types corresponds to one of eight generators for the group, but i haven't yet found a good visualization for what the group is doing past 'the generators are made up of a triplet of commutative ones, another of anticommutative ones, and two seperate ones that are unchanged for either 2-cycling the colors or 3-cycling the colors'.
@@numbers3268 I'm no physicist, but doesn't this correspondence come from the irreducible representations of SU(3)? Because apart from the fact that I genuinely don't know QFT or gauge theory or whatever theory this belongs to, computer scientists use representation theory more like number theorists and less like physicists, so I'd first have to get familiar with the ways of the physicist. What I'm thinking of doing though is covering the affine group, which is used a lot in relativity, but no promises. Would this maybe interest you? I'm genuinely curious, because I have no idea what physicists are up to these days.
@@Nemean im not a physicist _or_ a computer scientist (and i've only dabbled in number theory so far), so what i know is effectively grasping at straws (maybe sometime i'll find a textbook i can get into and find my way from there). i'll still watch the next video(s) though, this one was certainly interesting
Man, this video is my favorite of yours. I'm so glad computer scientists and students can discover how general and powerful algebra can get. Plus, it is animated just right. Keep it up !
This video made me understand group theory, thank you!
babe wake up, new nemean video just dropped
As a computer science Ph.D. with a degree in Math, I love this video.
Amazing description and teaching style. If I had this resource in my first abstract algebra course, my junior/senior years of undergrad would have been so much easier. Thank you!
Oh, your content is always so juicy and just shines with its high quality! Thanks, we appreciate the effort 🤝
Your work deserve much more appreciation!
Man you just earned a subscriber, just due the sheer passion you have for learning such stuff and presenting to us. You spend your time to go through stuff and helps us understand it. Thanks alot man
I had a very good prof for Algebra and it took him half a semester to teach group theory. And you summed it up in 30 minutes. Keep it up man.
I already subscribed and had the bell set to notify me when the next video is out. Can't wait for the rest of the story
I took abstract algebra for my math minor in college and this is perhaps the best introduction I've ever seen on it. Incredible job breaking down these concepts.
The Legend is back!
Hello from Ukraine 🟦🟨
Every video so far has been a banger
I am from Romania and we study group theory in high school and even though I am not even close to an expert I can tell you this video is insanely well made.❤
What a beautifully presented video. I am in awe of the graphics, and the explanations were so clear. I know this stuff from university (45 years ago) but it felt like you covered half a term's group theory lectures in half an hour!
You are finally back! Really love your videos. It was a pain to know that there is only three of them :(
Hey Nemean, I took abstract algebra as a math undergrad. The first isomorphism theorem is my favorite theorem and its beauty belies in its simplicity and power.
Wow! This is the best introduction to group theory, I have seen so far. The information density is just right. Not getting bogged down in too many details of the proofs while still giving good enough intuitions for why the theorems are plausible. Everything seems to fall into place naturally without much of a mental load. I'm looking forward to the next videos in the series.
Ridiculously good video, cannot wait to see the rest of the series!
I never got the "so what" part of abstract algebra when I took the class.
I'm super excited to see where this series goes!
this is the very first video i watched on your channel
and it's insane
i bet you deserve a lot more subscribers
thanks for your effort
you summed up two semesters of "advanced algebra" into one very reachable video
Omg, you're back, i watched you video about the fast inverse square root algorithm and i never expected to find this channel again until now. Good job and good luck
Nemean, this was fantastic. Easily the best group theory video I’ve seen. Can’t wait for the next video!
I love the visuals to this video, and the concept was explained well
I really like the simplicity of the visuals you use. Sometimes I notice other video visuals are so fancy that it sometimes distracts from the concepts it is trying to show. Great video!
Please never stop creating content, this is excellent
Great video! Even though I already took abstract algebra, the proof of Lagrange's theorem still helped me understand even better
Hi, I think the way you presented group theory is so great, and I'm looking forward to your next episode. I feel it's like a great tv series and I'm constantly checking your channel to see if there is anything new. Keep up the great work, and have a happy new year!
I've taken two semesters of abstract algebra as a CS major and sill your video made me understand and appreciate the Group Theory more. Great job, keep it up!
This must be the most intuitive explanation of subgroups and cosets I have ever seen! Can't wait for the next video!
Amazing amazing video!
The way you simplified the concepts with history, visualization, applications and examples was unreal!
I remember in my Grad. days, how many times I went after the textbook to learn group theory, only to be overwhelmed with all the definitions and proofs, only to give up couple of days later!
Can't wait for your upcoming videos! 👏👏👏
Genuinely the best explanation of group theroy I've seen. Bravo!
This is an awesome intro to group theory. You did a great job breaking down a very complex topic. Did not appreciate the cliffhanger at the end lol. Looking forward to the next one
Extraordinary! Well done. So many CZcamsrs try to teach math but none of them even come close to your video. And I love the other, mostly helpful, comments.
Great beginner-friendly explanations, I dig the format and the animations. Looking forward to future videos/
10 years ago, these higher level pure math videos like abstract algebra were only college lecture videos. Look how far we have came!
You did an amazing job with the animations! Thank you CZcams gods for showing me this gem of a channel
Bro This is the first time I heard about group and you already got me hooked, you are a great teacher.
I love that you touched on the 3-6-9 control theory without saying it. The subgroup portion really helped tie your justification for left sided neutrality - absolutely beautiful. This is light years beyond me but you made it make since- touche Sir.
Group theory was the part I liked most when I did Linear Algebra. It’s so neat and clean, still chaotic, and surprises you with connections to the most unlikely places.
Can't wait for the next one. Thanks for this!
Thank you very much. I recollect that I had a course in group theory nearly 25 years ago during my masters degree. Its good to refresh that again in a neat half an hour video and see it in action.
5 months ago, you said you will be uploading "A piece, the likes of which have never been seen before." . 5 months of anticipation, with the only clue being a GIF of a spinning icosahedron.
5 months later, you did not disappoint. Fantastic video!
Group theory is the single most fascinating thing to me in all of mathematics. I cannot wait for this.
Absolutely fantastic video. Just did this course last year and will probably take algebra II (ring theory) this year and this is a fantastic recap. Subscribed and eager for more!
I am a computer scientist like you and these explanations are astonishingly well done.