\documentclass[11pt]{amsart}
\usepackage{amsthm}
\frenchspacing \sloppy
\newcommand {\QQ}  {{\mathbb Q}}
\newcommand {\ZZ}  {{\mathbb Z}}

\newcommand {\CC}  {{\mathbb C}}
\newcommand {\RR}  {{\mathbb R}}
\newcommand {\PP}  {{\mathbb P}}
\newcommand {\NN}  {{\mathbb N}}
\newcommand {\FF}  {{\mathbb F}}
\newcommand {\KK}  {{\bf K}}
\newcommand {\BB}  {{\mathfrak B}}
\newcommand {\LL}  {\mathcal{L}}
\newcommand {\ord} {\mbox{ord}}

\newtheorem {Def}{Definition}
\newtheorem {Th}{Theorem}
\newtheorem {Cor}{Corollary}
\newtheorem {Pro}{Proposition}
\newtheorem {Le}{Lemma}
\newtheorem {Con}{Conjecture}

\begin{document}

\title[On the equation $G_{n}(x)=G_{m}(P(x))$]{On the diophantine equation
  $G_{n}(x)=G_{m}(P(x))$}
\author[Clemens Fuchs, Attila Peth\H{o} and Robert F. Tichy]{
Clemens Fuchs$^{*}$, Attila Peth\H{o}$^{\dag}$ and Robert F.
Tichy$^{*}$}
\date{\today}
\keywords{}
\thanks{$^*$This work was supported by the Austrian Science Foundation FWF,
  grant S8307-MAT}
\thanks{$^{\dag}$ The second author was supported by the Hungarian National
Foundation for Scientific Research Grants No 16741 and 38225}
\maketitle
\begin{center}
\textup{\small Dedicated to Edmund Hlawka to the occasion of his
$85$th birthday}
\end{center}
\vspace{0.3cm}

\begin{abstract}
Let $\KK$ be a field of characteristic $0$ and let
$p,q,G_{0},G_{1},P\in \KK[x], \deg P\geq 1$. Further let the
sequence of polynomials $(G_{n}(x))_{n=0}^{\infty}$ be defined by
the second order linear recurring sequence
$$ G_{n+2}(x)=p(x)G_{n+1}(x)+q(x)G_{n}(x), \quad \mbox{for} \,\, n\geq 0.$$
In this paper we give conditions under which the diophantine
equation $ G_{n}(x)=G_{m}(P(x))$
has at most $\exp(10^{18})$ many solutions $(n,m)\in \ZZ^{2},n,m\geq 0$. The proof
uses a very recent result on $S$-unit equations over fields of characteristic $0$ due to J.-H. Evertse,
H. P. Schlickewei and W. M. Schmidt (cf. \cite{ev+schl+schm}). Under the same
conditions we present also 
bounds for the cardinality of the set
$$\{(m,n)\in\NN \,\vert\,m\neq n, \exists\,c\in\KK\backslash\{0\} \,\,\mbox{such that}\,\, G_{n}(x)=c\,G_{m}(P(x))\}.$$
In the last part we specialize our results to certain
families of orthogonal polynomials.
\end{abstract}
\vspace{0.5cm}
%\maketitle

\section{Introduction}

Let $\KK$ denote a field of characteristic $0$. There is no loss of generality
in assuming that this field is algebraically closed and we will assume this for the rest of the paper. Let
$p,q,G_{0},G_{1}\in \KK[x]$ and let the sequence of polynomials
$(G_{n}(x))_{n=0}^{\infty}$ be defined by the second order linear
recurring sequence
\begin{equation}\label{oegngm-rec}
G_{n+2}(x)=p(x)G_{n+1}(x)+q(x)G_{n}(x), \quad \mbox{for} \,\,
n\geq 0.
\end{equation}

By $\alpha(x),\overline{\alpha}(x)$ we denote the roots of the
corresponding characteristic polynomial
\begin{equation}\label{oegngm-gl2}
T^{2}-p(x)T-q(x).
\end{equation}
Let $\Delta(x)=p(x)^{2}+4q(x)$ be the discriminant of the
characteristic polynomial of the recurring sequence
$(G_{n}(x))_{n=0}^{\infty}$. Then we have
\begin{displaymath}
\alpha(x)=\frac{p(x)+\sqrt{\Delta(x)}}{2}, \quad \overline{\alpha}(x)=
\frac{p(x)-\sqrt{\Delta(x)}}{2}.
\end{displaymath}
We will always assume that the recurring sequence is simple, which
means that $\Delta(x)\neq 0$. Then for $n\geq 0$
\begin{equation}\label{oegngm-meq2}
G_{n}(x)=g_{1}(x)\alpha(x)^{n}+g_{2}(x)\overline{\alpha}(x)^{n},
\end{equation}
where
\begin{equation}\label{oegngm-g1g2}
g_1(x)=\frac{G_1(x)-G_0(x)\overline{\alpha}(x)}{\alpha(x)-\overline{\alpha}(x)}
\quad\mbox{and}\quad
g_2(x)=\frac{G_1(x)-G_0(x)\alpha(x)}{\alpha(x)-\overline{\alpha}(x)}.
\end{equation}
Notice that
\begin{displaymath}
g_{1},g_{2}\in \KK(x,\sqrt{p(x)^{2}+4q(x)})=\KK(x,\sqrt{\Delta(x)}).
\end{displaymath}
Therefore, we have
$$G_{n}(x)=\frac{G_{1}(x)-G_{0}(x)\overline{\alpha}(x)}{\alpha(x)-\overline{\alpha}(x)}\alpha(x)^{n}+\frac{G_{1}(x)-G_{0}(x)\alpha(x)}
{\alpha(x)-\overline{\alpha}(x)}\overline{\alpha}(x)^{n}.$$
\\

$(G_{n}(x))_{n=0}^{\infty}$ is called nondegenerate, if the
quotient $\overline{\alpha}(x)/\alpha(x)$ is not a root of unity.
\\

Many diophantine equations involving the recurrence
$(G_{n}(x))_{n=0}^{\infty}$ were studied previously. For example
let us consider the equation
\begin{equation} \label{oegngm-nm}
G_{n}(x)=s(x),
\end{equation}
where $s(x) \in \KK[x]$ is given. We denote by $N(s(x))$ the
number of integers $n$ for which (\ref{oegngm-nm}) holds. Schlickewei
\cite{sch} established an absolute bound for $N(s(x))$, provided
that the sequence is nondegenerate and that also $\alpha,
\overline{\alpha}$ are not equal to a root of unity. His bound was
substantially improved by Beukers and Schlickewei \cite{b+s} who
showed that
\begin{displaymath}
N(s(x))\leq 61.
\end{displaymath}
In the particular case that not all algebraic functions $g_{1}(x)/s(x), g_{2}(x)/s(x),
\alpha (x),\overline{\alpha} (x)$ are constants (which will always be the case in our paper), Beukers and Tijdeman
(cf. Theorem 2 on p. 206 in \cite{beu+tij}) showed that
$$ N(s(x))\leq 3.$$
Very recently, Schmidt \cite{schm2} obtained the remarkable result
that for arbitrary nondegenerate complex recurring sequences of
order $q$ one has $N(a)\leq C(q)$, where $a\in \CC$ and $C(q)$
depends only (and in fact triply exponentially) on $q$.
\\

Another kind of result is due to Glass, Loxton and van der Poorten
\cite{glvdp}. They showed that, if $(G_{n}(x))_{n=0}^{\infty}$ is
nonperiodic and nondegenerate, then there are only finitely many
pairs of integers $m,n$ with $m>n\geq 0$ and
\begin{equation}\label{oegngm-eqq}
G_{n}(x)=G_{m}(x).
\end{equation}

In a recent paper Dujella and Tichy \cite{D+T} showed for linear
recurring sequences $G_{n+1}(x)=xG_n(x)+BG_{n-1}(x),\ \ G_0(x)=0,\
\ G_1(x)=1$ of polynomials with $B\in\ZZ\backslash\{0\}$ 
that there does not exist a polynomial
$P(x)\in\CC[x]$ satisfying
\begin{equation}\label{oegngm-dt}
G_n(x)=G_m(P(x))
\end{equation}
(for all $m,n\ge3,\ \ m\neq n$).
Applying a general theorem of Bilu and Tichy \cite{B+T}, this
result was used to show that the diophantine equation
$G_n(x)=G_m(y)$ has only finitely many solutions in integers
$n,m,x,y,$ with $n \not = m.$


It is the aim of this paper to present suitable extensions of the
results (\ref{oegngm-nm}) and (\ref{oegngm-dt}).
\\

\section{General Results}

Our first main result is a generalization of (\ref{oegngm-eqq}) to the
diophantine equation
\begin{equation}\label{oegngm-meq}
G_{n}(x)=G_{m}(P(x)),
\end{equation}
where $P \in \KK[x]$ is an arbitrary polynomial of degree $\geq 1$. We show that under certain hypotheses, the number of pairs $(n,m)$ with (\ref{oegngm-meq}) is bounded above by an absolute constant.

\begin{Th}\label{oegngm-th1}
Let $p,q,G_{0},G_{1},P \in\KK[x]$, $\deg P\geq 1$ and
$(G_{n}(x))_{n=0}^{\infty}$ be defined as above. Assume that the
following conditions are satisfied: $2\deg p>\deg q\geq 0$ and
\begin{eqnarray*}
\deg G_{1} &>& \deg G_{0}+\deg p\geq 0, \quad \mbox{or}\\
\deg G_{1} &<& \deg G_{0}+\deg q -\deg p.
\end{eqnarray*}
Then there are at most $\min\{\exp(18^{10}),C(p,q,P)\}$ pairs of integers $(n,m)$ with $n,m\geq 0$, $n\neq m$ such that
\begin{displaymath}
G_{n}(x)=G_{m}(P(x))
\end{displaymath}
holds. We have
$$C(p,q,P)=10^{28}\cdot \log(2C_{1}\deg p)\cdot (4e)^{8C_1\deg q}\cdot
7^{4C_1\deg q},$$
where $C_1=2(\deg P+1)$.
\end{Th}

\noindent{\bf Remark 1.}\label{oegngm-rem1} If $\deg P=1$ then Theorem \ref{oegngm-th1} does not remain valid if we allow $m=n$.
\\

\noindent{\bf Remark 2.}\label{oegngm-rem3} This example shows that also in the
polynomial case the condition $2\deg p>\deg q$ is needed. Assume
that
\begin{eqnarray*}
&& G_{0}(x)=1, \quad G_{1}(x)=x,\\
&& G_{n+2}(x)=\frac{x}{2}G_{n+1}(x)+\frac{x^{2}}{2}G_{n}(x).
\end{eqnarray*}
Here we have
$$ 2\deg p =\deg q=2 \,\,\, \mbox{and} \,\,\, \deg G_{0}=0, \deg G_{1}=1.$$
It follows that
$$G_{n}(x)=x^{n} \quad \forall n.$$
In this case the following equation holds
$$ G_{2n}(x)=G_{n}(x^{2})$$
for all integers $n$.
\\

