Finite and periodic orbits of shift radix systems

• Published in: Journal de theorie des nombres de bordeaux 2010-01, Vol.22 (2), p.421-448
• Main Authors: KIRSCHENHOFER, Peter, PETHÖ, Attila, SURER, Paul, THUSWALDNER, Jörg
• Format: Article
• Language: English
• Subjects: Algebra; Coefficients; Exact sciences and technology; Global analysis, analysis on manifolds; Hyperplanes; Hypersurfaces; Integers; Mathematical vectors; Mathematics; Number theory; Periodic orbits; Periodicity; Polynomials; Sciences and techniques of general use; Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
• ISSN: 1246-7405; 2118-8572
• DOI: 10.5802/jtnb.725

Pour r = (r₀,...rd-1)ϵ ℝd, nous définissons la fonction τr: ℤd→ℤd, z=(z₀,...,zd-1)↦(z₁,..,zd-1-[rz]), où rz est le produit scalaire des vecteurs r et z. Si chaque orbite de τr se termine par O, nous dirons que τr est un shift radix system. Il est bien connu que chaque orbite de τr est ultimement périodique si le polynôme td + rd-1td-1+···+r₀ associé à r est contractant. D'autre part, si ce polynôme a au moins une racine en dehors du disque unité, il existe des vecteurs initiaux qui conduisent à des orbites non-bornées. Le présent article considère les cas restants pour les propriétés de périodicité des applications τr pour des vecteurs r associés à des polynômes dont les racines ont un module supérieur ou égal à un, avec égalité dans au moins un cas. Nous montrons que pour une large classe de vecteurs r appartenant à la famille précédente, l'ultime périodicité des orbites est équivalente au fait que τs est un shift radix system ou a une autre structure prescrite d'orbite pour un certain paramètre s dépendant de r. Ces résultats sont combinés avec de nouveaux résultats algorithmiques dans le but de caractériser les vecteurs de la classe précédente qui donnent des orbites ultimement périodiques pour chaque valeur initiale. En particulier, nous donnons la description de ces vecteurs r pour le cas d = 3. Cela conduit à des ensembles qui semblent avoir une structure très compliquée. For r = (r₀,..., rd-1) ϵ ℝd define the function τr: ℤd→ℤd, z=(z₀,...,zd-1)↦(z₁,..,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-1 td-1+··· +r₀ associated to 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 cla