TITLE: Compactification in String Theory and Compactification in Topology are they the same thing?
QUESTION [6 upvotes]: In topology, there is a concept of compactification which is defined as follows.
A space $Z$ is a compactification of $X$ if $Z$ is compact Hausdorff and there exists an
embedding $j:X \rightarrow Z $ such that $\overline{j(X)} = Z$.
I would like to know if the compactification in String theory is the same compactification defined in topology.

REPLY [4 votes]: No, different concepts.
The compactification in string theory is the process of taking a theory with extra infinitely extended dimensions (w.r.t. the canonical 3+1 dimensions) and modifying it so that the extra dimensions are finite.
Intuitively, compactness in topology does not refer to the size of a space, but to properties of not having "gaps" or "missing endpoints". In particular a compact space may very well extend infinitely, for instance the real line including the endpoints $+\infty$, $-\infty$.

REPLY [4 votes]: I don't know much about compactification in string theory, but the idea is based on the compactification in (4+1) D Kaluza-Klein theory, proposed in the years after the theory of general relativity was published to unite gravity and electromagnetism. (The weak and strong interaction were not discovered yet.)
The idea proposed by Kaluza was to generalize the metric tensor to five dimensions to add the electromagnetic vector potential as the components of the fifth dimension.
The idea proposed by Klein was that this dimension cannot be observed because it is compactified and here we have the connection to the topological one-point or Alexandroff compactification: $\mathbb{R}$ can be mapped to $\mathbb{S}^1\setminus\{*\}$ by the stereographic projection (which is your map $j$) and then be compactified to $\mathbb{S}^1$ by adding the missing point. Spacetime is therefore not $\mathbb{R}^{1,4}$, but $\mathbb{R}^{1,3}\times\mathbb{S}^1$, the same topological space as the Anti-deSitter space $\operatorname{AdS}_5$.
The extension of this extra dimension curled up is described by another scalar field $\phi$ added to the theory and so small, that only microscopic objects can observe it. (Just like a rope looks like a one-dimensional line to us, but has a two-dimensional surface to an ant.) Electric charge for example can be described as the velocity of the particle along the curled up fifth dimension, but is far above that of light so the theory failed.
Decades later, string theory reused the idea again to compactify even more dimensions using six-dimensional Calabi-Yau manifolds to reduce the dimensions from ten to four.


TITLE: $K_0$ ring of del-pezzo surface
QUESTION [0 upvotes]: Is there book or paper where described structure of $K_0$ ring of a del-pezzo surfaces? Especially in case of the blowup of projective line in three points.
I know method for computing $K_0$ ring of blowup but it's computationally heavy and i'm afraid of making a mistake.

REPLY [3 votes]: Let $X$ be the blowup of a plane at points $P_1$, \dots, $P_n$ with the corresponding exceptional divisors $E_1$, \dots, $E_n$. Let $H$ be the pullback of the line class from the plane to $X$. Then
$$
O, O(H), O(2H), O_{E_1}, \dots, O_{E_n}
$$
is a full exceptional collection, hence the corresponding classes
$$
[O], [O(H)], [O(2H)], [O_{E_1}], \dots, [O_{E_n}]
$$
form a basis in $K_0$.
To understand the multiplication note that there are exact sequences
$$
0 \to O((t-3)H) \to O((t-2)H)^{\oplus 3} \to O((t-1)H)^{\oplus 3} \to O(tH) \to 0
$$
for each $t$ (this is a twist of the pullback of the Koszul complex),
that allows to express inductively all $[O(tH)]$ from $[O]$, $[O(H)]$, $[O(2H)]$,
and
$$
0 \to O \to O(H)^{\oplus 2} \to O(2H) \to O_P \to 0
$$
(again the pullback from the plane) that allows to express $[O_P]$.
After that you can write
$$
[O(aH)] \cdot [O(bH)] = [O((a+b)H)],\
[O(aH)] \cdot [O_{E_i}] = [O_{E_i}],\
[O_{E_i}] \cdot [O_{E_j}] = -\delta_{ij}[O_P].
$$


TITLE: Another planar separator ref question
QUESTION [8 upvotes]: Do any of you know a reference for the following (surprisingly tedious to prove) result?
Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \sqrt{t}+1)$.

REPLY [7 votes]: Here is a proof using a well-known hammer.
Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges which are part of the spanning tree.
I claim that the treewidth of $G$ is $O(\sqrt{t})$ which would imply the desired separator (and some more). To prove the claim let $k$ be the treewidth of $G$. Then by a theorem of Robertson-Seymour-Thomas, since $G$ is planar, there is a grid minor of size $\Omega(k)$. However a grid minor of size $\Omega(k)$ has $\Omega(k^2)$ disjoint cycles and each of them requires one of the $t+1$ edges. Hence $k = O(\sqrt{t})$.


TITLE: Modular Polynomial Arithmetic
QUESTION [0 upvotes]: I have came across this modular polynomial arithmetic question. I not really understand how the answers were derived.

For the first example right, from what I understand it is the polynomial whose coefficient are from Z_p, {0,1,...,p-1}. So given p = 3, I can get 0,1,2. And if given p = 2, I can get 0,1.
But I not sure how those x are derived. Any ideas? Thanks in advance.

REPLY [1 votes]: It seems to be the list of all polynomials of degree less than $2$, with coefficients in $\mathbf Z/3\mathbf Z$ in the first case; of all polynomials of degree less than $3$, with coefficients in $\mathbf Z/2\mathbf Z$ in the second case.
Indeed, for the first case, a polynomial of degree less than $2$  has the form  $a_0+a_1x$. Plug in the different possible values for  the pairs $(a_0,a_1)$, getting
\begin{matrix}
(0,0)\to \color{red}{0}&(0,1)\to \color{red}{x}&(0,2)\to \color{red}{2x}\\
(1,0)\to \color{red}{1}&(1,1)\to \color{red}{1+x}&(1,2)\to \color{red}{1+2x}\\
(2,0)\to \color{red}{2}&(2,1)\to \color{red}{2+x}&(2,2)\to \color{red}{2+2x}
\end{matrix}
The second case goe along the same lines:
\begin{matrix}
&(0,0,1)&&(0,1,1)\\
&\color{red}{x^2} &&\color{red}{x+x^2}\\
(0,0,0)&&(0,1,0) \\
\color{red}{0}&&\color{red}{x}\\[2ex]
&(1,0,1)&&(1,1,1)\\
& \color{red}{1+x}&&\color{red}{1+x+x^2}\\
(1,0,0)&&(1,1,0)\\
\color{red}{1}&& \color{red}{1+x}
\end{matrix}


TITLE: How many 100-digit numbers' sums of digits equal 3?
QUESTION [1 upvotes]: How many 100-digit numbers' sums of digits equal 3? How do I solve this?

REPLY [1 votes]: You may also want to check out integer partition or integer composition which counts the number of ways to sum to a number. 3 is such a small number so we don't have to think much about it for this particular problem, but it becomes increasingly useful when considering larger sums.
In this language what Travis does is to enumerate the compositions of the number 3:
3
2+1
1+2
1+1+1
As you can see in his answer each of them get their own combinatorics term in the sum.


text:
\begin{document}

\title{Functionals of Exponential Brownian Motion and Divided Differences}

\author{B. J. C. Baxter and R. Brummelhuis}

\address{School of Economics, Mathematics and Statistics,
Birkbeck College, University of London,
Malet Street, London WC1E 7HX,
England}

\email{b.baxter@bbk.ac.uk}

\begin{abstract}
We provide a surprising new application of classical approximation
theory to a fundamental asset-pricing model of mathematical finance.
Specifically, we
calculate an analytic value for the correlation coefficient between
exponential Brownian motion and its time average, and we find the
use of divided differences greatly elucidates formulae, providing a
path to several new results. As applications,
we find that this correlation coefficient is always at least
$1/\sqrt{2}$ and, via the Hermite--Genocchi integral relation,
demonstrate that all
moments of the time average are certain
divided differences of the exponential function. We also prove that
these moments agree with the somewhat more complex formulae
obtained by Oshanin and Yor.
\end{abstract}

\maketitle

\section{Introduction}
We begin with exponential, or geometric, Brownian motion, defined by
\be
S(t) = e^{(r-\frac{\sigma^2}{2})t +
  \sigma B(t)}, \qquad t \ge 0,
\label{a1}
\ee
where $B : [0,\infty) \to \RR$ is Brownian motion. In other words,
$B$ is a stochastic process, or {\em random function}, for which
$B(0) = 1$, its increments are independent, and, for $0 \le s < t$, the
increment $B(t) - B(s)$ is normally distributed with mean zero and
variance $t-s$. The basic properties of Brownian motion are
explained in Section 37 of \citeasnoun{billingsley}, while
\citeasnoun{karatzas} is a comprehensive treatise.
At a more elementary level, \citeasnoun{norris} provides a lucid derivation
of the main properties of Brownian motion, whilst \citeasnoun{higham}
provides a more general introduction well-suited to the numerical analyst.

We shall study the {\em time average}
\be
A(T) := \frac{1}{T} \int_0^T S(t)\,dt
\label{a2}
\ee
using the calculus of divided differences, a fundamental
tool in approximation theory. We will, in particular, show that the
correlation coefficient between $A(T)$ and $S(T)$, the moments of
$A(T)$ and, more generally, joint moments of $S(T)$ and $A(T)$ can be
elegantly, and usefully, expressed in terms of divided differences of
the exponential function. Now the time average $A(T)$ has been
extensively studied in the literature of Asian options; see, for
instance, \citeasnoun{yor}, \citeasnoun{yorbook} and
\citeasnoun{oshanin}. However, we find that our use of divided
differences both simplify and elucidate formulae. In Section 2, we
derive the correlation coefficient for $S(T)$ and $A(T)$, finding that
it is always at least $1/\sqrt{2}$, thus explaining the relative high
correlation that is observational folklore in the financial
community.\footnote{I am particularly grateful to my friend and colleague Dr
Dirk Siegel, a fellow PhD student of Mike Powell, who made this observation
known to me when consulting for
IBM.} In Section 3, we demonstrate that the divided
differences occurring in the lower moments of $S(T)$ and $A(T)$
generalise to all moments, using the fact that the integral of an
exponential function over a simplex can be expressed, via the
Hermite--Gennocchi formula, as a certain divided difference of the
exponential function. In Section 4, we provide the divided difference
theory required by the paper; some of this can, of course, be found in
the dedicatee's excellent textbook \citeasnoun{powell}, but
derivations of the
Hermite--Gennochi and Leibniz formula are less easily
available. Therefore we have provided their brief derivations in the
hope that this will enhance the

paper's use to both the mathematical
finance and the numerical analysis communities. Finally, in Section 5,
we use our divided difference approach to derive a recurrence relation
for the moments of $A(T)$.

We first observe the familiar result
\be
\EE S(T) = e^{(r-\sigma^2/2)T} \EE e^{\sigma T^{1/2} Z}
= e^{(r-\sigma^2/2)T} e^{\sigma^2 T/ 2} = e^{rT}.
\label{a4}
\ee
Here $Z$ denotes a generic $N(0,1)$ Gaussian random variable and we have
used the standard fact that
\be
\EE e^{\lambda Z}
= (2\pi)^{-1/2} \int_\RR e^{\lambda \tau} e^{-\tau^2/2}\,d\tau
= (2\pi)^{-1/2} \int_\RR e^{-\frac{1}{2}\{(\tau - \lambda)^2 -
  \lambda^2\}}\,d\tau
= e^{\lambda^2/2}.
\label{a5}
\ee
Similarly,
\begin{eqnarray}
\EE A(T)
&=& T^{-1} \int_0^T \EE S(t)\,dt\nonumber\\
&=& \frac{e^{rT} - 1}{rT}.
\label{a6}
\end{eqnarray}
The approximation theorist will immediately recognise the divided difference
\be
\EE A(T) = \exp[0, rT],
\label{a7}
\ee
but a sceptical reader might view this as mere coincidence; in fact,
it is but the tip of an iceberg.
We remind the reader that
$f[a_0, a_1, \ldots, a_n]$ is the highest coefficient of the unique polynomial
of degree $n$ interpolating $f$ at distinct points
$a_0, \ldots, a_n \in \RR$, which implies $f[a_0] = f(a_0)$ and
\[
f[a_0, a_1] = \frac{f(a_1) - f(a_0)}{a_1 - a_0}.
\]
Further, it is evident that a divided difference does not depend
on the order in which the points $a_0, a_1, \ldots, a_n$ are chosen.
As mentioned above, Section \ref{divdiffsec}
collects further divided difference theory required by this paper.

\section{The correlation coefficient between the time average and the asset}

We shall compute the correlation coefficient between $S(T)$
and $A(T)$. Specifically, we calculate
\be
R
:= \frac{\EE \left(S(T) A(T)\right) -
      \EE \left(S(T)\right) \EE\left(A(T)\right)}
   {\sqrt{\var S(T) \var A(T)}}.
\label{a7_1}
\ee

\noindent
We find an elegant  divided difference expression for $R$.

\begin{thm}
The correlation coefficient \eqref{a7_1} is given by
\be
R \equiv R(rT, \sigma^2 T) = \frac{ \exp[rT, 2rT, (2r+\sigma^2)T] }
    { \sqrt{ 2\exp[2rT, (2r+\sigma^2)T] \exp[0, rT, 2rT, (2r+\sigma^2)T]} }.
\label{a7_2}
\ee
\label{thm_corrcoeff}
\end{thm}

Let us begin our derivation.

\begin{lem} If $0 \le a \le b$, then
\be
\EE S(a) S(b) = \exp\Bigl( a (r+\sigma^2) + br \Bigr).
\label{a8}
\ee
\label{lem_a1}
\end{lem}

\begin{proof}
We have
\begin{eqnarray}
\EE S(a) S(b)
&=& \EE S(a)^2 e^{(b-a)(r-\sigma^2/2) + \sigma\left(B(b)-B(a)\right)}
\nonumber\\
&=& \EE S(a)^2 \EE e^{(b-a)(r-\sigma^2/2) + \sigma\sqrt{b-a} Z}\nonumber\\
&=& e^{(2r+\sigma^2) a} e^{(b-a)r}\nonumber\\
&=& e^{a(r+\sigma^2))} e^{br},
\end{eqnarray}
where $Z \sim N(0,1)$ and we have used \eqref{a4}.
\end{proof}

