TITLE: Is the many-worlds interpretation really just an interpretation?
QUESTION [20 upvotes]: Is the many-worlds interpretation just a different interpretation to quantum mechanics or does it contain some different predictions?
In other words, is it possible theoretically to conduct an experiment that checks the many-worlds interpretation?

REPLY [2 votes]: I'm adding a second answer to clearly demonstrate two experiments that could, in principle, be performed which would give different results under the Copenhagen or Everettian (Many Worlds) theories. The first experiment is a Wigner's friend experiment and the second is a double slit experiment with a humans in a Hamster balls (credit for this latter experiment to a conversation with Jess Reidel).
Wigner's Friend
In the Wigner's friend experiment Wigner has a friend who goes into a room. The friend then prepares a qubit in a superposition state $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. The friend then measures the qubit. On the Copenhagen theory the state of the system collapses as soon as the friend performs the measurement. On the Everettian theory the friend becomes entangled with the qubit and the total state inside the room including the friend and qubit is an entangled superposition state. Wigner then opens the door and asks his friend what she observed.
Wigner's Friend with Qubits/Qutrits
To butter you up for the full Wigner's friend experiment first I'm going to describe the case in which Wigner's friend is just a qutrit, a three level system which will interact with the qubit. The three states are $|R\rangle$, which means the qutrit is "ready" to interact with the qubit, and $|0\rangle$ and $|1\rangle$.
The qubit starts in the state $|0\rangle$. It then undergoes a Hadamard gate to bring it to a superposition state. The Hadamard gate is given by
$$
U_H = \frac{1}{\sqrt{2}}\begin{pmatrix}
1 & 1\\
1 & -1
\end{pmatrix}
$$
The top (left) row (column) corresponds to qubit state $|0\rangle$ ($|1\rangle$). Note that $\hat{U}_H$ is it's own inverse.
The qubit and qutrit then now undergo an interaction described by unitary $\hat{U}_I$ which has the following effect on the joint system:
\begin{align}
|0R\rangle \rightarrow_{U_I} |00\rangle\\
|1R\rangle \rightarrow_{U_I} |11\rangle\\
\end{align}
An example of a unitary that could effect this transformation is
$$
U_I = \begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
$$
The rows (columns) correspond to the states $|0R\rangle, |1R\rangle, |01\rangle, |11\rangle, |00\rangle, |01\rangle$. The reader can confirm that this matrix is unitary and that it effects the transformation above. In fact, $U_I^{-1} = U_I^{\dagger} = U_I$.
This unitary acts on the joint initial state to give
$$
\hat{U} \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle) \otimes |r\rangle = \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle)
$$
The qubit and qutrit are in an entangled state. The qutrit is in $|0\rangle$ ($|1\rangle$) if the qubit is in $|0\rangle$ ($|1\rangle$).
When Wigner examines the qubit and the qutrit half the time he sees the qubit in $|0\rangle$ and the qutrit in $|0\rangle$ and the other half of the time he see the qubit in $|1\rangle$ and the qutrit in $|1\rangle$.
But now Wigner does a different experiment. First the qubit undergoes $\hat{U}_H$, then the qubit and qutrit undergo $\hat{U}_I$. But now, the qubit and qutrit undergo $\hat{U}_I^{-1}$ and the qubit undergoes $\hat{U}_H^{-1}$. This essentially reverses the previous dynamics. The state is reverted back to
\begin{align}
|0R\rangle
\end{align}
For this second experiment, every time Wigner looks at the qubit and qutrit he sees the qubit to be in state $|0\rangle$ and the qutrit to be in state $|R\rangle$.
Wigner's Friend is a Human
The Wigner's friend experiment is the exact same as above with the qutrit replaced by a human. The human has 3 effective states, some initial state $|R\rangle$, the state of having seen the qubit as 0: $|0\rangle$ and the state having seen the qubit as 1: $|1\rangle$. The "observation" the qubit by Wigner's friend is enacted by the unitary matrix $U_I$ describing the dynamics inside the room while Wigner's friend examines the qubit.
For the first experiment described above, we have the classic Wigner's friend experiment.
On the Everettian theory the final state of Wigner's friend and the qubit is
$$
\frac{1}{\sqrt{2}}(|11\rangle + |00\rangle)
$$
When Wigner opens the door, half the time he finds the qubit in $|0\rangle$ and his friend having observed the qubit in $|0\rangle$ and the other half he finds the qubit in $1\rangle$ and his friend having observed the qubit in $|1\rangle$. On this theory, we maintain that Wigner's friend was indeed in a macroscopic superposition of quantum states. An idea which is unsettling to some.
On the Copenhagen theory, if we put the Heisenberg cut below Wigner's friend's observation, then we have that Wigner's friend CANNOT be in a superposition state, and that the wavefunction collapses when Wigner's friend measures the qubit. In this case, 50% of the time Wigner's friend is in the state $|00\rangle$ along with the qubit and $|11\rangle$ the other 50% of the time.
If we put the Heisenberg cut below Wigner's observation, but above Wigner's friend's observation, then, just like in the Everettian theory, Wigner's friend enters an entangled superposition state with the qubit and the quantum state only collapses when Wigner opens the room. This approach raises the major philosophical question of "what makes Wigner special that the wavefunction collapses when HE makes an observation but not when his friend makes an observation?"
All of this is fine. The 3 theories I have described (Everettian, Copenhagen 1 (low Heisenberg cut) and Copenhagen 2 (high Heisenberg cut)) all give the same prediction at the end of the day for what Wigner sees.
But now Wigner performs the second experiment in which the unitaries are time-reversed before his final measurement.
It is clear that on the Everettian theory (and the Copenhagen 2 theory) that Wigner will get the same exact results as he got with the qubit and qutrit. He will ALWAYS observe the qubit to be in state $|0\rangle$ at the end of the experiment. He will also always observe his friend to be back in the ready state.
But what would happen on the Copenhagen 1 theory? After $\hat{U}_H$ and $\hat{U}_I$ the system would be in state
$$
\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle$
$$
But, because the system collapses during Wigner's friends measurement. The system is EITHER in $|00\rangle$ OR $|11\rangle$. Suppose the system is in $|00\rangle$. Now when the system undergoes $\hat{U}_I^{-1}$ the resultant state will be
$$
\hat{U}_I^{-1}|00\rangle = |0R\rangle.
$$
This is fine and makes sense. But when the inverse Hadamard acts on the qubit the final state is
$$
\hat{U}_H^{-1}|0R\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\otimes|R\rangle
$$
For the case where the state collapsed to $|11\rangle$ after Wigner's Friends measurment the final state would have been
$$
\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\otimes |R\rangle
$$
In this case Wigner will always see his friend in the state $|R\rangle$, but now 50% of the time he will find the qubit in state $|0\rangle$ and 50% of the time he will find the qubit in $|1\rangle$.
**Therefore Copenhagen 1 theory makes DIFFERENT PREDICTIONS about this experiment than the Everettian and Copenhagen 2 theories.
Double Slit - Humans in a Hamster Balls
Researches have performed experiments in which particles with dozens of atoms have exhibited double slit interference. Suppose we could theoretically continue scaling this experiment up to large and large systems. Until eventually, we can perform an experiment in which we can put a human in a steel ball, shoot them through a double slit experiment, and look at where on a screen on the other side the human crashes.
On the Everettian theory as the person traverses the apparatus they would go into a superposition state of taking one path versus the other. So, mid-flight, they would be in a superposition state. Their paths would then interfere at the screen and, if we shoots 1000's or hundreds of poor people through this apparatus, we would see an interference pattern build up.
On the Copenhagen theory it would be forbidden for the human to be in a superposition state because they are a macroscopic system. Instead, after passing through the apparatus, they would probabilistically take one path or the other and no interference pattern would emerge. Just 2 blobs like in the double-slit experiment when it is known through which slit the particle passed.
Again we see a discrepancy between the Everettian and Copenhagen theories. If someone wants to defend the Copenhagen collapse theory my opinion is that the onus is on them to explain at what point, between dozens of atoms, and a full human, does it become fundamentally (as opposed to technically) impossible to perform a double slit experiment and why. This latter effort is exactly what is done by researchers looking into spontaneous collapse theories and non-linear extensions to the Schrodinger equation. I respect this effort. The bare Copenhagen theory, however, does not give any rigorous physical explanation for where the Heisenberg cut appears and why. And for this reason I claim the Copenhagen theory is incomplete

A note on terminology: Here I have (infinitely begrudgingly) used the convention that two interpretations make the same physical predictions. I've done this so I don't have to fuss about the terminology with folks who insist on this definition of interpretation. My preferred definition of "interpretation" is that an interpretation of quantum mechanics is any quantum theory which attempts to address the measurement problem using some approach. Anyways, for this reason you will see that I didn't use the word "interpretation" anywhere above, because I am, of course, discussing the possibility that the Copenhagen and Everettian stories make different predictions.


TITLE: Trigonometric identity proof
QUESTION [3 upvotes]: I’ve got to proof that:
$$\tan\left(\frac{A}{2}\right) = \sqrt{\frac{1 -\cos(A)}{1 + \cos(A)}}$$
My attempt was (tried with right side):
$$= \pm \sqrt{\frac{1 -\cos(A)}{1 + \cos(A)} \cdot \frac{1 -\cos(A)}{1 - \cos(A)}}$$
$$= \pm \sqrt{\frac{\left(1 -\cos(A)\right)^2}{1 - \cos^2(A)}}$$
$$= \pm \frac{1 -\cos(A)}{\sin(A)}$$
They are not even similar.
I tried Wolfram Alpha online calculator and it showed one of the alternate answers as:
$$\sqrt{\tan^2\left(\frac{A}{2}\right)}$$
That’s the answer I suppose I should get to, but I’ve tried it many times and I can’t find (imagine) a possible route.
Please, if you could point me in the right direction, I’d greatly appreciate it.
Thank you very much in advance.

REPLY [3 votes]: $\tan(a/2)$ is not uniquely determined by $\cos(a)$. For the formula to hold, one needs to restrict the angles to an interval, or take absolute values of both sides.
A correct statement without any qualification is that the squares of the two sides of the equation are equal:
$\tan^2(A/2)=\frac{1-\cos(A)}{1+\cos(A)}$
which follows from the half- or double-angle formulas for $\sin$ and $\cos$.


TITLE: A sequence of coin tosses HTTHT...can be related to the sequence 10010...
QUESTION [0 upvotes]: A sequence of coin tosses HTTHT...can be related to the sequence
  10010...and used to generate random binary numbers. If an unbiased coin is tossed 9 times and the related sequence of 0's and 1's is
  recorded, what is the probability that the binary number will exceed
  256?

I'm a little confused on how to set up the math for the problem - I know that 256 in binary is 100000000, and to calculate the probability that it will exceed 256 you want to know the probability of getting every number above 256 but...how do I find that out exactly? And what do I do with that information?

REPLY [1 votes]: If you get a first 0 the maximum you can get is $(011111111)_{2}=255$
To exceed 256 you have to get something like $(100000100)_{2}$, i.e. get the first 1, and do not get all zero for the 8 tosses after that.
The probability is then $\tfrac{1}{2}\times(1-(\tfrac{1}{2})^8)$


TITLE: How to denote a one-hot vector space, like $\mathbb{R}^n$ but for one-hot vectors?
QUESTION [2 upvotes]: For real vector $v_r$ we can write $v_r \in \mathbb{R}^n$.
For binary vector $v_b$, I think we can write $v_b \in \{0,1\}^n$.
But how should we write a one-hot vector $v_i$?

REPLY [3 votes]: You could denote the set of one-hot vectors by:
$$
\left\{
v \in \{0,1\}^n :
\sum \limits_{i=1}^n v_i = 1
\right\}
$$


TITLE: Formalization (and meaning) of Heisenberg Cut
QUESTION [3 upvotes]: In discussions around a recent  Stack answer which covered axiomatic quantum mechanics, Bell's Theorem and Random Fields (related to axiomatic QFT) the phrase "Heisenberg Cut" was used. The basic question is what does this mean?
Having reviewed this discussion I can provide some background to set a context for the question. In (Von Neumann) QM a distinction is made between :  OBSERVER [Cut] QUANTUM OBJECT
This simplistic distinction has been critized later in that article and elsewhere such that the term "Heisenberg Cut" has fallen into disuse. If one wishes to make distinctions in a QM experiment then here is a larger proposal:
ENVIRONMENT [Cut1] QUANTUM OBJECT [Cut2] CLASSICAL INSTRUMENT [Cut3] OBSERVER [Cut4] O-O
here O-O is any hypothetical observer-observer as discussed in the "Wigner's Friend" concept.
So has the concept of "Heisenberg Cut" been re-introduced in modern axiomatic QM/QFT and if so what is its formalisation (ie how can one make experimental or Bell Theorem-like deductions from it?)

