Cool abstract algebra proof

Question

zzr0ck3r · Answer

This is a cool proof that illustrates the use a group actions. I am trying to write up the proof in a way that an undergrad with knowledge of group theory can understand. 

(Cauchy's Theorem) Let $G$ be a finite group and $p$ a prime number such that $p$ divides $|G|$ then there exists an element of order $p$ in $G$.

(Proof) First we define the set $$\Omega:=\{(x_1,x_2,...,x_p)\mid x_i\in G\text{ and } x_1x_2...x_p=e\} \subseteq G^p=\underset{p-times}{G\times G \times...\times G}.$$We can say the exact size of $\Omega$ because we are free to choose the first $p-1$ elements and then, since inverses are unique in a group, there is only one choice for the $p'$th element. Example: If $p=3$ then we can choose any element in $G$ for $x_1$ and any element from $G$ for $x_2$ then we have $x_1x_2x_3=e$ and there is only one choice for $x_3$, namely $x_3=x_2^{-1}x_1^{-1}$. So with this we have  $\Omega=|G|^{p-1}$ 

Consider the permutation $\pi$  on $G^p$ where $(x_1,x_2,...,x_p)^\pi=(x_2,...,x_p,x_1)$ (it is easy to show that this is a bijection). Note that I am using the exponential notation for evaluating a function i.e. I could have written $\pi((x_1,x_2,...,x_p))=(x_2,...,x_p,x_1)$. 

Composing $\pi$ with itself gives the group $\langle \pi \rangle$ of order $p$ and since $\forall x\in \Omega$ it is true that $x^\pi\in\Omega$ ( if $ab=e$ then $ba=e$ ) we can think of $\langle \pi \rangle$ as a group acting on $\Omega$; it is obvious that $x^{\pi^p}=x$ for all $x\in \Omega$. 

By the Orbit-Stabalizer Theorem, we have that for all $x\in \Omega$ it is true that $|\langle \pi \rangle |=|x^{\langle \pi \rangle}|*|\langle \pi \rangle_x|$ where $x^{\langle \pi \rangle}$ is the orbit of $x$ and $\langle \pi \rangle_x$ is the stabalizer of $x$. Since $|\langle \pi \rangle|=p$ it must be that $|x^{\langle \pi \rangle}|\in \{1,p\}$. Let $a$ be the amount of orbits of size one and let $b$ be the amount of orbits of size $p$. Since the orbits partition the set $\Omega$ we have that $|G|^{p-1}=|\Omega|=a+bp$, but we know that there is at least one orbit of size $1$, namely $(e,e,...,e)^{\langle \pi \rangle}$, so it must be that $a>0$. Obviously $|G|^{p-1}$ is divisible by $p$ since $|G|$ is and so is $bp$ so it must be that $p$ divides $a$ where $a>0$. So we have $pk-1$ orbits of size one where $k\in \mathbb{N}$.

Let $x\in \Omega-\{(e,e,...,e)\}$, then $x=(x_1,x_2,...,x_p)$ and if its orbit has cardinality $1$ then $$x^{\pi}=x^{\pi^2}=...=x^{\pi^p}$$ which implies $$(x_1,x_2,...x_p)=(x_2,...x_p,x_1)=(x_3,...,x_1,x_2)...(x_1,x_2...,x_p)$$So it must be that $x_1=x_2=x_3=...=x_p$ and so we have an element $x_1\in G$ such that $x_1^p=e$. So the order of $x_1$ is a divider of $p$ but since $x_1\neq e$ ($x\in \Omega-\{(e,e,...,e)\}$) it must be that $x_1$ has order $p$.

steve816 · Answer

So... how could this be applied to real life?

zzr0ck3r · Answer

Applied group theory is often found in Physics, Biology, and Chemistry. I wanted to prove this so that I could prove something in graph theory, which is very much an applied math. But I don't do the applying :)

zzr0ck3r · Answer

I was hoping people would ask questions if they were confused, I could explain, and we all learn more.

zzr0ck3r · Answer

The cool thing here as that this really only uses a couple of things

A group $G$ is a set along with a binary operation such that the following properties hold.

1) For any $x,y\in G$ we have that $xy\in G$. Here we are not writing the group operation, just like we use the juxtaposition notation with multiplication. 
2) There exists an element $e\in G$ such that for all $x\in G$ we have $xe=ex=x$
3)) For any $x\in G$ we have that there is an element $y$ in $g$ such that $xy=e$ We call this element $x^{-1}$.

With just this information it is easy to prove the uniqueness of inverses and the cancellation laws.  

