% !TEX root = kFKM.tex
 \label{sec:definitions_kSuffix}
 
%In this section we investigate our second closure property from Theorem~\ref{thm:main} in more detail, including special consideration of necklaces.
In this section we investigate our second closure property from Theorem~\ref{thm:main} in more detail.
First we define the $k$-suffix property and prove that set of all necklaces satisfies it.
Then we formulate $k$-suffix languages as partially ordered sets, which provides helpful visualizations and closure properties at the end of the section.

%\subsection{$k$-Suffix Definitions} \label{sec:definitions_kSuffix}

%The following definition isolates our second closure property from Theorem~\ref{thm:1}.

\begin{definition} \label{def:kSuffixLanguage}
A \emph{$k$-suffix language} $\mathbf{S}$ is a subset of $\TUPLES{n}{k}$ that satisfies the following closure property: 
%\begin{equation} \label{eq:kSuffixLanguage}
\[
\text{If } a_1  a_2  \cdots  a_{n} \in \mathbf{S} \text{ then } a_1  a_2  \cdots  a_{n-i}  k^{i}  \in \mathbf{S} \text{ for all } 1 \leq i \leq n.
\]
%\end{equation} 
\end{definition}


As an example, let $\NECKS{n}{k}$ denote the set of necklaces in $\TUPLES{n}{k}$.  It is straightforward to observe that necklaces are a $k$-suffix language.
%This fact is illustrated by Figure~\ref{fig:PosetNecks} since the highlighted ideals are $\NECKS{4}{2}$ and $\NECKS{2}{3}$.

\begin{lemma} \label{lem:necklaceIdeal}
The set of necklaces $\NECKS{n}{k}$ is a $k$-suffix language.
\end{lemma}
\begin{proof}
Let $a_1 a_2 \cdots a_n = a_1 a_2 \cdots a_{n-j} k^{j} \in \NECKS{n}{k}$ where  $j \geq 0$.
By the definition of a necklace it is easy to see that  $a_1 a_2 \cdots a_{n-j-1} k k^{j} \in \NECKS{n}{k}$.  Thus it follows that  $a_1a_2\cdots a_{n-i}k^i \in \NECKS{n}{k}$
for all $1 \leq i \leq n$.
\end{proof}


%For example, \eqref{eq:sum10} is a $k$-suffix language.
%Condition \eqref{eq:kSuffixLanguage} provides closure under replacing any suffix of length $i$ by $k^i$.
Note that this definition of a $k$-suffix language implies closure under replacing any suffix of length $i$ by $k^i$.
Equivalently, $k$-suffix languages can be defined as closed under replacing the rightmost value that is less than $k$ by $k$.
We next formulate this idea using a partially ordered set over $\TUPLES{n}{k}$.
Consider the following definition,
\begin{equation*}
\tau_k(\alpha) =
\begin{cases}
k^n & \text{ if $\alpha = k^n$;} \\
\beta  k  k^j & \text{ if $\alpha = \beta x k^j$ for some $x < k$.}
\end{cases}
%\alpha  k  k^j \prec \alpha  x  k^j \text{ for all } x < k.
\end{equation*}
In other words, $k^n$ is \emph{terminal}, and otherwise $\tau(\alpha)$ is obtained by replacing the rightmost value in $\alpha$ that is less than $k$ with $k$.
When the context is clear we use $\tau$ instead of $\tau_k$.
For example, when $k=3$,
\begin{equation*}
\tau(1122) = 1123 \text{ and } \tau(2313) = 2333 \text{ and } \tau(3333) = 3333.
\end{equation*}
This provides our cover relation, and our partial order $\prec_k$ is the non-reflexive transitive closure of $\tau_k$.
Again we use $\prec$ instead of $\prec_k$ when the context allows.
For example, when $k=3$,
\begin{equation*}
1123 \prec 1122 \text{ and } 1333 \prec 1122 \text{ whereas } 2313 \nprec 2113 \text{ and } 2113 \nprec 2113.
\end{equation*}
Our partially ordered set is formally defined below.

\begin{definition} \label{def:kSuffixPoset}
The \emph{$k$-suffix poset} $\POSET{n}{k}$ has ground set $\TUPLES{n}{k}$ and partial order $\prec_k$.
\end{definition}

