text:
\begin{document}
\title{Large deviations for the maximum of a branching random walk with stretched exponential tails}
\author{Piotr Dyszewski, Nina Gantert and Thomas H\"ofelsauer}
\maketitle

\begin{abstract}
	We prove large deviation results for the position of the rightmost particle, denoted by $M_n$, in a one-dimensional branching random walk in a case when Cram\'er's condition is not
	satisfied. More precisely we consider step size distributions with stretched exponential upper and lower tails, i.e.~both tails decay as $e^{-|t|^r}$ for some $r\in( 0,1)$. It is known that in this case, $M_n$ grows as
	$n^{1/r}$ and in particular	faster than linearly in $n$. Our main result is a large deviation principle for the laws of
	$n^{-1/r}M_n$ . In the proof we use a comparison with the maximum of (a random number of) independent random walks, denoted by $\tilde M_n$, and we show a large deviation principle for the laws of
	$n^{-1/r}\tilde M_n$ as well.

\medskip
\noindent \textbf{Keywords:} branching random walk, large deviations, stretched exponential random variables

\smallskip
\noindent \textbf{AMS 2000 subject classification:} 60F10, 60J80, 60G50.
\end{abstract}

\section{Introduction} \label{intro}

	We study branching random walk, which is a discrete time Galton-Watson processes with a spatial component. Given a reproduction law and a step size distribution the
	evolution of the process can be described as follows.  At time $n=0$ we place one particle at the origin of the real line. At time $n=1$ this particle splits according to
	the reproduction law and each new particle performs an independent step, according to the step size distribution. We assume that the branching mechanism and the displacements
	are independent. From here, each particle evolves in the same way,
	independently of all other particles. \\

	We are interested in the position of the rightmost particle at time $n \in \mathbb{N}_0$, which we will denote by $M_n$. In the case when the step size distribution satisfies Cram\'er's condition,
	the asymptotic behaviour of $M_n$ is fairly well understood (see the recent monograph~\cite{S15} and references therein). We will investigate a case of heavy-tailed steps,
	when Cram\'er's condition if not satisfied. More specifically, we consider the case of steps with stretched exponential distribution, when both tails decay as
	$e^{-|t|^r}$ for some $r\in( 0,1)$. Then it is known that $M_n$ grows like $n^{1/r}$ as established by a law of large numbers proved in~\cite{G00}.
	In the present article we will provide the corresponding large deviation results. Our main result is Theorem \ref{theorem_BRW}  which gives a large deviation principle for the laws of $M_n/n^{1/r}$.
This complements previous results on large deviations for branching random walks given by
\cite{BM17}, \cite{CH17}, \cite{CH18}, \cite{GH18}, \cite{LP15}, \cite{LT17}, \cite{R93}.

The article is organized as follows. In Section~\ref{prel} we present the necessary preliminaries concerning the step size distribution and the branching mechanism and provide the necessary notation.

 The main results are presented in Section~\ref{sec:main} and are proved in Section~\ref{sec:proofs}.

\section{Preliminaries}\label{prel}

We write $f \sim g$ for two functions $f,g \colon \N \to \R$ whenever $f(n)/g(n) \to 1$ as $n \to \infty$. We call a sequence $(a_n)_{n \geq 0}$ subexponential if for
	any $\varepsilon>0$, $a_n e^{-\varepsilon n} \to 0$ as $n \to \infty$.

	\subsection{Step size distribution}
Let $X, X_1, X_2, \ldots$ be a collection of iid random variables of zero mean and let $S = (S_n)_{n \geq 0}$ be the corresponding random walk, that is $S_0=0$,
	$S_n = \sum_{k=1}^n X_k$.
	In the case when Cram\'er's condition holds, i.e.
	\begin{equation}\label{eq:cramer}
	\E[e^{sX}]<\infty \quad \mbox{for some }s>0
	\end{equation}
	it is well known that
	$\lim_{n \to \infty} n^{-1} \log \P(S_n>xn) = -\sup_{s \geq 0}\left\{sx - \log \E[e^{sX}] \right\}$ for  $x >0$,	 see~\cite{DZ10}. If on the other hand, $\E[e^{sX}]=\infty$ for any $s>0$, it is known that the probabilities $\P(S_n>xn)$ decay slower than exponentially in $n$ with the exact rate
	 being determined by the behaviour of the tail $\P(X>x)$ as $x \to \infty$. We will focus on the case of stretched exponential distribution.

	\begin{as} \label{assumption_RW}
		The random variable $X$ is centred $(\E [ X ] =0)$ and has stretched exponential upper and lower tails, that is there exist $\lambda_+, \lambda_->0$, $r \in (0,1)$ and slowly varying
		functions $a_+$ and $a_-$ such that
		\begin{equation}\label{upptail}
			\P(X \geq x)=a_+(x) e^{-\lambda_+ x^r}
			\end{equation}
			and
			\begin{equation}\label{lowtail}
			 \P(X \leq -x)=a_-(x) e^{-\lambda_- x^r}
		\end{equation}
		for all $x\geq 0$.
	\end{as}
\begin{remark}
We assume \eqref{lowtail} for simplicity, to avoid an annoying number of case
distinctions: our strategy of proof can be used for other lower tails, see also Remark \ref{moregeneral}.
\end{remark}

	Large deviations for a random walk in the case when Cram\'er's condition is not fulfilled go back to~\cite{N69} where it was established that if the law of $X$ has a density that decays as $e^{-|x|^r}$ as $|x| \to \infty$, then
$\lim_{n \to \infty} n^{-r} \log \P(S_n > nx) = -x^r$
	for $x>0$. It is easy to see, that in order to obtain an exponential rate of decay under Assumption~\ref{assumption_RW} one has to consider probabilities of the
	form $\P(S_n \geq xn^{1/r})$.

	\begin{lemma} \label{lem:LDP_RW}
		Let Assumption \ref{assumption_RW} hold. Then, the laws of $\frac{S_n}{n^{1/r}}$ satisfy a large deviation principle with rate function $I$ given by
			\begin{equation} \label{def_I}
				I(x)= \begin{cases}
				\lambda_+ x^r & \text{for } x \geq 0\\
				\lambda_- (-x)^r & \text{for } x \leq 0.\\
				\end{cases}
		\end{equation}
	\end{lemma}

	This lemma follows, for example, from the main results in~\cite{GRR14}.

\subsection{Branching mechanism}
	Let $Z = (Z_n)_{n \geq 0}$ be a Galton-Watson process with $Z_0 =1$ and reproduction law $ p =(p(k))_{k\geq 0}$.
The key parameter describing the asymptotic behaviour of
	$Z$ is the mean of $p$ denoted by
	\begin{equation*}
		m = \sum_{k \geq 0} k p(k).
	\end{equation*}
	It is well-known (assuming $p(1)<1$ to rule out a degenerate case)  that the branching process survives with positive probability if and only if $m >1$. More precisely, if we denote by $q= \P(\lim_{n \to \infty} Z_n =0)$
	the extinction probability, then $q$ is the smallest solution of the equation $f(s) = s$,
	where $f$ denotes the probability generating function of $p$, that is $f(s) = \sum_{k\geq 0}s^kp(k)$. If $m  = f'(1-)>1$, then we see that $q<1$.
	On the event of survival, $Z_n \to \infty$  as $n \to \infty$ and the Kesten-Stigum Theorem (see Theorem~\ref{Lemma_GWP_martingale}) asserts that $Z_n/m^n$ converges almost surely to a finite and strictly positive random variable,
	provided that $\E[ Z_1 \log Z_1] <\infty$.

Our assumptions on the branching process will be the following.
	\begin{as} \label{as:BP}
The Galton-Watson process $Z$ is supercritical, that is $m>1$, and $\E[ Z_1 \log Z_1] <\infty$.
	\end{as}

	We introduce the conditional probability
	\begin{equation}\label{Pstardef}
		\P^*(\: \cdot \: ) = \P(\: \cdot \:  | \: Z_n>0, \:\forall \: n \in\N ).
	\end{equation}
	We will need the rate of decay of the probabilities that $Z_n$ grows slower than $m^n$. It turns out
	that one has to distinguish between two cases, namely $p(0) + p(1) > 0$ and
	$p(0) +p(1) = 0$. The first one is often referred to as the Schröder case, while the latter is called Böttcher case. We see that in the second case ($p(0)+p(1)=0$), $Z$ should
	grow faster since $Z_n \geq 2^n$ for all $n$. Denote the set of all possible values of $Z$ by
	\begin{equation} \label{def_A}
		A= \bigl\{l \in \N \colon \exists n \in \N \text{ such that } \P(Z_n=l)>0 \bigr\}.
	\end{equation}
	Let $k^*$ be smallest possible number of offspring, that is
	\begin{equation} \label{def_k*}
		k^*=\inf\{k \geq 1 \colon p(k)>0 \}.
	\end{equation}
	Note that $k=k^*$ is the smallest positive integer, such that $\P(Z_n=k)>0$ for some $n \in \N$. In the Böttcher case we have $k^*\geq 2$.

\subsubsection{Schröder case: $p(0)+p(1)>0$}
	In this case the rate of deviations for the branching process $Z$ is determined by
	\begin{equation}\label{eq:defRho}
		\rho = - \log f'(q) = -\log \E \left[Z_1 q^{Z_1-1}\right] \in (0, \infty)\, .
	\end{equation}
	Note that $\rho = -\log p(1)$ if $p(0)=0$ (and therefore $q=0$). Moreover $p(0)+p(1)>0$ is necessary and sufficient for $\rho<\infty$.
	We summarize several results concerning the lower deviations of $Z$ in the following Lemma.

	\begin{lemma}\label{lem:LDBP_S}
		Let Assumption~\ref{as:BP} be in force and suppose that $p(0)+p(1)>0$. Then,
		\begin{itemize}
			\item For any $k \in A$,
				\begin{equation*}
					\limn \frac{1}{n} \log \P^* \bigl(Z_n =k \bigr) = - \rho.
				\end{equation*}
			\item For every subexponential sequence $(a_n)_{n \geq 0}$ such that $a_n \to \infty$ as $n \to \infty$,
				\begin{equation*}
					\limn \frac{1}{n} \log \P^* \bigl(Z_n \leq a_n \bigr) = - \rho.
				\end{equation*}
			\item For any $x \in [0, \log m]$,
				\begin{equation}\label{def_I_GW_S}
					\limn \frac{1}{n} \log \P^* \bigl( Z_n \leq e^{xn} \bigr) = -  I^{\textnormal{GW}}(x) := -\rho \bigl(1-x (\log m)^{-1} \bigr).
				\end{equation}
		\end{itemize}
	\end{lemma}

	The first claim of Lemma~\ref{lem:LDBP_S} can be found in  \cite[Chapter 1, Section 11, Theorem 3]{AN04}, the the last two are special cases of~ \cite[Theorem 4]{FW06}.
	 Note that in all three cases precise asymptotics for the deviations are known.
	In our arguments we will only make use of the logarithmic asymptotics.

\subsubsection{Böttcher case: $p(0)+p(1)=0$}

	We see that whenever $p(0)+p(1)=0$, $\rho$ given in~\eqref{eq:defRho} is infinite. Thus one may expect that $ \P^* \bigl( Z_n \leq e^{xn} \bigr)$ decays faster than
	exponentially in the Böttcher case.  For example, one can see directly that
	\begin{equation*}
		 \P\left(Z_n=(k^*)^n\right) = \exp\left \{ \frac{(k^*)^n-1}{k^*-1} \log p(k^*) \right\},
	\end{equation*}
	where $k^*$ is given in~\eqref{def_k*}. It turns out that $k^*$ is the key parameter describing the lower deviations of $Z$.
	We will make use of a result established in~\cite{FW06}.

	\begin{lemma}\label{lem:LDBP_B}
		For any $k_n = o(m^n)$ such that $k_n \geq (k^*)^n$, there are positive constants $B_1, B_2$ such that
		\begin{align*}
			-B_1 & \leq \liminf_{n \to \infty} (k^*)^{b_n-n} \log \P(Z_n \leq k_n) \\
				& \leq \limsup_{n \to \infty} (k^*)^{b_n-n} \log \P(Z_n \leq k_n) \leq -B_2,
		\end{align*}
		where
		\begin{equation*}
			b_n = \min \{ j \: | \: m^j(k^*)^{n-j} \geq 2 k_n \}.
		\end{equation*}
	\end{lemma}

\subsection{Branching random walk}

	We now define the branching random walk which is a discrete time stochastic process that evolves in the following way.
	At time $n=0$ one particle is placed at the origin of the real line.
	This particle will start a population which will be described by the branching process $Z = (Z_n)_{n\geq 0}$. At time $n=1$ the initial particle splits into $Z_1$ new particles which
	move independently of each other and $Z_1$. We assume that
	each displacement from the place of birth is an independent copy of $X$. Each particle evolves according to these rules independently of all others. More precisely at time $n=2$,
	each particle, independently of the others, splits into a random number of particles distributed according to $p$. The total number of particles present in the system at time $n=2$
	is denoted by $Z_2$. Each particle performs, independently of other particles and $Z_1, Z_2$, a step distributed as $X$. The system continues to evolve according to these rules.
	Let $\mathcal{T} = (V, E)$ be the associated Galton-Watson tree with the initial particle denoted as the root $o \in V$.
	Let $D_n \subset V$ denote the
	set of particles present at time $n$. Clearly $|D_n | = Z_n$.
	For $v, w \in V$ write $[v,w]$ for the set of edges along the unique line from $v$ to $w$. To model the displacements, assume that each edge of the tree $\mathcal{T}$ is labeled
	with an independent copy of $X$, that is we are given
a collection	$\{ X_e\}_{e\in E}$ of iid random variables distributed as $X$. Then the position of the particle $v$ is equal to
	\begin{equation*}
		S_v = \sum_{e \in [o,v]} X_e
	\end{equation*}
	and the position of the rightmost particle at time $n$ is
	\begin{equation*}
		M_n = \max_{v \in D_n}S_v.
	\end{equation*}
 	It is well known, that if \eqref{eq:cramer} is satisfied and the step size distribution has mean $0$, then $M_n$ has a linear speed, that is $n^{-1}M_n$ converges to a strictly positive constant a.s. (see \cite{B76, H74, K75}).
	In this case large deviations for $M_n$ were already considered in a number of papers, see \cite{BM17, CH17, CH18, GH18, LP15, LT17, R93}. We refer to~\cite{S15} for a more general model and many limit laws and concentration properties.

	In our case, as verified in~\cite{G00}, under Assumptions~\ref{assumption_RW} and \ref{as:BP}, $M_n$ grows with superlinear speed.
	\begin{lemma}
		Let Assumptions~\ref{assumption_RW} and \ref{as:BP} be in force. Then
		\begin{equation}\label{linspeed}
			\limn \frac{M_n}{n^{1/r}} = \alpha:= \Bigl( \frac{\log m}{\lambda_+} \Bigr)^{1/r} \quad \P^*\text{-a.s.}
		\end{equation}
	\end{lemma}

	A more detailed description of the asymptotic behaviour of $M_n$, giving also the second term, i.e.~the order of $M_n -n^{1/r}( \frac{\log m}{\lambda_+} )^{1/r}$, was recently delivered in~\cite{DGH20}.
	Our main results stated in the next section concern large deviations related to~\eqref{linspeed}.  Clearly, $M_n$ is a maximum of random walks which are pairwise dependent.
	In some aspects however, the asymptotic behaviour of $M_n$ is similar to that of a
	maximum of (a random number of) independent random walks. We will use the latter as a reference model. Consider a collection $(X^{(j)}_k)_{j,k\geq 1}$ of iid random variables distributed as $X$ and put
	$S_0^{(j)}=0$ and
	\begin{equation}\label{defcopy}
	S_n^{(j)}=\sum_{k=1}^nX_k^{(j)}\, .
	\end{equation}
	 We then define the maximum of (a random number of) independent random walks by
	\begin{equation}\label{eq:Mind}
		\tilde{M}_n = \max_{1\leq j\leq Z_n}S_n^{(j)}.
	\end{equation}
	Since $\tilde{M}_n$ involves independent random variables it stochastically dominates $M_n$ which involves dependent random walks, see Lemma \ref{lemma_BRW_vs_ind_RW2}. As a consequence, we can use the deviations of $\tilde{M}_n$ as a bound for the deviations of $M_n$. For completeness, we also establish large deviations for the laws of $n^{-1/r}\tilde{M}_n$.

\section{Main results}\label{sec:main}
Recall \eqref{linspeed} and let, for $x < \alpha$,
\begin{equation} \label{def_H}
		H(x) =
		\left\{ \begin{array}{cc} k^*\lambda_- (\alpha-x)^r & \mbox{if } p(0)+p(1)=0 \\
		  \min\left\{ \rho + \lambda_-(-x)^r, \lambda_- (\alpha-x)^r \right\}  & \mbox{if } x \leq 0,\: p(0)+p(1)>0\\
		   \min \left\{ \lambda_- \alpha^r,  \rho  \right\}\cdot \left(1 - \left( \frac x\alpha\right)^r \right) & \mbox{if } x \geq 0, \:p(0)+p(1)>0.
				\end{array} \right.
	\end{equation}

	Define the rate function of the branching random walk as
	\begin{equation} \label{def_I_BRW}
		I^{\text{BRW}}(x)=
		\begin{cases}
		\lambda_+ x^r - \log m & \text{for } x \geq \alpha,\\
		H(x) & \text{for } x < \alpha.
		\end{cases}
	\end{equation}
Our main result is the following.
	\begin{theorem}\label{theorem_BRW} [Branching random walk]\\
		Suppose that Assumptions \ref{assumption_RW}  and \ref{as:BP} are satisfied. Then, the laws of $ \frac{M_n}{n^{1/r}}$ under $\P^*$ satisfy a large deviation principle
		with rate function $I^{\textnormal{BRW}}$.
	\end{theorem}
\begin{remark}\label{Hvardes}
In the proof of Theorem \ref{theorem_BRW}, we will use the following variational form of $H$.
 For $x < \alpha$ let
\begin{equation} \label{gammadef}
\gamma =\gamma(x) =
		\left\{ \begin{array}{cc} 1 & \mbox{if } x\leq 0\\
		1- \bigl(\frac{x}{\alpha}\bigr)^r  & \mbox{if } x > 0.
				\end{array} \right.
	\end{equation}
Then
		\begin{equation} \label{def_Hvar}
		H(x) =
		\left\{ \begin{array}{cc} k^*\lambda_- (\alpha-x)^r & \mbox{if } p(0)+p(1)=0,\\
		\inf_{t \in [0,\gamma]} \Bigl\{ t \rho + \lambda_- \bigl((1-t)^{1/r}\alpha-x \bigr)^r  \Bigr\} & \mbox{if } p(0)+p(1)>0.
				\end{array} \right.
	\end{equation}
One derives \eqref{def_H} from \eqref{def_Hvar} by a straightforward calculation.
\end{remark}

\begin{remark}\label{moregeneral}
For the upper large deviations, \eqref{lowtail} is not needed: if \eqref{upptail} holds and if
$\E[ X ] =0$ and $\E[ X^2 ] < \infty$,
then for $x \geq \alpha$,
\begin{equation}
\lim_{n \to \infty} \P^* \Bigl(\frac{M_n}{n^{1/r}} \geq x \Bigr)= - \left(\lambda_+ x^r - \log m\right) \, .
\end{equation}
If \eqref{lowtail} is not satisfied, the asymptotics of
$\P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr)$
for $x < \alpha$ may change but our techniques of proof still apply.
\end{remark}
We now state the results for independent walks and then give some intuition for the rate functions.
	Define the rate function for the maximum of
	independent random walks in the Schröder case as
	\begin{equation} \label{def_I_ind_S}
		I^{\text{ind}}(x)=
		\begin{cases}
		\lambda_+ x^r - \log m & \text{for } x \geq \alpha,\\
		\rho \bigl(1 - \tfrac{\lambda_+ x^r}{\log m} \bigr)  &  \text{for } 0 \leq x \leq \alpha,\\
		k^* \lambda_- (-x)^r + \rho & \text{for } x \leq 0.
		\end{cases}
	\end{equation}
	Note that $\rho \bigl(1 - \tfrac{\lambda_+ x^r}{\log m} \bigr)= I^{\text{GW}}(I(x))$ for $ 0 \leq x < \alpha$, see \eqref{def_I} and \eqref{def_I_GW_S}.

	\begin{theorem}\label{theorem_ind_RW_Schröder}[Independent random walks, Schröder case]\\
		Suppose that Assumptions \ref{assumption_RW} and \ref{as:BP} are satisfied and that
		$p(0)+p(1)>0$. Then, the laws of $\frac{\tilde{M}_n}{n^{1/r}}$ under $\P^*$ satisfy a large deviation principle with rate function $I^{\text{ind}}$.
	\end{theorem}
We now turn to the deviations of $\tilde{M}_n$ in the Böttcher case.
In the Böttcher case ($p(0)+p(1)=0$) we have $\rho=\infty$ and therefore $I^{\text{ind}}(x)=\infty$ for all $x<\alpha$. Hence, in this case the lower deviation probabilities
	$\P^*( \tilde{M}_n \leq xn)$ for $x<\alpha$ decay faster than exponentially in $n$.

\begin{theorem}\label{theorem_ind_RW_B} [Independent random walks, Böttcher case]\\
	Suppose that Assumptions \ref{assumption_RW} and \ref{as:BP} are satisfied and that $p(0)+p(1)=0$. Then,
	\begin{align*}
		\log \P(\tilde{M}_n \geq xn^{1/r}) &\sim -(\lambda_+x^r-\log m)n & \mbox{for }x \geq \alpha, \\
		\log | \log \P(\tilde{M}_n \leq xn^{1/r})| &\sim - n \log k^* \left(1  - \frac{\lambda_+x^r}{\log m}\right) & \mbox{for } x \in [ 0, \alpha), \\
		\log \P(\tilde{M}_n \leq xn^{1/r}) &\sim -n(k^*)^n\lambda_- |x|^r& \mbox{for } x < 0.
	\end{align*}
\end{theorem}

Let us now give some intuition for the rate function $I^{\text{ind}}$ and describe the large deviation events leading to $\{\tilde{M}_n \geq xn^{1/r}\}$ and $\{M_n \geq xn^{1/r}\}$ for some $x>\alpha$, respectively
	$\{\tilde{M}_n \leq xn^{1/r}\}$ and $\{M_n \leq xn^{1/r}\}$ for some $x<\alpha$.

For $x>\alpha$, the number of particles should be larger or equal than expected, i.e.~$Z_n \geq e^{nt}$ for some $t \geq \log m$. It turns out that $t=\log m$ is the optimal value: it is too expensive to produce $e^{nt}$ particles for some $t > \log m$.
If there are $e^{nt}$ particles at time $n$, the probability that at least one particle reaches $xn^{1/r}$ is of order $\exp(-I(x)n+tn+o(n))$ for
	$t < I(x)$. Therefore,  the rate function is $I(x) - \log m$.
	This argument is the same for the independent walks and for the branching random walk.
Note that for $x > \alpha$ the rate of decay of $\log \P(\tilde{M}_n \geq xn^{1/r})$  in the Schröder case and the Böttcher case coincide, and concide with the rate function for branching random walk.\\
	Consider now independent walks in the Schröder case.
	If $0 \leq x< \alpha$, the probability that one particle reaches $xn^{1/r}$ is of order $\exp(-I(x)n+o(n))$. Hence, for every $\varepsilon>0$, if there are less than $e^{(I(x)- \varepsilon) n}$
	particles, the probability that none of these particles reaches $xn^{1/r}$ is close to 1. However, if there are more than $e^{(I(x)+ \varepsilon) n}$ particles, this probability decays
	exponentially in $n$.
	If $x<0$, already the probability that a single particle is below $xn^{1/r}$ at time $n$ decays exponentially fast in $n$. Hence, if the number of particles $Z_n$ grows exponentially, the
	probability that all particles are below $xn^{1/r}$ at time $n$ decays faster than exponentially. Therefore, the number of particles needs to grow subexponentially. Since $\rho$ does not
	depend on the choice of $k$ in Lemma~\ref{lem:LDBP_S}, the optimal strategy for $\{\tilde{M}_n \leq xn^{1/r}\}$ is to  have only $k^*$ particles at time $n$ with all their positions being below $ xn^{1/r}$.

For the branching random walk, in the Schröder case the strategy for
	$x < \alpha$ goes as follows. At time $tn$ there are only $k^*$ particles, and
	one of them has an offspring whose displacement is negative with a large absolute value, while all other $k^*-1$ particles have no offspring. Note that in the Schröder case either $k^*=1$ or $p(0) > 0$. Afterwards, all particles move and reproduce as usual.\\
Further notice, that in contrast to the case of independent random walks, the number of particles can also grow exponentially if $x<0$ in the Schröder case. It suffices to have a
small number of particles at time $tn$ for some $t \in [0,1]$.\\
To compare the rate functions in the Schröder case, note that the maximum of independent random walks stochastically dominates the maximum of the branching random walk, see
Lemma~\ref{lemma_BRW_vs_ind_RW2}. Therefore, $I^{\text{ind}}(x) \leq I^{\text{BRW}}(x)$ for $x>\alpha$, respectively $I^{\text{ind}}(x) \geq I^{\text{BRW}}(x)$ for
	$x<\alpha$. For $x<\alpha$, the inequality is in general strict. For $x>\alpha$, the rate functions coincide, see the argument above.

\section{Proofs}\label{sec:proofs}
\subsection{Auxiliary results}

	We often need to estimate the number of particles at time $n$, which has expectation $m^n$. Let $W_n = \frac{Z_n}{m^n}$ and $(\mathcal{F}_n)_{n \in \N}$ be the natural
	filtration of the Galton-Watson process, i.e.~$\mathcal{F}_n= \sigma(Z_1, \ldots, Z_n)$.
	Then $(W_n)_{n \in \N}$ forms a non-negative martingale with respect to the filtration $(\mathcal{F}_n)_{n \in \N}$. Therefore, $W_n \to W$ almost surely, where $W$ is an almost surely
	finite random variable. The following well-known theorem shows that under our assumptions, the limit $W$ is non-trivial, i.e.~$\P^*(W>0)=1$.
	\begin{theorem}[Kesten-Stigum Theorem] \label{Lemma_GWP_martingale}
		If Assumption \ref{as:BP} is satisfied, we have
		\begin{equation*}
			\E[W]=1 \quad \text{and } \quad \P(W=0)=q < 1.
		\end{equation*}
	\end{theorem}
	A proof can e.g.~be found in \cite[Chapter 1, Section 10, Theorem 1]{AN04}.\\
	In the proof of Theorem~\ref{theorem_BRW} we use the fact that the maximum of independent random walks stochastically dominates the maximum of the branching random walk, see
	Lemma~\ref{lemma_BRW_vs_ind_RW1} below. Lemma~\ref{lemma_BRW_vs_ind_RW2} comes from the following general statement which we will use in our proof as well.  Both lemmas are proven in~\cite[Lemma~5.1, 5.2]{GH18}.

\begin{lemma}
\label{lemma_BRW_vs_ind_RW1}
		Let $(X_i)_{i \in \N}$ and $(Y_i)_{i \in \N}$ be independent sequences of (not necessarily independent) random variables. Furthermore, assume that the random variables
		$Y_i, i \in \N$, have the same distribution. Then we have for all $k \in \N$ and $x \in \R$
		\begin{equation*}
		\P \Bigl( \max_{i \in \{1, \ldots, k\}} \{X_i+Y_1\} \leq x \Bigr) \geq \P \Bigl( \max_{i \in \{1, \ldots, k\}} \{X_i+Y_i\} \leq x \Bigr).
		\end{equation*}
	\end{lemma}
\begin{lemma}
\label{lemma_BRW_vs_ind_RW2}
		For all $n \in \N$ and $x \in \R$
		\begin{equation}\label{domino}
			\P (M_n \leq x) \geq \P (\tilde{M}_n \leq x).
		\end{equation}
	\end{lemma}

	The statement of Lemma~\ref{lemma_BRW_vs_ind_RW2} is also true with respect to $\P^*$.

We will also use the following tail asymptotic for stretched exponential random variables, which follows from~\cite[Theorem 8.3]{DDS08} .
\begin{lemma}
Let Assumption~\ref{assumption_RW} be in force.
		If $x_n \gg n^{\sigma}$, where $ \sigma = \frac{1}{2-2r}$, then
		\begin{equation}\label{sumasmax}
			\P\left[ S_n > x_n \right] \sim n \P\left[ X>x_n \right].
		\end{equation}
	\end{lemma}

\subsection{Main steps}
	In this section we prove the main results of the paper.  We first prove the results for the branching random walk using the results for the independent walks. Then, we
	give the proof of the results for the independent walks.

\subsection*{Branching random walk} \label{proofs_BRW}

\begin{proof}[Proof of Theorem \ref{theorem_BRW}]
\textbf{Case (1)}: $x > \alpha$\\
The upper bound immediately follows from Theorems~\ref{theorem_ind_RW_Schröder} and~\ref{theorem_ind_RW_B} combined with Lemma~\ref{lemma_BRW_vs_ind_RW2}.
	It remains to prove the lower bound. For $v \in D_{n-1}$ denote the rightmost descendant of $v$ at time $n$ by $M^v_1$. By Lemma~\ref{lemma_BRW_vs_ind_RW1},
	\begin{align}
	\P^* \Bigl(\frac{M_n}{n^{1/r}} \geq x \Bigr)
	& = \P^* \Bigl( \max \limits_{v \in D_{n-1}} \frac{M_1^v - S_v}{n^{1/r}} + \frac{S_v}{n^{1/r}} \geq x \Bigr) \notag \\
	& \geq \P^* \Bigl( \max \limits_{v \in D_{n-1}} \frac{M_1^v - S_v}{n^{1/r}} + \frac{S_{n-1}}{n^{1/r}} \geq x \Bigr) \notag \\
	& \geq \P^* \Bigl(\max \limits_{v \in D_{n-1}} \frac{M_1^v-S_v }{n^{1/r}} \geq x \Bigr) \cdot \P \Bigl( \frac{S_{n-1}}{n^{1/r}} \geq 0 \Bigr). \label{proof_theorem_BRW_case_x>x*_1}
	\end{align}
	The second probability on the right hand side of \eqref{proof_theorem_BRW_case_x>x*_1} converges to $\frac{1}{2}$ by the central limit theorem. It remains to estimate the
	first probability on the right hand side of \eqref{proof_theorem_BRW_case_x>x*_1}. Note that $(M_1^v - S_v)_{v \in D_{n-1}}$ are independent under $\P$.
	Therefore, using the inequality $1-(1-z)^y \geq zy(1-zy)$ valid for $z \in [0,1]$ and $y\geq 0$, we get for $c > 0$
	\begin{align} \label{proof_theorem_BRW_case_x>x*_2}
	& \quad \ \P^* \Bigl(\max \limits_{v \in D_{n-1}} \frac{M_1^v - S_v}{n^{1/r}} \geq x \Bigr) \notag \\
	& \geq \P^* \bigl(Z_{n-1} \geq c m^n \bigr) \cdot \biggl( 1- \Bigl(1- \P \Bigl(\frac{X}{n^{1/r}} \geq x \Bigr) \Bigr)^{c m^n} \biggr) \notag\\
	& \geq \P^* \bigl(W_{n-1} \geq cm \bigr)  \P \Bigl(\frac{X}{n^{1/r}} \geq x \Bigr) c m^n \Bigl(1-\P \Bigl(\frac{X}{n^{1/r}} \geq x \Bigr) c m^n \Bigr).
	\end{align}
	For the first factor on the right hand side of \eqref{proof_theorem_BRW_case_x>x*_2} it holds that $\liminf_{n \to \infty} \P^*(W_{ n-1} \geq cm ) \geq \P^*(W > cm )>0$ for $c$ small enough.
	Furthermore, the last term on the right hand side of \eqref{proof_theorem_BRW_case_x>x*_2} converges to 1 by Assumption~\ref{assumption_RW}.
	Combining \eqref{proof_theorem_BRW_case_x>x*_1} and \eqref{proof_theorem_BRW_case_x>x*_2} yields the lower bound.\\
\textbf{Case (2)}: $x < \alpha$ and $p(0)+p(1)>0$\\
Following the strategy explained in Section~\ref{sec:main}, we consider the situation where there are only $k^*$ particles at time $tn$ and one of them has an offspring with a large negative displacement while all others have no offspring. Afterwards, all particles move and reproduce as usual. For the lower bound, recall
\eqref{gammadef}, let $t \in [0, \gamma]$ and fix
	 $\varepsilon >0$.
We have
	\begin{align} \label{proof_theorem_BRW_case_x<x*_1}
		\P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr)
		& \geq \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \bigm\vert Z_{tn}=k^* \Bigr) \cdot \P^* (Z_{tn}=k^* ) \nonumber\\
		& \geq p(0)^{k^*-1} \P^* \Bigl(\frac{S_{tn}+M_{(1-t)n}}{n^{1/r}} \leq x \Bigr) \cdot \P^* (Z_{tn}=k^* ) \nonumber \\
		& \geq p(0)^{k^*-1} \P^* \Bigl(\frac{M_{(1-t)n}}{((1-t) n)^{1/r}} \leq \alpha + \varepsilon \Bigr) \cdot \P\Bigl(\frac{X_1}{n^{1/r}} \leq -\bigl( (\alpha+ \varepsilon)(1-t)^{1/r} -x \bigr) \Bigr) \nonumber \\
		& \quad \cdot \P(S_{tn-1} \leq 0) \cdot \P^* (Z_{tn}=k^* ).
	\end{align}
Since the first probability on the right hand side of \eqref{proof_theorem_BRW_case_x<x*_1} converges to 1 almost surely as $n \to \infty$ by
\eqref{linspeed}, we get
\begin{align*}
\P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr) \geq \exp \Bigl( -\Bigl[t \rho + \lambda_- \Bigl((\alpha+ \varepsilon)(1-t)^{1/r}-x \Bigr)^r \Bigr]n + o(n) \Bigr).
\end{align*}
Since this inequality holds for all $t \in [0, \gamma]$, letting $n \to \infty$ followed by $\varepsilon \to 0$ yields,
\begin{align*}
\liminf_{n \to \infty} \frac{1}{n} \log \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr) \geq \sup_{t \in [0, \gamma ]}\left( - H(x)\right) = -\inf_{t \in [0, \gamma]}  H(x).
\end{align*}
In what follows, we often omit integer parts for better readability. For the upper bound, recalling \eqref{gammadef}, assume $t < \gamma$ and define
\begin{equation*}
T_n = \inf \Bigl\{t \geq 0 \colon Z_{tn} \geq n^3 \Bigr\}
\end{equation*}
and for $\varepsilon_1>0$ introduce the set
\begin{equation*}
F=F(\varepsilon_1)= \Bigl\{\varepsilon_1, 2 \varepsilon_1, \ldots, \Bigl\lceil
\gamma \varepsilon_1^{-1} \Bigr\rceil \varepsilon_1 \Bigr\}.
\end{equation*}
By the definition of $T_n$ we then have
\begin{align} \label{proof_theorem_BRW_case_x<x*_2}
& \quad \ \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr) \nonumber\\
& \leq \P^* (T_n > \gamma ) + \sum_{t \in F} \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \bigm\vert T_n \in \bigl(t - \varepsilon_1, t \bigr] \Bigr) \P^* \bigl(T_n \in \bigl(t - \varepsilon_1, t \bigr] \bigr) \nonumber \\
& \leq \P^* \bigl(  Z_{\gamma n} \leq n^3 \bigr)+ \sum_{t \in F} \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \bigm\vert T_n \in \bigl(t - \varepsilon_1, t \bigr] \Bigr) \P^* (  Z_{(t- \varepsilon_1) n} \leq n^3).
\end{align}

