text:
\begin{document}

\title{Covering Rational Ruled Surfaces}

\author{J. Rafael Sendra, Carlos Villarino\\
       {Dept. of Physics and Mathematics, U. of Alcal\'a}\\
       {Ap. Correos 20}\\
       {E-28871 Alcal\'a de Henares (Madrid, Spain)}\\
       {$\{$Rafael.Sendra,Carlos.Villarino$\}$@uah.es}
\\ \\
       David Sevilla\\
       {U. Center of M\'erida, U. of Extremadura}\\
       {Av. Santa Teresa de Jornet 38}\\
       {E-06800 M\'erida (Badajoz, Spain)}\\
       {sevillad@unex.es}}

\date{}

\maketitle

\begin{abstract}
We present an algorithm that covers any given rational ruled surface with two rational parametrizations. In addition, we present an algorithm that transforms any rational surface parametrization into a new rational surface parametrization without affine base points and such that the degree of the corresponding maps is preserved.
\end{abstract}

2010 Mathematics Subject Classification: 14Q10, 68W30.

Keywords: parametrization of ruled surfaces, normality, base points

\section{Introduction}
One of the most important features of rational varieties, at least in practice, is the possibility to choose between parametric or implicit representations depending on the nature of the problem one is dealing with; examples are the computation of intersections, plotting figures, line and surface integrals, etc. However, when using the parametric representations additional difficulties may appear, and the feasibility of the strategy is affected. In particular, if the parametrization is not surjective, some solving strategies may fail.

In \cite{Ricam}, Example 1 illustrates a situation where the computation of the intersection of two surfaces fails when a non surjective parametrization is used. Let us see another motivating example.

\begin{example}
The Hausdorff distance appears naturally in applications in computer aided design, pattern matching and pattern recognition (see e.g. \cite{Bai}, \cite{Chen}, \cite{Kim}), when measuring the resemblance between two geometric objects. The computation or estimation of the Hausdorff distance implies, in particular, measuring the distance of a point to a set. Let us assume that we want to measure the distance of the point $A=(4/5, 6/5, 1)$ to the surface $S$ defined by $f(x,y,z)=xy-2yz+z^2$. Applying Lagrange multipliers one gets that the distance of $A$ to $S$ is $\sqrt{2}/5=0.283\ldots$ and it is reachable at $B=(1,1,1)\in S$. Nevertheless, in general, approaching this problem using implicit equations turns to be computationally intractable. Instead, one can try to use a parametrization of the surface so that the problem reduces to a  optimization problem without constrains. In our case, $S$ is rational, indeed it is rational ruled surface, and can be parametrized as
 \[ \cP(s,t)=\left((s^2-1)t, s^2t, t(s^2+s)\right). \]
However, if we optimize the function $\|A-\cP(s,t)\|^2$ we find that the minimum is obtained at $(0.889\ldots, -0.042\ldots, 0.155\ldots)$ and the distance is then estimated as $1.504\ldots$. The problem is that $B\in S\smallsetminus \Image(\cP)$, so it cannot be found with the parametrization. Nevertheless, $\cP$ satisfies the hypothesis in Theorem \ref{theorem-recta-critica}, and therefore we can determine that the $S\smallsetminus \Image(\cP)$ is included in the line $(t,t,t)$. Thus, we now optimize the  $\|A-(t,t,t)\|^2$ to get $B$ as solution.
\end{example}

In the case of curves, non-surjectivity is not so important since every rational proper parametrization of a curve may miss at most one point that can be easily computed (see e.g. \cite{AndradasRecio}, \cite{Sendra2002a}). The situation changes when working with rational parametrizations of algebraic surfaces: the missing subset can be of dimension 1.

Some authors have addressed the problem of finding surjective parametrizations of rational surfaces; see \cite{Bajaj}, \cite{Gao} for the case of quadrics or \cite{Ricam} for certain particular types of rational surfaces. Alternatively, one can compute finitely many rational parametrizations such that the union of their images covers the whole surface. This was done for the real general case, in \cite{Bajaj}, by computing a cover with $2^n$ parametrizations, where $n$ is the dimension of the rational variety; i.e. in the surface case, with four pieces. In \cite{issac} we show that, if a surface admits a rational parametrization without projective base points, then it can be covered with at most three pieces. Continuing with this research, in this paper we analyze the problem of covering   rational ruled surfaces. The next example shows that for the same surface, changing the parametrization, can make the missing subset bigger.

\begin{example}
We consider the ruled surface $S$ given by $x^2y-2xy^2+2y^3-3y^2z+3yz^2-z^3=0$. $S$ can be parametrized in {\it ruled form} as
\[ \cP(s,t)= \left(\frac{(s^3-1)t}{s(s+1)}, \frac{s^2t}{s+1}, \frac{(s^2+1)t}{s+1}\right) \]
Applying the algorithm in \cite{Ricam} for computing the critical sets, we obtain that $\cP$ covers all the surface but the three lines $\{x=2y=z\}, \{x=y=z\}, \{y=z=0\}$. However, the reparametrization
\[ \cP(s, ts(s+1))= \left( (s^2-1)t, ts^2, (s^2+s)t \right), \]
that is also in {\it ruled form},  only misses the line $\{x=y=z\}$ (see Theorem \ref{theorem-recta-critica}).
\end{example}

In this paper we prove that a rational ruled surface can always be covered with two rational surface parametrizations in {\it ruled form}. More precisely, we prove that there always exists a rational parametrization that, at most, misses a line on the surface; then the second parametrization covers that line. In order to compute the first parametrization we need parametrizations without affine base points. Later we consider this problem in general, and we present an algorithm that transforms any rational surface parametrization into a new parametrization without affine base points.

\section{Covering Ruled Surfaces: Main Results}\label{sec:covering-theory}

In the sequel, we show that every rational ruled surface can be covered by means of, at most, two rational parametrizations.

\begin{definition}\label{def-ruled-param}
 A \emph{standardized ruled surface parametrization} of a ruled suface $S$ is a triple of rational functions that determines a dominant rational map
 \[\begin{array}{rccc}
  \cP: & k^2 & \dashedrightarrow & S \\ [1em]
   & (s,t) & \mapsto & \left(\displaystyle \frac{r_1(s)+t\cdot p_1(s)}{q(s)}, \frac{r_2(s)+t\cdot p_2(s)}{q(s)}, \frac{r_3(s)+t\cdot p_3(s)}{q(s)} \right)
 \end{array}\]
 such that those $p_i$ that are nonzero have the same degree and do not have any common root (note that not all three of them are zero).

\end{definition}

\begin{remark}\label{remark-pi}
In a standardized ruled surface parametrization, if two of the polynomials $p_i$ are zero, then the third has to be a nonzero constant. In addition, we observe that, in that case, say $p_1=p_2=0$, then $\cP(s,(-r_3+qt)/p_3)=(r_1/q,r_2/q,t)$. So, $S$ is a cylinder over the plane curve $(r_1/q,r_2/q,0)$ and hence, applying the results in \cite{Sendra2002a}, $S$ can be parametrized surjectively.
\end{remark}

\begin{lemma}\label{lemma-stardard}
 Every rational ruled surface admits a standardized ruled surface parametrization.
\end{lemma}

\begin{proof}
By \cite{Sonia}, every rational ruled surface admits a rational parametrization of the form
\[ \cP(s,t)=\left(\frac{\alpha_1(s) +t \beta_1(s)}{\gamma(s)},\frac{\alpha_2(s) +t \beta_2(s)}{\gamma(s)}, \frac{\alpha_3(s) +t \beta_3(s)}{\gamma(s)}\right). \]
If two $\beta_i$ are zero, say $\beta_1=\beta_2=0$, then $\cP(s,t/\beta_3(t))$ is standardized. Let us suppose that at least two $\beta_i$ are nonzero. Then, we can assume that  those components of $\cP(s,t)$ depending on $t$ also do depend on $s$; if this is not the case a suitable change of the form $(s,as+bt)$ provides a parametrization with this property. Furthermore, applying a transformation of the form $(\frac{as+b}{cs+d},t)$,  we can assume that all nonzero $\beta_i$ have the same degree. It only remains to ensure that the gcd of the polynomial coefficients of $t$ are coprime. But this can be achieved by performing the transformation $(s, t/\Delta(s))$, where $\Delta$ is the gcd of the nonzero $\beta_i$.
\end{proof}

Associated to the standardized ruled surface parametrization $\cP(s,t)$, we consider the polynomials
\begin{equation}\label{eq-H}
 \begin{array}{l} H_1=r_1(s)+t\cdot p_1(s)-x\cdot q(s), \\ H_2=r_2(s)+t\cdot p_2(s)-y\cdot q(s), \\
H_3=r_3(s)+t\cdot p_3(s)-z\cdot q(s),
\end{array}
\end{equation}
as well as the polynomials $A_{ij} = p_iH_j-p_jH_i\in k[x,y,z,s]$ for $i\neq j$. We express $A_{ij}$ as
\begin{equation}\label{eq-A}
\begin{array}{r}
A_{12}= qp_2x -qp_1y -\alpha_{12}, \\ A_{13}= qp_3x -qp_1z -\alpha_{13}, \\
A_{23}= qp_3y -qp_2z -\alpha_{23}, \\
\alpha_{ij}=-p_{i}r_j+p_jr_i.
\end{array}
\end{equation}
 We have the following lemma.

\begin{lemma}\label{lemma-crit}
Let $\cP$ be a standardized ruled surface parametrization without affine base points of a surface $S$. Then $S\smallsetminus\Image(\cP)$ is contained in the variety $\cal W$ defined by $\{{\rm LC}_s(A_{ij})\}_{i\neq j}$, where ${\rm LC}_s$ denotes the leading coefficient w.r.t. $s$.
\end{lemma}
\begin{proof}
 In the ring $k[x,y,z,s,t,w]$ we consider the ideal
 \[
  I = (H_1(s,t,x),\ H_2(s,t,y),\ H_3(s,t,z),\ w\cdot q(s)-1).
 \]

Then $\Image(\cP)=\pi(V(I))$ where $\pi(x,y,z,s,t,w)=(x,y,z)$. We will use the extension theorem (see e.g. Chp.3, Th 3, p. 115 in \cite{CoxLittleOshea2007a}) to determine which points $(x,y,z)\in S$ can be lifted to $V(I)$. To this end we define
 \[
  I_1 = I \cap k[x,y,z,s,t], \quad I_2 = I \cap k[x,y,z,s], \quad I_3 = I \cap k[x,y,z].
 \]
 \begin{itemize}
  \item Extension from $I_1$ to $I$: a point $(x_0,y_0,z_0,s_0,t_0)$ has an extension provided $q(s_0)\neq0$. But if $q(s_0)=0$ we see from the equations that $r_i(s_0)+t_0p_i(s_0)=0$ for all $i$, and $(s_0,t_0)$ would be a base point, contrary to the hypotheses.
  \item Extension from $I_2$ to $I_1$: in order to extend a point $(x_0,y_0,z_0,s_0)$ to the coordinate $t$ it suffices that $p_1,p_2,p_3$ do not simultaneously vanish at $s_0$. This always holds since by definition they have no common root. Note that if two of the $p_i$ are zero, the other is a nonzero constant, and the extension is possible.
  \item Extension from $I_3$ to $I_2$:

   a point $(x,y,z)$ can be extended to the coordinate $s$ if for at least one of the polynomials $A_{ij}$ the leading coefficient in $s$ does not vanish at the point.

 \end{itemize}
\end{proof}

\begin{lemma}\label{lemma-recta}
The variety $\cal W$ introduced in Lemma \ref{lemma-crit} is either empty or a line. Furthermore, $\mathcal{W}=\emptyset$ if and only if $\deg(\alpha_{ij})>\deg(p_k q)$, for some different $i,j\in \{1,2,3\}$ and nonzero $p_k$.
\end{lemma}
\begin{proof}
Let us assume $p_1\neq 0$. If $\deg(\alpha_{ij})>\deg(p_1 q)$, for some different $i,j\in \{1,2,3\}$, then ${\rm LC}_s(A_{ij})$ is a nonzero constant and $\mathcal{W}=\emptyset$.

If $\deg(\alpha_{ij})\leq \deg(p_1 q)$ for all $i\neq j$, we distinguish two cases. If $p_2=p_3=0$ then $A_{12}=-p_1qy-\alpha_{12}, A_{13}=-p_1qz-\alpha_{13}, A_{23}=0$. Then, $\cal W$ is defined by two linear polynomials, one depending on $y$ and the other on $z$. So $\cal W$ is a line. In the second case, let us assume that at least two $p_i$ are nonzero. Since $p_3 A_{12}-p_2 A_{13}+p_1 A_{23}=0$, then
\[ {\rm LC}_s(p_1 A_{23})={\rm LC}_s(p_1){\rm LC}_s(A_{23})={\rm LC}_s(-p_3A_{12}+p_2 A_{13}). \]
Let us see that
\[ {\rm LC}_s(p_1){\rm LC}_s(A_{23})=-{\rm LC}_s(p_3){\rm LC}_s(A_{12})+{\rm LC}_s(p_2){\rm LC}_s(A_{13}). \]
If either $p_2$ or $p_3$ is zero, the result is clear. So, let none of them be zero. Then, $\deg_s(p_3A_{12})=\deg_s(p_2A_{13})$. Since the leading coefficient of $p_3A_{12}$ does depend on $\{x,y\}$ and the leading coefficient of $p_2A_{13}$ does depend on $\{y,z\}$,
$\deg_s(-p_3A_{12}+p_2 A_{13})=\deg_s(p_3A_{12})=\deg_{s}(p_2A_{13})$, from where the above equality on the leading coefficients follows.
In this situation we get that $\cal W$ is defined by ${\rm LC}_s(A_{12}),{\rm LC}_s(A_{13})$. Now, the result follows by taking into account that the rank of the linear system $\{{\rm LC}_s(A_{12})=0={\rm LC}_s(A_{13})\}$ is 2.
\end{proof}

Using the previous results one gets the following theorem.

\begin{theorem}\label{theorem-recta-critica}
 Let $\cP$ be a standardized ruled surface parametrization without affine base points of a surface $S$. Then $S\smallsetminus\Image(\cP)$ is contained in a line. Furthermore,
\begin{enumerate}
\item if there exists $i,j\in \{1,2,3\}$ such that $i\neq j$ and $\deg(\alpha_{ij})>\deg(p_k q)$ for nonzero $p_k$, then $\cP(s,t)$ is normal.
\item if for all $i,j\in \{1,2,3\}$, with $i\neq j$,  $\deg(\alpha_{ij})\leq \deg(p_k q)$ for nonzero $p_k$, then $S\smallsetminus\Image(\cP)$ is included in the line $V({\rm LC}_s(A_{12}),{\rm LC}_s(A_{13}),{\rm LC}_s(A_{23}))$.
\end{enumerate}
\end{theorem}

In Example \ref{ejemplo-grado-3}, one can see that the parametrization covers all the line $\cal W$ but a point, while in Example \ref{ejemplo-grado-5}, the parametrization only covers two points on the line $\cal W$.

In the previous theorem we have imposed the condition of not having affine base points. Let us see that this is always achievable.

\begin{lemma}\label{lemma-reglada-sin-puntos-base}
Every standardized ruled surface parametrization can be re\-pa\-ra\-me\-tri\-zed into another one without affine base points and where the degree of the induced map is preserved.

\end{lemma}

\begin{proof}
Let us assume first that all the $p_i$ are nonzero. Let $f(s)$ be a polynomial such that $f(s_1)=t_1$ for some base point $(s_1,t_1)$. With the change $(s,1/t+f(s))$ the resulting parametrization is
 \[ \left( \frac{Q_i(s)\cdot t+p_i(s)}{t\cdot q(s)} \right)_{i=1,2,3} \qquad \mbox{where $Q_i(s)=r_i(s)+f(s)p_i(s)$}. \]
 Since $s_1$ is a common root of $q$ and the $Q_i$, if we define $\widetilde{Q}=\gcd(Q_1,Q_2,Q_3,q)$, we have $\deg(\widetilde{Q})\geq1$. Now with the change $(s,1/(\widetilde{Q}t))$ we obtain the new parametrization
 \[ \left( \frac{Q_i/\widetilde{Q} + p_i\cdot t}{q/\widetilde{Q}} \right)_{i=1,2,3}. \]
 Note that this is standardized as well, but the degree of the denominator is strictly smaller than the original. Therefore repeating this procedure finitely many times we obtain a standardized parametrization without affine base points (since that is the case when the denominator is a constant). Finally, note that all transformations considered are birational, and hence the degrees of the maps are preserved.

 If any $p_i=0$, the corresponding component of the parametrization does not change after the first reparametrization, resulting in $Q_i=r_i$. The second reparametrization does not change the component as well, but the common factor $\widetilde{Q}$ of $r_i$ and $q$ can be directly simplified in that fraction.
\end{proof}

\begin{remark}\label{remark-pto-bases}
 In the previous result we can have some control on the removal of base points that occurs effectively in each iteration.
 Namely, suppose that the zeros of $q$ are $s_1,\ldots,s_l$ where $s_1,\ldots,s_k$, $k\leq l$, are the first coordinates of the base points of $\cP$. Note that for each of $s_1,\ldots,s_k$ there is exactly one base point $(s_i,t_i)$.

 Let $f(s)$ be an interpolating polynomial of $$(s_1,t_1),\ldots,(s_k,t_k), (s_{k+1},0),\ldots,(s_l,0).$$ As before, we define $Q_i(s)=r_i(s)+f(s)p_i(s)$ and $\widetilde{Q}=\gcd(Q_1,Q_2,Q_3,q)$, and make the change $(s,\widetilde{Q}t+f(s))$ to obtain
 \[ \cP^{(1)} = \left( \frac{r_i^{(1)} + p_i\cdot t}{q^{(1)}} \right)_{i=1,2,3} \qquad \mbox{where $r_i^{(1)}=Q_i/\widetilde{Q}$, \ $q^{(1)}=q/\widetilde{Q}$}. \]
 Note that the roots of $\widetilde{Q}$ are precisely $s_1,\ldots,s_k$.
 We will show that $\cP^{(1)}$ has at most as many base points as the number of multiple roots of $q$ among $s_1,\ldots,s_k$. To this end let $(\alpha,\beta)$ be a base point of $\cP^{(1)}$. Since $\alpha$ is a root of $q^{(1)}$, it must be a multiple root of $q$, say $\alpha=s_i$. If $i>k$ then $Q_i(\alpha)=r_i(\alpha)$. Now, by definition of $\beta$, we have $\beta=-r_i^{(1)}(\alpha)/p_i(\alpha)$ for some $i$. But then the point $(\alpha,\beta\widetilde{Q}(\alpha))$ is a base point of $\cP$, contradiction.
\end{remark}

\begin{corollary}\label{cor+2+1}
Every rational ruled surface can be parametrized in an standardized way that misses at most one line.
\end{corollary}

\begin{theorem}\label{theorem+2+2}
Every rational ruled surface can be covered with at most two surface parametrizations.
\end{theorem}
\begin{proof} By Lemma \ref{lemma-reglada-sin-puntos-base} we can assume that we are given an standardized  pa\-ra\-me\-tri\-za\-tion $\cP$ without affine base points. We use for $\cP$ the notation in Definition \ref{def-ruled-param} and in the previous results. By Theorem \ref{theorem-recta-critica}, we can also assume that $\max\{\deg(\alpha_{12}),\deg(\alpha_{13}),\deg(\alpha_{23})\}\leq \deg(p_kq)$ for nonzero $p_k$.

First we assume that all $p_i(s)$ are nonzero. Consider the reparametrizations
\[ \mathcal{Q}(s,t)=\cP\left(s,\frac{qt-r_3}{p_3}\right)=\left(\frac{q p_1t+\alpha_{13}}{p_3q},\frac{qp_2t+\alpha_{23}}{p_3q},t \right) \]
and
\[ \mathcal{H}(s,t)=\mathcal{Q}\left(\frac{1}{s},t\right).\]
Because of our above degree assumptions, we know that the degrees in $s$ of the numerator and denominator of each (first and second) component of $\mathcal{Q}$ are equal. Therefore, $s$ is not a factor of the denominators in $\mathcal{H}(s,t)$. So, $\mathcal{H}(0,t)$ is well defined and, indeed,
\[ \mathcal{H}(0,t)=\left(\frac{{\rm LC}_s(q p_1t+\alpha_{13})}{{\rm LC}_s(p_3q)},\frac{{\rm LC}_s(qp_2t+\alpha_{23})}{{\rm LC}_s(p_3q)},t \right) \]
that parametrizes the line $\cal W$.

A similar argument with obvious modifications works in the case when some $p_i$ are zero.
\end{proof}

\section{Covering Ruled Surfaces: Algorithm and Examples}\label{sec:covering-algorithm}

In order to derive an algorithm from the previous results, we need to algorithmically show how to remove the affine base points of an standardized ruled parametrization. This, essentially, requires to compute interpolation polynomials (see proof of Lemma \ref{lemma-reglada-sin-puntos-base} and Remark \ref{remark-pto-bases}). In the following lemma we see how to actually compute the interpolation polynomial  without explicitly determining the coordinates of the base points; i.e. without approximating roots.

\begin{lemma}\label{lemma-interpolation}
Let $\cP(s,t)$ be an standardized ruled parametrization as in Def. \ref{def-ruled-param} with affine base points. Let $I$ be the ideal generated by $\{p_1t+r_1,p_2t+r_2,p_3t+r_3,q\}$ in $k[s,t]$. Then,  there exists a polynomial of the form $t-f(s)$ in $\sqrt{I}$ where $f(s)$  interpolates the affine base points of $\cP(s,t)$.
\end{lemma}
\begin{proof} As observed in Remark \ref{remark-pto-bases}, all affine base points of $\cP$ have different $s$-coordinate. Thus, there exists an interpolating polynomial $f(s)$ passing through all base points. So,
 $t-f(s)$ vanishes on all the points in the variety of $I$. So, $t-f(s)\in \sqrt{I}$.
\end{proof}

Now, we are ready to outline our algorithm.

\begin{algorithm}\label{alg-1}
Given a rational parametrization $\cP(s,t)$ of a ruled surface $\cal S$, the algorithm computes a covering of $\cal S$.
\begin{enumerate}
\item If $\cP$ is not of the form $((r_i(s)+p_i(s)t)/q(s))_{i=1,2,3}$ apply the algorithm in \cite{Sonia} and replace $\cP$.
\item If $\cP$ is not in standardized form (see Def. \ref{def-ruled-param}) do the following
\begin{enumerate}
\item If some of the numerators of $\cP$ does not depend on $s$, replace $\cP$ by $\cP(s, as +
bt)$ with $a,b\in k$.
\item If the polynomials $p_1,p_2,p_3$ do not have the same degree, replace $\cP$ by $\cP((as+b)/(cs+d), t)$ where $a,b,c,d\in k$ and $ad-bc\neq 0$.
\item Replace $\cP$ by reparametrization $\cP(s, t/\Delta(s))$ where $\Delta$ is the gcd of the nonzero $p_i$.
\end{enumerate}
\item Calculate $\sqrt{I}$,  where $I$ is the ideal generated by $\{p_1t+r_1,p_2t+r_2,p_3t+r_3,q\}$ in $k[s,t]$. This can be done with a relatively inexpensive Gr\"obner basis computation (see e.g.  Ex 2.3.23 and 24 in \cite{Adams} and \cite{Seidenberg}).
 \item Calculate a Gr\"obner basis of $\sqrt{I}$ with respect to the lexicographical ordering $t>s$.
 \begin{enumerate}
  \item If the basis does not contain a polynomial of the form $t-f(s)$, by elementary properties of Gr\"obner basis it follows that there is no polynomial of that form in $\sqrt{I}$, so by  Lemma \ref{lemma-interpolation} we know that $\cP$ does not have affine base points.
  \item In the other case, let $t-f(s)$ belong to the basis, do
  \begin{enumerate}
  \item Replace $\cP$ by  $\cP(s, 1/t + f(s))$.
  \item Let $\widetilde{Q}$ be the gcd of the coefficients of $t$ of the numerators of $\cP$ and $q$, then replace $\cP$ by
  $\cP(s, 1/(\widetilde{Q}t))$.
  \item Repeat Steps 3 and 4 while $\sqrt{I}$ has an element of the form $s-f(t)$.
  \end{enumerate}
 \end{enumerate}
\item Compute the polynomials $\alpha_{ij}$  (see (\ref{eq-A})).
 \item If there exist $i,j\in \{1,2,3\}$ such that $i\neq j$ and $\deg(\alpha_{ij}) > \deg(p_kq)$ for nonzero $p_k$, RETURN $\cP(s,t)$.
 \item Assume that $p_k\neq 0$, compute $$\mathcal{H}(s,t) = \cP\left(\frac{1}{s},\frac{q(1/s)t-r_k(1/s)}{p_k(1/s)}\right)$$
and RETURN $[\cP(s,t),\mathcal{H}(s,t)]$.
\end{enumerate}
\end{algorithm}

\begin{remark}
 Remark \ref{remark-pto-bases} shows that, in general, the number of iterations of the loop in Step 4 is small. Indeed it is bounded by the maximum multiplicity of the roots of the denominator $q(t)$ of $\cP$.

In addition we observe that all parametrizations in the output of the algorithm are of ruled form, that is, of the form $(\alpha_1(s),\alpha_2(s),\alpha_3(s))+$\linebreak $t(\beta_1(s),\beta_2(s),\beta_3(s))$.
\end{remark}

Let us illustrate Algorithm \ref{alg-1} by some examples.

\begin{example}\label{ejemplo-grado-3}
We consider the parametrization
\[  \cP(s,t) =\left( \frac{r_1(s)+t p_1(s)}{q(s)}, \frac{r_2(s)+t p_2(s)}{q(s)}, \frac{r_3(s)+t p_3(s)}{q(s)} \right) = \]
\[
\left(  {\frac {t \left( {s}^{2}+s+1 \right) +s}{s \left( s-1 \right) }},{
\frac {t \left( {s}^{2}+2\,s \right) +s}{s \left( s-1 \right) }},{
\frac {t \left( {s}^{2}+1 \right) +s}{s \left( s-1 \right) }}\right).
\]
It parametrizes the degree 3 ruled surface defined by

\noindent $F(x,y,z)=5\,{x}^{3}-9\,{x}^{2}y-8\,{x}^{2}z+5\,x{y}^{2}+11\,xyz+3\,x{z}^{2}-{y}
^{3}-3\,{y}^{2}z-3\,y{z}^{2}-4\,{x}^{2}+4\,xy+4\,xz-{y}^{2}-2\,yz-{z}^
{2}.$

We observe that $\cP(s,t)$ is in standardized form. So, we go to Step 3 in Algorithm \ref{alg-1}. $I$ is the ideal generated by
 $\{p_1t+r_1,p_2t+r_2,p_3t+r_3,q\}$ in $k[s,t]$. We get $\sqrt{I}=I$, and a Gr\"obner basis w.r.t. the lexicographic ordering $t>s$ (Step 4) is
 $\{s,t\}$. So, in Step 4 (b) we get that $f(s)=0$; note that the origin is the only affine base point. In Step 4 (b, i), we replace $\cP(s,t)$ by
 $\cP(s,1/t+0)$, namely
 \[ \cP(s,t)=\left({\frac {{s}^{2}+st+s+1}{ts \left( s-1 \right) }},{\frac {s(s+2+t)}{ts
 \left( s-1 \right) }},{\frac {{s}^{2}+st+1}{ts \left( s-1 \right) }}\right). \]
 In Step 4 (b, ii), $\widetilde{Q}=\gcd(s,s,s,s(s-1))=s$. So, we replace $\cP$ by $\cP(s, 1/(st))$, namely
 \begin{equation}\label{eq-ex-1}
  \cP(s,t)=\left( {\frac {{s}^{2}t+st+t+1}{s-1}},{\frac {{s}^{2}t+2\,st+1}{s-1}},{
\frac {{s}^{2}t+t+1}{s-1}}\right).
\end{equation}
Now, the lexicographic order Gr\"obner basis of $\sqrt{I}$ is $\{1\}$, hence $\cP$ does not have base points. In Step 5 we get
\[ \alpha_{12}=s-1,\alpha_{13}=-s,\alpha_{23}=2\,s-1. \]
In Step 6 the boolean conditions do not hold. In Step 7 we calculate the parametrization
\[ \mathcal{H}=\cP\left(\frac{1}{s},\frac{q(1/s)t-r_3(1/s)}{p_3(1/s)}\right)= \]
\[ \left({\frac {{s}^{3}t-2\,{s}^{3}-{s}^{2}-2\,s-t}{ \left( {s}^{2}+1
 \right)  \left( s-1 \right) }},-{\frac {{s}^{3}-2\,{s}^{2}t+2\,{s}^{2
}+st+2\,s+t}{ \left( {s}^{2}+1 \right)  \left( s-1 \right) }},{\frac {
st-2\,s-t}{s-1}}\right).\]
The algorithm returns the covering $[\cP(s,t),\mathcal{H}(s,t)]$ where $\cP$ is the parametrization in (\ref{eq-ex-1}).
\begin{figure}[ht]
 \centering
 \includegraphics[scale=0.7]{fig-1}
 \caption{The surface in Example \ref{ejemplo-grado-3} and line $(t,t,t)$.}
 \label{fig: ex-1}
\end{figure}
Continuing with the example, since $\cP$ in (\ref{eq-ex-1}) is an standardized ruled parametrization without affine base points, by Theorem \ref{theorem-recta-critica}, the possible missing points of $\cP$ are included in the line defined by $\{x-y=0, x-z=0, y-z=0\}$, that is, the line $(t,t,t)$; see Fig. \ref{fig: ex-1}. In fact, $\cP$ covers all the line except the origin, by taking $\cP(s,0)$. Nevertheless,  ${\cal H}$ covers the whole line by taking ${\cal H}(0,t)$.
\end{example}

\begin{example}\label{ejemplo-grado-5}
We consider the parametrization
\[  \cP(s,t) =\left( \frac{r_1(s)+t p_1(s)}{q(s)}, \frac{r_2(s)+t p_2(s)}{q(s)}, \frac{r_3(s)+t p_3(s)}{q(s)} \right) = \]
\[
\left(  {\frac {t{s}^{3}+2\,{s}^{2}+1}{{s}^{2}-1}},{\frac {t \left( {s}^{3}+2
 \right) +s+1}{{s}^{2}-1}},{\frac {t \left( {s}^{3}+s+1 \right) +1}{{s
}^{2}-1}}\right).
\]
It parametrizes the degree 5 ruled surface defined by

\noindent $ F(x,y,z)=9\,{x}^{5}-45\,{x}^{4}y-24\,{x}^{4}z+77\,{x}^{3}{y}^{2}+80\,{x}^{3}yz-
15\,{x}^{3}{z}^{2}-83\,{x}^{2}{y}^{3}+34\,{x}^{2}{y}^{2}z-147\,{x}^{2}
y{z}^{2}+78\,{x}^{2}{z}^{3}+66\,x{y}^{4}-60\,x{y}^{3}z-189\,x{y}^{2}{z
}^{2}+460\,xy{z}^{3}-236\,x{z}^{4}+16\,{y}^{5}-86\,{y}^{4}z+111\,{y}^{
3}{z}^{2}+118\,{y}^{2}{z}^{3}-332\,y{z}^{4}+168\,{z}^{5}-104\,{x}^{4}+
319\,{x}^{3}y+108\,{x}^{3}z-207\,{x}^{2}{y}^{2}-621\,{x}^{2}yz+452\,{x
}^{2}{z}^{2}+147\,x{y}^{3}-382\,x{y}^{2}z+1034\,xy{z}^{2}-848\,x{z}^{3
}+297\,{y}^{4}-1549\,{y}^{3}z+3390\,{y}^{2}{z}^{2}-3380\,y{z}^{3}+1344
\,{z}^{4}+304\,{x}^{3}-741\,{x}^{2}y+389\,{x}^{2}z-267\,x{y}^{2}+1761
\,xyz-2314\,x{z}^{2}-4\,{y}^{3}+922\,{y}^{2}z-1930\,{z}^{2}y+1816\,{z}
^{3}-70\,{x}^{2}+597\,yx-2060\,zx+748\,{y}^{2}-1703\,zy+2940\,{z}^{2}-
761\,x-62\,y+2085\,z+746.$

We observe that $\cP(s,t)$ is in standardized form, so we go to Step 3 in Algorithm \ref{alg-1}. $I$ is the ideal generated by
 $\{p_1t+r_1,p_2t+r_2,p_3t+r_3,q\}$ in $k[s,t]$. We get $\sqrt{I}=I$, and a Gr\"obner basis w.r.t. the lexicographic ordering $t>s$ (Step 4) is
 $\{1\}$. Thus $\cP(s,t)$ does not have affine base points and we go to Step 5 to get
\[ \alpha_{12}=2{s}^{5}-{s}^{4}+4{s}^{2}+2 ,
\alpha_{13}=2{s}^{5}+2{s}^{3}+2{s}^{2}+s+1,
\alpha_{23}=-{s}^{4}-{s}^{2}-2s+1. \]
In Step 6 the boolean conditions do not hold. In Step 7 we get the parametrization
\[ \mathcal{H}=\cP\left(\frac{1}{s},\frac{q(1/s)t-r_3(1/s)}{p_3(1/s)}\right)= \]
\[ \left(-{\frac {{s}^{5}+{s}^{4}+2\,{s}^{3}-t{s}^{2}+4\,{s}^{2}+t+2}{ \left(
{s}^{3}+{s}^{2}+1 \right)  \left( {s}^{2}-1 \right) }},\right.\]\[ \left. {\frac {2\,{s}^
{5}t-3\,{s}^{5}-2\,{s}^{4}-2\,t{s}^{3}-{s}^{3}+t{s}^{2}-2\,{s}^{2}-s-t
}{ \left( {s}^{3}+{s}^{2}+1 \right)  \left( {s}^{2}-1 \right) }},{
\frac {t{s}^{2}-2\,{s}^{2}-t}{{s}^{2}-1}}\right).\]
The algorithm returns the covering $[\cP(s,t),\mathcal{H}(s,t)]$.
\begin{figure}[ht]
 \centering
 \includegraphics[scale=0.5]{fig-2}
 \caption{The surface in Example \ref{ejemplo-grado-5} and line $(t+2,t,t)$.}
 \label{fig: ex-2}
\end{figure}

Next, since the input parametrization $\cP$  is an standardized ruled parametrization without affine base points, by Theorem \ref{theorem-recta-critica}, the possible missing points of $\cP$ are included in the line defined by $\{x-y-2, x-z-2, y-z\}$, that is, the line $(t+2,t,t)$; see Fig. \ref{fig: ex-2}. In fact, on the line, $\cP$ reaches only the points
\[ \cP\left(\frac{1}{2}(1-i\sqrt{7}),\frac{1}{4}(3+i\sqrt{7})\right)=\left( {\frac {3}{32}}\,i\sqrt {7}+{\frac {65}{32}},{\frac {3}{32}}\,i\sqrt
{7}+\frac{1}{32},{\frac {3}{32}}\,i\sqrt {7}+\frac{1}{32}  \right),\]
 \[\cP\left(\frac{1}{2}(1+i\sqrt{7}),\frac{1}{4}(3-i\sqrt{7})\right)=\left(-{\frac {3}{32}}\,i\sqrt {7}+{\frac {65}{32}},-{\frac {3}{32}}\,i
\sqrt {7}+\frac{1}{32},-{\frac {3}{32}}\,i\sqrt {7}+\frac{1}{32} \right) \]
 Nevertheless,  ${\cal H}$ covers the whole line by taking ${\cal H}(0,t)$.
\end{example}

\begin{example}\label{ejemplo-grado-4}
We consider the parametrization
\[  \cP(s,t) =\left( \frac{r_1(s)+t p_1(s)}{q(s)}, \frac{r_2(s)+t p_2(s)}{q(s)}, \frac{r_3(s)+t p_3(s)}{q(s)} \right) = \]
\[
\left(  {\frac {ts+ \left( -3\,s+2 \right) {s}^{5}}{ \left( s-1 \right) {s}^{
2}}},{\frac {t \left( s+1 \right) + \left( -5\,s+3 \right) {s}^{2}}{
 \left( s-1 \right) {s}^{2}}},{\frac {t \left( s+2 \right) + \left( -8
\,s+5 \right) {s}^{2}}{ \left( s-1 \right) {s}^{2}}}\right).
\]
It parametrizes the degree 4 ruled surface defined by

\noindent $F(x,y,z)=x{y}^{3}-3\,{y}^{2}zx+3\,xy{z}^{2}-x{z}^{3}-2\,{y}^{4}+7\,z{y}^{3}-9\,
{y}^{2}{z}^{2}+5\,y{z}^{3}-{z}^{4}-9\,{y}^{2}x+18\,zyx-9\,{z}^{2}x-5\,
{y}^{3}-9\,{y}^{2}z+16\,{z}^{2}y-5\,{z}^{3}+27\,yx-27\,zx-78\,{y}^{2}+
89\,zy-23\,{z}^{2}-27\,x-14\,y+17\,z+12.$

We observe that $\cP(s,t)$ is in standardized form, so we go to Step 3 in Algorithm \ref{alg-1}. $I$ is the ideal generated by
 $\{p_1t+r_1,p_2t+r_2,p_3t+r_3,q\}$ in $k[s,t]$. We get $\sqrt{I}\neq I$, and a Gr\"obner basis of $\sqrt{I}$ w.r.t. the lexicographic ordering $t>s$ (Step 4) is
 $\{t^2-t, -t+s\}$. So, in Step 4 (b) we get that $f(s)=s$. Note that the affine base points are $(0,0)$ and $(1,1)$ and $t=s$ is the interpolating line; observe that the corresponding Gr\"obner basis of $I$, $\{t^2-t, st-t, s^2-t \}$, that does not read the interpolating polynomial of minimal degree, although it contains the parabola $t=s^2$ that passes through the base points.
  In Step 4 (b, i), we replace $\cP(s,t)$ by
 $\cP(s,1/t+s)$, namely
 \[ \cP(s,t)=\left(-{\frac {3\,{s}^{5}t-2\,{s}^{4}t-ts-1}{st \left( s-1 \right) }},-{
\frac {5\,{s}^{3}t-4\,t{s}^{2}-ts-s-1}{t \left( s-1 \right) {s}^{2}}},\right. \]\[\left.
-{\frac {8\,{s}^{3}t-6\,t{s}^{2}-2\,ts-s-2}{t \left( s-1 \right) {s}^{
2}}}\right). \]
 In Step 4 (b, ii), $\widetilde{Q}=s^2-s$. So, we replace $\cP$ by $\cP(s, 1/((s^2-s)t))$, namely
 \[
  \cP(s,t)=\left( {\frac {-3\,{s}^{4}-{s}^{3}-{s}^{2}+ts-s}{s}},{\frac {ts-5\,s+t-1}{s}
},{\frac {ts-8\,s+2\,t-2}{s}}\right).
\]
Now, the lexicographic order Gr\"obner basis of $\sqrt{I}$ is $\{s, t-1\}$, and hence $\cP$ still have one base point, namely $(0,1)$. Now, the interpolation polynomial is $f(s)=1$ and $\widetilde{Q}=s$. Repeating the steps as above we reach at the end of Step 4
\begin{equation}\label{eq-ejer-3}
 \cP(s,t)=(- (3\,{s}^{2}+s-t+1) s,ts+t-4,ts+2\,t-7)
 \end{equation}
In Step 5 we get
\[ \alpha_{12}=-3{s}^{5}-4{s}^{4}-2{s}^{3}+3{s}^{2},\alpha_{13}=-3{s}^{5}-7{s}^{4}-3{s}^{3}+5{s}^{2},\alpha_{23}=-3{s}^{2}+s
\]
In Step 6 the boolean conditions do  hold, and the output is the parametrization $\cP$ in (\ref{eq-ejer-3}) which is normal.

\end{example}

\section{Removal of Base Points: the General Case}

In Lemma \ref{lemma-reglada-sin-puntos-base} we have seen that, for the special case of standardized ruled surfaces, one can always find a reparametrization such that the new parametrization does not have affine base points. In this section we see that the ideas applied in the proof of that lemma can be generalized to any rational parametrization. More precisely we have the following result.

\begin{theorem}\label{th: remove bpt}
 Let $\cP\colon k^2\dashedrightarrow k^3$ be an affine rational parametrization,  with nonconstant components, of a surface. Then there exists a rational reparametrization $\cP\circ\psi$ without affine base points. Moreover,  $\deg(\cP)=\deg(\cP\circ\psi)$ as rational maps; in particular, properness is preserved.
\end{theorem}

\begin{proof}
 If $\cP$ has no affine base points, take as $\psi$ the identity.

 We can assume without loss of generality that, after a suitable linear birational change,
 \[
  \cP(s,t) = \left( \frac{p_1(s,t)}{q(s,t)}, \frac{p_2(s,t)}{q(s,t)}, \frac{p_3(s,t)}{q(s,t)} \right)
 \]
 where $\deg(p_1)=\deg(p_2)=\deg(p_3)=\deg(q)$, $\gcd(p_1,p_2,p_3,q)=1$, and the projective point $(0:1:0)$ does not belong to any of the projectivizations of the four curves determined by numerators and denominator. We also assume that there are no two affine base points with the same $s$-coordinate, since this can be achieved by composition with $(s,t)\to(s+\lambda t,t)$ for generic $\lambda$ without losing the previous assumptions.

 By the last assumption, there exists an interpolation polynomial $f(s)$ for the affine base points, i.e. for every base point $(s_i,t_i)$ we have $t_i=f(s_i)$; note that the $\gcd$ condition implies finiteness of the base point set. We define the birational reparametrization
 \[
  \psi(s,t)=\left(s,\frac{1}{t}+f(s)\right)
 \]
 and $\tcP=\cP\circ\psi$. We will prove that $\tcP$ has no affine base points. To this end we write
 \[
  \cP=\left(\frac{a_nt^n+a_{n-1}(s)t^{n-1}+\cdots+a_0(s)}{b_nt^n+b_{n-1}(s)t^{n-1}+\cdots+b_0(s)},\ldots,\ldots\right)
 \]
 with $a_n,b_n\neq0$ and $\deg(a_i),\deg(b_i)\leq n-i$. This is possible by the hypothesis on the degrees of $p_1,p_2,p_3,q$, and the fact that $t^n$ appears in all of them with nonzero coefficient (equivalent to the hypothesis on $(0:1:0)$.) Then
 \[
  \tcP=\left(\frac{a_n(1+tf(s))^n+ta_{n-1}(s)(1+tf(s))^{n-1}+\cdots+t^na_0(s)}{b_n(1+tf(s))^n+tb_{n-1}(s)(1+tf(s))^{n-1}+\cdots+t^nb_0(s)},\ldots,\ldots\right).
 \]
 This new parametrization cannot have any base points of the form $(s_0,0)$, since $\tcP(s_0,0)=(a_n/b_n,\ldots,\ldots)$. On the other hand, if $(s_0,t_0)$ is a base point of $\tcP$ with $t_0\neq0$, then $\psi(s_0,t_0)$ is a base point $(s_i,t_i)$ of $\cP$. But this is impossible: if $\psi(s_0,t_0)=(s_i,t_i)$ then $s_0=s_i$ and $1/t_0+f(s_0)=t_i$ which imply $1/t_0=0$, contradiction.   Finally, note that the previous transformations are birational, and $\psi$ is a birational map from $k^2$ on $k^2$, and hence the degree of the parametrization maps is preserved.
\end{proof}

 The reasoning in the previous proof leads to an algorithmic process to remove the affine base points of a surface parametrization. To be more precise, let
 \[
  \cP(s,t) = \left( \frac{p_1(s,t)}{q(s,t)}, \frac{p_2(s,t)}{q(s,t)}, \frac{p_3(s,t)}{q(s,t)} \right)
 \]
 be the surface parametrization. First, we observe that some assumptions on the parametrization are done, namely
\begin{enumerate}
\item {\sf [degree and gcd condition]} $\deg(p_1)=\deg(p_2)=\deg(p_3)=\deg(q)$, and $\gcd(p_1,p_2,p_3,q)=1$,
\item {\sf [condition on $(0:1:0)$]} the projective point $(0:1:0)$ does not belong to any of the projectivizations of the four curves determined by numerators and denominator,
\item {\sf [general position of the base points]} there are no two affine base points with the same $s$-coordinate.
\end{enumerate}

Observe that, in the rational ruled case, condition 3 is satisfied while, in general, conditions 1 and 2 fail because of the particular structure of standardized form, that we wanted to be preserved. So, in Section \ref{sec:covering-theory}, we have developed an \textit{ad hoc} proof for the ruled case.

Once the parametrization satisfies these conditions, one computes the interpolation polynomial $f(s)$ passing through the affine base points.  Then, $\psi(s,t)=(s,\frac{1}{t}+f(s))$. We observe that condition 1 can always be achieved by a birational change of the form
\[ \left(\frac{a_1t+b_1s+c_1}{d_1t+e_1s+h_1}, \frac{a_2t+b_2s+c_2}{d_2t+e_2s+h_2}\right), \]
and condition 2 with a linear change $(s+\lambda t, t)$. In the following lemma we see how to check the third condition and how to actually compute the interpolation polynomial $f(s)$  without approximating roots. This result extends Lemma \ref{lemma-interpolation} to the general case.

\begin{lemma}\label{lemma-interpolacion-general}
Let $I$ be the ideal generated by $\{p_1,p_2,p_3,q\}$ in $k[s,t]$.
\begin{enumerate}
\item Condition 3 is satisfied if and only if there exists a polynomial of the form $t-g(s)$ in $\sqrt{I}$.
\item If $t-g(s)\in \sqrt{I}$, then $g(s)$ interpolates the affine base points.
\end{enumerate}
\end{lemma}
\begin{proof}
If condition 3 holds, then $t-f(s)$ vanishes on all the points in the variety of $I$. So, $t-f(s)\in \sqrt{I}$. The converse is trivial, and (2) follows from (1).
\end{proof}

\begin{algorithm}\label{alg-2}
The input is a rational surface parametrization with affine base points, and the output is a parametrization of the same surface without base points.
\begin{enumerate}
 \item Reparametrize the input to satisfy conditions 1 and 2.
 \item Calculate $\sqrt{I}$; see Step 3 in Algorithm \ref{alg-1}.
 \item Calculate a Gr\"obner basis of $\sqrt{I}$ with respect to the lexicographical ordering $t>s$.
 \begin{enumerate}
  \item If the basis contains a polynomial of the form $t-f(s)$, then by the previous Lemma condition 3 is satisfied and we can apply the reparametrization of Theorem \ref{th: remove bpt} to RETURN $\cP(s,1/t+f(s))$.
  \item In the negative case, by elementary properties of Gr\"obner bases it follows that there is no polynomial of that form in $\sqrt{I}$. Again by Lemma \ref{lemma-interpolacion-general}, condition 3 is not satisfied. Apply a transformation $(s+\lambda t, t)$ for random $\lambda$ in the ground field and go to step 2.
 \end{enumerate}
\end{enumerate}
\end{algorithm}

As a consequence of Theorem \ref{th: remove bpt} and Algorithm \ref{alg-2}, the following corollaries hold.

\begin{corollary}\label{cor-1}
Every rational surface over an algebraically closed field of characteristic zero can always be parametrized without affine base points.
\end{corollary}

\begin{corollary}\label{cor-2}
Every rational surface parametrization can be reparametrized, without affine base points, without extending the field of coefficients and the degree as rational maps.
\end{corollary}

We illustrate the ideas of this section by an example.

\begin{example}\label{ex-pto-base-general}
We consider the rational parametrization
\[ \cP(s,t)=\left(\frac{p_1(s,t)}{q(s,t)},\frac{p_2(s,t)}{q(s,t)}, \frac{p_3(s,t)}{q(s,t)} \right)=  \left({\frac {4\,{s}^{2}-4\,st+{t}^{2}-6\,s+3\,t}{2\,{s}^{2}+8\,st+3\,{t}^{
2}-8\,s-11\,t}},\right. \]
\[\left. {\frac {{s}^{2}-6\,st-{t}^{2}+s+7\,t}{2\,{s}^{2}+8\,st
+3\,{t}^{2}-8\,s-11\,t}},{\frac {-3\,{s}^{2}+22\,st+4\,{t}^{2}-5\,s-26
\,t}{2\,{s}^{2}+8\,st+3\,{t}^{2}-8\,s-11\,t}}\right) \]
Its base points are $\{(0,0),(2,1),(1,2),(1,-1) \}$. We observe that $\cP(s,t)$ satisfies conditions 1 and 2. Let $I$ be the ideal generated
by $\{p_1,p_2,p_3,q\}$. A Gr\"obner basis of $\sqrt{I}$ w.r.t. the lexicographic order with $t>s$ is
\[ \{s^3-3s^2+2s, -s^2+2st+s-2t, 2s^2+t^2-4s-t \}.\]
Since there is no polynomial of the form $t-f(s)$ in the basis,  condition 3 fails, and we perform a change of parameters. For example $\cP$ is replaced by $\cP(s+t,t)$. Applying again the Gr\"obner basis computation to $\sqrt{I}$ for the new $\cP$, we obtain the basis
\[ \{s^4-2s^3-s^2+2s, 2s^3-3s^2-s+2t \}.\]
The second polynomial implies that $t-(-s^3+(3/2)s^2+(1/2)s)\in \sqrt{J}$. So condition 3 is now satisfied and $f(s)=-s^3+(3/2)s^2+(1/2)s$. Therefore, performing the transformation $\cP(s,1/t+f(s))$ we get a new parametrization without affine base points, namely
\[ \left( {\frac {4 {s}^{6}{t}^{2}-12 {s}^{5}{t}^{2}-11 {s}^{4}{t}^{2}+42 {
s}^{3}{t}^{2}-8 {s}^{3}t+7 {s}^{2}{t}^{2}+12 {s}^{2}t-30 {t}^{2}s+
20 st-12 t+4}{52 {s}^{6}{t}^{2}-156 {s}^{5}{t}^{2}+17 {s}^{4}{t}^
{2}+226 {s}^{3}{t}^{2}-104 {s}^{3}t-69 {s}^{2}{t}^{2}+156 {s}^{2}t
-70 {t}^{2}s+100 st-76 t+52}},\right.\]
\[-2 {\frac {12 {s}^{6}{t}^{2}-36 {s
}^{5}{t}^{2}+7 {s}^{4}{t}^{2}+46 {s}^{3}{t}^{2}-24 {s}^{3}t-19 {s}
^{2}{t}^{2}+36 {s}^{2}t-10 {t}^{2}s+20 st-16 t+12}{52 {s}^{6}{t}^
{2}-156 {s}^{5}{t}^{2}+17 {s}^{4}{t}^{2}+226 {s}^{3}{t}^{2}-104 {s
}^{3}t-69 {s}^{2}{t}^{2}+156 {s}^{2}t-70 {t}^{2}s+100 st-76 t+52}
}, \]
\[ \left. {\frac {92 {s}^{6}{t}^{2}-276 {s}^{5}{t}^{2}+51 {s}^{4}{t}^{2}+
358 {s}^{3}{t}^{2}-184 {s}^{3}t-143 {s}^{2}{t}^{2}+276 {s}^{2}t-82
 {t}^{2}s+156 st-124 t+92}{52 {s}^{6}{t}^{2}-156 {s}^{5}{t}^{2}+
17 {s}^{4}{t}^{2}+226 {s}^{3}{t}^{2}-104 {s}^{3}t-69 {s}^{2}{t}^{2
}+156 {s}^{2}t-70 {t}^{2}s+100 st-76 t+52}} \right). \]
\end{example}

\begin{example}
In \cite{Wang}, section 4.5, the author tests his implicitization algorithm with a family of rational surface parametrizations collected from different papers. For those having affine points, we apply Algorithm \ref{alg-2}:
\begin{enumerate}
\item {\sf Example 1 in \cite{Wang}.} The parametrization is
\[ \cP=\left( {\frac {s{t}^{2}-{t}^{3}-t}{{t}^{2}-2\,t+1}},{\frac {{t}^{3}-st-{t}^{
2}+t+1}{{t}^{2}-2\,t+1}},{\frac {st-2\,t}{{t}^{2}-2\,t+1}}\right). \]
 The Gr\"obner basis  of $\sqrt{I}$ w.r.t. the lexicographical ordering $t>s$ is $\{s-2, t-1\}$; indeed $\cP$ has the affine base point $(2,1)$. So the interpolating polynomial is $f(s)=1$. Therefore,  $\cP(s,1/t+1)$ does not have affine base points.
\item {\sf Example 6 in \cite{Wang}.} The parametrization is
\[ \cP=\left( {\frac {s \left( s+t-1 \right) }{{s}^{2}+st+{t}^{2}-1}},{\frac {t
 \left( s+t-1 \right) }{{s}^{2}+st+{t}^{2}-1}},{\frac {s+t-1}{{s}^{2}+
st+{t}^{2}-1}}\right). \]
 The Gr\"obner basis  of $\sqrt{I}$ w.r.t. the lexicographical ordering $t>s$ is $\{s^2-s, s+t-1\}$; indeed $\cP$ has the affine base points $(0,1),(1,0)$. So the interpolating polynomial is $f(s)=1-s$. Therefore,  $\cP(s,1/t+(1-s))$ does not have affine base points.
 \item {\sf Example 9 in \cite{Wang}.} The parametrization is
\[ \begin{array}{lll}
\cP&= &\left( {\dfrac {{s}^{2}t+2\,{t}^{3}+{s}^{2}+4\,st+4\,{t}^{2}+3\,s+2\,t+2}{{s}
^{3}+{s}^{2}t+{t}^{3}+{s}^{2}+{t}^{2}-s-t-1}},\right. \\ \\
& &\left. {\dfrac {-{s}^{3}-2\,s{t}
^{2}-2\,{s}^{2}-st+s-2\,t+2}{{s}^{3}+{s}^{2}t+{t}^{3}+{s}^{2}+{t}^{2}-
s-t-1}},\right.\\ \\
&& \left.{\dfrac {-{s}^{3}-2\,{s}^{2}t-3\,s{t}^{2}-3\,{s}^{2}-3\,st+2\,{
t}^{2}-2\,s-2\,t}{{s}^{3}+{s}^{2}t+{t}^{3}+{s}^{2}+{t}^{2}-s-t-1}}\right). \end{array} \]
 The Gr\"obner basis  of $\sqrt{I}$ w.r.t. the lexicographical ordering $t>s$ is
 $$ \begin{array}{l}
 \{9\,{s}^{6}+8\,{s}^{5}-12\,{s}^{4}+27\,{s}^{3}+34\,{s}^{2}-44\,s-40,\\
1665\,{s}^{5}+382\,{s}^{4}-2152\,{s}^{3}+4939\,{s}^{2}+1540\,s+3288\,t
-4268\}.
\end{array}$$
 So $\cP$ has 6  affine base points, and the interpolation polynomial is
  \[ f(s)=-{\frac {555}{1096}}\,{s}^{5}-{\frac {191}{1644}}\,{s}^{4}+{\frac {269
}{411}}\,{s}^{3}-{\frac {4939}{3288}}\,{s}^{2}-{\frac {385}{822}}\,s+{
\frac {1067}{822}}.
  \]  Therefore,  $\cP(s,1/t+f(s))$ does not have affine base points.
  \item {\sf Example 10 in \cite{Wang}.} The parametrization is
\[ \begin{array}{lll}
\cP&=&\left( {\dfrac {-{s}^{4}+4\,{s}^{3}t-2\,{s}^{2}{t}^{2}+s{t}^{3}+{s}^{2}t-2\,{
t}^{3}}{-{s}^{3}t+6\,{s}^{2}{t}^{2}-3\,s{t}^{3}+{t}^{4}+{s}^{3}-2\,s{t
}^{2}}},\right.\\ \\ && {\dfrac {-{s}^{3}t-2\,{s}^{3}+{s}^{2}t+3\,s{t}^{2}-{t}^{3}}{-{s
}^{3}t+6\,{s}^{2}{t}^{2}-3\,s{t}^{3}+{t}^{4}+{s}^{3}-2\,s{t}^{2}}}, \\ \\
&&
\left.{
\dfrac {-s{t}^{3}+{s}^{3}-4\,{s}^{2}t-s{t}^{2}+6\,{t}^{3}}{-{s}^{3}t+6
\,{s}^{2}{t}^{2}-3\,s{t}^{3}+{t}^{4}+{s}^{3}-2\,s{t}^{2}}}\right).\end{array} \]
 The Gr\"obner basis  of $\sqrt{I}$ w.r.t. the lexicographical ordering $t>s$ is
 $$ \begin{array}{l}
 \{{s}^{6}-7\,{s}^{5}-20\,{s}^{4}+173\,{s}^{3}-27\,{s}^{2}+s,\\-176\,{s}^{
5}+1205\,{s}^{4}+3605\,{s}^{3}-29867\,{s}^{2}+2371\,s+703\,t\}.
\end{array}$$
 So $\cP$ has 6  affine base points, and the interpolation polynomial is
  \[ f(s)={\frac {176}{703}}\,{s}^{5}-{\frac {1205}{703}}\,{s}^{4}-{\frac {3605}
{703}}\,{s}^{3}+{\frac {29867}{703}}\,{s}^{2}-{\frac {2371}{703}}\,s.
  \]  Therefore,  $\cP(s,1/t+f(s))$ does not have affine base points.
\end{enumerate}
\end{example}

\section{Acknowledgements}

This work was developed, and partially supported, by the Spanish \emph{Ministerio de Eco\-no\-m{\'\i}a y Competitividad} under Project MTM2011-25816-C02-01; as well as Junta de Extremadura and FEDER funds (group FQM024). The first and third authors are members of the
Research Group ASYNACS (Ref. CCEE2011/R34). The second author is a member of the research group GADAC (U. of Extremadura).


TITLE: Trying to get velocity of rebounding of a sphere.
QUESTION [0 upvotes]: Problem :

A sphere of mass $3/8kg$. is projected vertically upwards with velocity $7 m/sec$. from a point below the ceiling of the room at a distance $1.6 metre$. It impinges the ceiling, then it rebounded downwards. If the magnitude of change in the magnitude of its momentum due to this impact with the ceiling equals $2400 gm.m./sec$. Calculate the velocity of rebounding of the sphere.

So it should look like this :

My attempt :

to get $V_1$ :

$V_o = 7 m/s$
$a = g = -9 m/sec^2$
$d = 1.6m$

So $V_1^2 = (7)^2 + (2 \times -9.8 \times 1.6)$
$V_1^2 = 17.64$
$V_1 = 4.2m/s$

Since Change of Momentum = $2400 gm.m/sec$

$2400 = ({3 \over 8} \times 10^{3})(V_2 - V_1)$
$2400 = ({3 \over 8} \times 10^{3})(V_2 - 4.2)$

then $V_2 = 10.6m/s$ (my answer)

However my textbook says that the correct answer should be $2.2m/s$
i have no idea what went wrong , any help will be appreciated
thanks in advance.

REPLY [2 votes]: You're so close! Remember, momentum is a vector, so in most problems involving momentum, direction is important. In your equation
$$2400 = \left(\frac{3}{8} \times 10^3\right)(V_{2}-4.2)$$
You have implicitly defined a positive velocity as an upward velocity. Good choice. However, in this case, your change in momentum is negative, so your left hand side of the equation needs a negative sign. You should write
$$-2400 = \left(\frac{3}{8} \times 10^3\right)(V_{2}-4.2)$$
You will recover an answer of $-2.2\ m/s$. This is the ball's velocity, and it makes sense that it is negative since the ball is travelling downward after the rebound. Since the problem is really asking about the speed, just take the absolute value to obtain $2.2\ m/s$.


text:
\section{Verification of Local Convergence Assumptions}
\label{app:Verification}

In this section, we briefly discuss different situations that allow us to verify and establish the local conditions stated in Assumption~\ref{assum3-1} and required for Corollary~\ref{cor:stronger-loc}.

\subsection{The Smooth Case} \label{sec:app-smo}

Clearly, assumption \ref{Btwo} is satisfied if $g$ is a smooth mapping.

In addition, as mentioned at the end of subsection~\ref{sec:loc}, if the mapping $g$ is continuously differentiable in a neighborhood of its associated fixed-point $x^*$, then the stronger differentiability condition

\begin{enumerate}[label=\textup{\textrm{(C.\arabic*)}},topsep=0pt,itemsep=0ex,partopsep=0ex,parsep=0ex,leftmargin=6ex]
\item \label{Cone} $\|g(x)-g(x^*) - g^\prime(x^*)(x-x^*)\| = O(\|x-x^*\|^2)$ for $x \to x^*$,

\end{enumerate}

used in Corollary~\ref{cor:stronger-loc}, holds if the derivative $g^\prime$ is locally Lipschitz continuous around $x^*$, i.e., for any $x,y \in \mathbb{B}_\epsilon(x^*)$ we have

\begin{equation} \label{eq:lip-fre} \|g^\prime(x) - g^\prime(y)\| \leq L \|x-y\|. \end{equation}

Assumption \ref{Cone} can then be shown via utilizing a Taylor expansion. Let us notice that for \ref{Cone} it is enough to fix $y = x^*$ in \eqref{eq:lip-fre}. Such a condition is known as outer Lipschitz continuity at $x^*$. Furthermore, assumption \ref{Bone} holds if $\sup_{x \in \Rn} \|g^\prime(x)\| < 1$, see, e.g., Theorem 4.20 of~\citeappx{Bec14}.

\subsection{Total Variation Based Image Reconstruction} \label{sec:app-tv}

The alternating minimization solver for image reconstruction problem~\eqref{prob-TV} can be written as a fixed-point iteration
\begin{equation} \label{eq:tv-fix}
w^{k+1} = g(w^k) := (\Phi\circ h)(w^k),
\end{equation}
with
\begin{align*}
\Phi(w) &:= (s_\beta(w_{1})^T,\ldots,s_\beta(w_{N^2})^T)^T \in \mathbb{R}^{2N^2},\\
s_\beta(x) &:=\max\left\{\|x\|-\frac{1}{\beta},0\right\}\frac{x}{\|x\|},
\end{align*}
and
\begin{align*}
	h(w) &:= DM^{-1}(D^T w+ ({\nu}/{\beta})K^Tf ),\\
	D &:= (D_1^T,\ldots,D_{N^2}^T)^T,\\
	M &:=D^TD+\frac{\nu}{\beta}K^TK.
\end{align*}
Let us notice that the mapping $h$ and the fixed point iteration \eqref{eq:tv-fix} are well-defined when the null spaces of $K$ and $D$ have no intersection, see, e.g., Assumption~1 of~\citeappx{wang2008new}.

Next, we verify Assumption~\ref{assum3-1} for the mapping $g$ in \eqref{eq:tv-fix}.
\begin{proposition}
\label{prop4-2}
Suppose that the operator $K^TK$ is invertible. Then, the spectral radius $\rho(T)$ of $T := DM^{-1}D^T$ fulfills $\rho(T)<1$ and condition \ref{Bone} is satisfied.
\end{proposition}
\begin{proof}
Utilizing the Sherman-Morrison-Woodbury formula and the invertibility of $K^T K$, we obtain

\begin{align}
	& \hspace{-5ex}(I+\xi D(K^TK)^{-1}D^T)^{-1} \notag \\
	=~ &I - \xi D(K^TK)^{-1}(I + \xi D^TD(K^TK)^{-1})^{-1} D^T \notag \\
	=~ & I-T,
	\label{eq:smw}
\end{align}

where $\xi := {\beta}/{\nu}$.
Due to
$$\lambda_{\min}(I+\xi D(K^TK)^{-1}D^T) \geq 1$$
and
$$\lambda_{\max}(I+\xi D(K^TK)^{-1}D^T) \leq 1 + \xi \|D(K^TK)^{-1}D^T\|,$$
it then follows that

\begin{align*}
\sigma((I+\xi D(K^TK)^{-1}D^T)^{-1}) & \\ & \hspace{-20ex}
\subset \left [\frac{1}{1+\xi\|D(K^TK)^{-1}D^T\|},1 \right],
\end{align*}

where $\sigma(\cdot)$ denotes the spectral set of a matrix. Combining this observation with \eqref{eq:smw}, we have

\begin{align*}
& \sigma(T)\subset \left[0,1-\frac{1}{1+\xi\|D(K^TK)^{-1}D^T\|}\right]\\
& \implies \rho(T)<1.
\end{align*}

Furthermore, following the proof of Theorem 3.6 in~\citeappx{wang2008new}, it holds that

$$ \|g(w)-g(v)\|  \leq \rho(T)\|w-v\| \quad \forall~w,v \in\mathbb{R}^{2N^2}  $$

and hence, assumption \ref{Bone} is satisfied.
\end{proof}

Concerning assumption \ref{Btwo}, it can be shown that $g$ is twice continuously differentiable on the set
$$\mathcal W =\{w: \|[h(w)]_{i}\|\neq {1}/{\beta}, \,\forall~i=1,\ldots,N^2\}.$$
(In this case the max-operation in the shrinkage operator $s_\beta$ is not active).

Moreover, since $h$ is continuous, the set $\mathcal W$ is open. Consequently, for every point $w \in \mathcal W$, we can find a bounded open neighborhood $N(w)$ of $w$ such that $N(w) \subset \mathcal W$. Hence, if the mapping $g$ has a fixed-point $w^*$ satisfying $w^* \in \mathcal W$, then we can infer that $g$ is differentiable on $N(w^*)$ and assumption \ref{Btwo} has to hold at $w^*$. Furthermore, the stronger assumption \ref{Cone} for Corollary~\ref{cor:stronger-loc} is satisfied as well in this case. Finally, if $K$ is the identity matrix, then notice that the finite difference matrix $D$ satisfies that $\|D\|\leq 2$ and we can infer $\rho(T)\leq 1-(1+4\beta/\nu)^{-1}$ which
justifies the choice of $c$ in our algorithm.

\subsection{Nonnegative Least Squares}
\label{appx:NNLS}
We first note that given the specific form of $\varphi$, we can calculate the proximal operator $\varphi$ explicitly as

\[
\prox_{\beta\varphi}(v)=\frac12((v_1+v_2)^T,(v_1+v_2)^T)^T,
\]

where $v=(v_1^T,v_2^T)^T$. Consequently, we obtain
$$[2\prox_{\beta\varphi}-I](v)=(v_2^T,v_1^T)^T.$$
Similarly, by setting
$$ \psi_1(v_1) := \|Hv_1 - t\|_2^2, \qquad \psi_2(v_2) := \mathcal I_{v_2\geq0}(v_2),$$
we have

\begin{align*}
\prox_{\beta \psi}(v) & =
\begin{pmatrix}
	\prox_{\beta \psi_1}(v_1) \\
	\prox_{\beta \psi_2}(v_2)
\end{pmatrix},\\
\prox_{\beta \psi_1}(v_1) &=
(H^T H + (2\beta)^{-1}I )^{-1}(H^T t + v_1 /({2\beta})),\\
\prox_{\beta \psi_2}(v_2) &= \mathcal P_{[0,\infty)^q}(v_2),
\end{align*}
where $\mathcal P_{[0,\infty)^q}$ denotes the Euclidean projection onto the set of nonnegative numbers $[0,\infty)^q$. In the next proposition, we give a condition to establish \ref{Bone} for $g$.

\begin{proposition}
Let $\sigma_0$ and $\sigma_1$ denote the minimum and maximum eigenvalue of $2H^TH$, respectively and suppose $\sigma_0 > 0$. Then, the mapping $g$ is Lipschitz continuous with modulus ${\sqrt{3+c_1^2}}/{2}$, where $c_1=\max\{\frac{\beta\sigma_1-1}{\beta\sigma_1+1},\frac{1-\beta\sigma_0}{1+\beta\sigma_0}\} < 1$.
\end{proposition}

\begin{proof}
We can explicitly calculate $g$ as follows

\begin{align}
	g(v) &= \frac{1}{2}((2\prox_{\beta\varphi}-I)(2\prox_{\beta \psi}-I)+I)v \notag \\
	& = \frac12 \begin{pmatrix}\mathcal R^2_\beta(v_2)+v_1 \\ \mathcal R^1_\beta(v_1)+v_2\end{pmatrix},
	\label{eq:dr-nn}
\end{align}

where
$$\mathcal R^i_\beta=2\prox_{\beta \psi_i}-I, \quad i=1,2.$$
By Proposition~4.2 of~\citeappx{BauCom11}, the reflected operators $\mathcal R_\beta^1$ and $\mathcal{R}_\beta^2$ are nonexpansive. Moreover, since $\sigma_0>0$, $\psi_1$ is strongly convex with modulus $\sigma_0$ and $\sigma_1$-smooth. Then by Theorem~1 of~\citeappx{giselsson2016linear}, $\mathcal{R}_\beta^1$ is Lipschitz continuous with modulus $c_1$.
Next, for any $v,\bar{v}\in \R^{2q}$, we have

\begingroup
\allowdisplaybreaks
\begin{align}
\notag &\hspace{-4ex}\|g(v)-g(\bar v)\|\\
\notag =~& \frac12 \left[ \|\mathcal R_\beta^2(v_2)-\mathcal R_\beta^2(\bar v_2)  +v_1-\bar v_1\|^2\right. \\
\notag & \hspace{4ex} \left. + \|\mathcal R_\beta^1(v_1)-\mathcal R_\beta^1(\bar v_1)  +v_2-\bar v_2\|^2 \right]^\frac12 \\
\notag \leq~ & \frac12 \left[ (c_1^2 + 1)\|v_1 - \bar v_1\|^2 + 2(c_1 + 1)\|v_1 - \bar v_1\| \right. \\
\notag & \hspace{4ex} \left. \cdot \|v_2-\bar v_2\|  + 2 \|v_2 - \bar v_2\|^2 \right]^\frac12 \\
\notag \leq~ & \frac12 \left[ (c_1^2 + 1)\|v_1 - \bar v_1\|^2 +\frac{(c_1+1)^2}{c_1^2+1}\|v_1 - \bar v_1\|^2 \right. \\
\label{eq:g-2}& \hspace{4ex} \left. +(c_1^2+1)\|v_2-\bar v_2\|^2 + 2 \|v_2 - \bar v_2\|^2 \right]^\frac12 \\
\notag \leq~ & \frac12 \sqrt{(c_1^2 + 3)\|v_1 - \bar v_1\|^2 + (c_1^2+3) \|v_2 - \bar v_2\|^2}  \\

\notag\leq~ & \frac{\sqrt{3+c_1^2}}{2}\|v-\bar{v}\|,
\end{align}
\endgroup
where we have used Cauchy's inequality, the nonexpansiveness of $\mathcal R^2_\beta$ and the Lipschitz continuity of $\mathcal R^1_\beta$ in the first inequality. The estimate in Eqn.~\eqref{eq:g-2} follows from Young's inequality.
\end{proof}

Hence, assumption~\ref{Bone} is satisfied if $H$ has full column rank.
Using the special form of the mapping $g$ in \eqref{eq:dr-nn}, we see that $g$ is twice continuously differentiable at $v = (v_1^T,v_2^T)^T$ if and only if $v \in \mathcal V := \R^q \times \prod_{i=1}^q \R \backslash \{0\}$, i.e., if none of the components of $v_2$ are zero. As before, we can then infer that assumption~\ref{Btwo} and the stronger condition \ref{Cone} have to hold at every fixed-point $v^*$ of $g$ satisfying $v^* \in \mathcal V$.

\subsection{Further Extensions}
\label{sec:app-extension}

We now formulate a possible extension of the conditions presented in Section~\ref{sec:app-smo} to the nonsmooth setting.

If the mapping $g$ has more structure and is connected to an underlying optimization problem like in forward-backward and Douglas-Rachford splitting, nonsmoothness of $g$ typically results from the proximity operator or projection operators. In such a case, further theoretical tools are available and for certain function classes it is possible to fully characterize the differentiability of $g$ at $x^*$ via a so-called strict complementarity condition. In fact, the conditions $w^* \in \mathcal W$ and $v^* \in \mathcal V$ from section~\ref{sec:app-tv} and \ref{appx:NNLS} are equivalent to such a strict complementarity condition). In the case of forward-backward splitting, a related and in-depth discussion of this important observation is provided in \citeappx{SteThePat17,mai2019anderson} and we refer the interested reader to~\citeappx{PolRoc96,milzarek2016numerical,LiaFadPey17,SteThePat17} for further background.

Concerning the stronger assumption \ref{Cone}, we can establish the following characterization: Suppose that $g$ is locally Lipschitz continuous and let us consider the properties:

\begin{itemize}
\item The function $g$ is differentiable at $x^*$.
\item The mapping $g$ is strongly (or 1-order) semismooth at $x^*$~\citeappx{QiSun93}, i.e., we have

\[ \sup_{M \in \partial g(x)}~\|g(x) - g(x^*) - M(x-x^*) \| = O(\|x-x^*\|^2) \]

when $x \to x^*$. Here, the multifunction $\partial g : \Rn \rightrightarrows \R^{n \times n}$ denotes Clarke's subdifferential of the locally Lipschitz continuous (and possibly nonsmooth) function $g$, see, e.g., \citeappx{Cla90,QiSun93}.

\item There exists an outer Lipschitz continuous selection $M^* : \R^n \to \R^{n \times n}$ of $\partial g$ in a neighborhood of $x^*$, i.e., for all $x$ sufficiently close to $x^*$ we have

\[ M^*(x) \in \partial g(x)\]
{and}
\[\quad \|M^*(x) - M^*(x^*)\| \leq L_M \|x - x^*\| \]

for some constant $L_M > 0$.
\end{itemize}

Then, the mapping $g$ satisfies the condition \ref{Cone} at $x^*$.

\begin{proof} The combination of differentiability and semismoothness implies that $g$ is strictly differentiable at $x^*$ and as a consequence, Clarke's subdifferential at $x^*$ reduces to the singleton $\partial g(x^*) = \{g^\prime(x^*)\}$. We refer to~\citeappx{QiSun93,rockafellar2009variational,milzarek2016numerical} for further details. Thus, we can infer $M^*(x^*) = g^\prime(x^*)$ and we obtain

\begin{align*}
	& \hspace{-8ex}\|g(x) - g(x^*) - g^\prime(x^*)(x-x^*)\| \\
	\leq~ & \|g(x)-g(x^*)-M^*(x)(x-x^*)\| \\
	& + \|[M^*(x)-M^*(x^*)](x-x^*)\|\\
	\leq~& O(\|x-x^*\|^2) + L_M \|x-x^*\|^2,
\end{align*}

for $x \to x^*$, where we used the strong semismoothness and outer Lipschitz continuity in the last step. This establishes \ref{Btwo}. \end{proof}

The class of strongly semismooth functions is rather rich and includes, e.g., piecewise twice continuously differentiable (PC${}^2$) functions~\citeappx{Ulb11}, eigenvalue and singular value functions~\citeappx{SunSun02,SunSun05}, and certain spectral operators of matrices~\citeappx{DinSunSunToh20}. Let us further note that the stated selection property is always satisfied when $g$ is a piecewise linear mapping. In this case, the sets $\partial g(x)$ are polyhedral and outer Lipschitz continuity follows from Theorem~3D.1 of~\citeappx{DonRoc14}.

\section{Further Numerical Examples}
\label{app:Examples}

\subsection{Ablation Study on Parameter Choices}
This subsection provides more numerical experiments on the parameters of our method, using the examples given in Figs.~\ref{fig:LogisticRegression},  \ref{fig:TVDenoising} and \ref{fig:NNLS} of the paper. In each experiment, we run our method by varying a subset of the parameters while keeping all other parameters the same as in the original figures, to evaluate how the varied parameters influence the performance of our method.
For the evaluation, we plot the same convergence graphs as in the original figures to compare the performance resulting from different parameter choices.
The evaluation is performed on the parameters $c$, $(p_1, p_2)$, $(\eta_1, \eta_2)$, and $\mu_0$.

We first consider the logistic regression problem in Fig.~\ref{fig:LogisticRegression} with $m=15$ and $\tau = L_F \times 10^{-6}$. The parameters used in Fig.~\ref{fig:LogisticRegression} are: $p_1=0.01$, $p_2=0.25$, $\eta_1=2$, $\eta_2=0.25$, $\mu_0 = 100$, $c = \kappa = ({L_F-\tau})/(L_F+\tau)$. Figs.~\ref{fig:Ablation_LR_c}, \ref{fig:Ablation_LR_p}, \ref{fig:Ablation_LR_eta}, and \ref{fig:Ablation_LR_mu} show the results using varied values of $c$, $(p_1, p_2)$, $(\eta_1, \eta_2)$, and $\mu_0$, respectively. (Note: the figures in this subsection are placed at the end of this document.)

Next, we consider the image reconstruction problem in Fig.~\ref{fig:TVDenoising} with $m = 5$ and $\beta = 100$. The parameters used in Fig.~\ref{fig:TVDenoising} are: $p_1=0.01$, $p_2=0.25$, $\eta_1=2$, $\eta_2=0.25$, $\mu_0 = 1$, and $c = \kappa$ where $\kappa$ is derived in Appendix~\ref{sec:app-tv}. Figs.~\ref{fig:Ablation_TV_c}, \ref{fig:Ablation_TV_p}, \ref{fig:Ablation_TV_eta}, and \ref{fig:Ablation_TV_mu} show the results using varied values of $c$, $(p_1, p_2)$, $(\eta_1, \eta_2)$, and $\mu_0$, respectively.

Finally, we consider the nonnegative least squares problem in Fig.~\ref{fig:NNLS} with $m=10$. The parameters used in Fig.~\ref{fig:NNLS} are: $p_1=0.01$, $p_2=0.25$, $\eta_1=2$, $\eta_2=0.25$, $\mu_0 = 1$, and $c = \kappa$ where $\kappa$ is derived in Appendix~\ref{appx:NNLS}. Figs.~\ref{fig:Ablation_NNLS_c}, \ref{fig:Ablation_NNLS_p}, \ref{fig:Ablation_NNLS_eta}, and \ref{fig:Ablation_NNLS_mu} show the results using varied values of $c$, $(p_1, p_2)$, $(\eta_1, \eta_2)$, and $\mu_0$, respectively.

As shown in Figs.~\ref{fig:Ablation_LR_c}, \ref{fig:Ablation_TV_c}, and \ref{fig:Ablation_NNLS_c}, our algorithm is not very sensitive w.r.t. the choice of $c$. Specifically, we still observe convergence if $c$ is chosen smaller than the Lipschitz constant $\kappa$. This robustness is particularly important when good estimates of the constant $\kappa$ are not available. Although the bound $c \geq \kappa$ is required in our theoretical results in Section~\ref{sec:loc}, fast convergence can still be observed for other choices of $c$. This indicates that either we have over-estimated the Lipschitz constant $\kappa$ or the acceleration effect of AA steps can be much faster than $\kappa$.

The results in Figs.~\ref{fig:Ablation_LR_p}, \ref{fig:Ablation_TV_p}, and \ref{fig:Ablation_NNLS_p} demonstrate that the performance of LM-AA is not overly affected by the choice of the trust-region parameters $p_1$ and $p_2$ either. In general, good performance can be achieved if $p_1$ is moderately small and $p_2$ is not too large. Thus, we decide to work with the standard choice $p_1 = 0.01$ and $p_2 = 0.25$.

In comparison, the trust-region parameters $\eta_1$ and $\eta_2$ can have a more significant impact on the performance of our algorithm. While the performance of LM-AA is not sensitive to the choice of $\eta_1$ and $\eta_2$ in the logistic regression problem using the dataset \texttt{sido0} (Fig.~\ref{fig:Ablation_LR_eta}) and in the denoising problem (Fig.~\ref{fig:Ablation_TV_eta}), more variation can be seen in the remaining two examples. In general, the performance seems to deteriorate when $\eta_1$ and $\eta_2$ are chosen to be very close to each other. The standard choice $\eta_1 = 2$ and $\eta_2 = 0.25$ again achieves convincing performance on all numerical examples and has a good balance when increasing and decreasing the weight parameter $\lambda_k$.

Finally, the convergence plot for different values of $\mu_0$ are shown in Figs.~\ref{fig:Ablation_LR_mu}, \ref{fig:Ablation_TV_mu}, and \ref{fig:Ablation_NNLS_mu}. Our observations are again somewhat similar: the performance of LM-AA on the logistic regression problem for \texttt{sido0} (Fig.~\ref{fig:Ablation_LR_mu}) and on the denoising problem  (Fig.~\ref{fig:Ablation_TV_mu}) is very robust w.r.t. the choice of $\mu_0$. In the nonnegative least squares problem, $\mu_0$ appears to mainly affect the last convergence stage of the algorithm, i.e., different choices of $\mu_0$ can lead to an earlier jump to a level with higher accuracy. Overall the parameters $\mu_0 =1$ (for denoising and NNLS) and $\mu_0 = 100$ (for logistic regression) yield the most robust results.

\subsection{Statistics of Successful Steps}
In this subsection, we provide statistics of the successful steps in Figs.~\ref{fig:LogisticRegression},  \ref{fig:TVDenoising} and \ref{fig:NNLS}. Specifically, for each instance of LM-AA, we count the total steps required to reach a certain level of accuracy and we compare it with the corresponding number of successful AA steps within these steps.
Tables~\ref{tab:01}, \ref{tab:02}, \ref{tab:03}, and \ref{tab:04} show the statistics of successful steps for Figs.~\ref{fig:LogisticRegression},  \ref{fig:TVDenoising} and \ref{fig:NNLS}, respectively. Here, besides the total number of steps, we report the success rate which is defined as the ratio between successful and total steps required to reach different levels of accuracy.

The results in Table~\ref{tab:04} demonstrate that essentially all AA steps are accepted in the nonnegative least squares problem. This observation is also independent of the choice of the parameter $m$. More specifically, the success rate of AA steps only decreases and more alternative fixed-point iterations are performed when we seek to solve the problem with the highest accuracy $\textit{tol} = 10^{-15}$. Table~\ref{tab:03} illustrates that a similar behavior can also be observed for the image denoising problem \eqref{prob-TV} when setting $m=1$. Notice that this high accuracy is close to machine precision and hence this effect is mainly caused by numerical errors and inaccuracies that affect the computation and quality of an AA step. The results in Table~\ref{tab:03} also demonstrate a second typical effect: the success rate of AA step is often lower when the chosen accuracy is relatively low. With increasing accuracy, the rate then increases to around 70\%--80\%. This general observation is also supported by our results for logistic regression, see Tables~\ref{tab:01} and \ref{tab:02}. (Here the maximum success rate is more sensitive to the choice of $m$, $\tau$, and of the dataset).

In summary, the statistics provided in the Tables~\ref{tab:01}, \ref{tab:02}, \ref{tab:03}, and \ref{tab:04} support our theoretical results. The success rate of AA steps gradually increases as the iteration gets closer to the fixed point, which indicates transition to a pure regularized AA scheme. Furthermore, as more AA steps seem to be rejected at the beginning of the iterative procedure, our globalization mechanism effectively guarantees global progress and convergence of the approach.

\begin{table*}[t!]
\small
\centering
\begin{tabular}{|c||c|c|cl|cl|cl|cl|cl|}
\hline
\multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{\texttt{covtype}}}} &  & \multirow{3}{*}{$m$} & \multicolumn{10}{c|}{{\textit{tol} \quad (stopping criterion: $(F-F^*)/F^* \leq \textit{tol}$)}} \\
\cline{4-13}
\rule{0pt}{10pt} & & & \multicolumn{2}{c|}{$10^{-3}$} & \multicolumn{2}{c|}{$10^{-6}$} & \multicolumn{2}{c|}{$10^{-9}$} & \multicolumn{2}{c|}{$10^{-12}$} & \multicolumn{2}{c|}{$10^{-15}$} \\
& & & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter}  & \textit{$s$-rate} & \textit{iter} \\
\cline{2-13}
\rule{0pt}{8pt} & \multirow{3}{*}{$\tau = \frac{L_F}{10^6}$} & 10 & 72.3\% & 83 & 94.3\% & 599 & 98.3\% & 2000 & 98.3\% & 2000 & 98.3\% & 2000 \\
\rule{0pt}{6pt} & & 15 & 57.3\% & 82 & 88.0\% & 541 & 93.8\% & 1175 & 96.1\% & 1887 & 96.4\% & 2000 \\
\rule{0pt}{6pt} & & 20 & 49.0\% & 98 & 73.5\% & 434 & 87.8\% & 1058 & 90.5\% & 1351 & 92.9\% & 1812 \\
\cline{2-13}
\rule{0pt}{8pt} & \multirow{3}{*}{$\tau = \frac{L_F}{10^9}$} & 10 & 86.6\% & 119 & 95.7\% & 1083 & 96.3\% & 3336 & 96.7\% & 3755 & 96.7\% & 3781 \\
\rule{0pt}{6pt} & & 15 & 55.4\% & 83 & 86.0\% & 783 & 32.0\% & 5000 & 32.0\% & 5000 & 32.0\% & 5000  \\
\rule{0pt}{6pt} & & 20 & 50.5\% & 91 & 73.2\% & 593 & 18.8\% & 5000 & 18.8\% & 5000 & 18.8\% & 5000 \\
\hline
 \end{tabular}
\caption{Statistics of successful steps of LM-AA for the logistic regression problem \eqref{eq:LogisticRegression} and the dataset \texttt{covtype}. In each of the columns \textit{iter}, we report the number of iterations required to satisfy $(F(x^k)-F^*)/F^* \leq \textit{tol}$ with $\textit{tol} \in \{10^{-3},10^{-6},10^{-9},10^{-12},10^{-15}\}$. The columns \textit{$s$-rate} show the corresponding success rate of AA-steps, i.e., \textit{$s$-rate} is  the ratio between successful and total steps required to reach the different accuracies.}
\label{tab:01}
\end{table*}

\begin{table*}[t!]
\small
\centering
\begin{tabular}{|c||c|c|cl|cl|cl|cl|cl|}
\hline
\multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{\texttt{sido0}}}} &  & \multirow{3}{*}{$m$} & \multicolumn{10}{c|}{{\textit{tol} \quad (stopping criterion: $(F-F^*)/F^* \leq \textit{tol}$)}} \\
\cline{4-13}
\rule{0pt}{10pt} & & & \multicolumn{2}{c|}{$10^{-3}$} & \multicolumn{2}{c|}{$10^{-6}$} & \multicolumn{2}{c|}{$10^{-9}$} & \multicolumn{2}{c|}{$10^{-12}$} & \multicolumn{2}{c|}{$10^{-15}$} \\
& & & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter}  & \textit{$s$-rate} & \textit{iter} \\
\cline{2-13}
\rule{0pt}{8pt} & \multirow{3}{*}{$\tau = \frac{L_F}{10^6}$} & 10 & 67.1\% & 334 & 82.9\% & 686 & 88.3\% & 997 & 92.7\% & 1621 & 93.8\% & 2000 \\
\rule{0pt}{6pt} & & 15 & 55.6\% & 315 & 77.7\% & 676 & 84.8\% & 994 & 89.7\% & 1481 & 91.8\% & 1992 \\
\rule{0pt}{6pt} & & 20 & 46.2\% & 368 & 65.4\% & 619 & 76.7\% & 917 & 85.3\% & 1453 & 88.8\% & 2000 \\
\cline{2-13}
\rule{0pt}{8pt} & \multirow{3}{*}{$\tau = \frac{L_F}{10^9}$} & 10 & 48.3\% & 1208 & 64.6\% & 2051 & 67.1\% & 3006 & 53.5\% & 4774 & 51.9\% & 4950 \\
\rule{0pt}{6pt} & & 15 & 46.5\% & 1815 & 59.5\% & 2714 & 60.5\% & 3788 & 50.9\% & 5000 & 50.9\% & 5000 \\
\rule{0pt}{6pt} & & 20 & 46.6\% & 2205 & 57.8\% & 3037 & 57.8\% & 4090 & 51.7\% & 5000 & 51.7\% & 5000 \\
\hline
 \end{tabular}
