TITLE: Solving an equation in the complex field - radius of circle
QUESTION [0 upvotes]: I have a problem which is really easy but for some reason I don't understand what's going on here.
The assignment says: Solve the following equation in the field of complex numbers: $$z^4 -16=0$$ and present the solutions in the complex plane.
Now obviously I did this: $$z = \sqrt[4]{16}$$ which can be solved with
$$\sqrt[n]{w} = r\large {e}^{i\frac{\LARGE{\phi + 2k\pi}}{\LARGE{n}}}, k=0,1,2...n-1$$
So as my complex number is $16$, the magnitude or $r$ of this complex number is also 16, right? Which would mean that the radius of my circle in the complex plane is also 16, but in the solutions it is $2$. I get the angles right and I generally know how to operate with complex numbers but I can't figure out where I am wrong here.

REPLY [0 votes]: $16$ is the magnitude or $z^4$, so the magnitude of $z$ is $2$. We have in polar coordinates $$z^4=16=2^4=2^4e^{2ik\pi}, \space\space k\in\mathbb Z$$
so $$z=2e^{i\frac{k\pi}{2}}, k\in\mathbb Z$$
which has only $4$ different values for $k\in\mathbb Z$, that is for $k=0,1,2$ and $3$.


text:
\subsection{Proof of Theorem \ref{thm:spectral_lower}}\label{sec:pf-spec2}

To prove Theorem \ref{thm:spectral_lower}, we need two additional lemmas. The first lemma can be viewed as a reverse version of the inequality in Lemma \ref{lem:anderson}.

\begin{lemma}\label{lem:anderson_lower_bound}
Suppose $\wh{r}$ is a rank vector induced by $\wh{\theta}$, we then have
$$\h_k(\wh{r},r^*) \geq \frac{1}{k}\max_{t\in\mathbb{R}}\min\left(\sum_{i:r^*_i\leq k}\indc{\wh{\theta}_i< t} , \sum_{i:r^*_i>k}\indc{\wh{\theta}_i> t}\right).$$
The inequality holds for any $r^*\in\S_n$.
\end{lemma}
\begin{proof}
Following the proof of Lemma \ref{lem:anderson}, we have
\begin{eqnarray}
\nonumber 2k\h_k(\wh{r},r^*) &=& 2\max\left(\sum_{i=1}^k\indc{\wh{r}_i>k},\sum_{i=k+1}^n\indc{\wh{r}_i\leq k}\right) \\
\nonumber &\geq & 2\max\left(\sum_{i=1}^k\indc{\wh{\theta}_i<\theta_{(k+1)}},\sum_{i=k+1}^n\indc{\wh{\theta}_i>\theta_{(k)}}\right) \\
\label{eq:some-t_lower_spectral} &\geq& 2\min_t\max\left(\sum_{i=1}^k\indc{\wh{\theta}_i< t},\sum_{i=k+1}^n\indc{\wh{\theta}_i> t}\right)\\
\label{eq:any-t_lower_spectral} &=& 2\max_t\min\left(\sum_{i=1}^k\indc{\wh{\theta}_i< t},\sum_{i=k+1}^n\indc{\wh{\theta}_i> t}\right).
\end{eqnarray}
where (\ref{eq:some-t_lower_spectral}) and (\ref{eq:any-t_lower_spectral}) follow the same argument that leads to (\ref{eq:some-t}) and (\ref{eq:any-t}).
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:spectral_lower}]
We first note that condition (\ref{eq:spec-lower-condition}) necessarily implies $\Delta =o(1)$. Throughout the proof, we assume

$\kappa =\Omega(1)$ and there exists some $\delta_1 = o(1)$ such that
\begin{align}

\frac{\sqrt{(1+\delta_1)\overline{\snr}}}{2} - \frac{1}{\sqrt{(1+ \delta_1)\overline{\snr}}} \log \frac{n-k}{k} \rightarrow\infty.\label{eqn:overline_SNR_infty}
\end{align}
The case with

$\kappa =o(1)$ or $\overline{\snr}$ not satisfying (\ref{eqn:overline_SNR_infty}) will be addressed at the end of the proof.

Choose $\kappa_1,\kappa_2\geq 0$ such that we have both $\kappa_1+\kappa_2\leq \kappa$ and
\begin{align*}
\frac{k\psi'(\kappa_1)(1+e^{\kappa_1})^2+(n-k)\psi'(\kappa_2)(1+e^{-\kappa_2})^2}{(k\psi(\kappa_1)+(n-k)\psi(-\kappa_2))^2/n} = \overline{V}(\kappa).
\end{align*}
Let $\rho=o(1)$ be a vanishing number that will be specified later. Since $k\rightarrow\infty$ and $\kappa=\Omega(1)$, one can easily check that $\kappa_2=\Omega(1)$. Define $\theta^*_i=\kappa_1$ for all $1\leq i\leq k-\rho k$, $\theta^*_i=0$ for $k-\rho k<i\leq k$, $\theta^*_i=-\Delta$ for $k<i\leq k+\rho(n-k)$ and $\theta^*_i=-\kappa_2$ for $k+\rho(n-k)< i\leq n$. For the simplicity of proof, we choose $\rho$ so that both $\rho k$ and $\rho(n-k)$ are integers. Define $r^*$ to be $r^*_i = i,\forall i\in[n]$. Then we have
$$\sup_{\substack{r\in\S_n\\\theta\in\Theta(k,\Delta,\kappa)}}\mathbb{E}_{(\theta,r)}\h_k(\wh{r},r) \geq \mathbb{E}_{(\theta^*,r^*)}\h_k(\wh{r},r^*).$$
We will utilize several results established in the proof of Theorem \ref{thm:spectral-ranking}. Define
\begin{align}
\eta = \frac{1}{2} - \frac{\overline{V}(\kappa)}{(1+{\bar \delta})\Delta^2npL}\log\frac{n-k}{k},\label{eqn:spectral_lower_eta_def}
\end{align}
for $\bar \delta =o(1)$.
The specific choice of $\bar \delta$ will be specified later in the proof.
Also define  $t=\frac{e^{(1-\eta)\theta_k^*+\eta\theta_{k+1}^*}}{\sum_{j=1}^ne^{\theta_j^*}} = \frac{e^{-\eta \Delta}}{\sum_{j=1}^ne^{\theta_j^*}}$. Then, by Lemma \ref{lem:anderson_lower_bound}, we have
\begin{align*}

\h_k(\wh{r},r^*) & \geq  \frac{1}{k}\min\left(\sum_{i=1}^k\indc{\wh{\pi}_i< t},\sum_{i=k+1}^n\indc{\wh{\pi}_i> t}\right) \\
& \geq  \frac{1}{k}\min\left(\sum_{k-\rho k  <i \leq k}\indc{\wh{\pi}_i< t},\sum_{k< i \leq k + \rho(n-k)}\indc{\wh{\pi}_i> t}  \right).
\end{align*}
For any $\delta>0$, define the function $\phi(\delta) = \frac{\sqrt{(1+\delta)\overline{\snr}}}{2}-\frac{1}{\sqrt{(1+\delta)\overline{\snr}}}\log\frac{n-k}{k}$.
It suffices to show there exists some

constant $C>0$ such that
\begin{align}
&\mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k-\rho k  <i \leq k}\indc{\wh{\pi}_i< t} \geq Ck\exp\left(-\frac{\phi(\bar\delta)^2}{2} \right) \right) \geq 1-o(1) ,\label{eqn:H_lower_1}\\
\text{and }& \mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k< i \leq k + \rho(n-k)}\indc{\wh{\pi}_i> t} \geq Ck\exp\left(-\frac{\phi(\bar\delta)^2}{2} \right) \right) \geq 1-o(1).\label{eqn:H_lower_2}
\end{align}
Suppose both inequalities hold, we have
$$\mathbb{P}_{(\theta^*,r^*)}\left(\h_k(\wh{r},r^*) > 0\right) \geq 1-o(1).$$
By Markov's inequality, we also have
\begin{align*}
 &\mathbb{E}_{(\theta^*,r^*)}\h_k(\wh{r},r^*) \geq  C\exp\left(-\frac{\phi(\bar\delta)^2}{2} \right) \mathbb{P}_{(\theta^*,r^*)}\left(\h_k(\wh{r},r^*)  \geq C\exp\left(-\frac{\phi(\bar\delta)^2}{2} \right) \right)

 \geq  \frac{C}{2} \exp\left(-\frac{\phi(\bar\delta)^2}{2} \right).
