text:
\section{Sparse Linear Regression}\label{sec:linreg}

Recall the model described in the Introduction for the linear regression problem. The probability of obtaining a sample $(\vec{x},y) \in \R^d \times \R$ is:
$$\frac{\exp\left(-\frac12 (y-\vec{x}^\top {\vec{\Omega}^*})^2\right)}{\int  \exp\left(-\frac12 (z-\vec{x}^\top {\vec{\Omega}^*})^2\right) S(z) dz}$$
The infinite population negative log-likelihood function with $n$ samples is then:
\begin{equation}\label{eqn:popl}
\bar{l}(\vec{\Omega}) = \frac1n \sum_{i=1}^n \E_{y \sim \mathcal{N}(\vec{x}^{(i)}{\vec{\Omega}^*}, 1, S)}\left[\frac12 y^2 - y\cdot  \vec{x}^{(i)}\vec{\Omega} - \log \int \exp\left(-\frac12 z^2 + z \cdot  \vec{x}^{(i)}\vec{\Omega}\right) dz\right]
\end{equation}
where each $\vec{x}^{(i)}$ is viewed as a row vector.

As in the last section, we instead work with the finite sample negative log-likelihood, which is based on $n$ samples $(\vec{x}^{(1)}, y^{(i)}),\dots, (\vec{x}^{(n)},y^{(i)})$ with each $y^{(i)}$ being drawn from the distribution $\mathcal{N}(\vec{x}^{(i)}{\vec{\Omega}^*}, 1, S)$:
$$l_n(\vec{\Omega}) = \frac1n \sum_{i=1}^n \left(\frac{1}{2} {y^{(i)}}^2 - y^{(i)}  \vec{x}^{(i)}\vec{\Omega}  + \log \int \exp\left(-\frac{1}{2} z^2 +z  \vec{x}^{(i)}\vec{\Omega}\right) S(z) dz\right).$$

Note that $l_n$ is a random variable. We add a regularizer to  the sample negative log-likelihood to obtain the {\em truncated Lasso estimator}:
\begin{equation}\label{eqn:hat}
\hat{\vec{\Omega}} \in \arg \min_{\vec{\Omega} \in \R^d} \left\{l_n(\vec{\Omega}) + \lambda \|\vec{\Omega}\|_1\right\}.
\end{equation}
In the following, let $\vec{X}$ denote the $n$-by-$d$ design matrix whose $i$'th row corresponds to the $i$'th sample $\vec{x}^{(i)}$. Also,
 we let $\vec{x}_j \in \R^n$ denote the $j$'th column of $\vec{X}$.

\subsection{Assumptions} We now formally state the assumptions under which our result holds. For vectors $\vec{\Omega}$ and $\vec{x}$, let
$\alpha(\vec{\Omega}, \vec{x}) \defeq \E_{y \sim \mathcal{N}(\vec{\Omega}^\top \vec{x}, 1)}[S(y)].$
Also, in the following, let $K\subseteq [d]$ denote the support of $\vec{\Omega}^*$, and let $k = |K|$.

Our first assumption states that for every observed $\vec{x}^{(i)}$, there is a significant probability that the corresponding response variable $y^{(i)}$ is not truncated.
\begin{assumption}[Survival Probability]\label{ass:sur}
There exists a constant $\alpha>0$ such that for every $i \in [n]$, $\alpha(\vec{\Omega}^*, \vec{x}^{(i)}) \geq \alpha$.
\end{assumption}

Our second assumption is quite mild. It ensures that the model is identifiable when the support set $S$ is known in advance.
\begin{assumption}[Minimum Eigenvalue]\label{ass:id}
There exists a constant $\sigma_{\min}  > 0$ such that
$$\frac1n \vec{X}_K^\top \vec{X}_K \succeq \sigma_{\min}  \cdot \vec{I}.$$
\end{assumption}

Our third assumption ensures that the covariates corresponding to the support set are sufficiently prominent. More precisely,
the mutual incoherence assumption below requires that if $j \notin K$, then $\vec{x}_j$ is approximately orthogonal to the
span of the submatrix $\vec{X}_K$ corresponding to the covariates in $K$.
\begin{assumption}[Mutual incoherence]\label{ass:inc}
There exists a constant $\beta \in (0,1)$ such that:
$$\max_{j \notin K} \|\vec{x}_j^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1}\|_1 \leq \beta.$$
\end{assumption}
Mutual incoherence is known to hold, for example, with high probability when $\vec{x}^{(1)}, \dots, \vec{x}^{(n)}$ are drawn i.i.d.~from $N(0,\vec{I}_{d \times d})$
as long as $n \geq \Omega\left(k \log d\right)$.

Our last assumption puts a bound on each entry of $\vec{X}$.

\begin{assumption}[Normalization]\label{ass:norm}
There exists  $C>0$
such that
$\max_{i \in [n]} \|\vec{x}^{(i)}\|_\infty = \max_{j \in [d]}\|\vec{x}_j\|_\infty \leq C$.

\end{assumption}

\subsection{Support Recovery} We formally state the main theorem of this section.
\begin{theorem}\label{thm:regstat}
Consider a $k$-sparse linear regression model for which Assumptions \ref{ass:sur}, \ref{ass:id}, \ref{ass:inc}, and  \ref{ass:norm} are all satisfied.
Moreover, suppose that $\frac{C^2 k}{\alpha^5 \sigma_{\min}  (1-\beta)}$ is a sufficiently small constant.
Then, if
\[n \geq \tilde{\Omega}\left(\frac{C^4k^2\log d}{(1-\beta)^2\sigma_{\min} ^2 \alpha^9}\right)
\quad\quad
\text{and}
\quad\quad
\lambda  = \Theta\left(\frac{\alpha^4\sigma_{\min} }{Ck}\right),

\]
any solution $\hat{\vec{\Omega}}$ to the objective (\ref{eqn:hat}) satisfies the following properties with high probability.
\begin{itemize}
\item[(a)]
\textbf{Uniqueness}: There is a unique solution $\hat{\vec{\Omega}}$.
\item[(b)]
\textbf{No false inclusion}: $\mathrm{supp}(\hat{\vec{\Omega}}) \subseteq \mathrm{supp}(\vec{\Omega}^*)$.
\item[(c)]
\textbf{$\ell_\infty$-bounds}: The error $\hat{\vec{\Omega}}-\vec{\Omega}^*$ satisfies
\[
\|\hat{\vec{\Omega}}-\vec{\Omega}^*\|_\infty \leq O\left(\sqrt{\frac{\log(1/\alpha)}{\sigma_{\min} }} + \frac{\alpha^4}{C\sqrt{k}} \right).

\]
\end{itemize}

\end{theorem}
In other words, if the non-zero entries of $\vec{\Omega}^*$ are greater than a particular threshold $\tau$ (which is independent of $d$), then
the support of $\hat{\vec{\Omega}}$ exactly matches with the support of $\vec{\Omega}^*$.

In the untruncated setting, it is known (see Chapter 7 of \cite{Wbook}) that $\lambda$ can be made to scale as $\sim \frac{1}{\sqrt{n}}$, and the
$\ell_\infty$ error is the sum of two terms, one proportional to $\lambda$ and the other to $\frac{1}{\sqrt{n}}$. Hence, by making $n$ large, the
$\ell_\infty$ error can be made arbitrarily small. In contrast, in our analysis, we cannot make $\lambda$ arbitrarily small; so, above, we fix it in terms of the
other problem parameters.

The other notable aspect of Theorem \ref{thm:regstat} is the hypothesis that $\frac{C^2 k}{\alpha^5 \sigma_{\min}  (1-\beta)}$ is small, which is
also absent from the untruncated setting. The hypothesis can be satisfied if $C$ is mildly decreasing in $d$ (e.g., $\sim 1/\log(d)$), and $d$ is very large.

\subsection{Useful Lemmas}
We record for later use two convenient lemmas from \cite{Das19}.
\begin{lemma}[Lemma 6 in \cite{Das19}]\label{lem:das2}
For a set $S \subseteq \R$ and vectors $\vec{\Omega}, \vec{\Omega}', \vec{x} \in \R^{d}$, :
$$\alpha(\vec{\Omega},\vec{x}) \geq \alpha(\vec{\Omega}',\vec{x})^2 \cdot \exp\left(-|(\vec{\Omega}-\vec{\Omega}')^\top \vec{x}|^2 - 2\right).$$
\end{lemma}

\begin{lemma}[Lemma 14 in \cite{Das19}]\label{lem:das1}
For $\vec{x}, \vec{w} \in \R^k$, if $z \sim N(\vec{w}^\top \vec{x}, 1, S)$, then:
$$\E[(z-\E[z])^2] \geq \frac{1}{12}\left(\int_S N(\vec{w}^\top \vec{x}, 1)(y) \cdot S(y) \cdot dy\right)^2.
$$
\end{lemma}

\begin{comment}
\subsection{Proof of Theorem \ref{thm:regstat}}

Standard calculations (see, e.g., \cite{Das18, Das19}) show that the gradient and Hessian of the empirical log-likelihood can be written as:
\begin{equation}\label{eqn:reggrad}
\nabla l_n(\vec{\Omega}) = -\frac1n \sum_{i=1}^n  \left(\vec{x}^{(i)}y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}( \vec{x}^{(i)}\vec{\Omega}, 1, S)}[\vec{x}^{(i)} z^{(i)}]\right)
\end{equation}
\begin{equation}\label{eqn:reghess}
H(\vec{\Omega}) \defeq \nabla^2 l_n(\vec{\Omega}) = \frac1n \sum_{i=1}^n \Cov_{z^{(i)} \sim \mathcal{N}( \vec{x}^{(i)}\vec{\Omega}, 1, S)}[\vec{x}^{(i)} z^{(i)}, \vec{x}^{(i)} z^{(i)}]
\end{equation}
From (\ref{eqn:reghess}), since $H(\vec{\Omega}) \succeq 0$, it is clear that $l_n$ is convex for arbitrary choices of $\vec{x}^{(1)}, \dots, \vec{x}^{(n)}$.
\ignore{
Also, note that the Hessian of $l_n$ and $\bar{l}$ (from (\ref{eqn:popl})) are identical because neither depend on the $y$ variable. Hence, the strong convexity property of $\bar{l}, l_n$ and $l_n+\lambda \|\cdot\|_1$ are the same.

\begin{proof}[Proof of Theorem \ref{thm:regstat}]
The proof follows the outline of Wainwright's proof in \cite{Wbook} (Chapter 7) for subset selection by Lasso, except that our likelihood involves the truncation set, which significantly complicates the analysis.
}

