TITLE: How would you go about this algebra problem? (order of operations?)
QUESTION [1 upvotes]: Okay, so my teacher gave us this to solve:
$$a + b/c = 2$$
In this equation he explained that there were many ways to do it. However, we were told to do it with at least two negative numbers. I was a bit stuck at this one, however, more than a couple of students in my class had figured it out anyway.
So one of the solutions to this problem was to do $ -1 -1/-1 = 2$ ( $-$ & $+$ becomes $-$ and then $-$ & $-$ becomes $+$). (Of course assigning $a$, $b$ and $c$ $-1$ as a value). Another solution was to do for example $-5 + 1/-2$ ($a=-5$ $b=1$ & $c=-2$ and the $- / -$ is $+$).
However, there was still something that didn't seem right, although I could see the logic of how these made the answer. But then I realized what was bugging me. The order of operations, which states that you always should do multiplication and division before addition and subtraction (which is something these equations do not follow). So I raised my hand and asked the teacher about this, and he just told me that this wasn't the case for these kind of math problems.
He also told me that he had no logical answer to why it wasn't.
However, I also asked another (outside) person about this (whom is exeptionally good at math), and she told me that it didn't matter if it was letters (algebra) or just normal numbers, the order of operations would still have to be used. In which case what I learned in class is wrong. So my question is, what is right and what is wrong? And also why?
If anyone could help med with this it'd be awesome!
Kind regards ~

REPLY [0 votes]: You would have to do what is on top of the equation; or you could divide the equation as it is, and still get the same answer. So as you were confused about the order of operations, here is a brief explanation given your equation. Suppose we have your equation, -1-1/-1=2, we could divide at the beginning, so that when -1/-1=1, both of the numbers on the top, we would get the equation 1+1=2 if we were to do your equation through strict pemdas, we would get-1-1/-1=2, so that it becomes 1+1=2. Many people omit strict use of the order of operations because the answer is still equivalent, so if we were to do subtraction first, we would get -2/-2=2 which is a true statement


TITLE: Does energy of photon change due to some external magnetic field?
QUESTION [1 upvotes]: I came to know about the energy of photon changes (decreases) while going away from the emitter (even from earth) due to gravitational field effects.
Is there any change in energy/wavelength of a photon due to some external (artificial) magnetic field or electric field?

REPLY [1 votes]: Electromagnetic fields generate gravity, and therefore the answer is yes: the energy of a photon changes as it moves through a non-homogeneous electromagnetic field.


TITLE: Ordinal vs interval scales
QUESTION [1 upvotes]: I am reading about mean reciprocal rank and I came across this remark:

The major problem with MRR, however, is the following: as observed
already in [19], the difference between ranks $1$ and $2$ is the same as
that between ranks $2$ and $∞$. This means that RR is not an interval
scale, it is only an ordinal scale. However, one
cannot compute the mean for an ordinal scale! Only the median would be
possible here — which would produce ties in most cases.

