Ioannis C Michos
email: imichos@uoi.gr

On the support of the free Lie algebra: the Sch ützenberger problems

Keywords: Free Lie algebras, Pascal triangle mod m, shuffle product, set partitions, λ-tabloids

M.-P. Schützenberger asked to determine the support of the free Lie algebra LZ m (A) on a finite alphabet A over the ring Zm of integers mod m and all pairs of twin and anti-twin words, i.e., words that appear with equal (resp. opposite) coefficients in each Lie polynomial. We characterize the complement of the support of LZ m (A) in A * as the set of all words w such that m divides all the coefficients appearing in the monomials of l * (w), where l * is the adjoint endomorphism of the left normed Lie bracketing l of the free Lie ring. Calculating l * (w) via the shuffle product, we recover the well known result of Duchamp and Thibon (Discrete Math. 76 (1989) 123-132) for the support of the free Lie ring in a much more natural way. We conjecture that two words u and v of common length n, which lie in the support of the free Lie ring, are twin (resp. anti-twin) if and only if either u = v or n is odd and u = ṽ (resp. if n is even and u = ṽ), where ṽ denotes the reversal of v and we prove that it suffices to show this for a two-lettered alphabet. These problems can be rephrased, for words of length n, in terms of the action of the Dynkin operator ln on λ-tabloids, where λ is a partition of n. Representing a word w in two letters by the subset I of [n] = {1, 2, . . . , n} that consists of all positions that one of the letters occurs in w, the computation of l * (w) leads us to the notion of the Pascal descent polynomial pn(I), a particular commutative multi-linear polynomial which is equal to the signed binomial coefficient when |I| = 1. We provide a recursion formula for pn(I) and show that if m X i∈I (-1) i-1 n -1 i -1 ! , then w lies in the support of LZ m (A).

Introduction

Let A be a finite alphabet, A * be the free monoid on A and A + = A * \ { } be the free semigroup on A, with denoting the empty word. For a word w ∈ A * let |w| denote its length, |w| a denote the number of occurrences of the letter a ∈ A in w and let alph(w) be the set of all letters actually occurring in w.

Let K be a commutative ring with unity. For most of our purposes K = Z m , the ring Z/(m) of integers modm for a non-negative integer m. Let K A be the free associative algebra on A over K. Its elements are polynomials on non-commuting variables from A and coefficients from K. Each polynomial P ∈ K A is written in the form P = w∈A * (P, w) w, where (P, w) denotes the coefficient of the word w in P . Given two polynomials P, Q ∈ K A , their Lie product is the Lie bracket [P, Q] = P Q -QP . In this way K A is given a Lie structure. It can be proved (see e.g., [START_REF] Reutenauer | Free Lie Algebras[END_REF]Theorem 0.5]) that the free Lie algebra L K (A) on A over K is equal to the Lie subalgebra of K A generated by A. When K is the ring Z of rational integers, L K (A) is also known as the free Lie ring. A Lie monomial is an element of L K (A) formed by Lie products of the elements a ∈ A. A Lie polynomial is a linear combination of Lie monomials, i.e., an arbitrary element of L K (A). The support of L K (A) is the subset of A * consisting of those words that appear (with a non-zero coefficient) in some Lie polynomial. A pair of words u, v is called twin (respectively anti-twin) if both words appear with equal (respectively opposite) coefficients in each Lie polynomial over K.

M.-P. Schützenberger had posed the following problems (pointed to us in a private communication with G. Duchamp):

Problem 1.1 Determine the support of the free Lie ring L Z (A).

Problem 1.2 Determine the support of L Zm (A), for m > 1.

Problem 1.3 Determine all twin and anti-twin pairs of words with respect to L Z (A).

Problem 1.4 Determine all twin and anti-twin pairs of words with respect to L Zm (A), for m > 1.

In view of these problems Schützenberger considered, for each word w ∈ A * , the smallest non-negative integer -which we denote by c(w) -that appears as a coefficient of w in some Lie polynomial over Z. For each non-negative integer m he also defined and tried to characterize the language L m of all words with c(w) = m; considering, in particular, the cases m = 0 and m = 1 (see [14, §1.6.1]).

For m = 0 the language L 0 is clearly equal to the complement of the support of the free Lie ring L Z (A) in A * , since a word w does not appear in any Lie polynomial over Z if and only if c(w) = 0. Duchamp and Thibon gave a complete answer to Problem 1.1 in [START_REF] Duchamp | Le support de l'algèbre de Lie libre[END_REF] and proved that L 0 consists of all words w which are either a power a n of a letter a, with exponent n > 1, or a palindrome (i.e., a word u equal to its reversal, denoted by ũ) of even length. The non-trivial part of their work was to show that each word not of the previous form lies in the support of L Z (A) and this was achieved by a construction of an ad hoc family of Lie polynomials. This result was extended in [START_REF] Duchamp | On the support of graph Lie algebras[END_REF] -under certain conditions -to traces, i.e., partially commutative words (see [START_REF]The Book of Traces[END_REF] for an exposition of trace theory) instead of non-commutative ones, and the corresponding free partially commutative Lie algebra (also known as graph Lie algebra).

For m = 1 all Lyndon words on A (for more on this subject see e.g., [9, §5.1 and §5.3]) lie in L 1 since the element P w of the Lyndon basis of L Z (A) that corresponds to the standard factorization of a given Lyndon word w is equal to w plus a linear combination of greater words -with respect to the lexicographic ordering in A + -of the same length as w [START_REF] Lothaire | Combinatorics on Words[END_REF]Lemma 5.3.2]. On the other hand, there exist non Lyndon words which also lie in L 1 . For example, one can check that the word a 2 b 2 a -which is clearly non Lyndon as it starts and ends with the same letter -appears with coefficient equal to -1 in the Lie monomial P In Section 2 we relate Problems 1.1 up to 1.4 with the notion of the adjoint endomorphism l * of the left-normed Lie bracketing l of the free Lie algebra L K (A) with respect to the canonical scalar product on K A . Our starting point is the simple idea that a word w does not lie in the support of L K (A) if and only if l * (w) = 0 and a pair (u, v) of words is twin (respectively anti-twin) if and only if l * (u) = l * (v) (respectively l * (u) = -l * (v)). We also show that c(w) is either zero or the greatest common divisor of the coefficients of the monomials appearing in l * (w), for the left-normed Lie bracketing l of the free Lie ring. It turns out that it is also equal to the greatest common divisor of the coefficients in the expression of l * (w) as a linear combination of the images of the Lyndon words of length |w| under l * .

Considering the natural projection from Z onto Z m for m = 1, we show that the complement of the support of L Zm (A) in A * is identified with the language L m of all words w with m | c(w). For Problem 1.3 we conjecture that two words u, v of common length n that do not lie in the support of the free Lie ring, i.e., they are not n-th powers of a letter with n > 1 or palindromes of even length, are twin if and only if either u = v or n is odd and u = ṽ and are anti-twin if and only if n is even and u = ṽ. We also show that it suffices to prove this over an alphabet of two letters.

In Section 3 we calculate the polynomial l * (w) recursively in terms of all factors u of fixed length r ≥ 1 of w and the shuffle product of words (see [14, §1.4] for a definition) as

l * (w) = w=sut |u|=r l * (u) (-1) |s| {s ¡ t}
and use this to recover naturally the result of Duchamp and Thibon in [START_REF] Duchamp | Le support de l'algèbre de Lie libre[END_REF]. Furthermore, if w lies in the kernel of l * over K we show that |alph(w)| ≤ |w|/2 . Applying this for K = Z m for all m > 1 we obtain, as a corollary, the fact that all words w with |alph(w)| > |w|/2 have c(w) = 1 and therefore lie in L 1 , just as Lyndon words do.

In Section 4 Problems 1.1 up to 1.4 boil down to particular combinatorial questions on the group ring KS n of the symmetric group S n on n letters. Let [n] denote the set {1, 2, . . . , n} and fix a sub-alphabet B = {a 1 , a 2 , . . . a r } of A. The main idea is to view a word w of length n on B as an ordered set partition of [n] denoted by {w} = (I 1 (w), I 2 (w), . . . , I r (w)), where for each k ∈ [r] the set I k (w) consists of the positions of [n] in which the letter a k occurs in w. If λ = (λ 1 , λ 2 , . . . , λ r ) is the multi-degree of w then {w} is just a λ-tabloid, where λ may be, without loss of generality, assumed an integer partition of n. The role of the reversal w of a word w is then played by the tabloid τ n • {w}, where τ n is the involution

k i=1 (i, n -i + 1) of S n with k = n/2 .
Viewing each permutation as a word in n distinct letters, the left-normed multi-linear Lie bracketing

l n = l(x 1 x 2 • • • x n ) and its adjoint l * n = l * (x 1 x 2 • • • x n
) can be viewed as elements of the group ring KS n ; the first one is known as the Dynkin operator. The right permutation action of l * n on words is then equivalent to the left natural action of l n on tabloids; in particular w • l * n = 0 if and only if l n • {w} = 0. In this way all previous results and problems translate to corresponding problems on tabloids. In particular, Problem 1.2 boils down to the problem of finding all λ-tabloids t that satisfy the equation l n • t = 0 in the group ring Z m S n .

One can say more for words where only two letters occur since an ordered partition with two parts is determined by the subset I = {i 1 , i 2 , . . . , i s } of [n] that appears in its second row, and is denoted accordingly by I. We map I to the monomial x I = x i1 x i2 • • • x is in n commuting variables x 1 , x 2 , . . . , x n and extending this by linearity the element l n • I can be viewed as a multi-linear polynomial h n (I) of total degree s. In this way we can view all Schützenberger problems in a commutative algebra setting. We show that h n (I) is a multiple of the binomial x 1 -x 2 . The corresponding quotient p n (I) is called Pascal descent polynomial and is in many aspects a generalization of the notion of the signed binomial coefficient. We study the polynomials p n (I) in Section 5 and give a recursion formula for their calculation. Problem 1.2 is then equivalent to determining all subsets I of [n] such that p n (I) ≡ 0 (mod m). The latter leads us to an explicitly stated sufficient condition for a word w to lie in the support of the free Lie algebra L Zm (A): namely m N n (I), where n = |w|, I = I(w) is the subset of [n] consisting of the positions that one of the two letters occurs in w and

N n (I) = i∈I (-1) i-1 n -1 i -1
. This actually means that the signed sum of the entries appearing at the positions corresponding to the subset I in the n-th row (starting to count from n = 0) of the Pascal triangle mod m has to be different from zero mod m. Similar necessary conditions are obtained for twin and anti-twin words with respect to L Zm (A). Finally our conjecture for twin and anti-twin pairs in the free Lie ring is equivalent to showing that when p n (I) = 0 and p n (J) = 0, then p n (I) = p n (J) if and only if I = J or I = τ n (J) and n is odd and p n (I) = -p n (J) if and only if I = τ n (J) and n is even.

Preliminary results

The set K A becomes a non-commutative associative algebra with the usual concatenation product defined as

(P Q, w) = w=uv (P, u)(Q, v) , (2.1)
and a commutative associative algebra with the shuffle product that is initially defined for words as ¡w = w ¡ = w, if at least one of them is the empty word , and recursively as

(au ) ¡ (bv ) = a(u ¡ (bv )) + b((au ) ¡ v ) , (2.2)
if u = au and v = bv with a, b ∈ A and u , v ∈ A * (see [14, (1.4.2)] or [2, §4.1] for a q-deformation).

Elements of the form u ¡ v with u, v ∈ A + are called proper shuffles. The definition of the shuffle product is extended linearly to the whole of K A . The left-normed Lie bracketing of a word is the Lie polynomial l defined recursively as

l( ) = 0 , l(a) = a , and
l(ua) = [l(u), a] , (2.3)
for each a ∈ A and u ∈ A + . One can extend l linearly to K A and construct a linear map, denoted also by l, which maps K A onto the free Lie algebra L K (A), since the set {l(u) : u ∈ A * } is a well known K-linear generating set of L K (A) (see e.g. [14, §0.4.1]).

Given two polynomials P, Q ∈ K A there is a canonical scalar product defined as

(P, Q) = w∈A * (P, w)(Q, w) (2.4)
in the sense that it is the unique scalar product on K A for which A * is an orthonormal basis. The adjoint endomorphism l * of the left-normed Lie bracketing l is then defined by the relation

(l * (u), v) = (l(v), u) (2.5)
for any words u, v. The image of l * on a word of A * can also be effectively defined recursively by the relations l * ( ) = 0 , l * (a) = a , and

l * (aub) = l * (au) b -l * (ub) a , (2.6)
where a, b ∈ A and u ∈ A * (cf. [START_REF] Lothaire | Combinatorics on Words[END_REF]Problem 5.3.2]). The proof goes by induction on the length of the given word, just as in the case of the adjoint endomorphism of the right-normed Lie bracketing (discussed in detail in [14, pp. 32 -33]). The reason we choose to work with the left-normed one is that its multi-linear version corresponds to the Dynkin operator which has been thoroughly studied; this will be discussed later on in Section 4.

Lemma 2.1 Let w denote the reversal of the word w. Then l * ( w) = (-1) |w|+1 l * (w) .

Proof: By the recursive formula (2.6) and an easy induction on |w|. 2

One can also extend l * linearly to the whole of K A and construct a linear endomorphism of K A , denoted also by l * . What is of crucial importance for the Schützenberger problems is the kernel ker l * of l * . Let L K (A)

⊥ denote the orthogonal complement of L K (A) with respect to the scalar product (2.4) in K A . Then, for an arbitrary commutative ring K with unity, the following two results hold.

Lemma 2.2 ker l * = L K (A)
⊥ .

Proof (l(u), l i ) ξ i = (l(u), w).