Let:
$$F(\vec{\Omega}) = l_n(\vec{\Omega}) + \lambda \|\vec{\Omega}\|_1.$$
Clearly, $F$ is also convex since $l_n$ is. Now, any optimum $\hat{\vec{\Omega}} \in \arg \min F(\vec{\Omega})$ has to satisfy the zero-subgradient condition:
\begin{equation}\label{eqn:zsub}
\nabla l_n(\hat{\vec{\Omega}}) + \lambda \hat{\vec{W}} = 0
\end{equation}
where $\hat{\vec{W}} \in \partial \|\hat{\vec{\Omega}}\|_1$ and $\nabla l_n$ is as in (\ref{eqn:reggrad}).

Recall that $K \subseteq [d]$ denotes the support of $\vec{\Omega}^\ast$ and $|K| = k$. Let
\begin{equation}\label{eqn:subprob}
\check{\vec{\Omega}} \in \arg \min_{\vec{\Omega} \in \R^{d-1}: \forall j \notin K, \Omega_j = 0} F(\vec{\Omega})
\end{equation}
The rest of the proof goes as follows. First, we establish strong convexity of the restricted likelihood function:
\[
l_n^{K}(\vec{\Omega}) = \frac1n \sum_{i=1}^n \left(\frac{1}{2} {y^{(i)}}^2 -  \vec{x}^{(i)}\vec{\Omega}_{K} y^{(i)} - \ln \int \exp\left(-\frac{1}{2} z^2+ \vec{\Omega} \vec{x}^{(i)}_{K} z\right) S(z) dz\right),
\]
when $\vec{\Omega}$ lies in a neighborhood of $\vec{\Omega}^*$.
We show that our choice of $\lambda$ implies that $\check{\vec{\Omega}}$ falls in this neighborhood, and hence, there is a unique choice of $\check{\vec{\Omega}}$ in (\ref{eqn:subprob}).
Next, we use the {primal-dual witness method} to show that if strict dual feasibility holds, then $\hat{\vec{\Omega}}$ must in fact equal $\check{\vec{\Omega}}$.
 Then, we verify that strict dual feasibility holds under our choice of parameters and assumptions, establishing parts (a) and (b) of Theorem \ref{thm:regstat}. Finally, it remains to bound the $\ell_\infty$-distance between $\check{\vec{\Omega}}$ and $\vec{\Omega}^*$, proving part (c).

\ignore{
\begin{lemma}\label{lem:subunique}
If $n \geq {\Omega}(m^2 \cdot \mathrm{polylog}(mn/\alpha \delta))$, then with probability at least $1-\delta$, $\check{\vec{\Omega}}$ in (\ref{eqn:subprob}) is uniquely defined.
\end{lemma}
\begin{proof}
Define the restricted likelihood function $l_n^{T}: \R^{|T|} \to \R$:}

\paragraph{Local strong convexity:}
We first show that $l_n^K$ is strongly convex for $\Omega$ within a ball centered at $\Omega^*$. Below, $\vec{\Omega}^\ast_{K}$ is the restriction of $\vec{\Omega}^\ast$ to the coordinates in $K$.
\begin{lemma}\label{lem:locstrong}
There exists $\kappa\geq \Omega( \alpha^4\cdot \sigma_{\min} )>0$ such that $\nabla^2l_n^{K}(\vec{\Omega}) \succeq \kappa\cdot \vec{I}$ for all $\vec{\Omega}\in \R^{k}$ satisfying $\|\vec{\Omega}-\vec{\Omega}_{K}^*\|_2\leq \frac{1}{C\sqrt{k}}$.
\end{lemma}
\begin{proof}
	Computing the Hessian of $l_n^{K}$:
	\begin{align*}
		\nabla^2 l_n^{K}(\vec{\Omega}) &= \frac1n \sum_{i=1}^n \Cov_{z^{(i)} \sim \mathcal{N}(\vec{\Omega}^\top\vec{x}^{(i)}_K,1,S)}[\vec{x}^{(i)}_Kz^{(i)},\vec{x}^{(i)}_Kz^{(i)}]\\
		&= \frac1n \sum_{i=1}^n \vec{x}_K^{(i)} {\vec{x}_K^{(i)}}^\top \cdot \E_{z^{(i)} \sim \mathcal{N}(\vec{\Omega}^\top\vec{x}^{(i)}_K,1,S)}[(z^{(i)}-\E z^{(i)})^2]\\
		&\succeq  \frac{1}{12n} \sum_{i=1}^n \vec{x}_K^{(i)} {\vec{x}_K^{(i)}}^\top \cdot (\alpha(\vec{\Omega},\vec{x}^{(i)}))^2\\
		&\succeq \frac{1}{12e^2n} \sum_{i=1}^n \vec{x}_K^{(i)} {\vec{x}_K^{(i)}}^\top (\alpha(\vec{\Omega}^*, \vec{x}^{(i)}))^4 \cdot \exp\left(-2|(\vec{\Omega}-{\vec{\Omega}^*_{K}})^\top \vec{x}^{(i)}_K|^2-4\right)

	\end{align*}
	where the third line\footnote{We abuse notation in the third line. When we say $\alpha(\vec{\Omega},\vec{x}^{(i)})$, we mean by $\vec{\Omega}$ the extension of the vector to $\R^d$ where the coordinates not in $K$ are set to zero.} follows from Lemma \ref{lem:das1} and the fourth line follows from Lemma \ref{lem:das2}. Recall that by Assumption \ref{ass:norm},  $\|\vec{x}_K^{(i)}\|_\infty \leq C$, and hence, $\|\vec{x}_K^{(i)}\|_2 \leq C\sqrt{k}$. Plugging into the above, and again using Assumptions \ref{ass:sur} and \ref{ass:id}, we obtain:
	\[\nabla^2 l_n^{K}(\vec{\Omega}) \succeq \frac{1}{12e^2} \cdot \alpha^4 \cdot e^{-6} \cdot \sigma_{\min}  \vec{I}.\]
\end{proof}

\ignore{
Using Lemma \ref{lem:covest}, since $n \geq \tilde{\Omega}(m\log \alpha^{-1} \log^2 \delta^{-1})$,
$$\frac1n\sum_{i=1}^n \vec{x}_K^{(i)} {\vec{x}_K^{(i)}}^\top \succeq c_2 \E_{\vec{x}_K}[\vec{x}_K \vec{x}_K^\top]$$
with probability at least $1-\delta$, for some $c_2 > 0$.  Here, in the application of Lemma \ref{lem:covest}, we define $F(\vec{x}_K)$ as $S(\vec{x})$ where $\vec{x}=(\vec{x}_K,\vec{x}_{\bar{T}})$ is sampled from $\mathcal{N}(0,{\vec{\Omega}^\ast}^{-1})$. Similarly applying Lemma \ref{lem:covest2}:
$$\E_{\vec{x}_K}[\vec{x}_K \vec{x}_K^\top] \succeq \Omega(\alpha^2)\cdot ({\vec{\Omega}^\ast}^{-1})_{TT}.$$
The lemma follows because by Assumption \ref{ass:id}, the minimum eigenvalue of $({\vec{\Omega}^\ast}^{-1})_{TT}$ is positive}

\paragraph{Bounding the $\ell_2$-distance between $\check{\vec{\Omega}}$ and $\vec{\Omega}^*$:}
Let $r = \frac{1}{C\sqrt{k}}$ be the radius of the ball $B_r$ around $\vec{\Omega}_{K}^*$ inside which $l_n^{K}$ is strongly convex (by Lemma \ref{lem:locstrong}). This means that $l_n^{K}(\vec{\Omega})+\lambda  \|\vec{\Omega}\|_1$ is also locally strongly convex in $B_r$. The next proposition shows that for an appropriate choice of $\lambda $, $\check{\vec{\Omega}}$, defined in (\ref{eqn:subprob}) as the minimizer of $l_n^{K}(\vec{\Omega})+\lambda  \|\vec{\Omega}\|_1$, is in the ball $B_r$.

\begin{lemma}\label{lem:lambda}
If $2\|\nabla l_n^{T}(\vec{\Omega}^*_{K})\|_\infty < \lambda  <\frac{2\kappa r}{3\sqrt{k}}$, where $\kappa$ and $r$ are as above, then $\check{\vec{\Omega}} \in B_r$. Moreover, our choice of $\lambda $ satisfies these conditions with high probability.
\end{lemma}
\begin{proof}
	The first part follows exactly the same steps as the proof of Lemma \ref{lem:mainbig}, and so we omit it. For the second part, note that:
	\[\nabla l_n^{K}(\vec{\Omega}^*_{K}) = -\frac1n \sum_{i=1}^n \left(\vec{x}^{(i)}_K y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}({\vec{\Omega}^*_{K}}^\top \vec{x}_{K}^{(i)}, 1, S)}[\vec{x}_{K}^{(i)} z^{(i)}]\right).\]
Consider the $i$'th summand $\vec{x}^{(i)}_K\cdot \left(y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}({\vec{\Omega}^*_{K}}^\top \vec{x}_{K}^{(i)}, 1, S)}[z^{(i)}]\right)$. For every $i$, each coordinate of the $i$'th summand has mean zero. Also, for every $i$, each coordinate of the $i$'th summand is bounded by $O(C \sqrt{\log(n/\alpha)})$ with high probability because:
	\begin{itemize}
	\item[(i)] $\|\vec{x}_K^{(i)}\|_\infty \leq C$ for all $i$ by Assumption \ref{ass:norm}.
\item[(ii)]	 $y^{(i)}-\Omega_K^* \vec{x}_K^{(i)}$ is distributed as a standard normal truncated to a set of volume at least $\alpha$. The maximum of $n/\alpha$ standard normal variables is $O(\sqrt{\log(n/\alpha)})$ with high probability.
\item[(iii)] $\Omega_K^* \vec{x}_K^{(i)} - \E[\mathcal{N}({\vec{\Omega}^*_{K}}^\top \vec{x}_{K}^{(i)}, 1, S)]= \E[\mathcal{N}({\vec{\Omega}^*_{K}}^\top \vec{x}_{K}^{(i)}, 1)] - \E[\mathcal{N}({\vec{\Omega}^*_{K}}^\top \vec{x}_{K}^{(i)}, 1, S)]$ is bounded by $O(\sqrt{\log(1/\alpha)})$ by Lemma 6 in \cite{Das18}.
\end{itemize}

By the Hoeffding bound, $\|\nabla \ell_{K}(\vec{\Omega}^*_{K})\|_\infty < t$ with high probability if $n \geq {\Omega}(C^2\log k\log(n/\alpha)/t^2)$. Plugging in $t = O(\kappa r/\sqrt{k})$ and the values of $\kappa$ and $r$ from Lemma \ref{lem:locstrong}, we see that the constraint is non-vacuous if $n\geq \tilde{\Omega}(C^2/(\kappa^2r^2/k)) = \tilde{\Omega}(C^4k^2/\alpha^8\sigma_{\min} ^2)$. The condition on $n$ is satisfied by the hypotheses of Theorem \ref{thm:regstat}.
\end{proof}

