% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.11}{21(3)}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% 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}

% MY personnal packages
\usepackage{enumerate}

% 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}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% 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}

\newcommand{\todo}[1]{\texttt{TODO:#1}}

% entier, réels, etc
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}

% shortcut
\newcommand{\til}{\widetilde}
\newcommand{\Id}{\mathrm{Id}}
\newcommand{\Card}{\mathrm{Card}\,}
\newcommand{\Lst}{\textsc{Lst}}
\newcommand{\Fst}{\textsc{Fst}}
\newcommand{\Stab}{\mathrm{Stab}}
\newcommand{\Pal}{{\rm Pal}}
\newcommand{\alphabet}{\mathcal A}
\newcommand{\B}{\mathcal B}
\newcommand{\bu}{{\bf u}}
\newcommand{\bv}{{\bf v}}
\newcommand{\bx}{{\bf x}}
\newcommand{\bw}{{\bf w}}
\renewcommand{\L}{\mathcal L}
\newcommand{\Fact}{\L}
\newcommand{\emptyword}{\varepsilon}
\renewcommand{\P}{\mathcal P}
\newcommand{\modn}{\,\,(\bmod\,\, n)}
\newcommand{\modnalpha}{\,\,(\bmod\,\, n_\alpha)}


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

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

\title{\bf A Counterexample to a Question\\ of Hof, Knill and Simon}

% 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{Sébastien Labbé\thanks{With the support of NSERC (Canada)}\\
\small LIAFA, Université Paris Diderot - Paris 7,\\ [-0.8ex]
\small Case 7014, 75205 Paris Cedex 13, France\\ [-0.8ex]
\small \tt labbe@liafa.univ-paris-diderot.fr
}

% \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{Sep 27, 2013}{Jul 9, 2014}{Jul 21, 2014}\\
\small Mathematics Subject Classifications: 68R15, 37B10}

\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}
In this article, we give a negative answer to a question of Hof, Knill and
Simon (1995) concerning purely morphic sequences obtained from primitive
morphism containing an infinite number of palindromes. Their conjecture
states that such palindromic sequences arise from substitutions that are in
class~$\P$. The conjecture was proven for the binary alphabet by B. Tan in
2007. We give here a counterexample for a ternary alphabet.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Hof, Knill and Simon conjecture;
class~$\P$; palindromes; stabilizer.
\end{abstract}


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

A morphism of monoid $\varphi:\alphabet^*\to\alphabet^*$ is in \emph{class
$\P$} if there exists a palindrome $p$ and for every $\alpha \in \alphabet$
there exists a palindrome $q_\alpha$ such that $\varphi(\alpha)=pq_\alpha$
\cite{MR1372804}.  If $\bx$ is an infinite sequence generated by
a morphism in class~$\P$, then Hof, Knill and Simon proved
that $\bx$ contains an infinite number of palindrome factors.
Such morphisms allowed them to derive some discrete Schr\"odinger
operators having purely singular continuous spectrum.
% sage: rho = WordMorphism('a->bbaba,b->bba')
% sage: rho.fixed_point('b')
% word: bbabbabbababbabbabbababbabbabbababbabbab...
% sage: theta = WordMorphism('a->ab,b->ba')
% sage: theta.fixed_point('a')
% word: abbabaabbaababbabaababbaabbabaabbaababba...
For example, on the binary alphabet $\alphabet = \{a,b\}$, the morphism $\rho : a
\mapsto bbaba, b \mapsto bba$ is in class~$\P$. The morphism $\theta : a \mapsto ab,
b \mapsto ba$ is not in class~$\P$, but its square $\theta^2 : a \mapsto abba, b
\mapsto baab$ is in class~$\P$. Therefore, the fixed point
\[
\bx_{\rho} =
\rho(\bx_{\rho}) = bbabbabbababbabbabbababbabbabbababbabbab\cdots
\]
and the fixed point, also known as the Thue-Morse word,
\[
\bx_\theta =
\theta(\bx_\theta) = abbabaabbaababbabaababbaabbabaabbaababba\cdots
\]
are both palindromic, i.e., both contain an infinite number of palindromes.
The question of Hof, Knill and Simon that motivates this article concerns the
reciprocal. In their article, they wrote ``Clearly, we could include into
class~$\P$ substitutions of the form $s(b) = q_bp$. We do not know whether all
palindromic $x_s$ arise from substitutions that are in this extended class~$\P$."
It turns out that we need to extend a little bit more the class~$\P$ by
including also the conjugates. Blondin Massé
(proof available in \cite[Prop 3.5]{labbe_proprietes_2008}) proved that the
primitive morphism $\tau: a \mapsto abbab, b \mapsto abb$
% \[
% \begin{array}{cccl}
% \tau: & a & \mapsto & abbab\\
%        & b & \mapsto & abb
% \end{array}
% =
% \left(\begin{array}{ccl}
% a&\mapsto&ab \\
% b&\mapsto&b
% \end{array}\right)
% \circ
% \left(\begin{array}{ccl}
% a&\mapsto&ab  \\
% b&\mapsto&a
% \end{array}\right)
% \circ
% \left(\begin{array}{ccl}
% a&\mapsto&ab \\
% b&\mapsto&a
% \end{array}\right)
% \]
generates a fixed point $\bx_\tau$ having an infinite number of palindromes
such that for all $\varphi\neq\Id$ verifying $\varphi(\bx_\tau)=\bx_\tau$, then
$\varphi$ is not in the above extended class~$\P$.
% The proof uses the fact that $\tau$ is a Sturmian morphism so that $\bx_\tau$
% is rigid.
However $\tau$ has a conjugate in class~$\P$. Therefore, the initial question
was reformulated in \cite{labbe_proprietes_2008}.
\begin{conjecture}[Hof, Knill, Simon; Blondin Massé, Labbé]\label{conj:hks_corrige}
Let $\bu$ be the fixed point of a primitive morphism. Then,
$\bu$ is palindromic if and only if there exists a morphism $\varphi\neq\Id$
such that $\varphi(\bu)=\bu$ and $\varphi$ has a conjugate in class~$\P$.
\end{conjecture}
Conjecture~\ref{conj:hks_corrige} has an important application on another
question related to palindromic sequences with finite defect stated in
\cite{MR2566171} also considered in \cite{MR2822202} for uniformly recurrent
words. The conjecture states if the fixed point of a primitive morphism has
a finite and positive defect, then it must be periodic. The question
is still open for fixed point of primitive and injective morphisms since
Bucci and Vaslet \cite{bucci_vaslet_2012} noted that the fixed point of
$a\mapsto aabcacba, b\mapsto aa, c\mapsto a$ is not periodic and has defect $1$.

Partial results on Conjecture~\ref{conj:hks_corrige} have shown that morphisms
preserving palindrome complexity must be in class~$\P$, see \cite{MR2489283}
for more details.
The conjecture was answered positively for the periodic case in
\cite{MR1964623} and for the binary alphabet in
\cite{MR2363365}. This last result is stronger than the conjecture, because it shows
that the square of the morphism has a conjugate in class~$\P$.
\begin{theorem}{\rm\cite{MR2363365}}\label{thm:binary}
Let $\varphi$ be a primitive morphism on a binary alphabet. Then, the fixed
point of $\varphi$ is palindromic if and only if $\varphi^2$ has a conjugate
in class~$\P$.
\end{theorem}
It was also proven independently for uniform morphisms on the binary alphabet
in \cite{labbe_proprietes_2008} using a different approach based on overlap of
factors with a generalization to palindromes fixed by any antimorphism. In
the uniform case for binary alphabet, it appears that conjugate morphisms are
not needed.
\begin{theorem}{\rm\cite{labbe_proprietes_2008}}\label{thm:binaryuniform}
Let $\varphi$ be a uniform primitive morphism on a binary alphabet. Then, the
fixed point of $\varphi$  is palindromic if and only if $\varphi$ or
$\widetilde{\varphi}$ is in class~$\P$ or the image of any letter by
$\varphi^2$ is a palindrome (which means $\varphi^2$ is in class~$\P$).
\end{theorem}

In this article, we show that a result like Theorem~\ref{thm:binary} or
Theorem~\ref{thm:binaryuniform} is not possible beyond the binary alphabet.
Indeed, we show the existence of a primitive morphism having a palindromic
fixed point such that none of its power has a conjugate in class~$\P$
(Lemma~\ref{lem:gammaknoclassP}). We show even more by providing a
counterexample to Conjecture~\ref{conj:hks_corrige} (Theorem~\ref{thm:main}).
We manage to prove such a result by describing explicitly the stabilizer
of a particular infinite sequence $\bx$, i.e., the monoid of morphisms that fix
$\bx$, which is a hard problem in general. We use the properties of symmetric
words, a notion related to class~$\P$ morphisms.
Definitions are in Section 2, the proof of the counterexample is in Section 3.
% The next two sections provides definitions and the proof of the
% counterexample.
% The rest of this article consists of two sections, namely some definitions and
% notations and the proof of the counterexample.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Definitions and notation}

\subsection{Combinatorics on words}

We borrow from M. Lothaire \cite{MR1905123} the basic terminology about words.
In what follows, $\alphabet$ is a finite {\em alphabet} whose elements are
called  {\em letters}. A {\em word} $w$ is a finite sequence of letters
$w=w_0w_1\cdots w_{n-1}$ where $n\in\N$.
The length of $w$ is $|w|=n$ and $w_i$ denotes its $i$-th letter.
By convention the \emph{empty word} is denoted $\varepsilon$ and
its length is $0$.
The set of all finite words over $\alphabet$ is denoted by $\alphabet^*$.
Endowed with the concatenation, $\alphabet^*$ is the \emph{free monoid generated by
$\alphabet$}.
The set of right infinite words is denoted by $\alphabet^{\N}$ and the set of
biinfinite words is $\alphabet^\Z$.
Given a word $w \in \alphabet^*\cup \alphabet^{\N}$,  a \emph{factor} $f$ of $w$ is a word
$f \in \alphabet^*$ satisfying $w = xfy$ for some $x \in \alphabet^*$ and $y
\in \alphabet^*\cup \alphabet^{\N}$.
If $x=\varepsilon$ (resp. $y=\varepsilon$) then $f$ is called 
{\em prefix} (resp. {\em suffix}) of $w$.
The set of all factors of $w$, called the \emph{language} of $w$, is denoted
by $\Fact(w)$.
% ,  and those of length  $n$ is
% $\Fact_n(w) = \Fact(w) \cap \alphabet^n.$ 
%Finally $\Pref(w)$ denotes the set of all prefixes of $w$. 
%The number of occurrences of a factor  $f \in \alphabet^*$ is $|w|_f$. 
% Given a nonempty word $w$, let $\Fst(w)$ and $\Lst(w)$ denote respectively
% the first and last letter of the word $w$.
% An infinite word  $w$ is {\em recurrent} if it satisfies the condition  
% $ u \in \Fact(w) \implies |w|_{u}= \infty \;.$
A word $w$ is {\em primitive} if
it is not a power of another word, that is if $w=u^p$ for some word $u$ and
integer~$p$ then $w=u$ and $p=1$.
% Let $u\in\alphabet^*$. The conjugacy class of $u$ is the set
% \[
% [u] = \{v | \text{ there exists $w$ such that } v w = w u \}
% \]
% The \emph{$k$-th right conjugate} of $u$ is the word $v\in[u]$ such that $v w
% = w u$ and $|w|=k$.
Two words $u$ and $v$ are {\em conjugate} when there are words $x,y$ such that
$u=xy$ and $v=yx$.
A {\em period} of a word $w$ is an integer $p<|w|$ such that $w_i=w_{i+p}$,
for all $i< |w|-p$. We recall the result of Fine and Wilf for doubly periodic
words \cite[Theorem 8.1.4]{MR1905123}.
\begin{lemma}[Fine and Wilf]\label{lem:finewilf}
Let $w$ be a word having period $p$ and $q$. If
$|w|\geq p+q-\gcd(p,q)$, then $\gcd(p,q)$ is also a period of $w$.
\end{lemma}
The {\em reversal} of
$w = w_0w_1 \cdots w_{n-1} \in\alphabet^n$ is the word $\til{\,w\,}=w_{n-1}
w_{n-2}\cdots w_0$.  A {\em palindrome} is a word $w$ such that $
w=\til{\,w\,}$. An infinite sequence $\bw$ is \emph{palindromic} if its
language $\L(\bw)$ contains arbitrarily long palindromes.

The set of palindrome factors of a word $w$ is
$\Pal(w)=\{p\in\L(w):\til{p}=p\}$.
It is known \cite{droubay_episturmian_2001}
that $|\Pal(w)| \leq |w| + 1$ for all finite word $w\in\alphabet^*$.
The \emph{defect} $D(w)$ \cite{bhnr} of a finite word $w$ is the difference
between the maximal number of palindromes that it may contain and the number
of palindromes that it contains: $D(w) = |w| + 1 - |\Pal(w)|$.
The defect of a infinite word $\bw$ is
$D(\bw) = \sup_{w \in \Fact(\bw)} D(w)$; it may be finite or infinite. A finite or infinite
word $w$ is \emph{full} or \emph{rich} if $D(w)=0$.

\subsection{Symmetric words}

