tailieunhanh - Báo cáo toán học: "There exist binary circular 5/2+ power free words of every length"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: There exist binary circular 5/2+ power free words of every length. | There exist binary circular 5 2 power free words of every length Ali Aberkane James D. Currie Department of Mathematics and Statistics University of Winnipeg Winnipeg Manitoba R3B 2E9 Canada e-mail aberkane@. fr currie@ Submitted Oct 31 2003 Accepted Jan 5 2003 Published Jan 23 2004 MR Subject Classification 68R15 Abstract We show that there exist binary circular 5 2 power free words of every length. Keywords Combinatorics on words Dejean s conjecture Thue-Morse word 1 Introduction The word alfalfa consists of the segment alfa overlapped with itself. Alternatively we may view alfalfa as alf taken 21 times we write alfalfa alf 7 3. Let w be a word w w1w2 . .wn where the w are letters. We say that w is periodic if for some integer p n we have w wi p i 1 2 . n p. We call p a period of w. Thus by convention length n of w is always a period. Let k be a rational number. If p is a period of w and w kp then we say that w is a k power. For example every word is 1 power. A k power is a word which is an r power for some r k. A word is k power free if none of its subwords is a k power. A 2 power is called a square while a 2 power is called an overlap. Thue showed that there are infinite sequences over a b not containing any overlaps and infinite sequences over a b c not containing any squares 7 . As well as studying sequences Thue studied necklaces or circular words. Word v is a conjugate of word w if there are words x and y such that w xy and v yx. Let w be a word. The circular word w is the set consisting of w and all of its conjugates. We say that circular word w is k power free if all of its elements are k The author s research was supported by an NSERC operating grant. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R10 1 0 0 110 1 Figure 1 A 2 free circular word. power free that is all the conjugates of the ordinary word w are k power free. Thue proved that overlap-free binary circular words of length n exist exactly when n is of the form 2m or 3