Arithmetics in numeration systems with negative quadratic base

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

Kybernetika (2011)

  • Volume: 47, Issue: 1, page 74-92
  • ISSN: 0023-5954

Abstract

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

How to cite

top

Masáková, Zuzana, and Vávra, Tomáš. "Arithmetics in numeration systems with negative quadratic base." Kybernetika 47.1 (2011): 74-92. <http://eudml.org/doc/197050>.

@article{Masáková2011,
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\ge n\ge 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 =\frac\{1\}\{2\}(1+\sqrt\{5\})$, 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.},
author = {Masáková, Zuzana, Vávra, Tomáš},
journal = {Kybernetika},
keywords = {numeration systems; negative base; Pisot number; numeration systems; negative base; Pisot number},
language = {eng},
number = {1},
pages = {74-92},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Arithmetics in numeration systems with negative quadratic base},
url = {http://eudml.org/doc/197050},
volume = {47},
year = {2011},
}

TY - JOUR
AU - Masáková, Zuzana
AU - Vávra, Tomáš
TI - Arithmetics in numeration systems with negative quadratic base
JO - Kybernetika
PY - 2011
PB - Institute of Information Theory and Automation AS CR
VL - 47
IS - 1
SP - 74
EP - 92
AB - 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\ge n\ge 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 =\frac{1}{2}(1+\sqrt{5})$, 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.
LA - eng
KW - numeration systems; negative base; Pisot number; numeration systems; negative base; Pisot number
UR - http://eudml.org/doc/197050
ER -

References

top
  1. Ambrož, P., Dombek, D., Masáková, Z., Pelantová, E., Numbers with integer expansion in the numeration system with negative base, Preprint 2009. (2009) MR3051451
  2. Balková, L., Gazeau, J.-P., Pelantová, E., 10.1007/s11005-008-0241-z, Lett. Math. Phys. 84 (2008), 179–198. (2008) Zbl1185.11063MR2415548DOI10.1007/s11005-008-0241-z
  3. Bassino, F., β -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. (2002) Zbl1152.11342MR1966122
  4. Bernat, J., Arithmetics in β -numeration, Discr. Math. Theor. Comp. Sci. 9 (2007), 85–106. (2007) Zbl1152.68456MR2318443
  5. Burdík, Č., Frougny, Ch., Gazeau, J.-P., Krejcar, R., 10.1088/0305-4470/31/30/011, J. Phys. A: Math. Gen. 31 (1998), 6449–6472. (1998) MR1644115DOI10.1088/0305-4470/31/30/011
  6. Fabre, S., 10.1016/0304-3975(95)91132-A, Theoret. Comput. Sci. 137 (1995), 219–236. (1995) Zbl0872.11017MR1311222DOI10.1016/0304-3975(95)91132-A
  7. Frougny, Ch., On-line addition in real base, In: Proc. MFCS 1999, Lectures Notes in Comput. Sci. 1672 (1999), pp. 1–11. (1999) Zbl0955.68130MR1731220
  8. Frougny, Ch., Lai, A. C., On negative bases, In: Proc. DLT 09, Lectures Notes in Comput. Sci. 5583 (2009), 252–263. (2009) Zbl1247.68139MR2544706
  9. Frougny, Ch., Solomyak, B., Finite β -expansions, Ergodic Theory Dynamical Systems 12 (1994), 713–723. (1994) MR1200339
  10. Frougny, Ch., Surarerks, A., On-line multiplication in real and complex base, In: Proc. IEEE Arith. 16, IEEE Computer Society Press 2003, pp. 212–219. (2003) 
  11. Guimond, L. S., Masáková, Z., Pelantová, E., 10.4064/aa112-1-2, Acta Arith. 112 (2004), 23–40. (2004) Zbl1060.11065DOI10.4064/aa112-1-2
  12. Ito, S., Sadahiro, T., ( - β ) -expansions of real numbers, Integers 9 (2009), 239–259. (2009) MR2534912
  13. Kalle, C., Steiner, W., Beta-expansions, natural extensions and multiple tilings associated with Pisot units, To appear in Trans. Amer. Math. Soc. 2011. (2011) MR2888207
  14. Masáková, Z., Pelantová, E., Vávra, T., 10.1016/j.tcs.2010.11.033, Theor. Comp. Sci. 12 (2011), 835–845. (2011) Zbl1226.11015DOI10.1016/j.tcs.2010.11.033
  15. Mazenc, C., On the Redundancy of Real Number Representation Systems, Research Report 93-16, Laboratoire de l’informatique du parallélisme. 
  16. Parry, W., 10.1007/BF02020954, Acta Math. Acad. Sci. Hung. 11 (1960), 401–416. (1960) Zbl0099.28103MR0142719DOI10.1007/BF02020954
  17. Rényi, A., 10.1007/BF02020331, Acta Math. Acad. Sci. Hung. 8 (1957), 477–493. (1957) MR0097374DOI10.1007/BF02020331
  18. Schmidt, K., 10.1112/blms/12.4.269, Bull. London Math. Soc. 12 (1980), 269–278. (1980) Zbl0494.10040MR0576976DOI10.1112/blms/12.4.269
  19. Steiner, W., On the structure of ( - β ) -integers, Preprint 2010. (2010) MR2904969
  20. Thurston, W. P., Groups, tilings, and finite state automata, AMS Colloquium Lecture Notes, American Mathematical Society, Boulder 1989. (1989) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.