Let $\varepsilon_2>0$ be such that $(1-t)^{1/r}(\alpha -\varepsilon_2) \geq x$ (which is possible since $t < \gamma$).
 Using Lemma~\ref{lemma_BRW_vs_ind_RW1} again,
\begin{align} \label{proof_theorem_BRW_case_x<x*_3}
& \quad \ \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \bigm\vert T_n \in \bigl(t - \varepsilon_1, t \bigr] \Bigr) \nonumber \\
& \leq  \P^* \biggl(\max_{v \in D_{tn}} \frac{S_{tn}+ M^v_{(1-t)n}}{n^{1/r}} \leq x \Bigm\vert T_n \in \bigl(t - \varepsilon_1, t \bigr] \biggr) \nonumber \\
& \leq \P \Bigl(\frac{S_{tn}}{n^{1/r}} \leq -\bigl((1-t)^{1/r}(\alpha- \varepsilon_2)-x \bigr) \Bigr)+ \P^* \Bigl(\frac{M_{(1-t)n}}{((1-t)n)^{1/r}} \leq \alpha - \varepsilon_2 \Bigr)^{n^2} \notag \\
& \quad \ + \P^* \bigl( Z_{tn} \leq n^2 \bigm\vert  T_n \in (t - \varepsilon_1, t] \bigr).
\end{align}
Note that we ignored all but one particle at time $tn$. Further note that the second probability on the right hand side of \eqref{proof_theorem_BRW_case_x<x*_3} converges to $0$ by \eqref{linspeed} and therefore the second term in \eqref{proof_theorem_BRW_case_x<x*_3} decays faster than exponentially in $n$. For the third term on the right hand side of \eqref{proof_theorem_BRW_case_x<x*_3},
\begin{align} \label{proof_theorem_BRW_case_x<x*_4}
\P^* \bigl( Z_{tn} \leq n^2 \bigm\vert  T_n \in (t - \varepsilon_1, t] \bigr)
& \leq \P^* \bigl(\exists k \in \N \colon Z_k \leq n^2 \bigm\vert Z_0=n^3 \bigr) \notag\\
& \leq \binom{n^3}{n^2} q^{n^3-n^2} \leq \exp \bigl( (n^3-n^2) \log q + 3n^2 \log n \bigr).
\end{align}
In the second inequality we used the fact that for the event we consider, at most $n^2$ of the initial $n^3$ Galton-Watson trees can survive. Note that the Galton-Watson trees coming from different initial particles are independent.

