Weakly self-avoiding words and a construction of Friedman (Q5925761)

Summary: H. Friedman obtained remarkable results about the longest finite sequence \(x\) over a finite alphabet such that for all \(i \not= j\) the word \(x[i..2i]\) is not a subsequence of \(x[j..2j]\). In this note we consider what happens when ``subsequence'' is replaced by ``subword''; we call such a sequence a ``weakly self-avoiding word''. We prove that over an alphabet of size \(1\) or \(2\), there is an upper bound on the length of weakly self-avoiding words, while if the alphabet is of size \(3\) or more, there exists an infinite weakly self-avoiding word.