\begin{prop}
We have
\be
\EE S(T) A(T) = \exp[rT, (2r + \sigma^2)T].
\label{a9}
\ee
\end{prop}

\begin{proof}
Applying Lemma \ref{lem_a1}, we obtain
\begin{eqnarray*}
\EE S(T) A(T)
&=& T^{-1} \int_0^T \EE S(t) S(T)\,dt\\
&=& T^{-1} \int_0^T e^{(r+\sigma^2)t} e^{r T}\,dt\\
&=& \exp[rT, (2r+\sigma^2)T].
\label{a10}
\end{eqnarray*}
\end{proof}

\begin{prop}
\be
\EE (A(T)^2) = 2 \exp[0, rT, (2r + \sigma^2)T].
\ee
\end{prop}

\begin{proof}
We find
\begin{eqnarray}
\EE (A(T)^2)
&=& T^{-2} \int_0^T \Bigl( \int_0^T \EE S(t_1) S(t_2)\, dt_2 \Bigr)\,dt_1 \nonumber\\
&=& 2T^{-2} \int_0^T \Bigl( \int_0^{t_1} \EE S(t_1) S(t_2)\, dt_2 \Bigr)\,dt_1.
\end{eqnarray}
Thus
\begin{eqnarray}
\EE (A(T)^2)
&=& 2T^{-2} \int_0^T \Bigl( \int_0^{t_1} e^{r(t_1 + t_2)} e^{\sigma^2 t_2}\, dt_2 \Bigr)\,dt_1 \nonumber\\
&=& 2T^{-2} \int_0^T e^{rt_1}\Bigl(\frac{e^{(r+\sigma^2)t_1} - 1}{r+\sigma^2} \Bigr)\,dt_1 \nonumber\\
&=& \frac{2}{(r+\sigma^2)T} \left[ \exp[0,(2r+\sigma^2)T] - \exp[0,rT] \right]\nonumber\\
&=& 2 \exp[0, rT, (2r+\sigma^2)T],
\end{eqnarray}
using the divided difference recurrence relation \eqref{a7b} to obtain the
final line.
\end{proof}

\noindent
Any reader still doubtful of the simplification provided by divided difference notation
might consider the alternative expression provided in \citeasnoun{hull}:
\[
\EE \left(A(T)^2\right) =
\frac{2 e^{(2r+\sigma^2)T}}{(r+\sigma^2)(2r+\sigma^2)T^2} +
\frac{2}{rT^2}\left( \frac{1}{2r+\sigma^2} -
\frac{e^{rT}}{r+\sigma^2}\right).
\]
There is a similar divided difference relation for $\EE \left(A(T)^m\right)$,
described
in the next section, but we now complete our derivation of Theorem \ref{thm_corrcoeff}.

\begin{proof}[Proof of Theorem \ref{thm_corrcoeff}]
Applying (\ref{a5}, \ref{a6}, \ref{a9}) and \eqref{a7b}, we obtain
\begin{eqnarray}
\EE S(T) A(T) - \EE S(T) \EE A(T)
&=& \exp[rT,(2r+\sigma^2)T] - e^{rT}(e^{rT} - 1)/(rT)\nonumber\\
&=& \exp[rT,(2r+\sigma^2)T] - \exp[rT,2rT]\nonumber\\
&=& \sigma^2 T \exp[rT, 2rT, (2r+\sigma^2)T].
\label{a15}
\end{eqnarray}

Further,
\be
\var S(T)
= \EE(S(T)^2) - (\EE S(T))^2
= e^{(2r+\sigma^2)T} - e^{2rT}
= \sigma^2 T \exp[2rT, (2r+\sigma^2)T],
\label{a16}
\ee
and, by (\ref{a6}, \ref{a10}),
\begin{eqnarray}
\var A(T)
&=& 2\exp[0, rT, (2r+\sigma^2)T] - \left(\frac{e^{rT} - 1}{rT}\right)^2\nonumber\\
&=& 2\exp[0,rT,(2r+\sigma^2)T] - 2\exp[0,rT,2rT]\nonumber\\
&=& 2\sigma^2 T \exp[0,rT,2rT,(2r+\sigma^2)T],
\label{a17}
\end{eqnarray}
using the divided difference recurrence \eqref{a7b} once more.
Hence
\be
R = \frac{ \exp[rT, 2rT, (2r+\sigma^2)T] }
    { \sqrt{ 2\exp[2rT, (2r+\sigma^2)T] \exp[0, rT, 2rT, (2r+\sigma^2)T]} }.
\label{a18}
\ee
\end{proof}

It is remarkable that the divided differences appearing in (\ref{a18})
are coefficients of the cubic polynomial interpolating the exponential
function at $0, rT, 2rT, (2r+\sigma^2)T$. We make three further observations:

\begin{enumerate}
\item

Armed with
an analytic expression for the correlation coefficient, we can apply
the exchange option valuation formula of \citeasnoun{margrabe}
to derive the values of certain Asian
options, if we are willing to accept that the time--average is suitably
approximated by exponential Brownian motion. We are investigating
the numerics of this rather simple approximation at present
and preliminary results are surprisingly promising.

\item
The correlation coefficient $R(rT, \sigma^2 T)$ is typically
close to unity: typical values of $r$, $\sigma$ and $T$ produce
values of $R$ in the $0.8-0.9$ range. In fact, we are able to prove
that the correlation coefficient satisfies $R(rT, \sigma^2 T) \ge
1/\sqrt{2}$, for all $r \ge 0$, $\sigma \ge 0$ and $T > 0$,
a surprisingly high lower bound for the correlation
coefficient. The details of this derivation are too complicated to
include here, and we refer the reader to \citeasnoun{baxter_fretwell} for
further details. However, the numerical findings are summarised in
Figure~\ref{configs}, which displays values of the closely related
quantity
\[
S \equiv S(r,a) = \frac{\left(\exp[a,2r,r]\right)^2}{\exp[a,2r]
  \exp[a,2r,r,0]},
\]
for $-20 \le a \le 40$ and $0.1 \le r \le 10$. It is easily checked
that $R(rT, \sigma^2 T) = \sqrt{S(rT, (2r+\sigma^2)T)/2}$, so that the
lower bound $R \ge 1/\sqrt{2}$ becomes $S \ge 1$. It is plausible that
$S(r,a)$ should be a decreasing function of $a$, for fixed $r$,
because correlation should be a decreasing function of
volatility. Further, it
is not difficult to establish the limiting values $\lim_{a \to -\infty}
S(a,r) = 2$ and $\lim_{r\to\infty} S(a,r) = 1$. However, further
analysis is not straightforward, and the analysis of
\citeasnoun{baxter_fretwell} makes great use of properties of
divided differences.

\item
It is natural to ask whether these divided difference expressions are
particular to exponential Brownian motion. In fact, similar
expressions occur when exponential Brownian motion is replaced by
certain L\'evy-stable variants: see \citeasnoun{BCF} for further details.

\end{enumerate}

\begin{figure}[tb]
\vspace{6pt}

\includegraphics[scale=0.8]{asian1.eps}
\parbox{28.5pc}{\caption{$S(r,a)$ for $-20 \le a \le 40$ and $0.1 \le r
  \le 10$}\label{configs}}

\end{figure}

\section{Computing higher moments of $A(T)$}

We now demonstrate that the neat divided difference formulae obtained for
the first and second moments of $A(T)$ are {\em not} coincidences,
but part of a greater pattern from which arise new formulae generalising
the moment calculations of \citeasnoun{oshanin}, \citeasnoun{yor}
and \citeasnoun{yorbook}.

We begin with the iterated integral
\be
\EE A(T)^m
=
T^{-m} \int_0^T d\tau_m \int_0^T d\tau_{m-1} \cdots \int_0^T d\tau_1
\ \EE S(\tau_1) \cdots S(\tau_m).
\label{b3}
\ee
Now, given any point $(\tau_1, \ldots, \tau_m) \in [0,T]^m$,
let us sort its components into increasing order,
obtaining $(t_1, \ldots, t_n)$ (say). Then
\[
\EE S(\tau_1) \cdots S(\tau_m)
=
\EE S(t_1) \cdots S(t_m)
\]
and
\be
\EE A(T)^m
=
m! T^{-m}\int_0^T dt_m \int_0^{t_m} dt_{m-1} \cdots \int_0^{t_2} dt_1
\EE S(t_1) \cdots S(t_m).
\label{b4}
\ee
Our first task is to calculate the integrand, which we complete
after a simple lemma.

\begin{lem}
For any positive integer $k$, we have
\be
\EE \left[S(t)^k \right] = \exp \Bigl( krt + \frac{\sigma^2 t}{2} k(k-1)\Bigr).
\ee
\label{lem_b2}
\end{lem}

\begin{proof}
This is almost immediate from \eqref{a5}:
\[
\EE S(t)^k
= \EE e^{k(r-\sigma^2)t + \sigma k \sqrt{t} Z}
= e^{k(r-\sigma^2/2)t + \sigma^2 k^2 t/2}
= e^{krt + \sigma^2 t k(k-1)/2},
\]
where $Z \sim N(0,1)$.
\end{proof}

\begin{prop}
If $0 \le t_1 \le t_2 \le \cdots \le t_m$, then
\be
\EE S(t_1) S(t_2) \cdots S(t_m)
=
\exp \Bigl( \sum_{k=1}^m \left(r + (m-k)\sigma^2\right) t_k \Bigr).
\label{b5}
\ee
\label{prop_b3}
\end{prop}

\begin{proof} Lemma \ref{lem_a1} comprises the case $m=2$. We complete
the proof by induction on the number of terms $m$,
first observing that, by a standard property of
geometric Brownian motion,
\be
\EE S(t_1) S(t_2) \cdots S(t_m)
=
\EE S(t_1)^m \EE S(t_2 - t_1) \cdots S(t_m - t_1).
\label{b6}
\ee
Applying Lemma \ref{lem_b2} and our induction hypothesis, we obtain
\be
\EE S(t_1) S(t_2) \cdots S(t_m)
=
\exp\Bigl( mrt_1 + \sigma^2 t_1 m(m-1)/2
+ \sum_{\ell=2}^m
\left( r + (m-\ell)\sigma^2\right) \left(t_\ell - t_1\right)\Bigr).
\label{b7}
\ee
The $t_1$ coefficient in the exponent is given by
\[
mr - (m-1)r + \sigma^2 t_1 \left( \frac{1}{2} m(m-1) -
\sum_{\ell=1}^{m-2}\ell \right)
= r + \sigma^2 t_1 (m-1),
\]
using the elementary fact that $m(m-1)/2 = 1 + 2 + \cdots + m-1$.
The coefficients of $t_2, \ldots, t_m$ are as already stated in \eqref{b5}.
\end{proof}

Thus the desired integral \eqref{b4} becomes
\begin{eqnarray}
\EE A(T)^m
&=& m! T^{-m}
\int_0^T dt_m \int_0^{t_m} dt_{m-1} \cdots \int_0^{t_2} dt_1
\EE S(t_1) \cdots S(t_m)\nonumber\\
&=&
m! \int_0^1 dt_m \int_0^{t_{m-1}} \cdots \int_0^{t_2} dt_1
\exp(\alpha_1 t_1 + \cdots \alpha_m t_m),
\label{b8}
\end{eqnarray}
where
\be
\alpha_k = \left(r + (m-k)\sigma^2 \right) T, \qquad k = 1, \ldots,
m.
\label{b9}
\ee

The integral displayed in \eqref{b8} can now be identified as a divided
difference using a variant form of the Hermite--Genocchi
integral relation.

\begin{thm}
Let
\be
b_k := k r + \sigma^2 k(k-1)/2, \qquad k = 0, 1, \ldots.
\label{b1}
\ee
Then
\be
\EE (A(T))^m
=
m! \exp[b_0 T, b_1 T, \ldots, b_m T], \qquad m \ge 0.
\label{b2}
\ee
\label{thm_b1}
\end{thm}

\begin{proof}
Apply Corollary \ref{dcor4} to \eqref{b8} and \eqref{b9}, using
$\sum_{k=1}^j k = j(j+1)/2$.
\end{proof}

The statement of Theorem \ref{thm_b1} simplifies when
$r = \sigma^2$, for then the drift term in \eqref{a1} vanishes, that is,
we consider $S(t) = \exp(\sigma \sqrt{t} B(t))$ alone; this
is the special case studied by \citeasnoun{oshanin} and
\citeasnoun{yor}, for the formulae grow {\em much} more complicated
without the use of divided differences.
Therefore we now demonstrate that our expression
agrees with theirs.

\begin{thm}
If we set $r = \sigma^2/2$ in Theorem \ref{thm_b1}, then we obtain
\begin{align}
\EE \left[ A(T)^m \right]
&= m! \exp[0, rT, 2^2 rT, 3^2 rT, \ldots, m^2 rT]\nonumber\\
&= m! H_{\sqrt{rT}}[-m, \ldots, -1, 0, 1, \ldots, m],
\end{align}
where $H_{c}(x) := \exp(c^2 x^2)$, $x \in \RR$, for any positive $c$.
\label{thm_b2}
\end{thm}

\begin{proof}
We simply set $r = \sigma^2$ in Theorem \ref{thm_b1} and apply \eqref{dda0}.
\end{proof}

We can now apply Corollary \ref{dcor7} to derive the formula given in equation (14)
of \citeasnoun{oshanin}.

\begin{thm}
If we set $r= \sigma^2/2$, then
\be
\EE \left[A(T)^m \right]
=
\left( \frac{\Gamma(m)}{\Gamma(2m)}\right)
r^{-m} \left( -\frac{1}{2} (-1)^m {2m \choose m}
+ \sum_{\ell=0}^m {2m \choose \ell} (-1)^{\ell} e^{rT(m - \ell)^2} \right).
\label{osh1}
\ee
\end{thm}

\begin{proof}
Applying Corollary \ref{dcor7} to Theorem \ref{thm_b2}, we obtain
\begin{align}
\EE \left[A(T)^m\right]
&= \left( \frac{m!}{(2m)!} (rT)^{-m} \sum_{k=0}^{2m} {2m \choose k}
(-1)^k e^{rT(k-m)^2}\right) \nonumber\\
&=
\left( \frac{\Gamma(m)}{\Gamma(2m)}\right)
(rT)^{-m} \left( -\frac{1}{2} (-1)^m {2m \choose m}
+ \sum_{\ell=0}^m {2m \choose \ell} (-1)^{\ell} e^{rT(m - \ell)^2} \right),
\end{align}
after some straightforward algebraic manipulation.
\end{proof}

