From number systems to shift radix systems
Shigeki Akiyama∗and Klaus Scheicher†

Abstract
Shift radix systems provide a unified notion to study two important
types of number systems. In this paper, we briefly review the origin of thisnotion.

1. Introduction
Let r = (r1 , . . . , rd ) ∈ Rd . Consider a mapping τr : Zd → Zd , which maps eachelement (z1 , . . . , zd ) to (z2 , . . . , zd+1 ), provided that0 ≤ r1 z1 + r2 z2 + · · · + rd zd + zd+1 < 1.
Obviously, τr is defined by¡¢τr (z1 , . . . , zd ) = (z2 , . . . , zd , −br1 z1 + · · · + rd zd c).

(1.1)

We say that τr has the finiteness property if for every z ∈ Zd there exists a k,such that τrk (z) = 0.
This concept unifies notions for two important number systems, namely canonical number systems and β-expansions. For these number systems, the finitenessproperty means that all numbers of a certain set admit finite expansions. This
property also plays an important role for constructing tilings giving the Markoff
partitions of dynamical systems associated to these number systems.
If τr has the finiteness property, then (Z, τr ) is called a shift radix system (forshort SRS) (cf. [2, 3]). It turned out to be a hard problem to characterize all∗
The first author was supported by the Japanese Ministry of Education,Culture, Sports,
Science and Technology, Grant-in Aid for fundamental research 14540015, 2002–2005.
†
The second author was supported by the FWF projects 8305 and 8308.

r ∈ Rd which give rise to a SRS and currently, a complete solution seems to be outof range. However, in the last years, several partial results have been established.
For an introduction to SRS, we do not aim to give an exact account. For
detailed information, we refer to original papers. Emphasis will be put on results of Gilbert and Hollander who developed the essential structure of the SRS
algorithm.
2. Canonical number systems
As an example, we consider Knuth’s number system. He proposed a √way toexpress Gaussian integers by digits from A = {0, 1} with base α = −1 + −1:
1
2
3
4
5

=
=
=
=
=

α0 = (1)αα3 + α2 = (1100)αα3 + α2 + 1 = (1101)αα8 + α7 + α6 + α4 = (111010000)αα8 + α7 + α6 + α4 + 1 = (111010001)α

How do we find such expressions ? This is done by so called residual algorithm.
Take for example the expansion of 3 in base α: As A forms a complete system ofrepresentatives modulo α, and 3 ≡ 1 (mod α), the lowest digit is 1. We subtract√
1 and then divide by α. Then we restart this process from (3−1)/α = −1− −1.
Iterating this, we generate the expansion in base α. After four steps, we terminate
this process since we run into the trivial cycle 0 → 0 which generates infinitely
many leading zeros.
Generally, we may start with an algebraic integer α of degree d and a complete
residue system A modulo α in Z[α]. If all algebraic conjugates of α have modulus
greater than 1, then the residual algorithm can be viewed as a contractive map
on Z[α], which is isomorphic to Zd as an additive group. This means that eachorbit must be eventually periodic. However, it is not trivial that this process mustterminate in finitely many steps. In fact, it is possible√that the residual algorithm0
If we
runs into a non√ trivial cycle. For√e.g., let α = 1 +0 −1 and√ A = {0, 1}.
√0
try to expand −1, we find that −1 ≡ 1 (mod α ) and ( −1 − 1)/α = −1.
Thus,√−1 = (· · · 111)α0 .
For Knuth’s number system, it is proved that the process terminates for every
starting value. This is exactly the above mentioned finiteness property. In thiscase, the pair (α, A) is called a canonical number system (CNS for short).

Before explaining Gilbert’s idea, we summarize known results on the characterization of CNS. A first systematic treatment was given in Kátai-Szabó [18],where all CNS bases for Gaussian integers have been characterized. This result
was generalized to quadratic integers in Kátai-Kovács [16, 17] and independently
in Gilbert [13]. Körmendi [19] dealt with a special class of cubic integers and recently Brunotte [8, 9] characterized all CNS whose bases are roots of trinomials.
In the general case Kovács [20] proved that an algebraic integer α gives rise to a
CNS if its minimal polynomial
P (x) = xn + bn−1 xn−1 + . . . + b1 x + b0
satisfies
1 ≤ bn−1 ≤ bn−2 ≤ · · · ≤ b1 ≤ b0 ,b0 ≥ 2.

