User Name Remember Me? Password

 Abstract Algebra Abstract Algebra Math Forum

 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 well-defined and surjective. Please hepl me September 18th, 2017, 08:47 AM #3 Senior Member   Joined: Aug 2012 Posts: 2,386 Thanks: 746 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,386
Thanks: 746

Quote:
 Originally Posted by mona123 i didn't define it yet
How does your book or class define it? 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,386 Thanks: 746 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,386
Thanks: 746

Quote:
 Originally Posted by mona123 @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 10:45 AM. Tags action, finite, group, set Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post rayman Abstract Algebra 7 March 4th, 2012 05:41 AM nata Abstract Algebra 2 October 30th, 2011 05:29 PM johnmath Abstract Algebra 2 November 27th, 2010 10:52 PM stf123 Abstract Algebra 1 September 28th, 2007 12:08 PM sastra81 Abstract Algebra 1 January 9th, 2007 07:05 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      