Affordable Access

On multiplicatively dependent linear numeration systems, and periodic points

Publication Date
  • Mathematics


ita0221.dvi Theoretical Informatics and Applications Theoret. Informatics Appl. 36 (2002) 293{314 DOI: 10.1051/ita:2002015 ON MULTIPLICATIVELY DEPENDENT LINEAR NUMERATION SYSTEMS, AND PERIODIC POINTS Christiane Frougny1, 2 Abstract. Two linear numeration systems, with characteristic poly- nomial equal to the minimal polynomial of two Pisot numbers � and γ respectively, such that � and γ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number. Mathematics Subject Classification. 11A63, 11A67, 11B39, 37B10, 68R15. 1. Introduction This work is about the conversion of integers represented in two different nu- meration systems, linked in a certain sense. Recall that the conversion between base 4 and base 2 is computable by a finite automaton, but that conversion be- tween base 3 and base 2 is not. More generally, two numbers p > 1 and q > 1 are said to be multiplicatively dependent if there exist positive integers k and ‘ such that pk = q‘. A set of natural numbers is said to be p-recognizable if the set of representations in base p of its elements is recognizable by a finite automa- ton. Bu˝chi has shown that the set fqn j n � 0g is p-recognizable only if p and q are multiplicatively dependent integers [5]. In contrast, the famous theorem of Cobham [7] states that the only sets of natural numbers that are both p- and q-recognizable, when p and q are two multiplicatively independent integers >1, Keywords and phrases: Numeration system, Pisot number, �nite automaton, periodic point. 1 LIAFA, UMR 7089 du CNRS, 2 place Jussieu, 75251 Paris Cedex 05, France; e-mail: [email protected] 2 Universit�e Paris 8, France c© EDP Sciences 2002 294 CH. FROUGNY are unions of arithmetic progressions, and thus are k-recognizable for a

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times