TITLE: Formula for the center of gravity for overlapping cards and harmonic series
QUESTION [2 upvotes]: reading the book "prime obsession" written by Derbyshire (Rienmann), at the beginning of the book there is an introduction to the harmonic series done using a card game.
If you have a deck of cards, you can slide the top card of 1/2 of its lenght before it falls. After that you can do the same with the second card which can be moved of 1/4 of its lenght. You can do this considering the two top cards as one entity of lenght uqual to 1 + 1/2 and the center of gravity of these two cards is at 3/4.
          --------------
    --------------
--------------
--------------
--------------
--------------

Then the next slides (from the book) are: 1/6 of the lenght of a card, 1/8, 1/10 and so on.
But in general how can you find the center of gravity for overlappling cards? Is there a general formula to do that?
The book after the first two cards says, is is easy to do the computation. I tried, but at the beginning I was simply dividing by 2 the lenght of first the three cards (1 + 1/2 + 1/4). But of course I was wrong. So, how was so simple to say the the card had to be moved of 1/6 of its lenght? What am I missing?
I am approaching the general problem analysing the balance of levers considering the extremes of the cards as if the weight were all there, trying to make an equation out of it, since the left side has to balance the right side.
          --------------
    --------------
--------------
           ^
           x

REPLY [3 votes]: This problem is solved by considering that, for a given $n^{th}$ step, we have firstly to determine the position of the center of mass of a block of $n$ cards. This is done by calculating the weighted average between the position of the preceding block, formed by $n-1$ cards, and that of the new added card. Then, we have to move the whole block rigthward until the  vertical line passing through its center of mass coincides with the right edge of the deck.
For the sake of clarity it is convenient, at a given $n^{th}$ step and immediately before we move the $n^{th}$ card, to call $d(n)$ the horizontal distance of the center of mass of our block of $n$ cards from  the left edge of our deck.

Let  us start from the initial condition  where all cards are aligned. In the first step, we have to determine the maximal shifting of the first card to the right so that it does not fall. Our initial block is formed by $1$ card and its center of mass is in the middle of the deck, so that $d(1)=1/2$. The maximal rigthward shifting such that the  vertical line passing through the center of mass coincides with the right edge of the deck is then clearly $1-1/2=1/2$.

In the second step, we have to determine the maximal shifting of the second card to the right so that it does not fall. Our block is now formed by $2$ cards and its center of mass is the weighted average between that of the preceding block and that of the new card. The preceding block has $1$ card with center of mass at a distance $1$ (since it has been already moved to the right). Thus, $d(2)=(1\cdot 1 + 1\cdot 1/2)/2=3/4$. The maximal rigthward shifting of the second card is therefore $1-3/4=1/4$.

In the third step, we have to determine the maximal shifting of the third card to the right so that it does not fall. Our block is now formed by $3$ cards and again its center of mass is the weighted average between that of the preceding block and that of the new card. The moved preceding block has $2$ cards, with a center of mass at a distance $1$ from the left edge of the deck. Thus, $d(3)=(2\cdot 1 + 1\cdot 1/2)/3=5/6$. The maximal rigthward shifting of the second card is therefore $1-5/6=1/6$.

Generalizing, in the $n^{th}$ step, we have to determine the maximal shifting of the $n^{th}$ card to the right so that it does not fall. Our block is formed by $n$ cards and its center of mass is the weighted average between that of the moved preceding block and that of the new card. The preceding block has $n-1$ cards with center of mass at a distance $1$. Thus

$$d(n)=\frac{(n-1)\cdot 1 + 1\cdot 1/2}{n}=\frac{(n-1/2)}{n}=\frac{2n-1}{2n}$$
The maximal rigthward shifting of the $n^{th}$ card is therefore
$$1-\frac{2n-1}{2n}=  \frac{1}{2n}$$


TITLE: How do you solve a $n$-th order system of differential equations in the form of $\mathbf x^{(n)}=A\mathbf x$?
QUESTION [4 upvotes]: How do you solve a $n$-th order system of differential equations.

I know how to solve first order equations like $\mathbf{x}'=A\mathbf{x}$ but how would I solve $$\mathbf x^{(n)}=A\mathbf x$$ Could you maybe show me how it is done or link me some sources where I can look this up. I have looked at Paul's notes, Mathematical Methods for Physicsists and Engineers and Wikipedia but they seem to all focus on first order equations.
Edit: Winther demonstrated a standard procedure of reducing nth order systems to first order systems in the comments. I am looking for sources that explain this in detail.