However, this characterization is far from complete. Examples not contained inthis class are given in Kovács-Pethő [21], where also an algorithm is establishedto decides whether a given α is a CNS base or not. Akiyama-Pethő [4] developed
a much faster algorithm than the one in [21]. Akiyama-Rao [5] and ScheicherThuswaldner [26] studied CNS under a so called Dominant Condition|b1 | + . . . + |bn | < b0 .
In particular, all CNS up to degree five with this additional property have beencharacterized. Finally, we mention that Brunotte [8, 9] provided the fastest known
algorithm to determine if an arbitrary polynomial gives a CNS or not.
3. Gilbert’s Clearing Algorithm
In [13], W. J. Gilbert introduced his Clearing Algorithm which is one of the originsof the SRS setting. We explain his idea by using Knuth’s number system.
√√
Let α = −1 + −1. Then Z[α] = Z[ −1]. As α satisfies x2 + 2x + 2 = 0,
we have an isomorphism Z[α] ' Z[x]/(x2 + 2x + 2). The residual
Palgorithm isinterpreted by division algorithm on Z[x]. A polynomial Q(x) = i qi xi ∈ Z[x]will be called cleared if qi ∈ {0, 1}. For a given A(x) ∈ Z[x], we wish to find B(x)and Q(x) with
A(x) = (x2 + 2x + 2)B(x) + Q(x),PPsuch that Q(x) = i qi xi is cleared. If this holds, then Q(α) = i qi αi is thedesired expression.
This process is visualized for A(x) = 5 in the Table 1. The first line contains
coefficients of A(x) = 5. The last line gives coefficients of the cleared polynomial
Q(x) and each intermediate horizontal line contains a multiple of x2 + 2x + 2.

1
-1 -2
1 2 2
1 1 1

0
2
-2
0

-1
0
2

1

-2 -4
2 4 4
-2 -2
0

0

0

0

5
-4

1

Table 1: Gilbert’s Clearing Algorithm

Now we come to the main point. We only keep track of a sequence−2, 2, −1, 0, 1, −1, 1
appeared in the upper diagonal of the matrix in Table 1. This is nothing but
the sequence of coefficients of B(x). Denote this sequence by z1 , z2 , z3 , · · · . The
key step is to switch to this sequence instead of observing the output reminders
1, 0, 0, 0, 1, 0, 1, 1, 1. Then zi are determined by the inequality
0 ≤ zi + 2zi+1 + 2zi+2 < 2.
Dividing by 2, we get
0 ≤ 12 zi + zi+1 + zi+2 < 1.
Thus r = ( 12 , 1). If r gives a SRS, then Knuth’s number system has the expectedfiniteness property. A straightforward generalization yields
Theorem 3.1 The polynomial P (x) = ³xd + bd−1 xd−1 +´ · · · + b1 x + b0 gives ab, . . . , bb10 gives a d-dimensional
canonical number system if and only if b10 , d−1b0
SRS.
The clearing algorithm was reformulated by a suitable base change of Z[α]into a SRS. An important idea, the set of witnesses, was invented independently
by Brunotte [8, 9] and Scheicher-Thuswaldner [25, 26] under this base change.
This method gives the easiest and fastest algorithm to determine whether α gives
a CNS or not. Consult [2] to see how this idea works in SRS framework.

4. β-expansions
A second type of number system, so called β-expansions, are related to SRS as
well. Given β > 1, we wish to express a positive real number x in a formx = x−m β m + x−m+1 β m−1 + . . .

(4.1)

with xi ∈ A = [0, β) ∩ Z. A sum of form (4.1) is called a β-representation of
x. A special β-representation, which is called the β-expansion can be obtained
as follows. Find the largest integer m such that β m ≤ x < β m+1 . Computex − x−m β m withx−m = max{a ∈ A : x − aβ m ≥ 0}.
(4.2)
Iterating this process will lead to an expansion of form (4.1). This setting is alsoa natural generalization of the decimal expansions.
Since x−m is the largest possible digit such that β m ≤ x−m β m < β m+1 , thisalgorithm is called greedy algorithm. In general, there exist infinitely many βrepresentations apart from the β-expansion. For example, so called lazy expansions (cf. [10]) are defined by taking
x−m = min{a ∈ A : x − aβ m < β m }in place of (4.2). For x ∈ [0, 1), the greedy algorithm is equivalent to the following
setting: Define the β-transformation T : x → βx − bβxc. By iterating this map
and considering its trajectory
x

x

x

1
2
3
x −→
T (x) −→T 2 (x) −→...

with xj = bβT j−1 xc, we obtainx=