REPLY [2 votes]: I take the heart of the Heisenberg cut to be the way we calculate probabilities and expected values in QM. For elementary QM, for some measurement described by an operator $\hat M$, the expected value in a state described by a density matrix $\hat\rho$ is given by the trace $\left<\!M\right>=\mathsf{Tr}\left(\!\hat M\hat\rho\!\right)$. What we put in the $\hat\rho$ is what is in our model universe. The measurement operator describes our measurement apparatus, which is not in the model universe, but instead describes how our measurement apparatus gets information out of the model universe. There's an almost-symmetry between the ways $\hat M$ and $\hat\rho$ appear; it's almost as if there's a measurement apparatus universe as well as the model universe. Different measurement apparatuses can affect each other in the measurement apparatus universe without changing the model universe, which is called measurement incompatibility (did I just create an interpretation of QM? Do I know this one? I guess it's too glib, sadly.)
Edit: We can extend the mathematics in many different ways, but one deserves mention because it's of great practical value. We can introduce transformations $\hat T_i$ that operate between the preparation apparatus and the measurement apparatus, in which case we have $\left<\!M\right>=\mathsf{Tr}\left(\!\hat M\hat T_n\cdots\hat T_2\hat T_1\hat\rho\!\right)$. We can at any time say that $\hat M\hat T_n\cdots\hat T_5$, say, or any other part of this list (without changing the order), is our measurement.
Anyway, to some extent we can move stuff from the model universe into the measurement apparatus universe and vice versa, although we may have to get into technical stuff like POVMs to do it. Once we go to quantum field theory, there's a tight relationship between the measurement apparatus universe and the model universe, because we use the same Lego blocks to build measurements and states.
The separation into states and measurements is absolutely fundamental in QM. It's how the relationship between Hilbert spaces and experimental results works, which causes trouble when people want to do cosmology, with everything in the model universe. Although I hadn't previously thought about calculating where one should put the separation, I can see that if one chooses a particular accuracy that one wants one's model of an experimental apparatus to achieve relative to one's real apparatus, that might put a limit on where one can put the Heisenberg cut. I'm not sure, however, that one can't always improve the sophistication of one's description of a measurement, particularly if one is willing to go to POVMs. I suppose, however, that putting people inside your model universe is always going to be in the realm of toy models. The separation into states and measurement famously comes under the microscope in Bell's article `Against "Measurement" '.
Incidentally, I see you went to Willem de Muynck, who is perhaps a little idiosyncratic, but I've often found his a good counterpoint of view.


text:
\begin{document}

\begin{frontmatter}
\title{Symmetry Detection of Rational Space Curves\\ from their Curvature and Torsion}

\author[a]{Juan Gerardo Alc\'azar\fnref{proy}}
\ead{juange.alcazar@uah.es}
\author[a]{Carlos Hermoso}
\ead{carlos.hermoso@uah.es}
\author[b]{Georg Muntingh}
\ead{georgmu@math.uio.no}

\address[a]{Departamento de F\'{\i}sica y Matem\'aticas, Universidad de Alcal\'a,
E-28871 Madrid, Spain}
\address[b]{SINTEF ICT, PO Box 124 Blindern, 0314 Oslo, Norway}

\fntext[proy]{Supported by the Spanish ``Ministerio de
Ciencia e Innovacion" under the Project MTM2011-25816-C02-01. Partially supported by
the Jos\'e Castillejos' grant $\mbox{CAS12$/$00022}$ from the Spanish Ministerio de Educaci\'on, Cultura y Deporte.
Member of the Research Group {\sc asynacs} (Ref. {\sc ccee2011/r34}) }

\begin{abstract}
We present a novel, deterministic, and efficient method to detect whether a given rational space curve is symmetric. By using well-known differential invariants of space curves, namely the curvature and torsion, the method is significantly faster, simpler, and more general than an earlier method addressing a similar problem~\cite{AHM13-2}. To support this claim, we present an analysis of the arithmetic complexity of the algorithm and timings from an implementation in {\tt Sage}.
\end{abstract}

\end{frontmatter}

\section{Introduction}\label{section-introduction}
\noindent The problem of detecting the symmetries of curves and surfaces has attracted the attention of many researchers throughout the years, because of the interest from fields like Pattern Recognition \cite{Boutin, Calabi, Huang, LR08, LRTh, Suk1, Suk2, TC00, Taubin2, Weiss}, Computer Graphics \cite{Berner08, Bokeloh, Lipman, Martinet,  Mitra06, Podolak, Schnabel, Simari}, and Computer Vision \cite{Alt88, Brass, Jiang, Li08, Li10, Loy, Tate, Sun}. The introduction in \cite{AHM13-2} contains an extensive account of the variety of approaches used in the above references.

A common characteristic in most of these papers is that the methods focus on computing \emph{approximate} symmetries more than exact symmetries, which is perfectly reasonable in many applications, where curves and surfaces often serve as merely approximate representations of a more complex shape. Some exceptions appear here: If the object to be considered is discrete (e.g. a polyhedron), or is described by a discrete object, like for instance a control polygon or a control polyhedron, then the symmetries can be determined exactly \cite{Alt88, Brass, Jiang, Li08}. Examples of the second class are B\'ezier curves and tensor product surfaces. Furthermore, in these cases the symmetries of the curve or surface follow from those of the underlying discrete object. Another exception appears in \cite{LR08}, where the authors provide a deterministic method to detect rotation symmetry of an implicitly defined algebraic plane curve and to find the exact rotation angle and rotation center. The method uses a complex representation of the curve and is generalized in \cite{LRTh} to detect mirror symmetry as well.

Rational curves are frequently used in Computer Aided Geometric Design and are the building blocks of NURBS curves. Compared to implicit curves, rational parametric curves are easier to manipulate and visualize. Space curves appear in a natural way when intersecting two surfaces, and they play an important role when dealing with special types of surfaces, often used in geometric modeling, like ruled surfaces, canal surfaces or surfaces of revolution, which are generated from a {\it directrix} or {\it profile} curve. Furthermore, in geometric modeling it is typical to use rational space curves as profile curves.

In this paper we address the problem of deterministically finding the symmetries of a rational space curve, defined by means of a proper parametrization. Notice that since we deal with a global object, i.e., the set of all points in the image of a rational parametrization, and not just a piece of it, the discrete approach from \cite{Alt88, Brass, Jiang, Li08} is not suitable here. Determining if a rational space curve is symmetric or not is useful in order to properly describe the topology of the curve \cite{AD10}. Furthermore, if the space curve is to be used for generating, for instance, a canal surface or a surface of revolution, certain symmetries of the curve will be inherited by the generated surface. Hence, for modeling purposes it can be interesting to know these symmetries in advance.

Recently, the problem of determining whether a rational plane or space curve is symmetric has been addressed in \cite{A13, AHM13, AHM13-2} using a different approach. The common denominator in these papers is the following observation: If a rational curve is \emph{symmetric}, i.e., invariant under a nontrivial isometry $f$, then this symmetry induces another parametrization of the curve, different from the original parametrization. Assuming that the initial parametrization is proper (definition below), the second parametrization is also proper. Since two proper parametrizations of the same curve are related by a M\"obius transformation \cite{SWPD}, determining the symmetries is reduced to finding this transformation, therefore translating the problem to the parameter space. This observation leads to algorithms for determining the symmetries of plane curves with polynomial parametrizations \cite{A13} and of plane and space curves with rational parametrizations \cite{AHM13-2}, although in the latter case of general space curves only involutions were considered. The more general problem of determining whether two rational plane curves are similar was considered in \cite{AHM13}.

In this paper we again employ the above observation, but in addition we now also use well-known differential invariants of space curves, namely the curvature and the torsion. The improvement over the method in \cite{AHM13-2} is threefold: First of all, we are now able to find \emph{all} the symmetries of the curve instead of just the involutions. Secondly, the new algorithm is considerably faster and can efficiently handle even curves with high degrees and large coefficients in reasonable timings. Finally, the method is simpler to implement and requires fewer assumptions on the parametrization.

Some general facts on symmetries of rational curves are presented in Section~\ref{sec-prelim}. Section~\ref{sec-sym-detec} provides an algorithm for checking whether a curve is symmetric. The determination of the symmetries themselves is addressed in Section~\ref{sec-find}. Finally, in Section~\ref{exp-sec} we report on the performance of the algorithm, by presenting a complexity analysis and providing timings for several examples, including a comparison with the curves tested in \cite{AHM13-2}.

\section{Symmetries of rational curves} \label{sec-prelim}
\noindent Throughout the paper, we consider a rational space curve $\CCC\subset \RR^3$, neither a line nor a circle, parametrized by a rational map
\begin{equation}\label{eq:parametrizations}
{\bfx}: \RR \dashrightarrow \CCC\subset \RR^3, \qquad \bfx(t) = \big( x(t),y(t),z(t) \big) .
\end{equation}
The components $x(t), y(t), z(t)$ of $\bfx$ are rational functions of $t$ with rational coefficients, and they are defined for all but a finite number of values of $t$. Let the \emph{(parametric)} degree $m$ of $\bfx$ be the maximal degree of the numerators and denominators of the components $x(t),y(t),z(t)$. Note that rational curves are irreducible. We assume that the parametrization \eqref{eq:parametrizations} is \emph{proper}, i.e., birational or, equivalently, injective except for perhaps finitely many values of $t$. This can be assumed without loss of generality, since any rational curve can quickly be properly reparametrized. For these claims and other results on properness, the interested reader can consult \cite{SWPD} for plane curves and \cite[\S 3.1]{A12} for space curves.

We recall some facts from Euclidean geometry \cite{Coxeter}. An \emph{isometry} of $\RR^3$ is a map $f:\RR^3\longrightarrow \RR^3$ preserving Euclidean distances. Any isometry $f$ of $\RR^3$ is linear affine, taking the form
\begin{equation}\label{eq:isometry}
f(\bfx) = \mQ\bfx + \bfb, \qquad \bfx\in \RR^3,
\end{equation}
with $\bfb \in \RR^3$ and $\mQ\in \RR^{3\times 3}$ an orthogonal matrix. In particular $\det(\mQ) = \pm 1$. Under composition, the isometries of $\RR^3$ form the \emph{Euclidean group}, which is generated by \emph{reflections}, i.e., symmetries with respect to a plane, or \emph{mirror symmetries}. An isometry is called \emph{direct} when it preserves the orientation, and \emph{opposite} when it does not. In the former case $\det(\mQ) = 1$, while in the latter case $\det(\mQ) = -1$. The identity map of $\RR^3$ is called the \emph{trivial symmetry}.

The classification of the nontrivial isometries of Euclidean space includes reflections (in a plane), rotations (about an axis), and translations, and these combine in commutative pairs to form twists, glide reflections, and rotatory reflections. Composing three reflections in mutually perpendicular planes through a point $\bfp$, yields a \emph{central inversion} (also called \emph{central symmetry}), with center $\bfp$, i.e., a symmetry with respect to the point $\bfp$. The particular case of rotation by an angle $\pi$ is of special interest, and it is called a \emph{half-turn}. Rotation symmetries are direct, while mirror and central symmetries are opposite.

\begin{lemma}
A rational space curve $\CCC\subset \RR^3$ different from a line cannot be invariant under a translation, glide reflection, or twist.
\end{lemma}
\begin{proof}
If $\CCC$ were invariant under translation by a vector $\bfb$, then, for any point $\bfx$ on $\CCC$, the line $\LLL = \{\bfx + t\bfb\,:\,t\in \RR\}$ would intersect $\CCC$ in infinitely many points, implying that $\LLL\subset \CCC$ and contradicting that $\CCC$ is an irreducible curve different from a line. Since applying a glide reflection twice yields a translation, $\CCC$ cannot be invariant under a glide reflection either.
Suppose $\CCC$ is invariant under a twist $f$ with axis $\AAA$ and angle $\alpha$, and let $\pi: \RR^3 \longrightarrow \Pi$ be the orthogonal projection onto a plane $\Pi\perp \AAA$. Then the projection $\CCC' := \pi(\CCC)$ is a plane algebraic curve invariant under the rotation $\pi \circ f$ by the angle $\alpha$ about the point $\AAA\cap \Pi$. By Lemma 1 in \cite{AHM13-2}, $\alpha=2\pi/k$ with $k\leq \deg(\CCC')$. But then $\CCC$ is invariant under the translation $f^k$, which is a contradiction.
\end{proof}

Therefore, the rotations, reflections, and their combinations (like central inversions) are the only isometries leaving an irreducible algebraic space curve, different from a line, invariant. We say that an irreducible algebraic space curve is \emph{symmetric}, if it is invariant under one of these (nontrivial) isometries. In that case, we distinguish between a \emph{mirror symmetry}, \emph{rotation symmetry} and \emph{central symmetry}. If the curve is neither a line nor a circle, it has a finite number of symmetries~\cite{AHM13-2}.

We recall the following result from \cite{AHM13-2}. For this purpose, let us recall first that a \emph{M\"obius transformation} (of the affine real line) is a rational function
\begin{equation}\label{eq:Moebius}
\varphi: \RR\dashrightarrow \RR,\qquad \varphi(t) = \frac{a t + b}{c t + d},\qquad \Delta := ad - bc \neq 0.
\end{equation}
In particular, we refer to $\varphi(t) = t$ as the \emph{trivial transformation}. It is well known that the birational functions on the real line are the M\"obius transformations~\cite{SWPD}.

\begin{theorem}\label{th-fund}
Let $\bfx: \RR\dashrightarrow \CCC\subset \RR^3$ be a proper parametric curve as in \eqref{eq:parametrizations}. The curve $\CCC$ is symmetric if and only if there exists a nontrivial isometry $f$ and nontrivial M\"obius transformation $\varphi$ for which we have a commutative diagram
\begin{equation}\label{eq:fundamentaldiagram}
\xymatrix{
\CCC \ar[r]^{f} & \CCC \\
\RR \ar@{-->}[u]^{\bfx} \ar@{-->}[r]_{\varphi} & \RR \ar@{-->}[u]_{\bfx}
}
\end{equation}
Moreover, for each isometry $f$ there exists a unique M\"obius transformation $\varphi$ that makes this diagram commute.
\end{theorem}

Note that $\varphi(t)$ is the parameter value corresponding to the image under the symmetry $f$ of the point on $\CCC$ with parameter $t$.

\begin{lemma}
Let $\varphi$ be a M\"obius transformation associated to a parametrization~$\bfx$ and isometry $f$ in the sense of Theorem \ref{th-fund}. Then its coefficients $a,b,c,d$ can be assumed to be real, by dividing by a common complex number if necessary.
\end{lemma}
\begin{proof}
For any proper parametrization $\bfx$ and isometry $f$ the associated M\"obius transformation $\varphi = \bfx^{-1}\circ f \circ \bfx$ maps the real line to itself. In particular, since
\[
0 = \varphi(t) - \overline{\varphi(t)}
  = \frac{(a\overline{c} - \overline{a}c)t^2 + (b\overline{c} - \overline{b}c + a\overline{d} - \overline{a}d)t + (b\overline{d} - \overline{b}d)}{(ct + d)(\overline{c}t + \overline{d})}
\]
for any $t$ for which $\varphi(t)$ is defined, $a\overline{c}$ and $b\overline{d}$ are real, so that $\arg(a) = \arg(c)$ and $\arg(b) = \arg(d)$. A similar argument for $\varphi^{-1}$ yields that
$-d\overline{c}/|ad - bc|^2$ and $-b\overline{a}/|ad - bc|^2$ are real, implying that $\arg(c) = \arg(d)$ and $\arg(a) = \arg(b)$. It follows that all coefficients of $\varphi$ have a common argument $\theta$. Therefore, after dividing the coefficients of $\varphi$ by $\exp(i\theta)$, the coefficients of $\varphi$ can be assumed to be real.
\end{proof}

Let the \emph{curvature} $\kappa$ and \emph{torsion} $\tau$ of a parametric curve $\bfx$ be the functions
\[\kappa = \kappa_\bfx := \frac{\Vert \bfx' \times \bfx''\Vert}{\Vert \bfx' \Vert^3}, \qquad
    \tau =   \tau_\bfx := \frac{\langle \bfx'\times \bfx'', \bfx'''\rangle}{\Vert \bfx' \times \bfx''\Vert^2}\]
of the parameter $t$. Note that $\kappa$ is non-negative. The functions $\kappa^2$ and $\tau^2$ are well-known rational \emph{differential invariants} of the parametrization $\bfx$, in the sense that
\begin{equation}\label{eq:kappatauinv}
\kappa_{f\circ \bfx} = \kappa_\bfx, \qquad \tau_{f\circ \bfx} = \det(\mQ)\cdot \tau_\bfx
\end{equation}
for any isometry $f(\bfx) = \mQ\bfx + \bfb$. This follows immediately from $\mQ$ being orthogonal and the identity
\begin{equation}\label{eq:cross}
(\mM\bfa) \times (\mM\bfb) = \det(\mM) \mM^{-\mathrm{T}} (\bfa \times \bfb),
\end{equation}
which holds for any invertible matrix $\mM$ and follows from a straightforward calculation. Although $\tau_\bfx$ and $\kappa_\bfx^2$ are rational for any rational parametrization~$\bfx$, the curvature $\kappa_\bfx$ is in general not rational.

The following lemma describes the behavior of the curvature and torsion under reparametrization, for instance by a M\"obius transformation.

\begin{lemma} \label{Moeb-curvat}
Let $\bfx$ be the rational parametrization \eqref{eq:parametrizations} and let $\phi \in C^3(U)$, with $U\subset \RR$ open. Then
\[ \kappa_{\bfx \circ \phi} = \kappa_\bfx \circ \phi,\qquad \tau_{\bfx \circ \phi} = \tau_\bfx\circ\phi,\]
whenever both sides are defined.
\end{lemma}

\begin{proof}
Writing $\tilde{\bfx} := \bfx\circ \phi$ and using the chain rule, one finds
\begin{align*}
\tilde{\bfx}'(t)
 & = \bfx'  \big(\phi(t)\big)\cdot \phi'(t),\\
\tilde{\bfx}''(t)
 & = \bfx'' \big(\phi(t)\big)\cdot \big(\phi'(t)\big)^2 +\bfx'\big(\phi(t)\big)\cdot \phi''(t),\\
\tilde{\bfx}'''(t)
 & = \bfx'''\big(\phi(t)\big)\cdot \big(\phi'(t)\big)^3 +3\bfx''\big(\phi(t)\big)\cdot \phi'(t)\cdot \phi''(t)+\bfx'\big(\phi(t)\big)\cdot \phi'''(t),
\end{align*}
whenever $t\in U$ and $\bfx$ is defined at $\phi(t)$. Therefore
\[ \kappa_{\bfx \circ \phi}(t)
 = \frac{\left\| \tilde{\bfx}'(t) \times \tilde{\bfx}''(t) \right\|}{\left\| \tilde{\bfx}'(t) \right\|^3}
 = \frac{\left\| \bfx'\big(\phi(t)\big) \times \bfx''\big(\phi(t)\big)\right\|\cdot \left| \phi'(t)\right|^3}{\left\| \bfx'\big(\phi(t)\big) \right\|^3 \cdot \left| \phi'(t)\right|^3}
 = \big( \kappa_\bfx \circ \phi\big) (t), \]
and similarly one finds $\tau_{\bfx\circ \phi} = \tau_\bfx \circ \phi$.
\end{proof}

\section{Symmetry detection} \label{sec-sym-detec}
\noindent In this section we derive a criterion for the presence of nontrivial symmetries $f(\bfx) = \mQ\bfx + \bfb$ of curves of type \eqref{eq:parametrizations}, together with an efficient method for checking this criterion. The cases $\det(\mQ) = \pm 1$ need to be checked separately, but are considered simultaneously using linked $\pm$ and $\mp$ signs consistently throughout the paper. The resulting method is summarized in Algorithm {\tt Symm$^\pm$}.

\subsection{A criterion for the presence of symmetries}\label{subsec-main-th}
\noindent For any parametric curve $\bfx$ as in \eqref{eq:parametrizations}, write
\[\kappa_\bfx^2(t) =: \frac{A(t)}{B(t)}, \qquad \tau_\bfx(t)=:\frac{C(t)}{D(t)},\]
with $(A,B)$ and $(C,D)$ pairs of coprime polynomials. Let
\begin{equation}\label{eq:G}
G^\pm_\bfx := \gcd\big(K_\bfx, T^\pm_\bfx\big),
\end{equation}
with
\begin{equation}\label{eq:KT}
K_\bfx (t, s) := A(t)B(s) - A(s)B(t),\qquad T^\pm_\bfx (t, s) := C(t)D(s) \mp C(s)D(t)
\end{equation}
the result of clearing denominators in the equations
\begin{equation}\label{eq:kappatauts}
\kappa_\bfx^2(t) - \kappa_\bfx^2(s) = 0,\qquad \tau_\bfx (t) \mp \tau_\bfx (s) = 0.\ \ \ \
\end{equation}
Similarly, associate to any M\"obius transformation $\varphi$
the \emph{M\"obius-like} polynomial
\begin{equation}\label{eq:F}
F(t, s) := (ct + d)s - (at + b),\qquad ad - bc\neq 0,
\end{equation}
as the result of clearing denominators in $s - \varphi(t) = 0$. We call $F$ \emph{trivial} when $F(t, s) = s - t$, i.e., when the associated M\"obius transformation is the identity. Note that $F$ is irreducible since $ad - bc\neq 0$.

\begin{theorem} \label{funda-sym}
Consider the curve $\CCC$ defined by $\bfx$ in \eqref{eq:parametrizations} and let $G^\pm_\bfx$ be as above. Then $\CCC$ has a nontrivial symmetry $f(\bfx) = \mQ\bfx + \bfb$, with $\det(\mQ) = \pm 1$, if and only if there exists a nontrivial polynomial $F$ of type \eqref{eq:F}, associated with a M\"obius transformation $\varphi$, such that $F$ divides $G^\pm_\bfx$ and the parametrizations $\bfx$ and $\bfx\circ \varphi$ have identical speed,
\begin{equation}\label{new-cond}
\|\bfx'\| = \|(\bfx \circ \varphi)'\|.
\end{equation}
\end{theorem}

The zeroset of $F$ is the graph of $\varphi$, which is either a rectangular hyperbola with horizontal and vertical asymptotes when $c\neq 0$, or a line with nonzero and finite slope $a/d$ when $c = 0$.
Whenever $F$ is a factor of $G^\pm_\bfx$, the corresponding hyperbola or line is contained in the zeroset of $G^\pm_\bfx$; see Figure~\ref{fig:Example1}.

\begin{proof}[Proof of Theorem \ref{funda-sym}] ``$\Longrightarrow$'': If $\CCC$ is invariant under a nontrivial isometry $f(\bfx)=\mQ\bfx+\bfb$, with $\det(\mQ) = \pm 1$, by Theorem~\ref{th-fund} there exists a M\"obius transformation $\varphi$ such that $f \circ \bfx = \bfx \circ \varphi$. Let $F$ be the M\"obius-like polynomial associated with $\varphi$. The points $(t,s)$ for which $K_\bfx(t, s) = T^\pm_\bfx(t,s) = 0$ are the points satisfying $\kappa_\bfx(s) = \kappa_\bfx(t)$ and $\tau_\bfx(s) = \pm \tau_\bfx(t)$. This includes the zeroset $\left\{\big(t, s\big)\,:\,s = \varphi(t)\right\}$ of $F(t,s)$, since
\[
\kappa_\bfx \circ \varphi = \kappa_{\bfx\circ \varphi} = \kappa_{f\circ \bfx} = \kappa_\bfx,\qquad
\tau_\bfx \circ \varphi = \tau_{\bfx \circ \varphi} = \tau_{f\circ \bfx} = \det(\mQ) \tau_\bfx = \pm \tau_\bfx
\]
by Lemma \ref{Moeb-curvat} and \eqref{eq:kappatauinv}. Since $F$ is irreducible, B\'ezout's theorem implies that $F$ divides $K_\bfx$ and $T^\pm_\bfx$, and therefore $G^\pm_\bfx$ as well. Furthermore, since $\mQ$ is orthogonal, the parametrizations have equal speed,
\[ \|(\bfx \circ \varphi)'\|  = \|(f\circ \bfx)'\| = \|(\mQ \bfx + \bfb)'\|  = \|\mQ \bfx'\| = \|\bfx'\|. \]

``$\Longleftarrow$'': Let $\varphi$ be the nontrivial transformation associated to $F$. Let $t_0 \in I\subset \RR$ be such that $\bfx(t)$ is a regular point on $\CCC$ for every $t\in I$, and consider the arc length function
\[ s = s(t) := \int_{t_0}^t \|\bfx'(t)\|\rmd t,\qquad t\in I,\]
which (locally) has an infinitely differentiable inverse $t = t(s)$. By \eqref{new-cond},
\[ \left\| \frac{\rmd }{\rmd s} \big(\bfx\circ t\big)\right\|
 = \left\| \frac{\rmd \bfx}{\rmd t} \frac{\rmd t}{\rmd s} \right\|
 = 1
 = \left\| \frac{\rmd }{\rmd t} \big(\bfx\circ \varphi \big) \frac{\rmd t}{\rmd s} \right\|
 = \left\| \frac{\rmd }{\rmd s} \big(\bfx\circ \varphi \circ t\big)\right\|
 ,\]
so that $\bfx\circ t$ and $\bfx\circ \varphi \circ t$ are parametrized by arc length. Since $F$ divides $G^\pm_\bfx$, any zero $\big(t,\varphi(t)\big)$ of $F$ is also a zero of $K_\bfx$ and $T^\pm_\bfx$, implying that $\kappa_\bfx = \kappa_{\bfx} \circ \varphi$ and $\tau_\bfx = \pm \tau_{\bfx} \circ \varphi$. Then, by repeatedly applying Lemma \ref{Moeb-curvat},
\begin{equation}
\kappa_{\bfx \circ t} = \kappa_{\bfx} \circ t = \kappa_{\bfx\circ \varphi} \circ t = \kappa_{\bfx\circ \varphi\circ t}, \quad
\tau_{\bfx \circ t} =
\tau_{\bfx} \circ t =
\pm \tau_{\bfx \circ \varphi} \circ t =
\pm \tau_{\bfx \circ \varphi \circ t}.
\end{equation}
The Fundamental Theorem of Space Curves \cite[p. 19]{Docarmo} then implies that $\bfx\circ t$ and $\bfx\circ \varphi\circ t$ coincide on $s(I)$ up to an isometry $f(\bfx) = \mQ\bfx + \bfb$ with $\det(\mQ)=\pm 1$. Therefore $\CCC$ and $f(\CCC)$ have infinitely many points in common. Since $\CCC$ and $f(\CCC)$ are irreducible algebraic curves, it follows that $\CCC=f(\CCC)$ and therefore $f$ is a symmetry of $\CCC$.
\end{proof}

Note that the polynomial $G^\pm_\bfx$ cannot be identically 0. Indeed, $G^\pm_\bfx$ is identically $0$ if and only if $K_\bfx$ and $T^\pm_\bfx$ are both identically $0$, which happens precisely when $\kappa_\bfx$ and $\tau_\bfx$ are both constant. If $\kappa_\bfx = 0$ then $\CCC$ is a line, if $\tau_\bfx = 0$ and $\kappa_\bfx$ is a nonzero constant then $\CCC$ is a circle, and if $\kappa_\bfx, \tau_\bfx$ are both constant but nonzero then $\CCC$ is a circular helix, which is non-algebraic. All of these cases are excluded by hypothesis.

\subsection{Finding the M\"obius-like factors $F$ of $G^\pm_\bfx$} \label{Check-cond}
\noindent The criterion in Theorem \ref{funda-sym} requires to check if a bivariate polynomial $G = G^\pm_\bfx$ has \emph{real} factors of the form $F(t,s)=(ct+d)s-(at+b)$, with $ad-bc\neq 0$. However, $a,b,c,d$ need not be rational numbers, so that we need to factor over the algebraic or real numbers. This problem has been studied by several authors \cite{C04, CG06, CGKW, GR02}. However, since in our case we are looking for factors of a specific form, we develop an ad hoc method to check the condition.

Let $\GGG$ be the curve in the $(t,s)$-plane defined by $G(t,s)$. Let $t_0$ be such that the vertical line $\LLL$ at $t = t_0$ does not contain any zero of $\GGG$ where the partial derivative $G_s := \frac{\partial G}{\partial s}$ vanishes; see Figure \ref{fig:Example1}. These are the points $t_0$ for which the discriminant of $g(s) := G(t_0, s)$ does not vanish, which is up to a factor equal to the Sylvester resultant $\Res_s(G, G_s)$ and has degree at most $(2m_s - 1)m_t$ in $t_0$, with $(m_t, m_s)$ the bidegree of $G$. Therefore one can always find an integer abscissa $t_0$ with this property by checking for at most $(2m_s - 1)m_t + 1$ points $t_0$ whether the gcd of $g(s)$ and $G_s(t_0, s)$ is trivial.

If $G$ has a M\"obius-like factor $F$ as in \eqref{eq:F}, then the zeroset of $F$ intersects $\LLL$ in a single point $\bfp_0=(t_0, \xi)$ satisfying
\begin{equation} \label{valuesabc-1}
(ct_0 + d)\xi - (at_0 + b) = 0.
\end{equation}
Since $G_s(\bfp_0)\neq 0$, the equation $F(t,s) = 0$ implicitly defines a function $s = s(t)$ in a neighborhood of $\bfp_0$. Moreover, by differentiating the identity $F\big(t,s(t)\big) = 0$ once and twice with respect to $t$, and evaluating at $\bfp_0$, we find the relations
\begin{align}
-a + ds'_0 +c\cdot (\xi + t_0 s'_0)  & = 0,\label{valuesabc-2a}\\
d s''_0 + c\cdot (2s'_0 + t_0 s''_0) & = 0,\label{valuesabc-2b}
\end{align}
where $\xi = s(t_0)$, $s'_0 := s'(t_0)$, and $s''_0 := s''(t_0)$. In order to find expressions for $s'_0$, $s''_0$, we now use that the function $s(t)$ is also implicitly defined by $G(t, s) = 0$, because $F$ is a factor of $G$ and $G_s(\bfp_0)\neq 0$. Differentiating once and twice the identity $G\big(t,s(t)\big) = 0$ with respect to $t$ gives
\begin{equation} \label{eq:difffunc}
s'  = -\frac{G_t(t,s)}{G_s(t,s)},\qquad
s'' = -\frac{G_{tt}(t,s) +2G_{ts}(t,s)s' + G_{ss}(t,s)\big(s'\big)^2}{G_s(t,s)}.
\end{equation}
Evaluating these expressions at $\bfp_0$ yields expressions $s'_0 = s'_0 (\xi)$ and $s''_0 = s''_0 (\xi)$.

Now we distinguish the cases $d\neq 0$ and $d=0$. In the first case, we may assume $d=1$ by dividing all coefficients in the M\"obius transformation by $d$. In that case $2s_0' + t_0 s_0'' = 2\Delta/(ct_0 + 1)^3 \neq 0$ and \eqref{valuesabc-1}--\eqref{valuesabc-2b} yield rational expressions
\begin{equation}\label{eq:abcd=1}
c_1(\xi) := \frac{-s''_0}{2s'_0+t_0 s''_0},\ a_1(\xi) := s'_0 + c_1(\xi) (\xi + t_0 s'_0),\ b_1(\xi) := -a_1(\xi) t_0 + \xi + c_1(\xi) t_0\xi.
\end{equation}
The polynomial $F$ is a factor of $G$ if and only if the resultant $\Res_s(F,G)$ is identically $0$. Substituting $a_1(\xi), b_1(\xi), c_1(\xi)$, and $d=1$ into this resultant yields a polynomial $P_1(t)$, whose coefficients are rational functions of $\xi$. Let $R_1(\xi)$ be the gcd of the numerators of these coefficients and of $g(\xi)$. The real roots $\xi$ of $R_1(\xi)$ for which $a_1(\xi), b_1(\xi), c_1(\xi)$ are well defined and $\Delta_1 (\xi) := a_1(\xi) - b_1(\xi) c_1(\xi)\neq 0$ correspond to the M\"obius-like factors $F$ of $G$ as in \eqref{eq:F} with $d = 1$.

On the other hand, when $d=0$ we may assume $c=1$, and \eqref{valuesabc-1}--\eqref{valuesabc-2b} yield rational expressions
\begin{equation}\label{eq:ab}
a_0(\xi) := \xi + t_0 s'_0,\qquad b_0(\xi) := -a_0(\xi) t_0 + t_0\xi.
\end{equation}
Substituting $a_0(\xi), b_0(\xi), c = 1$, and $d = 0$ into the resultant $\Res_s(F,G)$ yields a polynomial $P_0(t)$, whose coefficients are rational functions of $\xi$. Let $R_0(\xi)$ be the gcd of the numerators of these coefficients and $g(\xi)$. The real roots $\xi$ of $R_0(\xi)$ for which $a_0(\xi)$ and $b_0(\xi)$ are well defined and $\Delta_0(\xi) := -b_0(\xi)$ is nonzero correspond to the M\"obius-like factors $F$ of $G$ as in \eqref{eq:F} with $d = 0$. We obtain the following theorem.
\begin{theorem} \label{factor}
The polynomial $G$ has a real M\"obius-like factor $F$ as in \eqref{eq:F} with $d\neq 0$ (resp. $d = 0$) if and only if $R_1(\xi)$ (resp. $R_0(\xi)$) has a real root. Furthermore, every such real root provides a factor of this form.
\end{theorem}

Note that the cases $d = 0$ and $d \neq 0$ can be computed in parallel.

\begin{figure}
\begin{center}
\includegraphics[scale=0.8]{Example1.pdf}
\end{center}
\caption{The zeroset (solid) of the polynomial $G=G^\pm_\bfx$ intersects the vertical line $\LLL$ (dashed) in the points $(2, \pm \sqrt{8})$ and $(2, \pm 1/\sqrt{12})$ in Example \ref{ex1}.}\label{fig:Example1}
\end{figure}

\begin{example} \label{ex1}
Consider the bivariate polynomial
\[ G(t,s) = 3s^4t^4 - 6s^4t^3 + 3s^4t^2 - 6s^2t^4 - s^2t^2 + 2s^2t - s^2 + 2t^2. \]
The vertical line $\LLL := \{t = t_0 := 2\}$ does not intersect the zeroset of $G$ in a point where $G_s$ vanishes, since the discriminant of $g(\xi) := G(t_0, \xi) = 12\xi^4 - 97\xi^2 + 8$ is nonzero (see Figure \ref{fig:Example1}). Evaluating \eqref{eq:difffunc} at $\bfp_0 = (2,\xi)$ yields
\begin{align*}
s'_0  & = -\frac{18\xi^4-97\xi^2+4}{\xi(24\xi^2-97)}, \\
s''_0 & =  \frac{16416\xi^{10}-206316\xi^8+879669\xi^6-1387682\xi^4+55302\xi^2+1552}{\xi^3(24\xi^2-97)^3}.
\end{align*}
When $d\neq 0$, we may assume $d=1$ and Equations \eqref{eq:abcd=1} yield
\begin{align*}
c_1(\xi) & = -\frac{1}{2}\frac{16416\xi^{10}-206316\xi^8+879669\xi^6-1387682\xi^4+55302\xi^2+1552}{6048\xi^{10}-66636\xi^8+256371\xi^6-456385\xi^4+17666\xi^2+1552},\\
a_1(\xi) & = -\frac{1}{2}\frac{\xi(72\xi^8+2019\xi^6-21192\xi^4+40138\xi^2-4656)}{504\xi^8-5511\xi^6+20905\xi^4-36290\xi^2-1552},\\
b_1(\xi) & = -\frac{(9504\xi^{10}-163836\xi^8+879621\xi^6-1434145\xi^4+133646\xi^2-4656)\xi}{(504\xi^8-5511\xi^6+20905\xi^4-36290\xi^2-1552)(12\xi^2-1)}.
\end{align*}
Substituting these expressions into the resultant $\Res_s (F, G)$ and taking the gcd of the numerators of its coefficients and $g$ yields a polynomial $R_1(\xi)=\xi^2 - 8$. We find $F_1(t,s) = -st+\sqrt{2}t+s$ for $\xi = \sqrt{8}$ and $F_2(t,s)=-st-\sqrt{2}t+s$ for $\xi=-\sqrt{8}$ as factors of $G$. In the case $d=0$, we may assume $c=1$ and we get
\[ a_0(\xi) = - \frac{(\xi^2 - 8)(12\xi^2 - 1)}{\xi(24\xi^2 - 97)}, \qquad b_0(\xi) = 4 \frac{18\xi^4 - 97\xi^2 + 4}{ \xi(24\xi^2 - 97)}. \]
Here $R_0(\xi)=12\xi^2-1$ and we obtain $F_3(t,s)=st-\frac{1}{3}\sqrt{3}$ for $\xi=1/\sqrt{12}$ and $F_4(t,s)=st+\frac{1}{3}\sqrt{3}$ for $\xi=-1/\sqrt{12}$. The entire computation takes a fraction of a second when implemented in {\tt Sage} on a modern laptop. For more details we refer to the worksheet accompanying this paper \cite{WebsiteGeorg}.
\end{example}

\begin{algorithm}[h!]
\begin{algorithmic}[1]
\REQUIRE A proper parametrization $\bfx$ of a space curve $\CCC$, not a line or a circle.
\ENSURE The number of symmetries $f(\bfx) = \mQ\bfx + \bfb$, with $\det(\mQ)=\pm 1$, of $\CCC$.
\STATE Find the bivariate polynomials $K, T^\pm$, and $G^\pm$ from \eqref{eq:G} and \eqref{eq:KT}.
\STATE Find the resultant $\Res_s(F, G^\pm)$, with $F$ as in \eqref{eq:F}.
\STATE Let $t_0$ be such that the discriminant of $g^\pm (\xi) := G^\pm(t_0, \xi)$ does not vanish.
\STATE Find the gcd $R_1(\xi)$ of $g^\pm$ and the numerators of the coefficients of the polynomial $P_1(t)$ obtained by substituting $d = 1$ and \eqref{eq:abcd=1} into $\Res_s(F, G^\pm)$.
\STATE Find the real roots of $R_1(\xi)$ for which \eqref{eq:kappatauts} is well defined, each defining a M\"obius transformation by substituting \eqref{eq:abcd=1} and $d = 1$ in \eqref{eq:Moebius}.
\STATE Let $n_1$ be the number of these M\"obius transformations satisfying \eqref{new-cond}.
\STATE Find the gcd $R_0(\xi)$ of $g^\pm$ and the numerators of the coefficients of the polynomial $P_0(t)$ obtained by substituting $c = 1$, $d = 0$, \eqref{eq:ab} into $\Res_s(F, G^\pm)$.
\STATE Find the real roots of $R_0(\xi)$ for which \eqref{eq:kappatauts} is well defined, each defining a M\"obius transformation by substituting \eqref{eq:ab}, $c = 1$ and $d = 0$ in \eqref{eq:Moebius}.
\STATE Let $n_0$ be the number of these M\"obius transformations satisfying \eqref{new-cond}.
\STATE Return ``{\tt The curve has $n_0 + n_1$ symmetries with $\det(\mQ) = \pm 1$}''.
\end{algorithmic}
\caption*{{\bf Algorithm} {\tt Symm$^\pm$}}
\end{algorithm}

\subsection{The complete algorithm} \label{sec-alg}
\noindent Let $\bfx: \RR \dashrightarrow \CCC$ as in \eqref{eq:parametrizations} be a parametric curve of degree $m$. Distinguishing the cases $d = 0, 1$, each tentative M\"obius transformation can be written as \begin{equation*}
\varphi_\xi(t) = \frac{a_d(\xi)t + b_d(\xi)}{c_d(\xi)t + d},
\end{equation*}
with $\xi$ a root of $R_d$ and $a_d, b_d, c_d$ as in \eqref{eq:abcd=1}, \eqref{eq:ab}. Condition \eqref{new-cond} can be checked as follows. Squaring and clearing denominators yields an equivalent polynomial condition
\begin{equation}\label{eq:W}
W_\xi(t) = w_n(\xi)t^n + w_{n-1}(\xi)t^{n-1} + \cdots + w_0(\xi) \equiv 0
\end{equation}
of degree $n\leq 24m - 4$. By Theorem \ref{funda-sym}, a root $\xi$ of $R_d$ corresponds to a symmetry of $\CCC$ precisely when $W_\xi(t)$ vanishes identically. In other words, every root $\xi$ of
\begin{equation}\label{gcd}
\gcd (R_d, w_0,\ldots,w_n)
\end{equation}
defines a M\"obius transformation $\varphi_\xi$ corresponding to a symmetry $f_\xi := \bfx \circ \varphi_\xi \circ \bfx^{-1}$ as in Theorem~\ref{th-fund}. We thus arrive at Algorithm {\tt Symm$^\pm$} for determining the number of symmetries of the curve $\CCC$.

\section{Determining the symmetries} \label{sec-find}
\noindent Algorithm {\tt Symm$^\pm$} detects whether the parametric curve $\bfx$ from \eqref{eq:parametrizations} has nontrivial symmetries. In the affirmative case we would like to determine these symmetries. By Theorem~\ref{th-fund}, every such symmetry corresponds to a M\"obius transformation $\varphi = (at + b)/(ct + d)$, which corresponds to a M\"obius-like factor $F$ of $G$ computed by Algorithm {\tt Symm$^\pm$}. In this section we shall see how the symmetry $f(\bfx) = \mQ\bfx+\bfb$ can be computed from $\varphi$.

The commutative diagram in Theorem \ref{th-fund} describes the identity
\begin{equation} \label{fund-equality}
\mQ \bfx(t)+\bfb=\bfx\big(\varphi(t)\big).
\end{equation}
Let us distinguish the cases $d\neq 0$ and $d = 0$. In the latter case, \eqref{fund-equality} becomes
\[ \mQ\bfx(t) + \bfb = \bfx\big(\varphi(t)\big) = \bfx\big(\ta / t + \tb \big),\qquad \ta := b/c,\qquad \tb := a/c.\]
Applying the change of variables $t\longmapsto 1/t$ and writing $\tbfx(t) := \bfx(1/t)$, we obtain
\begin{equation} \label{spec}
\mQ\bfx(t) + \bfb =  \tbfx\big(\ta t + \tb\big).
\end{equation}
Without loss of generality, we assume that $\bfx(t)$ (respectively $\tbfx(t)$), and therefore any of its derivatives, is well defined at $t=\tb$ (respectively $t=0$), and that $\bfx'(0),\bfx''(0)$ are well defined, nonzero, and not parallel. The latter statement is equivalent to requiring that the curvature $\kappa_\bfx (t)$ at $t=0$ is well defined and distinct from $0$. This can always be achieved by applying a change of parameter of the type $t\longmapsto t+\alpha$. Observe that $\varphi(t)$ can be determined before applying this change, because afterwards the new M\"obius transformation is just $\varphi(t+\alpha)$.

Evaluating \eqref{spec} at $t = 0$ yields
\begin{equation}\label{eq:evaldzero}
\mQ\bfx(0) + \bfb = \tbfx(\tb),
\end{equation}
while differentiating once and twice and evaluating at $t=0$ yields
\begin{equation}\label{eq:diff12dzero}
\mQ\bfx'(0) = \ta \cdot \tbfx'(\tb),\qquad \mQ\bfx''(0) = \ta^2\cdot \tbfx''(\tb).
\end{equation}
Using \eqref{eq:cross} and that $\mQ$ is orthogonal, taking the cross product in \eqref{eq:diff12dzero} yields
\begin{equation}\label{eq:diff1xdiff2dzero}
\mQ\big( \bfx'(0)\times \bfx''(0) \big) = \det(\mQ)\cdot \ta^3\cdot \tbfx'(\tb) \times \tbfx''(\tb).
\end{equation}
Multiplying $\mQ$ by the matrix $\mB := [\bfx'(0),\ \bfx''(0),\ \bfx'(0) \times \bfx''(0)]$ therefore gives
\[ \mC := \big[\ta\cdot \tbfx'(\tb),\ \ta^2\cdot \tbfx''(\tb) ,\ \det(\mQ)\cdot \ta^3 \cdot \tbfx'(\tb) \times \tbfx''(\tb)\big] \]
and $\mQ = \mC\mB^{-1}$. One sets $\det(\mQ) = 1$ to find the orientation-preserving symmetries, and $\det(\mQ) = -1$ to find the orientation-reversing symmetries. One finds $\bfb$ from \eqref{eq:evaldzero}.

Next we address the case $d\neq 0$. After dividing the coefficients of $\varphi$ by $d$, we may assume $d=1$. As before, we assume that $\bfx(t)$ is well defined at $t=0$, and we again assume that the curvature $\kappa_\bfx (0)$ is well defined and nonzero. Differentiating \eqref{fund-equality} once and twice,
\begin{align}
\mQ\bfx'(t)  & = \bfx'\big(\varphi(t)\big)\cdot\varphi'(t) = \bfx'\left(\frac{a t + b}{c t + 1}\right)\frac{\Delta}{(c t + 1)^2}, \label{eq:first}\\
\mQ\bfx''(t) & = \bfx''\big(\varphi(t)\big)\big(\varphi'(t)\big)^2 + \bfx'\big(\varphi(t)\big)\varphi''(t) \label{eq:second}\\
           & =\displaystyle{\bfx''\left(\frac{a t + b }{c t + 1 }\right) \frac{\Delta^2}{(c t + 1 )^4} - 2\bfx'\left(\frac{a t + b}{c t + 1}\right) \frac{c \Delta}{(c t + 1)^3}}. \notag
\end{align}
Evaluating \eqref{eq:first} and \eqref{eq:second} at $t = 0$ yields
\begin{equation}\label{eq:diff12}
\mQ \bfx'(0)  = \bfx' (b)\cdot \Delta,\qquad
\mQ \bfx''(0) = \bfx''(b)\cdot \Delta^2 - 2 \bfx'(b)\cdot c\Delta.
\end{equation}
Using \eqref{eq:cross} and that $\mQ$ is orthogonal, taking the cross product in \eqref{eq:diff12} yields
\begin{equation}\label{eq:diff1xdiff2}
\mQ\big(\bfx'(0) \times \bfx''(0) \big)  = \det(\mQ)\cdot \Delta^3 \cdot \bfx'(b) \times \bfx''(b) .
\end{equation}
Since $\varphi$ is known, the matrix $\mQ$ can again be determined from its action on $\bfx'(0), \bfx''(0)$, and $\bfx'(0) \times \bfx''(0)$, which is given by Equations \eqref{eq:diff12} and \eqref{eq:diff1xdiff2}. One finds $\bfb$ by evaluating \eqref{fund-equality} at $t = 0$.

Once $\mQ$ and $\bfb$ are found, one can compute the set of fixed points of $f(\bfx) = \mQ\bfx + \bfb$ to determine the elements of the symmetry, i.e., the symmetry center, axis, or plane.

\begin{example} \label{ex2}
Let $\CCC\subset \RR^3$ be the crunode space curve parametrized by
\[\bfx : t\longmapsto \left(\frac{t}{t^4+1},\frac{t^2}{t^4+1},\frac{t^3}{t^4+1}\right). \]
Applying Algorithm {\tt Symm$^+$} we get $G^+(t,s)=(t-s)(t+s)$. The first factor corresponds to the identity map $\varphi_1(t) = t$ and the trivial symmetry $f_1(\bfx) = \bfx$. The second factor corresponds to the M\"obius transformation $\varphi_2(t)=-t$. Clearly $\varphi_2$ satisfies Condition \eqref{new-cond}, so that Theorem \ref{funda-sym} implies that $\CCC$ has a nontrivial, direct symmetry $f_2(\bfx) = \mQ_2\bfx + \bfb_2$. With $a=-1$, $b=0$, $c=0$, $d=1$, and using that $\det(\mQ) = 1$,
\[ \mB = \left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & 2\end{array}\right],\
   \mC = \left[\begin{array}{ccr} -1 & 0 & 0\\ 0 & 2 & 0\\ 0 & 0 & -2\end{array}\right],\
   \mQ_2 := \mC \mB^{-1} = \left[\begin{array}{ccr} -1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1\end{array}\right]. \]
Evaluating \eqref{fund-equality} at $t = 0$ gives $\bfb_2 = (\mI - \mQ_2)\bfx(0)=0$, so that $\CCC$ is invariant under $f_2(\bfx) = \mQ_2\bfx$, which is a half-turn about the $y$-axis. Since there are no other factors in $G^+$, there are no direct symmetries corresponding to a M\"obius transformation with $d=0$.

As for the opposite symmetries, applying Algorithm {\tt Symm$^-$} yields $G^-(t,s) = (st-1)(st+1)$, whose factors correspond to the M\"obius transformations $\varphi_3(t)=1/t$ and $\varphi_4(t)=-1/t$. A direct computation shows that $\varphi_3$ and $\varphi_4$ satisfy Condition \eqref{new-cond}, and that they correspond to symmetries $f_3(\bfx) = \mQ_3 \bfx$ and $f_4(\bfx) = \mQ_4 \bfx$, with
\[ \mQ_3 = \left[\begin{array}{ccr} 0 & 0 &  1\\ 0 & 1 & 0\\  1 & 0 & 0\end{array}\right],\qquad
   \mQ_4 = \left[\begin{array}{ccr} 0 & 0 & -1\\ 0 & 1 & 0\\ -1 & 0 & 0\end{array}\right]. \]
The sets of fixed points of these isometries are the planes $\Pi_3 : z - x = 0$ and $\Pi_4 : z + x = 0$, which intersect in the symmetry axis of the half-turn; see Figure~\ref{fig:crunode}.
\end{example}

\begin{figure}
\begin{center}
\includegraphics[scale=0.16]{Crunode}
\includegraphics[scale=0.16]{Daisy1}
\end{center}
\caption{Left: The crunode curve from Example \ref{ex2}, together with the fixed points of the half-turn and mirror symmetries. Right: The daisy of degree 8 from Example \ref{ex:daisy}, together with the fixed points of the central inversion, half-turn, and mirror symmetries.}\label{fig:crunode}
\end{figure}

\begin{example}\label{ex:daisy}
Consider the family of \emph{daisies} of increasing degree $m = 4j + 4$, which are given parametrically by
\begin{equation}\label{eq:daisies}
\bfx(t) = \left(
u\sum_{i=0}^j (-1)^i {2j\choose 2i} u^{2j - 2i} v^{2i},
v\sum_{i=0}^j (-1)^i {2j\choose 2i} u^{2j - 2i} v^{2i},
\frac{1 - t^{4j + 4}}{1 + t^{4j + 4}}
\right),
\end{equation}
with
\[ u = \frac{1-t^2}{1+t^2},\qquad v = \frac{2t}{1+t^2}, \qquad j = 0, 1, \ldots \]
Applying Algorithm {\tt Symm$^+$} for the case $j = 1$, we get $G^+(t,s) = (t-s)(st - 1)$. The first factor again corresponds to the trivial symmetry $f_1(\bfx) = \bfx$. The second factor corresponds to the M\"obius transformation $\varphi_2(t) = 1/t$. Clearly $\varphi_2$ satisfies Condition \eqref{new-cond}, so that Theorem \ref{funda-sym} implies that $\CCC$ has a nontrivial, direct symmetry $f_2(\bfx) = \mQ_2\bfx + \bfb_2$. With $a=0$, $b=1$, $c=1$, $d=0$, and using that $\det(\mQ) = 1$,
\[ \mB = \left[\begin{array}{ccc} 0 & -20 & 0\\ 2 & 0 & 0\\ 0 & 0 & 40\end{array}\right],\
   \mC = \left[\begin{array}{ccr} 0 & 20 & 0\\ 2 & 0 & 0\\ 0 & 0 & -40\end{array}\right],\
   \mQ_2 := \mC \mB^{-1} = \left[\begin{array}{ccr} -1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1\end{array}\right]. \]
Equation \eqref{eq:evaldzero} gives $\bfb_2 = \tbfx(\tb) - \mQ_2\bfx(0) = 0$, so that $\CCC$ is invariant under $f_2(\bfx) = \mQ_2\bfx$, which is a half-turn about the $y$-axis.

Similarly applying Algorithm {\tt Symm$^-$}, we get $G^-(t,s) = (s+t)(st+1)$, whose factors correspond to the M\"obius transformations $\varphi_3(t)=-t$ and $\varphi_4(t)=-1/t$. A direct computation shows that $\varphi_3$ and $\varphi_4$ satisfy Condition \eqref{new-cond}, and that they correspond to symmetries
\[ f_3(\bfx) = \begin{bmatrix}  1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 &  1 \end{bmatrix}\bfx,\qquad
   f_4(\bfx) = \begin{bmatrix} -1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & -1 \end{bmatrix}\bfx, \]
which are a reflection in the plane $\Pi_3: y = 0$ and a central inversion about the point $(0,0,0)$, respectively; see Figure~\ref{fig:crunode}.
\end{example}

\section{Performance} \label{exp-sec}

\subsection{Complexity} \label{sec:complexity}
\noindent
Let us determine the \emph{arithmetic} complexity of Algorithm {\tt Symm$^\pm$}, i.e., the number of integer operations needed. In addition to using the standard Big O notation $\OOO$ for the space- and time-complexity analysis, we use the \emph{Soft O} notation $\tOOO$ to ignore any logarithmic factors in the time-complexity analysis. The \emph{bitsize} $\tau$ of an integer $k$ is defined as $\tau = \lceil \log_2 k \rceil + 1$; the bitsize of a parametrization~$\bfx$ (taken with integer coefficients) is the maximum bitsize of the coefficients of the  numerators and denominators of the components. The following theorem presents the arithmetic complexity of Algorithm {\tt Symm$^\pm$} when applied to parametric curves of varying degree $m$ and of fixed bitsize.

\begin{theorem}
For a parametric curve $\bfx$ as in \eqref{eq:parametrizations} with degree $m$, Algorithm {\tt Symm$^\pm$} finishes in $\tOOO(m^5)$ integer operations.
\end{theorem}

\begin{proof}
\emph{Step 1}. Using the Sch\"onhage-Strassen algorithm, two polynomials of degree $m$ with integer coefficients can be multiplied in $\tOOO(m)$ operations \cite[Table 8.7]{VonZurGathen.Gerhard}. Therefore the computation of $\kappa^2$ and $\tau$ can be carried out in $\tOOO(m)$ operations as well, resulting in rational functions whose numerators and denominators have degree $\OOO(m)$. As a consequence, $K$ and $T = T^\pm$ can also be computed in $\tOOO(m)$ operations, and have degrees $\OOO(m)$ in $t$ and $s$. The bivariate gcd $G = G^\pm$ can be computed in $\tOOO(m^5)$ operations using the `half-gcd algorithm' \cite{Reischert}, and has degree $\OOO(m)$ in both variables. Step 1 therefore takes at most $\tOOO(m^5)$ operations.

