Amy Glen
email: amy.glen@gmail.com

Bjarni V Halldórsson
email: bjarnivh@ru.is

Sergey Kitaev
email: sergey@ru.is

Crucial abelian k-power-free words

Keywords: 05D99, 68R05, 68R15 pattern avoidance, abelian square-free word, abelian cube-free word, abelian power, crucial word

In 1961, Erdős asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX where X is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian k-th powers, i.e., words of the form X1X2

, who showed that a minimal crucial word over an n-letter alphabet An = {1, 2, . . . , n} avoiding abelian squares has length 4n -7 for n ≥ 3. Extending this result, we prove that a minimal crucial word over An avoiding abelian cubes has length 9n -13 for n ≥ 5, and it has length 2, 5, 11, and 20 for n = 1, 2, 3, and 4, respectively. Moreover, for n ≥ 4 and k ≥ 2, we give a construction of length k 2 (n -1) -k -1 of a crucial word over An avoiding abelian k-th powers. This construction gives the minimal length for k = 2 and k = 3. For k ≥ 4 and n ≥ 5, we provide a lower bound for the length of crucial words over An avoiding abelian k-th powers.

Introduction

Let A n = {1, 2, . . . , n} be an n-letter alphabet and let k ≥ 2 be an integer. A word W over A n contains a k-th power if W has a factor of the form X k = XX • • • X (k times) for some non-empty word X. A k-th power is trivial if X is a single letter. For example, the word V = 13243232323243 over A 4 contains the (non-trivial) 4-th power (32) 4 = 32323232. A word W contains an abelian k-th power if W has a factor of the form X 1 X 2 • • • X k where X i is a permutation of X 1 for 2 ≤ i ≤ k. The cases k = 2 and k = 3

give us (abelian) squares and cubes, respectively. For instance, the preceding word V contains the abelian square 43232 32324 and the word 123 312 213 is an abelian cube. A word W is (abelian) k-power-free if W avoids (abelian) k-th powers, i.e., if W does not contain any (abelian) k-th powers. For example, the word 1234324 is abelian cube-free, but not abelian square-free since it contains the abelian square 234 324.

A word W is crucial with respect to a given set of prohibited words (or simply prohibitions) if W avoids the prohibitions, but W x does not avoid the prohibitions for any letter x occurring in W . A minimal crucial word is a crucial word of the shortest length. For example, the word W = 21211 (of length 5) is crucial with respect to abelian cubes since it is abelian cube-free and the words W 1 and W 2 end with the abelian cubes 111 and 21 21 12, respectively. Actually, W is a minimal crucial word over {1, 2} with respect to abelian cubes. Indeed, one can easily verify that there do not exist any crucial abelian cube-free words on two letters of length less than 5.

Abelian squares were first introduced by Erdős [START_REF] Erdős | Some unsolved problems[END_REF], who asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX where X is a permutation of X (i.e., abelian squares). This question has since been solved in the affirmative in a series of papers from 1968 to 1992 (see [START_REF] Evdokimov | Strongly asymmetric sequences generated by a finite number of symbols[END_REF][START_REF] Pleasants | Non-repetitive sequences[END_REF][START_REF] Keränen | Abelian squares are avoidable on 4 letters[END_REF] and also [START_REF] Carpi | On the number of abelian square-free words on four letters[END_REF]). Problems of this type were also considered by Zimin [START_REF] Zimin | Blocking sets of terms[END_REF], who used the following sequence of words as a key tool.

The Zimin word Z n over A n is defined recursively as follows: Z 1 = 1 and Z n = Z n-1 nZ n-1 for n ≥ 2. The first four Zimin words are:

Z 1 = 1, Z 2 = 121, Z 3 = 1213121, Z 4 = 121312141213121.
The k-generalized Zimin word Z n,k = X n is defined as

X 1 = 1 k-1 = 11 • • • 1, X n = (X n-1 n) k-1 X n-1 = X n-1 nX n-1 n • • • nX n-1
where the number of 1's, as well as the number of n's, is k -1. Thus Z n = Z n,2 . It is easy to see (by induction) that each Z n,k avoids (abelian) k-th powers and has length k n -1. Moreover, it is known that Z n,k gives the length of a minimal crucial word avoiding k-th powers.

However, much less is known in the case of abelian powers. Crucial abelian square-free words (also called right maximal abelian square-free words) of exponential length are given in [START_REF] Cummings | A one-sided Zimin construction[END_REF] and [START_REF] Evdokimov | Crucial words and the complexity of some extremal problems for sets of prohibited words[END_REF], and it is shown in [START_REF] Evdokimov | Crucial words and the complexity of some extremal problems for sets of prohibited words[END_REF] that a minimal crucial abelian square-free word over an n-letter alphabet has length 4n -7 for n ≥ 3.

In this paper, we extend the study of crucial abelian k-power-free words to the case of k > 2. In particular, we provide a complete solution to the problem of determining the length of a minimal crucial abelian cube-free word (the case k = 3) and we conjecture a solution in the general case. More precisely, we show that a minimal crucial word over A n avoiding abelian cubes has length 9n -13 for n ≥ 5 (Corollary 9), and it has length 2, 5, 11, and 20 for n = 1, 2, 3, and 4, respectively. For n ≥ 4 and k ≥ 2, we give a construction of length k 2 (n -1) -k -1 of a crucial word over A n avoiding abelian k-th powers (see Theorem 11). This construction gives the minimal length for k = 2 and k = 3, and we conjecture that this is also true for any k ≥ 4 and sufficiently large n. We also provide a rough lower bound for the length of minimal crucial words over A n avoiding abelian k-th powers, for n ≥ 5 and k ≥ 4 (see Theorem 12).

For a crucial word X over A n , we let X = X i ∆ i where ∆ i is the factor of minimal length such that ∆ i i is a prohibition for i ∈ A n . Note that we can rename letters, if needed, so we can assume that for any minimal crucial word X, one has

∆ 1 ⊂ ∆ 2 ⊂ • • • ⊂ ∆ n = X
where "⊂" means (proper) right factor (or suffix). In other words, for each i = 2, 3, . . . , n, we have

∆ i = Y i ∆ i-1 for some non-empty Y i .
In what follows we will use X i and Y i as stated above. We note that the definitions imply:

X = X i ∆ i = X i Y i ∆ i-1 = X n-1 Y n-1 Y n-2 • • • Y 2 ∆ 1 ,
for any i = 2, 3, . . . , n -1. Furthermore, in the case of crucial words avoiding abelian k-th powers, we write

∆ i i = Ω i,1 Ω i,2 • • • Ω i,k
, where the k blocks Ω i,j are equal up to permutation, and we denote by Ω i,k the block Ω i,k without the rightmost i.

Hereafter, we let k (n) denote the length of a minimal crucial word over A n avoiding abelian k-th powers. The length of a word W is denoted by |W |, and we denote by |W | x the number of occurrences of a letter x in W . The Parikh vector of a word W over A n is defined by

P(W ) := (|W | 1 , |W | 2 , . . . , |W | n ).
Clearly, if W is an abelian k-th power, then |W | x ≡ 0 (mod k) for all letters x occurring in W .

Crucial words for abelian cubes

An upper bound for 3 (n)

The fact that the 3-generalized Zimin word Z n,3 is crucial with respect to abelian cubes already gives us an upper bound of 3 n -1 for 3 (n). In Theorem 1 (below) we improve this upper bound to 3 • 2 n-1 -1. We then discuss a further improvement of the bound using a greedy algorithm, which gives asymptotically O(( √ 3) n ). This greedy algorithm provides minimal crucial abelian cube-free words over A n for n = 3 and n = 4, while the construction in Theorem 1 is optimal only for n = 3. We also provide a construction of a crucial word of length 9n -10 which exceeds our lower bound by only 3 letters, for n ≥ 5. Finally, we end this section with a construction of a crucial abelian cube-free word over A n of length 9n -13, which coincides with the lower bound given in Theorem 8 of Section 2.2 for n ≥ 5.

Theorem 1 One has that 3 (n) ≤ 3 • 2 n-1 -1.
Proof: We construct a crucial abelian cube-free word X = X n iteratively as follows. Set X 1 = 11 and assume X n-1 has been constructed. Then do the following:

1. Increase all letters of X n-1 by 1 to obtain X n-1 .

2. Insert 1 after (to the right of) each letter of X n-1 and adjoin one extra 1 to the right of the resulting word to get X n .

For example, X 2 = 21211, X 3 = 31213121211, etc. It is easy to verify that

|X n | = 3 • 2 n-1 -1.
We show by induction that X n avoids abelian cubes, whereas X n x does not avoid abelian cubes for any x ∈ A n . Both claims are trivially true for n = 1. Now take n ≥ 2. If X n contains an abelian cube, then removing all 1's from it, we would deduce that X n-1 must also contain an abelian cube, contradicting the fact that X n-1 contains no abelian cubes.

It remains to show that extending X n to the right by any letter x from A n creates an abelian cube. If x = 1 then we get 111 from the construction of X n . On the other hand, if x > 1 then we swap the rightmost 1 with the rightmost x in Xx, thus obtaining a word where every other letter is 1; removing all 1's and decreasing each of the remaining letters by 1, we have X n-1 (x -1), which contains an abelian cube (by the induction hypothesis).