x1 x2 x3
+ 2 + 3 + ....
βββWe say that dβ (x) is finite when xi = 0 for all sufficiently large i. This is the casewhen there in an integer i ≥ 0 such that T i (x) = 0. For an arbitrary x ≥ 1, there
is a maximal integer m such that β −m x ∈ [0, 1) with dβ (β −m x) = .x−m x−m+1 · · · .
By shifting, we obtaindβ (x) = x−m x−m+1 · · · x−1 x0 .x1 x2 · · · .
Formally, by applying T , one can expand 1 and obtains dβ (1) = .c1 c2 . . . .
In contrast to CNS, in β-expansions some subwords of A∗ never appear. For
example, a subword w = c1 (c2 + 1) can not appear even if c1 (c2 + 1) ∈ A2 . Thisis because w is too large and we should have already removed it earlier by thegreedy algorithm. Thus, a word of A∗ appears as a subword of a β-expansion if
and only if all its suffices are less than dβ (1) in natural lexicographic order (cf.
[22, 15]). For e.g., take a real root β ≈ 3.104 of x3 − 3x2 − 1 with A = {0, 1, 2, 3}.
Since dβ (1) = .301, we see that six words {33, 32, 31, 303, 302, 301} are forbidden.
In other words, the letter 3 must be followed by two 0’s in a β-expansion.
β-expansions were introduced by Rényi [23], who proved that the β-transformation
is ergodic. An invariant measure has been computed independently by Gelfondand Parry [12, 22]. As a non-trivial example for a dynamical system where theinvariant measure is explicitly known, its arithmetic, diophantine and ergodic
properties have been extensively studied. Let
Per(β) = {x ∈ R+ : dβ (x) is eventually periodic} andFin(β) = {x ∈ R+ : dβ (x) is finite}.
Recall that a Pisot number is an algebraic integer β > 1 for which all algebraic
conjugates γ 6= β satisfy |γ| < 1.
If β is a Pisot number, then Per(β) = Q(β) ∩ R+ (cf. Bertrand and Schmidt[7, 27]), which is a generalization of the fact that decimal expansions of rational
numbers are eventually periodic.
We say that a number β > 1 has the finiteness property or property (F), ifFin(β) = Z[β −1 ] ∩ R+ .

(F)

The inclusion Fin(β) ⊂ Z[β −1 ] ∩ R+ is trivial. Obviously a rational number
with a denominator 10n has a finite decimal expansion. Therefore we are just
expecting to have finite expansions for all reasonable candidates. The notion of
the property (F) was introduced in [11]. If β has property (F) then β is a Pisot
number (cf. [11]). Even a weaker condition Z+ ⊂ Fin(β) implies that β is a
Pisot number (cf. [1]). On the other hand, there exist Pisot numbers which do
not have property (F).
In [2] it is proved, that the problem of characterizing bases β with property (F)and the problem of characterizing CNS are both special cases of the SRS finitenessproblem. Before this, the following partial results have been established: Let
xd − ad−1 xd−1 − . . . − a0 be the minimal polynomial of β. Frougny and Solomyak[11] proved thatad−1 ≥ ad−2 ≥ · · · ≥ a0 > 0
is a sufficient condition for (F). Hollander proved thatad−1 ≥ ad−2 + · · · + a0 ,ai ≥ 0,is also sufficient. Akiyama [1] classified all cubic Pisot units with (F). AkiyamaRao-Steiner [6] includes further progress. However, the problem of characterizing
all cubic Pisot numbers with property (F) is still open.
5. Hollander’s Carry Sequence
The second originator of SRS is M. Hollander who was a student of B. Solomyak.
As his thesis [14] did not yet appear in publication, we emphasize that the ideaof SRS is basically due to him. Start from a relation:
β d = ad−1 β d−1 + ad−2 β d−2 + · · · + a0
which is not necessary irreducible. Let
a0
β
a1 a0
=
+ 2
β
β
..
.
ad−1 ad−2a0=+ 2 + ... + d.
β
β
β

r1 =
r2

rd

Then rd = 1 and {r1 , . . . , rd } generates Z[β] as a Z-module and gives a basis
if theis irreducible. Therefore, each γ ∈ Z[β] has a representation
Prelationdγ = i=1 zi ri with zi ∈ Z. Let γ ∈ Z[β] ∩ [0, 1), i.e.,0 ≤ z1 r1 + z2 r2 + . . . + zd rd < 1.
Then the β-transform of γ can be written as
T (γ) =dX

zi+1 rii=1

with zd+1 satisfying
0 ≤ z2 r1 + z3 r2 + . . . + zd+1 rd < 1.
Note that zd+1 is uniquely determined by this inequality, i.e.
zd+1 = −bz2 r1 + z3 r2 + . . . + zd rd−1 c.
Hollander called this sequence z1 , z2 . . . a Carry Sequence. We clearly have
Theorem 5.1 β has property (F) if and only if (r1 , r2 , . . . , rd−1 ) gives a (d − 1)-dimensional
SRS.

