1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Two Conjectures about Permutations in ##S_n##

  1. Dec 14, 2016 #1
    1. The problem statement, all variables and given/known data
    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##.

    2. Relevant equations


    3. 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!
     
  2. jcsd
  3. Dec 14, 2016 #2

    fresh_42

    Staff: Mentor

    Looks good, except one point: Why there has to be an element ##a##?
    (I know why, but you should mention this (im-)possibility.)
    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##.
     
  4. Dec 18, 2016 #3
    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?
     
  5. Dec 18, 2016 #4

    fresh_42

    Staff: Mentor

    I agree.
    ##(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.
    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.)
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Two Conjectures about Permutations in ##S_n##
Loading...