I get why the distance between ranks $1$ and $2$ is the same as between $2$ and $\infty$, that is because $1/1-1/2 = 1/2$ and $1/2-1/\infty = 1/2$. Why does this mean RR is an ordinal rather than an interval scale?
I can't really get my head around the mathematical definitions of the two types, and can only find vague statements online like 'interval scale is where .... the difference between two values is meaningful' under most of which MRR would seem to be fine.
The writer of that paper (http://sigir.org/wp-content/uploads/2018/01/p032.pdf) provided a reference to S.S. Stevens. On the theory of scales of measurement. Science, New Series
103(2684):677–680, June 1946. But I can't really understand what in this shows MRR is ordinal.

REPLY [0 votes]: If you take the Wikipedia example where the question is "what is the plural of torus?" and the guesses in order of belief are "torii, tori, toruses", then if tori is correct then the correct guess will be give a rank of $2$ and so a reciprocal rank score of $\frac12$.
This is independent of the degree of confidence in the various guesses: $51\%,48\%,1\%$ or $35\%,33\%,32\%$ or $97\%,2\%,1\%$ would all lead to the same reciprocal rank score of $\frac12$.  That is why it is seen as an ordinal scoring system rather than an interval scale or some other type scale; it is a score based only on rank position.


text:
\begin{document}

{\begin{flushleft}\baselineskip9pt\scriptsize

\end{flushleft}}
\vspace{18mm} \setcounter{page}{1} \thispagestyle{empty}

\begin{abstract}
In this article we calculate the profinite genus of the fundamental group  of a $n$-dimensional compact flat manifold $X$ with holonomy group of prime order. As consequence, we prove that if $n\leq 21$, then $X$ is determined among all $n$-dimensional compact flat manifolds by the profinite completion of its fundamental group. Furthermore, we characterize the isomorphism class of profinite completion of the fundamental group of $X$ in terms of the representation genus of its holonomy group.
\end{abstract}

\maketitle

\section{Introduction}

		There has been much recent study of whether residually finite groups, or classes of residually finite groups connected with geometry or topology may be distinguished from each other by their sets of finite quotient groups.

		In group theory the study in this direction started in 70-th of the last centure when Baumslag [Bau74],  Stebe [Ste72] and others found examples of finitely generated residually finite groups having the same set of finite quotients. The general question  addressed in this study can be formulated as follows:

		\begin{question}\label{question}
			To what extent a finitely generated residually finite group $\Gamma$ is  determined by its profinite completion?
		\end{question}

		The study leaded to the notion of genus $\mathfrak{g}(\Gamma)$, the set of isomorphism classes of finitely generated residually finite groups having the same set of finite quotients as $\Gamma$. Equivalently, $\mathfrak{g}(\Gamma)$ is the set of isomorphism classes of finitely generated residually finite groups having the same profinite completion isomorphic to the profinite completion $\widehat \Gamma$ of $\Gamma$. In fact, the term genus was  borrowed from integral representation theory, where for a finite group $G$  the genus of a $\Z G$-lattice $M$ is defined as the set of isomorphism classes of $\Z G$-lattices $N$ such that the $\widehat \Z G$-modules $\widehat M$ and $\widehat N$ are isomorphic.

		The study usually was concentrated to establish whether the cardinality $|\mathfrak{g}(\Gamma)|$ of   genus  is finite or  1 ( see \cite{GPS} or \cite{GS} for example).

		The recent stream of research was concentrated on important properties of manifolds that can be detected by the profinite completion (see \cite{WZ-10, WZ-16, Wil19}) or the \textquoteleft rigidity\textquoteright \ results showing that the fundamental group of certain manifolds has genus 1, i.e., determined by their profinite completions (see \cite{BCR16, BMRS18, BMRS20, Wil17}).  For the recent account of many results of these studies we refer the reader to \cite{Reid18}. There are only few papers where exact numbers or estimates of the genus appear due to the difficulties of such calculation (see \cite{GZ11, BZ, Ner19}).

		\bigskip
		We concentrate here on  $n$-dimensional compact flat manifolds. It is well known that these manifolds are well described by the famous Bieberbach’s theorems (see \cite{Cha86}). Consequently, the fundamental group $\pi_{1}(X)$ of $X$ is called Bieberbach group. Such groups are characterized as follows: a $n$-dimensional Bieberbach group  $\pi_{1}(X)$ is a torsion-free group having  a finitely generated maximal abelian torsion-free subgroup $M$ of $\pi_{1}(X)$ of finite index (see \cite{AK57}). The groups $M$ and $G=\pi_1(X)/M$ are known as the translation subgroup  and the holonomy group of $\pi_{1}(X)$ (or of $X$), respectively. A well known Auslander-Kuranishi theorem \cite{AK57} says that every finite group is the holonomy group of a compact flat manifold. Furthermore, a compact flat manifold is uniquely determined by its fundamental group, up to diffeomorphism.

		It  was proved recently in \cite{PPW} that all  Bieberbach groups of dimension $\leq 4$ are determined by their profinite completions.
		The main result of this  paper is the explicit  formula  for the genus of a $n$-dimensional Bieberbach group with holonomy group of prime order. Denote by $\Q(\zeta)$ the field of rational numbers with the $p$-th root of unity attached, by   $H(\Q(\zeta))$ its class group and by $\G(p)=G(\Q(\zeta)/\Q)$ its Galois group, the latter acts naturally on $H(\Q(\zeta))$.

		\begin{theorem}\label{main Theorem}
			Let  $\Gamma$ be a $n$-dimensional Bieberbach group whose holonomy group has prime order.

\begin{enumerate}

\item[(i)]			If all indecomposable summands of $\Z G$-module $M$ have $\Z$-rank $p-1$ except one trivial summand of $\Z$-rank $1$,  then $|\mathfrak{g}(\Gamma)|=|C_2\backslash H(\Q(\zeta))|$, where $C_2$ is the group of order $2$ acting on $H(\Q(\zeta))$ by invertion.

\item[(ii)] Otherwise $|\mathfrak{g}(\Gamma)|=|\mathcal{G}(p)\backslash H(\Q(\zeta))|$.
\end{enumerate}
		\end{theorem}

		As a consequence of this result we obtain the following statement.

		\begin{cor}\label{cor-1}
			Let $\Gamma$ be a $n$-dimensional Bieberbach group with holonomy group $G$ of prime order. Then

			$|\mathfrak{g}(\Gamma)|=1$ if and only if $|G|\leq 19$.
		\end{cor}

		In other words, Corollary \ref{cor-1} asserts that a $n$-dimensional compact flat manifold $X$ with holonomy group $G$ of prime order is determined among all $n$-dimensional compact flat manifolds by $\widehat{\pi_{1}(X)}$ if and only if $|G|\leq 19$. Furthermore, using the crystallographic restriction theorem (see \cite{Hil85}) we obtain the following statement.
		\begin{cor}\label{cor-2}
			Let $X$ be a $n$-dimensional compact flat manifold with holonomy group of prime order. If  $n\leq 21$, then $X$ is determined among all $n$-dimensional compact flat manifolds by the profinite completion of its fundamental group.
		\end{cor}

		The proof of Theorem \ref{main Theorem} uses the Charlap's classification of Bieberbach groups with holonomy group of prime order (see Subsection \ref{section-Bieberbach groups}). Furthermore, a crucial fact is the following correspondence that we establish  showing   that the genus $\mathfrak{g}(\Gamma)$ in our case coicides with the genus of the $\Z G$-lattice $M$ (in the represantation theory sense) in case (ii) of Theorem \ref{main Theorem}.

		\begin{theorem}\label{main Theorem 1} Let $M$ be a free abelian group of rank $n$ and $G$ a group of order $p$.
			Let $\Gamma_1$ and $\Gamma_2$ be $n$-dimensional Bieberbach groups which are extensions of $M$ by $G$. If  $M_1$ and $M_2$ are $G$-modules induced by the action of $\Gamma_1$ and $\Gamma_2$ on $M$, respectively, then

			\begin{enumerate}

				\item[(i)]    $\Gamma_1\cong \Gamma_2$  if and only if either $G$-modules $M_1$ and $M_2$ satisfy hypothesis (ii) of Theorem \ref{main Theorem} and are isomorphic or $M_1$ and $M_2$ satisfy hypothesis (i) of Theorem \ref{main Theorem} and  isomorphic up to a twist of $G$ by inversion.
				\item[(ii)]
				$\widehat{\Gamma}_1\cong\widehat{\Gamma}_2$  if and only if  $\widehat{M}_1\cong\widehat{M}_2$ as $G$-modules.
			\end{enumerate}
		\end{theorem}

		Throughout this paper, we use the following notations and terminology:  $\widehat{\Gamma}$ denotes the profinite completion of a group $\Gamma$ and $|S|$ denotes the cardinality of a set $S$, $p$ will be a prime number, $\zeta$ a primitive $p$-th root of unity, $H(\Q(\zeta))$ the ideal class group of the cyclotomic field $\Q(\zeta)$ with ring of integers $\Z[\zeta]$, $h_p$ the order of $H(\Q(\zeta))$, $\mathcal{G}(p)$ the Galois group of the field $\Q(\zeta)$ over $\Q$ and $G$ a cyclic group of order $p$ generated by an element $x$.

		\section{Preliminaries}

		\subsection{Modules over groups of prime order}\label{C_p-modules}

		\begin{defn}  Let $H$ be a finite group.
			A  $\Z H$-lattice is a  $\Z H$-module which is free as a $\Z$-module.
		\end{defn}

		According to \cite[Theorem 74.3]{CR62} there are exactly $2h_p+1$ indecomposable $ \Z G$-lattices (up to isomorphism). Namely denoting by $A_i \ (1\leq i\leq h_p)$   representatives of the $h_p$ distinct ideal classes of $\Q(\zeta)$, the indecomposable $ \Z G$-lattices are:
		\begin{enumerate}
			\item[(a)] the trivial module $\Z$.
			\item[(b)]  $A_i$  with action of $G=\langle x\rangle$ given by $x\cdotp a:=\zeta a$, $a\in A_i$.
			\item[(c)] $h_p$ modules $(A_i,a_i):=A_i\oplus \Z$, where  $a_i\in A_i\setminus (\zeta -1)A_i$ and the action of $G$ is defined by $x\cdotp (a,r):=(\zeta a+ ra_i,r)$, for $a\in A_i$ and $r\in \Z$.
		\end{enumerate}

		\begin{remark}\label{(A,a)=ZC}
			If $p$ does not divide $n \ (n\in \Z)$, then $(\Z[\zeta],n)\cong \Z G$ is a cyclic free $\Z G$-module (see \cite[p. 512 and p. 514]{CR62}).
		\end{remark}

		Thus we have

		\begin{prop}[\cite{CR62}, Theorem 74.3]\label{Diederichsen-Reiner}
			Every finitely generated  $\Z G$-lattice $M$ is isomorphic to a direct sum
			\begin{equation}\label{sum 1}
			M=\bigoplus_{i=1}^{c}(A_i,a_i)\oplus\bigoplus_{j=1}^{b}A_{j}\oplus \Z^{a}
			\end{equation}
			where $\Z^{a}$ is a trivial $\Z G$-module of rank $a$.
		\end{prop}

		\begin{defn}\label{exceptional}
			We will say that a $\Z G$-module $M$ is exceptional if in decomposition \eqref{sum 1} we have the invariants $a=1$ and $c=0$, i.e., if $M=\bigoplus_{j=1}^{b}A_{j}\oplus \Z$.
		\end{defn}

		Since $\mathbf{Z}_p G$ is local ring, for $\mathbf{Z}_p G$-modules we have the Krull-Schmidt-Azumaya's Theorem.

		\begin{prop}[\cite{CR81}, Theorem 6.12]\label{KSA}
			Let $R$ is a complete commutative noetherian local ring and $M$ be a finitely generated  $R$-module.
			Then $M$ is  a  direct sum of indecomposable submodules. Furthermore, if
			\begin{equation*}
			M=\bigoplus_{i=1}^{r}M_{i}=\bigoplus_{j=1}^{s}N_{j}
			\end{equation*}
			are two such sums, then $r=s$ and $M_1\cong N_{j_1},\cdots, M_r\cong N_{j_r}$, where $\{j_1,\cdots,j_r\}$ is some permutation of $\{1,\cdots,r\}$.
		\end{prop}

		There are exactly three non-isomorphic indecomposable
		$\mathbf{Z}_pG$-modules.

		\begin{prop}[\cite{HR62}, Theorem 2.6]\label{Heller-Reiner}
			The only indecomposable $\mathbf{Z}_p G$-modules (up to
			isomorphism) are   $\mathbf{Z}_p$, $\mathbf{Z}_p[\zeta]$ and $\mathbf{Z}_pG$.
		\end{prop}

		Let $M$ be a $\Z G$-lattice. Let us denote by $M_p=M\otimes_{\Z} \mathbf{Z}_p$ the $\mathbf{Z}_p G$-lattice. Note that $M_p$ is the pro-$p$ component of $\widehat{M}$.

		\begin{prop}[\cite{HR62}, Corollary 1.5]\label{HR62-Cor 1.5}
			The $\Z G$-module $M$ is indecomposable if and only if the corresponding $\mathbf{Z}_p G$-module $M_p$  is indecomposable.
		\end{prop}

		\begin{remark}\label{Remark-2}
			\begin{enumerate}
				\item[(i)]  The pro-$p$ completion of each non-zero ideal $A$ of $\Z[\zeta]$ is isomorphic to $\mathbf{Z}_p[\zeta]$ as  $\mathbf{Z}_pG$-modules, because $\mathbf{Z}_p[\zeta]$ is a local principal ideal domain.
				\item[(ii)] The pro-$p$ completion of $(A,a_0)$ is isomorphic to $\mathbf{Z}_pG$ as $\mathbf{Z}_pG$-modules, where $A$ is a  non-zero ideal of $\Z[\zeta]$. Indeed, this follows from Propositions \ref{Heller-Reiner} and \ref{HR62-Cor 1.5}.
			\end{enumerate}
		\end{remark}

		\begin{prop}[\cite{CR81}, Proposition 31.2 (ii)]\label{31.2 (ii)}
			Let $G$ be a finite group and $M$ and $N$ be $\Z G$-lattices. Then $M_q\cong N_q$ as $\mathbf{Z}_q G$-modules for all primes $q$   if and only if $M_p\cong N_p$ as $\mathbf{Z}_p G$-modules for all $p$ dividing $|G|$.
		\end{prop}

		\subsection{Galois groups acting on ideal class groups}

		The Galois group $\mathcal{G}(p)$ naturally acts on $\Q(\zeta)$ (respectively $\Z[\zeta]$) via automorphisms. In particular, $\mathcal{G}(p)$ acts on the set of ideals of $\Z[\zeta]$.

		\begin{lem}[\cite{Cha86}, Chapter IV, Exercise 6.2]\label{Exercise 6.2}
			Let $A$ and $B$ be ideals of $\Z[\zeta]$. If $A$ and $B$ are in the same ideal class, then $\sigma(A)$ and $\sigma(B)$ are in the same ideal class for any $\sigma \in \mathcal{G}(p)$.
		\end{lem}

		It follows from Lemma \ref{Exercise 6.2} that $\mathcal{G}(p)$ acts via automorphisms on $H(\Q(\zeta))$. We will denote by $\mathcal{G}(p)\backslash H(\Q(\zeta))$  the set of orbits of $H(\Q(\zeta))$ under this action.

		The cyclotomic fields of class number one were characterized by Montgomery, as well as  Uchida in 1971.

		\begin{prop}[\cite{Rib01}, p. 652]\label{h_p=1 iff p<19}
			Let $p$ be a prime number. Then $h_p=1$ if and only if $p\leq 19$.
		\end{prop}

		\begin{defn}
			Let $M$ and $N$ be $\Z G$-modules. A semi-linear homomorphism from $M$ to $N$  is a pair $(f,\varphi)$  where $f:M\rightarrow N$ is an abelian group homomorphism and $\varphi$ is  an automorphism of $G$ such that $$f(x\cdotp m)=\varphi(x)\cdotp f(m)$$ for $x\in G$ and $m\in M$.
		\end{defn}

		Let $[A]$ denote the ideal class of an ideal $A$ of $\Z[\zeta]$ and let $M(a,b,c;[A])$ be the unique (up to isomorphism) $\Z G$-lattice with invariants $a, \ b, \ c$ and $[A]$ (see \cite[Theorem 74.3]{CR62}).

		\begin{prop}[\cite{Cha86}, Chapter IV, Theorem 6.2]\label{Cha-th 6.2}
			Let $M=M(a,b,c;[A])$ and $M'=M(a',b',c';[A'])$ be $\Z G$-lattices. Then $M$ will be semi-linearly isomorphic to $M'$ if and only if $a=a', \ b=b', c=c'$ and $\sigma\cdotp [A]=[A']$ for some $\sigma\in \mathcal{G}(p)$.
		\end{prop}

		\subsection{Bieberbach groups with prime order holonomy}\label{section-Bieberbach groups}

		This subsection contains the classification of Bieberbach groups whose holonomy group has prime order. This classification is due to Charlap \cite{Cha65}.

		\begin{prop}[\cite{Cha86}, Chapter I, Proposition 4.1]\label{Cha, Prop 4.1}
			Let $\Gamma$ be a $n$-dimensional Bieberbach group. Then the translation subgroup $M$ is the unique normal, maximal abelian subgroup of $\Gamma$.
		\end{prop}

		Using the exact sequence
		\begin{equation}\label{exact sequence}
		1\rightarrow M\rightarrow \pi_{1}(X)\rightarrow G\rightarrow 1,
		\end{equation}  one sees that $M\cong \Z^n$ has a natural structure of $\Z G$-module. This defines the representation $\rho: G\rightarrow \mathrm{GL}(n,\Z)$ of the holonomy group $G$. Since $M$ is the maximal abelian subgroup, it follows that $\rho$ is faithful (i.e., $\rho$ is injective). It is well known that a representation $\rho$ induces a structure of $\Z G$-module on $M$.

		\begin{lem}\label{characterization-Bieberbach group with n(G)=1}
			Let $\Gamma$ be a $n$-dimensional Bieberbach group with holonomy group $G$ and  $M$ its maximal abelian normal subgroup. Then $M=M_{n-1}\oplus \Z$ admits a $\Z G$-decomposition, where $\Z$ is trivial module generated by $p$-th power of some element $c$ of $\Gamma$ and $\Gamma=M_{n-1}\rtimes C$ with $C=\langle c\rangle$.
		\end{lem}
		\begin{proof}
			By \cite[Theorem 2]{Szc97} we have the following exact sequence
			\begin{equation*}
			1\rightarrow M_{n-1}\rightarrow \Gamma\rightarrow \Z \rightarrow 1.
			\end{equation*}
			Since $\Z$ is free, this sequence splits as a semidirect product $\Gamma=M_{n-1}\rtimes C$. The lemma is proved.
		\end{proof}
		\begin{defn}
			A Bieberbach group $\Gamma$ with prime order holonomy group $G$ is exceptional if its maximal abelian normal subgroup $M$  is an exceptional $\Z G$-module.
		\end{defn}

		\begin{prop}[\cite{Cha86}, Chapter IV, Theorem 6.3]\label{C1-Bieberbach}
			There is a one-to-one correspondence between isomorphism classes of non-exceptional Bieberbach groups whose holonomy group has prime order $p$ and $4$-tuples $(a,b,c; \theta)$ where $a,b,c\in \Z$ are as in \eqref{sum 1} with $a> 0, \ b\geq 0, \ c\geq 0, \ (a,c)\neq (1,0), \ (b,c)\neq (0,0)$ and $\theta \in\mathcal{G}(p)\backslash H(\Q(\zeta))$.
		\end{prop}

		Note that $\mathcal{G}(p)$ is cyclic of order $p-1$ if $p>2$, and of order 2 if $p=2$. Hence, $\mathcal{G}(p)$ has a unique subgroup $C_2$ of order $2$.

		\begin{prop}[\cite{Cha86}, Chapter IV, Theorem 6.4]\label{C2-Bieberbach}
			There is a one-to-one correspondence between isomorphism classes of exceptional Bieberbach groups whose holonomy group has prime order $p$ and pairs $(b,\theta)$ where $b>0$ as in Definition \ref{exceptional},  and $\theta \in C_2\backslash H(\Q(\zeta))$.
		\end{prop}

\begin{remark}\label{charlap remark} By \cite[Remark p. 151]{Cha86} the isomorphism class of a Bieberbach group $\Gamma$ determines the structure of  $\Z G$-module $M$ in not exceptional case and  determines it up to a twist by inversion of $G$ in the exceptional case.

\end{remark}

		We shall need the following

		\begin{prop}[\cite{Hil85}, Theorem 1.5]\label{crystallographic restriction} Let $\Gamma$ be a Bieberbach group with holonomy group of order $p$. Then the rank of maximal free abelian normal subgroup $n$ of $\Gamma$ is at least $p-1$.
		\end{prop}

		\section{Profinite genus of Bieberbach groups with prime order holonomy}\label{genus}

		\begin{lem}\label{unique open}
			Let $\Gamma$ be a $n$-dimensional Bieberbach group with translation subgroup $M$. Then $\widehat{M}$ is the unique open normal, torsion-free maximal abelian subgroup of $\widehat{\Gamma}$.
		\end{lem}

		\begin{proof} There  is a one-to-one correspondence between the set of all finite index normal subgroups of  $\Gamma$  and the set of all open normal subgroups of $\widehat{\Gamma}$ (see \cite[Proposition 3.2.2]{RZ00}). Therefore the lemma follows from Proposition \ref{Cha, Prop 4.1}.
		\end{proof}

		From (\ref{exact sequence}) and Lemma \ref{unique open} we obtain the exact sequence
		\begin{equation*}
		1\rightarrow\widehat{M}\rightarrow\widehat{\Gamma}\rightarrow G\rightarrow 1
		\end{equation*}
		for the corresponding profinite completions.

		\begin{lem}\label{diagram}
			Let $\Gamma_1$ and $\Gamma_2$ be $n$-dimensional Bieberbach groups with translation subgroups $M_1$ and $M_2$ and  holonomy groups $G_1$ and $G_2$, respectively. If $\varphi:\widehat{\Gamma}_1\rightarrow\widehat{\Gamma}_2$ is an isomorphism, then there are isomorphisms $\phi:\widehat{M}_1\rightarrow \widehat{M}_2$ and $\psi: G_1\rightarrow G_2$ such that the following diagram commutes:
			\begin{equation}\label{diagram 1}
			\begin{CD}
			1 @>{}>> \widehat{M}_1 @>{}>> \widehat{\Gamma}_1 @>{}>> G_1 @>>> 1 \\
			@. @VV{\phi}V @VV{\varphi}V @VV{\psi}V\\
			1 @>{}>> \widehat{M}_2 @>{}>> \widehat{\Gamma}_{2} @>{}>> G_2 @>>> 1.
			\end{CD}
			\end{equation}
		\end{lem}
		\begin{proof}
			By Lemma \ref{unique open}, $\varphi(\widehat{M}_1)=\widehat{M}_2$. We define $\phi$ to be the restriction  of $\varphi$ to $\widehat{M}_1$. Since $\widehat{M}_1, \widehat{M}_2$ are profinite free abelian groups of the same rank,   $\phi: \widehat{M}_1\rightarrow\widehat{M}_2$ is an isomorphism. Thus $\varphi$ induces an isomorphism $\psi: G_1\rightarrow G_2$ such that the diagram (\ref{diagram 1}) commutes.
		\end{proof}

		Note that $\widehat M$ can be considered simply as $G$-modules (see  \cite[Proposition 5.3.6 (c)]{RZ00}).

		\begin{lem}\label{condition to isomorphism}
			Let $$M=\bigoplus_{i=1}^{c}(A_i,a_i)\oplus\bigoplus_{j=1}^{b}A_{j}\oplus \Z^{a},\ \ \  M'=\bigoplus_{i=1}^{c'}(B_i,b_i)\oplus\bigoplus_{j=1}^{b'}B_{j}\oplus\Z^{a'}$$ be $\Z G$-lattices. Then  $\widehat{M}\cong \widehat{M'}$ as $G$-modules if and only if $a=a', b=b'$ and $c=c'$.
		\end{lem}
		\begin{proof}
			Our proof starts with the observation that
			\begin{equation*}
			\widehat{M}= \bigoplus_{i=1}^{c}\widehat{(A_i,a_i)}\oplus\bigoplus_{j=1}^{b}\widehat{A}_{j}\oplus\widehat{\Z}^{a} \  \ \text{and} \ \ \widehat M'=\bigoplus_{i=1}^{c'}\widehat{(B_i,b_i)}\oplus\bigoplus_{j=1}^{b'}\widehat B_{j}\oplus\widehat{\Z}^{a'}.
			\end{equation*}
			If $\widehat{M}\cong\widehat{M'}$ as $G$-modules, then the pro-$p$ components of $\widehat{M}$ and $\widehat{M'}$ are isomorphic as $\mathbf{Z}_pG$-modules. Therefore, the necessity follows from Remark \ref{Remark-2} together with Propositions \ref{KSA} and \ref{Heller-Reiner}.

			On the other hand, by Remark \ref{Remark-2} the statement holds for pro-$p$ components of $\widehat{M}$ and $\widehat{M'}$. Hence by Proposition \ref{31.2 (ii)} $M_q\cong N_q$ for all primes $q$ and so $\widehat{M}\cong\widehat{M'}$ as $G$-modules.
		\end{proof}

		Let $\psi$ be an automorphism of a finite group $G$ and let $M$ be a $G$-module. Let $(M)^{\psi}$ denote the $G$-module $M$ given by the action $g\cdotp m:=\psi(g)\cdotp m$ for $g\in G$ and $m\in M$.

		\begin{prop}\label{item (i) th 1.4}
		Let $\Gamma_1$ and $\Gamma_2$ be $n$-dimensional Bieberbach groups with  holonomy group $G$ and translation subgroups $M_1$ and $M_2$, respectively.
		Then $\Gamma_1\cong \Gamma_2$ if and only if $M_1\cong (M_2)^{\psi}$ as $G$-modules where $\psi \in  \mathrm{Aut}(G)$.
		\end{prop}
		\begin{proof}
			  Suppose  $\varphi: \Gamma_1\rightarrow\Gamma_2$ is an isomorphism. By Proposition \ref{Cha, Prop 4.1}, $M_1$ and $M_2$ are the unique normal, maximal abelian subgroups of $\Gamma_1$ and $\Gamma_2$, respectively. Hence, $\varphi(M_1)=M_2$. Therefore, $\varphi$  induces an isomorphism $\psi:\Gamma_1/M_1\rightarrow\Gamma_2/M_2$, i.e., $\psi \in \mathrm{Aut}(G)$ because $\Gamma_1/M_1 \cong G\cong \Gamma_2/M_2$. Define $\phi:= \varphi|_{M_1}$. By definition of $\phi$ and $\psi$ the following diagram commutes
				\begin{equation*}
				\begin{CD}
				1 @>{}>> M_1 @>{}>> \Gamma_1 @>{\pi_1}>> G @>>> 1 \\
				@. @VV{\phi}V @VV{\varphi}V @VV{\psi}V\\
				1 @>{}>> M_2 @>{}>> \Gamma_{2} @>{\pi_2}>> G @>>> 1.
				\end{CD}
				\end{equation*}
				Thus,
				\begin{equation*}
				\phi(x\cdotp m)=\varphi(\alpha m \alpha^{-1})=\varphi(\alpha)\varphi(m)\varphi(\alpha)^{-1}=\psi(x)\cdotp \phi(m)
				\end{equation*}
				for $x\in G, m\in M_1$ and $\alpha \in \Gamma_1$ with $\pi_1(\alpha)=x$. Therefore, $M_1\cong (M_2)^{\psi}$ as $G$-modules.

				Conversely, suppose there is $\psi\in \mathrm{Aut}(G)$ such that $M_1\cong (M_2)^{\psi}$ as $G$-modules. Then $M_1$ is semi-linearly isomorphic to $M_2$. Therefore, by Propositions \ref{Cha-th 6.2}, \ref{C1-Bieberbach} and \ref{C2-Bieberbach} we have $\Gamma_1\cong\Gamma_2$.
		\end{proof}

		\begin{proof}[Proof of Theorem \ref{main Theorem 1}]

			\begin{enumerate}
				\item[(i)] It follows from Proposition \ref{item (i) th 1.4} and  by Remark \ref{charlap remark}.

				\item[(ii)] \textquoteleft Only if\textquoteright.
				From Lemma \ref{diagram} we see that there are isomorphisms $\phi:\widehat{M}_1\rightarrow \widehat{M}_2$ and $\psi: G\rightarrow G$ such that the following diagram is commutative
				\begin{equation*}
				\begin{CD}
				1 @>{}>> \widehat{M}_1 @>{}>> \widehat{\Gamma}_1 @>{}>> G @>>> 1 \\
				@. @VV{\phi}V @VV{\varphi}V @VV{\psi}V\\
				1 @>{}>> \widehat{M}_2 @>{}>> \widehat{\Gamma}_{2} @>{}>> G @>>> 1.
				\end{CD}
				\end{equation*}
				Then $\phi:\widehat{M}_1\rightarrow \widehat{M}_2$ is a $G$-module homomorphism which is an isomorphism by Lemma \ref{diagram}.

				Conversely, by Lemma \ref{characterization-Bieberbach group with n(G)=1}, $M=M_{n-1}\oplus \Z$, $M'=M'_{n-1}\oplus \Z'$ such that
				$\Gamma_1=M_{n-1}\rtimes C_1$ and  $\Gamma_2={M'}_{n-1}\rtimes C_2$, where $C_1,C_2$ contain $\Z$ and $\Z'$ as subgroups of index $p$ and act on $M_{n-1}, {M'}_{n-1}$ as $G$.
				Hence, $\widehat M=\widehat M_{n-1}\oplus \widehat\Z$, $\widehat M'=\widehat M'_{n-1}\oplus \widehat \Z'$ and
				$\widehat \Gamma_1=\widehat M_{n-1}\rtimes \widehat C_1$ and  $\widehat \Gamma_2=\widehat M'_{n-1}\rtimes \widehat C_2$, where $\widehat C_1,\widehat C_2$ act on $\widehat M_{n-1}, \widehat M'_{n-1}$ as $G$.
				By Lemma \ref{condition to isomorphism} and Proposition \ref{KSA}, we get that the profinite completions of $G$-modules $\widehat M_{n-1}$, $\widehat M'_{n-1}$ are isomorphic (since they are isomorphic as $\mathbf{Z}_pG$-modules). Hence, $\widehat \Gamma_1$ is isomorphic to $\widehat \Gamma_2$.
			\end{enumerate}
		\end{proof}

		The profinite version of Propositions \ref{C1-Bieberbach} and \ref{C2-Bieberbach} is the following.

		\begin{cor}\label{cor-3}
			Let  $\Gamma$ be a $n$-dimensional Bieberbach group whose holonomy group has prime order. Then there is a one-to-one correspondence between isomorphism classes of $\widehat{\Gamma}$ and triples $(a,b,c)$ from the decomposition \eqref{sum 1} with $a>0$.
		\end{cor}

		Now we are ready to prove Theorem \ref{main Theorem}.

		\begin{proof}[Proof of Theorem \ref{main Theorem}]
			Let $\Gamma_1$ and $\Gamma_2$ be $n$-dimensional Bieberbach groups with holonomy group of prime order and translation subgroups $M_1$ and $M_2$, respectively. By Lemma \ref{diagram} we can assume that $\Gamma_1$ and $\Gamma_2$ have the same holonomy group $G$ of prime order $p$. As $M_1$ and $M_2$ are $\Z G$-modules, by Proposition \ref{Diederichsen-Reiner},
			\begin{equation*}
			M\cong \bigoplus_{i=1}^{c}(A_i,a_i)\oplus\bigoplus_{j=1}^{b}A_{j}\oplus\Z^{a}
			\end{equation*}
			and
			\begin{equation*}
			M'\cong \bigoplus_{i=1}^{c'}(B_i,b_i)\oplus\bigoplus_{j=1}^{b'}B_{j}\oplus \Z^{a'}
			\end{equation*}
			where  $A_i, \  B_i$ are ideals of $\Z[\zeta]$. Since $\widehat{\Gamma}_1\cong\widehat{\Gamma}_2$, we have $\widehat{M}_1\cong\widehat{M}_2$ as $G$-modules (see Theorem \ref{main Theorem 1}). Hence, $a=a', \ b=b'$ and $c=c'$ by Lemma \ref{condition to isomorphism}. Therefore, the statement follows from Propositions \ref{C1-Bieberbach} and \ref{C2-Bieberbach} together with Theorem \ref{main Theorem 1}.
		\end{proof}

		\begin{cor}\label{example 1}
			Let $\Gamma$ be a  Bieberbach group whose holonomy group has prime order. If $H(\Q(\zeta))$ is non-trivial, then   $|\mathfrak{g}(\Gamma)|>1$.
		\end{cor}

\begin{remark} It follows  that the cardinality $|\mathfrak{g}(\Gamma)|$ of the genus of a Bieberbach group $\Gamma$ with the translation group $M$ and holonomy group $G$ of order $p$ equals to the cardinality of the genus of the $G$-module $M$ for non-exceptional $\Gamma$ and half of it if $\Gamma$ is exceptional.

\end{remark}

		\begin{proof}[Proof of Corollary \ref{cor-1}]
			This is a consequence of Theorem \ref{main Theorem} together with Proposition \ref{h_p=1 iff p<19}.
		\end{proof}

		\begin{proof}[Proof of Corollary \ref{cor-2}]
			From Proposition \ref{crystallographic restriction}, we deduce that for all $n\leq 21$ no prime number $p\geq 23$ can occur as orders of elements in the holonomy groups of $n$-dimensional Bieberbach groups. Then the result  follows from Corollary \ref{cor-1}.
		\end{proof}

		\begin{remark} If $\Gamma=M\rtimes G$, with $M$ free abelian of rank $n$ and $G$ of order $p$. Then it is not a Biebierbach group. Nevertheless using that $\Gamma$ and $M_1\rtimes G$ are isomorphic if and only if $M\cong M_1$ as $G$-modules and that the same holds for the profinite completions one can deduce that the genus of $\Gamma$ has the same cardinality  as in Theorem \ref{main Theorem}. Moreover, considering $G$ as a subgroup of $\mathrm{Aut}(M)=\mathrm{GL}(n, \Z)$ one deduces from \cite[Proposition 2.17]{GZ11} that the cardinality of the genus is exactly the number of conjugacy classes of subgroups of order $p$ of $\mathrm{GL}(n, \Z)$ in the conjugacy class of $G$ in $\mathrm{GL}(n,\widehat\Z)$.
		\end{remark}

		\section*{Acknowledgements}
		The author wishes to express his thanks to Prof. Dr. Pavel Zalesskii for many discussions and advices.

\bibliographystyle{amsplain}

config: arxiv


TITLE: Why should one expect valuations to be related to primes? How to treat an infinite place algebraically?
QUESTION [6 upvotes]: I understand the mechanics of the proof of Ostrowski's Theorem, but I'm a little unclear on why one should expect valuations to be related to primes. Is this a special property of number fields and function fields, or do primes of K[x,y] correspond to valuations on K(x,y) in the same way?
I'm hoping for an answer that can explain what exactly are the algebraic analogs of archimedian valuations, and how to use them - for example, I've heard that the infinite place on K(x) corresponds to the "prime (1/x)" - how does one take a polynomial in K[x] "mod (1/x)" rigorously?
Thanks in advance.

REPLY [3 votes]: I couldn't divine much information on your background (e.g. undergraduate, master's level, PhD student...) from the question, but I recently taught an intermediate level graduate course which had a unit on valuation theory.  Sections 1.6 through 1.8 of
http://alpha.math.uga.edu/~pete/8410Chapter1.pdf
address your questions.  In particular, if your field $K$ is the fraction field of a Dedekind domain $R$, then you can always use each prime ideal $\mathfrak{p}$ of $R$ to define a valuation on $K$, essentially the "order at $\mathfrak{p}$".  There is also a converse result, Theorem 13: if you have a valuation on $K$ which has the additional property that it is non-negative at every element of the Dedekind domain $R$, then it has to be (up to equivalence) the $\mathfrak{p}$-adic valuation for some $\mathfrak{p}$.   I felt the need to give this additional condition a name, so I called such a valuation R-regular.
The point is that (as Qiaochu says in his comments), in case $K$ is a number field and $R$ is its ring of integers, every valuation on $K$ is $R$-regular.  However, in the function field setting this is not true and this leads to a discussion of "infinite places".  Note that I do describe the analogues of Ostrowski's Theorem for finite extensions both of $\mathbb{Q}$ and of $F(t)$ for any field $F$ (in the latter case, one restricts to valuations which are trivial on $F$; when $F$ is finite, this condition is automatic).
I would be interested to know whether you find the notes helpful.  If not, I or someone else can probably recommend an alternative reference.

