How Many Squares Can a String Contain?

In this: publication
By this: publisher
In this Subject: <a title="Mathematics and Statistics" href="/content/subcat?j_subject=195&j_availability=">Mathematics and Statistics
By this author: Fraenkel A.S. ;&nbsp; Simpson J.

Authors: Fraenkel A.S.; Simpson J.

Source: Journal of Combinatorial Theory, Series A, Volume 82, Number 1, April 1998 , pp. 112-120(9)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

All our words (strings) are over a fixed alphabet. A square is a subword of the form uu=u², where u is a nonempty word. Two squares are distinct if they are of different shape, not just translates of each other. A word u is primitive if u cannot be written in the form u=v^j for some j ges 2. A square u²with u primitive is primitive rooted. Let M(n) denote the maximum number of distinct squares, P(n) the maximum number of distinct primitive rooted squares in a word of length n. We prove: no position in any word can be the beginning of the rightmost occurrence of more than two squares, from which we deduce M(n)<2n for all n>0, and P(n)=n-o(n) for infinitely many n. Copyright 1998 Academic Press.