text:
\begin{document}

\ifjour
\ifams

\title{Cycle-based formulations in Distance Geometry}\thanks{This paper extends \cite{cycledgp-ctw20}. Parts of the introduction have been changed. We give a full proof of the main theorem rather than the sketch in \cite{cycledgp-ctw20}. Sect.~\ref{s:existing} and \ref{s:eulerian} are new. The computational results presented in Sect.~\ref{s:compres} are new.}
\author[L.~Liberti]{Leo Liberti}
\address{LIX CNRS Ecole Polytechnique, Institut Polytechnique de Paris, 91128 Palaiseau, France}
\email{liberti@lix.polytechnique.fr}
\author[G.~Iommazzo]{Gabriele Iommazzo}
\address{LIX Ecole Polytechnique, Palaiseau, France; and Dip.~Informatica, Universit\`a di Pisa, Italy}
\email{giommazz@lix.polytechnique.fr}
\author[C.~Lavor]{Carlile Lavor}
\address{IMECC, University of Campinas, Brazil}
\email{clavor@ime.unicamp.br}
\author[N.~Maculan]{Nelson Maculan}
\address{COPPE, Federal University of Rio de Janeiro (UFRJ), Brazil}
\email{maculan@cos.ufrj.br}
\subjclass[2010]{Primary 90C26; Secondary 51K05}
\keywords{Mathematical Programming, cycle basis, protein conformation}

\else

\title{Cycle-based formulations in Distance Geometry\thanks{This paper extends \cite{cycledgp-ctw20}. Parts of the introduction have been changed. We give a full proof of the main theorem rather than the sketch in \cite{cycledgp-ctw20}. Sect.~\ref{s:existing} and \ref{s:eulerian} are new. The computational results presented in Sect.~\ref{s:compres} are new.}}
\author{Leo Liberti \and Gabriele Iommazzo \and Carlile Lavor \and Nelson Maculan}
\institute{Leo Liberti and Gabriele Iommazzo \at LIX CNRS \'Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France \\ \email{\url{{liberti,giommazz}@lix.polytechnique.fr}}\and Carlile Lavor \at IMECC, University of Campinaz, Brazil \\ \email{\url{clavor@ime.unicamp.br}}\and Nelson Maculan \at COPPE, Universidade Federal do Rio de Janeiro, Brazil \\ \email{\url{maculan@cos.ufrj.br}}}
\date{Received: date / Accepted: date}
\fi

\else

\thispagestyle{empty}
\begin{center}

{\LARGE Cycle-based formulations in Distance Geometry}
\par \bigskip
{\sc  Leo Liberti${}^{\ref{inst1}}$, G.~Iommazzo${}^{\ref{inst1},\ref{inst4}}$, C.~Lavor${}^{\ref{inst2}}$, N.~Maculan${}^{\ref{inst3}}$}
\par \bigskip
\begin{minipage}{15cm}
\begin{flushleft}
{\small
  \begin{enumerate}
   \item {\it CNRS LIX, \'Ecole Polytechnique, F-91128 Palaiseau, France} \\ Email:\url{liberti@lix.polytechnique.fr}\label{inst1}
   \item {\it DI, Universit\`a di Pisa, Italy} \\ Email:\url{giommazz@lix.polytechnique.fr}\label{inst4}
   \item {\it IMECC, University of Campinas, Brazil} \\ Email:\url{clavor@ime.unicamp.br}\label{inst2}
   \item {\it COPPE, Federal Univ.~Rio de Janeiro (UFRJ), Brazil} \\ Email:\url{maculan@cos.ufrj.br}\label{inst3}
  \end{enumerate}
}
\end{flushleft}
\end{minipage}
\par \medskip \today
\end{center}
\par \bigskip

\fi

\ifjour
\maketitle
\fi
\begin{abstract}
The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension $K$, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures.
\end{abstract}

\section{Introduction}
\label{s:intro}
We consider the fundamental problem in Distance Geometry (DG):
\begin{quote}
\textsf{Distance Geometry Problem} (DGP). Given a positive integer $K$ and a simple undirected graph $G=(V,E)$ with an edge weight function $d:E\to\mathbb{R}_{\ge 0}$, establish whether there exists a {\it realization} $x:V\to\mathbb{R}^K$ of the vertices such that Eq.~\eqref{dgp} below is satisfied:
\begin{equation}
  \forall \{i,j\}\in E\qquad \|x_i-x_j\|=d_{ij},\label{dgp}
\end{equation}
where $x_i\in\mathbb{R}^K$ for each $i\in V$ and $d_{ij}$ is the weight on edge $\{i,j\}\in E$.
\end{quote}
Although the DGP is given above in the canonical decision form, we consider the corresponding search problem, where one has to actually find the realization $x$. The DGP is also known as the {\it graph realization problem} in geometric rigidity \cite{laurent97,berg,eren04}. It belongs to a more general class of metric completion and embedding problems \cite{kopperman,hoffman,schaeffer2}.

In its most general form, the DGP might be parametrized over any norm \cite{oneinfnorm-lncs}. In practice, the $\ell_2$ norm is the most usual choice \cite{dgp-sirev}, and will also be employed in this paper. The DGP with the $\ell_2$ norm is sometimes called the {\sc Euclidean DGP} (EDGP). For the EDGP, Eq.~\eqref{dgp} is often reformulated to:
\begin{equation}
  \forall \{i,j\}\in E\qquad \|x_i-x_j\|^2_2=d_{ij}^2,\label{edgp}
\end{equation}
which is a system of quadratic polynomial equations with no linear terms \cite[\S 2.4]{dgbook}.

The EDGP is motivated by many scientific and technological applications. The clock synchronization problem, for example, aims at establishing the absolute time of a set of clocks when only the time difference between subsets of clocks can be exchanged \cite{singer4}. The sensor network localization problem aims at finding the positions of moving wireless sensor on a 2D manifold given an estimation of some of the pairwise Euclidean distances \cite{eren04,eren06,snl}. The {\sc Molecular DGP} (MDGP) aims at finding the positions of atoms in a protein, given some of the pairwise Euclidean distances \cite{lln4,dmdgpejor,dgp-sirev,dgbook,bipbip,jcim}. The position of autonomous underwater vehicles cannot be determined via GPS (since the GPS signal does not reach under water), but must rely on distances estimated using sonars: a DGP can then be solved in order to localize the fleet \cite{bahr}. Applications of the DGP to data science are described in \cite{dgds}; see \cite{dg4wv} for an application to natural language processing. In general, the DGP is an inverse problem which occurs every time one can measure some of the pairwise distances in a set of entities, and needs to establish their position.

The DGP is weakly {\bf NP}-hard even when restricted to simple cycle graphs (by reduction from {\sc Partition}) and strongly {\bf NP}-hard even when restricted to integer edge weights in $\{1,2\}$ in general graphs (by reduction from {\sc 3sat}) \cite{saxe79}. It is in {\bf NP} if $K=1$ but not known to be in {\bf NP} if $K>1$ for general graphs \cite{dgpinnp}, which is an interesting open question \cite{openprobsDG}.

There are many approaches to solving the DGP. Generally speaking, application-specific solution algorithms exploit some of the graph structure, whenever it is induced by the application. For example, a condition often asked when reconstructing the positions of sensor networks is that the realization should be unique (as one would not know how to choose between multiple realizations), a condition called {\it global rigidity} \cite{connelly}. This condition can, at least generically, be ensured by a specific graph rigidity structure of the unweighted input graph. For protein structures, on the other hand, which are found in nature in several isomers, one is sometimes interested in finding all (incongruent) realizations of the given protein graph \cite{dmdgp,symmBPjbcb,liberti-gsi13}. Since such graphs are rigid, one can devise an algorithm (called Branch-and-Prune) which, following a given vertex order, branches on reflections of the position of the next vertex, which is computed using trilateration \cite{lln5,dgbook}. In absence of any information on the graph structure, however, one can resort to Mathematical Programming (MP) formulations and corresponding solvers \cite{mdgpsurvey,zoo,isco16}.

The MP formulation which is most often used reformulates Eq.~\eqref{edgp} to the minimization of the sum of squared error terms:
\begin{equation}
  \min_x \sum\limits_{\{i,j\}\in E} (\|x_i-x_j\|_2^2 - d_{ij}^2)^2.  \label{go}
\end{equation}
This formulation describes an unconstrained polynomial minimization problem. The polynomial in question has degree 4, is always nonnegative, and generally nonconvex and multimodal. The decision variables are represented by a $n\times K$ rectangular matrix $x$ such that $x_{ik}$ is the $k$-th component of the vector $x_i$, which gives the position in $\mathbb{R}^K$ of vertex $i\in V$. Each solution $x^\ast\in\mathbb{R}^{nK}$ having global minimum value equal to zero is a realization of the given graph. Solutions with small objective function value represent approximate solutions. Because of the nonconvexity of the formulation and the hardness of the problem, Eq.~\eqref{go} is not usually solved to guaranteed $\varepsilon$-optimality (e.g.~using a spatial Branch-and-Bound approach \cite{couenne}); rather, heuristic approaches, such as MultiStart (MS) \cite{comparison2,lln1}, Variable Neighbourhood Search (VNS) \cite{dvnsjogo}, or relaxation-based heuristics \cite{isco16,barvinok_orl} may be used.

As far as we know, all existing MP formulations for the EDGP are based on the incidence of edges and vertices. In this paper we discuss a new MP formulation for the EDGP based on the incidence of cycles and edges instead, a relaxation based on Eulerian cycles, and a computational comparison with Eq.~\eqref{go}.

\section{Some existing MP formulations}
\label{s:existing}
In this short section we give a minimal list of typical variants of Eq.~\eqref{go} in order to motivate the claim that the cycle-based formulation of the DGP discussed in this paper is new. Of course, only a complete enumeration of DGP formulations in the literature could substantiate this claim. But even this short list shows that the typical modelling approach for the DGP is direct: namely, decision variables encode the realization of each vertex as a vector in $\mathbb{R}^K$. Many more formulations of the DGP and its variants, all corresponding to this criterion, are given in \cite{lln1,mdgpsurvey,zoo}.

The closest variant of Eq.~\eqref{go} simply adds a constraint ensuring that the centroid of all of the points in the realization is at the origin. This removes the degrees of freedom given by translations:
\begin{equation}
  \left.\begin{array}{rl}
    \min\limits_x & \sum\limits_{\{i,j\}\in E} (\|x_i-x_j\|_2^2 - d_{ij}^2)^2 \\
    \forall k\le K & \sum\limits_{i\in V} x_{ik} = 0.
  \end{array}\right\} \label{go1}
\end{equation}
This formulation describes a linearly constrained polynomial minimization problem. Like Eq.~\eqref{go}, the polynomial in Eq.~\eqref{go1} has degree 4, is always nonnegative, and is generally nonconvex and multimodal.

Another small variant of Eq.~\eqref{go1} is achieved by adding range bounds to the the realization variables $x$; generally valid (but slack) bound values can be set to $\pm\frac{1}{2}\sum_{\{u,v\}\in E} d_{uv}$. This corresponds to the worst case of a single path being arranged in a straight line with unknown orientation.

Another possible formulation, derived again from Eq.~\eqref{go}, is obtained by replacing the squared error with absolute value errors (whose positive and negative parts are encoded by $s^+,s^-$). This yields the following formulation:
\begin{equation}
  \left.\begin{array}{rl}
    \min\limits_{s,x} & \sum\limits_{\{i,j\}\in E} (s^+_{ij} + s^-_{ij}) \\
    \forall \{i,j\}\in E & \|x_i-x_j\|_2^2 = d_{ij}^2 + s^+_{ij} - s^-_{ij}\\
    \forall \{i,j\}\in E & s^+_{ij}, s^-_{ij} \ge 0.
  \end{array}\right\}
  \label{minabs}
\end{equation}
Note that, again, each solution $s^\ast,x^\ast$ with zero optimal objective value makes $x^\ast$ an encoding of a realization of the given graph. Thus, global optima are preserved by this reformulation, while local optimal may differ.

Yet another reformulation derived from replacing squared errors with absolute values consists in observing that the ``plus'' and ``minus'' parts of each absolute value term correspond to a convex and concave function. This yields a formulation called {\it push-and-pull}, since the objective pulls adjacent vertices apart, while the constraint push them back together:
\begin{equation}
  \left.\begin{array}{rrcl}
    \max\limits_x & \sum\limits_{\{i,j\}\in E} \|x_i-x_j\|_2^2 && \\
    \forall \{i,j\}\in E & \|x_i-x_j\|_2^2 &\le& d_{ij}^2.
  \end{array}\right\}
  \label{pushpull}
\end{equation}
Eq.~\eqref{pushpull} is a Quadratically Constrained Quadratic Program with concave objective and convex constraints. It was used within a Multiplicative Weights Update algorithm for the DGP in \cite{zoo,mwu}, as well as a basis for Semidefinite Programming and Diagonally Dominant Programming relaxations \cite{isco16,barvinok_orl}. It can be shown that all constraints are active at global optima, which therefore correspond to realizations of the given graph \cite{mwu}.

\section{A new formulation based on cycles}
\label{newform}
In this section we propose a new formulation for the EDGP, based on the fact that the quantities $x_{ik}-x_{jk}$ sum up to zero over all edges of any cycle in the given graph for each dimensional index $k\le K$. This idea was used in \cite{saxe79} for proving weak {\bf NP}-hardness of the DGP on cycle graphs. For a subgraph $H$ of a graph $G=(V,E)$, we use $V(H)$ and $E(H)$ to denote vertex and edge set of $H$ explicitly; given a set $F$ of edges we use $V(F)$ to denote the set of incident vertices. Let $m=|E|$ and $n=|V|$. For a mapping $x:V\to\mathbb{R}^K$ we denote by $x[U]$ the restriction of $x$ to a subset $U\subseteq V$.
\begin{lemma}
  \label{lemcycle}
  Given an integer $K>0$, a simple undirected weighted graph $G=(V,E,d)$ and a mapping $x:V\to\mathbb{R}^K$, then for each cycle $C$ in $G$, each orientation of the edges in $C$ given by a closed trail $W(C)$ in the cycle, and each $k\le K$ we have:
  \begin{equation}
    \sum\limits_{(i,j)\in W(C)} (x_{ik}-x_{jk})=0. \label{sumcycles}
  \end{equation}
\end{lemma}
\begin{proof}
We renumber the vertices in $V(C)$ to $1,2,\ldots,\gamma=|V(C)|$ following the walk order in $W(C)$. Then Eq.~\eqref{sumcycles} can be explicitly written as:
  \begin{eqnarray*}
   (x_{1k}-x_{2k}) + (x_{2k}-x_{3k}) + \cdots + (x_{\gamma k}-x_{1k}) &=& \\
  =  x_{1k} - (x_{2k}-x_{2k}) - \cdots - (x_{\gamma k}-x_{\gamma k}) - x_{1k} &=& 0,
  \end{eqnarray*}
  as claimed. \qed
\end{proof}

We introduce new decision variables $y_{ijk}$ replacing the terms $x_{ik}-x_{jk}$ for each $\{i,j\}\in E$ and $k\le K$. Eq.~\eqref{edgp} then becomes:
\begin{equation}
  \forall\{i,j\}\in E\qquad \sum\limits_{k\le K} y_{ijk}^2 = d_{ij}^2. \label{newsys}
\end{equation}
We remark that for the DGP with other norms this constraint changes. For the $\ell_1$ or $\ell_\infty$ norms, for example, we would have:
\begin{equation}
  \forall\{i,j\}\in E\quad \sum\limits_{k\le K} |y_{ijk}| = d_{ij}\quad\mbox{ or }\quad\max\limits_{k\le K} |y_{ijk}| = d_{ij}. \label{linnorms}
\end{equation}

Next, we adjoin the constraints on cycles:
\begin{equation}
  \forall k\le K, C\subset G\quad \bigg(C\mbox{ is a cycle}\Rightarrow \sum\limits_{\{i,j\}\in E(C)} y_{ijk} = 0\bigg). \label{newcon}
\end{equation}

We also note that the feasible value of a $y_{ijk}$ variable is the (oriented) length of the segment representing the edge $\{i,j\}$ projected on the $k$-th coordinate. We can therefore infer bounds for $y$ as follows:
\begin{equation}
\forall k\le K, \{i,j\}\in E \quad -d_{ij} \le y_{ijk}\le d_{ij}.\label{ybnd}
\end{equation}
Although Eq.~\eqref{ybnd} are not necessary to solve the cycle formulation, they may improve performance of spatial Branch-and-Bound (sBB) algorithms \cite{tawarmalani1,couenne} as well as of various ``matheuristics'' \cite{recipeconf}, as well as allow an exact linearization of variable products, should a $y$ variable occur in a product with a binary variable in some DGP variant.

We now state our main result, i.e.~that Eq.~\eqref{newsys} and \eqref{newcon} are a valid MP formulation for the EDGP.
\begin{theorem}\label{mainthm}
There exists a vector $y^\ast\in\mathbb{R}^{Km}$ which satisfies Eq.~\eqref{newsys} and \eqref{newcon}, parametrized on $K,G$, if and only if $(K,G)$ is a YES instance of the EDGP.
\end{theorem}

The proof argues by recursion on a graph decomposition of $G$ that a certain linear system related to the cycles of $G$ (see Eq.~\eqref{xysys} below) has a solution if and only if the given DGP instance is YES. We shall construct the proof by steps. The first step defines the graph decomposition.

Given a graph $G=(V,E)$ and a subset $U\subset V$, the subgraph $G[U]$ {\it induced} by $U$ is the graph $(U,\{\{u,v\}\in E\;|\;u,v\in U\})$. With a slight abuse of notation we denote the vertices of a graph $G'$ by $V(G')$ and its edges by $E(G')$. We let $\gamma(G)$ be the number of connected components of $G$. A vertex $v$ of $G$ with the property that $\gamma(G[V\smallsetminus\{v\}])>\gamma(G)$ is called a {\it cut vertex}. A graph $G$ is {\it biconnected} if there is a simple cycle in $G$ incident to any pair of distinct vertices of $G$.

\begin{lemma}
$G=(V,E)$ is biconnected if and only if it is connected and has no cut vertices.\label{biconncutv}
\end{lemma}
\begin{proof}
Suppose $G$ is biconnected with a cut vertex $v$: then the removal of $v$ from $G$ yields two separate connected components $G_1,G_2$. Let $u_1\in V(G_1)$ and $u_2\in V(G_2)$. Since $u_1,u_2\in V$ and $G$ is biconnected, there is a simple cycle in $G$ incident to $u_1,u_2$, consisting of two vertex-disjoint simple paths $p_1$ and $p_2$ from $u_1$ to $u_2$. Since the removal of $v$ can break at most one of these paths (by vertex disjointness), the other path shows that $G_1,G_2$ are not disconnected, against the assumption. So $G$ cannot have cut vertices. Conversely, if $G$ is connected and has a cut vertex $v$, then any pair of paths from $u_1$ to $u_2$ must necessarily pass through $v$, which means that they are not vertex disjoint, which implies that there is no cycle between $u_1$ and $u_2$ in $G$, which in turn implies that $G$ is not biconnected.  \qed
\end{proof}

We now define a graph decomposition based on removal of a single cut vertex.
\begin{definition}
\label{1dec}
A {\it $1$-decomposition} of a graph $G=(V,E)$ is a set of subgraphs $G_1,\ldots,G_r$ (where $r\in\mathbb{N}$ with $r\ge 1$) of $G$ such that:
\begin{enumerate}[(a)]
\item $G_i$ is either biconnected or a tree for all $i\le r$;\label{1da}
\item $\bigcup_{i\le r}E(G_i)=E$;\label{1db}
\item for any $i<j\le r$ the intersection $V(G_i)\cap V(G_j)$ either has zero cardinality or it consists of a single cut vertex of $G$. \label{1dc}
\end{enumerate}
A $1$-decomposition of $G$ is {\it nontrivial} if $r>1$. A graph $G$ is $1$-decomposable if it has a nontrivial $1$-decomposition.
\end{definition}

\begin{lemma}
A connected graph $G=(V,E)$ is $1$-decomposable if and only if it has a cut vertex.\label{lem01}
\end{lemma}
\begin{proof}
Suppose $\mathcal{C}=\{C_1,\ldots,C_t\}$ is a nontrivial $1$-decomposition of $G$. By Defn.~\ref{1dec} and since $G$ is connected, it follows that $G$ must have at least one cut vertex and as many as $|\mathcal{C}| - 1$. Conversely, supposing that $G$ has a cut vertex would yield a nontrivial $1$-decomposition by Defn.~\ref{1dec}, i.e.~$G$ is $1$-decomposable. \qed
\end{proof}

\begin{corollary}
No simple graph consisting of a single cycle is $1$-decomposable.
\label{lem01a}
\end{corollary}
\begin{proof}
Since a cycle is biconnected, by Lemma \ref{biconncutv} it cannot have a cut vertex, hence its only possible $1$-decomposition is trivial. \qed
\end{proof}

\begin{corollary}
Let $G$ be $1$-decomposable, with decomposition $\mathcal{G}=\{G_1,\ldots,G_r\}$, and $C$ be a cycle in $G$. Then there is an index $i\le r$ s.t.~$C$ is a subgraph of $G_i$.\label{lem01a2}
\end{corollary}
\begin{proof}
Consider there were two subgraphs $G_i,G_j$ in $\mathcal{G}$ both incident to the edges of $C$. Then there is a nontrivial path $p$ in $C$, with at least two edges, joining a vertex $u$ in $G_i$ to a vertex $v$ in $G_j$. Therefore there must be a cut vertex of $G$ on $p$, which implies that there is a cut vertex in $C$, which is impossible by Cor.~\ref{lem01a}. \qed
\end{proof}

\begin{corollary}
\label{lem01c}
No biconnected graph $G$ is $1$-decomposable.
\end{corollary}
\begin{proof}
By Lemma \ref{biconncutv}, if $G$ is biconnected it cannot have a cut vertex, therefore any $1$-decomposition must necessarily be trivial. \qed
\end{proof}

\begin{proposition}
Any simple graph $G=(V,E)$ has a $1$-decomposition consisting of biconnected subgraphs and tree subgraphs. \label{lem01d}
\end{proposition}
\begin{proof}
We prove this result by induction on the number $\beta$ of biconnected subgraphs in a $1$-decomposition $\mathcal{C}=\{G_1,\dots,G_r\}$ of $G$ for some $r\in\mathbb{N}$. We first deal with the base case, where $\beta=0$. We claim that $G$ must be a tree: supposing $G$ has a cycle $G'$, by Cor.~\ref{lem01a} and part (\ref{1dc}) of Defn.~\ref{1dec}, $G'$ must be one of the $G_1,\ldots,G_r$. But then $\beta=1$ against the assumption. Therefore, the trivial $1$-decomposition $\mathcal{C}=\{G\}$ is a valid $1$-decomposition of $G$. We now tackle the induction step. Consider the largest biconnected subgraph $B$ of $G$: then $\tilde{G}=G[V\smallsetminus V(B)]$ has one fewer biconnected components than $G$, so, by induction, $\tilde{G}$ has a $1$-decomposition $\mathcal{D}'=\{G'_1,\ldots,G'_{t-1}\}$ for some $t\in\mathbb{N}$ with $t>1$. We prove that $\mathcal{D}=\mathcal{D}'\cup\{B\}$ is a valid $1$-decomposition of $G$. Condition (\ref{1da}) is verified since $\mathcal{D}'$ is a valid 1-decomposition by induction, and B is biconnected; condition (\ref{1db}) is verified since the union of the graph in $\mathcal{D}$ is $\mathcal{G}$ by construction; for condition (\ref{1dc}), suppose there is $i<t$ s.t.~$|V(G_i) \cap V(B)|\ge 2$: this means there are two distinct vertices $u,v$ in both $V(G_i)$ and $V(B)$. Since $G_i$ is connected, there must be a path $p$ from $u$ to $v$ in $G_i$, hence $G[B\cup V(p)]$ is a biconnected graph larger than $B$. But $B$ was assumed to be largest, so this is not possible, and (\ref{1dc}) holds, which concludes the proof. \qed
\end{proof}

The second step proves the easier ($\Leftarrow$) direction of Thm.~\ref{mainthm}.
\begin{proposition}
  \label{rightdir}
For any YES instance $(K,G)$ of the EDGP there is a vector $y^\ast\in\mathbb{R}^{Km}$ which satisfies Eq.~\eqref{newsys} and \eqref{newcon}.
\end{proposition}
\begin{proof}
Assume that $(K,G)$ is a YES instance of the EDGP. Then $G$ has a realization $x^\ast\in\mathbb{R}^{nK}$ in $\mathbb{R}^K$. We define $y_{ijk}^\ast=x^\ast_{ik}-x^\ast_{jk}$ for all $\{i,j\}\in E$ and $k\le K$. Since $x^\ast$ is a realization of $G$, by definition it satisfies Eq.~\eqref{edgp}, and, by substitution, Eq.~\eqref{newsys}. Moreover, any realization of $G$ satisfies Eq.~\eqref{sumcycles} over each cycle by Lemma \ref{lemcycle}. Hence, by replacement, it also satisfies Eq.~\eqref{newcon}. \qed
\end{proof}

In the third step, we lay the groundwork towards the more difficult ($\Rightarrow$) direction of Thm.~\ref{mainthm}. We proceed by contradiction: we assume that $(K,G)$ is a NO instance of the EDGP, and suppose that Eq.~\eqref{newsys} and \eqref{newcon} have a non-empty feasible set $Y$. For every $y\in Y$ we consider the $K$ linear systems
\begin{equation}
\forall \{i,j\}\in E\quad x_{ik}-x_{jk}=y_{ijk}, \label{xysys}
\end{equation}
for each $k\le K$, each with $n$ variables and $m$ equations. We square both sides then sum over $k\le K$ to obtain
\begin{equation}
  \forall \{i,j\}\in E\quad \sum_{k\le K} (x_{ik}-x_{jk})^2= \sum_{k\le K} y_{ijk}^2.\label{xysys1a}
\end{equation}
By Eq.~\eqref{newsys} we have
\begin{equation}
  \sum_{k\le K} y_{ijk}^2 = d_{ij}^2,\label{xysys1b}
\end{equation}
whence follows Eq.~\eqref{edgp}, contradicting the assumption that the EDGP is NO. So we need only show that there is a solution $x$ to Eq.~\eqref{xysys} for any given $y\in Y$. To this effect, we shall exploit the $1$-decomposition of $G$ into biconnected graphs and trees derived in Prop.~\ref{lem01d}. First, though, we have to show that Eq.~\eqref{xysys} has a solution if $Y\not=\varnothing$ in the ``base cases'' of the $1$-decomposition, namely trees and biconnected graphs.

\begin{lemma}
  Let $G=(V,E)$ be a tree, and $Y\not=\varnothing$ satisfying Eq.~\eqref{newsys} and \eqref{newcon}. Then Eq.~\eqref{xysys} has a solution for every $k\le K$.
  \label{tree}
\end{lemma}
\begin{proof}
  Let $M^k$ be the matrix of each system Eq.~\eqref{xysys}, for $k\le K$; we aim at proving that $M^k$ and $(M^k,y^{k})$ have the same rank, where $y^{k}=(y_{uvk}\;|\;\{u,v\}\in E)$, and that this rank is full. We proceed by induction on the size $|E|$ of the tree. The base case, where $|E|=1$ and $G$ consists of a single edge $\{u,v\}$, yields $M^k=(1,-1)$ with rank 1 for each $k\le K$. By inspection, $(M^k,y_{uvk})$ also has rank 1 for any $y_{uvk}$. Consider a tree $G'$ with one fewer edge (say, $\{u,v\}$) than $G$, such that $V\smallsetminus V(G')=\{v\}$. Let the corresponding system Eq.~\eqref{xysys} $\tilde{M}^k=\tilde{y}^{k}$ satisfy $\mathsf{rank}(\tilde{M}^k)=\mathsf{rank}(\tilde{M}^k,\tilde{y}^{k})$, for all $k\le K$. Then the shape of $M^k$ is:
  \begin{equation*}
    M^k = \left(\begin{array}{cc} \tilde{M}^k & 0 \\  e_u & -1\end{array}\right),
  \end{equation*}
  where $e_u=(0,\ldots,0,1_u,0,\ldots,0)$. This shows that $\mathsf{rank}(M^k)=\mathsf{rank}(\tilde{M}^k)+1$, that this rank is full, and hence also that $\mathsf{rank}(M^k)=\mathsf{rank}((M^k,y^{k}))$, as claimed. \qed
\end{proof}

\begin{lemma}
  Let $G=(V,E)$ be biconnected, and $Y\not=\varnothing$ satisfying Eq.~\eqref{newsys} and \eqref{newcon}. Then Eq.~\eqref{xysys} has a solution for every $k\le K$. \label{biconn}
\end{lemma}
\begin{proof}
We proceed by induction on the simple cycles of $G$. For the base case, we consider $G$ to be a graph consisting of a single cycle, with corresponding $y$ satisfying Eq.~\eqref{newsys} and \eqref{newcon}. Since $G$ is a cycle, it has the same number of vertices and edges, say $q$. This implies that, for any fixed $k\le K$, Eq.~\eqref{xysys} is a linear system $M^kx=y^k$ (where $y^k=(y_{uvk}\;|\;\{u,v\}\in E)$ with a $q\times q$ matrix:
\begin{equation}
M^k=\left(\begin{array}{ccccc}
  1 & -1 &    & & \\
    &  1 & -1 & & \\
    &    &  1 &\ddots & \\
    &    &    &\ddots & -1 \\
 -1 &    &    & & 1
\end{array}\right).
\label{eqM}
\end{equation}
By Eq.~\eqref{sumcycles} and by inspection of Eq.~\eqref{eqM} it is clear that $\mathsf{rank}(M^k)=q-1$: then Eq.~\eqref{newcon} ensures that $\mathsf{rank}((M^k,y^k))=\mathsf{rank}(M^k)$, and therefore that Eq.~\eqref{xysys} has a solution.

We now tackle the induction step. The incidence vectors in $E$ of the cycles of any graph are a vector space of dimension $m-n+1$ over the finite field $\mathbb{F}_2=\{0,1\}$ \cite{seshu}. We consider a fundamental cycle basis $\mathcal{B}$ of $G$ (see Sect.~\ref{s:cycbas}). We assume that (a) $G'$ is a union of fundamental cycles in $\mathcal{B}'\subsetneq\mathcal{B}$, for which Eq.~\eqref{xysys} has a solution $x'$ by the induction hypothesis, and (b) that $C$ is another fundamental cycle in $\mathcal{B}\smallsetminus\mathcal{B}'$, with a solution $x^C$ of Eq.~\eqref{xysys} which exists by the base case. We aim at proving that Eq.~\eqref{xysys} has a solution for $G'\cup C$. Since $G$ is biconnected, the induction can proceed by ear decomposition \cite{eardecomp}, which means that $G'$ is also biconnected, and that $C$ is such that $E(G')\cap E(C)=F$ is a non-empty path in $G'$.

By Eq.~\eqref{newcon} applied to $C$, we have
\begin{equation}
  \forall k\le K \quad \sum\limits_{\{i,j\}\in C} y_{ijk} = 0.\label{thm1eq2}
\end{equation}
Since $x'$ satisfies Eq.~\eqref{xysys} by the induction hypothesis,
\begin{equation}
  \forall k\le K, \{i,j\}\in F \quad x'_{ik}-x'_{jk} = y_{ijk}.\label{thm1eq3}
\end{equation}
We replace Eq.~\eqref{thm1eq3} in Eq.~\eqref{thm1eq2}, obtaining
\begin{equation}
  \forall k\le K \quad \sum\limits_{\{i,j\}\in F} (x'_{ik}-x'_{jk}) = -\sum\limits_{\{i,j\}\in E(C)\smallsetminus F} y_{ijk}.\label{thm1eq4}
\end{equation}
Moreover, $x^C$ also satisfies Eq.~\eqref{xysys} over $C$, hence we can replace the right hand side of Eq.~\eqref{thm1eq4} with the corresponding terms in $x^C_{ik}-x^C_{jk}$ to get:
\begin{equation}
  \forall k\le K \quad \sum\limits_{\{i,j\}\in F} (x'_{ik}-x'_{jk}) + \sum\limits_{\{i,j\}\in E(C)\smallsetminus F} (x^C_{ik}-x^C_{jk}) = 0.\label{thm1eq5}
\end{equation}

We now fix $x'$, and aim at modifying $x^C$ so that: (a) $x^C$ matches $x'$ on $V(F)$, (b) the modified $x^C$ is still a solution of Eq.~\eqref{xysys} on $C$. We set $x^C_{ik}$ to $x'_{ik}$ for each $i\in V(F)$, and consider the resulting linear system Eq.~\eqref{xysys} given by $M^k$, as in Eq.~\eqref{eqM}, for each $k\le K$, where we assume without loss of generality that $V(F)=\{1,\ldots,r\}$ and $V(C)=\{r+1,\ldots,s\}$:
{\small
\begin{equation}
  \left.\begin{array}{rrrrrrcll}
    x'_{1k} &-\ x'_{2k} & & & & &= & y_{12k} & (1) \\
    & x'_{2k} & -\ x'_{3k} & & & &= & y_{23k}& (2) \\
    &\ddots&\ddots & & & &\vdots & \vdots & \vdots \\
  &  & x'_{rk} &-\ x^C_{r+1,k} & & & = & y_{r,r+1,k} & (r)\\
    & & & x^C_{r+1,k} &-\ x^C_{r+2,k} & & = & y_{r+1,r+2,k} & (r\!\!+\!\!1) \\
    & & & \ddots & \ddots & &\vdots &\vdots & \vdots \\
    & & & & x^C_{s-1,k} & -\ x^C_{sk} & = & y_{s-1,s,k} & (s\!\!-\!\!1) \\
   -\ x'_{1k} & & & & & x^C_{sk} & = & y_{1sk}. & (s) \\
  \end{array}\right\}\label{x'xC}
\end{equation}
}
The equations from ($1$) to ($r\!-\!1$) in Eq.~\eqref{x'xC} are satisfied by the induction hypothesis since they only depend on $x'$, so we can remove them from the system and assume $x'$ to be constant. We are left with:
\begin{equation}
  \left.\begin{array}{rrrcll}
  -\ x^C_{r+1,k} & & & = & y_{r,r+1,k}-x'_{rk} & (r)\\
    x^C_{r+1,k} &-\ x^C_{r+2,k} & & = & y_{r+1,r+2,k} & (r\!\!+\!\!1) \\
    \ddots & \ddots & &\vdots &\vdots & \vdots \\
    & x^C_{s-1,k} & -\ x^C_{sk} & = & y_{s-1,s,k} & (s\!\!-\!\!1) \\
    & & x^C_{sk} & = & y_{1sk}+x'_{1k}. & (s) \\
  \end{array}\right\}\label{x'xC1}
\end{equation}
Summing up the left hand sides of Eq.~\eqref{x'xC1}, we obtain:
\begin{eqnarray*}
  && -x^C_{r+1,k} + (x^C_{r+1,k}-x^C_{r+2,k}) + \cdots + (x^C_{s-1,k} - x^C_{sk}) + x^C_{sk} \\
  &=& (-x^C_{r+1,k} + x^C_{r+1,k}) +  \cdots + (-x^C_{sk} + x^C_{sk}) = 0
\end{eqnarray*}
for all $k\le K$, so the $(s-r+1)\times (s-r+1)$ matrix $\bar{M}^k$ of the $k$-th linear system Eq.~\eqref{x'xC1} has rank $\le s-r$. On the other hand, eliminating the first or last row makes it clear by inspection that the rest of the rows are linearly independent; therefore the rank of $\bar{M}^k$ is exactly $s-r$. Summing up the components of the right hand side vector $\bar{y}^k$ of Eq.~\eqref{x'xC1}, we obtain:
\begin{eqnarray*}
  \chi &=& - x'_{rk} + y_{r,r+1,k} + y_{r+1,r+2,k} + \cdots + y_{s-1,s,k} + y_{1sk} + x'_{1k} \\
  &=& (x'_{1k} - x'_{rk}) + \sum_{\{i,j\}\in E(C)\smallsetminus F} y_{ijk}.
\end{eqnarray*}
We remark that
\begin{eqnarray*}
  x'_{1k}-x'_{rk} &=& (x'_{1k}-x'_{2k})+(x'_{2k}-x'_{3k}) + \cdots + (x'_{r-1,k}+x'_{rk}) \\
  &=& \sum_{\{i,j\}\in F} (x'_{ik}-x'_{jk}) = \sum_{\{i,j\}\in F} y_{ijk}
\end{eqnarray*}
since $x'$ satisfies Eq.~\eqref{xysys} by the induction hypothesis. Therefore
\begin{equation*}
\chi = \sum_{\{i,j\}\in F} y_{ijk} + \sum_{\{i,j\}\in E(C)\smallsetminus F} y_{ijk} = \sum_{\{i,j\}\in E(C)} y_{ijk},
\end{equation*}
whence $\chi=0$ by Eq.~\eqref{thm1eq2}. This implies that $\mathsf{rank}((\bar{M}^k,\bar{y}^k))=\mathsf{rank}(\bar{M}^k)=s-r$. Therefore, Eq.~\eqref{x'xC1} has a solution, which yields the modified $x^C$ with properties (a) and (b) given above. This concludes the induction step and the proof. \qed
\end{proof}

We can finally give the proof of Thm.~\ref{mainthm}.

\noindent {\it Proof of Thm.~\ref{mainthm}.} The ($\Leftarrow$) part follows by Prop.~\ref{rightdir}. For the ($\Rightarrow$) part, we exploit a $1$-decomposition of $G$ into trees and biconnected subgraphs, derive solutions to Eq.~\eqref{xysys} for each subgraph, and show that the solutions can be easily combined to yield a solution to Eq.~\eqref{xysys} for the whole graph $G$.

We assume without loss of generality that $G$ is connected (otherwise each connected component can be treated separately), and consider  a $1$-decomposition $\mathcal{D}=\{G_1,\ldots,G_r\}$ of $G$. By Lemmata \ref{tree} and \ref{biconn}, there exist solutions $x^1,\dots x^r$ to Eq.~\eqref{xysys} applied to $G_1,\ldots,G_r$ respectively. Consider the graph
\[\mathscr{D}=(\mathcal{D},\; \{\{i,j\}\;|\; 1\le i\not=j\le r\land |V(G_i)\cap V(G_j)|=1\}).\]
By Cor.~\ref{lem01a2}, $\mathscr{D}$ is a tree: otherwise, a cycle in $\mathcal{D}$ would be a contraction of a cycle in $G$ not included in a single $G_i$, against Cor.~\ref{lem01a2}. This allows us to reorder $\mathcal{D}$ so that, for each $j>1$, there is a unique $i<i$ such that $\{i,j\}\in E(\mathscr{D})$.

We remark that, for each $i\le r$, $x^i$ is a realization of $G_i$ in $\mathbb{R}^K$ by Eq.~\eqref{xysys}-\eqref{xysys1b}. More precisely, $x^i$ is a $|V(G_i)|\times K$ matrix $x^i=(x^i_{\ell k})$ so that $x^i_\ell=(x^i_{\ell 1},\ldots,x^i_{\ell K})$ is the position of vertex $\ell\in V(G_i)$ in $\mathbb{R}^K$. Note that the realizations $x^1,\ldots,x^r$ can be modified by translations without changing the values of $y$ (by inspection of Eq.~\eqref{xysys}).

We now construct a solution $\bar{x}$ of Eq.~\eqref{xysys} for $G$ by induction on $\mathcal{D}$ ordered as described above. For the base case $i=1$, we fix $x^1$ in any way (e.g.~by taking the centroid of the rows of $x^1$ to be the origin), and initialize the first $|V(G_1)|$ rows of $\bar{x}$ with those of $x^1$. For any $i>1$, we identify the unique predecessor $j$ of $i$ in the order on $\mathcal{D}$. The induction hypothesis ensures the existence of a solution $\bar{x}$ of the union of $G_1,\ldots,G_j$. Consider the cut vertex $v$ in $V(G_j)\cap V(G_i)$ guaranteed by definition of the order on $\mathcal{D}$, and let $\bar{x}_v\in\mathbb{R}^K$ be its position. Then the translation $\tilde{x}^i=x^i-\mathbf{1}\transpose{(x^i_{v}-\bar{x}_v)}$ yields another valid solution of Eq.~\eqref{xysys} applied to $G^i$ by translation invariance, and this solution is such that $\tilde{x}^i_{v} = \bar{x}_v$. Therefore, using the rows of $\tilde{x}^i$, $\bar{x}$ can be extended to a solution of Eq.~\eqref{xysys} applied to the union of $G_1,\ldots,G_j$ and $G^i$, as claimed. \qed \vspace*{0.9em}

Thm.~\ref{mainthm} can also be interpreted as a polynomial reduction of the EDGP to the problem of finding a solution of Eq.~\eqref{newsys} and \eqref{newcon}.
\begin{corollary}
  Deciding feasibility of Eq.~\eqref{newsys} and \eqref{newcon} is $\mathbf{NP}$-hard.
  \label{nphard}
\end{corollary}
\begin{proof}
  By reduction from EDGP using Thm.~\ref{mainthm}. \qed
\end{proof}

A remarkable consequence of Thm.~\ref{mainthm} is that it allows a decomposition of the computation of the realization $x$ into two stages: first, solve Eq.~\eqref{newsys}-\eqref{newcon} to find a feasible $y^\ast$; then solve
\begin{equation}
  \forall k\le K, \{i,j\}\in E\quad x_{ik}-x_{jk} = y_{ijk}^\ast \label{xysys2}
\end{equation}
to find a realization $x^\ast$. We note that Eq.~\eqref{xysys2} is just a restatement of Eq.~\eqref{xysys} universally quantified over $k$.
\begin{corollary}
  Given a solution $y^\ast$ solving Eq.~\eqref{newsys} and Eq.~\eqref{newcon}, any solution $x^\ast$ of Eq.~\eqref{xysys2} is a valid realization of the EDGP instance $(K,G)$.
  \label{2stage}
\end{corollary}
\begin{proof}
  The feasibility of Eq.~\eqref{xysys2} with the right hand side replaced by a solution $y^\ast$ of Eq.~\eqref{newsys} and \eqref{newcon} follows directly from Thm.~\ref{mainthm}, since if such a $y^\ast$ exists then the EDGP is feasible. \qed
\end{proof}
The first stage is $\mathbf{NP}$-hard by Cor.~\ref{nphard}, while the second stage is tractable, since solving linear systems can be done in polynomial time.

\begin{remark}
  \label{xysysfeas}
  Note that Eq.~\eqref{xysys2} has $Km$ equations, but its rank may be lower, since there are only $Kn$ variables: in particular, Eq.~\eqref{xysys2} may be an overdetermined linear system. The feasibility of this system is guaranteed by Cor.~\ref{2stage}; in particular, the steps of the proof of Thm.~\ref{mainthm} imply that Eq.~\eqref{xysys2} loses rank w.r.t.~$Km$ according to the incidence of the edges in the cycles of $G$. In other words, any solution $y'$ to Eq.~\eqref{newcon} provides a right hand side to Eq.~\eqref{xysys2} that makes the system feasible.
\end{remark}

The issue with Thm.~\eqref{mainthm} is that it relies on the exponentially large family of constraints Eq.~\eqref{newcon}. While this is sometimes addressed by algorithmic techniques such as row generation, we shall see in the following that it suffices to consider a polynomial set of cycles (which, moreover, can be found in polynomial time) in the quantifier of Eq.~\eqref{newcon}.

\section{The cycle vector space and its bases}
\label{s:cycbas}
We recall that incidence vectors of cycles (in a Euclidean space having $|E|$ dimensions) form a vector space over a field $\mathbb{F}$, which means that every cycle can be expressed as a weighted sum of cycles in a basis. In this interpretation, a {\it cycle} in $G$ is simply a subgraph of $G$ where each vertex has even degree: we denote their set by $\mathcal{C}$. This means that Eq.~\eqref{newcon} is actually quantified over a subset of $\mathcal{C}$, namely the simple connected cycles. Every basis has cardinality $m-n+a$, where $a$ is the number of connected components of $G$. If $G$ is connected, cycle bases have cardinality $m-n+1$ \cite{seshu}.

Our interest in introducing cycle bases is that we would like to quantify Eq.~\eqref{newcon} polynomially rather than exponentially in the size of $G$. Our goal is to replace ``$C$ is any simple connected cycle in $\mathcal{C}$'' by ``$C$ is a cycle in a cycle basis of $G$''. In order to show that this limited quantification is enough to imply every constraint in Eq.~\eqref{newcon}, we have to show that, for each simple connected cycle $C\in\mathcal{C}$, the corresponding constraint in Eq.~\eqref{newcon} can be obtained as a weighted sum of constraints corresponding to the basis elements.

Another feature of Eq.~\eqref{newcon} to keep in mind is that edges are implicitly given a direction: for each cycle, the term for the {\it undirected} edge $\{i,j\}$ in Eq.~\eqref{newcon} is $(x_{ik}-x_{jk})$. Note that while $\{i,j\}$ is exactly the same vertex set as $\{j,i\}$, the corresponding term is either positive or not, depending on the direction $(i,j)$ or $(j,i)$. We deal with this issue by arbitrarily directing the edges in $E$ to obtain a set $A$ of arcs, and considering {\it directed} cycles in the directed graph $\bar{G}=(V,A)$. In this interpretation, the incidence vector of a directed cycle $C$ of $\bar{G}$ is a vector $c^C\in\mathbb{R}^m$ satisfying \cite[\S 2, p.~201]{mehlhorn_cb}:
\begin{equation}
  \forall j\in V(C)\quad \sum\limits_{(i,j)\in A} c^C_{ij} = \sum\limits_{(j,\ell)\in A} c^C_{j\ell}.\label{flowcons}
\end{equation}

A directed circuit $D$ of $\bar{G}$ is obtained by applying the edge directions from $\bar{G}$ to a connected subgraph of $G$ where each vertex has degree exactly 2 (note that a directed circuit need not be strongly connected, although its undirected version is connected). Its incidence vector $c^D\in\{-1,0,1\}^m$ is defined as follows:
\begin{equation*}
  \forall (i,j)\in A \qquad c^D_{ij} \triangleq \left\{\begin{array}{rcl} 1 & \mbox{if} & (i,j)\in A(D) \\
  -1 & \mbox{if} & (j,i)\in A(D) \\
  0 & \mbox{otherwise} & \end{array}\right.
\end{equation*}
where we have used $A(D)$ to mean the arcs in the subgraph $D$. In other words, whenever we walk over an arc $(i,j)$ in the natural direction $i\to j$ we let the $(i,j)$-th component of $c^D$ be $1$; if we walk over $(i,j)$ in the direction $j\to i$ we assign a $-1$, and otherwise a zero.

\subsection{Constraints over cycle bases}
\label{ccycbas}
The properties of undirected and directed cycle bases have been investigated in a sequence of papers by many authors, culminating with \cite{mehlhorn_cb}. We now prove that it suffices to quantify Eq.~\eqref{newcon} over a directed cycle basis.
\begin{proposition}
  \label{propnewcon}
  Let $\mathcal{B}$ be a directed cycle basis of $\bar{G}$ over $\mathbb{Q}$. Then Eq.~\eqref{newcon} holds if and only if:
\begin{equation}
  \forall k\le K, B\in\mathcal{B}\qquad \sum\limits_{(i,j)\in A(B)} c^B_{ij}y_{ijk} = 0.\label{newcon2}
\end{equation}
\end{proposition}
\begin{proof}
Necessity $\eqref{newcon}\Rightarrow\eqref{newcon2}$ follows because Eq.~\eqref{newcon} is quantified over all cycles: in particular, it follows for any undirected cycle in any undirected cycle basis. Moreover, the signs of all terms in the sum of Eq.~\eqref{newcon2} are consistent, by definition, with the arbitrary edge direction chosen for $\bar{G}$. \\ [0.3em]
Next, we claim sufficiency $\eqref{newcon2}\Rightarrow\eqref{newcon}$. Let $C\in\mathcal{C}$ be a simple cycle, and $\bar{C}$ be its directed version with the directions inherited from $\bar{G}$. Since $\mathcal{B}$ is a cycle basis, we know that there is a coefficient vector $(\gamma_B\;|\;B\in\mathcal{B})\in\mathbb{R}^{|\mathcal{B}|}$ such that:
  \begin{equation}
    c^{\bar{C}} = \sum\limits_{B\in\mathcal{B}} \gamma_B c^B. \label{eqcC}
  \end{equation}
  We now consider the expression:
  \begin{equation}
    \forall k\le K\quad \sum\limits_{B\in\mathcal{B}} \gamma_B\sum\limits_{(i,j)\in A(B)} c^B_{ij} y_{ijk}.\label{eqcB}
  \end{equation}
  On the one hand, by Eq.~\eqref{eqcC}, Eq.~\eqref{eqcB} is identically equal to $\sum_{(i,j)\in A(\bar{C})} c^{\bar{C}}_{ij}y_{ijk}$ for each $k\le K$; on the other hand, each inner sum in Eq.~\eqref{eqcB} is equal to zero by Eq.~\eqref{newcon2}. This implies $\sum_{(i,j)\in A(\bar{C})} c^{\bar{C}}_{ij} y_{ijk} = 0$ for each $k\le K$. Since $C$ is simple and connected, $\bar{C}$ is a directed circuit. This implies that $c^{\bar{C}}\in\{-1,0,1\}$. Now it suffices to replace $-y_{ijk}$ with $y_{jik}$ to obtain
  \[\forall k\le K\quad \sum\limits_{\{i,j\}\in E(C)} y_{ijk} = 0, \]
  where the edges on $C$ are indexed in such a way as to ensure they appear in order of consecutive adjacency. \qed
\end{proof}
Obviously, if $\mathcal{B}$ has minimum (or just small) cardinality, Eq.~\eqref{newcon2} will be sparsest (or just sparse), which is often a desirable property of linear constraints occurring in MP formulations. Hence we should attempt to find short cycle bases $\mathcal{B}$.

In summary, given a basis $\mathcal{B}$ of the directed cycle space of $\bar{G}$ where $c^B$ is the incidence vector of a cycle $B\in\mathcal{B}$, the following:
\begin{equation}
  \left.
  \begin{array}{rrcl}
    \min\limits_{s\ge 0, y} & \sum\limits_{\{i,j\}\in E} (s_{ij}^+ + s^-_{ij}) && \\
  \forall (i,j)\in A(\bar{G}) &  \sum\limits_{k\le K} y_{ijk}^2 - d_{ij}^2 &=& s^+_{ij} - s^-_{ij} \\
  \forall k\le K, B\in\mathcal{B} & \sum\limits_{(i,j)\in A(B)} c^B_{ij}y_{ijk} &=& 0
  \end{array}\right\}\label{dgpnew}
\end{equation}
is a valid formulation for the EDGP. The solution of Eq.~\eqref{dgpnew} yields a feasible vector $y^\ast$. As pointed out in Cor.~\ref{2stage}, we must then solve Eq.~\eqref{xysys2} to obtain a realization $x^\ast$ for $G$.

\subsection{How to find directed cycle bases}
\label{s:findcycbas}
We require directed cycle bases over $\mathbb{Q}$. By \cite[Thm.~2.4]{mehlhorn_cb}, each undirected cycle basis gives rise to a directed cycle basis (so it suffices to find a cycle basis of $G$ and then direct the cycles using the directions in $\bar{G}$). Horton's algorithm \cite{horton87} and its variants \cite{golynski,liebchenrizzi} find a minimum cost cycle basis in polynomial time. The most efficient deterministic variant is $O(m^3n)$ \cite{liebchenrizzi}, and the most efficient randomized variant has the complexity of matrix multiplication. Existing approximation algorithms have marginally better complexity.

It is not clear, however, that the provably sparsest constraint system will make the DGP actually easier to solve. We therefore consider a much simpler algorithm: starting from a spanning tree, we pick the $m-n+1$ circuits that each {\it chord} (i.e., non-tree) edge defines with the rest of the tree. This algorithm \cite{paton} yields a {\it fundamental} cycle basis (FCB). Finding the minimum FCB is known to be {\bf NP}-hard \cite{deo82}, but heuristics based on spanning trees prove to be very easy to implement and work reasonably well \cite{deo82} (optionally, their cost can be improved by an edge-swapping phase \cite{fcbmmor,fcbmatroid}).

\section{The Eulerian cycle relaxation}
\label{s:eulerian}
In this section we construct a relaxation of Eq.~\eqref{dgpnew} that decreases the number of constraints in Eq.~\eqref{newcon2}, which occurs as the last line in Eq.~\eqref{dgpnew}, from $|\mathcal{B}|$ to $1$.

We let $G'$ be the multigraph obtained from $G$ by adding sufficiently many parallel edges to $G$, so that the degree of each vertex in $G'$ is even. This can always be done by \cite{edmonds2}, which implies that $G'$ is Eulerian, i.e.~it has a cycle incident with every edge in $G'$ exactly once. We let $\mathscr{E}$ be a Eulerian cycle in $G'$, and let $\bar{\mathscr{E}}$ be either of the two orientations of $\mathscr{E}$ obtained by walking over the cycle. We let $\bar{G}'$ be the digraph induced by the Eulerian circuit $\bar{\mathscr{E}}$. For each $\{i,j\}\in E$ let $H_{ij}$ be the number of parallel edges between $i,j$ in $G'$.

We note that $\bar{G}'$ might have parallel and antiparallel arcs. Consider the family of arc subset $\mathcal{H}_{ij}=\{(i',j',h)\;|\;h\le H_{ij}\land \{i',j'\}=\{i,j\}\}$ of $A(\bar{G}')$. We replace each arc $(i',j',h)\in\mathcal{H}_{ij}$ having $h>1$ by an oriented $2$-path $p_{i'j'h}=\{(i',v_{ijh}),(v_{ijh},j')\}$ involving a new added vertex $v_{ijh}$. Call $\tilde{G}$ the digraph obtained from $\bar{G}'$ with this replacement. We remark that $\tilde{G}$ is simple (it has no parallel/antiparallel arcs) by construction. Moreover, $\tilde{G}$ is a Eulerian digraph: take the Eulerian circuit $\bar{\mathscr{E}}$ in $\bar{G}'$, and, every time it traverses a parallel/antiparallel arc $(i',j',h)\in\mathcal{H}_{ij}$ with $h>1$, let it traverse the oriented $2$-path replacement $p_{i'j'h}$ instead: this is clearly a Euclidean circuit in $\tilde{G}$, which we call $\mathscr{C}$.

Next we consider the simple graph $\hat{G}$ obtained by replacing each arc in $\tilde{G}$ with an edge. Let $\hat{V}=\{v_{ijh}\;|\;\{i,j\}\in E\land h>1\}$, and $\hat{E}$ be the subset of edges of $E(\hat{G})$ obtained from losing the orientation of the arcs in the union
\[\bigcup\limits_{(i',j',h)\in \mathcal{H}_{ij}\atop \{i,j\}\in E\land h>1} p_{i'j'h} \]
of all the arcs from the $2$-path replacements. We note that, by construction,
\begin{equation}
  \hat{V}=V(\hat{G})\smallsetminus V\quad\land\quad \hat{E}=E(\hat{G})\smallsetminus E.\label{EVhat}
\end{equation}
Let $c^{\mathscr{C}}_{ij}\in\{1,-1\}$ be the orientation of $(i,j)$ in $\mathscr{C}$ w.r.t.~$\hat{G}$; let $\hat{\mathscr{C}}$ be the simple Eulerian cycle in $\hat{G}$ corresponding to $\mathscr{C}$.

We can now prove the main result of this section.
\begin{proposition}
  \label{propdgprel}
  The formulation
\begin{equation}
  \left.
  \begin{array}{rrcl}
    \min\limits_{s\ge 0, y} & \sum\limits_{\{i,j\}\in E} (s_{ij}^+ + s^-_{ij}) && \\
  \forall (i,j)\in A(\bar{G}) &  \sum\limits_{k\le K} y_{ijk}^2 - d_{ij}^2 &=& s^+_{ij} - s^-_{ij} \\
  \forall k\le K & \sum\limits_{(i,j)\in \mathscr{C}} c^{\mathscr{C}}_{ij}y_{ijk} &=& 0\quad(\dag)
  \end{array}\right\}\label{dgprel}
\end{equation}
is a relaxation of Eq.~\eqref{dgpnew}.
\end{proposition}
\begin{proof}
We form a variant of the cycle formulation Eq.~\eqref{dgpnew} applied to $\hat{G}$, where, from the constraints corresponding to Eq.~\eqref{newsys} (second line of Eq.~\eqref{dgpnew}), we omit those indexed by $\hat{E}$. We call this variant ($\star$). We \underline{claim} that ($\star$) is an exact reformulation of Eq.~\eqref{dgpnew} applied to $G$. The claim holds because $E(\hat{G})\smallsetminus\hat{E}=E$ by Eq.~\eqref{EVhat}, and because the signs of the $y$ variables are irrelevant in Eq.~\eqref{newsys} since they are squared. Now, since $\hat{\mathscr{C}}$ is a Eulerian cycle in $\hat{G}$, Eq.~($\dag$) is an aggregation of constraints in Eq.~\eqref{newcon2}, which occur within the reformulation ($\star$). So Eq.~\eqref{dgprel} is a relaxation of ($\star$). The proposition follows because of the \underline{claim}. \qed
\end{proof}

Note that Eq.~\eqref{dgprel} provides a solution $\bar{y}$ which may not satisfy Eq.~\eqref{newcon2}, which also guarantee feasibility in Eq.~\eqref{newcon} by Prop.~\ref{propnewcon}. By Remark \ref{xysysfeas}, this implies that Cor.~\ref{2stage} is no longer applicable. In other words, the realization $x$ of $G$ cannot in general be retrieved from $\bar{y}$ using the linear system in Eq.~\eqref{xysys2}, since $\bar{y}$ might well make Eq.~\eqref{xysys2} infeasibile. Eq.~\eqref{xysys2}, however, can instead be integrated into Eq.~\eqref{dgprel} as additional constraints. This invalidates the decomposition property of Cor.~\ref{2stage}, but allows the relaxation to yield a valid realization.

We therefore define the Eulerian cycle-based relaxation formulation as follows:
\begin{equation}
  \left.
  \begin{array}{rrcl}
    \min\limits_{s\ge 0, x,y} & \sum\limits_{\{i,j\}\in E} (s_{ij}^+ + s^-_{ij}) && \\
  \forall (i,j)\in A(\bar{G}) &  \sum\limits_{k\le K} y_{ijk}^2 - d_{ij}^2 &=& s^+_{ij} - s^-_{ij} \\
  \forall k\le K & \sum\limits_{(i,j)\in A(\tilde{\mathscr{E}})} c^{\tilde{\mathscr{E}}}_{ij}y_{ijk} &=& 0 \\
  \forall \{i,j\}\in A(\bar{G}) & x_{ik}-x_{jk} &=& y_{ijk} \\
  \forall k\le K & \sum\limits_{i\in V} x_{ik} &=& 0.
  \end{array}\right\}\label{dgprel1}
\end{equation}

For a formulation $P$, we denote by $\val{P}$ its optimal objective function value. Since Eq.~\eqref{dgprel1} has additional constraints w.r.t.~Eq.~\eqref{dgprel}, we naturally have $\val{\ref{dgprel1}}\ge\val{\ref{dgprel}}$. Moreover, for every instance for which a solution $\bar{y}$ of Eq.~\eqref{dgprel} yields an infeasible system Eq.~\eqref{xysys2}, by inspection $\bar{y}$ must be infeasible in Eq.~\eqref{dgprel1}, which implies that there are cases where Eq.~\eqref{dgprel1} is a strictly tighter relaxation than Eq.~\eqref{dgprel}. The very last constraint in Eq.~\eqref{dgprel1} fixes the centroid of the points at the origin, as in Eq.~\eqref{go1}.

\section{Computational experiments}
\label{s:compres}
The aim of this section is to compare the computational performance of the following EDGP formulations:
\begin{enumerate}[(i)]
\item the cycle-based formulation in Eq.~\eqref{dgpnew}, where the realization is retrieved as a post-processing stage using \eqref{xysys2} according to Cor.~\ref{2stage};
\item the Eulerian cycle-based relaxation in Eq.~\eqref{dgprel1};
\item the classic edge-based formulation in Eq.~\eqref{go1}.
\end{enumerate}
All of these formulations are nonconvex Nonlinear Programs (NLP), which are generally $\mathsf{NP}$-hard to solve. Specifically, formulations (i) and (iii) are as hard to solve as the EDGP, which is $\mathsf{NP}$-hard. No specific $\mathsf{NP}$-hardness proof exists for formulation (ii) yet.

As a solution algorithm, we used a very simple MultiStart (MS) heuristic based on calling a local NLP solver from a random initial starting point at each iteration, and updating the best solution found so far as needed: although there are better heuristics around \cite{dvnsjogo,zoo,mwu}, MS is the best trade-off between implementation simplicity and efficiency. Moreover, more efficient heuristic often change the formulation during their execution, which may hinder the meaning of this computational comparison between formulations.

We evaluate the quality of a realization $x$ of a graph $G$ according to mean (MDE) and largest distance error (LDE), defined this way:
\begin{eqnarray*}
  \mathsf{mde}(x,G) &=& \frac{1}{|E|} \sum\limits_{\{i,j\}\in E} \big| \|x_i-x_j\|_2 - d_{ij}\big|\\
  \mathsf{lde}(x,G) &=& \max\limits_{\{i,j\}\in E} \big| \|x_i-x_j\|_2 - d_{ij}\big|.
\end{eqnarray*}

The CPU time taken to find the solution may also be important, depending on the application. In the control of underwater vehicles \cite{bahr}, for example, DGP instances might need to be solved in real time. In other applications, such as finding protein structure from distance data \cite{bipbip,jcim} (our application of choice), the CPU time is not so important.

Our tests were carried out on a single CPU of a 2.1GHz 4-CPU 8-core-per-CPU machine with 64GB RAM running Linux. The local NLP solver used within the MS heuristic was the IPOpt solver \cite{ipopt}. We remarked in some preliminary tests that IPOpt was considerably slowed down by variants of Eq.~\eqref{go} such as Eq.~\eqref{minabs}, which essentially move a nonconvexity on the objective to one in the constraints. The same holds for the cycle-based formulation in Eq.~\eqref{dgpnew}. We therefore reformulated Eq.~\eqref{dgpnew} as follows:
\begin{equation}
  \left.
  \begin{array}{rrcl}
    \min\limits_{y} & \sum\limits_{\{i,j\}\in A(\bar{G})} (\sum\limits_{k\le K} y_{ijk}^2 - d_{ij}^2)^2 && \\
  \forall k\le K, B\in\mathcal{B} & \sum\limits_{(i,j)\in A(B)} c^B_{ij}y_{ijk} &=& 0,
  \end{array}\right\}\label{dgpnew1}
\end{equation}
and Eq.~\eqref{dgprel1} similarly.

Our implementation consists of a mixture of Python 3 \cite{python3} and AMPL \cite{ampl} interfaced through \texttt{amplpy}. Cycle bases and Eulerian cycles are found using \texttt{networkX} \cite{networkX}. Solutions to the feasible but possibly overdetermined linear systems in Eq.~\eqref{xysys2} are obtained using an $\ell_1$ error minimization approach reformulated as a Linear Programming problem solved with CPLEX \cite{cplex129}.

\subsection{Results}
A benchmark on a diverse collection of randomly generated weighted graphs of small size and many different types, with a very similar set-up to the one discussed here, is presented in \cite{cycledgp-ctw20}. It was found that the cycle formulation finds better MDE values, while the edge formulation generally finds better LDE values and is faster. Some results on proteins, obtained with only 3 MS iterations, were also presented in \cite{cycledgp-ctw20}.

The benchmark we consider here contains medium to large scale protein graph instances realized in $\mathbb{R}^3$. W.r.t.~the protein results presented in \cite{cycledgp-ctw20}, we integrated one more instance, \texttt{1tii}, which, at 69800 edges and 5684 vertices, is considerably larger than all the others.

The results are given in Table \ref{t2}. We report instance name, instance sizes $m$ and $n$, then performance measures MDE, LDE and CPU for cycle, Eulerian and edge-based formulations. In the last three lines we report average, standard deviation, and number of instances where the formulation performed best, for all performance measures. In all tested cases, finding the cycle basis, the Eulerian cycles, and solving Eq.~\eqref{xysys2} took a small fraction of the total solution time. The missing result for instance \texttt{100d} on the Eulerian cycle reformulation is due to a failure occurred in the \texttt{networkX} module because the graph of \texttt{100d} is not connected.
\begin{table}[!ht]
  {\scriptsize
\begin{center}
  \hspace*{-0.8cm}\begin{tabular}{lrr|rrr|rrr|rrr} \hline
                   &   &  & \multicolumn{3}{c|}{MDE} & \multicolumn{3}{c|}{LDE} & \multicolumn{3}{c}{CPU} \\
{\it Instance}     & $m$  & $n$ & cycle & Eul   & edge      & cycle & Eul   & edge      & cycle    & Eul   & edge           \\ \hline
\texttt{1guu}      & 955  & 150 & 0.086 & 0.069 & \B{0.053} & 1.234 & 1.068 & \B{1.037} & \B{7.90} & 553.76   & 290.21      \\
\texttt{1guu-1}    & 959  & 150 & 0.080 & 0.082 & \B{0.059} & 1.013 & 1.069 & \B{0.980} & 9.67	   & 23.03    & \B{1.72}    \\
\texttt{1guu-4000} & 968  & 150 & 0.112 & 0.106 & \B{0.092} & 1.073 & 1.431 & \B{0.936} & 8.68	   & 10.77    & \B{1.56}    \\
\texttt{pept}      & 999  & 107 & \B{0.144} & 0.239 & 0.179 & 2.862 & \B{1.847} & 1.943 & 5.52	   & 4.72     & \B{1.4}     \\
\texttt{2kxa}     & 2711  & 177 & \B{0.051} & 0.119 & 0.172 & 3.705 & \B{2.826} & 3.813 & 21.53	   & 25.54    & \B{7.35}    \\
\texttt{res\_2kxa}& 2627  & 177 & \B{0.055} & 0.237 & 0.156 & \B{2.949} & 3.570 & 3.054 & 20.84	   & 21.20    & \B{12.44}   \\
\texttt{C0030pkl} & 3247  & 198 & \B{0.000} & 0.145 & 0.211 & \B{0.000} & 3.537 & 3.829 & 29.50	   & 26.69    & \B{7.36}    \\
\texttt{cassioli} & 4871  & 281 & 0.146 & 0.113 & \B{0.057} & 3.914 & 3.616 & \B{3.185} & 47.23	   & 48.44    & \B{14.51}   \\
\texttt{100d}     & 5741  & 488 & \B{0.201} & -     & 0.251 & \B{3.038} & -     & 3.987 & 387.32   & -        & \B{29.42}   \\
\texttt{hlx\_amb} & 6265  &392  & \B{0.105} & 0.214 & 0.119 & 3.836 & 3.888 & \B{3.485} & 120.25   & 80.27    & \B{20.54}   \\
\texttt{water}   & 11939  & 648 & \B{0.146} & 0.490 & 0.243 & \B{3.579} & 4.196 & 4.281 & 1346.69  & 399.42   & \B{224.66}  \\
\texttt{3al1}    & 17417  & 678 & \B{0.062} & 0.126 & 0.216 & 3.451 & \B{3.175} & 4.059 & 835.10   & 433.69   & \B{123.45}  \\
\texttt{1hpv}    & 18512 & 1629 & \B{0.385} & 0.402 & 0.416 & 3.847 & \B{3.831} & 4.015 & 10138.00 & 2387.29  & \B{442.70}  \\
\texttt{il2}     & 45251 & 2084 & 0.385 & \B{0.049} & 0.107 & 4.422 & \B{4.204} & 4.583 & 18141.22 & 9904.81  & \B{5255.76} \\
\texttt{1tii}    & 69800 & 5684 & 0.620 & 0.436 & \B{0.434} & 6.755 & 4.492 & \B{3.854} & 18846.37 & 38230.21 & \B{9039.28} \\ \hline
\textit{avg}     &       &      & \B{0.172} & 0.202 & 0.184 & \B{3.045} & 3.054 & 3.136 & 3331.05  & 3724.99  & \B{1031.49} \\
\textit{stdev}   &       &      & 0.167 & 0.144 & \B{0.118} & 1.673 & \B{1.204} & 1.272 & 6672.49  & 10272.3  & \B{2587.33} \\
\textit{$|\mbox{best}|$} &   &  & \B{9} &  1    &    5      &    4  &    5      & \B{6} &  1       & 0        & \B{14}
  \end{tabular}
\end{center}
  }
\caption{Cycle formulation vs.~edge formulation performance on protein graphs (realizations in $K=3$ dimensions).}
\label{t2}
\end{table}

It appears that, on average, there is relatively little difference between the quality performances of these three DGP formulations on protein graphs of medium and large sizes. CPU-time wise, of course, the edge formulation is best. Cycle formulations, taken together, are definitely better than the edge formulation on quality measures. The cycle-based formulation Eq.~\eqref{dgpnew} is slightly better than the other formulations for both MDE and LDE. The number of instances on which Eq.~\eqref{dgpnew} is best on quality measures is 13, against 11 for the edge-based formulation. Eq.~\eqref{dgpnew} was the only formulation by which a global optimum was found (that of \texttt{C0030pkl}). All in all, we believe that our results show that cycle formulations are credible competitors w.r.t.~the well established edge-based formulations, especially when the CPU time is not an important performance measure (which is generally the case in the protein conformation application).

\section*{Acknowledgements}
While the seminal idea for considering DGPs over cycles dates from Saxe's {\bf NP}-hardness proof \cite{saxe79}, the ``cycle formulation'' concept occurred to us as one of the authors (LL) attended a talk by Matteo Gallet given at the Erwin Schr\"odinger Institute (ESI), Vienna, during the Geometric Rigidity workshop 2018. LL has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement n.~764759 ``MINOA''. CL is grateful to the Brazilian research agencies FAPESP and CNPq for support. NM is grateful to the Brazilian research agencies COPPETEC Foundation and CNPq for support.

\ifjour
\ifams
\bibliographystyle{amsplain}
\else
\bibliographystyle{spmpsci}
\fi
\else


TITLE: Correspondence Between First Galois Cohomology and Semilinear Actions Up to Isomorphism
QUESTION [4 upvotes]: I've been stuck for a while on Exercise 1.9 of Bjorn Poonen's "Rational Points on Varieties". We start with $L/K$ a finite Galois extension with Galois group $G$, some $r \in \mathbb{Z}_{\geq 0}$, and for each 1-cochain $\xi: G \rightarrow GL_r\left(L\right)$, we define $W_{\xi}$ to be $L^r$ with equipped with the function $G \times L^r \rightarrow L^r$, $\sigma \mapsto \xi_{\sigma}\left(\sigma w\right)$.
In the first part of the question, we are asked to show that this function describes a semilinear $G$-action on $W_{\xi}$ iff $\xi$ is a 1-cocycle, i.e., $\xi_{\sigma \tau} = \xi_\sigma {}^{\sigma}\xi_{\tau}$. I have managed this.
The second part is to show that, for two $1$-cocycles $\xi$ and $\xi'$, the spaces $W_\xi$ and $W_{\xi'}$ are isomorphic as $L$-vector spaces with semilinear $G$-action iff $\xi$ and $\xi'$ are cohomologous. This is where I am stuck.
I am new to group cohomology, but I have studied other types of cohomology before and have read a few things on group cohomology in order to try and solve this problem. As I understand it, $\xi$ and $\xi'$ are cohomologous iff their difference is a $1$-coboundary, i.e., a principal crossed homomorphism. Translating the standard definitions into multiplicative language, I believe this amounts to showing that there is some $f \in GL_r\left(L\right)$ such that, for all $w \in W = L^r$ and all $\sigma \in G$, we have $$\xi'_{\sigma} \xi_{\sigma}^{-1}\left(w\right) = \left({}^{\sigma}f\right) f^{-1}\left(w\right),$$ i.e.,

\begin{equation}
\xi'_{\sigma} \xi_{\sigma}^{-1} = \left({}^{\sigma}f\right) f^{-1}.
\end{equation}

Now, from what I can gather, $W_{\xi}$ and $W_{\xi'}$ are isomorphic as $L$-vector spaces with semilinear $G$-action iff there is $g \in GL_r\left(L\right)$ such that for all $w \in W = L^r$ and all $\sigma \in G$, we have $$g\left(\xi_\sigma \left(\sigma w\right)\right) = \xi'_{\sigma}\left(\sigma g\left(w\right)\right),$$ i.e., $$g\left(\xi_\sigma \left(\sigma w\right)\right) = \xi'_{\sigma}\left( {}^{\sigma}g\left(\sigma w\right)\right),$$ meaning precisely that

\begin{equation}
g \xi{_\sigma} = \xi'_{\sigma}{}^{\sigma}g.
\end{equation}

My idea for tackling this is to show that we can manipulate the second expression until it is in the form of the first one.
From $\xi$ being a 1-cocycle, we can deduce that $\xi_{id_G} = id_{GL_r\left(L\right)}$ and then that $\xi_{\sigma}^{-1} = {}^{\sigma}\xi_{\sigma^{-1}}$, so, assuming the latter highlighted equation (involving $g$), we get $$\xi'_{\sigma} \xi_{\sigma}^{-1} = \xi'_{\sigma} {}^{\sigma}\xi_{\sigma^{-1}} = g\xi_\sigma {}^{\sigma}\left(g^{-1}\right) {}^{\sigma}\xi_{\sigma^{-1}} = g\xi_\sigma {}^{\sigma}\left(g^{-1}\xi_{\sigma^{-1}}\right),$$ but I can't work that into the form I want by a suitable choice of $f$. I have tried other manipulations, but with no success.
My conclusion is that I have probably misunderstood or mistranslated some concept. In particular, I fear I might have the wrong notion of isomorphism for $L$-vector spaces with semilinear $G$-action. The definition I have here is one I found for isomorphism of $G$-sets on Wikipedia. Initially, I had wondered whether an isomorphism should be a pair $\left(\phi,h\right)$ where $\phi: G \rightarrow G$ is an automorphism, $h \in Gl_r\left(L\right)$ and, for all $w \in W$ and $\sigma \in G$, $$h\left(\xi_\sigma \left(\sigma w\right)\right) = \xi'_{\phi\left(\sigma\right)}\left(\phi\left(\sigma\right)h\left(w\right)\right),$$
so in particular I get the first definition back if $\phi$ is the identity map on $G$, but I'm not sure.
If anybody can point out the erroneous definitions/where I am going wrong, then I would be very grateful.

REPLY [7 votes]: Your mistake is in the meaning of $\xi$ and $\xi'$ being cohomologous. The condition should be
$\xi_\sigma =f^\sigma \xi'_\sigma f^{-1}$, for some $f\in GL_r(L)$. This is the correct definition of cohomologous cocycles in the non-abelian cituation, and then $f$ just give you the isomorphism.
In general one should be careful about order and directions when dealing with non-abelian cohomologies. The correct formulas are usually not the first one you would guess.


TITLE: Test the convergence of the following series.
QUESTION [2 upvotes]: I have to find the limit of the following:
$\sum_{n=1}^{\infty}\frac{1}{2^{n}+x} = $,$x\geq0$
So I used Ratio test as follows:
$u_n=\frac{1}{2^n+x}$
$u_{n+1}=\frac{1}{2^{n+1}+x}$
$\frac{u_n}{u_{n+1}}=\frac{2^{n+1}+x}{2^n+x}$,
Taking limits as n tends to infinity, I got :
$lim\frac{u_n}{u_{n+1}}=2>1$
So given series is convergent. But in my textbook, the answer given is: convergent if $x=0$ and divergent if $x$ is not equal to 0. I can see why it is convergent if $x$ equals 0, but why is it divergent if $x$ not equal to 0?
Thanks in advance!

REPLY [3 votes]: The textbook answer is definitely wrong. Actually you can use comparison test:
\begin{align*}
\dfrac{1}{2^{n}+x}\leq\dfrac{1}{2^{n}},~~~~x\geq 0
\end{align*}
and $\sum 2^{-n}<\infty$.


TITLE: Is the mapping torus of an automorphism of a free group virtually an amalgamated product?
QUESTION [5 upvotes]: Let $F$ be a nonabelian finitely generated free group,
let $\tau \in \mathrm{Aut}(F)$ be an element of infinite order,
and set $G = F \rtimes \mathbb{Z}$,
where the action of $\mathbb{Z}$ on $F$ is given by $\tau$.
Must there be a finite index subgroup $U$ of $G$,
such that $U \cong A*_CB$ where $C$ is a proper subgroup of both $A$ and $B$, and its index in either $A$ or $B$ is at least $3$?
What happens if $\tau$ is inner?

REPLY [3 votes]: If you drop "virtually" from your question, then this has been analyzed very thoroughly by Brinkmann. Whether this is directly relevant to your question is, of course, open to debate.
Peter Brinkmann, MR 1934698 Splittings of mapping tori of free group automorphisms, Geom. Dedicata 93 (2002), 191--203.


TITLE: Diffeomorphisms of the torus $\mathbb T^n$
QUESTION [5 upvotes]: While reading the first chapter of Orbifolds and Stringy Topology by Adem, Leida and Ruan, I stumbled upon the following assertion, in page 5

The group
$\text{GL}_n(\mathbb Z)$ acts by matrix multiplication on $\mathbb R^n$, taking the lattice $\mathbb Z^n$ to itself. This
then induces an action on $\mathbb T^n=(\mathbb R/\mathbb Z)^n$. In fact, one can easily show that the
map induced by looking at the action in homology, $\Phi:\text{Aut}(\mathbb T^n)\rightarrow\text{GL}_n(\mathbb Z)$,
is a split surjection.

What? I know that a linear isomorphism $A:\mathbb R^n\rightarrow\mathbb R^n$ induces a diffeomorphism of $\mathbb T^n$ if, and only if the matrix associated to $A$ has coefficients in $\mathbb Z$ and has determinant equal to $\pm1$, that is, if it belongs to $\text{GL}_n(\mathbb Z)$. There are many posts about that on this site, but I am puzzled about that action in homology thing, and that it induces an split surjection from the group  $\text{Aut}(\mathbb T^n)$ onto $\text{GL}_n(\mathbb Z)$. I can imagine diffeomorphisms of the torus that don't come from any linear isomorphism on $\mathbb R^n$, but why should these have any structure whatsoever?
Thanks in advance for your answer.

REPLY [7 votes]: What it means is the following.
For any continuous map $\phi:\Bbb T^n\rightarrow \Bbb T^n$, there is an induced homomorphism of groups: $\phi_*: H_1(\Bbb T^n) \rightarrow H_1(\Bbb T^n)$.
We know that $H_1(\Bbb T^n)$ is isomorphic to $\Bbb Z^n$. Thus we can view $\phi_*$ as an endomorphism of $\Bbb Z^n$.
Now suppose that $\phi \in \operatorname{Aut}(\Bbb T^n)$. This means that it is not only a continuous map, but also has a continuous inverse. Therefore we see that $\phi_*$ is an automorphism of the group $\Bbb Z^n$, i.e. $\phi_*\in \operatorname{GL}_n(\Bbb Z)$.
By functoriality, the map $\phi \mapsto \phi_*$ is a group homomorphism from $\operatorname{Aut}(\Bbb T^n)$ to $\operatorname{GL}_n(\Bbb Z)$. This is the $\Phi$ map in your question.
They then state that this map is a split surjection. This is equivalent to sayting that there exists a splitting homomorphism $\Psi: \operatorname{GL}_n(\Bbb Z)\rightarrow \operatorname{Aut}(\Bbb T^n)$ such that $\Phi \circ \Psi$ is the identity map on $\operatorname{GL}_n(\Bbb Z)$.
This splitting map $\Psi$ is just constructed as you have described: for any $g\in \operatorname{GL}_n(\Bbb Z)$, the map $x \mapsto gx$ defined on $\Bbb R^n$ induces a map from $\Bbb T^n$ to itself, which we define as $\Psi(g)$.


TITLE: Calculate limit $\lim_{n\rightarrow\infty}\frac{(4n-100)^{4n-100}n^n}{(3n)^{3n}(2n)^{2n}}?$
QUESTION [2 upvotes]: The limit $$\lim_{n\rightarrow\infty}\dfrac{(4n)^{4n}n^n}{(3n)^{3n}(2n)^{2n}}$$ can be calculated as $\lim_{n\rightarrow\infty}\dfrac{4^{4n}}{3^{3n}2^{2n}}=\lim_{n\rightarrow\infty}\left(\dfrac{4^4}{3^32^2}\right)^n=\infty$.
What about $$\lim_{n\rightarrow\infty}\dfrac{(4n-100)^{4n-100}n^n}{(3n)^{3n}(2n)^{2n}}?$$ Would it still be $\infty$?

REPLY [2 votes]: Call your function $f(n)$.  Then it's enough to show that $\lim_{n \to \infty} \log f(n) = \infty$.  We can write
$\log f(n) = (4n-100) \log (4n-100) + n \log n - 2n \log 2n - 3n \log 3n$
and let's consider that first term, $(4n-100) \log (4n-100)$.  It would be really nice if that were $4n \log 4n$, so let's rewrite it as
$(4n-100) \log (4n-100) = (4n-100) \log 4n + (4n-100) \log ((4n-100)/4n)$
or, after some rearrangement,
$4n \log 4n - 100 \log 4n + (4n-100) \log (1 - 25/n)$.
Therefore the original function is
$\log f(n) = (4n \log 4n + n \log n - 2n \log 2n - 3n \log 3n) - 100 \log 4n + (4n-100) \log (1 - 25/n)$.
Now, let's start rearranging, recalling that $\log 4n = \log 4 + \log n$ and so on.  You get
$\log f(n) = 4n \log 4 + 4n \log n + n \log n - 2n \log 2 - 2n \log n - 3n \log 3 - 3n \log n - 100 \log 4n + (4n-100) \log (1-25/n)$.
The terms with $\log n$ cancel out, so you get
$\log f(n) = n(4 \log 4 - 2 \log 2 - 3 \log 3) - 100 \log 4n + (4n-100) \log (1-25/n)$.
The first term grows linearly.    The second term grows logarithmically.  The third term approaches $-100$ as $n \to \infty$.  So the whole thing grows linearly as $n \to \infty$; in particular since $4 \log 4 - 2 \log 2 - 3 \log 3 = \log (256/108) > 0$, the whole thing goes to infinity, as desired.


TITLE: Convergence or divergence of $\sum\limits_n(-1)^{\pi(n)}\frac1n$ where $\pi(n)$ is the number of primes less than or equal to $n$
QUESTION [13 upvotes]: Consider $$\sum_{n=1}^{\infty}\frac{(-1)^{\pi(n)}}{n}$$ where $\pi(n)$ is the number of primes less than or equal to $n$.
Does this sum converge or does it diverge? Are there any results related to this?

REPLY [0 votes]: It is not currently known whether or not the sum $\sum_{n=1}^\infty \frac{(-1)^{\pi(n)}}{n}$ converges.
I've been working on a related problem that sheds some light:
Erdos asks if the sum $\sum_{n=1}^\infty \frac{ (-1)^n n}{p_n}$ converges.  Here $p_n$ is the n-th prime number.  By using the prime number theorem and estimating the difference between $\frac{n}{p_n}$ and $\frac{n+1}{p_{n+1}}$ for odd and even $n$, one can show that Erdos' series converges simultaneously with the series $\sum_{n=2}^\infty \frac{(-1)^{\pi(n)}}{n \log n}$.  Here is a link to the problem I am working on https://mathoverflow.net/q/313999/8435