REPLY [3 votes]: Discrete valuations <-> points on a curve
For a nonsingular projective curve over an algebraically closed field, there is a one-one correspondence between the points on it, and the discrete valuations of the function field (i.e. all the meromorphic functions of the curve). The correspondence is point P -> the valuation that sends a function f, to the order of zero/pole of f at P.
Maximal ideals <-> points on a curve
At least for varieties (common zeros of several polynomials) over an algebraically closed field, there is a one-one correspondence between points on it, and the maximal ideal in $k[x_1,\cdots,x_n]$. The correspondence is point $P = (a_1,\cdots,a_n)$ -> the polynomials vanishing at P, which turns out to be $(x_1-a_1,\cdots,x_n-a_n)$. This is something true not only for curves, but for varieties. (Hilbert's Nullstellensatz)
So putting these together, for nonsingular projective curves over an algebraically closed field, you know that there is a one-one correspondence between the maximal ideals (think them as points) and the discrete valuations of the function field. Now the situation here is analogous. You consider a "curve", whose coordinate ring is $\mathbb{Z}$, with function field $\mathbb{Q}$. The nonarchimedean valuations correspond to discrete valuations in this case. So they should capture order of zeros/poles at some "points". What are the points? They should correspond to the maximal ideals of $\mathbb{Z}$, which are exactly the primes here.
As for $K(x)$, look at it as the function field of $K\mathbb{P}^1$. Just like the usual real/complex projective spaces, you should have two pieces here. Let's say $K[x]$ corresponds to the piece where the second coordinate is nonzero. So the corresponding homogeneous coordinates here is like $[x,1]$. We know there is one point missing, which is $[1,0]$. For this, we change our coordinates $[x,1] \to [1,1/x]$, so the piece where the first coordinate is nonzero should be $K[1/x]$. The missing point corresponds to the ideal $(1/x - 0) = (1/x)$, so this is why the infinite place corresponds to (1/x). Of course, a more straight forward interpretation is that for a rational function, you divide both numerator and denominator sufficiently high power of $x$ so that they both become polynomials in 1/x, have nonzero constant term, with an extra term (x to the some power). The infinite place measures this power.


TITLE: Primes and Finite Field Theory
QUESTION [0 upvotes]: Determine all primes $p>0$ so that there exists a solution in $\mathbb F_p$, the field with $p$ elements.
  $$a)\  3x^2 - 30x+40=0$$
  $$b)\ x^2 + 26x+139=0$$
  $$c)\ x^2 - 5x+6=0$$

