Exercise 15.2.7

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

The proof of Theorem 15.2.5 uses induction on $n$.
\be
\item[(a)] Assume that $n$ is even. In (15.18), we gave a formula for $Q_{n+1}(u)$ in terms of $Q_n(u)$ and $Q_{n-1}(u)$. Derive the corresponding formula for $P_{n+1}(u)$.
\item[(b)] Suppose that polynomials $P_n(u),Q_n(u)$ satisfy all of the conditions of the theorem except for the requirement that they be relatively prime. Since $\Z[u]$ is a $UFD$, we can write $P_n(u) = C_n(u)	ilde{P}_n(u), Q_n(u) = C_n(u) 	ilde{Q}_n(u)$, where $C_n(u), 	ilde P_n(u),	ilde Q_n(u) \in \Z[u]$ and $	ilde P_n(u), 	ilde Q_n(u)$ are relatively prime. Prove that we can assume that $	ilde Q_n(0) = 1$ and that $	ilde P_n(u), 	ilde Q_n(u)$ satisfy all conditions of Theorem 15.2.5.
\item[(c)] Complete the inductive step of the proof when $n$ is odd.
\ee

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} 
\item[(a,c)] We will prove the theorem by induction on $n$. The theorem holds for $n=1,n=2$  with $P_1(u) =  Q_1(u) = 1$, and $P_2(u) = 2,Q_2(u) = 1+u$ (misprint in Cox p. 477).
Now assume that it holds for $n-1$ and $n$.

$\bullet$
If $n$ is even,
\begin{align*}
& \varphi((n-1)x) = \varphi(x)\frac{P_{n-1}\left(\varphi^4(x)ight)}{Q_{n-1}\left(\varphi^4(x)ight)}, \
 &\varphi(nx) = \varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)} \varphi'(x).
  \end{align*}
 Using (15.13), we obtain
\begin{align*}
\varphi\left((n+1)xight) &= - \varphi\left( (n-1)x) ight) + \frac{2 \varphi(nx) \varphi'(x)}{1+\varphi^2(nx) \varphi^2(x)}\
&=- \varphi(x) \frac{P_{n-1}\left(\varphi^4(x)ight)}{Q_{n-1}\left(\varphi^4(x)ight)} + \frac{2 \left(\varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)} \varphi'(x) ight) \varphi'(x)}{1+\left(\varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)} \varphi'(x) ight)^2 \varphi^2(x)}.\
\end{align*}
To simplify, we write $a = \varphi(x), p_n = P_n(\varphi^4(x)), q_n = Q_n(\varphi^4(x))$.

Then, using $\varphi'(x)^2 = 1 - \varphi^4(x)$,
\begin{align*}
\varphi\left((n+1)xight) &= a \left[ -\frac{p_{n-1}}{q_{n-1}} + \frac{2 (1-a^4)\frac{p_n}{q_n} }{1 + a^4(1-a^4) \frac{p_n^2}{q_n^2}} ight] \
&=a \left[  -\frac{p_{n-1}}{q_{n-1}} + \frac{2(1-a^4)p_nq_n}{q_n^2+a^4(1-a^4)p_n^2}ight] \
&=a \frac {-p_{n-1}(q_n^2 + a^4(1-a^4) p_n^2) + 2(1-a^4) p_nq_nq_{n-1}}{q_{n-1}(q_n^2 + a^4(1-a^4)p_n^2)},
\end{align*}
that is
$$\varphi\left((n+1)xight) = \varphi(x) \frac{P_{n+1}(\varphi^4(x))}{Q_{n+1}(\varphi^4(x))},$$
where
\begin{align*}
P_{n+1}(u) &= -P_{n-1}(u) (Q_n^2(u) + u(1-u) P_n^2(u)) + 2(1-u) P_n(u)Q_n(u) Q_{n-1}(u),\
Q_{n+1}(u) &=Q_{n-1}(u)(Q_n^2(u) + u(1-u) P_n^2(u)).
\end{align*}
Verification : with $n = 2$, we obtain $P_3(u) = 3 - 6u - u^2, Q_3(u) = 1 + 6u - 3u^2$, which gives the tripling formula (15.17).

\qquad

$\bullet$ If $n$ is odd,
\begin{align*}
& \varphi((n-1)x) = \varphi(x)\frac{P_{n-1}\left(\varphi^4(x)ight)}{Q_{n-1}\left(\varphi^4(x)ight)} \varphi'(x), \
 &\varphi(nx) = \varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)} .
  \end{align*}
  Then(15.13) gives
  \begin{align*}
