Fdtxjr

How do conventional missiles fly?

Emailing HOD to enhance faculty application

Why doesn't H₄O²⁺ exist?

How is it possible to have an ability score that is less than 3?

Intersection of two sorted vectors in C++

In a spin, are both wings stalled?

Where does SFDX store details about scratch orgs?

Has there ever been an airliner design involving reducing generator load by installing solar panels?

Brothers & sisters

Could gravitational lensing be used to protect a spaceship from a laser?

Is the Joker left-handed?

Why are electrically insulating heatsinks so rare? Is it just cost?

How can I fix/modify my tub/shower combo so the water comes out of the showerhead?

Anagram holiday

What is a clear way to write a bar that has an extra beat?

Combinations of multiple lists

Can one be a co-translator of a book, if he does not know the language that the book is translated into?

How do I write bicross product symbols in latex?

Is "remove commented out code" correct English?

Took a trip to a parallel universe, need help deciphering

How much of data wrangling is a data scientist's job?

Today is the Center

Why do I get two different answers for this counting problem?

What is the word for reserving something for yourself before others do?

Algorithm to find representatives of orbits when group of permutations acts on set of mappings

Algorithm for scrolling through different orbits in a permutation groupThe group acts on an ordered setDefining action of an elementary abelian 2-group on a vector space.Permutations and group actsQuestion on Proof that in a primitive group we have for the subdegrees $n_i+1 le n_i(n_2-1)$Shortcuts when computing with permutations or other group related constructsLet $G$ act such that each nontrivial element has at most two fixed point and $P := O_p(N)$. Then $G_alpha$ acts fixed point freely on $P$Step in proof that a quotient is isomorphic to cohomology groupOrbits and Stabilizers of a group that acts t-transitively.Find a set of representatives of cosets in $S_4$

1

$begingroup$

Let $N$ be $1,ldots,n$, $R=1,ldots,r$. Consider mappings from $N$ to $R$. It is clear that there are $r^n$ such mappings.

Let $G_n$ be the group generated by $n$ length cycle permutation $alpha=(1,ldots,n)$. $G_n$ contains all powers of $alpha$.

One can see that the group $G_n$ acts on the set of mappings in the following way.
Let $alpha^kin G_n$ and $f:Rmapsto N$.

$alpha^k(f)$ would be the following mapping $(alpha^k(f))(i)=f(alpha^k(i))$.

We can use Bernside's lemma to find number of orbits. Now I need to find algorithm to find orbits. By finding orbits I mean finding set or representatives from each orbit.

Here is an example:

$n=4, r=2$.

A mapping from $1,2,3,4$ to $1,2$ can be represented by a vector $(f(1),f(2),f(3),f(4))$.

Group $G_4$ would be $(1234),(13)(24),(1342),e$

One can see that there are following $6$ orbits:

$(1,1,1,1)$

$(2,2,2,2)$

$(1,1,1,2),(1,1,2,1),(1,2,1,1),(2,1,1,1)$

$(2,2,2,1),(2,2,1,2),(2,1,2,2),(1,2,2,2)$

$(2,2,1,1),(2,1,1,2),(1,1,2,2),(1,2,2,1)$

$(2,1,2,1),(1,2,1,2)$

A set of representatives would be the first column.

As a algorithm one can choose the following. Mark all mappings unchecked. At each step get one unchecked mapping, put it in representation set, act group $G_n$ on it, get all resulting mappings and make them checked. Continue until all elements are checked.

I have posted general question for this problem here https://mathoverflow.net/questions/325839/find-representation-set-of-orbits-when-group-acts-on-a-set

I think there should be better algorithm at list for this specific case. Can anyone help?

group-theory permutations algorithms group-actions

share|cite|improve this question

asked Mar 21 at 14:38

AshotAshot

2,62932044

$endgroup$

add a comment | 

1

$begingroup$

Let $N$ be $1,ldots,n$, $R=1,ldots,r$. Consider mappings from $N$ to $R$. It is clear that there are $r^n$ such mappings.

Let $G_n$ be the group generated by $n$ length cycle permutation $alpha=(1,ldots,n)$. $G_n$ contains all powers of $alpha$.

