Source author record

Luca Q. Zamboni

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Formal Languages and Automata Theory math.DS math.GN math-ph math.MP math.NT

Catalog footprint

Research overview

32works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Ramsey Characterisation of Eventually Periodic Words

A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$ , if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$ . On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$ , for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$ , where $k_1 < \cdots < k_n$ , is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.

preprint2016arXiv

Cost and dimension of words of zero topological entropy

Let $A^*$ denote the free monoid generated by a finite nonempty set $A.$ In this paper we introduce a new measure of complexity of languages $L\subseteq A^*$ defined in terms of the semigroup structure on $A^*.$ For each $L\subseteq A^*,$ we define its {\it cost} $c(L)$ as the infimum of all real numbers $α$ for which there exist a language $S\subseteq A^*$ with $p_S(n)=O(n^α)$ and a positive integer $k$ with $L\subseteq S^k.$ We also define the {\it cost dimension} $d_c(L)$ as the infimum of the set of all positive integers $k$ such that $L\subseteq S^k$ for some language $S$ with $p_S(n)=O(n^{c(L)}).$ We are primarily interested in languages $L$ given by the set of factors of an infinite word $x=x_0x_1x_2\cdots \in A^ω$ of zero topological entropy, in which case $c(L)<+\infty.$ We establish the following characterisation of words of linear factor complexity: Let $x\in A^ω$ and $L=$ Fac $(x)$ be the set of factors of $x.$ Then $p_x(n)=Θ(n)$ if and only $c(L)=0$ and $d_c(L)=2.$ In other words, $p_x(n)=O(n)$ if and only if Fac $(x)\subseteq S^2$ for some language $S\subseteq A^+$ of bounded complexity (meaning $\limsup p_S(n)<+\infty).$ In general the cost of a language $L$ reflects deeply the underlying combinatorial structure induced by the semigroup structure on $A^*.$ For example, in contrast to the above characterisation of languages generated by words of sub-linear complexity, there exist non factorial languages $L$ of complexity $p_L(n)=O(\log n)$ (and hence of cost equal to $0)$ and of cost dimension $+\infty.$ In this paper we investigate the cost and cost dimension of languages defined by infinite words of zero topological entropy.

preprint2016arXiv

Cyclic Complexity of Words

We introduce and study a complexity function on words $c_x(n),$ called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equal to that of $x.$ Since $c_x(n)=1$ for some $n\geq 1$ implies $x$ is periodic, it is natural to consider the quantity $\liminf_{n\rightarrow \infty} c_x(n).$ We show that if $x$ is a Sturmian word, then $\liminf_{n\rightarrow \infty} c_x(n)=2.$ We prove however that this is not a characterization of Sturmian words by exhibiting a restricted class of Toeplitz words, including the period-doubling word, which also verify this same condition on the limit infimum. In contrast we show that, for the Thue-Morse word $t$ , $\liminf_{n\rightarrow \infty} c_t(n)=+\infty.$

preprint2016arXiv

Monochromatic factorisations of words and periodicity

In 2006 T. Brown asked the following question: Given a non-periodic infinite word $x=x_1x_2x_3\cdots$ with values in a non-empty set $\mathbb{A},$ does there exist a finite coloring $φ: \mathbb{A}^+\rightarrow C$ relative to which $x$ does not admit a $φ$ -monochromatic factorisation, i.e., a factorisation of the form $x=u_1u_2u_3\cdots$ with $φ(u_i)=φ(u_j)$ for all $i,j\geq 1$ ? Various partial results in support of an affirmative answer to this question have appeared in the literature in recent years. In particular it is known that the question admits an affirmative answer for all non-uniformly recurrent words and various classes of uniformly recurrent words including Sturmian words. In this note we answer this question in general by showing that if $x=x_1x_2x_3\cdots$ is an infinite word with values in a non-empty set $\mathbb{A},$ then $x$ is periodic if and only if for every $2$ -coloring $φ: \mathbb{A}^+\rightarrow \{0,1\}$ there exists a $φ$ -monochromatic factorisation of $x.$ This characterization of periodicity of infinite words may be reformulated in the language of ultrafilters. Let $β\mathbb{A}^+$ denote the Stone-Cech compactification of the discrete semigroup $\mathbb{A}^+$ which we regard as the set of all ultrafilters on $\mathbb{A}^+.$ Then $x$ is periodic if and only if there exists $p\in β\mathbb{A}^+$ such that for each $A\in p$ there exists a factorisation $x=u_1u_2u_3\cdots$ with each $u_i \in A.$

