Benoît RITTAUD ~Associate professor (USA) ~Lecturer senior (UK) Université Paris-13, Sorbonne Paris Cité Laboratoire Analyse, Géométrie et applications (CNRS, UMR 7539) |
 |
|
    |
 Homepage |
 Contact |
 Français |
Pure mathematics
Circular words: presentation, publications
Random Fibonacci sequences: presentation, publications
Continued fractions: presentation, publications
Ergodic theory and uniform distribution modulo 1: presentation, publications
List of publications by subject
PhD and accreditation to supervise research
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:
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).
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)
PhD, accreditation to supervise research
To display mathematics formulas and symbols, this web page uses ASCIIMathML.js.
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.
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).Random Fibonacci sequences (presentation)
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
É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.Continued fractions (presentation)
É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
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.Ergodic theory and uniform distribution modulo 1 (presentation)
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.
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.