TITLE: What exactly is the definition of motion and its relation to Mach's conjecture?
QUESTION [3 upvotes]: The notion of "movement" seems to be well understood in physics. In fact, I don't recall any physics text-book defining motion. Special relativity theory says that there is no absolute frame of reference.
Consider a star (such as the Sun). We say that the Sun is moving at so and so speed with respect to the Milky Way, which is moving at so and so speed with respect to the Andromeda Galaxy, and so on. However, this implies that motion only makes sense if there is a background frame of reference.
In a universe, where there is only one star, what would it mean for the star to rotate around its axis? How could we define this axis? And relative to what would it rotate?
If we can say that the star rotates, then there is some absolute frame of reference. In special relativity, the star would stop rotating if it was isolated from the rest of the universe. This seems to indicate that Mach's conjecture is true, and the existence of astronomical objects far away defines our notion of motion.
Is there any formal definition of motion, especially rotation?

REPLY [4 votes]: Even without external references, the presence of 'fictitious' forces, such as the coriolis force, would let you know that your planet is rotating. Or you could launch a rocket straight up until its speed slowed to nothing, and then falls back. If it falls back down to the launch pad, you have no rotation. Otherwise, it will fall back somewhere else, or even enter an elliptical orbit.
Mach's conjecture that the distant universe forms a frame of reference for zero rotation is difficult to test since it could be rotating very slowly at a rate we could never detect by experiment. But we know from the Big Bang theory that all those distant parts of the universe were once adjacent and connected to our part of the universe and frictional forces would have damped out any net rotation between our part of the universe and the now distant parts. So I would consider Mach's conjecture a manifestation of the Big Bang.


TITLE: Prove that $\mathbb{Q}$ has extensions of any finite degree in $\mathbb{C}$
QUESTION [3 upvotes]: This is a question from a course in Galois Theory and I am quite confused.
In general, the degree of a field extension $E/F$  is the dimension of the vector space $E$.
What would $E$ and $F$ be in these cases? Would $E$ be any field extension, $F$ be $\mathbb{Q}$.. where does $\mathbb{C}$ come into it - does this just mean that all elements in our field extensions over $\mathbb{Q}$ belong to the complex numbers?

REPLY [4 votes]: Consider the family of polynomials $f_n:=x^n-2$. Can you show that for each $n\geq 2$, $f_n$ is irreducible? What degree extension will adjoining a root of $f_n$ produce?


text:
\appendix

\section{Implementation Details} \label{sec:Feat}
In this appendix we describe additional details on the implementation of ALADIN-$\alpha$.
The main algorithm is based on Houska et al.\cite{Houska2016}, but additional practical considerations have been taking into account improving efficiency and numerical stability of ALADIN.
\subsection{ALADIN in Detail} \label{sec:ALADINdet}
The here-used version of standard ALADIN is summarized in Algorithm~\ref{alg:ALADIN}.
\begin{algorithm}
	\caption{Augmented Lagrangian Alternating Direction Inexact Newton (ALADIN)}
	\textbf{Initialization:} Initial guess $\left (\{z_i^0\}_{i\in \mathcal{S}},\lambda^0 \right )$, choose $\Sigma_i \succ 0,\rho^0,\mu^0,\epsilon$. \\
	\textbf{Repeat:}
	\begin{enumerate}
		\item \textit{Parallelizable Step:} \label{step:parStep}
		For each $i \in \mathcal{S}$, solve
	\begin{subequations}		\label{eq::denlp}
			\begin{align}
		\underset{x_i}{\min} &\;f_i(x_i) + (\lambda^k)^\top A_i x_i + \left\|x_i-z_i^k\right\|_{\Sigma_i^k}^2 \;\;\\
		\text{subject to }\; &g_i(x_i) = 0, \; h_i(x_i)\leq 0,\; \text{and} \; \underline{x}_i \leq x_i \leq  \overline{x}_i.
		\end{align}
	\end{subequations}
		\item \textit{Termination Check:} If
		$
		\label{eq::stop}
		\left\|\sum_{i\in \mathcal{S}}A_ix^k_i -b \right\|\leq \epsilon \text{ and } \left\| x^k - z^k \right \|\leq \epsilon\;,
		$
		return $x^\star = x^k$.

		\item \textit{Sensitivity Evaluations:} Compute and communicate local gradients~$g_i^k=\nabla f_i(x_i^k)$,
		Hessian approximations~{$ 0\prec B_i^k \approx \nabla^2\{f_i(x_i^k)+\kappa_i^{k\top} h_i(x_i^k)\} $} and constraint Jacobians $C^{k\top }_i :=\left [\nabla g_i(x^k_i)^\top\;  \left (\nabla \tilde  h_i(x^k_i) \right )_{j\in \mathbb{A}^k}^\top \right ]$.

		\item \textit{Consensus Step:} Solve the coordination QP
		\begin{align}
		\notag
		\underset{\Delta x,s}{\min}\;\;\sum_{i\in \mathcal{S}}\frac{1}{2}\Delta x_i^\top B^k_i\Delta x_i + &g_i^{k\top} \Delta x_i     + (\lambda^k)^\top s + \|s\|^2_{\Delta^k}  \\
		\text{subject to}\;                                   \sum_{i\in \mathcal{S}}A_i(x^k_i+\Delta x_i) &=  s   \label{eq::conqp}  \qquad  |\; \lambda^{\mathrm{QP} k},\\
		C^k_i \Delta x_i &= 0                                     \qquad   \forall i\in \mathcal{S}, \notag
		\end{align}
		returning $\Delta x^k$ and $\lambda^{\mathrm{QP}k}$.

		\item \textit{Line Search:} Update primal and dual variables by
		\begin{eqnarray}\notag
		z^{k+1}&\leftarrow&z^k + \alpha^k\Delta x^k \qquad \qquad
		\lambda^{k+1}\leftarrow\lambda^k + \alpha^k (\lambda^{\mathrm{QP}k}-\lambda^k),
		\end{eqnarray}
		with $\alpha^k=1$ for a full-step variant.
		Update $\Sigma_i^k$ and $\Delta^k$.
	\end{enumerate}
	\label{alg:ALADIN}
\end{algorithm}
Each ALADIN iteration executes three main steps: Step 1 solves local NLPs \eqref{eq::denlp} for fixed and given values for primal iterates $z_i^k$ and dual iterates $\lambda^k$ in parallel.
The parameter sequences $\{\Sigma_i^k\} \succ 0$ are user-defined---details are described in\autoref{sec:scalMat}.\footnote{We use scaled 2-norms $\|x\|_\Sigma:=\sqrt{x^\top \Sigma x}$ here.}
Note that the equality constraints $g_i$ and box constraints  are not explicitly detailed in Houska et al.\cite{Houska2016}---we consider them separately here for numerical efficiency reasons.\footnote{Some numerical solvers for \eqref{eq::denlp} can for example treat box constraints in an efficient way by using projection methods.}
Step 2 computes local sensitivities such as the gradient of the  local objectives $\nabla f_i(x_i^k)$ and positive definite approximations of the local Hessian matrices $B_i^k \approx H_i^k= \nabla^2_{xx}\big \{f_i(x_i^k)+\kappa_i^{k\top } g_i(x_i) + \left (\gamma_i^{k\top} \;\; \eta_i^{k\top }\right ) _{j \in \mathcal{A}_i^k   } \left ( \tilde h_j(x_i^k) \right )_{j \in \mathcal{A}_i^k} \big \}$.
Here, we define combined inequality constraints $\tilde h(x)^\top := \left (h(x)^\top \;\; (\underline{x}_i -x_i )^\top \;\; ( x_i - \bar {x}_i)^\top  \right )$ and a \emph{set of active inequality constraints}  in subproblems $i \in \mathcal{S}$
\begin{align*}
\mathbb{A}_i^k :=\left \{ j \in \{1,\dots, n_{hi} + 2n_{xi}\} \; | \; \left (\tilde h(x^k) \right )_j > -\tau     \right    \},
\end{align*}
with $\tau >0$ being a user-defined parameter which can be specified via the \texttt{actMargin} option.
Moreover, the Jacobians of the active constraints are defined as $C^{k\top}_i :$ $=\big (\nabla g_i(x^k_i)^\top\;  \left (\nabla \tilde  h_j(x^k_i) \right )_{j\in \mathbb{A}_i^k}^\top \big )$.
With this sensitivity information, step 4 solves an equality constrained quadratic program \eqref{eq::conqp} serving as a coordination problem.

The last step 5 of Algorithm~\ref{alg:ALADIN} updates $z^k$ and $\lambda^k$ based on the solution to  \eqref{eq::conqp}.
In order to get global convergence, the step size parameter $\alpha \in (0\;\;1]$ has to be properly chosen by a globalization routine.
Designing suitable distributed globalization routines is subject of ongoing and future work, currently we use the full step variant with $\alpha=1$.
A smaller stepsize can be specified via the \texttt{stepSize} option which might stabilize ALADIN-$\alpha$ for certain problems.
Note that time-varying parameter sequences $\{\Delta^k\}$ and $\{\Sigma_i^k\}$ with $\Sigma_i^k, \Delta^k \succ 0$ might accelerate convergence of ALADIN in practice.
Heuristic routines for doing so are described in \autoref{sec:scalMat}.\footnote{Note that in contrast to Houska et al.~\cite{Houska2016}, we omit the term $\rho/2$ in front of the penalization term in~\eqref{eq::denlp} removing redundancy. The setting from Houska et al.~\cite{Houska2016} can be recovered by choosing $\Sigma_i^k=\rho^k/2\,I$.}

\subsection{Solving the Coordination QP}
Note that as $B_i^k$ is assumed to be positive definite, \eqref{eq::conqp} is a strictly convex equality-constrainted QP which can be equivalently solved by solving the first order optimality conditions (if $C_i^k$ has full row rank) which is a linear system of equations.
The coordination problem \eqref{eq::conqp} can be solved in two different ways: either by centralized linear algebra routines or by iterative methods.
For centralized computation, several solvers are interfaced in ALADIN-$\alpha$ which can be specified via the \texttt{solveQP} option.
The available solvers are summarized in \autoref{tab:QPsol}.
Note that not all solvers support sparse matrices.
MA57 usually perfoms very well in practice---both in terms of speed and robustness.
The second approach to solve \eqref{eq::conqp} is via iterative and possibly \emph{decentralized} routines.
Details of these decentralized routines are described in \autoref{sec:bilAL}.

 \begin{table}[t]
	\centering
	\begin{tabular}{rllll}
		\toprule
		name	& MA57  &      pinv  & linsolve&  \\ \midrule
		algorithm & multifrontal LDL  & based on SVD & LU  \\
		sparse & yes & yes & no \\
\bottomrule
	\end{tabular}
	\caption{Centralized QP solvers interfaced in ALADIN-$\alpha$.	}
	\label{tab:QPsol}
\end{table}

\subsection{Hessian Approximations} \label{sec:hessApp}
As $H_i^k$ may have zero eigenvalues or may even be indefinite, special care has to be taken to ensure it's positive definiteness.\footnote{If one would use $\nabla^2\{f_i(x_i^k)+\kappa_i^{k\top} h_i(x_i^k)\}$ regardless, the coordination step \eqref{eq::conqp} would not necessarily produce decent directions  destroying the local convergence properties of ALADIN. In case of zero eigenvalues, $\nabla^2\{f_i(x_i^k)+\kappa_i^{k\top} h_i(x_i^k)\}$ is singular and the coordination step can not be easily solved by a standard solver for linear systems of equations.}
Here we use a heuristic using ideas from Nocedal and Wright~\cite{Nocedal2006}---other heuristics are possible and might accelerate convergence.
Our heuristics ``flips'' the sign of the negative eigenvalues (if there are any) and puts the zero eigenvalues to a small positive number $\delta$.
The intuition here is  that the stepsize in the direction of negative curvature gets smaller the ``more negative'' the curvature is; we made good numerical experience with that rule.
However there is no more sophisticated mathematical reasoning behind.
Mathematically this means we compute an eigendecomposition $H_i^k=V_i \Lambda_i V_i^\top$ locally, where $\Lambda_i$ is a matrix with the eigenvalues of $H_i$ on its main diagonal and $V_i$ is a matrix of the corresponding eigenvectors.
Our rule for regularization is
\begin{align*}
\tilde{\Lambda}_{jj} :=
\begin{cases}
|{\Lambda}_{jj}| & \text{if } {\Lambda}_{jj} < - \delta,\\
\delta & \text{if } |{\Lambda}_{jj}| \in (-\delta, \;\delta), \\
{\Lambda}_{jj} & \text{else},
\end{cases}
\qquad
\text{and}
\qquad
B_i^k:=V_i \tilde \Lambda_i V_i^\top,
\end{align*}
with $\delta = 10^{-4}$.
Regularization and the corresponding $\delta$ can be activated and specified by the options \texttt{reg} and \texttt{regParam} corresponding to $\delta$.