REPLY [5 votes]: Given an $n$'th order ODE
$${\bf y}^{(n)} = A{\bf y}$$
where ${\bf y}$ is a vector in $\mathbb{R}^k$ then we can reduce the order of the equation by introducing auxiliary variables ${\bf y_i} = {\bf y}^{(i-1)}$ for $i=1,2,3,\ldots,n$. With these variables the ODE can be written
$$\matrix{{\bf y_n}' &=& A{\bf y_1}\\
{\bf y_{n-1}}' &=& {\bf y_n}\\
&\ldots&\\
{\bf y_{1}}' &=& {\bf y_2}}$$
which is a closed system of coupled first order equations. The price to pay for this reduction in order is that the $k$ equations we started with have turned into $nk$ equations.
This system can also be written on matrix form ${\bf Y'} = B{\bf Y}$ by working with the vector
$${\bf Y} = \pmatrix{({\bf y_1})^1\\\ldots\\({\bf y_i})^j\\\ldots\\({\bf y_n})^k}$$
The matrix $B$ will contain $A$ in the lower-left corner and the rest of the component are $0$ except for $B_{j,k+j} = 1$ for $j=1,2,\ldots,(n-1)k$.
The general formulation of the method is a bit messy with a lot of vectors and components, but it's not very complicated in practice. As long as you remember the main method here then you will be able to use it for any equation of interest (I would not bother remembering the general formula for $B$ just focus on remembering the steps needed to reduce it to that form).

To show an application we can try to apply this method to your system
$${\bf y''} = A{\bf y}$$
where ${\bf y} = \pmatrix{y^1\\y^2}$ and $A = \pmatrix{13/3 & 20i/3\\20i/3 & -37/3}$. We introduce ${\bf y}_1 = {\bf y}$ and ${\bf y}_2 = {\bf y'}$ so that
$$\pmatrix{{\bf y_1'}\\{\bf y_2'}} = \pmatrix{{\bf y_2}\\A{\bf y_1}}$$
which can be written
$${\bf Y'} = \pmatrix{0&0&1&0\\0&0&0&1\\13/3 & 20i/3&0&0\\20i/3 & -37/3&0&0}{\bf Y}$$
where $Y_1 = {\bf y^1_1} = {\bf y^1}$, $Y_2 = {\bf y^2_1} = {\bf y^2}$, $Y_3 = {\bf y^1_2}$, $Y_4 = {\bf y^2_2}$ (here a super-script denotes the component number).


TITLE: Which bonds are the cross-links and which are secondary bonds (in elastomers)?
QUESTION [0 upvotes]: Elastomeres are "defined" as:
"linear-chain polymers with widely spaced cross-links attaching each molecule to its neighbours"
Now I found sentences (talking about glass transition):
"This means that at room temperature the secondary bonds are melted and the molecules can slide relative to each other with ease. Were it not for the cross-links, the material would be a viscous liquid, but the cross-links give it a degree of mechanical stability."
So, what exactly are these bonds that melt? and which ones do not? An example would be nice. Chemistry is not my strongest field so be rigorous.
The quotations are from cellular solids by gibson and ashby.

REPLY [0 votes]: This is really a chemistry question, but I don't think there is a chemistry SE at the moment.
Anyhow, there may not be clearly defined secondary bonds. If you take silicone (dimethicone) it has a glass transition temperature about -125C. There aren't any specific bonds involved: it's just due to the Van der Waals forces that you get in any solid.
When you have polymers with polar groups, e.g. polymethylmethacrylate you can get hydrogen bonding between the polymer chains. These are more what you'd describe as a "secondary bond" and are indeed broken by rising temperature. You generally find hydrogen bonded polymers have much higher glass transition temperatures than polymers that cannot form hydrogen bonds.


text:
\begin{document}

\title[Cube Number Properties]{Cube number can detect chirality and Legendrian type of knots}

\author[B. McCarty]{Ben McCarty}

\address{Department of Mathematics, Louisiana State University \newline
\hspace*{.375in} Baton Rouge, LA 70817, USA} \email{\rm{benm@math.lsu.edu}}

\subjclass{}
\date{}

\begin{abstract}
For a knot $K$ the cube number is a knot invariant defined to be the smallest $n$ for which there is a cube diagram of size $n$ for $K$.  We will show that the cube number detects chirality in all cases computed thus far, and distinguishes certain legendrian knots.
\end{abstract}

\maketitle

\bigskip
\section{Introduction}
\bigskip

Cube diagrams are $3$-dimensional representations of knots or links (c.f. \cite{Adam}).  A cube diagram is a cubic lattice knot embedded in an $n \times n \times n$ cube in $\mathbb{R}^3$ where each projection to an axis plane ($x = 0$, $y = 0$, and $z = 0$) is a grid diagram.  The integer $n$ is the \emph{size} of the cube diagram and the \emph{cube number} of a knot, denoted $c(K)$, is the smallest $n$ for which there is a cube diagram for the knot of size $n$.

In \cite{BaldMcCar} small examples of cube diagrams of knots were given up to $7$ crossings.  In some cases it was observed that the examples given were minimal.  In each of these examples minimality was guaranteed since the arc index, $\alpha(K)$, is less than or equal to the cube number and cube diagrams for $K$ can be found with cube number equal to $\alpha(K)$.  Cube number is a far more powerful invariant than arc index.  For example, $\alpha(K) = \alpha(mK)$ where $mK$ is the mirror image of $K$ for all knots and links, but:

\bigskip
\noindent
{\bf Theorem 1} \emph{For eight of the first twelve chiral knots in Rolfsen's knot table (up to $7$-crossing knots), cube number detects chirality and no counter example is known to exist in the remaining four cases.  See Theorem \ref{thm:chirality} for the full list of knots where cube number is known to detect chirality.}
\bigskip

Let $K$ be a Legendrian knot.  Define the \emph{Legendrian cube number} (or cube number when the context is clear), $c_\ell(K)$, to be the minimum $n$ such that there is a cube diagram for $K$ of size $n$ that projects to a Legendrian front of $K$ (see details in Section \ref{section:legendrian}).  Perhaps surprisingly, the Legendrian cube number detects Legendrian knot type in some cases.  This fact is unexpected because there is no clear relationship as of yet between cube diagrams and Legendrian knots (cube diagrams do not naturally embed as Legendrian knots even when they have the same Legendrian knot projections).  In this paper we prove:

\bigskip
\noindent
{\bf Theorem 2} \emph{Let $K_{min}$ be the left hand $(5,2)$-torus knot with maximal Thurston-Bennequin number and $r = -3$ and $K_{max}$ the $(5,2)$-torus knot with maximal Thurston-Bennequin number and $r = 3$.  Then the Legendrian cube number distinguishes between $K_{min}$ and $K_{max}$.}
\bigskip

We conclude this paper with a conjecture that generalizes Theorem 2 to all $(p,2)$ torus knots and show that this conjecture is true if Conjecture \ref{gridMoves} is true.

\bigskip
\section{Definition of a cube diagram}

Let $n \in \mathbb{Z}^{+}$ and $\Gamma$ an $n \times n \times n$ cube, thought of as a $3$-dimensional Cartesian grid with integer-valued vertices.  A \textit{flat of $\Gamma$} is any cuboid (a right rectangular prism) with integer vertices in $\Gamma$ such that there are two orthogonal edges of length $n$ with the remaining orthogonal edge of length $1$.  A flat with an edge of length 1 that is parallel to the $x$-axis, $y$-axis, or $z$-axis is called an {\em $x$-flat}, {\em $y$-flat}, or {\em $z$-flat} respectively.  Note that the cube itself is canonically oriented by the standard orientation of $\BR^3$ (right hand orientation).

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=.3]{tiltedtrefoil.jpg}
\caption{Lefthand trefoil cube diagram.}
\label{fig:LHTrefoil}
\end{figure}
\end{center}

A \emph{marking} is a labeled half-integer point in $\Gamma$.  We mark unit cubes of $\Gamma$ with either an $X$, $Y$, or $Z$ such that the following {\em marking conditions} hold:
\begin{itemize}
    \item each flat has exactly one $X$, one $Y$, and one $Z$ marking;\\

    \item the markings in each flat form a right angle such that each segment is parallel to a coordinate axis;\\

    \item for each $x$-flat, $y$-flat, or $z$-flat, the marking that is the vertex of the right angle is an $X, Y,$ or $Z$ marking respectively.
\end{itemize}

We get an oriented link in $\Gamma$ by connecting pairs of markings with a line segment whenever two of their corresponding coordinates are the same.  Each line segment is oriented to go from an $X$ to a $Y$, from a $Y$ to a $Z$, or from a $Z$ to an $X$. The markings in each flat define two perpendicular segments of the link $L$ joined at a vertex, call the union of these segments a {\it cube bend}. If a cube bend is contained in an $x$-flat, we call it an {\it $x$-cube bend}. Similarly, define {\it $y$-cube bends} and {\it $z$-cube bends}.

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=.2]{crossingconditions.jpg}
\caption{Crossing conditions of the knot at every intersection in each projection.}
\label{fig:crossings}
\end{figure}
\end{center}

Arrange the markings in $\Gamma$ so that at every intersection point of the $(x,y)$-projection (i.e., $\pi_z : \mathbb{R}^3 \rightarrow \mathbb{R}^3$ given by $\pi_z(x,y,z)=(x,y)$), the segment parallel to the $x$-axis has smaller $z$-coordinate than the segment parallel to the $y$-axis.  Similarly, arrange so that in the $(y,z)$-projection, $z$-parallel segments cross over the $y$-parallel segments, and in the $(z,x)$-projection, the $x$-parallel segments cross over the $z$-parallel segments (see Figure \ref{fig:crossings}).

A set of markings in $\Gamma$ satisfying the marking conditions and crossing conditions is called a \emph{cube diagram} for the knot or link.

\bigskip
\section{Liftability of grid diagrams}

Because cube diagrams project to grid diagrams, it is natural to think of a cube diagram as a lift of a grid diagram corresponding to, say, the $(x,y)$-projection of the cube.  However, such lifts do not always exist (c.f. \cite{Adam} and \cite{BaldMcCar}).

Before proceeding, we need to establish some terminology and facts about grid diagrams (for more details see \cite{Adam}).  Grid diagrams will be oriented so that vertical edges are directed from $X$ to $O$.  A \emph{bend} in a grid diagram, $G$, is a pair of segments that meet at a common $X$ or $O$ marking.  We will refer to the former pair of segments as an $X$-bend and the latter as an $O$-bend.  There are two ways to decompose any link component in $G$ into a set of non-overlapping bends, corresponding to a choice of $X$-bends or $O$-bends.  In particular, for a knot there are only two ways to decompose $G$ into non-overlapping bends, and such a choice will be called a \emph{bend decomposition}.

Consider a grid diagram, $G$, together with a choice of a bend decomposition.  If possible we wish to lift $G$ to a cube diagram where $G$ is the $(x,y)$-projection of the cube diagram and the bend decomposition of $G$ determines the $z$-cube bends of the cube diagram.  While $G$ carries with it an orientation on the knot, so does the $(x,y)$-projection of the cube diagram.  In order that these orientations agree, the $X$-bend decompositon of $G$ has to be chosen--$O$-bends cannot be lifted to $z$-cube bends.  Furthermore, because of the symmetry between all three projections in a cube diagram, it is enough to work only with the $(x,y)$-projection and lift $X$-bends to $z$-cube bends.

The crossings in a grid diagram sometimes generate a \emph{partial order} on the $X$-bends.  Let $b_1$ and $b_2$ be two $X$-bends.  If $b_1$ crosses over $b_2$ in $G$ we say that $b_1 > b_2$.  Thus in any lift of $G$, the $z$-cube bend corresponding to $b_1$ must have $z$-coordinate greater than that of the $z$-cube bend corresponding to $b_2$.

Of course, not every grid diagram has a partial order on the $X$-bends.  A grid diagram for which there is no partial order on the $X$-bends may not even lift to a lattice knot that has well-defined knot projections in the other planes (Figure 5 of \cite{Adam}).  However, if there is a partial ordering on the $X$-bends of the grid diagram, it will lift to a lattice knot in which all projections are well-defined knot projections (c.f. \cite{Adam}).  Nevertheless, even a partial order doesn't guarantee liftability to a cube diagram as the $(y,z)$- and $(z,x)$-projections may not be grid diagrams in such a lift (c.f \cite{Adam} and \cite{BaldMcCar}).  Below, we will introduce some grid configurations that fail to lift, not because of a lack of partial ordering but due to crossings in the $(y,z)$- or $(z,x)$-projections that do not satisfy the crossing conditions for a cube diagram.  In Figures \ref{fig:type1} and \ref{fig:type2}, the shaded regions are determined by the corresponding $X$-bend and extend from the $X$-bend to the boundary of the grid diagram as indicated.  Furthermore, a dotted edge represents a sequence of edges in the grid that remains in the shaded region.  This condition is required in the proofs that follow to guarantee that the $(y,z)$- or $(z,x)$-projections contain crossings that do not satisfy the crossing conditions for a cube diagram.

\begin{theorem}
The Type 1 configurations shown in Figure \ref{fig:type1} do not appear in the projection of a cube diagram.
\end{theorem}

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=.35]{Type1.jpg}
\caption{Type 1 configurations.}
\label{fig:type1}
\end{figure}
\end{center}

\begin{proof}
We will prove the result for the center configuration.  The remaining cases are similar.  If we assume first that there is a partial order on the $X$-bends of the grid diagram, then the shaded region must contain an $O$ marking.  If there is no $O$ marking in the shaded region, then $a$ and $b$ must end at the same $X$ mark, and thus there is no partial order on the $X$-bends, and no lift.  In any lift of the grid to a lattice knot satisfying the marking conditions for a cube diagram at least one such $O$ marking must represent a vertical edge that passes through the flat containing the $X$-bend shown, since $a$ is below the bend and $b$ is above.  Since this $z$-parallel edge is located in the shaded region, it must either cross over the $x$-parallel edge shown in the $(z,x)$-projection or behind the $y$-parallel edge shown in the $(y,z)$-projection, which breaks the crossing condition shown in Figure \ref{fig:crossings}.
\end{proof}

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=.35]{Type2.jpg}
\caption{Type 2 configurations.}
\label{fig:type2}
\end{figure}
\end{center}

\begin{theorem}
The Type 2 configurations shown in Figure \ref{fig:type2} do not appear in the projection of a cube diagram.
\end{theorem}

\begin{proof}
For the first configuration shown in Figure \ref{fig:type2}, if the edge ending in $a$ has $z$-coordinate less than the lower $X$-bend then the sequence of edges connecting $a$ to $b$ must contain an $O$-marking.  That $O$-marking corresponds to a $z$-parallel edge that crosses behind that lower $X$-bend in the $(y,z)$-projection.  Otherwise, the edge ending in $a$ is above that lower $X$-bend.  In this case, the sequence of edges connecting $a'$ to $b'$ must contain an $O$-marking that corresponds to a $z$-parallel edge that crosses above the edge ending in $a$ in the $(z,x)$-projection.  A similar argument will show that the other configuration fails to lift as well.
\end{proof}

\section{Cube number and chirality}

\begin{theorem}
\label{thm:chirality}
The cube number detects the chirality of the trefoil.  That is, if $K_L$ is the left hand trefoil and $K_R$ is the right hand trefoil, then $c(K_L) < c(K_R)$.
\end{theorem}

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=1.8]{RHTrefoils.jpg}
\caption{Minimal right hand trefoil grid diagrams.}
\label{fig:RHTrefoils}
\end{figure}
\end{center}

\begin{remark}
The cube number of the left hand trefoil is 5 and the cube number of the right hand trefoil is 7.
\end{remark}

\begin{proof}
Note first that $c(K_L) = \alpha(K_L)$ (see Figure \ref{fig:LHTrefoil}).  For the right hand trefoil, Figure \ref{fig:RHTrefoils} shows all minimal grid diagrams.  For columns $1$, $4$, and $5$ there is a Type $1$ configuration present in the grid (shown in blue and marked by the $X$-bend).  For columns $2$ and $3$ there is either no partial order on the bends or there is a Type $2$ configuration (shown in blue and marked by the $X$-bend).
\end{proof}

For all examples that have been computed, the cube number detects the chirality of the knot as in Theorem \ref{thm:chirality}.  For knots with arc index greater than $5$ proofs of this nature become infeasible.  However, a computer can do the same basic checks for Type 1 and Type 2 configurations.  A program was written that generates all grid diagrams, sifts out those that contain Type 1 and 2 configurations, and then attempts to lift the remaining diagrams to cube diagrams.  Upon finding a valid cube diagram, the Jones polynomial is computed to identify the knot type.  This program has been successfully run up to size $9$ diagrams, generating the following result:

\begin{theorem}
\label{thm:mainchirality}
The cube number detects the chirality of the following knots: $5_2$, $7_2$, $7_3$, $7_4$, $7_5$, $8_{19}$, $9_{49}$, $10_{124}$, $10_{128}$, $10_{139}$, $10_{145}$, $10_{161}$, $12_{n591}$,  and the $(3,2)$, $(5,2)$, and $(7,2)$ torus knots.
\end{theorem}

For most knots mentioned in Theorem \ref{thm:mainchirality} one knot has cube number equal to arc index and all that is known is that the mirror image has cube number strictly greater than arc index.  However, the calculation has also yielded the result that the cube number for the right hand trefoil is equal to $7$ and the cube number for the right hand $(5,2)$ torus knot is $10$ (the program found no diagrams for the right hand $(5,2)$ torus knot of size $9$ or less and an example of size $10$ exists).

