TITLE: order of elements in direct product
QUESTION [1 upvotes]: I have a conceptual question: if a group has 1 element of order 1 and 1 element of order 2 (e.g., nonzero reals), what changes if your take its direct/cartesian product as a group?

REPLY [2 votes]: If $g \in G$ has order $m$, and $h \in H$ has order $n$, then $(g, h) \in G \times H$ has order $lcm(m, n)$.
For example, consider the element $(1, 2) \in \mathbb{Z}_2 \times \mathbb{Z}_6$.


TITLE: the definition of the maximum value of a continuous function is impredicative?
QUESTION [0 upvotes]: Mathematical Thought From Ancient to Modern Times: Volume 3, P1199 says

Another example of an impredicative definition is the definition of
the maximum value of a continuous function defined over a closed
interval as the largest value that the function takes on in this
interval.

I cannot understand why the definition is impredicative, any one can give a clear explanation ?

REPLY [2 votes]: When the definition is stated that way, we are essentially making a set $V$: the set of values that the function takes on the interval. Then we define the maximum value, $m$, as the largest value of $V$. But $m$ is already an element of $V$, which is why this can be seen as impredicative.
There are other definitions of the maximum value of a continuous function that are not impredicative. For example, $m$ is the maximum if and only if there is no rational $q$ in the interval so that $f(q) > m$, and for every positive rational $r$ there is a rational $q$ in the interval with $f(q) > m-r$.   If we already have the rational numbers and the function $f$, then this definition implicitly characterizes $m$ - even if $m$ is not rational - but only quantifying over sets that we already have.


TITLE: absorption of strategically closed posets
QUESTION [7 upvotes]: It is a (folklore?) fact that if $\kappa$ is a regular cardinal, and $\mathbb{P}$ is a $\kappa$-closed poset such that $\Vdash_\mathbb{P} |\mathbb{P}| = \kappa$, then $\mathbb{P}$ is equivalent to $Col(\kappa,\mathbb{P})$, the collection of partial functions from $\kappa$ to $\mathbb{P}$ of size $<\kappa$, ordered by inclusion.  Hence if $\mathbb{P}$ is any $\kappa$-closed forcing, then $\mathbb{P} \times Col(\kappa,\mathbb{P}) \sim Col(\kappa,\mathbb{P})$, so $\mathbb{P}$ is completely embeddable into $\mathcal{B}(Col(\kappa,\mathbb{P}))$.
If $\mathbb{P}$ is $\kappa$-strategically closed (following the notation from Cummings' chapter of the Handbook of Set Theory, not Jech's book), then one can show that $\mathbb{P}$ is completely embeddable into $\mathcal{B}(Col(\kappa,\mathcal{P}(\mathbb{P})))$, since after forcing with this collapse we can use the strategy to build a filter on $\mathbb{P}$ that is generic over the ground model.  It is not clear to me whether we can always embed such $\mathbb{P}$ into the smaller forcing $Col(\kappa,\mathbb{P})$.
Question:  Are there counterexamples to the statement, "If $\kappa$ is regular and $\mathbb{P}$ is $\kappa$-strategically closed, then there is a complete embedding of $\mathbb{P}$ into $\mathcal{B}(Col(\kappa,\mathbb{P}))$?

REPLY [5 votes]: Meanwhile, let's observe that if you weaken strategic $\kappa$-closure to the requirement that the forcing is strategically ${\lt}\kappa$-closed, that is, strategically $\beta$-closed for all $\beta<\kappa$, then the conclusion does not necessarily hold. The difference is between player II being able to continue playing for $\kappa$ many moves in a single game, versus being able to play for $\beta$ many moves in the length $\beta$ games for arbitrarily large $\beta$ below $\kappa$.
Suppose $\kappa$ is a Mahlo cardinal, and let $\mathbb{P}$ be the forcing to kill the Mahloness of $\kappa$. Conditions in $\mathbb{P}$ consist of closed bounded subsets of $\kappa$, containing no regular cardinals, ordered by end-extension. This forcing has size $\kappa$, and it adds a club in $\kappa$ containing no regular cardinals. It is strategically $\lt\kappa$-closed, since for any $\beta<\kappa$, the collection of conditions mentioning an ordinal above $\beta$ is $\leq\beta$-closed and dense in $\mathbb{P}$. So player II can win the games of length $\beta+1$ simply by playing into that dense set at the first opportunity.
Meanwhile, $\mathbb{P}$ does not completely embed into $\text{Coll}(\kappa,\kappa)$, because that forcing is ${\lt}\kappa$ closed and hence preserves every ground model stationary subset of $\kappa$ (one can see this by a pseudo-generic argument, since for any name for a club avoiding a given set, one can produce a club in the ground model avoiding that set), while $\mathbb{P}$ destroys the stationarity of the set of regular cardinals below $\kappa$. So the collapse forcing cannot add a generic filter for $\mathbb{P}$.


TITLE: Software for computing n-Clique, n-Clan, n-Plex?
QUESTION [0 upvotes]: I am studying graph theory and complex network into details, I would like to ask if some one could help providing a useful (academic) tools or some good tools for computing n-clique, n-clan, n-core, etc,,
Or even some tools for finding centrality, density, closeness, betweeness, e-eccentricity.... or some thing like these measurements ?
Thank you

REPLY [0 votes]: For a start you should take a look at Sagemath. Simple example to get you started
sage: G = graphs.RandomGNP(10,0.6)
sage: G.centrality_betweenness()
{0: 0.03935185185185185,
 1: 0.0,
 2: 0.0,
 3: 0.034722222222222224,
 4: 0.27083333333333326,
 5: 0.24537037037037038,
 6: 0.011574074074074072,
 7: 0.04629629629629629,
 8: 0.04629629629629629,
 9: 0.0}
sage: G.clique_maximum()
[0, 4, 5, 7]


TITLE: Does there exist a graph with chromatic number 4 that has no triangle or square cycles?
QUESTION [2 upvotes]: $K_4$ is an example of a graph that requires 4 colours to be coloured but it contains triangle cycles and a square cycle too.
I've tried drawing ever more complicated graphs made up of pentagons, hexagons, etc. but I've been able to colour all of them with 3 colours.
If such a graph exists without any triangle or square cycles does anyone have a hint as to how I could discover it?

