Mapping rationals to binary strings while preserving order

Hello all!

Consider the following problem: we want to find a function
that maps rational numbers from the range [0, 1] into binary strings.
The function f should satisfy the condition that, for any two
rational numbers x, y, 0 <= x < y <= 1, the string f(x) should be
lexicographically less than f(y).

One suitable mapping is this: for a rational number u/v, where 0 <= u <= v
and gcd(u, v) = 1, consider the sequence
floor(i u/v) - floor((i-1) u/v) for i = 1, 2, ..., v.
Each of these values is either 0 or 1, and concatenating them we get a
string of v bits. If we define f(u/v) to return this string, it can be
shown that it has the property required in the first paragraph.

For example:
fraction value string
0/ 1 0.000000 0
1/ 9 0.111111 000000001
1/ 8 0.125000 00000001
1/ 7 0.142857 0000001
1/ 6 0.166667 000001
1/ 5 0.200000 00001
2/ 9 0.222222 000010001
1/ 4 0.250000 0001
2/ 7 0.285714 0001001
1/ 3 0.333333 001
3/ 8 0.375000 00100101
2/ 5 0.400000 00101
3/ 7 0.428571 0010101
4/ 9 0.444444 001010101
1/ 2 0.500000 01
5/ 9 0.555556 010101011
4/ 7 0.571429 0101011
3/ 5 0.600000 01011
5/ 8 0.625000 01011011
2/ 3 0.666667 011
5/ 7 0.714286 0110111
3/ 4 0.750000 0111
7/ 9 0.777778 011101111
4/ 5 0.800000 01111
5/ 6 0.833333 011111
6/ 7 0.857143 0111111
7/ 8 0.875000 01111111
8/ 9 0.888889 011111111
1/ 1 1.000000 1

The mapping from the previous paragraph requires a string of length v
bits to represent the fraction u/v. But if we didn't have the requirement
that x < y should imply f(x) < f(y), we know that we could represent the
fraction u/v using only O(log v) bits. So what I'm curious about is
this: can we make our strings shorter than O(v) bits and yet satisfy the
requirement that the ordering is preserved (i.e. that x < y implies
f(x) < f(y))? How would one go about looking for such a construction (or
proving that it can't be done)?

-----
Janez




.

Relevant Pages