AP05_5.vp 1 Introduction Numeration systems with an irrational base � give us an opportunity to perform exact arithmetic operations with irra- tional numbers – a tool necessary for the new methods of building aperiodic random number generators, for new cryp- tographic methods and also for the mathematical modelling of recently discovered materials with a long range order – so called quasicrystals. The whole field of irrational numeration originates from the article of A. Rényi [1], in which he proved that for each real base �>1 and for every positive real number x, there exists a unique representation of the number x in the numera- tion system with the base �. However, contrary to the usual numeration system with an integer base (such as binary or decimal numeration systems), there are several strange and unsteady (i.e. depending on the nature of the base �) phe- nomena, which have to be examined and described before we are able to employ these systems. The work is organized as follows. In the first part, there is a survey of the already classical �-expansions of real numbers. We recall basic definitions and fundamentals; then we discuss two key problems of these numeration systems – the so-called Finiteness property and the problem of fractional parts aris- ing under addition and multiplication of integers. In the second part, we study a slightly different approach to irrational representations of real numbers, which is called �-adic expansions. Since this concept has been much less studied in the past, we focus on one particular irrationality (namely the golden mean �), rather than trying to explain everything in general. After giving necessary definitions we discuss the relations of these �-adic expansions with integers and rationals, and we also study an analogue to the finiteness problem for �-expansions. 2 Beta-numeration systems Let �>1 be a fixed real number. A representation in base � (or simply �-representation) of a real number x � �R is an infi- nite sequence ( )xi n i� ���, xi � Z such that x x x x xn n n n� � � � � �� � � �� � � �1 1 0 0 1 1 � � for some n � Z. A particular �-representation with xi i i N N� � ��� � 1 for all �� N n is called �-expansion, see [1]. The greedy algorithm computes the digits of the �-expansions of a real number x: Let [ ]x and { }x denote the integer and the fractional part of x, respective- ly. Find n � Z such that � �n nx� �1. Put x xn n� [ ]� and r xn n� [ ]� . For i n n� � �1 2, ,� put x ri i� �[ ]� 1 and r ri i� �[ ]� 1 . The �-expansion can be seen as an analogue to the ordi- nary expansion in a system with an integer base (such as a dec- imal or binary system), we usually use the natural notation x x x x xn n� � �� �1 0 1� � and we say that the coefficients x xn� 0 form the integer part, whereas the coefficients x x� �1 2� form the fractional part of the �-expansion of a number x. A sequence of integer coefficients that corresponds to some �-expansion is sometimes called admissible in the �-nu- meration system. A sequence (or string) of integer coefficients that is not admissible is called forbidden. For the characteriza- tion of an admissible sequence one needs to introduce the so-called Rényi expansion of 1, d t t t�( ):1 1 2 3� �, where t1 � [ ]� and tn n n � � � 2 is the �-expansion of1 1� t �. The �-expan- sions (or �-admissible sequences) are then characterized by the Parry condition. Theorem 1.1: (Parry [2]). Let �>1 be a real number. Let d t t t�( ):1 1 2 3� � be the Rényi expansion of one. The sequence ( )xi n i m� � with xi �{ , , , [ ]}0 1 � � is a �-expansion of some x � 0 if and only if x x xn p n p m� � �1� is lexicographically strictly smaller (denoted by the symbol �) than d�( )1 for all 0 � � �p n m. The set of those x �R for which the �-expansion of x has only a finite number of non-zero fractional coefficients is denoted by Fin( )� . If the �-expansion of a real number x is of the form x xi i i n � � �0 , i.e. there is no fractional part, the number x is said to be a �-integer. The set of all �-integers is denoted by Z�. 2.1 Finiteness condition In general, the set Fin( )� does not have to be closed under arithmetic operations, and there is no criterion known which would decide whether Fin( )� is a ring. The �-numeration systems for which Fin( )� is a ring are equally characterized by the so-called Property (F) (F) Z [ ] ( )� �� �1 Fin , 24 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 5/2005 Czech Technical University in Prague Non-Standard Numeration Systems P. Ambrož We study some properties of non-standard numeration systems with an irrational base � >1, based on the so-called beta-expansions of real numbers [1]. We discuss two important properties of these systems, namely the Finiteness property, stating whether the set of finite expansions in a given system forms a ring, and then the problem of fractional digits arising under arithmetic operations with integers in a given system. Then we introduce another way of irrational representation of numbers, slightly different from classical beta-expansions. Here we restrict ourselves to one irrational base – the golden mean � – and we study the Finiteness property again. Keywords: numeration system, beta expansion, tau-adic expansion. where Z [ ]� denotes the ring of polynomials with integer coefficients in �. It is known [3] that the condition (F) implies that � is a Pisot number (an algebraic integer with all its algebraic conju- gates in modulus smaller than one). Several authors have found partial answers to the finiteness question by giving some sufficient conditions on the minimal polynomial of �. Theorem 2.1: (Frougny, Solomyak [3]). Let � be a positive root of the polynomial M x x a x am m m( ) � � � � � 1 1 � , ai � Z and a a am1 2 0� � � �� . Then � is a Pisot number and Prop- erty (F) holds for �. Theorem 2.2: (Hollander [4]). Let � be an algebraic integer with the minimal polynomial M x x a x am m m( ) � � � � � 1 1 � , ai � Z, ai � 0 and a a a am1 2 3� � � �� . Then Property (F) holds for �. Akiyama [5] proved a necessary and sufficient condition, however it is unfortunately quite vague. Theorem 2.3: (Akiyama [5]). Let � be a Pisot number of the degree m. Then � has Property (F) if and only if every element of x x x x j mj j � � � � � � � �� Z[ ]| ,| [ ] , , ,( ) ( ) ( ) � � � 0 1 1 2 31 for � � � � �� has a finite �-expansion in base �. Here x i( ) with i m�1 2, , ,� are the conjugates of x �Q( )� in the algebraic field. Ambrož et al. [6] gave a partial characterization of num- bers � fulfilling Property (F) in terms of minimal forbidden strings. Definition 2.4: Let � > 1. A forbidden string ukuk�1…u0 of non-negative integers is called minimal, if � uk�1…u0 and uk…u1 are admissible, � ui �1 implies uk…ui�1(ui�1) ui�1…u0 is admissible, for all i k� 0 1, , ,� . The conditions based on the above-defined notion of minimal forbidden strings were given by the following two propositions. Proposition 2.5: (Property (T)). If Fin( )� is closed under ad- dition of two positive numbers, then � must satisfy the follow- ing property: For every minimal forbidden string ukuk�1…u0 there exists a finite sequence vnvn�1…v of non-negative in- tegers, such that � k n, � � , � v v u u un n k k� � �� � � � � �� �� 1 0 , � v v v u un n k n k � � 1 000 0� � ��� �� ( )times . Theorem 2.6: (Ambrož et al. [6]). Let � > 1 satisfy Property (T), and suppose that for every minimal forbidden string ukuk�1…u0 we have the following condition: If vnvn�1…v is the lexicographically greater string of (T) corresponding to ukuk�1…u0 then v v v u u un n k k� � � � � � �� �1 1 0� �� . Then Fin( )� is closed under addition of positive elements. Moreover, for every positive x y, ( )�Fin � , the �-expansion of x y� can be obtained from any �-representation of x y� using finitely many transcriptions. Finally, Akiyama gave an algebraic characterization of cubic Pisot numbers satisfying Property (F). Theorem 2.7: (Akiyama [7]) Let � be a cubic Pisot number. � has Property (F) if and only if � is a root of the following poly- nomial with integer coefficients x ax bx3 2 1� � � where a � 0 and � � � �1 1b a . 2.2 Number of fractional digits The second question concerning arithmetics in �-numera- tion systems is connected to the fact that for non-integer � the set Z � is not closed under arithmetic operations. However, sometimes it is true that the result of addition or multiplica- tion of two �-integers has only a finite fractional part. Then it is interesting to try to estimate the maximal length of such fractional part. More precisely, the task is as follows. For given � find the value, or at least some good estimate, of the quantities L n x y x y x y n� �� � � � � � � � �( ): min{ | , , ( ) },� � �� �N Z ZFin L n x y xy xy n� �� � � � � � �( ): min{ | , , ( ) }� � �� �N Z ZFin . Two methods for estimation of L�( )� , L�( )� are known. The first of them uses the so-called Meyer property of the set of �-integers for � Pisot number, namely that Z Z Z� � �� � � F where F is a finite set, and Z Z Z� � �� � G where G is a finite set. This method is used in [6] to find values of L�( )� , L�( )� for � the Pisot number, solution of the equation x x x3 225 15 2� � � . The second, much more widely used method for estima- tion of L�( )� , L�( )� is based on the following theorem. Several version of this method are employed in [6, 8, 9, 10, 11, 12]. Theorem 2.8: (Guimond et al. [10]). Let � > 1 be an algebraic number, and let �� be its algebraic conjugate. For z �Q( )� we denote by �z the image of z under the field isomorphism � �: ( ) ( )Q Q� � . If H z z Z: sup{ | }� � � ��� , K z z Z Z: inf{ | \ }� � � �� �� 0, then 1 2 � � � � � � � � � � � L H K and 1 2 � � � � � � � � � � � L H K . Some known results on the values of L�( )� , L�( )� � Knuth [13]: L� �( )� 2, � root of x x 2 1� � . � Burdík et al. [14] L L� �� �( ) ( )� � 1 for � root of equation x mx 2 1� � , L L� �� �( ) ( )� � 2 for � root of equation x mx 2 1� � . � Guimond et al. [10] for � root the equation x mx n2 � � , m n� © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 25 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 5/2005 2 1 1 2 1 m m n L m m n � � � ! " #" � � � � $ % "" �( )� , L L m� �� �( ) ( ) log ( )� �4 22 . � Messaoudi [15]: L� �( )� 6 for � root of the equation x x x3 2 1� � � , that is the so-called Tribonacci number. � Ambrož et al. [6] for � Tribonacci number 5 6� ��L ( )� and 4 6� ��L ( )� and L� �( )� 5, L� �( )� 7 for � root of the equation x x x3 225 15 2� � � . � Bernat [9] gave an exact value for the Tribonacci addition, L� �( )� 5. � Ambrož et al. [8] for the � root of the equation x mx x3 2 1� � � 5 6� ��L ( )� for m � 2, 4 5� ��L ( )� for m � 3, 4 6� ��L ( )� for m � 2. 3 Tau-adic numeration system Let � be the golden mean, i.e. the Pisot number, root of the equation x x2 1� � and �� its algebraic conjugate. A �-adic rep- resentation of a real number x �R is a left-infinite sequence ( )di n i� � �, di � Z, n � �Z , such that x di i i n � � �� � ( )� . It is denoted � � �� �� ( ):x d d d d n� �1 0 1 . The value of a �-adic re- presentation is obtained by the function �: *Z R given by & '� �( ) : ( )d di n i i ii n� � � �� � � � . If all finite factors of the sequence ( )di n i� � � are admissi- ble in the �-numeration system, the sequence ( )di n i� � � is said to be the �-adic expansion of the number x, and it is de- noted �� x . 3.1 Basic properties of �-adic expansions We know [3] that Fin( ) [ ] { | , }� � �� � � �Z Za b a b . Hence for any z � �Z there exist m n, � Z, m n� such that z zi i i m n � � � thus z zi i i m n � � � (� � , i.e. for each z � �Z the �-adic expansion � � � � z z is a finite word with some possible fractional part. For negative integers z � �Z we have the fol- lowing proposition. Proposition 3.1: (Ambrož [16]). Letz � �Z be a negative integer. Its �-adic expansion �� z is a left infinite, eventu- ally periodic word of the form � � � �z v( )10 , where v x� � , x �Fin( )� . Moreover, in [16], an algorithm is given for computing �-adic expansions of negative integers. Since most of the �-adic expansions that we are dealing with are left infinite, eventually periodic, we define the follow- ing two sets of numbers. Iep( ): { | ( ) }� � � � �� � �� � �x R x d d d dk k k�� �1 0 , Fep( ): { | ( ) }� � � � �� � � � �� � �x R x d d d d d dk k k m�� � �1 0 1 , Indeed, Z F� �ep( )� . Concerning rational numbers, there is also an algorithm for computing their �-adic expansions [16], which was used to prove that also every rational number has its �-adic expan- sion, eventually periodic to the left, more precisely we have Q I( � � �( , ] ( )1 1 ep � and Q F� �ep( )� . 3.2 Finiteness condition In accordance with the usual �-expansions, it is interesting to inspect the properties of the set Fep( )�� , which can be seen as a �-adic correlate of the set Fin( )� . In [17] there is a proof that the set Fep( )�� is closed under the addition. The proof is of a constructive type, consisting of building a right to left transducer performing the addition, which preserves the pe- riodicity of its input. When we know that Fep( )�� is closed under addition of positive elements, it is quite easy to prove that it is a ring. Finally, there has been shown a relation be- tween eventually periodic �-adic expansions and the elements of the ring Q( )� . Theorem 3.2: (Ambrož [17]). The field Q( )�� (and therefore also the field Q( )� ) is equal to the set Fep( )�� of all real numbers having eventually periodic �-adic expansion with a finite frac- tional part. 4 Future perspectives There are several objectives that can be pursued in the fu- ture. Concerning the already classical �-expansions, there is always the challenging problem of the algebraic characteri- zation of numbers � satisfying Property (F). Moreover, there is a lot of work to be done while looking for the number of fractional digits arising under arithmetic operations. Finally, there is an open question [6] of finding arithmetic algorithms working with infinite, but periodic �-expansions. A partial answer to the last question was recently given by the author in [18]. Concerning the second notion of irrational representa- tion – �-adic expansions – there are also several possible ways of future research. It seems quite obvious that it will be only a question of solving some technical obstacles to broaden the �-adic expansions onto the �-adic expansions, for some class of �. Indeed, those classes of � fulfilling the Property (F) are suitable candidates. On the other hand, the proof of the finiteness property for the �-adic expansions is deeply connected with the nature of the system itself and its general- ization for some other irrationalities will be difficult or even impossible to perform without changing the approach. Acknowledgment The author acknowledges financial support from the Grant Agency of the Czech Republic GAČR 201/05/0169. References [1] Rényi, A.: “Representation for Real Numbers and Their Ergodic Properties.” Acta Math. Acad. Sci. Hungar, Vol. 8 (1957), p. 477–493. [2] Parry, W.: “On the �-Expansions of Real Numbers.” Acta Math. Acad. Sci. Hungar, Vol. 11 (1960), p. 401–416. [3] Frougny, C., Solomyak, B.: “Finite Beta Expansions.” Ergod. Th. and Dynam. Sys., Vol. 12 (1992), p. 713–723. [4] Hollander, M.: “Linear Numeration Systems, Finite Beta-Expansions, and Discrete Spectrum of Substitution Dynamical Systems.” PhD thesis, Washington Univer- sity, 1996. 26 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 5/2005 Czech Technical University in Prague [5] Akiyama, S.: “Pisot Numbers and Greedy Algorithm.” In: Number Theory (Eger, 1996). Berlin: de Gruyter, 1998, p. 9–21. [6] Ambrož, P., Frougny, C., Masáková, Z., Pelantová, E.: “Arithmetics on Number Systems with Irrational Bases.” Bull. Belg. Math. Soc. Simon Stevin, Vol. 10 (2003), p. 641–659. [7] Akiyama, S.: “Cubic Pisot Units with Finite Beta Expan- sions.” In: Algebraic number theory and Diphantine analysis (Graz, 1998). Berlin: de Gruyter, 2000, p. 11–26. [8] Ambrož, P., Masáková, Z., Pelantová, E.: “Addition and Multiplication of Beta-Integers in Generalized Tribo- nacci Base.” To appear in J. Autom. Lang. Comb. [9] Bernat, J.: Computation of for Pisot Numbers. Preprint, 2004. [10] Guimond, L. -S., Masáková, Z., Pelantová, E.: “Arith- metics on Beta-Expansions.” Acta Arith, Vol. 112 (2004), p. 23–40. [11] Messaoudi, A.: “Généralization de la multiplication de Fibonacci.” Math. Slovaca, Vol. 50 (2000), p. 135–148. [12] Messaoudi, A.: “Fronti re du fractal de Rauzy et syst me de numeration complexe.” Acta Arith., Vol. 95 (2000), p. 195–224. [13] Knuth, D. E.: “Fibonacci Multiplication.” Appl. Math. Lett., Vol. 1 (1988), p. 57–60. [14] Burdík, Č., Frougny, C., Gazeau, J. -P., Krejcar, R.: “Beta-Integers as Natural Counting System for Quasi- crystals.” J. Phys. A, Vol. 31 (1998), p. 6449–6472. [15] Messaoudi, A.: “Tribonacci Multiplication.” Appl. Math. Lett., Vol. 15 (2002), p. 981–985. [16] Ambrož, P.: “On the Tau-Adic Expansions of Real Num- bers.” In: ‘Words 2005, 5th International Conference on Words, actes’, S. Brlek and C. Reutenauer, (eds.). Publi- cations du LaCIM Vol. 36 (2005), p. 79–89. [17] Ambrož, P.: Addition of Eventually Periodic Tau-Adic Ex- pansions. Preprint, 2005. [18] Ambrož, P.: Addition in Pisot Numeration Systems. Preprint, 2004. Ing. Petr Ambrož phone: +420 224 358 564 email: ampy@linux.fjfi.cvut.cz Department of Mathematics Czech Technical University in Prague Faculty of Nuclear Science and Physical Engineering Trojanova 13 120 00 Praha 2, Czech Republic © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 27 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 5/2005