\section{Cube number and Legendrian type}
\label{section:legendrian}

Any grid diagram represents the front projection of a Legendrian knot by following this procedure.  First smooth the northeast and southwest corners.  Then convert northwest and southeast corners to cusps and rotate the grid diagram $45$ degrees counterclockwise.  Note that some authors (see \cite{legend}) describe a similar procedure to obtain a Legendrian projection for the mirror image of the knot represented by $G$, while the one described here is for the original knot type represented by $G$.  While there is no similar construction to convert a cube diagram into a Legendrian knot, each of the projections of a cube diagram is a grid diagram, and hence, represents the Legendrian front projection of some knot.  Therefore one can define the Legendrian cube number, $c_\ell(K)$, to be the smallest $n$ such that there is a cube diagram for the knot $K$ of size $n$ where the $(x,y)$-projection of the cube diagram is a grid diagram representing the Legendrian knot $K$.

According to \cite{etnyrehonda} the \emph{rotation number} may be computed from the Legendrian front projection as follows:
$$r(K) = \frac{1}{2}(D_c - U_c)$$
where $D_c$ is the number of downward oriented cusps and $U_c$ is the number of upward oriented cusps in the Legendrian front projection.  Furthermore, according to \cite{etnyrehonda} and \cite{Ng}, any minimal grid diagram for a left hand Legendrian torus knot, $T_{p,2}$, must realize the maximal Thurston Bennequin number and hence have rotation number satisfying:
$$r(K) \in \left\{ \pm (|p| - 2 - 4t): t \in \mathbb{Z}, 0 \leq t < \frac{|p| - 2}{2} \right\}.$$
For the following results we will need to refer to a \emph{standard diagram}, $G_{j,k}$, for a $(p,2)$-torus knot.  A standard diagram for $T_{p,2}$ is one that contains all crossings along two diagonals as shown in Figure \ref{fig:standardp2} (note that there is a similar notion of standard diagram for right hand $(p,2)$-torus knots).  For the standard diagram shown in Figure \ref{fig:standardp2} the rotation number may be computed as follows:
$$r(G_{j,k}) = \frac{1}{2} ( 2k - 2j ) = k - j.$$
Note that each Legendrian left hand $(p,2)$-torus knot realizable in a minimal grid diagram is represented by a standard grid diagram.  Also the standard diagram with maximum rotation number is one in which $k = p - 1$ (recall that $p = k + j$).  Similarly the standard diagram with minimum rotation number has $j = p - 1$.

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=.5]{standardp2.jpg}
\caption{Standard diagram $G_{j,k}$ where $j+k = p$ and $j,k \geq 1$.}
\label{fig:standardp2}
\end{figure}
\end{center}

\begin{theorem}
\label{thm:legendrian}
Let $K_{min}$ be the left hand $(5,2)$-torus knot with maximal Thurston-Bennequin number and $r = -3$ and $K_{max}$ the $(5,2)$-torus knot with maximal Thurston-Bennequin number and $r = 3$.  Then the Legendrian cube number distinguishes between $K_{min}$ and $K_{max}$.
\end{theorem}

\begin{proof}
Note first that $c_\ell(K_{max}) = \alpha(T_{5,2})$ (the construction shown in Figure \ref{fig:LHTrefoil} extends to $T_{5,2}$).  Now, for $K_{min}$ all minimal grid diagrams can be reached from the standard one (see Figure \ref{fig:lhp2}) by cyclic permutation.  This fact has been verified by a computer program that determines the total number of grid diagrams of a given Legendrian knot.  In this case the program confirmed that there are only $49$ distinct minimal diagrams for $K_{min}$, precisely those that may be reached from the standard diagram by cyclic permutation.  Finally, cyclic permutations do not eliminate all of the Type 1 configurations present in each of the $49$ diagrams.  Therefore $c_\ell(K_{min}) > \alpha(T_{5,2})$.
\end{proof}

There are also further results regarding cube number and Legendrian knot type.  A computer program has been used to show that cube number distinguishes between the Legendrian $(7,2)$ torus knots with $tb = 0$ and $r = \pm 5$.  The following conjecture has been verified up to $p = 7$ by a computer program.

\begin{conjecture}
\label{gridMoves}
Given a torus knot $T_{p,2}$ and a legendrian knot $K_L$ of topological type $T_{p,2}$ and a grid diagram for $K_L$ of size $\alpha(T_{p,2})$.  Then there is a sequence of commutation and cyclic permutation moves taking $K_L$ to the standard grid diagram representing it.
\end{conjecture}

To understand the conjecture, we must first define what is meant by commutation and cyclic permutation.  A cyclic permutation of a grid diagram takes a column (resp. row) adjacent to the boundary of the grid, and moves it to the opposite end of the grid (c.f. \cite{Cromwell}).  Two adjacent columns (resp. rows) are said to be \emph{interleaved} if the $y$-coordinates (resp. $x$-coordinates) of the markings are distinct and alternate between the columns (resp. rows).  A commutation switches the position of any two adjacent rows (resp. columns) that are not interleaved, including pairs that are adjacent with respect to the boundary (c.f. \cite{Adam}).  Note that the grid may be thought of as existing on a torus, so opposite edges may be identified (hence the commutation move includes rows and columns adjacent to the boundaries).  Furthermore, using this definition of commutation, commutation and cyclic permutation commute.

\begin{conjecture}
Let $K_{max}$ and $K_{min}$ be left hand Legendrian torus knots with $p \geq 5$ and maximal Thurston-Bennequin number such that the rotation number of $K_{max}$ is maximal and the rotation number of $K_{min}$ is minimal.  Then $c_\ell(K_{max}) < c_\ell(K_{min})$.
\end{conjecture}

\begin{proof}[Proof (Assuming conjecture \ref{gridMoves}).]
As in the proof of Theorem \ref{thm:legendrian} the cube diagram shown in Figure \ref{fig:LHTrefoil} extends to give a cube diagram for $K_{max}$ of size equal to the arc index.  Also for $p = 5$ this result is precisely Theorem \ref{thm:legendrian}.  A similar argument shows that the result holds for $p = 7$ as well.  Assume now that $p \geq 9$.  Since cyclic permutation commutes with commutation, all commutation moves may be moved to the beginning of the sequence. Since the standard grid diagram for $K_{min}$ has no possible commutation moves, it suffices to consider only cyclic permutations.  Consider a sequence of cyclic permutation moves.  Such a sequence is equivalent one in which the first $a$ moves are cyclic permutations down (i.e. moving the bottom row to the top of the grid) and the remaining moves, denote the number of moves by $b$, are cyclic permutations to the left (i.e. moving the left column to the right side of the grid).  Also, note that doing $a$ cyclic permutations down is equivalent to doing $n - a$ cyclic permutations up.  Similarly, doing $b$ cyclic permutations left is equivalent to doing $n - b$ cyclic permutations right.

\begin{center}
\begin{figure}[h]
\centering
\includegraphics[scale=.5]{p2.jpg}
\caption{Standard diagrams for the $(p,2)$ torus knot with $r = -(p - 2)$ and $r = p - 2$ respectively.}
\label{fig:lhp2}
\end{figure}
\end{center}

Now, if $a \leq n - 4$ and $b \leq n - 5$ the upper right most Type 1 configuration (labeled $X_1$ in Figure \ref{fig:lhp2}) will remain fixed.  If $a \geq 5$ and $b \geq 4$ then the lower left most Type 1 configuration (labeled $X_2$ in Figure \ref{fig:lhp2}) remains.  If $a > n - 4$ and $b < 4$, or if $a < 5$ and $b > n - 5$ then the Type 1 configuration labeled $X_3$ remains.

\end{proof}

Note that while chirality is detected in all examples computed so far, it is not true that cube number always detects legendrian knot type.  There are multiple examples of left hand $(p,2)$ torus knots that are of different Legendrian types yet still have cube number equal to arc index.  For example, when $p = 7$ all left hand Legendrian $(p,2)$ torus knots realizable in a minimal grid diagram have cube number equal to arc index except for those with rotation number equal to $-3$ and $-5$.

config: arxiv


text:
\section{The height pairing and intersection number of sections}
\subsection{Connected numbers of three bitangents}\label{cnof3b}

Let $\mcQ$ be a smooth plane quartic. We choose homogeneous coordinates $[T, X, Z]$ of $\PP^2$ such that $z_{o}=[0, 1, 0]$ and $Z=0$ is the tangent line of $\mcQ$ at $z_{o}$. Then we may assume that $\mcQ$ is given by a homogeneous polynomial $F_{\mcQ}(T, X, Z)$ of the form
\begin{align*}
F_{\mcQ}(T, X, Z) =ZX^3 + p(T, Z)X^2 + q(T, Z)X+r(T, Z).
\end{align*}
Then the affine part of $\mcQ$, i.e., the part with $Z \neq 0$ is given by
\begin{align*}
F_{\mcQ}(t, x, 1) =x^3 + p(t, 1) x^2 + q(t, 1)x+r(t, 1).
\end{align*}
Then let $\varphi_{\mcQ , z_{o}} : S_{\mcQ, z_{o}} \rightarrow \PP^1$ be the rational elliptic surface as in the Introduction and let $E_{\mcQ , z_{o}}$ be the generic fiber of $\varphi_{\mcQ , z_{o}}$. Then, by \cite[Theorem~10.4]{shioda90}, we have
\begin{align*}
E_{\mcQ , z_{o}}(\CC (t)) \cong E_{7}^{*},
\end{align*}
where $E_{7}^{*}$ is the dual lattice of the root lattice $E_{7}$. By \cite{shioda93}, $E_{\mcQ , z_{o}}(\CC (t))$ contains $56$ $\CC(t)$-rational points $P=(x, y)$ of the form:
\begin{align*}
x=at+b, \ y=c t^2 + dt +e.
\end{align*}
Since $-P=(x, -y)$, we denote them by
\begin{align*}
\pm P_{n} = (x_{n}, \pm y_{n}) = \left( a_{n}t+b_{n}, \pm (c_{n}t^2 +d_{n}t +e_{n}) \right) \quad ( n=1, \ldots , 28 ).
\end{align*}
Note that, by \cite[Proposition~4]{shioda93}, $28$ lines $L_n: x_{n}=a_{n}t+b_{n}$ are the $28$ bitangents to $\mcQ$.

As in \S 1, we denote the sections corresponding to $P$ by $s_{P}$. Let $q_{z_o}\circ f_{\mcQ , z_{o}} : S_{\mcQ , z_{o}} \rightarrow \PP^2$ be the map introduced in the Introduction and let $(q_{z_o}\circ f_{\mcQ , z_{o}})^{*}(L_{i})=s_{{i}}^{+}+s_{{i}}^{-}$ $(i = 1,\cdots,28$). Here,  $s_{{i}}^{+}=s_{P_i}$ and $s_{{i}}^{-}=s_{-P_{i}}$. Since $\Theta_{\infty, 1}\cdot s_{\pm P_n} = 1$ and $O\cdot s_{\pm P_n}=0 \ (n= 1, \ldots , 28)$, by the explicit formula for the height pairing, we have the following lemma:

\begin{lem}\label{lem: value of height} For $P_{i}$, $P_{j} \in \{  \pm P_{n} \}$,
\begin{enumerate}
\item[(i)] If $i = j$, then $\langle P_{i} , P_{j} \rangle = \frac{3}{2}$, $s_{P_{i}} \cdot s_{P_{j}}=-1$, and $s_{P_{i}} \cdot s_{-P_{j}}=2$,
\item[(ii)] If $i \neq j$, then
\begin{enumerate}
\item $\langle P_{i} , P_{j} \rangle =- \frac{1}{2}$ if and only if $s_{P_{i}} \cdot s_{P_{j}}=1$ and $s_{P_{i}} \cdot s_{-P_{j}}=0$,
\item $\langle P_{i} , P_{j} \rangle = \frac{1}{2}$ if and only if $s_{P_{i}} \cdot s_{P_{j}}=0$ and $s_{P_{i}} \cdot s_{-P_{j}}=1$.
\end{enumerate}
\end{enumerate}
\end{lem}

Choose three distinct bitangents $L_{i}$, $L_{j}$, and $L_{k}$ to $\mcQ$. Put $\triangle_{ijk} := L_{i}+L_{j}+L_{k}$. Then, by \S 1, we have connected numbers $c_{f_{\mcQ}}(\triangle_{ijk})=1$ or $2$.
 From Lemma \ref{lem: value of height}, we classify splitting types of three bitangents via the intersection number of $s_{\pm P_i}$'s. Let the matrix $G(i, j, k)$ be the matrix defined to be two times the Gramm matrix defined by the height pairing of $P_{i}, P_{j}$, and $P_{k}$. The diagonal entries of $G(i,j,k)$ are equal to $3$, and the off-diagonal entries take values $\pm1$. Since $G(i, j, k)$ is a symmetric matrix, then there are $8$ possible choices of $G(i, j, k)$. By the following lemma, the $8$ matrices are classified into two classes depending on $c_{f_{\mcQ}}(\triangle_{ijk})$.
\begin{lem}\label{lem:connected}
\begin{enumerate}
\item[(i)] $c_{f_{\mcQ}}(\triangle_{ijk})=1$ if and only if
\begin{align*}
G(i, j, k) \in
\left\{
\left[
\begin{array}{ccc}
3 & 1 & 1 \\
1 & 3 & 1 \\
1 & 1 & 3
\end{array}
\right]_{,}
\left[
\begin{array}{ccc}
3 & 1 & -1 \\
1 & 3 & -1 \\
-1 & -1 & 3
\end{array}
\right]_{,}
\left[
\begin{array}{ccc}
3 & -1 & 1 \\
-1 & 3 & -1 \\
1 & -1 & 3
\end{array}
\right]_{,}
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & 1 \\
-1 & 1 & 3
\end{array}
\right]
 \right\}_{.}
 \end{align*}
\item[(ii)] $c_{f_{\mcQ}}(\triangle_{ijk})=2$ if and only if
\begin{align*}
G(i, j, k) \in
\left\{
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 3
\end{array}
\right]_{,}
\left[
\begin{array}{ccc}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 3
\end{array}
\right]_{,}
\left[
\begin{array}{ccc}
3 & 1 & -1 \\
1 & 3 & 1 \\
-1 & 1 & 3
\end{array}
\right]_{,}
\left[
\begin{array}{ccc}
3 & 1 & 1 \\
1 & 3 & -1 \\
1 & -1 & 3
\end{array}
\right]
\right\}_{.}
\end{align*}
\end{enumerate}
\end{lem}

\proof
We give a proof when
\begin{align*}
G(i, j, k)=
\left[
\begin{array}{ccc}
3 & 1 & 1 \\
1 & 3 & 1 \\
1 & 1 & 3
\end{array}
\right]
\text{or}
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 3
\end{array}
\right]_{,}
\end{align*}
since the proof for the other 6 matrices can be done in the same manner.
\begin{enumerate}
\item[(i)] If
\begin{align*}
G(i, j, k)=
\left[
\begin{array}{ccc}
3 & 1 & 1 \\
1 & 3 & 1 \\
1 & 1 & 3
\end{array}
\right]_{,}
\end{align*}
i.e., $2\langle P_{i}, P_{j} \rangle = 2\langle P_{j}, P_{k} \rangle = 2\langle P_{k}, P_{i} \rangle =1$, we have $s_{P_{i}} \cdot s_{P_{j}}=s_{P_{j}} \cdot s_{P_{k}}=s_{P_{k}} \cdot s_{P_{i}}=0$ and $s_{P_{i}} \cdot s_{-P_{j}}=s_{P_{j}} \cdot s_{-P_{k}}=s_{P_{k}} \cdot s_{-P_{i}}=1$ from Lemma \ref{lem: value of height}. Since $\langle \ , \ \rangle$ is symmetric, we obtain $s_{P_{i}} \cdot s_{-P_{j}}=s_{-P_{j}} \cdot s_{P_{k}}=s_{P_{k}} \cdot s_{-P_{i}}=s_{-P_{i}} \cdot s_{P_{j}}=s_{P_{j}} \cdot s_{-P_{k}}=s_{-P_{k}} \cdot s_{P_{i}}=1$. This means that $c_{f_{\mcQ}}(\triangle_{ijk})=1$.

\item[(ii)]
If
\begin{align*}
G(i, j, k)=
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 3
\end{array}
\right]_{,}
\end{align*}
i.e., $2\langle P_{i}, P_{j} \rangle = 2\langle P_{j}, P_{k} \rangle = 2\langle P_{k}, P_{i} \rangle =-1$, we have $s_{P_{i}} \cdot s_{P_{j}}=s_{P_{j}} \cdot s_{P_{k}}=s_{P_{k}} \cdot s_{P_{i}}=1$ and $s_{P_{i}} \cdot s_{-P_{j}}=s_{P_{j}} \cdot s_{-P_{k}}=s_{P_{k}} \cdot s_{-P_{i}}=0$ from Lemma \ref{lem: value of height}. Hence we obtain $s_{P_{i}} \cdot s_{P_{j}}=s_{P_{j}} \cdot s_{P_{k}}=s_{P_{k}} \cdot s_{P_{i}}=1$ and $s_{-P_{i}} \cdot s_{-P_{j}}=s_{-P_{j}} \cdot s_{-P_{k}}=s_{-P_{k}} \cdot s_{-P_{i}}=1$, i.e., $c_{f_{\mcQ}}(\triangle_{ijk})=2$.
\end{enumerate}
\proofend

The figures below explain configurations of $(q_{z_o}\circ f_{\mcQ, z_o})^{-1}(\Delta_{ijk}\setminus \mcQ)$ in case (i), (ii) from the proof of Lemma \ref{lem:connected}. Note that the preimages of points on $\mcQ$ are
ignored.
\begin{figure}[h]
\begin{minipage}{0.5\linewidth}
\centering
\scalebox{0.8}{\input{hexagon.tex}}
\label{fig:connum1}
\subcaption{Case (i), where $c_{f_{\mcQ}}(\triangle_{ijk})=1$.}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\centering
\scalebox{0.8}{\input{triangles.tex}}
\label{fig:connum2}
\subcaption{Case (ii),  where $c_{f_{\mcQ}}(\triangle_{ijk})=2$.}
\end{minipage}
\end{figure}

By observing the matrices in the two classes above, we have the following Lemmas:
\begin{lem}\label{lem:cnof3b}
Let $m_{ijk}$ be the number of upper-half entries of $G(i,j,k)$ taking values equal to $-1$. Under the above setting,
\begin{enumerate}
\item[(i)] $c_{f_{\mcQ}}(\triangle_{ijk}) = 1$ if and only if $m_{ijk}$  is even,
\item[(ii)] $c_{f_{\mcQ}}(\triangle_{ijk}) = 2$ if and only if  $m_{ijk}$ is odd.\end{enumerate}
\end{lem}

We can restate the above Lemma in terms of determinants. Let $I_3$ be the identity matrix of size $3\times 3$.

\begin{lem}\label{lem:cnof3c}
\begin{enumerate}
\item[(i)]  $c_{f_{\mcQ}}(\triangle_{ijk}) = 1$ if and only if $\det(G(i,j,k)-3I_3)=2$,
\item[(ii)] $c_{f_{\mcQ}}(\triangle_{ijk}) = 2$ if and only if $\det(G(i,j,k)-3I_3)=-2$.
\end{enumerate}
\end{lem}

\subsection{The topology of plane quartic and its $n$ bitangents via sub-arrangement}

Let $\mcQ$ be a smooth plane quartic as in \S \ref{cnof3b} and $L_{1}, \ldots , L_{28}$ be $28$ bitangents to $\mcQ$. Choose a subset $I \subset \{ 1, \ldots , 28 \}$ such that $\sharp I = n \ (4 \leq n \leq 28)$ and put $\mcL_{I}:=\sum_{i \in I}L_{i}$. As in \S \ref{cnof3b}, we obtain the $n \times n$ matrix $G_I$ which is defined as twice of the Gramm matrix defined by the height pairing of $P_{i}$'s $(i \in I)$.

In order to consider the embedded topology of $\mcQ +\mcL_{I}$, we use the connected numbers of sub-arrangements $\underline{\mathrm{Sub}}_{\triangle}(\mcQ, \mcL_I)$. Let $c_{I}$ be the map defined in \S \ref{subsec:subarr} and put
\begin{align*}
m_I:=\sharp\left\{\text{ upper-half entries of $G_I$ equal to $-1$ }\right\}
\end{align*}
Since $\sharp \underline{\mathrm{Sub}}_{\triangle}(\mcQ, \mcL_I) = \binom{n}{3}$, we have
\begin{align*}
\sharp c_{I}^{-1}(2) = \binom{n}{3} - \sharp c_{I}^{-1}(1).
\end{align*}
Hence, there are $\binom{n}{3}+1$ possible pairs
\begin{align*}
\left( \ \sharp c_{I}^{-1}(1), \ \sharp c_{I}^{-1}(2) \ \right) = \left( 0, \binom{n}{3} \right) , \ \left( 1, \binom{n}{3} - 1 \right), \ldots , \  \left( \binom{n}{3}, 0 \right).
\end{align*}

By Proposition \ref{prop:key}, it seems that a Zariski $\left(\binom{n}{3}+1\right)$-ple may exist. However, the following proposition shows that this is not true when $n$ is even.
\begin{prop}\label{prp:m(n-2)}
Under the above setting, there exists a non-negative integer $M$ such that
\begin{align*}
m_I \, (n-2) = 2 \, M + \sharp c_{I}^{-1}(2).
\end{align*}
\end{prop}
\proof