For a), I got p=2, p=13. For b), I got p=5, p=31, for c), I got p=3. Could someone please tell me if there is an easier way to calculate all the prime p instead of brute forcing it? Could you also please let me know if these are all the primes p that satisfies the condition?
Thank you!!!

REPLY [0 votes]: In c) we have $$x^2-5x+6=(x-2)(x-3)$$ so $x=2$ and $x=3$ are solutions modulo any prime $p$.
In b) we have
$$
x^2+26x+139=(x+13)^2-30.
$$
So this quadratic has a solution modulo $p$, if and only if $30=2\cdot3\cdot5$ is a quadratic residue modulo $p$. In other words we need an even number of $2,3,5$ to be quadratic non-residues modulo $p>5$. By the law of quadratic reciprocity i) the question about $2$ depends on the residue class of $p$ modulo $8$, ii) the question about $3$ depends on the residue class of $p$ modulo $12$, and iii) the question about $5$ depends on the residue class of $p$ modulo $5$. A consequence of this is that the answer depends on the residue class of $p$ modulo $\mathrm{lcm}(8,12,5)=120$. Leaving it to you to check how the $\phi(120)=32$ residue classes split (it works for exactly one half of them and doesn't work for the other half).
Part a) is similar to part b). Leaving that to you as well. Apart from the factors of the discriminant (that you need to check separately), there will be a fifty-fifty split among the primes according to their residue class modulo a suitable number.


TITLE: How can we show that $I_{yy}=I_{zz}=I_{xx}$ and $I_{xy}=0$ using symmetry arguments?
QUESTION [0 upvotes]: Consider two integrals of the form $$I_{xx}=\int x^2 f(r)d^3r,~~I^\prime=\int xy ~f(r)d^3r$$ where $f(r)$ is a function of $r=|\vec{r}|$ only and has no dependence on $\theta,\phi$ in pherical polar coordinates. I have two questions. Can we show that $I_{yy}=I_{zz}=I_{xx}$ and $I_{xy}=I_{yz}=I_{zx}=0$ using symmetry arguments?

REPLY [1 votes]: $f(r)$ has two relevant symmetries: rotational and reflection. From the rotational symmetry we can conclude that $\int x^n f(r) d^3r=\int y^n f(r) d^3r=\int z^n f(r) d^3r$. explicitly $f(\sqrt{x^2+y^2+z^2})=f(\sqrt{y^2+x^2+z^2})$ etc (in fact we didn't use the rotational symmetry but a permutation symmetry).
From the reflection symmetry we conclude that $\int xy f(r) d^3r=\int (-x)y f(r) d^3r=-\int xy f(r) d^3r$ so that $I_{xy}=-I_{xy}=0$, since $f(\sqrt{x^2+y^2+z^2})=f(\sqrt{(-x)^2+y^2+z^2}) $ etc.


TITLE: Calculations involving kilowatt and kilowatt hour
QUESTION [0 upvotes]: :)
I am very confused with the calculation involving kWh and kW. I have tried searching my question on Google but couldn't find anything.
Say, we have a device with a power rating of 1 kW.
This means that, when the device is turned on, for every second, 1000 joules of energy is being consumed right?
And if we want to calculate how much energy has been consumed by this device in one hour, we simply multiply the value of kW by 1.
So, my question is: since watt is equivalent to joule per second, why don't we multiply 1 kW by 60 seconds, then by 60 minutes again? How is it that we simply multiply the value of kW according to how many hours the device has been turned on for?
I hope what I am saying makes sense to you. :0
Thanks in advance!