The above two lemmas imply that $\check{\vec{\Omega}}$ is uniquely defined. Now, the goal is to relate it to the structure of $\hat{\vec{\Omega}}$.
\paragraph{Unique global minimum under strict dual feasibility:}
We construct a vector $\check{\vec{W}}$ so that $(\check{\vec{\Omega}}, \check{\vec{W}})$ satisfy the zero subgradient condition (\ref{eqn:zsub}). Note that by definition, $\check{\vec{\Omega}}$ satisfies the restricted zero-subgradient condition on the coordinates in $K$:
$$\frac1n \sum_{i=1}^n \vec{x}_K^{(i)} y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\check{\vec{\Omega}}^\top\vec{x}^{(i)}_K,1,S))}[\vec{x}_{K}^{(i)} z^{(i)}] - \lambda \check{\vec{W}}_{K} = 0$$
for some $\check{\vec{W}}_{K} \in \partial \|\check{\vec{\Omega}}_{K}\|_1$. We set $\check{\vec{W}}$ so that it restricts to $\check{\vec{W}}_{K}$ on $K$ and satisfies the zero-subgradient condition (\ref{eqn:zsub}) on all other coordinates as well.

\begin{lemma}\label{lem:uniquemin}
If $\|\check{\vec{W}}_{-K}\|_\infty < 1$, then $\check{\vec{\Omega}} = \hat{\vec{\Omega}}$ is the unique minimizer of $F$.
\end{lemma}
\begin{proof}
Note that $\langle \check{\vec{W}}, \check{\vec{\Omega}} \rangle = \|\check{\vec{\Omega}}\|_1$ because outside $K$, $\check{\vec{\Omega}}$ is zero, and $\check{\vec{W}}_{K} \in \partial \|\vec{\Omega}_{K}\|_1$. Then, since $F(\hat{\vec{\Omega}}) \leq F(\check{\vec{\Omega}})$:
\begin{align*}
\lambda \|\hat{\vec{\Omega}}\|_1 &\leq l_n(\check{\vec{\Omega}}) + \lambda \|\check{\vec{\Omega}}\|_1 - l_n(\hat{\vec{\Omega}})\\
&= l_n(\check{\vec{\Omega}}) - l_n(\hat{\vec{\Omega}}) + \langle \lambda \check{\vec{W}}, \check{\vec{\Omega}}\rangle \\
&= l_n(\check{\vec{\Omega}}) - l_n(\hat{\vec{\Omega}}) -  \langle \nabla l_n(\check{\vec{\Omega}}), \check{\vec{\Omega}}\rangle
\end{align*}
where we used the fact that $\check{\vec{\Omega}}$ and $\check{\vec{W}}$ satisfy the zero-subgradient condition (\ref{eqn:zsub}). Invoking the convexity of $l_n$:
\begin{align*}
\lambda \|\hat{\vec{\Omega}}\|_1&\leq - \langle \nabla \bar{l_n}(\check{\vec{\Omega}}), \hat{\vec{\Omega}}\rangle = \lambda \langle \check{\vec{W}}, \hat{\vec{\Omega}}\rangle
\end{align*}
Hence, if $|\check{\vec{W}}_{K}| < 1$ for any $s$, then $\hat{\vec{\Omega}}_{K} = 0$. The claim then follows since we have already established that $\check{\vec{\Omega}}$ is defined uniquely.
\end{proof}

\paragraph{Verifying strict dual feasibility:} We next confirm that the $\check{\vec{W}}$ vector constructed above satisfies the condition of Lemma \ref{lem:uniquemin}.
\begin{lemma}
With high probability, $\|\check{\vec{W}}_{-K}\|_\infty<1$.
\end{lemma}
\begin{proof}
Since $(\check{\vec{\Omega}}, \check{\vec{W}})$ satisfy the zero subgradient condition (\ref{eqn:zsub}), we can solve for $\check{\vec{W}}_{-K}$:
\begin{align}
\check{\vec{W}}_{-K}
&=\frac{1}{n\lambda }\sum_{i=1}^n \vec{x}^{(i)}_{-K} \left(y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\check{\vec{\Omega}} \vec{x}^{(i)}, 1, S)}z^{(i)}\right)\nonumber\\
&=\frac{1}{n\lambda } \sum_i \vec{x}_{-K}^{(i)} \left({\vec{x}_{K}^{(i)}}^\top (\vec{\Omega}^* - \check{\vec{\Omega}})+ {z^*}^{(i)} - \E \check{z}^{(i)}\right)\label{eqn:j-K}
\end{align}
where ${z^*}^{(i)} \sim N(0,1, S(\cdot + \vec{\Omega}^* \vec{x}^{(i)}))$ and ${\check{z}}^{(i)}\sim N(0,1, S(\cdot + \check{\vec{\Omega}} \vec{x}^{(i)}))$. Similarly, we solve for $\check{\vec{W}}_{K}$:
\begin{align*}
\check{\vec{W}}_{K}
&=\frac{1}{n\lambda }\sum_{i=1}^n \vec{x}^{(i)}_{K} \left(y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\check{\vec{\Omega}}^\top \vec{x}^{(i)}, 1, S)}z^{(i)}\right)\nonumber\\
&=\frac{1}{n\lambda } \sum_i \vec{x}_{K}^{(i)} \left({\vec{x}_{K}^{(i)}}^\top (\vec{\Omega}^*-\check{\vec{\Omega}}) + {z^*}^{(i)} - \E \check{z}^{(i)}\right)\label{eqn:j-K}
\end{align*}
Let $\vec{u}$ denote the random vector whose $i$'th coordinate is ${z^*}^{(i)} - \E \check{z}^{(i)}$; note that the components of $\vec{u}$ are independent.  We can rewrite the above as:
\begin{equation}\label{eqn:omegadiff}
\vec{\Omega}^*-\check{\vec{\Omega}}  = \lambda n (\vec{X}_K^T \vec{X}_K)^{-1} \check{\vec{W}}_K - (\vec{X}_{K}^\top \vec{X}_K)^{-1}\vec{X}_K^\top \vec{u}
\end{equation}
Substituting back into (\ref{eqn:j-K}), we get:
\begin{equation}\label{eqn:boundonw}
\vec{W}_{-K} = \vec{X}_{-K}^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1} \check{\vec{W}}_K + \frac{1}{\lambda n} \vec{X}_{-K}^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top) \vec{u}.
\end{equation}
We analyze the contribution of each of the two terms above separately.
\begin{claim}
$\|\vec{X}_{-K}^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1} \check{\vec{W}}_K\|_\infty \leq \beta$.
\end{claim}
\begin{proof}
For any $j \notin K$,
\[|\vec{x}_j^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1} \check{\vec{W}}_K| \leq \|\vec{x}_j^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1}\|_1 \leq \beta\]
by Assumption \ref{ass:inc}.
\end{proof}
\begin{claim}\label{clm:randdual}
With high probability, $\|\frac{1}{\lambda n} \vec{X}_{-K}^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top) \vec{u}\|_\infty \leq \frac{1-\beta}{2}.$
\end{claim}
\begin{proof}
For any $j \notin K$, let $\vec{v}_j^\top = \vec{x}_j^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top)$. Note that $\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top$ is an
orthogonal projection matrix, and hence, by Assumption \ref{ass:norm}, $\|\vec{v}_j\|_2 \leq \|\vec{x}_j\|_2 \leq C\sqrt{n}$ and $\|\vec{v}_j\|_1 \leq Cn$.

Write $\vec{u} = \vec{z}^* - \E[\check{\vec{z}}]$. By the triangle inequality, it suffices to bound: (i) $\frac{1}{\lambda n} |\vec{v}_j^\top (\vec{z}^* - \E[\vec{z}^*])|$ and (ii) $\frac{1}{\lambda n} |\vec{v}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])|$.

We first bound (ii).
\[
\frac{1}{\lambda n} |\vec{v}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])| \leq \frac{1}{\lambda n} \|\vec{v}_j\|_1 \|\E[\vec{z}^*] - \E[\check{\vec{z}}])\|_\infty \leq \frac{C}{\lambda } \cdot\max_{i \in [n]} (|\E[{z^*}^{(i)}]| + |\E[\check{z}^{(i)}]|)
\]
Since each ${z^*}^{(i)}$ is a standard normal truncated to a set of volume at least $\alpha$, Lemma 6 of \cite{Das18} implies $\E[{z^*}^{(i)}] = O(\sqrt{\log(1/\alpha)})$.  Similarly, $\E[\check{z}^{(i)}] = O\left(\sqrt{\log(1/\alpha(\check{\vec{\Omega}}_K, \vec{x}_K^{(i)}))}\right)$. Invoking the fact that $\|\vec{\Omega}^* - \check{\vec{\Omega}}\|_2 \leq \frac{1}{C\sqrt{k}}$ and Lemma \ref{lem:das2}, we obtain that $\alpha(\check{\vec{\Omega}}, \vec{x}^{(i)}) = \Omega(\alpha^2)$. Hence, we get:
\[
\frac{1}{\lambda n} |\vec{v}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])|\leq \frac{C}{\lambda } \cdot O(\sqrt{\log(1/\alpha)}) \leq O\left(\frac{C^2k}{\alpha^5 \sigma_{\min} }\right) < \frac{1-\beta}{4}.
\]
where we used the assumption in the Theorem.

Now, we turn to (i). Observe that $\vec{\zeta}^* = \vec{z}^* - \E[\vec{z}^*]$ is a zero-mean vector with independent components ${\zeta^*}^{(1)}, \dots, {\zeta^*}^{(n)}$. In order to bound $\vec{v}_j^\top \vec{\zeta}^* = \sum_{i \in [n]} {v}_j^{(i)} {\zeta^*}^{(i)}$, we use Bernstein's inequality (Lemma \ref{lem:berns}). Fix an $i \in [n]$, and let $\zeta$ denote ${\zeta^*}^{(i)}$. For Bernstein's Lemma, we need bounds on $\E[{{\zeta}}^p]$ for $p>1$. It is easy to see that these quantities are maximized when $\zeta \sim \mathcal{N}(0,1,S_q)$ where $S_q = \{x : x^2 \geq q\}$ for some $q$ chosen such that $\mathcal{N}(0,1,S_q)=\alpha$. Routine calculations (Lemma 13 of \cite{Das19})  show that $\E[\zeta^2] \leq 2 + 2 \log(2/\alpha)$ and $\E[\zeta^p] \leq p! (2+2\log(2/\alpha))^p$. Applying Bernstein, we get that with probability $1-\exp(-t^2)$,  $\frac{1}{\lambda n} |\vec{v}_j^T \vec{\zeta}^*| \leq O\left(\frac{Ct\log(1/\alpha)}{\lambda \sqrt{n}}\right)$ for $t \leq O(\sqrt{n/\log(1/\alpha)})$.  Setting $t = \Omega(\sqrt{\log d})$, we get that with high probability, for all $j \notin K$:
\[
\frac{1}{\lambda n} |\vec{v}_j^T \vec{\zeta}^*| \leq O\left(\frac{C\sqrt{\log d}\log(1/\alpha)}{\lambda \sqrt{n}}\right) = O\left(\frac{C^2 k \sqrt{\log d}\log(1/\alpha)}{\alpha^4 \sigma_{\min}  \sqrt{n}}\right).
\]
If we take $n \geq \Omega((C^4k^2\log d)/((1-\beta)^2\sigma_{\min} ^2 \alpha^9))$, then the above is less than $(1-\beta)/4$. This proves the claim.
\end{proof}

