Two Conjectures about Permutations in ##S_n##

[Bashyboy]

Homework Statement

I have two conjectures whose truth I am interested in. The first is, "If $\tau, \sigma \in S_n$ are disjoint, then $\tau \sigma = e$ if and only if $\tau = e$ and $\sigma = e$., where $e$ denotes the identity permutation." The second is, "If $\tau$ and $\sigma$ are disjoint, then $\tau^n$ and $\sigma^n$ are disjoint for every integer $n$.

Homework Equations

The Attempt at a Solution

I think I may have a proof of the first, but I am hoping someone can help me clean it up and clarify a few notions: Suppose that $\tau$ and $\sigma$ are disjoint, satisfying $\tau \sigma = e$. Then $(\tau \circ \sigma)(a) = \tau(\sigma(a)) = a$ for all $a \in \{1,...,n\}$. Let $a$ be a positive integer not appearing in $\sigma$'s cycle decomposition but in $\tau$'s. Then $\tau(\sigma(a)) = a$ or $\tau(a) = a$, which is a contradiction unless $\tau = e$ and therefore $\sigma = e$.

What exactly does it mean for "$a$ not to appear on the cycle decomposition?" I can construe that as meaning $\tau(a) = a$.

Here is an attempt at proving the second conjecture: Suppose that $\tau$ and $\sigma$ are disjoint permutations. When $n=1$, the claim follows trivially. So suppose the claims holds for all such cycles raised to the $n$ power. Then $\tau^{n+1} = \tau^n \tau$ and $\sigma^{n+1} = \sigma^n \sigma$. By the induction hypothesis, $\tau_n$ and $\sigma^n$ are disjoint...

At this point, it seems that I would need something like the following to be true: If $\tau_1$, $\sigma_1$ and $\tau_2$, $\sigma_2$ are pairs of disjoint permutations, then $\tau_1 \tau_2$ and $\sigma_1 \sigma_2$ are disjoint permutations. Before I go any further, however, I would like to have my one proof verified and all these conjectures corroborated.

Thanks!

 

[fresh_42]

Suppose that $\tau$ and $\sigma$ are disjoint, satisfying $\tau \sigma = e$. Then $(\tau \circ \sigma)(a) = \tau(\sigma(a)) = a$ for all $a \in \{1,...,n\}$. Let $a$ be a positive integer not appearing in $\sigma$'s cycle decomposition but in $\tau$'s. Then $\tau(\sigma(a)) = a$ or $\tau(a) = a$, which is a contradiction unless $\tau = e$ and therefore $\sigma = e$.

Looks good, except one point: Why there has to be an element $a$?
(I know why, but you should mention this (im-)possibility.)

If $\tau_1$, $\sigma_1$ and $\tau_2$, $\sigma_2$ are pairs of disjoint permutations, then $\tau_1 \tau_2$ and $\sigma_1 \sigma_2$ are disjoint permutations.

This isn't true, because $\tau_2=\sigma_1$ or $\tau_1=\sigma_2$ could be the case and there is no assumption on them.
Why don't you perform a double induction, first on $\tau^n$ and then on $\sigma^n$? Just an idea, because the statement is also true for different powers. Or operate with the cycle decomposition and commutativity of $\tau$ and $\sigma$.

 

[Bashyboy]

Looks good, except one point: Why there has to be an element aaa?
(I know why, but you should mention this (im-)possibility.)

I am not sure how to justify this. I suppose I would say that, since $\tau \neq e$ and $\sigma \neq e$ (otherwise the claim follows trivially), then at least two integers appear in the cycle decomposition of each permutation. Moreover, since $\tau$ and $\sigma$ are disjoint, then every integer in $\tau$'s cycle decomposition does not appear in $\sigma$'s cycle decomposition. It seems that these two facts coupled together guarantee the existence of at least integer in $\tau$'s decomposition that is not in $\sigma$'s.

Before I offer a proof of the second claim, let me first prove a lemma: If $\tau$ and $\sigma$ are disjoint, then their inverses $\tau^{-1}$ and $\sigma^{-1}$ are disjoint. Assume the hypothesis, but suppose that the inverses are not disjoint. Then there exists an $a$ in both decompositions such that $\tau^{-1}(a) = b$ and $\sigma^{-1}(a) = c$, where $b$ and $c$ are not $a$. Note the following two equations hold if and only if $a = \tau(b)$ and $a = \sigma(c)$. Since $\tau$ and $\sigma$ are bijections, neither can map $a$ to $a$, implying that $a$ appears in the cycle decomposition of both $\tau$ and $\sigma$, contradicting initial assumption. Hence, the inverses must be disjoint.

Now, here is a proof of the second conjecture: We prove that if $\tau$ and $\sigma$ are disjoint, then $\tau^m$ and $\sigma^n$ are disjoint for all integers $m$ and $n$.

