On Wednesday, March 5, 2003, at 12:00 PM, Dylan Thurston wrote:
On Wed, Mar 05, 2003 at 08:22:31AM -0800, Bill Thurston wrote:
I've kept quiet about the discussion of different bases --- there's a whole lot that is known about these kinds of questions.
Do you kow some good references? (Besides Knuth Vol. 1)
I only wrote up lecture notes for some AMS talks I gave, which aren't in print. I'm not sure what the current best references are, but Rick Kenyon in particular pursued this line of investigation further, and wrote a number of papers. One key-word is self-similar tilings, i.e. tilings of the line or the plane with finitely many tile types where each tile can be subdivided into similar copies, with some given expansion constant \lambda. The various bases correspond to tilings with finitely many tiles up to translation.
.... As another example--- in base 5, the digits {-3, 0, 1, 3, 4} at least uniquely give all positive numbers. ... can you characterize which sets of digits "work" for integer bases?
Before I think about this too much, is this an open research problem, or is the answer known? I don't know the full answer; I'm not sure it's not known, and if it is I don't think I've heard the answer. For any particular set of digits it's a finite check, but I don't know whether or not the answers have a simple characterization.
One motivation is that for complex bases, there is no canonical choice of digits. BTW, a while ago I gave a characterization of those real or complex bases for which there is an almost-always unique representation of any number given by finite-state rules: this can be done if and only if the base is an algebraic integer whose Galois conjugates are not larger (in modulus) than itself.
Nice! What are the assumptions? Do you assume that the digits are all integers, or is that irrelevant?
I guess typically you'd use algebraic integer digits---but that's not necessary as an assumption.
There's even a more general context, where you allow the "place-shifting" operation to be something more general than multiplication by the base b. One good general context is to pick a set of elements of PSL2R or PSL2C as your "digits". As far as I kno this generalisation has mostly been studied by people interested in real computation, where unique representations are not desirable, since it may require an unbounded amount of computation to produce the next digit. I believe there are many open questions here; in particular, I don't think digits in PSL2C have been studied much at all. One theory of this sort is the theory of automatic groups and automatic semigroups, which is actually how I first got interested in the subject. I.e. if the "digits" are generators of a lattice in PSL(2,R) or PSL(2,C) then there are good forms for representations of "numbers" i.e. points on the real or complex projective plane. Cf. "Word-processing on groups" by Epstein et al. <-- that little abbreviation includes me, also cf. Derek Holt's web site maths.warwick.ac.uk/~dfh (I think) for some software; there's also a lot of other literature and software.
Best, Bill