\paragraph{Bounding the $\ell_\infty$-error:} The max-error can be bounded using (\ref{eqn:omegadiff}).
\[
\|\check{\vec{\Omega}}-\vec{\Omega}^*\|_\infty \leq \lambda  \opnorm*{\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}}_\infty + \left\|\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\vec{X}_K^\top \frac{\vec{u}}{n}\right\|_\infty
\]
where for a matrix $A$ with $r$ rows, $\opnorm{A}_\infty = \max_{i \in [r]} \|A^{(i)}\|_1$ is the matrix $\ell_\infty$-norm.

The first term is deterministic and can be bounded as follows:
\[
\lambda  \opnorm*{\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}}_\infty \leq \lambda  \sqrt{k}\cdot \lambda_{\max}\left(\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\right) \leq \frac{\lambda  \sqrt{k}}{\sigma_{\min} } = O\left(\frac{\alpha^4}{C\sqrt{k}}\right)
\]

To analyze the second term, define for $j \in K$, the vector $\vec{w}_j^\top = \vec{e}_j^\top \left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\frac{\vec{X}_K^\top}{n}$. We need to bound $\max_{j\in K} |\vec{w}_j^\top \vec{u}|$.
Note that $\|\vec{w}_j\|_2^2 = 	\frac1n \vec{e}_j^\top \left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\vec{e}_j \leq \frac{1}{n \sigma_{\min} }$.
Similar to the analysis in the proof of Claim \ref{clm:randdual}, we write $\vec{u}$ as $(\vec{z}^* - \E[\vec{z}^*]) + (\E[\vec{z}^*] - \E[\check{\vec{z}}])$. The quantity $\max_{j \in K}|\vec{w}_j^\top (\vec{z}^* - \E[\vec{z}^*])|$ can be
shown using Bernstein's inequality to be at most $O\left(\frac{\sqrt{\log k}\log(1/\alpha)}{\sqrt{\sigma_{\min}  n}}\right)$ with high probability. The other term can be bounded as:
\[
\max_{j \in K} |\vec{w}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])| \leq \max_{j \in K} \|\vec{w}_j\|_1 O(\sqrt{\log(1/\alpha)}) \leq O\left(\sqrt{\frac{\log(1/\alpha)}{\sigma_{\min} }}\right)
\]
So, putting everything together:
\[
\|\check{\vec{\Omega}}-\vec{\Omega}^*\|_\infty \leq O\left(\sqrt{\frac{\log(1/\alpha)}{\sigma_{\min} }} + \frac{\alpha^4}{C\sqrt{k}} + \frac{\sqrt{\log k}\log(1/\alpha)}{\sqrt{\sigma_{\min}  n}} \right).
\]
The last term is negligible because of the lower bound on $n$.
\ignore{
 The $j$'th component of the second term in (\ref{eqn:boundonw}) is bounded as:
\[
\frac{1}{\lambda n} |{X}_j^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top) \vec{u}|
\leq \frac{1}{\lambda n} \|X_j^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top)\|_2  \cdot \|u\|_2 \leq \frac{\|X_j\|_2}{\lambda n} \cdot \|u\|_2.
\]
where we used the fact that $\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top$ is an orthogonal projection matrix. By Assumption \ref{ass:id}, $\|X_j\|_2 \leq K\sqrt{n}$. It remains to bound $\|u\|_2$.

The first term is bounded by $1-\beta$ by Assumption \ref{ass:inc}. For the second term, note that $\|u\|=O(1)$ because they correspond to truncations according to sets that are close as we have already shown that $\|\check{\vec{\Omega}}-\vec{\Omega}^*\|\leq r$. Our desired bound follows by choice of $\lambda$.}
\end{proof}
\end{comment}

\input{linreg-proofs}


TITLE: How should two-photon transitions be modelled? Is second-order perturbation theory required? Or are sequential first-order processes sufficient?
QUESTION [0 upvotes]: For example, I want to consider the following situation: photon transit from $m$ energy level to $m+2$ after absorption of two phonons with frequency $\Omega$. I want to calculate a transition rate for this process and now I'm little stuck in the choosing the way to do it. Should I use a second-order perturbation theory to find this rate, or can I just multiply the probabilities as a sequential processes ($m \to m+1 \to m+2$ states) to find total probability? Which of these options is more correct?

REPLY [0 votes]: To be honest, it depends on the situation, and particularly on how long the pump lasts and what the lifetime of the states is. If you have long-lived states, then sequential processes become possible and they can dominate, but at shorter timescales you expect second-order perturbation theory to be more crucial.
It also depends on how close you are to the resonance on the middle transition. If you're exactly on resonance, then SOPT in its naive form will diverge, until you include the lifetime of the state, and you might be better off with a sequential process. On the other hand, it's quite common to have the full two-photon process be exactly on resonance, but not the middle step; in these cases SOPT is essential.


TITLE: Given that β and γ are in S4 with βγ=(1432), γβ=(1243), and β(1)=4, determine β and γ.
QUESTION [0 upvotes]: I'm trying to solve this using function composition but I don't know how to progress because all we know is β(1)=4.

REPLY [1 votes]: This is exercise 56 in chapter 5 of Gallian's Contemporary Abstract Algebra.
To find $\beta$ and $\gamma$ you can repeatedly use $\beta \gamma$ and $\gamma \beta$ as follows:
(1) $\beta (1) = 4$ and $\gamma \beta (1) = 2$ implies $\gamma (4) = 2$.
(2) $\gamma (4) = 2$ and $\beta \gamma (4) = 3$ implies $\beta (2) = 3$.
(3) $\beta (2) = 3$ and $\gamma \beta (2) = 4$ implies $\gamma (3) = 4$.
(4) $\gamma (3) = 4$ and $\beta \gamma (3) = 2$ implies $\beta (4) = 2$.
(5) $\beta (4) = 2$ and $\gamma \beta (4) = 3$ implies $\gamma (2) = 3$.
(6) $\gamma (2) = 3$ and $\beta \gamma (2) =1$ implies $\beta (3) = 1$.
Hence $\beta = (1423)$.
(7) $\beta (3) = 1$ and $\gamma \beta (3) = 1$ implies $\gamma (1) = 1$ hence $\gamma = (234)$.


TITLE: Solving $2^x+2^y+1=3^z$ in integers
QUESTION [4 upvotes]: I have reasons to believe that there should be an elementary, relatively simple way to find all solutions of the equation in the title in positive integers $x>y$ and $z$. Any ideas?

REPLY [0 votes]: @W-t-P  MINOR NIT: There is also the trivial solution $x$=0, $y$=0, $z$=1.  And since the original problem says 'solution in integers', not 'solution in natural numbers', one must also note that there are no solutions containing negative numbers (because either one gets an equality between an integer and a fraction [on either side], or after one clears fractions one gets an equality between a multiple of a power of three and an exact power of two).


TITLE: How do you write the matrix form of $Z_1 Z_2$ as a quantum circuit?
QUESTION [0 upvotes]: I am reading about the quantum bit flip error correction on the wikipedia page:
https://en.wikipedia.org/wiki/Quantum_error_correction
In order to perform the projective measurement to identify the error we must apply the $Z_1 \otimes Z_2 \otimes I$ operator. How do we represent this in quantum circuit notation?
The matrix form is a diagonal matrix with the diagonal:
$$\begin{matrix}(1 &&-1&&-1&&1&&1&&-1&&-1&&1)\end{matrix}$$

REPLY [1 votes]: The Kronecker product of matrices is the matrix representation of the linear transformation on a tensor product of spaces obtained by letting two linear transformations act independently on the factors. This should be understood in the tensor product basis whose elements could be written $|ij\rangle$ if $|i\rangle, |j\rangle$ are basis elements of the factors, and ordered in such a way that for each $i$, $j$ runs through all possibilities before $i$ is incremented.
In your case the transformation is already written as a tensor product, and the circuit simply is a 3-qubit system, where in parallel $Z_1$ is applied to the first qubit, $Z_2$ to the second, and $I$ to the third (doing nothing). If you don't know what these single-qubit gates do, you could easily factor the  matrix of the compound transformation.


TITLE: Minimize function - nested square roots
QUESTION [0 upvotes]: I would like to find $z$ which minimizes the below, when $x$ is held at a specific value.
$f(x,z) =\sqrt{\sqrt{x^2 + z^2} - 0.25}$
For example; I would like to find the value of $z$ which minimizes the function when $x = 0.5$

REPLY [0 votes]: It looks like the $z$ you are looking for is $0$ if $|x|\geq 0.25$, since the function square root only is increasing and taking the square only gives positive numbers. Similarly, if $|x|<0.25$, we only have to make sure that the pair $(x,z)$ is still in the domain of $f$, hence $z=\sqrt{1/16-x^2}$ is the right $z$.


TITLE: Disentangling $\int_Af(\mathbf{x})\ d\mathbf{x}$, using Fubini Theorem.
QUESTION [3 upvotes]: Let $\mathcal{B}^n$ be the borel sigma algebra generated by the rectangles in $\mathbb{R}^n$. I can write $f(\mathbf{x})=g_1(x_1)\cdots g_n(x_n)$.
Let $\mu=\mu_1\times \cdots \times \mu_n$ be the Lebesgue product measure.
Is it possible to write $\int_Af(\mathbf{x})\ d\mu(\mathbf{x})$, where $A \in \mathcal{B}^n$, as an expression of $\prod^n_{i=1}\int_{A_i}g_i(x_i) \, d\mu_i(\mathbf{x})$, where the $A_i$ are not dependent on each other?
So, I was thinking of using the fact that the $\mathcal{B}^n$ can be generated by rectangles of the form $I_1\times \cdots \times I_n$, where $I_i \subset \mathbb{R}$ are intervals; and then use the Fubini theorem, which is valid for rectangles, to reach the expression I desire. However, I don't know how to do this...
Any help would be appreciated.
P.S.: What if $\mu$ is not lebesgue?

