\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\usepackage{verbatim}
%\numberwithin{equation}{section}

%%%Document Configuration
\pagestyle{headings}
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in 
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar     
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{ex}[thm]{Example}
\newtheorem{exer}[thm]{Exercise}
\newtheorem{fact}[thm]{Fact}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{hw}[section]{}
%\newtheorem{hw}[section]{HW}
\newtheorem{dfn}{Definition}[section]
%%%

%%%Bibliography Configuration
\bibliographystyle{plain}
%%%

%%%semantic definitions
\DeclareMathOperator*{\Aut}{Aut}
\DeclareMathOperator*{\Dom}{Dom}
\DeclareMathOperator*{\Mod}{Mod}
\DeclareMathOperator*{\Th}{Th}
\DeclareMathOperator*{\tp}{tp}
\renewcommand{\div}{\mid}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\Acl}[1]{\obar{#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\caseif}{\Rightarrow}
\newcommand{\caseonlyif}{\Leftarrow}
\newcommand{\cantprove}{\nvdash}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\compat}{\uparrow}
\newcommand{\ncompat}{\not\uparrow}
\newcommand{\field}{\mathbb{F}}
\newcommand{\minus}{\setminus}
\newcommand{\power}[1]{{\mathcal{P}}({#1})}
\newcommand{\nonnegative}{\mathbb{N}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\intersect}{\cap}
\newcommand{\isomorphic}{\simeq}
\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\proves}{\vdash}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\union}{\cup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%long macros
%the #2th residual partial word modulo #3 of #1
%\newcommand{\rpw}[3]{{#1\left[#2,#3\right]}}
\newcommand{\rpw}[3]{
#1{\!\scriptsize\left[\!\!\!
 \begin{array}{c}
 #2\\
 #3
 \end{array}
\!\!\!\right]}
\!\!\,
}
%%%

%%%local definitions
\newcommand{\eleq}{\equiv}
\newcommand{\elleq}{\preccurlyeq}
\newcommand{\floor}[1]{{\left\lfloor#1\right\rfloor}}
\newcommand{\h}{\lozenge}
\newcommand{\lang}[1]{{\mathcal{#1}}}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\mathscr}[1]{{\mathcal{#1}}}
\newcommand{\st}[1]{{\mathcal{#1}}}
\newcommand{\structure}[1]{{\mathcal{#1}}}
\newcommand{\struct}[1]{\left\langle#1\right\rangle}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\WFF}{well-formed formula}
\newcommand{\0}{\textbf{0}}
\newcommand{\suc}{\textbf{S}}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\NNN}{\mathfrak{N}}
\newcommand{\E}{\textbf{E}}
\newcommand{\Cn}{\textrm{Cn}}
\newcommand{\res}{\upharpoonright}
%%%

\begin{document}

\title{A Relation on Partial Words}
\author{Dakota Blair}
\date{March 4, 2011}
\maketitle

\subsection*{Acknowledgements}
This is joint work with R. V. Lewis, F. Blanchet-Sadri.
This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020.

\section{Introduction}
Let $\natural$ denote the natural numbers,
and associate an element $n \in \natural$
with its corresponding ordinal number.
%Let $\omega$ be the ordinal number of $\natural$.
A \emph{partial function} from $X$ to $Y$ is
a function $f : X' \to Y$ such that $X' \subset X$
is the \emph{domain} of $f$.
Let the set of partial functions from $X$ to $Y$ be written as $Y^{(X)}$.
Denote the domain of $f \in Y^{(X)}$ as $D(f)$
and the \emph{set of holes of $f$} as $H(f) = X \minus D(f)$.
Given $n, m \in \natural$ let 
$k = n \pmod m$ be modular reduction of $n$ modulo $m$,
that is, $0 \leq k < m$ and $k \equiv n \pmod m$.
%The convention that 

\begin{dfn}[Partial Words]
A \textbf{partial word} $u$ of length $|u| = n$
on an alphabet $A$ is an element of $A^{(n)}$.
\end{dfn}

With this definition, $A^* = \union_{n \in \natural} A^{(n)}$
forms a monoid under concatenation
with identity element $\epsilon$, the empty word.

\begin{ex}
The partial word $c \h b$ is an element of $\{a, b, c\}^{(3)}$.
\end{ex}

\begin{dfn}[Containment]
A partial word $u$ is said to be \textbf{contained} in $v$,
written $u \subset v$,
if $|u| = |v|, D(u) \subset D(v)$ and $u(i) = v(i)$ for all $i \in D(u)$.
\end{dfn}

\begin{ex}
The partial word $c \h b$ is contained in both $cab$ and $cub$.
\end{ex}

\begin{dfn}[Compatibility]
A partial word $u$ is \textbf{compatible} with $v$, written $u \compat v$,
if there exists a partial word $w$ such that $u \subset w, v \subset w$.
\end{dfn}

\begin{ex}
Extending the previous example, $c \h b \compat cab$ and $c \h b \compat cub$,
but $cab \ncompat cub$.
Therefore the $\compat$ relation is
reflexive and symmetric, but not transitive.
Another example is $a\h b b c \compat aab \h c$.
\end{ex}

\begin{dfn}[Periodic]
A partial word $u$ is \textbf{$p$-periodic}
if $i \equiv j \pmod p$ and $i, j \in D(u)$ implies $u(i) = u(j)$.
\end{dfn}

\begin{ex}
The word $abcabc$ is $3$-periodic, and the partial word $abab \h b$
is $2$-periodic.
\end{ex}

\begin{dfn}[Residual Partial Words]
For a partial word $u$ and $i, p \in \natural$,
let $i'$ be $i' = i \pmod p$
and $k \in \natural$ be the greatest integer such that $i' + kp < |u|$.
Then the \textbf{$i$th residual partial word modulo $p$ of $u$},
denoted $\rpw{u}{i}{p}$, is defined to be
\[
\rpw{u}{i}{p}
= \prod_{j=0}^k u(i' + jp) = u(i') u(i'+p) u(i'+2p) \cdots u(i'+ kp).
\]
%Note that each such word has length $\floor{|u|/|p|}$
\end{dfn}

\begin{ex}
Let $u = (prime)^5$. Then $\rpw{u}{0}{6} = prime$.
If $v = (a\h b)^3$ then $\rpw{v}{1}{3} = \h\h\h$.
\end{ex}

\section{The relation $u^m \compat v^n$ on partial words}

\begin{lem}
\label{lem1}
Let $u$ and $v$ be partial words, such that
for $m, n \in \natural$ with $\gcd(m,n)=1$
$u^m \compat v^n$ and $p = |u|/n = |v|/m$.
If there exists an $i$ such that $0 \leq i < p$
and $\rpw{u}{i}{p}$ is not $1$-periodic
then $D\left(\rpw{v}{i}{p}\right)$ is empty.
\end{lem}

\begin{comment}
\begin{proof}
\end{proof}
\end{comment}

\begin{lem}
\label{lem2}
If $u$ is a partial word, $i, m, p \in \natural$
and $0 \leq i \leq p$ 
then
\begin{align*}
\rpw{u^m}{i}{p}
&= \rpw{u}{i}{p}\rpw{u}{(i-|u|)}{p}\rpw{u}{(i-2|u|)}{p}
   \cdots \rpw{u}{(i-(m-1)|u|)}{p}\\
&= \prod_{j=0}^{m-1}\rpw{u}{i-j|u|}{p}
\end{align*}
\end{lem}

\begin{dfn}[Good Pair]
A pair of partial words $(u,v)$ is a \textbf{good pair}
if for all $i \in H(u)$ the word $\rpw{v^n}{i}{|u|}$ is $1$-periodic
and for all $i \in H(v)$ the word $\rpw{u^m}{i}{|v|}$ is $1$-periodic.
\end{dfn}

\begin{ex}
The partial words $a \h b$ and $acbadb$ do not form a good pair.
\end{ex}

\begin{thm}
If $(u,v)$ is a good pair of partial words, $m$ and $n$ are positive integers
such that $u^m \compat v^n$ with $\gcd(m,n) = 1$
then
there exists a partial word $z$ such that
$u \subset z^n$ and $v \subset z^m$.
\end{thm}

\begin{proof}
Since $\gcd(m,n) = 1$,
there exists $p$ such that $|u|/n = |v|/m = p$.
Now assume there is an integer $i$ such that $0 \leq i < p$ and
$\rpw{u}{i}{p}$ is not $1$-periodic.
By Lemma \ref{lem1}, $i+jp \pmod{|v|} \in H(v)$
for all $j$ such that $0 \leq j < m$.
Then the assumption that $(u, v)$ is a good pair
implies $w = \rpw{u^m}{i+jp}{|v|}$ is $1$-periodic
for all $j$, and therefore $w \subset a^n$ for some letter $a$.
Note also that $|u|=np$ implies $|w| = |u| = n$.
To show
$\rpw{u}{i}{p}$ is a permutation of $w$
will be sufficient to complete the proof.
%\begin{comment}
By Lemma \ref{lem2}
\begin{align*}
w = \rpw{u^m}{i+jp}{mp}
&=\prod_{k=0}^{m-1}\rpw{u}{i+(j-k|u|)p}{mp}\\
&=\rpw{u}{i+jp}{mp}\rpw{u}{i+(j-|u|)p}{mp}\rpw{u}{i+(j-2|u|)p}{mp}
\cdots \rpw{u}{i+(j-(m-1)|u|)p}{mp}.
\end{align*}
Note that $i+jp-k|u| = i+(j-kn)p$ and since $\gcd(m, n) = 1$
\[
\{{j-kn \hspace{-1pc}\pmod m} \big| 0 \leq k < m\} = \{0, 1, \ldots, m-1\}.
\]
Therefore define $j_k = j-kn \pmod m$, so
\[
w
= \rpw{u^m}{i+jp}{mp} 
= \prod_{k=0}^{m-1} \rpw{u}{i+j_k p}{mp}
= \rpw{u}{i+j_0 p}{mp}
\rpw{u}{i+j_1 p}{mp}
\cdots
\rpw{u}{i+j_{m-1} p}{mp}.
\]
\begin{comment}
\begin{align*}
w = \rpw{u^m}{i+jp}{mp} &= 
\rpw{u}{i+j_0 p}{mp}
\rpw{u}{i+j_1 p}{mp}
\cdots
\rpw{u}{i+j_{m-1} p}{mp}\\
&= \prod_{k=0}^{m-1} \rpw{u}{i+j_k p}{mp}.
\end{align*}
\end{comment}
Since $w$ is $1$-periodic,
there is a letter $a$ such that for $0 \leq k < m$ and some $m_k \in \natural$
\[
\rpw{u}{i+j_k p}{mp} \subset a^{m_k}.
\]
Now observe that
\[
\left\{k + lm \Big| 0 \leq k < m, 0 \leq l < n - k/m - i/mp\right\}
= \{0,1,\ldots,n-1\}
\]
where the condition on $l$ comes from the requirement that
the sum $i + kp + lmp$ be less than $|u| = np$.
\begin{comment}
|u^m| = m|u| = nmp

i + kp + lmp < np

{k+lm | 0<= k < m, i + (k+lm)p < nmp} = {0,1,...,n-1}

{k+lm | 0<= k < m, 0 \leq l < n - k/m - i/mp}

i          + lmp = i + gmp
i +      p + lmp = i + (1+lm)p
i +     2p + lmp = i + (2+lm)p
i +     3p + lmp = i + (3+lm)p
...
i +     kp + lmp = i + (k+lm)p
...
i + (m-1)p + lmp = i + ((l+1)m-1)p
\end{comment}
Therefore the partial word $w$ is a permutation of $\rpw{u}{i}{p}$.
%\end{comment}
That is, if $\sigma \in S_n$, the symmetric group on $n$,
\[
w = \rpw{u^m}{i+jp}{mp}
= \prod_{k=0}^{m-1} \rpw{u}{i+j_k p}{mp}
= \prod_{h=0}^{n-1}u(i + \sigma(h)p) \subset a^n.
\]
But $w$ is $1$-periodic, and therefore so is $\rpw{u}{i}{p}$
which contradicts our choice of $i$.
Then $\rpw{u}{i}{p}$ is $1$-periodic for all $i$,
so $u$ is $p$-periodic.
Thus there is a partial word $z_u$ of length $p$ such that $u\subset z_u^n$.
Repeating the argument for $v$ yields
a partial word $z_v$ of length $p$ such that $v\subset z_v^m$.
Then $u^m \compat y^n$ implies that $z_u^{mn} \compat z_v^{mn}$
and therefore $z_u \compat z_v$.
Finally $z = z_u \vee z_y$ is a partial word such that
$u \subset z^n$ and $v \subset z^m$.
\end{proof}

\end{document}