Since {l(u) : u ∈ A n } and {P l1 , P l2 , . . . , P lr } are respectively a K-generating set and a K-basis of L n K (A), the latter is equivalent to the r × r linear system r i=1 (P li , l i ) ξ i = (P li , w), with i ∈ [r] in the unknowns ξ 1 , ξ 2 , . . . , ξ r . Since (P li , l i ) = 1 and (P li , l j ) = 0 for j < i this boils down to

ξ i + r j=i+1 (P li , l j ) ξ j = (P li , w), i ∈ [r]. (2.7)
By triangularity, the linear system (2.7) has a unique solution (ξ 1 , ξ 2 , . . . , ξ r ) ∈ K r , as required. 2

For a given word w of length n Schützenberger considered the unique non-negative generator c(w) of the ideal {(P, w) : P ∈ L Z (A)} of Z (see [14, §1.6.1]). It is natural to ask how to calculate the number c(w) and try to find a homogeneous Lie polynomial Q w of degree n such that (Q w , w) = c(w). One would a priori search amongst all Lie polynomials of some basis of L n Z (A). It turns out that this can be done in terms of just one polynomial, which is not a Lie polynomial in general, namely the element l * (w) ∈ Z A .

Theorem 2.6 Let w be a word of length n and l * be the adjoint endomorphism of the left-normed Lie bracketing l of the free Lie ring on A. Then c(w) is either zero or is equal to the greatest common divisor of the non-zero coefficients that appear either in the monomials of the polynomial l * (w) or in its representation as a linear combination of the images of the Lyndon words of length n under l * .

Proof: Clearly c(w) = 0 if and only if l * (w) = 0. Suppose that l * (w) = 0. Then we obtain (2.5) and the definition of c(w) we obtain c(w) = gcd (l(u), w) : u ∈ A n = gcd (l * (w), u) : u ∈ A n , as required. If, on the other hand, we choose X = {P l1 , P l2 , . . . , P lr }, where r is the number of all Lyndon words of length n, then again c(w) = gcd (P l1 , w), (P l2 , w), . . . , (P lr , w) . Now the triangular form of the linear system (2.7) for K = Z implies that (P l1 , w), (P l2 , w), . . . , (P lr , w) = ξ 1 , ξ 2 , . . . , ξ r , so that we also get c(w) = gcd(ξ 1 , ξ 2 , . . . , ξ r ).

{(P, w) : P ∈ L Z (A)} = {(P, w) : P ∈ L n Z (A)} = {(P, w) : P ∈ X , X a generating set for L n Z (A)} . For s ∈ N the ideal n 1 , n 2 , . . . , n s generated by n 1 , n 2 , . . . , n s ∈ Z is equal to gcd(n 1 , n 2 , . . . , n s ) . Thus if we choose X = {l(u) : u ∈ A n } then by
2

Suppose that l * (w) = d 1 u 1 + d 2 u 2 + • • • + d s u s , where d 1 , d 2 , . . . , d s ∈ Z * and u 1 , u 2 , . . . , u s ∈ A n . Then by Theorem 2.6 c(w) = gcd (d 1 , d 2 , . . . , d s )
and by an extension of Bezout's identity to more than two integers there exist

k 1 , k 2 , . . . , k s ∈ Z such that c(w) = k 1 d 1 + k 2 d 2 + • • • + k s d s . Therefore if we set Q w = k 1 l(u 1 ) + k 2 l(u 2 ) + • • • + k s l(u s ) by (2.5) we easily obtain (Q w , w) = c(w), as required. Let m be a positive integer with m > 1. The natural projection k → k = k (mod m) from Z onto Z m induces a surjective map θ : Z A Z m A that sends a polynomial P = u∈A * (P, u) u ∈ Z A to the polynomial θ(P ) = u∈A * (P, u) u ∈ Z m A . Clearly ker θ = (m) Z A . The restriction ψ of θ to L Z (A) is also surjective onto L Zm (A) with ker ψ = (m) L Z (A).
If we denote the left-normed Lie bracketing over Z m and its adjoint by l and l * , respectively, it is easy to see that for each word u in A * we have ψ(l(u)) = l(u). From this we can show that θ(l * (w)) = l * (w), for each word w in A * . Indeed,

θ(l * (w)) = θ u∈A * (l * (w), u) u = u∈A * (l * (w), u) u = u∈A * (l(u), w) u = u∈A * (l(u), w) u = l * (w).
Then extending linearly we get θ • l * = l * .

Theorem 2.7 (i) The complement, in A * , of the support of the free Lie algebra L Zm (A) over the ring Z m of integers mod m consists of all words w such that m | c(w), or equivalently those words with the property that the polynomial l * (w) lies in (m) Z A .

(ii) A pair of words u, v is twin (respectively anti-twin) with respect to L Zm (A) if and only if the polyno-

mial l * (u) -l * (v) (respectively l * (u) + l * (v)) lies in (m) Z A . Proof: (i) By Lemma 2.3 (i) applied for K = Z m , the complement of the support of L Zm (A) in A * is equal to {w ∈ A * : l * (w) = 0}. Since ker θ = (m) Z A and θ • l * = l * , the latter is equal to { w ∈ A * : l * (w) ∈ (m) Z A }. If l * (w) = d 1 u 1 + d 2 u 2 + • • • + d s u s , for d 1 , d 2 , . . . , d s ∈ Z * (that depend on the word w) then m | d i for all i ∈ [s] if and only if m | gcd(d 1 , d 2 , . . . , d s ) which, by Theorem 2.6, is equal to c(w). On the other hand, it is clear that l * (w) = 0 is equivalent to c(w) = 0. In any case l * (w) ∈ (m) Z A if and only if m | c(w) and the result follows. (ii) It follows similarly from Lemma 2.3 (ii). 2
Let us see now the way the Schützenberger problems relate to the Pascal triangle mod m. When m = p, a prime number, an old result due to E. Lucas [START_REF] Lucas | Sur les congruences des nombres Eulériens et des coefficients differentiels des fonctions trigonométriques, suivant un module premier[END_REF] known as the Lucas correspondence theorem (for a nice exposition of this see [START_REF] Fine | Binomial coefficients modulo a prime[END_REF]) asserts that if n and r have expansions in base p respectively given by n = q≥0 n q p q and r = q≥0 r q p q with n q , r q ∈ {0, 1, . . . , p -1}, then n r ≡ q≥0 n q r q (mod p).

(2.8)

By another old result of E. Kummer [START_REF] Kummer | Über die Ergänzungssätze den allgemeinen Reciprocitätsgesetzen[END_REF] known as Kummer's lemma, the highest power of a prime p dividing k+l k is equal to the number of carries in the p-ary addition of k and l. This enables us to solve directly the Schützenberger problems for words w of the form w = a k ba l . Lemma 2.8 Let k and l be non-negative integers which are not both equal to zero and m be a positive integer with primary decomposition m = p e1

1 p e2 2 • • • p es s . Then (i) l * (a k ba l ) = (-1) k k + l k l * (ba k+l ) = (-1) k k + l k {ba k+l -aba k+l-1 }.
(ii) The word a k ba l does not lie in the support of the free Lie algebra L Zm (A) if and only if for each i ∈ [s] the number of carries in the p i -ary addition of k and l is at least e i .

Proof: (i) It is easy to show that l * (ba m ) = ba m -aba m-1 , by induction on m. Assuming, without loss of generality, that k ≥ 1 (2.6) yields l * (a k ba l ) = {l * (a k ba l-1 ) -l * (a k-1 ba l )} a. The proof is completed by induction on k + l and the recursive definition of binomial coefficients.

(ii) By Theorem 2.7 (i) a word w lies in the complement of the support of Note that in the binary case the condition of Lemma 2.8 (ii) simply means that if k and l are written in base 2 as k = q≥0 k q 2 q and l = q≥0 λ q 2 q with k q , l q ∈ {0, 1}, there exists at least one position q where k q = l q = 1.

L Zm (A) in A * if and only if p ei i | c(w) for each i ∈ [s].
Let us now discuss Problem 1.3. In view of Lemma 2.3 (ii), given a pair of words u, v one has to check whether l * (u) = l * (v) (respectively l * (u) = -l * (v)) for the pair to be twin (respectively anti-twin). There are some trivial solutions of this problem, namely when l * (u) = l * (v) = 0, i.e., when both u and v are either powers of a letter with exponent larger than one or palindromes of even length. So let us suppose that both words do lie in the support of the free Lie ring. In view of Lemma 2.1 we propose the following conjecture.

Conjecture 2.9 Let l * be the adjoint endomorphism of the left-normed Lie bracketing l of the free Lie ring and let u and v be words of common length n such that both l * (u) and l * (v) are non-zero. Then

(i) l * (u) = l * (v) if and only if u = v or n is odd and u = ṽ. (ii) l * (u) = -l * (v) if
and only if n is even and u = ṽ. Reduction Theorem 2.10 It suffices to prove Conjecture 2.9 for an alphabet of two letters.

The proof of this result will occupy the remaining of this section. Let us first see how l * is affected by alphabetic substitutions. Consider two finite alphabets A and Σ with |A| ≥ |Σ| ≥ 2 and a mapping φ from A onto Σ. This induces a surjective literal morphism (i.e., a morphism such that φ(a) ∈ Σ, for each a ∈ A), also denoted by φ, from A * onto Σ * which in turn can be extended linearly to an algebra surjective homomorphism -still denoted by φ -from K A onto K Σ . Let l * A and l * Σ denote the adjoint endomorphism of the left-normed Lie bracketing of the free Lie algebras L K (A) and L K (Σ), respectively. Lemma 2.11 Let A and Σ be two finite alphabets with |A| ≥ |Σ| ≥ 2 and φ be a fixed literal morphism from A * onto Σ * .

(i) The algebra homomorphisms φ • l * A and l * Σ • φ from K A to K Σ are identical and φ(ker l * A ) ⊆ ker l * Σ . (ii) If |A| = |Σ| then ker l * A is mapped bijectively onto ker l * Σ under φ. (iii) φ(ker l * A ) = ker l * Σ but ker l * A is a proper subset of φ -1 (ker l * Σ ) if |A| > |Σ|.
Proof: (i) It suffices to show that l * Σ (φ(w)) = φ(l * A (w)) for each word w ∈ A * . This follows by an easy induction on |w| using the recursive definition (2.6) of l * . The inclusion φ(ker l * A ) ⊆ ker l * Σ follows easily.

(ii) We apply the result of part (i) for the literal morphisms φ : A Σ and φ -1 : Σ A and obtain φ(ker l * A ) ⊆ ker l * Σ and φ -1 (ker l * Σ ) ⊆ ker l * A which clearly implies the required result. (iii) It remains to show that φ(ker l *

A ) ⊇ ker l * Σ . Let Q = i λ i v i be a polynomial in ker l * Σ and Σ Q = i alph(v i ).
For each letter b ∈ Σ Q choose a unique letter a ∈ A such that φ(a) = b and let A Q be the subset of A consisting of all those chosen letters. Clearly the restriction φ of φ to A Q is a bijection from A Q onto Σ Q . Consider the extension of φ -denoted by the same symbol -to

A * Q which is a bijective homomorphism to Σ * Q . Let P = i λ i φ -1 (v i ). Then clearly φ(P ) = Q, so that φ(P ) = Q. Furthermore, since Q ∈ ker l * Σ Q and |A Q | = |Σ Q | part (ii)
applied for the bijection φ implies that P also lies in ker l * A Q and hence in ker l * A . Suppose now that |A| > |Σ|. We can consider three distinct letters a, b, c ∈ A and two distinct letters e, f ∈ Σ in such a way that, without loss of generality, φ(a) = e and φ(b

) = φ(c) = f . Consider the word w = abca. Then w ∈ φ -1 (ker l * Σ ) since clearly φ(w) = ef 2 e is a palindrome of length 4, but w ∈ ker l * A since l * A (w) = abca -baca -2bca 2 + 2cba 2 + caba -acba = 0. 2
Consider a two-lettered alphabet Σ = {0, 1}. For each subset B of A let φ B be the literal morphism from A * onto Σ * defined as φ B (a) = 1, when a ∈ B and φ B (a) = 0, otherwise. For brevity when B = {b} we write φ b instead of φ {b} . Let us also denote the set of palindromes of length n in A * and Σ * by P al n (A) and P al n (Σ), respectively. Lemma 2.12 Let u, v ∈ A * of common length and a, b be distinct elements of A.

(i) φ a (u) = φ a (v), for each a ∈ A, if and only if u = v. (ii) If φ a (u) ∈ P al n (Σ) for each a ∈ A, then u ∈ P al n (A). (iii) If φ {a,b} (u) = φ {a,b} (v) and φ a (u) = φ a (v) then φ b (u) = φ b (v).
(iv) If φ {a,b} (u) and φ a (u) lie in P al n (Σ) then φ b (u) does also.

Proof: For (i) and (iii) it suffices to check the case where u, v ∈ A. Then (i) follows directly from the definition of the morphism φ a . For (iii) if u, v ∈ {a, b} the result is clear, whereas if u, v ∈ {a, b} we necessarily obtain u = v = a or u = v = b and the result follows. Parts (ii) and (iv) follow respectively from (i) and (iii) for v = ũ and the fact that φ(w) = φ( w) for each literal morphism φ and each word w ∈ A * which is easily proved by induction on |w|.

2

Proof of Reduction Theorem 2.10.: Suppose that Conjecture 2.9 is true for a two lettered alphabet Σ = {0, 1}. We will show that it also holds for any finite alphabet A with |A| > 2. Suppose that u, v ∈ A * with |u| = |v| = n > 1 and that both polynomials l * (u) and l * (v) are non-zero.

