% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc,tabularx,booktabs}
\specs{P44}{19(3)}{2012}

\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\allowdisplaybreaks
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Parity index of binary words and \\ powers of prime words}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Aleksandar Ili\' c\\
\small Faculty of Sciences and Mathematics\\[-0.8ex]
\small University of Ni\v s, Serbia\\
\small\tt aleksandari@gmail.com\\
\and
Sandi Klav\v zar \\
\small Faculty of Mathematics and Physics \\[-0.8ex]
\small University of Ljubljana, Slovenia \\
\small and \\
\small Faculty of Natural Sciences and Mathematics \\[-0.8ex]
\small University of Maribor, Slovenia \\
\small \tt sandi.klavzar@fmf.uni-lj.si\\
\and
Yoomi Rho\footnote{Corresponding author} \\
\small Department of Mathematics \\[-0.8ex]
\small University of Incheon, Korea \\
\small \tt rho@incheon.ac.kr
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Apr 1, 2012}{Sep 15, 2012}{Oct 4, 2012}\\
\small Mathematics Subject Classifications: 05A05, 68R15, 68W32.}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
Let $f$ be a binary word and let ${\cal F}_d(f)$ be the set of words of length
$d$ which do not contain $f$ as a factor (alias words that avoid the pattern
$f$). A word is called even/odd if it contains an even/odd number
of 1s. The parity index of $f$ (of dimension $d$) is introduced as the
difference between the number of even words and the number of odd words in
${\cal F}_d(f)$. A word $f$ is called prime if every nontrivial suffix
of $f$ is different from the prefix of $f$ of the same length.
It is proved that if $f$ is a power of a prime word, then the
absolute value of the parity index of $f$ is at most~1. We conjecture
that no other word has this property and prove the conjecture
for words $0^r1^s0^t$, $r,s,t \geq 1$. The conjecture has also been verified
by computer for all words $f$ of length at most 10 and all $d\le 31$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} binary words; combinatorics on words; words avoiding
a pattern; parity index; generalized Fibonacci cubes.
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Elements of $B = \{0,1\}$ are called {\em bits} and an element of
$B^d$ is a {\em binary word} of length $d$. Since all words considered
here are binary, we will simply speak about {\em words}.
A word $u\in B^d$ will be written in the coordinate form as
$u=u_1u_2\ldots u_d$.
A word $f$ is a {\em factor} of a word $x$ if $f$
appears as a sequence of $|f|$ consecutive bits of $x$.
A word $u$ is called {\em $f$-free} if it does not
contain $f$ as a factor.
For a word $f$ and positive integer $d$, let
$${\cal F}_d(f) = \{ u\in B^d\ |\ u\ {\rm is}\ f{\rm -free} \}\,.$$
The product notation will mean concatenation, for example,
$1^r$ is the word of length $r$ with all bits equal 1.
A word $b$ is a {\em power} of a word $c$ if $b = c^k$ for
some $k\ge 1$. A word is called {\em even} if it contains an even number
of 1s and {\em odd} otherwise.

Suppose that $f$ is a word and $d$ is a positive integer. Then the
{\em generalized Fibonacci cube}, $Q_d(f)$, is the graph obtained
from the $d$-dimensional cube $Q_d$ by removing all vertices that contain $f$ as a
factor. In other words, $V(Q_d(f)) = {\cal F}_d(f)$, two vertices being
adjacent if they differ in exactly one bit.
These graphs were studied for the first time in~\cite{ilklro-2012},
but special cases were extensively studied earlier.
The most notable special case is formed by Fibonacci cubes
$\Gamma_d = Q_d(11)$, $d\ge 1$, see the survey~\cite{kl-2012}.
The special case of $Q_d(1^s)$ was introduced
in~\cite{hsu-93} (under the same name of generalized cubes)
and further investigated in~\cite{lihs-94,za-96}.

The definition of the generalized Fibonacci cubes naturally leads
to different problems on words. The most fundamental problem is
to determine the order of these graphs. This problem was
studied earlier under the notion of words avoiding
a pattern. Calling $f$ a pattern, then the number of words avoiding
$f$ is just the number of $f$-free words. Baccherini, Merlini and
Sprugnoli~\cite{bame-2007} were interested in the number of $f$-free
words that contain prescribed numbers of 0s and 1s and established
that they are closely related to proper Riordan arrays. This work
was extended in~\cite{mesp-2011}.

Another natural problem about generalized Fibonacci cubes is when they embed isometrically into hypercubes. This question
naturally leads to the concept of the so called good and bad words.
A word $f$ is said to be {\em $d$-good} if for any $f$-free words $u$ and $v$
of length $d$, $v$ can be obtained from $u$ by complementing one by one the bits
of $u$ on which $u$ and $v$ differ, such that all intermediate words are
$f$-free. Then $f$ is {\em good} if it is $d$-good for any $d\ge 1$.
The main result of~\cite{klsh-2012} asserts that about eight percent of
all words are good. 
The study of good words was continued in~\cite{ilklro-2012b}
by introducing the {\em index} $\beta(f)$ of $f$ as the smallest integer $d$
such that $f$ is not $d$-good. Among other results it was proved that
$\beta(f)<|f|^2$ holds for any bad word $f$.

