% !TEX root = kFKM.tex

In this section, we prove the FKM portion of Theorem \ref{thm:main} and Corollary \ref{cor:kn}.

%We prove that $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ when $\mathbf{S} \in \CLASS{n}{k}$. 
%Before we prove our main theorem, we first introduce some basic notations and terminologies.
%Let $\alpha \beta = \alpha \cdot \beta$ denote the concatenation of two strings $\alpha$ and $\beta$.
%The \emph{aperiodic prefix} $\aprefix{\alpha}$ of $\alpha$ is the shortest string such that $\alpha = (\aprefix{\alpha})^t$; $\alpha$ is \emph{periodic} if $t > 1$ and is otherwise \emph{aperiodic} if $t = 1$.
%Recall a \emph{necklace} is a string that is less than or equal to each of its rotations in lexicographic order.  
%Denote the set of all necklaces that belong to $\mathbf{S}$ by $\mathbf{N}(\mathbf{S})$.

%Let $m = |\mathbf{N}(\mathbf{S})|$, and $\alpha_1, \alpha_2, \ldots, \alpha_m$ be the necklaces in $\mathbf{S}$ listed in lexicographic order.
%Thus,
%\begin{equation*}
%\FKM{\mathbf{S}} = \aprefix{\alpha_1} \cdot \aprefix{\alpha_2} \cdots \aprefix{\alpha_m}.
%\end{equation*}
%To simplify some of our proofs, we use the notation $\delta_i$ to denote $|\aprefix{\alpha_i}|$. 
%As a preliminary step of the proof of the main theorem, we first prove the following lemmas.
Let $\mathbf{S} \in \CLASS{n}{k}$ where $|\mathbf{S}| > 1$ and let $\alpha_1, \alpha_2, \ldots, \alpha_m$ be the lexicographic ordering of necklaces in $\mathbf{N}(\mathbf{S})$. 
Let $\aprefix{\alpha}$ be the aperiodic prefix of $\alpha$.
Let $\FKM{\mathbf{S}}$ be the sequence created by the generalized FKM algorithm applied to $\mathbf{S}$.
That is, 
\begin{equation*}
\FKM{\mathbf{S}} = \aprefix{\alpha_1} \cdot \aprefix{\alpha_2} \cdot \cdots \cdot \aprefix{\alpha_m}
\end{equation*}
where $\cdot$ denotes concatenation.
We first prove the following results:
\begin{enumerate}
\item $m > 1$ and $k^n \in \mathbf{N}(\mathbf{S})$,
\item there are no consecutive periodic necklaces in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$,
\item if $\alpha_i = a_1 a_2 \cdots a_{n-j-1} \, xk^j$ for some $x<k$ and $1 \leq i < m$, then $\alpha_{i+1}$ has prefix $a_1 a_2 \cdots $ $a_{n-j-1}$,  
\item $\alpha_1$ is a prefix of $\FKM{\mathbf{S}}$, 
\item $xk^n$ is a suffix of $\FKM{\mathbf{S}}$ where $x$ is the maximum value less than $k$ such that $xk^{n-1}\in \mathbf{N}(\mathbf{S})$, and
\item if $\alpha_i = a_1 a_2 \cdots a_n = a_1 a_2 \cdots a_{n-j-1} \, xk^j$ for some $x<k$ and $1 \leq i < m$, then $\FKM{\mathbf{S}}$ contains the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{|\aprefix{\alpha}|-j-1}$.
\end{enumerate}

%In the proof of the first lemma we let $\Rotate{\mathbf{S}}$ denote the closure of $\mathbf{S}$ under the rotation operation. 
%For example, if $\mathbf{S} = \{112, 113, 133\}$, then $\Rotate{\mathbf{S}} = \{112, 113, 121, 131, 133, 211, 311, 313, 331\}$. 

\begin{lemma} \label{lem:cardinality-neck}
If $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$, then $|\mathbf{N}(\mathbf{S})| > 1$ and $k^n \in \mathbf{N}(\mathbf{S})$. 
\end{lemma}
\begin{proof}
%Since $\mathbf{S} \in \CLASS{n}{k}$ and $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language, $k^n \in \mathbf{N}(\mathbf{S})$ by the definition of $k$-suffix langauge. 
%Clearly there can be no necklace in $\mathbf{N}(\mathbf{S})$ that is lexicographically larger than $k^n$. 
Since $|\mathbf{S}| > 1$, there exists a string $\alpha$ in $\mathbf{S}$ such that $\alpha \neq k^n$. 
Since $\mathbf{S}$ is closed under rotation, it also contains a necklace $\beta$ such that $\beta \neq k^n$ and $\beta  \in \Rotate{\alpha}$. 
Also, since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language, $k^n$ must also be in $\mathbf{N}(\mathbf{S})$.
%If $\alpha$ is a necklace, then clearly $\mathbf{N}(\mathbf{S})>1$. 
%Otherwise, since $\mathbf{S}$ is closed under rotation, there exists another string $\beta$ in $\mathbf{S}$ such that $\beta \in \Rotate{\alpha}$ and $\beta \in \mathbf{N}(\mathbf{S})$. 
Thus $\mathbf{N}(\mathbf{S})>1$ and $k^n \in \mathbf{N}(\mathbf{S})$. 
\end{proof}