(

) l * (u) = l * (v). It means that u -v ∈ ker l * A . 1
Then by by Lemma 2.11 (i), for any subset ∈ P al n (Σ). In the former case the fact that φ c (u), φ c (v) ∈ P al n (Σ) and Lemma 2.12 (iv) yield φ d (u), φ d (v) ∈ P al n (Σ), which contradicts the assumption that d ∈ D. In the latter case Lemma 2.12 (iii) finally yields φ c (u) = φ c (v), as required.

B of A we get φ B (u -v) ∈ ker l * Σ , obtaining l * (φ B (u)) = l * (φ B (v)). We consider two cases. (i) n is even. Our aim is to show that u = v. If l * (φ B (u)) = l * (φ B (v)) = 0, then Conjecture 2.9 yields φ B (u) = φ B (v) / ∈ P al n (Σ). If, on the other hand, l * (φ B (u)) = l * (φ B (v)) = 0 both φ B (u)
(ii) n is odd. Our aim is to show that either u = v or u = ṽ. First we show that either φ B (u

) = φ B (v) or φ B (u) = φ B (ṽ). If l * (φ B (u)) = l * (φ B (v)) =
0 this follows immediately by Conjecture 2.9 which is assumed to hold for Σ. If, on the other hand, l * (φ

B (u)) = l * (φ B (v)) = 0 then both φ B (u) and φ B (v) lie in {0 n , 1 n }. We claim that φ B (u) = φ B (v).
If this is not the case, without loss of generality, φ B (u) = 1 n and φ B (v) = 0 n . By the definition of φ B it follows that alph(u) ⊆ B and alph(v) ⊆ A \ B. On the other hand having assumed that l * (u) = l * (v) = 0 we also get alph(u) = alph(v) and we reach a contradiction. For our fixed pair (u, v) define the sub-alphabets E and F of A as

E = {a ∈ A : φ a (u) = φ a (v)} and F = {a ∈ A : φ a (u) = φ a (ṽ)}.
(2.10)

It follows that A = E ∪ F . It remains to show that either E = A or F = A. Suppose, for the sake of contradiction, that e ∈ E \ F and f ∈ F \ E. Then if we let B = {e, f } we either get φ B (u) = φ B (v) or φ B (u) = φ B (ṽ)
. By Lemma 2.12 (iii) the former equality together with the fact that e ∈ E yields φ f (u) = φ f (v), so that f will also lie in E, which is a contradiction since we took f ∈ F \ E. We get a similar contradiction starting from the latter equality.

(

) l * (u) = -l * (v). It means that u + v ∈ ker l * A so by Lemma 2.11 (i) φ B (u + v) ∈ ker l * Σ and therefore l * (φ B (u)) = -l * (φ B (v)), for each subset B of A. 2
The case where n is even is dealt in an analogous way as in case 1(i) before; we leave the details to the reader.

If n is odd, by Conjecture 2.9, we can not have l * (φ B (u)) = -l * (φ B (v)) = 0. Thus for each B ⊆ A both φ B (u) and φ B (v) lie in {0 n , 1 n }. This will hold in particular, for each singleton B = {a}, with a ∈ A. Then if φ a (u) = 1 n for some a ∈ A we obtain u = a n , a contradiction. Therefore φ a (u) = φ a (v) = 0 n for each a ∈ A. Then alph(u) ∩ A = ∅, which also clearly can not hold. 2

3 Calculation of l *

We will now generalize the effective definition (2.6) of l * using the shuffle product of words and calculate the polynomial l * (w) recursively in terms of all factors u of fixed length r ≥ 1 of w. By a factor of a word w we mean a word u such that there exist s, t ∈ A * with w = sut. Let {u i : 0 ≤ i ≤ n -r} be the set of all n -r + 1 consecutive factors of length r ≥ 2 of w. We let

u i = a i v i b i with a i , b i ∈ A and v i ∈ A * . Note that v i b i = a i+1 v i+1 , for 0 ≤ i ≤ n -r -1.
Suppose that the result holds for the factors u i . We have to show that it also holds for factors of length r -1 of w. We let w = s i u i t i for 0 ≤ i ≤ n -r, where s 0 = t n-r = , s 1 = a 0 and t n-r-1 = b n-r . Then | s i | = |s i | = i, for each 0 ≤ i ≤ n -r and our induction hypothesis for factors of length r yields

l * (w) = l * (u 0 )t 0 + n-r-1 i=1 l * (u i ) (-1) i { s i ¡ t i } + l * (u n-r ) (-1) n-r s n-r .
We apply the recursive formula (2.6) on factors u i = a i v i b i and obtain

l * (w) = l * (a 0 v 0 )b 0 -l * (v 0 b 0 )a 0 t 0 + n-r-1 i=1 l * (a i v i )b i -l * (v i b i )a i (-1) i { s i ¡ t i } + l * (a n-r v n-r )b n-r -l * (v n-r b n-r )a n-r (-1) n-r s n-r . Since v i b i = a i+1 v i+1 for 0 ≤ i ≤ n -r -1, grouping all elements of the form a i v i for 0 ≤ i ≤ n -r we obtain l * (w) = l * (a 0 v 0 ) (-1) 0 b 0 t 0 + l * (a 1 v 1 ) (-1) 1 {a 0 t 0 + b 1 (a 0 ¡ t 1 )} + n-r-1 i=2 l * (a i v i ) (-1) i {b i ( s i ¡ t i ) + a i-1 ( s i-1 ¡ t i-1 )} + l * (a n-r v n-r ) (-1) n-r {b n-r s n-r + a n-r-1 ( s n-r-1 ¡ t n-r-1 )} + l * (v n-r b n-r ) (-1) n-r+1 a n-r s n-r .
Since s i = s i-1 a i-1 and t i-1 = b i t i for 1 ≤ i ≤ n -r (note the extreme cases s 1 = a 0 for i = 1 and t n-r-1 = b n-r for i = n -r), from the recursive definition (2.2) of the shuffle product we get

b i ( s i ¡ t i ) + a i-1 ( s i-1 ¡ t i-1 ) = a i-1 s i-1 ¡ b i t i = s i ¡ b i t i , for all i ∈ [n -r]. Then we immediately obtain l * (w) = l * (a 0 v 0 ) (-1) 0 { ¡ b 0 t 0 } + n-r i=1 l * (a i v i ) (-1) i { s i ¡ b i t i } + l * (v n-r b n-r ) (-1) n-r+1 { s n-r a n-r ¡ } ,
which is precisely the required summation for factors of length r -1 we had aimed for.

2

Remarks. The case where the factors u of the word w are letters (i.e., we are at the bottom level r = 1) seems to be known in a different setting in the literature (see [7, Lemma 2.1], cf. [1, Ex. 4.6.5 (2), p.126]) even for the broader class of free partially commutative Lie algebras. On the other hand, Proposition 3.1 clearly does not hold if we consider trivial factors of w, i.e., factors of length r = 0. In this case the identity 0 = w=st (-1) |s| {s ¡ t}, due to W. Schmidt, holds; see [14, §1.6.4].

We will now use Proposition 3.1 to reobtain -in a non ad hoc way -the result by Duchamp and Thibon [4, §3, p.124] for the calculation of the support of the free Lie ring.

Theorem 3.2

The words that vanish under the adjoint endomorphism l * of the left-normed Lie bracketing l of the free Lie ring are either powers of a single letter with exponent greater than one or palindromes of even length.

Proof: If w = a n , where n ≥ 2, then l * (w) = 0, since l * (w) = l * (a n-1 ) a -l * (a n-1 ) a. For a palindrome w of even length Lemma 2.1 yields 2 l * (w) = 0, hence l * (w) = 0 since we are in characteristic zero.

For the other direction of the theorem consider a word w such that l * (w) = 0. We will argue by induction on the length |w| = n. For n = 2 we necessarily get w = a 2 because if w = ab with a = b then l * (ab) = ab -ba = 0, so the result follows trivially. Let n > 2. We consider two cases. (i) If at least one of the words au and ub (without loss of generality say au) is a power of a single letter we obtain au = a n-1 . It follows that ub = a n-2 b, which contradicts l * (ub) = 0, as the word a n-2 b is neither a power of a single letter nor a palindrome of even length.

(ii) If both au and ub are palindromes of even length and not powers of a single letter we must have au = ss, for some s ∈ A + , so that there exists a t ∈ A * with s = at and u = t ta. But then the word ub = t tab can not be a palindrome of even length since |ub| a = |u| a = 2|t| a + 1 which is an odd positive integer and we obtain another contradiction.

(2) w = a k bvc a l , (a, b, c ∈ A, b, c = a). We consider all factors x of length |v| + 2 of w. Then Proposition 3.1 yields

l * (w) = l * (bvc) (-1) k {a k ¡ a l } + w=sxt (s,t) =(a k ,a l ) l * (x) (-1) |s| {s ¡ t} = (-1) k k + l k l * (bvc) a k+l + w=sxt (s,t) =(a k ,a l ) l * (x) (-1) |s| {s ¡ t}.
For any factorization w = sxt other than the one where (s, x, t) = (a k , bvc, a l ), each shuffle of s and t contains other letters except a so it will be different from a k+l , which will appear only as a shuffle of a k and a l . From this we deduce that the monomials of l * (w) such that a power of the letter a appears In this case every shuffle of the words s and t from each term of the first summand of (3.1) will be equal to a k+1 . Assuming that l * (w) = 0 yields (-1) k+1 l * (vba l )ba k + P a k+1 = 0, for some polynomial P ∈ Z A . But then l * (vba l ) = P = 0, so by our induction hypothesis the word vba l has to be a palindrome of even length. When v is a power of b this clearly can not happen. It remains to check the case where both bvb and vba l are palindromes of even length. Then |v| b would be an even positive integer in the former case, whereas |v| b = |vba l | b -1 would be odd in the latter case, a clear contradiction.

(ii) Suppose that k = l. If bvb = b q with q an odd positive integer then l * (w) = l * (a k b q a k ) = 2 l * (a k b q a k-1 ) a = 0, so that l * (a k b q a k-1 ) = 0 which is a contradiction since the word a k b q a k-1 can not be a palindrome of even length. So we are finally left with the case where bvb is a palindrome of even length which is what we had originally aimed for. Proof: Consider a word w such that l * (w) = 0. We will argue by induction on the length |w| = n. For n = 2 we clearly get w = a 2 and the result follows trivially. Let n > 2. We consider two cases.

(

) w = aub, (a, b ∈ A, a = b). Then 0 = l * (w) = l * (au) b -l * (ub) a. 1
Since a = b we get l * (au) = l * (ub) = 0. Our first claim is that both letters a and b have to lie in alph(u). Indeed, suppose for the sake of contradiction, that -without loss of generality -a / ∈ alph(u). Let us consider all factors of length 1 of w = aub and apply Proposition 3.1. We obtain

l * (w) = a ub + w=sct c ∈ alph(ub) (-1) |s| c {s ¡ t} .

Since a /

∈ alph(u) and a = b, we have c = a, hence the only monomial of l * (w) that starts with the letter a is the word aub which cannot be canceled and therefore l * (w) = 0, a contradiction.

Having obtained that a, b ∈ alph(u), we get alph(w) = alph(u). Our result then follows since, by our induction hypothesis, |alph(u)| ≤ (n -2)/2 ≤ n/2 .

(2) w = aua, (a ∈ A). We set r(w) = max { |s| : w = sut , |s| = |t| , alph(s) = alph(t) }. Since w starts and ends with the same letter, r(w) is a well defined positive integer. Let p and q be respectively the left and the right factor of w of length equal to r(w). The following example demonstrates that this is indeed possible.

l * Σ (w) = l * Σ (f eg){e ¡ f ef } + l * Σ (egf ){f e ¡ ef } + l * Σ (gf e){ef e ¡ f } = {l * Σ (f eg) + l * Σ (egf ) + l * Σ (gf e)}{ef ef + f ef e}.
All terms in l * Σ (f eg) + l * Σ (egf ) + l * Σ (gf e) cancel out, and therefore we obtain l * Σ (w) = 0. Now consider an arbitrary surjective map φ from A onto Σ and an arbitrary word u ∈ φ -1 ({w}) with alph(u) = A. Without loss of generality we may assume that φ(a) = e, φ(b) = f, φ(d) = g and φ(c) ∈ {e, f }. Indeed if φ(c) = g then alph(u) is either equal to {a, b, c} or to {a, b, d} which in both cases is a proper subset of A. We may also assume that φ(c) = f ; the case φ(c) = e is handled in a similar manner. Then u = apadqar, where p, q and r are either equal to b or c. We will show that l * A (u) = 0. Suppose the contrary. Since r = a we get l * A (padqar) = 0, so by Theorem It is customary for many problems on free Lie algebras to boil down to particular combinatorial questions on the group algebra of the symmetric group. This will also be the case for the Schützenberger problems. We start from the place permutation action of the symmetric group S n on n letters, on the set of words of length n, where if w = x 1 x 2 . . . x n and σ ∈ S n we have

(x 1 x 2 . . . x n ) • σ = x σ(1) x σ(2) . . . x σ(n) .
This is a right action of S n that extends by linearity to a right action of the group ring KS n on the n-th homogeneous component of the free associative algebra K A (e.g., see [14, §8.1]). Viewing each permutation in S n as a word in n distinct letters, the left-normed multi-linear Lie bracketing of the free Lie algebra, denoted by l n , is known as the Dynkin operator and can be viewed as an element of KS n defined by

(x 1 x 2 . . . x n ) • l n = l(x 1 x 2 . . . x n ). (4.1)
For a non-negative integer k let [k] denote the set {1, 2, . . . , k}, when k ≥ 1, or the empty set, when

k = 0. A descent of a permutation σ ∈ S n is a position i ∈ [n -1] for which σ(i) > σ(i + 1). Let Lemma 4.4
The right action of l * n on w is equivalent to the left action of l n to the tabloid τ n • {w}, i.e.,

