text:
\begin{document}

\maketitle

\begin{abstract}
We present an improved method for symbolic regression that seeks to fit data to formulas that are Pareto-optimal, in the sense of having the best accuracy for a given complexity. It improves on the previous state-of-the-art by typically being orders of magnitude more robust toward noise and bad data, and also by discovering many formulas that stumped previous methods. We develop a method for discovering generalized symmetries (arbitrary modularity in the computational graph of a formula) from gradient properties of a neural network fit. We use normalizing flows to generalize our symbolic regression method to probability distributions from which we only have samples, and employ statistical hypothesis testing to accelerate robust brute-force search.
\end{abstract}

\section{Introduction}
\label{IntroSec}

\begin{figure}[phbt]
\centerline{\includegraphics[width=0.6\linewidth]{kinetic_energy.pdf}}
\caption{Our symbolic regression of data on how kinetic energy depends on mass, velocity and the speed of light discovers a Pareto-frontier of four formulas that are each the most accurate given their complexity. Convex corners reveal particularly useful formulas, in this case Einstein's formula and the classical approximation $mv^2/2$.
\label{kineticFig}
}
\end{figure}

A central challenge in science is {\it symbolic regression}:
discovering a symbolic expression that provides a simple yet accurate fit to a given data set.
More specifically, we are given a table of numbers, whose rows are of the form $\{x_1,...,x_n,y\}$ where
 $y=f(x_1,...,x_n)$, and our task is to discover the correct symbolic expression (composing mathematical functions from a user-provided set)
for the unknown mystery function $f$, optionally including the complication of noise and outliers.
Science aside, symbolic regression has the potential to replace some inscrutable black-box neural networks by simple yet accurate symbolic approximations, helping with the timely goal of making
high-impact AI systems more interpretable and reliable \cite{russell2015research, amodei2016concrete, boden2017principles, krakovna2016increasing,russell2019human}.

Symbolic regression is difficult because of the exponentially large combinatorial space of symbolic expressions.
Traditionally, symbolic regression has relied on human intuition, leading to the discovery of some of the most famous formulas in science.
More recently, there has been great progress toward fully automating the process
\cite{crutchfield1987equation, dzeroski1995discovering, bradley2001reasoning, langley2003robust, schmidt2009distilling, mcree2010symbolic, searson2010gptips, dubvcakova2011eureqa, stijven2011separating, schmidt2011automated, hillar2012comment, daniels2015automated, langley2015heuristic, arnaldo2015building, brunton2016discovering, guzdial2017game, quade2018sparse, koch2018mutual, kong2018new, udrescu2020ai, liang2019phillips}, and open-source software now exists that can discover quite complex physics equations by combining neural networks with techniques inspired by physics and information theory \cite{udrescu2020ai}.
The goal of this paper is to further improve this state-of-the-art, by making three main
contributions:
\begin{enumerate}
\item We use learned neural-network gradients to discover and exploit modularity in the function's computational graph.
\item We use statistical hypothesis testing and recursive composition of description-length-based Pareto-frontiers to accelerate and robustify the symbolic regression.
\item We use normalizing flows to enable
regression of probability distributions from samples.
\end{enumerate}
We describe our symbolic regression algorithm in \Sec{MethodsSec} and test it with numerical experiments in \Sec{ResultsSec}.

\section{Method}
\label{MethodsSec}

Our symbolic regression algorithm uses a divide-and-conquer approach as in \cite{udrescu2020ai}.
We directly solve a mystery
in two base cases: if the mystery function
$f(x_1,...,x_n)$ is a low-order polynomial or if it is simple enough to be discovered by brute-force search.
Otherwise, we recursively try the
strategies that we will now describe for
replacing it by one or more simpler mysteries, ideally with fewer input variables.

\subsection{Leveraging graph modularity against the curse of dimensionality}
\label{ModularitySubsec}

\begin{figure}[phbt]
\centerline{\includegraphics[width=\linewidth]{modules.pdf}}
\caption{All functions can be represented as tree graphs whose nodes represent a set of
basic functions (middle panel). Using a neural network trained to fit a mystery function (left panel),
our algorithm seeks a decomposition of this function into others with fewer input variables (right panel), in this case of the form $f(x,y,z)=g[h(x,y),z]$ .
\label{modulesFig}
}
\end{figure}

When we define and evaluate a mathematical function, we typically represent it as composed of some basis set $S$ of simpler functions. As illustrated in \fig{modulesFig} (middle panel), this representation can be specified as a graph whose nodes contain elements of $S$. The most popular basis functions in the scientific literature tend to
be functions of two variables (such as $+$ or $\times$), one variable (such as $\sin$ or $\log$) or no variables (constants such as $2$ or $\pi$).
For many functions of scientific interest, this graph is {\it modular} in the sense that it can be partitioned in terms of functions with fewer input variables, as in \fig{modulesFig} (right panel).

A key strategy of our symbolic regression algorithm is to recursively discover such modularity, thereby reverse-engineering the computational graph of a mystery function, starting with no information about it other than an input-output data table.
This is useful because there are exponentially many ways to combine $n$  basis functions into a module, making it extremely slow and difficult for brute-force or genetic algorithms to discover the correct function when $n$ is large. Our divide-and-conquer approach of first breaking the function into smaller modules with smaller $n$ that can be solved separately thus greatly accelerates the solution.
We implement this modularity discovery algorithm in two steps:
\begin{enumerate}
\item Use the user-provided data table
 to train a neural network $\fnn(\x)$ that accurately approximates the mystery function $f(\x)$.
\item Perform numerical experiments on $\fnn(\x)$ to discover graph modularity.
\end{enumerate}

\begin{figure}[bt]
\centerline{\includegraphics[width=\linewidth]{modularity.pdf}}
\caption{Examples of graph modularity that our algorithm can auto-discover.
Lines denote real-valued variables and ovals denote functions, with larger ones being more complex.
\label{modularityFig}
}
\end{figure}

Specifically, we test for the six types of graph modularity illustrated in \fig{modularityFig} and listed in Table~\ref{strategyTable}, and choose between the discovered candidates as described in \Sec{ParetoSubsec}.
Our method for discovering separability is described in \cite{udrescu2020ai}.
As we will see below, all our other types of graph modularity
(compositionality, symmetry and generalized additivity)
can be revealed by $\nabla f$, the gradient of our mystery function $f$.

\begin{table}[tb]
  \caption{Simplification strategies}
  \label{strategyTable}
  \centering
  \begin{tabular}{lll}
\toprule
Name   			& Property&Action\\
\toprule
Negativity 			&$f(x_1,x_2,...)<0$					&Solve for $g\equiv -f$\\
\midrule
Positivity 			&$f(x_1,x_2,...)>0$					&Solve for $g\equiv\ln f$\\
\midrule
Additive 			&$f(x_1,...,x_k,x_{k+1},...,x_n)=$		&\\
separability				&$g(x_1,...,x_k)+h(x_{k+1},...,x_n)$		&Solve for $g$ \& $h$\\
\midrule
Multiplicative 		&$f(x_1,...,x_k,x_{k+1},...,x_n)=$		&\\
separability				&$g(x_1,...,x_k)h(x_{k+1},...,x_n)$		&Solve for $g$ \& $h$\\
\midrule
Simple symmetry	&$f(x_1,x_2,...)=g(x_1\odot x_2,...),\>\>\>\odot\in\{+,-,\times,/\}$			&Solve for $g$\\
\midrule
Compositionality 		&$f(x_1,...,x_n)=g(h(x_1,...,x_n)),\>\>\>\hbox{$h$ simpler than $f$}$	&Find $h$ with $\nabla h\propto\nabla f$\\
\midrule
Generalized 			&$f(x_1,...,x_k,x_{k+1},...,x_n)=$		&Find $h$ satisfying \\
symmetry				&$g[h(x_1,...,x_k),x_{k+1},...,x_n]$		&$h_{,i}\propto f_{,i}$, $i=1,...,k$\\
\midrule
Generalized 			&$f(x_1,x_2)=F[g(x_1)+h(x_2)]$	&Solve for $F$, $g$ \& $h$\\
additivity				&							&\\
\midrule
Zero-snap				&$\fhat$ has numerical parameters	$\p$&Replace $p_i$ by $0$\\
\midrule
Integer snap			&$\fhat$ has numerical parameters	$\p$&Round $p_i$ to integer\\
\midrule
Rational snap			&$\fhat$ has numerical parameters	$\p$&Round $p_i$ to fraction\\
\midrule
Reoptimize			&$\fhat$ has numerical parameters	$\p$&Reoptimize $\p$ to\\
	 				&						       &minimize inaccuracy\\
\bottomrule
\end{tabular}
\end{table}

\paragraph{Compositionality}

Let us first consider the case of {\it compositionality} (\fig{modularityFig}, top right), where
$f(\x)=g(h(\x))$ and $h$ is a scalar function simpler than $f$ in the sense of being expressible with a smaller graph as in \fig{modularityFig}.
By the chain rule, we have
\beq{CompositionalityCriterionEq}
\nabla f(\x) = g'(h(\x))\nabla h(\x),\quad\hbox{so}\quad
\widehat{\nabla f}=\pm\widehat{\nabla h},
\eeq
where hats denote unit vectors:
$\widehat{\nabla f}\equiv\nabla f/|\nabla f|$, {\etc}
This means that if we can discover a function $h$ whose gradient is proportional to that of $f$ (which we will describe a process for in \Sec{bruteSec}), then we can simply replace the variables $\x$ in the original mystery data table by the single variable $h(\x)$ and recursively apply our AI Feynman algorithm to the new one-dimensional symbolic regression problem of discovering $g(h)$.

\paragraph{Generalized symmetry}

Let us now turn to {\it generalized symmetry} (\fig{modularityFig}, bottom left), where
$k$ of the $n$ arguments enter only via some scalar function $h$ of them.
Specifically, we say that an $f$ has generalized symmetry if
the $n$ components of the
vector $\x\in\mathbb{R}^n$ can be split into groups of $k$ and $n-k$ components (which we denote  by the vectors $\x'\in\mathbb{R}^k$  and $\x''\in\mathbb{R}^{n-k}$)
such that $f(\x)=f(\x',\x'')=g[h(\x'),\x'']$ for some function $g$.
By the chain rule, we have
\beq{GenSymCriterionEq}
\nabla_{\x'} f(\x',\x'') = g_1[h(\x'),\x'']\nabla h(\x'),\quad\hbox{so}\quad
\widehat{\nabla_{\x'} f}=\pm\widehat{\nabla h},
\eeq
where $g_1$ denotes the derivative of $g$ with respect to its first argument.
This means that $\widehat{\nabla_{\x'}}f(\x',\x'')$ is independent of $\x''$, which it would not be for a generic function $f$.
$\x''$-independence of the normalized gradients  $\vhat(\x',\x'')\equiv\widehat{\nabla_{\x'}}f(\x',\x'')$ thus provides a
smoking gun signature of generalized symmetry.
Whereas our compositionality discovery above requires discovering an explicit function $h$, we can discover generalized symmetry without knowing $h$, thus only performing the time-consuming task of searching for an $h$ satisfying \eq{GenSymCriterionEq} after determining that a solution exists.
The Supplementary Material details how we numerically test for $\x''$-independence of $\vhat(\x',\x'')$.

\paragraph{Generalized additivity}

If $f$ is a function of two variables, then we also test for {\it generalized additivity}
(\fig{modularityFig}, bottom right), where
$f(x_1,x_2) = F[g(x_1)+h(x_2)]$.
If we define the function
\beq{GenAddCriterionEq}
s(x_1,x_2)\equiv {\partial f/\partial x_1\over \partial f/\partial x_2},\quad\hbox{then}\quad
s(x_1,x_2)={g'(x_1)\over h'(x_2)}
\quad
\eeq
if $f$ satisfies the generalized additivity property.
In other words, we simply need to test if $s$ is of the multiplicatively separable form
$s(x_1,x_2)=a(x_1)b(x_2)$, and we do this using a variant of the separability test described in \cite{udrescu2020ai}.
The Supplementary Material details how we perform this separability test numerically.

\subsection{Robustness through recursive Pareto-optimality}
\label{ParetoSubsec}

As illustrated in \fig{kineticFig}, the goal of our symbolic regression of a data set is to approximate $f(\x)$ by functions $\fhat(\x)$ that are not only accurate, but also simple, in the spirit of Occam's razor.
As in \cite{schmidt2009distilling}, we seek functions that are {\it Pareto-optimal} in the sense of there being no other function that is both simpler and more accurate.
We will adopt an information-theoretical approach and use bits of information to measure lack of both accuracy and simplicity.

For {\it accuracy}, we wish the vector $\vepsilon$ of prediction errors $\varepsilon_i\equiv y_i-\fhat(\x_i)$ to be small. We quantify this not by the
mean-squared error $\expec{\varepsilon_i^2}$
or max-error $\max |\varepsilon_i|$ as in \cite{schmidt2009distilling,udrescu2020ai},
but by the MEDL, the {\it mean error-description-length} $\expec{\DL(\varepsilon_i)}$
defined in Table~\ref{complexityTable}.
As argued in \cite{wu2019toward} and illustrated in \fig{mdlFig}, this improves robustness to outliers.
We analogously quantify {\it complexity} by the description length $\DL$ defined as in
\cite{wu2019toward}, summarized in Table~\ref{complexityTable}.

$\DL$ can be viewed as a crude but computationally convenient approximation of
the number of bits needed to describe each object, made differentiable where possible. We choose the precision floor $\epsilon\equiv 2^{-30}\sim 10^{-9}$.
For function complexity, both input variables and mathematical functions (\eg, $\cos$ and +) count toward $n$ and $k$.
For example, the classical kinetic energy formula has
$\DL(``m\times v\times v/2'') = \DL(2) + k\log_2 n=
\log_2 3 + 6\log_2 4 \approx 13.6$ bits, since the formula contains
$n=4$ basis functions ($m$, $v$, $\times$ and $/$) used
$k=6$ times.

\begin{table}[tb]
  \caption{Complexity definitions}
  \label{complexityTable}
  \centering
  \begin{tabular}{lll}
    \toprule
Object   			& Symbol	&Description length $\DL$\\
\midrule
Natural number		&$n$		&$\log_2 n$\\
Integer 			&$m$	&$\log_2 (1+|m|)$\\
Rational number	&$m/n$	&$\DL(m)+\DL(n)=\log_2[(1+|m|)n]$\\
Real number		&$r$		&$\logplus\left({r\over\varepsilon}\right),\quad\logplus(x)\equiv{1\over 2}\log_2\left(1+x^2\right)$\\
Parameter vector	&$\p$	&$\sum_i\DL(p_i)$\\
Parametrized function&$f(\x;\p)$&$\DL(\p)+k\log_2 n$; $n$ basis functions appear k times\\
\bottomrule
\end{tabular}
\end{table}

We wish to make the symbolic regression implementation of \cite{udrescu2020ai} more robust; it sometimes fails to discover the correct expression because of noise in the data or inaccuracies introduced by the neural network fitting. The neural network accuracy may vary strongly with $\x$, becoming quite poor in domains with little training data or when the network is forced to extrapolate rather than interpolate, and we desire a regression method robust to such outliers.
We expect our insistence on Pareto-optimal functions in the information plane of \fig{kineticFig} to increase robustness, both because $\expec{\DL(\varepsilon_i)}$ is robust (\fig{mdlFig})
and because noise and systematic errors are unlikely to be predictable by a simple mathematical formula with small $\DL$. More broadly, minimization of total exact description length (which $\DL$ crudely approximates) provably avoids the overfitting problem that plagues many alternative machine-learning strategies \cite{rissanen1978modeling,hutter2000theory,grunwald2005advances}.

\begin{figure}[bt]
\centerline{\includegraphics[width=\linewidth]{mdl.pdf}}
\caption{When fitting a function (the right panel shows the example ${ax^3\over e^{x/b}-1}$) to data with outliers,
minimizing mean-squared-error (MSE) biases the curve toward the outliers (here finding $a\approx 0.89$, $b\approx 1.056$), whereas minimizing mean error description length (MEDL) ignores the outliers and recovers the correct answer $a=b=1$. Left panel compares MSE and MEDL loss functions for $b=1$.
\label{mdlFig}
}
\end{figure}

\paragraph{Speedup by recursive Pareto frontier composition}

When recursively symbolically regressing various modules (see \fig{modulesFig}), we end up with a Pareto frontier of candidate functions for each one.
If there are $n_i$ functions on the $\ith$ frontier,
then combining them all would produce $\prod_i n_i$ candidates $\fhat(\x)$ for the original function
$f(\x)$. We speed up our algorithm by Pareto-pruning after each merge step: whenever two modules are combined (via composition or multiplication, say), the resulting $n_1 n_2$ functions are pruned by removing all functions that are Pareto-dominated by another function that is both simpler and more accurate.
Pruning models on the Pareto frontier significantly reduces the number of models that need to be evaluated, since in typical scenarios, the number of Pareto-optimal points grows only logarithmically with the total number of points.

\paragraph{Robust speedup of brute-force graph search with hypothesis testing}
\label{bruteSec}

Our recursive reduction of regression mysteries into simpler ones terminates at the base case when
the mystery function has only one variable and cannot be further modularized.
As in \cite{udrescu2020ai}, we subject these (and also all multivariate modules) to two solution strategies, polynomial fitting up to some degree ($4$ by default) and brute force search, and then add all candidates functions to the Pareto plane and prune as above.
The brute-force search would, if run forever, try all symbolic expressions by looping over ever-more-complex graphs  (the middle panel of \fig{modulesFig} shows an example) and over function options for each node.

Our brute-force computation of the
Pareto frontier simply tries all functions $f_k(\x)$ ($k=1,2...$) in order of increasing complexity $\DL(f_k)$ and keeps only those with lower mean error-description-length $d_k\equiv{1\over N}\sum_{i=1}^N d_{ki}$ than the previous record holder, where
$d_{ki}\equiv\DL[y_i-f_k(\x_i)]$.
When instead fitting normalized gradient vectors $\widehat{\nabla f}$ as in \Sec{ModularitySubsec},
we define $d_{ki}\equiv\DL[1-|\yhat_i\cdot\widehat{\nabla f_k}(\x_i)|]$ to handle the sign ambiguity. The bad news is that computing $d_k$ exactly is slow, requiring evaluation of $f_k(\x_i)$ for all $N$ data points $\x_i$.
The good news is that this is usually unnecessary, since for the vast majority of all candidate functions, it becomes obvious that they provide a poor fit after trying merely a handful of data points. We therefore accelerate the search via the following procedure.
Before starting the loop over candidate functions, we sort the data points in random order to be able to interpret
the numbers $d_{ki}$ as random samples from a probability distribution whose mean is the sought-for $d_k$ and whose standard deviation is $\sigma_k$. Let $d_{k*}$ and $\sigma_{k*}$ denote the corresponding quantities that were computed for the
previous best-fit function we added to the Pareto frontier.
We make the simplifying approximations that $\sigma_k=\sigma_{k*}$ and that all errors are uncorrelated, so that the loss
estimate from the first $m$ data points
$\bar{d}_{km}\equiv {1\over m}\sum_{i=1}^m d_{ki}$ has mean $d_k$ and standard deviation $\sigma_{k*}/\sqrt{m}$.
We now test our candidate function $f_i$ on one data point at a time and reject it as soon as
\beq{RejectionEq}
z>\nu,\quad\hbox{where}\quad z\equiv\sqrt{m}\>{\bar{d}_{km}-d_{k*}\over\sigma_{k*}},
\eeq
where $\nu$ is a hyperparameter that we can interpret as the ``number of sigmas" we require to rule out a candidate function as viable
when its average error exceeds the previous record holder.
We find that $\nu=10$ usually works well, generically requiring no more than a handful of evaluations $m$ per candidate function asymptotically.
We can further increase robustness by increasing $\nu$ at the price of longer runtime.

\paragraph{Speedup by greedy search of simplification options}

We do not {\it a priori} know which of the modular decompositions from \fig{modularityFig} are most promising, and recursively trying all combinations of them would involve trying exponentially many options.
We therefore accelerate our algorithm with a greedy strategy where at each step we compare the decomposition in a unified way and try only the most accurate one --- our runtime thus grows roughly linearly with $n$, the number of input variables.
$f(\x)$ stays constant along constant-$h$ curves for
generalized symmetry, simple symmetry (where $h(x,y)=x+y$, $x-y$, $xy$ or $x/y$) and
generalized additivity (where $h(x,y)=a(x)+b(y)$).
We thus test the accuracy of all such $h$-candidates by starting at a datapoint $\x_i$ and computing an error $\epsilon_i\equiv f(\tilde{\x}_i)-f(\x_i)$ for some $\tilde{\x}_i$
satisfying $h(\tilde{\x}_i)=h(\x_i)$. For additive and multiplicative separability, we follow \cite{udrescu2020ai} by examining a rectangle in parameter space and predicting $f$ at the fourth corner from the other three, defining $\epsilon_i$ as the mismatch. The supplementary material details how our test points are chosen.

After this greedy recursive process has terminated, we further improve the Pareto frontier in two ways. We first add models where rational numbers are replaced by reals and optimized by gradient descent to fit the data. We then add models with zero-snap, integer-snap and rational-snap from Table~\ref{strategyTable} applied to all real-valued parameters as described in \cite{wu2019toward}, pruning all Pareto-dominated models after each step. For example, if there are 3 real-valued parameters, integer-snap generates 3 new models where the 1, 2 and 3 parameters closest to integers get rounded, respectively.

\subsection{Leveraging normalizing flows to symbolic regress probability distributions}
\label{FlowSubsec}

An important but more difficult symbolic regression problem is when the unknown function $f(\x)$ is a probability distribution from
which we have random samples $\x_i$ rather than direct evaluations $y_i=f(\x_i)$.
We tackle this by adding preceding the regression by a step that estimates $f(\x)$.
For this step, we use the popular {\it normalizing flow} technique \cite{rezende15,dinh2017,kingma2018,durkan2019,kobyzev2020},
training an invertible neural network mapping $\x\mapsto\x'\equiv g(\x)$ such that $\x'$ has a multivariate normal distribution $n(\x')$
as illustrated in \fig{nfdemo}. We then obtain our estimator $\fnn(\x)=n[g(\x)]|J|$, where $J$ is the Jacobian of $g$.

We find rational-quadratic neural spline flows (RQ-NSF) suitable for relatively low-dimensional applications due to their enhanced expressivity.
Specifically, we used three steps of the RQ-NSF with RQ-NSF (C) coupling layers as described in \cite{durkan2019},
parametrized by three 16-neuron softplus layers, trained for $50,000$ epochs with the Adam optimizer. The learning rate was initialized to $3 \times 10^{-4}$ and halved every time the test loss failed to improve for $2500$ epochs.

\begin{figure}[bt]
\centerline{\includegraphics[width=\linewidth]{nfdemo.jpg}}
\caption{
\label{nfdemo}
A normalizing flow $g$ maps samples from a probability distribution $f$ (right) into a normal distribution (left), enabling an estimate (middle) of $f$, here illustrated for the $n=2$, $l=1$, $m=0$ hydrogen orbital from Table~\protect\ref{ProbDistTable}.
}
\end{figure}

\section{Results}
\label{ResultsSec}

We now turn to quantifying the performance of our method with numerical experiments, comparing it with that of \cite{udrescu2020ai} which recently exceded the previous state of-the-art performance of \cite{schmidt2009distilling}.
To quantify robustness to noise, we add Gaussian noise of standard deviation $10^{r}$ to $y_i$ and determine the largest integer $r<0$ for which the method successfully discovers the correct mystery function $f(\x)$.
As seen in Table~\ref{robustnessTable}, our method
solves 73 of 100 the baseline problems from the
Feynman Symbolic Regression Database \cite{udrescu2020ai}
with $r=-1$, and is typically 1-3 orders of magnitude more robust than that
of \cite{udrescu2020ai}.
Crudely speaking, we found that adding progressively more noise shifted the most accurate formula straight upward in the Pareto plane (\fig{kineticFig})
until it no longer provided any accuracy gains compared with simpler approximations.

\begin{table}
  \caption{Robustness to noise}
  \label{robustnessTable}
\centerline{\includegraphics[width=0.6\linewidth]{robustness.pdf}}
\end{table}

To quantify the ability of our method to discover more complex equations,
we reran it on all 17 mysteries that \cite{udrescu2020ai} tackled and failed to solve.
We also tested a dozen new mysteries exhibiting various forms of graph modularity (see Table~\ref{MysteryTable}) that were all chosen before any of them were tested.
Allowing at most two hours of run-time,
the method of \cite{udrescu2020ai} solved equations 5, 12,...,15,
whereas our new method solved them all,
as well as four of the outstanding mysteries from \cite{udrescu2020ai} (rows 1-4).
For these first four, our method got the numerical parameters in the right ballpark with rational approximations, then discovered their exact values through gradient descent.

\begin{table*}[tb]
\centering
\caption{\label{MysteryTable}
Test equations exhibiting
translational symmetry $h=x\pm y$ (T),
scaling symmetry $h=x/y$ (S),
product symmetry $h=xy$ (P),
generalized symmetry (G),
multiplicative separability (M),
compositionality (C) and
generalized additivity (A).
}
\begin{tabular}{r|l|c}
\toprule
&Equation   & Symmetries\\
\midrule
1&$\delta = -5.41+4.9\frac{\alpha-\beta+\gamma/\chi}{3\chi}$ &TC\\
2&$\chi = 0.23+14.2\frac{\alpha+\beta}{3\gamma}$ &TS\\
3&$\beta = 213.80940889\left(1-e^{-0.54723748542\alpha}\right)$ &\\
4&$\delta = 6.87 + 11\sqrt{\alpha\beta\gamma}$ &P\\
5&$V=\left[R_1^{-1}+R_2^{-1}+R_3^{-1}+R_4^{-1}\right]^{-1}I_0\cos\omega t$\quad\hbox{(Parallel resistors)}&PGSM\\
6&$I_0={V_0\over\sqrt{R^2+\left(\omega L-{1\over\omega C}\right)^2}}$\quad\hbox{(RLC circuit )}&MG\\
7&$I={V_0\cos\omega t\over\sqrt{R^2+\left(\omega L-{1\over\omega C}\right)^2}}$\quad\hbox{(RLC circuit)}&MG\\
8&$V_2 = (\frac{R_2}{R_1+R_2}-\frac{R_x}{R_x+R_3})V_1$\quad\hbox{(Wheatstone bridge)} &SGMA\\
9&$v = c\frac{(v_1 + v_2 + v_3)/c + v_1v_2v_3/c^3}{1 + (v_1v_2 + v_1v_3 + v_2v_3)/c^2}$\quad\hbox{(Velocity addition)} &AG\\
10&$v = c \frac{(v_1 + v_2 + v_3 + v_4)/c + (v_2 v_3 v_4 + v_1 v_3 v_4 + v_1 v_2 v_4 + v_1 v_2 v_3)/c^3}{1 + (v_1 v_2+ v_1 v_3+ v_1 v_4+ v_2 v_3+ v_2 v_4+ v_3 v_4)/c^2 + v_1 v_2 v_3 v_4/c^4}$\quad\hbox{(Velocity addition)}&GA\\
11&$z = (x^4+y^4)^{1/4}$\quad\hbox{($L_4$-norm)}&AC\\
12&$w = xyz-z\sqrt{1-x^2}\sqrt{1-y^2}-y\sqrt{1-x^2}\sqrt{1-z^2}-x\sqrt{1-y^2}\sqrt{1-z^2}$ &GA\\
13&$z = \frac{xy+\sqrt{1-x^2-y^2+x^2y^2}}{y\sqrt{1-x^2}-x\sqrt{1-y^2}}$ &A\\
14&$z = y\sqrt{1-x^2}+x\sqrt{1-y^2}$ &A\\
15&$z = xy-\sqrt{1-x^2}\sqrt{1-y^2}$ &A\\
16&$r = \frac{a}{\cot{(\alpha/2)}+\cot{(\beta/2)}}$\quad\hbox{(Incircle)}&GMAC\\
\bottomrule
\end{tabular}
\end{table*}

To quantify the ability of our method to discover probability distributions,
we tested it on samples from the ten distributions in Table~\ref{ProbDistTable}. As seen in the table, 80\% were solved, requiring between $10^2$ and $10^5$ samples $\x_i$.
The flows trained in about 20 minutes on one CPU, scaling roughly linearly with sample size and number of network weights.
The Supplementary Material details failure modes.

\begin{table*}[tb]
\centering
\caption{Probability distributions and number of samples $N$ required to discover them
\label{ProbDistTable}
}
\begin{tabular}{l|l|c}
\toprule
Distribution Name & Probability distribution & $N$\\
\midrule
Laplace distribution & $\frac{1}{2}e^{-|x|}$ & $10^2$\\
Beta distribution ($\alpha = 0.5$, $\beta = 0.5$) & $\frac{1}{\pi}\frac{1}{\sqrt{x(1-x)}}$ & $10^4$\\
Beta distribution ($\alpha = 5$, $\beta = 2$) & $30x^4(1-x)$ & $10^4$\\
Harmonic oscillator ($n=2$, $\frac{m\omega}{\hbar} = 1$) & $\frac{2}{\sqrt\pi}x^2e^{-x^2}$ & $10^5$\\
Sinc diffraction pattern & $\frac{1}{\pi}\left(\frac{\sin{x}}{x}\right)^2$ & $10^4$\\
2D normal distribution (correlated) & $\frac{1}{\sqrt{3}\pi}e^{-\frac{2}{3}(x^2-xy+y^2)}$ & $10^3$\\
2D harmonic oscillator ($n=2$, $m=1$, $\frac{m\omega}{\hbar} = 1$) & $\frac{2}{\pi}x^2e^{-x^2-y^2}$ &$10^5$\\
Hydrogen orbital ($n=1$, $l=0$, $m=0$) & $\frac{1}{\pi}e^{-2r}$ & $10^3$\\
Hydrogen orbital ($n=2$, $l=1$, $m=0$) & $\frac{1}{16}r^2e^{-r}\cos^2\theta$ & -\\
Hydrogen orbital ($n=3$, $l=1$, $m=0$) & $\frac{1}{729}r^2\left(4-\frac{2r}{3}\right)^2e^{-\frac{2r}{3}}\cos^2\theta$ & -\\
\bottomrule
\end{tabular}
\end{table*}

\section{Conclusions}
\label{ConclusionsSec}

We have presented a symbolic regression method that exploits
neural networks, graph modularity, hypothesis testing and normalizing flows.
It improves state-of-the-art performance both by being more robust towards noise and by solving harder problems, including symbolic density estimation.
These core ideas can enable further improvements. For example, gradients can reveal more types of graph modularity than the \fig{modularityFig} examples that we exploited; additional simplification strategies can be included in the Pareto-optimal recursion; and flow-based regression can be used for regularized
density estimation from sparse high-dimensional data. Larger and more challenging collections of science-based equations are needed to benchmark and inspire improved algorithms.

Pareto-optimal symbolic regression has the power to not only discover exact formulas, but also
approximate ones that are useful for being both accurate and simple.
The mainstream view is that all known science formulas are such approximations.
We live in a golden age of research with ever-larger datasets produced by both experiments and numerical computations, and we look forward to a future when symbolic regression is as ubiquitous as linear regression is today,
helping us better understand the relations hidden in these datasets.

\clearpage

\begin{ack}
The authors with to thank Philip Tegmark for helpful comments,  and the Center for Brains, Minds, and Machines (CBMM) for hospitality.

{\bf Funding:} This work was supported by The Casey and Family Foundation, the Ethics and Governance of AI Fund, the Foundational Questions Institute, the Rothberg Family Fund for Cognitive Science and the Templeton World Charity Foundation, Inc.

{\bf Competing interests:} The authors declare that they have no competing interests.

{\bf Data and materials availability:} Data and code will be publicly released when this paper is accepted for publication.

\end{ack}

\section*{Broader Impact}

\subsection*{Who may benefit from this research}

Our research presumably has quite broad impact, since discovery of mathematical patterns in data is a central problem
across the natural and social sciences. Given the ubiquity of {\it linear} regression in research, one might expect that there will significant benefits to a broad range of researchers also from more general symbolic regression once freely available algorithms get sufficiently good.

\subsection*{Who may be put at disadvantage from this research}

Although it is possible that some numerical modelers could get their jobs automated away by symbolic regression, we suspect that the main effect of our method, and future tools building on it, will instead be that these people will simply discover better models than today.

\subsection*{Risk of bias, failure and other negative outcomes}

Pareto-optimal symbolic regression can be viewed as an extreme form of lossy data compression that uncovers the simplest possible model for any given accuracy. To the extent that overfitting can exacerbate bias, such model compression is expected to help. Moreover, since our method produces closed-form mathematical formulas that have excellent interpretability compared to black-box neural networks, they make it easier for humans to interpret the computation and pass judgement on whether it embodies unacceptable bias. This interpretability also reduces failure risk.

Another risk is automation bias, whereby people overly trust a formula from symbolic regression when they extrapolate it into an untested domain. This could be exacerbated if symbolic regression promotes scientific laziness and enfeeblement, where researchers fit phenomenological models instead of doing the work of building models based on first principles. Symbolic regression should inform but not replace
traditional scientific discovery.

Although the choice of basis functions biases the discoverable function class, our method is
agnostic to basis functions as long as they are mostly differentiable.

The potentially greatest risk associated with this work does not stem from it failing but from it succeeding:
accelerated progress in symbolic regression, modularity discovery and its parent discipline program synthesis could hasten
the arrival of artificial general intelligence, which some authors have argued that humanity still lacks the tools
to manage safely \cite{russell2019human}.
On the other hand, our work may help accelerate research on intelligible intelligence more broadly, and
powerful future artificial intelligence is probably safer if we understand aspects of how it works than if it is an inscrutable black box.

\clearpage
\appendix

{\bf\Large Supplementary material}
\bigskip

Below we provide additional technical details about how we implement our method and numerical experiments.

\section{Testing for generalized symmetry}

We showed that generalized symmetry can be revealed by
$\vhat(\x',\x'')$  being independent of $\x''$. We will now describe how we test
for such $\x''$-independence numerically.
Given
a point $\x_i\in\mathbb{R}^k$ from our data set,
we compute a set of normalized gradients $\vhat_j\equiv\vhat_i(\x'_i,\x''_j)$, where $\x''_j\in\mathbb{R}^{n-k}$ correspond to a sample of $m$ other data points,
and quantify the variation between then by the quantity
\beq{VdefEq}
V(\x)\equiv 1-\max_{|\mu|=1} {1\over m}\sum_{j=1}^m(\muhat\cdot\vhat_j)^2
= 1-\max_{|\mu|=1} \muhat^t\V\muhat,\quad\hbox{where}\quad
\V\equiv {1\over m}\sum_{j=1}^m\vhat_j\vhat_j^t.
\eeq
We can intuitively interpret the optimal $\muhat$ as maximally aligned with the vectors $\vhat_j$ up to a sign.
\Eq{VdefEq} implies that our variation measure $V$ is simply one minus the smallest eigenvalue of $\V$, so
$V$ ranges from $0$ when all $\vhat_j$ are identical to $1-{1\over m}$ when all eigenvalues are equal (equal to $1/m$, since $\tr\V=1$).
As illustrated in \fig{VhistogramFig}, we compute $V(\x_i)$ for each subset of up to $\ng$
input variables, and select the subset with the smallest median $V(\x_i)$ as the most promising generalized symmetry candidate. In our numerical experiments, we set the hyperparameter $\ng=3$ to save time, since we do not wish to consider all $2^n$ subsets for large $n$.

\begin{figure}[h]
\centerline{
\includegraphics[width=\linewidth]{generalized_symmetry_RLC.pdf}
}
\caption{Distribution of $V(\x_i)$ for the function from \protect\fig{modulesFig}, revealing that evidence for
the generalized symmetry $f(x,y,z)=g[h(x,y),z]$ (shaded distribution) is stronger than for
$f(x,y,z)=g[h(x,z),y]$ (blue curve) or $f(x,y,z)=g[h(y,z),x]$ (red curve). The curves are shown slightly smoothed for clarity.
\label{VhistogramFig}
}
\end{figure}

\section{Testing for generalized additivity}

We showed that generalized additivity holds when the function $s(x_1,x_2)$ from Equation~(3) is multiplicatively separable.
We will now describe how we test
for such separability numerically.
If $s(x_1,x_2)$ being multiplicative separable is equivalent to $f(x_1,x_2)\equiv \ln{s(x_1, x_2)}$ being additively separable.
We numerically quantity this by the
and we test the function $\ln{s_{NN}(x_1, x_2)}$ for additive separability using the normalized score $S$ defining
\beq{AddSepScore}
S[f] = \frac{|f_{,xy}|^2}{|f_{,xx} f_{,yy}| + |f_{,xy}|^2}.
\eeq
It is easy to see that $S[f]=0$ if $f$ is additively separable functions $f$, and $S[f]>0$ otherwise.
If the median value of $S$ over all points $\x_i$ in the dataset, we take thisas evidence for generalized additivity in the dataset and proceed as below. It is important to use smooth (not, \eg, ReLU) activation functions in the activation function for this derivative-based test to be useful.

If this property holds, then we  recursively apply our
algorithm to the two new 1-dimensional symbolic regression problems of discovering $a(x_1)$ and $b(x_2)$. If this succeeds and we are able to discover the functions
$g(x_1)$ and $h(x_2)$ by symbolically integrating
our solutions $g'=a$ and $h'=1/b$, then we have
reduced the original problem to the same state as when we found compositionality above, now with $h(x_1,x_2)=g(x_1)+h(x_2)$.
Just as in that case, we simply replace the variables $\x$ in the original mystery data table by the single variable $h(\x)$ and recursively apply our AI Feynman algorithm to the new 1-dimensional symbolic regression problem of discovering how $f$ depends on $h$.

If we have determined that generalized additivity holds but the above aforementioned method for discovering $g(x_1)+h(x_2)$ fails,
we make a second attempt by training a neural network of the modular form $\fnn(x_1,x_2)=F[g(x_1)+h(x_2)]$ to fit the data. If this succeeds,
we then recursively apply our AI Feynman algorithm to the three new 1-dimensional symbolic regression problems of discovering $F$, $g$ and $h$.

\section{Further details on success and failure modes}

Our paper reported which symbolic regression problems our method succeeded and failed on. Here we add specifics on how these successes and failures occurred.

\paragraph{Success definition}

Given a data set $\{x_1,...,x_n,y\}$,
we use 90\% of the data to compute a Pareto-optimal set of candidate functions
$\fhat_i(\x)$, then rank them based on their MEDL accuracy on the held-back 10\%
of the data. We count our method as successful only if the top-ranked function
matches the true $f(\x)$ exactly, or, if the definition of $f$ involves irrational numerical
parameters, if these parameters are recovered to better than $0.01\%$ relative accuracy.

We considered an equation solved even if the top solution was not in the exact form presented in our
tables, but Mathematically equivalent. For example, our method predicted that Equation~(12) in Table~4 was $w=\cos[\arccos(x)+\arccos(y)+\arccos(z)]$, which is
mathematically equivalent within the domain of our provided data set, where $x,y,z\in[-1,1]$.

For the problem of density estimation from samples, our goal was to obtain the correct normalized probability distributions.
The candidate functions on the Pareto-frontier were therefore
discarded unless they were non-negative and normalizable.
The surviving candidates then normalized to integrate to unity by
symbolic/numerical integration to obtain the appropriate normalization constant, and
quality-ranked by the surprisal loss function $$L_i =  -\sum \log\fhat_i(\x_k)$$
evaluated on the held-back test data.

\paragraph{Success examples}

Tables 1 and 2 below show the highest noise level allowing allowing each of the 100 equations from the Feynman Database for Symbolic regression to be solved in the original paper analyzing it and in the present paper.

For many of the solved equations, the modularity discovery had to be used multiple times in order for the correct equation to be discovered, reflecting the power of the recursive algorithm. For example, for the quadruple velocity addition equation in Table 4, generalized symmetry was exploited twice. First, the code discovered that the first two velocities only enter in the combination $\frac{v_1+v_2}{1+v_1v_2}$, and these two variables were replaced by a new variable
$v_{12}$. The same method then discovered that $v_{12}$ and $v_3$ only enter in that same combination
$\frac{v_{12}+v_3}{1+v_{12} v_3}$, and thus the initial 3 variables $v_1$, $v_2$ and $v_3$ were replaced by a single variable $v_{123}$. Now the remaining equation had only 2 variables left, and was solved by brute force.
In principle, this recursive method can be used to discover relativistic addition of an arbitrary number of velocities, by reducing the number of variables by one at each step.

\paragraph{Failure examples}

As mentioned in the main text, numerous equations remained unsolved, motivating further work.
In some cases, the main reason for this failure was that the form of the equation did not allow our method to break it into small enough pieces. For example, for the equation
$$\alpha^3\exp(-\alpha)\cos(\alpha)\sin(\alpha)(\sin(\alpha)^2\cos(\alpha)-1)(\beta-5),$$
our algorithm is able to discover the multiplicative separability into terms including only $\alpha$ and only $\beta$. However, the remaining $\alpha$-term is too complicated to be solved in a reasonable amount of time by the brute force code, and none of the graph modularity methods apply because
they only help for functions of more than one variable.

For other equations, our method fails but not irreparably. For example, for  the function
$$22 - 4.2(\cos(\alpha)-\tan(\beta))\tanh(\gamma)/\sin(\chi),$$
our code is able to discover that $\gamma$ and $\chi$ can be separated from the rest of the equation. However, given that we allow the brute force code to run for only a minute at each iteration, the expression $\tanh(\gamma)/\sin(\chi)$ is not discovered, mainly because we did not include $\tanh$ as one of the functions used, so the brute force would have to write that as $\frac{e^{-2x}-1}{e^{2x}+1}$.
By allowing the code to run for longer and experimenting with additional basis functions (such as $\tanh$), it is likely that the code would solve this and several other mysteries that we reported as failures.

Fitting a normalizing flow for density estimation presents a `real-world' test of the symbolic regression code, which needs to cope with flow errors.
We demonstrated the robustness of the code to more challenging errors (i.e. not i.i.d. Gaussian); some of the failure modes are investigated and expanded on below.

It is worth noting that our definition of complexity is dependent on the chosen set of operations and does not always match our intuition.
For example, in fitting the probability distribution $$p(r, \theta) = \frac{1}{16} r^2 e^{-r} \cos^2\theta$$
of election positions in the $n=2$, $l=1$, $m=0$ hydrogen orbital,
solutions with $\theta$-dependence $\cos\left(\cos\left(\theta\right)\right)$ are preferred over $\cos^2\theta$.
This is because, up to additive and multiplcative prefactors, the two formulas differ by at most approximately $2 \times 10^{-2}$ over our parameter range, but given a set of operations that includes only $\left\{\times, \cos\right\}$ denoted by "$*$" and ``$C$" respectively in reverse Polish notation, $\cos\left(\cos\left(\theta\right)\right)$ (encoded as``$xCC$") is simpler than $\cos^2\theta$ (encoded as $``xCxC*"$).
In the presence of the imprecisions introduced by the normalizing flow, we were unable to perform the density estimation a level at which the accuracy for the correct $\cos^2\theta$ was preferred over the simpler alternative.

Furthermore, more interpretable approximations (e.g. Taylor expansions) are not always favored by our definition of complexity.
For example, in Figure 1, the unfamiliar solution
$$mc^2\left(\frac{1}{\cos{v/c}} - 1\right)$$
intermediate to the more familiar $mv^2/2$ and $mc^2\left(\frac{1}{\sqrt{1-v^2/c^2}} - 1\right)$ of  can be understood as a fourth-order approximation about $v=0$ of the exact formula.
Specifically, $mc^2\left(\frac{1}{\sqrt{1-v^2/c^2}} - 1\right) = \frac{mv^2}{2} + \frac{3mv^4}{8c^2} + O(v^6)$, and $mc^2\left(\frac{1}{\cos{v/c}} - 1\right) = \frac{mv^2}{2} + \frac{5mv^4}{24c^2} + O(v^6)$.
The Taylor expansions themselves are not preferred for reasons of complexity.

\begin{table*}[]
{\footnotesize
\begin{tabular}{|l|l|r|l|l|l|l|l|}
\hline
Feynman eq.  & Equation & Old Noise tolerance & New Noise tolerance\\
\hline

I.6.20a      & $f = e^{-\theta^2/2}/\sqrt{2\pi}$ & $10^{-2}$ & $10^{-1}$\\
I.6.20       & $f = e^{-\frac{\theta^2}{2\sigma^2}}/\sqrt{2\pi\sigma^2}$ & $10^{-4}$& $10^{-2}$\\
I.6.20b      & $f = e^{-\frac{(\theta-\theta_1)^2}{2\sigma^2}}/\sqrt{2\pi\sigma^2}$ & $10^{-4}$& $10^{-2}$ \\
I.8.14       & $d = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$ & $10^{-4}$  &$10^{-1}$ \\
I.9.18       & $F = \frac{Gm_1m_2}{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}$ & $10^{-5}$       &   $10^{-3}$\\
I.10.7       & $m = \frac{m_0}{\sqrt{1-\frac{v^2}{c^2}}}$  & $10^{-4}$  & $10^{-2}$  \\
I.11.19      & $A = x_1y_1+x_2y_2+x_3y_3$ & $10^{-3}$  & $10^{-1}$  \\
I.12.1       & $F = \mu N_n$ & $10^{-3}$&  $10^{-1}$\\
I.12.1a      & $K = \frac{1}{2}m(v^2+u^2+w^2)$ & $10^{-4}$&  $10^{-1}$  \\
I.12.2       & $F = \frac{q_1q_2}{4\pi\epsilon r^2}$  & $10^{-2}$& $10^{-1}$\\
I.12.4       & $U = \frac{q_1}{4\pi\epsilon r^2}$ & $10^{-2}$ & $10^{-1}$ \\
I.12.5       & $F = q_2 E_f$ & $10^{-2}$ &$10^{-1}$  \\
I.12.11      & $F = q(E_f+B v \sin\theta)$ & $10^{-3}$ & $10^{-1}$ \\
I.13.12      & $U = Gm_1m_2(\frac{1}{r_2}-\frac{1}{r_1})$ & $10^{-4}$ &$10^{-1}$ \\
I.14.3       & $U = mgz$ & $10^{-2}$&$10^{-1}$  \\
I.14.4       & $U = \frac{k_{spring}x^2}{2}$  & $10^{-2}$&$10^{-1}$  \\
I.15.3x      & $x_1 = \frac{x-ut}{\sqrt{1-u^2/c^2}}$ & $10^{-3}$ & $10^{-3}$\\
I.15.3t      & $t_1 = \frac{t-ux/c^2}{\sqrt{1-u^2/c^2}}$ & $10^{-4}$ &  $10^{-3}$\\
I.15.1       & $p = \frac{m_0v}{\sqrt{1-v^2/c^2}}$ & $10^{-4}$ & $10^{-1}$\\
I.16.6       & $v_1 = \frac{u+v}{1+uv/c^2}$ & $10^{-3}$  &$10^{-2}$ \\
I.18.4       & $r = \frac{m_1r_1+m_2r_2}{m_1+m_2}$ & $10^{-2}$& $10^{-1}$ \\
I.18.12      & $\tau = rF\sin\theta$ & $10^{-3}$ & $10^{-1}$\\
I.18.14      & $L = mrv \sin\theta$   & $10^{-3}$ &$10^{-1}$ \\
I.24.6 & $E = \frac{1}{4} m (\omega^2+\omega_0^2) x^2$  & $10^{-4}$&$10^{-1}$ \\
I.25.13      & $V_e = \frac{q}{C}$  & $10^{-2}$& $10^{-1}$ \\
I.26.2       & $\theta_1 = \arcsin(n  \sin\theta_2)$ & $10^{-2}$ &$10^{-1}$ \\
I.27.6       & $f_f$    $ = \frac{1}{\frac{1}{d_1}+\frac{n}{d_2}}$    & $10^{-2}$& $10^{-1}$ \\
I.29.4       & $k = \frac{\omega}{c}$ &  $10^{-2}$ & $10^{-1}$\\
I.29.16      & $x = \sqrt{x_1^2+x_2^2-2x_1x_2\cos(\theta_1-\theta_2)}$  & $10^{-4}$ &$10^{-3}$  \\
I.30.3 & $I_* = I_{*_0}\frac{\sin(n\theta/2)}{\sin(\theta/2)}$  & $10^{-3}$ & $10^{-3}$\\
I.30.5       & $\theta = \arcsin(\frac{\lambda}{nd})$  & $10^{-3}$ & $10^{-1}$ \\
I.32.5       & $P = \frac{q^2a^2}{6\pi\epsilon_c^3}$     & $10^{-2}$&  $10^{-1}$\\
I.32.17 & $P = (\frac{1}{2}\epsilon c E_f^2)(8\pi r^2/3) (\omega^4/(\omega^2-\omega_0^2)^2)$     & $10^{-4}$&  $10^{-3}$ \\
I.34.8       & $\omega = \frac{qvB}{p}$  & $10^{-2}$ & $10^{-1}$\\
I.34.10       & $\omega = \frac{1+v/c}{1-v/c}\omega_0$ & $10^{-3}$&  $10^{-2}$\\
I.34.14      & $\omega = \frac{1+v/c}{\sqrt{1-v^2/c^2}}\omega_0$  & $10^{-3}$ & $10^{-3}$ \\
I.34.27      & $E = \hbar\omega$ & $10^{-2}$  & $10^{-1}$\\
I.37.4       & $I_* = I_1+I_2+2\sqrt{I_1I_2}\cos\delta$ & $10^{-3}$ & $10^{-2}$ \\
I.38.12      & $r = \frac{4\pi\epsilon\hbar^2}{mq^2}$   & $10^{-2}$& $10^{-1}$ \\
I.39.10       & $E = \frac{3}{2}p_F V$     & $10^{-2}$& $10^{-1}$ \\
I.39.11      & $E = \frac{1}{\gamma-1}p_F V$  & $10^{-3}$ & $10^{-1}$\\
I.39.22      & $P_F = \frac{n k_b T}{V}$        & $10^{-4}$ & $10^{-1}$\\
I.40.1       & $n = n_0e^{-\frac{mgx}{k_bT}}$     & $10^{-2}$ & $10^{-1}$\\
I.41.16      & $L_{rad} = \frac{\hbar\omega^3}{\pi^2c^2(e^{\frac{\hbar\omega}{k_bT}}-1)}$ & $10^{-5}$ & $10^{-4}$ \\
I.43.16      & $v = \frac{\mu_{drift}q V_e}{d}$   & $10^{-2}$ &$10^{-1}$ \\
I.43.31      & $D = \mu_e k_bT$                            & $10^{-2}$ & $10^{-1}$\\
I.43.43      & $\kappa = \frac{1}{\gamma-1}\frac{k_bv}{A}$  & $10^{-3}$ & $10^{-1}$ \\
I.44.4       & $E = n k_b T \ln(\frac{V_2}{V_1})$       & $10^{-3}$&  $10^{-1}$\\
I.47.23      & $c = \sqrt{\frac{\gamma pr}{\rho}}$   & $10^{-2}$& $10^{-1}$ \\
I.48.2       & $E = \frac{m c^2}{\sqrt{1-v^2/c^2}}$ & $10^{-5}$ & $10^{-3}$\\
I.50.26 & $x = x_1[\cos(\omega t)+\alpha\> cos(\omega t)^2]$     &  $10^{-2}$ &  $10^{-1}$  \\
\hline
\end{tabular}
\caption{Tested Equations, part 1
\label{EqTableA}
}
}
\end{table*}

\begin{table*}[]
\begin{tabular}{|l|l|r|l|r|l|l|l|}
\hline
Feynman eq.   & Equation  &Old Noise tolerance &New Noise tolerance\\
\hline
II.2.42   & P     $ = \frac{\kappa(T_2-T_1)A}{d}$  & $10^{-3}$ &$10^{-1}$ \\
II.3.24   & $F_E = \frac{P}{4\pi r^2}$        & $10^{-2}$  & $10^{-1}$\\
II.4.23   & $V_e = \frac{q}{4\pi\epsilon r}$           & $10^{-2}$ & $10^{-1}$\\
II.6.11 & $V_e =\frac{1}{4\pi\epsilon}\frac{p_d\cos (\theta)}{r^2}$      & $10^{-3}$  & $10^{-1}$ \\
II.6.15a & $E_f = \frac{3}{4\pi\epsilon}\frac{p_d z}{r^5} \sqrt{x^2+y^2}$     & $10^{-3}$ & $10^{-2}$\\
II.6.15b & $E_f = \frac{3}{4\pi\epsilon}\frac{p_d}{r^3} \cos\theta\sin\theta$     & $10^{-2}$  & $10^{-2}$\\
II.8.7    & $E = \frac{3}{5}\frac{q^2}{4\pi\epsilon d}$   & $10^{-2}$ & $10^{-1}$\\
II.8.31   & $E_{den} = \frac{\epsilon E_f^2}{2}$          & $10^{-2}$ & $10^{-1}$\\
II.10.9   & $E_f = \frac{\sigma_{den}}{\epsilon}\frac{1}{1+\chi}$     & $10^{-2}$ &$10^{-1}$ \\
II.11.3 & $x = \frac{q E_f}{m(\omega_0^2-\omega^2)}$ & $10^{-3}$       & $10^{-2}$\\
II.11.7 & $n = n_0(1+ \frac{p_d E_f \cos\theta}{k_b T})$      & $10^{-2}$   & $10^{-1}$  \\
II.11.20  & $P_* = \frac{n_\rho p_d^2 E_f}{3 k_b T}$      & $10^{-3}$& $10^{-1}$ \\
II.11.27 & $P_* = \frac{n\alpha}{1-n\alpha/3}\epsilon E_f$ & $10^{-3}$   &  $10^{-1}$  \\
II.11.28  & $\theta = 1+\frac{n\alpha}{1-(n\alpha/3)}$    & $10^{-4}$  &$10^{-2}$ \\
II.13.17  & $B = \frac{1}{4 \pi \epsilon c^2}\frac{2I}{r}$ & $10^{-2}$&$10^{-1}$  \\
II.13.23  & $\rho_c = \frac{\rho_{c_0}}{\sqrt{1-v^2/c^2}}$           & $10^{-4}$ & $10^{-2}$\\
II.13.24  & $j = \frac{\rho_{c_0}v}{\sqrt{1-v^2/c^2}}$     & $10^{-4}$ & $10^{-1}$\\
II.15.4   & $E = -\mu_M B \cos\theta$               & $10^{-3}$&  $10^{-1}$\\
II.15.5   & $E = -p_d E_f\cos\theta$  & $10^{-3}$ & $10^{-1}$\\
II.21.32  & $V_e = \frac{q}{4\pi\epsilon r(1-v/c)}$    & $10^{-3}$  &  $10^{-1}$\\
II.24.17 & $k = \sqrt{\frac{\omega^2}{c^2}-\frac{\pi^2}{d^2}}$       & $10^{-5}$ &  $10^{-2}$\\
II.27.16  & $F_E = \epsilon c E_f^2$        & $10^{-2}$& $10^{-1}$ \\
II.27.18  & $E_{den} = \epsilon E_f^2$            & $10^{-2}$& $10^{-1}$ \\
II.34.2a  & $I = \frac{qv}{2\pi r}$            & $10^{-2}$&  $10^{-1}$\\
II.34.2   & $\mu_M = \frac{q v r}{2}$                       & $10^{-2}$&  $10^{-1}$\\
II.34.11  & $\omega = \frac{g_{\_} q B}{2m}$         & $10^{-4}$ & $10^{-1}$\\
II.34.29a & $\mu_M = \frac{q h}{4\pi m}$       & $10^{-2}$&$10^{-1}$  \\
II.34.29b & $E = \frac{g_{\_} \mu_M B J_z}{\hbar}$ & $10^{-4}$&  $10^{-1}$\\
II.35.18 & $n = \frac{n_0}{\exp(\mu_m B/(k_b T))+\exp(-\mu_m B/(k_b T))}$      & $10^{-2}$& $10^{-2}$\\
II.35.21  & $M = n_\rho \mu_M \tanh(\frac{\mu_M B}{k_b T})$     & $10^{-4}$ &$10^{-4}$ \\
II.36.38 & $f = \frac{\mu_m B}{k_b T}+\frac{\mu_m\alpha M}{\epsilon c^2 k_b T}$      &  $10^{-2}$&  $10^{-1}$\\
II.37.1   & $E = \mu_M(1+\chi)B$   & $10^{-3}$  & $10^{-1}$\\
II.38.3   & $F = \frac{Y A x}{d}$         & $10^{-3}$&  $10^{-1}$\\
II.38.14  & $\mu_S = \frac{Y}{2(1+\sigma)}$           & $10^{-3}$  &$10^{-1}$ \\
III.4.32  & $n = \frac{1}{e^{\frac{\hbar\omega}{k_bT}}-1}$    & $10^{-3}$ & $10^{-2}$ \\
III.4.33  & $E = \frac{\hbar\omega}{e^{\frac{\hbar\omega}{k_b T}}-1}$  & $10^{-3}$   &  $10^{-3}$\\
III.7.38  & $\omega = \frac{2 \mu_M B}{\hbar}$   & $10^{-2}$  & $10^{-1}$ \\
III.8.54  & $p_{\gamma}$    $ = \sin(\frac{E t}{\hbar})^2$     & $10^{-3}$  &  $10^{-3}$ \\
III.9.52  & $p_{\gamma}$    $ = \frac{\frac{p_d E_f t}{\hbar}     \sin((\omega-\omega_0)t/2)^2}{((\omega-\omega_0)t/2)^2}$ & $10^{-3}$&   $10^{-1}$\\
III.10.19 & $E = \mu_M\sqrt{B_x^2+B_y^2+B_z^2}$    & $10^{-4}$ & $10^{-1}$\\
III.12.43 & $L = n\hbar$ & $10^{-3}$  &  $10^{-1}$\\
III.13.18 & $v = \frac{2 E d^2 k}{\hbar}$           & $10^{-4}$&  $10^{-1}$ \\
III.14.14 & $I = I_0 (e^{\frac{q V_e}{k_b T}}-1)$   & $10^{-3}$  &$10^{-1}$ \\
III.15.12 & $E = 2U(1-\cos(kd))$    & $10^{-4}$ &  $10^{-1}$ \\
III.15.14 & $m = \frac{\hbar^2}{2E d^2}$    & $10^{-2}$  &  $10^{-1}$\\
III.15.27 & $k = \frac{2\pi\alpha}{nd}$              & $10^{-3}$ &$10^{-1}$ \\
III.17.37 & $f = \beta(1+\alpha \cos\theta)$     & $10^{-3}$ &  $10^{-1}$\\
III.19.51 & $E = \frac{-mq^4}{2(4\pi\epsilon)^2\hbar^2}\frac{1}{n^2}$      & $10^{-5}$&   $10^{-2}$  \\
III.21.20 & $j = \frac{-\rho_{c_0} q A_{vec}}{m}$      &  $10^{-2}$   &  $10^{-1}$\\

\hline
\end{tabular}
\caption{Tested Equations, part 2.
\label{EqTableB}
}
\end{table*}

\clearpage
\bibliographystyle{unsrt}
\bibliography{feynman2}

\end{document}

config: arxiv


text:
\begin{document}

\newcommand{\rk}{\mathsf{rk}}
\newcommand{\RR}{\mathsf{R}}
\newcommand{\LL}{\mathsf{L}}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}

\newcommand{\esp}{\vskip .3cm \noindent}

\newcommand{\el}{{\cal L}}
\newcommand{\de}{{\cal D}}
\newcommand\Cfty{${\cal C}^{\infty}$}
\newcommand{\emm}{{\cal M}}
\newcommand{\be}{{\cal B}}
\newcommand{\ess}{{\cal S}}
\newcommand{\enn}{{\cal N}}
\newcommand{\ka}{{\cal K}}
\newcommand{\emmh}{\hat {\cal M}}
\newcommand{\RD}{\text{\rm RD}}
\newcommand{\definition}{\overset{\text{\rm def}}{=}}
\newcommand{\graph}{\text{\rm graph}}

\def\CC#1{${\cal C}^{#1}$}
\def\wt#1{\widetilde{#1}}
\def\wh#1{\widehat{#1}}
\def\verti#1#2{\scriptsize\binom{#2}{#1}}

\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{defi}[prop]{Definition}
\newtheorem{thm}[prop]{Theorem}

\newtheoremstyle{mypl}{10pt}{10pt}{\it}{}{\em}{.}{ }{}
\theoremstyle{mypl}
\newtheorem{claim}{Claim}[prop]
\renewcommand\theclaim{\Alph{claim}}
\newtheorem*{claim*}{Claim}

\newtheoremstyle{myrem}{10pt}{10pt}{\rm}{}{\bf}{.}{ }{}
\theoremstyle{myrem}
\newtheorem*{rem}{Remark}

\renewcommand{\theprop}{\thesection.\arabic{prop}}

\centerline{\bf LONG LINE KNOTS}
\baselineskip=13pt
\vspace*{0.37truein}
\centerline{\footnotesize MATHIEU BAILLIF \& DAVID CIMASONI}
\vspace*{0.37truein}
\begin{abstract}
  We study continuous embeddings of the long line $\LL$ into $\LL^n$ $(n\ge 2)$ up to ambient isotopy of $\LL^n$. We define the direction of an embedding
  and show that it is (almost)
  a complete invariant in the case $n=2$ for continuous embeddings, and in the case $n\ge 4$ for differentiable ones. Finally, we
  prove that the classification of smooth embeddings $\LL\to\LL^3$ is equivalent to the classification of classical oriented knots.
\end{abstract}
\section*{Introduction}

Consider the following general problem:
\begin{equation}\tag{$\star$}
  \begin{array}{c}
    \text{Given finite dimensional manifolds $X,Y$, classify}\\
    \text{the embeddings $X\to Y$ up to ambient isotopy of $Y$.}
  \end{array}
  \label{problem}
\end{equation}
An instance of this problem is classical
knot theory, where $X=\mathbb{S}^1$, $Y=\mathbb{S}^3$ and the embeddings are assumed smooth (or PL).
Another instance is higher dimensional knot theory, where
$X=\mathbb{S}^k$ and $Y=\mathbb{S}^n$.
These fields have been very popular among mathematicians for over a century; there is a considerable litterature
about the classification of (topological, differentiable or PL) embeddings from a $k$-sphere to an $n$-sphere.

On the other hand, the study of this problem for non-metrizable manifolds remains to be done.
Even the study of homotopy and isotopy classes of maps of non-metrizable
manifolds seems to be at its very beginning. To our knowledge, David Gauld \cite{Gauld} was the first ever to publish a paper on the subject
(see also \cite{DeoGauld}). He investigated homotopy classes of maps of the {\em long line} $\LL$ (and of
the {\em long ray} $\RR$) into itself (see Definition \ref{Longlinedef} below), showing that
there are exactly $2$ such classes for the long ray, and $9$ for the long line.
He also proved that all embeddings $\RR\to\RR$ are isotopic, and that there are
$2$ isotopy classes
of embeddings $\LL\to\LL$. These results provide a solution to Problem (\ref{problem}) for $X=Y=\RR,\LL$.

In this paper, we investigate Problem (\ref{problem}) with $X=\LL$, $Y=\LL^n$ and $X=\RR$, $Y=\RR^n$.
We introduce a numerical invariant of embeddings $\RR\to\RR^n$ or $\LL\to\LL^n$ called the {\it direction},
see Definition \ref{def direction} and Theorem \ref{thm:invariant}.
Roughly speaking, two knots (that is, two embeddings) have the same direction if for all $1\le i\le n$, their projections on
the $i$-th coordinate
are either both cofinal or both bounded.

Our first results are that the direction is (almost) a complete invariant in the cases
$n=2$ for continuous embeddings (Theorems \ref{thm1} and \ref{corthm1}) and
$n\ge 4$ for smooth embeddings (Theorem \ref{thm2} and \ref{corthm2}). It follows that for these $n$,
there are exactly $2^n-1$ long ray knots and $(3^n-1)^2+(n-2)2^{n-1}$ long line knots (in the classes specified above).
We also prove that there are $7$ smooth knots $\RR\to\RR^3$ (Theorem \ref{thm3}).
Finally, our last result shows that the classification of differentiable embeddings $\LL\to\LL^3$ reduces to classical oriented knot theory
(see Proposition \ref{prop:ass} and Theorem \ref{thm4}).

The paper is organized as follows: Section \ref{secdef} deals with the definition of some basic objects, such as the long ray $\RR$,
the long line $\LL$, and the equivalence relation for knots. In Section \ref{sectools}, we prove several technical lemmas
(mainly partition and covering properties) that are used in
Section \ref{secres}, which contains all the main results.

The authors wish to acknowledge Claude Weber, David Gauld and Ren\'e Binam\'e.

\section{Definitions}\label{secdef}
For any ordinal $\alpha$, let us denote by $W(\alpha)$ the set of ordinals strictly smaller than $\alpha$.
\begin{defi}
\label{Longlinedef}
  The (closed) long ray $\RR$ is the set $W(\omega_1)\times[0,1[$,
  equipped with the lexicographic order and the order topology.
  The long line $\LL$ is the union of two copies $\LL_-,\LL_+$ of $\RR$ glued at $(0,0)$.
  We put the reverse order on $\LL_-$, so that $\LL$ is totally ordered.
\end{defi}
We will often identify $\alpha\in W(\omega_1)$ with $(\alpha,0)\in\RR$ and similarly for $\LL$.
Recall that $\RR$ and $\LL$ are non-metrizable, non-contractible and sequentially compact.
Also, $\LL$ and $\RR$ can be given a structure of oriented \CC{\infty} manifold. We will assume
throughout the text that we are given a {\em fixed} maximal atlas $\{U_j,\psi_j\}$ on $\LL$ (and on $\RR$)
with $U_j\ni 0$ for all $j$.
The atlas on $\LL^n$ (or $\RR^n$) is then assumed to be $\{(U_j)^n,(\psi_j,\dots,\psi_j)\}$,
the so-called `$n$-th power structure'.\footnote{These precisions are necessary, since P.J. Nyikos \cite{Nyikos:1992}
showed  that there are
uncountably many non-equivalent differentiable structures on $\LL$ (and thus, on $\LL^n$). Moreover, it is not clear that any differentiable structure on
$\LL^n$ is equivalent to a product of structures on $\LL$.}
This assumption is, in our opinion, quite natural.
For instance, it
ensures that the maps $\RR\to\RR^2$, given by
$x\mapsto (x,x)$ and $x\mapsto (x,c)$ are smooth, where $c$ is any constant.
Throughout the text, $\pi_i$ will denote the projection on the $i$-th coordinate of $\LL^n$ or $\RR^n$.
\begin{defi}
  We call an embedding from $X$ to $Y$ a $(Y,X)$-knot.
  Two $(\LL^n,\LL)$-knots $f,g$ are equivalent, which we denote by $f\sim g$,
  if there is an isotopy $\phi_t$ $(t\in[0,1])$ of $\LL^n$
  such that $\phi_0=id$ and $\phi_1\circ f=g$.
\end{defi}
Since $\RR$ is a manifold with boundary, we have to be more careful with the definition of equivalent
$(\RR^n,\RR)$-knots.
One possibility is to consider only embeddings of $\RR$ in the interior of $\RR^n$. Here is another
way to state the same equivalence relation:
\begin{defi}
  Let $\RR'$ be the set $(\{-1\}\times [0,1[)\sqcup\RR$ equipped with the order topology.
  Two $(\RR^n,\RR)$-knots $f,g$ are equivalent, which we denote by $f\sim g$,
  if there is an isotopy $\phi_t$ $(t\in[0,1])$ of $(\RR')^n$
  such that $\phi_0=id$ and $\phi_1\circ f=g$.
\end{defi}

\section{Tools}\label{sectools}

Let us begin by recalling the following well-known lemma; the proof of the corresponding statement
for ordinals can be found in any book on set theory.
\begin{lemma}\label{closedcofinal}
  Let $\{E_m\}_{m<\omega}$ be closed and cofinal subsets of $\RR$. Then $\bigcap_{m<\omega}E_m$ is also closed and cofinal in $\RR$.
  \hfill $\Box$
\end{lemma}
\noindent
We shall now investigate partition and covering properties of embeddings $\RR\to\RR^n$.
\begin{lemma}\label{partition}
  Let $\{f_k\}_{k\in K}$ be a finite or countable family of continuous maps $\RR\to\RR$. \\
  a) If each $f_k$ is bounded, there
  is a $z$ in $\RR$ such that $f_k$ is constant on $[z,\omega_1[$ for all $k\in K$. \\
  b) If each $f_k$ is cofinal, there is a
  cover $\mathcal{P}=\{[x_\alpha,x_{\alpha+1}]\}_{\alpha<\omega_1}$ of $\RR $ such that
  $x_\alpha<x_\beta$ if $\alpha<\beta$,
  $x_\beta =\sup_{\alpha<\beta} x_\alpha$ if $\beta$ is a limit ordinal,
  and for all $k\in K$,
  $f_k([x_\alpha,x_{\alpha+1}])=[x_\alpha,x_{\alpha+1}]$ for $\alpha>0$
  and $f_k([0,x_1])\subset [0,x_1]$.
\end{lemma}
\noindent{\em Proof:}
a) By \cite[Lemma 3.4 (iii)]{Nyikos:1984}, there exists $z_k\in \RR$ such that $f_k$ is constant on $[z_k,\omega_1[$. Take $z=\sup_{k\in K}z_k$.\\
b) This is a consequence of the following claims:
\begin{claim}\label{clm1}
  $A_k\definition\{ x\in \RR \, |\,  f_k(y)\le x \,\,\forall y\le x\}$ is closed and
  cofinal in $\RR $.
\end{claim}
\begin{claim}\label{clm2}
 $B_k\definition\{ x\in \RR \, |\,  f_k(y)\ge x \,\,\forall y\ge x\}$ is closed and cofinal
 in $\RR $.
\end{claim}
Indeed, these two claims together with Lemma \ref{closedcofinal} imply that the set
$E=\bigcap_{k\in K}(A_k\cap B_k)=\{x\in\RR\,|\,f_k([0,x])\subset[0,x]\mbox{ and }f_k([x,\omega_1[)\subset[x,\omega_1[\,\, \forall k\in K\}$
is closed and cofinal. We then define by
transfinite induction
$x_\alpha\in E$ for each $\alpha<\omega_1$ as follows.
Set $x_0=0$,
$x_{\alpha+1}=\min (E\cap [x_\alpha+1,\omega_1[)$,
and
$x_\beta=\sup_{\alpha<\beta}x_\alpha$ if $\beta$ is a limit ordinal.
(Recall that for any limit ordinal $\beta<\omega_1$, there is a sequence $\{\alpha_i\}_{i<\omega}$, with $\alpha_i<\beta$, such
that $\lim_{i\to\infty}\alpha_i=\beta$. Therefore, $x_\beta=\lim_{i\to\infty}x_{\alpha_i}$ belongs to $E$.)
\esp
{\it Proof of Claim \ref{clm1}:} Closeness is obvious (recall that a sequentially closed subset of $\RR$ is closed).
Given $z$ in $\RR$, one can choose a sequence $\{x_j\}_{j<\omega}$
such that $z < x_j \le x_{j+1}$  and
$\sup_{[0,x_j]} f_k \le x_{j+1}$. The sequence converges to a point $x>z$,
and $x\in A_k$.
\esp
{\it Proof of Claim \ref{clm2}:} Again, closeness is obvious. Fix $z$ in $\RR$;
for any $x\in\RR$, there is a $y\in\RR $ with $y\ge x$ such that
$f_k([y,\omega_1[)\subset [x,\omega_1[$.
(Otherwise, the set of $y$ such that $f_k(y)< x$ is cofinal and closed;
by
cofinality of $f_k$, so is
the set of $y'$ such that $f_k(y')> x$. By Lemma \ref{closedcofinal},
there would exist $v$ such that $f_k(v)< x$ and $f_k(v)> x$, which is impossible.)
We then define sequences $x_j,y_j$ ($j<\omega$) such that
$z < x_j\le y_j\le x_{j+1}$ and $f_k([y_j,\omega_1[)\subset [x_j,\omega_1[$.
The sequences $x_j,y_j$ converge to the same point $x>z$, which belongs to $B_k$.
\hfill $\Box$
\begin{lemma}\label{pearl necklace lemma}
  Let $\mathcal{P}=\{[x_\alpha,x_{\alpha+1}]\}_{\alpha<\omega_1}$ be a cover of $\RR$ with
  $x_\alpha<x_\beta$ if $\alpha<\beta$ and $x_\beta=\sup_{\alpha<\beta} x_\alpha$ if $\beta$ is a limit ordinal,
  and let $S_\alpha$ be the cube $[x_\alpha,x_{\alpha+1}]^n$.
  Then, for all $0<\alpha<\omega_1$, there are
  closed subsets $B_\alpha$ of $\RR^n$, diffeomorphic to a compact ball in $\R^n$,
  such that
  \begin{itemize}
    \item[$\bullet$]
    $B_\alpha\supset S_\alpha$,
    \item[$\bullet$]
    $\partial B_\alpha\cap S_\alpha=\{(x_\alpha,\dots,x_\alpha),(x_{\alpha+1},\dots,x_{\alpha+1})\}$,
    \item[$\bullet$]$\partial B_\alpha\cap S_\beta=S_\alpha\cap S_\beta$ if $\alpha\not=\beta$.
  \end{itemize}
\end{lemma}
\begin{figure}[h]
\begin{center}
  \epsfig{figure=fig3b.eps,  height=5cm}
  \caption{Lemma \ref{pearl necklace lemma} for $n=2$.}
 \label{fig:pearl}
\end{center}
\end{figure}
\noindent{\em Proof:}
Let $\beta$ be a limit ordinal or $1$. Consider $\psi_\beta:U_\beta\to\R$ the smallest chart such that
$U_\beta\supset[0,x_{\beta+\omega}]$ (such a chart always exists), and
$\wt{\psi}_\beta=(\psi_\beta,\dots,\psi_\beta):(U_\beta)^n\to\R^n$, which belongs
to the atlas of $\RR^n$.
Clearly, $\wt{\psi}_\beta(S_\alpha)$ is a cube in $\R^n$ for any $\alpha<\beta+\omega$.
We can therefore form ellipsoids $B_\alpha '$ for $\beta\le\alpha<\beta+\omega$ as in Figure \ref{fig:pearl},
and define $B_\alpha=\wt{\psi}_\beta^{-1}(B_\alpha ')$ for $\beta\le\alpha<\beta+\omega$.
Note that $B_\beta '\cap \wt{\psi}_\beta([0,x_\beta]^n)=\{\wt{\psi}_\beta(x_\beta)\}$.
Since $W(\omega_1)\backslash\{0\}=[1,\omega[\,\sqcup\,\,\bigsqcup_{\beta \text{ lim.}}[\beta,\beta+\omega[$,
we obtain the desired properties.
\hfill $\Box$
\begin{figure}[h]
\begin{center}
  \epsfig{figure=boxing.eps,  height=6cm}
  \caption{Lemma \ref{boxing lemma} for $n=3$, $s=1$.}
  \label{fig:boxing}
\end{center}
\end{figure}
\begin{lemma}\label{boxing lemma}
Let $f:\RR\to\RR^n$ be continuous, with $\pi_i\circ f$ bounded for $i=1,\dots,s$ $(s<n)$ and
cofinal for $i=s+1,\dots,n$. Then, there exists a cover
$\mathcal{P}=\{[x_\alpha,x_{\alpha+1}]\}_{\alpha<\omega_1}$ of $\RR$ and
a cover
$\mathcal{D}=\{D_\alpha\}_{0<\alpha<\omega_1}$ of $f([x_1,\omega_1[)$ with
$D_\alpha$ diffeomorphic to the compact ball in $\R^n$,
such that (see Figure \ref{fig:boxing}):
\begin{itemize}
\item[$\bullet$]
  $f(x)\subset\{c\}\times\RR^{n-s}\;\forall x\ge x_1$, for some fixed $c\in\RR^s$,
\item[$\bullet$]
  $f(x_\alpha)=(c,x_\alpha,\dots,x_\alpha)$ $\forall \alpha>0$,

\item[$\bullet$]
  $f^{-1}(D_\alpha)=[x_\alpha,x_{\alpha+1}]$ and $f^{-1}(\partial D_\alpha) = \{x_\alpha,x_{\alpha+1}\}$ $\forall\alpha>0$,

\item[$\bullet$]
  $D_\alpha\cap D_\beta=\left\{\begin{array}{ll}
            \emptyset &\text{\rm if }\alpha\not=\beta\pm 1\\
            (c,x_\alpha,\dots,x_\alpha)&\text{\rm if }\alpha=\beta+ 1.
            \end{array}
            \right.$
\end{itemize}
\end{lemma}
\noindent{\em Proof:}
By Lemma \ref{partition} a), there is some $z\in\RR$ such that $\pi_i\circ f$ is
constant on $[z,\omega_1[$ for $i=1,\dots,s$. Set $c_i=\pi_i\circ f(z)$ and $c=(c_1,\dots,c_s)$.
For $i=s+1,\dots,n$,
take the cover $\mathcal{P}$ for the family $\{\pi_i\circ f\}_{i=s+1,\dots,n}$ with $x_1>z$ given by
Lemma \ref{partition} b).
By construction, the cover $\mathcal{P}=\{I_\alpha\}_{\alpha<\omega_1}$, with $I_\alpha=[x_\alpha,x_{\alpha+1}]$, satisfies
the first two claims.
Choose now for each $i=1,\dots,s$ a compact interval $J_i$ containing $c_i$ in its interior, and
set $J=J_1\times\cdots\times J_s$.
By Lemma \ref{pearl necklace lemma} applied to the cover $\mathcal{P}$, we get closed sets $B_\alpha\subset\RR^{n-s}$,
such that $B_\alpha$
contains $(I_\alpha)^{n-s}$ for all $\alpha>0$.
Therefore, $f(I_\alpha)\subset D_\alpha'\definition J\times B_\alpha$ for $\alpha>0$, and
the intersection
$\partial D_\alpha'\cap f(I_\alpha)$ is equal to $\{f(x_\alpha),f(x_{\alpha+1})\}$.
By construction, $D_\alpha'\cap D_{\alpha+1}'=J\times\{(x_{\alpha+1},\dots,x_{\alpha+1})\}$.
Since $B_\alpha$ is a $(n-s)$-compact ball and
$f(I_\alpha)$ is contained in the hyperplane
$x_1=c_1,\dots,x_s=c_s$, one can find a subset $D_\alpha$ of $D_\alpha'$ which is diffeomorphic
to the compact ball in $\R^n$, that has the desired boundary properties (see Figure 3).
\hfill $\Box$
\begin{figure}[h]
  \begin{center}
  \epsfig{figure=fig4.eps, height=3cm}
  \caption{The subset $D_\alpha$ of $J\times B_\alpha$.}
\end{center}
\end{figure}
\begin{prop}
  \label{Schonfliess}
  Let $B$ be the closed unit ball in $\R^n$, and let
  $f,g:[0,1]\to B$ be continuous embeddings with $f^{-1}({\partial B})=g^{-1}({\partial B})=\{0,1\}$,
  $f(0)=g(0)$ and $f(1)=g(1)$. Then, there exists an isotopy $\phi_t:B\to B$ $(t\in[0,1])$ keeping $\partial B$ fixed,
  such that $\phi_0=id_B$ and $\phi_1\circ f=g$, if one of the following conditions holds:\\
  a) $n=2$,
  \\
  {b) $n\ge 4$ and $f,g$ are \CC{1} embeddings.}\\
  Suppose now that $f^{-1}({\partial B})=g^{-1}({\partial B})=\{0\}$ and $f(0)=g(0)$. Then, we have the same conclusion if:\\
  c) $n=2$, \\
  {d) $n\ge 3$ and $f,g$ are \CC{1} embeddings.}
\end{prop}
\noindent{\em Proof:}
Points a) and c) are direct consequences of Sch\"onfliess theorem. Point b) follows from Zeeman's unknotting theorem (see e.g.
\cite[Theorem 7.1]{RourkeSanderson}). Point d) follows from assertion b) for $n\ge 4$; for $n=3$, consider a good projection.
\hfill $\Box$

\section{Classification of long knots}\label{secres}

We are now ready to present our main results.
\begin{defi}\label{def direction}
The direction of a continuous function $f:\RR\to\RR^n$ is the vector
$D(f)=\left(\begin{array}{ccc}\delta_1(f)&\dots &\delta_n(f)\end{array}\right)^T$, where
$$
\delta_i(f)=\left\{\begin{array}{ll}
		1& \mbox{if $\pi_i\circ f$ is cofinal;}\\
		0& \mbox{if $\pi_i\circ f$ is bounded.}
		\end{array}\right.
$$
If $g:\RR\to\LL^n$ is continuous, let us define $\delta(g)=\left(\begin{array}{ccc}\delta_1(g)&\dots &\delta_n(g)\end{array}\right)^T$ as follows:
$$
\delta_i(g)=\left\{\begin{array}{lll}
		+1& \mbox{if $\pi_i\circ g$ is cofinal in $\LL_+$;}\\
		-1& \mbox{if $\pi_i\circ g$ is cofinal in $\LL_-$;}\\
		\phantom{-}0& \mbox{if $\pi_i\circ g$ is bounded.}
		\end{array}\right.
$$
The direction of a continuous fonction $f:\LL\to\LL^n$ is the $(n\times 2)$-matrix
$D(f)=\left(\begin{array}{cc}\delta(f|_{\LL_-})&\delta(f|_{\LL_+})\end{array}\right)$.
\\
A matrix $D$ is a $(Y,X)$-direction ($X=\RR,\LL$, $Y=\RR^n,\LL^n$) if $D=D(f)$ for some
continuous $f:X\to Y$.
\end{defi}
\begin{thm}\label{thm:invariant}
The direction is an invariant of $(\RR^n,\RR)$ and $(\LL^n,\LL)$-knots.
\end{thm}
\noindent{\em Proof:}
Let $f,g:\RR\to\RR^n$ be two continuous embeddings with $D(f)\neq D(g)$. Without loss of generality, it may be assumed that
$\pi_1\circ f$ is bounded and $\pi_1\circ g$ cofinal. Then, $f$ and $g$ are not equivalent. Indeed, consider an isotopy $\phi_t$ of $(\RR')^n$
such that $\phi_0=id$ and $\phi_1\circ f=g$; then, $\pi_1\circ\phi_t\circ f:\RR\to\RR'$ provides a homotopy between $\pi_1\circ f:\RR\to\RR\subset\RR'$
and $\pi_1\circ g:\RR\to\RR\subset\RR'$. Since $\pi_1\circ f$ is bounded, it follows from Lemma \ref{partition} a) that $\pi_1\circ f$ is homotopic to
a constant. On the other hand, Lemma \ref{partition} b) implies that $\pi_1\circ g$ is homotopic to the canonical inclusion $\RR\subset\RR'$. Therefore,
we would have a homotopy from a constant map to the inclusion $\RR\subset\RR'$. Since this inclusion is a homotopy equivalence, and since $\RR$
is not contractible (see e.g. \cite{Gauld}), such an homotopy does not exist. The proof for $(\LL^n,\LL)$-knots is very similar.
\hfill $\Box$

\subsection*{$(\RR^2,\RR)$ and $(\LL^2,\LL)$-knots}
\begin{thm}\label{thm1}
  The direction is a complete invariant for $(\RR^2,\RR)$-knots. Therefore, there are exactly $3$ classes of non-equivalent $(\RR^2,\RR)$-knots.
\end{thm}
\noindent{\em Proof:}
There are $4$ possible directions for a continuous map $f:\RR\to\RR^2$. If $f$ is an embedding, the direction $D=\verti{0}{0}$ is impossible.
(Otherwise, by Lemma \ref{partition} a), there would be some $z\in\RR$ such that $f$ is constant on $[z,\omega_1[$.) Therefore, we are left with three
possible directions, realized by the following $(\RR^2,\RR)$-knots: $f_{\verti{1}{0}}(x)=(0,x)$, $f_{\verti{0}{1}}(x)=(x,0)$ and $f_{\verti{1}{1}}(x)=(x,x)$.
By Theorem \ref{thm:invariant}, we just need to show that an $(\RR^2,\RR)$-knot $f$ with direction $D$ is equivalent to $f_D$, for
$D=\verti{1}{1},\verti{0}{1}$, and $\verti{1}{1}$.

Let us first assume that $D=\verti{1}{1}$, and let $\{I_\alpha=[x_\alpha,x_{\alpha+1}]\}_{\alpha<\omega_1}$ and $\{D_\alpha\}_{0<\alpha<\omega_1}$ be the covers
given by Lemma \ref{boxing lemma}.
Each $D_\alpha$ satisfies the hypotheses of Proposition \ref{Schonfliess} a),
with $f=f|_{I_\alpha}$ and $g=f_{\verti{1}{1}}|_{I_\alpha}$. Thus, we can find isotopies $(\phi_\alpha)_t$ of $D_\alpha$ $(rel \; \partial D_\alpha)$
such that $(\phi_\alpha)_0=id$ and $(\phi_\alpha)_1\circ f|_{I_\alpha}=f_{\verti{1}{1}}|_{I_\alpha}$. Then, consider a set $D_0\subset(\RR')^2$,
diffeomorphic to the compact ball, that contains $f([0,x_1[)\cup f_{\verti{1}{1}}([0,x_1[)$ in its interior, and
such that $D_0\cap D_1=\{(x_1,x_1)\}$. Then, $D_0$ satisfies the assumptions of Proposition \ref{Schonfliess} c), and there
in an ambient isotopy $(\phi_0)_t$ of $D_0$ $(rel \; \partial D_0)$ between $f|_{I_0}$ and $f_{\verti{1}{1}}|_{I_0}$. Extending the ambient
isotopies $(\phi_\alpha)_t$ $(\alpha<\omega_1)$ by the identity outside $\cup_{\alpha<\omega_1}D_\alpha$, we have proved that $f\sim f_{\verti{1}{1}}$.

Now, consider the case where $D=\verti{0}{1}$ (the case $D=\verti{1}{0}$ is similar). As before, take the cover
$\{D_\alpha\}_{0<\alpha<\omega_1}$ of $f([x_1,\omega_1[)$ given by Lemma \ref{boxing lemma}, and choose $D_0\subset(\RR')^2$,
diffeomorphic to the compact ball, that contains $f([0,x_1[)\cup (\{c_1\}\times[0,x_1[)$ in its interior, and
such that $D_0\cap D_1=\{(c_1,x_1)\}$. By Proposition \ref{Schonfliess} c), there
is an ambient isotopy of $D_0$ $(rel \; \partial D_0)$ that sends $f([0,x_1])$ on $\{c_1\}\times[0,x_1]$. Extending it by the identity
outside $D_0$, we have an ambient isotopy between $\text{\rm Im}f$ and $\{c_1\}\times\RR$.
It is now straightforward to define an isotopy between $\{c_1\}\times\RR$ and $\{0\}\times\RR=\text{\rm Im}f_{\verti{0}{1}}$. Therefore,
we can assume that $\text{\rm Im}f=\text{\rm Im}f_{\verti{0}{1}}=\{ (x,0)\, |\, x\in\RR\}$.
In that case, $\pi_1\circ f$ is an homeomorphism of $\RR$. By \cite[Corollary 2]{Gauld}, there is an isotopy $\gamma_t$
of $\RR$ (keeping $0$ fixed) such that $\gamma_0=id_\RR$ and $\gamma_1=\pi_1\circ f$.
Then, the isotopy $\phi_t$ of $(\RR')^2$ given by $\phi_t(x,y)=(\gamma_t(x),y)$ if $x\in\RR$ and $\phi_t(x,y)=(x,y)$ otherwise
satisfies $\phi_0=id$ and $\phi_1\circ f_D=f$.
\hfill $\Box$
\esp

The direction is almost a complete invariant for $(\LL^2,\LL)$-knots. It fails to be complete only
because some directions correspond to exactly
two non-equivalent knots. This phenomenon also appears in dimension $n\ge 2$, motivating the following definition.

\begin{defi}\label{double direction}
  A double direction is an $(\LL^n,\LL)$-direction with equal columns that contain exactly one $0$.
\end{defi}
\begin{thm}\label{corthm1}
   There are exactly $64$ non-equivalent $(\LL^2,\LL)$-knots.
\end{thm}
\noindent{\em Proof:}
Given $f:\LL\to \LL^2$ continuous, there are $9^2$ possible direction matrices $\left(\delta(f|_{\LL_-})\;\delta(f|_{\LL_+})\right)$. If $f$ is an
$(\LL^2,\LL)$-knot, the restrictions $f|_{\LL_-}$ and $f|_{\LL_+}$ are embeddings; by Lemma \ref{partition} a),
this implies that the columns
$\delta(f|_{\LL_-})$ and $\delta(f|_{\LL_+})$ are non-zero. Furthermore, the following four directions are also forbidden:
$$
\scriptstyle
\left(\begin{array}{cc}+1&+1\\+1&+1\end{array}\right)\,,\;\;\left(\begin{array}{cc}+1&+1\\-1&-1\end{array}\right)\,,\;\;
\left(\begin{array}{cc}-1&-1\\+1&+1\end{array}\right)\,\;\mbox{and}\;\;\left(\begin{array}{cc}-1&-1\\-1&-1\end{array}\right)\,.
$$
(Indeed, let us consider a continuous map $f:\LL\to \LL^2$ with direction matrix

$\verti{+1\, +1}{+1\, +1}$.
Since $\delta(f|_{\LL_+})=\verti{+1}{+1}$, it follows from Lemma \ref{partition} b) that the sets
$\{x\in\LL_+\;|\;\pi_1\circ f(x)=x\}$ and $\{x\in\LL_+\;|\;\pi_2\circ f(x)=x\}$ are
closed and cofinal. By Lemma \ref{closedcofinal}, so is their intersection $\{x\in\LL_+\;|\;f(x)=(x,x)\}$. Similarly,
$\delta(f|_{\LL_-})=\verti{+1}{+1}$ implies that $\{y\in\LL_-\;|\;f(y)=(-y,-y)\}$ is closed and cofinal.
By Lemma \ref{closedcofinal} again, the set $\{z\in\LL_+\;|\;f(z)=(z,z)=f(-z)\}$ is cofinal, so $f$ is not an embedding. The
other three cases are similar.) So, we are left with $(9-1)^2-4=60$ possible directions for an $(\LL^2,\LL)$-knot. It is easy to
exhibit a knot realizing each of these directions.

As in Theorem \ref{thm1}, one shows that
two knots with the same direction $D$ are equivalent, except if $D$ is a double direction.
To each double direction correspond exactly two classes of knots, as we shall see.
Since there are four double directions, namely
$$
\left(\begin{array}{rr}+1&+1\\0&0\end{array}\right)\,,\;\;\left(\begin{array}{rr}-1&-1\\0&0\end{array}\right)\,,\;\;
\left(\begin{array}{rr}0&0\\+1&+1\end{array}\right)\,\;\mbox{and}\;\;\left(\begin{array}{rr}0&0\\-1&-1\end{array}\right)\, ,
$$
the theorem follows.
Let $D$ be the first of these directions, and let $f:\LL\to\LL^2$
be an embedding with $f(x)=(x,1)$ for $x\ge 1$ and $f(x)=(-x,-1)$ for $x\le -1$
(as usual, we denote by $-x$ the point in $\LL_-$ corresponding to $x\in\LL_+$, and
vice versa).  Finally, let $g:\LL\to\LL^2$ be the knot given by $g(x)=f(-x)$.
Clearly, $D=D(f)=D(g)$ and any $(\LL^2,\LL)$-knot with direction $D$
is equivalent to either $f$ or $g$. It remains to check that $f$ and $g$ are non-equivalent.
Indeed, let $\phi_t$ be an isotopy between $f$ and $g$, i.e.
$\phi_0=id$ and $\phi_1\circ f=g$.
Since $\pi_2\circ\phi_t\circ f$ is a bounded continuous map $\LL\to\LL$, Lemma \ref{partition} a)
implies that $\pi_2\circ\phi_t\circ f([x,\omega_1[)$ is a single point for $x$ large enough.
Let us denote it by
$r_+(t)$, and similarly, let $r_-(t)$ be the element defined by $\pi_2\circ\phi_t\circ f(]-\omega_1,-x])$ for
$x$ large enough.
One checks that $r_+$ and $r_-$ are continuous. Since
$r_+(0)=r_-(1)=1$ and $r_+(1)=r_-(0)=-1$, there is some $t_0$ for which $r_+(t_0)=r_-(t_0)$. Then,
$\phi_{t_0}\circ f$ is not an embedding.
The other double directions are similarly treated.
\hfill $\Box$

\subsection*{Differentiable $(\RR^n,\RR)$ and $(\LL^n,\LL)$-knots for $n\ge 4$}

\begin{thm}\label{thm2}
  There are exactly $(2^n-1)$ non-equivalent differentiable $(\RR^n,\RR)$-knots if $n\ge 4$.
\end{thm}
\noindent{\em Proof:} Given $f$ an $(\RR^n,\RR)$-knot, at least one $\pi_i\circ f$ $(i=1,\dots,n)$ is cofinal;
hence, we have $2^n-1$ possible directions. Each of these directions $D$ can be realized by the $(\RR^n,\RR)$-knot $f_D$ given by $f_D(x)=x\cdot D^T$.
Now, we just need to prove that an $(\RR^n,\RR)$-knot $f$ with direction $D$ is equivalent to $f_D$.\\
By a permutation of the indices, it may be assumed that $\pi_i\circ f$ is bounded for $i=1,\dots,s$ and
cofinal for $i=s+1,\dots,n$. Consider the covers $\{[x_\alpha,x_{\alpha+1}]\}_{\alpha<\omega_1}$ of $\RR$ and
$\{D_\alpha\}_{0<\alpha<\omega_1}$ of $f([x_1,\omega_1[)$ given by Lemma \ref{boxing lemma}. For $i=1,\dots,s$, take an isotopy $\phi^i_t$ of $\RR'$
between $\pi_i\circ f(x_1)=c_i$ and $0$; the isotopy $\phi_t=(\phi^1_t,\dots,\phi^s_t,id,\dots,id)$ then sends $f([x_1,\omega_1[)$ on $\{0\}\times\RR^{n-s}$.
Using Proposition \ref{Schonfliess} d), we may assume that $f=f_D$ on $[0,x_1]$. By Proposition \ref{Schonfliess} b), we have an isotopy $(\phi_\alpha)_t$
in $D_\alpha$ between $f|_{[x_\alpha,x_{\alpha+1}]}$ and $f_D|_{[x_\alpha,x_{\alpha+1}]}$ for all $0<\alpha<\omega_1$. Extending this isotopy by the identity
outside $\cup_\alpha D_\alpha$, it follows that $f\sim f_D$.
\hfill $\Box$

\begin{thm}\label{corthm2}
 There are exactly $(3^n-1)^2+(n-2)2^{n-1}$
 non-equivalent differentiable $(\LL^n,\LL)$-knots if $n\ge 4$.
\end{thm}
\noindent{\em Proof:} We have $(3^n)^2$ possible directions for a continuous map $f:\LL\to\LL^n$. If $f$ is an embedding,
$\delta(f|_{\LL_-})$ and $\delta(f|_{\LL_+})$ are non-zero, giving $(3^n-1)^2$ directions. Furthermore, a direction matrix with
identical columns and no zero coefficient cannot be realized by an embedding (the argument is similar to the case $n=2$).
Therefore, we are left with $(3^n-1)^2-2^n$ directions, which can all clearly be realized by $(\LL^n,\LL)$-knots.
Finally, to any $(\LL^n,\LL)$-direction corresponds exactly one class of knots, except if
it is a double direction; in this case, there are exactly two classes of knots with this direction.
We thus have $(3^n-1)^2 - 2^n+n 2^{n-1}=(3^n-1)^2+(n-2)2^{n-1}$ different classes of knots.
\hfill $\Box$

\subsection*{Differentiable $(\RR^3,\RR)$ and $(\LL^3,\LL)$-knots}
\begin{thm} \label{thm3}
  There are $2^3-1=7$ non-equivalent differentiable $(\RR^3,\RR)$-knots.
\end{thm}
\noindent We shall need these two lemmas:
\begin{lemma}\label{monotone}
  Let $f$ be a differentiable $(\RR^3,\RR)$-knot such that $\pi_i\circ f$ is cofinal for $i=1,2,3$, and let
  $\mathcal{P}^3\definition\{[x_\alpha,x_{\alpha+1}]^3\}_{0<\alpha<\omega_1}$ with $x_\alpha$ as in Lemma \ref{boxing lemma}.
  Then, for all but finitely many $\alpha$, there is an index $i$ with $\pi_i\circ f$ monotone on $[x_\alpha,x_{\alpha+1}]$.
\end{lemma}
\begin{lemma} \label{monotone2}
  Let $f:[0,1]\to[0,1]^3$ be a differentiable embedding, and let $B$ be a compact $3$-ball such that $B\supset[0,1]^3$ and
  $\partial B\cap[0,1]^3=\{(0,0,0),(1,1,1)\}$. Suppose that $f(0)=(0,0,0)$, $f(1)=(1,1,1)$, and that $\pi_i\circ f$ is monotone for at least one $i$;
  then, there is an isotopy $\phi_t$ of $B$, which is the identity on $\partial B$, such that $\phi_0=id$ and $\phi_1\circ f(x)=(x,x,x)$.
\end{lemma}
\noindent{\em Proof of Lemma \ref{monotone}:}
Otherwise, let $\{\beta_m\}_{m<\omega}$ be an increasing sequence of ordinals such that $\pi_i\circ f$ is not monotone on
$I_{\beta_m}=[x_{\beta_m},x_{\beta_m+1}]$ for $i=1,2,3$, and let us denote by $\beta$ the limit of this sequence. For $m<\omega$ and
$i=1,2,3$, choose $x_{i,m},y_{i,m}\in I_{\beta_m}$ such that
$\pi_i\circ f$ is decreasing in a neighborhood of $x_{i,m}$ and increasing in a neighborhood of $y_{i,m}$.
In any chart containing $[0,x_\beta]$,
$(\pi_i\circ f)'(x_{i,m})\le 0$ and $(\pi_i\circ f)'(y_{i,m})\ge 0$ for any $m<\omega$ and $i=1,2,3$.
By construction, $\displaystyle\lim_{m\to\infty}x_{i,m}=\lim_{m\to\infty}y_{j,m}\definition u$ for any $i,j$.
By continuity,
$(\pi_i\circ f)'(u)=0$ for $i=1,2,3$, contradicting the $1$-regularity of $f$.
\hfill $\Box$
\esp
\noindent{\em Proof of Lemma \ref{monotone2}:}
Apply a descending curve argument.
\hfill $\Box$
\esp
\noindent{\em Proof of Theorem \ref{thm3}:}
Clearly, there are $7$ possible $(\RR^3,\RR)$-directions. Let us prove that two knots $f,g$ with $D(f)=D(g)$ are equivalent.\\
First, consider the case where $\pi_i\circ f$ is bounded for some index $i$ (let us say
that $i=1$). By Lemma \ref{partition} a), there is an $x_1$ in $\RR$ such that $\pi_1\circ f(x)=c$ for all $x\ge x_1$. Let $D_0$ be a compact
$3$-ball in $(\RR')^3$ such that $f([0,x_1])\subset D_0$, $f^{-1}(\partial D_0)=\{x_1\}$ and $f([0,x_1])\cap D_0=\{f(x_1)\}$. By Proposition
\ref{Schonfliess} d), $f$ is isotopic to an $(\RR^2,\RR)$-knot in $\{c\}\times\RR^2$. We can conclude with Theorem \ref{thm1}.\\
Now, let us assume that $\pi_i\circ f$ is cofinal for $i=1,2,3$. By
Lemmas \ref{monotone} and \ref{monotone2}, there is an $x$ in $\RR$ such that $f|_{[x,\omega_1[}$ is isotopic (in $[x,\omega_1[^3$) to the
knot $f_D$ given by $f_D(x)=(x,x,x)$. We then proceed as before for $f|_{[0,x]}$.
\hfill $\Box$

Let us now turn to $(\LL^3,\LL)$-knots. We will assume that $\mathbb{S}^3$
and $\LL^3$ have a fixed orientation.
Let $k$ be an oriented differentiable $(\mathbb{S}^3,\mathbb{S}^1)$-knot, and let $D$ be an $(\LL^3,\LL)$-direction.
If $D$ is not a double direction,
there is clearly a
unique equivalence class of `unknotted' differentiable $(\LL^3,\LL)$-knot with direction $D$; as before, let us denote a representant by $f_D$.
If $D$ is a double direction, there are exactly two such `unknotted' $(\LL^3,\LL)$-knots with direction $D$;
to simplify the notation we shall
abusively denote both by $f_D$.

\begin{defi}
  A differentiable $(\LL^3,\LL)$-knot $\wh{k}_D$ equivalent to the oriented connected sum $f_D\;\#\;k$ is called a $D$-associate of $k$.
  (See Figure \ref{fig:associate} for an example.)
\end{defi}
\begin{figure}[h]
  \begin{center}
    \epsfig{figure=associate.eps, height=3.5cm}
    \caption{The trefoil knot and its $D$-associate.}
    \label{fig:associate}
  \end{center}
\end{figure}
It is easy to show that, up to the subtleties due to the double directions,
the equivalence class of $\wh{k}_D$ only depends on the equivalence class of the oriented
$(\mathbb{S}^3,\mathbb{S}^1)$-knot $k$ and on the direction $D$: just follow the classical proof that the connected sum of
oriented differentiable $(\mathbb{S}^3,\mathbb{S}^1)$-knots is well defined.
Counting the directions as in Theorem \ref{corthm2}, we find immediately:
\begin{prop}\label{prop:ass}
  A differentiable $(\mathbb{S}^3,\mathbb{S}^1)$-knot has exactly $680$
  non-equivalent associates.\hfill $\Box$
\end{prop}
Moreover, the classification of smooth $(\LL^3,\LL)$-knots with direction $D$ is equivalent to the classification of
differentiable oriented $(\mathbb{S}^3,\mathbb{S}^1)$-knot. In other words:
\begin{thm}\label{thm4}
  A differentiable $(\LL^3,\LL)$-knot is the associate of a unique type of differentiable oriented $(\mathbb{S}^3,\mathbb{S}^1)$-knot.
\end{thm}
\noindent{\em Proof:} Let $f$ be a differentiable $(\LL^3,\LL)$-knot with direction $D$. Using the same argument as in Theorem \ref{thm3},
we see that for some $x_1\in\LL_+$, there is an isotopy $\varphi_t$ of $X=\LL^3\backslash]-x_1,x_1[^3$, keeping $\partial X$ fixed, such
that $\varphi_0=id_X$ and $\varphi_1\circ f|_{f^{-1}(X)}=f_D|_{f_D^{-1}(X)}$. Let $k$ be the smooth oriented $(\mathbb{S}^3,\mathbb{S}^1)$-knot
obtained by attaching both ends of $f|_{f^{-1}([-x_1,x_1]^3)}$  with an unknotted arc in $X$. By construction, $f$ is equivalent to $f_D\;\#\;k$, so
$f$ is the $D$-associate of $k$.
\\
Now, let $k,k'$ be two differentiable $(\mathbb{S}^3,\mathbb{S}^1)$-knots such that there is an ambient isotopy $\phi_t$ of $\LL^3$ with
$\phi_1\circ\wh{k}_D=\wh{k}'_D$. If $U_\alpha$ denotes the open cube $]-\alpha,\alpha[^3$ in $\LL^3$, then
$\{U_\alpha\,|\,\alpha<\omega_1\}$ is a {\em canonical sequence} in the sense of \cite[p. 147]{Gauld}.
By the proposition on the same page, the set
$$
  F_\phi\definition
  \{\alpha<\omega_1\,|\, \phi_t({\overline U_\alpha}\backslash U_\alpha)=
  {\overline U_\alpha}\backslash U_\alpha\, \forall t\}
$$
is cofinal in $W(\omega_1)$.
(The proposition is stated for $\omega$-bounded $2$-surfaces, but its proof shows
that it also holds for $\RR^n$ and $\LL^n$.) Take $\alpha$ large enough such that $\wh{k}_D|_{\LL^3\backslash U_\alpha}$ and
$\wh{k}'_D|_{\LL^3\backslash U_\alpha}$ are equal to $f_D|_{\LL^3\backslash U_\alpha}$; let us denote by $\{P_1,P_2\}$ the two points of
$\text{\rm Im}\wh{k}_D\cap({\overline U_\alpha}\backslash U_\alpha)=\text{\rm Im}\wh{k}'_D\cap({\overline U_\alpha}\backslash U_\alpha)$.
For all $t$, $\phi_t|:{\overline U_\alpha}\backslash U_\alpha\to{\overline U_\alpha}\backslash U_\alpha$ is a homeomorphism
isotopic $(rel\;\{P_1,P_2\})$ to the identity. Therefore, $\phi_t|$ can be extended to a homeomorphism $\widetilde{\phi}_t:B\to B$,
where $B$ is a compact ball containing ${\overline U_\alpha}$, with
$\widetilde{\phi}_t$ keeping $\partial B$ fixed. Extending $\widetilde{\phi}_t$ with the identity on $\mathbb{S}^3\backslash B$,
we get an isotopy between $k$ and $k'$.
\hfill $\Box$

\footnotesize

\bibliographystyle{plain}
\bibliography{/home/baillif/macros/biblio}

\vskip1cm
\noindent
Mathieu Baillif \\
Section de Math\'ematiques\\
2-4 rue du Li\`evre\\
1211 Gen\`eve 24\\
Switzerland\\
{\tt Mathieu.Baillif@math.unige.ch}

\vskip1cm
\noindent
David Cimasoni\\
Section de Math\'ematiques\\
2-4 rue du Li\`evre\\
1211 Gen\`eve 24\\
Switzerland\\
{\tt David.Cimasoni@math.unige.ch}

\end{document}


TITLE: Video lectures on graduate level Classical Electrodynamics
QUESTION [11 upvotes]: This is a rather broad question. Does anyone know of good video lectures for graduate level classical electrodynamics?

REPLY [2 votes]: https://ocw.metu.edu.tr/course/view.php?id=226

The above link has a list of videos for the Graduate Level Electrodynamics course. But it is more of the Classical Theory of Fields by Landau and the sections from Electromagnetics  in Continuous Media is not present. Still this course deals with Gauges, Green functions, Scattering, Diffraction and Covariant Formulation (a.k.a. tensor formulation of Maxwell Equations). I haven't looked at complete playlist but this is a good one to go for.

They even provided a YouTube playlist link for easy streaming!!
Here is the link: https://www.youtube.com/watch?list=PLuiPz6iU5SQ9d1uu1NrVO2BmCuyfddILt&v=LPnlqV5dGVI


TITLE: Does measuring the operator of a wave function collapse the wave function to the measured eigenstate?
QUESTION [1 upvotes]: Suppose you have a state described by the wave function $\psi(x) = \phi_1(x)+2\phi_2(x)+3\phi_3(x)$ , where the $\phi$s are normalised eigenfunctions of a Hermitian operator $\hat{O}$ with eigenvalues $\lambda_1 = 1, \lambda_2 = 5, \lambda_3 = 9$.
What happens to the wave function if you measure $\hat{O}$ and you obtain the result $\lambda_2=5$?
My answer is that the wave function immediately collapses to $\psi(x) = 5\phi_2$
EDIT: My answer should be $\psi(x) = 10\phi_2$,  I think
Is that correct? Or should I state the probability with which the wave function will collapse to that state:
$<\hat{O}> = \sum|c_n|^2\lambda_n$   where $|c_n|^2$ is the probability of the $n^{th}$ state.

REPLY [3 votes]: Well wavefunctions are technically rays, so what you wrote is acceptable, although usually one would normalize the wavefunction again. Once you have measured $\hat O$ and obtained $5$, you are past the point of asking about probabilities. Before measurement you have probabilities but it's like rolling dice. Once the dice is rolled and you got $6$, you don't ask what the probability is of having a $4$ because it is clearly zero.
Put another way, probability in quantum mechanics means that if you have $n$ identically prepared systems, and you perform the measurement on each one of them, then the fraction of times you get a result $x$ is given by some probability function $p(x)$ as $n\to \infty$. If you only perform the measurement once, or have already performed the measurement, then the probability is simply not defined.
Btw, all this wavefunction collapse business is just an idealization, because all our experiments point to the fact that everything is ruled by quantum mechanics, and unitarity is a central tenet of quantum mechanics. Wave function collapse is not a unitary process, decoherence and einselection is. Cheers.

REPLY [0 votes]: I think there is a little confusion here: the thing you wrote in the last line is the expectation value of a measurement on the state $\psi$: $\langle\psi|\hat O|\psi\rangle \equiv \langle \hat O \rangle$. However, the expectation value of finding your system in the state $|\phi_n\rangle$ after a measurement $\hat O$ is $\langle\phi_m|\hat O|\psi\rangle$, but I get a different result from yours:
\begin{align}
\langle\phi_m|\hat O|\psi\rangle &= \langle\phi_m|\sum_n |\phi_n\rangle\lambda_n \langle\phi_n|\sum_i c_i |\phi_i\rangle\\
 &= \sum_n\sum_i c_i\lambda_n\langle\phi_m|\phi_n\rangle\langle\phi_n|\phi_i\rangle \\
&= \sum_n\sum_i c_i\lambda_n\delta_{mn}\delta_{in}\\
&= c_m\lambda_m
\end{align}
Thus, the expectation value of finding your system in eigenstate 2 is 5*2 = 10.


TITLE: Find tangent of $2y=\ln{(x+1)}$ and calculate area between tangent,function and abscissa
QUESTION [1 upvotes]: We are given a curve $2y=\ln{(x+1)}$
1. Find equation of tangent of given curve parallel to line $4y-2e^{-2}x-3=0$
2. Calculate area between curve,tangent and abscissa.
My solution:
1.
Curve: $y=\frac{\ln{(x+1)}}{2}$
We have to find a tangent with slope $k=\frac{1}{2} e^{-2}$
$y'=\frac{1}{2} \frac{1}{x+1}$
We have $\frac{1}{2} \frac{1}{x+1}=\frac{1}{2} e^{-2}$, so $x=e^2-1$. For that $x$, $y=1$ and $y'=\frac{1}{2} e^{-2}$. Tangent has formula $g(x)=\frac{1}{2} e^{-2}(x-e^2+1)+1.$
2. I drew a picture, and i don't know how to calculate the area. I know there must be some combination of integrals, i was hoping if someone can draw a picture and give me solution. Thank you.
EDIT: Maybe I have wrong picture, i tried not to use WolframAlpha because we can't use it on exams. How do you even draw something like this?

REPLY [0 votes]: Tangent formula you gave appears to be correct (unless I've forgotten GCSE!).
Assuming the area is the same as JnxF's prediction, integral evaluates to $\frac{e^4-4e^2-1}{4e^2}$


TITLE: What is the need of homogeneous function?
QUESTION [0 upvotes]: I understand what an homogeneous function is, but I just can't seem to understand the purpose of having this concept of function. What does it even tell us?
I mean if $f(tx,ty) =t^n f(x,y)$ then what does it tell us? What is the use of this information?

REPLY [1 votes]: A useful result in the theory of partial differential is based on such homogeneous function is called Euler's theorem.

If $u=f(x,y)$ is homogeneous of degree $n$ then it always satisfy the partial differential equation of first order $x\frac{\partial u}{\partial x}+y\frac{\partial u}{\partial y}=nu$.