Kybernetika 47 no. 1, 74-92, 2011

Arithmetics in numeration systems with negative quadratic base

Zuzana Masáková and Tomáš Vávra

Abstract:

We consider positional numeration system with negative base $-\beta$, as introduced by Ito and Sadahiro. In particular, we focus on arithmetical properties of such systems when $\beta$ is a quadratic Pisot number. We study a class of roots $\beta>1$ of polynomials $x^2-mx-n$, $m\geq n\geq 1$, and show that in this case the set ${\rm Fin}(-\beta)$ of finite $(-\beta)$-expansions is closed under addition, although it is not closed under subtraction. A particular example is $\beta=\tau=\frac12(1+\sqrt5)$, the golden ratio. For such $\beta$, we determine the exact bound on the number of fractional digits appearing in arithmetical operations. We also show that the set of $(-\tau)$-integers coincides on the positive half-line with the set of $(\tau^2)$-integers.

Keywords:

numeration systems, negative base, Pisot number

Classification:

11K16, 68R15

References:

  1. F. Bassino: $\beta$-expansions for cubic Pisot numbers. In: 5th Latin American Theoretical Informatics Symposium (LATIN'02), Cancun 2002, Springer-Verlag, Lecture Notes in Comp. Sci. 2286 (2002), pp. 141-152.   CrossRef
  2. J. Bernat: Arithmetics in $\beta$-numeration. Discr. Math. Theor. Comp. Sci. 9 (2007), 85-106.   CrossRef
  3. \v{C}. Burd\'\i k, Ch. Frougny, J.-P. Gazeau and R. Krejcar: Beta-integers as natural counting systems for quasicrystals. J.~Phys. A: Math. Gen. 31 (1998), 6449-6472.   CrossRef
  4. S. Fabre: Substitutions et $\beta$-syst\`emes de num\'eration. Theoret. Comput. Sci. 137 (1995), 219-236.   CrossRef
  5. Ch. Frougny: On-line addition in real base. In: Proc. MFCS 1999, Lectures Notes in Comput. Sci. 1672 (1999), pp. 1-11.   CrossRef
  6. Ch. Frougny and A. C. Lai: On negative bases. In: Proc. DLT 09, Lectures Notes in Comput. Sci. 5583 (2009), 252-263.   CrossRef
  7. Ch. Frougny and B. Solomyak: Finite $\beta$-expansions. Ergodic Theory Dynamical Systems 12 (1994), 713-723.   CrossRef
  8. Ch. Frougny and A. Surarerks: On-line multiplication in real and complex base. In: Proc. IEEE Arith. 16, IEEE Computer Society Press 2003, pp. 212-219.   CrossRef
  9. L. S. Guimond, Z. Mas\'akov\'a and E. Pelantov\'a: Arithmetics of beta-expansions. Acta Arith. 112 (2004), 23-40.   CrossRef
  10. S. Ito and T. Sadahiro: $(-\beta)$-expansions of real numbers. Integers 9 (2009), 239-259.   CrossRef
  11. C. Kalle and W. Steiner: Beta-expansions, natural extensions and multiple tilings associated with Pisot units. To appear in Trans. Amer. Math. Soc. 2011.   CrossRef
  12. Z. Mas\'akov\'a, E. Pelantov\'a and T. V\'avra: Arithmetics in number systems with a negative base. Theor. Comp. Sci. 12 (2011), 835-845.   CrossRef
  13. C. Mazenc: On the Redundancy of Real Number Representation Systems. Research Report 93-16, Laboratoire de l'informatique du parall\'{e}lisme.   CrossRef
  14. W. Parry: On the $\beta$-expansions of real numbers. Acta Math. Acad. Sci. Hung. 11 (1960), 401-416.   CrossRef
  15. A. R\'enyi: Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hung. 8 (1957), 477-493.   CrossRef
  16. K. Schmidt: On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc. 12 (1980), 269-278.   CrossRef
  17. W. Steiner: On the structure of $(-\beta)$-integers. Preprint 2010.   CrossRef
  18. W. P. Thurston: Groups, tilings, and finite state automata. AMS Colloquium Lecture Notes, American Mathematical Society, Boulder 1989.   CrossRef