5 ms·

Ask HN: Wanted: Elementary but surprising group theory result ...

Recently I was asked for an example from group theory to show its utility. Basically, I'm looking for something slightly interesting or slightly unexpected or rather useful that is otherwise not obvious, but falls out of some elementary group theory. My first two responses were Lagrange's Theorem, that the size of a subgroup divides the size of the whole group (so the number of rotations of a cube divides the number of permutations of six objects), and the fact that a group of even order has a non-trivial element whose square is the identity. But I was hoping for something a bit deeper than either of these. Any suggestions? Thanks. PS: I know this is not about hackers or entrepreneurs or startups, but I also know people here like a bit of math. Sometimes.

jonp 16y ago
How about the result concerning finding the roots of polynomials; that there are increasingly complex exact and explicit formulae as you go from linear to quartic, but it's impossible to find such formulae for quintics or higher. I don't know if that fits your needs: it's elementary to state, but not exactly elementary to prove.
- RiderOfGiraffes 16y ago
  Lovely result, but as you expect, not really sufficiently elementary. Also, while mathematicians find impossibility proofs among the most useful results, non-mathematicians are usually more impressed by results that show something unexpected is possible. But I'll keep it in mind.
btilly 16y ago
I'd submit Euler's theorem, http://en.wikipedia.org/wiki/Euler%27s_theorem http://en.wikipedia.org/wiki/Euler%27s_theorem. This result is the heart of the Rabin-Miller primality test, which is what makes finding large (probable) primes easy, making RSA encryption practical.
- RiderOfGiraffes 16y ago
  Hmm. I do use that result in the context of number theory, and I suppose I could bend it to use it as an example of groups in abstract being used in practice. I'll have to think about that, but it does show promise. The question is, how can I present it as a result that's specifically from group theory being used in number theory? Does that make sense? I'd like to be able to demonstrate something that's specifically group theory, and I'm finding it hard to extract the abstract, in this case. But it shows promise.
korch 16y ago
I'd say mathematics is closer to the hacker spirit than startups or icky things involving money & bureaucracy. I like the proof of quadratic reciprocity by way of group theory. A novice might think the proof has no practical "utility". But Gauss invented it, and it's called the "jewel of arithmetic", so that's more than enough utility to me. Besides, doing it this way also shines light on the way group theory can be applied to other areas entirely, such as deep theorems in number theory. Here's a short proof of the quadratic reciprocity using group theory by an exceptional high school student: http://www.thehcmr.org/issue2_2/math_minutiae.pdf http://www.thehcmr.org/issue2_2/math_minutiae.pdf
dtyuldtulfdyu 16y ago
http://www.tkkshow.com http://www.tkkshow.com The company products cheaper price, reputation first, quality first, welcome friends order. Fashion, trends, avant-garde; the global epidemic. Woman Boot $40 + Air jordan(1-24)shoes $33 bag $30 + Tshirts $ 16 Low-heeled shoes $40 Air Max SHOE(Air Max 24-7,Air Max 2011,Air Max 2010,Air Max 2009 )$38 Jean (True Religion, ed hardy, coogi) $ 30, Sunglasses (Oakey, coach, gucci, Armaini) $ 16, New era cap $ 15, jacket(Gucci,G-STAR,Ed Hardy,ARMANI,AF ,) $40 Woman Boot: (Christian Louboutin,NIKE,LV,Jordan,)$48
alderssc 16y ago
Something slightly interesting might be the Rubik's cube group. By considering the Rubik's cube a group under the rotation operation, then we can essentially completely solve the Rubik's cube puzzle. If you are familiar with the Quaternions, take a look at the 3D rotation group SO(3). This group apparently has applications in computing where one needs a way to perform rotations in three dimensions. According to the Wikipedia article, https://secure.wikimedia.org/wikipedia/en/wiki/Quaternions_and_spatial_rotation https://secure.wikimedia.org/wikipedia/en/wiki/Quaternions_a..., this method of representation has certain important advantages over other methods, including being numerically stable and avoiding a problem called gimbal lock, where rotation about one of the possible axes is no longer possible.
- RiderOfGiraffes 16y ago
  Well, the idea of using commutators in the Rubik cube is what leads to a nice, elementary method of solving it, but it's not really a theorem or result from group theory that's telling us something we didn't already know. Plus I suspect many people would regard this as just a toy, a form of "play for play's sake" and hence still irrelevant. The fact that the quaternions form a field (hence two kinds of group, one of which is interesting) where the multiplication doesn't commute, and then that can be used to model rotations is again interesting, and can be asserted to be useful (and it is) but it's still not really what I'm looking for. But keep the ideas coming. There's got to be a good one out there somewhere - isn't there?