If we now replace $rT$ by $\alpha$ and $m$ by $j$ in \eqref{osh1}, then
we obtain equation (14) of \citeasnoun{oshanin}.

\section{Divided difference theory}
\label{divdiffsec}
Most of the properties of divided differences required here
can be found in Chapter 5 of \citeasnoun{powell}.
However,
proofs of the Hermite--Genocchi integral relation are
less easily available in the Anglophone mathematical literature, as is our
particular variant of it, although the specialist can find
much useful material in the treatise of \citeasnoun{lorentz}.
We have therefore provided a derivation for the convenience of the reader.
The Hermite--Genocchi formula and its consequences are
still very much topics of current research; see, for example,
\citeasnoun{waldron}.
Furthermore, the result is better served in other European languages; see,
for instance, \citeasnoun{gelfond} for a French translation of a
Russian classic,
or indeed the original \citeasnoun{hermite}.

We recall the {\em divided difference recurrence relation}.

\begin{thm}
\be
f[a_0, a_1, \ldots, a_n]
=
\frac{f[a_1, \ldots, a_n] - f[a_0, \ldots, a_{n-1}]}{a_n - a_0},
\label{a7b}
\ee
for any distinct complex numbers $a_0, \ldots, a_n$.
\end{thm}

\begin{proof}
See, for instance, \citeasnoun{powell}, Theorem 5.3.
\end{proof}

If $f$ is sufficiently differentiable, then we can, of course, define
divided differences for
coincident points. Further, the elementary relation
\be
f[a_0, a_1]
= \frac{f(a_1) - f(a_0)}{a_1 - a_0}
= \int_0^1 f^\prime((1-t)a_0 + ta_1)\,dt, \qquad\hbox{ when } a_0, a_1 \in \RR,
\label{dd1}
\ee
can be generalised to obtain the {\em Hermite--Genocchi formula}.

\begin{thm}[Hermite--Genocchi]
Let $f \in C^{(n)}(\RR)$ and let $a_0, a_1, \ldots, a_n$ be (not
necessarily distinct) real numbers
Then, for $n \ge 1$,
\begin{eqnarray}
\lefteqn{f[a_0, a_1, \ldots, a_n] }\nonumber \\
&=&
\int_{S_n} f^{(n)}(t_0 a_0 + t_1 a_1 + \cdots + t_n a_n)\,dt_1 \cdots
dt_n,\nonumber\\
&=& \int_0^1 dt_1 \int_0^{1-t_1} dt_2 \cdots
\int_0^{1 - \sum_{k=1}^{n-1}t_k} dt_n
f^{(n)}(t_0 a_0 + t_1 a_1 + \cdots + t_n a_n)
\label{hg1}
\end{eqnarray}
where the domain of integration is the simplex
\be
S_n = \left\{ t = (t_1, t_2, \ldots, t_n) \in \RR_+^n \colon
\sum_{k=1}^n t_k \le 1\right\}
\label{hg2}
\ee
and
\[
t_0 = 1 - \sum_{k=1}^n t_k.
\]
\end{thm}

\begin{proof}
We shall prove (\ref{hg1}) by induction on $n$, observing that
\[
\int_{S_1} f^\prime(t_0 a_0 + t_1 a_1)\,dt_1
=
\int_0^1 f^\prime(a_0 + t_1 (a_1 - a_0))\,dt_1
= \frac{f(a_1) - f(a_0)}{a_1 - a_0} = f[a_0, a_1].
\]
To extend the formula to higher-order divided differences, we
note that
\be
f[a_0, a_1, \ldots, a_n, a_{n+1}]
=
\frac{f[a_1, a_2, \ldots, a_{n+1}] - f[a_0, a_1, \ldots, a_n]}{a_{n+1}
- a_0}
= g[a_0, a_{n+1}],
\label{hg3}
\ee
where
\be
g(x) = f[a_1, \ldots, a_n, x], \qquad x \in \RR.
\label{hg4}
\ee
Now
\[
g(x) = \int_{S_n} f^{(n)}(xt_0 + a_1 t_1 + \cdots + a_n t_n) \,dt_1
\cdots dt_n
\]
so that
\[
g^\prime(x) = \int_{S_n} t_0 f^{(n+1)}(xt_0 + a_1 t_1 + \cdots + a_n
t_n)\,dt_1 \cdots dt_n.
\]
Therefore
\begin{eqnarray*}
\lefteqn{f[a_0, a_1, \ldots, a_n, a_{n+1}]}\\
&=& \int_0^1 d\tau\ g^\prime( (1-\tau) a_0 + \tau a_{n+1} )\\
&=& \int_0^1 d\tau \int_{S_n} dt_1 \cdots dt_n\ t_0 f^{(n+1)}([(1-\tau)a_0
+ \tau a_{n+1}]t_0 + a_1 t_1 + \cdots a_n t_n)\\
&=& \int_{S_n} dt_1 \cdots dt_n \int_0^1 d\tau\ t_0
f^{(n+1)}([(1-\tau)t_0 a_0 + \sum_{\ell=1}^n a_\ell t_\ell + \tau t_0
a_{n+1})\\
&=& \int_0^1 dt_1 \int_0^{1-t_1} dt_2 \cdots
\int_0^{1-\sum_{k=1}^{n+1}t_k}
dt_{n+1} f^{(n+1)}\left(T_0 a_0 + \sum_{k=1}^{n+1} t_k a_k\right)\\
&=& \int_{S_{n+1}} f^{(n+1)}\left(T_0 a_0 + t_1 a_1 + \cdots + t_{n+1}
a_{n+1}\right) \,dt_1 \cdots dt_{n+1},\\
\end{eqnarray*}
where we have used the substitution $t_{n+1} = t_0 \tau$ and the
notation $T_0 = 1 - \sum_{k=1}^{n+1} t_k$.
\end{proof}

We shall need a variant form of the Hermite--Genocchi integral
relation for which the following notation is useful. Given
any real $n \times n$ nonsingular matrix $V$, with columns $v_1,
\ldots, v_n$, we let $K(V)$ denote
the closed convex hull of
$0, v_1, \ldots, v_n$, i.e.
\[
K(V) := \conv\{0, v_1, \ldots, v_n\}.
\]
In this notation, the Hermite--Gnocchi integral relation states that
\be
f[a_0, a_1, \ldots, a_n]
=
\int_{K(I_n)} f^{(n)}\left(a_0 + \left(a - a_0 e\right)^T
y\right)\,dy,
\ee
where
\[
a = \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix}
,\qquad
e = \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix},
\]
and $I_n$ denotes the $n \times n$ identity matrix.
Integrating the $n$th derivative over the simplex $K(V)$ yields
a useful variant form of Hermite--Genocchi.

\begin{thm} Let $V \in \RR^{n \times n}$ be any nonsingular matrix.
Then
\be
\frac{1}{\left|\det V\right|}
\int_{K(V)} f^{(n)}\left(a^T y\right)\,dy
=
f[0, (V^T a)_1, \ldots, (V^T a)_n],
\ee
where $(V^T a)_k$ denotes the $k$th component of the vector $V^T a$.
\label{dthm2}\end{thm}

\begin{proof}
Substituting $y = Vz$, Hermite--Genocchi implies the relation
\[
\int_{K(V)} f^{(n)}\left((V^T a)^T z\right)\,dz
=
f[0, (V^T a)_1, \ldots, (V^T a)_n].
\]
\end{proof}

\begin{cor}
For any function $f \in C^{(n)}(\RR)$, we have
\begin{align}
&\int_0^1 dx_n \int_0^{x_n} dx_{n-1} \cdots \int_0^{x_2} dx_1
f^{(n)} \left(\sum_{k=1}^n a_k x_k\right)\nonumber\\
&\qquad =
f[0, a_n, a_n + a_{n-1}, \ldots, a_n + a_{n-1} + \cdots + a_1].
\end{align}
\label{dcor3}
\end{cor}

\begin{proof}
Set
\[
V =
\begin{pmatrix}
1 & & & \\
1 & 1 & & \\
\vdots & & \ddots & \\
1 & 1 & \cdots & 1
\end{pmatrix}
\]
in Theorem \ref{dthm2}.
\end{proof}

The exponential function is a
particularly important case for us,
in which case the Hermite--Genocchi formula becomes
\be
\exp[a_0, a_1, \ldots, a_n] =
\int_{S_n} e^{t_0 a_0 + t_1 a_1 + \cdots + t_n a_n}\,dt_1 \cdots dt_n
\label{a7c}
\ee
and Corollary \ref{dcor3} takes the following form.

\begin{cor}
We have
\begin{align}
&\int_0^1 dx_n \int_0^{x_n} dx_{n-1} \cdots \int_0^{x_2} dx_1
\exp \left(\sum_{k=1}^n a_k x_k\right)\nonumber\\
&\qquad =
\exp[0, a_n, a_n + a_{n-1}, \ldots, a_n + a_{n-1} + \cdots + a_1].
\label{a7ca}
\end{align}
\label{dcor4}
\end{cor}

\begin{proof}
Let $f$ be the exponential function in Corollary \ref{dcor3}.
\end{proof}

\noindent
Further, we note that, for the exponential function, Theorem \ref{dthm2}
becomes the interesting formula
\be
\frac{1}{\left|\det V\right|}
\int_{K(V)} e^{a^T y}\,dy
=
\exp[0, (V^T a)_1, \ldots, (V^T a)_n].
\ee
Thus, integrating exponentials over simplexes or, more generally, a
polyhedron formed by the disjoint union of simplexes, will generate
divided differences of the exponential.

We shall also
need two simple preliminary results. Let us use $\PP_n$ to denote
the vector space of polynomials of degree $n$.

\begin{lem} We have
\be
\exp(\mu) \exp[\lambda_0, \ldots, \lambda_m]
= \exp[\lambda_0 + \mu, \ldots, \lambda_m + \mu],
\label{a7d}
\ee
where $\lambda_0, \ldots, \lambda_m$ and $\mu$ can be any complex
numbers.
\end{lem}

\begin{proof}
Immediate.
\end{proof}

\begin{lem}
Let $f \colon \CC \to \CC$ and let $a_1, \ldots, a_n$ be distinct
nonzero complex numbers. Then
\be
f[0, a_1^2, \ldots, a_n^2]
= g[-a_n, \ldots, -a_1, 0, a_1, \ldots, a_n],
\label{dda0}
\ee
where $g(z) = f(z^2)$, for $z \in \CC$.
\end{lem}

\begin{proof}
Let $p \in \PP_n$ interpolate $f$ at $0, a_1^2, \ldots, a_n^2$.
Then $q(z) := p(z^2)$ is a polynomial of degree $2n$ satisfying
$q(\pm a_j) = p(a_j^2) = f(a_j^2) = g(\pm a_j)$, for $j=0, \ldots, n$,
setting $a_0 = 0$, for convenience. The result then follows from uniqueness
of the interpolating polynomial.

\end{proof}

It is well-known that a divided difference at equally spaced points
can be expressed in a particularly simple form using the forward difference
operator
\[
\Delta_h f(x) := f(x+h) - f(x),
\]
which we shall need when
demonstrating the equivalence between our moment calculations
and those of \citeasnoun{oshanin} and \citeasnoun{yor}.
The next proposition is well-known, but we again include
its short proof for the reader's convenience.

\begin{prop} Let $f \colon \RR \to \RR$, let $h$ be any positive
constant and let $n$ be a non-negative integer. Then
\be
f[x, x+h, x+2h, \ldots, x + nh]
= \frac{\Delta_h^n f(x)}{n! h^n}.
\label{dda1}
\ee
\label{dprop5}
\end{prop}

\begin{proof}
It is easily checked that $f[x, x+h] = \Delta_h f(x) / h$. Further,
if we assume \eqref{dda1} for $n-1$, then
the divided difference recurrence relation implies that
\begin{align*}
&f[x, x+h, \ldots, x+nh]\\
&= \frac{f[x+h, \ldots, x+nh] - f[x, x+h, \ldots, x+(n-1)h]}{nh}\\
&= \frac{\Delta_h f[x, \ldots, x+(n-1)h]}{nh}\\
&= \frac{1}{nh} \Delta_h \left( \frac{\Delta_h^{n-1} f(x)}{(n-1)! h^{n-1}}\right)\\
&= \frac{\Delta_h^n f(x)}{n! h^n}.
\end{align*}
Thus the result follows by induction.
\end{proof}

\begin{cor}Let $f \colon \RR \to \RR$ and let $h$ be any positive
constant. Then
\be
f[x, x+h, x+2h, \ldots, x + nh]
= \frac{1}{n! h^n}\sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x + kh).
\label{dda2}
\ee
\label{dcor6}
\end{cor}

\begin{proof}
We define the {\em forward shift} operator
\[
E_h f(x) := f(x+h), \qquad x \in \RR,
\]
and observe
that, by the binomial theorem,
\[
\Delta_h^n f(x) = \left(E_h - 1\right)^n f(x)
= \sum_{k=0}^n {n \choose k} (-1)^{n-k} E_h^k f(x)
= \sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x + kh).
\]
\end{proof}

\begin{cor}
Let $f \colon \RR \to \RR$ and let $h$ be any positive number.
Then
\be
f[-nh, -(n-1)h, \ldots, -h, 0, h, \ldots, nh]
=
\frac{1}{(2n)! h^{2n}} \sum_{k=0}^{2n} {2n \choose k} (-1)^k f((k-n)h).
\label{a7e}
\ee
\label{dcor7}
\end{cor}

\begin{proof}
This is an immediate consequence of Corollary \ref{dcor6}.
\end{proof}

We shall also need the {\em Leibniz} relation for divided differences
of a product when deriving the recurrence differential equation
for moments.

\begin{thm}[Leibniz] Let $D$ be any subset of $\CC$ containing the distinct points
$z_0, z_1, \ldots, z_n$ and let $v$ and $w$ be complex-valued functions on $D$.
If $u = v \cdot w$, then
\be
u[z_0, \ldots, z_n] = \sum_{k=0}^n v[z_0, \ldots, z_k] w[z_k, \ldots, z_n].
\label{r7}
\ee
\label{dcor9}
\end{thm}