0 5
2 -6
1

2

0

5
0 -2
-3 0
-1 3
-1
1 0

-1
0 1
3 0 1
2 1 1

Table 2: Hollander’s Carry Sequence

Let us come back to the example β 3 = 3β 2 + 0β + 1 with β ≈ 3.104. In Table
2, we expand 5β −2 + 5β −3 ≈ 0.2010. The reader will see that Hollander’s idea issimilar to Gilbert’s clearing algorithm. In this case, we keep track of a sequence−2, −1, 1, 1 in the upper diagonal in Table 2. For example, by considering thesecond line to 4-th, the sequence −2, −1, 1 appears because
µ ¶ µ
¶ µ
¶
1
0
3
1
0
1
(−2)r1 − r2 + r3 = −2
−
+
+
+
+
∈ [0, 1)
ββ β2
β β2 β3
gives the fractional part, the image by T . From the third to 5-th, we have
µ ¶ µ
¶ µ
¶
1
0
3
1
0
1
(−1)r1 + r2 + r3 = −
+
+
+
+
+
∈ [0, 1).
ββ β2
β β2 β3The key idea of Gilbert and Hollander is simply summarized:
Observe quotients instead of reminders.
Since the algorithms of CNS and β-expansions seemingly have not much to
do with each other, it is surprising that both systems could be unified to the SRS
setting.
6. Recent developments
For r = (r1 , . . . , rd ) ∈ Rd , let %(r) be the maximum absolute value of all roots ofthe polynomial xd + rd xd−1 + . . . + r1 . Let©
ª
Dd0 = r ∈ Rd | ∀a ∈ Zd ∃k > 0 : τrk (a) = 0ª©
Dd = r ∈ Rd | ∀a ∈ Zd the sequence {τrk (a)}k≥0 is ultimately periodic
Ed = {r ∈ Rd | %(r) < 1}.
Thus, Dd0 is the set of all vectors r ∈ Rd , such that (Z, τr ) is a SRS. Note that Ed
is a bounded subset of Rd which can be explicitly described by certain polynomial
inequalities. Furthermore, Ed ⊂ Dd ⊂ E d holds (see [2]).

Let H be a compact subset of Ed . In [2], an algorithm to determine Dd0 ∩ H
was derived. The set Dd0 ∩ H can be constructed efficiently from H by cuttingout finitely many convex polyhedra. However this algorithm does not work if Hintersects ∂(Ed ). The closer H is to ∂(Ed ), the harder becomes the computation.
We have E2 = {(x, y) ∈ R2 : x < 1, |y| < x + 1}. Figure 1 shows an approximation of D20 . In [2, 3], several parts of the shaded (resp. white) areas are proved
to be in (resp. not in) D20 . For example,¯©
ª
S := (r1 , r2 ) ∈ R2 ¯ −r1 ≤ r2 < r1 + 1, 0 ≤ r1 ≤ 23 ⊂ D20 ,which contains the point (1/2, 1) for Knuth’s number system. Furthermore thepoint (r1 , r2 ) ≈ (0.322, 0.104) for x3 − 3x2 − 1 belongs to S which means that theroot β ≈ 3.104 has property (F).
The characterization of D20 is a hard problem. The main difficulties occur
near the line L = {(1, y) : −1 ≤ y ≤ 2}.
A symmetric version of SRS can be defined by shifting by 1/2:
1
1
− ≤ r1 z1 + r2 z2 + · · · + rd zd + zd+1 < .
2
2This change gives rise to other number systems. They are symmetric canonicalnumber systems and symmetric β-expansions. Imagine a ternary expression using
digits {−1, 0, 1} instead of {0, 1, 2}. Symmetric β-expansions of real numbers are
generated by a transformation τr0 : x → βx − bβx + 12 c on [− 12 , 12 ). Let
¯
n
o
00
d ¯
d
0k
D d = r ∈ R ¯ ∀a ∈ Z ∃k > 0 : τ r (a) = 0 .
In [24], D0 02 was completely characterized in this case since the regions near ∂(E2 )were already cut out! A picture of D0 02 is given in Figure 2. The outcome of thisslight shift should be compared with Figure 1.
References[1] S. Akiyama. Cubic Pisot units with finite beta expansions. In F.Halter-Kochand R.F.Tichy, editors, Algebraic Number Theory and Diophantine Analysis,
pages 11–26. de Gruyter, 2000.
[2] S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, and J. M. Thuswaldner.
Generalized radix representations and dynamical systems I. to appear Acta
Math. Hungar., 2005.
[3] S. Akiyama, H. Brunotte, A. Pethő, and J. M. Thuswaldner. Generalized
radix representations and dynamical systems II. to appear in Acta Arith.

