TITLE: What is the current big question or motivation in quantum information?
QUESTION [6 upvotes]: As an prospective student, I am facing a crossing as many people did. I would love to know what is the current big question or motivation in the quantum information society? If anyone knows the answer for condensed matter or bio-physics or computational chemistry, you are welcome. Thanks!

REPLY [7 votes]: Expanding upon what others have already said and adding some things, the main experimental challenges are quantum control:

Quantum communications: For cryptography, we need entanglement generation and maintenance ovver very large distances. Currently, there seems to be a barrier at about 400km due to decoherence and the quantum repeaters availabe. This needs to be overcome. 1st challenge: Build a good quantum repeater and demonstrate a quantum network over hundreds of kilometres. 2nd challenge: Implement satellite communications (might be easier than land-based communication for very large distances). Condensed matter people might be interested in repeater designs and implementations. If the challenges are overcome, one can begin to implement cryptographic schemes and think about industrialisation.
Quantum computers: Actually build a working quantum computer that can do anything new. This is the field where condensed matter physicists have a huge playground: The main problem for quantum computation at present relies in 1st challenge: creating good (high fidelity) multi-qubit gates and 2nd challenge: scaling the computer. No one needs a computer with 8 qubits. Condensed matter approaches might be best suited for the 2nd challenge once the first has been addressed, hence they are a very active research area. Both essentially means battling against decoherence. All research here ist still pretty basic, a working computer and what it might be useful for is at least 10 years in the future. Both challenges are essentially about quantum control.
Quantum simulatons: This is what quantum computing will actually be very good at. Simulating a chemical system is hard - especially because it is quantum mechanical. Why not simulate it using quantum mechanics? This idea is currently being implemented on certain smaller systems and might already produce results within ten years. Once again, the main challenges are achieving better control. Note that this is essentially reclaiming the domain of computational chemistry to physics. You'll need more physics than comutational chemistry to do this. Biophysics is still years away.


TITLE: What is the most compelling reason to believe Church's thesis?
QUESTION [12 upvotes]: Church's thesis states that the Turing machine is a universal model of computation.  What is the most compelling argument supporting this assertion?

REPLY [6 votes]: There is a good amount of 'experimental evidence', I guess. There have been lots of other models proposed, and they've all been proven to be computationally equivalent to Turing machines. This is true even for quantum computers. That is, they can all do the exact same things that Turing machines can. But there is also the question of whether this equivalence is a polynomial-time equivalence. This leads to the 'strong Church-Turing thesis'. It is believed by many that quantum computers are strictly better than classical computers in terms of time complexity, though as far as I know this has not been proven yet. If this were proven, then the strong Church-Turing thesis would be false. Then the natural thing would be to assert a quantum version of the strong Church-Turing thesis...

Edit: I see that this topic has been closed. I agree that it is perhaps too philosophical for Math Overflow. But still, let me make a few more mathematical comments, and one philosophical comment. Consider the lambda calculus. This is a very simple model of computation; its functionality is essentially restricted to a notion of a function and a notion of evaluation of functions which allows for recursion. The interesting thing is that even with this seemingly very limited functionality, the lambda calculus is still Turing-equivalent. What this shows is that it is relatively easy for a "reasonable model of computation" to be at least as powerful as Turing machines; once it has a notion of functions and a notion of evaluation of functions, it will be at least as powerful as the lambda calculus, and thus Turing machines. The more philosophical question arises when we consider the converse situation, namely, why should we expect "reasonable models of computation" to not be strictly more powerful than Turing machines? There is (probably) no good mathematical answer to this, because there is (probably) no good mathematical definition of "reasonable".

REPLY [3 votes]: The usual answer is that all proposed models of computation have turned out to be equivalent.


text:
\section{Proofs for Sec. \ref{pca_section}} \label{proofs_pca_section}

\subsection{Proof of Theorem \ref{mainthm_pca}}

\begin{proof}[Proof of Theorem \ref{mainthm_pca}]
This uses the Davis-Kahan sin theta theorem \cite{davis_kahan}:
\begin{lem}[Davis-Kahan $\sin \theta$ theorem]\label{sintheta}
Let $\D_0$ be a Hermitian matrix whose span of top $r$ eigenvectors equals $\Span(\P)$. Let $\D$ be the Hermitian matrix with top $r$ eigenvectors  $\Phat$. Then,
\begin{align}
\SE(\Phat,\P) &\le \frac{\|(\D-\D_0)\P\|}{\lambda_r(\D_0) - \lambda_{r+1}(\D)} \nonumber \\
& \le  \frac{\|\D-\D_0\|}{\lambda_r(\D_0) - \lambda_{r+1}(\D_0) - \lambda_{\max}(\D-\D_0)}

\label{sintheta_bnd_2}
\end{align}
as long as the denominator is positive. The second inequality follows from the first using Weyl's inequality.
\end{lem}

