doc/polynomial/diag_rational.tex

   1 %% This LaTeX-file was created by <bruno> Sun Feb 16 14:19:08 1997
   2 %% LyX 0.10 (C) 1995 1996 by Matthias Ettrich and the LyX Team
   3
   4 %% Don't edit this file unless you are sure what you are doing.
   5 \documentclass[12pt,a4paper,oneside,onecolumn]{article}
   6 \usepackage[]{fontenc}
   7 \usepackage[latin1]{inputenc}
   8 \usepackage[dvips]{epsfig}
   9
  10 %%
  11 %% BEGIN The lyx specific LaTeX commands.
  12 %%
  13
  14 \makeatletter
  15 \def\LyX{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}%
  16 \newcommand{\lyxtitle}[1] {\thispagestyle{empty}
  17 \global\@topnum\z@
  18 \section*{\LARGE \centering \sffamily \bfseries \protect#1 }
  19 }
  20 \newcommand{\lyxline}[1]{
  21 {#1 \vspace{1ex} \hrule width \columnwidth \vspace{1ex}}
  22 }
  23 \newenvironment{lyxsectionbibliography}
  24 {
  25 \section*{\refname}
  26 \@mkboth{\uppercase{\refname}}{\uppercase{\refname}}
  27 \begin{list}{}{
  28 \itemindent-\leftmargin
  29 \labelsep 0pt
  30 \renewcommand{\makelabel}{}
  31 }
  32 }
  33 {\end{list}}
  34 \newenvironment{lyxchapterbibliography}
  35 {
  36 \chapter*{\bibname}
  37 \@mkboth{\uppercase{\bibname}}{\uppercase{\bibname}}
  38 \begin{list}{}{
  39 \itemindent-\leftmargin
  40 \labelsep 0pt
  41 \renewcommand{\makelabel}{}
  42 }
  43 }
  44 {\end{list}}
  45 \def\lxq{"}
  46 \newenvironment{lyxcode}
  47 {\list{}{
  48 \rightmargin\leftmargin
  49 \raggedright
  50 \itemsep 0pt
  51 \parsep 0pt
  52 \ttfamily
  53 }%
  54 \item[]
  55 }
  56 {\endlist}
  57 \newcommand{\lyxlabel}[1]{#1 \hfill}
  58 \newenvironment{lyxlist}[1]
  59 {\begin{list}{}
  60 {\settowidth{\labelwidth}{#1}
  61 \setlength{\leftmargin}{\labelwidth}
  62 \addtolength{\leftmargin}{\labelsep}
  63 \renewcommand{\makelabel}{\lyxlabel}}}
  64 {\end{list}}
  65 \newcommand{\lyxletterstyle}{
  66 \setlength\parskip{0.7em}
  67 \setlength\parindent{0pt}
  68 }
  69 \newcommand{\lyxaddress}[1]{
  70 \par {\raggedright #1
  71 \vspace{1.4em}
  72 \noindent\par}
  73 }
  74 \newcommand{\lyxrightaddress}[1]{
  75 \par {\raggedleft \begin{tabular}{l}\ignorespaces
  76 #1
  77 \end{tabular}
  78 \vspace{1.4em}
  79 \par}
  80 }
  81 \newcommand{\lyxformula}[1]{
  82 \begin{eqnarray*}
  83 #1
  84 \end{eqnarray*}
  85 }
  86 \newcommand{\lyxnumberedformula}[1]{
  87 \begin{eqnarray}
  88 #1
  89 \end{eqnarray}
  90 }
  91 \makeatother
  92
  93 %%
  94 %% END The lyx specific LaTeX commands.
  95 %%
  96
  97 \pagestyle{plain}
  98 \setcounter{secnumdepth}{3}
  99 \setcounter{tocdepth}{3}
 100
 101 %% Begin LyX user specified preamble:
 102 \catcode`@=11 % @ ist ab jetzt ein gewoehnlicher Buchstabe
 103 \def\Res{\mathop{\operator@font Res}}
 104 \def\ll{\langle\!\langle}
 105 \def\gg{\rangle\!\rangle}
 106 \catcode`@=12 % @ ist ab jetzt wieder ein Sonderzeichen
 107
 108
 109 %% End LyX user specified preamble.
 110 \begin{document}
 111
 112
 113 \title{The diagonal of a rational function}
 114
 115 \begin{description}
 116
 117 \item [Theorem:]~
 118
 119 \end{description}
 120
 121 Let  \( M \) be a torsion-free  \( R \)-module, and  \( d>0 \). Let
 122 \[
 123 f=\sum _{n_{1},...,n_{d}}a_{n_{1},...,n_{d}}\, x_{1}^{n_{1}}\cdots x_{d}^{n_{d}}\in M[[x_{1},\ldots x_{d}]]\]
 124 be a rational function,
 125 i.e. there are  \( P\in M[x_{1},\ldots ,x_{d}] \) and  \( Q\in R[x_{1},\ldots ,x_{d}] \) with  \( Q(0,\ldots ,0)=1 \) and  \( Q\cdot f=P \). Then the full diagonal of  \( f \)
 126 \[
 127 g=\sum ^{\infty }_{n=0}a_{n,\ldots ,n}\, x_{1}^{n}\]
 128 is
 129 a D-finite element of  \( M[[x_{1}]] \), w.r.t.  \( R[x_{1}] \) and  \( \{\partial _{x_{1}}\} \).
 130
 131 \begin{description}
 132
 133 \item [Proof:]~
 134
 135 \end{description}
 136
 137 From the hypotheses,  \( M[[x_{1},\ldots ,x_{d}]] \) is a torsion-free differential module over
 138  \( R[x_{1},\ldots ,x_{d}] \) w.r.t. the derivatives  \( \{\partial _{x_{1}},\ldots ,\partial _{x_{d}}\} \), and  \( f \) is a D-finite element of  \( M[[x_{1},\ldots ,x_{d}]] \) over
 139  \( R[x_{1},\ldots ,x_{d}] \) w.r.t.  \( \{\partial _{x_{1}},\ldots ,\partial _{x_{d}}\} \). Now apply the general diagonal theorem ([1], section 2.18)
 140  \( d-1 \) times.
 141
 142 \begin{description}
 143
 144 \item [Theorem:]~
 145
 146 \end{description}
 147
 148 Let  \( R \) be an integral domain of characteristic 0 and  \( M \) simultaneously
 149 a torsion-free  \( R \)-module and a commutative  \( R \)-algebra without zero divisors.
 150 Let
 151 \[
 152 f=\sum _{m,n\geq 0}a_{m,n}x^{m}y^{n}\in M[[x,y]]\]
 153  be a rational function. Then the diagonal of  \( f \)
 154 \[
 155 g=\sum ^{\infty }_{n=0}a_{n,n}\, x^{n}\]
 156  is algebraic
 157 over  \( R[x] \).
 158
 159 \begin{description}
 160
 161 \item [Motivation~of~proof:]~
 162
 163 \end{description}
 164
 165 The usual proof ([2]) uses complex analysis and works only for  \( R=M=C \).
 166 The idea is to compute
 167 \[
 168 g(x^{2})=\frac{1}{2\pi i}\oint _{|z|=1}f(xz,\frac{x}{z})\frac{dz}{z}\]
 169 This integral, whose integrand is a rational
 170 function in  \( x \) and  \( z \), is calculated using the residue theorem. Since
 171  \( f(x,y) \) is continuous at  \( (0,0) \), there is a  \( \delta >0 \) such that  \( f(x,y)\neq \infty  \) for  \( |x|<\delta  \),  \( |y|<\delta  \). It follows
 172 that for all  \( \varepsilon >0 \) and  \( |x|<\delta \varepsilon  \) all the poles of  \( f(xz,\frac{x}{z}) \) are contained in  \( \{z:|z|<\varepsilon \}\cup \{z:|z|>\frac{1}{\varepsilon }\} \). Thus the
 173 poles of  \( f(xz,\frac{x}{z}) \), all algebraic functions of  \( x \) -- let's call them  \( \zeta _{1}(x),\ldots \zeta _{s}(x) \) --,
 174 can be divided up into those for which  \( |\zeta _{i}(x)|=O(|x|) \) as  \( x\rightarrow 0 \) and those for which
 175  \( \frac{1}{|\zeta _{i}(x)|}=O(|x|) \) as  \( x\rightarrow 0 \). It follows from the residue theorem that for  \( |x|<\delta  \)
 176 \[
 177 g(x^{2})=\sum _{\zeta =0\vee \zeta =O(|x|)}\Res _{z=\zeta }\, f(xz,\frac{x}{z})\]
 178  This is algebraic
 179 over  \( C(x) \). Hence  \( g(x) \) is algebraic over  \( C(x^{1/2}) \), hence also algebraic over  \( C(x) \).
 180
 181 \begin{description}
 182
 183 \item [Proof:]~
 184
 185 \end{description}
 186
 187 Let
 188 \[
 189 h(x,z):=f(xz,\frac{x}{z})=\sum ^{\infty }_{m,n=0}a_{m,n}x^{m+n}z^{m-n}\in M[[xz,xz^{-1}]]\]
 190 Then  \( g(x^{2}) \) is the coefficient of  \( z^{0} \) in  \( h(x,z) \). Let  \( N(x,z):=z^{d}Q(xz,\frac{x}{z}) \) (with  \( d:=\max (\deg _{y}P,\deg _{y}Q) \)) be ``the denominator''
 191 of  \( h(x,z) \). We have  \( N(x,z)\in R[x,z] \) and  \( N\neq 0 \) (because  \( N(0,z)=z^{d} \)). Let  \( K \) be the quotient field of
 192  \( R \). Thus  \( N(x,z)\in K[x][z]\setminus \{0\} \).
 193
 194 It is well-known (see [3], p.64, or [4], chap. IV, §2, prop. 8, or
 195 [5], chap. III, §1) that the splitting field of  \( N(x,z) \) over  \( K(x) \) can be embedded
 196 into a field  \( L((x^{1/r})) \), where  \( r \) is a positive integer and  \( L \) is a finite-algebraic
 197 extension field of  \( K \), i.e. a simple algebraic extension  \( L=K(\alpha )=K\alpha ^{0}+\cdots +K\alpha ^{u-1} \).
 198
 199  \( \widetilde{M}:=(R\setminus \{0\})^{-1}\cdot M \) is a  \( K \)-vector space and a commutative  \( K \)-algebra without zero divisors.
 200  \( \widehat{M}:=\widetilde{M}\alpha ^{0}+\cdots +\widetilde{M}\alpha ^{u-1} \) is an  \( L \)-vector space and a commutative  \( L \)-algebra without zero divisors.
 201
 202
 203
 204 \begin{eqnarray*}
 205 \widehat{M}\ll x,z\gg  & := & \widehat{M}[[x^{1/r}\cdot z,x^{1/r}\cdot z^{-1},x^{1/r}]][x^{-1/r}]\\
 206  & = & \left\{ \sum _{m,n}c_{m,n}x^{m/r}z^{n}:c_{m,n}\neq 0\Rightarrow |n|\leq m+O(1)\right\}
 207 \end{eqnarray*}
 208 is an  \( L \)-algebra which contains  \( \widehat{M}((x^{1/r})) \).
 209
 210 Since  \( N(x,z) \) splits into linear factors in  \( L((x^{1/r}))[z] \),  \( N(x,z)=l\prod ^{s}_{i=1}(z-\zeta _{i}(x))^{k_{i}} \), there exists a partial
 211 fraction decomposition of  \( h(x,z)=\frac{P(xz,\frac{x}{z})}{Q(xz,\frac{x}{z})}=\frac{z^{d}P(xz,\frac{x}{z})}{N(x,z)} \) in  \( \widehat{M}\ll x,z\gg  \):
 212
 213
 214 \[
 215 h(x,z)=\sum ^{l}_{j=0}P_{j}(x)z^{j}+\sum ^{s}_{i=1}\sum ^{k_{i}}_{k=1}\frac{P_{i,k}(x)}{(z-\zeta _{i}(x))^{k}}\]
 216 with  \( P_{j}(x),P_{i,k}(x)\in \widehat{M}((x^{1/r})) \).
 217
 218 Recall that we are looking for the coefficient of  \( z^{0} \) in  \( h(x,z) \). We compute
 219 it separately for each summand.
 220
 221 If  \( \zeta _{i}(x)=ax^{m/r}+... \) with  \( a\in L\setminus \{0\} \),  \( m>0 \), or  \( \zeta _{i}(x)=0 \), we have
 222
 223
 224 \begin{eqnarray*}
 225 \frac{1}{(z-\zeta _{i}(x))^{k}} & = & \frac{1}{z^{k}}\cdot \frac{1}{\left( 1-\frac{\zeta _{i}(x)}{z}\right) ^{k}}\\
 226  & = & \frac{1}{z^{k}}\cdot \sum ^{\infty }_{j=0}{k-1+j\choose k-1}\left( \frac{\zeta _{i}(x)}{z}\right) ^{j}\\
 227  & = & \sum ^{\infty }_{j=0}{k-1+j\choose k-1}\frac{\zeta _{i}(x)^{j}}{z^{k+j}}
 228 \end{eqnarray*}
 229 hence the coefficient of  \( z^{0} \) in  \( \frac{P_{i,k}(x)}{(z-\zeta _{i}(x))^{k}} \) is  \( 0 \).
 230
 231 If  \( \zeta _{i}(x)=ax^{m/r}+... \) with  \( a\in L\setminus \{0\} \),  \( m<0 \), we have
 232 \[
 233 \frac{1}{(z-\zeta _{i}(x))^{k}}=\frac{1}{(-\zeta _{i}(x))^{k}}\cdot \frac{1}{\left( 1-\frac{z}{\zeta _{i}(x)}\right) ^{k}}=\frac{1}{(-\zeta _{i}(x))^{k}}\cdot \sum _{j=0}^{\infty }{k-1+j\choose k-1}\left( \frac{z}{\zeta _{i}(x)}\right) ^{j}\]
 234 hence the coefficient of  \( z^{0} \) in  \( \frac{P_{i,k}(x)}{(z-\zeta _{i}(x))^{k}} \) is  \( \frac{P_{i,k}(x)}{(-\zeta _{i}(x))^{k}} \).
 235
 236 The case  \( \zeta _{i}(x)=ax^{m/r}+... \) with  \( a\in L\setminus \{0\} \),  \( m=0 \), cannot occur, because it would imply  \( 0=N(0,\zeta _{i}(0))=N(0,a)=a^{d}. \)
 237
 238 Altogether we have
 239 \[
 240 g(x^{2})=[z^{0}]h(x,z)=P_{0}(x)+\sum _{\frac{1}{\zeta _{i}(x)}=o(x)}\sum ^{k_{i}}_{k=1}\frac{P_{i,k}(x)}{(-\zeta _{i}(x))^{k}}\in \widehat{M}((x^{1/r}))\]
 241
 242
 243 Since all  \( \zeta _{i}(x) \)(in  \( L((x^{1/r})) \)) and all  \( P_{j}(x),P_{i,k}(x) \) (in  \( \widehat{M}((x^{1/r})) \)) are algebraic over  \( K(x) \), the same
 244 holds also for  \( g(x^{2}) \). Hence  \( g(x) \) is algebraic over  \( K(x^{1/2}) \), hence also over  \( K(x) \).
 245 After clearing denominators, we finally conclude that  \( g(x) \) is algebraic
 246 over  \( R[x] \).
 247
 248 \begin{lyxsectionbibliography}
 249
 250 \item [1] Bruno Haible: D-finite power series in several variables. \em Diploma
 251 thesis, University of Karlsruhe, June 1989. \em Sections 2.18 and
 252 2.20.
 253
 254 \item [2] M. L. J. Hautus, D. A. Klarner: The diagonal of a double power
 255 series. \em Duke Math. J. \em \bfseries 38 \mdseries (1971),
 256 229-235.
 257
 258 \item [3] C. Chevalley: Introduction to the theory of algebraic functions
 259 of one variable. \em Mathematical Surveys VI. American Mathematical
 260 Society.\em
 261
 262 \item [4] Jean-Pierre Serre: Corps locaux. \em Hermann. Paris \em 1968.
 263
 264 \item [5] Martin Eichler: Introduction to the theory of algebraic numbers
 265 and functions. \em Academic Press. New York, London \em 1966.
 266
 267 \end{lyxsectionbibliography}
 268
 269 \end{document}