Center for Scientific Workshops in All Disciplines

Current Workshop | Overview | Back | Home | Search | | ||||||||||

## Numeration |

“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. ---
“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. ---
“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.
“Representing real numbers in a
generalized numeration system” --
"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. ---
“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. --
“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. ---
"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. ---
“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). ---
“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. ---
“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 ---
“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. ---
“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 2m Joint work with E. Charlier, N. Rampersad, L. Waxweiler ---
“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. ---
“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. ---
“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. ---
"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.
“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. ---
“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. ---
“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. ---
“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. [Back] |