Circular words
(publications)
A
(dotted) circular word on a given
alphabet is a finite word whose $\ell$ letters are indexed by
$\mathbb{Z}/\ell\mathbb{Z}$ (instead of $\{0,\ldots, \ell-1\}$
as in a standard finite word). We denote it by
$\widetilde{W}=\widetilde{w_0\ldots w_{\ell-1}}$ to avoid
confusion with the standard finite word $W=w_0\ldots
w_{\ell-1}$. Apparently, this notion has be introduced first in
a paper with
Laurent
Vivier (LDAR, université Paris-Diderot), originally to
study a generalization of $p$-adic numbers to numeration systems
differents from the base $p$ numeration system (as well as for
questions on substitutive dynamics).
Apart from applications in
mathematics education,
the algebraic structure of circular words on $\{0,\ldots b-1\}$
(where $b$ is an integer) is not very interesting : it is simply
the additive group $\mathbb{Z}/(b^\ell-1)\mathbb{Z}$. Things
become more interesting in a more general combinatorial
framework. For example, let us identify circular words with the
Fibonacci rule: any factor of $\widetilde{W}$ made of the
three letters $abc$ can be replaced by $(a-1)(b-1)(c+1)$ without
changing the equivalence class of the new circular word thus
obtained (of course, other rules can be imagined as well). For
example, we have $\widetilde{01100}=\widetilde{00010}$, as well
as (because of the circular structure)
$\widetilde{100001}=\widetilde{010000}$. We can then prove the
following fundamental result (up to some identifications):
the
set $G_\ell$ of classes of circular words with $\ell$ letters
is a finite abelian group than can be fully described. For
example, for $\ell=2m$, the order $c_m$ of the group is given by
the sequence A004146 of
Sloane's Encyclopedia ($1$, $5$, $16$, $45$, $121$,
$320\ldots$). More precisely, depending on the parity of $m$,
$c_m$ is either of the form $d_m^2$ or of the form $5d_m^2$, and
$G_{2m}$ is isomorphic to $(\mathbb{Z}/d_m\mathbb{Z})^2$ or
$(\mathbb{Z}/d_m\mathbb{Z})\times(\mathbb{Z}/5d_m\mathbb{Z})$.
The sequence A004146 is already known as the sequence that
provides the number of spanning trees of the $m$
-wheel
(the graph made of $m+1$ vertices $c$, $s_1$, $\ldots$,
$s_{m-1}$, where the $s_i$s defines a cycle and the vertex $c$,
the
center, is linked to eac $s_i$ by an edge), hence
providing a combinatorial interpretation of the set of classes
of admissible circular words.
Here are three applications of circular
words:
- a new proof of the well-known relation
$\gcd(F_i,F_j)=F_{\gcd(i,j)}$, where $(F_i)_i$ is the
Fibonacci sequence. The sequence $(c_m)_m$ can be easily
expressed in terms of the $F_i$s. The previous equality is
therefore an immediate consequence of the existence, for any
integer $d$, of the injective morphism of groupes
$G_\ell\longmapsto G_{d\ell}$ that send the circular word
$\widetilde{W}$ to $\widetilde{W^d}$ (where $W^d$ stands for
the concatenation of $d$ copies of $W$).
- a property of the prefixes of the Fibonacci word, that is:
the fixed point $M=abaababaabaab\ldots$ of the substitution
$\sigma$ defined on the alphabet $\{a,b\}$ by $\sigma(a)=ab$
and $\sigma(b)=a$. Properties of the group $G_\ell$ allow to
find nontrivial values $k$ and $q$ such that the word $bM$
can be written as $A_1\ldots A_qM'$, where the $q$ words
$A_1$, $\ldots$, $A_q$ are all of the same length $k$ and
all contain the same number of $a$ (and therefore also the
same number of $b$).
- the algebraic study of $F$-adic numbers, a
structure originally more studied (in a paper by Liardet,
Grabner and Tichy) in a dynamical standpoint. A $F$-adic
number is an infinite word on $\{0,1\}$ that satisfy the
Fibonacci admissibility condition, which is that the factor
$11$ does not appear in the word. Such numbers can be seen
as a generalization of $p$-adic numbers, in which the
successive powers of the positive integer $p$ ($p^0$, $p^1$,
$p^2$, $p^3$, etc.) are replaced by the terms of the
Fibonacci sequence $F_0=1$, $F_1=2$ and
$F_n=F_{n-1}+F_{n-2}$ for all $n\geq 2$. The set $F$ of
$F$-adic numbers has a natural structure of abelian group,
under the identifications $(01)^\infty=(10)^\infty$ and
$W0(01)^\infty=W10(01)^\infty$ for any finite admissible
word $W$. It is then natural to consider the rational
elements of the set $F$, that is: the $F$-adic numbers $X$
for which there exists two integers $p$ and $q$ such that
$qX=p$ (identifying $p$ to the $F$-adic number that
corresponds to the expansion of $p$ in the
Fibonacci-Zeckendorf numeration system). It can be proved
that, similarly to the case of usual numeration systems in
integer base, a $F$-adic number is rational if and only if
it is ultimately periodic. The main difference with the real
case is that the equation $qX=p$ has always exactly $q$
solutions (plus, possibly, a $(q+1)$-th one, in the
particular case where $q$ divides $p$).
Random Fibonacci sequences (publications)
In its classical form, a
random Fibonacci
sequence is a sequence defined by the induction relation
$F_n=|F_{n-1}\pm F_{n-2}|$ (or $F_{n-1}\pm F_{n-2}$), the $\pm$
sign being randomly chosen for each $n$ by the toss of a coin. A
central question is to determine whether such a sequence has a
growth rate. With the help of a result of Harry Furstenberg,
Divakar Viswanath showed that the answer is affirmative, in the
following sense: almost all random Fibonacci sequence is
exponentially increasing, with factor $v=1,1319\ldots$, i.e.,
almost surely, the sequence ${}^n\sqrt{F_n}$ converges to $v$,
this value being obtained as the integral of a rational fraction
along a measure built from Stern-Brocot intervals (that is:
intervals of $\mathbb{R}^+$ of the form $[a/b,c/d)$, where $a$,
$b$, $c$ and $d$ are integers such that $ad-bc=-1$).
Another way to study these sequences is to
build the binary tree whose root is labelled by $F_0$, its
unique child by $F_1$, and such that any node (apart from the
root) labelled $x$ and of parent $y$ has a left child labelled
$|x-y|$ and a right child labelled by $x+y$. Thus, to each walk
in this tree corresponds a random Fibonacci sequence. We denote
by $\mathbf{R}$ the subtree defined by the suppression of each
left child of a left child (here, the vertical edges stand for
right children of left children, the two first edges being
excluded).
With this tree, new
results on the growth rate of random Fibonacci sequences can
be obtained. Moreover, it has a lot of arithmetical and
combinatorial properties that are of interest for
themselves, the first of which being that the number of
edges at the row $\rho_n$ is given by the $n$-th term of the
Fibonacci sequence.
With
Thierry
de la Rue and
Élise
Janvresse (LMRS, CNRS, Université de Rouen), we made a
study of the dynamics of the system that allowed us to
simplify Viswanath's results, and to generalize them to the
case of an unbalanced coin. The main result consists in a
rewriting of Viswanath's constant $v$ on the form
$\int_0^{+\infty}\ln(x)\mbox{d}\mu(x)$, where $\mu$ is a
variant of the measure defined by Minkowski's question mark.
A natural generalization of random
Fibonacci sequences is given by the formula $F_n:=|\lambda
F_{n-1}\pm F_{n-2}|$, where $\lambda$ is a fixed parameter
(the generalization $F_n:=|\lambda F_{n-1}\pm \mu F_{n-2}|$
reduces to it with a simple change of variable). The
techniques employed for the case $\lambda=1$ can be
generalized in a very natural way when $\lambda$ is of the
form $\lambda_k:=2\cos(\pi/k)$, where $k\geq 3$ is an
integer (the first values of the sequence $(\lambda_k)_k$
are $\lambda_3=1$, $\lambda_4=\sqrt{2}$,
$\lambda_5=(1+\sqrt{5})/2$ and $\lambda_6=\sqrt{3}$). In
particular, there exists an equivalent of the tree
$\mathbf{R}$ for each $\lambda_k$, whose combinatorial
structure is the following: it is the biggest binary tree
that does not contain a $(k-1)$-th left child (a $i$-th left
child being the left child of a $(i-1)$-th left child, a
$0$-th left child being a right child).
All the results obtained for standard
random Fibonacci sequences (i.e. with $\lambda=1$) can be
generalized to these new cases. The latters correspond, in
hyperbolic geometry, to
Hecke groups, which are the
only ones for which the transformation group of the
hyperbolic half upper-plane $\mathbb{H}$ generated by
$z\longmapsto -1/z$ and $z\longmapsto z+\lambda$ is
discrete.
In number theory, the first interest of
the tree $\mathbf{R}$ is that it is an algorithm of
continued fraction expansion of rational numbers. The
function that send to each edge $(a,b)$ of $\mathbf{R}$ the
rational number $a/b$ is bijective, and the walk in the tree
from the root to this edge is a codage of the continued
fraction expansion of $a/b$. This algorithm is fundamentally
different from the classical algorithms, since to the
beginning
of the walk corresponds the
end of the continued
fraction expansion.
This property remains true for the
equivalent of $\mathbf{R}$ for $\lambda_k$-random Fibonacci
sequences. Writing $\lambda$ instead of $\lambda_k$, the
algorithm provided by the tree corresponds to a $\lambda$
-continued
fraction expansion, of the form
$$a_0\lambda+\frac{1}{\displaystyle
a_1\lambda+{\frac{1}{a_2\lambda+\cdots}}},$$
where the $a_i$s are integers (such an expression is a
Rosen
continued fraction expansion).
To generalize to other values of
$\lambda$ our results on random Fibonacci sequences, it is
probable that a deeper study of $\lambda$-continued
fractions is required, especially in their combinatorial
aspects. Such a study is the subject of an article that
investigates the properties of the function that joins
$\lambda$-continued fractions and $\beta$-shifts. This work,
which has an intereste of its own, is a first step for a
more general study of random Fibonacci sequences.
Continued fractions (publications)
A summary of my work on this subject will be soon available in
English. In the meantime, you may read the
French
version.
Ergodic theory and uniform distribution modulo 1
(publications)
A summary of my work on this subject will be soon available in
English. In the meantime, you may read the
French
version.
List of publication by subjects
(see here the full list of my publications)
Circular words (presentation)
Benoît Rittaud, "Numeration systems for circular
words and applications to arithmetics" (soumis).
Benoît Rittaud & Laurent Vivier, "The field $\mathbb{Q}$
from the standpoint of circular words and history" (soumis).
Benoît Rittaud, "Structure of Classes of Circular Words
defined by a Quadratic Equivalence", RIMS Kôkyûroku
Bessatsu (à paraître).
Benoît Rittaud & Laurent Vivier, "Does Numerology Allow a
group to have Two Identity Elements?", The American
Mathematical Monthly 119 n°4 (2012), 439.
Benoît Rittaud & Laurent Vivier, "Circular words and three
applications: factors of the Fibonacci word, $F$-adic numbers,
and the sequence 1, 5, 16, 45, 121, 320, $\ldots$, Functiones
et Approximatio 47 n°2 (2012), 207-231.
Benoît Rittaud & Laurent Vivier, "Circular words and
applications", Proceedings 8th International Conference
Words 2011, Prague, 31-36. Read the article
Random Fibonacci sequences (presentation)
Élise Janvresse, Benoît Rittaud & Thierry de la
Rue, "Dynamics of $\lambda$-continued fractions and
$\beta$-shifts", Discrete and Continuous Dynamical Systems
- Series A 33 n°4 (2013), 1477-1498.
Élise Janvresse, Benoît Rittaud & Thierry de la Rue,
"Almost-sure growth rate of generalized random Fibonacci
sequences", Annales de l'Institut Henri Poincaré -
Probabilités et Statistiques 46 n°1 (2010),
135-158.
Élise Janvresse, Benoît Rittaud & Thierry de la Rue,
"Growth rate for the expected value of a generalized random
Fibonacci sequence", Journal of Physics A 42
n°8 (2009), 085005.
Élise Janvresse, Benoît Rittaud & Thierry de la Rue, "How
do random Fibonacci sequences grow?", Probability Theory
and Related Fields 142 n°3-4 (2008), 619-648.
Benoît Rittaud, "On the average growth of random Fibonacci
sequences", Journal of Integer Sequences 10
(2007), Article 07.2.4. Read
the article
Continued fractions (presentation)
Benoît Rittaud, "Medietic numeration systems and
combinatorics of Rosen continued fractions", en préparation
pour le second volume de CANT: Combinatorics, Automata and
Number Theory.
Benoît Rittaud, "On subsequences of convergents to a quadratic
irrational given by some numerical schemes", Journal de
Théorie des Nombres de Bordeaux 22 n°2
(2010), 449-474.
Ryuji Abe & Benoît Rittaud, "Combinatorics on Words of
Markoff's Spectrum for $\mathbb{Q}$ (soumis).
Ryuji Abe & Benoît Rittaud, "Combinatorics on Words of
Markoff's Spectrum for $\mathbb{Q}(\mbox{i})$" (soumis).
Ryuji Abe & Benoît Rittaud, "Quasi-palindromy of elements
of $\mbox{PSL}(2, \mathbb{Z})$ associated to the Markoff
spectrum, WORDS 2007, Proceedings of the 6th International
Conference on Words (Pierre Arnoux, Nicolas Bédaride &
Julien Casseigne éds.), 7-17.
Ergodic theory and uniform distribution modulo 1 (presentation)
Benoît Rittaud, "A Koksma's inequality in $O(1/n)$
and a consequence for the mixing property of special flows", (soumis).
Benoît Rittaud, "Équidistribution presque partout modulo 1 de
suites oscillantes perturbées - III - Cas liouvillien
multidimensionnel", Journal of Number Theory 122
n°2 (2007), 261-282.
Benoît Rittaud, "Équidistribution presque partout modulo 1 de
suites oscillantes perturbées - II - Cas liouvillien
unidimensionnel", Colloquium Mathematicum 96
n°1 (2003), 55-73.
Emmanuel Lesigne, Benoît Rittaud & Thierry de la Rue,
"Weak disjointness of measure-preserving dynamical systems", Ergodic
Theory and Dynamical Systems 23 n°4 (2003),
1173-1198.
Benoît Rittaud, "Équidistribution presque partout modulo 1 de
suites oscillantes perturbées", Bulletin de la
Société Mathématique de France 128 n°3 (2000),
451-471.
Benoît Rittaud, "Équidistribution presque partout modulo $1$
de suites oscillantes", Comptes Rendus de l'Académie des
Sciences Paris Série I - Mathématiques 327
n°4 (1998), 339-342.
PhD, accreditation to supervise research
Text of my thesis defended in January 1999 (dir. Emmanuel
Lesigne, LMPT, CNRS, Université de Tours).
Text of my accreditation to supervise research defended in
December 2008 at Université Paris-13.
To display mathematics formulas and
symbols, this web page uses ASCIIMathML.js.