\caption{Statistics of successful steps of LM-AA for the logistic regression problem \eqref{eq:LogisticRegression} and the dataset \texttt{sido0}. In each of the columns \textit{iter}, we report the number of iterations required to satisfy the criterion $(F(x^k)-F^*)/F^* \leq \textit{tol}$ with $\textit{tol} \in \{10^{-3},10^{-6},10^{-9},10^{-12},10^{-15}\}$. The columns \textit{$s$-rate} show the corresponding success rate of AA-steps, i.e., \textit{$s$-rate} is  the ratio between successful and total steps required to reach the different accuracies.}
\label{tab:02}
\end{table*}

\begin{table*}[t!]
\small
\centering
\begin{tabular}{|c|c|cl|cl|cl|cl|cl|}
\hline
& \multirow{3}{*}{$m$} & \multicolumn{10}{c|}{{\textit{tol} \quad (stopping criterion: $\|f(w)\| \leq \textit{tol}$)}} \\
\cline{3-12}
\rule{0pt}{10pt} & & \multicolumn{2}{c|}{$10^{-3}$} & \multicolumn{2}{c|}{$10^{-6}$} & \multicolumn{2}{c|}{$10^{-9}$} & \multicolumn{2}{c|}{$10^{-12}$} & \multicolumn{2}{c|}{$10^{-15}$} \\
& & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter}  & \textit{$s$-rate} & \textit{iter} \\
\cline{1-12}
\rule{0pt}{8pt} \multirow{3}{*}{$\beta = 100$} & 1 & 93.7\% & 190 & 96.6\% & 378 & 98.4\% & 812 & 99.0\% & 1274 & 91.2\% & 2000 \\
\rule{0pt}{6pt} & 3 & 39.5\% & 223 & 54.4\% & 296 & 72.0\% & 483 & 79.7\% & 666 & 64.3\% & 2000 \\
\rule{0pt}{6pt} & 5 & 38.8\% & 227 & 53.4\% & 298 & 68.8\% & 446 & 75.9\% & 577 & 54.8\% & 2000 \\
\cline{1-12}
\rule{0pt}{8pt} \multirow{3}{*}{$\beta = 1000$} & 1 & 92.1\% & 1057 & 90.5\% & 1489 & 95.9\% & 3477 & 97.9\% & 7677 & 75.7\% & 15000 \\
\rule{0pt}{6pt} & 3 & 34.6\% & 1458 & 39.6\% & 1824 & 56.7\% & 2554 & 68.8\% & 3543 & 47.6\% & 15000 \\
\rule{0pt}{6pt} & 5 & 35.0\% & 1410 & 38.5\% & 1776 & 60.6\% & 2773 & 68.0\% & 3408 & 43.0\% & 15000 \\
\hline
 \end{tabular}