First we establish the result for natural numbers through induction. Clearly when $m=n=1$, the claim holds trivially. Now, suppose the claim holds for $m=1$ and some arbitrary $n \in \mathbb{N}$, but suppose that $\tau$ and $\sigma^{n+1}$ not disjoint. Then there exists a natural number $a$ such that $\tau(a) \neq a$ and $\sigma^{n+1}(a) \neq a$ or $\sigma(\sigma^n(a) \neq a$. By hypothesis, $\sigma^n$ and $\tau$ are disjoint, implying $\sigma^n(a) = a$. Hence, $\sigma(a) \neq a$, implying that $a$ appears in $\sigma$'s cycle decomposition, a contradiction.

Hence, we have that if $\tau$ and $\sigma$ are disjoint, then $\tau$ and $\sigma^n$ are disjoint for all $n \in \mathbb{N}$. By symmetry, we also have the conclusion that $\tau^m$ and $\sigma$ are disjoint for all $m \in \mathbb{N}$. Hence, $\tau^m$ and $\sigma^n$ are disjoint for all (strictly speaking, one needs that disjointness is transitive, but I'll just omit that; I have already proven enough). Now we prove it for negative integers.

Suppose that $m,n \in \mathbb{Z}^-$. Then $-m,-n \in \mathbb{N}$, and therefore $\tau^{-m}$ and $\sigma^{-n}$ are disjoint. Finally, by the above lemma, their inverses $\tau^m$ and $\sigma^n$ are disjoint.

Whew! That took quite a long time to type, but it was certainly worthwhile. So, how do these proofs sound?

 

[fresh_42]

I am not sure how to justify this. I suppose I would say that, since $\tau \neq e$ and $\sigma \neq e$ (otherwise the claim follows trivially), then at least two integers appear in the cycle decomposition of each permutation. Moreover, since $\tau$ and $\sigma$ are disjoint, then every integer in $\tau$'s cycle decomposition does not appear in $\sigma$'s cycle decomposition. It seems that these two facts coupled together guarantee the existence of at least integer in $\tau$'s decomposition that is not in $\sigma$'s.

I agree.

Before I offer a proof of the second claim, let me first prove a lemma: If $\tau$ and $\sigma$ are disjoint, then their inverses $\tau^{-1}$ and $\sigma^{-1}$ are disjoint. Assume the hypothesis, but suppose that the inverses are not disjoint. Then there exists an $a$ in both decompositions such that $\tau^{-1}(a) = b$ and $\sigma^{-1}(a) = c$, where $b$ and $c$ are not $a$. Note the following two equations hold if and only if $a = \tau(b)$ and $a = \sigma(c)$. Since $\tau$ and $\sigma$ are bijections, ...

$(12) \in S_3$ is also a bijection, but maps $3$ onto itself, so the argument doesn't apply. However, e.g. $a \notin \tau \Longleftrightarrow \tau(a)=a \Longleftrightarrow \tau^{-1}(a)=a \Longleftrightarrow a \notin \tau^{-1}$ because the cycle decomposition is a decomposition in disjoint cycles so $a$ can appear in at most one cycle and thus cannot be invariant.

... neither can map $a$ to $a$, implying that $a$ appears in the cycle decomposition of both $\tau$ and $\sigma$, contradicting initial assumption. Hence, the inverses must be disjoint.

Now, here is a proof of the second conjecture: We prove that if $\tau$ and $\sigma$ are disjoint, then $\tau^m$ and $\sigma^n$ are disjoint for all integers $m$ and $n$.

First we establish the result for natural numbers through induction. Clearly when $m=n=1$, the claim holds trivially. Now, suppose the claim holds for $m=1$ and some arbitrary $n \in \mathbb{N}$, but suppose that $\tau$ and $\sigma^{n+1}$ not disjoint. Then there exists a natural number $a$ such that $\tau(a) \neq a$ and $\sigma^{n+1}(a) \neq a$ or $\sigma(\sigma^n(a) \neq a$. By hypothesis, $\sigma^n$ and $\tau$ are disjoint, implying $\sigma^n(a) = a$. Hence, $\sigma(a) \neq a$, implying that $a$ appears in $\sigma$'s cycle decomposition, a contradiction.

The fact, that $\tau$ and $\sigma$ are disjoint can be written as $\forall b \, : \,\tau(b) \neq b \Rightarrow \sigma(b) = b$.
(I only mentioned this as a remainder for me, because I can better grasp it in this notation.)

Hence, we have that if $\tau$ and $\sigma$ are disjoint, then $\tau$ and $\sigma^n$ are disjoint for all $n \in \mathbb{N}$. By symmetry, we also have the conclusion that $\tau^m$ and $\sigma$ are disjoint for all $m \in \mathbb{N}$. Hence, $\tau^m$ and $\sigma^n$ are disjoint for all (strictly speaking, one needs that disjointness is transitive, but I'll just omit that; I have already proven enough). Now we prove it for negative integers.

Suppose that $m,n \in \mathbb{Z}^-$. Then $-m,-n \in \mathbb{N}$, and therefore $\tau^{-m}$ and $\sigma^{-n}$ are disjoint. Finally, by the above lemma, their inverses $\tau^m$ and $\sigma^n$ are disjoint.

Whew! That took quite a long time to type, but it was certainly worthwhile. So, how do these proofs sound?

Under the assumption I didn't get lost in the middle, yes. But strictly speaking: disjointness isn't transitive:
$((12),(34)) = 1 \wedge ((34),(15))=1 \wedge ((12),(15)) \neq 1$.

I'm sure it could be seen in a shorter way, e.g. by the equivalences I wrote above. But at least it was a good exercise - although I feel a bit dizzy now.