REPLY [3 votes]: Brinkmann graph has chromatic number 4 and girth 5 (so it has no cycles of length 3 or 4)
See https://en.wikipedia.org/wiki/Brinkmann_graph
Other such graphs:
Foster Cage : http://mathworld.wolfram.com/FosterCage.html
Wells graph (again on MathWorld, but I can't post the link...)
EDIT, by the way, it has been proved (I think Erdos among the others) that there exists always a graph with girth > a and chromatic number > b for every a and b. Search: high girth high chromatic number theorem on google.


TITLE: "Squeezing" a finite group between symmetric groups
QUESTION [18 upvotes]: For a finite group $G$, take $m$ as the largest integer such that $G$ has a subgroup $H\cong S_m$ and $n$ as the smallest integer such that $G$ is itself isomorphic to a subgroup of $S_n$. We then define the "squeezing number" of $G$ as $s(G):=\dfrac nm$. This is probably not a new idea, so pointers are welcome. My question:

Can each rational $q\ge1$ occur as squeezing number for an appropriate group? If not, what can be said about the set of squeezing numbers?

REPLY [32 votes]: Here is an attempt assuming Goldbach's Conjecture. Express the required ratio as $n/m$ with $n-m \ge 8$ even, and take $G = S_m \times C_{pq}$, where $p$ and $q$ are distinct primes with $p+q=n-m$.
In fact it appears to have been proved that every sufficiently large even integer is the sum of four distinct primes, so we could use that to complete the proof: choose $n/m$ such that $n-m$ is large and even, and take $G = S_m \times C_{pqrs}$ where $p,q,r,s$ are distinct primes with $p+q+r+s=n-m$.
But perhaps this is over-complicated. An alternative solution, that works whenever $n \ge m+2 \ge 4$ is to write $n=qm+r$ with $0 \le r < m$. If $r >1$, take $G = S_m^q \times S_r$, if $r=0$, $G=S_m^q$, and if $r=1$, $G = S_m^{q-1} \times A_{m+1}$.


TITLE: What is the formula for this combination?
QUESTION [1 upvotes]: Please help me write the formula for all possible combinations given below.
I am not expert in Maths, so please understand.
Elements: a,b,c,d,e
Example of possible combinations:
{a},{b},{c},{d},{e},
{a,b},{a,c},{a,d},{a,e},{b,c},{b,d},{b,e},{c,d},{c,e},{d,e},
{a,b,c},{a,b,d},{a,b,e},{a,c,d},{a,c,e},{a,d,e},
{a,b,c,d},{a,b,c,e},
{a,b,c,d,e}

As you see, no elements are repeating and number of selection is growing from 1 to 5.
I read about Permutations and Combinations basics but couldn't find the right formula.

REPLY [2 votes]: What you are actually trying to find the number of non-empty subsets of the set $$S=\{1, 2, 3, 4, 5\}$$, and you've listed over half of them.
The number of subsets, including the empty set $\{\;\,\}$, of a set with $5$ elements is given by $2^5 = 32$.
There are two choices with respect to including an element or not; so there are $$2\times2\times 2 \times 2 \times 2 = 2^5\;\;\text{possible sets}$$ If you want to count only the number of non-empty sets, we then have $2^5 - 1= 32-1 = 31$ subsets.
In general the number of subsets of a set with $n$ elements is given by $2^n$. If we take out the empty set, we count $2^n-1$
Note that in your list of three-element sets, you're missing
$$\{b,c,d\}, \{b,c,e\}, \{b, d, e\}, \{c, d, e\}$$
And you are also missing 3 four-element sets.
$$\{a, b, d, e\}, \{a, c, d, e\}, \{b, c, d, e\}$$


TITLE: Propositional logic and tautologies
QUESTION [1 upvotes]: Taken from P. Suppes "Introduction to logic" pp16

Starting from the sentence "If $P$ tautologically implies $Q$, then.."
Question: Is it true that, at least within propositional logic, we are able to prove only tautologies or do I mis-understand something?
If yes, is propositional logic special in some way? Is the notion of tautology meaningful only in propositional logic?

REPLY [0 votes]: It's not difficult to see that the following assertions are equivalent.

The statement $\mathcal B$ follows from the statements $\mathcal A_1, \mathcal A_2,\ldots ,\mathcal A_n$.
The implication $\mathcal A_1\land\ldots\land\mathcal A_n\implies \mathcal B$ is a tautology.

Not as easy to suggest this might be the case, though, without any a priori intuition.


text:
\begin{document}
\title{Generalized barycenters and variance maximization on metric spaces \footnote{ B.P. is pleased to acknowledge the support of  National Sciences and Engineering Research Council of Canada Discovery Grant number 04658-2018.}}

\author{ Brendan Pass\footnote{Department of Mathematical and Statistical Sciences, 632 CAB, University of Alberta, Edmonton, Alberta, Canada, T6G 2G1 pass@ualberta.ca.}}
\maketitle
\begin{abstract}
We show that the variance of a probability measure $\mu$ on a compact subset $X$ of a complete metric space $M$ is bounded by the square of the circumradius $R$ of the canonical embedding of $X$ into the space $P(M)$ of probability measures on $M$, equipped with the Wasserstein metric.  When barycenters of measures on $X$ are unique (such as on CAT($0$) spaces), our approach shows that $R$ in fact coincides with the circumradius of $X$ and so this result extends a recent result of Lim-McCann from Euclidean space.  Our approach involves bi-linear minimax theory on $P(X) \times P(M)$ and extends easily to the case when the variance is replaced by very general moments.

As an application, we provide a simple proof of Jung's theorem on CAT($k$) spaces, a result originally due to Dekster and Lang-Schroeder.

\end{abstract}

\section{Introduction}
The aim of this note is to establish bounds on the variance, and generalizations of it, of probability measures on metric spaces.   Letting $X \subseteq M$ be a compact subset of a complete metric space $(M,d)$, the variance of a probability measure $\mu \in P(X)$ on $X$ is
\begin{equation}\label{eqn: variance}
Var(\mu):=\inf_{y \in M}\int_Xd^2(x,y)d\mu(x).
\end{equation}
Points $y$ where the infimum is attained (if they exist) are often called \emph{barycenters}, or Frechet means, of $\mu$. 	When $M =\mathbb{R}^n$, $\bar x_\mu =\int_Xxd\mu(x)$ is the unique barycenter, and so \eqref{eqn: variance}  coincides with the familiar formula $Var(\mu) =\int_X|x-\bar x_\mu|^2d\mu(x)$.  On the real line (ie, when $n=1$), a classical result of Popoviciu bounds the variance by the diameter of $X$: if $X \subseteq [a,b]$, then $Var(\mu) \leq \frac{1}{4}(b-a)^2$ for all $\mu \in P(X)$.  Equality occurs only when $\mu=\frac{1}{2}(\delta_a+\delta_b)$ \cite{Popoviciu35}.

Recent work by Lim and McCann extends this to higher dimensions \cite{LimMcCann20a}; for $X \subseteq \mathbb{R}^n$, they prove (among other results) that
$$
Var(\mu) \leq R^2
$$
where $R$ is the radius of the smallest closed ball $\bar B(y,R)$ containing $X$ (in our subsequent terminology, $R$ will be called the \emph{circumradius}, $y$ the \emph{circumcenter} and $\bar B(y,R)$ the \emph{circumball}, of $X$).  Equality is obtained if and only if $\mu$ is supported on the intersection $\partial \bar B(y,R) \cap X$ of the corresponding sphere with $X$, and the barycenter of $\mu$ is the circumcenter $y$.  Their proof of this uses convex-concave minimax theory for the functional $H(y,\mu) =\int_X|x-y|^2d\mu(x)$.  This theory applies since the domain $\mathbb{R}^n$ of $y$ is affine and the integrand convex in $y$; Lim and McCann in fact prove an analogous result for more general convex moments (that is, when the integrand $|x-y|^2$ is replaced by a general convex function $v(x-y)$).  It does not appear, however, that one can directly apply these techniques to move beyond the affine setting and deal with more general metric spaces $M$ (or, even for $M=\mathbb{R}^n$, with non-convex integrands $V(x,y)$ replacing $|x-y|^2$ in \eqref{eqn: variance}).

We show here that this obstacle can be overcome by working with a type of \emph{generalized barycenter} introduced in recent work with Kim \cite{KimPass18}.  These amount to barycenters of measures on the image $i(X)$ of $X$ under the canonical isometric embedding $i:x \mapsto \delta_x$ of $X$ into the space $P(M)$ of probability measures on $M$, equipped with the Wasserstein metric.  Viewed within this framework, the analogue of the functional $H$ is \emph{bi-linear} on $P(X) \times P(M)$ (see \eqref{eqn: def of objection} below), without \emph{any} restriction on $M$.  We show that for any measure $\mu \in P(X)$ we have
$$
Var(\mu) \leq R^2
$$
where $R$ is the circumradius of $i(X)$ within the metric space $P(M)$, with equality if and only if the pushforward $i_\# \mu$ is concentrated on the boundary of a circumball  of $i(X)$ and a Wasserstein barycenter $\nu$ of it is a circumcenter. In addition, since the bi-linearity does not depend on the integrand, this technique applies equally well to other continuous moment functions, yielding analogous results, as we show.

As an application of their work, Lim and McCann establish that among all measures $\mu \in P(X)$  supported on  sets $X \subseteq \mathbb{R}^n$ with diameter at most $1$, the maximal variance is obtained by uniform measure on the $n+1$ vertices of the unit simplex.  They show that this is equivalent to a classical theorem of Jung, which states that the diameter of any set $X$ is at most $2R\sqrt{\frac{n+1}{2n}}$, where $R$ is the circumradius of $X$ \cite{Jung1901}.  On the other hand,  Jung's theorem has been generalized to sufficiently small sets in metric spaces with upper sectional curvature bounds, first by Dekster \cite{Dekster97} under several technical assumptions, and subsequently, with these assumptions eliminated, by Lang and Schroeder \cite{LangSchroeder97}; we use our framework to provide a simple new proof of this result.

In the following section, we introduce the general setting we will work in and establish a preliminary result which underlies the rest of the paper.  In section 3 we prove our main result on variance maximizers on metric spaces, several consequences of it, and a generalization to general valuation or moment functions.  The fourth section is reserved for our new proof of Jung's theorem on metric spaces with upper curvature bounds.

\section{General setting and preliminary result}
In this section, we establish a background proposition which our subsequent analysis will hinge on.

Consider a continuous function $V:X \times Y \rightarrow \mathbb{R}$ on compact metric spaces $X$ and $Y$.  In the following sections, our primary interest will be in the case where $V$ is the squared distance on a common metric space $M$ containing both $X$ and $Y$; however, working with a general moment function $V$ costs no extra difficulty in the proofs in this section, and so we choose to do so in order to illustrate the flexibility of this approach.

Given a probability measure $\mu \in P(X)$, we define the \emph{$V$-variance} of $\mu$ as

$$
Var_V(\mu) =\min_{y \in Y}\int_XV(x,y)d\mu(x).
$$

We consider the problem of maximizing the $V$-variance over $P(X)$. We will show below that this is equivalent to minimizing the \emph{$V$-anti-variance} of $\nu$ over $P(Y)$, where the anti-variance of  $\nu \in P(Y)$ is defined as
$$
AVar_V(\nu) = \max_{x \in X}\int_YV(x,y)d\nu(y).
$$
We will refer to minimizers of  $y \mapsto \int_XV(x,y)d\mu(y)$ as \emph{$V$-barycenters} of $\mu$ and maximizers of $x \mapsto \int_YV(x,y)d\nu(y)$ as \emph{$V$-anti-barycenters of $\nu$}.

We will consider the following functional on $P(X) \times P(Y)$:
\begin{equation}\label{eqn: def of objection}
\mathcal{V}(\mu,\nu):=\int_X\int_YV(x,y)d\mu(x)d\nu(y)
\end{equation}

We next note a simple fact about $\mathcal{V}$:
\begin{lemma}\label{lem: gen barycenters}
The $V$-variance of $\mu \in P(X)$ satisfies $Var_V(\mu) =\min_{\nu \in P(Y)} \mathcal{V}(\mu,\nu)$ and $\nu \in P(Y)$ minimizes $\nu \mapsto \mathcal{V}(\mu,\nu)$ if and only $\nu$ almost every $y$ is a $V$-barycenter of $\mu$.

Similarly, the  $V$-anti-variance of $\nu \in P(Y)$ satisfies $AVar_V(\nu) =\max_{\mu \in P(X)} \mathcal{V}(\mu,\nu)$,  and $\mu \in P(X)$ maximizes $\mu \mapsto \mathcal{V}(\mu,\nu)$ if and only $\mu$ almost every $x$ is a $V$-anti-barycenter of $\nu$.
\end{lemma}
\begin{proof}
	We prove only the first assertion, since the proof of the second is essentially identical.

	For every $y$, we have $Var_V(\mu) \leq \int_XV(x,y)d\mu(x)$, with equality if and only if $y$ is a $V$-barycenter of $\mu$.  Integrating against any $\nu \in P(Y)$ yields $Var_V(\mu) \leq \mathcal{V}(\mu,\nu)$, with equality if and only if $\nu$ almost every $y$ is a $V$-barycenter, in which case $\nu$ minimizes  $\nu \mapsto \mathcal{V}(\mu,\nu)$.
\end{proof}

 Motivated by the preceding lemma, we will call minimizers of  $ \nu \mapsto \mathcal{V}( \mu, \nu)$ (respectively, maximizers of $ \mu \mapsto \mathcal{V}( \mu,\nu)$) \emph{generalized $V$-barycenters} of $\mu$ (respectively, \emph{generalized $V$-anti-barycenters} of $\nu$).

 Note that when $X \subseteq M$,
 $$
 Y=conv(X):=\{y:\text{ y minimizes } z\in M \mapsto \int_Xd^2(x,z)d\mu(x) \text{ for some } \mu \in P(X)   \}
 $$ is the \emph{barycentric convex hull of X} (that is, the set of all barycenters in $M$ of measures supported on $X$)  and $V(x,y) =d^2(x,y)$ is the metric distance squared, $V$-barycenters and the $V$-variance coincide with the classical metric barycenters and variance of the measure $\mu$ on the metric space $M$, respectively (equaling $\bar x_\mu=\int_Xxd\mu(x)$ and $\int_X|x-\bar x_\mu|^2d\mu(x)$  when $X\subseteq\mathbb{R}^n$  ).
In this case we will drop the prefix $V$ on the other nomenclature as well (so that, for example, a generalized barycenter of $\mu$ is a minimizer of $\nu \mapsto \int_X\int_Yd^2(x,y)d\mu(x)d\nu(y)$). The concept of generalized barycenters was in fact introduced in earlier joint work with Kim \cite{KimPass18} (although this terminology was not used there).

The following definition will play an important role in this paper.
\begin{definition}\label{def: saddle point}
	A pair $(\mu,\nu) \in P(X) \times P(Y)$ is called a \emph{saddle point} of $\mathcal{V}$ if $\mu$ is  a generalized $V$-anti-barycenter of $\nu$ and $\nu$ is a generalized $V$-barycenter of $\mu$.
\end{definition}

\begin{remark}
Lim-McCann's original motivation for variance maximization problems came from models describing swarming in physics and biology \cite{LimMcCann20b}; their goal was to understand minimizers of an interaction energy $\mu \mapsto \int_X\int_XV(x,y)d\mu(x)d\mu(y)$ of a population $\mu$ with pairwise interaction $V(x,y)$ (this is equivalent to the variance when $V(x,y) =|x-y|^2$ on $X=\mathbb{R}^n$; more generally, in a certain limit another term forces the population to live on a set with a fixed upper bound on its diameter).  In our setting, $\nu$ and $\mu$ might be thought of as populations of two species; agents $x \in X$ wish to maximize their average interaction energies, $\int_YV(x,y)d\nu(y)$ with agents in $Y$ while agents $y$ in $Y$ seek to minimize their average interaction energy $\int_YV(x,y)d\mu(x)$.  Saddle points capture exactly equilibria in this model; if $(\mu,\nu)$ is a saddle point, Lemma \ref{lem: gen barycenters} implies that $\mu$ almost every $x \in X$ is a $V$-anti-barycenter of $\nu$ while $\nu$ almost every $y$ is a $V$-barycenter of $\mu$.
\end{remark}

Establishing the following result is the main purpose of this section.
\begin{proposition}\label{thm: saddle point}
There exists a  maximizer $\mu$ of the $V$-variance among all measures in $P(X)$ and a minimizer $\nu$ among measures in $P(Y)$ of the $V$-anti-variance such that $(\mu,\nu)$ is a saddle point of $\mathcal{V}$.

Furthermore, any other $\bar \mu \in P(X)$ maximizes the $V$-variance if and only if
$(\bar \mu,\nu)$ is a saddle point of $\mathcal{V}$. Similarly, any other $\bar \nu \in P(Y)$ minimizes the $V$-anti-variance if and only if $(\mu,\bar \nu)$ is a saddle point of $\nu$.
\end{proposition}

\begin{proof}
The proof is by standard minimax arguments. Note that (uniform on compact sets) continuity of $V$ implies weak continuity of the mappings $\mu \mapsto \mathcal{V}(\mu,\nu)$ and $\nu \mapsto \mathcal{V}(\mu,\nu)$ and thus existence of maximizers and minimizers respectively on the weakly compact sets $P(X)$ and $P(Y)$.  We define the set valued mapping $\mathcal{F}$ on $P(X) \times P(Y)$ by
$$
\mathcal{F}:(\mu,\nu) \mapsto argmax \Big(\bar \mu \mapsto \mathcal{V}(\bar \mu,\nu)\Big) \times argmin \Big(\bar \nu \mapsto \mathcal{V}( \mu,\bar \nu)\Big)
$$
It is straightforward to show that $\mathcal{F}$ has a closed graph and that $\mathcal{F}(\mu,\nu)$ is non-empty, compact and convex for each $(\mu,\nu) \in P(X) \times P(Y)$.  The Kakutani -- Glicksberg -- Fan fixed point theorem (see, for instance, \cite{GranasDugundji03}) then ensures the existence of a fixed point $(\mu,\nu)$ of $\mathcal{F}$; that is, a saddle point of $\mathcal{V}$.
 To see that $\mu$ maximizes the $V$-variance, note that for any other measure $\bar \mu \in P(X)$ we have, by Lemma \ref{lem: gen barycenters},
\begin{eqnarray*}
Var_V(\mu) &=&\int_X\int_YV(x,y)d\mu(x)d\nu(y)\\
&\geq&\int_X\int_YV(x,y)d\bar \mu(x)d\nu(y)\\
&\geq &Var_V(\bar \mu),
\end{eqnarray*}
with equality if and only $\bar \mu$ is a generalized $V$-anti-barycenter of $\nu$ (which gives equality in the first inequality above) and $\nu$ is a generalized $V$-barycenter of $\bar \mu$ (which gives equality in the second); that is, $(\bar \mu, \nu)$ is a saddle point. This yields the characterization of other maximizers in the statement of the Theorem.

A similar argument shows that $\nu$ minimizes the $V$-anti-variance, and yields the desired characterization of other minimizers $\bar \nu$ of the $V$-anti-variance.
\end{proof}
Although the proof of Proposition \ref{thm: saddle point} is straightforward, it has several notable consequences which we will describe in the coming sections.

\section{Maximizing variance on metric spaces.}
In this section, we will mostly (outside of Proposition \ref{cor: general V} below) focus on the case where $V$ is quadratic, $V(x,y) =d^2(x,y)$, where $X \subseteq M$, $Y =conv(X) \subseteq M$ and $(M,d)$ is a complete metric space.

We will call $R =\inf\{r:X\subseteq \bar B(y,r) \text{ for some } y \in M\} =\inf_{y \in M}\sup_{x\in X}d(x,y)$ the \emph{circumradius} of $X$ in $M$, where $\bar B(y,r)$ is the closed ball of radius $r$ centered at $y$.  If a ball $\bar B(y,r)$ attaining the minimum exists, we call it a \emph{circumball} of $X$ in $M$ and its center $y$ a \emph{circumcenter} of $X$ in $M$.

Recall that the Wasserstein metric on $P(M)$ is defined by
$$
W_2^2(\mu,\nu):=\inf\int_{M \times M}d^2(x,y)d\gamma(x,y)
$$
where the infimum is over all joint measures $\gamma \in P(M\times M)$ whose marginals are $\mu$ and $\nu$.  Of particular relevance here is the case where $\mu = \delta_x$ is a Dirac mass, in which case product measure $\delta_x \otimes \nu$ is the only joint measure with $\delta_x$ and $\nu$ as marginals and so $W_2^2(\delta_x ,\nu) =\int_Md^2(x,y)d\nu(y)$.

There is  a canonical isometry $i:X \rightarrow P(M)$, $i(x) =\delta_x$ from $X$ into $P(M)$ endowed with the Wasserstein distance.  We can then consider the circumradius of the subset  $i(X)$ of the metric space $(P(M), W_2)$, which is the infimum over all $R$ such that $W_2(\sigma, \nu) \leq R$ for all $\sigma \in i(X)$, for some $\nu \in P(M)$, or, equivalently, the infimum over $R$ such that,
$$
\int_Md^2(x,y)d\nu(y)=W_2^2(\delta_x ,\nu) \leq R^2
$$
for all $x \in X$, for some $\nu \in P(M)$.  We also note, as was observed in \cite{KimPass18}, that generalized barycenters $\nu$ of $\mu$ are exactly barycenters of the pushforward $i_\#\mu \in P(P(M))$, with respect to the Wasserstein metric.

Our main result is that a generalization of Lim and McCann's Theorem 1.1 b) \cite{LimMcCann20a} holds for the canonical embedding of $X$  into its Wasserstein space $P(X)$:
\begin{theorem}\label{cor: general Jung}
Assume that both $X \subseteq M$ and its convex hull $Y=conv(X)$ are compact, and that each $\mu \in P(X)$ admits a barycenter.  Then there exists a circumcenter $\nu \in P(M)$ of $i(X)$ and the square $R^2$ of the circumradius $R$ of $i(X)$ is equal to the maximal variance of measures $\mu \in P(X)$, and to the minimal anti-variance among measures $\bar \nu \in P(Y)$.

	Furthermore, any $ \bar \mu$ maximizing the variance is supported on the corresponding sphere; that is $W_2(\delta_x,\nu)=R$ for $\mu$ a.e. $x$.  If $\bar \nu$ is any other circumcenter of $i(X)$, we also have $W_2(\delta_x,\bar \nu)=R$ for $\bar \mu$ almost every $x$.
\end{theorem}
\begin{proof}
	Let $(\mu, \nu)$ be the saddle point guaranteed to exist by Proposition \ref{thm: saddle point}.  Using Lemma \ref{lem: gen barycenters}, $\nu$ almost every $y$ is a barycenter of $\mu$ and the maximal variance is given by $R^2:=\int_Xd^2(x,y)d\mu(x)$ for each such $y$; integrating against $\nu$, and using the fact that $\mu$ is a generalized anti-barycenter of $\nu$, combined with Lemma \ref{lem: gen barycenters} again gives $R^2=\int_X\int_Yd^2(x,y)d\mu(x)d\nu(y) =\int_Yd^2(x,y)d\nu(y) = W^2_2(\delta_x,\nu)$ for $\mu$ almost all $x$.  This $R^2$ is also the anti-variance of $\nu$ (and therefore the minimal anti-variance by Proposition \ref{thm: saddle point}), which means that for every $z \in X$ we have $W^2_2(\delta_z,\nu)=\int_Yd^2(z,y)d\nu(y) \leq R^2$; that is, $i(X) \subseteq B(\nu,R)$.  The same argument applies to any other $\bar \mu$ maximizing the variance and $\bar \nu$ minimizing the anti-variance.

	It remains to show that $R$ is the circumradius of $i(X)$ in $P(M)$; this is easily established by contradiction.  If $i(X) \subseteq \bar B(\nu',R')$ for some $\nu' \in P(M)$ and some $R'<R$,  then each $x \in X$ satisfies $\int_Yd^2(x,y)d\nu'(y) = W_2^2(\delta_x,\nu') \leq R'^2<R^2 $ and so the anti-variance of $\nu'$ is $\max_{x \in X}\int_Md^2(y,x)d\nu'(y)\leq R'^2<R^2 $.  This contradicts the fact that $\nu$ has minimal anti-variance.
\end{proof}

When barycenters are unique, as is the case on $CAT(0)$ spaces, or more generally, when the circumradius of $X$ is sufficiently small relative to its sectional curvature, this theorem yields the following modest contribution to our understanding of the geometry of Wasserstein space.
\begin{corollary}\label{cor: circumradius equal}
Let $X\subseteq M$ be such that  at least one variance maximizing probability measure $\mu \in P(X)$ has a unique barycenter.  Then, under the assumptions in Theorem \ref{cor: general Jung}, the circumradius of $X$ is the same as the circumradius of $i(X)$.
\end{corollary}
\begin{proof}
	If $X\subseteq \bar B(y,R)$  then the ball $\bar B(\delta_y,R)$ clearly contains $i(X)$ in $P(M)$, and so the circumradius of $i(X)$ is always less than or equal to that of $X$.

	On the other hand, Proposition \ref{thm: saddle point} implies the that each variance maximizing measure $\mu$ concentrates on the boundary $\{x: d(x,y)=R\}$ of a circumball $\bar B(\nu,R)$ of $i(X)$, where $\nu$ is any generalized barycenter of $\mu$.
	But this means that $\nu$ almost every $y$ is a barycenter of $\mu$, which by our uniqueness  assumption  implies $\nu = \delta_y$ where $y$ is the unique barycenter of $\mu$.  Since $i(X) \subseteq \bar B(\delta_y,R)$, we clearly have $X \subseteq \bar B(y,R)$, meaning that $R$ is the circumradius of $X$.
\end{proof}

The following Corollary generalizes Proposition 3.1 in \cite{LangSchroeder97} from CAT($k$) space (for compact sets $X$; compactness was not required in \cite{LangSchroeder97}).  Note that the uniqueness of barycenters required here follows under their assumptions from \cite{Yokota16} and \cite{Yokota17}; however, our result also applies to other subsets of metric spaces without upper curvature bounds but on which barycenters are unique, such as closed subsets of the set $P_{ac}(M) \subseteq P(M)$ of absolutely continuous probability measures on compact underlying metric spaces, equipped with the Wasserstein metric \cite{KimPass2017}.

\begin{corollary}\label{cor: unique circumcenter}
	Assume that $X \subseteq M$ is such that at least one variance maximizing $\mu$ in $P(X)$ has a unique barycenter. Then, under the assumptions in Theorem \ref{cor: general Jung}, the circumcenter $y \in Y$ of $X$ is unique.
	\end{corollary}
\begin{proof}
	 Since by Theorem \ref{cor: general Jung} and Corollary \ref{cor: circumradius equal}, the square $R^2$ of the circumradius is equal to the minimal anti-variance, we see that  $y$ is a circumcenter if and only if $\delta_y$ has minimal anti-variance.

	 Letting $\mu$ be the variance maximizer with a unique barycenter, Proposition \ref{thm: saddle point} and Lemma \ref{lem: gen barycenters} then imply that every circumcenter is a barycenter of $\mu$; uniqueness of the circumcenter then  follows.
\end{proof}
The following immediate consequence of Theorem \ref{cor: general Jung} and Corollaries \ref{cor: circumradius equal} and \ref{cor: unique circumcenter} directly generalizes Theorem 1.1 (b) of Lim and McCann \cite{LimMcCann20a}.
\begin{corollary}\label{cor: unique bc}
Assume that $X \subseteq M$ is such that at least one variance maximizing  $\mu$ in $P(X)$ has a unique barycenter.  Then, under the assumptions in Theorem \ref{cor: general Jung}, the maximal variance among measures in $P(X)$ is equal to the circumradius $R$ of $X$, and every variance maximizing $\mu$ gives full measure to the boundary $\partial B(y,R)$ of the circumball.
\end{corollary}
In particular, it is worth noting that the maximal variance over any compact, convex set $X\subseteq \mathbb{R}^n$ is equal to the minimal anti-variance over the same set, and  anti-variance is minimized by the Dirac mass $\delta_y$, where $y$ is the circumcenter of $X$.

The assumption on the uniqueness of barycenters in Corollaries \ref{cor: circumradius equal}, \ref{cor: unique circumcenter} and \ref{cor: unique bc} is necessary, as the following example verifies.
\begin{example} Let $X=Y=\mathcal{S}^n$ be the round sphere with metric diameter $1$ (ie, the geodesic distance from the north to south pole is $1$).  Then the only metric ball containing $X$ is the entire sphere, that is $\bar B(y,1)$ for any $y \in \mathcal{S}^n$. The circumradius is therefore $1$ and each point is a circumcenter.  However, it is not hard to see that there is no measure $\mu \in P(X)$ whose variance is $1$, so the maximal variance must be strictly  less than $1$.