We consider the sum
\[
\sum_{ \{ i_{1}, i_{2}, i_{3} \} \subset I} m_{i_{1}i_{2}i_{3}}
\]
where $m_{i_1i_2i_3}$ is defined as in Lemma \ref{lem:cnof3b}. Let us discribe this sum in two ways.
\begin{itemize}
\item[(I)]
Put $\triangle_{i_{1}i_{2}i_{3}}:=L_{i_{1}}+ L_{i_{2}} + L_{i_{3}}$. By Lemma \ref{lem:cnof3b}, we have
\begin{align*}
c_{f_{\mcQ}}(\triangle_{i_{1}i_{2}i_{3}})=1 & \text{ if and only if } m_{i_{1}i_{2}i_{3}}=0, 2, \\
c_{f_{\mcQ}}(\triangle_{i_{1}i_{2}i_{3}})=2 & \text{ if and only if } m_{i_{1}i_{2}i_{3}}=1, 3.
\end{align*}
Put
\begin{align*}
M_{N}:= \sharp \{ \triangle_{i_{1}i_{2}i_{3}} \ | \ m_{i_{1}i_{2}i_{3}}=N \} \ (N=0, 1, 2, 3).
\end{align*}
Then, we have
\begin{align*}
\sum_{ \{ i_{1}, i_{2}, i_{3} \} \subset I} m_{i_{1}i_{2}i_{3}} &= \sum_{c_{f_{\mcQ}}(\triangle_{i_{1}i_{2}i_{3}})=1} m_{i_{1}i_{2}i_{3}} + \sum_{c_{f_{\mcQ}}(\triangle_{i_{1}i_{2}i_{3}})=2} m_{i_{1}i_{2}i_{3}} \\
&= 0 \cdot M_{0} + 2 \cdot M_{2} + 1 \cdot M_{1} + 3 \cdot M_{3} \\
&= 2 (M_{2} + M_{3}) + M_{1} + M_{3} \\
&= 2 (M_{2} + M_{3}) + \sharp c_{I}^{-1}(2).
\end{align*}
Define $M$ to be $M_{2}+M_{3}$.

\item[(II)]
Fix an upper-half entry $g_{kl} (\{k,l\}\subset I)$ with value $-1$. Then, by the definitions of the matrices $G_{I}$ and $G({i_{1}, i_{2}, i_{3}})$, we have
\begin{center}
$G(i_{1}, i_{2}, i_{3})$ contains $g_{kl}$ as  its entry if and only if $k, l \in \{ i_{1}, i_{2}, i_{3} \}$.
\end{center}
Put $k=i_{1}, l=i_{2}$ without loss of generality. Then we have
\begin{align*}
& \, \sharp \{ G(i_{1}, i_{2}, i_{3}) \ | \ G(i_{1}, i_{2}, i_{3}) \text{ contains } g_{kl} \text{ as its entry } \} \\
= & \, \sharp \{ \{ i_{1}, i_{2}, i_{3} \} \subset I \ | \ k=i_{1}, l=i_{2} \} \\
= & \, n-2.
\end{align*}
Hence, by the definitions of $m_I$ and $m_{i_{1}i_{2}i_{3}}$, we obtain
\begin{align*}
\sum_{\{ i_{1}, i_{2}, i_{3} \} \subset I}m_{i_{1}i_{2}i_{3}}=m_I(n-2).
\end{align*}
\end{itemize}
\proofend

\begin{cor}\label{cor:even}
If $n$ is an even number, then the number of possible pairs of $\left( \, \sharp c_{I}^{-1}(1), \sharp c_{I}^{-1}(2) \, \right)$ is less than or equal to $\frac{1}{2}\binom{n}{3}+1$.
\end{cor}
\proof
If $n$ is an even number, $\sharp c_{I}^{-1}(2)$ is also even by Proposition \ref{prp:m(n-2)}. Hence, we have
\begin{align*}
( \, \sharp c_{I}^{-1}(1), \sharp c_{I}^{-1}(2) \, ) = \left( 0, \binom{n}{3} \right), \left( 2, \binom{n}{3}-2 \right), \ldots , \left( \binom{n}{3}-2, \, 2 \right), \left( \binom{n}{3}, \, 0 \right).
\end{align*}
\proofend

\begin{rem}{\rm
We do not know if $\frac{1}{2}\binom{n}{3}+1$ is a strict upper bound for general even $n$. In Section \ref{sec:example}, however,  we give an example attaining $\frac{1}{2}\binom{n}{3}+1$ when $n=4$.}
\end{rem}

\section{Examples}\label{sec:example}

Let $\mcQ$ be the Klein quartic given by the affine equation:
\begin{align*}
F(t, x):=x^3+t^{3}x+t.
\end{align*}
Then the generic fiber $E_{\mcQ, z_{o}}$ of $\varphi_{\mcQ , z_{o}}$ is $y^2 = F(t, x)$.
From \cite[Section 4]{shioda93}, the $28$ bitangents of $\mcQ$ are given by the following equations:
\begin{align*}
& L_{0, j} :x_{0, j}(t)=-\zeta^{j}t-\zeta^{3j},
& L_{1, j}:x_{1, j}(t)=-\zeta^{j}\varepsilon_{1}^2 t-\zeta^{3j}\varepsilon_{3}^{-2}, \\
& L_{2,j}:x_{2, j}(t)=-\zeta^{j}\varepsilon_{2}^2 t-\zeta^{3j}\varepsilon_{1}^{-2},
& L_{3,j}:x_{3, j}(t)=-\zeta^{j}\varepsilon_{3}^2 t-\zeta^{3j}\varepsilon_{2}^{-2},
\end{align*}
where $j=0, \ldots , 6, \ \zeta = e^{\frac{2 \pi i}{7}}, \ \varepsilon_{1}=\zeta + \zeta^{-1}, \ \varepsilon_{2}=\zeta^2 + \zeta^{-2}, \ \varepsilon_{3}=\zeta^{4}+\zeta^{-4}$. Put
\begin{align*}
& L_{1}:= L_{0, 0}, \ L_{2}:=L_{1, 0}, \ L_{3}:= L_{1, 1}, \ L_{4}:=L_{3, 3}, \\
& L_{5}:=L_{1, 6}, \ L_{6}:=L_{3, 4}, \ L_{7}:=L_{2, 5}.
\end{align*}
and rational points of $E_{\mcQ, z_{o}}$ defined by $L_{1}, \ldots , L_{7}$;
\begin{align*}
& P_{1}:=\left( \,  x_{0, 0}(t), \ y_{1}(t) \, \right),
P_{2}:=\left( \, x_{1, 0}(t) , \ y_{2}(t) \, \right),
P_{3}:=\left( \, x_{1, 1}(t), \ y_{3}(t) \, \right),
P_{4}:=\left( \, x_{3, 3}(t), \ y_{4}(t) \, \right), \\
& P_{5}:=\left( \, x_{1, 6}(t), \ y_{5}(t) \, \right),
P_{6}:=\left( \, x_{3, 4}(t), \ y_{6}(t) \, \right),
P_{7}:=\left( \, x_{2, 5}(t), \ y_{7}(t) \, \right).

\end{align*}
Here,
\begin{align*}
& y_{1}(t)= \sqrt{-1}(t^2 +t+1), \ y_{2}(t)=\sqrt{-1} \, \varepsilon_{1}(t^2 + a_{1}(\zeta) t + b_{1}(\zeta)), \\
& y_{3}(t)= \sqrt{-1}\zeta^{4}\varepsilon_{1}(t^2+\zeta^{2}a_{1}(\zeta) t + \zeta^{4}b_{1}(\zeta)), \ y_{4}(t)= \sqrt{-1}\zeta^{5}\varepsilon_{3}({t}^{2}+ a_{3}(\zeta)t + b_{3}(\zeta) ), \\
& y_{5}(t)=\sqrt{-1}\zeta^{3}\varepsilon_{1}(t^2+ \zeta^{5} a_{1}(\zeta) t+ \zeta^{3}b_{1}(\zeta) ), \ y_{6}(t)=\sqrt{-1}\zeta^{2}\varepsilon_{3}({t}^{2}+\zeta^{2}a_{3}(\zeta)t + \zeta^{4}b_{3}(\zeta)), \\
& y_{7}(t) = \sqrt{-1}\zeta^{6}\varepsilon_{2}({t}^{2}+( \zeta^2 +2 +2 \zeta^6 + \zeta^4 +4 \zeta^3 )t + \zeta^5 + 3 \zeta^3 +3 \zeta^2 + 1 +3 \zeta^6), \\
\intertext{where}
& a_{1}(\zeta) = 2 \zeta^5+\zeta^4+\zeta^3+2 \zeta^2+4, \ b_{1}(\zeta) = 3 \zeta^5+\zeta^4+\zeta^3+3 \zeta^2+3, \\
& a_{3}(\zeta) = 2 \zeta^5 + \zeta^4 + \zeta + 2 + 4 \zeta^6, \ b_{3}(\zeta) = 3 \zeta^4 + \zeta^3 + 1 + 3 \zeta^6 + 3 \zeta^5.
\end{align*}
Note that for $L_1,\ldots, L_7$, no three lines are concurrent and $\mcQ+\mcL_I$ ($I\subset\{1,\ldots,7\}$) all have the same combinatorics for fixed $\sharp I$.
\begin{itemize}
\item \underline{A Zariski pair for $\mcQ$ and its three bitangents} \\

We put
\[
\mcB^{1}:= \mcQ + L_{1} + L_{2} + L_{3},\quad
\mcB^{2}:= \mcQ + L_{1} + L_{2} + L_{4}.
\]
For $P_{1}$ and $P_{2}$, consider sections $s_{P_1}$ and $s_{P_2}$ as curves in the affine part of $S_{\mcQ, z_o}$ given by $s_{P_{1}}:=(x_{0, 0}(t), y_{1}(t))$ and $s_{P_{2}}:=(x_{1, 0}(t), y_{2}(t))$ with parameter $t$. Then $x_{0, 0}(t)=x_{1, 0}(t)$ and $y_{1}(t)=y_{2}(t)$ has a unique solution $t=\zeta + \zeta^{-1}$, which implies $s_{P_{1}} \cdot s_{P_{2}}=1$. In the same way, we obtain $s_{P_{2}} \cdot s_{P_{3}}=s_{P_{3}} \cdot s_{P_{1}}=s_{P_{1}} \cdot s_{P_{4}}=1$ and $s_{P_{2}} \cdot s_{P_{4}}=0$. Hence, we have
\[
G(1, 2, 3)=
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 3
\end{array}
\right]_{,} \quad
G(1, 2, 4)=
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & 1 \\
-1 & 1 & 3
\end{array}
\right]_{.}
\]
By Lemma \ref{lem:cnof3b}, we have $c_{f_{\mcQ}}(\triangle_{123})=2$ and $c_{f_{\mcQ}}(\triangle_{124}) = 1$, then $(\mcB^{1}, \mcB^{2})$ is a Zariski pair.

\item \underline{A Zariski triple for $\mcQ$ and its four bitangents} \\