REPLY [1 votes]: No, you can't. Look at the following example: If $A$ is the unit disc in the $(x_1,x_2)$-plane then Fubini's theorem says that
$$\int_A g_1(x_1) g_2(x_2)\>{\rm d}(x_1,x_2)=\int_{-1}^1  \int_{-\sqrt{1-x_1^2}}^{\sqrt{1-x_1^2}} g_1(x_1)\> g_2(x_2)\>dx_2\>dx_1\ ,$$
as you have learned in Calculus 102. (You are allowed to take the factor $g_1(x_1)$ out of the inner integral.)
Things are different if the domain of integration $B\subset{\mathbb R}^n$ is itself a cartesian product $$A=\prod_{i=1}^n A_i\tag{1}$$ with $A_i$ embedded in the $i^{\rm th}$ factor of ${\mathbb R}^n$. In this case the $n$-fold integral indeed  "separates" as envisaged in your question.
A general subset $A\subset{\mathbb R}^n$, even a finite union of boxes $B:=\prod_{i=1}^n [a_i,b_i]$, cannot be presented in the form $(1)$, and this definitively forbids the simplification you desire.


TITLE: What is really being claimed in this article about a prime number pattern?
QUESTION [3 upvotes]: I just read this "news" report about Stanford professors who discovered a pattern in prime numbers:
https://www.nature.com/news/peculiar-pattern-found-in-random-prime-numbers-1.19550
According to this report (which is admittedly not the original research paper), it sounds like the claim is merely that consecutive primes share a units digit less often than chance.
My first thought was "why would one expect differently?". If one merely makes a list of "potential primes" (namely any number with at least two digits that ends in 1,3,7,or 9) and then assigns each number an independent probability of being prime, then one would expect the units digits in consecutive primes to be equal slightly less often than chance.
To see what I mean, let's re-cast this as the following problem: Suppose I roll an ordinary 6-sided die many, many times, take 1000 as an example. I number the rolls 1-1000 in a list, and I put a check mark next to every time the number "1" comes up on the die. The probability that the numbers next to a pair of consecutive check marks have the same units digit will be less than 1/10. Why you ask? Because, the number of "failures" (rolls that are NOT a "1") follows a geometric distribution, which is monotone decreasing. Therefore, the probabilities that, after rolling a 1, it will take 1,2,3,...9 additional rolls to roll the next "1" are each greater than the probability it will take 10 rolls. Similarly, the probabilities that it will take any of 11-19 rolls are each greater than the probability it will take 20 rolls, and so on. So the probability of taking exactly 10, 20, 30,... etc. rolls is less than 1/10. In fact, it's less than 0.04.
Of course, the probability a number N is prime decreases as N increases. However, the above argument is independent of the probability, as long as the probabilities of success on successive trials don't change much. But since this probability is proportional to 1/ln(N), which varies very slowly indeed, this should be true.
However, what I think is going on here is that one only expects a significant bias when the average gap between primes is less than or about 10. In fact, for lists of small primes (e.g. primes less than 400), I've checked some cases and the above argument (using the observed fraction of potential primes in that range that ARE prime, as if it's uniform) predicts the chance of sharing units digits remarkably well. Above about 22,000, the average gap is longer than 10 but they looked at the first billion primes. Of them, such a small fraction are less than 22,000 that the bias should be negligible at that point. Yet they still see biases of more than a few percent.
So, I'm suspecting that the authors of the original paper are actually making the claim that the bias decays substantially slower than predicted by the geometric series argument, for some rigorous definition of "substantially slower", and this subtlety was lost in the general-audience reporting. I don't know enough number theory to understand what that might be, but does anyone here understand what they are actually claiming?

REPLY [1 votes]: You should really read the paper on arxiv, not the exposition on nature.com.
Anyway, here is an objection to your objection.
With a random model for primes, you are rolling a die. However, in the case of primes, this is not a 6-sided die, but a die with decreasing (and vanishing) chance to roll  a prime. Namely, each time you roll a prime $p$, the probability to roll the next prime is multiplied by $1-\frac1p$. Alternatively, thanks to the prime counting theorem, we can say that on the $n$th roll the probability to observe a prime is about $\frac{1}{\log n}$.
Now suppose we have rolled a large prime $p = 1\pmod {10}$. We have to look only at the rolls which are $=1,3,7,9 \pmod{10}$. Denote the probability to roll the next prime on those rolls as $r$; it is approximately equal to $\frac{10}{\varphi(10)\log p} = \frac{5}{2\log p}$, but it will only matter for us that it is small. The probabilities to get residues $3,7,9,1$ modulo $10$ for the next prime are then respectively equal to
\begin{align}
p_3 & = r + (1-r)^4 r + (1-r)^8 r +\dots = \frac{r}{1-(1-r)^4},\\
p_7  & = (1-r) r + (1-r)^5 r + (1-r)^9 r + \dots = \frac{r(1-r)}{1-(1-r)^4} = (1-r)p_3,\\
p_9 & = (1-r)^2p_3,\\ p_1 & = (1-r)^3 p_3.
\end{align}
Despite the probabilities are different, as you have mentioned, the difference becomes less and less noticeable. And no way it should be as remarkable as observed by the authors!
Another observation is that with probabilistic model we would have $$p_7/p_3 = p_9/p_7 = p_1/p_9 = 1-r.$$ However, the authors of the article find that in reality $$p_7/p_3>1,\ p_9/p_7 \approx 0.725,\ p_1/p_9 \approx 0.85.$$ So their finding does somehow contradict a random model for primes; you will find more details in the article.


TITLE: When does $\int^{\pi/2}_{0}\csc^{r}xdx$ exist?
QUESTION [1 upvotes]: I was trying to find the values of $r>0$ for which the integral
$$\int^{\pi/2}_{0}\csc^{r}x\,\mathrm{d}x$$
exists. Unfortunately, I'm short on ideas on how this could be done. If this may serve as any guidance, to be crude, I tried punching different values for $r$ in Mathematica, and it looks like we are looking for $r\in(0,1)$. In any case, I would be thankful for advice on how we can determine and prove that.

REPLY [0 votes]: Note that the problem with the integrand is at $x=0$. Using the fact that $\sin(x) \approx x$ as $x \rightarrow0 $, then $\frac{1}{\sin(x)^r} \approx \frac{1}{x^r}$. Now, you can derive some conditions on $r$.


text:
\begin{document}
\maketitle

\par\noindent
\begin{small}

\par\noindent
{\bf Abstract}
\newline
In this paper, we consider continuous-time quantum walks (CTQWs) on finite graphs determined by the Laplacian matrices. By introducing fully interconnected graph decomposition of given graphs, we show a decomposition method for the Laplacian matrices. Using the decomposition method, we show several conditions for graph structure which return probability of CTQW tends to 1 while the number of vertices tends to infinity.

\footnote[0]{
{\it Keywords: }
Continuous-time quantum walk, Laplacian matrix, Decomposition, Localization
}
\end{small}

\setcounter{equation}{0}

\section{Introduction}

Quantum walks (QWs) have been attractive research topic in this decade \cite{Konno2008b, VAndraca2012, ManouchehriWang2013} as quantum counterparts of the random walks which play important roles in various fields. For QWs, there are two types of time evolution, discrete-time and continuous-time. In this paper, we focus on continuous-time quantum walks (CTQWs) on finite graphs. There are a lot of studies of CTQWs on various deterministic graphs, such as the line \cite{Konno2005}, path graph \cite{Godsil2013}, star graph \cite{Salimi2009, Xu2009}, cycle graph \cite{abtw2003,ikkk2005,MuelkenBlumen2006}, dendrimers \cite{mbb2006}, spidernet graphs \cite{Salimi2010QIP}, the dual Sierpinski gasket \cite{abm2008}, direct product of Cayley graphs \cite{SalimiJafarizadeh2009}, quotient graphs \cite{Salimi2008IJQI}, odd graphs \cite{Salimi2008IJTP}, trees \cite{Konno2006IDAQP,JafarizadehSalimi2007} and ultrametric spaces \cite{Konno2006IJQI}. Also there are studies of CTQWs on probabilistic graphs, such as small-world networks \cite{mpb2007}, Erd\H{o}s-R\'enyi random graph \cite{XuLiu2008} and the threshold network model \cite{IdeKonno2010, KirklandSeverini2011}.

Here we give the definition of our CTQW.  Let $G_{n}$ be a simple (undirected) graph with $n$ numbers of vertices. In this paper, we use $V(G_{n})=\{1,\ldots,n\}$ for the vertex set and $E(G_{n})\subset V(G_{n})\times V(G_{n})$ for the edge set of the graph $G_{n}$. For a pair of vertices $i,j\in V(G_{n})$, we write $i\sim j$ if $(i,j)\in E(G_{n})$, i.e., the pair of vertices $i$ and $j$ is connected by an edge. Let $A_{G_{n}}$ be the adjacency matrix of the graph $G_{n}$ which is an $n\times n$ matrix whose $(i,j)$ component $(A_{G_{n}})_{i,j}$ equals $1$ if $i\sim j$ and $0$ otherwise. The Laplacian matrix $L_{G_{n}}$ of $G_{n}$ is defined by $L_{G_{n}}=D_{G_{n}}-A_{G_{n}}$ where $D_{G_{n}}$ be the $n\times n$ diagonal matrix given by $D_{G_{n}}=\mathrm{diag}(d_{G_{n}}(1),\ldots ,d_{G_{n}}(n))$ with $d_{G_{n}}(i)=\sum _{j=1}^{n}(A_{G_{n}})_{i,j}$, i.e., the degree of the vertex $i$, for $i\in V(G_{n})$.

The time evolution operator $U_{G_{n},t}$ of a CTQW on $G_{n}$ at time $t\geq 0$ is defined by

\begin{eqnarray}\label{defU}
U_{G_{n},t}\equiv e^{\sqrt{-1}tL_{G_{n}}}= \sum _{k=0}^{\infty }\frac{(\sqrt{-1}t)^{k}}{k!}L_{G_{n}}^{k},
\end{eqnarray}

where $\sqrt{-1}$ be the imaginary unit. Let $\{\Psi _{G_{n},t}\}_{t\geq 0}$ be the probability amplitude of the quantum walk, i.e.,
$
\Psi _{G_{n},t}=U_{G_{n},t}\Psi _{G_{n},0},
$
where
$
\Psi _{G_{n},0}=
{}^{T}\!
\begin{bmatrix}
\Psi _{G_{n},0}(1) & \ldots & \Psi _{G_{n},0}(n)
\end{bmatrix}
$
is an $n$ dimensional unit vector which we call the initial condition where ${}^TA$ is the transpose of a matrix $A$. Then the probability that the quantum walker on $G_{n}$ is in position $y\in V(G_{n})$
at time $t$ with initial condition $\Psi _{G_{n},0}$ is defined by

