Lorentz Center - Numeration from 7 Jun 2010 through 18 Jun 2010
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    from 7 Jun 2010 through 18 Jun 2010





1st week



Tutorial talks


Boris Adamczewski

“Automata in Number Theory”


Among infinite sequences or infinite sets of integers, some have a rigid structure, such as periodic sequences or arithmetic progressions, whereas others, such as random sequences or random sets, are totally unordered and could not be described in a simple way. Finite automata are one of the most basic model of computation and thus take place at the bottom of the hierarchy associated with Turing machines. Such machines can naturally be used at once to generate sequences with values over a finite set, and as a device to recognize some sets of integers. One of the main interest of these automatic sequences/sets comes from the fact that they are highly ordered without necessarily being trivial. One can thus consider that they lie somewhere between order and chaos, even if, in most respects, they appear to have a rigid structure. In these lectures, I will survey some of the connections between automatic sequences/sets and number theory. Several substantial advances have recently been made in this area and I will try to give an overview of some of these new results.  This will possibly includes discussions about prime numbers, the decimal expansion of algebraic numbers, the search for an analogue of the Skolem-Mahler-Lech theorem in positive characteristic and the study of some Diophantine equations that generalize the famous $S$-unit equations over fields of positive characteristic.






Vilmos Komornik

“Expansions in noninteger bases”


Abstract. Expansions in noninteger bases often appear in number theory and probability theory, and they are closely connected to ergodic theory, measure theory and topology. Seemingly innocent questions lead to surprisingly deep problems many of which are still open. Starting with a discussion of Renyi's greedy or beta-expansions, we give an overview of various results concerning the number of expansions of some given real number in a given base. Most of the early results in this field are due to P. Erd\H os and his collaborators. Next we concentrate ourselves to the case of unique expansions and we clarify the rich combinatorial, topological and fractal nature of the set of such bases and real numbers. Finally, we study the existence of so-called universal expansions and their relationship to problems of Diophantine approximation.






Mark Pollicott

“Dynamical Zeta Functions Revisited”


Dynamical zeta functions are complex functions which are used, amongst other things,  to  asymptotically count  dynamical quantities  for either discrete maps or flows (e.g., closed orbits).  The basic philosophy is that  the more you know about the domain of zeta function the more you know about the properties of the dynamical system.


i) Extending the Domain of zeta functions: In these lectures we will describe different approaches to extending zeta functions, culminating  in recent progress on extending Ruelle zeta functions for Anosov diffeomorphisms and flows using operator theoretic methods, and their applications.


ii) Special Values of zeta functions:  Once a zeta function (or the closely related L-function) has an extension to a larger domain it is a natural question to ask what is the significance of the locations of the zeros, the poles and their residues, and the value of the function at specific values.  Frequently, these provide interesting global information about the system.  We will describe a number of results of this type.


iii)  Dynamical zeta functions and counting:   One of the historical motivations for studying (dynamical) zeta functions was to obtain asymptotic estimates, particularly on the number of closed orbits.  We will describe both classical results and recent results.


Throughout we will motivate the work by drawing analogies with classical results in number theory.



Short talks


Emilie Charlier

“Representing real numbers in a generalized numeration system”

Click here for abstract






2nd week


Shigeki Akiyama

"What is Pisot conjecture?"


In this talk, I wish to give a rathor personal account on Pisot conjecture of substitutive dynamical systems. This conjecture contains many interesting aspects: ergodic, analytic, combinatorial and number theoretical nature. Moreover it can also be understood as a problem of numeration on Pisot number base, which is called Dumont-Thomas number system. In the end, I wish to talk on a possible generalization in higher dimension.




Pierre Arnoux

“Around The Rauzy Fractal”


Gérard Rauzy past away last May. In this lecture, I will give a short history of his work on substitutions, explaining some of his motivations for this research, and show recent developments of the theory.




Valerie Berthe

“Multidimensional Euclid's algorithms, numeration and substitutions”