Our principal motivation for the present paper is a result of~\cite{lihs-94}
asserting that each $Q_d(1^r)$ contains a hamiltonian path. This in particular
implies that the bipartition of $Q_d(1^r)$ is balanced. (By the way, it is
not difficult to see that every generalized Fibonacci cube is connected.)
Clearly, the bipartition sets of $Q_d(f)$ are formed by even and odd
words, respectively. Hence, for a set of words $X$, let $e(X)$ and $o(X)$ be
the number of even and odd words in $X$, respectively.
Let in addition $\Delta(X) = e(X) - o(X)$, in particular
write $\Delta(x) = \Delta(\{x\})$ for a word $x$. That is, $\Delta(x) = 1$ if $x$
is even and $\Delta(x) = -1$ if $x$ is odd. Then we define
the {\em parity index} of $f$ of dimension $d$ as
$${\rm PI}_d(f) = \Delta({\cal F}_d(f))\,.$$
Using this notation, a necessary condition for $Q_d(f)$ to contain a
hamiltonian path is that $|{\rm PI}_d(f)|\le 1$.

In the next section we introduce prime words and prove that if $f$ is a
power of a prime word then $|{\rm PI}_d(f)|\le 1$ holds for any $d$.
In Section~\ref{sec:not-prime} we consider the parity index of
the words $0^r1^s0^t$ and prove that for any $d$ large enough,
$|{\rm PI}_d(0^r1^s0^t)|\ge 2$. For the special case of $0^r10^r$
a more precise result is obtained, in particular it is noted that
$\{|PI_d(010)|\}_{d\ge 3}$ is the so-called Padovan sequence.
In Section~\ref{sec:evidence} we pose a conjecture that
powers of prime words are the only words with the property
$|{\rm PI}_d(f)|\le 1$ for any $d$ and verify the conjecture for all
words of length $\le 10$ and for all $d\le 31$. We conclude by indicating 
a possible approach to the conjecture via generating functions that 
count the words that do not contain the binary word as a given factor.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Powers of prime words}
\label{sec:prime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A word $f$ of length $d$ is {\em prime} if for any $k$, $1\le k\le d-1$,
the suffix of $f$ of length $k$ is different from the prefix of $f$ of the same
length. In particular, words 0 and 1 are prime, and if $d\ge 2$, then
the first bit and the last bit of a prime word are different.
For instance, $001101$ is a prime word which easily follows from the
fact that the factor $00$ appears only at its beginning. On the
other hand the word $01101011$ is not prime as it starts and ends with $011$.

For a word $f$ of length $\ell$ let
${\cal S}_d(f)=B^d\setminus {\cal F}_d(f)$, that is,
$${\cal S}_d(f)=\{b=b_1b_2\ldots b_d \ |\ b\ {\rm contains\ factor}\ f\}\,.$$
For $i=1, 2, \ldots, d-\ell+1$ let in addition
$${\cal S}_d^{(i)}(f)=\{b=b_1b_2\cdots b_d \ | \ b\in S, b_{i}b_{i+1}\cdots b_{i+\ell-1}=f\}\,.$$
Then ${\cal S}_d(f)=\bigcup_{i=1}^{d-\ell+1} {\cal S}_d^{(i)}(f)$.

By ${X\choose k}$ we denote the set of all $k$-subsets of the set $X$.

\begin{lemma}
\label{lem:inclusion-exclusion}
Let $f$ be a word of length $\ell$. Then
$$\Delta({\cal S}_d(f)) = \sum_{k=1}^{d-\ell+1} (-1)^{k-1}
\sum_{I\subseteq {{\mathbb N}_{d-\ell+1}\choose k}} \Delta\left(\cap_{i\in I}{\cal S}_d^{(i)}(f)\right)\,.$$
\end{lemma}

\begin{proof}
Let $\chi_A$ be the characteristic function of a set $A$:
$$\chi_A(x)=
\left\{ \begin{array}{ll}
 1;  & x\in A,\\
 0;  & \text{otherwise}\,.\\
\end{array}\right.$$
Since ${\cal S}_d(f)=\bigcup_{i=1}^{d-\ell+1} {\cal S}_d^{(i)}(f)$,
the inclusion and exclusion principle implies that for every $x\in {\cal S}_d(f)$,
$$\sum_{k=1}^{d-\ell+1}
(-1)^{k-1}\sum_{I\subseteq {{\mathbb N}_{d-\ell+1}\choose k}}\chi_{\cap_{i\in
I}{\cal S}_d^{(i)}(f)}(x) = 1\,.$$
Therefore,
\begin{eqnarray*}
\Delta({\cal S}_d(f)) & = & \sum_{x\in {\cal S}_d(f)}\Delta(x) \\
 & = & \sum_{x\in {\cal S}_d(f)}\Delta(x)\left(\sum_{k=1}^{d-\ell+1}
(-1)^{k-1}\sum_{I\subseteq {{\mathbb N}_{d-\ell+1}\choose k}}\chi_{\cap_{i\in
I}{\cal S}_d^{(i)}(f)}(x)\right) \\
& = & \sum_{k=1}^{d-\ell+1} (-1)^{k-1}\sum_{I\subseteq {{\mathbb N}_{d-\ell+1}\choose
k}}\sum_{x\in {\cal S}_d(f)}\Delta(x)\chi_{\cap_{i\in I}{\cal S}_d^{(i)}(f)}(x)\\
& = & \sum_{k=1}^{d-\ell+1} (-1)^{k-1}
\sum_{I\subseteq {{\mathbb N}_{d-\ell+1}\choose k}} \Delta(\cap_{i\in I}{\cal S}_d^{(i)}(f))\,.
\end{eqnarray*}
\end{proof}


\begin{theorem}
\label{thm:prime}
Let $f$ be a  power of a prime word. Then $|{\rm PI}_d(f)|\le 1$ for
any $d\ge 1$.
\end{theorem}

\begin{proof}
Let $d\ge 1$. Suppose first that $f$ is a prime word.
When $d < \ell$, we have ${\cal F}_d(f)= B^d$
and if $d = \ell$, then ${\cal F}_d(f)$ contains all but the
word $f$. Hence we may assume in the rest that $d > \ell$.
Since $e(B^d) = o(B^d)$, we have $e({\cal F}_d(f)) + e({\cal S}_d(f)) =
o({\cal F}_d(f)) + o({\cal S}_d(f))$. Hence ${\rm PI}_d(f)=\Delta({\cal F}_d(f)) =
-\Delta({\cal S}_d(f))$. It thus suffices to prove that
$|\Delta({\cal S}_d(f))|\le 1$.

We first note that $\Delta({\cal S}_d^{(i)}(f)) = 0$. Indeed, the first $i-1$ bits and the last
$d-\ell-i+1$ bits of the words from ${\cal S}_d^{(i)}(f)$ are arbitrary, hence ${\cal S}_d^{(i)}(f)$ contains
$2^{d-\ell-1}$ even words and the same number of odd words.
Consider now $X = \cap_{i\in I}{\cal S}_d^{(i)}(f)$ where $I = \{i_1, i_2, \ldots, i_k\}$
and $i_1<i_2<\cdots < i_k$. Because $f$ is a prime word,
$X = \emptyset$ as soon as for some index $j$, $i_{j+1} - i_j < \ell$.
Moreover, by the same argument as the one used for $\Delta({\cal S}_d^{(i)}(f))$,
$\Delta(X) = 0$ as soon as for some index $j$, $i_{j+1} - i_j > \ell$.
Hence $\Delta(X)$ can be nonzero only when
$k\ell = d$ and $i_j=(j-1)\ell+1$ for each $1\le j\le k$.
Therefore, applying Lemma~\ref{lem:inclusion-exclusion},
$$\Delta({\cal S}_d(f))= \left\{ \begin{array}{rll}
 0;  & \ell\nmid d,\\
 -1; & \ell |d,\ k\ {\rm odd},\ f\ \text{contains odd number of 1s},\\
 1; & \text{otherwise}\,.\\
\end{array}\right.$$
The proof is complete for a prime word $f$.

Assume now that $f = (f')^r$, where $f'$ is a prime word and $r\ge 2$.
Let $|f'| = \ell'$. The proof continues similarly as in the
case when $f$ was prime. The only difference is that now
$X = \emptyset$ as soon as for some index $j$, the difference $i_{j+1} - i_j$ is
not a multiple of $\ell'$ and so $\Delta(X)$ can be nonzero only when
$d$ is a multiple of $\ell'$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Non-prime words}
\label{sec:not-prime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we study the parity index of words consisting of
three blocks, that is, of words $0^r1^s0^t$, $r,s,t\ge 1$. Clearly,
none of these words is prime. In our main result (Theorem~\ref{thm:0^r1^s0^t})
we prove that for no such word $f$, $|{\rm PI}_d(f)|\le 1$ holds for all $d$.
Before that we separately give a more precise result for the special case
of $0^r10^r$. The obtained results in particular imply that $Q_d(0^r1^s0^t)$ does not
contain a hamiltonian path as soon as $d$ is large enough.

\begin{theorem}
\label{thm:0^r10^r}
Let $r\ge 1$. Then
$$|{\rm PI}_d(0^r10^r)| = \left\{ \begin{array}{ll}
        0; & d\le 2r, 2r+2\le d\le 3r+1\,, \\
        1; & d=2r+1, 3r+2\le d\le 4r+3\,.
\end{array} \right.$$
Moreover, for any $d\ge 4r+4$, $|{\rm PI}_d(0^r10^r)|\ge 2$.
\end{theorem}

\begin{proof}
Suppose first that $d\le 2r$. Then ${\cal F}_d(0^r10^r) = B^d$ and hence
${\rm PI}_{d}(0^r10^r) = 0$.
Since ${\cal F}_{2r+1}(0^r10^r) = B^d \setminus \{0^r10^r\}$ we
have ${\rm PI}_{2r+1}(0^r10^r) = 1$.

Let $d\ge 2r+2$.
Recall that $-{\rm PI}_d(0^r10^r)  = \Delta({\cal S}_d(f)) = \sum_{b \in {\cal S}_d(f)}\Delta(b)$.
By Lemma~\ref{lem:inclusion-exclusion},
$$-{\rm PI}_d(f) = \sum_{k=1}^{d-\ell+1} (-1)^{k-1}
\sum_{I\subseteq {{\mathbb N}_{d-\ell+1}\choose k}} \Delta(\cap_{i\in I}{\cal S}_d^{(i)}(f))\,.$$
Suppose that for a set $X=\cap_{i\in I}{\cal S}_d^{(i)}(f)$ there exists an index $i$
such that if $w\in X$ then also $w+e_i\in X$. Then
$\Delta(X) = 0$. It follows that
$\Delta(X) \ne 0$ if and only if there exist
$k\ge 0$ and $r\le r_j\le 2r$ for all $1\le j\le k$, such that
$$X = \{0^r10^{r_1}10^{r_2}1\cdots 0^{r_k}10^{r}\}\,.$$
Moreover, in that case $\Delta(X) =
\Delta(0^r10^{r_1}10^{r_2}1\cdots 0^{r_k}10^{r})= (-1)^{k+1}$.

Hence let $k\ge 0$ and $r\le r_j\le 2r$, $1\le j\le k$, and set
$b = 0^r10^{r_1}10^{r_2}1\cdots 0^{r_k}10^{r}$.
Let $v=b_{r_1+2}b_{t_1+3}\cdots b_d$ be the word obtained from $b$ by omitting
the first $r_1+1$ bits, so that $v\in B^{d-r_1-1}$.
Since $b$ has one more bit of 1 than $v$ does, $\Delta(v)=-\Delta(b)$.

Note that $v$ starts with $0^r1$. Then
$$
v\in \bigcap_{j\in J}S_{d-r_1-1}^{(j)}(f) \qquad \mbox{if and only
if} \qquad b\in {\cal S}_d^{(1)}(f)\bigcap \left(\cap_{j\in J}{\cal S}_d^{(j+r_1+1)}(f)\right).
$$
Now we can compute as
follows:
\begin{eqnarray}
\nonumber
{\rm PI}_d(0^r10^r) & = & -\Delta({\cal S}_d(f)) = - \sum_{b\in {\cal S}_d(f)}\Delta(b) \\
\nonumber
& = & -\left( \sum_{b\in {\cal S}_d(f) \atop r_1=r}\Delta(b)+\sum_{b\in {\cal S}_d(f) \atop r_1=r+1}\Delta(b) +
       \cdots+\sum_{b\in {\cal S}_d(f) \atop r_1=2r}\Delta(b) \right)\\
\nonumber
& = & -\Bigg( \sum_{v\in S_{d-r-1}(f)}-\Delta_{d-r-1}(v)+\sum_{v\in S_{d-r-2}(f)}-\Delta_{d-r-2}(v) + \cdots \\
\nonumber
     & & +\sum_{v\in S_{d-2r-1}(f)}-\Delta_{d-2r-1}(v)\Bigg)\\
\nonumber
& = & \sum_{v\in S_{d-r-1}(f)}\Delta_{d-r-1}(v)+\sum_{v\in S_{d-r-2}(f)}\Delta_{d-r-2}(v) + \cdots \\
\nonumber
     & & +\sum_{v\in S_{d-2r-1}(f)}\Delta_{d-2r-1}(v)\\
\nonumber
& = & \sum_{r\le r_1\le 2r}\sum_{v\in S_{d-r_1-1}(f)}\Delta_{d-r_1-1}(v)\\
\nonumber
& = & \sum_{r\le r_1\le 2r}\Delta_{d-r_1-1}\left(\bigcup_{v\in S_{d-r_1-1}(f)}v\right)\\
\nonumber
& = & \sum_{r\le r_1\le 2r}\Delta_{d-r_1-1}(S_{d-r_1-1}(f))\\
\label{eq:only-one}
& = & - \sum_{r\le r_1\le 2r}{\rm PI}_{d-r_1-1}(0^r10^r)\,.
\end{eqnarray}
It follows that $|{\rm PI}_d(0^r10^r)| = |\sum_{r\le r_1\le 2r}{\rm PI}_{d-r_1-1}(0^r10^r)|$.

As the values ${\rm PI}_{d-r_1-1}(0^r10^r)$ have the same sign for all
$r\le r_1\le 2r$, from Equation~\eqref{eq:only-one} we get
\begin{eqnarray}
\label{eq:0^r10^r}
|{\rm PI}_d(0^r10^r)| = \sum_{r\le r_1\le 2r}|{\rm PI}_{d-r_1-1}(0^r10^r)|\,.
\end{eqnarray}
Set $a_d=|{\rm PI}_d(0^r10^r)|$ for all $d$.
We already know that $a_d=0$ for all $d\le 2r$ and that $a_{2r+1}=1$.
Let $d\ge 2r+2$.
If $d\le 3r+1$ and there is a word $b\in S_{d}(f)$, then
there is an index $i$
such that if $w\in X$ then also $w+e_i\in X$ and hence
$\Delta(X) = 0$. %%Therefore $a_d=0$ if $2r+2\le d\le 3r+1$.

Assume $d\ge 3r+2$.
When $3r+2\le d\le 4r+2$, ${\rm PI}_d(0^r10^r)=\Delta(0^r10^{d-2r-2}10^r)=1$ or $-1$ and hence $a_d=1$.
When $d=4r+3$, $a_{d}=a_{2r+2}+\cdots +a_{3r+2}=1$.
Let $d= 4r+3+u$ for some $u\ge 1$.
Then by Equation~\eqref{eq:0^r10^r}, $a_{4r+3+u}=a_{2r+2+u}+\cdots +a_{3r+2+u}$.
If $u\le r$, then $2r+2+u\le 3r+2 < 3r+2+u\le 4r+2$ and therefore $a_d\ge 2$.
Assume $u\ge r+1$. Let $u'=u-r$. Then $d= 5r+3+u'$ for $u'\ge 1$.
By Equation~\eqref{eq:0^r10^r},
$a_{5r+3+u'}=a_{3r+2+u'}+\cdots +a_{4r+2+u'}$.
If $u'\le r$, then $3r+2\le 3r+2+u'< 4r+3\le 4r+2+u'$ and therefore $a_d\ge 2$.
Assume $u'\ge r+1$. Then let $u''=u'-r$. Then $d=6r+3+u''$ for $u''\ge 1$.
By Equation~\eqref{eq:0^r10^r}, $a_{6r+3+u''}=a_{4r+2+u''}+\cdots +a_{5r+2+u''}$.
As $3r+2\le 4r+2+u''< 5r+2+u''$, $a_d\ge 2$.
Thus when $d\ge 4r+4$, $a_d\ge 2$.
\end{proof}

The special case of Theorem~\ref{thm:0^r10^r} when $r=1$ deserves a special
attention. In that case,
$$|{\rm PI}_d(010)| = |{\rm PI}_{d-2}(010)| + |{\rm PI}_{d-3}(010)|$$
with initial conditions $|{\rm PI}_3(010)| = 1$, $|{\rm PI}_4(010)| = 0$,
$|{\rm PI}_5(010)| = 1$ which is the Padovan sequence, see
sequence A000931 from~\cite{Sloan}.

\begin{theorem}
\label{thm:0^r1^s0^t}
Let $r,s,t\ge 1$. Let $z$ be the integer such that $(z-1)t+2\le r+s\le zt+1$. Then
% $$|{\rm PI}_d(0^r1^s0^t)|  \left\{ \begin{array}{ll}
%         =0; & d<r+s+t,\\
%         & yr+ys+yt<d<(y+1)r+(y+1)s+t \ {\rm } \ {\rm for } \ {\rm } 1\le y\le z\,,\\
%         \ge 1; & d=r+s+t, \\
%         & (y+1)r+(y+1)s+t\le d\le (y+1)r+(y+1)s+(y+1)t \ {\rm } \ {\rm for } \ {\rm } 1\le y\le z,\\
%         & d=(z+1)r+(z+1)s+(z+1)t+1\,.
% \end{array} \right.$$
$$|{\rm PI}_d(0^r1^s0^t)|  \left\{ \begin{array}{ll}
        =0; & d<r+s+t,\\
        & y(r+s+t)<d<(y+1)(r+s)+t \ {\rm } \ {\rm for } \ {\rm } 1\le y\le z\,,\\
        \ge 1; & d=r+s+t, \\
        & (y+1)(r+s)+t\le d\le (y+1)(r+s+t) \ {\rm } \ {\rm for } \ {\rm } 1\le y\le z,\\
        & d=(z+1)(r+s+t)+1\,.
\end{array} \right.$$
Moreover, for any $d\ge (z+1)(r+s+t)+2$, $|{\rm PI}_d(0^r1^s0^t)|\ge 2$.
\end{theorem}

\begin{proof}
Since ${\rm PI}_d(0^r1^s0^t) = {\rm PI}_d(0^t1^s0^r)$, it suffices to prove
the result for words $0^r1^s0^t$ with $r\ge t$.
By the same argument as in the proof of Theorem \ref{thm:0^r10^r},
$\Delta(X) \ne 0$ if and only if there exist
$k\ge 0$ and $r\le r_j\le r+t$ for all $1\le j\le k$ such that
$$X = \{0^r1^s0^{r_1}1^s0^{r_2}1^s\cdots 0^{r_k}1^s0^{t}\}\,$$
where $\Delta(X) = (-1)^{(k+1)s}$.
Also
\begin{eqnarray}
\label{eq:0^r1^s0^t}
|{\rm PI}_d(0^r1^s0^t)| = \sum_{r\le r_1\le r+t}|{\rm PI}_{d-r_1-s}(0^r1^s0^t)|\,.
\end{eqnarray}

Set $a_d=|{\rm PI}_d(0^r1^s0^t)|$ for all $d$.
We already know that $a_d=0$ for all $d< r+s+t$ and that $a_{r+s+t}=1$.
Let $d\ge r+s+t+1$.
In the first part of the proof, we prove the theorem for
$d\le (z+1)r+(z+1)s+(z+1)t$ by induction on $y$ for $1\le y\le z$.
Then we prove the theorem for $d\ge (z+1)r+(z+1)s+(z+1)t+1$.
The idea of the proof is as follows. From the first part of the
proof, we notice that for each $y\ge 1$, $a_d=0$ for $r+s-(y-1)t-1$
consecutive numbers of $d$ and then $a_d\ge 1$ for the next $yt+1$ consecutive numbers of $d$.
As $y$ increases, $r+s-(y-1)t-1$ decreases to zero and $yt+1$ increases.
While, by Equation~\eqref{eq:0^r1^s0^t}, $a_d=a_{d-r-s-t}+\cdots+ a_{d-r-s}$,
which is a sum of $t+1$ consecutive numbers, where $t+1$ is a constant for given $0^r1^s0^t$.
Therefore for large enough $d$, $a_d\ge 2$.

By a similar argument as in the proof of Theorem \ref{thm:0^r10^r},
$a_d=0$ if $d< 2r+2s+t$ and $a_d=1$ if $2r+2s+t\le d\le 2r+2s+2t$.
Thus the statement is true for $y=1$.
Let $y\ge 2$.
Suppose the statement is true for all $1\le y_0<y$.
Let $d=yr+ys+yt+u$ for some $u\ge 1$.
Then by Equation~\eqref{eq:0^r1^s0^t}, $a_{yr+ys+yt+u}=a_{(y-1)r+(y-1)s+(y-1)t+u}+\cdots +a_{(y-1)r+(y-1)s+yt+u}$.
When $d<(y+1)r+(y+1)s+t$, i.e., $u< r+s-(y-1)t$,
$(y-1)r+(y-1)s+(y-1)t<(y-1)r+(y-1)s+(y-1)t+u<(y-1)r+(y-1)s+yt+u< yr+ys+t$
and hence by the induction assumption, $a_d=0$.
When $d=(y+1)r+(y+1)s+t$, i.e., $u= r+s-(y-1)t$,
$(y-1)r+(y-1)s+yt+u= yr+ys+t$ and hence by the induction assumption, $a_d\ge a_{yr+ys+t}\ge 1$.
Assume $d\ge (y+1)r+(y+1)s+t+1$, i.e., $u\ge r+s-(y-1)t+1$. Let $u'=u-r-s+(y-1)t$.
Then $d=(y+1)r+(y+1)s+t+u'$ where $u'\ge 1$.
By Equation~\eqref{eq:0^r1^s0^t}, $a_{d}=a_{yr+ys+u'}+\cdots +a_{yr+ys+t+u'}$.
If $d\le (y+1)r+(y+1)s+(y+1)t$, i.e., $u'\le yt$, then $yr+ys+u'\le yr+ys+yt$.
Considering that $yr+ys+t< yr+ys+t+u'$,
$a_d\ge a_{yr+ys+t}+a_{yr+ys+t+1}$ or $a_d\ge a_{yr+ys+u'}+a_{yr+ys+u'+1}$
depending on whether $yr+ys+u'< yr+ys+t$ or not.
Therefore by the induction assumption, $a_d\ge 1$.
Thus the theorem is proved for all $d\le (z+1)r+(z+1)s+(z+1)t$.

Assume $d\ge (z+1)r+(z+1)s+(z+1)t+1\ge (z+2)r+(z+2)s+t$.
Let $d= (z+2)r+(z+2)s+t+u''$ where $u''\ge 0$.
Then by Equation~\eqref{eq:0^r1^s0^t},
$a_d=a_{(z+2)r+(z+2)s+t+u''}=a_{(z+1)r+(z+1)s+u''}+\cdots +a_{(z+1)r+(z+1)s+t+u''}$.
Note that $(z+1)r+(z+1)s+t+u''\ge (z+1)r+(z+1)s+t$.
Assume $d= (z+2)r+(z+2)s+t$, i.e., $u''=0$. Then
$(z+1)r+(z+1)s+t+u''= (z+1)r+(z+1)s+t$. If $r+s>zt$, then $(z+1)r+(z+1)s> zr+zs+zt$
and hence $a_d=a_{(z+1)r+(z+1)s+t}\ge 1$. If $r+s\le zt$, then
$(z+1)r+(z+1)s\le zr+zs+zt$ and hence $a_d\ge a_{zr+zs+zt}+a_{(z+1)r+(z+1)s+t}\ge 2$.

Let $d> (z+2)r+(z+2)s+t$, i.e., $u''>0$. Then $(z+1)r+(z+1)s+t+u''> (z+1)r+(z+1)s+t$.
First assume $d<(z+2)r+(z+2)s+(z+2)t$, i.e., $u''<(z+1)t$. Then
$(z+1)r+(z+1)s+u''<(z+1)r+(z+1)s+(z+1)t$. Therefore
$a_d\ge a_{(z+1)r+(z+1)s+t}+a_{(z+1)r+(z+1)s+t+1}$ or
$a_d\ge a_{(z+1)r+(z+1)s+u''}+a_{(z+1)r+(z+1)s+u''+1}$ depending
on whether $(z+1)r+(z+1)s+u''<(z+1)r+(z+1)s+t$ or not.
Thus $a_d\ge 2$ in any case. Second assume $d=(z+2)r+(z+2)s+(z+2)t$, i.e.,
$u''=(z+1)t$. Then $(z+1)r+(z+1)s+u''=(z+1)r+(z+1)s+(z+1)t$
and hence $a_d\ge a_{(z+1)r+(z+1)s+u''}+a_{(z+1)r+(z+1)s+u''+1}\ge 2$ considering that
$(z+1)r+(z+1)s+(z+1)t<(z+1)r+(z+1)s+u''+1<(z+2)r+(z+2)s+(z+2)t$.
Finally assume $d>(z+2)r+(z+2)s+(z+2)t$, i.e., $u''>(z+1)t$.
Suppose there is $u''>(z+1)t$ such that $a_d\le 1$. Let $u''_0$ be the smallest
such an integer and $d_0= (z+2)r+(z+2)s+t+u''_0$.
Then $a_{d_0}=a_{(z+1)r+(z+1)s+u''_0}+\cdots +a_{(z+1)r+(z+1)s+t+u''_0}$. Since
$(z+1)r+(z+1)s+u''_0>(z+1)r+(z+1)s+(z+1)t$ and $(z+1)r+(z+1)s+t+u''_0<d_0$, $a_{d_0}\ge 2$,
which is a contradiction. Thus the statement is true for all $d$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Computer evidence and conjecture}
\label{sec:evidence}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Using computer we obtained the parity index for all words
$f$ of length at most 10 and all $d\le 31$. Since $Q_d(f)$ is isomorphic
to $Q_d(\overline{f})$, where $\overline{f}$ is the binary complement
of $f$, we have restricted the computation to words $f$ that contain
not more 1s than 0s. From the same reason reversed words need not
to be considered. In Table~\ref{tab:up-to-8} all words $f$ of
length at most 8 and with $|{\rm PI}_d(f)|\le 1$ for $d\le 31$
are collected.

%\begin{table}[ht]
%\centering
%\begin{tabular} {l|l}
%\toprule
%length & forbidden factor \\
%
%\midrule
%4  & 0010, 0110\\
%\midrule
%5 &  00010, 00100, 00110, 01001, 01010, 01110 \\
%\midrule
%6 &  000010, 000100, 000110, 001100, 001110,\\
% &  010001, 010010, 010110, 011001, 011110 \\
%\midrule
%7 & 0000010, 0000100, 0000110, 0001000, 0001010, \\
%& 0001100, 0001110, 0010001, 0010010, 0010100, \\
%& 0010110, 0011001, 0011010, 0011100, 0011110, \\
%& 0100001, 0100010, 0100101, 0100110, 0101001, \\
%& 0101010, 0101110, 0110001, 0110110, 0111110 \\
%\bottomrule
%\end{tabular}
%
%\caption{Classification of binary words with parity index greater than 1.}
%\end{table}

\begin{table}[ht]
\centering
\begin{tabular} {l|l}
\toprule
length & $f$ \\

\midrule

3 & 001 \\
\midrule
4 & 0001, 0011, 0101 \\
\midrule
5 & 00001, 00011, 00101 \\
\midrule
6 & 000001, 000011, 000101, 000111 \\
 & 001001, 001011, 001101, 010101 \\
\midrule
7 & 0000001, 0000011, 0000101, 0000111 \\
 & 0001001, 0001011, 0001101, 0010011 \\
 & 0010101, 0011101 \\
\midrule
8 & 00000001, 00000011, 00000101, 00000111 \\
 & 00001001, 00001011, 00001101, 00001111 \\
 & 00010001, 00010011, 00010101, 00010111 \\
 & 00011001, 00011011, 00011101, 00100011 \\
 & 00100101, 00101011, 00101101, 00110011 \\
 & 00110101, 00111101, 01010101 \\
\bottomrule
\end{tabular}
\caption{List of words $f$ with $|f|\le 8$ and $|{\rm PI}_d(f)|\le 1$ for $d\le 31$}
\label{tab:up-to-8}
\end{table}

It can be checked that every word from the table is a power of a prime
word. Moreover, the same was verified also for the obtained words
of length 9 and 10 (not given in the table). Based on this experiment and Theorems~\ref{thm:prime} and~\ref{thm:0^r1^s0^t} we pose:

\begin{conjecture}
\label{conj:main}
Let $f$ be a word such that $|{\rm PI}_d(f)|\le 1$ holds for any $d$.
Then $f$ is a power of a prime word.
\end{conjecture}

A possible approach to the conjecture would be to prove that if $f$ is
not a power of a prime word, then the sequence $\{|{\rm PI}_d(f)|\}_{d}$
satisfies a certain recurrence relation from which we can deduce the behavior
of the sequence. For instance, one can establish the recurrent formula
$$|{\rm PI}_d(01110)| = |{\rm PI}_{d-4}(01110)| + |{\rm PI}_{d-5}(01110)|,$$
with initial conditions  $|{\rm PI}_5(01110)| = 1$,
$|{\rm PI}_6(01110)| = |{\rm PI}_7(01110)| = |{\rm PI}_8(01110)| = 0$ and
$|{\rm PI}_9(01110)| = 1$. Similarly, either by applying
Equation~\eqref{eq:0^r1^s0^t} or by a tedious case analysis yields, one can get:
\begin{eqnarray*}
|{\rm PI}_d(000001000)| &=& |{\rm PI}_{d-6}(000001000)| + |{\rm PI}_{d-7}(000001000)| \\
&& + |{\rm PI}_{d-8}(000001000)| + |{\rm PI}_{d-9}(000001000)|,
\end{eqnarray*}
with initial conditions $|{\rm PI}_9(000001000)|=1$,
$|{\rm PI}_{10}(000001000)|=|{\rm PI}_{11}(000001000)|=|{\rm PI}_{12}(000001000)|=
|{\rm PI}_{13}(000001000)|=|{\rm PI}_{14}(000001000)|=0$, $|{\rm PI}_{15}(000001000)|=
|{\rm PI}_{16}(000001000)|=|{\rm PI}_{17}(000001000)|=1$.

In Fig.~\ref{fig:charts} the values of $|{\rm PI}_d(01110)|$ and $|{\rm PI}_d(000001000)|$ for
$5 \leq d \leq 55$ are plotted. Note that the sequence $|PI_d(f)|$ does not need to be monotone,
but it seems that starting from some large enough dimension the sequence is strictly increasing.

\begin{figure}[ht]
  \center
  \includegraphics [width = 13cm]{plot.eps}
  \caption {Values of $|{\rm PI}_d (f)|$ for $f = 01110$ and $f = 000001000$}
  \label{fig:charts}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding remarks}
\label{Concluding remarks} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Another approach to get further insight into the 
parity index of a binary word (in particular into Conjecture~\ref{conj:main})
would be to investigate the relationship with 
the generating function counting the words that do not contain the binary word as a 
given factor. To explicitly state these functions we need the following concepts 
from~\cite{guod-1981}, see also~\cite[page 374]{sefl-1996} and~\cite{bame-2007,mesp-2011}.  
Let $f=f_0f_1\ldots f_{d-1}$ be a word of length $d$, then its 
{\em autocorrelation} $c^{[f]}=c_0c_1\ldots c_{d-1}$ is the binary word with $c_i$ defined
to be $1$ if $f_j=f_{i+j}$ for all $0\le j\le d-1-i$, and  
defined to be $c_i=0$ otherwise. (In other words, $c_i=1$ if $f$ and its shift by $i$ bits agree 
in their intersection. In the terminology from~\cite{klsh-2012} we could also 
say that $c_i=1$ when $f$ has a 0-error overlap of length $d-i$.) 
For instance, the autocorrelation of $1100111$ is $1000011$ and the one
of $101010$ is $101010$. The {\em autocorrelation polynomial} $C^{[f]}(x,y)$ is the 
polynomial with coefficients given by the autocorrelation of $f$. More precisely, 
the coefficient of $x^jy^i$ is 1 if $c^{[f]}_{j+i}=1$ and the suffix of $f$ (of
length $i+j$) contains $j$ ones and $i$ zeros. For instance,  
$C^{[1100111]}(x,y) = 1 + x^3y^2 + x^4y^2$. Then the 
generating function counting the binary words that do not contain $f$ as
a factor is (see~\cite{bame-2007,mesp-2011}): 
$$F^{[f]}(x,y) = \frac{C^{[f]}(x,y)}{(1-x-y)C^{[f]}(x,y) + x^{d_1}y^{d_0}}\,,$$
where $d_1$ and $d_0$ are the numbers of ones and zeros in $f$, respectively, 
and the symbols $x$ and $y$ count the number of ones and zeros in the words. 

It could be interesting to notice the relation between the 
forbidden words studied here and the shape of the corresponding autocorrelation
polynomials as well as to approach $|{\rm PI}_d(f)|$ in terms of $F^{[f]}(x,y)$. 
To these two ideas we also add that it could also be interesting to relate 
the $r$-error overlap studies from~\cite{klsh-2012} with the respective 
autocorrelation polynomials. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We are grateful to a referee for pointing us the approach to the 
parity index as discussed in Section~\ref{Concluding remarks}. 

This work was supported by the
research Grants 174010 and 174033 of Serbian Ministry of Education and Science,
by the research grant P1-0297 of Ministry of Higher Education, Science
and Technology Slovenia, and by Basic Science Research Program through the National Research
Foundation of Korea funded by the Ministry of Education, Science and Technology grant 2011-0025319.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{99}

\bibitem{bame-2007}
  D.~Baccherini, D.~Merlini and R.~Sprugnoli. \newblock 
  Binary words excluding a pattern and proper {R}iordan arrays.
  \newblock {\em  Discrete Math.}, 307:1021--1037, 2007.

\bibitem{guod-1981}
  L.~J.~Guibas and A.~M.~Odlyzko. \newblock 
  String overlaps, pattern matching, and nontransitive games. \newblock 
  {\em J. Combin. Theory Ser. A}, 30:183--208, 1981.

\bibitem{hsu-93}
  W.-J.~Hsu. \newblock
  Fibonacci cubes---a new interconnection technology. \newblock
  {\em IEEE Trans. Parallel Distrib. Syst.}, 4:3--12, 1993.

\bibitem{ilklro-2012}
  A.~Ili{\'{c}}, S.~Klav{\v{z}}ar and Y.~Rho. \newblock
  Generalized {F}ibonacci cubes. \newblock
  {\em Discrete Math.}, 312:2--11, 2012.

\bibitem{ilklro-2012b}
  A.~Ili{\'{c}}, S.~Klav{\v{z}}ar and Y.~Rho. \newblock
  The index of a binary word. \newblock
  {\em Theoret. Comput. Sci.}, 452:100--106, 2012.
 	
\bibitem{kl-2012}
  S.~Klav{\v{z}}ar. \newblock
  Structure of Fibonacci cubes: a survey. \newblock
  {\em to appear in J. Comb. Optim.}, \doi{10.1007/s10878-011-9433-z}.

\bibitem{klsh-2012}
  S.~Klav{\v{z}}ar and S.~Shpectorov. \newblock
  Asymptotic number of isometric generalized {F}ibonacci cubes. \newblock
  {\em European J. Combin.}, 33:220--226, 2012.
	
\bibitem{lihs-94}
  J.~Liu, W.-J.~Hsu and M.~J.~Chung. \newblock
  Generalized {F}ibonacci cubes are mostly {H}amiltonian. \newblock
  {\em J. Graph Theory}, 18:817--829, 1994.

\bibitem{mesp-2011}
  D.~Merlini and R.~Sprugnoli. \newblock
  Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern. \newblock
  {\em Theoret. Comput. Sci.}, 412:2981--3001, 2011.

\bibitem{sefl-1996}
  R.~Sedgewick and P.~Flajolet. \newblock
  {\em An Introduction to the Analysis of Algorithms}. \newblock
  Addison-Wesley, Reading, MA, 1996.

\bibitem{Sloan}
  N.~J.~A.~Sloane. \newblock
  {\em The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences}. \newblock
  Published electronically at \url{http://oeis.org}.

\bibitem{za-96}
  N.~Zagaglia Salvi. \newblock
  On the existence of cycles of every even length on generalized {F}ibonacci cubes. \newblock
  {\em Matematiche (Catania)}, 51:241--251, 1996. 


\end{thebibliography}

\end{document}