On the other hand, Theorem \ref{cor: general Jung} still holds here. It is not hard to see that $(\mu,\nu ) =(vol/|vol|,vol/|vol|)$ is the saddle point from Proposition \ref{thm: saddle point}; that is both $\mu$ and $\nu$ are uniform.

The maximal variance is therefore attained by uniform measure and is equal to the average of the squared distance (which is clearly strictly less than the square $1$ of the circumradius, which is the \emph{maximal} squared distance between points).

 Theorem \ref{cor: general Jung} then implies that this coincides with the circumradius of $i(X)$, and that the circumcenter $\nu$ in Wasserstein space is uniform measure.  Symmetry implies $W_2(\delta_x,\nu) = \int_Xd^2(x,y)d\nu(y)$ is constant throughout $x \in spt(\mu) =X$, as predicted by Theorem \ref{cor: general Jung}.
\end{example}

We close this section by noting that Theorem \ref{cor: general Jung} and Corollary \ref{cor: unique bc} easily extend to general valuation, or moment functions, $V$.  The proof of the following Proposition is essentially the same as the arguments earlier in this section.

\begin{proposition}\label{cor: general V}
	Let $V: X\times Y \rightarrow \mathbb{R}$ be a continuous function on compact metric spaces $X$ and $Y$. Then
	\begin{enumerate}
		\item The maximal $V$-variance among measures $\mu \in P(X)$ is equal to the minimal $V$-anti-variance among $\nu \in P(Y)$.
		\item Let $\nu \in P(Y)$ minimize the $V$-anti-variance. Then $\mu \in P(X)$ maximizes the $V$-variance if and only for $\mu$ almost every $x$, $\int_YV(x,y) d\nu(y) =C_\nu$, where $C_\nu :=\max_{z \in X}\int_YV(z,y)d\nu(y)$ is the $V$-anti-variance of $\nu$ and $\nu$ almost every $y$ is a $V$-barycenter of $\mu$.
		 \item 	If at least one variance maximizing measure $\mu$ on $X$ has a unique $V$-barycenter $y$, then the $V$-anti-variance is uniquely minimized by the Dirac mass $\delta_y$.

		 In this case, $\bar \mu$ maximizes the $V$-variance if and only if $y$ is a $V$-barycenter of $\bar \mu$ and for $\bar \mu$ almost every $x$ we have $V(x,y) =C_y$, where $C_y:=\max_{z \in X}V(z,y)$ is the $V$-anti-variance of $\delta_y$.
	\end{enumerate}

\end{proposition}
\begin{example}
	Taking $V(x,y)=v(x-y)$ for $v$  convex and coercive on a compact $X \subseteq \mathbb{R}^n$ and compact $Y\subseteq \mathbb{R}^n$ large enough to contain all $V$-barycenters of measures on $X$, we recover the characterization of minimizers in \cite[Theorem 1.7]{LimMcCann20a}, provided that the $V$-anti-variance is minimized by a Dirac mass.

	This is clearly the case if $V$ is strictly convex, from the third point in the preceding Proposition; we claim it holds even without  strict convexity.  To see this, let $\nu$ minimize the anti-variance and $\bar y = \int_{\mathbb{R}^n}yd\nu(y)$ be the barycenter of $\nu$. Let $\bar x$ maximize  $x \mapsto V(x,\bar y)$, so that $V(\bar x,\bar y)=AVar_v(\delta_{\bar y})$.  By Jensen's inequality we have
	$$
AVar_v(\delta_{\bar y})	=V(\bar x, \bar y ) \leq \int_YV(\bar x ,y) d\nu(y) \leq AVar_V(\nu).
	$$
Thus, $\delta_{\bar y}$ minimizes the $V$-anti-variance, even for non-strictly convex $v$, and so Proposition \ref{cor: general V} implies Theorem 1.7 in \cite{LimMcCann20a}.

In addition, the Proposition above applies to much more general $V$, with no convexity assumptions, than are dealt with in \cite{LimMcCann20a}, although in the general case the characterization of $V$-variance minimizers involves minimizers of the $V$-anti-variance of measures $\nu$, rather than minimizers of the simpler function $y \mapsto \max_xV(x,y)$, as is the case in \cite{LimMcCann20a}.

