Báo cáo toán học: For each α 2 there is an infinite binary word with critical exponent α

For each > 2 there is an innite binary word with critical exponent James D. Currie& Narad Rampersady Department of Mathematics and Statistics University of Winnipeg Winnipeg, Manitoba R3B 2E9 CANADA e-mail: j.currie@uwinnipeg.ca, n.rampersad@uwinnipeg.ca Submitted: Feb 28, 2008; Accepted: Aug 25, 2008; Published: Aug 31, 2008 Mathematics Subject Classication: 68R15 Abstract The critical exponent of an innite word w is the supremum of all rational numbers such that w contains an -power. We resolve an open question of Krieger and Shallit by showing that for each > 2 there is an innite binary word with critical exponent . Keywords: Combinatorics on words, repetitions, critical exponent 1 Introduction If is a rational number, a word w is an -power if there exist words x and x0 and a positive integer n, with x0 a prex of x, such that w = xnx0 and = n+jx0j=jxj. We refer to jxj as a period of w. A word is -power-free if none of its subwords is a -power with ; otherwise, we say the word contains an -power. The critical exponent of an innite word w is dened as supf 2 Q j w contains an -powerg: Critical exponents of certain classes of innite words, such as Sturmian words [8, 10] and words generated by iterated morphisms [5, 6], have received particular attention. Krieger and Shallit [7] proved that for every real number > 1, there is an innite word with critical exponent . As tends to 1, the number of letters required to construct The author’s research was supported by an NSERC operating grant. yThe author is supported by an NSERC Post-doctoral Fellowship. the electronic journal of combinatorics 15 (2008), #N34 1 such words tends to innity. However, for > 7=3, Shur [9] gave a construction over a binary alphabet. For > 2, Krieger and Shallit gave a construction over a four-letter alphabet and left it as an open problem to determine if for every real number 2 (2;7=3], there is an innite binary word with critical exponent . Currie, Rampersad, and Shallit [3] gave examples of such words for a dense subset of real numbers in the interval (2;7=3]. In this note we resolve the question completely by demonstrating that for every real number > 2, there is an innite binary word with critical exponent . 2 Properties of the Thue-Morse morphism In this section we present some useful properties of the Thue-Morse morphism; i.e., the morphism dened by (0) = 01 and (1) = 10. Note that js(0)j = js(1)j = 2s for all s 0. Lemma 1. Let s be a positive integer. Let z be a subword of s+1(0) = s(01) with jzj 2s. Then z does not have period 2s. Proof. Write s(0) = a1a2 :::a2n, s(1) = b1b2 :::b2n. One checks by induction that ai = 1 bi for 1 i 2n, and the result follows. Brandenburg [1] proved the following useful theorem, which was independently redis-covered by Shur [9]. Theorem 2 (Brandenburg; Shur). Let w be a binary word and let > 2 be a real number. Then w is -power-free if and only if (w) is -power-free. The following sharper version of one direction of this theorem (implicit in [4]) is also useful. Theorem 3. Suppose (w) contains a subword u of period p, with juj=p > 2. Then w contains a subword v of length djuj=2e and period p=2. We will also have call to use the deletion operator which removes the rst (left-most) letter of a word. For example, (12345) = 2345: 3 A binary word with critical exponent We denote by L the set of factors (subwords) of words of (f0;1g): Lemma 4. Let 00v 2 L, and suppose that 00v is -power-free for some xed > 2. Let r = de. Suppose that 0rv = xuy where u contains an -power. Then x = and u = 0r. Proof. Suppose that u has period p. Since 00v 2 L, v begins with 1. Since 00v is -power-free, we can write u = 0sv0, where x = 0r s for some integer s, 3 s r, and v0 is a prex of v. If 0p is not a prex of u then the prex of u of length p contains the the electronic journal of combinatorics 15 (2008), #N34 2 subword 0001. Since > 2, this means that 0001 is a subword of u at least twice, so that 0001 is a subword of 00v. This is impossible, since 00v 2 L. Therefore, 0p is a prex of u, and u has the form 0t for some integer t . This implies that u has 0r as a prex, so that x = and u = 0r. Lemma 5. Let > 2 be given, and let r = de. Let s;t be positive integers, such that s 3 and there are words x;y 2 f0;1g such that s(0) = x00y with jxj = t. Suppose that 2 < r t=2s < and 00v 2 L is -power-free. Then the following statements hold. 1. The word ts(0rv) has a prex which is a -power, where = r t=2s. 2. Suppose that 00v contains a -power of period p for some and p. Then ts(0rv) contains a -power of period 2sp. 3. The word ts(0rv) is -power-free. Proof. We start by observing that s(0r) has period 2s. It follows that ts(0r) is a word of length r2s t with period 2s, and hence is a (r2s t)=2s = -power. Now suppose u is a -power of period p in 00v. Then s(u) is a -power of period 2sp in s(00v). However, s(0r 1v) is a sux of ts(0rv), since t < 2s = js(0)j. Thus s(u) is a -power of period 2sp in ts(0rv). Next, note that s(0r 1v) does not contain any -power, . Otherwise, by Theorem 3 and induction, 0r 1v contains a -power. This is impossible by Lemma 4. Suppose then that ts(0rv) contains a -power u^ of period q, . Using induction and Theorem 3, 0rv contains a -power u of period q=2s. By Lemma 4, the only possibility is u = 0r, and q=2s = 1. Thus q = 2s. Since 00v 2 L, the rst letter of v is a 1. Since u^ has period 2s, by Lemma 1 no subword of s(01) of length greater than 2s occurs in u^. We conclude that either u^ is a subword of ts(0r), or of s(v), and hence of s(0r 1v). As this second case has been ruled out earlier, we conclude that ju^j jts(0r)j = r2s t: This gives a contradiction: u^ is a -power, yet ju^j=q (r2s t)=2s = < : By construction, ts(0rv) has the form 00v^ where 00v^ 2 L. We are now ready to prove our main theorem: Theorem 6. Let > 2 be a real number. There is a word over f0;1g with critical exponent . Proof. Call a real number < obtainable if can be written = r t=2s, where r;s;t are positive integers, s 3, and the word obtained by removing a prex of length t from s(0) begins with 00. We note that 3(0) = 01101001 and 3(1) = 10010110 are of length 8, and both contain 00 as a subword; for a given s 3 it follows that r and t can be chosen so that = r t=2s < and j j 7=2s; by choosing large enough s, an obtainable number can be chosen arbitrarily close to . Let fig be a sequence of obtainable numbers converging to . For each i write i = ri ti=2si, where ri;si;ti are positive integers, si 3, and the word obtained by the electronic journal of combinatorics 15 (2008), #N34 3 removing a prex of length ti from si(0) begins with 00. If 00w 2 L, denote by i(w) the word tisi(0riw). Consider the sequence of words w1 = 1() w2 = 1(2()) w3 = 1(2(3())) . wn = 1(2(3((n())))) . By the third part of Lemma 5, if 00w 2 L is -power-free, then so is i(w). Since 00 is -power-free, each wi is therefore -power-free. By the rst and second parts of Lemma 5, wn contains i-powers, i = 1;2;:::;n. Note that is a prex of n+1(), so that wn = 1(2(3((n())))) is a prex of 1(2(3((n(n+1()))))) = wn+1: We may therefore let w = limn!1 wi. Since every prex of w is -power-free, w is -power-free but contains i-powers for each i. The critical exponent of w is therefore . The following question raised by Krieger and Shallit remains open: for > 1, if -powers are avoidable on a k-letter alphabet, does there exist an innite word over k letters with critical exponent ? In particular, for > RT(k), where RT(k) denotes the repetition threshold on k letters (see [2]), does there exist an innite word over k letters with critical exponent ? We believe that the answer is \yes". Acknowledgments We would like to thank the anonymous referee for helpful comments and suggestions. References [1] F.-J. Brandenburg, \Uniformly growing k-th power-free homomorphisms", Theoret. Comput. Sci. 23 (1983), 69{82. [2] A. Carpi, \On Dejean’s conjecture over large alphabets", Theoret. Comput. Sci. 385 (2007), 137{151. the electronic journal of combinatorics 15 (2008), #N34 4 [3] J.D. Currie, N. Rampersad, J. Shallit, \Binary words containing innitely many overlaps", Electron. J. Combin. 13 (2006), #R82. [4] J. Karhumaki, J. Shallit, \Polynomial versus exponential growth in repetition-free binary words", J. Combin. Theory Ser. A 104 (2004), 335{347. [5] D. Krieger, \On critical exponents in xed points of binary k-uniform morphisms". In Proc. STACS 2006, LNCS 3884, Springer-Verlag, 2006, pp. 104{114. [6] D. Krieger, \On critical exponents in xed points of non-erasing morphisms", Theo-ret. Comput. Sci. 376 (2007), 70{88. [7] D. Krieger, J. Shallit, \Every real number greater than 1 is a critical exponent", Theoret. Comput. Sci. 381 (2007), 177{182. [8] F. Mignosi, G. Pirillo, \Repetitions in the Fibonacci innite word", RAIRO Inform. Theor. Appl. 26 (1992), 199{204. [9] A. M. Shur, \The structure of the set of cube-free Z-words in a two-letter alphabet" (Russian), Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), 201{224. English translation in Izv. Math. 64 (2000), 847{871. [10] D. Vandeth, \Sturmian words and words with a critical exponent", Theoret. Comput. Sci. 242 (2000), 283{300. the electronic journal of combinatorics 15 (2008), #N34 5 ... - tailieumienphi.vn