As an alternative to exact Hessians with regularization, one can use the Broyden-Fletcher–Goldfarb-Shanno (BFGS) update-rule for successively approximating the exact Hessian based on the gradient of the Lagrangian.
This has the advantage that only the gradient of the Lagrangian has to be communicated (which is a vector) instead of the Hessian (which is a matrix).
A detailed description on how to use BFGS within ALADIN can be found in Engelmann et al.~\cite{Engelmann2019}.
The BFGS formula can be activated by the setting the option \texttt{Hess} to \texttt{BFGS} or to \texttt{DBFGS} for damped BFGS.
The advantage of damped-BFGS is that it guarantees positive-definiteness of $B_i^k$ regardless of the positive-definiteness of the exact Hessian at the current iterate.
Note that in case the nullspace method which we will introduce in \autoref{sec:redSp} is used, the regularization is done for the reduced Hessian $\bar H_i^k$ instead of $H_i^k$.

\subsection{Scaling Matrices} \label{sec:scalMat}
A simple Heuristic for the sequences $\{\Sigma_i^k\} \succ 0$ and $\{\Delta^k\} \succ 0$ is to start with certain (usually diagonal) initial matrices $\Sigma_i^0, \Delta^0$ and to multiply them by a factor $r_\Delta,r_\Sigma > 1$ in each iteration, i.e.
\begin{align} \label{eq:SigUpdate}
\Sigma_i^{k+1} =
\begin{cases}
r_\Sigma \Sigma_i^k\   &\text{if} \; \|\Sigma_i\|_\infty < \bar \sigma\\
\Sigma_i^k&\text{otherwise}
\end{cases}
\qquad   \text{and} \qquad
\Delta^{k+1} =
\begin{cases}
r_\Delta \Delta ^k\   &\text{if} \; \|\Delta\|_\infty < \bar \delta\\
\Delta^k&\text{otherwise} .
\end{cases}
\end{align}
This routine is successfully used in  previous works.\cite{Engelmann2019,Engelmann2020c}
An alternative option for choosing the sequence $\{\Delta^k\}$ is based on the consensus violation for each individual row in \eqref{eq:consCnstr}.
The idea here is to increase the corresponding $\Delta _{ii}^k$ to drive the corresponding consensus violation to zero.
This technique is common in algorithms based on augmented Lagrangians, cf. \cite[Chap 4.2.2]{Bertsekas1999}.
Mathematically this means that we choose
\begin{align*}
\Delta_{cc}^{k+1} =
\begin{cases}
\beta \, \Delta_{cc}^k   &\text{if} \; \left |\left (\sum_{i\in \mathcal{S}}A_i x_i^k - b \right )_c \right | >\gamma \left  |\left (\sum_{i\in \mathcal{S}}A_i x_i^{k-1} - b \right )_c \right | \phantom{\bigg |}\\
\Delta^k_{cc}&\text{if} \;  \left |\left (\sum_{i\in \mathcal{S}}A_i x_i^k - b \right )_c \right | \leq \gamma \left  |\left (\sum_{i\in \mathcal{S}}A_i x_i^{k-1} - b \right )_c \right | \phantom{\bigg |}
\end{cases}
  \text{for all }
c\in 1,\dots,n_c,
\end{align*}
with $\gamma \in (0\; \;1)$ and $\beta > 1$.
In ALADIN-$\alpha$ we choose $\beta= 10$ and $\gamma = 0.25$.
This rule can be activated by the option \texttt{DelUp} and is able to accelerate convergence of ALADIN-$\alpha$ substantially in some cases.

Note that all the above heuristics such as regularization or parameter updates do---although they are heuristics---not interfere with the fast local convergence properties of ALADIN-$\alpha$.
They are rather required for guaranteeing fast local convergence since they ensure that the assumptions made in the local convergence proof of ALADIN such as the positive-defniteness of $B_i^k$ are satisfied~\cite{Houska2016}.

\subsection{The Nullspace Method} \label{sec:redSp}
The nullspace method can be used to reduce the dimensionality of the coordination QP \eqref{eq::conqp}, thus reducing communication and computation in the coordination step.
The idea here is to parameterize the nullspace of the active constraints $\operatorname{null}(C_i^k):=\{x_i \in \mathbb{R}^{n_{xi}} \; |\; C_i^k x_i^k=0\}$ by $\operatorname{null}(C_i^k)= Z_i^k\Delta v_i$, where $Z_i^k \in \mathbb{R}^{x_{xi} \times\left  (n_{xi} - |\mathbb{A}_i^k|\right )}$ is matrix which's columns form a basis of  $\operatorname{null}(C_i^k)$.
Note that  $C_i^kZ_i^k=0$ by definition of the nullspace.
By using this parametrization, \eqref{eq::conqp} can be written as
\begin{align}
\begin{aligned}
&\underset{\Delta v,s}{\min}\;\;\sum_{i\in \mathcal{S}}\left\{\frac{1}{2}\Delta v_i^\top \bar B^k_i\Delta v_i + \bar  g_i^{k\top} \Delta v_i\right\}     + (\lambda^k)^\top s + \|s\|^2_{\Delta^k}  \\
&\label{eq:redQP}
\text{subject to}\;                                   \sum_{i\in \mathcal{S}}\bar A^k_i(v^k_i+\Delta v_i) =  s    \qquad  |\; \lambda^{\mathrm{QP} k},
\end{aligned}
\end{align}
where $\bar H_i^k=Z_i^{k\top}H_i^k Z_i^k \in \mathbb{R}^{\left (n_{xi} - |\mathbb{A}_i^k| \right )\times \left (n_{xi} - |\mathbb{A}_i^k| \right )}$, $\bar g_i^{k} = Z_i^{k\top}g_i^k \in \mathbb{R}^{\left (n_{xi} - |\mathbb{A}_i^k| \right )}$ and $\bar A_i^k= A_i Z_i^k\in \mathbb{R}^{n_c \times \left (n_{xi} - |\mathbb{A}_i^k| \right )}$.
Note that $\bar A_i^k$ has an iteration index $k$ and changes during the iterations since $Z_i^k$ changes.
Similar to the full-space approach, regulaization from \autoref{sec:hessApp} is also used here (if it is activated via the option reg \texttt{reg}) yielding a positive definite $\bar B_i^k$.
The nullspace method can be used by activating the option \texttt{redSpace}.
Notice that (at least in case of dense matrix storage formats) the required communication between the subproblems and the coordinator is reduced by twice the number of equality constraints and active inequality constraints.
The amount of communication reduction can be quite large---especially in case of problems with a large number of constraints.
Furthermore, the coordination QP \eqref{eq::conqp} is in general less expensive to solve since \eqref{eq:redQP} is of smaller dimension than \eqref{eq::conqp}.
Moreover,  \eqref{eq:redQP} is strongly convex under suitable assumptions which \eqref{eq::conqp} is not necessarily~\cite{Engelmann2020c}.
Note that computing such a nullspace is expensive in general as it involves a singular-value decomposition.
However, the advantage here is that this step is done \emph{locally}, enabling parallel computation.

\subsection{Bi-level ALADIN} \label{sec:bilAL}
Bi-level ALADIN is and extension of ALADIN to further reduce dimensionality of the already reduced coordination QP \eqref{eq:redQP} and thereby further reducing communication and computation overhead of the coordination step.
Moreover, bi-level ALADIN uses \emph{decentralized} inner algorithms for solving further reduced coordination QP.
By doing so, ALADIN becomes a \emph{decentralized} optimization algorithm which means that it can operate purely on a neighbor-to-neighbor basis.
Note that the here-presented inner algorithms \emph{decentralized ADMM} (D-ADMM) and \emph{decentralized conjugate gradients} (D-CG) are improved versions of the algorithms given in Engelmann et al.~\cite{Engelmann2020c}.
Their derivation is more intuitive and, in case of D-CG, the version given here \emph{avoids} the preparation step from Engelmann et al.~\cite{Engelmann2020c} further improving communication requirements.
Nonetheless---in terms of their theoretical properties and the generated iteration sequences---the algorithms from Engelmann et al.~\cite{Engelmann2020c} and the here-given variants are equivalent.
We provide a detailed derivation of both of these two algorithms in Engelmann et al.~\cite{Engelmann2020c}.

Let us briefly introduce the main idea of bi-level ALADIN.
Writing down the KKT conditions for \eqref{eq:redQP}  yields (under the assumptions from Engelmann et al.\cite{Engelmann2020c})
\begin{subequations} \label{eq:KKTred}
	\begin{align}
	\bar B^k \Delta v + \bar g^k + \bar A ^{k\top} \lambda^{\mathrm{QP}}&=0, \label{eq:SchurElim} \\
	\bar A^k(v^k + \Delta v) -b -\frac{1}{\mu}(\lambda^{\mathrm{QP}}-\lambda^k) &=0, \label{eq:redKKTdelV}
	\end{align}
\end{subequations}
where $\bar B^k$, $\bar A^k$ and $\bar \Delta v^k$ are block-diagonal concatenations of $\bar B_i^k$, $\bar A_i^k$ and $\bar \Delta v_i^k$.
Using the \emph{Schur-complement} reveals that \eqref{eq:KKTred} is equivalent to solving the unconstrained and strongly convex QP
\begin{align} \label{eq:SchurComp}
\left  (\sum_{i \in \mathcal{S}} S_i^k+\; \frac{1}{\mu} I\, \right  ) \lambda^{\mathrm{QP}}=\sum_{i \in \mathcal{S}} s_i^k   +I \left ( \frac{1}{\mu} \lambda^k - b \right ) ,
\end{align}
where we have local Schur-complement matrices $S_i^k := \bar A^k \, \bar B^{k^{-1}} \bar A^{k\top} $ and vectors $s_i^k:= \bar A^k\left (v^k - \bar  B^{k^{-1}} \bar g^k\right )$, cf. Engelmann et al.~\cite{Engelmann2020c}.
The key observation for decentralization is that the matrices $S_i^k$ and vectors $s_i^k$ inherit the sparsity pattern of the consensus matrices $A_i$, i.e. zero rows in $A_i$ yield zero rows/columns in $S_i^k$ and $s_i^k$.
Intuitively speaking, each row/column of $S_i^k$ corresponds to one consensus constraint (row of \eqref{eq:consCnstr}) and only the subproblems which ``participate'' in this constraint have non-zero rows in their corresponding $S_i$.
Mathematically, we collect all indices for which $S_i$ has non-zero rows/columns in the set $\mathcal{C}(i)$.
Note this set corresponds to all non-zero rows of $A_i$, which can be directly shown from the definition of $S_i^k$~\cite{Engelmann2020c}.
That means that we can equivalently define
$\mathcal{C}(i):=\{ c\in \{1,\dots,n_c\} \; | \; A_{ic} = 0\}$, where $A_{ic}$ denotes the $c$th row of $A_i$.
We say that two subproblems $i,j \in \mathcal{S}$ are \emph{neighbored}, if $\mathcal{C}(i) \cap \mathcal{C}(j) \neq \emptyset$.

