BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Christophe Reutenauer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We generalize the perfectly clustering words of Simpson and Puglisi and relate them to band bricks over certain gentle algebras. This allows us to prove a generalization of a conjecture by the second author on perfectly clustering words.
The free monoid $A^*$ on a finite totally ordered alphabet $A$ acts at the left on columns, by Schensted left insertion. This defines a finite monoid, denoted $Styl(A)$ and called the stylic monoid. It is canonically a quotient of the plactic monoid. Main results are: the cardinality of $Styl(A)$ is equal to the number of partitions of a set on $|A|+1$ elements. We give a bijection with so-called $N$-tableaux, similar to Schensted's algorithm, explaining this fact. Presentation of $Styl(A)$: it is generated by $A$ subject to the plactic (Knuth) relations and the idempotent relations $a^2=a$, $a\in A$. The canonical involutive anti-automorphism on $A^*$, which reverses the order on $A$, induces an involution of $Styl(A)$, which similarly to the corresponding involution of the plactic monoid, may be computed by an evacuation-like operation (Schützenberger involution on tableaux) on so-called standard immaculate tableaux (which are in bijection with partitions). The monoid $Styl(A)$ is $J$-trivial, and the $J$-order of $Styl(A)$ is graded: the co-rank is given by the number of elements in the $N$-tableau. The monoid $Styl(A)$ is the syntactic monoid for the the function which associates to each word $w\in A^*$ the length of its longest strictly decreasing subword.
We compute the coefficients of the polynomials $C_n(q)$ defined by the equation \begin{equation*} 1 + \sum_{n\geq 1} \, \frac{C_n(q)}{q^n} \, t^n = \prod_{i\geq 1}\, \frac{(1-t^i)^2}{1-(q+q^{-1})t^i + t^{2i}} \, . \end{equation*} As an application we obtain an explicit formula for the zeta function of the Hilbert scheme of $n$ points on a two-dimensional torus and show that this zeta function satisfies a remarkable functional equation. The polynomials $C_n(q)$ are divisible by $(q-1)^2$. We also compute the coefficients of the polynomials $P_n(q) = C_n(q)/(q-1)^2$: each coefficient counts the divisors of $n$ in a certain interval; it is thus a non-negative integer. Finally we give arithmetical interpretations for the values of $C_n(q)$ and of $P_n(q)$ at $q = -1$ and at roots of unity of order $3$, $4$, $6$.
We establish an explicit formula for the number $C_n(q)$ of ideals of codimension $n$ of the algebra ${\mathbb F}_q[x,y,x^{-1}, y^{-1}]$ of Laurent polynomials in two variables over a finite field of cardinality $q$. This number is a palindromic polynomial of degree $2n$ in $q$. Moreover, $C_n(q) = (q-1)^2 P_n(q)$, where $P_n(q)$ is another palindromic polynomial; the latter is a $q$-analogue of the sum of divisors of $n$, which happens to be the number of subgroups of ${\mathbb Z}^2$ of index $n$.
We investigate the relationship between two constructions of maximal comma-free codes described respectively by Eastman and by Scholtz and the notions of Hall sets and Lazard sets introduced in connection with factorizations of free monoids and bases of free Lie algebras.
We introduce the notion of specular sets which are subsets of groups called here specular and which form a natural generalization of free groups. These sets are an abstract generalization of the natural codings of linear involutions. We prove several results concerning the subgroups generated by return words and by maximal bifix codes in these sets.
Given a set $F$ of words, one associates to each word $w$ in $F$ an undirected graph, called its extension graph, and which describes the possible extensions of $w$ on the left and on the right. We investigate the family of sets of words defined by the property of the extension graph of each word in the set to be acyclic or connected or a tree. We prove that in a uniformly recurrent tree set, the sets of first return words are bases of the free group on the alphabet. Concerning acyclic sets, we prove as a main result that a set $F$ is acyclic if and only if any bifix code included in $F$ is a basis of the subgroup that it generates.
We investigate the relation between bifix codes and interval exchange transformations. We prove that the class of natural codings of regular interval echange transformations is closed under maximal bifix decoding.
We introduce a class of sets of words which is a natural common generalization of Sturmian sets and of interval exchange sets. This class of sets consists of the uniformly recurrent tree sets, where the tree sets are defined by a condition on the possible extensions of bispecial factors. We prove that this class is closed under maximal bifix decoding. The proof uses the fact that the class is also closed under decoding with respect to return words.
We prove that the number of right ideals of codimension $n$ in the algebra of noncommutative Laurent polynomials in two variables over the finite field $\mathbb F\_q$ is equal to $(q-1)^{n+1} q^{\frac{(n+1)(n-2)}{2}}\sum\_θq^{inv(θ)}$, where the sum is over all indecomposable permutations in $S\_{n+1}$ and where $inv(θ)$stands for the number of inversions of $θ$.
We investigate the natural codings of linear involutions. We deduce from the geometric representation of linear involutions as Poincaré maps of measured foliations a suitable definition of return words which yields that the set of first return words to a given word is a symmetric basis of the free group on the underlying alphabet $A$. The set of first return words with respect to a subgroup of finite index $G$ of the free group on $A$ is also proved to be a symmetric basis of $G$.
We describe in this paper a connection between bifix codes, symbolic dynamical systems and free groups. This is in the spirit of the connection established previously for the symbolic systems corresponding to Sturmian words. We introduce a class of sets of factors of an infinite word with linear factor complexity containing Sturmian sets and regular interval exchange sets, namemly the class of tree sets. We prove as a main result that for a uniformly recurrent tree set $F$, a finite bifix code $X$ on the alphabet $A$ is $F$-maximal of $F$-degree $d$ if and only if it is the basis of a subgroup of index $d$ of the free group on $A$.
In this article, we extend the definition of Christoffel words to directed subgraphs of the hypercubic lattice in arbitrary dimension that we call Christoffel graphs. Christoffel graphs when $d=2$ correspond to well-known Christoffel words. Due to periodicity, the $d$-dimensional Christoffel graph can be embedded in a $(d-1)$-torus (a parallelogram when $d=3$). We show that Christoffel graphs have similar properties to those of Christoffel words: symmetry of their central part and conjugation with their reversal. Our main result extends Pirillo's theorem (characterization of Christoffel words which asserts that a word $amb$ is a Christoffel word if and only if it is conjugate to $bma$) in arbitrary dimension. In the generalization, the map $amb\mapsto bma$ is seen as a flip operation on graphs embedded in $\mathbb{Z}^d$ and the conjugation is a translation. We show that a fully periodic subgraph of the hypercubic lattice is a translate of its flip if and only if it is a Christoffel graph.
Following and generalizing a construction by Kontsevich, we associate a zeta function to any matrix with entries in a ring of noncommutative Laurent polynomials with integer coefficients. We show that such a zeta function is an algebraic function.
We prove in this note that, for an alphabet with three letters, the set of first return to a given word in a set satisfying the tree condition is a basis of the free group.
The aim of this paper is to describe the inversion of the sum $\sum_{n\geq 0}a^nb^n$ where $a$ and $b$ are non-commuting variables as a formal series in $a$ and $b$. We show that the inversion satisfies a non-commutative quadratic equation and that the number of certain monomials in its homogeneous components equals to a Catalan number. We also study general solutions of similar quadratic equations.
Motivated by a construction in the theory of cluster algebras (Fomin and Zelevinsky), one associates to each acyclic directed graph a family of sequences of natural integers, one for each vertex; this construction is called a {\em frieze}; these sequences are given by nonlinear recursions (with division), and the fact that they are integers is a consequence of the Laurent phenomenon of Fomin and Zelevinsky. If the sequences satisfy a linear recursion with constant coefficients, then the graph must be a Dynkin diagram or an extended Dynkin diagram, with an acyclic orientation. The converse also holds: the sequences of the frieze associated to an oriented Dynkin or Euclidean diagram satisfy linear recursions, and are even $\mathbb N$-rational. One uses in the proof objects called $SL_2$-{\em tilings of the plane}, which are fillings of the discrete plane such that each adjacent 2 by 2 minor is equal to 1. These objects, which have applications in the theory of cluster algebras, are interesting for themselves. Some problems, conjectures and exercises are given.
We prove new results concerning the relation between bifix codes, episturmian words and subgroups offree groups. We study bifix codes in factorial sets of words. We generalize most properties of ordinary maximal bifix codes to bifix codes maximal in a recurrent set $F$ of words ($F$-maximal bifix codes). In the case of bifix codes contained in Sturmian sets of words, we obtain several new results. Let $F$ be a Sturmian set of words, defined as the set of factors of a strict episturmian word. Our results express the fact that an $F$-maximal bifix code of degree $d$ behaves just as the set of words of $F$ of length $d$. An $F$-maximal bifix code of degree $d$ in a Sturmian set of words on an alphabet with $k$ letters has $(k-1)d+1$ elements. This generalizes the fact that a Sturmian set contains $(k-1)d+1$ words of length $d$. Moreover, given an infinite word $x$, if there is a finite maximal bifix code $X$ of degree $d$ such that $x$ has at most $d$ factors of length $d$ in $X$, then $x$ is ultimately periodic. Our main result states that any $F$-maximal bifix code of degree $d$ on the alphabet $A$ is the basis of a subgroup of index $d$ of the free group on~$A$.
We study properties of (bi-infinite) arrays having all adjacent $k\times k$ adjacent minors equal to one. If we further add the condition that all adjacent $(k-1)\times (k-1)$ minors be nonzero, then these arrays are necessarily of rank $k$. It follows that we can explicit construct all of them. Several nice properties are made apparent. In particular, we revisit, with this perspective, the notion of frieze patterns of Coxeter. This shed new light on their properties. A connexion is also established with the notion of $T$-systems of Statistical Physics.
Initially stated in terms of Beatty sequences, the Fraenkel conjecture can be reformulated as follows: for a $k$-letter alphabet A, with a fixed $k \geq 3$, there exists a unique balanced infinite word, up to letter permutations and shifts, that has mutually distinct letter frequencies. Motivated by the Fraenkel conjecture, we study in this paper whether two Christoffel words can be superimposed. Following from previous works on this conjecture using Beatty sequences, we give a necessary and sufficient condition for the superimposition of two Christoffel words having same length, and more generally, of two arbitrary Christoffel words. Moreover, for any two superimposable Christoffel words, we give the number of different possible superimpositions and we prove that there exists a superimposition that works for any two superimposable Christoffel words. Finally, some new properties of Christoffel words are obtained as well as a geometric proof of a classic result concerning the money problem, using Christoffel words.
Let $\mathbf D$ be the set of isomorphism types of finite double partially ordered sets, that is sets endowed with two partial orders. On $\BZ\mathbf D$ we define a product and a coproduct, together with an internal product, that is, degree-preserving. With these operations $\BZ\mathbf D$ is a Hopf algebra, self-dual with respect to a scalar product which counts the number of pictures (in the sense of Zelevinsky) between two double posets. The product and coproduct correspond respectively to disjoint union of posets and to a natural decomposition of a poset into order ideals. Restricting to special double posets (meaning that the second order is total), we obtain a notion equivalent to Stanley's labelled posets, and obtain a sub-Hopf-algebra already considered by Blessenohl and Schocker. The mapping which maps each double poset onto the sum of the linear extensions of its first order, identified via its second (total) order with permutations, is a Hopf algebra homomorphism, which is isometric and preserves the internal product, onto the Hopf algebra of permutations, previously considered by the two authors. Finally, the scalar product between any special double poset and double posets naturally associated to integer partitions is described by an extension of the Littlewood-Richardson rule.
We define a self-map Pal: F_2 --> F_2 of the free group on two generators a, b, using automorphisms of F_2 that form a group isomorphic to the braid group B_3. The map Pal restricts to de Luca's right iterated palindromic closure on the submonoid generated by a, b, and is continuous for the profinite topology on F_2. The values of Pal are palindromes and coincide with the elements g of F_2 such that abg is conjugate to bag.
We introduce a natural Hopf algebra structure on the space of noncommutative symmetric functions which was recently studied as a vector space by Rosas and Sagan. The bases for this algebra are indexed by set partitions. We show that there exist a natural inclusion of the Hopf algebra of noncommutative symmetric functions indexed by compositions in this larger space. We also consider this algebra as a subspace of noncommutative polynomials and use it to understand the structure of the spaces of harmonics and coinvariants with respect to this collection of noncommutative polynomials.
We give a presentation by generators and relations of a certain monoid generating a subgroup of index two in the group Aut(F_2) of automorphisms of the rank two free group F_2 and show that it can be realized as a monoid in the group B_4 of braids on four strings. In the second part we use Christoffel words to construct an explicit basis of F_2 lifting any given basis of the free abelian group Z^2. We further give an algorithm allowing to decide whether two elements of F_2 form a basis or not. We also show that, under suitable conditions, a basis has a unique conjugate consisting of two palindromes.