\begin{eqnarray*}
\PM(Y_{G_{n},t}^{\Psi _{G_{n},0}}=y)\equiv |(U_{G_{n},t}\Psi _{G_{n},0})(y)|^{2},
\end{eqnarray*}

where $Y_{G_{n},t}^{\Psi _{G_{n},0}}$ be the random variable representing the quantum walker' s position at time $t$ on $G_{n}$ with initial condition ${\Psi _{G_{n},0}}$. In this paper, we only deal with $\Psi _{G_{n},0}(x)=1$ for some specific vertex $x\in V(G_{n})$ and $\Psi _{G_{n},0}(x^{\prime })=0$ for $x^{\prime} \neq x$ case. Note that this corresponds to the case that the walker starts from the vertex $x$.  Hereafter, we use $P_{G_{n},t}^{x}(y)$ instead of $\PM(Y_{G_{n},t}^{\Psi _{G_{n},0}}=y)$ for simplicity.

In this paper, we call strong localization for $x\in V(G_{n})$ occur when the return probability tends to $1$ in $n\to \infty$, i.e.,

\begin{align*}
\lim_{n\to \infty }P_{G_{n},t}^{x}(x)=1.
\end{align*}

It is known that CTQWs defined by the Laplacian matrix on complete graphs (see e.g. \cite{Konno2008b}), star graphs\cite{Salimi2009, Xu2009} and the threshold network model \cite{IdeKonno2010, KirklandSeverini2011} have the same transition probabilities from the vertices which connect with all other vertices and also strong localization for the vertices occur. But it seems that there are no comprehensive treatments for relationships between graph structure and the transition probabilities of such graphs.

The aim of this paper is to clarify relationships between graph structure and the transition probabilities of CTQWs on graphs. In order to do so, we introduce fully interconnected graph decomposition (Definition \ref{defFID}) which is a generalization of the graph operation ``join'' in Sec.\ 2. We should note that the decomposition procedure for the Laplacian matrix proposed in Sec.\ 2 is motivated by Merris' s work \cite{Merris1994, Merris1998}. After that we derive a decomposition formula for transition probabilities of CTQW with related to the decomposition (Lemma \ref{lem:transition}). As a consequence, we find that the limit of the return probabilities of the CTQW on graph with the decomposition starting from a vertex in a growing subgraph are equal to that of the subgraph (Theorem \ref{thm:localization}). This means that local subgraph structure can cause localization in the whole graph. We show two concrete examples of CTQWs which cause strong localization for some vertices in Sec.\ 3. The first one (Sec. 3.1) includes complete graphs, star graphs and the threshold network model cases. The second one (Sec. 3.2) shows that growing clique can cause the strong localization. It can be interesting future problems that to find necessary and sufficient condition of graph structure for the strong localization and to build a discrete-time version of this decomposition method.

\section{Fully interconnected graph decomposition}

In this paper, we consider the following decomposition of the graph $G_{n}$:

\begin{Def}[Fully interconnected graph decomposition]\label{defFID}
Let $G_{n}$ be a simple graph. Then $(G_{n_{1}},\ldots G_{n_{k}})$ is said to be a fully interconnected graph decomposition of $G_{n}$ if it satisfies the following conditions:
\begin{enumerate}
\item
Each $G_{n_{i}}$ is an induced subgraph of $G_{n}$, i.e., if $v\sim w$ in $G_{n}$ then $v\sim w$ in $G_{n_{i}}$ for all $v,w\in V(G_{n_{i}})\subset V(G_{n})$, on $n_{i}$ numbers of vertices for $i=1,\ldots k$.
\item
$V(G_{n})=V(G_{n_{1}})\cup \cdots \cup V(G_{n_{k}})$ and $V(G_{n_{i}})\cap V(G_{n_{j}})=\emptyset $ for $i\neq j$.
\item
For each pair of subgraphs $(G_{n_{i}},G_{n_{j}})$ for $i\neq j$, one of the following conditions is hold:
\begin{enumerate}
\item
All pairs of vertices $(v,w)\in V(G_{n_{i}})\times V(G_{n_{j}})$ are connected. In this case, we call the pair of subgraphs $(G_{n_{i}},G_{n_{j}})$ is fully interconnected and represent $G_{n_{i}}\sim G_{n_{j}}$.
\item
All pairs of vertices $(v,w)\in V(G_{n_{i}})\times V(G_{n_{j}})$ are disconnected. In this case, we call the pair of subgraphs $(G_{n_{i}},G_{n_{j}})$ is fully interdisconnected and represent $G_{n_{i}}\nsim G_{n_{j}}$.
\end{enumerate}
\end{enumerate}
\end{Def}

Remark that $(G_{n})$ is a trivial fully interconnected graph decomposition of $G_{n}$.

Now we consider a ($k$ blocks $\times$ $k$ blocks) block matrix $\widetilde{L}_{G_{n}}$ of $G_{n}$ with a fully interconnected graph decomposition $(G_{n_{1}},\ldots G_{n_{k}})$ defined as follows:

\begin{align}\label{eqblock}
(\widetilde{L}_{G_{n}})_{i,j\ \mathrm{block}}=
\begin{cases}
\widetilde{d}_{i}I_{n_{i}}, &\text{if $i=j$},\\
-J_{n_{i},n_{j}}, &\text{if $G_{n_{i}}\sim G_{n_{j}}$},\\
O_{n_{i},n_{j}}, &\text{otherwise},
\end{cases}
\end{align}

where $\widetilde{d}_{i}=\sum _{G_{n_{i}}\sim G_{n_{j}}}n_{j}$, $I_{n}$ is the $n\times n$ identity matrix, $J_{l,m}$ is $l\times m$ all $1$ matrix and $O_{l,m}$ is $l\times m$ all $0$ matrix. The Laplacian matrix $L_{G_{n}}$ of $G_{n}$ with related to a fully interconnected graph decomposition $(G_{n_{1}},\ldots G_{n_{k}})$ is decomposed into two ($k$ blocks $\times$ $k$ blocks) block matrices as follows:

\begin{align}\label{eqdecompose}
L_{G_{n}}=\mathrm{diag}(L_{G_{n_{1}}},\ldots ,L_{G_{n_{k}}})+\widetilde{L}_{G_{n}}.
\end{align}

In order to analyze the time evolution operator of CTQW, we discuss about the eigenspace of $L_{G_{n}}$. Let $\{\lambda_{i,l_{i}}\}_{l_{i}=1,\ldots ,n_{i}-1}$ be the eigenvalues of $L_{G_{n_{i}}}$ except for the trivial eigenvalue $0$ corresponding to $n_{i}$ dimensional all $1$ vector $\mathbf{1}_{n_{i}}$ for $i=1,\ldots ,k$. The corresponding eigenvectors $\{\mathbf{v}_{i,l_{i}}\}_{l_{i}=1,\ldots ,n_{i}-1}$ can be $n_{i}$ dimensional real unit vectors and orthogonal to each other and orthogonal to $\mathbf{1}_{n_{i}}$ since each  $L_{G_{n_{i}}}$ is an real symmetric matrix. By Eqs.\ (\ref{eqblock}), (\ref{eqdecompose}), if we define

\begin{align*}
\mathbf{w}_{i,l_{i}}={}^{T}\!
[
\overbrace{0,\ldots ,0}^{n_{1}+\cdots +n_{i-1}}, \mathbf{v}_{i,l_{i}}(1), \ldots , \mathbf{v}_{i,l_{i}}(n_{i}), \overbrace{0,\ldots ,0}^{n_{i+1}+\cdots +n_{k}}
],\quad \text{($l_{i}=1,\ldots ,n_{i}-1$)},
\end{align*}

for $i=1,\ldots ,k$, where $\mathbf{v}_{i,l_{i}}(j)$ denotes the $j$-th component of $\mathbf{v}_{i,l_{i}}$, then it is easy to see that

\begin{align*}
L_{G_{n}}\mathbf{w}_{i,l_{i}}=\left(\mathrm{diag}(L_{G_{n_{1}}},\ldots ,L_{G_{n_{k}}})+\widetilde{L}_{G_{n}}\right)\mathbf{w}_{i,l_{i}}=(\lambda _{i,l_{i}}+\widetilde{d}_{i})\mathbf{w}_{i,l_{i}}.
\end{align*}

Thus we have $(n-k)$ numbers of eigenvalues and corresponding orthonormal eigenvectors of $L_{G_{n}}$ from the Laplacian matrices $L_{G_{n_{i}}}\ (i=1,\ldots ,k)$ of subgraphs $G_{n_{1}},\ldots ,G_{n_{k}}$.

The remaining  $k$ numbers of eigenvectors are corresponding to all $1$ vectors $\mathbf{1}_{n_{1}},\ldots, \mathbf{1}_{n_{k}}$. Let

\begin{align}\label{eqconstvec}
\mathbf{x}_{i}={}^{T}\!
[
\overbrace{\alpha_{i}(1),\ldots ,\alpha_{i}(1)}^{n_{1}}, \overbrace{\alpha_{i}(2),\ldots ,\alpha_{i}(2)}^{n_{2}}, \ldots , \overbrace{\alpha_{i}(k),\ldots ,\alpha_{i}(k)}^{n_{k}}
],
\end{align}

for $i=1,\ldots ,k$, where $\alpha _{i}(1),\ldots ,\alpha _{i}(k)\in \RM$. Then we have

\begin{align*}
L_{G_{n}}\mathbf{x}_{i}=\left(\mathrm{diag}(L_{G_{n_{1}}},\ldots ,L_{G_{n_{k}}})+\widetilde{L}_{G_{n}}\right)\mathbf{x}_{i}=\widetilde{L}_{G_{n}}\mathbf{x}_{i}.
\end{align*}

Note that from Eqs.\ (\ref{eqblock}), (\ref{eqconstvec}), the eigen equations $\widetilde{L}_{G_{n}}\mathbf{x}_{i}=\nu _{i}\mathbf{x}_{i}$ are equivalent to $\overline{L}_{G_{n}}\overline{\mathbf{x}}_{i}=\nu _{i}\overline{\mathbf{x}}_{i}$ with a $k\times k$ matrix $\overline{L}_{G_{n}}$ such that