Combining \eqref{proof_theorem_BRW_case_x<x*_2}, \eqref{proof_theorem_BRW_case_x<x*_3} and \eqref{proof_theorem_BRW_case_x<x*_4} and letting $\varepsilon_1, \varepsilon_2 \to 0$, we conclude after a straightforward calculation
\begin{equation*}
\limsup_{n \to \infty} \frac{1}{n} \log \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr) \leq
 - \inf_{t \in [0,\gamma]} \Bigr\{t \rho + \lambda_- \bigl( \alpha(1-t)^{1/r} -x \bigr)^r \Bigr) \Bigr\} = -H(x).
\end{equation*}
\textbf{Case (3)}: $x < \alpha$ and $p(0)+p(1)=0$\\
Let $0< \varepsilon < \alpha - x$. Then we have
		\begin{align} \label{proof_theorem_BRW_case_x<x*_5}
			\P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr)
			& \geq \P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \bigm\vert Z_1=k^* \Bigr) \cdot \P^* (Z_1=k^* ) \nonumber\\
			& \geq \P^* \Bigl(\frac{X_1+M_{n-1}}{n^{1/r}} \leq x \Bigr)^{k^*} \cdot \P^* (Z_{1}=k^* ) \nonumber \\
			& \geq \P^* \Bigl(\frac{M_{n-1}}{ n^{1/r}} \leq \alpha + \varepsilon \Bigr)^{k^*} \cdot \P\Bigl(\frac{X_1}{n^{1/r}} \leq -\bigl( \alpha+ \varepsilon -x \bigr) \Bigr)^{k^*}
			\cdot \P^* (Z_{1}=k^* ).
		\end{align}
		Since the first probability on the right hand side of \eqref{proof_theorem_BRW_case_x<x*_5} converges to $1$ as $n \to \infty$ by \eqref{linspeed}, we get
		\begin{align*}
			\P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr) \geq p(k^*)\exp \Bigl( -  \lambda_-k^* (\alpha+ \varepsilon-x)^r n + o(1) \Bigr).
		\end{align*}
		Letting $\varepsilon \to 0$ finishes the proof.
				For the upper bound note that $4 \log k^* \geq 2$ and in particular $|D_{4 \log n}| \geq n^2$ a.s. Take $0< \varepsilon < \alpha-x$. Using Lemma~\ref{lemma_BRW_vs_ind_RW1} and the inequality $(a+b)^k \leq 2^{k-1}(a^k + b^k)$ valid for all $a,b>0$ and $k \in \N$, we get
		\begin{align*}
			\P^* \Bigl(\frac{M_n}{n^{1/r}} \leq x \Bigr)  & \leq \P^* \Bigl(\frac{M_{n-1}+X}{n^{1/r}} \leq x \Bigr)^{k^*} \leq
				\P^* \Bigl(\max_{v \in D_{4 \log n}} \frac{M^v_{n-1-4 \log n } + S_{4 \log n} + X}{n^{1/r}} \leq x \Bigr)^{k^*}  \\
& \leq \biggl(\P \Bigl(\frac{S_{4 \log n }}{n^{1/r}} \leq -(\alpha- \varepsilon-x ) \Bigr)+ \P^* \Bigl(\frac{M_{n-1- 4 \log n}}{n^{1/r}} \leq \alpha - \varepsilon \Bigr)^{n^2}	\biggr)^{k^*} \\
				& \leq 2^{k^*-1}\P \Bigl(\frac{S_{4 \log n}}{n^{1/r}} \leq -(\alpha- \varepsilon-x ) \Bigr)^{k^*}+ 2^{k^*-1}\P^* \Bigl(\frac{M_{n-1- 4 \log n}}{n^{1/r}} \leq \alpha - \varepsilon \Bigr)^{k^*n^2}.
	\end{align*}
Since the second probability on the right hand side  converges to $0$ as $n \to \infty$ by \eqref{linspeed}, we get, applying \eqref{sumasmax}
(with the random variables $-X_1, -X_2, \ldots $)
\begin{align*}
\P^* \Bigl(\frac{M_n}{n^{1/r}} \geq x \Bigr) \leq \exp \Bigl( - k^*\lambda_- (\alpha- \varepsilon-x)^r n + o(n) \Bigr).
\end{align*}
Letting $\varepsilon \to 0$ finishes the proof.
\end{proof}

\subsection*{Independent random walks} \label{proofs_ind_RW}

	\begin{proof}[Proof of Theorem \ref{theorem_ind_RW_Schröder}]
