On the product of two permutations (and its conjugates)

So this is from Charles C. Pinter’s “A Book of Abstract Algebra”- specifically, it’s from the second chapter on permutations. The question is:

Let $ \alpha_1$ and $ \alpha_2$ be cycles of the same length. Let $ \beta_1$ and $ \beta_2$ be cycles of the same length. Let $ \alpha_1$ and $ \beta_1$ be disjoint, and let $ \alpha_2$ and $ \beta_2$ be disjoint. [Prove that] There is a permutation, $ \pi\in S_n$ , such that $ \alpha_1\beta_1=\pi\alpha_2\beta_2\pi^{-1}$ .

That’s the question.

But this is actually the last of a five part question, sooooo here are the previous parts – the parts build on each other and it looks like part 4 (which can be found near the bottom) is of greatest relevance but I can’t quite see how to use it here.

Part 1 was:

Let $ \alpha=(a_1,…,a_s)$ be a cycle and let $ \pi$ be a permutation in $ S_n$ . Then $ \pi\alpha\pi^{-1}$ is the cycle $ (\pi(\alpha_1),…,\pi(\alpha_s))$ .

(a solution can be found here Proof for conjugate cycles)

Part 2 was:

Conclude from part 1: Any two cycles of the same length are conjugates of each other.

The idea here is not too hard to formulate and some formalization is given in a hint which suggests defining a permutation, $ \pi$ , as sending any element not in either cycle to itself, sending all of the elements of one of the cycles, denoted by A, to the other, denoted by B. Finally, define $ \pi$ over B-A as some bijection between B-A and A-B. Now, it is easy to show that $ \pi$ is a permutation and by part 1, that’s enough.

Parts 3 and 4 are straightforward.

Part 3:

If $ \alpha$ and $ \beta$ are disjoint cycles, then $ \pi\alpha\pi^{-1}$ and $ \pi\beta\pi^{-1}$ are disjoint cycles.
(this follows directly from part 1)

And Part 4:

Let $ \sigma$ be a product $ \alpha_1…\alpha_t$ of t disjoint cycles of lengths $ l_1,…,l_t$ , respectively. Then $ \pi\sigma\pi^{-1}$ is also a product of t disjoint cycles of lengths $ l_1,…,l_t$ .
(an easy generalization of part 3)

In the fifth part, I see how one can find a $ \pi$ such that $ \alpha_1=\pi\alpha_2\pi^{-1}$ . I also see how one can find a $ \pi$ such that $ \beta_1=\pi\beta_2\pi^{-1}$ (we can get this via an immediate application of part 2). What I can’t see is how we can ensure that these two $ \pi$ ‘s will be the same (which is what the question seems to be asking). I also can’t see how to use Part 4 here as, on its own, it doesn’t seem enough- it looks to me like we would need, in addition, to show that the act of taking a conjugate could be made ‘onto’ in a sense (and I don’t get how to do that).

Any help appreciated.

Are there proven cases of permutations of the Satake parameters being actually isometries ?

This is a follow-up to that rather old question of mine : Would a proof of Ramanujan Conjecture together with other known results about automorphic L-functions imply the Grand Riemann Hypothesis?

I would like to know if there are known cases of such automorphic L-functions for which it is proven that any permutation of its Satake parameters defined for a given finite place is an isometry of the complex plane.

Odd permutations $\tau\in S_n$ with $\sum_{k=1}^nk\tau(k)$ a square

For any positive integer $ n$ , as usual we let $ S_n$ be the symmetric group of all the permutations of $ \{1,\ldots,n\}$ .

QUESTION: Is it true that for each integer $ n>3$ there is an odd permutation $ \tau\in S_n$ such that $ \sum_{k=1}^n k\tau(k)$ is a square?

Let $ a(n)$ denote the number of odd permutations $ \tau\in S_n$ with $ \sum_{k=1}^nk\tau(k)$ a square. Via a computer I find that $ $ (a(1),\ldots,a(11))=(0,1,0,2,8,22,82,718,4583,53385,513897).$ $ For example, $ (2,4,1,3)$ and $ (3,1,4,2)$ are the only two odd permutations in $ S_4$ meeting our requirement; in fact, $ $ 1\cdot2+2\cdot4+3\cdot1+4\cdot3=5^2\ \ \text{and}\ \ 1\cdot3+2\cdot1+3\cdot4+4\cdot2=5^2.$ $ For $ n=2,3,4,5$ , there is no even permutation $ \tau\in S_n$ such that $ \sum_{k=1}^nk\tau(k)$ is a square.

I conjecture that the question has a positive answer. Any comments are welcome!

Find the number of permutations of $(1,2,…,n)$ so that they can be sorted in $k$ runs


Find the number of permutations $ (p_1,p_2,…,p_n)$ of $ (1,2,…,n)$ such that they are sorted (in ascending order) in at most $ k$ runs.

A run is defined as :

for ($ i=1$ to $ n-1$ ) do

if ($ p_i > p_{i+1}$ ) then

swap ($ p_i, p_{i+1}$ )

end if

end for

This is probably doable by recursion though I’m not sure of that. Define the number of permutations of $ n$ numbers in $ k$ runs by $ f(n,k)$ . For the case of $ k=1$ , we get the recursion $ f(n,1)=f(n-1,1)f(0,0)+f(n-2,1)f(1,0)+ \cdots +\cdots = 2^{n-1}$ . And it’s not hard to deduce the answer. I’m not sure how to generalize this. I have noted that $ f(p,p)=p!$ for any natural number $ p$ . That’s obvious because $ \{p,p-1, \cdots , 1\}$ gets sorted ($ j^\text{th}$ run takes the respective element to its respective location) and since that’s the worst possible case, any other case will also get sorted. Note that the answer to this problem is $ k! (k+1)^{n-k}$ . Now, an element $ j$ can go to any location b/w $ 1$ and $ j+k$ such that after it moves to some location $ l$ , any number between these two elements can be sorted in $ k-1$ runs. Considering all these in mind, I am not sure how to get a recursive or a non recursive solution.

The answer, if represented in the form $ f(n,k)$ can be written as $ f(n,k)=(k+1)f(n-1,k)$ for $ n-1 > k$ and then going recursively, we will get to the step when $ f(k,k)=k!$ and we will be done. But I’m not sure if this particular recursive relation will help solve this problem. It’s just that I observed it, I’m not sure if that would help.