\begin{proof}
Let $p \in \PP_n$ be the unique polynomial interpolant for $u$
written in standard Newton form, that is,
\be
p(z) = v[z_0] + v[z_0, z_1](z - z_0) +
\cdots v[z_0, z_1, \ldots, z_n] (z - z_0) \cdots (z - z_{n-1}).
\label{r8}
\ee
We shall let $q \in \PP_n$ be the unique polynomial interpolating $w$, but with
the points chosen in the order $z_n, z_{n-1}, \ldots, z_0$, that is,
\be
q(z) = w[z_n] + w[z_n, z_{n-1}](z - z_n) + \cdots
+ w[z_n, \ldots, z_0] (z - z_n) \cdots (z - z_1).
\label{r9}
\ee
Now their product $p \cdot q$ is a polynomial of degree $2n$. Dividing this
polynomial by $(z - z_0) \cdots (z - z_n)$, we obtain
\[
p(z) q(z) = r(z) + s(z) (z-z_0) \cdots (z-z_n),
\]
where $r \in \PP_n$. We see that $u(z_j) = v(z_j) w(z_j) = p(z_j) q(z_j) = r(z_j)$,
for $0 \le j \le n$. Hence, by uniqueness of the polynomial interpolant
for $u$ in $\PP_n$, we obtain
\be
r(z) = u[z_0] + \cdots + u[z_0, \ldots, z_n] (z - z_0) \cdots (z - z_n).
\label{r10}
\ee
We obtain \eqref{r7} by equating the coefficients of $z^n$
in \eqref{r10} and the product of the
expressions in \eqref{r8} and \eqref{r9}, modulo $(z-z_0) \cdots (z-z_n)$.
\end{proof}

\section{A recurrence relation}

The Feynman--Kac formula (see, for example, \citeasnoun{karatzas})
suggests that the moments $E_n(t) := \EE \left( A(t)^n \right)$ of the
time average should satisfy a certain differential equation,
which we shall also obtain as an illustration of the divided
difference approach.

\begin{thm}
Let $\{c_n\}_{n=1}^\infty$ be any strictly increasing sequence of
positive numbers and define $e_n : (0,\infty) \to \RR$ by the divided
difference
\be
e_n(t) = \exp[0, c_1 t , \ldots, c_n t], \qquad t > 0, \quad n \ge 0.
\label{r1}
\ee
Then
\be
t e_n^\prime(t) = e_n(t) \left( c_n t - n\right) + e_{n-1}(t),\qquad\hbox{ for } n \ge 1.
\label{r2}
\ee
\label{thm51}
\end{thm}

\begin{proof}
Applying the Hermite--Genocchi formula, we obtain
\be
e_n(t)
=
\int_{K(I_n)} \exp\left(t c^T y\right)\,dy,
\label{r3}
\ee
where $b = \left(c_1, \ldots, c_n\right)^T$, and differentiating \eqref{r3} yields
\be
e_n^\prime(t) = \int_{K(I_n)} \exp(t c^T y) (c^T y)\,dy.
\ee
Now writing $g(s) = s$ and applying Leibniz's formula for divided
differences, we find
\begin{align}
\left(g \cdot \exp\right)[0, c_1 t , \ldots, c_n t]
&= g[0] \exp[0, c_1 t, \ldots, c_n t] + g[0, c_1 t] \exp[c_1 t,
\ldots, c_n t]\nonumber\\
&= \exp[c_1 t, \ldots, c_n t].
\label{r4}
\end{align}
Further, the relation $(g\cdot\exp)^{(n)} = g \cdot\exp + n\exp$ and \eqref{r4} imply
\begin{align}
t e_n^\prime(t)
&= \int_{K(I_n)} \left(g\cdot \exp\right)^{(n)}(t c^T y)\,dy
- n \int_{K(I_n)} \exp(tc^T y)\,dy\nonumber\\
&= \left(g \cdot \exp\right)[0, c_1 t, \ldots, c_n t] -
n \exp[0, c_1 t, \ldots, c_n t]\nonumber\\
&= \exp[c_1 t, \ldots, c_n t] - n e_n(t).
\label{r5}
\end{align}
However,
\be
e_n(t) = \frac{\exp[c_1 t, \ldots, c_n t] - e_{n-1}(t)}{c_n t},
\ee
by the divided difference recurrence relation, so that
\be
\exp[c_1 t, \ldots, c_n t]
= c_n t e_n(t) + e_{n-1}(t).
\label{r6}
\ee
Substituting \eqref{r6} in \eqref{r5} provides \eqref{r2}.
\end{proof}

\noindent
The corresponding differential equation for $E_n$ is now immediate.

\begin{cor} The moments satisfy
\be
t E_n^\prime(t) = E_n(t) \left(b_n t - n\right) + E_{n-1}(t), \qquad
\hbox{ for } n \ge 1,
\ee
where $b_n$ is given by \eqref{b1}.
\end{cor}

\begin{proof}
We apply Theorem \ref{thm51} and Theorem \ref{thm_b1}.
\end{proof}

\bibliographystyle{actaagsm}
\bibliography{asian}

\end{document}

config: arxiv


TITLE: Why is visible light observed as confined to its source?
QUESTION [3 upvotes]: When I observe a visible light source, like the sun or a light bulb, why do I observe the light source as a confined object? Like why is the sun or a bulb or whatever seen as a confined ball of glowing light? Shouldn’t I Just see beams of light everywhere? Like a car passes you at night and you can see it’s head lamps as confined bright glowing things. You can see what those lamps illuminate but you don’t see anything in between. Why? I understand that the photons have to hit an object and be re-emitted and then hit your eye for you to see an object. But when I look at a visible light source I see that source as a confined glowing object. Why is it confined? Like why are glowing things able to be seen as a confined glowing thing? Like let’s change the source to fire - why do I see the flame as a confined luminous thing? If the plasma of the fire is emitting visible light why do I see it as a confined thing?! Also I am worried I can’t actually explain what I am wanting to know. So help clarifying is welcomed.
EDIT
Okay I forgot my login information but I need more assistance from this wonderful community, please if I may? I appreciate all the answers and they all make sense but I think what I was attempting to ask was -
Do photons somehow carry information. Just because a photon enters my pinhole retina doesn’t explain WHY my brain knows to construct an image from it in such a way as to make a thing appear a certain side or shape. Also if photons are the reason I see other things via refraction or what have you, it doesn’t explain why I can see their source if they’re not refracting off of anything. Or are they? Perhaps the atmosphere of the sun is the point of refraction? Or the glass of a light bulb or the plasma gas if a fire?  How can a photon show me it’s sources as a glowing thing, also show me the tree and remain invisible as it propagates. Is this because my brain only presents me an edited version of reality? How does it do that? Photons then must be some type of information packet. Is there a measurement of how much information a photon can store? Is any of this making sense to anyone? This is why I was saying it’s kind of a abstract question - I hope I’ve made the question more clear. Any book recommendations I can read that may answer these types of questions are gladly accepted, even if it may be out of my depth I would still appreciate anything from anyone. Thank you. I apologize in advance if this post is a violation of the proper guidelines for posting, I lost my login information and hoped I’d use Google to sign in previously- if I need to repost a new topic or question please let me know?