\varphi\left((n+1)xight) &= - \varphi\left( (n-1)x) ight) + \frac{2 \varphi(nx) \varphi'(x)}{1+\varphi^2(nx) \varphi^2(x)}\
&=- \varphi(x) \frac{P_{n-1}\left(\varphi^4(x)ight)}{Q_{n-1}\left(\varphi^4(x)ight)}  \varphi'(x)+ \frac{2 \left(\varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)}  ight) \varphi'(x)}{1+\left(\varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)}  ight)^2 \varphi^2(x)}\
&=\varphi(x) \left[ -  \frac{P_{n-1}\left(\varphi^4(x)ight)}{Q_{n-1}\left(\varphi^4(x)ight)} + \frac{2 \left(\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)}  ight) }{1+\left(\varphi(x)\frac{P_{n}\left(\varphi^4(x)ight)}{Q_{n}\left(\varphi^4(x)ight)}  ight)^2 \varphi^2(x)}ight] \varphi'(x)
\end{align*}
With the same notations as in the even case, and with $a' = \varphi'(x)$, 
\begin{align*}
\varphi\left((n+1)xight)&= a \left[ -\frac{p_{n-1}}{q_{n-1}} + \frac{2 \frac{p_n}{q_n}}{1 + a^4 \frac{p_n^2}{q_n^2}}ight] a'\
&= a \left[ -\frac{p_{n-1}}{q_{n-1}}  +\frac{ 2 p_n q_n}{q_n^2 + a^4 p_n^2}ight] a' \
&=a\left[ \frac{-p_{n-1} (q_n^2 + a^4 p_n^2) + 2 p_nq_nq_{n-1}} {q_{n-1}(q_n^2 + a^4 p_n^2)}ight] a'
\end{align*}
that is
$$\varphi\left((n+1)xight) = \varphi(x) \frac{P_{n+1}(\varphi^4(x))}{Q_{n+1}(\varphi^4(x))}\varphi'(x),$$
where
\begin{align*}
P_{n+1}(u) &= -P_{n-1}(u) (Q_n^2(u) + u P_n^2(u)) + 2 P_n(u)Q_n(u) Q_{n-1}(u),\
Q_{n+1}(u) &=Q_{n-1}(u)(Q_n^2(u) + u P_n^2(u)).
\end{align*}
The induction is done, and the induction formulas concerning $P_{n}, Q_{n}$ are
$$\begin{array}{ll}
&	ext {for } n 	ext { even},\
P_{n+1}(u) &= -P_{n-1}(u) (Q_n^2(u) + u(1-u) P_n^2(u)) + 2(1-u) P_n(u)Q_n(u) Q_{n-1}(u),\
Q_{n+1}(u) &=Q_{n-1}(u)(Q_n^2(u) + u(1-u) P_n^2(u)),\
&	ext {for } n 	ext { odd},\
P_{n+1}(u) &= -P_{n-1}(u) (Q_n^2(u) + u P_n^2(u)) + 2 P_n(u)Q_n(u) Q_{n-1}(u),\
Q_{n+1}(u) &=Q_{n-1}(u)(Q_n^2(u) + u P_n^2(u)).
\end{array}
$$
Note that we can take $P_0 = 0, Q_1 = 1$ ( and $P_1 = 1, Q_1 = 1$).

\bigskip

We give a Sage function to compute $P_n,Q_n$:
\begin{verbatim}
R.<u> = ZZ[]

def divisionPolynomial(n):
    P0, Q0 = 0, 1
    P1, Q1 = 1, 1
    for i in range(n):
        if i % 2 != 0:
            S = Q1^2 + u * (1-u) *P1^2
            P2 = -P0 * S + 2 * (1-u) * P1 * Q1 * Q0
            Q2 = Q0  * S
        else:
            S = Q1^2 + u * P1^2
            P2 = -P0 * S + 2 * P1 * Q1 * Q0
            Q2 = Q0  * S
        D = gcd(P2,Q2)
        (P2, Q2) = (P2/D, Q2/D)
        (P0, Q0) = (P1, Q1)
        (P1, Q1) = (P2, Q2)
    return (P0,Q0)
    
P5, Q5 = divisionPolynomial(5); P5,Q5
\end{verbatim}
$$u^{6} + 50u^{5} - 125u^{4} + 300u^{3} - 105u^{2} - 62u + 5,  5u^{6} - 62u^{5} - 105u^{4} + 300u^{3} - 125u^{2} + 50u + 1$$
\begin{verbatim}
P5.factor(), Q5.factor()
\end{verbatim}
$$(u^{2} - 2u + 5) \cdot (u^{4} + 52u^{3} - 26u^{2} - 12u + 1), (5u^{2} - 2u + 1) \cdot (u^{4} - 12u^{3} - 26u^{2} + 52u + 1)$$

\item[(b)] 
Since $\Z$ is a UFD, the same is true for $\Z[u]$ by Theorem A.5.6.
Thus we can write $P_n(u) = C_n(u) 	ilde{P}_n(u), Q_n(u) = C_n(u) 	ilde{Q}_n(u)$, where $C_n(u), 	ilde P_n(u),	ilde Q_n(u) \in \Z[u]$ and $	ilde P_n(u), 	ilde Q_n(u)$ are relatively prime.

Since $Q_n(0) = 1$, then $C_n(0) 	ilde{Q}_n(0) = 1$, where $C_n(0), 	ilde{Q}_n(0)$ are integers, thus $	ilde{Q}_n(0) = \pm 1$.

If $	ilde{Q}_n(0) = 1$, we are done, and if $	ilde{Q}_n(0) = -1$ We replace $	ilde{P}_n, 	ilde{Q}_n$ by $-	ilde{P}_n, - 	ilde{Q}_n$, which satisfy all conditions of Theorem 15.2.5.
\end{proof}

Exercise 15.2.7

Answers

Comments

Exercise 15.2.7

Answers

Comments

Add answer