\begin{lemma} \label{lem:consecutive-neck}
%Let $\alpha_1, \alpha_2, \ldots, \alpha_m$ denote the lexicographic ordering of necklaces in $\mathbf{N}(\mathbf{S})$ and $m > 1$. 
%If $\alpha_{i+1}$ is periodic and $1 \leq i < m$, then $\alpha_{i}$ is aperiodic.
If $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$, then there are no consecutive periodic necklaces in the lexicographic order of $\mathbf{N}(\mathbf{S})$. 
\end{lemma}
\begin{proof}
Let $\alpha$ and $\beta$ be consecutive necklaces in the lexicographic order of $\mathbf{N}(\mathbf{S})$ with $\alpha < \beta$. 
%We know they exist by Lemma~\ref{lem:cardinality-neck}.
Since $\alpha < \beta$ we have $\alpha \neq k^n$, and so $\alpha$ contains a rightmost symbol $x$ that is less that $k$.
That is, $\alpha = a_1 a_2 \cdots a_{n-j-1} x k^j$ where $x < k$ and $j \geq 0$.

Let $y$ be the smallest value such that $a_1 a_2 \cdots a_{n-j-1} y k^j \in \mathbf{N}(\mathbf{S})$ and $x < y \leq k$; the value $y$ exists because $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language.
Notice that $\beta$ must have $a_1 a_2 \cdots a_{n-j-1} y$ as a prefix.

Now suppose that $\alpha$ is periodic.
Therefore, $\alpha = (\gamma x k^j)^t$ for some $\gamma$ and $t > 1$. 
%Since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language, this implies that $\beta = (\gamma x k^j)^{t-1} \gamma y k^j$ for some $y > x$.   % Note: This is not true because it might not be the next necklace in lex order!
Therefore, $\beta$ has $(\gamma x k^j)^{t-1} \gamma y$ as a prefix.
However, $(\gamma x k^j)^{t-1} \gamma y$ is not the prefix of any periodic necklace of length $n$.
Therefore, $\beta$ is not periodic.
%Clearly $\beta$ is aperiodic because $\gamma y k^j > \gamma x k^j$. % What about other periods?
%Suppose $\beta$ is periodic. % with $\aprefix{\alpha_{i+1}} = \beta$.
%Observe that $\beta$ is the lexicographically smallest necklace with the prefix $\aprefix{\beta}$.
%Therefore, $\alpha$ is the lexicographically largest necklace in $\mathbf{N}(\mathbf{S})$ with a prefix that is lexicographically smaller than $\aprefix{\beta}$.
%Since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix languages, this implies that $\alpha$ has suffix $k^{n-|\aprefix{\beta}|}$.
%The only periodic string with this suffix is $k^n$ since $|\aprefix{\beta}| \leq {n\over 2}$. 
%However, since $\alpha < \beta$, $\alpha \neq k^n$.
%Therefore $\alpha$ must be aperiodic.
\end{proof}

