\documentclass[letterpaper,10pt]{article} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amsthm,amssymb,tikz,pgfplots,csquotes} \usetikzlibrary{decorations.markings} \usepackage{graphicx} %% For including images \usepackage{fancyvrb} %% For Verbatim environment % http://stackoverflow.com/a/11331659/1068170 \usepackage{upquote} \usepackage{hyperref} \hypersetup{colorlinks=true,urlcolor=blue} \usepackage{embedfile} \embedfile{\jobname.tex} \embedfile{make_images_for_tex.py} \embedfile{stationary_pt_test.py} \embedfile{writeup_image00.png} \usepackage{fancyhdr} \pagestyle{fancy} \lhead{Danny Hermes} \rhead{Implicitizing Coordinate-Wise Polynomial Curves} \renewcommand{\headrulewidth}{0pt} \renewcommand{\qed}{$$\blacksquare$$} \begin{document} \textbf{NOTE:} To extract the \LaTeX\ source and other sources files from this PDF file, execute: \begin{Verbatim}[commandchars=\\\{\}] pdftk \jobname.pdf unpack_files output . \end{Verbatim} This is an algebraic problem concerning parametric curves that are used as sides of curved mesh elements with known coordinates. \tableofcontents \section{Motivation} Consider the points $(x, y) = (0, 5), (1, 9), (4, 14)$ along the curved edge in Figure~\ref{fig:curved-element-p-is-1}. Given three constraints, we'd like to be able to fit a parabola to those points. However on closer inspection, we consider that a parabola is defined by a focus (two degrees of freedom) and a directrix line (two d.o.f.). Thus determining a unique parabola is in general impossible (since the system is underdetermined). \begin{center} \begin{figure} \centering \includegraphics[scale=0.3]{writeup_image00.png} \caption{Curved Mesh Element} \label{fig:curved-element-p-is-1} \end{figure} \end{center} \subsection{Enforced Uniqueness} Instead of fitting a parabola in space, we fit each coordinate as a parabola with respect to a shared parameter $$s$$: \begin{align*} x &= A_2 s^2 + A_1 s + A_0 \\ y &= B_2 s^2 + B_1 s + B_0 \end{align*} Since we think of our points geometrically as the beginning, midpoint and end, we choose $$s = 0, \frac{1}{2}, 1$$. Then solving for the coefficients of the $$x$$-parameterization becomes $\left[ \begin{array}{c c c} 1 & 0 & 0 \\ 1 & \frac{1}{2} & \frac{1}{4} \\ 1 & 1 & 1 \end{array}\right] \left[ \begin{array}{c} A_0 \\ A_1 \\ A_2 \end{array}\right] = \left[ \begin{array}{c} 0 \\ 1 \\ 4 \end{array}\right]$ We recognize a Vandermonde matrix and know it must have a unique solution since we chose unique $$s$$-values. Thus by parameterizing $$x$$ and $$y$$ on a coordinate-wise quadratic-curve (not necessarily a parabola), \fbox{we guarantee a unique set of coefficients} to fit our three datapoints. \section{Example} \subsection{Solving the System from the Motivating Example} To find the parameters of our curve $$\gamma(s)$$ we solve the system $\left[ \begin{array}{c c c} 1 & 0 & 0 \\ 1 & \frac{1}{2} & \frac{1}{4} \\ 1 & 1 & 1 \end{array}\right] \left[ \begin{array}{c c} A_0 & B_0 \\ A_1 & B_1 \\ A_2 & B_2 \end{array}\right] = \left[ \begin{array}{c c} x_0 & y_0 \\ x_1 & y_1 \\ x_2 & y_2 \end{array}\right]$ This can be solved as $\left[ \begin{array}{c c} A_0 & B_0 \\ A_1 & B_1 \\ A_2 & B_2 \end{array}\right] = \left[ \begin{array}{c c c} 1 & 0 & 0 \\ -3 & 4 & -1 \\ 2 & -4 & 2 \end{array}\right] \left[ \begin{array}{c c} x_0 & y_0 \\ x_1 & y_1 \\ x_2 & y_2 \end{array}\right]$ So with our curve, we find $x = 4 s^2, \quad y = 2 s^2 + 7 s + 5.$ \subsection{Classification} Our goal was a parabola, but we don't really know what we have. In order to figure this out, we implicitize'' the curve (in layman's terms, we eliminate the $$s$$). Luckily, the \textbf{resultant}, an object used quite frequently in elimination theory, can lend us a hand. The polynomial $f(x, y) = \operatorname{Res}_s\left(x(s) - x, y(s) - y\right)$ is equal to zero precisely when \textbf{there exists} $$s$$\footnote{in the algebraic closure of $$\mathbf{R}$$, i.e. $$\mathbf{C}$$} such that $x(s) - x = y(s) - y = 0.$ Thus $$f(x, y) = 0$$ gives a level curve in $$\mathbf{R}^2$$ that contains\footnote{We say contains'' since limiting to $$s \in \mathbf{R}$$ may not cover all points in $$\mathbf{R}^2$$ with $$f(x, y) = 0$$} $\gamma(s) = (x(s), y(s)).$ Computing the resultant (via the determinant of a Sylvester matrix) gives $f(x, y) = \det\left[ \begin{array}{c c c c} 4 & 0 & -x & 0 \\ 0 & 4 & 0 & -x \\ 2 & 7 & 5 - y & 0 \\ 0 & 2 & 7 & 5 - y \end{array}\right] = 4(x^2 - 4xy + 4y^2 - 29x - 40y + 100)$ In general, we may not be able to classify generic curves, but this specifically is a conic section. Such curves are \textbf{fully classified} by their discriminant, and here our discriminant $(-16)^2 - 4(4)(16) = 0$ tells us our curve is actually a \textbf{parabola}. \section{Degree Two: General Case} The general question of classifying \begin{align*} x &= x(s) = A_2 s^2 + A_1 s + A_0 \\ y &= y(s) = B_2 s^2 + B_1 s + B_0 \end{align*} can again be done by using the resultant to eliminate $$s$$. Before, $$f(x, y) \in \mathbf{R}\left[x, y\right]$$. But now our coefficients will come from the ring $$R = \mathbf{R}\left[A_2, A_1, A_0, B_2, B_1, B_0\right]$$, i.e. $$f \in R\left[x, y\right]$$. \subsection{Coefficients Computation} We want to compute the coefficients of $f(x, y) = \operatorname{Res}_s\left(x(s) - x, y(s) - y\right) = \det(M)$ for the Sylvester Matrix $M = M(x, y) = \left[ \begin{array}{c c c c} A_2 & A_1 & A_0 - x & 0 \\ 0 & A_2 & A_1 & A_0 - x \\ B_2 & B_1 & B_0 - y & 0 \\ 0 & B_2 & B_1 & B_0 - y \end{array}\right].$ This also gives us a quick way of computing $$f(x, y)$$ for a known $$(x, y)$$ without computing the coefficients of $$f$$ itself. To actually compute $$f(x, y)$$, one can consider the columns including $$x, y$$ values as a sum of three vectors and use the multilinearity property of the determinant. Writing $$M(0, 0)$$ as columns $M(0, 0) = \left[ \begin{array}{c c c c} v_1 & v_2 & v_3 & v_4 \end{array}\right]$ we have $\det\left(M(x, y)\right) = \det\left(v_1, v_2, v_3 - x b_1 - y b_3, v_4 - x b_2 - y b_4\right)$ where the $$b_j$$ are the canonical basis vectors of $$\mathbf{R}^4$$. We can expand each of the $$3$$ terms in the third and fourth components (via multilinearity) to get a total of $$9$$ determinants. Grouping terms we find: %% A2, A1, A0, B2, B1, B0 = sympy.symbols('A2, A1, A0, B2, B1, B0') %% v1 = sympy.Matrix([[A2, 0, B2, 0]]).T %% v2 = sympy.Matrix([[A1, A2, B1, B2]]).T %% v3 = sympy.Matrix([[A0, A1, B0, B1]]).T %% v4 = sympy.Matrix([[0, A0, 0, B0]]).T %% def cols_to_mat(*cols): %% n = len(cols) %% M = sympy.zeros(n) %% for i, col in enumerate(cols): %% M[:, i] = col %% return M %% b1 = sympy.Matrix([[1, 0, 0, 0]]).T %% b2 = sympy.Matrix([[0, 1, 0, 0]]).T %% b3 = sympy.Matrix([[0, 0, 1, 0]]).T %% b4 = sympy.Matrix([[0, 0, 0, 1]]).T %% cols_to_mat(v1, v2, v3, v4).det() %% cols_to_mat(v1, v2, -b1, v4).det() + cols_to_mat(v1, v2, v3, -b2).det() %% cols_to_mat(v1, v2, -b3, v4).det() + cols_to_mat(v1, v2, v3, -b4).det() %% cols_to_mat(v1, v2, -b1, -b2).det() %% cols_to_mat(v1, v2, -b3, -b2).det() + cols_to_mat(v1, v2, -b1, -b4).det() %% cols_to_mat(v1, v2, -b3, -b4).det() \begin{align*} \text{Const}\left(f(x, y)\right) &= \det\left(v_1, v_2, v_3, v_4\right) \\ &= \left(A_2 B_0 - A_0 B_2\right)^2 - \left(A_1 B_0 - A_0 B_1\right)\left( A_2 B_1 - A_1 B_2\right) \\ \text{Coeff}_{x}\left(f(x, y)\right) &= \det\left(v_1, v_2, -b_1, v_4\right) + \det\left(v_1, v_2, v_3, -b_2\right) \\ &= - A_2 B_1^2 + A_1 B_1 B_2 + 2 B_0 A_2 B_2 - 2 A_0 B_2^2 \\ \text{Coeff}_{y}\left(f(x, y)\right) &= \det\left(v_1, v_2, -b_3, v_4\right) + \det\left(v_1, v_2, v_3, -b_4\right) \\ &= - B_2 A_1^2 + B_1 A_1 A_2 + 2 A_0 A_2 B_2 - 2 B_0 A_2^2 \\ \text{Coeff}_{x^2}\left(f(x, y)\right) &= \det\left(v_1, v_2, -b_1, -b_2\right) \\ &= B_2^2 \\ \text{Coeff}_{xy}\left(f(x, y)\right) &= \det\left(v_1, v_2, -b_3, -b_2\right) + \det\left(v_1, v_2, -b_1, -b_4\right) \\ &= -2 A_2 B_2 \\ \text{Coeff}_{y^2}\left(f(x, y)\right) &= \det\left(v_1, v_2, -b_3, -b_4\right) \\ &= A_2^2 \end{align*} In particular, we find we always have discriminant $\left(-2 A_2 B_2\right)^2 - 4\left(B_2^2\right)\left(A_2^2\right) = 0.$ Hence when $$n = 2$$, we \textbf{always} have a \textbf{parabola}\footnote{ unless $$A_2 = B_2 = 0$$, but that situation effectively amounts to a degree one parameterization}. \section{Degree Three Examples}\label{degree3} If we were to compute the general coefficients for degree three, we would have more terms than can fit on this page. Instead, we cover four examples which showcase the different types of stationary points that an implicitized curve can exhibit. %% See stationary_pt_test.py, case3() \subsection{Cubic}\label{degree3-cubic} Given \begin{align*} x = x(s) &= s^3 + s^2 + s + 1 \\ y = y(s) &= 2s^3 + 2s^2 + 1 \end{align*} we have \begin{align*} f(x, y) &= \det\left[ \begin{array}{c c c c c c} 1 & 1 & 1 & 1 - x & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 - x & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 - x \\ 2 & 2 & 0 & 1 - y & 0 & 0 \\ 0 & 2 & 2 & 0 & 1 - y & 0 \\ 0 & 0 & 2 & 2 & 0 & 1 - y \end{array}\right] \\ &= 8 x^3 - 12 x^2 y + 6 x y^2 - y^3 - 4 x^2 + 4 x y - y^2 - 2 x - 3 y + 5 \\ &= -(y - 2x)^3 - (y - 2x)^2 - 2x - 3y + 5. \end{align*} To find the stationary points where $f = f_x = f_y = 0$ we first find where $$f_x = f_y = 0$$. Using the resultant to remove $$x$$: $\operatorname{Res}_x\left(f_x, f_y\right) = 9216$ thus there are no solutions. Hence $$f(x, y)$$ has no stationary points. Via the coordinate transformation $x_1 = y - 2x, \quad y_1 = - 4y$ our curve becomes $0 = -f = x_1^3 + x_1^2 - x_1 + 4y - 5 \Longrightarrow y_1 = x_1^3 + x_1^2 - x_1 - 5.$ Thus we take that cubic and transform it $\left[ \begin{array}{c c} -2 & 1 \\ 0 & -4 \end{array}\right] \left[ \begin{array}{c} x \\ y \end{array}\right] = \left[ \begin{array}{c} x_1 \\ y_1 \end{array}\right] \Longleftrightarrow -\frac{1}{8} \left[ \begin{array}{c c} 4 & 1 \\ 0 & 2 \end{array}\right] \left[ \begin{array}{c} x_1 \\ y_1 \end{array}\right] = \left[ \begin{array}{c} x \\ y \end{array}\right]$ via two rotations and a stretch (via the SVD): $-\frac{1}{8} \left[ \begin{array}{c c} 4 & 1 \\ 0 & 2 \end{array}\right] \approx \left[ \begin{array}{c c} 0.9889 & -0.1487 \\ 0.1487 & 0.9889\end{array}\right] \left[ \begin{array}{c c} 0.5199 & 0 \\ 0 & 0.2404\end{array}\right] \left[ \begin{array}{c c} -0.9510 & 0.3092 \\ -0.3092 & -0.9510 \end{array}\right]^T.$ %% See stationary_pt_test.py, case4() \subsection{Isolated Point}\label{degree3-isolated} Given \begin{align*} x = x(s) &= s^3 + s^2 + s + 1 \\ y = y(s) &= 2s^3 + 3s^2 + 1 \end{align*} we can show \begin{align*} f(x, y) &= 8 x^3 - 12 x^2 y + 6 x y^2 - y^3 + 9 x^2 - 2 y^2 - 24 x + 16 \\ &= (2x - y)^3 + 9 x^2 - 2 y^2 - 24 x + 16. \end{align*} To find stationary points, we again use the resultants: \begin{align*} \operatorname{Res}_x\left(f_x, f_y\right) &= 144(y + 12)(y + 48) \\ \operatorname{Res}_y\left(f_x, f_y\right) &= 36(x + 4)(x + 20) \end{align*} Of these four choices (two each for $$x, y$$), only $$f(-20, -48) = 0$$. Solving \begin{align*} x(s) = x &= -20 \Longrightarrow s \in \left\{-3, 1 \pm i \sqrt{6} \right\} \\ y(s) = y &= -48 \Longrightarrow s \in \left\{-\frac{7}{2}, 1 \pm i \sqrt{6} \right\} \end{align*} so we see $(x, y) = (-20, -48) \Longleftrightarrow s = 1 \pm i \sqrt{6}.$ In particular, this point occurs on $$f(x, y)$$ as an \textbf{isolated point}, but does not occur on our real parameterized curve $$\gamma(s) = (x(s), y(s))$$. Notice that the Hessian at this point is $H = \left[ \begin{array}{c c} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{array}\right] = \left[ \begin{array}{c c} 210 & -96 \\ -96 & 44 \end{array}\right]$ with $$\det(H) = 24$$ hence $$H$$ is positive definite which indicates that $$(-20, -48)$$ is a relative minimum. %% See stationary_pt_test.py, case8() \subsection{Cusp}\label{degree3-cusp} Given \begin{align*} x = x(s) &= 2s^3 - 3s^2 - 12s \\ y = y(s) &= -s^3 + 2s^2 + 4s \end{align*} we can show \begin{align*} f(x, y) &= -x^3 - 6 x^2 y - 12 x y^2 - 8 y^3 + 4 x^2 + 24 x y + 33 y^2 + 16 x + 48 y \\ &= -(x + 2y)^3 + 4 x^2 + 24 x y + 33 y^2 + 16 x + 48 y. \end{align*} To find stationary points, we again use the resultants: \begin{align*} \operatorname{Res}_x\left(f_x, f_y\right) &= 36(y - 8)^2 \\ \operatorname{Res}_y\left(f_x, f_y\right) &= 144(x + 20)^2 \end{align*} This lone point also satisfies $$f(-20, 8) = 0$$. Solving \begin{align*} x(s) = x &= -20 \Longrightarrow s \in \left\{-\frac{5}{2}, 2, 2 \right\} \\ y(s) = y &= 8 \Longrightarrow s \in \left\{-2, 2, 2\right\} \end{align*} so we see $(x, y) = (-20, 8) \Longleftrightarrow s = 2 \text{ (double root)}.$ Since $$x'(s) = 6(s - 2)(s + 1)$$ and $$y'(s) = -(s - 2)(3s + 2)$$, on our path $$\gamma(s)$$ we have $\left.\frac{d\gamma}{ds}\right|_{s=2} = (0, 0).$ Hence no tangent can be defined at this point, so it is a \textbf{cusp}. The Hessian at this point is $H = \left[ \begin{array}{c c} 32 & 72 \\ 72 & 162 \end{array}\right] = \left[ \begin{array}{c c} 4 & -9 \\ 9 & 4 \end{array}\right] \left[ \begin{array}{c c} 194 & \\ & 0 \end{array}\right] \left[ \begin{array}{c c} 4 & -9 \\ 9 & 4 \end{array}\right]^{-1}.$ %% See stationary_pt_test.py, case6() \subsection{Self-Crossing}\label{degree3-self-crossing} Given \begin{align*} x = x(s) &= -2s^3 - 2s^2 \\ y = y(s) &= -s^3 + s^2 + s + 1 \end{align*} we can show \begin{align*} f(x, y) &= -x^3 + 6 x^2 y - 12 x y^2 + 8 y^3 - 20 x^2 + 24 x y - 32 y^2 - 16 x + 40 y - 16 \\ &= (2y - x)^3 - 20 x^2 + 24 x y - 32 y^2 - 16 x + 40 y - 16 \end{align*} To find stationary points, we again use the resultants: \begin{align*} \operatorname{Res}_x\left(f_x, f_y\right) &= 192(8y - 11)(96y - 97) \\ \operatorname{Res}_y\left(f_x, f_y\right) &= 3072(4x + 1)(48x + 7) \end{align*} Of these four choices (two each for $$x, y$$), only $$f\left(-\frac{1}{4}, \frac{11}{8}\right) = 0$$. Solving \begin{align*} x(s) = x &= -\frac{1}{4} \Longrightarrow s \in \left\{-\frac{1}{2}, \frac{-1 \pm \sqrt{5}}{4}\right\} \\ y(s) = y &= \frac{11}{8} \Longrightarrow s \in \left\{\frac{3}{2}, \frac{-1 \pm \sqrt{5}}{4}\right\} \end{align*} so we see $(x, y) = \left(-\frac{1}{4}, \frac{11}{8}\right) \Longleftrightarrow s = \frac{-1 \pm \sqrt{5}}{4}.$ Since we have two valid real inputs which produce the same point, this point must be a \textbf{self-crossing} for $$\gamma(s)$$. At these points we have $\left.\frac{d\gamma}{ds}\right|_{s=\frac{-1 \pm \sqrt{5}}{4}} = \left( \frac{-5 \mp \sqrt{5}}{4}, \frac{-5 \pm 7 \sqrt{5}}{8}\right) \Longrightarrow \left.\frac{dy}{dx}\right|_{s=\frac{-1 \pm \sqrt{5}}{4}} = \frac{3}{2} \mp \sqrt{5}.$ So we see two things. First, at the stationary point, the derivative of the tangent line along $$\gamma(s)$$ can be defined. However, trying to solve for $$s$$ in $$\gamma(s) = \left(-\frac{1}{4}, \frac{11}{8}\right)$$ cannot be done uniquely. This is exactly equivalent to a failure in the implicit function theorem. The Hessian at this point is $H = \left[ \begin{array}{c c} -22 & -12 \\ -12 & 8 \end{array}\right]$ with $$\det(H) = -320$$, hence it is indefinite and $$\left(-\frac{1}{4}, \frac{11}{8}\right)$$ must be a \textbf{saddle point} on the graph of $$z = f(x, y)$$. %% FUN 3D PLOT %% x, y, s, f_symb = sympy.symbols('x, y, s, f') %% x_s, y_s, f, solns = case6(x, y, s, f_symb) %% s_vals = np.linspace(-1, 0.5, 1000) %% x_vals = eval(str(x_s), {}, {'s': s_vals}) %% y_vals = eval(str(y_s), {}, {'s': s_vals}) %% plt.plot(x_vals, y_vals) %% plt.show() %% from mpl_toolkits.mplot3d import Axes3D %% X = np.linspace(-0.8, 0.1, 201) %% Y = np.linspace(0.8, 2.0, 201) %% X, Y = np.meshgrid(X, Y) %% Z = eval(str(f), {}, {'x': X, 'y': Y}) %% fig = plt.figure() %% ax = fig.gca(projection='3d') %% from matplotlib import cm %% surf = ax.plot_surface(X, Y, Z, %% rstride=1, cstride=1, cmap=cm.coolwarm, %% linewidth=0, antialiased=False) %% Z2 = np.zeros(X.shape) %% surf2 = ax.plot_surface(X, Y, Z2, %% rstride=1, cstride=1, cmap=cm.coolwarm, %% linewidth=0, antialiased=False) %% ax.set_zlim(-8.2, 6.1) %% ax.view_init(elev=0, azim=30) %% plt.show() \section{Classifying Without Implicitizing} In the general case we have \begin{align*} x(s) &= A_d s^d + \cdots \\ y(s) &= B_e s^e + \cdots \end{align*} where the degrees $$d, e$$ are non-negative integers. We assume that one of $$d, e$$ is greater than $$1$$. If $$d, e < 2$$ we simply have lines or points and these are quite easy to classify (lines have no stationary points). Consider a stationary point $$(x_0, y_0)$$ (assuming one exists). By definition of the resultant we have $F_1(x) = f(x, y_0) = (-1)^{de} B_e^d \prod_{\sigma \, : \, y\left(\sigma\right) = y_0} \left[x\left(\sigma\right) - x\right]$ where the $$\sigma$$ are roots (with multiplicity) of $$y(s) - y_0 = 0$$. We know that for our stationary point $F_1(x_0) = f(x_0, y_0) = 0, \quad F_1'(x_0) = f_x(x_0, y_0) = 0$ hence $$F_1(x)$$ has (at least) a double\footnote{WLOG assume $$e \geq 2$$ since we could just swap $$x, y$$ if need be} root at $$x = x_0$$. This means that (at least) two roots (counting multiplicity) of $$y(s) - y_0$$ produce $x\left(\sigma\right) = x_0, \; x\left(\sigma'\right) = x_0, \; y\left(\sigma\right) = y_0, \; y\left(\sigma'\right) = y_0.$ In other words, the stationary points occur at places where the parameterization $$\gamma(s) = (x(s), y(s))$$ is non-unique. This makes sense; we know that stationary points are places where the implicit function theorem fails for both $$x$$ and $$y$$ since $$\nabla f = 0$$. In order to find values $$s \in \mathbf{C}$$ where $$\gamma(s)$$ is non-unique we define $X(s, t) = \frac{x(s) - x(t)}{s - t}, \quad Y(s, t) = \frac{y(s) - y(t)}{s - t}.$ Setting $$X(s, t) = Y(s, t) = 0$$ gives non-trivial\footnote{$$X(s, t) = 0$$ for a fixed $$t$$ gives roots that are functions of $$s$$. In our definition of $$X(s, t)$$ we divided by $$s - t$$ to eliminate the trivial root function $$r(s) = s$$. Taylor's Theorem says $$x(s) = x(t) + (s - t) x'(t) + (s - t)^2 x''(t) / 2 + \cdots$$ so unless $$x'(t) \equiv 0 \Longleftrightarrow x(t) \equiv C$$ we know that $$(s - t)^2$$ does not divide $$x(s) - x(t)$$ for all values of $$t$$ hence the root function $$r(s) = s$$ occurs exactly once among the roots of $$x(s) - x(t)$$.} pairs $$(s, t)$$ where $$x(s) = x(t)$$ and $$y(s) = y(t)$$. By construction we have the symmetry $$X(s, t) = X(t, s)$$ and $$Y(s, t) = Y(t, s)$$. Due to the symmetry, the polynomials $I(s) = I_1(s) = \operatorname{Res}_t\left(X(s, t), Y(s, t)\right) \quad \text{and} \quad I_2(t) = \operatorname{Res}_s\left(X(s, t), Y(s, t)\right)$ must be identical. So solving one of them can show where stationary points occur (or show that none do). \subsection{Cubic} Re-visiting the example from~\ref{degree3-cubic}, we have \begin{align*} X(s, t) &= (s^2 + s t + t^2) + (s + t) + 1 \\ Y(s, t) &= 2 (s^2 + s t + t^2) + 2(s + t) \\ \operatorname{Res}_t\left(X(s, t), Y(s, t)\right) &= 4 \end{align*} This confirms the absence of a stationary point. However, if we convert to homogeneous coordinates \begin{align*} x(S, T, U) &= (S^2 + S T + T^2) + (S + T) U + U^2 \\ y(S, T, U) &= 2 (S^2 + S T + T^2) + 2(S + T) U \\ \operatorname{Res}_S\left(x, y\right) &= 4 U^4 \\ \operatorname{Res}_T\left(x, y\right) &= 4 U^4 \\ \operatorname{Res}_U\left(x, y\right) &= 4\left(S^2 + ST + T^2\right)^2 \end{align*} This has two solutions (both points at infinity) $$\left(1:\omega:0\right)$$ and $$\left(\omega:1:0\right)$$ where $$\omega$$ is one of the roots of $\omega^2 + \omega + 1 = 0.$ \subsection{Isolated Point} Re-visiting the example from~\ref{degree3-isolated}, we have \begin{align*} X(s, t) &= (s^2 + s t + t^2) + (s + t) + 1 \\ Y(s, t) &= 2 (s^2 + s t + t^2) + 3 (s + t) \\ \operatorname{Res}_t\left(X(s, t), Y(s, t)\right) &= (s - 1)^2 + 6 \end{align*} This confirms the stationary point at $$s = 1 \pm i \sqrt{6}$$ and $X\left(1 \pm i \sqrt{6}, t\right) = (t + 3)\left(t - \left[1 \mp i \sqrt{6}\right]\right), \qquad Y\left(1 \pm i \sqrt{6}, t\right) = (2t + 7)\left(t - \left[1 \mp i \sqrt{6}\right]\right).$ \subsection{Cusp} Re-visiting the example from~\ref{degree3-cusp}, we have \begin{align*} X(s, t) &= 2 (s^2 + s t + t^2) - 3 (s + t) - 12 \\ Y(s, t) &= -(s^2 + s t + t^2) + 2 (s + t) + 4 \\ \operatorname{Res}_t\left(X(s, t), Y(s, t)\right) &= (s - 2)^2 \end{align*} This confirms the stationary point at $$s = 2$$ and $X(2, t) = (t - 2)(2t + 5), \qquad Y(2, t) = -(t - 2)(t + 2).$ \subsection{Self-Crossing} Re-visiting the example from~\ref{degree3-self-crossing}, we have \begin{align*} X(s, t) &= -2 (s^2 + s t + t^2) - 2(s + t) \\ Y(s, t) &= -(s^2 + s t + t^2) + (s + t) + 1 \\ \operatorname{Res}_t\left(X(s, t), Y(s, t)\right) &= (4 s + 1)^2 - 5 \end{align*} This confirms the stationary point at $$s = \frac{-1 \pm \sqrt{5}}{4}$$ and $X\left(\frac{-1 \pm \sqrt{5}}{4}, t\right) = -(2t + 1)\left(t - \left[\frac{-1 \mp \sqrt{5}}{4}\right]\right), \qquad Y\left(\frac{-1 \pm \sqrt{5}}{4}, t\right) = -\left(t - \frac{3}{2}\right)\left(t - \left[\frac{-1 \mp \sqrt{5}}{4}\right]\right).$ \subsection{Disjoint Pieces of Implicit Curve} Since polynomials $$x(s), y(s)$$ are continuous, the curve $$\gamma\left(\mathbf{R}\right)$$ must be continuous. We'd like to be able to show that the only points that can be produced by $$s \in \mathbf{C} - \mathbf{R}$$ are \textbf{isolated points}. In order to have \textbf{another} curve \textbf{disjoint} from $$\gamma\left(\mathbf{R}\right)$$, we'd need a set of inputs $$s \in \mathbf{C} - \mathbf{R}$$ which produce that curve. We'd like to show that for such $$s = a + bi$$ with $$b \neq 0$$, there are finitely many pairs $$(a, b)$$ such that $\operatorname{Im}\left(x(a + bi)\right) = \operatorname{Im}\left(y(a + bi)\right) = 0.$ Unfortunately this is easy to show false. The curve $$x(s) = s^2, y(s) = s^4$$ is implicitized as $$f(x, y) = \left(y - x^2\right)^2$$. However $$\gamma\left(\mathbf{R}\right)$$ is only the right half of the parabola while $$\gamma\left(i \mathbf{R}\right)$$ is the left half. But for this example since $$f(x, y)$$ is not square-free we always have $$f = 0 \Longrightarrow f_x = f_y = 0$$ hence every point is a stationary point. To see this in another way note that $$X(s, t) = s + t$$ divides $$Y(s, t) = X(s, t) (s^2 + t^2)$$ hence forces $$I(s) \equiv 0$$. From the Wikipedia \href{https://en.wikipedia.org/wiki/Algebraic_curve#Singular_points}{page} on algebraic curves: \begin{displayquote} The singular points of a curve defined by a polynomial $$f(x, y)$$ are the solutions of the system of equations: $f(x, y) = f_x(x, y) = f_y(x, y) = 0.$ This implies that the number of singular points is finite as long as $$f(x, y)$$ is square-free. \end{displayquote} The page goes on to count the number of possible singular points and says B\'{e}zout's theorem justifies this argument, but the theorem can only be applied when $$f(x, y)$$ is square-free. Note that if we can factor $f(x, y) = A(x, y) B(x, y)$ with $$\gcd\left(A, B\right) = 1$$. Let $$g(x, y) = \gcd\left(f, f_x\right)$$, then since $$g \mid f$$, we know $$g(x, y) = A_g(x, y) B_g(x, y)$$ for $$A_g \mid A$$ and $$B_g \mid B$$ (since polynomial rings are UFDs). Since $$\gcd(B, A_g) = 1$$ and $$A_g \mid A$$ we must have $0 \equiv f_x \equiv A_x B + A B_x \equiv A_x B \bmod{A_g} \Longrightarrow A_x \equiv 0 \bmod{A_g}.$ Thus we see that $$A_g \mid \gcd\left(A, A_x\right)$$ and $$B_g \mid \gcd\left(B, B_x\right)$$. Since $$\gcd\left(A, A_x\right) \mid f_x$$ as well we see that $$\gcd\left(A, A_x\right) \mid A_g$$ hence $\gcd\left(f, f_x\right) = \gcd\left(A, A_x\right) \gcd\left(B, B_x\right).$ When $$f(x, y) = p(x, y)^n$$ the power of an irreducible, we have WLOG $$B(x, y) = 1$$. Since $$f_x = n p^{n - 1} p_x$$ we see that $$\gcd(f, f_x) = p^{n - 1} \cdot \gcd(p, p_x) = p^{n - 1}$$ (since $$\deg p_x < \deg p$$ and $$p$$ is irreducible, $$\gcd(p, p_x) = 1$$). Thus, when we write $$f$$ as the power of irreducibles $f = p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k} \Longrightarrow \gcd(f, f_x) = p_1^{n_1 - 1} p_2^{n_2 - 1} \cdots p_k^{n_k - 1}.$ In particular, if $$f$$ is square-free (i.e. $$n_1 = n_2 = \cdots = n_k = 1$$) then $$\boxed{\gcd(f, f_x) = 1}$$. \section{Parameterizing an Algebraic Curve} An algebraic curve admits a parameterization if and only if it has genus zero (reference needed). \subsection{Isolated Point} Re-(re-)visiting the example from~\ref{degree3-isolated} %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> f = (2 * x - y)**3 + 9 * x**2 - 2 * y**2 - 24 * x + 16 %% >>> sympy.resultant(f.diff(x), f.diff(y), y).factor() %% 36*(x + 4)*(x + 20) %% >>> sympy.resultant(f.diff(x), f.diff(y), x).factor() %% 144*(y + 12)*(y + 48) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: -4, y: -12}) %% Matrix([[32, 0, 0, 114]]) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: -4, y: -48}) %% Matrix([[59648, 9504, -4608, 978]]) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: -20, y: -12}) %% Matrix([[-18144, 4320, -2304, -654]]) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: -20, y: -48}) %% Matrix([[0, 0, 0, 210]]) $f(x, y) = (2x - y)^3 + 9 x^2 - 2 y^2 - 24 x + 16$ we have already seen a unique singular point $f(-20, -48) = f_x(-20, -48) = f_y(-20, -48) = 0.$ Since $$f_{xx}(-20, -48) = 210$$, this is only a double point, hence the genus for our degree $$d = 3$$ curve is $g = \binom{d - 1}{2} - \binom{2}{2} = 0.$ \subsection{Cusp} Re-(re-)visiting the example from~\ref{degree3-cusp} %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> f = -(x + 2 * y)**3 + 4 * x**2 + 24 * x * y + 33 * y**2 + 16 * x + 48 * y %% >>> sympy.resultant(f.diff(x), f.diff(y), y).factor() %% 144*(x + 20)**2 %% >>> sympy.resultant(f.diff(x), f.diff(y), x).factor() %% 36*(y - 8)**2 %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: -20, y: 8}) %% Matrix([[0, 0, 0, 32]]) $f(x, y) = -(x + 2y)^3 + 4 x^2 + 24 x y + 33 y^2 + 16 x + 48 y$ we have already seen a unique singular point $f(-20, 8) = f_x(-20, 8) = f_y(-20, 8) = 0.$ Since $$f_{xx}(-20, 8) = 32$$, this is only a double point, hence the genus for our degree $$d = 3$$ curve is $g = \binom{d - 1}{2} - \binom{2}{2} = 0.$ \subsection{Self-Crossing} Re-(re-)visiting the example from~\ref{degree3-self-crossing} %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> f = (2 * y - x)**3 - 20 * x**2 + 24 * x * y - 32 * y**2 - 16 * x + 40 * y - 16 %% >>> sympy.resultant(f.diff(x), f.diff(y), y).factor() %% 3072*(4*x + 1)*(48*x + 7) %% >>> sympy.resultant(f.diff(x), f.diff(y), x).factor() %% 192*(8*y - 11)*(96*y - 97) %% >>> x1 = sympy.Rational(-1, 4) %% >>> x2 = sympy.Rational(-7, 48) %% >>> y1 = sympy.Rational(11, 8) %% >>> y2 = sympy.Rational(97, 96) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: x1, y: y2}) %% Matrix([[15925/110592, 2135/768, 35/128, -211/8]]) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: x2, y: y1}) %% Matrix([[-13325/110592, -595/256, -455/384, -181/8]]) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: x2, y: y2}) %% Matrix([[125/432, 0, 0, -27]]) %% >>> sympy.Matrix([[f, f.diff(x), f.diff(y), f.diff(x, 2)]]).subs({x: x1, y: y1}) %% Matrix([[0, 0, 0, -22]]) $f(x, y) = (2y - x)^3 - 20 x^2 + 24 x y - 32 y^2 - 16 x + 40 y - 16$ we have already seen a unique singular point $f\left(-\frac{1}{4}, \frac{11}{8}\right) = f_x\left(-\frac{1}{4}, \frac{11}{8}\right) = f_y\left(-\frac{1}{4}, \frac{11}{8}\right) = 0.$ Since $$f_{xx}\left(-\frac{1}{4}, \frac{11}{8}\right) = 22$$, this is only a double point, hence the genus for our degree $$d = 3$$ curve is $g = \binom{d - 1}{2} - \binom{2}{2} = 0.$ \subsection{Cubic} Re-(re-)visiting the example from~\ref{degree3-cubic} %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> f = -(y - 2 * x)**3 - (y - 2 * x)**2 - 2 * x - 3 * y + 5 %% >>> sympy.resultant(f.diff(x), f.diff(y), y).factor() %% 576 %% >>> X, Y, Z = sympy.symbols('X, Y, Z') %% >>> g = (f.subs({x: X / Z, y: Y / Z}) * Z**3).factor() %% >>> g_XY = sympy.resultant(g.diff(X), g.diff(Y), Z).factor() %% >>> g_XY %% 576*(2*X - Y)**4 %% >>> M = sympy.Matrix([[g, g.diff(X), g.diff(Y), g.diff(Z)]]) %% >>> sympy.Matrix([map(sympy.factor, M.subs({Y: 2 * X}))]) %% Matrix([[-Z**2*(8*X - 5*Z), -2*Z**2, -3*Z**2, -Z*(16*X - 15*Z)]]) %% >>> M.subs({Y: 2 * X, Z: 0}) %% Matrix([[0, 0, 0, 0]]) %% >>> g.diff(Z, 2).subs({Y: 2 * X, Z: 0}) %% -16*X $f(x, y) = -(y - 2x)^3 - (y - 2x)^2 - 2x - 3y + 5$ we have already seen there is no singular point since $\gcd(f_x, f_y) = 1.$ This would seem to indicate that our degree $$d = 3$$ curve has genus $$g = \binom{d - 1}{2} > 0$$. However, we \textbf{know} that $$f(x, y)$$ can be parameterized (we constructed it by \textbf{starting} from a parameterization). This is because the double point is a point at infinity. To see this, we convert to a homogeneous $g(X, Y, Z) = Z^3 f\left(\frac{X}{Z}, \frac{Y}{Z}\right) = -(Y - 2X)^3 - (Y - 2X)^2 Z - 2X Z^2 - 3 Y Z^2 + 5 Z^3.$ Noting that $\operatorname{Res}_Z\left(g_X, g_Y\right) = 576 (2 X - Y)^4$ we search for our double points among \begin{align*} g(X, 2X, Z) &= Z^2 (5 Z - 8 X) \\ g_X(X, 2X, Z) &= -2 Z^2 \\ g_Y(X, 2X, Z) &= -3 Z^2 \\ g_Z(X, 2X, Z) &= Z (15 Z - 16 X) \end{align*} and we see that $$Z = 0$$. So, our double point is $$(1:2:0)$$. Luckily, it is not a triple point since $g_{ZZ}(1, 2, 0) = -16.$ Thus, our \text{double} point gives a genus $g = \binom{d - 1}{2} - \binom{2}{2} = 0.$ \subsection{Non-Example: Failure} All the previous examples %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> f = x**3 - x - y**2 %% >>> X, Y, Z = sympy.symbols('X, Y, Z') %% >>> g = (f.subs({x: X / Z, y: Y / Z}) * Z**3).factor() %% >>> g_XY = sympy.resultant(g.diff(X), g.diff(Y), Z).factor() %% >>> g_XY %% 12*X**2*Y**2 %% >>> g_XZ = sympy.resultant(g.diff(X), g.diff(Z), Z).factor() %% >>> g_XZ %% 12*X**4 - Y**4 %% >>> M = sympy.Matrix([[g, g.diff(X), g.diff(Y), g.diff(Z)]]) %% >>> M.subs({X: 0, Y: 0, Z: 1}) %% Matrix([[0, -1, 0, 0]]) we considered were from \textbf{existing} parameterizations. Instead, consider an elliptic curve: $f(x, y) = x^3 - x - y^2.$ To make sure we don't miss a singular point consider: $g(X, Y, Z) = Z^3 f\left(\frac{X}{Z}, \frac{Y}{Z}\right) = X^3 - X Z^2 - Y^2 Z.$ Noting that $\operatorname{Res}_Z\left(g_X, g_Y\right) = 12 X^2 Y^2 \quad \text{and} \quad \operatorname{Res}_Z\left(g_X, g_Z\right) = 12 X^4 - Y^4$ we must have $$X = Y = 0$$ at a double point. However $g(0, 0, 1) = g_Y(0, 0, 1) = g_Z(0, 0, 1) = 0 \quad \text{but} \quad g_X(0, 0, 1) = -1.$ Hence there are no singular points and the curve has genus $g = \binom{3 - 1}{2} = 1.$ \subsection{Generic Cubic} Consider %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> A, B, C, D = sympy.symbols('A, B, C, D') %% >>> f = A * x**3 + B * x**2 + C * x + D - y %% >>> X, Y, Z = sympy.symbols('X, Y, Z') %% >>> g = (f.subs({x: X / Z, y: Y / Z}) * Z**3).factor() %% >>> g_XY = sympy.resultant(g.diff(X), g.diff(Y), Z).factor() %% >>> g_XY %% 9*A**2*X**4 %% >>> M = sympy.Matrix([[g, g.diff(X), g.diff(Y), g.diff(Z)]]) %% >>> sympy.Matrix([map(sympy.factor, M.subs({X: 0}))]) %% Matrix([[Z**2*(D*Z - Y), C*Z**2, -Z**2, Z*(3*D*Z - 2*Y)]]) %% >>> g.diff(Z, 2).subs({X: 0, Y: 1, Z: 0}) %% -2 $f(x, y) = A x^3 + B x^2 + C x + D - y \Longleftrightarrow g(X, Y, Z) = A X^3 + B X^2 Z + C X Z^2 + D Z^3 - Y Z^2.$ Since $\operatorname{Res}_Z\left(g_X, g_Y\right) = 9 A^2 X^4$ we must have $$X = 0$$ which gives \begin{align*} g(0, Y, Z) &= Z^2 (D Z - Y) \\ g_X(0, Y, Z) &= C Z^2 \\ g_Y(0, Y, Z) &= -Z^2 \\ g_Z(0, Y, Z) &= Z (3 D Z - 2 Y). \end{align*} Hence this always has a singular point at $$(0:1:0)$$. It is a double (not triple) point since $$g_{ZZ}(0, 1, 0) = -2$$ thus it has a genus $g = \binom{3 - 1}{2} - \binom{2}{2} = 0.$ This can be confirmed by the simple parameterization $x(s) = s, \quad y(s) = A s^3 + B s^2 + C s + D.$ \subsection{Generic Quartic} Consider %% >>> import sympy %% >>> x, y = sympy.symbols('x, y') %% >>> A, B, C, D, E = sympy.symbols('A, B, C, D, E') %% >>> f = A * x**4 + B * x**3 + C * x**2 + D * x + E - y %% >>> X, Y, Z = sympy.symbols('X, Y, Z') %% >>> g = (f.subs({x: X / Z, y: Y / Z}) * Z**4).factor() %% >>> g_XY = sympy.resultant(g.diff(X), g.diff(Y), Z).factor() %% >>> g_XY %% 64*A**3*X**9 %% >>> M = sympy.Matrix([[g, g.diff(X), g.diff(Y), g.diff(Z)]]) %% >>> sympy.Matrix([map(sympy.factor, M.subs({X: 0}))]) %% Matrix([[Z**3*(E*Z - Y), D*Z**3, -Z**3, Z**2*(4*E*Z - 3*Y)]]) %% >>> import itertools %% >>> for v1, v2 in itertools.combinations_with_replacement([X, Y, Z], 2): %% ... val = g.diff(v1).diff(v2).subs({X: 0, Y: 1, Z: 0}) %% ... print((v1, v2, val)) %% ... %% (X, X, 0) %% (X, Y, 0) %% (X, Z, 0) %% (Y, Y, 0) %% (Y, Z, 0) %% (Z, Z, 0) %% >>> g.diff(Z, 3).subs({X: 0, Y: 1, Z: 0}) %% -6 \begin{align*} f(x, y) &= A x^4 + B x^3 + C x^2 + D x + E - y \\ \Longleftrightarrow g(X, Y, Z) &= A X^4 + B X^3 Z + C X^2 Z^2 + D X Z^3 + E Z^4 - Y Z^3. \end{align*} Since $\operatorname{Res}_Z\left(g_X, g_Y\right) = 64 A^3 X^9$ we must have $$X = 0$$ which gives $g_Y(0, Y, Z) = -Z^3$ hence (as with the generic cubic) there is a singular point at $$(0:1:0)$$. It is a triple (not quadruple) point since $g_{XX} = g_{XY} = g_{YY} = g_{YZ} = g_{ZZ} = g_{ZX} = 0 \quad \text{at} \quad (0:1:0)$ and $$g_{ZZZ}(0, 1, 0) = -6$$. Hence the genus for our degree $$d = 4$$ curve is $g = \binom{d - 1}{2} - \binom{3}{2} = 0.$ This can be confirmed by the simple parameterization $x(s) = s, \quad y(s) = A s^4 + B s^3 + C s^2 + D s + E.$ \end{document}