preprint2016arXiv

Recurrence in the dynamical system $(X,\langle T_s\rangle_{s\in S})$ and ideals of $βS$

A {\it dynamical system\/} is a pair $(X,\langle T_s\rangle_{s\in S})$ , where $X$ is a compact Hausdorff space, $S$ is a semigroup, for each $s\in S$ , $T_s$ is a continuous function from $X$ to $X$ , and for all $s,t\in S$ , $T_s\circ T_t=T_{st}$ . Given a point $p\inβS$ , the Stone-\v Cech compactification of the discrete space $S$ , $T_p:X\to X$ is defined by, for $x\in X$ , $\displaystyle T_p(x)=p{-}\!\lim_{s\in S}T_s(x)$ . We let $βS$ have the operation extending the operation of $S$ such that $βS$ is a right topological semigroup and multiplication on the left by any point of $S$ is continuous. Given $p,q\inβS$ , $T_p\circ T_q=T_{pq}$ , but $T_p$ is usually not continuous. Given a dynamical system $(X,\langle T_s\rangle_{s\in S})$ , and a point $x\in X$ , we let $U(x)=\{p\inβS:T_p(x)$ is uniformly recurrent $\}$ . We show that each $U(x)$ is a left ideal of $βS$ and for any semigroup we can get a dynamical system with respect to which $K(βS)=\bigcap_{x\in X}U(x)$ and $c\ell K(βS)=\bigcap\{U(x):x\in X$ and $U(x)$ is closed $\}$ . And we show that weak cancellation assumptions guarantee that each such $U(x)$ properly contains $K(βS)$ and has $U(x) \setminus c\ell K(βS)\neq \emptyset$ .

preprint2015arXiv

On a group theoretic generalization of the Morse-Hedlund theorem

