BASIC PROPERTIES OF SHIFT RADIX SYSTEMS

Shigeki Akiyama1
Department of Mathematics, Faculty of Science, Niigata University, Ikarashi 2-8050, Niigata 950-2181,
JAPANakiyama@math.sc.niigata-u.ac.jp
Tibor Borbély
National Instruments Europe Kft, H - 4031 Debrecen, Hatar u. 1/A, HUNGARY

tibor.borbely@ni.com
Horst Brunotte
Haus-Endt-Straße 88, D-40593 Düsseldorf, GERMANY

brunoth@web.de
Attila Pethő2
Department of Computer Science, University of Debrecen, P.O. Box 12, H-4010 Debrecen, HUNGARY

pethoe@inf.unideb.huJörg M. Thuswaldner3
Chair of Mathematics and Statistics, Leoben University, Franz-Josef-Straße 18, A-8700 Leoben,
AUSTRIAjoerg.thuswaldner@unileoben.ac.at
Abstract
Certain dynamical systems on the set of integer vectors Zd are introduced and their basic
properties are described. Applications to β-expansions and canonical number systems
reveal unexpected relations between different radix representation concepts.

Key words: beta expansion, canonical number system, dynamical system, Pisot number, radix representation.
2000 Mathematics Subject Classification: 11A63
1The first author was supported by the Japan Society for the Promotion of Science, Grants in Aidfor fundamental research 14540015, 2002–2005.
2The fourth author was supported partially by the Hungarian National Foundation for Scientific
Research Grant Nos. T42985 and T38225.
3
The fifth author was supported by project S8310 of the Austrian Science Foundation.

1. Introduction
Let r = (r1 , . . . , rd ) ∈ Rd (d ≥ 1). We are interested in the mapping τr : Zd → Zd
defined by4τr (a) = (a2 , . . . , ad , − br1 a1 + · · · + rd ad c)
for a = (a1 , . . . , ad ) ∈ Zd . The mapping τr is called a shift radix system (SRS for short)
if for all a ∈ Zd we can find some n ∈ N with τrn (a) = (0, . . . , 0). In this note we givea short summary of basic properties and applications of SRS and mention some open
problems. For more detailed background information and proofs the reader is referred tothe original papers [1, 2].
Throughout we shall use the following sets which are closely connected to the orbitsof τr :
Dd0 := r ∈ Rd | τr is a SRSanddd
Dd := r ∈ R | for all a ∈ Z the sequence (τrn (a))n∈N is ultimately periodic .
Some subsets of these sets will be given later (see Sections 2 and 3), here we restrict toa few preliminary examples.
Examples(i) D1 = [−1, 1] , D10 = [0, 1) (see [1]).
(ii) D \ {(1, y) ∈ R2 | 0 < |y| < 1 or 1 < |y| < 2} ⊆ D2 ⊆ D whereD = {(x, y) ∈ R2 | |x| ≤ 1, |y| ≤ 1 + x, (x, y) 6= (1, −2), (1, 2)}\{(x, −x − 1) ∈ R2 | 0 < x < 1} (see [2]).
(iii) Set
E1 =E2 =
E3 =
L =



2x2(x, y) ∈ Rx < 1, y < 2x,+1≤y ,3
x2x2(x, y) ∈ Rx < 1, + 1 < y < 2x, y <+1 ,23
12(x, y) ∈ Rx < 1, −2x + 1 ≤ y < − x , and252(x, y) ∈ R 0 ≤ x ≤ , y < x + 1, y ≥ −x .
6ThenD20 ∩ L = L \ (E1 ∪ E2 ∪ E3 ) (see [2]).
In Figure 1 the gray points sketch an approximation of D20 ; note that the coordinate
system is changed to be easier comparable to Figure 2 in Section 2.2.
4b. . .c denotes the floor function.

2

Figure 1: An approximation of D20 .
2. Applications of shift radix systems
The main applications of SRS which have been dealt with so far are related to radix
representations.

2.1 Shift radix systems and β-expansions
The so-called β-expansions have first been studied by A. Rényi [17] and W. Parry [14]and have subsequently been intensively studied.
Let β > 1 be a non-integral real number. Then each γ ∈ [0, ∞) can be represented
uniquely by
γ = am β m + am−1 β m−1 + · · ·(1)with ai ∈ {0, 1, . . . , bβc} such that0≤γ−mXai β i < β n(2)i=nholds for all n ≤ m. Since by condition (2) the digits ai are selected as large as possible,
the representation in (1) is called the greedy expansion of γ with respect to β.
Apart from the SRS notion the following theorem is basically due to M. Hollander [6].
Theorem 1(M. Hollander) Let d > 1 and β > 1 be a real algebraic integer withminimal polynomial X d − b1 X d−1 − · · · − bd−1 X − bd ∈ Z[X]. Define r2 , . . . , rd ∈ R by
X d − b1 X d−1 − · · · − bd−1 X − bd = (X − β)(X d−1 + r2 X d−2 + · · · + rd ),hence rj = bj β −1 + bj+1 β −2 + · · · + bd β j−d−13(2 ≤ j ≤ d).