The only other thing we use in the proof is the definition of a Group Action, Orbits and Stabilizers and finally we use the Orbit-Stabilizer Theorem and I could show a proof of that if anyone is interested.

kainui · Answer

Couple questions, I'll be sorta in and out cause we have company over so might take me today and tomorrow to finish. Couple quick questions:

What's order $p$ of an element mean, that $g \in G$ we have $g^p=e$?

l noticed your definition for $\Omega$ has this condition that $x_1 \cdots x_p = e$ but in general this isn't true for all groups I think, so I was kind of curious if this ends up being restrictive. Specifically, if you have several elements that are their own inverses, then you wouldn't be including their inverses so that product would not end up being =e I think. Or maybe I'm wrong here and I am not thinking this fully through for some reason.

Also I've never heard of the orbit-stabilizer theorem before, but I have only skimmed it so I don't know how much you explain. I'm gonna guess it's something about finite groups not having cyclic groups that spiral out of control (somehow?) I dunno if you have just a quick rough explanation, or even a proof if it's short enough can you share?

I'll be back in a few hours or more depending to catch up on this, but I use a handful of group stuff all the time so this is comfy I look forward to getting through this later this evening and working some stuff out. Also I'm curious about what stuff in graph theory you're applying it to, sounds fun.

jhonyy9 · Answer

@Kainui i like your above wrote questions - ty

zzr0ck3r · Answer

Yes the order of an element $x$ is the least natural $n$ number such that $x^n=e$

Only the identity has order $1$ and there is only one identity (mini proof $e_2=e_1e_2=e_1$)

I am a little confused about the second question. No matter how many elements we "multiply by each other" say $x_1x_2x_3x_4....x_k$ there is always a group element $y $ such that $x_1x_2x_3x_4....x_ky=e$. Omega is a set, not a group; we only need sets for group actions to act on. Note that omega is a subset of GxGxGxGxG.. but we are talking about G as a set here. The real notation for a group is $(G,\cdot)$ but we often just write $G$. I am not sure if I answered question 2, but maybe elaborate a little more if not. 

Do you know much about group actions? Group actions are a way to make a group "collaborate" with a set, so that we may use group properties to tell us something about the set. This time it happened to tell us that there $k$  elements of the form $(x,x,x,...,x)$ in Omega (every component is the same). 

If we have a group $G$ and a set $S$ then a group action is a function  $\alpha:G\times S\rightarrow S$ (but we use the notation $s^g$ instead of $g(s)$ such that $s^e=s$ for all $s\in S$ and for all $g,h\in G$ we have $x^{gh}=(x^g)^h$.

Let $G$ be a group acting on a finite set $S$. Let $x\in G$, then the orbit of $x$ is defined as $$x^G:=\{s\in S\mid \exists g\in G \text{ s.t. } s=x^g\}$$

Note that this is a subset of our set $S$ and not necessarily a subset of our group $G$.

We define the stabilizer of $x$ to be $x_G:=\{g\in G \mid x^g=x\}$. It is easy to show this is a group. For sure $x^e=x$ so $e\in x_G$. Let $a,b\in x_G$ then $x^a=x\text{ and } x^b=x$ so $x^{ab}=(x^a)^b=x^b=x$ and thus $ab\in x_G$. Also if $g\in x_G$ then $x^g=x$ and so $(x^g)^{g^{-1}}=x^{g^{-1}}\implies x^{g^{-1}}=x$ so $g^{-1}\in x_G$. This shows that the claim that $x_G$ is a group is true. 

So $x_G$ is a subgroup of $G$. Now we can build these things called cosets with subgroups of groups. 

Consider the group $G$ where $H$ is a subgroup of $G$ (H lives in G and H is a group)

To make this a little easier we will consider finite groups ( but this extends to infinite groups). 

We define cosets of $H$ in $G$ to be $aH=\{ah\mid h\in H \text{ and } a\in G\}$

If $a\in H$ it is not hard to see that $aH=H$ if $a$ is NOT in $H$ it is easy to see $aH\cap H=\emptyset$ and so cosets are disjoint or equal and thus they partition the group $G$ (not necessarily into subgroups).

I realize now that this is much more than I thought it would be, but what the heck...

Depending on the subgroup, we may get many cosets or just one. We call the amount of cosets we get from one subgroup the index of $H$ in $G$ and we denote that with [$G:H$].

Ok now for the Orbit-Stabilizer Theorem. 

(Theorem) Let $G$ be a group acting on a set $S$ and let $s\in S$ then $|s^G|=$[$G:H=$]$\dfrac{|G|}{|s^G|}$

(my wife called and I need to go get buns, so I will be back with the proof (it is short).

zzr0ck3r · Answer

that last ] should be to the left of that = sign