The sum of orbit size of some element over the image of group "polynomial"

Question

$\DeclareMathOperator{\orb}{orb}$ Say I have a group "polynomial", $p$, on $S_n$, that is $p(x)=a_1 x^{\epsilon_1}...a_n x^{\epsilon_n}$ for all $x \in S_n$, fixed $a_i \in S_n$ and fixed $\epsilon_i \in \mathbb{Z}$. We will be considering $S_n$ with the natural action on $\{1,...,n\}$, $g \cdot i = g(i)$ for $i \in \{1,...,n\}$. Let $p S_n$ be the image of the polynomial. Generally, I am looking for $$ X(S_n,p,i)=\sum_{y \in p S_n} |\orb( \langle y \rangle, i)| $$ where $i \in \{1,...,n\}$ and $\orb(G,i)$ is the orbit of $i$ in $G$, or in the particular case we are looking at $\{j \mid g \in \langle y \rangle, j=g(i) \}$. For example, $p(x)=(1,2,3)x(1,2,3)x^{-1}$, then $p S_3=\{ (),(1,3),(1,3,2)\}$ and $$\begin{align*} X(S_3,p,1)&=X(S_3,p,3)=1+2+3=6, \\ X(S_3,p,2)&=1+1+3=5. \end{align*}$$

For these questions I mostly interested in references, although if you can prove it and don't know of a reference then I am happy with that too.

1. I have a particular interest in how to calculate $X(S_n,p,i)$ when $a\in S_n$ is such that $\orb( \langle a \rangle,i)=\{1,...,n\}$, $p(x)=axa^{-1} x^{-1}$ without calculating each image and adding up. Note that each element in the image has multiplicity $n$ and so there are $(n-1)!$ elements in the image.

2. Are there general ways to calculate $X(S_n,p,i)$ when I know the "coefficients" and the exponents on $x$ without just calculating each term?

3. Question "2." except generalize these notions to general (finite) groups and group actions.

4. Results on (non-trivial) upper and lower bounds for $X(S_n,p,i)$.

For question 1. I suspect that figuring out for particular $a$, like $(1,...,n)$, and for $i \in \{1,...,n\}$, since we can look at conjugations of the polynomial, although I have not thought much about how that permutes the $i$: what $i,j$ gives $X(S_n,p,i)=X(S_n,bpb^{-1},j)$.

Answer 1

since I can't comment I'll write it up here. You have probably done it too, but I cant know that so I'll present my findings.

First of all there is an error in your example, $pS_3$ should be $\{ (),(132)\}$, I checked it in Mathematica.

Now, obviously when $p(x)=axa^{-1} x^{-1}$ acts on $S_n$ we get some subset of commutator subgroup of $S_n$, that is, some subset of $A_n$. That subset is dependent on which $a\in S_n$ we choose. Doing some calculations I found, there is some order in all this, all $a$'s from the same conjugacy class give simmilar subsets i.e. they all have the "same" elements up to a conjugacy class of a particular element. (proof is easy)

Now, if you could determine the cyclic structure and number of all elements in those subsets you could easily calculate your sum. I was unable to do so, but I did do some heuristics for $a$ of specific cycle type and $i=1$.

Example:

$a=(12)$, $i=1$ , $S_n$, $p(x)=(12)x(12)^{-1} x^{-1}$

$X(S_n,p,i)= 2(n-2)3 + 2{n-2 \choose 2} +1 $

and for $a=(123)$

$X(S_n,p,i)= (2(n-3)+1)3 + 5{n-3 \choose 2}6 + 3(n-3)2 + 2{n-3 \choose 3}3 + (n+3) +1 $

As you can see there might be some formula for this, but just don't have time to research on this. Also this is valid only for $a$ containing the point $i=1$, those cycles whith the same type but without $i=1$ for example (2,3) or (2,3,4), produce different formulae (sort of splitting in conjugacy class of $a$), which is expected. I got this by inspecting the subsets generated by all $a$'s from the conjugacy class, for first 10 symmetric groups, beyond that my computer is too slow.