REPLY [0 votes]: If you multiply 1 kW by 3600 you are indeed finding total joules consumed in an hour.
That's not quite the same as a kilowatt hour.  The kilowatt hour is just a convenient way to measure energy usage.  It is fairly easy to determine power used in a circuit.  Generally most things we power with electricity, the purpose is to actually provide power, not energy.
These devices require a constant energy source to keep operating.  That's also how the power is generated, and how it is transmitted.
Essentially, most of our devices operate with respect to time, and therefore require a power draw.  It's a lot easier to measure and cost our electricity based on delivered power over a period of time, because those units fit in better with how the energy is delivered.  The units still end up as a form of energy, just one that is easier to convert back into power.  Instead of multiplying the power by the number of seconds and getting big numbers of joules, we multiply by hours, which is closer to the time scale we would expect to be drawing power on.
This is somewhat a supplemental answer to the other answer currently provided (showing the units), explaining more of the reasons why the units were chosen.


TITLE: How to evaluate this infinite series? $\sum_{r = 1}^{\infty} \frac{1}{r(r + \frac{1}{3})}$
QUESTION [1 upvotes]: The question is to find this infinite series:
$$ \sum_{r = 1}^{\infty} \frac{1}{r(r + \frac{1}{3})} = \; ? $$

I have tried applying the Riemann sum to the Integral technique as follows:
Assuming the lower and upper boundaries (a and b) are 0 and 1. Now, we know that
$$ \int_{0}^{1} {f(x)} \; dx = \lim_{n \to \infty} \frac{1}{n} \sum_{r = 1}^{n} f(\frac{r}{n}) $$
Therefore,
$$ \sum_{r = 1}^{\infty} \frac{1}{r(r + \frac{1}{3})} = \lim_{n \to \infty} \sum_{r = 1}^{n} \frac{1}{r(r + \frac{1}{3})} $$
$$ = \lim_{n \to \infty} \frac{1}{n} \sum_{r = 1}^{n} \frac{n}{r(r + \frac{1}{3})} = \lim_{n \to \infty} \frac{1}{n} \sum_{r = 1}^{n} \frac{n}{r} \frac{1}{({r+\frac{1}{3}})} $$
I'm stuck here.
Is there a different approach to this problem? Or, could this problem be solved this way?

Edit: Given in this comment below, does not answer my question. The answer is completely incomprehensible to me.

REPLY [0 votes]: Making the problem more general, for $a>0$, we can compute the partial sum
$$S_n=\sum_{r=1}^n \frac 1{r(r+a)}$$ Using partial fraction decomposition
$$S_n=\frac 1 a  (-\psi (a+n+1)+\psi (a+1)+\psi (n+1)+\gamma )$$ and using the asymptotics
$$S_n=\frac{\psi(a+1)+\gamma }a-\frac{1}{n}+\frac{ (a+1)}{2 n^2}-\frac{ (a+1) (2 a+1)}{6
   n^3}+O\left(\frac{1}{n^4}\right)$$


TITLE: Finding the extrema on sphere
QUESTION [1 upvotes]: Let $f(x,y,z) = xe^{yz}$ . Find the extrema on the sphere $x^2+y^2+z^2=1$ . We have $e^{yz}=2tx$ , $xze^{yz}= 2ty$ , $xye^{yz}=2tz$ solving by subtitutions i found that $z(x^4-2)=0$ implies that if $z=0$ then $y=0$ and $x= \pm1$ .   if the other part is zero then i found that the solution does not exist . Hence $( 1,0,0)$ is absolute maximum and $(-1,0,0)$ is absolute minimum . Is there any problem here ? Then i was asked to find the extrema for the unit sphere and for the sphere of radius $3$ to solve simultenously and i got stucked cqn somebody help me for that . ?

REPLY [2 votes]: An elementary approach without the Lagrange method: For $|x|\in [0,1]$ the value of $|f(x,y,z)|=|x e^{y z}|$ is maximized (minimized) by maximizing (minimizing) $y z$ subject to $y^2+z^2=1-x^2.$ Since $4(y z)^2=(y^2+z^2)^2-(y^2-z^2)^2,$ we see that $|y z|$ is maximized when $y=\pm z,$ and minimized when $y=0$ or $z=0.$ When $y=\pm z$ we have $f(x,y,z)=(\pm \sqrt {1-2 u})e^{\pm u}$ where $u=|y z|\in [0,1/2].$  When $y=0$ or $z=0$ we have  $f(x,y,z)=x\in [-1,1].$ Finding extrema of $(\pm \sqrt {1-2 u})e^{\pm u}$ for $u\in  [0,1/2]$ is an elementary one-variable problem, and finding extrema of $x\in [-1,1]$ is trivial.
Nicolas' solution is more instructive, as the method is applicable to a large class of problems.


TITLE: Hahn-Banach theorem
QUESTION [1 upvotes]: Hope this won't turn out to be a stupid question. If I want to apply the Hahn-Banach lemma to prove the Hahn-Banach theorem, then I want to define a function $p$ that provides an upper bound on my functional defined on a linear subspace $Y \subset X$. Say, I want to extend $f \in Y^\ast$. Then the notes define $p(x) = \|f\| \|x\|$. I don't quite believe this works since if $\|y\| \lt 1$ we might not have $f(y) \leq p(y) = \|f\| \|y\| = \sup_{\|x\|=1} |f(x)| \|y\|$. What am I missing? Thanks for your help.

REPLY [3 votes]: The thing you're probably missing is the fact that the left hand side depends on the norm of $y$. Maybe you will be more convinced if you write it that way (for $y\neq 0$, if $y$ is zero both sides are zero, so the inequality holds):
$$f(y)=f(y/\lVert y\rVert)\cdot\lVert y\rVert\leq \lVert f\rVert\lVert y\rVert$$
(notice that $\lVert (y/\lVert y\rVert) \rVert=1$).


TITLE: MST of an subgraf.
QUESTION [0 upvotes]: I find myself yet again stucked in one of the assignment's problems for my Graph Theory Course at my local university.
Let G = (V, E) be a connected (multi)graph and c : E → R be a cost function on its edges.
Let $T^∗$ be a minimum cost spanning (MST) tree of G (with respect to c). We said that a connected subgraph H of G is c-extendable if $T^*_H$ = (V (H), E(H) ∩ E($T^∗$)) is a spanning tree of H.
Here is where i am getting stucked.
~Prove that if H is c-extendable, then $T^∗_H$ is a MST of H.
The solution which I've worked my way through a certain point is supposing that $T^*_H$ is not the MST of H.Considering this I assumed that there is a MST of H called $A^*$.A property of $T^*_H$ considering $A*$ is $\sum_{(e \ from \ c(T^*_H))} c(e)$ > $\sum_{(f \ from \ c(A^*))} c(f)$ . How should i proceed next?
Any hint is welcomed!

REPLY [1 votes]: The key here is to recognize that $A^*$ can be used to construct a spanning tree $\bar A$ of G with lower total cost than $T^*$ which gives a contradiction because $T^*$ was presumed to have the smallest possible total cost.
$\bar A$ can be constructed by taking all the edges of $A^*$ and all the edges of $T^*$ that aren’t in $T*_H$.
All you need to do from there is prove that $\bar A$ is in fact a spanning tree, and that it has lower cost than $T^*$.


text:
\begin{document}
\maketitle

\begin{abstract}
Let $\xb$ be a signal to be sparsely decomposed over a redundant dictionary $\Ab$, \ie\, a sparse coefficient vector $\sbb$ has to be found such that $\xb=\Ab\sbb$. It is known that this problem is inherently unstable against noise, and to overcome this instability, the authors of

\cite{DonoET06}
have proposed to use an ``approximate'' decomposition, that is, a decomposition satisfying $\|{\bf x} - {\bf A s}\| \le \delta$ rather than satisfying the exact equality ${\bf x} = {\bf A s}$.
Then, they have shown that if there is a decomposition with $\|{\bf s}\|_0 < (1+M^{-1})/2$, where $M$ denotes the {\em coherence} of the dictionary, this decomposition would be stable against noise. On the other hand, it is known that a sparse decomposition with $\|{\bf s}\|_0 < \frac{1}{2} \mbox{\sl spark}({\bf A})$ is unique. In other words, although a decomposition with $\|{\bf s}\|_0 < \frac{1}{2} \mbox{\sl spark}({\bf A})$ is unique, its stability against noise has been proved only for highly more restrictive decompositions satisfying $\|{\bf s}\|_0 < (1+M^{-1})/2$, because usually $(1+M^{-1})/2 \ll \frac{1}{2} \mbox{\sl spark}({\bf A})$.

