# What prefix and factors determine a ultimately periodic word uniquely

Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all infixes of length $n$ determine $\xi$ uniquely, meaning it is the only word with this prefix and infixes.

Some context: I am currently searching for conditions under which a prefix and a set of infixes (or factors) determine a word uniquely. I guess this problem should be solvable for ultimately periodic words. If $\xi$ is just periodic, i.e. $\xi= q^{\omega}$ then this is easy, because choose $q$ minimal, meaning such that it is not a power of some other finite word (such words are called primitive), then the factors of length $n := |q|$ determine $\xi$ unique. For suppose $\eta$ is another word with the same prefix and factors of length $n$, then $\eta = q\tau$, now look at the word $\eta[2...n+1] = q[2...n] x$. Because $\eta$ has the same factors as $\xi$, and all factors of $\xi$ are conjugates (i.e. cyclic permutations) of $q$, there must be $i$ such that $q[2...n] x = q[i+1...n] q[1...i]$. As $q$ was choosen primitive it must have exactly $n$ different conjugate words (this is a well known fact about primitive words) so that $i = 1$ follows (otherwise there would be fewer then $n$ conjugates) which implies $x = q[1..1] = q_1$. Proceeding inductively in this way we see that $\eta = q^{\omega}$. But I am unable to extends this to ultimately periodic sequences, because the prefix $p$ could be anything. So any suggestions or help?

Some remarks on notation: If $w$ is a finite sequence, by $w[i...j]$ I denote the subsequence from the $i$-th up to the $j$ position $w[i...j] = w_i w_{i+1} \cdots w_{j}$.

• choose $n=R+1$, where $R$ is the shortest length for which you have no right special factor (i.e., no factor $w$ such that $wa,wb$ are factors for letters $a\neq b$). Note that $R$ is finite iff $\xi$ is ultimately periodic. – Ale De Luca Nov 30 '13 at 0:17
• When you say "a set of infixes" do you literally mean a set, e.g. not only is no order information given but you also don't count multiplicities? – Qiaochu Yuan Nov 30 '13 at 20:03

This is a more detailed version of Alessandro's comment. By a classical theorem of Morse-Hedlund, one has that an infinite word $\eta$ is ultimately periodic iff there exists $m\geq 0$ so that $\eta$ has the same number of factors of length $m$ and $m+1$. Moreover, if $M$ is the number of subwords of length $m$, then the period of $\eta$ is bounded by $M$.
Given $\xi=pq^{\omega}$ with $q$ primitive, we can compute $m$. I guess $m=|p|+|q|+1$ works (probably I don't need the $+1$). Also one can prove $M\leq |p|+|q|$. (This can be found in Combinatorics, Automata and Number Theory handbook edited by Berthe and Rigo.) Now surely $n=2|p|+2|q|+1$ is more than safe enough. If $\eta$ has the same factors and prefixes of length $n$ as $\xi$, then it will have the same number of factors of length $m$ and $m+1$ so be ultimately periodic with period bounded by the same $M=|p|+|q|$. Hopefully you can work out the details from here.