TITLE: Negation Normal Form and the length of formulas
QUESTION [2 upvotes]: Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. We have two well-formed formulas $\varphi$ and $\sigma$ which are equivalent: $\varphi \leftrightarrow \sigma$. The formula $\sigma$ has no occurrences of the negation symbol ($\lnot$). Now let's push negation inward to reduce $\varphi$ to Negation Normal Form and call that normal form $\varphi'$. We note that $\varphi' \leftrightarrow \sigma$.
EDIT: We further stipulate that neither $\varphi$ nor $\sigma$ contain tautologies or contradictions.
Two questions:

Can we conclude that $\varphi'$ has no occurrences of the negation symbol ($\lnot$)? If we convert both $\varphi'$ and $\sigma$ to disjunctive normal form for instance, neither should have negation symbols since we're given that $\sigma$ doesn't.
Can we conclude that the length of $\varphi'$ is bounded above by some polynomial function of the length of $\varphi$? That is, the length of $\varphi'$ won't be exponentially larger than the length of $\varphi$? If not, please provide a counterexample.

REPLY [1 votes]: No. Consider $\sigma = P$, and $\varphi = P \lor (P \land \neg P)$. These are equivalent, and since $\varphi$ is already in NNF, $\varphi'=\varphi$


TITLE: Prove a function to be analytic by dominated convergence theorem
QUESTION [0 upvotes]: Given $f \in L^1$, prove that
  $$F(z) = \frac{1}{2\pi i} \int^\infty_{-\infty} \frac{f(t)}{t-z}\,dt$$
  is an analytic function and $$F'(z)=\frac{1}{2\pi i} \int^\infty_{-\infty} \frac{f(t)}{(t-z)^2}\,dt.$$

My attempt:
It is sufficient to prove its analytic by showing that the derivative of $F(z)$ exists. (Any flaws with this argument?)
\begin{align}
F'(z)&=\lim_{\Delta z_n\to 0} \frac{F(z+\Delta z_n) - F(z)}{\Delta z_n}\\
&=\lim_{\Delta z_n\to 0} \frac{1}{\Delta z_n} \frac{1}{2\pi i} \left[\int^\infty_{-\infty} \left( \frac{f(t)}{t-(z+\Delta z_n)}-\frac{f(t)}{t-z} \right) dt \right]\\
\mbox{(a bit algebra)} &= \frac{1}{2\pi i} \lim_{\Delta z_n\to 0}   \int^\infty_{-\infty}  \frac{f(t)}{(t-z)(t-z-\Delta z_n)} \, dt \\
\end{align}
I came so close to justify the exchange of the limit with the integral (Hence, DCT). I somehow cannot find a appropriate $g\in L^1$ to bound the integrand.

REPLY [1 votes]: If $z$ is not real, you can always bound the denominator away from zero, and so you can use $f(t)/(t-z+\delta)^2$ for an appropriate (and small enough) $\delta>0$.
But when $t$ is real I see problems: for instance let $f$ be any $L^1$ function that is constant on some interval around $2$. Then
$$
\int_{-\infty}^\infty\frac{f(t)}{t-2}
$$
doesn't exists (it blows up at $2$).
Are you really supposed to show that $F$ is analytic on all of the complex plane?


TITLE: Notation for probability of either sign
QUESTION [0 upvotes]: I have a function $f(k) = \pm 2^k$ with probability $1/2$ of either sign. How would I express this in a cleaner notation? I'm guessing to use the Kronecker delta somehow, but I can't put a finger on it.

REPLY [1 votes]: You might try $f(k)=2^kX_k$ where $X_k$ is a symmetric Bernoulli random variable (this means that $\mathbb P(X_k=+1)=\mathbb P(X_k=-1)=\frac12$).


text:
\begin{document}
\title{Characterisation of Log-Convex Decay in Non-Selfadjoint Dynamics}
\keywords{Log-convex, hyponormal, non-selfadjoint, positively accretive, short-time behaviour}
\author{Jon Johnsen}
\address{Department of Mathematical Sciences, Aalborg University, Skjernvej 4A, DK-9220 Aalborg {\O}st, Denmark}
\email{jjohnsen@math.aau.dk}
\thanks{Supported by the Danish Research Council, Natural Sciences grant no.~4181-00042.}
\subjclass[2010]{35E15, 47D06}

\begin{abstract}
The short-time and global behaviour are studied for an
autonomous evolution equation, which is defined by a positively accretive operator,
inducing a holomorphic semigroup in a Hilbert space.
A general  condition is introduced under which the norm of the solution is shown to be a log-convex and
strictly decreasing function of time, and differentiable also at time zero with a derivative
controlled by the lower bound of the positively accretive operator. Injectivity of
holomorphic semigroups is the main technical tool.
\end{abstract}
\maketitle

\section{Introduction}
The subject of this short note is the global and short-time behaviour of the solutions to
autonomous evolution equations having a possibly non-selfadjoint generator $-A$.

It is assumed that $A$ is an accretive operator with domain $D(A)$ in a complex Hilbert space $H$,
with norm $|\cdot|$ and inner product $\ip{\cdot}{\cdot}$, and that $-A$ generates a uniformly bounded, holomorphic
semigroup $e^{-zA}$ for $z$ in an open sector of the form $\Sigma_{\delta}=\set{z\in\C}{-\delta< \arg
  z<\delta}$.  Then the ``height'' function
\begin{equation}
  h(t)=|e^{-tA}u_0|
\end{equation}
is studied for the solution $u(t)=  e^{-tA}u_0$ to the Cauchy problem, where $|u_0|=1$ is assumed for simplicity,
\begin{equation}
   \partial_t u+Au=0 \quad\text{ for $t>0$},\qquad u(0)=u_0\quad\text{ in $H$}.
\end{equation}
The intention is to investigate the algebraic conditions on $A$, which give a \emph{log-convex} decay of $h(t)$.

In recent article on final value problems by A.-E. Christensen and the author \cite{ChJo18ax}, cf.\
also \cite{ChJo18}, it
was elucidated and proved (except for one remnant) that if $A$ is an elliptic variational operator
and $A$ is \emph{hyponormal}, cf.\ work of Janas~\cite{Jan94}, then in terms of the numerical range and the lower bound
\begin{equation}
  \nu(A)=\Set{\ip{Ax}{x}}{|x|=1}, \qquad m(A)=\inf \,\Re\nu(A),
\end{equation}
there is a ``nice'' decay of the height function:
\begin{quote}
   $h(t)$ is \emph{strictly positive, strictly decreasing} and \emph{strictly convex} on the closed half\-line $t\ge0$,
   and $h(t)$ is differentiable at $t=0$, for $|u_0|=1$ generally with $h'(0)\le -m(A)$ though with
   $$
    h'(0)=-\Re\ip{Au_0}{u_0} \qquad\text{ if in addition $u_0\in D(A)$}.
   $$
 \end{quote}

First of all this shows how the \emph{short-time} behaviour at $t=0$ is specifically controlled by  $\nu(A)$, the
numerical range of $A$, and not by its spectrum $\sigma(A)$ (whereas the crude decay estimate $h(t)\le
Ce^{-t\underline\sigma}$ for $t\to\infty$ is given by the spectral abscissa $\underline\sigma=\inf\Re\sigma(A)$ of $A$
in case $A^*=A\ge0$). Secondly, the \emph{global} behaviour of the height $h(t)$ is
expressed in its strict decrease and strict convexity: even if $A$ has eigenvalues in
$\C\setminus\R$, as may be the case, they do not induce oscillations in the \emph{size} of the
solution $e^{-tA}u_0$ for such $A$. Indeed, this is ruled out by strict convexity, which
therefore can be seen as a stiffness in the decay of $h(t)$.

The present paper generalises the results in three ways: First the restriction
to variational generators $-A$ is removed. Indeed, monotone decay $h(t)\searrow0$ for
$t\to\infty$ results by assuming that $A$ is barely better
than accretive (i.e.\ $m(A)\ge0$) by requiring the numerical range to be contained in the open right half-plane,
\begin{equation} \label{C+-id}
  \nu(A)\subset \C_+:=\set{z\in\C}{\Re z>0}.
\end{equation}
It seems appropriate to call $A$ a
\emph{positively accretive} operator, when it has the property \eqref{C+-id}. This is a milder
condition on $A$ than strict accretivity, i.e.\ $m(A)>0$, used by Kato \cite{Kat95}.

Secondly, the additional assumption that $A$ is
hyponormal is replaced by the weaker condition that $A$ satisfies the following for vectors
$x\in D(A^2)$ such that $|x|=1$,
\begin{equation} \label{A-cond}
   2\big(\Re \ip{Ax}{x}\big)^2\le\Re\ip{A^2x}{x}+|Ax|^2.
\end{equation}
The third improvement to be obtained is the stronger conclusion that $h(t)$ is a log-convex
function
\footnote{A fortunately inconsequential flaw in the argument given for the strict convexity in
\cite{ChJo18ax} is pointed out in Remark~\ref{A2-rem} below. A remedy of this is provided by means
of the present more general results.
}.
Actually condition \eqref{A-cond} \emph{characterises} the $A$ for which $h(t)$ is
log-convex; cf.~Theorem~\ref{logcon-thm} below.

To shed light on the log-convexity criterion \eqref{A-cond}, recall that
every $B\in\B(H)$ can be written as $B=X+\im Y$ for unique selfadjoint operators $X, Y\in\B(H)$,
namely $X=\frac12 (B+B^*)$ and $Y=\frac1{2\im}(B-B^*)$. Hence
\begin{align} \label{AXY-id}
  \Re\ip{Bu}{u}&= \Re\ip{Xu+\im Yu}{u}= \ip{Xu}{u},
  \\
  \Re\ip{B^2u}{u}&= \Re\ip{(X^2-Y^2+\im(XY+YX))u}{u}=|Xu|^2-|Yu|^2,
  \\
   |Bu|^2&= |Xu+\im Yu|^2=|Xu|^2+|Yu|^2+2\Im\ip{Xu}{Yu}.
\end{align}
As the terms $\pm|Yu|^2$ cancel when the last two lines are added,
\eqref{A-cond} reduces for $B=X+\im Y$ in $\B(H)$ to
  \begin{equation} \label{A-cond''}
        \ip{Xu}{u}^2\le (|Xu||u|)^2 +\Im\ip{Xu}{Yu}|u|^2\qquad\text{for all $u\in H$}.
  \end{equation}
Here it is noteworthy that $Y$ only appears in one term. In view of the Cauchy--Schwarz inequality,
it is clear that the above is fulfilled when $X$ and $Y$ fit so together that the imaginary part is
positive for all $u\in H$. However, this is always violated for certain $B\in\B(H)$ when
$\dim H\ge2$; cf.\ Remark~\ref{Aneg-rem} below.

So, in other words, the log-convexity criterion is (as envisaged) not fulfilled for every operator
$A$ in $H$, neither for bounded $A$ nor even for  $n\times n$-matrices with $n\ge 2$.

