TITLE: Need help in dividing a set into different pairs
QUESTION [0 upvotes]: In how many ways can you divide the set of eight numbers {2,3,4,5,6,7,8,9} into 4 pairs such that no pair of numbers has G.C.D equal to 2?

REPLY [0 votes]: $2$ must be paired with an odd number.
$6$ can not be paired with an even number that doesn't also have three as a divisor so $6$ must be paired with an odd number.
$4$ may (but doesn't have to be) paired with $8$ and there are no other restrictions.
There are $4$ odd numbers to pair with TWO.
And after that there are $3$ remaining odd numbers to pair with SIX.
And for the remaining four numbers there are ${4\choose 2}$ ways to choose a the third pair and ${2 \choose 2} =1$ way to choose the last pair.
But choosing $(a,b)$ then $(c,d)$ is the same as $(c,d) $ then $(a,b)$ so this is double counting.  There are $\frac 62 = 3$ ways to choose the final two pairs.
(Alternatively given any of the $4$ remaining unpaired numbers there are $3$ numbers we can pair with it.  And the remaining to numbers must pair together.)
So there are $4*3*3 = 36$ such ways.


text:
\begin{document}
\maketitle

\input{abstract}

\begin{keywords} mean field games, common noise, forward-backward stochastic differential equations, stochastic maximum principle. \end{keywords}

\begin{AMS} 93E20, 60H30, 60H10, 49N70, 49J99.\end{AMS}

\pagestyle{myheadings}
\thispagestyle{plain}
\markboth{SARAN AHUJA}{MEAN FIELD GAMES WITH COMMON NOISE}

\section{Introduction}\label{introduction}
\input{Introduction}
\section{Model}\label{model}
\input{Model}

\section{Stochastic Maximum Principle}\label{smp_fbsde}
\input{SMP}

\section{Existence and Uniqueness of $\tsg$-MFG solution}\label{mainresult} In this section, we state and prove our main result which establishes an existence and uniqueness of a solution to Mean Field Games with a common noise.

In \cite{Carmona1}, Carmona and Delarue showed existence of $0$-MFG solution using SMP approach. They established the result under a convexity assumption and what they called a \textit{weak mean-reverting} assumption on the cost function. The latter states that for all $x \in \R$ and a constant $C > 0$.
\begin{equation}\label{weakMR}
 xg_x(0,\delta_x) \geq -C(1+|x|)
 \end{equation}
 where $\delta_x$ denote the Dirac measure at $x$. They first proved the result under a bounded derivative assumption on the  function, then relaxed this assumption using an approximation argument.

 In \cite{cardaliaguet2010}, using PDE method, Lasry and Lions showed the same result under similar assumptions plus boundedness condition on the cost function. They gave existence of a classical solution to a coupled HJB-FP equation. The uniqueness was shown in both works \add{\cite{cardaliaguet2010,Carmona1}} under the following \textit{monotonicity} condition (in $m$) on the cost function, i.e
$$ \int (g(x,m_1)-g(x,m_2))d(m_1-m_2)(x) \geq 0 $$
for any $m_1,m_2 \in \Ptwo$. This condition can be expressed in terms of random variables as follows: For any \del{$\xi,\xi' \in \Ltwo$ (over an arbitrary probability space).} \add{square-integrable random variables $\xi$ and $\xi'$ defined on a common probability space,}
\begin{equation}\label{monLion}
 	 \mb{E}\l[ g(\xi',\Law(\xi')) +g(\xi,\Law(\xi)) - g(\xi,\Law(\xi')) - g(\xi',\Law(\xi)) \r] \geq 0
\end{equation}
where $\Law(\cdot)$ denote the law of a random variable.

In the existence proof of both the Lasry and Lions PDE approach and the Carmona and Delarue probabilistic approach, they applied Schauder's theorem to establish an existence of a fixed point. However, this strategy cannot be extended simply in the presence of common noise as we no longer have a deterministic flow of probability measures given by the law of the optimal state process. Instead, we have to deal with a \textit{random} flow of probability measures from a \textit{conditional} law given a common noise. Working with this larger space, we cannot establish compactness which is necessary to apply the Schauder fixed point theorem in the same way.

\add{In parallel to our work, Carmona et al. \cite{carmona2014commonnoise} overcome this issue by using discretization of the common noise path. Working with this finite-dimensional approximation, they were able to prove the existence of a solution to the discretized MFG and obtain the existence of the original MFG by refining the approximation and passing the limit. This construction gives the \textit{weak} limit and leads to a notion of a  \textit{weak MFG} solution.}

\del{As a result, we will use} \add{In this work, however, we adopt an alternative approach}, namely the Banach fixed point theorem. In the same way as in the proof of wellposedness of FBSDE, the Banach fixed point theorem can be used to establish existence of a solution when the time duration $T$ is sufficiently small. This method can usually be applied in that case because the solution estimate depends on $T$,  and when $T$ is sufficiently small, we can get a contraction map easily. See \cite{Antonelli,Ma1999} for proofs of existence and uniqueness of a solution to FBSDE for a small time duration. However, the small time restriction is not a desirable assumption for obvious reasons, so we wish to extend the solution to arbitrary time duration. To do so, we need an extra condition on $g$ to be able to control the Lipschitz constant of a new terminal condition as we move backwards in time. So in addition to $\ref{a1},\ref{a2}$, we will need the following assumptions on $g$

\begin{assump}\label{a3}(Lipschitz in $m$) $g_x$ is Lipschitz continuous in $m$ uniformly in $x$, i.e. there exist a constant $C_g$ such that
	$$ |g_x(x,m)-g_x(x,m')|  \leq C_g W_2(m,m') $$
	for all $x \in \R, m,m' \in \Ptwo$, where $W_2(m,m')$ is the second order Wasserstein metric defined by (\ref{wass}). This is equivalent to the following; for any $x \in \R$, \del{$\xi,\xi'  \in \Ltwo$} \add{and any square-integrable random variables $\xi$ and $\xi'$ defined on a common probability space,}
	$$ |g_x(x,\Law(\xi))-g_x(x,\Law(\xi'))|  \leq C_g (\mb{E}|\xi-\xi'|^2)^{\frac{1}{2}} $$
\end{assump}
\begin{assump}\label{a4}(weak monotonicity in $m$) For any $m,m' \in \Ptwo$ and any $\gamma \in \P_2(\R^2)$ with marginals $m,m'$ respectively,
	$$ \int_{\R^2} \l[ (g_x(x,m)-g_x(y,m'))(x-y) \r] \gamma(dx,dy) \geq 0 $$
	Equivalently, for any \del{$\xi,\xi' \in \Ltwo$} \add{square-integrable random variables $\xi$ and $\xi'$ defined on a common probability space,}
	\begin{equation}\label{monotone}
		\mb{E}[ g_x(\xi,\Law(\xi)) - g_x(\xi',\Law(\xi'))(\xi-\xi')] \geq 0
	\end{equation}
\end{assump}

\begin{remark}\label{remark_example} An interesting example of $g$ which satisfies \ref{a1}-\ref{a4} is a general quadratic cost where $g$ is of the form
\begin{equation}\label{LQexample}
 g(x,m) = Ax^2 + x \int \psi(y)dm(y) + F(m)
 \end{equation}
 where $\psi:\R \to \R$ and $F: \Ptwo \to \R$ are Lipschitz continuous functions with $\text{Lip}(\psi) \leq 2A $. This form of $g$ includes the following examples
 \begin{gather}
 	g(x,m) = \l( x - \int y dm(y) \r)^2 \label{e1}\\
 	g(x,m) =  \int (x-y)^2 dm(y) \notag
\end{gather}
 which occur frequently in applications (see \cite{carmona2013mean,gueant2011} for instance). More generally, it includes the cost function in the Linear-Quadratic Mean Field Games \cite{bensoussan2014linear} where $g$ takes the form
 $$ g(x,m) = qx^2 + \bar{q}\l(x-s\int y m(y) \r)^2$$
 where $q,\bar{q},s$ are positive constants satisfying $q+\bar{q} \geq s\bar{q}$.
\end{remark}

Our main result establishes, under \ref{a1}-\ref{a4}, the existence and uniqueness of a $\tsg$-MFG solution. In the existence proof, our assumptions are similar to those in \cite{Carmona1} except that we replace the weak mean-reverting condition (\ref{weakMR}) by the weak monotonicity condition (\ref{monotone}). When $\xi = x, \xi' = 0$ is deterministic, (\ref{monotone}) reads
$$ (g_x(x,\delta_x) - g_x(0,\delta_{0}))x \geq 0, \qquad \forall x \in \R$$
where $\delta_x$ denote the Dirac measure at $x$. This implies (\ref{weakMR}), so one can view (\ref{monotone}) as a stronger version of (\ref{weakMR}). For the uniqueness result, when $g$ is convex in $x$, the weak monotonicity condition (\ref{monotone}) is indeed a weaker version of the monotonicity condition (\ref{monLion}) which was used in \cite{cardaliaguet2010,Carmona1} for the uniqueness proof of a $0$-MFG solution. The lemma below shows this.

\begin{lemma}\label{weakerMon} Let $h: \R \times \Ptwo$ be a continuously differentiable function such that $h$ is convex and satisfies the monotonicity condition (\ref{monLion}) stated above, then $h$ satisfies the weak monotonicity condition (\ref{monotone}).
\end{lemma}

\begin{proof} Suppose (\ref{monLion}) holds. Let $\xi,\xi' \in \Ltwo$, then by convexity in $x$ of $h$, we get
$$ h(\xi',\Law(\xi')) - h(\xi,\Law(\xi')) \leq h_x(\xi',\Law(\xi'))(\xi'-\xi) $$
and
$$ h(\xi,\Law(\xi)) - h(\xi',\Law(\xi)) \leq -h_x(\xi,\Law(\xi))(\xi'-\xi) $$
 Summing up, taking expectation, and using (\ref{monLion}) yields (\ref{monotone}).

\end{proof}

The converse of the lemma above does not hold.  Example (\ref{e1}) gives a cost function that is convex in $x$, satisfies (\ref{monotone}), but does not satisfy (\ref{monLion}). Thus, one see that our result gives a more general uniqueness result for $0$-MFG when $g$ is convex in $x$.

\subsection{Uniqueness}\label{uniqueness} We begin by showing uniqueness of a $\tsg$-MFG solution

\begin{theorem}[Uniqueness] \label{main2} Suppose $\ref{a1}-\ref{a4}$ holds, then the $\tsg$-MFG with initial condition $\xi_0 \in \Ltwo_{\F_0}$ has at most one solution.
\end{theorem}

\begin{proof}  Let $\ha^1,\ha^2 \in  \Htwo $ be solutions to $\tsg$-MFG with initial $\xi_0 \in \Ltwo_{\F_0}$, and let $m_t^i = \Law(X^{\ha^i}_t| \tF_t)$ for  $i=1,2$. \add{Recall that $(\tF_t)_{0 \leq t \leq T}$ is the filtration generated by the common noise $(\tW_t)_{0 \leq t \leq T}$.} By Theorem \ref{EUexample} and Corollary \ref{SMPexample}, we have that for $i \in \{1,2\}$,  $\ha^i= -Y^i$ where $(X^i_t,Y^i_t,Z^i_t,\tZ^i_t)_{0\leq t \leq T}$ is the solution to the FBSDE
\begin{gather*}
	 dX_t = -Y_tdt + \sigma dW_t + \tsg \tdW_t \\
	 dY_t =  Z_tdW_t + \tZ_t \tdW_t \\
	 X_0 = \xi_0, Y_T = g_x(X_T,m^i_T)
\end{gather*}
From the fact that $\ha^i$ is the solution to $\tsg$-MFG, we get that $m^i_t$ is precisely the law of $X^i_T$ conditional on $\tF_t$. That is, $(X^i_t,Y^i_t,Z^i_t,\tZ^i_t)_{0\leq t \leq T}$ satisfies, for $i=1,2$,
\begin{gather*}
	 dX^i_t = -Y^i_tdt + \sigma dW_t + \tsg \tdW_t \\
	 dY^i_t =  Z^i_tdW_t + \tZ^i_t \tdW_t \\
	 X^i_0 = \xi_0, Y^i_T = g_x(X^i_T, \Law(X^i_T | \tF_T))
\end{gather*}
Let $\Delta X_t = X^1_t-X^2_t$ and $\Delta Y_t = Y^1_t-Y^2_t$. Using \ito's lemma, we get
$$ \mb{E}[\Delta X_T\Delta Y_T] - \Delta X_0 \Delta Y_0 = - \mb{E}\l[ \int_0^T \Delta Y_t^2 dt \r] $$
Since $\Delta X_0 = 0$ and from (\ref{monotone}), it follows that
\begin{align*}
\mb{E}[\Delta X_T \Delta Y_T] &= \mb{E}[ (X_T^1-X_T^2)(g_x(X_T^1,\Law(X_T^1|\tF_T))-g_x(X_T^2,\Law(X_T^2|\tF_T))] \\
&= \mb{E} \l[ \mb{E}\l[ (X_T^1-X_T^2)(g_x(X_T^1,\Law(X_T^1|\tF_T))-g_x(X_T^2,\Law(X_T^2|\tF_T))\Big| \tF_T \r]\r]  \geq 0
\end{align*}
Thus,
$$   \mb{E}\l[ \int_0^T \Delta Y_t^2 dt \r]   = -  \mb{E}[\Delta X_T\Delta Y_T]  \leq 0 $$
so $\ha^1 = \ha^2$ in $\Htwo$.

\end{proof}

\subsection{Existence} Next, we state and prove the existence result for $\tsg$-MFG.

\begin{theorem}[Existence]\label{main1} Under \ref{a1}-\ref{a4}, there exist a solution to $\tsg$-MFG with initial $\xi_0 \in \Ltwo_{\F_0}$.
\end{theorem}

Before we delve into the  proof, let us first define a following map whose fixed point gives us a $\tsg$-MFG solution. This map is simply the rigorous definition of the diagram (\ref{diagram}) in Section \ref{model}  .

Let $0 \leq s < \tau \leq T$ and $v: \R \times \Ltwo_{\F_\tau} \times \Omega \to \R$ satisties, for $\mb{P}$-a.s.,
\begin{gather}
	 (v(x,\xi, \omega)-v(x',\xi,\omega))(x-x') \geq 0  \label{v1} \\
	 | v(x, \xi,\omega )-v(x',\xi',\omega) |^2  \leq C_v \l[ |x-x'|^2 + \mb{E}\l[(\xi-\xi')^2 \Big| \tF_\tau \r](\omega) \r]  \label{v2}
\end{gather}
for all $x,x' \in \R, \xi,\xi' \in \Ltwo_{\F_\tau}$.

We define a map $\Phi^{s,\tau,\eta,v} : \H^{2}([s,\tau];\R) \to \H^{2}([s,\tau];\R)$ as follows; given $\ha \in  \H^{2}([s,\tau];\R)$, we define $(\hX_t)_{s \leq t \leq \tau}$ to be the state process corresponding to $\ha$ with initial $\eta \in \Ltwo_{\F_s}$, i.e. for $t \in [s,\tau]$,
\begin{equation}\label{stateProcess}
 \hX_{t} =  \eta + \int_s^t \ha_{t} dt + \sigma (W_t - W_s) + \tsg (\tW_t - \tW_s)
 \end{equation}
We then solve the FBSDE
\begin{equation}
	\label{fbsde_phi}
	 \begin{gathered}
dX_{t} = -Y_{t}dt + \sigma dW_{t} + \tsg \tdW_{t}   \\
dY_{t} = Z_{t}dW_{t} +  \tZ_{t}\tdW_{t}\\
X_{s}=\eta,\quad Y_{\tau} = v(X_{\tau},\hX_{\tau})
	\end{gathered}
\end{equation}
and set
$$ \Phi^{s,\tau,\eta,v}(\ha) := -Y = (-Y_t)_{s \leq t \leq \tau}$$
By (\ref{v1}),(\ref{v2}), and Theorem \ref{EUexample}, FBSDE (\ref{fbsde_phi}) is uniquely solvable so the map $\Phi^{s,\tau,\eta,v}$ is indeed well-defined. Furthermore, the fixed point of $\Phi^{0,T,\xi_0,g_x}$ clearly gives $\tsg$-MFG solution with initial $\xi_0$. We are now ready to begin the proof of Theorem \ref{main1}

\begin{proof} We start by considering the map $\Phi^{t,T,\eta,g_x}$, which is well-defined by $\ref{a1}, \ref{a2}$, and Theorem \ref{EUexample}. The lemma below gives a solution over a small time duration.

\begin{lemma}\label{phi3} There exist $\gamma > 0$ depending only on $C_g$ such that for any non-negative $t \in [T-\gamma,T), \Phi^{t,T,\eta,g_x}$ satisfies the following: for any $\eta \in \Ltwo_{\F_t}$, there exist $\ha^{t,T,\eta} \in \H^{2}([t,T];\R)$ such that
$$ \Phi^{t,T,\eta,g_x}(\ha^{t,T,\eta}) = \ha^{t,T,\eta} $$
\end{lemma}

This lemma is a special case of Lemma \ref{phi2} which is stated below. The key point of this lemma is the fact that the small time duration $\gamma$ is independent of $\eta$. It requires us to prove that $\Phi^{t,T,\eta,g_x}$ is a contraction map uniformly in $\eta$ when $T-t$ is sufficiently small.

Let $\Gamma$ be the set of $t \in [0,T]$ such that the following statement holds; for any $\eta \in \Ltwo_{\F_t}$, there exist $\ha^{t,T,\eta} \in \H^{2}([t,T];\R)$ satisfying
$$  \Phi^{t,T,\eta,g_x}(\ha^{t,T,\eta}) = \ha^{t,T,\eta} $$
By Lemma \ref{phi3} above, $T-\gamma \in \Gamma$. If $0 \in \Gamma$, then we have completed the proof. Suppose not, let $t_0 = \inf \Gamma$ ($t_0$ can still be zero),  $\gamma_0 > 0$ be sufficiently small so that $t_0+\gamma_0 < T-\frac{\gamma}{2} $, and let $\tau \in [t_0,t_0+\gamma_0) \cap \Gamma$. From the fact that $\tau \in \Gamma$, for any initial $\eta \in \Ltwo_{\F_\tau}$, there exist a fixed point $(\ha^{\tau,\eta}_t)_{\tau \leq t \leq T} \in \H^2([\tau,T];\R)$ of the map $\Phi^{\tau,T,\eta,g_x}$. Let $(\hX^{\tau,\eta}_t)_{\tau \leq t \leq T}$ denote the corresponding state process, i.e. for $t \in [\tau,T]$,
\begin{equation}\label{refProcess}
	 \hX_t^{\tau,\eta} = \eta + \int_\tau^t\ha^{\tau,\eta}_t dt + \sigma(W_t - W_\tau) + \tsg (\tW_t - \tW_\tau)
\end{equation}
Consider the following FBSDE
\begin{gather}
dX_{t} = -Y_{t}dt + \sigma dW_{t} + \tsg \tdW_{t}   \nonumber \\
dY_{t} = Z_{t}dW_{t} +  \tZ_{t}\tdW_{t} \label{fbsde1}\\
X_{\tau}=x,\quad Y_{T} = g_{x}(X_{T},\Law(\hX^{\tau,\eta}_T|\tF_T)) \nonumber
\end{gather}
By Theorem \ref{EUexample}, the FBSDE (\ref{fbsde1}) above is uniquely solvable and we denote the solution by $(X_t^{\tau,x,\eta},Y_t^{\tau,x,\eta},Z_t^{\tau,x,\eta},\tZ^{\tau,x,\eta}_t)_{\tau \leq t \leq T}$. Let $u: \R \times \Ltwo_{\F_\tau} \times \Omega \to \R$ be defined as $u(x,\eta,\omega) = Y_\tau^{\tau,x,\eta}(\omega)$, then we have the following estimates whose proofs are given in the next section.

\begin{lemma}\label{decoupling} $u$ defined above satisfies, \del{for} $\mb{P}$-a.s.,
\begin{gather}
	 (u(x,\xi, \omega)-u(x',\xi,\omega))(x-x') \geq 0  \label{bddux} \\
	 | u(x, \xi,\omega )-u(x',\xi',\omega) |^2  \leq C_u \l[ |x-x'|^2 + \mb{E}\l[(\xi-\xi')^2 \Big| \tF_\tau \r](\omega) \r]  \label{bddum}
\end{gather}
for all $x,x' \in \R, \xi,\xi' \in \Ltwo_{\F_\tau}$ with the constant $C_u$ depending only on $T, C_g, \gamma$.
\end{lemma}

Next, we attempt to extend the solution further. Let $s \in [0,\tau)$ to be determined, $\eta \in \Ltwo_{\F_s}$ and consider the map $\Phi^{s,\tau,\eta,u}$ as defined above. We have the following lemma which enables us to extend the solution beyond $t_0$ creating a contradiction.

\begin{lemma}\label{phi2} Suppose $u: \R \times \Ltwo_{\F_\tau} \times \Omega \to \R$ satisfies (\ref{bddux}) and (\ref{bddum}), then there exist $\gamma' > 0$ depending only on $C_u$ such that for any non-negative $s \in [\tau-\gamma',\tau)$, the following holds: For any $\eta \in \Ltwo_{\F_s}$, there exist $\ha^{s,\tau,\eta} \in \H^{2}([s,\tau];\R)$ satisfying
$$ \Phi^{s,\tau,\eta,u}(\ha^{s,\tau,\eta}) = \ha^{s,\tau,\eta} $$
\end{lemma}

Note that this lemma implies Lemma \ref{phi3} above by setting $u(x,\xi) = g_x(x,\Law(\xi|\tF_T))$. Assumption \ref{a1}-\ref{a4} implies that $g_x$ satisfies (\ref{bddux}) and (\ref{bddum}). The proof of this lemma is given in the next section. Next, we let $\gamma'$ be a constant from Lemma \ref{phi2} and $s$ be a non-negative element in $[\tau-\gamma',\tau)$. We construct a following control $\ha^{s,T,\eta}$ by letting
$$ \ha^{s,T,\eta} = \begin{cases} \ha^{s,\tau,\eta}, &\text{if }s\leq t < \tau \\  \ha^{\tau,T,\hX_\tau}, &\text{if }\tau \leq t \leq T \end{cases} $$
By definition of $u$, it follows that $ \ha^{s,T,\eta}$ satisfies
$$ \Phi^{s,T,\eta,g_x}(\ha^{s,T,\eta}) = \ha^{s,T,\eta} $$
We are left to check that $\ha^{s,T,\eta}$ is in $\H^{2}([s,T];\R)$. To do so, we need the following estimate
\begin{lemma}\label{alpha_estimate}
Suppose $(\hX_t,\hY_t,\hZ_t,\htZ_t)_{\tau \leq t \leq T} \in (\H^2([\tau,T];\R))^4$ satisfies the FBSDE
\begin{gather*}
	d\hX_{t} = -\hY_{t}dt + \sg dW_{t} +\tsg \tdW_t					 \\
	d\hY_{t} = \hZ_{t}dW_{t} + \htZ_{t}\tdW_{t}			 \\
	\hX_{\tau} = \xi, \quad \hY_{T} = g_x(\hX_{T},\Law(\hX_{T}| \tF_T))
\end{gather*}
where $\xi \in \Ltwo_{\F_\tau}$, then the following estimate holds:
\begin{equation}\label{fbsde_full_est}
 \mb{E}\l[ \sup_{\tau \leq t \leq T} [ |X_t|^2 + |Y_t|^2 ] \r] \leq C_{T,C_g}(\mb{E}[\xi^2] +g^2_x(0,\delta_0)+\sigma^2 + \tsg^2)
 \end{equation}
\end{lemma}

Let $\hX = (\hX_t)_{s \leq t \leq T}$ denote the state process corresponding to the control $\ha^{s,T,\eta}$. Then by using estimate (\ref{fbsde_full_est}), we get
\begin{align*}
\mb{E} \l[ \int_s^T( \ha^{s,T,\eta})^2 dt \r]  &=  \mb{E} \l[ \int_s^\tau( \ha^{s,\tau,\eta})^2 dt  \r]+ \mb{E} \l[\int_\tau^T (\ha^{\tau,T,\hX_\tau})^2dt  \r]  \\
& \leq   \mb{E} \l[ \int_s^\tau( \ha^{s,\tau,\eta})^2 dt  \r] + C_{T,C_g} \l[ \mb{E}[\hX^2_\tau]  + g^2_x(0,\delta_0) + \sigma^2 + \tsg^2 \r] \\
&\leq  \tilde{C}_{T,C_g} \l( \mb{E} \l[ \int_s^\tau(\ha^{s,\tau,\eta})^2dt \r] + \mb{E}[\eta^2] + g^2_x(0,\delta_0) + \sigma^2 + \tsg^2 \r) < \infty
\end{align*}
which implies $\ha^{s,T,\eta} \in \H^{2}([s,T];\R)$.  The proof of Lemma \ref{alpha_estimate} is presented in the next section.

We have shown that $s \in \Gamma$. From Lemma \ref{phi2}, we know that $\gamma'$ depends only on $C_u$ which is independent of $\tau$. Therefore, we can select $\gamma_0$ sufficiently small so that $\gamma_0 <\gamma' $, so that $\tau - \gamma' \leq t_0+\gamma_0-\gamma' < t_0$. Thus, we can select $s$ to be strictly less than $t_0$ or $s=0$ creating a contradiction as we assumed $0 \notin \Gamma$ and $t_0 = \inf \Gamma$. Therefore, $0 \in \Gamma$ and we have completed the proof.

\end{proof}

\section{Main Lemma}\label{lemma}

In this section, we prove all the lemmas that was used in Theorem \ref{main1}. The first one is a priori estimate of the so-called ``decoupling field" while the second lemma is a construction of $\tsg$-MFG solution using Banach fixed point theorem over a small time duration. The third lemma give an FBSDE estimate needed to ensure that the extended control remains admissible.

\subsection{Proof of Lemma \ref{decoupling}}

Let $x_{1},x_{2} \in \R$ and $(X^{i}_{t},Y^{i}_{t},Z^{i}_{t},\tZ^{i}_{t})_{\tau \leq t \leq T}$ denote the solution to the FBSDE (\ref{fbsde1}) with initial condition $X^{i}_{\tau} = x_{i}, i=1,2$. Let $\Delta Y_{t} = Y^{1}_{t}-Y^{2}_{t}$ and $\Delta X_{t} = X^{1}_{t}-X^{2}_{t}$, then by applying \ito's lemma to $\Delta Y_t \Delta X_t$ from $\tau$ to $T$ and taking expectation conditional on $\F_\tau$ (denote by $\mb{E}_\tau[\cdot])$, we get
$$ \mb{E}_\tau[\Delta Y_T \Delta X_T] - \Delta Y_\tau \Delta X_\tau = - \mb{E}_{\tau}\l[ \int_{\tau}^{T}\Delta Y_{t}^{2} dt \r] $$
By convexity assumption \ref{a2}, it follows that
$$ \Delta Y_T \Delta X_T = \l(g_{x}(X^{1}_{T},\Law(\hX^{\tau,\eta}_T| \tF_T))-g_{x}(X^{2}_{T},\Law(\hX^{\tau,\eta}_T| \tF_T))\r)\Delta X_{t} \geq 0$$
Thus,
 $$ \Delta Y_{\tau} \Delta X_{\tau} = \mb{E}_{\tau}\l[\Delta Y_T \Delta X_T \r] +  \mb{E}_{\tau}\l[ \int_{\tau}^{T}\Delta Y_{t}^{2} dt \r]  \geq 0  $$
 That is,
 $$ (u(x_{1},\eta)-u(x_{2},\eta))(x_{1}-x_{2}) \geq 0$$

Now we proceed to show (\ref{bddum}). Let $\eta_1,\eta_2 \in \Ltwo_{\F_\tau}$ and we consider $u(x_1,\eta_1)$ and $u(x_2,\eta_2)$. For $i=1,2$, let  $(X^i_{t},Y^i_{t},Z^i_{t},\tZ^i_{t})_{\tau \leq t \leq T}$ denote the solution to the corresponding FBSDE (\ref{fbsde1}) from the definition of $u(x_i,\eta_i)$. In other words, they satisfy
\begin{gather}
	dX^i_{t} = -Y^i_{t}dt + \sg dW_{t} +\tsg \tdW_t	\nonumber				 \\
	dY^i_{t} = Z^i_{t}dW_{t} + \tZ^i_{t}\tdW_{t}	\label{fbsdeInd}		 \\
	X^i_{\tau} = x_i, Y^i_{T} = g_{x}(X^i_{T},\Law(\hX^{\tau,\eta^i}_T|\tF_T))  \nonumber
\end{gather}
where $(\hX_t^{\tau,\eta^i})_{\tau \leq t \leq T}$ is given by
$$ \hX_t^{\tau,\eta} = \eta + \int_\tau^t\ha^{\tau,\eta}_t dt + \sigma(W_t - W_\tau) + \tsg (\tW_t - \tW_\tau), $$
and $(\ha^{\tau,\eta_i}_t)_{\tau \leq t \leq T}$ is the $\tsg$-MFG solution over $[\tau,T]$ with initial $\eta_i$, i.e. the unique fixed point of the map $\Phi^{\tau,T,\eta^i,g_x}$. For notational convenience, we write $\hX^{\tau,\eta^i}_t$ as $\hX^i_t$. We begin by getting a bound on $\hX^1_t-\hX^2_t$ before we go back to bound $u(x_1,\eta_1) - u(x_2,\eta_2)$. From the definition of $\Phi^{\tau,T,\eta^i,g_x}$ and the fact that $(\ha^{\tau,\eta_i}_t)_{\tau \leq t \leq T}$ is the unique fixed point of this map, it follows that $(\hX^i_t)_{\tau \leq t \leq T}$ is the forward process of the unique solution of FBSDE
\begin{gather*}
	d\hX^i_{t} = -\hY^i_{t}dt + \sg dW_{t} +\tsg \tdW_t					 \\
	d\hY^i_{t} = \hZ^i_{t}dW_{t} + \htZ^i_{t}\tdW_{t}			 \\
	\hX^i_{\tau} = \eta^i, \hY^i_{T} = g_{x}(\hX^i_{T},\Law(\hX^i_T|\tF_T))
\end{gather*}
Let $\Delta \hX_{t} = \hX^1_{t}-\hX^2_{t}$ and define $\Delta \hY_{t}, \Delta \hZ_{t}, \Delta \hat{\tZ}_{t}, \Delta X_t, \Delta Y_t, \Delta Z_t, \Delta \tZ_t, \Delta x, \Delta \eta $ similarly. Then note that $(\Delta \hX_{t},\Delta \hY_{t}, \Delta \hZ_t, \Delta \htZ_t)_{\tau \leq t \leq T}$ satisfies
\begin{gather}
 d\Delta \hX_{t} = - \Delta \hY_{t} dt \nonumber \\
 d\Delta \hY_{t} = \Delta \hZ_{t} dW_{t} + \Delta \htZ_{t} \tdW_{t} \label{fbsdeDelta} \\
 \Delta \hX_{\tau} = \Delta \eta, \quad \Delta \hY_{T} = g_{x}(\hX^1_{T},\Law(\hX^1_T|\tF_T)) - g_{x}(\hX^2_{T},\Law(\hX^2_T|\tF_T)), \nonumber
 \end{gather}
so we get by \ito's lemma that
$$ d(\Delta \hY_{t}\Delta \hX_{t}) = - (\Delta \hY_{t})^2 dt + \Delta \hX_{t} d\Delta \hY_{t} $$
Taking integral from $\tau$ to $T$ and taking expectation conditional on $\tF_\tau$ (where $\tmb{E}_\tau[\cdot] := \mb{E}[\cdot | \tF_\tau]$), we have
\begin{align*}
\int_{\tau}^{T} \tmb{E}_{\tau}[\Delta \hY^{2}_{t}] dt	&\leq  \tmb{E}_\tau[\Delta \hX_\tau \Delta \hY_\tau] - \tmb{E}_{\tau} (\Delta \hY_{T}\Delta \hX_{T})  \\
&=  \tmb{E}_\tau[\Delta \hX_\tau \Delta \hY_\tau]- \tmb{E}_{\tau} ((g_{x}(\hX^1_{T},\Law(\hX^1_T|\tF_T))-g_{x}(\hX^2_{T},\Law(\hX^2_T|\tF_T)))\Delta \hX_{T})
\end{align*}
Using \ref{a4}, we get
$$  \tmb{E}_{\tau} \l[ (g_{x}(\hX^1_{T},\Law(\hX^1_T|\tF_T))-g_{x}(\hX^2_{T},\Law(\hX^2_T|\tF_T)))\Delta \hX_{T}\r] \geq 0 $$
so that, by Young's inequality,
\begin{align}
\int_{\tau}^{T} \tmb{E}_{\tau}[\Delta \hY^{2}_{t}] dt	&\leq  \tmb{E}[\Delta \hX_\tau \Delta \hY_\tau] \nonumber\\
& \leq \frac{1}{4\eps} \tmb{E}[\Delta \eta^2] + \eps \tmb{E}[\Delta \hY_\tau^2]  \label{b1}

\end{align}
for any $\eps > 0$. \del{Applying \ito's  lemma to $(\Delta \hY_t)^2$ yields,}
\dell{$$ \tmb{E}_\tau[\Delta \hY_t^2] = \tmb{E}_\tau[\Delta \hY_\tau^2] +\int_\tau^t \tmb{E}_\tau[ \Delta \hZ_t^2 + \Delta \htZ_t^2] dt  \geq  \tmb{E}_\tau[\Delta \hY_\tau^2]$$}
\add{Since $\Delta \hY_t$ is a martingale, it follows that $ \tmb{E}_\tau[\Delta \hY_\tau^2] \leq \tmb{E}_\tau[\Delta \hY_t^2] $  }for all $t \in [\tau,T]$. Thus, together with the fact that $\tau \leq T-\frac{\gamma}{2}$, we have
\begin{equation}\label{bY}
\tmb{E}_\tau[\Delta \hY_\tau^2] \leq \frac{1}{T-\tau}\int_\tau^T \tmb{E}_\tau[\Delta \hY_t^2] dt \leq \frac{2}{\gamma}\int_\tau^T \tmb{E}_\tau[\Delta \hY_t^2] dt
\end{equation}
Similarly, we have
\begin{equation}\label{bYY}
\tmb{E}_\tau[\Delta Y_\tau^2] \leq \frac{1}{T-\tau}\int_\tau^T \tmb{E}_\tau[\Delta Y_t^2] dt \leq \frac{2}{\gamma}\int_\tau^T \tmb{E}_\tau[\Delta Y_t^2] dt
\end{equation}
\add{The inequality \eqref{bYY} will be used later in the proof. Next, }going back to (\ref{b1}) and use (\ref{bY}), it follows that
$$ \int_{\tau}^{T} \tmb{E}_{\tau}[\Delta \hY^{2}_{t}] dt \leq \frac{1}{4\eps}\tmb{E}_\tau[\Delta \eta^2] + \frac{2\eps}{\gamma} \int_{\tau}^{T} \tmb{E}_{\tau}[\Delta \hY^{2}_{t}] dt $$
Therefore, for sufficiently small $\eps$, we have
$$ \int_{\tau}^{T} \tmb{E}_{\tau}[\Delta \hY^{2}_{t}] dt \leq C_{\eps,\gamma}\tmb{E}_\tau[ \Delta \eta^2] $$
Thus, by (\ref{fbsdeDelta}),
\begin{equation}\label{boundRef}
	\tmb{E}_\tau(\Delta \hX_T)^2 =  \tmb{E}_\tau\l( \Delta \eta - \int_\tau^T \hY_t dt \r)^2 \leq C'_{\eps,\gamma} \tmb{E}_\tau[\Delta \eta]^2
\end{equation}
Now we go back to showing (\ref{bddum}). Note that $(\Delta X_{t},\Delta Y_{t}, \Delta Z_t, \Delta \tZ_t)_{\tau \leq t \leq T}$ satisfies
\begin{gather*}
 d\Delta X_{t} = - \Delta Y_{t} dt  \\
 d\Delta Y_{t} = \Delta Z_{t} dW_{t} + \Delta \tZ_{t} \tdW_{t} \\
 \Delta X_{\tau} = \Delta x, \quad \Delta Y_{T} = g_{x}(X^1_{T},\Law(\hX^1_{T}|\tF_T)) - g_{x}(X^2_{T},\Law(\hX^2_T|\tF_T))
 \end{gather*}
so we have
\begin{equation}\label{bX}
  \tmb{E}_\tau(\Delta X_T)^2 =  \tmb{E}_\tau\l(\Delta x - \int_\tau^T Y_t dt \r)^2 \leq 2(\Delta x)^2 +  2T \int_\tau^T \mb{E}(\Delta Y_s)^2 ds,
 \end{equation}
 then following the same sequence of inequalities as we did earlier,
\begin{align*}
 \int_{\tau}^{T}  \tmb{E}_\tau[\Delta Y^{2}_{t}] dt &=   \tmb{E}_\tau(\Delta X_\tau \Delta Y)-  \tmb{E}_\tau \l[ (g_{x}(X^1_{T},\Law(\hX^1_T|\tF_T))-g_{x}(X^2_{T},\Law(\hX^2_T|\tF_T)))\Delta X_{T}\r] \\
&=  \tmb{E}_\tau(\Delta X_\tau \Delta Y_\tau) -  \tmb{E}_\tau \l[ (g_{x}(X^1_{T},\Law(\hX^1_T|\tF_T))-g_{x}(X^2_{T},\Law(\hX^1_T|\tF_T))\Delta X_T\r] \\
& \qquad +\tmb{E}_\tau\l[ g_{x}(X^2_{T},\Law(\hX^2_T|\tF_T))-g_{x}(X^2_{T},\Law(\hX^1_T|\tF_T)))\Delta X_{T}) \r]
\end{align*}
By convexity assumption \ref{a2},
$$ \tmb{E}_\tau \l[ (g_{x}(X^1_{T},\Law(\hX^1_T|\tF_T))-g_{x}(X^2_{T},\Law(\hX^1_T|\tF_T)))\Delta X_T\r]  \geq 0 $$
and by Lipschitz continuity (in $m$) assumption \ref{a3},
$$ \tmb{E}_\tau\l[ g_{x}(X^2_{T},\Law(\hX^2_T|\tF_T))-g_{x}(X^2_{T},\Law(\hX^1_T|\tF_T)))\Delta X_{T}) \r]
 \leq C_g \tmb{E}_\tau \l((\tmb{E}_T[\Delta \hX_T^2 ])^{\frac{1}{2}}\Delta X_{T}\r) $$
 where $\tmb{E}_T[\cdot] := \mb{E}[\cdot | \tF_T]$.
Thus,
\begin{align*}
\int_{\tau}^{T}  \tmb{E}_\tau[\Delta Y^{2}_{t}] dt
&\leq   \tmb{E}_\tau(\Delta X_\tau \Delta Y_\tau) +C_g  \tmb{E}_\tau ((\tmb{E}_T[\Delta \hX_T^2])^{\frac{1}{2}}\Delta X_{T}) \\
&\leq C_{\eps,C_g}(\Delta x^2 + \tmb{E}_\tau[\Delta \hX_T^2]) + \eps\l(  \tmb{E}_\tau[\Delta Y_\tau^2]+  \tmb{E}_\tau[\Delta X_T^2] \r)
\end{align*}
From  (\ref{bYY}), (\ref{boundRef}), and (\ref{bX}), it follows that
\begin{align*}
\int_{\tau}^{T}  \tmb{E}_\tau[\Delta Y^{2}_{t}] dt
&\leq C'_{\eps,C_g}(\Delta x^2 + \mb{E}[\Delta \hX_T^2]) + \eps\l(  \tmb{E}_\tau[\Delta Y_\tau^2]+ 2T\int_\tau^T  \tmb{E}_\tau[\Delta Y_s^2] ds \r) \\
&\leq C'_{\eps,\gamma}(\Delta x^2 + \tmb{E}_\tau[\Delta \eta ^2]) + \eps \l(\frac{2}{\gamma}+2T \r)\int_\tau^T  \tmb{E}_\tau[\Delta Y_s^2] ds
\end{align*}
Thus, by selecting $\eps$ sufficiently small, we get
$$  \int_\tau^T  \tmb{E}_\tau[\Delta Y_s^2] ds \leq C_{\gamma,T,C_g}(\Delta x^2 + \tmb{E}_\tau[ \Delta \eta ^2]) $$
Therefore, using (\ref{bYY}) again,
$$  \tmb{E}_\tau[\Delta Y_\tau^2]  \leq \frac{2}{\gamma} \int_\tau^T  \tmb{E}_\tau[\Delta Y_s]^2 ds \leq  \tilde{C}_{\gamma,T,C_g}(\Delta x^2 + \tmb{E}_\tau[\Delta \eta ]^2) $$
Observe that all the coefficients in the FBSDE (\ref{fbsdeInd}) are $\tF_t$-progressively measurable, therefore, $Y_\tau$ is $\tF_\tau$-measurable. Hence,
$$ \Delta Y_\tau^2 =  \tmb{E}_\tau[\Delta Y_\tau^2]  \leq   \tilde{C}_{\gamma,T,C_g}(\Delta x^2 + \tmb{E}_\tau[\Delta \eta ]^2)  $$
or equivalently,
$$ (u(x_1,\eta_1)-u(x_1,\eta_2))^2 \leq \tilde{C}_{\gamma,T,C_g}((x_1-x_2)^2 + \mb{E}[ (\eta_1-\eta_2)^2 | \tF_\tau] ) $$
as desired.

\subsection{Proof of Lemma \ref{phi2}} \label{fix}

 Let $\ha^1,\ha^2 \in \H^2([s,\tau];\R)$, $(X^i_t,Y^i_t,Z^i_t,\tZ^i_t)_{s \leq t \leq \tau}$ denote the solution of corresponding FBSDE (\ref{fbsde_phi}) from the definition of $\Phi^{s,\tau,\eta,u}(\ha^i)$, $(\hX_t^i)_{s \leq t \leq \tau}$ denote the state process corresponding to $(\ha^i_t)_{s \leq t \leq \tau}$ with initial $\eta \in \Ltwo_{\F_s}$ as defined by (\ref{stateProcess}). Let $\Delta X_{t} = X^1_{t}-X^2_{t}$ and define $\Delta Y_t, \Delta Z_t, \Delta \tZ_t, \Delta \ha_t, \Delta \hX_t$ similarly. Note that $(\Delta X_{t},\Delta Y_{t}, \Delta Z_t, \Delta \tZ_t)_{s \leq t \leq \tau}$ satisfies
\begin{gather*}
 d\Delta X_{t} = - \Delta Y_{t} dt  \\
 d\Delta Y_{t} = \Delta Z_{t} dW_{t} + \Delta \tZ_{t} \tdW_{t} \\
 \Delta X_{s} = 0, \quad \Delta Y_{\tau} = u(X^1_{\tau},\hX^1_{\tau}) - u(X^2_{\tau},\hX^2_\tau)
 \end{gather*}
 \del{By applying \ito's lemma to $\Delta Y_t^2$, we get}
 \dell{$$ \mb{E}[\Delta Y_t^2] = \mb{E}[\Delta Y_\tau^2] -\int_t^\tau \mb{E}[ \Delta Z_t^2 + \Delta \tZ_t^2] dt  \leq  \mb{E}[\Delta Y_\tau^2]$$}
\add{Since $\Delta Y_t$ is a martingale, it follows that $ \mb{E}[\Delta Y_t^2] \leq \mb{E}[\Delta Y_\tau^2]$ for all $t \in [s,\tau]$ and} thus,
\begin{equation}\label{bdx}
 \mb{E}[\Delta X_\tau^2] = \mb{E}\l[ \l( \int_s^\tau \Delta Y_t dt \r)^2 \r]  \leq (\tau-s) \int_s^\tau \mb{E}[\Delta Y_t^2] dt \leq (\tau-s)^2 \mb{E}[\Delta Y_\tau^2]
 \end{equation}
Furthermore,
\begin{equation}\label{bdhx}
 \mb{E}[\Delta \hX_\tau]^2  = \mb{E}\l[ \l( \int_s^\tau \Delta \ha_t dt \r)^2 \r] \leq (\tau-s) \mb{E}\l( \int_s^\tau \Delta \ha_t^2 \r) dt
\end{equation}
Therefore, by (\ref{bddum}), (\ref{bdx}), and (\ref{bdhx}), we have
\begin{align*}
	\mb{E}[\Delta Y_\tau^2]  &= \mb{E}[ u(X^1_{\tau},\hX^1_\tau) - u(X^2_{\tau},\hX^2_\tau) ] \\
						&\leq C_u\l( \mb{E}[\Delta X_\tau^2] + \mb{E}[\mb{E}[ \Delta \hX_\tau^2 | \tF_\tau] ] \r) \\
						&\leq  C_u \l[  (\tau-s)^2\mb{E}[\Delta Y_\tau^2] + (\tau-s)\mb{E}\l( \int_s^\tau (\Delta \ha_t)^2 dt \r)  \r]
\end{align*}
Hence, for $\tau-s$ sufficiently small such that $C_u(\tau-s)^2 < 1$, we get
$$ \mb{E}[\Delta Y_\tau^2] \leq \frac{C_u(\tau-s)}{1-C_u(\tau-s)^2}\mb{E}\l( \int_s^\tau (\Delta \ha_t)^2 dt \r) =\frac{C_u(\tau-s)}{1-C_u(\tau-s)^2} \| \Delta \ha \|^2_{\H^2([s,\tau];\R)} $$
and it follows that
$$ \| \Phi(\ha^1)-\Phi(\ha^2) \|^2_{\H^2([s,\tau];\R)} =  \int_s^\tau \mb{E}[\Delta Y_t^2] dt  \leq (\tau-s)\mb{E}[\Delta Y_\tau^2] \leq  \frac{C_u(\tau-s)^2}{1-C_u(\tau-s)^2} \| \ha^1-\ha^2 \|^2_{\H^2([s,\tau];\R)} $$
As a result, we get a contraction map for sufficiently small $\tau-s$ depending only on $C_u$ as desired.

\subsection{Proof of Lemma \ref{alpha_estimate}}

 Applying \ito's lemma to $\hX_t\hY_t$ from $\tau$ to $T$ yields
$$ \mb{E}[\hX_T g_x(\hX_T,\Law(\hX_T|\tF_T))] - \mb{E}[\xi \hY_\tau] = - \int_\tau^T \mb{E}[\hY_t^2] dt + \int_\tau^T \mb{E}[ \sigma \hZ_t + \tsg \htZ_t] dt $$
From the weak monotonicity assumption \ref{a4}, we get
$$\mb{E}[\hX_T g_x(\hX_T,\Law(\hX_T|\tF_T))]  \geq \mb{E}[\hX_T g_x(0,\delta_0)] $$
Thus,
\begin{align*}
\int_\tau^T \mb{E}[\hY_t^2] dt & \leq \mb{E}[\xi \hY_\tau] - \mb{E}[ \hX_T g_x(0,\delta_0) ] +  \int_\tau^T \mb{E}[ \sigma \hZ_t + \tsg \htZ_t] dt \\
	&\leq C_{\eps,T} \l[  \mb{E}[\xi^2] + g^2_x(0,\delta_0) + \sigma^2 + \tsg^2 \r] + \eps \mb{E}\l[\hX_T^2 + \hY_\tau^2 + \int_\tau^T [\hZ_r^2 +  \htZ_r^2]dr \r]
\end{align*}
Applying \ito's lemma to $\hY_t^2$ from $t$ to $T$ together with the Lipschitz assumption \ref{a1} and \ref{a3} give, for all $t \in [\tau,T]$,
\begin{equation}\label{bound_y2}
\mb{E}[\hY_t^2] + \int_t^T \mb{E}[  \hZ_r^2 +  \htZ_r^2]dr \leq \mb{E}[\hY_T^2] = \mb{E}[g^2_x(\hX_T,\Law(\hX_T|\tF_T))] \leq C_g(g^2_x(0,\delta_0) + \mb{E}[\hX_T^2])
\end{equation}
Thus, we get a bound of the form
$$ \int_\tau^T \mb{E}[\hY_t^2] dt  \leq C_{\eps,T,C_g}(\mb{E}[\xi^2] + g^2_x(0,\delta_0) + \sigma^2+\tsg^2) + \eps\mb{E}[\hX_T^2] $$
Note that by Doob's Martingale inequality, we also have
$$ \mb{E}[\sup_{\tau\leq t \leq T} |\hX_t|^2 ] \leq C_T\l( \int_\tau^T \mb{E}[\hY_t^2] dt  + \sigma^2 + \tsg^2 \r) $$
Combining with the previous bound, we can select $\eps$ sufficiently small depending only on $T,C_g$ to get
\begin{equation}\label{bound_x}
  \mb{E}[\sup_{\tau\leq t \leq T} |\hX_t|^2 ] \leq C_{T,C_g}(\mb{E}[\xi^2] + g^2_x(0,\delta_0) + \sigma^2+\tsg^2)
  \end{equation}
Applying Doob's Martingale inequality to $Y_t$ and use (\ref{bound_y2}) and (\ref{bound_x}), we then complete the proof.

\section{Summary and Conclusions}\label{summary}

	The aim of this paper is to establish an existence and uniqueness result for a Mean Field Game in the presence of common noise. We assume a linear-convex control problem with the quadratic running cost depending only on the control and a general convex and Lipschitz terminal cost function. In addition, we assume that the terminal cost also satisfies what we call a weak monotonicity condition (see (\ref{monotone})).

	For the existence result, our assumptions are similar to those used in \cite{Carmona1} for a $0$-MFG problem except that we replace the weak mean-reverting assumption (\ref{weakMR}) with the weak monotonicity condition (\ref{monotone}). Our existence proof is also different from those of a $0$-MFG problem which rely on the Schauder fixed point theorem. Instead, we apply the Banach fixed point theorem to given existence of a solution over a small time duration and show that it can be extended to an arbitrary time duration. For the uniqueness part, under the convexity assumption on the cost functions, our result extends those of a $0$-MFG problem as our weak monotonicity condition is weaker than the monotonicity condition used in \cite{cardaliaguet2010,Carmona1}.

	Although we assume a simple state process and running cost, our result is expected to hold for a more general setting, namely a model with a linear state process
	$$ dX_t = (A\alpha_t + BX_t + C\bar{m}_t) dt + \sigma dW_t + \tsg d\tW_t$$
and a running cost of the form
$$ f(t,x,\alpha,m) = f_0(t,x,\alpha)+f_1(t,x,m) $$
where $f_0$ is Lipschitz and convex in $(x,\alpha)$ and strongly convex in $\alpha$, $f_1$ is Lipschitz in $(x,m)$ and satisfies the weak monotonicity condition.

\bibliographystyle{abbrv}
\bibliography{../MFG}

\end{document}

config: arxiv


TITLE: Why do you need to show A(1) before proving A(n) by induction?
QUESTION [0 upvotes]: My instructor stated that in order to have a valid proof by mathematical induction, you first have to show A(1) holds, and then assume A(n) to deduce A(n+2). Why is the first step necessary if we are going to assume A(n) though?
I get that showing A(1) is true suggests that A(n) might be, but that could very easily not be the case. Perhaps A(3) does not hold. So why logical benefit do we gain by proving A(1) before completing a more general proof by induction?

REPLY [0 votes]: The reason proof by induction works is because of the well-ordering principle (WOP) of the natural numbers. The well-ordering principle says any nonempty subset of the natural numbers has a least element. It turns out that WOP is logically equvalent to the principle of mathematical induction (PMI). This is fairly straightforward to prove as follows:
$WOP\leftarrow PMI$ Suppose $S$ has no minimal element. Then $ n = 1 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 2 \notin S$, because then $2$ would be minimal, since $n = 1$ is not in $S$. Suppose none of $1, 2, \cdots, n$ is in $S$. Then $n+1 \notin S$, because otherwise it would be minimal. Then by induction $S%$ is empty, a contradiction.
$WOP\leftarrow PMI$ Suppose $P(1)$ is true, and $P(n+1)$ is true whenever $P(n)$ is true. If $P(k)$ is not true for all integers, then let $S$ be the non-empty set of $k$ for which $P(k)$ is not true. By well-ordering $S$ has a least element, which cannot be $k = 1$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.
So clearly WOP is true iff PMI is true. A lot of teachers don't like going through this in basic rigorous mathematics courses, which to me is a big mistake. Students need to understand why induction works,it's a critical method of proof.
How's that?


TITLE: Matrix Groups and the Upper Half Plane
QUESTION [0 upvotes]: Why is it that the upper half plane $\mathbb{H}$ can be thought of as equivalent to $SL_{2}(\mathbb{R})/SO(2)$?

REPLY [4 votes]: If $S$ is a set on which a group $G$ acts transitively, then as a $G$-set, $S$ can be identified with $G/\text{Stab}(s)$ for any $s \in S$. This follows from the fact that there is an obvious morphism of $G$-sets
$$G \ni g \mapsto gs \in S$$
which factors through a morphism $G/\text{Stab}(s) \to S$, and by the definition of the stabilizer and transitivity this is an isomorphism.
Now $\text{SL}_2(\mathbb{R})$ naturally acts transitively on $\mathbb{H}$ by hyperbolic isometries. I claim that $\text{Stab}(i) = \text{SO}(2)$ (regarded as a subgroup of $\text{SL}_2(\mathbb{R})$ in the usual way). To see this, write
$$\frac{ai + b}{ci + d} = i \Leftrightarrow ai + b = di - c$$
where $z \mapsto \frac{az + b}{cz + d} \in \text{PSL}_2(\mathbb{R})$. Since $ad - bc = 1, a = d, b = -c$, it follows that $a^2 + b^2 = 1$, so we can write
$$a = \cos \theta, b = \sin \theta$$
for some $\theta$, and then $d = \cos \theta, c = - \sin \theta$; precisely a rotation matrix. Conversely, any such element of $\text{SL}_2(\mathbb{R})$ fixes $i$. So $\mathbb{H}$ can be identified with $\text{SL}_2(\mathbb{R})/\text{SO}(2)$ as a $\text{SL}_2(\mathbb{R})$-space as desired.

REPLY [1 votes]: Each member of $SL(2,\mathbb R)/SO(2,\mathbb R)$ is an equivalence class of linear mappings modulo rotations. Choose for each equivalence class the unique member $f$ such that $f(1,0)$ lies on the positive $x$ axis and $f(0,1)$ lies in the upper half plane. Because the determinant must be $1$, knowing the coordinates of $f(0,1)$ allows you to determine the length of $f(1,0)$.
By the way, $SO(2)$ is not normal in $SL(2)$, as far as I can figure out, so I'm not sure how meaningful this construction is. It's not as it it will give you a group structure on the upper half-plane, for example. If you're taking left cosets instead of right ones, you probably need to work with the inverse maps to establish the equivalence.


text:
\section{Stability of LS-CS (CS on LS residual)}
\label{addLSdel_lscs}
LS-CS uses partial knowledge of support in a different way than modified-CS. It first computes an initial LS estimate using the known part of the support, $T$, and then computes the LS observation residual. CS is applied on the residual instead of applying it to the observation. Add-LS-del is used for support estimation.

We summarize the algorithm in Algorithm \ref{lscsalgo_2}.

\begin{algorithm}[h!]
\caption{{\bf \small LS-CS with Add-LS-Del}}

For $t\ge 0$, do
\ben
\item {\em Simple CS. } Do as in Algorithm \ref{modcsalgo_2}.

\item {\em CS-residual. }
\ben
\item Use $T:=\Nhat_{t-1}$ to compute the initial LS estimate, $\xhat_{t,\text{init}}$, and the LS residual, $\tty$, using
\label{initls}
\bea
(\xhat_{t,\text{init}})_{T} \se {A_{T}}^\dag y_t, \ \ (\xhat_{t,\text{init}})_{T^c} = 0 \nn \\
\tty \se  y_t - A \xhat_{t,\text{init}}
\label{deftty0}
\eea

\item Do CS on the LS residual, i.e.  solve
\bea
\min_\beta \|\beta\|_1 \ s.t. \ \| \tty - A \beta \| \le \eps
\label{simplecs}
\eea
and denote its output by $\betahat_t$. Compute
\bea
\xhat_{t,\CSres} : = \betahat_t + \xhat_{t,\text{init}}.
\label{xhatcsres}
\eea
\een

\item {\em Additions / LS.} Compute $T_\dett$ and LS estimate using it as in  Algorithm \ref{modcsalgo_2}. Use $\xhat_{t,\CSres}$ instead of $\xhat_{t,modcs}$.

\item {\em Deletions / LS.} Compute $\tT$ and LS estimate using it as in Algorithm \ref{modcsalgo_2}.

\item Set $\Nhat_t = \tT$. Output $\xhat_t$. Feedback $\Nhat_t$.

\een

\label{lscsalgo_2}
\end{algorithm}

The CS-residual step error can be bounded as follows. The proof follows in exactly the same way as that given in \cite{just_lscs} where CS is done using Dantzig selector instead of (\ref{simplecs}). We use (\ref{simplecs}) here to keep the comparison with modified-CS easier.

\begin{lemma}[CS-residual error bound \cite{just_lscs}]
If  $\|w\| \le \eps$, $\delta_{2|\Delta|} < (\sqrt{2}-1)/2$ and $\delta_{|T|} < 1/2$,
\bea
&& \|x - \xhat_{\CSres}\| \le C'(|T|,|\Delta|) \eps +  \theta_{|T|,|\Delta|} C''(|T|,|\Delta|) \|x_\Delta\| \nn \\
&& C'(|T|,|\Delta|)  \defn C_1(2|\Delta|) + \sqrt{2} C_2(2|\Delta|) \sqrt{\frac{|T|}{|\Delta|}} \nn \\
&& C''(|T|,|\Delta|) \defn 2 C_2(2|\Delta|) \sqrt{{|T|}}, \ \text{where} \nn \\
&& \text{$C_1(S)$ is defined in (\ref{defC1s}),~}  C_2(S) \defn 2\frac{1 + (\sqrt{2}-1) \delta_S}{1 - (\sqrt{2}+1) \delta_S}
\eea
\label{lscs_bnd}
\end{lemma}

\subsection{Stability result for LS-CS with Add-LS-Del}
The overall approach is similar to the one discussed in the previous section for modified-CS. The key difference is in the detection condition lemma, which we give below. Its proof is given in Appendix \ref{proof_detectcond_lscs}.

\begin{lemma}[Detection condition for LS-CS]
Assume that $\|w\| \le \eps$, $|T| \le S_T$ and $|\Delta| \le S_\Delta$.
Let $b:=\|x_\Delta\|_\infty$. For a $\gamma \le 1$, let $\Delta_1:=\{i \in \Delta: \gamma b \le |x_i| \le b \}$ and let $\Delta_2:= \Delta \setminus \Delta_1$. Assume that $|\Delta_1| \le S_{\Delta_1}$ and $\|x_{\Delta_2}\| \le \kappa b$. All $i \in \Delta_1$ will definitely get detected at the current time if $\delta_{2S_\Delta} < (\sqrt{2}-1)/2$, $\delta_{S_T} < 1/2$, $\theta_{S_T,S_\Delta} C''(S_T,S_\Delta) \le {\gamma}/{2(\sqrt{S_{\Delta_1}} + \kappa)}$, and
\bea

&& \max_{|\Delta| \le S_\Delta} \frac{ \alpha_{add} + C'(S_T,|\Delta|)\eps }{\gamma - {\theta_{S_T,|\Delta|}} C''(S_T,|\Delta|) (\sqrt{S_{\Delta_1}} + \kappa)} < b \ \  \nn
\label{detcond_lscs}
\eea
where $C'(.,.)$, $C''(.,.)$ are defined in Lemma \ref{lscs_bnd}.
\label{detectcond_lscs}
\end{lemma}

The stability result then follows in the same fashion as Theorem \ref{stabres_modcs}. The only difference is that instead of Lemma \ref{detectcond_modcs}, we apply Lemma \ref{detectcond_lscs} with $S_T=S_0, S_\Delta=2S_a$, $b=2r$, $\gamma=1$, $S_{\Delta_1}=S_a$ and $\kappa = (\sqrt{2S_a} r)/(2r) = \sqrt{S_a}/\sqrt{2}$.

\begin{theorem}[Stability of LS-CS]
Assume Signal Model \ref{sigmod2} and $\|w\| \le \eps$. If
\ben
\item  {\em (addition and deletion thresholds) }
\ben
\item $\alpha_{add}$ is large enough so that there are at most $S_a$ false additions per unit time,
\label{addthresh_lscs}

\item $\alpha_{del}  = \sqrt{2} \eps + 2 \sqrt{S_a} \theta_{S_0+2S_a,S_a} r $
\label{delthresh_lscs}
\een

\item {\em (support size, support change rate)} $S_0, S_a$ satisfy
\label{measmodel_lscs}
\ben
\item $\delta_{4S_a} < (\sqrt{2}-1)/2$
\label{measmodel_lscs_1a}
\item $\delta_{S_0+2S_a} < 1/2$
\label{measmodel_lscs_1b}

\item $\theta_{S_0,2S_a} C''(S_0,2S_a)   <  \frac{1}{(2+\sqrt{2})\sqrt{S_a}}$
\label{measmodel_lscs_2a}

\item $\theta_{S_0+2S_a,S_a} < \frac{1}{2} \sqrt{  \frac{1}{4S_a } }$
\label{measmodel_lscs_2b}

\een

\item {\em  (new element increase rate) } $ r \ge \max(\tilde{G}_1,\tilde{G}_2)$, where
\label{add_del_lscs}
\bea
&& \tilde{G}_1 \defn
 \max_{|\Delta| \le 2S_a}
 [\frac{ \alpha_{add} + C'(S_0,|\Delta|)\eps  }{2 -  (2+\sqrt{2}) {\theta_{S_0,|\Delta|}} \sqrt{S_a} C''(S_0,|\Delta|)}] \nn \\

&& \tilde{G}_2 \defn \frac{\sqrt{2} \eps}{1 - \theta_{S_0+2S_a,S_a}\sqrt{4S_a }}
\eea

\item {\em (initialization) }  (same condition as in Theorem \ref{stabres_modcs})
\een
then, all conclusions of Theorem \ref{stabres_modcs} hold for LS-CS, except the last one, which is replaced by $\|x_t - \xhat_{t,\CSres}\| \le \max_{|\Delta| \le 2S_a} [ C'(S_0,|\Delta|)\eps  + (\theta_{S_0,|\Delta|} C''(S_0,|\Delta|) + 1) \sqrt{2S_a} r]$.
\label{stabres_lscs}
\end{theorem}

\subsection{Discussion}
Notice that conditions \ref{measmodel_lscs_2a} and \ref{measmodel_lscs_2b} are the most difficult conditions to satisfy as the problem size increases and consequently $S_a$ increases. We get condition \ref{measmodel_lscs_2b} because we bound the $\ell_\infty$ norm of the detection LS step error by its  $\ell_2$ norm which is a loose bound. This can be relaxed in the same fashion as in the previous section by assuming that the LS step error is spread out enough (see Corollary \ref{cor2_relax}).

Consider condition \ref{measmodel_lscs_2a}. We get this because (i) we upper bound the $\ell_\infty$ norm of the CS-residual step error, $x_t - \xhat_{t,CSres}$, by its $\ell_2$ norm and (ii) in the proof of Lemma \ref{lscs_bnd}, we upper bound the $\ell_1$ norm of the initial LS step error, $(x_t - \xhat_{t,\text{init}})_T$, by $\sqrt{|T|}$ times its $\ell_2$ norm (this results in the expression for $C''(.,.)$ given in Lemma \ref{lscs_bnd}). If one can argue that both the initial LS step error and the CS-residual error are spread out enough, we can relax condition \ref{measmodel_lscs_2a} to make it somewhat comparable to that of modified-CS.

But even then, $\tilde{G}_1$ will be larger and so LS-CS will still require a higher rate of coefficient increase, $r$, to ensure stability. This is also observed in our simulations. See Fig. \ref{r2_4}.


TITLE: Proof of Terras' method for finding T(k)(x) of Collatz sequence.
QUESTION [2 upvotes]: Terras (via Lagarias) has a method explained here (2.2) for finding the kth term of any Collatz sequence (that is)
$$T(n) = \frac{3n+1}{2}$$ if n is odd and
$$=\frac n2$$ if n is even.
The lambda term makes perfect sense as the factor by which n has been increased or decreased, but what is the p(n) term? What does it signify, and how does one prove that this equation yields $T^k(n)$?

REPLY [2 votes]: $\rho$ is the contribution of all the +1 terms.

For reference, the relevant equations are:
$$
T^{(k)}(n) = \lambda_k (n) n + \rho_k(n)
$$
$$
\lambda_k(n) = \frac{3^{x_0(n) + \cdots + x_{k-1}(n)}}{2^k}
$$
$$
\rho_k(n) = \sum_{i=0}^{k-1} x_i(n) \frac{3^{x_{i+1}(n)+\cdots+x_{k-1}(n)}}{2^{k-i}}
$$
Where $x_i(n)$ is defined as
$$
T^{(i)}(n) \equiv x_i(n) \mod 2
$$

E.g. in the case of $n=3$, $T^{(1)}(3) = 5$ and $T^{(2)}(3) = 8$, which are broken down as:
$$
T^{(1)}(3) = \frac{3}{2} \times 3 + \frac{1}{2}
$$
$$
T^{(2)}(3) = \frac{9}{4} \times 3 + \left( \frac{3}{4} + \frac{1}{2} \right)
$$

Sketch of inductive step in a proof by induction on $k$:
$$
T^{(k)}(n) = \frac{3^{x_{k-1}(n)}}{2}( T^{(k-1)}(n) + x_{k-1}(n) )
=\\= \frac{3^{x_{k-1}(n)}}{2}(\lambda_{k-1}(n) + \rho_{k-1}(n) + x_{k-1}(n) ) =\\
=\lambda_k(n) + \frac{3^{x_{k-1}(n)}}{2} ( \rho_{k-1}(n) + x_{k-1}(n) )
$$
Giving
$$
\rho_k(x) = \frac{3^{x_{k-1}(n)}}{2}( x_{k-1}(n) + \rho_{k-1}(n) ) = \\ =
x_{k-1}(n) \frac{3^{x_{k-1}(n)}}{2} + \sum_{i=0}^{k-2} x_i(n) \frac{3^{x_{i+1}(n)+\cdots+x_{k-1}(n)}}{2^{k-i}} = \\
= \sum_{i=0}^{k-1} x_i(n) \frac{3^{x_{i+1}(n)+\cdots+x_{k-1}(n)}}{2^{k-i}}
$$


TITLE: If $S$ and $M$ are Positive Definitive Matrices, Why $S$ and $M^{-1/2}$S$M^{-1/2}$ share the same eigenvalues?
QUESTION [0 upvotes]: Following and argument to find the solution to the max of the generalized Rayleig Quotient, $\frac {x^tSx}{x^tMx}$,  I found the stament:
if $S$ and $M$ be Positive Definitive, $S$ and $M^{-1/2}$S$M^{-1/2}$ share the same eigenvalues.
How can it be proved?

REPLY [1 votes]: The statement is obviously false. As a counterexample, consider any positive definite $S,M$ for which $S \neq I$ and $S = M$.


TITLE: Linear Transformation Regarding A Vector Space of Continuous Functions
QUESTION [1 upvotes]: The question reads:

Let $V$ be the subspace of $C[0,2\pi]$ spanned by the vectors $1, \sin{x}, \cos{x}$, and let $T: V \to \mathbb{R^3} $ be the evaluation transformation at the sequence of points $0, \pi, 2\pi$. Find: $T(1+\sin{x}+\cos{x}),$ ker($T$), and the range of $T$.

First off, I want to make sure I am interpreting $V$ correctly, in that it is the set of functions that are continuous in the closed interval of $0$ to $2\pi$ and that these functions are of the form $f(x) = c_1 + c_2\sin{x} + c_3\cos{x}$ for some $c_1, c_2, c_3 \in \mathbb{R}$.
Finding $T(1+\sin{x}+\cos{x})$ seemed simple enough, and my answer is the point $(2,0,2)$.
For ker($T$), because any linear combination of $\sin{x}$ will give you zero when you evaluate it at the three points, I said that $\sin{x}$ is in the kernal of $T$. So my answer is ker($T$) = {$0,\sin{x}$}.
And as for the range, because you could have $c_2, c_3 = 0$, the function can be any constant, so all the points in $\mathbb{R^3}$ could be hit. So I said the range of $T$ is $\mathbb{R^3}$.
Is my thought process correct? Any help or criticism is appreciated.

REPLY [2 votes]: Your reasoning for the kernel and range are not correct.  For the kernel, you have shown that $\sin x$ is an element of the kernel, but there may be other elements besides $\sin x$ (and $0$).  In fact, for any $c$, $c\sin x$ must also be in the kernel since the kernel is a subspace.  This still may not be the entire kernel though: you need to determine whether it is possible for $f(x) = c_1 + c_2\sin{x} + c_3\cos{x}$ to be in the kernel if $c_1$ or $c_3$ is nonzero (and if it is possible, when exactly it happens).
For the range, you have shown that for any $a\in\mathbb{R}$, there is some point in the range which has $a$ as one of its coordinates (namely $(a,a,a)$).  However, this does not imply the range is all of $\mathbb{R}^3$: for instance, how do you know $(0,1,2)$ is in the range?  In fact, the range cannot be all of $\mathbb{R}^3$: the space $V$ has dimension at most $3$ (it is spanned by three elements) and $\ker T$ has dimension at least $1$ (it contains $\sin x$), so the dimension of the image of $T$ is at most $3-1=2$.


TITLE: Tensor product of representation of $\mathrm{SU}(2)$ Identity
QUESTION [0 upvotes]: I have troubles to understand an equation, which was stated in a lecture. Consider the spin-j representation $V_{j}$ of $\mathrm{SU}(2)$ with its standard basis
$$\{\vert j,m\rangle\}_{-j\leq m\leq j}$$
Now, consider the fundamental representation $V_{\frac{1}{2}}$.It was then stated that
$$\vert\uparrow\rangle^{\otimes 2j}=\vert j,j\rangle$$
where $\vert\uparrow\rangle=\vert 1/2,1/2\rangle$ is one of the two basis vectors of $V_{1/2}$. I cannot see why this is the case. I know that $V_{1/2}^{\otimes 2j}$ is a submodule of $V_{j}$, as a consequence of the Clebsch-Gordan decomposition, but I do not see how to obtain the equality from above. I guess, the result has something to do with the Clebsch-Gordan coefficients.

REPLY [3 votes]: You have it backwards: $V_j$ (dimension $2j+1$) is a submodule of $V^{\otimes 2j}_{1/2}$ (dimension $2^{2j}$).
The state  $|\uparrow, \ldots, \uparrow\rangle$  is the highest weight state of both the $V_j$ module and the $V^{\otimes 2j}_{1/2}$. In other words it is the unique state with  the highest $m$ spin value $m=j$ in both the larger and the smaller space. Applying step-down ladder opertors keeps the resulting states in $V_j$ so $|\uparrow, \ldots, \uparrow\rangle$   must coincide  with $|j,j\rangle$.


text:
\section{Introduction}
We are working over an algebraically closed field $\K$ of characteristic zero.
Let $X$ be an affine algebraic variety over $\K$.
A point $p\in X$ is called \emph{flexible} if the tangent space $T_pX$ is spanned by the tangent vectors to the orbits of actions of the additive group of the field $\G_a=\G_a(\K)$ on $X$.
The variety $X$ is called \emph{flexible} if each smooth point of $X$ is flexible, see \cite{AFKKZ}.
All the $\G_a$-actions on $X$ generate the \emph{special automorphism group} $\SAut X\subset\Aut X$.

 A group $G$ is said to act on a set $S$ \emph{infinitely transitively} if it acts transitively on the set of ordered $m$-tuples of pairwise distinct points in $S$ for any $m\in\NN$.

 The following theorem explains the significance of the flexibility concept.
\begin{theorem}[{\cite[Theorem 0.1]{AFKKZ}}]\label{th:AFKKZ}
  Let $X$ be an affine algebraic variety of dimension $\ge2$. Then the following conditions are equivalent:
  \vspace{-2pt}
  \begin{enumerate}
    \item The variety $X$ is flexible;
    \item the group $\SAut X$ acts transitively on the smooth locus $X_{\mathrm{reg}}$ of $X$;
    \item the group $\SAut X$ acts infinitely transitively on $X_{\mathrm{reg}}$.
  \end{enumerate}
\end{theorem}

 The flexibility of affine cones over del Pezzo surfaces of degree $\ge4$ corresponding to any very ample polarization was confirmed in \cite{AKZ}, \cite{PW16}, \cite{P13}.
 In this paper we study flexibility of affine cones over smooth del Pezzo surfaces of degree $3$.

 A plurianticanonical polarization is a polarization with respect to a divisor proportional to the anticanonical one.
 It is shown in \cite[Corollary~1.8]{CPW13} that the affine cone $X$ over any plurianticanonically polarized del Pezzo surface of degree $3$  admits no $\G_a$-action.
Nevertheless, $X$ admits a $\G_a$-action for any other very ample polarization, see \cite{CPW15}.
We use constructions and results from \cite{CPW15} in order to show that $\SAut(X)$ acts on $X$ with an open orbit, see Theorem~\ref{th:flex}.
Then $X$ contains an open subset of flexible points,
that is, $X$ is \emph{flexible in codimension one}, see Corollary~\ref{c:flex}.

In Section 2 we provide a criterion of flexibility in codimension one for affine cones, which generalizes similar flexibility criteria in our previous articles \cite{MPS} and \cite{P13}.
In Section 3 we recall generalities on cubic surfaces.
In Section 4 we introduce a useful subdivision of the effective cone.
In Section 5 we recall two constructions of cylinders.
In Section 6 for each of the considered smaller cones we introduce a collection of cylinders.
In order to find these collections, we used the computer algebra system SageMath \cite{Sage}, especially the module for rational polyhedral cones created by V.~Braun and A.~Novoseltsev.
In Section 7 we use these collections to prove flexibility in codimension one and provide an example of a flexible cone.

The author is grateful to M.G.~Zaidenberg for everlasting motivation, numerous discussions and remarks, to I.~Cheltsov and J.~Park for useful discussions on the subject, and to I.~Arzhantsev for useful remarks and suggestions.


TITLE: Is almost sure convergence equivalent to pointwise convergence?
QUESTION [0 upvotes]: I am getting confused with the difference between pointwise convergence and almost sure convergence (or if there should be any difference at all)...
Say that I have a random variable $X_n=n1_{[0,1/n]}$. In this case, $X_n$ converges to $0$ pointwise, and it also converges in probability, since:
$$
P(|X_n - 0| > \epsilon) = \frac{1}{n} \rightarrow 0
$$
However, even though $X_n$ converges pointwise, this is not almost sure convergence right? Since we have
$$
\sum P(|X_n - 0| > \epsilon) = \sum_{n=1}^{\infty} \frac{1}{n} = \infty
$$
since the sum diverges, it means (using the Borel-Cantelli lemma) that it is not convergence almost surely.
So how should I relate the following?

convergence pointwise
convergence almost surely
convergence almost everywhere

REPLY [3 votes]: From the comments it is clear that the probability space is $\Omega=[0,1]$ endowed with the Borel-$\sigma$-algebra and the uniform measure, call it $\mathbb P$.
Let's clarify the definitions first. Almost everywhere convergence is the same as saying that there exists some $\Omega^*$ for which $\mathbb P(\Omega^*)=1$ and $X_n$ converges pointwise on $\Omega^*$. That is for all $\omega\in\Omega^*$ we have $X_n(\omega)\to X$ for some random variable $X$. In probability setting one usually uses "almost surely" instead of "almost everywhere". One also says converges surely if $\Omega^*=\Omega$, i.e. the whole space.
Using this definition we see that for all $\omega \in (0,1]:=\Omega^*$ we have $X_n(\omega)=0$ for $n$ large enough. Moreover $\mathbb P((0,1])=1$ which means that we have almost surely convergence to $0$.
Where does the application of Borel-Cantelli goes wrong in the question then? Well, for the use of Borel-Cantelli like that one needs to assume that the events are independent. However they are not. Just see that for $\varepsilon\in (0,1)$ the event $\{|X_n-0|\leq \varepsilon\}$ implies that $\{|X_m-0|\leq \varepsilon\}$  for all $m>n$ (You see this?).


TITLE: How can I find explicit examples of maximal orders of quaternion algebras that are not isomorphic?
QUESTION [3 upvotes]: I know that there exist algorithms that will construct maximal orders of a quaternion algebra over, say, $\mathbb{Q}$. However, the implemented algorithms that I know of require that you input an order that is not necessarily maximal, which the algorithm then completes. Unfortunately, this does not help if you want examples of orders that are not isomorphic to one another.
The more examples (at least over $\mathbb{Q}$, but preferably over other number fields) that I can get, the better, but I would be happy even with a table of some known examples.

REPLY [1 votes]: Ben explained what happens for indefinite quaternion algebras, and in particular that you don't get such examples if your base field has narrow class number one.  Let me discuss the (totally) definite quaternion algebra case, where you get lots of such examples even over $F=\mathbb Q$.  I can tell you at least 2 methods.  The first you can easily do in Magma.  The second, you can do in Magma or Sage (or by hand if you are patient).  Possibly you can do these things in Pari/GP as well.
Method 1:
Let $F$ be a totally real number field and $B/F$ a totally definite quaternion algebra.  Let $O$ be any maximal order, and $Cl(O)$ the set of left ideal classes of $O$.  Let $I_1, ..., I_h$ be a set of representatives for $Cl(O)$.
Theorem: Every type of maximal order (i.e., conjugacy class of maximal order) of $B$ is represented by some $O_r(I_i)$, the right order of $I_i$.
(The converse is not true, different ideal classes may have the same type of right order, but at least we have the type number is at most the class number $h$.)
Here's a simple example in Magma (unfortunately, I don't think the calculation of $Cl(O)$ is implemented in Sage) for $B$ the quaternion algebra of discriminant 11 over $F = \mathbb Q$.  Here $h=2$.
> QQ := RationalField();
> B := QuaternionAlgebra(QQ, -1,-11);
> O := MaximalOrder(B);
> Cl := LeftIdealClasses(O);
> O1 := RightOrder(Cl[1]);
> O2 := RightOrder(Cl[2]);
> IsIsomorphic(O1,O2);
false
> Basis(O1);
[ 1, i, 1/2*i + 1/2*k, 1/2 + 1/2*j ]
> Basis(O2);
[ 1/2 + 1/2*j + k, 1/4*i + 1/2*j + 5/4*k, j, 2*k ]

Method 2:
Your comment about not an algorithm for extending orders to maximal orders not being helpful is incorrect.  For instance, let's work with definite $B/\mathbb Q$.  Take some imaginary quadratic $E$ embedding in $B$.  Then the ring of integers $O_E$ of $E$ will not in general embed in all maximal orders (if $E$ has small class number).  So as you vary $O_E$ and construct maximal orders containing $O_E$ you should often find non-isomorphic ones.
My recent student, Jordan Wiebe, used a similar idea to construct bases of orders of level $N$ in quaternion algebras $B$:
https://arxiv.org/abs/1810.05249
In our convention of level $N=D$, the discriminant, corresponds to maximal orders.  This basis depends on choosing several parameters (though things are much simpler in the maximal order case), one of which is a quadratic order $o \subset E$ that will be contained in your quaternionic order.  So you can also use this to construct various maximal orders, and test them for isomorphism.  Currently you can get my student's Sage code from his webpage, though this might disappear at some point since he has graduated.
I don't remember, but I imagine Sage has code to test whether different orders in the same quaternion algebra are isomorphic.  FYI here is an elementary method you can use that differentiates most orders: if you have two orders $O_1$ and $O_2$, they can only be isomorphic if they have the same theta series, i.e., if they have the same number of elements of norm $n$ for every $n$.  So you can just count the number of such elements using lattice/quadratic form methods for small $n$, and if you find a discrepancy then $O_1 \not \simeq O_2$.  (Note it is quite rare, but an interesting problem to find, non-isomorphic lattices with the same theta series.)


TITLE: Why is it ok to swap modulus and sum in this case?
QUESTION [1 upvotes]: I am trying to solve Exercise 3.21 in Folland's real analysis. I am watching the solution to this question in the following video.
https://www.youtube.com/watch?v=E8FwgGn1e_o
At about 2:31 in the video he says something along the lines of, "we can bring the sum inside the modulus since the sets are disjoint"
That is to say that if $E_1, E_2,...$ are disjoint measurable sets such that $E=\cup_{i=1}^{\infty}E_i$ then
$\sum_{i=1}^{\infty}\lvert \nu (E_i) \rvert =\sum_{i=1}^{\infty}\lvert \int_{E}\chi_{E_i}d\nu \rvert=\lvert \int_{E}(\sum_{i=1}^{\infty}\chi_{E_1})d\nu\rvert$. The first equality is fine but the second equality does not seem true to me. At the end of the day those integrals are complex numbers, so it does not seem reasonable that this should be true. Note that $\nu$ is a complex measure.

REPLY [1 votes]: The reasoning is definitely not correct, or at least not worded properly.  But we can amend this as follows:
Given $E_1,E_2,\ldots$ disjoint with $E=\cup_jE_j$, define $g:X\to\mathbb C$ by
$$g=\sum_{j=1}^\infty\overline{\operatorname{sgn}(\nu(E_j))}\chi_{E_j}.$$
Then $|g|\leq1$, and
$$\sum_{j=1}^\infty|\nu(E_j)|=\left|\int_Eg\ d\nu\right|\leq\sup\left\{\left|\int f\ d\nu\right|:|f|\leq 1\right\}.$$
Taking the supremum over all such partitions $\{E_j\}$ of $E$, we obtain $\mu_2(E)\leq\mu_3(E)$.


TITLE: Any closed subset in a separable metric space is the union of a perfect set and a set that is at most countable. Why does this matter?
QUESTION [4 upvotes]: I am writing regarding problem 2.28 in Rudin's "Principles of Mathematical Analysis". The statement the reader is asked to prove is as follows:

Every closed subset of a separable metric space is the union of a perfect set and a set that is at most countable.

This statement sounds like it should be important.
What came to mind to me was the definition of the functional limits and the ensuing definitions of continuity we encounter later in an undergraduate analysis course. The definition of continuity works "intuitively" with limit points in the domain, but less "intuitively" at isolated points. Since a perfect set is made up entirely of limit points (and is closed), it seems like this result should let us say something about "weird things" happening at only countably many places for functions defined on closed subsets of a separable metric space. I'm not really sure if this matters at all or is really comprehensible.
Thank you.

REPLY [2 votes]: By the time you read the statement
$\tag 1 \text{Every closed subset of a separable metric space}$
$\qquad \qquad \text{is the union of a perfect set and a set that is at most countable.}$
you are far along the path of mathematically 'sculpturing' topological concepts. it is instructive to 'reverse engineer' this statement. I think you can safely say that if you do this, you will be forced to discover the foundations of point-set topology.
We all agree that the integers $\mathbb Z$ is a closed set of isolated points on the real number line $\mathbb R$. But this is just too easy to do, since you have the integers extending out to both $-\infty$ and $+\infty$. So can you find a countable (infinite) closed set of isolated points constrained to be inside the interval $[-1,+1]$?
Answering this question and the natural questions that arise as you proceed on your journey will be an awe inspiring mathematical challenge.
To answer the OP's question, reading and understanding (1) in a math book makes me think of mountaineers, and images like

The work, training and challenges of the accomplishment is safely behind them now.

The reader might be interested in exploring the perfect set property where they will find the following:
The Cantor–Bendixson theorem states that closed sets of a Polish space $X$ have the perfect set property in a particularly strong form; any closed set $C$ may be written uniquely as the disjoint union of a perfect set $P$ and a countable set $S$. Thus it follows that every closed subset of a Polish space has the perfect set property. In particular, every uncountable Polish space has the perfect set property, and can be written as the disjoint union of a perfect set and a countable open set.
Example: Consider $\text{2-dim Euclidean space, } \mathbb R^2$, which is a polish space. Define
$\quad C = \text{The Unit Circle } \cup \{(\pm \frac{1}{n},\, 0) \;|\; n \ge 1\} \cup \{(0,\, \pm \frac{1}{n}) \;|\; n \ge 1\} \cup \{(0,\,0)\}$
The set $C$ is closed in $\mathbb R^2$, and it can be written (uniquely) as the union of the unit circle, a perfect set, and the remaining countable points in $C$ with norm less than $1$. All these points not on the unit circle are isolated except for $(0,\,0)$, the origin.


TITLE: Which physics subjects should a math major follow if s/he's interested in Smart Grid Networks?
QUESTION [0 upvotes]: I study mathematics and I would like to work on Smart Grid Networks in the (near) future. I would like to do so by applying optimization theory, percolation theory, Markov chains and more to problems that are related to Smart Grid Networks.
However, I don't know anything about physics. Would it be useful for me to learn about a couple of physics subjects that are related to Smart Grid Networks? If so, which ones?

REPLY [2 votes]: The smart grid isn't a single thing, or even a bound-able set of technologies.  To give a non-physics example, you can watch a Google Tech Talk from someone who's largely focused on the communications, as in TCP/IP sort of stuff, as it applies to the smart grid.
Physical underpinnings are important, but I would say that what you want is more a "generalist engineer" background built around smart grid applications.  Then a focus that will develop with whatever direction you take or mathematical optimization subset you're interested in.
The part of Electrical Engineering you're interested in is power systems.  The bread and butter of this is electrical network analysis, but there are other physical principles behind it which come from manifestations of Maxwell's Laws.  For generators, a broad sense of inductance is necessary, even with reference frame transformations applied to them.  You should know about mutual inductance, leakage inductance, and general matrix formulation.  You should also be privy to the basics of 3-phase power and how it ties in with electrical network analysis.
Particularly for the smart grid, the field is expanding, and you should expect a short half-life for a degree in the "new" stuff.  In studying the basics of power systems, you should have a good deal of comfort with inductance and the mechanism of operation for conventional transformers, but there's ongoing interest in solid state transformers.  But this isn't all.  Not only are solid state transformers exciting because the technology is getting better - but they can do different tasks, tasks that will be relevant to a more heterogeneous smart grid.  Specifically, I would suggest getting a strong background in IGBTs.  A part of the thinking is that this kind of new technology will prove a general purpose power converter box, which can do DC-DC, AC-DC, and lots of switching.
The physical basis of that is all semiconductor technology.  If you're interested in smart grid, you should be braced for hearing a lot of this, even if it's not your own focus.  From your mathematical background and interest in mathematical optimization, I would predict you're more interested in dispatch algorithms and multilayer control systems.  But this doesn't really point to any particular physics mastery that's needed.
In all cases, grid management is tied in with the physics of the components tied into it.  For instance, grid-connected batteries have their own physics.  These physics are simplified and lumped into a mathematical model which can be plugged right into the system-level simulation.  At its core, however, it relies on ion transport.  In other cases, we still have conventional power plants.  Beyond the heat production you should be very interested in the fuel source or combustion physics unless it's direct use like a combustion turbine.  Thermal cycles are more directly relevant, and how that energy gets communicated to the generator through expansion and torque.  In a more fine-detail, you should be interested in the dynamical aspect of rotor (prime mover) inertia and the oscillations that those are subject to when plugged into the rest of the system.  There are even more levels of oscillation you should be worried about, as the next generation electrical conversion systems, HVDC equipment, and things like that often employ high-frequency switching which contributes oscillations that are problems for other components.  Of course, you'll also probably be interested in photovoltaic, taking you back to semiconductor physics.
This is so much that it might be better to ask yourself what your priorities are.  I would go through something like this:

Maxwell's equations and the principle behind inductors/generators
A broad foundation in semiconductor physics
EM wave propagation, and the physical limits of AC network matrix representations


TITLE: Find the additive inverse of binary number
QUESTION [3 upvotes]: My online assembly class doesn't really show us how to find the additive inverse of finding the additive inverse of binary, and I can't find much online. The question is: find the additive inverse of 0000 0000 1110 1111 1010 1101 0110 1100. Any insight on how to solve this or some steps would be great. Thanks.

REPLY [3 votes]: If we're dealing with $n$-bit binary numbers, i.e., only numbers in the range $0$--$2^n - 1$, and for a given $a$ we denote by $\bar a$ that $2^n$ bit number whose every bit is the opposite to that in the same position in $a$, then
$a + \bar a = \underset{\text{n bits}}{1 1 \ldots 1}; \tag 1$
then
$a + \bar a + 1 = \underset{\text{n bits}}{0 0 \ldots 0}; \tag 2$
thus
$-a \equiv \bar a + 1; \tag 3$
for example, with
$a = 1110, \tag 4$
we have
$\bar a = 0001, \tag 5$
$-a = \bar a + 1 = 0010; \tag 6$
it is easy to check that
$-a + a = a + \bar a + 1 = 1110 + 0010 = 0000; \tag 7$
again, with
$a = 1010, \tag 8$
$\bar a = 0101, \tag 9$
$-a = 1 + \bar a = 0110, \tag{10}$
and we see that
$1010 + 0110 = 0000. \tag{11}$
The reader may easily try this out/check it for larger values of $n$ than $4$.
It is important to remember that we are really dealing with arithmetic $\mod 2^n$, i.e., in $\Bbb Z_{2^n}$, where the elements are written in binary representation.