We set $I_{1}:= \{ 1, 2, 3, 5 \}$, $I_{2}:= \{ 1, 2, 3, 6 \}$, $I_{3}:= \{ 1, 2, 4, 7 \}$ and put
\begin{align*}
\mcB^{k}:= \mcQ + \mcL_{I_{k}} \ (k = 1, 2, 3).
\end{align*}
As above, we have $G(1, 2, 3) = G(1, 2, 5) = G(1, 3, 5)$, $G(1, 2, 4)=G(1, 2, 7)=G(1, 4, 7)$ and
\begin{align*}

& G(1, 2, 6) = G(1, 3, 6) =
\left[
\begin{array}{ccc}
3 & -1 & -1 \\
-1 & 3 & 1 \\
-1 & 1 & 3
\end{array}
\right]_{,} \\
& G(2, 3, 6)=
\left[
\begin{array}{ccc}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 3
\end{array}
\right]_{,} \quad

G(2, 4, 7)=
\left[
\begin{array}{ccc}
3 & 1 & 1 \\
1 & 3 & 1 \\
1 & 1 & 3
\end{array}
\right]_{.}
\end{align*}
Hence, we obtain
\[
\left( \, \sharp c_{I_{1}}^{-1}(1), \sharp c_{I_{1}}^{-1}(2) \, \right) = ( 4, 0 ),\,
\left( \, \sharp c_{I_{2}}^{-1}(1), \sharp c_{I_{2}}^{-1}(2) \, \right) = ( 2, 2 ), \,
\left( \, \sharp c_{I_{3}}^{-1}(1), \sharp c_{I_{3}}^{-1}(2) \, \right) = ( 0, 4 ).
\]
By Proposition \ref{prop:key}, $(\mcB^{1}, \mcB^{2}, \mcB^{3})$ is a Zariski triple.
\end{itemize}

The existence of the above examples gives a proof to Theorem \ref{thm:main}.


text:
\begin{document}

\title{The Newton-Shamanskii method for solving a quadratic matrix equation arising in quasi-birth-death problems}

\author{Pei-Chang Guo \thanks{ e-mail: guopeichang@pku.edu.cn}\\
School of Mathematical Sciences, Peking University, Beijing 100871, Beijing, China}

\date{}

\maketitle
\begin{abstract}
In order to determine the stationary distribution for discrete time
quasi-birth-death Markov chains, it is necessary to find the minimal nonnegative solution of a quadratic matrix equation. We apply the Newton-Shamanskii method for solving the equation. We show that the sequence of matrices generated by the Newton-Shamanskii method is monotonically increasing and converges to the minimal nonnegative solution of the equation. Numerical experiments show the effectiveness of our method.

\vspace{2mm} \noindent \textbf{Keywords}: quadratic matrix equation, quasi-birth-death problems, Newton-Shamanskii method, minimal nonnegative solution.
\end{abstract}

\section{Introduction}

We first introduce some necessary notation for the paper. For any matrices $B=[b_{ij}]\in \mathbb{R}^{m\times n}$, we write $B\geq 0 (B>0)$ if $b_{ij} \geq 0 (b_{ij}> 0)$ holds for all $i,j$. For any matrices $A,B \in \mathbb{R}^{n\times n}$, we write $A\geq B (A > B)$ if $a_{ij}\geq b_{ij}(a_{ij} > b_{ij})$ for all $i, j$. For any vectors $x,y \in \mathbb{R}^n$ ,we write $x\geq y (x>y)$ if $x_i\geq y_i (x_i>y_i)$ holds for all $i=1, \cdots,n$. The vector of all ones is denoted by e, i.e., $e=(1, 1, \cdots, 1)^T$. The identity matrix is denoted by $I$.

In this paper, we consider the quadratic matrix equation (QME)
\begin{equation}\label{qme}
    \mathcal{Q}(X)=AX^2+BX+C=0,
\end{equation}
where $A, B, C, X \in \mathbb{R}^{n\times n}$, $A, B+I, C \geq 0$, $A+B+I+C$ is irreducible and $(A+B+C)e=e$.

The quadratic matrix equation (\ref{qme}) has applications in quasi-birth-death processes (QBD)\cite{qbini}. The elementwise minimal nonnegative solution $S$ of the equation (\ref{qme}) is of interest in the applications. The rate $\rho$ of a QBD Markov chain is defined by
\begin{equation}\label{qrho}
    \rho= p^T(B+I+2A)e
\end{equation}
where $p$ is the stationary probability
vector of stochastic matrix $A+B+I+C$, i.e., $p^T(A+B+I+C)=p^T$ and $p^Te=1$. We refer the readers to the monograph \cite{qbini} for the details. We recall that a QBD is positive recurrent if $\rho <1$, null recurrent if $\rho =1$ and transient if $\rho > 1$. Throughout this paper, we always assume that the QBD is positive recurrent.

 There have been several numerical methods for solving the equation.
 Some linearly convergent fixed point iterations are analyzed in \cite{qlinear}
and the references therein. In \cite{qnewton} Latouche showed that Newton's algorithm for this equation is well defined and the matrix sequences is  monotonically increasing and quadratically convergent. The invariant subspaces method approximates the minimal nonnegative solution $S$ quadratically by approximating the left invariant subspace of a suitable block companion matrix \cite{qbini,crqbd1}. Latouche and Ramaswami propose a logarithmic reduction algorithm based on a divide-and conquer strategy in \cite{qlrqbd}, producing sequences of approximations which converge quadratically to $S$.
Bini and Meini et al. devise a quadratically convergent and
numerically stable algorithm \cite{crqbd1,crqbd2,crqbd3,crqbd4,qbd} for the computation of $S$ based on a functional representation
of cyclic reduction, which applies to general M/G/1 type Markov chains \cite{stoch}
and which extends the method of Latouche and Ramaswami \cite{qlrqbd}.

In this paper, we apply the Newton-Shamanskii method to equation \eqref{qme}. We show that, starting with a suitable initial guess, the sequence of the iterative matrices generated by the Newton-Shamanskii method is monotonically increasing and converges to the minimal nonnegative solution of QME \eqref{qme}. Numerical experiments show that the Newton-Shamanskii method is effective and outperforms the Newton method.

The rest of the paper is organized as follows. In section 2 we recall Newton's method and present the Newton-Shamanskii iterative procedure. Insection3 we prove the monotone convergence result for the Newton-Shamanskii method. In section 4 we present some
numerical examples, which show that our new algorithm is faster
than Newton method. In section 5, we give our conclusions.

\section{Newton-Shamanskii Method}