\end{example}
\section{Jung's theorem on spaces with curvature bounded above}

The purpose of this section is to provide a new proof of Jung's theorem, comparing the circumradius and diameter, $D=\sup_{x_0,x_1 \in X}d(x_1,x_2)$ of a compact set $X \subseteq M$,  when $M$ is a  CAT($k$) spaces.  We recall that CAT($k$) spaces are not-necessarily smooth generalizations of Riemannian manifolds with sectional curvature bounded above by $k$; we refer to, for example, \cite{AlexanderKapovitchPetrunin}, for precise definitions of CAT($k$) spaces and other relevant concepts.

The first proof of Jung's theorem on CAT($k$) spaces is due to Dekster \cite{Dekster97}; shortly afterwards, Lang and Schroeder produced a improved result with many technical assumptions removed \cite{LangSchroeder97}.

The formulation of Jung's theorem on CAT($k$) spaces requires the following notion:
\[ S(R,n,k) = \left\{
	\begin{array}{l l}
	\frac{1}{\sqrt{-k}}2\sinh^{-1}\big(\sqrt{\frac{n+1}{2n}}\sinh(\sqrt{-k}R)\big) & \quad k<0\\
	2R\sqrt{\frac{n+1}{2n}} & k=0\\
	\frac{1}{\sqrt{k}}2\sin^{-1}\big(\sqrt{\frac{n+1}{2n}}\sin(\sqrt{k}R)\big) &k>0.
	\end{array} \right.\]
We then set $S(R,\infty, K) = \lim_{n\rightarrow \infty} S(R,n,k) $, that is:

\[ S(R,\infty,k) = \left\{
\begin{array}{l l}
\frac{1}{\sqrt{-k}}2\sinh^{-1}\big(\frac{1}{\sqrt{2}}\sinh(\sqrt{-k}R)\big) & \quad k<0\\
\sqrt{2}R & k=0\\
\frac{1}{\sqrt{k}}2\sin^{-1}\big(\frac{1}{\sqrt{2}}\sin(\sqrt{k}R)\big) &k>0.
\end{array} \right.\]

We note that $S(R,n,k)$ can be interpreted as the third side length of a triangle in the model space of constant sectional curvature $k$ (that is, the $n$-dimensional complete, simply connected Riemannian manifold of constant sectional curvature $k$), when the other two sides both have length $R$ and subtend an angle of $\arccos(-1/n)$.

We will need the following Lemma:
\begin{lemma}\label{lem: diff of distance}
Let  $t \mapsto x(t)$ be a unit speed geodesic  in the complete CAT($k$) space $M$ and $p \in M$ such that, if $k>0$, $d(x(0),p) <\frac{\pi}{2\sqrt{k}}$. Then $t \mapsto d^2(x(t),p)$ is differentiable  at $t=0$; its derivative is given by:

$$
\frac{d}{dt}(d^2(x(t),p))\Big |_{t=0} =-2d(x(0),p)\cos(\alpha)
$$
where $\alpha$ is the angle at $x(0)$ between $x(t)$ and the (unique) minimizing geodesic joining $x(0)$ and $p$.
\end{lemma}
\begin{proof}
	The first variation formula (see \cite[Formula 8.14.3]{AlexanderKapovitchPetrunin}) asserts that $t\mapsto d(x(t),p)$ is differentiable at $t=0$, with derivative $-\cos(\alpha)$; the result now follows from the chain rule.
\end{proof}
\begin{theorem}[Jung's Theorem on spaces with curvature bounded above]
Let $X \subseteq M$ be a compact subset of a complete CAT($k$) space $M$, which, if $k>0$, is contained in a metric ball of radius $r<\frac{\pi}{2\sqrt{k}}$.  Assume that all barycenters of measures on $X$ are contained in a compact subset $Y \subseteq M$.  Then there exists a unique circumcenter $y$ of $X$.

Furthermore, $D \geq S(R,\infty,k)$, where $D$ is the diameter of $X$ and $R$ the circumradius.  If, in addition, there exists a variance maximizer $\mu \in P(X)$ supported on $n+1$ points, we have $D \geq S(R,n,k)$.
 \end{theorem}

\begin{remark}
	Lang and Schroeder's version did not require the compactness assumption on $X$ or $Y$, assuming instead only boundedness of the non-empty set $X$.  On the other hand, compactness seems to be necessary for our approach to work.  If $X=\{e_i\}_{i=1}^{\infty}$ is an orthonormal basis in a Hilbert space $M$, then the circumcenter $0$ is the origin, which is not a barycenter of any probability measure on $X$.  Therefore, there is no $\mu \in P(X)$ so that $(\mu,\delta_0)$ is a saddle point of $\mathcal{V}$, which is a key ingredient in our argument.
\end{remark}

\begin{proof}
The existence and uniqueness of barycenters in CAT($k$) spaces, due, under the conditions here, to Yokota \cite{Yokota17}\cite{Yokota16}, together with Corollary \ref{cor: unique circumcenter} imply the existence of a unique circumcenter, $y\in Y$ which is the barycenter of every variance maximizing $\mu \in P(X)$, which, in turn, are all supported on the boundary $\partial B(y,R)$ of the circumball.

Now fix a variance maximizing $\mu$ and let $y(\cdot):[0,R] \rightarrow M$ be a unit speed geodesic starting at $y(0)=y$.    By Lemma \ref{lem: diff of distance} and the dominated convergence theorem,  the function
\begin{equation}\label{eqn: variance function}
t \mapsto \int_Xd^2(y(t),x)d\mu(x)
\end{equation}
is differentiable at $t=0$ and its derivative is

\begin{equation}\label{eqn: variance derivative}
\int_X-2d(y,x)\cos(\alpha(x))d\mu(x)=-2R\int_X\cos(\alpha(x))d\mu(x),
\end{equation}
where $\alpha(x)$ is the angle at $y=y(0)$ between $y(t)$ and the geodesic  joining $y$ and $x$. Since $y$ is a barycenter of $\mu$, the function \eqref{eqn: variance function} is minimized at the endpoint $t=0$ and so its derivative \eqref{eqn: variance derivative} must be non-negative.

Now, letting the endpoint $z:=y(R) \in \partial B(y,R)$ of the geodesic be any point in the support of $\mu$, this inequality means $\cos(\alpha(x)) \leq 0$ for some $x$ in the support of $\mu$, meaning that $|\alpha(x)|\geq \frac{\pi}{2}$.  Therefore, since the points $y$, $x$ and $z$ form a triangle in the $CAT($k$)$ space with the angle at $y$ equal to $\alpha(x) \geq \frac{\pi}{2}$, we have by \cite[8.3.1]{AlexanderKapovitchPetrunin}

$$
D \geq d(x,z) \geq d_k(R,R,\alpha(x)) \geq d_k(R,R,\frac{\pi}{2}) = S(R,\infty,k)
$$
where $d_K(l_1,l_2,\alpha)$ denotes the length of the third side of a triangle in the model space of constant curvature $k$ with two side lengths equal to $l_1$ and $l_2$ and an angle of $\alpha$ between them.

Now, suppose further that there exists a variance maximizing $\mu$ supported on $n+1$ points, so that $\mu=\sum_{i=1}^{n+1}\lambda_i\delta_{x_i}$    with each $\lambda_i>0$ and $\sum_{i=1}^{n+1}\lambda_i=1$.  Assume without loss of generality that $\lambda_1=\max_i\lambda_i$ and choose the geodesic $y(\cdot)$ so that $y(R) =x_1$.  We then have
$$
\sum_{i=1}^{n+1}\lambda_i\cos(\alpha(x_i)) \leq 0,
$$
where each $\alpha(x_i)$ is the angle at $y=y(0)$ between the geodesic $y(t)$ from $y$ to $x_1$, and the geodesic from $y$ to $x_i$.  Let $C=\min_i\cos(\alpha(x_i)) \leq 0$.  Then the above yields
\begin{eqnarray*}
-\lambda_1 &\geq & \sum_{i=2}^{n+1}\lambda_i\cos(\alpha(x_i))\\
&\geq & C\sum_{i=2}^n\lambda_i\\
&\geq &Cn\lambda_1.
\end{eqnarray*}
Therefore, $C\leq -\frac{1}{n}$.  Assuming without loss of generality that $C=\cos(\alpha(x_2))$, we have, again by \cite[8.3.1]{AlexanderKapovitchPetrunin},
$$
D \geq d(x_1,x_2) \geq d_K(R,R,\arccos (-\frac{1}{n}))=S(R,n,k),
$$
as desired.
\end{proof}

\begin{remark}
	In general, the inequality $D \geq S(R,\infty,k)$ is the best we can hope for (note that the notion of CAT($k$) space does not come with a dimension).
	 Dekster \cite{Dekster97} proves $D \geq S(R,n,k)$ under (a strengthening of) the additional assumption that  the intersection  $\omega( X \cap \partial B(y,R))$  is contained in a set isometric to the $(n-1)$ -- dimensional unit sphere (here $\omega( X)$ is the image of $X$ under the canonical mapping into the space of directions at $y$), as is always the case, for example, on an $n$-dimensional Riemannian manifold with sectional curvature less than $k$.  Under Dekster's assumption, Cartheodory's theorem implies that that $\mu$ can be taken to be supported on $n+1$ points, as hypothesized by Lang and Schroeder \cite{LangSchroeder97} and in our version above.
\end{remark}
\bibliographystyle{plain}
\bibliography{biblio}
\end{document}

config: arxiv


TITLE: Composition of convex functions
QUESTION [3 upvotes]: If $f$ is increasing convex function and $g$ is convex function then $f\circ g$ is also convex function.
But can anyone give a counterexample where $f$ is decreasing convex and $g$ convex but $f\circ g$ is NOT convex?

REPLY [1 votes]: First exampke that comes to mind is, on $(0,\infty) $, $f (x)=1/x $, $g (x)=1/\sqrt x $. Then $f (g (x))=\sqrt x $, not convex.

REPLY [1 votes]: How about $f(x) = x^{-1/2}$ and $g(x) = x^{-1}$ for $x>0$.

REPLY [1 votes]: $g(x)=x^2$, $f(x)=(\frac{1}{2})^x$. Then $f\circ g (x)=(\frac{1}{2})^{x^2}$ is not convex


TITLE: If $f$ and $g$ are homotopic, then $H_n(f) = H_n(g)$ proof question
QUESTION [1 upvotes]: From Rotman's Algebraic Topology:

Theorem : If $f$ and $g$ are homotopic, then $H_n(f) = H_n(g)$.
It suffices to construct homomorphisms $P_n^X: S_n(X) \rightarrow S_{n+1}(X \times I)$ with $\lambda_{1 \text{#}}^X - \lambda_{0 \text{#}}^X = \partial_{n+1} P_n^X + P^X_{n-1}\partial_n$.
Where:
$(1.)$ $\lambda_i^X : X \rightarrow X \times I$ by $x \mapsto (x,i)$
$(2.)$ $\lambda_{i \text{#}}^X: S_n(X) \rightarrow S_{n}(X \times I )$ by $\sigma \mapsto \lambda_i^X \sigma$
$(3.)$ $\partial \sigma = \sum_{i=0}^n (-1)^{i} \epsilon_i^n$
$(4.)$ $\epsilon_i^n$ is defned as the affine map $\epsilon_i^n : \Delta^{n-1} \rightarrow \Delta^{n}$ taking vertices $\{e_0, e_1, \dots, e_{n-1}\}$ to $\{e_0, \dots, \hat e_i, \dots, e_n\}$ preserving the displayed orderings: $e_i^n: (t_0, \dots, t_{n-1}) \mapsto (t_0, \dots, t_{i-1}, 0, t_{i}, \dots, t_{n-1})$.

And the first part of the proof where I have my question:

Define $P_0^X(\sigma) : \Delta^1 \rightarrow X \times I$ by $t \mapsto (\sigma(\epsilon_0), t)$, and thendefine $P_0(X) : S_0(X) \rightarrow S_1(X \times I)$ by extending by linearity.
Then evaluating $\partial_1 P_0^X \sigma$, we have $\partial_1 P_0^X \sigma = (\sigma(e_0), 1) - (\sigma(e_0), 0)$.

My question is:
How is $\partial_1 P_0^X \sigma = (\sigma(e_0), 1) - (\sigma(e_0), 0)$?
By definition: $\partial_1 P_0^X \equiv \sum_{i=0}^{1} (-1)^i P_0^X \sigma \epsilon_i^1 \equiv P_0^X \sigma ((0, 1)) -  P_0^X \sigma ((1, 0))$ since $\epsilon_0^1 : \{1\} \mapsto (0, 1)$ and $\epsilon_1^1 : \{1\} \mapsto (1,0)$.
And since $\Delta^1 \equiv \{(t_0, t_1) \in \Bbb R^2 : t_0 + t_1 = 1, t_i \ge 0\} = \{t_0 \in \Bbb R : 0 \le t_0 \le 1\}$ (since $t_1 = 1 - t_0$), shouldn't it equal $\partial_1 P_0^X \sigma = (\sigma(e_0), 0) - (\sigma(e_0), 1)$?

REPLY [2 votes]: Let's examine in detail what's going on in the proof.
First you start with a function $\sigma: \Delta^0 \rightarrow X$. This function maps $e_0$, which is the only point in $\Delta^0$, to a single point in $X$, namely $\sigma(e_0)$.
You then define $P_0^X(\sigma) : \Delta^1 \rightarrow X \times I$ by $t \mapsto (\sigma(e_0), t)$. What this function is doing is taking a $t$ in the one dimensional simplex $\Delta^1$ (which is homeomorphic to the unit interval $[0,1]$) and mapping it to the point in $X \times I$ with first coordinate a fixed point (the image of the only point $e_0$ in $\Delta^0$ under $\sigma$) and second coordinate $t$.
So $P_0^X(\sigma)$ is a function with first component the constant map $t \mapsto \sigma(e_0)$ and second component the identity $\operatorname{Id}_{\Delta^1}$
Finally:
$$\partial_1 P_0^X = \sum_{i=0}^{1} (-1)^i P_0^X \sigma \epsilon_i^1 = P_0^X \sigma ((0, 1)) -  P_0^X \sigma ((1, 0))= \\ (\sigma(e_0),\operatorname{Id}_{\Delta^1})((0,1))-(\sigma(e_0),\operatorname{Id}_{\Delta^1})((1,0))=(\sigma(e_0),1)-(\sigma(e_0),0)$$


TITLE: Pressure variation created due to just changing the configuration of the system
QUESTION [1 upvotes]: Let there be a beaker that has a opening in the top and now we just place some kind of a metal plate or something due to which the top gets closed and we can consider the system to be isolated now. What would be the pressure inside? Would it change ?

REPLY [0 votes]: Actually, it depends on how good of a heat conductor the material used for the body of the beaker and the top is. As you say, you can't isolate the system by a metal plate or (something like that) on the top. The glass used in the beaker may be considered to be a good insulator to some extent but the  material used for the top can't be. The system may not be completely isolated and as a result allow transfer of mass or energy or both.
We can also get it by applying the famous equation of state for ideal gases to our system (the beaker). Air can be approximated to be an ideal gas for a while.
$$P_\text{sys}=\frac{nRT_\text{sys}}V$$
Here we can clearly see that in the system you suggest, either $n$ or $T$ or both may change which will affect the pressure inside. So unless you attain a very good level of isolation like in a thermos flask, $P_\text{sys}$ and $T_\text{sys}$ will very soon change to match $P_\text{surr}$ and $T_\text{surr}$.


TITLE: Coloring the integers with red, blue, and green
QUESTION [1 upvotes]: Can all integers can be painted either red, blue, or green such that there exists at least $1$ integer of each color, and if any $3$ integers $a$, $b$, and $c$ have the same color then $a+b$, $a+c$, $b+c$, and $a+b+c$ also have the same colour?

REPLY [3 votes]: You want the red, blue and green sets to be closed under addition.  Can you partition the integers into such sets?
Big hint:

 Consider the signs of the integers.


text:
\section{Initial-value instability of standard accelerated gradient descent}
\label{sec:instability}
\subsection{Main theorem and lemmas}
In this section we show that standard accelerated gradient descent \citep{Nesterov-18} may not be initial-value stable even for strongly convex and smooth objectives in the sense that the initial infinitesimal difference may grow exponentially fast.
This provides an evidence on the necessity of acceleration-stability tradeoff.

We formally define the standard deterministic AGD in \cref{algo:agd} for $L$-smooth and $\mu$-strongly-convex objective $F$  \citep{Nesterov-18}.
\begin{algorithm}
    \caption{Nesterov's Accelerated Gradient Descent Method (\agd)}
    \begin{algorithmic}[1]
        \label{algo:agd}
        \Procedure{\agd}{$w_0^{\mathrm{ag}}, w_0, L, \mu$}
        \State $\kappa \gets L/\mu$
        \For{$t = 0, \ldots, T-1$}
        \State $w_t^{\mathrm{md}} \gets \frac{1}{\sqrt{\kappa} + 1} w_t + \frac{\sqrt{\kappa}}{\sqrt{\kappa} + 1} w_t^{\mathrm{ag}} $
        \State $w_{t+1}^{\mathrm{ag}} \gets w_t^{\mathrm{md}} - \frac{1}{L} \nabla F(w_t^{\mathrm{md}})$
        \State $w_{t+1} \gets \left( 1 - \frac{1}{\sqrt{\kappa}} \right)w_t + \frac{1}{\sqrt{\kappa}} w_t^{\mathrm{md}} - \sqrt{\frac{1}{L \mu}} \nabla F(w_t^{\mathrm{md}})$
        \EndFor
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

Now we introduce the formal theorem on the initial-value instability.
\begin{theorem}[Initial-value instability of deterministic standard \agd, complete version of \cref{instability:sketch}]
    \label{instability:full}
    For any $L, \mu > 0$ such that $\nicefrac{L}{\mu} \geq 25$, and for any $K \geq 1$, there exists a 1D objective $F$ that is $L$-smooth and $\mu$-strongly-convex, and an $\varepsilon_0 > 0$, such that for any positive $\varepsilon < \varepsilon_0$, there exists $w_0, u_0, w_0^{\mathrm{ag}}, u_0^{\mathrm{ag}}$ such that $|w_0 - u_0| \leq \varepsilon$, $|w_0^{\mathrm{ag}} - u_0^{\mathrm{ag}}| \leq \varepsilon$, but
    the sequence $\{w_t^{\mathrm{ag}}, w_t^{\mathrm{md}}, w_t\}_{t=0}^{3K}$ output by $\agd(w_0^{\mathrm{ag}}, w_0, L, \mu)$ and sequence
    $\{u_t^{\mathrm{ag}}, u_t^{\mathrm{md}}, u_t\}_{t=0}^{3K}$ output by $\agd(u_0^{\mathrm{ag}}, u_0, L, \mu)$ satisfies
    \begin{equation}
        |w_{3K} - u_{3K}| \geq \frac{1}{2} \varepsilon (1.02)^K,
        \qquad
        |w^{\mathrm{ag}}_{3K} - u^{\mathrm{ag}}_{3K}| \geq \varepsilon (1.02)^K.
    \end{equation}
\end{theorem}

We first introduce the supporting lemmas for \cref{instability:sketch}. \cref{instability:1} shows the existence of an objective $F$ and a trajectory of \agd on $F$ such that $F''(w_t^{\mathrm{md}})=L$ (including also the neighborhood) once every three steps and $F''(w_t^{\mathrm{md}})=\mu$ otherwise. The proof of \cref{instability:1} is deferred to \cref{sec:instability:1}.
\begin{lemma}
    \label{instability:1}
    For any $L > \mu > 0$, and for any $K \geq 1$, there exists a 1D objective $F$ that is $L$-smooth and $\mu$-strongly convex, a neighborhood bound $\delta > 0$, and initial points $w_0$ and $w_0^{\mathrm{ag}}$ such that the sequence $\{w_t^{\mathrm{ag}}, w_t^{\mathrm{md}}, w_t\}_{t=0}^{3K-1}$ output by $\agd(w_0^{\mathrm{ag}}, w_0, L, \mu)$ satisfies for any $t = 0, \ldots, 3K-1$,
    \begin{align}
        \text{ if }  t \mathrm{~mod~} 3 \neq 1, \text{ then } F''(w) \equiv \mu \text{, for all } w \in [w_t^{\mathrm{md}}-\delta, w_t^{\mathrm{md}} + \delta],
        \\
        \text{ if }  t \mathrm{~mod~} 3 = 1, \text{ then } F''(w) \equiv L \text{, for all } w \in [w_t^{\mathrm{md}}-\delta, w_t^{\mathrm{md}} + \delta].
    \end{align}
\end{lemma}

The following \cref{instability:2} analyzes the growth of the difference of two instances of \agd. The proof is very similar to the analysis of \fedac.
\begin{lemma}
    \label{instability:2}
    Let $F$ be a $L$-smooth and $\mu>0$-strongly convex 1D function.
    Let $(w_{t+1}^{\mathrm{ag}}, w_{t+1})$, $(u_{t+1}^{\mathrm{ag}}, u_{t+1})$ be generated by applying one step of \agd on $F$ with hyperparameter $(L, \mu)$ from $(w_t^{\mathrm{ag}}, w_t)$ and $(u_t^{\mathrm{ag}}, u_t)$, respectively. Then there exists a $\zeta_t$ within the interval between $w_t^{\mathrm{md}}$ and $u_t^{\mathrm{md}}$, such that
    \begin{equation}
        \begin{bmatrix}
            w_{t+1}^{\mathrm{ag}} - u_{t+1}^{\mathrm{ag}}
            \\
            w_{t+1} - u_{t+1}
        \end{bmatrix}
        =
        \begin{bmatrix}
            \frac{\sqrt{\kappa}}{\sqrt{\kappa} + 1} \left(1- \frac{1}{L} F''(\zeta_t) \right)
            &
            \frac{1}{\sqrt{\kappa} + 1} \left(1- \frac{1}{L} F''(\zeta_t) \right)
            \\
            \frac{1}{\sqrt{\kappa} + 1} \left(1- \frac{1}{\mu} F''(\zeta_t) \right)
            &
            \frac{\sqrt{\kappa}}{\sqrt{\kappa} + 1} \left(1- \frac{1}{L} F''(\zeta_t) \right)
        \end{bmatrix}
        \begin{bmatrix}
            w_{t}^{\mathrm{ag}} - u_{t}^{\mathrm{ag}}
            \\
            w_{t} - u_{t}
        \end{bmatrix}.
    \end{equation}
\end{lemma}
\begin{proof}[Proof of \cref{instability:2}]
    This is a special case of \cref{fedac:general:stab} with no noise.
\end{proof}

With \cref{instability:1,instability:2} at hand we are ready to prove \cref{instability:full}. The proof follows by constructing an auxiliary trajectory for around the one given by \cref{instability:1}.
\begin{proof}[Proof of \cref{instability:full}]
    First apply  \cref{instability:1}.
    Let $F$ be the objective, $(w_0^{\mathrm{ag}}, w_0)$ be the initial point and $\delta$ be the neighborhood bound given by  \cref{instability:1}.
    Since $\{w_t^{\mathrm{ag}}, w_t^{\mathrm{md}}, w_t\}_{t=0}^{3K-1}$ is a continuous function with respect to the initial point $(w_0^{\mathrm{ag}}, w_0)$, there exists a $\varepsilon_0$ such that for any $(v_0^{\mathrm{ag}}, v_0)$ such that $|v_0^{\mathrm{ag}} - w_0^{\mathrm{ag}}| \leq \varepsilon_0$ and $|v_0 - w_0| \leq \varepsilon_0$, trajectory $\{v_t^{\mathrm{ag}}, v_t^{\mathrm{md}}, v_t\}_{t=0}^{3K}$ output by \agd $(v_0^{\mathrm{ag}}, v_0, L, \mu)$ satisfies $\max_{0 \leq t < 3K} |v_t^{\mathrm{md}} - w_t^{\mathrm{md}}| \leq \delta$.

    Thus, by \cref{instability:2}, for any $t = 0, \ldots, 3K -1$,
    \begin{alignat}{2}
        \begin{bmatrix}
            w_{t+1}^{\mathrm{ag}} - v_{t+1}^{\mathrm{ag}}
            \\
            w_{t+1} - v_{t+1}
        \end{bmatrix}
        & =
        \begin{bmatrix}
            1 - \frac{1}{\sqrt{\kappa}}
            &
            \frac{1}{\kappa}(\sqrt{\kappa} - 1)
            \\
            0
            &
            1 - \frac{1}{\sqrt{\kappa}}
        \end{bmatrix}
        \begin{bmatrix}
            w_{t}^{\mathrm{ag}} - v_{t}^{\mathrm{ag}}
            \\
            w_{t} - v_{t}
        \end{bmatrix},
        \quad
        &&
        \text{if } t \mathrm{~mod~} 3 \neq 1;
        \\
        \begin{bmatrix}
            w_{t+1}^{\mathrm{ag}} - v_{t+1}^{\mathrm{ag}}
            \\
            w_{t+1} - v_{t+1}
        \end{bmatrix}
        & =
        \begin{bmatrix}
            0
            &
            0
            \\
            1 - \sqrt{\kappa}
            &
            0
        \end{bmatrix}
        \begin{bmatrix}
            w_{t}^{\mathrm{ag}} - v_{t}^{\mathrm{ag}}
            \\
            w_{t} - v_{t}
        \end{bmatrix},
        \quad
        &&
        \text{if } t \mathrm{~mod~} 3 = 1.
    \end{alignat}
    Hence for any $k = 0, \ldots, K-1$,
    \begin{align}
        \begin{bmatrix}
            w_{3(k+1)}^{\mathrm{ag}} - v_{3(k+1)}^{\mathrm{ag}}
            \\
            w_{3(k+1)} - v_{3(k+1)}
        \end{bmatrix}
        & =
        -
        \begin{bmatrix}
            \frac{1}{\kappa^{\frac{3}{2}}}(\sqrt{\kappa} - 1)^3
            &
            \frac{1}{\kappa^2} (\sqrt{\kappa} - 1)^3
            \\
            \frac{1}{\kappa}  (\sqrt{\kappa} - 1)^3
            &
            \frac{1}{\kappa^\frac{3}{2}} (\sqrt{\kappa} - 1)^3
        \end{bmatrix}
        \begin{bmatrix}
            w_{3k}^{\mathrm{ag}} - v_{3k}^{\mathrm{ag}}
            \\
            w_{3k} - v_{3k}
        \end{bmatrix}
        \\
        & =
        - 2 \left( 1 - \frac{1}{\sqrt{\kappa}} \right)^3
        \begin{bmatrix}
            \frac{1}{2} & \frac{1}{2\sqrt{\kappa}}
            \\
            \frac{1}{2}\sqrt{\kappa} & \frac{1}{2}
        \end{bmatrix}
        \begin{bmatrix}
            w_{3k}^{\mathrm{ag}} - v_{3k}^{\mathrm{ag}}
            \\
            w_{3k} - v_{3k}
        \end{bmatrix}.
    \end{align}
    Note that
    \(
        \begin{bmatrix}
            \frac{1}{2} & \frac{1}{2\sqrt{\kappa}}
            \\
            \frac{1}{2}\sqrt{\kappa} & \frac{1}{2}
        \end{bmatrix}
    \)
    is idempotent, \ie,
    \(
        \begin{bmatrix}
            \frac{1}{2} & \frac{1}{2\sqrt{\kappa}}
            \\
            \frac{1}{2}\sqrt{\kappa} & \frac{1}{2}
        \end{bmatrix}^{K}
        =
        \begin{bmatrix}
            \frac{1}{2} & \frac{1}{2\sqrt{\kappa}}
            \\
            \frac{1}{2}\sqrt{\kappa} & \frac{1}{2}
        \end{bmatrix}.
    \)
    Thus
    \begin{equation}
        \begin{bmatrix}
            w_{3K}^{\mathrm{ag}} - v_{3K}^{\mathrm{ag}}
            \\
            w_{3K} - v_{3K}
        \end{bmatrix}
        =
        \left( -2 \left( 1 - \frac{1}{\sqrt{\kappa}} \right)^3 \right)^K
        \begin{bmatrix}
            \frac{1}{2} & \frac{1}{2\sqrt{\kappa}}
            \\
            \frac{1}{2}\sqrt{\kappa} & \frac{1}{2}
        \end{bmatrix}
        \begin{bmatrix}
            w_{0}^{\mathrm{ag}} - v_{0}^{\mathrm{ag}}
            \\
            w_{0} - v_{0}
        \end{bmatrix}.
    \end{equation}
    Thus for any given $\varepsilon \leq \varepsilon_0$, put $u_0^{\mathrm{ag}} = w_0^{\mathrm{ag}} - \varepsilon$, and $u_0 = w_0 - \varepsilon$, we have
    \begin{align}
        \begin{bmatrix}
            w_{3K}^{\mathrm{ag}} - u_{3K}^{\mathrm{ag}}
            \\
            w_{3K} - u_{3K}
        \end{bmatrix}
        =
        \frac{1}{2} \varepsilon \left( -2 \left( 1 - \frac{1}{\sqrt{\kappa}} \right)^3 \right)^K
        \begin{bmatrix}
            1 + \frac{1}{\sqrt{\kappa}}
            \\
            \sqrt{\kappa} + 1
        \end{bmatrix}.
    \end{align}
    For $\kappa \geq 25$ we have $ \left|2 \left( 1 - \frac{1}{\sqrt{\kappa}} \right)^3 \right| > 1.02 $. Therefore
    \begin{equation}
        | w_{3K}^{\mathrm{ag}} - u_{3K}^{\mathrm{ag}}|
        \geq
        \frac{1}{2} (1.02)^K \cdot \varepsilon,
        \quad
        | w_{3K} - u_{3K}|
        \geq
        (1.02)^K \cdot \varepsilon,
    \end{equation}
    completing the proof.
\end{proof}
As a sanity check, the proof framework above for instability does not apply to the convergence of \agd. For instability, we only need to locally change the curvature to ``separate'' two instances. This trick does not break the convergence proof where the progress depends on the global curvature. We refer readers to \citet{Lessard.Recht.ea-SIOPT16} for the relative discussion.

\subsection{Proof of \cref{instability:1}}
\label{sec:instability:1}
In this section we prove \cref{instability:1} on the existence of objective $F$ and the trajectory with specific curvature at certain intervals. The high-level rationale is that \cref{instability:1} only specifies local curvatures of $F$, and therefore we can modify an objective at certain local points to make \cref{instability:1} satisfied.
Here we provide a constructive approach by incrementally updating $F$.

We inductively prove the following claim.
    \begin{claim}
        \label{instability:induction}
        For any $k = 0, \ldots, K$, there exists a function $H_k$ valued in $[\mu, L]$,
        a neighborhood bound $\delta_k > 0$,  and a pair of initial points $(w_0^{\mathrm{ag}}, w_0)$, such that for objective
        $F_k(w) := \int_0^{w} \int_0^{y} H_k(x) \diff x \diff y$,  the sequence output by \agd($w_0^{\mathrm{ag}}, w_0, L, \mu$) on $F_k$ satisfies $|w_{t_1}^{\mathrm{md}} - w_{t_2}^{\mathrm{md}}| \geq 2\delta_k$ if $t_1 \neq t_2$, and  for any $t = 0, \ldots, 3K - 1$,
        \begin{align}
            & \text{ if }  t \mathrm{~mod~} 3 \neq 1 \text{ or } t \geq 3k, \text{ then } F''(w) \equiv H_k(w) \equiv \mu \text{ for all } w \in [w_t^{\mathrm{md}}-\delta_k, w_t^{\mathrm{md}} + \delta_k];
            \label{eq:curvature:1}
            \\
            & \text{ if }  t \mathrm{~mod~} 3 = 1 \text{ and } t < 3k, \text{ then } F''(w) \equiv H_k(w) \equiv L \text{ for all } w \in [w_t^{\mathrm{md}}-\delta_k, w_t^{\mathrm{md}} + \delta_k].
            \label{eq:curvature:2}
        \end{align}
    \end{claim}
    To simplify the notation, we refer to \cref{eq:curvature:1,eq:curvature:2} as ``curvature conditions'' and denote $\mathcal{U}(x;r) := \{y: |y - x| < r\}$, and $\bar{\mathcal{U}}(x;r) := \{y: |y - x| \leq r\}$.
    \begin{proof}[Inductive proof of \cref{instability:induction}]
        For $k = 0$, we can put $H_0(w) \equiv \mu$ (then $F_k(w) = \frac{1}{2}\mu w^2$) and select any arbitrary initial points $(w_0^{\mathrm{ag}}, w_0)$ as long as $w_{t_1}^{\mathrm{md}} \neq w_{t_2}^{\mathrm{md}}$ for $t_1 \neq t_2$, which is trivially possible.

        Suppose \cref{instability:induction} holds for $k$,
        now we construct $H_{k+1}$ and $\delta_{k+1}$.
        Let $\{{w}_{t,k}^{\mathrm{ag}}, {w}_{t,k}^{\mathrm{md}}, {w}_{t,k}\}_{t=0}^{3K-1}$ be the trajectory output by \agd ($w_0^{\mathrm{ag}}, w_0, L, \mu$) on $F_k$.
        For some positive $\varepsilon_{k} < \frac{1}{2}\delta_k$ to be determined, consider
        \begin{equation}
            \tilde{H}_{k+1}(w) = H_{k}(w) + (L - \mu) \mathbf{1} \left[ w \in \bar{\mathcal{U}}(w_{3k+1, k}^{\mathrm{md}}; \varepsilon_k) \right],
            \quad
            \tilde{F}_{k+1}(w) = \int_0^w \int_0^y \tilde{H}_{k+1}(x) \diff x \diff y.
        \end{equation}
        Let $\{\tilde{w}_{t,k+1}^{\mathrm{ag}}, \tilde{w}_{t,k+1}^{\mathrm{md}}, \tilde{w}_{t,k+1}\}_{t=0}^{3K-1}$
        be  the trajectory output by \agd($w_0^{\mathrm{ag}}, w_0, L, \mu$) on $\tilde{F}_{k+1}$.
        Since the trajectory is continuous with respect to $\varepsilon_k$,
        there exists a $\bar{\varepsilon} < \frac{1}{2} \delta_k$ such that for any $\varepsilon_k < \bar{\varepsilon}$ (which we assume from now on),  it is the case that $|\tilde{w}_{t, k+1}^{\mathrm{md}} - w_{t,k}^{\mathrm{md}}| \leq \frac{1}{2}\delta_k$ for all $t \leq 3k+1$.
        Then let
        \begin{equation}
            {H}_{k+1}(w) = H_{k}(w) + (L - \mu) \mathbf{1} \left[ w \in  \bar{\mathcal{U}}(\tilde{w}_{3k+1, k+1}^{\mathrm{md}}; \varepsilon_k) \right],
            \quad
            {F}_{k+1}(w) = \int_0^w \int_0^y {H}_{k+1}(x) \diff x \diff y.
        \end{equation}
        and let $\{{w}_{t,k+1}^{\mathrm{ag}}, {w}_{t,k+1}^{\mathrm{md}}, {w}_{t,k+1}\}_{t=0}^{3K-1}$
        be  the trajectory output by \agd($w_0^{\mathrm{ag}}, w_0, L, \mu$) on ${F}_{k+1}$.

        Consequently,
        \begin{enumerate}
            \item[(a)] By construction of $H_{k+1}$ and $\tilde{H}_{k+1}$, we have $H_{k+1}(w) = \tilde{H}_{k+1}(w) = H_k(w)$ and $\nabla F_{k+1}(w) = \nabla \tilde{F}_{k+1}(w)$ for all $w \notin \bar{U}(w_{3k+1,k}^{\mathrm{md}}; \delta_k)$.
            \item[(b)] Since $\tilde{w}_{t, k+1}^{\mathrm{md}} \notin \bar{U}(w_{3k+1,k}^{\mathrm{md}}; \delta_k)$, by (a), we can inductively show that $\tilde{w}_{t, k+1}^{\mathrm{md}} = w_{t, k+1}^{\mathrm{md}}$ for $t < 3k+1$, namely the trajectories for $F_{k+1}$ and $\tilde{F}_{k+1}$ are identical up to timestep $t < 3k+1$.
            \item[(c)] Since $|\tilde{w}_{t, k+1}^{\mathrm{md}} - w_{t,k}^{\mathrm{md}}| \leq \frac{1}{2}\delta_k$, by (b), we further have $|w_{t, k+1}^{\mathrm{md}} - w_{t, k}^{\mathrm{md}}| \leq \frac{1}{2} \delta_k$ for $t < 3k + 1$.
            Thus, by (a), the curvature conditions will be satisfied for $w_{t, k+1}^{\mathrm{md}}$ and $H_{k+1}$ up to $t < 3k+1$ and any neighborhood bound $\delta_{k+1} < \frac{1}{2} \delta_k$ since $H_{k+1} \equiv H_k$ for $w \notin \bar{U}(w_{3k+1,k}^{\mathrm{md}}; \delta_k)$.
            \item[(d)] By (b), we have $w_{3k+1, k+1}^{\mathrm{md}} = \tilde{w}_{3k+1, k+1}^{\mathrm{md}}$ since all previous gradients evaluated are identical for $F_{k+1}$ and $\tilde{F}_{k+1}$. Thus, by construction of $H_{k+1}$ the curvature conditions hold for $w_{3k+1,k+1}^{\mathrm{md}}$ and $H_{k+1}$.
            \item[(e)] Similarly, for sufficiently small $\varepsilon_k$, we have $|w_{t, k+1}^{\mathrm{md}} - w_{t,k}^{\mathrm{md}}| \leq \frac{1}{2} \delta_k$ for $t > 3k+1$, and the curvature conditions also hold for $t > 3k+1$.
        \end{enumerate}
        Summarizing (c), (d), and (e) completes the induction.
    \end{proof}
\begin{proof}[Proof of \cref{instability:1}]
    Follows by applying \cref{instability:induction}.
\end{proof}


TITLE: Question about divergent series
QUESTION [1 upvotes]: Is it true that if $(a_n) \geq 0$ and $\displaystyle\sum_1^\infty a_n$ diverges, then $\displaystyle\sum_1^\infty a_n(1-r^n)$ diverges for all $r \in (0,1)$? I think it's true but I'm having a hard time proving it.

REPLY [3 votes]: Hint: If $\displaystyle\sum_1^\infty a_n(1-r^n)$ converges then $\displaystyle a_n = \frac{a_n(1-r^n)}{1-r^n} \to 0$ and hence $\displaystyle\sum_1^\infty a_n r^n$ also converges.


TITLE: How to find $\mathbb{P}\left(\int_0^1W_tdt>\dfrac{2}{\sqrt{3}}\right)$?
QUESTION [2 upvotes]: How to find $\mathbb{P}\left(\int_0^1W_tdt>\dfrac{2}{\sqrt{3}}\right)$? Where $W_t$ is Browninan Motion.
What I have done is, for $Z\sim N(0,1)$:
$$\begin{align}
\mathbb{P}\left(\int_0^1W_tdt>\dfrac{2}{\sqrt{3}}\right) &= \mathbb{P}\left(\int_0^1\sqrt{t}Zdt>\dfrac{2}{\sqrt{3}}\right)\\
&= \mathbb{P}\left(Z\dfrac{2}{3}>\dfrac{2}{\sqrt{3}}\right)\\
&= \mathbb{P}\left(Z>\sqrt{3}\right)\\
&= \dfrac{1}{\sqrt{2\pi}}\int_\sqrt{3}^\infty e^{-\frac{z^2}{2}}dz\\
&= -N\left(-\sqrt{3}\right)
\end{align}$$
Any help would be very much appreciated.

REPLY [2 votes]: We first show that
$$ \int_0^t W_s \,\mathrm{d}s \sim N\left(0,\frac13 t^3 \right).$$
Indeed, the integral is defined as a limit of Riemann sums; since each of these sums are normally distributed, the limiting integral is also normally distributed (this can be proven using characteristic functions, for instance). Applying Fubini's theorem,
$$ \mathbb{E} \left[\int_0^t W_s \,\mathrm{d}s \right] = \int_0^t \mathbb{E}[W_s] \,\mathrm{d}s = \int_0^t 0 \,\mathrm{d}s = 0,$$
where the interchange of limits is permissible since w.p.1 the function $s \mapsto W_s$ is continuous and hence bounded on a compact interval. Finally,
\begin{align*}
\mathrm{Var}\left(\int_0^t W_s \,\mathrm{d}s\right)
&= \mathbb{E}\left[\left(\int_0^t W_s \,\mathrm{d}s\right)^2\right] \\
&= \mathbb{E}\left[\left(\int_0^t W_s \,\mathrm{d}s\right)\left(\int_0^t W_u \,\mathrm{d}u\right)\right] \\
&= \mathbb{E}\left[\int_0^t \int_0^t W_sW_u \,\mathrm{d}s \mathrm{d}u \right] \\
&= \int_0^t \int_0^t \mathbb{E}[W_sW_u] \,\mathrm{d}s \mathrm{d}u \\
&= \int_0^t \int_0^t \min(s,u) \,\mathrm{d}s \mathrm{d}u \\
&= 2 \int_0^t \int_0^u s \,\mathrm{d}s \mathrm{d}u  \\
&= \int_0^t u^2 \mathrm{d}u  \\
&= \frac{1}{3}t^3,
\end{align*}
where we use the fact that $\mathrm{Cov}(W_s, W_t) = \min(s, t)$ and Fubini again to pass the expectation inside. It follows that
$$ \sqrt{3} \int_0^1 W_s \,\mathrm{d}s \sim N(0,1), $$
and
$$\mathbb{P}\left(\int_0^1 W_s \,\mathrm{d}s \geq \frac{2}{\sqrt{3}} \right) = 1 - \Phi(2),$$
where $\Phi$ is the standard normal cdf.

REPLY [1 votes]: The law of $(W_t)_{0\leq t\leq 1}$ is not the same as that of $(\sqrt{t}Z)_{0\leq t \leq 1}$. So there is no reason $\int_{0}^{1} W_t \, dt$ and $\int_{0}^{1} \sqrt{t}Z \, dt$ have the same law, and as it turns out they have different laws.
Since $X = \int_{0}^{1} W_t \, dt$ is gaussian, it suffices to determine its mean and variance. And they can be computed as
$$ \mathbb{E}[X]=\int_{0}^{1} \mathbb{E}[W_t] \, dt = 0$$
and
$$ \mathbb{E}[X^2]
= \int_{0}^{1} \int_{0}^{1} \mathbb{E}[W_s W_t] \, dsdt
= \int_{0}^{1} \int_{0}^{1} s \wedge t \, dsdt = \frac{1}{3}. $$
So $X \sim \mathcal{N}(0, \frac{1}{3})$ and hence $X \stackrel{d}{=} \frac{1}{\sqrt{3}}Z$. This gives
$$ \mathbb{P}(X > \tfrac{2}{\sqrt{3}}) = \mathbb{P}(Z > 2). $$


TITLE: QCQP with bilinear constraints
QUESTION [1 upvotes]: I have the optimization problem in $u := \left(u_{1},u_{2}\right)$
$$\begin{array}{ll} \text{minimize} & \frac{1}{2}u^{\top}\Sigma u-au^{\top}\beta\\ \text{subject to} & u_{1}u_{2}\le0\end{array}$$
where matrix $\Sigma$ is positive definite and $a>0$.
The first-order condition is
\begin{equation}
\nabla f=\Sigma u-\beta a=0\Rightarrow u^{*}=a\Sigma^{-1}\beta=\left(\begin{array}{c}
u_{1}^{*}\\
u_{2}^{*}
\end{array}\right)
\end{equation}
If $u_{1}^{*}u_{2}^{*}>0$ and we assume $f\left(u\right)$ attain minimum at $u^{\#}=\left(\begin{array}{c}
u_{1}^{\#}\\
u_{2}^{\#}
\end{array}\right)$, do we have $u_{1}^{\#}u_{2}^{\#}=0$?
Does anyone know how to show it in a rigorous proof?

REPLY [0 votes]: I have solved the problem based on user7530's comment.
Here is a proof:
Assume $f$ attains minimum at $u^{0}\in\left\{ x\in\mathbb{R}^{2}:x_{1}x_{2}<0\right\}$. Then there exists $r>0$ such that $B\left(u^{0},r\right)\subset\left\{ x\in\mathbb{R}^{2}:x_{1}x_{2}<0\right\} $
Since $f$ is strictly convex, we have $f\left(u^{*}\right)<f\left(u^{0}\right)$ And since $u^{*}\notin\left\{ x\in\mathbb{R}^{2}:x_{1}x_{2}\le0\right\} $, there exists $u^{1}\in B\left(u^{0},r\right)$ such that $u^{1}=\lambda u^{0}+\left(1-\lambda\right)u^{*}$ with $\lambda\in\left(0,1\right)$, then $f\left(u^{1}\right)<\lambda f\left(u^{0}\right)+\left(1-\lambda\right)f\left(u^{*}\right)<f\left(u^{0}\right)$
contradiction! Hence $f$ attains minimum at $u^{0}\in\left\{ x\in\mathbb{R}^{2}:x_{1}x_{2}=0\right\} $.


TITLE: differentials on formal schemes
QUESTION [3 upvotes]: Let $A$ be a topological ring, we say that it is pseudo-compact  if :

there is family of ideals $\Lambda_A$ which gives a basis of neighborhoods of $0$ and such that $A/\mathfrak{a}$ is artinian for every $\mathfrak{a} \in \Lambda_A$
$A$ is complete.

We have $A = \varprojlim\limits_{\mathfrak{a} \in \Lambda_A} A/\mathfrak{a}$
A topological module $M$ over a pseudo-compact ring $A$ is said to be profinite if :

There is a familly of submodules $\Lambda_M$ which forms a basis of neighborhoods of $0$ and such that $M/N$ is finite over $A$ for every $N \in \Lambda_M$
$M$ is complete

We have $M = \varprojlim\limits_{N \in \Lambda_M} M/N$
A profinite $A$ algebra is just an $A$-algebra which is profinite as an $A$ module, it is easy to see that it is in fact a pseudocompact ring.
Now let $A$ be a pseudo-compact ring and $B$ be a profinite $A$ given by a map $f : A \to B$. (We can consider this a map of formal schemes $ :Spf(B) \to Spf(A)$ if we want to be more geometric)
It is very natural to define the differentials of $B$ over $A$ to be
$$\widehat{\Omega}_{B/A} := \varprojlim\limits_{\mathfrak{b},\mathfrak{a}} \Omega_{(B/\mathfrak{b})/(A/\mathfrak{a})}$$
where the limits runs over pairs of ideal over $B$ and $A$ respectively whith $f^{-1}(\mathfrak{b}) \subset \mathfrak{a}$. Indeed we are just saying that $Spf(A)$ is the glueing of real schemes $Spec(A/\mathfrak{a})$ and $Spf(B)$ is the glueing of real schemes $Spec(B/\mathfrak{b})$ over each $Spec(A/\mathfrak{a})$ and we glue our original construction of the Kähler differentials.
you can look at http://www.math.jussieu.fr/~polo/SGA3/Exp7B-23mai11.pdf for much more on the subject of pseudo-compact rings
My question :  I've read that $\widehat{\Omega}_{B/A}$ represent the functor taking a profinite $B$-module to the module of continous derivations from $B$ to $M$. Although it seems intuitive and I'd be glad to accept it as a fact I haven't been able to prove it myself so I'm wondering if someone could give a proof of this (with all the gory details if possible)

REPLY [1 votes]: To answer your question in full would take quite a bit of work (to get all details straight -- if the thing is true) which I am not willing to do. I suggest looking back at where you found this statement and look for a proof there or a reference.
But here is a baby case. Suppose we have a ring map $A \to B$ and a finitely generated ideal $I$ of $B$. Then we can endow every module with respect to the $I$-adic topology and we can consider the $I$-adic completion of a module. Now there are two things we can do to $\Omega_{B/A}$. Namely, we can take its $I$-adic completion
$$
\hat \Omega_{B/A, 1} = \lim \Omega_{B/A}/I^n\Omega_{B/A}
$$
and we can form
$$
\hat \Omega_{B/A, 2} = \lim \Omega_{(B/I^n)/A}
$$
There is a canonical map $\hat \Omega_{B/A, 1} \to \hat \Omega_{B/A, 2}$. I think your question in this case is whether this map is an isomorphism (did not carefully check this --- instead of profinite modules I am considering complete modules). Anyway, the statement is true because the kernel of the surjective map $\Omega_{B/A} \to \Omega_{(B/I^{n + 1})/A}$ is contained in $I^n\Omega_{B/A}$ by Lemma Tag 02HQ. This allows us to define the inverse map.
Hope this helps!


TITLE: Simplifying $\frac{y}{y^2+b^2}$ where $y=b \cot\theta$
QUESTION [1 upvotes]: Could appreciate some help with this question.

I want to simplify the following trigonometric equation.
  $$\frac{y}{y^2+b^2}$$
  where $y=b \cot\theta$.

The solution I got was
$$\frac{1}b \cos\theta$$
Can someone verify and try and guide me through the solution?

REPLY [1 votes]: $$1+\cot^2\theta=1+\frac{\cos^2\theta}{\sin^2\theta}=\frac1{\sin^2\theta}=\csc^2\theta$$ or
$$1+\cot^2\theta=\frac1{\sin^2\theta}$$
Now take reciprocal of both side:
$$\frac{1}{1+\cot^2\theta}=\sin^2\theta$$
If $y=b\cot\theta$, then:
$$\frac{y}{y^2+b^2}=\frac{b\cot\theta}{b^2\cot^2\theta+b^2}=\frac{\cot\theta}{b\left(1+\cot^2\theta\right)}=\frac{1}{b}\cot\theta\sin^2\theta=\frac{1}{b}\frac{\cos\theta}{\sin\theta}\sin^2\theta=\frac{1}{2b}2\cos\theta\sin\theta=\frac{1}{2b}\sin{2\theta}$$


TITLE: Twins Paradox Paradox
QUESTION [2 upvotes]: I've recently has special-relativity explained to be in a rather elegant way. All objects travel at the speed of light in space time. Thus, when you travel faster through the three dimensions of space, the speed at which you travel through time decreases. Photons do not experience time because all their velocity is in the spatial directions and none of it is in time.
Considering the 4-dimensional universe this invokes, how can I ever interact with anything that has traveled at a different velocity than me unless it changes direction to meet me?
In the terms of the twin paradox, how is it possible for the twins to meet? Twin A, stays on earth traveling at a fixed speed in spacetime. Twin B leaves earth traveling faster in space and slower in time but still traveling at c in spacetime.
Some basic geometry tells me that if two objects forced to travel at a fixed speed from the same origin in changeable directions (in any number of dimensions) that there is no way their future locations can be the same unless they both change direction to provide the possibility of intersection.
If Earth is traveling at a fixed speed and Twin B is traveling at a fixed speed in a space (no matter the dimension) then there is no way they could ever be in the same location in spacetime again unless the earth changes direction and meets Twin B in the middle.
Wouldn't they be forever doomed to be in different places along the axis of time unless Twin A goes on a relativistic voyage to allow Twin B to catch up? Should we not expect time to behave the same way as the spacial dimensions?

REPLY [3 votes]: That way of thinking about this is a nice one. From “The Elegant Universe”?
Anyway, mathematically, you can define this four-velocity like the normal velocity, the time derivative of the position. However, in special relativity, the position is space and time $(t, x, y, z)$. And the derivative has to be with respect to the proper time (or curve parameter) $\tau$:
$$ u = \frac{\mathrm d}{\mathrm d\tau} x $$
The velocities that you normally measure are calculated with respect to $t$. So we need the chain rule here:
$$ \frac{\mathrm d}{\mathrm d\tau} = \gamma \frac{\mathrm d}{\mathrm dt}$$
So the four-velocity is, taking $c = 1$:
$$ u = \gamma \frac{\mathrm d}{\mathrm dt} (t, x, y, z) = \gamma (1, v_x, v_y, v_z) $$
As you said:

All objects travel at the speed of light in space time.

That means that $|u| = 1$. With the Minkowsi metric, this is:
$$ 1 = \gamma^2 - \gamma^2( v_x^2 + v_y^2 + v_z^2) $$
This means that you travel less through time when you travel through space. But since the equation are for the squares of the velocities, you can indeed have $v_x < 0$.
So the twin that is on the journey can have $v_x > 0$ for the first half and then $v_x < 0$ for the second part and go back to earth. That is not a problem.
If you look at a space time diagram of this, you can construct the time intervals for each party. The observer on the earth will have gone through a couple of time steps. When you draw in the planes of simultaneity of the observer on earth, you will see the time intervals for the traveling observer. There, you can see that the earth time intervals are much longer for the traveler. He will only experience a bit more than two of those intervals during his journey. Therefore, he is younger.
So, when they meet at a space time point again, their age is different. They cannot meet at the space time point where earth is the same age as the traveler, though.


TITLE: As shown in the figure: Prove that $a^2+b^2=c^2$
QUESTION [17 upvotes]: Geometry: Buildings in the triangle

Other triangles with the same property:
$1.$  12  18   6  12  30 102
$2.$  15  30  15  15  15  90
$3.$  24  30  54  24   6  42
$4.$  30  10  40  30  20  50 (proposed problem in sense of clockwise)
$5.$  36  12   6  12  18  96
$6.$  36  18   6  36   6  78
$7.$  42   6  36  42  12  42
$8.$  60   6  57  30   3  24
$9.$  60  24  12  12   6  66
Using matlab we can find all triangles (integer solutions) with this property sums of squares:

REPLY [6 votes]: I thought that this problem should be solvable without using trigonometry. Here's a hint for a geometric solution:

Draw the segment $DG$ and let $B'$ be the intersection of the line through $AE$ and the perpendicular line to $DG$. I claim that the triangle $DB'G$ has sides of length $a,b,c$, so $c^2 = a^2 + b^2$ by the Pythagorean theorem.
Since geometry is hard to communicate, I think it is better to let you figure this out on your own.