In order to exploit this sparsity, we introduce matrices $I_{\mathcal{B}}:=\left (e_s^\top\right )_{s \in \mathcal{B}}\in \mathbb{R}^{|\mathcal{B}| \times n_c}$, where $e_c\in \mathbb{R}^{n_c}$ is the $c$th unit-vector and  $\mathcal{B}$ is an arbitrary index set.
Moreover, let us define  $I_{ij}=I_{\mathcal{C}(i)}^{\phantom \top} I_{\mathcal{C}(j)}^{\top} $, $\Lambda_i=I_{\mathcal{C}(i)}^{\phantom \top}  \left (\sum_{j \in \mathcal{S}} I_{\mathcal{C}(j)}^{ \top} I_{\mathcal{C}(j)}^{\phantom \top} \right ) I_{\mathcal{C}(i)}^{ \top}$, $\hat S_i^k = I_{\mathcal C(i)}^{ \top} \tilde S_i^k I_{\mathcal C(i)}^{\phantom \top}$, and $\hat s_i^k = I_{\mathcal C(i)}\tilde s^{k}$.
Based on these definitions, it is possible to derive D-CG and D-ADMM.
The resulting algorithms are summarized in Algorithm~\ref{alg:D-ADM}~(D-ADMM) and Algorithm~\ref{alg:D-CG}~(D-CG).
Therein, superscripts $(\cdot)^n$ denote inner iterations.
Detailed derivations can be found in Engelmann et al.~\cite{Engelmann2020c,Engelmann2020b}.
\begin{algorithm} [t]
	\caption{D-ADMM for problem \eqref{eq:SchurComp}}
	\textbf{Initialization: $\bar \lambda_i^0$, $\gamma_i^0$ for all $i \in \mathcal{S}$, $\rho$}\\
	\textbf{Repeat for all $i \in \mathcal{S}$:}
	\begin{enumerate}
		\item $\lambda_i^{n+1}=\left (\hat S_i^k + \rho I \right)^{-1}\left ( \hat s_i^k - \gamma_i^n + \rho  \bar \lambda^n_i \right ) \qquad $\hfill (local)
		\item
		$
		\bar \lambda^{n+1}_i = \left (\Lambda_i \right )^{-1} \sum_{j \in N(i)} I_{ij} \lambda_j^{n+1}
		\qquad \qquad \qquad \;
		$

		\hfill (neighbor-neighbor)
		\item $\gamma_i^{n+1} = \gamma_i^n + \rho(\lambda^{n+1}_i -  I_{\mathcal{C}(i)} \bar \lambda^{n+1})\qquad \qquad \quad \;\;  $ \hfill (local)
	\end{enumerate} \label{alg:D-ADM}
\end{algorithm}
\begin{algorithm}[t]
	\caption{D-CG for problem \eqref{eq:SchurComp}}
	\textbf{Initialization: $ \lambda^0$ and $r^0=p^0=\tilde s -\tilde S  \lambda^0$}\\
	\textbf{Repeat for all $i \in \mathcal{S}$:}
	\begin{enumerate}
		\item
		$\sigma^{n} = \sum_{i \in \mathcal{S}} \sigma_i^{n}$ \hfill (scalar global sum)
		\item
		$r^{n+1}_i = r_i^n - \frac{\eta^{n}}{\sigma^{n}} \sum_{i \in N(i)} I_{ji} u_j$ \hfill (neighbor-neighbor)
		\item
		$\eta^{n+1}_i= r_i^n \Lambda_i r_i^n $ \quad  $\lambda_i^{n+1} = \lambda_i^n + \frac{\eta^{n}}{\sigma^n} p_i$ \hfill (local)
		\item
		$\eta^{n+1}= \sum_{i \in \mathcal{S}} \eta_i^{n+1}$  \hfill (scalar global sum)
		\item $ p_i^{n+1}= r_i^n + \frac{\eta^{n+1}}{\eta^n} p_i^n$ \quad $u_i^{n+1}= \hat S_i p_i^{n+1}$
		\quad
		$\sigma^{n+1}_i = p^{n+1 \top }_i \hat S_i p^{n+1}_i$  \hfill (local)
	\end{enumerate} \label{alg:D-CG}
\end{algorithm}
In both algorithms, we have three different types of steps:
\emph{Local} steps which are independently performed by each subsystem $i \in \mathcal{S}$, \emph{neighbor-neighbor} steps requiring communication between neighbors,\footnote{It can be shown that if two subproblems $i,j \in \mathcal{S}$ are \emph{not} neighbored, we have $I_{ij}=0$ making D-CG and D-ADMM decentralized.\cite{Engelmann2020b}} and \emph{scalar global sums}  (only in D-CG), which requires summing up one scalar number in each inner iteration globally.
D-ADMM maintains the  variables $\lambda_i,\bar \lambda_i \in \mathbb{R}^{|\mathcal{C}(i)|}$, and $\gamma_i\in \mathbb{R}^{|\mathcal{C}(i)|}$ locally in each subsystem $i \in \mathcal{S}$.
D-CG has $\lambda_i,r_i, u_i \in \mathbb{R}^{|\mathcal{C}(i)|}$ and $p_i\in \mathbb{R}^{|\mathcal{C}(i)|}$ as local variables.

\begin{figure}
	\centering
	\includegraphics[width=.75\linewidth]{figures/nodeEdgeVals3}
	\caption{Information exchange and local variables for D-ADMM  and D-CG.}
	\label{fig:nodeedgevals}
\end{figure}

The amount of information exchanged between neighbors is almost the same in both algorithms.
In D-ADMM, the product $I_{ij}\lambda_i$ is exchanged comprising $|\mathcal{C}(i)|$ floats, which is the same number of floats required for the product $I_{ij} u_i$.
However, D-CG requires to exchange two scalar values per subsystem in each iteration additionally.
On the other hand this yields to substantial acceleration of convergence---theoretically and practically~\cite{Engelmann2020c}.
The information exchange and the locally maintained variables for both algorithms are graphically illustrated in \autoref{fig:nodeedgevals}.

In ALADIN-$\alpha$, both algorithms D-ADMM and D-CG terminate after a fixed number of inner iterations which can be specified via the \texttt{innerIter} option.
Furthermore, warm starting of both algorithms with the previous $\lambda$ improves the overall performance significantly and is by default activated in the \texttt{warmStart} option.
Note that D-CG has to be initialized \emph{consistently}, i.e. the initial values $r^0$ and $p^0$ have to fulfill the condition in the initialization step of Algorithm~\ref{alg:D-CG}.
The type of inner algorithm can be specified with the \texttt{innerAlg} option; the parameter $\rho$ for ADMM is specified with \texttt{rhoADM}.

config: arxiv


TITLE: Understanding definition of explicit Euler method
QUESTION [1 upvotes]: I'm quite new to ODE and the IVP (initial value problem), so I've some doubts related to these topics.
I'm reading a draft provided by my professor which talks about the "polygon" or explicit Euler method.
The goal to use this method is to find an approximation of the solution to the IVP.
In the draft, it starts by explaining the following things:

Then, starting from $y_0$, we construct an approximation $y_\tau$ of $y$ as follows: first, we choose $n + 1$ points $t_0,\ldots ,t_n$ with the following properties:

$$\tau = \frac{t_n - t_0}{n}$$
$$t_i = t_0 + i\cdot \tau$$ for $i = 0,1,\ldots,n$

Now we recursively define the values of our approximation $y_\tau$ by exploiting the ODE
$$\frac{d y(t)}{ dt} = \lambda y(t)$$
  $t \in (t_0, t_{\rm end}]$
$$y_\tau(t_{i + 1}) = y_\tau(t_i) + \tau \cdot \lambda\cdot  y_\tau(t_{i})$$

Can someone explain to me:

What's the relation between the IVP and this definition to find $y_\tau$?
What's "tau" ($\tau$) here doing?
Why do we choose the 2 points above as we did?

One-line answers may not be satisfiable, since I'm new to these topics, but I appreciate any help!

REPLY [2 votes]: To get an intuition for IVP, I approach it like this:
Assume you want to find $y(t_{end})$ for some unknown function $y(t)$. What you have is $y(t_0$) and the slope of the graph given by the first order ODE:
$$ \frac{dy(t)}{dt} = \lambda y(t)$$
How would you try to find $y(t_{end})$ when looking at the graph of $y$ where the abscissa is $t$? As said before, what you know is $y(t_0)$ and the slope at every point, thus we also know the slope at $t_0$ given by $\frac{dy}{dt} (t_0)$.
The following steps can be more comprehensive if you try it with pen and paper and try to draw the graph of $y(t)$ where the abscissa is $t$. We can get a crude approximation of $y(t_{end})$ by constructing a line going through $y(t_0)$ with the slope at $t_0$ given by $\frac{dy}{dt}(t_0)$. We evaluate that line at $t_{end}$ and get the approximation for $y(t_{end})$.
More compactly we can formulate this walking on the line by directly by computing $ y(t_0) + \Delta t \cdot m$ where $\Delta t := t_{end} - t_0$ is how far we go on the abscissa and $m$ is the line slope given by $\frac{dy}{dt} (t_0)$. This gives $y(t_{end}) \approx y(t_0) + \Delta t \frac{dy}{dt}(t_0) $.
But as you probably expect this doesn't give you a very good approximation. Something simple that you can do to improve the approximation is you divide your step (which is now $\Delta t$) into $n$ steps. To do this we need to compute the corresponding step size tau $\tau = \frac{\Delta t}{n} = \frac{t_{end}- t_0}{n}$ and evaluate the line slopes at the intermediate positions i.e. $\frac{dy}{dt}(t_i)$ where $t_{i+1} = t_{i} + \tau$ which is equal to $t_i = t_0 + i \cdot \tau$.
In our case, the intermediate $y$ values are then given by
$$ y(t_{i+1}) = y(t_{i}) + \tau \cdot \frac{dy}{dt}(t_{i})= y(t_{i}) + \tau \cdot \lambda y(t_{i})$$
If you already know Taylor series', you can look at this formula as a first order taylor approximation of $y(t_{i+1})$ at $y(t_{i})$.
The different evaluation points $t_i$ can be chosen arbitrarily (you want them to choose s.t. your result is a good approximation), but the step size must be adapted accordingly. If we look at the taylor approximation we have
$$y(t_{i+1}) = y(t_i) + (t_{i+1} - t_i) \cdot \frac{dy}{dt}(t_i)$$


TITLE: Funky change in correlation
QUESTION [0 upvotes]: Context: The figure below plots the record-high yearly precipitation in each state against the state's record-high 24-hour precipitation. Hawaii is a high outlier, with a record-high yearly record of 704.83 inches of rain recorded in Kukui in 1982. (Figure will not embed because of new member rep.)
enter image description here
Question: Why is it that while taking an outlier away from a collection of data in a scatter plot the correlation of the data decreases? Will this always be the case? Mathematically, I think this can be proven, but could anyone explain why this is the case from a more conceptual/intuitive point of view?
Thoughts: I think I kind of get it, but I'm having difficulty articulating why this is the case here--would it be true that if all of the data were shifted up and the outlier moved to the bottom right of the figure, then there would be a slightly positive correlation without the outlier, but including the outlier would actually decrease the correlation?

REPLY [0 votes]: The reason is that there is low correlation. If you remove outliers in this plot, then you end up with almost all dots being around 100 on the y axis, no matter where they sit on the x axis. Hawaii makes it appear like the correlation is stronger than it actually is.
So no, this will not always be the case. If you have strongly correlated data and removed outliers, your correlation will increase.


TITLE: Suspension of a map
QUESTION [0 upvotes]: Suppose I have a surjective map, say $f$, between two spheres (of dimension $n+1 \geq 2$) such that it takes the closed upper hemisphere to itself and the closed lower hemisphere to itself. Now, I get a map $\hat{f}$ between $S^n$ by restricting $f$ to the equator.

Can someone help me find an explicit homotopy between the suspension of $\hat{f}$ and $f$

Using this I want to establish that the degree of $\hat{f}$ is the same as $f$, which I know to be true via another argument.

REPLY [1 votes]: Let $S^+$ be be northen hemisphere of your $n$-sphere $S$. Then $f$ restricts to a map $f:(S^+,\partial S^+)\to(S^+,\partial S^+)$, which gives us a class in $\pi_n(S^+,\partial\ S^+)$. The long exact sequence for homotopy groups corresponding to the pair $(S^+,\partial S^+)$ shows that the boundary map $$\pi_n(S^+,\partial S^+)\to\pi_{n-1}(\partial S^+)$$ is an isomorphism.
Can you see how to use this fact (and the symmetric one for the southern hemisphere) to show what you want?
(Knowing how the long exact sequence for the homotopy groups of a pair is built out of the Barratt-Puppe sequence will help here; standard textbooks should help ---I particularily like the meticulousness of Switzer!--- as well as this nice post by our co-M.SEer Akhil)