This limitation maybe had not been very important before, because $\|{\bf s}\|_0 < (1+M^{-1})/2$ is also the bound which guaranties that the sparse decomposition can be found via minimizing the $\ell^1$ norm, a classic approach for sparse decomposition. However, with the availability of new algorithms for sparse decomposition, namely SL0 and Robust-SL0, it would be important to know whether or not unique sparse decompositions with $(1+M^{-1})/2 \le \|{\bf s}\|_0 < \frac{1}{2} \mbox{\sl spark}({\bf A})$ are stable. In this paper, we show that such decompositions are indeed stable. In other words, we extend the stability bound from $\|{\bf s}\|_0 < (1+M^{-1})/2$ to the whole uniqueness range $\|{\bf s}\|_0 < \frac{1}{2} \mbox{\sl spark}({\bf A})$. In summary, we show that {\em all unique sparse decompositions are stably recoverable}. Moreover, we see that sparser decompositions are `more stable'.
\end{abstract}

\begin{IEEEkeywords}
Sparse Signal Decomposition, Sparse recovery, Compressed Sensing, Sparse Component Analysis (SCA), Overcomplete dictionaries.
\end{IEEEkeywords}

\section{Introduction}
\IEEEPARstart{L}{et} $\Ab$ be an $n \times m$ matrix with $m>n$, and consider the Underdetermined System of Linear Equations (USLE) $\Ab \sbb = \xb$. Such a linear system has typically infinitely many solutions, but let consider its sparsest solution, that is, a solution $\sbb_0$ which has as much as possible zero components.

This problem has recently attracted a lot of attention from many different viewpoints. It is used, for example, in Compressed Sensing (CS)~\cite{CandRT06,Dono06,Bara07}, underdetermined Sparse Component Analysis (SCA) and source separation~\cite{GribL06, BofiZ01, GeorTC04, LiCA03}, atomic decomposition on overcomplete dictionaries~\cite{ChenDS99,DonoET06},  decoding real field codes~\cite{CandT05}, image deconvolution~\cite{FiguN03,FiguN05}, image denoising~\cite{Elad06}, electromagnetic imaging and Direction of Arrival (DOA) finding~\cite{GoroR97}, etc.

In atomic decomposition viewpoint~\cite{MallZ93}, the columns of $\Ab$ are called `atoms' and the matrix $\Ab$ is called the `dictionary' over which the `signal' $\xb$ is to be decomposed. When the dictionary is overcomplete ($m>n$), the representation is not unique, but by the sparsest solution, we are looking for the representation which uses as small as possible number of atoms to represent the signal.

Sparse solutions of underdetermined linear systems would not be useful, unless positive answers can be provided for the following three questions:
\begin{enumerate}
	\item {\bf Uniqueness:} Is such a solution unique?

	\item {\bf Practical algorithm:} Is it practically possible to find the sparsest solution of an USLE?

	\item {\bf Stability against noise:} Doesn't a small amount of noise result in a completely different sparse solution?
\end{enumerate}

In this paper we study the third question, and we generalize previously available results. To better explain the problem and our contribution, we firstly do a brief review in Section~\ref{sec: Problem statement} on the available results about the above questions, and then explain in subsection~\ref{sec: our contrib} what our contribution is. We state then the main theorem in Section~\ref{sec: Main Thm}. Finally, a generalized result will be stated in Section~\ref{sec: Gen Thm}.

\section{Problem statement}\label{sec: Problem statement}
\subsection{Uniqueness?}
The uniqueness problem has been addressed in~\cite{GoroR97,GribN03,DonoE03}, and it has been shown that if an underdetermined linear system has a sparse enough solution, it would be its unique sparsest solution. More precisely:

\medskip
\begin{theorem}[Uniqueness~\cite{GribN03,DonoE03}]
\label{th: uniqueness}\em
Let $\spark(\Ab)$ denote the minimum number of columns of $\Ab$ that are linearly dependent, and $\|\cdot\|_0$ denotes the $\ell^0$ norm of a vector (i.e. the number of its non-zero components). Then if the USLE $\Ab \sbb = \xb$ has a solution $\sbb_0$ for which $\|\sbb_0\|_0 < \frac{1}{2} \spark(\Ab)$, it is its unique sparsest solution.
\end{theorem}
\medskip

A special case of this uniqueness theorem has been stated in~\cite{GoroR97}: if $\Ab$ has the Unique Representation Property (URP), that is, if all $n \times n$ submatrices of $\Ab$ are non-singular, then $\spark(\Ab)=n+1$ and hence $\|\sbb_0\|_0 \le \frac{n}{2}$ implies that $\sbb_0$ is the unique sparsest solution.

\subsection{Practical Algorithm?}
Finding the sparsest solution of an USLE can be expressed as:
\begin{equation}
	(P_0): \quad \mbox{Minimize } \nz{\sbb} \quad \mbox{subject to}\quad \Ab \sbb = \xb,
\end{equation}
where $\nz{\cdot}$ stands for the $\ell^0$ norm of a vector. Solving the above problem requires a combinatorial search and is generally NP-hard. Then, many algorithms have been proposed to indirectly solve the problem. One of the first and most successful ideas is the idea of Basis Pursuit (BP)~\cite{ChenDS99}, which is to replace the above problem by
\begin{equation}
	(P_1): \quad \mbox{Minimize } \no{\sbb} \quad \mbox{subject to}\quad \Ab \sbb = \xb,
\end{equation}
where $\no{\sbb}\triangleq\sum_i|s_i|$ is the $\ell^1$ norm of \sbb.
Note that the problem $P_1$ is convex and can be easily solved by using Linear Programming (LP) techniques. Moreover, it has been shown that if the sparsest solution $\sbb_0$ is highly sparse, then the solution of $P_1$ is also the sparsest solution, \ie\ it is also the solution of $P_0$.

To express this property more precisely, let the columns of $\Ab$ be normalized to have unit $\ell^2$ (Euclidean) norm. Let also define the {\em `coherence'}, $M$, of the dictionary $\Ab$ as the maximum correlation between its atoms, that is:
\begin{equation}
	M \triangleq \max_{i\neq j} |\ab_i^T \ab_j|,
\end{equation}
where $\ab_i$, $i=1,...,m$ denote the columns of $\Ab$. Then:

\medskip
\begin{theorem}[Equivalence of $P_0$ and $P_1$~\cite{GribN03,DonoE03}]
\label{th: equiv P0 P1}\em
If the USLE $\Ab \sbb = \xb$ has a solution $\sbb_0$ for which $\|\sbb_0\|_0 < \frac{1+M^{-1}}{2}$, then it is the unique solution of both problems $P_0$ and $P_1$.
\end{theorem}
\medskip

In other words, if the sparsest solution satisfies $\|\sbb_0\|_0 < \frac{1+M^{-1}}{2}$, it can be found by solving the convex program $P_1$.

\medskip

