On Multiplicative Independent Bases for Canonical Number Systems in Cyclotomic Number Fields

About the paper

ISBN
coauthors Manfred Madritsch
Volker Ziegler
language English
published in Elsholtz C., Grabner P.
Number Theory – Diophantine Problems, Uniform Distribution and Applications
Springer, Cham (2017)
pages 313 to 332
DOI 10.1007/978-3-319-55357-3_16
supported by FWF, project P23990

Abstract

In the present paper we are interested in number systems in the ring of integers of cyclotomic number fields in order to obtain a result equivalent to Cobham’s theorem. For this reason we first search for potential bases. This is done in a very general way in terms of canonical number systems. In a second step we analyse pairs of bases in view of their multiplicative independence. In the last part we state an appropriate variant of Cobham’s theorem.

References

  1. B. Adamczewski, J. Bell, An analogue of Cobham’s theorem for fractals, Trans. Am. Math. Soc. 363 (2011), 4421—4442.
  2. S. Akiyama, A. Pethő, On canonical number systems, Theor. Comput. Sci. 270 (2002), 921—933.
  3. S. Akiyama, H. Rao, New criteria for canonical number systems, Acta Arith. 111 (2004), 5—25.
  4. S. Akiyama, H. Brunotte, A. Petho, Cubic CNS polynomials, notes on a conjecture of W.J. Gilbert, J. Math. Anal. Appl. 281 (2003), 402—415
  5. S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, J.M. Thuswaldner, Generalized radix representations and dynamical systems I, Acta Math. Hungar. 108 (2005), 207—238.
  6. S. Akiyama, H. Brunotte, A. Pethő, J.M. Thuswaldner, Generalized radix representations and dynamical systems II, Acta Arith. 121 (2006), 21—61.
  7. S. Akiyama, H. Brunotte, A. Pethő, Reducible cubic CNS polynomials, Period. Math. Hungar. 55 (2207), 177—183.
  8. A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui n’est pas entière, Acta Math. Hungar. 54 (1989), 237—241.
  9. B. Boigelot, J. Brusten, A generalization of Cobham’s theorem to automata over real numbers, Theor. Comput. Sci. 410 (2009), 1694—1703.
  10. A. Bremner, On power bases in cyclotomic number fields, J. Number Theory 28 (1988), 288—298.
  11. H. Brunotte, On trinomial bases of radix representations of algebraic integers, Acta Sci. Math. Acta Sci. Math. (Szeged), 67 (2001), 521—527.
  12. H. Brunotte, Characterization of CNS trinomials, Acta Sci. Math. (Szeged) 68 (2002), 673—679.
  13. H. Brunotte, On cubic CNS polynomials with three real roots, Acta Sci. Math. (Szeged) 70 (2004), 495—504.
  14. H. Brunotte, Symmetric CNS trinomials, Integers 9 (2009), 201—214.
  15. H. Brunotte, A unified proof of two classical theorems on CNS polynomials, Integers 12 (2012), 709—721.
  16. H. Brunotte, Unusual CNS polynomials, Math. Pannon. 24 (2013), 125—137.
  17. H. Brunotte, A. Huszti, A. Pethő, Bases of canonical number systems in quartic algebraic number fields, J. Théor. Nombres Bordeaux 18 (2006), 537–557.
  18. A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theory 3 (1969), 186—192.
  19. F. Durand, Cobham’s theorem for substitutions, J. Eur. Math. Soc. (JEMS) 13 (2011), 1799—1814.
  20. F. Durand, M. Rigo, On Cobham’s theorem, in Handbook of Automata: From Mathematics to Applications (European Mathematical Society Publishing House, Zurich, 2017).
  21. S. Eilenberg, Automata, Languages, and Machines. Vol. A, Pure and Applied Mathematics, vol. 58 (Academic Press, New York, 1974).
  22. I. Gaál, L. Robertson, Power integral bases in prime-power cyclotomic fields, J. Number Theory 120 (2006), 372—384.
  23. W.J. Gilbert, Radix representations of quadratic fields, J. Math. Anal. Appl. 83 (1981), 264—274.
  24. G. Hansel, T. Safer, Vers un théorème de Cobham pour les entiers de Gauss, Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 723—735.
  25. I. Kátai, B. Kovács, Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen Zahlen, Acta Sci. Math. (Szeged) 42 (1980), 99—107.
  26. I. Kátai, B. Kovács, Canonical number systems in imaginary quadratic fields, Acta Math. Acad. Sci. Hungar. 37 (1981), 159—164.
  27. I. Kátai, J. Szabó, Canonical number systems for complex integers, Acta Sci. Math. (Szeged) 37 (1975), 255—260.
  28. S.I. Khmelnik, Specialized digital computer for operations with complex numbers, Quest. Radio Electronics XII (1964), 60—82. In Russian.
  29. P. Kirschenhofer, J.M. Thuswaldner, Shift radix systems—a survey, RIMS K%circo;ky&circu;roku Bessatsu B46 (2014), 1—59.
  30. D.E. Knuth, A imaginary number system, CACM 3 (1960), 245—247.
  31. D.E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, London, 1998.
  32. B. Kovács, Canonical number systems in algebraic number fields, Acta Math. Hungar. 37 (1981), 405—407.
  33. B. Kovács, A. Pethő, Number systems in integral domains, especially in orders of algebraic number fields, Acta Sci. Math. (Szeged) 55 (1981), 287—299.
  34. B. Kovács, A. Pethő, On a representation of algebraic integers, Studia Sci. Math. Hungar. 27 (1992), 169—172.
  35. M.G. Madritsch, V. Ziegler, An infinite family of multiplicatively independent bases of number systems in cyclotomic number fields, Acta Sci. Math. (Szeged) 81 (2015), 33—44.
  36. M.G. Madritsch, V. Ziegler, On multiplicatively independent bases in cyclotomic number fields, Acta Math. Hungar. 146 (2015), 224—239.
  37. W. Penney, A "binary" system for complex numbers, J. ACM 12(1965), 247—249.
  38. A. Pethő, On a polynomial transformation and its application to the construction of a public key cryptosystem, in: Computational Number Theory, Debrecen, 1989, de Gruyter, Berlin, 1991, 31—43.
  39. A. Pethő, R.F. Tichy, S-unit equations, linear recurrences and digit expansions, Math. Debr. 42 (1993), 145—154.
  40. G. Ranieri, Générateurs de l’anneau des entiers d’une extension cyclotomique, J. Number Theory 128 (2008), 1576—1586.
  41. L. Robertson, Power bases for cyclotomic integer rings, J. Number Theory 69 (1998), 98—118.
  42. L. Robertson, Power bases for 2-power cyclotomic fields, J. Number Theory 88 (2001), 196—209.
  43. L. Robertson, Monogeneity in cyclotomic fields, Int. J. Number Theory 6 (2010), 1589—1607.
  44. L. Robertson, R. Russell, A hybrid Gröbner bases approach to computing power integral bases, Acta Math. Hungar. 147 (2015), 427—437.
  45. J. Sakarovitch, Elements of Automata Theory Cambridge University Press, Cambridge, 2009.
  46. H.P. Schlickewei, Linear equations in integers with bounded sum of digits, J. Number Theory 35 (1990), 335—244.
  47. K. Scheicher, J.M. Thuswaldner, On the characterization of canonical number systems, Osaka J. Math. 41 (2004), 327—351.
  48. K. Scheicher, P. Surer, J.M. Thuswaldner, C.E. van de Woestijne, Digit systems over commutative rings, Int. J. Number Theory 10 (2004), 1459—1483.
  49. H.G. Senge, E.G. Straus, PV-numbers and sets of multiplicity, Period. Math. Hungar. 3 (1973), 93—100.
  50. C.L. Stewart, On the representation of an integer in two different bases, J. Reine Angew. Math. 319 (1980), 63—72.
  51. M. Waldschmidt, Diophantine Approximation on Linear Algebraic Groups, Grundlehren der Mathematischen Wissenschaften, vol. 326 (Springer, Berlin, 2000)

Links

Information on the entire collection at Springer
Austrian Science Foundation (FWF)