\section{Discussion and Main Results}  \label{disc-sect}
The reader is assumed familiar with semigroup theory, for which the book of Pazy
\cite{Paz83} could be a reference; the simpler Hilbert space case is exposed e.g.\ by Grubb
\cite[Ch.\ 14]{G09}. It is briefly mentioned that there is a bijective
correspondence between the semigroups $e^{-tA}$ in $\B(H)$ that are uniformly bounded, i.e.\
$\|e^{-tA}\|\le M$ for $t\ge0$, and holomorphic in some sector $\Sigma_\delta\subset \C$ for
$\delta\in\,]0,\frac\pi2[\,$, and the
densely defined, closed operators $A$ in $H$ satisfying a resolvent estimate
$|\lambda|\|(A-\lambda I)^{-1}\|\le C$ for all $\lambda \in \{0\}\cup\Sigma_{\delta+\pi/2}$.

\bigskip

It is first recalled that for a strictly positive function $f\colon \R\to \,]0,\infty[\,$, log-convexity means
that $\log f(t)$ is convex, that is, for all $r\le  t$ in $\R$ and $0<\theta<1$,
\begin{equation} \label{f-logcon}
  f((1-\theta)r+\theta t)\le  f(r)^{1-\theta}f(t)^\theta.
\end{equation}
As a slight extension, this also makes sense for non-negative functions $f\colon \R\to[0,\infty[\,$.

A classical exercise shows that in terms of the intermediate point $s=(1-\theta)r+\theta t$,
one has that $\theta =(s-r)/(t-r)$.
Explicitly log-convexity therefore means for the height function that, for $0\le r< s<t$,
\begin{equation} \label{h-logcon}
  |e^{-sA}u_0| \le |e^{-rA}u_0|^{1-\frac{s-r}{t-r}}  |e^{-tA}u_0|^{\frac{s-r}{t-r}}.
\end{equation}
In case $\dim H=1$ the operator $A$ is just a positive scalar, so \eqref{h-logcon} is an identity because
of the functional equation of the exponential function $e^{-tA}$ (whereas its slightly weaker
property of strict convexity is expressed via a sharp inequality, oddly enough).
For  $\dim H>1$ the inequality \eqref{h-logcon} is by no means obvious for the operator function
 $e^{-tA}$ in $\B(H)$;  it is the main result of this paper.

 It is noteworthy that the application of the power function $t^\theta$, say for
 $\theta=\frac{s-r}{t-r}$, does not require the continuous extension to $t=0$, for since the
 semigroup is holomorphic, the height function fulfils $h(t)>0$, or equivalently $e^{-tA}u_0\ne0$,
 for $t\ge0$.

 This follows from the normalisation $|u_0|=1$ and the crucial fact that $e^{-zA}$ is an
 \emph{injection} for all $z\in S$:

 \begin{lem}[\cite{ChJo18ax}] \label{inj-lem}
 Whenever $-A$ generates a holomorphic semigroup $e^{-zA}$ in $\B(X)$ for some complex Banach space
 $X$, and $e^{-zA}$ is holomorphic in the open sector $\Sigma_{\delta}\subset \C$ given by $|\arg z|<\delta$ for some
 $\delta>0$, then the operator $e^{-zA}$ is injective on $X$ for each such $z$.
 \end{lem}

The injectivity is for $t>0$ clearly equivalent to the geometric property that two solutions
$e^{-tA}v$ and $e^{-tA}w$ to the differential equation $u'+Au=0$ cannot have any points of confluence in $X$ when $v\ne w$.
In particular an obvious consequence of this is the backward uniqueness of $u'+Au=0$; i.e.\ $u(T)=0$ implies $u(0)=0$.
But injectivity was seemingly first obtained in \cite{ChJo18ax},
cf.\ the elementary proof in Proposition~1 there, using unique analytic continuation.
(\cite[Cor.\ 4.3.9]{Rau91} is analogous, but is given for the Laplace operator $A=\mlap$ on
Euclidean space and local vanishing of $e^{t\lap}u_0$ in an open set at a fixed time $t>0$.)

Injectivity of $e^{-tA}$ is also a crucial tool for the proof of the log-convexity in the present paper.
Indeed, the fact that $h(t)>0$ allows an application of the next result, that characterises the
log-convex $C^2$-functions as the solutions to a differential inequality:

\begin{lem} \label{logconvex-lem}
If $f$ is continuous $[0,\infty[\,\to \,]0,\infty[\,$ and $C^2$ for $t>0$,
the following properties are equivalent:
\begin{Rmlist}
  \item For $0<t<\infty$ it holds true that
  \begin{equation}
                                      f'(t)^2\le f(t)f''(t).
  \end{equation}
  \item $f(t)$ is log-convex on the open half\-line $\,]0,\infty[\,$, that is,
  \begin{equation}
  f(s) \le f(r)^{\frac{t-s}{t-r}}  f(t)^{\frac{s-r}{t-r}} \quad\text{ for $0< r<s<t<\infty$}.
\end{equation}
\end{Rmlist}
In the affirmative case $f(t)$ is log-convex also on the closed half\-line $[0,\infty[\,$.
\end{lem}

\begin{rem}
   It is classical that a $C^2$-function $f$ is convex if and only if
  $f''\ge0$. This positivity is fulfilled if $f$ satisfies
  (I), as $(f')^2\ge0$ and $f(t)>0$ is assumed, and it is so in qualified way, equivalent to
  log-convexity by Lemma~\ref{logconvex-lem}.
  Though the lemma is not mentioned, convexity is amply elucidated in \cite{NiPe06}.
\end{rem}

\begin{proof}
By the assumptions $F(t)=\log f(t)$ is defined for $t\ge0$ and $C^2$
for $t>0$, as the Chain Rule gives
\begin{equation}
  F''(t)=\left (\frac{f'(t)}{f(t)}\right)'=\frac{f''(t)f(t)-f'(t)^2}{f(t)^2}.
\end{equation}
Hence (I) is equivalent to $F''(t)\ge 0$ for $t>0$, which is
the criterion for the $C^2$-function $F$ to be convex for $t>0$;
which is a paraphase of the condition (II) for log-convexity of the positive function
$f(t)$ for $t>0$.

By letting $r\to 0^+$ for fixed $s<t$, it follows from the continuity of $f(r)$ and
of $\exp({\frac{t-s}{t-r}}\log f(r))$, that the
inequality in (II) is valid for $0\le r<s<t$. Consequently $f$ is log-convex on the closed
half\-line $[0,\infty[\,$.
\end{proof}

To shed light on the lemma's consequences for height functions, one may conveniently use
differential calculus in Banach spaces as exposed e.g.\ by H{\"o}rmander \cite[Ch.\ 1]{H} or Lang \cite{Lan}. Note, though, that the
inner product on $H$ despite its sesquilinearity is differentiable on the induced real vector space $H_\R$
with derivative $\ip{\cdot}{y}+\ip{x}{\cdot}$ at $(x,y)\in H_\R\oplus H_\R$.
Since $u(t)=e^{-tA}u_0$ is non-zero by injectivity of the semigroup, and since
$u'=-Au$ and $u''=(-Au)'=A^2u$ for $t>0$, it follows from the Chain Rule for real Banach spaces that
\begin{equation} \label{h'-id}
  h'(t)=-\frac{\ip{Au}{u}+\ip{u}{Au}}{2\sqrt{\ip{u}{u}}} = -\frac{\Re\ip{Au}{u}}{|u|};
\end{equation}
and hence
\begin{equation}  \label{h''-id}
  h''(t)= \frac{\ip{A^2u}{u}+2\ip{Au}{Au}+\ip{u}{A^2u}}{2|u|}-\frac{(\Re\ip{Au}{u})^2}{|u|^3}.
\end{equation}
The differential inequality in (I) of Lemma~\ref{logconvex-lem},
\begin{equation} \label{h-ineq}
  (h'(t))^2\le h''(t) h(t),
\end{equation}
is therefore equivalent to
\begin{equation}
  \frac{(\Re\ip{Au}{u})^2}{|u|^2}\le   \Re\ip{A^2u}{u}+\ip{Au}{Au} -\frac{(\Re\ip{Au}{u})^2}{|u|^2};
\end{equation}
and to
\begin{equation} \label{h-ineq'}
  2(\Re\ip{Au}{u})^2\le   \Big(\Re\ip{A^2u}{u}+|Au|^2\Big)|u|^2.
\end{equation}
Obviously this condition is fulfilled for every $t>0$ when $A$ satisfies condition \eqref{A-cond}
above, for $u(t)=e^{-tA}u_0$ belongs to $D(A^n)$ for every $n\in\N$, and all $u_0\in H$, when the semigroup
is holomorphic.
So in this case, it follows from Lemma~\ref{logconvex-lem} that $h(t)=|e^{-tA}u_0|$ is log-convex
for $t\ge0$, for  the continuity of $h(t)$ and of its derivatives given above entail that the
$C^2$-condition is fulfilled.

Conversely, in case the height function $h(t)$ is known to be log-convex, then the generator $-A$
necessarily fulfils condition \eqref{A-cond} above. Indeed, in view of the equivalence of
\eqref{h-ineq} and \eqref{h-ineq'}, the former of these holds by the log-convexity of $h$, and so
does the latter. Especially it is seen by insertion of an arbitrary $u_0\in D(A^2)$ in
\eqref{h-ineq'} and commutation of $A$ and $A^2$ with the semigroup that
\begin{equation}
  2(\Re\ip{e^{-tA}Au_0}{e^{-tA}u_0})^2\le   \Big(\Re\ip{e^{-tA}A^2u_0}{e^{-tA}u_0}+|e^{-tA}Au_0|^2\Big)|e^{-tA}u_0|^2.
\end{equation}
By passing to the limit for $t\to 0^+$ it follows for reasons of continuity that
\begin{equation}
  2(\Re\ip{Au_0}{u_0})^2\le   \Big(\Re\ip{A^2u_0}{u_0}+|Au_0|^2\Big)|u_0|^2.
\end{equation}
Hence a normalisation to $x=\frac1{|u_0|}u_0$ yields \eqref{A-cond} for every unit vector
$x$ in $D(A^2)$. Altogether this shows that \eqref{A-cond} characterises the generators $-A$ of
uniformly bounded, holomorphic semigroups having log-convex height functions for non-trivial initial data.

The log-convexity criterion \eqref{A-cond} should be compared to the sufficient condition $h''(t)>0$ for strict
convexity. The latter is seen at once from the above arguments to be equivalent to the property
\begin{equation} \label{A-strictly}
  (\Re\ip{Ax}{x})^2<   \Re\ip{A^2x}{x}+|Ax|^2, \qquad\text{ for $x\in D(A^2)$, $|x|=1$},
\end{equation}
where in comparison to \eqref{A-cond} the inequality is strict and a factor of 2 is absent on the left-hand side.

This clearly indicates that log-convexity is \emph{stronger} than strict convexity for non-constant functions:

\begin{lem} \label{logcon-lem}
  When $f\colon I\to [0,\infty[\,$ is log-convex on an interval or half\-line $I\subset\R$, then
  $f$ is convex---and if $f$ is not constant in any subinterval, then $f$ is \emph{strictly} convex
  on $I$.
\end{lem}
\begin{proof}
  Convexity on $I$ follows from \eqref{f-logcon} and Young's inequality for the dual exponents $1/\theta$ and
  $1/(1-\theta)$:
  \begin{equation}
    f((1-\theta)r+\theta t)\le f(r)^{1-\theta}f(t)^\theta \le (1-\theta)f(r)+\theta f(t).
  \end{equation}

In case $f(r)\ne f(t)$, then the last inequality is strict, as equality holds in Young's inequality if
and only if the numerators are identical (cf.\ \cite[p.\ 14]{NiPe06}). This yields the inequality of strict convexity in this
case.

If there is a common value $C=f(r)=f(t)$ for some $r<t$ in $I$, there is by assumption a
$u\in\,]r,t[\,$ so that $f(u)\ne f(r)$, and because of the convexity of $f$ this entails
that $f(u)<f(r)=f(t)$: when $r<s\le u$ one may write $s=(1-\theta)r+\theta u=(1-\omega)r+\omega t$ for suitable
$\theta,\omega\in\,]0,1[\,$, so clearly
\begin{equation}
  \begin{split}
  f(s)&\le(1-\theta)f(r)+\theta f(u)
\\
      &<(1-\theta)f(r)+\theta f(t) = C= (1-\omega)f(r)+\omega f(t);
  \end{split}
\end{equation}
similarly for $u\le s<t$; so $f$ is strictly convex.
\end{proof}

For completeness it is noted that for example $f(t)=e^{t}-1$ is convex, but not log-convex as
$(\log f)''<0$. However, when $f\colon I\to \,]0,\infty[\,$ is log-convex, so is the streched function
defined for $a<b$ in $I$ as
\begin{equation}
  f_{a,b}(t)=
  \begin{cases}
    f(t)\quad\text{for $t<a$}, \\ f(a)\quad \text{for $a\le t<b$}, \\ f(t-b)\quad\text{for $b\le t$}.
  \end{cases}
\end{equation}
This follows from the geometrically obvious fact that the convexity of $\log f$ survives the
streching. Since $f_{a,b}$ clearly is not strictly convex, the last assumption of
Lemma~\ref{logcon-lem} is necessary.

It is also noteworthy that the injectivity of $e^{-tA}$ implies strict negativity of the derivative
of $h$; i.e.\ $h'<0$. Indeed, since $u_0\ne0$ gives $h(t)=|u|>0$, the assumed inclusion
$\nu(A)\subset\C_+$ in \eqref{C+-id} yields
\begin{equation} \label{h'-ineq}
  h'(t) = -\Re\Ip{A(\frac{1}{|u|}u)}{\frac{1}{|u|}u}|u|<0.
\end{equation}
Consequently $h(t)=|e^{-tA}u_0|$ is strictly decreasing for $t>0$ and this extends to the closed
half\-line $[0,\infty[\,$ by means of the Mean Value Theorem, since for some $t'\in\,]0,t[\,$,
\begin{equation}  \label{h't'-id}
  (h(t)-h(0))/t=h'(t')<0.
\end{equation}
Hence $h(t)<h(0)=1$ for all $t>0$; that is, $h$ attains a  unique global maximum at $t=0$.

Moreover, as \eqref{h'-ineq} entails that $h$ cannot be constant in any subinterval of the positive real axis, $h$ is
a strictly convex function, according to Lemma~\ref{logcon-lem} and the log-convexity.
Hence $h''(t)\ge0$ for $t>0$, so $h'(t)$ is monotone increasing on $\,]0,\infty[\,$.
Consequently $\lim_{t\to 0^+ }h'(t)=\inf_{t>0} h'$ exists in $[-\infty,0]$, cf.\ \eqref{h'-ineq},
and from \eqref{h'-ineq}, \eqref{h't'-id} it is then seen that $h(t)$ is (extended) differentiable from the right at $t=0$ with
\begin{equation}
  h'(0)=\inf h'\le -m(A).
\end{equation}

In case $u_0\in D(A)$ one can commute $A$ with the semigroup in the formula for $h'$, which by
passage to the limit gives, because of the strong continuity at $t=0$ and the continuity of inner
products,
\begin{equation}
  h'(0)=\lim_{t\to 0^+} -\Re\ip{e^{-tA}Au_0}{e^{-tA}u_0}
         = -\Re\ip{Au_0}{u_0} \quad\text{ for $u_0\in D(A)$, $|u_0|=1$}.
\end{equation}
In addition, it is seen from the proof of existence for $h'(0)$ that $h\in C^1([0,\infty[\,,\R)$ for
$u_0\in D(A)$. For general $u_0\in H$ it follows from the Chain Rule that $h\in C^\infty(\,]0,\infty[\,,\R)$.

The above discussion can now be summed up as the main result of this article:

\begin{thm} \label{logcon-thm}
  Whenever $-A$ denotes a generator of a uniformly bounded, holomorphic semigroup $e^{-tA}$ in a
  complex Hilbert space $H$, then the following properties are equivalent:
  \begin{rmlist}
    \item For every $x\in D(A^2)$ with $|x|=1$,
      \begin{equation} \label{A-cond'}
        2\big(\Re\ip{Ax}{x}\big)^2\le \Re\ip{A^2x}{x}+|Ax|^2.
      \end{equation}
   \item The height function $h(t)=|e^{-tA}u_0|$ is log-convex on $[0,\infty[\,$ for every
     $u_0\ne0$; that is, whenever $0\le r<s<t$,
\begin{equation}  \label{h-logcon''}
  |e^{-sA}u_0| \le |e^{-rA}u_0|^{\frac{t-s}{t-r}}  |e^{-tA}u_0|^{\frac{s-r}{t-r}}.
\end{equation}
  \end{rmlist}
Furthermore, if $A$ in addition to the equivalent properties \upn{(i)} and \upn{(ii)} also is positively
accretive, that is,
\begin{equation} \label{C+-id'}
  \nu(A)\subset\C_+,
\end{equation}
then for $u_0\ne0$ the function $h(t)$ is moreover strictly decreasing  (hence strictly convex) on the closed half\-line
$[0,\infty[\,$ and differentiable from the right at $t=0$, with a derivative in $[-\infty,0]$,
which satisfies
\begin{align}
  h'(0)&=\inf_{t>0} h'(t)\le - m(A)  \qquad \text{for $|u_0|=1$};
\\
\intertext{and  even}
  h'(0)&=-\Re\ip{Au_0}{u_0}
 \label{h'-eq}
\\
  h&\in C^1([0,\infty[\,,\R)\bigcap C^\infty(\,]0,\infty[\,,\R)
\end{align}
in case $u_0\in D(A)$ with $|u_0|=1$.
\end{thm}

Returning to the case of hyponormal generators considered in \cite{ChJo18ax}, it is first recalled that
a densely defined unbounded operator $A$ in $H$, following Janas~\cite{Jan94}, is said
to be hyponormal if
\begin{equation} \label{hypo-id}
  D(A)\subset D(A^*),\qquad |Ax|\ge |A^*x| \qquad\text{for all $x\in D(A)$}.
\end{equation}
Obviously this is fulfilled if $A^*=A$, but the hyponormal operators extend the
selfadjoint operators in another direction than symmetric ones do (as these have a full operator
inclusion $A\subset A^*$). Since clearly $A$ is normal if and only if both $A$ and $A^* $ are hyponormal,
this operator class is quite general.

For $A\in \B(H)$ hyponormality means that $\ip{(A^*A-AA^*)x}{x}\ge0$ for all $x$, i.e.\
the commutator is positive, $[A^*,A]\ge0$. If this is the case, the trace
$\tr([A^*,A])$ is defined, and when $A$ is a Hilbert--Schmidt operator, so that
$A^*A$ and $AA^*$ are of trace class, then $\tr([A^*,A])=\tr(A^*A)-\tr(AA^*)=0$.
Since $\|T\|\le \tr(T)$ when $T$ is positive, it follows that $[A^*,A]=0$ in
$\B(H)$. (Cf.\ Section 3.4 in \cite{GKP} for these facts.)  Therefore every hyponormal Hilbert--Schmidt operator is normal.
Especially every hyponormal $n\times n$-matrix is normal.

In case $A$ is a hyponormal operator in $H$, the inclusion $D(A)\subset D(A^*)$ gives at once
for $x\in D(A)$ that
\begin{equation}
  2\Re\ip{Ax}{x}=\ip{Ax}{x}+\ip{x}{Ax}=\ip{(A+A^*)x}{x}.
\end{equation}
Invoking also the norm inequality from the definition of hyponormality, a similar reasoning shows for $x\in D(A^2)$,
since $D(A^2)\subset D(A)\subset D(A^*)$, that
\begin{equation}
  |(A+A^*)x|^2= |Ax|^2+\ip{Ax}{A^*x}+\ip{A^*x}{Ax}+|A^*x|^2
  \le 2|Ax|^2+2\Re\ip{A^2x}{x}.
\end{equation}
Hence, by using the Cauchy--Schwarz inequality in the above identity, one finds
\begin{equation} \label{hypo-ineq}
\begin{split}
  2(\Re\ip{Ax}{x})^2&=\frac12\big(\ip{(A+A^*)x}{x}\big)^2
  \\
  &\le \frac12|(A+A^*)x|^2|x|^2
  \le \big(|Ax|^2+\Re\ip{A^2x}{x}\big)|x|^2.
  \end{split}
\end{equation}
After a normalisation to $|x|=1$, this shows that a hyponormal operator always fulfils condition (i) in
Theorem~\ref{logcon-thm}, cf.\ \eqref{A-cond'}.
Therefore one has the following generalisation of \cite{ChJo18ax} to the case of hyponormal non-variational generators:

\begin{cor} \label{hypo-cor}
 Let $-A$ denote a generator of a holomorphic semigroup $e^{-tA}$ in a
  complex Hilbert space $H$. If $A$ is positively accretive and hyponormal, cf.\ \eqref{C+-id}
  and \eqref{hypo-id}, then $A$ fulfils the equivalent
  conditions (i) and (ii) in Theorem~\ref{logcon-thm} and consequently the height function
  $|e^{-tA}u_0|$ has all the properties of log-convexity, strict convexity and strict decrease
  together with differentiablity at $t=0$ given in the theorem.
\end{cor}

It is instructive to review condition \eqref{A-cond'} in case the accretive operator $A$ is variational:
that is, for some Hilbert space $V\subset H$ algebraically, topologically and densely and some
sesquilinear form $a\colon V\times V\to \C$, which is $V$-bounded and $V$-elliptic in the sense
that (with $\|\cdot\|$ denoting the norm in $V$) for some $C_0>0$
\begin{equation}
  \Re a(u,u)\ge C_0\|u\|^2 \qquad\text{for all $u\in V$},
\end{equation}
it holds for $A$ that $\ip{Au}{v}=a(u,v)$ for all
$u\in D(A)$ and  $v\in V$. This framework and Lax--Milgram's lemma on the properties of $A$ is exposed in \cite[Ch.\ 12]{G09}.
It is classical that $-A$ generates a holomorphic semigroup $e^{-tA}$ in $\B(H)$; an explicit proof
is e.g.\ given in \cite[Lem.\ 4]{ChJo18ax}.

For such operators, $\ip{A^2u}{u}=a(Au,u)$ and $|Au|^2=a(u,Au)$ holds for $u\in D(A^2)$. So with the usual
convention for the ``real'' part, namely $a_{\Re}(v,w)=\frac12(a(v,w)+\overline{a(w,v)})$ for $v,w\in V$, one has
\begin{equation}
  \Re\ip{A^2u}{u}+|Au|^2=\Re a(Au,u)+\Re a(u,Au)= 2\Re \big(a_{\Re}a(Au,u)\big).
\end{equation}
Thus the log-convexity criterion \eqref{A-cond'} can be stated for $V$-elliptic variational operators in the form of a
comparison of sesquilinear forms,
\begin{equation}
  \big(\Re a(u,u)\big)^2\le \Re \big(a_{\Re}(Au,u)\big)\ip{u}{u}\qquad\text{ for $u\in D(A^2)$}.
\end{equation}

\begin{exmp}
  To see that variational operators need not be hyponormal, one may take $H=L_2(\alpha,\beta)$, with norm
  $\|f\|_0=(\int_{\alpha}^{\beta} |f(x)|^2\,dx)^{1/2}$, for reals $\alpha<\beta$ and let
  $V=\set{v\in H^1(\alpha,\beta)}{u(\alpha)=0}$ be a subspace of the first Sobolev space with norm
  given by $\|f\|_1^2=\int_{\alpha}^{\beta} (|f(x)|^2+|f'(x)|^2)\,dx$ and the  sequilinear form
  \begin{equation}
    a(u,v)=\int_{\alpha}^{\beta} u'(x)\overline{v'(x)}+u'(x)\overline{v(x)}\,dx.
  \end{equation}
 This is clearly $V$-bounded, and also $V$-elliptic: using partial integration and taking the mean
 of the two expressions for $a(u,v)$, one finds  $\Re a(u,u)=\|u'\|_0^2+\frac12|u(\beta)|^2$, so that
 $\Re a(u,u)\ge C_0\|u\|_1^2$ follows for all $u\in V$ and e.g.\ $C_0=\min(\frac12,(\beta-\alpha)^{-2})$ by ignoring
   the last term and applying the Poincar\'e inequality (it is known that a standard proof of this,
   as in e.g.\ \cite[Thm.\ 4.29]{G09}, applies to  the functions in $V$).

 The induced $A$ acts in the distribution space of Schwartz \cite{Swz66} as $Au=-u''+u'$,
 which is the advection-diffusion operator having its domain given by a mixed Dirichlet and Neumann condition,
 \begin{equation}
   D(A)=\Set{u\in V}{u\in H^2(\alpha,\beta),\ u'(\beta)=0}=\Set{u\in H^2(\alpha,\beta)}{u(\alpha)=0,\ u'(\beta)=0}.
 \end{equation}
(The pure Dirichlet realisation of $A=-u''+u'$ has been studied at length; cf.\
Chapter 12 in the treatise of Embree and Trefethen \cite{EmTr05}, where use of pseudospectra is the
main tool.)

 Since $A^*$ is induced by the adjoint form $a^*(u,v)=\overline{a(v,u)}$, it is similarly seen that
 $A^*u=-u''-u'$, but here with the domain characterised by a mixed Dirichlet and Robin condition,
 \begin{equation}
   D(A^*)=\Set{u\in H^2(\alpha,\beta)}{u(\alpha)=0,\ u'(\beta)+u(\beta)=0}.
 \end{equation}
 As both $D(A)\setminus D(A^*)\ne \emptyset$ and $D(A^*)\setminus D(A)\ne\emptyset$, it follows from \eqref{hypo-id}
 that neither $A$ nor $A^*$ is hyponormal. This is part of the motivation for the introduction of
 the general condition \eqref{A-cond'} in this paper.
\end{exmp}

\section{Accretive squares}  \label{A2-sect}

The considerations in \cite{ChJo18,ChJo18ax} also dealt with variational operators $A$ that, instead of being hyponormal, have
accretive squares,
\begin{equation} \label{A2+-id}
  \nu(A^2)\subset\overline{\C}_+=\set{z\in\C}{\Re z\ge0}.
\end{equation}
The discussion in Section~\ref{disc-sect} also extends to such operators without the assumption that $A$ is variational,
albeit only strict convexity is obtained for $h(t)$.

Indeed, when $m(A^2)\ge0$ holds, then it is seen from \eqref{h''-id} and Cauchy--Schwarz' inequality that
\begin{equation} \label{acc-sq}
  h''(t)=\frac{\Re\ip{A^2u}{u}|u|^{2}+|Au|^2|u|^{2}-(\Re\ip{Au}{u})^2}{|u|^{3}}
        \ge \frac{(|Au||u|)^2-(\Re\ip{Au}{u})^2}{|u|^{3}}
        \ge 0.
\end{equation}
With reference to this instead of Lemma~\ref{logcon-lem}, the arguments from
\eqref{h'-ineq} and onwards can now be repeated \emph{verbatim} when $\nu(A)\subset\C_+$; which yields strict decrease of $h(t)$
and its differentiability at $t=0$ etc.

However, it remains to show that $h(t)$ is strictly convex on $[0,\infty[\,$ when $A^2$ is
accretive (because of the number 2 on the left-hand side of
\eqref{A-cond'}, this condition is hardly implied by $m(A^2)\ge0$).
Of course the mere convexity of $h$ for $t>0$ is implied by the above inequality $h''(t)\ge0$,
so for $0<r<s<t$ one has
\begin{equation} \label{h-conv}
  h(s)\le \frac{t-s}{t-r}h(r)+\frac{s-r}{t-r}h(t).
\end{equation}
Since $h$ is continuous on $[0,\infty[\,$, this extends to $0\le r<s<t$, so $h$ is convex on $[0,\infty[\,$.

If e.g.\ $\nu(A^2)\subset\C_+$, it is seen at once from Cauchy--Schwarz'
inequality that \eqref{A-strictly} is fulfilled (or that \eqref{acc-sq} is strict), whence $h''(t)>0$ for $t>0$. Therefore $h$
is strictly convex on $\,]0,\infty[\,$ in this case.

However, by inspection of the formula above, $h''(t)=0$ is seen to imply
that both $\Re\ip{A^2u}{u}\ge 0$ and $(|Au||u|)^2-(\Re\ip{Au}{u})^2\ge 0$ must hold with equality in the first numerator.
But then the inequalities
\begin{equation}
  |\Re\ip{Au}{u}|\le |\ip{Au}{u} | \le |Au||u|
\end{equation}
hold with equality. As Cauchy-Schwarz' inequality is an identity only for proportional vectors,
there is some $\lambda=\mu+\im \omega$, $\mu,\omega\in\R$, such that $Au(t)=\lambda u(t)$. Insertion
of this into the equation $h''(t)=0$ yields
\begin{equation}
  \Re\lambda^2|u|^4+|\lambda|^2|u|^4-(\Re \lambda|u|^2)^2=0,
\end{equation}
which reduces to
\begin{equation}
  \mu^2=0.
\end{equation}
Hence $\lambda=\im\omega$ is an eigenvalue of $A$, as $u(t)=e^{-tA}u_0\ne0$ in view of the
normalisation $|u_0|=1$ and injectivity of $e^{-tA}$; cf.\ Lemma~\ref{inj-lem}. But the inclusion $\nu(A)\subset\C_+$
rules out that $A$ can have any eigenvalues on the imaginary axis. Consequently $h''(t)>0$ holds for all $t>0$,
so $h(t)$ is strictly convex for $t>0$.

To extend the strict convexity to the closed half\-line where $t\ge0$, one may conveniently take
recourse to the slope function $S(r,t)=(h(t)-h(r))/(t-r)$.
Because of the Mean Value Theorem and the strict increase of $h'$, this satisfies $S(r,s)< S(s,t)$
whenever $0<r<s<t$; which is a classical criterion for strict convexity of $h$ on $\,]0,\infty[\,$.
But this sharp inequality extends to the case $r=0$, for by introducing some $r'$ such that $r=0<r'<s<t$, one
finds from the convexity of $h$ on $[0,\infty[\,$ obtained after \eqref{h-conv} that
\begin{equation}
  S(0,s)\le S(r',s)<S(s,t).
\end{equation}
Indeed, the first of these inequalities is valid since the slope function $S(s,t)$ is monotone
increasing in both arguments separately for every convex function on an interval.
Hence $h$ is strictly convex on $[0,\infty[\,$.

Altogether this proves a result analogous to Theorem~\ref{logcon-thm}, but not quite as strong as
this, for operators $A$ with accretive squares:

\begin{prop}  \label{A2-prop}
  If $-A$ denotes a generator of a uniformly bounded, holomorphic semigroup $e^{-tA}$ in a
  complex Hilbert space $H$ and $A$ in addition to $\nu(A)\subset\C_+$ has an accretive square,
  that is
  \begin{equation}
    \nu(A^2)\subset\overline{\C}_+,
  \end{equation}
  then if $u_0\ne0$ the height function
  $h(t)=|e^{-tA}u_0|$ is strictly convex and strictly decreasing on $[0,\infty[\,$, even with
  $h''>0$ for $t>0$,
  and it is differentiable from the right at $t=0$, with a derivative in $[-\infty,0]$ satisfying
\begin{equation}
  h'(0)=\inf_{t>0} h'(t)\le - m(A) \qquad \text{for $|u_0|=1$};
\end{equation}
and if $u_0\in D(A)$ with $|u_0|=1$ it holds that $  h'(0)=-\Re\ip{Au_0}{u_0}$
and $h\in C^1([0,\infty[\,,\R)\bigcap C^\infty(\,]0,\infty[\,,\R)$.
\end{prop}

Here $h''(t)>0$ was mentioned explicitly, as not all strictly convex functions
fulfil this (cf.\ $t^4$), whereas in Theorem~\ref{logcon-thm} this property  was  straightforward
from the differential inequality characterising log-convexity.

It is obviously important for Proposition~\ref{A2-prop} to know that for an accretive operator
$A$ to have an accretive square, cf.\ \eqref{A2+-id}, it is \emph{necessary} that $A$
has semiangle $\delta\le\frac{\pi}4$, that is, $|\Im z|\le \Re z$ for every $z\in\nu(A)$.
This was shown already by Showalter \cite[Lem.\ 3]{Sho74}, who
gave the main lines in the proof of the following

\begin{lem} \label{A2-lem}
  If $A$ is an operator in $H$ so that $A$, $A^2$ are accretive, then $|\arg z|\le\pi/4$ for all $z\in\nu(A)$.
\end{lem}
\begin{proof}
  First the claim is proved for every bounded operator
  $B\in \B(H)$; here $B=X+\im Y$ for selfadjoint
  $X$, $Y\in \B(H)$, as noted prior to \eqref{AXY-id}. Since $B$ is accretive,
  $\ip{Xu}{u}=\Re\ip{Bu}{u}\ge0$ holds for $u\in H$, as does
  \begin{equation}
    \Re\ip{B^2u}{u}\ge0 \iff \ip{(X^2-Y^2)u}{u}\ge0\iff  |Yu|^2 \le |Xu|^2
  \end{equation}
   By the polar decomposition, $Y=US$ holds for a partial isometry $U$ and
  $S=|Y|=(Y^*Y)^{1/2}$; the latter is positive and fulfils $|Yu|=|Su|$ and
  $|\ip{Yu}{u}|\le\ip{Su}{u}$ for all $u\in H$ [recall that as $S\ge0$, one has
  $|\ip{Yu}{u}|^2=|\ip{Su}{U^*u}|^2\le \ip{Su}{u}\ip{SU^*u}{U^*u}=\ip{Su}{u}^2$, for
  $USU^*=|Y^*|=|Y|=S$ as $Y$ is selfadjoint, cf.\ \cite[3.2.19]{GKP}].
  Exploiting the fact $|Yu|=|Su|$ in the above,
  $m(B^2)\ge0$ is seen to imply $X^2-S^2\ge0$, which by the well-known operator monotonicity of the square root on positive operators
  implies that $X\ge S$; cf.\ \cite[E3.2.13]{GKP}. When combined with the second fact on $S$, one finds $|\ip{Yu}{u}|\le
    \ip{Su}{u}\le \ip{Xu}{u}$, so that $z=\ip{Bu}{u}$ belongs to the closed sector
    $\overline{\Sigma}_{\pi/4}\subset\C$ given by $|\arg z|\le \pi/4$.

  For general accretive $A$, the resolvent $B=(A+\varepsilon I)^{-1}$ is in $\B(H)$ for
  all $\varepsilon>0$, and for $v=B^2u\in D(A^2)$,
  \begin{equation}
    \Re\ip{B^2u}{u}=\Re\ip{(A+\varepsilon I)^2v}{v}=\varepsilon^2|v|^2+2\varepsilon \Re\ip{Av}{v}+\Re\ip{A^2v}{v}.
  \end{equation}
  Now, as $A$, $A^2$ are accretive, so is $B^2$ for $\varepsilon>0$;
  whilst $\ip{Bu}{u}=\varepsilon|v|^2+ \overline{\ip{Av}{v}}$ yields that $B$ is
  accretive. So by the above, $\ip{Bu}{u}\in\overline{\Sigma}_{\pi/4}$ for any $\varepsilon>0$; hence, by
  the formula, $\ip{Av}{v}$ must belong to $\overline{\Sigma}_{\pi/4}$ too.
\end{proof}

As motivation for stating Lemma~\ref{A2-lem} and giving a concise proof
(without the assumption, made in \cite{Sho74}, that $-A$ should
generate a $C_0$-semigroup), it should be mentioned that, contrary to the claim in \cite{Sho74}, having
semiangle $\delta\le\pi/4$ does \emph{not} suffice for $A^2$ to be accretive.

This inaccuracy was pointed out by means of the counter-example in
\cite[Rem.~9]{ChJo18ax}, which is slightly reformulated here for a better reading and in order to note
explicitly that the constructed operator gives rise to a contraction semigroup by the Lumer--Philips theorem, cf.\
\cite[Cor.\ 14.11]{G09} or \cite[Thm.\ 4.3]{Paz83}:

\begin{exmp} \label{Show-ex}
To obtain an operator $A$ so that $m(A^2)<0<m(A)$ and $\nu(A)\subset\overline{\Sigma}_{\pi/4}$,
it suffices to take $A$ in $\B(H)$ if $\dim H\ge2$:
As $A=X+\im Y$ for selfadjoint $X$, $Y\in\B(H)$,  cf.\ \eqref{AXY-id},
clearly $m(A)=m(X)$. Here $X$ can just be chosen to have
two orthonormal eigenvectors $v_1$, $v_2$ with eigenvalues $\lambda_2>\lambda_1>0$ and $X=I$ on
$H\ominus\Span(v_1,v_2)$, if this is non-trivial. Then $m(X)=\min(1,\lambda_1)>0$.
Obviously $\nu(A)\subset\overline{\Sigma}_{\pi/4}$ means that
$|\ip{Yv}{v}|\le\ip{Xv}{v}$ for all $v\in H$, or that  $-X\le Y\le X$.
This is achieved for $Y=\delta X+\lambda_1 U$ if $\delta>0$ is small enough and $U$ is a
partial isometry interchanging $v_1$ and $v_2$; with $U=0$ on $H\ominus\Span(v_1,v_2)$.
In fact, writing $v=c_1v_1+c_2v_2+v_\perp$ for $v_\perp\in
H\ominus\Span(v_1,v_2)$, since $v_1\perp v_2$, the inequalities for $Y$ are equivalent to
$2\lambda_1|\Re(c_1\bar c_2)|\le \lambda_1(1-\delta)|c_1|^2+(1-\delta)\lambda_2|c_2|^2
+(1-\delta)|v_\perp|^2$, which by Young's inequality is
assured if $1/(1-\delta)\le (1-\delta)\frac{\lambda_2}{\lambda_1}$, that is if $0<\delta\le
1-\sqrt{\lambda_1/\lambda_2}$.
Now, $m(A^2)\ge0$ means that $|Xv|^2\ge |Yv|^2$ for all $v$ in $H$, but
this is \emph{always} violated, as one can see from
$|Yv|^2= \delta^2|Xv|^2+\lambda_1^2|Uv|^2+2\delta\lambda_1\Re\ip{Xv}{Uv}$ by inserting $v=v_1$,
whereby the last term vanishes as $v_1\perp v_2=Uv_1$: this leads to
\begin{equation}
  |Xv_1|^2-|Yv_1|^2
  = \lambda_1^2|v_1|^2-(\delta^2\lambda_1^2|v_1|^2+\lambda_1^2|v_2|^2)= -\delta^2\lambda_1^2<0 .
\end{equation}
Specifically the matrices $    A=
   \left(\begin{smallmatrix}\lambda&0\\0&4\lambda\end{smallmatrix}\right)
  + \im\lambda\left(\begin{smallmatrix}\delta& 1\\ 1 & 4\delta\end{smallmatrix}\right)$
are counter-examples in $\B(\C^2)$ for $\lambda>0$, $0<\delta\le 1/2$.
\end{exmp}

\begin{rem} \label{Aneg-rem}
The bounded operator $A$ constructed in Example~\ref{Show-ex} above is also useful in relation to the log-convexity criterion \eqref{A-cond'} in Theorem~\ref{logcon-thm}.
The notation from Example~\ref{Show-ex} is continued here.

First $A=X+\im Y=(1+\im\delta)X+\im \lambda_1 U$ entails
$[A^*,A]=2\im[X,Y]=2\lambda_1\im[X,U]$, so  $w=c_1v_1+c_2v_2$ gives $[A^*,A]w=2\im\lambda_1((\lambda_1-\lambda_2)c_2v_1+(\lambda_2-\lambda_1)c_1v_2)$.
Hence $[A^*,A]\ne0$, so $A$ is non-normal in $\B(H)$.

Moreover, one has
$\ip{[A^*,A]w}{w}=2\im\lambda_1((\lambda_1-\lambda_2)\bar
c_1c_2+(\lambda_2-\lambda_1)c_1\bar c_2)=4\lambda_1(\lambda_1-\lambda_2)\Im(c_1\bar c_2)$,
and insertion of $c_1=\pm c_2=2^{-1/2}$ yields that $\nu([A^*,A])$ contains $\pm 2\lambda_1(\lambda_2-\lambda_1)\ne0$;
hence both $[A^*,A]$ and $[A,A^*]$ are non-positive. Therefore neither $A$ nor $A^*$ is hyponormal.

Furthermore $A$ does not satisfy the criterion for log-convexity in
Theorem~\ref{logcon-thm} for any choice of the parameters. Indeed, for this operator $A$
the criterion for bounded operators in \eqref{A-cond''} is that, for $v\in H$,
  \begin{equation}
        \ip{Xv}{v}^2\le (|Xv||v|)^2 +\Im\ip{Xv}{\delta Xv +\lambda_1Uv}|v|^2
        = (|Xv||v|)^2 +\lambda_1\Im\ip{Xv}{Uv}|v|^2.
  \end{equation}
Here it is obvious that $\delta$ is absent in the criterion. To show that the inequality is violated for any choice
of $\lambda_2>\lambda_1>0$ it suffices to insert vectors of the form $v=\im sv_1+v_2$ for $s>0$.
As $|v|^2=s^2+1$ due to the orthogonality, and $Xv=\im s\lambda_1v_1+\lambda_2v_2$
while $Uv=v_1+\im sv_2$, the above gives for this $v$,
\begin{equation}
  \begin{split}
  (s^2\lambda_1+\lambda_2)^2&\le (s^2+1)(s^2\lambda_1^2+\lambda_2^2+\lambda_1\Im(\im s(\lambda_1-\lambda_2))),
\\
  &\le (s^2+1)(s^2\lambda_1^2+\lambda_2^2+s\lambda_1(\lambda_1-\lambda_2)).
  \end{split}
\end{equation}
 As the fourth order term $\lambda_1^2s^4$ cancels on both sides, the term of highest
 degree in the resulting polynomial is $s^3\lambda_1(\lambda_1-\lambda_2)$ on the right-hand
 side. After division by $s^3$ and passage to the limit $s\to\infty$ one therefore  arrives at the
 false statement  ``$0\le \lambda_1(\lambda_1-\lambda_2)$''.
Consequently the operator $A$ from Example~\ref{Show-ex} does not fulfil the log-convexity criterion
in Theorem~\ref{logcon-thm} for any of the considered values of the parameters. Especially this is
so for the matrix given at the end of Example~\ref{Show-ex}.
\end{rem}

\section{Final remarks}

\begin{rem} \label{A2-rem}
When $\nu(A^2)\subset\overline{\C}_+$ as in Section~\ref{A2-sect}, it is also illuminating to observe the possibility to depart from
the cleaner expression of the derivatives of the squared height $h(t)^2=|e^{-tA}u_0|^2$:
\begin{equation} \label{h2''-id}
  (h^2)''(t)=(-2\Re\ip{Au}{u})'= 2\Re\ip{A^2u}{u}+2|Au|^2\ge |Ae^{-tA}u_0|^2.
\end{equation}
Here $e^{-tA}$ is injective, and $A$ is so as $\nu(A)\subset\C_+$, whence $u_0\ne0$ yields
$(h^2)''>0$.
Similarly $(h^2)''>0$ can be seen from \eqref{hypo-ineq} to hold if $A$ is hyponormal.
That is, $h^2$ is in both cases strictly convex for $t>0$.

But as $\sqrt\cdot$ is concave (not convex), strict convexity of
$h^2$ is not simply carried over to $h$.
As the task is to prove $h'$ strictly increasing, the formula $h'=(h^2)'/(2\sqrt{h^2})$ looks
convincing as there is strict decrease of the denominator  while the numerator is increasing\,---\,but
the formula does not lead to the desired conclusion because $(h^2)'<0$. This small point was overlooked in \cite[Prop.~4]{ChJo18ax},
yet the statement there is nevertheless correct.

Indeed, in the framework of positively accretive $A$, \cite[Prop.~4]{ChJo18ax} is generalised
to non-variational $A$ having accretive squares in Proposition~\ref{A2-prop},
and to non-variational hyponormal $A$ in Corollary~\ref{hypo-cor}. A further generalisation to
operators satisfying the log-convexity criterion \eqref{A-cond'} is provided by Theorem~\ref{logcon-thm}.
\end{rem}

\begin{rem}
  For matrices $A$ in $\B(\Cn)$ the dynamical properties have been studied for decades, and there
  are some similar results, a glimpse of which is given here, following the inspiring exposition of
  Embree and Trefethen \cite[Ch.\ 14]{EmTr05}. A major subject of interest has been the behaviour
  of the operator norm $E(t)=\|e^{-tA}\|$, which has the benefit of being independent of any
  initial data $u_0$, thereby letting the influence of especially nonnormal matrices shine
  though. At $t=0$ it is a main result that
  \begin{equation} \label{E'-id}
    E'(0)=-m(A),
  \end{equation}
  which also shows the role of the numerical range $\nu(A)$ of $A$. Moreover, for $t\to\infty$ it
  is known that $\log E(t)\to -\underline\sigma$, where again $\underline\sigma=\inf\Re\sigma(A)$ denotes the
  spectral abscissa of $A$; so the long-term behaviour is controlled by the spectrum of
  $A$. For the transition phase there are estimates of $\sup_{t\ge0} E(t)$ in terms of the Kreiss constant
  of $-A$ or the pseudospectral estimate $\sup_{t\ge0}E(t)\ge \alpha_\varepsilon(-A)/\varepsilon$.

  However, when $u_0$ is reintroduced, the inequality $|e^{-tA}u_0|\le E(t)|u_0|$
  is a crude estimate (a worst-case scenario), which does not suffice to settle whether
  $h(t)=|e^{-tA}u_0|$ has properties like strict decrease or
  log-convexity as in Theorem~\ref{logcon-thm}. Moreover,
  \eqref{E'-id} is often highly misleading for the short-time behaviour of $h(t)$ itself. For
  example, for $A=\left(\begin{smallmatrix}-1&0\\0&3\end{smallmatrix}\right) $ one has
  $\nu(A)=[-1,3]$ with $m(A)=-1$, so while $E'(0)=1$ holds by \eqref{E'-id}, indicating a
  \emph{growth} at $t=0$, the choice $u_0=e_2=(0,1)$ gives, because of \eqref{h'-eq},
  \begin{equation}
    h'(0)=-\Re\ip{Ae_2}{e_2}=-3<1=E'(0).
  \end{equation}
 This sharp contrast between the properties of the solutions to $u'+Au=0$, $u(0)=u_0$, and those of
 $\|e^{-tA}\|$ also motivates the study of the height function $h(t)=|e^{-tA}u_0|$ in the present paper.
\end{rem}

\begin{rem} \label{contraction-rem}
  If the generator $-A$ of the uniformly bounded holomorphic semigroup is dissipative, i.e.\ $A$
  is accretive, then $e^{-tA}$ is a classical contraction semigroup; cf.\ \cite[Cor.\ 14.11]{G09}.
  That is, $\|e^{-tA}\|\le 1$ holds for the operator norm for $t\ge0$, whence $h(t)\le
  \|e^{-tA}\|\cdot |u_0|\le |u_0|$---i.e.\ an estimate by a constant. If $m(A)>0$ it is also classical that
  $-(A-\varepsilon I)$ for $0<\varepsilon<m(A)$ gives the contractions
  $e^{-t(A-\varepsilon I)}=e^{t\varepsilon}e^{-tA}$, so the sharper estimate $|e^{-tA}u_0|\le
  e^{-t\varepsilon}|u_0|$ holds for $t\ge0$ and any $\varepsilon\in\,]0,m(A)[\,$, hence also for
  $\varepsilon=m(A)$.
  But this exponential decay is just a crude estimate that requires
  $m(A)>0$. For comparison it observed that if $A$ is merely positively accretive and satisfies the log-convexity
  criterion \eqref{A-cond'}, so that $m(A)=0$ is
  possible and Theorem~\ref{logcon-thm} applies, the log-convex and strictly decreasing
  behaviour of the height function $|e^{-tA}u_0|$  is a rather more precise dynamical
  property of the evolution problem $u'+Au=0$, $u(0)=u_0$.
\end{rem}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }

\providecommand{\MRhref}[2]{
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}

config: arxiv


TITLE: Solutions to a Cubic Root
QUESTION [2 upvotes]: I'm looking for a sanity check to my work.
We are supposed to find the solutions of the cubic polynomial, $x^3+3x+5=0$.
Let $x=w-\frac{1}{w}$ and substitute.
Then $(w-\frac{1}{w})^3+3(w-\frac{1}{w})+5=0$.
Then $w^3+5w^3-1=0$.
Finally $w^3=\frac{-5+\sqrt{29}}{2}$ and $\frac{-5-\sqrt{29}}{2}$.
Solution 1: $\sqrt[3]\frac{-5+\sqrt{29}}{2}-\sqrt[3]\frac{-5-\sqrt{29}}{2}$.
Solution 2: $\left(\frac{-1+\sqrt{3}i}{2}\right)$$\sqrt[3]\frac{-5+\sqrt{29}}{2}-\left(\frac{-1-\sqrt{3}i}{2}\right)$$\sqrt[3]\frac{-5-\sqrt{29}}{2}$.
Solution 3: $\left(\frac{-1-\sqrt{3}i}{2}\right)$$\sqrt[3]\frac{-5+\sqrt{29}}{2}-\left(\frac{-1+\sqrt{3}i}{2}\right)$$\sqrt[3]\frac{-5-\sqrt{29}}{2}$.

REPLY [1 votes]: In general Let be $f(x)=x^3+ax+b$
put $x=u-v$, then $f(u-v)=(u^3-v^3)-(3uv-a)(u-v)+b$ and if $f(u,v)=0$, then $(u^3-v^3)+b=0$ and $3uv-a=0$. From second equation we have $v=\frac{a}{3u}$ and then $u^3-(\frac{a}{3u})^3+b=0 \Rightarrow 3^3u^6-a^3+3^3u^3b=0\Rightarrow 3^3y^2+3^3by-a^3=0 ; y=u^3 $, we solve the equation for $y$, then we have $y=\frac{-b}{2}+\sqrt{(\frac{b}{2})^2+(\frac{a}{3})^3 } \Rightarrow u=\sqrt[3] {y}=\sqrt[3]{\frac{-b}{2}+\sqrt{(\frac{b}{2})^2+(\frac{a}{3})^3 }} $ and $v^3=u^3+b\Rightarrow v=\sqrt[3]{u^3+b}=\sqrt[3]{\frac{b}{2}+\sqrt{(\frac{b}{2})^2+(\frac{a}{3})^3 }} $.Therefore first solution of $f(x)$ is $u-v$
and other solutions are complex, i.e. second solution is $\zeta u-\zeta^2v$ and third solution is $\zeta^2 u-\zeta v$.
In question we have $a=3, b=5$, then $ y=\frac{-5+\sqrt{29}}{2} \Rightarrow u= \sqrt[3] {\frac{-5+\sqrt{29}}{2} }, v= \sqrt[3] {\frac{5+\sqrt{29}}{2} } $ ,so
first solution is $u-v=\sqrt[3] {\frac{-5+\sqrt{29}}{2} }- \sqrt[3] {\frac{5+\sqrt{29}}{2} } $
second solution is $\zeta u-\zeta^2v=(\frac{-1+\sqrt3i}{2})\sqrt[3] {\frac{-5+\sqrt{29}}{2} }- (\frac{-1-\sqrt3i}{2}) \sqrt[3] {\frac{5+\sqrt{29}}{2} }$
third solution is $\zeta^2 u-\zeta v=(\frac{-1-\sqrt3i}{2})\sqrt[3] {\frac{-5+\sqrt{29}}{2} }- (\frac{-1+\sqrt3i}{2}) \sqrt[3] {\frac{5+\sqrt{29}}{2} }$


TITLE: curve with two minimum points
QUESTION [0 upvotes]: how can we mathematically express a function whose the graph is a curve, like a parabola, where it has a minimum point (or maximum if opposite, it doesn't matter) BUT the minimum point is not one, but TWO points, one next to the other? is it possible?

REPLY [2 votes]: How about $x^4-4x^2$?  This has minima at $x=\sqrt{2}$ and $x=-\sqrt{2}$.


TITLE: The free group II$_{\infty}$ factor isomorphism problem
QUESTION [5 upvotes]: Let $\Gamma$ be an infinite discrete group, and $H = l^{2}(\Gamma)$ the separable infinite dimensional Hilbert space.
Let $\rho$ be the left regular representation of $\Gamma$ on $H$.
Definition : Let $L(\Gamma) := \rho (\Gamma)''$ the von Neumann algebra generated by $\Gamma$.
Proposition :  $L(\Gamma)$ is a $II_{1}$ factor iff $\Gamma$ is ICC (infinite conjugacy class).
Let $\Gamma = \mathbb{F}_{n} = \langle a_{1}, a_{2},..., a_{n} \vert   \rangle$  the free group with $n$ generator. It's ICC iff $n \geq 2$.
Free group factor isomorphism problem : $L(\mathbb{F}_{n}) ≃ L(\mathbb{F}_{m})$, $∀n,m≥2$ ?
Voiculescu's formula (see here p 3) :  $L(\mathbb{F}_{n}) \simeq L(\mathbb{F}_{(n-1)k^{2}+1}) \otimes M_{k}(\mathbb{C})$
Example:  $L(\mathbb{F}_{2}) \simeq L(\mathbb{F}_{5}) \otimes M_{2}(\mathbb{C})$
Corollary: $\bigotimes_{i} L(\mathbb{F}_{n_{i}})   \simeq \bigotimes_{i} L(\mathbb{F}_{m_{i}})$ if $\prod_{i}(n_{i}-1) = \prod_{i}(m_{i}-1)$
Observation : $L(\mathbb{F}_{n}) \otimes B(H) \simeq L(\mathbb{F}_{(n-1)k^{2}+1}) \otimes M_{k}(\mathbb{C}) \otimes B(H) \simeq L(\mathbb{F}_{(n-1)k^{2}+1})  \otimes B(H)$
However, "$\exists k_{1}, k_{2} $ : $(n-1)k_{1}^{2}+1 = (m-1)k_{2}^{2}+1$" $\Leftrightarrow$  "$(n-1)(m-1)$ is a square".
Corollary: $L(\mathbb{F}_{n}) \otimes B(H) \simeq  L(\mathbb{F}_{m}) \otimes B(H)$   if $(n-1)(m-1)$ is a square.

Question :  Is it known to be true in general : $L(\mathbb{F}_{n}) \otimes B(H) \simeq  L(\mathbb{F}_{m}) \otimes
 B(H)$ $\forall n, m \ge 2$ ?
  (if "no", is it equivalent to the free group factor isomorphism problem ?)

In general:  $L(\mathbb{F}_{n}) \simeq L(\mathbb{F}_{m})^{\alpha} $ with  $\alpha = (\frac{m-1}{n-1})^{1/2}$.
Definition: Let $\mathcal{M}$ be a $II_{1}$ factor, then $\mathcal{M}^{t} \simeq p(M_{k}(\mathbb{C}) \otimes  \mathcal{M})p \simeq q(B(H) \otimes  \mathcal{M})q$,
 with $q \in B(H) \otimes  \mathcal{M}$ and $p \in M_{k}(\mathbb{C}) \otimes  \mathcal{M}$ projections, $Tr(q) = t$,  $k=\lceil t \rceil$ and $\tau(p) = \frac{t}{k}$.
Remark : Let $n, m \ge 2$ such that $(n-1)(m-1)$ is a square.
Let the $II_{\infty}$ factor $\mathcal{N} \simeq  L(\mathbb{F}_{n}) \otimes B(H) \simeq  L(\mathbb{F}_{m}) \otimes B(H)$.
Let $Tr$ (resp. $Tr'$) be the trace on $\mathcal{N}_{+}$ coming from the unique trace of $L(\mathbb{F}_{n})$ (resp. $L(\mathbb{F}_{m})$).
Let the projection $p, q \in \mathcal{N}$ such that $Tr(p) = Tr'(q) = 1$.
Then  $p \mathcal{N} p \simeq L(\mathbb{F}_{n})$ and $q \mathcal{N} q \simeq L(\mathbb{F}_{m})$. So, $Tr' = \alpha Tr$ with  $\alpha = (\frac{n-1}{m-1})^{1/2}$.

REPLY [7 votes]: Yes, this is true.
Radulescu introduced the interpolated free group factors $L(\mathbb{F}_r)$ for all $1<r<\infty$. They obey the rule that if $r\in\mathbb{N}$ then we get the proper free group factor and they also obey,
$L(\mathbb{F}_r)^s=L(\mathbb{F}_{r'})$ where $r'={1+\frac{r-1}{s^2}}$. This gives that all free group factors are amplifications of each other. Which implies that they all generate the same $II_\infty$ factors. (ie $L(\mathbb{F}_n)\overline\otimes\mathcal{B(H)}\simeq L(\mathbb{F}_m)\overline\otimes\mathcal{B(H)} $.
Further, this reduces the free group factor isomorphism problem to the calculation of the fundamental groups one of the finite free group factors.
It is known that it is either
I.) All of $\mathbb{R}^+$ in which case they are all isomorphic.
II.) Or $\{1\}$, in which case they are all non-isomorphic.
Here is part of Dykema's thesis where this is proved.
http://arxiv.org/pdf/funct-an/9211012v1.pdf


text:
\def\DATE{April 12, 2020}

\line{\fchapter\hfill\the\chapterNo.\qquad Algorithms}
\vSkipAfterTitle

\def\prevs{\the\chapterNo.\the\sectionNo.\the\statementNo}
\def\preveq{(\the\chapterNo.\the\sectionNo.\the\equationNo)}

\noindent

\bigskip

\noindent
The purpose of this chapter is to gather several algorithms which allow one to
implement the results obtained so far. These algorithms will be used in our
next chapter when we study particular equations.

This chapter is as self-contained as possible, in the sense that the
implementation of these algorithms does not require a deep understanding
of the previous chapters. It is aimed at readers with primary interest in
applications.

We use the term algorithm in a loose way, because
the main methods we show depend on operations which are known to be
non-algorithmic, such as, for example, finding roots of polynomials or deciding
whether a number is zero.

In applications, $q$ may be either a generic variable, or can be specified as
a given value. Overall, if all the coefficients and parameters of
a $q$-algebraic equation are specific numbers, then all polynomials involved
in finding the solution, such as the indicial and initial polynomials, are
explicit. Their roots can be found numerically. When $q$ or other quantities
in the equation are generic parameters, our key algorithms are subject
to the ability to solve for zeros of polynomials whose coefficients may
be parameters with unspecified values. In this case, as we will see in our
last chapter devoted to examples, the main use of the algorithms is then not
to automate the process of studying $q$-algebraic equations, but to provide
a clear path on how to study these equations, this study requiring often a
combination of hand calculation and the use of a computer algebra package.

\bigskip

\section{Notation and assumptions}

All the procedures described below are given a name typeset in small capitals,
and, whenever they are used, a notation like $\algoname{algo}(a,b)$
means that procedure \algoname{algo} is called with parameters $a$ and
$b$. The required parameters for each procedure are stated in the
corresponding
{\bf Require} section. Although this is remarked whenever
necessary, there are places where a method is called which has not
been defined. This implies that that method is assumed to be part of
the symbolic algebra system or that its implementation is rather
straightforward. For example, $\algoname{roots}(P)$ refers
to a procedure which should return the roots of a polynomial $P$.

It is convenient to have a hash table which
associates to each point in the cloud, the list of monomials in $P$
corresponding to that point. This makes the coding and
computations easier, albeit at a price in memory use. We assume that
this hash table is defined, and will call it $\hash(P,p)$, where $p$ is
a point. Thus, $\hash(P,p)$
is the list of monomials of $P$ whose corresponding point is
$p$. It is an empty list if no monomial corresponds to $p$,
and, more generaly, it represents what we would write $P_p$ with
notation \PQNotation.

We distinguish between lists and tuples, using brackets for lists and
parentheses for tuples. If $L$ is a list, then \PUSH{L}{c}
adds the elements $c$ to the end of list $L$.

For convenience, we use the following notation: if $p$ is a point in the plane,
$\scx (p)$ and $\scy (p)$ are its abscissa and ordinate.

\bigskip

\section{\ikey{Newton-Puiseux polygon}}
Given a polynomial $P$ in $\CC\[[z^{\RR}\]][\,Y_0,\dots,
Y_n\,]$, or more precisely, a $q$-operator with finite support,
we want to generate a data structure describing the
Newton-Puiseux polygon corresponding to $P$. For this we need the
cloud of points, though only the leftmost points at each height are needed
to describe the Newton-Puiseux polygon. The polygon
is completely described by its vertices, but it is convenient to add
the list of co-slopes of each side.

\subsection{Computation of the \ikey{Newton-Puiseux polygon}}
In order to compute the actual vertices of the Newton-Puiseux polygon,
we proceed geometrically as follows. First of all, we compute the list of
leftmost vertices at each height and order them according to
increasing ordinate, obtaining a list $[\,p_1, \dots, p_n\,]$.
If there is only one, this
means that all the points in the cloud have the same ordinate and
the polygon is just the half line starting at $p_1$ and going to the
right. Procedure \algoname{newton-puiseux-polygon} returns a pair made of
two lists: the first list, {\it vertices}, contains the vertices of
the Newton-Puiseux polygon, the second one, {\it coslopes},
contains the co-slopes of the sides. This procedure uses another one,
\algoname{coslope}$(p_1,p_2)$, which returns the co-slope of the line passing
through $p_1$ and $p_2$, that is, when $p_1$ and $p_2$ do not have the same
ordinates,
$\bigl(\scx(p_2)-\scx(p_1)\bigr)\bigm/\bigl(\scy(p_1)-\scy(p_2)\bigr)$.

\finetune{\vfill\eject}

\ALGORITHM{\algoname{newton-puiseux-polygon}. Computation of the
    Newton-Puiseux polygon (vertices and co-slopes).
  }{
\REQUIRE a list $[\,p_1, \dots, p_n\,]$ of points in the plane
ordered by strictly increasing ordinate (no two points with same ordinate).
    \START{newton-puiseux-polygon}
    \STATE $v\leftarrow p_1$
    \STATE {\it vertices}$\,\leftarrow[\,v\,]$;
{\it coslopes}$\,\leftarrow[\,\,]$
    \STATE $\mu = -\infty$ \COMMENT{$\mu$ will be the last computed co-slope}
    \WHILE{$v \not=p_n$}
    \STATE $j\leftarrow\min\{\, i\,:\, \scy(p_i)>\scy(v)\,\}$
    \WHILE{$j\leq n$}
    \STATE $\lambda\leftarrow \algoname{coslope}(v, p_j)$
    \IF{$\lambda \geq \mu$} \COMMENT{note $\geq$, not $>$}
    \STATE $\mu \leftarrow \lambda\,;\, \hbox{\it nextv} \leftarrow p_j$
    \ENDIF
    \STATE $j \leftarrow j + 1$
    \ENDWHILE
    \STATE \PUSH{\hbox{\it vertices}}{\hbox{\it nextv}}
    \STATE \PUSH{\hbox{\it coslopes}}{\mu}
    \STATE $v\leftarrow \hbox{\it nextv}$
    \ENDWHILE
    \RETURN $(\hbox{\it vertices}, \hbox{\it coslopes})$
}

\subsection{Convenience methods} The following easy-to-implement
methods will be useful.

\noindent{\it Points at a \ikey{co-slope}.} Recall that $L_\mu(P)$ is the leftmost
line of co-slope $\mu$ meeting the Newton-Puiseux polygon in a nonempty set.
Given a co-slope $\mu$, the points which are part of $L_{\mu}$
can be computed using minima as procedure
\algoname{points-at-coslope} describes. We use this because
procedure \algoname{newton-puiseux-polygon} only returns the vertices,
and therefore, if an edge of the polygon contains more than two points,
some of those points will not be included.

\ALGORITHM{\algoname{points-at-coslope.} Points of the cloud on $L_\mu$.}{
\REQUIRE the list of points in the cloud,
$\hbox{\it cloud}=[\,p_1, \dots, p_n\,]$, and a co-slope $\mu$.
    \START{points-at-coslope}
    \STATE $\hbox{\it output}\leftarrow[\,\,]$
    \STATE $\nu \leftarrow
            \min\{\,\scx (p)+\mu \scy (p)\,:\, p\in\hbox{\it cloud}\,\}$
    \FOR{$p$ \IN $\hbox{\it cloud}$}
    \IF{$\scx (p) + \mu \scy (p) = \nu$}
    \STATE \PUSH{\hbox{\it output}}{p}
    \ENDIF
    \ENDFOR
    \RETURN{\hbox{\it output}}
}

\bigskip

\noindent{\it \ikey{Indicial polynomial} of a point.} Recall that
for a point $p$ in the cloud of $P$, the indicial polynomial of $P$ at $p$ is
$$
  \Psi_{P,p}(t) = \sum_{\ss A\in P\atop\ss(a, \ell)=p}P_At^{\alpha(A)} \, .
$$
Procedure \algoname{indicial-polynomial} shows how to compute
$\Psi_{P,p}(t)$. Assume that $P$ is a polynomial in $z$ and $Y_0,\ldots,Y_n$.
We compute the coefficient of a monomial of $\Psi_{P,p}(t)$
by substituting $z$ by $1$  and all the $Y_i$, $1\leq i\leq n$,  by $t$.
We assume that the procedure \algoname{substitute}$(L,E)$ allows us to make
the substitution indicated by the list $L$ in the expression $E$. For instance
$\algoname{substitute}([\,z=1,Y_0=t\,], z^3Y_0^4Y_1)$ would return $t^4Y_1$.

\ALGORITHM{\algoname{indicial-polynomial.}
           The indicial polynomial for $P$ at a point $p$.
          }{
    \REQUIRE{a $q$-operator $P$ and a point $p$.}
    \START{indicial-polynomial}
    \STATE{$\Psi(t) \leftarrow 0$}
    \FOR{$A$ \IN $\hash(P,p)$}
    \STATE{$\Psi(t) \leftarrow \Psi(t)
      + \algoname{substitute}([\,z=1\,;\, Y_i=t\,;\, 0\leq i\leq n\,], A)$}
    \ENDFOR
    \RETURN $\Psi$
}

\noindent{\it \ikey{Initial polynomial} for a given co-slope.}
Computing the initial polynomial for a given co-slope is just a matter of
computing the indicial
polynomials and multiplying their evaluations at $q^{\mu}$ by the
appropriate power of the variable $c$, and summing. We assume that the
procedure $\algoname{cloud}(P)$ returns the list of points in the cloud of $P$.
We assume that given a list of points, {\it listOfPoints}, the procedure
\algoname{leftmost-point} returns a list containing for each ordinate the
leftmost point in the list {\it listOfPoint}. The list returned is assumed to
be ordered by increasing ordinates.

\ALGORITHM{\algoname{initial-polynomial}.
           Compute the initial polynomial of a $q$-operator $P$ for a
           co-slope $\mu$.}{
    \REQUIRE a $q$-operator $P$ and a co-slope $\mu$.
    \START{initial-polynomial}
    \STATE $\Phi(c) \leftarrow 0$
    \STATE $\hbox{\it temporary}\,\leftarrow\algoname{NEWTON-PUISEUX-POLYGON}
            \bigl($
    \STATE \finetune{\hskip 137pt}$\algoname{leftmost-points}
            \bigl(\algoname{CLOUD}(P) \bigr)\bigr)$
    \STATE $\hbox{\it points}\,\leftarrow \algoname{points-at-coslope}
            (\hbox{\it temporary},\mu)$
    \FOR{$p$ \IN \hbox{\it points}}
    \STATE $m = \scy (p)$
    \STATE $\Phi(c) \leftarrow \Phi(c)
    + c^m\,\algoname{indicial-polynomial}(P,p)(q^{\mu})$
    \ENDFOR
    \RETURN $\Phi(c)$
}

\noindent{\it \ikey{Translation} $T_{cz^\mu}$.}
Translating and shifting are probably the most used operations
when trying to study solutions of $q$-algebraic equations. One only needs
to take care of the adequate exponents of $q$, as shown in the following
procedure \algoname{translation}.

\ALGORITHM{\algoname{translation.} Translate a $q$-operator by $cz^{\mu}$.
    }{
    \REQUIRE a $q$-operator $P$, a complex number $c$, and a co-slope $\mu$.
    \START{translation}
    \STATE $Q \leftarrow P$
    \STATE $\oalpha \leftarrow \max\{\alpha_{\ell} : A \in P\}$
    \STATE $Q \leftarrow \algoname{substitute}
         \,([\,Y_i = Y_i +cq^{i\mu}z^{\mu}\,;\, 0\leq i\leq \oalpha\,] , Q)$
    \RETURN $Q$
}

\noindent{\it \ikey{Simplification} by $z$.}
Simplifying by $z$ is simple as translating, as procedure
\algoname{simplify} shows.

\ALGORITHM{\algoname{simplify}. Simplify a $q$-operator by $z$.}{
    \REQUIRE a $q$-operator $P$ and a complex number $c$.
    \STATE \hskip-10pt$\star$ Start \algoname{simplify}
    \STATE $Q \leftarrow P$
    \STATE $\oalpha \leftarrow \max\{\alpha_{\ell} : A \in P\}$
    \STATE $Q \leftarrow \algoname{substitute}
            \,([\,Y_i = c + zY_i\,;\, 0\leq i\leq \oalpha \,], Q)$
    \RETURN $Q/z$
}

Note that procedure \algoname{simplify} may return something which has
a nonzero denominator in $z$ if $P_{(0;\sp)}$ does not vanish (see Propostion
\SFSimplificationMeaning).

\noindent{\it Test for solved form.}
One usually wants to check whether a $q$-algebraic equation is in
solved form or not. This is what procedure \algoname{is-in-solved-form}
does. It assumes that there exist four procedures,

\medskip\noindent
-- \algoname{z-exponent}, which returns the exponent of $z$ in a monomial
$z^aY^\lambda$;

\medskip\noindent
-- \algoname{y-exponent}, which, given a monomial $z^aY^\lambda$, returns the
tuple of exponents $(\lambda_0, \dots, \lambda_n)$, where $\lambda_i$ is the
exponent of $Y_i$;

\medskip\noindent
-- \algoname{not-integer}, which decides whether a number is an integer or not;

\medskip\noindent
-- \algoname{monomials}, which returns the list of monomials of a $q$-operator
passed as argument.

\bigskip

Since deciding if a $q$-algebraic equation is in solved form or not requires
to assess if the nonshifting $q$-factors are linear, we will make use of the
following procedure which decides if a $q$-operator has at least one
\ikey{non-shifting} term.

\ALGORITHM{\algoname{has-a-nonshifting-part}.
           Decide if a $q$-operator has a non-shifting part.}{
    \REQUIRE a $q$-opeartor $P$.
    \START{has-a-nonshifting-part}
    \FOR{$A$ \IN \algoname{monomials}$(P)$}
    \STATE $a\leftarrow \algoname{z-exponent}(A)$
    \STATE $\lambda\leftarrow\algoname{y-exponent}(A)$
    \IF{$(a=0)\wedge (\sum_{1\leq i\leq n} \lambda_i\not=0)$}
    \RETURN \TRUE
    \ENDIF
    \ENDFOR
    \RETURN \FALSE
}

We can then write a procedure to decide if an equation is in \ikey{solved form} or
not.

\ALGORITHM{\algoname{is-in-solved-form}.
           Decide whether an equation is in solved form or not.}{
    \REQUIRE a $q$-operator $P$.
    \START{is-in-solved-form}
    \IF{\algoname{has-a-non-shifting-part}($P$)}
    \FOR{$A$ \IN $\algoname{monomials}(P)$}
    \STATE $a \leftarrow \algoname{z-exponent}(A)$
    \IF{$(a < 0) \lor \algoname{not-integer}(a)$}
    \RETURN \FALSE
    \ENDIF
    \STATE $(\lambda_0,\dots,\lambda_n) \leftarrow \algoname{y-exponent}(A)$
    \IF{$(a = 0) \land \bigl(\sum_i\lambda_i > 1\bigr)$}
    \RETURN \FALSE
    \ENDIF
    \ENDFOR
    \RETURN \TRUE \COMMENT{Only reached when true}
    \ELSE   \COMMENT{$P$ has only shifting terms}
    \RETURN \FALSE
    \ENDIF
}

\section{Computation of the initial terms of the solutions}
All the previous procedures are relevant for the following one which
we improperly call the ``computation of
solutions'' of $q$-algebraic equations using the Newton-Puiseux
procedure. As a matter of fact, the most we can do is to find a number
of possible initial expansions of possible solutions, given a
$q$-operator $P$. In general we cannot always guarantee that what has been
found is the beginning of a solution.

\subsection{Calculating the exponents}
The initial terms of a solution are monomials in $z$. To determine their
exponents, we need to find the possible
co-slopes corresponding to vertices of the Newton-Puiseux polygon. These
are related to the co-slopes of the supporting lines of the Newton-Puiseux
polygon and the roots of the indicial polynomials of the vertices.
In order to decide
whether these roots are relevant or not, we need to assess what co-slopes
appear both before and after a specific vertex of the polygon. Our next
procedure, \algoname{next-coslopes}, could well be called `next exponent
of $z$';
it takes a $q$-operator $P$ and returns the list of the possible exponents
for the first terms of the solution. In some instances we may want to
restrict the output to exponents above some given threshold $\mu_{min}$; for
instance, when solving the $q$-Catalan equation, one may be interested only
in power series solutions, restricting the exponents to be at least $0$.
An additional flag, {\it flagEqual}, allows us to select the exponents which
are greater than or equal to $\mu_{min}$, or only those which are greater
than $\mu_{min}$.

This procedure assumes that we have

\medskip\noindent
-- a method \algoname{nonzero-roots} which, for a polynomial,
returns a list of all its nonzero complex roots;

\medskip\noindent
-- a method \algoname{is-real} which decides whether its parameter is
a real number or not, that is if it has no imaginary part;

\medskip\noindent
-- the ability to compare two real values.

\bigskip

Though these three items are not realistic in general,
current symbolic algebra systems are capable enough to deal with most
of the practical examples, and this will be illustrated in the next
chapter.

As indicated in the introduction to this chapter, the value
of $q$ is implicit everywhere in procedure
\algoname{recursive-solve}. One may wish to add a parameter to this
function in order to substitute this parameter for $q$ whenever the
latter appears.

The procedure \algoname{newton-puiseux-polygon} defined earlier returns
a pair of lists. We agree that the second list in that pair can be accessed as
\algoname{newton-puiseux-polygon}$(\,\,)[2]$.

The procedure \algoname{next-coslopes} uses a procedure
{\eightrm\uppercase{vertices-be\-low-lowest-point-in}}$(P,\hbox{\it listOfPoints})$ which
returns the vertices of the Newton-Puiseux polygon of $P$ which are
below the lowest point in the list of points {\it listOfPoints}.

In the procedure \algoname{next-coslopes}, we calculate some indicial
polynomials, from which we calculate the roots. It is possible for an
indicial polynomial to be $0$, as in equation \GSEq. In this case, the
polynomial has infinitely many roots, and the algorithm fails, printing
that infinitely many exponents are possible.

\ALGORITHM{\algoname{next-\ikey{coslopes}}. }{
    \REQUIRE{a $q$-operator $P$, a minimum coslope $\mu_{min}$ which is a
      lower bound for the co-slopes to
      be computed, a binary flag {\it flagEqual}, asserting if we allow
      for equality to $\mu_{min}$.}
    \START{next-coslopes}
    \STATE $\hbox{\it borderP}\leftarrow
           \algoname{leftmost-points}\bigl(\algoname{cloud}(P)\bigr)$
    \STATE $\hbox{\it coslopesNPP} \leftarrow \algoname{newton-puiseux-polygon}
            (\hbox{\it borderP})[2]$
    \STATE{{\it listOfMu}$\leftarrow [\,\,]$}\COMMENT{to become a list of coslopes}
    \FOR{$\mu$ \IN \hbox{\it coslopesNPP}}
    \IF{$(\mu>\mu_{min}) \lor \bigl(\hbox{\it flagEqual} \land
         (\mu =\mu_{min})\bigr)$}
    \STATE{\PUSH{\hbox{\it listOfMu}}{\mu}}
    \ENDIF
    \ENDFOR
    \STATE{$\hbox{\it points} \leftarrow
      \algoname{points-at-coslope}(P,\mu_{min})$}
    \STATE{\PUSH{\hbox{\it points}}{\algoname{vertices-below-lowest-point-in}
                                    (P,$ \hfill\break\hbox{\hskip 240pt} $\hbox{\it points})}}
    \FOR{$p$ \IN \hbox{\it points}}
    \STATE{$\Psi \leftarrow
      \algoname{indicial-polynomial}(P,p)$}
    \IF{$\Psi = 0$}
    \STATE\PRINT{``$\psi=0$: infinitely many exponents are possible''}
    \STATE{$\hbox{\it rootsOfPsi} \leftarrow \infty$}
    \RETURN \NONE
    \ELSE
    \STATE{$\hbox{\it rootsOfPsi} \leftarrow
      \algoname{nonzero-roots}(\Psi)$}
    \ENDIF
    \FOR{$r$ \IN \hbox{\it rootsOfPsi}} \COMMENT{does $r$ provide a valid coslope?}
    \STATE{$\lambda \leftarrow \log_{q}(r)$}
    \IF{$\algoname{is-real}(\lambda)$}
    \STATE{$\lambda_- \leftarrow \max\{\,\nu \in
            \hbox{\it coslopesNPP}\, :\, \nu
            \leq \lambda\,\}$} \hskip -15pt\COMMENT{coslope before $\lambda$}
    \STATE{$\lambda_+ \leftarrow
            \min\{\,\nu \in \hbox{\it coslopesNPP}\, :\, \nu
            \geq \lambda\,\}$} \hskip -10pt\COMMENT{coslope after $\lambda$}
    \IF{$\bigl( (\lambda_-<\lambda)\vee (\hbox{\it flagEqual}
         \wedge(\lambda_-=\lambda))\bigr)\wedge (\lambda_+>\lambda)$}
    \STATE{\PUSH{\hbox{\it listOfMu}}{\lambda}}
    \ENDIF
    \ENDIF
    \ENDFOR
    \ENDFOR
    \COMMENT{\hbox{\it listOfMu} lists all the possible next coslopes}
    \RETURN \hbox{\it listOfMu}
}

\subsection{A recursive method using a tree structure}
Recall that a $q$-algebraic equation may have several solutions which
start with the same few monomials. This leads us to think of the solutions as
a tree. For instance, if we have two solutions, say $f_1(z)=1+z+z^2+z^3\cdots$
and $f_2(z)=1+z+2z^2+3z^3+\cdots$, we can organize the first few terms of these
solutions as a tree as in figure \fixedref{12.3.1}.

\setbox1 = \hbox to 265pt{\hfill\vtop{\hsize=100pt
\kern -20pt
$$\halign{$#$&$\,#\,$&$#$\cr
                    &         & z^2\longrightarrow z^3\cr
                    &\nearrow & \cr
  1\longrightarrow z&         & \cr
                    &\searrow & \cr
                    &         & 2z^2\longrightarrow 3z^3\, \cr}
$$
\flabel{algorithmsFigA}
}}
\wd1=0pt\dp1=0pt\ht1=0pt

\parshape 1 0pt 170pt
This\box1 leads us to define a Newton-Puiseux object as
a recursive structure, that is, as a tree with a finite number of branches
at each node, each branch representing the next term in a solution and
carrying the equation as it is being translated and simplified along the
solution.

The procedure \algoname{recursive-solve} takes for argument a Newton-Puiseux
object, which is a recursive object composed of a
list $[\,\mu, Q, M, \calL\,]$ where:

\medskip\noindent
-- the number $\mu$ represents the last exponent which was
added to the ``solution'' under consideration. This is $-\infty$ at
the beginning;

\medskip\noindent
-- $Q$ is the equation at the present stage, that is, after
performing all the substitutions which have led to this point;

\medskip\noindent
-- $M$ is the last monomial added, which will be of the form $cz^{\mu}$;

\medskip\noindent
-- $\calL$ is a list of Newton-Puiseux objects, one for each possible
coslope and each possible root of the corresponding indicial and initial polynomials.

\bigskip

As an example, if up to this point two solutions have been found, one of the
form
$$
  3 + 2z^{1/2} + 7z^{2/3} - 3z^2 \, ,
$$
and one of the form
$$
  2 - 2z^{1/2} \, ,
$$
we would have the recursive list-type object

\medskip

\vbox{\obeylines\tt
[0, Q0, 3,
\quad [
\quad\quad [1/2, Q1, 2z\^{ }(2/3),
\quad\quad\quad [
\quad\quad\quad\quad [ 2/3, Q3, 7z\^{ }(2/3),
\quad\quad\quad\quad\quad[
\quad\quad\quad\quad\quad\quad [2, Q4, -3z\^{ }2, [[]]]]]],
\quad\quad [1/2, Q5, -2z\^{ }(1/2), []]]]] .
}

\medskip

Note that $\calL$ starts as an empty list. The value returned by
procedure \algoname{recursive-solve} is a Newton-Puiseux object.

One of the inputs is a non-negative integer $k$, the number of terms
of each solution still to be computed, which is then the depth of the tree.
This value is what guarantees that the recursion
is finite, as it is decreased with each call.

In order to call Procedure \algoname{recursive-solve}, one has to
build an initial Newton-Puiseux object. This can be easily done with
just the list $[\,\mu, P, 0, [\,\,]\,]$,
where $\mu$ is the minimum desired starting coslope, or exponent, so
that $\mu=-\infty$ gives all the possible trees.

\ALGORITHM{\algoname{recursive-solve}. Recursive call to find
    ``solutions.''}{
    \REQUIRE{a Newton-Puiseux object $\calN$, a number of terms
      to be computed $k$, a binary flag \hbox{\it flagEqual} to be passed
      to \algoname{next-coslope}}
    \START{recursive-solve}
    \STATE{$[\,\mu, Q, M, \calL\,] \leftarrow \calN$}
    \IF{$k=0$} \COMMENT{end of recursion}
    \RETURN{$\calN$}
    \ENDIF
    \STATE{$\hbox{\it listOfMu}\leftarrow\algoname{next-coslopes}
            (P,\mu,\hbox{\it flagEqual})$}
    \IF{$(\hbox{\it listOfMu}=[\,\,]) \wedge (Q(z,0)\not=0)$}
    \STATE{$M=\hbox{\bf not\_available}\,;\,
            \mu\leftarrow\hbox{\bf not\_available}$} \hfill{\it (this branch does}\break
    \hbox to 1in{~} \hfill{\it not lead to a solution)}\break\finetune{\vskip -24.75pt}
    \RETURN $[\, \mu,Q,M,\calL\,]$
    \ELSE
    \FOR{$\mu$ {\bf in} \hbox{\it listOfMu}}
    \STATE{$\Phi\leftarrow\algoname{initial-polynomial}(P,\mu)$}
    \STATE{$\hbox{\it rootsOfPhi}\leftarrow\algoname{nonzero-roots}(\Phi)$}
    \FOR{$r$ {\bf in} \hbox{\it rootsOfPhi}}
    \STATE{$Q \leftarrow \algoname{translation}(P,r,\mu)$}
    \STATE{$\calN^{\prime} \leftarrow [\,\mu, Q, rz^\mu, [\,\,\,]\,]$}
    \STATE{$\algoname{push-into}(\calL,
      \algoname{recursive-solve}\bigl(\calN^{\prime}, k-1, \FALSE)
                                \bigr)$}
    \ENDFOR
    \ENDFOR
    \ENDIF
}

The purpose of flag {\it flagEqual} in the procedure
\algoname{recursive-solve} is to allow for a call with a
starting coslope different from $-\infty$ in order to get the
solutions starting at least with that exponent.

We could also add a flag {\it flagPowerSeries} to discard
solutions with non-integer or negative exponents and keep only power series
solutions. This flag should be passed
recursively with the same value. If it is added, then any call to
procedure \algoname{recursive-solve} with initial $\mu=0$ and
$\hbox{\it flagPowerSeries}=\TRUE$, would only provide `solutions' which
have non-negative integer exponents, that is, which correspond to true
formal power series. We will use this technique to transform an equation into
solved form.

\subsection{The list of \ikey{initial expansions}}
From the Newton-Puiseux object returned by procedure
\algoname{recursive-solve}, one usually wants to extract the list of initial
terms of solutions which have been
computed. This requires traversing the tree structure and adding the
corresponding monomials at each point. This is what procedure
\algoname{initial-expansions} does.

\ALGORITHM{\algoname{initial-expansions.} Expand into sums the monomials
    from the tree structure
    returned by \algoname{recursive-solve}}{
    \REQUIRE a Newton Polygon object $\calN$ as, for example, returned by
    \algoname{recursive-solve}, a list $\calS$ which contains the different
    expansions and is empty in the first call, and a
    value $s(t)$ which represents the sum of the terms in the present
    branch ($0$ for the initial call).
    \START{initial-expansions}
    \STATE $[\,\nu, P, M, \calL\,] \leftarrow \calN$
    \COMMENT{Values of the node}
    \STATE $s(t) \leftarrow s(t) + M$
    \IF{$\calL = \emptyset$}
    \STATE \PUSH{\calS}{s(t)}
    \RETURN $\calS$
    \ENDIF
    \FOR{$\calN^{\prime}$ {\bf in} $\calL$}
    \STATE $\calS \leftarrow
    \algoname{initial-expansions}(\calN^{\prime}, \calS, s(t))$
    \ENDFOR
    \RETURN $\calS$
}

\section{Reduction to ikey{solved form}}
As we saw in Chapter \fixedref{4}, there is no guarantee that
an equation can be reduced to solved form in a finite number of steps.
However, one is usually interested in trying or
at least knowing if one can get to solved form in some finite number
of steps. However, in the end, the effort to reduce to solved form
amounts to solving the equation with non-negative integer exponents,
so that our procedure \algoname{to-solved-form} is almost a simple
wrapper around the procedure \algoname{recursive-solve}, It returns a pair
of lists: the first list contains the beginning of the solutions bringing
the equation to a solved form; the second list contains the corresponding
solved form derived from these initial terms.

One should be aware that for some equations one needs to ramify $z$ in order
to be able to bring them to solved form; in this case, the following procedure
cannot be applied directly. We will see such an example in the next chapter.

We use a procedure $\algoname{coeff}\bigl(Q(t), t, n\bigr)$ which returns
the coefficient of $t^n$ in the polynomial $Q(t)$, as well as
$\algoname{deg}\bigl(Q(t)\bigr)$ which returns the degree of the
polynomial $Q(t)$.

We assume that we implemented the procedure {\eightrm\uppercase{recursive-solve\--integer}}
which is the procedure \algoname{recursive-solve} but allowing only for power
series solutions, as described at the end of subsection \fixedref{3.2}.

\ALGORITHM{\algoname{to-solved-form.} Bring an equation to its solved form
    and returns all the paths leading to solved forms and the
    transformed equations.}{
    \REQUIRE a $q$-operator $P$ and a finite number $k$ indicating the
    maximum number of simplifications to make.
    \STATE \hskip-10pt$\star$ Start \algoname{to-solved-form}
    \STATE $\hbox{\it solutions}\leftarrow [\,\,\,]$;
           $\hbox{\it equations}\leftarrow [\,\,\,]$
    \STATE $\calT = [\,0, P, 0, [\,\,\,]\,]$ \COMMENT{first $0$
      for solutions with no poles}
    \STATE $\calN \leftarrow
    \algoname{recursive-solve-integer}(\calT, k)$
    \STATE $\calS \leftarrow \algoname{initial-expansions}(\calN)$
    \STATE $i \leftarrow 0$
    \FOR{$s$ {\bf in} $\calS$}
    \IF{$s$ is not marked {\bf not\_available}}
    \STATE $P' \leftarrow P$
    \FOR{$j=0$ \TO $\algoname{deg}\bigl(s(t)\bigr)$}
    \STATE $P' \leftarrow \algoname{simplify}\bigl(\algoname{translate}
            \bigl(P',\algoname{coeff}(s(t), t, j),1\bigr)\bigr)$
    \ENDFOR
    \IF{$\algoname{in-solved-form}(P^{\prime})$}
    \STATE{\PUSH{\hbox{\it solutions}}{s(t)}$\,;\,$
           \PUSH{\hbox{\it equations}}{P'}}
    \ENDIF
    \ENDIF
    \ENDFOR
    \RETURN $(\hbox{\it solution},\hbox{\it equations})$
}

\bigskip

\section{An easy optimization}

Procedure \algoname{initial-expansions} tries to find all possible initial
solutions up to a specific number of terms. If one fixes a positive number
$\nu$ and wishes to compute the
possible initial expansions, say $s(z)$, such that $Ps(z)=o(z^\nu)$,
an easy and
often useful optimization is posible. Let $\mu$ be any co-slope and
$A=(a;\alpha_1,\ldots,\alpha_\ell)$ be a $q$-factor. The point corresponding
to $A$ in the cloud is $(a,\ell)$. The line of co-slope $\mu$ passing through
$(\nu,0)$ is the set of points $(b,m)$ such that $b+\mu m=\nu$. If
$a+\mu\ell>\nu$, then the monomial $A$ has no influence in the terms of degree
less than $\nu$ of any solution, so that it can be subtracted from $P$
for the purpose of finding a solution up to $o(z^\nu)$.

\setbox1=\hbox to \hsize{\hskip 182pt\vtop to 120pt{
  \eightpoints
  \kern 85pt
  \special{psfile=Figures/algo_fig01.eps}
  \anotePT{20}{23}{\rotate{18.43}{$L_\mu(P)$}}
  \anotePT{100}{2}{$\nu$}
  \anotePT{0}{-20}{\flabel{algoFigA}}
  \vfill
  \vss
}}
\dp1=0pt\wd1=0pt\ht1=0pt

\kern-\baselineskip
\parshape 1 0pt 163pt
\box1 As an illustration, the points at the top of the dashed line on the
figure \algoFigA\ may be removed from $P$.

\parshape 7 0pt 160pt 0pt 160pt 0pt 160pt 0pt 160pt 0pt 160pt 0pt 160pt 0pt \hsize
This idea may be implemented in the procedure
{\eightrm RECURSIVE-SOLVE},
before the last call to {\bf push-into} which contains the recursive call to
\algoname{recurive-solve}. One might include before that line the following
code. It assumes that a procedure $\algoname{sum-terms}$ is passed a list and
sums all the terms in this list.

{ \FOR{$p$ \IN \algoname{cloud}$(Q)$}
  \IF{$\scx(Q)+\mu\scy(Q)>\nu$}
  \STATE{$Q\leftarrow Q-\algoname{sum-terms}\bigl(\algoname{hash}(Q,p)\bigr)$}
  \ENDIF
  \ENDFOR
}

\bigskip

With this optimization, the procedure \algoname{recursive-solve} needs a new
input parameter, namely the maximum order $\nu$, which should then be passed
in the recursive calls.