Challenge III: Rational Tangles, solved by pwsnafu

[micromass]

The newest challenge is the following:

Challenge:
Define the functions $R(x)= -1/x$ and $T(x)=x+1$. Let $q$ and $q^\prime$ be two rational numbers. Prove that we can go from $q$ to $q^\prime$ in finitely many steps by applying $T$ and $R$ in a certain combination.

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$.

 

[pwsnafu]

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.

 

[Number Nine]

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 \Gamma of transformations of the upper half-plane. Answering the question amounts to proving that \Gamma acts transitively on \mathbb{Q}.

 

[lurflurf]

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?

 

[Number Nine]

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?

Surely a challenge question would require the reader to derive facts like the above for themselves.

 

[pwsnafu]

Surely a challenge question would require the reader to derive facts like the above for themselves.

I found deriving that equation quite fun. So I'm glad micro didn't write that.

 

[verty]

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.

 

[micromass]

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?

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!

 

[TheShrike]

Challenge V: Sylvester-Gallai Theorem, solved by Mandelbroth

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.

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.

 

[micromass]

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.

Should work now.