tailieunhanh - Báo cáo toán học: "How many square occurrences must a binary sequence contain?"

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í toán học quốc tế đề tài: How many square occurrences must a binary sequence contain? | How many square occurrences must a binary sequence contain Gregory Kucherov Pascal Ochem Michael Rao Submitted Dec 3 2002 Accepted Dec 15 2002 Published Apr 15 2003 Abstract Every binary word with at least four letters contains a square. A. Fraenkel and J. Simpson showed that three distinct squares are necessary and sufficient to construct an infinite binary word. We study the following complementary question how many square occurrences must a binary word contain We show that this quantity is in the limit a constant fraction of the word length and prove that this constant is . 1 Introduction Infinite words avoiding repetitions is a classical area in word combinatorics 2 . A famous result of 9 10 see also 1 is that squares subwords of the form uu for a nonempty u can be avoided on a ternary alphabet and cubes subwords uuu on a binary alphabet. Different generalizations of the Thue results have been studied recently. One direction is related to considering fractional exponents. Thue showed that on the binary alphabet a strongly cube-free infinite word can be constructed . a word that does not contain a subword uua where a is the first letter of u. Putting this result in terms of fractional exp onents there exists an infinite binary word that does not contain a subword of exponent 2 E for any E 0. 2 is trivially a tight bound as any binary word longer than three letters contains a square. Generalizing this to the ternary alphabet F. Dejean 4 showed that any exponent bigger than 7 4 can be avoided using three letters and this bound is tight. These results have been generalized to larger alphabets and on the other hand to the abelian case LORIA INRIA-Lorraine 615 rue du Jardin Botanique . 101 54602 Villers-les-Nancy France tLaboratoire Bordelais de Recherche en Informatique 351 cours de la Libration 33405 Talence Cedex France ochem@ lUniversite de Metz Laboratoire d Informatique Theorique et Appliquee 57045 Metz .