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)
.... 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?
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? 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 know, 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. Best, Dylan