Sunday, September 6, 2015

Flipping the number line

Here is a number line. It looks funny because I did two things: first, I stretched and compressed different parts so I could fit all the numbers in. Second, I rolled it into a circle.

All the numbers are in there. Most of them are really crammed near the top.

What happens to the number line if you apply a linear fractional transform? Here I apply 1/x:

1/x flips the entire diagram vertically. (What happens if you apply -x?)

In this example, I apply x + 1:

The numbers in the circle rotate clockwise, but not exactly linearly. The negative numbers are compressed and the positive numbers expanded.

There are, of course, an unlimited number of linear fractional transformations I can apply to my number line, but they all act by flipping or rotating the number line in some manner. We can derive every transform by a sequence of flips and rotates. Can we find a basic set of operations from which we can construct all the rest?

We can enumerate all the linear fractional transforms the same way we enumerate all rational numbers. We conceptually make a table of all of them, but we walk the table diagonally. There are four integers per linear fractional transform, rather than the two in a rational number, but that makes only a minor difference. It seems likely that our basic set of operations will be found in the set of linear fractional transforms with small integers for coefficients. If we use the positive and negative integers with absolute value of four or less, we'll have a good sized set to start with. Just from the combinatorics, we'd expect (expt 9 4) possible ways to list them, but many of these are duplicates. Nonetheless, there are still 2736 unique linear fractional transforms with coefficients that have an absolute value of four or less.

(I'm tired of typing "linear fractional transform". I'm going to abbreviate it lft.)

What happens if you compose an lft with itself? Obviously constants and identity remain unchanged, but the other ones are more interesting. These lfts are self inverses. If you compose them with themselves, you get the identity:

#[linear-fractional-transform 20 -x]
#[linear-fractional-transform 14 1/x]
#[linear-fractional-transform 13 -1/x]
#[linear-fractional-transform 227 x/(x - 1)]
#[linear-fractional-transform 226 -x/(x + 1)]
#[linear-fractional-transform 225 -(x + 1)]
#[linear-fractional-transform 224 (1 - x)]
#[linear-fractional-transform 223 (x + 1)/(x - 1)]
#[linear-fractional-transform 222 (1 - x)/(x + 1)]
These ones are not identities when you compose them twice (lft/compose x x), but they are identities if you compose them three times (lft/compose x x x)
#[linear-fractional-transform 522 1/(1 - x)]
#[linear-fractional-transform 521 -1/(x + 1)]
#[linear-fractional-transform 397 -(x + 1)/x]
#[linear-fractional-transform 396 (x - 1)/x]
These two are examples that require four composes
#[linear-fractional-transform 528 (x + 1)/(1 - x)]
#[linear-fractional-transform 527 (x - 1)/(x + 1)]

And these examples require six:

#[linear-fractional-transform 59 (x + 1)/(2 - x)]
#[linear-fractional-transform 58 (x - 1)/(x + 2)]
#[linear-fractional-transform 57 (2x + 1)/(1 - x)]
#[linear-fractional-transform 56 (2x - 1)/(x + 1)]
#[linear-fractional-transform 55 1/(3 - 3x)]

I have not seen an lft that gives the identity when composed with itself five times, nor seven, or eight.

Some lfts never self compose to identities. Obviously repeated self composition of x+1 will never equal the identity.