\documentclass[12pt]{article}
\usepackage{e-jc}
% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
% we recommend the graphicx package for importing figures
\usepackage{graphicx}
% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem*{conjecture-nonum}{Conjecture}
\theoremstyle{definition}
\newtheorem*{question}{Question}
\newtheorem*{problem}{Problem}
\title{Words with many palindrome pair factors}
\author{Adam Borchert and Narad Rampersad \thanks{The first author is
supported by an NSERC USRA, the second by an NSERC Discovery
Grant.}\\
\small Department of Mathematics and Statistics \\[-0.8ex]
\small University of Winnipeg \\[-0.8ex]
\small 515 Portage Avenue \\[-0.8ex]
\small Winnipeg, Manitoba R3B 2E9 (Canada)\\
\small\tt {adamdborchert@gmail.com, n.rampersad@uwinnipeg.ca}}
\date{\dateline{???}{???}\\
\small Mathematics Subject Classifications: 68R15}
\begin{document}
\maketitle
\begin{abstract}
Motivated by a conjecture of Frid, Puzynina, and Zamboni,
we investigate infinite words with the property that for infinitely many $n$,
every length-$n$ factor is a product of two palindromes. We show that
every Sturmian word has this property, but this does not characterize
the class of Sturmian words. We also show that the Thue--Morse word
does not have this property. We investigate finite words with the
maximal number of distinct palindrome pair factors and characterize
the binary words that are not palindrome pairs but have the property
that every proper factor is a palindrome pair.
\end{abstract}
\section{Introduction}
The \emph{palindromic length} of a word $x$ is the least $\ell$ such
that $x = p_1p_2\cdots p_\ell$, where each $p_i$ is a palindrome (we
consider the empty word a palindrome). Frid, Puzynina, and Zamboni
\cite{FPZ13} made the following, remarkable conjecture:
\begin{conjecture-nonum}[Frid--Puzynina--Zamboni]
Let ${\bf w}$ be an infinite word. If there exists $k$ such that
every factor of $w$ has palindromic length at most $k$, then ${\bf w}$ is
ultimately periodic.
\end{conjecture-nonum}
In this paper we focus on words with palindromic length at most
$2$: these are called \emph{palindrome pairs} and have been studied
before \cite{GSS15,HM15,Kem82}. Assuming that the
Frid--Puzynina--Zamboni Conjecture is true, there is no aperiodic word
with the property that all of its factors are palindrome pairs. We
therefore investigate the following question, with the hope that it
will give some insight into the conjecture.
\begin{quotation}
Are there aperiodic words {\bf w} with the property ({\bf PP}) that for
\emph{infinitely many $n$}, every length-$n$ factor of ${\bf w}$ is a
palindrome pair?
\end{quotation}
As we will see, all Sturmian words have property {\bf PP}, but this does
not characterize the Sturmian words: there are other words with this
property as well. We also show that the Thue--Morse word does not have
property {\bf PP}. We then look at the analogue of (finite) \emph{rich words}
for palindrome pairs, rather than palindromes. Finally, we
characterize the finite binary words that are not palindrome pairs, but have
the property that each of their proper factors is a palindrome pair.
\section{Palindrome pairs in Sturmian words}\label{sturmian}
In this section we show that every Sturmian word ${\bf s}$ has
property {\bf PP} and we characterize the lengths $n$ for which every
length-$n$ factor of ${\bf s}$ is a palindrome pair. We begin with
some preliminaries concerning Sturmian words.
Let $\alpha$ be an irrational real number (fixed for the remainder of
this section) with $0<\alpha<1$ and let $\alpha$ have the continued
fraction expansion $\alpha = [0; a_1 + 1, a_2, a_3, \ldots]$. We
define the following sequence of words:
\[
s_0 = 1, \quad s_1 = 0, \quad s_n = s_{n-1}^{a_{n-1}} s_{n-2} \text{
for } n \geq 2.
\]
Since $s_n$ is a prefix of $s_{n+1}$ for all $n\geq 1$, this sequence
converges to an infinite word ${\bf c}_\alpha$ called the
\emph{characteristic (or standard) Sturmian word} with slope $\alpha$.
An infinite word ${\bf s}$ is a \emph{Sturmian word} with slope
$\alpha$ if it has the same set of factors as ${\bf c}_\alpha$. Since
we are only concerned with the language of factors of ${\bf s}$, we
will assume without loss of generality that ${\bf s} = {\bf c}_\alpha$.
There are many equivalent definitions of ``Sturmian word''. For
instance, another definition is the following: An infinite word
is Sturmian if it has $n+1$ factors of length $n$ for every $n \geq
0$. For more details on Sturmian words see \cite[Chapter~2]{Lot02}.
Recall that words $x$ and $y$ are \emph{conjugates} if $x=uv$ and
$y=vu$ for some words $u$ and $v$.
\begin{lemma}
\label{pp_conj}
Any conjugate of a palindrome pair is a palindrome pair.
\end{lemma}
\begin{proof}
Let $A_0 B_0$ be a palindrome pair where $A_0 = a_1 a_2 \cdots a_r$ and $B_0 = b_1 b_2 \cdots b_s$ are palindromes. As the result is trivial for the empty word, we may assume without loss of generality that $r \geq 1$ and $s \geq 0$. If $r = 1$, note that $B_0 a_1$ is a palindrome pair. Assume that $r\geq2$. Then, since $A_1 = a_2 a_3\cdots a_{r-1}$ and $B_1 = a_r b_1 b_2 \cdots b_s a_1$ are palindromes it follows that $A_1 B_1$ is a palindrome pair. The result follows on repeated application of this argument.
\end{proof}
\begin{lemma} \cite{F06}
\label{all_pal_pref}
A palindrome $p$ is a palindromic prefix of ${\bf s}$ if and
only if one of the following hold:
\begin{itemize}
\item $p$ is a factor of $s_1^{a_1}$.
\item For either $u = p01$ or $u = p10$ we
have $u = s_{n-1}^ks_{n-2}$ for some $n \geq
2$ and some $k$ such that $1 \leq k \leq a_{n-1}$.
\end{itemize}
\end{lemma}
\begin{lemma} \cite{dM94}
\label{pal_pairs}
For every $n \geq 2$ and every $k$ such that $1 \leq k
\leq a_{n-1}$, $s_{n-1}^ks_{n-2}$ is a palindrome
pair.
\end{lemma}
If $w$ is a word (finite or infinite), the notation $w[i:j]$ indicates
the factor of $w$ beginning at position $i$ and ending at position $j-1$
in $w$. Unless otherwise stated, we assume that positions are indexed
starting with $0$.
\begin{lemma}
\label{left_special}
Let $w$ be a left special factor of ${\bf s}$ such that neither $w[0:|w|-1]$ nor $w$ is a palindrome. The words $1w$ and $0w$ are not both palindrome pairs.
\end{lemma}
\begin{proof}
Let $w$ be such a factor. Since $w$ is left special,
it is well known that $w$ occurs as a prefix of ${\bf
s}$. Assume without loss of generality that $1w$ is
a palindrome pair. Write $1w = AB$ for palindromes $A$
and $B$. Based on our hypotheses on $w$, it follows
from Lemma \ref{all_pal_pref} that $|A| \ne 0,
1$. Hence, we may write $A = 1P_11$ for a palindrome
$P_1$. Since $P_1$ is a palindromic prefix of ${\bf
s}$ it then follows from Lemma \ref{all_pal_pref}
that $B$ has prefix $0$. Then, since $B$ is a
palindrome it follows that $B$ (and hence, $w$) has
suffix $0$. If $0w$ were a palindrome pair it would
follow by a similar argument that $w = 0p_201\ldots 1$
and thus $w$ has suffix $1$, which is impossible.
\end{proof}
\begin{lemma}
\label{exc_non_pp}
Let $u = s_{n-1}^ks_{n-2}$ for some $n \geq 4$ and
some $k$ such that $1 \leq k \leq a_{n-1}$, where
$|u| \geq 3 a_1 + 6$. There is a factor of ${\bf s}$
of length $|u| - 1$ which is not a palindrome pair.
\end{lemma}
\begin{proof}
Let $a = 0^{a_1}$ and $b = 0^{a_1 + 1}$. Note that
these are the only two maximal blocks of zeros
occurring in ${\bf s}$. Let $w$ be the right special
factor of ${\bf s}$ of length $|u| - 2$. Note that
since $w0$ is a factor of ${\bf s}$, and since $b$ is
maximal, that $w$ cannot have suffix $b$. Thus $w$ is
a palindromic prefix of ${\bf s}$ with suffix (and
hence, prefix) $a$. We consider the word $v =
0^{-1}w01$. Note that $|v| = |u| - 1$. It follows from
the facts that $w$ is right special and that $b$ is
the maximal block of zeros in ${\bf s}$ that $v$
occurs in ${\bf s}$. If $v$ is not a palindrome pair we are done. Assume otherwise, and write $v = P_1 P_2$ for palindromes $P_1$ and $P_2$.
Suppose that $P_1 \ne 0^{-1} a$. It then follows that
\[u = \overbrace{\ldots 10^{-1}a}^{P_1} \overbrace{1 \ldots}^{P_2}\]
which contradicts that $a$ is the shortest maximal block of zeros in ${\bf s}$. Hence, $P_1 = 0^{-1}a$.
Thus we have $w01 = aP_2 = a1 \ldots 1b1$. Since $P_2$
is a palindrome it follows that $P_2 = 1b1\ldots
1b1$. Then, since $w$ is a palindrome it follows that
$w01 = aP_2 = a1b1\ldots 1b1b1$. Continuing in this
manner we obtain that $P_2 = 1(b1)^k$ for some integer
$k\geq0$. We now consider two cases depending on which
of $w0$ or $w1$ occurs as a prefix of ${\bf s}$.
\textbf{Case 1.} Assume that $w0$ is a prefix of ${\bf
s}$. Observe that $v$ occurs as a suffix of $s_n$,
which itself is a prefix of ${\bf s}$. Let ${\bf
s}[i:j]$ be this occurrence of $v$. Since the prefix
$s_n$ is either followed by $s_{n-1}$, or $s_n$ (which
has prefix $s_{n-1}$) and since $n\geq 4$, we then have either
\[{\bf s} = \overbrace{a1b1b\ldots\underbrace{\ldots
b1}_{{\bf s}[i:j]} }^{s_n} \overbrace{a1b \ldots}^ {s_{n-1}} \ldots\]
or
\[{\bf s} = \overbrace{a1b1b\ldots\underbrace{\ldots
b1}_{{\bf s}[i:j]} }^{s_4} \overbrace{a10}^ {s_{3}} \overbrace{a1} ^{s_{2}} \ldots\]
depending on the length of $s_{n-1}$.
Now, let $x = {\bf s}[i+2|b|:j+2|b|]$. Note that $|x|
= |v| = |u| - 1$. Suppose for contradiction that $x$
is a palindrome pair. Note that $x$ has prefix $b$ and
suffix $1a1b$ where $1a1$ is unioccurrent in
$x$. Since $x$ is a palindrome pair it then follows
that $x$ is a palindrome, and hence that $x =
b1a1b$. Thus, $|u| = 3|b| + 2 < 3 a_1 + 6$, contrary
to our hypothesis.
\textbf{Case 2.} We now assume that $w1$ is a prefix
of ${\bf s}$. Note that $w1 = a1(b1)^k a1$ for some $k
> 0$, and that $w10 = u$. As before, $u$ is either
followed by $s_{n-1}$, or $s_n$ (which has prefix
$s_{n-1}$). Thus, \[{\bf s} = \overbrace{ \underbrace {a1b1b\ldots b1a} _ {w}10}^{u} \overbrace{a1\ldots}^{s_{n-1}}\ldots\]
Set $x = {\bf s}[|b|:|u| + |a|]$. Again, note that $|x| = |u| - 1$. We suppose that $x$ is a palindrome pair and apply the same argument to $x$ as was done in the previous case to obtain $x = b1a1b$ and thus that $|u| < 3 a_1 + 6$, a contradiction. This completes the proof.
\end{proof}
\begin{lemma}
\label{stur_non_pps}
If $n \ne |s_{m-1}^ks_{m-2}|$ for any $m \geq 2$
and any $k$ such that $1 \leq k \leq a_{m-1}$, and
$n \geq 3 a_1 + 6$, then ${\bf s}$ has at most $n-1$
palindrome pair factors of length $n$.
\end{lemma}
\begin{proof}
This follows from Lemmas \ref{left_special} and
\ref{exc_non_pp}, the fact that ${\bf s}$ has
$n+1$ factors of length $n$, and the fact that the factor set of
${\bf s}$ is closed under reversal.
\end{proof}
\begin{theorem}
\label{sturm_pals}
Let ${\bf s}$ be a Sturmian word and let $n
\geq 3 a_1 + 6$ be a positive integer. Every factor of
${\bf s}$ of length $n$ is a palindrome pair if and
only if $n = |s_{m-1} ^ k s_{m-2}|$ for some $m \geq
4$ and some $k$ such that $1 \leq k \leq a_{m - 1}$.
\end{theorem}
\begin{proof}
Let $n$ be such an integer. It is known that the $n+1$
factors of length $n$ in ${\bf s}$ are the conjugates
of $s_{m-1} ^ k s_{m-2}$, as well as a palindromic
singular factor \cite{Mel99}. It follows from Lemma
\ref{pal_pairs} that $s_{m-1} ^ k s_{m-2}$ is a
palindrome pair. It then follows from Lemma
\ref{pp_conj} that all factors of length $n$ are
palindrome pairs. The converse follows immediately
from Lemma \ref{stur_non_pps}.
\end{proof}
\begin{corollary}
Every Sturmian word has property {\bf PP}.
\end{corollary}
Property {\bf PP} does not characterize Sturmian words. Consider the
following construction. For $i = 1,2,\ldots$ let $w_i$ be an
arbitrary palindrome of some length $t_i$ over $\{0,1\}$ and write
$w_i = w_{i,1}w_{i,2}\cdots w_{i,t_i}$. We define a sequence of palindromes
$p_1,p_2,\ldots$ as follows:
\begin{align*}
p_1 &= 0 \\
p_2 &= p_1\, w_{1,1}\, p_1\, w_{1,2} \cdots p_1\, w_{1,t_1}\, p_1 \\
p_3 &= p_2\, w_{2,1}\, p_2\, w_{2,2} \cdots p_2\, w_{2,t_2}\, p_2 \\
&\vdots
\end{align*}
Note that $p_i$ is a prefix of $p_{i+1}$ for all $i$, so we have a
limiting infinite word ${\bf p}$.
\begin{proposition}\label{shuffling_pals}
For each $i \geq 1$, every factor of ${\bf p}$ of length $|p_i|+1$ is
a palindrome pair.
\end{proposition}
\begin{proof}
Any factor of ${\bf p}$ of length $|p_i|+1$ is a conjugate of $p_ia$
for some $a \in \{0,1\}$. The result follows from
Lemma~\ref{pp_conj}.
\end{proof}
Now the word ${\bf p}$ is not necessarily Sturmian. For a suitable
choice of $w_i$, we have that $0p_i0$ and $1p_i1$ are both factors of
${\bf p}$. However it is well-known that this implies that ${\bf p}$ is not
Sturmian (see \cite[Chapter~2]{Lot02}).
\section{Palindrome pairs in the Thue--Morse word}\label{tm}
Let $\mu$ be the morphism that maps $0\to 01$ and $1\to 10$.
Let ${\bf t} = \mu^\omega(0)$ be the Thue--Morse word.
\begin{theorem}\label{tm_pp}
The word ${\bf t}$ does not have property {\bf PP}.
\end{theorem}
\begin{proof}
This can be verified ``automatically'' using the Walnut Prover
software created by Hamoon Mousavi and available at
\begin{center}
\url{https://cs.uwaterloo.ca/~shallit/papers.html}~.
\end{center}
We will not explain in detail the methodology implemented by the
Walnut Prover (the reader may consult \cite{GHS13} or \cite{SS15}, for example). The
important point is that to be able to apply this method, we need the property
{\bf PP} to be expressible in a certain extension of first order
logic. The relevant formulae are given below. The first defines all
pairs $(i,j)$ such that ${\bf t}[i : j]$ is a palindrome:
\[
(i,j) : (i=j) \vee ((i1$,
then the suffix of $w$ starting with the last $1$ of $b_{k-1}$
is a proper factor of $w$, but not a palindrome pair, a
contradiction. Thus all internal blocks of ones have length
$1$. Thus $z = 11(01)^r 00$ is a factor of $w$ for some
$k\geq1$, and hence, as $z$ is not a palindrome pair, $z =
w$. This completes the case.
\textbf{Case 2.} Assume now that $w$ has at most four blocks. Thus \[w = b_0 0 b_1 0\ldots 0\]
Since $w$ is not a palindrome pair it follows that $00$ is a suffix of $w$. Since $10 b_1 00$ is a proper factor of $w$, and hence a palindrome pair, it follows that $|b_1| = 1$. Thus $w$ contains, and is hence equal to, $110100$. This completes the proof.
\end{proof}
We now construct the class of minimal non-palindrome pairs inductively. It is easily verified that every word of length five or less is a palindrome pair. The minimal non-palindrome pairs of length six are given below. For $i\geq 7$, to generate the minimal non-palindrome pairs of length $i$:
\begin{itemize}
\item Extend any internal maximum block in a minimal non-palindrome pair of length $i-1$ by one.
\item If $i$ is even, add the words
$11(01)^{\frac{i-4}{2}}00$, $0 1^\frac{i-4}{2} 0
1^{\frac{i-4}{2}+1} 0$, $1 0^\frac{i-4}{2} 1
0^{\frac{i-4}{2}+1} 1$, $01^{\frac{i-2}{2}}0^{\frac{i-2}{2}}1$ and their reverses.
\end{itemize}
The minimal non-palindrome pairs for the first few $i$ are given in the following table. For conciseness, reverses and words with prefix $1$ have been omitted.
\begin{table}[h!]
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
i & 6 & 7 & 8 & 9 & 10 \\ \hline
& 001011 & 0011101 & 00101011 & 001111101 & 0010101011\\
& 001101 & 0100011 & 00111101 & 010000011 & 0011111101\\
& 010011 & 0101110 & 01000011 & 010111110 & 0100000011\\
& 010110 & 0110001 & 01011110 & 011000001 & 0101111110\\
& 011001 & 0111001 & 01100001 & 011011110 & 0110000001\\
& & & 01101110 & 011100001 & 0110111110\\
& & & 01110001 & 011110001 & 0111000001\\
& & & 01111001 & 011111001 & 0111011110\\
& & & & & 0111100001\\
& & & & & 0111110001\\
& & & & & 0111111001\\
\hline
\end{tabular}
\caption{List of short minimal non-palindrome pairs}
\end{center}
\end{table}
This leads us to our main result.
\begin{theorem}
The minimal non-palindrome pairs are exactly those words described above.
\end{theorem}
\begin{proof}
It is easily verified that those words of length six given in the
table, as well as those described in part two of the construction
above are minimal non-palindrome pairs. It then follows from Lemma
\ref{mnpp_add} that all the constructed words are also minimal
non-palindrome pairs.
To show that these are the only minimal non-palindrome pairs, let
$w'$ be a minimal non-palindrome pair of length $i \geq 7$. If $w'$
has no internal maximum blocks, then by
Lemma~\ref{mnpp_without_max_int_blk}, $w'$ is either
$11(01)^{\frac{i-4}{2}}00$ or its reverse, and is therefore
accounted for by our construction.
If $w'$ has exactly one internal maximum block, then $w'$ can be
obtained by extending an internal maximum block in some word $w$ of
length $i-1$. By Lemma~\ref{mnpp_delete} $w$ is either a minimal
non-palindrome pair, or is one of
$0 1^\frac{i-4}{2} 0 1^{\frac{i-4}{2}} 0$ or
$1 0^\frac{i-4}{2} 1 0^{\frac{i-4}{2}} 1$. Again $w'$ is accounted
for by our construction.
If $w'$ has more than one internal maximum block, then without loss
of generality $w'$ contains a factor $01^k0^k1$ for some $k \geq 2$.
However this factor is not a palindrome pair. It follows that this
factor is not a proper factor and hence that
$w' = 01^{\frac{i-2}{2}}0^{\frac{i-2}{2}}1$. Again $w'$ is accounted
for by our construction. This concludes the proof.
\end{proof}
\begin{corollary}
Let $npp(i)$ be the number of minimal non-palindrome pairs of
length $i$. Then $npp(i) = 0$ if $i<6$ and for all $j \geq 3$,
\[npp(2j) = npp(2j+1) = 8j-12.\]
\end{corollary}
\begin{proof}
One first checks that there are 12 minimal non-palindrome pairs of
length 6. Let $i > 6$ be odd. Every minimal non-palindrome pair
of length $i-1$ with exactly 1 internal maximum block produces one of
length $i$ by extending this internal maximum block. The word
$11(01)^{\frac{i-5}{2}}00$ and its reversal produce no minimal
non-palindrome pairs of length $i$, since they have no internal
maximum blocks to extend. The word $01^{\frac{i-3}{2}}0^{\frac{i-3}{2}}1$ and
its reversal each produce two minimal non-palindrome pairs, since they
each have two internal maximum blocks. Thus there is no net increase
in the number of minimal non-palindrome pairs when going from length
$i-1$ to $i$, and so we have $npp(i)=npp(i-1)$.
On the other hand, if $i$ is even, then every minimal non-palindrome
pair of length $i-1$ produces one minimal non-palindrome pair of length
$i$. Additionally, our construction adds eight new words of length
$i$. Thus there are
\begin{eqnarray*}
&&npp(i-1)+8 \\
&=& npp(i-2)+8 \quad\quad\text{(since $i-1$ is odd)}\\
&=& 4(i-2)-12+8 \quad\quad\text{(inductively)}\\
&=& 4i-12
\end{eqnarray*}
minimal non-palindrome pairs of length $i$.
Writing $i=2j$ if $i$ is even and $i=2j+1$ if $i$ is odd, the above
gives $npp(2j) = npp(2j+1) = 8j-12$, as required.
\end{proof}
\section{Conclusion}
Here we mention some interesting open questions raised by the previous
results. The first one is an obvious one, although we shall
see shortly that the answer may, in fact, be ``no''.
\begin{question}
Does property {\bf PP} characterize some interesting class of words?
\end{question}
We can also define a complexity function based on palindrome pairs.
Recall that the \emph{factor complexity function} $C_{\bf w}(n)$
counts the number of factors of ${\bf w}$ of length $n$. Similarly,
the \emph{palindrome complexity function} $P_{\bf w}(n)$ counts the
number of palindromic factors of ${\bf w}$ of length $n$. We could
therefore define a \emph{palindrome pair complexity function} $PP_{\bf
w}(n)$ that counts the number of factors of ${\bf w}$ of length $n$
that are palindrome pairs. Property {\bf PP} could then be rephrased
as ``$C_{\bf w}(n) = PP_{\bf w}(n)$ for infinitely many $n$.''
\begin{problem}
Explore the relationships between the functions $C_{\bf w}(n)$,
$P_{\bf w}(n)$, and $PP_{\bf w}(n)$.
\end{problem}
It is known that if ${\bf w}$ has linear factor complexity then its
palindromic complexity is bounded \cite{ABCD03}. We have already seen
above that this is not true for the palindrome pair complexity. The
results of Section~\ref{tm} give upper and lower bounds for the
palindrome pair complexity of the Thue--Morse word for certain values
of $n$.
\begin{problem}
Give explicit formulas for the palindrome pair complexity of words
such as the Fibonacci word and the Thue--Morse word.
\end{problem}
Further to the question posed above regarding whether property ${\bf
PP}$ characterizes some interesting class of words, one might wonder
if, for instance, property {\bf PP} implies $O(n)$ factor complexity.
Unfortunately, this is not the case. Suppose we perform the
construction of the word ${\bf p}$ in Proposition~\ref{shuffling_pals}
by defining the $w_i$'s as follows: $w_i = B_iB_i^R$, where $B_i$ is
a \emph{de Bruijn sequence} of order $|p_i|+1$; that is, $B_i$
contains every binary word of length $|p_i|+1$ exactly once (see, for
instance, \cite{FM78}). Then
${\bf p}$ contains at least $2^{|p_i|+1}$ factors of length
$(|p_i|+1)^2$. If we set $n_i = (|p_i|+1)^2$, then we see that
$C_{\bf p}(n_i) \geq 2^{\sqrt{n_i}}$. So there are words that are not
so ``nice'' that still have property ${\bf PP}$.
The following would show that property {\bf PP} is a property of
Sturmian words that does not carry over to \emph{episturmian words}.
In principle, it could be resolved using the Walnut Prover, as
described in the proof of Theorem~\ref{tm_pp}\ \footnote{When the
second author attempted to perform the necessary calculations using the Walnut
Prover, his computer ran out of memory. Apparently the current
version of Walnut does not handle Tribonacci-base computations efficiently.}.
\begin{conjecture}
The Tribonacci word does not have property {\bf PP}.
\end{conjecture}
In Section~\ref{rich_pp} we already stated the problem of
characterizing the binary words of each length that have the maximum
possible number of distinct palindrome pair factors.
Of course, the most interesting open problem is to resolve the
Frid--Puzynina--Zamboni Conjecture.
\section*{Acknowledgments}
We would like to
thank Luke Schaeffer for his help with using the Walnut Prover.
\begin{thebibliography}{9}
\bibitem{ABCD03}
J.-P. Allouche, M. Baake, J. Cassaigne, D. Damanik. Palindrome
complexity. {\it Theoret. Comput. Sci.} 292:9--31, 2003.
%\bibitem{ADQZ01}
%J.-P. Allouche, J. L. Davison, M. Queff\'elec, L. Q. Zamboni,
%``Transcendence of Sturmian or morphic continued fractions'',
%J. Number Theory 91 (2001), 39--66.
\bibitem{BBGL08}
A. Blondin-Mass\'e, S. Brlek, A. Garon, S. Labb\'e. Combinatorial
properties of $f$-palindromes in the Thue--Morse sequence. {\it Pure
Math. Appl. (PU.M.A.)} 19:39--52, 2008.
%\bibitem{Brl89}
%S. Brlek, ``Enumeration of factors in the Thue--Morse word'', Discrete
%Appl. Math. 24 (1989), 83--96.
%\bibitem{BR11}
%S. Brlek, C. Reutenauer, ``Complexity and palindromic defect of
%infinite words'', Theoret. Comput. Sci. 412 (2011), 493--497.
\bibitem{dM94}
A. de Luca, F. Mignosi. Some combinatorial properties of Sturmian
words. {\it Theoret. Comput. Sci.} 136:361--385, 1994.
\bibitem{F06}
S. Fischler. Palindromic prefixes and episturmian words, {\it J.
Combin. Theory Ser. A} 113:1285--1286, 2006.
\bibitem{FM78}
H. Fredricksen, J. Maiorana. Necklaces of beads in $k$ colors and
$k$-ary de~Bruijn sequences. {\it Discrete Math.} 23:207--201, 1978.
\bibitem{FPZ13}
A. E. Frid, S. Puzynina, L. Q. Zamboni. On palindromic factorization
of words. {\it Adv. in Appl. Math.} 50:737--748, 2013.
\bibitem{GJWZ09}
A. Glen, J. Justin, S. Widmer, L. Q. Zamboni. Palindromic richness.
{\it European J. Combin.} 30:510--531, 2009.
\bibitem{GHS13}
D. Go\u{c}, D. Henshall, J. Shallit. Automatic theorem-proving
in combinatorics on words. {\it Int. J. Found. Comput. Sci.}
24:781--798, 2013.
\bibitem{GSS15}
C. Guo, J. Shallit, A. Shur. On the combinatorics of palindromes and
antipalindromes. Preprint available at \arxiv{1503.09112}.
\bibitem{HM15}
S. Holub, M. M\"uller. Binary words with the fewest unbordered
conjugates. Preprint available at \arxiv{1504.02222}.
\bibitem{Kem82}
R. Kemp. On the number of words in the language $\{w\in \Sigma^*
\mid w=w^R\}^2$. {\it Discrete Math.} 40:225--234, 1982.
\bibitem{Lot02}
M. Lothaire. {\it Algebraic Combinatorics on Words}. Cambridge, 2002.
\bibitem{Mel99}
G. Melan\c{c}on. Lyndon words and singular factors of sturmian [sic]
words. {\it Theoret. Comput. Sci.} 218:41--59, 1999.
\bibitem{SS15}
L. Schaeffer, J. Shallit. Closed, rich, privileged, trapezoidal, and
balanced words in automatic sequences. Preprint available at
\arxiv{1508.02074}.
\end{thebibliography}
\end{document}