I did this just to show how complicated, and interesting this is. It sure would be nice to see some general formula for this, but it is out of my reach.

sym = GroupElements[SymmetricGroup[4]];
tz = DeleteDuplicates[Table[PermutationProduct[Take[sym, {i}][[1]],Cycles[{{1, 2, 3}}],InversePermutation[Take[sym, {i}][[1]]]], {i, 1, 4!}]]
TableForm[Table[Sort[DeleteDuplicates[Table[PermutationProduct[Take[tz, {k}][[1]],Take[sym, {i}][[1]],InversePermutation[Take[tz, {k}][[1]]],InversePermutation[Take[sym, {i}][[1]]]], {i, 1, 4!}]]], {k, 1,Length[tz]}]]

$tz$ is a conjugacy class of $(123)$ cycle type permutation. Rows in the generated table are those subsets you get for specific $a$ from conjugacy class. From this you can find heuristically how may elements will have a specific cycle type, the rest is easy, groups generated by those ellements are always cyclic an computing the orbit is easy.

Also here is the code for computing the sum for specified $S_n, i$ and $a$

sym=GroupElements[SymmetricGroup[4]];
f[k_]:=DeleteDuplicates[Table[PermutationProduct[Take[sym, {k}][[1]],Take[sym,i}][[1]],InversePermutation[Take[sym, {k}][[1]]],InversePermutation[Take[sym,{i}][[1]]]],{i,1, 4!}]];
ab=Table[Table[Length[GroupOrbits[PermutationGroup[Take[f[k], {t}]], {1}][[1]]], {t,1,Length[f[k]]}],{k, 1, 4!}];
Map[Total, ab]

Add this to see how are thise sums distributed on conjugacy classes and observe the splitting in sum value for certain types of conjugacy classes. (In the above code you conjugacy class of cycle type(12) splits between two values, 11 and 15)

Now, if you put your polynomial $p$ to be the conjugation i.e. $p(x)=xa^{-1} x^{-1}$, you can easily calculate the sums.

For some $a\in S_n$ of cyclic type Cm we just count the number of permutations in that conjugacy class that have $i$ inside, multiply it by length of cycle of $a$ that contains $i$ and add up all those trivial orbits of groups generated by elements in conjugacy class that do not contain $i$ (they fix $i$). The sum would be the same for any $i$ (easy proof)

so the sum would be:

$X(S_n,p,i)=$ ((size of conjugacy class of $a$ in $S_n$)-(size of conjugacy class of $a$ in $S_{n-1}$) )*(length of cycle in $a$ that contains $i$) + (size of conjugacy class of $a$ in $S_{n-1}$))

Example:

$S_6$, $i=1$ , $a=(123)(45)$ , $p(x)=xa^{-1} x^{-1}$

sym=GroupElements[SymmetricGroup[6]];
aaa=DeleteDuplicates[Table[PermutationProduct[Take[sym, {i}][[1]],InversePermutation[Cycles[{{1, 2, 3}, {4, 5}}]],InversePermutation[Take[sym, {i}][[1]]]], {i, 1, 6!}]];
Total[Table[Length[GroupOrbits[PermutationGroup[Take[aaa, {t}]], {1}][[1]]],{t,1,Length[aaa]}]]

The sum is 280. Now we look in Symmetric group:S6 for size of conjugacy class of (123)(45) type cycle: it is 120. The size in $S_{n-1}$ is 20. The length of cycle that contains $i=1$ is 3 so:

$(120-20)*3-20 = 280$

Is the same value Mathematica gave us.

In the end, I would like to apologize for not ansewring the question, but I did some research and I wanted to comment. Perhaps you can continue my heuristics and deduce some neat formula if you have time. Also I gave this examples just to show how things gets complicated by adding just one term in your group "polynomial" defined in the beginning, so I believe the is no simple formula your sum just knowing the "coefficients". Also check out the Dihedral group instead of Symmetric and you'll get some nice results (only 3 possible values for your sum). From my formula for sums for polynomial $p(x)=xa^{-1} x^{-1}$ you can get some bounds for sums for $p(x)=axa^{-1} x^{-1}$.