The function $\mathcal{Q}$ in \eqref{qme} is a mapping from $\mathbb{R}^{n\times n}$ into
itself and the Fr\'{e}chet derivative of $\mathcal{Q}$ at $x$ is a linear map $\mathcal{Q}^{'}_X:  \mathbb{R}^{n\times n}\rightarrow \mathbb{R}^{n\times n}$ given by
\begin{equation}\label{qfdao}
   \mathcal{Q}^{'}_X(Z)= AZX+AXZ+BZ.
\end{equation}
The second derivative at $X$, $\mathcal{Q}^{''}_X : \mathbb{R}^{n\times n}\rightarrow \mathbb{R}^{n\times n}$, is given by
\begin{equation}\label{q2fdao}
    \mathcal{Q}^{''}_X(Z_1,Z_2)=AZ_1Z_2+AZ_2Z_1.
\end{equation}

For a given $X_0$, the Newton sequence for the solution of $\mathcal{Q}(X) = 0$ is
\begin{equation}\label{qnewit}
 X_{k+1}=X_k-(\mathcal{Q}^{'}_{X_k})^{-1}\mathcal{Q}({X_k}) ,\quad k=0,1 ,2, \cdots,
\end{equation}
 provided that $\mathcal{Q}^{'}_{X_k}$ is invertible for all $k$. By equation (\ref{qfdao}), the Newton iteration (\ref{qnewit}) is equivalent to
\begin{eqnarray}\label{qnewz}
                  \left\{  \begin{array}{c}
                 AZX _k+(AX_k+B)Z=-Q(X_k),\\
                  X_{k+1}=X_k+Z , \quad k=0,1 ,2, \cdots
                  \end{array}\right.
  \end{eqnarray}
    or
    \begin{equation}\label{qnewx}
        AX_{k+1}X_k+(AX_k+B)X_{k+1}=AX_k^2-C, \quad k=0,1 ,2, \cdots.
    \end{equation}

As we see in \cite{qnewton}, for the nonlinear equation $\mathcal{Q}(X)=0$ with the minimal nonnegative solution $S$, the sequence generated by Newton method will converge quadratically and globally to the the solution $S$. However, there is a disadvantage with Newton method. At every iteration step, a Sylvester-type equation
\begin{equation*}
     A_1XB_1^T+A_2XB_2^T=E.
\end{equation*}
is needed to solve. The Bartels-Stewart method and the Hessenberg-Schur method can be employed to solve the Sylvester-type equation \cite{laub}, where the QZ algorithm is involved. When solving the Sylvester-type equation, a transformation method is used which employs the QZ algorithm to structure the equation in such a way that it can be solved columnwise by a back substitution technique. The work count of the floating point operations involved in QZ algorithm is large compared with the back substitution \cite{laub}. In order to save the overall cost, we would like to reuse the special coefficient matrix structure form produced by QZ algorithm. We present the Newton-Shamanskii algorithm for QME(\ref{qme}) as follows.

\vspace{3mm}

\textbf{Newton-Shamanskii algorithm for QME(\ref{qme})}\\

Given initial value $X_{0}$, for $k=0,1,\cdots$
\begin{eqnarray}

\label{qlikea}   X_{k,0}&=&X_k-(\mathcal{Q}^{'}_{X_k})^{-1}\mathcal{Q}({X_k}) ,\\
\label{qlikeb}  X_{k,s} &=& X_{k,s-1}-(\mathcal{Q}^{'}_{X_k})^{-1}\mathcal{Q}({X_{k,s-1}}) , \quad s=1,2,\cdots , n_k, \\
 \label{qlikec} X_{k+1} &=& X_{k,n_k}
\end{eqnarray}

\section{Convergence Analysis}
In this section, we prove a monotone convergence result for Newton-Shamanskii method for QME \eqref{qme}.
\subsection{preliminary}
We first recall that a real square matrix $A$ is called a Z-matrix if
all its off-diagonal elements are nonpositive. Note that any Z-matrix A can be
written as $sI-B$ with $B \geq 0$. A Z-matrix $A$ is called an M-matrix if $s\geq \rho(B)$,
where $\rho(\cdot)$ is the spectral radius; it is a singular M-matrix if $s=\rho(B)$ and a
nonsingular M-matrix if $s>\rho(B)$.
We will make use of the following result (see \cite{varga}).
\begin{lemma}\label{qyubei1}
For a Z-matrix $A$, the following are equivalent:
\begin{itemize}
  \item [$(a)$] $A$ is a nonsingular M-matrix.
  \item [$(b)$] $A^{-1}\geq 0$ .
  \item [$(c)$] $Av>0$ for some vector $v>0$.
  \item [$(d)$] All eigenvalues of $A$ have positive real parts.
\end{itemize}
\end{lemma}
The next result is also well known and also can be found in \cite{varga}.
\begin{lemma}\label{qyubei2}
Let $A$ be a nonsingular M-matrix. If $B \geq A$ is a Z-matrix, then $B$ is also  nonsingular M-matrix . Moreover, $B^{-1}\leq A^{-1}$.
\end{lemma}
We recall the property of the minimal nonnegative solution $S$ for QME \eqref{qme}, see \cite{qnewton,qbini} for more details.
\begin{theorem}\label{qthm0}
If the quasi-birth-death process is positive recurrent, i.e., rate $\rho$ defined by \eqref{qrho} satisfies that $\rho <1$, then the matrix
\begin{equation*}
    -[(S^T\otimes A+I\otimes AS)+I\otimes B]
\end{equation*}
is a nonsingular M-matrix.
\end{theorem}
\subsection{Monotone convergence}
The next lemma displays the monotone convergence properties of Newton iteration for QME \eqref{qme}.  \begin{lemma}\label{qlemm1}
Suppose that a matrix $X$ is such that
\begin{itemize}
  \item [(i)] $\mathcal{Q}(X)\geq 0$,
  \item [(ii)] $0\leq X\leq S$,
  \item [(iii)]$-[(X^T\otimes A+I\otimes AX)+I\otimes B]$ is a nonsingular M-matrix.
\end{itemize}
Then there exists the matrix
\begin{equation}\label{qzheng1}
    Y=X-(\mathcal{Q}^{'}_{X})^{-1}\mathcal{Q}(X)
\end{equation}
such that
\begin{itemize}
  \item [(a)] $\mathcal{Q}(Y)\geq 0$,
  \item [(b)] $0\leq X \leq Y\leq S$,
  \item [(c)]$-[(Y^T\otimes A+I\otimes AY)+I\otimes B]$ is a nonsingular M-matrix.
\end{itemize}
\end{lemma}
\begin{proof}
$\mathcal{Q}^{'}_{X}$ is invertible and the matrix $Y$ is well defined by (iii) and Lemma \ref{qyubei1}.
Because $\mathcal{Q}(X)\geq 0$ and $-[(X^T\otimes A+I\otimes AX)+I\otimes B]^{-1}\geq0$ by (iii) and Lemma \ref{qyubei1}, we have $vec(Y)\geq vec(X)$ and thus $Y\geq X$.
From equation (\ref{qzheng1}) and Taylor formula,
we have
   \begin{eqnarray*} \mathcal{Q}(Y)&=&\mathcal{Q}(X)+\mathcal{Q}^{'}_{X}(Y-X)+\frac{1}{2}\mathcal{Q}^{''}_X(Y-X,Y-X)\\
       \nonumber &=&\frac{1}{2}\mathcal{Q}^{''}_X(Y-X,Y-X)  \\
      \nonumber &=& A(Y-X)^2 \geq 0
     \end{eqnarray*}
We now prove (b). From the equivalent form of \eqref{qzheng1}
\begin{equation*}
   \nonumber  A Y X+(AX+B)Y = AX^2-C
   \end{equation*}
   and the equation
   \begin{equation*}
    AS^2+BS+C = 0,
   \end{equation*}
 we get
 \begin{eqnarray*}
   \nonumber   A(Y-S)X+(AX+B)(Y-S)&=& AX^2-C-ASX-AXS-BS \\
      \nonumber &=& A(X-S)(X-S)\\
      \nonumber &\geq & 0.
     \end{eqnarray*}

Note that $-[(X^T\otimes A+I\otimes AX)+I\otimes B]$ is a nonsingular M-matrix, therefore by Lemma \ref{qyubei1} we get $vec(S-Y)\geq 0$, which is $S-Y\geq 0$. Note that $Y\geq X$, we have proved (b).

From $0\leq Y \leq S$, we know $$-[(Y^T\otimes A+I\otimes AY)+I\otimes B] \geq -[(S^T\otimes A+I\otimes AS)+I\otimes B],$$ and we know $-[(S^T\otimes A+I\otimes AS)+I\otimes B]$ is a nonsingular M-matrix, so
 $-[(Y^T\otimes A+I\otimes AY)+I\otimes B]$ is a nonsingular M-matrix by Lemma \ref{qyubei2}.
\end{proof}
The next lemma is an extension of Lemma \ref{qlemm1}, which will be the theoretical basis of monotone convergence result of Newton-Shamanskii method for QME \eqref{qme}.

\begin{lemma}\label{qlemm2}
Suppose that a matrix $X$ is such that
\begin{itemize}
  \item [(i)] $\mathcal{Q}(X)\geq 0$,
  \item [(ii)] $0\leq X\leq S$,
  \item [(iii)]$-[(X^T\otimes A+I\otimes AX)+I\otimes B]$ is a nonsingular M-matrix.
\end{itemize}
Then for any matrix $N$ with $0\leq N\leq X$, there exists the matrix
\begin{equation}\label{qzheng2}
    Y=X-(\mathcal{Q}^{'}_{N})^{-1}\mathcal{Q}(X)
\end{equation}
such that
\begin{itemize}
  \item [(a)] $\mathcal{Q}(Y)\geq 0$,
  \item [(b)] $0\leq X\leq Y\leq S$,
  \item [(c)]$-[(Y^T\otimes A+I\otimes AY)+I\otimes B]$ is a nonsingular M-matrix.
\end{itemize}
\end{lemma}
\begin{proof}
First, because $0\leq N\leq X$, we get $$-[(N^T\otimes A+I\otimes AN)+I\otimes B]\geq -[(X^T\otimes A+I\otimes AX)+I\otimes B]$$. From (iii) and Lemma \ref{qyubei2} we know $\mathcal{Q}^{'}_{N}$ is invertible and the matrix $Y$ is well defined such that $0\leq X \leq Y$. Let
\begin{equation*}
    \hat{Y}=X-(\mathcal{Q}^{'}_{X})^{-1}\mathcal{Q}(X),
\end{equation*}
we have $\hat{Y} \geq Y$ from Lemma \ref{qyubei2}. Note that $\hat{Y}\leq S$ by Lemma \ref{qlemm1}, so we have proved (b) $0\leq Y\leq S$. Note that $$-[(\hat{Y}^T\otimes A+I\otimes A\hat{Y})+I\otimes B]$$is a nonsingular M-matrix by Lemma \ref{qlemm1} and $\hat{Y} \geq Y$, we have $-[(Y^T\otimes A+I\otimes AY)+I\otimes B]$ is a nonsingular M-matrix by Lemma \ref{qyubei2}. Last, from Taylor formula and $\mathcal{Q}^{'}_{N}(Y-X)+\mathcal{Q}(X)=0$, we have
   \begin{eqnarray*}
   \nonumber \mathcal{Q}(Y)&=&\mathcal{Q}(X)+\mathcal{Q}^{'}_{X}(Y-X)+\frac{1}{2}\mathcal{Q}^{''}_X(Y-X,Y-X)\\
 \nonumber &=&\mathcal{Q}(X)+\mathcal{Q}^{'}_{N}(Y-X)+(\mathcal{Q}^{'}_{X}-\mathcal{Q}^{'}_{N})(Y-X)+\frac{1}{2}\mathcal{Q}^{''}_X(Y-X,Y-X)\\
\nonumber &=&(\mathcal{Q}^{'}_{X}-\mathcal{Q}^{'}_{N})(Y-X)+\frac{1}{2}\mathcal{Q}^{''}_X(Y-X,Y-X)\\
\nonumber &=&\mathcal{Q}^{''}_{X}(X-N,Y-X)+\frac{1}{2}\mathcal{Q}^{''}_X(Y-X,Y-X)\\
      \nonumber &=& A(X-N)(Y-X)+A(Y-X)(X-N)+A(Y-X)^2 \\
      \nonumber &\geq &0.
     \end{eqnarray*}
\end{proof}
Using Lemma \ref{qlemm2}, we can arrive at the following monotone convergence result of Newton-Shamanskii method for QME \eqref{qme}.
\begin{theorem}\label{qthm1}
Suppose that a matrix $X_0$ is such that
\begin{itemize}
  \item [(i)] $\mathcal{Q}(X_0)\geq 0$,
  \item [(ii)] $0\leq X_0\leq S$,
  \item [(iii)]$-[(X_0^T\otimes A+I\otimes AX_0)+I\otimes B]$ is a nonsingular M-matrix.
\end{itemize}
Then the Newton-Shamanskii algorithm (\ref{qlikea}) (\ref{qlikeb}) (\ref{qlikec}) generates a sequence $\{X_k\}$
such that $X_k \leq X_{k+1}\leq S$ for all $k \geq 0$, and $ \lim_{k \to \infty} X_k=S$.
\end{theorem}
\begin{proof}
We prove the theorem by mathematical induction. From Lemma \ref{qlemm2}, we have
\begin{equation*}
    X_0\leq X_{0,0}\leq \cdots \leq X_{0,n_0}=X_1 \leq S,
\end{equation*}
\begin{equation*}
    \mathcal{Q}(X_1)\geq 0,
\end{equation*}
and know that
\begin{equation*}
    -[(X_1^T\otimes A+I\otimes AX_1)+I\otimes B]
\end{equation*}
 is a nonsingular M-matrix.
Assume
\begin{equation*}
    \mathcal{Q}(X_i)\geq 0,
\end{equation*}
\begin{equation*}
    X_0\leq X_{0,0}\leq \cdots \leq X_{0,n_0}=X_1 \leq \cdots \leq X_{i-1,n_{i-1}}=X_{i} \leq S,
\end{equation*}
and
$-[(X_i^T\otimes A+I\otimes AX_i)+I\otimes B]$ is a nonsingular M-matrix.
Again by Lemma \ref{qlemm2} we have
\begin{equation*}
    \mathcal{Q}(X_{i+1})\geq 0,
\end{equation*}
\begin{equation*}
    X_i \leq X_{i,0}\leq \cdots \leq X_{i,n_i}=X_{i+1}\leq S,
\end{equation*}
and $-[(X_{+1}i^T\otimes A+I\otimes AX_{i+1})+I\otimes B]$ is a nonsingular M-matrix.
Therefore we have proved inductively the sequence $\{X_k\}$ is monotonically increasing and bounded above by $S$. So it has a limit $X_*$ such that $X_* \leq S$.
Let $i\rightarrow \infty$ in $X_{i+1}\geq X_{i,0}=X_i-(\mathcal{Q}^{'}_{X_i})^{-1}\mathcal{Q}({X_i})\geq 0$, we see that $\mathcal{Q}({X_*})=0$. Since $X_*\leq S$, and $S$ is the minimal nonnegative solution of QME (\ref{qme}), we get $X_*=S$.
\end{proof}

\section{Numerical Experiments}
We remark that the Newton-Shamanskii method differs from Newton's method in that the  Fr\'{e}chet derivative is not updated at every iteration step. That is to say the coefficient matrix pairs of the Sylvester-type equation are evaluated and reduced with QZ algorithm after several inner iteration steps. So, while more iterations will be needed than for Newton's method, the overall cost of the Newton-Shamanskii method will be less. Our numerical experiments confirm the efficiency of the Newton-Shamskii method for QME (\ref{qme}).

The numerical tests were performed on a laptop (2.4 Ghz and 2G Memory) with MATLAB R2013a. We use $X_0=0$ as the initial iteration value of the Newton-like method. As is reported in \cite{laub}, the Hesseberg-Schur method is faster than the Bartels-Stewart method when solving the general Sylvester-type equation
\begin{equation*}
    A_1XB_1^T+A_2XB_2^T=E.
\end{equation*}
So in Newton iteration we adopt the Hesseberg-Schur method for solving the Sylvester-type equation. In Newton-Shamanskii iteration, we can reuse the reduced coefficient matrix in the back substitution step when solving Sylvester-type equation, so we adopt the Bartels-Stewart method to solve the Sylvester-type equation. That is to say in the first call to QZ algorithm, we reduce $A_1$ to quasi-upper-triangular form.

About how to choose the optimal scalars $n_i$ in the Newton-like  algorithm \eqref{qlikeb},  we have no theoretical results. In our extensive numerical experiments, we update the Fr\'{e}chet derivative every $m=2$ steps.

We define the number of the evaluation of the Fr\'{e}chet derivative in the algorithm as the outer iteration steps, which is $k+1$ for an approximate solution $x_{k,l}$ in the Newton-Shamanskii algorithm.

The outer iteration steps (denoted as ``it"),  the
elapsed CPU time in seconds (denoted as ``time"), and the normalized residual
(denoted as ``NRes" ) are used to measure the
feasibility and effectiveness of our new method, where ``NRes" is
defined as
\begin{equation*}
\mbox{NRes}=\frac{\parallel A\tilde{X}^2+B\tilde{X}+C\parallel}{\parallel \tilde{X}\parallel(\parallel A\parallel \parallel \tilde{X}\parallel + \parallel B\parallel)+\parallel C\parallel},
\end{equation*}
where $\parallel\cdot\parallel$ denotes the infinity-norm of the matrix and $\tilde{X}$ is an approximate solution to the minimal nonnegative solution of (\ref{qme}).
Numerical experiments show that the Newton-Shamanskii method are more efficient than Newton method .
\begin{example} We use the example in \cite{qlrqbd,qbd} to test our algorithm. In this example we construct a quasi-birth-death problem defined by the $n \times n$
matrices $A=W$, $B=W-I$, $C =W+\delta I$, where $I$ is the identity matrix, $W$ is a matrix having null diagonal entries
and constant off-diagonal entries,and $0 < \delta< 1$ . As was observed in \cite{qlrqbd}, the rate
$\rho = p^T (B+I+2A)e$, where $p^T (A + B+I + C) = p^T$ and $p^T e = 1$, is exactly $1-\delta$. We
have tested with three different $\delta$ values and three problem sizes. Tables \ref{tab1}, Table \ref{tab2} and Table \ref{tab3}, report the results obtained with sizes $n = 20$, $n=100$ and $n = 200$, respectively.
\end{example}

\begin{table}
\begin{center}
\caption{Comparison of the numerical results when $n=20$}
\begin{tabular}{|c|c|c|c|c|} \hline

  $\delta$ & Method  & time & it & NRes \\
  5.0e-1 & Newton  & 0.013&  5 & 4.77e-16 \\
  5.0e-1 & Newton-Shamanskii & 0.009 & 3 & 2.38e-14\\
  1.0e-1 & Newton & 0.036 & 7 & 1.61e-16 \\
  1.0e-1 & Newton-Shamanskii & 0.012 & 5 & 9.25e-16 \\
  1.0e-3 & Newton& 0.043 & 13 & 8.70e-16 \\
   1.0e-3 & Newton-Shamanskii & 0.036 & 9 & 3.00e-16 \\
  \hline
\end{tabular}\label{tab1}
\end{center}
\end{table}
\begin{table}
\begin{center}
\caption{Comparison of the numerical results when $n=100$}
\begin{tabular}{|c|c|c|c|c|}\hline

  $\delta$ & Method  & time & it & NRes \\
  5.0e-1 & Newton  & 0.142&  5 & 1.24e-15 \\
  5.0e-1 & Newton-Shamanskii & 0.110 & 3 & 2.50e-14\\
  1.0e-1 & Newton & 0.190 & 7 & 1.21e-15 \\
  1.0e-1 & Newton-Shamanskii & 0.168 & 5 & 1.60e-15 \\
  1.0e-3 & Newton& 0.444 & 13 & 1.60e-15\\
   1.0e-3 & Newton-Shamanskii & 0.359 & 9 & 6.14e-16 \\
  \hline
\end{tabular}\label{tab2}
\end{center}
\end{table}
\begin{table}
\begin{center}
\caption{Comparison of the numerical results when $n=200$}
\begin{tabular}{|c|c|c|c|c|}\hline

  $\delta$ & Method  & time & it & NRes \\
  5.0e-1 & Newton  & 1.026&  5 & 9.40e-15 \\
  5.0e-1 & Newton-Shamanskii & 0.746 & 3 & 2.34e-14\\
  1.0e-1 & Newton & 1.433& 7 & 2.18e-15 \\
  1.0e-1 & Newton-Shamanskii & 1.200 & 5 & 1.25e-15 \\
  1.0e-3 & Newton& 4.798& 13 & 5.64e-15\\
   1.0e-3 & Newton-Shamanskii & 4.271 & 9 & 2.50e-15\\
  \hline
\end{tabular}\label{tab3}
\end{center}
\end{table}

\section{Conclusions}
In this paper, we apply the Newton-Shamanskii method to the quadratic matrix equation arising from the analysis of quasi-birth-death processes. The convergence analysis shows that this method is feasible and the minimal nonnegative solution of the quadratic matrix equation can be obtained. Numerical experiments show that the Newton-Shamanskii method outperforms Newton method.


TITLE: How to convert a hypergeom function to the Legendre function?
QUESTION [1 upvotes]: Anyone can help me to convert the following maple pdsolve expressed by the hypergeom function to the $LegendreP(n,b,x)$ or $Q$ function?
\begin{equation}
dsolve\Big( (1-x^2)\cdot \frac{d^2 y(x)}{dx^2} + n(n+1) \cdot y(x) = 0 \Big); \\
y(x) = c_1 (-1+x^2) \cdot hypergeom \Big (\Big[\frac{3}{4} - \frac{1}{4} \cdot \sqrt{4 \cdot n(n+1)+1}, \frac{3}{4} + \frac{1}{4} \cdot \sqrt{4 \cdot n(n+1)+1} \Big], \Big[\frac{1}{2}\Big],x^2 \Big) + c_2 (x^3-x) \cdot hypergeom \Big( \Big[\frac{5}{4} + \frac{1}{4} \cdot \sqrt{4 \cdot n(n+1)+1}, \frac{5}{4} - \frac{1}{4} \cdot \sqrt{4 \cdot n(n+1)+1} \Big], \Big[\frac{1}{2} \Big],x^2 \Big)
\end{equation}
I just want $y(x)$ to be expressed in the form of $LegendreP(n,b,x)$.

REPLY [2 votes]: This is not an answer to the question.
Using two different CAS, the solution given for
$$(1-x^2)y''+n(n+1)y=0$$
is
$$y=c_1 \times _2F_1\left(-\frac{n+1}{2},\frac{n}{2};\frac{1}{2};x^2\right)+c_2\times x
   \times _2F_1\left(\frac{n+1}{2},-\frac{n}{2};\frac{3}{2};x^2\right)$$
For $n=1$, this would give
$$y=c_1 \left(x^2-1\right)+c_2 \left(\left(x^2-1\right) \tanh ^{-1}(x)-x\right)$$
For $n=2$, this would give
$$y=c_1 x \left(x^2-1\right)+c_2 \left(-3 x^2+3 \left(x^2-1\right) x \tanh
   ^{-1}(x)+2\right)$$
For $n=3$, this would give
$$y=c_1 \left(x^4-\frac{6 x^2}{5}+\frac{1}{5}\right)+ c_2 \left(-15 x^3+13x+3
   \left(5 x^4-6 x^2+1\right) \tanh ^{-1}(x)\right)$$
For $n=4$, this would give
$$y=c_1 \left(x^5-\frac{10 x^3}{7}+\frac{3 x}{7}\right)+c_2 \left(-105
   x^4+115 x^2-16+15 \left(7 x^4-10 x^2+3\right) x \tanh ^{-1}(x)\right)$$
You can try this and simplify the result going from $\log(.)$ to $\tanh ^{-1}(.)$.
Update
Concerning, as asked later in comments, about polynomial forms of the solutions of
$$(1-x^2)y''+ny=0$$ the general solution of which being
$$y=c_1 \times \, _2F_1\left(-\frac{\sqrt{4 n+1}+1}{4} ,\frac{\sqrt{4 n+1}-1}4 ;\frac{1}{2};x^2\right)+$$ $$\qquad c_2 \times x \times \,
   _2F_1\left(-\frac{\sqrt{4 n+1}-1}{4} ,\frac{\sqrt{4 n+1}+1}4;\frac{3}{2};x^2\right)$$ only those for which the first and second arguments of the hypergeometric functions are multiples of $\frac 12$ will show this kind of forms.
For example,
$$\left(
\begin{array}{ccc}
n & \, _2F_1\left(-\frac{\sqrt{4 n+1}+1}{4} ,\frac{\sqrt{4 n+1}-1}4 ;\frac{1}{2};x^2\right)  \\
 2 & 1-x^2  \\
 6 & \frac{1}{2} \left(2-3 x^2\right)+\frac{3}{2} x \left(x^2-1\right) \tanh
   ^{-1}(x)  \\
 12 & \left(1-5 x^2\right) \left(1-x^2\right)  \\
 20 & \frac{1}{16} \left(105 x^4-115 x^2+16\right)-\frac{15}{16} \left(7 x^5-10
   x^3+3 x\right) \tanh ^{-1}(x)  \\
 30 & \left(1-x^2\right) \left(21 x^4-14 x^2+1\right)
\end{array}
\right)$$
$$\left(
\begin{array}{ccc}
n &  \,
   _2F_1\left(-\frac{\sqrt{4 n+1}-1}{4} ,\frac{\sqrt{4 n+1}+1}4;\frac{3}{2};x^2\right) \\
 2 &  \frac{\left(1-x^2\right) \tanh ^{-1}(x)}{2 x}+\frac{1}{2} \\
 6 &  1-x^2 \\
 12 & \frac{1}{16} \left(13-15
   x^2\right)+\frac{3 \left(5 x^4-6 x^2+1\right) \tanh ^{-1}(x)}{16 x} \\
 20 & \frac{1}{3} \left(3-7 x^2\right)
   \left(1-x^2\right) \\
 30 &  \frac{1}{128} \left(315
   x^4-420 x^2+113\right)-\frac{15 \left(21 x^6-35 x^4+15 x^2-1\right) \tanh
   ^{-1}(x)}{128 x}
\end{array}
\right)$$