Kybernetika 49 no. 2, 258-279, 2013

Greedy and lazy representations in negative base systems

Tomáš Hejda, Zuzana Masáková and Edita Pelantová

Abstract:

We consider positional numeration systems with negative real base $-\beta$, where $\beta>1$, and study the extremal representations in these systems, called here the greedy and lazy representations. We give algorithms for determination of minimal and maximal $(-\beta)$-representation with respect to the alternate order. We also show that both extremal representations can be obtained as representations in the positive base $\beta^2$ with a non-integer alphabet. This enables us to characterize digit sequences admissible as greedy and lazy $(-\beta)$-representation. Such a characterization allows us to study the set of uniquely representable numbers. In the case that $\beta$ is the golden ratio and the Tribonacci constant, we give the characterization of digit sequences admissible as greedy and lazy $(-\beta)$-representation using a set of forbidden strings.

Keywords:

numeration systems, negative base, lazy representation, greedy representation, unique representation

Classification:

11A63, 37B10

References:

  1. K. Dajani and Ch. Kalle: Transformations generating negative $\beta$-expansions. Integers 11B (2011), A5, 1-18.   CrossRef
  2. K. Dajani and C. Kraaikamp: From greedy to lazy expansions and their driving dynamics. Exposition. Math. 20 (2002), 4, 315-327.   CrossRef
  3. M. de Vries and V. Komornik: Unique expansions of real numbers. Adv. Math. 221 (2009), 2, 390-427.   CrossRef
  4. P. Erd{ö}s, I. Jo{ó} and V. Komornik: Characterization of the unique expansions $1=\sum^\infty_{i=1}q^{-n_i}$ and related problems. Bull. Soc. Math. France 118 (1990), 3, 377-390.   CrossRef
  5. S. Ito and T. Sadahiro: Beta-expansions with negative bases. Integers 9 (2009), A22, 239-259.   CrossRef
  6. Ch. Kalle and W. Steiner: Beta-expansions, natural extensions and multiple tilings associated with Pisot units. Trans. Amer. Math. Soc. 364 (2012), 2281-2318.   CrossRef
  7. W. Parry: On the $\beta $-expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416.   CrossRef
  8. M. Pedicini: Greedy expansions and sets with deleted digits. Theoret. Comput. Sci. 332 (2005), 1-3, 313-336.   CrossRef
  9. A. Rényi: Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8 (1957), 477-493.   CrossRef
  10. K. Schmidt: On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc. 12 (1980), 4, 269-278.   CrossRef
  11. W. Thurston: Groups, tilings, and finite state automata. AMS Colloquium Lecture Notes, American Mathematical Society, Boulder, 1989.   CrossRef