f ( w • l * n ) = l n • (τ n • {w}) .
Proof: Clearly w • τ n = w so if we apply Lemma 4.2 for σ = τ n we obtain τ n • {w} = { w}. The result then follows from Theorem 4.3.

2

A major implication of the isomorphism established in Theorem 4.3 is the equivalence

w • l * n = 0 ⇐⇒ l n • {w} = 0 , (4.7)
so Problem 1.2 takes the following form.

Problem 4.5 Let m be a positive integer with m = 1. Find all unordered set partitions of [n], written in tabloid form P = I 1 /I 2 / . . . /I r , with the property that P satisfies

l n • P = 0 , (4.8)
where l n is the left-normed multi-linear Lie bracketing viewed as an element of the group ring Z m S n .

A few points need to be clarified here.

1. Theorem 3.3 imposes the restriction r = l(P) ≤ n/2 in (4.8). Fix such a length r. If a specific ordered partition P = (I 1 , I 2 , . . . , I r ) satisfies (4.8) then by Lemma 2.11 (ii) and the equivalence (4.7) all r! ordered partitions formed by permutations of its blocks will also be solutions of (4.8).

Hence it suffices to consider only ordered partitions in tabloid form, i.e., unordered partitions, of length r where 2 ≤ r ≤ n/2 , since the 1-block partition is always a trivial solution of (4.8).

2. If B 1 and B 2 are sub-alphabets of A with B 1 ⊃ B 2 , φ is a literal surjective morphism from B * 1 onto B * 2 and there exists a word w ∈ B * 1 such that l n • {w} = 0 then Lemma 2.11 (i) and the equivalence (4.7) imply that also l n • {φ(w)} = 0. Consequently, if P, Q ∈ Π n , P is a solution of (4.8) and P Q then Q will also satisfy (4.8).

3. In view of the two previous remarks to solve Problem 4.5 we must determine the smallest set of unordered partitions P in tabloid form (4.5) with r parts that satisfy (4.8) and generate all solutions of (4.8) in the sense that every other solution will be a partition Q refined by P and moreover P can not itself be refined by some other solution R of (4.8) with more than r parts. We search for such a set of minimal solutions starting from partitions of length n/2 and moving up on in the Hasse diagram of the partially ordered set (∆ n , ).

For example, when n = 5 and m = 2 one can show that the solutions with 3 parts are the tabloids of the form 1, 3, 5 / 2 / 4 and 1, 5 / 2, 4 / 3 and every solution with 2 parts is generated from those. On the other hand, for n = 7 and m = 2 we have the solution 1, 3, 6 / 2, 5, 7 / 4 with 3 parts which can not be refined by any solution with 4 parts; the latter follows directly from Example 3.5.

In characteristic zero Theorem 3.2 and the equivalence (4.7) yield the following result, which -according to our knowledge -has not been traced in the literature.

Let h n (I) be the image under ψ of the element l n • I; for simplicity we write h n (i) instead of h n ({i}). Let us clarify this definition a bit more. Suppose that l n = σ∈Sn α σ σ. Then we obtain