For our proof, set $\bm{D}_0 = \frac{1}{\tmaxpca}\sum_t \lt\lt{}'$. Notice that this is a Hermitian matrix with $\P$ as the top $r$ eigenvectors.
Let $\bm{D} = \frac{1}{\tmaxpca}\sum_t \yt \yt{}'$. Recall that $\Phat$ is its matrix of top $r$ eigenvectors.
Observe
\begin{align*}
&\D - \D_0 = \frac{1}{\tmaxpca} \sum_t (\yt \yt{}' - \lt \lt{}') \\
&= \frac{1}{\tmaxpca} \sum_t  ( \wt \wt{}' + \bv \bv{}'  + \lt \wt{}'  + \bv \wt{}'  \\
&+ \lt \bv{}' + \wt \lt{}' + \wt \bv{}' + \bv \lt{}'  ) \\
&:= \noise_{\w} + \noise_{\bv} + \cross_{\l,\w}  +  \cross_{\l, \bv} \\
&+ \cross_{\bv,\w} +  \cross_{\l, \w}{}' + \cross_{\l, \bv}{}'  + \cross_{\bv,\w}{}' \\
&: = \noise + \cross + \cross{}'
\end{align*}
Also notice that $\lambda_{r+1}(\D_0) = 0$, $\lambda_r(\D_0) = \lambda_{\min}\left(\frac{1}{\tmaxpca} \sum_t \at \at{}'\right)$.
Now, applying Theorem \ref{sintheta},
\begin{align*}
\SE(\Phat,\P) \leq \frac{2\|\cross\| + \|\noise\|}{\lambda_{\min}\left(\frac{1}{\tmaxpca}\sum_t\at\at{}'\right) - \mathrm{numerator}}
\end{align*}

Now, we can bound $\|\cross\| \leq \|\E[\cross]\| + \|\cross - \E[\cross]\|$ and similarly for the $\noise$ term. We use the Cauchy-Schwartz inequality for bounding the expected values of both.

Recall that $\M_t = \M_{2,t} \M_{1,t}$ with $\bz:= \|\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{2,t}{}'\|$ and $ q:=  \max_t \|\M_{1,t} \P\|$ with $q < 2$. Thus,
\begin{align}
&\|\E[\noise]\| \leq  \norm{\frac{1}{\tmaxpca} \sum_t \M_t \P \Lam \P{}'\M_{1,t}{}' \M_{2,t}{}'} + \norm{\Sigma_{\bv}} \nn \\
& \le  \sqrt{\norm{\frac{1}{\tmaxpca} \sum_t \M_t \P \Lam \P{}'\M_{1,t}{}'(\cdot){}'}  \norm{\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{2,t}{}'} } + \lambda_v^+ \nn \\
& \le  \sqrt{\max_t \|\M_t\P \Lam \P{}'\M_{1,t}{}' \|^2  \ \bz} + \lambda_v^+ \le  \sqrt{\bz} q^2 \lambda^+ + \lambda_v^+
\label{bnd_avg_sig_noise_cor_bnd_2}
\end{align}
Similarly,
\begin{align}
&\|\E[\cross_{\l,\wt}]\| = \norm{\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{1,t} \P \Lam \P{}'} \nn \\
& \le \sqrt{ \norm{\frac{1}{\tmaxpca} \sum_t \P \Lam \P{}'\M_{1,t}{}'\M_{1,t}\P \Lam \P{}'}   \norm{\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{2,t}{}'} } \nn \\
& \le \sqrt{ \max_t \|\M_{1,t}\P \Lam \P{}'\|^2 \ \bz } \le  \sqrt{\bz} q \lambda^+
\label{bnd_avg_sig_noise_cor_bnd_1}
\end{align}

Since $\bv$ is uncorrelated noise, $\E[\cross_{\l,\bv}] = 0$ and $\E[\cross_{\wt,\bv}] = 0$.
We now lower bound $\lambda_{\min}\left(\frac{1}{\tmaxpca}\sum_t \at \at{}'\right)$ as
\begin{align*}
\lambda_{\min}\left(\frac{1}{\tmaxpca}\sum_t \at \at{}' \right) &= \lambda_{\min}\left( \Lam - \left(\frac{1}{\tmaxpca}\sum_t \at \at{}' - \Lam\right) \right) \\
 &\geq \lambda_{\min}(\Lam) -  \lambda_{\max}\left(\frac{1}{\tmaxpca}\sum_t \at \at{}'- \Lam \right) \\
&\geq \lambda^- - \norm{\frac{1}{\tmaxpca}\sum_t \at \at{}' - \Lam}
\end{align*}
and thus we have
\begin{align*}
&\SE(\Phat, \P) \\
&\leq \frac{4 \sqrt{\bz}q \lambda^+ + \lambda_v^+ + 2\|\cross - \E[\cross]\| + \|\noise - \E[\noise]\|}{\lambda^- - \norm{\frac{1}{\tmaxpca}\sum_t\at \at{}' - \Lam} - \mathrm{numerator}}
\end{align*}
\subsubsection{Concentration bounds}
Now we only need to bound $\|\noise - \E[\noise]\|$ and $\|\cross - \E[\cross]\|$. These are often referred to as  ``statistical error'', while the error due to nonzero  $\| \E[\cross]\|$ or $\| \E[\noise]\|$ is called the ``bias''.  We use concentration bounds from Lemma \ref{hp_bnds}.
\begin{align*}
& \|\noise - \E[\noise]\| + 2 \|\cross - \E[\cross]\| \\
 \leq & \norm{\frac{1}{\tmaxpca}\sum_t(\wt \wt{}' - \E[\wt\wt{}'])]} + \norm{\frac{1}{\tmaxpca}\sum_t(\bv \bv{}' - \E[\bv \bv{}'])]} \\
 &+ 2\norm{\frac{1}{\tmaxpca}\sum_t(\lt \wt{}' - \E[\lt\wt{}'])]} \\
& + 2\norm{\frac{1}{\tmaxpca}\sum_t \lt \bv{}'} + 2\norm{\frac{1}{\tmaxpca}\sum_t \wt \bv{}'} \\
 \leq &
C\sqrt{\eta} q^2  f  \sqrt{\frac{r \log n}{\tmaxpca}}   \lambda^- +
C \sqrt{\eta}  \frac{\lambda_v^+}{\lambda^-}  \sqrt{\frac{r \log n}{\tmaxpca}}   \lambda^-  \\
&+
C \sqrt{\eta} q f  \sqrt{\frac{r \log n}{\tmaxpca}}     \lambda^- \\

& +  C   \sqrt{\eta}  \sqrt{\frac{\lambda_v^+}{\lambda^-} f} \sqrt{\frac{r \log n}{\tmaxpca}} \lambda^-  +  C   \sqrt{\eta} q \sqrt{\frac{\lambda_v^+}{\lambda^-} f}  \sqrt{\frac{r \log n}{\tmaxpca}} \lambda^- \\
  \leq & C   \sqrt{\eta}   q f \sqrt{\frac{r \log n}{\tmaxpca}} \lambda^-   +  C   \sqrt{\eta}  \sqrt{\frac{\lambda_v^+}{\lambda^-} f}  \sqrt{\frac{r \log n}{\tmaxpca}} \lambda^-
:= \epsbnd\lambda^-
\end{align*}
where the last line follows from using $q^2 < 2q $ and $\lambda_v^+ \leq \lambda^+$.

In case we only need to bound $\|\noise - \E[\noise]\|$, we can get a tighter bound that contains only the first two terms and not all five. Clearly, we have
\begin{align*}
& \|\noise - \E[\noise]\| \\
& \le C\sqrt{\eta} q^2  f  \sqrt{\frac{r \log n}{\tmaxpca}}   \lambda^- +
C \sqrt{\eta}  \frac{\lambda_v^+}{\lambda^-}  \sqrt{\frac{r \log n}{\tmaxpca}}   \lambda^-  +\\
& : = H_{noise}(\alpha)
\end{align*}

The bound on $\|\frac{1}{\tmaxpca} \sum_t \at \at{}' - \Lam\|_2$ follows directly from the first item of Lemma \ref{hp_bnds}.
\end{proof}

\subsection{A useful corollary that follows from above proof}
From the above proof, we can write out a bound for   $\| \bphi\mathrm{cross} \bphi' \| $  for a projection matrix $\bphi$ by noticing that
each term of $\cross $ is of the form $\sum_t \lt (.)' = \P \sum_t \at (.)'$. Thus $\| \P' \mathrm{cross} \|  = \|\cross\|$. Thus,
$\| \bphi\mathrm{cross} \bphi' \| \le  \|\bphi \P\| \|\mathrm{cross}\| \le \|\bphi \P\| ( \|\E[\mathrm{cross}]\|  +  \|\cross - \E[\cross]\| )$.
Similarly, we can also get a bound on $\lambda_{\max}( \mathrm{noise} ) = \|\mathrm{noise}\|$.

Assume $b = 0.01/f^2$, $ q> \zz > \sqrt{g}$.
Consider $\mathrm{cross}$. If $\alpha \ge C \max\left( \frac{q^2 f^2}{\epsilon_1^2} r \log n, \frac{g f}{\epsilon_1^2} \max(r_v,r) \log n\right)$, then $\epsbnd \le \epsilon_1 \lambda^-$.
If we set $\epsilon_1 = 0.002 \max(  \sqrt{b} q, \sqrt{b} \zz)$ and $b = 0.01/f^2$ (bound on $\outfracrow(\alpha)$), then, since $\zz > \sqrt{g}$ , $\alpha = C f^2 \max(r_v,r) \log n$ suffices. Since $q \ge \zz$, then, $\epsilon_1 = 0.002 \sqrt{b} q$. Thus,
\[
 \| \bphi\mathrm{cross} \bphi' \|   \le  \|\bphi \P\| (2 \sqrt{b} q \lambda^+  + \epsbnd \lambda^-)  \le 2.02 \sqrt{b} \|\bphi \P\| q \lambda^+
\]

Consider $\noise$.  We will use $H_{noise}(\alpha)$ for this. If $\alpha > C \max\left( \frac{q^4 f^2}{\epsilon_2^2} r \log n, \frac{g^2}{\epsilon_2^2}  \max(r_v,r) \log n\right)$, then  $H_{noise}(\alpha) \le \epsilon_2 \lambda^-$. If we set $\epsilon_2 = 0.002 \sqrt{b} \max(   q^2, \zz^2)$, then since $\zz^4 > g^2$, thus, $\alpha = C f^2 \max(r_v,r) \log n$ suffices. Since $q> \zz$, $\epsilon_2 = 0.002 \sqrt{b}  q^2$. We have the following corollary.

\begin{corollary} \label{pca_corol}

If $\alpha = C f^2 \max(r_v,r) \log n$, and if $ q \ge \zz > \sqrt{g}$, then, w.p. $1 - 10 n^{-10}$,
\begin{align*}
 \| \bphi\mathrm{cross} \bphi' \|  & \le  \|\bphi \P\| (2 \sqrt{b} q \lambda^+  + \epsbnd \lambda^-)  \\
 &\le 2.02 \sqrt{b} \|\bphi \P\| q \lambda^+,
 \\
 \lambda_{\max}( \bphi \mathrm{noise} \bphi)  \le \|\noise\|
 & \le  \sqrt{b} q^2 \lambda^+  + \lambda_v^+  + \epsbnd \lambda^- \\ &\le 1.01 \sqrt{b} q^2 \lambda^+  + \lambda_v^+ \\
& \le 1.01 \sqrt{b} q^2 \lambda^+  + \zz^2 \lambda^-

 \end{align*}
\end{corollary}

\subsection{Main idea of the proof of Corollary \ref{pca_ssch}} \label{proof_pca_ssch_idea}
The key difference in this proof is our choice of $\D_0$. Since we want to bound $\SE(\Phat,\P)$, we need to pick it in such a way that its matrix of top $r$ singular vectors equals $\Span(\P)$. We pick
\[
\D_0 = \frac{1}{\alpha}  \P \left(  (\alpha-\alpha_0) \Lam +  \alpha_0 \P' \P_0  \Lam \P_0' \P \right) \P'
\]
Clearly, $\lambda_{r+1}(\D_0) = 0$. With this choice of $\D_0$,
\begin{align*}
\D - \D_0 &= \cross + \cross{}' +  \noise  \\
&+ \left(\frac{1}{\alpha} \sum_t \lt \lt'  - \E[\frac{1}{\alpha} \sum_t \lt \lt'] \right) +  \left( \E[\frac{1}{\alpha} \sum_t \lt \lt'] - \D_0 \right)
\end{align*}
where $\cross, \noise$ are as defined earlier with the change that $\lt$ is now defined differently. Thus, the only thing that changes when bounding these is our definition of $q$. The last term in the expression above equals $c_0 \P_\perp \P_\perp' \P_0  \Lam \P_0' \P_\perp \P_\perp{}'  + c_0 \P_\perp \P_\perp' \P_0  \Lam \P_0' \P \P' + (.)'$ with $c_0: = \frac{\alpha_0}{\alpha}$. This is what  generates the extra $4 \Delta f$ term in our $\SE$ bound.
A complete proof is provided in the Supplement given in the ArXiv version of this work \cite[Appendix IV-A]{jsait_arxiv}).

\subsection{Concentration Bounds}
We state the lemma below so that it can also be used in proving the most general PCA result given in the Supplement given in the ArXiv version of this work \cite[Appendix IV-A]{jsait_arxiv}).

Let
$\Lam_t = \E[\at \at{}']$, $\Lamb = \frac{1}{\tmaxpca}\sum_t \Lam_t$, $\lambda_{\max}^+ := \max_t \|\Lam_t\|$, $\lambda^-_{\avg} = \lambda_{\min}(\Lamb)$, $f = \lambda_{max}^+/\lambda^-_{\avg}$, $\lambda_{v,\max}^+ := \max_t \|\E[\vp_t\vp_t{}']\|$ and $\nois = \lambda_{v,\max}^+/\lambda^-_{\avg}$.

To use the lemma under the simpler i.i.d. assumption used in the main paper, remove the $_{\max}, _{\avg}$ subscripts from all terms, e.g., replace $\lambda_{\max}^+$ by $\lambda^+$, $\lambda^-_{\avg}$ by $\lambda^-$ and so on.

\begin{lem}\label{hp_bnds}
With probability at least $1 - 10n^{-10}$,
\begin{align*}

&  \left\|\frac{1}{\tmaxpca}\sum_t \at \at{}' -  \Lamb \right\| \le    C \sqrt{\eta} f \sqrt{\frac{r \log n}{\tmaxpca}}  \lambda^-_{\avg}, \\

& \left\|\frac{1}{\tmaxpca}\sum_t \lt \wt{}' - \frac{1}{\tmaxpca}\E\left[\sum_t \lt \wt{}'\right] \right\|_2 \le C\sqrt{\eta} q f  \sqrt{\frac{r \log n}{\tmaxpca}}     \lambda^-_{\avg}, \\

& \left\|\frac{1}{\tmaxpca}\sum_t \wt \wt{}' - \frac{1}{\tmaxpca}\E\left[\sum_t \wt \wt{}'\right] \right\|_2 \le  C\sqrt{\eta} q^2  f  \sqrt{\frac{r \log n}{\tmaxpca}}   \lambda^-_{\avg}, \\

& \left\|\frac{1}{{\tmaxpca}} \sum_t \lt {\vp_t}' \right\|_2 \le  C\sqrt{\eta} \sqrt{\nois f} \sqrt{\frac{ \max(r_v, r) \log n}{\tmaxpca}} \lambda^-_{\avg}, \\
& \left\|\frac{1}{{\tmaxpca}} \sum_t \wt {\vp_t}' \right\|_2 \le  C\sqrt{\eta} q \sqrt{\nois f} \sqrt{\frac{ \max(r_v, r) \log n}{\tmaxpca}} \lambda^-_{\avg}, \\

& \left\| \frac{1}{{\tmaxpca}} \sum_t  \vp_t {\vp_t}' - \frac{1}{{\tmaxpca}} \E\left[ \sum_t  \vp_t {\vp_t}' \right] \right\|_2 \le  C\sqrt{\eta}  \nois \sqrt{\frac{r_v \log n}{\tmaxpca}} \lambda^-_{\avg}. \\
\end{align*}
\end{lem}

\begin{proof}[Proof of Lemma \ref{hp_bnds}]  \