\caption{Statistics of successful steps of LM-AA for the image denoising problem \eqref{prob-TV}. In each of the columns \textit{iter}, we report the number of iterations required to satisfy the criterion $\|f(w^k)\| \leq \textit{tol}$ with $\textit{tol} \in \{10^{-3},10^{-6},10^{-9},10^{-12},10^{-15}\}$. The columns \textit{$s$-rate} show the success rate of AA-steps, i.e., \textit{$s$-rate} is  the ratio between successful and total steps required to reach the different accuracies.}
\label{tab:03}
\end{table*}

\begin{table*}[t!]
\small
\centering
\begin{tabular}{|c|cl|cl|cl|cl|cl|}
\hline
\multirow{3}{*}{$m$} & \multicolumn{10}{c|}{{\textit{tol} \quad (stopping criterion: $\|f(v)\| \leq \textit{tol}$)}} \\
\cline{2-11}
\rule{0pt}{10pt} & \multicolumn{2}{c|}{$10^{-3}$} & \multicolumn{2}{c|}{$10^{-6}$} & \multicolumn{2}{c|}{$10^{-9}$} & \multicolumn{2}{c|}{$10^{-12}$} & \multicolumn{2}{c|}{$10^{-15}$} \\
& \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter} & \textit{$s$-rate} & \textit{iter}  & \textit{$s$-rate} & \textit{iter} \\
\cline{1-11}
\rule{0pt}{8pt} 5 & 100\% & 646 & 100\% & 1500 & 100\% & 1500 & 100\% & 1500 & 100\% & 1500 \\
\rule{0pt}{6pt} 10 & 100\% & 235 & 100\% & 512 & 100\% & 696 & 93.3\% & 989 & 67.5\% & 1500 \\
\rule{0pt}{6pt} 15 & 100\% & 151 & 100\% & 437 & 100\% & 680 & 100\% & 792 & 58.0\% & 1500 \\
\rule{0pt}{6pt} 20 & 100\% & 162 & 100\% & 344 & 100\% & 465 & 100\% & 572 & 44.4\% & 1500 \\
\hline
 \end{tabular}