\noindent{\bf Remark 3.}\label{oegngm-rem4} Let us consider the Chebyshev polynomials
of the first kind, which are defined by
$$ T_{n}(x)=\cos(n\arccos x).$$
It is well known that they satisfy the following second order
recurring relation:
\begin{eqnarray*}
&& T_{0}(x)=1, \quad T_{1}(x)=x,\\
&& T_{n+2}(x)=2xT_{n+1}(x)-T_{n}(x).
\end{eqnarray*}
In this case we have
$$ 2\deg p >\deg q \,\,\, \mbox{and} \,\,\, \deg T_{1}=\deg T_{0}+\deg p=1.$$
It is also well known and in fact easy to prove that
$$T_{2n}(x)=T_{n}(2x^{2}-1)$$
holds for all integers $n$. This example shows that also the
second assumption in Theorem \ref{oegngm-th1} is needed.
\\

Actually, it is also possible to give an upper bound for the number of pairs $(m,n)$ with
$G_{n}(x)=c\,G_{m}(P(x))$, $c\in\KK^{*}=\KK\backslash\{0\}$ variable. This means that we can
give an upper bound for the cardinality of the set
$$\{(m,n)\in\NN \,\vert\,m\neq n, \exists\,c\in\KK^{*} \,\,\mbox{such that}\,\, G_{n}(x)=c\,G_{m}(P(x))\}.$$
(Here $c$ may vary with $m,n$). In fact, the second part of the upper bound in the last theorem, which depends on the degrees of the polynomials involved, follows from this more general theorem. 

\begin{Th}\label{oegngm-th2}
Let $p,q,G_{0},G_{1},P \in\KK[x]$, $\deg P\geq 1$ and
$(G_{n}(x))_{n=0}^{\infty}$ be defined as above. Assume that the
following conditions are satisfied: $2\deg p>\deg q\geq 0$ and
\begin{eqnarray*}
\deg G_{1} &>& \deg G_{0}+\deg p\geq 0, \quad \mbox{or}\\
\deg G_{1} &<& \deg G_{0}+\deg q -\deg p.
\end{eqnarray*}
Then the number of pairs of integers $(n,m)$ with $n,m\geq 0, n\neq m$ for which there
exists $c\in\KK^{*}$ with
$$ G_{n}(x)=c\,G_{m}(P(x))$$
is at most $C(p,q,P)$.
We have
$$C(p,q,P)=10^{28}\cdot \log(2C_{1}\deg p)\cdot (4e)^{8C_1\deg q}\cdot
7^{4C_1\deg q},$$
where $C_1=2(\deg P+1)$.
\end{Th}

It is also possible to replace the conditions concerning the
degree by algebraic conditions.

\begin{Th}\label{oegngm-th3}
Let $p,q,G_{0},G_{1},P\in\KK[x]$ and
$(G_{n}(x))_{n=0}^{\infty}$ be defined as above. Assume that
\begin{itemize}
\item[(1)] $\deg\Delta\neq 0,$
\item[(2)] $\deg P \geq 2,$
\item[(3)] $\gcd(p,q)=1 \,\,\, \mbox{and}$
\item[(4)] $\gcd(2G_{1}-G_{0}p,\Delta)=1.$
\end{itemize}
Then there are at most $\min\{\exp(10^{18}),\tilde{C}(p,q,P)\}$ pairs of integers $(n,m)$ with $n,m\geq 0$ such
that
$$G_{n}(x)=G_{m}(P(x))$$
holds. We have
$$\tilde{C}(p,q,P)=10^{28}\cdot \log(C_1\max\{2\deg p,\deg q\})\cdot(4e)^{8C_1\deg q}\cdot 
7^{4C_1\deg q},$$
where $C_1=2(\deg P+1)$.
\end{Th}

\noindent{\bf Remark 4.}\label{oegngm-rem5} The degree assumptions from Theorems \ref{oegngm-th1} and \ref{oegngm-th2} arise from considering the infinite valuation in the rational function field $\KK(x)$, whereas by looking at the finite valuations one obtains the divisiblity conditions from Theorem \ref{oegngm-th3}.
\\

\noindent{\bf Remark 5.}\label{oegngm-rem6} It is obvious that for $\deg P=1$ Theorem
3 cannot hold in full generality. For example: if $G_{n}(x)$ is a
polynomial in $x^{2}$ for all $n$ we get
$$ G_{n}(x)=G_{n}(-x)$$
for all $n$.
\\

