text:
\begin{document}

\title[The Conway potential function of a graph link]
  {The Conway potential function of a graph link}

\author[David Cimasoni]{DAVID CIMASONI\\
Section de Math\'ematiques, Universit\'e de Gen\`eve,\addressbreak
2-4, rue du Li\`evre, CP 240, CH-1211 Gen\`eve 24, Suisse\addressbreak
  e-mail\textup{: \texttt{David.Cimasoni@math.unige.ch}}}

\volume{136}
\pubyear{2004}
\setcounter{page}{1}
\receivedline{Received \textup{15} July \textup{2002}}
\maketitle

\begin{abstract}
We give a closed formula for the multivariable Conway potential function of any graph link in a homology sphere. As corollaries,
we answer three questions by Walter Neumann \cite{N} about graph links.
\end{abstract}

\section{Introduction}\label{sec:1}

A link $L$ in a homology $3$-sphere is called a {\it graph link\/} if its exterior is a graph manifold. For example, a link in $S^3$ is a graph link
if and only if it is {\it solvable}, that is, if it can be constructed by iterated cabling and connected sum operations from the unknot.
This class of links is particularly interesting, since all the links that arise in complex algebraic geometry are of this type.

Eisenbud and Neumann \cite{E-N} gave a classification of graph links by means of decorated trees called {\it splice diagrams\/}; they also found a formula
for the multivariable Alexander polynomial $\Delta_L$ of graph links in terms of the splice diagram (see (\ref{thm:multi-Alex}) below).
Since the Conway potential function is determined up to a sign by $\Delta_L$, the only problem is to compute this sign.

In 1999, Walter Neumann \cite{N} succeeded in computing the Conway polynomial (that is: the one variable potential function) of any fibered
solvable link. In this article, Neumann proves several formulas for fibered solvable links,
and asks whether these equalities still hold for any graph link. In this paper, we compute the multivariable potential function of any
(fibered or non-fibered) graph link in a homology sphere (Theorem \ref{theorem:CPF}). As a consequence, we give a positive answer to Neumann's
questions (Corollaries \ref{cor:1}, \ref{cor:2} and \ref{cor:3}).

\section{The Conway Potential Function}\label{sec:2}

In 1970, Conway \cite{Con} introduced a new invariant of links called the {\it potential function}.
Given an oriented ordered link $L=L_1\cup\dots\cup L_n$ in $S^3$, its potential function is a well defined rational function
$\nabla_L(t_1,\dots,t_n)$ which satisfies
\begin{equation}\label{equ:Alex}
\nabla_L(t_1,\dots,t_n)\,\;\dot{=}\,\cases{\frac{1}{t_1-t_1^{-1}}\,\Delta_L(t_1^2) & if $n=1$; \cr
            	\Delta_L(t_1^2,\dots,t_n^2) & if $n\geqslant 2$,\cr}
\end{equation}
where $\;\dot{=}\;$ means equal up to a multiplication by $\pm t_1^{\nu_1}\cdots t_n^{\nu_n}$. Thus, this invariant is basically the
multivariable Alexander polynomial without the ambiguity concerning multiplication by units of $\Z[t_1^{\pm 1},\dots,t_n^{\pm 1}]$.
As a particular case of the potential function, Conway defined what was later called the {\it Conway polynomial} of a non-ordered link $L$.
It is given by
$$
\Omega_L(t)=(t-t^{-1})\;\nabla_L(t,\dots,t).
$$
Unfortunately, Conway's paper contains neither a precise definition of the potential function, nor a proof of its uniqueness.

In 1981, Kauffman \cite{Kau} found a very simple geometric construction of the Conway polynomial, namely
$$
\Omega_L(t)=\det\left(t^{-1}A-tA^T\right),
$$
where $A$ is any Seifert matrix of the link $L$ and $A^T$ the transpose of $A$. Finally, in 1983, Hartley \cite{Har} gave a definition of the
multivariable potential function $\nabla_L$ for any ordered oriented link in $S^3$. This definition was later extended by Turaev \cite{Tur} to
links in a $\Z$-homology $3$-sphere, and by Boyer and Lines \cite{B-L} to links in a $\Q$-homology $3$-sphere.

Let us now state several useful properties of the potential function; we refer to \cite{B-L} for the proofs.
Given an oriented ordered link $L=L_1\cup\dots\cup L_n$ in a $\Z$-homology sphere, there exists a well defined invariant $\nabla_L$
related to the multivariable Alexander polynomial $\Delta_L$ of $L$ by the equality (\ref{equ:Alex}). Furthermore, $\nabla_L$ satisfies the symmetry formula
\begin{equation}\label{equ:sym}
\nabla_L(t_1^{-1},\dots,t_n^{-1})=(-1)^n\,\nabla_L(t_1,\dots,t_n).
\end{equation}
Also, if $L'=(-L_1)\cup L_2\cup\dots\cup L_n$, where $(-L_1)$ denotes $L_1$ with the opposite orientation, then
\begin{equation}\label{equ:inv}
\nabla_{L'}(t_1,t_2,\dots,t_n)=-\nabla_L(t_1^{-1},t_2,\dots,t_n).
\end{equation}
Finally, if $L'=L_2\cup\dots\cup L_n$, we have the following {\it Torres formula\/}:
\begin{equation}\label{equ:Torres}
\nabla_L(1,t_2,\dots,t_n)=(t_2^{\ell_{12}}\cdots t_n^{\ell_{1n}}-t_2^{-\ell_{12}}\cdots t_n^{-\ell_{1n}})\;\nabla_{L'}(t_2,\dots,t_n),
\end{equation}
where $\ell_{ij}$ stands for the linking number $\Lk (L_i,L_j)$.

\section{Graph Links} \label{sec:3}
Eisenbud and Neumann \cite{E-N} gave a classification of graph links using splice diagrams. Following Neumann \cite{N}, we will
not recall the whole construction here, just several important features of these combinatorial objects. A splice diagram $\Gamma$ for a graph link $L$
is a tree decorated as follows:

\begin{romanlist}
\item{some of its valency one vertices are drawn as arrowheads, and correspond to the components of $L$;}
\item{the arrowheads have weight $+1$ or $-1$ (depending on whether the corresponding component of $L$ has ``intrinsic'' orientation or not);}
\item{each edge has an integer weight at any end where it meets a {\it node} (vertex of valency greater than one), and all the edge weights
around a node are pairwise coprime.}
\end{romanlist}

Given a non-arrowhead vertex $v$ of $\Gamma$, there is a so-called {\it virtual component} $L_v\,$: this is the additional link component that would
correspond to a single arrow at $v$ with edge weight $1$. It is very easy, given two vertices $v$ and $w$, to compute the linking number $\Lk(L_v,L_w)$
of their corresponding components (virtual or genuine): if $\sigma_{vw}$ denotes the shortest path in $\Gamma$ joining $v$ and $w$ (including $v$
and $w$), then $\Lk(L_v,L_w)$ is the product of the edge weights adjacent to but not on $\sigma_{vw}$, and of the possible arrowhead weights.

Let us now recall Eisenbud and Neumann's formula for the multivariable Alexander polynomial of a graph link \cite[Theorem 12.1]{E-N}.
If $L=L_1\cup\dots\cup L_n$ is a graph link given by a splice diagram $\Gamma$, its multivariable Alexander polynomial is equal to
\begin{equation}\label{thm:multi-Alex}
\Delta_L(t_1,\dots,t_n)\;\,\dot{=}\,\cases{(t_1-1)\prod_v(t_1^{\ell_{1v}}-1)^{\delta_v-2}& if $n=1$;\cr
				\prod_v(t_1^{\ell_{1v}}\cdots t_n^{\ell_{nv}}-1)^{\delta_v-2}& if $n\geqslant 2$,}
\end{equation}
where the product is over all non-arrowhead vertices $v$ of $\,\Gamma$, $\delta_v$ is the valency of the vertex $v$, and $\ell_{iv}$ denotes the
linking number of $L_i$ with $L_v$. In this equation, the terms of the form $(t_1^0\cdots t_n^0-1)^a$ should
be formally cancelled against each other before being set equal to zero.

In proving this theorem, Eisenbud and Neumann also show another remarkable result \cite[Theorem 12.2]{E-N}. Let us call an $n$-component link
{\it algebraically split\/} if, after possible renumbering, there is an index $1\leqslant q<n$ such that $\Lk(L_i,L_j)=0$ whenever $1\leqslant i\leqslant q<j\leqslant n$.
The theorem says that if $L$ is a graph link, then
\begin{equation}\label{thm:split}
\Delta_L(t_1,\dots,t_n)=0\quad\Longleftrightarrow\quad L\; \hbox{ is algebraically split}.
\end{equation}

This is a very striking property of graph links. For example, it implies that the Alexander polynomial $\Delta_L$ of a $2$-component graph link is zero if
and only if the linking number $\ell$ of the components is zero. For general $2$-component links $L$, if $\Delta_L$ vanishes, then $\ell=0$ (by the Torres
formula). But the converse is false: the Whitehead link has Alexander polynomial $(t_1-1)(t_2-1)$, although $\ell=0$.
As a matter of fact, it is still an open question how to characterize geometrically $2$-component links with vanishing Alexander polynomial
(see \cite[Problem 16]{Fox}).

Before stating and proving our results, let us finally recall very briefly Neumann's argument \cite{N} for fibered solvable links.
Let $L$ be an oriented graph link given by a splice diagram $\Gamma$. Using the value of the one variable Alexander polynomial $\Delta_L$ of $L$, together
with the equality $\Omega_L(t)=\pm t^{-d}\Delta_L(t^2)$, where $d$ is the degree of $\Delta_L$, we obtain the formula
$$
\Omega_L(t)=\pm(t-t^{-1})\prod_v(t^{\ell_v}-t^{-\ell_v})^{\delta_v-2}\;,
$$
where the product is over all non-arrowhead vertices of $\Gamma$, $\delta_v$ is the valency of the vertex $v$, and $\ell_v$ denotes the linking
number of $L$ with $L_v$. Thus, the only issue is the determination of the sign of $\Omega_L$.

If $L$ is a fibered link, its Seifert matrix $A$ is unimodular. Therefore, the leading coefficient of $\Omega_L(t)=\det\left(t^{-1}A-tA^T\right)$
is given by $\det(-A)$. For fibered links, Lee Rudolph defined an integer invariant $\lambda$ called the
{\it enhanced Milnor number}. If the ambient sphere is $S^3$, this number is known to satisfy the following formula (see \cite{N-R}):
$$
(-1)^\lambda=\det(-A).\eqno(\star)
$$
Neumann proves that $\lambda\equiv k_-+j_-\!\!\!\pmod{2}$, where $k_-$ is the number of $(-1)$-weighted arrowheads and $j_-$
the number of non-arrowhead vertices $v$ for which $\ell_v$ is negative and $\delta_v$ is odd. This leads to
$$
\det(-A)=(-1)^{k_-+j_-},\eqno(\star\star)
$$
giving the formula
$$
\Omega_L(t)=(-1)^{k_-}(t-t^{-1})\prod_v(t^{\ell_v}-t^{-\ell_v})^{\delta_v-2}.\eqno(\star\star\star)
$$
These results lead Neumann to the following questions:

\begin{romanlist}
\item{is the formula $(\star\star\star)$ true for any graph link in a homology sphere~?}
\item{does the equality $(\star\star)$ hold for fibered graph links in a homology sphere~?}
\item{is the equation $(\star)$ still valid for fibered graph links in a homology sphere~?}
\end{romanlist}

Corollaries \ref{cor:1}, \ref{cor:2} and \ref{cor:3} provide an affirmative answer to these three questions.

\section{Results} \label{sec:4}

We are now ready to state and prove our results. Using (\ref{thm:multi-Alex}) along with the equations (\ref{equ:Alex}) and (\ref{equ:sym}),
it is easy to compute the Conway potential function up to a sign.

\begin{lemma}\label{lemma:uptosign}
The potential function of a graph link $L$ in a homology sphere is given by
$$
\nabla_L(t_1,\dots,t_n)=\epsilon(L)\;\prod_v(t_1^{\ell_{1v}}\cdots t_n^{\ell_{nv}}-t_1^{-\ell_{1v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2},
$$
where $\epsilon(L)$ is equal to $+1$ or $-1$.
\end{lemma}

\begin{proof*}
By (\ref{thm:multi-Alex}) and equation (\ref{equ:Alex}), $\nabla_L(t_1,\dots,t_n)$ is equal to
\begin{eqnarray*}
\nabla_L&=&\cases{\frac{\epsilon(L)}{t_1-t_1^{-1}}\; t_1^{\nu_1}\; (t_1-t_1^{-1})\;
		\prod_v(t_1^{\ell_{1v}}-t_1^{-\ell_{1v}})^{\delta_v-2} & if $n=1$; \cr
            	\epsilon(L)\; t_1^{\nu_1}\cdots t_n^{\nu_n}\;
            	\prod_v(t_1^{\ell_{1v}}\cdots t_n^{\ell_{nv}}-t_1^{-\ell_{1v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2}  & if $n \geqslant 2$,}\\
&=&\epsilon(L)\; t_1^{\nu_1}\cdots t_n^{\nu_n}\;
		\prod_v(t_1^{\ell_{1v}}\cdots t_n^{\ell_{nv}}-t_1^{-\ell_{1v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2},
\end{eqnarray*}
for some integers $\nu_1,\dots,\nu_n$ and some sign $\epsilon(L)=\pm 1$.
The symmetry formula (\ref{equ:sym}) implies that $\nu_1=\dots=\nu_n=0$, giving the lemma.
\end{proof*}

\begin{lemma}\label{lemma:knot}
Let $K$ be a graph knot with $(+1)$-weighted arrowhead. Then $\epsilon(K)=+1$, that is:
$$
\nabla_K(t)=\prod_v(t^{\ell_v}-t^{-\ell_v})^{\delta_v-2}.
$$
\end{lemma}

\begin{proof*}
Let us use Kauffman's construction of the reduced potential function
$$
\Omega_K(t)=(t-t^{-1})\;\nabla_K(t)=\det(t^{-1}A-tA^T),
$$
where $A$ is any Seifert matrix for $K$. It is easy to check that the Seifert matrix for a graph knot $K$ is equal to the Seifert matrix for the
knot $K'$ obtained from $K$ by deleting every non-fibered splice component. (In other words: if $\Gamma$ is a splice diagram for $K$, a splice
diagram $\Gamma'$ for $K'$ is obtained from $\Gamma$ by deleting every vertex $v$ such that $\ell_v=0$.) Therefore, we can assume that $K$ is fibered.
In that case, $A$ is unimodular.
In particular, $\det(-A)$ is non-zero, so that $\det(-A)$ is the leading coefficient of $\Omega_L(t)=\det(t^{-1}A-tA^T)$.
There is an explicit computation of $A$ for graph knots in \cite{E-N}; it can be used to check the lemma.
Details can be found in \cite{these}.
\end{proof*}

\begin{lemma}\label{lemma:split}
Consider $L=L_1\cup\dots\cup L_n$. If $L-L_i$ is algebraically split for all $i$, then $L$ is algebraically split.
\end{lemma}

\begin{proof*}
Let us associate to $L$ a graph $G_L$ as follows: the vertices of $G_L$ correspond to the components of $L$, and two
vertices are linked with an edge if the linking number of the corresponding components is not equal to zero. Clearly, $L$ is algebraically split if and
only if $G_L$ is not connected.
Given a vertex $v$ of a graph $G$, let us denote by $G-v$ the subgraph obtained by deleting the vertex $v$ and every edge adjacent to $v$.
We are left with the proof of the following assertion: given a graph $G$, if $G-v$ is not connected for any vertex $v$ of $G$, then $G$ is not connected.
In other words: if $G$ is a connected graph, there exists a vertex $v$ such that $G-v$ is connected. This last statement is very easy to prove:
given $G$ a connected graph, let $T$ be a maximal subtree of $G$. Since $T$ is a tree, it has at least
one vertex $v$ of degree one. Then, $T-v$ is connected, as well as $G-v$.
\end{proof*}

\begin{theorem}\label{theorem:CPF}
Let $L$ be a graph link with $n$ components given by a splice diagram $\Gamma$. Then, its Conway potential function is equal to
$$
\nabla_L(t_1,\dots,t_n)=(-1)^{k_-}\prod_v(t_1^{\ell_{1v}}\cdots t_n^{\ell_{nv}}-t_1^{-\ell_{1v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2},
$$
where the product is over all non-arrowhead vertices $v$ of $\,\Gamma$, $\delta_v$ is the valency of the vertex $v$, $\ell_{iv}=\Lk(L_i,L_v)$,
and $k_-$ is equal to the number of $(-1)$-weighted arrowheads.
\end{theorem}

\begin{proof*}
By formula (\ref{equ:inv}), it may be assumed that all the arrowheads have weight $(+1)$. Using the notation of Lemma \ref{lemma:uptosign},
we have to check that if $k_-=0$, then $\epsilon(L)=+1$. Let us do this by induction on $n\geqslant 1$.

The case $n=1$ is settled by Lemma \ref{lemma:knot}. Let us fix some $n\geqslant 2$, and assume that $\epsilon(L')=+1$ for all graph link $L'$ with
$n'\leqslant n-1$ arrowheads, all $(+1)$-weighted. Let $L=L_1\cup\dots\cup L_n$ be a graph link with $k_-=0$. If $\nabla_{L-L_i}=0$ for all $i$, then
(by (\ref{equ:Alex}) and (\ref{thm:split})) $L-L_i$ is algebraically split for all $i$. By Lemma \ref{lemma:split}, it follows that $L$ is
algebraically split, so that $\nabla_L=0$. In this case, there is nothing to prove. Therefore,
it may be assumed (after possible renumbering) that $\nabla_{L-L_1}\neq 0$. Let us note $L'=L-L_1$. If $\ell_{12}=\dots=\ell_{1n}=0$, then $L=L_1\sqcup L'$
is algebraically split, so $\nabla_L=0$. Hence, we can assume without loss of generality that $\ell_{12}\cdots\ell_{1n}\neq 0$. To summarize,
it may be assumed that
$$
(t_2^{\ell_{12}}\cdots t_n^{\ell_{1n}}-t_2^{-\ell_{12}}\cdots t_n^{-\ell_{1n}})\;\nabla_{L'}(t_2,\dots,t_n)\neq 0.
$$
The key ingredient of the induction step is the Torres formula (\ref{equ:Torres}). By Lemma \ref{lemma:uptosign}, we have
$$
\nabla_L(1,t_2,\dots,t_n)=\epsilon(L)\;\prod_{v\in \VV}(t_2^{\ell_{2v}}\cdots t_n^{\ell_{nv}}-t_2^{-\ell_{2v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2}.
$$
On the other hand, by (\ref{equ:Torres}),
$$
\nabla_L(1,t_2,\dots,t_n)=(t_2^{\ell_{12}}\cdots t_n^{\ell_{1n}}-t_2^{-\ell_{12}}\cdots t_n^{-\ell_{1n}})\;\nabla_{L'}(t_2,\dots,t_n)\;,
$$
which, by induction, is equal to
$$
(t_2^{\ell_{12}}\cdots t_n^{\ell_{1n}}-t_2^{-\ell_{12}}\cdots t_n^{-\ell_{1n}})\;
\prod_{v\in \VV'}(t_2^{\ell_{2v}}\cdots t_n^{\ell_{nv}}-t_2^{-\ell_{2v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2}.
$$
Now, the set of non-arrowhead vertices $\VV'$ of $L'$ is equal to $\VV\cup \{v_1\}$, where $v_1$ is the vertex corresponding to the component $L_1$.
Therefore, $\delta_{v_1}=1$, $\ell_{v_1v}=\ell_{1v}$, and we have the equality
$$
\epsilon(L)\;\prod_{v\in \VV}(t_2^{\ell_{2v}}\cdots t_n^{\ell_{nv}}-t_2^{-\ell_{2v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2}=
\prod_{v\in \VV}(t_2^{\ell_{2v}}\cdots t_n^{\ell_{nv}}-t_2^{-\ell_{2v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2}.
$$
Since
$$
\prod_{v\in \VV}(t_2^{\ell_{2v}}\cdots t_n^{\ell_{nv}}-t_2^{-\ell_{2v}}\cdots t_n^{-\ell_{nv}})^{\delta_v-2}=
	(t_2^{\ell_{12}}\cdots t_n^{\ell_{1n}}-t_2^{-\ell_{12}}\cdots t_n^{-\ell_{1n}})\;\nabla_{L'}(t_2,\dots,t_n),
$$
which is assumed to be non-zero, $\epsilon(L)$ is equal to $+1$.
\end{proof*}

\begin{corollary}\label{cor:1}
The Conway polynomial of a fibered graph link $L$ is given by
$$
\Omega_L(t)=(-1)^{k_-}(t-t^{-1})\prod_v(t^{\ell_v}-t^{-\ell_v})^{\delta_v-2}.
$$
\end{corollary}

\begin{proof*}
Use the fact that $\Omega_L(t)=(t-t^{-1})\;\nabla_L(t,\dots,t)$.
\end{proof*}

\begin{corollary}\label{cor:2}
Let $A$ be a Seifert matrix for a fibered graph link $L$; then
$$
\det(-A)=(-1)^{k_-+j_-},
$$
where $j_-$ is the number of non-arrowhead vertices $v$ with $\ell_v$ negative and $\delta_v$ odd.
\end{corollary}

\begin{proof*}
If $L$ is a fibered link, $A$ is unimodular, so $\det(-A)$ is the leading coefficient of
$\Omega_L(t)=\det(t^{-1}A-tA^T)$. By Corollary \ref{cor:1}, $\det(-A)$ is the leading coefficient of
$(-1)^{k_-}\prod_v(t^{\ell_v}-t^{-\ell_v})^{\delta_v-2}$, which is clearly $(-1)^{k_-+j_-}$.
\end{proof*}

\begin{corollary}\label{cor:3}
Let $A$ be a Seifert matrix for a fibered graph link $L$; then
$$
\det(-A)=(-1)^\lambda\,,
$$
where $\lambda$ is the enhanced Milnor number of $L$.
\end{corollary}

\begin{proof*}
By Theorem 6.1 and $\S$10 in \cite{N-R}, we have the equality
$$
\lambda=\ell k(P\cup L_+,N\cup L_-),
$$
where the notations are as in \cite{N}. By Corollary \ref{cor:2}, it remains to show that
$$
\ell k(P\cup L_+,N\cup L_-)\equiv k_-+j_-\!\!\!\pmod{2}.
$$
The argument is exactly as in \cite{N}.
\end{proof*}

Of course, Corollaries \ref{cor:2} and \ref{cor:3} are false for non-fibered graph links. For example, a Seifert matrix $A$
for the trivial $2$-component link satisfies $\det(-A)=0$.

\begin{ex*}
{\rm Consider the graph link $L$ given by the splice diagram illustrated below,

\begin{figure}[ht]
\begin{center}
\epsfig{figure=splice.eps,height=2.7cm}
\end{center}
\end{figure}
and let us note $\alpha=\alpha_1\cdots\alpha_k$. Then, the potential function of $L$ is equal to}
$$
\nabla_L(t_1,\dots,t_n)\;=\;\frac{\left(t_1^{\alpha/\alpha_1}\cdots t_n^{\alpha/\alpha_n}-t_1^{-\alpha/\alpha_1}\cdots t_n^{-\alpha/\alpha_n}\right)^{k-2}}
{\prod_{i=n+1}^k\left(t_1^{\alpha/\alpha_1\alpha_i}\cdots t_n^{\alpha/\alpha_n\alpha_i}-t_1^{-\alpha/\alpha_1\alpha_i}\cdots t_n^{-\alpha/\alpha_n\alpha_i}\right)}.
$$
\end{ex*}

\begin{acknowledgments}
The author wishes to express his thanks to Fran\c coise Michel, Claude Weber and Mathieu Baillif.
\end{acknowledgments}

config: arxiv


TITLE: Does my "Prime Factor Look-and-Say" sequence always end?
QUESTION [37 upvotes]: I'm trying to create a challenge for PP&CG where the object will be to find the longest sequence in a given time, but I'm worried that there may be an infinite sequence that will ruin things.
The sequence is similar to the Look-and-say sequence, but using the prime factors (in increasing order) of the previous term for the current. When the current term is prime, the sequence stops. For example, if the first term is 15, you get:
15       = one 3, one 5  (1 3 1 5)
1315     = one 5, one 263 (1 5 1 263)
151263   = two 3s, five 7s (2 3 5 7)
2357     = prime, stop sequence

So, starting with 15 gives a four-term series. Starting with any prime gives a one-term series.
Additionally, if a sequence revisits a number, it stops (counting the revisited number only once). I don't know if there are any cyclic sequences, but that's there to prevent it.
Each number I've tried so far (manually) eventually terminates, but I'm not confident that it holds for any starting term. Is there any simple insight I'm missing that would show (or disprove) that for every (positive) starting number the sequence will be finite? I don't care if it's absurdly long, just not infinite.

REPLY [17 votes]: Starting with $8$ I get $32, 52, 22113, 5317113, 131167110613, \ldots$ and the sequence shows no sign of ending.  At some point the numbers get so big that factoring becomes very slow.  My program gave up when trying to factor
$$ 231331170111602782603539242084011491005276716148307683565573944963714969597915443$$
EDIT: Let $x_k$ be the sequence of numbers obtained in this process.
If $x_k = p_1 \cdots p_m$ has $n$ digits, the factors $p_1, \ldots, p_m$ have
between $n$ and $n+m-1$ digits together (i.e. if $10^{d_j-1} \le  p_j < 10^{d_j}$ and $s = d_1 + \ldots + d_m$ we have $10^{s-m} \le x < 10^s$), and (if the $p_j$ are distinct) the next number $x_{k+1}$ has between $n+m$ and $n + 2m-1$ digits. Numbers that are not squarefree reduce this somewhat.  Typically, a number with $n$ digits has roughly $\log n$ distinct prime factors.  So we should expect the number of digits in $x_k$ not to grow much more than linearly, maybe at most something like $k \log(k)$.  The probability of a random integer of this size being prime is something like $\dfrac{1}{k \log(k)}$.  Since $\sum_k \dfrac{1}{k \log(k)}$ diverges,
we should expect to eventually encounter a prime.  However, this is only a heuristic argument, not a proof, and that sum diverges extremely slowly, so
given that we have reached an $81$-digit number without finding a prime the number of steps needed might well be enormous.
Here is a plot of the number of digits in $x_k$ for $k = 0 \ldots 20$ with
$x_0 = 8$.

EDIT: Actually there was the bug in my code (I forgot that Maple does not always list the factors in numerical order), so the number 231331... above was wrong.  But the plot should be correct.  The $90$-digit $x_{20}$ is
$$ \small 143314611607153852459854993120121438819369187408718398556398062751481672397689379055730183$$


TITLE: Space (Lorentz-Fitzgerald) contraction
QUESTION [2 upvotes]: Lorentz transform can be written, according to wikipedia, as:
$$
\begin{align}
  ct' &= \gamma \left( c t - \beta x \right)  \\
  x' &= \gamma \left( x  - \beta ct \right)  \\
  y' &= y \\
  z' &= z.
\end{align}
$$
I see a complete symmetry between terms ct/ct' and x/x', that is, I can exchange ct with x and ct' with x' obtaining exactly the same equations.
However, books talk about "time dilation" and "space (Lorentz-Fitzgerald) contraction", not about "time and space dilation".
I assume "time" is related to term ct and "space" to x.
Please, could someone help me to see my error or understand the point of view under the expression "space contraction"?

REPLY [1 votes]: To measure the length of a rod in the frame of reference in which it is stationary (the S' frame or "the rod's frame") we place a ruler against it and take readings against the ruler of either end of the rod. It doesn't matter whether or not we take the readings at the same time.
To measure the length of the rod in the laboratory or S frame, in which the rod is whizzing past the ruler we must clearly take simultaneous readings of either end of the rod against the ruler. Thus the events of taking the readings are at (say) ($T, x_1) \text{and} (T, x_2)$.
The separation of these events in the ruler's frame (where the events are not simultaneous, but this doesn't matter) is$$x_{1}'-x_{2}'=\gamma(x_1-\beta cT-[x_2 -\beta cT])= \gamma(x_1-x_2 )$$
So $x_1-x_2 < x_{1}'-x_{2}'.$ Hence the length contraction.
Now consider time dilation. A rocket whizzes through the laboratory (the S frame). Let it emit flashes of light separated by a time interval $T_0\  (=t_{2}'-t_{1}')$ as measured by its own clock. In the clock's frame (the frame in which the clock is stationary) these flashes are in the same place (X'). In the lab frame they are in different places. Using the inverse transform, the time interval between the flashes, as measured in the lab by (synchronised) clocks at the places where the flashes occur, is
$$ct_2-ct_1=\gamma(ct_{2}'+\beta X'-[ct_{1}'+\beta X'])=\gamma(ct_{2}'-ct_{1}').$$
Thus $t_2-t_1\ >\ t_{2}'-t_{1}'.$  This is time dilation.
We can now see how the asymmetry arises. For length comparisons, measurements must be at the same time in the lab frame. For time comparisons the place is the same in the 'moving' frame, but different in the lab frame.


TITLE: On an inequality about asymptotics of Whittaker functions
QUESTION [1 upvotes]: I'm reading Wallach's paper 'Asymptotic expansions of generalized matrix entries of representations of real reductive groups'(Lecture Notes in Math., 1024,287–369) and got confused by one statement there on asymptotics of Whittaker functions. Near the bottom of page 361, there is an inequality without proof
$$|f_{\lambda,v}(x)|\le C_{n,v}x^{-n} for \ \ all \ \ x\ge 1 \ \ and \ \ all \ \ n=1,2,...$$
where $\lambda$ is the Whittaker functional on an irreducible generic smooth representation $\pi$, $v$ is a vector in $\pi$, $f_{\lambda,v}(e^t)=\lambda(\pi( exp \ \ tH)v)$, $H\in \mathfrak{a}$ and the smallest eigenvalue of $ad H$ on $\mathfrak{n}$ is 1 (see on top of page 358 of that paper), here $(P,A)$ is a standard parabolic pair with unipotent radical $N$ and $\mathfrak{a},\mathfrak{n}$ are Lie algebras of $A,N$ respectively.
I couldn't figure out this simple fact. Any help or reference are appreciated in advance.

REPLY [2 votes]: Not sure about the level of generality in Wallach's paper, but if that Whittaker function is given by a Jacquet integral (Multiplicity One for Whittaker functions), you can integrate by parts many times and would give you the result.


TITLE: Torsors in Algebraic Geometry?
QUESTION [29 upvotes]: I think I am confused about some terminology in algebraic geometry, specifically the meaning of the term "torsor". Suppose that I fix a scheme S. I want to work with torsors over S. Let $\mu$ be a sheaf of abelian groups over S. Then my understanding is that a $\mu$-torsor, what ever that is, should be classified by the cohomology gorup $H^1(X; \mu) \cong \check H^1(X; \mu)$.
Now suppose that $\mu$ is representable in the category of schemes over S, i.e. there is a group object $$\mathbb{G} \to S$$
in the category of schemes over $S$, and maps (over S) to $\mathbb{G}$ is the same as $\mu$. Lots of interesting example arise this way.
I also thought that in this case a torsor over S can be defined as a scheme $P \to S$ over S with an action of the group $\mathbb{G}$ such that locally in S it is trivial. I.e. there exists a cover $U \to S$ such that
$$ P \times_S U \cong \mathbb{G} \times_S U $$
as spaces over S with a $\mathbb{G}$-action (or rather as spaces over U with a $\mathbb{G} \times_S U$-action).
The part that confuses me is that these two notions don't seem to agree. Here is an example that I think shows the difference. Let $S= \mathbb{A}^1$ be the affine line (over a field k) and let $x_1$ and $x_2$ by two distinct points in $S$. Consider the subscheme $Y = x_1 \cup x_2$, and let $C_Y$ be the complement of Y in S. Let $A$ be your favorite finite abelian group which we consider as a constant sheaf over S. Then we have an exact sequence of sheaves over S,
$$0 \to A_{C_Y} \to A \to i_*A \to 0$$
Where $i_*A(U) = A(U \cap Y)$. I believe the first two are representable by schemes over S, namely $$C_Y \times A \cup S \times 0$$
and  $S \times A$, where we are viewing the finite set $A$ as a scheme over $k$ (and these products are scheme-theoretic products of schemes over $spec \; k$).
In any event, the long exact sequence in sheaf cohomology shows that
$$H^1(S; A_{C_Y}) \cong \check H^1(S; A_{C_Y}) \cong A$$
and it is easy to build an explicit C$\check{\text{e}}$ch cocycle using the covering given by the two opens consisting of the subschemes $U_i = S \setminus x_i$, for $i = 1,2$.
Now the problem comes when I try to glue these together to get a representable object over S, i.e. a torsor in the second sense. Then I am looking at the coequalizer of
$$C_Y  \times A \rightrightarrows (C_Y\cup C_Y) \times A$$
where the first map is the inclusion and the second is the usual inclusion together with addition by a given fixed element $a \in A$. This seems to just gives back the trivial "torsor" $C_Y \times A$.
Am I doing this calculation wrong, or is there really a difference between these two notions of torsor?

REPLY [19 votes]: As remarked by Brian Conrad above, there is an excellent explanation of all this in Milne's book Étale cohomology, Section III.4.  There wouldn't be much point in reproducing the details here, but the main issues are:

You need to decide whether a torsor is going to be a scheme over S which locally looks like a trivial torsor, or merely a sheaf of sets over S which locally looks like a trivial torsor.  What people mean by "torsor" can be either of these things.  As Milne says, "The question of which sheaf torsors arise from schemes is, in general, quite delicate".  If you go for the sheaf definition, then isomorphism classes of torsors are indeed classified by $\check H^1(S,G)$.  Beware that if G is not commutative then you need to define $\check H^1(S,G)$ appropriately as a pointed set.
You need to decide which topology all this is happening in; the usual definition of torsor uses the flat topology, though if G is smooth over S then you can use the étale topology instead.
Depending on what topology you're using, and what S and G look like, there may be issues about whether $\check H^1(S,G)$ and $H^1(S,G)$ are isomorphic.


text:
\section{Proof of Theorem \ref{thm:phaseTrans}}

We will prove Theorem \ref{thm:phaseTrans} by deriving a so-called \emph{dual certificate} \cite{Fuchs, Gross,TroppDual}, that is a vector $\nu\in \R^M$ having a small $\ell_2$-norm and fulfilling $A^*\nu\in H_S^t$, for some $t\ge0$, where
\begin{align*}
H_S^t:=\left\{w\in \R^N: w_i\le -t\text{ for } i \in S \text{ and } w_i\ge t \text{ for } i \notin S\right\}.
\end{align*}

To justify that this will help to prove the theorem, let us recall some results from \cite{FlKei}.

\begin{proposition}[Propositions II.3 and III.1 of \cite{FlKei}]
		\renewcommand{\labelenumi}{\roman{enumi})}
Let $A\in \R^{M,N}$ and $S\subset[N]$. Then the following statements are equivalent:
	\renewcommand{\labelenumi}{\roman{enumi})}
\begin{enumerate}
	\item $\one_S$ and $\one-\one_S=\one_{S^C}$ are the unique solutions of \eqref{Pbin}.
	\item $\ker(A)\cap H_S^0=\{0\}$.
	\item $\{x\in [0,1]^N: Ax=A\one_S\}=\one_S$.
	\item There is $\nu\in \R^M$ such that $A^*\nu\in H_S^t$ for some $t>0$.
\end{enumerate}
\end{proposition}

Hence, finding a dual certificate indeed ensures, that $\one_S$ is the unique solution of \eqref{Pbin}. However, the third equivalence even yields that there is no other solution of $Ax=A\one_S$ other than $\one_S$ in the box $[0,1]^N$. Thus, the minimization in \eqref{Pbin} is not crucial and we can run box-constrained least-squares \eqref{LSBin} instead.

The proof of Part \emph{iii)} of Theorem \ref{thm:phaseTrans} will further make use of the following result from \cite{FlKei}.

\begin{proposition}\label{prop:noise}[Proposition III.4 of \cite{FlKei}]
Let $r,t, \eta>0$, $S\subset [N]$ and $A\in \R^{M,N}$. Suppose that there exists a dual certificate $\nu\in \R^M$ such that $A^*\nu \in H_S^t$ and $\norm{\nu}_2 \leq r$.

Let $x_0=\mathbb{1}_S\in \R^N$ be the binary signal supported on $S$, and $y=Ax_0 + n$ with $\norm{n}_2 \leq \eta$. Then the solution $x_*$ of the program \eqref{LSBin} obeys
\begin{align*}
\norm{x_*-x_0}_2 \leq \frac{2r}{t}\eta.
\end{align*}
\end{proposition}

Before constructing the dual certificate explicitly, let us recall a so-called Hoeffding-type inequality as well as Hanson-Wright inequality, which will be an important probabilistic tools for the proof of Theorem \ref{thm:phaseTrans}.

\begin{theorem}[Proposition 5.10 of \cite{VershyninRandomMatrices} and Theorem 1.1 of \cite{rudelson2013hanson}]\label{ProbTools}\
	\renewcommand{\labelenumi}{\roman{enumi})}
	\begin{enumerate}
	\item There exists a universal constant $C>0$ with the following property: If $X_1, \dots, X_M$ are independent sub-Gaussian random variables, then
	\begin{align*}
	\prb{ \bigg\vert \sum_{i=1}^M  X_i\bigg\vert \geq t} \leq e \cdot \exp\left(- \frac{Ct^2}{\gamma^2}\right),
	\end{align*}
	with $\gamma= \sum_{i=1}^M \norm{X_i}_{\psi_2^2}^2$.
	\item There exists a universal constant $C>0$ with the following property: Suppose that $X= (X_1, \dots, X_q) \in \R^{q}$ is a random vector with independent, sub-Gaussian entries. Let further $L$ be a fixed linear map from $\R^q$ to $\R^q$. Then we have
	\begin{align*}
	\prb{ \abs{ \sprod{X, LX} - \erw{\sprod{X,LX}}}>t} \leq 2\exp\left( -C \min \left(\frac{t^2}{R^4\norm{L}_{HS}^2},\frac{t}{R^2\norm{L}}\right) \right)
	\end{align*}
	with $R= \max_{\ell=1, \dots q} \norm{X_\ell}_{\psi_2}$.
	\end{enumerate}
\end{theorem}

Now we are prepared to prove Theorem \ref{thm:phaseTrans}. Note that we will use the same dual certificate as for the proof of the main theorem of \cite{FlKei} and that the probabilistic tool will also be Hanson-Wright inequality. However, the proof is considerable more sophisticated.

\begin{proof}[Proof of Theorem \ref{thm:phaseTrans}]

	We first prove \textbf{Part \emph{i)}} of Theorem \ref{thm:phaseTrans}, hence, we assume that the measurement matrix $A$ is a biased partial random circulant matrix.  To make notations easier we enlarge $A$ by inserting zero-rows for indices not in $\Theta$. Hence, we define
	\begin{align}
	A=\mu \one+ \Phi_{\Theta}(b),
	\end{align}
	where
	\begin{align*}
	(\Phi_{\Theta})_{k,j}=\begin{cases}
	b_{j-k\imod N} & \text{if}\quad k\in \Theta\\
	0 & \text{else}
	\end{cases} \qquad \text{and}\qquad \one_{k,j}=\begin{cases}
	1 & \text{if}\quad k\in \Theta\\
	0 & \text{else}
	\end{cases} ,
	\end{align*}
	and $b\in \R^N$ is the given sub-Gaussian vector. This matches the aforementioned measurement process; the vector $Ax_0$ is only enlarged by some zeros. Further we define $\beta_0$ to be the sparser of the two vectors $x_0$ and $\one-x_0$, i.e.,
	\begin{align}
	\beta_0=\begin{cases}
	x_0 & \text{if } \|x_0\|_0\le \|\one-x_0\|_0,\\
	\one-x_0 & \text{else}.
	\end{cases}
	\end{align}

	As in \cite{FlKei} we define the dual certificate to be
	\begin{align}
	\nu=\rho \one +\Phi \beta_0-M^{-1}\sprod{\Phi\beta_0,\one}\one, \qquad 	\text{where}\quad \rho=-\frac{\sigma^2}{4\mu},
	\end{align}
	and prove that $A^*\nu\in H_S^t$, where $S=\supp \beta_0$ and $t=\frac{M\sigma^2}{16}$. This particularly means we prove for $i\in [N]$
	\begin{align}\label{eqn:goal}
	\sprod{\nu,A e_i}=\sprod{A^*\nu, e_i}=(A^*\nu)_i\begin{cases}
	\le -t & \text{if } i \in S\\ \ge t  & \text{if } i \notin S.
	\end{cases}
	\end{align}
	A simple calculation yields
	\begin{align}
	\sprod{\nu,A e_i}&=\rho\mu M+\rho \sprod{\one, \Phi_\Theta e_i}+\sprod{\Phi_\Theta\beta_0,\Phi_\Theta e_i}-M^{-1}\sprod{\Phi_\Theta\beta_0,\one}\sprod{\one, \Phi_\Theta e_i}\\&=:\rho\mu M+\rho X_1(i)+X_2(i)-M^{-1}X_3(i).
	\end{align}

	We now estimate the numbers $X_1(i), X_2(i), X_3(i)$ for each $i\in S$ and $i\notin S$ separately.
	\newline

	\noindent\textbf{Estimation of $X_1$:}\\
	 We start with $X_1$. For every $i\in [N]$,
	\begin{align}
	X_1(i)=\sprod{\one, \Phi_\Theta e_i}=\sum_{l\in \Theta} (\Phi_\Theta)_{l,i}=\sum_{l\in \Theta} b_{i-l\imod{N}}
	\end{align}
	is a sum of $M$ independent sub-Gaussian variables with sub-Gaussian norm $R$. Thus it follows from Part i) of Theorem \ref{ProbTools} that
	\begin{align}
	\Pr(\abs{X_1(i)}\ge \theta_1)\le e\exp\left(-\frac{C\theta_1^2}{MR^2}\right),
	\end{align}
	for every $i\in [N]$.
	The estimations of $X_2$ and $X_3$ are a slightly more involved. Let us start with $X_2$.
	\newline

	\noindent \textbf{Estimation of $X_2$:}\\
	 For every $i\in [N]$ it holds true that
	\begin{align*}
	X_2(i)=\sprod{\Phi_\Theta \beta_0, \Phi_\Theta e_i}=\sum_{j=1}^N\sum_{k\in S}(\Phi_\Theta)_{j,k}(\Phi_\Theta)_{j,i}=\sum_{k\in S}\sum_{j\in \Theta}b_{k-j\imod{N}}b_{i-j\imod{N}},
	\end{align*}
	and therefore
	\begin{align}
	\E (X_2(i))=\sum_{k\in S}\sum_{j\in \Theta}\sigma^2\delta_{k-j\imod{N},i-j\imod{N}},
	\end{align}
	where for  $j,k\in[N]$ the number $\delta_{j,k}$ is equal to one for $j=k$ and to zero otherwise. Now it holds true that $k-j\imod{N}=i-j\imod{N}$ if and only if $k=i$ and therefore
	\begin{align}
	\E (X_2(i))=\begin{cases}
	\sum_{j\in\Theta}\sigma^2 \delta_{i-j,i-j} & \text{if } i\in S\\
	0 & \text{if } i \notin S
	\end{cases}\quad=\begin{cases}
	M\sigma^2 & \text{if } i\in S\\
	0 & \text{if } i \notin S.
	\end{cases}
	\end{align}

	To estimate the deviation from this expected value we want to use Hanson-Wright inequality. Thus we want to define a map  $L(i):\R^N\to \R^N$ such that $\sprod{b,L(i)b}=X_2(i)$ for all $i\in [N]$. We therefore define the map $L(i):\R^N\to \R^N$, $(v_1,\dots,v_N)\mapsto (w_1,\dots,w_N)$ with
	\begin{align}
	w_j=\begin{cases}
	\sum_{k\in S}v_{k-i+j\imod{N}} & \text{if } j\in \Theta_i\\
	0 & \text{else},
	\end{cases}
	\end{align}
	where $\Theta_i:=i-\Theta$.	Then it indeed holds true that
	\begin{align}
	\sprod{b,L(i)b}=\sum_{j=1}^Nb_j (L(i)b)_j=\sum_{j\in \Theta_i} b_j\sum_{k\in S}b_{k-i+j\imod{N}}=\sum_{j\in \Theta}b_{i-j\imod{N}}\sum_{k\in S}b_{k-j\imod{N}}=X_2(i).
	\end{align}
	Thus, to apply the Hanson-Wright inequality we just need to estimate the Hilbert-Schmidt norm $\|L(i)\|_{HS}$ and the operator norm $\|L(i)\|$. Note that $L$ is a linear map and we therefore can rewrite it as matrix map. The corresponding matrix, which we also call $L(i)=(L_{j,l})_{j,l=1}^N$ is given by
	\begin{align}
	L(i)_{j,l}=\begin{cases}
	1 &\text{if}\; j\in \Theta_i\; \text{and}\; l\in S_{j-i}\\
	0 & \text{else},
	\end{cases}
	\end{align}
	where $S_{j-i}=j-i+S$. Thus, one easily verifies that $\|L\|_{HS}=M|S|=Ms$. To estimate $\|L\|$ we use the Gershgorin circle Theorem \ref{thm:Gers}. For $j\in \Theta_i$ we have either $L(i)_{j,j}=1$ or $L(i)_{j,j}=0$ and $R_j=s-1$ or $R_j=s$. For $j\notin \Theta_i$ we have $L(i)_{j,j}=0$ and $R_j=0$. Thus by Gershgorin circle theorem all eigenvalues of $L(i)$ lie in the circle $D(0,s)$ and the operator norm can be estimated by $\|L(i)\|\le s$.
	Hanson-Wright inequality therefore implies that there is a universal constant $C>0$ such that for $i\notin S$
	\begin{align}
	\prb{\abs{X_2(i)}>\theta_2}\le 2\exp\left(-C\min\left(\frac{\theta_2^2}{R^4Ms},\frac{\theta_2}{R^2s}\right)\right),
	\end{align}
	and for $i\in S$
	\begin{align}
	\prb{\abs{X_2(i)-M\sigma^2}>\theta_2}\le 2\exp\left(-C\min\left(\frac{\theta_2^2}{R^4Ms},\frac{\theta_2}{R^2s}\right)\right).
	\end{align}
	\newline

	\noindent \textbf{Estimation of $X_3$:}\\
	The estimation of $X_3(i)$ is even more involved. We can simplify
	\begin{align*}
	X_3(i)=\sprod{\Phi\beta_0,\one}\sprod{\one, \Phi e_i}=\beta_0^*\Phi^*\one\one^*\Phi e_i=\sum_{k\in S}\sum_{m\in \Theta}\sum_{l\in \Theta}b_{k-m\imod{N}}b_{i-l\imod{N}},
	\end{align*}
	because $(\Phi^*\one\one^*\Phi)_{k,n}=\sum_{m\in \Theta}\sum_{l\in \Theta}b_{k-m\imod{N}}b_{n-l\imod{N}}$. We start by estimating the expected value of $X_3(i)$:
	\begin{align}\label{eqn:E3kn}
	E_{k,n}:&=\E{(\Phi^*\one\one^*\Phi)_{k,n}}=\sum_{m\in \Theta}\sum_{l\in \Theta}\E{\left(b_{k-m\imod{N}}b_{n-l\imod{N}}\right)}\\&=\sum_{m\in \Theta}\sum_{l\in \Theta}\begin{cases} \sigma^2 & \text{if}\; k-m\imod{N}=n-l\imod{N}\\ 0 & \text{else}\end{cases}.
	\end{align}
	Note that $k-m\imod{N}=n-l\imod{N}$ if and only if $k-m-n+l\imod{N}=0$. That is, if and only if $k-m-n+l\in \{-N,0,N\}$, because $k-m-n+l\in (-2N,2N)$. Let us try to identify when this is the case:

	First, suppose that $k<n$, then we have $k-n-m<0$, or more precisely either $k-n-m\in[-N,-1]$ or $k-n-m\in[-2N,-N-1]$. If the first case is true,  $l$ can only be chosen such that $k-n-m+l=0$, because $l\in [N]$ there is no possibility that  $k-n-m+l\in \{-N,N\}$. Analogously, if the second case is true, the only possibility to choose $l$ such that  $k-n-m+l\in\{-N,0,N\}$ is $l=m+n-k-N$. In other words for fixed $k<n$ and $m\in[N]$ there is exactly one $l\in [N]$ such that $k-m\imod{N}=n-l\imod{N}$. Similarly we can show that the same is true for $k\ge n$.

	However, the sum in \eqref{eqn:E3kn} is not over $m,l\in[N]$ but over the smaller subset $m,l\in \Theta$. Thus the number matching the criterion $k-m\imod{N}=n-l\imod{N}$ is smaller than $M=|\Theta|$, more precisely:
	\begin{align}
	E_{k,n}=\begin{cases}
	\abs{\Theta\cap \left((k-n+\Theta)\cup(N+k-n+\Theta)\right)}\sigma^2 & \text{if}\; k<n,\\
	M\sigma^2 &\text{if}\; k=n,\\
	\abs{\Theta\cap \left((k-n+\Theta )\cup(- N+k-n+\Theta)\right)}\sigma^2 & \text{if}\; k<n.
	\end{cases}=\abs{\Theta\cap(k-n+\Theta)}\sigma^2
	\end{align}

	It holds true that for $i\notin S$
	\begin{align}\label{eqn:EX3nS}
	\E(X_3(i))=\sprod{\beta_0,(E_{ki})_{k=1}^N}=\sum_{k\in S} E_{ki}=\sum_{k\in S}\abs{\Theta\cap(k-i+\Theta)}\sigma^2\in [0,sM\sigma^2]
	\end{align}
	and for $i\in S$ that
	\begin{align}
	\E(X_3(i))\in [M\sigma^2,sM\sigma^2].\label{eqn:EX3S}
	\end{align}

	Now we can compute the probability that $X_3(i)$ deviates from its expected value. We again aim to apply the Hanson-Wright inequality. For this we define $L^3(i):\R^N\to\R^N$, $(v_1,\dots,v_N)\mapsto (w_1,\dots,w_N)$ with
	\begin{align}
	w_l=\begin{cases}
	\sum_{m\in \Theta}\sum_{k\in S} v_{k-m\imod{N}} & \text{if}\; l\in i-\Theta,\\0&\text{else}.
	\end{cases}
	\end{align}
	This yields $X_3(i)=\sprod{b,L^3(i)b}$. To compute the Hilbert-Schmidt norm and operator norm of $L_3(i)$, we further define the matrices $(K^1_{n,m})_{n,m=1}^N$ and $(K^2_{i,j})_{i,j=1}^N$ by
	\begin{align}
	K^1_{n,m}=\begin{cases}
	1 & \text{if}\, n\in i-\Theta , m\in \Theta\\0 & \text{else},
	\end{cases} \quad \text{and} \quad 	K^2_{k,l}=\begin{cases}
	1 & \text{if}\, k\in \Theta , l\in -k+S\\0 & \text{else}.
	\end{cases}
	\end{align}
	It is then easy to verify, that $K^1K^2v=L_3(i)(v)$. Now the Hilbert-Schmidt norm of $K^1$ is given by $\|K^1\|_{\text{HS}}=M^2$ and of $K^2$ by $\|K^2\|_{\text{HS}}=Ms$. Thus
	\begin{align}
	\|L_3(i)\|_{\text{HS}}=\|K^1K^2\|_{\text{HS}}\le \|K^1\|_{\text{HS}}\|K^2\|_{\text{HS}}=M^3s.
	\end{align}
	On the other hand it holds true that
	\begin{align}
		(K^1K^2)_{m,n}=\begin{cases}
		\sum_{l\in \Theta\cap (S-n)}1 &\text{if}\; m\in i-\Theta\\
		0 & \text{else}.
		\end{cases}
	\end{align}
	By  Gershgorin circle theorem this yields  that
	\begin{align}
	\|L_3(i)\|=\|K^1K^2\|\le Ms,
	\end{align}
	since for every $n\in [N]$ it holds true that $\abs{\Theta\cap (S-n)}\le s$ and therefore that the column sum of $K^1K^2$ is smaller than $Ms$ for each column, since the $m$-th entry of each column of $K^1K^2$ is equal to zero if $m\notin i-\Theta$.
	By the Hanson-Wright inequality it follows
		\begin{align}
	\prb{\abs{X_3(i)-\E(X_3(i))}>\theta_3}\le 2\exp\left(-C\min\left(\frac{\theta_3^2}{R^4M^3s},\frac{\theta_3}{R^2Ms}\right)\right).
	\end{align}
	In particular it follows for $i\notin S$
	\begin{align}
	\prb{X_3(i)< -\theta_3}&\le 	\prb{X_3(i)<\E(X_3(i)) -\theta_3}\le \prb{X_3(i)-\E(X_3(i))< -\theta_3}\le	\prb{\abs{X_3(i)-\E(X_3(i))}>\theta_3}\\&\le 2\exp\left(-C\min\left(\frac{\theta_3^2}{R^4M^3s},\frac{\theta_3}{R^2Ms}\right)\right),
	\end{align}
	where we used \eqref{eqn:EX3nS} in the first step. For $i\in S$ it follows
	\begin{align}
	\prb{X_3(i)>\theta_3+M^2\sigma^2}&\le 	\prb{X_3(i)>\theta_3+\E(X_3(i))}\le \prb{X_3(i)-\E(X_3(i))> \theta_3}\\&\le	\prb{\abs{X_3(i)-\E(X_3(i))}>\theta_3}\le 2\exp\left(-C\min\left(\frac{\theta_3^2}{R^4M^3s},\frac{\theta_3}{R^2Ms}\right)\right),
	\end{align}
	where we used \eqref{eqn:EX3S}.

	Finally we are able to estimate the probability that Equation \eqref{eqn:goal} is true for $t=\frac{M\sigma^2}{16}$. To this end remember that $\rho=-\frac{\sigma^2}{4\mu}$ and choose
	\begin{align}
	\theta_1 =\frac{\mu M}{4}, \qquad \theta_2 =\frac{\abs{\rho}\mu M}{4}, \qquad \theta_3 =\frac{\abs{\rho}\mu M^2}{4}.
	\end{align}

	Using that by Equation \eqref{eqn1:main} we have in particular $M>2s$ we derive for  $i\in S$
	\begin{align}
	\sprod{\nu,A e_i}&=\rho\mu M-\abs{\rho} X_1(i)+X_2(i)-M^{-1}X_3(i)\ge \rho\mu M-\abs{\rho}\theta_1+M\sigma^2-\theta_2-s\sigma^2-M^{-1}\theta_3\\&=\frac{7\rho\mu M}{4}+(M-s)\sigma^2\ge\frac{7\rho\mu M}{4}+\frac{M}{2}\sigma^2 =-\frac{7}{16}M\sigma^2-\frac{1}{2}M\sigma^2=\frac{M\sigma^2}{16}
	\end{align}
	with a failure probability no larger than
	\begin{align}
	s\left(e\exp\left(-\frac{C\mu M}{16R^2}\right)+2\exp\left(-C\min\left(\frac{\rho^2\mu^2M}{16R^4s},\frac{\abs{\rho}\mu M}{4R^2s}\right)\right)+ 2\exp\left(-C\min\left(\frac{\rho^2\mu^2 M}{16R^4s},\frac{\rho\mu M}{4R^2s}\right)\right)\right).
	\end{align}

	On the other hand we can estimate for $i\notin S$
	\begin{align}
		\sprod{\nu,A e_i}&\le \rho\mu M +\abs{\rho}\theta_1+\theta_2+M^{-1}\theta_3=\frac{\rho \mu M}{4}=-\frac{M\sigma^2}{16}
	\end{align}
		with a failure probability no larger than
	\begin{align}
	(N-s)\left(e\exp\left(-\frac{C\mu M}{16R^2}\right)+2\exp\left(-C\min\left(\frac{\rho^2\mu^2M}{16R^4s},\frac{\abs{\rho}\mu M}{4R^2s}\right)\right)+ 2\exp\left(-C\min\left(\frac{\rho^2\mu^2 M}{16R^4s},\frac{\rho\mu M}{4R^2s}\right)\right)\right).
	\end{align}
	This finishes the proof of Part \emph{i)} of Theorem \ref{thm:phaseTrans}.
\newline

	Now we aim to prove \textbf{Part \emph{iii)}}. Applying Proposition \ref{prop:noise}, we particularly need to prove the boundedness of the dual certificate $\nu$, i.e., $\|\nu\|_2\le r$, for some $r>0$. First, note that
	\begin{align}
	\|\nu\|_2^2\le M\rho^2+\sprod{\Phi\beta_0,\Phi\beta_0}.
	\end{align}
	Thus, we in particular need to bound $\sprod{\Phi\beta_0,\Phi\beta_0}$. It is easy to verify that
	\begin{align}
	\sprod{\Phi\beta_0,\Phi\beta_0}=\sum_{n\in \Theta} \sum_{k\in S}\sum_{l\in S}b_{k-n\imod{N}}b_{l-n\imod{N}}.
	\end{align}
	Because $k-n\imod{N}=l-n\imod{N}$ if and only if $k=l$ we obtain
	\begin{align}
	\E(\sprod{\Phi\beta_0,\Phi\beta_0})=\sum_{n\in \Theta} \sum_{k\in S}\sum_{l\in S}\E(b_{k-n\imod{N}}b_{l-n\imod{N}})=\sum_{n\in \Theta} \sum_{k\in S}\E(b_{k-n\imod{N}}b_{k-n\imod{N}})=Ms\sigma^2.
	\end{align}

	To estimate the deviation of $\sprod{\Phi\beta_0,\Phi\beta_0}$ from its expected value we define $L:\R^N\to \R^N$, $(v_1,\dots v_N)\mapsto (w_1,\dots,w_N)$ with
	\begin{align}
	w_i=\begin{cases}
	\sum_{k\in S}v_{k-i\imod{N}} & \text{if } i\in \Theta\\ 0 &\text{else}.
	\end{cases}
	\end{align}
	Then it holds true that $\sprod{\Phi\beta_0,\Phi\beta_0}=\sprod{Lb,Lb}:=\sprod{b,Kb}$, with $K:=L^*L$. To again apply the Hanson-Wright inequality we need to estimate the Hilbert-Schmidt norm $\|K\|_{\text{HS}}$ as well as the operator norm $\|K\|$ of $K$. Note that $L$ can be represented by the matrix $[L_{ij}]_{i,j=1}^N$, where
	\begin{align}
	L_{ij}=\begin{cases}
	1 & \text{if } i\in \Theta \text{ and } j\in S-i\\
	0& \text{else}
	\end{cases}=\begin{cases}
	1 & \text{if } i\in \Theta\cap S-j\\
	0& \text{else}
	\end{cases}.
	\end{align}

	Further $K$ can be represented by the matrix $[K_{kl}]_{k,l=1}^N$ with
	\begin{align}
	K_{kl}=\sum_{i=1}^N L_{ki}^*L_{il}=\sum_{i\in \Theta\cap(S-k)\cap (S-l)}1=\abs{\Theta\cap(S-k)\cap (S-l)}.
	\end{align}
	By Gershgorin circle theorem all eigenvalues of $K$ lie in the circle $D(0,\sum_{k\in[N]}K_{kl})$ for all $l\in [N]$ and
	\begin{align}
	\sum_{k\in[N]}K_{kl}=\sum_{k\in[N]}\abs{\Theta\cap(S-k)\cap (S-l)}\le\sum_{k\in[N]}\abs{(S-k)\cap (S-l)} \le s^2,
	\end{align}
	where the last step follows from the following fact: Let $l\in [N]$ and $S-k=\{k_1,\dots, k_s\}$ then for $i\in [s]$ it holds true that $k_i\in K-(k_j-k_i)$ for each $j\in [s]$. Thus, each $k_i\in S-k$ is contained in exactly $s$ sets of the form $S-r$.
	Therefore, we can conclude $\|K\|\le s^2$ and $\|L\|=\sqrt{\lambda_{\text{max}}(L^*L)}=\sqrt{\lambda_{\text{max}}(K)}=s$, where $\lambda_{\text{max}}$ denotes the largest eigenvalue. Further it is easy to verify by the matrix representation that $\|L\|_{\text{HS}}=\sqrt{Ms}$ and therefore by \eqref{eqn:EstHS}
	\begin{align}
	\|K\|^2_{\text{HS}}=\|L^*L\|^2_{\text{HS}}\le \|L^*\|^2\|L\|^2_{\text{HS}}\le Ms^3.
	\end{align}

	By the Hanson-Wright inequality it now follows
	\begin{align}
	\prb{\abs{\sprod{\Phi\beta_0,\Phi\beta_0}-Ms\sigma^2}\ge Ms\sigma^2 }\le2 \exp\left(-c\min\left(\frac{M\sigma^4}{sR^4},\frac{M\sigma^2}{R^2s}\right)\right).
	\end{align}
	Thus $\sprod{\Phi\beta_0,\Phi\beta_0}\le 2Ms\sigma^2$ with high probability. And more precisely we derive for the dual certificate that
	$\|\nu\|_2^2\le M\sigma^2\left(\frac{\sigma^2}{16\mu^2}+2s\right)$ with probability $1-\varepsilon$ if $M\gtrsim \max\left(\frac{R^4}{\sigma^4},\frac{R^2}{\sigma^2}\right)\ln\left(\frac{2}{\varepsilon}\right)s$ for some $\varepsilon>0$.
	\newline

	It remains to prove \textbf{Part \emph{ii)}}. For this purpose it is enough to argue that the previous proof also applies to Toeplitz matrices of the form \eqref{eqn:BiasedCirc}. To see this, note that Toeplitz matrices are submatrices of circulant matrices. More precisely, let  $T=T(c_{-N+1},c_{-N+2},\dots, c_{N-1})\in \R^{N,N}$ then T is the submatrix of $\Phi([c_0,\dots,c_{N-1},c_{-N+1},\dots,c_{-1}])\in \R^{2N-1,2N-1}$ consisting of the first $N$ columns and rows of $\Phi$, i.e., $T_{i,j}=C_{i,j}$ for $i,j\in [N]$.

Define $A=\mu\one+T_{\Theta}$ and $B=\mu\one+\Phi_{\Theta}$. For the dual certificate $\nu$ and $i\in [N]$ it then holds true that $\sprod{\nu,A e_i}=\sprod{\nu,B\tilde{e}_i}$, where $\tilde{e}_i$ denotes the $i$-th canonical vector in $\R^{2N-1}$. Further note that $Ax=B[x \quad\vec{0}]$ for $x\in \R^N$, where $\vec{0}\in \R^{N-1}$.

Thus the former proof shows that $B^*\nu\in \tilde{H}_S^t:=\left\{w\in \R^{2N-1}: w_i\le -t\text{ for } i \in S \text{ and } w_i\ge t \text{ for } i\in [N]\setminus S\right\}$ for some $t>0$. Note that for $w\in\tilde{H}_S^t$, the last $N-1$ entries of $w$ can be arbitrary. Moreover it is easy to prove similarly as in \cite{FlKei} (cf. Proposition 2.3 in \cite{FlKei}) that this is equivalent to $$\left\{x\in [0, 1]^{2N-1}: Bx=B\one_S\right\}\cap \left\{x\in[0,1]^{2N-1}: x_{i}=0, i=N+1,\dots,2N-1 \right\}=\one_S\in \R^{2N-1}.$$  Hence, $\left\{x\in [0, 1]^{N}: Ax=A\one_S\right\}=\one_S\in \R^{N}$, under same assumption of Theorem \ref{thm:phaseTrans}.
\end{proof}

\begin{remark}
	Note that the (implicit) constant in Equation \eqref{eqn1:main} is doubled in comparison to the result in \cite{FlKei} for non structured matrices. The main reason is the pessimistic estimation of the expected value of $X_3(i)$ in Equation \eqref{eqn:EX3S}. Particularly, $\E{X_3(i)}=sM\sigma^2$ can only be true for very artificial choices of $\Theta$ and $S$. Suppose $\Theta=\{m,m+k,m+2k,\dots,m+(M-1)k\}$ such that $Mk=N$ and $S_i=\{0,k,2k,3k,(s-1)k\}$ then  $\E{X_3(i)}=sM\sigma^2$. However, if there is no $k\in S$ such that $\Theta=\{m,m+k,m+2k,\dots,m+(M-1)k\}$ then $\abs{\Theta\cap (k+\Theta)}\le (M-1)$. Moreover, if $S_i\neq \{0,k,2k,3k,(s-1)k\}$ for some $k$, then for $l\in S_i, l\neq k$, it holds true that $\abs{\Theta\cap (l+\Theta)}\le (M-1)$.

	One possibility to ensure that $\E(X_3(i))\le\frac{Ms}{2}$, which gives the same constant as in \cite{FlKei}, is to choose $\Theta=\{m_1>m_2>\dots m_M\}$ such that every possible distance between $m_i$ and $m_{i+1}$ arises at most $M/2$-times. This might be possible because we may assume that $M\le \frac{N}{2}$ by what the numerics indicate (see Section \ref{sec:numeric}).
\end{remark}


TITLE: Question about limit points.
QUESTION [3 upvotes]: I just have a short (most likely trivial) question regarding this assignment:

Let $(x_n)_{n\in\mathbb{N}}$ be a (real) subsequence. Let $A \subset\mathbb{R}$ be the set of limit points in $(x_n)_{n\in\mathbb{N}}$ and $B \subset\mathbb{R}$ the set of limit points in $M = \{x_n\,|\,n\in\mathbb{N}\}$.
(Prove that $B \subset A$ and show that there is a sequence so that $A$ is an infinite set an $B = \varnothing$.)

I am just wondering what exactly the difference is between the set of limit points of a sequence (here: $(x_n)_{n\in\mathbb{N}}$) and set of limit points of a set (here: $M = \{x_n\,|\,n\in\mathbb{N}\}$).
Thanks in advance.

REPLY [0 votes]: "Consider the sequence $(x_n)=1,3,1/2,3,1/4,3,1/8,3,….$ Then 3 is a limit point of a subsequence of our sequence. But the set of points of the form $x_n$ is ${3,1,1/2,1/4,…}$ and does not have 3 as a limit point."


TITLE: Question about the proof of the Fundamental Theorem of Homomorphisms
QUESTION [0 upvotes]: Theorem:
Let  $\phi: G \rightarrow H$ be a group homomorphism.
Then $\operatorname{Ker}(\phi)$ is a normal subgroup of G. $\phi(G)$ is a subgroup of H and the map
$\phi'$: $G/\operatorname{Ker}(\phi) \rightarrow \phi(G)$,
$a\operatorname{Ker}(\phi)\mapsto \phi(a)$ is a group isomorphism.
My question relates to the part where it is shown that $\phi'$ is surjective. From the proof:
Because of $\phi'(G/N)=\phi(G)$, $\phi'$ is obviously surjective.
So why do we know that $\phi'(G/N)=\phi(G)$ holds?

REPLY [1 votes]: Anything in $\phi(G)$ takes the form $\phi(a)$ for $a \in G$, and the coset $aN$ will map to $\phi(a)$.  Check the definition of $\phi'$.


TITLE: Determining whether a set of vectors is a subspace
QUESTION [1 upvotes]: So I have a set of vectors
$U = \{(r, 3s, r-2)\ |$ $r$ and $s$ in $R$}
If I let $r = 1$, and $s = 1$, I get a vector (1, 3, -1).
If I multiply that by 2, I get the vector (2, 6, -2).
Since the new vector is not obtainable by substitution, this set of vectors is not in $R^3$.
At first instead of multiplying the vector by 2, I was using a constant $c$. However, I ended up with $(cr, 3cs, c(r-2))$. Since $r$ and $s$ are real numbers, they are still real numbers when multiplied by $c$. So I first thought it was closed under multiplication, but I'm obviously wrong.
Can someone explain to me how to properly support my answer using constants?

REPLY [1 votes]: You really should take Harto's suggestion to merely check whether $0$ is in the set, but you can use your calculation.
Namely, to check whether the scalar multiple $\big(cr, 3cs, c(r - 2)\big)$ of a generic vector $(r, 3s, r - 2)$ is in the set $U = \{(r, 3s, r - 2) : r, s \in \Bbb R\}$, we certainly need the first coordinate to be two more than the last coordinate. So, we check: if we subtract $2$ from the first coordinate, do we get the last coordinate?
$$cr - 2 \overset{?}= c(r - 2) = cr - 2c, $$
which is certainly not true whenever $c \neq 1$. Thus, only the trivial scalar multiple (scaling by $c = 1$) of any vector in $U$ is also in $U$, and it must not be a subspace.


TITLE: Relationship between $A$ is normal ans $A$ has $n$ linearly independent eigenvectors
QUESTION [0 upvotes]: I am learning matrix analysis, and one theorem states

A matrix A $\in \mathbb{C}^{n \times n}$ is unitarily similar to a diagonal matrix if and only if $A$ is normal ($AA^H=A^HA$)

However, from the previous study I learnt that $A \in  \mathbb{C}^{n \times n}$ is diagonalizable when it has $n$ independent eigenvectors. So it seems that the two claims are equivalent. But I do not know why this random thought is true or not
Could anyone help me, thank you in advance.

REPLY [2 votes]: Hint: ponder on the difference between the following:
$A \in  \mathbb{C}^{n \times n}$ is diagonalizable - this means that there exists a basis of your space consisting of eigenvectors of $A$.
$A \in  \mathbb{C}^{n \times n}$ is unitarily diagonalizable - this means that there exists a basis of your space consisting of mutually orthogonal eigenvectors of $A$.


TITLE: Unable to find next number of perfect numbers.
QUESTION [1 upvotes]: Perfect numbers are $6, 28, 496, 812, \dots $
From this source

Here “double proportion” means that each number is twice the preceding number, as in $1, 2, 4, 8, ….$ For example, $1 + 2 + 4 = 7$ is prime; therefore, $7 × 4 = 28$ (“the sum multiplied into the last”) is a perfect number.

Now following this rule $3$rd perfect number should be
$1+2+4+8=15$ and $15×8=120$ but $120$ is not next perfect number.
Can someone help me where I am going wrong?

REPLY [0 votes]: Every perfect number $\mathcal{P}$ is of the form $2^{n - 1}(2^n - 1)$ such that $n$ must be prime and $2^n - 1$ is also prime. Any prime of the form $2^n - 1$ is known as a Mersenne Prime, it's appropriate symbol being $M_n$ (in most cases $M_p$ where $n = p =$ prime).
When you do $1 + 2 + 4 + 8 = 15$, you are proposing that $2^{4 - 1}(2^4 - 1)$ is a perfect number since there are four terms on the $LHS$ (Left Hand Side of the equation). Here I will write it out in a clearer way:
$$\sum_{k = 0}^n2^k = x$$
This is read as:
"The sum that goes from $2^0$ to $2^n = x$." Here the variable $k$ is used to express how it starts from $0$ then goes to $1$, $2$, $3$, $\ldots$ $n$.
$$\sum_{k = 0}^n2^k = 2^0 + 2^1 + 2^2 + 2^3 + \cdots + 2^n = x$$
This $\longrightarrow \sum$ is known as a "Capital Sigma" (where the lower case sigma is $σ$.) "Sigma" along with other fancy symbols are mainly derived from the Greek alphabet.
To spare you the math, $$\sum_{k = 1}^n2^k = x = 2^n - 1$$ So when you do $$1 + 2 + 4 + 8 = 2^0 + 2^1 + 2^2 + 2^3 = \sum_{k = 0}^32^k = 15$$ and then multiply the furthest $RHS$ (Right Hand Side of the equation) by $2^3 = 8$, you will not get a perfect number since $15$ is not prime! $15 = 3\times 5$.
A nice trick is to know what $\sum_{k = 0}^n2^k$ is, is to just count how many numbers are there from $0$ to $n$ including $0$ and $n$ themselves. Let's call that number $d$. Then, $$\sum_{k = 0}^n2^k = 2^{d - 1}$$ And since $k$ is every number from $0$ to $n$ then all you need to do is count how many terms there are on the $LHS$.
Example:
$$\sum_{k = 0}^{64}2^k = 2^0 + 2^1 + 2^2 + 2^3 + \cdots + 2^{64} = 2^{65} - 1$$ Now there is no way in telling if $2^{65} - 1$ is prime just by looking at it... unless you know that if you want $2^n - 1$ to be prime, then $n$ must also be prime. And since $65$ is obviously divisible by $5$ (and $13$), then $2^{65} - 1$ is not prime, or at least a Mersenne Prime, so $$2^{65 - 1}(2^{65} - 1) = 2^{64}(2^{65} - 1) \neq \mathcal{P}$$ such that $\mathcal{P}$ is a perfect number. I hope now you can find a solution for $n$ in the following equation: $$\sum_{k = 0}^n2^k = \frac{496}{2^{n - 1}}$$ And perhaps by just making $496$ the subject (making it alone on the $RHS$) you can figure out why $\sum_{k = 0}^n2^k = 2^n - 1$ if you haven't already. Hope I helped! :)


TITLE: Annuity and Perpetuity
QUESTION [0 upvotes]: A thirty-year annuity X has annual payments of $\$1,000$ at the beginning of each year for twelve years, then annual payments of $\$2,000$ at the beginning of each year for eighteen years. A perpetuity $Y$ has payments of $Q$ at the end of each year for twenty years, then payments of $3Q$ at the end of each year thereafter. The present values of $X$ and $Y$ are equal when calculated using an annual effective discount rate of $10\%$ . Find $Q$.

We have that the discount rate is $d=.1$. Therefore $i=\frac{.1}{.9}=.11$. Our present values are:
$$X=1000\ddot{a}_{\overline{12}|i}+2000\ddot{a}_{\overline{18}|i}(1+i)^{-12}$$$$Y=Qa_{\overline{20}|i}+3Qa_{\overline{\infty}|i}$$
My instructor then writes that if we set these equal to each other we get $12040.14=11.75Q$. I haven't the slightest on how he simplified $Y$ to $11.75Q$, I've tried all the formulas for present value of annuity and perpetuity but it's not correct.

REPLY [2 votes]: The expression you wrote for the present value of the perpetuity is not correct, because the present value of the payments of $3Q$ should be discounted by the $20$ years of deferral that passes after the first $20$ annual payments of $Q$ are made.  That is to say, $$Y = Qa_{\overline{20}\rceil i} + 3Q v^{20} a_{\overline{\infty}\rceil i},$$ where $v = (1+i)^{-1} = 1 - d = 0.9$ is the present value discount factor.  Alternatively, because the interest rate is fixed across all payments, you may equivalently regard the cash flow $Y$ as comprising two level perpetuities-immediate, one that pays $Q$, and the other paying $2Q$ after $20$ years:  $$Y = Qa_{\overline{\infty}\rceil i} + 2Q v^{20} a_{\overline{\infty}\rceil i} = Q(1+2v^{20})a_{\overline{\infty}\rceil i} = \frac{1+2v^{20}}{i} Q,$$ which is a simpler expression to evaluate.  In both cases, the result is $11.1884Q$.


TITLE: Using the Nested Sphere theorem too
QUESTION [1 upvotes]: Let $(X,d)$ is a complete metric space. Use the Nested Spehere theorem to show that any countable intersection of open dense sets in $X$ is not empty.
Let $\mathcal{U}=\{U \subset X:\ U \ \text{is open dense sets in }\ X \}.$ Let $U_1,U_2,U_3,...$ be any elements in $\mathcal{U}$. Since for each $n \in \mathbb{Z^+},$ $\bar{U_n}=X$, then for any $x \in U_k \subset X$ and any $\epsilon>0$ we have that $$\emptyset \neq B_\epsilon(x) \cap  U_m$$
for any $m$ positive integer. So for $\epsilon_0>0$ such that $x \in B_{\epsilon_0}(x) \subseteq U_k$, we have  So $$\emptyset \neq B_{\epsilon_0}\cap U_m \subseteq U_k\cap U_m  $$ for any $k,m$ positive integer. Does this guarantee that $\displaystyle \bigcap_{n=1}^\infty U_n \neq \emptyset$? Also I am getting stack with the part regards using the Nested Sphere theorem.
Thanks for any help!

REPLY [1 votes]: The idea is of course to find a sequence of balls $B_{\epsilon_n}(x_n)\subseteq B_{\epsilon_{n-1}}(x_{n-1})\subseteq...\subseteq B_{\epsilon_1}(x_1)$ with $\epsilon_n\to0$ so that $B_{\epsilon_n}(x_n)\subseteq \bigcap_{k=1}^nU_k$. By the nested ball theorem the sequence $x_1,...,x_n$ converges to some $x$. This $x$ necessarily lies in every $B_{\epsilon_n}(x_n)$, hence in every intersection $\bigcap_{k=1}^n U_k$, hence in $\bigcap_{k=1}^\infty U_k$.
How can you find such a sequence? Start with an arbitrary $x_1\in U_1$. Since $U_1$ is open is a radius $\epsilon_1$ so that $B_{\epsilon_1}(x_1)\subseteq U_1$. Further since $U_1, U_2$ are open dense so is $U_1\cap U_2$ and $B_{\epsilon_1}(x_1)\cap (U_1\cap U_2)$ is non-empty. In particular there is some point $x_2$ in that intersection and some radius $\epsilon_2$ so that that $B_{\epsilon_2}(x_2)\subseteq B_1(x_1)\cap (U_1\cap U_2)$. By making $\epsilon_2$ smaller we can assume it to be $≤\epsilon_1/2$.
That last step was actually an induction argument. Given an $x_n$ and an $\epsilon_n$ we know that $B_{\epsilon_n}(x_n)\cap(U_1\cap...\cap U_{n+1})$ must be non-empty and open, so we can find some $x_{n+1}$ and $\epsilon_{n+1}$ so that $B_{\epsilon_{n+1}}(x_{n+1}) \subseteq B_{\epsilon_n}(x_n)\cap ( U_1\cap...\cap U_{n+1})$ and by making $\epsilon_{n+1}$ smaller we may assume $\epsilon_{n+1}≤\epsilon_n/2$.
These sequences $x_n, \epsilon_n$ then satisfy the conditions that we were looking for.