\begin{lemma} \label{lem:next-necklace-prefix}
Suppose $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$. 
Let $\alpha$ and $\beta$ denote consecutive necklaces in the lexicographical ordering of $\mathbf{N}(\mathbf{S})$ such that $\alpha < \beta$. 
If $\alpha = a_1 a_2 \cdots a_{n-j-1} \, xk^j$ for some $x < k$, then $\beta$ has prefix $a_1 a_2 \cdots $ $a_{n-j-1}$. 
\end{lemma}
\begin{proof}
%By Lemma~\ref{lem:cardinality-neck}, $|\mathbf{N}(\mathbf{S})| > 1$ thus $\alpha$ and $\beta$ exist. 
Since $\alpha$ is a necklace, clearly $a_1 a_2 \cdots a_{n-j-1} \, yk^j$ is a necklace for all $x < y \leq k$. 
There exists some smallest value of $y$ such that $a_1 a_2 \cdots a_{n-j-1} \, yk^j \in \mathbf{N}(\mathbf{S})$ since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix langauge. 
Since $\beta$ is lexicographically smaller or equal to $a_1 a_2 \cdots a_{n-j-1} \, yk^j$ but lexicographically larger than $\alpha$, clearly $\beta$ has prefix $a_1 a_2 \cdots a_{n-j-1}$. 
%Let $y$ be the smallest value such that $y > x$ and $a_1 a_2 \cdots a_{n-j-1} \, yk^j \in \mathbf{N}(\mathbf{S})$. 
%within $\alpha_i$ the suffix $xk^j$ can be replaced by $yk^j$ to give another necklace in $\mathbf{S}$. 
%Also, the string $a_1 a_2 \cdots a_{n-j-1} \, yk^j \in \mathbf{N}(\mathbf{S})$ since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix langauge. 
%such a value of $y$ exists since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix langauge. 
%Furthermore, $\beta = a_1 a_2 \cdots a_{n-j-1} \, yk^j$ since $\alpha$ and $\beta$ are consecutive necklaces in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$ with $\alpha < \beta$ and $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language, there can be no necklace between it and $\alpha$ in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$.
%Therefore, $\beta$ has prefix $a_1 a_2 \cdots a_{n-j-1}$. %$\beta$ as claimed with $|\beta| = n-j-1$.
\end{proof}

\begin{lemma} \label{lem:fkm-prefix}
If $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$, then the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$ is a prefix of $\FKM{\mathbf{S}}$. 
\end{lemma}
\begin{proof}
Let $\alpha = a_1 a_2 \cdots a_{n-j-1} \, xk^j$ be the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$ for some $x < k$.  
Such a value of $x$ exists since $\alpha \neq k^n$ by Lemma~\ref{lem:cardinality-neck}. 
If $\alpha$ is aperiodic, then clearly $\FKM{\mathbf{S}}$ has prefix $\alpha$. 
Otherwise if $\alpha$ is periodic, then $\alpha = (\aprefix{\alpha})^t$ for some $t > 1$. 
Let $\beta$ be the necklace that is after $\alpha$ in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$.
Such a necklace exists since $|\mathbf{N}(\mathbf{S})| > 1$ by Lemma~\ref{lem:cardinality-neck}. 
By Lemma~\ref{lem:consecutive-neck}, $\beta$ is aperiodic. 
Also by Lemma~\ref{lem:next-necklace-prefix}, $\beta$ has prefix $a_1 a_2 \cdots a_{n-j-1}  = (\aprefix{\alpha})^{t-1} a_{(t-1)|\aprefix{\alpha}|+1} a_{(t-1)|\aprefix{\alpha}|+2} \cdots a_{n-j-1}$. 
Therefore, $\aprefix{\alpha} \cdot \aprefix{\beta}$ has prefix $\aprefix{\alpha} \cdot (\aprefix{\alpha})^{t-1} = \alpha$. 
\end{proof}

%\begin{lemma} \label{lem:lexi}
%Let $\alpha_1, \alpha_2, \ldots, \alpha_m$ denote the lexicographic ordering of necklaces in $\mathbf{N}(\mathbf{S})$ and $m > 1$. Successive necklaces in lexicographic ordering satisfy the following two properties:
%\begin{itemize}
%\item[(P1)] If $\alpha_{i+1}$ is periodic and $1 \leq i < m$, then $\alpha_{i}$ is aperiodic.
%\item[(P2)] If $\alpha_i = a_1 a_2 \cdots a_{n-j-1} \, xk^j$ for some $x < k$, then $\alpha_{i+1}$ has prefix $a_1 a_2 \cdots $ $a_{n-j-1}$. 
%\end{itemize}
%\end{lemma}

%\begin{proof}
%For (P1), suppose that $\alpha_{i+1}$ is periodic with $\aprefix{\alpha_{i+1}} = \beta$.
%Observe that $\alpha_{i+1}$ is the lexicographically smallest necklace with the prefix ${\beta}$.
%Therefore, $\alpha_{i}$ is the lexicographically largest necklace in $\mathbf{N}(\mathbf{S})$ with a prefix that is lexicographically smaller than ${\beta}$.
%Since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix languages, this implies that $\alpha_{i}$ has suffix $k^{n-|\beta|}$.
%The only periodic string with this suffix is $k^n$ since $|\beta| \leq n/2$, however $\alpha_{i} \neq k^n$ since $i \neq m$.
%Therefore, $\alpha_{i}$ is aperiodic.