\emph{Step 2}. Since $F(t,s) = (ct + d)s - (at + b)$, the resultant $\Res_s(F,G)$ is the polynomial in $t$ obtained by replacing $s$ by $(at + b)/(ct + d)$ and clearing denominators. Writing $G(t, s) = \sum_{k=0}^{m_0} G_k(t) s^k$ as a sum of $m_0 + 1 = \OOO(m)$ terms, with each
$G_k(t)$ a polynomial of degree $\OOO(m)$, gives
\begin{align}\label{eq:resFG}
\Res_s(F, G) &= \sum_{k=0}^{m_0} G_k(t) ( a t + b )^k ( c t + 1 )^{m_0 - k},
\end{align}
which is a polynomial of degree $\OOO(m)$ in $a,b,c$, and $t$.

\emph{Step 3}. For any integer $t_0$, the two polynomials $G(t_0, s)$, $G_s(t_0, s)$ have degree $\OOO(m)$, so that their (univariate) gcd can be computed in $\tOOO(m)$ operations \cite[Corollary 11.6]{VonZurGathen.Gerhard}. Since we need to consider at most $\OOO(m^2)$ values of $t_0$, Step 3 takes $\tOOO(m^3)$ operations.

\emph{Step 4}. For any integer $t_0$ and unknown $\xi$, evaluating \eqref{eq:difffunc} at $(t_0, \xi)$ takes $\OOO(m^2)$ operations, yielding rational functions $s_0'(\xi)$ and $s_0''(\xi)$ whose numerator and denominator have degree $\OOO(m)$. Substituting these rational functions into \eqref{eq:abcd=1} takes $\tOOO(m)$ operations and yields rational functions
\begin{equation}\label{eq:aibici}
   a(\xi) = \frac{a_1(\xi)}{a_2(\xi)},\qquad
   b(\xi) = \frac{b_1(\xi)}{b_2(\xi)},\qquad
   c(\xi) = \frac{c_1(\xi)}{c_2(\xi)},
\end{equation}
whose numerator and denominator have degree $\OOO(m)$. Substituting these rational functions into \eqref{eq:resFG} followed by binomial expansion, i.e., computing
\begin{equation}\label{eq:binexp}
\frac{\displaystyle \sum_{n = 0}^k {k\choose n} a_1^n b_2^{m_0 - k + n} b_1^{k-n} a_2^{m_0 - n} t^n}{a_2^{m_0} b_2^{m_0}},\qquad
\frac{\displaystyle \sum_{n = 0}^{m_0 - k} {m_0 - k\choose n} c_1^n c_2^{m_0-n} t^n}{c_2^{m_0}},
\end{equation}
involves raising polynomials of degree $\OOO(m)$ to the power $\OOO(m)$, which can be computed in $\tOOO(m^2)$ operations using repeated squaring, i.e., $\OOO(\log m)$ multiplications of polynomials of degree $\OOO(m^2)$. All powers $a_i^l, b_i^l, c_i^l$, with $i = 1,2$ and $l = 0, \ldots, m_0$, in the above expression can therefore be computed in $\tOOO(m^3)$ operations, resulting in polynomials of degree $\OOO(m^2)$ in $\xi$. All remaining products can be computed in $\tOOO(m^3)$ operations, resulting in polynomials of degree $\OOO(m^2)$.

Now the rational functions in \eqref{eq:binexp} are determined, the product of their numerators can be carried out in $\tOOO(m)$ ring operations, the ring now being the polynomials in $\xi$. Since these polynomials have degree $\OOO(m^2)$, the product of $G_k(t)$ and the rational functions in \eqref{eq:binexp} takes $\tOOO(m^2)$ integer operations, and yields the terms in the sum \eqref{eq:resFG}. After factoring out the common denominator $(a_2 b_2 c_2)^{m_0}$, this sum involves $\OOO(m)$ polynomials of degree $\OOO(m)$ in $t$, which requires $\OOO(m^2)$ additions of polynomials of degree $\OOO(m^2)$ in $\xi$. This involves $\OOO(m^4)$ integer operations and yields a polynomial of degree $\OOO(m)$ in $t$, whose coefficients $P_i(\xi)$ are polynomials of degree $\OOO(m^2)$. The gcd of $g(\xi)$ with the $P_i(\xi)$ can be computed in $\tOOO(m^3)$ operations, resulting in a polynomial $R_1(\xi)$ of degree $\OOO(m)$, since $g(\xi)$ has degree $\OOO(m)$. Step~4 therefore takes $\OOO(m^4)$ operations.

\emph{Step 5}. One determines whether $R_1(\xi)$ has real roots using root isolation, which takes $\tOOO(m)$ operations using Pan's algorithm for root isolation \cite{Pan, Mehlhorn}.

