**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?

3more comments