Substitutions  are among the most    basic objects  in  symbolic dynamics: a substitution is a  morphism of the free monoid that allows  to replace letters by words. Substitutions allow to construct  under some  algebraic conditions  (Pisot case, see also S. Akiyama's talk) intriguing tilings whose tiles have a fractal boundary, and which have  numerous  applications in  Diophantine approximation, in  the  ergodic study of toral utomorphisms and in  beta-numeration.This lecture aims at  extending such constructions to a more general framework where non-algebraic parameters can also be considered. The idea  is to  work   with  suitable multidimensional versions of Euclid's algorithm and with multidimensional continued fractions.






Christiane Frougny

"Representation of p-adic numbers in rational base numeration systems"


Representation of p-adic numbers in base p by left-infinite sequences of digits in A_p={0,1,...,p-1} is classical.

In this talk we consider numeration systems with basis of the form 1/q(p/q)^i, i >=0, and digit-set A_p, introduced by Akiyama, Frougny and Sakarovitch (2008).

We show that any p-adic number is representable in that system. We discuss unicity, finiteness and eventual periodicity of these representations.

We also consider some variants of this system. Joint work with Karel Klouda.






Peter Grabner

“Distribution properties of digital functions over the Gaussian integers”


We present threeconceptually different methods to prove distribution results for block additivefunctions with respect to radix expansions of the Gaussian integers. Based on generating function approaches we obtain a central limit theorem and asymptotic expansions for the moments. Furthermore, these generating functions as well as ergodic skew products are used to prove uniform distribution in residue classes and modulo $1$.

Joint work with M. Drmota (TU Vienna) and P. Liardet (Marseille).






Ted Janssen

“Structural Phase Transitions in Aperiodic Crystals”


Phase transitions in physical systems may be analysed in the framework of the Landau theory, in which representations of the relevant symmetry groups play an important role. Such phase transitions may occur, and have been observed, in aperiodic crystals as well. The question about the relevant symmetry groups rises.

An analysis of the possible structural phase transitions in aperiodic crystals will be given, and of the special character of phase transitions in these systems. In particular, transitions in aperiodic tilings, as models for aperiodic crystals, will be considered.






Jan Willem Klop

“Defining and comparing infinite streams”


We discuss joint work with Clemens Grabmayer (UU),  Joerg Endrullis (VU) and Dimitri Hendriks (VU), concerning two topics  in infinite sequences (or streams).

The first topic is how to define streams in a uniform framework, that we call Pure Stream Format (PSF). Specifically we concentrate on proving well-definedness of such specifications - an issue know in computer science as productivity. We single out a restricted class of specifications, still expressive enough to encompass automatic streams, morphic streams, and more. For specifications in this restricted format  we can automatically decide productivity. The second topic is concerned with an attempted classification of infinite streams, by means of finite state transducers (FSTs), leading to a notion of 'degree of stream' that is analogous to the well-known Turing degrees of unsolvability in mathematical logic. (In fact FSTs correspond to context expressions in PSF.) We mention initial results in the form of some elementary properties of this partial order of stream degrees, concluding with our favourite conjecture about  the degree of the Thue-Morse sequence.

Jan Willem Klop, Section Theoretical Computer Science, VU University Amsterdam






Bernard Nienhuis

“Counting probabilities”


Loop models are ensembles of paths over the edges of a lattice which are either closed or terminate on the boundary.  The total ensemble of paths induces an ensemble of matchings between the two terminals of the same path. In 2001 Razumov and Stroganov proposed a remarkable conjecture between two loop models, one on a half infinite cylinder and another on a finite square grid.  It links the properties of a probablistic and a combinatoric model.  This year saw the proof of this conjecture by Cantini and Sprotiello. In this lecture I present the Razumov-Stroganov conjecture and some of its generalizations.  A number of results in the form of exact correlation functions will be illustrated.






Michel Rigo

“State complexity of testing divisibility and structural properties of numeration languages”


The aim of this talk is twofold. We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. Then, under some mild assumptions, we study the state complexity of the minimal automaton accepting the greedy representations of the

multiples of m for a wide class of linear numeration systems. As an example, the number of states of the minimal automaton accepting the greedy representations of mN in the Fibonacci system is 2m2.

Joint work with E. Charlier, N. Rampersad, L. Waxweiler






Robbie Robinson

f-expansions and entropy”


The idea of f-expansions as generalizations of continued fractions and radix representations has a long history, going back at least to Kakeya (1924). The connection to ergodic theory and dynamics was brought out by Renyi (1957) and Parry (1964).  In the best-known cases, the corresponding dynamical system is non-invertible and has positive entropy. In this talk, we start by discussing the general case of f-expansions. Then we study some entropy-zero examples and their properties. In particular, we discuss Sturmian sequences as numerations.





Klaus Schmidt

“Symbolic representations of toral automorphisms


By using an idea which originally goes back to Vershik one can construct nice symbolic covers of hyperbolic toral automorphisms. For quasihyperbolic (i.e., ergodic, but nonhyperbolic) automorphisms the costruction of symbolic representations is much more mysterious and raises a number of interesting and challenging problems.






Thomas Schmidt

“Natural extensions and entropy of alpha-continued fractions”


We give natural extensions for H. Nakada's alpha-continued fractions. The alpha-continued fractions are a family of interval maps, indexed by alpha in [0,1].  With the natural extensions,  one determines  maximal intervals of alpha  upon which the entropy of the maps is constant (similarly for decreasing, and  increasing).

The dynamics of the situation lends itself to pictures, and I hope to illustrate some of the richness of the deformation through the family of the natural extensions. This is joint work with Cor Kraaikamp and Wolfgang Steiner.






Anne Siegel

"Numeration, redundancy graphs and topological properties of fractals"


Since Thurston, beta numeration are proved to be very related to "nice" compact sets with fractal boundaries,  called central tiles or Rauzy fractals. A beta-tile can be seen as a compact representation of integers in base beta, since they correspond to those reals numbers whose beta expansion contains no negative power of beta.  The shape of the fractals obtained with this process is quite puzzling : connectivity, disk-likeness, or the place of zero in the tile are far from being invariant. In this talk, we will explain why redundancy graphs may allow us to set up topological properties of tiles. Then we will illustrate how such topological properties may be used to provide new insights on properties of beta-expansions.




Victor Sirvent

“Symmetries in  k-bonacci adic systems”


In this talk we explore the symmetries of the $k$-bonacci adic systems and their geometrical realizations konwn as Rauzy fractals. We consider the maximal  invariant subset  under the involution in $\{0,1\}^{\N}$ that exchanges $0$ with $1$.

We explore the dynamical properties of the induced dynamical system on this set and their geometrical realizations as subsets of Rauzy fractals.






Boris Solomyak

“Invariant measures for non-minimal tiling substitutions”


We consider self-affine tiling substitutions in Euclidean space and the corresponding tiling dynamical systems. It is well-known that in the primitive case the dynamical system is uniquely ergodic. We investigate invariant measures when the substitution is not primitive, and the tiling dynamical system is non-minimal. We prove that if there are no periodic points, then all ergodic invariant probability measures are supported on minimal components, and obtain results of the same nature for a class of tiling dynamical systems with periodic points. Examples include the ``integer Sierpi\'nski gasket and carpet'' tilings. For such tilings the only invariant probability measure is supported on trivial periodic tilings, but there is a unique (up to constant multiple) fully supported locally finite measure, which is sigma-finite.

This is a joint work with Maria Isabel Cortez.






Wolfgang Steiner

“Natural extensions of beta-expansions and continued fractions”


For any base beta > 1, the beta-expansion of a number x in [0,1) is given by the beta-transformation T(x) = beta x mod 1. A natural extension of this transformation, i.e., an invertible transformation which admits T as a factor, was given by Dajani, Kraaikamp and Solomyak (1996). However, their natural extension does not take into account certain algebraic properties of numbers. When beta is a Pisot unit, then one can define a natural extension using the algebraic conjugates of beta and the two-sided extension of the symbolic dynamical system given by the beta-expansions, see e.g. a recent joint work with Kalle. Using this natural extension, Ito and Rao (2005) characterized the numbers with purely periodic beta-expansion.

The continued fraction expansion of a number x in [0,1) is given by the Gauss map T(x) = 1/x mod 1. Here, a natural extension can be defined by inverting the map on the second coordinate. A generalization to alpha-continued fractions was given by Nakada (1981), a generalization to Rosen continued fractions by Burton, Kraaikamp and Schmidt (1999), and to alpha-Rosen continued fractions in a joint work with Dajani and Kraaikamp (2009). New results on alpha-continued fractions are presented in Tom Schmidt's talk.

The aim of this talk is to exhibit similarities and differences in the construction of natural extensions for these two kinds of transformations. E.g., in both cases, the orbits of the endpoints of the fundamental interval play an important role.




Vincent van Oostrom

Infinitary Term Rewriting”


Term rewriting constitutes a universal model of computation. Research in term rewriting focusses on developing methods for establishing properties of reductions (computations) by establishing properties of their individual (computation) steps.

Computations can be both finite, e.g. computing the value of 3+4, and infinite, e.g. computing the infinite list of prime numbers. In this talk we focus on infinite computations within term rewriting, how to express them, how to express results, how to implement them, and techniques to establish properties for them.