As with the usual Farey sequence, you can profitably think of these as lattice vectors like (0,1) and (1,1) instead of fractions. The rational number is the slope. When you subdivide the interval [p/q, r/s] into three subintervals by inserting two new values, you can interpret it as starting with the 2x2 matrix M with columns (p,q) and(r,s), and getting three new matrices (<--> intervals) M A, M B, M C where A has columns (1,0) and (2,1), B has columns (2,1) and (1,2), and C has columns (1,2) and (0,1). In other words, you're looking at orbits of two vectors under the semigroup generated by three integer matrices. Since B has determinant 3, you can't get all primitive lattice points (primitive <--> lcd of entries is 1) with odd denominator: inthe process, you subdivide the initial 45 degree angle into finer and finer angles, each with a certain word in the semigroup as suffix. The determinant of this suffix is 3^(number of B's), whose image is a sublattice of high index, so the lattice points you get have low density. But primitive lattice points with odd 2nd element have an approximately uniform density*, so any high-index lattice misses most of them. *This is a well-known fact, with an easy argument, using a sieve just as for primes: first strike out that half of the lattice points that have even 2nd entries; then strike out the 1/4 of lattice points that are divisible by 2; the independent 1/9 of lattice points divisible by 3; the 1/25 divisible by 5; etc. Since the series 1/prime(i)^2 converges, so you end up striking out a fraction < 1. Here's a plot of the rational numbers obtained up through the 9th iteration the subdivision rule, where the x coordinate gives the position in the list. It appears that there are even gaps in the image in R, but I'm too lazy to check right now ---but it's an exercise in hyperbolic geometry, if someone wants to do it. http://dl.dropbox.com/u/5390048/ProppAddition.jpg Bill On Dec 9, 2010, at 6:10 PM, James Propp wrote:

It's well-known that if you start with the list of fractions 0/1, 1/1 and successively interpose the mediant (a+c)/(b+d) between successive elements a/b and c/d of the list, every rational between 0 and 1 will eventually appear.

I just tried a variant of this today in which I interpose the weighted mediants (2a+c)/(2b+d) and (a+2c)/(b+2d) instead, like this:

0/1, 1/1 0/1, 1/3, 2/3, 1/1 0/1, 1/5, 2/7, 1/3, 4/9, 5/9, 2/3, 5/7, 4/5, 1/1 ...

Does every rational between 0 and 1 with odd denominator eventually appear?

I've checked this up through denominator 9.

Also, if one instead interposes the weighted mediants (4a+c)/(4b+d), (3a+2c)/(3b+2d), (2a+3c)/(2b+3d), and (a+4c)/(b+4d), one does NOT obtain every rational between 0 and 1 with odd denominator; for instance, 1/3 never appears. Is there a nice way to characterize those rationals that do appear?

Jim Propp

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun