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.