0Then (rd , . . . , r2 ) ∈ Dd−1
if and only if Z[ β1 ] ∩ [0, ∞) coincides with the set of positive
real numbers having finite greedy expansion with respect to β.
Proof. See [1].
A. Bertrand [3] and K. Schmidt [18] proved that if β is a Pisot number thenthe β-expansion of every element of Q(β) ∩ [0, ∞) is ultimately periodic. The above
mentioned finiteness property can only hold for Pisot numbers β (see [4], Lemma 1).
We remark that the characterization of Pisot numbers with the above mentioned
finiteness property is not even known for degree d = 3.

2.2 Shift radix systems and canonical number systems
An example of a canonical number system was first studied by D. E. Knuth [10, 11].
His notion was extended by W. J. Gilbert, I. Kátai, B. Kovács and J. Szabó([5, 7, 8, 9]) to quadratic number fields and by B. Kovács [12] to arbitrary number fields
as straightforward generalizations of the well-known radix representation of ordinary
integers.
This concept was further generalized by the fourth author [15] by defining CNS polynomials: A monic integral polynomial P (X) is called a CNS polynomial if every coset ofZ[X]/P (X)Z[X] contains an element of the form
a0 + a1 x + · · · + al x lwith a0 , ..., al ∈ {0, 1, . . . , |P (0)|−1} where x denotes the image of X under the canonicalepimorphism from Z[X] to Z[X]/P (X)Z[X].
p1
Theorem 2 Let p0 , . . . , pd−1 ∈ Z with p0 > 1. Then p10 , pd−1,.
.
.
,∈ Dd0 if andp0p0
only if X d + pd−1 X d−1 + · · · + p0 is a CNS polynomial.
Proof. See [1].

As an illustration the grey points in Figure 2 represent all cubic CNS polynomials
with constant term equal to 474.
The complete description of CNS polynomials of degree d > 2 is still open.

3. Basic properties of shift radix systems
For r = (r1 , . . . , rd ) ∈ Rd the mapping τr differs from a linear mapping by a certain additive term. Although being small this term is the reason for the difficulties in controlling4Figure 2: CNS polynomials X 3 + p2 X 2 + p1 X + 474.
the iterates of τr : More precisely, we have for a ∈ Zd
τrn (a) = R(r)n a +nXR(r)n−i vi

i=1for all n ∈ N with the matrix

010 ···
0.. ... ... ...
 ..
.  .
..
..
R(r) :=  ...
.
.
0 


 0··· ··· 01 −r1 −r2 · · · · · · −rdand vectors vi ∈ Rd with k vi k∞ < 1 (see [1]).
Theorem 3(i) The characteristic polynomial of R(r) is given by
X d + rd X d−1 + · · · + r2 X + r1 .
(ii) If r ∈ Dd then the spectral radius of R(r) is less than or equal to 1.
(iii) If the spectral radius of R(r) is less than 1 then r ∈ Dd .
(iv) Let r ∈ Rd with spectral radius of R(r) less than 1. Then there exists an effectively
computable constant cr ∈ R with the property: r ∈ Dd0 if for each a ∈ Zd withk a k∞ ≤ cr the orbit of a under the iterates of τr falls into the zero cycle.
Proof. For (i), (ii), (iii) see [1] (note that the analogue of (ii) for canonical number
systems is well known, see e. g. [5]). The proof of (iv) is analogous to that of Theorem 1in [16].
5By statement (iii) Dd contains the bounded set
Ed = (r1 , . . . , rd ) ∈ Rd | all roots of X d + rd X d−1 + · · · + r1 lie inside the open unit circle
which can be described by polynomial inequalities (for more information see the SchurCohn criterion (e. g. [13], Theorem 2.4.4)), and the closure of this set contains Dd bystatement (ii).
Statement (iv) shows in particular that one can algorithmically decide whether or not
a given r belongs to Dd0 (for a different algorithm and computational issues see [1]).
The next theorem exhibits a large subset of Dd0 .
Theorem 4 If 0 ≤ r1 ≤ r2 ≤ · · · ≤ rd < 1 then r ∈ Dd0 .
Proof. See [2].

Theorem 5 For each d ∈ N the sets Dd and Dd0 are Lebesgue measurable. Further
λ(Dd ) = λ(Ed ) where λ denotes the d-dimensional Lebesgue measure.
Proof. See [1].
The geometrical structure of Dd0 is quite complicated. For each r ∈ Dd \ Dd0 one canpick a point in Zd which gives rise to a periodic orbit under the iterates of τr . On theother hand, given a point a ∈ Zd one may consider the collection of all r ∈ Rd such thatthe sequences (τrn (a))n∈N are periodic: More precisely, let(0 ≤ j ≤ L − 1)