\caption{Statistics of successful steps of LM-AA for the nonnegative least squares problem \eqref{eq:reNNLS}. In each of the columns \textit{iter}, we report the number of iterations required to satisfy the criterion $\|f(w^k)\| \leq \textit{tol}$ with $\textit{tol} \in \{10^{-3},10^{-6},10^{-9},10^{-12},10^{-15}\}$. The columns \textit{$s$-rate} show the success rate of AA-steps, i.e., \textit{$s$-rate} is the ratio between successful and total steps required to reach the different accuracies.}
\label{tab:04}
\end{table*}

config: arxiv


TITLE: Show $P(S_{2n}=x|S_0=x) \ge \frac{1}{N}$
QUESTION [0 upvotes]: Let $X_n$ be an aperiodic, discrete-time Markov chain so $S=\{1,...,N\}$ whose transition probability is symmetric. How can I show that for all $x \in S$ and all integers $n$, $P(S_{2n}=x|S_0=x) \ge \frac{1}{N}$. And would this hold in $2n$ is replaced with $2n+1$?
I'm really stuck and have no idea how to do this practice problem. Any help would be appreciated. Thanks

REPLY [0 votes]: Let $p$ denote the transition matrix of the Markov chain, then $p$ is symmetric hence $p^n(x,y)=p^n(y,x)$ for every $x$ and $y$ in $S$ and, for every $x$ in $S$,
$$
|S|\cdot p^{2n}(x,x)=|S|\cdot\sum_{y\in S}p^n(x,y)p^n(y,x)=\sum_{y\in S}1\cdot\sum_{y\in S}(p^n(x,y))^2.
$$
By Cauchy-Schwarz inequality, the RHS is at least
$$
\left(\sum_{y\in S}p(x,y)\right)^2=1.$$