%For (P2), let $y$ be the smallest value such that $a_1 a_2 \cdots a_{n-j-1} \, yk^j \in \mathbf{N}(\mathbf{S})$. 
%Such a value of $y$ exists since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix langauge. 
%Furthermore, $\alpha_{i+1} = a_1 a_2 \cdots a_{n-j-1} \, yk^j$ since there can be no necklace in $\mathbf{N}(\mathbf{S})$ between it and $\alpha_i$ in lexicographic order.
%Therefore, $\alpha_{i+1}$ has prefix $a_1 a_2 \cdots a_{n-j-1}$. %$\beta$ as claimed with $|\beta| = n-j-1$.
%\end{proof}

\begin{lemma} \label{cor:properties-1}
If $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$, then $\FKM{\mathbf{S}}$ has suffix $xk^n$, where $x$ is the maximum value such that $x<k$ and $xk^{n-1} \in \mathbf{N}(\mathbf{S})$.
\end{lemma}

\begin{proof}
Let $\alpha$ and $\beta$ denote the two lexicographically largest necklace in $\mathbf{N}(\mathbf{S})$ such that $\alpha < \beta$. 
By Lemma~\ref{lem:cardinality-neck}, $\beta = k^n$ and $\alpha$ exists since $|\mathbf{N}(\mathbf{S})| > 1$. 
%Since $\mathbf{S} \in \CLASS{n}{k}$ and $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language, $\alpha_m = k^n$. 
%Furthermore, since $|\mathbf{S}| > 1$, $\alpha_{m-1}$ exists. 
%Furthermore, there exists a necklace in $\mathbf{N}(\mathbf{S})$ that is not equal to $k^n$ since $|\mathbf{N}(\mathbf{S})| > 1$. 
There exists a maximum value $x < k$ such that $xk^{n-1} \in \mathbf{N}(\mathbf{S})$ since $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language. 
Observe that $\alpha = x k^{n-1}$ since there can be no necklace between it and $\beta$ in the lexicographical ordering of $\mathbf{N}(\mathbf{S})$. 
Therefore, $\FKM{\mathbf{S}}$ has suffix $\aprefix{\alpha} \cdot \aprefix{\beta} = x k^{n-1} \cdot k = xk^n$.
\end{proof}

\begin{lemma} \label{cor:properties-2}
Suppose $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$. If $\alpha = a_1 a_2 \cdots a_n = a_1 a_2 \cdots a_{n-j-1} \, xk^j \in \mathbf{N}(\mathbf{S})$ for some $x < k$, then $\FKM{\mathbf{S}}$ contains the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots $ $a_{|\aprefix{\alpha}|-j-1}$. 
\end{lemma}

\begin{proof}
Let $p = |\aprefix{\alpha}|$ and let $\beta$ denote the necklace that is after $\alpha$ in the lexicographic ordering $\mathbf{N}(\mathbf{S})$. 
Clearly $\alpha \neq k^n$ and $\beta$ exists by Lemma~\ref{lem:cardinality-neck}. 
%and similarly denote $\alpha_{i+2}$ as the necklace in $\mathbf{N}(\mathbf{S})$ that is after $\alpha_{i+1}$ in lexicographic ordering when $i < m - 1$. 
By Lemma~\ref{lem:next-necklace-prefix} $\beta$ has prefix $a_1 a_2 \cdots a_{n-j-1}$. 
By Lemma~\ref{lem:consecutive-neck} at most one of these necklaces is periodic and we proceed in three cases.
\begin{enumerate}
\item If both $\alpha$ and $\beta$ are aperiodic, then $\aprefix{\alpha} \cdot \aprefix{\beta} = {\alpha} \cdot {\beta}$ is a substring of $\FKM{\mathbf{S}}$ which has prefix $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{n-j-1}  = a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$. 

\item If $\alpha$ is periodic and $\beta$ is aperiodic, then $\aprefix{\alpha} \cdot \aprefix{\beta} = \aprefix{\alpha} \cdot \beta$ is a substring of $\FKM{\mathbf{S}}$ which has prefix $\aprefix{\alpha} \cdot a_1 a_2 \cdots a_{n-j-1}$. Let $\alpha = (\aprefix{\alpha})^t$ for some $t > 1$. 
Observe that 
\begin{eqnarray}
\aprefix{\alpha} \cdot a_1 a_2 \cdots a_{n-j-1} &=&  \aprefix{\alpha} \cdot (\aprefix{\alpha})^{t-1} a_{(t-1)p+1} a_{(t-1)p+2} \cdots a_{n-j-1}\nonumber \\
&=& \alpha  \cdot a_{(t-1)p+1}  a_{(t-1)p+2} \cdots a_{n-j-1}\nonumber \\
&= & a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}\nonumber.
\end{eqnarray}

