Section 5

Puiseux Series and the Newton Polygon Algorithm

Part 2: Examples

$$ \newcommand{\bint}{\displaystyle{\int\hspace{-10.4pt}\Large\mathit{8}}} \newcommand{\res}{\displaystyle{\text{Res}}} \newcommand{\wvalx}{\underbrace{z^{\lambda_4}(c_4+w_5)}_{w_4}} \newcommand{wvalxx}{\underbrace{z^{\lambda_3}(c_3+\wvalx)}_{w_3}} \newcommand{wvalxxx}{\underbrace{z^{\lambda_2}\{c_2+\wvalxx\}}_{w_2}} \newcommand{wvalxxxx}{z^{\lambda_1}\big(c_1+\wvalxxx\big)} $$

The Newton Polygon Method (expansion about the origin):

The reader is advised to read part 1 of this section for background information pertaining to the method.

We begin by first normalizing, if necessary, the function (see Part 1). We then represent a branch as $$ w(z)=c_1z^{\lambda_1}+c_2 z^{\lambda_1+\lambda_2}+c_3 z^{\lambda_1+\lambda_2+\lambda_3}+\cdots $$ in which $\lambda_1\geq 0$ and $\lambda_i>0$ for $i>1$ and $c_i \in \mathbb{C}$. And we find the exponents $\lambda_i$ and coefficients $c_i$ by both constructing a convex hull of points for the (normalized) function as well as by regular substitution. The points for the hull construction are obtained as follows: We plot a set of points $\left(i,\textbf{ord}(a_i)\right)$ and then extract from this set of points, the lower Newton Leg described in the previous section with one additional requirement: The lower leg is the lower part of the convex hull with negative or zero slope for the first iteration and then only negative slopes for successive iterations.

  1. First Function:

    Consider again, the (normalized) function $$ F(z,w)= (z+z^2)+(1+z) w+w^2 $$ The lower Newton leg is then the two red segments spanning the points $(0,1),(1,0),(2,0)$ shown in Figure 1. And a critical component of the algorithm is the necessity of working with a normalized version of the function: A normalized function will always have the point $(n,0)$ on the convex hull and so guaranteeing that we can always find a lower Newton Leg for the first iteration, that is, the lower portion of the convex hull with negative or zero slope with all remaining points above and to the right of the lower leg. In order to gain experience in identifying the lower Newton Leg of the type of convex hulls encountered in this paper, the interested reader should study several examples and if possible, review and run either the following Mathematica code or other types of available code. The code below generates random convex hulls of the type we study.

    Mathematica code

    mypoints = Table[{n, RandomInteger[{0, 10}]}, {n, 0, 9}]
    mypoints = Append[mypoints, {10, 0}]
    thePoints = Graphics[{Red, PointSize[0.018], Point@ mypoints}];
    p1 = ConvexHullMesh[mypoints,
    MeshCellStyle -> {{1, All} -> Red, {0, All} -> Black}];
    Show[{p1, thePoints}, Axes -> True, PlotRange -> {{0, 11}, {0, 11}}]

    As we discussed in Part 1, we let $$ w_1(z)=z^{\lambda_1}(c_1+w_2) $$ where $w_2=c_2 z^{\lambda_2}+c_3 z^{\lambda_2+\lambda_3}+\cdots$. Our first step of course is to find $\lambda_1$,$\beta_1$ and $c_1$. See Walker1 for a derivation of the method. We obtain the possible values of $\lambda_1$ from the negative of the slopes for the lower Newton leg of the the convex hull. And $\beta_i$ is the $y$-intercept of the segment. In Figure 1, we have two legs. One has slope of -1 and the other has zero slope. For the segment $S_1$ spanning $(0,1)$ to $(1,0)$, we have $\beta_1=1$. And for $S_2$ we have $\beta_1=0$. For each segment, we derive a separate power series for $w(z)$. We therefore consider two cases:

    1. Power series for $S_1$

      We first recall the recursive formula: $$ F_{i+1}=z^{-\beta_i} F_{i}\left(z,z^{\lambda_i}(c_i+w_{i+1})\right) $$ where we let $F_1(z,w_1)=F(z,w)$, the original function.

      In Figure 1, we have $\beta_1=1$, $\lambda_1=1$. We then substitute $w\to w_1=z^{\lambda_1}(c_1+w_2)$ into the first recursive equation: $$ \begin{aligned} F_2(z,w_2)&=z^{-\beta_1} F_1\left(z,z^{\lambda_1}(c_1+w_2)\right)\\ &=z^{-1} F_1\left(z,z^{1}(c_1+w_2)\right)\\ &=1+c_1+w_2+(1+c_1+c_1^2) z+(1+2 c_1) w_2 z+w_2^2 z \end{aligned} $$ We now rely on one of the necessary conditions for the method: The lowest powers in $z$ alone must cancel so that we have $(1+c_1)z^0=0$ and note this is the same form for the characteristic equation for this segment, that is, $E_1(x)=1+x$ and this is precisely how the characteristic equation is derived. So we have $c_1=-1$ which gives us: $$ F_2(z,w_2)=z+(1-z)w_2+z w_2^2 $$ and the next Newton polygon shown in Figure 2.

      This gives us $\beta_2=1$,$\lambda_2=1$ with characteristic equation $1+x=0$ or $c_2=-1$. We have now reached a simple segment and can now begin regular substitution discussed in Part 1 by letting the exponents increase by one over the denominator of $\lambda_2$ for some finite number of terms say $w_3=a_3 z+a_4 z^2+\cdots+a_{11}z^{8}$. Plugging these into the next recursive formula $$ \begin{aligned} F_3(z,w_3)&=z+(-1+z)w_3+zw_3^2\\ &=z+(1-z)(a_3z+a_4z^2+\cdots+a_{11}z^8)+z(a_3 z+a_4 z^2+\cdots+a_{11}z^8)^2 \end{aligned} $$ and it is now a simple matter to equate powers of $z$ to zero and compute the remaining constants $a_i$. (Recall we are working with the expression $f(z,w)=0$ so coefficients on both sides of the equation must be equal.) When we do this, we obtain $$ \begin{aligned} -a_2+a_3&=0 \\ a_2^2-a_3+a_4&=0 \\ 2a_2 a_3-a_4+a_5&=0 \\ a_3^2+2 a_2 a_4-a_5+a_6&=0 \\ 2 a_3 a_4+2 a_2 a_5-a_6+a_7 &=0 \\ a_4^2+2 a_3 a_5+2 a_2 a_6-a_7+a_8 &=0 \\ 2a_4 a_5+2 a_3 a_6+2 a_2 a_7-a_8+a_{9} &=0 \\ a_5^2+2 a_4 a_6+2 a_3 a_7+2 a_2 a_8-a_9+a_{10}&=0 \\ 2 a_5 a_6+2 a_4 a_7+2 a_3 a_8+2 a_2 a_9-a_{10}+a_{11}&=0 \\ \end{aligned} $$ and sequentially solving for $a_3$ then $a_4$ and so on we obtain $$ w=-z-z^2-z^3-2 z^4-4 z^5-9 z^6-21 z^7-51 z^8-127 z^9-323 z^{10} $$ However remember from the previous section that this expansion was for the normalized version of our original function and the power series for $f(z,w)$ is the power series for $F(z,w)$ divided by $z^2$ so we obtain $$ w_1(z)=-1-1/z-z-2 z^2-4 z^3-9 z^4-21 z^5-51 z^6-127 z^7-323 z^8 $$
    2. Power series for $S_2$

      We now consider segment $S_2$ where we have $\lambda=0$ and $\beta=0$. It's now a simple matter to substitute these into the recursive formula to obtain: $$ \begin{aligned} F(z,w)&=z^{-\beta_1} F\left(z,z^{\lambda_1}(c_1+w_2)\right)\\ &=z^0 F(z,z^0(c_1+w_2) \\ &=(z+z^2)+(z-1)(c_1+w_2)+(c_1+w_2)^2 \\ &=(c_1+c_1^2+z+c_1 z+z^2)+(1+2c_1+z) w+ w^2\\ &=F_2(z,w_2). \end{aligned} $$ We now equate the lowest powers of $z$ to zero and obtain $c_1+c_1^2=0$ once again noting $E_2(x)=x+x^2$ and at this point we wish to focus exclusively on the characteristic equation without having to manually determine the lowest power of $z$. We then choose the non-zero roots to $E_1(x)$ as our values of $c_i$ so that we have $c_1=-1$ and obtain for the second recursion formula: $$ F_2(z,w_2)=z^2+(-1+z) w+w^2. $$ and the Newton polygon shown in Figure 2. This gives us $\beta_2=2$, $\lambda_2=2$ and a characteristic equation of $1-x=0$ or $c_2=1$. And since the segment is simple, we can use one over the denominator of $\lambda_2$ noting that $2=\frac{2}{1}$ (in lowest terms) for the remaining exponents $\lambda_i$. We can then substitute for the first ten terms, $w_3=c_3 z+c_4 z^2+\cdots+c_{10} z^{8}$ into $F_2(z,w_3)$ to obtain: $$ \begin{aligned} F_2(z,w_3)&=z^2+(-1+z)w+w^2 \\ &=z^2+(-1+z)(c_3 z+c_4z^2+\cdots+c_{10}z^{8})+(c_3 z+c_4 z_2+\cdots+c_{10}z^8)^2 \end{aligned} $$ and once again equating coefficients to zero obtain $$ w(z)=-1+z^2+z^3+2 z^4+4 z^5+9 z^6+21 z^7+51 z^8+127 z^9+323 z^{10} $$ likewise remembering that the power series for $f(z,w)$ is that of $w(z)$ divided by $z^2$, we obtain the second power series for the function as $$ w_2(z)=1-1/z^2+z+2 z^2+4 z^3+9 z^4+21 z^5+51 z^6+127 z^7+323 z^8 $$

  2. Second Function

    We now wish to work with a function in which the segments (and characteristic equations) do not become simple until several iterations of the recursive equation: $$ F(z,w)=(z^4)+(2 z^2+z^4)w+(1+z^2+z^3)w^2+(z)w^3+(1/4-z/2)w^4+(-(1/2))w^5 $$

    Figure 2 shows the Newton polygon for the initial function $F_1(z,w)$. The first thing to note about the lower Newton leg is that each of the segments have three points so has the potential for roots with multiplicities for their associated characteristic equations.

    And we will now dispense with the manual computation of the recursive equations. Readers may wish to review the earlier sections to review. Rather, we will now use getSegmentData described in the Mathematica code page. This routine will automatically compute for us the slope and intercepts for each segment of the lower Newton leg as well as the characteristic equations and their roots and multiplicities. theSegmentData returns a list of lists in the form $\{list1,list2,\cdots,listn\}$, one list for each segment on the lower Newton leg. And each segment list has the form {slopeIntercept,characteristicEquation,rootTally}. For example the following code

    theFunction=w^2+2z^2 w+z^4+z^2 w^2+z w^3+1/4 w^4+z^4 w+z^3 w^2-1/2 z w^4-1/2 w^5;
    {slopeInterceptList, charEquations, theRootTally} = 
      getSegmentData[minVals, myPoints, lcpsave, 1];

    returns in theSegmentData:
    1+2 x+x^2==0,
    {1/6 (1+(217-12 Sqrt[327])^(1/3)+(217+12 Sqrt[327])^(1/3)),1},
    {1/6-1/12 (1+I Sqrt[3]) (217-12 Sqrt[327])^(1/3)-1/12 (1-I Sqrt[3]) (217+12 Sqrt[327])^(1/3),1},
    {1/6-1/12 (1-I Sqrt[3]) (217-12 Sqrt[327])^(1/3)-1/12 (1+I Sqrt[3]) (217+12 Sqrt[327])^(1/3),1}}}}

    Where: $\{2,4\}$ represents $2$ as the (negative) slope and $4$ as the intercept of segment $S_1$. $1+2x+x^2=0$ is the associated characteristic equation for the segment, and $\{\{-1,2\}\}$ is the root tally, that is, $-1$ with multiplicity 2. For the horizontal segment, $S_2$, we next have $\{0,0\}$ as the slope and intercept, $x^2+x^4/4-x^5/2=0$ as its characteristic equation, and $\{0,2\}$ as a root of zero with multiplicity two and the three remaining roots with multiplicity one as the five roots to its associated characteristic equation.

    1. Power series for $S_1$

      And note for the first segment, we have non-zero root of multiplicity greater than one. This means that we will have to iterate the recursive equation for this segment. We therefore let $\beta_1=4$, $\lambda_1=2$ and $c_1=-1$ and substitute this into the recursive formula: $$ F_2=z^{-4}F_1(z,z^{2}(-1+w_2));\quad w_2=c_2 z^{\lambda_2}+c_3 z^{\lambda_2+\lambda_3}+\cdots $$ and omit the details of this substitution and rather show the next polygon for this iteration in Figure 3:

      We execute getSegmentData with kval=2 for this iteration since this is the second polygon and we are now interested only in segments on the lower Newton leg having negative slopes. theSegmentData returns:


      Recall again, this means the slope is (negative) 2, the intercept is 4. The characteristic equation is next and we see the root tally as $\{1/2,2\}$. So that again we have a multiple root. We let $\lambda_2=2$, $\beta_2=4$ and $c_2=1/2$ and iterate a second recursion: $$ F_3=z^{-4}F_2(z,z^{2}(1/2+w_3));\quad w_3=c_3 z^{\lambda_3}+c_4 z^{\lambda_3+\lambda_4}+\cdots $$ and obtain a third Newton polygon shown in Figure 4 with segment data

      Letting $\lambda_3=1$, $\beta_3=2$ and $c_3=-1/2$, we iterate the recursion equation a third time: $$ F_4=z^{-2}F_3(z,z^{1}(-1/2+w_4));\quad w_4=c_4 z^{\lambda_4}+c_5 z^{\lambda_4+\lambda_5}+\cdots $$ and obtain the fourth Newton polygon for the function shown in Figure 5 with segment data:


      and taking $\lambda_4=1/2$, $\beta_4=1$ and $c_4=\frac{i}{\sqrt{2}}$, we generate $$ F_5=z^{-1}F_4\left[z,z^{1/2}\left(\frac{i}{\sqrt{2}}+w_5\right)\right];\quad w_5=c_5 z^{\lambda_5}+c_6 z^{\lambda_5+\lambda_6}+\cdots $$

      We have after four recursions, reached a simple segment and can now use substitution to find the remaining terms using one over the denominator of $\lambda_4$ or $1/2$ as the exponent for the remaining exponents. Using the technique of equating powers to zero described above, we can compute for example, the first 13 terms for the power expansion of this $2$-cycle branch: $$ \begin{aligned} w_1(z)&=-1. z^2+0.5 z^4-0.5 z^5-(0. +0.707107 I) z^{11/2}+(0. +0.441942 I) z^{13/2}+0.5 z^7\\ &+(0. +0.933602 I) z^{15/2}-0.5 z^8-(0. +2.24493 I) z^{17/2}+1.375 z^9+(0. +1.0694 I) z^{19/2}\\ &-1.375 z^{10}+(0. +2.68726 I) z^{21/2} \end{aligned} $$ And using the second root, we would obtain the second conjugate series: $$ w_{2}(z)=-z^2+0.5 z^4-0.5 z^5+0.70711 I z^{11/2}-0.44194 I z^{13/2}+0.5 z^7-0.93360 I z^{15/2}+\cdots $$ And note the first three terms are the same for both conjugate series. And since each conjugate series is a single-valued branch, we could write: $$ w(z)=\begin{cases} w_1(z), & -\pi \leq \theta < \pi \\ w_2(z), & \pi \leq \theta <2\pi \end{cases} $$ so that both single-valued branches are identical up to order 5. We can visually see this similarity by viewing this function in AFRender and unselecting all rings except the first and then display only the $2$-cycle branch corresponding to these power series. Note how both branch surfaces are very close to one another appearing as a single sheet until the plot is magnified.

    2. Power series for $S_2$

      The characteristic equation for this leg is $x^2+1/4 x^4-1/2 x^5=0$ with the following non-zero root tally: $$ \text{rootTally: }\left\{\left( \begin{array}{cc} \frac{1}{6} \left(\sqrt[3]{217-12 \sqrt{327}}+\sqrt[3]{217+12 \sqrt{327}}+1\right) & ,1 \\ -\frac{1}{12} \sqrt[3]{217+12 \sqrt{327}} \left(1-i \sqrt{3}\right)-\frac{1}{12} \left(1+i \sqrt{3}\right) \sqrt[3]{217-12 \sqrt{327}}+\frac{1}{6} & ,1 \\ -\frac{1}{12} \sqrt[3]{217-12 \sqrt{327}} \left(1-i \sqrt{3}\right)-\frac{1}{12} \left(1+i \sqrt{3}\right) \sqrt[3]{217+12 \sqrt{327}}+\frac{1}{6} & ,1 \\ \end{array} \right)\right\} $$ Each of these roots generate after the first recursive equation, a simple segment having slope of one. After which, we can then use substitution to arrive at the first ten terms of the remaining branches for this function: $$ \begin{aligned} w_1(z)&=1.45054 +0.163939 z+0.926917 z^2-0.0717314 z^3-0.602722 z^4+0.148923 z^5+0.769661 z^6\\ &-0.328224 z^7-1.21161 z^8+0.748091 z^9+2.10653 z^{10}\\ w_2(z)&=(-0.47527+1.07374 I)-(0.581969 +0.330162 I) z+(0.536541 +0.268988 I) z^2+(0.0358657 -0.201663 I) z^3\\ &-(0.198639 -0.35995 I) z^4+(0.425538 +0.122047 I) z^5-(0.38483 +0.423919 I) z^6-(0.335888 -0.857064 I) z^7\\ &+(1.10581 -0.450021 I) z^8-(1.74905 +1.05306 I) z^9+(0.321735 +2.92673 I) z^{10}\\ w_3(z)&=(-0.47527-1.07374 I)-(0.581969 -0.330162 I) z+(0.536541 -0.268988 I) z^2+(0.0358657 +0.201663 I) z^3 \\ &-(0.198639 +0.35995 I) z^4+(0.425538 -0.122047 I) z^5-(0.38483 -0.423919 I) z^6-(0.335888 +0.857064 I) z^7\\ &+(1.10581 +0.450021 I) z^8-(1.74905 -1.05306 I) z^9+(0.321735 -2.92673 I) z^{10} \end{aligned} $$ We should also note that since the original function $f(z,w)$ was of degree five and the first leg generated a $2$-cycle branch, and since each of the roots above were simple, they must each lead to single-cycle branches, the total cycles summing up to five.

  3. Third Function: The degenerate case.

    Consider $$ f(z,w)=(1+z+z^2)+(2+z^2)w+(-1+2z^2)w^2+(5+z)w^3 $$ and note this function will lead to the degenerate polygon shown in Figure 6 since the lowest term in each $a_i$ is a constant.

    But a degenerate polygon with zero slope is an acceptable lower Newton leg for the first iteration. This give us a characteristic equation $1 +2 x-x^2+5 x^3$, the root tally being $$\left( \begin{array}{ccc} \{-0.341781,1.\} & \{0.27089\, -0.715394 i,1.\} & \{0.27089\, +0.715394 i,1.\} \\ \end{array} \right) $$ And substituting each of these roots into the recursive equation, we get for each of the roots, a simple segment shown in Figure 7. And we know from previous cases that we can now use regular substitution with $\lambda_i=1$ for each succeeding exponent and obtain three $1$-cycle branches for this function.

  4. Fourth Function: Polynomials in $w$

    Now consider a polynomial strictly in terms of $w$: $$ f(z,w)=(w-1)(w-2)(w-3)^3=w^5-12 w^4+56 w^3-126 w^2+135 w-54 $$ Again, this function will lead to a degenerate polygon like that shown in Figure 6 with the characteristic equation being identical to the polynomial, $-54.+135. x-126. x^2+56. x^3-12. x^4+x^5$ with the roots being $\{1,2,3\}$. Now, when we substitute these roots into the first recursive equation, we obtain a second degenerate polygon with zero slope. For example, when we use the first root, we obtain $f_2(z,w)=(8)w+(-20)w^2+(18)w^3+(-7)w^4+(1)w^5$. Recall from the discussion, that we choose lower Newton legs with negative or zero slope only for the first polygon and then those only with negative slopes for successive iterations. We therefore have reached a termination point and should stop the algorithm. In this case, we would like the algorithm to report:

    Mathematica code

    Series is terminating.
    Series 1 is 1.
    Series is terminating.
    Series 2 is 2.
    Series is terminating.
    Series 3 is 3.

  5. Fifth Function: Fractional Polynomials

    We now consider a function having a fractional polynomial solution: $$ (1 - 3 z + 3 z^2 - z^3) + (-4 + 8 z - 4 z^2) w + (6 - 6 z) w^2 + (-4) w^3 + (1) w^4 $$ Readers should refer to the section on finite series for a derivation of this function having as it's solution $w(z)=1+z^{1/4}+z^{1/2}+z^{3/4}$. We would like to process $f(z,w)$ through the Newton polygon algorithm and confirm after the fourth iteration, that is after we have computed the coefficient on the $z^{3/4}$ term, we would obtain a degenerate polygon indicating the series is finite. And for this test, we will not use regular substitution when we obtain a simple segment but rather continue the recursive process up to the fifth iteration.

    Computing the polygon for $f(z,w)$, we obtain the degenerate case shown in the top left plot of Figure 8 and a root tally of $\{1,4\}$ indicating multiple roots. We choose $c_1=1$ and then continue the recursive process through the second, third, and fourth iterations shown in Figure 8 to obtain the four coefficients of the first conjugate series for the solution. We are left with the function $$ \begin{aligned} f_4(z,w)&=(-4+8z^{1/4}-12 z^{1/2}+16 z^{3/4}-12 z+8 z^{5/4}-4 z^{3/2})w \\ &+(6 z^{1/2}-12 z^{3/4}+12 z-12 z^{5/4}+6 z^{3/2})w^2 \\ &+(-4z+4 z^{5/4}-4 z^{3/2})w^3 \\ &+ z^{3/2} w^4 \end{aligned} $$ The Newton polygon for $f_4(z,w)$ is shown in Figure 9 and this is another degenerate polygon indicating that the series has terminated. The reader is encouraged to work out these iterations.

  6. Sixth Function

    We would like now to used what we've learned to construct a particular type of function: We want to work on a second-degree function which completely ramifies around the origin. That is, one which consists of a single $2$-cycle branch. Using what we know about Newton polygons, it's not difficult to design such a function. For example, the following function would lead to such a geometry: $$ F(z,w)=\left(z+p(z)\right)+\left(z+q(z)\right)w+\left(k+r(z)\right)w^2 $$ where $\textbf{ord}(p(z))>1$, $\textbf{ord}(q(z))>1$ and $\textbf{ord}(r(z))>0$ are polynomials and $k$ is any non-zero constant. For example, even the unwieldy function $$ F(z,w)=(z+2z^2+100 z^{10}) +(z+z^6) z+ (1+z^3+z^5+2z^6)w^2 $$ would fit that criteria and indeed is fully-ramified about the origin. We will explain this with the simpler function $$ F(z,w)=z+z w+(1+z)w^2. $$

    and its convex hull shown in Figure 9. The characteristic equation is $E_1(x)=1+c_1^2$ with simple roots $(i,-i)$. Secondly, the slope of the segment is $1/2$. So we know immediately $\lambda_1=1/2$ and that all succeeding powers of $z$ will increase by one over the denominator of this slope or $\lambda_2=1/2$, $\lambda_3=1/2$, etc. That is, this branch is $2$-cycle. So letting $\lambda_1=1/2$, $\beta_1=1$, and taking $c_1=i$ we obtain $$ F(z,w_2)=w_2^2 z+w_2^2+2 i w_2 z+w_2 \sqrt{z}+2 i w_2-z+i \sqrt{z}. $$ And since the characteristic equation is simple for this example, we can next substitute $w_2=c_2 z^{1/2}+c_3 z+c_4 z^{3/2}+\cdots+c_n z^{(n-1)/2}$ for a desired number of terms and solve sequentially for $c_2, c_3,$ etc. The first five terms of one conjugate power expansion for this $2$-cycle branch is: $$ w(z)=i z^{1/2}-z/2-5/8 i z^{3/2}+1/2 z^2+71/128 i z^{5/2} $$ We can either substitute $c_1=-i$ and solve for the second conjugate series or derive it using the method in Section 2.

1 Algebraic Curves, Walker, R.J.

No comments:

Post a Comment

Blog Archive