0
$\begingroup$

It is given a permutation $$\alpha=\left( \begin{array}{cccccccccc} 1&2&3&4&5&6&7&8&9&10 \\ 7&6&5&9&10&2&1&4&8&3 \\ \end{array} \right).$$ Can equations $\pi^{29}=\alpha,$ $\pi^{30}=\alpha,$ $\pi^{31}=\alpha$ and $\pi^{32}=\alpha$ be solved? Can someone explain me the way to solve this task?

$\endgroup$
  • $\begingroup$ Needs some definitions. What is $\pi$? $\endgroup$ – motherboard Jan 12 at 5:42
  • $\begingroup$ $\pi$ is also a permutation we have to find. $\endgroup$ – math_ Jan 12 at 8:14
1
$\begingroup$

Here is a starter. It is convenient to look at the cycle notation of $\alpha$: \begin{align*} \color{blue}{\alpha=(1\ 7)(2\ 6)(3\ 5\ 10)(4\ 9\ 8)}\tag{1} \end{align*} We see $\alpha$ consists of two involutions $(1\ 7)$ and $(2\ 6)$ which have order two and two cycles of length $3$ which have order $3$, namely \begin{align*} (1\ 7)^2=\varepsilon\qquad\qquad&(3\ 5\ 10)^2=(3\ 10\ 5)\\ &(3\ 5\ 10)^3=\varepsilon\tag{2}\\ (2\ 6)^2=\varepsilon\qquad\qquad&(4\ 9\ 8)^2=(4\ 8\ 9)\\ &(4\ 9\ 8)^3=\varepsilon\\ \end{align*} with $\varepsilon$ the identity permutation.

From (1) and (2) we see $\alpha^{30}=\varepsilon$ and consequently \begin{align*} \color{blue}{\alpha^{31}}=\alpha^{30}\circ \alpha=\varepsilon\circ \alpha\color{blue}{=\alpha} \end{align*}

We also derive from (2) \begin{align*} (3\ 10\ 5)^{29}&=(3\ 5\ 10)^{58}=(3\ 5\ 10)^{3\cdot19+1}=(3\ 5\ 10)\\ (4\ 8\ 9)^{29}&=(4\ 9\ 8)^{58}=(4\ 9\ 8)^{3\cdot19+1}=(4\ 9\ 8)\\ (1\ 7)^{29}&=(1\ 7)^{2\cdot 14+1}=(1\ 7)\\ (2\ 6)^{29}&=(2\ 6)^{2\cdot 14+1}=(2\ 6)\\ \end{align*}

It follows: \begin{align*} \color{blue}{((1\ 7)(2\ 6)(3\ 10\ 5)(4\ 8\ 9))^{29}=\alpha} \end{align*}

$\endgroup$
0
$\begingroup$

Permutation can be represented as the product of cycles, where two cycles do not have common elements, as in

$$\alpha=(1\ 7)(2\ 6)(3\ 5\ 10)(4\ 9\ 8)$$

Some properties of permutations and cycles:

The length of a cycle $\gamma$ we denote $l(\gamma)$. So $l((1\ 7))=2$ and $l((3\ 5\ 10))=3$. If a permutation is represented by $n$ (pairwise disjoint) cycles $$\gamma_1\gamma_2\ldots \gamma_n$$ then $$(\gamma_1\gamma_2\ldots \gamma_n)^k=\gamma_1^k\gamma_2^k\ldots \gamma_n^k\tag {1.1}$$

The permutation $\gamma_i^k$ must not be a cycle. It may be the product of more than one cycle. But the following holds, if $\gamma$ is a cycle and $k$ is a prime:

  • If not $k|l(\gamma)$, then $$\gamma^k=\delta \tag {1.2}$$ where $\delta$ is a cycle and $l(\delta)=l(\gamma)$.

  • If $k|l(\gamma)$, then $$\gamma^k=\gamma_1\gamma_2\ldots \gamma_k \tag {1.3}$$ where all $\gamma_i$ are cycles and $l(\gamma_i)=l(\gamma)/k$.

If $\pi$ is a permutation and $a,b,c\in \mathbb{Z}$ then following properties hold:

$$\pi^{ab+c}={(\pi^a)}^b \pi^c\\ \pi^0=\textrm{id}\\ \pi^{-1}=\pi^* \tag {1.4}$$ where $\textrm{id}$ is the identity and $\pi^*$ is the inverse permutation. If $\pi$ is a permutation of $n$ elements then $$\pi^{n!}=\textrm{id}$$ holds and if $\gcd(k,n!)=1$ then there exists a $k'$ such that $$k\cdot k'\equiv 1\pmod{n!} \tag{1.5}$$ and therefore $$(\pi^k)^{k'}=\pi$$.

For a cycle $\gamma$ we have $$\gamma^{l(\gamma)}=\textrm{id}$$


Now let's solve $$\pi^{29}=\alpha \tag{2.1}$$

We have $$\alpha^6=\textrm{id}$$ and so $$(\pi^{29})^6=\alpha^6=\textrm{id}$$ and by raising to the power $29'$. The symbol $'$ is defined in $(1.5).$ But $$(\pi^{29})^{29'}=\pi$$ so we get $$\pi^6=\textrm{id}$$ we have$$\pi^{29}=(\pi^6)^{24}\pi^5=\pi^5$$ and so from from $(2.1)$ we get $$\pi^5=\alpha$$ $$\textrm{id}=\alpha\pi$$ and $$\pi=\alpha^{-1}$$ So $$\pi=(1\ 7)(2\ 6)(3\ 10\ 5)(4\ 8\ 9)$$ is the unique solution of $(2.1).$

The equation $$\pi^{31}=\alpha \tag{2.3}$$ can be processed in a similar way.

To solve $$\pi^{30}=\alpha \tag{2.2}$$

we transform it to $$(\pi^{15})^2=\alpha$$

We first try to solve $$\rho^2=\alpha$$ $\rho$ is a square root of $\alpha$.

The cycles $$(3\ 5\ 10)(4\ 9\ 8)$$ of $\alpha$ can be generated by two cycles of length $3$ according to $(1.2)$ or by a cycle of length $6$ according to $(1.3)$ The cycles $$(1\ 7)(2\ 6)$$ of $\alpha$ can only be generated by a cycle of length $4$

So $$\rho=\phi\psi$$ where either $$\phi=(1\ 2\ 7\ 6)$$ or $$\phi=(1\ 6\ 7\ 2)$$ and where $$\psi=(3\ 10\ 5)(4\ 8\ 9)$$ or $$\psi=(3\ 4\ 5\ 9\ 10\ 8)$$ or $$\psi=(3\ 9\ 5\ 8\ 10\ 4)$$ or $$\psi=(3\ 8\ 5\ 4\ 10\ 9)$$

By combining all possible $\phi$ and $\psi$ we get $8$ different square roots $\rho$.

In the next step we want to solve $$\sigma^3=\rho$$ for the square root $\rho$.

But $$(1\ 2\ 7\ 6)(3\ 10\ 5)(4\ 8\ 9)$$ does not have a third root because the cycles $(3\ 10\ 5)(4\ 8\ 9)$ do not have one according to $1.1$ and $1.2$ and $1.3.$ Similar holds for the other seven square roots $\rho.$

In a similar manner it can be shown that $(2.4)$ has no solutions.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.