Asymptotic Behaviour of the Maximal Number of Squares in Standard Sturmian Words (Extended Abstract)

Denote by sg(w) the number of district squares in a string w and let S he the class of standard Sturmian words. They are generalizations of Fibonacci words and are important in combinatorics on words. For Fibonacci words the asymptotic behaviour of the number of rims and the number of squares is the same. We show that for Sturrniart words the situation is quite different. The tight bound 4,1 w for the number of runs was given in [3]. In this paper we show that the tight bound for the maximal number of squares is 9/10 vertical bar w vertical bar We use the results of [11] where exact (but not closed) complicated formulas were given for sq(w) for w is an element of S and we show: (1) for all w is an element of S sq (w) <= 9/10 vertical bar w vertical bar + 4, (2) there is an infinite sequence of words w(k) is an element of S such that lim(k ->infinity) vertical bar w(k)vertical bar = infinity and lim(k ->infinity) sq(w(k))/vertical bar w(k)vertical bar = 9/10. Surprisingly the maxima! number of runs is reached by the words with recurrences of length only 5. This contrasts with the situation of Fibbonaci words, though standard Sturrnian words are natural extension of Fibonacci words. If this length drops to 4, the asynitotic behaviour of the maximal number of squares falls down significantly below 9/10 vertical bar w vertical bar. The structure of Sturmian words rich in squares has been discovered by us experimentally and verified theoretically. The upper bound is much harder, its proof is not a matter of simple calculations. The summation formulas for the number of squares are complicated, no closed formula is known. Some nontrivial reductions were necessary.