And would this hold in $2n$ is replaced with $2n+1$?

No, as shown by chains of period $2$ in a neighborhood of radius $n+1$ around $x$.


TITLE: Why does graphene exist?
QUESTION [5 upvotes]: I started to read some articles on graphene and almost all say that graphene was discovered late because physicists thought it would be unstable. Despite this, I didn't found a clear explanation of why graphene is indeed stable.
Why does graphene exist, despite the Mermin-Wagner theorem?

REPLY [4 votes]: The answer lies in the fact that, in graphene, there is an effective long range interaction mediated by the inverse biharmonic operator (which in 2D goes as $x^2\ln(x)$ and is extremely long-ranged) coupling the gaussian curvature at any two points on the sheet. Due to this, any static ripples or thermally produced dynamic ripples interact at arbitrary distances and allow for the existence of a flat phase (ordering of the normals). I have written an answer  here , which basically explains this point. David Nelson and Peliti did quite a bit of work on this in the 1980s, in the context of polymerized or tethered membranes (membranes with crystalline order).


TITLE: Determine $\textrm{sign}[x + \ln y]$
QUESTION [2 upvotes]: I need to determine the sign of
\begin{align}
f(a,b) = \textrm{sign}\left[\frac{(a-1)(b-1)^2}{ba^2(b(a-1)+1)} + \ln\left(\frac{b(a-1)+1}{ab}\right)\right] = ?
\end{align}
with $a \geq 1$, and $b > 0$.
We have $f(a,b=1) = 0$. I conjecture also that $f(a,b<1) > 0$ and $f(a,b>1) < 0$. Cannot show it, however, because of the $\ln$. Any hints are appreciated.
Idea: There is only one root for $f$, namely $f(a,b) = 0$ iff $b=1$ for all $a$. Let $a=1$ such that
\begin{align}
f(1,b) = \ln\left(\frac{1}{b}\right)
\begin{cases}
> 0 \quad &\textrm{if } b < 1\\
< 0 \quad &\textrm{if } b > 1.
\end{cases}
\end{align}