pmiller2 16y ago
What about (not) Burnside's lemma: If $G$ acts on a set $X$ and $|X^g|$ denotes the number of elements of $X$ fixed by $g$, then the number of orbits $|X/G|$ is given by $|X/G| = \frac {1} {|G|} \sum_{g \in G} |X^g|.$ The proof is simple, yet you can count an amazing number of things with it.
- RiderOfGiraffes 16y ago
  Ah, now that's more interesting. I'm not sure I can make that readily accessible, but if I consider a specific example (yet to be invented) then maybe I can make it "obviously useful" while still being an abstract result. I'll have to think about that. Boffo. Good one. Thanks.

jonp 16y ago

How about the result concerning finding the roots of polynomials; that there are increasingly complex exact and explicit formulae as you go from linear to quartic, but it's impossible to find such formulae for quintics or higher. I don't know if that fits your needs: it's elementary to state, but not exactly elementary to prove.

RiderOfGiraffes 16y ago
Lovely result, but as you expect, not really sufficiently elementary. Also, while mathematicians find impossibility proofs among the most useful results, non-mathematicians are usually more impressed by results that show something unexpected is possible. But I'll keep it in mind.

btilly 16y ago

I'd submit Euler's theorem, http://en.wikipedia.org/wiki/Euler%27s_theorem http://en.wikipedia.org/wiki/Euler%27s_theorem. This result is the heart of the Rabin-Miller primality test, which is what makes finding large (probable) primes easy, making RSA encryption practical.

RiderOfGiraffes 16y ago
Hmm. I do use that result in the context of number theory, and I suppose I could bend it to use it as an example of groups in abstract being used in practice. I'll have to think about that, but it does show promise. The question is, how can I present it as a result that's specifically from group theory being used in number theory? Does that make sense? I'd like to be able to demonstrate something that's specifically group theory, and I'm finding it hard to extract the abstract, in this case. But it shows promise.

korch 16y ago

I'd say mathematics is closer to the hacker spirit than startups or icky things involving money & bureaucracy. I like the proof of quadratic reciprocity by way of group theory. A novice might think the proof has no practical "utility". But Gauss invented it, and it's called the "jewel of arithmetic", so that's more than enough utility to me. Besides, doing it this way also shines light on the way group theory can be applied to other areas entirely, such as deep theorems in number theory. Here's a short proof of the quadratic reciprocity using group theory by an exceptional high school student: http://www.thehcmr.org/issue2_2/math_minutiae.pdf http://www.thehcmr.org/issue2_2/math_minutiae.pdf

dtyuldtulfdyu 16y ago

http://www.tkkshow.com http://www.tkkshow.com The company products cheaper price, reputation first, quality first, welcome friends order. Fashion, trends, avant-garde; the global epidemic. Woman Boot $40 + Air jordan(1-24)shoes $33 bag $30 + Tshirts $ 16 Low-heeled shoes $40 Air Max SHOE(Air Max 24-7,Air Max 2011,Air Max 2010,Air Max 2009 )$38 Jean (True Religion, ed hardy, coogi) $ 30, Sunglasses (Oakey, coach, gucci, Armaini) $ 16, New era cap $ 15, jacket(Gucci,G-STAR,Ed Hardy,ARMANI,AF ,) $40 Woman Boot: (Christian Louboutin,NIKE,LV,Jordan,)$48

alderssc 16y ago

Something slightly interesting might be the Rubik's cube group. By considering the Rubik's cube a group under the rotation operation, then we can essentially completely solve the Rubik's cube puzzle. If you are familiar with the Quaternions, take a look at the 3D rotation group SO(3). This group apparently has applications in computing where one needs a way to perform rotations in three dimensions. According to the Wikipedia article, https://secure.wikimedia.org/wikipedia/en/wiki/Quaternions_and_spatial_rotation https://secure.wikimedia.org/wikipedia/en/wiki/Quaternions_a..., this method of representation has certain important advantages over other methods, including being numerically stable and avoiding a problem called gimbal lock, where rotation about one of the possible axes is no longer possible.

RiderOfGiraffes 16y ago
Well, the idea of using commutators in the Rubik cube is what leads to a nice, elementary method of solving it, but it's not really a theorem or result from group theory that's telling us something we didn't already know. Plus I suspect many people would regard this as just a toy, a form of "play for play's sake" and hence still irrelevant. The fact that the quaternions form a field (hence two kinds of group, one of which is interesting) where the multiplication doesn't commute, and then that can be used to model rotations is again interesting, and can be asserted to be useful (and it is) but it's still not really what I'm looking for. But keep the ideas coming. There's got to be a good one out there somewhere - isn't there?

pmiller2 16y ago

What about (not) Burnside's lemma: If $G$ acts on a set $X$ and $|X^g|$ denotes the number of elements of $X$ fixed by $g$, then the number of orbits $|X/G|$ is given by $|X/G| = \frac {1} {|G|} \sum_{g \in G} |X^g|.$ The proof is simple, yet you can count an amazing number of things with it.

RiderOfGiraffes 16y ago
Ah, now that's more interesting. I'm not sure I can make that readily accessible, but if I consider a specific example (yet to be invented) then maybe I can make it "obviously useful" while still being an abstract result. I'll have to think about that. Boffo. Good one. Thanks.