\end{align*}
Therefore, we obtain the desired conclusions.

\indent In the rest of the proof, we are going to establish (\ref{eqn:H_lower_1}).

 Recall the definition of $\bar \pi$  in (\ref{eqn:pi_bar_def}).
For any $k-\rho k<i\leq k$, define the event $\mathcal{F}$ as
\begin{align*}
\mathcal{F}_i = \left\{\frac{|\wh{\pi}_i-\bar{\pi}_i|}{ \pi^*_i} \leq  \delta_0(1-e^{-\eta\Delta}) \text{ and } \left|\frac{\sum_{j\in[n]\backslash\{i\}}A_{ji}\bar{y}_{ji}}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)}-1\right| \leq  \delta_0\right\}.
\end{align*}
Using a similar argument that leads to (\ref{eq:pi-hat-bar-approx}) and (\ref{eq:easy-de-pi}), we can show that there exists some $\delta_0=o(1)$ not dependent on $\bar \delta$, such that
\begin{equation}
\mathbb{P}_{(\theta^*,r^*)} (\mathcal{F}_i) \geq 1-\left(  O(n^{-4})+\exp\left(-\eta^2\Delta^2npL\frac{np}{\log n}\right)+\exp\left(-\eta^2\Delta^2npL\sqrt{\frac{npL}{\log n}}\right)   \right). \label{eq:indi-F-i}
\end{equation}
Suppose $\mathcal{F}_i$ holds, we then have
\begin{align}
\indc{\wh \pi_i < t  } & =  \indc{\wh \pi_i < \frac{e^{(1-\eta)\theta_k^*+\eta\theta_{k+1}^*}}{\sum_{j=1}^ne^{\theta_j^*}}  } \nonumber     \\
&  = \indc{\frac{\wh{\pi}_i-\pi_i^*}{\pi_i^*} \leq e^{(1-\eta)\theta_k^*+\eta\theta_{k+1}^*-\theta_i^*}-1    } \nonumber    \\
&  = \indc{\frac{\wh{\pi}_i-\pi_i^*}{\pi_i^*} \leq e^{-\eta\Delta}-1   } \nonumber    \\
& \geq \indc{\frac{\bar{\pi}_i-\pi_i^*}{\pi_i^*}\leq -(1+ \delta_0)(1-e^{-\eta\Delta})  } \nonumber    \\
& \geq  \indc{\frac{\sum_{j\in[n]\backslash\{i\}}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \leq -(1+ \delta_0)^2(1-e^{-\eta\Delta}) }  \nonumber  \\
& \geq \indc{\frac{\sum_{j\in[n]\backslash\{i\}}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \leq -(1+ \delta_0)^2\eta\Delta }.\label{eqn:spectral_lower_L}
\end{align}
We use the notation $L_i$ for the indicator function on the right hand side of (\ref{eqn:spectral_lower_L}).
In other words, we have shown that
\begin{eqnarray*}
\sum_{k-\rho k<i\leq k}\indc{\wh \pi_i < t  } &\geq& \sum_{k-\rho k<i\leq k}L_i\mathbb{I}_{\mathcal{F}_i} \\
&\geq& \sum_{k-\rho k<i\leq k}L_i - \sum_{k-\rho k<i\leq k}\mathbb{I}_{\mathcal{F}_i^c}.
\end{eqnarray*}
By (\ref{eq:indi-F-i}), we have
$$\mathbb{E}\left(\sum_{k-\rho k<i\leq k}\mathbb{I}_{\mathcal{F}_i^c}\right)\leq O(n^{-3}) + \rho k\exp\left(-\eta^2\Delta^2npL\frac{np}{\log n}\right)+\rho k\exp\left(-\eta^2\Delta^2npL\sqrt{\frac{npL}{\log n}}\right).$$
Since the above bounds is of smaller order than $k\exp\left(-\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\left(\frac{np}{\log n}\right)^{1/4}\right)$, we can use Markov's inequality and obtain
\begin{equation}
\mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k-\rho k<i\leq k}\mathbb{I}_{\mathcal{F}_i^c} \leq k\exp\left(-\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\left(\frac{np}{\log n}\right)^{1/4}\right)\right) \geq 1-o(1). \label{eq:etos}
\end{equation}
To lower bound $\sum_{k-\rho k<i\leq k}L_i$, we define
\begin{align}
\mathcal{A} = \Bigg\{A: \forall k-\rho k < i \leq k, &\left|\frac{\sum_{j\in[n]\backslash\{i\}}A_{ij}\psi'(\theta_i^*-\theta_j^*)\left(1+e^{\theta_j^*-\theta_i^*}\right)^2}{p\sum_{j\in[n]\backslash\{i\}}\psi'(\theta_i^*-\theta_j^*)\left(1+e^{\theta_j^*-\theta_i^*}\right)^2}-1\right|\leq \delta_0,\label{eqn:A_1} \\
& \left|\frac{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)}{p\sum_{j\in[n]\backslash\{i\}}\psi(\theta_j^*-\theta_i^*)}-1\right|\leq  \delta_0 ,\label{eqn:A_2}\\
& \abs{\sum_{k-\rho k< j <k}A_{ji}\psi'(\theta_i^*-\theta_j^*)(1+e^{\theta_j^*-\theta_i^*})^2 }\leq 2\rho kp + 10\log n \Bigg\}.\label{eqn:A_3}
\end{align}

By Bernstein's inequality and union bound, we have $\mathbb{P}(A\in \mathcal{A})\geq 1- O(n^{-3})$. From now on, we use the notation $\mathbb{P}_A$ for the conditional probability $\mathbb{P}_{(\theta^*,r^*)}(\cdot|A)$ given $A$.
For any $s>0$,
\begin{align}
\mathbb{P}_{(\theta^*,r^*)}&\left(\sum_{k-\rho k  <i \leq k}L_i \geq s \right) \geq  \mathbb{P}(A\in\mathcal{A}) \inf_{A\in \mathcal{A}}\mathbb{P}_{A}\left(\sum_{k-\rho k  <i \leq k}L_i \geq s \right).  \label{eqn:spectral_final_1}
\end{align}
To study  $\mathbb{P}_{A}\left(\sum_{k-\rho k  <i \leq k}L_i \geq s \right)$, we define the set $S = \cbr{i\in[n]: i\leq k-\rho k \text{ or }i > k}$.

Note that for each $k-\rho k  <i \leq k$, we have $L_i \geq L_{i,1}- L_{i,2}-L_{i,3}$, where
\begin{align*}
L_{i,1} & =\indc{\frac{\sum_{j\in S}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \leq -(1+2\delta')(1+ \delta_0)^2\eta\Delta} \\
L_{i,2} & = \indc{\frac{\sum_{k-\rho k< j <i}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \geq \delta'(1+\delta_0)^2\eta\Delta}\\
L_{i,3} & = \indc{\frac{\sum_{ i <j \leq k}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \geq \delta'(1+\delta_0)^2\eta\Delta},
\end{align*}
for some $\delta'=o(1)$ whose value will be determined later. We are going to control each term separately.

\textbf{(1).}
Analysis of $L_{i,1}$. Note that conditional on $A$, $\{L_{i,1}\}_{k-\rho k <i \leq k}$ are all independent Bernoulli random variables. We have $L_{i,1} \sim \text{Bernoulli}(p_i)$, where $p_i = \E_{(\theta^*,r^*)} (L_{i,1}| A)$. By Chebyshev's inequality, we have
\begin{align*}
\mathbb{P}_{A}\left(\sum_{k-\rho k <i \leq k}L_{i,1} \geq \frac{1}{2} \sum_{k-\rho k <i \leq k}p_{i}\right) \geq 1-\frac{4}{\sum_{k-\rho k <i \leq k}p_{i}}.
\end{align*}
By Lemma \ref{lem:spectral_lower_tail_prop} stated and proved at the end of the section, we can lower bound each $p_i$ by
\begin{align}
p_i &= \p_{A} \left(\frac{\sum_{j\in S}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \leq -(1+2\delta')(1+\delta_0)^2\eta\Delta\right)   \nonumber\\
& \geq C_1\exp\left(-\frac{(1+\delta_2)\eta^2\Delta^2npL}{2\overline{V}(\kappa)} - C_1' \eta \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}}\right),\nonumber
\end{align}
for some constants $C_1,C_1'>0$ and some $\delta_2 = o(1)$ that are not dependent on $\eta$. By (\ref{eqn:overline_SNR_infty}), there exists some $\delta_3=o(1)$ such that
\begin{align}
\sum_{k-\rho k < i\leq k } p_i \geq  C_1k\exp\left(-\frac{(1+\delta_3)\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right).\label{eqn:p_i_lower_bound}
\end{align}
To obtain (\ref{eqn:p_i_lower_bound}), we need to set $\rho$ that tends to zero sufficiently slow so that it can be absorbed into the exponent.
Note that condition (\ref{eq:spec-lower-condition}) is equivalent to $\frac{(1+\epsilon)\overline{\snr}}{2} \left(\frac{1}{2} - \frac{1}{(1+\epsilon)\overline{\snr}} \log \frac{n-k}{k}\right)^2 < \log k$.
Since $\epsilon$ is a constant, it implies
\begin{align*}
\frac{\overline{\snr}}{2} \left(\frac{1}{2} - \frac{1}{(1+\bar \delta)\overline{\snr}} \log \frac{n-k}{k}\right)^2 < (1-\epsilon')^{-1}\log k,
\end{align*}
for some constant $\epsilon'>0$.
As a result, under the condition that $k \rightarrow\infty$, we have
\begin{align*}
\sum_{k-\rho k < i\leq k }p_i \geq \sum_{k-\rho k < i\leq k } C_1\exp\left( -(1+\delta_3)(1-\epsilon')\log k \right) \geq k^\frac{\epsilon'}{2}\rightarrow\infty.
\end{align*}

Hence, we have proved
\begin{align*}
\inf_{A\in \mathcal{A}}\mathbb{P}_{A}\left(\sum_{k-\rho k  <i \leq k}L_{i,1} \geq  \frac{1}{2}C_1k\exp\left(-\frac{(1+\delta_2)\eta^2\Delta^2npL}{2\overline{V}(\kappa)} - C_1' \eta \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}}\right)  \right) \geq  1- o(1).
\end{align*}

\textbf{(2).} Analysis of $L_{i,2}$. By (\ref{eqn:A_1})-(\ref{eqn:A_3}) and Bernstein's inequality, we can bound $\E (L_{i,2}|A)$ by
\begin{align*}
& \exp\left( - \frac{\left(\delta'(1+\delta_0)^2\eta\Delta L \sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)   \right)^2}{2 \left( L \sum_{k-\rho k< j <i}A_{ji}\psi'(\theta_i^*-\theta_j^*)(1+e^{\theta_j^*-\theta_i^*})^2  + \frac{1}{3}\delta'(1+\delta_0)^2\eta\Delta L  \sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)   \right)}\right)\\
&\leq \exp\left( - \frac{\left(\delta'(1+\delta_0)^2\eta\Delta L \sum_{j\in[n]\backslash\{i\}}p\psi(\theta_j^*-\theta_i^*)   \right)^2}{4 \left( 2L \rho kp +10\log n  + \frac{1}{3}\delta'(1+\delta_0)^2\eta\Delta L  \sum_{j\in[n]\backslash\{i\}}p\psi(\theta_j^*-\theta_i^*)   \right)}\right).
\end{align*}
Now we set $\delta' = \max\{\rho^\frac{1}{2},\Delta^\frac{4}{3}, \left(\frac{\log n}{np}\right)^\frac{1}{2}\}$.

Then, there exists some constant $C_2,C_3>0$ such that
$$
\E (L_{i,2}|A) \leq \exp\left(-C_2\rho^{-\frac{1}{2}}npL \eta^2\Delta^2\right) \leq \exp\left(-C_3\rho^{-1/2}\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right).
$$
Then,
$$
\E \left(\sum_{k-\rho k < i \leq k}L_{i,2}\Bigg|A\right) \leq \rho k\exp\left(-C_3\rho^{-1/2}\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right).
$$
By Markov inequality, we have
\begin{equation}
\inf_{A\in \mathcal{A}}\mathbb{P}_{A}\left(\sum_{k-\rho k  <i \leq k}L_{i,2} \geq \rho k  \exp\left(-\frac{1}{2}C_3\rho^{-1/2}\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right) \right) \leq \exp\left(-\frac{1}{2}C_3\rho^{-1/2}\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right). \label{eqn:L_i2_upper}
\end{equation}

\textbf{(3).} Analysis of $L_{i,3}$. By a similar argument, we also have
\begin{equation}
\inf_{A\in \mathcal{A}}\mathbb{P}_{A}\left(\sum_{k-\rho k  <i \leq k}L_{i,3} \geq \rho k  \exp\left(-\frac{1}{2}C_3\rho^{-1/2}\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right) \right) \leq \exp\left(-\frac{1}{2}C_3\rho^{-1/2}\frac{\eta^2\Delta^2npL}{2\overline{V}(\kappa)}\right). \label{eqn:L_i3_upper}
\end{equation}

~\\
\indent Now we can combine the above analyses of $L_{i,1}$, $L_{i,2}$ and $L_{i,3}$.
Since $\rho=o(1)$, the bounds (\ref{eqn:L_i2_upper}) and (\ref{eqn:L_i3_upper}) are of smaller order than (\ref{eqn:p_i_lower_bound}). We have
\begin{align}
\inf_{A\in \mathcal{A}}\mathbb{P}_{A}\left(\sum_{k-\rho k  <i \leq k}L_i \geq C_4k\exp\left(-\frac{(1+\delta_2)\eta^2\Delta^2npL}{2\overline{V}(\kappa)} - C_1' \eta \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}}\right) \right)\geq 1-o(1),\label{eqn:k_1}
\end{align}
for some constant $C_4 >0$. Then  (\ref{eq:etos}) and (\ref{eqn:spectral_final_1}) lead to
\begin{align}
\mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k-\rho k  <i \leq k}\indc{\wh{\pi}_i <t}\geq C_4k\exp\left(-\frac{(1+\delta_2)\eta^2\Delta^2npL}{2\overline{V}(\kappa)} - C_1' \eta \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}}\right) \right)\geq 1-o(1).\label{eqn:k_1_1}
\end{align}

We are going to show it leads to (\ref{eqn:H_lower_1}) by selecting an appropriate $\bar \delta$ as follows. We write $\eta=\eta_{\bar\delta} = \frac{1}{2} - \frac{\overline{V}(\kappa)}{(1+{\bar\delta})\Delta^2npL}\log\frac{n-k}{k}$ to make the dependence on $\bar{\delta}$ explicit. Recall that $\delta_2$ and $C_1'$ are independent of the $\bar \delta$ in the definition of $\eta_{\bar \delta}$. First we can let $\bar\delta > \delta_1$, then we have
\begin{align*}
\frac{(1+\delta_2)\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)} + C_1' \eta_{\bar \delta} \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}} &\leq \left( 1+ \delta_2 + 2C'_1 \left(\eta_{\bar \delta}\frac{\Delta^2npL}{\overline{V}(\kappa)}\right)^{-\frac{1}{2}}\right)\frac{\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)} \\
& \leq \left( 1+ \delta_2 + 2C'_1 \left(\eta_{ \delta_1}\frac{\Delta^2npL}{\overline{V}(\kappa)}\right)^{-\frac{1}{2}}\right)\frac{\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)}\\
&\leq \left(1+\delta_4\right)\frac{\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)},
\end{align*}
for some $\delta_4=o(1)$ not dependent on $\bar\delta$. Here the second inequality is due to the fact that $\eta_\delta$ is in increasing function of $\delta$, and the last inequality is due to (\ref{eqn:overline_SNR_infty}). Then we can let $\bar \delta \geq \delta_4$ to have the above expression to be upper bounded by $\left(1+\bar\delta\right)\frac{\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)}$. Hence, (\ref{eqn:k_1_1}) leads to
\begin{align}
\mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k-\rho k  <i \leq k}\indc{\wh{\pi}_i <t} \geq C_4k\exp\left(-\frac{(1+\bar\delta)\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)} \right)  \right)\geq 1-o(1),\label{eqn:k_2}
\end{align}
witch establishes (\ref{eqn:H_lower_1}).

\indent Similar to (\ref{eqn:k_1_1}), we can establish
\begin{align*}
&\mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k< i \leq k+\rho(n-k)}\indc{\wh{\pi}_i >t} \geq C_4(n-k)\exp\left(-\frac{(1+\delta_2)(1-\eta_{\bar \delta})^2\Delta^2npL}{2\overline{V}(\kappa)} - C_1' (1-\eta_{\bar \delta}) \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}}\right) \right)\\
&\geq 1-o(1).
\end{align*}
Due to (\ref{eqn:overline_SNR_infty}), we have $(1-\eta_{\bar \delta})\in[0,1]$, then
\begin{align*}
\frac{(1+\delta_2)(1-\eta_{\bar \delta})^2\Delta^2npL}{2\overline{V}(\kappa)} + C_1' (1-\eta_{\bar \delta}) \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}} & \leq \frac{(1+\delta_2)(1-\eta_{\bar \delta})^2\Delta^2npL}{2\overline{V}(\kappa)} + C_1' \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}} \\
& \leq   \left(1+\delta_5\right)\frac{(1-\eta_{\bar \delta})^2\Delta^2npL}{2\overline{V}(\kappa)},
\end{align*}
for some $\delta_5=o(1)$ not dependent on $\bar \delta$.
Since $(1-\eta_{\bar \delta})^2\Delta^2npL/(2\overline{V}(\kappa)) = \eta_{\bar \delta}^2\Delta^2npL/(2\overline{V}(\kappa))  + 2\log\frac{n-k}{k}/(1+\bar\delta)$, we have
\begin{align*}
&(n-k)\exp\left(-\frac{(1+\delta_2)(1-\eta_{\bar \delta})^2\Delta^2npL}{2\overline{V}(\kappa)} - C_1' \eta_{\bar \delta} \sqrt{\frac{\Delta^2npL}{\overline{V}(\kappa)}}\right) \\
& \geq k \exp\left( \log \frac{n-k}{k}-\left(1+\delta_5\right)\frac{(1-\eta_{\bar \delta})^2\Delta^2npL}{2\overline{V}(\kappa)}\right) \\
& = k \exp\left( \frac{\bar \delta - \delta_5}{1+\bar \delta}\log \frac{n-k}{k}-\left(1+\delta_5\right)\frac{\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)}\right).
\end{align*}
By letting $\bar \delta \geq \delta_5$ and using the same argument as in obtaining (\ref{eqn:k_2}), we have
\begin{align}
\mathbb{P}_{(\theta^*,r^*)}\left(\sum_{k< i \leq k+\rho(n-k)}\indc{\wh{\pi}_i >t} \geq C_4k\exp\left(-\frac{(1+\bar\delta)\eta_{\bar \delta}^2\Delta^2npL}{2\overline{V}(\kappa)} \right)  \right)\geq 1-o(1),\label{eqn:k_3}
\end{align}
which establishes (\ref{eqn:H_lower_2}).
To sum up, we can choose $\bar \delta = \max\{\delta_1,\delta_4,\delta_5\}$ to

establish (\ref{eqn:H_lower_1}) and (\ref{eqn:H_lower_2}).

\indent The above proof assumes that

$\kappa=\Omega(1)$ and $\overline{\snr}$ satisfies (\ref{eqn:overline_SNR_infty}). When these two conditions do not hold, we need to slightly modify the argument.  When (\ref{eqn:overline_SNR_infty}) is not satisfied, there must exist some small constant $\bar\epsilon>0$ such that $\frac{\sqrt{(1+\bar \epsilon)\overline{\snr}}}{2} - \frac{1}{\sqrt{(1+\bar \epsilon)\overline{\snr}}} \log \frac{n-k}{k} =O(1)$. We can then take $\rho$ to be a sufficiently small constant, and the proof will go through with some slight modification.
When $\kappa=o(1)$, we can simply construct $\theta^*$ by $\theta_i^*=0$ for $1\leq i\leq k$ and $\theta_i^*=-\Delta$ for $k+1\leq i\leq n$.

\end{proof}

Finally, we state and prove Lemma \ref{lem:spectral_lower_tail_prop} to close this section.

\begin{lemma}\label{lem:spectral_lower_tail_prop}

Assume $\frac{np}{\log n}\rightarrow\infty$, $\kappa =O(1)$, $\rho=o(1)$, $k\to\infty$ and  (\ref{eq:spec-lower-condition}) holds for some arbitrarily small constant $\epsilon>0$. Choose $\kappa_1,\kappa_2\geq 0$ such that we have both $\kappa_1+\kappa_2\leq \kappa$ and
$$\frac{k\psi'(\kappa_1)(1+e^{\kappa_1})^2+(n-k)\psi'(\kappa_2)(1+e^{-\kappa_2})^2}{(k\psi(\kappa_1)+(n-k)\psi(-\kappa_2))^2/n}=\overline{V}(\kappa).$$
Define $\theta_i^*=\kappa_1$ for all $1\leq i\leq k-\rho k$, $\theta_i^*=0$ for $k-\rho k<i\leq k$, $\theta_i^*=-\Delta$ for $k+1\leq i\leq k+\rho(n-k)$ and $\theta_i^*=-\kappa_2$ for $k+\rho(n-k)< i\leq n$ and $S = \cbr{i\in[n]: i\leq k-\rho k \text{ or }i > k}$.

There exists some constants $C_1>0$ such that for any $\tilde{\delta}=o(1)$, there exists $C_2>0$ and $\delta_1=o(1)$ such that for any $\eta<1/2$ and any $A\in\mathcal{A}$ where $\mathcal{A}$ is defined in (\ref{eqn:A_1})-(\ref{eqn:A_3}), we have
\begin{align}
 &\p \left(\frac{\sum_{j\in S}A_{ji}(\bar{y}_{ij}-\psi(\theta_i^*-\theta_j^*))(1+e^{\theta_j^*-\theta_i^*})}{\sum_{j\in[n]\backslash\{i\}}A_{ji}\psi(\theta_j^*-\theta_i^*)} \leq -(1+\tilde{\delta}) \eta\Delta\Bigg| A\right)   \nonumber\\
& \geq C_1\exp\left(-\frac{1+\delta_1}{2}\eta_+^2\overline{\snr}-C_2\eta_{+}\sqrt{\overline{\snr}}\right).\label{eqn:spectral_lower_tail_prop}
\end{align}
for any $k-\rho k<i\leq k$.
\end{lemma}
\begin{proof}
We suggest readers to go through the proof of Lemma \ref{lem:two_point_testing_lower} in Section \ref{sec:partial-lower-pf} first.
The proof of Lemma \ref{lem:spectral_lower_tail_prop} basically follows that of Lemma \ref{lem:two_point_testing_lower}. We will omit repeated details in the proof of Lemma \ref{lem:two_point_testing_lower} and only present key steps and calculations specific to this Lemma \ref{lem:spectral_lower_tail_prop}.

 We denote $q_j=\psi(\theta_i-\theta_j)$. Then $1+e^{\theta_j^*-\theta_i^*}=1/q_j$ and $ \psi(\theta_j-\theta_i)=1-q_j$. Then what we need to  lower bound can be written as
\begin{align*}
\p_A\left(\sum_{\ell\in[L]}\sum_{j\in S}A_{ji}\frac{q_j-y_{ij\ell}}{q_j}\geq Lt'\right),
\end{align*}
where $t'=(1+\delta^\prime)\eta\Delta\sum_{j\in[n]\backslash\{i\}}p(1-q_j)$ for some $\delta^\prime=o(1)$ due to (\ref{eqn:A_1})-(\ref{eqn:A_3}), and $\p_A$ is the conditional probability given $A$. Note that  $\delta^\prime$ can be chosen independent of $\eta$. We remark that
$$\overline{\snr}=(1+\delta^{\prime\prime})\frac{L\Delta^2(\sum_{j\in[n]\backslash\{i\}}p(1-q_j))^2}{\sum_{j\in S}p\frac{1-q_j}{q_j}}$$
due to $\rho=o(1)$ for some $\delta^{\prime\prime}=o(1)$ independent of $\eta$.
We  still first consider the regime when
\begin{align}
\eta\sqrt{\overline{\snr}}\rightarrow\infty,\label{eqn:spectral_lower_tail_prop_1}
\end{align}
This implies $\eta\in(0,1/2)$.

The conditional cumulant of $\sum_{j\in S}A_{ji}\frac{q_j-y_{ijl}}{q_j}$ for each $l\in[L]$ is
\begin{align*}
&\nu(u)=\sum_{j\in S}A_{ji}\log\left(q_j e^{\frac{u(q_j-1)}{q_j}}+(1-q_j)e^{u}\right)=\sum_{j\in S}A_{ji}\left[-u\frac{1-q_j}{q_j}+\log((1-q_j)e^{u/q_j}+q_j)\right].
\end{align*}
The function $\nu(u)$ acts as the same role as $K(u)$ in the proof of Lemma \ref{lem:two_point_testing_lower}.
Define
$$u^*=\arg\min_{u\geq0}\left(L\nu(u)-uLt^\prime\right).$$
Its first derivative is
\begin{align*}
\nu^\prime(u)&=\sum_{j\in S}A_{ji}\left[\frac{\frac{(1-q_j)}{q_j}e^{u/q_j}}{(1-q_j)e^{u/q_j}+q_j}-\frac{1-q_j}{q_j}\right].
\end{align*}
Following the same argument in the proof of Lemma \ref{lem:two_point_testing_lower}, we need to pin down a range for $u^*$. First due to (\ref{eqn:spectral_lower_tail_prop_1}) and $\nu^\prime(0)=0$, we have $t^\prime>0$ and thus $\nu^\prime(0)-t^\prime<0$.
Now for $u=o(1)$, we can approximate $\nu^\prime(u)$ by Taylor expansion and obtain
\begin{align}
1-\delta_2\leq\frac{\nu^\prime(u)}{\overline{\nu^\prime}(u)}\leq1+\delta_2,\label{eqn:nu_prime_bar}
\end{align}
for some $0<\delta_2=o(1)$,
where $\overline{\nu^\prime}(u)=\sum_{j\in S}p\frac{1-q_i}{q_i}u$. Note that we can replace $A_{ji}$ by $p$ because of the condition $A\in\mathcal{A}$.  Then we consider $\tilde{u}=\frac{2t^\prime}{\sum_{j\in S}p\frac{1-q_i}{q_i}}$, which is $o(1)$ since $\Delta=o(1)$ and $\rho=o(1)$. Therefore,
\begin{align*}
&\nu^\prime(\tilde{u})-t^\prime\geq(1-\delta_2)\overline{\nu^\prime}(\tilde{u})-t^\prime=(1-\delta_2)t^\prime>0.
\end{align*}
This implies that $u^*\in\left(0, \frac{2t^\prime}{\sum_{j\in S}p\frac{1-q_i}{q_i}}\right)$. Thus $u^*=o(1)$.

When $u=o(1)$, $\nu(u)$ also follows a second order Taylor expansion such that:
$$1-\delta_3\leq\frac{\nu(u)}{\bar{\nu}(u)}\leq1+\delta_3,$$
where $\bar{\nu}(u)=\frac{1}{2}\sum_{j\in S}p\frac{1-q_j}{q_j}u^{2}$ and $\delta_3=o(1)$ due to (\ref{eqn:A_1})-(\ref{eqn:A_3}).

Following the change-of-measure argument in the proof of Lemma \ref{lem:two_point_testing_lower}, the probability of interest can be lower bounded by
$$\exp\left(-u^*T+L\nu(u^*)-Lu^*t^\prime\right)\mathbb{Q}_A\left(0\leq\sum_{l=1}^L\sum_{j\in S}Z_{jl}-Lt^\prime\leq T\right),$$
where $\mathbb{Q}_A$ is a measure under which $Z_{jl}$ are all independent given $A$ and follow
$$\mathbb{Q}_A(Z_{jl}=s)=e^{A_{ji}u^*s-A_{ji}\nu_j(u^*)}\p_A\left(A_{ji}\frac{q_j-y_{ijl}}{q_j}=s\right)$$
and $\nu_j(u)=-u\frac{1-q_j}{q_j}+\log((1-q_j)e^{u/q_j}+q_j)$. Then for each $Z_{jl}$ such that $A_{ij}=1$, its second and 4th moment under $\mathbb{Q}_A$ can be analyzed:
\begin{align}
\mathbb{Q}_A((Z_{jl}-\mathbb{Q}_A(Z_{jl}))^2)=\nu_j^{\prime\prime}(u^*)=\frac{1-q_j}{q_j}\frac{e^{u^*/q_j}}{[(1-q_j)e^{u^*/q_j}+q_j]^2}\in(C_1^\prime, C_2^\prime),\label{eq:spectral-second}
\end{align}
\begin{align}
\mathbb{Q}_A((Z_{jl}-\mathbb{Q}_A(Z_{jl}))^4)=\nu_j^{\prime\prime\prime\prime}(u^*)+3\nu_j^{\prime\prime}(u^*)\leq(3+C_4^\prime)\nu_j^{\prime\prime}(u^*)\leq C_3^\prime,\label{eq:spectral-fourth}
\end{align}
where (\ref{eq:spectral-fourth}) comes from
\begin{align*}
&\nu_j^{\prime\prime\prime\prime}(u)=\frac{1-q_j}{q_j^3}e^{u/q_j}\frac{(1-q_j)^3e^{3u/q_j}-3(1-q_j)^2q_je^{2u/q_j}-3(1-q_j)q_j^2e^{2u/q_j}+q_j^3}{[(1-q_j)e^{u/q_j}+q_j]^5}\\
&\leq\max_{j\in S}1/q_j^2\nu^{\prime\prime}(u)\leq C_4^\prime\nu^{\prime\prime}(u).
\end{align*}

Now, to lower bound $L\nu(u^*)-Lu^*t^\prime$:
\begin{align}
\nonumber&L\nu(u^*)-Lu^*t^\prime\geq L(1-\delta_3)\frac{1}{2}\sum_{j\in S}p\frac{1-q_j}{q_j}u^{*2}-Lu^*t^\prime\\
\label{eqn:spectral_minimization}&\geq L\min_{u\in(0,1)}\left[(1-\delta_3)\frac{1}{2}\sum_{j\in S}p\frac{1-q_j}{q_j}u^{*2}-u^*t^\prime\right]\\
\nonumber&\geq-\frac{1}{2}\frac{Lt^{\prime2}}{(1-\delta_3)\sum_{j\in S}p\frac{1-q_j}{q_j}}\\
\nonumber&\geq-\frac{1+\delta_4}{2}\eta^2\overline{\snr},
\end{align}
where (\ref{eqn:spectral_minimization}) is achieved at
$u=\frac{t^\prime}{(1-\delta_3)\sum_{j\in S}p\frac{1-q_j}{q_j}}$ and $\delta_4=o(1)$ since $\rho=o(1)$. This gives us the desired exponent. We remark that $\delta_4$ is independent of $\eta$.

To choose $T$, observe that
$$\Var_{\mathbb{Q}_A}\left(\sum_{l\in[L]}\sum_{j\in S}Z_{jl}\right)\leq \tilde{C}_1npL,$$
for some constant $\tilde{C}_1>0$ using (\ref{eqn:A_1}) - (\ref{eqn:A_3}) , (\ref{eq:spectral-second}) and $\rho=o(1)$. Thus we choose $T=\sqrt{\tilde{C}_1npL}$, which leads to a term $C_2\eta\sqrt{\overline{\snr}}$ in the exponent for some $C_2>0$ independent of $\eta$.

Finally, to lower bound the $\mathbb{Q}_A$ measure, we only need to verify the vanishing property of the 4th moment approximation bound in Lemma \ref{lem:CLT-stein}:
\begin{align}
\nonumber&\sqrt{L\sum_{j\in S}A_{ji}\left(\frac{\mathbb{Q}_A((Z_{j1}-\mathbb{Q}_A(Z_{j1})^4)}{(L\sum_{j\in S}A_{ji}\mathbb{Q}_A((Z_{j1}-\mathbb{Q}_A(Z_{j1})^2))^2}\right)^{3/4}}\\
&\leq \tilde{C}_2(npL)^{-1/4}\label{eq:spectral-clt}
\end{align}
where (\ref{eq:spectral-clt}) is by (\ref{eq:spectral-second}),   (\ref{eq:spectral-fourth}) and $\rho=o(1)$. To summarize, we have proved
$$\p_A\left(\sum_{l\in[L]}\sum_{j\in S}A_{ji}\frac{q_j-y_{ijl}}{q_j}\geq Lt'\right)\geq C_1\exp\left(-\frac{1+\delta_5}{2}\eta^2\overline{\snr}-C_2\eta\sqrt{\overline{\snr}}\right)$$
for some constant $C_1,C_2>0$ and $\delta_5=o(1)$, when (\ref{eqn:spectral_lower_tail_prop_1}) holds. This $\delta_5$ can be used as the $\delta_1$ in (\ref{eqn:spectral_lower_tail_prop}). We remark that $C_1,C_2, \delta_5$ are all independent of $\eta$.

Finally, when
$$\eta\sqrt{\overline{\snr}}\leq C_3$$
for some constant $C_3>0$. This condition, together with (\ref{eqn:A_1})-(\ref{eqn:A_3}) and $\rho=o(1)$, implies that
$$Lt^\prime\leq C_4\sqrt{L\sum_{j\in S}A_{ji}\frac{1-q_i}{q_i}}.$$
Therefore,
\begin{align}
\nonumber\p_A\left(\sum_{l\in[L]}\sum_{j\in S}A_{ji}\frac{q_j-y_{ijl}}{q_j}\geq Lt'\right)&\geq\p_A\left(\sum_{l\in[L]}\sum_{j\in S}A_{ji}\frac{q_j-y_{ijl}}{q_j}\geq C_5\sqrt{L\sum_{j\in S}A_{ji}\frac{1-q_i}{q_i}}\right)\\
&\geq c_1-o(1)\label{spectral-constant}
\end{align}
where (\ref{spectral-constant}) comes from Lemma \ref{lem:CLT-stein}. The  4th moment approximation can be checked to be of order $(npL)^{-1/4}$ similarly as in (\ref{eq:spectral-clt}) using (\ref{eqn:A_1})-(\ref{eqn:A_3}) and $\rho=o(1)$ since the second and fourth moment of $\frac{q_j-y_{ijl}}{q_j}$ are at the constant order under measure $\p_A$, which completes the proof.

\end{proof}

config: arxiv


TITLE: Norm on commutative algebra satisfying square property is submultiplicative
QUESTION [1 upvotes]: Let $A$ be a commutative algebra and $\| \cdot \|$ be a norm on $A$ such that $\|x^2\|=\|x\|^2$ for all $x \in A$. Show that $\|xy\| \leq \|x\|\|y\|.$

My attempt: If I assume $$2\|xy\|\leq(\|x\|+\|y\|)^2\tag{1}$$ for all $x,y \in A.$
Then from this I get from all $x,y \in A$ $$\|xy\|\leq 2\|x\|\|y\|.$$
Then replacing $x$ and $y$ with $x^{2^n}$ and $y^{2^n}$, the required result follows.

However, I'm not able to prove equation $(1).$ I tried using $4xy=(x+y)^2-(x-y)^2$ but didn't get too far.

Any hints are appreciated.

REPLY [4 votes]: How did you use $4xy=(x+y)^2-(x-y)^2$? We have
\begin{align*}
\|4xy\|
&=\|(x+y)^2-(x-y)^2\| \\
&\leq\|(x+y)^2\|+\|(x-y)^2\| \\
&=\|x+y\|^2+\|x-y\|^2 \\
&\leq(\|x\|+\|y\|)^2+(\|x\|+\|y\|)^2 \\
&=2(\|x\|+\|y\|)^2,
\end{align*}
and therefore
$$
2\|xy\| \leq (\|x\|+\|y\|)^2.
$$


TITLE: Trivial extension in QPA Software
QUESTION [3 upvotes]: For a given quiver algebra $A$, one can calculate the trivial extension   algebra  $T(A)$ (see Trivial extension of an algebra for the definition) of $A$ with the GAP-package QPA.

Question: Is there an easy way to obtain $A$ as $T(A)$-module in QPA? (note that $A$ is a quotient of $T(A)$ by $D(A)$ and thus a $T(A)$-module in this way)

REPLY [4 votes]: One can do the following in QPA, where $A$ is some admissible quotient of a path algebra. The code below should work for any admissible quotient of a path algebra. The last line of code gives the indecomposable projective $A$-modules as $T(A)$-modules.  In fact, you can enter any $A$-module $M$ into the command
RestrictionViaAlgebraHomomorphism(f,M)

and get it as a $T(A)$-module.
gap> A;
<Rationals[<quiver with 3 vertices and 5 arrows>]/
<two-sided ideal in <Rationals[<quiver with 3 vertices and 5 arrows>]>,
  (5 generators)>>
gap> TA := TrivialExtensionOfQuiverAlgebra(A);
<Rationals[<quiver with 3 vertices and 8 arrows>]/
<two-sided ideal in <Rationals[<quiver with 3 vertices and 8 arrows>]>,
  (26 generators)>>
gap> Q := QuiverOfPathAlgebra(A);
<quiver with 3 vertices and 5 arrows>
gap> QTA := QuiverOfPathAlgebra(TA);
<quiver with 3 vertices and 8 arrows>
gap> gensA := GeneratorsOfAlgebraWithOne(A);
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e] ]
gap> gensTA := GeneratorsOfAlgebraWithOne(TA);
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e],
  [(1)*te_a1_1_1], [(1)*te_a1_1_2], [(1)*te_a1_3_3] ]
gap> n := Length(gensTA) - Length(gensA);
3
gap> gensA := ShallowCopy(gensA);
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e] ]
gap> list := List( [1..n], i -> Zero(A));
[ [<zero> of ...], [<zero> of ...], [<zero> of ...] ]
gap> Append(gensA,list);
gap> gensA;
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e],
  [<zero> of ...], [<zero> of ...], [<zero> of ...] ]
gap> f := AlgebraHomomorphismByImages(TA,A,gensTA,gensA);
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e],
  [(1)*te_a1_1_1], [(1)*te_a1_1_2], [(1)*te_a1_3_3] ] ->
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e],
  [<zero> of ...], [<zero> of ...], [<zero> of ...] ]
gap> f!.generators := gensTA;
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e],
  [(1)*te_a1_1_1], [(1)*te_a1_1_2], [(1)*te_a1_3_3] ]
gap> f!.genimages := gensA;
[ [(1)*v1], [(1)*v2], [(1)*v3], [(1)*a], [(1)*b], [(1)*c], [(1)*d], [(1)*e],
  [<zero> of ...], [<zero> of ...], [<zero> of ...] ]
gap> P := IndecProjectiveModules(A);
[ <[ 1, 4, 3 ]>, <[ 0, 2, 2 ]>, <[ 1, 2, 2 ]> ]
gap> test := List( P, p -> RestrictionViaAlgebraHomomorphism(f,p));
[ <[ 1, 4, 3 ]>, <[ 0, 2, 2 ]>, <[ 1, 2, 2 ]> ]


text:
\begin{definition}[Definition:Inverse Mapping/Definition 1]
Let $f: S \to T$ be a [[Definition:Mapping|mapping]].
Let $f^{-1} \subseteq T \times S$ be the [[Definition:Inverse of Mapping|inverse]] of $f$:
:$f^{-1} := \set {\tuple {t, s}: \map f s = t}$
Let $f^{-1}$ itself be a [[Definition:Mapping|mapping]]:
:$\forall y \in T: \tuple {y, x_1} \in f^{-1} \land \tuple {y, x_2} \in f^{-1} \implies x_1 = x_2$
and
:$\forall y \in T: \exists x \in S: \tuple {y, x} \in f$
Then $f^{-1}$ is called the '''inverse mapping of $f$'''.
\end{definition}

config: wiki


text:
\section{Dimension-Independent Convergence of Clipped Private Gradient Descent}
\label{sec:clipping}

In Sections~\ref{sec:ucconvex} and~\ref{sec:privNonConvex}, we have seen that $\adpgd$ (Algorithm~\ref{Alg:Frag}) has dimension-independent convergence for unconstrained GLMs (convex or non-convex). Moreover, the bound is tight in the convex case.
An issue with $\adpgd$ is that it requires an apriori bound on the $\ell_2$-norm of the gradients for all values of $\theta$ and $d$. In practice~\citep{DP-DL,papernot2020tempered}, when such a bound is unknown or non-existent, a modified version of $\adpgd$, called \emph{clipped} DP-GD, is used.
In this algorithm, the gradients on individual data points are projected to ensure that they conform to a pre-defined $\ell_2$-norm bound (denoted by \emph{clipping norm} $\cn$). This is done by  replacing Line 3 in Algorithm~\ref{Alg:Frag} by
\begin{align}
\gpriv_t \leftarrow &\frac{1}{n}\sum\limits_{i=1}^n \clip\left(\subg \ell(\theta_t;d_i)\right) + \calN\left(0,\sigma^2\right)
\label{eq:clipGD}
\end{align}
where $\clip(\boldv)=\boldv\cdot\min\left\{1,\frac{\cn}{\|\boldv\|_2}\right\}.$ We denote this algorithm as $\adpgdc$.

Now, we show that $\adpgdc$ enjoys the same dimension-independent convergence as $\adpgd$ as long as the underlying problem is \emph{convex} GLM. For all values of {clipping norm} $\cn>0$, the convergence is always to the minimum of a well-defined convex objective function. Based on the value of $\cn$ (i.e., whether $\cn \leq L$), the convergence may be to the minimum of a different (well-specified) objective function, rather than the original objective $\calL(\theta;D)$.

\subsection{Characterizing Clipping in Convex GLMs}
\label{sec:clipeqvhuber}

First, we provide an analytical tool in Lemma \ref{lem:huberized} to precisely quantify the objective function that $\adpgdc$ optimizes when the underlying loss function is a convex GLM.

\begin{lem}\label{lem:truncation}\label{lem:huberized}
Let $f:\bfR\to\bfR$ be any convex function and $\cn \in \bfR_+$ be any positive value.

For any $\bfx \neq \mathbf{0}$, let
$Y_1 = \bbracket{y: u < -\frac{\cn}{\snorm{\boldx}{2}} \ \forall u \in \partial f(y)}$ and
$Y_2 = \bbracket{y: u > \frac{\cn}{\snorm{\boldx}{2}} \ \forall u \in \partial f(y)}$.
If $Y_1$ is non-empty, let $y_1 = \sup Y_1$; otherwise  $y_1 = -\infty$.
If $Y_2$ is non-empty, let $y_2 = \inf Y_2$; otherwise  $y_2 = \infty$.

Let $g_{\boldx}:\bfR\to\bfR$ be
\begin{align*}
g_{\boldx}(y) =
\begin{cases}
-\frac{\cn}{\|\bfx\|_2} (y - y_1) + f(y_1) & \text{for } y \in (-\infty, y_1) \\
f(y) & \text{for } y\in [y_1, y_2] \cap \bfR \\
\frac{\cn}{\|\bfx\|_2} (y - y_2) + f(y_2) & \text{for } y \in (y_2,\infty)
\end{cases}.
\end{align*}

Then the following holds.
\begin{enumerate}[leftmargin=12pt]
\item $g_{\boldx}$ is convex.
\item
Let $\ell_f:\bfR^p\times\bfR^p\to\bfR$ be $\ell_f(\theta;\bfx)=f\left(\ip{\theta}{\bfx}\right)$ for any $\theta,\bfx$.
Let $\ell_g:\bfR^p\times\bfR^p\to\bfR$ be $\ell_g(\theta; \bfx) = g_{\boldx}(\ip{\theta}{\bfx})$ for any $\theta,\bfx$.
Then, for any $\theta$, $\boldx$, we have
\begin{align*}
\partial_{\theta}\ell_g(\theta;\bfx) =
\bbracket{\min\left\{1,\frac{\cn}{\snorm{\boldu}{2}}\right\}\cdot \boldu : \boldu \in \partial_{\theta}\ell_f(\theta;\bfx)}.
\end{align*}
\end{enumerate}
\end{lem}

\mypar{Note} Lemma \ref{lem:huberized} is a generic tool for understanding the effect of clipping. In fact, it can be used to justify the use of standard private convex optimization analysis in \citep{BST14,FMTT18,feldman2019private,bassily2019private} to $\adpgdc$ on convex GLMs.

The proof (see \ifsupp Appendix~\ref{app:undclip}\else the supplementary material\fi) is based on the fact that clipping does not affect the monotonicity property of the derivative of one-dimensional convex function. A pictorial representation of Lemma~\ref{lem:huberized} is given in Figure~\ref{fig:clipnormlr}.

\begin{figure}[h]
\centering

\includegraphics[width=0.45\textwidth]{fig/ClippingRepresentation.pdf}
\caption{Representing the clipping operation in~\eqref{eq:clipGD} for Algorithm $\adpgdc$ via Lemma~\ref{lem:truncation}.}
\label{fig:clipnormlr}
\end{figure}

\subsection{Rank-based Convergence of Algorithm $\adpgdc$}

Now, we provide the rank-based convergence of Algorithm $\adpgdc$. Recall that the original loss function is given by $\calL(\theta;D)=\frac{1}{n}\sum\limits_{i=1}^n\ell(\ip{\theta}{\boldx_i};y_i)$. Since, by Lemma~\ref{lem:huberized} we know that for any clipping level $\cn>0$, one can replace each loss function $\ell(\ip{\theta}{\boldx_i};y_i)$ with that obtained from Lemma~\ref{lem:huberized}. We denote these clipped losses as $\ellc(\ip{\theta}{\boldx_i};y_i)$, and the corresponding objective function as $\calLc(\theta;D) =\frac{1}{n}\sum\limits_{i=1}^n\ellc(\ip{\theta}{\boldx_i};y_i)$. We immediately have the following corollary from Theorem~\ref{thm:dimIndependence}.

\begin{cor}
Let $\theta_0=\mathbf{0}^p$ be the initial point for $\adpgdc$, and let $\cn>0$ be the corresponding clipping norm.
Let $\thetaH = \argmin\limits_{\theta\in\bfR^p}\calLc(\theta;D)$, and $M$ be the projector to the eigenspace of matrix $\sum\limits_{i=1}^n \bfx_i\bfx_i^T$. For constraint set $\calC=\boldR^p$, clipping norm $L$, and running $\adpgdc$ on $\calL(\theta;D)$ for $T=n^2\epsilon^2$ steps with appropriate learning rate $\eta$, we get
\ifaistats
\begin{align*}
& \mathbb{E}\left[\calLc\left(\privT;D\right)\right]-\calLc\left (\thetaH;D\right)\\
& \qquad \leq\frac{L\snorm{\thetaH}{M}\sqrt{1 + 2\cdot\rank(M)\cdot \log(1/\delta)}}{\epsilon n}.
\end{align*}
\else
\begin{align*}
\mathbb{E}\left[\calLc\left(\privT;D\right)\right]-\calLc\left (\thetaH;D\right)
\leq\frac{L\snorm{\thetaH}{M}\sqrt{1 + 2\cdot\rank(M)\cdot \log(1/\delta)}}{\epsilon n}.
\end{align*}
\fi
Here, $\rank(M)\leq n$ (but can be much smaller), and $\snorm{\cdot}{M}$ is the seminorm w.r.t. the projector $M$.
\label{cor:dimIndependencec}
\end{cor}

From Corollary~\ref{cor:dimIndependencec}, it is immediate that as long as the clipping norm $\cn \geq L$ (where $L$ is the $\ell_2$-Lipschitz constant of the loss functions $\ell$), $\adpgdc$ optimizes the original loss $\calL$.

\subsection{Interlude: Adverse Effects of Aggressive Clipping}
\label{sec:negclip}

Corollary~\ref{cor:dimIndependencec} eludes two natural questions:
i) Is the output of Algorithm $\adpgdc$ guaranteed to be good in terms of the empirical loss on the original loss $\calL(\theta;D)$ when $\cn < L$, and
ii) When the underlying loss  \emph{does not} satisfy the convex GLM property, is the objective function that gets optimized by $\adpgdc$ still well-defined as for convex GLMs?
Our answers to both questions are \emph{negative}.

To answer the first question, we construct an instance of logistic regression $\calL(\theta;D)$ with $L$, the $\ell_2$-Lipschitz constant of the individual loss functions, being $1$. We show that if the clipping norm $\cn < 1/4$, then the excess empirical risk of Algorithm $\adpgdc$ on $\calL(\theta;D)$ is $\Omega(1)$. Whereas Algorithm $\adpgd$ with $L=1$ has an excess empirical risk of $O(1/n)$, where $n$ is the number of training examples. A formal description of this bound is in \ifsupp Appendix~\ref{sec:lower bound logistic regression}. \else the supplementary material. \fi

To answer the second question, we show that even for simple convex problems like multi-class logistic regression (that does not belong to the traditional GLM class), clipping in $\adpgdc$ can generate a sequence of ``clipped gradient vectors'' that do not conform to a gradient field of any ``natural'' convex function,
though the output of $\adpgdc$ might still  minimize the excess empirical risk on $\calL(\theta;D)$ practically.
We leave this exploration for future work.

Formally, consider a $K$-class classification problem for $K \geq 3$.
Given a sample $(x,y)$ with $x\in\bfR^p$ and $y\in [K]$, the cross-entropy loss $\ell: \bfR^{p\times K} \times \bfR^p\times [K] \to \bfR$ is, for $\bt = [\theta^{(1)}, \dots, \theta^{(K)}]$,
\begin{align*}
\ell\bracket{\bt; (x,y)} = \sum_{k=1}^K \indi{y=k} \log \frac{\expo{\theta^{(k)}\cdot x}}{\sum_{k'=1}^K \expo{\theta^{(k')}\cdot x}}.
\end{align*}