(a1+j , . . . , ad+j )with aL+1 = a1 , . . . , aL+d = ad be vectors of Zd . We ask for which r = (r1 , . . . , rd ) ∈ Rd
we have τrL (a) = a. By the definition of τr this is the case if and only if the inequalities
0 ≤ r1 a1+j + · · · + rd ad+j + ad+j+1 < 1 (0 ≤ j ≤ L − 1)hold simultaneously. Hence, these points r form a (possibly degenerate) polyhedronin Rd . As we saw in Example (i) we get D10 by simply taking away a single point and aline segment from D1 . However, it turns out that for d > 1 infinitely many polyhedra
have to be removed from Dd in order to arrive at Dd0 .
Theorem 6 Let d ≥ 2. Then Dd0 emerges from Dd by cutting out countably manypolyhedra.
Proof. See [1].
3. Some open problems
By what has been said above, the investigation of SRS leaves several questions open (see[1] and [2]). Here we only mention three problems.
6Figure 3: The behavior of N 0 (3, M )/M 2 for 2 ≤ M ≤ 464.
1. We conjecture that D2 coincides with the set D defined in Example (ii). The truthof this conjecture would imply that
D2 is convex. We thank W. Steiner [19] for the√1+ 5
information that the point (1, 2 ) belongs to D2 .
2. We conjecture that if r ∈ Dd0 then the spectral radius of R(r) is less than 1. Thisis clear for d = 1 (see Example (i) in Section 1), and for d = 2 it is proved in [2].
3. The following conjecture seems to be even more challenging: Let M be a positiveinteger andN 0 (d, M ) = |{(p1 , . . . , pd−1 ) ∈ Zd−1 | M +p1 X+· · ·+pd−1 X d−1 +X d is a CNS polynomial}|.
ThenN 0 (d + 1, M )M →∞Mdexists and is equal to the Lebesgue measure of Dd0 . On Figure 3. we displayed N 0 (3, M )/M 2for 2 ≤ M ≤ 464. It seems that the quotient stabilizes after the first few values, which
support the truth of the conjecture. An analogous conjecture has been formulated forthe set Dd as well.
lim

References[1] S. Akiyama, T. Borbély, H. Brunotte, A. Pethő and J. M. Thuswald7

ner, Generalized radix representations and dynamical systems I, to appear in Acta
Math. Hungar., 108 (3) (2005), 207 – 238.
[2] S. Akiyama, H. Brunotte, A. Pethő and J. M. Thuswaldner, Generalized radix representations and dynamical systems II, to appear in Periodica Math.
Hungar.
[3] A. Bertrand, Développement en base de Pisot et répartition modulo 1, C. R. Acad.
Sci. Paris Sér. A-B, 285 (1977), 419 – 421.
[4] C. Frougny and B. Solomyak, Finite beta-expansions, Ergod. Th. and Dynam.
Sys. 12 (1992), 713 – 723.
[5] W. J. Gilbert, Radix representations of quadratic fields, J. Math. Anal. Appl., 83(1981), 264 – 274.
[6] M. Hollander, Linear Numeration Systems, Finite Beta Expansions, and Discrete
Spectrum of Substitution Dynamical Systems, PhD thesis, Washington University,Seattle (1996).
[7] I. Kátai and B. Kovács, Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen Zahlen, Acta Sci. Math. (Szeged), 42 (1980), 99 – 107.
[8] I. Kátai and B. Kovács, Canonical number systems in imaginary quadratic fields,
Acta Math. Acad. Sci. Hungar., 37 (1981), 159 – 164.
[9] I. Kátai and J. Szabó, Canonical number systems for complex integers, Acta Sci.
Math. (Szeged), 37 (1975), 255 – 260.
[10] D. E. Knuth, An imaginary number system, Comm. ACM, 3 (1960), 245 – 247.
[11] D. E. Knuth, The Art of Computer Programming, Vol. 2 Semi-numerical Algorithms, Addison Wesley (1998) London 3rd edition.
[12] B. Kovács, Canonical number systems in algebraic number fields, Acta Math. Acad.
Sci. Hungar., 37 (1981), 405 – 407.
[13] M. Mignotte, D. Ştefănescu, Polynomials, Springer, Berlin Heidelberg New
York (1999)[14] W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar.
11 (1960), 401 – 416.
[15] A. Pethő, On a polynomial transformation and its application to the construction ofa public key cryptosystem, Computational Number Theory, Proc., Walter de Gruyter
Publ. Comp. Eds.: A. Pethő, M. Pohst, H. G. Zimmer and H. C. Williams, 1991,
pp 31 – 43.
[16] A. Pethő, Notes on CNS polynomials and integral interpolation, to appear.
8[17] A. Rényi, Representations for real numbers and their ergodic properties, Acta Math.
Acad. Sci. Hungar. 8 (1957), 477 – 493.
[18] K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull.
London Math. Soc., 12 (1980), 269 – 278.
[19] W. Steiner, private communication (28/09/2004).

9