\item If $\alpha$ is aperiodic and $\beta$ is periodic, then there are two subcases.
If $\beta = k^n$, the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$ is simply equal to $a_1 a_2 \cdots a_n$ due to the fact that $\alpha$ has suffix $k^{n-1}$.
The desired substring is found in the length $n+1$ suffix of $\FKM{\mathbf{S}}$ by Lemma~\ref{cor:properties-1}.  
%Therefore, the desired substring is found in $\aprefix{\alpha_i} = a_1 a_2 \cdots a_n$.
Otherwise if $\beta \neq k^n$, then let $\gamma$ be the necklace that is after $\beta$ in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$. 
Such a necklace exists since $\beta \neq k^n$. 
Notice that $\gamma$ is aperiodic by Lemma~\ref{lem:consecutive-neck}.
Therefore, by the arguments in the previous case, $\aprefix{\beta} \cdot \aprefix{\gamma}$ has prefix $\beta$.
Therefore, $\aprefix{\alpha} \cdot \aprefix{\beta} \cdot \aprefix{\gamma}$ is a substring of $\FKM{\mathbf{S}}$ which has prefix $\alpha \cdot \beta$. The prefix $\alpha \cdot \beta$ contains the prefix $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$. 
\end{enumerate}
Thus $\FKM{\mathbf{S}}$ contains the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots $ $a_{|\aprefix{\alpha}|-j-1}$. 
\end{proof}


%\begin{lemma} \label{cor:properties}
%Suppose $\mathbf{S} \in \CLASS{n}{k}$. 
%Let $\alpha_1, \alpha_2, \ldots, \alpha_m$ denote the lexicographic ordering of necklaces in $\mathbf{N}(\mathbf{S})$. 
%Then $\FKM{\mathbf{S}}$ satisfies the following four properties:
%\begin{itemize}
%\item[(P1)] If $\alpha_{i}$ is periodic and $1 < i \leq m$, then $\alpha_{i-1}$ is aperiodic.
%\item[(P2)] If $\alpha_i = a_1 a_2 \cdots a_{n-j-1} \, xk^j$ for some $x < k$, then $\alpha_{i+1}$ has prefix $a_1 a_2 \cdots $ $a_{n-j-1}$. 
%\item[(P3)] $\FKM{\mathbf{S}}$ has prefix $\alpha_1$ when $\alpha_1 \neq k^n$. 
%\item[(P4)] If $\alpha_i = a_1 a_2 \ldots a_n$, then $\FKM{\mathbf{S}}$ contains the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots $ $a_{|\alpha_i|-j-1}$ when $i < m$. 
%\end{itemize}
%\end{lemma}
%\begin{proof}



%For (P4), let $p = |\alpha_i|$. 
%By (P2) $\alpha_{i+1}$ has prefix $a_1 a_2 \cdots a_{n-j-1}$. 
%By (P1) at most one of these necklaces is periodic and we proceed in three cases.
%\begin{enumerate}
%\item If both $\alpha_i$ and $\alpha_{i+1}$ are aperiodic, then $\aprefix{\alpha_{i}} \cdot \aprefix{\alpha_{i+1}} = {\alpha_{i}} \cdot {\alpha_{i+1}}$ which has prefix $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{n-j-1}  = a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$. 

%\item If $\alpha_i$ is periodic and $\alpha_{i+1}$ is aperiodic, then $\aprefix{\alpha_{i}} \cdot \aprefix{\alpha_{i+1}}$ has prefix $\aprefix{\alpha_{i}} \cdot a_1 a_2 \cdots a_{n-j-1}$. Observe that 
%\begin{eqnarray}
%\aprefix{\alpha_{i}} \cdot a_1 a_2 \cdots a_{n-j-1} &=&  \aprefix{\alpha_{i}} \cdot \aprefix{\alpha_{i}}^{t-1} a_{(t-1)p+1} a_{(t-1)p+2} \cdots a_{n-j-1}\nonumber \\
%&=& \alpha_i  \cdot a_{(t-1)p+1}  a_{(t-1)p+2} \cdots a_{n-j-1}\nonumber \\
%&= & a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}\nonumber
%\end{eqnarray}

