## GENERALIZED TRAPEZOIDAL WORDS

## AMYGLENANDFLORENCELEVÉ

ABSTRACT. The factor complexity function Cw ( n ) of a finite or infinite word w counts the number of distinct factors of w of length n for each n ≥ 0. A finite word w of length | w | is said to be trapezoidal if the graph of its factor complexity Cw n ( ) as a function of n (for 0 ≤ n ≤ | w | ) is that of a regular trapezoid (or possibly an isosceles triangle); that is, Cw n ( ) increases by 1 with each n on some interval of length r , then Cw n ( ) is constant on some interval of length s , and finally Cw n ( ) decreases by 1 with each n on an interval of the same length r . Necessarily Cw ( 1 ) = 2 (since there is one factor of length 0, namely the empty word ), so any trapezoidal word is on a binary alphabet. Trapezoidal words were first introduced by de Luca (1999) when studying the behaviour of the factor complexity of finite Sturmian words , i.e., factors of infinite 'cutting sequences', obtained by coding the sequence of cuts in an integer lattice over the positive quadrant of R 2 made by a line of irrational slope. Every finite Sturmian word is trapezoidal, but not conversely. However, both families of words (trapezoidal and Sturmian) are special classes of socalled rich words (also known as full words ) - a wider family of finite and infinite words characterized by containing the maximal number of palindromes - studied in depth by the first author and others in 2009.

In this paper, we introduce a natural generalization of trapezoidal words over an arbitrary finite alphabet A , called generalized trapezoidal words (or GT-words for short). In particular, we study combinatorial and structural properties of this new class of words, and we show that, unlike the binary case, not all GT-words are rich in palindromes when |A| ≥ 3, but we can describe all those that are rich.

## 1. INTRODUCTION

Given a finite or infinite word w , let Cw n ( ) (resp. Pw ( n ) ) denote the factor complexity function (resp. the palindromic complexity function ) of w , which associates with each integer n ≥ 0 the number of distinct factors (resp. palindromic factors) of w of length n . The well-known infinite Sturmian words are characterized by both their factor complexity and palindromic complexity. In 1940 Morse and Hedlund [11] established that an infinite word w is Sturmian if and only if C w ( n ) = n + 1 for each n ≥ 0. Almost half a century later, in 1999, Droubay and Pirillo [7] showed that an infinite word w is Sturmian if and only if P w ( n ) = 1 whenever n is even, and P w ( n ) = 2 whenever n is odd. In the same year, de Luca [4] studied the factor complexity function of finite words and showed, in particular, that if w is a finite Sturmian word (meaning a factor of an infinite Sturmian word), then the graph of Cw n ( ) as a function of n (for 0 ≤ n ≤ | w | , where | w | denotes the length of w ) is that of a regular trapezoid (or possibly an isosceles triangle). That is, Cw n ( ) increases by 1 with each n on some interval of length r , then Cw n ( ) is constant on some interval of length s , and finally Cw n ( ) decreases by 1 with each n on an interval of the same size r . Such a word is said to be trapezoidal . Since Cw ( 1 ) = 2, any trapezoidal word is necessarily on a binary alphabet.

In this paper, we study combinatorial and structural properties of the following natural generalization of trapezoidal words over an arbitrary finite alphabet.

Date : Submitted August 2014; Revised February 2015.

2000 Mathematics Subject Classification. 68R15.

Key words and phrases. word complexity; trapezoidal word; Sturmian word; palindrome; rich word.

Corresponding author: Amy Glen.

Note: Preliminary work on this new class of words was presented in talks by the first author at the 35th Australasian Conference on Combinatorial Mathematics &amp; Combinatorial Computing (35ACCMCC) in December 2011 and at a workshop on Outstanding Challenges in Combinatorics on Words at the Banff International Research Station (BIRS) in February 2012.

Definition 1. A finite word w with alphabet Alph ( w ) : = A |A| ≥ , 2, is said to be a generalized trapezoidal word (or GT-word for short) if there exist positive integers m M , with m ≤ M such that the factor complexity funtion Cw n ( ) of w increases by 1 for each n in the interval [ 1, m ] , is constant for each n in the interval [ m M , ] , and decreases by 1 for each n in the interval [ M w , | | ] . That is, w is a GT-word if there exist positive integers m M , with m ≤ M such that Cw satisfies the following:

$$\begin{array} { c c c c } \tilde { \nu } & \cdot$$

So if a finite word w consisting of at least two distinct letters is a GT-word then the graph of its factor complexity Cw n ( ) as a function of n (for 0 ≤ n ≤ | w | ) forms a regular trapezoid (or possibly an isosceles triangle when m = M ) on the interval [ 1, | w | - |A| + ] 1 , as shown in Figure 1 below. In the case of a 2-letter alphabet, the GT-words are precisely the (binary) trapezoidal words studied by de Luca [4].

FIGURE 1. Graph of the factor complexity function Cw n ( ) of a GT-word w .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0451v2-figure-5265a355-4f61-4925-852e-63a1184dd0f8.jpg)

Remark 2. In what follows, any finite word w with | Alph w ( ) | = 1 (e.g., w = aaaa) will also be classed as a generalized trapezoidal word since the complexity function of such a word, being constant on the interval [ 1, | w , satisfies the 'trapezoidal conditions' in Definition 1 with m | ] = 1 and M = | w . |

Let w be a finite word with alphabet Alph ( w ) : = A |A| ≥ , 2. A right special factor u of w is one that can be extended to the right by at least two different letters and still remains a factor of w , i.e., ux is a factor of w for at least two different letters x ∈ A . Let Rw ( = R ) denote the smallest positive integer r such that w has no right special factor of length r and let Kw ( = K ) denote the length of the shortest unrepeated suffix of w (i.e., the shortest suffix of w that occurs only once in w ). In [4, Proposition 4.7], de Luca proved that a finite word w is a binary trapezoidal word if and only if | w | = Rw + Kw .

Example 3. The binary word w = aaabb of length 5 has complexity sequence { Cw n ( ) } n ≥ 0 = 1, 2, 3, 3, 2, 1, so w is clearly a trapezoidal word and we see that Rw = 3, Kw = 2, and indeed | w | = Rw + Kw .

Every finite Sturmian word w , being a binary trapezoidal word, satisfies the condition | w | = Rw + Kw , but not conversely, i.e., there exist non-Sturmian binary trapezoidal words. For instance, the binary trapezoidal word aaabb in Example 3 is not Sturmian because it contains two palindromes,

aa and bb , of even length 2. All non-Sturmian trapezoidal words were classified by D'Alessandro [3] in 2002.

/negationslash

It is natural to wonder if there is an analogous combinatorial characterization in terms of R and K for generalized trapezoidal words. One might guess, for instance, that GT-words are, perhaps, the finite words w that satisfy the condition | w | = Rw + Kw + | Alph ( w ) | -2. But whilst it is true that any word satisfying this 'RK-condition' is a GT-word (see Corollary 6 later), the converse does not hold. For example, the GT-word u = ababadac of length 8 with complexity sequence { Cu ( n ) } n ≥ 0 = 1, 4, 5, 5, 5, 4, 3, 2, 1 has Ru = 4 and Ku = 1, but Ru + Ku + 2 = 8. However, we see that | u | = Rv + Kv + | Alph ( u ) | -2 where v is the so-called 'heart' of u (see Definition 11); namely, the factor v = ababada (with Rv = 4, Kv = 2) obtained from u by deleting its last letter c that occurs only once in u . It turns out that the condition | w | = Rv + Kv + | Alph ( w ) | -2, where v is the heart of w , does indeed characterize generalized trapezoidal words (see Theorem 17 later).

In the next section, we prove some combinatorial properties of GT-words, particularly with respect to the parameters R and K , followed by our main results in Section 3 where we prove some characterizations of GT-words (see Theorem 17, Corollary 20, and Theorem 21) and describe all the GT-words that are rich in palindromes (see Theorem 27). We use standard terminology and notation for combinatorics on words, as in the book [10], for instance.

## 2. PRELIMINARY RESULTS

The following result of de Luca [4], which describes the graph of the complexity function of any given word w , will be needed in what follows.

Proposition 4. [4, Proposition 4.2] Let w be a finite word with | Alph w ( ) | ≥ 2 and let m = min { Rw Kw , } , M = max { Rw Kw , } . The factor complexity function Cw of w is strictly increasing on the interval [ 0, m , is ] non-decreasing on the interval [ m M , and is strictly decreasing on the interval , ] [ M w . Moreover, for all , | | ] n ∈ [ M w , one has Cw , | | ] ( n + ) = 1 Cw n ( ) -1 . If Rw &lt; Kw, then Cw is constant on the interval [ m M . , ]

As a first step towards obtaining a combinatorial characterization of generalized trapezoidal words, we describe, in the following theorem, the finite words w satisfying the so-called RK-condition | w | = Rw + Kw + | Alph ( w ) | -2.

Theorem 5. Suppose w is a finite word with Alph ( w ) : = A |A| ≥ , 2 . Then | w | = Rw + Kw + |A| 2 if and only if the factor complexity function Cw of w satisfies:

$$\begin{array} {$$

where m = min { Kw , Rw } and M = max { Kw , Rw } . Moreover, Cw ( Rw ) = Cw Kw ( ) and the maximal value of Cw is m + |A| 1 .

Proof. ( ⇒ ): Suppose that | w | = Rw + Kw + |A| 2. We first consider the case Rw ≤ Kw so that m = Rw and M = Kw . By Proposition 4, we know that Cw is strictly increasing on the interval [ 0, Rw ] and is constant on the interval [ Rw Kw , ] , and then strictly decreasing on the interval [ Kw , | w | ] ; in particular,

$$C _ { w } ( i + 1 ) = C _ { w } ( i ) - 1 \$$

It remains to show that Cw i ( ) = |A| + i -1 for i ∈ [ 1, Rw ] . Since Cw ( 1 ) = |A| , we have Cw i ( ) ≥ |A| + i -1 for i ∈ [ 1, Rw ] , so Cw ( Rw ) ≥ |A| + Rw -1, and in fact, we have Cw ( Rw ) = |A| + Rw -1.

Indeed, from Equation (1) and the hypothesis | w | = Rw + Kw + |A| 2, we deduce that

$$1 = C _ { w } ( | w | ) = C _ { w } ( K _ {$$

Hence, since Cw Kw ( ) = Cw ( Rw ) , it follows that Cw ( Rw ) = |A| + Rw -1. This implies that Cw i ( ) = |A| + i -1 for i ∈ [ 1, Rw ] . For if not, then there exists an r &lt; Rw such that Cw r ( ) &gt; |A| + r -1 and Cw r ( + ) n ≥ Cw r ( ) + n for n = 1, 2, . . . , Rw -r (e.g., see [4]) implying that

$$C _ { w } ( R _ { w } ) \geq C _ { w } ( r$$

which is impossible because Cw ( Rw ) = |A| + Rw -1.

Nowlet us consider the case Kw &lt; Rw , so that m = Kw and M = Rw . By Proposition 4, we know that Cw is strictly increasing on the interval [ 0, Kw ] and is non-decreasing on the interval [ Kw Rw , ] , and then strictly decreasing on the interval [ Rw , | w | ] ; in particular,

$$C _ { w } ( i + 1 ) = C _ { w } ( i ) - 1 \text{ \ for } i \in [ R _ { w }, | w | ].$$

Moreover, by the hypothesis | w | = Rw + Kw + |A| 2, it is easy to see that the maximal value of the complexity is Cw ( Rw ) = | w | -Rw + 1 = Kw + |A| 1. But since Kw &lt; Rw , we have Cw Kw ( ) ≥ Kw + |A| 1, and therefore, Cw ( Rw ) = Cw Kw ( ) = |A| + Kw -1. Using a similar argument to that used in the previous case, it follows that Cw i ( ) = |A| + i -1 for i ∈ [ 1, Kw ] .

( ⇐ ): To prove the converse statement, let us first suppose that Kw &lt; Rw . Then by assumption, Cw i ( ) = |A| + i -1 for i ∈ [ 1, Kw ] , and so Cw Kw ( ) = |A| + Kw -1. Moreover, since Cw i ( + ) = 1 Cw i ( ) for i ∈ [ Kw Rw , -1 , it follows that ] Cw Kw ( ) = Cw ( Rw ) . Furthermore, by the condition Cw i ( + ) = 1 Cw i ( ) -1 for i ∈ [ Rw , | w | ] , we have Cw ( Rw ) = | w | -( Rw -1 ) = | w | -Rw + 1. Hence, | w | -Rw + 1 = Kw + |A| 1, i.e., | w | = Rw + Kw + |A| 2. On the other hand, if we suppose now that Kw ≥ Rw , we easily deduce from the hypothesis that Cw ( Rw ) = Rw + |A| 1 = Cw Kw ( ) = | w | -Kw + 1, and therefore | w | = Rw + Kw + |A| 2. /square

Corollary 6. Suppose w is a non-empty finite word. If | w | = Rw + Kw + | Alph w ( ) | -2 , then w is a GT-word.

Proof. In the case when | Alph ( w ) | ≥ 2, the result follows immediately from Theorem 5. It remains to consider the case when | Alph ( w ) | = 1. Any such word has length equal to Rw + Kw + | Alph ( w ) | -2 where Rw = 1 and Kw = | w | , and clearly all such words are GT-words since the graphs of their complexity functions, being constant, satisfy the trapezoidal property (see Remark 2). /square

It should be noted here that we are using a slightly different convention for Rw compared to [4]; in that paper, a power of a letter had Rw = 0, not 1, since the empty word was considered to be a factor that is not right special in such a word. However, our convention (defining Rw to be the smallest positive integer such that w does not have a right special factor of length Rw ) allows us to view single-letter words as GT-words satisfying the RK-condition.

Let w be a finite word with Alph ( w ) : = A |A| ≥ , 2. A factor u of w is said to be right-extendable if there exists a letter x ∈ A such that ux is a factor of w and u is said to have right-valence j ≥ 0 if u is right-extendable in w by j distinct letters (e.g., see [4]). Left special factors , left-extendable factors , and left-valences are all similarly defined. A factor of w is said to be bispecial if it is both left and right special. Clearly, any left (resp. right) special factor has left (resp. right) valence at least 2. In the case when |A| = 2, left and right special factors have valences equal to 2 since any factor of a word is only extendable to the left or right in at most two different ways.

For the subset of GT-words satisfying the RK-condition, we have the following consequence of Theorem 5 and Proposition 4.

Proposition 7. Suppose w is a finite word with | Alph w ( ) | ≥ 2 . Then | w | = Rw + Kw + | Alph w ( ) | -2 if and only if there exists exactly one right special factor of w of length i for every (non-negative) integer i &lt; Rw and each non-empty right special factor of w has right-valence 2 .

Proof. ( ⇒ ): Let | w | = Rw + Kw + | Alph ( w ) | -2, m = min { Rw Kw , } , and M = min { Rw Kw , } . Suppose w contains two distinct right special factors of the same length i for some i &lt; Rw . If i &lt; m , then since each factor of w of length less than m is right-extendable in w , we would have Cw i ( + ) 1 -Cw i ( ) &gt; 1, contradicting the fact that Cw n ( + ) 1 -Cw n ( ) = 1 for each n ∈ [ 1, m -1 ] by Theorem 5. On the other hand, if m ≤ i &lt; Rw (in which case m = Kw and M = Rw ), then there being two distinct right special factors of length i implies that Cw i ( + ) 1 -Cw i ( ) ≥ 1. Indeed, since all factors of length i of w , except the suffix of w of length i , are right-extendable in w , the two different right special factors of length i would increase the complexity of w by at least 1 when going from factors of length i to factors of length i + 1. But this contradicts that fact that Cw must be constant on the interval [ Kw , Rw ] by Theorem 5. So w contains exactly one right special factor of each length i &lt; Rw . Furthermore, using similar reasoning as above, we deduce that all non-empty right special factors of w must have right-valence 2.

( ⇐ :) Conversely, if w contains exactly one right special of each length i &lt; Rw with each non-empty right special factor having right-valence 2, then using Proposition 4, we deduce that Cw must satisfy the conditions in Theorem 5, and hence | w | = Rw + Kw + | Alph ( w ) | -2. /square

/negationslash

Recall that binary trapezoidal words are precisely those that satisfy | w | = Rw + Kw (see [3, 4]), so Proposition 7 (above) applies to all binary trapezoidal words, but it is not true in general for all GTwords w with | Alph ( w ) | &gt; 2 (only those that satisfy the RK-condition). For instance, the GT-word w = abbac does not satisfy the RK-condition (since Rw = 2, Kw = 1, and Rw + Kw + | Alph ( w ) | -2 = 4 = | w | ) and it has two different right special factors of length 1 (namely the letters a and b ). We also note that GT-words that do not satisfy the RK-condition can also contain right special factors with right-valences greater than 2 (and also left special factors with left-valences greater than 2). For example, in the GT-word u = ababadac (which does not satisfy the RK-condition), the letter a is a right special factor with right-valence 3. The letters b and d are each right-extendable only by the letter a in u , whereas the letter c is not right-extendable as a factor of u , so there is only a jump of 1 between Cu ( 1 ) = 4 and Cu ( 2 ) = 5.

As introduced by de Luca [4], one can define two parameters, Lw and Hw , analogous to Rw and Kw , when considering left factors instead of right factors. Specifically, for a given finite word w with | Alph ( w ) | ≥ 2, Lw is defined to be the smallest positive integer /lscript such that w has no left special factor of length /lscript and Hw is the shortest unrepeated prefix of w . In [4, Proposition 4.6], de Luca proved that any finite word w satisfies | w | ≥ Rw + Kw and also | w | ≥ Lw + Hw . Moreover, Cw ( Rw ) = Cw ( Lw ) and max { Rw Kw , } = max { Lw , Hw } [4, Corollary 4.1].

Using the dual of Proposition 4, in which Rw is replaced by Lw and Kw is replaced by Hw (see [4]), we can prove (in a symmetric way) the corresponding dual of Theorem 5, and subsequently we have the following dual of Proposition 7.

Proposition 8. Suppose w is a finite word with | Alph w ( ) | ≥ 2 . Then | w | = Lw + Hw + | Alph w ( ) | -2 if and only if there exists exactly one left special factor of w of length i for every (non-negative) integer i &lt; Lw and each non-empty left special factor of w has left-valence 2 . /square

The following useful result of de Luca [4] concerns the structure of right and left special factors of maximal length of a given word w with respect to the parameters Rw , Kw , Lw , and Hw .

Proposition 9. [4, Proposition 4.5] Suppose w is a word and u is a right (left) special factor of w of maximal length. Then u is either a prefix (suffix) of w or bispecial. If Rw &gt; Hw (Lw &gt; Kw), then u is bispecial.

The next result is a refinement of [4, Proposition 4.6].

Proposition 10. Suppose w is a non-empty finite word. Then

$$| w | \geq R _ { w } + K _ { w } + | A l p h ( w ) | - 2 \ \ a n d \ \ | w | \geq L _ { w } + H _ { w } + | A l p h ( w ) | - 2.$$

Proof. We will prove only the first inequality since the second one is proved by a symmetric argument. If | Alph ( w ) | = 1, then Rw = 1 and Kw = | w | , so | w | = Rw + Kw + | Alph ( w ) | -2. Now suppose that | Alph ( w ) | ≥ 2 and let m = min { Rw Kw , } , M = max { Rw Kw , } . Since Cw ( 1 ) = | Alph ( w ) | , it follows from Proposition 4 that Cw i ( ) ≥ | Alph ( w ) | + i -1 for i = 1, 2, . . . , m , and so Cw m ( ) ≥ | Alph ( w ) | + m -1. Moreover, since Cw i ( + ) 1 ≥ Cw i ( ) for all integers i ∈ [ m M , -1 , ] we have Cw ( M ) ≥ Cw m ( ) . Furthermore, by Proposition 4, we have Cw i ( + ) = 1 Cw i ( ) -1 for all integers i ∈ [ M w , | | ] , and therefore Cw ( M ) = | w | -( M -1 ) = | w | -M + 1. Hence

$$\text{cores} \, & \mathcal { C } _ { w } \, \mathcal { U } _ { J } - \mathcal { U } _ { J } - \mathcal { U } _ { J } - \mathcal { U } _ { J } - \mathcal { U } _ { J } \, \mathcal { T } \\ | w | & = C _ { w } ( M ) + M - 1 \\ & \geq C _ { w } ( m ) + M - 1 \\ & \geq | \text{Alph} ( w ) | + m - 1 + M - 1 \\ & = | \text{Alph} ( w ) | + m + M - 2 \\ & = | \text{Alph} ( w ) | + R _ { w } + K _ { w } - 2.$$

/square

Let | w x | denote the number of occurrences of a letter x in a non-empty finite word w .

Definition 11 (Heart) . Let w be a non-empty finite word. Suppose that r is the longest (possibly empty) prefix of w such that | w x | = 1 for all x ∈ Alph ( r ) and that s is the longest (possibly empty) suffix of w such that | w x | = 1 for all x ∈ Alph ( s ) . If | w | &gt; | Alph ( w ) | , then there exists a unique (non-empty) word v with | v | &lt; | w | such that w = rvs and we call v the heart of w . Otherwise, if | w | = | Alph ( w ) | , then r = s = w and we define the heart of w to be itself.

Note. Roughly speaking, for any finite word w with | w | &gt; | Alph ( w ) | (i.e., for any finite word w that contains at least two occurrences of some letter), the heart of w is defined to be the unique (nonempty) factor of w that remains if we delete the longest prefix and the longest suffix of w that contain letters only occurring once in w .

Equivalently, the heart of a non-empty finite word w is the unique (non-empty) factor v of w such that w = rvs where rv is the longest prefix of w such that Krv &gt; 1 and vs is the longest suffix of w such that Hvs &gt; 1, i.e., ˜ vs is the longest prefix of ˜ w such that Kvs ˜ &gt; 1 (where ˜ u denotes the reversal of a given word u ).

Example 12. Consider the word w = ebbacbadf . By deleting from w the longest prefix and the longest suffix that contain letters only occurring once in w , we determine that the heart of w is v = bbacba . We also observe that w can be expressed as w = rvs with r = e , s = df , and where rv = ebbacba is the longest prefix of w such that Krv &gt; 1 and vs = bbacbadf is the longest suffix of w such that Hvs &gt; 1. Note that the word w is a generalized trapezoidal word with Rw = 3 and Kw = 1, and we see that | w | = Rv + Kv + | Alph ( w ) | -2 (where Rv = 2 and Kv = 3); in fact, this condition characterizes GT-words (see Theorem 17 in the next section).

Remark 13. All binary trapezoidal words are equal to their own hearts, except those of the form a n b or ab n where a, b are distinct letters and n &gt; 1 is an integer. Such (binary) trapezoidal words have hearts of the form x n for some letter x ∈ { a b , } . We also note that any word w with | w | = | Alph w ( ) | , i.e., any word w that is a product of mutually distinct letters, is a GT-word (such a word w has Rw = 1 and Kw = 1 and therefore satisfies the RK-condition).

The next result generalizes [4, Proposition 4.8].

Proposition 14. Let w be a non-empty finite word with heart v. If | w | = Rv + Kv + | Alph w ( ) | -2 , then

$$\min \{ R _ { v }, K _ { v } \} = \min \{ L _ { v }, H _ { v } \} \ \ a n d \ \ | w | = L _ { v } + H _ { v } + | A l p h ( w ) | - 2.$$

Proof. We first observe that if | w | = Rv + Kv + | Alph ( w ) | -2, then | v | = Rv + Kv + | Alph ( v ) | -2 because, by definition of the heart v of w , | w | - | v | = | Alph ( w ) | - | Alph ( v ) | , i.e., | v | = | w | -| Alph ( w ) | + | Alph ( v ) | . The result is trivial if | Alph ( v ) | = 1 because, in this case, Rv = Lv = 1 and Kv = Hv = | v | . So we will henceforth assume that | Alph ( v ) | ≥ 2.

By [4, Corollary 4.1], Cv ( Rv ) = Cv ( Lv ) and max { Rv , Kv } = max { Lv , Hv } . Hence, since any finite word v satisfies | v | ≥ Lv + Hv + | Alph ( v ) | -2 (by Proposition 10), we deduce that min { Lv , Hv } ≤ min { Rv , Kv } . Indeed, we have

$$\dots \dots ( \cdots v, \cdots v _ { 1 } ) \cdots \dots \dots \dots \\ | v | & = R _ { v } + K _ { v } + | \text{Alph} ( v ) | - 2 \\ & = \min \{ R _ { v }, K _ { v } \} + \max \{ R _ { v }, K _ { v } \} + | \text{Alph} ( v ) | - 2 \\ & = \min \{ R _ { v }, K _ { v } \} + \max \{ L _ { v }, H _ { v } \} + | \text{Alph} ( v ) | - 2 \\ & \geq L _ { v } + H _ { v } + | \text{Alph} ( v ) | - 2 \\ \tau \cup \cdots \dots \cdots \tau n \quad \nu \ \, \cdots$$

and thus min { Lv , Hv } ≤ min { Rv , Kv } .

Suppose that Lv ≤ Hv . Then, by [4, Corollary 4.1], Hv = max { Rv , Kv } , and thus, since min { Lv , Hv } ≤ min { Rv , Kv } , we have Lv ≤ min { Rv , Kv } . Furthermore, since Lv ≤ Hv , it follows from Theorem 5 and the dual statement of Proposition 4 (with Lv and Hv instead of Rv and Kv ) that Cv ( Lv ) = Cv ( Hv ) = Cv ( Rv ) = Cv ( Kv ) = min { Rv , Kv } + | Alph ( v ) | -1. This implies that min { Rv , Kv } ≤ Lv ≤ max { Rv , Kv } because Cv ( ) i ≥ | Alph ( v ) | + i -1 for i = 1, 2, . . . , min { Rv , Kv } . But, as deduced above, Lv ≤ min { Rv , Kv } ; thus we must have Lv = min { Rv , Kv } , and hence min { Lv , Hv } = min { Rv , Kv } .

Let us now suppose that Hv &lt; Lv = max { Lv , Hv } (= max { Rv , Kv } ) . Then, since min { Lv , Hv } ≤ min { Rv , Kv } , we have Hv ≤ min { Rv , Kv } . We wish to show that Hv = min { Rv , Kv } . Suppose not, i.e., suppose Hv &lt; min { Rv , Kv } . Let m = min { Rv , Kv } . Since v is a (generalized trapezoidal) word satisfying the RK-condition, it follows from Proposition 7 that there exists exactly one right special factor of v of length i for every non-negative integer i &lt; m , with each right special factor having right-valence 2. Likewise, there must exist exactly one left special factor of v of length i for every non-negative integer i &lt; m (where Hv &lt; m ≤ Lv ), with each left special factor having left-valence 2. But this implies that Cv ( m ) = Cv ( m -1 , contradicting the fact that the complexity function of ) v satisfies Cv ( m ) = Cv ( m -1 ) + 1 by Theorem 5. Hence we must have Hv = min { Rv , Kv } .

Finally, since we have min { Lv , Hv } = min { Rv , Kv } and also max { Lv , Hv } = max { Rv , Kv } , it easily follows that | v | = Lv + Hv + | Alph ( v ) | -2, and hence | w | = Lv + Hv + | Alph ( w ) | -2. /square

We have the following easy consequence of Proposition 14.

Corollary 15. Let w be a non-empty finite word with heart v. Then | w | = Rv + Kv + | Alph w ( ) | -2 if and only if | w | = Lv + Hv + | Alph w ( ) | -2 . /square

/negationslash

Note. If a word w satisfies the RK -condition | w | = Rw + Kw + | Alph ( w ) | -2 (with Rw and Kw instead of Rv and Kv ), it is not necessarily true that | w | = Lw + Hw + | Alph ( w ) | -2 (and vice versa). For example, the word u = abbcc of length | u | = 5 is a GT-word with complexity sequence { Cu ( n ) } n ≥ 0 = 1, 3, 4, 3, 2, 1. This GT-word has Ru = 2, Ku = 2, and Ru + Ku + 1 = | u | . On the other hand, Lu = 2, Hu = 1, and Lu + Ku + 1 = | u | . However, we see that | u | = Rv + Kv + 1 and | u | = Lv + Hv + 1 where v = bbcc is the heart of u with Rv = Lv = Kv = Hv = 2.

In [4, Corollary 5.3], de Luca proved that the minimal period length π w of any finite word w satisfies π w ≥ Rw + 1, and moreover, if π w = Rw + 1, then | w | = Rw + Kw . The following proposition gives a refinement of that result.

Proposition 16. Suppose w is a non-empty finite word with minimal period length π w. Then π w ≥ Rw + | Alph w ( ) | -1 . Moreover, if π w = Rw + | Alph w ( ) | -1 , then | w | = Rw + Kw + | Alph w ( ) | -2 .

Proof. For any finite word w with minimal period length π w , we have π w ≥ | w | -Kw + 1 [4, Proposition 5.1], and by Proposition 10, Rw ≤ | w | -Kw -| Alph ( w ) | + 2. Hence π w ≥ Rw + | Alph ( w ) | -1. Furthermore, if π w = Rw + | Alph ( w ) | -1, then it follows from [4, Proposition 5.1] that | w | ≤ Rw + Kw + | Alph ( w ) | -2, and therefore | w | = Rw + Kw + | Alph ( w ) | -2 by Proposition 10. /square

We are now ready to prove our main results about GT-words.

## 3. MAIN RESULTS

## 3.1. Characterizations of GT-words.

Theorem 17. Suppose w is a non-empty finite word with heart v. Then w is a GT-word if and only if | w | = Rv + Kv + | Alph w ( ) | -2 .

Example 18. The GT-word w = ababadac does not satisfy the RK -condition, but it does satisfy the following condition in terms of its heart v :

$$| w | = R _ { v } + K _ { v } + | \text{Alph} ( w ) | - 2.$$

Indeed, v = ababada with Rv = 4, Kv = 2, and | w | = 4 + 2 + 2 = 8.

The following lemma is needed for the proof of Theorem 17.

Lemma 19. Suppose w is a non-empty finite word with heart v. Then w is a GT-word if and only if v is a GT-word. Moreover, when w (or equivalently v) is a GT-word, the maximal interval [ mw Mw , ] on which Cw is constant is equal to the maximal interval [ mv , Mv ] on which Cv is constant, i.e., mw = mv and Mw = Mv.

/negationslash

/negationslash

Proof. If v = w , we are done. So suppose v = w . Then | w | &gt; | Alph ( w ) | ≥ 2 and we have w = rvs where r and s are maximal such that | w x | = 1 for all x ∈ Alph ( r ) ∪ Alph ( s ) . We distinguish three cases: w = vs (where s is non-empty), w = rv (where r is non-empty), or w = rvs (where both r and s are non-empty). The latter two cases (when w = rv or w = rvs ) are proved similarly to the first case (when w = vs ), so we consider only that case. By definition of v and s , there exist distinct letters a 1 , . . . , aj ∈ Alph ( v ) such that s = a 1 · · · aj (i.e., w = va 1 · · · aj ) where j = | w | - | v | . Hence, Cw i ( ) = Cv ( ) + i j for i = 1, 2, . . . , | v | .

Now suppose w is a GT-word. Let [ mw Mw , ] be the maximal interval on which Cw is constant and let [ mv , Mv ] be the maximal interval on which Cv is constant. Then since Cv ( ) i = Cw i ( ) -j for i = 1, 2, . . . , | v | , we see that Cv increases by 1 with each n in the interval [ 1, mw ] , is constant on the interval

[ mw Mw , ] , and decreases by 1 with each n in the interval [ Mw , | v | ] . So v is a GT-word, and moreover mv = mw and Mv = Mw .

Conversely, suppose v is a GT-word. Then since Cw i ( ) = Cv ( ) + i j for i = 1, 2, . . . , | v | , we see that Cw increases by 1 with each n in the interval [ 1, mv ] , is constant on the interval [ mv , Mv ] , and decreases by 1 with each n in the interval [ Mv , | v | ] . Moreover, by Proposition 4, Cw must continue to decrease by 1 with each n in the interval [ | v | + 1, | w | ] . Thus, w is a GT-word and mw = mv , Mw = Mv . /square

Proof of Theorem 17. ( ⇐ ): First suppose that | w | = Rv + Kv + | Alph ( w ) | -2 where v is the heart of w . By definition of v , | w | - | v | = | Alph ( w ) | - | Alph ( v ) | , so | v | = Rv + Kv + | Alph ( v ) | -2. Hence, v is a GT-word by Corollary 6, and therefore w is also a GT-word by Lemma 19.

( ⇒ ): Conversely, suppose w is a GT-word. If | w | = | Alph ( w ) | (i.e., if w is a product of mutually distinct letters), then w = v (by Definition 11) and such a GT-word has Rv = Rw = 1 and Kv = Rw = 1; whence | w | = | v | = Rv + Kv + | Alph ( w ) | -2. So we will henceforth assume that | w | &gt; | Alph ( w ) | , in which case Kv &gt; 1.

Since w is a GT-word, so too is v by Lemma 19. It suffices to show that | v | = Rv + Kv + | Alph ( v ) | -2 because it follows from this equality that | w | = Rv + Kv + | Alph ( w ) | -2 by noting that | w | - | v | = | Alph ( w ) | - | Alph ( v ) | .

/negationslash

/negationslash

If | Alph ( v ) | = 1, then Rv = 1 and Kv = | v | , and hence | v | = Rv + Kv + | Alph ( v ) | -2. Now suppose that | Alph ( v ) | ≥ 2 and let [ mv , Mv ] denote the maximal interval on which Cv is constant. If Rv &lt; Kv , then by Proposition 4 (and the fact that v is a GT-word), the complexity Cv of v satisfies the conditions of Theorem 5 with m = mv = Rv and M = Mv = Kv ; whence | v | = Rv + Kv + | Alph ( v ) | -2. On the other hand, if Rv ≥ Kv , then Mv = Rv (by Proposition 4 again) and we claim that mv = Kv . Suppose not, i.e., suppose that mv = Kv . If mv &lt; Kv then Cv ( mv ) = Cv ( mv + ) 1 . But since each factor of v of length mv is right-extendable in v , this implies that v has no right special factor of length mv ; a contradiction (since mv &lt; Kv ≤ Rv ). Now suppose mv &gt; Kv . Then we have Cv ( Kv + ) = 1 Cv ( Kv ) + 1. Let s denote the suffix of v of length Kv . Since all factors of v of length Kv except s are right-extendable in v , the equality Cv ( Kv + ) = 1 Cv ( Kv ) + 1 implies that v contains either two different right special factors of length Kv , each with right-valence 2, or only one right special factor of length Kv with right-valence 3. But then so too would any GT-word w ′ with heart v and Kw ′ = 1 (e.g., w ′ = vx where x ∈ Alph ( v ) ). And since s is right-extendable in any such w ′ , it follows that Cw ′ ( Kv + ) = 1 Cw ′ ( Kv ) + 2; a contradiction. Thus mv = Kv , and so by Proposition 4 (and the fact that v is a GT-word), the complexity Cv of v satisfies the conditions of Theorem 5 with m = mv = Kv and M = Mv = Rv . Hence | v | = Rv + Kv + | Alph ( v ) | -2. /square

In view of Corollary 15, we have the following straightforward consequence of Theorem 17.

Corollary 20. Suppose w is a non-empty finite word with heart v. Then w is a GT-word if and only if | w | = Lv + Hv + | Alph w ( ) | -2 . /square

The next result describes the generalized trapezoidal words w that are 'triangular' in the sense that the graphs of their factor complexity functions are triangles on the interval [ 1, | w | - |A| + ] 1 where A = Alph ( w ) .

Theorem 21. Let w be a finite word with | Alph w ( ) | ≥ 2 and suppose v is the heart of w. Then the graph of the factor complexity Cw ( n ) of w as a function of n ( 0 ≤ n ≤ | w | ) is a triangle on the interval [ 1, | w | - | Alph w ( ) | + ] 1 if and only if Kv = Rv.

Proof. ( ⇐ ): If Kv = Rv , then the graph of the factor complexity function Cv of v is clearly a triangle on the interval [ 1, | v | - | Alph ( v ) | + ] 1 by Proposition 4. Hence, by Lemma 19, the graph of Cw is a triangle on the interval [ 1, | w | - | Alph ( w ) | + ] 1 .

( ⇒ ): Suppose the graph of Cw is a triangle on the interval [ 1, | w | - | Alph ( w ) | + ] 1 . More precisely, suppose Cw increases by 1 with each n in the interval [ 1, m ] and decreases by 1 with each n in the interval [ m w , | | - | Alph ( w ) | + ] 1 for some positive integer m .

Let us first consider the case Rv ≥ Kv . By Proposition 4, Cv increases by 1 with each n in the interval [ 1, Kv ] , is non-decreasing on the interval [ Kv , Rv ] , and decreases by 1 with each n in the interval [ Rv , | v | ] . But by Lemma 19, since the graph of Cw is a triangle, so too is the graph of Cv ; in particular, Cv increases by 1 with each n in the interval [ 1, m ] and decreases by 1 with each n in the interval [ m w , | | - | Alph ( w ) | + ] 1 where m is the same as above. Hence m = Kv = Rv . Similarly, when considering the case Rv ≤ Kv , we deduce that m = Kv = Rv . /square

We end this section by noting that the set of all GT-words is factorial (i.e., closed by taking factors) and is also closed under reversal.

Proposition 22. The set of all GT-words is closed by factors.

/negationslash

/negationslash

Proof. Let w be a GT-word. If | Alph ( w ) | = 1, then clearly all of its factors are GT-words too (see Remark 2). So let us now assume that | Alph ( w ) | ≥ 2. By Lemma 19, it suffices to consider the heart v of w . Suppose, by way of contradiction, that there exists a factor u of v (and hence w ) that is not a GTword. Then the heart v ′ of u is not a GT-word (by Lemma 19 again), so | v ′ | = Rv ′ + Kv ′ + | Alph ( v ′ ) | -2 by Theorem 17 . Hence, by Proposition 7, v ′ contains two different right special factors of the same length or a right special factor with right-valence greater than 2. But then the same would be true for the heart v of w , and therefore | v | = Rv + Kv + | Alph ( v ) | -2 by Proposition 7, contradicting the fact that v is a GT-word (by Theorem 17). /square

Proposition 23. A finite word w is a GT-word if and only if w is a GT-word. ˜ Proof. The result follows immediately from the definition of a GT-word (Definition 1) by observing that, for any word w , its reversal w has the same complexity as w . /square

/negationslash

˜ Example 24. The word abbcc and its reversal are both GT-words with complexity sequence { C n ( ) } n ≥ 0 = 1, 3, 4, 3, 2, 1. We note, however, that abbcc satisfies the RK-condition, but its reversal ccbba does not because it has K = 1, R = 2, and R + K + 1 = 5. So the set of all words satisfying the RK-condition is not closed under reversal, whereas the set of all GT-words is closed under this involution.

3.2. Palindromically-Rich GT-words. In the case when |A| = 2, the first author, together with de Luca and Zamboni [5], have shown that the set of all palindromic (binary) trapezoidal words coincides with the set of all Sturmian palindromes. Moreover, if w is a (binary) trapezoidal word, then w contains exactly | w | + 1 distinct palindromes (including the empty word ε ). That is, (binary) trapezoidal words (and hence finite Sturmian words) are rich in palindromes in the sense that they contain the maximum possible number of distinct palindromic factors since, as shown in [6], a finite word of length n contains at most n + 1 distinct palindromic factors (including ε ). More precisely, a finite word w is said to be rich if and only if it has | w | + 1 distinct palindromic factors, and an infinite word is rich if all of its factors are rich [8]. So, roughly speaking, a finite or infinite word is rich if and only if a new palindrome is introduced at each position in the word (see Proposition 26 below).

The family of rich words was studied in depth by the first author and others in [8]. Such words were also independently considered in 2004 by Brlek, Hamel, Nivat, and Reutenauer [1] who called them

full words . Amongst various properties of rich words, we have the following characterization in terms of so-called complete returns . Let u be a non-empty factor of a finite or infinite word w . A factor of w having exactly two occurrences of u , one as a prefix and one as a suffix, is called a complete return to u in w .

Proposition 25. [8] A finite or infinite word w is rich if and only if, for each non-empty palindromic factor u of w, every complete return to u in w is a palindrome.

In short, w is rich if and only if all complete returns to palindromes are palindromes in w . We also have the following characterization of rich words that will be useful in what follows. Note that a factor u of a word w is said to be unioccurrent in w if u has exactly one occurrence in w .

Proposition 26. [6, Proposition 3] A word w is rich if and only if all of its prefixes have a unioccurrent palindromic suffix (called a ups for short). Similarly, w is rich if and only if all of its suffixes have a unioccurrent palindromic prefix.

Note. The ups of a rich word w is necessarily the longest palindromic suffix of w .

Whilst it is true that all binary trapezoidal words are rich [5], the converse does not hold; for example, the binary word aabbaa is rich, but not trapezoidal because its complexity jumps by 2 from C ( 1 ) = 2 to C ( 2 ) = 4. Moreover, unlike in the binary case, not all generalized trapezoidal words are rich. For instance, the word aabca is a non-rich GT-word. However, it is easy to see, for instance, that all GTwords w with | Alph ( w ) | = 3 and Kw = 1 are rich since any such word is simply a binary GT-word (which is rich) followed by a new letter (its ups). More generally, our next result describes all the rich GT-words.

Theorem 27. Let w be a GT-word and suppose that its heart v has longest palindromic prefix p and longest palindromic suffix q. Then w is rich if and only if one of the following conditions is satisfied.

- (i) p and q are unseparated in v (i.e., either v = pq, v = p = q, or p and q overlap in v).

/negationslash

- (ii) v = pxq where Alph ( p ) ∩ Alph q ( ) = ∅ and x ∈ Alph p ( ) ∪ Alph q . ( )
- (iii) v = puq where Alph ( p ) ∩ Alph q ( ) = ∅ and u = u Zu 1 2 where u , u , Z are words (at least one of 1 2 which is non-empty) such that Alph ( u 1 ) ⊆ Alph ( p , Alph ) ( u 2 ) ⊆ Alph q , and Z contains no letters ( ) in common with p and q.

## Examples

- /trianglerightsld Rich GT-word: abacabade has complexity sequence { C n ( ) } n ≥ 0 = 1, 5, 6, 6, 6, 5, 4, 3, 2, 1 with heart v = p = q = abacaba (a palindrome).
- /trianglerightsld Rich GT-word: ababadac has complexity sequence { C n ( ) } n ≥ 0 = 1, 4, 5, 5, 5, 4, 3, 2, 1 with heart v = ababada , p = ababa , and q = ada ( p and q overlap).
- /trianglerightsld Rich GT-word: aaabab has complexity sequence { C n ( ) } n ≥ 0 = 1, 2, 3, 4, 3, 2, 1 with heart v = pq where p = aaa and q = bab ( v is a product of p and q ).
- /trianglerightsld Rich GT-word: bacabacac has complexity sequence { C n ( ) } n ≥ 0 = 1, 3, 4, 5, 5, 5, 4, 3, 2, 1 with heart v = paq where p = bacab and q = cac . Here Alph ( q ) ⊂ Alph ( p ) and p , q are separated by a letter in Alph ( p ) .
- /trianglerightsld Rich GT-word: acacbcb has complexity sequence { C n ( ) } n ≥ 0 = 1, 3, 4, 5, 4, 3, 2, 1 with heart v = pcq where p = aca and q = bcb . Here | Alph ( p ) ∪ Alph ( q ) | &gt; | Alph ( p ) ∩ Alph ( q ) | ≥ 1 and p , q are separated by a letter in Alph ( p ) ∩ Alph ( q ) .

- /trianglerightsld Rich GT-word: aabcc has complexity sequence { C n ( ) } n ≥ 0 = 1, 3, 4, 3, 2, 1 with heart v = puq where p = aa , u = b , and q = cc . Here Alph ( p ) ∩ Alph ( q ) = ∅ and p , q are separated by a letter not in Alph ( p ) ∪ Alph ( q ) .
- /trianglerightsld Rich GT-word: aaadcbcb has complexity sequence { C n ( ) } n ≥ 0 = 1, 4, 5, 6, 5, 4, 3, 2, 1 with heart v = puq where p = aaa , u = dc , and q = bcb . Here Alph ( p ) ∩ Alph ( q ) = ∅ and p , q are separated by the word dc where the letter d is not in Alph ( p ) ∪ Alph ( q ) and c ∈ Alph ( q ) .
- /trianglerightsld Non-Rich GT-word: ababadbc has complexity sequence { C n ( ) } n ≥ 0 = 1, 4, 5, 5, 5, 4, 3, 2, 1 with heart v = pdq where p = ababa and q = b . Here Alph ( q ) ⊂ Alph ( p ) and p , q are separated by a letter not in Alph ( p ) . Note that v ends with a non-palindromic complete return to b .
- /trianglerightsld Non-Rich GT-word: abacbab has complexity sequence { C n ( ) } n ≥ 0 = 1, 3, 4, 5, 4, 3, 2, 1 with heart v = pcq where p = aba and q = bab . Here Alph ( p ) = Alph ( q ) and p , q are separated by a letter that they do not contain. Note that v contains non-palindromic complete returns to each of the letters a and b .
- /trianglerightsld Non-Rich GT-word: dcdbacdc has complexity sequence { C n ( ) } n ≥ 0 = 1, 4, 5, 6, 5, 4, 3, 2, 1 with heart v = puq where p = dcd , u = ba , and q = cdc . Here Alph ( p ) = Alph ( q ) and p , q are separated by a product of two distinct letters, neither of which they contain themselves. Note that v contains non-palindromic complete returns to each of the letters c and d .
- /trianglerightsld Non-Rich GT-word: aaaaaadebcad has complexity sequence { C n ( ) } n ≥ 0 = 1, 5, 6, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1 with heart v = puq where p = aaaaaa , u = debca , q = d . Here Alph ( p ) ∩ Alph ( q ) = ∅ and p , q are separated by a product of mutually distinct letters, with last letter in Alph ( p ) and first letter in Alph ( q ) . Note that v begins with a nonpalindromic complete return to a and also ends with a non-palindromic complete return to d .
- /trianglerightsld Non-Rich GT-word: abcedabceded has complexity sequence { C n ( ) } n ≥ 0 = 1, 5, 6, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1 with heart v = puq where p = a , u = bcedabce , q = ded . Here Alph ( p ) ∩ Alph ( q ) = ∅ and p , q are separated by a word containing letters in Alph ( p ) and Alph ( q ) , but beginning with a letter not in Alph ( p ) . Note that v begins with a non-palindromic complete return to the letter a and also contains non-palindromic complete returns to each of the other letters b , c , d , and e .

The proof of Theorem 27 requires several lemmas (Lemmas 30-35, to follow), but first we show that, in the case of a binary alphabet, every trapezoidal word has unseparated p and q . This result allows us to give an alternative proof of the fact that all binary trapezoidal words are rich, originally proved in [5] (see Corollary 29 below).

Proposition 28. Suppose w is a binary trapezoidal word. Then the longest palindromic prefix p and longest palindromic suffix q of w are unseparated in w.

Proof. Let Alph ( w ) = { a b , } . We first observe that if w takes the form x n y or xy n where { x y , } = { a b , } and n ∈ N + , then w is simply a product of its longest palindromic prefix and longest palindromic suffix.

Let us now suppose, on the contrary, that w is a binary trapezoidal word (not of the form x n y or xy n ) of minimal length such that its longest palindromic prefix p and longest palindromic suffix q are separated, i.e., such that w = puq where u is a non-empty word. Clearly, w cannot be a palindrome; otherwise w would itself be its longest palindromic prefix and suffix (i.e., w = p = q ).

/negationslash

We first show that p = q . Suppose not, i.e., suppose w = pup . Then u must be a non-palindromic word because w is not a palindrome. If p has an occurrence in w that is neither a prefix nor a suffix of

/negationslash

/negationslash w , then w would begin with a complete return to p (shorter than w ), which cannot be a palindrome because otherwise w would begin with a palindrome longer than p (its longest palindromic prefix). So w would begin with a non-palindromic complete return to p (shorter than w ) of the form pUp where U is a non-palindromic word. Let s = pUp . Since any factor of w is a (binary) trapezoidal word (by Proposition 22 or [3, Proposition 8]), the proper prefix s = pUp of w is a binary trapezoidal word. But this contradicts the minimality of w as a binary trapezoidal word (of shortest length) having separated longest palindromic prefix and suffix. Therefore p occurs only twice in w , as a prefix and as a suffix. That is, w = pup is itself a non-palindromic complete return to p . If p were a letter, say p = a , then w = aua where Alph ( u ) = { } b (since w is a complete return to p ), which implies that u = b n for some integer n ≥ 1. However, this is not possible because u is not a palindrome. So | p | ≥ 2. If p = aa , then w = aauaa where u begins and ends with the letter b . In this case, the letter a is bispecial, so b cannot be left or right special by Propositions 7 and 8. In particular, bb cannot a factor of u nor can aa because w is a complete return to aa . Hence, we deduce that u = ( ba ) n b for some integer n ≥ 1; a contradiction (since u is not a palindrome). Thus p = aa , and likewise it can be shown that p = bb . Hence | p | ≥ 3. Let us write p = xPx where x ∈ { a b , } and P is a palindrome. Then we have w = xPxuxPx . Let w ′ be the prefix of w obtained from w by removing its last letter x , i.e., w ′ = wx -1 = xPxuxP = puxP and let S = PxuxP so that w ′ = xS and w = w x ′ = xSx . Clearly p = xPx is the longest palindromic prefix of w ′ . Let q ′ denote the longest palindromic suffix of w ′ . By the minimality of w as binary trapezoidal word (of shortest length) having separated longest palindromic prefix and suffix, p and q ′ cannot be separated in w ′ . Hence | uxP | ≤ | q ′ | &lt; | w ′ | . If | q ′ | = | uxP | , then w ′ (and hence w ) begins with the palindrome xPxPx longer than p . Therefore | uxP | &lt; | q ′ | &lt; | w ′ | and the prefix Px of q ′ overlaps with a suffix of the prefix xPx of w ′ . Hence w ′ either begins with the palindrome xPPx (if | q ′ | = | uxP | + 1) or begins with a palindrome Q having xP as a prefix (and Px as a suffix) with | xPx | &lt; | Q | &lt; | 2 P | + 2 (since P , being a palindrome, overlaps with itself in a palindrome). Neither case is possible because p = xPx is the longest palindromic prefix of w ′ . Thus p = q .

We now claim that p and q are both unioccurrent in w . Indeed, if p occurs more than once in w , then w would begin with a complete return to p (shorter than w ), which cannot be a palindrome because otherwise w would begin with a palindrome longer than p (its longest palindromic prefix). So w begins with a non-palindromic complete return to p (shorter than w ) of the form pUp with p being its longest palindromic prefix and suffix. But since pUp is trapezoidal (by Proposition 22 or [3, Proposition 8]), this contradicts the minimality of w as a binary trapezoidal word (of shortest length) having separated longest palindromic prefix and suffix. Likewise, we deduce that q occurs only once (as a suffix) in w . So Hw ≤ | p | and Kw ≤ | q | . Moreover, since w is a binary trapezoidal word, we have | w | = Rw + Kw and | w | = Lw + Hw .

/negationslash

If Rw &gt; Hw , then by Proposition 9, the right special factor r of w of maximal length | r | = Rw -1 is bispecial, so r occurs at least twice in w . In particular, w contains either both ara and brb or both arb and bra . Let P be the shortest prefix of w that contains both arx and bry where { x y , } = { a b , } . Without loss of generality, we may assume that P ends with a factor S of the form S = arxS ′ = S bry ′′ . In particular, S = aEy where E is a complete return to r . Let p ′ (resp. q ′ ) denote the longest palindromic prefix (resp. suffix) of P = P S ′ = P aEy ′ . If | q ′ | &gt; | S | = | aEy | , then P would have a proper prefix containing yEa ˜ , of which yrb ˜ and xra ˜ are factors. So ˜ r would be a bispecial factor of P (and hence of w ) of length | r | , and therefore ˜ r = r by Propositions 7 and 8. Moreover, we deduce that E must be palindromic complete return to (the palindrome) r ; otherwise, reasoning as above, we would reach a contradiction. It follows that y = a and x = b , and so we see that w has a prefix shorter than P that contains both arx = arb and bry = bra , contradicting the minimality of P . Thus | q ′ | ≤ | aEy | . If | ry | &lt; | q ′ | &lt; | aEy | , then E contains yr ˜ , which implies ˜ r = r (since E is a complete return to r ). Furthermore, E cannot contain xr ˜ ; otherwise ˜ r would be a left special factor of length | r | different

/negationslash

/negationslash from r , which is not possible by Proposition 8. So E contains a factor X of the form X = rxX ′ = X yr ′′ ˜ that contains only one occurrence of r (as a prefix) and only one occurrence of ˜ r (as a suffix). Such a factor cannot be a palindrome (since x = y ) and it follows that the longest palindromic prefix and longest palindromic suffix of X each have length less than | r | and therefore they must be the same palindrome, Q say. But then X would be a non-palindromic complete return to Q , contradicting the minimality of w . So either | q ′ | ≤ | ry | or | q ′ | = | S | = | aEy | . In the former case, one can use similar reasoning as above to deduce that p ′ and q ′ are separated in P , again contradicting the minimality of w . In the latter case (when | q ′ | = | S | = | aEy | ), S = aEy is a palindrome, which implies that y = a (and hence x = b ) and that ˜ r = r (i.e., r is a palindrome). So w = P aEaQ ′ ′ where E is a palindromic complete return to r beginning with rb and ending with br . Reasoning as above, we deduce that | p | &lt; | P ar ′ | and | q | &lt; | raQ ′ | (for if not, we reach a contradiction to either the minimality of P or the fact that E is a complete return to r ). Let w ′ denote the prefix of w obtained from w by removing the last letter of w , i.e., let w ′ = wz -1 = P aEaQ z ′ ′ -1 where z is the last letter of w . Then, since | p | &lt; | P ar ′ | , we see that p (the longest palindromic prefix of w ) is also the longest palindromic prefix of w ′ , and using similar arguments as above, we deduce that the longest palindromic suffix q ′′ of w ′ has length | q ′′ | &lt; | raQ ′ | -1. Hence, just as p and q are separated in w , we see that the longest palindromic prefix and longest palindromic suffix of w ′ (namely p and q ′′ ) are separated in w ′ ; a contradiction (yet again) to the minimality of w as a binary trapezoidal word (of shortest length) having separated longest palindromic prefix and suffix. Thus Rw ≤ Hw , and similarly we deduce that Lw ≤ Kw .

If Rw = Hw , then | w | = | p | + | u | + | q | ≥ Rw + | u | + Kw &gt; Rw + Kw (because Rw = Hw ≤ | p | , Kw ≤ | q | , and | u | ≥ 1); a contradiction. So Rw &lt; Hw , and using similar reasoning, we deduce that Lw &lt; Kw too. Hence it follows that Rw = Lw and Kw = Hw since max { Rw Kw , } = max { Lw , Hw } and min { Rw Kw , } = min { Lw , Hw } by [4, Corollary 4.1] and Proposition 14. This implies that | pu | ≤ Rw since | pu | = | w | - | q | where | w | = Rw + Kw and Kw ≤ | | q . However, by Proposition 9, the right special factor r of w of maximal length | r | = Rw -1 is a prefix of w , which occurs at least twice in w , and therefore p (which is a prefix of r since | pu | ≤ Rw = | r | + 1) occurs more than once in w ; a contradiction. Thus p and q are unseparated in w . /square

Corollary 29. All binary trapezoidal words are rich.

Proof. If w is a binary trapezoidal word, but not rich, then w contains a non-palindromic complete return to a palindrome p of the form pup where u is a non-palindromic word. Let r = pup . Clearly p is both the longest palindromic prefix and the longest palindromic suffix of r and these occurrences of p in r are separated. But this yields a contradiction because r , being a factor of w , must be a binary trapezoidal word (by Proposition 22 or [3, Proposition 8]), and therefore its longest palindromic prefix and suffix cannot be separated (by Proposition 28). /square

Lemma 30. A GT-word w is rich if and only if the heart of w is rich.

Proof. Let w be a GT-word. If w is rich, then clearly the heart of w is rich too since any factor of a rich word is rich.

/negationslash

/negationslash

Conversely, suppose that the heart v of w is rich. If v = w , we are done. So suppose that v = w . Then | w | &gt; | Alph ( w ) | ≥ 2 and we have w = rvs where r and s are maximal such that | w x | = 1 for all x ∈ Alph ( r ) ∪ Alph ( s ) . Moreover, since v = w , at least one of the factors r and s is non-empty. If r is non-empty, then | r | = | Alph ( r ) | and it is easy to see that each prefix of r has a unioccurrent palindromic suffix - just the last letter of each prefix. Likewise, if s is non-empty, each prefix of s has a ups. Moreover, since v is rich, each prefix of v has a ups, by Proposition 26. Thus, since the alphabets Alph ( v ) , Alph ( r ) , and Alph ( s ) are mutually disjoint sets, we see that each prefix of w = rvs has a ups, and thus w is rich, by Proposition 26 again. /square

Lemma 31. Let w be a GT-word and suppose that its heart v has longest palindromic prefix p and longest palindromic suffix q. If v = puq for some non-empty word u, then one of the following conditions holds:

- (i) p = ( ax ) n a, u = x, q = ( bx ) m b for some n , m ∈ N + where a, b, and x are mutually distinct letters;
- (ii) Alph ( p ) ⊆ Alph q ( ) or Alph ( q ) ⊆ Alph ( p ; )
- (iii) Alph ( p ) ∩ Alph q ( ) = ∅ .

Moreover, if condition (i) is satisfied, then w is rich.

/negationslash

In other words, the above lemma says that if v is the heart of a GT-word with separated p and q such that the alphabets of p and q are not disjoint and neither alphabet is a subset of the other, then v takes the form given by condition (i). All other hearts of the form v = puq ( u = ε ) are such that the alphabets of p and q are disjoint or one is a subset of the other.

Remark 32. For a given letter x, let ϕ x denote the morphisms defined as follows:

↦

↦

$$\iota \iota \iota _ { x }, \iota \iota _ { x } \, \iota \iota _ { y } \, \iota \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _{ y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \, \iota \iota _ { y } \\ \varphi _ { x } \, \colon & \begin{cases} x \mapsto x \\ y \mapsto y x \end{cases} & \text{for all letters $y \neq x$},$$

/negationslash

/negationslash i.e., ϕ x maps the letter x to itself and inserts the letter x to the right of all other letters different from x. A word v satisfying condition (i) in Lemma 31 can be expressed as v = ϕ x ( a n + 1 b m ) b, i.e., v is obtained from the binary trapezoidal word a n + 1 b m + 1 by inserting the letter x ∈ { a b , } to the right of each letter except the last. The shortest such word takes the form ϕ x ( aab b. )

Proof of Lemma 31. Wefirst observe that, for any word v with longest palindromic prefix p and longest palindromic suffix q , the alphabets of p and q satisfy one of the following three conditions.

/negationslash

- (A) Alph ( p ) ∩ Alph ( q ) = ∅ and neither alphabet is a subset of the other.
- (B) Alph ( p ) ⊆ Alph ( q ) or Alph ( q ) ⊆ Alph ( p ) (i.e., one alphabet is a subset of the other).
- (C) Alph ( p ) ∩ Alph ( q ) = ∅ .

/negationslash

Furthermore, we observe that there exist hearts v of GT-words of the form v = puq ( u = ε ) with p and q satisfying these conditions. For example, the GT-word acacbcb has heart v = acacbcb = puq (itself) where p = aca , u = c , q = bcb with the alphabets of p and q satisfying condition (A). Condition (B) is satisfied, for instance, by the GT-word ababadbc which has heart v = ababadb = puq where p = ababa , u = d , q = b with Alph ( q ) ⊂ Alph ( p ) . We also observe that the reversal of v = ababadb (which is also a GT-word by Proposition 23) is such that the alphabet of its longest palindromic prefix (namely b ) is contained in the alphabet of its longest palindromic suffix (namely ababa ). An example of a heart of a GT-word of the form v = puq satisfying condition (B) with Alph ( p ) = Alph ( q ) is abacbab . And lastly, condition (C) is satisfied, for example, by the GT-word aabcc , which has heart v = aabcc = puq (itself) where p = aa , u = b , q = cc .

Now suppose, more generally, that v is the heart of a GT-word of the form v = puq where u is a non-empty word. Then | Alph ( v ) | ≥ 3. Indeed, if | Alph ( v ) | = 1, then v = x n for some letter x and positive integer n , in which case v = p = q (i.e., p and q are unseparated). And if | Alph ( v ) | = 2 then p and q cannot be separated by a non-empty word in v by Proposition 28. We also note that if | w | = | Alph ( w ) | , then w = v and such a word is simply a product of mutually distinct letters with its first and last letters being its longest palindromic prefix and longest palindromic suffix, respectively, and therefore it satisfies condition (iii) in the statement of the lemma. So we will henceforth assume that | w | &gt; | Alph ( w ) | , in which case the heart v of w satisfies Kv &gt; 1 and Hv &gt; 1. This means, in particular, that each letter in Alph ( v ) is both left and right extendable in v .

/negationslash

/negationslash

We showed above that there exist hearts v of GT-words of the form v = puq ( u = ε ) with p and q satisfying conditions (ii) and (iii) in the statement of the lemma (which correspond to conditions (B) and (C) above). So let us now suppose that v satisfies neither of those two conditions. Then v satisfies condition (A) above, i.e., Alph ( p ) ∩ Alph ( q ) = ∅ and there exist at least two distinct letters a and c such that a ∈ Alph ( p ) \ Alph ( q ) and c ∈ Alph ( q ) \ Alph ( p ) . We now show that p , q , and u must take the form given in condition (i) of the lemma.

/negationslash

/negationslash

/negationslash

/negationslash

Let us first note that the palindrome p (resp. q ) must contain at least two distinct letters - at least one letter in Alph ( p ) ∩ Alph ( q ) and at least one in Alph ( p ) \ Alph ( q ) (resp. Alph ( q ) \ Alph ( p ) ). Hence the palindromes p and q each have length at least three. Now, p contains a letter x ∈ Alph ( q ) such that xa is a factor of v for some letter a ∈ Alph ( p ) \ Alph ( q ) . Since q is a palindrome, the letter x will occur at least twice in q , except if q has odd length and x occurs only once as its central letter. In any case, x will be right-extendable in q by a letter b = a (since a ∈ Alph ( q ) ). So xa and xb are factors of v (where a = x and a = b ), and therefore x is a right special factor of v of length 1. On the other hand, q contains a letter y ∈ Alph ( p ) such that yc is a factor of v for some letter c ∈ Alph ( q ) \ Alph ( p ) . Since p is a palindrome, the letter y will occur at least twice in p , except if p has odd length and y occurs only once as its central letter. In any case, y will be right-extendable in p by a letter d = c (since c ∈ Alph ( p ) ). So yc and yd are factors of v (where c = y and c = d ), and therefore y is a right special factor of v of length 1. We have thus shown that the letters x and y are right special factors of v . But since v is a GT-word (with | v | = Rv + Kv + | Alph ( v ) | -2 by Theorem 17), it contains at most one right special factor of each length (see Proposition 7), and so we must have x = y . Therefore xa , xb , xc , and xd are all factors of v where a = b , c = d , and moreover, a = c since a ∈ Alph ( p ) \ Alph ( q ) and c ∈ Alph ( q ) \ Alph ( p ) . If a = d or b = c , then x would have right-valence at least 3 in v , which is not possible by Proposition 7. (Alternatively, we observe that since each distinct letter in v is right-extendable in v because Kv &gt; 1, the letter x having right-valence at least 3 would imply that Cv ( 2 ) ≥ | Alph ( v ) | + 2, i.e., Cv ( 2 ) ≥ Cv ( 1 ) + 2, contradicting the hypothesis that v is a GT-word.) Hence we must have a = d and b = c . It follows that the only factors of p of length 2 are xa and ax and the only factors of q of length 2 are xb and bx . So we deduce that p takes the form p = ( xa ) n x or p = ( ax ) n a for some n ∈ N + and that q takes the form q = ( xb ) m x or q = ( bx ) m b for some m ∈ N + . Moreover, we note that xa , ax , bx , and xb are the only factors of length 2 of v . Indeed, x must always be preceded or followed by either a or b , otherwise x would have right or left valence greater than 2, and also each of the letters a and b must always be preceded or followed by the letter x in v , otherwise we would have another left or right special factor of length 1 in addition to x (which is bispecial), contradicting the hypothesis that v is a GT-word. So the word u that separates p and q in v = puq cannot contain any letters different from a , b , or x , and any factor of u of length 2 (if | u | ≥ 2) must be one of the words ax , xa , bx , xb .

/negationslash

/negationslash

/negationslash

/negationslash

/negationslash

Wenowseparately consider the two possible forms of each of p and q with respect to the 'separating word' u .

Case 1: p = ( ax ) n a for some n ∈ N + . In this case, if u begins with the letter a , then a would be a right special factor of length 1; a contradiction. So u must begin with the letter x . If u = x , then v satisfies condition (i) in the statement of lemma. Otherwise, if | u | ≥ 2, then u must begin with xa or xb since x must be followed by either a or b in v . But if u begins with xa , then v begins with the palindrome ( ax ) n axa longer than p . Thus u begins with xb .

Case 2: p = ( xa ) n x for some n ∈ N + . In this case, u must begin with the letter a or b since x can only be followed and preceded by one of these letters. If u begins with the the letter a (which must always be followed by the letter x ), then v would begin with the palindrome ( xa ) n xax = ( xa ) n + 1 x longer than p , which is not possible. So u must begin with the letter b . If u = b , then q must begin with x

/negationslash

/negationslash

/negationslash

/negationslash

(not b ), and so q takes the form q = ( xb ) m x for some m ∈ N + , in which case v would end with the palindrome xb xb ( ) m x longer than q . So | u | ≥ 2 and u begins with bx .

Case 3: q = ( bx ) m b for some m ∈ N + . Using similar reasoning as in Case 1, we deduce that either v satisfies condition (i) or that u must end with ax .

Case 4: q = ( xb ) m x for some m ∈ N + . Using similar reasoning as in Case 2, we deduce that u must end with xa .

From the above considerations, we see that either v satisfies condition (i), or u takes one of the following forms:

$$u = x b u ^ { \prime } a x, \ \ u = x b u ^ { \prime } x a, \ \ u = b x u ^ { \prime } a x, \ \ u = b x u ^ { \prime } x a, \ \ \text{or} \ \ u = b x a.$$

But if u takes any of the above forms, we see that v contains the following 6 factors of length 3: axa , xax , axb , bxa , bxb , xbx . This means that the complexity of v jumps by 2 from Cv ( 2 ) = 4 to Cv ( 3 ) = 6, contradicting the hypothesis that v is a GT-word.

Hence we have shown that v must satisfy one of the conditions (i)-(iii).

Lastly, it is easily verified that if v satisfies condition (i), then each prefix of v has a unioccurrent palindromic suffix, and hence v is rich by Proposition 26. Thus w is rich by Lemma 30. /square

Lemma 33. Let w be a GT-word with heart v having longest palindromic prefix p and longest palindromic suffix q. Suppose v = pxq where x is a letter and Alph ( p ) ⊆ Alph q ( ) or Alph ( q ) ⊆ Alph ( p . Then w is rich ) if and only if x ∈ Alph ( p ) ∪ Alph q . ( )

/negationslash

Proof. We first note that | w | &gt; | Alph ( w ) | because if | w | = | Alph ( w ) | , then w = v and v would be a product of mutually distinct letters which does not take the assumed form. Hence Kv &gt; 1 and Hv &gt; 1. It is also easy to see that p = q and | Alph ( v ) | = 1. Furthermore, if | Alph ( v ) | = 2 then p and q cannot be separated by a non-empty word in v (by Proposition 28). Hence | Alph ( v ) | ≥ 3.

/negationslash

/negationslash

/negationslash

( ⇒ ): Suppose w is rich, then v is rich (by Lemma 30). By way of contradiction, let us suppose that x ∈ Alph ( p ) ∪ Alph ( q ) . Without loss of generality, we will assume that Alph ( q ) ⊆ Alph ( p ) . Since p and q contain at least one letter in common, there exists a letter a = x such that p = p ap ′ ′′ and q = q ′′ aq ′ where p ′′ and q ′′ are (possibly empty) words that contain no letters in common. But ap ′′ xq ′′ a is a complete return to a , so it must be a palindrome (since v is rich), which implies that p ′′ = q ′′ = ε . So v = p axaq ′ ′ where p ′ = ˜ q ′ because v is not a palindrome. Moreover, both p ′ and q ′ must be nonempty. Indeed, if p ′ = ε , then v = axaq ′ and we see that v begins with the palindrome axa which is longer than p = a ; a contradiction. Likewise, if q ′ = ε , we reach a contradiction. Now, since both p ′ and q ′ are non-empty, there exists a letter y ∈ Alph ( p ′ ) and a letter z ∈ Alph ( q ′ ) (with y = x and z = x ) such that ya and az are factors of v . But then, since xa and ax are also factors of v , we see that the letter a is a bispecial factor of v of length 1. Moreover, since Kv &gt; 1, each letter in Alph ( v ) is rightextendable in v , and therefore the letter a must always be followed by either x or z in v . For if not, then a would have right-valence greater than 2 in v , which would imply that Cv ( 2 ) ≥ | Alph ( v ) | + 2, i.e., Cv ( 2 ) ≥ Cv ( 1 ) + 2, contradicting the hypothesis that v is a GT-word (also see Proposition 7). Likewise, the letter a can only be preceded by the letter x or y in v by Proposition 8. Since p is a palindrome containing ya , we see that ay is a factor of p . Similarly, since q is a palindrome containing az , we see that za must be a factor of q . We thus deduce that y = z . So the only factors of v of length 2 are za , az , ax , and xa . If z = a , then p = a m and q = a n for some m n , ∈ N + , in which case v = a m xa n , contradicting the hypothesis that the longest palindromic prefix and longest palindromic suffix of v are separated. So z = a and we deduce that p takes the form p = ( az ) m a for some m ∈ N + and q takes the form q = ( az ) n a for some n ∈ N + . But then v = ( az ) m ax ( az ) n a , in which case either v is a

/negationslash

/negationslash

/negationslash

/negationslash

palindrome (if m = n ) or the longest palindromic prefix and longest palindromic suffix of v overlap in v ; a contradiction. Hence x ∈ Alph ( p ) ∪ Alph ( q ) .

/negationslash

( ⇐ ): Conversely, suppose x ∈ Alph ( p ) ∪ Alph ( q ) . We will show that v (and hence w ) is rich by determining the possible forms of p and q in v . Without loss of generality, we will assume that Alph ( q ) ⊆ Alph ( p ) . Then Alph ( p ) = Alph ( v ) , and so p contains at least three distinct letters (since | Alph ( v ) | ≥ 3); in particular, p contains the letter x and at least two other distinct letters a and b (different from x ). We first observe that v cannot contain the square of a letter. Indeed, if yy were a factor of v for some letter y , then y would be a factor of p (since Alph ( p ) = Alph ( q ) ), and therefore y would be preceded and followed by some letter z = y (since | Alph ( p ) | ≥ 3). But then yy would be bispecial and y can only ever be preceded (and followed) by itself and z in v , otherwise y would have left or right valence more than 2, which is impossible by Propositions 7 and 8. Likewise, the letter z can only ever be preceded and followed by the letter y in v , which implies that v is a binary word; a contradiction. So v does not contain the square of a letter. Moreover, using similar arguments as in the proof of Lemma 31 (with the aid of Propositions 7-8 again), we deduce that p (and hence v ) contains only two distinct letters different from x and that p and q must take the following forms:

$$p = [ b ( x a ) ^ { m } x ] ^ { k } b \text{ \ and \ } q = ( a x ) ^ { n } a$$

where a and b are distinct letters (different from x ) and k m n , , ∈ N + with n ≥ m . That is,

$$v = p x q = [ b ( x a ) ^ { m } x ] ^ { k } b ( x a ) ^ { n + 1 }$$

with | v | = | p | + | q | + 1 = Rv + Kv + | Alph ( v ) | -2 where Rv = | p | and Kv = | q | . (Note that when Alph ( p ) ⊆ Alph ( q ) the forms of p and q are opposite to those given above.) It is easy to see that every prefix of any such v has a unioccurrent palindromic suffix. Hence v is rich (by Proposition 25), and thus w is rich by Lemma 30. /square

Lemma 34. Let w be a GT-word with heart v having longest palindromic prefix p and longest palindromic suffix q. If v = puq where | u | ≥ 2 and Alph ( p ) ⊆ Alph q ( ) or Alph q ( ) ⊆ Alph ( p , then Alph ) ( u ) is not contained in Alph ( p ) ∪ Alph q . Moreover, w is not rich. ( )

Proof. As in the proof of Lemma 33, we first note that | w | &gt; | Alph ( w ) | because if | w | = | Alph ( w ) | , then w = v and v would be a product of mutually distinct letters which does not take the assumed form. Hence Kv &gt; 1 and Hv &gt; 1. We must also have | Alph ( v ) | ≥ 3, because if | Alph ( v ) | = 1 then v would be a palindrome (i.e., v = p = q ), and if | Alph ( v ) | = 2, then p and q cannot be separated by a non-empty word in v by Proposition 28.

Without loss of generality, we will assume that Alph ( q ) ⊆ Alph ( p ) . Suppose on the contrary that v is a heart of a GT-word of minimal length such that v = puq where | u | ≥ 2 and the alphabet of u is contained in Alph ( p ) ∪ Alph ( q ) (where Alph ( q ) ⊆ Alph ( p ) ).

/negationslash

Using very similar reasoning as in the proof of Proposition 28 (and keeping in mind that any left/right special factor of v has left/right valence 2 by Propositions 7 and 8), we deduce that p = q and that both p and q are unioccurrent in v . Hence Hv ≤ | p | and Kv ≤ | | q . Moreover, one can also show (using much the same reasoning as in the proof of Proposition 28) that Rv ≤ Hv and Lv ≤ Kv , from which it follows that Rv = Lv and Kv = Hv since max { Rv , Kv } = max { Lv , Hv } and min { Rv , Kv } = min { Lv , Hv } by [4, Corollary 4.1] and Proposition 14. This implies that | pu | ≤ Rv + | Alph ( v ) | -2 since | pu | = | v | - | q | where | v | = Rv + Kv + | Alph ( v ) | -2 (by Theorem 17) and Kv ≤ | q | . Moreover, since Alph ( u ) ⊆ Alph ( p ) , we have Kpu &gt; 1 and Hpu &gt; 1, and therefore pu is (the heart of) a GT-word (by Proposition 22). Hence | pu | = Lpu + Hpu + Alph ( pu ) -2 (by Corollary 20), where Alph ( pu ) = Alph ( v ) and Hpu = Hv = Kv since Hv ≤ | p | . Therefore

$$| p u | = L _ { p u } + H _ { v } + | \text{Alph} ( v ) | - 2 \leq R _ { v } + | \text{Alph} ( v ) | - 2,$$

i.e., Lpu + Hv ≤ Rv . But Rv ≤ Hv . This implies that Rv = Hv and Lpu = 0, which is impossible.

Thus Alph ( u ) is not contained in Alph ( p ) ∪ Alph ( q ) ; in particular, u contains a letter not in Alph ( p ) ∪ Alph ( q ) . Suppose that u also contains a letter in common with p or q . Then, using the fact that v contains at most one left (resp. right) special factor of each length, with any such factor having left (resp. right) valence 2 (Propositions 7 and 8), it can be (tediously) shown that v must take one of the following forms ( cf. arguments in the proofs of Lemmas 31 and 33).

/negationslash

- /trianglerightsld Type 1: v = aZ aZ a 1 2 where a is a letter, each Zi is a product of at least two mutually distinct letters different from a (i.e., | Zi | = | Alph ( Zi ) | ≥ 2 and a ∈ Alph ( Zi ) for i = 1, 2), and Alph ( Z 1 ) ∩ Alph ( Z 2 ) = ∅ .

/negationslash

- /trianglerightsld Type 2: v = ( ab ) m + 1 Z ab ( ) n -1 a where a , b are distinct letters, m n , ∈ N + , and Z is a product of mutually distinct letters (possibly just a single letter) different from a and b (i.e., | Z | = | Alph ( Z ) | and a b , ∈ Alph ( Z ) ).
- /trianglerightsld Type 3: The reverse of Type 2.

Note that hearts v of Type 1 have p = q = a and u = Z aZ 1 2 (e.g., abcadea ); hearts of Type 2 have p = ( ab ) m a , u = bZ q , = ( ab ) n -1 a (e.g., ababcaba ); and hearts of Type 3 have p = ( ab ) n -1 a , u = Zb , q = ( ab ) m a (e.g., adcbaba ). It is easy to see that any such word is not rich. Indeed, if v is of Type 1, then v contains two non-palindromic complete returns to the letter a (namely aZ a 1 and aZ a 2 ). On the other hand, if v is of Type 2 (or similarly Type 3), then v contains the non-palindromic complete return abZa (or aZba ) to the letter a .

It remains to show that if u has no letters in common with p and q , then v (and hence w ) is not rich. We distinguish two cases, as follows.

Case 1: u is not a palindrome . Since Alph ( q ) ⊆ Alph ( p ) , the first letter a of q is a factor of p and we can write p = p ap ′ ′′ and q = aq ′ where p ′′ is a (possibly empty) word not containing the letter a . That is, v = p ap ′ ′′ uaq ′ where ap ′′ ua is a non-palindromic complete return to the letter a . Thus v is not rich.

/negationslash

/negationslash

/negationslash

Case 2: u is a palindrome . If p = q then v ( = pup ) would be a palindrome. But this is absurd because if v were a palindrome, then we would necessarily have v = p = q by definition of p and q . Therefore p = q . Let x denote the last letter of u . Since | u | ≥ 2, there exists a letter y (possibly equal to x ) such that xy and its reversal yx are factors of u . Moreover, if /lscript is the last letter of p and f is the first letter of q , then /lscript x and xf are factors of v where { /lscript , f } ∩ { x y , } = ∅ since u contains no letters in common with p and q . So the letter x is a bispecial factor of v of length 1. This means that neither p nor q contains a left or right special factor, otherwise v would contain another left or right special factor different from x , which is not possible by Propositions 7 and 8. So either p = a m for some letter a and m ∈ N + or p = ( ab ) m a where a , b are distinct letters and m ∈ N + . Likewise, since q has no left or right special factor of length 1 and Alph ( q ) ⊆ Alph ( p ) , it follows that q must take the form a n , ( ab ) n a or ( ba ) n b for some n ∈ N + . If p = a m , then q = a n where n = m (since p = q and Alph ( q ) ⊆ Alph ( p ) ). However, if this was the case, then v would begin (or end) with a palindrome of the form a k ua k longer than p (or q ). So p must take the form ( ab ) m a for some m ∈ N + . If q also takes the form ( ab ) n a for some n ∈ N + , then v would begin (or end) with a palindrome of the form ( ab ) k au ab ( ) k a longer than p (or q ). So q must take the form ( ba ) n b . But then v = ( ab ) m au ( ba ) m b which contains the nonpalindromic complete return baub to the letter b (and also the non-palindromic complete return auba to the letter a ). Thus v is not rich. /square

Lemma 35. Let w be a GT-word with heart v having longest palindromic prefix p and longest palindromic suffix q. Suppose v = puq where u is a non-empty word and Alph ( p ) ∩ Alph q ( ) = ∅ . Then v is rich if and only if there exist words u 1 , u , and Z (at least one of which is non-empty) such that u 2 = u Zu 1 2 where Alph u ( 1 ) ⊆ Alph ( p , Alph ) ( u 2 ) ⊆ Alph q , and Z contains no letters in common with p and q. Moreover, ( ) | Z | = | Alph Z ( ) | and there exist mutually distinct letters a, b, x, y and positive integers m , n such that one of the following conditions is satisfied:

- (i) p = ( ab ) m a, u = Zx, q = ( yx ) n y;
- (ii) p = ( ba ) m b, u = aZx, q = ( yx ) n y;
- (iii) p = a m + 1 , u = Zx, q = ( yx ) n y;
- (iv) p = ( ab ) m a, u = Z, q = x n + 1 ;
- (v) p = ( ab ) m a, u = Z, q = ( xy ) n x;
- (vi) p = a m , u = Z, q = x n ;
- (vii) the forms of p and q are the opposite of those satisfying one of the conditions (i)-(vi) with the reversal of the corresponding u separating them.

Note. The word Z must be non-empty in conditions (iv)-(vi).

Proof. Clearly we have | Alph ( v ) | ≥ 3, because if | Alph ( v ) | = 1 then v would be a palindrome (i.e., v = p = q ), and if | Alph ( v ) | = 2, then p and q cannot be separated by a non-empty word in v by Proposition 28. We also observe that if | w | = | Alph ( w ) | , then w = v and such a word is simply a product of mutually distinct letters with its first and last letters being its longest palindromic prefix and longest palindromic suffix, respectively. Such a word v has p , u , and q satisfying condition (vi) with m = n = 1. So we will now assume that | w | &gt; | Alph ( w ) | , in which case the heart v of w satisfies Kv &gt; 1 and Hv &gt; 1. This means, in particular, that each letter in Alph ( v ) is both left and right extendable in v .

( ⇒ :) Suppose v is rich. Then we must have | p | ≥ 2 and | q | ≥ 2. Indeed, if p = a for some letter a , then since Hv &gt; 1, p occurs at least twice in v , and therefore v begins with a palindromic complete return to p that is longer than p (its longest palindromic prefix), which is not possible. Likewise, we deduce that | q | ≥ 2. We distinguish two cases, as follows.

/negationslash

/negationslash

Case 1: Alph ( u ) ⊆ Alph ( p ) ∪ Alph ( q ) . Suppose x is the left-most letter in u that is not in the alphabet of p . Then v = pu xu q 1 2 where u 1 , u 2 are (possibly empty) words with Alph ( pu 1 ) = Alph ( p ) . Let a denote the last letter of pu 1 . Then a occurs in p (since Alph ( pu 1 ) = Alph ( p ) ), and moreover, since | p | ≥ 2, there exists a letter b = x such that ba and ab are factors of p . Since ax is also a factor of v , we see that a is a right special factor of v of length 1. Moreover, the letter x is left special in v because x ∈ Alph ( q ) and so there exists a letter y ∈ Alph ( q ) such that xy and also yx is a factor of q ; whence ax and yx are factors of v where y = a . We thus deduce that p contains no left or right special factor of length 1. Indeed, the right special letter a can only be followed by b (not x ) in p ; otherwise a would have right-valence greater than 2, which implies that Cv ( 2 ) ≥ Cv ( 1 ) + 2 (since each letter in Alph ( v ) is right-extendable in v ). But this is impossible because v is a GT-word (also see Proposition 7). We also note that the letter a can be preceded by only the letter b in p ; otherwise a would be another left special factor of v of length 1 (in addition to the letter x ) which is not possible by Proposition 8. So pu 1 takes one of the following forms:

/negationslash

$$\ p u _ { 1 } = a ^ { m + 1 } \, ( a = b, u _ { 1 } = \varepsilon ), \ \ p u _ { 1 } = ( a b ) ^ { m } a \, ( a \neq b, u _ { 1 } = \varepsilon ), \ \text{ or } \ \ p u _ { 1 } = ( b a ) ^ { m } b a \, ( a \neq b, u _ { 1 } = a )$$

/negationslash for some m ∈ N + . Furthermore, we observe that the letters a and b cannot occur to the right of x in v ; otherwise one of those letters would be left special. But the only letter that can be left special in v is

/negationslash

˜ ˜ Case 2: Alph ( u ) contains a letter not in Alph ( p ) ∪ Alph ( q ) . Using very similar reasoning as in Case 1, we deduce that v satisfies one of the conditions (i)-(vi) where Z is a non-empty word containing no letters in common with p and q , and the reversal of any such v (namely, ˜ v = qup ˜ , which is also a GT-word by Proposition 23) satisfies condition (vii). Moreover, we note that | Z | = | Alph ( Z ) | , i.e., Z is a product of mutually distinct letters. Indeed, Z has no left or right special factor of length 1 because the letters a and x are, respectively, the unique right and left special factors of v of length 1. This implies that Z is either a product of mutually distinct letters (possibly just a single letter), or Z takes one of the following forms:

x , by the fact that | v | = Lv + Hv + | Alph ( v ) | -2 (by Corollary 20) together with Proposition 8. Hence Alph ( xu q 2 ) = Alph ( q ) , and using similar reasoning as for pu 1 , we observe that xu q 2 has no left or right special factor of length 1. Therefore xu q 2 = x yx ( ) n y for some n ∈ N + where x = y (and u 2 = ε ). We have thus shown that v satisfies one of the conditions (i)-(iii) with Z = ε , and the reversal of any such v (namely, v = qup , which is also a GT-word by Proposition 23) satisfies condition (vii).

$$Z = ( c d ) ^ { k } c, \ \ Z = ( c d ) ^ { k + 1 }, \ \ \text{or} \ \ Z = c ^ { k + 1 } \ \ \text{for some} \, k \in \mathbb { N } ^ { + },$$

where c and d are distinct letters. But none of the above forms are possible because in each case the letter c would be a left special factor of v of length 1 (different from x ). Thus Z must be a product of mutually distinct letters.

( ⇐ ): Conversely, suppose u = u Zu 1 2 where u 1 , u 2 , and Z are words such that Alph ( u 1 ) ⊆ Alph ( p ) , Alph ( u 2 ) ⊆ Alph ( q ) , and Z contains no letters in common with p and q . Then, using the same reasoning as above, we deduce that v satisfies one of the conditions (i)-(vii) and it is easy to see that every prefix of any such word has a unioccurrent palindromic suffix; whence v is rich. /square

Proof of Theorem 27. ( ⇒ ): Suppose w is rich. Then the heart v of w is clearly rich too since any factor of a rich word is rich (see Lemma 30). Suppose, by way of contradiction, that v is the (rich) heart of a rich GT-word w such that v satisfies none of the conditions (i)-(iii) in the statement of the theorem. Then, by Lemmas 31, 33, and 35, the only possibility is that v takes the form v = puq where | u | ≥ 2 and Alph ( p ) ⊆ Alph ( q ) or Alph ( q ) ⊆ Alph ( p ) . However, by Lemma 34, all such v are not rich. Hence one of the conditions (i)-(iii) must hold.

( ⇐ ): Conversely, suppose that v satisfies one of the conditions (i)-(iii) in the statement of the theorem. To prove that w is rich, it suffices to prove that v is rich (by Lemma 30). We first observe that if v satisfies either of the conditions (ii) or (iii), then v is rich (by Lemmas 31, 33, and 35). So let us now assume that v satisfies condition (i) and suppose, on the contrary, that v is a heart of a GT-word of minimal length satisfying that condition but v is not rich. Then, by Proposition 25, v contains a non-palindromic complete return to some non-empty palindrome P , say r = PUP where U is a nonpalindromic word. If r = PUP is a factor of p , then p would be a non-rich (heart of a) GT-word shorter than v satisfying condition (i), contradicting the minimality of v as a heart of a GT-word of shortest length satisfying condition (i), but not rich. So r = PUP is not a factor of p , and likewise, r is not a factor of q . Therefore r = PUP is not wholly contained in either of the palindromes p and q . Hence, we have v = p rq ′ ′ = p PUPq ′ ′ where p ′ is prefix of p and q ′ is a suffix of q . Note that at least one of the words p ′ and q ′ is non-empty; otherwise v = PUP where P = p = q and | U | ≥ 2, in which case v does not satisfy either of the conditions (i) or (ii). We distinguish three cases, as follows.

/negationslash

Case 1: The first occurrence of P in r is not contained in p. In this case, q = P UPq ′ ′ where P ′ is a (possibly empty) suffix of P with P ′ = P (i.e., P ′ is a proper suffix of P ) because, by assumption, q does not contain r = PUP as a factor. Let S = PUPq ′ . This proper suffix of v is (the heart of) a GT-word (by Proposition 22) and its longest palindromic prefix is P . Indeed, if S had a palindromic prefix longer than P , but shorter than r = PUP , then P would occur more than twice in r (i.e., P would

occur as an interior factor of r ), which is impossible because r is a complete return to P . On the other hand, if S had a palindromic prefix Z longer than r = PUP , then the palindrome Z (which begins with r = PUP ) would be a non-rich (heart of a) GT-word shorter than v satisfying condition (i), contradicting the minimality of v . So we see that the longest palindromic prefix of S (namely P ) and the longest palindromic suffix of S (namely q ) are unseparated in S . Hence S is a non-rich (heart of a) GT-word (shorter than v ) satisfying condition (i), contradicting the minimality of v again.

Case 2: The second occurrence of P in r is not contained in q. Using the same reasoning as in Case 1 we reach a contradiction.

Case 3: The first occurrence of P in r is contained in p and the second occurrence of P in r is contained in q . In this case, p ends with PU ′ where U ′ is a proper prefix of UP and q begins with U P ′′ where U ′′ is a proper suffix of PU . Let S = PUPq ′ where q ′ is a suffix of q . We observe that S has longest palindromic suffix q , and using the same reasoning as in Case 1, we deduce that the longest palindromic prefix of S is P . Moreover, P and q must be unseparated in S . Otherwise, if P and q were separated by a letter or word of length at least 2 in S , then the same would be true of p and q in v , which is impossible because v satisfies condition (i). Hence S is a non-rich (heart of a) GT-word (shorter than v ) satisfying condition (i), contradicting the minimality of v .

In each of the above three cases we have reached a contradiction. Hence v (and therefore w ) must be rich. /square

## 4. CLOSING REMARKS

In this paper we have introduced a new class of words that encompass the (original) binary trapezoidal words and have studied combinatorial and structural properties of these so-called generalized trapezoidal words. We have also proved some characterizations of these words and have described all those that are rich in palindromes. A nice (direct) consequence of our characterization of rich GTwords is that all GT-words with palindromic hearts are rich. In the case of binary trapezoidal words, we have independently proved that the longest palindromic prefix and longest palindromic suffix of any such word must be 'unseparated', from which it follows that all binary trapezoidal words are rich, originally proved in a different way in [5]. Further work-in-progress concerns the enumeration of generalized trapezoidal words, as has recently been considered in the binary case [2] (see also [9] in which an enumeration formula for binary trapezoidal words was independently obtained).

## 5. ACKNOWLEDGEMENTS

We thank very much the two anonymous referees for their thoughtful comments and suggestions which greatly helped to improve the paper. The first author would also like to thank members of the Laboratoire MIS and Equipe SDMA at the Université de Picardie Jules Verne for their kind hospitality during her 1-month visit in mid 2011 when some of the preliminary work on this paper was done. She also gratefully acknowledges the funding provided by the Université de Picardie Jules Verne for her visit to Amiens.

## REFERENCES

- [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the palindromic complexity of infinite words, Internat. J. Found. Comput. Sci. 15 (2004) 293-306.
- [2] M. Bucci, A. De Luca, G. Fici, Enumeration and structure of trapezoidal words, Theoret. Comput. Sci. 468 (2013) 12-22.
- [3] F. D'Alessandro, A combinatorial problem on trapezoidal words, Theoret. Comput. Sci. 273 (2002) 11-33.
- [4] A. de Luca, On the combinatorics of finite words, Theoret. Comput. Sci. 218 (1999) 13-39.
- [5] A. de Luca, A. Glen, L.Q. Zamboni, Rich, Sturmian, and trapezoidal words, Theoret. Comput. Sci. 407 (2008) 569-573.

- [6] X. Droubay, J. Justin, G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001) 539-553.
- [7] X. Droubay, G. Pirillo, Palindromes and Sturmian words, Theoret. Comput. Sci. 223 (1999), p. 73-85.
- [8] A. Glen, J. Justin, S. Widmer, L.Q. Zamboni, Palindromic richness, European J. Combin. 30 (2009) 510-531.
- [9] A. Heinis, On low-complexity bi-infinite words and their factors, J. Théor. Nombres Bordeaux 13 (2001) 421-442.
- [10] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications , vol. 90, Cambridge University Press , UK, 2002.
- [11] M. Morse, G. A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940) 1-42.

AMY GLEN

SCHOOL OF ENGINEERING &amp; INFORMATION TECHNOLOGY MURDOCH UNIVERSITY 90 SOUTH STREET MURDOCH WA 6150 AUSTRALIA

E-mail address :

amy.glen@gmail.com

FLORENCE LEVÉ LABORATOIRE MIS UNIVERSITÉ DE PICARDIE JULES VERNE 33 RUE SAINT LEU 80039 AMIENS FRANCE

E-mail address :

florence.leve@u-picardie.fr
Amy Glen Florence Levé
Generalized trapezoidal words
The factor complexity function $C_w(n)$ of a finite or infinite word $w$
counts the number of distinct factors of $w$ of length $n$ for each $n \ge 0$.
A finite word $w$ of length $|w|$ is said to be trapezoidal if the graph of its
factor complexity $C_w(n)$ as a function of $n$ (for $0 \leq n \leq |w|$) is
that of a regular trapezoid (or possibly an isosceles triangle); that is,
$C_w(n)$ increases by 1 with each $n$ on some interval of length $r$, then
$C_w(n)$ is constant on some interval of length $s$, and finally $C_w(n)$
decreases by 1 with each $n$ on an interval of the same length $r$. Necessarily
$C_w(1)=2$ (since there is one factor of length $0$, namely the empty word), so
any trapezoidal word is on a binary alphabet. Trapezoidal words were first
introduced by de Luca (1999) when studying the behaviour of the factor
complexity of finite Sturmian words, i.e., factors of infinite "cutting
sequences", obtained by coding the sequence of cuts in an integer lattice over
the positive quadrant of $\mathbb{R}^2$ made by a line of irrational slope.
Every finite Sturmian word is trapezoidal, but not conversely. However, both
families of words (trapezoidal and Sturmian) are special classes of so-called
"rich words" (also known as "full words") - a wider family of finite and
infinite words characterized by containing the maximal number of palindromes -
studied in depth by the first author and others in 2009.
  In this paper, we introduce a natural generalization of trapezoidal words
over an arbitrary finite alphabet $\mathcal{A}$, called generalized trapezoidal
words (or GT-words for short). In particular, we study combinatorial and
structural properties of this new class of words, and we show that, unlike the
binary case, not all GT-words are rich in palindromes when $|\mathcal{A}| \geq
3$, but we can describe all those that are rich.