In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word $x\in A^N,$ over a non empty finite alphabet $A,$ contains at least $n+1$ distinct factors of each length $n.$ They further showed that an infinite word $x$ has exactly $n+1$ distinct factors of each length $n$ if and only if $x$ is binary, aperiodic and balanced, i.e., $x$ is a Sturmian word. In this paper we obtain a broad generalization of the Morse-Hedlund theorem via group actions. Given a subgroup $G$ of the symmetric group $S_n,$ let $1\leq ε(G)\leq n$ denote the number of distinct $G$ -orbits of $\{1,2,\ldots ,n\}.$ Since $G$ is a subgroup of $S_n,$ it acts on $A^n=\{a_1a_2\cdots a_n\,|\,a_i\in A\}$ by permutation. Thus, given an infinite word $x\in A^N$ and an infinite sequence $ω=(G_n)_{n\geq 1}$ of subgroups $G_n \subseteq S_n,$ we consider the complexity function $p_{ω,x}:N \rightarrow N$ which counts for each length $n$ the number of equivalence classes of factors of $x$ of length $n$ under the action of $G_n.$ We show that if $x$ is aperiodic, then $p_{ω, x}(n)\geqε(G_n)+1$ for each $n\geq 1,$ and moreover, if equality holds for each $n,$ then $x$ is Sturmian. Conversely, let $x$ be a Sturmian word. Then for every infinite sequence $ω=(G_n)_{n\geq 1}$ of Abelian subgroups $G_n \subseteq S_n,$ there exists $ω'=(G_n')_{n\geq 1}$ such that for each $n\geq 1:$ $G_n'\subseteq S_n$ is isomorphic to $G_n$ and $p_{ω',x}(n)=ε(G'_n)+1.$ Applying the above results to the sequence $(Id_n)_{n\geq 1},$ where $Id_n$ is the trivial subgroup of $S_n$ consisting only of the identity, we recover both directions of the Morse-Hedland theorem.

preprint2015arXiv

On prefixal factorizations of words

We consider the class ${\cal P}_1$ of all infinite words $x\in A^ω$ over a finite alphabet $A$ admitting a prefixal factorization, i.e., a factorization $x= U_0 U_1U_2 \cdots$ where each $U_i$ is a non-empty prefix of $x.$ With each $x\in {\cal P}_1$ one naturally associates a "derived" infinite word $δ(x)$ which may or may not admit a prefixal factorization. We are interested in the class ${\cal P}_{\infty}$ of all words $x$ of ${\cal P}_1$ such that $δ^n(x) \in {\cal P}_1$ for all $n\geq 1$ . Our primary motivation for studying the class ${\cal P}_{\infty}$ stems from its connection to a coloring problem on infinite words independently posed by T. Brown in \cite{BTC} and by the second author in \cite{LQZ}. More precisely, let ${\bf P}$ be the class of all words $x\in A^ω$ such that for every finite coloring $φ: A^+ \rightarrow C$ there exist $c\in C$ and a factorization $x= V_0V_1V_2\cdots$ with $φ(V_i)=c$ for each $i\geq 0.$ In \cite{DPZ} we conjectured that a word $x\in {\bf P}$ if and only if $x$ is purely periodic. In this paper we show that ${\bf P}\subseteq {\cal P}_{\infty},$ so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of ${\cal P}_{\infty}.$ We establish several results on the class ${\cal P}_{\infty}$ . In particular, we show that a Sturmian word $x$ belongs to ${\cal P}_{\infty}$ if and only if $x$ is nonsingular, i.e., no proper suffix of $x$ is a standard Sturmian word.

preprint2015arXiv

On some variations of coloring problems of infinite words

Given a finite coloring (or finite partition) of the free semigroup $A^+$ over a set $A$ , we consider various types of monochromatic factorizations of right sided infinite words $x\in A^ω$ . Some stronger versions of the usual notion of monochromatic factorization are introduced. A factorization is called sequentially monochromatic when concatenations of consecutive blocks are monochromatic. A sequentially monochromatic factorization is called ultra monochromatic if any concatenation of arbitrary permuted blocks of the factorization has the same color of the single blocks. We establish links, and in some cases equivalences, between the existence of these factorizations and fundamental results in Ramsey theory including the infinite Ramsey theorem, Hindman's finite sums theorem, partition regularity of IP sets and the Milliken-Taylor theorem. We prove that for each finite set $A$ and each finite coloring $φ: A^+\rightarrow C,$ for almost all words $x\in A^ω,$ there exists $y$ in the subshift generated by $x$ admitting a $φ$ -ultra monochromatic factorization, where "almost all" refers to the Bernoulli measure on $A^ω.$

preprint2014arXiv

A Coloring Problem for Infinite Words

In this paper we consider the following question in the spirit of Ramsey theory: Given $x\in A^ω,$ where $A$ is a finite non-empty set, does there exist a finite coloring of the non-empty factors of $x$ with the property that no factorization of $x$ is monochromatic? We prove that this question has a positive answer using two colors for almost all words relative to the standard Bernoulli measure on $A^ω.$ We also show that it has a positive answer for various classes of uniformly recurrent words, including all aperiodic balanced words, and all words $x\in A^ω$ satisfying $λ_x(n+1)-λ_x(n)=1$ for all $n$ sufficiently large, where $λ_x(n)$ denotes the number of distinct factors of $x$ of length $n.$

preprint2014arXiv

Infinite Self-Shuffling Words

In this paper we introduce and study a new property of infinite words: An infinite word $x\in A^\mathbb{N}$ , with values in a finite set $A$ , is said to be $k$ -self-shuffling $(k\geq 2)$ if $x$ admits factorizations: $x=\prod_{i=0}^\infty U_i^{(1)}\cdots U_i^{(k)}=\prod_{i=0}^\infty U_i^{(1)}=\cdots =\prod_{i=0}^\infty U_i^{(k)}$ . In other words, there exists a shuffle of $k$ -copies of $x$ which produces $x$ . We are particularly interested in the case $k=2$ , in which case we say $x$ is self-shuffling. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue-Morse word and all Sturmian words of intercept $0<ρ<1$ (while those of intercept $ρ=0$ are not self-shuffling). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the {\it stepping stone model}. One important feature of self-shuffling words stems from its morphic invariance, which provides a useful tool for showing that one word is not the morphic image of another. The notion of self-shuffling has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic.

preprint2013arXiv

A Coloring Problem for Sturmian and Episturmian Words

We consider the following open question in the spirit of Ramsey theory: Given an aperiodic infinite word $w$ , does there exist a finite coloring of its factors such that no factorization of $w$ is monochromatic? We show that such a coloring always exists whenever $w$ is a Sturmian word or a standard episturmian word.

preprint2013arXiv

Central sets and substitutive dynamical systems

In this paper we establish a new connection between central sets and the strong coincidence conjecture for fixed points of irreducible primitive substitutions of Pisot type. Central sets, first introduced by Furstenberg using notions from topological dynamics, constitute a special class of subsets of $\nats$ possessing strong combinatorial properties: Each central set contains arbitrarily long arithmetic progressions, and solutions to all partition regular systems of homogeneous linear equations. We give an equivalent reformulation of the strong coincidence condition in terms of central sets and minimal idempotent ultrafilters in the Stone-Čech compactification $β\nats .$ This provides a new arithmetical approach to an outstanding conjecture in tiling theory, the Pisot substitution conjecture. The results in this paper rely on interactions between different areas of mathematics, some of which had not previously been directly linked: They include the general theory of combinatorics on words, abstract numeration systems, tilings, topological dynamics and the algebraic/topological properties of Stone-Čech compactification of $\nats.$

preprint2013arXiv

Central sets defined by words of low factor complexity

A subset $A$ of $\mathbb{N}$ is called an IP-set if $A$ contains all finite sums of distinct terms of some infinite sequence $(x_n)_{n\in \mathbb{N}}$ of natural numbers. Central sets, first introduced by Furstenberg using notions from topological dynamics, constitute a special class of IP-sets possessing additional nice combinatorial properties: Each central set contains arbitrarily long arithmetic progressions, and solutions to all partition regular systems of homogeneous linear equations. In this paper we show how certain families of aperiodic words of low factor complexity may be used to generate a wide assortment of central sets having additional nice properties inherited from the rich combinatorial structure of the underlying word. We consider Sturmian words and their extensions to higher alphabets (so-called Arnoux-Rauzy words), as well as words generated by substitution rules including the famous Thue-Morse word. We also describe a connection between central sets and the strong coincidence condition for fixed points of primitive substitutions which represents a new approach to the strong coincidence conjecture for irreducible Pisot substitutions. Our methods simultaneously exploit the general theory of combinatorics on words, the arithmetic properties of abstract numeration systems defined by substitution rules, notions from topological dynamics including proximality and equicontinuity, the spectral theory of symbolic dynamical systems, and the beautiful and elegant theory, developed by N. Hindman, D. Strauss and others, linking IP-sets to the algebraic/topological properties of the Stone-Čech compactification of $\mathbb{N}.$ Using the key notion of $p$ - $\lim_n,$ regarded as a mapping from words to words, we apply ideas from combinatorics on words in the framework of ultrafilters.

preprint2013arXiv

Central sets generated by uniformly recurrent words

A subset $A$ of $\nats$ is called an IP-set if $A$ contains all finite sums of distinct terms of some infinite sequence $(x_n)_{n\in \nats} $ of natural numbers. Central sets, first introduced by Furstenberg using notions from topological dynamics, constitute a special class of IP-sets possessing rich combinatorial properties: Each central set contains arbitrarily long arithmetic progressions, and solutions to all partition regular systems of homogeneous linear equations. In this paper we investigate central sets in the framework of combinatorics on words. Using various families of uniformly recurrent words, including Sturmian words, the Thue-Morse word and fixed points of weak mixing substitutions, we generate an assortment of central sets which reflect the rich combinatorial structure of the underlying words. The results in this paper rely on interactions between different areas of mathematics, some of which had not previously been directly linked. They include the general theory of combinatorics on words, abstract numeration systems, and the beautiful theory, developed by Hindman, Strauss and others, linking IP-sets and central sets to the algebraic/topological properties of the Stone-Čech compactification of $\nats .$

preprint2013arXiv

Extremal words in morphic subshifts

Given an infinite word X over an alphabet A a letter b occurring in X, and a total order σon A, we call the smallest word with respect to σstarting with b in the shift orbit closure of X an extremal word of X. In this paper we consider the extremal words of morphic words. If X = g(f^ω(a)) for some morphisms f and g, we give two simple conditions on f and g that guarantees that all extremal words are morphic. This happens, in particular, when X is a primitive morphic or a binary pure morphic word. Our techniques provide characterizations of the extremal words of the Period-doubling word and the Chacon word and give a new proof of the form of the lexicographically least word in the shift orbit closure of the Rudin-Shapiro word.

preprint2013arXiv

On a generalization of Abelian equivalence and complexity of infinite words

In this paper we introduce and study a family of complexity functions of infinite words indexed by $k \in \ints ^+ \cup {+\infty}.$ Let $k \in \ints ^+ \cup {+\infty}$ and $A$ be a finite non-empty set. Two finite words $u$ and $v$ in $A^*$ are said to be $k$ -Abelian equivalent if for all $x\in A^*$ of length less than or equal to $k,$ the number of occurrences of $x$ in $u$ is equal to the number of occurrences of $x$ in $v.$ This defines a family of equivalence relations $\thicksim_k$ on $A^*,$ bridging the gap between the usual notion of Abelian equivalence (when $k=1$ ) and equality (when $k=+\infty).$ We show that the number of $k$ -Abelian equivalence classes of words of length $n$ grows polynomially, although the degree is exponential in $k.$ Given an infinite word $ω\in A^\nats,$ we consider the associated complexity function $\mathcal {P}^{(k)}_ω:\nats \rightarrow \nats$ which counts the number of $k$ -Abelian equivalence classes of factors of $ω$ of length $n.$ We show that the complexity function $\mathcal {P}^{(k)}$ is intimately linked with periodicity. More precisely we define an auxiliary function $q^k: \nats \rightarrow \nats$ and show that if $\mathcal {P}^{(k)}_ω(n)<q^k(n)$ for some $k \in \ints ^+ \cup {+\infty}$ and $n\geq 0,$ the $ω$ is ultimately periodic. Moreover if $ω$ is aperiodic, then $\mathcal {P}^{(k)}_ω(n)=q^k(n)$ if and only if $ω$ is Sturmian. We also study $k$ -Abelian complexity in connection with repetitions in words. Using Szemerédi's theorem, we show that if $ω$ has bounded $k$ -Abelian complexity, then for every $D\subset \nats$ with positive upper density and for every positive integer $N,$ there exists a $k$ -Abelian $N$ power occurring in $ω$ at some position $j\in D.$

preprint2013arXiv

On a question of Hof, Knill and Simon on palindromic substitutive systems

In a 1995 paper, Hof, Knill and Simon obtain a sufficient combinatorial criterion on the hull $Ω$ of the potential of a discrete Schrödinger operator which guarantees purely singular continuous spectrum on a generic subset of $Ω.$ In part, this condition requires the existence of infinitely many palindromic factors. In this same paper, they introduce the class P of morphisms $f:A^*\rightarrow B^*$ of the form $a\mapsto pq_a$ and ask whether every palindromic subshift generated by a primitive substitution arises from morphisms of class P or by morphisms of the form $a\mapsto q_ap$ where again $p$ and $q_a$ are palindromes. In this paper we give a partial affirmative answer to the question of Hof, Knill and Simon: we show that every rich primitive substitutive subshift is generated by at most two morphisms each of which is conjugate to a morphism of class P. More precisely, we show that every rich (or almost rich in the sense of finite defect) primitive morphic word $y\in B^ω$ is of the form $y=f(x)$ where $f:A^*\rightarrow B^*$ is conjugate to a morphism of class P, and where $x$ is a rich word fixed by a primitive substitution $g:A^*\rightarrow A^*$ of class P.

preprint2013arXiv

On additive properties of sets defined by the Thue-Morse word

In this paper we study some additive properties of subsets of the set $\nats$ of positive integers: A subset $A$ of $\nats$ is called {\it $k$ -summable} (where $k\in\ben$) if $A$ contains $\textstyle \big{\sum_{n\in F}x_n | \emp\neq F\subseteq {1,2,...,k\} \big}$ for some $k$ -term sequence of natural numbers $x_1<x_2 < ... < x_k$ . We say $A \subseteq \nats$ is finite FS-big if $A$ is $k$ -summable for each positive integer $k$ . We say is $A \subseteq \nats$ is infinite FS-big if for each positive integer $k,$ $A$ contains ${\sum_{n\in F}x_n | \emp\neq F\subseteq \nats and #F\leq k}$ for some infinite sequence of natural numbers $x_1<x_2 < ...$ . We say $A\subseteq \nats $ is an IP-set if $A$ contains ${\sum_{n\in F}x_n | \emp\neq F\subseteq \nats and #F<\infty}$ for some infinite sequence of natural numbers $x_1<x_2 < ...$ . By the Finite Sums Theorem [5], the collection of all IP-sets is partition regular, i.e., if $A$ is an IP-set then for any finite partition of $A$ , one cell of the partition is an IP-set. Here we prove that the collection of all finite FS-big sets is also partition regular. Let $\TM =011010011001011010... $ denote the Thue-Morse word fixed by the morphism $0\mapsto 01$ and $1\mapsto 10$ . For each factor $u$ of $\TM$ we consider the set $\TM\big|_u\subseteq \nats$ of all occurrences of $u$ in $\TM$. In this note we characterize the sets $\TM\big|_u$ in terms of the additive properties defined above. Using the Thue-Morse word we show that the collection of all infinite FS-big sets is not partition regular.

preprint2013arXiv

On the least number of palindromes contained in an infinite word

We investigate the least number of palindromic factors in an infinite word. We first consider general alphabets, and give answers to this problem for periodic and non-periodic words, closed or not under reversal of factors. We then investigate the same problem when the alphabet has size two.

preprint2013arXiv

Reversible Christoffel factorizations

We define a family of natural decompositions of Sturmian words in Christoffel words, called *reversible Christoffel* (RC) factorizations. They arise from the observation that two Sturmian words with the same language have (almost always) arbitrarily long Abelian equivalent prefixes. Using the three gap theorem, we prove that in each RC factorization, only 2 or 3 distinct Christoffel words may occur. We begin the study of such factorizations, considered as infinite words over 2 or 3 letters, and show that in the general case they are either Sturmian words, or obtained by a three-interval exchange transformation.

preprint2012arXiv

Abelian returns in Sturmian words

Return words constitute a powerful tool for studying symbolic dynamical systems. They may be regarded as a discrete analogue of the first return map in dynamical systems. In this paper we investigate two abelian variants of the notion of return word, each of them gives rise to a new characterization of Sturmian words. We prove that a recurrent infinite word is Sturmian if and only if each of its factors has two or three abelian (or semi-abelian) returns. We study the structure of abelian returns in Sturmian words and give a characterization of those factors having exactly two abelian returns. Finally we discuss connections between abelian returns and periodicity in words.

preprint2012arXiv

Clustering words

We characterize words which cluster under the Burrows-Wheeler transform as those words $w$ such that $ww$ occurs in a trajectory of an interval exchange transformation, and build examples of clustering words.

preprint2012arXiv

Some characterizations of Sturmian words in terms of the lexicographic order

In this paper we present three new characterizations of Sturmian words based on the lexicographic ordering of their factors.

preprint2011arXiv

Abelian returns in Sturmian words

In this paper we study an abelian version of the notion of return word. Our main result is a new characterization of Sturmian words via abelian returns. Namely, we prove that a word is Sturmian if and only if each of its factors has two or three abelian returns. In addition, we describe the structure of abelian returns in Sturmian words, and discuss connections between abelian returns and periodicity.

preprint2010arXiv

Avoiding Abelian powers in binary words with bounded Abelian complexity

The notion of Abelian complexity of infinite words was recently used by the three last authors to investigate various Abelian properties of words. In particular, using van der Waerden's theorem, they proved that if a word avoids Abelian $k$ -powers for some integer $k$ , then its Abelian complexity is unbounded. This suggests the following question: How frequently do Abelian $k$ -powers occur in a word having bounded Abelian complexity? In particular, does every uniformly recurrent word having bounded Abelian complexity begin in an Abelian $k$ -power? While this is true for various classes of uniformly recurrent words, including for example the class of all Sturmian words, in this paper we show the existence of uniformly recurrent binary words, having bounded Abelian complexity, which admit an infinite number of suffixes which do not begin in an Abelian square. We also show that the shift orbit closure of any infinite binary overlap-free word contains a word which avoids Abelian cubes in the beginning. We also consider the effect of morphisms on Abelian complexity and show that the morphic image of a word having bounded Abelian complexity has bounded Abelian complexity. Finally, we give an open problem on avoidability of Abelian squares in infinite binary words and show that it is equivalent to a well-known open problem of Pirillo-Varricchio and Halbeisen-Hungerbühler.

preprint2009arXiv

Abelian Complexity in Minimal Subshifts

In this paper we undertake the general study of the Abelian complexity of an infinite word on a finite alphabet. We investigate both similarities and differences between the Abelian complexity and the usual subword complexity. While the Thue-Morse minimal subshift is neither characterized by its Abelian complexity nor by its subword complexity alone, we show that the subshift is completely characterized by the two complexity functions together. We give an affirmative answer to an old question of G. Rauzy by exhibiting a class of words whose Abelian complexity is everywhere equal to 3. We also investigate links between Abelian complexity and the existence of Abelian powers. Using van der Waerden's Theorem, we show that any minimal subshift having bounded Abelian complexity contains Abelian k-powers for every positive integer k. In the case of Sturmian words we prove something stronger: For every Sturmian word w and positive integer k, each sufficiently long factor of w begins in an Abelian k-power.

preprint2009arXiv

Balance and Abelian complexity of the Tribonacci word

G. Rauzy showed that the Tribonacci minimal subshift generated by the morphism $τ: 0\mapsto 01, 1\mapsto 02 and 2\mapsto 0$ is measure-theoretically conjugate to an exchange of three fractal domains on a compact set in $R^2$ , each domain being translated by the same vector modulo a lattice. In this paper we study the Abelian complexity AC(n) of the Tribonacci word $t$ which is the unique fixed point of $τ$ . We show that $AC(n)\in {3,4,5,6,7}$ for each $n\geq 1$ , and that each of these five values is assumed. Our proof relies on the fact that the Tribonacci word is 2-balanced, i.e., for all factors $U$ and $V$ of $t$ of equal length, and for every letter $a \in {0,1,2}$ , the number of occurrences of $a$ in $U$ and the number of occurrences of $a$ in $V$ differ by at most 2. While this result is announced in several papers, to the best of our knowledge no proof of this fact has ever been published. We offer two very different proofs of the 2-balance property of $t$ . The first uses the word combinatorial properties of the generating morphism, while the second exploits the spectral properties of the incidence matrix of $τ$ .

preprint2008arXiv

A connection between palindromic and factor complexity using return words

In this paper we prove that for any infinite word W whose set of factors is closed under reversal, the following conditions are equivalent: (I) all complete returns to palindromes are palindromes; (II) P(n) + P(n+1) = C(n+1) - C(n) + 2 for all n, where P (resp. C) denotes the palindromic complexity (resp. factor complexity) function of W, which counts the number of distinct palindromic factors (resp. factors) of each length in W.

preprint2008arXiv

A new characteristic property of rich words

Originally introduced and studied by the third and fourth authors together with J. Justin and S. Widmer in arXiv:0801.1656, rich words constitute a new class of finite and infinite words characterized by containing the maximal number of distinct palindromes. Several characterizations of rich words have already been established. A particularly nice characteristic property is that all 'complete returns' to palindromes are palindromes. In this note, we prove that rich words are also characterized by the property that each factor is uniquely determined by its longest palindromic prefix and its longest palindromic suffix.

preprint2008arXiv

Palindromic Richness

In this paper, we study combinatorial and structural properties of a new class of finite and infinite words that are 'rich' in palindromes in the utmost sense. A characteristic property of so-called "rich words" is that all complete returns to any palindromic factor are themselves palindromes. These words encompass the well-known episturmian words, originally introduced by the second author together with X. Droubay and G. Pirillo in 2001. Other examples of rich words have appeared in many different contexts. Here we present the first unified approach to the study of this intriguing family of words. Amongst our main results, we give an explicit description of the periodic rich infinite words and show that the recurrent balanced rich infinite words coincide with the balanced episturmian words. We also consider two wider classes of infinite words, namely "weakly rich words" and almost rich words (both strictly contain all rich words, but neither one is contained in the other). In particular, we classify all recurrent balanced weakly rich words. As a consequence, we show that any such word on at least three letters is necessarily episturmian; hence weakly rich words obey Fraenkel's conjecture. Likewise, we prove that a certain class of almost rich words obeys Fraenkel's conjecture by showing that the recurrent balanced ones are episturmian or contain at least two distinct letters with the same frequency. Lastly, we study the action of morphisms on (almost) rich words with particular interest in morphisms that preserve (almost) richness. Such morphisms belong to the class of "P-morphisms" that was introduced by A. Hof, O. Knill, and B. Simon in 1995.

preprint2008arXiv

Rich, Sturmian, and trapezoidal words

In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced in arXiv:0801.1656 by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity.

preprint2002arXiv

Arnoux-Rauzy Subshifts: Linear Recurrence, Powers, and Palindromes

We consider Arnoux-Rauzy subshifts $X$ and study various combinatorial questions: When is $X$ linearly recurrent? What is the maximal power occurring in $X$ ? What is the number of palindromes of a given length occurring in $X$ ? We present applications of our combinatorial results to the spectral theory of discrete one-dimensional Schrödinger operators with potentials given by Arnoux-Rauzy sequences.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Luca Q. Zamboni

Research overview

Is this your work?

32 publications

A Ramsey Characterisation of Eventually Periodic Words

Cost and dimension of words of zero topological entropy

Cyclic Complexity of Words

Monochromatic factorisations of words and periodicity

Recurrence in the dynamical system $(X,\langle T_s\rangle_{s\in S})$ and ideals of $βS$

On a group theoretic generalization of the Morse-Hedlund theorem

On prefixal factorizations of words

On some variations of coloring problems of infinite words

A Coloring Problem for Infinite Words

Infinite Self-Shuffling Words

A Coloring Problem for Sturmian and Episturmian Words

Central sets and substitutive dynamical systems

Central sets defined by words of low factor complexity

Central sets generated by uniformly recurrent words

Extremal words in morphic subshifts

On a generalization of Abelian equivalence and complexity of infinite words

On a question of Hof, Knill and Simon on palindromic substitutive systems

On additive properties of sets defined by the Thue-Morse word

On the least number of palindromes contained in an infinite word

Reversible Christoffel factorizations

Abelian returns in Sturmian words

Clustering words

Some characterizations of Sturmian words in terms of the lexicographic order

Abelian returns in Sturmian words

Avoiding Abelian powers in binary words with bounded Abelian complexity

Abelian Complexity in Minimal Subshifts

Balance and Abelian complexity of the Tribonacci word

A connection between palindromic and factor complexity using return words

A new characteristic property of rich words

Palindromic Richness

Rich, Sturmian, and trapezoidal words

Arnoux-Rauzy Subshifts: Linear Recurrence, Powers, and Palindromes

See the researcher in context

Building this map preview

Luca Q. Zamboni

Research overview

Is this your work?

32 publications

A Ramsey Characterisation of Eventually Periodic Words

Cost and dimension of words of zero topological entropy

Cyclic Complexity of Words

Monochromatic factorisations of words and periodicity

Recurrence in the dynamical system (X,⟨Ts⟩s∈S)(X,\langle T_s\rangle_{s\in S})(X,⟨Ts​⟩s∈S​) and ideals of βSβSβS

On a group theoretic generalization of the Morse-Hedlund theorem

On prefixal factorizations of words

On some variations of coloring problems of infinite words

A Coloring Problem for Infinite Words

Infinite Self-Shuffling Words

A Coloring Problem for Sturmian and Episturmian Words

Central sets and substitutive dynamical systems

Central sets defined by words of low factor complexity

Central sets generated by uniformly recurrent words

Extremal words in morphic subshifts

On a generalization of Abelian equivalence and complexity of infinite words

On a question of Hof, Knill and Simon on palindromic substitutive systems

On additive properties of sets defined by the Thue-Morse word

On the least number of palindromes contained in an infinite word

Reversible Christoffel factorizations

Abelian returns in Sturmian words

Clustering words

Some characterizations of Sturmian words in terms of the lexicographic order

Abelian returns in Sturmian words

Avoiding Abelian powers in binary words with bounded Abelian complexity

Abelian Complexity in Minimal Subshifts

Balance and Abelian complexity of the Tribonacci word

A connection between palindromic and factor complexity using return words

A new characteristic property of rich words

Palindromic Richness

Rich, Sturmian, and trapezoidal words

Arnoux-Rauzy Subshifts: Linear Recurrence, Powers, and Palindromes

See the researcher in context

Building this map preview

Recurrence in the dynamical system $(X,\langle T_s\rangle_{s\in S})$ and ideals of $βS$