One can see that the group $G_n$ acts on the set of mappings in the following way.
Let $alpha^kin G_n$ and $f:Rmapsto N$.

$alpha^k(f)$ would be the following mapping $(alpha^k(f))(i)=f(alpha^k(i))$.

We can use Bernside's lemma to find number of orbits. Now I need to find algorithm to find orbits. By finding orbits I mean finding set or representatives from each orbit.

Here is an example:

$n=4, r=2$.

A mapping from $1,2,3,4$ to $1,2$ can be represented by a vector $(f(1),f(2),f(3),f(4))$.

Group $G_4$ would be $(1234),(13)(24),(1342),e$

One can see that there are following $6$ orbits:

$(1,1,1,1)$

$(2,2,2,2)$

$(1,1,1,2),(1,1,2,1),(1,2,1,1),(2,1,1,1)$

$(2,2,2,1),(2,2,1,2),(2,1,2,2),(1,2,2,2)$

$(2,2,1,1),(2,1,1,2),(1,1,2,2),(1,2,2,1)$

$(2,1,2,1),(1,2,1,2)$

A set of representatives would be the first column.

As a algorithm one can choose the following. Mark all mappings unchecked. At each step get one unchecked mapping, put it in representation set, act group $G_n$ on it, get all resulting mappings and make them checked. Continue until all elements are checked.

I have posted general question for this problem here https://mathoverflow.net/questions/325839/find-representation-set-of-orbits-when-group-acts-on-a-set

I think there should be better algorithm at list for this specific case. Can anyone help?

group-theory permutations algorithms group-actions

share|cite|improve this question

asked Mar 21 at 14:38

AshotAshot

2,62932044

$endgroup$

add a comment | 

$begingroup$

Let $N$ be $1,ldots,n$, $R=1,ldots,r$. Consider mappings from $N$ to $R$. It is clear that there are $r^n$ such mappings.

Let $G_n$ be the group generated by $n$ length cycle permutation $alpha=(1,ldots,n)$. $G_n$ contains all powers of $alpha$.

One can see that the group $G_n$ acts on the set of mappings in the following way.
Let $alpha^kin G_n$ and $f:Rmapsto N$.

$alpha^k(f)$ would be the following mapping $(alpha^k(f))(i)=f(alpha^k(i))$.

We can use Bernside's lemma to find number of orbits. Now I need to find algorithm to find orbits. By finding orbits I mean finding set or representatives from each orbit.

Here is an example:

$n=4, r=2$.

A mapping from $1,2,3,4$ to $1,2$ can be represented by a vector $(f(1),f(2),f(3),f(4))$.

Group $G_4$ would be $(1234),(13)(24),(1342),e$

One can see that there are following $6$ orbits:

$(1,1,1,1)$

$(2,2,2,2)$

$(1,1,1,2),(1,1,2,1),(1,2,1,1),(2,1,1,1)$

$(2,2,2,1),(2,2,1,2),(2,1,2,2),(1,2,2,2)$

$(2,2,1,1),(2,1,1,2),(1,1,2,2),(1,2,2,1)$

$(2,1,2,1),(1,2,1,2)$

A set of representatives would be the first column.

As a algorithm one can choose the following. Mark all mappings unchecked. At each step get one unchecked mapping, put it in representation set, act group $G_n$ on it, get all resulting mappings and make them checked. Continue until all elements are checked.

I have posted general question for this problem here https://mathoverflow.net/questions/325839/find-representation-set-of-orbits-when-group-acts-on-a-set

I think there should be better algorithm at list for this specific case. Can anyone help?

group-theory permutations algorithms group-actions

share|cite|improve this question

asked Mar 21 at 14:38

AshotAshot

2,62932044

$endgroup$

share|cite|improve this question

asked Mar 21 at 14:38

AshotAshot

2,62932044

share|cite|improve this question

asked Mar 21 at 14:38

AshotAshot

2,62932044

asked Mar 21 at 14:38

AshotAshot

2,62932044

asked Mar 21 at 14:38

AshotAshot

2,62932044