%\item If $\alpha_i$ is aperiodic and $\alpha_{i+1}$ is periodic, then there are two subcases.
%If $i = m-1$, then the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$ is simply equal to $a_1 a_2 \cdots a_n$ due to the fact that $\alpha_{m-1}$ has suffix $k^{n-1}$.
%Therefore, the desired substring is found in $\aprefix{\alpha_i} = a_1 a_2 \cdots a_n$.
%Otherwise if $i < m-1$, then $\alpha_{i+2}$ is aperiodic by (P1).
%Therefore, by the arguments in the previous case, $\aprefix{\alpha_{i+1}} \cdot \aprefix{\alpha_{i+2}}$ has prefix $\alpha_{i+1}$.
%Therefore, $\aprefix{\alpha_{i}} \cdot \aprefix{\alpha_{i+1}} \cdot \aprefix{\alpha_{i+2}}$ has prefix $\alpha_i \cdot \alpha_{i+1}$, which prefix $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$. 
%\end{enumerate}
%Thus $\FKM{\mathbf{S}}$ contains the substring $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots $ $a_{|\alpha_i|-j-1}$ when $i < m$ as claimed. 
%\end{proof}
%\end{adjustwidth}


%
%A \emph{Lyndon word} is an aperiodic necklace.
%A string is a \emph{prenecklace} if it is a prefix of some necklace. 
%We denote the set of prenecklaces, necklaces and Lyndon words in a set $\mathbf{S}$ as $\mathbf{P}(\mathbf{S})$, $\mathbf{N}(\mathbf{S})$ and $\mathbf{L}(\mathbf{S})$ respectively. 
%For example:
%\begin{itemize}
%\item $\mathbf{P}(\TUPLES{3}{2}) = \{111, 112, 121, 122, 222\}$,
%\item $\mathbf{N}(\TUPLES{3}{2}) = \{111, 112, 122, 222\}$,
%\item $\mathbf{L}(\TUPLES{3}{2}) = \{112, 122\}$.
%\end{itemize}
%Observe that the prenecklace 121 is a prefix of the necklace 1212 so it is in $\mathbf{P}(\TUPLES{3}{2})$. 

%We prove Theorem~\ref{thm:kFKM} by induction on number of necklaces in $\mathbf{S}$.  
We now prove the FKM portion of Theorem \ref{thm:main}.
%proceed to the proof of the main theorem of our paper. %which prove that $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ when $\mathbf{S} \in \CLASS{n}{k}$. 
%Suppose that $\mathbf{S} \in \CLASS{n}{k}$. % and $U = \FKM{\mathbf{S}}$.

%$\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ if it contains each string in $\mathbf{S}$ as a substring.


\begin{theorem} \label{thm:kFKM}
If $\mathbf{S} \in \CLASS{n}{k}$, then $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$.
\end{theorem}

\begin{proof}%[Proof (Theorem~\ref{thm:kFKM})]
%Suppose that $\mathbf{S} \in \CLASS{n}{k}$ and let $U = \FKM{\mathbf{S}}$.
%Since $\mathbf{S}$ is closed under rotation and its strings all have length $n$, the definition of $\FKM{\mathbf{S}}$ implies $|U| = |\mathbf{S}|$.
%Therefore, $U$ is a universal cycle for $\mathbf{S}$ if it contains each string in $\mathbf{S}$ once as a circular substring.

%Let $m = |\mathbf{N}(\mathbf{S})|$.
%Let $\alpha_1, \alpha_2, \ldots, \alpha_m$ denote the lexicographic ordering of necklaces in $\mathbf{N}(\mathbf{S})$. 
Since $\mathbf{S}$ is closed under rotation by the definition of $\CLASS{n}{k}$ and its strings all have length $n$, the definition of $\FKM{\mathbf{S}}$ implies $|\FKM{\mathbf{S}}| = |\mathbf{S}|$.
Therefore, to prove $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$, we only need to show that $\FKM{\mathbf{S}}$ contains each string in $\mathbf{S}$ as a substring when the sequence is considered circularly. 

When $|\mathbf{N}(\mathbf{S})| = 1$, $\mathbf{S} = \mathbf{N}(\mathbf{S}) = \{k^n\}$.  In this case, $\FKM{\mathbf{S}}$ is the single character $k$ which is a universal cycle for $\mathbf{S}$. For the remainder of the proof we assume $|\mathbf{N}(\mathbf{S})|>1$.

Now consider a rotation $\beta = a_i a_{i+1} \cdots a_n a_1 a_2 \cdots a_{i-1}$ of an arbitrary necklace $\alpha = a_1 a_2 \ldots a_n$ in $\mathbf{N}(\mathbf{S})$.
By Lemma~\ref{cor:properties-1} we can assume that $\alpha \neq k^n$ since the only rotation of $k^n$ is found at the end of $\FKM{\mathbf{S}}$.
Therefore, without loss of generality, we suppose $\alpha$ has suffix $x k^j$ for some $x < k$.
Let $p = |\aprefix{\alpha}|$.
We show that all $p$ distinct rotations of $\alpha$ exist in $\FKM{\mathbf{S}}$.
There are two cases depending on the value of $i$. 