\begin{thm}
Consider any sample $(x, y)$ with $x\in \bfR^p\backslash{\{\mathbf{0}\}}$, $y\in [K]$ (for $K \geq 3$) and any $\cn > 0$ such that $\bT = \bbracket{\bt: \|\nabla_{\bt} \ell(\bt;(x,y))\|_2 > \cn}$ is non-empty.
Let $G(\theta)$ be the clipped gradient of $\ell(\bt;(x,y))$ as defined above.
Consider any function $f:\calC \to \bfR$, $\calC\subseteq \bfR^{p\times K}$ such that $\interior{\calC}\cap \bT\neq \emptyset$, where $\interior{\calC}$ is the interior of set $\calC$.

If $f$ is differentiable everywhere except for a set $\calC_N\subseteq \calC$
s.t. $\calC_N$ is a closed set on $\calC$ and has zero Lebesgue measure, then it is not possible for $\nabla_{\bt} f(\bt) = G(\bt)$ to hold for all $\bt \in \interior{\calC}\backslash\calC_N$.
\label{thm:clipped_softmax}
\end{thm}

As convexity implies differentiability almost everywhere~\cite[Theorem 25.5]{rockafellar1970convex}, if $f$ is convex, we only need $\calC_N$ to be a closed set.
The $\ell_1$ regularizer $\snorm{\bt}{1}$ is non-differentiable on a closed set, and so is the hinge loss $\ell_{\sf hinge}(\theta; (x,y))=\max\bracket{0, 1-y\ip{\bt}{x}}$.
Theorem~\ref{thm:clipped_softmax} essentially rules out the possibility that the field of clipped gradients corresponds to any single objective function in convex models like softmax regression and SVMs with $\ell_1/\ell_2$ regularization, and in non-convex models like neural networks with popular activation functions like logistic sigmoid, tanh, ReLu.
We defer the proof of Theorem~\ref{thm:clipped_softmax} to \ifsupp Appendix~\ref{app:softMax}.
\else the supplementary material. \fi
One might further ask if the problem above could be resolved by ``per-class'' clipping, i.e., clipping $\nabla_{\theta^{(k)}} \ell$ individually for each $k$? The answer is still negative.

