% !TEX root = kFKM.tex

%In this section, we define the term $k$-suffix language and prove that universal cycles exist for sets in such language. A set can be defined to be in $k$-suffix language in two ways. We then introduce a few sets that are in the language. 

In this section we ground our construction results with a simple existence proof.
We also give a list of interesting universal cycles constructed by our results.

\subsection{Class of Strings} \label{sec:examples_CLASS}

The class of strings covered by Theorem \ref{thm:main} is defined below.
Recall that $\NeckSubset{\mathbf{S}}$ denotes the necklaces in $\mathbf{S} \subseteq \TUPLES{n}{k}$.
That is, $\NeckSubset{\mathbf{S}} = \mathbf{S} \cap \NECKS{n}{k}$.

\begin{definition} \label{def:CLASS}
Let $\CLASS{n}{k}$ be the set that contains precisely all $\mathbf{S} \subseteq \TUPLES{n}{k}$ that are closed under rotation, and whose necklaces $\NeckSubset{\mathbf{S}}$ form a $k$-suffix language. 
%Let $\CLASS{n}{k} \subseteq 2^{\TUPLES{n}{k}}$ contain all $\mathbf{S} \subseteq \TUPLES{n}{k}$ that are closed under rotation, and whose necklaces $\NeckSubset{\mathbf{S}}$ form a $k$-suffix languages. 
\end{definition}

%When applying Definition \ref{def:CLASS} it is sometimes more convenient to prove that $\mathbf{S}$ is a $k$-suffix language.
To prove that $\mathbf{S} \in \CLASS{n}{k}$ we need to prove that $\mathbf{S}$ is closed under rotation and its subset of necklaces $\NeckSubset{\mathbf{S}}$ is a $k$-suffix language.
Sometimes it is more convenient to prove that the entire set $\mathbf{S}$ is a $k$-suffix language rather than its necklace subset $\NeckSubset{\mathbf{S}}$.
The following lemma proves that this approach is also sufficient.

%In fact, Corollary \ref{cor:closure} and Lemma~\ref{lem:necklaceIdeal} imply that this is sufficient for our purposes.
%More specifically, these two results prove that if $\mathbf{S}$ is a $k$-suffix language, then $\NeckSubset{\mathbf{S}} = \mathbf{S} \cap \NECKS{n}{k}$ is also a $k$-suffix language.
%We summarize the result of this argument below.

%\begin{remark} \label{rem:CLASS}
%If $\mathbf{S}$ is a $k$-suffix language that is closed under rotation then $\mathbf{S} \in \CLASS{n}{k}$.
%\end{remark}
%\begin{remark} \label{rem:kSuffixNecklaces}
%If $\mathbf{S} \subseteq \TUPLES{n}{k}$ is a $k$-suffix language, then the necklaces in $\mathbf{S}$ are a $k$-suffix language.
%\end{remark}

\begin{lemma} \label{lem:CLASS}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$.
If $\mathbf{S}$ is closed under rotation and $\mathbf{S}$ is a $k$-suffix language, then $\mathbf{S} \in \CLASS{n}{k}$.
\end{lemma}
\begin{proof}
Recall that $\NECKS{n}{k}$ is a $k$-suffix language by Lemma \ref{lem:necklaceIdeal}.
Therefore, if $\mathbf{S}$ is a $k$-suffix language, then so is $\NeckSubset{\mathbf{S}} = \mathbf{S} \cap \NECKS{n}{k}$.
Therefore, if $\mathbf{S}$ is also closed under rotation, then $\mathbf{S}$ is a $k$-suffix language by Definition \ref{def:CLASS}.
\end{proof}