2

As a further improvement of Theorem 1 we sketch here, without providing all the details, the work of a greedy algorithm. Here, "greedy" means that we assume (by induction) that an "optimal" crucial abelian cube-free word X n-1 over A n-1 has been constructed. Next (for the greedy step) we add just two n's (the minimum possible), and then we add as few of the other letters as possible to build a crucial abelian cubefree word X n over A n . More precisely, we set ∆ 1 = 11 and assuming that ∆ i-1 is built, we consider the minimum list T i of letters we must add (forming Y i and possibly updating ∆ i-1 by permuting letters in Y i-1 ) to build ∆ i , for i = 2, 3, . . . , n, which can then be turned into a construction of a crucial abelian cube-free word X n over A n . It is easy to see from the definitions of an abelian cube and a crucial word that T 2 must contain at least two 2's and at least one 1. Then T 3 must contain at least two 3's, at least one 2, and at least three 1's (the last statement follows from the fact that the two 3's in ∆ 3 are supposed to be accompanied by at least one 1 in Ω 3,1 and Ω 3,2 in ∆ 3 3 = Ω 3,1 Ω 3,2 Ω 3,3 , but without extra 1's, whose number of occurrences must be divisible by 3, we cannot manage it). Running this type of argument, one can come up with the following T i for initial values of i:

T 2 = {1, 2, 2}, T 3 = {1, 1, 1, 2, 3, 3}, T 4 = {1, 1, 1, 2, 2, 2, 3, 4, 4}, T 5 = {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5}, T 6 = {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 6}, etc.
In particular, we observe that (|T n |) n≥1 = 2, 3, 6, 9, 18, 27, . . . where

|T 2i+1 | = 2 • 3 i and |T 2i+2 | = 3 i for all i ≥ 0.
Hence, these considerations lead to a crucial abelian cube-free word over an n-letter alphabet of length

n-1 2 j=0 2 • 3 j + n 2 j=1 3 j .
Initial values for the lengths are 2, 5, 11, 20, 38, 65, . . . . Furthermore, by observing that

m j=0 3 j = 3 m+1 -1 2
for any integer m ≥ 0 (which can be easily proved by induction), we deduce that the length of a crucial abelian cube-free word obtained in this way is asymptotically O(( √ 3) n ). Even though this length is exponential, we do in fact obtain optimal values for n ≤ 4. Below we list optimal abelian cube-free crucial words over A n for n = 1, 2, 3, 4 of lengths 2,5,11, and 20, respectively: 11; 21211; 11231321211; 42131214231211321211.

A construction giving the best possible upper bound for n ≥ 5 can be easily described by examples, and we do this below (for n = 4, 5, 6, 7; the construction does not work for n ≤ 3). We also provide a general description. The pattern in the construction is easy to recognize.

An almost optimal construction for crucial abelian cube-free words.

An almost optimal construction of a crucial abelian cube-free word W n over A n for n = 4, 5, 6, 7 is shown below. We use spaces to separate the blocks Ω n,1 , Ω n,2 , and

Ω n,3 in W n = ∆ n . W 4 = 344233122 433221432 32122334 W 5 = 455344233122 544332215432 43212233445 W 6 = 566455344233122 655443322165432 54321223344556 W 7 = 677566455344233122 766554433221765432 65432122334455667 In general, the block Ω n,1 in W n = ∆ n = Ω n,1 Ω n,2 Ω n,3 is built by adjoining the factors i(i + 1)(i + 1) for i = n -1, n -2, . . . , 1.
The block Ω n,2 is built by adjoining together the following factors: n, xx for n -1 ≥ x ≥ 2, and n(n -1) . . . 2. Finally, the block Ω n,3 is built by adjoining the factors

(n -1)(n -2) . . . 1, xx for 2 ≤ x ≤ n -1, and finally n.
It is easy to see that |W n | = 9n -10. We omit the details of showing that W n is crucial with respect to abelian cubes since this can be shown in a similar manner for the optimal construction described below (see the proof of Theorem 11).

An optimal construction for crucial abelian cube-free words.

An optimal construction of a crucial abelian cube-free word E n over A n for n = 4, 5, 6, 7 works as follows. As above, we use spaces to separate the blocks Ω n,1 , Ω n,2 , and Ω n,3 in E n = ∆ n . In general, the block [START_REF] Cummings | A one-sided Zimin construction[END_REF] is built by adjoining the factors i(i + 1)(i + 1) for i = n -1, n -2, . . . , 2, followed by two 1's. The block Ω n,2 is built by adjoining the following factors: i(i + 1) for i = n -1, n -2, . . . , 2, followed by 11, and then the factor 34 • • • (n -1)n. Finally, the block Ω n,3 is built by adjoining the factors (n -1)(n -2) • • • 32, then xx for 3 ≤ x ≤ n -1, followed by n, and finally two 1's.

Ω n,1 in E n = ∆ n = Ω n,1 Ω n,2 Ω n,
We have

E n = Ω n,1 Ω n,2 Ω n,3
where Ω n,3 = Ω n,3 n, and by construction each Ω n,i contains two 1's, one 2, two n's, and three x's for x = 3, . . . , n -1. That is, for each i = 1, 2, 3, the Parikh vector of the block Ω n,i is given by P(Ω n,i ) = (2, 1, 3, 3, . . . , 3, 2). Hence, P(E n ) = (6, 3, 9, 9, . . . , 9, 5), and therefore |E n | = 6 + 3 + 9(n -3) + 5 = 9n -13. Moreover, for all n ≥ 4, the word E n is crucial with respect to abelian cubes. We omit the proof of this latter fact since it is very similar to the proof of Theorem 11 (to follow), from which the fact can actually be deduced by setting k = 3 (in view of Remark 3, later). Thus, a minimal crucial word avoiding abelian cubes has length at most 9n -13 for n ≥ 4. That is:

Theorem 2 For n ≥ 4, we have 3 (n) ≤ 9n -13.
Proof: See the proof of Theorem 11 where one needs to set k = 3 (in view of Remark 3, later). 2

2.2 A lower bound for 3 (n)

If X = ∆ n is a crucial word over A n with respect to abelian cubes, then clearly the number of occurrences of each letter except n must be divisible by 3, whereas the number of occurrences of n is 2 modulo 3. We sort in non-decreasing order the number of occurrences of the letters 1, 2, . . . , n -1 in X to get a nondecreasing sequence of numbers (a

1 ≤ a 2 ≤ • • • ≤ a n-1 )
. Notice that a i does not necessarily correspond to the letter i. We denote by a 0 the number of occurrences of the letter n. Also note that a 0 can be either larger or smaller than a 1 . By definitions, |X| = n-1 i=0 a i . For example, the abelian cube-free crucial word E n of length 9n -13 in Sec. 2.1 has the following sequence of a i 's: (a 0 , a 1 , . . . , a n-1 ) = (5, 3, 6, 9, . . . , 9). In this subsection, we prove that this sequence cannot be improved for n ≥ 5, meaning that, e.g., 5 cannot be replaced by 2, and/or 6 cannot be replaced by 3, and/or 9('s) cannot be replaced by 3('s) or 6('s), no matter what construction we use to form a crucial word. This is a direct consequence of Lemmas 4-7 (below) and is recorded in Theorem 8. In the rest of this section we use, without explanation, the following two facts that are easy to see from the definitions. For any letter x in a crucial abelian cube-free word X over A n :

1. |∆ x | x ≡ 2 (mod 3) and |∆ x | y ≡ 0 (mod 3) for any other letter y occurring in X.

If

x + 1 occurs in X, then we have ∆ x+1 = Y x+1 ∆ x where |Y x+1 | x+1 ≡ 2 (mod 3), |Y x+1 | x ≡ 1
(mod 3), and |Y x+1 | y ≡ 0 (mod 3) for any other letter y occurring in X.

The following fact will also be useful.

Lemma 3 Suppose X is a crucial abelian cube-free word over A n containing letters x and y such that x < y < n and |X| x = |X| y = 6. Then ∆ x cannot contain 5 occurrences of the letter x.

Proof: Suppose to the contrary that (under the hypotheses of the lemma) ∆ x contains 5 occurrences of the letter x.

Let A 1 = Y n Y n-1 • • • Y y+1 and A 2 = Y y Y y-1 • • • Y x+1 so that X = A 1 A 2 ∆ x . Then |A 1 A 2 | x = 1 and |A 1 A 2 | y ≥ 3
, contradicting the fact that each of the blocks Ω n,1 , Ω n,2 , and Ω n,3 in X = ∆ n = Ω n,1 Ω n,2 Ω n,3 must each receive two x's and two y's. 2

Lemma 4 For a crucial abelian cube-free word X over A n , the sequence of a i 's cannot contain 3, 3.

That is, (a 1 , a 2 ) = (3, 3).

Proof: Suppose that x and y are letters such that x < y < n and

|X| x = |X| y = 3. Let A 1 = Y n Y n-1 • • • Y y+1 and A 2 = Y y Y y-1 • • • Y x+1 so that we have X = A 1 A 2 ∆ x .
Then we must have the following distribution of x's and y's in X:

|A 1 | y = 1, |A 2 | y = 2, |A 2 | x = 1, and |∆ x | x = 2.
However, we get a contradiction, since each of the blocks Ω n,2 and Ω n,3 in X = ∆ n = Ω n,1 Ω n,2 Ω n,3 must receive one copy of x and one copy of y, which is impossible (no x can exist between the two rightmost y's). 2

Lemma 5 For a crucial abelian cube-free word X over A n , the sequence of a i 's cannot contain 6, 6, 6.

Proof: Suppose that x, y, z are three letters such that x < y < z < n and

|X| x = |X| y = |X| z = 6. Let A 1 = Y n Y n-1 • • • Y z+1 , A 2 = Y z Y z-1 • • • Y y+1 , and A 3 = Y y Y y-1 • • • Y x+1 so that X = A 1 A 2 A 3 ∆ x .
Then the minimal requirements on the A i are as follows:

|A 1 | z ≥ 1, |A 2 | z ≥ 2, |A 2 | y ≥ 1, |A 3 | y ≥ 2,
and

|A 3 | x ≥ 1.
Moreover, applying Lemma 3 to x and y, we have |∆ x | 2 = 2. And applying the same lemma to the letters y and z guarantees that A 1 A 2 contains 4 y's (in particular, ∆ x does not contain any y's).

Looking at

