×

On number system constructions. (English) Zbl 1153.11003

Let \(\Lambda\) be a lattice, i.e., a free \({\mathbb Z}\)-module of rank \(k\), in \({\mathbb R}^k\), \(M:\Lambda\to\Lambda\) a group endomorphism with \(\det(M)\neq 0\) and \(D\) a finite subset of \(\Lambda\) containing \(0\). The triple \((\Lambda,M,D)\) is called a number system, if every element \(x\in\Lambda\) has a unique, finite representation of the form \(x=\sum_{i=0}^{\ell} M^i d_i\), where \(d_i\in D\) and \(\ell\in{\mathbb N}\).
The first half of the paper is devoted to an overview on results in this area. In the second part, the authors prove two results.
Let \(\Lambda\) and \(M\) be given. If the spectral radius of \(M^{-1}\) is less than \(1/2\), then there exists a digit set \(D\) for which \((\Lambda, M, D)\) is a number system.
Let \(f=c_0+c_1x+\cdots +c_k x^k\in{\mathbb Z}[x]\) with \(c_k=1\) be a polynomial and \(M\) its companion matrix. If the weak dominant condition \(| c_0| >2\sum_{i=1}^k | c_i| \) holds, then there exists a digit set \(D\) for which \(({\mathbb Z}^k, M, D)\) is a number system.

MSC:

11A63 Radix representation; digital problems
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] S. Akiyama and A. Petho, On canonical number systems, Theor. Comp. Sci., 270 (2002), 921–933. · Zbl 0988.68101
[2] S. Akiyama and H. Rao, New criteria for canonical number systems, Acta Arithm., 111 (2004), 5–25. · Zbl 1049.11008
[3] S. Akiyama, H. Brunotte and A. Petho, Cubic CNS polynomials, notes on a conjecture of W. J. Gilbert, J. Math. Anal. and Appl., 281 (2003), 402–415. · Zbl 1021.11005
[4] S. Akiyama, T. Borbély, H. Brunotte and A. Petho, On a generalization of the radix representation – a survey, in: High Primes and Misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Inst. Commun., 41 (2004), 19–27.
[5] A. Barbé and F. von Haeseler, Binary number systems for Z k , J. of Number Theory, 117 (2006), 14–30. · Zbl 1163.11302
[6] H. Brunotte, On trinomial bases of radix representation of algebraic integers, Acta Sci. Math. (Szeged), 67 (2001), 407–413. · Zbl 0996.11067
[7] H. Brunotte, Characterization of CNS trinomials, Acta Sci. Math. (Szeged), 68 (2002), 673–679. · Zbl 1026.11077
[8] P. Burcsi and A. Kovács, An algorithm checking a necessary condition of number system constructions, Annales Univ. Sci. Budapest., Sect. Comp., 25 (2005), 143–152. · Zbl 1109.11011
[9] G. Farkas, Location and number of periodic elements in Q(), Annales Univ. Sci. Budapest., Sect. Comp., 20 (2001), 133–146. · Zbl 0981.11006
[10] G. Farkas and A. Kovács, Digital expansion in Q(2)), Annales Univ. Sci. Budapest., Sect. Comp., 22 (2003), 83–94. · Zbl 1108.11013
[11] W. J. Gilbert, Radix representation of quadratic fields, J. Math. Anal. Appl., 83 (1991), 264–274. · Zbl 0472.10011
[12] I. Kátai, Construction of number systems in algebraic number fields, Annales Univ. Sci. Budapest., Sect. Comp., 18 (1999), 103–107. · Zbl 0963.11060
[13] I. Kátai, Number systems in imaginary quadratic fields, Annales Univ. Sci. Budapest., Sect. Comp., 18 (1994), 91–103. · Zbl 0817.11046
[14] I. Kátai, Generalized number systems in Euclidean spaces, Math. and Comp. Modelling, 38 (2003), 883–892. · Zbl 1083.11011
[15] I. Kátai and B. Kovács, Kanonische Zahlensysteme bei reelen quadratischen algebraischen Zahlen, Acta Sci. Math. (Szeged), 42 (1980), 99–107.
[16] I. Kátai and B. Kovács, Canonical number systems in imaginary quadratic fields, Acta Math. Hungar., 37 (1981), 159–164. · Zbl 0477.10012
[17] I. Kátai and I. Környei, On number systems in algebraic number fields, Publ. Math. Debrecen, 41 (1992), 289–294. · Zbl 0784.11049
[18] I. Kátai and J. Szabó, Canonical number systems for complex integers, Acta Sci. Math. (Szeged), 37 (1975), 255–260. · Zbl 0297.12003
[19] A. Kovács, On computation of attractors for invertible expanding linear operators in Z k , Publ. Math. Debrecen, 56 (2000), 97–120. · Zbl 0999.11009
[20] A. Kovács, Generalized binary number systems, Annales Univ. Sci. Budapest., Sect. Comp., 20 (2001), 195–206. · Zbl 0988.11002
[21] A. Kovács, Number expansion in lattices, Math. and Comp. Modelling, 38 (2003), 909–915. · Zbl 1100.11008
[22] A. Kovács, On expansions of Gaussian integers with non-negative digits, Math. Pannonica, 10 (1999), 177–191. · Zbl 0930.11077
[23] A. Kovács, Canonical expansions of integers in imaginary quadratic fields, Acta Math. Hungar., 93 (2001), 347–357. · Zbl 0997.11011
[24] B. Kovács, Canonical number systems in algebraic number fields, Acta Math. Acad. Sci. Hungar., 37 (1981), 405–407. · Zbl 0505.12001
[25] S. Körmendi, Canonical number systems in Q(3), Acta Sci. Math. (Szeged), 50 (1986), 351–357. · Zbl 0616.10007
[26] T. J. Laffey, Lectures on integer matrices, hermite.cii.fc.ul.pt/meetings/im_1997/lectures.pdf, 1–38.
[27] J. C. Lagarias and Y. Wang, Corrigendum/addendum: ”Haar bases for L 2(R n ) and algebraic number theory” [J. Number Theory, 57/1 (1996).] J. Number Theory, 76 (1999), 330–336. · Zbl 1007.11066
[28] C. G. Latimer and C. C. MacDuffee, A correspondence between classes of ideals and classes of matrices, Annals Math., 34 (1933), 313–316. · Zbl 0006.29002
[29] A. Petho, On a polynomial transformation and its application to the construction of a public key cryptosystem, in: Proc. Computational Number Theory, Walter de Gruyter Publ. Co. (1991), pp. 31–44.
[30] K. Scheicher and J. M. Thuswaldner, On the characterization of canonical number systems, Osaka J. Math., 41 (2004), 327–351. · Zbl 1161.11305
[31] G. Steidl, On symmetric representation of Gaussian integers, BIT, 29 (1989), 563–571. · Zbl 0685.12002
[32] O. Taussky, On matrix classes corresponding to an ideal and its inverse, Illinois J. Math., 1 (1957), 108–113. · Zbl 0078.02903
[33] J. M. Thuswaldner, Attractors for invertible expanding linear operators and number systems in Z 2, Publ. Math. Debrecen, 58 (2001), 423–440. · Zbl 1012.11009
[34] A. Vince, Replicating tessellations, SIAM J. Discrete Math., 6 (1995), 191–215. · Zbl 0826.52019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.