\textbf{Case (1)}: $x > \alpha$\\
For $z \in [0,1]$ and $y\geq 0$ we have $1-(1-z)^y \geq zy(1-zy)$. Following the strategy explained in Section~3, independence of the random walks and the aforementioned
		inequality yield
		\begin{align} \label{proof_thm_ind_RW_1}
			\P^* \Bigl( \frac{\tilde{M}_n}{n^{1/r}} \geq x \Bigr)
				& = \E^* \biggr[ 1- \Bigr(1- \P \Bigl( \frac{S_n}{n^{1/r}} \geq x \Bigr) \Bigr)^{Z_n} \biggr] \nonumber\\
				& \geq \P^* \Bigl(Z_n \geq \frac{1}{2} m^n \Bigr) \cdot  \biggr( 1- \Bigr(1- \P \Bigl( \frac{S_n}{n^{1/r}} \geq x \Bigr) \Bigr)^{\frac{1}{2} m^n} \biggr) \nonumber \\
				& \geq \P^* \Bigl(W_n \geq \frac{1}{2} \Bigr) \P \Bigl( \frac{S_n}{n^{1/r}} \geq x \Bigr) \frac{1}{2} m^n \Bigl( 1- \P \Bigl( \frac{S_n}{n^{1/r}} \geq x \Bigr) \frac{1}{2} m^n \Bigr).
		\end{align}
		By Lemma~\ref{lem:LDP_RW}, $\P \bigl( \frac{S_n}{n^{1/r}} \geq x \bigr) \frac{1}{2} m^n \to  0$ as $n \to \infty$, since $\log m < I(x)$.
		For the first factor on the right hand side of \eqref{proof_thm_ind_RW_1} we have
		$\liminf_{n \to \infty} \P^* (W_n \geq \frac{1}{2} ) \geq \P^*(W > \frac{1}{2}) >0$, since $\E^*[W]=\frac{1}{1-q}>1$ by Theorem~\ref{Lemma_GWP_martingale}. This establishes the estimate
		\begin{equation*}
			\P^* \Bigl( \frac{\tilde{M}_n}{n^{1/r}} \geq x \Bigr) \geq  \exp \bigl( - (I(x) - \log m )n + O(1) \bigr) = \exp \bigl( - (\lambda_+ x^r - \log m )n + O(1) \bigr).
		\end{equation*}
		For the upper bound, the Markov inequality yields, recalling \eqref{defcopy}
		\begin{align*}
			\P^* \Bigl( \frac{\tilde{M}_n}{n^{1/r}} \geq x \Bigr) & = \P^* \Bigl( \sum_{i=1}^{Z_n} \mathds{1}_{\{S_n^{(i)} \geq n^{1/r}x\}} \geq 1 \Bigr) \leq \P \Bigl( \frac{S_n}{n^{1/r}} \geq x \Bigr)\E^*[Z_n] \\
				& \leq \P \Bigl( \frac{S_n}{n^{1/r}} \geq x \Bigr) \frac{m^n}{1-q},
		\end{align*}
		which immediately implies the claim by the merit of Lemma~\ref{lem:LDP_RW}\\

 \textbf{Case (2)}: $0 < x < \alpha$\\
Since the rate function $I$ is strictly increasing on the interval $[0,\alpha]$, we can choose $\varepsilon>0$ such that $\varepsilon < I(x) < \log m - \varepsilon$. We prove the
	upper bound first. Using the inequality $1-y \leq e^{-y}$ and the third part of Lemma~\ref{lem:LDBP_S}, we have for $n$ large enough
	\begin{align*}
		\P^* \Bigl(\frac{\tilde{M}_n}{n^{1/r}} \leq x \Bigr)
		& = \E^* \biggl[\Bigl(1-\P \Bigl(\frac{S_n}{n^{1/r}} > x \Bigr)\Bigr)^{Z_n} \biggr] \leq \E^* \biggl[\exp \Bigl(-\P \Bigl(\frac{S_n}{n^{1/r}} > x \Bigr) Z_n \Bigr) \biggr]\\
		& \leq \P^* \Bigl(Z_n \leq e^{(I(x)+\varepsilon)n} \Bigr) + \exp \bigr(-e^{\varepsilon n +o(n)} \bigr)= \exp \Bigl(- \bigl( I^{\text{GW}}(I(x) +\varepsilon \bigr) n + o(n) \Bigr).
	\end{align*}
	Letting $\varepsilon \to 0$ gives the desired upper bound, since $I^{\text{GW}}$ defined in \eqref{def_I_GW_S} is continuous.
	The proof for the lower estimate is similar. Since $\P (\frac{S_n}{n^{1/r}} > x) < e^{-1}$ for $n$ large enough,  inequality $1-y>e^{-ey}$ for $y \in [0, e^{-1}]$
	yields
	\begin{align*}
		\P^* \Bigl(\frac{\tilde{M}_n}{n^{1/r}} \leq x \Bigr)
		& = \E^* \biggl[\Bigl(1-\P \Bigl(\frac{S_n}{n^{1/r}} > x \Bigr)\Bigr)^{Z_n} \biggr] \geq \E^* \biggl[\exp \Bigl(-e \cdot \P \Bigl(\frac{S_n}{n^{1/r}} > x \Bigr) Z_n \Bigr) \biggr]\\
		& \geq \P^* \Bigl(Z_n \leq e^{(I(x)-\varepsilon)n} \Bigr) \cdot \exp \bigr(-e^{-\varepsilon n +o(n)}  \bigr)= \exp \Bigl(- I^{\text{GW}}(I(x) - \varepsilon ) n + o(n) \Bigr).
	\end{align*}
	Letting $\varepsilon \to 0$ concludes the proof for $0<x<\alpha$.\\

\textbf{Case (3)}: $x \leq 0$\\
We first consider $x <0$. For the upper bound we have for $K \in \N$
	\begin{align}\label{eq:proof_thm_ind_RW_3}
		\P^* \Bigl(\frac{\tilde{M}_n}{n^{1/r}} \leq x \Bigr) &= \E^* \biggl[\P \Bigl(\frac{S_n}{n^{1/r}} \leq x \Bigr)^{Z_n} \biggr] \nonumber \\
		 	& \leq \sum_{k=1}^K \P \Bigl(\frac{S_n}{n^{1/r}} \leq x \Bigr)^k \P^*(Z_n=k) + \P \Bigl(\frac{S_n}{n^{1/r}} \leq x \Bigr)^K.
	\end{align}
	By the first part of Lemma~\ref{lem:LDBP_S}, the probability $\P(Z_n=k)$ is of order $\exp(-\rho n + o(n))$ for all $k \in A$ (defined in \eqref{def_A}) and $\P(Z_n=k)=0$ otherwise.
	Therefore, for all $K \in \N$,
	\begin{equation*}
		\limsup_{n \to \infty} \frac{1}{n} \log \P^* \Bigl(\frac{\tilde{M}_n}{n^{1/r}} \leq x \Bigr)  \leq  \max \bigl\{-(k^*I(x)+\rho), -KI(x) \bigr\}.
	\end{equation*}
	Hence, letting $K \to \infty$ proves the upper bound since $I(x)>0$ for $x<0$.  The lower bound can be established similarly:
	\begin{align*}
		\P^* \Bigl(\frac{\tilde{M}_n}{n^{1/r}} \leq x \Bigr)
		& = \E^* \biggl[\P \Bigl(\frac{S_n}{n^{1/r}} \leq x \Bigr)^{Z_n} \biggr] \geq \P \Bigl(\frac{S_n}{n^{1/r}} \leq x \Bigr)^{k^*} \cdot \P(Z_n=k^*)\\
		&= \exp \bigl( -(k^*I(x)+\rho)n +o(n) \bigr),
	\end{align*}
	which shows the lower bound. For $x=0$ the result follows from continuity of the rate function $I^\textnormal{ind}$ at 0.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{theorem_ind_RW_B}]
\textbf{Case (1)}: $x > \alpha$\\
	In this case one can use exactly the same arguments as in the proof of Theorem~\ref{theorem_ind_RW_Schröder}.\\

\textbf{Case (2)}: $0 \leq x < \alpha$\\
	Take $a \in (k^*, m)$ such that
	\begin{equation*}
		\log a = I(x) \frac{\log m - \log k^*}{\log m} + \log k^*.
	\end{equation*}
	Lemma~\ref{lem:LDBP_B} provides us with
	\begin{equation*}
		\log \left(- \log \P^*(Z_n\leq a^n)\right) \sim - n \log k^* \left(1  - \frac{\lambda_+x^r}{\log m}\right),
	\end{equation*}
	while the choice of $a$ guarantees
	\begin{equation*}
		\log \left(a^n \P(S_n\leq xn^{1/r})\right) \sim - n \log k^* \left(1  - \frac{\lambda_+x^r}{\log m}\right).
	\end{equation*}
	If we now recall the bounds established in the proof of Theorem~\ref{theorem_ind_RW_Schröder}, i.e.
	\begin{equation*}
		\P(Z_n\leq a^n) \exp ( -e a^n \P(S_n>x n^{1/r}) ) \leq \P^*(\tilde{M}_n \leq xn^{1/r})
	\end{equation*}
	and
	\begin{equation*}
		\P^*(\tilde{M}_n \leq xn^{1/r}) \leq \P(Z_n\leq a^n)  + \exp ( -a^n \P(S_n>x n^{1/r}) )
	\end{equation*}
	the claim will follow.\\

	\textbf{Case (3)}: $x < 0$\\
For the upper bound just write
	\begin{equation*}
		\P^*(\tilde{M}_n \leq xn^{1/r}) = \E^*[ \P(S_n\leq xn^{1/r})^{Z_n}] \leq \P(S_n\leq xn^{1/r})^{(k^*)^n}
	\end{equation*}
	which implies the claim. For the lower bound we have
	\begin{equation*}
		\P^*(\tilde{M}_n \leq xn^{1/r}) = \E^*[ \P(S_n\leq xn^{1/r})^{Z_n}] \geq \P(S_n\leq xn^{1/r})^{(k^*)^n} \P(Z_n=(k^*)^n)
	\end{equation*}
	since
	\begin{equation*}
		\log \P(Z_n=(k^*)^n) = \frac{(k^*)^n-1}{k^*-1} \log p(k^*)  = o(n(k^*)^n)
	\end{equation*}
	and the claim follows.
\end{proof}

\bibliographystyle{amsplain}


text:
{\bf Problem.} Let $\omega$ be a complex number such that $\omega^7 = 1$ and $\omega \ne 1.$  Let $\alpha = \omega + \omega^2 + \omega^4$ and $\beta = \omega^3 + \omega^5 + \omega^6.$  Then $\alpha$ and $\beta$ satisfy the quadratic
\[x^2 + ax + b = 0\]for some real numbers $a$ and $b.$  Enter the ordered pair $(a,b).$
{\bf Level.} Level 5
{\bf Type.} Intermediate Algebra
{\bf Solution.} From the equation $\omega^7 = 1,$ $\omega^7 - 1 = 0,$ which factors as
\[(\omega - 1)(\omega^6 + \omega^5 + \omega^4 + \omega^3 + \omega^2 + \omega + 1) = 0.\]Since $\omega \neq 1,$
\[\omega^6 + \omega^5 + \omega^4 + \omega^3 + \omega^2 + \omega + 1 = 0.\]We have that
\[\alpha + \beta = \omega + \omega^2 + \omega^4 + \omega^3 + \omega^5 + \omega^6 = -1.\]Also,
\begin{align*}
\alpha \beta &= (\omega + \omega^2 + \omega^4)(\omega^3 + \omega^5 + \omega^6) \\
&= \omega^4 + \omega^6 + \omega^7 + \omega^5 + \omega^7 + \omega^8 + \omega^7 + \omega^9 + \omega^{10} \\
&= \omega^4 + \omega^6 + 1 + \omega^5 + 1 + \omega + 1 + \omega^2 + \omega^3 \\
&= 2 + (\omega^6 + \omega^5 + \omega^4 + \omega^3 + \omega^2 + \omega + 1) \\
&= 2.
\end{align*}Then by Vieta's formulas, $\alpha$ and $\beta$ are the roots of $x^2 + x + 2 = 0,$ so $(a,b) = \boxed{(1,2)}.$

set_name: MATH


TITLE: Solution to a special differential equation
QUESTION [1 upvotes]: I am wondering whether the following differential equation can be solved.
$$\frac{\partial^{2}f}{\partial x^2}+ \frac{\partial^{2}f}{\partial y^2}+ \frac{\partial^{2}f}{\partial z^2}+ \alpha \frac{\partial f}{\partial t} = g,$$
where $f= f(x,y,z,t)$, $\alpha$ is a constant and $g=g(x,y,z,t)$ is a given continuous function. This equation is similar to the heat equation except for function $g$.
Is there any analytic solution for this kind of equation? If not, what is the appropriate numerical method to solve it?
Thanks for any hint!

REPLY [0 votes]: The equation is called inhomogeneous heat equation.
If and how a analytical solution can be obtained is depending on the domain $(x,y,z)\in\Omega$, the boundary conditions the initial data and $g$. Especially the following cases are noteworthy
$\Omega=\mathbb{R}^3$: Use the fourier transform in the space domain.
$\Omega$ is a cuboid: Use a separation ansatz for the space domain which (for suitable boundary conditions) results in a sum over sine and cosine functions.
Additionally, it is possible to solve via fundamental solution but depending on the domain it might be hard to achieve.
Hope that helps.


TITLE: Aysmptotic variance of an estimator of the parameter of an exponential distribution
QUESTION [0 upvotes]: There is a hint: you may use the expression for gamma function. But I don't know how to use it since it the sum of squares of exponential random variables. I computed the expression of the asymptotic variance in an extremely complicated way. The result is $\frac 1{2\theta^2}~$ but I don't know if its correct. Does anyone know how to use the hint? Thank you.