{\bf Remark 1.\ } Note that the bound on sparsity that guaranties the equivalence of $P_0$ and $P_1$ is highly more restrictive than the bound which guaranties the uniqueness of the sparsest solution. For example, suppose that the dictionary $\Ab$ is constructed by concatenating two orthonormal bases, $\Ab=[\Phib, \Psib]$, and hence $m=2n$. It can be easily shown~\cite{GribN03} that in this case the maximum possible value for $M$ is $1/\sqrt{n}$ (this maximum value for $M$ is obtained for example for concatenation of a Dirac and a Fourier dictionary). Consider for example such a dictionary $\Ab$ with $m=1000$ and $n=500$, which satisfies the URP and has the maximum possible coherence $M=\frac{1}{\sqrt{n}}\approx {1}/{(22.36)}$. Then, by Theorem~\ref{th: uniqueness} a solution $\sbb_0$ with $\nz{\sbb_0} \le 250$ is necessarily the unique sparsest solution. However, from Theorem~\ref{th: equiv P0 P1}, it is guaranteed that the sparsest solution can be found by $P_1$ only where $\nz{\sbb_0} < (1+22.36)/2$, that is $\nz{\sbb_0} \le 11$. In other words, if there is a solution $\sbb_0$ such that among its 1000 entries there are at most 250 non-zero entries, it would be the unique sparsest solution, but we cannot necessarily find it by solving $P_1$, unless among these 1000 entries, there are at most 11 non-zero entries. Consequently, equivalence of $P_1$ and $P_0$ holds only for the case there exists a {\em `very very' sparse} solution.

\medskip

{\bf Remark 2.\ } Note also that if the unique sparsest solution satisfies $\frac{1+M^{-1}}{2} \le \|\sbb_0\|_0 < \frac{1}{2} \spark(\Ab)$, the above theorem does not state that it `cannot' be found by solving $P_1$; it simply does not `guarantee' that $P_1$ can recover it. In fact, from the uniqueness Theorem~\ref{th: uniqueness}, we know that if we find a solution $\hsbb_0$ by using any method (\eg\ $P_1$, or even simply by a magic guess), and we see that it happens that $\|\hsbb_0\|_0 < \frac{1}{2} \spark(\Ab)$, we will know that we have found the unique sparsest solution.

\medskip

In addition to the methods based on $\ell^1$ norm minimization, there are other ideas for finding the sparsest solution, for example Matching Pursuit (MP)~\cite{MallZ93} and Smoothed $\ell^0$ (SL0)~\cite{MohiBJ09}. The latter method (SL0), which has been designed in our group, tries to directly solve the $P_0$ problem by replacing the $\ell^0$ norm by a smooth approximation of it (and hence the name `smoothed' $\ell^0$). One of the motivations behind SL0 is the fact stated above: Since the equivalence of $P_0$ and $P_1$ holds only where there exist very very sparse solutions, it would probably be better trying to solve $P_0$ directly. Another motivation is the speed: it has been shown~\cite{MohiBJ09} that SL0 is highly faster than solving $P_1$.

\subsection{Stability against noise?} \label{sec: stability}
Suppose that $\xb_0$ is a linear combination of a few atoms of the dictionary, that is, $\xb_0=\Ab \sbb_0$, where $\sbb_0$ is sparse. Now consider a noisy measurement of $\xb_0$, that is, $\xb=\xb_0+ \nb$, where $\nb$ denotes the noise, and $\nt{\nb} \le \eps$.
The question of `stability'~\cite{DonoET06} is then:
Even for a very small $\eps$, is it guaranteed that the sparse decomposition of $\xb$ over the dictionary (problem $P_0$) is not too different from the sparse decomposition of $\xb_0$?
The answer is unfortunately no, that is, the problem $P_0$ can be too sensitive to noise~\cite{Wohl03}.

To overcome this problem, it has been proposed in~\cite{DonoET06} that instead of solving $P_0$ or $P_1$ one considers solving their noise aware variants:
\begin{gather}
(P_{0,\delta}): \quad \mbox{Minimize } \nz{\sbb} \quad \mbox{s.t.}\quad \nt{\xb - \Ab \sbb} \le \delta \\
(P_{1,\delta}): \quad \mbox{Minimize } \no{\sbb} \quad \mbox{s.t.}\quad \nt{\xb - \Ab \sbb} \le \delta
\end{gather}
In other words, it has been proposed to do an ``approximate'' decomposition, that is, a decomposition with $\|{\bf x} - {\bf A s}\| \le \delta$ instead of the exact decomposition ${\bf x} = {\bf A s}$.
These noise aware variants have to be solved for a sufficiently large $\delta$, that is, for $\delta \ge \eps$ to guarantee that the true solution $\sbb_0$ satisfies the constraints of the above optimization problems. Then, in~\cite{DonoET06}, the authors prove that both problems $P_{0,\delta}$ and $P_{1,\delta}$ are stable against noise, that is, the estimation error is at worst proportional to the noise level. More precisely, the stability of $P_{0,\delta}$ is given by the following theorem:

\medskip
\begin{theorem}[Stability of $P_{0,\delta}$; theorem 2.1 of \cite{DonoET06}] \label{th: Donoho}
\em
Let $M$ denote the coherence of the dictionary $\Ab$. Suppose that for the sparse representation of the noiseless signal $\xb_0=\Ab \sbb_0$ we have:
\begin{equation}
	k \triangleq \nz{\sbb_0} < \frac{1+M^{-1}}{2}
	\label{eq: Condition Classic}
\end{equation}
If $\hsbb_{0,\delta}$ denotes the result of applying $P_{0,\delta}$ on the noisy data $\xb$ with $\delta \ge \eps$, then:
\begin{equation}
	\nt{\hsbb_{0,\delta}-\sbb_0} \le \frac{\eps+\delta}{\sqrt{1-M(2k-1)}}\, .
	\label{eq: error bound classic}
\end{equation}
\end{theorem}
\bigskip

Note that (\ref{eq: Condition Classic}) implies also that the term under the square root in (\ref{eq: error bound classic}) is positive.

The authors of \cite{DonoET06} also prove the stability of $P_{1,\delta}$ for the case $\nz{\sbb_0} < {(1+M^{-1})}/{4}$.

A noise aware variant of SL0 (called Robust-SL0), has already been developed~\cite{EfteBJA09}, which tries to solve directly $P_{0,\delta}$ without passing through $P_{1,\delta}$.

\subsection{Our Contribution}\label{sec: our contrib}
As it was said in Section~\ref{sec: stability}, the stability of the problem $P_{0,\delta}$ has only been shown for the case $\nz{\sbb_0} < {(1+M^{-1})}/{2}$. This sparsity limit for stability is the same as the sparsity limit for the equivalence of $P_0$ and $P_1$ as stated in Theorem~\ref{th: equiv P0 P1}. However, as was stated in Remark~1 after Theorem~\ref{th: equiv P0 P1}, this sparsity limit is highly more restrictive than the sparsity limit for the uniqueness of the sparse solution.
In other words, current results state that although a sparse representation with $\frac{1+M^{-1}}{2} \le \nz{\sbb_0} < \frac{1}{2} \spark(\Ab)$ is unique, it is not guaranteed that $P_{0,\delta}$ can stably recover this representation in presence of noise.

Maybe the lack of this guarantee had not been important before, because, the classic idea for solving $P_0$ was solving $P_1$, and the sparsity limit for the equivalence of these two solutions is the same as the sparsity limit for the stability of $P_{0,\delta}$. However, with new algorithms like SL0 or Robust-SL0, one can now try to solve $P_{0,\delta}$ directly and without relying on $P_{1,\delta}$. Hence it is now important to know whether or not sparse representations with $\frac{1+M^{-1}}{2} \le \nz{\sbb_0} < \frac{1}{2} \spark(\Ab)$ are stable.

In the next section, we will show that $P_{0,\delta}$ is stable for the {\em whole sparsity range} that guarantees the uniqueness, that is, $P_{0,\delta}$ is stable whenever $\nz{\sbb_0} < \frac{1}{2} \spark(\Ab)$. Moreover, we will show that for smaller $\nz{\sbb_0}$ the problem is `more stable', that is, {\em the more sparsity, the more stability}. Finally, we will show in Section~\ref{sec: Gen Thm} that {\em this stability not only holds for $P_{0,\delta}$, but also holds for any estimation $\hsbb_0$ such that $\nz{\hsbb_0} < \frac{1}{2} \spark(\Ab)$ and $\nt{\xb - \Ab \hsbb_0} \le \delta$}.

\section{The main theorem}\label{sec: Main Thm}
To state the main theorems, we need first to define two notations:

\begin{itemize}
	\item Let $q=q(\Ab)=\spark(\Ab)-1$. Then, by definition, every $q$ columns of $\Ab$ are linearly independent, and there is at least a set of $q+1$ columns which are linearly dependent (in the literature, the quantity $q$ is usually called `Kruskal rank' or `k-rank' of the matrix $\Ab$). It is also obvious that $q\le n$, in which, $q=n$ corresponds to the case $\Ab$ has the URP.

	\item Let $\sm{j}$, $1\le j \le q(\Ab)$, denote the smallest singular value among all of the submatrices of $\Ab$ formed by taking $j$ columns of $\Ab$. Note that since every $q$ columns of $\Ab$ are linearly independent, we have $\sm{j} > 0$, $\forall 1\le j \le q(\Ab)$.
\end{itemize}

Moreover, it is known~\cite[p. 419]{HornJ85},~\cite[Lemma 3]{BabaMJ09} that if we add a new column to a full-rank tall matrix, its smallest singular value decreases or remains the same (refer to \cite{BabaMJ09} for a simple direct proof). Therefore, $\sm{j}$ is a decreasing sequence in $j$, that is:
\begin{equation}\label{eq: sigma decrease}
	\sm{j} \ge \sm{j+1} > 0, \quad \forall 1 \le j \le q-1
\end{equation}

We are now ready to state the following theorem.

\medskip
\begin{theorem}[Stability of $P_{0,\delta}$]
\label{th: Main Theorem}\em
Suppose that the noiseless signal $\xb_0$ has a sparse representation $\xb_0=\Ab \sbb_0$ satisfying $\nz{\sbb_0} <
\frac{1}{2}\spark(\Ab)$. Let also $\xb=\xb_0+\nb$ be a noisy measurement of $\xb_0$ and $\nt{\nb} \le \eps$.
If $\hsbb_{0,\delta}$ denotes the result of applying $P_{0,\delta}$ on the noisy signal $\xb$ with $\delta \ge \eps$, then:
\begin{equation}
	\nt{\hsbb_{0,\delta}-\sbb_0} \le \frac{\delta+\eps}{\sm{\ell}},
	\label{eq: our first upper bound}
\end{equation}
where $\ell = 2 \nz{\sbb_0}$.
\end{theorem}
\medskip

{\bf Remark~1.\ } Theorem~\ref{th: Main Theorem} shows that $P_{0,\delta}$ is stable not only for $\nz{\sbb_0} < \frac{1+M^{-1}}{2}$, but also for the whole uniqueness range $\nz{\sbb_0} < \frac{1}{2} \spark(\Ab)$. The stability is in the sense that the estimation error increases at worst proportionally to the noise level. Moreover, from (\ref{eq: sigma decrease}), the upper bound on estimation error decreases or remains the same as the sparsity increases (this is because sparser $\sbb_0$ means smaller $\nz{\sbb_0}$, which implies smaller $\ell$ and hence larger or the same $\sm{\ell}$). In other words, {\em sparser solutions are `more stable'}.

\medskip

{\bf Remark~2.\ } The main reason for stating Theorem~\ref{th: Main Theorem} is to provide a stability result for the case $1+M^{-1} \le \ell=2 \nz{\sbb_0} < \spark(\Ab)$, because in this case, Theorem~\ref{th: Donoho} provides
no stability result. Moreover, note that for the case $\ell < 1+M^{-1}$, in which both bounds (\ref{eq: error bound classic}) and (\ref{eq: our first upper bound}) are applicable, (\ref{eq: our first upper bound}) provides also a tighter bound than (\ref{eq: error bound classic}). This is implied from Lemma~2.2 of~\cite{DonoET06} which states that in this case $\sm{\ell}>\sqrt{1-M(\ell - 1)}$.

\medskip

\begin{IEEEproof}[Proof of Theorem~\ref{th: Main Theorem}]
Let define $\hxb_{0,\delta} \triangleq \Ab \hsbb_{0,\delta}$. We write:
\begin{align}
 	  \nt{\xb_0 - \hxb_{0,\delta}} &= \nt{\xb-\nb - \hxb_{0,\delta}} \nonumber \\
 	  &= \nt{(\xb - \Ab \hsbb_{0,\delta}) -\nb} \nonumber \\
 	  &\le \underbrace{\nt{\xb - \Ab \hsbb_{0,\delta}}}_{\le \delta} + \underbrace{\nt{\nb}}_{\le \eps} \nonumber \\
 	  &\le \delta+\eps \label{eq: upper bound on x diff}
\end{align}

\noindent On the other hand:
\begin{equation}
\label{eq: temp1}
	\xb_0 - \hxb_{0,\delta} = \Ab (\sbb_0 - \hsbb_{0,\delta}) = \Bb \vb
\end{equation}
where $\vb$ is a vector composed of non-zero entries of $\sbb_0 - \hsbb_{0,\delta}$, and
$\Bb$ is a submatrix of $\Ab$ composed of the columns of $\Ab$ corresponding to the non-zero entries of $\sbb_0 - \hsbb_{0,\delta}$.
Since $\delta \ge \eps$, $\sbb_0$ satisfies the constraint of the optimization problem $P_{0, \delta}$, and hence $\nz{\hsbb_{0,\delta}} \le \nz{\sbb_0}$. Therefore $\sbb_0 - \hsbb_{0,\delta}$ has at most $\ell\triangleq2 \nz{\sbb_0}<\spark(\Ab)$ non-zero entries (note that $\ell < \spark(\Ab)$ means $\ell \le q(\Ab)$). In other words, $\Bb$ has at most $\ell\le q$ columns, and hence (by having also in mind (\ref{eq: sigma decrease})):
\begin{equation}
	\nt{\Bb \vb} \ge \sm{\ell} \nt{\vb}
	\label{eq: Bv low bound}
\end{equation}
Noting that $\nt{\vb}=\nt{\sbb_0 - \hsbb_{0,\delta}}$, and combining the above inequality with (\ref{eq: temp1}), we obtain:
\begin{equation} \label{eq: lower bound on x diff}
	\nt{\xb_0 - \hxb_{0,\delta}} \ge \sm{\ell} \nt{\sbb_0 - \hsbb_{0,\delta}}
\end{equation}
Combining (\ref{eq: upper bound on x diff}) and (\ref{eq: lower bound on x diff}) gives:
\begin{equation}
	\sm{\ell} \nt{\sbb_0 - \hsbb_{0,\delta}} \le \delta + \eps
\end{equation}
which completes the proof.
\end{IEEEproof}
\medskip

{\bf Remark~3.\ } From (\ref{eq: sigma decrease}) and $\ell=2 \nz{\sbb_0} \le q(\Ab)$, we may replace $\sm{j}$ by its worst case to obtain the following looser bound, which does not need knowing the value of $\nz{\sbb_0}$:
\begin{equation}
	\nt{\hsbb_{0,\delta}-\sbb_0} \le \frac{\delta+\eps}{\sm{q}}.
	\label{eq: looser bound}
\end{equation}

\section{A generalized stability theorem}\label{sec: Gen Thm}
If we carefully re-examine the proof of Theorem~\ref{th: Main Theorem}, we notice that the fact that $\nz{\hsbb_{0,\delta}}\le\nz{\sbb_0}$ is not essential for obtaining the looser bound~(\ref{eq: looser bound}). Hence, the bound~(\ref{eq: looser bound}) holds not only for the sparse recovery methods based on solving $P_{0, \delta}$, but also for {\em any other estimation} $\hsbb_{0,\delta}$ (obtained from any sparse recovery algorithm or even simply from a magic guess),
provided that it satisfies $\nz{\hsbb_{0,\delta}} < \frac{1}{2} \spark(\Ab)$ and $\nt{\xb - \Ab\hsbb_{0,\delta}} \le \delta$.
In other words, {\em not only $P_{0,\delta}$ is stable, but also any other method for `approximate' sparse representation is stable\/} provided that it provides a sparse enough estimation.
More precisely:

\medskip
\begin{theorem}[Stability of approximate sparse representation]
\label{th: Generalized Theorem}\em
Suppose that the noiseless signal $\xb_0$ has a sparse representation $\xb_0=\Ab \sbb_0$ satisfying $\nz{\sbb_0} <
\frac{1}{2}\spark(\Ab)$. Let also $\xb=\xb_0+\nb$ be a noisy measurement of $\xb_0$ and $\nt{\nb} \le \eps$.
If we have at hand an estimation $\hsbb_{0,\delta}$ of the sparse representation coefficients which satisfies $\nz{\hsbb_{0,\delta}} < \frac{1}{2} \spark(\Ab)$ and $\nt{\xb - \Ab\hsbb_{0,\delta}} \le \delta$, then:
\begin{equation}
	\nt{\hsbb_{0,\delta}-\sbb_0} \le \frac{\delta+\eps}{\sm{q}},
	\label{eq: gen bound}
\end{equation}
\end{theorem}
\medskip

\begin{IEEEproof} It is easily obtained by following the same steps as the proof of Theorem~\ref{th: Main Theorem}: equations (\ref{eq: upper bound on x diff}) and (\ref{eq: temp1}) still hold. We then note that:
\begin{equation}
	\nz{\hsbb_{0,\delta}-\sbb_0} \le \nz{\hsbb_{0,\delta}} + \nz{\sbb_0} < \spark(\Ab)
\end{equation}
and hence $\nz{\hsbb_{0,\delta}-\sbb_0}\le q(\Ab)$. Consequently, instead of (\ref{eq: Bv low bound}) we write:
\begin{equation}
   \nt{\Bb \vb} \ge \sm{q} \nt{\vb}
\end{equation}
which in combination by (\ref{eq: upper bound on x diff}) and (\ref{eq: temp1}) proves (\ref{eq: gen bound}).
\end{IEEEproof}

\medskip

{\bf Remark.\ } Note that the condition $\delta \ge \eps$ does not explicitly appeared in Theorem~\ref{th: Generalized Theorem}, and is no more essential (while it was essential in Theorem~\ref{th: Main Theorem}, because it was necessary to insure that $P_{0,\delta}$ gives an estimation satisfying $\nz{\hsbb_{0,\delta}}\le\nz{\sbb_0}$, which was essential in the proof). However, implicitly, the $\delta$ in Theorem~\ref{th: Generalized Theorem} cannot be too small, because for a very small $\delta$, it is possible that there exists no $\hsbb_{0,\delta}$ satisfying $\nt{\xb-\Ab\hsbb_{0,\delta}}\le \delta$.

\section{Conclusion}
Since minimizing $\ell^1$ norm has been one of the first and most successful ideas for finding the sparsest solution of an USLE, some theoretical aspects of the sparsest solution are currently too much influenced by the $\ell^1$ minimization idea. Currently, with the availability of the algorithms that try to find the sparse solution by means of other approaches, \eg\ SL0 and Robust-SL0, some of the properties of the sparsest solution need to be revisited. In this paper, we studied the stability of the sparsest solution, and we showed that it is stable not only where $\nz{\sbb_0}< (1+M^{-1})/2$, but also for the whole uniqueness range $\nz{\sbb_0}< \frac{1}{2} \spark(\Ab)$. These results prove the practical interest of designing $\ell^0$-norm minimization algorithms, since they can provide a good estimation from noisy data, with the weakest condition of sparsity.


TITLE: Supremum and compact sets
QUESTION [1 upvotes]: $8$. Show that for any compact set $K$ and any continuous function $f:\Bbb R\to\Bbb R$, $f(K)$ is also a compact set. Deduce that there exists $x^*\in K$ such that $f(x^*)=\sup_{x\in K}f(x)$.
$8$. Let $\{A_\alpha\}_\alpha$ be an open covering for $f(K)$. Then $$f(K)\subset\bigcup_\alpha A_\alpha\Leftrightarrow K\subset f^{-1}\left(\bigcup_\alpha A_\alpha\right)=\bigcup_\alpha f^{-1}(A_\alpha)\;,$$ where the last inequality can be proved in a similar way as the one at exercise $4$ for the union of two. We have seen in the lectures that if $A_\alpha$ is open, and $f$ is continuous, $f^{-1}(A_\alpha)$ is also open. Now, since $K$ is compact, there exists a finite subcovering for $K$. That is $$K\subset\bigcup_{j=1}^N f^{-1}(A_{\alpha_j})=f^{-1}\left(\bigcup_{j=1}^NA_{\alpha_j}\right)\Leftrightarrow f(K)\subset\bigcup_{j=1}^NA_{\alpha_j}\;.$$ Then, $f(K)$ is a compact set. Since we know that any compact set is bounded, the completeness axiom for the real line yields that there exists $s=\sup\{f(x):x\in K\}$. Hence, there exists a sequence $x_n\in K$ such that $\lim_nf(x_n)=s$. But, since $f(K)$ is closed, $s\in f(K)$. Hence, there exists $x^*\in K$ such that $f(x^*)=s$.

I don’t follow the italicized part of the solution just before the end.

REPLY [1 votes]: As $s = \sup f(K)$ and $f(K)$ is bounded there exists a sequence $y_n \in f(K)$ such that $$\lim y_n = \lim f(x_n) = s$$
Just notice that $$s - \frac{1}{n} < y_n \leq s$$
Then as $y_n = f(x_n)$ for some $x_n \in K$, there exists a sequence $x_n \in K$ such that what you sublined is true.


TITLE: "Inverse" of tensor product
QUESTION [4 upvotes]: I am trying to figure out something. I have a 4-tensor $\phi_{i \, j \, k \, \ell}$ and I know that $\phi = A \otimes B$, being $A$ and $B$ two matrices. With indices, I know this:
$\phi_{i \, j \, k \, \ell} = A_{k \, i} \, B_{j \, \ell}$
Now, if I know $A$ and $B$ I can create $\phi$. How can I do the inverse? If I know $\phi$, how can I find $A$ and $B$?
I know this is not an "inverse" tensor product, but I hope I was sufficiently clear :)

REPLY [3 votes]: First of all, if you're under the impression that there is going to be a unique $A$ and $B$, let's dispel that expectation.
The equation given $\phi_{i \, j \, k \, \ell} = A_{k \, i} \, B_{j \, \ell}$ describes a "outer product" of two row vectors $A$ and $B$: $A^TB=\phi$. (We could establish the convention here of writing $A$ and $B$ as vectors by lexicographically ordering the indices.)
Using any nonzero scalar $\lambda$, you can see that $(A^T\lambda)(\lambda^{-1}B)=A^TB=\phi$, so you will have at least as many factorizations of $\phi$ as there are nonzero $\lambda$ in your field. Or even worse, if $\phi=0$, then you could write $A=0$ and use arbitrary $B$. (That is a sort of degenerate case.)
You can uncover a unique $A$ and $B$ if you know a nonzero term of $A$, however. Looking at the outer product $A^TB$, you can see that the rows of $\phi$ are just scalar multiples of the row vector $B$. Let's say you know $\phi$ and one nonzero entry of $A$, say $A_{11}$ for the sake of an example. You could then go to the row of $\phi$ corresponding to multiplication by $A_{11}$ (row $\phi_{11}$ given by entries $\phi_{1,j,1,\ell}$) and then divide all entries by $A_{11}$, uncovering exactly what $B$ is.
The columns of $\phi$ are also scalar multiples of $A^T$. By taking a nonzero entry of $B$ (assuming there is one, otherwise we are in the degenerate case), you can analogously go to the column corresponding to the nonzero entry of $B$ and divide through by the entry to retrieve $A^T$.


TITLE: a point process is characterized by its void probabilities
QUESTION [2 upvotes]: Consider a planar point process $X$ and call $N_A = \text{Card}\big( X \cap A\big)$ the number of points inside the subset $A \subset \mathbb{R}^2$. If one knows the law of $(N_{A_1}, \ldots, N_{A_r})$  for any sets $A_1, \ldots, A_r$, then the process is completely characterized. I recently learned that it in fact suffices to know $f(A)=P(N_A=0)$ (called the void-probability function) for any set $A$ in order to completely characterize the law of $X$.
Intuitively, I do not understand why such a result is true. Indeed, the knowledge of the function $f$ brings some information in the correlation structure of the process $X$: nevertheless, I still fail to understand how the function $f$ can encode the whole correlation structure of the process. Any thoughts on this ?

REPLY [3 votes]: To add to Omer's concise explanation, the general result is known as Choquet's capacity theorem. It says that the void probabilities characterise any random closed set. Simple point processes are an example of random closed sets.


TITLE: Can a polynomial with degree (r+s-1) have (r+s) distinct roots?
QUESTION [0 upvotes]: While reading about generalised eigenvectors, i came to a strange proof. It goes like
If p is a polynomial which has r distinct roots {λ1,λ2...,λr}, and q is a polynomial with s distinct roots {μ1,μ2...,μs}.
We can have two polynomials a(of degree s-1),b(of degree r-1) such that a(x)=p(x)^-1,when x={μ1,μ2...,μs} and b(x)=q(x)^-1,when x={λ1,λ2...,λr}.
Now a(x).p(x)+b(x).q(x)=1 for x={μ1,μ2...,μs,λ1,λ2...,λr}, all being distinct by definition.
Writing ap+bq-1=0, has r+s roots, while its a polynomial with degree at most (r+s-1). How does it works?
Reference http://math.mit.edu/~dav/generalized.pdf

REPLY [0 votes]: Any nontrivial polynomial of degree at most $r+s-1$ can have at most $r+s-1$ distinct roots. So if $a(x)p(x) + b(x)q(x) - 1$ is equal to $0$ at $r+s$ points, that means it can only be the trivial polynomial which is $0$ everywhere.


TITLE: Does expected value change as the number of bets increases?
QUESTION [0 upvotes]: I am reading about Expected Value in the context of roulette-game. I understand that it is the weighted sum of all the probabilities.
Here is the scenario:
The roulette game consists of a small ball and a wheel with 38
numbered pockets around the edge. As the wheel is spun, the ball
bounces around randomly until it settles down in one of the pockets.
Suppose random variable X represents the (monetary) outcome of a $1 bet on a single
number ("straight up" bet). If the bet wins (which happens with
probability 1/38 in American roulette), the payoff is $35; otherwise
the player loses the bet.

Expected value for the above bet could be calculated as :
-1 * 37/38 + 35 * 1/38

which comes equal to -0.0526. Now what does it really mean? Can expected value change as the total number of bets increases? If yes, what does the above number actually mean? If it will not change with the increasing number of bets, are there some other factors that could influence the expected value?

REPLY [1 votes]: To make this a little easier with the arithmetic, suppose we had a smaller roulette wheel, with numbers $0$ through $9$.  If you bet a dollar on any number, you win eight dollars if your number comes up; otherwise, you lose your your one-dollar bet.
The expected gain from this game is
$$
0.9 \times (-1) + 0.1 \times 8 = -0.9+0.8 = -0.1
$$
That $-0.1$ represents the house percentage, or vigorish ("vig" for short).  In the long run, you will lose a dime for every dollar you bet, but it may take a large number of bets for this percentage to become apparent; in the short run, you may lose a different percentage, or even come out ahead.
If you were to play a thousand games, for instance, you would lose, on average, about $100$ dollars.  However, there would be some dispersion in the actual amount you would lose; this dispersion or spread is expressed by something called the standard deviation.  The standard deviation in this case is about $85$ dollars.  Your actual losses would be distributed in a bell curve, such that about $68$ percent of the time, the loss would be within one standard deviation of the average—that is, between $15$ and $185$ dollars.  The dispersion is actually quite substantial.


TITLE: Area under region $y=log(x)$
QUESTION [2 upvotes]: I encountered a problem that asks me to calculate the area between the curves $y=0$, $y=-2$, $y=log(x)$, and $x=0$.
But in order to do so, it requires to calculate and use the following integral: $\int_{-2}^{0}{e^x}{dx} = 1 - \frac{1}{e^2}$.
I can't find a way of using that value, since the logarithm function is in base 10. (If $y=ln(x)$ I could claim that there is symmetry along $x=y$ and that would be proof enough to say the area is the same, wouldn't it?).
What step should I look into?
Thanks a lot.

REPLY [1 votes]: If you draw out the graphs, you will realise that the area you are trying to find is $$\int_{-2}^0 x dy= \int_{-2}^0 e^y dy$$
and that looks very similar to $\int_{-2}^{0}{e^x}{dx}$ with the only difference being that $y$ has been renamed to $x$. In other words, when you evaluate $\int_{-2}^{0}{e^x}{dx}$ and $\int_{-2}^{0}{e^y}{dy}$ you should get the same value.
Then you can use the result $\int_{-2}^{0}{e^x}{dx} = 1 - \frac{1}{e^2}$ to deduce that the area you are looking for is in fact $1 - \frac{1}{e^2}$.
EDIT: I am assuming that by $log (x)$ you are referring to the natural logarithm.