REPLY [1 votes]: for $0<b<1$:
$$
[\ldots]=\left[\underbrace{\ldots}_{> 0}+\ln\Big(\underbrace{1+\frac{1-b}{ab}}_{> 1}\Big)\right]>0.
$$
for $b>1$: use the fact that $\ln(1+x)\le x$, for $x>-1$, i.e.
$$
[\ldots]\le\frac{a-1}{a-1+1/b}\cdot\Big(\frac{b-1}{ab}\Big)^2
-\frac{b-1}{ab}=\epsilon\cdot q^2-q<0
$$
since $0<\epsilon<1$ and $0<q<1$.


TITLE: $H$ $\cong$ $K$ and $G/H$ $\cong$ $G'/K$ implies $G$ $\cong$ $G'$?
QUESTION [0 upvotes]: Let $G$ and $G'$ be groups not necessarily finite and $H$ and $K$ their subgroups respectively. Given $H$ $\cong$ $K$ and $G/H$ $\cong$ $G'/K$, is it true that $G$ $\cong$ $G'$? Please help me with an explicit map if they are isomorphic.

REPLY [10 votes]: No, this is very false. For the simplest counterexample, take $G = \mathbb{Z}_4$, $G' = \mathbb{Z}_2 \times \mathbb{Z}_2$, $H,K \cong \mathbb{Z}_2$. In fact, it is in general extremely hard to classify all the so-called extensions of a group by another.
However, if there exists a homomorphism $f:G \to G'$ that restricts to an isomorphism $H \cong K$ and that induces an isomorphism $G/H \cong G'/K$, then $f$ is an isomorphism (this is the short five lemma).