{\em $\at \at{}'$ term. } This and all other items use Matrix Bernstein for rectangular matrices, Theorem 1.6 of \cite{tail_bound}. This says the following. For a finite sequence of $d_1 \times d_2$ zero mean independent matrices $\Z_k$ with
\begin{align*}
& \|\Z_k\|_2 \le R, \text{ and}  \\
&\max(\|\sum_k \E[ \Z_k{}'\Z_k ]\|_2, \|\sum_k \E[ \Z_k\Z_k{}' ]\|_2) \le \sigma^2,
\end{align*}
we have $\Pr(\|\sum_k \Z_k\|_2 \ge s ) \le (d_1+d_2) \exp\left(- \frac{s^2/2}{\sigma^2 + Rs / 3}\right) \leq (d_1+d_2) \exp\left(- c\min\left(\frac{s^2}{2\sigma^2}, \frac{3s}{2R}\right)\right)$. Let $\tilde{\Z}_t := \at \at{}'$ and we apply the above result to $\Z_t = \tilde{\Z}_t - \E[\tilde{\Z}_t]$. with $s = \epsilon \tmaxpca$. Now it is easy to see that $\|\Z_t\| \leq 2\|\at\at{}'\| \leq 2 \|\at\|_2^2 \leq 2 \eta r \lambda_{\max}^+ := R$ and similarly, $\|\E[\Z_t^2]\| = \|\E[\|\at\|_2^2 \at\at{}']\|\leq \tmaxpca \cdot  \max_{\at} \|\at\|_2^2 \cdot \max_t \E[\at\at{}'] \leq \tmaxpca \eta r (\lambda_{\max}^+)^2 := \sigma^2 $ and thus, w.p. at most $2 r \exp\left( - c \min\left( \frac{\epsilon^2 \tmaxpca}{r (\lambda_{\max}^+)^2}, \frac{\epsilon^2\tmax}{r \lambda_{\max}^+ \epsilon} \right) \right)$. Now we set $\epsilon = \epsilon_5 \lambda_{\min}^-$ with $\epsilon_5 = C \sqrt\eta f \sqrt{\frac{r\log n}{\tmaxpca}}$ to get our result.

{\em $\lt \wt'$ term. }

Let $\Z_t := \lt \wt{}'$. We apply this result to $\tilde{\Z}_t:= \Z_t - \E[\Z_t]$ with $s = \epsilon \tmaxpca$. To get the values of $R$ and $\sigma^2$ in a simple fashion, we use the facts that (i)
if $\|\Z_t\|_2 \le R_1$, then $\|\tilde{\Z}_t\| \le 2R_1$; and (ii) $\sum_t \E[\tilde{\Z}_t \tilde{\Z}_t{}'] \preccurlyeq \sum_t \E[\Z_t \Z_t{}']$.
Thus, we can set $R$ to two times the bound on $\|\Z_t\|_2$ and  we can set $\sigma^2$ as the maximum of the bounds on $\|\sum_t \E[\Z_t \Z_t{}']\|_2$ and $\|\sum_t \E[\Z_t{}' \Z_t]\|_2$.

It is easy to see that  $R = 2 \sqrt{\eta  r \lambda^+_{\max}} \sqrt{\eta r  q^2 \lambda^+_{\max}} = 2 \eta r q \lambda^+_{\max}$. To get $\sigma^2$, observe that
\begin{align*}
\left\| \sum_t \E[\wt \lt{}' \lt \wt{}'] \right\|_2 & \le \tmaxpca (\max_{\lt} \|\lt\|^2) \cdot \max_t  \|\E[\wt \wt{}']\| \\
& \le \tmaxpca \eta  r \lambda^+_{\max} \cdot  q^2 \lambda^+  = \tmaxpca \eta r q^2 (\lambda^+_{\max})^2.
\end{align*}

Repeating the above steps, we get the same bound on $\| \sum_t \E[\Z_t \Z_t{}'] \|_2$. Thus,  $\sigma^2 = \tmaxpca \eta r q^2 (\lambda^+_{\max})^2$.

Thus, we conclude that,
$
\left\|\sum_t \lt \wt{}' - \E[\sum_t \lt \wt{}'] \right\|_2 \ge \epsilon \tmaxpca

$
w.p. at most
$2n \exp\left(- c \min \left(\frac{\epsilon^2 \tmaxpca}{\eta r q^2 (\lambda^+_{\max})^2}, \frac{\epsilon \tmaxpca}{\eta r q \lambda^+_{\max}}\right)\right)$

Set $\epsilon = \epsilon_0 \lambda^-$ with $\epsilon_0 = c q f \sqrt{\frac{r \log n}{\tmaxpca}}$ so that our bound holds w.p. at most $2n^{-10}$. This follows because $\tmaxpca \geq C f^2 r \log n$.

{\em $\wt \wt{}'$ , $\lt \vp_t'$, $\wt \vp_t'$ and $\vp_t \vp_t'$ terms. } Apply matrix Bernstein as done above.
\end{proof}

\section{Proof of Theorem \ref{thm1} and Corollary \ref{cor:thm1}} \label{proof_of_thm1}

\begin{proof}[Proof of Theorem \ref{thm1}]
The overall structure of this proof is similar to that in \cite{rrpcp_isit15,rrpcp_aistats}.

Define
\[
\that_{j-1,fin}: =  \that_{j-1} + K \alpha, \  t_{j,*}=\that_{j-1,fin} + \left \lceil \frac{t_j - \that_{j-1,fin}}{\alpha} \right \rceil \alpha
\]
Thus, $\that_{j-1,fin}$ is the time at which the $(j-1)$-th subspace update is complete; w.h.p., this occurs before $t_j$. With this assumption, $t_{j,*}$ is such that $t_j$ lies in the interval $[t_{j,*}-\alpha+1,t_{j,*}]$.

\noindent Recall from the algorithm that we increment $j$ to $j+1$ at $t= \that_j+K\alpha:= \that_{j,fin}$.

Define the events
\ben
\item $\mathrm{Det0}:= \{\that_j = t_{j,*} \} = \{\lambda_{\max}(\frac{1}{\alpha} \sum_{t= t_{j,*}-\alpha+1}^{t_{j,*}} \bphi \lhat_t \lhat_t'\bphi) > \lthres\}$ and
\\ $\mathrm{Det1}:= \{\that_j = t_{j,*} + \alpha\} = \{\lambda_{\max}(\frac{1}{\alpha} \sum_{t= t_{j,*} +1}^{t_{j,*}+\alpha} \bphi \lhat_t \lhat_t'\bphi) > \lthres\} $,
\item $\mathrm{\subup}:=\cap_{k=1}^K  \mathrm{\subup}_k$ where $\mathrm{\subup}_k:= \{\SE(\Phat_{j,k}, \P_{j}) \le q_k\}$,

\item $\mathrm{NoFalseDets}:= \{\text{for all $\J^\alpha \subseteq [\that_{j,fin}, t_{j+1})$, } \\ \lambda_{\max}(\frac{1}{\alpha} \sum_{t \in \J^\alpha} \bphi \lhat_t \lhat_t'\bphi) \le \lthres\}$
\item $\Gamma_{0,\ed}:= \{\SE(\Phat_0, \P_0) \le 0.25 \}$,
\item  $\Gamma_{j,\ed}:= \Gamma_{j-1,\ed} \cap
\big( (\mathrm{Det0} \cap \mathrm{\subup} \cap \mathrm{NoFalseDets}) \cup
(\overline{\mathrm{Det0}} \cap \mathrm{Det1} \cap \mathrm{\subup} \cap \mathrm{NoFalseDets}) \big)$.
\een

Let $p_0$ denote the probability that, conditioned on $\Gamma_{j-1,\ed}$, the change got detected at $t=t_{j,*}$, i.e., let
\[
p_0:= \Pr(\mathrm{Det0}|\Gamma_{j-1,\ed}).
\]
Thus, $\Pr(\overline{\mathrm{Det0}}|\Gamma_{j-1,\ed}) = 1- p_0$. It is not easy to bound $p_0$. However, as we will see, this will not be needed. Assume that $\Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}}$ holds. Consider the interval $\J^\alpha: = [t_{j,*}, t_{j,*}+\alpha)$. This interval starts at or after $t_j$, so, for all $t$ in this interval, the subspace has changed. For this interval, $\bphi = \I - \Phat_{j-1} \Phat_{j-1}{}'$.
Applying the first item of Lemma \ref{lem:sschangedet}, w.p. at least $1-10n^{-10}$,
\[
\lambda_{\max} \left(\frac{1}{\alpha} \sum_{t \in \J^\alpha} \bphi \lhat_t \lhat_t'\bphi \right) \geq \lthres
\]
and thus $\that_j = t_{j,*} + \alpha$.

In other words,
\[
\Pr(\mathrm{Det1} | \Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}}) \ge 1 - 10n^{-10}.
\]

Conditioned on $\Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}} \cap \mathrm{Det1}$, the first SVD step is done at $t= \that_j + \alpha = t_{j,*} + 2\alpha$ and the subsequent steps are done every $\alpha$ samples. We can prove Lemma \ref{lem:reprocspcalemone} with $\Gamma_{j,0}$ replaced by $\Gamma_{j,\ed} \cap \overline{\mathrm{Det0}} \cap \mathrm{Det1}$ and Lemma \ref{lem:reprocspcalemk} with $\Gamma_{j,k-1}$ replaced by $\Gamma_{j,\ed} \cap \overline{\mathrm{Det0}} \cap \mathrm{Det1} \cap \subup_1 \cap \cdots \cap \subup_{k-1}$ and with the $k$-th SVD interval being $\J_k:=[\that_j+(k-1)\alpha, \that_j + k \alpha)$. Applying Lemmas \ref{lem:reprocspcalemone}, and \ref{lem:reprocspcalemk} for each $k$, we get
\[
\Pr(\subup |\Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}} \cap \mathrm{Det1}) \ge ( 1 - 10n^{-10})^{K+1}.
\]
We can also do a similar thing for the case when the  change is detected at $t_{j,*}$, i.e. when $\mathrm{Det0}$ holds. In this case, we replace $\Gamma_{j, 0}$ by $\Gamma_{j,\ed} \cap \mathrm{Det0}$ and $\Gamma_{j, k}$ by $\Gamma_{j,\ed} \cap \mathrm{Det0} \cap \subup_1 \cap \cdots \cap \subup_{k-1}$ and conclude that
\[
\Pr(\subup|\Gamma_{j-1,\ed} \cap \mathrm{Det0}) \ge ( 1 - 10n^{-10})^{K}.
\]

Finally consider the $\mathrm{NoFalseDets}$ event. First, assume that $\Gamma_{j-1,\ed} \cap \mathrm{Det0} \cap \subup$ holds.  Consider any interval $\J^\alpha \subseteq [\that_{j,fin}, t_{j+1})$. In this interval, $\Phat_{(t)} = \Phat_j$, $\bphi = \I -  \Phat_j \Phat_j{}'$ and $\SE(\Phat_j,\P_j) \le \zz$. Using the second part of Lemma \ref{lem:sschangedet} we conclude that w.p. at least $1- 10n^{-10}$,
\[
\lambda_{\max} \left(\frac{1}{\alpha} \sum_{t \in \J^\alpha} \bphi \lhat_t \lhat_t'\bphi \right)  < \lthres
\]
Since $\mathrm{Det0}$ holds, $\that_j = t_{j,*}$.
Thus, we have a total of $\lfloor \frac{t_{j+1} - t_{j,*} - K \alpha - \alphadel}{\alpha} \rfloor$ intervals $\J^\alpha$ that are subsets of $[\that_{j,fin}, t_{j+1})$. Moreover, $\lfloor \frac{t_{j+1} - t_{j,*} - K \alpha - \alphadel}{\alpha} \rfloor \le \lfloor \frac{t_{j+1} - t_j - K \alpha - \alphadel}{\alpha} \rfloor \le \lfloor \frac{t_{j+1} - t_j}{\alpha} \rfloor - (K+1)$ since $\alpha \le \alphadel$.
Thus,
\begin{align*}
\Pr(\mathrm{NoFalseDets} | \Gamma_{j-1,\ed} \cap \mathrm{Det0} \cap \subup) \\ \ge (1 - 10n^{-10})^{\lfloor \frac{t_{j+1} - t_j}{\alpha} \rfloor - (K)}
\end{align*}
On the other hand, if we condition on $\Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}} \cap \mathrm{Det1} \cap \subup$, then $\that_j = t_{j,*} + \alpha$. Thus,
\begin{align*}
\Pr(\mathrm{NoFalseDets} | \Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}} \cap \mathrm{Det1} \cap \subup) \\
\ge (1 - 10n^{-10})^{\lfloor \frac{t_{j+1} - t_j}{\alpha} \rfloor - (K+1)}
\end{align*}
We can now combine the above facts to bound $\Pr(\Gamma_{j,\ed}|\Gamma_{j-1,\ed})$. Recall that $p_0:= \Pr(\mathrm{Det0}|\Gamma_{j-1,\ed})$.
Clearly, the events $(\mathrm{Det0} \cap \subup \cap \mathrm{NoFalseDets})$ and $(\overline{\mathrm{Det0}} \cap \mathrm{Det1} \cap \subup \cap \mathrm{NoFalseDets})$ are disjoint. Thus,
\begin{align*}
& \Pr(\Gamma_{j,\ed}|\Gamma_{j-1,\ed}) \\
& = p_0 \Pr(\subup \cap \mathrm{NoFalseDets} |\Gamma_{j-1,\ed} \cap \mathrm{Det0})  \\
& + (1-p_0) \Pr(\mathrm{Det1}|\Gamma_{j-1,\ed} \cap \overline{\mathrm{Det0}}) \cdot \\
& \Pr(\subup \cap \mathrm{NoFalseDets} |\Gamma_{j-1,\ed}\cap \overline{\mathrm{Det0}} \cap \mathrm{Det1}) \\
& \ge p_0 ( 1 - 10n^{-10})^{K} (1 - 10n^{-10})^{\lfloor \frac{t_{j+1} - t_j}{\alpha} \rfloor - (K)} \\
& + (1-p_0) ( 1 - 10n^{-10}) \cdot \\& ( 1 - 10n^{-10})^{K}  (1 - 10n^{-10})^{\lfloor \frac{t_{j+1} - t_j }{\alpha} \rfloor - (K+1)}  \\