We provide more details in \ifsupp Appendix~\ref{sec:per-class_clip}. \else the supplementary material. \fi


TITLE: Find coefficients of $x^2$ and $x^3$ in the expansion of $(3 − 2x) ^6$
QUESTION [2 upvotes]: The coefficients of $x^2$ and $x^3$ in the expansion of $(3 − 2x) ^6$ are $a$ and $b$ respectively. What is the value of $a$ and $b$?

They need to be good at the binomial theorem and know the formulas.

REPLY [0 votes]: Hint: By binomial theorem
$$(3-2x)^6=2^6\sum_{k=0}^6 {6\choose k}\left(\frac{3}{2}\right)^kx^{6-k}.$$


TITLE: Why is throwing one part of the EPR state away not the same as measuring it and not looking at the result?
QUESTION [0 upvotes]: Disclaimer: The amount of sense that the following makes might differ depending on which interpretation of quantum mechanics you are supporting.
Suppose that I have the EPR-state
\begin{align*}
 \frac{\mid 0 0 \rangle +  \mid 1 1 \rangle }{ \sqrt{2}}
\end{align*}
If I throw the second system out (i.e. taking the partial trace over the second system) I end up with the pure state.  "EDIT: This is not the correct way to throw the second system out"
\begin{align*}
 \frac{\vert 0 \rangle +  \vert 1 \rangle }{ \sqrt{2}}