\begin{description}
\item[Case 1: $0 < i \leq p - j - 1$] 
By Lemma~\ref{cor:properties-2}, $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$ is a substring of $\FKM{\mathbf{S}}$. 
Observe that $\beta$ is a substring of $a_1 a_2 \cdots a_n \cdot a_1 a_2 \cdots a_{p-j-1}$ when $0 < i \leq p - j - 1$. 
\item[Case 2: $p-j-1 < i \leq p$] 
Observe that $\beta = k^{n-i} a_1 a_2 \cdots a_{i-1}$ when $p-j-1 < i \leq p$. 
Let $\gamma$ be the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$ such that it has prefix $a_1 a_2 \cdots a_{i-1}$.
If $\gamma$ is not the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$, then the previous necklace of $\gamma$ has the suffix $k^{n-i}$ due to the fact that $\mathbf{N}(\mathbf{S})$ is a $k$-suffix language.
On the other hand, if $\gamma$ is the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$, then the previous $n-i$ symbols in $\FKM{\mathbf{S}}$ are $k^{n-i}$ by Lemma~\ref{cor:properties-1} when the sequence is considered circularly.
Thus, $\beta$ is a substring of $\FKM{\mathbf{S}}$. 
\end{description}
%Thus to complete the proof, we only need to show the existence of the substrings $a_{n-s+1} a_{n-s+2} \cdots a_{n} \cdot a_1 a_2 \cdots a_{n-s} = k^s a_1 a_2 \cdots a_{n-s}$ in $\FKM{\mathbf{S}}$ for all $1 \leq s \leq j$. These substrings are the remaining rotations of $\alpha$ starting from any of its last $j$ symbols. 
Therefore, $\FKM{\mathbf{S}}$ contains each string in $\mathbf{S}$ as a substring and is a universal cycle for $\mathbf{S}$ since $|\FKM{\mathbf{S}}| = |\mathbf{S}|$.
\end{proof}


%In addition to sets in $\CLASS{n}{k}$, $\FKM{\mathbf{S}}$ can also construct universal cycles for sets ${\mathbf{S}}$ that are ``almost" in $\CLASS{n}{k}$. 
%The following lemma provides a usage of $\FKM{\mathbf{S}}$ on a broader language. 
%From the proof of Theorem \ref{thm:kFKM}, $\FKM{\mathbf{S}}$ for $\mathbf{S} \subseteq \CLASS{n}{k}$ ends with the suffix $k^n$. 
%It is easy to see that removing the last aperiodic prefix $\aprefix{\alpha_m} = k$ only removes the tuple $k^n$ in $\FKM{\mathbf{S}}$ but preserves the strings in $\mathbf{S} \setminus \{k^n\}$. %since $\aprefix{\alpha_{m-1}}$ contains the suffix $k^{n-1}$. 

We now extend this result to the FKM portion of Corollary \ref{cor:kn}.