\begin{align*}
\left(\overline{L}_{G_{n}}\right)_{i,j}=
\begin{cases}
\widetilde{d}_{i}, &\text{if $i=j$},\\
-n_{j}, &\text{if $G_{n_{i}}\sim G_{n_{j}}$},\\
0, &\text{otherwise},
\end{cases}
\end{align*}

and a $k$-dimensional vector

\begin{align*}
\overline{\mathbf{x}}_{i}={}^{T}\!
[
\alpha _{i}(1),\ldots ,\alpha _{i}(k)
].
\end{align*}

Because we can take the set of eigenvectors as an orthonormal base,  the following matrix $B_{G_{n}}$ can be an orthogonal matrix:

\begin{align*}
B_{G_{n}}\equiv
\left[
\mathbf{w}_{1,1},\ldots ,\mathbf{w}_{1,n_{1}-1}, \ldots ,\mathbf{w}_{k,1},\ldots ,\mathbf{w}_{k,n_{k}-1}, \frac{\mathbf{x}_{1}}{\sqrt{\sum _{l=1}^{k}n_{l}\alpha _{1}(l)^{2}}},\ldots ,\frac{\mathbf{x}_{k}}{\sqrt{\sum _{l=1}^{k}n_{l}\alpha _{k}(l)^{2}}}
\right].
\end{align*}

After diagonalization of the time evolution operator $U_{G_{n},t}$ of CTQW on $G_{n}$ (Eq.\ (\ref{defU})) by using $B_{G_{n}}$, we have the following spectoral decomposition of $U_{G_{n},t}$:

\begin{align*}
&\left(U_{G_{n},t}\right)_{x,y}\notag\\
&=
\begin{cases}
\displaystyle\sum _{j=1}^{n_{i}-1}\exp\left\{\sqrt{-1}t(\lambda _{i,j}
+
\widetilde{d}_{i})\right\}\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)\\
+
\displaystyle\sum _{j=1}^{k}\exp\left(\sqrt{-1}t\nu _{j}\right)\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}
&\text{if $x,y\in V(G_{n_{i}})$},
\\
\\
\displaystyle\sum _{j=1}^{k}\exp\left(\sqrt{-1}t\nu _{j}\right)\frac{\alpha _{j}(i)\alpha _{j}(i^{\prime })}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}
&\text{if $x\in V(G_{n_{i}})$ and $y\in V(G_{n_{i^{\prime }}})$ ($i\neq i^{\prime }$)}.
\end{cases}
\end{align*}

Therefore we have the transition probabilities of CTQW as follows:

\begin{lem}\label{lem:transition}
Let $(G_{n_{1}}, \ldots ,G_{n_{k}})$ be a fully interconnected graph decomposition of a graph $G_{n}$. Then the transition probabilities of CTQW are given as follows:
\begin{align}\label{expressU2}
&P_{G_{n},t}^{x}(y)\notag\\
&=
\left|\left(U_{G_{n},t}\right)_{x,y}\right|^{2}\notag\\
&=
\begin{cases}
P_{G_{n_{i}},t}^{x}(y)
+
\widetilde{P}_{G_{n_{i}},t}^{x}(y)\\
-
\displaystyle\frac{1}{n_{i}^{2}}
-
\frac{2}{n_{i}}\sum _{j=1}^{n_{i}-1}\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)\cos(t\lambda _{i,j})\\
+
2\displaystyle\sum _{j=1}^{n_{i}-1}\sum _{j^{\prime }=1}^{k}\frac{\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)\alpha _{j^{\prime }}(i)^{2}\cos\left\{t(\lambda _{i,j}+\widetilde{d}_{i}-\nu _{j^{\prime }})\right\}}{\sum _{l=1}^{k}n_{l}\alpha _{j^{\prime }}(l)^{2}}
&\text{if $x,y\in V(G_{n_{i}})$},
\\
\\
\widetilde{P}_{G_{n_{i}},G_{n_{i^{\prime }}},t}^{x}(y)
&\text{if $x\in V(G_{n_{i}})$ and $y\in V(G_{n_{i^{\prime }}})$ ($i\neq i^{\prime }$)}.
\end{cases}
\end{align}

where
\begin{align}
P_{G_{n_{i}},t}^{x}(y)
&=
\displaystyle\sum _{j=1}^{n_{i}-1}\mathbf{v}_{i,j}(x)^{2}\mathbf{v}_{i,j}(y)^{2}

+
\frac{1}{n_{i}^{2}}\notag\\
&+
2\displaystyle\sum _{1\leq j<j^{\prime }\leq n_{i}-1}\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)\mathbf{v}_{i,j^{\prime }}(x)\mathbf{v}_{i,j^{\prime }}(y)\cos\left\{t(\lambda _{i,j}-\lambda _{i,j^{\prime }})\right\}\notag\\
&+
\displaystyle\frac{2}{n_{i}}\displaystyle\sum _{j=1}^{n_{i}-1}\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)\cos(t\lambda _{i,j}),
\notag\\
\widetilde{P}_{G_{n_{i}},t}^{x}(y)
&=
\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{4}}{\left(\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}\right)^{2}}
+
2\displaystyle\sum _{1\leq j<j^{\prime }\leq k}\frac{\alpha _{j}(i)^{2}\alpha _{j^{\prime }}(i)^{2}\cos\left\{t(\nu _{j}-\nu _{j^{\prime }})\right\}}{\left(\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}\right)\left(\sum _{l=1}^{k}n_{l}\alpha _{j^{\prime }}(l)^{2}\right)},
\label{defptildeni}\\
\widetilde{P}_{G_{n_{i}},G_{n_{i^{\prime }}},t}^{x}(y)
&=
\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{2}\alpha _{j}(i^{\prime })^{2}}{\left(\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}\right)^{2}}
+
2\displaystyle\sum _{1\leq j<j^{\prime }\leq k}\frac{\alpha _{j}(i)\alpha _{j}(i^{\prime })\alpha _{j^{\prime }}(i)\alpha _{j^{\prime }}(i^{\prime })\cos\left\{t(\nu _{j}-\nu _{j^{\prime }})\right\}}{\left(\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}\right)\left(\sum _{l=1}^{k}n_{l}\alpha _{j^{\prime }}(l)^{2}\right)}.
\notag
\end{align}
\end{lem}

The first term $P_{G_{n_{i}},t}^{x}(y)$ in Eq.\ (\ref{expressU2}) is the transition probability of CTQW on the graph $G_{n_{i}}$. The second term $\widetilde{P}_{G_{n_{i}},t}^{x}(y)$ and the last term $\widetilde{P}_{G_{n_{i}},G_{n_{i^{\prime }}},t}^{x}(y)$ are the transition probabilities determined only by $\widetilde{L}_{G_{n}}$ which is not depend on the detailed structures of the subgraphs $G_{n_{1}}, \ldots ,G_{n_{k}}$. Because the number of vertices $n_{i}$ in $G_{n_{i}}$ plays an important role in Theorem \ref{thm:localization}, we explicitly describe $n_{i}$ in Eqs.\ (\ref{expressU2}) and  (\ref{defptildeni}). The following theorem shows that the terms in Eq.\ (\ref{expressU2}) except for $P_{G_{n_{i}},t}^{x}(y)$ vanish in $n_{i}\to \infty $ for return probability cases $(x=y)$:

\begin{thm}\label{thm:localization}
Let $(G_{n_{1}}, \ldots ,G_{n_{k}})$ be a fully interconnected graph decomposition of a graph $G_{n}$. If $\lim_{n_{i}\to \infty }P_{G_{n_{i}},t}^{x}(x)$ with $x\in V(G_{n_{i}})$ exists then

\begin{align*}
\lim_{n_{i}\to \infty }P_{G_{n,t}}^{x}(x)=\lim_{n_{i}\to \infty }P_{G_{n_{i}},t}^{x}(x).
\end{align*}

\end{thm}

(Proof of Theorem \ref{thm:localization})
\\
From $B_{G_{n}}\!{}^{T}\!B_{G_{n}}=I_{n}$, we have

\begin{align}\label{eqorth1}
\sum _{j=1}^{n_{i}-1}\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)
+
\sum _{j=1}^{k}
\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}
=
\begin{cases}
1 &\text{if $x=y$,}\\
0 &\text{otherwise,}
\end{cases}
\end{align}

for $x,y\in V(G_{n_{i}})$, and also we have

\begin{align}\label{eqorth2}
\sum _{j=1}^{n_{i}-1}\mathbf{v}_{i,j}(x)\mathbf{v}_{i,j}(y)
+
\frac{1}{n_{i}}
=
\begin{cases}
1 &\text{if $x=y$,}\\
0 &\text{otherwise,}
\end{cases}
\end{align}

for $x,y\in V(G_{n_{i}})$ because $\{\mathbf{v}_{i,l_{i}}\}_{l_{i}=1,\ldots ,n_{i}-1}\cup \{\frac{1}{\sqrt{n_{i}}}\mathbf{1}_{n_{i}}\}$ is a set of orthonormal eigenvectors of $L_{G_{n_{i}}}$. Combining Eqs.\ (\ref{eqorth1}) and (\ref{eqorth2}), we obtain

\begin{align}\label{eqorth3}
\sum _{j=1}^{k}
\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}
=\frac{1}{n_{i}}.
\end{align}

In particular, we obtain the following uniform bound from Eq.\ (\ref{eqorth3}):

\begin{align}\label{eqorth4}
\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}
\leq \frac{1}{n_{i}}\quad \text{for $\forall i,j\in \{1,\dots k\}$}.
\end{align}

By substituting Eq.\ (\ref{eqorth3}) into Eq.\ ({\ref{defptildeni}}) and using Eq.\ (\ref{eqorth4}), we have

\begin{align*}
\widetilde{P}_{G_{n_{i}},t}^{x}(y)
&=
\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{4}}{\left(\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}\right)^{2}}
+
2\displaystyle\sum _{1\leq j<j^{\prime }\leq k}\frac{\alpha _{j}(i)^{2}\alpha _{j^{\prime }}(i)^{2}\cos\left\{t(\nu _{j}-\nu _{j^{\prime }})\right\}}{\left(\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}\right)\left(\sum _{l=1}^{k}n_{l}\alpha _{j^{\prime }}(l)^{2}\right)}\notag\\
&\leq
\frac{1}{n_{i}}\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}
+
2\left(\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}\right)^{2}
=
\frac{3}{n_{i}^{2}}.
\end{align*}

On the other hand, by using Eqs.\ (\ref{eqorth1}) and (\ref{eqorth3}), we have