\end{align*}
If I measure the second system, but I do not look at the measurement then I end up then the system is described by the density matrix
\begin{align*}
\frac{\vert 0 \rangle \langle 0 \vert + \vert 1 \rangle \langle 1 \vert }{2}
\end{align*}
These systems are fundamentally different. Do you have an intuition/explanation why I do not get effectively the same system?

REPLY [2 votes]: As was pointed out in the comments by Jakob and Rusian. The point/mistake is that you can't (of course) just throw away the second part of the kets to throw away the second system. You need to take the partial trace of the corresponding $density$ $ matrix$. Then you will end up with the same as the density matrix when you measure and never look at the measurement.


TITLE: A non-measurable, real-valued function with inverse image of singletons measurable (particular construction)
QUESTION [1 upvotes]: Let $M$ denote the set of measurable subsets of $\mathbb{R}$. Show
  that there exists a non-measurable function $g:\mathbb{R}\to \mathbb{R}$ such that $g^{-1}(\{x\}) \in M$ for every $x \in
> \mathbb{R}$.
Hint: Construct an injective function $g$ such that $\{x \in \mathbb{R}: g(x) > 0\}$ is a non-measurable set.

I am trying to figure out how to show the result using a construction satisfying the hint. My idea was:
Let $E$ be a non-measurable subset of $(0,\infty)$. Define $g$ as follows:
$$g(x)=\begin{cases}
x & x \in E \\
-x & x \in [0,\infty) \setminus E \\
x & x \in (-\infty,0) \end{cases}.$$
Then $g^{-1}(\{ x \})$ is measurable for each singleton (because it is finite (either 1 or 2 values)) but $g^{-1}((0,\infty)) = \{x \in \mathbb{R} : g(x) > 0 \}=E$, which is not measurable.
However, this is obviously not quite injective. How can I modify this to get an injective function?