%To illustrate \eqref{eq:kSuffixPoset} we note that in $\POSET{4}{3}$,
Figure~\ref{fig:PosetNecks} illustrates the Hasse diagram of $\POSET{4}{2}$ and $\POSET{2}{3}$, in which each cover relation $\beta = \tau(\alpha)$ is shown as an edge from $\alpha$ down to $\beta$.
It is easy to see that $\POSET{n}{k}$ is a tree poset with unique minimum element $k^n$.

\begin{figure} 
\centering
\begin{tabular}{|@{\;}c@{\;}|@{\;}c@{\;}|} \hline
\includegraphics[scale=0.13]{Poset42Necks} &
\includegraphics[scale=0.13]{Poset23Necks} \\ \hline 
\end{tabular}
\caption{The Hasse diagram of $\POSET{4}{2}$ and $\POSET{2}{3}$ respectively.
In both cases the necklaces form the ideal in bold.}
\label{fig:PosetNecks}
\end{figure}

An \emph{ideal} (also known as a \emph{lower set}) of $\POSET{n}{k}$ is a subset $\mathbf{I} \subseteq \POSET{n}{k}$ such that $x \in \mathbf{I}$ and $y \prec x$ implies $y \in \mathbf{I}$.
Figure~\ref{fig:PosetNecks} illustrates an ideal of necklaces in both of its posets.
The following theorem proves that every $k$-suffix language can be visualized in this way.

\begin{theorem} \label{thm:poset}
A set $\mathbf{S} \subseteq \TUPLES{n}{k}$ is a $k$-suffix language if and only if $\mathbf{S}$ is an ideal of $\POSET{n}{k}$.
\end{theorem}
\begin{proof}
Suppose $\mathbf{S}$ is a $k$-suffix language.
If $s \in \mathbf{S}$ and $s \neq k^n$, then $s = \alpha  x  k^j$ for some $x < k$.
By the definition of $k$-suffix language, $\alpha  k  k^j \in \mathbf{S}$.
Therefore, $\tau_k(s) \in \mathbf{S}$, and thus $\mathbf{S}$ is an ideal of $\POSET{n}{k}$.
The other direction is similar.
\end{proof}

Ideals of a given poset are closed under union and intersection, so Theorem \ref{thm:poset} immediately gives the following corollary.

\begin{corollary} \label{cor:closure}
If $\mathbf{S}_A, \mathbf{S}_B \subseteq \TUPLES{n}{k}$ are \emph{$k$-suffix languages}, then $\mathbf{S}_A \cup \mathbf{S}_B$ and $\mathbf{S}_A \cap \mathbf{S}_B$ are also $k$-suffix languages.
\end{corollary}


%\subsection{Necklaces} \label{sec:definitions_necklaces}



\begin{comment}

If $a_1 a_2 \cdots a_{n-j-1} k k^{n-j} \notin \NECKS{n}{k}$, then there exists an $i$ such that 
\begin{equation*} %\label{eq:contradict1}
a_i \, a_{i+1} \, \cdots \, a_{n-j-1} \, k \, k^{n-j} \, a_1 \, a_2 \, \cdots \, a_{i-1} \, < \, a_{1} \, a_{2} \, \cdots \, a_{n-j-1} \, k \, k^{j} \text{ and } i \leq n{-}j{-}1.
\end{equation*}
But $\alpha$ is a necklace so we know that 
\begin{equation*}
a_i \, a_{i+1} \, \cdots \, a_{n-j-1} \, x \, \geq \, a_{1} \, a_{2} \, \cdots \, a_{n-j-i+1}.
\end{equation*}
Therefore, 
\begin{equation*} \label{eq:contradict2}
a_i \, a_{i+1} \, \cdots \, a_{n-j-1} \, k \, > \, a_{1} \, a_{2} \, \cdots \, a_{n-j-i+1}.
\end{equation*}
%But \eqref{eq:contradict2} contradicts \eqref{eq:contradict1}.
%Therefore, the value of $i$ considered in \eqref{eq:contradict1} does not exist.
But this inequality contradicts the first inequality.
Hence, $\NECKS{n}{k}$ is an ideal. % of $\POSET{n}{k}$.


\end{proof}

\end{comment}


%This lemma will be useful in Section \ref{sec:examples} when we give examples of universal cycles that are created by our main results.