(1,2)(−1,0)(1,−1)(1,−2)

Figure 1: The sets D20 and E2 .

(1,2)

(1/2,1)(−1,0)(1/2,−1)(1,−2)

Figure 2: The sets D0 02 and E2 .

[4] S. Akiyama and A. Pethő. On canonical number systems. Theor. Comput.
Sci., 270(1-2):921–933, 2002.
[5] S. Akiyama and H. Rao. New criteria for canonical number systems. Acta
Arith., 111(1):5–25, 2004.
[6] S. Akiyama, H. Rao, and W. Steiner. A certain finiteness property of Pisot
number systems. J. Number Theory, 107(1):135–160, 2004.
[7] A. Bertrand. Développements en base de Pisot et répartition modulo 1. C.
R. Acad. Sci. Paris Sér. A-B, 285(6):A419–A421, 1977.
[8] H. Brunotte. On trinomial bases of radix representations of algebraic integers. Acta Sci. Math. (Szeged), 67(3-4):521–527, 2001.
[9] H. Brunotte. Characterization of CNS trinomials. Acta Sci. Math. (Szeged),
68:673–679, 2002.
[10] K. Dajani and C. Kraaikamp. From greedy to lazy expansions and theirdriving dynamics. Expo. Math., 20(4):315–327, 2002.
[11] Ch. Frougny and B. Solomyak. Finite beta-expansions. Ergod. Th. andDynam. Sys., 12:713–723, 1992.
[12] A. O. Gel’fond. A common property of number systems. Izv. Akad. NaukSSSR. Ser. Mat., 23:809–814, 1959.
[13] W. J. Gilbert. Radix representations of quadratic fields. J. Math. Anal.
Appl., 83:264–274, 1981.
[14] M. Hollander. Linear numeration systems, finite beta expansions, and discrete spectrum of substitution dynamical systems. PhD thesis, University ofWashington, 1996.
[15] Sh. Ito and Y. Takahashi. Markov subshifts and realization of β-expansions.
J. Math. Soc. Japan, 26:33–55, 1974.
[16] I. Kátai and B. Kovács. Kanonische Zahlensysteme in der Theorie derQuadratischen Zahlen. Acta Sci. Math. (Szeged), 42:99–107, 1980.
[17] I. Kátai and B. Kovács. Canonical number systems in imaginary quadratic
fields. Acta Math. Acad. Sci. Hungar., 37:159–164, 1981.
[18] I. Kátai and J. Szabó. Canonical number systems for complex integers. Acta
Sci. Acad. Sci. Math. (Szeged), 37:255–260, 1975.
√[19] S. Kormendi. Canonical number systems in Q( 3 2). Acta Sci. Math. (Szeged),50(3-4):351–357, 1986.

[20] B. Kovács. Canonical number systems in algebraic number fields. Acta Math.
Acad. Sci. Hungar., 37:405–407, 1981.
[21] B. Kovács and A. Pethő. Number systems in integral domains, especiallyin orders of algebraic number fields. Acta Sci. Math. (Szeged), 55:286–299,
1991.
[22] W. Parry. On the β-expansions of real numbers. Acta Math. Acad. Sci.
Hungar., 11:401–416, 1960.
[23] A. Rényi. Representations for real numbers and their ergodic properties.
Acta Math. Acad. Sci. Hungar., 8:477–493, 1957.
[24] S.Akiyama and K. Scheicher. Symmetric shift radix systems and finite expansions. submitted.
[25] K. Scheicher. Kanonische Ziffernsysteme und Automaten. Grazer Math.
Ber., 333:1–17, 1997.
[26] K. Scheicher and J. M. Thuswaldner. On the characterization of canonicalnumber systems. Osaka Math. J., 41:327–351, 2004.
[27] K. Schmidt. On periodic expansions of Pisot numbers and Salem numbers.
Bull. London Math. Soc., 12:269–278, 1980.

Shigeki Akiyama

Klaus Scheicher,

Department of Mathematics
Faculty of Science
Niigata University
Ikarashi 2-8050
Niigata 950-2181, Japan.

Johann Radon Institute for
Computational and Applied
Mathematics,
Altenbergerstraße 69,
A-4040 Linz, Austria.

akiyama@math.sc.niigata-u.ac.jp

klaus.scheicher@oeaw.ac.at