REPLY [3 votes]: Let $f: \mathbb{R} \to (0,\infty)$ be an injective function, e.g. $f(x) = \exp(x)$. Now define
$$g(x) := \begin{cases} x, & x \in E \\ -f(x), & x \notin E. \end{cases}$$
As $f$ is injective and takes only strictly positive values, it is not difficult to see that $g$ is injective but not measurable (as $\{g>0\} = E$).


TITLE: show partial sum converges almost surely
QUESTION [3 upvotes]: I am trying to show giving a sequence $(X_n) \subseteq L^2$ of independent random variables with zero mean and  $\sum_{n\in N}E[X_n^2]< \infty$ , $\sum_{n\in N}X_n$ converges a.s.
For this I wanna get  $\sum_{n\in N} \mathbb{P}(|\sum_{k=1}^{n}X_k|>\epsilon)<\infty$. As if I can show it , then by Borel-Cantelli lemma,  $\sum_{n\in N}X_n$ converges to zero almost surely.
But I dont know how to get $\sum_{n\in N} \mathbb{P}(|\sum_{k=1}^{n}X_k|>\epsilon)<\infty$,
I tried this:
By Chebychev's inequality, $\mathbb{P}(|\sum_{k=1}^{n}X_k|>\epsilon)\leq \mathbb{E}[X_n^2]/\epsilon^2 $, follows that  $\sum_{n\in N}\mathbb{P}(|\sum_{k=1}^{n}X_k|>\epsilon)\leq\sum_{n\in N}\mathbb{E}[X_n^2]/\epsilon^2$. However, letting $\epsilon\longrightarrow 0$ doesn't make the right side bounded. Seems doesnt work...
I am wondering if anyone can show the correct way to do it. Thanks in advance.