h n (I) = σ∈Sn α σ ψ(σ • I) = σ∈Sn α σ ψ(σ(I)) = σ∈Sn α σ x σ(I) .
(

The polynomial h n (I) is multi-linear and homogeneous of total degree s.

Let now N be a positive integer with N > n and set

[n + 1, N ] = [N ] \ [n].
It will be useful for us to extend the definition of h n (I) to subsets of [N ]. We do this by using the last equality of (5.1), i.e., h n (I) = σ∈Sn α σ x σ(I) , and by identifying S n with the set of permutations σ ∈ S N that leave the subset

[n + 1, N ] of [N ]
point-wise invariant. We obtain the following technical result. Lemma 5.1 Let n, N be positive integers with n < N and

I ⊆ [N ] such that J = I ∩ [n + 1, N ] = ∅. Then h n (I) = h n (I \ J) x J .
Proof: In view of the aforementioned identification let σ ∈ S n . Then σ(I) is the disjoint union of σ(I \ J) and J since σ(J) = J, so that (5.1) yields

h n (I) = σ∈Sn α σ x σ(I) = σ∈Sn α σ x σ(I\J) x J = σ∈Sn α σ x σ(I\J) x J = h n (I \ J) x J , as required. 2 Lemma 5.2 Let I ⊆ [n].
Then the polynomial h n (I) is recursively defined as

h n (I) =    (-1) i-1 n -1 i -1 {x 1 -x 2 }, if I = {i}; h n-1 (I) -h n-1 (ζ n I), otherwise,
where ζ n denotes the descending cycle (n . . . 2 1).

Proof: For I = {i} Theorem 4.3 and Lemma 2.8 (i) yield

h n (i) = ψ(l n • i ) = ψ f (a i-1 ba n-i ) • l * n = ψ f l * (a i-1 ba n-i ) = (ψ • f ) (-1) i-1 n -1 i -1 {ba n-1 -aba n-2 } = (-1) i-1 n -1 i -1 {(ψ • f )(ba n-1 ) -(ψ • f )(aba n-2 )} = (-1) i-1 n -1 i -1 {(ψ(1) -ψ(2)} = (-1) i-1 n -1 i -1 {x 1 -x 2 }.
When |I| > 1 we argue by induction on n, where n ≥ 2. The case n = 2 follows trivially. Using the multiplicative formula (4.2) for l n the induction step yields

h n (I) = ψ(l n • I) = ψ l n-1 (1 -ζ n ) • I = ψ l n-1 • I -l n-1 • (ζ n I) = h n-1 (I) -h n-1 ζ n I . Note that if n ∈ I or 1 ∈ I we obtain h n-1 (I) = h n-1 (I\{n}) x n and h n-1 (ζ n I) = h n-1 (ζ n I\{n}) x n , respectively, by Lemma 5.1. 2
Proposition 5.3 Let I be a subset of [n] of cardinality s. The binomial x 1 -x 2 divides h n (I). The corresponding quotient, which we denote by p n (I), is a multi-linear polynomial of total degree s -1 given by the recursive formula

p n (I) =    (-1) i-1 n -1 i -1 , if I = {i};
(I) = h n-1 (I \ J) x J -h n-1 (ζ n I \ K) x K . By our induction hypothesis we get h n-1 (I \ J) = (x 1 -x 2 ) • p n-1 (I \ J) and h n-1 (ζ n I \ K) = (x 1 -x 2 ) • p n-1 (ζ n I \ K). Our result then follows if we set p n (I) = p n-1 (I \ J) x J -p n-1 (ζ n I \ K) x K . 2
We give the name Pascal descent polynomial to p n (I) since it yields a signed binomial coefficient when |I| = 1 and it originates from the additive formula (4.3) which relates to the descent sums

D [k-1] , for k ∈ [n].
By Lemma 4.4, the analogue of Lemma 2.1 for Pascal descent polynomials is given by the equation

p n (τ n (I)) = (-1) n+1 p n (I), (5.2)
where τ n is the involution of S n defined in (4.6). In particular, if n is even and τ n (I) = I then p n (I) = 0.

The following result yields a recursive decomposition of the polynomial p n (I).

p n (I) = (-1) k+1 l i=0 k + i i p n-k-1-i (D) • x n-k-i + k j=0 (-1) j l + j j p n-l-1-j (D j ) • x n-l-j ,
where D = {a 2 -a 1 , a 3 -a 1 , . . . , a d -a 1 } and D j = {a 1 -j, a 2 -j, . . . , a d-1 -j}, for each j = 0, . . . , k.

Proof: We apply Proposition 5.3. The case where a 1 = 1 and a d = n follows trivially. The cases a 1 = 1, a d < n and a 1 > 1, a d = n follow by an immediate induction on n. If 1 < a 1 and a d < n the induction on n is a bit more tedious. For n = 3 the result is true; one can check it easily for I = {1, 2} and I = {2, 3}. Suppose that it holds for n = m. We will show that it also holds for n = m + 1. Setting k = a 1 -1 and l = m + 1 -a d , Proposition 5.3 and our induction hypothesis yield

p m+1 (I) = p m (I) -p m ({a 1 -1, a 2 -1, . . . , a d -1}) = (-1) k+1 l-1 i=0 k + i i p m-k-1-i (D) • x m-k-i + k j=0 (-1) j l -1 + j j p m-l-j (D j ) • x m-l-j+1 + (-1) k+1 l i=0 k -1 + i i p m-k-i (D) • x m-k-i+1 + k-1 j=0 (-1) j+1 l + j j p m-l-1-j (D j+1 ) • x m-l-j = (-1) k+1 l i=1 k + i -1 i -1 p m-k-i (D) • x m-k-i+1 + l i=0 k + i -1 i p m-k-i (D) • x m-k-i+1 + k j=0 (-1) j l -1 + j j p m-l-j (D j ) • x m-l-j+1 + k j=1 (-1) j l -1 + j j -1 p m-l-j (D j ) • x m-l-j+1 = (-1) k+1 l i=1 k + i -1 i -1 + k + i -1 i p m-k-i (D) • x m-k-i+1 + p m-k (D) • x m-k+1 + k j=1 (-1) j l -1 + j j + l -1 + j j -1 p m-l-j (D j ) • x m-l-j+1 + p m-l (D 0 ) • x m-l+1 = (-1) k+1 l i=1 k + i i p m-k-i (D) • x m-k-i+1 + k + 0 0 p m-k (D) • x m-k+1 + k j=1 (-1) j l + j j p m-l-j (D j ) • x m-l-j+1 + (-1) 0 l + 0 0 p m-l (D 0 ) • x m-l+1 = (-1) k+1 l i=0 k + i i p m-k-i (D) • x m-k-i+1 + k j=0 (-1) j l + j j p m-l-j (D j ) • x m-l-j+1 , as required. 2
By way of example let us calculate p 6 (I) for the subset I = {2, 3, 5} of [START_REF] Graham | Concrete Mathematics : a foundation for computer science[END_REF]. We write p 6 (2, 3, 5) for brevity and by Proposition 5.4 we obtain

p 6 (2, 3, 5) = 1 + 0 0 p 4 (1, 3)•x 5 + 1 + 1 1 p 3 (1, 3)•x 4 + 1 + 0 0 p 4 (2, 3)•x 5 - 1 + 1 1 p 3 (1, 2)•x 4 .
Clearly p 4 (2, 3) = 0 since the subset {2, 3} of [START_REF] Duchamp | Le support de l'algèbre de Lie libre[END_REF] corresponds to the even palindrome ab 2 a. For p 3 (1, 2) we obtain p 3 (1, 2) = p 2 (1, 2) -p 2 (1) • x 3 . Again {1, 2} = [START_REF] Duchamp | Noncommutative symmetric functions III: Deformations of Cauchy and convolution algebras[END_REF] corresponds to the word b 2 so we have p 2 (1, 2) = 0, hence p 3 (1, 2) = -(-1) 1-1 2-1 1-1 x 3 = -x 3 . For the remaining terms we have

p 3 (1, 3) = p 2 (1) • x 3 -p 2 (2) • x 3 = (-1) 1-1 2-1 1-1 x 3 -(-1) 2-1 2-1 2-1 x 3 = 2x 3 and consequently p 4 (1, 3) = p 3 (1, 3) -p 3 (2) • x 4 = 2x 3 -(-1) 2-1 3-1 2-1 x 4 = 2x 3 + 2x 4 .
Summing up we finally obtain

p 6 (2, 3, 5) = 1 • (2x 3 + 2x 4 ) • x 5 + 2 • (2x 3 ) • x 4 -2 • (-x 3 ) • x 4 = 6x 3 x 4 + 2x 3 x 5 + 2x 4 x 5 .
Observe that the greatest common divisor of the coefficients of p 6 (2, 3, 5) is equal to 2, hence the word ab 2 aba of length 6, that corresponds to I, has c(w) = 2 and therefore does not lie in the support of the free Lie algebra over a field of characteristic 2.

By Theorem (i) and the equivalence (4.7) established by Theorem 4.3, if we consider words on a two-lettered alphabet Problem 1.2 will be equivalent to the following. (ii) In particular if m is a prime number p, n = p e and p |I| then p n (I) ≡ 0 (mod m).

Proof: (i) We need to relate the polynomial h n (I) ∈ Z[x 1 , x 2 , . . . , x n ] with the integer N n (I). Let |I| = s. We claim that if we set x 1 = 1 and

x 2 = x 3 = • • • = x n = t in h n (I) we obtain the polynomial specialization h n (I)(1, t, t, . . . , t) = N n (I) t s-1 -N n (I) t s . (5.3) If (5.3) is true then it is evident that m | N n (I). Since h n (I) = (x 1 -x 2 ) p n (I) by Proposition 5.3, equation (5.3) yields p n (I)(1, t, t, . . . , t) = N n (I) t s-1 . (5.4)
Thus N n (I) may be given a combinatorial interpretation as the sum of the coefficients appearing in all the monomials of p n (I).

To prove our claim we use the additive formula (4.3) for l n . Since h n (I) = ψ(l n • I) we obtain

h n (I) = n k=1 (-1) k-1 ψ(D [k-1] • I ). (5.5)
A typical element of D [k-1] is a permutation π which, when viewed as word in n distinct letters from [n], is written as π = j 1 j 2 . . . j k-1 j k j k+1 . . . j n-1 j n ,

where

j 1 > j 2 > • • • > j k-1 > j k = 1 < j k+1 < • • • < j n-1 < j n . Clearly |D [k-1] | = n -1 k -1 and
ψ(π • I) = x ji 1 x ji 2 • • • x ji s , when I = {i 1 , i 2 , . . . , i s }. Setting x 1 = 1 and x 2 = x 3 = • • • = x n = t we obtain ψ(D [k-1] • I)(1, t, t, . . . , t) =            n -1 k -1 t s-1 , if k ∈ I; n -1 k -1 t s , otherwise .
(5.7)

Summing up all these elements by (5.5) we obtain (ii) If u, v is a twin pair of words with respect to L Zm (A) then N n (I) ≡ N n (J) (mod m).

h n (I)(1, t, t, . . . , t) = i∈I (-1) i-1 n -1 i -1 t s-1 + i / ∈I (-1) i-1 n -1 i -1 t s and our claim follows since i∈I (-1) i-1 n -1 i -1 + i / ∈I (-1) i-1 n -1 i -1 = n i=1 (-1) i-1 n -1 i -1 = 0,
(iii) If u, v is an anti-twin pair of words with respect to L Zm (A) then N n (I) ≡ -N n (J) (mod m).

Proof: Part (i) is a direct consequence of Proposition 5.6. For parts (ii) and (iii) we use Theorem 2.7 (ii).

For a twin pair we obtain l * (u) -l * (v) ∈ (m) Z A which yields p n (I) -p n (J) ≡ 0 (mod m) by Theorem 4.3 and our result follows by (5.4). For an anti-twin pair we argue similarly for the polynomial l * (u) + l * (v) and its commutative analogue p n (I) + p n (J).

Remarks. The invariant N n (I) is a partial sum of signed binomial coefficients from the n-th row of the Pascal triangle (starting to count from n = 0). Considering this row mod m, Corollary 5.7 (i) poses the requirement that the signed sum of the entries in the positions appearing in I has to be different from zero mod m in order that the word w corresponding to I lies in the support of L Zm (A). In the binary case this simply means that the digit 1 is allowed to appear an odd number of times in these positions; note that the number of appearances of 1's in each row of the Pascal triangle mod 2 is equal to 2 b(n) , where b(n) is the number of occurrences of 1 in the binary representation of n (e.g., see [START_REF] Wolfram | Geometry of binomial coefficients[END_REF]).

The condition of Corollary 5.7 (i) is sufficient but not necessary since there exist many words w with m | N n (I) that also lie in the support of L Zm (A). For example, for m = 2 and w = a 2 b 2 a we get I = I(w) = {2, 3} and N 5 (I) = 2, but w lies in the support of L Z2 (A) since p 5 (I) = x 3 + x 4 and c(w) = 1. On the other hand, for |I| = 1 it is a necessary and sufficient condition identified with our theoretical characterization of the support of L Zm (A) and is checked with Kummer's Lemma. Note also that it is even possible to have N n (I) = 0 with p n (I) = 0, e.g., for w = a 2 b 2 a 2 ba 2 we get I = {3, 4, 7} and N 9 (I) = 0. Similar examples which demonstrate that the converse of Corollary 5.7 (ii) and (iii) does not hold, can be found. For example, consider the words u = ab 3 a 2 ba 2 and v = a 2 b 2 a 2 b 2 a of length 9 with corresponding I = I(u) = {2, 3, 4, 7} and J = J(v) = {3, 4, 7, 8}. Then clearly N 9 (I) = N 9 (J) = -8, but p 9 (I) = p 9 (J), as one can check by Proposition 5.4, so that l * (u) = l * (v) and hence the the words u, v are not twin. (ii) p n (I) = -p n (J) if and only if n is even and I = τ n (J).

For s = 1, i.e., when I = {i} and J = {j}, Conjecture 5.8 holds as a special case (for r = n -1, k = i-1 and l = j -1) of the fact that r k = r l if and only if k = l or k = r -l. The "if" part, known as the symmetry identity, follows directly from the definition of binomial coefficients and the "only if" part follows from the inequality r k < r k+1 when 1 ≤ k+1 ≤ r/2 . This is another indication showing that the Pascal descent polynomial p n (I) is indeed an extension of the usual notion of the binomial coefficient.

Further Research

Various equivalent forms of Conjecture 2.9 on twin and anti-twin words -which, in view of Reduction Theorem 2.10, is enough to prove on a two-lettered alphabet -have been presented in this article and we strongly believe that this will finally be resolved. More precisely one can use the recursive formula of Proposition 3.1 in a manner similar to the proofs of Theorem 3.2 and Theorem 3.3, but as it has turned out so far, a lot more cases in combinatorics on words appear in such a consideration.

In view of Remark 2.4, another equivalent to Conjecture 2.9 which seems to be worth investigating is the following. Suppose that K is a Q-algebra and u and v are words of common multi-degree and length n on a two-lettered alphabet which are not powers of a single letter or palindromes of even length. Then the binomial u -v (respectively u + v) can be expressed as a K-linear combination of proper shuffles if and only if either u = v or n is odd and u = ṽ (respectively if n is even and u = ṽ).

One is challenged to check this using one of the two well known bases of the shuffle algebra, namely the triangular Z-basis {Q w : w not a Lyndon word}, originally due to Radford [START_REF] Radford | A natural ring basis for the shuffle algebra and an application to group schemes[END_REF], where

Q w = 1 i 1 !i 2 ! • • • i k ! l 1 ¡i 1 ¡ l 2 ¡i 2 ¡ • • • ¡ l k ¡i k , and w = l i1 1 l i2 2 • • • l i k k
is the unique decreasing decreasing factorization (with respect to the lexicographical order in A + ) of w as a product of Lyndon words with l 1 > l 2 > • • • > l k and i 1 , i 2 , . . . , i k ∈ N (see [14, §6.1]); and the Lie polynomial Q-basis that corresponds to the decomposition n≥0 V n , where V n denotes the subspace of Q A generated by the shuffle products of n Lie polynomials (see [14, §6.5

.1]).

A completely different approach via Pascal descent polynomials, is to use Proposition 5.4 in order to be able to resolve Conjecture 5.8. We do not yet know how this could lead to a complete solution of Problem 5.5 (probably combined with successive applications of our condition in Proposition 5.6 involving the invariant N n (I)) but we are certain that the right framework for such a search is within the geometry of the Pascal triangle mod m, which after all is needed even in the simple case where |I| = 1.

Finally, in the case where m = 2 -the smallest instance of Problem 5.5 -we have made some computations using the computer algebra system GAP 4 and have obtained all solutions up to n = 12. (A list of those solutions up to n = 10 is presented in the Appendix.)

  1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

a 3 b 2 =

 2 [ a, [ a, [ [ a, b ], b ] ] ] and therefore (-P a 3 b 2 , a 2 b 2 a) = 1.

  Theorem 2.6 (i) and part (i) of this lemma yield c(a k ba l ) = k+l k and the result follows by Kummer's lemma.2

  and φ B (v) lie in P al n (Σ). Restricting ourselves initially to singleton subsets B = {a} we define, for our fixed words u and v, the sub-alphabets C and D of A asC = {a ∈ A : φ a (u), φ a (v) ∈ P al n (Σ)} and D = {a ∈ A : φ a (u) = φ a (v) ∈ P al n (Σ)}. (2.9)By construction A = C ∪ D and C ∩ D = ∅. Suppose that C = ∅. Then A = D and the result follows immediately by Lemma 2.12 (i). If C = ∅ then also D = ∅, since otherwise A = C and by Lemma 2.12 (ii) it would follow that u, v ∈ P al n (A), contradicting our original assumption that both l * (u) and l * (v) are non-zero. Let c be an arbitrary element of C. In view of Lemma 2.12 (i) it suffices to show that φ c (u) = φ c (v). Let d ∈ D and set B = {c, d}. Then either φ B (u) and φ B (v) lie in P al n (Σ) or φ B (u) = φ B (v) /

Proposition 3 . 1

 31 Let w be a word and r be a positive integer with r ≤ |w|. Consider the set of all factors u of length r of w. Then l * (w) = w=sut |u|=r l * (u) (-1) |s| {s ¡ t} . Proof: Let |w| = n. We argue by induction on k = n -r. Clearly 0 ≤ k ≤ n -1. Note that for k = 0 the result is trivial since s = t = . Also for k = 1 it follows from the recursive definition (2.6) of l * since the factors of length n -1 of w = aub are just the words au and ub.

( 1 )

 1 w = aub, (a, b ∈ A, a = b). Then 0 = l * (w) = l * (au) b -l * (ub) a. Since a = b we get l * (au) = l * (ub) = 0. By our induction hypothesis we have to consider two subcases.

  as a right factor with maximum possible exponent are precisely the monomials in k + l k l * (bvc) a k+l . Now, the assumption l * (w) = 0 yields k + l l l * (bvc) = 0 and since we are in characteristic zero we immediately obtain l * (bvc) = 0. Then by our induction hypothesis we get b = c and v is a power of b or a palindrome of even length. Two subcases have to be considered. (i) If k = l (without loss of generality say k < l) we consider factors y of length |v| + l + 1 of w and apply again Proposition 3.1. We obtain l * (w) = w=syt (s,t) =(a k b, ) l * (y) (-1) |s| {s ¡ t} + l * (vba l ) (-1) k+1 b a k . (3.1)

2 Theorem 3 . 3

 233 Let K be a commutative ring with unity and suppose that l * (w) = 0 for a word w ∈ A * . Then |alph(w)| ≤ |w|/2 .

2 Corollary 3 . 4 2

 2342 There are three cases to consider: either w = pq; w = pbq with b ∈ A; or finally w = pbucq, where u ∈ A * , b, c are distinct letters and at least one of them, without loss of generality say b, does not lie in alph(p). In the first case our result follows immediately since clearly |alph(w)| = |alph(p)| ≤ |p| = |w|/2 = |w|/2 . Similarly in the second one |alph(w)| ≤ |alph(p)| + 1 ≤ |p| + 1 = |w|/2 . Finally in the third one we have alph(w) = alph(pbuc) = alph(p) ∪ alph(buc), hence |alph(w)| ≤ |alph(p)| + |alph(buc)|. Since b = c, Case (1) yields |alph(buc)| ≤ |buc|/2 , so that |alph(w)| ≤ |p| + |buc|/2 = (2|p| + |buc|)/2 = |w|/2 . If w is a word of A * with |alph(w)| > |w|/2 then c(w) = 1. Proof: Suppose that c(w) = m where m is a non-negative integer with m = 1. If m = 0 then l * (w) = 0 over Z, hence by Theorem 3.3 for K = Z we get |alph(w)| ≤ |w|/2 , a contradiction. If m > 1 then l * (w) ∈ (m)Z A by Theorem 2.7 (i). Thus if l * is the adjoint of the left-normed Lie bracketing l over Z m , we get l * (w) = 0. Once more Theorem 3.3, this time for K = Z m , yields |alph(w)| ≤ |w|/2 , the same contradiction. Recall that by Lemma 2.11 (iii) if A and Σ are finite alphabets with |A| > |Σ| ≥ 2 and φ is a literal morphism from A * onto Σ * then φ(ker l * A ) = ker l * Σ and ker l * A is a proper subset of φ -1 (ker l * Σ ). It is worth asking the following: is it possible to have a solution w of the equation l * Σ (w) = 0 with alph(w) = Σ that can not be the image, under any literal surjective morphism φ : A * Σ * , of a corresponding solution u of the equation l * A (u) = 0 with alph(u) = A? If |w| = n Theorem 3.3 implies that our question makes sense when in fact n/2 ≥ |A| > |Σ|.

Example 3 . 5

 35 Set K = Z 2 , A = {a, b, c, d}, Σ = {e, f, g} and w = ef egf ef . Then w ∈ ker l * Σ but for each literal morphism φ from A * onto Σ * no word u with alph(u) = A and φ(u) = w lies in ker l * A . Proof: All calculations are made over Z 2 . We apply Proposition 3.1 for all factors of length 3 in w. Since l * (ef e) = l * (f ef ) = 0 and e ¡ f ef = f e ¡ ef = ef e ¡ f = ef ef + f ef e, we get

3 . 3 2 4

 332 |alph(padqar)| ≤ 3. On the other hand, clearly alph(padqar) = alph(u) = A, so that |alph(padqar)| = 4 and we reach a contradiction. Combinatorial interpretation of l *

p n- 1

 1 (I) -p n-1 (ζ n I), otherwise, where whenever I is a subset of [n] with n ∈ I we set p n-1 (I ) = p n-1 (I \ {n}) x n . Proof: For s = 1 the result follows immediately immediately by Lemma 5.2. For s > 1 we argue by induction on n. Set J = I ∩ {n} and K = ζ n I ∩ {n}. Then clearly x J = 1 when n / ∈ I and x K = 1 when 1 / ∈ I. By Lemma 5.2 we have h n (I) = h n-1 (I) -h n-1 (ζ n I), so by Lemma 5.1 we obtain h n

Proposition 5 . 4

 54 Let I = {a 1 , a 2 , . . . , a d } be a proper subset of [n] of cardinality d ≥ 2. Set k = a 1 -1 and l = n -a d . Then

Problem 5 . 5

 55 Let m be a non-negative integer with m = 1. Find all set partitions J / I of [n] with the property that p n (I) ≡ 0 (mod m) .For m = 0 Proposition 4.6 implies that the only solutions to Problem 5.5 are -except from the trivial solution where I = ∅, for each n -all the subsets I of [n] fixed by the involution τ n defined by (4.6), when n is even.For m > 1 our next result provides a necessary condition -stated explicitly on n, m and I -for p n (I) ≡ 0 (mod m) to hold. Proposition 5.6 Let m and n be positive integers with m > 1, I be a subset of [n] and N n (I) be the integer defined as N n (I) = i∈I (-1) i-1 n -1 i -1 . (i) If p n (I) ≡ 0 (mod m) then m | N n (I).

1 t=0(p - 1 ) p t and k = e- 1 t=0k 1 ( 2 Corollary 5 . 7

 1111257 by the binomial theorem.(ii) We claim that N n (I) = s. If this is true the result will follow immediately by part (i) and the assumption p s. To prove the claim it suffices to show that for each k ∈ {0, . . . , p e -1} (-1) k p e -1 k ≡ 1 (mod p).(5.8)We write p e -1 and k in base p respectively as p e -1 = et p t , where k t ∈ {0, 1, . . . , p -1}. By Lucas correspondence theorem it is enough to show that (-1) l p -1 l ≡ 1(mod p), for each l ∈ {0, . . . , p -1}. The latter follows from the fact that p p mod p), and a straightforward induction on l. Let u, v and w be words of length n with alph(w) = {a, b}; I, J and K be the subsets of [n] consisting of the positions that b occurs in u, v and w, respectively and N n (I), N n (J) and N n (K) be defined as in Proposition 5.6. If m is a non-negative integer with m = 1 then (i) If m N n (K) the word w lies in the support of the free Lie algebra L Zm (A). In particular, if m = p, a prime number and n = p e every word w with |K| = s and p s lies in the support of L Zm (A).

Finally, in view

  of Reduction Theorem 2.10, Conjecture 4.7 for tabloids boils down to the following one for Pascal descent polynomials. Conjecture 5.8 Let I and J be subsets of [n] of cardinality s ≤ n/2 such that p n (I) = 0 and p n (J) = 0. Then (i) p n (I) = p n (J) if and only if I = J or n is odd and I = τ n (J).

  : A polynomial P ∈ ker l * if and only if Let u, v, w ∈ A * . Then (i) A word w does not lie in the support of L K (A) if and only if w ∈ ker l * .(ii) A pair of words u, v is twin (respectively anti-twin) with respect to L K (A) if and only if the binomial u -v (respectively u + v) ∈ ker l * . Let K be a commutative ring with unity and l 1 , l 2 , . . . , l r be the Lyndon words of length n on the alphabet A. Then the set {l * (l 1 ), l * (l 2 ), . . . , l * (l r )} is a K-basis of the image under l * of the n-th homogeneous component of K A . Suppose that, without loss of generality, l 1 < l 2 < • • • < l r with respect to the lexicographic ordering in A + . Consider also the corresponding Lyndon basis {P l1 , P l2 , . . . , P lr } of the n-th homogeneous component L n Z (A) of L Z (A), where each P li is written in the form P li = l i + (l i ) = l * (w). This means that for all u ∈ A n

		r
	unique coefficients ξ 1 , ξ 2 , . . . , ξ r ∈ K such that (l * (l i ), u) ξ i = (l * (w), u), which by (2.5) is equivalent to i=1 ξ i l we must have r	r
	i=1		i=1
		(P, w) l * (w), u =	(P, w)(l * (w), u) = 0,
		w∈A *	w∈A *
	for each u ∈ A * . By (2.5) and (2.4) the latter means that (P, l(u)) = 0, for each u ∈ A * . Since
	{l(u) : u ∈ A * } is a K-linear generating set for L K (A), this is equivalent to having (P, Q) = 0 for each
	Q ∈ L K (A), which means precisely that P ∈ L K (A) ⊥ .	2
	Lemma 2.3 Proof: (i) It follows from Lemma 2.2 and the fact that a word w does not lie in the support of L K (A) if
	and only if (Q, w) = 0, for each Lie polynomial Q.
	(ii) Suppose that u and v are twin words. By definition this means that (Q, u) = (Q, v), for every
	Q ∈ L K (A), i.e., the binomial u -v ∈ L K (A) ⊥ and the result follows from Lemma 2.2. An analogous
	argument is used for anti-twin pairs and the binomial u + v.	2
	Remark 2.4 By a result of Ree [13] (cf. [14, Theorem 3.1]) it is known that if K is assumed to be a
	commutative Q-algebra, where Q denotes the field of rational numbers, a polynomial with zero constant
	term lies in L K (A)	⊥ -and hence not in the support of L K (A) in view of Lemma 2.2 and Lemma 2.3 -if
	and only if it is a K-linear combination of proper shuffles.
	Proposition 2.5 Proof: t>li	c t t, for suitable
	c t ∈ K (see [9, Lemma 5.3.2]). Let w now be a given word of length n; we have to show that there exist

*

  {1, 5}, {1, 7}, {2, 4}, {2, 6}, {3, 5}, {3, 7}, {4, 6} s= 3 : {1, 3, 6}, {1, 4, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 5} n= 8 s= 2 : {1, 5}, {1, 7}, {1, 8}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {3, 5}, {3, 6}, {3, 7}, {4, 5}, {4, 6}, {4, 7}, {4, 8} s= 4 : {1, 2, 7, 8}, {1, 3, 5, 7}, {1, 3, 5, 8}, {1, 3, 6, 8}, {1, 4, 5, 8}, {1, 4, 6, 8}, {2, 3, 5, 7}, {2, 3, 6, 7}, {2, 4, 5, 7}, {2, 4, 6, 7}, {2, 4, 6, 8}, {3, 4, 5, 6} n= 9 s= 1 : {2}, {3}, {4}, {5}, {6}, {7}, {8} s= 2 : {1, 9}, {2, 4}, {2, 6}, {2, 8}, {3, 6}, {3, 7}, {4, 6}, {4, 7}, {4, 8}, {6, 8} s= 3 : {1, 5, 9}, {2, 4, 6}, {2, 4, 8}, {2, 5, 7}, {2, 5, 8}, {2, 6, 8}, {3, 5, 7}, {3, 5, 8}, {4, 5, 6}, {4, 6, 8} s= 4 : {1, 2, 8, 9}, {1, 3, 5, 9}, {1, 3, 6, 9}, {1, 3, 7, 9}, {1, 4, 6, 9}, {1, 4, 7, 9}, {1, 5, 7, 9}, {2, 3, 4, 8}, {2, 3, 7, 8}, {2, 4, 6, 8}, {2, 6, 7, 8}, {3, 4, 6, 7} n= 10 s= 1 : {3}, {4}, {5}, {6}, {7}, {8} s= 2 : {1, 9}, {1, 10}, {2, 9}, {2, 10}, {3, 7}, {3, 8}, {4, 7}, {4, 8}, {5, 6} s= 3 : {1, 5, 9}, {2, 5, 9}, {2, 6, 9}, {2, 6, 10}, {3, 5, 7}, {4, 5, 7}, {4, 6, 7}, {4, 6, 8} s= 4 : {1, 2, 9, 10}, {1, 3, 5, 9}, {1, 3, 6, 9}, {1, 3, 6, 10}, {1, 3, 7, 9}, {1, 3, 8, 10}, {1, 4, 6, 9}, {1, 4, 6, 10}, {1, 4, 7, 10}, {1, 5, 6, 10}, {1, 5, 7, 9}, {1, 5, 7, 10}, {1, 5, 8, 10}, {2, 3, 5, 9}, {2, 3, 7, 9}, {2, 3, 8, 9}, {2, 4, 5, 9}, {2, 4, 6, 9}, {2, 4, 6, 10}, {2, 4, 7, 9}, {2, 4, 8, 9}, {2, 4, 8, 10}, {2, 5, 6, 9}, {2, 5, 7, 9}, {2, 5, 7, 10}, {2, 5, 8, 10}, {2, 6, 7, 9}, {2, 6, 8, 9}, {2, 6, 8, 10}, {3, 4, 7, 8}, {3, 5, 6, 8}, {4, 5, 6, 7} s= 5 : {1, 3, 4, 5, 9}, {1, 3, 4, 6, 10}, {1, 3, 5, 7, 9}, {1, 3, 5, 7, 10}, {1, 3, 5, 8, 10}, {1, 3, 6, 8, 10}, {1, 4, 6, 8, 10}, {1, 5, 7, 8, 10}, {2, 3, 4, 6, 9}, {2, 3, 5, 7, 9}, {2, 4, 5, 7, 9}, {2, 4, 6, 7, 9}, {2, 4, 6, 8, 9}, {2, 4, 6, 8, 10}, {2, 5, 7, 8, 9},

	n= 5	s= 1 : {2}, {3}, {4}
		s= 2 : {1, 5}, {2, 4}
	n= 6	s= 1 : {3}, {4}
		s= 2 : {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 4}
		s= 3 : {1, 3, 5}, {1, 3, 6}, {1, 4, 6}, {2, 3, 5}, {2, 4, 5}, {2, 4, 6}
	n= 7	s= 1 : {2}, {4}, {6}
		s= 2 : {2, 6, 7, 8, 10}

Acknowledgements

The author wishes to thank Professor G. Duchamp for helpful discussions on this subject -in particular for pointing out Problems 1.3 and 1.4 on twin and anti-twin words -during the author's visit at LIPN (Laboratoire d' Informatique de Paris-Nord) at the University of Paris XIII. He is also indebted to professor A. Konovalov for his advice on computations using GAP 4 to implement the action of l n on subsets of [n].

D(σ) be the set of all descents of σ and for X ⊆ [n -1] let D X = D(σ)=X σ ∈ KS n . Then the following formulae for l n are well known (see [START_REF] Reutenauer | Free Lie Algebras[END_REF]Theorem 8.16]):

