GROUPE d'ETUDE sur la NUMERATION CIRM, 23-25 juin 2003 Programme Lundi 23 juin 09.00 - 10.00 Luca Zamboni On the Fibonacci Numeration System 10.00 - 11.00 Petr Ambroz Arithmetics on number systems with irrational bases 11.00 - 11.30 Pause 11.30 - 12.30 Pierre Liardet Dynamical and harmonical structures of (t,s)-sequences 14.30 - 15.30 Anne Bertrand Traces of algebraic integers and dynamical systems 15.30 - 16.00 Pause 16.00 - 17.00 Christiane Frougny On multiplicatively dependent linear numeration systems, and periodic points Mardi 24 juin 09.00 - 09.30 Yann Bugeaud Sturmian continued fractions and Diophantine approximation 09.30 - 10.30 Michel Rigo Odometer on a regular language 10.30 - 11.00 Pause 11.00 - 12.00 Wolfgang Steiner Generalised beta expansions and ultimately periodic representations 12.00 - 12.30 Jean-Louis Verger-Gaugry Rauzy fractals in adele spaces over beta-integers 14.30 - 15.30 Anne Siegel Periodic beta-expansions with a non-unit Pisot basis 15.30 - 16.00 Pause 16.00 - 17.00 Zhi-Ying Wen Homogeneous Moran Sets, Recurrent Moran Sets and Structure of the Spectrum of One-Dimensional Schrodinger Operator with Sturmian Potentials 17.00 - 18.00 Avi Elkharrat Beta-integers' Voronoi cells Mercredi 25 juin 09.00 - 10.00 Shigeki Akiyama Shift radix system and its applications 10.00 - 11.00 Joerg Thuswaldner Number Systems and Tilings of the Plane 11.00 - 11.30 Pause 11.30 - 12.30 Hui Rao On one-dimensional self-similar tilings and pq-tiles 14.30 - 15.30 Edmund Harriss Substitution tilings of the Ammann-Beenker type 15.30 - 16.00 Pause 16.00 - 17.00 Peter Grabner Numeration systems related to fast multiplication in cryptography -------------------------------------------------------------------- Abstracts Petr Ambroz Arithmetics on number systems with irrational bases (joint work with Ch. Frougny, Z. Masakova, E. Pelantova) For irrational $\beta>1$ we consider the set ${\rm Fin}(\beta)$ of real numbers for which $|x|$ has a finite number of non-zero digits in its expansion in base $\beta$. In particular, we consider the set of $\beta$-integers, i.e. numbers whose $\beta$-expansion is of the form $\sum_{i=0}^nx_i\beta^i$. We discuss some necessary and some sufficient conditions for ${\rm Fin(\beta)}$ to be a ring. We also describe methods to estimate the number of fractional digits that appear by addition or multiplication of $\beta$-integers. We apply these methods among others to $\beta$ solution of $x^3=x^2+x+1$, the so-called Tribonacci number. In this case we show that multiplication of arbitrary $\beta$-integers has a fractional part of length at most 5. We show an example of a $\beta$-integer $x$ such that $x\cdot x$ has the fractional part of length $4$. By that we improve the bound provided by Messaoudi from value 9 to 5; in the same time we refute the conjecture of Arnoux that 3 is the maximal number of fractional digits appearing in Tribonacci multiplication. ----------------------------------------------------------------- Luca Zamboni On the Fibonacci Numeration System For each positive integer $n$ we consider the number of distinct ways of representing $n$ in the Fibonacci base. We denote this quantity by $R(n).$ The sequence $R(n)$ was recently studied by J. Berstel who gave an explicit formula to compute $R(n)$ from the Zeckendorff representation of $n$ denoted $z(n).$ In this talk we describe a related combinatorial algorithm for constructing the sequence $R(n).$ Also, for each positive integer $m$ we consider the set $G(m)$ of all positive integers $n$ such that $R(n)=m$ and $z(n)$ does not end in a prefix of the periodic sequence $10101010....$ We show that for each $m$ the set $G(m)$ is finite and we give a formula to compute it's cardinality. For instance in case $m$ is a prime number, we show $|G(m)|=2(m-1).$ --------------------------------------------------------------------- Joerg Thuswaldner Number Systems and Tilings of the Plane In my talk I want to study self affine tiles which are related to number systems defined in the two dimensional real vector space. Mainly, I will concentrate on topological properties of these tiles. It turns out that some of them have a rather easy topological structure: in fact they are homeomorphic to a closed disc. Others are of a more difficult structure. In this case we give some results on their fundamental group. -------------------------------------------------------------------- Wolfgang Steiner Generalised beta expansions and ultimately periodic representations (joint work with Michel Rigo) We study representations of real numbers in number systems coming from automata, which where introduced by P. Lecomte and M. Rigo. These number systems include those beta expansions where the expansion of one in base $\beta$ is ultimately periodic. In general, the dominant eigenvalue $\beta$ of the automaton plays an important role. We show that the set of real numbers having an ultimately periodic representation in these numbers systems is just $\mathbb Q(\beta)$ if $\beta$ is a Pisot number. If $\beta$ is neither a Pisot number nor a Salem number, then some elements of $\mathbb Q(\beta)$ have (unique) aperiodic expansions. This is a generalisation of a theorem of A. Bertrand and K. Schmidt. --------------------------------------------------------------------------- Michel Rigo Odometer on a regular language (joint work with Valerie Berthe) Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequence of integers. We generalize this notion to systems defined on an arbitrary infinite regular language. In this latter situation, if (A,<) is a totally ordered alphabet then enumerating the words of a regular language L over A with respect to the induced genealogical ordering gives a one-to-one correspondence between N and L. In this general setting, the odometer is not defined on a set of sequences of digits but on a set of pairs of sequences where the first (resp. the second) component of the pair is an infinite word over A (resp. an infinite sequence of states of the minimal automaton accepting L). We study some properties of this function like continuity, injectivity, surjectivity,... In particular, we show the equivalence of this new function with the classical odometer built upon a sequence of integers whenever the set of greedy representations of all the integers is a regular language. -------------------------------------------------------------------------- Yann Bugeaud Sturmian continued fractions and Diophantine approximation Let $\alpha \in (0, 1)$ be an irrational real number with continued fraction expansion $\alpha = [0; a_1, a_2, \ldots]$. Let $(X_n)_{n \ge -1}$ be the sequence of words on $\{1, 2\}$ defined by $X_{-1} = 2$, $X_0 = 1$, $X_1 = 1^{a_1 - 1} 2$, and, for $n \ge 2$, $X_n = X_{n-1}^{a_n} X_{n-2}$. Denote by $x_j$ the $j$-th `letter' of the infinite word $X_{\infty} = \lim_{n \to \infty} X_n$ and set $\xi = [0; x_1, x_2, \ldots...]$. We give very precise results on the approximation of $\xi$ by quadratic real numbers. This is a joint work with Michel Laurent, which extends earlier work of Damien Roy, who treated the case when $\alpha$ is the Golden Ratio. ------------------------------------------------------------------------ Shigeki Akiyama Shift radix system and its applications We introduce a new type of dynamics on \mathbb{Z}^d, which can be viewed in several ways, such as generalized linear recurrence, generalized beta expansion and a certain `limit' of canonical number systems. The fractal figure created by this dynamics will give a geometrical answer to several open questions on number systems at a time. (Joint work with H. Brunotte, J. Thuswaldner, A. Pethoe and T. Borbery) -------------------------------------------------------------------------- Zhi-Ying Wen Homogeneous Moran Set, Recurrent Moran Sets and Structure of the Spectrum of One-Dimensional Schr\"odinger Operator with Sturmian Potentials The first part of this talk, we will talk about Homogenous Moran sets and Recurrent Moran sets which generalize the self-similar sets by some nontrivial ways, by studying their dimension properties, we will develop some techniques for estimating the dimensions. Then we will show some examples. The second part of this talk, as the application of the first part, we will study the structure of the spectrum of a kind of one-dimensional Schr\"odinger operators with Sturmian potentials. Let $\beta\in(0,1)$ be an irrational, and $[a_1,a_2,\cdots]$ be the continued fraction expansion of $\beta$. Let $H_\beta$ be the one-dimensional Schr\"odinger operator with Sturmian potentials. We show that if the potential strength $V>20$, then the Hausdorff dimension of the spectrum $\sigma(H_\beta)$ is strictly great than zero for any irrational $\beta$, and is strictly less than $1$ if and only if $\liminf\limits_{k\rightarrow\infty}(a_1 a_2 \cdots a_k)^{1/k}<\infty$. ----------------------------------------------------------------------------- Hui Rao On one-dimensional self-similar tilings and $pq$-tiles Let $b\geq 2$ be an integer base, ${\cal D}=\{0,d_1,\dots, d_{b-1}\}\subset {\mathbb Z}$ a digit set and $T=T(b,{\cal D})$ the set of radix expansions. It is well known that if $T$ has nonvoid interior, then $T$ can tile ${\mathbb R}$ with some translation set ${\cal J}$ ($T$ is called a tile and ${\cal D}$ a tile digit set). There are two fundamental questions studied in the literature: (i) describe the structure of ${\cal J}$; (ii) for a given $b$, characterize ${\cal D}$ so that $T$ is a tile. We show that for a given pair $(b,{\cal D})$ , there is a unique self-replicating translation set ${\cal J}\subset {\mathbb Z}$, and it has period $b^m$ for some positive integer $m$. This completes some earlier work of Kenyon. Our main result for (ii) is to characterize the tile digit sets for $b=pq$ when $p,q$ are distinct primes. The only other known characterization is for $b=p^l$, due to Lagarias and Wang. The proof for the $pq$ case depends on the techniques of Kenyon and De Bruijn on the cyclotomic polynomials, and also on an extension of the product-form digit set of Odlyzko. ---------------------------------------------------------------------------- Christiane Frougny On multiplicatively dependent linear numeration systems, and periodic points Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers $\beta$ and $\gamma$ respectively, such that $\beta$ and $\gamma$ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number. -------------------------------------------------------------------------- Anne Bertrand Traces of algebraic integers and dynamical systems We study the number of periodic points in symbolic dynamical systems. We prove the following formula, who concerns square matrices with entries in $\Z$ $$\sum{d|n}\mu(d) Tr A^{n/d} \equiv 0 \mod n$$ Here $\mu(d)$ is the Mobius function. We ask some questions about the sequence $(TrA^n)$. We also give a language-theoretic proof of a result from Boyle and Handelman. ------------------------------------------------------------------------------ Jean-Louis Verger-Gaugry Rauzy fractals in adele spaces over beta-integers We review classical constructions of adele spaces over Q(beta) where beta is the dominant root of the incidence matrix of a substitution dynamical system over a finite number of letters (beta is assumed to be a Perron number). The objective of the present work consists in specifying the geometrical (and canonical) adelic context called by the simultaneous existence of the Euclidean Rauzy fractal, the p-adic one and the set of beta-integers (Arnoux, Berthe, Siegel). We deduce a spectral theorem associated to the dynamics. Some open questions are raised. ---------------------------------------------------------- Anne Siegel Periodic beta-expansions with a non-unit Pisot basis It is well-known that real numbers with a purely periodic decimal expansion are the rationals having a denominator coprime with 10. We are interested in beta-expansions with a non-unit Pisot basis. We give a characterization of real numbers having a purely periodic expansion in such a basis. The characterization is given in terms of an explicit self-similar compact subset of non-zero measure in a product of a Euclidean space and p-adic spaces. ------------------------------------------------------------------------------ Avi Elkharrat Beta-integers' Voronoi cells We characterize nodes of a class of one-dimensional aperiodic sets called beta-integers, with $\beta$ a quadratic Pisot-Vijayaraghavan unit, by their Voronoi cells. The set of beta-integers resort to the fields of Number Theory and Numeration Systems, more precisely, they are in the frame of beta-expansions and beta-shifts. Presently we show that there is a relation between the Voronoi cell of a beta-integer and its beta-expansion, we classify beta-integers consequently, and give their arithmetic properties. This work could have interesting consequences, in the theory of Quasicrystals, in the characterization of atomic decorations of quasiperiodic point-sets. ------------------------------------------------------------------------------ Edmund Harriss Substitution tilings of the Ammann-Beenker type Many of the most well known non-periodic tilings on the plane can be generated by substitution rules. Some of these, for example the Penrose and Ammann tilings, can also be constructed by canonical projection. They are therefore a generalisation of the geometric structure of Sturmian tilings. In this talk we explain how the existence of substitution rules for canonical projection tilings can be identified with the existence of some hyperbolic structure, which takes the form of a hyperbolic automorphism of the lattice that commutes with the canonical projection. I will illustrate this with the one-dimensional sturmian sequences and the 2-dimensional Ammann-Beenker tiling. ------------------------------------------------------------------------------ Pierre Liardet Dynamical and harmonical structures of (t,s)-sequences (joint paper with Peter Hellekalek) The concept of $(t,s)$-sequences has given rise to various constructions of low-discrepancy sequences in the $s$-dimensional unit cube. We show that many of these sequencies are related to a basic type which arises from a general dynamical system, a skew product extension of a Kakutani adding machine. From this relation, we deduce some new properties. In particular, we study certain spectral properties of these sequencies that allow to characterize those $s$-dimensional boxes with bounded remainder. This solves an open problem in the theory of irregularities of distribution of such sequencies. ----------------------------------------------------------------------------- Peter Grabner Numeration systems related to fast multiplication in cryptography Numeration systems related to fast multiplication in cryptography We discuss an optimal method for the computation of linear combinations of elements of Abelian groups, which uses signed digit expansions. This has applications in elliptic curve cryptography. We compute the expected number of operations asymptotically (including a periodically oscillating second order term) and prove a central limit theorem. Apart from the usual right-to-left (i.e., least significant digit first) approach we also discuss a left-to-right computation of the expansions. This exhibits fractal structures that are studied in some detail.