TITLE: Simple Bayes rule question, how much to pay
QUESTION [1 upvotes]: I'm reviewing probability and this question is simple, not sure why I can't get the answer!  How is this done?

There are 2 envelopes.  One has 2 red beads, 2 black beads, and 1
  dollar in it.  The second has 1 red bead, 2 black beads, and 0 dollars
  in it.  Suppose an envelope is selected at random and you are shown
  one bead, and it is black.  How much should you pay for the envelope?

This seems like it could be solved with Bayes rule and expected values, but I'm trying to get Bayes rule stuck in my head, so I'm hoping for a solution with that :)

REPLY [7 votes]: I will assume that "we are shown one bead" means that we are shown one bead, chosen at random from the beads in the selected envelope.
Since intuition can sometimes lead us astray, we will use the formal conditional probability machinery.  Let $W$ (for "win") be the event that the envelope contains $2$ red and $2$ black, and let $B$ be the event that the ball that was drawn is black. We want the conditional probability $P(W|B)$.
By the definition of conditional probability, we have
$$P(W|B)=\frac {P(W\cap B)}{P(B)}.$$
We compute the two required probabilities on the right.
The probability of $W\cap B$ is $(1/2)(2/4)$.  This is because we must pick the correct envelope (probability $1/2$) and draw one of the $2$ black beads from the $4$ beads in the envelope.
The probability of $B$ is $(1/2)(2/4)+(1/2)(2/3)$.  This is because the event "we get a black bead" can happen in two disjoint ways: (i) We pick the envelope with $2$ black, $2$ red and draw a black bead or (ii) We pick the envelope with $2$ black, $1$ red and draw a black bead.
Divide and simplify.  We get $3/7$.
The expectation of the amount of money in the envelope is therefore $(3/7)(1)+(4/7)(0)$, which is $3/7$.
As to how much one "should" pay for the envelope, the commonsense answer is as little as possible.  But if we pay $3/7$ of a dollar for the envelope, then our expected total gain is $0$, making it a "fair" game. That is undoubtedly the expected answer.
A Somewhat Different Analysis: Let $a$ be the amount that we pay for the envelope, and let $X$ be our net gain.
If there is a dollar in the envelope, the net gain is $1-a$.  If there is no money in the envelope, our net gain is $-a$.
Thus
$$E(X)=(1-a)(3/7)+(-a)(4/7).$$
Simplify. We get
$$E(X)=\frac{3-7a}{7}.$$
This expectation is $0$ ("fair game") if $3-7a=0$, that is, if $a=3/7$.
Reality Check: The envelope with no money is (proportionally) richer in black than the envelope with money.  So drawing a black bead means that there is a better than $1/2$ probability that we are dealing with the no money envelope.  Thus the expected value of the money in the envelope is less  than $50$ cents.  And indeed $3/7$ is less than $1/2$.  It is almost always a good idea to check whether a computed answer "makes sense."
Comment: If the bead we are shown is not chosen at random, the answer depends on the strategy that the opponent is using.  For example, if the opponent always shows you a black bead, whatever envelope you choose, then the probability of winning a dollar is $1/2$, so a payment of $50$ cents makes the game fair.

REPLY [1 votes]: When you say "at random", do you mean the two envelopes have equal probabilities of being chosen?  If so then we can represent the prior distribution as
$$
(1/2, 1/2).
$$
The likelihood function can be represented as
$$
(1/2,2/3)
$$
(The probability of getting a black bead from the first envelope is $1/2$; from the second is $2/3$.)
Multiply the likelihood by the prior term-by-term:
$$
(1/2,1/2)\cdot(1/2,2/3) = (1/4,1/3),
$$
then normalize to get a probability distribution, thus: $1/4 + 1/3 = 7/12$, multiply all entries by $12/7$:
$$
\frac{12}{7}\left(\frac14, \frac13\right) = \left(\frac37,\frac47\right).
$$
That's the posterior probability distribution.
Bayes rule can be stated thus: Multiply the prior probbility distribution by the likelihood and then normalize, to get the posterior probability distribution.


text:
\newcommand{\losssq}{L_{\rm sq}}

\section{Introduction}

The increasing collection of data at large scale---medical records, location
information from cell phones, internet browsing history---points to the
importance of a deeper understanding of the tradeoffs inherent between
privacy and the utility of using the data collected.  Classical mechanisms
for preserving privacy, such as permutation, small noise addition, releasing
only mean information, or basic anonymization are insufficient, and notable
privacy compromises with genomic data~\cite{HomerSzReDuTeMuPeStNeCr08} and
movie rating information~\cite{NarayananSh08} have caused the NIH to
temporarily stop releasing genetic information and Netflix to cancel a
proposed competition for predicting movie ratings. Balancing the tension
between utility and the risk of disclosure of sensitive information
is thus essential.

In response to these challenges, researchers in the statistics, databases,
and computer science communities have studied \emph{differential
  privacy}~\cite{Warner65, EvfimievskiGeSr03, DworkMcNiSm06, DworkSm09,
  HardtTa10, DuchiJoWa18} as a formalization of disclosure risk limitation,
providing strong privacy guarantees. This literature discusses two notions
of privacy: \emph{local} privacy, in which data is privatized before it is
even shared with a data collector, and \emph{central} privacy, where a
centralized curator maintains the sample and guarantees that any information
it releases is appropriately private. The local model is stronger, and
consequently it is more challenging to develop statistically efficient
algorithms.  Yet the strong privacy protections local privacy provides
encourage its adoption. Whether for ease of compliance with regulatory
strictures, for example with European Union privacy rules~\cite{EU18}; for
reasons of transparency and belief in the importance of privacy; or to avoid
the risks proximate to holding sensitive data, like hacking or subpoena
risk, because private data never leaves an individual's device in the clear;
major technology companies have adopted local differential privacy
protections in their data collection and machine learning tools. Apple
provides local differential privacy in many of its iPhone
systems~\cite{ApplePrivacy17}, and Google has built systems supplying
central and local differential
privacy~\cite{ErlingssonPiKo14,AbadiErGoMcPaMiTaZh17}.  The broad impact of
privacy protections in billions of devices suggest we should carefully
understand the fundamental limitations and possibilities of learning with
local notions of privacy.

To address this challenge, we study the \emph{local minimax complexity} of
estimation and learning under local notions of privacy.
Worst-case notions of complexity may be too stringent for statistical
practice~\cite{DuchiJoWa18}, and in real-world use, we wish to understand
how difficult the \emph{actual} problem we have is, and whether we can adapt
to this problem difficulty, so that our procedurs more efficiently solve
easy problems as opposed to being tuned to worst-case notions of
difficulty. Our adoption of local minimax complexity is thus driven by three
desiderata: we seek fundamental limits on estimation and learning that (i)
are instance specific, applying to the particular problem at hand, (ii) are
uniformly attainable, in that there exist adaptive procedures to achieve the
instance-specific difficulty, and (iii) have super-efficiency limitations, so
that if a procedure achieves \emph{better} behavior than the lower bounds
suggest is possible, there should be problem instances in which the
procedure must have substantially worse behavior. In this paper, we provide
a characterization of the difficulty of estimation of one-dimensional
quantities under local privacy that satisfies these desiderata.

The celebrated Le Cam--H\'{a}jek local asymptotic minimax
theory~\cite{Hajek72, LeCam72, LeCam86, VanDerVaart98, LeCamYa00} cleanly
delineates efficient from inefficient estimators in classical statistics and
highlights the importance of local notions of optimality (making
Fisher information bounds rigorous). As an example encapsulating the
differences between global and local minimax complexity, consider the
one-dimensional logistic regression problem of predicting $y \in \{\pm 1\}$
from $x \in \R$, with $p_\theta(y \mid x) = (1 + \exp(-y x\theta))^{-1}$,
where---taking our motivation from applications of machine
learning~\cite{HastieTiFr09, ApplePrivacy17,AbadiErGoMcPaMiTaZh17}---we wish
only to accurately estimate $p(y \mid x)$. This problem is easier the larger
$|\theta|$ is, and a calculation
shows that the maximum likelihood estimator has misclassification error
decreasing exponentially in $|\theta|$; a fully minimax analysis provides a
lower bound at $\theta = 0$, or random guessing, with convergence lower
bound $1/\sqrt{n}$ independent of $\theta$. For most applications of
statistical learning, we hope our model substantially outperforms random
guessing, so such (global worst-case) analyses are of limited utility in the
design of (near-) optimal procedures. To that end, any practicable theory of
optimal private estimation should encapsulate a \emph{local} notion of
problem difficulty.

\subsection{Contributions, outline, and related work}

Our development of instance-specific (local) notions of problem complexity
under privacy constraints allows us to more precisely quantify the
statistical price of privacy. Identifying the tension here is of course of
substantial interest, and \citet*{DuchiJoWa18,DuchiJoWa13_focs} develop a
set of statistical and information-theoretic tools for understanding the
\emph{minimax} risk in locally differentially private settings, providing
the point of departure for our work.  To understand their and our coming
approach, let us formally define our setting.

We have i.i.d.\ data
$X_1, \ldots, X_n$ drawn according to a distribution $P$ on a space
$\mc{X}$. Instead of observing the original sample $\{X_i\}$, however, the
statistician or learner sees only \emph{privatized} data $Z_1, \ldots, Z_n$,
where the data $Z_i$ is drawn from a Markov kernel $\channel(\cdot \mid
X_i)$ conditional on $X_i$ (following information-theoretic parlance, we
often call $\channel$ the privacy \emph{channel}~\cite{CoverTh06}; in the
privacy literature $\channel$ is the
\emph{mechanism}~\cite{DworkMcNiSm06}). In full generality, we allow the
channel to be \emph{sequentially interactive}~\cite{DuchiJoWa18}, meaning
that at observation $i$, the channel may depend on the previous (private)
observations $Z_1, \ldots, Z_{i - 1}$. That is, we have
\begin{equation}
  \label{eqn:sequential-interactive}
  Z_i \mid X_i = x, Z_1, \ldots, Z_{i-1}
  \sim \channel(\cdot \mid x, Z_{1:i-1}).
\end{equation}
This notion of interactivity is important for procedures, such as stochastic
gradient methods~\cite{DuchiJoWa18} or the one-step-corrected estimators we
develop in the sequel, which modify the mechanism after some number of
observations to more accurately perform inference.

The statistical problems we consider are, abstractly, as follows.  Let
$\mc{P}$ be a family of distributions, and let $\theta: \mc{P} \to \Theta$
be a parameter belonging to a parameter space $\Theta$ we wish to
estimate, where $\theta(P)$ denotes the estimand. Let
$L : \Theta \times \mc{P} \to \R_+$ be a loss function measuring the loss of
an estimated value $\theta$ for the distribution $P$, where we assume that
$L(\theta(P), P) = 0$ for all distributions $P$.  As an example, we
may consider the mean $\theta(P) = \E_P[X] \in \R$ and squared error
$L(\theta, P) = (\theta - \theta(P))^2 = (\theta - \E_P[X])^2$.
Let $\channeldistset$ be a collection of appropriately private
channels, for example, $\diffp$-differentially private channels (which
we define in the sequel). The \emph{private minimax risk}~\cite{DuchiJoWa18}
is
\begin{equation}
  \label{eqn:private-minimax}
  \minimax_n(L, \mc{P}, \channeldistset)
  \defeq \inf_{\what{\theta}, \channel \in \channeldistset}
  \sup_{P \in \mc{P}}
  \E_{\channel \circ P}\left[L(\what{\theta}(Z_1, \ldots, Z_n), P)\right]
\end{equation}
where $\channel \circ P$ denotes
the marginal $X_i \sim P$ and $Z_i$ drawn
conditionally~\eqref{eqn:sequential-interactive}.  \citet{DuchiJoWa18}
provide upper and lower bounds on this quantity when $\channeldistset$ is
the collection of $\diffp$-locally differentially private channels,
developing strong data processing inequalities to quantify the costs of
privacy.

The worst-case nature of the formulation~\eqref{eqn:private-minimax} may
suggest lower bounds that are too pessimistic for practice, and
does not allow a characterization of
problem-specific difficulty, which is important for a deeper understanding
of adaptive and optimal procedures. Accordingly, we adopt a \emph{local
  minimax approach}, which builds out of the classical statistical
literature on hardest one-dimensional alternatives that begins with
Stein~\cite{Stein56a, Birge83, DonohoLi87,DonohoLi91a,DonohoLi91b, CaiLo15,
  ChatterjeeDuLaZh16}.  In the same setting as the above,
we define the \emph{local minimax risk} at
the distribution $P_0$ for the set of channels $\channeldistset$ as
\begin{equation}
  \label{eqn:private-local-minimax}
  \localminimax_n(P_0, L, \mc{P}, \channeldistset)
  \defeq \sup_{P_1 \in \mc{P}}
  \inf_{\what{\theta},
    \channel \in \channeldistset}
  \max_{P \in \{P_0, P_1\}}
  \E_{Q \circ P}\left[L(\what{\theta}(Z_1, \ldots, Z_n), P)\right].
\end{equation}
The quantity~\eqref{eqn:private-local-minimax} measures the
difficulty of the loss minimization problem for a \emph{particular
  distribution} $P_0$ under the privacy constraints $\channeldistset$
characterizes, and at this distinguished distribution, we look for the
hardest alternative distribution $P_1 \in \mc{P}$.

To situate our contributions, let us first consider the non-private variant
of the minimax complexity~\eqref{eqn:private-minimax} and local minimax
complexity~\eqref{eqn:private-local-minimax}, when $\channeldistset =
\{\id\}$ (the identity mapping), and we use the squared error loss
$\losssq(\theta, P) = (\theta - \theta(P)))^2$. Let us first consider a
classical setting, in which we wish to estimate a linear function $v^T
\theta$ of a parameter $\theta$ in a parametric family $\mc{P} =
\{P_\theta\}_{\theta \in \Theta}$ with Fisher information matrix
$\fisher[\theta]$. The
Fisher information bound~\cite{LeCamYa00} for the parameter $\theta_0$
is
\begin{equation*}
  \localminimax_n(P_{\theta_0}, \losssq, \mc{P}, \{\id\})
  \asymp \frac{1}{n} \E\left[\left(v^T Z\right)^2\right]
  ~~ \mbox{for} ~~
  Z \sim \normal\big(0, \fisher[\theta_0]^{-1}\big).
\end{equation*}
More generally,
if we wish to estimate a functional $\theta(P) \in \R$ of
a distribution $P$, \citet{DonohoLi87,DonohoLi91a,DonohoLi91b} show
how the \emph{modulus of continuity} takes the place of the classical
information bound. Again considering the squared error, define the
modulus of continuity of $\theta(\cdot)$ over $\mc{P}$ with respect
to Hellinger distance by
\begin{equation}
  \label{eqn:hellinger-modcont}
  \modcont[{\rm hel}](\delta; \mc{P})
  \defeq \sup_{P_0, P_1 \in \mc{P}}
  \left\{(\theta(P_0) - \theta(P_1))^2 \mid P_0, P_1 \in \mc{P},
  \dhel(P_0, P_1) \le \delta \right\}