REPLY [1 votes]: We can apply Kolmogorov three series theorem. We have to check that

$\sum_{j=1}^{+\infty}P(|X_j|>1)$ is convergent. It's the case, as $P(|X_j|>1)\leq EX_j^2$.
$\sum_{j=1}^{+\infty}E[X_j\chi_{\{X_j\leq 1\}}]$ is convergent. We have, as $EX_j=0$, $$E[X_j\chi_{\{X_j\leq 1\}}]=-E[X_j\chi_{\{|X_j|>1\}}]\leq \sqrt{EX_j^2}\sqrt{P(|X_j|\geq 1)}\leq EX_j^2.$$
$\sum_{j=1}^{+\infty}\operatorname{Var}(X_j\chi_{\{|X_j|\leq 1\}})$ is convergent. But since the expectation of $X_j $ is $0$,  $$\operatorname{Var}(X_j\chi_{\{|X_j|\leq 1\}})\leq \operatorname{Var}(X_j)=EX_j^2,$$
and we can conclude.


TITLE: How to solve this limit without the L'Hospital?
QUESTION [0 upvotes]: How would one evaluate the following limit without using L'Hospital Rule
$$\lim_{x\to -1}\dfrac{\sin(x+1)}{x^3+1}$$
the result should be $1/3$.

REPLY [2 votes]: Hint: Use
$$\dfrac{\sin(x+1)}{x^3+1}=\dfrac{\sin(x+1)}{(x+1)(x^2-x+1)}$$
and
$$\lim_{u\to 0} \dfrac{\sin u }{u}=1.$$