REPLY [0 votes]: The canonical way is to use the Delta method. However, it is sometimes possible to apply tricks that make calculations easier. And this is just such a case if you are familiar with the Slutsky's theorem.
Denote $\overline {X^2}=\frac{\sum_{i=1}^n X_i^2}{n}$
$$
\sqrt{n}\left(T_2-\frac1\theta\right)=\sqrt{n}\left(\sqrt{\frac12\overline {X^2}}-\frac1\theta\right)
$$
Multiply and divide by the conjugate:
$$
=\sqrt{n}\left(\frac12\overline{X^2}-\frac1{\theta^2}\right)\frac{1}{\sqrt{\frac12\overline {X^2}}+\frac1\theta} = \sqrt{n}\left(\overline{X^2}-\frac2{\theta^2}\right)\frac{1}{2\sqrt{\frac12\overline {X^2}}+\frac2\theta}
$$
$$
=\sqrt{n}\left(\overline{X^2}-\mathbb E[X_1^2]\right) \cdot \frac{1}{2T_2+\frac2\theta}
$$
Consider multipliers separately:
$$
\sqrt{n}\left(\overline{X^2}-\mathbb E[X_1^2]\right) \xrightarrow{\mathcal D_\theta} \mathcal N(0, \text{Var}(X_1^2)).
$$
$$
T_2 \xrightarrow{p} \frac1\theta,
\quad\text{ then } \quad
\frac{1}{2T_2+\frac2\theta}\xrightarrow{p}\frac\theta4.
$$
Next, Slutsky's theorem implies that the product converges in distribution to
$$
\mathcal N(0, \left(\frac\theta4\right)^2 \cdot \text{Var}(X_1^2)).
$$
You need to calculate $\text{Var}(X_1^2)$, and for it you definitelyneed to use Gamma function.


TITLE: Simple(?) question about divisibility of polynomials based on roots
QUESTION [2 upvotes]: Suppose $F$ a field and $A, B \subseteq F$ be finite subsets. Define $g(x) = \prod_{a \in A}(x- a)$ and $h(y) = \prod_{b \in B}(y - b)$. Then consider $f \in F[x, y]$ such that for every $(a, b) \in A \times B$ we have that $f(a, b) = 0$. Show that $f \in (g, h)$.

On the face of it this seems intuitive and obvious. But I'm somehow struggling with it. I think it's notational mostly. If it was just one variable $x$, and we have that $f(a) = 0$ for every $a \in A$ then I think it's fairly obvious that $g | f$ or $f = 0$. But when you add the second variable, I'm a tad confused how to make the argument work.
I hope it's not too silly of a question but I would appreciate help.

REPLY [1 votes]: Here's an elementary approach. By subtracting off multiples of $g$ and $h$, we may assume that $f$ is of degree less than $|A|$ in $x$ and less than $|B|$ in $y$. Writing $f = \sum_{i=0}^{|A|} p_i(y)x^i$, we see that if $f(x,b)\neq 0$, it cannot vanish at all elements in $A\times\{b\}$ for any fixed $b\in B$ because its degree is too low. Therefore $f(x,b)=0$ for all $b\in B$. But this means $p_i(b)=0$ for any $b\in B$, and every $p_i$ is of degree less than $|B|$, so each $p_i$ is actually zero as well and therefore $f\in (g,h)$.


text:
\section{Computations via Morse complex families}  \label{sec:MCF}
With Corollary \ref{cor:augmentationset} we have seen that for a compact Legendrian cobordism, $\Sigma$, the two versions of the
induced augmentation sets, $I_\Sigma^{\mathit{cell}}$ and $I_\Sigma$, defined via the cellular and ordinary versions of the LCH functor, $F_{\mathit{cell}}$ and  $F$, are equivalent invariants of $\Sigma$ (in a canonical way).
In this section, we focus on obtaining methods for computing $I_\Sigma^{\mathit{cell}}$.   Augmentations of the cellular DGA can be conveniently viewed as \emph{chain homotopy diagrams} (abbr. CHDs) which are certain homotopy commutative diagrams of chain complexes that have their form specified by the base and front projections of a Legendrian knot or surface.    CHDs for $2$-dimensional Legendrians were introduced in \cite{RuSu3} where they were shown to be closely connected with \emph{Morse complex families} (abbr. MCFs) which are combinatorial objects motivated by Morse theory.  In the 1-dimensional case, Morse complex families have been studied in the works of Henry and Rutherford, \cite{Henry, HenryRu1, HenryRu2}.  In particular, for a Legendrian knot, $\Lambda \subset J^1\R$, \cite{Henry, HenryRu2} establishes a bijection between $\aug(\Lambda)/{\sim}$ and equivalence classes of MCFs for $\Lambda$.

In Section \ref{sec:5-1}, we briefly review the correspondence between augmentations and CHDs in the context of compact Legendrian cobordisms. In Sections \ref{sec:5-2}-\ref{sec:5-3MCF}, we review MCFs and their connection with CHDs in the context of cobordisms.  In Section \ref{sec:5-4},
Proposition \ref{prop:MCFcomp} establishes a characterization of induced augmentation sets in terms of MCFs.   The section concludes in Section \ref{sec:Aform} with a discussion of $A$-form MCFs, as defined by Henry, that are particularly convenient for computing induced augmentation sets in explicit examples.

\subsection{Augmentations of the cellular DGA}  \label{sec:5-1} We briefly recall the definition of chain homotopy diagrams as in \cite{RuSu3}, and extend the definition to compact Legendrian cobordisms.