\begin{corollary} \label{cor:almost-k-suffix}
If $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$, then $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$.  
\end{corollary}  
\begin{proof}
If $\mathbf{S} \in \CLASS{n}{k}$, then by Theorem~\ref{thm:kFKM}, $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$. 
Otherwise if $\mathbf{S} \notin \CLASS{n}{k}$ but $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$, then observe that $\FKM{\mathbf{S}}\cdot k = \FKM{\mathbf{S} \cup k^n}$.
By Theorem~\ref{thm:kFKM} $\FKM{\mathbf{S}}\cdot k$ is a universal cycle for $\mathbf{S} \cup k^n$. 
By Lemma~\ref{cor:properties-1}, $\FKM{\mathbf{S}}\cdot k$ ends with the suffix $k^n$. 
%Hence, removing the last $k$ in $\FKM{\mathbf{S}}\cdot k$ only removes the string $k^n$ while preserves all strings in $\mathbf{S} \cup \{k^n\} \setminus \{k^n\} = \mathbf{S}$ as a substring when considered circularly. % and has length $|\mathbf{S}|$. 
Hence, removing the last $k$ in $\FKM{\mathbf{S}}\cdot k$ only removes its substring $k^n$ when considered circularly.
Thus, all other strings in $\mathbf{S} \cup \{k^n\} \setminus \{k^n\} = \mathbf{S}$ are preserved.
Therefore, $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ since $\FKM{\mathbf{S}}$ has length $|\mathbf{S}|$.
%Otherwise if $\mathbf{S} \notin \CLASS{n}{k}$ but $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$, then $\FKM{\mathbf{S}\cup \{k^n\}}$ is a universal cycle for $\mathbf{S} \cup \{k^n\}$. 
%
%Observe that by removing the last aperiodic prefix $\aprefix{k^n} = k$ in $\FKM{\mathbf{S}\cup \{k^n\}}$, all the strings in $\mathbf{S} \cup \{k^n\} \setminus \{k^n\}$ are still substrings of the sequence. 
%Furthermore, the sequence is a concatenation of all aperiodic prefixes of necklaces in lexicographic ordering of $\mathbf{N}(\mathbf{S} \cup \{k^n\} \setminus \{k^n\}) = \mathbf{N}(\mathbf{S})$. 
%Thus, the resulting sequence is equivalent to $\FKM{\mathbf{S}}$, which is also a universal cycle for $\mathbf{S}$ since it contains all strings in $\mathbf{S} \cup \{k^n\} \setminus \{k^n\} = \mathbf{S}$ as a substring exactly once and has length $|\mathbf{S}|$. 
%Therefore, $\FKM{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ when $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$.
\end{proof}


The proof of Theorem \ref{thm:kFKM} explicitly states where the rotations of each necklace are found. 
To specify the position of a substring in a universal cycle we introduce the following notation.
Suppose $\FKM{\mathbf{S}} = u_0 u_1 \cdots u_{|\mathbf{S}|-1}$ is a universal cycle for $\mathbf{S} \subseteq \TUPLES{n}{k}$ and $\alpha \in \mathbf{S}$.
Let $\last{\alpha}$ be the last position of the substring $\alpha$ in $\FKM{\mathbf{S}}$.
%In other words, if $\last{\alpha} = i$, then $u_{i-n+1} u_{i-n+2} \cdots u_{i} = \alpha$ where $0 \leq i < |\mathbf{S}|$ and the other index expressions are taken modulo $|\mathbf{S}|$.
In other words, if $u_{i-n+1} u_{i-n+2} \cdots u_{i} = \alpha$, then $\last{\alpha} = i$ because $i$ is the last position of the substring $\alpha$, where $0 \leq i < |\mathbf{S}|$ and the other index expressions are taken modulo $|\mathbf{S}|$.

%When the context is clear we let $\last[U]{\alpha} = \last{\alpha}$.
\begin{corollary} 
\label{cor:where}
If $\mathbf{S} \in \CLASS{n}{k}$, $\alpha \in \mathbf{N}(\mathbf{S})$ has suffix $xk^j$ for some $x<k$, and $\beta$ is a rotation of $\alpha$, then $\last{\beta} \leq \last{\alpha} + |\aprefix{\alpha}|{-}j{-}1$. %with respect to $\FKM{\mathbf{S}}$.
\end{corollary}
\begin{proof}
Let $\alpha = a_1 a_2 \cdots a_{n}$.
% and $\last{\alpha} = j$.
By Lemma~\ref{cor:properties-2}, the rotations of $\alpha$ starting from $a_i$ where $1 \leq i \leq |\aprefix{\alpha}|-j$ are all found in succession starting from $\alpha$ itself.
In particular, the last of these rotations $\beta$ has $\last{\beta} = \last{\alpha}+|\aprefix{\alpha}|-j-1$.
The remaining rotations of $\alpha$ end within the first necklace in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$ with prefix $a_1 a_2 \cdots a_i$ for some $i$ satisfying $1 \leq i \leq |\aprefix{\alpha}|-j-1$.
None of these necklaces appear after $\alpha$ in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$, thus $\last{\beta} < \last{\alpha}$ for any such rotation of $\beta$.
\end{proof}
\noindent
%In other words, the last symbol of $\beta$ either appears before $\alpha$'s last symbol, or at most $|\aprefix{\alpha}|-j-1$ symbols after $\alpha$'s last symbol within the FKM universal cycle. 
This information will be crucial for the greedy algorithm in Section \ref{sec:greedy}.


%\begin{theorem} \label{thm:FKM-CAT}
%Universal cycles for $\mathbf{S} \subseteq \TUPLES{n}{k}$
%\begin{enumerate}[label=\roman*)]
%\item with sum at least $s$;
%\item with at least $\ell_k$ copies of $k$;
%\item with at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$;
%\item that avoid rotations of periodic necklaces; and
%\item that are union or intersection of any of the above,
%\end{enumerate}
%can be generated in constant amortized time per symbol using $O(n)$ space. 
%\end{theorem}

%\begin{proof}
%We prove the algorithms for the combinatorial objects (i) - (v) satisfy the two conditions in Theorem~\ref{thm:FKM-CAT-1}. 
%Thus their universal cycles can be generated in constant amortized time per symbol by Theorem~\ref{thm:FKM-CAT-1}. 
%\end{proof}