%We note that Lemma \ref{lem:CLASS} does not cover all sets that are covered by Definition \ref{def:CLASS}.
We note that Lemma \ref{lem:CLASS} does not cover all sets in $\CLASS{n}{k}$.
For example, 
\begin{equation*}
\mathbf{S_3} = \{1111{,}
1112{,}1121{,}1211{,}2111{,}
1122{,}1221{,}2211{,}2112{,}
1222{,}2122{,}2212{,}2221{,}
2222\},
\end{equation*}
is in $\CLASS{4}{2}$.
However,  since $1211 \in \mathbf{S_3}$ and $1212 \notin \mathbf{S_3}$, the set $\mathbf{S_3}$ is not a $k$-suffix language by itself.
%is closed under rotation and its subset of necklaces $\NeckSubset{\mathbf{S}} = \{1111, 1112, 1122, 1222,2222\}$ is a $k$-suffix language.


%=============================
\subsection{Existence} \label{sec:examples_exist}

Stevens and Williams \cite{existRotate} characterized the existence of universal cycles for subsets of $\TUPLES{n}{k}$ that are closed under rotation.
We now use one of their results to prove that every set in $\CLASS{n}{k}$ has a universal cycle.
First we recount a definition from \cite{existRotate}.
A set $\mathbf{S} \subseteq \TUPLES{n}{k}$ is \emph{increasable} if the following is true:
\begin{quote}
If $\alpha \in \mathbf{S}$ and $\alpha$ is not equal to $k^n$, then there exists a symbol in $\alpha$ that can be increased and the resulting string is also in $\mathbf{S}$.
\end{quote}
More precisely, $\mathbf{S}$ is increasable if $a_1 a_2 \cdots a_n \in \mathbf{S}$ and $a_1 a_2 \cdots a_n \neq k^n$, then there exist $i$ and $b > a_i$ such that $a_1 \, a_2 \, \cdots \, a_{i-1} \, b \, a_{i+1} \, a_{i+2} \, \cdots \, a_n \in \mathbf{S}$.

\begin{theorem}[\cite{existRotate}] \label{thm:existRotate}
If $\mathbf{S} \subseteq \TUPLES{n}{k}$ is increasable and closed under rotation, then $\mathbf{S}$ has a universal cycle.
\end{theorem}

\begin{corollary} \label{cor:exist}
Every $\mathbf{S} \in \CLASS{n}{k}$ has a universal cycle.
\end{corollary}
\begin{proof}
By Definition \ref{def:CLASS}, each $\mathbf{S} \in \CLASS{n}{k}$ is closed under rotation.
Consider an arbitrary $\alpha \in \mathbf{S}$ with $\alpha \neq k^n$, and let $\beta \in \mathbf{S}$ be its smallest rotation in lexicographic order.
By Definition \ref{def:CLASS}, there is at least one symbol in $\beta$ that is less than $k$ that can be increased to $k$ so that the resulting string is also in $\mathbf{S}$.
Since $\mathbf{S}$ is closed under rotation, the same statement is true for $\alpha$.
Thus, $\mathbf{S}$ is increasable.
Hence, $\mathbf{S}$ has a universal cycle by Theorem~\ref{thm:existRotate}.
\end{proof}



%=============================
\subsection{Examples} \label{sec:examples_examples}

\begin{comment}
\begin{enumerate}[label=\roman*)]
\item $\TUPLES{n}{k}$;
\item $\mathbf{S}_1$ that contains all strings in $\TUPLES{n}{k}$ with sum at least $s$;
\item $\mathbf{S}_2$ that contains all strings in $\TUPLES{n}{k}$ with at least $\ell_k$ copies of $k$;
\item $\mathbf{S}_3$ that contains all strings in $\TUPLES{n}{k}$ with at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$;
\item $\mathbf{S}_4$ that contains all strings in $\TUPLES{n}{k}$ that circularly avoid $\beta \in \{1, 2, \ldots, k-1\}^*$;
\item $\mathbf{S}_5$ that contains all rotations of the lexicographically largest $i$ necklaces in $\TUPLES{n}{k}$;
\item $\mathbf{S}_6$ that contains all strings in $\TUPLES{n}{k}$ that not equal to rotations of some periodic necklaces $\beta \neq k^n$.
\end{enumerate}
\end{comment}