& =  ( 1 - 10n^{-10})^{\lfloor \frac{t_{j+1} - t_j}{\alpha} \rfloor}
\ge ( 1 - 10n^{-10})^{t_{j+1}-t_j}.
\end{align*}

Thus, since the events $\Gamma_{j,\ed}$ are nested,
$
\Pr(\Gamma_{J,\ed}|\Gamma_{0,\ed}) = \prod_j \Pr(\Gamma_{j,\ed}|\Gamma_{j-1,\ed}) \ge \prod_j ( 1 - 10n^{-10})^{t_{j+1}-t_j} = ( 1 - 10n^{-10})^d
\ge  1 - 10d n^{-10}.
$
\end{proof}

\begin{proof}[Proof of  Corollary \ref{cor:thm1}]

It should be noted that $basis(\M)$ is not a unique matrix, it refers to any matrix $\P$ that has orthonormal columns and whose span equals the span of $\M$. Thus $basis([\Phat_{j-1},\Phat_j]) \equiv basis( [ \Phat_{j-1}, \Phat_{j-1,\perp} \Phat_j]) \equiv basis( [ \Phat_{j}, \Phat_{j,\perp} \Phat_{j-1}])$. Let us denote any of these matrices by $\Phat_{j-1,j}$.

For $t \in [\that_{j-1} + K\alpha, t_{j})$,  $\Pt = \P_{j-1}$ while for $t \in [t_j, \that_j + K\alpha -1 )$, $\Pt = \P_j$. For all $t$ in these two intervals $\Phat_{(t)} = \Phat_{j-1,j}$.
The proof of this corollary is an easy consequence of this fact and the fact that, for two basis matrices $\P_1, \P_2$ that are mutually orthonormal, i.e., for which $\P_1{}' \P_2 = 0$,
\[
(\I - \P_1 \P_1' - \P_2 \P_2') = (\I - \P_1\P_1') (\I - \P_2\P_2').
\]
Thus, $\SE(\Phat_{j-1,j}, \P_{j-1}) \le \SE(\Phat_{j-1}, \P_{j-1}) \le \zz$ and $\SE(\Phat_{j-1,j}, \P_j) \le \SE(\Phat_j, \P_j) \le \zz$.
\end{proof}

\section{Proofs for Section \ref{sec:norst}: Time complexity derivation and Proof of Theorem \ref{thm1_newnorst}}\label{sec:proof}

