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.