Finite and periodic orbits of shift radix systems

Abstract

For r = (r0,…, rd-1) ε ℝd define the function τr: ℤd → ℤd, z = (z0,…, zd-1) → (z1,…, zd-1,- ⌊rz⌊), where rz is the scalar product of the vectors r and z. If each orbit of τr ends up at 0, we call τr a shift radix system. It is a well-known fact that each orbit of τr ends up periodically if the polynomial td+rd-1td-1+…+r0 associated to r is contractive. On the other hand, whenever this polynomial has at least one root outside the unit disc, there exist starting vectors that give rise to unbounded orbits. The present paper deals with the remaining situations of periodicity properties of the mappings τr for vectors r associated to polynomials whose roots have modulus less than or equal to one with equality in at least one case. We show that for a large class of vectors r belonging to the above class the ultimate periodicity of the orbits of τr is equivalent to the fact that τs is a shift radix system or has another prescribed orbit structure for a certain parameter s related to r. These results are combined with new algorithmic results in order to characterize vectors r of the above class that give rise to ultimately periodic orbits of τr for each starting value. In particular, we work out the description of these vectors r for the case d = 3. This leads to sets which seem to have a very intricate structure.