\emph{Step 6}. Writing $\bfx = (x, y, z) = (x_1/x_2, y_1/y_2, z_1/z_2)$, we find that
\[ \|\bfx'\|^2 = \frac{(x_2x_1' - x_1x_2')^2 y_2^4 z_2^4 + (y_2y_1' - y_1y_2')^2 x_2^4 z_2^4 + (z_2z_1' - z_1z_2')^2 x_2^4 y_2^4}{x_2^4 y_2^4 z_2^4} \]
can be computed in $\OOO(m)$ operations. From Step 3 we already know the expansions of the powers $(at + b)^l, (ct + d)^l$ and their products, thus determining $x\circ \varphi$. Taking the derivative of $x\circ \varphi$ and then squaring involves multiplying and adding polynomials of degree $\OOO(m)$ in $t$ and $\OOO(m^2)$ in $\xi$, which requires $\tOOO(m^2)$ operations. Similarly we determine $[(y \circ \varphi)']^2$ and $[(z \circ \varphi)']^2$ in $\tOOO(m^2)$ operations. The resulting rational functions have numerator and denominator of degree $\OOO(m)$ in $t$ and $\OOO(m^2)$ in $\xi$, and can be added in $\tOOO(m^2)$ operations. Clearing denominators again takes $\tOOO(m^2)$ operations and results in the polynomial $W_\xi(t)$ from \eqref{eq:W} of degree $\OOO(m)$ in $t$ and of degree $\OOO(m^2)$ in $\xi$. To compute \eqref{gcd}, we need to compute $\OOO(m)$ times the univariate gcd of polynomials of degree $\OOO(m)$ and degree $\OOO(m^2)$, which requires $\tOOO(m^3)$ operations.
Step~6 therefore requires $\tOOO(m^3)$ operations.

\emph{Steps 7--10}. These steps have the same complexity as Steps 4--6.
\end{proof}

Note that resorting to probabilistic algorithms, the bivariate gcd $G$ in Step~1 can be computed in $\tOOO(m^2)$ operations using the `small primes modular gcd algorithm' and fast polynomial arithmetic \cite[Corollary 11.9.(i)]{VonZurGathen.Gerhard}. Thus a probabilistic version of Algorithm {\tt Symm$^\pm$} uses $\OOO(m^4)$ operations.

\begin{table}
\begin{tabular*}{\columnwidth}{@{ }@{\extracolsep{\stretch{1}}}*{1}{lcrr}@{ }}
\toprule
curve & degree & $t_{\mbox{old}}$ & $t_{\mbox{new}}$ \\
\midrule
twisted cubic &  3 &  0.26 & 0.15 \\
cusp          &  4 &  0.52 & 0.16 \\
half-turn 1   &  4 &  2.22 & 0.14 \\
crunode       &  4 & 39.60 & 0.42 \\
inversion 1   &  7 &  6.80 & 0.19 \\
space rose    &  8 & 57.60 & 0.25 \\
inversion 2   & 11 & 75.60 & 0.22 \\
\bottomrule
\end{tabular*}
\caption{Average CPU time (seconds) of the algorithm in \cite{AHM13-2} ($t_\text{old}$) and Algorithm {\tt Symm$^\pm$} ($t_{\text{new}}$) for parametric curves given in \cite{AHM13-2}.}\label{tab:spaceinvolutions}
\end{table}

\subsection{Experimentation} \label{exp}
\noindent Algorithm {\tt Symm$^\pm$} was implemented in the computer algebra system {\tt Sage} \cite{sage}, using {\tt Singular} \cite{singular} as a back-end, and was tested on a Dell XPS 15 laptop, with 2.4 GHz i5-2430M processor and 6 GB RAM. Additional technical details are provided in the {\tt Sage} worksheet, which can be downloaded from the third author's website \cite{WebsiteGeorg} and can be tried out online by visiting {\tt SageMathCloud}~\cite{SageMathCloud}.

\begin{table}
\begin{tabular*}{\columnwidth}{@{ }@{\extracolsep{\stretch{1}}}*{1}{cccccc}@{ }}
\toprule
& \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose1}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose2}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose3}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose4}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose5}\hspace{-0.5em} \\
degree         &    8 &   12 &   16 &   20 &   24 \\
$t_\text{new}$ & 0.66 & 0.92 & 1.47 & 2.30 & 4.38 \\
\midrule
& \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose6}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose7}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose8}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose9}\hspace{-0.5em} &
  \hspace{-0.5em}\includegraphics[scale = 0.1]{SpaceRose10}\hspace{-0.5em} \\
degree         &   28 &   32 &   36 &    40 &    44 \\
$t_\text{new}$ & 5.33 & 6.53 & 8.77 & 15.88 & 18.11 \\
\bottomrule
\end{tabular*}
\caption{Average CPU time $t_\text{new}$ (seconds) of Algorithm {\tt Symm$^\pm$} for daisies of various degrees.}\label{tab:spacerose}
\end{table}

We present tables with timings corresponding to different groups of examples. Table \ref{tab:spaceinvolutions} corresponds to the set of examples in \cite{AHM13-2}, making it possible to compare the timing $t_\mathrm{new}$ of Algorithm {\tt Symm$^\pm$} to the timing $t_\mathrm{old}$ of the algorithm in \cite{AHM13-2}. It is clear from the table that the algorithm introduced in this paper is considerably faster for each curve.

To test Algorithm {\tt Symm$^\pm$} for symmetric curves with higher degree, Table~\ref{tab:spacerose} lists the timings for a family of daisies of increasing degree $m = 4j + 4$, parametrically given by \eqref{eq:daisies}. The algorithm quickly finds the symmetries of these symmetric curves, also for high degree.

\begin{table}[t!]
\begin{tabular*}{\columnwidth}{m{5em}@{\extracolsep{\stretch{1}}}*{1}{rrrrrrrrrr}}
\toprule
$t_\text{new}$ &  $\tau = 4$ &  $\tau = 8$ & $\tau = 16$ & $\tau = 32$ & $\tau = 64$ & $\tau = 128$ & $\tau = 256$ \\ \midrule
$m=4$  &          0.61 &          0.62 &          0.66 &          0.73 &          0.83 &          1.14 &          1.88 \\
$m=6$  &          1.65 &          1.76 &          1.72 &          1.89 &          2.13 &          2.80 &          4.55 \\
$m=8$  &          3.50 &          3.54 &          3.55 &          3.84 &          4.27 &          5.36 &          8.59 \\
$m=10$ &          7.53 &          7.47 &          7.30 &          7.98 &          8.42 &          9.76 &         15.35 \\
$m=12$ &         14.46 &         14.35 &         14.30 &         14.84 &         15.98 &         18.35 &         25.87 \\
$m=14$ &         22.31 &         23.24 &         22.39 &         22.71 &         24.93 &         27.35 &         38.36 \\
$m=16$ &         34.86 &         35.60 &         35.38 &         35.27 &         38.14 &         41.91 &         55.74 \\
$m=18$ &         53.03 &         52.78 &         52.78 &         51.16 &         54.49 &         60.44 &         78.27 \\

\bottomrule
\end{tabular*}
\caption{CPU times $t_{\text{new}}$ (seconds) for random dense rational parametrizations of various degrees $m$ and coefficients with bitsize bounded by $\tau$.}\label{tab:sizedegree}
\end{table}

\begin{table}[t!]
\begin{tabular*}{\columnwidth}{m{5em}@{\extracolsep{\stretch{1}}}*{1}{rrrrrrrrrr}}
\toprule
$t_\text{new}$ &  $\tau = 4$ &  $\tau = 8$ & $\tau = 16$ & $\tau = 32$ & $\tau = 64$ & $\tau = 128$ & $\tau = 256$ \\ \midrule
$m=4$  &      0.85 &      0.89 &      0.91 &      0.97 &      1.12 &      1.51 &      2.39 \\
$m=6$  &      1.89 &      2.02 &      1.99 &      2.21 &      2.57 &      3.36 &      5.40 \\
$m=8$  &      4.08 &      4.24 &      4.52 &      5.16 &      5.45 &      7.42 &     10.41 \\
$m=10$ &      8.29 &      8.80 &      8.88 &      9.30 &     10.74 &     12.64 &     19.87 \\
$m=12$ &     17.47 &     18.20 &     17.96 &     17.12 &     18.49 &     25.19 &     34.11 \\
$m=14$ &     28.54 &     28.72 &     29.55 &     28.54 &     31.87 &     34.71 &     44.19 \\
$m=16$ &     41.20 &     41.53 &     42.02 &     43.07 &     45.55 &     51.36 &     65.58 \\
$m=18$ &     58.42 &     58.91 &     59.54 &     61.08 &     64.31 &     71.89 &     94.33 \\
\bottomrule
\end{tabular*}
\caption{CPU times $t_{\text{new}}$ (seconds) for random dense rational parametrizations with a central inversion of various degrees $m$ and coefficients with bitsize bounded by $\tau$.}\label{tab:sizedegreeinv}
\end{table}

\begin{figure}[t!]
\begin{center}
\includegraphics[scale=0.7]{CPU-time1}\quad
\includegraphics[scale=0.7]{CPU-time2}
\end{center}
\caption{Left: The average CPU time $t_{\text{new}}$ (seconds) versus the degree $m$ for daisies and random dense rational parametrizations with bitsize $\tau = 4$ and with only the trivial symmetry (random) and with an additional central inversion (central), fitted by the power laws \eqref{eq:powerlaw1}--\eqref{eq:powerlaw2} (dotted). Right: The average CPU time $t_{\text{new}}$ (seconds) versus the coefficient bitsizes for degree $m=4$. The symbols indicate the average CPU times, and the error bars show the interval of CPU times.}\label{fig:timings}
\end{figure}

Table \ref{tab:sizedegree} lists average timings for random dense rational parametrizations with various degrees $m$ and coefficients with bitsizes at most $\tau$. To study the effect of an additional nontrivial symmetry, we consider random parametrizations $\bfx = (x_1, x_2, x_3)$ with antisymmetric numerators and symmetric denominators of the same degree $m$ and with bitsize at most $\tau$, i.e., of the form
\[
x_i(t) = \frac
{c_{i,0} + c_{i, 1} t + \cdots - c_{i, 1} t^{m-1} - c_{i, 0} t^m}
{d_{i,0} + d_{i, 1} t + \cdots + d_{i, 1} t^{m-1} + d_{i, 0} t^m},
\qquad i = 1,2,3,
\]
with $\lceil \log_2 |c_{i,j}| \rceil, \lceil \log_2 |d_{i,j}| \rceil \leq \tau - 1$. Since $\bfx(1/t) = - \bfx(t)$, such parametric curves have a central inversion about $\bfx(1) = 0$. Table \ref{tab:sizedegreeinv} lists average timings for these curves with various degrees $m$ and bitsizes at most $\tau$.

For very large coefficient bitsizes ($> 256$, i.e., coefficients with more than 77 digits) and high degrees ($> 20$) the machine runs out of memory. We have therefore analyzed separately the regime with high degree and the regime with large coefficient bitsize.

Figure~\ref{fig:timings} presents log-log plots of the CPU times against the degree (left) and against the coefficient bitsizes (right). The (eventually) linear nature of these data suggests the existence of an underlying power law. Least squares approximation yields that, as a function of the degree $m$, the average CPU time $t_\text{new}$ satisfies
\begin{equation}\label{eq:powerlaw1}
t_\text{new} \sim \alpha m^\beta, \qquad \alpha \approx 6.7\cdot 10^{-3},\qquad \beta\approx 3.2
\end{equation}
in case of random dense rational parametrizations with coefficient bitsize at most $\tau = 4$,
\begin{equation}\label{eq:powerlaw1b}
t_\text{new} \sim \alpha m^\beta, \qquad \alpha \approx 4.7\cdot 10^{-3},\qquad \beta\approx 3.3,
\end{equation}
in case of random dense rational parametrizations with a central inversion and with coefficient bitsize at most $\tau = 4$, and
\begin{equation}\label{eq:powerlaw2}
t_\text{new} \sim \alpha m^\beta, \qquad \alpha \approx 7.9\cdot 10^{-5},\qquad \beta\approx 3.2
\end{equation}
for the daisies. Note that these timings are close to the $\tOOO(m^3)$ operations needed by Brown's modular gcd algorithm \cite{Brown}, which is used in the implementation in {\tt Sage} for bivariate gcd computations. The reason is that in the analyzed examples almost all time is spent computing the bivariate gcd in Step 1, which then typically has low degree, so that the remaining calculations take relatively little time.

\subsection{An observation on plane curves} \label{obs-planar}
\noindent If $\CCC$ is planar, then $\tau$ and $T^\pm$ are identically zero, so that $G^\pm = K$. Although Algorithm {\tt Symm$^\pm$} is still valid for such curves, we have observed a very poor performance in this case. The reason is that, for non-planar curves, the degree of $G^\pm$ is typically small compared to the degrees of $K$ and $T^\pm$. However, for plane curves the degree of $G^\pm$ is equal to the degree of $K$, and then the computation takes a very long time. Therefore, for plane curves, the algorithms in \cite{AHM13} and \cite{AHM13-2} are preferable.

\subsection{Comparison to previous method}
\noindent Table \ref{tab:spaceinvolutions} indicates a dramatic improvement of the CPU time of {\tt Symm$^\pm$} over the method described in \cite{AHM13-2}. In that paper the symmetry $f(\bfx) = Q\bfx + \bfb$ and M\"obius transformation $\varphi(t) = (at + b)/(ct + d)$ are first expressed polynomially in terms of some (yet unknown) algebraic number $\beta$. By far the most CPU time is spent after that, on substituting $a(\beta), b(\beta), c(\beta), Q(\beta)$ and $\mathbf{b}(\beta)$ into the relation
\begin{equation*}\label{eq:fundamentalrelation}
f\big(\bfx(t)\big) - \bfx\big(\varphi(t)\big) \equiv 0.
\end{equation*}
Since the degrees can get very high in this relation, this substitution can take a long time. Then the algebraic numbers $\beta$, and therefore the symmetry and M\"obius transformation, are found by requiring that this relation holds identically.

Furthermore, the method described in \cite{AHM13-2} requires that the parametrization $\bfx$ satisfies rather strict conditions. Quite often, a reparametrization is needed in order to achieve these conditions, which can result in destroying sparseness and increasing the coefficient size. This, in turn, has an impact on the time taken by the substitution step.

By contrast, in Algorithm {\tt Symm$^\pm$} we use additional information provided by the curvature and torsion of the curve to compute $G^\pm_{\bfx}=\gcd(K_{\bfx}, T^\pm_{\bfx})$, whose degree is generally low. The M\"obius transformations are then computed in just one step as factors of $G^\pm_{\bfx}$. As a consequence, no	 substitution step is needed. Moreover, unless $\bfx$ is not proper, no reparametrization is required.

\section{Conclusion} \label{sec-conclusions}
\noindent We have presented a new, deterministic, and efficient method for detecting whether a rational space curve is symmetric. The method combines ideas in \cite{A13, AHM13-2} with the use of the curvature and torsion as differential invariants of space curves. The complexity analysis and experiments show a good theoretical and practical performance, clearly beating the performance obtained in \cite{AHM13-2}. The algorithm also improves in scope on the algorithm of \cite{AHM13-2}, which can only be applied to find the symmetries for Pythagorean-hodograph curves and involutions of other curves. Finally Algorithm {\tt Symm$^\pm$} is simpler than the algorithm in \cite{AHM13-2}, which imposes certain conditions on the parametrization that often lead to a reparametrized, non-sparse curve whose coefficients have a large bitsize. By contrast, the algorithm in this paper has fewer requirements and is efficient even with high degrees.

Note that Algorithm {\tt Symm$^\pm$} is based on two conditions in Theorem \ref{funda-sym}, one involving the curvature and torsion of the curve and the other one involving the arc length. One might wonder whether these two conditions really are independent for the case of rational curves. We included both conditions because we did not succeed in proving that they are dependent, but neither did we find an example of a tentative M\"obius transformation not satisfying Condition \eqref{new-cond}. The relation between the conditions is therefore undetermined, and we pose the question here as an open problem. In any case, in the complexity analysis and experiments we observed that the cost of checking \eqref{new-cond} is small compared to the rest of the algorithm.

The implementation in {\tt Sage} can be improved in several ways. First, several of the methods named in the complexity section are not included in {\tt Sage}, which carries out the corresponding tasks by using other algorithms. Furthermore, almost all space curves are asymmetric, and these cases can be identified faster. In order to do this, one can first remove all factors $s-t$ from $K_\bfx$ and $T^\pm_{\bfx}$, and then check whether the remaining polynomials are coprime using modular arithmetic. In the affirmative case, the conclusion that the curve has no nontrivial symmetries could be obtained at very little computational cost.

As a final remark, as this paper sets forth a method for computing exact symmetries of parametric curves with rational coefficients, one could ask whether a similar development could yield a method for computing approximate symmetries of parametric curves with floating point coefficients. This is an open question that we would like to address in the future.

\section*{Acknowledgments}
\noindent We are very grateful for the detailed reports of the reviewers, which helped to improve the paper significantly, in particular Section \ref{exp-sec}. We also thank Rob Corless for suggesting the term ``daisies'' for the curves in Table 2.

\bigskip

config: arxiv


TITLE: Virasoro constraints in quantization of the Polyakov action
QUESTION [11 upvotes]: The generators of the Virasoro algebra (actually two copies thereof) appear as constraints in the classical theory of the Polyakov action (after gauge fixing). However, when quantizing only "half" of the constraints are imposed.
I understand it's inconsistent to apply all of the constraints. I also understand this choice has mathematical significance in the sense of picking out highest-weight vectors. Nevertheless, on the surface it seems somewhat arbitrary. What is the physical reason it is "ok" to ignore the other constraints while mandatory to impose these? Also, are there simpler (preferably finite dimensional phase space) examples of quantization where some of the constraints must be dropped?

REPLY [9 votes]: You seem to be talking about the "old covariant quantization" in which $L_n$ for positive $n$ and $(L_0-a)$ annihilate physical ket states $|\psi\rangle$, right? It's analogous to the Gupta-Bleuler quantization

http://en.wikipedia.org/wiki/Gupta-Bleuler_quantization

which was a standard procedure used already in electromagnetism. The idea is that the Hermitian conjugate condition guarantees that $L_n$ for a negative $n$ annihilates all the physical bra-vectors $\langle \psi |$. So all the matrix elements
$$ \langle \psi | (L_n - a \delta_{n0}) | \phi \rangle =0 $$
vanishes for all pairs of physical states  because the matrix inside annihilates either the ket vector or the bra vector. A few more conditions follow.
But I want to say that this treatment has become obsolete in the 1970s when people started to describe gauge theories – and analogously, Virasoro- or diff-symmetric gravitational theories (on the world sheet or in spacetime) – by the modern covariant quantization or BRST quantization.
In that new formalism, you have the $bc$ ghosts, the BRST charge, and physical states are cohomologies of $Q$, the BRST charge. In particular, this also allows you to demand that physical states (representatives) are annihilated by all $L_n$ for both signs of $n$.

REPLY [5 votes]: A modern treatment of this subject can be found in Segreev's book on the Kahler geometry of loop spaces also available online. This line of research started with the seminal work of Bowick and Rajeev: The holomorphic geometry of the closed bosonic string theory and $Diff S^1/S^1$ (Spires) (and independently Kirillov and Yuriev (Please see the reference in Sergeev's book)).
The basic idea is that loop spaces are Kahler manifolds carrying a $Diff S^1$ invariant closed two form (Kahler form). ( These manifolds are quantizeable by selection of a complex structure compatible with the Kahler form and performing Kahler (holomorphic) quantization.)
In the present problem, one seeks to define a  $Diff S^1$ equivariant quantizations on them, i.e., to find a representation of $Diff S^1$ invariant functions on these loop spaces as $Diff S^1$ invariant subspace of vectors on a Hilbert space.
The invariant vectors are obtained as null vectors of the quantized algebra.
Now, as many other cases in quantum mechanics, one cannot find a faithful representation at the quantum level but only a projective one.
This means that the $Diff S^1$ invariant subspace can only be trivial.
This is the main reason that the original solution was found by imposition of half the constraints which is reminiscent of the Kahler quantization itself where one selects holomorphic sections.
The modern solution lies in the fact that a given complex structure on the loop space is not invariant under $Diff S^1$. Thus also a given Kahler quantization is not invariant as well.
The vacuum of the Kahler quantization Hilbert space corresponding to a given complex structure is not invariant under $Diff S^1$. The transformed vacuum is the vacuum corresponding to the Kahler quantization associated with the transformed complex structure.
This leads to the notion of the "Vacuum bundle" which is a line bundle over $Diff S^1/S^1$ comprising all the individual vacua. This bundle has a connection associated with the projective representation of $Diff S^1$, which becomes flat when one takes into account all the fields of the theory (in the case of the bosonic string at $d=26$).
The main result is that the flatness of the connection is equivalent to the unitary equivalence of the quantization Hilbert spaces under the action of $Diff S^1$, which is the required result expressing the equivariance of the quantization.
This treatment has many connections to many contemporary research areas. for example the bundle of complex structures over the loop space is a twistor space as was noticed by Bowick and Rajeev in their original work.
Update:
Sorry for never mentioning it in the original answer (It appears in the references), the loop space under consideration is $\Omega \mathbb{R}^{d-1,1}$ (based loops), (becoming $\Omega \mathbb{R}^{d-1,1}//diff S1$ after the Hamiltonian reduction).
The (unitary) equivalence of the three mentioned quantization methods Goddard Goldstone Rebbi Thorn (GGRT- half of the constraints method), BRST and the Bowick-Rajeev (twistor) can be explained as follows:
GGRT-BRST: The BRST invariance condition of the physical states is equivalent by explicit construction to the GGRT half number of constraints, please see Green Schwarz Witten equation: 3.2.31
BRST - Bowick-Rajeev: The inclusion of the ghost sector of the string is equivalent to tensoring with the anticanonical bundle to the Fock bundle of the bosonic string.
This can be understood from the fact that the Ricci tensor of $Diff S1/S1$ is exactly equal to the contribution of the ghost sector to the vacuum bundle curvature (for example by a direct calculation). Thus the half form quantization is equivalent to the introduction of ghosts. This can be further seen in the fact that the physical states have a ghost number of $-\frac{1}{2}$. This is also consistent with the path integral picture, where one must divide by the redundant gauge orbit measure.
In addition to the fact that in this method, one is not required to introduce the ghost fields explicitly, the flatness of the connection establishes the equivalence between the quantizations with respect to different Kahler polarizations.


TITLE: Number theoretic proof that $n\mid\phi(a^n-1)$
QUESTION [3 upvotes]: While 'playing' with the multiplicative group of integers mod $n$, I noticed that $n\mid \phi(a^n-1)$.
The proof is straightforward:

$a \in \left ( \mathbb{Z}/(a^n-1)\mathbb{Z}  \right )^\times$ because $a \equiv 0 \pmod{p} \Leftrightarrow a^n-1 \equiv -1 \pmod{p}$ for a prime $p$, and hence $\gcd(a,a^n-1)=1$
$\left | a \right |=n $ because $ a^n = (a^n-1)+1 \equiv 1 \pmod{a^n-1} $ and if $ 1 \leq k \leq n-1 $ we have $ a<a^k<a^n-1 \Rightarrow a^k\not\equiv 1 \pmod{a^n-1} $ so that $n $ is the smallest positive power for which $a^k \equiv 1$
Finally, by Lagrange's theorem, we get: $\left| a \right| \mid \left|\left ( \mathbb{Z}/(a^n-1)\mathbb{Z}  \right )^\times\right| \Rightarrow n\mid\phi(a^n-1)$

I assumed that such a simple looking identity had to have a simple direct number theoretic explanation, and with my limited knowledge of number theory, I tried to tackle the problem but without success.
I still have a feeling that there is a simple explanation and that I'm just missing the elephant in the room that easily illuminates this fact.
Off Topic: I had difficulty formatting the 'proof' because I am new to $\LaTeX$ and I don't know how things should really be done on this website, so feel free to edit anything to make it "more right", I will certainly appreciate it.

REPLY [1 votes]: The standard "classical" number-theoretic proof is the same. Let $a\gt 1$. We have $a^n\equiv 1\pmod{a^n-1}$, and obviously $a^k\not\equiv 1\pmod{a^n-1}$ if $1\le k\lt n$. So $a$ has order $n$ modulo $a^n-1$, and therefore $n$ divides $\varphi(a^n-1)$.
At the end one does not appeal to Lagrange's Theorem explicitly. But a standard easy early number-theoretic lemma is that if $a$ has order $k$ modulo $m$, then $k$ divides $\varphi(m)$.


TITLE: $\int_0^1\int_x^1f(t) \,dt \,dx=\int_0^1t f(t) \,dt$
QUESTION [4 upvotes]: Lets suppose that f is continuous in $[0,1]$.
I want to prove that $$\int_0^1\int_x^1f(t) \,dt \,dx=\int_0^1t f(t) \,dt$$ for the left part I set the following function: $$F(y)=\int_0^y f(t)\,dt$$ so from the left part I have that
$$\int_0^1\int_x^1f(t)\,dt\,dx$$ $$=\int_0^1(F(1)-F(x))\,dx$$ $$=F(1)-\int_0^1F(x)\,dx$$ $$=F(1)-F(0)-\int_0^1F(x)\,dx$$
Then, I tried to solve the right part by integrating by parts but I got confussed because of the limits of integration.
$u=t$, $du=dt$, $v=\int f(t)\,dt$, $dv=f(t)$.
Here is were I´am stuck, can you help me?

REPLY [0 votes]: I will assume that $f$ is absolutely integrable so that we can apply Fubini. Using Iverson Brackets:
$$
\begin{align}
\int_0^1\int_x^1f(t)\,\mathrm{d}t\,\mathrm{d}x
&=\int_0^1\int_0^1f(t)[t\gt x]\,\mathrm{d}t\,\mathrm{d}x\tag1\\
&=\int_0^1\int_0^1f(t)[t\gt x]\,\mathrm{d}x\,\mathrm{d}t\tag2\\
&=\int_0^1tf(t)\,\mathrm{d}t\tag3
\end{align}
$$
Explanation:
$(1)$: write the inner integral using the indicator function of $t\gt x$
$(2)$: change order of integration
$(3)$: evaluate the integral in $x$


TITLE: Could the complex zeros of Riemann zeta function be of the form $ s=0.5+ik$ with $k$ a positive integer?
QUESTION [1 upvotes]: I have checked in Andrew Odlyzko, Tables of zeros of the Riemann zeta function, to know if there is an example of zeros of Riemann zeta function with integer imaginary parts, but I don't see that. I would like to know if there is an example of zeros as $s=0.5+at$ with $a$ a positive integer .

Now my question here is:
Could the complex zeros of the Riemann zeta function be of the form $ s=0.5+ik$  with $k$ a positive integer?

Thank you in advance.

REPLY [5 votes]: As explained by Peter Humphries in the comments, the famous conjecture here is that the imaginary part of the non-trivial zeros of $\zeta(s)$ is transcendental (or equivalently, linearly independent over $\mathbb{Q}$).
I'm not sure of the origins of the conjecture, but it was certainly around before the Rubinstein-Sarnak paper. Rumely a year before alredy says that it is "generally believed" for all Dirichlet L-functions. Both papers are avaible online:

Robert Rumely, "Numerical Computations Concerning the ERH" (1993)
Michael Rubinstein & Peter Sarnak, "Chebyshev's bias" (1994)

In particular, you can consider the fact that $k$ is not an integer as numerically verified at least in the range in which the RH has (up to $10^{13}$ after Gourdon).


TITLE: Give examples in $(\Bbb R^2, \|\cdot\|_2)$ of a set $A ⊂ \Bbb R^2$ which is open, not closed, not bounded.
QUESTION [0 upvotes]: Somebody please needs to explain to me what I have to do. I have been struggling all day to understand the concepts but I have absolutely no idea what to do. I know what $\Bbb R^2$ is and I know the definition of $\|\cdot\|_2$ but I still don't know what a subset of this set should be, which criteria it should fulfill to be a subset of $(\Bbb R^2, \|\cdot\|_2)$ and then how do I tackle it.
I would really appreciate some understanding. It was taught extremely vaguely in our class and I have been trying all day to find literature or texts which can really help me but they don't, so if someone could explain the concept to me and help me out I would be very glad.
Thanks

REPLY [2 votes]: $$A= \mathbb{R}^2 \setminus \{(0,0)\}$$

Complement of a closed set, thus open.
Not closed, because $(1/n,1/n)\to (0,0)$, or because $\{(0,0)\}$ is not open.
Not bounded is evident.

Other examples (without explanation):

$A=\mathbb{R}^2 \setminus F$ where $F$ is any finite subset of $\mathbb{R}^2$
The complement of any line in the plane.


TITLE: Automorphism group action leads to a "quotient graph"
QUESTION [4 upvotes]: Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.
Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.
Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.
I have two questions

$\cdot$ Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$  (I think the answer is YES)
$\cdot$ If so, how many vertices $H$ must have?

REPLY [3 votes]: I also think that the answer to the first question is yes. Your note shows us that it is enough to consider graphs with non trivial automorphism group. If we can transform them in such a way, that we destroy all the initial (old) automorphisms, without creating vertices that can not be reached by new automorphisms. We are done. I think it can be done this way:
Consider the transformation which takes the $n$-dimensional hypercube to the $n+1$ dimensional one. (Or you can call it Cartesian product with $K_2$) We will do something similar. Take an exact copy of the initial graph $G$, and connect one vertex from each nontrivial orbit to its counterpart. In the resulting graph there will be no old automorphisms which can move them, since they can be moved only to each other, but they are from different orbits. We also did not create unreachable vertices since we can take every vertex to its counterpart and vice versa.
Iterating this procedure we can eliminate every old automorphism, but the number of vertices of the resulting graph grows exponentially with the number of transformations.
EDIT: If we take $n+1$ copies of $G$, and from every nontrivial old orbit, we chose a single vertex, and put a clicque on the vertices corresponding to the chosen one in the copies, then it is clear that the chosen vertices must map to each other.

REPLY [3 votes]: I think the answer to Question 1 is yes, at least for finite graphs.
Lets $(T,E)$ be a graph.
You can choose a group $G$ that is large enough to do the following: For each node $x∈V$ choose a subgroup $G_x$ (called stabilizer) such that the intersection of all subgroups is $\{1\}$ and each subgroup has a different cardinality. Then you can form the graph in the following way:
$$ V= \dot\bigcup_{t∈T} \{gG_t\mid g∈G\}, \mbox{ and } F=\{(gG_s,hG_t)\mid g,h∈G, (s,t)∈E\}.$$
Then each node $t$ is broken up into $|G/G_t|$ pairwise unconnected nodes. And each edge is split up into a complete bipartite graph connecting all equivalent vertices. By changing the group size and the size of the stabilizer you can ensure that any two edges in $F$ have the same valency iff they belong to the same node in $T$.
For more information:

Monika Zickwolff: Darstellung Symmetrischer Strukturen durch Transversale, In: Contributions to General Algebra 7, Teubner, Wien/Stuttgart
Daniel Borchmann and Berhard Ganter: Concept Lattice Orbifolds – First Steps, In: Formal Concept Analysis, LNAI 5548, Springer, p. 22

Edit:
I forgot to mention that each orbit in $(V,F)$ must be connected in certain cases (e.g. considering the lattice family $M_n$ as graphs).
For each node $t∈T$ choose a (connected) Cayley graph $C_t=(G/G_t,E_t)$ and add its edges to $F$ so that the above formula reads
$$F=\{(gG_s,hG_t)\mid g,h∈G, (s,t)∈E\}∪⋃_{t∈T}E_t.$$
Addendum: Size estimation.
Assuming the node are numbered by $1,…,n$, one way to assure that each node has different cardinality is to split each node $i$ into the circle $C_{(n+3)k^i}$. So we get an exponential upper bound.
However, in many cases a much smaller size can be achieved as you have to split up only as many nodes as a minimal system of generators of the automorphism group has (split up nodes instead of linking them to copies in Daniels Answer). E.g., for the complete graph $K_n$ the nodes can be replaced by circles of length $4$ to $n+4$ leading to a total size of $\frac{n(n+1)}{2}+3n$ nodes, which is polynomial. This is probably not the lower bound as it should be possible to replace certain circles by smaller Cayley graphs.


TITLE: Is there MDPs (Markow Decision Process) which have a non deterministic optimal policy ?
QUESTION [7 upvotes]: I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it shown that an optimal policy is always deterministic ?
If a stochastic policy exist, is it shown that some algorithms (like Q-Learning) converge to this policy ?

REPLY [0 votes]: A possible counter example (for negative dynamic programming) is the St. Petersburg paradox in Bertsekas/Shreve, Stochastic Optimal Control: The deterministic case. Academic Press (1978). (Example 3 in Sect. 9.6, p. 241)


TITLE: Law of large numbers, convergence in probabillity
QUESTION [1 upvotes]: Let $(X_n)_n$ i.i.d with distribution function $F_{X_i}(x)=(1-x^{-\lambda})1_{x>1}, \lambda >0$. I calculated the expected value $(\frac{- \lambda}{1-\lambda})\,\textrm for \lambda \in (1,\infty)$ and undefined for $\lambda =1$
I also calculated the distribution from $X:=log(X_1)$.
Now I want to show that $(Y_n)_n :=((X_1X_2 ... X_n)^\frac{1}{n})_{n\in \mathbb N} $ is convergent in Probability and calculate the limes.
My attempt:
I tried to use the law of large numbers to get almost sure convergence (and this implies convergenc in probability),i.e.
$lim_{n\to \infty}\frac{1}{n}\sum_{j=1}^nY_j=\mathbb E(Y_1)$ and $\mathbb E(Y_1) $ is the same like $\mathbb E(X_1)$ but I do not see how this could help me in any way.
Any help is much appreciated!

REPLY [0 votes]: $$
\ln{Y_n}=\frac{1}{n}\sum_{i=1}^n\ln{X_i}\xrightarrow{p}\mathsf{E}\ln{X}_1=\lambda^{-1}.
$$
Thus, $Y_n\xrightarrow{p}e^{1/\lambda}$.

$F_{\ln{X_1}}(x)=\mathsf{P}(\ln{X_1}\le x)=(1-e^{-\lambda x})1\{x\ge 0\}$ and $\mathsf{E}\ln{X_1}=\lambda^{-1}$.


TITLE: Prove the injectivity of a function with two variables and sketch it
QUESTION [0 upvotes]: How can I prove that $f(x,y) = (e^x \cos y, e^x \sin y)$ is injective in $A = \{(x,y) \in R^2 | 0 < y < 2\pi\}$? I know that proving the injectivity is done by proving $f(x, y) = f(z, w) \Rightarrow x = z$ and $y = w$, but I don't know how to continue after making the system.
After that, how can I have a notion of how to sketch this function?

REPLY [0 votes]: HINT: note that $\|f(x,y)\|_2=|e^x|=e^x$, so $f(x,y)=f(z,w)$ imply that $e^x=e^z$, what can just happen when $x=z$, thus we had reduced the exercise to prove that if $y\neq w$ then $f(x,y)\neq f(x,w)$.
Now use what you knows about the sine and cosine to finish. That is, if $\cos y=\cos w$ then show that necessarily $\sin y\neq \sin w$.


TITLE: Understanding proof that $\mathbb{Z}/m\mathbb{Z}\otimes\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/d\mathbb{Z}$
QUESTION [3 upvotes]: I am reading an example in Dummit and Foote showing that $\mathbb{Z}/m\mathbb{Z}\otimes\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/d\mathbb{Z}$, where $d$ is the greatest common divisor of $n$ and $m$, but I'm having trouble understanding one line. We have that $m(1\otimes 1)=m\otimes 1=0$, and similarly $n(1\otimes 1)=(1\otimes n)=0$. The next line states that because of this, we have $d(1\otimes 1)=0$ as well. Why is this so?

REPLY [6 votes]: There exist $s,t\in\mathbb{Z}$ such that $sm+tn=d$.  So $$d(1\otimes 1)=(sm+tn)(1\otimes 1)=sm(1\otimes 1)+tn(1\otimes 1)=s\cdot 0+t\cdot 0=0.$$