tailieunhanh - Báo cáo toán học: "The Number of Positions Starting a Square in Binary Words"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The Number of Positions Starting a Square in Binary Words. | The Number of Positions Starting a Square in Binary Words Tero Harju Department of Mathematics University of Turku Finland harju@ Tomi Karki Department of Mathematics University of Turku Finland topeka@ Dirk Nowotka Institute for Formal Methods in Computer Science FMI Universităt Stuttgart Germany nowotka@ Submitted Sep 3 2010 Accepted Dec 14 2010 Published Jan 5 2011 Mathematics Subject Classification 68R15 Abstract We consider the number ơ w of positions that do not start a square in binary words w. Letting ơ n denote the maximum of ơ w for length w n we show that lim ơ n n 15 31. 1 Square-free positions and strong words Every binary word with at least 4 letters contains a square. . Fraenkel and J. Simpson 2 1 studied the number of distinct squares in binary word see also Ilie 4 where it was shown that a binary word can contain at most 2n logn distinct squares. It has been conjectured that n is an upper bound in this case. On the other hand in an impressive paper 5 G. Kucherov P. Ochem and M. Rao proved that the minimum number of occurrences of squares in binary words is asymptotically equal to . times the length of the word. Later Ochem and Rao 7 showed that this constant is exactly 103 187. In the present paper we count the minimum number of positions in binary words that starts a square and we show that asymptotically this is 16 31 . For our convenience we state the result in the dual case . we count the maximum number of positions that are square-free. Related question for borders of cyclic words was considered by T. Harju and D. Nowotka 3 . THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P6 1 Several parts of the proofs are computer aided both for searching the strong words the main concept in the proofs as well as for checking their compatibilities. We have included the Mathematica code for the search of strong words. We refer to Lothaire 6 for elementary definitions in combinatorics on words. Let A a b c .