My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
September 17th, 2017, 11:45 AM   #1
Member
 
Joined: Jan 2015
From: usa

Posts: 79
Thanks: 0

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.
mona123 is offline  
 
September 18th, 2017, 08:38 AM   #2
Member
 
Joined: Jan 2015
From: usa

Posts: 79
Thanks: 0

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 well-defined and surjective.
Please hepl me
mona123 is offline  
September 18th, 2017, 09:47 AM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,661
Thanks: 427

How do you define the action on the product?
Maschke is online now  
September 18th, 2017, 10:17 AM   #4
Member
 
Joined: Jan 2015
From: usa

Posts: 79
Thanks: 0

i didn't define it yet

Please help me i am blocked
mona123 is offline  
September 18th, 2017, 10:51 AM   #5
Senior Member
 
Joined: Aug 2012

Posts: 1,661
Thanks: 427

Quote:
Originally Posted by mona123 View Post
i didn't define it yet
How does your book or class define it?
Maschke is online now  
September 18th, 2017, 11:34 AM   #6
Member
 
Joined: Jan 2015
From: usa

Posts: 79
Thanks: 0

$[(x,y)]$ is the orbit $\left\{g.(x,y)=(g.x,g.y), g\in G\right\}$
mona123 is offline  
September 18th, 2017, 08:33 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 1,661
Thanks: 427

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 08:53 PM.
Maschke is online now  
September 20th, 2017, 01:44 AM   #8
Member
 
Joined: May 2017
From: Russia

Posts: 34
Thanks: 4

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$.
ABVictor is offline  
September 20th, 2017, 11:34 AM   #9
Member
 
Joined: Jan 2015
From: usa

Posts: 79
Thanks: 0

@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
mona123 is offline  
September 20th, 2017, 11:37 AM   #10
Senior Member
 
Joined: Aug 2012

Posts: 1,661
Thanks: 427

Quote:
Originally Posted by mona123 View Post
@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
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 11:45 AM.
Maschke is online now  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

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 06:41 AM
Prove that this finite set is a group nata Abstract Algebra 2 October 30th, 2011 06:29 PM
Let G be a finite group and h:G>G an isomorphism, such that johnmath Abstract Algebra 2 November 27th, 2010 11:52 PM
finite group stf123 Abstract Algebra 1 September 28th, 2007 01:08 PM
T'-group finite (help-me please thanks) sastra81 Abstract Algebra 1 January 9th, 2007 08:05 AM





Copyright © 2017 My Math Forum. All rights reserved.