TITLE: Krull dimension and localization
QUESTION [11 upvotes]: If we have a commutative ring with 1, what can we say about $\operatorname{dim} S^{-1}A$ for some multiplicative subset $S$, or more specifically, what happens if $S = A \setminus \mathfrak{p}$ for a prime ideal $\mathfrak{p}$?
Do the dimensions of the localization generally coincide for distinct prime or maximal ideals? Thanks!

REPLY [15 votes]: What is true is that $\dim S^{-1}A\le \dim A$ because $\mathrm{Spec}(S^{-1}A)$ is homeomorphic to a subset of $\mathrm{Spec}(A)$.
For $A_{\mathfrak p}$, the dimension varies: if $\mathfrak p$ is a minimal prime, then the localization has dimension $0$. If $\mathfrak p$ is not maximal and $\dim A$ is finite, then $\dim A_{\mathfrak p}<\dim A$. On the other hand, $\dim A$ is the supremum of the $\dim A_{\mathfrak m}$ when $\mathfrak m$ runs the maximal ideals of $A$. If $A$ is an integral finitely generated algebra over a field, then $\dim A=\dim A_{\mathfrak m}$ for any maximal ideal.


TITLE: The physics behind tilting trains
QUESTION [0 upvotes]: So I'm trying to get an intuition behind the physics behind banked curves (and tilting trains). I know how to do the calculations, but I'm still struggling with the "why".
If I'm sitting in a train, and the train is engineered in such a way that it tilts $ \theta $ degrees during a turn, how would you draw the free body diagram of a person sitting in the train in such an event? Normally, the normal force $ N $ would be $ \cos(\theta)mg $ (assuming there's a tilt but no velocity). However, when you introduce velocity and curves into the equation the normal force $ N $ suddenly becomes larger than $ mg $, i.e. $$ N = mg/\cos(\theta) .$$
What gives? Obviously it has something to do with the centripetal acceleration, but I feel like total moron for not understanding the intuition behind it.

REPLY [1 votes]: This is a difficulty I see regularly: people often confuse real forces with the direction of the acceleration they experience.
In your situation, the real forces are gravity and the interaction with the seat/floor. The interaction with the seat/floor is often split into two components, tangent to the contact point (friction) and perpendicular to the contact point (normal). People often try to assume they know the normal force, but they can't without doing a proper free-body diagram. A good rule is do not assume that the normal force magnitude is equal to the weight. (Often, in overly-simplified drill problems it is, but in the real world it usually is not.) Let it have its own symbol ($F_N$ or $\mathcal{N}$) and see what the analysis tells you about how it relates to other quantities.
Draw a diagram (another failure on the part of many) showing the directions of these two/three forces. Then, superimpose a coordinate system that is convenient. The choice of the coordinate system never affects what happens, but does affect how one describes what is happening. If you are dealing with something moving circularly in a horizontal plane, choose horizontal and vertical, even if the train is tilted. The normal force from the seat/floor will be tilted, as will the friction, but you must resolve those into horizontal and vertical components so that you can apply Newton's 2nd Law to each coordinate direction easily.
Choose the positive horizontal direction to be toward the center of the circular path. Those force components will sum and be equal to the mass times the centripetal acceleration, in whatever form you want (linear speed, angular speed, period, etc):
$$\Sigma F_{\mathrm{horizontal}} = ma_{\mathrm{centripetal}}$$
The vertical force components sum to equal the mass times the vertical acceleration (zero for horizontal planar motion):
$$\Sigma F_{\mathrm{vertical}} = ma_{\mathrm{vertical}}=0$$
When you solve this system, you may be able to write an equation $$\mathcal{N}=\text{some combination of other quantities}.$$
Remember that this is a specific relationship between the magnitude of the normal force and other things affecting the object. It is not a general statement that explains the normal force, nor is it a fundamental equation.


text:
\section{Cover relations}
\label{sec:ulbounds}

In this section we compute the number of upper and lower covers for each Shi tableau $T$
in the poset $(\shiT{},\preceq_{\shiT{}})$. To do so, we define irreducible and strongly irreducible
Shi tableaux and we find closed/recursive formulas for their number of lower/upper covers.
Then, we explain how each Shi tableau is decomposed into its  irreducible components and how the lower/upper covers are computed in terms of the upper/lower covers of the decomposition.
\medskip

We start with notation and definitions that will be used throughout the section.
In this section, we find it more convenient to use the notation $\pa$ for Dyck paths, rather than $T$ for Shi tableaux, since most of the arguments use the realization of $\pa$ as a word in $\{\U,\D\}^*$.
However, the underlying tableau of $\pa$ and more precisely its columns and rows is
present in all the proofs.

Let $T$ be a Shi  tableau of size $n$ and denote by $\pa\in\dP{n+1}$ the corresponding Dyck path.
Let us denote by $\col{k}$ the $k$-th column of the underlying tableau of
$\pa\in\dP{n+1}$ and index the $\U$-steps and $\D$-steps of $\pa$ from $1$ to
$n+1$.
 The portion  of the path $\pa$ contained in column $\col{k}$ consists of all
the steps that satisfy $k-1\leq{x}\leq{k}$. In other words
$\pa\cap\col{k}$ is the subpath between (and not including) $\D_{k-1}$
and $\D_{k+1}$.

An {\em ascent} of a Dyck path $\pa$ is a maximal string of consecutive $\U$-steps  and a
{\em descent} is a maximal string of consecutive $\D$-steps of $\pa$.
Each Dyck path $\pi$ can be written as a concatenation of ascents and descents,
i.e.\,,
\begin{equation}
	\pi=\U^{a_1}\D^{b_1}\U^{a_2}\D^{b_2}\cdots\U^{a_\ell}\D^{b_\ell}
	\text{ \;\;for some\;\; } 1\leq{\ell}\leq{n+1} \text{ \;\; and\;\;  } a_i,b_i\geq{1}.
	\label{asc_des}
\end{equation}

For each ascent $\U^{a_i}$ of $\pa$ we define
a subpath $\overline \pa_i$  of $\pa$ as follows:
\begin{align}
  \overline\pa_1= \pa\cap\bigl(\bigcup_{r=1}^{a_1}
  \col{r}\bigr)  \text{ \;\;\;\; and \;\;\;\;\;\;}
 \overline\pa_i=\pa\cap\bigl(\bigcup_{r=0}^{a_i}
 \col{a_1+\cdots+a_{i-1}+r}\bigr) \text{\;\; if \;\;} i \geq{2}
 \label{equ:pi}
\end{align}
   (see Figure \ref{figci}).
As we will explain subsequently, the subpaths $\overline \pa_i$ are involved
in the computation of the lower and uppers
covers of $\pa$.
For example, for the lower covers,  $\overline\pa_i$
  is the range of possible $\D$-step
 deletions  that correspond to the deletion of a $\U$-step from  the ascent
$\U^{a_i}$ of $\pa$.
\medskip

We say that $\pi\in\dP{n+1}$ is {\em irreducible} if it does not touch the
the line $y=x$  except for the origin and the final point
 and  {\em strongly irreducible} if it does not touch the
 the line $y=x+1$  except for the first and last step.
If $\pa$ is irreducible then $b_1+\cdots+b_i<a_1+\cdots+a_i$
and if $\pa$ is  strongly irreducible then $b_1+\cdots+b_i+1<a_1+\cdots+a_i$
for all $i$ with $1\leq i<\ell$.

The situation where a Shi tableau $T$ can be obtained from a tableau $T'$ by two different bounce deletions is rather restrictive.
The lemma below describes the conditions when this is possible.
 Pictorially, the following lemma implies that, if two bounce deletions  produce the same lower cover,  then they both delete a $\U$ and a $\D$-step from the same ascent and descent respectively.
 The only exception is the case where $\pa$
 is symmetric, where deletion of first column or last row produce the same lower cover  (see  Figure \ref{fig:lem_covers}).
Given a word $w\in\{\U,\D\}^*$ let $\nup(w)$ denote the number of $\U$-steps in $w$, and let $\ndown(w)$ denote the number of $\D$-steps in $w$.
\begin{lemma}
	\label{Lemma:double_cover}
	Consider  $i,j\in[n]$ with $i<j$ and   let $k_i\in\{i-1,i\}$ and $k_j\in\{j-1,j\}$.
	Let $\pa$ be a Dyck path with $\U$ and $\D$-steps indexed by $\U_1,\ldots,\U_n,\D_1,\ldots, \D_n$,

	 and let $\pa'$ be a Dyck path  obtained from $\pa$ by deleting
	$\U_i$ and $\D_{k_i}$   and also by deleting
	$\U_j$ and $\D_{k_j}$.
	That is, $\pi'=\de{i}{k_i}(\pi)=\de{j}{k_j}(\pi)$.

	\begin{enumerate}[(i)]
		\item
		\label{Item:double_cover:normal}
		If $\D_{k_i}$ occurs after $\U_j$, then
		$\U_i$ and $\U_j$  belong to the same ascent of $\pi$.
		Furthermore
		$\D_{k_i}$ and $\D_{k_j}$  belong to the same descent of $\pi$.

		\item
		\label{Item:double_cover:exception}
		If $\D_{k_i}$ occurs before  $\U_j$, then the segment of $\pi$ connecting
		$\U_i$ and $\D_{k_j}$
		 is of the form $\U^r(\U\D)^{\ell}\D^t$ for some $r,\ell,t\in\NN$ with $\ell>0$.
		Furthermore this segment begins at height $i-k_i\in\{0,1\}$ and ends at height $j-k_j\in\{0,1\}$.
	\end{enumerate}
\end{lemma}

\begin{proof}
First assume that we are in case \refi{double_cover:normal}.
Then there exist unique (possibly empty) words $\alpha,x,y,z,\beta\in\{\U,\D\}^*$ such that
\begin{eq*}
\pi'=\alpha xyz\beta
\qquad\text{and}\qquad
\pi
=\alpha \U xy\D z\beta
=\alpha x\U yz\D \beta
\end{eq*}
such that $\alpha $ contains $i-1$ $\U$-steps, $\alpha x$ contains $j-1$ $\U$-steps, $\alpha \U xy$ contains $k_i-1$ $\D$-steps, and $\alpha x\U yz$ contains $k_j-1$ $\D$-steps.
In particular the two words
\begin{eq*}
\begin{array}{*{13}c}
\U & x_1 & \cdots & x_{r-1} & x_r & y_1 & \cdots & y_s & \D & z_1 & \cdots & z_{t-1} & z_t\\
x_1 & x_2 & \cdots & x_{r} & \U & y_1 & \cdots & y_s & z_1 & z_2 & \cdots & z_t & \D
\end{array}
\end{eq*}
agree.
Consequently $x=\U^r$ and $z=\D^t$ for some $r,t\in\NN$.

Next assume we are in case \refi{double_cover:exception}.
Then there exist unique (possibly empty) words $\alpha ,x,y,z,\beta \in\{\U,\D\}^*$ such that
\begin{eq*}
\pi'=\alpha xyz\beta
\qquad\text{and}\qquad
\pi
=\alpha \U x\D yz\beta
=\alpha xy\U z\D \beta
\end{eq*}
such that $\alpha $ contains $i-1$ $\U$-steps, $\alpha \U x$ contains $k_i-1$ $\D$-steps, $\alpha xy$ contains $j-1$ $\U$-steps, and $\alpha xy\U z$ contains $k_j-1$ $\D$-steps.
In particular the two words
\begin{eq*}
\begin{array}{*{15}c}
\U & x_1 & \cdots & x_{r-1} & x_r & \D & y_1 & \cdots & y_{s-2} & y_{s-1} & y_s & z_1 & \cdots & z_{t-1} & z_t\\
x_1 & x_2 & \cdots & x_{r} & y_1 & y_2 & y_3 & \cdots & y_s & \U & z_1 & z_2 & \cdots & z_t & \D
\end{array}
\end{eq*}
agree. It follows from
\begin{eq*}
\D =y_2=y_4=\dots
\end{eq*}
and
\begin{eq*}
\U=y_{s-1}=y_{s-3}=\dots
\end{eq*}
that $s$ is even, say $s=2\ell$ for some $\ell\in\NN$, and $y=(\U\D)^{\ell}$.
The assumption that the $j$-th $\D$-step in $\pi$ occurs after the $k_i$-th $\U$-step implies $\ell>0$.
Moreover $x=\U^r$ and $z=\D^t$ for some $r,t\in\NN$.
We have
\begin{eq*}
i-k_i
=\nup(\alpha )-\ndown(\alpha \U x)
=\nup(\alpha )-\ndown(\alpha ).
\end{eq*}
Thus $\alpha $ ends at height $i-k_i$.
Similarly
\begin{eq*}
j-k_j
=\nup(\alpha xy)-\ndown(\alpha xy\U z)
=\nup(\alpha xy\U z\D)-\ndown(\alpha xy\U z\D).
\end{eq*}
Thus $\beta $ starts at height $j-k_j$.
\end{proof}