\begin{align*}
\frac{2}{n_{i}}\sum _{j=1}^{n_{i}-1}\mathbf{v}_{i,j}(x)^{2}\cos(t\lambda _{i,j})
&\leq
\frac{2}{n_{i}}\left(1-\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}\right)
=\frac{2}{n_{i}}\left(1-\frac{1}{n_{i}}\right),
\label{estpn1}
\\
2\displaystyle\sum _{j=1}^{n_{i}-1}\sum _{j^{\prime }=1}^{k}\frac{\mathbf{v}_{i,j}(x)^{2}\alpha _{j^{\prime }}(i)^{2}\cos\left\{t(\lambda _{i,j}+\widetilde{d}_{i}-\nu _{j^{\prime }})\right\}}{\sum _{l=1}^{k}n_{l}\alpha _{j^{\prime }}(l)^{2}}
&\leq
2\left(1-\displaystyle\sum _{j=1}^{k}\frac{\alpha _{j}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j}(l)^{2}}\right)\displaystyle\sum _{j^{\prime }=1}^{k}\frac{\alpha _{j^{\prime }}(i)^{2}}{\sum _{l=1}^{k}n_{l}\alpha _{j^{\prime }}(l)^{2}}\notag\\
&=
\frac{2}{n_{i}}\left(1-\frac{1}{n_{i}}\right).
\end{align*}

As a consequence, we have the following estimation on the return probabilities:

\begin{align*}
\left|P_{G_{n,t}}^{x}(x)-P_{G_{n_{i}},t}^{x}(x)\right|\leq \frac{4}{n_{i}},
\end{align*}
for $x\in V(G_{n_{i}})$. This implied that

\begin{align*}
\lim_{n_{i}\to \infty }P_{G_{n,t}}^{x}(x)=\lim_{n_{i}\to \infty }P_{G_{n_{i}},t}^{x}(x),
\end{align*}

if $\lim_{n_{i}\to \infty }P_{G_{n_{i}},t}^{x}(x)$ exists.
\\
\qed

\section{Local subgraph structure can cause localization}

In this section, we show two examples of CTQWs which cause strong localization for some vertices.

\subsection{Graphs with dominating vertices}

In this paper, we call a vertex $i\in V(G_{n})$ ``dominating vertex'' if $d(i)=n-1$, i.e., the vertex is connected with all other vertices in $V(G_{n})$. If there are $n_{d}$ numbers of dominating vertices in $G_{n}$, then the dominating vertices form a complete graph $K_{n_{d}}$ on $n_{d}$ numbers of vertices as an induced subgraph of $G_{n}$ (In other words, the induced subgraph of all dominating vertices is a clique $K_{n_{d}}$). In this case, $G_{n}$ is devided into two subgraphs $K_{n_{d}}$ and $G_{n-n_{d}}$ the induced subgraph with the vertex set $V(G_{n})\setminus V(K_{n_{d}})$. It is easy to see that $(K_{n_{d}},\ G_{n-n_{d}})$ is a fully interconnected graph decomposition of $G_{n}$. Therefore, we can apply Lemma \ref{lem:transition} with $k=2,\ G_{n_{1}}=K_{n_{d}},\ G_{n_{2}}=G_{n-n_{d}},\  \widetilde{d}_{1}=n-n_{d},\  \widetilde{d}_{2}=n_{d}$.

The eigenvalues $\{\lambda _{1,l_{1}}\}_{l_{1}=1,\ldots ,n_{d}}$ and corresponding orthonormal eigenvectors $\{\mathbf{v}_{1,l_{1}}\}_{l_{1}=1,\ldots ,n_{d}}$ of $L_{K_{n_{d}}}$ are know as follows:

\begin{align*}
&\lambda_{1,l_{1}}=n_{d},
\quad
\mathbf{v}_{1,l_{1}}=
\frac{1}{\sqrt{l_{1}(l_{1}+1)}}
\begin{bmatrix}
\mathbf{1}_{l_{1}}\\
-l_{1}\\
\mathbf{0}_{n-l_{1}-1}
\end{bmatrix}
\quad (l_{1}=1,\ldots ,n_{d}-1),\\
&\lambda_{1,n_{d}}=0,
\quad
\mathbf{v}_{1,n_{d}}=
\frac{1}{\sqrt{n_{d}}}\ \mathbf{1}_{n_{d}},
\end{align*}

where $\mathbf{0}_{n}$ is the $n$ dimensional all zero vector. On the other hand, it is easy to see that the eigenvalues $\nu _{1}, \nu _{2}$ and corresponding eigenvectors $\mathbf{x}_{1}, \mathbf{x}_{2}$ are given as follows:

\begin{align*}
&\nu _{1}=n,
\quad
\mathbf{x}_{1}=
\begin{bmatrix}
(n-n_{d})\mathbf{1}_{n_{d}}\\
-n_{d}\mathbf{1}_{n-n_{d}}
\end{bmatrix}
\\
&\nu _{2}=0,
\quad
\mathbf{x}_{2}=\mathbf{1}_{n}.
\end{align*}

This shows that $\alpha _{1}(1)=n-n_{d},\  \alpha _{1}(2)=-n_{d},\  \alpha _{2}(1)=\alpha _{2}(2)=1$. Therefore from Eq.\ (\ref{expressU2}), we have the following result:

\begin{pro}[Dominating vertices can cause strong localization]\label{pro:dominating}
Let $G_{n}$ be a graph with arbitrary numbers of dominating vertices. If we consider CTQW starting from a dominating vertex $x$ then
\begin{align*}
P_{G_{n},t}^{x}(y)
=
\begin{cases}
\displaystyle1-\frac{2}{n}\left(1-\frac{1}{n}\right)(1-\cos nt)
&\text{if $x=y$},
\\
\displaystyle\frac{2}{n^{2}}(1-\cos nt)
&\text{if $x\neq y$}.
\end{cases}
\end{align*}
Therefore
\begin{align*}
\lim_{n\to \infty }P_{G_{n},t}^{x}(x)=1.
\end{align*}
\end{pro}

\begin{rem}
Proposition \ref{pro:dominating} shows that if we consider the CTQW defined by the Laplacian matrix on complete graph then strong localization always occur for all vertices. Because complete graphs, star graphs and the threshold network model have dominating vertices, then CTQWs starting from dominating vertices on these graphs have the same transition probabilities.
\end{rem}

\subsection{Graphs with growing clique}

In this subsection, we show another sufficient condition for strong localization. Suppose $G_{n}$ includes a clique $K_{n_{c}}$. A vertex $v\in K_{n_{c}}$ is said to be a gateway vertex when there exist at least one edge $(v,w)\in E(G_{n})$ with $w\in V(G_{n})\setminus V(K_{n_{c}})$.

\begin{pro}[Clique can cause strong localization]\label{pro:clique}
Suppose $G_{n}$ includes a clique $K_{n_{c}}$. Let $n_{g}$ be the number of gateway vertices in $K_{n_{c}}$ and $\{i_{1}, \ldots ,i_{n_{g}}\}\subset K_{n_{c}}$ be the set of all gateway vertices in $K_{n_{c}}$. If $x\in V(K_{n_{c}})\setminus \{i_{1}, \ldots ,i_{n_{g}}\}$ and $(n_{c}-n_{g})\to \infty $, then

\begin{align*}
\lim_{n\to \infty }P_{G_{n},t}^{x}(x)=1.
\end{align*}

\end{pro}

(Proof of Proposition \ref{pro:clique})\\
By the assumption, $(K_{n_{c}-n_{g}}, \{i_{1}\}, \ldots , \{i_{n_{g}}\}, G_{n-n_{c}})$ is a fully interconnected graph decomposition of the graph $G_{n}$, where $K_{n_{c}-n_{g}}$ be the clique with the vertex set $V(K_{n_{c}})\setminus \{i_{1}, \ldots ,i_{n_{g}}\}$ and $G_{n-n_{c}}$ be the induced subgraph with the vertex set $V(G_{n})\setminus V(K_{n_{c}})$. By Proposition \ref{pro:dominating}, we can see that
\begin{align*}
\lim_{(n_{c}-n_{g})\to \infty }P_{K_{n_{c}-n_{g}},t}^{x}(x)=1.
\end{align*}
Therefore, by the virtue of Theorem \ref{thm:localization}, we have desired result.
\qed

\par
\
\par\noindent
{\bf Acknowledgments.}

This work was supported by the Grant-in-Aid for Young Scientists (B) of Japan Society for the Promotion of Science (Grant No. 23740093). The author thank professors Norio Konno, Iwao Sato and Etsuo Segawa for fruitful discussions on this topic.

\begin{small}

config: arxiv


TITLE: Comparing two numbers given their factorization
QUESTION [11 upvotes]: I'm not an expert, but given the integer factorization of two numbers $a,b$:
$$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$

What is the time and space compexity of checking if $a > b$ ?

Suppose that the factors and the exponents are given in binary and the whole input over alphabet $\{0,1,\wedge,;,*\}$ looks like:
$$p_{i_1}\wedge{a_1}*...*p_{i_n}\wedge{a_n};p_{j_1}\wedge{b_1}*...*p_{j_m}\wedge{b_m}$$
What algorithms can be used?

REPLY [9 votes]: According to this paper from 2013 by Etessami, Stewart, and Yannakakis, the time complexity of the [a priori] harder problem where the $p_k$ are not required to be prime is still open.  In that paper the authors show that certain conjectures in number theory would imply that the simple algorithm ("compute enough bits of the logs") runs in polynomial time.  The authors also observe that unconditional on any conjectures the algorithm runs in polynomial time for fixed $m$ and $n$ by Baker's Theorem.  Of course, it is possible that the version of the problem with $p_k$ prime is strictly easier than the more general one.


TITLE: Transitive group action- a problem from representation theory of finite groups by Steinberg
QUESTION [0 upvotes]: Let $\sigma:G\rightarrow S_X$  be a transitive group action with $|X|\geq 2$. If $x\in X$, denote $G_x$ as the stabiliser of $x$ in $G$.
Show that if $G_x$ is transitive on $X\setminus\{x\}$ for some $x\in X$, then $G_x$ is transitive on $X\setminus\{x\}$ for every $x\in X$.
I tried to show it by means of contraposition but it didn't workout. Help will really be appreciated. Thanks in advance!!

REPLY [0 votes]: To simplify notation, I will write $g \cdot x$ for the image of $x \in X$ under $\sigma(g)$ with $g \in G$.
Suppose that $G_x$ is transitive on $X \setminus \{x\}$, and let $y \in X$. By transitivity there exists $g \in G$ such that $g \cdot x = y$. Now let $u,v \in Y \setminus \{ y \}$. Then $g^{-1}\cdot u,\, g^{-1} \cdot v \in X \setminus \{ x \}$, so there exists $h \in G_x$ such that $hg^{-1} \cdot u = g^{-1} \cdot v$. Hence $ghg^{-1} \cdot u = v$ and $ghg^{-1} \in G_y$, so we have shown that $G_y$ is transitive on $Y \setminus \{y\}$.