REPLY [0 votes]: Regarding the question: does a photon contain information? The answer is no. Foregoing polarization, when you observed a photon, it has 3 pieces of information as encoded in its wave vector:
$$ k^{\mu}=(\omega/c, \vec k) $$
with the constraint:
$$k^{\mu}k_{\mu}\equiv \frac{\omega^2}{c^2}-||\vec k||^2=0 $$
Since your frame of reference isn't special, any Lorentz transform of that photon:
$$k^{\mu'}=\Lambda^{\mu}_{\ \nu}k^{\nu}$$
is equally valid, and with that transform, you can make pretty much any frequency or direction you want.
Now there will be objections: but there is a natural rest frame, the frame of the source. This is human bias creeping in. Once it is emitted, the source is irrelevant. Any statement about the source is a physical model that may or may not be applicable. Moreover, thanks to Doppler broadening and inherent line widths, you can never know the rest frame of the parent atom (say if it's an apparent Balmer line photon) exactly. You can never know if that one photon is a signal photon, or a background photon--from a different source, that has scattered into your detector.
Now with many photons you can form an image of the source and get some idea (an image, even), but that information is not in a single photon.


TITLE: Trivial representation in Clebsch-Gordan decomposition
QUESTION [1 upvotes]: My professor defined the Clebsch-Gordan series as the direct sum decomposition of the tensor product of two representations of the Lie group SU(2):
$$
D_{j_1} \otimes D_{j_2} = D_{j_1+j_2} \oplus D_{j_1+j_2-1} \oplus ... \oplus D_{|j_1-j_2|}
$$
I think it's an interesting fact that the trivial representation $D_0$ will be in the tensor product if and only if $j_1=j_2$.
Is there an intuitive explanation for that? What common property of all systems with $j_1=j_2$ leads to the trivial representation being part of the tensor product?
This question could be generalized to a similar fact about $D_{1/2}$ and $D_1$.

REPLY [1 votes]: Yes.  To obtain a scalar (or the trivial representation) one must multiply a representation $D^{\lambda}$ by its conjugate $D^{\lambda^*}$: the weights in the conjugate representation $\lambda^*$ are the negative of those in $\lambda$, and the scalar occurs when combining conjugate functions, so,as to produce a final function with weight $0$.
In $SU(2)$ all representations are self conjugate, so $\lambda^*$ is equivalent to $\lambda$, and indeed the weights in $\lambda$ runs from $-\lambda$ to $\lambda$, so that any weight and its negative are in the representation.  This means that, to get a scalar, you need to have $\lambda_1=\lambda_2$.
In other groups, v.g. $SU(3)$, not all irreps are self-conjugate.  To get a scalar one must then combine two properly conjugate irreps, such as $(1,0)$ and $(0,1)$.  Indeed $(1,0)\otimes (0,1)=(0,0)\oplus (1,1)$ etc.


TITLE: regular homotopy
QUESTION [6 upvotes]: Hello.  I am trying to give a seminar in my University about the Whitney-Graustein Theorem. There are many elementary proofs for that including Whitney's paper. The conclusion is that the  connected components ($π_0$)  of regular immersions  $S^1 \rightarrow R^2$  are equal to $Z$ (mod regular homotopies). Is there an elementary way to find the fundamental group of the space of immersions ?
There are many books and papers that treat fundamental group of mapping spaces including Smale's,Michor's etc, but they are far from elementary and the audience are undergraduates.
Any idea would be much appreciated

REPLY [3 votes]: See theorem 2.10 (with elementary proof) for the case of rotation idex $\ne 0$ of the paper:
Peter W. Michor; David Mumford: Riemannian geometries on spaces of plane curves. J. Eur. Math. Soc. (JEMS) 8 (2006), 1-48. pdf
For rotation index $=0$ (with a somewhat surprising answer) see the paper:
Hiroki Kodama, Peter W. Michor: The homotopy type of the space of degree 0 immersed curves. Revista Matemática Complutense 19 (2006), no. 1, 227-234. pdf


TITLE: About a problem on Chebyshev's inequality
QUESTION [2 upvotes]: Regarding a solved problem from one Book from Sheldon Ross as below:
Problem: Suppose that it is known that the number of items produced in a factory
during a week is a random variable with mean 50
b)If the variance of a week’s production is known to equal 25, then what can
be said about the probability that this week’s production will be between
40 and 60?
The solution is as mentioned below:
By Chebyshev’s inequality
$$P\{\lvert X - 50 \rvert \ge 10\} \le \frac {\sigma^2} {10^2} = \frac {1}{4} $$
Hence
$$P\{\lvert X - 50 \rvert \lt 10\} \ge 1-\frac{1}{4} = \frac {3}{4} $$
and so the probability that this week’s production will be between 40 and 60 is at
least .75
Assuming Chebyshev's inequality as:
$$P\{\lvert X - \mu \rvert \ge k\} \le \frac {\sigma^2} {k^2} $$
What I am unable to understand that why we took k as 10 ? also How above result comes for between 40 and 60?
Thank You

REPLY [0 votes]: So, I can solve like this:
in $|X| \lt k$ If we take k = 10 we have
$|X| \lt 10 \Rightarrow X \in (-10,10) \Rightarrow -10 \lt X \lt 10$
$ \Rightarrow 50-10 \lt 50-X \lt 50+10 \Rightarrow 40 \lt 50-X \lt 60$
Now
$P\{\lvert X - 50 \rvert \ge 10\} \le \frac {1}{4}$ for week's production below 40(including) and above 60(including)
$ P\{\lvert X - 50 \rvert \lt 10\} \ge  \frac {3}{4}$ for week's production above 40(excluding) and below 60(excluding)
Please correct me if needed. Thanks


TITLE: Generate recurrence relation for a hyperbolic equation
QUESTION [1 upvotes]: I want to generate the recurrence relation for the integer solution of the equation 3m² - 2n² = 1 ; I'm a tenth grader, and so it took me pretty long to at first get out of the normal Quadratic Formula and stuff and realize that there exists things like Cayley-Hamilton Theorem, but unfortunately, I'm inexperienced enough to even try that !! I used Diophantine solving methods, manipulating it but end up messing with the equation ... With reference to Ryan's Generating Integer solution from Hyperbolic Equation , I'd appreciate if one can explain Will Jagy's solution and how he arrived at the recurrence xn+2 =  6xn+1 - xn

REPLY [0 votes]: The equation is the same as
$$(3m)^2-6n^2=3$$
which in effect is the same as
$$r^2-6n^2=3$$
as each solution of this has $3\mid r$.
That's the same as
$$(r+n\sqrt6)(r-n\sqrt6)=3.$$
Now
$$(5+2\sqrt6)(5-2\sqrt6)=1.$$
If
$$r'+n'\sqrt6=(5+2\sqrt6)(r+n\sqrt6)$$
then
$$r'-n'\sqrt6=(5-2\sqrt6)(r-n\sqrt6)$$
which leads to
$$r'^2-6n'^2=(r'+n'\sqrt6)(r'-n'\sqrt6)=(5+2\sqrt6)(r+n\sqrt6)
(5-2\sqrt6)(r-n\sqrt6)=3.$$
Then $r'=5r+12n$ and $n'=2r+5n$. If we let $m'=r'/3=5m+4n$
then $n'=6m+5n$ and
$$3m'^2-2n'^2=1.$$
So we can start with $(m_0,n_0)=(1,1)$ and then
recursively define $$(m_{k+1},n_{k+1})=(5m_k+4n_k,6m_k+5n_k).$$
Then
$$m_{k+2}=5m_{k+1}+4n_{k+1}=5m_{k+1}+24m_k+20n_k=10m_{k+1}-m_k$$
and similarly for $n_k$.

REPLY [0 votes]: I would expect you to do better with Conway's topograph method. Everything involved here can be done without actual matrices, including the recursion.
I guess I will put some books, including a very good new one, CONWAY and HATCHER. There is also (I bought a copy) a well illustrated new one by WEISSMAN
This time it is
$$ x_{n+2} = 10 x_{n+1} - x_n \; \; , $$
$$ y_{n+2} = 10 y_{n+1} - y_n \; \; . $$
These come from the combined one-step rule
$$ (x_{n+1}, y_{n+1}) = (5 x_n + 4 y_n \; , \;  6 x_n + 5 y_n)  $$
which you get pretty quickly with Conway. Here is a fairly basic version of the topograph for $3x^2 - 2 y^2,$ showing several locations with $3 x^2 - y^2 = 1$ labelled with the appropriate $\left( \begin{array}{c} x \\ y \end{array} \right)$ in green

Then the separation into two rules can be done without matrices, I wrote that out at http://math.stackexchange.com/questions/1786760/recursive-system-solution/1786850#1786850
Mon Apr  2 10:34:50 PDT 2018
 x:  1   y:  1
 x:  9   y:  11
 x:  89   y:  109
 x:  881   y:  1079
 x:  8721   y:  10681
Mon Apr  2 10:34:53 PDT 2018


TITLE: Does tautological line bundle $\mathcal{O}(-1)$ over complex projective space have zero section?
QUESTION [2 upvotes]: In Complex Geometry written by Huybrechts, it defines the tautological line bundle $\mathcal{O}(-1)$ as followed
$$ \mathcal{O}(-1):=\{(\ell,z)\in \mathbb{C}P^n \times \mathbb{C}^{n+1}: z\in \ell\} $$
and the projection map $\pi:(\ell,z)\mapsto \ell$, then I think for a standard open covering $\{U_i\}_{i=0}^n$ of $\mathbb{C}P^n$ where
$$ U_i:=\{ (z_0:\cdots:z_n): z_i\neq 0 \} $$
then $\pi^{-1}(U_i)\cong U_i \times \mathbb{C}^* $ where $\mathbb{C}^*=\mathbb{C}\backslash\{0\}$, then there is no zero in each fiber $\pi^{-1}(\ell)$, that is $\mathcal{O}(-1)$ is not a line bundle. So where am i wrong?

REPLY [2 votes]: The fiber $\pi^{-1}(\ell)\subset \mathcal{O}(-1)$ above $\ell \in \Bbb CP^n$ is by definition $\{\ell\}\times \ell \simeq \ell$, which obviously has an origin $0$: it is the origin of $\Bbb C^{n+1}$. The zero section is just the map $\ell \in \Bbb CP^n \mapsto (\ell,0)\in \mathcal{O}(-1)\subset \Bbb CP^n \times \Bbb C^{n+1}$.


TITLE: Under what circumstances do symmetries in polar graphs hold?
QUESTION [0 upvotes]: It’s common knowledge that when dealing with polar graphs if you can replace r with -r and θ with -θ then the graph should be symmetrical about θ=pi/2.
However, when drawing r=θ/2 it seems this doesn’t hold true.
Are there specific criteria that need to hold for the standard 3 symmetry tests to hold? Also under what circumstances are the symmetries reflections or rotations?
Thanks in advance.

REPLY [0 votes]: The 3 symmetry tests are necessary and sufficient conditions (in fact, definitions) on any set "closed under taking negatives." That is, if $\theta$ is in the domain, then $-\theta$ should be too. For example, this includes sets of the form $(-a, a)$, and the whole real line. If, for some angle $\theta_0$ in the domain of your function, the opposite angle $-\theta_0$ is not in the domain, then the conditions of the symmetry test don't even make sense, since $r(-\theta)$ isn't defined.
The function $r = \theta/2$ is symmetric about the line $\theta = \pi / 2$ as long as whenever you plot $r(\theta)$ you also plot $r(-\theta)$. If you plot it on $[0, a]$ for some real number $a$, you will notice that this symmetry does not exist.
As for the second question, each symmetry test deals with a specific type of symmetry and I will restate them here.
Let $r = f(\theta)$ be a function $\mathbb{R} \to \mathbb{R}$.

If, for each $\theta$,  $r(\theta) = r(-\theta)$, then $f$ is equal to its reflection about the line $\theta = 0$ ($x$-axis).
If, for each $\theta$, $r(\theta) = -r(\theta)$, then $f$ is equal to its rotation by $\pi$ radians about the origin.
If, for each $\theta$, $r(\theta) = -r(-\theta)$, then $f$ is equal to its reflection about the line $\theta = \pi/2$ ($y$-axis).


TITLE: Concavity of trace of positive definite matrix
QUESTION [0 upvotes]: I have to show that $Tr((A^{-1} + B^{-1})^{-1})$ is a concave function, being A and B positive definite matrices.
I cannot imagine how is this possible since we are computing the trace of a positive definite matrix and the result will be always greater than zero.
Any idea? Thanks!

REPLY [0 votes]: We can use the excellent idea of the answer here.
The idea is to show that the second derivative is negative, which implies the function is concave.
Define $\widetilde{A}=A+\epsilon_1 C$ and $\widetilde{B}=B+\epsilon_2 D$, with $C,D$ symmetric.
So, we should show:
$$
\frac{\partial^2}{\partial \epsilon_i^2}
\text{tr}
 \left( \left[\widetilde{A}^{-1} +\widetilde{B}^{-1}\right]^{-1}\right)\bigg|_{\epsilon_i=0}
\leq 0
$$
Notice that we can do it for $i=1$, then the result holds by symmetry.
Next we will use the Woodbury matrix formula and the Taylor expansion of the inverse function for matrices (see here as well).
Note the assumption that $||A^{-1}B||<1$.
This lets us write:
\begin{align*}
\left[ \widetilde{A}^{-1} +\widetilde{B}^{-1} \right]^{-1}
&=
\widetilde{A} - \widetilde{A}(\widetilde{A} + \widetilde{B})^{-1}\widetilde{A}\\
&=
\widetilde{A} -
\widetilde{A}
(\widetilde{A}^{-1} - \widetilde{A}^{-1}\widetilde{B}\widetilde{A}^{-1}+
\widetilde{A}^{-1}\widetilde{B}\widetilde{A}^{-1}\widetilde{B}\widetilde{A}^{-1}-\ldots\,)
\widetilde{A}\\
&=
\widetilde{B} - \widetilde{B}\widetilde{A}^{-1}\widetilde{B}+
\widetilde{B}\widetilde{A}^{-1}\widetilde{B}\widetilde{A}^{-1}\widetilde{B}+\ldots\\
&=
\widetilde{B}
-
\widetilde{B}
\left[
{A}^{-1} - \epsilon_1{A}^{-1}C{A}^{-1}+
\epsilon^2_1{A}^{-1}C{A}^{-1}C{A}^{-1}+
\ldots
\right]
\widetilde{B}
+ \ldots
\end{align*}
Thus we can get:
\begin{align*}
\frac{\partial^2}{\partial \epsilon_i^2}
\text{tr}
 \left( \left[\widetilde{A}^{-1} +\widetilde{B}^{-1}\right]^{-1}\right)\bigg|_{\epsilon_i=0}
&=
\text{tr}(-2\widetilde{B}
\underbrace{
A^{-1}CA^{-1}CA^{-1}}_{PA^{-1}P^T}
\widetilde{B})\\
&=-2 \text{tr}(-2\widetilde{B}
\underbrace{PA^{-1}P^T}_{\text{Pos. Semi. Def}}
\widetilde{B})\\
&\leq 0
\end{align*}
using the fact that $B$ and $A^{-1}$ are positive definite.
Since the second derivative is non-positive, the trace function
$\text{tr}([A^{-1}+B^{-1}]^{-1})$
 is concave with respect to a perturbation of its arguments.


TITLE: Closedness of the image of the closed unit ball under a linear operator from a reflexive Banach space to an arbitrary Banach space
QUESTION [3 upvotes]: Let $V$ be a reflexive banach space. If $W$ is a Banach space and if $T$ is in $L(V,W)$, show that $T(B)$ is closed in $W$ where $B$ is closed unit ball in $V$,
the problem is in the chapter of weak and weak$^{\ast}$ topologies but I am not getting any hint what result I should use. please help.

REPLY [4 votes]: I'll assume you mean that $V$ is reflexive, since that's the only way that makes sense.

Since $V$ is reflexive, what can you say about the unit ball of $V$ (in a certain topology...)?
To show $T(B)$ is closed, suppose $v_n$ in $B$ with $Tv_n \to w$.  You need to produce $v \in B$ with $Tv = w$.  In light of the previous hint, can you think of a candidate for $v$?


TITLE: Value of $u(0)$ of the Dirichlet problem for the Poisson equation
QUESTION [6 upvotes]: Pick an integer $n\geq 3$, a constant $r>0$ and write
$B_r = \{x \in \mathbb{R}^n : |x| <r\}$. Suppose that
$u \in C^2(\overline{B}_r)$ satises
\begin{align}
-\Delta u(x)=f(x),  & \qquad x\in B_r, \\
u(x) = g(x),        & \qquad x\in \partial B_r,
\end{align}
for some $f \in C^1(\overline{B}_r)$ and $g \in C(\partial B_r)$
I have to show that
$$
u(0) = \frac{1}{n \alpha(n) r^{n-1}} \int_{\partial B_r} g(x) dS(x)
+ \frac{1}{n(n-2)\alpha(n)} \int_{B_r} \left( \frac{1}{|x|^{n-2}} - \frac{1}{r^{n-2}} \right) f(x) dx,
$$
Where $\alpha(n)$ is the volume of the unit ball and $n\alpha(n)$ is the surface area of its boundary, the unit sphere.Then I'm given the hint to modify the proof of the mean value theorem.
With the final remark to remember that
$\vec{\nabla} \cdot (v \vec{w}) = (\vec{\nabla}v) \vec{w} + v\vec{\nabla}\cdot \vec{w}$.
Now the mean value theorem from the book Partial Differential Equations by Evans
states that
$$
u(x) = \frac{1}{n \alpha(n) r^{n-1}}\int_{\partial B(x,r)} u \, dS  = \frac{1}{\alpha(n)r^n}\int_{B(x,r)} u \, dy,
$$
which is valid for harmonic functions. Thus in case $f(x)=0$ we seen that the statement holds.
For the proof of the mean value theorem defines the function
$$
\phi(r) := \frac{1}{n \alpha(n) r^{n-1}}\int_{\partial B(x,r)} u(y) dS(y)
= \frac{1}{n \alpha(n) r^{n-1}}\int_{\partial B(0,1)} u(x+rz) dS(z).
$$
Then it is shown that $\phi'(r)=0$, and so
$$
\phi(r) = \lim_{t\rightarrow 0} \phi(t) = \lim_{t\rightarrow 0} \frac{1}{n \alpha(n) t^{n-1}}\int_{\partial B(x,t)} u(y) dS(y) = u(x).
$$
The proof that $\phi'(x)$ is indeed constant is done with Green's formulas
\begin{align}
\phi'(r) &= \frac{1}{n \alpha(n) r^{n-1}}\int_{\partial B(0,1)} D u(x+rz)\cdot z \, dS(z) \\
&= \frac{1}{n \alpha(n) r^{n-1}}\int_{\partial B(x,r)} D u(y)\cdot \frac{y-x}{r} \, dS(y) \\
&= \frac{1}{n \alpha(n) r^{n-1}}\int_{\partial B(x,r)} \frac{\partial u}{\partial \nu} \, dS(y) \\
& = \frac{1}{n \alpha(n) r^{n-1}}\int_{B(x,r)} \Delta u \, dy =0.
\end{align}
However for the non harmonic problem I'm given the last equation
becomes
$$
\frac{1}{n \alpha(n) r^{n-1}}\int_{B(x,r)} \Delta u \, dy =
\frac{1}{n \alpha(n) r^{n-1}}\int_{B(x,r)} f(x) \, dy.
$$
What I probably should do is change the function $\phi$,
but I can't seem to figure out how.
Any help will be much appreciated.

REPLY [2 votes]: Edit: Sorry, I made a mess with the notation. To clarify, I will fix $R>0$, rename the domain $B_R$ and use the small case $r$ to denote the variable radius that will be the argument of $\phi$. With this change, what you need to show is
$$
u(0) = \frac{1}{n \alpha(n) R^{n-1}} \int_{\partial B_R} g(x) dS(x)
+ \frac{1}{n(n-2)\alpha(n)} \int_{B_R} \left( \frac{1}{|x|^{n-2}} - \frac{1}{R^{n-2}} \right) f(x) dx.
$$

You are right, another $\phi$ must be chosen. Try to imitate the previous effort: first, defining $\phi$ to be the expression that you want to prove is equal to $u$, then making the radius a variable and trying to prove that it actually doesn't depend on $r$ by showing that $\phi'=0.$ You know that $g$ is $u$ on the boundary and it's not defined in the interior of the domain (which we need to make $r$ vary), so replace $g$ with with $u$ to get a more general expression, valid for any radius $r$:
\begin{align}
\phi(r)=  \frac{1}{n \alpha(n) r^{n-1}} \int_{\partial B_r} u(x) dS(x)
+ \frac{1}{n(n-2)\alpha(n)} \int_{B_r} \left( \frac{1}{|x|^{n-2}} - \frac{1}{r^{n-2}} \right) f(x) dx.
\end{align}
You already showed in your question that the derivative of the first term is $-\frac{1}{n \alpha(n) r^{n-1}}\int_{B_r} f(y) \, dy$. Now it remains to differentiate the two other terms. To do it, use the product rule, the fact that $$\frac d{dr}\int_{B_r}h(x) \, dz=\int_{\partial B_r}h(x)dS(x)$$ for any integrable function $h$, and  that $|x|$ is constant and equal to $r$ in $\partial B_r$.
If everything goes right, the terms should cancel out, so that $\phi$ is a constant function of $r$. Next, notice as before that the first term approaches $u(0)$ when $r$ approaches $0$ (because of the usual averaging arguments), and that the other two terms become arbitrarily small, because the integrands are integrable and the measures of the domains of integration are approaching $0$. Therefore, $\phi$ equals $u(0)$ identically. Now, evaluating at $R$ you get the desired result:
$$
u(0) = \frac{1}{n \alpha(n) R^{n-1}} \int_{\partial B_R} g(x) dS(x)
+ \frac{1}{n(n-2)\alpha(n)} \int_{B_R} \left( \frac{1}{|x|^{n-2}} - \frac{1}{R^{n-2}} \right) f(x) dx.
$$


TITLE: Calculating value of definite integral
QUESTION [2 upvotes]: If $$ f(x) = x + \int_{0}^{1} t(x+t) f(t) dt $$
Then how to calculate $$ \int_{0}^{1} f(x) dx $$

REPLY [7 votes]: We can write
$$f(x)=x+x\int_0^1tf(t)dt+\int_0^1t^2f(t)dt=x+ax+b$$
where
$$a=\int_0^1tf(t)dt=\int_0^1t(t+at+b)dt$$
$$b=\int_0^1t^2f(t)dt=\int_0^1t^2(t+at+b)dt$$
Now solve this system.


TITLE: square every element of a measurable set
QUESTION [1 upvotes]: Given a measurable set $A$, if we square every element $B=\{a^2: a\in A\}$, is $B$ still measurable?
I have no idea about this question, can someone help me?

REPLY [2 votes]: Let $B_+=\bigl\{a^2\,|\,a\in A\cap[0,+\infty)\bigr\}$ and let $B_-=\bigl\{a^2\,|\,a\in A\cap(-\infty,0]\bigr\}$. Since $B=B_+\cup B_-$, if you prove that $B_+$ and $B_-$ are both measurable, then $B$ is measurable.
Now, note that if $s(x)=\sqrt x$, then $B_+=s^{-1}\bigl(A\cap[0,+\infty)\bigr)$. Since $s$ is continuous and $A\cap[0,+\infty)$ is measurable, $B_+$ is measurable. A similar argument shows that $B_-$ is measurable.


TITLE: Question on exchanging probability with limit
QUESTION [1 upvotes]: Consider a sequence of random variables $\{X_n\}_{n=1}^\infty$ where each random variable takes values in a set $\mathcal{X}$. Let $A \subset \mathcal{X}$ and assume that $X_n\rightarrow \alpha$ almost surely, where $\alpha \notin A$. From the convergence of $X_n$ we have that
\begin{equation}
\mathbb{P} (\lim_{n \rightarrow \infty}  X_n \in A) =0.
\end{equation}
Under which conditions does this relation imply
\begin{equation}
\lim_{n \rightarrow \infty}\mathbb{P} (  X_n \in A) =0.
\end{equation}
I think the result should follow directly by an application of the Dominated Convergence theorem. I tried to use the theorem by writing the probability as the expected value of an indicator function, so we have:
\begin{equation}
\lim_{n \rightarrow \infty}\mathbb{P} (  X_n \in A)  = \mathbb{E}[\lim_{n\rightarrow \infty} \mathbb{1}_{\{X_n \in A\}}].
\end{equation}
However, I am not if I can bring the limit inside the indicator somehow to prove the result. Any help would be appreciated.

REPLY [2 votes]: Since you are talking about $\lim_{n\to\infty}X_n$, I will assume $\mathcal X$ is a topological space.
A sufficient condition is to have $\alpha$ be a point in the interior of $A^c=\mathcal X\setminus A$. This means there is a neighborhood $U$ such that $\alpha \in U$ and $U\cap A=\varnothing$. Now, let $E_n$ be the event $\bigcap_{m\ge n} \{X_m\in U\}$, so $E_1\subset E_2\subset \dots$. Since $X_n\to \alpha$ a.s, we have $P(\bigcup E_n)=1$, which means $\lim_n P(E_n)=1$, which a fortiori implies $\lim_n P(X_n\notin A)=1$.
Edit: More detail. In a topological space, $x_n\to \alpha$ iff for every open set $U$ containing alpha, $x_n$ is "eventually" within alpha. This means there is an integer $n$ so $m\ge n$ implies $x_m\in U$. When $X_n$ is random, the property $\{X_m\in U\text{ for all } m\ge n\}$ is an event, which we denote $E_n$.
Since $X_n\to \alpha$ occurs almost surely, and convergence occurs implies at least one event $E_n$ occurs, we have $P(\bigcup E_n)=1$. Now, it is a standard result in probability theory that whenever $E_n$ is an increasing sequence of events, so that $E_1\subset E_2\subset \dots$, we have that $\lim_{n\to\infty} P(E_n)=P(\bigcup E_n)=1$.
Finally, consider the event $F_n = \{X_n\notin A\}$. Note that $F_n$ is implied by $E_n$, since $E_n\implies X_n\in U$ and $U$ is disjoint from $A$. Therefore, $\lim_{n\to\infty} P(E_n)=1$ implies $\lim_{n\to\infty} P(F_n)=1$ implies $\lim_{n\to\infty}P(X_n\in A)\to 0$.

However, anything can happen if $\alpha$ is a limit point. For example, letting
$\mathcal X=\mathbb R$, $A=(0,1)$, and $\alpha=0$, we have the following two possible situations:
$$
X_n\sim \text{Unif}(-1/n,1/n),\quad\qquad\qquad P(X_n\in A)=1/2\not\to 0\\
Y_n\sim \text{Unif}(-1/n+1/{n^2},1/n^2),\qquad P(Y_n\in A)=1/n\to 0
$$
Finally, you cannot use Dominated convergence because you have not proved that that the random variables ${\mathbb 1}(X_n \in A)$ even converge almost surely. That is, $\lim_{n\to\infty}{\mathbb 1}(X_n \in A)$ does not exist almost surely.


TITLE: Open maps of spaces vs open maps of locales
QUESTION [6 upvotes]: A continuous function between topological spaces $f:X\to Y$ is called open, if $f[U]\in\mathcal{O}(Y)$ for all $U\in\mathcal{O}(X)$.
A morphism of locales $f:X\to Y$ is called open, if the associated morphism of frames $f^*:\mathcal{O}(Y)\to\mathcal{O}(X)$ has a monotone left adjoint $f_!$ which satisfies the Frobenius condition $f_!(U)\wedge V\leq f_!(U\wedge f^*(V))$ for all $U\in\mathcal{O}(X)$ and $V\in\mathcal{O}(Y)$.
It is easy to see that every continuous $f$ that is open in the topological sense is also open in the localic sense, but the converse is false in general. For example,  the maps $1\to\nabla(2)$ and $\mathsf{cofin}(\mathbb{N})\to\mathsf{sobrify}(\mathsf{cofin}(\mathbb{N}))$ are open in the localic, but not in the topological sense, since they're not surjective, but the induced locale-morphisms are iso.
These two examples involve non-sober spaces, so the natural thing to ask is: Do the two notions coincide for sober spaces? Or more generally, does the canonical functor from locales to spaces preserve open maps?
Or are there other criteria for when the two notions coincide? For example, I think I have convinced myself that continuous maps that are open in the localic sense are open in the topological sense whenever the codomain is $T_1$.

REPLY [4 votes]: Sketches of an Elephant notes (before Lemma C1.5.3)

Of course, we say a [locale morphism] $f: X \to Y$ is open if, for every open sublocale $U$ of $X$, its image $f_!(U)$ in $\mathrm{Sub}(Y)$ is an open sublocale of $Y$....this is not quite equivalent to the usual notion of openness for continuous maps of spaces; it is implied by the latter, but in the opposite direction it only implies that the set-theoretic image of each open subset of $X$ is 'almost open' in $Y$, in the sense that its subclosure is open. Even when X and Y are both sober, this does not suffice to make all such images open..., but it obviously does so if $Y$ is a $T_D$-space.

The distinction here seems to correlate with the distinction between subspaces and sublocales. The latter extends to a distinction between image of a subspace and image of a sublocale, which are invoked in the definition of open map of spaces and locales, respectively.


text:
\section{Implementation}
\label{sec:implementation}

In this section, we present an implementation of our framework
and validate our assumptions using a concrete reachability algorithm and a concrete set representation.

\subsection{Computation of Reachable Sets}
\label{ssec:setprop}

We over-approximate the exponential matrix~$e^{At}$
by a finite number of Taylor terms~$\eta \in \naturalsof{+}$
and an interval matrix~$\E{}$ enclosing the remainder \cite[Prop. 2]{Althoff2011a}.

\begin{align}
	e^{A \Delta t} &\in \sum_{k=1}^{\eta} \frac{(A \Delta t)^k}{k!} \oplus \Eof{\Delta t, \eta} \; ,
		\label{eq:eAt} \\
	\Eof{\Delta t, \eta} &= [-\Eabsof{\Delta t, \eta}, \Eabsof{\Delta t, \eta}]\label{eq:E}  \\

	\text{with} \quad \Eabsof{\Delta t, \eta}
		&= \Big| \sum_{k=\eta + 1}^\infty \frac{1}{k!} \big(|A| \Delta t\big)^k \Big| \; . \label{eq:Eabs}
\end{align}

To cover all trajectories in a time interval spanned by~$\Delta t$,
we introduce the terms $\F{}$ \cite[Sec. 4]{Althoff2011a}
and $\inputCorr{}$ \cite[Sec. 3.2.2]{Althoff2010a}:

\begin{align}
	\Fof{\Delta t, \eta} &= \bigoplus_{k=2}^\eta [(k^{\frac{-k}{k-1}}
		- k^{\frac{-1}{k-1}}) \Delta t^k,0] \frac{A^k}{k!}
		\oplus \Eof{\Delta t, \eta} \; , \label{eq:F} \\
	\begin{split} \label{eq:inputCorr}
		\inputCorrof{\Delta t, \eta} &= \bigoplus_{k=2}^{\eta+1}
			[(k^{\frac{-k}{k-1}} - k^{\frac{-1}{k-1}}) \Delta t^k,0] \frac{A^{k-1}}{k!} \\
			&\qquad \oplus \Eof{\Delta t, \eta} \, \Delta t \; .
	\end{split}
\end{align}

The reachable sets for the homogeneous and inhomogeneous solution,
generally defined in~\eqref{eq:HRtieqplus} and~\eqref{eq:PRtieqplus},
are computed by~\cite[Sect. 3.2.1-3.2.2]{Althoff2010a}

\begin{align}
	\HRti{[0, \Delta t]} &=
		\underbrace{\CH{\initset{}, e^{A \Delta t} \initset{}}}_{= \, \HReqtiunderbrace{[0,\Delta t]}} \nonumber \\
		&\qquad \oplus \underbrace{\Fof{\Delta t, \eta} \, \initset{}
		\oplus \inputCorrof{\Delta t, \eta} \, \uTrans{}}
			_{= \, \HRplustiunderbrace{[0,\Delta t]}} \;, \label{eq:HRti_cora} \\

	\PRti{[0, \Delta t]} &= \underbrace{\sum_{k=0}^{\eta}
		\Big( \frac{A^k \Delta t^{k+1}}{(k+1)!} \Big) \, \inputset{}}_{= \, \PReqtiunderbrace{[0,\Delta t]}}
		\oplus \underbrace{\Eof{\Delta t, \eta} \, \Delta t \, \inputset{}}_{= \, \PRplustiunderbrace{[0,\Delta t]}} ,
			\label{eq:PRti_cora}
\end{align}
with~$\uTrans{}$ being the center of the input set~$\inputset{}$.
We include the term~$\inputCorrof{\Delta t, \eta} \, \uTrans{}$ in the homogeneous solution
as it only covers the current time interval and therefore does not accumulate over time.
In the next section, we will verify the applicability of
\eqref{eq:HRti_cora} and \eqref{eq:PRti_cora} for our adaptive framework.

\subsection{Verification of Assumptions}
\label{ssec:verass}

We now want to verify \assref{ass:bloatHRPR} and \propref{prop:bloatPRtiadm}.
To obtain the error $\bloatHRti{[t_i, t_{i+1}]}$
of the homogeneous solution $\HRti{[t_i, t_{i+1}]}$,
we multiply \eqref{eq:HRti_cora} by $e^{A t_i}$ as required in \eqref{eq:HRPR_start}
and insert the result in \eqref{eq:bloatHRti}, which yields
\begin{align}
	\begin{split} \label{eq:bloatHRti_cora}
	\bloatHRti{[t_i, t_{i+1}]} &=
		\errOp{ e^{A t_i} \, \Fof{\Delta t_i, \eta_i} \, \initset{} \\
			&\qquad \qquad \oplus \, e^{A t_i} \, \inputCorrof{\Delta t_i, \eta_i} \, \uTrans{} } \; .
	\end{split}
\end{align}

\begin{proposition} \label{prop:bloatHRti_cora}
The error $\bloatHRti{[t_i,t_{i+1}]}$ in \eqref{eq:bloatHRti_cora}
converges to 0 for $\Delta t_i \rightarrow 0$
and therefore satisfies \assref{ass:bloatHRPR}.
\end{proposition}

\begin{proof}
Since the operation $\errOp{\Sarb{}}$ returns the enclosing radius
of the interval over-approximation of a set $\Sarb{}$,
it suffices to show that the volume of $\Sarb{}$
converges to 0 for $\Delta t_i \rightarrow 0$.
This is the case if the interval matrices $\F{}$ and $\inputCorr{}$
converge to $[\zeroMat{n}, \zeroMat{n}]$:

Using \eqref{eq:inputCorr}, we yield
$\lim_{\Delta t \rightarrow 0} \inputCorrof{\Delta t, \eta} = [\zeroMat{n}, \zeroMat{n}]$.
For $\F{}$, we have that
$\lim_{\Delta t \rightarrow 0} \Eof{\Delta t, \eta} \overset{\eqref{eq:E}}{=} [\zeroMat{n},\zeroMat{n}]$ since
$\lim_{\Delta t \rightarrow 0} \Eabsof{0, \eta} \overset{\eqref{eq:Eabs}}{=} \zeroMat{n}$.
By plugging this in \eqref{eq:F}, we immediately see that
$\Fof{\Delta t, \eta} = [\zeroMat{n}, \zeroMat{n}]$ for $\Delta t \rightarrow 0$.
\end{proof}

To obtain the error $\bloatPRti{[t_i, t_{i+1}]}$
of the inhomogeneous solution $\PRti{[t_i, t_{i+1}]}$,
we multiply \eqref{eq:PRti_cora} by $e^{A t_i}$ as required in \eqref{eq:HRPR_start}
and insert the result in \eqref{eq:bloatPRti}, which gives us
\begin{equation} \label{eq:bloatPRti_cora}
	\bloatPRti{[t_i, t_{i+1}]} =
		\errOp{ e^{A t_i} \, \Eof{\Delta t_i, \eta_i} \, \Delta t_i \, \inputset{} } \; .
\end{equation}

\begin{proposition} \label{prop:bloatPRti_cora}
The error $\bloatPRti{[t_i,t_{i+1}]}$ in \eqref{eq:bloatPRti_cora}
converges to 0 for $\Delta t_i \rightarrow 0$
and therefore satisfies \assref{ass:bloatHRPR}.
\end{proposition}

\begin{proof}
Equivalently to the proof of \propref{prop:bloatHRti_cora},
we show that the volume of the resulting set converges to 0 for ${\Delta t_i \rightarrow 0}$.
Since $\Delta t_i$ appears as a multiplicative factor, it holds that
$\lim_{\Delta t_i \rightarrow 0} \, e^{A t_i} \, \Eof{\Delta t_i, \eta_i} \, \Delta t_i \, \inputset{}
= [\zeroMat{n}, \zeroMat{n}]$.
$~$ \hfill $~$
\end{proof}
We introduce the following lemma for the subsequent derivations:
\begin{lemma} \label{lmm:E}
The size of $\Eof{\Delta t, \eta}$ decreases superlinearly with respect to $\Delta t$:
\begin{equation*}
	\forall \varphi \in (0,1): \Eof{\varphi \Delta t, \eta} \subseteq \varphi \, \Eof{\Delta t, \eta} \; .
\end{equation*}
\end{lemma}

\noindent \textit{Proof.}
Using $\Eof{\Delta t, \eta} \overset{\eqref{eq:E}}{=} [-\Eabsof{\Delta t, \eta},\Eabsof{\Delta t, \eta}]$,
it is sufficient to show that each entry of $\Eabsof{\Delta t, \eta}$ decreases superlinearly
with respect to $\Delta t$:
\begin{align*}
	\hspace{20pt}
	&\forall \varphi \in (0,1): \Eabsof{\varphi \Delta t, \eta} \overset{\eqref{eq:Eabs}}{=}
	\Big| \sum_{k = \eta + 1}^{\infty} \frac{1}{k!} \big(|A| \varphi \Delta t\big)^k \Big| \\
	&\qquad \leq \varphi \, \Big| \sum_{k = \eta + 1}^{\infty} \frac{1}{k!} \big(|A| \Delta t\big)^k \Big|
	= \varphi \, \Eabsof{\Delta t, \eta} \; .
	\hspace{18pt} \square
\end{align*}

\begin{theorem}
The error $\bloatPRti{[t_i,t_{i+1}]}$ in \eqref{eq:bloatPRti_cora}
decreases superlinearly according to \defref{def:superlinear}:
\begin{equation*}
	\forall \varphi \in (0,1): \bloatPRti{[t_i, t_i + \varphi \Delta t_i]}
		\leq \varphi \, \bloatPRti{[t_i, t_i + \Delta t_i]} \; .
\end{equation*}
\end{theorem}

\textit{Proof:}
Since $\errOp{\cdot}$ is defined by the enclosing radius~$r$
according to \propref{prop:bloat},
it suffices to show that the enclosing radius decreases
superlinearly with respect to $\Delta t_i$:
\begin{equation*}
	\forall \varphi \in (0,1): r \big( \PRplusti{[t_i, t_i + \varphi \Delta t_i]} \big)
	\leq \varphi \, r \big( \PRplusti{[t_i, t_i + \Delta t_i]} \big) .
\end{equation*}
This condition is satisfied if
\begin{equation*}
	\forall \varphi \in (0,1): \PRplusti{[t_i, t_i + \varphi \Delta t_i]}
	\subseteq \varphi \, \PRplusti{[t_i, t_i + \Delta t_i]} \; .
\end{equation*}
Using the definition of $\PRplusti{[0, \Delta t]}$ in \eqref{eq:PRti_cora}
and \lmmref{lmm:E} it holds that
\begin{align*}

	&\PRplusti{[t_i, t_i + \varphi \Delta t_i]}
		\overset{\eqref{eq:PRti_cora}}{=} ( \varphi \, \Delta t_i ) \, e^{A t_i} \,
		\underbrace{\Eof{\varphi \Delta t_i, \eta_i}}_
			{\overset{\text{\lmmref{lmm:E}}}{\subseteq} \,
			\varphi \, \Eof{\Delta t_i, \eta_i}} \, \inputset{} \subseteq \\
		&\varphi \, \big( \underbrace{\varphi \Delta t_i \, e^{A t_i} \, \Eof{\Delta t_i, \eta_i} \, \inputset{}}_
			{\overset{\eqref{eq:PRti_cora}}{=} \,
			\varphi \, \PRplusti{[t_i, t_i + \Delta t_i]}} \big)
		\overset{\varphi \in (0,1)}{\subseteq} \varphi \, \PRplusti{[t_i, t_i + \Delta t_i]}. \;

	\square
\end{align*}

The cut-off value $\etamax{}$ can be automatically obtained according to \cite{Bickart1968}
to truncate the power series in \eqref{eq:eAt}.
If $\etamax{}$ does not satisfy the current error bounds,
we proceed to smaller values for $\Delta t$
which are guaranteed to eventually satisfy the error by \thmref{thm:alg:full}.

Following the above derivations, the presented implementation satisfies \thmref{thm:alg:full}.
Hence, it can be used to perform reachability analysis for LTI systems
while remaining below a user-defined over-approximation error.

\subsection{Set Representation}
\label{ssec:setrepr}

It remains to choose a set representation.
The work in~\cite{Althoff2016c} shows that zonotopes are optimal
and that one should add support functions if the initial set is not a zonotope.
Since we only use zonotopes as initial sets, we only use them:

\begin{definition} \label{def:zonotopes} (Zonotopes)
Given a center ${c \in \R{n}}$
and an arbitrary number ${\Gsize{} \in \naturals{}}$
of generator vectors ${g^{(1)}, ..., g^{(\Gsize{}{})} \in \R{n}}$,
a zonotope is defined as \cite[Def. 1]{Girard2005}

\begin{equation*}

	\mathcal{Z} = \Big\{ x \in \R{n} \, \Big| \, x
		= c + \sum_{i=1}^{\Gsize{}} \beta_i \cdot g^{(i)}, \, -1 \leq \beta_i \leq 1 \Big\} \; .

\end{equation*}
The order of a zonotope is $\zonOrder{} = \frac{\Gsize{}}{n}$. \hfill $\square$
\end{definition}

Following \defref{def:zonotopes}, we have that $\SetReprP{} = \zonOrder{}$.
We iteratively decrease the zonotope order by decrementing
the total number of generators describing $\PRti{[0,t_{i+1}]}$
as shown in~\cite{Kopetzki2017},
which also provides us with $\bloatSetti{[t_i,t_{i+1}]}$.
Therefore, we define the operator
$\decrOp{\SetReprP{}}: n\Gsize{} \gets n(\Gsize{} - 1)$.
In the next section, we apply the presented implementation.


TITLE: Interchanging total derivative and partial derivative
QUESTION [0 upvotes]: Say I have a function $F(x,y)$, where $x = f(t)$ and $y = g(t)$.
$$\frac{\mathrm{d} }{\mathrm{d} t} \frac{\partial F}{\partial x} \tag{1}$$
$$\frac{\partial }{\partial x} \frac{\mathrm{d} F}{\mathrm{d} t} \tag{2}$$
They both evaluate to the same thing. But is there something that I have to watch out for? For example, note that in eqn. (2), $\frac{\mathrm{d} F}{\mathrm{d} t}$ is a function of four variables: $x,y,\dot{x},\dot{y}$. So, the $\frac{\partial }{\partial x}$ in $\frac{\partial }{\partial x} \frac{\mathrm{d} F}{\mathrm{d} t}$ is not used in the same sense as equation (1)
Also, can I do something like this without reservation:
$$\frac{\mathrm{d^{10}} }{\mathrm{d^{10}} t} \frac{\partial^7 F}{\partial x^4 \partial y^3} = \frac{\partial^2}{\partial x \partial y} \frac{\mathrm{d^{2}} }{\mathrm{d^{2}} t} \frac{\partial^5 F}{\partial x^3 \partial y^2} \frac{\mathrm{d^{8}} F}{\mathrm{d^{8}} t}$$

REPLY [0 votes]: $\frac{\partial }{\partial x}\frac{dF}{dt}$ has no sense... Don't forget that $$t\mapsto F(x(t),y(t))$$ is a function from $\mathbb R\to\mathbb R$.


TITLE: least square optimization under positive semidefinite constraint
QUESTION [1 upvotes]: i have the following optimization problem:
$min_X \|aX-b\|$
$s.t. \quad X\geq 0$
where $a$, $b$ are vectors and $X$ is a matrix. Is there any possibility of obtain the closed form of the optimized X? Thanks.

REPLY [0 votes]: This is easy to formulate and solve (presuming it's not too large or otherwise unpleasant) in CVX or YALMIP.
CVX:
cvx_begin
variable X(length(a),length(a)) semidefinite
minimize(norm(a*X-b))
cvx_end

YALMIP:
X = sdpvar(length(a),length(a))
optimize(X>=0,norm(a*X-b))

By virtue of referring to least square optimization, presumably your intended norm is the 2-norm.  But you can easily change to the p-norm for any p >= 1(convex) in CVX by adding an extra argument to norm; or to the 1 or inf norms in YALMIP by adding this as an extra argument to  norm.


TITLE: Proof of: For all linearly ordered sets $X$, if there is a bijection from $n∈ℕ$ to $X$, then $n$ and $X$ are order-isomorphic
QUESTION [0 upvotes]: The theorem is:

This is the full proof given by my textbook:

I don't understand the structure of this proof. The proof goes:

Inductive hypothesis (the one i stated in the title of the question)
Define $f|ₙ:n→A\setminus\{f(n)\}$ is a bijection
Codomain of $f|ₙ$ is linearly ordered
Then by the inductive hypothesis there exist an order-isomorphism $g:n→A\setminus\{f(n)\}$
construct an order-isomorphism $h$ using $g$

and then i get lost.
Why do they define $h$ in two ways (the definition before the image and the definition after the image)?
Another thing i don't understand is, a proof by induction is a proof of the type:

Where is the $p(n+1)$ in this proof?

REPLY [1 votes]: It is a case study. First definition of $h$ is for the case $S\ne\emptyset$ and the second one is for the case $S=\emptyset$. In both cases, they show such an order-isomorphism exists.
For your second question, $p(n+1)$ is the construction of an order-isomorphism from $n+1$ (or $n^+, S(n))$ to $A$ when it is given that there is a bijection between $n+1$ and $A$.


TITLE: Under what conditions, if any, does a vector $(u, v, w)$ lie under the image of $T$?
QUESTION [1 upvotes]: I'm being asked to consider $T: \mathbb{R}^3 \to \mathbb{R}^3$ given by the formula:
$$(u, v, w) = T(x, y, z) = (x-y, y-z, z-x)$$
Then, I'm asked under what conditions, if any, does a vector $(u, v, w)$ lie in the image of $T$?
If my understanding is correct, the term "image" refers to the range of a transformation, meaning any element mapped to by $T$ within the codomain is the image.
It looks to me that any value for $u$, $v$, or $w$ will be acceptable under $T$, but I don't know how to validate that. I think I need some sort of equation that will prove that any input will produce a valid output. Is this a valid line of thinking, or am I on the wrong track?
My question is: How do I prove that any value is acceptable for a valid output? Thank you.

REPLY [1 votes]: $(u,v,w)$ will lie in the image of $T$ precisely if it is a linear combination of the columns of $T's$ matrix.  Namely, $(u,v,w)\in\rm{span}\{(1,-1,0),(0,1,-1), (-1,0,1)\}=\rm{span}\{(1,-1,0),(0,1,-1)\}$.
That is, the vector must lie on the plane $x+y+z=0$.


TITLE: About the double limit of a sequence
QUESTION [2 upvotes]: My book states that if the double limit $\lim_{m,n}f(m,n)$ exists and is equal to $l$ and if $\lim_nf(m,n)$ exists for all $m$, then $\lim_m\lim_nf(m,n)$ exists and is also equal to $l$. I was able to prove this result. However, the author gives the example :
$f(m,n)=\frac{1-(-1)^n}m$ and says that $\lim_nf(m,n)$ does not exist and hence the double limit cannot exist. I don't see how he made that conclusion. The hypothesis requires first the existence of the limit $\lim_nf(m,n)$ before we can conclude anything.
Also, I think the double limit does exist and is equal to $0$, since $|f(m,n)-0|≤\frac2m \forall m,n$.

REPLY [1 votes]: This seems to be a case of ambiguous expression, but it could be mis-statement.
It would be better, perhaps, to say that, while $$\lim_{m,n\to\infty}f(m,n)=0,\tag{1}$$ we have by contrast that $$\lim_{m\to\infty}\lim_{n\to\infty}f(m,n)$$ does not exist. That latter could be considered a double limit of a sort, but "iterated limit" would be more precise.
By your observation, we can, indeed, prove $(1),$ and further can prove that $$\lim_{m\to\infty}f(m,n)=0$$ for all $n,$ whence by the result you proved, we have $$\lim_{m,n\to\infty}f(m,n)=\lim_{n\to\infty}\lim_{m\to\infty}f(m,n).$$ This function $f$ therefore provides a good example of where a double-limit can be rewritten as an iterated limit in one way, but not the other.


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

Many of the recent unprecedented successes of machine learning can be partially attributed to state-of-the-art neural network architectures that come with up to tens of billions of trainable parameters.
Although test accuracy is one of the gold standards in choosing one of these architectures, in many applications having a ``compressed'' model  is of practical interest, due to typically reduced energy, memory, and computational footprint \cite{deng2020model,han2015learning, HanEtAl16,li2016pruning, wen2016learning,hubara2016binarized,hubara2017quantized,he2017channel,wu2016quantized,zhu2016trained, he2018amc,zhu2017prune,ChengEtAl19,mlsys2020_73}.
Such a compressed form can be achieved by either modifying the architecture to be leaner in terms of the number of weights, or by starting with a high-accuracy network and pruning it down to one that is sparse in some representation domain, while not sacrificing much of the original network's accuracy. A rich and long body of research work shows that one can prune a large network to a tiny fraction of its size, while maintaining (or sometimes even improving) its original accuracy
\cite{deng2020model,han2015learning, HanEtAl16,li2016pruning, wen2016learning,hubara2016binarized,hubara2017quantized,he2017channel,wu2016quantized,zhu2016trained, he2018amc,zhu2017prune,ChengEtAl19,mlsys2020_73}.

Although network pruning dates back at least to the 80s~\cite{HassibiStork93,LevinEtAl94,MozerSmolensky89,LeCunEtAl90},  there has been a recent flurry of results that introduce sophisticated pruning, sparsification, and quantization techniques which lead to significantly compressed model representations that attain state-of-the-art accuracy~\cite{deng2020model,  ChengEtAl19,mlsys2020_73}. Several of these pruning methods require many  rounds of pruning and retraining, resulting in a time-consuming and hard to tune iterative meta-algorithm.

Could we avoid this pruning and retraining cycle, by ``winning'' the weight initialization lottery, with a ticket that puts stochastic gradient descent (SGD) on a path to, not only accurate, but also very sparse neural networks? Frankle and Carbin~\cite{FrankleCarbin18} define {\it lottery tickets} as sparse subnetworks of a randomly initialized network, that if trained to full accuracy just once, can reach the performance of the fully-trained but dense target model. If these lottery tickets can be found efficiently, then the computational burden of pruning and retraining can be avoided.

Several works build  and expand on the {\it lottery ticket hypothesis} (LTH) that was introduced by Frankle and Carbin~\cite{FrankleCarbin18}.
 Zhou et al.~\cite{ZhouEtAl20} experimentally analyze different strategies for pruning.
 Frankle et al.~\cite{FrankleEtAl20} relate the existence of lottery tickets to a notion of stability of networks for SGD. Cosentino et al.~\cite{cosentino2019search}  show that  lottery tickets are amenable to adversarial training, which can lead to both sparse and robust neural networks. Soelen et al.~\cite{8852405} show that the winning tickets from one task are transferable to another related task. Sabatelli et al.~\cite{sabatelli2020transferability} show further that the trained winning tickets can be transferred with minimal retraining on new tasks, and sometimes may even generalize better than models trained from scratch specifically for the new task.

Along this literature, a striking finding was reported by Ramanujan et al.~\cite{RamanujanEtAl20} and Wang et al.~\cite{WangEtAl19}:
one does not even need to train the lottery tickets to get high test accuracy; they find that
high-accuracy, sparse models simply reside within larger random networks, and appropriate pruning can reveal them.
However, these high-accuracy lottery tickets do not exist in plain sight, and finding them is in itself a challenging (as a matter of fact NP-Hard) computational task.
Still, the mere existence of these random substructures is interesting, and one may wonder whether it is a universal phenomenon.

The phenomenon corroborated by the findings of Ramanujan et al.~\cite{RamanujanEtAl20} is referred to as the {\it strong lottery ticket hypothesis}.
Recently, Malach et al.~\cite{MalachEtAl20} proved the strong LTH for  fully connected networks with ReLU activations.
In particular, they show that one can approximate any target neural network, by pruning a sufficiently over-parameterized network of random weights. The degree of over-parameterization, i.e., how much larger this random network has to be, was bounded by a polynomial term with regards to the width $d$ and depth $l$ of the target network.
Specifically, their analysis requires the random network to be of width $\widetilde{O}(d^5 l^2 /\epsilon^2)$
and depth $2l$, to allow for a pruning that leads to an $\epsilon$-approximation with regards to the output of the target network, for any input in a bounded domain.
They also show that the required width can be improved to
$\widetilde{O}(d^2 l^2 /\epsilon^2)$
under some sparsity assumptions on the input.
Although polynomial, the required degree of over-parameterization is still too demanding, and it is unclear that it explains the experimental results that corroborate the strong LTH. For example, it does not reflect the findings in Ramanujan et al.~\cite{RamanujanEtAl20} that only seem to require a constant factor over-parameterization, e.g., a randomly initialized Wide ResNet50, can be pruned to a model that has the accuracy of a fully trained ResNet34. In this work, our goal is to address the following question:
\begin{quotation}
\begin{center}
    \noindent \it What is the required over-parameterization so that a network of random weights can be pruned to approximate a smaller target network?
\end{center}
\end{quotation}
Towards this goal, we identify the crucial step in the proof strategy of Malach et al.~\cite{MalachEtAl20} that leads to the polynomial factor requirement on the per-layer over-parameterization.
Say that one wants to approximate a weight $w^*\in[-1,1]$ with a random number drawn from a distribution, e.g., $\text{Uniform}([-1,1])$.
If we draw  $n=O(1/\epsilon)$ i.i.d. samples,
$$X_1,\ldots, X_n\sim\text{Uniform}([-1,1]),$$
then one of these $X_i$'s will be $\epsilon$ close to $w^*$, with constant probability. In a way, this random sampling generates an $\epsilon$-net, i.e., a set of numbers such that any weight in $[-1,1]$ is $\epsilon$ close to one of these $n$ samples. Pruning that set down to a single number, i.e., selecting the point closest to $w^*$, leads to an $\epsilon$ approximation for a single weight.
At the cost of a polynomial overhead on the number of samples $n$, one can appropriately apply this to every weight of a given layer, and then all layers of the network, in order to obtain a uniform approximation result for every possible input of the neural network.

Perhaps the surprising fact is that one can achieve the same approximation, with exponentially smaller number of samples, while still using a pruning algorithm. The idea is that instead of approximating the target weight $w^*$ with only one of the $n$ samples $X_1,\ldots, X_n$, one could add a subset of them to get a better approximation.
Indeed, when $n=O(\log(1/\epsilon))$, then, with high probability, there exists a subset $S\subseteq[1,\ldots,n]$, such that
$$\left|w^*-\sum\nolimits_{i\in S} X_i\right|\le \epsilon.$$
Hence, approximating $w^*$ by the best subset sum $\sum_{i\in S} X_i$, offers an exponential improvement on the sample complexity requirement compared to approximating it with one of the $X_i$'s.

The above approximation result for random $X_i$'s is drawn from a line of work on the random \textsc{SubsetSum}
 problem~\cite{Karp72,KarmarkarEtAl86,Lueker82,Lueker98}.
In particular, Lueker~\cite{Lueker98} showed that one can achieve an $\epsilon$-approximation of any target number $t\in[-1,1]$, with only $O (\log\left(1/\epsilon\right))$ i.i.d. samples from any distribution that contains a uniform distribution on $[-1,1]$, by using the solution to the following (NP-hard in general) problem
$$\min_{S}\left|t-\sum\nolimits_{i\in S} X_i\right|.$$
Adapting this result to ReLU activation functions is precisely what allows us to get an exponential improvement on the over-parameterization required for the strong LTH to be true.

\paragraph{Our Contributions:}
In this work, by adapting the random \textsc{SubsetSum} results of Lueker~\cite{Lueker98} to ReLU activation functions, we offer an exponential improvement on the over-parameterization required for the strong LTH to be true.
In particular we establish the following result.
\begin{inftheorem} (informal)
A randomly initialized network with width
$O(d\log( dl/ \min\{\epsilon,\delta\}))$ and depth $2l$,
with probability at least $1 - \delta$, can be pruned to approximate any neural network with width $d$ and depth $l$, up to error $\epsilon$.
\end{inftheorem}
The formal statement of  Theorem~\ref{thm:upperBound} is provided in Section~\ref{sec:upperBound}.
Note that in the above result, no training is required to obtain the sparser network within the random model, i.e., {\it pruning is all you need}. Further, note that we guarantee a good approximation to {\it any} network of fixed width and depth by pruning a {\it  single} larger network that is logarithmically wider. That is, the set of networks obtained by pruning the larger random network amounts to an $\epsilon$-net with regards to the smaller target networks.

We then show that this logarithmic over-parameterization is essentially optimal for constant depth networks.
Specifically, we provide a lower bound for 2-layered networks that matches the upper bound proposed in Theorem~\ref{thm:upperBound}, up to logarithmic terms with regards to the width (see Theorem~\ref{thm:lowerBoundStrong} in Section~\ref{sec:lowerBound} for a formal statement):
\begin{inftheorem} (informal)
There exists a 2-layer neural network with width $d$ which cannot be approximated to error within $\epsilon$ by pruning a randomly initialized 2-layer network, unless the random network has width at least $\Omega(d\log(1/\epsilon))$.
\end{inftheorem}
To the best of our knowledge, the only prior work that proves the validity of the strong LTH is Malach et al.~\cite{MalachEtAl20}.
However, as discussed earlier, their result gives an upper bound of $\widetilde{O}(d^5l^2)$ on the required width of the random networked to be pruned, which we improve to $O(d\log(dl))$.
A concurrent and independent work by Orseau et al.~\cite{orseau2020logarithmic} also prove a version of the strong LTH, where they use a hyperbolic distribution for initialization, and require the over-parameterized network to have width $O(d^2\log(dl))$. Although Orseau et al.~\cite{orseau2020logarithmic} prove their result for the hyperbolic distribution, they conjecture that it also holds for the uniform distribution.
Theorem \ref{thm:upperBound} proves this conjecture with an improved guarantee that a $O(d\log(dl))$ wide network suffices (which is smaller by a factor of $d$).
Furthermore, our result holds for a broad class of distributions beyond the uniform distribution (see Remark~\ref{rem:1}).

\paragraph{Notation}
We use lower-case letters to represent scalars, e.g., we may use $w$ to denote the weight of a single link between two neurons.
We use bold lower-case letters to denote vectors, for example, $\mathbf{v}, \mathbf{u}, \mathbf{v}_1, {\bf v}_2$. The $i$-th coordinate of the vector $\mathbf{v}$ is denoted as $v_i$.
Finally, matrices are denoted by bold upper-case letters.
For a vector $\mathbf{v}$, we use $\|\mathbf{v}\|$ to denote its $\ell_2$ norm.
If a matrix $\mathbf{W}$ has dimension $d_1 \times d_2$, we say $\mathbf{W} \in \mathbb{R}^{d_1 \times d_2}$.
The operator norm of a $d_1\times d_2$ dimensional matrix $\mathbf{M}$ is defined as $\|\mathbf{M}\|=\sup_{\mathbf{x}\in \mathbb{R}^{d_2},\|\mathbf{x}\|=1}\|\mathbf{M}\mathbf{x}\|.$
We denote the uniform distribution on $[a, b]$ by $U[a,b]$. We use $c,C$ to denote positive absolute constants, which may vary from place to place, and their exact values can be inferred from the proof details


TITLE: Prove that the polar decomposition of normal matrices, $A=SU$, is such that $SU=US$
QUESTION [5 upvotes]: Assume $A$ is a normal matrix. Suppose $A=SU$ is a polar decomposition of $A$. Prove that $SU=US$.
I have no idea to prove this.
$A$ is normal then $AA^*=A^*A$. And then we have
$$
SS^*=U^*S^*SU.
$$
But I don't know how to continue.

REPLY [0 votes]: Let $\newcommand{\bs}[1]{\boldsymbol{#1}} A$ be a normal matrix. It is therefore unitarily diagonalisable, i.e. writable as
$$A = \sum_k c_k P_{\bs u_k}$$
for a set of orthogonal projectors $P_{\bs u_k}\equiv \bs u_k \bs u_k^*$, where $\langle \bs u_j,\bs u_k\rangle=\delta_{jk}$ (and thus $\operatorname{Tr}(P_{\bs u_j} P_{\bs u_k})=\delta_{jk}$) and complex coefficients $c_k\in\mathbb C$.
The corresponding SVD (or more generally one possible choice of SVD) reads $A=UD V^\dagger$ with
$$
U = \sum_k e^{i\varphi_k} \bs u_k \bs e_k^*,\qquad
D=\sum_k |c_k| \bs e_k\bs e_k^*, \qquad
V=\sum_k \bs u_k \bs e_k^*,
$$
where $c_k\equiv |c_k|e^{i\varphi_k}$, and $\bs e_k$ are the basis vectors for some reference basis used to represent the matrices.
The polar decomposition reads $A=|A| U_A$ with
$$|A|\equiv UDU^\dagger= \sum_k |c_k| \bs u_k \bs u_k^*,
\qquad
U_A \equiv UV^\dagger = \sum_k e^{i\varphi_k} \bs u_k \bs u_k^*.$$
From this, it's clear that $|A|$ and $U_A$ commute, being them diagonal in the same basis.

It's worth seeing where exactly the above argument breaks in the case of non-normal matrices. For a generic matrix $A$ the SVD reads
$$A = UDV^\dagger = \sum_k p_k \bs u_k \bs v_k^*, \\
U\equiv \sum_k \bs u_k\bs e_k^*,
\qquad V \equiv \sum_k \bs v_k\bs e_k^*,
\qquad D \equiv \sum_k p_k \bs e_k \bs e_k^*,$$
for some positive coefficients $p_k>0$ and orthonormal sets $\{\bs u_k\}_k$ and $\{\bs v_k\}_k$. Then $A=|A| U_A$ with
$$|A| \equiv UD U^\dagger = \sum_k p_k \bs u_k \bs u_k^*,
\qquad
U_A \equiv UV^\dagger = \sum_k \bs u_k \bs v_k^*.
$$
Now we have
$$U_A |A| = (UV^\dagger U)DU^\dagger = \sum_{jk} p_k \langle \bs v_j,\bs u_k\rangle \bs u_j \bs u_k^*,$$
which in general differs from $|A| U_A=A$.


TITLE: Gravity, planetary orbits
QUESTION [0 upvotes]: If a planet was slowed down, what effect would it have on it’s orbit around a star. Or adversely if it were speeded up what effect would that have ?

REPLY [1 votes]: if you slow the orbiting planet down, it will move closer to the star it is orbiting around, and pick up orbital speed as it does. If you speed it up in its orbit, it will move out farther away from the star and slow down as it does.