In Sections \ref{sec:examples_first}--\ref{sec:examples_last} we describe interesting members of $\CLASS{n}{k}$, including the sets of strings considered by Moreno \cite{IOPORT.02107234}, Au~\cite{lexi-smallest-aperiodic}, and the authors~\cite{lexi-smallest}.
Figure \ref{fig:FKMRing}  illustrates the lexicographically smallest universal cycles for each example over $\TUPLES{4}{4}$.
When considering periodic and aperiodic strings we prove that $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$; our constructive results from Theorem \ref{thm:main} will still apply in these cases by Corollary~\ref{cor:kn}.

%We also 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{figure}
\includegraphics[width=15cm]{FKMRingCrop}
\caption{
The lexicographically smallest universal cycles for a variety of $4$-ary strings of length four.
Each set $\mathbf{S}$ is in $\CLASS{4}{4}$ (or $\mathbf{S} \cup \{4444\} \in \CLASS{4}{4}$) and hence can be generated by the generalized FKM and greedy algorithms.
The outermost ring is a universal cycle for all strings $\TUPLES{n}{k}$.
The remaining rings from outer-to-inner are for subsets that
(i) have sum at least $5,6,\ldots,15$;
(ii) have at most $2,1$ cyclic descents;
(iii) have at most $2,1$ cyclic decrements;
(iv) have frequency for symbol $k=4$ at least $1,2,3$;
(v) have frequency for symbol $1$ at most $3,2,1$;
(vi) do not have $11$, $22$, $33$ as a cyclic substring;
(vii) are rotations of the largest $50, 30, 10$ necklaces;
(viii) are not rotations of the periodic necklace $1212$, $3434$;
(ix) are in the intersection of the previous two universal cycles (i.e. not rotations of $1212$ or $3434$);
(x) are aperiodic;
(xi) have period in $\{1,4\}$, $\{1,2\}$.
Each universal cycle starts from 12 o'clock and proceeds in clockwise order, with a gap between the examples of each type.
For example, the fourth ring from the outside gives the universal cycle $1114 \, 1123 \, 1124 \, \cdots \, 3444 \, 4$ which contains all strings in $\TUPLES{4}{4}$ with sum at least $7$.
}
\label{fig:FKMRing}
\end{figure}
%=============================


\subsubsection{Minimum Sum} \label{sec:examples_sum} \label{sec:examples_first}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings with sum at least $s$.
This set is closed under rotation since rotation does not change a string's sum.
Also, $\mathbf{S}$ is a $k$-suffix language by Theorem \ref{thm:poset} since replacing any symbol $x < k$ with $k$ increases the sum of the string.
Therefore, $\mathbf{S} \in \CLASS{n}{k}$ by Lemma \ref{lem:CLASS}.
The authors previously considered sets of this type when $n=2$ \cite{lexi-smallest}.
%=============================
\subsubsection{At most $d>0$ cyclic descents} \label{sec:examples_descent}
A \emph{descent} in a string $a_1a_2\cdots a_n$ is a pair of consecutive elements $a_i$, $a_{i+1}$ such that 
$a_i  > a_{i+1}$.   A \emph{cyclic descent} is a descent or the pair $a_n$, $a_1$ where $a_n > a_1$.
 Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings with at most $d$ cyclic descents for some fixed $d > 0$.
This set is clearly closed under rotation.  Also, $\NeckSubset{\mathbf{S}}$ is a $k$-suffix language since replacing any suffix of length $i$ by $k^i$ will increase the number of descents only in the special case where a necklace is of the form $x^n$ for $x<k$.  For these strings the number of descents increases from 0 to 1, which does not violate the upperbound since $d>0$.  Therefore, $\mathbf{S} \in \CLASS{n}{k}$.

