text:
\begin{document}
\input{zcom}
\setlength{\arraycolsep}{0.05cm}
\newcommand{\rest}{{T_\text{rest}}}
\newcommand{\zetahat}{\hat{\zeta}}

\newcommand{\tDelta}{{\tilde{\Delta}}}
\newcommand{\tDeltae}{{\tilde{\Delta}_e}}
\newcommand{\tT}{{\tilde{T}}}
\newcommand{\add}{{\cal A}}
\newcommand{\rem}{{\cal R}}
\newtheorem{sigmodel}{Signal Model}

\newcommand{\thr}{{\text{thr}}}
\newcommand{\delthr}{{\text{del-thr}}}
\newcommand{\delbound}{{b}}
\newcommand{\err}{{\text{err}}}
\newcommand{\Q}{{\cal Q}}

\newcommand{\dett}{{\text{det}}}
\newcommand{\CSres}{{\text{CSres}}}
\newcommand{\diff}{{\text{diff}}}

\newcommand{\Section}[1]{ \vspace{-0.13in}  \section{#1} \vspace{-0.12in} }
\newcommand{\Subsection}[1]{  \vspace{-0.12in} \subsection{#1}  \vspace{-0.08in} }
\newcommand{\Subsubsection}[1]{   \subsubsection{#1} }

\date{}
\maketitle

\newcommand{\Aset}{{\cal A}}
\newcommand{\Rset}{{\cal R}}
\newcommand{\Iset}{{\cal I}}
\newcommand{\Dset}{{\cal D}}
\newcommand{\Cset}{{\cal C}}
\newcommand{\Sset}{{\cal S}}
\newcommand{\sm}{e^2}
\newcommand{\smd}{\sm}

\begin{abstract}
In this work, we study the ``stability" of our recently proposed algorithm, LS-CS (compressive sensing on least squares residual), designed for recursive reconstruction of sparse signal sequences from noisy measurements. By ``stability" we mean that the number of extra elements and the number of misses from the current support estimate remains bounded by a small value compared to the current signal support size. This, in turn, implies that the LS-CS reconstruction error remains bounded by a small value compared to the total signal power. We show that ``stability" holds under mild assumptions (bounded noise, high enough SNR and enough measurements at every time) for a simple deterministic signal model with fixed signal power and support size, support changes (additions and removals) at every time, and gradual coefficient magnitude increase/decrease.

\end{abstract}

{\bf Index Terms: } compressed sensing, sparse reconstruction

\Section{Introduction}
Consider the problem of recursively and causally reconstructing time sequences of spatially  sparse signals (with unknown and time-varying sparsity patterns) from a limited number of linear incoherent measurements with additive noise. The signals are sparse in some transform domain referred to as the ``sparsity basis" \cite{dantzig}. Important applications include real-time dynamic MRI, video compression, single-pixel video imaging and spatial field sensing over time. Due to strong temporal dependency in the signal sequence, it is usually valid to assume that its {\em sparsity pattern (support of the sparsity transform vector) changes slowly over time}. This was empirically verified in \cite{icipmodcs} for dynamic MRI.
The solution to the static version of the above problem is provided by compressed sensing (CS). CS for noisy observations, e.g. Dantzig selector  \cite{dantzig} or Basis Pursuit Denoising (BPDN) \cite{bpdn}, has been shown to have small error as long as incoherence assumptions hold.
{\em Note that, in this paper, whenever we say ``CS", we refer to the Dantzig selector \cite{dantzig}.}

In \cite{kfcsicip,kfcspap}, we proposed the first recursive solution to the dynamic problem, CS on Least Squares residual (LS-CS) and CS on Kalman filtering residual (KF-CS). The key idea of LS-CS is to replace CS on the observation (simple CS) by CS on the least squares (LS) residual computed using the previous support estimate. Doing this significantly improves the reconstruction error of LS-CS when the number of measurements available at any time is small.

Other related work includes \cite{giannakis} (mostly focusses on the case when support does not change) \cite{rozell,romberg} (use past reconstructions to speed up current optimization but not to improve reconstruction error), and \cite{jung_etal} (causal but batch solution for dynamic MRI).

In \cite{kfcspap,lscspaper} we bounded LS-CS error and compared it with the CS bound. In \cite{kfcspap} we also studied LS-CS and KF-CS stability  but under strong assumptions and for a random walk model with increasing support size. By ``stability" we mean that the extras and misses in the support estimate are bounded by a small value compared to the support size and the reconstruction error remains small compared to the signal power. In \cite{lscspaper}, we proved LS-CS stability under mild  assumptions and for a bounded SNR and bounded support size model. But we still assumed that the delay between support addition/removal times is more than one. In many real applications, particularly if we define the support of a compressible signal using a smaller threshold, {\em the delay is actually one, i.e. the support changes occur at every time \cite{kfcsmri}. This important case is the focus of the current work.}

The paper is organized as follows.
 We give the LS-CS algorithm and the error bound from \cite{lscspaper} in Sec. \ref{lscs}. Our stability result and its implications and the outline of its proof is given in Sec. \ref{stability}. Simulation results are discussed in Sec. \ref{sims} and conclusions in Sec. \ref{conclusions}.

\Subsection{Problem Definition and Notation}
The set operations $\cup$, $\cap$, $\setminus$ have the usual meanings. $\phi$ denotes the empty set. $T^c$ denotes the complement of $T$ w.r.t. $[1,m]:=[1,2,\dots m]$, i.e. $T^c := [1,m] \setminus T$. $|T|$ denotes the cardinality of $T$.

For a vector, $v$, and a set, $T$, $v_T$ denotes the $|T|$ length sub-vector containing the elements of $v$ corresponding to the indices in the set $T$. $\|v\|_k$ denotes the $\ell_k$ norm of a vector $v$. If just $\|v\|$ is used, it refers to $\|v\|_2$.

For a matrix $M$, $\|M\|_k$ denotes its induced $k$-norm, while just $\|M\|$ refers to $\|M\|_2$. $M'$ denotes the transpose of $M$. For a tall matrix, $M$, $M^\dag : = (M'M)^{-1}M'$.

For a fat matrix $A$, $A_T$ denotes the sub-matrix obtained by extracting the columns of $A$ corresponding to the indices in $T$.
The $S$-restricted isometry constant \cite{dantzig}, $\delta_S$, for an $n \times m$ matrix (with $n<m$), $A$, and the $S,S'$ restricted orthogonality constant \cite{dantzig}, $\theta_{S,S'}$, are as defined in \cite[eq 1.3]{dantzig} and \cite[eq 1.5]{dantzig} respectively.

Let $(z_t)_{m \times 1}$ denote the spatial signal at time $t$ and $(y_t)_{n \times 1}$, with $n<m$, denote its noise-corrupted observation vector at $t$, i.e. $y_t = H z_t + w_t$. The signal, $z_t$, is sparse in a given sparsity basis (e.g. wavelet) with orthonormal basis matrix, $\Phi_{m \times m}$, i.e. $x_t \defn \Phi' z_t$ is a sparse vector. We denote its support by $N_t$ and we use $S_t:= |N_t|$ to denote its size.
Thus the observation model is
\bea
y_t = A x_t + w_t, \ A \defn H \Phi, \ \  \E[w_t]=0, \  \E[w_t w_t']= \sigma^2 I \ \ \ \

\label{obsmod}
\eea

We assume that $A$ has unit norm columns. The observation noise, $w_t$, is independent identically distributed (i.i.d.) over $t$ and is independent of $x_t$. Our goal is to recursively obtain the best estimates of $x_t$ (or equivalently of the signal, $z_t = \Phi x_t$) using $y_1, \dots y_t$. By {\em recursively}, we mean, use only $y_t$ and the estimate from $t-1$, $\xhat_{t-1}$, to compute the estimate at $t$.

To quantify the incoherence (approximate orthogonality) of $A$, define the following quantities.
\bd[$\sone$, $\sinf$]
\vspace{-0.08in}
\label{delta_bnd}
For $A:=H \Phi$,
\ben
\label{deltas}
\item let $\sone$ denote the largest $S$ for which $\delta_S < 1/2$,
\label{delta3s}
\item let $\sinf$ denote the largest $S$ for which $\delta_{2S}+ \theta_{S,2S} < 1$.
\een

\vspace{-0.1in}
\ed
We assume that the support changes slowly over time, i.e. the additions, $|N_t \setminus N_{t-1}| \le S_a  \ll  S_t$ and the removals, $|N_{t-1} \setminus N_t| \le S_a  \ll  S_t$. This was verified in \cite{kfcsmri}. Also, $A$ is incoherent enough to at least satisfy $S_t + S_a < \sone$ and $S_a < \sinf$.

{\em Further Notation. }
We use $\xhat_t$ to denote the estimate of $x_t$ given by our algorithm at time $t$ and $\Nhat_t$ to denote its support estimate.
We will use the following sets often.
\bd[$T$, $\Delta$, $\Delta_e$]
\vspace{-0.05in}
We use $T  : = \Nhat_{t-1}$ to denote the support estimate from the previous time.
We use $\Delta := N_t \setminus T$ to denote the unknown part of the support at the current time and $\Delta_e := T \setminus N_t$ to denote the ``erroneous" part of $T$. We attach the subscript $t$ to the set, i.e. we use $T_t$, $\Delta_t$ or $\Delta_{e,t}$ where necessary, e.g. in Sec. \ref{proofs}.

\ed
\bd[$\tT$, $\tDelta$, $\tDelta_e$]
\vspace{-0.05in}
We use $\tT := \Nhat_t$ to denote the final estimate of the current support; $\tDelta : = N_t \setminus \tT$ to denote the ``misses" in the final estimate and $\tDelta_e := \tT \setminus N_t$ to denote the ``extras".
\vspace{-0.08in}
\ed

\Section{CS on Least Squares Residual (LS-CS)}
\label{lscs}
Given observation, $y$, CS (Dantzig selector) \cite{dantzig} solves
\bea
\min_{\zeta} \|\zeta\|_1 \ \text{s.t.} \ \|A'(y - A \zeta)\|_\infty < \lambda
\label{simplecs}
\eea
The main idea of LS-CS is to replace CS on $y_t$ (simple CS) by CS on the observation residual computed using the previous support estimate, $T:=\Nhat_{t-1}$. The residual is computed as follows:
\bea
(\xhat_{t,\text{init}})_{T} \se {A_{T}}^\dag y_t, \ \ (\xhat_{t,\text{init}})_{T^c} = 0 \nn \\
\tty \se  y_t - A \xhat_{t,\text{init}}
\label{deftty0}
\eea
Notice that the residual can be rewritten as $\tty = A\beta_t + w_t$ where $\beta_t$ is a $|T \cup \Delta|$-sparse vector with $(\beta_t)_{(T \cup \Delta)^c} = 0$,
\bea
(\beta_t)_T \se (x_t)_T - {A_T}^\dag y_t  = -  {A_{T}}^\dag (w_t + A_\Delta (x_t)_\Delta), \nn \\
(\beta_t)_\Delta \se (x_t)_\Delta - 0 = (x_t)_\Delta
\label{defbeta}
\eea
If $|T| \le \sone$,
$\|(\beta_t)_T\|^2 \le  2 \frac{{\theta_{|T|,|\Delta|}}^2}{(1-\delta_{|T|})^2} \|x_\Delta\|^2 + \frac{2}{(1-\delta_{|T|})} \|w\|^2 \le 8{\theta_{|T|,|\Delta|}}^2 \|x_\Delta\|^2 + 4 \|w\|^2$. Thus, if $|\Delta|$ is small enough (i.e. $S_a$ is small enough and $T \approx N_{t-1}$) and if the noise is small enough, then $\|(\beta_t)_T\|$ will be small, i.e. $\beta_t$ will be only $|\Delta|$-approximately-sparse. Thus, doing CS on $\tty$ incurs much less error than simple CS, which needs to reconstruct a $|N_t|$-sparse signal, $x_t$ [see Fig. \ref{fig1}].

At each time $t$, LS-CS computes $\tty$ using (\ref{deftty0}) and solves (\ref{simplecs}) with $y = \tty$. It uses the output to compute additions to $T$ to get a new support estimate, $\tT_\dett$, followed by LS estimation using $\tT_\dett$ to get $\xhat_{t,\dett}$. Finally it uses $\xhat_{t,\dett}$ to compute deletions from $\tT_\dett$ to get the final support estimate, $\Nhat_t$, followed by LS estimation to get $\xhat_t$.

\Subsection{LS-CS algorithm}
\label{lscsalgo}
We list the LS-CS algorithm \cite{lscspaper,kfcspap} below.
(In LS-CS, at $t=0$ we run simple CS (or equivalently CS-residual with $T=\phi$). This needs  a large enough number of measurements, $n_0 > n$ so that the simple CS estimate is accurate enough. Thus at $t=0$ we use $A = H_0 \Phi$ where $H_0$ is an $n_0 \times m$ measurement matrix.)

\noindent Set $\Nhat_{-1}=\phi$.

For $t \ge 0$ do,

\ben
\item If $t=0$, set $A := H_0 \Phi$, else set $A := H \Phi$.
\label{step1}

\item {\em Initial LS. } Use $T:=\Nhat_{t-1}$ to compute the initial LS estimate, $\xhat_{t,\text{init}}$, and the LS residual, $\tty$ using (\ref{deftty0}).
\label{initls}

\item {\em CS-residual. } Do CS (Dantzig selector) on the LS residual, i.e.  solve (\ref{simplecs}) with $y= \tty$ and denote its output by $\betahat_t$. Compute $\xhat_{t,\CSres}$ using
$
\xhat_{t,\CSres} : = \betahat_t + \xhat_{t,\text{init}}.
\label{xhatcsres}
$

\item {\em Detection and LS. } Compute additions to the support using
\label{addls}
\bea
\Nhat_{t,\dett} = T \cup \{ i \in [1,m] : |(\xhat_{t,\CSres})_i| > \alpha \}
\eea
Compute the LS estimate, $\xhat_{t,\dett}$, using $\tT_{\dett}:=\Nhat_{t,\dett}$ as
\bea
(\xhat_{t,\dett})_{\tT_{\dett}} \se {A_{\tT_{\dett}}}^\dag  y_t, \ \ (\xhat_{t,\dett})_{(\tT_{\dett})^c} = 0
\label{secls}
\eea

\item {\em Deletion and LS. } Compute deletions from the support using
\label{delete}
\bea
\Nhat_t \se  \tT_{\dett} \setminus \{ i \in  \tT_{\dett} : |(\xhat_{t,\dett})_i| \le \alpha_{del} \}
\label{delstep}
\eea
Compute the LS estimate, $\xhat_t$, using $\tT:=\Nhat_t$ as
\bea
(\xhat_{t})_{\tT} \se {A_{\tT}}^\dag  y_t, \ \ (\xhat_{t})_{\tT^c} = 0
\label{finalls}
\eea

\item Output $\xhat_t$ and $\hat{z}_t = \Phi \xhat_t$.  Feedback $\Nhat_t$.
\een
Increment $t$ and go to step \ref{step1}.

We define the following sets which will be used in Sec. \ref{stability}.
\bd[$\tT_{\dett}$, $\tDelta_{\dett}$, $\tDelta_{e,\dett}$]
\vspace{-0.07in}
We define $\tT_{\dett} := \Nhat_{t,\dett}$, $\tDelta_{\dett}:= N_t \setminus \tT_{\dett}$ and $\tDelta_{e,\dett}:= \tT_{\dett} \setminus N_t$.
\vspace{-0.05in}
\ed

\Subsection{Reconstruction Error Bound for CS-residual step}
\label{csresbnd}
In \cite[Theorem 1, Corollary 1]{lscspaper}, we bounded CS-residual error and showed that (a) our bounds hold under weaker assumptions than those of \cite{dantzig} and (b) under these weaker assumptions, the bound on CS error is much looser.
We restate \cite[Corollary 1]{lscspaper} below.
\begin{lemma}
Assume that  $\|w\|_\infty \le {\lambda}/{\|A\|_1}$, $|\Delta| \le \sinf$, $|T| \le \sone$.

The CS-residual error satisfies
\label{cor1}
\bea
\|x - \xhat_{\CSres}\|^2 \sle C' + C''{\theta_{|T|,|\Delta|}}^2 \|x_\Delta\|^2, \ \text{where} \nn \\
 C' \equiv C'(|T|,|\Delta|) \sdefn C_2(|\Delta|) |\Delta| \lambda^2 +  C_3(|\Delta|) |T| \frac{4n\lambda^2}{\|A\|_1^2}, \nn \\
\label{defcprime}
 C'' \equiv C''(|T|,|\Delta|) \sdefn C_3(|\Delta|) |T|8,  \\
C_2(S) \sdefn \frac{48}{(1-\delta_{2S} - \theta_{S,2S})^2}, \nn \\
\label{defc2c3}
C_3(S) \sdefn 8 + \frac{24 \theta_{S,2S}^2}{(1-\delta_{2S} - \theta_{S,2S})^2}
\eea

\end{lemma}

\begin{remark}
Notice that $C'(|T|,|\Delta|)$ and $C''(|T|,|\Delta|)$ are {\em non-decreasing functions of $|T|$, $|\Delta|$}.

\label{cor1_rem}
\end{remark}

\Section{LS-CS Stability}
\label{stability}
In Sec. \ref{csresbnd} we bounded the CS-residual error as a function of $|T|,|\Delta|$. The bound is small as long as $|\Delta_e|$ and $|\Delta|$ are small. Similarly a bound on the final LS-CS error as a function of $|\tT|,|\tDelta|$ is easy to obtain.
The next question is: under what conditions on the measurement model, {\em will $|\tDelta_e|$, $|\tDelta|$ (and hence $|\Delta_e|$, $|\Delta|$) remain stable, i.e. remain bounded by a small value compared to the signal support size, at all times? This, in turn, will imply that the LS-CS error is small compared to the signal power at all times.}

\Subsection{LS-CS Stability Result}
For studying stability, we need to assume a signal model. We assume a simple deterministic model that (a) allows equal and nonzero number of additions/removals from the support at every time, (b) allows a new coefficient magnitude to gradually increase from zero for sometime and finally reach a constant value, $M$, (c) allows coefficients to gradually decrease and become zero (get removed from support) at the same rate, and (d) has constant signal power and support size.

\begin{sigmodel} Assume the following.
\ben

\item At $t=0$, the support size is $S_0$. The support contains $2S_a$ elements each with magnitude $M/d,2M/d, \dots (d-1)M/d$, and $S_0-(2d-2)S_a$ elements with magnitude $M$.

\item At each $t>0$, $S_a$ coefficients get added to the support at magnitude $M/d$.

\item At each $t>0$, $S_a$ coefficients which had magnitude $M/d$ at $t-1$ get removed from the support (magnitude becomes zero).

\item At each $t>0$, the magnitude of $S_a$ coefficients which had magnitude $j M/d$ at $t-1$ increases to $(j+1)M/d$. This occurs for all $1 \le j \le d-1$.

\item At each $t>0$, the magnitude of $S_a$ coefficients which had magnitude $j M/d$ at $t-1$ decreases to $(j-1)M/d$. This occurs for all $2 \le j \le d$.

\een
\label{sigmod2}
\end{sigmodel}

From the above model, the composition of the support at any time $t$ is the same as that at $t=0$. It consists of $(d-1)S_a$ increasing and $(d-1)S_a$ decreasing coefficients, and $S_0- (2d-2)S_a$ constant coefficients (with magnitude $M$). Also $|N_t|=S_0$ for all $t$.

To understand the model better, let us define the following sets.
\bd Define the following, for any $d_0 \le d$
\vspace{-0.04in}
\ben
\item Newly added set, $\Aset_t:= \{i: |x_{t,i}|=M/d,  \  |x_{t-1,i}|=0 \}$.
\item Newly removed set, $\Rset_t:= \{i: |x_{t,i}|=0,  \  |x_{t-1,i}|=M/d \}$.

\item Small coefficients set, $\Sset_t(d_0):= \{i:  0 < |x_{t,i}| < d_0M/d \}$.
\item $\Dset_{t}(d_0): = \{i: |x_{t,i}| = (d_0-1)M/d, \ |x_{t-1,i}| = d_0M/d \}$.
\item $\Iset_{t}(d_0): = \{i: |x_{t,i}| = d_0M/d, \ |x_{t-1,i}| = (d_0-1)M/d \}$.
\een
\vspace{-0.04in}
\ed

From our model, at any $t$, $S_a$ elements enter the set $\Sset_t(d_0)$ from the bottom (set $\Aset_t$) and $S_a$ enter from the top (set $\Dset_{t}(d_0)$); $S_a$ elements leave  $\Sset_t(d_0)$ from the bottom  (set $\Rset_t$) and $S_a$ from the top (set $\Iset_{t}(d_0)$), i.e.
\bea
\Sset_t(d_0) = \Sset_{t-1}(d_0) \ \cup \ (\Aset_t \cup \Dset_{t}(d_0)) \ \setminus  \ (\Rset_t \cup \Iset_{t}(d_0))
\label{sseteq}
\eea

Our approach to show stability is as follows. We use Lemma \ref{cor1} to obtain conditions for an element of $\Delta$ to definitely get detected at $t$. Next, we use a bound on the error in the LS step after the detection step to obtain conditions for a nonzero element of $\tT_{\dett}$ to not get falsely deleted and for all elements of $\tDelta_{e,\dett}$ to get deleted.

Using the above conditions, we obtain sufficient conditions to ensure that at the end of LS-CS at time $t$, $\tDelta \subseteq \Sset_t(d_0)$ (i.e. $|\tDelta| \le (2d_0-2)S_a$) and $|\tDelta_{e}|=0$ for some $d_0 \le d$. In other words, all elements with current magnitude greater than or equal to $d_0M/d$ are correctly detected and not falsely deleted, while all zero elements (removals or false additions) are deleted. This leads to the following result.

\begin{theorem}
For any $d_0$, let \\
$k^a:=\max(1,(2d_0-2))S_a$, ~ $k^d:=\max(0,(2d_0-3))S_a$,
\label{stabres2}
\bea
&& \sm:= \frac{S_a (\sum_{j=1}^{d_0-1} j^2 + \sum_{j=1}^{d_0-2} j^2) M^2}{d^2}, \nn \\
&& \theta^a:=\theta_{S_0,k^a}, \ \ \theta^d:= \theta_{S_0+S_a+f,k^d}, \ \nn \\
&& C':=C'(S_0,k^a), \ \ C'':=C''(S_0,k^a),
\eea
Under Signal Model \ref{sigmod2}, if the following hold for some $d_0 \le d$,
\ben
\item the addition threshold, $\alpha$, is set large enough so that there are at most $f$ false additions per unit time,
\label{addthresh}

\item  the deletion threshold, $\alpha_{del}^2  = (4n\lambda^2/\|A\|_1^2) + 8 (\theta^d)^2 \sm $,
\label{delthresh}

\item $\|w\|_\infty \le \lambda/\|A\|_1$, $k^a S_a \le \sinf$, $S_0+S_a + f \le \sone$,
\label{measmodel}

\item $2S_a (\theta^a)^2 C'' < 1$ and $(d_0M/d)^2 \ge \max(G1,G2)$, where
\label{add_del}
\bea
G1 \se \frac{2 \alpha^2 + 2C' + 2(\theta^a)^2  \sm C''}{1 - 2S_a (\theta^a)^2 C''} \nn \\
G2 \se 2\alpha_{del}^2 + \frac{8n\lambda^2}{\|A\|_1^2} + 16 (\theta^d)^2 \smd
\eea

\item and, at $t=0$, we use enough measurements, $n_0$, so that $\tDelta  \subseteq \Sset_0(d_0)$, $|\tDelta| \le (2d_0-2)S_a$, $|\tDelta_e| =0$, and $|\tT| \le S_0$,
\label{initass}

\een

then,
\ben
\item at all $t \ge 0$, $\tDelta \subseteq \Sset_t(d_0)$, i.e. no element with magnitude $d_0M/d$ or larger is part of the unknown support.
\item at all $t \ge 0$, $|\tDelta| \le (2d_0-2)S_a$,  $|\tDelta_e| =0$, and $|\tT| \le S_0$,
\een
\end{theorem}

\begin{corollary}
Under the assumptions of Theorem \ref{stabres2},
\label{stabres2_cor}
\ben
\item at all $t > 0$, $|\Delta| \le k^a$,
$|\Delta_e| \le S_a$, $|T| \le S_0$ and  $|\tDelta_\dett| \le k^d$,
$|\tDelta_{e,\dett}| \le S_a+f$, $|\tT_\dett| \le S_0+S_a+f$,

\item at all $t \ge 0$, the LS-CS error, $\|x-\xhat\|^2 \le \frac{4n\lambda^2}{\|A\|_1^2} + (8(\theta_{S_0,(2d_0-2)S_a})^2+1) (\smd+S_a (d_0-1)^2M^2/d^2)$.

\item at all $t \ge 0$, the CS-residual error, $\|x - \xhat_\CSres\|^2 \le C' + (\theta^a)^2 (\sm + S_a d_0^2 M^2/d^2) C''$.
\een
\end{corollary}

\begin{remark}
Note that the initialization condition (condition \ref{initass}) is not restrictive. Denote the bound given by Theorem 1.1 of \cite{dantzig} for $S=S_0$ by $B_1$. It can be shown that condition \ref{initass} will hold if assumptions of Theorem 1.1 of \cite{dantzig} hold ($n_0$ is large enough); $\alpha_0$ is large enough to ensure at most $f$ false additions; $\alpha_{del,0} = ({4n\lambda^2}/{\|A\|_1^2})+8 (\theta_{S_0+f,k^a})^2 \sm$; and $M^2 > \min((\alpha_0+B_1)^2,4\alpha_{del,0}^2)$. Here $\alpha_0$ ($\alpha_{del,0}$) are the addition (deletion) thresholds used at $t=0$.
\label{initremark}
\end{remark}

\Subsection{Implications}
Under Signal Model \ref{sigmod2}, at all $t$, $|N_t|= S_0$; there are $S_a$ additions and removals; and the signal power is $\frac{S_a\sum_{j=1}^{d-1} j^2 M^2}{d^2} + (S_0-(2d-2)S_a)M^2$.

Also notice that if $2dS_a \ll S_0$ (valid to assume that only a small number of coefficients are increasing or decreasing), then Theorem \ref{stabres2} implies that $|\tDelta| \le (2d_0-2)S_a < 2dS_a \ll S_0$, i.e. $|\tDelta|$ is small compared to the support size, $S_0$. Clearly, $|\tDelta_{e}|=0 \ll S_0$. Also, if the SNR is large enough, clearly the LS-CS error bound is much smaller than the signal power. In other words, LS-CS is ``stable".

From Theorem \ref{stabres2}, under Signal Model \ref{sigmod2}, ``stability" is ensured under the following mild assumptions: (a) the addition/deletion thresholds are appropriately set (conditions \ref{addthresh} and \ref{delthresh});  (b) the noise is bounded and (c) the SNR is high enough and there are enough measurements (for a given support change rate, $S_a$, and magnitude change rate, $M/d$) so that $\sone, \sinf$ are large enough for condition \ref{measmodel} to hold and $\theta^2$, $C',C''$ are small enough for condition \ref{add_del} to hold.

Notice that if $M/d$ is large enough and if $f \ll S_0$ and $(2d_0-2)S_a \ll S_0$, then the requirements of Theorem \ref{stabres2} on the measurements (condition \ref{measmodel}) are {\em significantly weaker} than those for the corresponding CS results \cite[Theorems 1.1,1.2]{dantzig} which require $S_0 \le \sinf$.

\Subsection{Key Lemmas for Theorem \ref{stabres2}}
The following facts follow easily from the LS-CS algorithm.
\ben
\item An $i \in \Delta$ will definitely get detected if $x_i^2 > 2\alpha^2 + 2\|x - \xhat_\CSres\|^2$.
\label{det1}

\item An $i \in (\tT_\dett \setminus \tDelta_{e,\dett})$ will definitely not get falsely deleted if $x_i^2 > 2 \alpha_{del}^2 + 2\|(x - \xhat_\dett)_{\tT_\dett}\|^2$.
\label{nofalsedel1}

\item All $i \in \tDelta_{e,\dett}$ will get deleted if $\alpha_{del}^2 \ge \|(x - \xhat_\dett)_{\tT_\dett}\|^2$.
\label{truedel1}

\item If $\|w\|_\infty \le \lambda/\|A\|_1$ and $|\tT_\dett| \le \sone$, then $\|(x - \xhat_\dett)_{\tT_\dett}\|^2 \le (4n\lambda^2/\|A\|_1^2) + 8 {\theta_{|\tT_\dett|,|\tDelta_\dett|}}^2 \|x_{\tDelta_\dett}\|^2$. This follows using an approach similar to the bound on $\|\beta_T\|$ (given below (\ref{defbeta})).
\label{errls1}

\item The bound in fact \ref{errls1} is non-decreasing in $|\tT_\dett|$ and $|\tDelta_\dett|$.
\label{nondec}
\een

Using the above facts, we can prove the following lemmas.
\vspace{-0.05in}
\begin{lemma}[Detection condition]
Assume that $\|w\|_\infty \le \lambda/\|A\|_1$, $|T| \le S_T \le  \sone$ and $|\Delta| \le S_\Delta \le \sinf$. Let $b:=\|x_\Delta\|_\infty$. For a $\gamma \le 1$, let $\Delta_1:=\{i \in \Delta: \gamma b^2 \le x_i^2 \le b^2 \}$ and $\Delta_2:= \Delta \setminus \Delta_1$. All $i \in \Delta_1$ will definitely get detected at the current time if
\label{detectcond}
\bea
{2|\Delta_1|C''(S_T,S_\Delta)} {\theta_{S_T,S_\Delta}}^2 & < & {\gamma} \ \ \text{and} \nn \\
 \frac{2 \alpha^2 + 2C'(S_T,S_\Delta) + 2{\theta_{S_T,S_\Delta}}^2C''(S_T,S_\Delta) \|x_{\Delta_2}\|^2}{\gamma - 2{\theta_{S_T,S_\Delta}}^2 |\Delta_1| C''(S_T,S_\Delta)} & < & b^2
\label{detcond}
\eea

\end{lemma}

{\em Proof: }
Notice that $\|x_\Delta\|^2 \le |\Delta_1| b^2 + \|x_{\Delta_2}\|^2$. Using Lemma \ref{cor1}, if
$\|w\|_\infty \le \lambda/\|A\|_1$, $|T| \le \sone$ and $|\Delta| \le \sinf$, $\|x - \xhat_\CSres\|^2 \le C' + \theta^2 C''\|x_\Delta\|^2 \le C' + \theta^2 C''(|\Delta_1| b^2 + \|x_{\Delta_2}\|^2)$. Using fact \ref{det1} and the fact that for all $i \in \Delta_1$, $x_i^2 \ge \gamma b^2$, we can conclude that all $i \in \Delta_1$ will get detected if ${2|\Delta_1|C''(|T|,|\Delta|)} {\theta_{|T|,|\Delta|}}^2 < {\gamma}$ and $\frac{2 \alpha^2 + 2C'(|T|,|\Delta|) + 2{\theta_{|T|,|\Delta|}}^2C''(|T|,|\Delta|) \|x_{\Delta_2}\|^2}{\gamma - 2{\theta_{|T|,|\Delta|}}^2 |\Delta_1| C''(|T|,|\Delta|)}  < b^2$. Using Remark \ref{cor1_rem}, the left hand sides of both inequalities are non-decreasing functions of $|T|,|\Delta|$. Thus if $|T| \le S_T$ and $|\Delta| \le S_\Delta$, and if (\ref{detcond}) holds, then all $i \in \Delta_1$ will get detected, i.e. Lemma \ref{detectcond} follows.

\begin{lemma}[No false deletion condition]
Assume that $\|w\|_\infty \le \lambda/\|A\|_1$, $|\tT_\dett| \le S_T \le \sone$ and $|\tDelta_\dett| \le S_\Delta$. For a given $b_1$, let $T_1:=\{i \in \tT_\dett:x_i^2 \ge b_1\}$. All $i \in T_1$ will not get (falsely) deleted at the current time if
\label{nofalsedelscond}
$
b_1^2 >2 \alpha_{del}^2 + \frac{8n\lambda^2}{\|A\|_1^2} + 16 {\theta_{S_T,S_\Delta}}^2 \|x_{\tDelta_\dett}\|^2.
$
\end{lemma}
{\em Proof: } The lemma follows directly from facts \ref{nofalsedel1}, \ref{errls1} and \ref{nondec}.

\begin{lemma}[Deletion condition]
Assume that $\|w\|_\infty \le \lambda/\|A\|_1$, $|\tT_\dett| \le S_T \le \sone$ and $|\tDelta_\dett| \le S_\Delta$. All elements of $\tDelta_{e,\dett}$ will get deleted if
\label{truedelscond}
$
\alpha_{del}^2 \ge \frac{4n\lambda^2}{\|A\|_1^2} + 8 {\theta_{S_T,S_\Delta}}^2 \|x_{\tDelta_\dett}\|^2.
$
\end{lemma}
{\em Proof: } The lemma follows directly from facts \ref{truedel1}, \ref{errls1} and \ref{nondec}.

\begin{figure}[t!]
\centerline{
\epsfig{file = C:/Code/KFCS/LSCS_KFCS_code/icassp10_CS_large_delthresh.eps, width=5cm, height=3cm}

}
\vspace{-0.2in}
\caption{\small{Stability of LS-CS, CS-residual error \& comparison with CS.}}
\vspace{-0.15in}
\label{fig1}
\end{figure}

\Subsection{Outline of Proof of Theorem \ref{stabres2} and Corollary \ref{stabres2_cor}}
\label{proofs}

The proof of Theorem \ref{stabres2} follows by induction. Using condition \ref{initass}, the result holds for $t=0$. This proves the base case.
For the induction step, assume that $\tDelta_{t-1} \subseteq \Sset_{t-1}$, $|\tDelta_{e,t-1}|=0$ and $|\tT_{t-1}| \le S_0$. We use the signal model to show that $\Delta_{t} \subseteq \Sset_{t-1}(d_0) \cup \Aset_t \setminus \Rset_t$ and $\Delta_{e,t} \subseteq \Rset_t$. Thus, $|\Delta_{t}| \le
k^a$ and $|\Delta_{e,t}| \le S_a$. Also, $|T_t|=|\tT_{t-1}| \le S_0$.
Next, we use this and conditions \ref{measmodel} and \ref{add_del} in Lemma \ref{detectcond} (applied with $\gamma=1$) to show that $\tDelta_{\dett,t} \subseteq \Sset_{t-1}(d_0) \cup \Aset_t \setminus (\Rset_t \cup \Iset_{t}(d_0)) = \Sset_{t}(d_0) \setminus \Dset_t(d_0)$, i.e. the elements that just increased to $d_0M/d$ definitely get detected (the last equality follows from (\ref{sseteq})). Thus $|\tDelta_{\dett,t}| \le k^d$.
 Because of condition \ref{addthresh}, $|\tDelta_{e,\dett,t}| \le S_a+f$ and hence $|\tT_{\dett,t}| \le |N_t|+ |\tDelta_{e,\dett,t}| \le S_0+S_a+f$.
We use this and conditions \ref{measmodel} and \ref{add_del} in Lemma \ref{nofalsedelscond} (applied with $b_1=d_0M/d$) to show that only the elements that have magnitude $(d_0-1)M/d$ or lesser may get falsely deleted (and no others), i.e. $\tDelta_t \subseteq \Sset_{t-1}(d_0) \cup (\Aset_t \cup \Dset_{t}(d_0)) \setminus (\Rset_t \cup \Iset_{t}(d_0)) = \Sset_{t}(d_0)$. Thus, $|\tDelta_t| \le (2d_0-2)S_a$. Finally, we use condition \ref{delthresh} in Lemma \ref{truedelscond} to show that $|\tDelta_{e,t}|=0$ and thus $|\tT_t| \le S_0$. This completes the proof of the induction step.

For the first part of Corollary \ref{stabres2_cor}, use Theorem \ref{stabres2} to bound $|\tDelta_{t-1}|,|\tT_{t-1}|,|\tDelta_{e,t-1}|$. The discussion above then gives the desired bounds on $|\Delta_t|,|T_t|,|\Delta_{e,t}|$ and $|\tDelta_{\dett,t}|,|\tT_{\dett,t}|,|\tDelta_{e,\dett,t}|$.
The second and third part follow using $\tDelta \subseteq \Sset_t(d_0)$ and $\Delta \subseteq \Sset_{t-1}(d_0) \cup \Aset_t \setminus \Rset_t$.

The complete proof is given in the Appendix of the long version of this paper (available at \url{http://www.ece.iastate.edu/~namrata/LSCS_stability.pdf}).

\Section{Simulation Results}
\label{sims}
We ran 50 simulations of Signal Model \ref{sigmod2} with $m=200$, $S_0=20$, $S_a=2$, $d=1$, $M=3$, and the observation model of (\ref{obsmod}) with $n=59$, a random Gaussian $A$ and $w_t \sim unif(-c,c)$ with $c=0.1266$. LS-CS was run with $\alpha=0.0633$, $\alpha_{del}=14\alpha=0.8862$ and $\lambda=c \|A\|_1$. As can be seen from Fig. \ref{fig1}, the LS-CS and CS-residual error are stable at 0.1\% and 8\%. The CS error (both Dantzig and Gauss-Dantzig selector with $\lambda= c \|A\|_1/10$, which is the best choice of $\lambda$) is between 40-50\%.

Also,  $|\tDelta_{e}|=0$ and $|\tDelta|=0$ in all simulations, at all $t$, i.e. Theorem \ref{stabres2} holds with $d_0=d=1$.

\Section{Conclusions}
\label{conclusions}
We showed the stability of  LS-CS under fairly mild assumptions (bounded noise, high enough SNR and enough measurements at every time) for a simple deterministic signal model with fixed signal power; fixed support size, $S_0$; support changes (additions and removals) at every time at rate $S_a \ll S_0$; and gradual coefficient magnitude increase/decrease at rate $M/d$. By ``stability" we mean that the extras, $|\tDelta_e|$, and the misses, $|\tDelta|$, in the support estimate, remain bounded by a small value compared to $S_0$. This also implies that the LS-CS error remains small compared to the signal power. Future work includes studying KF-CS stability for a similar signal model.

\bibliographystyle{IEEEbib}
\bibliography{tipnewpfmt_kfcsfullpap}

\clearpage \input{LSCS_stab_appendix}

\end{document}

config: arxiv


text:
\begin{document}
\title{Invariant tensors and cellular categories}
\author{Bruce W. Westbury}
\address{Mathematics Institute\\
University of Warwick\\
Coventry CV4 7AL}
\email{Bruce.Westbury@warwick.ac.uk}
\date{\today}
\begin{abstract} Let $U$ be the quantised enveloping algebra associated
to a Cartan matrix of finite type. Let $W$ be the tensor product of
a finite list of highest weight representations of $U$. Then $\End_U(W)$
has a basis called the dual canonical basis and this gives an integral form for
 $\End_U(W)$. We show that this integral form is cellular by using results
due to Lusztig.
\end{abstract}
\maketitle

\section{Introduction}
The definition of a cellular algebra was given in \cite{MR1376244}
and the examples of cellular algebras given were the Temperley-Lieb
algebras, the Hecke algebras, the Brauer (or Birman-Wenzl) algebras
and the Ariki-Koike algebras.

The aim of this paper is to give a general construction of cellular
algebras using the dual canonical bases of spaces of invariant tensors
defined in \cite[Part IV]{MR1227098}. This construction includes the Temperley-Lieb
algebras, the Hecke algebras, and the  Birman-Wenzl algebras.
This should not be confused with the observation made in \cite{MR1713038}
that the results of \cite[Chapter 29]{MR1227098} imply that the
algebra $\mathbf{\dot U}$ and its finite dimensional quotients
$\mathbf{\dot U}/\mathbf{\dot U}[P]$ are cellular.

The definition of a cellular algebra has a natural generalisation
to cellular categories. An endomorphism algebra in a cellular category
is cellular and many of the sequences of cellular algebras arise this
way. Examples are the many diagram algebras such as the partition algebras,
the blob algebras, the affine Temperley-Lieb algebras, the contour algebras,
the two-boundary Temperley-Lieb algebras.

Let $U$ be the quantised enveloping algebra associated
to a Cartan matrix of finite type and let $V$ be a self-dual finite
dimensional highest weight representation. Then the category of invariant
tensors has objects $n=0,1,2,\ldots $ and the morphisms are
$\Hom_U(\otimes^nV,\otimes^mV)$. The examples which have been studied
are
\begin{itemize}
\item \cite{MR1446615}, the representations of $\fsl(2)$
\item \cite{MR992598}, the vector representations of the symplectic and orthogonal Lie algebras
\item \cite{MR1403861}, the fundamental representations of the rank two simple Lie algebras
\item \cite{MR1941983}, the adjoint representation of $\fsl(n)$
\item \cite{MR2388243}, the spin representation of $\fso(7)$
\end{itemize}
In each case there is an integral form of the category of invariant
tensors which is constructed using planar graphs and in each case
this integral form can be seen to be cellular.

If $V$ is not self-dual then we need to consider tensor products
of copies of both $V$ and $V^*$. The only case that has been studied
is for $V$ the vector representation of $\fsl(n)$. Then the walled
Brauer algebras are endomorphism algebras in the category of invariant
tensors.

In this paper we consider a larger category of invariant tensors.
This is the full subcategory of the category of finite dimensional
representations of $U$ whose objects are tensors products of highest
weight representations. In this paper we observe that the results of
\cite[Part IV]{MR1227098} show that the dual canonical basis defines an
integral form of this category and that this integral form is cellular.
In particular this shows that if $W$ is any tensor product of highest
weight representations then the integral form of $\End_U(W)$ associated
to the canonical basis is cellular.

This work was influenced by the principle that the diagram bases and the
dual canonical bases have similar properties. In the examples in which
the diagram bases have been defined it is straightforward to see that
the category is cellular. It is then natural to look for a cellular
structure in the dual canonical basis.

The diagram bases and dual canonical bases for $\fsl(2)$ are discussed and
shown to be the same in \cite{MR1446615}. The diagram
bases and the dual canonical bases for the category of
invariant tensors of $\fsl(3)$ are compared in \cite{MR1680395} and shown to be
different.

The diagram bases and the dual canonical bases have the following properties in
common. They each define an integral form of the category of invariant tensors.
They each admit a cellular structure with the same poset. In each case the
tensor functor $-\otimes -$ and the duality functor respect the cell structure.
This makes it reasonable to conjecture that these categories are equivalent
as integral forms and that the equivalences respect the cellular structure, the
tensor structure and the duality.

\section{Cellular categories}
First we extend the definition of a cellular algebra given in
\cite{MR1376244} to cellular categories. The motivating examples
are the Temperley-Lieb category discussed in \cite{MR1343661},
and the categories whose endomorphism algebras are the sequences
of algebras in the Introduction.

\begin{defn}
Let $R$ be a commutative ring with identity. Let $\cA$ be a $R$-linear
category with an anti-involution $*$. Then cell datum for $\cA$ consists
of a partially ordered set $\Lambda$, a finite set $K(n,\lambda)$
for each $\lambda\in\Lambda$ and each object $n$ of $\cA$, and for
$\lambda\in\Lambda$ and $n$,$m$ any two objects of $\cA$ we have an inclusion
\[ C\colon K(n,\lambda)\times K(m,\lambda)\rightarrow \Hom_\cA(n,m) \]
\[ C\colon (S,T)\mapsto C^\lambda_{S,T} \]
The conditions that this datum is required to satisfy are:
\begin{enumerate}
\item[C-1] For all objects $n$ and $m$, the image of the map
\[ C\colon \coprod_{\lambda\in\Lambda} K(n,\lambda)\times K(m,\lambda)
\rightarrow \Hom_\cA(n,m) \]
is a basis for $\Hom_\cA(n,m)$ as an $R$-module.
\item[C-2] For all objects $n,m$, all $\lambda\in\Lambda$ and all
$S\in K(n,\lambda)$, $T\in K(m,\lambda)$ we have
\[ \left(C^\lambda_{S,T}\right)^*=C^{\lambda}_{T,S} \]
\item[C-3] For all objects $p,n,m$, all $\lambda\in\Lambda$ and all
$a\in \Hom_\cA(p,n)$,
$S\in K(n,\lambda)$, $T\in K(m,\lambda)$ we have
\[ aC^\lambda(S,T)=\sum_{S^\prime\in K(p,\lambda)}
r_a(S^\prime,S)C^\lambda_{S^\prime ,T}
\mod \cA(<\lambda) \]
where $r_a(S^\prime,S)\in R$ is independent of $T$ and
$\cA(<\lambda)$ is the $R$-linear span of
\[ \left\{ C^\mu_{S,T} | \mu < \lambda ; S\in K(p,\mu),T\in K(m,\mu)
\right\} \]
\end{enumerate}
\end{defn}
Another way of formulating C-3 is that for all objects
$p,n,m$, all $\lambda\in\Lambda$ and all
$S\in K(p,\lambda)$,$T\in K(n,\lambda)$,
$U\in K(n,\lambda)$,$V\in K(m,\lambda)$ we have
\[ C^\lambda(S,T)C^\lambda(U,V)=\langle T,U\rangle C^\lambda_{S,V}
\mod \cA(<\lambda) \]
where $\langle T,U\rangle$ is independent of $S$ and $V$.

A consequence of this definition is that for all order ideals
$\pi\subset\Lambda$ we have an ideal $\cA(\pi)$ where
for all objects $n,m$ the subspace $\cA(\pi)(n,m)$ is the
$R$-linear span of
\[ \left\{ C^\mu_{S,T} | \mu\in\pi ; S\in K(n,\mu),T\in K(m,\mu) \right\} \]

This is a generalisation of the definition of a cellular algebra
since we can regard any algebra over $R$ as an $R$-linear category
with one object.

More significantly, if $\cA$ is a cellular category then $\End(n)$
is a cellular algebra for any object $n$ of $\cA$.

A functor $\phi\colon\cA\rightarrow\cA^\prime$ between cellular categories
is cellular if we have a map of partially ordered sets
$\phi\colon \Lambda\rightarrow\Lambda^\prime$ such that for any order
ideal $\pi\in\Lambda$ we have $\phi(O(\pi))\subset O(\phi(\pi))$.

One reason for considering cellular categories instead of just
the cellular endomorphism algebras is that for each object $n$
and each order ideal $\pi\subset\Lambda$ we have an $R$-linear functor
$\rho(n;\pi)$ from $\cA$ to the category of left
$\End_\cA(n)$-modules which on objects is given by
\[ \rho(n;\pi)\colon m\mapsto \Hom_{\cA(\pi)}(n,m) \]
Furthermore if $\pi\subset\pi^\prime$ then we have a natural transformation
from $\rho(n;\pi)$ to $\rho(n;\pi^\prime)$. This is used
in \cite{MR1659204}.

\section{Canonical bases}
The rest of the paper is based on \cite[Part IV]{MR1227098}.
In particular all references are to this book and we have tried
to use notation which is the same as or compatible with the
notation in this book.

Let $C$ be a Cartan matrix of finite type and let $U$ be the
Drinfeld-Jimbo quantum group associated to $C$. This is a Hopf
algebra over the field $\bQ(v)$. The integral weight lattice is denoted
by $X$ and the dominant integral weights are denoted by $X^+$.
For each $\lambda\in X^+$ there is a finite dimensional representation
of $U$ with highest weight $\lambda$; we denote this representation
by $V_\lambda$. This representation has a canonical basis which we denote
by $B_\lambda$. There is an anti-involution, $\omega$, of the
$\bQ(v)$-algebra $U$. This induces a duality on representations
which we denote by $M\mapsto {}^\omega M$. Then
${}^\omega V_\lambda\cong V_{-w_o\lambda}$ where $w_0$ is the
longest element of the Weyl group so we put ${}^\omega\lambda = -w_0\lambda$.

A based module is defined in \cite[27.1.2]{MR1227098}. Here we
consider a category $\cB$. The objects are the based modules.
Let $(M,B)$ and $(M^\prime,B^\prime)$ be based modules. Then a
morphism $(M,B)\rightarrow (M^\prime,B^\prime)$ is a homomorphism
of $U$-modules $\phi\colon M\rightarrow M^\prime$ which maps
$B$ to the $\bZ[v,v^{-1}]$-module generated by $B^\prime$ and
which is compatible with the involutions in the sense that
$\overline{\phi(m)}=\phi(\overline{m})$ for all $m\in M$.

Put $\delta=v+v^{-1}$. Then observe that $\bZ[\delta]$ is the
subring of $\bZ[v,v^{-1}]$ fixed by the bar involution. Then
it is clear that $\cB$ is a $\bZ[\delta]$-linear category.
Then \cite[27.3]{MR1227098} constructs a tensor product of based modules
and shows that this makes $\cB$ a monoidal category.
Let $(M,B)$ and $(M^\prime,B^\prime)$ be based modules. Then the
tensor product is the
based module $(M\otimes M^\prime, B\diamond B^\prime)$.

For each $\lambda\in X^+$ we have a based module $(V_\lambda ,B_\lambda)$
where $B_\lambda$ is the canonical basis of $V_\lambda$. Furthermore
\cite[Proposition 21.1.2]{MR1227098} says that there is also a based module
$({}^\omega V_\lambda,{}^\omega B_\lambda)$. Let $\cT$ be the full
subcategory of $\cB$ whose objects are finite tensor products of based
modules isomorphic to these based modules. Then, by construction, $\cT$ is  a
$\bZ[\delta]$-linear monoidal subcategory of $\cB$. This category is also closed under
the duality $\omega$ and is in fact a spherical category, as defined in
\cite{MR1686423}.

Then we show that the $\bZ[\delta]$-linear category $\cT$ with the
anti-involution $\omega$ is a cellular category. The poset $(\Lambda,<)$
is the poset $(X^+,>)$.

If $(M,B)$ is a based module \cite[27.2.1]{MR1227098}
gives a partition of $B$ into subsets $B[\lambda]$.
Furthermore \cite[27.2.5]{MR1227098} shows that $B[0]$ can be regarded
as a base for the space of coinvariants of $M$.
There is a canonical identification of $\Hom_U(M,M^\prime)$ with the
dual of the space of coinvariants of $M\otimes {}^\omega M^\prime$.
Hence we may regard $(B\diamond {}^\omega B^\prime)[0]$ as a basis
of $\Hom(M,M^\prime)$.

The subsets $B[\lambda]^{hi}\subset B[\lambda]$ and $B[\lambda]^{lo}\subset B[\lambda]$
are defined in \cite[27.2.3]{MR1227098}
and \cite[Proposition 27.2.6]{MR1227098} says that for $\lambda=0$
both of these inclusions are bijections.

Let $(M,B)$  be an object of
$\cT$. Then we define the cells by
\[ K((M,B),\lambda)=B[\lambda]^{hi} \]

The map $C$ is defined by
\[ C\colon (b,b^\prime)\mapsto  b\diamond {}^\omega b^\prime \]

This gives cell datum and it remains to check that this satisfies the conditions for
a cellular category. The condition C-2 holds by construction.

The partition of $(B\diamond B^\prime)[0]$ as
\[ (B\diamond B^\prime)[0] = \cup_{\mu\in X^+}
\{ b\diamond b^\prime |
b\in B[-w_0(\mu)]^{lo},b^\prime\in B^\prime[\mu]^{hi} \} \]
is given in \cite[Proposition 27.3.8]{MR1227098}.
This shows that condition C-1 holds.

It remains to discuss C-3. This condition holds modulo an ideal $I$.
This means that, for any $M$, that we can replace $M$ by $M/MI$ and
so we assume that $MI=0$. Equivalently we assume that $M[>\lambda]=0$.

By \cite[27.2.4]{MR1227098}, each $b\in B[\lambda]^{hi}$
gives a homomorphism of based modules $\left| b\right\rangle
\colon (M,B)\rightarrow (V_\lambda,B_\lambda)$. Then
$b\diamond {}^\omega b^\prime\colon (M,B)\rightarrow (M^\prime,B^\prime)$
is the composite of the two maps
\[ \left| b\right\rangle
\colon (M,B)\rightarrow (V_\lambda,B_\lambda) \qquad
\left\langle {}^\omega b^\prime\right| \colon (V_\lambda,B_\lambda)
\rightarrow (M^\prime ,B^\prime ) \]
and so we have $b\diamond {}^\omega b^\prime=
\left| b\right\rangle\left\langle {}^\omega b^\prime\right|$.

Now $\End((V_\lambda,B_\lambda))$ is a free $\bZ[\delta]$-module
with basis the identity map $1_\lambda$.


TITLE: Find the upper and lower Riemann sums $U(f,P)$ and $L(f,P)$ for discontinuous function
QUESTION [1 upvotes]: I know how to find these sums for continuous functions but I don't understand how they work for discontinuous functions. I'm getting the Riemann sums as $U(f,P)=\frac{3}{4}$ and $L(f,P)=\frac{1}{4}$ but this seems to disregard when $x$ is irrational.
Let $f(x)$ on $[0,1]$ be defined by
\begin{equation} f(x)= \left\{ \begin{array}{cc} x & \text{if} & x \quad \text{rational}\\\\ 0 & \text{if} & x \quad \text{irrational}\\ \end{array} \right. \end{equation}
Find $U(f,P)$ and $L(f,P)$ where P is the partition $\left\{0,\displaystyle\frac{1}{2}, 1\right\}$

REPLY [0 votes]: The piecewise function is a test for rationality.
The lower sum of some function f with respect to its partition P, $L(P,f)$ is defined as the sum of all non overlapping rectangular units contained by the function's area and the line $y=0$, created by partitioning some bounded interval.
If we define $m_i=inf\left\{f(x):x\in [x_{i-1},x_i]\right\}$ for $i = 1,2,...,n$, then the lower sum $L(P,f)$ is defined as:
$$\sum_{k=1}^nm_i(x_i-x_{i-1}) $$
So, considering your given function, x takes on irrational values much more often than it does rational, as the reals is more densely covered with irrationals than rationales. So $L(P,f)=0$
If we define $M_i=sup\left\{f(x):x\in [x_{i-1},x_i]\right\}$ for $i = 1,2,...,n$, then the upper sum $U(P,f)$ is defined as:
$$\sum_{k=1}^nM_i(x_i-x_{i-1}) $$
When x is rational, its mapping $x\rightarrow x$ has identical input and output function values. This is analogous to the function $f(x)=x$, for $x\in \mathbb{Q}.$
So if we partition a set into two subintervals with three distinct elements $P=\left\{0,\frac 12, 1\right\}$ and because x is bounded by the interval $[0,1]$ as specified, the upper sum is as follows:
$$U(P,f)=\sum_{k=1}^nM_i(x_i-x_{i-1}) =1(1- \frac 12)+ \frac 12(\frac 12-0)=\frac 34.$$
The upper sum takes on this value for the specified partition, because when x is rational, the function increases monotonically on the interval $[0,1]$.


text:
\begin{document}
\maketitle

\begin{abstract}
A semiprime is a natural number which can be written as the
product of two primes. The asymptotic behaviour of the
function $\pi_2(x)$, the number of semiprimes less than or
equal to~$x$, is studied. Using a combinatorial argument,
asymptotic series of $\pi_2(x)$ is determined, with all
the terms explicitly given. An algorithm for the calculation
of the constants involved in the asymptotic series
is presented and the constants are computed to
20 significant digits. The errors of the partial sums of the
asymptotic series are investigated. A generalization of
this approach to products of $k$ primes, for $k\geq 3$, is also
proposed.
\end{abstract}

\section{Introduction}

\noindent
For a positive integer $k$ and a positive integer (or real number)
$x$, let $\pi_k(x)$  be the number of integers less than or
equal $x$ which can be written as the product of $k$ prime
factors. The behaviour of $\pi_k(x)$ has been extensively studied
during last two centuries, with the main focus on the case $k=1$,
where $\pi_1(x)$ is the prime counting function, denoted
$\pi(x)$ in the rest of this paper. The prime number theorem
states that $\pi(x) \sim \text{li}(x)$, where the logarithmic
integral function
$\mbox{li}(x)
=
\int_{0}^{x}
\log^{-1} t \; \mbox{d} t
$
can be written as an asymptotic expansion
$
\mbox{li} (x)
\sim
{\frac {x}{\log x}}
\sum _{n=0}^{\infty }{\frac {n!}{(\log x)^{n}}}
$.
Bounds on the error term have been established in the literature,
including the recent work of Trudgian~\cite{Trudgian:2016:AET},
who proved that, for sufficiently large $x$,
\begin{equation*}
\big| \pi(x) - \mbox{li}(x) \big|
\, \leq  \, 0.2795 \,
\frac{x}{(\log x)^{3/4}}
\, \exp\left( -\sqrt{\frac{\log x}{6.455}} \right).
\end{equation*}
This implies the existence of constants $d_1$ and $d_2$ such that
\begin{equation}
\label{ineq_noRH}
\big| \pi(x) - \mbox{li}(x) \big|
\, \leq \, d_1 \,
\frac{x}{(\log x)^{3/4}}
\, \exp\left( - d_2 \sqrt{\log x} \right),
\qquad
\mbox{for all} \; x\geq 2.
\end{equation}
Assuming the Riemann hypothesis, Rosser and
Schoenfeld~\cite{Rosser:1975:SBC,Schoenfeld:1976:SBC} established
even sharper bounds on the error term, including
\begin{equation*}
|\pi(x)-\text{li}(x)| < \frac{\sqrt{x} \log x}{8\pi}
\end{equation*}
for large enough $x$. Other explicit estimates of $\pi(x)$,
in terms of $x$ and $\log x$ are achievable, as proved by
Axler~\cite{Axler:2006:NBP}.

In this paper, we focus on the case $k=2$, where the numbers
written as products of two (not necessarily distinct) primes
are called semiprimes. In this case, Ishmukhametov and
Sharifullina~\cite{Ishmukhametov:2014:DSN} recently
used probabilistic arguments to approximate the behaviour
of $\pi_2(x)$ as
\begin{equation}
\pi_2(x)
\approx
\frac{x \log (\log x)}{\log x}
+
\, 0.265 \, \frac{x}{\log x}
-
\, 1.540 \, \frac{x}{(\log x)^2} \, .
\label{ishsha}
\end{equation}
The first term of~(\ref{ishsha}) has already been known to
Landau~\cite[\S{}56]{Landau:1909:HLV}, with his
result stated, for general $k \in {\mathbb N}$, as
\begin{equation}
\pi_k(x)
\sim
\frac{1}{(k-1)!} \, \frac{x \, (\log (\log x))^{k-1}}{\log x} \, .
\label{landaupoi}
\end{equation}
Delange~\cite[Theorem 1]{Delange:1971:FAS} obtained the asymptotic
expansion of $\pi_k(x)$ in the form
\begin{equation}
\pi_k(x)
\sim
\frac{x}{\log x}
\,
\sum_{n=0}^{\infty}
\frac{P_{n,k} (\log (\log x))}{(\log x)^n} \, ,
\label{delange}
\end{equation}
where $P_{n,k}$ are polynomials of degree $k-1$, with the
leading coefficient equal to $n!/(k-1)! \, .$
Tenenbaum~\cite{Tenenbaum:2015:IAP} proved a similar
result, giving an expression for the coefficients in the
polynomial $P_{0,k}$ in terms of the derivatives of
$
\frac{1}{\Gamma(z+1)}
\prod_{p} \big( 1 + \frac{z}{p-1} \big)
\big( 1 - \frac{1}{p} \big)^{\! z}
$
evaluated at $z=0$.
Considering $k=2$ in (\ref{delange}), we can write
an asymptotic expansion for $\pi_2(x)$ as
\begin{equation}
\pi_2 (x)
\sim
\sum_{n=1}^{\infty} (n-1)! \,
\frac{x \log(\log x)}{(\log x)^n}
+
\sum_{n=1}^{\infty} C_{n-1} \, \frac{x}{(\log x)^n} \, .
\label{aspi2}
\end{equation}
In Theorem~\ref{theoremM}, we prove that $C_0 = M$,
where $M = 0.261497...$ is the Meissel--Mertens constant
defined by
\begin{equation}
M
=
\lim_{x\rightarrow \infty}
\Bigg(
\sum_{p\leq x} \, \frac{1}{p}
\, - \, \log (\log x)
\Bigg),
\label{defMMcon}
\end{equation}
where we sum over all primes such that $p \le x.$
In Section~\ref{sectionCkcomp},
we calculate the rest of constants $C_n$
appearing in equation~(\ref{aspi2}).
They are given in Table~\ref{tablecbk} and obtained
by the formula
\begin{equation}
C_n
=
n! \; \Bigg(
\sum_{i=0}^{n} \frac{B_i}{i!} - \sum_{i=1}^{n} \frac{1}{i}
\Bigg)
=
n! \; \Bigg(
\sum_{i=0}^{n} \frac{B_i}{i!} - H_i
\Bigg),
\label{constCk}
\end{equation}
where $H_i$ is the $i$-th harmonic number, $B_0 = M$ and
constants $B_i$ are defined using the asymptotic behaviour
of sums~\cite[\S{}56]{Landau:1909:HLV}
\begin{equation}
\sum_{p\leq x} \frac{(\log p)^i}{p}
=
\frac{(\log x)^i}{i} + B_i + \bigO
\! \left( e^{-\sqrt[14]{\log x}} \right),
\qquad
\mbox{for} \; i \in {\mathbb N}.
\label{landaulog}
\end{equation}
Constants $B_i$ are given as limits~(\ref{constBklimit}) in
Section~\ref{sectionCkcomp}, where we present an algorithm
to efficiently calculate them to a desired accuracy. They are
computed in Table~\ref{tablecbk} to 20 significant digits.
Rosser and Schoenfeld~\cite{Rosser:1962:AFS} prove that
the error term in (\ref{landaulog}) can be given explicitly
in terms of an integral, which contains the error terms in
the prime number theorem. For the case $i=1$ in
equation~(\ref{landaulog}), explicit estimates of this
sum and, in particular, of the constant $B_1$ involved,
were recently obtained by Dusart~\cite{Dusart:2018:EES}.

A related arithmetic function, $\Omega(m)$, is defined to
be the number of prime divisors of $m \in {\mathbb N}$,
where prime divisors are counted with their multiplicity.
Considering fixed $x$ in equation~(\ref{landaupoi}), we
can view this approximation of $\pi_k(x)/x$ as the
probability mass function of the Poisson distribution
with mean $\log(\log(x)).$ Erd\H{o}s and Kac~\cite{Erdos:1940:GLE}
showed that the distribution of $\Omega(x)$ is Gaussian with
mean $\log(\log(x))$ (see also R\'enyi and
Tur\'an~\cite{Renyi:1958:TEK} and Harper \cite{Harper:2008:TNP} for
generalizations and better bounds). Diaconis~\cite{Diaconis:1976:AEM}
obtained the asymptotic expansions for the average number of
prime divisors as (see also Finch~\cite[Section 1.4.3]{Finch:2018:MC2})
\begin{equation}
\frac{1}{x} \sum_{m \le x}
\Omega(m)
\, \sim \,
\log (\log x)
+
1.0346538818\dots
+
\sum_{n=1}^\infty
\left(
- 1
+
\sum_{i=0}^{n-1}
\frac{\gamma_i}{i!}
\right)
\frac{(n-1)!}{\log^n x} \, ,
\label{defOmegaLarge}
\end{equation}
where the constants $\gamma_i$ are the Stieltjes constants,
numerically computed in \cite{Bohman:1988:SFD} to 20
significant digits. An asymptotic series for the
variance of $\Omega$ have also been
obtained~\cite[Section 1.4.3]{Finch:2018:MC2}. The Stieltjes
constants $\gamma_i$ are used in Section~\ref{sectionCkcomp}
during our calculation of the values of constants $B_n$ and
$C_n$, for $n \in {\mathbb N}.$

This paper is organized as follows. Section \ref{k=2} begins
with a counting lemma for expressing the semiprime counting
function $\pi_2$ in terms of the prime counting function $\pi$.
Using this lemma, the main results on the asymptotic
behaviour of $\pi_2$ are stated and proved in Section~\ref{k=2}
as Theorem~\ref{theoremM} and Theorem~\ref{theoremgen}.
While Theorem~\ref{theoremM} only gives the first two terms,
its proof is more coincise than the proof
of Theorem~\ref{theoremgen}, which
gives the full asymptotic series of $\pi_2$. The constants
$C_n$ which appear in this asymptotic series are computed in
Section~\ref{sectionCkcomp}, where we present an efficient approach to calculate both constants $B_n$ and $C_n$,
based on the differentiation of the prime zeta function. In Section~\ref{sectionerrorterms}, we
investigate the behaviour of the error terms given by
the partial sums of the asymptotic series of $\pi_2$. We conclude
with a generalization of the counting argument in
Section~\ref{secdiscussion}, discussing the extensions of the
presented results to the general case of counting
functions $\pi_k$ for $k\geq 3$.

\section{Asymptotic behaviour of the counting function
of semiprimes}
\label{k=2}

\noindent
As in equation (\ref{defMMcon}), we denote primes by
$p$ and the sums over $p$ shall be understood as sums over
all primes satisfying the given condition.
In the case of summing over primes twice, we
denote the corresponding prime summation indices
by $p_1$ and $p_2$.
We begin with a simple counting
formula~\cite{Ishmukhametov:2014:DSN},
that gives a way of computing $\pi_2 (x)$.

\begin{lemma}
\label{counting_pi2}
For a positive integer $x$, the following holds
\begin{equation}
\pi_2(x)
=
\frac{\pi(\sqrt{x}) - \pi(\sqrt{x})^2}{2}
\,
+
\sum_{p\leq \sqrt{x}}
\pi \! \left(\frac{x}{p}\right).
\label{countformpi2}
\end{equation}
\end{lemma}

\begin{proof} \noindent
By the definition of counting functions
$\pi_2$ and $\pi$, we have
$$
\pi_2(x)
=
\sum_{\substack{p_1\leq p_2\\ p_1 p_2 \leq x}}
\! \! 1
\;
=
\sum_{p_1 \leq \sqrt{x}}
\,
\sum_{p_1 \leq p_2 \leq \frac{x}{p_1}}
\! \!
1
\;
=
\sum_{p_1 \leq \sqrt{x}}
\left(
\pi \! \left( \frac{x}{p_1} \right) - \pi(p_1) + 1
\right)
$$
and formula~(\ref{countformpi2}) follows by renaming
$p_1$ to $p$ in the first term and observing that the rest
of the right hand side is the sum of
all natural numbers from 1 up to $\pi(\sqrt{x})-1.$
\end{proof}

\noindent
Formula~(\ref{countformpi2}) gives an expression of $\pi_2(x)$
in terms of the prime counting function $\pi(x),$ which
can be approximated using the prime number
theorem~\cite{Tenenbaum:2015:IAP} as
\begin{equation}
\pi(x)
=
\alpha_n (x)
+
\bigO \! \left( \frac{x}{(\log x)^{n+1}} \right),
\label{PNT}
\end{equation}
where $n \in {\mathbb N}$ and
\begin{equation}
\alpha_n(x)
=
\frac{x}{\log x}
\left(
\,
\sum_{i=0}^{n-1}
\frac{i!}{(\log x)^i}
\right).
\label{notationalphak}
\end{equation}
Using Landau~\cite[\S{}56]{Landau:1909:HLV}, we
can rewrite equation~(\ref{defMMcon}) for any
integer $n \in {\mathbb N}$ as
\begin{equation}
\sum_{p\leq \sqrt{x}} \frac{1}{p}
=
\log (\log x) - \log 2 + M +
o\left( \frac{1}{(\log x)^n}\right),
\label{sqrtMform}
\end{equation}
where we use the little $o$ asymptotic
notation~\cite{deBruijn:1958:AMA}, as opposed
to the big $\bigO$ asymptotic notation used in
the prime number theorem~(\ref{PNT}). First we use
this result to approximate the sum on the right
hand side of equation~(\ref{countformpi2}).

\begin{lemma}
\label{pi_to_alphas}
Let $n \in {\mathbb N}$ and $\alpha_n(x)$ be defined
by~$(\ref{notationalphak})$. Then we have
\begin{equation}
\label{sum_pi_to_sum_alphas}
\sum_{p\leq \sqrt{x}}
\pi \! \left(\frac{x}{p}\right)
=
\sum_{p\leq \sqrt{x}}
\alpha_n \! \left(\frac{x}{p}\right)
+
\bigO \!
\left(
\frac{x \log(\log x)}{(\log x)^{n+1}}
\right).
\end{equation}
\end{lemma}

\begin{proof}
Using equation~(\ref{PNT}), we have
$$
\left|
\sum_{p\leq \sqrt{x}}
\pi \! \left(\frac{x}{p}\right)
-
\sum_{p\leq \sqrt{x}}
\alpha_n \! \left(\frac{x}{p}\right)
\right|
\, \leq
\sum_{p\leq \sqrt{x}}
\left|
\pi \! \left(\frac{x}{p}\right)
-
\alpha_n \! \left(\frac{x}{p}\right)\right|
\, \leq \,
c \,
x \sum_{p\leq \sqrt{x}} \frac{1}{p \, (\log x - \log p)^{n+1}}
\;,
$$
where $c>0$ is a constant.
Equation~(\ref{sum_pi_to_sum_alphas}) then follows
by estimating the right hand side by
$$
\frac{c \, x \, 2^{n+1}}{(\log x)^{n+1}} \sum_{p\leq \sqrt{x}} \frac{1}{p}
=
\bigO \! \left( \frac{x \log(\log x)}{(\log x)^{n+1}} \right),
$$
where the last equality follows from
equation~(\ref{sqrtMform}).
\vskip -4mm
\end{proof}

\subsection{The first two terms of the asymptotic
series for $\pi_2(x)$}
\label{k=2_first_terms}

\noindent Using~(\ref{sum_pi_to_sum_alphas}) for $n=1$,
we obtain
\begin{equation}
\sum_{p\leq \sqrt{x}} \pi \! \left(\frac{x}{p}\right)
=
\sum_{p\leq \sqrt{x}} \frac{x}{p \, (\log x - \log p)}
+
\bigO \! \left( \frac{x \log(\log x)}{(\log x)^2 } \right).
\label{kis1sumform}
\end{equation}
Using Landau~\cite[\S{}56]{Landau:1909:HLV}, we can
rewrite equation~(\ref{landaulog})
for any integers $i \in {\mathbb N}$
and $n \in {\mathbb N}$ as
\begin{equation}
\sum_{p\leq \sqrt{x}}
\frac{(\log p)^i}{p}
=
\frac{(\log x)^i}{i \, 2^i}
+
B_i
+
o
\left( \frac{1}{(\log x)^n}\right).
\label{constBk}
\end{equation}
We will use this to prove the first theorem of this section.

\begin{theorem}
\label{theoremM}
Let $M$ be the Meissel--Mertens constant defined by
$(\ref{defMMcon})$. Then
\begin{equation}
\label{pi_2_first_two_terms}
\pi_2 (x)
=
\frac{x \log (\log x)}{\log x}
+
M {\hskip 0.1mm} \frac{x}{\log x}
+
o\left( \frac{x}{\log x}\right).
\end{equation}
\end{theorem}

\begin{proof}
Using equations~(\ref{countformpi2}),
(\ref{PNT}) for $n=1$, and
(\ref{kis1sumform}), we obtain
\begin{equation}
\label{pi_2_first_two_terms_computations}
\pi_2(x)
=
\sum_{p\leq \sqrt{x}}
\pi \! \left(\frac{x}{p}\right)
+ o \left( \frac{x}{\log x}\right)
=
\frac{x}{\log x}
\sum_{p\leq \sqrt{x}} \frac{\log x}{p \, (\log x - \log p)}
+ o\left( \frac{x}{\log x}\right).
\end{equation}
We have the following identity
$$
\frac{\log x}{p \, (\log x - \log p)}
=
\frac{1}{p}
+
\frac{\log p}{\log x}
\left(
\frac{\log x}{p \, (\log x - \log p)}
\right).
$$
Substituting the left hand side into the right hand side,
we obtain, for any natural number $n \in {\mathbb N}$,
that
$$
\frac{\log x}{p \, (\log x - \log p)}
=
\frac{1}{p}
\sum_{i=0}^n
\left(
\frac{\log p}{\log x}
\right)^{\!\!i}
\, + \,
\left(
\frac{\log p}{\log x}
\right)^{\!\!n+1}
\!
\left(
\frac{\log x}{p \, (\log x - \log p)}
\right).
$$
Summing over all primes $p \le \sqrt{x}\,$, we get
\begin{equation*}
\sum_{p\leq \sqrt{x}}
\frac{\log x}{p \, (\log x - \log p)}
=
\sum_{i=0}^n \left( \frac{1}{(\log x)^{i}}
\sum_{p\leq \sqrt{x}} \frac{(\log p)^i}{p}
\right)
+
\frac{1}{(\log x)^{n}} \sum_{p\leq \sqrt{x}}
\frac{(\log p)^{n+1}}{p \, (\log x - \log p)}.
\end{equation*}
Each term on the right hand side can be evaluated
using equations~(\ref{sqrtMform}) and~(\ref{constBk}),
with $o(1)$ accuracy, as
\begin{equation}
\sum_{p\leq \sqrt{x}}
\frac{\log x}{p \, (\log x - \log p)}
=
\log(\log x)
- \log 2
+
M
+
\sum_{i=1}^n
\frac{1}{i \, 2^i}
+
f(n)
+
o(1) {\hskip 0.2mm} ,
\label{intermform}
\end{equation}
where $f(n)$ is a decreasing function of $n$ satisfying
$f(n) \to 0$ as $n \to \infty$. This can be deduced by
applying equation~(\ref{constBk}) to the error term
$$
\frac{1}{(\log x)^{n}}
\sum_{p\leq \sqrt{x}}
\frac{(\log p)^{n+1}}{p \, (\log x - \log p)}
\leq
\frac{2}{(\log x)^{n+1}}
\sum_{p\leq \sqrt{x}} \frac{(\log p)^{n+1}}{p}
=
\frac{1}{(n+1) \, 2^n}
+
o(1).
$$
Since we have
$$
-
\log 2
+
\sum_{i=1}^n
\frac{1}{i \, 2^i}
+
f(n)
\to
0,
\qquad
\mbox{as}
\quad
n \to \infty,
$$
equation~(\ref{intermform}) implies that
$$
\sum_{p\leq \sqrt{x}}
\frac{\log x}{p \, (\log x - \log p)}
=
\log(\log x)
+
M
+
o(1).
$$
Substituting into
equation~(\ref{pi_2_first_two_terms_computations}),
we obtain formula~(\ref{pi_2_first_two_terms}).
\end{proof}

\subsection{Asymptotic series for the counting
function of semiprimes}
\label{k=2_complete_series}

\noindent To derive formulas for all terms in the asymptotic
series of $\pi_2$, we first define an auxiliary sequence of
numbers $q_n$ for $n \in {\mathbb N}$ by
\begin{equation}
q_n
=
\sum_{i=1}^{n-1}
\frac{2^{i}-1}{i},
\quad
\mbox{for}
\; \; n \ge 2,
\qquad
\mbox{and}
\qquad
q_1=0 \, .
\label{defqn}
\end{equation}
Then $q_n$ is an increasing sequence of rational numbers
with the first few terms given
as $q_1 = 0,$ $q_2 = 1$, $q_3 = 5/2$, $q_4 = 29/6$,
$q_5 = 103/12$ and $q_6 = 887/60$, which satisfies
the following identity.

\begin{lemma}
\label{lemmaqn}
Let $n \in {\mathbb N}$ and let $q_n$ be given
by equation~$(\ref{defqn})$. Then we have
\begin{equation}
\label{qnidentity}
\sum_{i=1}^{\infty}
\binom{n+i-1}{n-1} \, \frac{1}{i \, 2^i}
=
q_n + \log 2 \, .
\end{equation}
\end{lemma}

\begin{proof}
Considering the binomial series
\begin{equation*}
(1-t)^{-n}
=
1 + t \, \sum_{i=0}^{\infty}
\binom{n+i}{n-1} \, t^i,
\qquad
\mbox{for} \; t\in(-1,1),
\end{equation*}
we can rewrite it as
$$
\sum_{i=0}^{\infty} \binom{n+i}{n-1} \, t^i
=
\frac{(1-t)^{-n}-1}{t}
=
\sum_{i=1}^n
(1-t)^{-i}.
$$
Integrating, we get
\begin{equation*}
\sum_{i=0}^{\infty}
\binom{n+i}{n-1} \, \frac{t^{i+1}}{i+1}
=
-
\log(1-t)
+
\sum_{i=2}^n
\frac{(1-t)^{-i+1}-1}{i-1},
\end{equation*}
which holds for $t\in(-1,1)$.
Substituting $t=1/2$, we obtain (\ref{qnidentity}).
\end{proof}

\noindent
We will use Lemma~\ref{lemmaqn} in the proof of the following
theorem, giving the asymptotic series for the semiprime
counting function $\pi_2(x).$

\begin{theorem}
\label{theoremgen}
The constants $C_n$ appearing in the asymptotic
expansion~$(\ref{aspi2})$ are given
by equation~$(\ref{constCk})$ for $n \in {\mathbb N}$
and as $C_0 = B_0 = M$ for $n=0.$
\end{theorem}

\begin{proof}
\noindent
The case $n=0$ is studied in Theorem~\ref{theoremM}, which
states that $C_0 = M.$ To derive equation~(\ref{constCk}),
we again use formula~(\ref{countformpi2}) from
Lemma~\ref{counting_pi2} and approximate each term
using the prime number theorem~(\ref{PNT}). We
need to analyze sums of the form
\begin{equation}
S_n(x)
=
\sum_{p\leq \sqrt{x}}
\frac{(\log x)^n}{p \, (\log x - \log p)^n}
=
\sum_{p\leq \sqrt{x}}
\frac{1}{p}
\left( 1-\frac{\log p}{\log x}\right)^{\!\!-n} \!\! .
\label{defSnx}
\end{equation}
Using the binomial series on the right hand side, we get
\begin{equation}
S_n(x)
\, = \,
\sum_{p\leq \sqrt{x}}
\frac{1}{p}
\sum_{i=0}^{\infty} \binom{n+i-1}{n-1}
\left( \frac{\log p}{\log x}\right)^{\!\!i}
\, = \,
\sum_{i=0}^{\infty} \binom{n+i-1}{n-1}
\frac{1}{(\log x)^i} \sum_{p\leq \sqrt{x}}
\frac{(\log p)^i}{p} \, . \;\;
\label{S_k_formula0}
\end{equation}
Substituting $x^2$ for $x$, we obtain
\begin{equation}
\label{S_k_formula1}
S_n(x^2)
=
\sum_{i=0}^{\infty} \binom{n+i-1}{n-1}
\frac{1}{2^i (\log x)^i} \sum_{p\leq x}
\frac{(\log p)^i}{p} \, .
\end{equation}
To estimate the sums over primes on the right hand side,
we apply the result of Rosser and
Schoenfeld~\cite[equation (2.26)]{Rosser:1962:AFS},
which can be formulated as
$$
\sum_{p\leq x} \frac{1}{p} = \log (\log x) + \bigL_0(x),
\qquad
\sum_{p\leq x}
\frac{(\log p)^i}{p} = \frac{(\log x)^i}{i} + \bigL_i(x),
$$
where the error terms $\bigL_i(x)$ are defined by
\begin{eqnarray*}
\bigL_0(x) &=&
-
\log(\log 2)
+
\frac{\mbox{li}(2)}{2}
+
\frac{\pi(x) - \mbox{li}(x)}{x}
+
\int_2^{x}
\frac{\pi(y) - \mbox{li}(y)}{y^2} \,
\mbox{d}y,
\\
\bigL_i(x) &=&
-
\frac{(\log 2)^i}{i}
+
\frac{(\log 2)^i \, \mbox{li}(2)}{2}
+ \frac{(\log x)^i}{x} \big( \pi(x) - \mbox{li}(x) \big) \\
&&
+ \, \int_2^{x}
\frac{(\log y-i) \,
(\log y)^{i-1}}{y^2}
\big( \pi(y) - \mbox{li}(y) \big) \,
\mbox{d}y,
\qquad \mbox{for} \; i \in {\mathbb N}.
\end{eqnarray*}
Using this notation and identity~(\ref{qnidentity})
in Lemma~\ref{lemmaqn}, we rewrite
equation~(\ref{S_k_formula1}) as
\begin{equation}
\label{S_k_formula2}
S_n(x^2)
=
\log (\log x)
+
q_n
+
\log(2)
+
\sum_{i=0}^{\infty} \binom{n+i-1}{n-1}
\frac{1}{2^i}
\frac{\bigL_i(x)}{(\log x)^i} \, .
\end{equation}
Using the inequality (\ref{ineq_noRH}), there exist
constants $d_1$ and $d_2$ such that
\begin{eqnarray}
\left|\frac{\bigL_i(x)}{(\log x)^i} \right|
&<&
\frac{2}{(\log x)^i}
+
\frac{\left| \pi(x) - \mbox{li}(x) \right|}{x}
+
\frac{1}{(\log x)^i}
\int_2^{x}
\frac{|i - \log y| \, (\log y)^{i-1}}{y^2}
\big| \pi(y) - \mbox{li}(y) \big| \, \mbox{d}y
\nonumber
\\
&\leq&
\frac{2}{(\log x)^i}
+
d_1 \,
\frac{
\exp\left(
- d_2 \sqrt{\log x} \right)
}{(\log x)^{3/4}}
+
\frac{i
\, I(i-1,x)
+
I(i,x)}{(\log x)^i} \, ,
\label{estimateLi}
\end{eqnarray}
where we define
(note that we allow the second argument to be $\infty$ in this definition):
$$
I(i,x)
=
d_1
\int_2^{x}
(\log y)^{i-3/4} \,
\frac{
\exp\left( -d_2 \sqrt{\log y}
\right)}{y} \, \mbox{d}y \, .
$$
Choose $\ell \in {\mathbb N}$. Our goal is to use
(\ref{estimateLi}) to estimate the rate of
convergence of the sum on the right hand of
equation~(\ref{S_k_formula2}). To do this we
first observe that, for $i \ge \ell$,
we have
\begin{equation}
\frac{
I(i,x)}{(\log x)^i}
\le
\frac{d_1}{(\log x)^\ell}
\int_2^{x}
(\log y)^{\ell-3/4} \,
\frac{
\exp\left( -d_2 \sqrt{\log y}
\right)}{y} \, \mbox{d}y
\le
\frac{I(\ell,\infty)}{(\log x)^\ell} \,.
\label{Iiellineq}
\end{equation}
Using inequalities~(\ref{estimateLi})
and~(\ref{Iiellineq}) and assuming $\log(x) \ge 1$,
we can estimate the remainder
of the series on the right hand of
equation~(\ref{S_k_formula2}) as
\begin{eqnarray*}
&& \left|
\sum_{i=\ell+1}^{\infty}
\binom{n+i-1}{n-1}
\frac{1}{2^i}
\frac{\bigL_i(x)}{(\log x)^i}
\right|
\; \leq \;
\left(
\frac{2}{(\log x)^{\ell+1}}
+
d_1 \,
\frac{
\exp\left(
- d_2 \sqrt{\log x} \right)
}{(\log x)^{3/4}}
\right)
\sum_{i=\ell+1}^{\infty}
\binom{n+i-1}{n-1}
\frac{1}{2^{i}}
\\
&&
\hskip 2cm
+
\;
\frac{
\, I(\ell,\infty)
}{(\log x)^{\ell+1}}
\sum_{i=\ell+1}^{\infty}
\binom{n+i-1}{n-1}
\frac{i}{2^i}
\;
+
\;
\frac{I(\ell+1,\infty)}{(\log x)^{\ell+1}}
\sum_{i=\ell+1}^{\infty}
\binom{n+i-1}{n-1}
\frac{1}{2^i} \,.
\end{eqnarray*}
Since all three sums on the right hand side converge
independently of $x$, we deduce that the
remainder is of the order
$\bigO \big( (\log x)^{-(\ell+1)}) \big)$.
Therefore, equation~(\ref{S_k_formula2}) becomes
\begin{equation*}
S_n(x^2)
=
\log (\log x)
+
q_n
+
\log(2)
+
\sum_{i=0}^{\ell} \binom{n+i-1}{n-1}
\frac{1}{2^i}
\frac{\bigL_i(x)}{(\log x)^i}
+
\bigO\left( \frac{1}{(\log x)^{\ell+1}} \right).
\end{equation*}
This means that an asymptotic expansion of
$S_n(x^2)$ in terms of negative powers of
$\log x$ is given by the sum of the asymptotic
series of terms in equation~(\ref{S_k_formula1}).
The same is true for $S_n(x)$ in
equation~(\ref{S_k_formula0}). Thus, using
equations~(\ref{sqrtMform}), (\ref{constBk}),
(\ref{qnidentity}) and~(\ref{S_k_formula0}),
we obtain
\begin{eqnarray}
S_n(x)
&=&
\sum_{i=0}^{\ell} \binom{n+i-1}{n-1}
\frac{1}{(\log x)^i} \sum_{p\leq \sqrt{x}}
\frac{(\log p)^i}{p}
+
\bigO\left( \frac{1}{(\log x)^{\ell+1}} \right)
\nonumber
\\
&=&
\log(\log x)
+
M
+
q_n
+
\sum_{i=1}^{\ell}
\binom{n+i-1}{n-1} \, \frac{B_i}{(\log x)^i}
+
\bigO\left( \frac{1}{(\log x)^{\ell+1}} \right).
\label{Siasympt}
\end{eqnarray}
Using equations~(\ref{notationalphak})
and~(\ref{sum_pi_to_sum_alphas}),
we have
\begin{equation*}
\sum_{p\leq \sqrt{x}}
\pi \! \left(\frac{x}{p}\right)
+
o
\left(\!
\frac{x}{(\log x)^{\ell}}
\!\right)
=
\sum_{n=1}^{\ell}
\sum_{p\leq \sqrt{x}}
\frac{x \, (n-1)!}{p \, (\log x - \log p)^{n}}
=
\sum_{n=1}^{\ell} (n-1)! \,
\frac{x \, S_n(x)}{(\log x)^n} \,,
\end{equation*}
where we used the definition~(\ref{defSnx})
of $S_n(x)$ to get the second equality.
Using equation~(\ref{Siasympt}) and notation
$B_0 = M$, we obtain
\begin{equation*}
\sum_{p\leq \sqrt{x}}
\pi \! \left(\frac{x}{p}\right)
=
\sum_{n=1}^{\ell} (n-1)! \,
\frac{x \log(\log x)}{(\log x)^n}
+
\sum_{n=1}^{\ell} (n-1)!
\left(
q_n
+
\sum_{i=0}^{n-1}
\frac{B_{i}}{i!}
\right)
\frac{x}{(\log x)^n}
+
o
\left(\!
\frac{x}{(\log x)^{\ell}}
\!\right).
\end{equation*}
Thus, using formula~(\ref{countformpi2}) and
the prime number theorem~(\ref{PNT}),
we obtain the asymptotic expansion~(\ref{aspi2}),
where we have
$$
C_{n}
=
n!
\left(
q_{n+1}
+
\sum_{i=0}^{n}
\frac{B_{i}}{i!}
\right)
-
2^{n} \sum_{i=1}^{n} (i-1)! \, (n-i)! \; .
$$
This can be further simplified by using
definition~(\ref{defqn}) of $q_n$. We get
$$
C_n
=
n!
\left(
\sum_{i=1}^{n} \frac{2^i-1}{i}
+
\sum_{i=0}^{n} \frac{B_i}{i!}
-
\frac{2^{n}}{n}
\sum_{i=0}^{n-1}
\frac{1}{\binom{n-1}{i}}
\right)
=
n!
\left(
\sum_{i=1}^{n} \frac{2^i-1}{i}
+
\sum_{i=0}^{n} \frac{B_i}{i!}
-
\sum_{i=1}^{n} \frac{2^{i}}{i}
\right).
$$
Subtracting the first and the third sum, we obtain
(\ref{constCk}).
\end{proof}

\section{Computing the constants}
\label{sectionCkcomp}

\noindent
In this section, we use a fast converging series
to determine the values of the constants $B_n$ and,
as a result, of the constants $C_n$ given by equation
(\ref{constCk}). The first constant, $B_0=C_0=M$,
is the well-studied Meissel--Mertens constant,
so we will focus on constants $B_n$ in the
case $n \geq 1$. They have been
defined by equations~(\ref{landaulog})
or~(\ref{constBk}), which can be rewritten as
\begin{equation}
B_n
=
\lim_{x\rightarrow \infty}
\left(
\sum_{p\leq \sqrt{x}} \frac{(\log p)^n}{p}
- \frac{(\log x)^n}{n \, 2^n}
\right)
=
\lim_{x\rightarrow \infty}
\left(
\sum_{p\leq x} \frac{(\log p)^n}{p}
- \frac{(\log x)^n}{n}\right).
\label{constBklimit}
\end{equation}
To derive a formula for evaluating $B_n$ on a computer,
we use the prime zeta function~\cite{Froberg:1968:PZF}
defined by
\begin{equation}
P(s) = \sum_{p} \frac{1}{p^s} \;,
\qquad \quad
\mbox{for} \; \; s \in (1,\infty).
\label{primezeta}
\end{equation}
Differentiating equation~(\ref{primezeta}), we get
the formula for the $n$-th derivative of the
prime zeta function as
\begin{equation}
P^{(n)}(s)
=
(-1)^n \,
\sum_{p} \frac{(\log p)^n}{p^{s}}
=
(-1)^n \,
\sum_{p \le x} \frac{(\log p)^n}{p^{s}}
+
(-1)^n \,
\sum_{p > x} \frac{(\log p)^n}{p^{s}}.
\label{derprimezeta1}
\end{equation}
The prime zeta function $P(s)$ can also be related to
the Riemann zeta function $\zeta(s)$ through the
formula~\cite{Froberg:1968:PZF}
\begin{equation*}
P(s)
=
\sum_{i=1}^{\infty}
\mu(i)
\,
\frac{\log \big( \zeta(i \, s) \big)}{i}
\, ,
\qquad \quad
\mbox{for} \; \; s \in (1,\infty),
\end{equation*}
where $\mu(n)$ is the M\"obius function. Taking the
derivative of order $n$ of this expression,
we obtain
\begin{equation*}
P^{(n)}(s)
=
\sum_{i=1}^{\infty}
\mu(i)
\,
i^{n-1}
\,
\left(\frac{\zeta'}{\zeta}\right)^{\!\!(n-1)}
\!\!\!\!\!\!\!\!(i \, s) \, .
\end{equation*}
Substituting into (\ref{derprimezeta1}), we obtain
\begin{equation}
\sum_{p \le x} \frac{(\log p)^n}{p^{s}}
=
(-1)^n \,
\sum_{i=1}^{\infty}
\mu(i)
\,
i^{n-1}
\,
\left(\frac{\zeta'}{\zeta}\right)^{\!\!(n-1)}
\!\!\!\!\!\!\!\!(i \, s)
\; - \;
\sum_{p > x} \frac{(\log p)^n}{p^{s}} \, .
\label{fromeqder}
\end{equation}
Using integration by parts, we obtain
$$
\int_{1}^{\infty} \frac{(\log u)^{n-1}}{u^{s}}
\; \mbox{d}u
=
\frac{(n-1)!}{(s-1)^n}
=
-
\left(
\frac{(-1)^n}{s-1}
\right)^{\!\!(n-1)}
\!\! .
$$
Thus, the second sum on the right hand side of
equation~(\ref{fromeqder}) can be
approximated by
$$
\sum_{p > x} \frac{(\log p)^n}{p^{s}}
=
\int_{x}^{\infty} \frac{(\log u)^{n-1}}{u^{s}}
\; \mbox{d}u
+
o(1)
=
-
\left(
\frac{(-1)^n}{s-1}
\right)^{\!\!(n-1)}
\!\! - \,
\int_{1}^{x} \frac{(\log u)^{n-1}}{u^{s}}
\; \mbox{d}u
+
o(1) \, .
$$
Substituting into equation~(\ref{fromeqder}), we
get
\begin{equation*}
\sum_{p \le x} \frac{(\log p)^n}{p^{s}}
-
\int_{1}^{x} \frac{(\log u)^{n-1}}{u^{s}}
\; \mbox{d}u
=
(-1)^n \,
\sum_{i=1}^{\infty}
\mu(i)
\,
i^{n-1}
\,
\left(\frac{\zeta'}{\zeta}\right)^{\!\!(n-1)}
\!\!\!\!\!\!\!\!(i \, s)
\, + \,
\left(
\frac{(-1)^n}{s-1}
\right)^{\!\!(n-1)}
\!\!\!\!
+ \,
o(1) \, .
\end{equation*}
Taking the limit as $s\rightarrow 1$ and substituting
into equation~(\ref{constBklimit}), we obtain
\begin{equation}
B_n
=
(-1)^n
\sum_{i=2}^{\infty}
\mu(i)
\,
i^{n-1}
\left(\frac{\zeta'}{\zeta}\right)^{\!\!(n-1)}
\!\!\!\!\!\!\!\!(i)
\; + \;
(-1)^n
\lim_{s\rightarrow 1}
\left(
\frac{\zeta'(s)}{\zeta(s)}
+
\frac{1}{s-1}
\right)^{\!\!(n-1)} \!\!\!\! ,
\label{Bkform}
\end{equation}
where the first term on the right hand side is a quickly
converging series and the limit in the second term
can be evaluated using the Laurent expansion of $\zeta(s)$
around $s=1$. This is given by
$$
\zeta (s)
=
\frac{1}{s-1}
+
\sum_{n=0}^{\infty}
\frac{(-1)^n}{n!}
\,
\gamma_n
\,
(s-1)^n,
$$
where the Stieltjes constants $\gamma_n$ are computed
to $20$ significant digits in~\cite{Bohman:1988:SFD}.
Then, the Laurent expansion of the logarithmic
derivative~\cite{Broughan:2009:ERF} of the Riemann
zeta function is
\begin{eqnarray}
\frac{\zeta'(s)}{\zeta(s)}
&=&
-\frac{1}{s-1}
+ \gamma_0
+ (-2 \gamma_1 - \gamma_0 ^2) (s-1)
+ \left( \frac{3}{2} \gamma_2 + 3 \gamma_0 \gamma_1
+ \gamma_0 ^3 \right) (s-1)^2
\nonumber
\\
&&
{\hskip 1cm}
+
\;
\left( -\frac{2}{3} \gamma_3 - 2\gamma_0 \gamma_2
-2 \gamma_1 ^2 - 4\gamma_0 ^2 \gamma_1 - \gamma_0 ^4
\right) (s-1)^3 \, + \, \ldots.
\label{laurent}
\end{eqnarray}
Constants $B_n$ computed by formula~(\ref{Bkform}) using
the Laurent series~(\ref{laurent}) are presented in
Table~\ref{tablecbk}. Once we know constants
$B_n$ to the desired accuracy, we can use equation~(\ref{constCk}) to calculate constants
$C_n$. They are also presented in Table~\ref{tablecbk}
to 20 significant digits.

\begin{table}[t]
{\normalsize
\begin{center}
\begin{tabular}{|r|l|l|l|}
\hline
$n$ & {\hskip 17mm}$B_n$ & {\hskip 19mm}$C_n$ \\
\hline
{\hskip 3mm}$0$\rule{0pt}{3.75mm}
& {\hskip 3mm}$0.26149721284764278375$
& {\hskip 3mm}$0.26149721284764278375$
\\
{\hskip 3mm}$1$
& $-1.3325822757332208817$
& $-2.0710850628855780875$
\\
{\hskip 3mm}$2$
& $-2.5551076154464547041$
& $-7.6972777412176108802$
\\
{\hskip 3mm}$3$
& $-10.253827096911327612$
& $-35.345660320564161516$
\\
{\hskip 3mm}$4$
& $-59.332397971808450296$
& $-206.71503925406509339$
\\
{\hskip 3mm}$5$
& $-453.62459086132753356$
& $-1.5111997871316530251  \times 10^3$
\\
{\hskip 3mm}$6$
& $-4.3591249600559955673 \times 10^3$
& $-1.3546323682845914021 \times 10^4$
\\
{\hskip 3mm}$7$
& $-5.0684840978914262902 \times 10^4$
& $-1.4622910675883565523 \times 10^5$
\\
{\hskip 3mm}$8$
& $-6.9270677393697978276 \times 10^5$
& $-1.8675796280076650637 \times 10^6$
\\
{\hskip 3mm}$9$
& $-1.0884508606344556845 \times 10^7$
& $-2.7733045258413542557 \times 10^7$
\\
$10$
& $-1.9329009099289751454 \times 10^8$
& $-4.7098342357703294361 \times 10^8$
\\
\hline
\end{tabular}
\end{center}
}
\caption{Table of constants $B_n$ and $C_n$, for
$n=0,1,2,\dots,10$, defined by equations~$(\ref{constBk})$
and~$(\ref{constCk})$, which appear in the asymptotic
expansion of $\pi_2(x)$. The values of constants
$B_n$ are computed by formula~$(\ref{Bkform})$ using
the Laurent series~$(\ref{laurent})$. The values
of constants $C_n$ are computed by
equation~$(\ref{constCk})$.
\label{tablecbk}}
\end{table}

\section{Computational results: behaviour
of error terms}

\label{sectionerrorterms}

\begin{figure}
\leftline{\hskip 2mm (a) \hskip 6.95cm (b)}
\centerline{{\hskip 4mm}
\includegraphics[height=5.5cm]{fig1a.eps}
\includegraphics[height=5.5cm]{fig1b.eps}}
\caption{(a)
{\it Relative errors calculated
by~$(\ref{epsevenll})$ for $x=10^6$, $x=10^8$ and
$x=10^{10}$.} \hfill \break
(b) {\it Relative errors calculated
by~$(\ref{defvarepsk})$ for $x=10^8$ and
$x=10^{10}$. The relative error of
Landau's approximation~$(\ref{landauapprox})$
is plotted as $\varepsilon_1(x)$. The relative error
of the approximation given in
Theorem~$\ref{theoremM}$ is plotted
as $\varepsilon_2(x)$.}
}
\label{figerror}
\end{figure}

\noindent
In this section, we illustrate the accuracy of
the asymptotic series (\ref{aspi2}) by calculating
its error terms at each order. Since (\ref{aspi2})
is a sum of two formal asymptotic series, we have
two ways to define its errors. First, we can
truncate both sums after the same number, $\ell$,
of terms to define the relative error
\begin{equation}
\varepsilon_{2 \ell}(x)
=
\frac{1}{\pi_2(x)}
\left|
\left(\sum_{n=1}^{\ell} (n-1)! \,
\frac{x \log(\log x)}{(\log x)^n}
+ \sum_{n=1}^{\ell} C_{n-1} \frac{x}{(\log x)^n}
\right)
- \pi_2(x)
\right|,
\quad
\mbox{for} \; \ell \in {\mathbb N}, \;\;
\label{epsevenll}
\end{equation}
which is plotted in Figure~\ref{figerror}(a) for $x=10^6$,
$x=10^8$ and $x=10^{10}$. Combining both sums in the
asymptotic expansion~(\ref{aspi2}) into one, we can
write it as
$$
\pi_2(x)
\sim
\frac{x \log(\log x)}{\log x}
+
C_0 \, \frac{x}{\log x}
+
\frac{x \log(\log x)}{(\log x)^2}
+
C_1 \, \frac{x}{(\log x)^2}
+
\frac{2 \, x \log(\log x)}{(\log x)^3}
+
\dots,
$$
so we can define the $n$-th approximation, $a_n(x)$,
by
\begin{eqnarray}
a_1(x)
&=&
\frac{x \log(\log x)}{\log x} \, ,
\label{landauapprox}
\\
a_{2 \ell}(x)
&=&
\sum_{i=1}^{\ell} (i-1)! \,
\frac{x \log(\log x)}{(\log x)^i}
+ \sum_{i=1}^{\ell} C_{i-1} \frac{x}{(\log x)^i} \, ,
\qquad \mbox{for} \; \ell = 1, \, 2, \, 3, \, \dots,
\label{evena2l}
\\
a_{2 \ell+1}(x)
&=&
\sum_{i=1}^{\ell + 1} (i-1)! \,
\frac{x \log(\log x)}{(\log x)^i}
+
\sum_{i=1}^{\ell} C_{i-1} \frac{x}{(\log x)^i} \, ,
\qquad \mbox{for} \; \ell = 1, \, 2, \, 3, \, \dots,
\label{odd2lp1}
\end{eqnarray}
where approximation $a_1(x)$ is used
in equation (\ref{landaupoi}) and
$\alpha_2(x)$ is the approximation given in
equation~(\ref{pi_2_first_two_terms}).
With definitions (\ref{landauapprox})--(\ref{odd2lp1}), we can define the relative error by
\begin{equation}
\varepsilon_n(x)
=
\frac{|a_n(x) - \pi_2(x)|}{\pi_2(x)} \, .
\label{defvarepsk}
\end{equation}
This definition is consistent with~(\ref{epsevenll})
for even values of $n$. The results computed by
(\ref{defvarepsk}) are plotted in
Figure~\ref{figerror}(b) for $x=10^8$ and
$x=10^{10}$.

In Figure~\ref{figerror}, we study the behaviour
of the relative error~(\ref{defvarepsk}) for a fixed
value of $x$. We observe that the relative error
$\varepsilon_n(x)$ is initially a decreasing
sequence (for smaller values of~$n$). It reaches its
minimum and then it starts increasing again. Denoting
the value of $n$ where the relative error reaches its
minimum as $n_{\mathrm{min}}(x)$, we observe
that $n_{\mathrm{min}}(x)$ is an increasing
function of $x$, at least for the three values
of $x$ considered in Figure~\ref{figerror}(a).

Since $x$ is fixed in Figure~\ref{figerror},
the relative error~(\ref{defvarepsk})
is a constant multiple of the absolute error
$|a_n(x) - \pi_2(x)|$. In particular, the same conclusion
about $n_{\mathrm{min}}(x)$ could be reached when
considering the absolute errors instead of relative errors.
Since we plot results for two or three different (fixed)
values of $x$ in Figure~\ref{figerror}, we can also observe
that the relative error is (for many of the values
of $n$) a decreasing function of $x$, although this does
not look to be true for $n=2$ in
Figure~\ref{figerror}.

To confirm this
observation, we plot the behaviour of the relative
error $\varepsilon_n(x)$ as a function of $x$ in
Figure~\ref{figerrorasfunctionofx}. We use the first
eight values of $n$ and confirm that the relative
error $\varepsilon_n(x)$ resembles a decreasing
function of $x$ for $n=1,$ $3,$ $4,$ \dots, $8,$ while
$\varepsilon_2(x)$ reaches its minimum between
$2 \times 10^5$ and $3 \times 10^5$.
For smaller values of $x$, the approximation
$a_2(x)$ overestimates $\pi_2(x)$, while it is
an underestimate for larger values of $x$.
The graphs of $a_2(x)$ and $\pi_2(x)$ cross
for the values of $x$ between
$2 \times 10^5$ and $3 \times 10^5$, so in
this interval we can get very close to the
correct answer, which results in the minimum
of $\varepsilon_2(x)$ in
Figure~\ref{figerrorasfunctionofx}(a), because
our error definition~(\ref{defvarepsk}) includes
the absolute value. In Figure~\ref{figerrorasfunctionofx},
we also observe that the other errors are not
strictly decreasing, but they fluctuate with
a decreasing trend, see, for example, the plot
of $\varepsilon_8(x)$ in
Figure~\ref{figerrorasfunctionofx}(b).

\begin{figure}
\leftline{\hskip 2mm (a) \hskip 6.95cm (b)}
\centerline{{\hskip 4mm}
\includegraphics[height=5.5cm]{fig2a.eps}
\includegraphics[height=5.5cm]{fig2b.eps}}
\caption{(a)
{\it Relative errors $\varepsilon_n(x)$, for
$n=1$, $2$, $3$ and $4$, calculated
by~$(\ref{defvarepsk})$ as a function of $x$.
The relative error of Landau's
approximation~$(\ref{landauapprox})$
is plotted as $\varepsilon_1(x)$. The relative
error of the approximation given in
Theorem~$\ref{theoremM}$ is plotted
as $\varepsilon_2(x)$.}
\hfill \break
(b) {\it Relative errors
$\varepsilon_n(x)$, for
$n=5$, $6$, $7$ and $8$ as a function of $x$.
}
}
\label{figerrorasfunctionofx}
\end{figure}

\section{Discussion}

\label{secdiscussion}

\noindent In this paper, we have studied the behaviour of the semiprime
counting function $\pi_2(x),$ which is a special case ($k=2$)
of the $k$-almost prime counting function $\pi_k(x)$. To generalize the
presented results to the case $k \ge 3,$ we need to first generalize the
counting Lemma~\ref{counting_pi2}. Using the inclusion-exclusion
principle, it is possible to deduce the following counting formula
\begin{equation}
\label{count_form_pi_k}
\pi_k(x)
=\sum_{i=1}^{k}
(-1)^{i-1}
\!\!\!
\sum_{p_1<p_2<\ldots<p_i\leq \sqrt[k]{x}} \!\!\!
\pi_{k-i} \! \left( \frac{x}{p_1 p_2 \ldots p_i} \right)\, ,
\end{equation}
where we define function $\pi_0(x)$ to be identically equal
to 1, i.e. $\pi_0(x)=1$, and the sum over
$p_1<p_2<\ldots<p_i\leq \sqrt[k]{x}$ means that we are
summing $i$-times over all primes satisfying the given condition.
Substituting $k=2$ into equation~(\ref{count_form_pi_k}), we
obtain
$$
\pi_2(x)
=
\sum_{p_1 \leq \sqrt{x}} \!\!\!
\pi_{1} \! \left( \frac{x}{p_1} \right)
\, - \!
\sum_{p_1<p_2\leq \sqrt{x}} \!\!\!
\pi_{0} \! \left( \frac{x}{p_1 p_2} \right).
$$
Using $\pi_0(x)=1$, we deduce equation~(\ref{countformpi2}). Thus,
equation~(\ref{count_form_pi_k}) provides a generalization of
equation~(\ref{countformpi2}), which expresses the $k$-almost
prime counting function $\pi_k(x)$ in terms of the counting functions
$\pi_1(x),$ $\pi_2(x)$, \dots, $\pi_{k-1}(x)$. It can be inductively
used to derive forms of coefficients of polynomials $P_{n,k}$ in
the asymptotic series~(\ref{delange}). In addition to constants
$B_n$ and $C_n$, certain new constants will appear in such
calculations, including the (converging) sums of the form
$\sum_{p} (\log p)^i p^{-\ell}$ with $\ell\geq 2$ and
$i \in {\mathbb N}$. For a detailed discussion of the
asymptotic behaviour of these sums for $\ell = 1$,
see Axler~\cite{Axler:2019:FFD}. Substituting $n=\pi(x)$
in~\cite[Theorem 5]{Axler:2019:FFD} gives a different
expansion for the sums in~(\ref{landaulog}), which may be
further examined using the prime number theorem.

There are, also, other possible approximations for $\pi_k(x)$.
For example, Erd\H{o}s and S\'ark\H{o}zy~\cite{Erdos:1980:NPF}
prove that
\begin{equation*}
\pi_k(x)
<
\begin{cases}
\displaystyle c(\delta) \,
\frac{x}{\log x}
\, \frac{(\log (\log x))^{k-1}}{(k-1)!} \,,
&\text{for }1\leq k \leq (2-\delta)\log (\log x);
\\
\displaystyle
\rule{0pt}{5mm} c \, k^4 \, 2^{-k} \,
x \, \log x \, , &\text{for }k\geq 1;
\end{cases}
\end{equation*}
for some constants $c(\delta)$ and $c$. Other approximations,
relating the function $\pi_k$ to some other products over primes
are possible to obtain, as explained in \cite{Tenenbaum:2015:IAP}.

Functions $\pi_k(x)$ and $\Omega(x)$, used in
expansion~(\ref{defOmegaLarge}), count the prime divisors
with their multiplicity. Another possible generalization
is to investigate the related functions $N_k(x)$ and $\omega(x)$,
counting prime divisors without multiplicity. That is,
functions $N_k(x)$ and $\omega(x)$ are defined to be the number
of natural numbers $n\leq x$ which have exactly $k$ distinct
prime divisors and the number of distinct prime divisors of
$x$, respectively. Finch~\cite[page 26]{Finch:2018:MC2} shows that
\begin{equation*}
\frac{1}{x} \sum_{m \le x}
\omega(m)
\, \sim \,
\log (\log x)
+
0.2614972128\dots
+
\sum_{n=1}^\infty
\left(
- 1
+
\sum_{i=0}^{n-1}
\frac{\gamma_i}{i!}
\right)
\frac{(n-1)!}{\log^n x} \, ,
\end{equation*}
which has the higher order terms in the same form as in the
expansion~(\ref{defOmegaLarge}). Using the prime number theorem,
we also observe that
$
N_1(x)
=
\pi\left(x\right) + \pi\left(\sqrt{x}\right)
+
\pi\left(\sqrt[3]{x}\right) + \ldots \sim \mbox{li}(x)
$
admits an identical asymptotic expansion as $\pi(x)$.
Delange~\cite[Theorem 1]{Delange:1971:FAS} and
Tenenbaum \cite{Tenenbaum:2015:IAP} obtained the asymptotic
expansion of $N_k(x)$ in the form
\begin{equation*}
N_k(x)
\, \sim \,
\frac{x}{\log x}
\,
\sum_{n=0}^{\infty}
\frac{Q_{n,k} (\log (\log x))}{(\log x)^n} \, ,
\end{equation*}
where $Q_{n,k}$ are polynomials of degree $k-1$. Here, the expansion
is similar to the expansion~(\ref{delange})
for $\pi_k(x)$, but the polynomials $P_{n,k}$ and $Q_{n,k}$
are different. Results about the leading terms of polynomials
$Q_{n,k}$ and about $Q_{0,k}$ have also been obtained,
as in the case of $\pi_k$. Several different approximations
for $N_k(x)$ are also possible to derive, as shown
in Tenenbaum~\cite{Tenenbaum:2015:IAP}, who points out
that the function $N_k$ is easier to analyse than $\pi_k$,
for larger values of $k$, relative to $\log (\log x)$.
For example, the following holds uniformly for $x\geq 3$ and
$(2+\delta)\log(\log x) \leq k \leq A \log(\log x) $:
$$
N_k(x)
=
C
\, \frac{x \log x}{2^k}
\left( 1 +
\bigO
\! \left( (\log x)^{-\delta^2/5} \right)
\right) \, ,
$$
where $A>0$, $0<\delta<1$ and $C \approx 0.378694$.
Similar results, but for larger values of $k$, can
be obtained for functions $\pi_k$ as
well~\cite{Nicolas:1984:DNE}.

\begin{acknowledgements} \noindent
Authors would like to thank Julia Stadlmann for helpful comments during the
preparation of this manuscript.
\end{acknowledgements}


TITLE: How did they solve for a here?
QUESTION [0 upvotes]: Consider the following algebraic steps:
$$ F - (M_1 a + \mu_k M_1 g) - \mu_k M_2 g = M_2 a $$
$$ F - \mu_k M_1 g - \mu_k M_2 g = (M_1 + M_2) a $$
$$ a = \frac{F - \mu_k M_1 g - \mu_k M_2 g}{(M_1 + M_2)} = \frac{80N - 16.17N - 17.248N}{31kg} $$
$$ = 1.5 \tfrac{m}{s^2} $$
Could someone walk me through the process they did to solve for $a$ here? Those parentheses are really throwing me off; I don't know what to do with them.

REPLY [5 votes]: $$\begin{align}F \color{orange}{-} (m_1a+\mu_xm_1g)-\mu_xm_2g &= m_2a\\ F \color{orange}{-} m_1a\color{orange}{-}\mu_xm_1g-\mu_xm_2g &= m_2a \\ F \color{red}{- m_1a}-\mu_xm_1g-\mu_xm_2g &= m_2a\\ F -\mu_xm_1g-\mu_xm_2g &= \color{red}{ m_1a} + m_2a \\ F -\mu_xm_1g-\mu_xm_2g &= \color{blue}{(m_1+m_2)}a\\  \frac{F -\mu_xm_1g-\mu_xm_2g}{\color{blue}{(m_1+m_2)}} &= a.\end{align}$$


text:
{\bf Problem.} What is the modulo $5$ remainder of the sum $1+2+3+4+5+ \ldots + 120+121+122+123?$
{\bf Level.} Level 3
{\bf Type.} Number Theory
{\bf Solution.} Instead of adding up the sum and finding the residue, we can find the residue of each number to make computation easier.

Each group of $5$ numbers would have the sum of residues $1+2+3+4+0=10$. Since $10 \equiv 0 \pmod{5}$, we can ignore every group of $5$.

This leaves the numbers $121,122,$ and $123$. The sum of the residues is $1+2+3 \equiv 6 \equiv \boxed{1} \pmod{5}$.

set_name: MATH


TITLE: Ensuring that a symmetric matrix with nonnegative elements is positive semidefinite
QUESTION [6 upvotes]: I have the following matrix $A$:

symmetric
all positive and/or zero values
the main diagonal is all the same value, $x$.

To ensure that the matrix $A$, is positive semidefinite, must I only ensure that $x \geq 0$?  It seems correct from my thinking, but wanted to make sure. Thanks.

REPLY [7 votes]: Note however that a diagonally dominant symmetric matrix is positive semi definite.
In your case it is sufficient to add the condition $x \ge \sum_{j\neq i} A_{ij}, i\neq j$ to ensure $A$ to be positive semi definite.


TITLE: From norm to scalar product
QUESTION [10 upvotes]: In the Eculidean Space, one can automatically define a norm if a specific scalar product is given. On the contrary, it's not always true. A p-norm is a scalar product if and only if p=2. My question is what condition do we need in order to move back?

REPLY [0 votes]: Maybe more generally, while every norm gives us a metric, a metric is generated by
  a norm, I think, if the norm is translation-invariant.