text:
\section{Pattern avoidance in Shi tableaux}
  \label{sec:avoid}

 Recall from  our definition in  Section \ref{sec:shi} that $T'$ occurs as a pattern in $T$  if $T'$ can be obtained   from $T$ after an iteration of  bounce deletions.
  Otherwise, we say that $T$ {\em avoids} $T'$.

We denote by $\av{}{T'}$ the subset of Shi tableaux   that avoid $T'$,
	and by $\av{n}{T'}$ the  subset of Shi tableaux in  $\shiT{n}$ that avoid $T'$. If
	$|\av{n}{T'}|=|\av{n}{T}|$ for all $n\in\mathbb N$,
	we say that $T$ and $T'$ are \emph{Wilf-equivalent}.
  A fundamental problem on patterns is related to Wilf-equivalence and more precisely to finding
  classes of Wilf equivalent objects.
  \medskip

We begin this  section with an analysis of small patterns.
More precisely, we present closed formulas for   $|\av{n}{T}|$, where
$T$ is any Shi tableau of size 2.  We continue with  analogous results for
certain tableau of size $k$, which can be considered as natural
generalizations of the ones of size 2.
 Finally, we compare
the results we obtain with known results in the theory of permutation-patterns.

\subsection{Shi tableaux of size 2}
There are five Shi tableaux of size two
\begin{align}
\label{size2}
\te{}=\U^3\D^3, \tg{}=\U^2\D\U\D^2, \tor{}=\U^2\D^2\U\D,
\tv{}=\U\D\U^2\D^2 \text{ and } \tf{}=(\U\D)^3,
\end{align}

which are divided into two Wilf-equivalence classes, as shown in the following proposition.

\begin{proposition}
  \label{prop:avtableaux2}
  For every $n\geq 2$ we have
  \begin{enumerate}[(i)]
    \item $|\av{n}{\te{}}|=|\av{n}{\tf{}}|=2^n$, and
    \item $|\av{n}{\tg{}}|=|\av{n}{\tor{}}|=|\av{n}{\tv{}}|=\binom{n+1}{2}+1$.
  \end{enumerate}
\end{proposition}
To prove Proposition \ref{prop:avtableaux2} we need the following lemma which
provides us with precise characterizations of pattern avoidance
for each of the five tableau of size 2.
\begin{lemma}
  \begin{enumerate}[(i)]
\item  $T\in\shiT{n}$ avoids
$\tf{}$ if and only if its bounce path $b(T)$
has at most two return points.
\item  $T\in\shiT{n}$ avoids  $\te{}$ if and only if its height is at most 2.
\item  $T\in\shiT{n}$ avoids $\tg{}$
if and only if it has at most one peak at height $\geq{2}$.
\item   $T\in\shiT{n}$ avoids $\tv{}$ if and only if
 is  $T=\U^{n+1}\D^{n+1}$ or   $T=\U^{r}\D\cdots\D(\U\D)^{n-r}$ with  $1\leq{r}\leq{n}$.
 Since $T\in \shiT{n}$, the subword between $\D\cdots\D$ is a permutation  of $r-1$ $\D$'s and a
single $\U$.
\item[(iv\,$'$)] $T\in\shiT{n}$ avoids $\tor{}$ if and only if
is  $T=\U^{n+1}\D^{n+1}$ or   $T=(\U\D)^{n-r}\U\cdots \U\D^r$ with  $1\leq{r}\leq{n}$.
 Since $T\in \shiT{n}$,
the subword between $\U\cdots\U$ is a permutation  of $r-1$ $\U$'s and a
single $\D$.
  \end{enumerate}
  \label{lem:avtableaux2}
\end{lemma}
\begin{proof}
  For (i), notice that if the bounce path of $T$
  has at most two return points, say $(k,k)$ with $1\leq{k}\leq{n+1}$ and
  $(n+1,n+1)$, then the columns $\col{k+1},\ldots,\col{n+1}$
  are empty (see Figure \ref{fig:avoid_full2}).  Thus,
  if we want to arrive   at the   pattern $\tf{}$  we have to delete $k-1$ among the $k$ first
  rows  of   $T$. This  eliminates $k-1$ among the first $k$ columns of
  $T$, resulting in a tableau with at most  one non-empty column which,
  clearly,  cannot
  contain  the pattern $\tf{}$.

  For the reverse, we leave  the reader to check that if $T$ has more than
  two return points,    there exists an iteration of  bounce  deletions which leads
  to   $\tf{}$.

 For (ii), it is immediate to see that $T$ has height  at most
2  if  all boxes, except possibly the last, in each row are full.
To prove the claim in (ii), notice that if  $T$ has height more than 2, then
  it has a row ending with at least two empty boxes, from which we can
  obtain the pattern   $\te{}$.

  Reversely, if no row has more than one empty
  boxes then  $T$ can be written as a concatenation of $\U\D$'s and $\U^2\D^2$'s, i.e.,
    $T=(\U\D)^{a_1}\U^2\D^2(\U\D)^{a_2}\U^2\D^2\cdots$.
    Given such a path,  each bounce  deletion
  either deletes a peak at height 1 or 2 (i.e.,  a consecutive  $\U\D$)
  or a valley at height 0 (i.e.,  a consecutive $\D\U$).
  In both cases the resulting path will again  be
  of a similar form, i.e., a concatenation of   $\U\D$'s
  and $\U^2\D^2$'s.    Thus, it will never contain the pattern  $\te{}=\U^3\D^3$.

  For (iii) notice that if
   $T$ has at most one peak at height $\geq{2}$, then
   it can be written as   $T=(\U\D)^{a_1}\U^{a_2}\D^{a_2}(\U\D)^{a_3}$
   with $a_1+a_2+a_3=n+1$ (see Figure \ref{fig:avoidtg}(a)).
   Arguing as in (ii), iteration of any bounce deletions  leads to
   a   tableau of a similar   form, i.e.,
   $(\U\D)^{a'_1}\U^{a'_2}\D^{a'_2}(\U\D)^{a'_3}$
   with $a'_i\leq{a_i}$.
   This implies that we can never obtain the pattern $\tg{}=\U^2\D\U\D^2$.
   For the reverse, we leave  the reader to check that if $T$ has more
   than    one peaks at height $\geq{2}$, then $T$ contains the pattern $\tg{}$.

The claim in (iv) is obvious for $T=\U^{n+1}\D^{n+1}$.
 We next show that if
$T=\U^{r}\D\cdots\D(\U\D)^{n-r}$ as described in the statement
then it avoids the pattern $\tv{}=\U\D\U^2\D^2$ (see Figure~\ref{sfig:avoidtvk}(a)).
Indeed, in order to obtain the  pattern $\U\D\U^2\D^2$
we have to delete at least $r-1$ among the first $r$ $\U$-steps.    This
deletes  at least $r-1$ among the first $r$ columns of $T$,
resulting to one of the following tableaux:
$\U^2\D^2(\U\D)^{n-r}$,
$\U\D\U\D(\U\D)^{n-r}$ or $\U\D(\U\D)^{n-r}$, none of which  contains the pattern $\tv{}=\U\D\U^2\D^2$.
For the reverse,  we leave the reader to check that if there exists  $r+2\leq{i}\leq n+1$ such that
the $i$-th row has an empty box, then  there is a sequence  of bounce deletions leading to $\U\D\U^2\D^2$.

The statement in  (iv\,$'$) is completely analogous by symmetry.
\end{proof}
\begin{proof}[Proof of Proposition \ref{prop:avtableaux2}]
  For (i) we need to enumerate the tableaux  described in
   Lemma \ref{lem:avtableaux2}(i),(ii).

  We first  count the tableaux having at most two return points.
  Since the second return point is always the endpoint $(n+1,n+1)$,
  let us assume that the first return point of the bounce path is $(k,k)$
  with $1\leq{k\leq{n+1}}$.
   To count the  tableau whose bounce path has first return point $(k,k)$
      it suffices to count the  paths within the rectangle defined by
  $(1,k),(k,k),(k,n),(1,n)$ (see Figure~\ref{fig:avoid_full2}a).
  The latter are   $\binom{n}{k-1}$, from which we deduce that
  $|\av{n}{\tf{}}|=\sum_{k=1}^{n+1}\binom{n}{k-1}=2^n$.
Next, notice that the tableaux with height at most   2 are just
  those all whose boxes are full,  except possibly the last box of each row.
  This immediately implies that $|\av{n}{\tf{}}|=2^n$.

\input{fig_avoid_full2}

For (ii), we need to enumerate the tableaux  described in
Lemma \ref{lem:avtableaux2}(iii),(iv).
Recall from the proof of Lemma \ref{lem:avtableaux2}(iii) that
if a tableau $T$ has at most one peak at height $\geq{2}$, then
  it can be written as   $T=(\U\D)^{a_1}\U^{a_2}\D^{a_2}(\U\D)^{a_3}$
  with $a_1+a_2+a_3=n+1$ and $a_2\geq{2}$ (see Figure \ref{fig:avoidtg}(a)).
  Thus, we have  to count the  non-negative integer solutions of
  $a_1+a_2+a_3=n+1$ with $a_2\geq{2}$. These are $\binom{n+1}{2}$. Including also the tableau $\tf{n}$,
  all   whose   peaks are at height 1, we  conclude that
  $|\av{n}{\tg{}}|=\binom{n+1}{2}+1$.

  Finally,  in view of the characterisation in Lemma \ref{lem:avtableaux2}(iv),
    for each $1\leq{r}\leq n$   we  count the words
  with $r-1$ $\D$'s and a single $\U$.
  Including  $T=\te{n}$, we have  that $|\av{n}{\tv{}}|=1+\sum_{r=1}^n r=1+\binom{n+1}{2}$.
  \end{proof}
\medspace

\input{fig_avoid_g}
\input{fig_avoid_tg}

\subsection{Generalizations}

  In this subsection  we generalize  the  five cases in \eqref{size2} to  the following Shi
tableaux of size $k\geq{3}$:
\begin{align}
\label{sizek}
\te{k}=\U^{k+1}\D^{k+1},\, \tg{k}=\U^k\D\U\D^k,\, \tor{k}=\U^k\D^k\U\D, \,
\tv{k}=\U\D\U^k\D^k \text{ and }\, \tf{k}=(\U\D)^{k+1}.
\end{align}
It turns out  that for  fixed $k\geq 3$  the tableaux in \eqref{sizek}
fall into two Wilf-equivalence classes.

\begin{proposition}
  \label{prop:avtableauxk}
  For every $3\leq k\leq n$ we have
  \begin{enumerate}[(i)]

    \item $|\av{n}{\te{k}}|=|\av{n}{\tf{k}}|=|\av{n}{\tg{k}}|=|\tnk{n+1}{k}|$,

    \item $|\av{n}{\tv{k}}|=|\av{n}{\tor{k}}|=
\sum\limits_{\ell=0}^{k-1}\frac{n-\ell+1}{n+1}\binom{n+\ell}{\ell}+|\mathcal{F}(n,n,k-1)|+
\sum\limits_{\ell=k}^{n-1}\sum\limits_{h=0}^{k-1}\binom{n-\ell+h-1}{h}|\mathcal{F}(\ell-h,\ell,k-1)|,$
        \end{enumerate}
              \medskip
         where $|\tnk{n}{k}|$ is the number  of Dyck paths in $\dP{n}$ with
         height at most $k$ and  $|\mathcal{F}(m,n,k)|$  is the number of lattice
         paths  { from $(0,0)$ to
         	$(n,m)$ with steps $(1,0)$ and $(0,1)$ such that all points $(x,y)$
         	visited by the path satisfy $x\leq y\leq x+ k$.}
\end{proposition}

\begin{remark}
  The numbers $|\mathcal{F}(m,n,k)|$ can be computed efficiently using the
  following formula,
  which is a consequence of the iterated reflection principle \cite[Chap.~1.3, Thm.~2]{Mohanty}.

  $$ |{\mathcal F}(m,n,k)|
=\sum_{i=0}^{\infty}\tfrac{n-m+2i(k+2)+1}{n+i(k+2)+1}\tbinom{m+n}{m-i(k+2)}
+\sum_{i=1}^{\infty}\tfrac{n-m-2i(k+2)+1}{m+i(k+2)}\tbinom{m+n}{m+i(k+2)}.$$

\end{remark}
To prove  Proposition~\ref{prop:avtableauxk}  we need the following lemma.
\begin{lemma}
  \label{lem:avk}
  Let $k\geq 3$ and $T\in \shiT{n}$. Then
  \begin{enumerate}[(i)]
    \item $T$  avoids   $\tf{k}$ if and only if  its bounce path
    has at most $k$ return points,
    \item $T$  avoids $\te{k}$ if and only if its height is at most  $k$,
    \item $T$ avoids $\tg{k}$ if and only if it has no valley at
    height     $\geq{k-1}$.
 \item   Let  $\ell$ denote the number of the
    non-empty rows of $T$.
    Then $T\in\av{n}{\tv{k}}$ if and only if the tableau $T'\in\shiT{\ell-1}$
    obtained    by deleting the first $n+1-\ell$ columns of $T$ avoids $\te{k-1}.$

  \end{enumerate}
\end{lemma}
\newcommand{\wud}{w_{\scalebox{0.6}{\U\D}}}
\newcommand{\wdu}{w_{\scalebox{0.6}{\D\U}}}
\begin{proof}
  To prove (i) we use induction on $k$, the base case $k=2$ being Lemma
  \ref{lem:avtableaux2}(i).

  Thus assume that the claim holds for $k$ and consider the case $k+1$.
  Suppose on the contrary that there exists some $T\in\shiT{n}$
  containing $\tf{k+1}$ and  whose bounce path  has  $k+1$  return points.
  Then $n>k+1$ and there there exist a non-empty sequence $\de{i_1}{*},\ldots,\de{i_\ell}{*}$ of bounce deletions such that $\de{i_1}{*}\cdots \de{i_\ell}{*}(T)=\tf{k+1}$.
  Applying one more bounce deletion we have $\de{i_0}{*}\, \de{i_1}{*}\cdots
  \de{i_\ell}{*}(T)=\tf{k}$.
  In particular the tableau $\de{i_\ell}{*}(T)$ contains $\tf{k}$.
  However, the deletion $\de{i_\ell}{*}$ can only possibly reduce the number of return points of the bounce path by one.
  Thus the bounce path of $\de{i_\ell}{*}(T)$ has at least $k$
  return points and, by the induction hypothesis, $\de{i_\ell}{*}(T)$
  avoids $\tf{k}$.
  This is a contradiction.

  For the other direction, we show that any $T$ whose bounce path has at least $k+1$
  return points must contain $\tf{k}$.
  Indeed, this can be done by  applying $\de{i}{i}$
  on each row $i>0$ that does not contain a bounce step (see Figure \ref{fig:avoid_full2}b).

  For (ii), we use the fact that  $T$ has height at most $k$ if and only if
  no row has more than $k-1$ empty boxes. In view of this, it is immediate to see that if a row of $T$ has more than $k-1$ empty boxes, then
  $T$ contains $\te{k}$.
  { Reversely,  if all rows of $T$ have at most $k-2$ empty boxes,
then   no iteration of bounce  deletions can  lead  to a tableau having a row with
$k$ or more  empty boxes, and thus to $\te{k}$. }

   To prove (iii), we use the fact that  $T$ has no valley at
    height $\geq{k-1}$
    if and only if    each initial subword  of the form $w\U\D$
 satisfies    $\#\U(w\D\U)-\#\D(w\D\U)\leq{k}$. Next, notice that each bounce deletion
 either deletes a $\U,\D$  or a single $\U$(the corresponding $\D$ being on a subsequent position) from each such initial subword $w\D\U$. Thus, the above inequality   still holds after any bounce deletion, which futher implies that
 $T$ cannot contain the pattern $\tg{k}$. Reversely, if $T$ has a valley at height $\geq{k-1}$
then, deleting all rows and columns above and to the left of this valley we get a tableau  $\tg{\kappa}$ with $\kappa\geq{k}$ which, clearly,  contains $\tg{k}$.

  Finally,  notice that (iv) is trivially true for $\ell<k$
since  both assumptions that  $T$ avoids ${\tv{k}}$ and $T'$ avoids ${\te{k-1}}$ are satisfied (by size restrictions).
If $\ell\geq{k}$,  assume first that $T'$ contains $\te{k-1}$.
Then, it is easy to see that there exist bounce deletions on $T$ leading to a Shi tableau $T''$ which is $T'$ with a full column adjoint on its left.
Since $T'$ contains $\te{k-1}$ we conclude that $T''$ contains $\tv{k}$ and consequently that $T$ contains $\tv{k}$.

Next, assume that  $\ell\geq{k}$  and $T'$ avoids $\te{k-1}$.
 In order to answer the existence (or not) of the pattern  $\tv{k}=\U\D\U^k\D^k$
 in $T$ and since $T$ begins with $\U^{n-\ell+1}\D$, we have to delete $n-\ell$ among the first $n-\ell+1$  $\U$-steps of $T$
 in a way that the resulting tableaux $T''$ has a full first column,\,i.e., begins with
 $\U\D$.
  This will delete $n-\ell$ among the first $n-\ell+1$ columns of $T$ so that
   $T''$   is $T'$ with a full column adjoint on its left.
 Then, it is clear that since the pattern $\te{k-1}$ does not occur in $T'$,
 the pattern $\tv{k}=\U\D\U^k\D^k$ does not occur in
  $T''$ and hence in $T$.

\end{proof}

Now we are ready to prove Proposition~\ref{prop:avtableauxk}
\begin{proof}[Proof of Proposition~\ref{prop:avtableauxk}]
  (i) The fact that $\tf{k},\te{k}$ are Wilf-equivalent
  is a consequence of the well-known  {\em zeta map}
  \cite{akop-adnil-02,hag-dh-08}.
  Consider a Dyck path $\pa\in\Dp{n+1}$ with area vector
  $a(\pa)=(a_1,a_2,\ldots,a_{n+1})$.
  That is, $a_i$ denotes the number of empty boxes in row $i$ of the corresponding Shi tableau.
  For each $j=0,\ldots,n$ we define $w_j$ as a word in the
  alphabet $\{\U,\D\}$ obtained as follows: reading $a(\pa)$ from left to right,
  we draw a down-step whenever we encounter an entry $a_i=j-1$
  and a up-step whenever we encounter an entry $a_i=j$.
  Finally, we set $\zeta(\pa)=w_0w_1\cdots{w}_n$.
  It is easy to see that $\zeta(\pa)\in\dP{n+1}$ since every entry of
  $a(\pa)$ contributes twice: an up-step first and a down-step later.

  The map $\zeta:\dP{n+1}\rightarrow\dP{n+1}$ is a bijection with surprising
  properties.

  The following are equivalent:
\begin{enumerate}[(a)]
  \item The area vector $a(\pa)$ satisfies $a_i\leq{k-1}$ for all $i$.
  \item The word $w_j$ is empty for all $j>k$.
  \item The bounce path of $\zeta(\pa)$ has at most $k$ return points.
 \end{enumerate}

  Notice that a Dyck path has height at most $k$
  if and only if all entries of its area vector are less than $k$.
  The equality $|\av{n}{\te{k}}|=|\av{n}{\tf{k}}|=|\tnk{n+1}{k}|$ therefore
  follows from the characterization of the Shi tableaux in $\av{n}{\te{k}}$
  and $\av{n}{\tf{k}}$ in Lemma~\ref{lem:avk}~(i) and~(ii) and
  the equivalence of (a) and (c) above.

  It remains to prove that $|\av{n}{\tg{k}}|=|\tnk{n+1}{k}|$.
  In view of Lemma~\ref{lem:avk}~(iii) suppose that $\pa$ is a Dyck path
  with no valleys at height greater or equal to $k-1$. Then the steps of $\pa$ above the line
  $y=x+k-1$   form a (possibly empty) set of disconnected peaks.

  Replacing each such peak of the form $\U^\ell \D^\ell$ by a sequence
 $(\U\D)^\ell$ we obtain a Dyck path of height at most $k$.

  This yields a bijection between $\tg{k}$-avoiding and $\te{k}$-avoiding
  Shi tableaux.

To prove (ii), let $T\in\av{n}{\tv{k}}$ with $\ell$ non-empty rows.
By Lemma~\ref{lem:avk}~(iv) the tableau $T$ falls in one of three categories:
(a) $\ell<k$, (b) $\ell=n$ and the tableau $T'\in\shiT{n-1}$ obtained by deleting the
first column of $T$ avoids $\te{k-1}$, or (c) $k\leq \ell<n$ and the tableau
$T'\in\shiT{\ell-1}$ obtained by deleting the first $n+1-\ell$ columns of $T$ avoids
$\te{k-1}$.

The set of Shi tableaux that satisfy $\ell<k$ corresponds naturally
 to ballot paths with $n$ $\U$-steps and $\ell$ $\D$-steps, that is,
 lattice paths  from $(0,0)$ to
 	$(\ell,n)$ with steps $(1,0)$ and $(0,1)$ that never go below the line $x=y$.
 Such ballot paths are known to be counted by $\frac{n-\ell+1}{n+1}\binom{n+\ell}{\ell}$.
The second category contains $|\tnk{n}{k-1}|=|{\mathcal F}(n,n,k-1)|$ elements by
part (i) of the proposition.
It remains to count the tableaux that fall into the third category.
To this end write $T=\U^{n+1-\ell}\D \pa \D \pa'$, where $\pa$ contains $n-\ell-1$
$\D$-steps, and let $h$ denote the number of $\U$-steps of $\pa$.
Thus the tableau $T'$ corresponds to the path $\U^h\pa'$.
In order for $T'$ to avoid $\te{k-1}$ we must have $h\leq k-1$ and $\pa'$ must correspond to a ballot path from $(0,0)$ to $(\ell-h,\ell)$ of height at most $k-1$.
There are $|\mathcal F(\ell-h,\ell,k-1)|$ such ballot paths.
The fact that $T'$ avoids $\te{k-1}$ imposes no restriction on the path $\pa$.
Thus there are $\binom{n-\ell+h-1}{h}$ possible choices for $\pa$.

\end{proof}

\begin{remark}
  The zeta map and the bounce path of a Dyck path were first defined by Andrews
  et al.~in \cite{akop-adnil-02} in order to enumerate $ad$-nilpotent ideals in
  a borel subalgebra of the complex simple Lie algebra of type $A$ with class
  of nilpotence less than $k$.
  These ideals are in bijection with certain Dyck paths
  (\cite[Thm.~4.1]{akop-adnil-02}), which correspond precisely to the Shi
  tableaux that avoid $\tf{k}$.
  The zeta map provides a bijection to Dyck paths of height at most $k$ (see
  \cite[\textsection5]{akop-adnil-02}), which of course coincide with
  $\te{k}$-avoiding tableaux.
  Thus our use of the zeta map in the proof of \ref{prop:avtableauxk}~(i)
  really agrees with its original purpose.
  The combinatorial description of $ad$-nilpotent ideals with bounded class of nilpotence in terms of pattern avoidance is, in the opinion of the authors, quite intriguing.

  We further remark that the zeta map also ties to different problems in
  algebraic combinatorics such as the Hilbert series of diagonal
  harmonics~\cite{hag-ha-13,hag-dh-08}.
  The zeta map and the bounce path have also previously been considered in
  conjuction with the Shi arrangement, for example, in \cite{arm-hadh-02}.
\end{remark}

config: arxiv


TITLE: Unit conversion multiplication
QUESTION [1 upvotes]: This is going to sound like a really dumb question. At first I thought it was just my brain failing to function, but I can't work my mind around it.
I'm using a problem to demonstrate the conceptual issue, but what I care about is why things work however they may.
Let's say we have a rectangle $5~\text{cm} \times 10~\text{cm}$. What is the area in meters?
If we say it is an area of $50~\text{cm}$, our answer should be $.05~\text{m}^2$.
On the other hand, if we were to convert to meters first, $.05~\text{m} \cdot .1~\text{m} =.005~\text{m}^2$.

REPLY [0 votes]: There are $100~\text{cm}$ in a meter.  A square meter is the area of a square with side length $1~\text{m} = 100~\text{cm}$.  Hence,
$$1~\text{m}^2 = (1~\text{m})(1~\text{m}) = (100~\text{cm})(100~\text{cm}) = 10000~\text{cm}^2$$
Thus, to convert an area given in $\text{cm}^2$ to an area given in $\text{m}^2$, we must multiply by the conversion factor
$$\frac{1~\text{m}^2}{10000~\text{cm}^2}$$
Hence, in your example, the area in square meters of a rectangle with area $50~\text{cm}^2$ is
$$50~\text{cm}^2 \cdot \frac{1~\text{m}^2}{10000~\text{cm}^2} = 0.005~\text{m}^2$$


TITLE: Is total boundedness implying boundedness by topological vector space's definition in Rudin?
QUESTION [0 upvotes]: Rudin defined total boundedness of a set in a TVS(topological vector space) as "for every neighborhood $V$ of zero in TVS $X$, there is a finite set $F$ such that $E$ is contained in $F+V$". However a set $E$ bounded in $X$ means that for any neighborhood $V$ of zero for any $t>0$ sufficiently large, $E$ is contained in $tV$. From the names it seems total boundedness should imply boundedness. This is obviously true if there is a local convex base for $X$. Is it true for any TVS?

REPLY [1 votes]: Yes, of course. Given a $0$-neighborhood $V$ there is (by continuity of multiplication with scalars and addition) another $0$-neighborhood $W$ such that $W+tW\subseteq V$ for all $|t|\le 1$. Applying total boundedness to $W$ yields a finite set $F$ with $B\subseteq F+W$ and since $W$ is absorbing and $F$ finite there is $0<|t|\le 1$ with $tF \subseteq W$. This gives
$$ tB \subseteq tF+tW\subseteq W+tW \subseteq U.$$
Hence $B\subseteq \frac 1t U$.


TITLE: Determinant of symmetrical factorized matrix
QUESTION [4 upvotes]: Given $A, B \in \mathbb{R}^{n\times n}, t \in \mathbb{R}\setminus \{0\}$ with $b_{ij} = t^{i-j}\cdot a_{ij}$. Prove $\det(A) = \det(B)$.
I first thought of induction. I can easily prove this for $n \le 2$.
My induction hypothesis: $\det(A) = \det(B)$ with $A, B \in \mathbb{R}^{n\times n}$
Induction step: $\det(B) = \sum_{i=1}^{n+1} b_{ij} \cdot (-1)^{i+j} \cdot \det(B_{ij})\overset{IH}{=} \sum_{i=1}^{n+1} t^{i-j} a_{ij} \cdot (-1)^{i+j} \cdot \det(A_{ij})$
So far, so good, but I can't seem to get rid of the exponentiation of $t$. Any thoughts?

REPLY [3 votes]: Let
$$
T=\begin{bmatrix}t \\ & t^2\\ & & \ddots\\ & & & t^n\end{bmatrix}
$$
(and zeroes off-diagonal).
Then
$$
B=TAT^{-1},
$$
so $\det B=\det T\; \det A\;(\det T)^{-1}=\det A$.


TITLE: $V = W \cap W^{-1}$ a symmetric neighborhood such that $V\cdot V \subset U$.
QUESTION [1 upvotes]: This is an answer from another question.

Use that the multiplication is continuous and $1\cdot 1=1$. Let $U$ be
  a neighborhood of $1$. By continuity there are neighborhoods $A,B \ni 1$ such that $AB \subset U$. Let $W= A \cap B$ and then $V:= W \cap W^{-1}$ is a symmetric neighborhood of $1$ such that $V \cdot V \subset U$.

How is $V\cdot V \subset U$?

REPLY [2 votes]: You have that $W\subseteq A\cap B$ and $A\cdot B \subseteq U$. Hence, $W\cdot W \subseteq A\cdot B \subseteq U$.
Moreover $V\subseteq W$ so $V\cdot V\subseteq W\cdot W \subseteq U$.


TITLE: Does every group have a representation?
QUESTION [1 upvotes]: For any set $A$, we can give it an group structure and make it a free group. For example:
$$\mathbb Z=<a;aa^{-1}=1>$$
Further more, we can introduce some relation on it:
$$\mathbb Z_2=<a;a^2=1>$$
 $$\mathbb Z_2\times{\mathbb Z_3}=<a,b;a^2=b^3=1,ab=ba>$$
So if a group can be represented by the form:
$$<a_1,a_2...;r_1,r_2...>$$
then we call that it has a representation.

Question: Does every group have a representation?

Below is my attempt:

Let $G$ be a group. If we remove the group structure of $G$, then we can give it a trivial free relation: $G^{*}=<g;gg^{-1}=1>$.
   Then we consider the map
   $$\sigma:G^{*}\rightarrow{G}$$
   $$g_1^{\varepsilon_1}...g_n^{\varepsilon_n}\mapsto{g_1^{\varepsilon_1}...g_n^{\varepsilon_n}}$$

So now I'm confused. Is the map well-defined? And what should I do next step?

REPLY [3 votes]: Yes, let $X:=\{x_g\}_{g\in G}$ be the set of variables and take relations
$x_gx_h=x_u$ whenever $gh=u$.
If you wish to generate it as semigroup you indeed need the extra symbols $x_g^{-1}$ and relations $x_gx_g^{-1}=1$.


text:
\subsection{Indecomposable Cut Sets}
In this section we will assume that the decomposition space has no cut
pairs.

Our ultimate goal is to construct a cubing quasi-isometric to
a bounded valence tree.
For this purpose, we will need to choose a collection of cut sets in a
such a way that there is a bound on the number of cut sets in the
collection that cross any fixed cut set in the collection.

Cut sets with disjoint pruned cores do not cross, so we could control
crossings if we could control the diameters of the pruned cores of the
cut sets in some collection.

The following example shows that cut sets of a fixed size can have
pruned cores with arbitrarily large diameter.
We subsequently introduce
the property of \emph{indecomposability} to rule out this kind of bad behavior.

Let $\lines$ be the line pattern in $F=\left<a,b\right>$ generated by
the words $ab\bar{a}\bar{b}$, $a$ and $b$.
The edge cut sets have size three. It can be shown that these are the
only cut sets of size three and there are none smaller, see \fullref{example:complete}.
It is also possible to find minimal cut sets of size four.
Pick any two of the edge cut sets that share a line. The four lines of
the symmetric difference are a minimal cut set.
\fullref{fig:indecomposable} shows the line pattern. The two dashed
lines indicate edge cut sets of size three. The four thickened lines
make up the cut set of size four that is the symmetric difference.
 There is no bound on
the size of the pruned core of such a cut set, nor on the number of
such cut sets that cross each other.

\begin{figure}[h]
  \centering
  \includegraphics[width=\textwidth]{Pictures/complete}
  \caption{A problematic minimal cut set}
  \label{fig:indecomposable}
\end{figure}

We say that a minimal finite cut set $S\subset\decomp$ is \emph{decomposable} if there are
minimal cut sets $Q$ and $R$ such that:
\begin{enumerate}
\item $Q$ and $R$ are non-crossing,
\item $|Q|<|S|$ and $|R|<|S|$,
\item $S=Q\Delta R=(Q\setminus R)\cup (R\setminus Q)$
\end{enumerate}

A minimal finite cut set $S$ is \emph{indecomposable} if it is not decomposable.

The smallest cut sets in $\decomp$ are indecomposable since there are no smaller cut sets to decompose them into.

\begin{lemma}\label{proposition:decomposable}
  Suppose $S$ is a finite minimal cut set and the pruned core $\pcore$ of $\tilde{S}$ has an interior vertex $v$ such that $\Wh(v)\setminus \pcore$ has exactly two components, one of which is a free edge, and no lines of $\tilde{S}$ go through $v$. Then $S$ is decomposable.
\end{lemma}
\begin{proof}

  \begin{figure}[h]
\labellist \small
\pinlabel $l$ [t] at 46 17
\pinlabel $v$ [br] at 56 22
\pinlabel $Q$ [b] at 5 18
\pinlabel $R$ [b] at 110 18
\pinlabel $\X_1$ at 16 33
\pinlabel $\X_0$ at 16 7
\pinlabel $\Y_0$ at 99 7
\pinlabel $\Y_1$ at 99 33
\endlabellist
    \centering
    \includegraphics[width=.7\textwidth]{Pictures/decomposable}
    \caption{Schematic diagram of decomposable cut set}
    \label{fig:decomposable}
  \end{figure}

Let $l$ be the line of $\lines$ corresponding to the free edge in $\Wh(v)\setminus \pcore$.
Let $\tilde{Q}$ be $l$ and the lines of $\tilde{S}$ on one side of $\pcore\setminus\{v\}$, and let $\tilde{R}$ be $l$ and the lines of $\tilde{S}$ on the other side of $\pcore\setminus\{v\}$.

Then $Q\cap R=q_*(l)$, and $S=Q\Delta R$.

Let $A^0$ and $A^1$ be the components of $\decomp\setminus S$.
The line $l$ does not belong to $\tilde{S}$, so we may assume that
$q_*(l)\in A^0$.
Let $\X$ and $\Y$ be the two components of $\pcore\setminus\{v\}$.
We may assume $Q$ is on the $\X$ side.

Let $\X_0$ be the portion $\X$ corresponding to $A^0$, and define
$\X_1$, $\Y_0$ and $\Y_1$ analogously, see \fullref{fig:decomposable}.
The edge of $\Wh(\pcore)\setminus\tilde{S}$ corresponding to $l$ is the only connection between $\X_0$ and $\Y_0$, so $\tilde{Q}$ separates $\X_0$ from $\X_1\cup \Y_0\cup \Y_1$.

Thus, $Q$ is a cut set. Moreover, $Q$ is a minimal cut set since every edge corresponding to a
line in $\tilde{Q}$ has one end in $\X_0$ and one end in $\X_1\cup
\Y_0\cup \Y_1$.

By a similar argument, $R$ is a minimal cut set.

$Q$ and $R$ are non-crossing because the only line of $R$ that has an
endpoint in $\X_0$ is $l=\tilde{Q}\cap\tilde{R}$.

Finally, as there are no cut pairs, we have:
\[3\leq |Q|=|Q\setminus R|+|Q\cap R|=|Q\setminus R|+1\implies |Q\setminus R|\geq2\]
Thus:
\[|S|=|Q\setminus R|+|R\setminus Q|>1+|R\setminus Q|=|R\cap Q|+|R\setminus Q|=|R|\]
Similarly, $|Q|<|S|$.

\end{proof}

\begin{theorem}[Edge cut sets are indecomposable]\label{theorem:indecomposableedges}
Suppose we have chosen a free basis of $F$ such that $\Wh(*)$ is minimal complexity. Then edge cut sets are indecomposable.
\end{theorem}
\begin{proof}
Let $e$ be an edge of $\tree$. Let
$\tilde{S}$ be the lines of $\lines$ that cross $e$. Let $S=q_*(\tilde{S})$.

$S$ is minimal by \fullref{proposition:edgeset}.
Suppose $S$ decomposes into $Q$ and $R$.
We must have $Q\cap R\neq \emptyset$, otherwise $Q$ and $R$ are proper subsets of
$S$ that are cut sets, contradicting minimality of $S$.
Since $Q$ and $R$ do not cross and $S\setminus R=Q\setminus R$, $S$ does
not cross $R$.
Thus, since they are minimal, $R$ does not cross $S$.
Therefore, $R\setminus S=R\cap Q$ is contained in one component of
$\decomp\setminus S$.
This means that $q_*^{-1}(Q\cap R)=\tilde{Q}\cap\tilde{R}$ is contained in one component of $\tree\setminus e$.

Let $*$ be the vertex of $\tree$ incident to $e$ on the $\tilde{Q}\cap \tilde{R}$ side.

It is possible that pruning the cores of $\tilde{Q}$ or $\tilde{R}$ would remove $*$. Let the
\emph{partially pruned core} of $\tilde{Q}$, $\ppcore_{\tilde{Q}}$, be the result of pruning the
core of $\tilde{Q}$ as much as possible without pruning off $*$.
Note $\ppcore_{\tilde{Q}}=\ppcore_{\tilde{R}}$, so we may just call it $\ppcore$.

\[|R\setminus Q|+|Q\cap R|=|R| < |S|=|Q\setminus R|+|R\setminus Q|\]

So $|Q\cap R|<|Q\setminus R|$. Similarly, $|Q\cap R|<|R\setminus Q|$.

There are two connected components of $\Wh(\ppcore)\setminus\tilde{Q}$,
call them component 0 and component 1.
Since $Q$ and $S$ do not cross, everything on the side of $e$ opposite $\tilde{Q}\cap \tilde{R}$
belongs to a single component.

First suppose $\ppcore=*$.
Suppose the edge $e$ oriented away from $*$ has label
$x\in\mathcal{B}\cup\bar{\mathcal{B}}$; suppose the corresponding
vertex in $\Wh(\ppcore)\setminus\tilde{Q}$ is in component 1.
Suppose the vertex
corresponding to the edge labeled $\bar{x}$ is in component 0.
Then the Whitehead automorphism that pushes the vertices in $\Wh(*)$ in
component 1 through $x$ changes the valence at $x$ from
$|S|=|Q\setminus R|+|R\setminus Q|$ to
$|Q\cap R|+|R\setminus Q|$.
Since $|Q\cap R|<|Q\setminus R|$ this contradicts the assumption that
the Whitehead graph had minimal complexity.

Conversely, if the vertex $\bar{x}$ is in component 1 push
\[Z=\{x\}\cup\{\text{vertices of component } 0\}\] through $x$ and get a contradiction.

Now suppose $\ppcore$ is not just $*$. Then there is some leaf $v\neq *$.
Suppose the stem of $v$ (oriented away from the leaf) has label $x\in\mathcal{B}\cup\bar{\mathcal{B}}$, and suppose the
vertex in $\Wh(\ppcore)\setminus\tilde{Q}$ corresponding to $\bar{x}$ is in component 1.

\fullref{fig:ppcore} shows a schematic diagram of $\Wh(\ppcore)$.

The labeling in the diagram is as follows:
\begin{itemize}
\item $\X_0$ = the portion of component 0 on the $v$ side of
 the stem.
\item $\X_1$ = the portion of component 1 on the $v$ side of
 the stem.
\item $\Y_0$ = the portion of component 0 between the stem of
 $v$ and $e$.
\item $\Y_1$ = the portion of component 1 between the stem of
 $v$ and $e$.
\item $\mathcal{Z}$ = everything on the side of $e$ opposite $\tilde{Q}\cap\tilde{R}$.
\item lowercase letters represent the number of lines with endpoints
  in the specified regions with:
  \begin{itemize}
  \item $a$, $b$, $c$ and $h$ counting the lines of
    $\tilde{Q}\cap\tilde{R}$
\item $d$ and $i$ counting the lines of $\tilde{Q}\setminus\tilde{R}$
\item $e$ and $j$ counting the lines of $\tilde{R}\setminus\tilde{Q}$
\item $f$ and $g$ counting the lines not in $\tilde{Q}\cup\tilde{R}$
  crossing the stem.
  \end{itemize}
\end{itemize}

\begin{figure}[h]
\labellist \small
\pinlabel $v$ [r] at 33 36
\pinlabel $a$ [l] at 13 36
\pinlabel $b$ [tr] at 28 53
\pinlabel $c$ [br] at 28 19
\pinlabel $d$ [tr] at 39 55
\pinlabel $e$ [br] at 39 16
\pinlabel $f$ [bl] at 48 60
\pinlabel $g$ [tl] at 48 12
\pinlabel $h$ [r] at 114 33.5
\pinlabel $i$ [b] at 183 57
\pinlabel $j$ [t] at 183 16
\pinlabel $\X_0$ at 22 64
\pinlabel $\X_1$ at 22 9
\pinlabel $\Y_0$ at 115 64
\pinlabel $\Y_1$ at 115 9
\pinlabel $\mathcal{Z}$ at 205 37
\pinlabel $Q$ [b] at 170 65
\pinlabel $R$ [t] at 170 9
\pinlabel $S$ [b] at 176 66
\endlabellist
  \centering
  \includegraphics[width=\textwidth]{Pictures/whschematic}
  \caption{Schematic diagram for $\Wh(\ppcore)$}
\label{fig:ppcore}
\end{figure}

Since $v\neq *$ is a leaf of $\ppcore$ we must have $a>0$ and
$\X_0$ and $\X_1$ nonempty.

Minimality of $Q$ implies that $\Wh(\ppcore)\setminus\tilde{Q}$ has
exactly two connected components. In the diagram they are
$\X_0\cup\Y_0$ and
$\X_1\cup\Y_1\cup\mathcal{Z}$.

$\X_0\cup\Y_0$ must belong to a connected component,
so $\Y_0=\emptyset$ if and only if $f=0$.
$\Y_0=\emptyset$ also implies $c=h=i=0$. Now $d+i=|Q\setminus
R|$, so this would imply $d>0$.

$R$ is also a minimal cut set, so $\Wh(\ppcore)\setminus\tilde{R}$ must
have exactly two components. In the diagram they are
$\X_0\cup\Y_0\cup\mathcal{Z}$ and
$\X_1\cup\Y_1$.
Since $\X_1\cup\Y_1$ is connected,
$\Y_1=\emptyset$ if and only if $g=0$.

Thus, we have:
\begin{enumerate}
\item $\Y_0=\emptyset \iff f=0 \implies d>0,\,c=h=i=0$
\item $\Y_1=\emptyset \iff g=0 \implies e>0,\,b=h=j=0$
\end{enumerate}

The Whitehead automorphism that pushes
\[Z=\{x\}\cup\{\text{vertices of $\Wh(v)$ in
component 0 of $\Wh(\ppcore)\setminus\tilde{Q}$}\}\]
 through the stem changes the valence of
vertex $x$ from $b+c+d+e+f+g$ to $a+c+e+g$.
By our minimal complexity assumption, we must therefore have $a\geq
b+d+f$.

Now $|Q\setminus R|>|Q\cap R|\geq a+b+c\geq 2b+c+d+f$, which means
that $|Q\setminus R|>d$, so $i>0$.

We will now change $Q$ and $R$ to a new decomposing pair $Q'$ and $R'$ for $S$ with
strictly smaller partially pruned core.

Let $\tilde{Q}'\setminus \tilde{R}'$ be the lines of
$\tilde{Q}\setminus \tilde{R}$ that do not pass through $v$.

Let $\tilde{R}'\setminus\tilde{Q}'$ be the rest of $\tilde{S}$.

Let $\tilde{Q}'\cap\tilde{R}'$ be $\tilde{Q}\cap\tilde{R}$ minus the
lines contributing to $a$ and $b$ plus the lines contributing to $f$.

\begin{figure}[h]
\labellist \small
\pinlabel $v$ [r] at 33 36
\pinlabel $a$ [l] at 13 36
\pinlabel $b$ [tr] at 28 53
\pinlabel $c$ [br] at 28 19
\pinlabel $d$ [tr] at 39 55
\pinlabel $e$ [br] at 39 16
\pinlabel $f$ [bl] at 48 60
\pinlabel $g$ [tl] at 48 12
\pinlabel $h$ [r] at 114 33.5
\pinlabel $i$ [b] at 183 57
\pinlabel $j$ [t] at 183 16
\pinlabel $\X_0$ at 22 64
\pinlabel $\X_1$ at 22 9
\pinlabel $\Y_0$ at 115 64
\pinlabel $\Y_1$ at 115 9
\pinlabel $\mathcal{Z}$ at 205 37
\pinlabel $Q'$ [b] at 170 65
\pinlabel $R'$ [t] at 170 9
\pinlabel $S$ [b] at 176 66
\endlabellist
  \centering
  \includegraphics[width=\textwidth]{Pictures/whschematic2}
  \caption{Schematic diagram for modified $\Wh(\ppcore)$}
\label{fig:ppcore2}
\end{figure}

\begin{align*}
  |S|-|R'|&=|{Q}'\setminus{R}'|-|{Q}'\cap{R}'|\\
&=|Q\setminus R|-d-(|Q\cap R|-a-b+f)\\
&=|Q\setminus R|-|Q\cap R|+a+b-d-f\\
&\geq |Q\setminus R|-|Q\cap R| +(b+d+f)+b-d-f\\
&=|S|-|R|+2b\geq |S|-|R|>0
\end{align*}

A similar computation shows $|S|-|Q'|\geq |S|-|Q|+2(b+d)>0$.

We must show that $Q'$ and $R'$ are non-crossing minimal cut sets.

The components of $\Wh(\ppcore)\setminus\tilde{Q}'$ are $\Y_0$
and $\X_0\cup\X_1\cup\Y_1\cup\mathcal{Z}$. To
see that the latter is connected, note that $a>0$, $e+j>0$ and either
$\Y_1=\emptyset$ or $g>0$.

Thus, $Q'$ is a minimal cut set since $\Wh(\ppcore)\setminus\tilde{Q}'$
has exactly two connected components and every line of $\tilde{Q}'$
goes from one component to the other.

By similar considerations, $R'$ is a minimal cut set since
$\Wh(\ppcore)\setminus\tilde{R}'$ has components
$\Y_0\cup\mathcal{Z}$ and $\X_0\cup\X_1\cup\Y_1$.

That $Q'$ and $R'$ are non-crossing follows from the observation:
\[\Y_0\cap\left(\X_0\cup\X_1\cup\Y_1\right)=\emptyset\]

We have not added anything to $\tilde{Q}'\cap\tilde{R}'$ except
possibly some lines going through $v$, so the new partially pruned core is contained in the old one minus the
vertex $v$.

If $\bar{x}$ is in component 0, repeat the argument with the roles of
$Q$ and $R$ reversed and reach a similar conclusion.

Thus, by repeating this process, we can reduce the partially pruned
core until we find some decomposing pair $Q$ and $R$
so that the partially pruned core is just $*$. We have already
seen that that leads to a contradiction, so $S$ is indecomposable.
\end{proof}

\begin{theorem}[Indecomposables are bounded]\label{theorem:boundeddecomposable}
  The diameter of the pruned core of an indecomposable cut set $S$ is
  bounded in terms of $\mathcal{L}$ and $|S|$.
\end{theorem}
\begin{proof}
If $\pcore$ is a point or two points we are done. Otherwise it is a tree with leaves. Each leaf contains a line from $\tilde{S}$ that does not go through its stem, so there are at most $|S|$ leaves.

Suppose $\X$ is a segment of $\pcore$ that does not have any lines of $\tilde{S}$ going through it.
By \fullref{corollary:bothcomponents}, at every vertex of $\pcore$ there are edges of $\Wh(\pcore)\setminus\tilde{S}$ from both components.
Since $S$ is indecomposable, by \fullref{proposition:decomposable} it is not the case that one of these components is a free edge.
Now apply \fullref{corollary:longsegments} and conclude that there is a bound $R$ on the length $\X$.

Similarly, if $\X$ is a segment of $\pcore$ that meets exactly one of the $l_i$ then it has length bounded by $R$.

It follows that the diameter of $\pcore$ is at most $2R(|S|-1)$.
\end{proof}

\endinput


TITLE: What is the value of $\frac{d\alpha}{dt} $?
QUESTION [2 upvotes]: The following question was asked in an exam:
 Given $\alpha $=$\int_{0}^{\infty}{\frac {dt}{1+t^2}} $.
Then is $\frac {d\alpha}{dt} $=$\frac{1}{1+t^2}$?
I know that the value $\alpha$=$\frac {\pi}{2} $. So as $\alpha $ is a constant, it's derivative is 0. Am I correct?

REPLY [3 votes]: I think that the question is silly. But anyway, you are right. And the fact that $\int_0^\infty\frac{\mathrm dt}{1+t^2}=\frac\pi2$ is not important. The only thing that matters is that $\alpha$ is constant.


TITLE: Question regarding logarithms
QUESTION [0 upvotes]: Can you factor out the $m$ out of $\ln(c\cdot x^m)$  where $c$ is a constant?

REPLY [0 votes]: If $m\not = 0$, then we have
$$ \ln\left(cx^m\right) = \ln c + \ln x^m = \ln c + m\ln x = m\left(\frac1m\ln c + \ln x\right)$$


text:
In this appendix, we discuss how the algorithms in \cref{sec:algorithms} fit within the general \acl{SA} framework of \cref{sec:SA}.
Specifically, we prove the general conditions of \cref{thm:APT,prop:APT} which guarantee that \crefrange{alg:SGDA}{alg:SPSA} generate \aclp{APT} of the mean dynamics \eqref{eq:MD}.

\subsection{Generalities and preliminaries}

Before doing so, we will require some background material on \aclp{APT}.
Following \citet{BH96} and \citet{Ben99}, we first recall the definition of the ``effective time'' $\curr[\efftime] = \sum_{\runalt=\start}^{\run} \iter[\step]$ as the time that has elapsed at the $\run$-th iteration of the discrete-time process $\curr[\state]$;
recall also the definition \eqref{eq:interpolation} of the continuous-time interpolation $\apt{\ctime}$ of $\curr$ as
\begin{equation}
\tag{\ref{eq:interpolation}}
\apt{\ctime}
	= \curr
		+ \frac{\ctime - \curr[\efftime]}{\next[\efftime] - \curr[\efftime]} (\next - \curr)
\end{equation}
We will further require the ``continuous-to-discrete'' correspondence
\begin{equation}
\label{eq:tinv}
\tinv(\ctime)
	= \sup\setdef{\run\geq\start}{\ctime\geq\curr[\efftime]}
\end{equation}
which measures the number of iterations required for the effective time $\curr[\efftime]$ of the process to reach the timestamp $\ctime$;
for future use, we also define the quantity
\begin{equation}
\label{eq:tinv-horizon}
\curr[\tinv]
	\equiv \curr[\tinv](\horizon)
	= \tinv(\curr[\efftime] + \horizon).
\end{equation}
Finally, given an arbitrary sequence $\curr[A]$, we will denote its piecewise constant interpolation as
\begin{equation}
\overline A(\ctime)
	= \curr[A]
	\quad
	\text{for all $\ctime \in [\curr[\efftime],\next[\efftime]]$, $\run\geq\start$.}
\end{equation}
Using this notation, the (affinely) interpolated process $\apt{\ctime}$ can be expressed in integral form as
\begin{equation}
\apt{\ctime}
	= \apt{\cstart}
		+ \int_{\cstart}^{\ctime}
			\bracks{\vecfield(\overline\state(\ctimealt)) + \overline\error(\ctimealt)} \dd\ctimealt
\end{equation}
where $\curr[\error]$ denotes the generalized error term of \eqref{eq:RM}.

With all this in hand, \citet[Prop.~4.1]{Ben99} provides the following general condition for $\apt{\ctime}$ to be an \ac{APT} of the mean dynamics \eqref{eq:APT}:

\begin{proposition}
\label{prop:Benaim}
Suppose that $\apt{\ctime}$ is bounded and satisfies the general condition

\begin{equation}
\label{eq:Benaim}
\lim_{\ctime\to\infty} \Delta(\ctime;\horizon)
	= 0
	\quad
	\text{for all $\horizon>0$},
\end{equation}
where
\begin{equation}
\label{eq:delta}
\txs
\Delta(\ctime;\horizon)
	= \sup_{0\leq h\leq \horizon} \norm*{\int_{\ctime}^{\ctime+h} \overline\error(\ctimealt) \dd\ctimealt}.
\end{equation}
Then, $\apt{\ctime}$ is an \ac{APT} of \eqref{eq:MD}.
\end{proposition}

\subsection{Proof of \cref{thm:APT}} \label{app:proof-APT}

Our proof of \cref{thm:APT} revolves around the direct verification of the requirement \eqref{eq:Benaim} of \cref{prop:Benaim} via the use of maximal inequalities and martingale limit theory.\footnote{\citet{Ben99} provides a set of sufficient conditions for \eqref{eq:Benaim} to hold when $\apt{\ctime}$ is generated by a \ac{RM} scheme with $\bbound_{\run}=0$ and $\sup_{\run} \sdev_{\run} < \infty$;
however, our setting requires a more general treatment.}
For convenience, we restate the theorem below in full:

\APT*

\begin{proof}

Since we have shown that $\curr$ remains bounded in \cref{prop:stability}, it suffices to verify \eqref{eq:Benaim}.

Our proof relies on the \acf{BDG} inequality \citep{Bur73,HH80} which bounds the maximal value of a martingale $\curr[S]$ via its quadratic variation as
\begin{equation}
\label{eq:BDG}
\tag{BDG}
c_{2} \exof*{\sum_{\runalt=\start}^{\run} (\iter[S] - \preiter[S])^{2}}
	\leq \exof*{\max_{\runalt=\start,\dotsc,\run} \abs{\iter[S]}^{2}}
	\leq C_{2} \exof*{\sum_{\runalt=\start}^{\run} (\iter[S] - \preiter[S])^{2}},
\end{equation}
where $c_{2},C_{2}>0$ are universal constants.
As such, applying \eqref{eq:BDG} to the martingale $S_{m} = \sum_{\runalt=\run}^{m} \iter[\step] \iter[\noise]$ (after an appropriate shift of the starting time), we get
\begin{align}
\exof*{
	\sup_{\run\leq m \leq\curr[\tinv]}
		\norm*{\sum_{\runalt=\run}^{m} \iter[\step] \iter[\noise]}^{2}}
	&\leq C_{2} \exof*{\sum_{\runalt=\run}^{\curr[\tinv]} \iter[\step]^{2} \norm{\iter[\noise]}^{2}}

	\notag\\
	&= C_{2} \sum_{\runalt=\run}^{\curr[\tinv]} \iter[\step]^{2} \iter[\sdev]^{2}
	= C_{2} \int_{\curr[\efftime]}^{\curr[\efftime]+\horizon}
		\overline\step^{2}(\ctimealt) \overline\sdev^{2}(\ctimealt) \dd\ctimealt,
\end{align}
where $\curr[\tinv] = \curr[\tinv](\horizon) = \tinv(\curr[\efftime] + \horizon)$ is defined as in \eqref{eq:tinv-horizon}.
Now, mimicking \eqref{eq:delta}, let
\begin{equation}
\label{eq:delta-0}
\Delta_{0}(\ctime;\horizon)
	= \sup_{0\leq h\leq \horizon} \norm*{\int_{\ctime}^{\ctime+h} \overline\noise(\ctimealt) \dd\ctimealt}.
\end{equation}
so our previous bound shows that
\begin{align}
\exof{\Delta_{0}(\ctime;\horizon)^{2}}
	&\leq C_{2} \int_{\ctime}^{\ctime+\horizon}
		\overline\step^{2}(\ctimealt) \overline\sdev^{2}(\ctimealt) \dd\ctimealt.
\end{align}

We will proceed to show that $\lim_{\ctime\to\infty} \Delta_{0}(\ctime;\horizon) = 0$ for all $\horizon>0$ by considering the sequence of intervals $[\runalt\horizon,(\runalt+1)\horizon]$ and using the Borel-Cantelli lemma in order to show that $\Delta_{0}(\runalt\horizon;\horizon) \to 0$ as $\runalt\to\infty$.
Indeed, we have
\begin{align}
\sum_{\runalt=\start}^{\infty} \exof{\Delta_{0}(\runalt\horizon;\horizon)^{2}}
	&\leq C_{2} \int_{\cstart}^{\infty}
		\overline\step^{2}(\ctimealt) \overline\sdev^{2}(\ctimealt) \dd\ctimealt
	= C_{2} \sum_{\run=\start}^{\infty} \curr[\step]^{2} \curr[\sdev]^{2}
	< \infty
\end{align}
with the last step following from \cref{asm:noise}.
Then, if we consider the event $\event_{\runalt}(\eps) = \{\Delta_{0}(\runalt\horizon;\horizon) > \eps\}$,
Chebysev's inequality gives
\begin{equation}
\sum_{\runalt=\start}^{\infty} \probof{\event_{\runalt}(\eps)}
	\leq \frac{\sum_{\runalt=\start}^{\infty} \exof{\Delta_{0}(\runalt\horizon;\horizon)^{2}}}{\eps^{2}} < \infty,
\end{equation}
and hence, by the Borel-Cantelli lemma, we get
\begin{equation}
\probof*{\limsup_{\runalt\to\infty} \event_{\runalt}(\eps)}
	= 0.
\end{equation}
This shows that, with probability $1$, we have $\Delta_{0}(\runalt\horizon;\horizon) \leq \eps$ for all but a finite number of $\runalt$;
put differently, the event $\event(\eps) = \{\text{$\Delta_{0}(\runalt\horizon;\horizon)$ occurs infinitely often}\} = \intersect_{\run=\start}^{\infty} \union_{\runalt=\run}^{\infty} \event_{\runalt}(\eps)$ has $\probof{\event(\eps)} = 0$.
Therefore, as a union of probability zero events, we have
\begin{equation}
\probof*{\liminf_{\runalt\to\infty} \Delta_{0}(\runalt\horizon;\horizon) > 0}
	= \probof*{\union_{\run=\start}^{\infty} \event(1/\run)}
	\leq \sum_{\run=\start}^{\infty} \probof{\event(1/\run)}
	= 0,
\end{equation}
\ie $\Delta_{0}(\runalt\horizon;\horizon) \to 0$ with probability $1$.

Thus, going back to the requirements of \cref{prop:Benaim}, we get
\begin{align}
\Delta(\runalt\horizon;\horizon)
	&= \sup_{0\leq h\leq \horizon} \norm*{\int_{\runalt\horizon}^{\runalt\horizon+h} \overline\error(\ctime) \dd\ctime}
	= \sup_{0\leq h\leq \horizon} \norm*{\int_{\runalt\horizon}^{\runalt\horizon+h} [\overline\noise(\ctime) + \overline\bias(\ctime)]\dd\ctime}
	\notag\\
	&\leq \Delta_{0}(\runalt\horizon;\horizon)
		+ \sup_{0\leq h\leq \horizon} \int_{\runalt\horizon}^{\runalt\horizon+h} \overline\bbound(\ctime) \dd\ctime.
	\notag\\
	&\leq \Delta_{0}(\runalt\horizon;\horizon)
		+ \horizon \max_{0\leq h \leq \horizon} \overline\bbound(\runalt\horizon + h).
\end{align}
Given that $\lim_{\runalt\to\infty} \bbound_{\runalt} = 0$, the above shows that $\Delta(\runalt\horizon;\horizon) \to 0$ as $\runalt\to\infty$.
Moreover, for all $\ctime \in [\runalt\horizon,(\runalt+1)\horizon]$, we have $\Delta(\ctime;\horizon) \leq 2 \Delta(\runalt\horizon;\horizon) + \Delta((\runalt+1)\horizon;\horizon)$ so $\Delta(\ctime;\horizon) \to 0$ with probability $1$.
With $\horizon>0$ arbitrary, we conclude that \eqref{eq:Benaim} holds with probability $1$, so our claim follows from \cref{prop:Benaim}.
\end{proof}

\subsection{Proof of \cref{prop:APT}}\label{app:RM-APT}

We are now in a position to prove that the generalized \ac{RM} schemes presented in \cref{sec:algorithms} comprise \aclp{APT} of the mean dynamics \eqref{eq:MD}.
For convenience, we state the relevant result below:

\algoAPT*

\begin{proof}\label{pf:prop1}

We first note that $\sum_n \curr[\step]^2  < \infty$ by our choice of step-sizes. Thus, in order to prove that $\exof{\sum_n \curr[\step] \curr[\bbound]} < \infty$, $\exof{\sum_n \curr[\step]^2 \curr[\bbound]^2} < \infty$, and $\exof{\sum_n \curr[\step]^2 \curr[\sdev]^2} < \infty$, it suffices to show $\exof{\curr[\bbound]}= \exof{\norm{\curr[\bias]}} = \bigoh( \curr[\step])$ and $\exof{\curr[\sdev]^2} \leq \sdev^2$ for some constant $\sdev$.

We next proceed method-by-method:

\para{\cref{alg:SGDA}: \Acl{SGDA}}

For \eqref{eq:SGDA}, we have $\curr[\error] = \curr[\noise] = \err(\curr;\curr[\seed])$ and $\curr[\bias] = 0$, so \cref{asm:bias} is satisfied automatically (since $\curr[\bbound] = 0$).
Our claim then follows from the stated assumptions for \eqref{eq:SFO}.

\para{\cref{alg:PPM}: \Acl{PPM}}

For \eqref{eq:PPM}, we have $\curr[\noise] = 0$ and
\begin{align*}
\norm{\curr[\bias]} &= \norm{  \vecfield(\curr) - \vecfield(\next)  } \\
&\leq \lips  \norm{  \curr - \next  } \\
&= \curr[\step] \lips \norm{  \vecfield(\curr) }  \\
&\leq \curr[\step] \lips M = \bigoh ( \curr[\step]).
\end{align*}where $\lips$ and $M$ are the Lipschitz constant of $\vecfield$ and $\minmax$, respectively.

\para{\cref{alg:SEG}: \Acl{SEG}}

For \eqref{eq:SEG}, we have
$\curr[\noise] = \err(\lead;\lead[\seed])$
and
$\curr[\bias] = \vecfield(\lead) - \vecfield(\curr)$ so that $\exof{\curr[\sdev]^2} \leq \sdev^2$ by \eqref{eq:SFO}.

To verify \cref{asm:bias}, by the definition of \eqref{eq:SEG}, we have
\begin{align}
\label{eq:bias-SEG}
\norm{\curr[\bias]}
	= \norm{\vecfield(\lead) - \vecfield(\curr)}
	&\leq \lips \norm{\lead - \curr}
	\notag\\
	&= \curr[\step] \norm{\orcl(\curr;\curr[\seed])}
	= \curr[\step] \lips \norm{\vecfield(\curr) + \err(\curr;\curr[\seed])}
	\notag\\
	&\leq \curr[\step] \lips \norm{\vecfield(\curr)}
		+ \curr[\step] \lips \norm{\err(\curr;\curr[\seed])}.
\end{align}Since $\minmax$ is assumed to be Lipschitz and $\err(\curr;\curr[\seed])$ finite variance,

taking the expectation on both sides of the above shows $\exof{\curr[\bbound]} = \bigoh( \curr[\step])$.
\newcommand{\noiselevel}{\sqrt{\run \log^{1+\frac{\epsilon}{2}} \run}}
It remains to verify that $\lim_{\run\to\infty} \curr[\bbound] =0$ with probability 1. Now, by Chebyshev's inequality and \eqref{eq:SFO}, we have
\begin{equation}
\prob\left( {\norm{\err(\curr;\curr[\seed])} \geq \noiselevel}\right)
	\leq \frac{\sdev^2}{\run \log^{1+\frac{\epsilon}{2}} \run}
\end{equation}where $\eps$ is the same as in our choice of step-size in \cref{prop:APT}.
In turn, this implies that $$\sum_{\run = 2}^\infty\prob\left( {\norm{\err(\curr;\curr[\seed])} \geq \noiselevel}\right) < \infty$$so, by the Borel-Cantelli lemma, we have $\norm{\err(\curr;\curr[\seed])} = \bigoh\left( \noiselevel \right)$ with probability $1$.
Hence, by our assumptions for the method's step-size, we get
\begin{equation}
\curr[\step] \norm{\err(\curr;\curr[\seed])}

	= \bigoh\parens*{\frac{\noiselevel}{ \sqrt{\run \log^{1+\eps} \run} }}
	= \bigoh\parens*{\frac{1}{    \log^{\frac{\eps}{4}}\run  } }
\end{equation}
so that, in view of \eqref{eq:bias-SEG}, $\bbound_{\run}\to0$ with probability $1$.

\para{\cref{alg:PEG}: \Acl{OG}}

For \eqref{eq:PEG}, we have
$\curr[\noise] = \err(\curr;\lead[\seed])$
and
$\curr[\bias] = \vecfield(\lead) - \vecfield(\curr)$,
so $\exof{\curr[\sdev]^2} = \sdev^2$ again holds by \eqref{eq:SFO}.
The bias term can then be bounded exactly as in the case of \cref{alg:SEG}.

\para{\crefrange{alg:SGDA}{alg:PEG}: Alternating \ac{RM} schemes \eqref{eq:alt-RM}}

We now show that the alternating version of \crefrange{alg:SGDA}{alg:PEG} still constitute an \ac{APT} of \eqref{eq:MD}.

By \cref{lem:alternating}, we know that the alternating version of an \ac{RM} scheme is another \ac{RM} scheme with the same noise and new bias satisfying:
\begin{align}
\norm{\curr[\bias']}

&\leq \norm{\curr[\bias]} +  \norm{\vecfield_{\maxvar}(\next[\minstate],\curr[\maxstate]) - \vecfield_{\maxvar}(\curr[\minstate],\curr[\maxstate])}  \nonumber\\
	&\leq  \norm{\curr[\bias]} +  \lips \norm{\next[\minstate] - \curr[\minstate]} \nonumber\\
	&\leq \norm{\curr[\bias]} +  \curr[\step]\lips \left( \norm{ \vecfield(\curr)}  +\norm{ \curr[\bias]} + \norm{\curr[\noise]    } \right)  \label{eq:bias-order}
\end{align}by the definition of an \ac{RM} scheme. Since $\curr[\step]\lips\norm{ \curr[\bias]} = o \left( \norm{ \curr[\bias]} \right)$, the rest is the same as \cref{alg:SEG}.

We also note that \eqref{eq:bias-order} can be applied recursively to show that the bias term $\curr[\bias]^{(k_1,k_2)}$ of any $(k_1,k_2)$ version of \ac{RM} schemes satisfy
\begin{equation}
\norm{\curr[\bias]^{(k_1,k_2)}} \leq (k_1+k_2-1) \Big( \norm{\curr[\bias]} +  \curr[\step]\lips \left( \norm{ \vecfield(\curr)}  +\norm{ \curr[\bias]} + \norm{\curr[\noise]    } \right) \Big),
\end{equation}thus enjoying the same properties as the vanilla alternating $(1,1)$-\ac{RM} schemes in view of \eqref{eq:bias-order}.

\para{\cref{alg:SPSA}: \Acl{SPSA}}

Because of the algorithm's different oracle structure (zeroth- \vs first-order feedback), the analysis of \eqref{eq:SPSA} is different.
We begin with the algorithm's bias term, given here by
\begin{align}
\label{eq:bias-SPSA}
\curr[\bias]
	&= \exof{\curr[\signal] \given \curr[\filter]} - \vecfield(\curr)
\end{align}
with
\begin{equation}
\label{eq:signal-SPSA}
\curr[\signal]
	= \pm (\vdim/\curr[\mix])
		\, \minmax(\curr + \curr[\mix]\curr[\seed])
		\, \curr[\seed]
\end{equation}
denoting the method's one-shot \ac{SPSA} estimator.
To bound it, let
\begin{equation}
v_{\coord,\run}
	= \exof{\signal_{\coord,\run} \given \curr[\filter]}
\end{equation}
denote the $\coord$-th component of $\curr[\signal] \in \R^{\vdim}$ after having averaged out the choice of the random seed $\curr[\seed]$ (which, by default, is not $\curr[\filter]$-measurable).
We then have

\begin{align}
v_{\coord,\run}
	&= \pm \frac{\vdim}{\mix_{\run}}
		\cdot \frac{1}{2\vdim}
			\bracks[\big]{
			\minmax(\curr + \mix_{\run}\bvec_{\coord})
			- \minmax(\curr - \mix_{\run}\bvec_{\coord})}

\end{align}
where, as per our discussion in \cref{sec:algorithms}, the ``$\pm$'' sign is equal to $-1$ if $\bvec_{\coord}\in\bvecs_{\minvars}$ and $+1$ if $\bvec_{\coord}\in\bvecs_{\maxvars}$.
Then, by the mean value theorem, there exists some $\curr[\aux]$ in the line segment $\big[\curr - \mix_{\run}\bvec_{\coord},\curr + \mix_{\run}\bvec_{\coord}\big]$ such that
\begin{equation}
v_{\coord,\run}
	= \pm \pd_{\coord} \minmax(\curr[\aux])
	= \vecfield_{\coord,\run}(\curr[\aux]).
\end{equation}
Since $\vecfield$ is Lipschitz continuous, it follows that
\begin{align}
\label{eq:vecdiff}
\abs{v_{\coord,\run} - \vecfield_{\coord,\run}(\curr)}
	&= \abs[\big]{
		\vecfield_{\coord,\run}(\curr[\aux])
		- \vecfield_{\coord,\run}(\curr)
		}
	\leq \lips \norm{\curr[\aux] - \curr}
	= \bigoh(\curr[\mix])
\end{align}
since $\curr[\aux] \in \big[\curr - \mix_{\run}\bvec_{\coord},\curr + \mix_{\run}\bvec_{\coord}\big]$.
Finally, for the oracle's variance, we have $\norm{\curr[\signal]}^{2} = \bigoh(1/\curr[\mix]^{2})$ by construction so, under the stated assumptions for $\curr[\step]$ and $\curr[\mix]$, \cref{asm:noise} is satisfied and our claim follows from \cref{thm:APT}.
\end{proof}


TITLE: Derive a closed formula for the generating function of this recurrence relation
QUESTION [3 upvotes]: This is a given recurrence relation
$a_n=19(F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0)$
where $F_n$ is Fibonacci number and $a_0=9$. Find the generating function $A(x)$  of the sequence $a_n$
I get the generating function for $F_n=\frac x{1-x-x^2}$
I try this for hour with derivative method $A'(x)$ but I still do not get it. Can you help me please, any method is fine.

REPLY [2 votes]: From
$$
  F(x)A(x) = \sum_{n=0}^\infty F_nx^n   \cdot  \sum_{n=0}^\infty a_nx^n
 = \sum_{n=0}^\infty \Bigl( \sum_{k=0}^n F_k a_{n-k}\Bigr) x^n
$$
we see that $F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0$ is the coefficient of
$x^{n-1}$ in $F(x)A(x)\,$, or the coefficient of $x^n$ in $xF(x)A(x)\,$.
Therefore your recurrence relation can be expressed in terms of
the generating functions as
$$
A(x) = 9 + 19 \, x \, A(x) F(x)
$$
and $F(x)$ is known.


TITLE: Lagrange Multipliers for farthest distance
QUESTION [2 upvotes]: I am trying to find the farthest point from the origin to a point on the circle $$(x-2)^2+y^2=1$$ I am not great with the formatting on here but this is what I have so far...
$$f(x,y)=x^2+y^2 $$ $$g(x,y)=(x-2)^2+y^2-1$$
$$\nabla f =\lambda\nabla g$$
$$<2x,2y>=\lambda<2(x-2),2y>$$
(1)$$2x=2\lambda(x-2)$$ (2)$$2y=\lambda2y$$
From (2)$$\lambda=1$$
substitute $\lambda$ into (1) and produce 0=-4 which tells me no solution... What did I do wrong???

REPLY [2 votes]: You have proved that $\lambda=1$ was impossible.
So from (2):
$$
0 = (\lambda-1)y \implies y = 0;
\\
x - 2 = \pm 1
$$
which gives the maximizer and minimizer.


TITLE: How exotic can an infinite biproduct in an additive category be?
QUESTION [15 upvotes]: Let $C$ be a category with a zero object $0$, small products, and small coproducts. Let $(A_i)_{i \in I}$ be a (possibly infinite) list of objects. There is a canonical map $\amalg_{i \in I} A_i \to \prod_{i \in I} A_i$. If this map is an isomorphism, we denote the product / coproduct by $\oplus_{i \in I} A_i$ and call it the biproduct of the $A_i$. If the $A_i$'s are all the same, call this the $I$-fold bipower $A^{(I)}$ of $A$. When $I$ is finite, I think I have a pretty good handle on $I$-indexed biproducts. But when $I$ is infinite, I get more confused. Here are some things I know or think I know about this situation:

Some categories have all small biproducts. The main examples I'm aware of are the category of suplattices and the category of locally presentable categories (and left adjoint functors). These can be modified to get examples of categories which have $\kappa$-small biproducts but no larger.

Certain infinite biproducts may exist in an additive category. For example, in $Ab^{\mathbb N}$ (where $\mathbb N$ is regarded as a set), the constant functor at $\mathbb Z$ is the biproduct of the representables.

On the other hand, I thought I knew an argument at some point that in an additive category, any infinite bipower of an object must be zero. I can't seem to reproduce the argument, but I think it was some sort of Eilenberg swindle sort of thing...

More generally, I want to say that if an infinite biproduct $\oplus_{i \in I} A_i$ exists in an additive category, then we must be "close" to the situation of (2) above, where $Hom(A_i,A_j) = 0$ for $i \neq j$. I don't know how to formulate this, though, if it's correct in any sense at all.

So I suppose my questions are the following:
Question 1: Is it true that in an additive category, any infinite bipower which exists must be zero?
Question 2: In an additive category, if an infinite biproduct $\oplus_{i \in I} A_i$ exists, is there sense in which it must be "close" to the setting of (2) above? For example, must it be the case that for each $i \in I$, $Hom(A_i,A_j) = 0$ for all but finitely many $j \in I$?

REPLY [7 votes]: Here's another example for Question 2 that I encountered in nature.
In the derived category of modules for a ring, pick one module $M_i$ for each $i\in\mathbb{Z}$, and let $A_i=M_i[i]$. Then the natural map
$$\coprod_{i\in\mathbb{Z}} A_i\to\prod_{i\in\mathbb{Z}} A_i$$
is an isomorphism, since in each degree only finitely many (in fact, only one) of the $A_i$ have nonzero homology, so the map is an isomorphism on homology. So there is a biproduct $\bigoplus_{i\in\mathbb{Z}} A_i$.
But $\text{Hom}(A_i,A_j)=\text{Ext}^{j-i}(M_i,M_j)$, which may be nonzero for all $j\geq i$.


TITLE: X and Y are uniformly distributed independent random variables, let Z = max{X,Y}. find the PDF of Z
QUESTION [1 upvotes]: I have a few questions regarding this problem that I do not quite understand.
For a random variable U distributed uniformly on the interval [0,1] its CDF is given by
$$\ F_U(u) = \begin{Bmatrix} 0, & u < 0 \\ u, & 0 \le u \le 1, \\ 1, & u > 1 \\ \end{Bmatrix} $$

I don't understand why for values of u > 1 the CDF of U is 1. I would think that $\ F_U $ would be undefined outside of the interval that the random variable U is defined on.

====The solution to the problem in post title and  explanation of my lack of understanding====
Let Z = max{X,Y}. For z$\ \in $ (0,1)
$\ F_Z(z) = P(Z \le z ) $
=  P(X$\le$z and Y$\le$z)
= $\ F_X(z)F_Y(z)$
= $\ z^2 $

I understand that the CDF of a u.r.v. is $\ \frac{x-a}{b-a}$ for X on [a,b] so that $\ F_X(z)$ and $\ F_Y(z) $ are equal to z, but I do not understand why P(X$\le$z and Y$\le$z) = $\ F_Z$

REPLY [2 votes]: I don't understand why for values of $u > 1$ the CDF of $U$ is $1$. I would think that $F_U$ would be undefined outside of the interval that the random variable $U$ is defined on.

The probability density function is defined for values above the support's supremum; it equals zero there.   (Likewise for values below the infimum.)
$U$ has a support of $(0;1)$, so $\mathsf P(U\leqslant 1)=1$ by the Law of total probability.   A random variable is certainly not-more than the supremum of its support.   Likewise it will also certainly not be greater than any higher value.   $\therefore~\forall u\geqslant 1 : \mathsf P(U\leqslant u)= 1~$.

I do not understand why $P(X\leqslant z\text{ and }Y\leqslant z) =
F_Z(z)$

Because $F_Z(z)=\mathsf P(Z\leqslant z)$, by definition, and $Z=\max\{X,Y\}$.
Now when $Z$ is not greater than $z$, neither $X$ nor $Y$ is greater than $z$, and vice versa.   Thus the event $\{Z\leq z\}$ is the join of the events $\{X\leqslant z\}$ and $\{Y\leqslant z\}$.
$$\begin{align}F_Z(z) &= \mathsf P(Z\leqslant z) \\ & =\mathsf P(\min\{X,Y\}\leqslant z) \\ &= \mathsf P(X\leqslant z~\cap~ Y\leqslant z) \\ &= \mathsf P(X\leqslant z)~\mathsf P(Y\leqslant z) \\ &= F_X(z)~F_Y(z)\end{align}$$