text:
\begin{document}

\title{On the Asymptotic Stability of De-Sitter Spacetime: a non-linear perturbative approach}

\author{Filipe C. Mena\footnote{email: fmena@math.uminho.pt}\\\\
{\em{Dep. Matem\'atica, Universidade do Minho, 4710-057 Braga, Portugal}}\\\vspace{6pt}}

\maketitle

\begin{abstract}
We derive evolution and constraint equations for second order perturbations of flat dust homogeneous and isotropic solutions to the Einstein field equations using all scalar, vector and tensor perturbation modes. We show that the perturbations decay asymptotically in time and that the solutions converge to the De-Sitter solution. By induction, this result is valid for perturbations of arbitrary order. This is in agreement with the cosmic no-hair conjecture of Gibbons and Hawking.
\\\\
keywords: General Relativity; Cosmic no-hair Conjecture; Non-linear Perturbations; Cosmological Attractor; Stability
\\\\
classcode: 83F05 ; 83C30; 53Z05
\end{abstract}

\section{Introduction}

A long standing problem in Mathematical General Relativity is the proof of the Gibbons-Hawking cosmological attractor conjecture, best known as the cosmic no-hair conjecture. This conjecture is the statement
that generic expanding cosmological solutions to the Einstein Field Equations (EFEs) with a positive cosmological constant $\Lambda$ tend asymptotically in time to the De-Sitter solution \cite{GW}. Wald provided a proof of this conjecture within the class of spatially
homogeneous solutions \cite{Wald} while other authors, including Stein-Schabes and collaborators  \cite{BSS,JSS}, have used particular classes of inhomogeneous exact solutions with symmetries. So, it is important to consider more general non-symmetric cases and this can be achieved by using perturbation theory. An interesting result along this line was derived in \cite{Reula} where the author shows, subject to conditions on a symmetric hyperbolic system, the exponential decay of linear and non-linear perturbations around flat homogeneous and isotropic cosmologies. Other results, which do not necessarily imply an exponential decay, were obtained for linear metric perturbations around homogeneous and isotropic backgrounds by \cite{Starobinski, Boucher-Gibbons, Rendall}.

A second order perturbative approach
was followed by \cite{MBT} using scalar perturbations modes at first order which then coupled to source second order scalar and tensor perturbations. In particular, it has been shown that those first and second order perturbations decay and that the respective perturbed solution to the EFEs approaches the De-Sitter solution asymptotically in time \cite{MBT}.

In this note, we generalize the results of \cite{MBT} in three ways: firstly, by including vector and tensor perturbations at first order (besides the scalar modes of \cite{MBT}). Secondly, by considering vector perturbations at second order, so that all scalar, vector and tensor modes are included at both first and second orders. Thirdly, by considering all those perturbations at any order.
To do that, we shall first derive the second order perturbation equations around flat dust homogeneous and isotropic backgrounds by generalising the work of \cite{Mata}. We shall then estimate the asymptotic dynamics of the solutions and show that they decay in time. This will enable to prove that the perturbed spacetime asymptotes to De-Sitter. Finally, we shall show that, by induction, this result is valid for perturbations of any order.

We use the following indice notation: small greek $\a, \b, ... =0, 1, 2, 3$ and small latin $a, b, ...= 1, 2, 3$.

\\

We shall consider solutions to the EFEs such that $T_{\a\b}=\rho u_\a u_\b$, where $\rho$ is the mass density and $u_\a$ the 4-velocity of the fluid. We denote by $\Sigma$ the space orthogonal to $u$ on spacetime $(M,g)$.
Following \cite{Mata}, we use comoving euclidean coordinates, say $\{t,x^1,x^2, x^3\}$, to write the components of $u$ as $u^\a=(1,0,0,0)$ and, in this basis, the metric on $M$ can be written as:
\begin{equation}
\label{dust}
g=-dt^2+h_{ab}dx^a dx^b,
\end{equation}
where $h_{ab}$ is a function of all coordinates.
The components of the extrinsic curvature on $\Sigma$ coincide with the expansion tensor  (see \cite{Ehlers} for definitions about the 1+3 formalism)  and can be written as
$$\theta^\a_{~\b}=\nabla_\b u^\a=\frac{1}{2}h^{\a\gamma}\dot{h}_{\gamma\b},$$
where the dot denotes differentiation with respect to $t$.
In this case, the EFEs give (see also \cite{Mata}):
\begin{eqnarray}
\label{evolutiona}
&&\dot{\theta}_{\a\b}+\theta\theta_{\a\b}+R^*_{\a\b}=
\frac{1}{2}\rho\delta_{\a\b}+\Lambda\delta_{\a\b},\\
\label{Ray}
&&\dot{\theta}+\theta^{\a\b}\theta_{\a\b}+\frac{1}{2}\rho=\Lambda, \\
\label{mra1}
&&\nabla_\a\theta^\a_{~\b}=\nabla_\b\theta\\
\label{energy}
&&\theta^2-\theta^{\a\b}\theta_{\a\b}+R^*=2(\rho+\Lambda),
\end{eqnarray}
where we have denoted the components of the Ricci tensor on $\Sigma$ as $R^*_{\a\b}$ and  the Ricci scalar on $\Sigma$ as $R^*$.

\section{Perturbations around FLRW flat backgrounds}

In this section, we consider small perturbations of arbitrary order $n\in \NN$ on a flat Friedmann-Lema\^itre-Robertson-Walker (FLRW) background spacetime $(M_{\scriptscriptstyle \rm B}, g_{\scriptscriptstyle \rm B})$ with $\Lambda>0$ and $T_{\a\b}=\rho u_\a u_\b$. Following \cite{Mata}, we take the conformally rescaled FLRW flat metric $g_{\scriptscriptstyle \rm B}$
\begin{equation}
\label{de-sitter}
g_{\scriptscriptstyle \rm B}\equiv g^{(0)}_{\a\b}=a^2(\tau)(-d\tau^2+\delta_{ab}dx^a dx^b),
\end{equation}
where $\tau$ is the conformal time defined by $dt=a d\tau$ and $a$ is the scale factor. We consider perturbations in the form \cite{Mata}
\begin{equation}
\label{pert-metric}
g_{\alpha\beta}=g_{\a\b}^{(0)}+\sum_{n=1}^{+\infty} \frac{1}{n!}g_{\alpha\beta}^{(n)}
\end{equation}
with
\begin{eqnarray}
\label{bn1}
g_{00}&=&-a(\tau)^2\left(1+2\sum_{n=1}^{\infty}\frac{1}{n!}\psi^{(n)}\right)\\
\label{bn2}
g_{0a}&=&a(\tau)^2\sum_{n=1}^{\infty}\frac{1}{n!}V^{(n)}_a\\
\label{bn3}
g_{ab}&=&a(\tau)^2\left[\left(1-2\sum_{n=1}^{\infty}\frac{1}{n!}\phi^{(n)}\right)
\delta_{ab}+
\sum_{n=1}^{\infty}\frac{1}{n!}\chi^{(n)}_{ab}\right]
\end{eqnarray}
where $V^{(n)}_a$ can be decomposed as
\begin{equation}
\label{vecy}
V^{(n)}_{a}=\nabla_a \Phi^{(n)}+W^{(n)}_a,
\end{equation}
with $\nabla^a W^{(n)}_a=0$.
Now, for this case, as was shown by Stewart \cite{Stewart} (following works of
Choquet-Bruhat, Fischer \& Marsden \cite{Choquet-etal} and D'Eath \cite{D'Eath}):
\begin{theorem} (Stewart) Any symmetric tensor $\chi^{(n)}_{\a\b}$ defined on three-surfaces $\Sigma$ of $M_{\scriptscriptstyle \rm B}$
can be decomposed into three parts
\begin{equation} \label{decomp}
\chi^{(n)}_{ab}=(\nabla_a \nabla_b -\frac{1}{3}\delta_{ab}\Delta)\chi^{(n)}+2\nabla_{(a}Z^{(n)}_{b)}+\pi^{(n)}_{ab},
\end{equation}
where $\Delta=\nabla^a \nabla_a$, the scalar $\chi$ is defined up to a constant,
the vector field $Z^{(n)}_a$ is divergence-free and
$\pi^{(n)}_{ab}$ is both transverse and tracefree (i.e. $\nabla^a\pi^{(n)}_{ab}=\pi^{(n)a}_{~a} =0$).

\end{theorem}
There are, however, too many degrees of freedom in the above decomposition,

and one can set some of the free perturbations functions to zero thus choosing a certain {\em gauge}. For convenience, we consider the {\em synchronous gauge} which, in this case, corresponds to taking
$$\nabla_a\Phi^{(n)}=\psi^{(n)}=W^{(n)}_a=0.$$
However, we shall prove our main results in a gauge independent manner.

We note that, in this framework, the initial perturbations (\ref{bn1})-(\ref{bn3}) are assumed to be small, in the sense that they result from a Taylor series expansion for each order $O(\epsilon^n)$, with $\epsilon\ll 1$ (see e.g. \cite{Stewart, Mata}), and are such that the metric can be written in "almost-RW" form (holding the inequalities (2.58) of \cite{Ellis}).
We also note that the dependence of the asymptotic dynamics on more general initial conditions cannot be rigorously studied with the present methods. In order to do that, one could use methods from the theory of hyperbolic partial differential equations, such as the ones used in \cite{Rendall, Reula}.

\section{Evolution of first order perturbations}

The evolution of first order perturbations in this context is a much studied subject (see e.g. \cite{MBT} and references therein). Here we shall just recall the main results which will be needed for the next section.
\\
From the EFEs with the perturbed metric (\ref{bn1})-(\ref{bn3}) on FLRW flat backgrounds in the synchronous gauge one finds that the evolution equations for the
first order perturbations are:
\begin{eqnarray}
&&\label{scalar1}
\phi^{(1)''}+\frac{a'}{a}\phi^{(1)'}-\frac{1}{2} a^2\rho_{\scriptscriptstyle \rm B}\phi^{(1)}=0\\
&& \label{vector1}Z^{(1)'}_a+\frac{a'}{a}Z^{(1)}_a=0\\
&&\label{tensor1}\pi^{(1)''}_{ab}+2\frac{a'}{a}\pi^{(1)'}_{ab}-\nabla^2\pi^{(1)}_{ab}=0,
\end{eqnarray}
where the prime denotes differentiation with respect to conformal time. Note that, in the synchronous gauge, the only non-zero perturbation variables are $\phi^{(1)}, Z_{a}^{(1)}, \pi_{ab}^{(1)}, \chi^{(1)}$ but $\phi^{(1)}$ and $\chi^{(1)}$ are related through the momentum constraint equation (\ref{mra1}).

It is known that the solutions of (\ref{scalar1}) increase in time and approach a positive constant asymptotically. In turn, the solutions of  (\ref{vector1}) decrease in time and asymptote to zero, while the solutions of (\ref{tensor1}) oscilate and decay asymptotically to a constant value in time (an example of this behaviour is depicted in Figure 1).

\begin{figure}
           \includegraphics[width=6cm]{tensor1.pdf}

           \caption{{Plot obtained from numerical integration of equation (\ref{tensor1}) after Fourier decomposition for $\Lambda=0.001, \rho_0=0.01$ and the Fourier mode $q=1$ (see equations (\ref{mare24}) and (\ref{mare23})).}}
           \end{figure}

One way to show this is to use the asymptotic form for the scale factor which results from the Friedmann equations (see e.g. \cite{MBT}):
\begin{equation}
\label{asymp-a}
a(\tau)=-\sqrt{\frac{3}{\Lambda}}\frac{1}{\tau}.
\end{equation}
Note that as $a\to +\infty$ one has $\tau\to 0$. So, we are interested in the asymptotic behaviour of the solutions to the perturbation equations as $\tau\to 0$.
Using (\ref{scalar1}) and (\ref{asymp-a}) one gets
\begin{equation}
\label{mare18}
\phi^{(1)}(\tau,{\bf x})=C_1({\bf x}) \tau Y\left(\frac{2}{3},\frac{2}{3}A\tau^{3/2}\right)+ C_2({\bf x})\tau
 J\left(\frac{2}{3},\frac{2}{3}A\tau^{3/2}\right),
\end{equation}
where $A^2=\frac{1}{2}\rho_0\sqrt{\frac{\Lambda}{3}}$,
$C_1$ and $C_2$ are $C^2$-functions which depend on
the initial data and
$J$ and $Y$ are the Bessel functions of the first and second
kind, respectively. One can also find a formal solution to (\ref{tensor1})
which can be written in terms of an integral over the wave vector space
\begin{equation}
\label{mare24}
\pi^{(1)}_{ab}(\tau,{\bf x})=\int^\infty_0\pi^{(1)}_{ab}(q,\tau)e^{-i{\bf q}{\bf x}}d{\bf q},
\end{equation}
with
\begin{equation}
\label{mare23}
\pi^{(1)}_{ab}(\tau,q)=K_{ab}(q)(\sin{(q\tau)}-q\tau\cos{(q\tau)})+F_{ab}(q)(\cos{(q\tau)}+q\tau\sin{(q\tau)}),
\end{equation}
where $K_{ab}$ and $F_{ab}$ are functions (of the Fourier mode $q$) which depend on the initial data, but are otherwise arbitrary. Finally, from (\ref{vector1}) one finds
\begin{equation}
\label{marealta}
Z^{(1)}_a=\frac{C({\bf x})}{a},
\end{equation}
where $C({\bf x})$ depends on the initial conditions.

So, from (\ref{mare24}), ({\ref{mare23}) and (\ref{marealta}) one gets that the linear perturbations $\phi^{(1)}, \pi^{(1)}_{ab}$ and $Z^{(1)}_a$ tend asymptotically in time to constant values. This corresponds to a local asymptotic approach to the De-Sitter solution. In order to see this explicitly one can use the Boucher-Gibbons \cite{Boucher-Gibbons} local coordinate change to transform the resulting asymptotic form of (\ref{pert-metric}) into the De-Sitter metric (see e.g. \cite{MBT}). This enables to show:
\begin{proposition}
\label{prop1}
For $n=1$, the metric (\ref{pert-metric}), satisfying the Einstein Field Equations, approaches the De-Sitter solution locally asymptotically in time.
\end{proposition}

\section{Evolution of second order perturbations and non-linear asymptotic stability of De-Sitter}

One can carry over to second order the first order analysis.
In this section, we present the evolution and constraint equations for second order perturbations which
include scalar, tensor and vector modes at first and second orders in presence of a non-zero
cosmological constant ($\Lambda\ne 0$). These equations are derived in the synchronous gauge from (\ref{evolutiona})-(\ref{energy}) and generalise the equations obtained in
\cite{Mata} for the case of $\Lambda=0$ and zero vector perturbation modes. For convenience, we do not split $\chi_{ab}^{(2)}$ into its vector and tensor parts as before (recall equation (\ref{decomp})) and we write the perturbations in the 3-metric
as $g^{(1)}_{ab}=a^2(\tau)\gamma^{(1)}_{ab}$ and  $g^{(2)}_{ab}=a^2(\tau)\gamma^{(2)}_{ab}$.
\\\\

{\bf Raychaudhuri equation}

\begin{eqnarray}
\label{lp0}
&&{\phi_{\scriptscriptstyle}^{(2)}}''+
{a' \over a} {\phi_{\scriptscriptstyle}^{(2)}}' - {1 \over 2} \rho_{\scriptscriptstyle \rm B} a^2
\phi_{\scriptscriptstyle}^{(2)} = - {1 \over 6} {\gamma^{(1)ab}}'
\biggl( {\gamma^{(1)}_{{\scriptscriptstyle}ab}}'
+ 2{a'  \over a} \gamma^{(1)}_{{\scriptscriptstyle}ab} \biggr)
- \frac{1}{3}\gamma^{(1)ab}\gamma^{(1)''}_{ab}-\\

&&~~~-{1 \over 6} \rho_{\scriptscriptstyle \rm B} a^2 \biggl[ - {1 \over 4}
\biggl(\gamma^{(1)a}_{{\scriptscriptstyle}a}
- \gamma^{(1)~a}_{{\scriptscriptstyle}0a} \biggr)^2
- {1 \over 2}
\biggl(\gamma^{(1)ab}_{\scriptscriptstyle}
\gamma^{(1)}_{{\scriptscriptstyle}ab} -
\gamma^{(1)ab}_{{\scriptscriptstyle}0}
\gamma^{(1)}_{{\scriptscriptstyle}0ab} \biggr)
+ \delta_0 \biggl(\gamma^{(1)a}_{{\scriptscriptstyle}a} -
\gamma^{(1)~a}_{{\scriptscriptstyle}0a} \biggr) \biggr]\equiv N^{(2)}_1. \nonumber
\end{eqnarray}

{\bf Energy constraint}

\begin{eqnarray}
\label{lp1}
&&{a' \over a} {\phi^{(2)}_{\scriptscriptstyle}}'- {1 \over 3}
\nabla^2 \phi^{(2)}_{\scriptscriptstyle} +\frac{1}{2}\rho_{\scriptscriptstyle \rm B} a^2
\phi^{(2)}_{\scriptscriptstyle} - {1 \over 12}
\chi^{(2)ab}_{{\scriptscriptstyle}~~~,ab}
= - \frac{1}{3}{a' \over a} \gamma^{(1)ab}_{\scriptscriptstyle}
{\gamma^{(1)}_{{\scriptscriptstyle}ab}}' -\nonumber\\
&&~~~~+{1 \over 24} \biggl( {\gamma^{(1)ab}_{\scriptscriptstyle}}'
{\gamma^{(1)}_{{\scriptscriptstyle}ab}}' -
{\gamma^{(1)a}_{{\scriptscriptstyle}a}}'
{\gamma^{(1)b}_{{\scriptscriptstyle}b}}'\biggr)
+
{1 \over 6} \biggl[ \gamma^{(1)ab}_{\scriptscriptstyle}
 \biggl( \nabla^2 \gamma^{(1)}_{{\scriptscriptstyle}ab}
+ \gamma^{(1)d}_{{\scriptscriptstyle}d~,ab} -
2 \gamma^{(1)d}_{{\scriptscriptstyle}a~,bd} \biggr) +\nonumber\\
&&
~~~~+\gamma^{(1)d a}_{{\scriptscriptstyle}~~~,d}
\biggl( \gamma^{(1)b}_{{\scriptscriptstyle}b~,a} -
\gamma^{(1)b}_{{\scriptscriptstyle}a~,b} \biggr)
+ {3 \over 4} \gamma^{(1)ab}_{{\scriptscriptstyle}~~~,d}
\gamma^{(1),d}_{{\scriptscriptstyle}ab}
- {1 \over 2} \gamma^{(1)ab}_{{\scriptscriptstyle}~~~,d}
\gamma^{(1)d}_{{\scriptscriptstyle}a~~,b}
- {1 \over 4} \gamma^{(1)a,d}_{{\scriptscriptstyle}a}
\gamma^{(1)b}_{{\scriptscriptstyle}b~,d} \biggr]
\\
&&~~~~+ \frac{1}{6}\rho_{\scriptscriptstyle \rm B} a^2 \biggl[ -
{1 \over 4} \biggl(\gamma^{(1)a}_{{\scriptscriptstyle}a}
- \gamma^{(1)~a}_{{\scriptscriptstyle}0a} \biggr)^2 - {1 \over 2}
\biggl( \gamma^{(1)ab}_{\scriptscriptstyle}
\gamma^{(1)}_{{\scriptscriptstyle}ab} -
\gamma^{(1)ab}_{{\scriptscriptstyle}0}
\gamma^{(1)}_{{\scriptscriptstyle}0ab} \biggr)
+ \delta_0 \biggl(\gamma^{(1)a}_{{\scriptscriptstyle}a} -
\gamma^{(1)~a}_{{\scriptscriptstyle}0a} \biggr) \biggr]\equiv N^{(2)}_2\nonumber
\end{eqnarray}

{\bf Momentum constraint}

\begin{equation}
\label{lp2}
2 {\phi^{(2)}_{{\scriptscriptstyle},b}}' + {1 \over 2}
{\chi^{(2)a}_{{\scriptscriptstyle}b~,a}}' =
\gamma^{(1)ad}_{\scriptscriptstyle}
\biggl( {\gamma^{(1)}_{{\scriptscriptstyle}bd,a}}' -
{\gamma^{(1)}_{{\scriptscriptstyle}ad,b}}' \biggr)
+ \gamma^{(1)ad}_{{\scriptscriptstyle}~~~~,a}
{\gamma^{(1)}_{{\scriptscriptstyle}bd}}'
- {1 \over 2} \gamma^{(1)ad}_{{\scriptscriptstyle}~~~~,b}
{\gamma^{(1)}_{{\scriptscriptstyle}ad}}'
- {1 \over 2} \gamma^{(1)a}_{{\scriptscriptstyle}a~,d}
{\gamma^{(1)d}_{{\scriptscriptstyle}b}}'\equiv N^{(2)}_{3b}
\end{equation}

{\bf Evolution equation}

\begin{eqnarray}
\label{lp3}
&&-\biggl({\phi^{(2)}_{\scriptscriptstyle}}'' + 2{a' \over a}
{\phi^{(2)}_{\scriptscriptstyle}}' \biggr) \delta^a_{~b} +
{1 \over 2} \biggl( {\chi^{(2)a}_{{\scriptscriptstyle}b}}'' +
2{a' \over a} {\chi^{(2)a}_{{\scriptscriptstyle}b}}' \biggr) +
\phi^{(2),a}_{{\scriptscriptstyle},b} -{1 \over 4}
\chi^{(2)dn}_{{\scriptscriptstyle}~~~,d n} \delta^a_{~b} +\nonumber\\
&&~~~~~~+{1 \over 2} \chi^{(2)da}_{{\scriptscriptstyle}~~~,d b} +
{1 \over 2} \chi^{(2)d,a}_{{\scriptscriptstyle}b~~~,d} - {1 \over 2}
\nabla^2
\chi^{(2)a}_{{\scriptscriptstyle}b}={\gamma^{(1)ad}_{\scriptscriptstyle}}'
{\gamma^{(1)}_{{\scriptscriptstyle}db}}' - {1 \over 2}
{\gamma^{(1)d}_{{\scriptscriptstyle}d}}'
{\gamma^{(1)a}_{{\scriptscriptstyle}b}}' + \nonumber\\
&&~~~~~~+{1 \over 8}
\biggl[\biggl({\gamma^{(1)d}_{{\scriptscriptstyle}d}}'\biggr)^2 -
{\gamma^{(1)d}_{{\scriptscriptstyle}n}}'
{\gamma^{(1)n}_{{\scriptscriptstyle}d}}' \biggr] \delta^a_{~b}
- {1 \over 2} \biggl[ - \gamma^{(1)a}_{{\scriptscriptstyle}b}
\biggl( \gamma^{(1)d,n}_{{\scriptscriptstyle}n~~~,d}
- \nabla^2 \gamma^{(1)d}_{{\scriptscriptstyle}d} \biggr)
\\
&&~~~~~~+ 2 \gamma^{(1)dn}_{\scriptscriptstyle}
\biggl( \gamma^{(1)a}_{{\scriptscriptstyle}b~,dn} +
\gamma^{(1)~,a}_{{\scriptscriptstyle}dn~,b}
- \gamma^{(1)a}_{{\scriptscriptstyle}n~,bd}
- \gamma^{(1)~,a}_{{\scriptscriptstyle}n b~,d}  \biggr)
+ 2 \gamma^{(1)dn}_{{\scriptscriptstyle}~~~,d}
\biggl( \gamma^{(1)a}_{{\scriptscriptstyle}b~,n}
- \gamma^{(1)a}_{{\scriptscriptstyle}n~,b} -
\gamma^{(1),a}_{{\scriptscriptstyle}bn} \biggr)
\nonumber\\
&&~~~~~~
+ 2 \gamma^{(1)ea}_{{\scriptscriptstyle}~~~,n}
\gamma^{(1),n}_{{\scriptscriptstyle}be}
- 2 \gamma^{(1)ea}_{{\scriptscriptstyle}~~~,n}
\gamma^{(1)n}_{{\scriptscriptstyle}b~,e}
+ \gamma^{(1)en}_{{\scriptscriptstyle}~~~,b}
\gamma^{(1)~,a}_{{\scriptscriptstyle}en}
+ \gamma^{(1)n}_{{\scriptscriptstyle}n~,e}
\biggl( \gamma^{(1)ea}_{{\scriptscriptstyle}~~~,b} +
\gamma^{(1)e,a}_{{\scriptscriptstyle}b} -
\gamma^{(1)a,e}_{{\scriptscriptstyle}b} \biggr)
\nonumber\\
&&~~~~~~
- \gamma^{(1)dn}_{\scriptscriptstyle}
\biggl( \nabla^2 \gamma^{(1)}_{{\scriptscriptstyle}dn}
+ \gamma^{(1)m}_{{\scriptscriptstyle}m~,dn} -
2 \gamma^{(1)m}_{{\scriptscriptstyle}d~~,mn} \biggr)
\delta^a_{~b}
- \gamma^{(1)n d}_{{\scriptscriptstyle}~~~,n}
\biggl( \gamma^{(1)m}_{{\scriptscriptstyle}m~,d} -
\gamma^{(1)m}_{{\scriptscriptstyle}d~,m}
\biggr) \delta^a_{~b}
\nonumber\\
&&~~~~~~
- {3 \over 4}
\gamma^{(1)dn}_{{\scriptscriptstyle}~~~,m}
\gamma^{(1),m }_{{\scriptscriptstyle}dn}
\delta^a_{~b}
+ {1 \over 2} \gamma^{(1)dn}_{{\scriptscriptstyle}~~~,m}
\gamma^{(1)m }_{{\scriptscriptstyle}d~~,n}
\delta^a_{~b} + {1 \over 4} \gamma^{(1)d,m}_{{\scriptscriptstyle}d}
\gamma^{(1)n}_{{\scriptscriptstyle}n~,m}
\delta^a_{~b} \biggr]\equiv N_{4b}^{(2)a}.\nonumber
\end{eqnarray}
where $\delta=(\rho-\rho_{\scriptscriptstyle \rm B})/\rho_{\scriptscriptstyle \rm B}$, the subindex $0$ denotes evaluation at an initial time
$\tau_0$ and the commas denote $\nabla$ derivatives.

Notice that, while at first order the perturbation equations for the different modes (scalar, vector and tensor) decouple from each other (recall equations (\ref{scalar1})-(\ref{tensor1})), at second order the perturbation equations (and, therefore, the perturbation modes) are coupled. So, for example, products of first order scalar-tensor, scalar-scalar or scalar-vector modes will, in general, source all second order modes.

Notice also that the terms $N^{(2)}$ on the r.h.s. of the four equations are of the form $O(1)O(1)$, i.e. these terms result from couplings of first order perturbations. So, from (\ref{mare18})-(\ref{marealta}) we get that all terms $N^{(2)}$ approach constant values asymptotically in time. This will be crucial ahead to find, from (\ref{lp0})-(\ref{lp3}), that all $Z^{(2)}_a$, $\pi^{(2)}_{ab}$ and $\phi^{(2)}$ also tend asymptotically to constants in time (an example of this behaviour is depicted in Figure 2).

In detail, using the asymptotic expressions (\ref{asymp-a})-(\ref{marealta}) in equation (\ref{lp0}) we can integrate to get the asymptotic estimate
\begin{equation}
\label{mare38}
\phi^{(2)}(\tau,{\bf x})=\frac{L({\bf x})}{A^2}+ O(\tau^2),
\end{equation}
where $L({\bf x})$ is a constant function in time whose expression can be obtained from the asymptotic form of $N^{(2)}_1$. In turn, from integration of (\ref{lp1}) and (\ref{lp2}) we obtain asymptotic conditions in the form
\begin{eqnarray}
\nabla_\a\chi^{(2)\a}_{\b}(\tau,{\bf x})&=& Q_\b({\bf x})+O(\tau^2)\nonumber\\
\label{wate}
\nabla_\a\nabla_\b\chi^{(2)\a\b}(\tau,{\bf x})&=& G({\bf x})+O(\tau^2)
\end{eqnarray}
where, again, $Q_\b$ and $G$ are constant functions in time.
Also, substituting the expressions (\ref{asymp-a})-(\ref{marealta}) in equation (\ref{lp3}), the latter can formally be integrated to give
\begin{equation}
\label{mare43}
\chi^{(2)}_{\a\b}(\tau,{\bf x})=\int^\infty_0\chi^{(2)}_{\a\b}(\tau,k)e^{-i{\bf k}{\bf x}}d{\bf k},
\end{equation}
with\begin{equation}
\label{mare42}
\chi^{(2)}_{\a\b}(\tau,k)=\frac{E_{\a\b}(k)}{k}+O(\tau^2)
\end{equation}
where $E$ is a function of the Fourier modes $k$ which depends on the initial conditions.

From (\ref{mare38})-(\ref{mare42}) it is then clear that both $\phi^{(2)}$ and $\chi_{ab}^{(2)}$ tend to constant values in time asymptotically. Finally, to see that $Z^{(2)}_a$ individually tends to constant values we substitute $\chi_{ab}^{(2)}=2\nabla_{(a}Z^{(2)}_{b)}+\pi^{(2)}_{ab}$ into equation (\ref{lp3}).  Given
$\nabla^a\pi^{(2)}_{ab}=0$, then there will be no $\pi_{ab}^{(2)}$ terms in (\ref{lp3}). Now, since the first order terms (on the r.h.s.) and the terms in $\phi^{(2)}$ (on the l.h.s.) are already known to asymptote to constants, then the remaining term in $Z_a^{(2)}$ will also tend to a constant value in time. We can use this in equation (\ref{lp3}) to show that $\pi^{(2)}_{ab}$ also tends to constants.

Therefore, we conclude that all second perturbations $\phi^{(2)}, \pi^{(2)}_{ab}$ and $Z^{(2)}_a$ tend asymptotically in time to constant values. We note that the density perturbations can be written in terms of the metric perturbations and the expressions that relate these quantities have been derived in \cite{Mata}. In the present case, since the metric perturbations asymptote to constants in time, so do the density perturbations.

As before, one can now apply the Boucher-Gibbons \cite{Boucher-Gibbons} local coordinate change to explicitly transform the resulting asymptotic form of (\ref{pert-metric}) into the De-Sitter metric.

One can also see this in a coordinate and gauge invariant way: Using (\ref{mare38})-(\ref{mare42}) we can show

that at second order, asymptotically,
\begin{eqnarray}
\label{mare49}
&& \theta^2\to \Lambda, ~~~ H_{\a\b}\to 0,~~~R\to 4\Lambda, \\
\label{mare50}
&& \sigma^2 \to 0,~~~E_{\a\b}\to 0,~~~R^*\to 0,
\end{eqnarray}

where $\sigma$ is the shear scalar, $H_{\a\b}$ and $E_{\a\b}$ are the magnetic and electric parts of the Weyl tensor, respectively. The asymptotic behaviour (\ref{mare49})-(\ref{mare50}), together with the fact that $\dot u_\a=0$ and $\omega_{\a\b}\to 0$, where $\omega_{\a\b}$ is the vorticity, caracterizes gauge invariantly the approach to the De-Sitter solution (see e.g. \cite{Ellis}).

This result generalises the result of Proposition \ref{prop1} and previously known second order results  \cite{MBT} by including, at second order, sources of first order vector and tensor perturbation modes as well as pure second order vector modes:
\begin{proposition}
\label{prop2}
For $n=2$, the metric (\ref{pert-metric}), satisfying the Einstein Field Equations, approaches the De-Sitter solution locally asymptotically in time.
\end{proposition}

\begin{figure}
           \includegraphics[width=6cm]{tensor2.pdf}

           \caption{{Two plots obtained from numerical integration of equation (\ref{lp0}) for the
           evolution of second order scalar perturbations $\phi^{(2)}$ for a $k=0$ FLRW dust background with
           $\Lambda=0.001$ and $\rho_0=0.01$.}}
           \end{figure}

Consider now $n$th order perturbations in (\ref{pert-metric}). It is clear that, as before, the sources of the EFEs for the $n$th order perturbations are products of lower  order terms such as $O(n-1)O(1), O(n-2)O(2)$ etc. For example:
\begin{equation}
{\phi_{\scriptscriptstyle}^{(n)}}''+
{a' \over a} {\phi_{\scriptscriptstyle}^{(n)}}' - {1 \over 2} \rho_{\scriptscriptstyle \rm B} a^2
\phi_{\scriptscriptstyle}^{(n)}=N_1^{(n)},
\end{equation}
where $N_1^{(n)}$ is a sum of products of lower order terms. By proving that the lower order terms tend to constants asymptotically in time, one can proceed as before, order by order, and show, by induction, the following result:
\begin{theorem}
At each order $n$, the truncated metric (\ref{pert-metric}), satisfying Einstein Field Equations, is convergent and approaches the De-Sitter solution locally asymptotically in time.
\end{theorem}
\vspace{0.5cm}

{\bf Acknowledgements:}
\\\\
The author is funded by FCT (Portugal) through project\\ PTDC/MAT/108921/2008, thanks Centro de Matem\'atica, University of Minho for support and Dep. Matem\'atica, IST, Lisbon, where this work has been completed.


TITLE: Probability computation involving order statistics
QUESTION [4 upvotes]: Let $X_1$, $X_2$.. $X_n$ be iid uniform random variables i.e.   $X_i \sim U(0,1)$. We know that the order statistics, $X_{(i)}$ is beta distributed $X_{(k)} \sim B(k,n+1-k)$.
Also let $Y_1$, $Y_2$.. $Y_n$ be another set of uniform random variables i.e.   $Y_i \sim U(0,1)$. The order statistics $Y_{(i)}$ are also beta distributed $Y_{(k)} \sim B(k,n+1-k)$.
I'm interested in  finding the following probability,
$\Pr(X_{(1)} < Y_{(2)}, X_{(2)} < Y_{(3)})= ?$
The problem here is that the events $E_1 \equiv \{X_{(1)} < Y_{(2)}\}$ and $E_2 \equiv \{X_{(2)} < Y_{(3)}\}$ etc are not independent, and I'm unable to come up with ways to make them independent so as to make use of the known marginal densities.
Is there any simple way to solve this problem?  Any pointers to a solution are welcome.

REPLY [4 votes]: One solution is to use joint distribution for two order statistics:
$$
   f_{X_{1:n}, X_{2:n}}\left(x_1, x_2\right) = n(n-1) \left(1-x_2\right)^{n-2} \left[ 0 < x_1 < x_2 <1\right]
$$
$$
   f_{Y_{2:n}, Y_{3:n}}\left(y_2, y_3\right) = n(n-1)(n-2) y_2 \left(1-y_3\right)^{n-3} \left[ 0 < y_2 < y_3 <1\right]
$$
To evaluate the probability use
$$ \begin{eqnarray}
    \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n}\right) &=& \mathbb{E}\left( \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n} \mid Y_{2:n},Y_{3:n}\right) \right) \\ &=& \mathbb{E}\left(  F_{X_{1:n},X_{2:n}}\left(Y_{2:n},Y_{3:n}\right)\right)
\end{eqnarray}
$$
The probability $F_{X_{1:n},X_{2:n}}(y_2,y_3)$ is computed as follows, assuming $0<y_2<y_3<1$
$$\begin{eqnarray}
   F_{X_{1:n},X_{2:n}}(y_2,y_3) &=& n(n-1) \int_0^{y_3} \mathrm{d}x_2 \int_{0}^{\min(y_2,x_1)} \mathrm{d}x_1 \cdot  \left(1-x_2\right)^{n-2} \\&=& 1 - \left(1-y_2\right)^{n} - n y_2 \left(1-y_3\right)^{n-1}
\end{eqnarray}$$
Now
$$
 \begin{eqnarray}
    \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n}\right) &=&  1 - \mathbb{E}\left(  \left(1-Y_{2:n}\right)^{n} \right) - n \mathbb{E}\left( Y_{2:n} \left(1-Y_{3:n}\right)^{n-1}\right) \\
  &=& 1 - \mathbb{E}\left(  Y_{n-1:n}^{n} \right) - n \mathbb{E}\left( Y_{2:n} \left(1-Y_{3:n}\right)^{n-1}\right)
\end{eqnarray}
$$
The latter integral is easy to evaluate:
$$
\begin{eqnarray}
  n \mathbb{E}\left( Y_{2:n} \left(1-Y_{3:n}\right)^{n-1}\right) &=& \int_0^{1} \mathrm{d}y_3 \int_0^{y_3} \mathrm{d} y_2 \cdot n^2(n-1)(n-2) y_2^2 (1-y_3)^{2n-4}  \\
  &=& \frac{n^2 (n-1)(n-2)}{ \frac{1}{2} (2n)(2n-1)(2n-2)(2n-3)} \int_0^{1} \mathrm{d}y_3 \int_0^{y_3} f_{Z_{3:2n},Z_{4:2n}}\left(y_2,y_3\right) \\
  &=& \frac{n(n-2)}{2 (2n-1)(2n-3)}
\end{eqnarray}
$$
The remaining integral is evaluated using singe statistics density function:
$$
  \mathbb{E}\left(  Y_{n-1:n}^{n} \right) = \int_0^1 x^n \cdot n(n-1) x^{n-2} (1-x) \mathrm{d} x = \frac{n(n-1)}{2n(2n-1)} \int_0^1 f_{Y_{2n-1:2n}}(x) \mathrm{d}x =  \frac{n-1}{2(2n-1)}
$$
Thus
$$
   \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n}\right) = 1-\frac{n-1}{2(2n-1)}-\frac{n(n-2)}{2 (2n-1)(2n-3)}=\frac{(5n-4)(n-1)-1}{2(2n-1)(2n-3)}
$$


TITLE: Polarization of the Jacobian variety
QUESTION [4 upvotes]: I'm walking towards the Torelli's Theorem.I started from scratch! I did not even know what a divisor was in a Riemann surface. I currently went through Abel's Theorem, theta divisor... Now I am reading the proof of the following theorem:
Theorem 2.25: The theta divisor $\Theta$ of the Jacobian variety $J(R)$, the subvariety $W^{g-1}$ and Riemann's constant are related by following equality:
$\Theta=W^{g-1} + [k]$.
In the reference I'm using https://www.amazon.com/Advances-Moduli-Translations-Mathematical-Monographs/dp/0821821563
After this theorem 2.25 is written: This theorem implies that the polarization of the Jacobian variety
is given by the line bundle $[W^{g-1}]$.
I need to read about polarization of the Jacobian variety. Right now I have another very good reference Compact Riemann surfaces  (Raghavan Narasimhan), But I did not find out about polarization of the Jacobian variety in this book.
I would like references on the subject. Thank you!

REPLY [4 votes]: Perhaps http://jmilne.org/math/articles/1986c.pdf helps you. Theorem 6.6 is the principal polarisation of the Jacobian.


TITLE: Counter-example: Cauchy Riemann equations does not imply differentiability
QUESTION [10 upvotes]: I need help with this exercise:

Let $$ f(z) = \left\{ \begin{align}
&e^{-\frac{1}{z^4}}  &\hspace{1mm} \mbox{if} \hspace{1mm} z \neq 0 \\
&0  &\hspace{1mm} \mbox{if} \hspace{1mm} z = 0 \\
\end{align} \right. $$ Show that $f$ satisfies Cauchy-Riemann equations, but $f$ is not differentiable in $z=0$.

I have to compute $u_x(x,y)$, $u_y(x,y)$, $v_x(x,y)$ and $v_y(x,y)$, so I have to find $u(x,y)$ and $v(x,y)$ explicitly. My attempts: if $z = x+iy$, then $z^4 = (x+iy)^4$, doing the math, I found
$$ z^4 = (x^4 - 6x^2y^2 + y^4)+i(4x^3y - 4xy^3) $$
I don't know how to find $-\dfrac{1}{z^4}$. My second attempt was this: (trying to find $f(z)$ in polar coordinates) let be $z = |z|e^{i\theta}$, then $z^4 = |z|^4e^{i(4\theta)}$, thus
$$ e^{-\frac{1}{z^4}} = e^{-|z|^4}e^{e^{i\theta}} $$
I appreciate any idea you have.

REPLY [12 votes]: The function $f$ is analytic off the origin, hence satisfies the CR equations at all $z\ne0$. For $z=0$ look at
$$f_x(0,0)=\lim_{x\to0}{e^{-1/x^4}\over x}=0\ ,$$
and similarly
$$f_y(0,0)=\lim_{y\to0}{e^{-1/(iy)^4}\over y}=0\ .$$
It follows that $u_x(0,0)=v_x(0,0)=u_y(0,0)=v_y(0,0)=0$; so $f$ satisfies the CR equations also at $z=0$.
But $f$ is not even continuous at $z=0$: Consider the points $z(t):=(1+i)t$ for real $t$ near $0$. I leave the details to you.


text:
\begin{document}
\maketitle
\begin{abstract}
Graphs triangulating the $2$-sphere are generically rigid in $3$-space, due to Gluck-Dehn-Alexandrov-Cauchy. We show there is a \emph{finite} subset $A$ in $3$-space so that the vertices of each graph $G$ as above can be mapped into $A$ to make the resulted embedding of $G$ infinitesimally rigid. This assertion extends to the triangulations of any fixed compact connected surface, where the upper bound obtained on the size of $A$ increases with the genus. The assertion fails, namely no such finite $A$ exists, for the larger family of all graphs that are generically rigid in $3$-space and even in the plane.
\end{abstract}

\section{Introduction}
A theorem of Dehn asserts that the $1$-skeleton of every simplicial convex $3$-polytope is infinitesimally rigid \cite{Dehn}. Combined with Steinitz theorem, this gives Gluck's result that the $1$-skeleton of any simplicial $2$-sphere is \emph{generically} rigid in $\R^3$ \cite{Gluck}, i.e., the locus of realizations that are not infinitesimally rigid is of codimension one in the configuration space of all possible locations. See~\cite{Connelly:RigiditySurvey} and \cite{Pak-book} for further references and discussion.

\\
We ask the following question:
How generic does the embedding of a generically rigid graph need to be to guarantee that it is infinitesimally rigid?

\\
We give a natural precise meaning to this meta question, and partially answer it for various families of graphs, including the one mentioned above.

Let us first recall some notions pertaining to infinitesimal rigidity:

An embedding of a graph $G=(V,E)$ into $\R^d$
is any map $f: V\rightarrow \R^d$ such that $f(V)$ affinely spans $\R^d$; it defines a realization of the edges in $E$ by segments via linear extension, this realization is called the \emph{framework} $f(G)$.
A \emph{motion} of $f(G)$ is any assignment
of velocity vectors $a:V\rightarrow \R^d$ that satisfies
\begin{equation} \label {eq:infi-rigidity}
\langle a(v)-a(u),f(v)-f(u)\rangle=0
\end{equation}
 for every edge $uv \in E$. A motion $a$ is \emph{trivial} if the relation (\ref{eq:infi-rigidity}) is satisfied for {\em every pair} of vertices; otherwise $a$ is \emph{nontrivial}.
The framework $f(G)$ is \emph{infinitesimally rigid} if all its motions are trivial.
Equivalently, (\ref{eq:infi-rigidity}) says that the velocities preserve infinitesimally the distance
along an embedded edge,  and if  (\ref{eq:infi-rigidity}) applies to all pairs of
vertices then the velocities necessarily correspond to a rigid motion of the entire space.

We now arrive at the central definition of this note, quantifying the genericity of the embedding needed for an infinitesimally rigid embedding.
\begin{definition}\label{def:c}
Let $F$ be a family of graphs. We say $F$ is \emph{$d$-rigid with $c$-locations} if there exists a set $A\subseteq \mathbb{R}^d$ of cardinality $c$ such that for any graph $G=(V(G),E(G))\in F$ there exists a map $f:V(G)\rightarrow A$ such that the framework $f(G)$ is infinitesimally rigid. Denote by $c_d(F)$ the minimal such $c$.
\end{definition}
We are interested in the question whether a given infinite family of finite graphs, which is known to be generically infinitesimally $d$-rigid (namely, $d$-rigid with $\aleph_0$-locations),

is also $d$-rigid with $c$-locations, for some \emph{finite} $c$.

Clearly, the answer is yes iff \emph{any} \emph{generic} set $A$ will do in  Definition~\ref{def:c}, i.e. any $A$ where the $c\times d$ entries of its vectors are algebraically independent over the rational numbers.
Perhaps surprisingly, we show:

\begin{theorem}[Dehn-Gluck theorem with few locations]\label{thm:2-spheres}
Let $F(S^2)$ be the family of $1$-skeleta of all triangulations of the $2$-sphere. Then $F(S^2)$ is $3$-rigid with $76$-locations. Namely, $c_3(F(S^2))\leq 76$.
\end{theorem}

The phenomenon in Theorem~\ref{thm:2-spheres} generalizes to any surface, orientable or not: let $F(S)$ be the family of $1$-skeleta of all triangulations of compact connected surfaces, and let $F(g)$ be the subfamily when fixing the surface of genus $g$ (orientable or  non-orientable genus). Fogelsanger proved that any graph in $F(S)$ is generically $3$-rigid \cite{Fogelsanger}.

\begin{theorem}\label{thm:S_g}
For any $g$, $c_3(F(g))$ is finite.
\end{theorem}
\iffalse
In fact, Fogelsanger showed more generally that the $1$-skeleton of any \emph{minimal cycle complex} (defined in the Preliminaries) of dimension $d\ge 2$ is generically $(d+1)$-rigid. Our results on surfaces extend to this context as well: let $FOG(b)$ be the family of $2$-dimensional minimal cycle complexes with \emph{socle} of dimension at most $b$ in the Artinian reduction of their Stanley-Reisner ring over the reals. This provides a natural generalization of genus in terms of intersection homology, and we obtain:
\begin{theorem}\label{thm:FOG}
For any $b>0$, $c_3(FOG(b))$ is finite.
\end{theorem}
\fi

We now consider the larger family of all generically $3$-rigid graphs. Some well-known open problems are to characterize this family by combinatorial means, and, concretely, whether there exists a deterministic polytime algorithm to decide if a given graph is generically $3$-rigid; see e.g. the survey \cite{Jackson-Jordan06:3Drigidity}.

Let $F_d$ be the family of all generically d-rigid finite graphs.

Note that for $d=1$, $F_1$ is the family of connected graphs, so considering a spanning tree for $G\in F_1$ shows $c_1(F_1)=2$.
Perhaps not surprisingly, $F_d$ is quantitatively more complicated for any $d\ge 2$, as shown also by Fekete and Jordan~\cite[Sec.4]{Fekete-Jordan} for $d=2$:
\begin{theorem}\label{thm:no_c(F_d)}
For any $d\ge 2$ and any finite $c$, $F_d$ is \emph{not} $d$-rigid with $c$-locations.
\end{theorem}

Let us remark that infinitesimal rigidity for (slightly) non-generic embeddings has been considered in the literature, for subfamilies of triangulated spheres and manifolds -- in the centrally symmetric case and in the balanced case, see e.g. Stanley~\cite{Stanley-CSpolytopes,Stanley-balancedCM} (phrased in the language of face rings), for convex position, see e.g. Izmestiev and Schlenker~\cite{Izmestiev-Schlenker}, and for embeddings on small grids~\cite{Fekete-Jordan} -- however, the problem of embedding with a constant number of locations, seems to be new.

\textbf{Outline}:
Preliminaries are given in Section~\ref{sec:prelim}.
We prove Theorem~\ref{thm:no_c(F_d)} in Section~\ref{sec:all}, Theorem~\ref{thm:2-spheres} in Section~\ref{sec:2-spheres}, Theorem~\ref{thm:S_g} in Section~\ref{sec:surfaces},

and conclude with open questions in Section~\ref{sec:conclude}.

\section{Preliminaries}\label{sec:prelim}

\subsection{Complexes and polytopes.}
We set some notation: the \emph{link} of a face $\sigma$ in a simplicial complex $X$ is the subcomplex $\lk_{\sigma}(X)=\{\tau\in X:\ \sigma\cap\tau=\emptyset,\ \sigma\cup\tau\in X \}$ and its (open) star is the filter $\st_{\sigma}(X)=\{\tau\in X: \sigma \subseteq \tau\}$; the set of all $l$-dimensional faces ($l$-faces for short) of $X$ is $X_l$ and its \emph{$l$-skeleton} is the subcomplex $X_{\le l}=\cup_{i\le l}X_i$.
The \emph{geometric realization} of $X$ is denoted by $|X|$; we say $X$ is a \emph{simplicial $d$-sphere / surface} if $|X|$ is a topological $d$-sphere / surface.

A $d$-dimensional polytope is \emph{simplicial} if any face in its boundary is a simplex; it is \emph{$k$-neighborly} if any subset of its vertices of size $k$ is the vertexset of some face of it; it is \emph{stacked} if it is either a $d$-simplex, or can be obtained from a stacked $d$-polytope by gluing on one of its $(d-1)$-faces a $d$-simplex.

\subsection{Rigidity}
The rigidity matrix of the framework $f(G)$, of a graph $G=(V,E)$ and an embedding $f:V\rightarrow \R^d$, is the $d|V|\times|E|$ real matrix where in the column of edge $vu\in E$ the entries in the $v$-rows are $f(v)-f(u)$, in the $u$-rows are $f(u)-f(v)$, and the other entries in this column are zero; denote this matrix by $R(f(G))$. When $|V|=n>d$, the rank of $R(f(G))$ is always
$\le dn-\binom{d+1}{2}$, and equality holds iff $f(G)$ is infinitesimally rigid.

The space of \emph{affine $2$-stresses},

or simply \emph{stresses}, of a framework $f(G)$ of a graph $G=(V,E)$ is
the real vector space
\[\{(w_{\sigma})\in \mathbb{R}^{E}: \forall \tau\in V,\ \ \sum_{\tau \in \sigma}w_{\sigma}(f(\sigma\setminus\tau)-f(\tau))=\overrightarrow{0} \}.\]
The space of affine $2$-stresses of $f(G)$ is exactly the kernel of the rigidity matrix $R(f(G))$.

For $G$ the $1$-skeleton of a simplicial $2$-sphere with $n$ vertices, it has $3n-6$ edges, and thus for $f:V\rightarrow \mathbb{R}^3$, $f(G)$ is infinitesimally rigid iff its only affine $2$-stress is the trivial (all zero) stress.

\section{All $d$-rigid graphs}\label{sec:all}
Clearly, for $F'_d \subseteq F_d$ the subfamily of \emph{minimally} generically infinitesimally $d$-rigid graphs, $c_d(F_d)=c_d(F'_d)$. For $d=2$, $F'_2$ is the family of the well studied Laman graphs.

Theorem~\ref{thm:no_c(F_d)} for $d=2$ was proved in~\cite[Sec.4]{Fekete-Jordan}, we give their short argument for completeness: Suppose by contradiction that $c=c_2(F'_2)$ is finite, and let $G$ be a Laman graph that is $2$-rigid with $c$-locations but not with $(c-1)$-locations. We may assume $|V(G)|=n>c$ (as any Laman graph is a strict subgraph of another Laman graph), so for any map $f:V(G)\rightarrow A$, $|A|=c$, $A \subset \mathbb{R}^2$, there exist two vertices $w,u\in V(G)$ with $f(w)=f(u)$.
Let $G'$ be obtained from $G$ by adding for each pair of vertices $x,y \in V(G)$  a new vertex $v=v(x,y)$ and two new edges $vx$ and $vy$.
Then $G'$ is Laman because $G'$ is obtained from $G$ by Henneberg moves, and these moves preserve the property of being Laman.
Assume by contradiction that there exists a map $f_{G'}:V(G')\rightarrow A$ with $|A|=c$ and $f_{G'}(G')$ infinitesimally rigid.
Consider $x,y \in V(G)$ with $f_{G'}(x)=f_{G'}(y)$ and the vertex $v=v(x,y)$.
Let $a(v)$ be any non-zero vector perpendicular to $f_{G'}(x)-f_{G'}(v)=f_{G'}(y)-f_{G'}(v)$, and let $a(w)=0$ for every vertex $w\neq v$. Then $a$ is a non-trivial infinitesimal motion of $G'$, which is a contradiction.

\textbf{Case $d>2$}: First proof: Argue similarly to the $d=2$ case, when adding a new vertex $v(B)$ for any $d$-subset $B\subseteq V(G)$, and connecting $v(B)$ to all vertices in $B$, to obtain $G'$ from $G\in F'_d$, where $G$ requires $c=c_d(F'_d)$ locations.

Second proof: Restrict to repeated cones over Laman graphs, forming a subfamily $F''_d$ of $F'_d$, so $c_d(F''_d)\le c_d(F'_d)\le c_d(F_d)$. By the Cone Lemma (see e.g.~\cite{TayWhiteWhiteley-Skel2Cone}), any $G\in F''_d$ is minimally generically infinitesimally $d$-rigid, and projection gives that $c_2(F'_2)\le c_d(F''_d)$, so by the $d=2$ case, $c_d(F_d)$ is infinite.
$\square$

\section{Graphs of simplicial $2$-spheres}\label{sec:2-spheres}
The proof of Theorem~\ref{thm:2-spheres} requires
the following couple of simple facts: let $G$ be a maximal planar graph on at least $5$ vertices, equivalently $G$ is the $1$-skeleton of a triangulation of the $2$-sphere different from the boundary of a tetrahedron.
\begin{lemma}\label{lem:deg3,4,5}
$G$ has a vertex of degree $\in\{3,4,5\}$.
\end{lemma}
\begin{proof}
By Euler's formula, the average degree is $<6$, and by maximality of $G$ it is $\ge 3$.
\end{proof}
\begin{lemma}\label{lem:starhole}
For any vertex $v\in G=(V,E)$, there is an edge $uv\in G$ such that the contraction of $v$ to $u$ yields a graph $G'=(V-\{v\},E')$ which is again the $1$-skeleton of a triangulation of the $2$-sphere.
\end{lemma}
The contraction as above is defined by the edgeset $E':=(E\setminus \{e\in E:\ v\in e\})\cup\{uw:\ vw\in E, w\neq u \}$.
This lemma too should be known; as we failed to find a reference we provide a proof.
\begin{proof}

Let the vertices in $\lk_v(G)$ be $u_1,u_2,\ldots,u_t$ in the cyclic order. We need to show that for some $i$, $u_iu_j\notin G$ for any $j\neq i+1,i-1 \mod{t}$, namely that $vu_i$ is not part of a missing triangle of the sphere triangulation (a.k.a. separating triangle). Then $u=u_i$ is good.

This follows from planarity, and is even simpler to argue when $\deg(v)\in\{3,4,5\}$, which suffices for our purposes:
if $\deg(v)=3$ then any $u_i$ is good. If $\deg(v)=4,5$, if $u_i$ is not good then w.l.o.g. by relabeling $(\mod t)$ $u_iu_{i+2}\in G$, so planarity shows that $u=u_{i+1}$ is good (and there exists another $u_j$ which is good as well).
\end{proof}

The proof of Theorem~\ref{thm:2-spheres} follows by showing:

\begin{theorem}\label{thm:24}
Let $A$ be a generic subset of $\R^3$, $|A|=76$. Then for any graph $G\in F(S^2)$ there exists a function $f_G:V(G)\rightarrow A$ such that

(R) the framework $f_G(G)$ is infinitesimally $3$-rigid, and

(C) for any subgraph $H\subseteq G$ of a subcomplex that triangulates a $4-$ or $5-$gon, the restriction of $f_G$ to $V(H)$ is injective.
Equivalently, for any subcomplex which is a disc consisting of up to $3$ triangles, $f_G$ is injective on its vertices.
\end{theorem}
For Theorem~\ref{thm:2-spheres} we only need (R), however, for our inductive proof to work we require (C) as well.
The theorem clearly holds if $|V(G)|\le 76$. Assume $|V(G)|>76$, let $v\in G$ be a vertex of degree $3,4$ or $5$ (it exists by Lemma~\ref{lem:deg3,4,5}), and let $uv\in G$ such that the contraction of $v$ to $u$ gives a smaller graph $G'\in F(S^2)$ ($u$ exists by Lemma~\ref{lem:starhole}).
By the induction hypothesis, there exists a function $f_{G'}$ satisfying (R) and (C) for $G'$; we will show that $f_{G'}$ can be extended to a function $f_G$ as required. We just need to show that $A$ has enough room so that $f_G(v)$ can be defined so that (R) and (C) hold for $G$.

We loose nothing by assuming that $f_{G'}$ has an image of smallest possible size.

To achieve (C), $f_G(v)$ just needs to avoid the values of $f_G$ on all the vertices (i) in the link $\lk_G(v)$, (ii) in triangles without $v$ that share an edge with triangles with $v$, and (iii) in triangles without $v$ that share an edge with triangles that share an edge with triangles with $v$.
Thus, when $\deg(v)=3$ (resp. $4$; resp. $5$), $f_G(v)$ needs to avoid a set $N$ of at most $12$ (resp. $16$; resp. $20$) values in $A$, so if $|A|>20$, we can define $f_G(v)$ so that (C) is satisfied.

We now turn to the rigidity requirement (R).
Let $c(G)$ (resp. $C(G)$) be the minimum size $c$ such that $G$ is $3$-rigid with $c$-locations (resp. and with $f_G:V(G)\rightarrow A$, $|A|=c$, satisfying property (C) as well). Thus $c(G)\leq C(G)$, hence it is enough to show that for $G,G'\in F(S^2)$ as above, $C(G)\le \max(C(G'),76)$.

Let $f_{G'}:V(G')\rightarrow A$ with $|A|=C(G')$ satisfy (R) and (C) of Theorem~\ref{thm:24}.

\textbf{First}, we notice that $f_{G'}$ has an extension ${f}_G: V(G)\rightarrow A\cup\{a\}$, with ${f}_G(v)=a$ not necessarily in $A$, such that ${f}_G(G)$ is rigid.
This follows by combining (C) with a closer look at Whiteley's proof of the Contraction Lemma~\cite{Whiteley-split}; rephrased here suitably.

\begin{proposition}[Contraction Lemma]\label{prop:WhiteleylikeContraction}
Let $vu$ be an edge in $G=(V,E)$ and assume that $u$ and $v$ have two
common neighbors $a$ and $b$. Contract $v$ to $u$ to obtain graph $G'=(V-v,E')$.
Let $f:V-v \rightarrow \mathbb{R}^3$ such that

(i) $f(G')$ is infinitesimally rigid, and

(ii) $f(a),f(b),f(u)$ are all different.\\
Then there exists an extension $f(v)$ of $f$ to $V$, such that the framework $f(G)$ is infinitesimally rigid.
\end{proposition}
To guarantee (ii) in our case, we need that $f_{G'}$ is injective on the restriction to the subgraph $H=\lk_v(G)$ of $G'$,

so (C) for $f_{G'}$ implies (ii).

\textbf{Second}, we show that in fact $f_G(v)$ can
be chosen in $A$ so that resulted $f_G$ is as required in the theorem.
We need the following crucial fact:

\begin{proposition}\label{prop:key}
Let $v\in G$ be a vertex of degree $\le b$, $A\subseteq \mathbb{R}^3$ a generic subset of size $\ge \binom{b+3}{3}$, $f: V(G)\rightarrow \mathbb{R}^3$ such that $f(V(G)\setminus\{v\})=A$ and $f(G)$ is infinitesimally rigid.

Then there exists another map $f': V(G)\rightarrow A$ that agrees with $f$ on $V(G)\setminus\{v\}$, and such that $f'(G)$ is infinitesimally rigid.
\end{proposition}
\begin{proof}
Consider the rigidity matrix
$R(f_G(G);x,y,z)$ of the framework $f_G(G)$, where $f_G(v)$ is a vector with \emph{variable} entries $(x,y,z)$. As we assumed that for some assignment $f_G(G)$ is infinitesimally rigid then, for $|V|\ge 4$, at least one of the determinants of $(3|V|-6)\times(3|V|-6)$-minors in $R(f_G(G);x,y,z)$ is nonzero; denote by $P$ such determinant. Then $P$ is a nonzero polynomial in the variables $x,y,z$ of degree at most $b$ (as $v$ is incident to at most $b$ edges).
The dimension of the space of all such polynomials is $\binom{b+3}{3}$.

Then, as $A$ is generic, no choice of different $\binom{b+3}{3}$ points in $A$ make the determinant $P$ vanish on each of the points. To see this,
put the coefficients of the polynomial $P$ into a vector $U$. Consider the $\binom{b+3}{3}$ by $\binom{b+3}{3}$ matrix $M$, where the entries of the $j$-th row are the values of our $\binom{b+3}{3}$ monomials computed using the coordinates of the $j$-th point, $(x_j,y_j,z_j)$. The determinant of $M$ is then a non-zero polynomial in $x_1,\ldots, x_{\binom{b+3}{3}}, y_1,\ldots,y_{\binom{b+3}{3}}, z_1,\ldots,z_{\binom{b+3}{3}}$ with rational coefficients.

Since our points are generic, it follows that $\det(M)\neq 0$.

On the other hand, if the value of $P$ at each of our $\binom{b+3}{3}$ points is $0$, then $MU=0$. Hence $U=0$, a contradiction, as $P$ is a nonzero polynomial.

As $|A|\ge \binom{b+3}{3}$ there is a choice $f_G(v)\in A$ as desired.
\end{proof}

Summarizing, to guarantee both (C) and (R) for $f_G(G)$, $f_G(v)$ needs to avoid at most $20+(\binom{8}{5}-1)=75$ values in $A$, which is possible for $|A|=76$.

This completes the proof that $c_3(F(S^2))\le 76$.  $\ \ \square$
\\

Variations on the above proof give stronger upper bounds for subfamilies of $F(S^2)$, which we consider next. In the rest of this section we keep the notation used in Theorem~\ref{thm:24} and its proof.

\begin{proposition}\label{prop:stacked}
The family of $1$-skeleta of \emph{stacked} $d$-polytopes is $d$-rigid with $(d+1)$-locations, but not with $d$-locations.

In particular, for the subfamily $T\subseteq F(S^2)$ of graphs of stacked $3$-polytopes, $c_3(T)=4$.
\end{proposition}
\begin{proof}[Proof sketch.]
For $v$ a vertex of degree $d$, its contraction gives the graph $G'$ of a stacked polytope. Letting $f_G(v)$ be different from the $f_G$-values of the neighbors of $v$ makes $f_G(G)$ rigid, by say the Gluing Lemma~\cite{Asimow-Roth2, Whiteley96-SomeMatroids}, or simply by inspecting the rigidity matrix of $f_G$.
\end{proof}

Note that the assertion of Proposition~\ref{prop:stacked} extends to any $d$-polytope whose $1$-skeleton contains the $1$-skeleton of a stacked $d$-polytope as a spanning subgraph. There are numerous such examples, e.g.~\cite{Shemer,Padrol}, and in particular:
\begin{corollary}\label{cor:2-nei}
The family of $1$-skeleta of \emph{2-neighborly} $d$-polytopes is $d$-rigid with $(d+1)$-locations, but not with $d$-locations.
\end{corollary}

Next we consider the subfamily $Q\subseteq F(S^2)$ of graphs that can be reduced to the complete graph $K_4$ by always contracting vertices of degree $\le 4$, obtaining a smaller triangulation of the $2$-sphere at each step.
\begin{proposition}
$c_3(Q)\le 10$.

In fact, any generic subset $A$ of $\R^3$ of size $10$ satisfies that for any graph $G\in Q$
there exists a function $f_G:\ V(G)\rightarrow A$ such that

(R') the framework $f_G(G)$ is infinitesimally $3$-rigid, and

(C') for any subgraph $H\subseteq G$ of a subcomplex that triangulates a $4$-gon, the restriction of $f_G$ to $V(H)$ is injective.
Equivalently, for any subcomplex which is a disc consisting of $2$ triangles, $f_G$ is injective on its vertices.
\end{proposition}
\begin{proof}

Contract a vertex $v\in G$ of degree $\le 4$ to vertex $u$ so that $G'$ is in $Q$.
Again, we extend $f_{G'}$ to $f_G$.
For $(C')$ to hold for $f_G$, $f_G(v)$ needs to avoid a subset $N$ of at most $8$ points in $A$.

To achieve also $(R')$, we show that for any two points $x,y\in A\setminus N$, either $f_G(v)=x$
or $f_G(v)=y$ provides the desired extension.

Note that removing an edge from $G'$ creates
a nontrivial infinitesimal motion, unique up to scaling,
say $M_{G'}:V(G')\rightarrow\mathbb{R}^3$, so for the right choice of an edge $e$ this is the nontrivial motion for the induced framework of the graph $G-v$. Then $M_{G'}$ does not preserve the distance between the vertices of $e$ up to first order. Note that the vertices of $e$ belong to $\lk_v(G)$.

Tentatively define $f_G(v)=x$; it may allow an extension of the motion $M_{G'}$ on $G'$ to $G$ for suitable $M_G(v)=v_x$. Similarly when tentatively defining $f_G(v)=y$ and $M_G(v)=v_y$. Assume by contradiction that both options extend the motion $M_{G'}$. As $M_{G'}$ is unique (up to nonzero scalar multiplication), we will get a nontrivial infinitesimal motion $M$ on the octahedron $O$ with antipodal vertices $x,y$ and equator $4$-cycle $f_G(\lk_v(G))$, by setting $M(x)=v_x, M(y)=v_y$ and $M(f_G(u))=M_{G'}(u)$ for any $u\in \lk_v(G)$.
As all $6$ vertices of $O$ are in different points of $\mathbb{R}^3$, and as $A$ is generic, by Gluck's theorem $O$ is infinitesimally rigid; a contradiction.

\end{proof}

\section{Graphs of surfaces}\label{sec:surfaces}
Barnette and Edelson~\cite{BE88,BE89} have shown that for any given compact surface $M$, the number of its \emph{irreducible} triangulations, namely those where no edge can be contracted to give a (smaller) triangulation of $M$, is finite. More strongly, and useful for our purposes, Schipper~\cite{Schipper91} has shown the following, using the Barnette-Edelson results.
\begin{lemma}(\cite[Lem.9]{Schipper91})\label{lem:Schipper}
For any compact $2$-manifold $M$ there exists a constant $n_0(M)\in \mathbb{N}$ such that any triangulation $\Delta$ of $M$, with $n>n_0(M)$ vertices, contains a vertex $v$ of degree at most $6$ such that
$v$ has a neighbor $u$ such that the contraction of $v$ to $u$ results in a (smaller) triangulation $\Delta'$ of $M$; equivalently, $vu$ is in no missing triangle of $\Delta$.
\end{lemma}

\begin{remark}~\label{rem:n_0(g)}
In fact, the argument in Schipper's proof shows more: for some $0<\epsilon <1$, independent of $M$, at least $\epsilon n$ such vertices $v$ exist. However, $\{n_0(M)\}_M$ is of course unbounded, as the minimal number of vertices needed to triangulate a surface grows with the genus.

\end{remark}

With Lemma~\ref{lem:Schipper} at hand, we can prove Theorem~\ref{thm:S_g} in the same spirit of the

proof of Theorem~\ref{thm:24}.

Let $\Delta_{\leq 1}$ denote the $1$-skeleton of a triangulation $\Delta$.
 Let $n>n_0(M)$ and contract $v$ to $u$ as in Lemma~\ref{lem:Schipper}. We need to verify that infinitesimal rigidity of the framework $f_{\Delta'_{\le 1}}(\Delta'_{\le 1})$ implies the existence of an extension $f_{\Delta_{\le 1}}(v)\in A$ that makes $f_{\Delta_{\le 1}}(\Delta_{\le 1})$ infinitesimally rigid. For this we first use Proposition~\ref{prop:WhiteleylikeContraction}; in order to apply it we need the following condition to hold, which guarantees that condition (ii) in the proposition holds:

(C") any $2$-ball $B$ in $\Delta'$ made of at most $4$ triangles with a common vertex has $f_{\Delta'_{\le 1}}$ injective on the vertices of $B$.

(Indeed,

the contraction of $v$ as in Lemma~\ref{lem:Schipper},

replaces its star by such ball $B$.)

For (C") to hold for $f_{\Delta_{\le 1}}(\Delta_{\le 1})$, $f_{\Delta_{\le 1}}(v)$ needs to avoid at most $48=6+6+12+24$ values in $A$.

Now, by Propositions~\ref{prop:WhiteleylikeContraction} and~\ref{prop:key} for $b=6$ we finish the proof as before:

among any $\binom{9}{3}=84$ points in $A$, there will be a point $a$ such that $f_{\Delta_{\le 1}}(v)=a$ makes the rigidity matrix of $\Delta_{\le 1}$ full rank.
Thus, by avoiding at most $48+83=131$ values in $A$, both (R) and (C") are guaranteed, given $n>n_0(M)$.
Thus, $c_3(F(g))\le \max(n_0(M),132)$.  $\square$

Note that when the (orientable or non-orientable) genus of $M$ tends to infinity, so does $n_0(M)$ (see Remark~\ref{rem:n_0(g)}). We do not know if $\{c_3(F(g))\}_g$ is bounded.

\iffalse
\section{Graphs of minimal cycles}\label{sec:FOG}

Consider now a (strongly) minimal homology $2$-cycle, i.e.\ a simplicial complex of dimension $2$ that has but a single homology cycle in dimension $2$, and is minimal with that property.

\begin{proposition}
A weakly minimal cycle that is not strongly minimal is a union of two smaller weakly minimal cycles that share a triangle.
\end{proposition}

\begin{corollary}
A weakly minimal cycle is a weakly minimal cycle in characteristic zero.
\end{corollary}

The \emph{degeneracy} of $\mu$ is the difference of the dimension of space of linear $2$-stresses and the dimension of the space of linear $1$-stresses. Algebraically, this quantity measures the distance of the underlying intersection ring from a Poincar\'e duality algebra. We denote it by $\delta(\mu)$.

The \emph{singular set} of a minimal cycle $\mu$ is the subcomplex of faces at which the underlying complex of their star is \emph{not} a manifold; as such, it is a subgraph of $\mu$, denote it by $S(\mu)$. For a vertex $v$ in particular, let us denote by $m_v$ the number of connected components in the link of $v$.

\begin{proposition}
For a strongly minimal cycle $\mu$, we have
\[\delta(\mu)\ =\ 3(\beta_1(|\mu|)-2\sum_{v\ \text{vertex in}\ \mu} (m_v-1)\ \ge\ \beta_1(|\mu|).\]
\end{proposition}

\begin{proof}
If $v$ is a vertex with $m_v\ge 2$, then we can disconnect $\mu$ at this vertex by introducting $m_v$  vertices $(v_1,\dots,v_{m_v})$ whose links are the connected components of the link of $v$ in $\mu$. This increases the first Betti number by $(m_v-1)$.

In this process, we have decreased $\delta(\mu)$ by $\sum_{v\ \text{vertex in}\ \mu} (m_v-1)$. The remaining cycle $\mu'$ is Buchsbaum, so in terms of its Betti number, \cite{Novik} gives
\[\delta(\mu')\ = \ 3(\beta_1(|\mu'|).\]
\end{proof}

\karim{I leave the proof of the following to you}
\begin{lemma}
For every $\delta_0 \ge 0$, there exists an $N=N(\delta_0)$ such that every minimal
$2$-cycle with
$\delta(\mu)\le \delta_0$ and number of vertices greater than $N$ has a vertex of degree $\le 6$
\end{lemma}

\begin{proof}
If all vertices of $\mu$ are of degree $7$ or higher, then $\delta(\mu)$ tends to infinity as the number of vertices grows.
\end{proof}

\karim{the rest is mine again}
There are now two situations: Once we have identified a vertex $v$ of degree $6$ or less is contained in a contractible edge (i.e. an edge that is contained in no empty triangle.) In that case, we conclude
We can contract such an edge, ultimately ending up with a number of locations depending only on $\delta_0$; so again finite locations suffice.

If an edge is not contractible, i.e., it is contained in an empty triangle $\Delta$, then following Fogelsanger, $\mu$ decomposes into two smaller minimal cycles, $\mu_0$ and $\mu_1$. Now, we note that $\mu_0$ and $\mu_1$ can only intersect in a graph. Moreover, no cycle in that graph, apart from $\Delta$ can be contractible in both $\mu_0$ and $\mu_1$ since $\mu$ is minimal. Hence, the dimension of linear degree $2$ stresses in their intersection is at most $2\beta_1(\mu)$. Hence, the number of degree $1$ stresses in the intersection of $\mu_0$ and $\mu_1$ is at most $3\delta(\mu)$.

Hence, we can decompose $\mu$ into strictly smaller cycles of smaller deficiency, and we can induct in this way.

Let us close the section by remarking that the dependence on degeneracy in Theorem \ref{thm:FOG} is necessary.

\begin{theorem}
There is no finite number of locations in $\R^3$ such that every minimal $2$-cycle can be realized with vertices in these locations.
\end{theorem}

\begin{proof}
The proof follows the idea in the first proof of Theorem~\ref{thm:no_c(F_d)}.

Indeed, assume that $c$ locations are enough to guarantee that every minimal $2$-cycle can be realized  in an infinitesimally rigid way. Consider a minimal $2$-cycle $\mu$ that requires $c$ locations.

Consider secondly the boundary of a tetrahedron $\Delta$, and mark the four vertices by $0,1,2$ and $3$. We subdivide the triangle $\{123\}$ with a triangle $\Gamma$ that bisects its edges, as well as the triangles incident to $0$. Denote the resulting subdivision of $\Delta$ by $\Delta'$. (Thus, $\Delta'$ has 7 vertices and 10 triangles.)

Totally order the triples of vertices in $\mu$. According to this order,
for every triple of vertices of $\mu$, attach a new copy of $\Delta'$ along the vertices $1$, $2$ and $3$ to the currently constructed complex $\mu'$ (starting with the original $\mu$), then remove $\Gamma$ and some triangle of $\mu'$, and connect both along a simplicial tube.

The resulted complex $\mu''$ is also a minimal $2$-cycle, and contains the $1$-skeleton of $\mu$, thus also requires $c$ location; however it has more vertices. Repeating this process, can can assume $\mu$ has more than $c$ vertices, so it has a triple of vertices $T$ occupying at most two locations, and with the copy $w$ of $0\in \Delta$ corresponding to $T$, all $4$ vertices $T\cup\{w\}$ are contained in an affine plane $P$. Now, in $\mu''$, assign $w$ a nonzero velocity perpendicular to $P$, and zero velocity to all other vertices; this is a nontrivial motion on the $1$-skeleton of $\mu''$, a contradiction.
\end{proof}
\fi

\iffalse
\section{Planar Laman graphs}\label{sec:PlanarLaman}
Consider the subclass of Laman graphs which are also planar, a.k.a. pointed pseudo-triangulations by the main result of~\cite{planarMinimallyRigid05}. Unlike the class of all Laman graphs (see Theorem~\ref{thm:no_c(F_d)}), this subclass admits rigidity with few locations in the plane:

\begin{theorem}\label{thm:PlanarLaman}
Let $A\subseteq \R^2$ be a generic subset of size $|A|=44$. Then for any planar Laman graph $G=(V,E)$ there exists a map $f:V(G)\rightarrow A$ for which the framework $f(G)$ is infinitesimally rigid.
\end{theorem}
\eran{Better bound on $|A|$?}
\begin{proof}
The proof is by induction on the sequence of Henneberg moves used to construct $G$ from the single-edge graph $K_2=G_0$, denoted $G_0,G_1,\ldots,g_t=G$.
Identify $A\cong A'\times [4]$ for some generic subset $A'\subseteq \R^2$ of size $|A'|=11$.
Suppose, by induction, that the map $f_{i-1}=(\pi,c):V(G_{i-1})\rightarrow A'\times [4]$ both

(R) makes $\pi(G_{i-1})$ infinitesimally rigid (hence the same holds for $f_{i-1}(G_{i-1})$), and

(C) $c$ is injective (hence so is $f_{i-1}$) on the restriction to the the 2 or 3 vertices of $V(G_{i-1})$ involved in the next Henneberg move, i.e. to $N(v)$ the set of neighbors of the unique vertex $v$ in $V(G_i)\setminus V(G_{i-1})$.

We now extend $f_{i-1}$ to $f_i=(\pi',c'):V(G_i)\rightarrow A'\times [4]$ satisfying (R) and (C).

The Henneberg move of type (I) connects $v$ to any subset $N(v)$ of size two; then by avoiding any of the two locations $f_{i-1}(N(v))$
\end{proof}
\fi

\section{Concluding remarks}\label{sec:conclude}
Regarding simplicial spheres, does a higher dimensional analog of Theorem~\ref{thm:2-spheres} hold? Namely,
\begin{problem}
Let $F(S^{d-1})$ be the family of $1$-skeleta of triangulations of the $(d-1)$-sphere. For $d>3$, is $F(S^{d-1})$ $d$-rigid with $c$-locations for some finite $c$? Namely, is $c_d(F(S^{d-1}))$ finite?
\end{problem}

Regarding surfaces, does a uniform bound in Theorem~\ref{thm:S_g} hold? Namely, for $F(S)$, the family of all graphs of compact connected surfaces, we ask:
\begin{problem}
Is $c_3(F(S))$ finite?
\end{problem}
We remark that for the larger family of Fogelsanger's minimal cycle complexes~\cite{Fogelsanger}, and even for the intermediate family which still contains $F(S)$, of complexes minimal with respect to containment among those supported by homology $2$-cycles, rigidity with few locations fails:
\begin{theorem}
There is no finite set of locations in $\R^3$ such that every minimal $2$-cycle can be realized with vertices in these locations in an infinitesimally rigid way.
\end{theorem}

\begin{proof}
The proof follows the idea in the first proof of Theorem~\ref{thm:no_c(F_d)}.

Indeed, assume that $c$ locations are enough to guarantee that every minimal $2$-cycle can be realized  in an infinitesimally rigid way. Consider a minimal $2$-cycle $\mu$ that requires $c$ locations.

Consider secondly the boundary of a tetrahedron $\Delta$, and mark the four vertices by $0,1,2$ and $3$. We subdivide the triangle $\{123\}$ in some way that
introduces exactly 3 new vertices, all in its interior, which form
a triangle $\Gamma$ (in the interior of the triangle $\{123\}$). Denote the resulting subdivision of $\Delta$ by $\Delta'$.

Totally order the triples of vertices in $\mu$. According to this order,
for every triple of vertices of $\mu$, attach a new copy of $\Delta'$ along the vertices $1$, $2$ and $3$ to the currently constructed complex $\mu'$ (starting with the original $\mu$), then remove $\Gamma$ and some triangle of $\mu'$, and connect both along a simplicial tube.

The resulted complex $\mu''$ is also a minimal $2$-cycle, and contains the $1$-skeleton of $\mu$, thus also requires $c$ locations; however it has more vertices. Repeating this process, we can assume $\mu$ has more than $2c$ vertices, so it has a triple of vertices $T$ occupying at most one location, and with the copy $w$ of $0\in \Delta$ corresponding to $T$, all $4$ vertices $T\cup\{w\}$ are contained in an affine plane $P$. Now, in $\mu''$, assign $w$ a nonzero velocity perpendicular to $P$, and zero velocity to all other vertices; this is a nontrivial infinitesimal motion on the $1$-skeleton of $\mu''$, a contradiction.
\end{proof}

Regarding Theorem~\ref{thm:no_c(F_d)}, while the phenomenon of rigidity with few locations does not hold for Laman graphs in the plane, Walter Whiteley asked us whether it does hold for the subfamily of planar Laman graphs, see~\cite[Thm.1]{PlanarLaman2005} for an equivalent characterization via pointed pseudo-triangulations.
We leave this question open.
\begin{problem}
Let $F$ be the family of planar Laman graphs. Is $c_2(F)$ finite?
\end{problem}

Given that rigidity with few locations holds, it is interesting to find optimal bounds. For $F(S^2)$, note that the vertices of the octahedron must occupy 6 different locations in $\R^3$ in any infinitesimally rigid embedding, thus $c_3(F(S^2))\ge 6$.
\begin{problem}\label{prob:PlanarLaman}
For every surface $M$, what is the value $c_3(F(M))$? At least, find improved bounds.
\end{problem}

In this note we considered infinitesimal rigidity with $c$-locations, for $c$ a constant. More generally, for a family $F$ of generically $d$-rigid graphs, let $F(n)$ be the subfamily of graphs in $F$ with at most $n$ vertices, and let $c_{d,F}(n)$ be the minimum $c$ such that $F(n)$ is $d$-rigid with $c$-locations. One can study the growth of the function $c_{d,F}(n)$.

\begin{problem}
For $F_3$, the family of all generically $3$-rigid graphs, what is the asymptotic growth of $c_{3,F_3}(n)$? Is it sublinear in $n$?
\end{problem}
Let us remark that for $G$ a minimally $d$-rigid graph, the chromatic number $\chi(G)$ of $G$ is a lower bound for $c_{d,F_d}(n)$, as infinitesimal $d$-rigidity forces the vertices of any edge to occupy two different locations. However, as any induced subgraph $G'=(V',E')$ of $G$ supports no nontrivial stress, $G'$ must satisfy $|E'|\leq d|V'|$, hence $G$ is $(2d-1)$-degenerate, so $\chi(G)\leq 2d$, and we get no growth with $n$ in the lower bound on $c_{d,F_d}(n)$ by using the chromatic number.

\section*{Acknowledgments}
We thank Isabella Novik and Orit Raz for helpful discussions, and Bob Connelly, Louis Theran and Walter Whiteley for helpful comments and references.
We thank the referee for valuable advice, resulted in greatly improved presentation.
K.A. was supported by ERC StG 716424 - CASe and ISF Grant 1050/16.
E.N. was partially supported by ISF grant 1695/15, by ISF-NRF joint grant 2528/16 and by ISF-BSF joint grant 2016288.

\newcommand{\etalchar}[1]{$^{#1}$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }

\providecommand{\MRhref}[2]{
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}

config: arxiv


TITLE: Physical examples where changing the order of limits yields wrong result
QUESTION [5 upvotes]: In mathematics it is generally not allowed to change order of limits. For example it is not always true for a sequence of functions $f_n$, that $\int_a^b \left(\sum_{n=0}^\infty f_n(x) \right) dx = \sum_{n=0}^\infty \left(\int_a^b f_n(x) dx\right)$. (Note that series $\sum_{n=0}^\infty\ldots$ and the integral $\int_a^b \ldots dx$ are mathematically defined via limits of sequences).
In my experience it happens a lot in physics lectures, that limits are changed in their order without any additional comment (such as mentioning Fubini's theorem or uniform convergence). It also seems to me that there are not many examples relevant for physics where changing the order of limits yield wrong results.
I'm looking for good physical examples showing to students that one has to be careful when he changes the order of limits. So for which physical example the order of the limits is important and you get a wrong result, when you change it?

REPLY [3 votes]: The low-frequency ($\omega\rightarrow 0$), long-wavelength ($q\rightarrow 0$) conductivity of an electron gas in the random phase approximation depends on the order in which those two limits are taken.
Intuitively, if you take the $\omega\rightarrow 0$ limit first, you're talking about a static, long-wavelength potential to which the electrons adjust, so the conductivity is imaginary (non-dissapative).  If you take the $q\rightarrow 0$ limit first, you're talking about a uniform, slowly varying field applied to the gas, so you get a current (real conductivity).  See page 27 of these notes for a discussion.
Basically, you order the limits one way to learn about Thomas-Fermi screening, and the other way to learn about DC currents.  Changing the limits here is not "wrong" per se, but it may get you an answer to a question you didn't ask!


TITLE: Intuition behind Snake Lemma
QUESTION [58 upvotes]: I've been struggling with this for some time. I can prove the Snake Lemma, but I don't really “understand” it. By that I mean if no one told me Snake Lemma existed, I would not even attempt to prove it. I believe I am missing some important intuition that tells me that the lemma “could” be true before actually trying to prove it. Please give me some pointers.

REPLY [19 votes]: All these diagram chasing lemmas (snake lemma, $3x3$ lemma, four lemma, five lemma, etc.) follow directly from the "salamander lemma" due to George Bergman, see salamander lemma.
And that is pretty transparent. It is so transparent that for instance it is immediate to see (which no textbook ever mentions) that there are just as easily 4x4 lemmas, 5x5 lemmas, 6x6 lemmas. etc. In other words: once you see the simple idea of the salamander lemma, you can come up yourself with more such diagram chasing lemmas at will.