Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge III: Rational Tangles, solved by pwsnafu

  1. Aug 5, 2013 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The newest challenge is the following:

    As an example, we can easily go from ##0## to ##-1/3##. Indeed, we can apply ##T## to ##0## to go to ##1##, we apply ##T## to go to ##2##, we apply ##T## to go to ##3##, and then we apply ##R## to go to ##-1/3##.
     
    Last edited by a moderator: Aug 8, 2013
  2. jcsd
  3. Aug 5, 2013 #2

    pwsnafu

    User Avatar
    Science Advisor

    Might as well start.

    Well ##R^{-1} = R## and ##T^{-1} = RTRTR## so that shows we can invert any combination.
    Secondly, observe
    ##T^c R T^b R T^a (0) = c - \frac{1}{b - \frac{1}{a}},##
    and in general
    ##T^{k_1} R T^{k_2} \ldots T^{k_n}(0) = k_1 - \frac{1}{k_2 - \frac{1}{\ldots - \frac{1}{k_n}}}##
    We get something similar to continued fractions, the only difference being the subtractions instead of additions. But every positive rational number can be written in this form for the same reason that every rational can be written as a continued fraction (just change "integer part" to "integer part + 1" in the algorithm). So we can map 0 to any positive rational. R'ing that means we get every negative rational.

    Hmm, there's probably something left to prove. Oh well.
     
  4. Aug 5, 2013 #3
    Posting an answer would be kind of cheating, since I've encountered it before. Someone might be interested to know that T and R are generators of the modular group [itex]\Gamma[/itex] of transformations of the upper half-plane. Answering the question amounts to proving that [itex]\Gamma[/itex] acts transitively on [itex]\mathbb{Q}[/itex].
     
  5. Aug 6, 2013 #4

    lurflurf

    User Avatar
    Homework Helper

    Further insight into micro's hatred of Wikipedia and arithmetic. Clearly we have a group whose action on 0 generates Q. As pwsnafu points out we can use continued fractions. It was quite a macro oversight not to provide the reader with
    $$T^{-1}=RTRTR=x-1$$
    Don't you like to subtract?
     
    Last edited: Aug 6, 2013
  6. Aug 6, 2013 #5
    Surely a challenge question would require the reader to derive facts like the above for themselves.
     
  7. Aug 6, 2013 #6

    pwsnafu

    User Avatar
    Science Advisor

    I found deriving that equation quite fun. So I'm glad micro didn't write that. :approve:
     
  8. Aug 6, 2013 #7

    verty

    User Avatar
    Homework Helper

    The following algorithm takes any rational number to a natural number:

    1. If a/b is a natural number, stop.
    2. Else if a/b < 0, apply T.
    3. Else if a/b > 0, apply R.
    4. Repeat.

    The only way this could fail to terminate is if it gets stuck in a rule or cycles continuously. Getting stuck in rule 2 is not possible by the Archimedean property of the integers. Getting stuck in rule 3 is not possible because it takes positive numbers to negative numbers. Cycling from rule 2 to 3 and back again is not possible because the first positive number after a chain of rule T's will be < 1, therefore rule R will reduce the size of the denominator. Eventually, it'll reduce it to 1. This is sufficient to show that the algorithm terminates.

    To extend this, given any two rational numbers, apply the algorithm to each giving two natural numbers N < M. Apply T finitely many times to transform N into M. Then, if R and T are invertible, invert the process that generated M and voila.
     
  9. Aug 6, 2013 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Not sure why you think I should give a partial solution in a challenge question...

    Anyway, very big congratulations to pwsnafu for giving such a short and elegant solution. And of course, a congratulations to verty as well for providing a more elementary solution. I hope you enjoyed it.

    For a cool application of this question to knot theory, anybody interested can go to:
    http://nrich.maths.org/5776
    http://www.geometer.org/mathcircles/tangle.pdf

    A new question will be up shortly!!
     
    Last edited: Aug 6, 2013
  10. Aug 6, 2013 #9
    Challenge V: Sylvester-Gallai Theorem, solved by Mandelbroth

    I didn't get anywhere with it, but I'm pleased to find I was going in this very direction. I just didn't know how to show it.

    Also, micromass, your second link is giving me a 404 Not Found error.
     
  11. Aug 6, 2013 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Should work now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook