text:
\begin{document}

\begin{abstract} In this short note we prove that, in dimension three, flat metrics are the only complete metrics with non-negative scalar curvature which are critical for the $\sigma_{2}$-curvature functional.
\end{abstract}

\maketitle

\begin{center}

\noindent{\it Key Words: critical metrics, quadratic functionals, rigidity results}

\medskip

\centerline{\bf AMS subject classification:  53C24, 53C25}

\end{center}

\

\section{Introduction}

Let $(M^{n},g)$ be a Riemannian manifold of dimension $n\geq 3$. To fix the notation, we recall the decomposition of the Riemann curvature tensor of a metric $g$ into the Weyl, Ricci and scalar curvature component
$$
Rm \,= \, W + \frac{1}{n-2} Ric \kn g - \frac{1}{(n-1)(n-2)}R \, g \kn g \,,
$$
where $\kn$ denotes the Kulkarni-Nomizu product. It is well known~\cite{hilbert} that Einstein metrics are critical points for the Einstein-Hilbert functional
$$
\mathcal{H} \,=\, \int R \,dV
$$
on the space of unit volume metrics $\M1(M^{n})$. From this perspective, it is natural to study  canonical metrics which arise as solutions of the Euler-Lagrange equations for more general curvature functionals.  In~\cite{berger3}, Berger commenced the study of Riemannian functionals which are quadratic in the curvature (see~\cite[Chapter 4]{besse} and~\cite{smot} for surveys). A basis for the space of quadratic curvature functionals is given by
$$
\mathcal{W} \,=\, \int |W|^{2} dV\, \quad \mathcal{\rho} \,=\, \int |Ric|^{2} dV\, \quad\, \mathcal{S} \,=\, \int R^{2} dV \,.
$$
All such functionals, which also naturally arise as total actions in certain gravitational field theories in physics, have been deeply studied in the last years by many authors, in particular on compact Riemannian manifolds with normalized volume (for instance, see~\cite{berger3, besse, lamontagne2, lamontagne1, ander2, gurvia3, gurvia1, gurvia2, cat3} and references therein).

On the other hand, the study of critical metrics for quadratic curvature functionals also has a lot of interest in the non-compact setting. For instance, Anderson in~\cite{ander3} proved that every complete three-dimensional critical metric for the Ricci functional $\mathcal{\rho}$ with non-negative scalar curvature is flat, whereas in~\cite{cat2} the first author showed a characterization of complete critical metrics for $\mathcal{S}$ with non-negative scalar curvature in every dimension.

In this paper we focus our attention on the three dimensional case and consider the $\sigma_{2}$-curvature functional
$$
\mathscr{F}_{2} \,=\, \int \sigma_{2}(A) \, dV \,,
$$
where $\sigma_{2}(A)$ denotes the second elementary symmetric function of the eigenvalues of the Schouten tensor $A = Ric - \frac{1}{4}R\,g$. This functional was first considered by Gursky and Viaclovsky in the compact three dimensional case. In~\cite{gurvia3} they proved a beautiful characterization theorem of space forms as critical metrics for $\mathscr{F}_{2}$ on $\M1(M^{3})$ with non-negative energy $\mathscr{F}_{2}\geq 0$.

The main result of this paper is the following variational characterization of three dimensional flat spaces.

\begin{teo}\label{t-main}
Let $(M^{3},g)$ be a complete critical metric for $\mathscr{F}_{2}$ with non-negative scalar curvature. Then $(M^{3},g)$ is flat.
\end{teo}

We remark the fact that the non-negativity condition on the scalar curvature cannot be removed. This is clear from the example in~\cite{gurvia3} where the authors exhibit an explicit
family of critical metrics for $\mathscr{F}_{2}$ on $\mathbb{R}^{3}$. For instance, the metric given in standard coordinates by
$$
g \,=\, dx^{2} + dy^{2} + \big(1+x^{2}+y^{2}\big)^{2} dz^{2}
$$
is complete, critical and has strictly negative scalar curvature $R=-\frac{8}{1+x^{2}+y^{2}}$.

\

\section{The Euler-Lagrange equation for $\Ft$} \label{s-euler}

In this section we will compute the Euler-Lagrange equation satisfied by critical metrics for $\mathscr{F}_{2}$. To begin, we observe that, in dimension $n\geq 3$, the second elementary symmetric function of the eigenvalues of the Schouten tensor
$$
A \,=\, \frac{1}{n-2} \Big( Ric - \frac{1}{2(n-1)} R\,g\Big)
$$
can be written as
$$
\sigma_{2}(A) \,=\, -\frac{1}{2(n-2)^{2}}|Ric|^{2}+\frac{n}{8(n-1)(n-2)^{2}}R^{2} \,.
$$
In particular, the functional $\mathscr{F}_{2}$ is proportional to a general quadratic functional of the form
$$
\Ft \,=\, \int |Ric|^{2} dV +  t \int R^{2}  dV \,,
$$
with the choice $t=-\frac{n}{4(n-1)}$ (see also~\cite{gurvia1, cat3}). The gradients of the functionals $\mathcal{\rho}$ and $\mathcal{S}$, computed using compactly supported variations, are given by (see~\cite[Proposition 4.66]{besse})
$$
(\nabla \mathcal{\rho})_{ij} \,=\, -\Delta R_{ij} - 2 R_{ikjl}R_{kl}+\nabla^{2}_{ij} R - \frac{1}{2}(\Delta R)g_{ij} + \frac{1}{2} |Ric|^{2} g_{ij} \,,
$$

$$
(\nabla \mathcal{S})_{ij} \,=\, 2 \nabla^{2}_{ij} R - 2(\Delta R) g_{ij} -2 R R_{ij} + \frac{1}{2} R^{2} g_{ij} \,.
$$
Hence, the gradient of $\Ft$ reads
$$
(\nabla \Ft)_{ij} \,=\, -\Delta R_{ij} +(1+2t)\nabla^{2}_{ij} R - \frac{1+4t}{2}(\Delta R)g_{ij} + \frac{1}{2} \Big( |Ric|^{2}+ t R^{2}\Big) g_{ij} - 2 R_{ikjl}R_{kl} -2t R R_{ij} \,.
$$
Tracing the equation $(\nabla \Ft) = 0$, we obtain
$$
 \Big(n+4(n-1)t\Big)\Delta R \,=\,(n-4)\Big(|Ric|^{2}+ t R^{2}\Big) \,.
$$
Defining the tensor $E$ to be the trace-less Ricci tensor, $E_{ij} = R_{ij} - \frac{1}{n} R g_{ij}$, we obtain the Euler-Lagrange equation of critical metrics for $\Ft$.

\begin{prop}\label{p-eulern}
Let $M^{n}$ be a complete manifold of dimension $n\geq 3$. A metric $g$ is critical for $\Ft$ if and only if it satisfies the following equations
\begin{eqnarray*}
\Delta E_{ij} &=&  (1+2t) \nabla^{2}_{ij} R - \frac{n+2+4nt}{2n} (\Delta R) g_{ij} - 2 R_{ikjl} E_{kl} -\frac{2+2nt}{n} R E_{ij} \\&&+  \frac{1}{2}\Big( |Ric|^{2}-\frac{4-n(n-4)t}{n^{2}} R^{2} \Big) g_{ij} \,,
\end{eqnarray*}
\begin{equation*}
\Big(n+4(n-1)t\Big)\Delta R \,=\, (n-4) \Big( |Ric|^{2} + t R^{2} \Big) \,.
\end{equation*}
\end{prop}

In dimension three we recall the decomposition of the Riemann curvature tensor
$$
R_{ikjl} \,=\, E_{ij}g_{kl}-E_{il}g_{jk}+E_{kl}g_{ij}-E_{kj}g_{il} + \frac{1}{6}\, R \,(g_{ij}g_{kl}-g_{il}g_{jk}) \,.
$$
In particular, one has
$$
R_{ikjl} E_{kl} \,=\, -2 E_{ip}E_{jp} -\frac{1}{6}R E_{ij} +  |E|^{2}g_{ij} \,.
$$

Hence, if $n=3$ and $t=-n/4(n-1)=-3/8$, one has
$$
\mathscr{F}_{2} \,=\, -\frac{1}{2} \mathcal{F}_{-3/8} \,,
$$
and the following formulas hold.

\begin{prop}\label{p-euler3}
Let $M^{3}$ be a complete manifold of dimension three. A metric $g$ is critical for $\mathscr{F}_{2}$ if and only if it satisfies the following equations
\begin{eqnarray}\label{eq1}
\Delta E_{ij} \,=\,  \frac{1}{4} \nabla^{2}_{ij} R - \frac{1}{12} (\Delta R) g_{ij} + 4 E_{ip} E_{jp} +\frac{5}{12} R E_{ij} -\frac{1}{2}\Big(3|E|^{2} - \frac{1}{72} R^{2}\Big) g_{ij} \,,
\end{eqnarray}

\begin{equation} \label{eq2}
-2\,\sigma_{2}(A) \,=\,  |Ric|^{2} - \frac{3}{8} R^{2}  \,=\, |E|^{2} - \frac{1}{24}R^{2} \,=\, 0 \,.
\end{equation}
\end{prop}

Now, contracting equation~\eqref{eq1} with $E$ we obtain the following Weitzenb\"ock formula.

\begin{cor}
Let $M^{3}$ be a complete manifold of dimension three. If $g$ is a critical metric for $\mathscr{F}_{2}$, then the following formula holds
\begin{equation}\label{eq-w}
\frac{1}{2}\Delta |E|^{2} \,=\,  |\nabla E|^{2} + \frac{1}{4} E_{ij}\nabla^{2}_{ij} R +4 E_{ip} E_{jp}E_{ij} +\frac{5}{12} R |E|^{2} \,.
\end{equation}
\end{cor}

\

\section{Proof of Theorem~\ref{t-main}}

In this section we will prove Theorem~\ref{t-main}. We  assume that $(M^{3},g)$ is a critical metric for $\mathscr{F}_{2}$ with non-negative scalar curvature $R\geq 0$. In particular, $g$ has zero $\sigma_{2}$-curvature, i.e. $|E|^{2} = \frac{1}{24} R^{2}$ and we obtain
$$
\frac{1}{2} \Delta |E|^{2} \,=\, \frac{1}{48} \Delta R^{2} \,=\, \frac{1}{24} R \Delta R + \frac{1}{24} |\nabla R|^{2} \,.
$$
Putting together this equation with~\eqref{eq-w}, we obtain that the scalar curvature $R$ satisfies the following PDE

\begin{equation}\label{eq-pde}
\frac{1}{24} \Big( R g_{ij} - 6 E_{ij} \Big) \nabla^{2}_{ij} R \,=\, |\nabla E|^{2} - \frac{1}{24}|\nabla R|^{2} + 4 E_{ip} E_{jp}E_{ij} +\frac{5}{12} R |E|^{2} \,.
\end{equation}

To begin, we need the following purely algebraic lemmas.

\begin{lemma} \label{l1}
Let $(M^{3},g)$ be a Riemannian manifold with $R\geq 0$ and $\sigma_{2}(A) \geq 0$. Then,
$$
R g_{ij} \,\geq\, 6 E_{ij}
$$
and $g$ has non-negative sectional curvature.
\end{lemma}
\begin{proof} Let $\lambda_{1}\leq \lambda_{2} \leq \lambda_{3}$ be the eigenvalues of the Schouten tensor $A=E + \frac{1}{12} R g $ at some point. Then, by assumptions, we have
$$
4 R \,=\, tr(A) \,=\, \lambda_{1} + \lambda_{2} + \lambda_{3} \,\geq\, 0 \quad \quad \hbox{and}\quad \quad  \sigma_{2}(A)\,=\,\lambda_{1} \lambda_{2} + \lambda_{1}\lambda_{3} +\lambda_{2} \lambda_{3} \geq 0 \,.
$$
We want to show that $E \leq \frac{1}{6} R g$ or, equivalently, that
$$
 A \,\leq\, \frac{1}{4} R g \,=\, \hbox{tr}(A) g \,.
$$
Hence, it is sufficient to prove that $\lambda_{3} \leq \hbox{tr}(A) = \lambda_{1} + \lambda_{2} + \lambda_{3}$, i.e. $\lambda_{1} + \lambda_{2} \geq 0$. But this follows by
$$
0 \,\leq\, \lambda_{1} \lambda_{2} + \lambda_{1}\lambda_{3} +\lambda_{2} \lambda_{3} \,=\, ( \lambda_{1} + \lambda_{2} ) \hbox{tr}(A) - (\lambda_{1}^{2} + \lambda_{2}^{2}+\lambda_{1}\lambda_{2} ) \,\leq\, ( \lambda_{1} + \lambda_{2} ) \hbox{tr}(A) \,.
$$
The fact that $g$ has non-negative sectional curvature follows from the decomposition of the Riemann tensor in dimension three and the curvature condition $Ric \,\leq\, \frac{1}{2} R g $ (for instance see~\cite[Corollary 8.2]{hamilton1}).
\end{proof}

\begin{lemma}\label{l2}
Let $(M^{3},g)$ be a Riemannian manifold with $R\geq 0$ and $\sigma_{2}(A) = \hbox{const} \geq 0 $. Then,
$$
|\nabla E|^{2} \,\geq\, \frac{1}{24}|\nabla R|^{2} \,.
$$
\end{lemma}
\begin{proof} We will follow the proof in~\cite[Lemma 4.1]{gurvia3}. Let $p$ be a point in $M^{3}$. If $R(p)=0$, then $\nabla R=0$ and the lemma follows. So we can assume that $R(p)>0$. Since $-2\,\sigma_{2}(A)= |E|^{2} - \frac{1}{24} R^{2} = const$, one has
\begin{equation}\label{eqp}
|E|^{2} |\nabla |E||^{2} \,=\, \frac{1}{576} R^{2} |\nabla R|^{2} \,.
\end{equation}
By Kato's inequality $|\nabla |E||^{2} \leq |\nabla E|^{2}$ and the fact that $|E|^{2} \leq \frac{1}{24} R^{2}$, we obtain
$$
|E|^{2} |\nabla E|^{2} \, \geq \, \frac{1}{576} R^{2} |\nabla R|^{2} \,\geq \, \frac{1}{24} |E|^{2} |\nabla R|^{2} \,.
$$
Dividing by $|E|^{2}(p)\neq 0$ the result follows, otherwise, if $|E|(p)=0$, $(\nabla R)(p)=0$ from equation~\eqref{eqp}, and we conclude.
\end{proof}

\begin{lemma}\label{l3}
Let $(M^{3},g)$ be a Riemannian manifold. Then,
$$
E_{ip} E_{jp}E_{ij} \,\geq\, - \frac{1}{\sqrt{6}} |E|^{3} \,.
$$
\end{lemma}
\begin{proof} For a proof of this lemma, for instance, see~\cite[Lemma 4.2]{gurvia3}.
\end{proof}

\begin{cor}\label{c-pdesub}
Let $(M^{3},g)$ be a complete critical metric for $\mathscr{F}_{2}$ with non-negative scalar curvature. Then, $R g_{ij} \geq 6 E_{ij}$, $g$ has non-negative sectional curvature and the scalar curvature satisfies the following differential inequality
$$
 \Big( R g_{ij} - 6 E_{ij} \Big) \nabla^{2}_{ij} R \,\geq\, \frac{1}{12} R^{3} \,.
$$
\end{cor}
\begin{proof} From equation~\eqref{eq-pde}, combining lemmas~\ref{l1}~\ref{l2} and~\ref{l3}, we obtain
$$
\frac{1}{24}\Big( R g_{ij} - 6 E_{ij} \Big) \nabla^{2}_{ij} R \, \geq\, \frac{5}{12} R |E|^{2} -\frac{4}{\sqrt{6}} |E|^{3} \,=\, |E|^{2} \Big( \frac{5}{12}R - \frac{4}{\sqrt{6}} |E| \Big) \,=\, \frac{1}{288} R^{3} \,,
$$
where in the last equality we have used the fact that $|E|^{2} = \frac{1}{24} R^{2}$.
\end{proof}

Now we can prove Theorem~\ref{t-main}. Clearly, if $M^{3}$ is compact, from Corollary~\ref{c-pdesub}, at a maximum point of $R$ we obtain $R\leq 0$. Hence, $R\equiv 0$ on $M^{3}$ and from equation~\eqref{eq2}, $Ric\equiv 0$ and the metric is flat. So, from now on, we will assume the manifold $M^{3}$ to be non-compact.

Choose now $\phi=\phi(r)$ be a function of the distance $r$ to a fixed point $O\in M^{3}$ and let $B_{s}(O)$ be a geodesic ball of radius $s>0$. We denote by $C_{O}$ the cut locus at the point $O$ and we choose $\phi$ satisfying the following properties: $\phi=1$ on $B_{s}(O)$, $\phi=0$ on $M^{3} \setminus B_{2s}(O)$ and
$$
-\frac{c}{s} \phi^{3/4} \,\leq\, \phi' \,\leq\, 0  \quad \quad \hbox{and} \quad \quad |\phi''| \,\leq\, \frac{c}{s^{2}} \, \phi^{1/2} \,
$$
on $B_{2s}(O) \setminus B_{s}(O)$ for some positive constant $c>0$. In particular, $\phi$ is $C^{3}$ in $M^{3}\setminus C_{O}$. Let $u := R \phi$ and $a_{ij}:= \Big( R g_{ij} - 6 E_{ij} \Big)$. From Corollary~\ref{c-pdesub}, we know that $a_{ij}\geq 0$ and we obtain
\begin{eqnarray} \label{eqn3}
 a_{ij} \nabla^{2}_{ij} u &=& a_{ij} \Big( \phi \nabla^{2}_{ij}R + R \nabla^{2}_{ij} \phi + 2 \nabla_{i}R \nabla_{j} \phi \Big) \\ \nonumber
 &\geq& \frac{1}{12} R^{3} \phi + R \phi' a_{ij} \nabla^{2}_{ij} r + R \phi'' a(\nabla r, \nabla r) + 2 a(\nabla R, \nabla \phi) \,.
\end{eqnarray}
Now, let $p_{0}$ be a maximum point of $u$ and assume that $p_{0}\notin C_{O}$. If $\phi(p_{0})=0$, then $u\equiv 0$ and then $R\equiv 0 $ on $B_{2s}(O)$. Hence, from now on we will assume  $\phi(p_{0})>0$. Then, at $p_{0}$, we have $\nabla u (p_{0})=0$ and $\nabla^{2}_{ij} u (p_{0}) \leq 0$. In particular, at $p_{0}$, one has
$$
\nabla R (p_{0}) \,=\, -\frac{R(p_{0})}{\phi(p_{0})} \nabla \phi (p_{0}) \,.
$$
Moreover, since $a_{ij} \geq 0$, for every vector field $X$, one has $a(X,X) \leq \hbox{tr}(a)|X|^{2} = 3 R |X|^{2}$. On the other hand, from standard Hessian comparison theorem, since $g$ has non-negative sectional curvature, we know that on $M^{3}\setminus C_{O}$, one has $ \nabla^{2}_{ij} r \,\leq\, \frac{1}{r} g_{ij} \,.$ Thus, from equation~\eqref{eqn3}, at $p_{0}$, we get
\begin{eqnarray*}
0 &\geq & \frac{1}{12} R^{3} \phi + R \phi' a_{ij} \nabla^{2}_{ij} r + R \phi'' a(\nabla r, \nabla r) - 2 \frac{R}{\phi} a(\nabla \phi, \nabla \phi) \\
&\geq & \frac{1}{12} R^{3} \phi - \Big(\frac{|\phi'|}{r}+|\phi''| + 2 \frac{(\phi')^{2}}{\phi} \Big)R \, \hbox{tr}(a) \\
&\geq & \frac{1}{12} R^{3} \phi - 3\Big(\frac{|\phi'|}{s}+|\phi''| + 2 \frac{(\phi')^{2}}{\phi} \Big) R^{2} \,,
\end{eqnarray*}
where, in the last inequality, we have used the fact that $r\geq s$ on $B_{2s}(O)\setminus B_{s}(O)$, i.e. where $\phi' \neq 0$. From the assumptions on the cut-off function $\phi$, we obtain, at the maximum point $p_{0}$
$$
0 \,\, \geq \,\, \frac{1}{12} R^{2} \phi^{1/2} \Big( R\phi^{1/2} - \frac{c'}{s^{2}} \Big)
$$
for some positive constant $c'>0$. Thus, we have proved that, if $p_{0} \notin C_{O}$, then for every $p\in B_{2s}(O)$
$$
u(p)\,\leq \,u(p_{0}) \,=\, R(p_{0}) \phi (p_{0}) \,\leq\, \frac{c'}{s^{2}}\,.
$$
If $p_{0}\in C_{O}$ we argue as follows (this trick is usually referred to Calabi). Let $\gamma:[0,L] \rightarrow M^{3}$, where $L=d(p_{0},O)$, be a minimal geodesic joining $O$ to $p_{0}$, the maximum point of $u$. Let $p_{\eps}=\gamma(\eps)$ for some $\eps>0$. Define now
$$
u_{\eps}(x) \,=\, R (x)\phi \big(d(x,p_{\eps})+\eps\big)\,.
$$
Since $d(x,p_{\eps})+\eps\geq d(x,O)$ and $d(p_{0},p_{\eps}) + \eps = d(p_{0},O)$, it is easy to see that $u_{\eps}(p_{0}) = u (p_{0})$ and
$$
u_{\eps}(x) \,\leq \, u(x) \quad\quad\hbox{for all }\,x \in M^{3} \,,
$$
since $\phi'\leq 0$. Hence $p_{0}$ is also a maximum point for $u_{\eps}$. Moreover, $p_{0}\notin C_{p_{\eps}}$, so the function $d(x,p_{\eps})$ is smooth in a neighborhood of $p_{0}$ and we can apply the maximum principle argument as before to obtain an estimate for $u_{\eps}(p_{0})$ which depends on $\eps$. Taking the limit as $\eps\rightarrow 0$, we obtain the desired estimate on $u$.

By letting $s\rightarrow +\infty$ we obtain $u\equiv 0$, so $R\equiv 0$. From equation~\eqref{eq2} we have $E\equiv 0$ and so $Ric\equiv 0$ and Theorem~\ref{t-main} follows.

This concludes the proof of Theorem~\ref{t-main}.

\

\

\begin{ackn} The authors are members of the Gruppo Nazionale per
l'Analisi Matematica, la Probabilit\`{a} e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM). The first author is supported by the GNAMPA project ``Equazioni di evoluzione geometriche e strutture di tipo Einstein''. The second and the third authors are supported by the GNAMPA project ``Analisi Globale ed Operatori Degeneri''. The third author is partially supported by FSE, Regione Lombardia.
\end{ackn}

\

\bibliographystyle{amsplain}
\bibliography{biblio}

\bigskip

\parindent=0pt

\

\end{document}


TITLE: Closed formula for Pokémon Go evolutions
QUESTION [3 upvotes]: In the game Pokémon Go, you need a fixed number of candies to evolve one Pokémon belonging to a given species. However, when you transfer the evolved Pokémon, it gives you one candy back. For instance, a pidgey costs 12 candies to evolve. If you start with 498 such candies, you can evolve 41 pidgeys on the first round, 3 on the second round, and 1 on the last round, resulting in 45 evolutions.
I can easily write an iterative algorithm to calculate that:
def evolve_and_transfer(candies, evolution_cost):
    result = 0
    i = 1
    while candies >= evolution_cost:
        (evolutions, candies) = divmod(candies, evolution_cost)
        print("Round %s: %s evolutions, %s candies remain." % (i, evolutions, candies))
        candies += evolutions
        result += evolutions
        i += 1
    return result

assert evolve_and_transfer(498, 12) == 45

But I wonder whether there exists a closed formula which calculates the same function, and could be implemented without loops.

REPLY [5 votes]: Took a little longer than a few hours ;P
As I said in the comments, Perdu's formula
$$
E = \begin{cases}
0 & \text{if $A=0$}\\
\left\lfloor\frac{A-1}{N-1}\right\rfloor & \text{otherwise}
\end{cases}
$$
is correct. The basic idea here is as follows:

If you have at least $N$ candies, then you are permitted to evolve at least once, for an effective cost of $N-1$ candies.
If you have at least $2N-1=(N-1)+N$ candies you are allowed to evolve at least twice: use the $+N$ candies first, receive $+1$ additional candy, and then use the remaining $(N-1)+1=N$ candies to evolve once more, for an effective cost of $2N-2$ candies.
If you have at least $3N-2=(2N-2)+N$, you are allowed to evolve at least three times: use the $+N$ candies first, receive $+1$ additional candy, and then repeat the procedure in the previous step, for an effective cost of $3N-3$ candies.

This looks like a recursive process, so you use induction to show that if you have at least $E(N-1)+1$ candies, you can perform at least $E$ evolutions for an effective cost of $E(N-1)$ candies. [This argument is not hard, but it's also basically the same argument I made in the third bullet point, so I'll skip it.]
It follows that if you want to have exactly $E$ evolutions, you need to be able to evolve at least $E$ times, but not at least $E+1$ times, which means that
$$ E(N-1)+1\leq A<(E+1)(N-1)+1. $$
This is equivalent to
$$ E\leq \frac{A-1}{N-1}<E+1, $$
and that is precisely what the notation $E=\left\lfloor\frac{A-1}{N-1}\right\rfloor$ means.

Why does the $A=0$ case fail in this chain of reasoning? Well, our base case on the induction starts at $E=1$, which means that you cannot substitute $E=0$ into the double inequality. Thus cannot get the desired lower bound, and so you have no guarantee that the floor function describes the situation. So in fact we have to handle the case $A<N$ separately, but of course the problem tells us that in this case (including $A=0$), we cannot evolve at all; that is, $E=0$.
It is convenient that for $0<A<N$, zero happens to be equal to $\left\lfloor\frac{A-1}{N-1}\right\rfloor$, so that we can hide this corner case in the notation, but alas, the $A=0$ subcase still requires special treatment.

Amusing consequence:

Proposition. Fix $N$ and $A$ positive integers, and let $a_n$ be a sequence defined by $a_0=A$ and $$a_{n+1} = a_n - (N-1)\left\lfloor\frac{a_n}{N}\right\rfloor$$
  Then
  $$\sum_{n=0}^\infty \left\lfloor\frac{a_n}{N}\right\rfloor = \left\lfloor\frac{A-1}{N-1}\right\rfloor.$$

Proof: the sequence $a_n$ is the number of candies left after performing $n$ rounds of evolutions, and hence both sides count the number of evolutions.


TITLE: Is it possible to directly measure the expectation value of a physical observable without measuring the entire probability distribution?
QUESTION [4 upvotes]: The expectation value of a physical observable in a given state is just a single real scalar quantity. On the other hand, the probability distribution of the eigenvalues of the observable is a set of $N$ numbers, where $N$ is the dimensionality of the Hilbert space. My question is the following: is it possible to measure only the expectation value of an observable without having to measure the entire probability distribution of its eigenvalues?
P.S: I am not looking for answers that make any additional assumptions, or approximations, or that apply only in specific cases.

REPLY [2 votes]: I'm not sure how general of an answer you want, but here's an explicit proof it can't be done for standard measurements of Hermitian operators. Consider an arbitrary operator $A$ and suppose we want to measure its expected value by measuring some other operator $B$.
Now, no matter what state we're in, measuring $B$ should always give us a definite value, the expectation value. This is only possible if every vector is an eigenvector of $B$, with the eigenvalue (the corresponding measured value) equal to $\langle A \rangle$. That is, we want
$$B | v \rangle = \langle v | A | v \rangle |v \rangle.$$
We know for sure that if $A$ has a definite value, then $B$ should also have that same definite value,
$$A | v \rangle = \lambda |v \rangle \quad \rightarrow \quad B |v \rangle = \lambda |v \rangle.$$
But since $A$ is Hermitian, it has a complete basis of eigenvectors, so this constraint alone completely determines $B$; it must be equal to $A$. So this 'expected value' operator can't exist.


TITLE: second theorem of Minkowski proof
QUESTION [1 upvotes]: I am wondering if anyone have a proof of second theorem of Minkowski.
He says that if $vol(K) = 2^{n} det(L)$ and $K$ is compact and symmetric and convex then $K$ contains a non zero lattice point. I would appreciate your help.
Thanks!

REPLY [1 votes]: Let me take the slightly stronger condition $\mathrm{vol}(K) > 2^n \det(L)$, rather than $\mathrm{vol}(K) = 2^n \det(L)$. (You can then use the fact that $K$ is compact to argue that equality actually suffices.) By applying a linear transformation, let's also assume that $L$ is the integer lattice $\mathbb{Z}^n$, so that we simply have $\mathrm{vol}(K) > 2^n$. (This step isn't necessary at all, but I think it makes the proof easier to understand.)
For vectors $x,x' \in \mathbb{R}^n$, let's write $x \equiv x' \mathbb{Z}^n$ if $x - x' \in \mathbb{Z}^n$. (I.e. $x$ and $x'$ have coordinates with the same fractional part.) Suppose that there exists distinct $x, x' \in K/2$ such that $x \equiv x' \bmod \mathbb{Z}^n$. Then, $x - x' \in \mathbb{Z}^n$ by definition, and $x - x' \neq 0$ because $x$ and $x'$ are distinct. However, by symmetry, $-x' \in K/2$, and by convexity, $(x-x')/2 \in K/2$ so that $x - x'$ is a non-zero lattice vector in $K$.
It therefore remains to find such an $x, x' \in K/2$. To that end, we simply notice that for every $x \in \mathbb{R}^n$, there is a unique representative $f(x) \equiv x \bmod \mathbb{Z}^n$ with $f(x) \in [0,1)^n$. Notice that the map $x$ is a piecewise combination of volume-preserving maps. So, if $f$ is an injective mapping when restricted to $K/2$, then we must have
$$\mathrm{vol}(f(K/2)) = \mathrm{vol}(K/2) = 2^{-n}\mathrm{vol}(K) > 1
; .
$$
But, this can't be true, since the entire image of $f$ is $[0,1)^n$, which has volume $1$. Therefore, $f$ is not injective over $K/2$. I.e., there exist distinct $x,x' \in K/2$ such that $f(x) = f(x')$, as needed.
Edit: For what it's worth, this is typically referred to as Minkowski's first theorem. His second theorem finds a set of linearly independent vectors satisfying a certain constraint.


TITLE: Major errors in an inclusion-exclusion application to counting twin primes in a certain interval.
QUESTION [0 upvotes]: Let $a,b,n,q$ all be odd numbers, and let $p_N$ be the $N$th odd prime, throughout.
Formula for the number $H(a,b,n) = \# \{a \lt x \lt b : x^2 - 1 = 0 \pmod n, x \text{ even}\}$.  This is true since the pairs are in one-to-one correspondence with the averages of the two pair components.
Therefore, by inclusion-exclusion, we get the number $G(a,b) = \# \{ a \lt x \lt b : x^2 - 1 = 0 \pmod q$ for some $q \in Q\}$, where $Q$ is a finite set of primes.  We have:
$$
G(a,b) = \sum_{u \ \mid \ \prod Q \\ u \neq 1} (-1)^{\Omega(u)}H(a,b,u)
$$
where $\Omega$ is prime Omega from number theory or $\Omega(p_1^{k_1} \cdots p_r^{k_r}) = \sum_{i = 1}^r k_i$.  But in this case, since $Q$ consists of distinct primes we have $\Omega(u) = \omega(u)$ so you can use either.
And therefore, the number $F(a,b) = \# \{ a \lt x \lt b: x^2 - 1 \text{ is a unit } \pmod q, \forall q \in Q\}$ is given by:
$$
F(a,b) = \dfrac{b - a}{2} + G(a,b)
$$
Since for $a,b$ odd there are $\dfrac{b - a}{2}$ total pairs of consecutive odd numbers $o, o+2 \in [a,b]$.

Now, if we let $a = p_{N}, b = p_{N}^2$, then no prime $q\lt p_N$ divides the end points and so $H(p_N, p_{N+1}^2, u)$ has the surprisingly simple form (for $u$ comprised of primes $q \lt p_N$):
$$
H(a,b,u) = 2 \left( \lfloor\dfrac{b}{u}\rfloor - \lfloor\dfrac{b}{2u} \rfloor -\lfloor\dfrac{a-1}{u}\rfloor + \lfloor\dfrac{a - 1}{2u} \rfloor\right)
$$
Let $Q = $ the first $N-1$ odd primes.  Then $F(p_N, p_N^2)$ should count the number of twin prime averages in the interval $(p_N, p_N^2)$.  However, here is some code that performs this inclusion-exclusion formula:
#import matplotlib.pyplot as plt
from sympy import primepi, isprime, primerange, divisors, primeomega
from math import floor, sqrt

N = 1000

def H(a,b,u):
    res = 2*(floor(b/u) - floor(b/(2*u)) - floor((a-1)/u) + floor((a-1)/(2*u)))
    return res

def inclusion_exclusion(F, Q):
    prodQ = 1
    for q in Q:
        prodQ *= q
    sum = 0
    for u in divisors(prodQ):
        if u != 1:
            sum += (-1)**primeomega(u) * F(u)
    return sum

primes = list(primerange(3, N))

for n in range(1, len(primes) + 1):
    Q = primes[:n]
    p_n = primes[n]
    formula0 = (p_n**2 - p_n)//2 + inclusion_exclusion(lambda u: H(p_n, p_n**2, u), Q)

    #formula = (p_N**2 - p_N) - (primepi(p_N**2) - primepi(sqrt(p_N - 1)) - 1)

    actual_count = 0
    for x in range(p_n, p_n**2):
        if isprime(x - 1) and isprime(x + 1):
            actual_count += 1

    print(formula0 - actual_count)

However, the code is printing a growing error value. It has to be all $0$'s for the formula to be correct.
I cannot figure out where my math is going wrong.  I thought the code was simple enough so I've included it here.
So, I need some help with the math of it.  Did I correctly apply inclusion-exclusion, for example.

Here is a fully worked example to help us out:
$$
a = 7, b = 7^2, Q = \{3,5\} \\
H(a,b,3) = 2([49/3] -[49/6] - [6/3] + [6/6]) = 14\\
H(a,b,5) = 2([49/5] -[49/10] - [6/5] +[6/10]) = 8 \\
H(a,b,15) = 2([49/15] - [49/30] - [6/15] + [6/30]) = 4 \\
G(a,b) = H(a,b,3) + H(a,b,5) - H(a,b,15) = 18 \\
F(a,b) = \dfrac{b - a}{2} + G(a,b) = 3 \\
$$
This formula is not working, as clearly the number should be $\#\{12,18,30,42\} = 4$.  So it is off by $1$ in this case.  It is close, but no cigar.  I can't see where the problem is in my derivation.

I think a problem can be seen here:
$$
H(5,25,3) = 2([25/3] - [25/6] - [4/3] + [4/6]) = 2(8 - 4 - 1 + 0) = 6
$$
                       .......
      _____   _____          ________          ________    ........
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  _____           _______          ________          _______
         ......                          ........

____'s count the odd pairs divided by $3$.  .....'s count those that are not.
True, there are 6 ____'s between 5 and and 25, but 24 is not a twin prime average.
So the formula should be:
$$
H(a, b, u) = 2\left(\lfloor \dfrac{b}{u}\rfloor - \lfloor\dfrac{b}{2u}\rfloor - \lfloor \dfrac{a-1}{u}\rfloor + \lfloor\dfrac{a-1}{2u} \rfloor\right) + \begin{cases} 0 \text{ if }, p_N^2 = 1 \pmod u \\ 1 \text{ otherwise}\end{cases}
$$
whenever $a = p_N, b = p_N^2$, $u$ is comprised of the first $N-1$ odd primes.

REPLY [2 votes]: I looked at the overcount for the case $a = 7, b = 49$ and it turns out that $H(a,b,15)$ doesn't count odd pairs $(25,27)$ nor $(33,35)$ which explains why the count is off by two when I run the up-to-date code.
The reason is because:
$$
(x^2 = 1 \pmod 3) \wedge (x^2 = 1 \pmod 5) \iff \\
(x = \pm 1 \pmod 3) \wedge(x = \pm 1 \pmod 5) \iff \\
(x^2 = 1 \pmod {15}) \\ \vee (x = -1 \pmod {3} \wedge x = 1 \pmod {5}) \\\vee (x = 1 \pmod {3} \wedge x = -1 \pmod {5})
$$
$H(a,b,15)$ only counts the first part, the parts where $x = -1 \pmod {3}$ and $x = 1 \pmod {5}$ or vise versa (swapping $3, 5$) are not counted and those are precisely the pairs $(25,27)$ and $(33,35)$.
The good news is that those $\vee$'s are exclusive or's so once we come up with a formula for the rest we can add/subtract it in.  The bad news is I'm not sure how to count those, for general $q_1\cdots q_n$.  It might be easier, knowing each $q_i$ is distinct.


TITLE: Why exactly is π(mean of radius)² less than the mean of the areas calculated for each radius?
QUESTION [0 upvotes]: For example, a uniformly distributed value for a radius between 0 and 1 is calculated many times and the area for each radius is calculated:
μ(radius) = 0.4998

μ(area) = 1.0467

π ( μ(radius) ) ² = 0.7849

If you compare the mean of the areas calculated during the loop with the value of the mean of the radii squared, why are they different? I would guess that it's to do with squaring the radius each time having a logarithmic / exponential effect on the sum of the areas, but I have no idea how. Any ideas?

REPLY [1 votes]: In general $E(X^2)\ne E(X)^2$. The simplest case to see this is when $X=\pm1$ with probability $\frac12$ each, so that $E(X)=0\ne E(X^2)=1$.
In fact, $$V(X):=E((X-E(X))^2)=E(X^2-2E(X)X+E(X)^2) = E(X^2)-E(X)^2$$ is the variance of random variable $X$.
Since the variance oof the uniform distribution on $[0,1]$ is $\frac1{12}$, we'd expect the difference between your expressions to be $\frac\pi{12}\approx 0.2618$, which matches very well with your numerical results.


text:
\begin{document}

\maketitle

\begin{abstract}
Memory is a key computational bottleneck when solving large-scale convex optimization problems such as semidefinite  programs (SDPs). In this paper, we focus on the regime in which storing an $n\times n$ matrix decision variable is prohibitive. To solve SDPs in this regime, we develop a randomized algorithm that returns a random vector whose covariance matrix is near-feasible and near-optimal for the SDP. We show how to develop such an algorithm by modifying the Frank-Wolfe algorithm to systematically replace the matrix iterates with random vectors. As an application of this approach, we show how to implement the Goemans-Williamson approximation algorithm for \textsc{MaxCut} using $\mathcal{O}(n)$ memory in addition to the memory required to store the problem instance. We then extend our approach to deal with a broader range of structured convex optimization problems, replacing decision variables with random extreme points of the feasible region.
\end{abstract}

\begin{comment}
\begin{abstract}
Semidefinite  Programs (SDPs)  are  an  important  class  of  optimization  problems with a variety of applications. For large-scale instances of these problems, memory becomes a key computational bottleneck. In this paper, we look at a way to represent an $\epsilon$-approximate solution of SDP with linear objective function and equality constraints in low dimensional space. This is done by generating random vectors with covariance that is positive semidefinite and an $\epsilon$-approximate solution to the SDP. Furthermore, we use the modified Frank-Wolfe algorithm, a first-order algorithm, to generate the \textit{sampled representation} of an approximate solution. This algorithm requires $\mathcal{O}(n^2/\epsilon^2)$ iterations for $\epsilon$-approximate convergence and linear additional memory at every step of the algorithm. With the advantage of low memory use throughout the algorithm, large-scale problems can be effectively solved on a small machine. One application of the framework is to use the algorithm to solve \textsc{MaxCut}. We provide a linear memory implementation of Goemans-Williamson rounding method so that the generated feasible solution has provable optimality guarantees.
\end{abstract}
\end{comment}

\begin{comment}
\section{Outline}
\begin{enumerate}
\item Introduction
\begin{enumerate}
\item Motivation\\
Need low memory algorithm which uses linear memory for large-scale SDPs when we only need low-rank approximation of the solution.\\
\textsc{MaxCut} problem has a rank-1 solution that is approximately computed with Goemans-Williamson method using properties of the solution matrix.\\
Can we find an algorithm which uses linear memory and find a rank-1 solution with the same approximation ratio as Goemans-Williamson method?
\item Review of \textsc{MaxCut} problem, Goemans-Williamson method and similar applications.
\item Literature review of sketchyCGM~\cite{sketchy}, `approximate complementarity'~\cite{ding2019optimal}
\item Brief review of methodology (idea of Gaussian sampling, why should we use Frank-Wolfe algorithm)
\end{enumerate}
\item Preliminaries
\begin{enumerate}
\item Use of linear mapping given in~\cite{sketchy}
\item Approximate Frank-Wolfe algorithm (the update direction and stopping criteria for SDP with bounded trace constraint and its convergence rate)
\end{enumerate}
\item Methodology
\begin{enumerate}
\item Elaborate on the idea of Gaussian sampling (how the samples relate to the low-rank factorization of the semidefinite matrix, how it can be combined with Frank-Wolfe algorithm, and how we can track the change in sample values). State the changes to be made to Frank-Wolfe algorithm to accommodate the linear mapping and the Gaussian sampling. For sparse input parameters, this modified algorithm requires the memory of order $\mathcal{O}(n)$ (linear) and has a convergence rate of $\mathcal{O}\Big( \frac{n^2}{\epsilon^2}\Big)$.
\item Penalty imposed on the linear constraints using LogSumExp approximation as given in~\cite{hazan2008sparse}. The paper~\cite{hazan2008sparse} minimizes the penalty for the feasibility problem. In this paper, we combine the penalty term $\phi(X)$ with the linear objective function by appropriately selecting the weight $\beta$ for $\phi(X)$.
\item With the penalty given above, the objective function is modified and the problem has a bounded trace constraint. The convergence result of the Frank-Wolfe algorithm for this type of problem is given above, and we can determine the bounds on the objective function value of the original SDP and the infeasibility of the solution.

\item \textsc{MaxCut} problem is a specific type of problem which falls under this regime. Using the properties of the cost and constraint matrices of \textsc{MaxCut} problem, we derive specific (and slightly better) optimality and feasibility result for \textsc{MaxCut} and the related class of problems. We also find the approximate rank-1 solution that is feasible to the original problem and bound on the solution value for this approximate rank-1 solution.
\end{enumerate}
\item Numerical experiments
\item Applications
\begin{enumerate}
\item Postprocessing of the samples to find a low-rank ($>1$) solution to a problem
\item Application of the above technique to certain special classes of SDPs such as chordal graphs, finding Lov\'asz theta function of graphs, etc.
\end{enumerate}
\item Conclusion
\end{enumerate}
\end{comment}

\input{Introduction}

\input{Methodology}

\input{Applications}

\input{Conclusion}

\bibliography{References}
\appendix
\input{AppendixA}

\end{document}

config: arxiv