X = ∆ n = Ω n,1 Ω n,2 Ω n,3 , we see that for each i = 1, 2, 3, |Ω n,i | x = |Ω n,i | y = |Ω n,i | z = 2.
Thus, in A 3 , we must have the following order of letters: x, y, y and the boundary between Ω n,2 and Ω n,3 must be between x and y in A 3 . But then ∆ x entirely belongs to Ω n,3 , so it cannot contain any z's (if it would do so, ∆ x would then contain 3 z's which is impossible). On the other hand, we must have [START_REF] Cummings | A one-sided Zimin construction[END_REF] to receive 2 z's. Thus, ∆ y contains 2 y's, 3 z's, and 3 x's, which is impossible by Lemma 4 applied to the word ∆ y with two letters occurring exactly 3 times each. (Alternatively, one can see, due to the considerations above, that no z can be between the two rightmost x's, contradicting the structure of ∆ y ).

|A 3 | z = 3 for Ω n,
2

Lemma 6 For a crucial abelian cube-free word X over A n , the sequence of a i 's cannot contain 3, 6, 6.

Proof: Suppose that x, y, and z are letters such that |X| x = 3 and |X| y = |X| z = 6. We consider three cases covering all the possibilities up to renaming y and z.

Case 1: z < y < x < n. One can see that ∆ y does not contain x, but it contains at least 3 z's contradicting the fact that each of the blocks Ω n,1 , Ω n,2 , and Ω n,3 must receive 1 x and 2 z's.

Case 2: x < z < y < n. We let A = Y n Y n-1 • • • Y z+1 so that X = A∆ z . All three x's must be in ∆ z , while A must contain at least 3 y's contradicting the fact that each of the blocks Ω n,1 , Ω n,2 , and Ω n,3 must receive 1 x and 2 y's.

Case 3: z < x < y < n. We let

A 1 = Y n Y n-1 • • • Y y+1 , A 2 = Y y Y y-1 • • • Y x+1 , and A 3 = Y x Y x-1 • • • Y z+1 so that X = A 1 A 2 A 3 ∆ z .
The minimal requirements on the A i and ∆ z are as follows:

|A 1 | y ≥ 1, |A 2 | y ≥ 2, |A 2 | x = 1, |A 3 | x = 2, |A 3 | z ≥ 1, and |∆ z | z ≥ 2.
Now ∆ z cannot contain 3 y's, for otherwise, considering the structure of ∆ x , it would not be possible to distribute x's and y's in a proper way. However, if A 3 contains 3 y's then, so as not to contradict the structure of ∆ x (no proper distribution of y's and z's would exist), ∆ x must contain 3 z's, which contradicts to the structure of X = ∆ n = Ω n,1 Ω n,2 Ω n,3 (no proper distribution of y's and z's would exist among the blocks Ω n,1 , Ω n,2 , and Ω n,3 , each of which is supposed to contain exactly 2 occurrences of y and 2 occurrences of z). Thus, there are no y's in ∆ x , contradicting the structure of ∆ n (no proper distribution of y's and x's would exist among the blocks Ω n,1 ,Ω n,2 , and Ω n,3 ).

2

Lemma 7 For a crucial abelian cube-free word X over A n , (a 0 , a 1 , a 2 , a 3 , a 4 ) = (2, 3, 6, 9, 9).

Proof: Suppose |X| n = 2 and assume that |X| t = 3 for some other letter t. If t = n -1, then all three occurrences of t are in ∆ n-1 , whereas the two occurrences of n are in Y n (recall that X = ∆ n = Y n ∆ n-1 ). This contradicts the fact that |Ω n,1 | n = |Ω n,1 | t = 1. Thus, t = n -1 and |X| n-1 = 3. Now, assuming x, y, and z are three letters, with x < y < z < n -1, occurring {6, 9, 9} times in X (we do not specify which letter occurs how many times). Then, as in the proof of Lemma 5, we deduce that ∆ z belongs entirely to the block Ω n,3 . Moreover, the block Ω n,3 has {2, 3, 3} occurrences of letters x, y, z (in some order). However, if x or y occur twice in Ω n,3 , they occur twice in ∆ z , contradicting the structure of ∆ z . Thus z must occur twice in Ω n,3 , and the letters x and y each occur 3 times in Ω n,3 . But then it is clear that x and y must each occur 3 times in ∆ z , contradicting the fact that x and z should be distributed properly in ∆ z , by Lemma 4.

2

Theorem 8 For n ≥ 5, we have 3 (n) ≥ 9n -13.

Proof: This is a direct consequence of the preceding four lemmas, which tell us that any attempt to decrease numbers in the sequence (5, 3, 6, 9, 9, . . . , 9) corresponding to E n will lead to a prohibited configuration. 2

Corollary 9 For n ≥ 5, we have 3 (n) = 9n -13.

Proof: The result follows immediately from Theorems 2 and 8. 2

Remark 1 Recall from Sec. 2.1 that 3 (n) = 2, 5, 11, 20 for n = 1, 2, 3, 4, respectively. For instance, the word 42131214231211321211 is a minimal crucial abelian cube-free word over A 4 of length 20 (= 2 + 3 + 6 + 9). This can be proved using similar arguments as in the proofs of the Lemmas 4-7.

3 Crucial words for abelian k-th powers

An upper bound for k (n) and a conjecture

The following theorem is a direct generalization of Theorem 1 and is a natural approach to obtaining an upper bound that improves k n -1 given by the k-generalized Zimin word Z n,k .

Theorem 10 For k ≥ 3, we have k (n) ≤ k • (k -1) n-1 -1.
Proof: We proceed as in the proof of Theorem 1, with the only difference being that we begin with X 1 = 1 k-1 and put (k -2) 1's to the right of each letter except for the last (k -2) letters, after which we put (k -1) 1's instead. 2

We skip here the analysis of the work of a greedy algorithm, and proceed directly with the construction of a crucial abelian k-power-free word W n,k over A n before describing the construction of a similar word D n,k that we believe to be optimal.

A construction of a crucial abelian k-power-free word W n,k , where n ≥ 4 and k ≥ 3.

We illustrate each step of the algorithm by example, letting k = n = 4.

The construction can be explained directly, but we introduce it recursively, obtaining, for n ≥ 4, W n,k from W n,k-1 and using the abelian cube case W n,3 = W n as the basis. For n = 4,

W 4,3 = Ω 4,1 Ω 4,2 Ω 4,3 = 344233122 433221432 32122334.
Assume that W n,k-1 = Ω n,1 Ω n,2 . . . Ω n,k-1 is constructed and implement the following steps to obtain W n,k : It is easy to see that |W n,k | = k 2 (n -1) -1. We omit the proof that W n,k is crucial with respect to abelian k-th powers since it is similar to the proof for the following word D n,k , which is k letters shorter than W n,k (see Theorem 11).

1. Duplicate Ω n,1 in W n,k-1 to obtain the word W n,k-1 = Ω n,1 Ω n,1 Ω n,2 . . . Ω n,k-1 . For n = k = 4, W 4
A construction of a crucial abelian k-power-free word D n,k , where n ≥ 4 and k ≥ 2.

As we shall see, the following construction of the word D n,k is optimal for k = 2, 3. We believe that it is also optimal for any k ≥ 4 and sufficiently large n (see Conjecture 1).

As our basis for the construction of the word D n,k , we use the following word D n , which is constructed as follows, for n = 4, 5, 6, 7. (As previously, we use spaces to separate the blocks Ω n,1 and Ω n,2 in In general, the first block Ω n,1 in D n = ∆ n = Ω n,1 Ω n,2 is built by adjoining the factors i(i + 1) for i = n -1, n -2, . . . , 2, followed by the letter 1. The second block Ω n,2 is built by adjoining the factors

D n = ∆ n .) D 4 =
(n -1)(n -2) • • • 432, then 34 • • • (n -2)(n -1)
, and finally the letter 1.

Remark 2

The above construction coincides with the construction given in [6, Theorem 5] for a minimal crucial abelian square-free word over A n of length 4n -7. In fact, the word D n can be obtained from the minimal crucial abelian cube-free word E n (defined in Sec. 2.1) by removing the second block in E n and deleting the rightmost copy of each letter except 2 in the first and third blocks of E n . Now we illustrate each step of the construction for the word D n,k by example, letting n = 4 and k = 3. The construction is very similar to that of W n,k and can be explained directly, but we introduce it recursively, obtaining D n,k from D n,k-1 for n ≥ 4, and using the crucial abelian square-free word D n,2 := D n as the basis. For n = 4, we have

D 4,2 = Ω 4,1 Ω 4,2 = 34231 3231. Assume that D n,k-1 = Ω n,1 Ω n,2 • • • Ω n,k-1 is constructed and implement the following steps to obtain D n,k : 1. Duplicate Ω n,1 in D n,k-1 to obtain the word D n,k-1 = Ω n,1 Ω n,1 Ω n,2 • • • Ω n,k-1 .
For n = 4 and k = 3, D 4,2 = 34231 34231 3231. Proof: Fix n ≥ 4 and k ≥ 2. We have

D n,k = Ω n,1 Ω n,2 • • • Ω n,k-1 Ω n,k
where Ω n,k = Ω n,k n, and by construction each Ω n,i contains (k -1) occurrences of the letter 1, one occurrence of the letter 2, (k -1) occurrences of the letter n, and k occurrences of the letter x for x = 3, 4, . . . , n -1. That is, for each i = 1, 2, . . . , k, the Parikh vector of the block Ω n,i is given by

P(Ω n,i ) = (k -1, 1, k, k, . . . , k, k -1), (1)
and hence

P(D n,k ) = (k(k -1), k, k 2 , k 2 , . . . , k 2 , k(k -1) -1). Thus, |D n,k | = k(k -1) + k + k 2 (n -3) + k(k -1) -1 = k 2 (n -1) -k -1.
We will now prove that D n,k is crucial with respect to abelian k-th powers; whence the result. The following facts, which are easily verified from the construction of D n,k , will be useful in the proof.

Fact 1. In every block Ω n,i , the letter 3 has occurrences before and after the single occurrence of the letter 2.

Fact 2. In every block Ω n,i , all (k -1) of the 1's occur after the single occurrence of the letter 2 (as the factor 1 k-1 ). Fact 3. For all i with 2 ≤ i ≤ k -1, the block Ω n,i ends with n i-1 and the other (k -1 -i + 1) n's occur (together as a string) before the single occurrence of the letter 2 in Ω n,i . In particular, there are exactly k -2 occurrences of the letter n between successive 2's in D n,k .

Freeness: First we prove that D n,k is abelian k-power-free. Obviously, by construction, D n,k is not an abelian k-th power (as the number of occurrences of the letter n is not a multiple of k) and D n,k does not contain any trivial k-th powers, i.e., k-th powers of the form x k for some letter x. Moreover, each block Ω n,i is abelian k-power-free. For if not, then according to the Parikh vector of Ω n,i (see [START_REF] Bullock | Improved bounds on the length of maximal abelian square-free words[END_REF]), at least one of the Ω n,i must contain an abelian k-th power consisting of exactly k occurrences of the letter x for all x = 3, 4, . . . , n -1, and no occurrences of the letters 1, 2, and n. But, by construction, this is impossible because, for instance, the letter 3 has occurrences before and after the letter 2 in each of the blocks Ω n,i in D n,k (by Fact 1). Now suppose, by way of contradiction, that D n,k contains a non-trivial abelian k-th power, say P . Then it follows from the preceding paragraph that P overlaps at least two of the blocks Ω n,i in D n,k . We first show that P cannot overlap three or more of the blocks in D n,k . For if so, then P must contain at least one of the blocks, and hence P must also contain all k of the 2's. Furthermore, all of the 1's in each block occur after the letter 2 (by Fact 2), so there are (k -1) 2 = k 2 -2k + 1 occurrences of the letter 1 between the leftmost and rightmost 2's in D n,k . Thus, P must contain all k(k -1) = k 2 -k of the 1's. Hence, since Ω n,k ends with 1 k-1 , we deduce that P must end with the word

W = 23 k-1 1 k-1 Ω n,2 • • • Ω n,k-1 Ω n,k , where |W | n = k, |W | 3 = k(k -1) + (k -1) = k 2 -1, and |W | x = k(k -1) for x = 4, . . . , n -1. It follows that P must contain all k 2 of the 3's. But then, since D n,k = (n -1)n k-1 • • • 34 k-1 W
(by construction), we deduce that P must contain all k 2 of the 4's that occur in D n,k , and hence all k 2 of the 5's, and so on. That is, P must contain all k 2 occurrences of the letter x for x = 3, . . . , n -1; whence, since D n,k begins with the letter n -1, we have

P = Ω n,1 Ω n,2 • • • Ω n,k = D n,k , a contradiction.
Thus, P overlaps exactly two adjacent blocks in D n,k , in which case P cannot contain the letter 2; otherwise P would contain all k of the 2's, and hence would overlap all of the blocks in D n,k , which is impossible (by the preceding arguments). Hence, P lies strictly between two successive occurrences of the letter 2 in D n,k . But then P cannot contain the letter n as there are exactly k -2 occurrences of the letter n between successive 2's in D n,k (by Fact 3). Therefore, since the blocks Ω n,i with 2 ≤ i ≤ k -1 end with the letter n, it follows that P overlaps the blocks Ω n,1 and Ω n,2 . Now, by construction, Ω n,1 ends with 1 k-1 , and hence P contains k of the 2(k -1) = 2k -2 occurrences of the letter 1 in Ω n,1 Ω n,2 . But then P must contain the letter 2 because Ω n,1 contains exactly (k -1) occurrences of the letter 1 (as a suffix) and all (k -1) of the 1's in Ω n,2 occur after the letter 2 (by Fact 2); a contradiction.

We have now shown that D n,k is abelian k-power-free. It remains to show that D n,k x ends with an abelian k-th power for each letter x = 1, 2, . . . , n.

Cruciality: By construction, D n,k n is clearly an abelian k-th power. It is also easy to see that D n,k 1 ends with the (abelian) k-th power ∆ 1 1 := 1 k . Furthermore, for all m = n, n -1, . . . , 4, we deduce from the construction that

Ω m,1 = (m -1)m k-1 Ω m-1,1 , Ω m,2 = (m -1)m k-2 Ω m-1,2 m, . . . Ω m,k-2 = (m -1)m 2 Ω m-1,k-2 m k-3 , Ω m,k-1 = (m -1)mΩ m-1,k-1 m k-2 , Ω m,k = (m -1)Ω m-1,k [1 k-1 ] -1 (m -1)m k-2 1 k-1 ,
where

Ω m-1,k [1 k-1 ] -1 indicates the deletion of the suffix 1 k-1 of Ω m-1,k .
Consequently, for x = n -1, n -2, . . . , 3, the word D n,k x ends with the abelian k-th power ∆ x x where ∆ x is such that ∆ x+1 = x(x + 1) k-1 ∆ x with ∆ n := D n,k .

2

Observe that |D n,2 | = 4n-7 and |D n,3 | = 9n-13. Hence, since D n,k is a crucial abelian k-power-free word (by the proof of Theorem 11), it follows from [6, Theorem 5] and Corollary 9 that the words D n,2 and D n,3 are minimal crucial words over A n avoiding abelian squares and abelian cubes, respectively. That is, for k = 2, 3, the word D n,k gives the length of a minimal crucial word over A n avoiding abelian k-th powers. In the case of k ≥ 4, we make the following conjecture.

Conjecture 1 For k ≥ 4 and sufficiently large n, the length of a minimal crucial word over A n avoiding abelian k-th powers is given by k 2 (n -1) -k -1.

A Lower Bound for k (n)

A trivial lower bound for k (n) is nk -1 as all letters except n must occur at least k times, whereas n must occur at least k -1 times. We give here the following slight improvement of the trivial lower bound, which must be rather imprecise though.

Theorem 12 For n ≥ 5 and k ≥ 4, we have k (n) ≥ k(3n -4) -1.

Proof: Assuming that X is a crucial word over the n-letter alphabet A n with respect to abelian k-th powers (k ≥ 4), we see that adjoining any letter from A n to the right of X must create a cube as a factor from the right. In particular, adjoining n from the right side leads to creating a cube of length at least 9n -13 (by . This cube will be Ω n,k-2 Ω n,k-1 Ω n,k in X and thus Ω n,i , for 1 ≤ i ≤ k -1, will have length at least 3n -4, whereas Ω n,k has length at least 3n -5, which yields the result. 2

4 Further Research 1. Prove or disprove Conjecture 1. Notice that the general construction uses a greedy algorithm for going from k -1 to k, which does not work for going from n -1 to n for a fixed k. However, we believe that the conjecture is true.

2. A word W over A n is maximal with respect to a given set of prohibitions if W avoids the prohibitions, but xW and W x do not avoid the prohibitions for any letter x ∈ A n . For example, the word 323121 is a maximal abelian square-free word over {1, 2, 3} of minimal length. Clearly, the length of a minimal crucial word with respect to a given set of prohibitions is at most the length of a shortest maximal word. Thus, obtaining the length of a minimal crucial word we get a lower bound for the length of a shortest maximal word.

Can we use our approach to tackle the problem of finding maximal words of minimal length? In particular, Korn [START_REF] Korn | Maximal abelian square-free words of short length[END_REF] proved that the length (n) of a shortest maximal abelian square-free word over A n satisfies 4n -7 ≤ (n) ≤ 6n -10 for n ≥ 6, while Bullock [START_REF] Bullock | Improved bounds on the length of maximal abelian square-free words[END_REF] refined Korn's methods to show that 6n -29 ≤ (n) ≤ 6n -12 for n ≥ 8. Can our approach improve Bullock's result (probably too much to ask when taking into account how small the gap is), or can it provide an alternative solution?

E 4 =

 4 34423311 34231134 3233411 E 5 = 45534423311 45342311345 4323344511 E 6 = 56645534423311 56453423113456 5432334455611 E 7 = 67756645534423311 67564534231134567 6543233445566711

2 .Remark 3

 23 Append to the second Ω n,1 in D n,k-1 the factor 134 • • • n (in our example, 134; in fact, any permutation of {1, 3, 4, . . . , n} would work at this place) to obtain Ω n,2 in D n,k . In each of the remaining blocks Ω n,i in D n,k-1 , duplicate the rightmost occurrence of each letter x, where 1 ≤ x ≤ n and x = 2. Finally, in the last block of D n,k insert the letter n immediately before the leftmost 1 to obtain the word D n,k . For n = 4 and k = 3, we have D 4,3 = 34423311 34231134 3233411, where the bold letters form the word D 4,2 from which D 4,3 is derived. We provide five more examples here, namely D 5,3 , D 5,4 , D 4,4 , D 4,5 , and D 6,4 , respectively, so that readers can check their understanding of the construction: By construction, D n,3 = E n for all n ≥ 4. Theorem 11 For n ≥ 4 and k ≥ 2, we have k (n) ≤ k 2 (n -1) -k -1.

  ,3 = 344233122 344233122 433221432 32122334.We provide two more examples here, namely W 5,4 and W 4,5 , respectively, so that readers can check their understanding of the construction:

	W 4,4 = 344423331222 344233122432 433221443322 32122233344.
	4555344423331222 4553442331225432 5443322155443322 432122233344455;
	344442333312222 344423331222432 344233122443322 433221444333222 32122223333444.

2. Append to the second Ω n,1 in W n,k the factor n(n -1) . . . 2 (in our example, 432) to obtain Ω n,2 in W n,k , and in each of the remaining blocks Ω n,i in W n,k-1 , duplicate the rightmost occurrence of each letter x, where 2 ≤ x ≤ n, to obtain W n,k . For n = k = 4,

Acknowledgements

The authors would like to thank an anonymous referee for helpful comments and suggestions. The first and third authors were supported by the Icelandic Research Fund (grant nos. 09003801/1 and 060005012/3).


Evgeny Skvortsov
email: skvortsoves@googlemail.com.current

Yulia Zaks
email: yuzaks@gmail.com.

Synchronizing random automata

Keywords: Synchronizing DFA, Random DFA, Wormald's Theorem, Černý problem

Conjecture that any synchronizing automaton with n states has a reset word of length (n -1) 2 was made by Černý in 1964. Notwithstanding the numerous attempts made by various researchers this conjecture hasn't been definitively proven yet. In this paper we study a random automaton that is sampled uniformly at random from the set of all automata with n states and m(n) letters. We show that for m(n) > 18 ln n any random automaton is synchronizing with high probability. For m(n) > n β , β > 1/2 we also show that any random automaton with high probability satisfies the Černý conjecture.

Introduction

Let A = (Q, Σ, δ) be a deterministic finite automaton (DFA), where Q denotes a state set, Σ stands for an input alphabet, and δ : Q × Σ → Q is a transition function defining an action of the letters in Σ on Q. A word w is said to be a reset word for DFA A if its action leaves A in one particular state no matter what state it starts at: δ(q 1 , w) = δ(q 2 , w) for all q 1 , q 2 ∈ Q. A DFA A is called synchronizing if it possesses a reset word.

It is not too difficult to see that if an automaton with n states is synchronizing then there exists a reset word of length n 3 or shorter. It is not that easy, however, to see whether or not this bound is tight. In 1964 Černý formulated a conjecture concerning an upper bound of the length of the shortest reset word of a synchronizing DFA [START_REF] Černý | Poznámka k homogénnym eksperimentom s konečnými automatami, Matematickofyzikalny Časopis Slovensk[END_REF]: the length cannot be larger than (n -1) 2 . By now the Černý conjecture is arguably the most long standing open problem in the combinatorial theory of finite automata. The best upper bound has been obtained so far is (n 3 -n)/6; it was proved by Pin [START_REF] Pin | On two combinatorial problems arising from automata theory[END_REF] in 1983.

In fact, slowly synchronizing automata, i.e. automata with the shortest reset word of length Θ(n 2 ) are known to be exceptional. For a long time the only infinite series of such automata was the original one proposed by Černý [START_REF] Černý | Poznámka k homogénnym eksperimentom s konečnými automatami, Matematickofyzikalny Časopis Slovensk[END_REF]. The other substantially different ones [START_REF] Ananichev | Synchronizing automata with a letter of deficiency 2[END_REF] have only recently been constructed.

On the other hand, Higgins has shown that a composition of 2n random mappings of a set of size n into itself with high probability (whp) is a mapping with an image of size 1. (By "high probability" we mean that the probability tends to 1 with n going to infinity.) In terms of automata, Higgins's result means that a random automaton with an alphabet of size larger than 2n whp has a reset word of length 2n. Indeed, if we pick an automaton uniformly at random among all automata with n states and 2n letters then the action of a word composed of all the letters is identical to a mapping composed of 2n random mappings.

The problem of finding the shortest reset word for a given automaton is both NP-hard [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF] and co-NPhard [START_REF] Samotij | A note on the complexity of the problem of finding shortest synchronizing words[END_REF], which dramatically limits a size of automata feasible for numerical experiments. A limited simulation that we conducted supposedly shows that a random automaton on 2-letter alphabet whp has a reset word of a length sublinear with respect to the number of states.

The numerical experiment output combined with Higgins's result offers a new field of research: study of the shortest reset word of random automata, or the most probable length of the shortest reset word, as opposed to the classical problem of the upper bound; and allows to put forward a hypothesis that the most probable length should be much smaller than the upper bound.

Starting this new line of research we address the following questions.

• What size of an alphabet implies that almost all automata with the alphabet of this size are synchronizing and what is the length of the shortest reset word in this case?

• What size of an alphabet implies that almost all automata with the alphabet of this size are synchronizing and comply with the Černý conjecture?

In this paper we show that 2n upper bound can be improved with regards to both of these questions. We show that if an alphabet size is greater than 18 ln n then an automaton whp is synchronizing and if an alphabet consists of more than n 1/2+ǫ letters for some positive ǫ then it whp satisfies the Černý conjecture.

To get the latter bound we apply the Wormald's theorem [START_REF] Wormald | Differential equations for random processes and random graphs[END_REF]. The theorem allows one to reduce the analysis of a stochastic process to a system of differential equations. This method was originally developed for the analysis of algorithms on random graphs [START_REF] Wormald | Differential equations for random processes and random graphs[END_REF] and was later used to proof the efficiency of algorithms for the random Satisfiability problem [START_REF] Achlioptas | Lower bounds for random 3-SAT via differential equations[END_REF].

Also as a byproduct of the latter bound we address the problem of an epidemia spreading invertedly to the edges of a directed graph corresponding to two mappings. The problem of the epidemia spread along a digraph of one random mapping was formulated and initially studied by B. Gertbakh [START_REF] Gertbakh | Epidemic process on a random graph: some preliminary results[END_REF], and further explored by J. Jaworski [START_REF] Jaworski | Epidemic processes on digraphs of random mappings[END_REF]. We show that in a digraph with edges corresponding to two random mappings if one individual is infected, then the whole population will be with constant probability infected, too.

The paper is organized as follows. The results of the work are stated and discussed in Section 1. The proofs of the two main theorems are stated in Section 1 and presented in Sections 2 and 3. The Wormald's theorem and the other results used in the work are formulated in Appendix.

Main result

Consider a set of states Q and an alphabet Σ. Let us pick uniformly at random a transition function δ from the set {δ : Q × Σ → Q}. A resulting triple (Q, Σ, δ) defines a random deterministic finite automaton. It is important to note that a random automaton can be constructed as follows: for each q ∈ Q and for each a ∈ Σ we choose q ′ = δ(q, a) uniformly at random from Q.

The following theorem states the lower bound of the alphabet size that whp guarantees synchronizability of the random automaton.

Theorem 1 Let A = (Q, Σ, δ) be a random automaton such that |Q| = n, |Σ| > 18 ln n. Then A is synchronizing whp. Moreover, the length of the shortest reset word of A is whp less than 3n 2 ln n.

The theorem proof is presented in Section 2. The natural question is whether the bound stated in Theorem 1 is tight. From our point of view it is not and we conjecture that even a 2-letter alphabet is sufficient for synchronizability of a random automaton. At the moment, however, this question remains open.

The length of the shortest reset word 3n 2 ln n is smaller than the one obtained by Pin, but is still larger than Černý's. To comply with the Černý Conjecture we should enlarge our alphabet. Here we state the following theorem.

Theorem 2 Let A = (Q, Σ, δ) be a random automaton such that |Q| = n, |Σ| > n 1/2+ǫ for some ǫ > 0. Then A is whp synchronizing. Moreover, the length of the shortest reset word of A is whp at most (n -1) 2 letters.

The theorem proof is presented in Section 3. We believe that the bound stated by the Černý Conjecture is far from being tight for random automata and according to numerical experiments the tight one should be a sublinear one, as well.

The proof of Theorem 1

Let u, v be a pair of states of a random automaton A = (Q, Σ, δ). Consider the process called VACUUM procedure. The aim of the process is to find a word w = a 1 . . . a k such that uw = vw.

At the first step of the process we randomly choose a letter a 1 ∈ Σ and move from u = u 0 to u 1 = u 0 a 1 and from v = v 0 to v 1 = v 0 a 1 . If u 1 = v 1 then the process successfully finishes with w = a 1 , else it continues.

At the m-th step we have two states u m-1 and v m-1 . Let us choose a letter a m that has not been applied yet to any of the states u m-1 and v m-1 . If we cannot choose such a letter, the process fails. If we can choose a m , we make a move from u m-1 , v m-1 to u m , v m similar to the first one. If u m = v m the process finishes with w = a 1 a 2 . . . a m , else it continues. Obviously, at any step there are three possible outcomes for the process: it can fail, it can successfully finish and it can continue. So if it does not fail then at some step k it finishes with w = a 1 . . . a k such that uw = vw.

A formal description of the procedure is presented at Fig. 1 Now let us pass over to the behavior of the VACUUM procedure.

Lemma 1 If the VACUUM procedure is applied to a random automaton A = (Q, Σ, δ) and performs at least t steps then each of the paths {u 0 , . . . , u t } and {v 0 , . . . , v t } is indistinguishable from a random walk path on a complete directed graph.

Proof:

In other words, we should prove, that any u i is selected uniformly at random. Indeed, if we choose a letter a i at any step t we will get u i = u i-1 a i for a letter a i that has never been used at the state u i-1 . Random selection of a new letter for the transition from the state in a random automaton is equal to uniformly-at-random selection of the transition result u t . Thus, u i (similarly v i ) is selected uniformly at random from Q and is history-independent.

The same proposition can be proved constructively. Let B = (Q, E) be a complete directed graph; {u 0 , . . . , u t } and {v 0 , . . . , v t } -random walk paths in B of the length t. We construct from B a random

INPUT: A random automaton A = (Q, Σ, δ) and a pair of states u ∈ Q, v ∈ Q OUTPUT: failure or a word w = a 1 . . . a k such that uw = vw METHOD: let ∆ q ⊆ Σ, w ∈ Σ * initialize ∆ q = ∅ for all q ∈ Q, w = ε while uw = vw if ∆ uw ∪ ∆ vw = Σ then choose a ∈ Σ \ (∆ uw ∪ ∆ vw ) else return failure let ∆ uw = ∆ uw ∪ {a}, ∆ vw = ∆ vw ∪ {a} let w = wa return w
Fig. 1: VACUUM procedure automaton A with 2 paths performing first t steps of the VACUUM procedure. We label all edges in E with letters from Σ using the following algorithm: moving along the random paths we label the edge from u i (then similarly v i ) with an arbitrary letter never used in this vertex before, then we label other edges uniformly at random such that every vertex has |Σ| outgoing edges labelled with different letters. After labelling we remove all unlabelled edges. The result is by defintion a random automaton and our paths are precisely the first t steps of VACUUM (while labelling the edges we were using the same logic). The construction of B from A consists in adding edges and erasing labels from the existing ones. Explanation of the fact that {u 0 , . . . , u t } and {v 0 , . . . , v t } are the random walk paths in B is completely equivalent to one performed in the first proof of the lemma.

2

Next we are bounding the probability of long executions of the VACUUM procedure.

Lemma 2 If the VACUUM procedure is applied to a pair u, v of states of a random automaton A = (Q, Σ, δ) such that |Q| = n then for an arbitrary constant K the probability that this procedure makes at least Kn ln n steps is less than n -K .

Proof: As we have already observed, at every step t < Kn ln n the process either fails or continues: states u t and v t are selected independently and uniformly at random from Q. The probability that u t and v t will coincide equals 1 n . Thus, the probability that the process will not terminate within Kn ln n steps is less than 1 -

1 n Kn ln n ≤ n -K 2
So far we have proved that the probability of the existence of a long path u 1 u 2 . . . u t is rather low. Next, another question arises: how often do these states repeat in this path? In order to answer this question we need to obtain a certain information on a random path in a complete digraph -it is formulated below. Lemma 3 Let q 1 , . . . , q Kn ln n for some constant K be a random walk path in a complete digraph of size n then for any constant L, L > K the probability that there is a vertex

x such that |{i | q i = x}| ≥ L ln n is less than n 1-(L-K) 2 6K
for a sufficiently large n.

Proof: The expectation of |{i | q i = x}| for bx ∈ Q equals to 1 n × Kn ln n = K ln n. So the Chernoff bound for the random variable |{i | q i = x}| gives (see for example [START_REF] Papadimitriou | On the greedy algorithm for satisfiability[END_REF])

P |{i | q i = x}| -K ln n > δK ln n ≤ 2e -δ 2 K ln n 3 . (1)
Setting δ = L-K K we get required inequality

P |{i | q i = x}| -K ln n > (L -K) ln n ≤ 2e -(L-K) 2 ln n 3K ≤ n -(L-K) 2 6K . (2)
The last inequality holds for a sufficiently large n. Applying the union bound to all x ∈ Q we get the

desired bound n 1-(L-K) 2 6K
and finish the proof. 2

Now we are ready to prove the key lemma of the section.

Lemma 4 Let A = (Q, Σ, δ) be a random automaton such that |Q| = n, |Σ| > 18 ln n then for any two states u ∈ Q, v ∈ Q the VACUUM procedure whp does not fail.

Proof: Setting K = 3 in Lemma 2 we conclude that the VACUUM procedure will not terminate within 3n ln n steps with the probability at most n -3 . It means that our procedure will finish with a word w, or with failure, with the probability at least 1 -n -3 . Setting L = 18 in Lemma 3 and using Lemma 1 we conclude that the probability that u t or v t will visit some state more than 18 ln n times is less than 2n -23/2 .

If there are 18 ln n letters in our alphabet and there is a state x such that |{i | q i = x}| ≥ 18 ln n then the process will fail at the j-th step when we come to x for (18n ln n + 1)-th time.

There are more than 18n ln n letters, thus the probability that the process will fail is less than 2n -23/2 . There are only two possibilities not to find the word w before the 3n ln n-th step -to fail or to continue the process after this step, therefore the probability not to find the word w before the step 3n ln n is at most n -3 + 2n -23/2 ≤ 3n -3 . That means that the VACUUM procedure finishes with the probability 1 -3n -3 . The Lemma is proved.

2

Proof Proof of Theorem 1.: Our Theorem 1 is easily derived from Lemma 4. Application of the union bound to all pairs of states u, v ∈ Q finishes the synchronizability proof. The length of the reset word that is stated in the theorem is derived from the fact that every two states of the automaton may be synchronized within 3n ln n steps. In order to synchronize the automaton we subsequently synchronize (n -1) pairs. 2

3 The proof of Theorem 2

Let us define one more procedure on automata, entitled EPIDEMIA -this algorithm works for automata with a 2-letter alphabet. It takes a random automaton A = (Q, {a, b}, δ) and a state x ∈ Q and returns a set Q 2 of all the states from which x can be reached. Let a state q ∈ Q have some illness and this illness can invertedly spread along the edges, i.e., if the state q is ill, then at a certain time all the states {u | ua = q ∨ ub = q} will be ill, too. In these terms the aim of the procedure is to find all states that could be infected when only state x is initially ill.

INPUT: A random automaton A = (Q, {a, b}, δ) and a state x ∈ Q OUTPUT: a set Q 2 of all the states from which x can be reached METHOD:

let Q 0 , Q 1 , Q 2 be the subsets of Q intialize Q 0 = Q \ {x}, Q 1 = {x}, Q 2 = ∅ while Q 1 = ∅ choose q ∈ Q 1 arbitrary let N = {u ∈ Q 0 | ua = q ∨ ub = q} let Q 0 = Q 0 \ N , Q 1 = (Q 1 \ {q}) ∪ N , Q 2 = Q 2 ∪ {q} return Q 2 Fig. 2: EPIDEMIA procedure
The algorithm works as follows. At each step of the algorithm we introduce 3 sets: Q 2 is the set of all states that are ill now and have already infected all their neighbours, Q 1 is the set of all states that are ill but have not infected their neighbours yet, Q 0 is the set of all states that are still healthy.

At the first step

Q 0 = Q \ {x}, Q 1 = {x}, Q 2 = ∅.
At every step of the process we pick q ∈ Q 1 arbitrarily and consider a set N = {u ∈ Q 0 | ua = q ∨ ub = q} of all the healthy states that can be infected by s. At this step we exclude N from Q 0 and include it into Q 1 -from now on the states from this set are infected and may infect the new states at the following steps. State q is transferred to Q 2 -from now on it is not dangerous for the healthy states. At some step Q 1 becomes empty: all the states that could be infected are infected. Q 2 is constructed. A formal description of the procedure is presented on Fig. 2. A step of the procedure is illustrated on Fig. 3.

We shall also need the following technical lemma.

Lemma 5

For any letter a probability that there is a state q such that there are at least n 1/5 states q ′ for which q ′ a = q is at most e -cn 1/5 for some constant c.

Proof: It is known that for any n, m we have

n m ≤ ne m m . (3)
For a fixed q and a fixed set M of n 1/5 other states the probability that for all of them application of a letter a leads to q is less than n -n 1/5 = e -n 1/5 ln n .

There are less than n n n 1/5 ≤ n(n 1-1/5 e) n 1/5 ≤ e ( 4 5 +o(1))n 1/5 ln n [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF] ways to choose q and M . By the union bound, the probability that such a set M and a state q exist is less than e -( 15 n 1/5 +o(1)) ln n . 2

Now we are ready to state the key lemma of this section.

x

a b Q 2 Q 1 Q 0 N Fig. 3: One step of the EPIDEMIA procedure. Lemma 6 If A = (Q, {a, b}, δ
) is a random automaton over a two-letter alphabet and x ∈ Q. Then there is a constant r, 0 < r < 1, such that for sufficiently large n probability of the event "for any state q ∈ Q there is a word w q→x ∈ {a, b} * satisfying qw q→x = x" is greater than r.

Proof: We consider a state x ∈ Q and compute the probability that it can be reached from any element of Q, i.e. the EPIDEMIA procedure with x on input returns Q 2 = Q. The computation may be divided into 3 parts:

• computation of the probability that the process will not terminate in the very beginning and at least 0.1n steps will be made;

• computation of the probability that the process will not terminate in the middle between 0.1n-th and 0.9n-th steps;

• computation of the probability that the process will not finish at the end before |Q 2 | = n, i.e. if the EPIDEMIA makes 0.9n steps, then it will make n.

Let us start with the first probability. Execution of the EPIDEMIA procedure for a random automaton can be viewed as a Galton-Watson process. That is, at every step we have a population of species Q 1 . One of them (namely q) dies, but possibly leaves some offsprings N . The question of interest for us is the following: how many species will ever be born? We will use this model for the first n/10 steps of the procedure. Within this model at the step t the set N will be viewed as a set of all offsprings of q. Note that if at the step t < 0.1n we happened to have |Q 1 | > 0.2n then the process will not terminate by the step 0.1n and we will have at the step |Q 1 | ≥ 0.1n. Otherwise at the step t we have |Q 2 | + |Q 1 | ≤ 0.3n and consequently |Q 0 | > 0.7n. Each state q ∈ Q 0 with probability greater than 2 n -1 n 2 will satisfy q ∈ N . Therefore, expectation of the number of offspings at the step t < 0.1n is at least 2 n • 0.7n + o(1) ≥ 1.3. According to Lemma 8 when an expected number of offspings is more than 1 after 0.1n steps with at least constant probability we have a number of species at least ℓn for some constant ℓ > 0.

Now consider the t-th step of the EPIDEMIA, where t ∈ (0.1n, 0.9n). Let Q i (t) be Q i at the t-th step and let us compute the expectation of the change of

|Q 0 |, |Q 1 | and |Q 2 |: E (|Q 0 (t + 1)| -|Q 0 (t)|) = -2 × |Q 0 (t)| 1 -|Q 2 (t)| , (6)
E (|Q 1 (t + 1)| -|Q 1 (t)|) = -1 + 2 × |Q 0 (t)| 1 -|Q 2 (t)| , (7)
E (|Q 2 (t + 1)| -|Q 2 (t)|) = 1 (8)
So the change of Q j at each step has constant expectation that can be expressed as a function of Q 0 (t), Q 1 (t) and Q 2 (t). Since, according to Lemma 5, a degree of any variable exceeds n 1/5 with an exponentially small probability we have P |Q 0 (t + 1) -Q 0 (t)| > n 1/5 < n -3 . We also observe that the functions in the right hand side of the equations are continuous and differentiable on the segment [0.1, 0.9]. Therefore, all conditions of the Wormald's theorem are met.

Applying the Wormald's theorem and denoting t/n by y we get the following system of differential equations in variables q 0 , q 1 and q 2 corresponding to |Q 0 |, |Q 1 | and |Q 2 |, respectively.

dq 0 dy = -2 × |q 0 (y)| 1 -|q 2 (y)| , (9)
dq 1 dy = -1 + 2 × |q 0 (y)| 1 -|q 2 (y)| , (10)
dq 2 dy = 1 (11)
or, shorter,

     q0 = -2q0 1-q2 q1 = -1 + 2q0 1-q2 q2 = 1 (12)
It's easy to see that at the step t of the EPIDEMIA process we have |Q 2 (t)| = t. Thus we are interested in the solution that has q 2 (y) = y. Substituting the expression for q 2 into the first equation we get a linear differential equation and solve it for q 0 . Once q 0 and q 2 are known q 1 can be found by integrating the right hand side of the second equation. Thus, we get a parameterized set of solutions

q 0 = (y -1) 2 c, q 1 = (2c -1)y -y 2 c + d, q 2 = y (13)
with parameters c and d. By definition of q i q 0 + q 1 + q 2 = 1, so c + d = 1. Obviously, q 0 ≥ 0, so c ≥ 0. Consequently, 0 ≤ c ≤ 1 and an analysis of the quadratic function q 1 shows us that q 1 (0.9n) > 0 and the process whp goes on for at least 0.9n steps reaching |Q 2 | = 0.9n. Thus, we have shown that with constant probability we have the vertex x reachable from 0.9n vertices. We finish the proof by showing that whp there is no set of size substantially less than n/e without outgoing edge. In terms of the EPIDEMIA it means that if at some step |Q 0 | < n/e, the next step is possible, and finally we get Q 2 = Q.

Indeed, for an arbitrary set of size m (m = n/c for some constant c > e) the probability that there are no outgoing edges equals to (m/n) 2m . There are n m ≤ ne m m sets of size m. Applying the union bound we conclude that the probability that there is a set of size m with no outgoing edges is less than

m n 2m ne m m = me n m -→ n→∞ 0. (14) 2
To start proving Theorem 2 we need one more lemma. In proving it we use Chebushev inequality that holds for any random variable X and any real number k:

P |X -E (X) | > k V (X) ≤ 1/k 2 .
(15)

Lemma 7 Let A = (Q, Σ, δ) be a random automaton, such that |Q| = n, |Σ| = n β , β > 0.5. Let Σ 1 , Σ 2 be an arbitrary pair of sets such that Σ ⊇ Σ 1 ∪ Σ 2 , Σ 1 ∩ Σ 2 = ∅, |Σ 1 | = |Σ 2 | = n α for a real α satisfying 0.5 < α < β.
Then, with high probability, a set of the triples (a, b, q), a

∈ Σ 1 , b ∈ Σ 2 such that qa = qb = q, (16)
contains more than n 2α-1 elements.

Proof: Let us denote a set Σ 1 × Σ 2 × Q by T and a random variable

|{(a, b, q) ∈ T | qa = qb = q}| (17)
by N . We shall use the Chebyshev inequality to prove that N > 0 whp. At first we compute the expectation of N . The probability that a triple (a, b, q) ∈ Σ 1 × Σ 2 × Q satisfies (16) equals n -2 . There are n 2α+1 triples thus we have

E (N ) = n 2α+1 × n -2 = n 2α-1 . (18)
Now we compute an upper bound of the variance of N . Since we have

V (N ) = E N 2 -E (N ) 2 (19)
we need an upper bound for E N 2 . We define a random variable

∆ (a,b,q) = 1, qa = qb = q, 0, otherwise (20)
and compute

E N 2 = E      (a,b,q)∈T ∆ (a,b,q)   2    = {(ai,bi,qi)}i=1,2 E ∆ (a1,b1,q1) • ∆ (a2,b2,q2) = {(ai,bi,qi)}i=1,2∈T 2 ,q1 =q2 E ∆ (a1,b1,q1) • ∆ (a2,b2,q2) + a1 =a2,b1 =b2,q E ∆ (a1,b1,q) • ∆ (a2,b2,q) + a,b1 =b2,q E ∆ (a,b1,q) • ∆ (a,b2,q) + a1 =a2,b,q E ∆ (a1,b,q) • ∆ (a2,b,q) + a,b,q E ∆ (a,b,q) • ∆ (a,b,q) . Considering that |Σ 1 | = |Σ 2 | = n α , |Q| = n we get E N 2 = n 4α n(n -1)n -4 + n 2α (n α -1) 2 nn -4 + 2n 2α (n α -1)nn -3 + n 2α nn -2 (21)
and thus

E N 2 ≤ n 4α-2 + n 4α-3 + 2n 3α-2 + n 2α-1 ≤ E (N ) 2 + o(n) + E (N ) . (22)
So we have

V (N ) = E N 2 -E (N ) 2 ≤ E (N ) + o(n) ≤ 2E (N ) . (23)
The Chebyshev inequality in application to N , using the fact that V (N ) ≤ 2E (N ) states that

P |N -E (N ) | > k 2E (N ) ≤ 1/k 2 . ( 24
) Setting k = √ E(N ) 2 √
2 and remembering that V (N ) < 2E (N ) , E (N ) = n 2α-1 we apply the Chebyshev inequality and get

P (|N -E (N ) | > 0.5E (N )) ≤ 8/E (N ) = o(1), (25)
which implies P (N = 0) = o(1). 2
Proof Proof of Theorem 2.: Let α be a real number satisfying 0.5 < α < min(2/3, 0.5 + ε). Let us fix some sets of letters

Σ 1 ⊆ Σ, Σ 2 ⊆ Σ such that |Σ 1 | = |Σ 2 | = n α , Σ 1 ∩ Σ 2 = ∅. Let L be the set of all triples (a, b, x), a ∈ Σ 1 , b ∈ Σ 2 , x ∈ Q such that xa = x, xb = x
. By Lemma 7 the set L whp contains more than n 2α-1 elements. For any triple (a, b, x) ∈ L by Lemma 6 probability of event S(a, b, x) ="for any state q ∈ Q there is a word w q→x ∈ {a, b} * satisfying w q→x q = x" is greater than some constant r.

Consequently expectation of the random variable

Z = |{(a, b, x) | S(a, b, x) ∧ (a, b, x) ∈ L}|. (26)
is greater or equal to rn 2α-1 . In order to apply Chebyshev inequality and to show that whp Z > 0 we are going to prove that events S(a, b, x) are pairwise independent for triples (a, b, x) ∈ L. And to prove that we show that whp for any pair of triples (a

1 , b 1 , x 1 ) ∈ L, (a 2 , b 2 , x 2 ) ∈ L we have a 1 = a 2 ∧ b 1 = b 2 . ( 27
) Note that a i = b j because Σ 1 ∩ Σ 2 = ∅. We compute the probability that there are distinct triples (a 1 , b 1 , x 1 ), (a 2 , b 2 , x 2 ) such that the statement a 1 = a 2 , b 1 = b 2 does not hold and yet (a 1 , b 1 , x 1 ) ∈ L, (a 2 , b 2 , x 2 ) ∈ L, that is x 1 a 1 = x 1 ∧ x 1 b 1 = x 1 ∧ x 2 a 2 = x 2 ∧ x 2 b 2 = x 2 . ( 28
) If distinct triples (a 1 , b 1 , x 1 ), (a 2 , b 2 , x 2 ) do not satisfy condition a 1 = a 2 , b 1 = b 2
they must satisfy one of the following:

1. x 1 = x 2 , a 1 = a 2 , b 1 = b 2 , 2. x 1 = x 2 , a 1 = a 2 , b 1 = b 2 , 3. x 1 = x 2 , a 1 = a 2 , b 1 = b 2 , 4. x 1 = x 2 , a 1 = a 2 , b 1 = b 2 , 5. x 1 = x 2 , a 1 = a 2 , b 1 = b 2 .
For each condition C from this list we compute the probability of event "There are triples (a 1 , b 1 , x 1 ), (a 2 , b 2 , x 2 ) that satisfy condition C and equation (28)".

To pick a pair of triples satisfying condition 1. we need to choose x 1 , a 1 , b 1 and b 2 . So there are n • n α • (n 2α -1) ≤ n • n 3α pairs of triples satisfying condition 1. For those the equation (28) takes form

x 1 a 1 = x 1 ∧ x 1 b 1 = x 1 ∧ x 1 b 2 = x 1 (29)
and its probability equals n -3 . Thus, the probability that there exists a pair of triples satisfying condition 1. and equation (28) can be bounded above by

nn 3α × n -3 = n 3α-2 -→ n→∞ 0. (30)
Similar bounds for probabilities of conditions 2, . . . , 5 equal nn 3α × n -3 , n 2 n 3α × n -4 , n 2 n 3α × n -4 , n 2 n 2α × n -4 , respectively, and it is easy to see that they all tend to 0 when n goes to infinity. Thus whp for any pair of distinct triples (a

Similarly to Lemma 7 we can apply Chebyshev inequality and conclude that whp Z > rn 2α-1 /2. Thus whp Z > 0 and there is a triple (a, b, x) ∈ L such that for any state q there is a word w q→x ∈ {a, b} * satisfying w q→x q = x. Since (a, b, x) ∈ L, w q→x ∈ {a, b} we have xw = x. Then we consider a word w Q→x defined as follows: at the first step we take an arbitrary state q 0 and set w Q→x = w q0→x , at the i-th step we take as a q i one of the states remaining landed and set w Q→x = w Q→x w qi→x . There are n -1 steps at most. By definition w Q→x is a reset word of the length at most (n -1) 2 . 2

Future Work

The results presented in this paper set new upper bounds for the number of letters required for a random automata to be synchronizing whp and to satisfy whp the Černý conjecture. The bounds still do not reach quantities that are to be expected considering the rareness of slowly synchronizing automata and the experimental results. We believe that an n state random automaton with an alphabet of size 2 is with high probability synchronizing and has a reset word of the length less than n.

  1 , b 1 , x 1 ) ∈ L, (a 2 , b 2 , x 2 ) ∈ L we have a 1 = a 2 , b 1 = b 2 .So far we have proven that whp |L| > n 2α-1 and for any (a1 , b 1 , x 1 ) ∈ L, (a 2 , b 2 , x 2 ) ∈ L we have a 1 = a 2 , b 1 = b 2 .The expectation of Z is at least rn 2α-1 and it is a sum of pairwise independent random variables I S(a,b,x) = 1, S(a, b, x), 0, otherwise.

Acknowledgements

We are grateful to Prof. M.V. Volkov for attracting our attention to the problem and several discussions on the topic, and to the anonymous reviewers for their remarks which have helped us make the article more accurate and clear.

The second author acknowledges support from the Federal Education Agency of Russia, grant 2.1.1/3537, and from the Russian Foundation for Basic Research, grants 09-01-12142 and 10-01-00793.

1365-8050

Appendix

Chernoff's Bound

Let B(p, n) be a random variable, that is the number of successes in n independent trials. If p is the probability of success in each trial, then the following inequality is known as Chernoff Bound [START_REF] Raghavan | Randomized Algorithms[END_REF]

Galton-Watson Process

A simple Galton-Watson Process [START_REF] Asmussen | Branching processes[END_REF] is a sequence of random variables {X n } which satisfies

where ξ is some predefined random variable. Galton-Watson Process was studied as a model of population survival. X 1 represents the size of the initial population and X n is the size of the n-th generation. Distribution of the random variable ξ reflects the distribution of the number of offsprings of an individual.

The following statement was proven for the Galton-Watson process (see Proposition 1.2 and Corollary 1.6 in [START_REF] Asmussen | Branching processes[END_REF])

Then there is a constant r such that P (X n = 0) > r for all n.

Wormald's Theorem

One of the instruments of our analysis is the Wormald's theorem [START_REF] Wormald | Differential equations for random processes and random graphs[END_REF] that allows one to replace a probabilistic analysis of a combinatorial algorithm with an analysis of a deterministic system of differential equations. All random processes are discrete time random processes. Such a process is a probability space Ω denoted by (Q 0 , Q 1 , . . .), where each Q i takes values in some set S. Consider a sequence Ω n , n = 1, 2, . . ., of random processes. The elements of Ω n are sequences (q 0 (n), q 1 (n), . . .) where each q i (n) ∈ S. For the convenience's sake the dependance of n will usually be dropped from the notation. Asymptotics, denoted by the notation o and O, are for n → ∞, but uniform over all other variables. For a random X, we say

. We denote by S + the set of all h t = (q 0 , . . . , q t ), each q t ∈ S for t = 0, 1 . . .. By H t we denote the history of the processes, that is the n × (t + 1)-matrix with entries

A function f (u 1 , . . . , u j ) satisfies the Lipschitz condition on D ⊆ R j if a constant L > 0 exists with the property that

for all (u 1 , . . . , u j ) and (v 1 , . . . , v j ) in D.

Theorem 3 (Wormald, [13])

Let k be fixed. For 1 ≤ ℓ ≤ k, let y (ℓ) : S + → R and f ℓ : R k+1 → R, such that for some constant C and all ℓ, |y (ℓ) | < Cn for all h t ∈ S + for all n. Suppose also that for some function m = m(n):

(i) for all i and uniformly over all t < m, P |Y

(ii) for all ℓ and uniformly over all t < m, E(Y

t /n, . . . , y