TITLE: How many solutions does this system of equations have?
QUESTION [3 upvotes]: I have $2$ equations :

$$-\frac{a}{2}x-\frac{b}{2}+cx+d=x+2$$
  $$-2ax-2b+cx+d=2x+1$$
  with $a, b, c, x \neq 0$

We have to find all possible solutions of $a, b, c, d$ that make the equations true for all $x$.
I found one solution
$a=-\frac{2}{3}$,
$b=\frac{2}{3}$,
$c=\frac{2}{3}$,
$d=\frac{7}{3}$
But, I wonder if there are any other solutions to this system of equations?

REPLY [3 votes]: Write the equations as:
$$
\begin{cases}
\begin{align}
(a-2c+2)x+b-2d+4 = 0 \\
(2a-c+2)x+2b-d+1 = 0
\end{align}
\end{cases}
$$
A polynomial is identical $0$ (i.e. for all $x$) iff all its coefficients are $0\,$, which gives the system to solve:
$$
\begin{cases}
\begin{align}
a - 2c + 2 = 0 \\
2a - c + 2 = 0 \\[7px]
b - 2d + 4 = 0 \\
2b -d + 1 = 0
\end{align}
\end{cases}
$$
The system has the unique solution as posted $\;a=-\frac{2}{3}$, $b=\frac{2}{3}$, $c=\frac{2}{3}$, $d=\frac{7}{3}\,$.


TITLE: Unit sphere in $L^p([0,1])$ is not compact.
QUESTION [5 upvotes]: I am studying $L^p$ spaces and I would like a proof why the unit sphere in $L^p([0,1])$ is not compact. I know that unit sphere is not compact in infinite dimensional spaces, but I think there is an elementary proof, tailored to this example. I would appreciate your help.

REPLY [1 votes]: Consider
$$
f_n := n\chi_{[0,1/n]} \in L^p[0,1]
$$
Then if $n<m$,
$$
\|f_n - f_m\|_p^p = \int_0^{1/m} (m-n)^pdt + \int_{1/m}^{1/n} n^pdt \geq \frac{(m-n)^p}{m}
$$
Hence if $p\geq 1$, this sequence cannot have a convergent subsequence.


TITLE: Is a $G$-cell complex always a $G$-CW complex?
QUESTION [5 upvotes]: I recall vaguely once reading that a cell complex—constructed like a CW-complex but without assuming the cells are appended in order of increasing dimension —"is" actually a CW-complex. I cannot remember if this means there is a homotopy equivalent CW-complex or something stronger.
Is there a similar result for $G$-cell complexes vs. $G$-CW-complexes, for $G$ a compact Lie group?

REPLY [4 votes]: As Najib says in the comments to the question, the proof of the classical statement can be easily-ish adapted to the equivariant case. Let's see the details
Lemma Let $X$ be a $G$-CW-complex and let $f:G/H\times S^n\to X$ be a $G$-equivariant continuous map. Then $f$ factors up to equivariant homotopy through the $n$-skeleton of $X$
Proof: This is just a special case of the cellular approximation theorem (theorem I.3.4 in May's Equivariant Homotopy and Cohomology Theory).
A $G$-equivariant continuous map from $G/H\times S^n$ is the same thing as a continuous map from $S^n$ to $X^H$ and the same hold for equivariant homotopies. Hence we need to show that, if $X^{(n)}$ is the $n$-skeleton of $X$, the inclusion $(X^{(n)})^H\to X^H$ is $n$-connected. But the cofiber $X^H/(X^{(n)})^H\cong (X/X^{(n)})^H$ is obtained by adding cells of the form $(G/K\times D^m)^H$ for $m>n$, and so it is $n$-connected. $\square$
Armed with the lemma, we can prove that every $G$-complex $Y$ is homotopy equivalent to a $G$-CW-complex. I will prove only the case where $Y$ has finitely many cells, the general case just needs a transfinite induction that I don't want to write down right now.
We will proceed by induction on the number of cells. If $Y$ has only one cell, then it has of course the structure of a $G$-CW-complex, obtained by using a CW structure on the disc.
Suppose now that the thesis is true for all $G$-complexes with $m$ cells. Then, if $Y$ is a $G$-complex with $(m+1)$ cells, we can write it as the pushout $Y=Y'\amalg_{G/H\times S^n} G/H\times D^{n+1}$ for some $H$ and $n$. But, by the previous lemma, the attaching map $G/H\times S^n\to Y'$ factors up to homotopy through the $n$-skeleton of $Y'$. So we can attach it together with the other $(n+1)$-cells without changing the homotopy type of $Y$. Hence $Y$ has the homotopy type of a $G$-CW-complex.


TITLE: Quotient Group question ambiguity about group order
QUESTION [1 upvotes]: $\mathbb{R}$  and $\mathbb{Z} $ are groups under addition.
Show $a+\mathbb{Z} \in \mathbb{R/Z}$ is of finite order if and only if $a$ is rational.
How can this be of finite order for any $a$? Let $a=\frac{1}{2}$
Then the group coset $a+\mathbb{Z}$ is $\{...-\frac{5}{2},-\frac{3}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2},\frac{5}{2}...\}$
This is certainly not of finite order.
I'm obviously misunderstanding something- can someone help?

REPLY [1 votes]: By taking the quotient, we are effectively treating any integer as the identity element. Hence an element in $\mathbb{R}/\mathbb{Z}$ has finite order if some multiple of the coset representative is an integer.But this is precisely the definition of a rational number.


TITLE: Find the smallest value of positive constant $m$ such that curve will never lie below $x$-axis?
QUESTION [0 upvotes]: Question:
Find the smallest value of positive constant $m$ that will make curve
$$y=mx-1+\dfrac{1}{x}$$
Greater than or equal to zero for all positive values of $x$?
My attempt:
By $AM\geq GM$
$mx+ \dfrac {1}{x} \geq 2.\sqrt{m}$
so,
for curve to attain positive or zero value
$2\sqrt m -1\geq 0\implies m\geq1/4$
giving minimum value $m=0.25$.
But I want to ask how to do this problem using only calculus without using inequalities  because in my sheet, this problem was under the calculus section so I want to do it using calculus only. Thank you

REPLY [0 votes]: Imagine you have a string in the Cartesian plane that is mostly above the x-axis, but some of it is below. Now imagine this string moves in such a way that all of it is above the x-axis. Now think about what has to happen at the moment it goes from being partly below to being completely above. At that moment, it has to be tangent to the x-axis. That is, it has to have a point with y-value of zero (because it's right on the edge between being below the x-axis and not), and the slope has to be zero there (if, for instance, the slope were positive, then that would mean that there's a little bit to the left that's below, so you could still move it a little more while keeping some of it below the x-axis).
So you're looking for a point where both y and y' are zero. First, set y' to zero.
y'= m-1/x2 = 0
x = $\frac{1}{\sqrt{m}}$
Next, set y to zero
y = mx -1 + 1/x = $\sqrt{m} -1 + \sqrt{m} $ = 0
So
$2 \sqrt{m} = 1$
$\sqrt{m} = \frac{1}{2}$
$m = \frac{1}{4}$
Another way to think of it:
Imagine that the string intersects the x-axis at r1 and r2. As less and less of the string is below the x-axis, r1 and r2 should get closer and closer together. You're looking for the moment where they are the same.
You have
y = mx -1 + 1/x
y = (mx2 - x +1)/x
Setting this to zero, you have
(mx2 - x +1)/x = 0
mx2 - x +1 = 0
You now want the discriminant in the quadratic formula to be zero so that the two roots will be the same.
b2-4ac = 0
1-4m = 0
m = 1/4


TITLE: Counting Probabilities
QUESTION [1 upvotes]: An appliance comes in two colors, white and brown, which are in equal demand. A certain dealer in these appliances has three of each color in stock, although this is not known to the customers. Customers arrive and independently order these appliances. How do I find the probability that
a) the third white is ordered by the fifth customer?
b) all of the whites are ordered before any of the browns are ordered?
c) all of the whites are ordered before all of the browns are ordered?
Is there a more efficient method to solve these problems rather than counting?