%=============================
\subsubsection{At most $d>0$ cyclic decrements} \label{sec:examples_decrement}
A \emph{decrement} in a string $a_1a_2\cdots a_n$ is a pair of consecutive elements $a_i$, $a_{i+1}$ such that 
$a_i  = a_{i+1}+1$.   A \emph{cyclic decrement} is a decrement or the pair $a_n$, $a_1$ where $a_n = a_1+1$.
 Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings with at most $d$ cyclic decrements for some fixed $d > 0$.
This set is clearly closed under rotation.  Also, $\NeckSubset{\mathbf{S}}$ is a $k$-suffix language since replacing any suffix of length $i$ by $k^i$ will only increase the number of decrements in the special case of the necklace $(k{-}1)^n$.  For this string the number of decrements increases from 0 to 1, which does not violate the upperbound since $d>0$. Therefore, $\mathbf{S} \in \CLASS{n}{k}$.

%=============================
\subsubsection{Frequency of $k$} \label{sec:examples_freqk}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings with at least $\ell_k$ copies of $k$.
This set is closed under rotation since rotation does not change a string's symbol frequencies.
Also, $\mathbf{S}$ is a $k$-suffix language by Theorem \ref{thm:poset} since replacing any symbol $x < k$ with $k$ increases the frequency of $k$ in the string.
Therefore, $\mathbf{S} \in \CLASS{n}{k}$ by Lemma \ref{lem:CLASS}.

%=============================
\subsubsection{Frequency of $i < k$} \label{sec:examples_freqi}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings with at most $u_i$ copies of $i < k$.
This set is closed under rotation since rotation does not change a string's symbol frequencies.
Also, $\mathbf{S}$ is a $k$-suffix language by Theorem \ref{thm:poset} since replacing any symbol $x < k$ with $k$ does not increase the frequency of $i$ in the string.
Therefore, $\mathbf{S} \in \CLASS{n}{k}$ by Lemma \ref{lem:CLASS}.

%=============================
\subsubsection{Avoiding a Substring} \label{sec:examples_substring}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings that do not contain $\beta \in \TUPLES{m}{k-1}$, for some $m \geq 1$, as a cyclic substring.
This set is closed under rotation since rotation does not change a string's cyclic substrings.
Also, $\mathbf{S}$ is a $k$-suffix language by Theorem \ref{thm:poset} since replacing any symbol $x < k$ with $k$ cannot create a new cyclic substring in $\TUPLES{m}{k-1}$.
Therefore, $\mathbf{S} \in \CLASS{n}{k}$ by Lemma \ref{lem:CLASS}.

%=============================
\subsubsection{Rotations of Large Necklaces} \label{sec:examples_large}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings that are rotations of the largest $i$ necklaces in $\NECKS{n}{k}$ in lexicographic order.
This set is closed under rotation by its definition.
If $\alpha \in \NeckSubset{\mathbf{S}}$, then replacing its rightmost symbol $x < k$ with $k$ will create another necklace by Lemma \ref{lem:necklaceIdeal}, and this necklace is larger in lexicographic order.
Therefore, $\NeckSubset{\mathbf{S}}$ is a $k$-suffix language.
Hence, $\mathbf{S} \in \CLASS{n}{k}$.
Moreno previously considered sets of this type \cite{IOPORT.02107234}.

%=============================
\subsubsection{Avoiding the Rotations of a Periodic Necklace} \label{sec:examples_periodic}
%\noteComment{This section can be generalized by characterizing the necklaces that are leaves in the k-suffix poset ... see unused/neckLeaves.tex for details.}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the strings that are not rotations of a fixed periodic necklace $\beta \in \NECKS{n}{k}$.
That is, $\mathbf{S} = \TUPLES{n}{k} - \Rotate{\{\beta\}}$.
This set is closed under rotation by its definition.
If $\beta = k^n$, then $\mathbf{S} \cup \{k^n\} = \TUPLES{n}{k} \in \CLASS{n}{k}$.
Otherwise, consider $\beta \neq k^n$.
Let $\alpha x k^j \in \NeckSubset{\mathbf{S}}$ with $x < k$ be an arbitrary necklace in $\mathbf{S}$ that is not equal to $\beta$ (where $j=0$ is possible).
We know that $\alpha k k^j$ is a necklace by Lemma \ref{lem:necklaceIdeal}.
Suppose that $\alpha k k^j = \beta$. 
Since $\beta$ is periodic and $\beta \neq k^n$, we can write $\beta$ as $\beta = (\gamma k^{j+1})^t$ where $\gamma \neq \epsilon$ and $t > 1$. 
Observe that $\alpha x k^j = (\gamma k^{j+1})^{t-1}\gamma xk^j$ is not a necklace since $x < k$, which contradicts $\alpha x k^j$ being a necklace. 
Thus $\alpha k k^j \neq \beta$ and $\NeckSubset{\mathbf{S}}$ is a $k$-suffix language.  
Therefore $\mathbf{S} \in \CLASS{n}{k}$. 