\subsection{Time complexity derivation} \label{timecomp_derive}
Consider initialization.
To ensure that $\SE(\Phat_0, \P_0) \in O(1/\sqrt{r})$, we need to use $C \log r$ iterations of AltProj. Since there is no lower bound in the AltProj guarantee on the required number of matrix columns (except the trivial lower bound of rank) \cite{robpca_nonconvex}, we can use $t_\train = C r$ frames for initialization. Thus the initialization complexity is $O(n t_\train r^2 \log(\sqrt{r}) = O(n r^3 \log r)$ \cite{robpca_nonconvex}. The projected-CS step complexity is equal to the cost of a matrix vector multiplication with the measurement matrix times negative logarithm of the desired accuracy in solving the $l_1$ minimization problem. Since the measurement matrix for the CS step is $\I - \Phat_{(t-1)} \Phat_{(t-1)}{}'$, the cost per CS step (per frame) is $O(nr\log(1/\epsilon))$ \cite{l1_best} and so the total cost is $O((d-t_\train) nr\log(1/\epsilon))$.
 The subspace update involves at most $((d - t_\train)/ \alpha)$ rank $r$-SVD's on $n\times \alpha$ matrices all of which have constant eigen-gap (this is indirectly proved in the proofs of the second item of Lemmas \ref{lem:reprocspcalemone} and \ref{lem:reprocspcalemk}). Thus the total time for subspace update steps is at most $((d-t_\train)/\alpha)*O(n \alpha r \log(1/\epsilon)) = O((d-t_\train) n r \log(1/\epsilon))$ \cite{musco2015randomized}. Thus the running time of the complete algorithm is $O(ndr\log(1/\epsilon) + nr^3 \log r)$. As long as $r^2 \log r \le d \log(1/\epsilon)$, the time complexity of the entire algorithm is $O(n d r\log(1/\epsilon))$.

\subsection{Proof of Theorem \ref{thm1_newnorst} for NORST-NoDet}
In this algorithm we do not detect change. We just keep updating the subspace by $r$-SVD applied every $\alpha$ time instants on the last $\alpha$ $\lhat_t$'s, $\Lhat_{t;\alpha}$. For $\alpha$-intervals $\J$ for which $\Pt = \P_j$ for all $t \in \J$, there is no change to the analysis.

We start at $t = t_0 = \that_0 = 1$ with initial subspace estimate $\Phat_0$ available. Let $\Delta_0 = \SE(\Phat_0, \P_0)$.
The first subspace update is done at $t = \alpha$, the second at $t=2\alpha$, and so on. By Lemma \ref{lem:reprocspcalemone} with $\Phat_{j,0} =\Phat_0$, we can show that after one update, the error reduces to $ 1.2 \max(\Delta_0/4, \zz )$. After this, by applying Lemma \ref{lem:reprocspcalemk} $K-1$ times, we can show that, after at most $K$ steps with $K = \log (\Delta_0/\zz)$, the error reduces to $1.2 \zz$.  Beyond this time, the error does not decrease further.
We know that $\Pt = \P_0$ for $t \in [t_0, (K+2)\alpha]$, but can change after that.

Consider the $\alpha$-interval  $\J$ that contains the change time $t_1$.  The projected CS analysis for this interval remains exactly the same as above. But to analyze the subspace update for this interval we need to  use Corollary \ref{pca_ssch}. More generally consider the $j$-th change, and the interval $\J = [\lfloor t_j/\alpha \rfloor+1, \lfloor t_j/\alpha\rfloor + \alpha]$, which is the $\alpha$-frame interval that contains $t_j$.

For $t \in \J$, we have $\lhat_t = \yt - \xhat_t = \lt +\et + \vt$ where
\begin{align*}
\et &= \bm{I}_{\Tt}\left(\bpsi_{\Tt}{}'\bpsi_{\Tt}\right)^{-1} \I_{\Tt}{}' \bpsi(\lt + \vt):= (\e_{\l})_t + (\e_{\v})_t

\end{align*}
$\bpsi = \I - \Phat_{j-1}\Phat_{j-1}{}'$,  $\lt = \P_{j-1} \at $ for $t \in [\lfloor t_j/\alpha\rfloor, t_j)$ and $\lt = \P_{j} \at $ for $t \in [t_j, \lfloor t_j/\alpha \rfloor +\alpha)$.

Let $\Phat_{j,0}$ denote the subspace estimate $\Phat_{(t)}$ computed for this interval.
We apply Corollary \ref{pca_ssch} with $\yt \equiv \lhat_t$, $\wt \equiv (\e_{\l})_t$, $\vp_t \equiv (\e_{\v})_t + \vt$, $\lt \equiv \lt$, $\M_{1,t} = -\left( \bpsi_{\T_t}{}' \bpsi_{\T_t}\right)^{-1} \bpsi_{\T_t}{}'$, $\Phat = \Phat_{j,0}$, $\P = \P_j$, $\P_0 = \P_{j-1}$.
Since
$\norm{\M_{1, t} \P_0} = \| \left( \bpsi_{\T_t}{}' \bpsi_{\T_t}\right)^{-1} \bpsi_{\T_t}{}' \P_j\| \leq 1.2 \zz $, $\norm{\M_{1, t} \P} = \| \left( \bpsi_{\T_t}{}' \bpsi_{\T_t}\right)^{-1} \bpsi_{\T_t}{}' \P_j\| \leq 1.2 (\zz + \SE(\P_{j-1}, \P_j))$, thus $q_{00} = 1.2 (\zz + \SE(\P_{j-1}, \P_j))$.

Also, $\bz \equiv b_0= 0.01/f^2$ which is the upper bound on $\outfracrow(\alpha)$, $\|\E[(\e_{\v})_t (\e_{\v})_t{}']\| \leq (1.2)^2 \lambda_v^+$.

Thus, with probability at least $1 - 10n^{-10}$,
\begin{align*}
\SE(\Phat_{j,0},\P_j) \le 2.5 (3 (\Delta f + 4 \cdot 0.1  \cdot 1.2 (\zz + \Delta) + \frac{\lambda_{v}^+ }{ \lambda^-} ) \le 10 \Delta
\end{align*}
Here we used $\frac{\lambda_{v}^+ }{ \lambda^-} = \zz^2 < \Delta$.

Redefine $\that_j = \lfloor t_j/\alpha \rfloor + \alpha$ and $\Phat_{j,0}$ to denote the estimate from the change interval.
To analyze the next $\alpha$-interval for new-NORST, we apply Lemma \ref{lem:reprocspcalemone} with above re-definitions. Thus, $q_0 = 1.2 \cdot 10 \Delta$. We can conclude that $\SE(\Phat_{j,1}, \P_j) \le \max(0.3 q_0,\zz) = q_1$. For the next $K-1$ intervals, we apply  Lemma \ref{lem:reprocspcalemk} $K-1$ times with $q_{k} =1.2 \max(0.25 q_{k-1},\zz)$.

config: arxiv


TITLE: Mean and variance of distance to a point on a circle
QUESTION [1 upvotes]: If $P$ is a random point on the circle $x^2+y^2=1$, what are the mean and variance $P$'s distance to $(0,1)$?
The random variable has the function
$$X=\sqrt{-2x+2}$$
can't quite figure out what to do next...

REPLY [1 votes]: Since we are supposed to choose a random point on the circle, I think it is best to write our circle as $(\cos(t),\sin(t))$ in order that we go through each point at the same speed ($1$), and thus count them equally. Then we can write our definitions of mean and variance as follows (I only go from $t=0$ to $t=\pi$ because of symmetry.
$$E(X) = \frac{\int_0^\pi \sqrt{(1-\cos(t))^2+\sin^2(t)}dt}{\pi}$$
$$E(X^2) = \frac{\int_0^\pi (1-\cos(t))^2+\sin^2(t)dt}{\pi}$$
$$\mu(X) = E(X^2)-E(X)^2$$
Now it's just evaluating integrals. If you need more help, just ask!


TITLE: Difference between local, global and maximum solutions of a differential equation?
QUESTION [3 upvotes]: Unfortunately I can't find a good answer in 3 different books I have, and I dont get the difference, nor could I find any explanation online for this. Can someone be so kind to explain it to me or point me to the right direction?
Thank you!

REPLY [6 votes]: A local solution is a solution defined on a neighborhhod of a point. The standard existence and uniqueness result proves the existence of a unique local solution (under certain conditions on the equation.)
A global solution is a solution defined on $(-\infty,\infty)$. $y(x)=e^x$ is a global solution of $y'=y$.
There are two different uses for the word maximal (which I suppose you meant instead of maximum.) I assume that you are refering to the fact that the solution is defined on a maximal interval, that is, $y\colon(a,b)\to\mathbb{R}$ is a solution that cannot be extended to any interval $(c,d)$ with $(a,b)\subset(c,d)$. $y=\tan x$ is a maximal solution of $y'=1+y^2$ on $(-\pi/2,\pi/2)$.


text:
\begin{document}

\begin{abstract}
A semigroup is \emph{regular} if it contains at least one idempotent in each $\mathcal{R}$-class and in each $\mathcal{L}$-class. A regular semigroup is \emph{inverse} if it satisfies either of
the following equivalent conditions: (i) there is a unique idempotent in each $\mathcal{R}$-class and in each $\mathcal{L}$-class, or (ii) the idempotents commute.

Analogously, a semigroup is \emph{abundant} if it contains at least one idempotent in each $\mathcal{R}^*$-class and in each $\mathcal{L}^*$-class. An abundant semigroup is \emph{adequate} if its idempotents commute. In adequate semigroups, there is a unique idempotent in each $\mathcal{R}^*$ and $\mathcal{L}^*$-class. M. Kambites raised the question of the converse: in a finite abundant semigroup such that there is a unique idempotent in each $\mathcal{R}^*$ and $\mathcal{L}^*$-class, must the idempotents commute? In this note we provide a negative answer to this question.
\end{abstract}

\maketitle

\section{Introduction}

For a set $X$, denote by $T(X)$ the monoid of all total transformations of $X$ to itself.
For $t\in T(X)$, let $\Im(t)= \{ xt \mid x\in X\}$ and $\Ker(t)=\{(x,y) \mid xt=yt\}$
denote, respectively, the image of $X$ under $t$ and the kernel of $t$.

Let $S$ be a semigroup. We denote the right regular representation and
the left regular antirepresentation of $S$ by
$\rho:S\rightarrow T(S^1) ; s \mapsto \rho_s$ and $\lambda: S\rightarrow T(S^1) ; s \mapsto \lambda_s$,
respectively, where $(x)\rho_s = xs$ and $\lambda_s(x) = sx$ for all $x\in S^1$.

Now we can define the usual Green's equivalence relations on $S$ as follows:
for $s,t\in S$,
\[
s\mathcal{L}t \Leftrightarrow \Im (\rho_s)=\Im(\rho_t)
\qquad\text{and}\qquad
s\mathcal{R}t \Leftrightarrow \Im (\lambda_s)=\Im(\lambda_t)\,.
\]
Similarly we can define two more equivalence relations on $S$ as follows: for $s,t\in S$,
\[
s\mathcal{L}^* t \Leftrightarrow \Ker (\lambda_s)=\Ker(\lambda_t)
\qquad\text{and}\qquad
s\mathcal{R}^* t \Leftrightarrow \Ker (\rho_s)=\Ker(\rho_t)\,.
\]
More simply put, $s\mathcal{L}^* t$ if and only if, for all $x,y\in S^1$,
$sx=sy\Leftrightarrow tx=ty$, and similarly, $s\mathcal{R}^* t$ if and only if,
for all $x,y\in S^1$, $xs=ys\Leftrightarrow xt=yt$.
It is not difficult to show that $\mathcal{L}\subseteq \mathcal{L}^*$ and
$\mathcal{R}\subseteq \mathcal{R}^*$. In addition, it is well known that
$s\mathcal{L}^* t$ if and only if $s\mathcal{L} t$ in some semigroup containing $S$
as a subsemigroup, and a similar characterization holds for $\mathcal{R}^*$.

A semigroup is \emph{regular} if there is at least one idempotent in every
$\mathcal{L}$-class and in every $\mathcal{R}$-class. A semigroup is
\emph{abundant} if there is at least one idempotent in every
$\mathcal{L}^*$-class and in every $\mathcal{R}^*$-class \cite{fountain2}.

Within regular semigroups, the notion of \emph{inverse} semigroup is characterized
by either of the following equivalent properties: (i) the idempotents commute, or
(ii) there exists a unique idempotent
in every $\mathcal{L}$-class and in every $\mathcal{R}$-class.

A generalization of (i) is as follows: a semigroup is \emph{adequate} if it is
abundant and the idempotents commute \cite{fountain1}. Adequate semigroups satisfy the starred
analog of (ii), that is, in an adequate semigroup,
there exists a unique idempotent in every $\mathcal{L}^*$-class and
in every $\mathcal{R}^*$-class. Fountain constructed an infinite example of an abundant, nonadequate semigroup with unique idempotents in each $\mathcal{L}^*$-class and
in each $\mathcal{R}^*$-class (\cite{fountain1}, Example 1.4).

At the second meeting of the North British Semigroups and Applications Network
(16-17 April 2009) \cite{MK}, Mark Kambites asked a natural question:

\medskip

\noindent\emph{Let} $S$ \emph{be a finite abundant semigroup such that
there exists a unique idempotent in every} $\mathcal{L}^*$\emph{-class and
in every} $\mathcal{R}^*$\emph{-class. Do the idempotents of} $S$ \emph{commute?}

\medskip

We will say that a semigroup is \emph{amiable} if each $\mathcal{R}^*$-class and each $\mathcal{L}^*$-class
contains a unique idempotent. Every amiable semigroup is obviously abundant. Kambites'
question can be rephrased as: \emph{Is every finite amiable semigroup adequate?}

Kambites' question attracted the attention of a number of semigroup theorists
attending the NBSAN meeting. The aim of this note is to answer the question in the negative.

\section{The Smallest Example}

In this section we construct the smallest example of an amiable semigroup with a pair
of noncommuting idempotents, and show further that, up to isomorphism, it is the unique
such semigroup of its size.

A key observation used in the arguments that follow is that for idempotents $a,b$ in
a semigroup, $a \mathcal{L}^* b$ if and only if $a\mathcal{L} b$, and similarly for
$\mathcal{R}^*$ and $\mathcal{R}$.

\begin{lemma}
\label{lem:atleast4}
Let $S$ be an amiable semigroup and assume $a,b\in S$ are noncommuting idempotents.
Let $c = ab$ and $d = ba$. Then the elements $a,b,c,d$ are distinct. Further,
$ac = cb = c$, $bd = da = d$, $ad = ca = cd = aba \neq a,b$ and $bc = db = dc = bab \neq a,b$.
\end{lemma}

\begin{proof}
Suppose, for instance, $c = a$. Then $dd = baba = bca = ba = d$, that is, $d$ is an idempotent.
Since $da = d$ and $ad = a$, we have $a \mathcal{L} d$. Since $S$ is amiable,
$a = d$, which contradicts the assumption that $c\neq d$. Thus $c\neq a$,
and by a similar argument, $d\neq b$. Exchanging the roles of $a$ and $b$, we also have
$d\neq a$ and $c \neq b$. This establishes the first claim.

If $aba = a$, then $abab = ab$ so that $ab$ is an idempotent. Since $a(ab) = ab$ and
$(ab)a = a$, we have $ab\mathcal{R}a$. Since $S$ is amiable, $ab = a$,
a contradiction. If $aba = b$, then $ab = aaba = aba = b$, another contradiction.
That $bab \neq a,b$ follows from exchanging the roles of $a$ and $b$. The remaining
equalities are clear.
\end{proof}

It follows from Lemma \ref{lem:atleast4} that an amiable semigroup
which is not adequate must have order at least $4$. A partial multiplication table
looks like this:
\begin{table}[htb]
\[
\begin{tabular}{c|cccc}
    & $a$ & $b$ & $c$ & $d$ \\ \hline
  $a$ & $a$ & $c$ & $c$ & $e$ \\
  $b$ & $d$ & $b$ & $f$ & $d$ \\
  $c$ & $e$ & $c$ & $g$ & $e$ \\
  $d$ & $d$ & $f$ & $f$ & $h$
\end{tabular}
\]
\end{table}

\noindent where $e = ad = ca = cd$, $f = bc = db = dc$ and $g = cc = eb = af$ are not necessarily
distinct from $a,b,c,d$ or from each other.

\begin{lemma}
\label{lem:basic}
Let $S$ be an amiable semigroup and assume $a,b\in S$ are noncommuting idempotents.
Then $aba = ab$ if and only if $bab = ab$. When these conditions hold, $a$ and $b$
generate a subsemigroup of $S$ of order $4$.
\end{lemma}

\begin{proof}
Suppose first that $aba = ab$. Then $abab = ab$ and $(bab)(bab) = bab$, that is,
$ab$ and $bab$ are idempotents. Since $(ab)(bab) = ab$ and $(bab)(ab) = bab$, we have
$ab \mathcal{L} bab$. Since $S$ is amiable, $bab = ab$.

Conversely, if $bab = ab$, then again $ab$ is an idempotent and also
$(aba)(aba) = aba$, that is, $aba$ is an idempotent. Since $(aba)(ab) = ab$
and $(ab)(aba) = aba$, we have $ab \mathcal{R} aba$. Since $S$ is amiable, $aba = ab$.

Now assume the conditions $aba = bab = ab$ hold.
Set $c = ab$ and $d = ba$. By Lemma \ref{lem:atleast4} and the discussion that
follows, $ad = ca = cd = bc = db = dc = cc = c$, and so
$M = \{a,b,c,d\}$ is a subsemigroup of $S$ with multiplication table given in
Table 1.
\end{proof}

\begin{table}
\[
\begin{tabular}{c|cccc}
  $M$ & $a$ & $b$ & $c$ & $d$ \\ \hline
  $a$ & $a$ & $c$ & $c$ & $c$ \\
  $b$ & $d$ & $b$ & $c$ & $d$ \\
  $c$ & $c$ & $c$ & $c$ & $c$ \\
  $d$ & $d$ & $c$ & $c$ & $c$
\end{tabular}
\]
\caption{The smallest amiable semigroup which is not adequate.}
\end{table}

In Lemma \ref{lem:basic}, the magma $M$ of Table 1 is a semigroup because $M$ is closed
under the multiplication of the semigroup $S$. Now we show that $M$ is a semigroup in its
own right.

\begin{lemma}
\label{lem:referee}
The magma $M$ defined by Table 1 is a semigroup.
\end{lemma}

\begin{proof}
For $s\in M$, define $\tau_s : M\to M$ by
$(t)\tau_s = ts$ for all $t\in M$. We prove associativity by showing that $\tau_s \tau_t = \tau_{st}$ for all $s,t\in M$. Order the elements of $M$ by $a<b<c<d$. Then the mapping $\tau_s$ can be represented by the (transposed) column corresponding to $s$ in Table 1. Thus we write
\[
\tau_a = [\ a\ d\ c\ d\ ], \qquad \tau_b = [\ c\ b\ c\ c\ ], \qquad
\tau_c = [\ c\ c\ c\ c\ ], \qquad \tau_d = [\ c\ d\ c\ c\ ]\,.
\]
The entry of the transformation $\tau_s$ indexed by $t\in M$ is $(t)\tau_s$.
Since $c$ is a zero of $M$, we have $\tau_c \tau_s = \tau_c = \tau_{cs}$ and similarly
$\tau_s \tau_c = \tau_{sc}$ for all $s\in M$. We verify the other nine cases by direct calculation,
recalling that composition is from left to right:
\begin{alignat*}{3}
\tau_a \tau_a &= [\ a\ d\ c\ d\ ]\ [\ a\ d\ c\ d\ ] &&= [\ a\ d\ c\ d\ ] &&= \tau_a = \tau_{aa} \\
\tau_a \tau_b &= [\ a\ d\ c\ d\ ]\ [\ c\ b\ c\ c\ ] &&= [\ c\ c\ c\ c\ ] &&= \tau_c = \tau_{ab} \\
\tau_a \tau_d &= [\ a\ d\ c\ d\ ]\ [\ c\ d\ c\ c\ ] &&= [\ c\ c\ c\ c\ ] &&= \tau_c = \tau_{ad} \\
\tau_b \tau_a &= [\ c\ b\ c\ c\ ]\ [\ a\ d\ c\ d\ ] &&= [\ c\ d\ c\ c\ ] &&= \tau_d = \tau_{ba} \\
\tau_b \tau_b &= [\ c\ b\ c\ c\ ]\ [\ c\ b\ c\ c\ ] &&= [\ c\ b\ c\ c\ ] &&= \tau_b = \tau_{bb} \\
\tau_b \tau_d &= [\ c\ b\ c\ c\ ]\ [\ c\ d\ c\ c\ ] &&= [\ c\ d\ c\ c\ ] &&= \tau_d = \tau_{bd} \\
\tau_d \tau_a &= [\ c\ d\ c\ c\ ]\ [\ a\ d\ c\ d\ ] &&= [\ c\ d\ c\ c\ ] &&= \tau_d = \tau_{da} \\
\tau_d \tau_b &= [\ c\ d\ c\ c\ ]\ [\ c\ b\ c\ c\ ] &&= [\ c\ c\ c\ c\ ] &&= \tau_c = \tau_{db} \\
\tau_d \tau_d &= [\ c\ d\ c\ c\ ]\ [\ c\ d\ c\ c\ ] &&= [\ c\ c\ c\ c\ ] &&= \tau_c = \tau_{dd}\,. \tag*{\qedhere}
\end{alignat*}
\end{proof}

\begin{theorem}
\label{thm:order4}
Up to isomorphism, there is exactly one amiable semigroup of order $4$ which is not adequate.
\end{theorem}

\begin{proof}
By Lemma \ref{lem:referee}, $M$ is a semigroup. The $\mathcal{L}^*$-classes are
$\{a,d\}$, $\{b\}$ and $\{c\}$. The $\mathcal{R}^*$-classes are
$\{b,d\}$, $\{a\}$ and $\{c\}$. Hence $M$ is amiable, but not adequate since $ab = c\neq d=ba$.

Now let $S$ be an amiable semigroup of order $4$ and assume that $a,b\in S$
are noncommuting idempotents. Set $c = ab$ and $d = ba$.
By Lemma \ref{lem:atleast4}, $S = \{a,b,c,d\}$ and $aba \neq a,b$.
Thus $aba = c$ or $aba = d$. The desired isomorphism of $S$ with $M$ then follows from
Lemma \ref{lem:basic}, directly for the case $aba=c$, and with the roles of
$a$ and $b$ reversed for the case $aba=d$.
\end{proof}

\section{Larger Examples}

A computer search for amiable semigroups which are not adequate revealed that up to order $37$,
every such semigroup contains a copy of the order $4$ example $M$. Thus we offer the following.

\begin{conjecture}
Let $S$ be a finite amiable semigroup which is not adequate. Then $S$ contains a subsemigroup isomorphic to $M$.
\end{conjecture}

As some corroborating evidence for the conjecture, we now prove a special case.

\begin{proposition}
\label{prp:order5}
Let $S$ be an amiable semigroup of order $5$ which is not adequate. Then $S$ contains a subsemigroup
isomorphic to $M$.
\end{proposition}

\begin{proof}
Assume $S = \{a,b,c,d,e\}$ where $a$ and $b$ are noncommuting idempotents, $ab =c$ and $ba = d$.
(Here we use Lemma \ref{lem:atleast4} once again to guarantee that $a,b,c,d$ are distinct.)
Suppose that $S$ does not contain a copy of $M$. By Lemmas \ref{lem:atleast4} and \ref{lem:basic},
$aba \neq a,b,c,d$, and so $aba = e$. By the same argument with the roles of $a$ and $b$ reversed,
$bab = e$. Then $ae = ea = e$, $be = eb = e$, $ce = ed = ababa = aea = e$,
$de = ec = babab = beb = e$ and $ee = ababa = e$. Thus we have the multiplication table given in Table 2.
\begin{table}[htb]
\[
\begin{tabular}{c|ccccc}
   & $a$ & $b$ & $c$ & $d$ & $e$  \\ \hline
  $a$ & $a$ & $c$ & $c$ & $e$ & $e$ \\
  $b$ & $d$ & $b$ & $e$ & $d$ & $e$ \\
  $c$ & $e$ & $c$ & $e$ & $e$ & $e$ \\
  $d$ & $d$ & $e$ & $e$ & $e$ & $e$ \\
  $e$ & $e$ & $e$ & $e$ & $e$ & $e$
\end{tabular}
\]
\caption{}
\end{table}
However, we see immediately by inspection of the table that $d$ does not have any
idempotent in its $\mathcal{L}^*$-class. This contradicts the abundance of $S$.
\end{proof}

Note that there do exist amiable semigroups with noncommuting idempotents which themselves do not
generate a copy of $M$. The smallest order where this occurs is $8$. Table 3 gives an example.

\begin{table}[htb]
\[
\begin{tabular}{c|cccccccc}
    & $a$ & $b$ & $c$ & $d$ & $e$ & $f$ & $g$ & $h$ \\ \hline
  $a$ & $a$ & $c$ & $c$ & $c$ & $f$ & $f$ & $c$ & $f$ \\
  $b$ & $d$ & $b$ & $c$ & $d$ & $b$ & $g$ & $g$ & $c$ \\
  $c$ & $c$ & $c$ & $c$ & $c$ & $c$ & $c$ & $c$ & $c$ \\
  $d$ & $d$ & $c$ & $c$ & $c$ & $g$ & $g$ & $c$ & $g$ \\
  $e$ & $d$ & $b$ & $c$ & $d$ & $e$ & $g$ & $g$ & $h$ \\
  $f$ & $c$ & $c$ & $c$ & $c$ & $f$ & $c$ & $c$ & $f$ \\
  $g$ & $c$ & $c$ & $c$ & $c$ & $g$ & $c$ & $c$ & $g$ \\
  $h$ & $c$ & $c$ & $c$ & $c$ & $h$ & $c$ & $c$ & $h$
\end{tabular}
\]
\caption{}
\end{table}

\noindent Here $a$ and $e$ are noncommuting idempotents with $aea \neq ae, ea$ and
$eae \neq ae, ea$.
Note that this semigroup contains two copies of $M$, namely $\{a,b,c,d\}$ and
$\{h,a,c,f\}$. Indeed, every example known
to us contains \emph{some} pair of noncommuting idempotents which generates a copy of $M$.

\section{Idempotent and Pseudozero Inflations}

In this section, we will discuss constructions of new amiable semigroups
from existing ones by adjoining a single element. Of course, two obvious ways
of doing this are by adjoining an identity element or by adjoining a zero.
Here we discuss two other constructions.

Let $S$ be a semigroup and $e^2=e\in S$. The \emph{idempotent inflation of} $S$ \emph{induced by} $e$ is a magma $(U,\circ)$ such that $U=S\cup \{\epsilon\}$ (where $\epsilon$ is a symbol not in $S$), and for $x,y \in U$,
\[
x\circ y=\begin{cases}
     xy, & \text{if}\ x,y\in S \\
     ey, & \text{if}\ x=\epsilon, y\in S \\
     xe, & \text{if}\ x\in S, y=\epsilon \\
     \epsilon, & \text{if}\ x=y=\epsilon\,.
\end{cases}
\]
The idempotent inflation of $S$ induced by $e^2=e\in S$ will be denoted by $S[e]$.

\begin{lemma}
For a semigroup $S$ with idempotent $e\in S$, the idempotent inflation $S[e]$ is a semigroup.
\end{lemma}

\begin{proof}
We show that for $x,y,z\in S$, $x\circ (y\circ z)=(x\circ y)\circ z$.
For $x,y\in S$ and $z=\epsilon$,
$(x\circ y)\circ \epsilon = (xy)e = x(ye) = x\circ (y\circ \epsilon)$.
Similarly, $(x\circ \epsilon)\circ y = x\circ (\epsilon\circ y)$ and
$\epsilon\circ (y\circ z) = (\epsilon\circ y)\circ z$. Finally, for $x\in S$,
$x\circ (\epsilon \circ \epsilon) = x\circ \epsilon = xe = (xe)e
= (xe)\circ \epsilon = (x\circ \epsilon)\circ \epsilon$.
Similarly, $(\epsilon \circ x)\circ \epsilon = \epsilon\circ (x\circ \epsilon)$
and $(\epsilon \circ \epsilon)\circ x = \epsilon\circ (\epsilon \circ x)$.
\end{proof}

Note that $S[e]$ is an inflation of $S$ in the usual sense (see \cite[ex.10, p.98]{clifford}) because the map $\phi: S[e] \to S$
given by $x\phi = x$ for $x\in S$ and $\epsilon\phi = e$ is an idempotent homomorphism onto $S$.

For a semigroup $S$ with idempotent $e\in S$ and idempotent inflation $U = S[e]$,
we will write $\mathcal{R}_S^*$ and $\mathcal{R}_U^*$ for the $\mathcal{R}^*$
relations in $S$ and $U$, respectively, and similarly for the $\mathcal{L}^*$ relations.

\begin{lemma}
\label{lem:stars}
Let $S$ be a semigroup with idempotent $e\in S$ and let $U = S[e]$ be the idempotent
inflation of $S$ induced by $e$. Then
(i) the $\mathcal{R}_U^*$-classes are $\{\epsilon\}$ and the $\mathcal{R}_S^*$-classes, and
(ii) the $\mathcal{L}_U^*$-classes are $\{\epsilon\}$ and the $\mathcal{L}_S^*$-classes.
\end{lemma}

\begin{proof}
Firstly suppose $s\mathcal{R}_U^* \epsilon$
for some $s\in S$. Since $1\circ \epsilon = \epsilon = \epsilon\circ \epsilon$, we have
$1\circ s = \epsilon\circ s = es = e\circ s$. But then
$1\circ \epsilon = e\circ \epsilon$, that is, $\epsilon = e$, which is a contradiction.
Therefore the $\mathcal{R}_U^*$-class of $\epsilon$ is $\{\epsilon\}$. The remaining
$\mathcal{R}_U^*$-classes are contained in $S$.

Next, if $s\mathcal{R}_U^* t$ for $s,t\in S$, then $s\mathcal{R}_T t$ for some
oversemigroup $T$ of $U$. Since $T$ is also an oversemigroup of $S$, $s\mathcal{R}_S^* t$.
Thus each $\mathcal{R}_U^*$-class is contained in an
$\mathcal{R}_S^*$-class. What remains is to show the reverse inclusion. Thus suppose
$s\mathcal{R}_S^* t$
for some $s,t\in S$. For $x\in S^1$, $\epsilon\circ s = x\circ s$ if and only if $es = xs$
if and only if $et = xt$ if and only if $\epsilon\circ t = x\circ t$. Therefore, for
all $x,y\in U^1$, $x\circ s=y\circ s\Leftrightarrow x\circ t=y\circ t$. This shows
$s\mathcal{R}_U^* t$ as desired.

The corresponding results for the $\mathcal{L}^*$ relations follow by symmetry.
\end{proof}

Immediately from Lemma \ref{lem:stars}, we have the following.

\begin{theorem}
\label{thm:inflation-preserve}
Let $S$ be a semigroup, and let $e\in S$ be an idempotent.
Then $S$ is abundant, amiable or adequate if and only if $S[e]$ has the same corresponding property.
\end{theorem}

Let $S$ be a semigroup with a zero $0\in S$. The \emph{pseudozero inflation} of $S$
is a magma $(U,\circ)$ where $U = S\cup \{\bar{0}\}$ (where $\bar{0}$ is a symbol
not in $S$) and for $x,y\in U$,
\[
x\circ y=\begin{cases}
     xy, & \text{if}\ x,y\in S \\
     \bar{0}, & \text{if}\ x=\bar{0}, y\in S\ \text{or}\ x\in S, y=\bar{0} \\
     0, & \text{if}\ x=y=\bar{0}\,.
\end{cases}
\]
The pseudozero inflation of $S$, where $0\in S$ is a zero, will be denoted by $S^{\bar{0}}$.

\begin{lemma}
For a semigroup $S$ with zero $0\in S$, the pseudozero inflation $S^{\bar{0}}$ is a semigroup.
\end{lemma}

\begin{proof}
We show that for $x,y,z\in S$, $x\circ (y\circ z)=(x\circ y)\circ z$.
For $x,y\in S$ and $z=\bar{0}$,
$(x\circ y)\circ \bar{0} = \bar{0} = x\circ (y\circ \bar{0})$.
Similarly, $(x\circ \bar{0})\circ y = x\circ (\bar{0}\circ y)$ and
$\bar{0}\circ (y\circ z) = (\bar{0}\circ y)\circ z$. For $x\in S$,
$x\circ (\bar{0} \circ \bar{0}) = x\circ 0 = 0 =
\bar{0}\circ \bar{0} = (x\circ \bar{0})\circ \bar{0}$. Similarly,
$(\bar{0} \circ \bar{0})\circ x = \bar{0}\circ (\bar{0} \circ x)$ and
 $(\bar{0} \circ x)\circ \bar{0} = \bar{0}\circ (x\circ \bar{0})$.
\end{proof}

As in the idempotent case,
$S^{\bar{0}}$ is an inflation of $S$ in the usual sense because the map
$\phi: S^{\bar{0}} \to S$
given by $x\phi = x$ for $x\in S$ and $\bar{0}\phi = 0$ is an idempotent
homomorphism onto $S$.

For a semigroup $S$ with zero $0\in S$ and pseudozero inflation $U = S^{\bar{0}}$,
we will again write $\mathcal{L}_S^*$ and $\mathcal{L}_U^*$ for the $\mathcal{L}^*$
relations in $S$ and $U$, respectively, and similarly for the $\mathcal{R}^*$ relations.

\begin{lemma}
\label{lem:pseudo-stars}
Let $S$ be a semigroup with zero $0\in S$ and let $U = S^{\bar{0}}$ be the pseudozero
inflation of $S$. Then
(i) the $\mathcal{R}_U^*$-classes are $\{0,\bar{0}\}$ and the $\mathcal{R}_S^*$-classes contained in $S\backslash \{0\}$, and
(ii) the $\mathcal{L}_U^*$-classes are $\{0,\bar{0}\}$ and the $\mathcal{L}_S^*$-classes contained in $S\backslash \{0\}$.
\end{lemma}

\begin{proof}

We have $x\circ\bar{0} = y\circ\bar{0}$ if and only if either $x, y\in S^1$ or $x=y=\bar{0}$.
For $s\in S$, we have $x\circ s = y\circ s$ for all $x,y\in S^1$ if and only if $s = 0$.
It follows that $\{0,\bar{0}\}$ is an $\mathcal{R}_U^*$-class, and so the remaining
$\mathcal{R}_U^*$-classes are contained in $S\backslash \{0\}$.

As in the proof of Lemma \ref{lem:stars}, if $s\mathcal{R}_U^* t$ for some $s,t\in S\backslash \{0\}$,
then $s\mathcal{R}_S^* t$ since any oversemigroup of $U$ is an oversemigroup of $S$.
Conversely, suppose $s\mathcal{R}_S^* t$ for $s,t\in S$. If for $x,y\in U^1$, we have
$x\circ s = y\circ s$, then either $x,y\in S^1$ or $x=y=\bar{0}$. In either case,
$x\circ t = y\circ t$. Similarly, $x\circ t = y\circ t$ implies $x\circ s = y\circ s$
for all $x,y\in U^1$. Therefore $s\mathcal{R}_U^* t$.

The corresponding results for the $\mathcal{L}^*$ relations follow by symmetry.
\end{proof}

\begin{theorem}
\label{thm:pseudozero-preserve}
Let $S$ be a semigroup with zero $0\in S$.
Then $S$ is abundant, amiable or adequate if and only if $S^{\bar{0}}$ has the same corresponding property.
\end{theorem}

If an amiable semigroup is not adequate, then neither its pseudozero inflation
nor any of its idempotent inflations will be adequate, and so we have two ways
of generating new amiable semigroups which are not adequate from existing ones.
But these one point inflations certainly do not tell the whole story, even for
small orders. We verified the following result computationally.

\begin{theorem}
\label{thm:order5}
The following seven semigroups are the unique (up to isomorphism) amiable
semigroups of order $5$ which are not adequate:
(i) $M^1$ ($M$ with an identity element adjoined),
(ii) $M^0$ ($M$ with a zero adjoined),
(iii) $M^{\bar{c}}$ (the pseudozero inflation of $M$),
(iv) $M[a]$, $M[b]$, $M[c]$ (the three idempotent inflations of $M$) and
(v) the semigroup given by the following table:
\begin{table}[htb]
\[
\begin{tabular}{c|ccccc}
      & a & b & c & d & e\\
\hline
    a & a & c & c & c & c \\
    b & d & b & c & d & e \\
    c & c & c & c & c & c \\
    d & d & c & c & c & c \\
    e & e & c & c & c & c\\
\end{tabular}
\]
\end{table}
\end{theorem}

\section{Problems}

Besides our main conjecture in {\S}3, we also suggest the following.

For each $x$ in an amiable semigroup, there is a unique idempotent $x_{\ell}$ in the $\mathcal{L}^*$-class of $x$
and a unique idempotent $x_r$ in the $\mathcal{R}^*$-class of $x$. One can view such semigroups as algebras of type
$\langle 2,1,1\rangle$ where the binary operation is the semigroup multiplication and the unary operations are
$x\mapsto x_{\ell}$ and $x\mapsto x_r$. Such algebras form a quasivariety axiomatized by, for instance, the
eight quasi-identities

\begin{center}
\begin{tabular}{ccc}
$x_{\ell} x_{\ell} = x_{\ell}$ & \qquad & $x_r x_r = x_r$ \\
$x x_{\ell} = x$ & & $x_r x = x$ \\
$xy = xz \Rightarrow x_{\ell}y = y_{\ell}z$ & & $yx = zx \Rightarrow yx_r = zx_r$
\end{tabular}

\begin{tabular}{c}
$(\ xx = x\ \&\ yy = y\ \&\ xy = x\ \&\ yx = y\ ) \Rightarrow x = y$ \\
$(\ xx = x\ \&\ yy = y\ \&\ xy = y\ \&\ yx = x\ ) \Rightarrow x = y$.
\end{tabular}
\end{center}

\noindent Fountain's infinite example \cite{fountain1} and our finite examples show that the quasivariety of amiable semigroups properly contains the quasivariety of adequate semigroups.
Kambites determined the free objects in the latter quasivariety \cite{MK2}, and thus the
following is quite natural.

\begin{problem}
Determine the free objects in the quasivariety of amiable semigroups.
\end{problem}

As we saw in Theorem \ref{thm:order5}, there are amiable semigroups with noncommuting idempotents which are not given by idempotent or pseudozero inflations or by
adjoining an identity element or zero element to a given amiable semigroup. Consider, for the moment, constructions such as direct products and amiable subsemigroups to be ``trivial''.

\begin{problem}
Find other nontrivial ways of building new amiable semigroups from existing ones.
\end{problem}

\begin{acknowledgment}
We are pleased to acknowledge the assistance of
the finite model builder \textsc{Mace4} and the automated deduction tool \textsc{Prover9},
both developed by
McCune \cite{McCune}. We initially found small examples using
\textsc{Mace4} and then reverse engineered them into the examples
presented here. \textsc{Prover9} was helpful in working out the proofs in {\S}2.

The first author was partially supported by FCT and FEDER,
Project POCTI-ISFL-1-143 of Centro de Algebra da Universidade de Lisboa,
and by FCT and PIDDAC through the project PTDC/MAT/69514/2006.
\end{acknowledgment}


text:
\section{Fresnel Cosine Integral Function of Zero}
Tags: Fresnel Cosine Integral Function

\begin{theorem}
:$\map {\operatorname C} 0 = 0$
\end{theorem}

\begin{proof}
By [[Fresnel Cosine Integral Function is Odd]], $\operatorname C$ is an [[Definition:Odd Function|odd function]].
Therefore, by [[Odd Function of Zero is Zero]]:
:$\map {\operatorname C} 0 = 0$
{{qed}}
\end{proof}

config: wiki


TITLE: Probability distribution estimation
QUESTION [0 upvotes]: The joint frequency distribution of two discrete random variables $X$ and $Y$ is given in the table below:

$y$

1
2
3
4

1
0.10
0.05
0.02
0.02

$x$
2
0.05
0.20
0.05
0.02

3
0.02
0.05
0.20
0.04

4
0.02
0.02
0.04
0.10

Using $\text{Var}(X)=\sum [x_i−\mathbb E(X)]^2 \cdot \mathbb P(X=x_i)$, we can define the conditional variance of $X$ for a given value of $Y$: $\text{Var}(X|Y=y)$. For example: $\text{Var}(X|Y=1)=\sum[x_i−\mathbb E(X|Y=1)]^2⋅\mathbb P(X=x_i|Y=1)$. Find $\text{Var}(X|Y=1)$.
In order to solve this I estimated this tables below
|       | y     |   |   |   |   |   |
|-  |:-:    |-  |-  |-  |-  |-  |
| x     |       | 1     | 2     | 3     | 4     |   |
|   | 1     | 0.10  | 0.05  | 0.02  | 0.02  | 0.19  |
|   | 2     | 0.05  | 0.20  | 0.05  | 0.02  | 0.32  |
|   | 3     | 0.02  | 0.05  | 0.20  | 0.04  | 0.31  |
|   | 4     | 0.02  | 0.02  | 0.04  | 0.10  | 0.18  |
|   |   | 0.19  | 0.32  | 0.31  | 0.18  |   |

1
2
3
4

X | Y = 1
0.53
0.26
0.11
0.11

X | Y = 2
0.16
0.63
0.16
0.06

X | Y = 3
0.06
0.16
0.65
0.13

X | Y = 4
0.11
0.11
0.22
0.56

W   = E(X | Y = y)

1.79
2.13
2.84
3.22

So next should be estimation of of E(W). In last table I estimated half of this but I can't find how to estimate other half with values 0.19, 0.32, 0.31, 0.18 So can anybody help me how to find this ?

REPLY [0 votes]: Are you trying to calculate $\mathrm{Var}(X|Y=1)$? To calculate that, you can use the table (with rows $X | Y = y$ for $y = 1, 2, 3, 4$) you have computed. Since we are interested in the distribution of $X$ conditional on $Y = 1$, you would be interested in the first row. Indeed, you can then simply imagine those four entries as defining your desired distribution, and you can then use the usual formulas to calculate the expected value (e.g. $\mathbb{E}[X|Y=1] = 0.53(1) + 0.26(2) + 0.11(3) + 0.11(4) = 1.82$), and the variance (i.e. using the first formula you wrote).


TITLE: Mandelbrot set incorrect picture
QUESTION [0 upvotes]: I'm writing an algorithm to generate the Mandelbrot set in Java. However, the final picture is incorrect. It looks like this

I was wondering if the algorithm was incorrect.
public void Mandlebrot() {
    float reMax=2;
    float imMax=2;
    float reMin=-2;
    float imMin=-2;
    float xDelta = (reMax - reMin)/test.width;
    float yDelta = (imMax - imMin)/test.height;

    int N=20000;
    float complex = imMin;
    for(int y=0; y<test.height; y++) {
        float real = reMin;
        for(int x=0; x<test.width; x++) {
            int count = 0;
            float complexC = 0.4f;
            float realC = 0.3f;

            while(count<N && complexC*complexC+realC*realC<=4.0f) {
                complexC = realC*realC-complexC*complexC + complex;
                realC = 2*complexC*realC + real;
                count++;
            }

            if(complexC*complexC+realC*realC<=4.0f) {
                setPixel(x,y) = 1000;
            } else {
                setPixel(x,y) = 1+ 1000*count/N;
            }

            real+=xDelta;
        }
        complex+=yDelta;
    }
}

REPLY [4 votes]: In the loop
while(count<N && complexC*complexC+realC*realC<=4.0f) {
    complexC = realC*realC-complexC*complexC + complex;
    realC = 2*complexC*realC + real;
    count++;
}

You use the updated complexC to compute the new realC, but you ought to use the old one:
float oldC = complexC;
complexC = realC*realC-complexC*complexC + complex;
realC = 2*oldC*realC + real;
count++;

Besides, you seem to have flipped the real and imaginary parts. I think that only rotates the picture, though.


TITLE: If $A$ is paranormal then $A$ is normal in dimension finite
QUESTION [1 upvotes]: Let $A\in\mathcal L(V),\dim V\lt+\infty$.
We know that if $A$ normal then $A$ is paranormal. I need help to prove the following:
If $A$ is paranormal then $A$ is normal in finite-dimension.
Thank you in advance!

REPLY [1 votes]: We may prove the statement by mathematical induction on $\dim V$. The base case $\dim V=1$ is trivial, because every linear operator is normal. In the inductive step, the statement follows if $A=0$. Suppose $A\ne0$. By scaling it, we may assume that its operator norm is $1$. Thus $Av=w$ for some unit vectors $v$ and $w$. As $A$ is paranormal,
$$
\|Aw\|=\|A^2v\|\ge\|Av\|^2=\|w\|^2=\|w\|.
$$
As $\|A\|=1$, we must have $\|Aw\|=\|w\|$. Hence $W:=\{w\in AV,\ \|Aw\|=\|w\|\}$ contains at least one nonzero vector.
It follows that $r=\dim\operatorname{span}(W)\ge1$. Let $\{Av_1,Av_2,\ldots,Av_r\}$ be a basis of $\operatorname{span}(W)$ and let $w=\sum_{i=1}^rc_iAv_i$ be an arbitrary unit vector in $\operatorname{span}(W)$. Since $A$ is paranormal, we have
$$
\|Aw\|=\left\|A^2\sum_{i=1}^rc_iv_i\right\|\ge\left\|A\sum_{i=1}^rc_iv_i\right\|^2=\|w\|^2=\|w\|.
$$
Again, as $\|A\|=1$, we must have $\|Aw\|=\|w\|$. Hence $W$ is a nontrivial invariant subspace of $A$. If we complete an orthonormal ordered basis of $W$ to an orthonormal ordered basis of $V$, the matrix representation of $A$ will become
$$
\pmatrix{U&Y\\ 0&X}
$$
where $U$ is a nonempty (because $r\ge1$) unitary matrix that represents the restriction of $A$ on $W$. Since $\|A^\ast\|=\|A\|=1$, the norm of every row of $A$ is at most $1$. Therefore $Y=0$. But then $X$ is paranormal and by induction assumption, it is normal. Therefore $A=U\oplus X$ is normal.


TITLE: Proof of L'Hospital's rule in the form of$\frac{\infty }{ \infty }$ for complex functions
QUESTION [1 upvotes]: Let $f$ and $g$ be complex functions that are continuous and differentiable in a neighborhood of $z_0$ and $g'(z)$ does not equal zero. If $\lim_{z\to\ z_0}f(z)=\lim_{z\to\ z_0}g(z)=\infty$ and the limit $\lim_{z\to\ z_0} \frac{f(z) }{ g(z) }$ exists prove:
$\lim_{z\to\ z_0} \frac{f(z) }{ g(z) }=\lim_{z\to\ z_0} \frac{f'(z) }{ g'(z) }$
I've seen many proofs for real functions for L'Hospital's rule in the form of $\frac{\infty  }{ \infty }$ but I am yet to find any formal proof for complex functions, does this rule apply to complex functions in the first place?

REPLY [2 votes]: In fact, L'Hopital is pretty much a non-issue here.
Thm: Assume both $f(z),g(z)\to \infty$ at $z_0.$ Then there exists $L\in (\mathbb C \cup\{\infty\})$ such that
$$\tag 1 \lim_{z\to z_0}\frac{f(z)}{g(z)} = \lim_{z\to z_0}\frac{f'(z)}{g'(z)}=L.$$
Proof: Since $f(z),g(z)\to \infty$ as $z\to z_0,$ these functions have poles of order $M,N$ at $z_0$ respectively, where $M,N$ are positive integers. Thus we can write
$$f(z)=\sum_{k=-M}^{\infty}a_k(z-z_0)^k,\,g(z)=\sum_{k=-N}^{\infty}b_k(z-z_0)^k,$$
for $z\in D(z_0,r)\setminus \{z_0\}$ for some $r>0,$ where $a_{-M},b_{-N}$ are nonzero numbers in $\mathbb C.$
Suppose $M=N.$ Then
$$\frac{f(z)}{g(z)} = \frac{\sum_{k=-M}^{\infty}a_k(z-z_0)^k}{\sum_{k=-M}^{\infty}b_k(z-z_0^k)} = \frac{\sum_{k=-M}^{\infty}a_k(z-z_0)^{k+M}}{\sum_{k=-M}^{\infty}b_k(z-z_0)^{k+M}}.$$
This is the quotient of two analytic functions in $D(z_0,r),$ whose nonzero values at $z_0$ are $a_{-M},b_{-M}$ respectively. Clearly the limit of this is $a_{-M}/b_{-M}.$
The quotient of derivatives in this case is
$$\frac{f'(z)}{g'(z)}=\frac{\sum_{k=-M}^{\infty}ka_k(z-z_0)^{k-1}}{\sum_{k=-M}^{\infty}kb_k(z-z_0)^{k-1}}.$$
By the same reasoning as above, the limit of this is $(-Ma_{-M})/(-Mb_{-M}) = a_{-M}/b_{-M}.$ We have thus proved the theorem for the case $M=N.$
In the case $M<N,$ $f(z)$ is on the order of $(z-z_0)^{-M}$ and $g(z)$ is on the order of $(z-z_0)^{-N}$ as $z\to z_0.$ It follows that $f(z)/g(z)\to 0.$ The same is true for the quotient of derivatives. If $M>N,$ then both $f(z)/g(z),f'(z)/g'(z)\to \infty.$ The proof of the theorem is complete.


TITLE: Superquadratic boundedness from $L^2$ convergence
QUESTION [0 upvotes]: Assume $f_n,f\in L^2(\mathbb{R}^3)$ and $f_n\to f$ strongly in $L^2$. It seems there is a common fact that there exists a superquadratic maps $\beta\in C([0,\infty);[0,\infty))$ such that $\beta(0)=0$, $\beta(t)t^{-2}\to+\infty$ as $t\to+\infty$, $\beta(t)t^{-1}\to+\infty$ as $t\to0^+$, and $\int_{\mathbb{R}^3}\beta(f_n)\,dx\le C<\infty$ where $C$ is independent of $n$. I have seen in many papers but I can't find it in the textbooks.

REPLY [2 votes]: Let me give a proof in $L^1$ and construct $\beta$ only for large values of $t$. Assuming first that $f=0$ we may suppose that $f_n \geq 0$. Let $E_{k,n}=\{2^k \le f_n<2^{k+1} \}$ for $k \in Z$ so that $\sum_k 2^k|E_{k,n}| \le \int_{R^N} f_n \le \sum_k 2^{k+1}|E_{k,n}|$. Next find an increasing  sequence of integers $n_j$ such that $\sum_{|k| \geq n_j} 2^k |E_{k,n}| \leq 2^{-j}$ for every $n$. This can be done since the series tend to $0$ as $n \to \infty$ (for a fixed $j$ first select $\nu$ in a such a way that all series are less than $2^{-j}$ for $n >\nu$ and then fix $n_j$ for the first $\nu$ terms). Now we can define $\beta(t)=jt$ for $t \in ]2^{n_j}, 2^{n_{j+1}}]$ and $\beta(t)=t$ for $t \leq 2^{n_1}$. Then
$$\int_{R^N}\beta(f_n) \leq \int_{\{f_n \le 2^{n_1}\}}f_n+\sum_{k \geq n_1} \beta (2^{k+1} )|E_{k,n}| \le c+\sum_j j\sum_{k=n_j}^{n_{j+1}-1}2^{k+1}|E_{k,n}| \le c+2\sum_j j 2^{-j} =C.
$$
When $f \neq 0$ we apply the same construction to $|f_n-f|$ and to $|f|$ to find $\beta_1$ in such a way that $\int_{R^N}(\beta_1(|f_n-f|)+\beta_1(|f|) \le C)$. The above construction gives $\beta_1$ increasing and convex. If $\beta(t)=\beta_1(t/2)$, then $\beta(|f_n|)\le \frac12 \beta_1 (|f_n-f|)+\frac12 \beta_1(|f|)$ and the bound follows by integration. The construction neat $t=0$ can be done similarly.


TITLE: On the functoriality of assigning a simplicial complex to is Stanley-Reisner ring
QUESTION [2 upvotes]: If $k$ is a field and $\Delta$ a finite simplicial complex with vertex set $x_1, \ldots, x_n$, the Stanley-Reiser ideal of $\Delta$ is
$$I_\Delta := \left\langle \prod_{i \in S}x_i : S \not \in \Delta \right\rangle \subset k[x_1, \ldots, x_n].$$
There is a bijective correspondence between simplicial complexes on a finite set $x_1, \ldots, x_n$ and monomial ideals of $k[x_1, \ldots, x_n]$ given by $\Delta\leftrightarrow I_\Delta$.
The Stanley-Reiser ring of $K$ is $k[\Delta] := k[x_1, \ldots, x_n]/I_\Delta$.

Are these constructions functorial?
Concretely, if $f : \Delta_1 \to \Delta_2$ is a simplicial map between finite simplicial complexes, does this induce a $k$-algebra morphism between $k[\Delta_1]$ and $k[\Delta_2]$?

REPLY [1 votes]: To expand on my comment, yes this correspondence can be made functorial, but is a contravariant functor.

Proposition (See e.g. Proposition 3.1.5 cf. this answer)
Let $f:\Gamma \to \Delta$ be a simplicial map where $\{1,2,\dots,m\}$ and $\{1,2,\dots,n\}$ are the vertex sets of $\Gamma$ and $\Delta$ respectively. Define the map $f^*:k[x_1,\dots,x_n] \to k[y_1,\dots,y_m]$ on generators by $f^*(x_i)=\displaystyle \sum_{j \in f^{-1}(i)} y_j$. Then $f^*$ induces a homomorphism $k[\Delta] \to k[\Gamma]$.

For example, let $\Gamma=\{\{1,\},\{2\}\}$ and $\Delta=\{\{1\}\}$, with simplicial map $f:\Gamma \to \Delta$ given by $f(1)=f(2)=1$. Note this is the example mentioned by Angina Seng in their answer. Then $k[\Delta]=k[y]$ and $k[\Gamma]=k[x_1,x_2]/(x_1x_2)$. The map $f^*$ induces the map $k[\Delta] \to k[\Gamma]$ given by $y \mapsto x_1+x_2$.