\noindent{\bf Remark 6.}\label{oegngm-rem7} By looking at the proof, it is clear that
Theorem \ref{oegngm-th3} also holds, if we assume instead of $(2)$
\begin{itemize}
\item[$(2')$] There is no $c \in \KK$ such that $\Delta(P(x))=c\Delta(x)$ holds.
\end{itemize}
To our knowledge this is the weakest condition under which our
proof works.\\
It is clear that $(2')$ holds if $\deg P\geq 2$ or if $P$ is a constant.
If $P(x)=x$ then $\Delta(P(x))=c\Delta(x)$ holds with $c=1$.
Suppose that
$P(x)=ax+b$ with $a,b\in{\bf K}$ and $a\not= 0$, $(a,b)\not= (1,0)$.
Denote by $P^{(k)}$ the $k$-th iterate of $P$. Let $\Delta_0$ be the leading
coefficient of $\Delta (x)$.
It is left to the reader
to show that $\Delta(P(x))=c\Delta(x)$ for some $c\in\KK^*$ if and only if $a^{\deg \Delta}=c$, $a$
is a root of unity of order $k>1$
and
$$
\Delta (x)= \Delta_0\Big( x+{b\over a-1}\Big)^s
\prod_{i=1}^r\prod_{j=0}^{k-1} (x-P^{(j)}(x_i)),
$$
where $r,s$ are non-negative integers with $rk+s=\deg \Delta$ and
$-{b\over a-1},x_1,\ldots,x_r$ are distinct elements of ${\bf K}$.
\\

The second part of the bound of Theorem \ref{oegngm-th3} follows from Theorem \ref{oegngm-th4} below, which deals with the case $G_n(x)=c\,G_m(P(x))$ with $c\in\KK^*$ variable.

\begin{Th}\label{oegngm-th4}
Let $p,q,G_{0},G_{1},P \in\KK[x]$ and
$(G_{n}(x))_{n=0}^{\infty}$ be defined as above. Assume that the
conditions (1)-(4) of Theorem \ref{oegngm-th3} are satisfied. Then the number of pairs of integers $(n,m)$
with $n,m\geq 0$ for which there exists $c\in\KK^{*}$ with
$$G_{n}(x)=c\,G_{m}(P(x))$$
is at most $\tilde{C}(p,q,P)$. We have
$$\tilde{C}(p,q,P)=10^{28}\cdot \log(C_1\max\{2\deg p,\deg q\})\cdot(4e)^{8C_1\deg q}\cdot 
7^{4C_1\deg q},$$
where $C_1=2(\deg P+1)$.
\end{Th}

\section{Results for Families of Orthogonal Polynomials}

We will turn now our discussion to sequences of certain orthogonal
polynomials satisfying (\ref{oegngm-rec}). The following results can be found in the
monograph of Borwein and Erd\'elyi \cite[Chapter 2.3]{b+e}, Chihara \cite[Chapter I and II]{ch} or Szeg\H{o}
\cite[Chapter III]{sz}. Let $(\mu_{n})_{n=0}^{\infty}$ be a sequence of
complex numbers and let $\LL : \CC[x] \longrightarrow \CC$ be a linear
functional defined by
$$ \LL[x^{n}]=\mu_{n}, \quad n=0,1,2,\ldots.$$
Then $\LL$ is called the \emph{moment functional} determined by
the formal \emph{moment sequence} $(\mu_{n})$. The number
$\mu_{n}$ is called the \emph{moment of order} $n$. A sequence
of polynomials $(P_{n}(x))_{n=0}^{\infty}$ with complex coefficients is called an \emph{orthogonal
polynomial sequence} (OPS) with respect to a moment functional
$\LL$ provided that for all nonnegative integers $m$ and $n$ the
following conditions are satisfied:
\begin{itemize}
\item[(i)] $\deg P_{n}(x)=n$,
\item[(ii)] $\LL[P_{m}(x)P_{n}(x)]=0 \,\, \mbox{for} \,\, m\neq n,$
\item[(iii)] $\LL[P_{n}^{2}(x)]\neq 0.$
\end{itemize}
If there exists an OPS for $\LL$, then each $P_{n}(x)$ is uniquely
determined up to an arbitrary non-zero factor. An OPS in which
each $P_{n}(x)$ is monic will be referred to as a \emph{monic}
OPS; it is indeed unique.
\\

It is well known that a necessary and sufficient condition for the
existence of an OPS for a moment functional $\LL$ with moment
sequence $(\mu_{n})$ is that for the determinants defined by
$$ \Delta_{n}=\det(\mu_{i+j})_{i,j=0}^{n}=\left\vert
\begin{array}{cccc}
\mu_{0}&\mu_{1}&\ldots&\mu_{n}\\
\mu_{1}&\mu_{2}&\ldots&\mu_{n+1}\\
\vdots&\vdots&\ddots&\vdots\\
\mu_{n}&\mu_{n+1}&\ldots&\mu_{2n}
\end{array}\right\vert
$$
the following conditions hold
$$ \Delta_{n}\neq 0,\quad n=0,1,2,\ldots.$$
In this case $\LL$ is called \emph{quasi-definite}.
\\

A moment functional $\LL$ is called \emph{positive-definite} if
$\LL[\pi(x)]>0$ for every $\pi(x)\in \CC[x]$ that is not
identically zero and which satisfies $\pi(x)\geq 0$ for all real
$x$. The following holds: $\LL$ is positive-definite if and only
if its moments are all real and $\Delta_{n}>0$ for all $n\geq 0$.
Furthermore, using the Gram-Schmidt process, a corresponding OPS
consisting of real polynomials exists. Moreover, $\LL$ is
positive-definite if and only if a bounded, non-decreasing
function $\psi$ exists, whose moments
$$ \mu_{n}=\int_{-\infty}^{\infty}x^{n}d\psi(x), \quad n=0,1,2,\ldots,$$
are all finite and for which the set
$$ \mathfrak{S}(\psi)=\{x\,\vert\, \psi(x+\delta)-\psi(x-\delta)>0 \,\, \mbox{for all}
\,\, \delta>0\}$$ is infinite. Further for the function $\psi$
$$\int_{-\infty}^{\infty}x^{n}d\psi(x)=\mu_{n}=\LL[x^{n}],\quad n=0,1,2,\ldots$$
is valid. This is known as the representation theorem for
positive-definite moment functionals or as the solution to the
\emph{Hamburger} moment problem.

Thus, an OPS with respect to a positive-definite moment
functional $\LL$ induces an inner product defined by
$$\langle p,q\rangle =\LL[p(x)\overline{q(x)}], \quad p,q\in \CC[x],$$
where $\overline{q(x)}$ is obtained by taking the complex conjugates of
the coefficients of $q(x)$,
on the linear space of polynomials with complex coefficients. In particular,
we have $\langle P_{m},P_{n}\rangle=\LL[P_m(x)\overline{P_n(x)}]=0,\quad m\neq n.$ Thus, our definition of orthogonality for the OPS is consistent with the
usual definition of orthogonality in an inner product space.
\\

One of the most important characteristics of an OPS is the fact
that any three consecutive polynomials are connected by a very
simply relation: Let $\LL$ be a quasi-definite moment functional
and let $(P_{n}(x))_{n=0}^{\infty}$ be the corresponding monic
OPS. Then there exist constants $c_{n}$ and $\lambda_{n}\neq 0$
such that
\begin{equation}\label{oegngm-recops}
P_{n}(x)=(x-c_{n})P_{n-1}(x)-\lambda_{n}P_{n-2}(x),\quad
n=1,2,3,\ldots,
\end{equation}
where we define $P_{-1}(x)=0$. Moreover, if $\LL$ is
positive-definite, then $c_{n}$ is real and $\lambda_{n+1}>0$ for
$n\geq 1$ ($\lambda_{1}$ is arbitrary). 
\\

The converse is also true and it is referred to as
Favard's theorem: Let $(c_{n})_{n=0}^{\infty}$ and
$(\lambda_{n})_{n=0}^{\infty}$ be arbitrary sequences of complex
numbers and let $(P_{n}(x))_{n=0}^{\infty}$ be defined by the
recurring formula
\begin{eqnarray}\label{oegngm-recfav}
&& P_{n}(x)=(x-c_{n})P_{n-1}(x)-\lambda_{n}P_{n-2}(x), \quad n=1,2,3,\ldots,\\
&& P_{-1}(x)=0, \,\, P_{0}(x)=1.
\end{eqnarray}
Then there is a unique moment functional $\LL$ such that
$$ \LL[1]=\lambda_{1}, \,\, \LL[P_{m}(x)P_{n}(x)]=0 \,\, \mbox{for} \,\,
m\neq n, \,\, m,n=0,1,2,\ldots.$$ $\LL$ is quasi-definite and
$(P_{n}(x))_{n=0}^{\infty}$ is the corresponding monic OPS if and
only if $\lambda_{n}\neq 0$ for all $n\geq 1$, while $\LL$ is positive-definite if
and only if $c_{n}$ is real and $\lambda_{n}>0$ for all $n\geq 1$.
\\

More generally, let $(P_{n}(x))_{n=0}^{\infty}$ be a sequence of polynomials in $\CC[x]$
satisfying
\begin{eqnarray*}
&&P_{n}(x)=(A_nx+B_n)P_{n-1}(x)+D_nP_{n-2}(x)\quad (n\geq 1)\\
&&P_{-1}(x)=0, \,\, P_0(x)=g\neq 0,
\end{eqnarray*}
where $A_n,B_n,D_n$ are complex numbers with $A_n\not= 0, D_n\not=0$
for every $n\geq 1$.
It follows easily by induction on $n$ that $P_n$ has degree $n$
and that $P_n$ has leading coefficient $k_n=gA_1\cdots A_{n}$ for $n\geq 0$.
Let $k_{-1}:=1$. For $n\geq -1$ write
$P_n(x)=k_n\hat{P}_n(x)$. Thus $\hat{P}_n(x)$ is monic for $n\geq 0$.
Further, $\hat{P}_{-1}(x)=0$, $\hat{P}_{1}(x)=1$ and
the sequence $(\hat{P}_n(x))_{n=0}^{\infty}$ satisfies (8) with
$c_n=-B_nk_{n-1}/k_n=-B_n/A_n$, $\lambda_1$ arbitrary and
$\lambda_n=-D_nk_{n-2}/k_n=-D_n/A_{n-1}A_n$ for $n\geq 2$.
So by Favard's Theorem, $(\hat{P}_n(x))_{n=0}^{\infty}$ is a monic OPS
and therefore, $(P_n(x))_{n=0}^{\infty}$ is an OPS for some
quasi-definite moment functional ${\LL}$. Moreover, ${\LL}$
is positive definite if $B_n/A_n\in\RR$ and
$D_n/A_{n-1}A_n<0$ for $n\geq 2$.
\\

We now consider the special case that $A_1=e/g$, $B_1=f/g$, $D_1=0$ where $g\neq 0$ and $A_n=a$, $B_n=b$, $D_n=d$ do not
depend on $n$ for $n\geq 2$, that is, we consider
the sequence of polynomials $(P_n(x))_{n=0}^{\infty}$
with $P_n(x)\in \CC[x]$ given by
\begin{eqnarray}
&&P_{n+1}(x)=(ax+b)P_n(x)+dP_{n-1}(x), \quad n\geq 1,\label{oegngm-oeq1}\\
&&P_0(x)=g, \,\, P_1(x)=ex+f,\label{oegngm-oeq2}
\end{eqnarray}
where $a,b,d,e,f,g$ are complex numbers with $adeg\not= 0$. By the comments just
made this sequence is an OPS
for some quasi-definite moment functional ${\LL}$.
\\

In the view of Remark \ref{oegngm-rem4} it is clear that Theorem \ref{oegngm-th1} and Theorem \ref{oegngm-th2}
cannot hold for all OPS $(P_{n}(x))_{n=0}^{\infty}$, because the
Chebyshev polynomials of the first kind are orthogonal with
respect to the positive-definite moment functional
$$ \LL[\pi(x)]=\int_{-1}^{1}\pi(x)(1-x^{2})^{-1/2}dx.$$
Using the same methods as above we will prove the following analogues of Theorems \ref{oegngm-th1} and \ref{oegngm-th2}.

\begin{Th}\label{oegngm-th5}
Let $a,b,d,e,f,g \in \CC$ with $adeg\neq 0$ and let
$(P_{n}(x))_{n=0}^{\infty}$ be a sequence of polynomials in $\CC[x]$
defined by (\ref{oegngm-oeq1}) and (\ref{oegngm-oeq2}). Let $S(x)\in \CC[x],
\deg S\geq 1$. If we assume that $e=ag$, then there are at most 
$\min\{\exp(18^{10}),C(S)\}$ pairs of integers $(n,m)$ with $n,m\geq 0$, $n\neq m$ such
that
$$P_{n}(x)=P_{m}(S(x))$$
holds. We have
$$ C(S)=10^{28} \cdot \log(4(\deg S+1)).$$
\end{Th}

Again we can prove the following result concerning the more general equation $P_{n}(x)=c\,P_{m}(S(x))$
with some $c\in\CC^{*}$ variable and again the second part of the last theorem follows from this theorem.

\begin{Th}\label{oegngm-th6}
Let $a,b,d,e,f,g \in \CC$ with $adeg\neq 0$ and let
$(P_{n}(x))_{n=0}^{\infty}$  be defined by (\ref{oegngm-oeq1}) and
(\ref{oegngm-oeq2}). Let $S(x)\in \CC[x],\deg S\geq 1$ and $e=ag$. Then
the number of pairs of integers $(n,m)$ with $n\neq m$ for which
there exists $c\in\CC^*$ with $$P_{n}(x)=c\,P_m(S(x))$$ is at most $C(S)$. We have
$$ C(S)=10^{28} \cdot \log(4(\deg S+1)).$$
\end{Th}
\vspace{0.3cm} \noindent{\bf Remark 7.}\label{oegngm-rem8} We want to mention that
Theorem \ref{oegngm-th3} and therefore also Theorem \ref{oegngm-th4} can be applied to this
situation. The conditions (1) and (3) are trivially satisfied in
this case. Condition (4) holds, if
$\Delta(x)=p(x)^{2}+4q(x)=(ax+b)^{2}+4d$ and
$2P_{1}(x)-P_{0}(x)p(x)=2(ex+f)-g(ax+b)=(2e-ag)x+2f-bg$ have no common
roots. This means that, if $2e=ag, 2f=bg$ does not hold or if
$$x=\frac{bg-2f}{2e-ag}$$
is not a root of $\Delta(x)$, then we get our assertion for all
$S(x)\in \CC[x], \deg S\geq 2$.

This is satisfied for example if we consider sequences $P_{n}(x)\in\CC[x]$ defined by
\begin{eqnarray*}
&&P_{n+1}(x)=(ax+b)P_n(x)+dP_{n-1}(x), \quad n\geq 1,\\
&&P_{-1}(x)=0,\,\,P_0(x)=g\neq 0,
\end{eqnarray*}
where $a,b,d,g$ are complex numbers with $adg\not= 0$.

\section{Auxiliary Results}

In this section we collect some important theorems which
we will need in our proofs.
\\

Let $\KK$ be an algebraically closed field of characteristic $0$, $n\geq
1$ an integer, $\alpha_{1},\ldots,\alpha_{n}$ elements of $\KK^{*}$
and $\Gamma$ a finitely generated multiplicative subgroup of
$\KK^{*}$. A solution $(x_{1},\ldots,x_{n})$ of the so called
\emph{weighted unit equation}
\begin{equation}\label{oegngm-ueq}
\alpha_{1}x_{1}+\cdots+\alpha_{n}x_{n}=1 \,\, \mbox{in} \,\,
x_{1},\ldots,x_{n} \in \Gamma
\end{equation}
is called \emph{non-degenerate} if
\begin{equation}
\sum_{j\in J}\alpha_{j}x_{j}\neq 0 \,\, \mbox{for each non-empty
subset $J$ of} \,\, \{1,\ldots,n\}
\end{equation}
and \emph{degenerate} otherwise. It is clear that if $\Gamma$ is
infinite and if (\ref{oegngm-ueq}) has a degenerate solution then
(\ref{oegngm-ueq}) has infinitely many degenerate solutions. For
non-degenerate solutions we have the following result, which is
due to Evertse, Schlickewei and Schmidt \cite{ev+schl+schm}.

\begin{Th}[{\bf Evertse, Schlickewei and Schmidt}]\label{oegngm-mainth}
Let $\KK$ be a field of characteristic $0$, let $\alpha_{1},\ldots,´\alpha_{n}$ be
non-zero elements of $\KK$ and let $\Gamma$ be a multiplicative subgroup
of $(\KK^{*})^{n}$ of rank $r$. Then the equation
$$\alpha_{1}x_{1}+\ldots+\alpha_{n}x_{n}=1$$ has at most
$$\exp((6n)^{3n}(r+1))$$ non-degenerate solutions $(x_{1},\ldots,x_{n})\in\Gamma$.
\end{Th}

This theorem is the Main Theorem on $S$-unit equations
over fields of characteristic $0$. It is a
generalization and refinement of earlier results due to Evertse and Gy\H{o}ry \cite{ev+g}, Evertse \cite{ev0} and van der Poorten
and Schlickewei \cite{vdP+s} on the finiteness of the number of non-degenerate solutions of (\ref{oegngm-ueq}). For a
general survey on these equations and their applications we refer
to Evertse, Gy\H{o}ry, Stewart and Tijdeman \cite{ev+g+st}. 
\\

Next we will consider equation (\ref{oegngm-ueq}) also over function
fields. Let $F$ be an algebraic function field in one variable
with algebraically closed constant field $\KK$ of characteristic
$0$. Thus $F$ is a finite extension of $\KK(t)$, where $t$ is a
transcendental element of $F$ over $\KK$. The field $F$ can be
endowed with a set $M_{F}$ of additive valuations with value group
$\ZZ$ for which
$$ \KK=\{0\}\cup\{z\in F \, \vert \, \nu(z)=0 \,\, \mbox{for each
$\nu$ in $M_{F}$} \,\}$$ holds. Let $S$ be a finite subset of
$M_{F}$. An element $z$ of $F$ is called an $S$-\emph{unit} if
$\nu(z)=0$ for all $\nu \in M_{F}\backslash S$. The $S$- units
form a multiplicative group which is denoted by $U_{S}$. The group
$U_{S}$ contains $\KK^{*}$ as a subgroup and $U_{S}/ \KK^{*}$
is finitely generated. For function fields we have the following result:

\begin{Th}[{\bf Evertse and Gy\H{o}ry}]\label{oegngm-fmt}
Let $F,\KK,S$ be as above. Let $g$ be the genus of $F/\KK$, $s$ the
cardinality of $S$, and $n\geq 2$ an integer. Then for every
$\alpha_{1},\ldots,\alpha_{n}\in F^{*}$, the set of solutions of
\begin{eqnarray}\label{oegngm-fueq}
&&\alpha_{1}x_{1}+\ldots+\alpha_{n}x_{n}=1 \,\, \mbox{in} \,\,
x_{1},\ldots,x_{n}
\in U_{S}\\
&& \mbox{with}\,\,\alpha_{1}x_{1},\ldots,\alpha_{n}x_{n} \,\,
\mbox{not all in} \,\, \KK
\end{eqnarray}
is contained in the union of at most
$$ \log(g+2)\cdot (e(n+1))^{(n+1)s+2}$$
$(n-1)$-dimensional linear subspaces of $F^{n}$.
\end{Th}

For deriving this upper bound an effective upper bound of
Brownawell and Masser \cite{b+m} for the heights of solutions of
(\ref{oegngm-fueq}) is used. For $n=2$ the theorem gives the upper bound
$$ \log(g+2)(3e)^{3s+2}$$
for the number of solution of (\ref{oegngm-fueq}). We note that for the case
$n=2$ Evertse \cite{ev1} established an upper bound, which is
better and independent of $g$.

\begin{Th}[{\bf Evertse}]\label{oegngm-evs}
Let $F,\KK,S$ be as above. For each pair $\lambda,\mu$ in $F^{*}$,
the equation
$$ \lambda x+\mu y=1 \,\, \mbox{in} \,\, x,y \in U_{S}$$
has at most $2\cdot 7^{2s}$ solutions with $\lambda x/\mu y \notin
\KK$. As above, $s$ denotes the cardinality of $S$.
\end{Th}

Finally, we need some results from the theory of algebraic
function fields, which can be found for example in the monograph
of Stichtenoth \cite{st}. We will need the following estimates for the genus of a function
field $F/K$ (cf. \cite{st}, page 130 and 131).

\begin{Th}[{\bf Castelnuovo's Inequality}]\label{oegngm-cueq}
Let $F/K$ be a function field with constant field $K$. Suppose
there are given two subfields $F_{1}/K$ and $F_{2}/K$ of $F/K$
satisfying
\begin{itemize}
\item[(1)] $F=F_{1}F_{2}$ is the compositum of $F_{1}$ and $F_{2}$,
\item[(2)] $[F:F_{i}]=n_{i}$, and $F_{i}/K$ has genus $g_{i}\,\,(i=1,2)$.
\end{itemize}
Then the genus $g$ of $F/K$ is bounded by
$$ g\leq n_{1}g_{1}+n_{2}g_{2}+(n_{1}-1)(n_{2}-1).$$
\end{Th}

In the special case $F_{1}=K(x)$ and $F_{2}=K(y)$, Castelnuovo's
Inequality yields:

\begin{Th}[{\bf Riemann's Inequality}]\label{oegngm-rueq}
Let $\varphi$ be a non-constant irreducible polynomial in two variables with coefficients in $K$ and suppose that $F=K(x,y)$ with $\varphi(x,y)=0$. Then we have the following estimate for the
genus $g$ of $F/K$:
$$ g\leq ([F:K(x)]-1)\cdot ([F:K(y)]-1).$$
\end{Th}

We mention that Riemann's Inequality (and therefore also
Castelnuovo's Inequality) is often sharp, and that in general it cannot be
improved.
\\

Let ${\bf K}$ be an algebraically closed field of characteristic $0$.
Let $K$ be a finite extension of ${\bf K}(x)$ where $x$ is transcendental
over ${\bf K}$.
For $\xi\in{\bf K}$ define the valuation $\nu_{\xi}$
such that for $Q\in {\bf K}(x)$ we have $Q(x)=(x-\xi )^{\nu_{\xi}(Q)}A(x)
/B(x)$
where $A,B$ are polynomials with $A(\xi )B(\xi )\not=0$.
Further, for $Q=A/B$ with $A,B\in{\bf K}[x]$
we put $\deg Q:=\deg A -\deg B$; thus $\nu_{\infty}:=-\deg$ is a discrete
valuation on ${\bf K}(x)$.
Each of the valuations
$\nu_{\xi}$, $\nu_{\infty}$ can be extended
in at most $[K:{\bf K}(x)]$ ways to a discrete valuation on $K$
and in this way one obtains all discrete valuations on $K$.
A valuation on $K$ is called finite if it extends $\nu_{\xi}$
for some $\xi\in{\bf K}$ and infinite if it extends $\nu_{\infty}$.
We choose one of the extensions of $\nu_{\infty}$
to $K$ and denote this by $-{\rm ord}$.
Thus ${\rm ord}$ is a function from $K$ to $\QQ$ having the properties
\begin{eqnarray*}
&\mbox{(a)}&{\rm ord}(Q) =\deg Q\,\,\hbox{for $Q\in{\bf K}[x]$,}\\
&\mbox{(b)}&{\rm ord}(AB) ={\rm ord}(A)+{\rm ord}(B)\,\,\hbox{for $A,B\in K$,}\\
&\mbox{(c)}&{\rm ord}(A+B)\leq \max \{{\rm ord}(A),{\rm ord}(B)\}
\,\,\hbox{for $A,B\in K$,}\\
&\mbox{(d)}&{\rm ord}(A+B) = \max \{{\rm ord}(A),{\rm ord}(B)\}
\,\,\hbox{for $A,B\in K$}\\
&&\hspace*{2.4cm} \hbox{with ${\rm ord}(A)\not= {\rm ord}(B)$.}
\end{eqnarray*}

\section{Proof of Theorem \ref{oegngm-th1}}

First we reduce the solvability of (\ref{oegngm-meq}) to the solvability
of three systems of exponential equations in $n,m$. We start with
a sequence of polynomials $(P_{n}(x))_{n=0}^{\infty}$ defined by
(\ref{oegngm-rec}). Then, in the sequel $\alpha(x),\overline{\alpha}(x),g_{1}(x),g_{2}(x)$
are always be given by (\ref{oegngm-meq2}).

\begin{Le}\label{oegngm-mlem}
Let $(G_{n}(x))_{n=0}^{\infty}$ be a sequence of polynomials
defined by (\ref{oegngm-rec}) and let $P\in \KK[x], \deg P\geq 1$. Assume that $g_1(x)g_2(x)\neq 0$. Then
(\ref{oegngm-meq}) has at most $\exp(18^{9}\cdot 3)$ solutions $m,n\in \ZZ,m\neq n$, which do not satisfy any of the systems:
\begin{eqnarray}\label{oegngm-eq1}
&&\left\{\begin{array}{l}
       g_{1}(x)\alpha(x)^{n}+g_{2}(x)\overline{\alpha}(x)^{n}=0\\
       g_{1}(P(x))\alpha(P(x))^{m}+g_{2}(P(x))\overline{\alpha}(P(x))^{m}=0
       \end{array}\right.\\
&&\left\{\begin{array}{l}
       g_{1}(x)\alpha(x)^{n}=g_{1}(P(x))\alpha(P(x))^{m}\\
       g_{2}(x)\overline{\alpha}(x)^{n}=g_{2}(P(x))\overline{\alpha}(P(x))^{m}
       \end{array}\right.\label{oegngm-eq2}\\
&&\left\{\begin{array}{l}
       g_{2}(x)\overline{\alpha}(x)^{n}=g_{1}(P(x))\alpha(P(x))^{m}\\
       g_{1}(x)\alpha(x)^{n}=g_{2}(P(x))\overline{\alpha}(P(x))^{m}
       \end{array}\right.\label{oegngm-eq3}
\end{eqnarray}
\end{Le}

\emph{Proof.} First we define
$$K=\KK(x,\sqrt{p(x)^{2}+4q(x)},\sqrt{p(P(x))^{2}+4q(P(x))}).$$
Clearly, $K$ is finitely generated extension field of $\QQ$.
Furthermore, let $\Gamma$ be the multiplicative subgroup of $(K^{*})^{3}$ generated
by
$$ (\alpha(x),\overline{\alpha}(x),1) \quad \mbox{and}\quad (\overline{\alpha}(P(x))^{-1},\overline{\alpha}
(P(x))^{-1},\alpha(P(x))/\overline{\alpha}(P(x))).$$
We consider now for $n\neq m$ the
equation $G_{n}(x)=G_{m}(P(x))$ and obtain
$$g_{1}(x)\alpha(x)^{n}+g_{2}(x)\overline{\alpha}(x)^{n}-g_{1}(P(x))\alpha(P(x))^{m}
-g_{2}(P(x))\overline{\alpha}(P(x))^{m}=0.$$ This yields
\begin{equation}\label{oegngm-auseq}
\frac{g_{1}(x)}{g_{2}(P(x))}\frac{\alpha(x)^{n}}{\overline{\alpha}(P(x))^{m}}+
\frac{g_{2}(x)}{g_{2}(P(x))}\frac{\overline{\alpha}(x)^{n}}{\overline{\alpha}(P(x))^{m}}-
\frac{g_{1}(P(x))}{g_{2}(P(x))}\frac{\alpha(P(x))^{m}}{\overline{\alpha}(P(x))^{m}}
=1.
\end{equation}
Now we consider the weighted unit equation
\begin{equation}\label{oegngm-ausueq}
\frac{g_{1}(x)}{g_{2}(P(x))}x_{1}+
\frac{g_{2}(x)}{g_{2}(P(x))}x_{2}-
\frac{g_{1}(P(x))}{g_{2}(P(x))}x_{3} =1 \,\, \mbox{in}\,\,
(x_{1},x_{2},x_{3}) \in \Gamma.
\end{equation}
According to Theorem \ref{oegngm-mainth}, equation (\ref{oegngm-ausueq}) has
at most $\exp(18^{9}\cdot 3)$ solutions if no non-trivial subsum vanishes.
By observing that $g_{1}(x),g_{2}(x)\neq 0$ this means that (\ref{oegngm-auseq}) has at most
$\exp(18^{9}\cdot 3)$ solutions $m,n$ not satisfying (\ref{oegngm-eq1}), (\ref{oegngm-eq2}) and (\ref{oegngm-eq3}).
\hfill $ \square $
\\

In the next lemma we calculate the order of $\alpha(x)$ and
$\overline{\alpha}(x)$ respectively in the function field $K/\KK$,
where $K$ is defined as in the previous proof. We will assume that
$$\ord(\alpha)\geq\ord(\overline{\alpha}).$$
If this is not satisfied we can achieve this by interchanging $\alpha(x)$ and $\overline{\alpha}(x)$.
Then we have:

\begin{Le}\label{oegngm-lemord}
Let $(G_{n}(x))_{n=0}^{\infty}$ be a sequence of polynomials
defined by (\ref{oegngm-rec}) and assume that $2\deg p>\deg q\geq
0$. Then 
\begin{eqnarray}
&&\mbox{\emph{ord}}(\alpha)=\deg p,\\
&&\mbox{\emph{ord}}(\overline{\alpha})=\deg q-\deg p<\deg p.
\end{eqnarray}
\end{Le}

\emph{Proof.} 
First assume $\ord(\alpha)=\ord(\overline{\alpha})$.
Then by (a), (c), (b) we have
$$\deg p=\ord(\alpha +\overline{\alpha})\leq \ord(\alpha)
={1\over 2}\deg q$$ which is against our assumption.
Therefore, $\ord(\alpha)>\ord(\overline{\alpha})$.
Now it follows from (a), (d) that
$\deg p=\ord(\alpha +\overline{\alpha})= \ord(\alpha)$.
Using (a), (b) and $\alpha(x)\overline{\alpha}(x)=-q(x)$
we then obtain $$\ord(\overline{\alpha})=\deg q-\deg p<\deg p.$$
Therefore the proof is finished.
\hfill $\square $
\\

Next we prove the following lemma.

\begin{Le}\label{oegngm-lemnull}
Let $(G_{n}(x))_{n=0}^{\infty}$ be a sequence of polynomials
defined by (\ref{oegngm-rec}) and let $P\in \KK[x], \deg P\geq 1$. Assume
that neither $\alpha(x)/\overline{\alpha}(x)$, nor
$\alpha(P(x))/\overline{\alpha}(P(x))$ is a root of unity. We consider
the systems of equations
$$
\left\{\begin{array}{l}
       g_{1}(x)\alpha(x)^{n}+g_{2}(x)\overline{\alpha}(x)^{n}=0\\
       g_{1}(P(x))\alpha(P(x))^{m}+g_{2}(P(x))\overline{\alpha}(P(x))^{m}=0
       \end{array}\right.
$$
The first equation  has at most one solution in $n$, and the
second one at most one solution in $m$.
\end{Le}

\emph{Proof.} This follows from the fact that neither
$\alpha(x)/\overline{\alpha}(x)$, nor $\alpha(P(x))/\overline{\alpha}(P(x))$
are roots of unity. In particular, assume that we have two
solutions $n_{1},n_{2}$. Then we obtain
$$-\frac{g_{1}(x)}{g_{2}(x)}=\left(\frac{\overline{\alpha}(x)}{\alpha(x)}\right)^{n_{1}}=
\left(\frac{\overline{\alpha}(x)}{\alpha(x)}\right)^{n_{2}},$$ which
implies that $n_{1}=n_{2}$. \hfill $\square $
\\
\\
{\sc Proof of Theorem \ref{oegngm-th1}.}

First, it is clear that
we have
$$ \mbox{ord}(\alpha-\overline{\alpha})=\deg p.$$ Moreover, the following relations hold
\begin{eqnarray*}
&&\mbox{ord}(\alpha(P))=\deg p \,\,\deg P,\\
&&\mbox{ord}(\overline{\alpha}(P))=(\deg q-\deg p)\deg P,\\
&&\mbox{ord}(\alpha(P)-\overline{\alpha}(P))=\deg p \,\,\deg P.
\end{eqnarray*}
The important relations
\begin{eqnarray}\label{oegngm-eqg1}
&&g_{1}(x)(\alpha(x)-\overline{\alpha}(x))=G_{1}(x)-G_{0}(x)\overline{\alpha}(x),\\
&&g_{2}(x)(\overline{\alpha}(x)-\alpha(x))=G_{1}(x)-G_{0}(x)\alpha(x)\label{oegngm-eqg2}
\end{eqnarray}
are consequences of (\ref{oegngm-g1g2}).
Observe that under the condition $2\deg p>\deg q\geq 0$ our
sequence $(G_{n}(x))_{n=0}^{\infty}$ is nondegenerate. This
follows from the fact that $\alpha(x)^{n}=\overline{\alpha}(x)^{n}$
implies ord$(\alpha)$=ord$(\overline{\alpha})$, which by Lemma
\ref{oegngm-lemord} yields a contradiction. The same is true for the
quotient $\alpha(P(x))/\overline{\alpha}(P(x))$. 
\\

In order to finish our proof, we want to show that
$g_{1}(x),g_{2}(x)\neq 0$ and
that (\ref{oegngm-eq2}) and (\ref{oegngm-eq3}) have no solutions.\\
\\
\emph{Case 1.} $\deg G_{1}>\deg G_{0}+\deg p$.\\
In this case we have
\begin{eqnarray*}
&&\mbox{ord}(G_{1}-G_{0}\overline{\alpha})=\deg G_{1},\\
&&\mbox{ord}(G_{1}-G_{0}\alpha)=\deg G_{1}.
\end{eqnarray*}
This implies
\begin{eqnarray*}
&&\mbox{ord}(G_{1}(P)-G_{0}(P)\overline{\alpha}(P))=\deg G_{1}\, \deg P,\\
&&\mbox{ord}(G_{1}(P)-G_{0}(P)\alpha(P))=\deg G_{1}\,
\deg P.
\end{eqnarray*}
Therefore we get
\begin{eqnarray*}
&&\mbox{ord}(g_{1})=\deg G_{1}-\deg p,\\
&&\mbox{ord}(g_{2})=\deg G_{1}-\deg p.
\end{eqnarray*}
Observe that from this we can conclude that $g_{1}(x),g_{2}(x)\neq 0$.
Now assume that $m,n$ is a solution of (\ref{oegngm-eq2}). Then we obtain
by calculating the order of both sides of the equations and by
using Lemma \ref{oegngm-lemord}
\begin{eqnarray}\label{oegngm-heq}
&&(\deg G_{1}-\deg p)+n\deg p=(\deg G_{1}-\deg p)\deg P+m\deg p\deg P,\\
&&(\deg G_{1}-\deg p) +n(\deg q-\deg p)=(\deg G_{1}-\deg p)\deg
P+\\ \nonumber &&\hspace*{7cm}+m(\deg q-\deg p) \deg P.
\end{eqnarray}
Subtraction yields
$$ n(2\deg p-\deg q)=m(2\deg p-\deg q)\deg P.$$
By our assumption $2\deg p>\deg q$ we derive
\begin{equation}\label{oegngm-heq2}
n=m\deg P\ ,
\end{equation}
and substituting this in (\ref{oegngm-heq}) implies
$$ (\deg G_{1}- \deg p)=(\deg G_{1}-\deg p)\deg P.$$
But this yields $\deg P=1$, which by (\ref{oegngm-heq2}) gives $m=n$, or
$\deg G_{1}=\deg p$, leading to a contradiction.

In the same way we conclude that a solution $m,n$ of (\ref{oegngm-eq3})
implies
\begin{eqnarray*}
&&(\deg G_{1}-\deg p)+n\deg p=(\deg G_{1}-\deg p)\deg P+\\
\nonumber
&&\hspace*{7cm}+m(\deg q-\deg p)\deg P,\\
&&(\deg G_{1}-\deg p)+n(\deg q-\deg p)=(\deg G_{1}-\deg p)\deg
P+\\ \nonumber &&\hspace*{7cm}+m\deg p\deg P.
\end{eqnarray*}
Again subtraction yields
$$ n(2\deg p-\deg q)=m(\deg q-2\deg p)\deg P\ ,$$
and therefore we get $n=-m\deg P$, which contradicts $\deg P\neq
0$.
\\
\\
\emph{ Case 2.} $\deg G_{1} < \deg G_{0}+\deg q-\deg p$.\\
Here we have
\begin{eqnarray*}
&&\mbox{ord}(G_{1}-G_{0}\overline{\alpha})=\deg G_{0}+\deg q-\deg p,\\
&&\mbox{ord}(G_{1}-G_{0}\alpha)=\deg G_{0}+\deg p.
\end{eqnarray*}
Thus
\begin{eqnarray*}
&&\mbox{ord}(g_{1})=\deg G_{0}+\deg q-2\deg p,\\
&&\mbox{ord}(g_{2})=\deg G_{0}.
\end{eqnarray*}
>From this we derive $g_{1}(x),g_{2}(x)\neq 0$. Again by Lemma \ref{oegngm-lemord}, for any solution $(n,m)$ of (\ref{oegngm-eq2}) we must have
\begin{eqnarray}\label{oegngm-heq3}
&&(\deg G_{0}+\deg q-2\deg p)+n\deg p=(\deg G_{0}+\deg q-\\
\nonumber &&\hspace*{6cm}-2\deg p)\deg P+m\deg p
\deg P,\\
&&\deg G_{0}+n(\deg q-\deg p)=\deg G_{0}\deg P+m(\deg q-\deg
p)\deg P.
\end{eqnarray}
Subtraction yields
$$(n-1)(2\deg p-\deg q)=(m-1)\deg P(2\deg p-\deg q)$$
and therefore
$$(n-1)=(m-1)\deg P.$$
By (\ref{oegngm-heq3}) we obtain
$$(\deg G_{0}+\deg q-\deg p)(1-\deg P)=0.$$
This yields $\deg P=1$, which again implies $n=m$, or $\deg
G_{0}+\deg q-\deg p=0$, which gives $\deg G_{1}<0$, in both cases a
contradiction.

Again we get from (\ref{oegngm-eq3})
\begin{eqnarray*}
&&(\deg G_{0}+\deg q-2\deg p)+n\deg p=\deg G_{0}\deg P+\\
\nonumber
&&\hspace*{7cm}+m(\deg q-\deg p)\deg P,\\
&&\deg G_{0}+n(\deg q-\deg p)=(\deg G_{0}+\deg q-2\deg p)\deg P+\\
\nonumber &&\hspace*{7cm}+m\deg p\deg P.
\end{eqnarray*}
Subtraction gives
$$(n-1)=-(m-1)\deg P,$$
which implies $\deg P=0$, a contradiction.
\\

Now by Lemma \ref{oegngm-mlem} we get that (\ref{oegngm-meq}) has at most
$$1+\exp(18^{9}\cdot 3)\leq \exp(18^{10})$$
solutions $n,m\in\ZZ,n,m\geq 0$ with $m\neq n$. The second part of our upper bound will follow from the proof of Theorem \ref{oegngm-th2} where a different method of proof is used and thus the proof is
finished. \hfill $\square $

\section{Proof of Theorem \ref{oegngm-th5}}

Here $(P_{n}(x))_{n=0}^{\infty}$ is an OPS and we have in the
sense of (\ref{oegngm-oeq1}) and (\ref{oegngm-oeq2})
$$ p(x)=ax+b, \,\, q(x)=d.$$
Again we want to apply Lemma \ref{oegngm-mlem} to show that the equation
\begin{equation}\label{oegngm-th7eq}
P_{n}(x)=P_{m}(S(x)),
\end{equation}
where $S(x)\in \CC[x], \deg S\geq 1$, has only finitely many
solutions $m,n\in \ZZ,m\neq n$. Let
$\alpha(x),\overline{\alpha}(x),g_{1}(x),g_{2}(x)$ be given by (\ref{oegngm-meq2}).

As above we may assume without loss of generality that $\ord(\alpha)\geq\ord(\overline{\alpha})$. By
observing $2\deg p=2>0=\deg q$, we get by Lemma \ref{oegngm-lemord} that
$$
\mbox{ord}(\alpha)=1\quad \mbox{and}\quad \mbox{ord}(\overline{\alpha})=-1.
$$
This yields
\begin{eqnarray*}
&&\mbox{ord}(\alpha-\overline{\alpha})=1,\\
&&\mbox{ord}(P_{1}-P_{0}\overline{\alpha})=1.
\end{eqnarray*}
We have to calculate $\mbox{ord}(P_{1}-P_{0}\alpha)$. 
Using that $P_0(x)=g$,
$P_1(x)=ex+f$ and the assumption that $e=ag$
we get
\begin{eqnarray*}
&&(P_1(x)-P_0(x)\alpha(x) )(P_1(x)- P_0(x)\overline{\alpha}(x))=\\
&&\hspace*{3cm}=P_1(x)^2-P_0(x)P_1(x)p(x)-P_0(x)^2q(x)=\\
&&\hspace*{3cm}=(ex+f)^2-g(ex+f)(ax+b)-g^2d=sx+t
\end{eqnarray*}
for certain $s,t\in\CC$. By invoking (a), (b) we then obtain
$$
\ord(P_1-P_0\alpha )=:w\leq 1-\ord(P_1-P_0\overline{\alpha})=
0.
$$
Observe that Lemma \ref{oegngm-lemnull} can be sharpened in this case.
Because of the fact that $\deg P_{n}=n$ the number of solutions of
(\ref{oegngm-eq1}) is zero. Furthermore it is clear that $g_{1}(x),g_{2}(x)$
cannot be zero in this case, because the following relations hold
\begin{eqnarray*}
&& \mbox{ord}(g_{1})=0,\\
&& \mbox{ord}(g_{2})=w-1<0.
\end{eqnarray*}

Now assume that $m,n\in \ZZ,m\neq n$ is a solution of (\ref{oegngm-eq2}).
Then we get
\begin{eqnarray*}
&&n=m\deg S,\\
&&(w-1)-n=[(w-1)-m]\deg S.
\end{eqnarray*}
Consequently $\deg S=1$, and therefore $m=n$, a contradiction.

In the same way we get for a solution of (\ref{oegngm-eq3}), that
\begin{eqnarray*}
&&(w-1)-n=m\deg S,\\
&&n=[(w-1)-m]\deg S.
\end{eqnarray*}
Adding the two equations gives $\deg S=1$, and thus $n=(w-1)-m$, a
contradiction because the left side of the equation is positive
and the right side negative.

By Lemma \ref{oegngm-mlem} the first part of the theorem follows and the proof is finished as the second part of the bound will follow from Theorem \ref{oegngm-th6}.
\hfill $\square $

\section{Proof of Theorem \ref{oegngm-th3}}

We start our proof with some useful lemmas.

\begin{Le}\label{oegngm-lemgcd}
Let $A,B,P\in \KK[x]$. If $\gcd(A,B)=1$ then $\gcd(A(P),B(P))=1$.
\end{Le}

This lemma is a special case of a lemma in the monograph of Schinzel \cite{schinzel-book}, page 16. It was originally proved in \cite{schinzel}.
\\

We will use the same notations as introduced in the proof of
Theorem \ref{oegngm-th1}. There we calculated the order which was defined as the negative value
of some valuation extending $1/x$ from $\KK(x)$ to the function field
$$K=\KK(x)(\sqrt{\Delta(x)},\sqrt{\Delta(P(x))})$$
of the elements $g_{1}(x),g_{2}(x)$
by using the equations (\ref{oegngm-eqg1}) and (\ref{oegngm-eqg2}). Here we want
to calculate the valuations $\nu(g_{1})$ and $\nu(g_{2})$ where $\nu$ extends $\nu_{\xi}$ to $K$ for some
$\xi\in \KK$.

\begin{Le}\label{oegngm-lemnp}
Let $(G_{n}(x))_{n=0}^{\infty}$ be a sequence of polynomials
defined by (\ref{oegngm-rec}) and assume that
$\gcd(2G_{1}-G_{0}p,\Delta)=1$. If $\nu$ is a finite valuation on $K$ with
$\nu(\Delta)>0$ then $\nu(g_{1}\sqrt{\Delta})=\nu(g_{2}\sqrt{\Delta})=0$.
\end{Le}

\emph{Proof.} We have equation (\ref{oegngm-eqg1})
$$g_{1}(x)(\alpha(x)-\overline{\alpha}(x))=G_{1}(x)-G_{0}(x)\overline{\alpha}(x),$$
which we may rewrite in the form
$$2g_{1}(x)\sqrt{\Delta(x)}=2G_{1}(x)-G_{0}(x)p(x)+G_{0}(x)\sqrt{\Delta(x)}.$$
By our assumption that $\gcd(2G_{1}-G_{0}p,\Delta)=1$ we have that
$$\nu(2G_{1}-G_{0}p)=0.$$
Because of the fact that
$$ \nu(G_{0}\sqrt{\Delta})=\nu(G_{0})+\frac{1}{2}\nu(\Delta)>0$$
we get that
$$\nu(g_{1}\sqrt{\Delta})=\nu(2g_{1}\sqrt{\Delta})=\min\{\nu(2G_{1}-G_{0}p),\nu
(G_{0}\sqrt{\Delta})\}=0$$
which was our assertion.

The same holds for $g_{2}(x)$ and therefore the proof is finished.
\hfill $\square $
\\

Assumption (4) of Theorem \ref{oegngm-th3} together with Lemma \ref{oegngm-lemgcd} imply
$$\gcd(2G_{1}(P)-G_{0}(P)p(P),\Delta(P))=1.$$
As
\begin{eqnarray*}
&&2g_{1}(P(x))\sqrt{\Delta(P(x))}=\\
&&\hspace*{2cm}=2G_{1}(P(x))-G_{0}(P(x))p(P(x))+G_{0}(P(x))\sqrt{\Delta(P(x))}
\end{eqnarray*}
we have again, as in the proof of the previous lemma, that for a finite valuation
$\nu$ on $K$ with $\nu(\Delta(P))>0$ we have $\nu(g_{1}\sqrt{\Delta(P)})=\nu(g_{2}\sqrt{\Delta
(P)})=0$.
\\
\\
{\sc Proof of Theorem \ref{oegngm-th3}.}

Our intention is to prove that the systems of equations (\ref{oegngm-eq2})
and (\ref{oegngm-eq3}) are not solvable.

Consider for example the equation
\begin{equation}\label{oegngm-eqth3}
g_{1}(x)\alpha(x)^{n}=g_{1}(P(x))\alpha(P(x))^{m}.
\end{equation}
The other equations can be handled analogously.

We have $\deg \Delta(P)=\deg \Delta\deg P>\deg \Delta>0$, as $\deg
P>1$ by assumption (2). Hence $\Delta(P)$ has a zero $\xi$ such
that
$$ \nu_{\xi}(\Delta(P))>\nu_{\xi}(\Delta)\geq 0.$$
This implies that there is a finite valuation $\nu$ on $K$ such that
$$ \nu(g_{1}(P))=-\nu(\Delta(P)).$$
Next we want to show that $\nu(\alpha(P))=0$. Indeed, as $\nu(\Delta(P))>0$ and
$$ \alpha(P(x))=\frac{p(P(x))+\sqrt{\Delta(P(x))}}{2}$$
we have
\begin{equation}\label{oegngm-heqth3}
\nu\left(\alpha(P)-\frac{1}{2}p(P)\right)>0.
\end{equation}
By assumption (3) of Theorem \ref{oegngm-th3} and Lemma \ref{oegngm-lemgcd} we have $\gcd(p(P),q(P))=1$ which
implies $\min\{\nu(p(P)),\nu(q(P))\}=0$. If $\nu(p(P))>0$ then from 
$$\nu(\Delta(P))=\nu(p(P)^{2}+4q(P))>0$$
it follows that then also $\nu(q(P))>0$ which is impossible. Therefore, $\nu(p(P))=0$.
Consequently we have $\nu(\alpha(P))=0$. In a similar fashion it follows that $\nu(\overline{\alpha}(P))=0$.

Thus equation (\ref{oegngm-eqth3}) implies
$$ \nu(g_{1})+n\nu(\alpha)=\nu(g_{1}(P)),$$
which yields
$$ n\nu(\alpha)=\nu(g_{1}(P))-\nu(g_{1})<0,$$
hence (\ref{oegngm-eqth3}) has no solution in $n$, if
$\nu(\alpha)\geq 0$ and at most one, if
$\nu(\alpha)<0$.

Studying the second equation of (\ref{oegngm-eq2}) we may conclude in the
same way that this equation has no solution in $n$, if
$\nu(\overline{\alpha})\geq 0$ and at most one if
$\nu(\overline{\alpha})<0$. Thus the system of equations
(\ref{oegngm-eq2}) may have a solution only if
$\nu(\alpha),\nu(\overline{\alpha})<0$. Observe that this is impossible since
$\alpha(x),\overline{\alpha}(x)$ are integral over $\KK[x]$, as they are zeros of the monic equation
$T^{2}-p(x)T-q(x)=0$ with coefficients in $\KK[x]$. The integral closure of $\KK[x]$ in $K$
consists of those elements $f$ such that $\nu(f)\geq 0$ for every finite valuation $\nu$
of $K$. So in particular, $\nu(\alpha)\geq 0, \nu(\overline{\alpha})\geq 0$. 
Hence (\ref{oegngm-eq2}) has no solution.
\\

The proof of the unsolvability of (\ref{oegngm-eq3}) is analogous. It is
clear that $g_{1}(x),g_{2}(x)\neq 0$ holds, because from assumption (1)
we can conclude that there is a zero $\zeta$ of $\Delta(x)$, for which we
can derive using Lemma \ref{oegngm-lemnp} that $\nu(g_{1})<0$ and $\nu(g_{2})<0$, where
$\nu$ is a finite valuation extending $\nu_{\zeta}$ to $K$. Consequently
they must be different from zero. Since Lemma \ref{oegngm-lemnull} is
true also in this case, (because $\alpha(x)/\overline{\alpha}(x)$ and
$\alpha(P(x))/\overline{\alpha}(P(x))$ are not roots of unity), we get
the first part of the assertion of Theorem \ref{oegngm-th3} by Lemma \ref{oegngm-mlem}. The second part of the bound will follow from Theorem \ref{oegngm-th4}.\hfill $\square $

\section{Proof of the Theorems \ref{oegngm-th2}, \ref{oegngm-th4} and \ref{oegngm-th6}}

We keep using the notation introduced before. Especially, let $K/\KK$ be the algebraic
function field in one variable defined by
$$ K=\KK(x,\sqrt{p(x)^{2}+4q(x)},\sqrt{p(P(x))^{2}+4q(P(x))}).$$
Now we have the following lemma.

\begin{Le}\label{oegngm-lem10}
There exists a finite subset $S\subset M_K$ of valuations of the
function field $K$ such that $\alpha(x),\overline{\alpha}(x),\alpha(P(x),\overline{\alpha}(P(x)) \in U_S$ and such that
$$|S|\leq 4\deg q (\deg P+1)+4.$$
\end{Le}

\emph{Proof.}
Let $S_{\infty}$ be the set of infinite valuations of $K$ and $S_0$ the set
 of
finite valuations of $K$.
Note that for every $\nu\in S_0$ we have
$\nu (\alpha )\geq 0$, $\nu (\overline{\alpha})\geq 0$,
$\nu (\alpha (P))\geq 0$, $\nu (\overline{\alpha}(P))\geq 0$
since these functions
are integral over ${\bf K}[x]$.
Take $S=S_{\infty}\cup S_1\cup S_2\cup S_3\cup S_4$,
where
\begin{eqnarray*}
&&S_1 =\{ \nu\in S_0 \vert\, \nu (\alpha )>0\},\\
&&S_2 =\{ \nu\in S_0 \vert\, \nu (\overline{\alpha} )>0\},\\
&&S_3 =\{ \nu\in S_0 \vert\, \nu (\alpha (P))>0\},\\
&&S_4 =\{ \nu\in S_0 \vert\, \nu (\overline{\alpha}(P) )>0\}.
\end{eqnarray*}
Then clearly $\alpha(x),\overline{\alpha}(x),\alpha(P(x),\overline{\alpha}(P(x))$ are contained in $U_S$.
Since $[K:{\bf K}(x)]\leq 4$, we have $|S_{\infty}|\leq 4$.
Further,
$\alpha(x)\cdot\overline{\alpha}(x)\cdot\alpha (P(x))\cdot\overline{\alpha}(P(x))
= q(x)\cdot q(P(x))=: Q(x)$. Therefore,
$S_1\cup S_2\cup S_3\cup S_4=: S_5:=\{ \nu\in S_0:\, \nu (Q)>0\}$.
Each of the valuations in $S_5$ is an extension to $K$ of some valuation
$\nu_{\xi}$ on ${\bf K}(x)$ corresponding to a zero $\xi$
of $Q(x)$. The polynomial $Q(x)$ has at most
$\deg Q=\deg q(\deg P+1)$ zeros, and for each of these zeros $\xi$,
the valuation $\nu_{\xi}$ can be extended in at most four ways to a
valuation on $K$. Therefore, $|S_5|\leq 4\deg q(\deg P+1)$.
This implies Lemma \ref{oegngm-lem10}. \hfill $\square $
\\

Next we want to estimate the genus of the function field $K/\KK$.
This can be done using Castelnuovo's Inequality (Theorem
\ref{oegngm-cueq}).

\begin{Le}\label{oegngm-lemg}
We denote by $g$ the genus of the function field $K/\KK$. Then
we have
$$ g\leq 2 \max\{2\deg p,\deg q\}(\deg P+1)-3.$$
\end{Le}

\emph{Proof.} First observe that we have
$$
F=\KK(x,\sqrt{\Delta(x)},\sqrt{\Delta(P(x))})=\KK(x,\sqrt{\Delta(x)})\cdot\KK(x,\sqrt{\Delta(P(x))}).$$
Let us denote $F_{1}=\KK(x,\sqrt{\Delta(x)}),
F_{2}=\KK(x,\sqrt{\Delta(P(x))})$. Thus we have
$$ F_{1}=\KK(x,y), \quad \varphi_{1}(x,y)=y^{2}-\Delta(x)=0$$
and
$$ F_{2}=\KK(x,y), \quad \varphi_{2}(x,y)=y^{2}-\Delta(P(x))=0.$$
Furthermore we denote by $g_{i}$ the genus of $F_{i}/\KK$
$(i=1,2)$. We have
$$ n_{1}=[F:F_{1}]\leq 2 \quad \mbox{and} \quad n_{2}=[F:F_{2}]\leq 2.$$
By Riemann's Inequality (Theorem \ref{oegngm-rueq}) we get the following
estimates:
\begin{eqnarray*}
&&g_{1}\leq\left([F_{1}:\KK(x)]-1\right)\cdot\left([F_{1}:\KK(y)]-1\right)\leq
\deg \Delta-1,\\
&&g_{2}\leq
\left([F_{2}:\KK(x)]-1\right)\cdot\left([F_{2}:\KK(y)]-1\right)\leq
\deg \Delta\,\deg P-1.
\end{eqnarray*}
Since $\Delta(x)=p(x)^{2}+4q(x)$ we have $\deg \Delta\leq
\max\{2\deg p,\deg q\}$. Now using Castelnuovo's Inequality
(Theorem \ref{oegngm-cueq}) we get
$$ g\leq 2(\deg \Delta-1)+2(\deg \Delta\deg P-1)+1=2\deg \Delta(\deg P+1)-3,$$
and therefore our proof is finished. \hfill $\square $
\\

Finally, we need the following lemma.

\begin{Le}\label{oegngm-lemred}
Assume $2\deg p>\deg q\geq 0$ or $\gcd(p,q)=1$ and $p,q$ not both in $\KK$. Let
$\gamma_{1},\gamma_{2}$ be non-zero elements of $K$. Then there is at most one pair
of integers $n,m$ such that
\begin{equation}\label{oegngm-ek1}
\gamma_1{\alpha (x)^n\over \overline{\alpha}(P(x))^m}\in {\bf K}^*\quad\mbox{and}\quad
\gamma_2{\overline{\alpha}(x)^n\over \overline{\alpha}(P(x))^m}\in {\bf K}^*
\end{equation}
or
\begin{equation}\label{oegngm-ek2}
\gamma_1{\alpha (x)^n\over \overline{\alpha}(P(x))^m}\in {\bf K}^*\quad\mbox{and}\quad
\gamma_2{\alpha(P(x))^m\over \overline{\alpha}(P(x))^m}\in {\bf K}^*
\end{equation}
or
\begin{equation}\label{oegngm-ek3}
\gamma_1{\overline{\alpha} (x)^n\over \overline{\alpha}(P(x))^m}\in {\bf K}^*\quad\mbox{and}\quad
\gamma_2{\alpha(P(x))^m\over \overline{\alpha}(P(x))^m}\in {\bf K}^*,
\end{equation}
respectively.
\end{Le}

\emph{Proof.} First we prove equation (\ref{oegngm-ek1}). Suppose there are two such pairs $(n_1,m_1)$, $(n_2,m_2)$.
Let $n=n_1-n_2$, $m=m_1-m_2$. Then
$(\gamma_1/\gamma_2)(\alpha (x)/\overline{\alpha}(x))^{n_i}\in {\bf K}^*$
for $i=1,2$, hence $(\alpha (x)/\overline{\alpha}(x))^n\in {\bf K}^*$.
Suppose $n\not= 0$. Then $\alpha(x)/\overline{\alpha}(x)\in{\bf K}^*$.
Using $p(x)=\alpha(x)+\overline{\alpha}(x)$, $q(x)=\alpha(x)\cdot\overline{\alpha}(x)$
it follows that $p(x)=c_1\alpha(x)$, $q(x)=c_2\alpha(x)^2$ with $c_1,c_2\in{\bf K}^*$
and so $p(x)^2=c_3q(x)$ with $c_3\in{\bf K}^*$.
But this contradicts both $2\deg p>\deg q\geq 0$ and gcd$(p,q)=1$.
It follows that $n=0$, whence $n_1=n_2$
and so $(n_1,m_1)=(n_2,m_2)$. This proves the first part of the lemma.

Now we consider equation (\ref{oegngm-ek2}). As above we assume that there are two such pairs.
Hence we get $(\alpha(P(x))/ \overline{\alpha}(P(x)))^{m}\in\KK^{*}$. This implies that either
$\alpha(P(x))/ \overline{\alpha}(P(x))\in\KK^*$ which is impossible by the same arguments
as above or $m=0$. But now, using the other expression in (\ref{oegngm-ek2}) we get that also $n=0$ must
hold. Consequently we have $(n_1,m_1)=(n_2,m_2)$. Thus we proved the second part of our lemma.

The arguments for (\ref{oegngm-ek3}) are the same as for (\ref{oegngm-ek2}). This proves the lemma also in 
the third case.
\hfill $\square$
\\

Assume that $n,m$ are integers satisfying $G_n(x)=c\,G_m(P(x))$ for some
$c\in{\bf K}^*$.
It follows that
$$
\beta_1x_1+\beta_2x_2+\beta_3x_3 =1
$$
where
\begin{equation}\label{oegngm-hauptgl}
\beta_1:={g_1(x)\over g_2(P(x))},\,\,
\beta_2:={g_2(x)\over g_2(P(x))},\,\,
\beta_3:=-{g_1(P(x))\over g_2(P(x))},
\end{equation}
$$
x_1=c^{-1}{\alpha (x)^n\over\overline{\alpha} (P(x))^m},\,\,
x_2=c^{-1}{\overline{\alpha} (x)^n\over\overline{\alpha} (P(x))^m},\,\,
x_3={\alpha (P(x))^m\over\overline{\alpha} (P(x))^m}\, .
$$
>From the choice of $S$ in Lemma \ref{oegngm-lem10} and from the fact that $c\in\KK^*$, $\KK^*\subset U_S$, it follows that $x_1,x_2,x_3\in U_S$.
Lemma \ref{oegngm-lemred} implies that any given pair of elements $(x_{i},x_{j})$ gives rise to
at most one pair $(n,m)$, especially any triple $(x_1,x_2,x_3)$ induces at most one 
solution $(n,m)$ of the equation in consideration.

By Theorem \ref{oegngm-fmt}, either
$\beta_1x_1,\beta_2x_2,\beta_3x_3$ all belong to ${\bf K}^*$,
which by Lemma \ref{oegngm-lemred} is possible for at most one pair $(n,m)$,
or $(x_1,x_2,x_3)$ lies in one of at most
$\log (g+2)\cdot(4e)^{4s+2}$ proper linear subspaces of $K^3$, where
$s$ denotes the cardinality of the set of valuations $S$ introduced by Lemma \ref{oegngm-lem10}.
That is, $(x_1,x_2,x_3)$ satisfies one of at most
$\log (g+2)(4e)^{4s+2}$ relations of the shape
\begin{equation}\label{oegngm-eqns}
\gamma_1x_1+\gamma_2x_2+\gamma_3x_3=0
\end{equation}
 with
$(\gamma_1,\gamma_2,\gamma_3)$ a non-zero triple in $K^3$.
Assume for the moment that $\gamma_i\not=0$ for $i=1,2,3$
and write
$\Delta_{ij}=\gamma_j^{-1}(\beta_i\gamma_j-\beta_j\gamma_i)$.
Assume for the moment also that all $\Delta_{ij}$ are non-zero.
Then we have
$$
\Delta_{13}x_1+\Delta_{23}x_2=1,\quad
\Delta_{12}x_1+\Delta_{32}x_3=1,\quad
\Delta_{21}x_2+\Delta_{31}x_3=1.
$$
In fact it suffices to consider one of these equations for example the first one
$$\Delta_{13}x_1+\Delta_{23}x_2=1.$$
Lemma \ref{oegngm-lemred} implies that there is at most one pair $(n,m)$ such that both
quantities $\Delta_{13}x_1$ and $\Delta_{23}x_2$ belong to ${\bf K}$.
Theorem \ref{oegngm-evs} implies that there are at most
$2\cdot 7^{2s}$ pairs $(x_1,x_2)$ such that at
least one of these quantities does not belong to ${\bf K}$.
It follows that there are at most $1+2\cdot 7^{2s}$ pairs $(n,m)$
for which $\gamma_1x_1+\gamma_2x_2+\gamma_3x_3=0$.

Next, we handle the case that one of the $\Delta_{ij}$, where $(i,j)=(1,3)$ or $(2,3)$, is zero. We assume that all $\gamma_{i}\neq 0$ for $i=1,2,3$.
It is clear that $\Delta_{ij}=0$ implies also $\Delta_{ji}=0$. Moreover, we
remark that if $\Delta_{ij}=0$ then neither $\Delta_{ik}=0$ nor $\Delta_{jk}=0$ where
$\{i,j,k\}=\{1,2,3\}$ can hold. Because assume that $\Delta_{ij}=0$ and $\Delta_{ik}=0$. This
implies that also $\Delta_{jk}=0$ which means that all the quantities $\Delta_{13},\ldots,
\Delta_{31}$ are zero. Hence we would get
$$\beta_1 x_1+\beta_2 x_2+\beta_3 x_3=(\gamma_1 x_1+\gamma_2 x_2+\gamma_3 x_3)\left(\frac{\beta_3}
{\gamma_3}\right)=1,$$
which is a contradiction to equation (\ref{oegngm-eqns}).
>From this discussion it follows that $\Delta_{ij}=0$ for $(i,j)=(1,3)$ or $(2,3)$ implies that we have
$$\Delta_{ik}x_{i}+\Delta_{jk}x_{j}=1,$$
with non-zero $\Delta_{ik},\Delta_{jk}$ and $\{i,j,k\}=\{1,2,3\}$.
As above, Theorem \ref{oegngm-evs} implies that there are at most $2\cdot 7^{2s}$ pairs $(x_{i},x_{j})$
such that at least one of these quantities does not belong to $\KK$ which can happen for at
most one pair $(n,m)$ by Lemma \ref{oegngm-lemred}.

Finally, we handle the case that $\gamma_i =0$ for some $i=1,2,3$. Observe that at most one of
the $\gamma_{i}$ can be zero.
Now we assume that $\gamma_{1}=0$. Then (\ref{oegngm-eqns}) becomes
$$\gamma_{2}x_2+\gamma_3 x_3=0.$$
Therefore we have
$$\beta_1 x_1+\left(\beta_3-\frac{\gamma_3}{\gamma_2}\beta_2\right)x_3=1.$$
This implies, under the condition $\beta_3-(\gamma_3 / \gamma_2)\beta_2\neq 0$, that there are at most $1+2\cdot 7^{2s}$ pairs of solutions $(n,m)$. If this condition is not
satisfied then we have
$$\beta_1 x_1=1 \quad \mbox{and}\quad \beta_{2}x_2 +\beta_3 x_3=0$$
which means that (\ref{oegngm-hauptgl}) has a vanishing subsum.
The cases $\gamma_{2}=0$ and $\gamma_3 =0$ are totally analogous. We get in both cases
that there are at most $1+2\cdot 7^{2s}$ pairs of solutions $(n,m)$, if we assume that
(\ref{oegngm-hauptgl}) has no vanishing subsum. 

The cases for vanishing subsums of equation (\ref{oegngm-hauptgl}) can be rewritten in the following
form:
\begin{eqnarray*}
&&\left\{\begin{array}{l}
       g_{1}(x)\alpha(x)^{n}=c\, g_{2}(P(x))\overline{\alpha}(P(x))^{m}\\
       g_{2}(x)\overline{\alpha}(x)^{n}=c\, g_{1}(P(x))\alpha(P(x))^{m}\\
       \end{array}\right.\\
&&\left\{\begin{array}{l}
       g_{2}(x)\overline{\alpha}(x)^{n}=c\, g_{2}(P(x))\overline{\alpha}(P(x))^{m}\\
       g_{1}(x)\alpha(x)^{n}=c\, g_{1}(P(x))\alpha(P(x))^{m}\\
       \end{array}\right.\\
&&\left\{\begin{array}{l}
       g_{1}(x)\alpha(x)^{n}+g_{2}(x)\overline{\alpha}(x)^{n}=0\\
       g_{1}(P(x))\alpha(P(x))^{m}+g_{2}(P(x))\overline{\alpha}(P(x))^{m}=0\\
       \end{array}\right.
\end{eqnarray*}
But the first two systems of equations are, up to the constant $c$, the same as (\ref{oegngm-eq3}), (\ref{oegngm-eq2}), respectively, while the third system is (\ref{oegngm-eq1}). In the proof of Theorems \ref{oegngm-th1}, \ref{oegngm-th3} and \ref{oegngm-th5} we showed that (\ref{oegngm-eq3}), (\ref{oegngm-eq2}) are unsolvable by calculating the values of certain infinite or finite valuations. Since for any of these valuations $\nu$ we have $\nu(c)=0$, the same argument applies to the first two systems above and we conclude that these systems are unsolvable. Further it has been proved that (\ref{oegngm-eq1}) has at most one solution $(n,m)$, therefore the third system above has at most one solution $(n,m)$.
\\

Altogether, we get for the number of pairs $(n,m)$ of integers with $n\neq m$ satisfying $G_{n}(x)=c\,G_{m}(P(x))$ for some $c\in\KK^*$ the upper bound
$$
1+\log(g+2)(4e)^{4s+2}\cdot \left[7+12\cdot 7^{2s}\right]\leq
\log(g+2)(4e)^{4s+2}7^{2s+2}.
$$
Now using the estimation for the genus of our function field (Lemma \ref{oegngm-lemg}) and the estimate
for the cardinality of the set $S$ (Lemma \ref{oegngm-lem10}) we get that the number of solutions
can be bounded by
\begin{eqnarray*}
&&C(p,q,P)=\tilde{C}(p,q,P)=\log(2\max\{2\deg p,\deg q\}(\deg P+1))\cdot\\
&&\hspace*{4cm}\cdot (4e)^{16\deg q(\deg P+1)+18}7^{8\deg q(\deg P +1)+10}.
\end{eqnarray*}

Last observe that in Theorem \ref{oegngm-th2} we have assumed that $2\deg p>\deg q$ and in Theorem \ref{oegngm-th6} we
have
$$p(x)=ax+b\quad \mbox{and}\quad q(x)=d,$$
i.e., $\deg q=0$ and $\deg p=1$. This proves the bounds as claimed.
\hfill
$\square $

\section{Acknowledgment}

The authors are most grateful to an anonymous referee for
various suggestions improving an earlier draft of the paper. Especially, the observation that we can
handle the more general equation $G_{n}(x)=c\,G_{m}(P(x))$ ($c$ variable) with our method was suggested by him.

\begin{thebibliography}{99}
\bibitem{ba} {\sc A.\ Baker}, {\it New advances in transcendence theory}, Cambridge
Univ. Press, Cambridge, 1988.
\bibitem{b+s} {\sc F.\ Beukers and H.\ P.\ Schlickewei}, The equations $x+y=1$
in finitely generated groups, {\it Acta Arith.} {\bf 78} (1996),
189-199.
\bibitem{beu+tij} {\sc F.\ Beukers and R.\ Tijdeman}, On the multiplicities of binary complex
recurrences, {\it Compos. Math.} {\bf 51} (1984), 193-213.
\bibitem{B+T}{\sc Y. Bilu and R. F. Tichy},  The diophantine equation $f(x)=g(y)$,
{\it Acta Arith.} {\bf 95} (2000), no. 3, 261-288.
\bibitem{b+e} {\sc P. Borwein and T. Erd\'elyi}, {\it Polynomials and
    Polynomial Inequalities}, Springer Verlag, Berlin, 1995.
\bibitem{b+m} {\sc W.\ D.\ Brownawell and D.\ W. Masser}, Vanishing sums in function
fields, {\it Proc. Cambridge Philos. Soc.} {\bf 100} (1986),
427-434.
\bibitem{ch} {\sc T.\ S.\ Chihara}, {\it An Introduction to Orthogonal
    Polynomials}, Gordon and Breach Science Publishers, New York - London -
  Paris, 1978.
 \bibitem{D+T} {\sc A. Dujella and R.F. Tichy}, Diophantine
 equations for second order recursive sequences of polynomials,
 {\it Quarterly Journal of Mathematics (Oxford)} {\bf 52} (2001), no. 2, 161-169.
\bibitem{ev0} {\sc J.\-H.\ Evertse}, On sums of $S$-units and linear recurrences,
{\it Comp. Math.} {\bf 53} (1984), 225-244.
\bibitem{ev1} {\sc J.\-H.\ Evertse}, On equations in two $S$-units over
function fields of characteristic $0$, {\it Acta Arith.} {\bf 47}
(1986), 233 -253.
\bibitem{ev+g} {\sc J.\-H.\ Evertse and K.\ Gy\H{o}ry}, On the number of solutions
of weighted unit equations, {\it Compositio Math.} {\bf 66}
(1988), 329-354.
\bibitem{ev+g+st} {\sc J.\-H.\ Evertse, K.\ Gy\H{o}ry, C.\ L.\ Stewart and R.\ Tijdeman},
$S$-unit equations and their applications. In: {\it New advances
in transcendence theory} (ed. by {\sc A.\ Baker}), 110-174,
Cambridge Univ. Press, Cambridge, 1988.
\bibitem{ev+s} {\sc J.\-H.\ Evertse and H.\-P.\ Schlickewei}, The Absolute Subspace
Theorem and linear equations with unknowns from a multiplicative
group, {\it
  Number Theory in Progress} Vol. 1 (Zakopane-Ko\'scielisko, 1997), 121-142,
de Gruyter, Berlin, 1999.
\bibitem{ev+schl+schm} {\sc J.\-H.\ Evertse, H.\-P.\ Schlickewei and W.\ M.\ Schmidt}, Linear
equations in variables which lie in a multiplicative group, {\it Ann. Math.} {\bf 155} (2002), 1-30.
\bibitem{glvdp} {\sc J.\ P.\ Glass, J.\ H.\ Loxton and A.\ J.\ van der
    Poorten}, Identifying a rational function, {\it
    C. R. Math. Rep. Acad. Sci. Canada} {\bf 3} (1981), 279-284. Corr. {\bf 4}
  (1982), 309-314.
\bibitem{vdP+s} {\sc J.\ van der Poorten and H.\ P.\ Schlickewei}, {\it The growth conditions
for recurrence sequences}, Macquarie Univ. Math. Rep. 82-0041,
North Ryde, Australia, 1982.
\bibitem{schinzel} {\sc A.\ Schinzel}, Reducibility of polynomials in several variables, {\it Bull. Acad. Polon. Sci., Ser. Sci. Math.} {\bf 11} (1963), 633-638.
\bibitem{schinzel-book} {\sc A.\ Schinzel}, {\it Polynomials with special regard to reducibility}, Cambridge University Press, Cambridge - New York, 2000.
\bibitem{sch} {\sc H.\ P.\ Schlickewei}, The multiplicity of binary recurrences,
{\it Invent. Math.} {\bf 129} (1997), 11-36.
\bibitem{schm2} {\sc W.\ M.\ Schmidt}, The zero multiplicity of linear recurrence sequences,
{\it Acta Math.} {\bf 182} (1999), 243-282.
\bibitem{st} {\sc H.\ Stichtenoth}, {\it Algebraic Function Fields and Codes}, Springer
Verlag, Berlin, 1993.
\bibitem{sz} {\sc G.\ Szeg\H{o}}, {\it Orthogonal Polynomials}, American
  Mathematical Society Colloquium Publications Vol. 23, Providence, Rhode Island, 1939.
\end{thebibliography}

\hspace{3cm}

\noindent{\sc Clemens Fuchs\\
Institut f\"ur Mathematik\\
TU Graz\\
Steyrergasse 30\\
A-8010 Graz, Austria\\
e-mail: {\sf clemens.fuchs@tugraz.at}}

\hspace{0.8cm}

\noindent{\sc Attila Peth\H{o}\\
Institute for Mathematics and Informatics\\
University of Debrecen\\
Debrecen Pf. 12\\
H-4010 Debrecen, Hungary\\
e-mail: {\sf pethoe@math.klte.hu}}

\hspace{0.8cm}

\noindent{\sc Robert F. Tichy\\
Institut f\"ur Mathematik\\
TU Graz\\
Steyrergasse 30\\
A-8010 Graz, Austria\\
e-mail: {\sf tichy@tugraz.at}}

\end{document}