Let $\Lambda \subset J^1M$ be either a Legendrian knot or surface, i.e. $\dim(\Lambda) = \dim(M) = 1$ or $2$, equipped with a $\Z/\rho$-valued Maslov potential, $\mu$, and let $\mathcal{E}$ be a compatible polygonal decomposition for $\Lambda$.  We allow the case that $\Lambda$ is a compact Legendrian cobordism, and in this case  $\mathcal{E}$ also restricts to a polygonal decomposition for the boundary components of $\Lambda$.  To simplify the definition, when $\dim(\Lambda) = 2$ we assume
$\Lambda$ has no swallowtail points.  To each $d$-cell $e^d_\alpha \in \mathcal{E}$, $d=0,1,2$, we associate the $\Z/\rho$-graded $\Z/2$-vector space,
\[
V_\alpha = \mbox{Span}_{\Z/2}\{S^\alpha_p\},
\]
where $\{S^\alpha_p\}$ is the set of sheets of $\Lambda$ above $e^0_\alpha$.  (Recall that sheets are components of $\pi_x^{-1}(e_\alpha^d) \cap \Lambda$ not contained in a cusp edge.)
The  $\Z/\rho$-grading is specified on generators by the Maslov potential, i.e. in $V_\alpha$ the sheet $S^\alpha_p$ has grading
\[
|S^\alpha_p| = \mu(S^\alpha_p).
\]
The basis sets $\{S^\alpha_p\}$ are partially ordered by descending $z$-coordinates of sheets,
and we say that a linear map $f:V_\alpha \rightarrow V_\alpha$ is {\bf strictly upper triangular} if
\begin{equation}  \label{eq:strictly}
\langle f(S^\alpha_q), S^\alpha_p \rangle \neq 0 \quad \Rightarrow \quad z(S^\alpha_p) > z(S^\alpha_q).
\end{equation}
For $d' <d$, whenever $e^{d'}_\alpha$ appears along the boundary of $e^d_{\beta}$ (via a lifting $e^{d'}_\alpha \hookrightarrow D^{d} \stackrel{c_\beta}{\rightarrow} \overline{e^{d}_\beta}$ where $c_\beta$ is the characteristic map for $e^{d}_\beta$), there  is an inclusion of sheets $\iota: \{S^\alpha_p\} \hookrightarrow \{S^\beta_q \}$ where $\iota(S^\alpha_p)$ is the sheet above $e^d_\beta$ that limits to $S^\alpha_p$ as the $x$-coordinate approaches $e^{d'}_\alpha$.  This extends linearly to an inclusion $\iota: V_\alpha \hookrightarrow V_\beta$ such that
\[
V_\beta = \iota(V_\alpha) \oplus V_{\mathit{cusp}}
\]
where $V_{\mathit{cusp}}$ is spanned by those sheets above $e^{d}_\beta$ that limit to a cusp edge above $e^{d'}_\alpha$.

Suppose in addition that $V_\alpha$ is equipped with a differential $d:V_{\alpha} \rightarrow V_{\alpha}$ of degree $+1$ mod $\rho$  making $(V_{\alpha}, d)$ into a $\Z/\rho$-graded cochain complex.  Then, there is an associated {\bf boundary differential} $\widehat{d}:V_\beta \rightarrow V_\beta$ obtained by extending $d$ so that on $V_{\mathit{cusp}}$ we have $\widehat{d}(S^\beta_q) = S^\beta_p$ if the sheets $S^\beta_p$ and $S^\beta_q$ meet at a cusp above $e^{d'}_\alpha$ so that $S^\beta_p$ (resp. $S^\beta_q$) is the upper (resp. lower) sheet of the cusp.  Suppose next that $e^{d'}_\alpha$ is a $1$-cell and $f:(V_\alpha, d_-) \rightarrow (V_\alpha, d_+)$ is a chain map (for some pair of differentials $d_\pm$ on $V_\alpha$).  Then, there is an associated {\bf boundary map} $\widehat{f}:(V_\beta, \widehat{d}_-) \rightarrow (V_\beta, \widehat{d}_+)$ obtained by extending $f$ to be the identity on $V_\mathit{cusp}$.

\begin{definition} \label{def:CHD}
A {\bf $\rho$-graded chain homotopy diagram} (abbrv. {\bf CHD}) for $(\Lambda, \mu, \mathcal{E})$ is a triple $\mathcal{D} = (\{d_{\alpha}\}, \{f_\beta \}, \{K_\gamma\})$ satisfying:
\begin{enumerate}
\item For each $0$-cell, $e^0_\alpha$,
\[
d_\alpha: V_\alpha \rightarrow V_\alpha,  \quad d_\alpha^2=0
\]
 is a strictly upper triangular differential of degree $+1$ mod $\rho$ making $(V_\alpha, d_\alpha)$ into a cochain complex.
\item For each $1$-cell, $e^1_\beta$,
\[
f_\beta: (V_{\beta}, \widehat{d}_-) \rightarrow (V_{\beta}, \widehat{d}_+),  \quad f_\beta \circ \widehat{d}_- = \widehat{d}_+ \circ f_\beta
\]
is a chain isomorphism of degree $0$ mod $\rho$ such that $f_\beta - \mathit{id}$ is strictly upper triangular.  Here, $\widehat{d}_-$ and $\widehat{d}_+$ are the boundary differentials arising from the  initial and terminal vertices of $e^1_\beta$.
\item For each $2$-cell, $e^2_\gamma$,
\[
K_\gamma: (V_\gamma, \widehat{d}_0) \rightarrow (V_\gamma, \widehat{d}_1), \quad \widehat{f}_j^{\eta_j} \circ \cdots \circ \widehat{f}_1^{\eta_1} - \widehat{f}_{m}^{\eta_{m}} \circ \cdots \circ \widehat{f}_{j+1}^{\eta_{j+1}} = \widehat{d}_1 \circ K_\gamma + K_\gamma \circ \widehat{d}_0,
\]
is a homotopy operator of degree $-1$ mod $\rho$ between the compositions of boundary maps $\widehat{f}_j^{\eta_j} \circ \cdots \circ \widehat{f}_1^{\eta_1}$ and $\widehat{f}_{m}^{\eta_{m}} \circ \cdots \circ \widehat{f}_{j+1}^{\eta_{j+1}}$.
Here, $f_1, \ldots, f_j$ and $f_{j+1}, \ldots, f_{m}$ are the chain maps associated to the sequencess of edges that appear as we travel
the two paths around the boundary of $e^2_\gamma$ from the initial vertex, $v_0$, to the terminal vertex, $v_1$ (as in the definition of the differential for $\mathcal{A}(\Lambda, \mathcal{E})$);
the exponents $\eta_{i}$ are $\pm1$ depending on whether the orientation of the edge agrees or disagrees with the direction of the path from $v_0$ to $v_1$; and the maps $\widehat{d}_0$ and $\widehat{d}_1$ are the boundary differentials arising from $v_0$ and $v_1$.
\end{enumerate}

We write $\CHD_\rho(\Lambda, \mu, \mathcal{E})$ or simply $\CHD_\rho(\Lambda, \mathcal{E})$ for the set of all $\rho$-graded CHDs for $(\Lambda, \mu, \mathcal{E})$.
\end{definition}

\begin{remark}  When $\Lambda \subset J^1M$ is a Legendrian surface with swallowtail points, the same definition applies except that more  care needs to be taken in the construction of boundary differentials and boundary maps for cells that border swallowtail points.  See \cite[Section 3]{RuSu3}.  We will not need the precise details near swallowtail points in this article.
\end{remark}

Given a CHD $\mathcal{D} = (\{d_{\alpha}\}, \{f_\beta \}, \{K_\gamma\})$ for $(\Lambda, \mathcal{E})$, we can define an algebra homomorphism $\epsilon: \mathcal{A}(\Lambda, \mathcal{E}) \rightarrow \Z/2$ on the cellular DGA so that
\begin{align*}
\forall \, \mbox{ 0-cells $e^0_\alpha$, } & \epsilon(a^\alpha_{p,q}) = \langle d_\alpha( S^\alpha_q), S^\alpha_p \rangle & \mbox{ when $z(S^\alpha_p) > z(S^\alpha_q)$;}   \\
\forall \, \mbox{ 1-cells $e^1_\beta$, } & \epsilon(b^\beta_{p,q}) = \langle f_\beta( S^\beta_q), S^\beta_p \rangle & \mbox{ when $z(S^\beta_p) > z(S^\beta_q)$;} \\
\forall \, \mbox{ 2-cells $e^2_\gamma$, } & \epsilon(c^\gamma_{p,q}) = \langle K_\gamma( S^\gamma_q), S^\gamma_p \rangle & \mbox{ when $z(S^\gamma_p) > z(S^\gamma_q)$.}
\end{align*}
That is, the values of $\epsilon$ on generators associated to a given cell of $\mathcal{E}$ are the above diagonal matrix coefficients of the map associated to the cell by $\mathcal{D}$.

\begin{proposition} \label{prop:bijectaugchd} For any $(\Lambda, \mu, \mathcal{E})$ consisting of a $\rho$-graded Legendrian knot or surface (including cobordisms) equipped with a compatible polygonal decomposition $\mathcal{E}$, the above defines a bijection
\[
\aug_\rho(\Lambda, \mathcal{E})  \leftrightarrow \mathit{CHD}_\rho(\Lambda, \mathcal{E})
\]
between $\rho$-graded augmentations of the cellular DGA $\mathcal{A}(\Lambda, \mathcal{E})$ and $\rho$-graded CHDs.
\end{proposition}
\begin{proof}
This is proven in Proposition 3.7 of \cite{RuSu3} by checking that $\epsilon \circ \partial =0$ holds on the generators of a given cell if and only if the corresponding condition from (1)-(3) holds for that cell.  Because of the local nature of the proof, it applies equally well in the cobordism case.
\end{proof}

Note that when $\mathcal{E}$ is a compatible polygonal decomposition for a Legendrian surface, $\Sigma$, and $\mathcal{E}'$ is a CW sub-complex of $\mathcal{E}$ above which $\Sigma$ restricts to a Legendrian $\Lambda$, we get a {\bf restriction map} on CHDs
\[
\CHD_\rho(\Sigma, \mathcal{E}) \rightarrow \CHD_\rho(\Lambda, \mathcal{E}'), \quad \mathcal{D} \mapsto \mathcal{D}|_{\Lambda}
\]
by forgetting the data associated to cells not belonging to $\mathcal{E}'$.

\begin{proposition} \label{prop:chdCompute}
Let  $\Sigma: \Lambda_- \rightarrow \Lambda_+$ be a $\rho$-graded compact Legendrian cobordism and $\mathcal{E}$ be a compatible polygonal decomposition for $\Sigma$ restricting to decompositions $\mathcal{E}_\pm$ for $\Lambda_\pm$.
Then, using the bijection from Proposition \ref{prop:bijectaugchd} to identify augmentations and CHDs,
 the (cellular) augmentation map $i_{-}^* \times i_+^*: \aug_\rho(\Sigma, \mathcal{E}) \rightarrow \aug_\rho(\Lambda_-, \mathcal{E}_-) \times \aug_\rho(\Lambda_+, \mathcal{E}_+)$ associated to the immersed DGA map $F_{\mathit{cell}}(\Sigma)$ satisfies
\[
(i_-^*\times i_+^*)(\mathcal{D}) = (\mathcal{D}|_{\Lambda_-}, \mathcal{D}|_{\Lambda_+}).
\]
\end{proposition}
\begin{proof}
This is clear since the maps $ i_\pm:\mathcal{A}(\Lambda_\pm, \mathcal{E}_\pm) \hookrightarrow \mathcal{A}(\Sigma, \mathcal{E})$ are inclusions of sub-DGAs.
\end{proof}

\subsection{Morse complex families}  \label{sec:5-2}
We now review the definition of Morse complex families for Legendrian knots and surfaces, as in \cite{Henry, RuSu3}, allowing for the case of Legendrian cobordisms.  Morally, a Morse complex family can be thought of as a CHD with all chain maps and chain homotopies factored into elementary pieces.

\subsubsection{The 1-dimensional case} Let $(\Lambda, \mu) \subset J^1M$ be a $1$-dimensional $\rho$-graded Legendrian knot.
 Recall that we use the respective notations $\pi_x:J^1M \rightarrow M$ and $\pi_{xz}:J^1M \rightarrow M \times \R$ for the base and front projections.

\begin{definition}
A {\bf $\rho$-graded Morse complex family} (abbr. {\bf MCF}) for $(\Lambda, \mu)$
 is a pair $\mathcal{C} = (H, \{d_\nu\})$ consisting of the following items:
\begin{enumerate}
\item[(1)] A {\bf handleslide set} $H$ which is a finite collection of points in $M$ such that each $p\in H$ is equipped with lifts $u(p), l(p) \in \Lambda$ not belonging to cusp edges and satisfying $\pi_x(u(p)) = \pi_x(l(p)) = p$, $z(u(p)) > z(l(p))$, and such that $\mu(u(p)) = \mu(l(p))$.  We refer to $p \in H$ as a (formal) handleslide of $\mathcal{C}$ with upper and lower endpoints at $u(p)$ and $l(p)$.
\end{enumerate}
Denote by $\Lambda_{\mathit{sing}}$ the base projection of the singular set of $\pi_{xz}(\Lambda)$ (crossings and cusps), and let $\{R_\nu\}$ be the collection of path components of  $M \setminus (H \cup \Lambda_{\mathit{sing}})$.  Note that above each $R_\nu$, the sheets of $\Lambda$ are totally ordered by their $z$-coordinates, so they can be enumerated as
\[
S^\nu_1, \ldots, S^\nu_{n_\nu} \quad \mbox{with } z(S^\nu_1) > \cdots > z(S^\nu_{n_{\nu}}).
\]
We then have $\Z/\rho$-graded vector spaces $V(R_\nu) = \mbox{Span}_{\Z/2}\{S^\nu_i\}$, and we sometimes omit the superscript $\nu$ in the notation for sheets.

\begin{enumerate}
\item[(2)] The second piece of information defining an MCF is a collection of strictly upper triangular (as in (\ref{eq:strictly})) differentials $\{d_\nu\}$ of degree $+1$ mod $\rho$ making each $(V(R_\nu), d_\nu)$ into a $\Z/\rho$-graded cochain complex.
\end{enumerate}
Moreover, $H$ and $\{d_\nu\}$ are required to satisfy the following Axiom \ref{ax:1dim}.
\end{definition}

\begin{axiom} \label{ax:1dim}
Let $R_0$ and $R_1$ be connected components of $\pi_{x}(\Lambda) \setminus (H \cup \Lambda_{\mathit{sing}})$ that border each other at a  point $p \in H \cup \Lambda_{\mathit{sing}}$.

\begin{enumerate}
\item If $p \in H$ is a \emph{handleslide}  with upper endpoint $u(p) \in S_u$ and $l(p) \in  S_l$, then the handleslide map
\[
h_{u,l}( S_i) = \left\{\begin{array}{cr} S_i, & i \neq l, \\ S_u+S_l, & i = l, \end{array} \right.
\]
gives a chain isomorphism $h_{u,l} :(V(R_0), d_0)  \stackrel{\cong}{\rightarrow} (V(R_1), d_1)$.

\item If $p$ is the base projection of a \emph{crossing} between sheets $S_k$ and $S_{k+1}$, then the permutation map
\[
Q(S_k) = S_{k+1}, \,  Q(S_{k+1}) = S_k, \, Q(S_{i}) = S_i, i \notin \{k,k+1\}
\]
is a chain isomorphism, $Q :(V(R_0), d_0)  \stackrel{\cong}{\rightarrow} (V(R_1), d_1)$.
\item Suppose that $p$ is a \emph{cusp} point such that the two sheets of the cusp, $S^1_{k}$ and $S^1_{k+1}$, exist above $R_1$ but not above $R_0$.  Then, identifying sheets of $R_0$ and $R_1$ whose closures intersect at $p$ gives an inclusion $\iota: V(R_0) \hookrightarrow V(R_1)$ with
\[
V(R_1) = \iota(V(R_0)) \oplus V_{\mathit{cusp}}, \quad V_{\mathit{cusp}} = \mbox{Span}_{\Z/2}\{S^1_k, S^1_{k+1}\}.
\]
We require that $\iota \circ d_0 = d_1 \circ \iota$ and $d_1 S^1_{k+1} = S^1_k$, i.e. as a complex $(V(R_1), d_1)$ is the split extension of $(V(R_0), d_0)$ by $(V_{\mathit{cusp}}, d')$ where $d'$ maps the lower sheet of the cusp to the upper sheet of the cusp.
\end{enumerate}
\end{axiom}

\begin{remark} \label{rem:6-8}
\begin{enumerate}
\item The requirement in Axiom \ref{ax:1dim} (3) used here is stronger than in some other versions of the definition, eg. in \cite{Henry, HenryRu1, HenryRu2}. In the terminology of \cite{Henry}, with our definition we only consider Morse complex families with ``simple births and deaths''.  The collection of equivalence classes of MCFs is not affected by making this restriction; see \cite[Proposition 3.17]{Henry}.

\item If $ \Lambda \subset J^1 \R$, then the collection of differentials $\{d_\nu\}$ is uniquely determined by $\Lambda$ and $H$, since one can work from left to right and apply Axiom \ref{ax:1dim} to determine the $\{d_\nu\}$ inductively.  However, it should be noted that not every handleslide set $H$ for $\Lambda$ will produce an MCF.  For example, consider the case when $R_0$ and $R_1$ are seperated by a crossing point, and  $d_0$ has already been determined.  If $\langle d_0 S_{k+1}, S_k \rangle \neq 0$, then the differential $d_1 = Q \circ d_0 \circ Q^{-1}$ required by Axiom \ref{ax:1dim} (2) will not be strictly upper triangular.
\end{enumerate}
\end{remark}

In figures, we picture handleslides as vertical segments connecting $u(p)$ and $l(p)$ on the front projection of $\Lambda$.  When convenient, differentials $d_\nu$ may be indicated above $R_{\nu}$ by drawing a dotted arrow from $S_i$ to $S_j$ whenever $\langle d_\nu S_j, S_i \rangle =1$.  See for example Figures \ref{fig:Endpoints} and \ref{fig:8_21} below.

\subsubsection{The 2-dimensional case}

Consider a 2-dimensional $\rho$-graded compact Legendrian surface, $(\Sigma, \mu) \subset J^1M$ where $\dim M = 2$.
We allow for $\partial M \neq \emptyset$, but in this case require that $\Sigma$ is properly embedded, eg. $\Sigma$ could be a compact Legendrian cobordism in $J^1([0,1] \times \R)$ or $J^1([0,1] \times S^1)$.  We again use the notation $\Sigma_{\mathit{sing}} \subset M$ for the base projection of the singular set of $\pi_{xz}(\Sigma)$ (which now includes crossings, cusps, and swallowtail points).

\begin{definition}  \label{def:MCF2d}
A {\bf $\rho$-graded MCF} for $\Sigma$ is a triple $(H_0, H_{-1}, \{d_\nu\})$ consisting of:
\begin{enumerate}
\item A set of {\bf super-handleslide points}, $H_{-1} \subset \mathit{Int}(M)\setminus \Sigma_{\mathit{sing}}$, equipped with upper and lower endpoint lifts to $\Sigma$  satisfying $\mu(u(p)) = \mu(l(p))-1$ for all $p \in H_{-1}$.
\item A collection of {\bf handleslide arcs} which is an immersion $H_0: X \rightarrow M$ of a compact $1$-manifold, transverse to $\partial M$.
Aside from the exceptions at boundary points specified in Axiom \ref{ax:endpoints} below, we require that $H_0$ is transverse to $H_0 \cup \Sigma_{\mathit{sing}}$ and that the only self intersections are at transverse double points in $\mathit{Int}(M)$.  In addition, $H_0$ should be equipped with upper and lower endpoint lifts defined on the interior of $X$
\[
u,l:\mathit{Int}(X) \rightarrow \Sigma, \quad \pi_x\circ u = \pi_x \circ l = H_0,
\]
satisfying
\[
 u(s) > l(s) \quad \mbox{and} \quad \mu(u(s)) = \mu(l(s)) \quad \forall s \in \mathit{Int}(X).
\]
Endpoints of handleslide arcs must satisfy Axiom \ref{ax:endpoints} below.
\item A collection of differentials $\{d_\nu\}$ of degree $+1$ mod $\rho$ making each $(V(R_\nu), d_\nu)$ into a $\Z/\rho$-graded cochain complex where $\{R_\nu\}$ is the collection of path components of $M \setminus ( H_{-1} \cup H_0(X) \cup \Sigma_{\mathit{sing}})$.  Note that $H_{-1} \cup H_0(X) \cup \Sigma_{\mathit{sing}}$ is a stratified subset of $M$ whose $1$-dimensional strata are \emph{handleslide arcs}, \emph{crossing arcs}, and \emph{cusp arcs}.  For each such $1$-dimensional stratum, we require that the complexes $(V(R_0), d_0)$ and $(V(R_1), d_1)$ that appear adjacent to the stratum are related as in Axiom \ref{ax:1dim} (1)-(3).
\end{enumerate}
\end{definition}

Before stating Axiom \ref{ax:endpoints} we introduce some convenient terminology.  Above $M\setminus \Sigma_{\mathit{sing}}$ sheets of $\Sigma$ are locally labelled $S_1, \ldots, S_n$ with descending $z$-coordinate.  We will refer to a handleslide arc that has its upper and lower lift on sheets $S_i$ and $S_j$ as an {\bf $(i,j)$-handleslide}.  We caution that this terminology only applies locally since the labeling of upper and lower sheets of a handleslide arc may change when the arc passes through $\Sigma_{\mathit{sing}}$.  We use a similar terminology for super-handleslide points.

\begin{axiom} \label{ax:endpoints}
Endpoints of handleslide arcs can occur at transverse intersections of $H_0$ and $\partial M$.  All other endpoints of handleslide arcs occurring in the interior of $M$ are as specified in the following:
\begin{enumerate}
\item Suppose that $p \in M$ is a transverse double point for $H_0|_{\mathit{Int}(X)}$ where a $(u_1,l_1)$-handleslide arc crosses a $(u_2,l_2)$-handleslide arc.  If $l_1 = u_2$, then at $p$ there is a single endpoint of a $(u_1, l_2)$-handleslide arc.
\item Let $p \in H_0$ be a $(u,l)$-super-handleslide point,
 and fix some region $R_\nu$ bordering $p$.
\begin{itemize}
\item For every $i < u$ such that $\langle d_\nu S_u, S_i \rangle=1$, there is a single $(i,l)$-handleslide arc with an endpoint at $p$.
\item For every $l < j$ such that $\langle d_\nu S_j, S_l \rangle=1$, there is a single $(u,j)$-handleslide arc with an endpoint at $p$.
\end{itemize}
\item Let $p \in \Sigma_{\mathit{sing}}$ be the base projection of an upward swallowtail point, i.e. one where in the front projection the crossing arc appears below the third sheet that
that limits to the swallowtail point.  The two cusp arcs in $\Sigma_{\mathit{sing}}$ that meet at $p$ divide a small neighborhood $N \subset M$ of $p$ into halfs $N_-$ and $N_+$ above which $\Sigma$ has $(n-2)$ or $n$ sheets respectively.  Let $k$ be such that above $N_-$ (resp. above $N_+$)
the sheets that border the swallowtail point are numbered $S_k$ (resp. $S_k$, $S_{k+1}$, $S_{k+2}$) with
$S_{k+1}$ and $S_{k+2}$ meeting along the crossing arc, $c$, that ends at $p$ and is contained in $N_+$.
Let $(V(R_0), d_0)$ be the complex associated to the region, $R_0$, that borders $p$ on the same side as $N_-$.
\begin{itemize}
\item There are two $(k+1,k+2)$-handleslide arcs contained in $N_+$ and ending at $p$, one on each side of $c$.
\item For each $i<k$ such that  $\langle d_0S_k, S_i \rangle=1$ there is a $(i,k)$-handle slide arc in $N_+$ with endpoint at $p$.
\end{itemize}
When $p$ is a downward swallowtail, the requirement is symmetric.  The sheets $S_k$ in $N_-$ (resp. $S_k, S_{k+1}, S_{k+2}$ in $N_+$) correspond now to sheets $S_{l-2}$ in $N_-$ (resp. $S_{l}, S_{l-1}, S_{l-2}$).  There are now two $(l-2,l-1)$-handleslide arcs in $N_+$  on opposite sides of $c$ with endpoints at $p$, and for each $l-2< j$ with $\langle d_0 S_j, S_{l-2} \rangle=1$ there is an $(l, j+2)$-handleslide arc in $N_+$ with endpoint at $p$.
\end{enumerate}
\end{axiom}

The three types of endpoints for handleslide arcs are pictured in Figure \ref{fig:Endpoints}.

\begin{remark}
\begin{enumerate}
\item In Axiom \ref{ax:endpoints} (2), if the condition holds for some region $R_\nu$ bordering $p$, then it holds for every region that borders $p$.
\item In Axiom \ref{ax:endpoints} (3), in a neighborhood of a swallowtail point $p$, assume that a differential $d_0$ has been assigned to the region $R_0$ that borders $p$ in $N_-$.  Then, as long as handleslide arcs are placed in $N_+$ as specified by the axiom, there is always a unique way to assign differentials to regions in $N_+$ to produce an MCF near $p$.

\item See \cite[Section 6.1]{RuSu3} for a further discussion of constructions of MCFs.
\end{enumerate}
\end{remark}

\begin{figure}

\quad

\quad

\labellist
\small
\pinlabel (1) [r] at -16 64
\tiny
\pinlabel $(m,j)$ [b] at 24 116
\pinlabel $(i,j)$ [b] at 68 124
\pinlabel $(i,m)$ [b] at 136 116
\small
\pinlabel $S_i$ [l] at 586 112
\pinlabel $S_m$ [l] at 586 64
\pinlabel $S_j$ [l] at 586 16
\pinlabel $x_2=a$ [l] at 146 16
\pinlabel $x_2=b$ [l] at 146 72
\endlabellist
\centerline{\includegraphics[scale=.5]{Images/Endpoints1}}

\quad

\quad

\quad

\labellist
\small
\pinlabel (2) [r] at -16 64
\pinlabel $S_{u}$ [l] at 586 68
\pinlabel $S_{l}$ [l] at 586 34
\pinlabel $x_2=a$ [l] at 146 26
\pinlabel $x_2=b$ [l] at 146 82
\endlabellist

\centerline{\includegraphics[scale=.5]{Images/Endpoints2}}

\quad

\quad

\quad

\labellist
\small
\pinlabel (3) [r] at -16 152
\pinlabel $x_1$ [t] at 32 -2
\pinlabel $x_2$ [r] at -2 32
\pinlabel $x_1$ [t] at 272 -2
\pinlabel $z$ [r] at 238 32
\pinlabel $x_2=a$ [l] at 146 74
\pinlabel $x_2=b$ [l] at 146 186

\endlabellist

\centerline{\includegraphics[scale=.5]{Images/Endpoints3}}

\caption{The three possible endpoints for handleslide arcs specified by Axiom \ref{ax:endpoints} (1)-(3).    The left column depicts the base projection (to $M$) of $H_0$ (in red), $H_{-1}$ (a green star) and $\Sigma_{\mathit{sing}}$, (in blue).
The center and right column depict slices of the front projection, $\pi_{xz}(\Sigma)$, at $x_2=a$ and $x_2=b$ with dotted black arrows  from $S_i$ to $S_j$ used to indicate when $\langle d S_j, S_i \rangle = 1$.  In (3), a downward swallowtail point is pictured.
}
\label{fig:Endpoints}
\end{figure}

Note that when $\Sigma$ and $M$ are $2$-dimensional and have boundary, an MCF $\mathcal{C}$ for $\Sigma$ restricts to an MCF for the $1$-dimensional Legendrian $\Sigma|_{\partial M} \subset J^1(\partial M)$.

\begin{definition} \label{def:MCFequiv} Let $\mathcal{C}_0$ and $\mathcal{C}_1$ be two MCFs for a 1-dimensional Legendrian knot $\Lambda \subset J^1M$.  We say that $\mathcal{C}_0$ and $\mathcal{C}_1$ are {\bf equivalent} if there exists an MCF $\mathcal{C}$ for the product cobordism $j^1(1_{[0,1]}\cdot\Lambda)  \subset J^1([0,1]\times M )$ such that $\mathcal{C}|_{\{0\} \times M} = \mathcal{C}_0$ and $\mathcal{C}|_{\{1\} \times M} = \mathcal{C}_1$.
\end{definition}

\begin{remark} \label{rem:6-13}
The statement of Definition \ref{def:MCFequiv} is slightly different than the definition of equivalence in \cite{Henry, HenryRu1, HenryRu2}.  These earlier works did not consider MCFs for $2$-dimensional Legendrians and instead present a collection of elementary moves on 1-dimensional MCFs with two MCFs $\mathcal{C}_0$ and $\mathcal{C}_1$ declared to be equivalent if they can be related by a sequence of elementary moves.
 The two versions of the definitions are equivalent, since the elementary moves simply describe the bifurcations that occur along the slices, $\mathcal{C}|_{\{t\} \times M}$, of a generic $2$-dimensional MCF $\mathcal{C}$ for $j^1(1_{[0,1]}\cdot \Lambda)$ as $t$ increases from $0$ to $1$.  For instance, as numbered in \cite[Section 4.3]{HenryRu1},  Move 1 corresponds to passing a critical point of $t \circ H_0$; Moves 2-6 correspond to a transverse self intersection of $H_0$ with Move 6 demonstrating the handleslide endpoints required by Axiom \ref{ax:endpoints} (1); Moves 7, 8, and 10 are transverse intersections of $H_0$ with the base projection of a crossing arc of $j^1(1_{[0,1]}\cdot \Lambda)$; Moves 9 and 11 are transverse intersections of $H_0$ and the base projection of a cusp arc; and Move 15 corresponds to passing a super-handleslide point.  The Moves 12-14 do not occur in our case since we only consider MCFs with ``simple births and deaths'', and this does not affect the resulting equivalence classes.  Indeed, when two such MCFs with only ``simple births and deaths'' are related by a sequence of the Moves 1-15, possibly passing through some MCFs with non-simple births or deaths, we can always arrive at an alternate sequence of moves avoiding non-simple cusps by treating the implicit handleslides discussed in \cite{HenryRu1} as explicit handleslides located near a cusp.  See \cite[Proposition 3.17]{Henry}.
\end{remark}

\subsection{MCFs and CHDs}  \label{sec:5-3MCF}

Suppose now that $(\Lambda, \mu) \subset J^1M$ is a $\rho$-graded Legendrian knot or surface equipped with a  compatible polygonal decomposition $\mathcal{E}$.

\begin{definition} An MCF $\mathcal{C}$ will be called {\bf nice} with respect to $\mathcal{E}$ if the handleslide sets (including super-handleslides when $\mathit{dim}(M) = 2$) are transverse all vertices and edges of $\mathcal{E}$ except at the endpoints of handleslide arcs that occur at swallowtail points as specified by Axiom \ref{ax:endpoints} (3).  Moreover\footnote{This technical requirement will not be relevant to the later discussion in the present article.  It is included in order for Proposition \ref{prop:CHD} to be true.  See \cite{RuSu3}.}, in a neighborhood of each upward (resp. downward) swallowtail point, $s_0$, all of the $(i,k)$- (resp. $(l,j+2)$-) handleslide arcs specified by Axiom \ref{ax:endpoints} (3) appear on the $S$ side of the crossing arc ending at $s_0$.
Denote by $\MCF_\rho(\Lambda, \mathcal{E})$ the set of all nice $\rho$-graded MCFs for $(\Lambda, \mu, \mathcal{E})$.
\end{definition}

Any MCF can be made nice after a perturbation of the handleslide sets.  In particular, when $\dim \Lambda =1$,  for any $\mathcal{E}$, the set of equivalence classes of nice MCFs, $\MCF_\rho(\Lambda, \mathcal{E})/{\sim}$, coincides with the set of equivalence classes of arbitrary MCFs for $\Lambda$.

\subsubsection{From MCF to CHD: 1-dimensional case}  Assume now that $\Lambda \subset J^1M$ is $1$-dimensional and that $\mathcal{C}$ is a $\rho$-graded MCF for $\Lambda$ that is nice with respect to $\mathcal{E}$.  We use  $\mathcal{C}$ to produce a $\rho$-graded CHD, $\Phi(\mathcal{C}) = (\{d_\alpha\}, \{f_\beta \})$, for $(\Lambda, \mathcal{E})$  as follows:

\begin{itemize}
\item For each $0$-cell, $e^0_\alpha \in \mathcal{E}$, by identifying sheets whose closures intersect we obtain an isomorphism
\[
V(e^0_\alpha) \cong V(R_\nu)
\]
where $R_\nu$ is a region that either contains $e^0_\alpha$ or is adjacent to $e^0_\alpha$.  (If $e^0_\alpha$ is at a cusp of $\Lambda$, then $R_\nu$ must be taken to be the bordering region above which the cusp sheets do not exist.)  We define $d_\alpha: V(e^0_\alpha) \rightarrow V(e^0_\alpha)$ to agree with $d_\nu$ under this isomorphism.  (This is independent of the choice of $R_\nu$ by Axiom \ref{ax:1dim} (2).)

\item For each $1$-cell,  $e^1_\beta$, let $p_1, \ldots, p_s \in H$, $s\geq 0$, be the sequence of handleslide points of $\mathcal{C}$ that appear when $e^1_\beta$ is traversed according to its orientation.  Let $u_i$ and $l_i$ be the indices above $e^1_\beta$ of the sheets that contain the upper and lower lift of $p_i$ respectively, and put
\begin{equation} \label{eq:betadef}
f_\beta: V(e^1_\beta) \rightarrow V(e^1_\beta), \quad f_\beta = h_{u_s,l_s} \circ \cdots \circ h_{u_1,l_1}
\end{equation}
where the $h_{u_i,l_i}$ are the handleslide maps from Axiom \ref{ax:1dim} (1).
\end{itemize}
\begin{proposition} \label{prop:surjective} The construction defines a $\rho$-graded CHD, $\Phi(\mathcal{C}) = (\{d_\alpha\}, \{f_\beta\})$, for $(\Lambda, \mathcal{E})$.  Moreover, $\Phi$ gives a surjective map from $\MCF_\rho(\Lambda, \mathcal{E})$ to $\CHD_\rho(\Lambda, \mathcal{E})$.
\end{proposition}
\begin{proof}
To verify that $f_\beta: (V(e^1_\beta), \widehat{d}_-) \rightarrow (V(e^1_\beta), \widehat{d}_+)$ is a chain map with respect to the boundary differentials arising from the vertices at the ends of $e^1_\beta$, use Axiom \ref{ax:1dim}.  Or, see \cite[Section 5]{RuSu3}.  For surjectivity, recall that the standard row reduction algorithm shows that any upper triangular map with $1$'s on the main diagonal can be factored into a product of handleslide maps.
\end{proof}

We will see in Proposition \ref{prop:bijectMCFAug} below that $\Phi$ is bijective on equivalence classes.

\subsubsection{MCFs and CHDs in 2-dimensions}

Now, let $(\Sigma, \mu, \mathcal{E})$  be a Legendrian surface in $J^1M$ (allowing for $\Sigma$ and $M$ to have non-empty boundary) with Maslov potential and polygonal decomposition.  The construction from Proposition \ref{prop:surjective} applies more generally to produce from a nice MCF $\mathcal{C} \in \MCF_\rho(\Sigma, \mathcal{E})$ an assignment of differentials and chain maps to the $0$- and $1$-cells of $\mathcal{E}$.
\begin{itemize}
\item Given $e^0_\alpha$, choose any bordering region $R_\nu$ whose sheets are in bijection with those of $e^0_\alpha$ and use $V(e^0_\alpha) \cong V(R_\nu)$ to define $d_\alpha$ via $d_\nu$.
\item Given $e^1_\beta$, push $e^1_\beta$ slightly\footnote{ As a technical requirement, when $e^1_\beta$ has an endpoint at a swallowtail point, $s_0$, the endpoint of the shifted version of $e^1_\beta$ should not be seperated (locally) from $e^1_\beta$ by any of the handleslide arcs with endpoints at $s_0$. See \cite{RuSu3}.}  into the interior of a neighboring $2$-cell whose sheets are in bijection with the sheets of $e^1_\beta$, and again define $f_\beta$ as a composition of handleslide maps as in (\ref{eq:betadef}).
\end{itemize}
Note that Propositions 5.2 and 5.3 of \cite{RuSu3} show that the $d_\alpha$ and $f_\beta$ are well defined.

\begin{definition}
Let $\mathcal{C} = (H_{-1}, H_0, \{d_\nu\}) $ and $\mathcal{D}= (\{d_\alpha\}, \{f_\beta\}, \{K_\gamma\})$ be a nice MCF and a CHD for $(\Sigma, \mathcal{E})$ where $\dim\Sigma = 2$.  We say that $\mathcal{C}$ and $\mathcal{D}$ {\bf agree on the $1$-skeleton} if the $\{d_\alpha\}$ and $\{f_\beta\}$ are related to $\mathcal{C}$ as in the above construction.
\end{definition}

In the case where $\partial \Sigma = \emptyset$, (1) and (2) of the following proposition appear as Proposition 6.4 and Proposition 5.5 of \cite{RuSu3}.

\begin{proposition} \label{prop:CHD}  Let $(\Sigma, \mu, \mathcal{E})$ be a $\rho$-graded Legendrian surface possibly with boundary equipped with  a   compatible polygonal decomposition.
\begin{enumerate}
\item Given any nice $\rho$-graded MCF $\mathcal{C}$ for $(\Sigma, \mathcal{E})$, there exists a $\rho$-graded CHD $\mathcal{D}$ for $(\Sigma, \mathcal{E})$ that agrees with $\mathcal{C}$ on the $1$-skeleton.
\item Given any  $\rho$-graded CHD $\mathcal{D}$ for $(\Sigma, \mathcal{E})$, there exists a nice $\rho$-graded MCF $\mathcal{C}$ for $(\Sigma, \mathcal{E})$  that agrees with $\mathcal{D}$ on the $1$-skeleton.
\end{enumerate}
Moreover, in (2) $\mathcal{C}$ can be constructed to extend any given nice MCF $\mathcal{C}_X$ defined above a $1$-dimensional (CW) sub-complex $X \subset \mathcal{E}$ that agrees with $\mathcal{D}$ on $X$.
\end{proposition}

\begin{proof}  There is no issue with allowing $\partial \Sigma \neq \emptyset$ in the proofs of (1) and (2) from \cite{RuSu3}.  To see this, and to verify the statement about $\mathcal{C}_X$, we briefly review the proofs.
In proving either (1) or (2), the construction starts by defining the required $\mathcal{D}$ or $\mathcal{C}$ above the $1$-skeleton.  [For (2), start with $\mathcal{C}_X$ above $X$, and then  assign handleslide marks along all remaining edges by arguing as in the proof  of surjectivity of $\Phi$ in Proposition \ref{prop:surjective}.]  Then, the proofs in \cite{RuSu3} show that (once additional handleslide endpoints are placed at swallowtail points as specified by Axiom \ref{ax:endpoints} (3)) $\mathcal{C}$ can be extended over a 2-cell if and only if $\mathcal{D}$ can.
\end{proof}

\subsection{Bijection between equivalence classes of MCFs and augmentations}  \label{sec:5-4}

\begin{proposition} \label{prop:bijectMCFAug}  Given $(\Lambda, \mu, \mathcal{E})$ with $\Lambda \subset J^1M$ and $\dim \Lambda =1$,  the map $\Phi: \mathit{MCF}_\rho(\Lambda, \mathcal{E}) \rightarrow \CHD_\rho(\Lambda, \mathcal{E}) = \aug_\rho(\Lambda, \mathcal{E})$ from Proposition \ref{prop:surjective} induces a bijection
\[
\widehat{\Phi} :  \mathit{MCF}_\rho(\Lambda)/{\sim} \rightarrow \CHD_\rho(\Lambda, \mathcal{E})/{\sim} = \aug_\rho(\Lambda, \mathcal{E})/{\sim}.
\]
\end{proposition}
In the statement, the equality $\CHD_\rho(\Lambda, \mathcal{E}) = \aug_\rho(\Lambda, \mathcal{E})$ is from Proposition \ref{prop:bijectaugchd}, and under this equality the equivalence relation  on $\CHD_\rho(\Lambda, \mathcal{E})$ is  DGA homotopy.

\begin{proof}  Let $\mathcal{E}'$ denote the product polygonal decomposition for $j^1(1_{[0,1]}\cdot \Lambda)$ as constructed in Section \ref{sec:4-3}.

\begin{lemma} \label{lem:CHDhomotopy} Two CHDs $\mathcal{D}_0$ and $\mathcal{D}_1$ for $(\Lambda, \mathcal{E})$ correspond to homotopic augmentations if and only if there exists a CHD $\mathcal{D}$ for $(j^1(1_{[0,1]}\cdot \Lambda), \mathcal{E}')$ such that $\mathcal{D}|_{\{0\} \times \Lambda} = \mathcal{D}_0$ and $\mathcal{D}|_{\{1\} \times \Lambda} = \mathcal{D}_1$.
\end{lemma}
\begin{proof} Using the computation of $\mathcal{A}(j^1(1_{[0,1]}\cdot \Lambda), \mathcal{E}')$ in terms of $\mathcal{A}(\Lambda, \mathcal{E})$ found in Proposition \ref{prop:alg01}, we see that, in the notations found there, two augmentations $\epsilon_0$ and $\epsilon_0$ for $\Lambda$ are DGA homotopic if and only if there exists a single augmentation
\[
\alpha:\mathcal{A}(j^1(1_{[0,1]}\cdot \Lambda), \mathcal{E}') \rightarrow \Z/2
\]
 such that $i_0^*\alpha = \epsilon_0$ and $i_1^*\alpha = \epsilon_1$.  The statement of the lemma is simply the translation of this statement to CHDs resulting from the bijection from Proposition \ref{prop:bijectaugchd}.
\end{proof}

To complete the proof of Proposition \ref{prop:bijectMCFAug}, we need show that for any $\mathcal{C}_0, \mathcal{C}_1 \in \mathit{MCF}_\rho(\Lambda)$ we have $\mathcal{C}_0 \sim \mathcal{C}_1$ if and only if $\epsilon_0 \simeq \epsilon_1$ where $\epsilon_i$ is the augmentation corresponding to $\Phi(\mathcal{C}_0)$ under the bijection from Proposition \ref{prop:bijectaugchd}.
Suppose that $\mathcal{C}_0 \sim \mathcal{C}_1$.  Then, there exists an MCF, $\mathcal{C}$, for $j^1(1_{[0,1]}\cdot \Lambda)$  that restricts to $\mathcal{C}_i$ on $\{i\}\times M$ for $i=0,1$.  Applying Proposition \ref{prop:CHD} (1), we obtain a CHD $\mathcal{D}$ on $\Lambda \times [0,1]$ that agrees with $\mathcal{C}$ on the $1$-skeleton.  In particular, $\mathcal{D}|_{\{i\} \times \Lambda} = \Phi(\mathcal{C}_i)$, so Lemma \ref{lem:CHDhomotopy} implies that $\Phi(\mathcal{C}_0) \sim \Phi(\mathcal{C}_1)$.

Conversely, suppose that $\Phi(\mathcal{C}_0) \sim \Phi(\mathcal{C}_1)$.  Then, there exists a CHD $\mathcal{D} \in \CHD_\rho(j^1(1_{[0,1]}\cdot\Lambda), \mathcal{E}')$ restricting to $\Phi(\mathcal{C}_i)$ on $\{i\}\times\Lambda$, $i=0,1$.  Using the relative statement at the end of Proposition \ref{prop:CHD}, there is an MCF $\mathcal{C}$ for $j^1(1_{[0,1]} \cdot\Lambda)$ restricting to $\mathcal{C}_i$ on $\{i\}\times \Lambda$.  Thus, $\mathcal{C}_0 \sim \mathcal{C}_1$.

\end{proof}

The bijection between equivalence classes of MCFs and augmentations leads to the following characterization of the (cellular) induced augmentation set of a compact Legendrian cobordism (see Section \ref{sec:AugSet} for the definition).
\begin{proposition}  \label{prop:MCFcomp}  Let $\Sigma \subset J^1([0,1]\times M)$ be a compact $\rho$-graded Legendrian cobordism from $(\Lambda_0, \mathcal{E}_0, \mu_0)$ to $(\Lambda_1, \mathcal{E}_1, \mu_1)$.
Using the bijection $\widehat{\Phi}:\mathit{MCF}_\rho(\Lambda)/{\sim} \stackrel{\cong}{\rightarrow} \aug_\rho(\Lambda, \mathcal{E})/{\sim}$, the induced augmentation set
\[
I^\comp_\Sigma \subset \aug_\rho(\Lambda_0, \mathcal{E}_0)/{\sim} \times \aug_\rho(\Lambda_1, \mathcal{E}_1)/{\sim}
\]
 viewed as a subset
\[
I^{\mathit{MCF}}_\Sigma \subset \mathit{MCF}_\rho(\Lambda_0, \mathcal{E}_0)/{\sim} \times \mathit{MCF}_\rho(\Lambda_1, \mathcal{E}_1)/{\sim}
\]
satisfies
\[
I^{\mathit{MCF}}_\Sigma = \left\{ ([\mathcal{C}|_{\Lambda_0}], [\mathcal{C}|_{\Lambda_1}]) \, \middle|\, \mathcal{C} \in \MCF_\rho(\Sigma) \right\}.
\]
\end{proposition}

\begin{proof}
From Proposition \ref{prop:chdCompute},
under the identification $\mathit{CHD}_\rho(\Lambda_i,\mathcal{E}_i)/{\sim} = \aug_\rho(\Lambda_i, \mathcal{E}_i)/{\sim}$ we have
\[
I^\comp_\Sigma = \left\{ ([\mathcal{D}|_{\Lambda_0}], [\mathcal{D}|_{\Lambda_1}]) \, \middle|\,  \mathcal{D} \in \CHD(\Sigma, \mathcal{E}) \right\}.
\]
Then, the result follows easily using Proposition \ref{prop:CHD}.
\end{proof}

\subsection{$A$-form MCFs}\label{sec:Aform} From
Proposition \ref{prop:MCFcomp} and Corollary \ref{cor:LegInv}, we see that $I^{\mathit{MCF}}_\Sigma$ is invariant of $\Sigma$ up to Legendrian isotopy rel. $\partial \Sigma$.  Moreover, $I^{\mathit{MCF}}_\Sigma$  is equivalent in a canonical way to both the cellular induced augmentation set $I^{\mathit{cell}}_\Sigma$ and, via Corollary \ref{cor:augmentationset}, to the induced augmentation set
$I_{\Sigma}$ of the conical version of $\Sigma$, $G_{\mathit{std}}(\Sigma)$.
 For computing $I^{\mathit{MCF}}_\Sigma$ in explicit examples, it is convenient to have an efficient characterization of the sets, $\mathit{MCF}_\rho(\Lambda)/{\sim}$,
not requiring the cellular DGA which often has a large number of generators.
For Legendrian links in $J^1\R$, work of Henry \cite{Henry, HenryRu2}, which we now review,  gives an explicit bijection $\MCF_\rho(\Lambda)/{\sim} \leftrightarrow \aug_\rho(\Lambda_\res)/{\sim}$ where $\Lambda_\res$ is the Ng resolution of $\Lambda$.  Recall that the DGA $\mathcal{A}(\Lambda_\res)$ has generators in bijection with the crossings and right cusps of the front projection of $\Lambda$; see \cite[Section 2]{NgCompute}.

\begin{definition}[\cite{Henry}] \label{def:Aform}
A $\rho$-graded MCF $\mathcal{C}$ for a Legendrian link $\Lambda \subset J^1\R$ is in {\bf $A$-form} if its handleslides occur only in the following locations:
\begin{enumerate}
\item Handleslides connecting the two crossing strands appear immediately to the left of {\it some subset} of the crossings of $\pi_{xz}(\Lambda)$.
\item In the case $\rho=1$, handleslides connecting the two strands that meet at a right cusp appear immediately to the left of {\it some subset} of the right cusps of $\pi_{xz}(\Lambda)$.
\item Near a right cusp,  any number of additional handleslides may appear connecting the upper (resp. lower) strand of the right cusp to a strand above (resp. below) the right cusp.  These handleslides are located to the right of the handleslide from (2), if it exists.
\end{enumerate}
See Figure \ref{fig:Aform}.
\end{definition}

\labellist
\small
\endlabellist

\begin{figure}
\centerline{ \includegraphics[scale=.6]{Images/Aform} }
\caption{ The allowed locations for handleslides in an $A$-form MCF. }
\label{fig:Aform}
\end{figure}

\begin{remark}
The definition appears slightly different from that found in \cite{Henry, HenryRu2} as the handleslides from (3) are implicit handleslides in these references; see Remarks \ref{rem:6-8} (1) and \ref{rem:6-13}. Moreover, an $A$-form MCS is uniquely determined by its handleslides of type (1) and (2), since the handleslides of type (3) are determined by the form of the complexes $(R_\nu, d_\nu)$ near right cusps.
\end{remark}

Given an $A$-form MCF, $\mathcal{C}$, for $\Lambda \subset J^1\R$ we can define an algebra homomorphism
\[
\epsilon_{\mathcal{C}}: \mathcal{A}(\Lambda_\mathit{res}) \rightarrow \Z/2
\]
where for each crossing or right cusp $b_i \in \mathcal{A}(\Lambda_\mathit{res})$ we set $\epsilon_\mathcal{C}(b_i)$ to be $1$ (resp. $0$) if a handleslide connecting the two strands of the crossing or cusp appears (resp. does not appear) to the left of $b_i$.

\begin{proposition}[\cite{Henry, HenryRu2}] \label{prop:Aform}
For any $\Lambda \subset J^1\R$, the correspondence $\mathcal{C} \mapsto \epsilon_{\mathcal{C}}$ defines a surjective map from the set of $\rho$-graded $A$-form MCFs for $\Lambda$ to $\aug_\rho(\Lambda_\res)$.  Moreover, this induces a bijection
\[
\mathit{MCF}_\rho(\Lambda)/{\sim} \stackrel{\cong}{\rightarrow} \aug_\rho(\Lambda_\res)/{\sim}.
\]
\end{proposition}
\begin{proof}
In \cite{Henry}, a map $\widehat{\Psi}:\mathit{MCF}_\rho(\Lambda)/{\sim} \rightarrow \aug_\rho(\Lambda_\res)/{\sim}$ is defined and shown to be surjective.  Moreover, this map has the property that when $\mathcal{C}$ is an $A$-form MCF we have $\widehat{\Psi}([\mathcal{C}]) = [\epsilon_\mathcal{C}]$, and it is shown that every MCF is equivalent to an $A$-form MCF.  Finally, in \cite{HenryRu2} it is shown that $\widehat{\Psi}$ is injective.
\end{proof}

config: arxiv


TITLE: Does changing the order of the indices of the Kronecker delta within a summation matter?
QUESTION [2 upvotes]: In my notes I have that

$$\sum_m a_m \delta_{nm}=a_1\delta_{n1}+a_2\delta_{n2}+a_3\delta_{n3}+\cdots=a_n\tag{A}$$

Is this really correct?
I thought that for the Kronecker delta the first index must match the summation index. For this reason, I thought that the expression $(\mathrm{A})$ should written as
$$\sum_\color{blue}{m} a_m \delta_{\color{blue}{m}n}=a_1\delta_{1n}+a_2\delta_{2n}+a_3\delta_{3n}+\cdots=a_n\tag{B}$$
Just to make my argument clear, I have made the color of the indices match.
After looking at this page on the Kronecker delta I know that it is okay to write
$$\sum_ja_j\delta_{ij}=a_i\tag{1}$$
or
$$\sum_ia_i\delta_{ij}=a_j\tag{2}$$
Expression $(1)$ matches $(\mathrm{A})$ and expression $(2)$ matches $(\mathrm{B})$

So does this mean that switching the order of the indices of the Kronecker delta (within a summation) has no effect on the result (the RHS), or am I missing something?

REPLY [1 votes]: By its definition, $\delta_{i,j}=\delta_{j,i},$ [one can drop the commas as you have]  one can switch the indices anywhere, in a sum or otherwise.