where 1 denotes the identity permutation and ζ k the descending k-cycle (k . . . 2 1). Note that in (4.2) the products στ of permutations σ, τ ∈ S n are to be read from right to left: first τ and then σ. It is well known that the elements D X span a subalgebra of rank 2 n-1 of the group algebra QS n , called the Solomon descent algebra and denoted by D n (e.g., see [START_REF] Schocker | The descent algebra of the symmetric group, Representations of finite dimensional algebras and related topics in Lie theory and geometry[END_REF] and cf. [START_REF] Reutenauer | Free Lie Algebras[END_REF]Chapter 9]). By (4.3) it follows that l n lies in D n . We also define l * n to be the element of KS n such that

where x 1 x 2 . . . x n is a word in n distinct letters and obtain the following result. (ii

Proof: (i) The coefficients β σ and α σ -1 are related via the canonical scalar product in K A defined by (2.4) in the following way:

Setting new variables y i = x σ(i) for i ∈ [n] we have y σ -1 (i) = x i , so we obtain

Our result then follows from this property and part (i).

2

We carry on with some preliminaries on set partitions and tabloids. A composition λ of a positive integer n into r positive parts, written λ |= n, is an ordered sequence (λ 1 , λ 2 , . . . , λ r ) of positive integers such that is the number of blocks r. Let Π r n (respectively ∆ r n ) denote the set of ordered (respectively unordered) partitions of [n] with r blocks and Π n (respectively ∆ n ) be the set of all ordered (respectively unordered) set partitions of [n]. Let also T λ n be the set of ordered partitions of given type λ = (λ 1 , λ 2 , . . . , λ r ), where λ |= n. This is nothing but the set of λ-tabloids. (Note that λ-tabloids are usually defined for λ n as row equivalence classes of Young tableaux of shape λ (see [START_REF] Sagan | The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Second Edition[END_REF]Def. 2.1.4]), but the same can be done in general for λ |= n since the definition of a tableau is extended to compositions in the obvious way (cf. [15, p. 67

, since each element in ∆ r n yields r! distinct elements in Π r n by permuting its blocks. On the other hand, clearly |T λ n | is equal to the multinomial coefficient

Following Sagan in [15, Def. 5.5.7] each π ∈ ∆ r n may be written uniquely in the form of a special ordered partition, called the tabloid form of π, which is defined as

where numbers in each block are written in the natural increasing order; blocks are listed in weakly decreasing order of size and furthermore blocks of equal size are arranged in increasing order of their minimal elements. The type of π is then the integer partition

For example the partition π = {{1, 2}, {4, 7, 8}, {3, 5, 6}} of [START_REF] Kummer | Über die Ergänzungssätze den allgemeinen Reciprocitätsgesetzen[END_REF] is written in tabloid form as P = 3, 5, 6 / 4, 7, 8 / 1, 2 and is of type (3, 3, 2). Let P, Q ∈ Π n . We say that P refines Q and write P Q if each block of P is a subset of some block of Q. The relation on Π n is reflexive and transitive. We have P Q and Q P if and only if Q may be obtained by rearranging the blocks of P . In this case we write P Q and obtain an equivalence relation in Π n . The set of its equivalence classes is then clearly identified with the set ∆ n of unordered set partitions of [n] which inherits the refinement order from Π n . The n-block partition 1 /2 / . . . / n and the 1-block partition 1, 2, . . . , n / appear respectively at the bottom and at the top of the Hasse diagram of the partially ordered set (∆ n , ).

The symmetric group S n acts naturally from the left on the sets ∆ r n , Π r n and T λ n defined above, simply by permuting the entries in the blocks of a set partition or a tabloid. For a commutative ring K with unity let D r n , P r n and T λ n be the K-modules freely generated by the sets ∆ r n , Π r n and T λ n , respectively. Extending the permutation action of S n linearly to D r n , P r n and T λ n these become left permutation KS n -modules.

In Problem 1.2 we search for words w with |w| = n and |alph(w)| = r that vanish under l * . By Lemma 2.11 (ii) if B 1 and B 2 are sub-alphabets of cardinality r of A then ker l * B1 is identified with ker l * B2 . Therefore, without loss of generality, we may fix a sub-alphabet B = {a 1 , a 2 , . . . a r } of A with the natural total order a 1 < a 2 < • • • < a r and consider the set W r n of all words w with |w| = n and alph(w) = B. The mapping w → {w} from W r n to Π r n that sends a word w = x 1 x 2 . . . x n ∈ W r n to the ordered partition {w} = (I 1 (w), I 2 (w), . . . , I r (w)), where for each k ∈ [r] the set I k (w) consists of the positions in [n] where the letter a k occurs in w, is clearly a bijection. Moreover, if λ = (λ 1 , λ 2 , . . . , λ r ) |= n we can also consider the set W λ n of all words w of multi-degree (λ 1 , λ 2 , . . . , λ r ) in B, i.e., |w|

The ordered partition {w} is then a λ-tabloid, hence the restriction of the map w → {w} to W λ n is a bijection between the set of words W λ n and the set T λ n of λ-tabloids. For example, for λ = (3, 3, 1, 1) and B = {a, b, c, d}, the word w = aacbdbba is represented by the tabloid 1, 2, 8 / 4, 6, 7 / 3 / 5. By changing our initial order on B to another one which makes λ = (|w| a1 , |w| a2 , . . . , |w| ar ) an integer partition of n, we may, without loss of generality, assume that λ n and consider only the sets W λ n and T λ n for λ n.

Let W r n be the K-span of W r n in K B and W λ n be the set of all polynomials on B over K of multidegree (λ 1 , λ 2 , . . . , λ r ). The symmetric group S n acts on the sets W r n and W λ n from the right by place permutations. Extending these actions naturally to W r n and W λ n the latter become right permutation modules for S n . We compare the left action of S n on P r n and T λ n with the right action of S n on W r n and W λ n , respectively by the following results. Lemma 4.2 Let w be a word of length n and σ be an arbitrary permutation in the symmetric group S n on n letters. Then

We extend by linearity the bijective mapping w → {w} from W r n to Π r n to a K-module isomorphism f from W r n to P r n defined as f (

Theorem 4.3 The right action of the symmetric group S n on the polynomials W r n (respectively W λ n , where λ n) is equivalent to the left action of S n on the K-space of ordered partitions P r n of [n] into r parts (respectively on λ-tabloids T λ n ). Moreover,

Proof: If we define σ • w = w • σ -1 for σ ∈ S n and w ∈ W r n , we have also a left action of S n on W r n and consequently on W r n . In view of Lemma 4.2 one can show that f (σ

As a result the corresponding left KS n -modules W r n and P r n are isomorphic. The restriction of f to W λ n is an isomorphism of W λ n onto T λ n . The second part of the theorem follows directly from Lemma 4.2 and Lemma 4.1 (i).

2

Consider the involution τ n of the symmetric group S n written as

Proposition 4.6 Let λ n. The λ-tabloids that satisfy the equation

where l n is the Dynkin operator of the free Lie ring, are either the 1-block partition 1, 2, . . . , n / or the tabloids t which, when viewed as partitions of [n], are refined by the tabloid

for n = 2k.

We also present the equivalent of Conjecture 2.9 stated in λ-tabloid form.

Conjecture 4.7 Let λ n, l n be the Dynkin operator of the free Lie ring and t 1 and t 2 be λ-tabloids with both l n • t 1 and l n • t 2 different from zero. Then

(ii) l n • t 1 = -l n • t 2 if and only if n is even and

We conclude this section with a few remarks on the case m = 2. It is easy to show by induction that palindromes of length n > 1, where n might be even or odd, lie in the kernel of l * . The latter correspond of course to tabloids of the form

where n = 2r + 1. By an easy induction on r we also get the hook-shaped solution We conjecture that (4.10) and (4.11) are the only solutions of (4.8) with r + 1 parts when n = 2r + 1.

For n = 2r, except from tabloids of the form (4.9) that correspond to palindromes of even length, there exist other solutions with r parts. For example for n = 6 we have also the solutions

Such a partition is written in tabloid form J / I, so it is uniquely determined by the subset I = {i 1 , i 2 , . . . , i s } of [n] appearing in its second block and will be denoted accordingly by I; when I = {i} for brevity we will write i.

We define a mapping ψ from the set Π 2 n of ordered partitions with 2 parts to the polynomial algebra K[x 1 , x 2 , . . . , x n ] in n commuting variables that sends I -viewed as an ordered partition -to the monomial x I = x i1 x i2 • • • x is . In the extreme case where I = ∅ we set x I = 1. The mapping ψ is extended by linearity to a KS n -module isomorphism, also denoted by ψ, from P 2 n to K[x 1 , x 2 , . . . , x n ], under the natural place permutation actions of the symmetric group S n in each case.

Note added in proof

After the submission of this manuscript we followed the guidelines drawn up in Section 6 and quite recently we have finally managed to resolve Conjecture 2.9 in [START_REF] Michos | On twin and anti-twin words in the support of the free Lie algebra[END_REF] using a combination of techniques from combinatorics of words (mainly the 1st and the 2nd Theorem of Lyndon and Schützenberger) and the shuffle algebra (K A , +, ¡), where K is a commutative Q-algebra (in particular, the left or right residual of shuffles by a Lie polynomial R).


Pavel V Salimov
email: ch.cat.s.smile@gmail.com

On uniform recurrence of a direct product

Keywords: infinite words, uniform recurrence, strong recurrence, symmetric morphisms, Thue-Morse

The direct product of two words is a naturally defined word on the alphabet of pairs of symbols. An infinite word is uniformly recurrent if each its subword occurs in it with bounded gaps. An infinite word is strongly recurrent if the direct product of it with each uniformly recurrent word is also uniformly recurrent. We prove that fixed points of the expanding binary symmetric morphisms are strongly recurrent. In particular, such is the Thue-Morse word.

Introduction

Let Σ = Σ s = {0, 1, . . . , s -1} be a finite alphabet, and x = x 0 x 1 • • • ∈ Σ N0 be an infinite word on Σ with indices in N 0 = N ∪ {0}.

A word u is called a factor or a subword of a word v = v 0 v 1 . . . if u = v i v i+1 . . . v i+n for some i and n. In this case we say the word u occurs in v at position i. A subword u occurs in an infinite word x uniformly if u occurs in x infinitely many times and the distances between contiguous positions where it occurs are bounded by some constant. An infinite word is uniformly recurrent if each its subword occurs in it uniformly.

The given definition of uniform recurrence is a paraphrase in terms of words of the original definition that came from works of Poincaré in classical mechanics and became the fundamental one of dynamics. The reason why it is studied from such a perspective is that the notion of recurrence turns out to be very useful in combinatorial number theory [START_REF] Furstenberg | Recurrence in Ergodic Theory and Combinatorial Number Theory[END_REF]. Applied to infinite words, it allows to prove new Ramsey type results and improve some classical ones like theorems of Hidman, van der Waerden and Szemeredi. At present time, uniform recurrence is a recognized property in factorial language theory, theoretical computer science and symbolic dynamics.

The direct product of two infinite words (or words of the same length) x = x 0 x 1 . . . on Σ and y = y 0 y 1 . . . on ∆ is the word x ⊗ y = x 0 , y 0 x 1 , y 1 . . . on the alphabet Σ × ∆. An infinite word x is strongly recurrent if for each uniformly recurrent infinite word y the product x ⊗ y also is uniformly recurrent. The property of strong recurrence is rare [START_REF] Furstenberg | The mathematical heritage of Henri Poincare[END_REF] and not much is known on this subject. In the present paper we prove that words of some classical construction meet this property. More precisely, we speak of morphic sequences [START_REF] Allouche | Automatic Sequences. Theory, Applications, Generalizations[END_REF].

A morphism ϕ : Σ * → ∆ * is a mapping that obeys the identity ϕ(xy) = ϕ(x)ϕ(y) for all words x, y ∈ Σ * . We usually consider binary, i.e., Σ * 2 → Σ * 2 morphisms. A morphism ϕ : Σ * → ∆ * is an expanding one if for each a ∈ Σ the inequality |ϕ(a)| > 1 takes place.

A morphism is called uniform (m-uniform, where m > 1) if the images of all letters are of the same length (equal to m). An m-uniform morphism ϕ : Σ * → Σ * is symmetric if for each i ∈ Σ we have ϕ(i) = ϕ(0) ⊕ i m , where ⊕ denotes the symbol-by-symbol addition modulo |Σ|. Such a morphism is considered in Example 1. In the rest of the paper, when speaking of a symmetric morphism, we mean a binary symmetric morphism.

Any expanding morphism ϕ : Σ * → Σ * generates the mapping Σ N0 → Σ N0 that maps an infinite word x = x 0 x 1 . . . to the word ϕ(x 0 )ϕ(x 1 ) . . . . We denote it by the same letter ϕ for convenience. When the word ϕ(a) begins with a for some a ∈ Σ, this mapping has fixed points, i.e., words satisfying x = ϕ(x). These are exactly the words that can be obtained as limits lim n→∞ ϕ n (a) = ϕ ω (a) for such a ∈ Σ.

Example 1 A classical morphic sequence is the Thue-Morse word x T M = 01101001100101 . . . that is a fixed point of the binary symmetric morphism ϕ T M defined by ϕ T M (0) = 01 and ϕ T M (1) = 10. This word can be obtained as a limit ϕ ω T M (0). In this paper we prove that fixed points of the binary symmetric morphisms, in particular, the Thue-Morse word are strongly recurrent.

Words, languages and products

The length of a word u = u 0 u 1 . . . u n-1 is n and is denoted by |u|. We call a subword occurring in a word at position 0 a prefix of that word.

We use three equivalent [START_REF] Allouche | Automatic Sequences. Theory, Applications, Generalizations[END_REF] definitions of uniform recurrence.

Claim 1 For any infinite word x the following statements are equivalent:

1. each subword of x occurs in it uniformly 2. each prefix of x occurs in it uniformly 3. for each integer n there exists such m that all subwords of x of length n occur in each subword of x of length m.

For an infinite word x, let us define the recurrence function R x as the function that maps an integer n to the smallest integer such that all subwords of x of length n occur in each subword of x of length R x (n). This function is well-defined if and only if the word is uniformly recurrent. A subword u of an infinite word x is said to occur in x non-uniformly if x contains arbitrary long subwords where u does not occur.

Let us denote the set of all finite words on Σ by Σ * , the set of all non-empty finite words by Σ + and the set of all words of length n by Σ n .

A language is a subset of Σ * . A language is factorial if it contains all subwords of its words. Let us denote the language of factors of a word x by F x and the set of symbols occurring in x by Σ x . For a language L, let us denote by Ω L the set of infinite words x such that F x ⊆ L. It is convenient to use the notation Ω x instead of Ω Fx for an infinite word x.

The cantor distance between infinite words x and y on Σ is d c (x, y) = 2 -inf{i : xi =yi} . Provided with such a distance the set Ω L for an infinite factorial language L ⊆ Σ * is a compact metric space. Let us give an example of the product of two uniformly recurrent words that is not uniformly recurrent.

Example 2 Let the morphism ϕ be the one defined by ϕ(0) = 011 and ϕ(1) = 101. Let us consider its fixed points x = ϕ ω (0) = 011101101101011101 . . . and y = ϕ ω (1) = 101011101011101101 . . .. They are obviously uniformly recurrent but the word x ⊗ y is not. Indeed, the word x⊗y is the fixed point beginning with 0, 1 of the morphism ϕ defined by ϕ ( a, b

) = ϕ(a) ⊗ ϕ(b) for a, b ∈ Σ 2 .
From the definition of ϕ we see that there are arbitrary long subwords of x ⊗ y which wholly consist of symbols 0, 0 and 1, 1 , hence the letter 0, 1 occurs in x ⊗ y non-uniformly.

A set I ⊆ N 0 is called thick if it contains arbitrary long intervals (subsets of the form {a, a + 1, . . . , a + n}). For example, if a subword occurs in an infinite word non-uniformly then the set of positions where it does not occur is thick.

Let x = x 0 x 1 . . . be an infinite word on Σ and I = {i 0 < i 1 < . . . } be a subset of N 0 . By x I we denote the word x i0 x i1 . . .. By x| I we denote the restriction of the function x : N 0 → Σ to I.

Infinite words x and y are equivalent on the set I ⊆ N 0 if there exists a bijection h : Σ x I ↔ Σ y I such that h(x| I ) ≡ y| I . In other words, h is a renaming of symbols such that the equality h(x i ) = y i holds for each i ∈ I. In this case we use the notation x I y. If these words are equivalent on the whole set N 0 , we use the notation x y and call them just equivalent.

Claim 2 The direct product of strongly recurrent words is strongly recurrent.

Proof: Let infinite words x and y be strongly recurrent. The word (x ⊗ y) ⊗ z x ⊗ (y ⊗ z) is uniformly recurrent for each uniformly recurrent word z. So x ⊗ y is strongly recurrent by the definition.

2

Let us define the block representation of order m of an infinite word x on an alphabet Σ as the word

x [m] = x [m] 0 x [m] 1 . . . on Σ m such that x [m] i = x im x im+1 . . . x im+m-1 .
An arithmetical subsequence of an infinite word x is an infinite word of the form x k x k+d x k+2d . . . for arbitrary initial positions k 0 and differences d 1.

The following lemma belongs to the folklore, the proof can be found in [START_REF] Avgustinovich | Arithmetical complexity of infinite words[END_REF], for example.

Lemma 1 An arithmetical subsequence of a uniformly recurrent word is uniformly recurrent.

We use its corollary.

Corollary 1 A block representation of a word is uniformly recurrent if and only if the word is uniformly recurrent.

Proof: "If" part. Let an infinite word x = x 0 x 1 . . . on an alphabet Σ be uniformly recurrent. Let us consider the word x = x 0 x 1 . . . on alphabet Σ m such that x i = x i x i+1 . . . x i+m-1 . The word x is uniformly recurrent since for its recurrence function we have R x (n) = R x (n + m -1). The word x [m] = x 0 x m x 2m . . . is an arithmetical subsequence of x . Hence, by Lemma 4 it is uniformly recurrent.

"Only if" part. The word x can be obtained from the word x [m] by applying the evident m-uniform morphism. The word x is uniformly recurrent since for its recurrence function we have R

x (n) R x [m] ( n m + 1). 2
An infinite word x = x 0 x 1 . . . is periodic of a period m if x i = x i+m for each i.

Claim 3 Periodic words are strongly recurrent.

Proof: Let x be a periodic infinite word of a period m. Then for each uniformly recurrent word y we have (x ⊗ y) [m] y [m] . Using Corollary 4 of Lemma 4 we obtain that x ⊗ y is uniformly recurrent. So, x is strongly recurrent. 2

The left shift operator denoted by T maps an infinite word x = x 0 x 1 . . . to the word T x = x 1 x 2 . . . . Note that if an infinite word x is uniformly recurrent and y ∈ Ω x then there exists an increasing progression (n i ) i∈N0 such that T ni x → y.

Orbits of fixed points of binary symmetric morphisms

In this section we investigate the equivalence on a set relation between the Thue-Morse or a similar word x and words from Ω x . The result (Lemma 5) is that if x I y holds for a thick set I ⊆ N 0 , a fixed point x of a binary symmetric morphism and a word y ∈ Ω x then x y. This fact is a consequence of the circularity (recognizability) of such a words that is described further.

Let us call an infinite word x (m, d)-circular if for each its subword u of length at least d all positions of occurrences of u in x are equivalent modulo m. This is not the original definition introduced in [START_REF] Mignosi | If a d0l language is k-power-free then it is circular[END_REF] and [START_REF] Cassaigne | An algorithm to test if a given circular hd0l-language avoids a pattern[END_REF] but the particular case of it. We call a fixed point of an muniform morphism circular if it is (d, m)-circular for some d.

Example 3 The Thue-Morse word x T M = 01101001100101 . . . is (2, 16)-circular since each of its subwords of length at least 16 contains the subword 00 occurring in x T M only at odd positions.

The criterion for a fixed point of a morphism to be circular was formulated and proved in [START_REF] Frid | On uniform dol words[END_REF]. A straightforward corollary of the result of that work is Lemma 2 If a fixed point of an expanding binary symmetric morphism is not circular then it is periodic.

If an infinite word x is periodic and x I y for some thick set I ⊆ N 0 and y ∈ Ω x , then we obviously have x y. So, let us concentrate on circular words. Proof: In the conditions of the first statement we have ϕ(v) occurring in x at positions divisible by m, since x = ϕ(x). Hence, the word u occurs in x at positions divisible by m and only there, due to the definition of circularity.

For the second statement one may consider words ϕ n (0) ϕ n (1) that occurs in x at positions divisible by m. If n is large enough, the word u occurs in ϕ n (0) at some position k. Obviously, in this case v occurs in ϕ n (0) or ϕ n (1) at the same position. Hence the statement is true due to the definition of circularity. 2

The basis of the main lemma is the following claim.

Claim 5 Let x be a circular fixed point of an m-uniform symmetric morphism ϕ. Then for each y ∈ Ω x there exist a unique word z = z(y) ∈ Ω x and a unique number t = t(y) < m such that y = T t ϕ(z).

Proof: Let x be (m, d)-circular. Then for the fixed point x and an arbitrary integer n we have ϕ(T n x) = T mn ϕ(x) = T mn x.

Let us consider a sequence (n i ) i∈N0 of integers such that T ni x → y. Since x is circular, there are integers i 0 and t < m such that for all i i 0 we have n i = t mod m. Hence, the sequence (T n i -t m x) i i0 of words is well-defined.

Due to the compactness of Σ N0 , there exists a subsequence (T n i -t m x) i∈I⊆N0 that converges to some word z. Obviously, z ∈ Ω x . For such a word z we have

T t ϕ(z) = T t ϕ(lim i∈I T n i -t m x) = T t lim i∈I ϕ(T n i -t m x) = T t lim i∈I T ni-t x = y .
Suppose that some z ∈ Ω x and t < m satisfy y = T t ϕ(z ). Applying Claim 4 to prefixes of ϕ(z) and ϕ(z ) we find that y 0 y 1 . . . y d-1 occurs in x at positions equal to t and t modulo m. So, t = t by the d-circularity of x.

The morphism ϕ is symmetric hence

T t ϕ(z) = T t ϕ(z ) implies z = z . 2
When σ = (σ k ) k∈N is an infinite sequence of numbers satisfying 0 σ k < m for any k, let us denote by S σ (i) the sum i j=1 m j-1 σ j . The statement of Claim 5 can be improved the following way. Lemma 3 Let x be a circular fixed point of an m-uniform symmetric morphism ϕ. Then for each y ∈ Ω x there exist a unique sequence (σ i ) i∈N of integers and a unique sequence (y (i) ) i∈N of words, where 0 σ i < m and y (i) ∈ Ω x for each i, such that

y = T Sσ(i) ϕ i (y (i) ) for every i ∈ N . (1)
Proof: Applying Claim 4 iteratively we can obtain sequences (σ i ) i∈N of integers and (y (i) ) i∈N of words, where 0 σ i < m and y (i) ∈ Ω x for each i, such that y (i) = T σi+1 ϕ(y (i+1) ) for each i ∈ N 0 (supposing y (0) = y). By the statement of Claim 4, sequences satisfying such a property exist and are unique.

As it is easy to see

y =T σ1 ϕ(y (1) ) = T σ1 ϕ(T σ2 ϕ(y (2) )) = T σ1+mσ2 ϕ 2 (y (2) ) = . . . . . . = T Sσ(i) ϕ i (y (i) ) = . . . . 2
We call such a sequence (σ i ) i∈N the characteristic sequence of y and denote it by σ(y). We use this characteristic to prove that if a word y ∈ Ω x is equivalent on a thick set to the fixed point x of a binary symmetric morphism then y is either x itself or the another fixed point of this morphism.

The characteristic sequence of the fixed point itself is a sequence of 0. One may expect the same from characteristic sequences of words that are equivalent on a thick set to the fixed point and it is true.

Lemma 4 Let x be a circular fixed point of a symmetric morphism ϕ and y ∈ Ω x . If x I y for a thick set I ⊆ N 0 then σ(y) consists only of 0.

Proof: Let x be (m, d)-circular. Suppose σ 1 = 0. In this case y = T σ1 ϕ(y (1) ).

is a bijection between whole alphabets Σ x and Σ y and the uniformly recurrent word x = h -1 (y) is well defined. By the definition of x , we have x | I ≡ x| I .

Since the set I is thick, it contains an interval B = {i, i + 1, . . . , i + R x (n) -1} for each n and some i = i(n). The word x is uniformly recurrent thus each of its subwords of length n occurs in the word x B . Hence, the statement

x B = x B implies F x ∩ Σ n x ⊆ F x ∩ Σ n x . Therefore, x ∈ Ω x . The product x ⊗ x is not uniformly recurrent because x ⊗ x x ⊗ y. 2
Now we came to the proof of the main result of this paper.

Theorem 1 Fixed points of the binary symmetric morphisms are strongly recurrent.

Proof: Let a word x is the fixed point of an m-uniform symmetric morphism ϕ and y be a uniformly recurrent word. Without lose of the generality we may assume that x = ϕ ω (0) and 1 occurs in x.

The idea of the proof is to show that if the product x ⊗ y is not uniformly recurrent then there exists a uniformly recurrent word x ∈ Ω x such that the product x ⊗ x again is not uniformly recurrent and x I x for some thick set I. This is a contradiction to the statement of Lemma 5.

Note that x [m i ] x for each i since x satisfy x = ϕ i (x) as a fixed point. The bijection between Σ x [m i ] and Σ x that realizes the equivalence maps ϕ i (0) to 0 and ϕ i (1) to 1.

Suppose that the product x ⊗ y is not uniformly recurrent and some prefix p of x ⊗ y occurs in it non-uniformly. Let an integer k satisfies m k |p|.

Consider the word z = y [m k ] that is uniformly recurrent by Corollary of Lemma . Suppose that (x ⊗ z) i = 0, z 0 for some i. Since

x ⊗ z x [m k ] ⊗ z (x ⊗ y) [m k ]
, it implies that p occurs in x ⊗ y at the position im k . Thus the symbol 0, z 0 occurs in x ⊗ z non-uniformly. Now, let us consider the word z = z [m l ] , where the integer l satisfies m l R z (1). The word z is uniformly recurrent by Corollary of Lemma .

Each symbol u of Σ z is a word u 0 u 1 . . . u m l -1 on Σ z that contains the symbol z 0 ∈ Σ z .

Let us define a morphism ψ : Σ * z → {0, 1} * by the following way. Let ψ(u) = 1 if and only if the word ϕ l (0) ⊗ u 0 u 1 . . . u m l -1 contains the symbol 0, z 0 . Otherwise, let ψ(u) = 0 (in this case the symbol 0, z 0 occurs in the word ϕ l (1) ⊗ u 0 u 1 . . . u m l -1 since ϕ is symmetric).

Let us consider the word y = ψ(z ) that obviously is uniformly recurrent. Since the symbol 0, z 0 occurs non-uniformly in the product x ⊗ z, there are arbitrary large subwords of x [m l ] ⊗ y that contains symbols ϕ l (0), 0 and ϕ l (1), 1 only. That implies the existence of a thick set I such that x [m l ] I y . Using the fact x [m l ] x we obtain x I y . The word x ⊗ y is not uniformly recurrent since x ⊗ y

x [m l ] ⊗ y and x [m l ] ⊗ y contains arbitrary large subwords where the symbol ϕ l (0), 1 does not occur.

By Lemma 6 there exists a word x ∈ Ω x satisfying to x I x for the thick set I and the product x ⊗ x is not uniformly recurrent. On the other hand, we have x x by Lemma 5 and hence x ⊗ x is uniformly recurrent. This is a contradiction we obtain supposing that x ⊗ y is not uniformly recurrent. 2

Conclusion

The problem of uniform recurrence of a direct product is still far from a solution. We prove strong recurrence for the very particular classical case of infinite words. The same is true and will be done in subsequent papers for another classical constructions like Sturmian words (and some of its generalizations) and words constructed from strongly recurrent words by "Toeplitzation" method (including the Toeplitz words themselves). The problem is still open for interval exchange words that are another generalization in some sense of Sturmian words.

Claim 4

 4 Let x be an (m, d)-circular fixed point of a symmetric morphism ϕ and u, v ∈ F x . The next statements are true. 1. If u is a prefix of ϕ(v) and |u| d then u occurs in x only at positions divisible by m. 2. If u v and |u| d then the positions of occurrences of u and v are equal modulo m.

Acknowledgements

The author is grateful to Anna Frid and Sergey Avgustinovich for the useful discussions and to anonymous referees for the remarks that helped to essentially improve the readability of the paper. The author thanks the organization committee of AutoMathA 2009 for granting him the travel grant.

The set I is thick hence it contains the interval B = {mj + m -σ 1 , mj + m -σ 1 + 1, . . . , mj + mσ 1 + d -1} for some j. Let us consider the word u = y B that is equal to x B . Due to the part 2 of Claim 4 the word u occurs in x only at positions equal to m -σ 1 modulo m.

On the other hand, we have u = ϕ(v) where v = y

(1) j+1 y

(1)

j+d is a subword of x. Due to the part 1 of Claim 4, it implies that u occurs in x at positions divisible by m. This is the contradiction to the circularity of x.

Suppose now, that a number i is the minimal satisfying σ i = 0. By Lemma 3, there exists a unique word y ∈ Ω Fx such that y = T m i-1 σi ϕ i (y ) = ϕ i-1 (T σi ϕ(y )). For the fixed point x we have x = ϕ i-1 (x).

Since the morphism ϕ is symmetric, the statement ϕ i-1 (T σi ϕ(y )) I ϕ i-1 (x) implies the existence of a thick set I such that T σi ϕ(y )) I x. Doing the same reasoning as we did for the case i = 0 we shall have the contradiction σ i = 0.

2

Now we are ready to prove the main lemma of this part. Using that equality of some word y ∈ Ω x on a thick set to the fixed point x implies that σ(y) ≡ 0, we will prove that equality on a thick set of some word to the fixed point implies equality of this words on the whole set N 0 .

Lemma 5 Let x be a fixed point of a symmetric morphism and y ∈ Ω Fx . Then for each thick set I ⊆ N 0 the statement x y follows from x I y.

Proof: If x is periodic, the statement of the lemma is obviously true. So, due to Lemma 2, we may restrict ourselves to the case x being circular.

Lemma 4 states that in this case σ(y) consists only of 0. By Lemma 3, for each i there is a word y (i) satisfying y = T Sσ(i) ϕ i (y (i) ) = ϕ i (y (i) ). Hence the sequence (ϕ i (y (i) 0 )) i∈N of finite words is a sequence of growing prefixes of y and y = lim i→∞ ϕ i (y

The morphism ϕ is symmetric and has fixed points that implies ϕ(a) 0 = a for each a ∈ Σ 2 . In view of this fact we have y (i) 0 = y 0 and y = lim i→∞ ϕ i (y 0 ). So, y is either x itself or another fixed point of ϕ and therefore x y.

2

We conclude this section with the remark that a little bit more general statement than Lemma 5 can be proved using the same technique. It can be proved that if words y, y ∈ Ω x are equivalent on a thick set I for a fixed point x of a binary symmetric morphism then there is an integer t ∈ N 0 such that T t y T t y .

Strong recurrence of fixed points of binary symmetric morphisms

We start proving strong recurrence of fixed points of the binary symmetric morphisms with an observation of some case of not uniformly recurrent product.

Lemma 6 If the product x⊗y of uniformly recurrent words x and y is not uniformly recurrent and x I y for some thick set I, then there exists a word x ∈ Ω x such that x ⊗ x is not uniformly recurrent and x I x .

Proof: Let a bijection h : Σ x I ↔ Σ y I be such that h(x i ) = y i for each i ∈ I.

The thick set I contains arbitrary large intervals of N 0 , in particular, larger than R x (1) and R y (1). Therefore, for each symbol a ∈ Σ x ∪ Σ y there is an integer i ∈ I such that either x i = a or y i = a. So, h