\end{equation}
where $\dhel^2(P_0, P_1) = \half \int (\sqrt{dP_0} - \sqrt{dP_1})^2$.
Then under mild regularity conditions,
\begin{equation*}
  \minimax_n(\losssq, \mc{P}, \{\id\})
  \asymp \modcont[{\rm hel}] (n^{-1/2}; \mc{P}),
\end{equation*}
which highlights that separation in Hellinger distance precisely governs
problem difficulty in non-private classical statistical problems.  In the
local minimax case, similar characterizations via a local modulus of
continuity are available in some problems, including estimation of the value
of a convex function~\cite{CaiLo15} and stochastic
optimization~\cite{ChatterjeeDuLaZh16}.

In contrast, the work of \citet{DuchiJoWa18,DuchiJoWa13_focs} suggests that
for $\diffp$-locally differentially private estimation, we should replace
the Hellinger distance by \emph{variation distance}.  In the case of
higher-dimensional problems, there are additional dimension-dependent
penalties in estimation that local differential privacy makes unavoidable,
at least in a minimax sense~\cite{DuchiJoWa18}. In work independent of and
contemporaneous to our own, \citet{RohdeSt18} build off
of~\cite{DuchiJoWa18} to show that (non-local) minimax rates of convergence
under $\diffp$-local differential privacy are frequently governed by a
modulus of continuity~\eqref{eqn:hellinger-modcont}, except that the
variation distance $\tvnorm{P_0 - P_1} = \sup_A |P_0(A) - P_1(A)|$ replaces
the Hellinger distance $\dhel$. \citeauthor{RohdeSt18} also exhibit a
mechanism that is minimax optimal for ``nearly'' linear functionals based on
randomized response~\cite[Sec.~4]{Warner65,RohdeSt18}. Thus, locally
differentially private procedures give rise to a different geometry than
classical statistical problems.

Now we are in a position for a high-level description of our results.  Our
results apply in a variety of locally private estimation settings, whose
definitions we formalize in Section~\ref{sec:definition-of-privacy}, but all
of them consist of weakenings of $\diffp$-differential privacy (including
concentrated and R\'{e}nyi-differential
privacy~\cite{DworkMcNiSm06, DworkRo16, BunSt16, Mironov17}).  We provide a
precise characterization of the local minimax
complexity~\eqref{eqn:private-local-minimax} in these settings.
If we define the local modulus of continuity (for the squared
error) at $P_0$ by
\begin{equation*}
  \modcont[{\rm TV}](\delta; P_0, \mc{P})
  \defeq \sup_{P \in \mc{P}} \left\{(\theta(P_0) - \theta(P))^2
  \mid \tvnorm{P - P_0} \le \delta \right\},
\end{equation*}
then a consequence of our
Theorem~\ref{theorem:modulus-of-continuity} is that for
the squared loss and family $\channeldistset_\diffp$ of $\diffp$-locally
private channels,
\begin{equation*}

  \localminimax_n(P_0, \losssq, \mc{P}, \channeldistset_\diffp)
  \asymp \modcont[{\rm TV}]\left((n\diffp^2)^{-1/2}; P_0, \mc{P}\right).
\end{equation*}
We provide this characterization in more detail and for general losses in
Section~\ref{sec:local-minimax}.  Moreover, we show a super-efficiency
result that any procedure that achieves risk better than the local minimax
complexity at a distribution $P_0$ \emph{must} suffer higher risk at another
distribution $P_1$, so that this characterization does indeed satisfy our
desiderata of an instance-specific complexity measure.

The departure of these risk bounds from the typical Hellinger-based moduli
of continuity~\eqref{eqn:hellinger-modcont} has consequences for
locally private estimation and adaptivity of estimators, which we address
via examples in Section~\ref{sec:examples}.  For instance,
instead of the classical Fisher information, an alternative we
term the \emph{$L_1$-information} characterizes the complexity of locally
private estimation: the classical Fisher information bounds are
unobtainable.  A challenging consequence of these results is that, for some
parametric models (including Bernoulli estimation and binomial logistic
regression), the local complexity~\eqref{eqn:private-local-minimax} is
\emph{independent} of the underlying parameter: problems that are easy (in
the classical Fisher information sense) are never easy under local privacy
constraints.  Our proofs, building off of those of \citet{DuchiJoWa18}, rely
on novel Markov contraction inequalities for divergence measures, which
strengthen classical strong data processing
inequalities~\cite{CohenKeZb98,DelMoralLeMi03}.

Developing adaptive procedures uniformly achieving the instance-specific
local minimax risk~\eqref{eqn:private-local-minimax} is challenging, but we
show that such optimal design is possible in a number of cases in
Section~\ref{sec:examples}, including well- and mis-specified exponential
family models, using an extension of classical one-step corrected
estimators. We compare these locally optimal procedures with the minimax
optimal procedures \citet{DuchiJoWa18} propose on a protein
expression-prediction problem in Section~\ref{sec:experiments}; the
experimental results suggests that the local minimax perspective indeed
outperforms the global minimax procedures, however, the costs of privacy are
\emph{still} nontrivial.

Lastly, because we consider weaker notions of privacy, one might ask whether
it is possible to improve the minimax bounds that \citet{DuchiJoWa18,
  DuchiJoWa13_focs} develop. Unfortunately, this appears impossible (see
Section~\ref{sec:high-dim}). \citeauthor{DuchiJoWa18} show
only that \emph{non-interactive privacy} mechanisms (i.e.\ the channel
$\channel$ may depend only on $X_i$ and not the past observations) must
suffer poor performance in high dimensions under stringent
differential privacy constraints. Our results show that this is unavoidable,
even with weaker notions of privacy and allowing interactive mechanisms.  We
provide some additional discussion and perspective in
the closing of the paper in Section~\ref{sec:discussion}.

config: arxiv


TITLE: Why $\operatorname{Im}(\lambda-A)\neq C_{[0,1]}$?
QUESTION [0 upvotes]: Example.  Study the spectrum of the following operator: $Ax(t)=tx(t)$

$tx(t)=\lambda x(t)\\x(t)(t-\lambda)=0\:\:\:t\in[0,1]$
$x(t)\equiv 0$ and $\lambda\notin[0,1]$
Now let's see the image.
$(t-\lambda)x(t)=y(t)\:\:\:(t-\lambda)\neq 0$
$x(t)=\frac{y(t)}{t-\lambda}\:\:\lambda\in[0,1]$
$x(t)(t-\lambda)=y(t)$, then $y(\lambda)=0$ and $y_0(t)\equiv 1$ which implies $\rho(y,y_0)>1$.
Therefore $\operatorname{Im}(\lambda-A)\neq C_{[0,1]}$ then $\lambda$ is residual.
Question:
I am having a hard time understanding this proof, more specifically why $\rho(y,y_0)>1$. What does $\rho(y,y_0)>1$ mean? Is it a metric? What was the procedure used on this example?
Thanks in advance!

REPLY [1 votes]: $\rho$ is the supremum metric on $C[0,1]$. Note that if $Ax(t)=\lambda x(t)$ and $x(t)$ is not the zero function then $\lambda \in [0,1]$ necessarily. Nor $\rho (y_0,y) \geq |y_0(\lambda)-y(\lambda)| =|1-0|=1$. This proves that any function $y$ in the image has distance at least 1 from $y_0$. In particular $y_0$ itself is not in the image.


TITLE: If $a$ and $-a$ are both quadratic residues mod an odd prime $p$, then $p \equiv 1\pmod4$
QUESTION [1 upvotes]: If $a$ and $-a$ are both quadratic residues modulo an odd prime $p$, for $a \in \mathbb{Z}$ and $p\ \not\mid\ a$, then $p \equiv 1\pmod{4}$.
My guess is that was true and my reasoning was that with$$
\left(\frac{a}{b}\right) \equiv a^{\frac{p-1}{2}} \equiv 1 \pmod{p},\quad \left(\frac{-a}{b}\right) \equiv (-a)^{\frac{p-1}{2}} \equiv 1 \pmod{p}$$
both satisfied, we must have $p \equiv 1\pmod{4}$, but I am not too sure about this reasoning.
Would appreciate help!

REPLY [1 votes]: Just note that
$
1
\equiv (-a)^{\frac{p-1}{2}}
\equiv (-1)^{\frac{p-1}{2}} a^{\frac{p-1}{2}}
\equiv (-1)^{\frac{p-1}{2}}
\bmod p
$.


TITLE: If $A$ is a unitary upper triangular matrix, then $A^{-1} = A^\ast$ is also upper triangular. How?
QUESTION [0 upvotes]: I understand that if $A$ is unitary, then $A^{-1} = A^\ast$ are also unitary matrices.
But if $A$ is a unitary upper triangular matrix, then how are $A^{-1}$ and $A^\ast$ also upper triangular? This was from a particular class.
Then the statement goes on to say that $A$ will be a diagonal matrix with diagonal entries having absolute value $1$.

REPLY [1 votes]: If $A$ is an upper triangular matrix, then $A^{-1}$ is an upper triangular matrix, and the conjugate transpose $A^*$ is a lower triangular matrix.
If $A$ is upper triangular and unitary, i.e. $A^{-1} = A^*$, then $A$ is simultaneously upper triangular and lower triangular.  The only matrices that are both upper and lower triangular are diagonal matrices.


text:
\begin{document}

\maketitle

\begin{abstract}
In this paper, we determine the relative rank of the semigroup
$\T(X,Y)$ of all transformations on a finite chain $X$ with restricted range $Y\subseteq X$ modulo the set $\OP(X,Y)$ of all orientation-preserving transformation in $\T(X,Y)$. Moreover, we state the relative rank of the semigroup $\OP(X,Y)$ modulo the set $\O(X,Y)$ of all order-preserving transformations in $\OP(X,Y)$. In both cases we characterize the minimal relative generating sets.
\end{abstract}

\textit{Key words:} transformation semigroups with restricted range, order-preserving
transformations, orientation-preserving transformations, relative rank, relative generating sets.

2010 Mathematics Subject Classification: 20M20
\\

\section{Introduction and Preliminaries}

Let $S$ be a semigroup. The \textit{rank} of $S$ (denoted by $\rank S$) is defined to be the minimal number of elements of a generating set of $S$. The ranks of various well known semigroups have been calculated \cite{GH, GH1, Howie, HMcF}.
For a set $A \subseteq S$, the \textit{relative rank} of $S$ modulo $A$, denoted by $\rank (S : A)$, is the minimal cardinality of a set $B\subseteq S$ such that $A \cup B$ generates $S$. It follows immediately from the definition that $\rank (S : \emptyset) = \rank S$, $\rank ( S : S) = 0$, $\rank (S : A ) = \rank (S : \langle A \rangle )$ and $\rank (S : A) = 0$ if and only if $A$ is a generating set for $S$.
The relative rank of a semigroup modulo a suitable set was first introduced by Ru\v skuc in \cite{Ruskuc} in order to describe the generating sets of semigroups with infinite rank. In \cite{HRH}, Howie, Ru\v skuc, and Higgins  considered the relative ranks of the monoid $\T(X)$ of all full transformations on $X$, where $X$ is an infinite set, modulo some distinguished subsets of $\T(X)$.
They showed that $\rank (\T(X) : \S(X)) = 2$, $\rank (\T(X) : \E(X)) = 2$ and $\rank (\T(X) : J) = 0$, where $\S(X)$ is the symmetric group on $X$, $\E(X)$ is the set of all idempotent transformations on $X$ and $J$ is the top $\mathcal{J}$-class of $\T(X)$, i.e.
$J=\{\alpha\in\T(X) : |X\alpha|=|X|\}$.
But also if the rank is finite, the relative rank gives information about the generating sets. In the present paper, we
will determine the relative rank for a particular semigroup of
transformations on a finite set.

Let $X$ be a finite chain, say $X=\{1<2<\cdots <n\}$, for a natural number $n$.
A transformation $\alpha \in \T(X)$ is called \textit{order-preserving} if $x\le y$ implies $x\alpha\le y\alpha$, for all $x,y\in X$.
We denote by $\O(X)$ the submonoid of $\T(X)$ of all order-preserving full transformations on $X$.
The relative rank of $\T(X)$ modulo $\O(X)$ was considered by Higgins, Mitchell, and Ru\v{s}kuc in \cite{HMR}.
They showed that $\rank(\T(X) : \O(X)) = 1$, when $X$ is an arbitrary countable chain or an arbitrary well-ordered set,
while $\rank(\T(\R) : \O(\R))$ is uncountable, by considering the usual order of the set $\R$ of real numbers.
In \cite{DFK}, Dimitrova, Fernandes, and Koppitz studied the relative rank of the semigroup $\O(X)$ modulo $J=\{\alpha\in\O(X) : |X\alpha|=|X|\}$,
for an infinite countable chain $X$.
We say that a transformation $\alpha \in\T(X)$ is \textit{orientation-preserving} if there
are subsets $X_{1},X_{2}\subseteq X$ with $\emptyset \neq X_{1}<X_{2}$, (i.e.
$x_{1}<x_{2}$ for $x_{1}\in X_{1}$ and $x_{2}\in X_{2}$), $X=X_{1}\cup X_{2}$,
and $x\alpha \leq y\alpha$, whenever either $(x,y)\in X_{1}^{2}\cup X_{2}^{2}$ with $x\leq y$ or $(x,y)\in X_{2}\times X_{1}$.
Note that $X_{2}=\emptyset$ provides $\alpha \in \O(X)$.
We denote by $\OP(X)$ the submonoid of $\T(X)$ of all orientation-preserving full transformations on $X$. An equivalent notion of an orientation-preserving transformation was first introduced by McAlister in \cite{McA} and, independently, by Catarino and Higgins in \cite{CH}. It is clear that $\O(X)$ is a submonoid of $\OP(X)$, i.e. $\O(X)\subset \OP(X)\subset \T(X)$. It is interesting to note that the relative rank of $\T(X)$ modulo $\OP(X)$ as well as the relative rank of $\OP(X)$ modulo $\O(X)$ is one (see \cite{CH, HRH}), but the situation will change if one considers transformations with restricted range.

