text:
\begin{document}

\title{The Schur degree of additive sets}

\author{S. Eliahou and M.P. Revuelta}
\date{}

\maketitle

\begin{abstract} Let $(G,+)$ be an abelian group. A subset of $G$ is \emph{sumfree} if it contains no elements $x,y,z$ such that $x+y=z$. We extend this concept by introducing the \emph{Schur degree} of a subset of $G$, where Schur degree $1$ corresponds to sumfree. The classical inequality $S(n) \le R_n(3)-2$, between the Schur number $S(n)$ and the Ramsey number $R_n(3)=R(3,\dots,3)$, is shown to remain valid in a wider context, involving the Schur degree of certain subsets of $G$. Recursive upper bounds are known for $R_n(3)$ but not for $S(n)$ so far. We formulate a conjecture which, if true, would fill this gap. Indeed, our study of the Schur degree leads us to conjecture $S(n) \le n(S(n-1)+1)$ for all $n \ge 2$. If true, it would yield substantially better upper bounds on the Schur numbers, e.g. $S(6) \le 966$ conjecturally, whereas all is known so far is $536 \le S(6) \le 1836$.
\end{abstract}

\begin{quote}
Keywords: Sumfree; Schur numbers; Ramsey numbers; Discrete derivative; Minors. \vspace{0.15cm} \\
MSC Classification: 05D10, 11B75, 11P70
\end{quote}

\section{Introduction}

For $a,b \in \Z$, let $[a,b]=\{z \in \Z \mid a \le z \le b\}$ and $[a,\infty[=\{z \in \Z \mid a \le z\}$ denote the integer intervals they span. Denote $\N=\{0,1,2,\dots\}$ and $\N_+=\N\setminus \{0\}$.

\smallskip
A subset of $\Z$ is \emph{sumfree} if it contains no elements $x,y,z$ such that $x+y=z$. The problem of partitioning $[1,N]$ into as few sumfree parts as possible was initiated by Schur~\cite{schur}. Given $n \in \N_+$, Schur established the existence of a number $S(n)$ such that $[1,N]$ can be partitioned into $n$ sumfree parts if and only if $N \le S(n)$. The $S(n)$ are called the Schur numbers and, despite more than a century in existence, remain poorly understood at the time of writing. Their only currently known values are
\begin{equation}\label{schur numbers}
\big(S(1),\,\, S(2),\,\, S(3),\,\, S(4),\,\, S(5)\big) = (1,\,\, 4,\,\, 13,\,\, 44,\,\, 160).
\end{equation}
See Section~\ref{sec comparisons} for more details.
In his paper, Schur proved the following upper bound and recursive lower bound on the $S(n)$ for $n \ge 2$, namely
\begin{equation}\label{schur bounds}
3S(n-1)+1 \,\le\, S(n) \,\le\, n!e,
\end{equation}
leading in particular to $S(n) \ge (3^n-1)/2$ for all $n \ge 2$.

\smallskip
For $n \ge 1$, the $n$-color Ramsey number $R_n(3)=R(3,\dots,3)$ denotes the smallest $N$ such that, for any $n$-coloring of the edges of the complete graph $K_N$ on $N$ vertices, there is a monochromatic triangle. See~\cite{radzi} for an extensive dynamic survey on this topic. Only three of the numbers $R_n(3)$ are currently known, namely
\begin{equation}\label{ramsey numbers}
\big(R_1(3),\,\, R_2(3),\,\, R_3(3)\big) = (3,\,\, 6,\,\, 17).
\end{equation}
As for $n=4$, the presently known bounds are $51 \le R_4(3) \le 62$. It is conjectured in~\cite{XuR} that $R_4(3)$ equals $51$. Similarly to the upper bound in~\eqref{schur bounds}, it was shown in~\cite{GG} that $R_n(3) \le n!e+1$ for all $n \ge 1$. This bound has later been improved to $$R_n(3) \le n!(e-1/6)+1$$ for all $n \ge 4$ in~\cite{XuXC}. See also~\cite{E}, where the conjecture $R_4(3)=51$ is shown to imply $R_n(3) \le n!(e-5/8)+1$ for all $n \ge 4$.

\smallskip
In fact, there is a well known relationship between the Schur and the Ramsey numbers, namely
\begin{equation}\label{S and R v1}
S(n) \le R_n(3)-2.
\end{equation}
See e.g.~\cite{soifer}. That is, \emph{if the set $[1,N]$ admits a partition into $n$ sumfree parts, then $N \le R_{n}(3)-2$.}

\smallskip

We shall show here that \eqref{S and R v1} holds in a more general context. Let $(G,+)$ be an abelian group. As in $\Z$, a subset of $G$ is \emph{sumfree} if it contains no elements $x,y,z$ such that $x+y=z$. Given a finite sequence $A=(a_1,\dots,a_N)$ in $G$, let us denote by $\hat{A}$ the set of all \emph{block sums} $a_{k}+\dots+a_\ell$ of $A$, where $1 \le k \le \ell \le N$. For instance, if $A=(1,\dots,1)$ of length $N$ in $G=\Z$, then $\hat{A}=[1,N]$.

In this paper, we are concerned with partitioning subsets of $G$ of the form $\hat{A}$ into as few sumfree parts as possible. As just noted, this includes Schur's original problem for the integer intervals $[1,N]$.  Our extension of~\eqref{S and R v1} to this more general setting states that \emph{if $A$ is a sequence in $G$ of length $|A|=N$ and if $\hat{A}$ can be covered by $n$ sumfree parts, then $N \le R_{n}(3)-2$}.

Currently, the best available theoretical upper bound on $S(n)$ for $n \ge 4$ is the one provided by~\eqref{S and R v1}. While the Ramsey numbers $R_n(3)$ satisfy the well known recursive upper bound
$$
R_n(3) \le n(R_{n-1}(3)-1)+2
$$
for all $n \ge 2$~\cite[Theorem 6, p. 6]{GG}, no similar statement is known yet for the $S(n)$. Here we fill this gap, at least conjecturally, as an outcome of our study of sumfree partitions of sets of the form $\hat{A}$. Indeed, as we shall see, that study leads us to conjecture the following recursive upper bound, for all $n \ge 2$:
\begin{equation}\label{conj S}
S(n) \le n(S(n-1)+1).
\end{equation}

The contents of this paper are as follows. In Section~\ref{sec basic}, we introduce the Schur degree and the basic notions and tools needed in the sequel. In Section~\ref{sec schur degree}, we prove initial properties of the Schur degree and illustrate them with selected examples in $\Z$. Our main result, an extension of \eqref{S and R v1} to sets $\hat{A}$ bounding their Schur degree with the Ramsey numbers $R_n(3)$, is proved in Section~\ref{sec comparison}. The material developed so far leads us in Section~\ref{sec conjectures} to the conjectural recursive upper bound~\eqref{conj S}, a substantial would-be improvement over~\eqref{S and R v1}.

\section{Basic notions and tools}\label{sec basic}

Here is the main notion introduced and studied in this paper.

\begin{definition} Let $(G,+)$ be an abelian group. Let $X \subseteq G$ be a subset. We define the \emph{Schur degree} of $X$, denoted $\sd(X)$, as the smallest $n \ge 1$ such that $X$ can be covered by $n$ sumfree subsets. If no such $n$ exists, we set $\sd(X)=\infty$.
\end{definition}
For instance, $\sd(X)=1$ if and only if $X$ is sumfree, whereas $\sd(X)=\infty$ whenever $0 \in X$, as $\{0\}$ is not sumfree. As another instance, in $\N$ we have
\begin{equation}\label{eq schur}
\sd([1,S(n)]) = n, \quad \sd([1,S(n)+1]) = n+1
\end{equation}
by definition of $S(n)$. Equivalently, $\sd([1,N]) \le n \iff N \le S(n)$.

\smallskip
Measuring the Schur degree of most subsets is likely to remain an extremely difficult task, even for the integer intervals $[1,N]$ as witnessed by the still highly mysterious Schur numbers $S(n)$. In this paper, we focus on subsets of a certain form $\hat{A}$, generalizing the intervals $[1,N]$ and introduced below.

\subsection{Block sums}

Let $(G,+)$ be an abelian group. Let $A=(a_1,\dots,a_N)$ be a finite sequence in $G$. We denote by $|A|=N$ its length and by $\sigma(A)=\sum_i a_i$ the sum of its elements.

A \emph{block} in $A$ is any nonempty subsequence of consecutive elements of $A$. That is, any subsequence of the form
\[
B=(a_{i},
\dots,a_j)
\]
for some $1 \le i \le j \le N$. A \emph{block sum} in $A$ is a sum $\sigma(B)$ where $B$ is any block in $A$, i.e. any element in $G$ of the form $a_i+\dots+a_j$ for some $1 \le i \le j \le N$.

\begin{notation} Let $A=(a_1,\dots,a_N)$ be a sequence in $G$. We denote by
$$\hat{A} = \{\sigma(B) \mid B \textrm{ is a block in }A \},$$ the set of block sums in $A$.
\end{notation}
For instance, if $A=(1,\dots,1)$ of length $N$ in $\Z$, then $\hat{A}=[1,N]$ as noted above. In this paper, we initiate the study of the Schur degree of subsets of the form $\hat{A}$ for finite sequences $A$ in $G$, with the hope to shed some light on the basic case $[1,N]$ in $\Z$. Our main result is Theorem~\ref{main thm}, an extension of \eqref{S and R v1} to this context.

\subsection{Minors}

We show here that the association $A \mapsto \hat{A}$ is monotone with respect to taking minors, as defined below.

\begin{definition} Let $A=(a_1,\dots,a_N)$ be a sequence in the abelian group $G$.

\noindent
$\bullet$ An \emph{elementary contraction} of $A$ is any sequence $\overline{A}$ obtained by replacing a block $B$ in $A$ by its sum $\sigma(B)$. That is, if $B=(a_i,\dots,a_j)$ for some $1 \le i \le j \le N$, then
$$
\overline{A} \ = \ (a_1,\dots,a_{i-1},\sigma(B),a_{j+1},\dots,a_N).
$$
\noindent
$\bullet$ A \emph{contraction} of $A$ is any sequence obtained from $A$ by successive elementary contractions.
\end{definition}
For instance, let $A=(1,2,3,4)$. Then $(3,3,4)$, $(6,4)$ and $(3,7)$ are contractions of $A$, the first two ones being elementary. See also~\cite{ABERS}.

\begin{definition} Let $A=(a_1,\dots,a_N)$ be a sequence in $G$. A \emph{minor} of $A$ is either a block $B$ in $A$ or a contraction $\overline{A}$ of $A$.
\end{definition}

\begin{proposition}\label{prop minor} Let $G$ be an abelian group. Let $A$ be a finite sequence in $G$. If $B$ is a minor of $A$, then $\hat{B} \subseteq \hat{A}$.
\end{proposition}
\begin{proof}{}
The stated inclusion clearly holds if $B$ is a block in $A$, since any block sum of $B$ is a block sum of $A$. If $B$ is an elementary contraction of $A$ then again, any block sum of $B$ is a block sum of $A$. Therefore, the same holds if $B$ is obtained from $A$ by successive elementary contractions.
\end{proof}

\subsection{The discrete derivative}
For subsets $X,Y$ of a group $(G,+)$, their \emph{sumset} is $X+Y=\{x+y \mid x \in X, y \in Y\}$. Thus, $X$ is sumfree if and only if $(X+X) \cap X = \emptyset$; equivalently, if and only $(X-X) \cap X = \emptyset$, where $-X=\{-x \mid x \in X\}$.

In this section, for $X \subset \Z$ finite, we relate $X-X$ with a subset of the form $\hat{A}$ for a certain sequence $A$ closely linked to $X$. This is done with a variant of the discrete derivative, associating to a subset $X \subset \Z$ its sequence of successive jumps. See also~\cite{ABERS}.

\begin{definition} Let $X \subset \Z$ be a finite subset. Let the elements of $X$ be $x_0 < x_1 < \dots < x_r$. The \emph{discrete derivative} of $X$ is the sequence
\[
\Delta X \ = \ (x_1-x_0,\  x_2-x_1, \dots, \ x_r-x_{r-1})
\]
of successive jumps in $X$.
\end{definition}

The interesting point for our purposes here is that $X-X$ can be read off from the block sums of $\Delta X$.

\begin{proposition}\label{X-X} Let  $X \subset \Z$ be a nonempty finite subset, and let $A=\Delta X$. Then
$$
\hat{A} = (X-X) \cap \N_+.
$$
\end{proposition}

\begin{proof} Denote by $x_0 < x_1 < \dots < x_r$ the elements of $X$. Then
$$
(X-X) \cap \N_+ \ = \ \{x_t-x_s \mid 0 \le s < t \le r\}.
$$
Let $A = \Delta X = (a_1,\dots,a_r)$, where $a_i = x_i-x_{i-1}$ for $1 \le i \le r$. For any indices $0 \le s < t \le r$, let $B=(a_{s+1},\dots,a_t)$ be the corresponding block in $A$. Then
\begin{equation}\label{sigma B}
x_t-x_s=\sigma(B).
\end{equation}
Indeed, $\sigma(B)=\sum_{i=s+1}^t a_i= \sum_{i=s+1}^t (x_i-x_{i-1})=x_t-x_s$.
Hence $x_t-x_s \in \hat{A}$. This concludes the proof of the proposition.
\end{proof}

The next proposition bounds the Schur degree of certain subsets $\hat{A}$ in $\Z$. We start with a lemma.

\begin{lemma}\label{delta sumfree} Let $X$ be a sumfree subset of $[1, N]$ for some $N\in \N_+$. Let $A=\Delta(X)$. Then $\hat{A} \subseteq [1,N-1] \setminus X$.
\end{lemma}
\begin{proof} Denote $X=\{x_0,\dots,x_n\}$ with $1 \le x_0 < x_1 < \dots < x_n \le N$. Then $A=(a_1,\dots,a_n)$ where $a_i=x_i-x_{i-1}$ for all $1 \le i \le n$. Let $s \in \hat{A}$. Then
$$s=a_i+\dots+a_j =x_j-x_{i-1}$$
for some $1 \le i \le j \le n$. Therefore $1 \le s \le N-1$, and $s \notin X$ since $s+x_{i-1}=x_j$ and $X$ is sumfree. That is, $s \in [1,N-1] \setminus X$, as desired.
\end{proof}

\begin{proposition}\label{prop sdeg} Let $N \ge 1$, and let $X_1 \sqcup \dots \sqcup X_n$ be a sumfree partition of $[1,N]$. Let $A_i=\Delta(X_i)$ for all $i$. Then $\sd(\widehat{A_i}) \le n-1$.
\end{proposition}

\begin{proof}
Let $i \in [1, n]$. It follows from Lemma~\ref{delta sumfree} that $\widehat{A_i}$ is contained in
$$
X_1 \sqcup \dots \sqcup X_{i-1} \sqcup X_{i+1} \sqcup \dots \sqcup X_n.
$$
This induces a partition of $\widehat{A_i}$ into at most $n-1$ sumfree parts.
\end{proof}

\section{Basic properties of the Schur degree}\label{sec schur degree}

In this section, we compute the Schur degree in a few examples after giving its first basic properties. Let us start with the monotonicity of the Schur degree with respect to set inclusion.

\begin{lemma}\label{lem sdeg monotone} Let $G$ be an abelian group. If $X \subseteq Y\subseteq G$ then $\sd(X) \le \sd(Y)$.
\end{lemma}
\begin{proof} Let $n=\sd(Y)$. If $n= \infty$, we are done. Otherwise, $Y$ admits a partition into $n$ sumfree parts, inducing a partition of $X$ into at most $n$ sumfree parts.
\end{proof}
Here is a useful consequence.
\begin{proposition} Let $A$ be a finite sequence in the abelian group $G$. If $B$ is a minor of $A$, then $\sd(\hat{B}) \le \sd(\hat{A})$.
\end{proposition}
\begin{proof}
We have $\hat{B} \subseteq \hat{A}$ by Proposition~\ref{prop minor}. Now apply Lemma~\ref{lem sdeg monotone}.
\end{proof}
Note also that if $A'$ denotes the reverse sequence of $A$, then $\sd(\hat{A})=\sd(\widehat{A'})$. Indeed, $A$ and $A'$ have identical block sums, i.e. $\hat{A}=\widehat{A'}$.

\smallskip
Our next proposition shows that the Schur degree is also monotone with respect to inverse images under group morphisms. We start with a lemma.

\begin{lemma}\label{lemma sumfree} Let $G_1,G_2$ be abelian groups and let $f \colon G_1 \to G_2$ be a morphism. Let $Y \subseteq G_2$. If $Y$ is sumfree then $f^{-1}(Y)$ also is.
\end{lemma}
\begin{proof} Assume that $f^{-1}(Y)$ is not sumfree. Then there exist $x_1,x_2,x_3 \in f^{-1}(Y)$ such that $x_1+x_2-x_3=0$. Hence $f(x_1)+f(x_2)-f(x_3)=0$, implying that $Y$ is not sumfree either.
\end{proof}

\begin{proposition}\label{map} Let $G_1,G_2$ be abelian groups and let $f \colon G_1 \to G_2$ be a morphism. Let $Y \subseteq G_2$. Then $\sd(f^{-1}(Y)) \le \sd(Y)$.
\end{proposition}
\begin{proof}
Let $n=\sd(Y)$. Then there exist sumfree subsets $Y_1, \dots, Y_n \subseteq Y$ such that
$$Y=Y_1 \sqcup\dots\sqcup Y_n.$$
Therefore $f^{-1}(Y)=f^{-1}(Y_1)\sqcup\dots\sqcup f^{-1}(Y_n)$, and $f^{-1}(Y_i)$ is sumfree for all $i$ by Lemma \ref{lemma sumfree}. Hence $\sd(f^{-1}(Y))\le n$.
\end{proof}

\subsection{Examples}
As an illustration, we determine the Schur degree of a few selected subsets of $\Z$. In some cases, the results were obtained using specially written functions in \emph{Mathematica 10}~\cite{W}.

\begin{example} Let $B=[1,2] \cup [m,m+4]$. We claim that
$$
\sd(B) = 3
$$
for all $m \ge 3$. Indeed, let $A=(1,1,m,1,1)$. Then $\hat{A}=B$, and $\sd(\hat{A}) \ge 3$ by Corollary~\ref{length 5} in the next section. Equality is obvious here.
\end{example}

\begin{example}\label{powers of 2}
Let $A = (2^i)_{0 \le i \le 13}$.
Then here also, $\sd(\hat{A})=3$. But with one more term, i.e. for $B = (2^i)_{0 \le i \le 14}$, it is no longer the case as $\sd(\hat{B})=4$.
\end{example}

\begin{example}
This example is an application of Proposition~\ref{map}. Let $x,y$ be positive integers, and let $A=(x,y,\dots,x,y)$ be the $2$-periodic sequence of length $14$. Then $\sd(\hat{A} \setminus \{7x+7y\})=3$. Indeed, here are three sumfree classes covering that set:
\begin{align*}
C_1: &\,\,\, x,\, y,\, 2x+2y,\, 5x+5y,\, 7x+6y,\, 6x+7y. \\
C_2: &\,\,\, x+y,\, 2x+y,\, x+2y,\, 6x+5y,\, 5x+6y,\, 6x+6y.  \\
C_3: &\,\,\, 3x+2y,\, 2x+3y,\, 3x+3y,\, 4x+3y,\, 3x+4y,\, 4x+4y,\, 5x+4y,\, 4x+5y.
\end{align*}

Mapping $x,y$ to $1$ yields a sumfree $3$-partition of $[1,13]$. In fact, the partition $C_1,C_2,C_3$ was constructed to do exactly that, using Proposition~\ref{map}.
\end{example}

\begin{example}\label{ex [1,6]}
For each integer $x \ge 8$, one has
$$
\sd([1,6] \cup [x,x+13]) = 3.
$$
Indeed, this is shown by the following sumfree $3$-partition of this set:
\begin{align*}
C_1: &\,\,\,\, 1,6,x,x+3,x+7,x+10. \\
C_2: &\,\,\,\, 2,5,x+1,x+2,x+8,x+9.  \\
C_3: &\,\,\,\, 3,4,x+4,x+5,x+6,x+11,x+12,x+13.
\end{align*}
However, adjoining $7$ to it, one has $\sd([1,7] \cup [x,x+13]) = 4$.
\end{example}

\begin{example}
Let $G$ be an abelian group containing $\Z$ and let $x \in G \setminus \Z$. Then
\begin{eqnarray*}
\sd(\{1,2\} \cup [x,x+3]) & = & 2, \\
\sd(\{1,2\} \cup [x,x+4]) & = & 3.
\end{eqnarray*}
Indeed, as easily seen, the \emph{only} sumfree $2$-coloring of $\{1,2\} \cup [x,x+3]$ is given by the two color classes $\{1,x,x+3\}$ and $\{2,x+1,x+2\}$. Hence, it is impossible to add $x+4$ to either class while maintaining the sumfree property.
\end{example}

\begin{example}
Let $G$ be an abelian group containing $\Z$. Let $x \in G \setminus \Z$ be such that $\{1,x\}$ is $\Z$-free, i.e. spans a free-abelian subgroup of rank $2$ of $G$. Then
$$
\sd([1,6] \cup (x+\N)) = 3.
$$
Indeed, consider the $3$-partition of Example~\ref{ex [1,6]} and extend it periodically as follows:
\begin{align*}
C_1: &\,\,\,\, 1,6,x,x+3,x+7,x+10, x+14,x+17,\dots \\
C_2: &\,\,\,\, 2,5,x+1,x+2,x+8,x+9,x+15,x+16,\dots  \\
C_3: &\,\,\,\, 3,4,x+4,x+5,x+6,x+11,x+12,x+13,x+18,x+19,x+20,\dots
\end{align*}
One can also extend it towards the left. Thus in fact, $\sd([1,6] \cup (x+\Z)) = 3$. But here again, adjoining $7$ to it, one has $\sd([1,7] \cup (x+\Z))=4$.
\end{example}

\section{Comparison with $R_n(3)$}\label{sec comparison}

Recall that, for $n \ge 1$, the Ramsey number $R_n(3)$ denotes the smallest $N$ such that, for any $n$-coloring of the edges of the complete graph $K_N$, there is a monochromatic triangle. There is a well known relationship between the Schur and the  Ramsey numbers, namely
\begin{equation}\label{bound on S}
S(n) \le R_n(3)-2.
\end{equation}
Using the Schur degree of $[1,N]$, this may be expressed as follows:
$$
N \ge R_{n}(3)-1 \, \Longrightarrow \, \sd([1,N]) \ge n+1.
$$
Theorem~\ref{main thm} below extends this relationship to the Schur degree of $\hat{A}$ for any finite sequence $A$ in an abelian group.

\begin{theorem}\label{main thm} Let $G$ be an abelian group. Let $A$ be a finite sequence in $G$. If $|A|\ge R_n(3)-1$ then $\sd(\hat{A}) \ge n+1$.
\end{theorem}

\begin{proof} Let $N=|A| \ge R_n(3)-1$. Denote $b(i,j)=x_i+ \dots +x_{j-1}$ for all $1 \le i < j \le N+1$. Then
$$\hat{A}=\{b(i,j) \mid 1 \le i < j \le N+1\}.$$
Let $\chi \colon \hat{A} \to [1,n]$ be an arbitrary $n$-coloring of $\hat{A}$. Consider the complete graph $K_{N+1}=(V,E)$ on the vertex set $V=[1, N+1]$. Then $\chi$ induces an $n$-coloring $\chi' \colon E \to [1,n]$ on $E$
defined by
$$\chi'(\{i,j\}) = \chi(b(i,j))$$
for all $1 \le i < j \le N+1$. Since $N+1 \ge R_n(3)$, there is a monochromatic triangle under $\chi'$ in $K_{N+1}$, say with vertices $i, j, h$ for some $1 \le i < j  <h \le N+1$. This yields, under $\chi$, the monochromatic subset
$$\{b(i,j), b(j,h), b(i,h)\} \subset \hat{A}.$$
Since $b(i,j)+b(j,h)=b(i,h)$, the corresponding color class in $\hat{A}$ is not sumfree. Since $\chi$ was an arbitrary $n$-coloring of $\hat{A}$, we conclude that $\sd(\hat{A}) \ge n+1$.
\end{proof}

In particular, for $n=2$, $3$ and $4$, one has the following consequences.

\begin{corollary}\label{length 5} Let $A$ be a sequence in an abelian group $G$. If $|A|\ge 5$, then $\sd(\hat{A}) \ge 3$. If $|A|\ge 16$, then $\sd(\hat{A}) \ge 4$. If $|A|\ge 61$, then $\sd(\hat{A}) \ge 5$.
\end{corollary}

\begin{proof}
Follows from Theorem~\ref{main thm} and the well-known values $R_2(3) = 6$, $R_3(3) = 17$ and current upper bound $R_4(3) \le 62$.
\end{proof}

The converse of Theorem~\ref{main thm} does not hold in general. For instance, for $n=3$ and $A=(1,\dots,1)$ of length $14$ in $\Z$, by \eqref{eq schur} we have $\sd(\hat{A}) \ge 4$ since $\hat{A}=[1,14]$ and $S(3)=13$, yet $|A| \le R_3(3)-2=15$. However, here is a partial converse showing that Theorem~\ref{main thm} is best possible. First observe that if $|A|=N$, then
$$|\hat{A}| \le 1+2+\cdots+N=\binom{N+1}2.$$
The case of equality, where all block sums in $A$ are pairwise distinct, is of interest. It occurs for instance if $A$ is \emph{$\Z$-free}, i.e. generates a subgroup isomorphic to $\Z^N$.

\begin{theorem}\label{thm converse} Let $A$ be a finite sequence in an abelian group $G$. If $|A| \le R_n(3)-2$ and $A$ is $\Z$-free, then $\sd(\hat{A}) \le n$.
\end{theorem}
\begin{proof} Denote $A = \{x_1,\dots,x_N\}$. Reusing the notation introduced in the proof of Theorem~\ref{main thm}, we have
$$\hat{A}=\{b(i,j) \mid 1 \le i < j \le N+1\}.$$
Again, let $K_{N+1}=(V,E)$ be the complete graph on the vertex set $V=[1, N+1]$. Consider the map $f \colon E \to \hat{A}$
defined by
\begin{equation}\label{map f}
f(\{i,j\}) = b(i,j)
\end{equation}
for all $1 \le i < j \le N+1$. Since $|E|=|\hat{A}|$ and the $b(i,j)$ are pairwise distinct by assumption, the map $f$ is a \emph{bijection}. Since $N+1 \le R_n(3)-1$, there is an $n$-coloring $\chi \colon E \to [1,n]$ without any monochromatic triangle. Consider the composed map
$$
\chi \circ f^{-1} \colon \hat{A} \longrightarrow [1,n].
$$
We claim that  under this $n$-coloring of $\hat{A}$, every color class is sumfree. Indeed, let $u_1,u_2,u_3$ be any triple in $\hat{A}$ satisfying $u_1+u_2=u_3$. We claim that it cannot be monochromatic under $\chi \circ f^{-1}$. We have $u_1=b(i_1,j_1)$, $u_2=b(i_2,j_2)$, $u_3=b(i_3,j_3)$ for some indices $i_1 <j_1$, $i_2 <j_2$, $i_3 <j_3$ in $[1,N+1]$. The relation $u_1+u_2=u_3$ then becomes
$$
(x_{i_1}+\cdots+x_{j_1-1})+(x_{i_2}+\cdots+x_{j_2-1})=(x_{i_3}+\cdots+x_{j_3-1}).
$$
We may freely assume $i_1 \le i_2$. Since the sequence $x_1,\dots,x_N$ is $\Z$-free by hypothesis, the above equality is only possible if $i_1=i_3$, $j_1=i_2$ and $j_2=j_3$. That is, if the three edges $\{i_1,j_1\}$, $\{i_2,j_2\}$, $\{i_3,j_3\}$ form a triangle in $K_{N+1}$. Since that triangle is not monochromatic under $\chi$, the triple $u_1,u_2,u_3=u_1+u_2$ in $\hat{A}$ is not monochromatic under $\chi \circ f^{-1}$ either, since $f^{-1}(u_k)=\{i_k,j_k\}$ for $k=1, 2, 3$ by \eqref{map f}. Hence $\sd(\hat{A}) \le n$, as claimed.
\end{proof}

\begin{remark} The hypothesis that $A$ be $\Z$-free is not strictly needed in Theorem~\ref{thm converse}. For instance, let $A=(1,3, 3^2,\dots,3^{N-1})$. Even though $A$ is not $\Z$-free, it is still true that if $N \le R_n(3)-2$ then $\sd(\hat{A}) \le n$. This derives from the above proof and the fact that the only triples $u,v,u+v$ in $\hat{A}$ are those of the form $b(i,j),b(j,h),b(i,h)$.
\end{remark}

\section{A recursive upper bound on $S(n)$?}\label{sec conjectures}

The Ramsey numbers admit well-known recursive upper bounds, including
\begin{equation}\label{ramsey bound}
R_n(3) \le n(R_{n-1}(3)-1)+2
\end{equation}
\cite[Theorem 6, p. 6]{GG}. To the best of our knowledge, no recursive upper bounds are known yet for the Schur numbers. We propose here a conjecture which, if true, would fill this gap. Let us start with an upper bound on $S(n)$ involving the number $L(n)$ defined below.

\begin{definition} Let $n \ge 2$. We define $L(n)$ to be the smallest positive integer with the following property: for every sequence $A$ in $\N_+$ of length $|A| = L(n)$ and average $\mu(A) \le n$, one has $\sd(\hat{A}) \ge n$.
\end{definition}

\begin{example}\label{n=2} Let $n=2$. Then $L(2)=2$. Indeed, up to symmetry, the only sequences $A$ to consider are $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$. This yields $\hat{A}=\{1,2\}$, $\{1,2,3\}$, $\{1,3,4\}$, $\{2,4\}$, respectively. As none is sumfree, we have $\sd(\hat{A}) \ge 2$ in all cases, as required.
\end{example}

Let us now establish the existence of $L(n)$ in full generality.
\begin{proposition}\label{prop L exists} For all $n\ge 2$, the number $L(n)$ exists and satisfies
\begin{equation}\label{L}
S(n-1)+1 \: \le\: L(n) \: \le\: R_{n-1}(3)-1.
\end{equation}
\end{proposition}

\begin{proof} If $A$ is any sequence in $\N_+$ of length $|A| = R_{n-1}(3)-1$, then irrespective of its average $\mu(A)$, we have $\sd(\hat{A}) \ge n$ by Theorem~\ref{main thm}, as desired. Thus $L(n)$ exists and is bounded above by $R_{n-1}(3)-1$. On the other hand, let $A=(1,\dots,1)$ of length $L(n)$ and average $\mu(A)=1$. Then $\hat{A}=[1,L(n)]$, whence $\sd([1,L(n)]) \ge n$ by hypothesis. Hence $L(n)  \ge S(n-1)+1$, by definition of $S(n-1)$.
\end{proof}

Here is our upper bound on $S(n)$ involving $L(n)$.
\begin{theorem}\label{conditional} We have $S(n) \le n L(n)$ for all $n \ge 2$.
\end{theorem}

\begin{proof}
We claim that $[1,nL(n)+1]$ has Schur degree at least $n+1$. This will imply $nL(n)+1 \ge S(n)+1$, the desired conclusion. Assume for a contradiction that $nL(n)+1 \le S(n)$. Let then
\begin{equation}\label{partition}
[1,nL(n)+1] = X_1 \sqcup \dots \sqcup X_n
\end{equation}
be a sumfree partition. By the pigeonhole principle, one of the $X_i$'s has cardinality at least $L(n)+1$, say $|X_1| \ge L(n)+1$. Let $A=\Delta(X_1)$. Then $|A| \ge L(n)$, and $\sd(\hat{A}) \le n-1$ by Proposition~\ref{prop sdeg}. Let $B$ be a block of $A$ of length $|B|=L(n)$. Since $B$ is a minor of $A$, Proposition~\ref{prop minor} implies
\begin{equation}\label{sdeg B}
\sd(\hat{B}) \le \sd(\hat{A}) \le n-1.
\end{equation}
Let $s=\min(X_1)$, $t=\max(X_1)$. Then $\sigma(A) = t-s$ by~\eqref{sigma B}, and $t-s \le nL(n)$ since $X_1 \subseteq [1,nL(n)+1]$ by~\eqref{partition}. Hence $\sigma(B) \le nL(n)$ and so $\mu(B) = \sigma(B)/L(n) \le n.$ Since $|B|=L(n)$, the defining property of $L(n)$ implies $\sd(\hat{B}) \ge n$, contradicting~\eqref{sdeg B}. This concludes the proof of the theorem.
\end{proof}

\begin{remark}
Proposition~\ref{prop L exists} and Theorem~\ref{conditional} imply the upper bound $$S(n) \le n(R_{n-1}(3)-1)$$
for all $n \ge 2$. However, this also follows by combining \eqref{bound on S} and \eqref{ramsey bound}, namely $S(n) \le R_n(3)-2$ and $R_n(3) \le n(R_{n-1}(3)-1)+2$.
\end{remark}

\subsection{Conjectures}

Given $n \ge 2$, what is the exact value of $L(n)$? It follows from Proposition~\ref{prop L exists} that
\begin{equation}\label{if S+1= R-1}
\textit{ if }\ S(n-1)+1=R_{n-1}(3)-1 \ \textit{ then } \  L(n)=S(n-1)+1.
\end{equation}
This occurs for $n=2$ and $3$, since by~\eqref{schur numbers} and~\eqref{ramsey numbers}, we have $(S(1),R_1(3))=(1,3)$ and $(S(2),R_2(3))=(4,6)$. Thus $L(2)=2$ as already seen, and $L(3)=5$. As for $n=4$, we have
$$
(S(3),R_3(3))=(13,17).
$$
Proposition~\ref{prop L exists} then implies
$
14 \le L(4) \le 16.
$
We conjecture that $L(4)=14$ and, more generally, that the lower bound on $L(n)$ in~\eqref{L} is optimal.

\begin{conjecture}\label{conj1} Let $n \ge 2$. Then $L(n)=S(n-1)+1$. That is, every sequence $A$ in $\N_+$ of length $|A|=S(n-1)+1$ and average $\mu(A) \le n$ satisfies \emph{$\sd(\hat{A}) \ge n$}.
\end{conjecture}

As shown below, this has very interesting consequences for the Schur numbers themselves.

\smallskip
We have seen above that Conjecture~\ref{conj1} holds for $n=2$ and $3$. Does it hold for $n=4$? That is, is it true that for any sequence $A$ in $\N_+$ of length $14$ and average $\mu(A) \le 4$, one has \emph{$\sd(\hat{A}) \ge 4$}? We do not know yet. In any case, some hypothesis bounding $\mu(A)$ from above cannot be completely dispensed of. For instance, consider the sequence
$$
A=(23,375,23,209,209,60,60,60,23,1,60,261,209,23)
$$
of length $14$. Then $|\hat{A}|=83$, and $\sd(\hat{A})=3$ as can be verified.

But this does not contradict Conjecture~\ref{conj1} for $n=4$, since $\mu(A) =114$ here. Such exotic examples in length $14$ are hard to come by. This one was found with a semi-random search by computer. See also Example~\ref{powers of 2} with the powers of $2$, also of length $14$ but with a still higher average.

\medskip Here is a worthwhile consequence of Conjecture~\ref{conj1} for the Schur numbers, potentially the first known recursive upper bound for them.

\begin{conjecture}\label{conj2} $S(n) \le n(S(n-1)+1)$ for all $n \ge 2$.
\end{conjecture}

This directly follows from Theorem~\ref{conditional} and Conjecture~\ref{conj1}. Table~\ref{tab} shows that Conjecture~\ref{conj2} actually holds for $2 \le n \le 5$.

\medskip
\begin{table}[h!]
\centering
\begin{tabular}{|c||c|c|}
\hline
$n$ & $S(n)$ & $n(S(n-1)+1)$ \\
\hline \hline
1 & 1 &  \\
\hline \hline
2 & 4 & 4 \\
\hline \hline
3 & 13 & 15 \\
\hline \hline
4 & 44 & 56 \\
\hline \hline
5 & 160 & 225 \\
\hline
\end{tabular}
\caption{$S(n) \le n(S(n-1)+1)$ for $2 \le n \le 5$}
\label{tab}
\end{table}

\subsection{Comparisons}\label{sec comparisons}
Let us now compare this conjectural upper bound on $S(n)$ with the general currently known ones given by \eqref{bound on S} and \eqref{ramsey bound}, namely
\begin{equation}\label{S and R}
S(n) \le R_n(3)-2, \quad R_n(3) \le n(R_{n-1}(3)-1)+2.
\end{equation}

The currently known bounds on $R_4(3)$ are $51 \le R_4(3) \le 62$, established in \cite{Ch} and \cite{FKR}, respectively. Starting with $R_4(3) \le 62$, the bounds~\eqref{S and R} yield
$$
S(5) \le R_5(3)-2 \le 305, \quad S(6) \le R_6(3)-2 \le 1836.
$$

$\bullet$  For $n=4$, the equality $S(4)=44$ was established by computer~\cite{baumert}. But, as far as theory is concerned, nothing better than $S(4) \le R_4(3)-2 \le 60$ is currently known. A proof of Conjecture~\ref{conj1} for $n=4$ would yield $S(4) \le 56$, still far away from the true value $44$, yet a little closer to it.

\smallskip
$\bullet$ For $n=5$, the bound $S(5) \ge 160$ was first established in~\cite{exoo}, with  equality later conjectured to hold in \cite{FS}. Inded, the exact value $S(5)=160$ has recently been established by massive computer calculations with a certified SAT solver~\cite{heule}. A proof of Conjecture~\ref{conj1} for $n=5$, namely that every sequence $A$ in $\N_+$ such that $|A|=45$ and $\mu(A) \le 5$ satisfies $\sd(\hat{A}) \ge 5$, would imply $S(5) \le 225$. Here again, it would still be far away from the true value, yet it would provide a marked improvement over the currently best known theoretical upper bound $S(5) \le 305$.

\smallskip
$\bullet$ For $n=6$, on the one hand we have $S(6) \ge 536$ by~\cite{FS}, while at the time of writing, the best known upper bound is again the one given above, namely
$$
S(6) \le R_6(3)-2 \le 1836.
$$
By sharp contrast, using the true value $S(5)=160$, Conjecture~\ref{conj2} implies the following substantial improvement.

\begin{conjecture}\label{conj3} $S(6) \le 966$.
\end{conjecture}

$\bullet$  As for $n=7$, Conjectures~\ref{conj2} and~\ref{conj3} yield the conjectural upper bound $$S(7) \le 6769,$$ to be compared with the known ones given by~\eqref{S and R}, namely $S(7) \le R_7(3) \le 12861$. For a lower bound, the best we currently have is $S(7) \ge 1680$, by~\cite{FS} again.

\small

config: arxiv


TITLE: What Numerical Methods Are Known to Solve $ {L}_{1} $ Regularized Quadratic Programming Problems?
QUESTION [9 upvotes]: What numerical methods are suitable to solve the following problem
$$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$
where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive definite, and $\lambda\in\mathbf{R}$ is positive?
Typically this problem arises in L1-regularized regression problems (e.g. LASSO) but the common method to solve that (LARS) requires that you can compute regression residuals, which you can't in this case.
Are there standard tools (open source or commercial) that can solve problems like this?

REPLY [3 votes]: CVX (MATLAB) or CVXPY (Python) would allow you to solve that really easily, as long as your problem isn't too large.
The CVX code would be just:
cvx_begin
    variable x(n)
    minimize( 1/2*quad_form(x,A) + b'*x + lambda*norm(x,1) )
cvx_end


text:
\begin{document}

\title[Stress matrices and global rigidity of frameworks on surfaces]{Stress matrices and global rigidity of frameworks on surfaces}
\author[B. Jackson]{B. Jackson}
\address{School of Mathematical Sciences\\ Queen Mary, University of London\\
E1 4NS \\ U.K. }
\email{b.jackson@qmul.ac.uk}
\author[A. Nixon]{A. Nixon}
\address{Department of Mathematics and Statistics\\ Lancaster University\\
LA1 4YF \\ U.K. }
\email{a.nixon@lancaster.ac.uk}
\date{\today}

\begin{abstract}
In 2005, Bob Connelly showed that a generic framework in $\bR^d$ is
globally rigid if it has a stress matrix of maximum possible rank,
and that this sufficient condition for generic global rigidity is
preserved by the 1-extension operation. His results gave a key step
in the characterisation of generic global rigidity in the plane. We
extend these results to frameworks on surfaces in $\bR^3$. For a
framework on a family of concentric cylinders, cones or ellipsoids,
we show that there is a natural surface stress matrix arising from
assigning edge and vertex weights to the framework, in equilibrium
at each vertex.  In the case of cylinders and ellipsoids,
we show that  having a maximum rank stress matrix is
sufficient to guarantee generic global rigidity on the surface. We
then show that this sufficient condition for generic global rigidity is preserved under 1-extension and use this to
make progress on the problem of characterising generic global
rigidity on the cylinder.
\end{abstract}

\maketitle

\section{Introduction}

A bar-joint framework $(G,p)$ in $d$-dimensional Euclidean space $\bR^d$ is a realisation of a (simple) graph $G=(V,E)$, via a map $p:V\to \bR^d$, with vertices considered as universal joints and edges as fixed length bars. A framework $(G,p)$ is \emph{rigid} if the only continuous motions of the vertices in $\bR^d$ that preserve

the edge lengths, arise from isometries of $\bR^d$.
More strongly, $(G,p)$ is \emph{globally rigid} in $\bR^d$ if every realisation $(G,q)$ with the same edge lengths as $(G,p)$ arises from an isometry of $\bR^d$. We refer the reader to  \cite{Wlong} for more information on rigidity and its applications.

It is NP-hard to determine if an arbitrary framework is rigid \cite{Abb} or globally rigid \cite{Sax}. These problems become more tractable if we restrict to generic frameworks, for which rigidity and global rigidity can be determined in polynomial time when $d=1,2$.
It remains a difficult open problem to characterise, in an efficient combinatorial way, when a $3$-dimensional generic
framework is rigid or globally rigid.

Results have recently been obtained concerning the rigidity and global rigidity of frameworks in $\bR^3$ that are constrained to lie on a fixed surface \cite{JMN,NOP,NOP2}. In this paper we obtain a natural sufficient condition for such a framework to be globally rigid.

We first recall

some fundamental results about the generic (global) rigidity of bar-joint frameworks in Euclidean space.

A graph $G=(V,E)$ is \emph{$(2,k)$-sparse} if for every subgraph
$G'=(V',E')$, with at least one edge, the inequality $|E'|\leq
2|V'|-k$ holds. Moreover $G$ is \emph{$(2,k)$-tight} if $|E|=2|V|-k$
and $G$ is $(2,k)$-sparse. While the definitions of {$(2,k)$-sparse}
and {$(2,k)$-tight} make sense for graphs with multiple edges and
loops, such edges are of no use when considering rigidity so we will
restrict our attention to simple graphs.

\begin{thm}[\cite{Lam}]\label{thm:Laman}
A generic framework $(G,p)$ in $\bR^2$ is

rigid if and only if $G$ contains a spanning $(2,3)$-tight subgraph.
\end{thm}

A framework $(G,p)$ is said to be {\em redundantly rigid} if
$(G-e,p)$ is rigid for all edges $e$ of $G$.

\begin{thm}[\cite{C2005,J&J}]\label{thm:2dcomb}
A generic framework  $(G,p)$ in $\bR^2$ is globally rigid if and only if $G$ is a complete graph on at most three vertices or $(G,p)$ is redundantly rigid and $G$ is $3$-connected.
\end{thm}

Hendrickson \cite{Hdk} had previously shown that $(d+1)$-connectivity and redundant rigidity are necessary conditions for generic global rigidity in $\bR^d$
for all $d$. Examples constructed by Connelly \cite{C91} show that they are not sufficient to imply generic global rigidity when $d\geq 3$.
Connelly also obtained a different kind of sufficient condition for generic global rigidity in terms of `stress matrices' (which will be defined in Section \ref{sec:stress}).

\begin{thm}[\cite{C2005}]\label{thm:Consufficiency}
Let $(G,p)$ be a generic framework in $\bR^d$ with $n\geq d+2$ vertices. Suppose that $(G,p)$ has an equilibrium stress $\omega$ whose associated stress matrix $\Omega$ has
rank $n-d-1$. Then $(G,p)$ is globally rigid in $\bR^d$.
\end{thm}

Gortler, Healy and Thurston \cite{GHT} have shown that Connelly's sufficient condition for generic global rigidity is also a necessary condition. This characterization implies that generic global rigidity depends only on the underlying graph (but does not give rise to a polynomial algorithm for deciding which graphs are generically globally rigid in $\bR^d$).

In this paper we develop natural analogues of an equilibrium  stress and a stress
matrix for frameworks constrained to lie on a surface. Our main result is an analogue of Theorem \ref{thm:Consufficiency}, giving a sufficient condition for generic frameworks on families of concentric cylinders

and ellipsoids to be globally rigid.

We conclude the introduction by giving a short outline of what follows.
Section \ref{sec:surf} recalls basic definitions and results for frameworks on surfaces.

We describe the rigidity map and rigidity matrix for surfaces in Section \ref{sec:gen}. In Section \ref{sec:stress} we develop basic properties of stresses, stress matrices and energy functions for frameworks on surfaces.

Section \ref{sec:main} contains our main result, Theorem \ref{thm:global}, an analogue of Theorem \ref{thm:Consufficiency} for generic frameworks on cylinders and ellipsoids. We use this result in Section \ref{sec:1ext} to show that the property of having a maximum rank surface stress matrix is preserved by 1-extensions on these surfaces. We finish by applying our results to make some progress on the problem of characterising generic global rigidity on the cylinder.

\section{Frameworks on Surfaces}\label{sec:surf}

It was shown in \cite{NOP} that the rigidity of a generic framework on a surface depends crucially  on the number of continuous isometries of $\bR^3$ admitted by the surface, see Theorems \ref{thm:cylinderlaman}, \ref{thm:conelaman} and \ref{thm:surfacerank} below. Since generic rigidity and global rigidity on the plane and sphere \cite{C&W}, the surfaces with 3-dimensional isometry groups, are now well understood,  we consider cylinders, cones and ellipsoids as natural examples of surfaces with $2$, $1$ and $0$-dimensional isometry groups, respectively.

Let $r=(r_1,r_2,\dots, r_n)$ be a vector of (not necessarily distinct) positive real numbers. For $1\leq i \leq n$, let

$\Y_i=\{(x,y,z) \in \bR^3:x^2+y^2=r_i\}$, $\C_i=\{(x,y,z) \in \bR^3:x^2+y^2=r_iz^2\}$ and $\E_i=\{(x,y,z) \in \bR^3:x^2+\alpha y^2+\beta z^2=r_i\}$ for some fixed $\alpha,\beta \in \bQ$ with $1 < \alpha < \beta$. Let

$\Y=\bigcup_{i=1}^n\Y_i$, $\C=\bigcup_{i=1}^n\C_i$ and $\E=\bigcup_{i=1}^n\E_i$.

We will use $\F=\bigcup_{i=1}^n \F_i$ to denote one of the three surfaces $\Y,\C,\E$,  and $\ell$ for the dimension of its space of infinitesimal isometries (so $\ell=2,1$ or $0$ when $\F=\Y,\C$ or $\E$, respectively). We will occasionally use $\F(r)$ when we wish to specify a particular vector $r$ and $\F(1)$ for the special case when $r_1=r_2=\dots = r_n$ (there is no loss in generality  in assuming that $r_i=1$ for all $1\leq i\leq n$ when the $r_i$ are all equal).

A {\em framework on $\F$} is a pair $(G,p)$ where $G=(V,E)$ is a
graph with $V=\{v_1,v_2,\ldots,v_n\}$, and $p:V\to \bR^3$ with
$p(v_i)\in \F_i$ for all $1\leq i\leq n$. Two frameworks $(G,p)$ and
$(G,q)$ on $\F$ are \emph{equivalent}  if
$\|p(v_i)-p(v_j)\|=\|q(v_i)-q(v_j)\|$ for all $v_iv_j \in E$ and
\emph{congruent}  if $\|p(v_i)-p(v_j)\|=\|q(v_i)-q(v_j)\|$ for all
$v_i,v_j \in V$. The framework $(G,p)$ is \emph{globally rigid on $\F$} if every
framework $(G,q)$ on $\F$ which is equivalent to $(G,p)$ is
congruent to $(G,p)$.
We say that $(G,p)$ is \emph{rigid on $\F$} if
there exists an $\epsilon>0$ such that every framework $(G,q)$ on
$\F$ which is equivalent to $(G,p)$, and has
$\|p(v_i)-q(v_i)\|<\epsilon$ for all $1\leq i\leq n$, is congruent
to $(G,p)$. (This is equivalent to saying that every continuous
motion of the vertices that stays on $\F$ and preserves equivalence
also preserves congruence). If $(G,p)$ is not rigid on $\F$ then
$(G,p)$ is said to be \emph{flexible on $\F$}. The framework $(G,p)$
is \emph{minimally rigid on $\F$} if it is rigid and, for every edge $e\in
E$,  $(G-e,p)$ is flexible on $\F$. It is \emph{redundantly rigid on
$\F$} if $(G-e,p)$ is rigid on $\F$  for all $e\in E$.

An \textit{infinitesimal flex} $s$ of $(G, p)$ on $\F$ is a map
$s:V\to \bR^3$ such that $s(v)$ is tangential to $\F$ at $p(v)$ for
all $v\in V$ and $(p(u)-p(v))\cdot(s(u)-s(v))=0$ for all $uv\in E$.
The framework $(G,p)$ is \emph{infinitesimally rigid} on $\F$ if
every infinitesimal flex $s$ of $(G,p)$ satisfies
$(p(u)-p(v))\cdot(s(u)-s(v))=0$ for all $u,v\in V$.

We consider a framework $(G,p)$ on $\F=\F(r)$ to be \emph{generic} if $\td[\bQ(r,p):\bQ(r)]=2|V|$, where $\td[\bQ(r,p):\bQ(r)]$ denotes the transcendence degree of the field extension. Thus  $(G,p)$ is generic on $\F$ if the coordinates of the vertices of $G$ are as algebraically independent as possible.
The following results characterise when a generic framework on $\Y$
or $\C(1)$ is minimally rigid.

\begin{thm}[\cite{NOP}]\label{thm:cylinderlaman}
Let $(G,p)$ be a generic framework on $\Y$. Then $(G,p)$ is
minimally rigid if and only if $G$ is a complete graph on at most
three vertices or $G$ is $(2,2)$-tight.
\end{thm}

\begin{thm}[\cite{NOP2}]\label{thm:conelaman}
Let $(G,p)$ be a generic framework on $\C(1)$. Then $(G,p)$ is
minimally rigid if and only if $G$ is  a complete graph on at most
four vertices or $G$ is $(2,1)$-tight.
\end{thm}

 It remains an open problem to characterise generic minimally rigid frameworks on $\E$. (The natural analogue of the above theorems is known to be false.)

The final result of this section gives necessary conditions for generic global rigidity of frameworks on $\F$ which are analogous to Hendrickson's conditions for $\bR^d$.

\begin{thm}[\cite{JMN}]\label{thm:redundant}
Suppose $(G,p)$ is a generic globally rigid framework on $\F$ with $n\geq 7-\ell$ vertices.

Then $(G,p)$ is redundantly rigid on $\F$, and $G$ is k-connected,
where $k=2$ if $\F\in \{\Y,\C\}$ and $k=1$ if $\F=\E$.
\end{thm}

We believe that these necessary conditions for generic global rigidity are also sufficient when $\F\in \{\Y,\C\}$, see \cite[Conjecture $9.1$]{JMN}. One motivation for the current paper is to try to verify this conjecture by using the same proof technique as Theorem \ref{thm:2dcomb}. We will return to this in Section
\ref{sec:cyl}.

\section{The Rigidity Map}
\label{sec:gen}

We assume henceforth that $G=(V,E)$ is a graph with $V=\{v_1,v_2,\ldots,v_n\}$ and $E=\{e_1,e_2,\ldots,e_m\}$.

The {\em rigidity map} $F^G:\bR^{3n}\rightarrow \bR^m$ is defined by $F^G(p)=(\|e_1 \|^2, \dots, \|e_m\|^2)$ where $\|e_i\|^2=\|p(v_j)-p(v_k)\|^2$
when $e_i=v_jv_k$. Its differential at
the point $p$ is the map  $dF^G_p:\bR^{3n}\rightarrow \bR^m$ defined
by $dF^G_p(q)=2R(G,p)\cdot q$ where $R(G,p)$ is
 the $|E|\times 3|V|$ matrix  with rows indexed by $E$ and 3-tuples of columns indexed by $V$ in which, for
$e=v_iv_j\in E$, the submatrices in row $e$ and columns $v_i$ and $v_j$ are $p(v_i)-p(v_j)$ and  $p(v_j)-p(v_i)$, respectively, and
all other entries are zero.
We refer to $R(G,p)$ as the {\em rigidity matrix} for $(G,p)$.

We next define a rigidity map and matrix for a framework $(G,p)$ constrained to lie on our surface $\F$.
Let $\Theta^\F:\bR^{3n}\rightarrow \bR^n$ be the map defined by $\Theta^\F(p)=(h_1(p(v_1)),\dots, h_n(p(v_n)))$ where, for each $1 \leq i\leq n$,
\begin{equation}\label{eqn:surface}
h_i(x,y,z)= \begin{cases}
 x^2+y^2-r_i, & \text{if }\F=\Y(r_1,r_2,\ldots,r_n); \\
 x^2+y^2-r_iz^2, & \text{if }\F=\C(r_1,r_2,\ldots,r_n); \\
  x^2+\alpha y^2+\beta z^2-r_i, & \text{if }\F=\E(\alpha,\beta,r_1,r_2,\ldots,r_n).
\end{cases}
\end{equation}
Then the differential of $\Theta^\F$ at the
point $p$ is the map  $d\Theta^\F_p:\bR^{3n}\rightarrow \bR^n$ defined by
$d\Theta^\F_p(q)=2S(G,p)\cdot q$ where
\[ S(G,p) = \begin{bmatrix} s_1 & 0 & \dots  &0  \\  0 & s_2 & \dots &0  \\ \vdots && \ddots & \vdots\\ 0 & 0 & \dots & s_n \end{bmatrix},
\]
$s_i=s_i(p(v_i))$
and
\begin{equation}\label{eq:si}
s_i(x,y,z)= \begin{cases}
 (x,y,0), & \text{if } \F=\Y; \\

 (x,y,-r_iz), & \text{if }\F=\C;\\
 (x,\alpha y,\beta z), & \text{if }\F=\E.
\end{cases}
\end{equation}

It follows that $\rank d\Theta^\F_p=n$ if $p\in \W=\F_1\times\F_2\times\ldots\times\F_n$ and $p(v_i)\neq (0,0,0)$ for all $1\leq i \leq n$. Hence $p\in \W$ is a regular point of $\Theta^\F$ unless $\F=\C$ and $p(v_i)= (0,0,0)$ for some $1\leq i \leq n$.

The
{\em $\F$-rigidity map} $F^{G,\F}:\bR^{3n}\rightarrow \bR^{m+n}$ is defined by $F^{G,\F}=(F^G,\Theta^\F)$.
The {\em rigidity matrix}
$$R_{\F}(G,p)=\begin{bmatrix}R(G,p) \\S(G,p)\end{bmatrix}\,$$
for the framework $(G,p)$ on $\F$
is (up to scaling)  the Jacobian matrix

of $F^{G,\F}$ evaluated at the point $p$.
It is shown in \cite{NOP} that the null space of $R_{\F}(G,p)$ is the space of infinitesimal flexes of $(G,p)$ on $\F$. This allows us to
characterise infinitesimal rigidity in terms of $R_{\F}(G,p)$.

\begin{thm}[\cite{NOP}]\label{thm:surfacerank}
Let
$(G,p)$ be a framework on $\F$.

Then $(G,p)$ is infinitesimally rigid on $\F$ if and only if $\rank R_{\F}(G,p) = 3n-\ell$.
\end{thm}

Theorem \ref{thm:surfacerank} implies that the (redundant) rigidity of a generic framework $(G,p)$ on $\F$ depends only on the graph $G$. Hence we say that $G$ is {\em (redundantly) rigid on $\F$} if some, or equivalently every, generic realisation of $G$ on $\F$ is (redundantly) rigid.

We close this section by pointing out that Theorem
\ref{thm:cylinderlaman}  implies that a graph which is (redundantly)
rigid on some family of concentric cylinders, is (redundantly) rigid
on all families of concentric cylinders irrespective of their radii.
We do not know if analogous results hold for families of concentric
cones or ellipsoids.

\section{Stresses and stress matrices}
\label{sec:stress}

In this section we develop the notion of an equilibrium stress

for a framework on our surface $\F$

and show that if $(G,p)$ is `fully realised' on $\F$ and has a maximum rank positive semi-definite stress matrix then every equivalent framework on $\F$ is an affine image of $(G,p)$.

A \emph{stress} for a framework $(G,p)$ on $\F$ is a pair $(\omega,\lambda)$, where $\omega:E\to \bR$ and $\lambda:V\to \bR$. A stress $(\omega,\lambda)$ is an \emph{equilibrium stress} if it belongs to the cokernel of $R_{\F}(G,p)$. Thus
$(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ on $\F$ if and only if
 \begin{equation}\label{eq:stressdefn}
 \sum_{j=1}^n \omega_{ij}(p(v_i)-p(v_j)) + \lambda_i s_i(p(v_i))=0 \mbox{ for all $1\leq i \leq n$},
\end{equation}
where $s_i(p(v_i))$ is as defined in Equation (\ref{eq:si}), $\omega_{ij}$ is taken to be equal to $\omega_e$ if $e=v_iv_j\in E$ and to be equal to $0$ if $v_iv_j\not\in E$.
We can think of $\omega$ as a weight function on the edges
and $\lambda$ as a weight function on the vertices.
Note that, if the rows of $R_\F(G,p)$ are linearly independent, then the only equilibrium stress for $(G,p)$ is the all-zero equilibrium stress.

Given a stress $(\omega,\lambda)$ for a framework $(G,p)$ on $\F$ we define: $\Omega=\Omega(\omega)$ to be the $n\times n$ symmetric matrix with off-diagonal entries $-\omega_{ij}$ and diagonal entries $\sum_j \omega_{ij}$;
$\Lambda=\Lambda(\lambda)$ to be the $n\times n$ diagonal matrix with diagonal entries $\lambda_1,\lambda_2,\ldots,\lambda_n$; and $\Delta=\Delta(\lambda, r)$ to be the $n \times n$ diagonal matrix with diagonal entries $\lambda_1 r_1,\lambda_2 r_2,\ldots,\lambda_n r_n$.
The {\em stress matrix} associated to $(\omega,\lambda)$ on $\F$ is the $3n\times 3n$ symmetric matrix

$$\Omega_{\F}(\omega,\lambda)=\begin{bmatrix} \Omega + \Lambda & 0 & 0\\ 0 & \Gamma & 0\\ 0 & 0 & \Sigma \end{bmatrix}$$
where: $\Gamma = \Omega + \Lambda$ if $\F\in \{\Y,\C\}$ and $\Gamma=\Omega+\alpha \Lambda$ if $\F=\E$; $\Sigma=\Omega$ if $\F=\Y$, $\Sigma = \Omega-\Delta$ if $\F=\C$, and $\Sigma=\Omega+\beta \Lambda$ if $\F=\E$.
Our next result, which follows immediately from the definition of an equilibrium stress, tells us how we can use $\Omega_{\F}(\omega,\lambda)$ to determine if $(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ on $\F$.

\begin{lem}
Let $(G,p)$ be a framework on $\F$ with $p(v_i)=(x_i,y_i,z_i)$ and let
\[ \Pi=\begin{bmatrix} x_1 & \dots & x_n & 0 & \dots &0 &0 &\ldots & 0\\
0 & \dots & 0 & y_1 & \dots & y_n & 0 & \dots & 0 \\
0 & \dots &0 &0 &\ldots & 0 & z_1 & \dots & z_n \end{bmatrix}.\]
Then $(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ on $\F$ if and only if
$\Pi \, \Omega_{\F}=0.$
\end{lem}

We next define the {\em configuration matrix} $C_\F(G,p)$ for a framework $(G,p)$ on $\F$ by modifying the above matrix $\Pi$ as follows:

$$ C_\F(G,p)=
\begin{bmatrix} x_1 & \dots & x_n & 0 & \dots &0 &0 &\ldots & 0\\
0 & \dots & 0 & y_1 & \dots & y_n & 0 & \dots & 0 \\
0 & \dots &0 &0 &\ldots & 0 & z_1 & \dots & z_n \\
y_1 & \dots & y_n & 0 & \dots &0 &0 &\ldots & 0\\
0 & \dots & 0 & x_1 & \dots & x_n & 0 & \dots & 0 \\
0 & \dots &0&0&\ldots& 0 & 1 & \dots & 1 \end{bmatrix} \;\;\; \mbox{if } \M=\Y,$$

$$ C_\F(G,p)=
\begin{bmatrix} x_1 & \dots & x_n & 0 & \dots &0 &0 &\ldots & 0\\
0 & \dots & 0 & y_1 & \dots & y_n & 0 & \dots & 0 \\
0 & \dots &0 &0 &\ldots & 0 & z_1 & \dots & z_n \\
y_1 & \dots & y_n & 0 & \dots &0 &0 &\ldots & 0\\
0 & \dots & 0 & x_1 & \dots & x_n & 0 & \dots & 0 \\
\end{bmatrix}
\;\;\; \mbox{if } \M=\C,$$
and $C_\F(G,p)=\Pi$ if $\M=\E$.
We can use the configuration matrix to obtain an upper bound on the rank of a stress matrix.

\begin{lem}\label{lem:coker} Let $(\omega,\lambda)$ be an equilibrium stress for a framework $(G,p)$ on $\F$.
Then each row of $C_{\F}(G,p)$ belongs to the cokernel of
$\Omega_{\F}(\omega,\lambda)$,
$\rank \Omega_{\F}(\omega,\lambda) \leq 3n-\rank C_{\F}(G,p)$ and, if equality holds, then the rows of $C_{\F}(G,p)$ span the cokernel of
$\Omega_{\F}(\omega,\lambda)$.
\end{lem}

\begin{proof}
Equation (\ref{eq:stressdefn}) and the definitions of $\Omega_{\F}(\omega,\lambda)$ and
$C_{\F}(G,p)$ imply that
\[ C_{\F}(G,p) \,  \Omega_{\F}(\omega,\lambda)=0.\]
Thus each row of $C_{\F}(G,p)$ belongs to the cokernel of
$\Omega_{\F}(\omega,\lambda)$. Hence $\dim \coker \Omega_{\F}(\omega,\lambda) \geq \rank C_{\F}(G,p)$ and we have
$\rank \Omega_{\F}(\omega,\lambda) =3n-\dim \coker \Omega_{\F}(\omega,\lambda)\leq 3n-\rank C_{\F}(G,p).$
Furthermore, if equality holds, then $\coker \Omega_{\F}(\omega,\lambda)$ is equal to the row space of $C_{\F}(G,p)$.
\end{proof}

We next use Lemma \ref{lem:coker} to show that, if a framework
$(G,p)$ on $\F$ has an equilibrium stress $(\omega,\lambda)$ whose associated stress
matrix has maximum rank, then every framework $(G,q)$ on $\F$ which
has $(\omega,\lambda)$ as an equilibrium stress can be obtained from $(G,p)$ by an affine transformation.

\begin{lem}\label{lem:1}
Let $(G,p)$ and $(G,q)$ be frameworks on $\F$
and let $(\omega,\lambda)$ be an equilibrium stress for both $(G,p)$ and $(G,q)$. Suppose that $\rank \Omega_{\F}(\omega,\lambda) = 3n-\rank C_{\F}(G,p)$.
Then, for some fixed $a,b,c,d,e,f \in \bR$, we have
\begin{equation}\label{eqn:affine}q(v_i)=
\begin{bmatrix} a & b & 0\\ c & d & 0\\ 0 & 0 & e \end{bmatrix} \, p(v_i) + \begin{bmatrix} 0 \\ 0 \\ f\end{bmatrix} \mbox{ for all $1\leq i\leq n$,}\end{equation}
where $f=0$ if $\F\in\{\C,\E\}$ and $b=c=0$ if $\F=\E$.
\end{lem}

\begin{proof}
Lemma \ref{lem:coker} implies that the rows of $C_{\F}(G,p)$ span
the cokernel of $\Omega_{\F}(\omega,\lambda)$, and that each row of $C_{\F}(G,q)$ belongs to the cokernel of $\Omega_{\F}(\omega,\lambda)$.
It follows that each row of $C_{\F}(G,q)$ is a linear combination of the rows of $C_{\F}(G,p)$. The lemma now follows from the structure of the matrices
$C_{\F}(G,p)$ and $C_{\F}(G,q)$.
\end{proof}

We will say that $(G,q)$ is {\em an $\F$-affine image of $(G,p)$} if it satisfies the conclusion of Lemma \ref{lem:1}.
Our next result gives a converse to Lemma \ref{lem:1}.

\begin{lem}\label{lem:converse}
Let $(G,p)$ and $(G,q)$ be frameworks on $\F$ such that $(G,q)$ is an $\F$-affine image of $(G,p)$.
Then every equilibrium stress $(\omega,\lambda)$ for $(G,p)$ is an equilibrium stress for $(G,q)$.
\end{lem}

\begin{proof}
Since $(G,q)$ is an $\F$-affine image of $(G,p)$, we have $q(v_i)=Ap(v_i)+t$ for some fixed $A,t$ satisfying the conclusion of
Lemma \ref{lem:1}, and all $1\leq i\leq n$.
Hence
\begin{eqnarray*}
\sum_j \omega_{ij}(q(v_i)-q(v_j))+\lambda_i s_i(q(v_i)) &=& \sum_j \omega_{ij}A(p(v_i)-p(v_j)) + \lambda_i s_i(Ap(v_i)+t)
\\ &=& A\left( \sum_j \omega_{ij}(p(v_i)-p(v_j)) + \lambda_i s_i(p(v_i))\right), \end{eqnarray*}
since $s_i(Ap(v_i)+t)=As_i(p(v_i))$ by the definitions of $s_i,A,t$. The
lemma now follows by applying Equation (\ref{eq:stressdefn}).
\end{proof}

A framework $(G,p)$ on $\F$ is {\em fully realised} on $\F$ if the rows of its configuration matrix are linearly independent i.e. we have $\rank C_\F(G,p)=\mu$ where
\begin{equation}\label{eq:mu}
\mu=\begin{cases}
6 & \mbox{ if } \F=\Y; \\
5 & \mbox{ if } \F=\C; \\
3 & \mbox{ if } \F=\E.
\end{cases}
\end{equation}
It can be seen that $(G,p)$ is fully realised on $\F$ if and only if
its points do not all lie on: a plane containing or
perpendicular to the $z$-axis when $\F=\Y$; a plane containing the $z$-axis when $\F=\C$;  one of the planes $x=0$, $y=0$ or $z=0$ when $\F=\E$.

We will next use a similar argument to that used by Connelly in \cite{C82}
to show that, if $(G,p)$ has a positive semi-definite stress matrix of maximum rank then any equivalent framework is an $S$-affine image of $(G,p)$.

The {\em energy function} associated to a stress $(\omega,\lambda)$ for a framework $(G,q)$ and a family of concentric surfaces $\F$ is
defined as
\[ E_{\omega,\lambda,\F}(q)=\sum_{1\leq i<j\leq n} \omega_{ij}\|q(v_i)-q(v_j)\|^2 + \sum_{i=1}^n \lambda_i k(q(v_i))\]
where
\begin{equation}\label{eq:k}
k(x,y,z)=\begin{cases}
x^2+y^2 & \mbox{ if } \F=\Y; \\
x^2+y^2-r_iz^2 & \mbox{ if } \F=\C; \\
x^2+\alpha y^2+\beta z^2 & \mbox{ if } \F=\E.
\end{cases}
\end{equation}

Then the differential of $E_{\omega,\lambda,\F}(q)$ at a point $q$
with $q(v_i)=(x_i,y_i,z_i)$ for all $1\leq i\leq n$ is given by
\begin{equation}\label{eq:grad1}
dE_{\omega,\lambda,\F}|_q = 2
(x_1,\ldots, x_n,y_1,\dots, y_n, z_1, \dots,
z_n)\Omega_{\F}\,(\omega,\lambda).
\end{equation}
Hence, when $(G,q)$ is a framework on $\F$, $q$ is a critical point of $E_{\omega,\lambda,\F}$ if and only if $(\omega,\lambda)$ is an equilibrium stress for $(G,q)$ on $\F$.

\begin{lem}\label{lem:0}
Suppose $q\in \bR^{3n}$. If $q$ is a critical point of
$E_{\omega,\lambda,\F}$ then $E_{\omega,\lambda,\F}(q)=0$. In
addition, when $\Omega_{\F}(\omega,\lambda)$ is positive
semi-definite and $(G,q)$ lies on $\F$, we have
$E_{\omega,\lambda,\F}(q)=0$ if and only if $q$ is a critical point
of $E_{\omega,\lambda,\F}$.
\end{lem}

\begin{proof}
Suppose $q$ is a critical point of $E_{\omega,\lambda,\F}$. Then the
differential of $E_{\omega,\lambda,\F}(q)$ in the direction of $q$
is zero.
This implies that $E_{\omega,\lambda,\F}(tq)$ is constant for all
$t\in \bR$. We can now take $t=0$ to deduce that
$E_{\omega,\lambda,\F}(q)=E_{\omega,\lambda,\F}(0)=0$.

Observe that, if $q(v_i)=(x_i,y_i,z_i)$ for all $1\leq i\leq n$,
then
$$E_{\omega,\lambda,\F}(q)=(x_1,\ldots, x_n,y_1,\dots, y_n, z_1, \dots,
z_n) \Omega_{\F}(\omega,\lambda)(x_1,\ldots, x_n,y_1,\dots, y_n,
z_1, \dots, z_n)^T.$$ Thus, when $\Omega_{\F}(\omega,\lambda)$ is
positive semi-definite,
we have $E_{\omega,\lambda,\F}(q)\geq 0$ for all $q \in \bR^{3n}$.
Hence $q$ is a critical point of $E_{\omega,\lambda,\F}$ if
$E_{\omega,\lambda,\F}(q)=0$.
\end{proof}

We can now deduce that equivalent frameworks with maximum rank
positive semi-definite stress matrices are linked by affine
transformations.

\begin{thm}\label{thm:psdequiv}
Let $(G,p)$ be a framework which is fully realised on $\F$
and let $(\omega,\lambda)$ be an equilibrium stress for $(G,p)$. Suppose that $\Omega_{\F}(\omega,\lambda)$ is positive semi-definite and $\rank \Omega_{\F}(\omega,\lambda) = 3n-\mu$. Let $(G,q)$ be a framework on $\F$ which is equivalent to $(G,p)$. Then $(\omega,\lambda)$ is an equilibrium stress for $(G,q)$, and $(G,q)$ is an $\F$-affine image of $(G,p)$.
\end{thm}

\begin{proof}
Since $(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ we have $E_{\omega,\lambda,\F}(p)=0$.
Then
$$ E_{\omega,\lambda,\F}(q) =  E_{\omega,\lambda,\F}({q}) -E_{\omega,\lambda,\F}(p) =
\sum_{i=1}^n \lambda_i [k(q(v_i)) - k(p(v_i))]=0$$ since
$(G,p)$ and $(G,q)$ are equivalent and both lie on $\F$. Lemma
\ref{lem:0} now implies that
$q$ is a critical point of $E_{\omega,\lambda,\F}$ and hence
$(\omega,\lambda)$ is an equilibrium stress for $(G,q)$. The last part of the theorem now
follows from Lemma \ref{lem:1}.
\end{proof}

We close this section by showing that any two equivalent generic frameworks on $\F$ which are linked by an $\F$-affine map, are in fact congruent.

We say that a framework $(G,p)$ on $\F$ is
\emph{quasi-generic} if it is congruent to a generic framework on
$\F$.  The framework $(G,p)$  is said to be in \emph{standard position} on
$\F$ if $p(v_1)=(x_1,y_1,z_1)$ and: $p(v_1)=(0,y_1,0)$ when $\F=\Y$; $p(v_1)=(0,y_1,z_1)$ when $\F=\C$. All frameworks on $\E$ are taken to be
in standard position. Two frameworks on $\F$ are {\em
$\F$-congruent} if there is an isometry of $\F$ which maps one on to
the other.

We use $\overline{\bK}$ to denote the algebraic closure of a field $\bK$.

We will need the following result, \cite[Lemma $8$]{JMN}.

\begin{lem}\label{lem:q-g<=>}
Suppose $(G,p)$ and $(G,p_0)$ are $\F$-congruent frameworks on $\F$ and $(G,p_0)$ is in standard position on $\F$.
Then $(G,p)$ is quasi-generic if and only if $\td[\bQ(r,p_0):\bQ(r)]=2n-\ell$.
\end{lem}

\begin{lem}\label{lem:global}
Let $(G,p)$ be a generic framework on $\F$ with $n\geq 5$ vertices.
Suppose that $(G,q)$ is an equivalent framework to $(G,p)$ on $S$ which is also an $\F$-affine image of $(G,p)$.
Then $(G,q)$ is congruent to $(G,p)$
\end{lem}

\begin{proof}

We may use the isometries of
$\F$ to move $(G,p)$ and $(G,q)$ to two frameworks $(G,p_0)$ and
$(G,q_0)$ in standard position on $\F$. Then $(G,q_0)$ will be an
$\F$-affine image of $(G,p_0)$.

Let $p_0(v_i)=(x_i,y_i,z_i)$ and $q_0(v_i)=(\hat{x}_i,\hat{y}_i,\hat{z}_i)$.
We will analyse each choice of $\F$ in turn.

\textbf{Case 1}: $\F=\Y$. We have
\begin{equation}\label{eqn:affine2}q_0(v_i)=
\begin{bmatrix} a & b & 0\\ c & d & 0\\ 0 & 0 & e \end{bmatrix} \cdot p_0(v_i) + \begin{bmatrix} 0 \\ 0 \\ f\end{bmatrix} \mbox{ for all $1\leq i\leq n$.}\end{equation}
Applying Equation (\ref{eqn:affine2}) with $q_0(v_1)=(0,y_1,0)=p_0(v_1)$ ($\hat{y}_1=y_1$ since $(G,p)$ and $(G,q)$ are on $S$) reveals that $b=0=f$ and $d=1$.
For $i=2,3,\dots,n$, Equation (\ref{eqn:affine2}) now gives
\[ \begin{bmatrix} \hat{x}_i \\ \hat{y}_i \\ \hat{z}_i\end{bmatrix}=q_0(v_i)=\begin{bmatrix} a & 0 & 0\\ c & 1 & 0\\ 0 & 0 & e\end{bmatrix}\begin{bmatrix} x_i \\ y_i \\ z_i\end{bmatrix} = \begin{bmatrix} ax_i \\ cx_i+y_i \\ ez_i\end{bmatrix}. \]
Using the fact $q_0(v_i)$ and $p_0(v_i)$ are on $\Y_i$ we deduce
that
\begin{equation}\label{eqn:1}
(a^2-1+c^2)x_i^2+2cx_iy_i=0.
\end{equation}

Suppose $c\neq 0$. Then we have
\begin{equation*}
y_i=\frac{(1-a^2-c^2)x_i}{2c},
\end{equation*}
and
\[ r_i=x_i^2 + y_i^2= x_i^2+ \frac{(1-a^2-c^2)^2x_i^2}{4c^2}. \]
These equations imply that $x_i,y_i \in \overline{\bQ(r,a,c)}$. We may
now deduce that
$$\td [\bQ(r,p_0):\bQ(r)]\leq \td [\overline{\bQ(r,z_2,z_3,\dots,z_n,a,c)}:\bQ(r)]\leq n+2.$$
Since $n\geq 5$, this contradicts the fact that $\td
[\bQ(r,p_0):\bQ(r)]=2n-2$
by Lemma \ref{lem:q-g<=>}. Hence $c=0$.

Equation (\ref{eqn:1}) and the fact that $c=0$ implies $a=\pm 1$. It remains to show that $e=\pm 1$.
We may assume, without loss of generality, that $v_1v_2 \in E$. Then
\begin{eqnarray*} x_2^2+(y_1-y_2)^2 +z_2^2 &=& \|(0,y_1,0)-(x_2,y_2,z_2)\|^2 = \| p_0(v_1)-p_0(v_2)\|^2 \\ &=& \| q_0(v_1)-q_0(v_2)\|^2 = \|(0,y_1,0)-(\hat{x}_2,\hat{y}_2,\hat{z}_2)\|^2 \\ &=& \|(0,y_1,0)-A(x_2,y_2,z_2)\|^2 = \| (0,y_1,0)-(\pm x_2,y_2,ez_2)\|^2 \\ &=& x_2^2 + (y_1-y_2)^2 +e^2z_2^2. \end{eqnarray*}
Hence $z_2^2=e^2z_2^2$ and $e=\pm 1$.

We have shown that, if $q_0\neq p_0$, then $(G,q_0)$ is a reflection of $(G,p_0)$ in a plane which contains $(0,y_1,0)$ and either contains, or is perpendicular to, the $z$-axis or a composition thereof.
Hence $(G,p_0)$ and $(G,q_0)$ are congruent. This implies that $(G,p)$ and $(G,q)$ are congruent.
\newline

\textbf{Case 2}: $\F=\C$. We have
\begin{equation}\label{eqn:affine23}q_0(v_i)=
\begin{bmatrix} a & b & 0\\ c & d & 0\\ 0 & 0 & e \end{bmatrix} \cdot p_0(v_i) \mbox{ for all $1\leq i\leq n$.}\end{equation}
Since $p_0(v_1)=(0,y_1,z_1)$, $q_0(v_1)=(0,\hat{y}_1,\hat{z}_1)$, $y_1^2=r_1z_1^2$ and $\hat{y}_1^2=r_1\hat{z}_1^2$ applying Equation (\ref{eqn:affine23}) shows that $b=0$ and $d=e$. For $i=2,3,\dots,n$, we have

\[ \begin{bmatrix} \hat{x}_i \\ \hat{y}_i \\ \hat{z}_i\end{bmatrix}=q_o(v_i)=\begin{bmatrix} a & 0 & 0\\ c & d & 0\\ 0 & 0 & d\end{bmatrix}\begin{bmatrix} x_i \\ y_i \\ z_i\end{bmatrix} = \begin{bmatrix} ax_i \\ cx_i+dy_i \\ dz_i\end{bmatrix}. \]
Using the fact $q_0(v_i)$ and $p_0(v_i)$ are on $\C_i$ we deduce
that
\begin{equation}\label{eqn:12}
(a^2-1+c^2)x_i^2+2cdx_iy_i + (d^2-1)y_i^2-r_i(d^2-1)z_i^2=0.
\end{equation}

Suppose $d^2\neq 1$. Then
\begin{equation*}
z_i^2=\frac{(a^2-1+c^2)x_i^2+2cdx_iy_i + (d^2-1)y_i^2}{r_i(d^2-1)}.
\end{equation*}
Since
\[ x_i^2 + y_i^2= r_iz_i^2= \frac{(a^2-1+c^2)x_i^2+2cdx_iy_i + (d^2-1)y_i^2}{d^2-1},\]
this implies $x_i,z_i \in \overline{\bQ(r,a,c,d,y_i)}$.
We may now deduce that
$$\td [\bQ(r,p_0):\bQ(r)]\leq \td [\overline{\bQ(r,y_1,y_2,y_3,\dots,y_n,a,c,d)}:\bQ(r)]\leq n+3.$$
Since $n\geq 5$, this contradicts the fact that $\td [\bQ(r,p_0):\bQ(r)]=2n-1$, by Lemma \ref{lem:q-g<=>}.
Hence $d^2=1$. Substituting $d^2=1$ into Equation (\ref{eqn:12}) gives
\begin{equation}\label{eqn:123}
(a^2-1+c^2)x_i^2+2cdx_iy_i=0.
\end{equation}
Similar arguments to those used in Case 1 can now be applied to
deduce $c=0$ and $a=\pm 1$.

We have shown that, if $q_0\neq p_0$, then $(G,q_0)$ is a reflection of $(G,p_0)$ in the plane containing $(0,y_1,z_1)$ and the $z$-axis, or a rotation by $\pi$ around the $x$-axis, or a composition thereof.
Hence $(G,p_0)$ and $(G,q_0)$ are congruent. This implies that $(G,p)$ and $(G,q)$ are congruent.
\newline

\textbf{Case 3}: $\F=\E$. We have
\begin{equation}\label{eqn:affine234}q_0(v_i)=
\begin{bmatrix} a & 0 & 0\\ 0 & d & 0\\ 0 & 0 & e \end{bmatrix} \cdot p_0(v_i) \mbox{ for all $1\leq i\leq n$.}\end{equation}
Since $p_0(v_i)$ and $q_0(v_i)$ both lie on $\E_i$, we have $x_i^2 + \alpha y_i^2 + \beta z_i^2 = r_i$ and $a^2 x_i^2 + \alpha d^2 y_i^2 + \beta e^2 z_i^2 = r_i$. We can eliminate $x_i^2$ from these equations to obtain
\begin{equation}\label{eqn:yyy}
r_i(a^2-1)+\alpha y_i^2(d^2-a^2) + \beta z_i^2(e^2-a^2)=0.
\end{equation}
Hence, if $d^2-a^2 \neq 0$, then $x_i,y_i \in \overline{\bQ(r,a,d,e,z_i)}$. This would imply that
\[
2n = td [\bQ(r,p_0):\bQ(r)] \leq td [\overline{\bQ(r,a,d,e,z_1,z_2,\dots, z_n)}:\bQ(r)] \leq n+3,
\]
a contradiction since $n\geq 5$. Hence $d^2=a^2$. We can deduce similarly, from Equation (\ref{eqn:yyy}), that $a^2=e^2$. Equation (\ref{eqn:yyy}) now implies that $a^2=1$.

We have shown that $(G,q_0)$ is a reflection of $(G,p_0)$ in either the plane $x=0,y=0$ or $z=0$ or a composition thereof.
Hence $(G,p_0)$ and $(G,q_0)$ are congruent. This implies that $(G,p)$ and $(G,q)$ are congruent.\end{proof}

Theorem \ref{thm:psdequiv}  and Lemma \ref{lem:global} immediately imply that a generic framework on $\F$ with a maximum rank positive semi-definite stress matrix is globally rigid. We believe that the same conclusion holds without the hypothesis that there is a positive semi-definite stress matrix.

\begin{con}\label{con:affine}
Suppose that $(G,p)$ is generic on $\F$ and that $(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ with $\rank \Omega_{\F}(\omega,\lambda) = 3n-\mu$. Then $(G,p)$ is globally rigid on $\F$.
\end{con}

\section{A sufficient condition for global rigidity on families of cylinders and ellipsoids}
\label{sec:main}

We will show that Conjecture \ref{con:affine} holds when $\F\in \{\Y,\E\}$ and the parameters $r_1,r_2,\dots,r_n$ are algebraically independent over $\mathbb{Q}$.

To do this we need to change our viewpoint from the surface $S\subset \bR^3$
to a point $p\in \bR^{3n}$.

Given a map $p:V\to \bR^{3n}$, there is a unique family of concentric surfaces $\F$ with $p(v_i)\in \F_i$
for each $\F\in \{\Y,\C,\E\}$, as long as $p(v_i)$ does not lie on the $z$-axis for all $1\leq i\leq n$ when
$\F\in \{\Y,\C\}$ and $p(v_i)\neq (0,0,0)$ for all $1\leq i\leq n$ when
$\F=\E$. We will refer to $S$ as the {\em surface induced by $p$} and denote it by $S^p$.

With this restriction we can use the following result, due to Connelly \cite{C2005},  to obtain the special case of Conjecture \ref{con:affine}.

\begin{prop}[\cite{C2005}]\label{prop:Bobs3.3}
Suppose that $f:\mathbb{R}^a\rightarrow \mathbb{R}^b$ is a function, where each coordinate is a polynomial with integer coefficients, $p\in \mathbb{R}^a$ is generic, and $f(p)=f(q)$, for some $q\in \mathbb{R}^a$. Then there are (open) neighbourhoods $N_p$ of $p$ and $N_q$ of $q$ in $\mathbb{R}^a$ and a diffeomorphism $g:N_q\rightarrow N_p$ such that for all $x\in N_q$, $f(g(x))=f(x)$, and $g(q)=p$.
\end{prop}

\begin{thm}\label{thm:global}
Suppose $p$ is a generic point in $\mathbb{R}^{3n}$ and let $\F=\F^p$ for some $\F\in \{\Y,\E\}$. Let $(\omega,\lambda)$ be an equilibrium stress for $(G,p)$ on $\F$ and let $(G,q)$ be equivalent to $(G,p)$ on $\F$. Then $(\omega,\lambda)$ is an equilibrium stress for $(G,q)$ on $\F$. Furthermore, if $\rank \Omega_{\F}(\omega,\lambda) = 3n-\mu$, then $(G,p)$ is globally rigid on $\F$.
\end{thm}

\begin{proof}
Let $F:\bR^{3n}\to \bR^{m+n}$ be the modified surface rigidity map defined by $F(p)=(F^G(p),\hat\Theta^\S(p)$ where $F^G$ is the rigidity map for $G$, $\hat\Theta^\S(p)=( k(p(v_1),\ldots,k(p(v_n))$, $k(x,y,z)=x^2+y^2$ when $\F=\C$ and $k(x,y,z)=x^2+\alpha y^2+\beta z^2$ when $\F=\E$.  By Proposition \ref{prop:Bobs3.3} there exist open
neighbourhoods $N_{p}$ of $p$ and $N_{q}$ of $q$ in $\mathbb{R}^{3n}$ and
a diffeomorphism $g:N_{q}\to N_{p}$ such that $g(q)=p$ and,
for all $q\in N_{q}$, $f(g( q))=f(q)$.
Taking differentials at
$q$, and using the fact that the Jacobian matrix of $F$ evaluated at $p$ is $2R_{\F}(G,p)$, we obtain $R_{\F}(G,q)=R_{\F}(G,p)\,D$ where $D$ is the Jacobian matrix of $g$ at $q$.

Since $(\omega,\lambda)$ is an
equilibrium stress for $(G,p)$ we have $(\omega,\lambda)\,
R_{\F}(G,q)=(\omega,\lambda)\, R_{\F}(G,p)D= 0\,D=0$.

Hence $(\omega,\lambda)$ is an equilibrium stress of $(G,q)$.

Since $(G,p)$ is generic, it is fully realised on $\F$. We can now use Lemma \ref{lem:1} and the hypothesis that
$\rank \Omega_{\F}(\omega,\lambda) = 3n-\mu$
to deduce that
$(G,q)$ is an $\F$-affine image of $(G,p)$. Lemma \ref{lem:global} now tells us that $(G,q)$ is congruent to $(G,p)$. Hence $(G,p)$ is globally rigid.
\end{proof}

The above proof works for families of cylinders and ellipsoids because we can eliminate the parameters $r_i$ from their defining equations without changing their Jacobian matrix. This is not possible for families of cones. We will discuss this further in Section \ref{sec: Closing Remarks}.

\section{1-extensions and global rigidity}
\label{sec:1ext}

Given a graph $G$, the {\em $1$-extension operation} constructs a
new graph by first deleting an edge $v_1v_2$ and then adding a
new vertex $v_0$ and three new edges $v_0v_1,v_0v_2,v_0v_3$ for some
vertex $v_3$ distinct from $v_1,v_2$. Our aim is to show that the
property of having a maximum rank stress matrix is preserved by the
1-extension operation.

\begin{lem}\label{lem:1ext}
Suppose $(G,p)$ is a generic framework on $S$ with $n\geq 3$.

Let $G'=(V',E')$ be a 1-extension of  $G$,
obtained by deleting an edge $e=v_1v_2$ and adding a new vertex $v_0$ and new edges
$v_0v_1, v_0v_2,v_0v_3$.
Then there exists a map $q:V'\to \bR^3$ such that $\rank R_{S^q}(G',q)=\rank R_{S}(G,p)+3$.
Furthermore, if $(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ on $S$ and $\omega_e\neq 0$, then
there exists an equilibrium stress $(\omega',\lambda')$ for $(G',q)$ on $S^q$ such that  $\rank
\Omega_{\F^q}(\omega',\lambda')=rank \Omega_{\F}(\omega,\lambda)+3$.
\end{lem}

\begin{proof}
Define $(G',q)$ by putting $q(v)=p(v)$ for all $v\in V$ and
$q(v_0)=\frac{1}{2}p(v_1)+\frac{1}{2}p(v_2)$.

Let $S^q$ be the surface induced
by $q$.

We first consider the framework $(G'+v_1v_2-v_0v_2,q)$ on $S^q$. Its
rigidity matrix $R$ can be constructed from $R_\F(G,p)$ by adding 3
new columns indexed by $v_0$, and 3 new rows indexed by $v_0$,
$v_0v_1$ and $v_0v_3$, respectively. Since $(p(v_1),p(v_2),p(v_3))$
is a generic point on $S(r_1)\times S(r_2)\times S(r_3)$,

the $3\times 3$ submatrix $M$ of $R$ with rows indexed by $v_0,
v_0v_1,v_0v_3$ and columns indexed by $v_0$ is
non-singular.\footnote{We can consider  $\det M$ as a polynomial in
the coordinates of $(p(v_1),p(v_2),p(v_3))$. If $\det M=0$, then
genericness would imply that this polynomial evaluates to $0$ at all
points in $S(r_1)\times S(r_2)\times S(r_3)$. It is straightforward
to show that this is not the case by finding points
$(p_1,p_2,p_3)\in S(r_1)\times S(r_2)\times S(r_3)$ at which the
polynomial is nonzero. When $\F=\Y(r)$, we can take
$p_1=(\sqrt{r_1},0,0)$, $p_2=(0,\sqrt{r_2},0)$ and
$p_3=(\sqrt{r_3},0,1)$; when $\F=\C(r)$, we can take
$p_1=(\sqrt{r_1},0,1)$, $p_2=(\sqrt{r_2},0,-1)$ and
$p_3=(0,\sqrt{r_3},1)$; and when $\F=\E(r)$, we can take
$p_1=(\sqrt{r_1},0,0)$, $p_2=(0,\frac{\sqrt{r_2}}{\sqrt{\alpha}},0)$ and
$p_3=(0,0,\frac{\sqrt{r_3}}{\sqrt{\beta}})$.}

The fact that the new columns contain zeros everywhere except in the new rows
now gives $\rank R=\rank R_\F(G,p)+3$.
Since $q(v_0),q(v_1)$ and $q(v_2)$ are collinear, the rows in $R_{\F^q}(G'+v_1v_2,q)$ corresponding to
$v_0v_1,v_0v_2,v_1v_2$ are a minimal linearly dependent set. Thus
$$\rank R_{S^q}(G',q)=\rank R_{S^q}(G'+v_1v_2,q)=\rank R=\rank R_{S}(G,p)+3.$$

Let $({\omega'},{\lambda'})$ be the stress for $({G'},{q})$ on
${\F^q}$ defined by putting $\omega'_f=\omega_f$ for all $f \in
E-e$, ${\omega'}(v_1v_{0})=2\omega_e$,
${\omega'}(v_2v_{0})=2\omega_e$, ${\lambda'}(v)=\lambda(v)$ for all
$v \in V$ and ${\lambda'}(v_{0})=0$. It is straightforward to verify
that $({\omega'},{\lambda'})$ is an equilibrium stress for
$({G'},{q})$ on ${\F^q}$. Let $\omega_{ij}$ be the $ij$-th entry of
$\Omega(\omega')$ for $i\neq j$ and $\lambda_i$ be the $ii$-th entry
of $\Lambda(\lambda')$.

We first consider $\Omega({\omega'}) + \Lambda({\lambda'})$. We have

\[ \Omega({\omega'})+ \Lambda({\lambda'})=\begin{bmatrix}
4\omega_{12} & -2\omega_{12} & -2\omega_{12} & 0 & \dots & 0\\
-2\omega_{12} & \sum_j \omega_{1j} + \omega_{12}+\lambda_1 & 0 & -\omega_{13} & \dots & -\omega_{1n}\\
-2\omega_{12} & 0 & \sum_j \omega_{2j} + \omega_{12}+\lambda_2 &
-\omega_{23} & \dots & -\omega_{2n} \\ 0 & -\omega_{13} &
-\omega_{23} &  \dots & \dots & -\omega_{3n} \\ \vdots & \vdots &
\vdots &  &  & \vdots
\end{bmatrix}. \] By adding $1/2$ times the first row to
the second and third rows, respectively, this reduces to
\[\begin{bmatrix}
4\omega_{12} & -2\omega_{12} & -2\omega_{12} & 0 & \dots & 0\\
0 & \sum_j \omega_{1j}+\lambda_1 & -\omega_{12} & -\omega_{13} &
\dots & -\omega_{1n}\\ 0 & -\omega_{12} & \sum_j
\omega_{2j}+\lambda_2 & -\omega_{23} & \dots & -\omega_{2n} \\
\vdots & \vdots & \vdots & \vdots & & \vdots \\  \end{bmatrix}. \]
Now adding $1/2$ times the first column to the second and third
columns, respectively, gives
\[\begin{bmatrix}
4\omega_{12} & 0 & 0 & 0 & \dots & 0\\0 & \sum_j
\omega_{1j}+\lambda_1 & -\omega_{12} & -\omega_{13} & \dots &
-\omega_{1n}\\ 0 & -\omega_{12} & \sum_j \omega_{2j}+\lambda_2 &
-\omega_{23} & \dots & -\omega_{2n} \\ \vdots & \vdots & \vdots &
\vdots & & \vdots \\ \end{bmatrix} =
\begin{bmatrix} 4\omega_{12} & 0 & \dots & 0\\ 0 & \\ \vdots & & \Omega(\omega) + \Lambda(\lambda)\\ 0 \end{bmatrix}. \]
Since $\omega_{12}\neq 0$, we have
 $\rank \Omega({\omega'})+ \Lambda({\lambda'})=\rank \Omega(\omega)+ \Lambda(\lambda)+1$.

Since $\lambda'(v_0)=0$, we can repeat the above
argument for $\Omega({\omega'})$ when $\F=\Y$, for $\Omega({\omega'})-\Delta({\lambda'})$
when $\F=\C$, and for both $\Omega({\omega'})+\alpha\Lambda({\lambda'})$ and
$\Omega({\omega'})+\beta\Lambda({\lambda'})$ when $\F=\E$, to deduce that
$\rank \Omega_{{\F^q}}({\omega'},{\lambda'})=  \rank \Omega_{\F}(\omega,\lambda)+3$.
\end{proof}

We do not know whether we can find a framework $(G',q)$ which satisfies the conclusions of Lemma \ref{lem:1ext} and in addition has $\F^q=\F$.\footnote{Partial results are known for particular surfaces: there exists a framework $(G,q)$ with $\rank R_{\F^q}(G',q)=\rank R_{S}(G,p)+3$ and $\F^q=\F$ when $\F=\Y$ \cite{NOP}, and when $\F=\C(1)$ or $\F=\E(1)$ \cite{NOP2}.} Lacking such a result, we are forced
to consider frameworks on `generic surfaces' i.e. surfaces $S^q$ induced by some generic $q\in \bR^{3n}$.

\begin{lem}\label{lem:genrank} Suppose $(G,p)$ is an infinitesimally rigid framework on some surface $\F$. Then $(G,q)$ is infinitesimally rigid on $\F^q$ for all generic
$q\in \bR^{3n}$.
\end{lem}

\begin{proof}
Choose $q:V\to \bR^3$ such that $q(v_i)$ does not lie on the $z$-axis for all $1\leq i\leq n$ when
$\F\in \{\Y,\C\}$ and $q(v_i)\neq (0,0,0)$ for all $1\leq i\leq n$ when
$\F=\E$. Since $q(v_i)\in S_i^q$ for all $1\leq i \leq n$,
the $\F^q$-rigidity matrix for $(G,q)$ has the form $R_{\F^q}(G,q)=\begin{bmatrix}R(G,q) \\S(G,q)\end{bmatrix}$ where $R(G,q)$ is the ordinary rigidity matrix
of $(G,q)$,
\[ S(G,q) = \begin{bmatrix} s_1 & 0 & \dots  &0  \\  0 & s_2 & \dots &0  \\ \vdots && \ddots & \vdots\\ 0 & 0 & \dots & s_n \end{bmatrix},
\]
and
\begin{equation}\label{eq:si_new}
s_i= \begin{cases}
 (x_i,y_i,0), & \text{if } \F^q=\Y^q; \\
 (x_i,y_i,-\frac{x_i^2+y_i^2}{z_i}), & \text{if }\F^q=\C^q; \\
 (x_i,\alpha y_i,\beta z_i), & \text{if }\F^q=\E^q.
\end{cases}
\end{equation}
The expression for $s_i$ when $\F^q=\C^q$ is obtained by substituting $r_i=(x_i^2+y_i^2)/z_i^2$ into Equation (\ref{eq:si}). Since the entries in $R_{\F^q}(G,q)$ are rational functions of $q$, its rank will be maximised when $q$ is a generic point in $\bR^{3n}$.
\end{proof}

The analogous result for frameworks with a maximum rank stress matrix is not true in general. It becomes true, however, if we restrict our attention to
infinitesimally rigid frameworks.

\begin{lem}\label{lem:genstress} Suppose $(G,p)$ is an infinitesimally rigid framework on  $\F$
and $\rank \Omega_{\F}(\omega,\lambda)= 3n-\mu$ for some equilibrium stress $(\omega,\lambda)$ of $(G,p)$. Then $(G,q)$ has an equilibrium stress $(\omega',\lambda')$
on $\F^q$ with
$\rank \Omega_{\F^q}(\omega',\lambda')= 3n-\mu$
for all generic
$q\in \bR^{3n}$. In addition, if $\F\in \{\Y,\E\}$, then $(\omega',\lambda')$ can be chosen so that $w'_e\neq 0$ for all
$e\in E$.
\end{lem}

\begin{proof} We adapt the proof technique of Connelly and Whiteley \cite[Theorem 5]{C&W}.
Choose $q:V\to \bR^{3n}$ such that $(G,q)$ is infinitesimally rigid on $\F^q$. We saw in the proof of Lemma \ref{lem:genrank} that the entries in
$R_{\F^q}(G,q)$ are rational functions of $q$. Since the space of equilibrium stresses of $(G,q)$ is the cokernel of $R_{\F^q}(G,q)$, each equilibrium stress of $(G,q)$ can be expressed as a pair of rational functions $(\omega(q,t),\lambda(q,t))$ of $q$ and $t$, where $t$ is a vector of $m-2n+\ell$ indeterminates. This implies that the entries in the corresponding stress matrix $\Omega_{\F^q}(\omega(q,t),\lambda(q,t))$ will also be rational functions of $q$ and $t$. Hence the rank of
$\Omega_{\F^q}(\omega(q,t),\lambda(q,t))$ will be maximised whenever $q,t$ is algebraically independent over $\bQ$. In particular, for any generic $q\in \bR^{3n}$, $(G,q)$ is infinitesimally rigid on $\F^q$ by Lemma \ref{lem:genrank}, and we can choose $t\in \bR^{m-2n+\ell}$ such that
 $\rank \Omega_{\F^q}(\omega(q,t),\lambda(q,t))=3n-\mu$.

\iffalse
An equilibrium stress $(\omega,\lambda)$ for a framework $(G,p)$ on $\F$ is said to be {\em nowhere zero} if $\omega_e\neq 0$ for all $e\in E$.

\begin{lem}\label{lem:nonzero} Let $p$ be a generic point in $\mathbb{R}^{3n}$ and let $\F=\F^p$ for some $\F\in \{\Y,\E\}$. Let $(G,p)$ be a generic framework on $\F$
and suppose $\rank \Omega_{\F}(\omega,\lambda)= 3n-\mu$ for some equilibrium stress $(\omega,\lambda)$ of $(G,p)$. Then $\rank \Omega_{\F}(\omega',\lambda')= 3n-\mu$ for some nowhere zero equilibrium stress $(\omega',\lambda')$
of $(G,p)$ on $\F$.
\end{lem}

\begin{proof}

\fi

Now suppose that $\F\in \{\Y,\E\}$ and that  $(\omega',\lambda')$ has been chosen such that the number of edges $e\in E$ with $\omega'_e=0$ is as small as possible. We may assume  that
$\omega'_e=0$ for some $e\in E$. Then $(\omega'|_{E-e},\lambda')$ is an equilibrium stress for $(G-e,p)$ on $\F^q$ and $\rank \Omega_{\F^q}(\omega'|_{E-e},\lambda')= 3n-\mu$. By Theorem \ref{thm:global}, $(G-e,p)$ is globally rigid on $\F^q$. In particular $(G-e,p)$ is rigid on $\F^q$. Since $p$ is generic, $(G-e,p)$ is infinitesimally rigid on $\F^q$. This implies that the row of $R_{\F^q}(G,p)$ indexed by $e$ is contained in a minimal linearly dependent set of rows of $R_{\F^q}(G,p)$. This gives us an equilibrium stress $(\hat \omega, \hat \lambda)$ for $(G,p)$ on $\F^q$ with $\hat \omega_e\neq 0$. Then
$(\omega'',\lambda'')=(\omega',\lambda')+c(\hat\omega,\hat\lambda)$ is an equilibrium stress for $(G,p)$ on $\F^q$ for any $c\in \bR$. We can now choose
a small $c>0$ so that  $\rank \Omega_{\F^q}(\omega'',\lambda'')= 3n-\mu$, and $\omega''_f\neq 0$ for all $f\in E$ with $\omega'_f\neq 0$.
This contradicts the choice of $(\omega',\lambda')$.
\end{proof}

We can now obtain our result on generic 1-extensions.

\begin{thm}\label{thm:1extgeneric}
Suppose $(G,p)$ is an infinitesimally rigid framework on $\F$, for some $\F\in \{\Y,\E\}$, and $(\omega,\lambda)$ is an equilibrium stress for $(G,p)$ with
$\rank
\Omega_{\F}(\omega,\lambda)=3n-\mu$. Let $G'=(V',E')$ be a $1$-extension of $G$ and $q:V'\to \bR^{3}$ such that
$q$ is generic in  $\bR^{3(n+1)}$.
Then $(G',q)$ is infinitesimally rigid on $S^q$ and has an equilibrium stress $(\omega',\lambda')$ with
$\rank
\Omega_{\F^q}(\omega',\lambda')=3(n+1)-\mu$.
\end{thm}

\begin{proof}
We may assume that $p$ is a generic point in $\bR^{3n}$  and that
$\omega_e\neq 0$ for all $e\in E$  by Lemmas \ref{lem:genrank} and \ref{lem:genstress}. We can now use Lemma \ref{lem:1ext} to deduce that there exists a
map $p^*:V'\to \bR^3$ such that $(G,p^*)$ is infinitesimally rigid on $\F^{p^*}$ with an equilibrium stress $(\omega^*,\lambda^*)$ for $(G',p^*)$ on $S^{p^*}$ such that  $\rank
\Omega_{\F^{p^*}}(\omega^*,\lambda^*)=3(n+1)+3$. The theorem now follows by another application of Lemmas \ref{lem:genrank} and \ref{lem:genstress}.
\end{proof}

\section{Global rigidity on concentric cylinders}
\label{sec:cyl}

In this section we apply our results to make progress on the conjectured characterisation of global rigidity on concentric cylinders given in \cite[Conjecture $9.1$]{JMN}, see also \cite[Conjecture $5.7$]{Nix}.

\begin{con}\label{con:redundant}
Suppose $(G,p)$ is a generic  framework on a family of concentric cylinders $\Y$.

Then $(G,p)$ is globally rigid if and only if $G$ is a complete graph on at most four vertices, or $G$ is 2-connected and redundantly rigid on $\Y$.
\end{con}

We have seen that the redundant rigidity of $G$ on $\Y$ is independent of the radii of the cylinders in $\Y$. Thus
Conjecture \ref{con:redundant} would imply that the global rigidity of a generic realisation of $G$ on a family of concentric cylinders is also independent of the radii of the cylinders.

Theorem \ref{thm:redundant} shows that the combinatorial conditions given in Conjecture \ref{con:redundant} are necessary for global rigidity. We could try to demonstrate sufficiency using a similar proof technique to that of Theorem \ref{thm:2dcomb}. This would involve two steps: (i) a graph theoretic step obtaining a recursive construction for 2-connected, redundantly rigid graphs; (ii) a geometric step showing that each operation used in the recursive construction preserves global rigidity. Part (i) would be resolved by the following conjecture (which uses the base graphs $K_5-e,H_1,H_2$ and the operations of $1$-, $2$- and $3$-join illustrated in Figures \ref{fig:smallgraphs} and \ref{fig:sums}).

\begin{con}\label{con:recurse}
Suppose $G$ is a $2$-connected graph which is redundantly rigid on some (or equivalently every) family of concentric cylinders. Then $G$ can be obtained from either $K_5-e$, $H_1$ or $H_2$ by recursively applying the operations of edge addition, $1$-extension, and  $1$-, $2$- and $3$-join.

\end{con}

The results of \cite{Nix} verify the special case of this conjecture when $|E|=2|V|-1$ i.e. $E$ is a circuit in the generic rigidity matroid for the cylinder.

 \begin{figure}[htp]
\begin{center}
\begin{tikzpicture}[very thick,scale=.47]
\filldraw (-.5,0) circle (3pt)node[anchor=east]{$v_5$};
\filldraw (0,3) circle (3pt)node[anchor=east]{$v_1$};
\filldraw (3.5,0) circle (3pt)node[anchor=west]{$v_3$};
\filldraw (3,3) circle (3pt)node[anchor=west]{$v_2$};
\filldraw (1.5,-1.5) circle (3pt)node[anchor=west]{$v_4$};

 \draw[black,thick]
(1.5,-1.5) -- (-.5,0) -- (0,3) -- (3.5,0) -- (3,3) -- (-.5,0) -- (3.5,0);

\draw[black,thick]
(1.5,-1.5) -- (0,3) -- (3,3) -- (1.5,-1.5);

  \node [rectangle, draw=white, fill=white] (b) at (1.5,-3) {(a)};
        \end{tikzpicture}
          \hspace{0.5cm}
     \begin{tikzpicture}[very thick,scale=.47]
\filldraw (0,0) circle (3pt)node[anchor=east]{$v_4$};
\filldraw (0,3.5) circle (3pt)node[anchor=east]{$v_1$};
\filldraw (3.5,0) circle (3pt)node[anchor=north]{$v_5$};
\filldraw (3.5,3.5) circle (3pt)node[anchor=south]{$v_2$};
\filldraw (7,0) circle (3pt)node[anchor=west]{$v_6$};
\filldraw (7,3.5) circle (3pt)node[anchor=west]{$v_3$};

 \draw[black,thick]
(0,0) -- (0,3.5) -- (3.5,0) -- (3.5,3.5) -- (0,0) -- (3.5,0) -- (7,3.5);

\draw[black,thick]
(0,3.5) -- (3.5,3.5) -- (7,3.5) -- (7,0) -- (3.5,3.5);

\draw[black,thick]
(7,0) -- (3.5,0);

\node [rectangle, draw=white, fill=white] (b) at (3.5,-2) {(b)};
\end{tikzpicture}
       \hspace{0.5cm}
    \begin{tikzpicture}[very thick,scale=.47]
\filldraw (0,-1) circle (3pt)node[anchor=east]{$v_4$};
\filldraw (-1.5,2) circle (3pt)node[anchor=east]{$v_1$};
\filldraw (3,0) circle (3pt)node[anchor=north]{$v_5$};
\filldraw (1.5,3) circle (3pt)node[anchor=south]{$v_2$};
\filldraw (6,-1) circle (3pt)node[anchor=north]{$v_6$};
\filldraw (4.5,3) circle (3pt)node[anchor=south]{$v_3$};
\filldraw (7.5,2) circle (3pt)node[anchor=west]{$v_7$};

 \draw[black,thick]
(0,-1) -- (-1.5,2) -- (3,0) -- (1.5,3) -- (0,-1) -- (3,0) -- (4.5,3);

\draw[black,thick]
(-1.5,2) -- (1.5,3) -- (4.5,3) -- (6,-1) -- (7.5,2) -- (4.5,3);

\draw[black,thick]
(6,-1) -- (3,0) -- (7.5,2);

  \node [rectangle, draw=white, fill=white] (b) at (3,-3) {(c)};
         \end{tikzpicture}
\end{center}
\vspace{-0.3cm}
\caption{The graphs $K_5-e,H_1$ and $H_2$.}
\label{fig:smallgraphs}
\end{figure}

\begin{center}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=0.8]

\filldraw (0,3.5) circle (3pt) node[anchor=south]{$a$};
\filldraw (0,2.5) circle (3pt) node[anchor=north]{$b$};

\filldraw (-4.5,2.5) circle (3pt) node[anchor=east]{$b_1$};
\filldraw (-4.5,3.5) circle (3pt) node[anchor=east]{$a_1$};

\filldraw (4.5,2.5) circle (3pt) node[anchor=west]{$b_2$};
\filldraw (4.5,3.5) circle (3pt) node[anchor=west]{$a_2$};
\filldraw (3.5,2.5) circle (3pt) node[anchor=east]{$d_2$};
\filldraw (3.5,3.5) circle (3pt) node[anchor=east]{$c_2$};

\draw[thick] plot[smooth, tension=1] coordinates{(-1.5,3.48) (-1.5,2.5) (-.5,2.3) (.3,2.4) (-.3,3) (.3,3.6)(-.5,3.7) (-1.5,3.48)};

\draw[thick] plot[smooth, tension=1] coordinates{(1.5,3.48) (1.5,2.5) (.5,2.3) (-.3,2.4) (.3,3) (-.3,3.6)(.5,3.7) (1.5,3.48)};

\draw[thick] plot[smooth, tension=1] coordinates{(-6,3.48) (-6,2.5) (-5,2.3) (-4.2,2.4) (-4.8,3) (-4.2,3.6)(-5,3.7) (-6,3.48)};

\draw[thick] plot[smooth, tension=1] coordinates{(6,3.48) (6,2.5) (5,2.3) (4.2,2.4) (4.8,3) (4.2,3.6)(5,3.7) (6,3.48)};

\draw[black]
(-4.5,3.5) -- (-4.5,2.5);

\draw[black]
(4.5,3.5) -- (4.5,2.5) -- (3.5,2.5) -- (3.5,3.5) -- (4.5,3.5) -- (3.5,2.5);

\draw[black]
(4.5,2.5) -- (3.5,3.5);

\draw[black]
(-3,3) -- (-2.5,3) -- (-2.6,3.1);

\draw[black]
(-2.5,3) -- (-2.6,2.9);

\draw[black]
(3,3) -- (2.5,3) -- (2.6,2.9);

\draw[black]
(2.5,3) -- (2.6,3.1);

\filldraw (0,.5) circle (3pt) node[anchor=south]{$a$};
\filldraw (0,-.5) circle (3pt) node[anchor=north]{$b$};

\filldraw (-4.5,-.5) circle (3pt) node[anchor=east]{$b_1$};
\filldraw (-4.5,.5) circle (3pt) node[anchor=east]{$a_1$};
\filldraw (-3.5,-.5) circle (3pt) node[anchor=west]{$d_1$};
\filldraw (-3.5,.5) circle (3pt) node[anchor=west]{$c_1$};

\filldraw (4.5,-.5) circle (3pt) node[anchor=west]{$b_2$};
\filldraw (4.5,.5) circle (3pt) node[anchor=west]{$a_2$};
\filldraw (3.5,-.5) circle (3pt) node[anchor=east]{$d_2$};
\filldraw (3.5,.5) circle (3pt) node[anchor=east]{$c_2$};

\draw[thick] plot[smooth, tension=1] coordinates{(-1.5,0.48) (-1.5,-.5) (-.5,-.7) (.3,-.6) (-.3,0) (.3,.6)(-.5,.7) (-1.5,.48)};

\draw[thick] plot[smooth, tension=1] coordinates{(1.5,0.48) (1.5,-.5) (.5,-.7) (-.3,-.6) (.3,0) (-.3,.6)(.5,.7) (1.5,.48)};

\draw[thick] plot[smooth, tension=1] coordinates{(-6,0.48) (-6,-.5) (-5,-.7) (-4.2,-.6) (-4.8,0) (-4.2,.6)(-5,.7) (-6,.48)};

\draw[thick] plot[smooth, tension=1] coordinates{(6,0.48) (6,-.5) (5,-.7) (4.2,-.6) (4.8,0) (4.2,.6)(5,.7) (6,.48)};

\draw[black]
(-4.5,.5) -- (-4.5,-.5) -- (-3.5,-.5) -- (-3.5,.5) -- (-4.5,.5) -- (-3.5,-.5);

\draw[black]
(-4.5,-.5) -- (-3.5,.5);

\draw[black]
(4.5,.5) -- (4.5,-.5) -- (3.5,-.5) -- (3.5,.5) -- (4.5,.5) -- (3.5,-.5);

\draw[black]
(4.5,-.5) -- (3.5,.5);

\draw[black]
(0,.5) -- (0,-.5);

\draw[black]
(-3,0) -- (-2.5,0) -- (-2.6,.1);

\draw[black]
(-2.5,0) -- (-2.6,-.1);

\draw[black]
(3,0) -- (2.5,0) -- (2.6,-.1);

\draw[black]
(2.5,0) -- (2.6,.1);

\draw (-5,-3) circle (27pt);
\draw (5,-3) circle (27pt);
\draw (1.2,-3) circle (27pt);
\draw (-1.2,-3) circle (27pt);

\filldraw (-3.4,-3) circle (3pt) node[anchor=south]{$v_1$};
\filldraw (3.4,-3) circle (3pt) node[anchor=south]{$v_2$};
\filldraw (-4.2,-3) circle (3pt) node[anchor=east]{$b_1$};
\filldraw (4.2,-3) circle (3pt) node[anchor=west]{$b_2$};
\filldraw (-4.5,-3.5) circle (3pt) node[anchor=east]{$c_1$};
\filldraw (-4.5,-2.5) circle (3pt) node[anchor=east]{$a_1$};
\filldraw (4.5,-3.5) circle (3pt) node[anchor=west]{$c_2$};
\filldraw (4.5,-2.5) circle (3pt) node[anchor=west]{$a_2$};
\filldraw (0.7,-2.5) circle (3pt) node[anchor=west]{$a_2$};
\filldraw (.7,-3.5) circle (3pt) node[anchor=west]{$c_2$};
\filldraw (.4,-3) circle (3pt) node[anchor=west]{$b_2$};
\filldraw (-.7,-2.5) circle (3pt) node[anchor=east]{$a_1$};
\filldraw (-.7,-3.5) circle (3pt) node[anchor=east]{$c_1$};
\filldraw (-.4,-3) circle (3pt) node[anchor=east]{$b_1$};

\draw[black]
(-.4,-3) -- (.4,-3);

\draw[black]
(-.7,-2.5) -- (.7,-2.5);

\draw[black]
(-.7,-3.5) -- (.7,-3.5);

\draw[black]
(-.4,-3) -- (.4,-3);

\draw[black]
(-.4,-3) -- (.4,-3);

\draw[black]
(-4.5,-3.5) -- (-3.4,-3) -- (-4.2,-3);

\draw[black]
(-3.4,-3) -- (-4.5,-2.5);

\draw[black]
(4.5,-3.5) -- (3.4,-3) -- (4.2,-3);

\draw[black]
(3.4,-3) -- (4.5,-2.5);

\draw[black]
(-3,-3) -- (-2.5,-3) -- (-2.6,-3.1);

\draw[black]
(-2.5,-3) -- (-2.6,-2.9);

\draw[black]
(3,-3) -- (2.5,-3) -- (2.6,-3.1);

\draw[black]
(2.5,-3) -- (2.6,-2.9);

\end{tikzpicture}
\caption{The 1-, 2- and 3-join operations. The 1- and 2-join operations form the graphs in the centre by merging $a_1$ and $a_2$ into $a$, and $b_1$ and $b_2$ into $b$.}
\label{fig:sums}
\end{figure}
\end{center}

We close by showing that all graphs constructed from our base graphs using the edge addition and 1-extension operations are generically globally rigid on concentric cylinders with algebraically independent radii.

\begin{thm}\label{thm:cylinderglobal1ext}
Suppose $G$ is a graph on $n$ vertices which can be constructed from $K_5-e$, $H_1$, or $H_2$ by a sequence of $1$-extensions and edge additions. Then $(G,p)$ is globally rigid on $\Y^p$ for all generic $p\in \bR^{3n}$.
\end{thm}

\begin{proof}
We use induction on $n$ to show that $(G,p)$ is infinitesimally rigid on $\Y^p$ and has an equilibrium stress $(\omega,\lambda)$ with $\rank \Omega_{\Y^p}(\omega,\lambda)=3n-6$. The result will then follow from Theorem \ref{thm:global}. The base case of the induction is when $G\in \{K_5-e,H_1,H_2\}$. We construct a particular realisation $(G,p)$ for each such $G$ which is infinitesimally rigid on $\Y^p$ and has an equilibrium stress with a full rank stress matrix in Appendix A. We may deduce that the same properties hold for all generic $p$ by applying Lemmas \ref{lem:genrank} and \ref{lem:genstress}. To complete the induction we need to show that the $1$-extension and edge addition operations preserve the  properties of
infinitesimal rigidity and having a maximum rank stress matrix. This is trivially true for edge addition. It holds for 1-extension by Theorem
\ref{thm:1extgeneric}.
\end{proof}

We conjecture that Theorem \ref{thm:cylinderglobal1ext} can be strengthened to show that, if $G$ can be constructed as in Theorem \ref{thm:cylinderglobal1ext} and $(G,p)$ is a generic framework on any family of concentric cylinders $\Y$, then $(G,p)$ is globally rigid on $\Y$.

\section{Closing Remarks}\label{sec: Closing Remarks}

\noindent 1. Conjecture \ref{con:affine} would  follow from  Lemmas \ref{lem:1} and \ref{lem:global} if we could show that equivalent generic frameworks on $\F$ must have the same equilibrium stresses. To date we have only been able to prove the following partial result.

\begin{thm}\label{thm:genstressPartial}
Let $(G,p_0)$ be a generic framework on $\F$ and $(\omega,\lambda)$ be an equilibrium stress for
$(G,p_0)$. Let $(G,q_0)$ be equivalent to $(G,p_0)$. Then $(\omega,\lambda')$ is an equilibrium stress for $(G,q_0)$ for some $\lambda' \in \mathbb{R}^n$.
\end{thm}

The proof of Theorem \ref{thm:genstressPartial} is given in Appendix B.\\

\noindent 2. It follows from \cite{C2005} and  \cite{GHT} that a generic framework in $\bR^d$ with $n\geq d+2$ vertices is globally rigid if and only if it has a stress matrix of rank
$n-d-1$.  It is conceivable that the stress matrix condition given in Theorem
 \ref{thm:global} provides a necessary, as
 well as a sufficient, condition for the global rigidity of a generic
 framework on $\F$ whenever the framework has at least $7-\ell$
 vertices.
The following examples indicate why we need this lower bound on $n$.

 The smallest redundantly rigid graph on the cone is $K_5$, but
  no framework $(K_5,p)$ on $\C$ can have a stress matrix with the maximum
  possible rank of $3n-\mu=10$. To see this consider a generic $p\in
  \bR^{15}$. Since every equilibrium stress for $(K_5,p)$ in $\bR^3$ is an equilibrium stress for $(K_5,p)$ on $\C^p$, and since the spaces of equilibrium stresses
  for $(K_5,p)$ in $\bR^3$ and on $\C^p$ are both 1-dimensional, these
  spaces are the same. This implies that every equilibrium stress
  $(\omega,\lambda)$ for $(K_5,p)$ has $\lambda=0$ and $\rank
  \Omega(\omega)\leq 3$. Hence $\rank \Omega_{\C^p}(\omega,\lambda)\leq 9$.
  On the other hand, $(K_5,p)$ is globally rigid on $\C^p$ for all $p$.

 Similarly,
 the smallest redundantly rigid graph on the ellipsoid is $K_6-\{e,f\}$ for
 two nonadjacent edges $e,f$, but no framework $(K_6-\{e,f\},p)$ on $\E$ can have
 a stress matrix with the maximum possible rank of $3n-\mu=15$. (We do not know whether every generic framework $(K_6-\{e,f\},p)$ on $\E^p$ is globally rigid.)\\

\textbf{Acknowledgements.} We would like to thank the School of Mathematics, University of Bristol for providing partial financial support for this research. We would also like to thank Lee Butler for helpful discussions concerning semi-algebraic sets and Bob Connelly for many helpful discussions.


TITLE: Understanding attraction and repulsion between 3 charges
QUESTION [0 upvotes]: Quoting Feynman from Chapter 2 of his book Six Easy Pieces (emphasis mine):

Suppose that we have two unlikes that attract each other, a plus and a minus, and that they stick very close together. Suppose that we have another charge some distance away. Would if feel any attraction? It would feel practically none.
...
On the other hand, if we get very close with the extra charge, attraction arises, because the repulsion of likes and attraction of unlikes will tend to bring unlikes closer together and push likes farther apart. Then the repulsion will be less than the attraction.

I get the first part. The two unlikes are so closely bonded that the distant charge can't affect them in any way. However, the second part is confusing. Why would the repulsion of the two bonded unlikes with respect to the third charge "tend" to be less than their attraction?

REPLY [2 votes]: As the third charge is moved closer, if the orientation of the bonded charges can change it would do so in a way that the like charge will tend to move farther, and the unlike charge will tend to move closer, to the third charge. Now as the third charge is close to the pair, the difference in the distances becomes significant and the repulsion of the like charge, being further away, will be less than the attraction of the unlike charge, which is closer.


TITLE: Pushforward of pullback of an etale sheaf
QUESTION [2 upvotes]: I hope this question is not too elementary, but I'm a bit lost :
Let $S$ be a finite set of closed points of $\mathbb{P^1_{C}}$ and $j : U \longrightarrow \mathbb{P^1_{C}}$ be the inclusion of the complement. I have an etale $\mathbb{Q}_{\ell}$-sheaf $\mathcal{F}$ on $\mathbb{P^1_{C}}$ such that $j^{*} \mathcal{F}$ is locally constant (hence corresponds to some $\ell$-adic representation $V$ of $\pi_{1,et}(U)$), and I would like to understand the fiber of $j_{*}j^{*} \mathcal{F}$ over a point $s \in S$. Is there a description of this fiber in term of the monodromy representation $V$ ?

REPLY [3 votes]: Yes, it is just the invariants under the inertia group corresponding to the point. The reason is that the stalk of $j_*\mathcal{G}$ can be computed as global sections of $\mathcal{G}$ over $\text{Spec}(K^{sh})$ where $K^{sh}$ is the fraction field of the strictly henselian local ring $O_{\mathbf{P}^1, s}^{sh}$ at $s$, see Theorem Tag 03Q9. To be sure, I am using that $s$ is not contained in $U$. Finally, you observe that the absolute Galois group of $K^{sh}$ is the inertia group and use Lemma Tag 04JM.


TITLE: when does $1-x-\frac{x^2}{2!}+\frac{x^3}{3!}-...$converge
QUESTION [4 upvotes]: when does $1-x-\frac{x^2}{2!}+\frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!}-\frac{x^7}{7!}...$ converge and diverge
where the pattern is the Thue morse sequence with adding and subtracting. $+--+-++--++-+--+...$.
I plotted it with 31 terms and found that it might diverge between 7 and 6.
I'm sure how to test it?

REPLY [10 votes]: It absolutely converges, so the signs don't matter.  Compare with the series for $e^x$.