Unusual digit sets that allow finite expansions for all (positive and negative) integers

Question

Informal introduction

(If you don't like informal introductions, please skip to 'Mathematical formulation')

Whenever our 'decimal positional system' for writing numbers comes up in conversation, mathematicians are quick to denounce the prominent role played by the number 10 as a completely arbitrary choice, a relict from an ancient time when human biology played a more significant part in our abilities to do mathematics. By contrast, the use of the numbers $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ (or more generally $\{0, \ldots b-1\}$ in base $b$) as digits in our system is rarely questioned. This seems unsurprising: using digits all of which are are at least 2 (say) would give us a hard time writing down the number 1. But - newsflash! - in the current system it is equally impossible to write down all integers, at least without retorting to introducing an auxiliary non-digit symbol like '$-$'. By contrast, if we were to use digits (symbols) representing the numbers $\{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5\}$ (perhaps with one of the two boundary cases omitted) we could easily write down any integer we want without introducing any further non-digit symbols. (E.g. 17 would be written $2[-3]$.) Now the point of this question is not to convince anybody to switch to this system. (Although I can't resist pointing out that when writing the negative digits as the mirror image of their positive counterparts, doing long multiplication manually in this system is remarkably easy.) Instead the point is to draw attention to some highly non-obvious digit sets that also have the power of representing any integer in the positional system such as (still for base 10) the set $\{-404,97,-482,49,0,471,-238,-797,64,605\}$ . The question is whether these digit sets can somehow be classified (for general base $b$ of course; I'm still a mathematician).

Mathematical Formulation

Let $b \geq 2$ be an integer (the 'base') and let $D \subset \mathbb{Z}$ (the 'digit set') be a finite set satisfying

• $D$ contains exactly one element from every congruence class modulo $b$

• The congruence class of $0$ modulo $b$ is represented in $D$ by the element $0$. (Shorter: $0 \in D$.)

Given $b$ and $D$, define a discrete dynamical system $T_D: \mathbb{Z} \to \mathbb{Z}$ by

$$T_D(a) = \frac{a - d_a}{b}$$ where $d_a \in D$ is the unique element of $D$ congruent to $a$ ($\mod b$).

Obviously $T_D(0) = 0$. We say that the digit set $D$ is complete if for every $a \in \mathbb{Z}$ there exist a $n \in \mathbb{N}$ such that $T_D^n(a) = 0$. (So repeated application of $T_D$ will bring every number $a$ down to zero.)

Question: Can we, for a given $b$, characterize all the complete digit sets $D$ among all sets satisfying the criteria?

(At the risk of stating the obvious: the relation between this formulation and the informal one above is that the successive numbers $d_a, d_{T(a)}, d_{T_D(T_D(a))}, \ldots$ appearing when repeatedly applying $T_D$, form, when read from right to left, the $b$-al expansion of the number $a$. Of course this expansion is only readable when it is finite, i.e. ends in an infinite string of zeroes (still reading from right to left). Thus the complete digit sets are the digit sets for which every integer has a finite $b$-expansion. (Ok, strictly speaking infinite expansions are also readable in the case that $b$ is a prime and we can interpret the sequence as a series convergent in the $b$-adic topology. But in that case I think that the set of numbers with finite expansions cut out by the digit set $D$ is an interesting subset of $\mathbb{Z}_b$ and a fortiori the question for which digit sets this interesting subset turns out to be the most interesting subset of all (i.e. all of $\mathbb{Z}$) is interesting in its own right.))

A necessary but not sufficient condition

An obvious sufficient condition for $D$ to be not complete is when all elements of $D$ are divisible by some prime $p$ (necessarily not dividing $b$) or when all elements of $D$ are either non-positive or non-negative. (Side question: is there some 'higher viewpoint' from which I can see these conditions as the same, e.g. a way in which the sets of positive and negative numbers are just 'congruence classes modulo the archimedian prime' or something?) However, avoiding these constellations (as is easily done to require $\{-1, 0, 1\}$ to be a subset of $D$) is necessary but not sufficient for completeness as illustrated by the digit set $D = \{-57, -1, 0, 1, 12\}$ for $b = 5$ which gives the cycle $(-2, 11, 2)$ under $T_D$ (thus preventing at least these numbers to ever reach $0$).

An easy but still surprising observation

When a given digit set $D$ is not complete, this can be seen in finite time by applying $T_D$ to a finite set of numbers.

This observation allowed me to obtain the numerical results below. The reason is fairly simple. If $D$ is not complete and the dynamical system $T_D$ contains a cycle (including fixed points and infinite cycles) then there must be an integer $a \neq 0$ such that $|T(a)| \geq |a|$. If $d \in D$ is such that $a \equiv d$ then this can only happen if $$a = d - cb \textrm{ where } d/(b+1) \leq c \leq c/(b-1) \textrm{ if } d >0$$ or $$a = d - cb \textrm{ where } d/(b-1) \leq c \leq d/(b+1) \textrm{ if } d <0$$

This for instance immediately shows that the digit set $\{[-b/2], \ldots, [b/2]\}$ is complete as it leaves no $a$ satisfying the criteria. (I write [] for floor since apparently \floor is not recognized.)

However, even if there are fairly many $a$ satisfying $|T_D(a)| \geq |a|$ it is still possible that all of them end up at 0 under repeated application of $T_D$ as is illustrated by the digit set $D = \{-605, -233, -309, 0, -671, 58, 31\}$ for $b = 7$. This digit set is also fairly illustrative for how little I understand about this problem.

Numerical results

Complete digit sets are rare. I wrote a program to generate random digit sets as follows: start with the set $\{[-b/2], \ldots, [b/2]\}$ and then add to each non-zero element a multiple of $b$ chosen independently uniformly at random from the interval $[-100b, 100b]$. Next the program checks whether the random digit set is complete by the above method. I found that for $b = 5$ in 1200 random digit sets only 4 were complete: $$\{-262,-311,0,-134,77\}$$ $$\{-167,-71,0,21,-123\}$$ $$\{198,-346,0,-489,87\}$$ $$\{3,-21,0,381,-13\}$$

From 1200 random digit sets for $b = 7$ only 8 were complete: $$\{382,376,-1,0,197,23,-256\}$$ $$\{242,-79,-57,0,-13,100,689\}$$ $$\{403,-79,377,0,533,142,-39\}$$ $$\{4,-597,34,0,463,-446,73\}$$ $$\{-3,-415,-526,0,449,37,675\}$$ $$\{4,593,34,0,-454,-201,-109\}$$ $$\{697,-548,13,0,-531,205,458\}$$ $$\{-605, -233, -309, 0, -671, 58, 31\}$$

From 600 random digit sets for $b = 10$ only 3 were complete: $$\{46,77,298,339,0,-489,-748,-347,64,615\}$$ $$\{-404,97,-482,49,0,471,-238,-797,64,605\}$$ $$\{616,-33,388,-701,0,321,92,-367,-526,155\}$$

When we force our digit sets to contain the elements $1$ and $-1$ in order to satisfy the condition above, numbers increase dramatically: 200 complete digit sets in 1200 random digit sets containing $1$ and $-1$ for $b = 5$; 134 complete digit sets in 1200 random digit sets of this form for $b = 7$ and 112 out of 1200 for $b = 10$.

On the other hand demanding that the digit set is symmetric in the sense that for every $d \in D$ also $-d \in D$, seems to bring the number of complete digit sets down. Quite to my surprise I found 0 (!) complete digit sets among 1200 random symmetric digit sets containing 1 and -1 for b = 5. This does not mean it is impossible: the 'small' examples $\{-7, -1, 0, 1, 7\}, \{3, -1, 0, 1, -3\}, \{-17, -1, 0, 1, 17\}, \{23, -1, 0, 1, -23\}$ are complete. Dropping the requirement that 1 and -1 are part of the digitsets revealed one more symmetric digit set in 300 random symmetric digit sets for $b = 5$: $\{-17,-81,0,81,17\}$ so also with relatively small numbers.

Staring at these digit sets doesn't reveal very much about what makes them special. They look just as random as the others. So hence my question: do the complete digit sets share any other property by which they can be recognized, classified or constructed?

Answer 1

This is not an answer. One way to succinctly describe both the existence and uniqueness of base-$b$ representations is as the generating function identity

$$\frac{1}{1 - x} = 1 + x + x^2 + \cdots = \prod_{i=0}^{\infty} \left( 1 + x^{b^i} + x^{2 b^i} + \dots + x^{(b-1) b^i} \right)$$

And one reason this is particularly nice is that it's easy to prove by telescoping, using the identity

$$1 + x^{b^i} + \dots + x^{(b-1) b^i} = \frac{1 - x^{b^{i+1}}}{1 - x^{b^i}}.$$

Partially telescoping gives a refinement of the existence and uniqueness of base-$b$ representations, namely that base-$b$ representations of integers between $0$ and $b^n - 1$ exist, are unique, and involve $n$ digits.

If you want existence and uniqueness for both positive and negative integers then you are now trying to prove an identity of the form

$$\cdots x^{-1} + 1 + x^1 + \cdots = \prod_{i=0}^{\infty} \left( 1 + x^{d_1 b^i} + x^{d_2 b^i} + \dots + x^{d_{b-1} b^i} \right).$$

We need to be a bit careful about the meaning of this identity. Unlike formal power series, doubly-infinite formal power series do not form a ring. However, they do form a module over Laurent polynomials, and the RHS is a product of Laurent polynomials, so it makes sense to ask whether it converges to some doubly-infinite series with respect to the obvious topology.

Let $f(x) = 1 + x^{d_1} + \dots + x^{d_{b-1}}$ and let $\delta(x - 1)$ be the LHS above. The notation is justified due to the identity $\delta(x - 1) g(x) = \delta(x - 1) g(1)$ for any Laurent polynomial $g$. Then the identity we want has the form

$$\delta(x - 1) = \prod_{i=0}^{\infty} f(x^{b^i}).$$

It's now tempting to proceed as follows. Substituting in $x = x^b$ gives

$$\delta(x^b - 1) = \prod_{i=1}^{\infty} f(x^{b^i})$$

and hence

$$\delta(x - 1) = \delta(x^b - 1) f(x).$$

It's tempting to argue that this identity is equivalent to the desired identity, by repeatedly substituting $x = x^b$. But in fact that's not true; this identity only expresses the necessary but not sufficient condition that the $d_i$ should contain exactly one representative of each equivalence class $\bmod b$ (counting $d_0 = 0$). There's an analogous argument for formal power series which works because multiplication of formal power series is continuous in the $x$-adic topology, but the analogous statement for the action of Laurent polynomials on doubly infinite series is false.

So prospects for a clean telescope-type argument seem poor here. In general, the fact that we can't divide (let alone multiply) by doubly-infinite series suggests that there won't be anything extremely clean to say.