%=============================
\subsubsection{Unions and Intersections} \label{sec:examples_closure}
If $\mathbf{S}_A$ and $\mathbf{S}_B$ are closed under rotation, then both $\mathbf{S}_A \cup \mathbf{S}_B$ and $\mathbf{S}_A \cap \mathbf{S}_B$ are closed under rotation.
Thus, Corollary \ref{cor:closure} gives the following.

\begin{lemma} \label{lem:closureCLASS}
If $\mathbf{S}_A, \mathbf{S}_B \in \CLASS{n}{k}$, then $\mathbf{S}_A \cup \mathbf{S}_B \in \CLASS{n}{k}$ and $\mathbf{S}_A \cap \mathbf{S}_B \in \CLASS{n}{k}$.
\end{lemma}

Lemma \ref{lem:closureCLASS} allows us to combine the previous results in interesting ways, as illustrated in Sections \ref{sec:examples_aperiodic} and \ref{sec:examples_periods}.

\subsubsection{Aperiodic Strings} \label{sec:examples_aperiodic}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ contain the aperiodic strings.
Let the periodic necklaces in $\NECKS{n}{k}$ be $\beta_1, \beta_2, \ldots, \beta_t$.
Notice that 
\begin{align*}
\mathbf{S} 
&= \phantom{\big(} \TUPLES{n}{k} - \Rotate{\{\beta_1, \beta_2, \ldots, \beta_t\}} \\
%&= \TUPLES{n}{k} - \big(\Rotate{\{\beta_1\}} \cup \Rotate{\{\beta_2\}} \cup \cdots \cup \Rotate{\{\beta_t\}} \big) \\
&= \big(\TUPLES{n}{k} - \Rotate{\{\beta_1\}}\big) \cap \big(\TUPLES{n}{k} - \Rotate{\{\beta_2\}}\big) \cap \cdots \cap \big(\TUPLES{n}{k} - \Rotate{\{\beta_t\}}\big).
\end{align*}
Therefore, $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$ by Section \ref{sec:examples_periodic} and Lemma \ref{lem:closureCLASS}.
Au previously considered sets of this type \cite{lexi-smallest-aperiodic}.

%=============================
\subsubsection{Strings with Given Periods} \label{sec:examples_periods} \label{sec:examples_last}
Let $\mathbf{S} \subseteq \TUPLES{n}{k}$ be the strings with period in $P \subseteq \{1,2,\ldots,n\}$ with $n \in P$.
We can prove that $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$ by using the same approach as in Section \ref{sec:examples_aperiodic}.
More specifically, replace $\beta_1, \beta_2, \ldots, \beta_t$ by the necklaces whose period is not in $P$.
This provides a nice generalization of Au's result \cite{lexi-smallest-aperiodic}.

%A string is a \emph{prenecklace} if it is the prefix of some necklace. 
%Let $\mathbf{S}\subseteq \TUPLES{n}{k}$ be a set that is closed under rotation, and $\mathbf{P}$ be the set of prenecklaces that are prefixes of necklaces in $\mathbf{S}$ with $\mathbf{S} \cap \NECKS{n}{k}$ $k$-suffix language.   