%Reflexion in a point:
%\url{https://en.wikipedia.org/wiki/Point_reflection}
A word $w=w_0w_1\cdots w_{n-1}$ is \emph{symmetric} if it is the product of
two palindromes if and only if there exists an integer $a\in[0,n-1]$ such that
\[
w_{a-i} = w_i \quad\text{for all integer $i\in [0,n-1]$}
\]
where the indices are taken modulo $n$. We say that the
integer $a$ is a \emph{point of symmetry} of the word~$w$.
For example, the integer $6$ is the unique point of symmetry of the word
$w=abcdcbaxyzzyx$. In the table below, we verify that
$w_{6-i} = w_i$ for all integer $i\in[0,12]$:
\[
\begin{array}{c|ccccccccccccc}
i   & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\
\hline
w_i & a & b & c & d & c & b & a & x & y & z & z & y & x\\
6-i & 6 & 5 & 4 & 3 & 2 & 1 & 0 & 12 & 11 & 10 & 9 & 8 & 7\\
w_{6-i} & a & b & c & d & c & b & a & x & y & z & z & y & x
\end{array}
\]
The proofs of the following lemmas are easy.
\begin{lemma}\label{lem:basicpointofsymmetry}
A finite $w$ word has a point of symmetry at $a$ if and only if $w=pq$ for some
palindromes $p$ and $q$ such that $|p|=a+1$.
\end{lemma}

\begin{lemma}\label{lem:conjugatesymmetric}
Let $w$ and $w'$ be two conjugate words, i.e., $uw = w'u$ for some word $u$.
If $w$ has a point of symmetry at $a$, then $w'$ has a point of symmetry at
$a+2|u|\mod |w|$.
\end{lemma}

\begin{lemma}\label{lem:twopoints}
If a finite word $w$ has two points of symmetry $a$ and $b$, then $gcd(b-a,|w|)$
is a period of $w$. In particular, $w$ is not primitive.
\end{lemma}

\begin{proof}
Let $\bw=\cdots ww.www\cdots = \cdots w_{n-1}.w_0w_1\cdots\in\alphabet^\Z$ be
the biinfinite word such that the index $0$ of both $\bw$ and $w$ coincide.
The fact that $w$ has two points of symmetry $a$ and $b$ translates into the
fact that $\bw_{a-i} = \bw_{b-i} = \bw_i$ for all $i \in \Z$.
Then $\bw_{i} = \bw_{a-i} = \bw_{b-(a-i)} = \bw_{i+(b-a)}$ for all $i\in\Z$.
Therefore, both $|w|$ and $b-a$ are periods of $\bw$.
We conclude by Lemma~\ref{lem:finewilf} that $gcd(b-a,|w|)$
is a period of $\bw$ and of $w$.
\end{proof}

\subsection{Morphisms}

A {\em morphism} is a function $\varphi : \alphabet^* \to \alphabet^*$
compatible with concatenation, that is, such that $\varphi (uv)= \varphi(u)
\varphi (v)$ for all $u,v \in \alphabet^*$. 
The \emph{identity morphism} on $\alphabet$ is denoted by $\Id_\alphabet$ or
simply $\Id$ when the context is clear.
A morphism $\varphi$ is \emph{primitive} if
there exists an integer $k$
such that for all $\alpha\in\alphabet$,
$\varphi^k(\alpha)$ contains each letter of $\alphabet$.
% For $\alpha \in \alphabet$ we call {\em $\varphi$-block} (block for short if
% no confusion arises) a factor of the form $\varphi(\alpha)$. 
A morphism is called {\em uniform} when $|\varphi(\alpha)|=|\varphi(\beta)|$
for all letters $\alpha,\beta\in\alphabet$.
A morphism also extends in a natural way to a map over $\alphabet^\N$.
% The \emph{language} of a morphism $\varphi$ is denoted $\L(\varphi)$. This is not
% ambiguous as we consider primitive morphisms. Also
% $\Pal(\varphi)=\{w\in\L(\varphi)| w = \widetilde{w} \}$ denotes the set of
% palindromes in the language.
The set of \emph{sturmian morphisms} is \cite{MR1265903} the monoid generated
by
\[
\left\{
\begin{array}{ccl}
a & \mapsto & ab\\
b & \mapsto & a
\end{array},
\quad\quad
\begin{array}{ccl}
a & \mapsto & ba\\
b & \mapsto & a
\end{array},
\quad\quad
\begin{array}{ccl}
a & \mapsto & b\\
b & \mapsto & a
\end{array}
\right\}.
\]
A subset $X$ of the free monoid $\alphabet^*$ is a \emph{code} if there
exists an injective morphism $\beta: \mathcal B^*\to \alphabet^*$ such that $X
= \beta(\mathcal B)$.

Recall from Lothaire \cite{MR1905123} (Section 2.3.4)
that $\varphi$ is \emph{right conjugate} of $\varphi'$,
or that $\varphi'$ is \emph{left conjugate} of $\varphi$,
noted $\varphi\triangleleft\varphi'$, if
there exists $w \in \alphabet^*$ such that
\begin{equation}
\varphi(x)w = w\varphi'(x), \quad \textrm{for all words } x \in \alphabet^*, \label{FirstCond}
\end{equation}
or equivalently that
$\varphi(\alpha)w = w\varphi'(\alpha)$, for all letters $\alpha \in \alphabet$.
Clearly, this relation is not symmetric so that we say that two
morphisms $\varphi$ and $\varphi'$ are \emph{conjugate},
%noted $\varphi\bowtie\varphi'$,
if $\varphi\triangleleft\varphi'$ or $\varphi'\triangleleft\varphi$.  It is
easy to see that conjugacy of morphisms is an equivalence relation.

A morphism is \emph{erasing} if the image of at least one of the letters is the
empty word.
If $\varphi$ is a nonerasing morphism, we define
$\Fst(\varphi):\alphabet\to\alphabet$ to be the
function defined by $\Fst(\varphi)(a)$ is the first letter of $\varphi(a)$.
Similarly, let $\Lst(\varphi):\alphabet\to\alphabet$ be the
function defined by $\Lst(\varphi)(a)$ is the last letter of $\varphi(a)$.
% Note that we have
% \[
% \Fst(\varphi\circ\mu) = \Fst(\varphi) \circ \Fst(\mu)
% \quad \quad
% \text{and}
% \quad \quad
% \Lst(\varphi\circ\mu) = \Lst(\varphi) \circ \Lst(\mu).
% \]

%\todo{define incidence matrix}

A morphism $\varphi$ is \emph{prolongable at $a$} if there is a letter $a$
such that $\varphi(a) = aw$ where $w$ is a nonempty word $w$.
If $\varphi$ is prolongable at $a$, then
\[
\bw = a w \varphi(w) \varphi(\varphi(w)) \cdots \varphi^{n}(w) \cdots
\]
is a \emph{purely morphic word}. It is also a \emph{fixed point} of
$\varphi$, i.e., $\varphi(\bw)=\bw$.
A \emph{morphic word} is the image of a pure morphic word under a morphism.

The \emph{mirror-image} of a morphism $\varphi$, denoted by $\til{\varphi}$,
is the morphism such that $\til{\varphi}(\alpha) = \til{\varphi(\alpha)}$ for
all $\alpha \in \alphabet$.
A morphism $\varphi$ is in \emph{class~$\P$} if there exists a palindrome $p$
and for every $\alpha \in \alphabet$ there exists a palindrome $q_\alpha$ such
that $\varphi(\alpha)=pq_\alpha$. The mirror-image $\til{\varphi}$ of a
morphism $\varphi$ in class~$\P$ is conjugate to $\varphi$.
If a morphism has a conjugate in class~$\P$, then the image of the letters are
symmetric and they all share a common symmetry point which is quite demanding
as we will see.

\begin{lemma}
If $\varphi$ has a conjugate in class~$\P$, then there exists an integer
$a\in\N$ such that for all $\alpha\in\alphabet$, $\varphi(\alpha)$ is
symmetric with a point of symmetry at $a \mod |\varphi(\alpha)|$.
\end{lemma}

\begin{proof}
Let $\varphi'$ in class~$\P$ be the conjugate of $\varphi$.
Let $p$ and $q_\alpha$ be the palindromes such that
$\varphi'(\alpha)=pq_\alpha$.
Then for all letters $\alpha$, $\varphi'(\alpha)$ has a point of symmetry at
$|p|-1$ (Lemma~\ref{lem:basicpointofsymmetry}). The result follows from
Lemma~\ref{lem:conjugatesymmetric}.
\end{proof}




\subsection{Stabilizer}

The \emph{stabilizer} of a right-infinite word $\bw$ over a finite alphabet
$\alphabet$, denoted by $\Stab(\bw)$, is the monoid of morphisms
$f:\alphabet^*\to\alphabet^*$ that satisfy $f(\bw)=\bw$. Its unit element is the
identity morphism. Words that have a cyclic stabilizer are called \emph{rigid}.
See \cite{MR2543346,MR2424350} for a discussion on the subject and
\cite{MR2901382} for a recently completed proof of the rigidity of
words generated by sturmian morphisms.
\begin{proposition}{\rm\cite{MR1603835,MR2901382}}
Sturmian words generated by sturmian morphisms are rigid.
\end{proposition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The counterexample}

Let $\alphabet=\{a,b,c\}$ and $\gamma:\alphabet^*\to\alphabet^*$ be defined by
\[
\gamma:a\mapsto aca, b\mapsto cab, c\mapsto b.
\]
Let $\bx_\gamma$ be the fixed point of $\gamma$ starting with letter $a$:
% sage: m = WordMorphism('a->aca,b->cab,c->b')
% sage: m('a',oo)
% word: acabacacabacabacabacacabacabacacabacabac...
\[
\bx_\gamma = acabacacabacabacabacacabacabacacabacabac \cdots
\]
In this section, we show that $\bx_\gamma$ is a counterexample to
Conjecture~\ref{conj:hks_corrige}. More precisely, we prove the following
result.
\begin{theorem}\label{thm:main}
The fixed point $\bx_\gamma$ of the primitive morphism $\gamma$ is
palindromic, but none of the morphisms
$\varphi\in\Stab(\bx_\gamma)\setminus\{\Id\}$ has a conjugate in class~$\P$.
\end{theorem}

\subsection{$\bx_\gamma$ is palindromic}

First, we show that the sequence $\bx_\gamma$ is palindromic.
Let $(p_k)_k$ be the sequence of finite words defined recursively by
\begin{equation}
p_{-1}=a^{-1},
\quad
p_0=b
\quad\text{and}\quad
p_{k+1}=\gamma(cap_k) \quad\text{for each}\quad k>0.
\end{equation}
The first terms are $p_0=b$, $p_1=bacacab$ and $p_2=bacacabacabacabacacab$;
these three words are palindromes.
Also, the first letter of $p_k$ is $b$ for each $k\geq0$.
The next lemma shows that $(p_k)_k$ is a sequence of palindromes. Moreover,
$p_{k}\,aca\,p_{k-1}$ is not a palindrome only because it contains
the centered factor $cab$ or $bac$ (the rest is perfectly symmetric with
respect to the center).


\begin{lemma}\label{lem:pk}
For all $k\geq0$, the following statements are verified:
\begin{enumerate}[\rm (i)]
\item $p_{k+1} = p_{k}\, aca\, p_{k-1}\, aca\, p_k$;
\item $p_{k}$ is a palindrome;
\item $p_{k-1}\,aca\,p_{k}$ is not a palindrome.
\end{enumerate}
\end{lemma}

\begin{proof}
(i)
Notice that $p_1=p_0\cdot aca\cdot p_{-1}\cdot aca\cdot
p_0=bacaa^{-1}acab=bacacab$ and $p_2=p_1\cdot aca\cdot p_0\cdot aca\cdot p_1$.
Suppose that $p_{k}=p_{k-1}\cdot aca\cdot p_{k-2}\cdot aca\cdot p_{k-1}$, for
some $k\geq 2$.
Then,
\begin{eqnarray*}
p_{k+1}
&=& \gamma(ca p_k) \\
&=& \gamma(ca\, p_{k-1}\, aca\, p_{k-2}\, aca\, p_{k-1})\\
&=& \gamma(ca p_{k-1})\, \gamma(a)\, \gamma(ca p_{k-2})\, \gamma(a)\, \gamma(ca p_{k-1}) \\
&=& p_{k}\, aca\, p_{k-1}\, aca\, p_k.
\end{eqnarray*}

(ii) We remark that $p_0$ and $p_1$ are palindromes. Also, from (i), if
$p_{k-1}$ and $p_k$ are palindromes, then $p_{k+1}$ is a palindrome.
Therefore $p_{k}$ is a palindrome for all $k\geq 0$.

(iii)
First, $p_{-1}\,aca\,p_0=a^{-1}acab=cab$ and $p_0\,aca\,p_1=bacabacacab$ are
not palindromes.
Suppose $p_{k-1}\,aca\,p_{k}$ is not a palindrome for some $k\geq 1$.
Then $p_{k}\,aca\,p_{k+1}=p_{k}\,aca\,p_{k}\,aca\,p_{k-1}\,aca\,p_{k}$ is a
palindrome if and only if the middle part $p_{k}\,aca\,p_{k-1}$ is a
palindrome. But, it is not being the reversal of $p_{k-1}\,aca\,p_{k}$.
\end{proof}

\begin{lemma}\label{lem:infty}
$\bx_\gamma$ is palindromic.
\end{lemma}

\begin{proof}
We show that for each $k\geq0$, the word $p_k$ shown to be palindrome at
Lemma~\ref{lem:pk} is included in $\L(\bx_\gamma)$.
Note that the first letter of $p_k$ is $b$ for each $k\geq0$.
Since each letter $b$ is preceded by the factor $ca$ in the language of
$\bx_\gamma$, we conclude that if $p_k\in\L(\bx_\gamma)$, then
$cap_k\in\L(\bx_\gamma)$ so that $p_{k+1}=\gamma(cap_k)\in\L(\bx_\gamma)$.
Therefore, $p_k\in\L(\bx_\gamma)$ for all $k\geq0$.
\end{proof}

Note that the previous two results are quite interesting. For a morphism
$\varphi:\alpha\mapsto pq_\alpha$ in class~$\P$, one shows that if $w$ is a
palindrome, then $\varphi(w)p$ is also a palindrome. Here, the result says
that prepending the non-palindromic word $baca$ to $\gamma(p_k)$ makes it a
new longer palindrome. This is a first indication that $\bx_\gamma$ contains
an infinite number of palindromes for a different reason than for well known
fixed point of class~$\P$ morphisms.

\subsection{The stabilizer of $\bx_\gamma$}

In this section, we describe exactly the stabilizer $\Stab(\bx_\gamma)$ of the
sequence $\bx_\gamma$. This is a hard problem in general.
Over a ternary alphabet, the monoid of morphisms generating a given infinite
word by iteration can be infinitely generated \cite{MR2424350}.
To achieve this, we show that the purely morphic sequence $\bx_\gamma$ defined
above is equal to the morphic sequence $\pi(\bw_\mu)$ where
\[
\mu\left\{
\begin{array}{l}
x \mapsto xy\\
y \mapsto xxy
\end{array}\right.,
\quad\quad
\quad\quad
\pi\left\{
\begin{array}{l}
x \mapsto ac\\
y \mapsto ab
\end{array}\right.
\]
and $\bw_\mu$ is the infinite fixed point of $\mu$ starting with letter $x$:
% sage: mu = WordMorphism('x->xy,y->xxy')
% sage: mu.fixed_point('x')
% word: xyxxyxyxyxxyxyxxyxyxxyxyxyxxyxyxxyxyxyxx...
\[
\bw_\mu = xyxxyxyxyxxyxyxxyxyxxyxyxyxxyxyxxyxyxyxx \ldots
\]
%Let
%\[
%\pi:x\mapsto ac, y\mapsto ab.
%\]
The finite prefix of $\bx_\gamma$ shown earlier seems to indicate that the
letter $a$ appears exactly at the even positions and that $b$ and $c$ letters
appears at odd positions. This can be formulated by saying that $\bx_\gamma$
is the image by the morphism $\pi$ of some infinite word over $\{x,y\}$. The
next lemma shows that this infinite word is unique and is $\bw_\mu$.


\begin{lemma}\label{lem:corresondancexw}
We have $\gamma\circ\pi = \pi\circ\mu$.
There exists a unique infinite word $\bw$ such that
$\bx_\gamma=\pi(\bw)$. Moreover, $\bw=\bw_\mu$.
\end{lemma}

\begin{proof}
First, we verify that $\gamma\circ\pi = \pi\circ\mu$. It is sufficient to
check it for letters:
\[
\begin{array}{c}
\gamma(\pi(x))=\gamma(ac)=acab = \pi(xy)=\pi(\mu(x)),\\
\gamma(\pi(y))=\gamma(ab)=acacab = \pi(xxy)=\pi(\mu(y)).
\end{array}
\]
The word $\bx_\gamma$ is an infinite product of two kinds of blocks of length
$2$ namely $ac$ and $ab$.
Since $\{ac, ab\}$ is a code,
there exists a unique infinite word $\bw$ such that
$\pi(\bw)=\bx_\gamma$. But, using $\gamma\circ\pi = \pi\circ\mu$, we get
\[
\bx_\gamma = \gamma(\bx_\gamma) = \gamma(\pi(\bw)) = \pi(\mu(\bw)).
\]
From the injectivity of $\pi$ we conclude that $\bw=\mu(\bw)$ is a fixed
point of $\mu$, i.e., $\bw=\bw_\mu$.
\end{proof}

\begin{lemma}\label{lem:oddoreven}
Let $\varphi\in\Stab(\bx_\gamma)$.
Then, $|\varphi(a)|$, $|\varphi(b)|$ and $|\varphi(c)|$ are all odd or all
even.
\end{lemma}
\begin{proof}
We have that $\varphi(a)$ is a prefix of $\bx_\gamma$ and it must start with
$a$. Therefore, $\varphi(b)$ and $\varphi(c)$ both do not end with $a$.

If $|\varphi(a)|$ is odd, then $\varphi(a)$ ends with letter $a$, $\varphi(c)$
does not start with letter $a$ so that $|\varphi(c)|$ is odd. Then
$|\varphi(aca)|$ is odd and hence $\varphi(b)$ does not start with letter $a$
from what we get that $|\varphi(b)|$ is odd as well.

If $|\varphi(a)|$ is even, then $\varphi(a)$ does no end with letter $a$, $\varphi(c)$
starts with letter $a$ so that $|\varphi(c)|$ is even. Then
$|\varphi(aca)|$ is even and hence $\varphi(b)$ starts with letter $a$
from what we get that $|\varphi(b)|$ is even as well.
\end{proof}

\noindent
The morphism $\mu$ is sturmian being factorized as $\mu=(x\mapsto xy,y\mapsto
x)\circ(x\mapsto x,y\mapsto yx)$.
Therefore, the sequence $\bw_\mu$ is rigid. This is what allows us to describe
exactly the stabilizer of~$\bx_\gamma$.

\begin{proposition}\label{prop:stab}
$\Stab(\bx_\gamma) = \{\varphi :\text{there exists an integer $k$ such
that }\varphi\circ\pi = \gamma^k\circ\pi\}$.
\end{proposition}

\begin{proof}
Let $\varphi\in\Stab(\bx_\gamma)$.
From Lemma~\ref{lem:oddoreven}, $\varphi(ac)$ and $\varphi(ab)$ both have
even length. Therefore, there exist words $u,v\in\{x,y\}^*$ such that
$\varphi(\pi(x)) = \varphi(ac) = \pi(u)$ and
$\varphi(\pi(y)) = \varphi(ab) = \pi(v)$.
Since the image of the alphabet by $\pi$ is a code, the words $u$ and $v$ are
uniquely determined. Hence, let $\sigma:x\mapsto u,y\mapsto v$. We have that
$\varphi\circ\pi=\pi\circ\sigma$.
From Lemma~\ref{lem:corresondancexw}, $\bx_\gamma=\pi(\bw_\mu)$. We get
\[
\bx_\gamma = \varphi(\bx_\gamma) = \varphi(\pi(\bw_\mu)) = \pi(\sigma(\bw_\mu)).
\]
From the injectivity of $\pi$, we get that
$\bw_\mu=\sigma(\bw_\mu)$, that is $\sigma\in\Stab(\bw_\mu)$.
Since the fixed point $\bw_\mu$ is sturmian and rigid, more precisely
$\Stab(\bw_\mu)=\langle\mu\rangle$, there exists an integer $k$ such that
$\sigma=\mu^k$. Finally, from Lemma~\ref{lem:corresondancexw}, we have
$\pi\circ\mu^k = \gamma^k\circ\pi$.
Thus, $\varphi\circ\pi=\pi\circ\sigma = \pi\circ\mu^k = \gamma^k\circ\pi$.

Reciprocally, suppose $\varphi$ is such that $\varphi\circ\pi =
\gamma^k\circ\pi$. Then,
\[
\varphi(\bx_\gamma) = \varphi(\pi(\bw_\mu)) = \gamma^k(\pi(\bw_\mu)) =
\gamma^k(\bx_\gamma) = \bx_\gamma.
\]
Thus, $\varphi\in\Stab(\bx_\gamma)$.
\end{proof}

In other words, $\varphi\in\Stab(\bx_\gamma)$ if and only if
$\varphi\in S_k$ for some integer $k\geq 0$
where
\[
S_k = \{\varphi:\varphi(ab)=\gamma^k(ab)\text{ and
}\varphi(ac)=\gamma^k(ac)\}.
\]
The cardinality of the set $S_k$ is equal to the number of common prefixes of
$\gamma^k(ab)$ and $\gamma^k(ac)$, i.e., $\Card S_k = |\gamma^k(a)|+1$.
The first values of this sequence can be computed easily:
\[
\begin{array}{c|cccccccccccccc}
k         & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
\Card S_k & 2 & 4 & 8 & 18 & 42 & 100 & 240 & 578 & 1394 & 3364\\
\end{array}
\]
We have $\varphi\in S_0$ if and only if $\varphi=a\mapsto\emptyword,b\mapsto
ab,c\mapsto ac$ or $\varphi$ is the identity morphism.
If $\varphi\in S_1$, then $\varphi$ is one of the following four morphisms:
\[
\gamma_0\left\{
\begin{array}{l}
a \mapsto \emptyword\\
b \mapsto acacab\\
c \mapsto acab
\end{array}\right.,\quad
\gamma_1\left\{
\begin{array}{l}
a \mapsto a\\
b \mapsto cacab\\
c \mapsto cab
\end{array}\right.,\quad
\gamma_2\left\{
\begin{array}{l}
a \mapsto ac\\
b \mapsto acab\\
c \mapsto ab
\end{array}\right.,\quad
\gamma=\gamma_3\left\{
\begin{array}{l}
a \mapsto aca\\
b \mapsto cab\\
c \mapsto b
\end{array}\right..
\]
The indices for $\gamma$ are chosen according to the length of the image of
$a$.
If $\varphi\in S_2$, then $\varphi$ is one of the following eight morphisms:
\[
\gamma_0^2\left\{
\begin{array}{l}
a \mapsto \emptyword\\
b \mapsto acabacabacacab\\
c \mapsto acabacacab
\end{array}\right.,
\gamma_1^2\left\{
\begin{array}{l}
a \mapsto a\\
b \mapsto cabacabacacab\\
c \mapsto cabacacab
\end{array}\right.,
\gamma_2\gamma_1\left\{
\begin{array}{l}
a \mapsto ac\\
b \mapsto abacabacacab\\
c \mapsto abacacab
\end{array}\right.,
\]
\[
\gamma_3\gamma_1\left\{
\begin{array}{l}
a \mapsto aca\\
b \mapsto bacabacacab\\
c \mapsto bacacab
\end{array}\right.,
\gamma_2^2\left\{
\begin{array}{l}
a \mapsto acab\\
b \mapsto acabacacab\\
c \mapsto acacab
\end{array}\right.,
\gamma_1\gamma_3\left\{
\begin{array}{l}
a \mapsto acaba\\
b \mapsto cabacacab\\
c \mapsto cacab
\end{array}\right.,
\]
\[
\gamma_2\gamma_3\left\{
\begin{array}{l}
a \mapsto acabac\\
b \mapsto abacacab\\
c \mapsto acab
\end{array}\right.,
\gamma_3^2\left\{
\begin{array}{l}
a \mapsto acabaca\\
b \mapsto bacacab\\
c \mapsto cab
\end{array}\right..
\]
In this case, we have $(S_1)^2 = S_2$.
However, this is not true in general as
$(S_1)^3 \subsetneq S_3$.
In other words, $S_1=\{\gamma_0, \gamma_1, \gamma_2, \gamma_3\}$ do not form a set of
generators for $\Stab(\bx_\gamma)$.
In fact, $\Card(S_1)^3=16$ but $\Card S_3=18$. The two elements of
$S_3\setminus(S_1)^3$ are
% sage: gamma3 = WordMorphism('a->aca,b->cab,c->b')
% sage: gamma2 = WordMorphism('a->ac,b->acab,c->ab')
% sage: gamma1 = WordMorphism('a->a,b->cacab,c->cab')
% sage: gamma0 = WordMorphism('a->,b->acacab,c->acab')
% sage: G = [gamma0,gamma1,gamma2,gamma3]
% sage: D = set(pseudo_conjugates(gamma3^3)) - set(prod(m) for m in itertools.product(G,G,G))
% sage: for m in D: print m
% WordMorphism: a->acabacac, b->abacabacacabacabacabacacab, c->abacabacabacacab
% WordMorphism: a->acabacaca, b->bacabacacabacabacabacacab, c->bacabacabacacab
\[
\begin{array}{l}
a\mapsto acabacac, b\mapsto abacabacacabacabacabacacab, c\mapsto abacabacabacacab,\\
a\mapsto acabacaca, b\mapsto bacabacacabacabacabacacab, c\mapsto bacabacabacacab.
\end{array}
\]

% \begin{lemma}
% $\langle \gamma_0, \gamma_1\gamma_2, \gamma_3
% \rangle=\gamma_2^*\{\gamma_1,\gamma_3\}^*\cup\gamma_0^*$
% \end{lemma}
% \begin{proof}
% This follows from the fact that $\gamma_3\gamma_2=\gamma_2^2$.
% \end{proof}

\subsection{Proof of Theorem~\ref{thm:main}}

Before proving the theorem, we show that the powers of $\gamma$ itself do not
have any conjugate in class~$\P$. This implies that results like
Theorem~\ref{thm:binary} or Theorem~\ref{thm:binaryuniform} are not possible
beyond the binary alphabet.

\begin{lemma}\label{lem:gammaknoclassP}
For all $k\geq1$, $\gamma^k$ does not have any conjugate in class~$\P$.
\end{lemma}

\noindent
In the following  proof, if $\varphi$ is a morphism on $\alphabet^*$ with
$\alphabet=\{a,b,c\}$, we represent the function
$f=\Fst(\varphi):\alphabet\to\alphabet$ as an ordered tuple $(f(a), f(b),
f(c))$ and similarly for $\Lst(\varphi):\alphabet\to\alphabet$.

\begin{proof}
We have that $\Fst(\gamma^k)=(a,b,c)$ for all even $k$ and
$\Fst(\gamma^k)=(a,c,b)$ for all odd~$k$.
Also $\Lst(\gamma^k)=(a,b,b)$ for all $k$.
Since none of these functions is constant, $\gamma^k$ does not have conjugates
other than itself.
For the same reason, the image of each letter by
$\gamma^k$ must be a palindrome in order to be in class~$\P$. But it is not
the case since $\Fst(\gamma^k)\neq\Lst(\gamma^k)$ for all~$k$.
\end{proof}

\noindent
We show that the words $\gamma^k(ab)$ and $\gamma^k(ac)$ are symmetric with
distinct points of symmetry.
\begin{lemma}\label{lem:points_symmetry}
We have
\begin{enumerate}[\rm (i)]
\item $\gamma^k(ab) = aca\,p_{k-2}\,aca\,p_{k-1}$ is a symmetric word with
a point of symmetry at $|p_{k-2}| + 5$ for all $k\geq 2$,
\item $\gamma^k(ac) = aca\,p_{k-1}$ is a symmetric word with
a point of symmetry at $2$ for all $k\geq 1$,
\end{enumerate}
\end{lemma}

\begin{proof}
(i) We have 
\[
\gamma^2(ab)=aca\,b\,aca\,bacacab=aca\,p_0\,aca\,p_1.
\]
Suppose
$\gamma^k(ab) = aca\,p_{k-2}\,aca\,p_{k-1}$ for some $k\geq2$.  Then
\begin{align*}
\gamma^{k+1}(ab) = \gamma(\gamma^k(ab))
&= \gamma(aca\,p_{k-2}\,aca\,p_{k-1})\\
&= \gamma(a) \gamma(cap_{k-2})\gamma(a) \gamma(cap_{k-1})
= aca\, p_{k-1}\, aca\, p_{k}.
\end{align*}

(ii)
We verify $\gamma(ac)=acab=aca\,p_0$.
Suppose $\gamma^k(ac) = aca\,p_{k-1}$ for some $k\geq 1$.
Then
\[
\gamma^{k+1}(ac) = \gamma(\gamma^k(ac))
= \gamma(aca\,p_{k-1})
= \gamma(a) \gamma(cap_{k-1})
= aca\, p_{k}.\qedhere
\]
\end{proof}

\noindent
We also need the property that the words $\gamma^k(ab)$ and
$\gamma^k(ac)$ are primitive. This is a consequence of the more general
following result showing that $\mu$ preserves primitivity as well as $\gamma$
under some extra conditions.
\begin{lemma}\label{lem:primitivity}
We have
\begin{enumerate}[\rm (i)]
\item for all $w\in\{x,y\}^*$, $\mu(w)$ is primitive if and only if $w$ is primitive,
\item for all $w\in\pi\left(\{x,y\}^*\right)$, $\gamma(w)$ is primitive if and only if $w$ is primitive,
\end{enumerate}
\end{lemma}
\begin{proof}
(i) $(\implies)$ If $w$ is not primitive, it can be written as $w=u^p$ for
some word $u$ and integer $p\geq2$. Therefore, $\mu(w)=\mu(u^p)=\mu(u)^p$ is
not primitive.
$(\impliedby)$ If $\mu(w)$ is not primitive, there exist a word $u$ and an
integer $p\geq2$ such that $\mu(w)=u^p$. Then $u$ starts with the letter $x$
and ends with letter $y$. Therefore, $u$ can be desubstituted uniquely as
$u=\mu(v)$ for some word $v$. We get $\mu(w)=u^p=\mu(v)^p=\mu(v^p)$. From the
fact that the letter images of $\mu$ is a prefix code, we get that $w=v^p$
and $w$ is not primitive.

(ii) $(\implies)$ The proof is the same as in (i).
$(\impliedby)$ If $\gamma(w)$ is not primitive, there exist a word $u$ and an
integer $p\geq2$ such that $\gamma(w)=u^p$. The last letter of $u$ must be $b$
and the first letter of $u$ must be $a$. Hence, $u$ can be written as the
image under $\gamma$ of some word $v$. The word $v$ is unique because the
images of letters by $\gamma$ is a prefix code. We get
$\gamma(w)=u^p=\gamma(v)^p=\gamma(v^p)$ and thus $w=v^p$ because $\gamma$
forms a code. Then, $w$ is not primitive.
\end{proof}


\noindent
We have now gathered enough information to prove the main result.
\begin{proposition}\label{prop:noconjuclassP}
If $\varphi\in\Stab(\bx_\gamma)\setminus\{\Id\}$, then $\varphi$ does not
have a conjugate in class~$\P$.
\end{proposition}

\begin{proof}
Let $\varphi\in\Stab(\bx_\gamma)$.
From Proposition~\ref{prop:stab}, we have that $\varphi(ab)=\gamma^k(ab)$ and
$\varphi(ac)=\gamma^k(ac)$ for some integer $k$.
We may suppose that $k\geq1$ since $\varphi$ is not the identity.
Suppose by contradiction that $\varphi$ has a conjugate in class~$\P$.
We may assume that $k\geq2$ since we may check that none of
$\gamma_0$, $\gamma_1$, $\gamma_2$, $\gamma_3$
defined above have a conjugate in class~$\P$.
This means that there exist a word $w$ and palindromes $q$, $p_a$, $p_b$ and
$p_c$ such that
\[
\begin{array}{l}
w\,p_aq = \varphi(a)\,w,\\
w\,p_bq = \varphi(b)\,w,\\
w\,p_cq = \varphi(c)\,w,
\end{array}
\quad\quad
\text{or}
\quad\quad
\begin{array}{l}
p_aq\,w = w\,\varphi(a),\\
p_bq\,w = w\,\varphi(b),\\
p_cq\,w = w\,\varphi(c).
\end{array}
\]
Therefore $\varphi(ab)$ and $\varphi(ac)$ are symmetric words with the same
axis of symmetry. Indeed, from the equations above we get that
$\varphi(ab)$ and $\varphi(ac)$ are conjugate to symmetric words having a
point of symmetry at $|p_a|-1$ (Lemma~\ref{lem:basicpointofsymmetry}):
\[
\begin{array}{c}
\varphi(ab)\cdot w = w\cdot p_aqp_bq,\\
\varphi(ac)\cdot w = w\cdot p_aqp_cq.
\end{array}
\quad\quad
\text{or}
\quad\quad
\begin{array}{c}
w\cdot \varphi(ab) = p_aqp_bq\cdot w,\\
w\cdot \varphi(ac) = p_aqp_cq\cdot w.
\end{array}
\]
From Lemma~\ref{lem:conjugatesymmetric}, $\varphi(ab)$ and $\varphi(ac)$ both
have a point of symmetry at $A= |p_a|-1+2|w|$ or at $A=|p_a|-1-2|w|$.
From Lemma~\ref{lem:points_symmetry}, $\varphi(ab)$ already has a point of
symmetry at $|p_{k-2}|+5$. If $A\neq|p_{k-2}|+5$,
then $\varphi(ab)$ has two distinct points of symmetry.  Then, $\varphi(ab)$ is
periodic with period $g$ where $g$ is a divisor of $|\varphi(ab)|$
(Lemma~\ref{lem:twopoints}). Therefore,
$\varphi(ab)$ is not primitive which is a contradiction.
From Lemma~\ref{lem:primitivity}, $\varphi(ab)$ is
primitive because from the beginning $ab$ is a primitive word.

If $A=|p_{k-2}|+5$, then $2$ and $A$ are two distinct points of symmetry of
$\varphi(ac)$. We can get a contradiction using a primitivity argument as
above, but also using an argument based on palindromes. We have
\[
\varphi(ac)=aca\,p_{k-1}=aca\,p_{k-2}\,aca\,p_{k-3}\,aca\,p_{k-2}
\]
from Lemma~\ref{lem:points_symmetry}. A point of symmetry at $A=|p_{k-2}|+5$ implies that
$p_{k-3}acap_{k-2}$ is a palindrome which is a contradiction with
Lemma~\ref{lem:pk} (iii).  We conclude that none of the conjugate of
$\varphi$ are in class~$\P$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Follows from Lemma~\ref{lem:infty} and Proposition~\ref{prop:noconjuclassP}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

We have seen that the fixed point $\bx_\gamma$ of $\gamma$ is not rigid. It is
still open to show that its stabilizer is not finitely generated. We have
shown that the infinite sequence $\bx_\gamma$ is palindromic but none of the
morphisms that stabilizes it have a conjugate in class~$\P$. This is thus a
counterexample to Conjecture~\ref{conj:hks_corrige} which was considered for a
long time as the interpretation of the question of Hof, Knill and Simon.

% sage: gamma = WordMorphism('a->aca,b->cab,c->b')
% sage: m = matrix(gamma)
% sage: latex(m.charpoly().factor())
% (x - 1) \cdot (x^{2} - 2x - 1)
% sage: mu = WordMorphism('x->xy,y->xxy')
% sage: m = matrix(mu)
% sage: m.charpoly()
% x^2 - 2*x - 1
The characteristic polynomial of the incidence matrix of $\gamma$ is not
irreducible as it factorizes as $(x - 1) \cdot (x^{2} - 2x - 1)$.
Note that $x^{2} - 2x - 1$ is the characteristic polynomial of the incidence
matrix of $\mu$. It is still an open question whether there exists a
counterexample to Conjecture~\ref{conj:hks_corrige} such that the
characteristic polynomial is irreducible, or if there exists a
counterexample that is not the image on a larger alphabet of a purely morphic
word.

Note that $\gamma_0:a\mapsto\emptyword, b\mapsto acacab, c\mapsto acab$ is
almost in class~$\P$. This leads to think that the question of Hof,
Knill and Simon could be fixed once more by including erasing morphisms such
that their nonerasing part has a conjugate in class~$\P$. More investigations
need to be done here to find a proper statement of the original question
of Hof, Knill and Simon.

Recent work \cite{harju_remark_2013} was done in that direction motivated by
our counterexample suggesting that the good interpretation of the question of
Hof, Knill and Simon should be that if $\bu$ is a primitive morphic word and
$\bu$ is palindromic, then there exist two morphisms $\varphi$ and $\varphi'$
such that $\bu=\varphi(\bv)$, $\varphi'(\bv)=\bv$ and both $\varphi$ and
$\varphi'$ have a conjugate in class~$\P$.
They remarked that this property holds for $\bx_\gamma$ since $\pi$ and $\mu$
have a conjugate in class~$\P$. They show that this statement holds for
sequences $\bu$ that are primitive morphic word with finite defect.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The author is thankful to the anonymous referee whose suggestions improved
considerably the presentation.

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

\begin{thebibliography}{BMBG}


\bibitem[ABCD03]{MR1964623}
J.-P. Allouche, M. Baake, J. Cassaigne, and D. Damanik.
\newblock Palindrome complexity.
\newblock {\em Theoret. Comput. Sci.}, 292(1):9--31, 2003.

\bibitem[BHNR04]{bhnr}
S. Brlek, S. Hamel, M. Nivat, and C. Reutenauer.
\newblock On the palindromic complexity of infinite words.
\newblock {\em Int. J. Found. Comput. Sci.}, 15(2):293--306, 2004.

\bibitem[BMBGL08]{MR2566171}
A.~Blondin-Mass{\'e}, S.~Brlek, A.~Garon, and S.~Labb{\'e}.
\newblock Combinatorial properties of {$f$}-palindromes in the {T}hue-{M}orse
  sequence.
\newblock {\em Pure Math. Appl. (PU.M.A.)}, 19(2-3):39--52, 2008.

\bibitem[BPS11]{MR2822202}
L. Balkov{\'a}, E. Pelantov{\'a}, and {\v{S}}.  Starosta.
\newblock Infinite words with finite defect.
\newblock {\em Adv. in Appl. Math.}, 47(3):562--574, 2011.

\bibitem[BV12]{bucci_vaslet_2012}
M.~Bucci and E.~Vaslet.
\newblock Palindromic defect of pure morphic aperiodic words.
\newblock {\em 14th Mons Days of Theoretical
  Computer Science}, 2012 (talk).

\bibitem[DJP01]{droubay_episturmian_2001}
X. Droubay, J. Justin, and G. Pirillo.
\newblock Episturmian words and some constructions of de {L}uca and {R}auzy.
\newblock {\em Theoret. Comput. Sci.}, 255(1-2):539--553, 2001.

\bibitem[DK09]{MR2543346}
V. Diekert and D. Krieger.
\newblock Some remarks about stabilizers.
\newblock {\em Theoret. Comput. Sci.}, 410(30-32):2935--2946, 2009.

\bibitem[GJWZ09]{MR2489283}
A. Glen, J. Justin, S. Widmer, and L.~Q. Zamboni.
\newblock Palindromic richness.
\newblock {\em European J. Combin.}, 30(2):510--531, 2009.

\bibitem[HKS95]{MR1372804}
A.~Hof, O.~Knill, and B.~Simon.
\newblock Singular continuous spectrum for palindromic {S}chr\"odinger
  operators.
\newblock {\em Comm. Math. Phys.}, 174(1):149--159, 1995.

\bibitem[HVZ13]{harju_remark_2013}
T. Harju, J. Vesti, and L.~Q. Zamboni.
\newblock On a remark of Hof, Knill and Simon on palindromic substitutive
  systems.
\newblock \arxiv{1311.0185v1}, Nov 1 2013.

\bibitem[Kri08]{MR2424350}
D. Krieger.
\newblock On stabilizers of infinite words.
\newblock {\em Theoret. Comput. Sci.}, 400(1-3):169--181, 2008.

\bibitem[Lab08]{labbe_proprietes_2008}
S. Labb\'e.
\newblock Propri\'et\'es combinatoires des $f$-palindromes.
\newblock Mémoire de maîtrise, Universit\'e du Qu\'ebec \`a Montr\'eal, Montr\'eal,
  2008.
\newblock M10615.

\bibitem[Lot02]{MR1905123}
M.~Lothaire.
\newblock {\em Algebraic combinatorics on words}, volume~90 of {\em
  Encyclopedia of Mathematics and its Applications}.
\newblock Cambridge University Press, Cambridge, 2002.

\bibitem[MS93]{MR1265903}
F. Mignosi and P. S{\'e}{\'e}bold.
\newblock Morphismes sturmiens et r\`egles de {R}auzy.
\newblock {\em J. Th\'eor. Nombres Bordeaux}, 5(2):221--233, 1993.

\bibitem[RS12]{MR2901382}
G. Richomme and P. S{\'e}{\'e}bold.
\newblock Completing a combinatorial proof of the rigidity of {S}turmian words
  generated by morphisms.
\newblock {\em Theoret. Comput. Sci.}, 428:92--97, 2012.

\bibitem[S{\'e}{\'e}98]{MR1603835}
P. S{\'e}{\'e}bold.
\newblock On the conjugation of standard morphisms.
\newblock {\em Theoret. Comput. Sci.}, 195(1):91--109, 1998.
\newblock Mathematical foundations of computer science (Cracow, 1996).

\bibitem[Tan07]{MR2363365}
B.~Tan.
\newblock Mirror substitutions and palindromic sequences.
\newblock {\em Theoret. Comput. Sci.}, 389(1-2):118--124, 2007.

\end{thebibliography}

\end{document}