\begin{figure}
	\centering
	\input{figures/fig_lemma_covers}
	\caption{The two situations described in Lemma \ref{Lemma:double_cover}}
	\label{fig:lem_covers}
\end{figure}

\subsection{Lower covers}
\label{ssec:lb}
Our  goal in this subsection is to describe  and count the elements of the
 set $\lcov{}{\pa}$ of lower covers of $\pa$. To this end, we write $\de{s}{k_s}$
 where $k_s\in\{s,s-1\}$ and we group the lower covers of
$\pa$ according to the ascent from which we delete a $\U$-step.
More precisely, for each ascent $\U^{a_i}$ we define the set $\lcov{i}{\pa}\subseteq\dP{n}$
as follows:
\begin{equation}
\begin{aligned}
 \lcov{1}{\pa}:=&\{\de{s}{k_s}(\pa) \text{ for }
 1\leq{s}\leq{a_1}\}  \hspace{5cm}\text{ if } i=1\\
  \lcov{i}{\pa}:=&\{\de{s}{k_s}(\pa) \text{ for }
  a_1+\cdots+a_{i-1}+1\leq{s}\leq{a_1+\cdots+a_{i}}\} \;\;\; \text{ if\; }
  2\leq{i}\leq{\ell}.
 \end{aligned}
  \label{setlci}
  \end{equation}
  Clearly, the lower  covers of $\pi$ are all paths in the union
 \begin{align}
 \label{lcovers}
 \lcov{}{\pi}\,=  \bigcup_{i=1}^{\ell}   \lcov{i}{\pi}.
 \end{align}
 To describe the paths in each $\lcov{i}{\pa}$
 with respect to the original path $\pa$, notice that the
  range of  $s$ for  $\de{s}{k_s}(\pa)\in\lcov{i}{\pa}$
 is the index of all  $\U$-steps $\U_s$ in $\U^{a_i}$.
  Since  $\de{s}{k_s}(\pa)$  acts by deleting the pair $\U_s,\D_{k_s}$
  with $k_s\in\{s,s-1\}$, we deduce that
  all    paths $\pa'\in\lcov{i}{\pa}$ are obtained from $\pa$
     by replacing $U^{a_i}$ with $\U^{a_i-1}$ and deleting
     a $\D$-step $\D_{s'}$ where
  \begin{equation}
  \begin{aligned}

   1\leq{s'}\leq{a_1}  \hspace{1.7cm} &\text{ if\; } i=1 \;\;\;\;  \text{ or }
   \\
   a_1+\cdots+a_{i-1}\leq{s'}\leq{a_1+\cdots+a_{i}} &\text{ if \;}
   2\leq{i}\leq{\ell}.
  \end{aligned}
  \label{setlci2}
  \end{equation}
    This means that the range of possible $\D$-step deletions in
    $\lcov{i}{\pa}$
    is precisely the set of $\D$-steps of the  subpath $\overline \pa_i$
    described in       \eqref{equ:pi}.
 In other words, $\lcov{i}{\pa}$
is  the  set of  paths obtained from $\pa$ after deleting a
$\U$-step from the $i$-th ascent $\U^{a_i}$ and a $\D$-step from $\overline\pa_{i}$.

\begin{figure}
	\input{figures/fig_arm_leg}
	\caption{The path $\pi=\U^3\D\U^2\D^2\U\D\U\D^3$
		and the subpaths $\overline\pa_{i}$ defined in \eqref{equ:pi}. }
	\label{figci}
\end{figure}

\begin{lemma}
  Let  $\pi=\U^{a_1}\D^{b_1}\ldots\U^{a_\ell}\D^{b_\ell}$ be a Dyck path
  in $\dP{n+1}$.
  \begin{enumerate}[(i)]
 \item If $\pi$ is strongly irreducible with
 $\pi\not=\U^a(\D\U)^{n+1-a}\D^{a}$,

  the sets in the union \eqref{lcovers} are pairwise disjoint.
 \item If  $\pi=\U^a(\D\U)^{n+1-a}\D^{a}$ with  $2<a<n+1$ then
 the sets in the union \eqref{lcovers} are pairwise disjoint
 except for $\lcov{1}{\pa}$ and $\lcov{\ell}{\pa}$
 which both contain the path $\U^{a}(\U\D)^{n-a}\D^{a}$.
  \end{enumerate}
\label{lem:ULi_disjoint}
\end{lemma}

\begin{proof}
Let $i<j$ and suppose that $\pi'\in\lcov{i}{\pa}\cap\lcov{j}{\pa}$.
Then $\pi'$ can be obtained from $\pi$ by two bounce deletions $\de{I}{k_I}$ and $\de{J}{k_J}$ such that the $I$-th and $J$-th $\U$-steps of $\pi$ do not belong to the same acsent of $\pi$.
By Lemma~\ref{Lemma:double_cover} this implies that $\pi$ is of the form $\pi=\alpha U^r(DU)^{\ell}D^t\beta$ for some words $\alpha,\beta\in\{\U,\D\}^*$, and $r,\ell,t\in\NN$ with $\ell>0$, such that $\alpha$ ends at height $I-k_I \in\{0,1\}$, and $\beta$ starts at height $J-k_J \in\{0,1\}$.
If $\pi$ is strongly irreducible
then  the only possibilities for the words $\alpha, \beta$ are
 $\alpha=\U$ if $k_I=I-1$  or $\alpha$ is empty if $k_I=I$.
Similarly $\beta=\D$ if $k_J=J-1$ and $\beta$ is empty if $k_J=J$.
The claims follow.
\end{proof}

\begin{figure}
	\centering
	\input{figures/covers}
	\caption{The tableau $T$ corresponding to the path $\pa=\U\U\U\D\U\D\U\U\D\U\D\D\D\D$ and  its lower covers.
		Since $\pa$ is irreducible and  has four ascents, its lower covers are divided into
		four pairwise disjoint sets $\lcov{i}{\pa}$ as follows.
		The first tree lower covers belong to $\lcov{1}{\pa}$, the next two in $\lcov{2}{\pa}$,
		the next in $\lcov{3}{\pa}$ and the last one in $\lcov{4}{\pa}$.
	}
	\label{fig:covers}
\end{figure}

Using the above lemma, we can prove the following proposition,
which counts the number of lower covers of all strongly irreducible Dyck paths.
\begin{theorem}
  \begin{enumerate}[(i)]
  \item[]
  \item
 If $\pi\in\dP{n+1}$ is strongly irreducible, the number of its lower covers
   is     $$|\lcov{}{\pi}|=|peaks(\pi)| +|valleys(\pi)|$$
   unless $\pi=\U^a(\D\U)^{n+1-a}\D^{a}$ for some $a>2$
   in which case
   $$|\lcov{}{\pi}|=|peaks(\pi)| +|valleys(\pi)|-1=2(n+1-a).$$
\item  If $\pa=(\U\D)^{n+1}$ or $\pa=\U^{n+1}\D^{n+1}$ then
$|\lcov{}{\pa}|=1$.
\item
 If $\pa=\U(\U\D)^{n}\D$ and $n>0$ then $|\lcov{}{\pa}|=n$.
   \end{enumerate}
  \label{theor:UCclosedfor}
   \end{theorem}
\begin{proof}
  To prove (i), recall that all  Dyck paths in $\lcov{i}{\pa}$ are
 obtained from $\pa$ by replacing $U^{a_i}$ by $\U^{a_i-1}$  and deleting a
 $\D$-step from $\overline \pa_{i}$. The different ways to delete
 a $\D$-step from $\overline\pa_i$
 are  as many as the ways to
  delete a $\D$-step from a different descent of $\overline\pa_i$,  which implies that
 $|\lcov{i}{\pi}|=|{descents}(\overline\pa_{i})|$.
 Therefore, in view of Lemma \ref{lem:ULi_disjoint},
 we have that   $|\lcov{}{\pa}|=  \sum_{i=1}^{\ell}|\lcov{i}{\pa}|=
 \sum_{i=1}^{\ell}|descents(\overline\pa_i)|$.
Next, notice that for all pairs $i,j$ we have $\overline \pa_i\cap
\overline\pa_j=\emptyset$ except for $j=i+1$ where
$\overline\pa_i\cap\overline\pa_{i+1}=
\pa\cap\col{a_1+\cdots+a_i}$.

In other words, $\overline \pa_i, \overline \pa_{i+1}$
share a column and thus a descent.
We can therefore rewrite the above sum as
 $|\lcov{}{\pa}|= |descents(\pa)|+ \ell-1=2\ell-1=|peaks(\pi)| +|valleys(\pi)|$.

 For (ii), it is immediate to see that the unique lower cover of $(\U\D)^{n+1}$
 and $\U^{n+1}\D^{n+1}$  is $(\U\D)^n$ and $\U^n\D^n$ respectively.
 For (iii), we leave it to the reader to check that the lower covers of
 $\pa=\U(\U\D)^n\D$ are  the paths obtained from
 $\pa$
 by replacing a $\U\D\U\D$ by $\D\U$,
 or the path $\U(\U\D)^{n-1}\D$, which are altogether $n$.
\end{proof}

An {\em irreducible decomposition}
$\pa=\pa_1\oplus\pa_2\oplus\cdots\oplus\pa_k$
of a Dyck path $\pi$ is the way to write $\pa$ as a concatenation of Dyck paths
$\pa_i$, where each $\pa_i$ is either an irreducible Dyck path
  or a, possibly empty, sequence of peaks  at height $1$\footnote{
  i.e., we     count the  common endpoint between two consecutive
  irreducible components as a component itself.
We refer to it as an {\em empty } component.}.  In the first case we
  say that   $\pi_i$ is an {\em irreducible component}
  and in the latter  a {\em connecting component} of $\pa$.

 If $\pa_1,\pa_3$ are irreducible Dyck paths
and $\pa_2$ is a sequence of $k$ peaks at height 1,
we abbreviate $\pa_1\oplus\pa_2\oplus\pa_3$ as
 $\pa_1\oplus_{k}\pa_3$ (see Figure \ref{fig:decomp}).
Next, we introduce the symbol $\oplus'$ to denote concatenation of paths whose unique common
point lies on $y=x+1$. More precisely, a {\em strongly irreducible decomposition} of an  {\em irreducible} Dyck path $\pi$
is a way to write $\pi=\U\pa_1\oplus'\pa_2\oplus'\cdots\oplus'\pa_k\D$ as a
concatenation of paths $\pa_i$,
 where each $\U\pa_i\D$ is either  a strongly irreducible Dyck path  or a
 non empty  sequence of  peaks  at height $2$

 (see Figure  \ref{fig:decomp2}). We separate
 the components  of a strongly irreducible decomposition
 to {\em strongly irreducible} and
 {\em  connecting} ones.
 We also abbreviate $\U\pa_1\oplus'\pa_2\oplus'\pa_3\D$\; to\; $\U\pa_1\oplus_{k}'\pa_3\D$
in the case where $\U\pa_2\D$ is a sequence of $k$ peaks at height 2.

\begin{figure}
  \input{figures/irred_components1}
  \caption{The irreducible decomposition of a path.
The second and fourth components are connecting components while all others are irreducible components.
}
  \label{fig:decomp}
\end{figure}

\begin{figure}
	\input{figures/irred_components2}
	\caption{Decomposition of an irreducible path into its  strongly
		irreducible components.}
	\label{fig:decomp2}
\end{figure}

\begin{theorem}
  \begin{enumerate}[(i)]
    \item   If $\pa$ is a Dyck path with  irreducible decomposition
    $\pa=\pa_1\oplus\pa_2\oplus\cdots\oplus\pa_k$ then
 \begin{align}
 |\lcov{}{\pa}|=k'+
\sum_{\substack{\pi_i\text{ irreducible}\\\text{component}
}}\!\!\!|\lcov{}{\pa_i}|.
 	\label{equ:ucdecom}
 \end{align}
       where $k'$ is the number of  connecting components of $\pa$,  including the empty ones, i.e., those consisting of a simple point.
       \medskip
    \item
    If $\pa$ is an irreducible  Dyck path with strongly  irreducible
    decomposition   $\pa=\U\pa_1\oplus'\cdots\oplus'\pa_{k}\D$
     then
    \begin{align}
    |\lcov{}{\pa}|&=
    k-1 +\sum_{i=1}^{k} |\lcov{}{\U\pi_i\D}|  \label{equ:str_irr}  \\
     &=
    k-1 +\sum_{\substack{
    		\U\pi_i\D\\
    		\text{ strongly}\,\,\,\,\,\\
        \text{irreducible }}}\!\!\!\!\!\!  |\lcov{}{\U\pi_i\D}|+
    \sum_{\substack{\U\pi_i\D=\\\U(\U\D)^{k_i}\D}}  k_i.
    \label{equ:str_irr2}
    \end{align}
  \end{enumerate}
\end{theorem}
\begin{proof}
  For (i), it is easy to see that the lower covers of $\pa$ are obtained
  either by applying a bounce deletion on an irreducible component or
  on a nonempty connecting component. In other words,
  no  bounce deletion deletes steps from different components. From the first we get $\sum_{i=1}^{k}
  |\lcov{}{\U\pi_i\D}|$ possible lower covers  and from the latter we get one lower cover
  for each   connecting  component. This leads to \eqref{equ:ucdecom}.

  For (ii), the lower covers of $\pa$ belong to one of the following
   categories: either  they occur from bounce deletions on a single
   component $\U\pa_{i}\U$ (either strongly irreducible or of type $\U(\U\D)^{k_i}\D$)
    or they interact between two consecutive components
 by deleting the last  $\U$-step of   $\U\pa_i\D$ and the first  $\D$-step of $\U\pa_{i+1}\D$
 (as the deletion shown in Figure \ref{fig:decomp2} on the left).
   More precisely,
   if $(a-1,a)$ is the common endpoint between the two consecutive components
   $\pa_i\oplus'\pa_{i+1}$ then $\de{a}{a}(\pa)$ is such  a lower cover.
   The first case contributes $\sum_{i=1}^{k} |\lcov{}{\U\pi_i\D}|$ and
   the second contributes $k-1$,  in the total number \eqref{equ:str_irr} of
  lower covers  of $\lcov{}{\pa}$.
   We can further refine \eqref{equ:str_irr} to  \eqref{equ:str_irr2}
by distinguishing the type of each component $\pa_i$.
\end{proof}

\subsection{Upper covers}
\label{ssec:ub}
Our next goal is the  computation of the upper covers of a Dyck path
$\pa\in\dP{n+1}$.
To do so,  we have to consider all the ways to  insert a
$U$ and a $D$-step in $\pi$ so that the resulting path $\pa'$ is a Dyck
path in $\dP{n+2}$ satisfying $\de{j}{k_j}(\pa')=\pa$ for some $j=1,\ldots,n+2$ and $k_j\in\{j-1,j\}$.
In view of the definition of $\de{j}{k_j}$, if
the inserted $\U$ is the $j$-th $\U$-step of the new path
$\pi'$ then the inserted $\D$ should be  either  the  $j$-th or the
$(j-1)$-st $\D$-step of
$\pa'$.
Described more graphically,
if $p=(x,j-1)$ is  the integer point
(other than  $(0,0)$ or $(n+1,n+1)$) where we insert the new $\U$-step, the range of possible insertions of the new  $\D$-step  is  the  subpath $\pa\cap\col{j-1}$  contained in the $(j-1)$-th column of  $\pa$.
We can describe the above as a {\em bounce insertion}: we draw a
 horizontal line starting at the point $p$
 at which we want to insert $\U$,
  until it hits the main  diagonal  and then we turn vertically up
  selecting the portion of the path contained in the
   column at which the horizontal line terminated.
 The selected subpath is the range of insertion of $\D$, i.e., if we insert a $\U$-step at $p$ then  we can insert a $\D$-step at any integer point of the above subpath  (see Figure  \ref{fig:bounce_insert}).
 If $p=(i,i)$, $1\leq{i}\leq{n}$, is on the main diagonal, then the bounce insertion described
 above reduces to selecting the portion of the path at  column $\col{i}$, i.e., $\pa\cap\col{i}$.
 Trivially,  if $p=(0,0)$ or $(n+1,n+1)$ the only possibilities are to insert $\U\D$ at $p$.

 \begin{figure}
 	\input{figures/fig_upper_covers}
 	\caption{Bounce insertions:
 		if we add a $\U$-step at  $(x,j-1)\in\pa$ and a $\D$-step at any integer
 		point of $\pa\cap{\col{j-1}}$, the resulting path $\pa'$
 		satisfies $\de{j}{k_j}(\pa')=\pa$
 		for some $k_j\in\{j-1,j\}$.   	}
 	\label{fig:bounce_insert}
 \end{figure}

  \smallskip

We next assume that  $\pa$ is strongly irreducible and we group
all its upper covers  according to the $x$-coordinate of the integer  point
where we insert the new $\U$-step.
 This can be further partitioned into the case where
 we insert a new $\U$-step at an ascent $\U^{a_i}$ or the case where we
 insert a
 new $\U$-step between two consecutive $\D$-steps of a descent $\D^{b_i}$ of
 $\pa$.
Altogether, we have the  following possibilities for the upper covers of
$\pa$:
\medskip

\noindent
  (i)
  $\ucov{1}{\pa}$ is the set of upper covers of  $\pa$ obtained by inserting the new $\U$-step at some integer point of    $\U^{a_1}$.
  In this case, the range of possible insertions of  the new  $\D$-step  is the set of all  integer points  of   the   subpath   of $\pa$ contained in the first $a_1$ columns,
  i.e., the subpath  $\pa\cap(\cup_{s=1}^{a_i}\col{s})=\overline \pa_1$.   \\

  \noindent
  (ii) $\ucov{i}{\pa}$, $2\leq{i}\leq{\ell}$,  is the set of upper covers of
  $\pa$ obtained by inserting the new $\U$-step at an integer point of  $\U^{a_i}$.
  Since the endpoints of $\U^{a_i}$ have coordinates
    $(b_1+\cdots+b_{i-1},a_1+\cdots+a_{i-1})$,   $(b_1+\cdots+b_{i-1},a_1+\cdots+a_{i})$
      the range of possible insertions of the new $\D$-step is the set of all integer points
  on the  subpath
  $\pa\cap(\cup_{s=0}^{a_i}\col{a_1+\cdots+a_{i-1}+s})=\overline \pa_i$.

\noindent
   (iii)
   $\ucovv{i}{\pa}$, $1\leq{i}\leq{\ell}$, is the set of upper covers of
  $\pa$ obtained by inserting a new $\U$-step   between  a double descent
  $\D\D$ of   $\D^{b_i}$. If $\D^{b_i}$ consists of a single descent, i.e.,
   $b_i=1$, then clearly $\ucovv{i}{\pa}=\emptyset$.
  If $b_i>1$, let $(x_{\circ},y_{\circ})$
   be the point between  a double descent   of $\D^{b_i}$. Clearly   $y_{\circ}=a_1+\cdots+a_i$ which further implies that, when inserting a new $\U$ at  $(x_{\circ},y_{\circ})$,
   the range of all possible   insertions of the new $\D$-step is the set of all integer points on  the subpath $\pa\cap\col{a_1+\cdots+a_i}$
  of $\pa$ contained in the $(a_1+\cdots+a_i)$-th column  of the underlying tableau.

  \noindent
  (iv)
  $\ucovv{\ell+1}{\pa}$ is the set containing the unique upper cover of
  $\pa$ we obtain by inserting  a $\U$-step (and a $\D$-step) at the end of the
  path $\pa$.  In other words,
  $\ucovv{\ell+1}{\pa}=\{\U^{a_1}\D^{b_1}\ldots\U^{a_\ell}\D^{b_\ell}\U\D\}.$
\medskip

Finally,
since $\pa$ is strongly  irreducible it is not hard to see that all paths
in the sets $\ucov{i}{\pa}$ and $\ucovv{i}{\pa}$ are again Dyck paths.
\begin{figure}
  \input{figures/fig_upper_coversUC}
  \caption{
     The set $\ucov{3}{\pa}$ contains all paths obtained by increasing the third ascent
     from $\U^2$ to $\U^3$ and inserting a $\D$-step at any integer point on the indicated subpath.
    }
  \label{fig:bounce_insertUC}
\end{figure}
We, therefore, conclude that the upper covers of a strongly
irreducible Dyck  path  $\pi$ are all paths in the  union
\begin{equation}
\displaystyle
  \ucov{}{\pa}=\bigcup_{i=1}^{\ell}
  \ucov{i}{\pa}\cup\bigcup_{i=1}^{\ell+1}
  \ucovv{i}{\pa}.
\label{ucovers}
\end{equation}
\medspace

The following lemma is the analogous of Lemma \ref{lem:ULi_disjoint} in the case of the upper covers.
\begin{lemma}
\begin{enumerate}[(i)]
  \item[]
  \item If $\pi'\not=\U^a(\D\U)^{n+1-a}\D^{a}$ is strongly irreducible then
    the sets $\ucov{i}{\pa'}, \ucovv{j}{\pa'}$ are pairwise disjoint.
    \item If  $\pi'=\U^a(\D\U)^{n+1-a}\D^{a}$ with  $a>{2}$ then
  the sets $\ucov{i}{\pa'}, \ucovv{j}{\pa'}$ are pairwise disjoint
   except for $\ucov{1}{\pa'}$ and $\ucov{\ell}{\pa'}$
   which both contain the path  $\U^{a}(\D\U)^{n+2-a}\D^{a}$.
\end{enumerate}
\label{lem:UCi_disjoint}
\end{lemma}

\begin{proof}
	Suppose that $\pa$ lies in the intersection of two distinct sets among sets
$\ucov{i}{\pa'}$ and $\ucovv{j}{\pa'}$.
	Then $\pa'$ can be obtained from $\pa$ by two different bounce deletions $\de{I}{k_I}$ and $\de{J}{k_J}$ such that the $I$-th and $J$-th $\U$-steps of $\pa$ do not belong to the same ascent of $\pa$.
By Lemma~\ref{Lemma:double_cover} this implies that $\pa$ is of the form $\pa=\alpha U^r(DU)^{\ell}D^t\beta$ for some words $\alpha,\beta\in\{\U,\D\}^*$, and $r,\ell,t\in\NN$ with $\ell>0$, such that $\alpha$ ends at height $I-k_I$, and $\beta$ starts at height $J-k_J$.
Moreover $\pa'=\alpha U^r(DU)^{\ell-1}D^t\beta$.
If $\pa'$ is strongly irreducible we obtain that $\alpha=\U$ if $k_I=I-1$ and $\alpha$ is empty if $k_I=I$.
Similarly $\beta=\D$ if $k_J=J-1$ and $\beta$ is empty if $k_J=J$.
The claims follow.
\end{proof}

 Using the fact that the sets in the union \eqref{ucovers} are disjoint if $\pa$ is strongly irreducible, we  arrive at a closed formula for $|\ucov{}{\pa}|$.
In what follows,  we use the notation $\#\U(\pa)$ for the number of
$\U$-steps of the path $\pa$.
  \begin{theorem}
 Let $\pa=\U^{a_1}\D^{b_1}\cdots\U^{a_\ell}\D^{b_\ell}$ be a Dyck path in $\dP{n+1}$.
  \begin{enumerate}[(i)]
    \item If $\pi\in\dP{n+1}$ is strongly  irreducible with
     $\pi\not=\U^a(\D\U)^{n+1-a}\D^{a}$,
   the  number of its upper covers is
   \begin{align}
   \label{up_irred}
 |\ucov{}{\pa}|= 2n+3+\sum_{ i=1 }^{\ell-1} b_i\cdot
 \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr).
    \end{align}
 \item  If  $\pi=\U^a\D\U\cdots\D\U\D^{a}$ with $a\geq{2}$,  then
    $|\ucov{}{\pa}|$
  is given by \eqref{up_irred} reduced by 1.

\item  If $\pi=(\U\D)^{n+1}$ or $\pa=\U^{n+1}\D^{n+1}$ then
$|\ucov{}{\pa}|=2(n+1)$.
\item
If $\pi=\U(\U\D)^{n}\D$ then $|\ucov{}{\pa}|=4n-5$.
\end{enumerate}
\label{prop:uc}
\end{theorem}

\begin{proof}
  If  $\pi\not=\U^a\D\U\cdots\D\U\D^{a}$ is strongly irreducible then
  the sets in \eqref{ucovers} are disjoint, hence we have

  \begin{align}
   |\ucov{}{\pa}| &
   =\sum_{i=1}^{\ell}|\ucov{i}{\pa}|+\sum_{i=1}^{\ell+1}
   |\ucovv{i}{\pa}|
   =1+\sum_{i=1}^{\ell}|\ucov{i}{\pa}|+\sum_{i=1}^{\ell}
   |\ucovv{i}{\pa}|. \label{i}
   \end{align}
   Each set $\ucov{i}{\pa}$ has as many elements as there are ways to insert
   a $\D$-step  in $\overline\pa_i$.
   The different ways to insert a $\D$ in any path
   are, either to insert a $\D$ in the beginning of the path or
    to insert a $\D$ immediately after a $\U$-step.
    This implies that $ |\ucov{i}{\pa}|=\#U(\overline\pa_i)+1$.
    Likewise, by the definition of $\ucovv{i}{\pa}$ (see  \eqref{ucii}) since for each double
     descent  $\D\D$ in $\D^{b_i}$   the range of possible ways to insert a new $\D$-step is the subpath     $\pa\cap\col{a_1+\cdots+a_i}$,
    we conclude that the sum in \eqref{i} becomes:
   \begin{align}
        |\ucov{}{\pa}|

        &= 1+
   \sum\limits_{i=1}^{\ell}\bigl(\#U(\overline\pa_i)+1\bigr)
    +\sum_{ i=1 }^{\ell} (b_i-1)
    \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})+1\bigr) \notag\\
     & = 1+\sum_{i=1}^{\ell}b_i+
    \sum\limits_{i=1}^{\ell}\#U(\overline\pa_i)
    +\sum_{ i=1 }^{\ell} (b_i-1)
    \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr) \notag\\
    & = 1+(n+1)+
    \sum\limits_{i=1}^{\ell}\#U(\overline\pa_i)
    +\sum_{ i=1 }^{\ell} (b_i-1)
    \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr). \label{ii}
    \end{align}
     Counting the $\U$-steps of each $\overline \pa_i$  on each vertical line $x=s$ and taking into account that
     the $\U$-steps in each $\overline\pa_i\cap\overline\pa_{i+1}=\pa\cap
     \col{a_1+\cdots+a_i}$ are
     counted twice, we have
     \begin{align*}
           \sum\limits_{i=1}^{\ell}\#U(\overline\pa_i)=
           \sum_{s=0}^{n+1}
           \Bigl(\#\U(\pa\cap\{x=s\})\Bigr)
           +\sum_{ i=1 }^{\ell-1}
           \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr).
      \end{align*}
    Thus,  we continue from
     \eqref{ii} as
    \begin{align}
     &  n+2+ \sum_{s=0}^{n+1}
    \Bigl(\#\U(\pa\cap\{x=s\})\Bigr)
    +\sum_{ i=1 }^{\ell-1}
    \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr)
    +\sum_{ i=1 }^{\ell} (b_i-1)
    \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr) \label{b} \\
     & =\,   2 n+3 +\sum_{ i=1 }^{\ell-1} b_i
       \bigl(\#\U(\pa\cap \col{a_1+\cdots+a_i})\bigr), \label{bb}
    \end{align}
    where, to go from \eqref{b} to \eqref{bb}, we used the fact that
    the total number of $\U$-steps in the first sum of \eqref{b} is $n+1$, and that
    the last column  has no $\U$-steps (i.e., $\#\U(\pa\cap \col{a_1+\cdots+a_\ell})=0$).

The claim in $(ii)$  is straightforward from Lemma\ref{lem:UCi_disjoint}(ii).

For $(iii)$, it is not hard to see that  all the upper covers of
$(\U\D)^{n+1}$ are  obtained either  by replacing a $\U\D$ by
$\U^2\D^2$,
or a $(\U\D)^2$ by $\U(\U\D)^2\D$,  or  $(\U\D)^{n+2}$.
In the case where $\pa=\U^{n+1}\D^{n+1}$, the upper covers  are either $\U^k\D\U^{n+2-k}\D^{n+1}$ for $1\leq{k}\leq{n+2}$, or $\U^{n+1}\D^k\U\D^{n+2-k}$ for $2\leq{k}\leq{n+1}$.

Finally, for $(iv)$,  the upper covers
$\pa'\in\ucov{}{\pa}$  of $\pa=\U(\U\D)^n\D$ fall in one of the following
categories:
\begin{enumerate}[(i)]
  \item $\pa'=\U(\U\D)^{n+1}\D$,
  \item $\pa'$ is obtained from $\pa$
  by increasing a $\D\U$ to $\D^2\U^2$,
  \item $\pa'$ is obtained from $\pa$
   by increasing a $\U\D$ to $\U^2\D^2$,
    \item $\pa'$ is obtained from $\pa$
     by increasing a $\U\D\U\D$ to $\U^2\D\U\D^2$,
    \item $\pa'$ is obtained from $\pa$
     by increasing a $\D\U\D\U$ to $\U^2\U\D\U^2$.
 \end{enumerate}
All the above,  sum up to $4n-5$ possible upper coves.
\end{proof}
\medspace

\begin{remark}
 The sum in \eqref{up_irred} can be easily  computed as follows.
 Extend each descent $\U^{b_i}$ of  $\pa$  until it hits
    the   line $x=y$ and turn vertically up  selecting the subpath
   in the column   at which the extended descent terminated.
This is  the subpath
$\pa\cap\col{a_1+\cdots+a_i}$ whose number of $\U$-steps is  multiplied by
$b_i$ in \eqref{up_irred} (see, for example, \ref{fig:UCformula}(a)).
\label{remark:UC}
\end{remark}

\begin{figure}
  \input{figures/fig_upper_formula}
  \caption{(a)
  	In view of Remark \ref{remark:UC}, the number of upper covers of the path on the left
  	is $|\ucov{}{\pa}|=(2\cdot10+3)+(2\cdot{2}+1\cdot{1}+3\cdot{2}+1\cdot{0})$.}
    \label{fig:UCformula}
\end{figure}
\medspace

The computation of the number of upper covers  of an arbitrary Dyck path $\pa$
is recursive. Unlike the case with the lower covers, we cannot have an explicit formula of
$|\ucov{}{\pa}|$  in terms of
the upper covers of the irreducible components of $\pa$, since
there exist  upper covers that occur
by inserting a $\U$-step in a component of $\pa$ and a $\D$-step in the subsequent one.

In the following proposition we
use the notation $\oplus,\oplus'_1$ without requiring that the components are
irreducible. In other words, $\pa_1\oplus \pa_2$ is the concatenation of any two  Dyck paths
 $\pa_1,\pa_2$.
  If $\U\pa_1\D,\U\pa_2\D$ are Dyck paths
      then  $\U\pa_1\oplus' \pa_2\D$ is the  concatenation  of $\U\pa_1,\pa_2\D$,
      whereas
$\U\pa_1\oplus'_1 \pa_2\D $ is the concatenation of $\U\pa_1\U$ and $\D\pa_2\D$.

\begin{theorem}
  \begin{enumerate}[(i)]
    \item[]
    \item   If $\pa_1,\pa_2$ are Dyck paths and $\pa=\pa_1\oplus\pa_2$ then
        \begin{align}
        |\ucov{}{\pa}|=|\ucov{}{\pa_1}|+|\ucov{}{\pa_2}|-1+b\cdot{a}
        \label{equ:ub1}
        \end{align}
     where $\D^{b}$ is the last descent of $\pa_1$
    and $\U^a$ is the first ascent of $\pa_2$.
          \item   If  $\pa=\U\pa_1\oplus'_{1}\pa_2\D$ then
           \begin{align}
|\ucov{}{\pa}|=|\ucov{}{\U\pa_1\D}|+|\ucov{}{\U\pa_2\D}|+(b+1)(a+1)
           \label{equ:ub2}
           \end{align}
 where $\D^{b+1}$ is the last descent of $\U\pa_1\D$
and $\U^{a+1}$ is the first ascent of $\U\pa_2\D$.

      \item[(iii)]
        If  $\pa=\U\pa_1\oplus'\pa_2\D$ with $\U\pa_1\D,\U\pa_2\D$ strongly irreducible Dyck paths
        then
      \begin{align}
   |\ucov{}{\pa}|=|\ucov{}{\U\pa_1\D}|+|\ucov{}{\U\pa_2\D}|-2+a'b+ab+ab'
   \label{equ:ub3}
   \end{align}
 where $\D^{b'}\U\D^b$ is the subpath in the last row of
$\U\pa_1\D$ and
$\U^{a}\D\D^{a'}$ is the subpath in the first column of $\U\pa_2\D$.
    \end{enumerate}
     \label{prop:UCdecomp}
  \end{theorem}
  \begin{proof}

For (i), first notice that all Dyck paths  of the form
$\pa'\oplus\pa_2$ with $\pa'\in\ucov{}{\pa_1}$ or  the form
$\pa_1\oplus\pa'$ with
$\pa'\in\ucov{}{\pa_2}$ are upper covers of $\pa$.
Since  the upper cover $\pa_1\U\D\pa_2$ occurs in both cases,
we have   $|\ucov{}{\pa_1}|+|\ucov{}{\pa_2}|-1$  such paths.

We next need to count the upper covers that occur by inserting a $\U$-step
in $\pa_1$ and a $\D$-step in $\pa_2$ and are not encountered in the previous cases.
Assume that  $p=(k,k)$ is the intersection  point of $\pa_1,\pa_2$ (see
Figure \ref{fig:UCformula}(b)).
Viewing these upper covers in terms of bounce insertions, one can
see that these are  the paths we get by  inserting a $\U$-step
at any integer point, other than $p$, of the last descent of $\pa_1$
(light blue, Figure \ref{fig:UCformula}(b))
and  a $\D$-step at any integer point, other than $p$, of the first ascent of
$\pa_2$ (light gray, Figure \ref{fig:UCformula}(b)).
This contributes the term $b\cdot{a}$  in \eqref{equ:ub1}.

For (ii), notice that  all Dyck paths  of the form
$\U\pa'\oplus'_1\pa_2\D$ where
$\U\pa'\D\in\ucov{}{\U\pa_1\D}$ or of the form $\pa_1\oplus'_1 \pa'$ where
$\U\pa'\D\in\ucov{}{\U\pa_2\D}$ are upper covers of $\pa$.
This contributes $|\ucov{}{\pa_1}|+|\ucov{}{\pa_2}|$ in \eqref{equ:ub2}.
As before, we also have to count the upper covers
that occur by inserting a $\U$-step in $\pa_1$ and a $\D$-step in $\pa_2$.
Viewing these upper covers in terms of bounce insertions,  these are all
paths we get by  inserting a $\U$-step
at any integer point  of the last descent of $\pa_1$
(light blue, Figure \ref{fig:UCformula}(c))
and  a $\D$-step at any integer point  of the first ascent of $\pa_2$ (light
gray, Figure \ref{fig:UCformula}(c)).
This contributes  $(b+1)(a+1)$  in \eqref{equ:ub2}.

For (iii),

in order to compute $|\ucov{}{\pa}|$,   notice that
all Dyck paths  of the form
$\U\pa'\oplus'\pa_2\D$ with $\U\pa'\D\in\ucov{}{\U\pa_1\D}$ or  of the form $\U\pa_1\oplus'\pa'\D$ with
$\U\pa'\D\in\ucov{}{\U\pa_2\D}$ are upper covers of $\pa$.
Since  the upper covers $\U\pa_1\U\D\pa_2\D$
and  $\U\pa_1\D\U\pa_2\D$
occur in both instances, we have a total of $|\ucov{}{\pa_1}|+|\ucov{}{\pa_2}|-2$
contributed in \eqref{equ:ub3}.

We next count all upper covers
that occur by inserting a $\U$-step in $\pa_1$ and a $\D$-step in $\pa_2$.
Viewing these upper covers in terms of bounce insertions, we have two categories: \\
a) we insert a
$\U$-step in one of the first $b'$ integer points  of the last but one descent  $\D^{b'}$  of $\pa_1$ (i.e., points
\tikz{\draw[line width=0.7pt] (0,0) circle (2.5pt);}
in Figure \ref{fig:UCformula}(c)) and insert a $\D$-step in one of the last $a$ integer points of
the first ascent $\U^a$  of $\pa_2$
(i.e.,  points
\tikz{\draw[line width=0.7pt,black] (0,0) rectangle (.15,.15);} in Figure \ref{fig:UCformula}(c)). This contributes $a\cdot b'$ upper covers in \eqref{equ:ub3},  or \\
b) we insert a  $\U$-step in one of the first $b$ integer points  of
the last descent $\D^{b}$ of $\pa_1$ (i.e., points
\tikz{\draw[line width=0.7pt,fill=gray] (0,0) circle (2.5pt);}
in Figure \ref{fig:UCformula}(c)) and  insert a $\D$-step in one of
the last  $a$ integer points of $\U^a$  or the last  $a'$ integer points of $\U^{a'}$
(i.e.,  points
\tikz{\draw[line width=0.7pt,black] (0,0) rectangle (.15,.15);}
or  \tikz{\draw[line width=0.7pt,black,fill=gray] (0,0) rectangle (.15,.15);}
in Figure \ref{fig:UCformula}(c)). This contributes $b\cdot (a+a')$ upper covers in \eqref{equ:ub3}.
  \end{proof}

\begin{example}\rm  In  Figure  \ref{fig:UCformula}
	\begin{itemize}
		\item[(b)]
		we depict the path $\pa=\pa_1\oplus\pa_2$ for   $\pa_1=\U^4\D^2\U\D^3$ and $\pa_2=\U^4\D\U\D^4$.
		Using Theorem \ref{prop:uc} we compute
		$|\ucov{}{\pa_1}|=11$ and  $|\ucov{}{\pa_2}|=10$.
		In view of Theorem \ref{prop:UCdecomp}(i), we  have $|\ucov{}{\pa}|=11+10+3\cdot4-1=32$.
		\item[(c)]
		we depict the path $\pa=\U\pa_1\oplus'_1\pa_2\D$ for   $\U\pa_1\D=\U^4\D^2\U\D^3$ and $\U\pa_2\D=\U^4\D\U\D^4$. In view of Theorem \ref{prop:UCdecomp}(ii) we have  $|\ucov{}{\pa}|=11+10+3\cdot4=33$
		\item[(d)]
		we depict the path $\pa=\U\pa_1\oplus'\pa_2\D$ for   $\U\pa_1\D=\U^4\D^2\U\D^3$ and $\U\pa_2\D=\U^4\D\U\D^4$. In view of Theorem \ref{prop:UCdecomp}(iii) we have   $|\ucov{}{\pa}|=11+10-2+
		2\cdot{3}+2\cdot{3}+2\cdot{1}=33$.
	\end{itemize}

\end{example}


TITLE: Oil-water interface simulation using Gromacs
QUESTION [1 upvotes]: I would like to perform a decane/water(tip4p) interface simulation using GROMACS to analyse the fluctuation of the interface over a long period of time (50ps - 1ns).
Though I have a rough idea on how to perform it, I still am unsure about how to create a initial configuration which looks like the figure give below (A.R. Buuren, Ph.D. Thesis, University of Groningen, 1995).
Also once I start my production run I would like to know, how to obtain the height fluctuations of the interface as a function of time.

REPLY [2 votes]: The standard way would be to simulate bulk water and bulk decane, separately, to generate two relaxed configurations for each phase.
You will want them to both be the same pressure but to have the same cell dimensions in the x and y plane, so you should perform NPT but only allowing the cells to relax in the z-direction.
Then write a script to stick the two relaxed configurations together, side-by-side, into a single cell. You will need to reverse any breaking apart of the individual molecules by the periodic boundary conditions first though.
Then relax the merged simulation cell under NPT (this time allowing all three cell vectors to relax).

how to obtain the height fluctuations of the interface as a function of time

One possible idea: construct a histogram along the z-dimension where, for each decane you add (+1), and for each water molecule you minus (-1). Then  your histogram will cross zero in two places - these define the boundary where the two phases meet.


text:
\section{Practical Considerations}

Since $\bm{x}$ is arbitrary, it is possible to select it as being parallel to $\bm{\tilde{v}}$, so that its presence can be eliminated from Theorem \ref{thm:mine} altogether. This is made clear in Corollary \ref{cor:mine}, which removes $\bm{x}$, whilst studying the case of $w_1 \geq 0$ (the central concern of this paper).

\begin{cor}\textbf{[Appropriate $\bm{\alpha}$ Range]}\label{cor:mine}

\begin{align}
\tikzmarkin[eqnbox2]{b}
    \alpha \geq \frac{\| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| }{\|\bm{\tilde{v}}\|}, \quad \text{ for  } w_1\geq 0.
\end{align}
\tikzmarkend{b}
\end{cor}
\begin{proof}

Consider,

\begin{align*}
\alpha - \frac{\|\bm{x}\| \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| }{ \ip{\bm{x}}{\bm{\tilde{v}}} } &=  \alpha - \frac{\|\bm{x}\| \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| }{ \|\bm{x}\| \|\bm{\tilde{v}}\| \cos{\theta_{\bm{x},\bm{\tilde{v}} } } } \\
&= \alpha - \frac{ \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| \cos{\theta_{\bm{x},\bm{\tilde{v}} } }},
\end{align*}

where $\theta_{\bm{x},\bm{\tilde{v}} }$ denotes the angle between vectors $\bm{x}$ and $\bm{\tilde{v}}$. Since we require $w_1\geq 0$, this implies that in turn we are looking at the case, \begin{align*} \alpha \geq \frac{ \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| \cos{\theta_{\bm{x},\bm{\tilde{v}} } }}. \end{align*} Since $\bm{x}$ can be arbitrarily chosen, select $\bm{x}$ so as to run parallel to $\bm{\tilde{v}}$, thereby making $\cos{\theta_{\bm{x},\bm{\tilde{v}} } }=1$. Thus, $\bm{x}$ becomes completely removed from this expression, completing the proof.
\end{proof}

Therefore we have access to a lower bound as a function of $\alpha$, using \textit{only} the left and right eigenvectors. However notice that unfortunately this definition is implicit, in that $\alpha$ appears on both the left, and right-hand sides. In order to establish an expression with $\alpha$ only on one side, some assumptions will need to be made. These will be clarified in Remark \ref{rem:extend}.

\begin{remark}\textbf{[Simplified $\bm{\alpha}$ Range]}\label{rem:extend}
If $w_1 \geq 0$, and $|w_1 - \alpha| < |w_2 - \alpha|$, then,  \begin{align}\alpha \geq \frac{1}{2}\rho(\bm{M}).\end{align}
\end{remark}
\begin{proof}

\begin{align}
    \frac{ \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| } &= \frac{ \| (\bm{M} - \alpha\bm{I}) \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| }\nonumber\\
    &\leq \frac{ \| (\bm{M} - \alpha\bm{I})\| \| \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| }\nonumber\\
    &=  \| (\bm{M} - \alpha\bm{I})\| \nonumber\\
    &= \rho(\bm{M} - \alpha\bm{I})
\end{align}

where $\bm{v} \neq 0$. From the proof thus far we have by implication: $\alpha - \frac{ \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| } \geq \alpha -  \rho(\bm{M} - \alpha\bm{I})$. From Corollary \ref{cor:mine} it is known that $\alpha - \frac{ \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| }\geq 0$, if $w_1 \geq 0$, and so by transitivity it is natural to require that $\alpha -  \rho(\bm{M} - \alpha\bm{I})\geq 0$. The given condition of $|w_1 - \alpha| < |w_2 - \alpha|$ means that we can expand as follows: $\alpha -  \rho(\bm{M} - \alpha\bm{I})=2\alpha -\rho(\bm{M})$, which in turn implies that $\alpha \geq \frac{1}{2}\rho(\bm{M})$, thus completing the proof.

\end{proof}

Ultimately, Remark \ref{rem:extend} tries to make clear that a reasonable value to choose for $\alpha$ in order to best estimate the value of an (unobserved) $w_1$ is that of: $\alpha = \frac{1}{2}\rho(\bm{M})$. This is because from Corollary \ref{cor:mine} we know that $\alpha - \frac{ \| \bm{\tilde{g}} - \alpha \bm{\tilde{v}}\| } { \|\bm{\tilde{v}}\| }\geq 0$ in order to ensure that $w_1\geq 0$, and the value $\alpha=\frac{1}{2}\rho(\bm{M})$ appears to also satisfy this condition (Remark \ref{rem:extend}). However, once again it seems that we have run into a problem! This $\alpha$ value still requires access to $\bm{M}$! In particular, to the access of $\rho(\bm{M})$. Luckily however, $\rho(\bm{M})$ (the largest eigenvalue in this case) is much easier to estimate than least eigenvalue, $w_1$, because matrix reconstruction procedures tend to be much more strongly driven by the presence of the \textit{larger} eigenvalues (i.e. the larger singular values). For example, since we already have the relationship: $\bm{g}_i= \bm{Mv}_i$ (Lemma \ref{lem:LR}), one could pose an estimate for $\bm{M}$ as: $\bm{M}\approx \bm{g}_i\bm{v}_i^{\dagger}$, where the dagger symbol denotes the pseudo-inverse. This estimation of $\bm{M}$ is much more strongly driven by the larger singular values, and in fact, it can be shown that the largest singular value of this pseudo-inverse estimate for $\bm{M}$, is upper-bounded by the largest singular value for the full $\bm{M}$. This idea is clarified in Lemma \ref{lem:sigma1}. In practice this means as one collects more left and right eigenvectors, one can obtain increasingly better estimates of $\alpha$.

\begin{lem}\label{lem:sigma1}
If $\bm{g} = \bm{Mv}$, then $\sigma_1(\bm{g} \bm{v}^{\dagger})\leq \sigma_1(\bm{M})\coloneqq\rho(\bm{M})$, where $\sigma_1(\bm{M})$ denotes the largest singular value of $\bm{M}$.
\end{lem}

\begin{proof}
Consider that $\bm{g} \bm{v}^{\dagger} =  \bm{g} (\bm{v}^{\intercal}\bm{v})^{-1}\bm{v}^{\intercal}$ by definition of the pseudo-inverse. Thus,

\begin{align}
    \|\bm{g} (\bm{v}^{\intercal}\bm{v})^{-1}\bm{v}^{\intercal}\| &\leq  \|\bm{g}\|\cdot  \|(\bm{v}^{\intercal}\bm{v})^{-1}\| \cdot \|\bm{v}^{\intercal}\| \nonumber \\
   &= \|\bm{Mv}\|\cdot  \|\|\bm{v}\|^{-2}\| \cdot \|\bm{v}^{\intercal}\|\nonumber \\
   &\leq  \|\bm{M}\| \cdot \|\bm{v}\| \cdot  \|\bm{v}\|^{-2} \cdot \|\bm{v}^{\intercal}\| \nonumber\\
   &= \|\bm{M}\|\cdot\|\bm{v}\|^2 \cdot  \|(\bm{v})\|^{-2}  \nonumber \\
   &= \|\bm{M}\|\nonumber
\end{align}

Thus, $\|\bm{g} \bm{v}^{\dagger}\| \leq \|\bm{M}\|$. Moreover the induced operator norm of a matrix evaluates to its largest singular value (the spectral radius in the case of symmetric positive definite matrices) implying that, $\sigma_1(\bm{g} \bm{v}^{\dagger})\leq \sigma_1(\bm{M})=\rho(\bm{M})$ which completes the proof.
\end{proof}

\textbf{Summary: } \textit{We have established conditions under which the bound of Theorem \ref{thm:mine} can be practically used. These conditions are developed by observing how $\alpha$ behaves around the required region of $w_1 \geq 0$. It seems that a good reference for $\bm{\alpha}$ is to be around $\frac{1}{2}\rho(\bm{M})$, and in turn, $\rho(\bm{M})$ can be approximated from knowledge that $\bm{M}\approx \bm{gv}^{\dagger}$.}