
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 17th, 2017, 10:45 AM  #1 
Senior Member Joined: Jan 2015 From: usa Posts: 104 Thanks: 1  Action of a finite group on finite set
I need help to answer the following problem: Let $G$ be a finite group acting on a finite set $X$. Let $m$ be a number of orbits of $G$ on $X$ and $M$ be the number of orbits of $G$ on $X\times X$.Show that $m^2\le M$ with equality if and only if G acts trivialy on $X$. Thanks. 
September 18th, 2017, 07:38 AM  #2 
Senior Member Joined: Jan 2015 From: usa Posts: 104 Thanks: 1 
For that i defined the map $\mathcal{O}_{X\times X}\to \mathcal{O}_X\times \mathcal{O}_X$, $[(x,y)] \mapsto ([x],[y])$ where $O_Z$ denotes the set of orbits of $Z$ and $[z]$ denotes the orbit $\{g\cdot z : g\in G\}$ I want to check that this map is welldefined and surjective. Please hepl me 
September 18th, 2017, 08:47 AM  #3 
Senior Member Joined: Aug 2012 Posts: 2,307 Thanks: 706 
How do you define the action on the product?

September 18th, 2017, 09:17 AM  #4 
Senior Member Joined: Jan 2015 From: usa Posts: 104 Thanks: 1 
i didn't define it yet Please help me i am blocked 
September 18th, 2017, 09:51 AM  #5 
Senior Member Joined: Aug 2012 Posts: 2,307 Thanks: 706  
September 18th, 2017, 10:34 AM  #6 
Senior Member Joined: Jan 2015 From: usa Posts: 104 Thanks: 1 
$[(x,y)]$ is the orbit $\left\{g.(x,y)=(g.x,g.y), g\in G\right\}$

September 18th, 2017, 07:33 PM  #7 
Senior Member Joined: Aug 2012 Posts: 2,307 Thanks: 706 
If $\{[x_i]\}$ is a complete set of orbits of $X$, then $\{[(x_i, x_j)]\}$ is surely a distinct set of $m^2$ orbits of $X \times X$. So $m^2 \leq M$ for sure. I don't have the second half of the proof, equality iff the action is trivial, but I did work out an example that gives a bit of insight. This Wiki article defines a trivial action as $gx = x$ for all $g$. In this case each element of $X$ is its own orbit and so is each element of $X \times X$ so we have equality between $m^2$ and $M$. Now I found an example of a nontrivial action where $m^2 < M$. First, if $G$ is any group, then $G$ acts on itself by left multiplication, and this action is just a permutation of the elements. [You should supply the proofs if this isn't clear]. So, let $G = \mathbb Z / 5 \mathbb Z$ (the integers mod 5) act on itself by left "multiplication," which in this case is just addition since that's the group operation. Now there is $1$ orbit in $G$. That's because the action is just a permutation so everything's in the same orbit. For example the orbit of $1$ is $0 + 1$, $1 + 1$, $2 + 1$, etc. which you can see permutes the elements. Remember the group operation is addition! On the other hand there are $5$ orbits in the Cartesian product. For example consider the orbit of $(1,2)$. Its orbit is $\{(1,2), (2,3), (3, 4), (4, 0),(0, 1)\}$. It never hits anything else. That's only $5$ out of the $25$ elements that must be hit. So there are a total of $5$ orbits once you work out the rest of the details, which I did not do. I think the problem is that the definition $(g, (x,y)) \mapsto (gx, gy)$ doesn't let the target pairs "spread out" enough to cover the entire Cartesian product, if that makes sense. By holding the group element constant we don't let the group act independently on the coordinates, so we can't cover all the elements of the product. That's handwaving in search of insight, but I'd be better off trying to just nail down a proof. So this is one specific example that shows what goes wrong if the action's not trivial. If I get a chance I'll see if I can get that last part. Or you might work through this and see if you get any insight. Last edited by Maschke; September 18th, 2017 at 07:53 PM. 
September 20th, 2017, 12:44 AM  #8 
Member Joined: May 2017 From: Russia Posts: 34 Thanks: 5 
Let $\displaystyle x_i\in X$. $\displaystyle x_i$ belongs to one and only one orbit. And let $\displaystyle m^2=M$. Let $\displaystyle \mathcal{O}_{ij}=\{ [(x_r,\ x_s)]\  \ x_r\in[x_i], \ x_s\in [x_j]\}$. The number of all $\displaystyle \mathcal{O}_{ij}$ is $\displaystyle m^2$. And every $\displaystyle \mathcal{O}_{ij}$ contains at least one orbit $\displaystyle [(x_i,\ x_j)]$. So, $\displaystyle \mathcal{O}_{ij}$ contains unique orbit $\displaystyle [(x_i,\ x_j)]$, and the orbit has to contain all the pairs $\displaystyle (x_r,\ x_s)$ where $\displaystyle x_r\in[x_i], \ x_s\in [x_j]$: $\displaystyle \mathcal{O}_{ij}=\left\{ \{(x_r,\ x_s) \  \ x_r\in[x_i], \ x_s\in [x_j] \} \right\}.$ Suppose, there are $\displaystyle x_i, x_k\in [x_i]$ such that $\displaystyle x_i\neq x_k$. Then there has to be such $\displaystyle g\in G$ such that $\displaystyle g\left((x_i,\ x_i)\right)=(x_i,\ x_k)$. But it is impossible because the map $\displaystyle x\mapsto gx, \ \ x\in X, \ \ g\in G$ is bijective. So, there is a contradiction, and one has $\displaystyle x_i, x_k\in [x_i]$ implies $\displaystyle x_i=x_k$. 
September 20th, 2017, 10:34 AM  #9 
Senior Member Joined: Jan 2015 From: usa Posts: 104 Thanks: 1 
@AB Victor, you proved the implication $m^2=M$ then G acts trivialy on $X$ but how we can prove the other implication?: if G acts trivialy on $X$ the $m^2=M$ Thanks 
September 20th, 2017, 10:37 AM  #10 
Senior Member Joined: Aug 2012 Posts: 2,307 Thanks: 706  Didn't my post do that? If the action is trivial then each orbit consists of exactly one element: $[x] = \{x\}$. Then $X$ has $X$ distinct orbits and $X \times X$ has $X^2$. Yes?
Last edited by Maschke; September 20th, 2017 at 10:45 AM. 

Tags 
action, finite, group, set 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
example of a finite group....  rayman  Abstract Algebra  7  March 4th, 2012 05:41 AM 
Prove that this finite set is a group  nata  Abstract Algebra  2  October 30th, 2011 05:29 PM 
Let G be a finite group and h:G–>G an isomorphism, such that  johnmath  Abstract Algebra  2  November 27th, 2010 10:52 PM 
finite group  stf123  Abstract Algebra  1  September 28th, 2007 12:08 PM 
T'group finite (helpme please thanks)  sastra81  Abstract Algebra  1  January 9th, 2007 07:05 AM 