Let $Y=\{a_{1}<a_{2}<\cdots <a_{m}\}$ be a nonempty subset of $X$, for a natural number $m\leq n$, and denote by $\T(X,Y)$ the subsemigroup $\{\alpha \in \T(X) : X \alpha \subseteq Y\}$ of $\T(X)$ of all transformations with range (image) restricted to $Y$.
The set $\T(X,Y)$ coincides with $\T(X)$, whenever $Y=X$ (i.e. $m=n$).
In 1975, Symons \cite{Symons} introduced and studied the semigroup $\T(X,Y)$, which is called
semigroup of transformations with restricted range.
Recently, the rank of $\T(X,Y)$ was computed by Fernandes and Sanwong
in \cite{FS}. They proved that the rank of $\T(X,Y)$ is the Sterling number $S(n,m)$ of second kind with $\left\vert X\right\vert =n$
and $\left\vert Y\right\vert =m$.
The rank of the order-preserving counterpart $\O(X,Y)$ of $\T(X,Y)$ was studied in \cite{FHQS1} by Fernandes, Honyam, Quinteiro, and Singha.
The authors found that
$\rank\O(X,Y)=\left(
\begin{array}{c}
n-1 \\
m-1
\end{array}
\right) +\left\vert Y^{\#}\right\vert,$
where $Y^{\#}$ denotes the set of all
$y\in Y$ with one of the following properties:
(i) $y$ has no successor in $X$;
(ii) $y$ is no successor of any element in $X$;
(iii) both the successor of $Y$ and the element whose successor is $y$ belong to $Y$.
Moreover, the regularity and the rank of the semigroup $\OP(X,Y)$ were studied by the same authors in \cite{FHQS2}.
They showed that
$\rank\OP(X,Y)=\left(
\begin{array}{c}
n \\
m
\end{array}
\right)$.
In \cite{TK}, Tinpun and Koppitz studied the relative rank of $\T(X,Y)$ modulo $\O(X,Y)$ and proved that
$\rank(\T(X,Y):\O(X,Y))=
S(n,m)-
\left(
\begin{array}{c}
n-1 \\
m-1
\end{array}
\right) + a$,
where $a \in \{0,1\}$ depending on the set $Y$.
In this paper, we determine the relative rank of $\OP(X,Y)$ modulo $\O(X,Y)$ as well as the relative
rank of $\T(X,Y)$ modulo $\OP(X,Y)$.

Let $\alpha \in \T(X,Y)$. The kernel of $\alpha$ is the
equivalence relation $\ker\alpha $ with $(x,y)\in \ker\alpha $ if $x\alpha
=y\alpha$. It corresponds uniquely to a partition on $X$. This justifies to regard $\ker \alpha $ as a partition on $X$. We will call a
block of this partition as $\ker\alpha$-class. In particular, the sets $x\alpha^{-1}=\{y\in X:y\alpha =x\}$, for $x\in X\alpha$, are the $\ker\alpha$-classes.
We say that a partition $P$ is a subpartition of a
partition $Q$ of $X$ if for all $p\in P$ there is $q\in Q$ with
$p\subseteq q$. A set $T\subseteq X$ with $\left\vert T\cap x\alpha^{-1}\right\vert =1$, for all $x\in X\alpha$, is called a transversal of $\ker\alpha$. Let $A\subseteq X$. Then $\alpha |_{A}:A\rightarrow Y$ denotes the restriction of $\alpha$ to $A$ and $A$ will be called convex if $x<y<z$ with $x,z\in A$ implies $y\in A$.

Let $l\in \{1,\ldots ,m\}$. We denote by $\mathcal{P}_{l}$ the set of all
partitions $\{A_{1},\ldots,A_{l}\}$ of $X$ such that $A_{2}<A_{3}<\cdots
<A_{l}$ are convex sets (if $l>1$) and $A_{1}$ is the union of two convex
sets with $1,n\in A_{1}.$
Further, let $\mathcal{Q}_{l}$ be the set of all partitions $\{A_{1},\ldots,A_{l}\}$
of $X$ such that $A_{1}<A_{2}<\cdots <A_{l}$ are convex and let $\mathcal{R}_{l}$
be the set of all partitions of $X$, which not belong to $\mathcal{Q}_{l} \cup \mathcal{P}_{l}$. We observe that $\ker \beta \in \mathcal{Q}_{l} \cup \mathcal{P}_{l}$, whenever $\beta\in \OP(X,Y)$ with $|X\beta|=l$. In particular, $\ker \beta \in \mathcal{Q}_{l}$, whenever $\beta \in \O(X,Y)$.

Let us consider the case $l=m>1$. For $P\in \mathcal{P}_{m}$ with the blocks $A_{1}$,$A_{2}<\cdots <A_{m}$,
let $\alpha _{P}$ be the transformation on $X$ defined by
$$x\alpha_{P}:=a_{i}, \text{ whenever } x\in A_{i} \text{ for } 1\leq i\leq m$$
in the case $1\notin Y$ or $n\notin Y$ and
$$x\alpha_{P}:=\left\{\begin{array}{ll}
                 a_{i+1}, & \text{if } x\in A_{i} \text{ for } 1\leq i<m \\
                 a_{1} & \text{if } x\in A_{m}
               \end{array}\right.$$
in the case $1,n\in Y$.
Clearly, $\ker \alpha _{P}=P$. With $X_{1}=\{1,\ldots ,\max A_{m}\}$, $X_{2}=\{\max A_{m}+1,\ldots ,n\}$ in the case $1\notin Y$ or $n\notin Y$ and $X_{1}=\{1,\ldots ,\max A_{m-1}\}$, $X_{2}=\{\max A_{m-1}+1,\ldots ,n\}$ in the case $1,n\in Y$, where $\max A_{m}$ ($\max A_{m-1}$) denotes the greatest element in the set $A_{m}$ ($A_{m-1}$, respectively), we can easy verify that $\alpha _{P}$ is orientation-preserving.

Further, let $\eta \in \T(X,Y)$ be defined by
\[
x\eta :=\left\{
\begin{array}{ll}
a_{i+1} & \mbox{if }~~ a_{i}\leq x<a_{i+1}\mbox{ for }1\leq i<m \\
a_{1} & \mbox{if }~~ x=a_{m} \\
a_{\Gamma} & \mbox{otherwise}
\end{array}
\right. ~~\mbox{ with }~~ \Gamma :=\left\{
\begin{array}{ll}
1 & \mbox{if }~~ 1\notin Y \\
2 & \mbox{otherwise,}
\end{array}
\right.
\]
in the case $1\notin Y$ or $n\notin Y$ and
\[
x\eta :=\left\{
\begin{array}{lll}
a_{i+1} & \text{if} & a_{i}\leq x<a_{i+1},~~ 1\leq i<m \\
a_{1}=1 & \text{if} & x = a_{m}=n
\end{array}
\right.
\]
in the case that $1,n\in Y$. Notice that $P_0 :=\ker \eta \in \mathcal{P}_{m}$ if $1\notin Y$ or $n\notin Y$ and $\ker \eta \in \mathcal{Q}_{m}$ if $1,n\in Y$.
In fact, $\eta \in \OP(X,Y)$ with $X_{1}=\{1,2,\ldots,a_{m}-1\}$ and $X_{2}=\{a_{m},a_{m}+1,\ldots,n\}$.
Moreover, $\eta |_{Y}$ is a permutation on $Y$, namely
$$\eta |_{Y}=\left(
\begin{array}{cccc}
a_{1} & \ldots & a_{m-1} & a_{m} \\
a_{2} & \cdots & a_{m} & a_{1}
\end{array}
\right).$$
We will denote by $\S(Y)$ the set of all permutations on $Y$.
Note, $\beta \in \O(X,Y)$ implies that either $\beta|_{Y}$ is the identity mapping on $Y$ or $\beta|_{Y} \notin \S(Y)$.

\section{The relative rank of $\OP(X,Y)$ modulo $\O(X,Y)$}

In this section, we determine the relative rank of $\OP(X,Y)$ modulo $\O(X,Y)$. A part of these results were presented at the 47-th Spring Conference of the Union of Bulgarian Mathematicians in March 2018 and are published in the proceedings of this conference \cite{DKT}.

If $m=1$ then $\OP(X,Y)$ is the set of
all constant mappings and coincides with $\O(X,Y)$, i.e. $\rank(\OP(X,Y):\O(X,Y))=0$. So, we admit that $m>1$.

First, we will show that
$$\mathcal{A}:=\{\alpha_{P}: P\in \mathcal{P}_{m}\}\cup \{\eta\}$$
is a relative generating set of $\OP(X,Y)$ modulo $\O(X,Y)$.
Notice that $\eta=\alpha_{P_0}$ if $1\notin Y$ or $n\notin Y$.

\begin{lemma}\label{le1}
For each $\alpha \in \OP(X,Y)$ with $\rank\alpha =m$, there is $\widehat{
\alpha }\in \{\alpha _{P}: P\in \mathcal{P}_{m}\} \cup \O(X,Y)$ with $\ker \alpha =\ker \widehat{\alpha }$.
\end{lemma}

\begin{proof}
Let $\alpha \in \OP(X,Y)$ and let $X_{1},X_{2}\subseteq X$ as in the
definition of an orientation-preserving transformation. If $X_{2}=\emptyset$
then $\alpha \in \O(X,Y)$. Suppose now that $X_{2}\neq \emptyset $ and let $
X_{1}\alpha =\{x_{1}<\cdots <x_{r}\}$ and $X_{2}\alpha =\{y_{1}<\cdots
<y_{s}\}$ for suitable natural numbers $r$ and $s$. We observe that $
X_{1}\alpha $ and $X_{2}\alpha $ have at most one joint element (only $x_{1}=y_{s}$ could be possible). If $x_{1}\neq y_{s}$ then $\ker \alpha =\{x_{1}\alpha
^{-1}<\cdots <x_{r}\alpha ^{-1}<y_{1}\alpha ^{-1}<\cdots <y_{s}\alpha
^{-1}\}=\ker \widehat{\alpha }$ with $\widehat{\alpha }=\left(
\begin{array}{cccccc}
x_{1}\alpha ^{-1} & \cdots & x_{r}\alpha ^{-1} & y_{1}\alpha ^{-1} & \cdots
& y_{s}\alpha ^{-1} \\
a_{1} & \cdots & a_{r} & a_{r+1} & \cdots & a_{r+s}
\end{array}
\right) \in \O(X,Y)$. If $x_{1}=y_{s}$ then $1,n\in x_{1}\alpha ^{-1} =
y_{s}\alpha ^{-1}$ and $\ker \alpha = \ker \alpha_P$ with $P = \{x_{1}\alpha ^{-1}, x_{2}\alpha ^{-1}<\cdots <x_{r}\alpha^{-1}<y_{1}\alpha ^{-1}<\cdots <y_{s-1}\alpha ^{-1}\}\in \mathcal{P}_{m}$.
\end{proof}

\begin{proposition}\label{le2}
$\OP(X,Y)=\left\langle \O(X,Y),\mathcal{A}\right\rangle $.
\end{proposition}

\begin{proof}
Let $\beta \in \OP(X,Y)$ with $\rank\beta =m$. Then there is $\theta \in
\{\alpha _{P}:P\in \mathcal{P}_{m}\}\cup \O(X,Y)$ with $\ker \beta =\ker
\theta$ by Lemma \ref{le1}. In particular, there is $r\in \{0,\ldots ,m-1\}$ with $
a_{1}\theta ^{-1}=a_{r+1}\beta ^{-1}$. Then it is easy to verify that $\beta
=\theta \eta ^{r}$, where $\eta ^{0}=\eta ^{m}$. \newline
Admit now that $i=\rank\beta <m$. Suppose that $\ker \beta \in \mathcal{P}_{i}$, say $\ker \beta =\{A_{1},A_{2}<\cdots <A_{i}\}$
with $1,n\in A_{1}$. Then there is a subpartition $P'\in \mathcal{P}_{m}$ of $\ker\beta$. We put $\theta =\alpha _{P'}$, $a=\min X\beta$, and let $T$ be a
transversal of $\ker \theta$. In particular, we have $Y=\{x(\theta
|_{T})\eta ^{k}:x\in T\}$ for all $k\in \{1,\ldots ,m\}$. Since both
mappings $\theta |_{T}:T\rightarrow Y$ and $\eta |_{Y}:Y\rightarrow Y$ are
bijections, there is $k\in \{1,\ldots ,m\}$ with $a_{1}((\theta |_{T})\eta
^{k})^{-1}\beta =a$ and $a_{1}((\theta |_{T})\eta ^{k+1})^{-1}\beta \neq a$.
Moreover, since $(\theta |_{T})\eta^{k}$ is a bijection from $T$ to $Y$ and both transformations $\theta \eta^{k}$ and $\beta $ are orientation-preserving, it is easy to verify that $f^{\ast }=((\theta |_{T})\eta ^{k})^{-1}\beta $ can be extended to an orientation-preserving transformation $f$ defined by
$$xf=\left\{
\begin{array}{lll}
a_{1}f^{\ast } & \text{if} & x<a_{1}  \\
a_{i}f^{\ast } & \text{if} & a_{i}\leq x<a_{i+1},~~ 1\leq i<m \\
a_{m}f^{\ast } & \text{if} & a_{m}\leq x,
\end{array}
\right.$$
i.e. $f$ and $f^{\ast }$ coincide on $Y$. Moreover, $
a_{1}f=a_{1}f^{\ast }=a_{1}((\theta |_{T})\eta ^{k})^{-1}\beta =a$. In order
to show that $f$ is order-preserving, it left to verify that $nf\neq a$.
Assume that $nf=a$, where $n\geq a_{m}$. Then $nf=a_{m}f^{\ast }=a_{m}f$,
i.e. $(n,a_{m})\in \ker f$ and $n\eta =a_{m}\eta =a_{1}$. So, there is $
x^{\ast }\in T$ such that $x^{\ast }((\theta |_{T})\eta ^{k})=a_{m}$, i.e. $
x^{\ast }=a_{m}((\theta |_{T})\eta ^{k})^{-1}$. Now, we have $
a=nf=a_{m}f^\ast=a_{m}((\theta |_{T})\eta ^{k})^{-1}\beta =a_{m}(\eta
^{k}|_Y)^{-1}(\theta |_{T})^{-1}\beta =a_{1}(\eta|_Y)^{-1}(\eta ^{k}|_Y)^{-1}(\theta
|_{T})^{-1}\beta =a_{1}((\theta |_{T})\eta ^{k+1})^{-1}\beta \neq a$, a
contradiction. \\
Finally, we will verify that $\beta =\theta \eta ^{k}f\in
\left\langle \O(X,Y),\mathcal{A}\right\rangle $. For this let $x\in X$. Then there is $
\widetilde{x}\in T$ such that $(x,\widetilde{x})\in $ $\ker \beta $. So, we
have $x\theta \eta ^{k}f=x\theta \eta ^{k}f^{\ast }=\widetilde{x}\theta \eta
^{k}((\theta |_{T})\eta ^{k})^{-1}\beta =\widetilde{x}\beta =x\beta $.
\newline
Suppose now that $\ker \beta \notin \mathcal{P}_{i}$ and thus, $\ker \beta \in \mathcal{Q}_{i}$.
Let $X\beta =\{b_{1},\ldots b_{i}\}$ such that $b_{1}\beta ^{-1}<\cdots <b_{i}\beta ^{-1}
$. Then we define a transformation $\varphi $ by $x\varphi =a_{j}$ for all $
x\in b_{j-1}\beta ^{-1}$ and $2\leq j\leq i+1$. Clearly, $\varphi \in \O(X,Y)$
. Further, we define a transformation $\nu \in \T(X,Y)$ by
$$x\nu =\left\{
\begin{array}{ll}
b_{j-1} & \text{if }  a_{j}\leq x < a_{j+1},~~ 2\leq j\leq i \\
b_{i} & \text{otherwise.}
\end{array}
\right. $$
Since $\beta $ is orientation-preserving, there is $k\in
\{1,\ldots ,i\}$ such that $k=i$ or $b_{1}<\cdots <b_{k-1}>b_{k}<\cdots
<b_{i}$. Then $X_{1}=\{a_{1},\ldots ,a_{k+1}-1\}$ and $X_{2}=\{a_{k+1},
\ldots ,n\}$ gives a partition of $X$ providing that $\nu $ is
orientation-preserving. Clearly, $\rank\nu =i$ and $1\nu =n\nu =b_{i}$.
Thus, it is easy to verify that $\ker \nu \in \mathcal{P}_{i}$. Hence, $\nu
\in \left\langle \O(X,Y),\mathcal{A}\right\rangle $ by the previous case and it remains
to show that $\beta =\varphi \nu \in \left\langle \O(X,Y),\mathcal{A}\right\rangle$.
For this let $x\in X$. Then $x\in b_{j}\beta ^{-1}$ for some $j\in
\{1,\ldots ,i\}$, i.e. $x\varphi \nu =a_{j+1}\nu=b_{j}=x\beta $.
\end{proof}
~~\\

The previous proposition shows that $\mathcal{A}$ is a relative generating set for $\OP(X,Y)$
modulo $\O(X,Y)$. It remains to show that $\mathcal{A}$ is of minimal size.

\begin{lemma}\label{le3}
Let $B\subseteq \OP(X,Y)$ be a relative generating set of $\OP(X,Y)$ modulo $
\O(X,Y)$. Then $\mathcal{P}_{m}\subseteq \{\ker \alpha :\alpha \in B\}$.
\end{lemma}

\begin{proof}
Let $P\in \mathcal{P}_{m}$. Since $\alpha _{P}\in \OP(X,Y)=\left\langle
\O(X,Y),B\right\rangle $, there are $\theta _{1}\in \O(X,Y)\cup B$ and $\theta
_{2}\in \OP(X,Y)$ with $\alpha _{P}=\theta _{1}\theta _{2}$. Because of $
\rank\alpha _{P}=m$, we obtain $\ker \alpha _{P}=\ker \theta _{1}$. Since $
1\alpha _{P}=n\alpha _{P}$, we conclude that $\theta _{1}\notin \O(X,Y)$,
i.e. $\theta _{1}\in B$ with $\ker \theta _{1}=\ker \alpha _{P}=P$.
\end{proof}
~~\\

In order to find a formula for the number of elements in $\mathcal{P}_{m}$,
we have to compute the number of possible partitions of $X$ into $m+1$ convex sets.
This number is $\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$. Thus, we have

\begin{remark}\label{re1}
$\left\vert \mathcal{P}_{m}\right\vert =\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$.
\end{remark}

Now, we are able to state the main result of the section. The relative rank
of $\OP(X,Y)$ modulo $\O(X,Y)$ depends of the fact whether both $1$ and $n$
belong to $Y$ or not.

\begin{theorem}\label{th5} For each $1 < m < n \in \mathbb{N}$,
\begin{enumerate}
  \item $\rank(\OP(X,Y):\O(X,Y))=\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$ if $1\notin Y$ or $n\notin Y$;
  \item $\rank(\OP(X,Y):\O(X,Y))=1+\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$ if $\{1,n\}\subseteq Y$.
\end{enumerate}
\end{theorem}

\begin{proof}
1. Note that $\ker \eta \in \mathcal{P}_{m}$ and $\eta = \alpha_{P_0}$. Hence, the set $\mathcal{A}=\{\alpha_{P}:P\in \mathcal{P}_{m}\}$ is a generating set of $\OP(X,Y)$ modulo $\O(X,Y)$ by Proposition \ref{le2}, i.e. the relative rank of $\OP(X,Y)$ modulo $\O(X,Y)$ is bounded by the cardinality of $\mathcal{P}_{m}$,
which is $\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$ by Remark \ref{re1}. But this number cannot be reduced by Lemma \ref{le3}.\\
\\
2. Let $B\subseteq \OP(X,Y)$ be a relative generating set of $\OP(X,Y)$ modulo $
\O(X,Y)$. By Lemma \ref{le3}, we know that $\mathcal{P}_{m}\subseteq \{\ker \alpha
:\alpha \in B\}$. Assume that the equality holds. Note that $\ker \eta \in \mathcal{Q}_{m}$
and $\eta$ is not order-preserving. Hence, there are $\theta _{1},\ldots ,\theta _{l}\in
\O(X,Y)\cup B$, for a suitable natural number $l$, such that $\eta
=\theta _{1}\cdots \theta _{l}$. From $\rank\eta =m$, we obtain $\ker \theta
_{1}=\ker \eta $ and $\rank\theta _{i}=m$ for $i\in \{1,\ldots ,l\}$ and thus,
$\{1,n\}\subseteq Y$ implies $(1,n)\notin \ker \theta _{i}$ for $i \in
\{2,\ldots ,l\}$. This implies $\theta _{2},\ldots ,\theta _{l}\in \O(X,Y)$.
Since $\ker \theta _{1}=\ker \eta \notin \mathcal{P}_{m}$, we get $\theta
_{1}\in \O(X,Y)$, and consequently, $\eta =\theta _{1}\theta _{2}\cdots
\theta _{l}\in \O(X,Y)$, a contradiction. So, we have verified that $
\left\vert \mathcal{P}_{m}\right\vert <\left\vert B\right\vert $, i.e. the
relative rank of $\OP(X,Y)$ modulo $\O(X,Y)$ is greater than $\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right) $. But it is bounded by $1+\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$ due to Proposition \ref{le2}. This proves the assertion.
\end{proof}
~~\\

We finish this section with the characterization of the minimal relative
generating sets of $\OP(X,Y)$ modulo $\O(X,Y)$. We will
recognize that among them there are sets with size greater than $\rank(\OP(X,Y):\O(X,Y))$.

\begin{theorem}
Let $B\subseteq \OP(X,Y)$. Then $B$ is a minimal relative generating set of $\OP(X,Y)$ modulo $\O(X,Y)$ if and only if for the set $\widetilde{B}=\{\beta
\in B:\ker \beta \in \mathcal{Q}_{m}\} \subseteq B$ the following three statements are
satisfied:\newline
$(i)$ $\mathcal{P}_{m} \subseteq \{\ker \beta :\beta \in B\setminus \widetilde{B}\}$,\newline
$(ii)$ $|B\setminus \widetilde{B}| = |\mathcal{P}_{m}|$, \newline
$(iii)$ $\eta |_{Y}\in \left\langle \beta |_{Y}:\beta \in B\right\rangle $ but
$\eta |_{Y}\notin \left\langle \beta |_{Y}:\beta \in B\setminus \{\gamma
\}\right\rangle $ for any $\gamma \in \widetilde{B}$.
\end{theorem}

\begin{proof}
Suppose that the conditions $(i) - (iii)$ are satisfied for $\widetilde{B}=\{\beta \in B:\ker\beta \in \mathcal{Q}_{m}\}$.
We will show that $\mathcal{A} \subseteq \left\langle \O(X,Y),B \right\rangle$.
Let $\alpha \in \mathcal{A}\setminus\{\eta\}$.
Then there is a partition $P = \{A_{1},A_{2}<\cdots<A_{m}\}\in \mathcal{P}_{m}$ such that
$$\alpha = \alpha_{P}=\left(
\begin{array}{cccc}
A_{1} & A_{2} & \cdots  & A_{m} \\
a_{1} & a_{2} & \cdots  & a_{m}
\end{array}
\right), \mbox{ if } 1 \notin Y \mbox{ or } n \notin Y,$$
or
$$\alpha = \alpha_{P}=\left(
\begin{array}{ccccc}
A_{1} & A_{2} & \cdots  & A_{m-1} & A_m\\
a_{2} & a_{3} & \cdots  & a_{m} & a_1
\end{array}
\right), \mbox{ if } 1, n \in Y.$$
Notice that in the latter case $a_1 = 1$ and $a_m = n$.\\
Further, from $(i)$ it follows that there is $\beta \in B$ with $\ker\beta =\ker\alpha_P$, i.e. $\beta = \alpha_P$ or
$$\beta =\left(
\begin{array}{ccccccc}
A_{1} & A_{2} & \cdots  & A_{m-i+1} & A_{m-i+2} & \cdots  & A_{m} \\
a_{i} & a_{i+1} & \cdots  & a_{m} & a_{1} & \cdots  & a_{i-1}
\end{array}
\right)$$
for some $i\in \{3,\ldots,m\}$. It is easy to verify that $\alpha_{P}=\beta^{k}\in \left\langle
B\right\rangle$, for a suitable natural number $k$. Hence, $\{\alpha_{P}: P \in \mathcal{P}_{m}\} \subseteq \left\langle\O(X,Y),B \right\rangle$.
Further, $\ker \eta \in \mathcal{P}_{m}$, whenever $1\notin Y$ or $n\notin Y$,
and $\ker \eta \in \mathcal{Q}_{m}$ otherwise. Thus, there
is $\delta \in \left\langle \O(X,Y), B \right\rangle $ with $\ker \delta
=\ker \eta$. Then we obtain as above that $\eta =\delta^{l}\in \left\langle \O(X,Y),B \right\rangle$,
for a suitable natural number $l$. Consequently, $\left\langle
\O(X,Y),\mathcal{A}\right\rangle \subseteq \left\langle \O(X,Y),B \right\rangle$.
By Proposition \ref{le2}, we obtain $\OP(X,Y)=\left\langle \O(X,Y),B \right\rangle$.
The generating set $B$ is minimal by properties $(i)$ and $(ii)$
together with Lemma \ref{le3} and by the property $(iii)$ of $\widetilde{B}$.

Conversely, let $B$ be a minimal relative generating set of $\OP(X,Y)$ modulo
$\O(X,Y)$. By Lemma \ref{le3}, there is a set $\overline{B}\subseteq B$ such that
$\mathcal{P}_{m}=\{\ker \beta :\beta \in \overline{B}\}$ and $\left\vert
\overline{B}\right\vert =\left\vert \mathcal{P}_{m}\right\vert$.
Since $\OP(X,Y) = \left\langle \O(X,Y),B \right\rangle$, there are
$\beta _{1},\ldots ,\beta _{k}\in \O(X,Y)\cup B$ such that $\eta =\beta
_{1}\cdots \beta _{k}$. Without loss of generality, we can assume that
there is not $\gamma \in \{\beta _{i}:1\leq i\leq k$, $\ker \beta
_{i}\in \mathcal{Q}_{m}\}=: \widehat{B}$ such that $\eta$ is a product of transformations in
$\overline{B}\cup (\widehat{B}\setminus \{\gamma \})$. In the first
part of the proof, we have shown that $\overline{B}\cup \widehat{B}$ is a
relative generating set of $\OP(X,Y)$ modulo $\O(X,Y)$. Because of the
minimality of $B$, we have $B=\overline{B}\cup \widehat{B}$, where $\{\ker
\beta :\beta \in B\setminus \widehat{B}\}\supseteq\mathcal{P}_{m}$, $|B\setminus\widehat{B}| = |\overline{B}| = |\mathcal{P}_{m}|$ and $\eta |_{Y}\in
\left\langle \beta |_{Y}:\beta \in B\right\rangle$ but $\eta |_{Y}\notin
\left\langle \beta |_{Y}:\beta \in B\setminus \{\gamma \}\right\rangle $ for any $\gamma \in \widehat{B}$.
\end{proof}
~~\\

In particular, for the relative generating sets of minimal size we have

\begin{remark}
$B\subseteq \OP(X,Y)$ is a relative generating set of $\OP(X,Y)$ modulo $\O(X,Y)$
of minimal size if and only if $|\widetilde{B}| = 1$ if $1,n \in Y$ and $\widetilde{B} = \emptyset$, otherwise.
\end{remark}

\section{The relative rank of $\T(X,Y)$ modulo $\OP(X,Y)$}

In this section, we determine the relative rank of $\T(X,Y)$ modulo $\OP(X,Y)$
and characterize all minimal relative generating sets of $\T(X,Y)$ modulo $\OP(X,Y)$. Since $\O(X,Y)\leq \OP(X,Y)$, we see immediately that
$\rank(\T(X,Y):\OP(X,Y))\leq S(n,m)-\left(
\begin{array}{c}
n-1 \\
m-1
\end{array}
\right) +1$. First, we state a sufficient condition for a set $B\subseteq
\T(X,Y)$ to be a relative generating set of $\T(X,Y)$ modulo $\OP(X,Y)$.

\begin{lemma}\label{le7}
Let $B\subseteq \T(X,Y)$. If $\mathcal{R}_{m}\subseteq \{\ker \beta :\beta\in B\}$ and $\S(Y)\subseteq \left\langle \{\beta|_{Y}:\beta \in B\},\eta|_{Y}\right\rangle $ then $\left\langle \OP(X,Y),B\right\rangle =\T(X,Y)$.
\end{lemma}

\begin{proof}
Let $\gamma \in \T(X,Y)$ with $\rank \gamma =k \leq m$.
We will consider two cases.

\textit{Case 1.} Suppose that $\ker \gamma \in \mathcal{R}_{k}$.
Then $\ker \gamma$ contains a non-convex set which cannot be decomposed into two convex sets, which contain $1$ and $n$, respectively.
Since $k\leq m$, we can divide the partition $\ker \gamma$ into a partition
$P\in \mathcal{R}_{m}$ such that $P$ contains a non-convex set which cannot be decomposed into two convex sets, which contain $1$ and $n$, respectively
(if $k=m$ then we put $P=\ker \gamma$). Since $\mathcal{R}_{m}\subseteq \{\ker
\beta :\beta \in B\}$, there is $\lambda \in B$ with $\ker \lambda = P$.
It is clear that $X\lambda = Y$.\\
Further, let $X\gamma = \{y_1 < y_2 < \cdots < y_k\}$ and define the sets
\[A_i = \{x \in Y : x\lambda^{-1} \subseteq y_i\gamma^{-1}\}\]
for $i = 1,\ldots,k$. It is clear that $\{A_1, A_2, \ldots, A_k\}$ is a partition of $Y$.
Moreover, let $\{C_1 < C_2 < \cdots < C_k\} \in \mathcal{Q}_k$ be a partition of $X$
such that $|C_i \cap Y| = |A_i|$ for all $i = 1,\ldots,k$.
Let $A_i = \{a_{i_1} < a_{i_2} < \cdots < a_{i_{t_i}}\}$ and $C_i \cap Y = \{c_{i_1} < c_{i_2} < \cdots < c_{i_{t_i}}\}$ with $t_i \in \{1, \ldots, m\}$ for $i \in \{1, \ldots, k\}$.
We define a bijection
\[\sigma: \bigcup_{i=1}^k A_i = Y \longrightarrow \bigcup_{i=1}^k (C_i \cap Y) = Y\]
on $Y$ with $a_{i_l}\sigma = c_{i_l}$, for $l = 1,\ldots,t_i$ and $i = 1,\ldots,k$. Since $\sigma \in \S(Y)$ and
$\S(Y)\subseteq \left\langle \{\beta|_{Y}:\beta \in B\},\eta|_{Y}\right\rangle$ there is
$\mu \in \langle B, \eta\rangle$ with $\mu|_Y = \sigma$.\\
Finally, we define a transformation $\nu \in \O(X,Y) \subseteq \OP(X,Y)$ with
$\ker \nu = \{C_1 < C_2 < \cdots < C_k\}$ and $x\nu = y_i$ for all $x \in C_i$ and $i = 1,\ldots,k$.\\
Therefore, we have $\lambda, \mu, \nu \in \left\langle \OP(X,Y),B\right\rangle$ and it
remains to show that $\gamma = \lambda\mu\nu$, i.e. $\gamma \in \left\langle \OP(X,Y),B\right\rangle$.
Let $x \in X$. Then $x\gamma = y_i$ for some $i \in \{1,\ldots,k\}$ and we have
\[x\gamma = y_i \Rightarrow x\lambda = z \in A_i \Rightarrow z\mu = u \in C_i \cap Y \Rightarrow u\nu = y_i.\]
Hence, $x\gamma = y_i = x(\lambda\mu\nu)$ and we conclude $\gamma = \lambda\mu\nu$.

\textit{Case 2.} Suppose that $\ker \gamma \notin \mathcal{R}_{k}$, i.e.
$\ker \gamma \in \mathcal{Q}_{k}\cup \mathcal{P}_{k}$ and there is $\rho_{1}\in \OP(X,Y)$ with $\ker\rho_{1}=\ker \gamma$.
Further, there is a partition $P = \{D_{y} : y \in X\rho_{1}\} \in \mathcal{R}_{k}$
such that $y\in D_{y}$, for all $y\in X\rho_{1}$. Then we define a
transformation $\rho_{2} : X \rightarrow X\gamma$ with
$\ker\rho_{2} = P$ and $\{x\rho_2\} = y\rho_1^{-1}\gamma$ for all $x \in D_y$ and $y\in X\rho_{1}$.
Since $\ker \rho_{1}=\ker \gamma$, the transformation $\rho_2$ is
well defined and we have $\gamma = \rho_{1}\rho_{2}$.
Moreover, $\rho_2 \in \left\langle \OP(X,Y),B \right\rangle$
by Case 1 (since $\ker \rho_2 \in \mathcal{R}_{k}$) and thus
$\gamma =\rho_{1}\rho_{2}\in \left\langle \OP(X,Y),B \right\rangle$.
\end{proof}

\begin{lemma}\label{lenew}
$\left\langle \eta |_{Y}\right\rangle =\left\langle \left\{ \beta
|_{Y}:\beta \in \OP(X,Y)\right\} \right\rangle \cap \S(Y)$.
\end{lemma}

\begin{proof}
The inclusion $\left\langle \eta |_{Y}\right\rangle \subseteq \left\langle
\left\{ \beta |_{Y}:\beta \in \OP(X,Y)\right\} \right\rangle \cap \S(Y)$ is
obviously. Let now $\beta \in \OP(X,Y)$ with $\beta |_{Y}\in \S(Y)$. Then
there is $k\in \{1,\ldots ,m\}$ such that
\[
\beta =\left(
\begin{array}{cccccc}
A_{1} & \cdots  & A_{m-k+1} & A_{m-k} & \cdots  & A_{m} \\
a_{k} & \cdots  & a_{m} & a_{1} & \cdots  & a_{k-1}
\end{array}
\right)
\]
with $\{A_{1},A_{2}<\cdots <A_{m}\} \in \mathcal{P}_{m} \cup \mathcal{Q}_{m}$ and $a_{i}\in A_i$ for $i\in \{1,\ldots ,m\}$
since $Y$ is a transversal of $\ker \beta $. Thus,
\[
\beta |_{Y}=\left(
\begin{array}{cccccc}
a_{1} & \cdots  & a_{m-k+1} & a_{m-k} & \cdots  & a_{m} \\
a_{k} & \cdots  & a_{m} & a_{1} & \cdots  & a_{k-1}
\end{array}
\right) =(\eta |_{Y})^{m-k+1}\in \left\langle \eta |_{Y}\right\rangle.
\]
This shows that $\left\langle \left\{ \beta |_{Y}:\beta \in \OP(X,Y)\right\}
\right\rangle \cap \S(Y)\subseteq \{(\eta |_{Y})^{p}:p\in \mathbb{N}
\}=\left\langle \eta |_{Y}\right\rangle$.
\end{proof}

The following lemmas give us necessary conditions for a set $B\subseteq
\T(X,Y)$ to be a relative generating set of $\T(X,Y)$ modulo $\OP(X,Y)$.

\begin{lemma}\label{le8}
Let $B\subseteq \T(X,Y)\setminus \OP(X,Y)$ with $\left\langle \OP(X,Y),B\right\rangle =\T(X,Y)$.
Then $\S(Y)\subseteq \left\langle \{\beta |_{Y}:\beta \in B\},\eta|_{Y}\right\rangle$.
\end{lemma}

\begin{proof}
Let $\sigma \in \S(Y)$. We extend $\sigma$ to a transformation $\gamma : X \rightarrow Y$,
i.e. $\gamma|_{Y}=\sigma$. Hence, there are $\gamma_{1},\ldots,\gamma_{k}\in \OP(X,Y)\cup B$
(for a suitable natural number $k$) such that $\gamma=\gamma_{1}\cdots \gamma_{k}$.
Since the image of any transformation in $\T(X,Y)$ belongs to $Y$, we have
$\sigma =\gamma|_{Y}=\gamma_{1}|_{Y}\cdots \gamma_{k}|_{Y}$. Moreover, from $\sigma \in \S(Y)$,
we conclude $\gamma_{i}|_{Y}\in \S(Y)$ for $1\leq i\leq k$.
Let $\gamma_{i}\in \OP(X,Y)$ for some $i\in\{1,\ldots,k\}$. Then by Lemma \ref{lenew}
$$\gamma_{i}|_{Y}=\left(
\begin{array}{cccccc}
a_{1} & \cdots  & a_{t} & a_{t+1} & \cdots  & a_{m} \\
a_{m-t+1} & \cdots  & a_{m} & a_{1} & \cdots  & a_{m-t}
\end{array}
\right) \in \langle\eta |_{Y}\rangle$$
for a suitable natural number $t$. This shows $\sigma
\in \left\langle \{\beta |_{Y}:\beta \in B\},\eta |_{Y}\right\rangle$.
\end{proof}

\begin{lemma}\label{le9}
Let $B\subseteq \T(X,Y)\setminus \OP(X,Y)$ with $\left\langle \OP(X,Y),B\right\rangle =\T(X,Y)$.
Then $\mathcal{R}_{m}\subseteq \{\ker \beta :\beta \in B\}$.
\end{lemma}

\begin{proof}
Assume that there is $P\in \mathcal{R}_{m}$ with $P \not\in \{\ker \beta :\beta \in B\}$.
Let $\gamma \in \T(X,Y)$ with $\ker\gamma =P$. Then there are $\theta_{1}\in \OP(X,Y)\cup B$ and
$\theta_{2}\in \T(X,Y)$ such that $\gamma = \theta _{1}\theta _{2}$. Since
$\rank\gamma = m$, we obtain $\ker \gamma =\ker \theta_{1}= P$. Thus,
$\theta_{1}\not\in B$, i.e. $\theta_{1}\in \OP(X,Y)$ and
$\ker \theta_{1}\in \mathcal{Q}_{m}\cup \mathcal{P}_{m}$, contradicts $\ker \theta_{1} = P \in \mathcal{R}_{m}$.
\end{proof}
~~\\

Lemma \ref{le9} shows that $\rank(\T(X,Y):\OP(X,Y))\geq \left\vert \mathcal{R}_{m}\right\vert $. We will verify the equality.

\begin{lemma}\label{le10}
$\left\vert \mathcal{R}_{m}\right\vert = S(m,n)-\left(
\begin{array}{c}
n \\
m
\end{array}
\right)$.
\end{lemma}

\begin{proof}
The cardinality of the set $\mathcal{D}_{m}:=\mathcal{R}_{m}\cup \mathcal{P}_{m}$
was determined in \cite{TK}. The
authors show that $\left\vert \mathcal{D}_{m}\right\vert
=S(m,n)-\left(
\begin{array}{c}
n-1 \\
m-1
\end{array}
\right)$. Because of $\mathcal{R}_{m}\cap \mathcal{P}_{m}=\emptyset$, we
obtain $\mathcal{R}_{m}=\mathcal{D}_{m}\setminus \mathcal{P}_{m}$. Since
$|\mathcal{P}_{m}| =\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right)$ (see Remark \ref{re1}) it follows $\left\vert \mathcal{R}_{m}\right\vert =\left\vert \mathcal{D}_{m}\right\vert
-\left\vert \mathcal{P}_{m}\right\vert =S(m,n)-\left(
\begin{array}{c}
n-1 \\
m-1
\end{array}
\right) -\left(
\begin{array}{c}
n-1 \\
m
\end{array}
\right) =S(m,n)-\left(
\begin{array}{c}
n \\
m
\end{array}
\right)$.
\end{proof}
~~\\

Finally, we can state the relative rank of $\T(X,Y)$ modulo $\OP(X,Y)$.

\begin{theorem}\label{th11}
$\rank(\T(X,Y):\OP(X,Y))=S(m,n)-\left(
\begin{array}{c}
n \\
m
\end{array}
\right)$.
\end{theorem}

\begin{proof}
If $m=1$ then $\T(X,Y)=\OP(X,Y)$, i.e. $\rank(\T(X,Y):\OP(X,Y))=0$. On the other hand, we have
$S(1,n)=n=\left(
\begin{array}{c}
n \\
1
\end{array}
\right) $. Suppose now that $n\geq 2$.
By Lemmas \ref{le9} and \ref{le10}, we obtain $\rank(\T(X,Y):\OP(X,Y))\geq \left\vert
\mathcal{R}_{m}\right\vert =S(m,n)-\left(
\begin{array}{c}
n \\
m
\end{array}
\right) $. In order to prove the equality, we have to find a relative
generating set $B$ of $\T(X,Y)$ modulo $\OP(X,Y)$ with $\left\vert
B \right\vert = |\mathcal{R}_{m}|$.
We observe that for each $P \in \mathcal{R}_{m}$, there
is $\beta_P \in \T(X,Y)$ with $\ker \beta_P = P$, which will be fixed.
Let $\mathcal{B} := \{\beta_P : P \in \mathcal{R}_{m}\}$.
If $m=2$ then $\mathcal{R}_{m}=\emptyset$ and $\S(Y)=\{\eta |_{Y},(\eta |_{Y})^{2}\} = \langle \eta |_{Y} \rangle$, obviously.
If $m\geq 3$ then without loss of generality we can assume that there is $P'\in \mathcal{R}_{m}$ such
that $Y$ is a transversal of $\ker \beta_{P'}$ and
$\beta_{P'}|_{Y}=\left(
\begin{array}{ccccc}
a_{1} & a_{2} & a_{3} & \cdots  & a_{m} \\
a_{2} & a_{1} & a_{3} & \cdots  & a_{m}
\end{array}
\right)$.
It is well known that $\S(Y)=\left\langle \beta_{P'}|_Y, \eta|_Y \right\rangle$.
Hence, $\mathcal{B}$ is a relative generating set of $\T(X,Y)$ modulo $\OP(X,Y)$ by Lemma \ref{le7}.
Since $|\mathcal{B}| = |\mathcal{R}_{m}|$, we obtain the required result.
\end{proof}

Now we will characterize the minimal relative generating sets of $\T(X,Y)$ modulo $\OP(X,Y)$. The minimal relative generating sets do not coincide with the relative generating sets of size $\rank(\T(X,Y):\OP(X,Y))$.

\begin{theorem}
Let $B\subseteq \T(X,Y)$. Then $B$ is a minimal relative generating set of $\T(X,Y)$ modulo $\OP(X,Y)$ if and only if there is a set $\widetilde{B}\subseteq B$ such that the following three statements are satisfied:\newline
$(i)$ $\mathcal{R}_{m} \subseteq \{\ker \beta :\beta \in B\setminus \widetilde{B}\}$,\newline
$(ii)$ $|B\setminus \widetilde{B}| = |\mathcal{R}_{m}|$, \newline
$(iii)$ $\S(Y) \subseteq \left\langle \{\beta|_{Y}:\beta \in B\}, \eta|_{Y} \right\rangle$ but
$\S(Y) \nsubseteq \left\langle \{\beta |_{Y}:\beta \in B\setminus \{\gamma\}\}, \eta|_{Y} \right\rangle$
for any $\gamma \in B$ with $\ker \gamma \in \{\ker \beta : \beta \in \widetilde{B}\}$.
\end{theorem}

\begin{proof}
Suppose that the conditions $(i) - (iii)$ are satisfied. Then
by Lemma \ref{le7} we have $\left\langle \OP(X,Y),B\right\rangle =\T(X,Y)$.
It remains to show that $B$ is minimal. Assume that there is $\gamma
\in B$ such that $\left\langle \OP(X,Y),B\setminus \{\gamma \}\right\rangle
=\T(X,Y)$. Note that $\alpha \beta |_{Y}=\alpha |_{Y}\beta |_{Y}$ for all
$\alpha ,\beta \in \T(X,Y)$. Hence, we can conclude that $\S(Y)\subseteq
\left\langle \left\{ \beta |_{Y}:\beta \in \T(X,Y)\right\} \right\rangle
\subseteq \left\langle \left\{ \beta |_{Y}:\beta \in \OP(X,Y)\cup (B\setminus
\{\gamma \})\right\} \right\rangle =\left\langle \left\{ \beta |_{Y}:\beta
\in B\setminus \{\gamma \}\right\} ,\eta |_{Y}\right\rangle $ by Lemma \ref{lenew}.
Hence, $\ker \gamma \notin \{\ker\beta :\beta \in \widetilde{B}\}$ by $(iii)$.
This implies that $\gamma \in B\setminus \widetilde{B}$ and
$|(B\setminus \widetilde{B})\setminus \{\gamma \}|<|\mathcal{R}_{m}|$ by $(ii)$,
i.e. $\mathcal{R}_{m}\nsubseteqq \{\ker \beta :\beta \in (B\setminus \widetilde{B})\setminus \{\gamma \}\}$.
Since $\ker\gamma \notin \{\ker \beta :\beta \in \widetilde{B}\}$, we have
$\mathcal{R}_{m}\nsubseteqq \{\ker \beta :\beta \in (B\setminus \{\gamma \})\}$ and by
Lemma \ref{le9}, we obtain that $\left\langle \OP(X,Y),B\setminus \{\gamma
\}\right\rangle \neq \T(X,Y)$, a contradiction. This shows that $B$ is a
minimal relative generating set of $\T(X,Y)$ modulo $\OP(X,Y)$.

Conversely, let $B$ be a minimal relative generating set of $\T(X,Y)$ modulo
$\OP(X,Y)$. We have $\mathcal{R}_{m}\subseteq
\{\ker \beta :\beta \in B\}$ and $\S(Y)\subseteq \left\langle \{\beta
|_{Y}:\beta \in B\},\eta |_{Y}\right\rangle $ by Lemma \ref{le9} and Lemma \ref{le8},
respectively. Then there exists a set  $\widetilde{B}\subseteq B$ with
$|B\setminus \widetilde{B}| = |\mathcal{R}_{m}|$
and $\mathcal{R}_{m}\subseteq \{\ker \beta :\beta \in (B\setminus \widetilde{B})\}$.
For the set $\widetilde{B}$, the conditions $(i)$ and $(ii)$ are satisfied. Assume
now that there is $\gamma \in B$ with $\ker \gamma \in \{\ker \beta :\beta
\in \widetilde{B}\}$ such that $\S(Y)\subseteq \left\langle \{\beta
|_{Y}:\beta \in B\setminus \{\gamma\}\},\eta |_{Y}\right\rangle$. Then
because of $\mathcal{R}_{m}\subseteq \{\ker \beta :\beta \in (B\setminus \{\gamma\})\}$,
the set $B\setminus \{\gamma)$ is a relative generating set of
$\T(X,Y)$ modulo $\OP(X,Y)$ by Lemma \ref{le7}. This contradicts the minimality of $B$.
Consequently, $(iii)$ is satisfied.
\end{proof}
~~\\

In particular, for the relative generating sets of minimal size we have

\begin{remark}
$B\subseteq \T(X,Y)$ is a relative generating set of $\T(X,Y)$ modulo $\OP(X,Y)$ of minimal size if and only if
$\widetilde{B}=\emptyset$.
\end{remark}


TITLE: Relationship between eigendecomposition and singular value decomposition
QUESTION [38 upvotes]: Let $A \in \mathbb{R}^{n\times n}$ be a real symmetric matrix. Please help me clear up some confusion about the relationship between the singular value decomposition of $A$ and the eigen-decomposition of $A$.
Let $A = U\Sigma V^T$ be the SVD of $A$. Since $A = A^T$, we have $AA^T = A^TA = A^2$ and:
$$A^2 = AA^T = U\Sigma V^T V \Sigma U^T = U\Sigma^2 U^T$$
$$A^2 = A^TA = V\Sigma U^T U\Sigma V^T = V\Sigma^2 V^T$$
Both of these are eigen-decompositions of $A^2$. Now consider some eigen-decomposition of $A$
$$A = W\Lambda W^T$$
Then
$$A^2 = W\Lambda W^T W\Lambda W^T = W\Lambda^2 W^T$$
So $W$ also can be used to perform an eigen-decomposition of $A^2$.
So now my confusion:
It seems that $A = W\Lambda W^T$ is also a singular value decomposition of A. But singular values are always non-negative, and eigenvalues can be negative, so something must be wrong.
What is going on?

REPLY [32 votes]: If $A = U \Sigma V^T$ and $A$ is symmetric, then $V$ is almost $U$ except for the signs of columns of $V$ and $U$.
$$A = W \Lambda W^T = \displaystyle \sum_{i=1}^n w_i \lambda_i w_i^T = \sum_{i=1}^n w_i \left| \lambda_i \right| \text{sign}(\lambda_i) w_i^T$$ where $w_i$ are the columns of the matrix $W$.
The left singular vectors $u_i$ are $w_i$ and the right singular vectors $v_i$ are $\text{sign}(\lambda_i) w_i$. (You can of course put the sign term with the left singular vectors as well.)The singular values $\sigma_i$ are the magnitude of the eigen values $\lambda_i$.
Hence, $A = U \Sigma V^T = W \Lambda W^T$
and $$A^2 = U \Sigma^2 U^T = V \Sigma^2 V^T = W \Lambda^2 W^T$$
Note that the eigenvalues of $A^2$ are positive.


TITLE: Find the area described by $S=\{(x,y)\mid -2<x\leq 0, 0\leq y\leq 2/\sqrt{x+2}\}$
QUESTION [0 upvotes]: Find the area described by $S=\{(x,y)\mid -2<x\leq 0, 0\leq y\leq 2/\sqrt{x+2}\}$.
I have tried to use logic to figure out what to do but cannot figure it out. I have tried to think about this region as a set of values that satisfy the conditions but then I have no idea how to integrate it if that is the case. Thank you.

REPLY [1 votes]: $\int_{-2}^0 \dfrac{2}{\sqrt{x+2}} dx =4\sqrt{x+2}\quad|_{-2}^0=4\sqrt{2}$


TITLE: Trigonometry inequation with cotangent
QUESTION [2 upvotes]: The second term equals $-\tan x$ and for the 3rd term I used the identity of $\cot(a+b)$. I obtain $\sqrt{3}\cot^3 x+3\cot^2 x-3\sqrt{3}\cot x-1$ How can I factorize this and solve the inequation?

REPLY [0 votes]: Instead of using the formula for $\cot(a+b)$, let us use
$$\cot a+\cot b=\dfrac{\sin(a+b)}{\sin a\sin b}$$
$\cot x+\cot(x+\frac{\pi}{2})=\dfrac{\cos 2x}{\sin x\cos x}=2\cot(2x)$
We obtain
$2\cot (2x)+2\cot(x+\frac{\pi}{3})=2\left(\cot (2x)+\cot(x+\frac{\pi}{3})\right)$. Use the same identity on the last parenthesis.


TITLE: Why can AdS/CFT correspondence be applied to condensed matter systems when their space is not anti-deSitter?
QUESTION [2 upvotes]: The AdS/CFT correspondence postulates a duality between string theory of gravity and a CFT on an AdS background. This duality is employed in some condensed matter systems. I was wondering why it is applicable here when the condensed matter system in a laboratory is described by a quantum field theory that doesn't reside in AdS space - our space isn't AdS. Keep in mind I have studied general relativity and quantum field theory but not string theory.

REPLY [2 votes]: You mixed it up.
CFT lives in the flat Minkowski spacetime. It is the gravitional side of the equivalence that lives in the AdS spacetime. That's why in the name you have AdS and CFT separated by slash - they denote two different sides of the correspondence.
E.g. the nost famous case is the equivalence of the $\mathcal{N}=4$ supersymmetric Yang-Mills theory in the 4-dimensional Minkowski spacetime (which is CFT) with the Type IIb string theory in $AdS_5\times S_5$.
One of the most basic signs of the equivalence is that the conformal group of the $d$-dimensional Minkowski spacetime $SO(2,d)$ is exactly the isometry group of the $d+1$-dimensional AdS.


text:
\section{Introduction}\label{sec:intro}

The application and computation of optimal transport (OT) plans has recently received a great deal of attention within the machine learning community.
Applications of optimal transport in machine learning include generative modeling
\citep{arjovsky2017wasserstein, deshpande2018generative, genevay2017learning,  kolouri2018sliced,salimans2018improving}
and supervised learning \citep{frogner2015learning, janati2019wasserstein, Luise2018DifferentialPO}.
In this paper, we study the optimal transport (OT) problem in the case where the objects of interest are stationary Markov chains or processes possessing hidden Markov structure.
The problem of interest to us is distinct from traditional applications of coupling to Markov chains, e.g.,
to establish convergence to a stationary distribution.
Our interest is in the computation of optimal transport plans for Markov chains that explicitly account for both stationarity
and Markovian structure.
In particular, we develop algorithms for computing solutions to a Markov-constrained form of the OT problem.
The algorithms leverage recent advances in computational OT as well as techniques from Markov decision processes.

The principled extension of computational OT techniques to classes of distributions that possess additional structure, such as martingales or dependent processes, is an important direction of research.  Indeed, some variations of constrained OT have been considered in recent work \citep{beiglbock2013model,zaev2015monge,forrow2019statistical,moulos2020bicausal,backhoff2020estimating}, and

several recent applications of OT have focused on dependent observations \citep{schiebinger2019optimal,xu2018distilled}.

Extensions of OT to dependent processes open the door to new applications in climate science, finance, epidemiology and other fields, where it is common for observations to possess temporal or spatial structure.
The OT problem that we consider is tailored to the alignment and comparison of Markov chains and hidden
Markov models (HMMs).
As an illustration, we describe in Section \ref{sec:experiments} an application of the proposed techniques to
the analysis of computer-generated music.

The primary contributions of this paper are as follows:
\begin{itemize}
\item We formulate a constrained version of the OT problem for stationary Markov chains, referred to as the optimal transition coupling (OTC) problem.
The OTC problem aims to align the two chains of interest so as to minimize long-term average cost while preserving Markovity and stationarity.

\item We detail an extension of the OTC problem to HMMs.

In particular, we describe how one may couple a pair of HMMs via a coupling of their hidden chains using a cost that is derived from the OT cost between their emission distributions.

\item
We establish a useful connection between the OTC problem and Markov decision processes (MDPs) that
provides a means of computing optimal solutions in an efficient manner.

Leveraging this connection, we arrive at an algorithm combining policy iteration \citep{howard1960dynamic} with OT solvers that we refer to as \texttt{ExactOTC} (Algorithm \ref{alg:pia}).
We state in Theorem \ref{thm:convergence_of_pia} that if the two Markov chains of interest are irreducible, then \texttt{ExactOTC} converges to a solution of the OTC problem in a finite number of iterations.

\item
We introduce an entropically-constrained OTC problem and an associated regularized algorithm, referred to as \texttt{EntropicOTC} (Algorithm \ref{alg:fastentropic_pia}), that exhibits improved computational efficiency in theory and in practice.

In Theorems \ref{thm:policy_evaluation_complexity} and \ref{thm:policy_improvement_complexity}, we establish upper bounds on the computational complexity of this algorithm, demonstrating that the runtime of each iteration is nearly-linear in the dimension of the couplings under study.
This dependence is comparable to the state-of-the-art for computational OT.

\item We prove a stability result for the OTC problem, stated formally in Theorem \ref{thm:consistency}.
Consistency of the plug-in estimate of the optimal transition coupling and its expected cost follows as a corollary (see Corollary \ref{cor:consistency}).
\end{itemize}

The rest of the paper is organized as follows:
We begin by providing some background on optimal transport and define the OTC problem in Section \ref{sec:background_on_otc}.
In Section \ref{sec:hmm}, we detail our extension of the OTC problem to HMMs.
In Section \ref{sec:computing}, we establish the connection between the OTC problem and MDPs and state our result regarding \texttt{ExactOTC} for obtaining optimal transition couplings.
A faster, regularized algorithm \texttt{EntropicOTC} for computing optimal transition couplings is described
in Section \ref{sec:fast_approx_pia}.
In Section \ref{sec:consistency} we present our result regarding the stability of the OTC problem and the statistical consistency of optimal transition couplings computed from data.
In Section \ref{sec:experiments} we describe a simulation study and an application of our algorithms to computer-generated music.
We close with a discussion of our results in Section \ref{sec:conclusion}.
Proofs for all stated results may be found in Section \ref{sec:proofs}.

Finally, an appendix containing some supplementary results and information may be found in the accompanying supplemental material.

\paragraph{Notation.} Let $\bbR_+$ be the non-negative reals and $\Delta_n = \{u \in \mathbb{R}^n_+ | \sum_{i=1}^n u_i = 1\}$ denote the probability simplex in $\bbR^n$.
Given a metric space $\calU$, let $\calM(\calU)$ denote the set of Borel probability measures on $\calU$.
For a vector $u \in \bbR^n$, let $\|u\|_\infty = \max_i |u_i|$ and $\|u\|_1 = \sum_i |u_i|$.
Occasionally we will treat matrices in $\bbR^{n\times n}$ as vectors in $\bbR^{n^2}$.


text:
{\bf Problem.} The sum of three numbers $a$, $b$, and $c$ is 99. If we increase $a$ by 6, decrease $b$ by 6 and multiply $c$ by 5, the three resulting numbers are equal. What is the value of $b$?
{\bf Level.} Level 4
{\bf Type.} Algebra
{\bf Solution.} We are given the equations $a+b+c=99$ and $a+6=b-6=5c$.  Solve $b-6=5c$ for $b$ to find $b=5c+6$, and solve $5c=a+6$ for $a$ to find $a=5c-6$.  Substituting both of these equations into $a+b+c=99$, we have $(5c-6)+(5c+6)+c=99$.  Simplifying the left hand side, we get $11c=99$ which implies $c=9$.  Substituting into $b=5c+6$, we have $b=5(9)+6=\boxed{51}$.

set_name: MATH


TITLE: check convergence $\int _{-\infty }^0\:\frac{e^{3x}}{1+x^2} $
QUESTION [1 upvotes]: check convergence of  $\int _{-\infty }^0\:\frac{e^{3x}}{1+x^2} $

so for $x\le0$ : $e^{3x}\le1$ then we get $0\le\frac{e^{3x}}{1+x^2}\le\frac{1}{1+x^2}\le\frac{1}{x^2}$
and because $\int _{-\infty }^{-1}\:\frac{1}{x^2}$ is convergence we get $\int _{-\infty }^0\:\frac{e^{3x}}{1+x^2} $ is convergence
is that answer correct
thanks alot

REPLY [0 votes]: $f(x)=\frac{e^{-3x}}{1+x^2}$ is a positive function on $\mathbb{R}^+$ and
$$\int_{0}^{+\infty}\frac{e^{-3x}}{1+x^2}\,dx\stackrel{\text{Cauchy-Schwarz}}{\leq}\sqrt{\int_{0}^{+\infty}e^{-6x}\,dx \int_{0}^{+\infty}\frac{dx}{(1+x^2)^2}}=\sqrt{\frac{\pi}{24}}. $$
This inequality can also be improved up to
$$\int_{0}^{+\infty}\frac{e^{-3x}}{1+x^2}\,dx\stackrel{\text{Cauchy-Schwarz}}{\leq}\sqrt{\int_{0}^{+\infty}(1+x)^3e^{-6x}\,dx \int_{0}^{+\infty}\frac{dx}{(1+x^2)^2 (1+x)^3}}=\sqrt{\frac{61(8-\pi)}{3456}}=\color{green}{0.29}2836\ldots $$


text:
theory TopoS_Impl
imports TopoS_Library TopoS_Composition_Theory_impl
    (*Mehr Meta wagen!*)
    "Security_Invariants/METASINVAR_SystemBoundary"
    (*stuff*)
    "Lib/ML_GraphViz"
    TopoS_Stateful_Policy_impl
begin

section \<open>ML Visualization Interface\<close>

definition print_offending_flows_debug ::
  "'v  SecurityInvariant list \<Rightarrow> 'v list_graph \<Rightarrow> (string \<times> ('v \<times> 'v) list list) list" where
  "print_offending_flows_debug M G = map
    (\<lambda>m.
         (implc_description m @ '' ('' @ implc_type m @ '')''
         , implc_offending_flows m G)
    ) M"

(*TODO: move and tune*)
ML\<open>
fun pretty_assoclist ctxt header t = let
    val ls : (term * term) list = t |> HOLogic.dest_list |> map HOLogic.dest_prod;
    val pretty = fn t => Pretty.string_of (Syntax.pretty_term ctxt t);
    in ls
       |> map (fn (x, y) => "  "^pretty x^": "^pretty y)
       |> space_implode "\n"
       |> (fn s => header^s)
       |> writeln end
\<close>

subsection\<open>Utility Functions\<close>

  fun rembiflowdups :: "('a \<times> 'a) list \<Rightarrow> ('a \<times> 'a) list" where
    "rembiflowdups [] = []" |
    "rembiflowdups ((s,r)#as) = (if (s,r) \<in> set as \<or> (r,s) \<in> set as then rembiflowdups as else (s,r)#rembiflowdups as)"

  lemma rembiflowdups_complete: "\<lbrakk> \<forall>(s,r) \<in> set x. (r,s) \<in> set x \<rbrakk> \<Longrightarrow> set (rembiflowdups x) \<union> set (backlinks (rembiflowdups x)) = set x"
    proof
      assume a: "\<forall>(s,r) \<in> set x. (r,s) \<in> set x"
      have subset1: "set (rembiflowdups x) \<subseteq> set x"
        apply(induction x)
         apply(simp)
        apply(clarsimp)
        apply(simp split: if_split_asm)
         by(blast)+
      have set_backlinks_simp: "\<And> x. \<forall>(s,r) \<in> set x. (r,s) \<in> set x \<Longrightarrow> set (backlinks x) = set x"
        apply(simp add: backlinks_set)
        apply(rule)
         by fast+
      have subset2: "set (backlinks (rembiflowdups x)) \<subseteq> set x"
        apply(subst set_backlinks_simp[OF a, symmetric])
        by(simp add: backlinks_subset subset1)

      from subset1 subset2
      show "set (rembiflowdups x) \<union> set (backlinks (rembiflowdups x)) \<subseteq> set x" by blast
    next
      show "set x \<subseteq> set (rembiflowdups x) \<union> set (backlinks (rembiflowdups x))"
        apply(rule)
        apply(induction x)
         apply(simp)
        apply(rename_tac a as e)
        apply(simp)
        apply(erule disjE)
         apply(simp)
         defer
         apply fastforce
        apply(case_tac a)
        apply(rename_tac s r)
        apply(case_tac "(s,r) \<notin> set as \<and> (r,s) \<notin> set as")
         apply(simp)
        apply(simp add: backlinks_set)
        by blast
      qed

  text\<open>only for prettyprinting\<close>
  definition filter_for_biflows:: "('a \<times> 'a) list \<Rightarrow> ('a \<times> 'a) list" where
    "filter_for_biflows E \<equiv> [e \<leftarrow> E. (snd e, fst e) \<in> set E]"

  definition filter_for_uniflows:: "('a \<times> 'a) list \<Rightarrow> ('a \<times> 'a) list" where
    "filter_for_uniflows E \<equiv> [e \<leftarrow> E. (snd e, fst e) \<notin> set E]"

  lemma filter_for_biflows_correct: "\<forall>(s,r) \<in> set (filter_for_biflows E). (r,s) \<in> set (filter_for_biflows E)"
    unfolding filter_for_biflows_def
    by(induction E, auto)

  lemma filter_for_biflows_un_filter_for_uniflows: "set (filter_for_biflows E) \<union> set (filter_for_uniflows E) = set E"
    apply(simp add: filter_for_biflows_def filter_for_uniflows_def) by blast

  definition partition_by_biflows :: "('a \<times> 'a) list \<Rightarrow> (('a \<times> 'a) list \<times> ('a \<times> 'a) list)" where
    "partition_by_biflows E \<equiv> (rembiflowdups (filter_for_biflows E), remdups (filter_for_uniflows E))"

  lemma partition_by_biflows_correct: "case partition_by_biflows E of (biflows, uniflows) \<Rightarrow> set biflows \<union> set (backlinks (biflows)) \<union> set uniflows = set E"
    apply(simp add: partition_by_biflows_def)
    by(simp add: filter_for_biflows_un_filter_for_uniflows filter_for_biflows_correct rembiflowdups_complete)

  lemma "partition_by_biflows [(1::int, 1::int), (1,2), (2, 1), (1,3)] = ([(1, 1), (2, 1)], [(1, 3)])" by eval

ML\<open>
(*apply args to f. f ist best supplied using @{const_name "name_of_function"} *)
fun apply_function (ctxt: Proof.context) (f: string) (args: term list) : term =
  let
    val _ = writeln ("applying "^f^" to " ^ (fold (fn t => fn acc => acc^(Pretty.string_of (Syntax.pretty_term (Config.put show_types true ctxt) t))^" ") args ""));
    (*val t_eval = Code_Evaluation.dynamic_value_strict thy t;*)
    (* $ associates to the left, give f its arguments*)
    val applied_untyped_uneval: term = list_comb (Const (f, dummyT), args);
    val applied_uneval: term = Syntax.check_term ctxt applied_untyped_uneval;
  in
    applied_uneval |> Code_Evaluation.dynamic_value_strict ctxt
  end;

(*ctxt -> edges -> (biflows, uniflows)*)
fun partition_by_biflows ctxt (t: term) : (term * term) =
  apply_function ctxt @{const_name "partition_by_biflows"} [t] |> HOLogic.dest_prod

local
  fun get_tune_node_format (edges: term) : term -> string -> string =
    if (fastype_of edges) = @{typ "(string \<times> string) list"}
    then
      tune_string_vertex_format
    else
      Graphviz.default_tune_node_format;

  fun evalutae_term ctxt (edges: term) : term =
    case Code_Evaluation.dynamic_value ctxt edges
      of SOME x => x
      | NONE => raise TERM ("could not evaluate", []);
in
  fun visualize_edges ctxt (edges: term) (coloredges: (string * term) list) (graphviz_header: string) =
    let
      val _ = writeln("visualize_edges");
      val (biflows, uniflows) = partition_by_biflows ctxt edges;
    in
      Graphviz.visualize_graph_pretty ctxt (get_tune_node_format edges) ([
      ("", uniflows),
      ("edge [dir=\"none\", color=\"#000000\"]", biflows)] @ coloredges) (*dir=none, dir=both*)
       graphviz_header
    end

  (*iterate over the edges in ML, useful for printing them in certain formats*)
  fun iterate_edges_ML ctxt (edges: term) (all: (string*string) -> unit) (bi: (string*string) -> unit) (uni: (string*string) -> unit): unit =
    let
      val _ = writeln("iterate_edges_ML");
      val tune_node_format = (get_tune_node_format edges);
      val node_to_string = Graphviz.node_to_string ctxt tune_node_format;
      val evaluated_edges : term = evalutae_term ctxt edges;
      val (biflows, uniflows) = partition_by_biflows ctxt evaluated_edges;
    in
      let
        fun edge_to_list (es: term) : (term * term) list = es |> HOLogic.dest_list |> map HOLogic.dest_prod;
        fun edge_to_string (es: (term * term) list) : (string * string) list =
          map (fn (v1, v2) => (node_to_string v1, node_to_string v2)) es
      in
        edge_to_list evaluated_edges |> edge_to_string |> map all;
        edge_to_list biflows |> edge_to_string |> map bi;
        edge_to_list uniflows |> edge_to_string |> map uni;
        ()
      end
      handle Subscript => writeln ("Subscript Exception in iterate_edges_ML")
    end;

end
\<close>

ML_val\<open>
local
  val (biflows, uniflows) = partition_by_biflows @{context} @{term "[(1::int, 1::int), (1,2), (2, 1), (1,3)]"};
in
  val _ = Pretty.writeln (Syntax.pretty_term (Config.put show_types true @{context}) biflows);
  val _ = Pretty.writeln (Syntax.pretty_term (Config.put show_types true @{context}) uniflows);
end;

val t = fastype_of @{term "[(''x'', 2::nat)]"};

\<close>
ML_val\<open>(*
visualize_edges @{context}  @{term "[(1::int, 1::int), (1,2), (2, 1), (1,3)]"} []; *)
\<close>

definition internal_get_invariant_types_list:: "'a SecurityInvariant list \<Rightarrow> string list" where
  "internal_get_invariant_types_list M \<equiv> map implc_type M"

definition internal_node_configs :: "'a list_graph \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> ('a \<times>'b) list" where
  "internal_node_configs G config \<equiv> zip (nodesL G) (map config (nodesL G))"

ML \<open>
local
  fun get_graphivz_node_desc ctxt (node_config: term): string =
   let
     val (node, config) = HOLogic.dest_prod node_config;
     (*TODO: tune node format? There must be a better way ...*)
     val tune_node_format = if (fastype_of node) = @{typ "string"}
      then
        tune_string_vertex_format
      else
        Graphviz.default_tune_node_format;
     val node_str = Graphviz.node_to_string ctxt tune_node_format node;
     val config_str = Graphviz.term_to_string_html ctxt config;
   in
     node_str^"[label=<

"^node_str^"

"^config_str^"

>]\n"
   end;
in
  fun generate_graphviz_header ctxt (G: term) (configs: term): string =
    let
      val configlist: term list = apply_function ctxt @{const_name "internal_node_configs"} [G, configs] |> HOLogic.dest_list;
    in
      fold (fn c => fn acc => acc^get_graphivz_node_desc ctxt c) configlist ""
    end;
end;

(* Convenience function. Use whenever possible!
  M: security requirements, list
  G: list_graph*)
fun visualize_graph_header ctxt (M: term) (G: term) (Config: term): unit =
  let
    val wf_list_graph = apply_function ctxt @{const_name "wf_list_graph"} [G];
    val all_fulfilled = apply_function ctxt @{const_name "all_security_requirements_fulfilled"} [M, G];
    val edges = apply_function ctxt @{const_name "edgesL"} [G];
    val invariants = apply_function ctxt @{const_name "internal_get_invariant_types_list"} [M];
    val _ = writeln("Invariants:" ^ Pretty.string_of (Syntax.pretty_term ctxt invariants));
    val header = if Config = @{term "[]"} then "#header" else generate_graphviz_header ctxt G Config;
  in
    if wf_list_graph = @{term "False"} then
      error ("The supplied graph is syntactically invalid. Check wf_list_graph.")
    else if all_fulfilled = @{term "False"} then
      (let
        val offending = apply_function ctxt @{const_name "implc_get_offending_flows"} [M, G];
        val offending_flat = apply_function ctxt @{const_name "List.remdups"} [apply_function ctxt @{const_name "List.concat"} [offending]];
        val offending_debug = apply_function ctxt @{const_name print_offending_flows_debug} [M, G];
      in
       writeln("offending flows:");
       Pretty.writeln (Syntax.pretty_term ctxt offending);
       pretty_assoclist ctxt "Offending flows per invariant:\n" offending_debug;
       visualize_edges ctxt edges [("edge [dir=\"arrow\", style=dashed, color=\"#FF0000\", constraint=false]", offending_flat)] header;
      () end)
    else if all_fulfilled <> @{term "True"} then raise ERROR "all_fulfilled neither False nor True" else (
       writeln("All valid:");
       visualize_edges ctxt edges [] header;
      ())
  end;

fun visualize_graph ctxt (M: term) (G: term): unit = visualize_graph_header ctxt M G @{term "[]"};
\<close>

end

subset_name: curated


TITLE: Density functions for ordered statistics, how to find $\mu$ and the density function of a minimum
QUESTION [0 upvotes]: Problem: Let Y denote the amount of milk (in gallons) remaining in a 1-gallon container on its expiration date. Suppose that the density function for Y is $f(y)=2y$ for $0 \le y \le 1$. Suppose that a random sample of 5 gallons of milk is taken and the amount of milk remaining on the expiration date is recorded.
a.) Find $\mu$
b.) Find the density function of the minimum, $Y_{(1)}$
I know that the density function for any order statistic, $k^{th}$ , is as follows
$$g_{(k)}(y)= \left(\frac{n!}{(k-1)!(n-k)!1!}\right)\left(F_Y(y)\right)^{k-1}\left(1-F_Y(y)\right)^{n-k}\left(f_Y(y)\right)$$
Part a.) We had a similar (less complicated) example in our notes where we found the density function for the median and then used that to find the Expected value. Is this the proper route to solve this problem as well? If so, I am confused as to what the median is in this example. Would it be the median amount of 1-gallon, $k=.5$, where $n=1$? Or the median amount of all 5 1-gallon containers combined, $k=2.5$, where $n=5$?
Part b.) How is the minimum  $Y_{(1)}$ ? Is this using the sample size $n=5$? Is 1 referring to 1 gallon? Is 1 the minimum because the event $\left(Y_{(n)} \le y \right)$ will only occur iff the events $\left(Y_i \le y \right)$ for every $i = 1,2,3,...,n$?

REPLY [0 votes]: (a) If by $\mu$ you mean $E(Y)$ then
\begin{align}
E(y) &= \int_{y=0}^{1} yf_Y(y)\;dy \\
&= \int_0^1 2y^2\;dy \\
&= 2/3.
\end{align}
You don't need the median at all for this.
(b) The formula you have for $g_{(k)}(y)$ is the way to go. Here, we have $n=5, k=1$ and $F_Y(y) = \int_0^y 2y\; dy = y^2$. If my calculation is correct, you should end up with pdf $g_{(1)}(y) = 10y(1-y^2)^4$.
You seem to be confused by the notation $Y_{(1)}$ for the first-order statistic random variable. We have $5$ samples and so, firstly, we have $5$ random variables: $Y_1, Y_2, Y_3, Y_4, Y_5,$ with $Y_1$ being the $Y$ value for the first sample, and so on.
Next, we have $5$ order statistic random variables: $Y_{(1)}, Y_{(2)}, Y_{(3)}, Y_{(4)}, Y_{(5)}$, defined:
\begin{align}
Y_{(1)} &= \text{Smallest value of $Y_1, Y_2, Y_3, Y_4, Y_5$} \\
Y_{(2)} &= \text{Second smallest value of $Y_1, Y_2, Y_3, Y_4, Y_5$} \\
Y_{(3)} &= \text{Third smallest value of $Y_1, Y_2, Y_3, Y_4, Y_5$} \\
Y_{(4)} &= \text{Fourth smallest value of $Y_1, Y_2, Y_3, Y_4, Y_5$} \\
Y_{(5)} &= \text{Largest value of $Y_1, Y_2, Y_3, Y_4, Y_5$}.
\end{align}


TITLE: Finding $T^\dagger$ where $T\varphi(x)=\varphi(x+a)$
QUESTION [2 upvotes]: Finding $T^\dagger$ where $T\varphi(x)=\varphi(x+a)$. It is a pretty straightforward and I imagine easy question.

REPLY [3 votes]: I will only give you a hint. The adjoint $T^\dagger$ is defined by the property
$$ ( \psi, T\varphi ) = (T^\dagger\psi, \varphi) $$
for all wave functions $\psi, \varphi$.
Here, $(\psi, \varphi) = \int_{-\infty}^\infty \psi(x)^\ast \varphi(x) \, \mathrm dx$ is the inner product.
In other words: given a function $\psi(x)$, you must find another function $f(x)$ so that
$$ \int_{-\infty}^\infty \psi(x)^\ast \varphi(x+a) \, \mathrm dx = \int_{-\infty}^\infty f(x)^\ast \varphi(x) \, \mathrm dx $$
for all $\varphi$.
If you can find such a function $f$, then $T^\dagger \psi = f$.


TITLE: Center of the universal enveloping algebra
QUESTION [4 upvotes]: Suppose I have non-abelian 2-dimensional Lie algebra or 3-dimensional Heisenberg algebra.
How to calculate the center of universal enveloping algebra in this cases?

REPLY [5 votes]: Let $U(\mathfrak h)$ be the enveloping Lie algebra of the heisenberg algebra $\mathfrak h$. The algebra $\mathfrak h$ has a basis formeb by
$$X:=
\left(\begin{array}{ccc}
0 & 1 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{array}\right),\quad
Y:=
\left(\begin{array}{ccc}
0 & 0 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0
\end{array}\right)\quad
\text{ and }\quad Z:=
\left(\begin{array}{ccc}
0 & 0 & -1 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{array}\right).$$
Hence, we have a PBW basis for $U(\mathfrak h)$ given by
$$\{X^aY^bZ^c\colon a,b,c\geqslant 0\}.$$
The relations
$$[X,Y]=Z,\quad [X,Z]=0\quad\text{ and }\quad [Y,Z]=0$$
in $\mathfrak h$ provide the relations
$$YX=XY+Z,\quad ZX=XZ\quad\text{ and }\quad ZY=YZ.$$
Thus, $Z$ is in the center $\operatorname Z(U(\mathfrak h))$ of $U(\mathfrak h)$. We will show above that $Z(U(\mathfrak h))$ is the subalgebra of $U(\mathfrak h)$ generated by $Z$ (i.e. the polynomials in $Z$).
One can prove, by induction in $n\in\mathbb Z_+$, that
$$Y^nX=XY^n + nY^{n-1}Z$$
and
$$YX^n=X^nY + nX^{n-1}Z.$$
The cases where $n=1$ are just the relation $YX=XY+Z$ given above.
With the equations above, one can show that if
$$\alpha = \sum_{i=1}^m\lambda_{a_i,b_i,c_i}X^{a_i}Y^{b_i}Z^{c_i}$$
is not in the subalgebra generated by $Z$ then $\alpha$ is not in $Z(U(\mathfrak h))$ (more specifically, $\alpha$ will not commute with both $X$ and $Y$):

Suppose without generality that $(a_i,b_i)\neq (0,0)$ for each $i$.
Take
$$c=\operatorname{max}\{c_1,\dots,c_n\}.$$
If
$$a=\operatorname{max}\{a_i\colon c=c_i,\quad i=1,\dots,n\}>0$$
and $(a,b,c)=(a_i,b_i,c_i)$ then $\alpha$ does not commute with $Y$ because $Y\alpha$ will have a component in the vector $X^{a-1}Y^bZ^{c+1}$ of the PBW basis and $\alpha Y$ will not.
Similarly, if
$$b=\operatorname{max}\{b_i\colon c=c_i,\quad i=1,\dots,n\}>0$$
and $(a,b,c)=(a_i,b_i,c_i)$ then $\alpha$ does not commute with $X$ because $\alpha X$ will have a component in the vector $X^aY^{b-1}Z^{c+1}$ of the PBW basis and $X\alpha$ will not.

Therefore, $Z(U(\mathfrak h))$ must be the subalgebra generated by $Z$. Which is, by the way, the subalgebra of $U(\mathfrak g)$ generated by the center of $\mathfrak h$.
The case of the bi-dimensional non-abelian algebra $\mathfrak g$ can be attacked in a similar way. The center of $U(\mathfrak g)$ is the vectorial subspace generated by element $1$. Take a basis formed by $X$ and $Y\in\mathfrak g$ such that $[X,Y]=Y$ in $\mathfrak g$ and consider a PBW basis of $U(\mathfrak g)$ induced by $X$ and $Y$. Then prove that no element in $U(\mathfrak g)\backslash\mathbb K 1$ commute with both $X$ and $Y$.


TITLE: (Proof-verification) Geometric interpretation of homology
QUESTION [3 upvotes]: I want to verify the following claim:

Any singular $n-$boundary "encloses" a homotopy of singular $n-$simplices (for $n \ge 1$).

Specifically, let $p \in \Delta_n$ be given, i.e. $p=(p_0,p_1,\dots,p_n) \in \mathbb{R}^{n+1}$, $\sum_{k=0}^n p_k =1$.
Let $\phi: \Delta_{n+1} \to X$ be continuous (this is called a singular $(n+1)-$simplex).
As I argue below, I think the following assertion "proves" the above heuristic claim -- I am pretty sure that the correctness of the assertion follows immediately from the definitions, but I would like someone to double-check this, since I have not seen it written anywhere else before:

Assertion: Between the two singular $n-$simplices, $$(\partial_i\phi)(r_0, \dots, r_n) = \phi(r_0, \dots, r_{i-1},0,r_i, r_{i+1}, \dots, r_n), \\ (\partial_j\phi)(s_0, \dots, s_n)=\phi(s_0,\dots,s_{j-1},0,s_j,s_{j+1},\dots, s_n),$$ called the $i$th and $j$th faces of the singular $(n+1)-$simplex $\phi$, respectively, the following is a homotopy, i.e. a continuous function $H: \Delta_n \times[0,1] \to X$ such that for all $p \in \Delta_n$, $H(p,0)=(\partial_i \phi)(p)$ and $H(p,1)=(\partial_j \phi)(p)$: $$ H(p,\!t)\!=\!\begin{cases}  \phi(p_0,\!\dots\!, p_{i-1}, tp_i, (1\!-\!t)p_i + tp_{i+1},\!\dots\!, (1\!-\!t)p_{j-2}+tp_{j-1}, (1\!-\!t)p_{j-1}, p_j,\!\dots\!, p_n) & i < j \\ \phi(p_0,\!\dots\!, p_{j-1}, tp_j, (1\!-\!t)p_j + tp_{j+1},\!\dots\!, (1\!-\!t)p_{i-2}+tp_{i-1}, (1\!-\!t)p_{i-1}, p_i,\!\dots\!, p_n) & j<i \end{cases}$$ Additionally, it is also the case that $H(\Delta_n \times [0,1]) \subseteq \phi(\Delta_{n+1})$.

REPLY [1 votes]: Unnecessarily Verbose Background Information
Note: singular $n-$simplices are continuous maps $\sigma: \Delta_n \to X$, so given two singular $n-$simplices $\sigma_1, \sigma_2$, a homotopy between them is a continuous function $H: \Delta_n \times [0,1] \to X$ such that, for $p \in \Delta_n$, $H(p,0)=\sigma_1(p)$ and $H(p,1)=\sigma_2(p)$.
What I mean by the image of a singular $m-$chain $0\not=\mathfrak{s}\in C_m(X)$: for any singular $m-$chain $\mathfrak{s}\not=0$ we have a decomposition as follows: $$ \mathfrak{s} = a_1\mathfrak{s}_1 + \dots + a_{\ell}\mathfrak{s}_{\ell} $$ where all of the $a_i \not=0$ and all of the $\mathfrak{s}_i$ are singular $m-$simplices, continuous maps $\mathfrak{s}_i: \Delta_m \to X$. Then we define the image of $\mathfrak{s}$ to be $$\bigcup_{j=1}^{\ell} \mathfrak{s}_j(\Delta_m) \subseteq X$$ i.e. the image of the "sum" of generators is just their union, and non-zero multiplicity does not affect the set of points we determine to be their image. For the singular $m-$chain $0$ (the additive identity of the free abelian group $C_m(X)$), we declare its image to be the empty set $\emptyset$.
When I say that a singular $n-$boundary $\partial(c)$ encloses a homotopy $\tilde{\phi}$ singular $n-$simplices, I mean that the image of the homotopy $\tilde{\phi}(\Delta_n \times [0,1]) \subseteq X$ in X is a subset of the image of the singular $(n+1)-$chain $c$ as defined above.
Attempt: Define the $(n+1)$th boundary map $\partial: C_{n+1}(X) \to C_n(X)$ by $$\partial:= \sum_{i=0}^{n+1} (-1)^i \partial_i \quad \text{(with the $i$th face $\partial_i$ to be defined later).}$$ (This is the definition used in Vick's Homology Theory -- note that $C_{n+1}(X)$ is the group of singular $(n+1)-$chains, i.e. the free abelian group whose generators are singular $(n+1)-$simplices). Given any $n-$boundary, by definition it equals $\partial(c)$ for some $a_1 c_1 + \dots + a_kc_k \in C_{n+1}(X)$, where all of the $c_i$ are singular $(n+1)-$simplices. Since $\partial$ is a group homomorphism, we have that $$\partial(c)=\partial(a_1c_1 + \dots + a_k c_k)=a_1\partial(c_1) + \dots + a_k\partial(c_k), $$ so without loss of generality we consider only the case of $n-$boundaries of the form $\partial(\phi)$ for $\sigma$ a singular $(n+1)-$simplex, $\phi: \Delta_{n+1} \to X$ continuous.
Now we define the faces of $\phi$ for $0 \le i \le n$ by $$(\partial_i\phi)(s_0, \dots, s_n)=\phi(s_0, s_1, \dots, s_{i-1},0,s_i, \dots, s_n),$$ note that these are all singular $n-$simplices. Now for $i\not=j$ such that $(-1)^i=(-1)^j$ (which exists since $n+1 \ge 2$ by assumption and $0 \le i,j \le n+1$) we can define a homotopy between the singular $n-$simplices $(\partial_i \phi)$ and $(\partial_j \phi)$ as follows: $$ t\in[0,1], \quad \tilde{\phi}_{i \to j} =  \begin{cases} \phi(s_0, s_1, \dots, s_{i-1}, ts_j, s_i, s_{i+1}, \dots, s_{j-1}, (1-t)s_i, s_j, s_{j+1}, \dots, s_n) & i<j \\ \phi(s_0, s_1, \dots, s_{j-1}, (1-t) s_i, s_j, s_{j+1}, \dots, s_{i-1}, ts_j, s_i, s_{i+1}, \dots, s_n) & j <i \end{cases} $$ Letting $(-1)^i = \varepsilon = (-1)^j$, we have that $\varepsilon \tilde{\phi}_{i \to j}(0) = \varepsilon \phi_i$ with $\phi_i(\Delta_n) \subseteq \bigcup_{i=0}^{n+1} (\partial_i \phi)(\Delta_n)$ and $\varepsilon \tilde{\phi}_{i \to j}(1) = \varepsilon \phi_j$ with $\phi_j(\Delta_n) \subseteq \bigcup_{i=0}^{n+1} (\partial_i \phi)(\Delta_n)$, thus the singular $n-$boundary "encloses" a homotopy between the singular $n-$simplices $\varepsilon \phi_i$ and $\varepsilon \phi_j$. This completes the proof. $\square$
Now since I am not proving that coordinate restrictions of $\phi$ are again continuous functions into $X$, I am not sure if this proof is obviously incorrect or obviously correct -- either way I'm sure it is a dumb question. In any case, if anyone who is an expert in this area wouldn't mind giving this a quick glance-over and me a sanity check, I would be much obliged for their help.
Context/Motivation for Question: So far I have been trying to use the following heuristic interpretation of (singular) homology to motivate the definitions and computations:

Geometric holes are modeled topologically by the non-existence of continuous deformations.
The absence of geometric holes is modeled topologically by the existence of continuous deformations.

Specifically, for each dimension $n$ (and to motivate the definition of boundaries and why we factor them out from homology groups):

"$n-$dimensional holes" are modeled topologically by the non-existence of an enclosed homotopy between singular $n-$simplices.
The absence of "$n-$dimensional holes" (i.e. (generators of) $n-$boundaries) are modeled topologically by the existence of an enclosed homotopy of singular $n-$simplices.

If you have any comments about the sensibility/dangerousness of these statements, please let me know, although it is not the main thrust of my question.


TITLE: A geometry (circles and tangents) problem
QUESTION [2 upvotes]: In the following figure
There is a circle with centre at origin. D and E are two tangent points of the circle from point C. FGHI is a rectangle and it is given that DG=5 and GI=4. And I have to find the length of EH
I tried solving this question could not solve it. Is the question correct? If it is please provide the solution.

REPLY [4 votes]: Extend $HF$ to cut the circle second time at $J$. By the power of the point $H$ with respect to the circle we have $$HE^2 = HF\cdot HJ = HF\cdot (HF+2DG) =4\cdot 14 $$
so $$HE = 2\sqrt{14}$$