On a Conjecture by Eriksson Concerning Overlap in Strings

Source abstract

Consider a finite alphabet Ω and strings consisting of elements from Ω. For a given string w , let cor( w ) denote the autocorrelation, which can be seen as a measure of the amount of overlap in w . Furthermore, let a w ( n ) be the number of strings of length n that do not contain w as a substring. Eriksson [4] stated the following conjecture: if cor( w )>cor( w ′), then a w ( n )> a w ′ ( n ) from the first n where equality no longer holds . We prove that this is true if [mid ]Ω[mid ][ges ]3, by giving a lower bound for a w ( n )− a w ′ ( n ).