Researchers Use Group Theory to Speed Up Algorithms - Introduction to Groups 

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?

agreed

*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

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

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

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.

It's a power 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 RU-vid 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

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.

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

Same, just wish I had this video back then lmao

50th like

wow I didn't know that that was required. Thanks!

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. ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE--uXFYpVumh4.html ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-sJgK0jjd6oE.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

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

Good point! It's at people.cs.uchicago.edu/~laci/2015-11-10talk.mp4