REPLY [1 votes]: A small amount of counting is used in (a). For (c), there is an easy no counting solution.
(a) We want the probability that the first four customers order a total of $2$ white and $2$ brown and the $5$th customer orders white.
The probability of $2$ white and $2$ brown in $4$ orders is $\dbinom{4}{2}\left(\dfrac{1}{2}\right)^4$. Given that this has happened, the probability the $5$th order is white is $\dfrac{1}{2}$. For the required probability, multiply. We get
$$\binom{4}{2}\left(\frac{1}{2}\right)^5.$$
(b) This is just the probability of three heads in a row when tossing a fair coin.
(c) This can be computed in various ways. One reasonable approach is by recycling. Let $x$ be the probability all the whites are ordered before any brown. Let $y$ be the probability the $3$rd white is the $4$th item ordered. And let $z$ be the probability that the $3$rd white is the $5$th item ordered. We want $x+y+z$. We already computed $x$ in part (b), and $z$ in part (a). It remains to compute $y$, which can be done in a way quite similar to the solution of (a).
But there is a trivial way of finding the answer! By symmetry, "we run out of whites before we run out of browns" is just as likely as "we run out of browns before we run out of whites." Thus the required probability is $\dfrac{1}{2}$.
Remark: The $\binom{4}{2}\left(\frac{1}{2}\right)^4$ that formed part of the answer to (a) did use counting. We need to know how many $4$-letter words there are that have $2$ W and $2$ B.


TITLE: SUVAT applied to circular motion
QUESTION [1 upvotes]: My teacher set me this problem:
A ball is suspended from a ceiling by a string of length $7.5\ m$. The ball is kicked horizontally and rises to a maximum height of $6.0\ m$. Assuming that air resistance is negligible, show that the initial speed of the ball is $11\ ms^{-1}$
Now, I solved this problem by applying the SUVAT equation: $v^2 = u^2 + 2as$; where $v=0$, $a=g$, and $s=6$. Therefore $u=11$.
My teacher did not accept my solution and showed me how to do it using the conservation of energy: intial KE = gain in GPE;  $K_i=U_g$. She also explained that I cannot use SUVAT because the object is in circular motion and the acceleration is not constant. Also, the acceleration $g$ is not in the same direction as initial speed $u$. I understand this.
My question is: how can I get the right answer? Both the SUVAT method and the energy conservation method produce an expression for the change in height: $h = \frac{u^2}{2g}$
Is this just a coincidence? One valid method and one invalid method just happen to give the same expression?

REPLY [2 votes]: Is this just a coincidence? One valid method and one invalid method just happen to give the same expression?

If you take your kinematic SUVAT equation (kinematics  - the branch of mechanics that deals with pure motion, without reverence to the masses or forces involved in it ) $v^2=u^2+2as$ and multiply both sides by $\frac 12 m$ where $m$ is the mass of the mass of the ball you get $\frac 12 m v^2= \frac 12 m u^2+mas$ which you will see is the equation which your teacher wanted you to use.
So why in this case does a SUVAT (constant acceleration) equation being used where the acceleration is not constant produce the correct answer?
Well let’s examine the correct method using $\frac 12 m v^2- \frac 12 m u^2= mgs$.
The left hand side is the change in kinetic energy and the right hand side is the work done by a force $mg$ when its displacement is $s$ along the line of action of the force which for the gravitational force $mg$ is in the vertical direction.
However when treating this problem correctly as a dynamics problem (dynamics - the branch of mechanics concerned with the motion of bodies under the action of forces) one has to include all forces acting on the ball and in this case as well as the force $mg$ acting on the ball there is the force due to the string.
It just so happens in your example that the force on the ball due to the string does no work on the ball as the displacement of the ball is always at right angles to the force on the ball due to the string and that is why you got the correct answer using the SUVAT equation.


TITLE: Differentiation how to find the equation of normal perpendicular to the straight line
QUESTION [0 upvotes]: A curve has the equation $y=(2x-3)^2$. Find the equation of the normal to the curve that is perpendicular to the straight line $4x-y-5=0$,
I have differentiated the curve’s equation and I got $4(2x-3)$ as the answer. For the gradient of the straight line, I found that to be $4$. As it is perpendicular, the gradient for the normal would be $-\frac{1}{4}$. Is that right? Well, after this, what are the following steps to find the the equation of the normal?

REPLY [1 votes]: The derivative gives you the slope of the tangent which is perpendicular to the normal - So the tangent must be parallel to the external line - as you correctly determined the tangent must have a slope of 4.
The normal has slope $-\frac14$
and passes through the point $(
a, (2a-3)^2
)$
where $a$ is the solution to $4(2a-3)=4$


TITLE: If $Q\ltimes P$ is a Schmidt group with abelian $P$ and cyclic $Q$, then $\phi(P)$ is trivial.
QUESTION [2 upvotes]: Let $G$ be a Schmidt group. Suppose that $G=Q\ltimes P$, where $P$ is a Sylow $p$-subgroup of $G$ and $Q=\langle a \rangle$ is a cyclic Sylow $q$-subgroup of $G$.  Prove that if $P$ is abelian, then $\phi(P)=1$.

REPLY [2 votes]: If not, then $\Phi(P) \rtimes Q$ is a proper subgroup of $G$ and hence nilpotent, so $\Phi(P) \le C_P(Q)$. Now there is a general result (for finite groups) that  if a $p'$-group $Q$ acts on an abelian $p$-group $P$, then $P = C_P(Q) \times [P,Q]$. But then $[P,Q] \rtimes Q$ is a proper subgroup of $G$ and hence it is nilpotent, so $[P,Q] \le C_P(Q)$, contradiction.


TITLE: Reflexive, Symmetric and Transitive Closure verification or explanation
QUESTION [3 upvotes]: I've been given the following function where:
$$R:0..10 \iff 0..10 $$
$$ R = \{ m,n\colon\mathbb{N} \| m \neq n \land m + n = 8 \} $$
Therefore, I've calculated R as:
$$ R = \{(0,8),(1,7),(2,6),(3,5),(5,3),(6,2),(7,1),(8,0)\} $$
Reflexive Closure:
$$\{(0,0),(1,1),(2,2),(3,3),(5,5),(6,6),(7,7),(8,8)\} $$
Symmetric Closure:
$$ \{(8,0),(7,1),(6,2),(5,3),(3,5),(2,6),(1,7),(0,8)\} $$
Transitive Closure:
$$ \{(3,3)\} $$
Are these correct?

REPLY [5 votes]: For the reflexive closure, you have to add the points $(n,n)$ not only for $n$ in the field of your relation, but for $n$ in the set over which you are viewing your relation. Since the context here seems to be relations on the natural numbers between $0$ and $10$, according to what you wrote at first, then I would say that the reflexive closure of $R$ has all the elements of $R$ plus the pairs $(n,n)$ for $n\in\{0,1,\ldots,10\}$. So you need also to add $(4,4)$ and $(9,9)$ and $(10,10)$.
For the symmetric closure, what you wrote is fine, but actually it is the same as $R$ itself, since $R$ is already symmetric! So the symmetric closure of $R$ is $R$ itself.
For the transitive closure, you will end up adding the points that you've listed wrongly under the reflexive closure, since from $(0,8)$ and $(8,0)$ you've got to add $(0,0)$. From $(8,0)$ and $(0,8)$, you got to add $(8,8)$, and so on with the other numbers in the field.
Lastly, I thought you might like to see the figure I created illustrating the various kinds of closures of an example relation (not the same as your example). Some of my students found it useful to notice the differences in the various kinds of closures, and to discover the reason each diagram was as it was. I believe that anyone who can understand this picture really knows the reflexive, transitive and symmetric closures of a relation and their combinations.

I made a small post at https://plus.google.com/u/0/+JoelDavidHamkins1/posts/Gu3eScwxDzf.


TITLE: Definite integrals: Evaluate the integral
QUESTION [3 upvotes]: Evaluate:
  $$ \int ^{1/2}_{1/4} \frac{dx}{ \sqrt{x-x^2}}dx$$

can u help me with this?
What is meant by the dx in the numerator?
EDIT:
ANSWER AS GIVEN IN THE BOOK
$$ \int ^{1/2}_{1/4} \frac{dx}{ \sqrt{x-x^2}}dx$$
$$=\int ^{1/2}_{1/4} \frac{1}{\sqrt {-(x^2-x+\frac{1}{4}- \frac{1}{4})}}dx$$
$$=\int ^{1/2}_{1/4} \frac{1}{\sqrt{({\frac{1}{2}})^2-(x-\frac{1}{2})^2}}$$
$$=\int ^{1/2}_{1/4} \frac{dx}{\sqrt{({\frac{1}{2}})^2-(x-\frac{1}{2})^2}}$$
$$= [ \arcsin\frac{x-1/2} {1/2} ]^{1/2}_{1/4}= \arcsin0-\arcsin\frac{-1}{2}$$
$$=\pi/6$$
Please offer your assistance :)

REPLY [1 votes]: $$I=\int_{\frac14}^{\frac12}\frac{dx}{\sqrt{\left(\frac12\right)^2-\left(x-\frac12\right)^2}} =\int_{\frac14}^{\frac12}\frac{2dx}{\sqrt{1^2-(2x-1)^2}}$$
Put $2x-1=\sin y\implies 2dx=\cos y dy,$
When $x=\frac12,\sin y=0\implies y=0$ and $x=\frac14,\sin y=-\frac12\implies y=-\frac\pi6$
$$\implies I=\int_{-\frac\pi6}^0\frac{\cos ydy}{\cos y}=0-\left(-\frac\pi6\right)=\frac\pi6$$


TITLE: Is there a way to attach a mirror to a piezoelectric?
QUESTION [0 upvotes]: I want to use a mirror on the piezoelectric in Mickelson setup, how should I connect this?
Resonance frequency of piezoelectric is important for me. Is there a method to not change the frequency?

REPLY [2 votes]: Extra mass will change the resonance frequency. It would be minimal for an evaporated layer of aluminum (but the effect is large enough to be used for thickness monitoring: https://en.wikipedia.org/wiki/Quartz_crystal_microbalance ).


TITLE: Prove that qubits can be represented on a unit sphere, avoiding the density matrix formalism
QUESTION [2 upvotes]: The Bloch Sphere is regarded as the most "intuitive" way of explaining a 2-level quantum system in computation and rotations of states described on Bloch sphere provides a really easy picture. Despite that, I've been having some problems with understanding this representation of quantum states. I read quite a few articles and answers on StackExchange too, but most of them try to explain things using Pauli Matrices and Density Matrices. But the real problem I've been struggling to solve and understand would be better stated as follows-
Prove that a 2-level Quantum State (qubits) is mathematically equivalent to a point on the Unit Sphere in $\mathbb{R}^3$.
Most of the explanations I've seen are based on hand-wavy arguments and lack proper formalism. I've been trying to prove this without involving Pauli matrices or Density matrices. By using the arguments of normalization and global-phase invariance, I've been able to deduce that we can write an arbitrary state as follows-
$$|\psi \rangle=r|0\rangle + (a+ib)|1\rangle $$
where $r\in \mathbb{R}^{\geq0}$ and $ a,b\in \mathbb{R}$ with the constraint $r^2+a^2+b^2=1.$ If $a,b,r$ are the co-ordinates in the Cartesian system, then since we have $r\geq0$, the equation results in a hemisphere.
If anyone has an explanation or a proof of how qubits have an equivalent description on the Bloch sphere, or some suggestion, I would be grateful.

REPLY [1 votes]: Parametrizing a general state as
\begin{align}
\cos(\vartheta/2)\vert +\rangle + e^{i\varphi}\sin(\vartheta/2)\vert -\rangle
\tag{1}
\end{align}
(any state up to a global phase can be written that way) and computing
\begin{align}
\langle \sigma_x\rangle =\sin(\varphi)\sin(\vartheta)\, ,\qquad
\langle \sigma_y \rangle =\cos(\varphi)\sin(\vartheta)\, ,\qquad
\langle \sigma_z\rangle =\cos(\vartheta)
\end{align}
gives a vector
\begin{align}
\hat n=\left(\langle \sigma_x\rangle ,\langle \sigma_y\rangle,\langle\sigma_z\rangle
\right)
\end{align}
which points to a point on the Bloch sphere.


TITLE: Two pendulums, same pendulum length, same bob mass, but one bob's full of water
QUESTION [5 upvotes]: Suppose, a ideal pendulum which has a pendulum lenghth $L$ and a bob of mass $m$, another one whose bob has same mass and same effective length. But the second one's bob is hollow and and the hollow is full of water.
Will the periodic time $T$ of the two pendulums be same?

REPLY [2 votes]: If we can neglect friction with air, the formula for the period of a pendulum will be:
$T= 2\pi \sqrt {\frac {l}{g}}$
If $g$ is costant, as in this case, the period of the pendulum will only depend on the lenght of the string.
Because the center of mass of both bobs lays in the middle, the effective lenght (lenght of the string + distance of CM from the top of the bob) will be the same, ergo the two pendula will have the same period.
It is also interesting to see how the period of the pendulum changes when we ad different amounts of water in the bob.

At first, with no water, the center of mass of the bob lays in the middle (distance of CM from the top of the bob= Radius). The period is T.

2.When we star adding water, the CM of the system will go below the original one (distance of CM from the top of the bob= Radius +y ).The new period of the bob will be $T_f>T$. The period  will rise as long as we keep adding water below the original CM of the bob. When the water fills in half the bob,  the period will reach a maximum. As we add more water, the period will start to decrease again.

Eventually,when we fill the bob (completly) with water,  the CM of the system will lay in the same positon of the beginning. At this point, the effective lenght will be the same and so will be the period.

REPLY [0 votes]: The simple version
I think the time period will be same, in both cases.
Think of the pendulum's bob as the system. When "deriving" the expression for time period, we consider the bob to be the system, with the forces on it as $mg$, $T$ etcetera. We assert that:
$$ m\ell^2\dfrac{\mathrm d^2\theta}{\mathrm dt^2} = -mg\ell\sin\theta \approx -mg \cdot \theta$$
Giving,
$$T \approx 2\pi\sqrt{\dfrac {\ell}g}$$
All along, we involved only the forces that were applied on the bob, as a whole, externally. We didn't think of the internal forces. Now if we replace the rigid spherical bob by a hollow bob filled with fluid, we will have to consider "the hollow sphere, along with the fluid" as the system. We would then arrive at the same result. All along, we have assumed small oscillations.
Digging deeper
The thing is, all the above process is an approximation. But, importantly, I have also indirectly approximated that the fluid is a rigid body.$^1$ It is perfectly reasonable, if the hollow was completely filled, and the fluid was incompressible. But the question says water, which is compressible.
So what would happen is as the bob reaches the bottommost part of its trajectory, the water would be compressed due to the centrifugal force, thus shifting the centre of mass of the "bob system" lower for some time. This itself will vary so complicatedly that I cannot even begin to calculate the time period (good luck on that). But I predict that the time period will increase, seeing that for short periods $\ell$ effectively increases. For larger amplitudes, this effect will be even larger.
Note that, if the question had said "an incompressible fluid" instead of water, then whatever the situation (the bob should be completely filled though), the time period would be exactly the same.
I am open to discussion on this answer and any errors you might spot. I would like to know from the experts if my answer is indeed correct (just upvote! :P). Thank you.

$1$: I have also approximated that the bob is a point mass, but it doesn't really matter here, because both our bobs will be identical in all respects, except the ability of the fluid to be deformed. The essential difference has already been discussed!