Rich square-free words (Q2357378): Difference between revisions

A word of length \(n\) is called \textit{rich} (or \textit{full}) if it contains \(n\) distinct nonempty factors (e.g. the word \(aababb\)). An infinite word is rich if all its finite factors are rich. A word is \textit{square-free} (or \textit{non-repetitive}) if it does not contain a nonempty factor of the form \(vv\). Both rich and square-free words have been studied extensively. The author gives a proof of the fact that an infinite rich word cannot be square-free (this was already proved in reference [16] of the paper [\textit{E. Pelantová} and \textit{Š. Starosta}, Discrete Math. 313, No. 21, 2432--2445 (2013; Zbl 1279.05002)]), thus there exists a limit on the length of a rich square-free word for every alphabet size. The author then investigates the value of the maximal length \(r(n)\) of a rich square-free word over an alphabet of cardinality \(n\). For example, \(r(3)=7\) since the word \(abacaba\) is rich and square-free but every ternary rich word of length at least \(8\) contains a square. The main result of the paper consists in a construction of a series of words that leads to the following bounds: \(2.008^n<r(n)<2.237^n\), for every \(n\geq 5\).