For a real number β>1, we say that a permutation π of length n is allowed (or realized) by the β-shift if there is some x∈[0,1] such that the relative order of the sequence x,f(x),…,fn-1(x), where f(x) is the fractional part of βx, is the same as that of the entries of π. Widely studied from such diverse fields as number theory and automata theory, β-shifts are prototypical examples of one-dimensional chaotic dynamical systems. When β is an integer, permutations realized by shifts have been recently characterized. In this paper we generalize some of the results to arbitrary β-shifts. We describe a method to compute, for any given permutation π, the smallest β such that π is realized by the β-shift.
Résumé. Pour un nombre réel β>1, on dit qu'une permutation π de longueur n est permise (ou réalisée) par β-shift s'il existe x∈[0,1] tel que l'ordre relatif de la séquence x,f(x),…,fn-1(x), où f(x) est la partie fractionnaire de βx, soit le même que celui des entrées de π. Largement étudiés dans des domaines aussi divers que la théorie des nombres et la théorie des automates, les β-shifts sont des prototypes de systèmes dynamiques chaotiques unidimensionnels. Quand β est un nombre entier, les permutations réalisées par décalages ont été récemment caractérisées. Dans cet article, nous généralisons certains des résultats au cas de β-shifts arbitraires. Nous décrivons une méthode pour calculer, pour toute permutation donnée π, le plus petit β tel que π soit réalisée par β-shift.