TITLE: Is this relation reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive?
QUESTION [1 upvotes]: There is relation
$$R=\left\{(1,1),(1,5),(2,4),(3,3),(4,1),(4,2),(5,4)\right\}$$
What properties (see title) it have?

Hi maths people I learn for test next week. Here is my idea is it good or not?
-not reflexive because we don't have $(2,2)$ as example
-not irreflexive because we have for example $(1,1)$
-not symmetric because for example $(1,5)$ exists but no $(5,1)$
-not asymmetric because for example $(2,4)$ and $(4,2)$ exist
-not antisymmetric because for example $(2,4)$ and $(4,2)$ exist but they are not equal
But no idea is transitive very complicated.. Is trick to check it easy pls tell me?
And is my reasons good and correct?

REPLY [3 votes]: All your answers (and reasons given!) so far are correct!
Transitivity means that whenever you have $(a,b)$ and $(b,c)$, you should also have $(a,c)$.  What do you think: do you have that here?


TITLE: Apparent paradox with magnetic vector potential
QUESTION [1 upvotes]: I wanted to calculate the magnetic field in the figure using the magnetic vector potential.

In case the drawing I made is not too clear, that is a circular wire of radius $a$ with a current $I$ across it. The $z$-axis goes through the center of the circle. For simplicity, I assumed that the circle is on the plane at $z=0$.
Let $|\mathbf{r}-\mathbf{r'}|=R$. So the vector potential is calculated as
$$\mathbf{A}(\mathbf{r})=\frac{\mu _0}{4\pi}\iiint\limits_V\frac{\mathbf{J}(\mathbf{r'})}{R}dV'$$
In this case the wire is infinteliy thin, so the volume integral becomes a line one and using cylindrical coordinates we have that
$$\mathbf{A}=\frac{\mu _0}{4\pi}\oint\limits_C \frac{Ia\mathbf{\hat{\phi}}}{R} d\phi'=\frac{\mu _0 Ia}{4\pi \sqrt{(z^2+a^2)}}\oint\limits_C \mathbf{\hat{\phi}} d\phi'$$
But $\oint\limits_C \mathbf{\hat{\phi}} d\phi'=\mathbf{0}$. So, according to these calculations:
$$\mathbf{A}=\mathbf{0}\implies \mathbf{\nabla}\times\mathbf{A}=\mathbf{B}=\mathbf{0}$$
So I got that $\mathbf{B}=\mathbf{0}$ but I know this is wrong, because the result for this problem is well-known and I have calculated without using $\mathbf{A}$.
However, I want to know what I did wrong during these steps. Can anyone see it?

REPLY [1 votes]: Using the line integral, you need to find a general vector function for A.
Say you are trying to find the field at a point (in cylindrical coordinates): ($r_1,\phi_1,z_1$) due to the circular loop.
Let the vector from the origin to this point be $\vec{r_1}$ and the vector from the origin to any point on the loop be $\vec{r'}$. The coordinates of a point on the loop are ($a,\phi ,0$).
Then the distance from a point on the loop to ($r_1,\phi_1,z_1$) $=r=|\vec{r_1}-\vec{r'}|=(a^2+r_1^2-2r_1a*cos(\phi-\phi_1)+z_1^2)^{1/2}$
We have,
$$\mathbf{A}(\mathbf{r})=\frac{\mu _0}{4\pi}\int\frac{\mathbf{I}(\mathbf{r'})}
{r}dl'$$
$$\mathbf{A}(\mathbf{r})=\frac{\mu _0I}{4\pi}\int\frac{\mathbf{dl'}}
{r}$$
$$\mathbf{A}(\mathbf{r})=\frac{\mu _0I}{4\pi}\int\limits_{0}^{2\pi}\frac{a*d\phi*\hat{\phi}}
{(a^2+r_1^2-2r_1a*cos(\phi-\phi_1)+z_1^2)^{1/2}}$$
After evaluating this integral, you can take the curl with respect to $r_1,\phi_1,z_1$, hence generalizing these coordinates and obtaining a function for B.
The integral for A is frustratingly hard to evaluate, because it is exact (and involves elliptical integrals) So, we just use the multipole expansion to find the B field.
If you do want to see how to work through the integral, this treatment is absolutely fantastic. The video finds the field at points in the x-z plane, but if you change the $\phi'$ everywhere to $\phi'-\phi_1$, where $\phi_1$ is the azimuth angle of point P, the solution will be valid for all space.


TITLE: The Verdier Quotient
QUESTION [1 upvotes]: In A.Neeman's book and D.Murfet's notes I have been reading about the construction of the Verdier quotient of a triangulated category, $\mathscr{T}$, by some triangulated subcategory $\mathscr{C}$. In both places they require that triangulated subcategories be strict (i.e. closed under taking isomorphisms). Is it possible to remove the strictness assumption and still define the Verdier quotient? I have been studying the proof of existence and I haven't been able to find a place with strictness is required. Thanks!

REPLY [7 votes]: $\mathscr{T}/\mathscr{C}$ still makes sense if $\mathscr{C}$ is not strict, but it's exactly the same as taking the quotient by the "strictification" of $\mathscr{C}$ (i.e., the subcategory consisting of all objects isomorphic to an object of $\mathscr{C}$), so you don't get anything more general.


text:
\section{Proof of the main results}
\label{sec:proof_main}

\subsection{Proof of Theorem~\ref{thm:noiseless}}
\label{proof:noiseless}

In order to prove that $x$ is the unique solution of \eqref{pb:BP}, one can use Fermat's rule for \eqref{pb:BP}. Under injectivity of $A_S$,
{this corresponds to the quest of} a vector $v \in \Rc (A^*)$, called dual certificate, such that
\[
\left\{
\begin{array}{ll}
v_S &= \sgn (x_S ) \\
\| v_{S^c} \|_\infty &<1.
\end{array}
\right.
\]
A natural candidate for such a vector $v$ is the dual certificate with minimal $\ell^2$-norm, i.e.
$$
v = A^* (A_S^\dagger)^* \sgn ( x_{S}) = A^* A_S (A_S^* A_S)^{-1}  \sgn (x_{S}),
$$
which trivially lies in the range of $A^*$ and satisfies $v_S=\sgn (x_S )$. The second condition $\| v_{S^c} \|_\infty <1$ remains to be satisfied, as required by assumption (ii) of the following proposition.
\begin{prop}[{\cite[Corollary 4.28]{foucart2013mathematical}}]
\label{cor:FR}
For $x\in \Cbb^n$ with support $S$, if
\begin{enumerate}
\item $A_S$ is injective,
\item $\left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| < 1$ for all $\ell\in S^c$,
\end{enumerate}
then the vector $x$ is the unique solution of \eqref{pb:BP} with $y=Ax$.
\end{prop}

By Lemma \ref{lem:localIsometry_ext}, one gets the injectivity of $A_S$ with high probability.
The rest of the proof is then dedicated to ensure (ii) of Proposition \ref{cor:FR}. By a union bound, one can control the probability that \eqref{pb:BP} fails to recover $x$ as follows:
\begin{align*}
\Pbb &( \text{failure of BP}  ) \\
&\replacemath{=}{\leq}\Pbb \left( \max_{\ell \in S^c} \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq 1\right) \\
&\leq \Pbb\left(  \max_{\ell \in S^c} \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq 1 \left| \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \leq \alpha \right. \right) + \Pbb \left(  \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \geq \alpha \right)
\\
&\leq \sum_{\ell\in S^c} \Pbb\left(  \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq \|A_S^\dagger Ae_\ell \|_2\alpha^{-1}   \left| \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \leq \alpha \right. \right) + \Pbb \left(  \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \geq \alpha \right)
\\
& \leq 2 n \exp \left( -\frac{1}{2\alpha^2} \right) + \Pbb \left(  \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \geq \alpha \right),
\end{align*}
where the last inequality is obtained using a Hoeffding-type bound (see  \cite[Corollary 7.21 {and Corollary 8.10}]{foucart2013mathematical} {for  Rademacher and Steinhaus sequences, respectively)}.
To control the second term, one can remark that for all $\ell\in S^c$
$$
\|A_S^\dagger Ae_\ell \|_2 = \| (A_S^* A_S)^{-1} A_S^* A e_\ell \|_2 \leq \| (A_S^* A_S)^{-1} \|_{2\to 2} \|A_S^* A e_\ell \|_2.
$$
Using Lemma~\ref{lem:localIsometry_ext}, $\| (A_S^* A_S)^{-1} \|_{2\to 2} $ is bounded by $1/(1-\delta)$ for some $\delta>0$ with high probability.
Using Lemma~\ref{lem:C.3Ext}, $\max_{\ell\in S^c} \|A_S^* A e_\ell \|_2 \leq t$ with high probability. Then, we set $$\alpha:=t/(1-\delta).$$
The probability that \eqref{pb:BP} fails is then bounded by
\begin{align*}
\Pbb &\left( \max_{\ell \in S^c} \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq 1\right) \\
&\leq \underbrace{2n \exp \left( -\frac{1}{2\alpha^2} \right) }_{P_1}
+\underbrace{\Pbb \left( \| A_S^*A_S - {\Id} \|_{2\to 2}  \geq \delta \right)}_{P_2} + \underbrace{\Pbb\left(  \max_{\ell\in S^c} \|A_S^* A e_\ell \|_2 \geq t  \right) }_{P_3}.
\end{align*}

Note that $P_2 \leq \varepsilon/3$  by Lemma \ref{lem:localIsometry_ext} if
\begin{align}
\label{eq:m1}
m \geq \frac{1+2\delta/3}{\delta^2/2} \cdot \Lambda(S,F) \cdot \ln \left( \frac{6s}{\varepsilon} \right).
\end{align}

As for the last term $P_3$,
using Lemma \ref{lem:C.3Ext}, choosing $t = \sqrt{\Theta/m} + t'$ for some $t'>0$ to be fixed later, one has
 $P_3\leq \varepsilon/3$ if
\begin{align}
\label{eq:m2}
m \geq  \frac{2}{(t')^2} \cdot  \Theta (S,F) \cdot \left( 3+2 t'/3 \right)  \ln \left( \frac{3n}{\varepsilon}\right),
\end{align}
{where we have used} that $m \geq 4 \Theta(S,F)$.
Finally \replace{vy}{by} setting $t'=\delta$, one has
\begin{align*}
P_1 \leq \varepsilon/3
& \Longleftrightarrow 2n \exp \left( -\frac{1}{2\alpha^2} \right) \leq \varepsilon /3
 \Longleftrightarrow 2n \exp \left( -\frac{(1-\delta)^2}{2t^2} \right) \leq \varepsilon /3 \\
& \Longleftrightarrow 2n \exp \left( -\frac{(1-\delta)^2}{2\left( \sqrt{\Theta/m} +\delta\right)^2} \right) \leq \varepsilon /3
  \Longleftrightarrow\frac{(1-\delta)^2}{2\left( \sqrt{\Theta/m} +\delta\right)^2} \geq \ln\left(\frac{6n}{\varepsilon} \right).
\end{align*}
Assuming that $m\geq c\cdot \Theta(S, F) \ln (6n/\varepsilon)$ and choosing $\delta = \sqrt{\frac{1}{\replacemath{c'}{c} \ln (6n/\varepsilon)}}$ with \replace{$\min (c ,c') \geq 8$}{$c \geq 13$} leads to the previous inequality (notice that the constant \replace{8}{13} could be optimized in principle). Consequently, if
$$
\delta = \replacemath{\frac{1}{2\sqrt{2 \ln \left( \frac{6n}{\varepsilon} \right)} }}{\frac{1}{\sqrt{13 \ln \left( \frac{6n}{\varepsilon} \right)} }}
\qquad \text{and}\qquad
m \geq \replacemath{8}{13} \cdot \Theta {(S,F)} \cdot \ln \left( \frac{6n}{\varepsilon} \right),
$$
then $P_1 \leq \varepsilon/3$.

Plugging this value of $\delta$ into \eqref{eq:m1} and \eqref{eq:m2},  one gets the following conditions on the number of measurements:
\[
\left\{
\begin{array}{ll}
m & \geq \replacemath{19}{30}   \cdot \Lambda  (S,F)   \cdot \ln \left( \frac{6n}{\varepsilon} \right) \ln \left( \frac{6s}{\varepsilon} \right),   \\
m &\geq  \replacemath{51}{82} \cdot \Theta  (S,F)  \cdot \ln^2 \left( \frac{6n}{\varepsilon} \right).
\end{array}
\right.
\]
Finally, the probability of recovery failure from \eqref{pb:BP} is bounded by $\varepsilon$, if the total number of blocks of measurements satisfy
\begin{align*}
m & \geq  \replacemath{51}{82} \cdot \Theta(S,F)  \cdot \ln^2 \left( \frac{6n}{\varepsilon} \right).
\end{align*}
This concludes the proof of Theorem \ref{thm:noiseless}.

\subsection{Proof of Theorem \ref{thm:noisy}}
\label{proof:noisy}

In order to ensure stable and robust recovery via \eqref{pb:qBP}, we take advantage of a result analogous to  Proposition~\ref{cor:FR}, which hinges again on the concept of dual certificate. (Notice that in \cite[Theorem 4.33]{foucart2013mathematical} $S$ is assumed to be the set of $s$ largest absolute entries of $x$, but an inspection of the proof reveals that $S$ can be an arbitrary subset of $\{1,\ldots,n\}$).

\begin{prop}[{\cite[Theorem 4.33]{foucart2013mathematical}}]
\label{prop:FRstable}
Let $x \in \Cbb^n$, $S \subseteq\{1,\ldots,n\}$, and  $y = Ax + \epsilon$ with $\|\epsilon\|_2 \leq \eta$. For $\delta,t,\gamma,\theta,\tau \geq 0$, with $\delta < 1$, assume that
\begin{equation}
\label{eq:FRstable_cond1}
\|A^*_S A_S - \Id\|_{2\to2} \leq \delta,
\quad
\max_{\replacemath{\ell \in S}{\ell \in S^c}}\|A^*_S A e_\ell\|_2 \leq t,
\end{equation}
and that there exists a vector $u = A^*h \in \Cbb^n$ with $h$ such that
\begin{equation*}
\|u_S - \sgn(x_S)\|_2 \leq \gamma,
\quad \|u_S\|_\infty \leq \theta,
\quad \|h\|_2 \leq \tau \sqrt{s}.
\end{equation*}
If $\rho := \theta + t \gamma /(1-\delta) < 1$, then a minimizer $x^\sharp$ of \eqref{pb:qBP} satistfies
$$
\|x - x^\sharp\|_2 \leq C_1 \|x-x_S\|_1 + (C_2 + C_3\sqrt{s})\eta
$$
for some constants $C_1, C_2, C_3 > 0$ depending only on $\delta, t, \gamma, \theta, \tau$.
\end{prop}

Using arguments analogous to the proof of Theorem \ref{thm:noiseless}, one
can show that \eqref{eq:FRstable_cond1} holds with high probability.
Therefore, using Proposition~\ref{prop:FRstable}, we choose the dual certificate to be $u = A^* h$ with $h=  A_S (A_S^* A_S)^{-1}\sgn (x_S)$.

Since $u_S = \sgn(x_S)$, for any $\gamma \geq 0$, the condition
$ \|u_S - \sgn(x_S) \|_2\leq \gamma$
is trivially satisfied  {(in particular, we can set $\gamma = 0$)}.

As for ensuring that $\|u_{S^c}\|_\infty \leq \theta$ with high probability,
we have to slightly modify a part of the proof in the noiseless setting. First, let us observe that
\begin{align*}
\|u_{S^c}\|_\infty &= \max_{\ell \in S^c} \left|\left\langle A^*  A_S (A_S^* A_S)^{-1} \sgn (x_S) , e_\ell \right\rangle \right|
= \max_{\ell \in S^c} \left|\left\langle  \sgn (x_S) , A_{S}^\dagger A e_\ell \right\rangle \right|.
\end{align*}
For $0<\theta=1/4<1$, using again a union bound and a Hoeffding-type inequality (see \cite[Corollary 7.21 and Corollary 8.10]{foucart2013mathematical} for  Rademacher and Steinhaus sequences, respectively), one has

\begin{align*}
\Pbb &\left( \max_{\ell \in S^c} \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq  \theta\right) \\
&\leq \Pbb\left(  \max_{\ell \in S^c} \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq \theta \left| \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \leq \alpha \right. \right) + \Pbb \left(  \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \geq \alpha \right)
\\
&\leq \sum_{\ell\in S^c} \Pbb\left(  \left|\left\langle A_S^\dagger A e_\ell, \sgn (x_S) \right\rangle \right| \geq \theta \|A_S^\dagger Ae_\ell \|_2 \alpha^{-1}   \left| \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \leq \alpha \right. \right) + \Pbb \left(  \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \geq \alpha \right)
\\
& \leq  2n \exp \left( -\frac{\theta^2}{2\alpha^2} \right) + \Pbb \left(  \max_{\ell \in S^c} \|A_S^\dagger Ae_\ell \|_2 \geq \alpha \right) \\
& \leq
\underbrace{2n \exp \left( -\frac{\theta^2}{2\alpha^2} \right)}_{P_1}
+\underbrace{\Pbb \left( \| A_S^*A_S - {\Id} \|_{2\to 2}  \geq \delta \right)}_{P_2} + \underbrace{\Pbb\left(  \max_{\ell\in S^c} \|A_S^* A e_\ell \|_2 \geq t  \right) }_{P_3}.
\end{align*}
Now, analogously to the proof of Theorem~\ref{thm:noiseless}, we fix
$$
\alpha = \frac{t}{1-\delta}, \quad t = \sqrt{\frac{\Theta}{m}}+t', \quad t' = \delta.
$$
With these choices of parameters, conditions \eqref{eq:m1} and \eqref{eq:m2} suffice to guarantee that $P_2 \leq \varepsilon/3$ and $P_3\leq \varepsilon/3$, respectively. {Moreover}, since $\theta=1/4$,
if
$$
\delta = \replacemath{\frac{1}{2\sqrt{32 \ln \left( \frac{6n}{\varepsilon} \right)}}}{\frac{1}{\sqrt{146 \ln \left( \frac{6n}{\varepsilon} \right)}}}
\quad \text{and} \quad m \geq {\replacemath{128}{146}} \cdot \Theta(S,F) \cdot\ln\left(\frac{6n}{\varepsilon}\right),
$$
then ${P_1} \leq \varepsilon/3$.
Plugging this value of $\delta$ in \eqref{eq:m1} and \eqref{eq:m2},  one gets the following conditions on the number of measurements:
\[
\left\{
\begin{array}{ll}
m & \geq \replacemath{268}{305} \cdot  \Lambda  (S,F) \cdot \ln \left( \frac{6n}{\varepsilon} \right) \ln \left( \frac{6s}{\varepsilon} \right)   \\
m &\geq \replacemath{780}{889} \cdot \Theta  (S,F)  \cdot \ln^2 \left( \frac{6n}{\varepsilon} \right).
\end{array}
\right.
\]

Now, we have to find a suitable constant $\tau > 0$ such that $\|h\|_2 \leq \tau \sqrt{s}$. Note that
\begin{align*}
\|h\|_2 &= \|  A_S (A_S^* A_S)^{-1}\sgn (x_S) \|_2 \leq  \|  A_S (A_S^* A_S)^{-1} \|_{2\to 2} \| \sgn (x_S) \|_2  =\frac{1}{\sigma_{\min}(A_S)} \sqrt{s},
\end{align*}
since $A_S$ has full column rank. Moreover, observe that
$$
\|A_S^* A_S - \Id \|_{2\to 2} \leq \delta \Rightarrow \sigma_{\min} (A_S) \geq \sqrt{1-\delta}.
$$
Hence, one can choose $\tau = \frac{1}{\sqrt{1-\delta}}$, so that
\begin{align*}
\Pbb \left(  \| h\|_2 \geq  \sqrt{\frac{s}{1-\delta}} \right) &\leq  \Pbb \left(  \frac{1}{\sigma_{\min}(A_S)} \geq  \sqrt{\frac{1}{1-\delta}} \right)  \leq \Pbb \left(  \|A_S^*A_S -\Id \|_{2\to 2} \geq \delta\right),
\end{align*}
which has been already controlled as $P_2 \leq \varepsilon / 3$.

Finally, in order to apply Proposition~\ref{prop:FRstable}, let us notice that $\theta + \gamma t/(1-\delta) <1$ {since $\gamma = 0$ and $\theta = 1/4$.

This} leads to the desired result.

\subsection{Proof of Theorem~\ref{thm:oracle_theta}}
\label{proof:oracle_theta}

We will show a more general result, which will imply Theorem~\ref{thm:oracle_theta} as a corollary. In particular, in order to obtain Theorem~\ref{thm:oracle_theta} it will suffice to consider the partition $S^{c}$ formed by its singletons in Theorem~\ref{thm:partition_trick}, i.e.\ $S^c = \sqcup_{j \in S^c}\{j\}$.

\begin{thm}
\label{thm:partition_trick}
Let \replace{$x\in \Cbb^n$}{$x\in \Rbb^n$ or $\Cbb^n$} be a vector supported on $S$, such that $\sgn(x_S)$ forms a Rademacher or Steinhaus sequence. Let $A$ be the random sensing matrix defined in \eqref{eq:sensing_matrix} with parameter $\Lambda(S,F)$ {and let $y = Ax + \epsilon$, with $\|\epsilon\|_2 \leq \eta$}. {Then, there exist constants $c_1,C_1,C_2  > 0$ such that the following holds. For every $0<\varepsilon < 1$, if}
$$
m \geq c_1  \min_{\substack{\{S_r\}\\ \textnormal{partition of }S^c}}\max_r \Lambda(S\cup S_r,F) \ln \left(\frac{6  |\{S_r\}| \replacemath{}{\max_r}|S \cup S_r|}{\varepsilon}\right)\ln\left(\frac{6n}{\varepsilon}\right),
$$

then, with probability at least $1-\varepsilon$, a minimizer $x^\sharp$ of \eqref{pb:qBP} satisfies
\begin{align*}
\|x-x^\sharp\|_2 \leq  (C_1 + C_2\sqrt{s})\eta.
\end{align*}
In particular, in the noiseless case (i.e., $\eta = 0$), $x$ is exactly recovered via \eqref{pb:BP} with probability at least $1-\varepsilon$ and with constant $c_1 = \replacemath{36}{19}$.
\end{thm}

For the sake of simplicity, let us address the case $\eta = 0$ (the argument can be generalized to the case $\eta >0$ in the same spirit of Appendix~\ref{proof:noisy}). Analogously to the proof of Theorem~\ref{thm:noiseless} in Appendix~\ref{proof:noiseless}, our aim is to find sufficient conditions such that
$$

\underbrace{2n \exp\left(-\frac{1}{2\replacemath{\alpha}{\alpha^2}}\right)}_{\replacemath{P1}{P_1}}
+
\underbrace{\Pbb\left(\|A_S^*A_S - \Id\|_{2 \to 2} \geq \delta \right)}_{P_2}
+
\underbrace{\Pbb\left(\max_{\ell\in S^c} \|A_S^* A e_\ell \|_2 \geq t\right)}_{P_3} \leq \varepsilon,
$$
where $\alpha = t/(1-\delta)$. In the following, we show how to ensure that $P_i \leq \varepsilon /3$, for $i = 1,2,3$.

By using Lemma~\ref{lem:localIsometry_ext}, we have $P_2 \leq \varepsilon /3$ under condition \eqref{eq:m1}.

In order to control $P_3$, let us consider a partition $\{ S_r \}_r$ of $S^c$ and note that
\begin{align*}
\max_{\ell \in S^c} \|A_S^* A e_\ell \|_2
&\leq \max_{r} \|A_S^* A_{S_r} \|_{2 \to 2 }
= \max_{r} \|P_S A^* A P_{S_r}^{*} \|_{2 \to 2 }
= \max_{r} \|P_S (A^* A - \Id) P_{S_r}^{*} \|_{2 \to 2 } \\
& \leq \max_{r} \|P_{S\cup S_r} (A^* A - \Id) P_{S\cup S_r}^{*} \|_{2 \to 2 }
 = \max_{r} \|A^*_{T_r} A_{T_r} - \Id \|_{2\to 2},
\end{align*}
where we have used that $P_S P_{S_r}^* = 0$ and where we have defined $T_r= S \cup S_r$ for each index $r$ of the partition. Now, combining the above inequality with Lemma~\ref{lem:localIsometry_ext} and with a union bound over the elements $S_r$ of the partition $\{S_r\}$, we obtain
$$
P_3 \leq \Pbb\left(\max_r \|A_{T_r}^* A_{T_r} - \Id\|_{2 \to 2} \geq t \right)
\leq
2 |\{S_r\}|\left( \max_r |T_r| \right) \exp \left(-\frac{mt^2/2}{\left(\displaystyle\max_{r}\Lambda(T_r,F)\right) (1+2t/3)}\right).
$$
Notice that introducing the partition $\{S_r\}$ allowed us to control $P_3$ by the quantity $\displaystyle\max_{r}\Lambda(T_r,F)$ rather than $\Theta(S,F)$. Simple algebraic manipulations show that the condition
\begin{equation}
\label{eq:condLambdaTr}
m \geq \frac{2}{t^2} \left(1 + \frac{2t}{3}\right) \max_r \Lambda(T_r,F) \ln \left(\frac{6 |\{S_r\}| \replacemath{}{\max_r}|T_r| }{\varepsilon}\right),
\end{equation}

is sufficient to have \replacemath{$P_2 \leq \varepsilon$}{$P_3 \leq \varepsilon /3$}.

Now, by choosing
$$
t = \delta \quad \text{and} \quad \delta = \frac{1}{\sqrt{8 \ln(6n /\varepsilon)}},
$$
it is not difficult to show that $P_1 \leq \varepsilon /3$ is satisfied. Moreover, with this choice, condition \eqref{eq:condLambdaTr} implies \eqref{eq:m1}.

Finally, observing that
$$
\frac{2}{\delta^2} \left(1 + \frac{2\delta}{3}\right) \leq \replacemath{36}{19} \ln\left(\frac{6n}{\varepsilon}\right)
$$
and taking the minimum over all partitions $\{S_r\}$ of $S^c$ in \eqref{eq:condLambdaTr} concludes the proof.

\subsection{Proof of Theorem \ref{thm:killthetalog}}
\label{proof:noiseless_log}

The proof   is analogous to that of Theorem \ref{thm:noiseless}. Therefore, we will employ the same notation as in Appendix~\ref{proof:noiseless}. By similar arguments, one has
\begin{align*}
\Pbb ( \text{failure of BP}  )
 &\leq \underbrace{2n \exp \left( -\frac{1}{2\alpha^2} \right) }_{P_1}
+\underbrace{\Pbb \left( \| A_S^*A_S - {\Id} \|_{2\to 2}  \geq \delta \right)}_{P_2} + \underbrace{\Pbb\left(  \max_{\ell\in S^c} \|A_S^* A e_\ell \|_2 \geq t  \right) }_{P_3},
\end{align*}
for some $t, \delta >0$ and $\alpha = t /(1-\delta)$.
Note that $P_2 $ is controlled as before using Lemma \ref{lem:localIsometry_ext}. In particular, $P_2 \leq \varepsilon/3 $ if
\begin{align}
\label{eq:m1_log}
m \geq \frac{1+\delta/3}{\delta^2/2} \cdot \Lambda(S,F) \cdot \ln \left( \frac{6s}{\varepsilon} \right).
\end{align}
Thus, let us suppose for the rest of the proof to choose
\begin{equation}
\label{eq:m_choice}
{m \geq c_2 \cdot \Lambda(S,F) \cdot \ln\left(\frac{3n}{\varepsilon}\right)},
\end{equation}
where $c_{2}\geq (1+\delta/3)/(\delta^2/2)$ is a  constant that will be fixed later and where we are using $s \leq  n/2$.
The slight modification in the proof compared to the one in Appendix \ref{proof:noiseless} appears in the control of $P_3$. Indeed, using Lemma \ref{lem:C.5Ext}, one has for some $t'>0$
$$
\Pbb \left( \max_{i\in S^c} \| A_S^* A e_i \|_2 \geq \sqrt{\frac{\Lambda}{m}} + t' \right) \leq n \exp\left(-\frac{m {(t')^2}/2}{\Gamma + 4 \Lambda \sqrt{\Gamma /m} + 2 t' \sqrt{\Lambda\Gamma}/3}\right).
$$
Therefore, combining the above inequality with \eqref{eq:m_choice}, fixing $t'= \frac{1}{2}\sqrt{\frac{\Lambda}{m}}$, and assuming that $ \Lambda \geq c_1 \Gamma \ln(3n/\varepsilon)$,  one has
\begin{align*}
P_3 &\leq n \exp \left(- \frac{\Lambda /8}{\Gamma + 13/3 \Lambda \sqrt{\Gamma /{m}}} \right)
\leq n \exp\left( -\frac{1/8}{1/{c_1} + 13/(3 \sqrt{c_1 c_2})} \ln \left( 3n / \varepsilon \right)  \right)
\leq \varepsilon/3,
\end{align*}
provided that
\begin{equation}
\label{eq:cond_c1_c2}
 \frac{1}{8} \geq \frac{1}{{c_1}} + \frac{13}{3\sqrt{c_1 c_2}}.
\end{equation}

Condition on $P_1 \leq \varepsilon / 3$ remains to be checked. In accordance with the previous computation, we set $t= \frac{3}{2}\sqrt{\frac{\Lambda}{m}} $ and if we choose $\delta =1/2$, with $\alpha = t/(1-\delta) $, we obtain
\begin{align*}
P_1 &\leq \varepsilon/3 \qquad  \Longleftarrow \qquad  m \geq 18 \cdot \Lambda(S,F)  \cdot \ln\left( \frac{3n}{\varepsilon} \right).
\end{align*}
Finally, {we note that \eqref{eq:cond_c1_c2} holds true for, e.g., $c_1 = 50$ and $c_2 = 100$. Therefore,} conditions
\[
\left\{
\begin{array}{ll}
\Lambda (S,F) \geq 50 \cdot  \Gamma (F) \cdot  \ln(3n/\varepsilon)  \\
m \geq 100 \cdot  \Lambda(S,F) \cdot \ln\left( \frac{3n}{\varepsilon} \right),
\end{array}
\right.
\]
ensure that \eqref{pb:BP} exactly  recovers $x$ with probability larger than $1-\varepsilon$.

Note that no effort was made in order to optimize the constants $c_1$ and $c_2$, and the result in the noisy setting can be easily deduced from the noiseless one as in Appendix \ref{proof:noisy}.

config: arxiv


TITLE: Reference Requests: The Turaev-Viro model and Topological QFT's
QUESTION [1 upvotes]: I've been inspired by the string-net condensation paper by Levin and Wen (see here) to learn about the Turaev-Viro model and its relationship to topological QFTs. Any references that could be helpful for accomplishing that would be very welcome. While I'm at it, pedagogical reviews/introductions to topological QFTs would be useful as well. Textbook and paper recommendations are both welcome.
I should also mention that I'm definitely not a mathematician. I'm familiar with the details of non-abelian gauge quantization, and with it the basics of representation theory. I've also made some progress learning about CFTs from the big yellow book (di Francesco et al.). But beyond that, my pure math background is a bit limited, so physically motivated arguments would be most immediately useful to me. But, if you're aware of good sources for learning about relevant math topics, that would be useful as well.

REPLY [1 votes]: Turaev has a new book on exactly this.
Turaev also has a slightly older book that has overlapping material on TQFTs


text:
\section{Binomial Coefficient with Two/Corollary}
Tags: Examples of Binomial Coefficients, Triangular Numbers

\begin{theorem}
:$\forall n \in \N: \dbinom n 2 = T_{n - 1} = \dfrac {n \paren {n - 1} } 2$
where $T_n$ is the [[Definition:Triangular Number|$n$th triangular number]].
\end{theorem}

\begin{proof}
From the definition of [[Definition:Binomial Coefficient|binomial coefficient]]:
:$\dbinom n 2 = \dfrac {n!} {2! \paren {n - 2}!}$
The result follows directly from the definition of the [[Definition:Factorial|factorial]]:
:$2! = 1 \times 2$
{{qed}}
\end{proof}

config: wiki


TITLE: Question of Munkres article 17 problem 10
QUESTION [0 upvotes]: Let $X$ be an ordered set and it is given the order topology.How to show that $X$ is Hausdorff.
I know to show Hausdorff I have to take two points $a,b\in X$ and find disjoint open sets $U,V$ in $X$ such that $a\in U,b\in V$.Without loss of generality I can take $a<b$ .
But I cant proceed after that.Any help will be useful

REPLY [2 votes]: HINT: Suppose that $a<b$. You’ll need to distinguish two cases.

Case $\mathbf{1}$: There is a $c\in X$ such that $a<c<b$. In this case you can use $c$ to produce disjoint open sets containing $a$ and $b$.
Case $\mathbf{2}$: There is no such $c$. This means that $a$ and $b$ are adjacent in $X$. What can you say about the sets $(\leftarrow,b)$ and $(a,\to)$?

In case you’re not familiar with the notation, $$(\leftarrow,b)=\{x\in X:x<b\}$$ and $$(a,\to)=\{x\in X:a<x\}\;.$$


TITLE: Show that $\sqrt{-6}$ is irreducible in $\mathbb{Z}+\mathbb{Z}\sqrt{-6}$
QUESTION [7 upvotes]: Suppose not. Then there exists $\alpha,\beta\in\mathbb{Z}+\mathbb{Z}\sqrt{-6}$ such that $\sqrt{-6}=\alpha\beta\implies\alpha,\beta$ are not units. I'm not really sure where to go from here. Any advice?

REPLY [3 votes]: The concept of norm is extremely important, including the fact that it is multiplicative (meaning that $N(m) N(n) = N(mn)$). Learn it, love it, live it.
What really makes things easy in $\mathbb{Z}[\sqrt{-6}]$ (which is the same thing as $\mathbb{Z} + \mathbb{Z}\sqrt{-6}$, right?) is the fact that there are only two units: 1 and $-1$. How do we know those are the only units? A unit has norm 1 or $-1$. The norm of a number of the form $a + b \sqrt{-6}$ is $a^2 + 6b^2$, so the norm can't be negative. The possible norms in $\mathbb{Z}[\sqrt{-6}]$ are 0, 1, 4, 6, 7, 9, 10, etc. (see Sloane's A002481). Both 1 and $-1$ have a norm of 1, no number in this domain can have a norm of $-1$. If $a > 1$ or $b > 1$, then $N(a + b \sqrt{-6}) > 1$.
2 and 3 are potentially prime because no number in this domain has a norm of 2 or 3. But, as you already know from the other question you asked, $2 \times 3 = -(\sqrt{-6})^2 = 6$, which means 2 and 3 are irreducible but not prime in this domain.
But what about $\sqrt{-6}$? Its norm is 6. If it's reducible, we can find two numbers, neither of them 1, such that $N(\alpha) N(\beta) = 6$. So we're looking for a number with a norm of 2 and another with a norm of 3. But we just saw that there are no numbers in that domain with that norm. Therefore, $\sqrt{-6}$ is irreducible.
If you really want to be sure, you can try each product $(a - b \sqrt{-6})(a + b \sqrt{-6})$ for $0 \leq a \leq 3$ and $b$ likewise.


TITLE: Hidden points in polygons
QUESTION [20 upvotes]: Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point strictly exterior to the closed set $P$.

I have a vague sense that this question—What is $h(n)$?—may have been studied before, and perhaps even entirely resolved, but I am not recalling references. Any help would be appreciated—Thanks!

Answered by Wlodek Kuperberg:

The same construction shows that $h(n)=n-3$ for hiding points in a
polyhedron of $n$ vertices in $\mathbb{R}^3$.

REPLY [14 votes]: OK - following the suggestion of Mariano Suárez-Alvarez, a moderator - I post my comment as an answer:
If k points are mutually invisible in an n-sided poygon, then no two of them lie in the same triangle of a triangulation. Therefore $h(n)≤n−2$, and there is a simple example, generalizing your construction for $n=4$ and $5$, of an $(n+2)$-sided polygon with $n$ mutually invisible points in it, for every $n$: Draw a concave-up arc of a circle tangent to your "V" at its upper ends and place $n$ vertices on it. Place your red points very close to the midpoints of the chords of the circular arc. Unless I misinterpret your question, this shows that $h(n)=n−2\ \ $ for every $n≥3$.


TITLE: Given $2018 \times 4$ grids and tint them with red and blue. So that each row and each column...
QUESTION [3 upvotes]: Given $2018 \times 4$ grids and tint them with red and blue. So that each row and each column has the same number of red and blue grids, respectively. Suppose there're $M$ ways to tint the grids with the mentioned requirement. Determine $M \pmod {2018}$.

Solution?: Each column can be colored such as $$(R,R,B,B),(R,B,R,B),(R,B,B,R),$$$$(B,B,R,R),(B,R,B,R),(B,R,R,B)$$ Say the column colorings appears $a,b,c,a',b',c'$ respectively.
Clearly we must have $a+b+c= a'+b'+c'$ since $R$ appears the same times as $B$ in first row. Simillary we have $a+b'+c' = a'+b+c$ which implies $a=a'$. The same is true for $b=b'$ and $c=c'$. So we have that $a+b+c=1009$ and thus  $$M =\sum_{a+b+c=1009}\frac{2018!}{a!^2b!^2c!^2} \equiv ?\pmod{2018}$$
Edit: after Ross Millikan answer.

My question here is: is this is correct and seeking for an alternative solution via generating functions.

REPLY [1 votes]: We are required to count the number of colourings of a $2018 \times 4$ grid with two colours (red & blue). Well not quite count them all ... just calculate how many there are modulo $2018$. (... Oh yes, forgot to mention the equal number of blues & reds in each row & column constraint).
You state the $6$ possible configurations for each column in your solution and these will be useful later. But we shall first consider the rows.
The first row can be chosen in $ \binom{2018}{1009}$ ways. The second row can also be chosen in $ \binom{2018}{1009}$ ways.
but we cannot simply choose the third & fourth rows like this, indeed looking at the $6$ possible configurations for the columns shows that there are two possibilities. EITHER the first two entries are the same colour and so the third & fourth entries will need to be the other colour OR they are different colours and then third & fourth entries will also need to be
different colours. So given the first row, we need to keep track of how many colours are the same or different in the second row; how will we do this ? ... remember the combinatorial identity
\begin{eqnarray*}
\sum_{i=0}^{n} \binom{n}{i}^2= \binom{2n}{n}.
\end{eqnarray*}
This identity counts how many pairs need to be toggled to get from one binary string with an equal number of $1$'s & $0$'s to another. Now in our situation there will be $2i$ place where the first two colours are different & then the third and fourth are also different. Half of these $2i$ can be chosen arbitarily and the other half will be forced in order to ensure the third & fourth rows have equal numbers of each colour. So the total number of configurations is
\begin{eqnarray*}
\binom{2018}{1009} \sum_{i=0}^{1009} \binom{1009}{i}^2 2^i.
\end{eqnarray*}
But we only want this value modulo $2018$ ... & at this point we consult Wolfy https://www.wolframalpha.com/input/?i=+binom%282018%2C1009%29+sum%28+binom%281009%2Ci%29%5E2+2%5Ei%2C%7Bi%2C0%2C1009%7D%29+mod+2018
So the answer to the question is $\color{red}{6}$.


TITLE: What causes the chaotic trajectory of a balloon going flat?
QUESTION [7 upvotes]: I think this is not a duplicate of the question John mentions. That question asks specifically why the balloon makes a spiraling movement, which in general is not the case (the answers pay only attention to two variables: the nozzle and air resistance, for which there isn't a fixed centre of drag) while I ask the broader question which variables make the movement chaotic (which it is for sure while its velocity responds in a non-linear way to these variables). The non-spiraling movement can be seen as a sequence of (infinite) little pieces of circular trajectories because there are other variables influencing the motion of the balloon too (like the chaotic air movement around the moving balloon, which causes a non-fixed center of drag).
When a balloon goes flat it makes a chaotic movement through the air. Is it the interaction with the air, the behavior of the part through which the air escapes (in which case the balloon will also trace out a chaotic trajectory on the moon), or what?

REPLY [2 votes]: Chaos and irregular motion are not one and the same thing!

Chaotic motion is a precisely defined concept and every irregular motion that you see in a physical system need not be chaotic. However, chaotic motion always seems to be irregular. To be specific, chaotic motion refers to the deterministic motion that sensitively depends on the initial condition of the system. Also, the motion should satisfy things like "boundedness" and "topological mixing".
This means that if you have many obvious random variables in the system, you should not use the term "chaos" to describe the observed irregularities. For example, atomic transitions are irregular, but not chaotic. In the case of the balloon you are describing, we do not have (at least I do not know of) any model that is deterministic. If you have such a model, then one can try to find our whether it exhibits chaotic motion (at least for some ranges of its parameters) and only then you would be able to ask questions like which parameters cause chaos in the model and so on.
In fact, as I see it, the balloon's behavior, in this case, seems to be only a transient to me (because it stops after all the air has escaped) and hence cannot be chaotic. To understand more about the actual concept of chaos, you can try to read this.


TITLE: Am I using these Probability Theory Terms Correctly?
QUESTION [0 upvotes]: Let $\Theta$ be a random variable with sample space $\{\theta_1, \ldots, \theta_n\}$.
Questions:

Is it terminologically correct to refer to $\Theta$ as a "parameter"? What about the members $\theta_k$ of its sample space? Are they also "parameters"?
Are the "values of $\Theta$" the members of the sample space? For example, is $\theta_1$ a value of $\Theta$?

REPLY [0 votes]: If the sample space is a population, each of whose members has an income, then the income of the randomly chosen member of the population is a random variable.  I.e. a random variable is a function whose domain is the sample space.
In some problems each point in the sample space may be a value of the random variable: for example, the outcome when a die is thrown is a member of the set $\{1,2,3,4,5,6\}$, and that may be taken to be the sample space, and the randomly chosen on of those numbers is the value of the random variable.
But in other problems it's different: Suppose two dice are thrown, and the sum of the two resulting number is the random variable you're calling $\Theta$.  Then there is a sample space with $36$ members: the pairs.  But a value of the random variable is not one of the pairs; it is the sum.  Notice that $(1,3)$, $(2,2)$, and $(3,1)$ are different points in the sample space, but all three yield the same value of the random variable, which is $4$.  In that case, if $\theta_1$ is one of the $36$ pairs, then $\theta_1$ is not one of the values of the random variable, but $\theta_1$ is a member of the sample space.
Parameters, however, are something else.  Let's say we paint $N$ of the $3$ marbles in an urn red and the other $3-N$ green.  You will choose one marble at random from the urn.  Let $X$ be the number of red marbles so chosen; thus $X$ must be either $0$ or $1$.  In that case:

$N$ is a parameter;
The sample space is the set of three marbles in the urn;
The random variable is $X$, which must be $0$ or $1$;

In this case, the members of the sample space are not values of the random variable.


text:
\section{\amsgrad/ with momentum}
\label{app:amsgrad-momentum-proofs}
We first show the relation between the \amsgrad/ momentum and heavy ball momentum and then present the proofs with \amsgrad/ momentum in~\ref{app:amsgrad-mom-proofs}
and heavy ball momentum in~\ref{app:amsgrad-hb-proofs}.
\subsection{Relation between the \amsgrad/ update and preconditioned SGD with heavy-ball momentum}
\label{app:amsgrad-momentum-equivalence}
Recall that the \amsgrad/ update is given as:
\begin{align*}
\xkk & = \xk - \etak \,  \smallAkInverse \mk  \quad \text{;} \quad \mk = \beta  \mkm + (1 - \beta) \gradk{\xk}
\end{align*}
Simplifying,
\begin{align*}
\xkk & = \xk - \etak \,  \smallAkInverse (\beta \mkm + (1 -\beta) \gradk{\xk}) \\
\xkk & = \xk - \etak (1 - \beta) \, \smallAkInverse \gradk{\xk} - \etak  \beta \, \smallAkInverse \mkm
\intertext{From the update at iteration $k-1$,}
\xk & = \xkm - \eta_{k-1} \,  \smallAkmInverse m_{k-1} \\
\implies - m_{k-1} & = \frac{1}{\eta_{k-1}} \smallAkm \left(\xk - \xkm \right)
\intertext{From the above relations,}
\xkk & = \xk - \etak (1 - \beta) \, \smallAkInverse \gradk{\xk} + \beta \, \frac{\etak}{\eta_{k-1}} \, \smallAkInverse \smallAkm \left(\xk - \xkm \right)
\end{align*}
which is of the same form as
\aligns{
\xkk & = \xk - \etak \,  \smallAkInverse + \gamma (\xk - \xkm),
}
the update with heavy ball momentum. The two updates are equivalent up to constants except for the key difference that for \amsgrad/, the momentum vector $\paren{\xk - \xkm}$ is further preconditioned by $\smallAkInverse \smallAkm$.
\newpage
\input{Proofs-momentum-mvgavg}

\newpage
\input{Proofs-momentum-hb}


TITLE: Prove that $100|11^{10} - 1$
QUESTION [0 upvotes]: I want to prove divisibility using factoring, So i need to show that $11^{10}-1$ can be written as prime factors of 100.
This is what I've tried:
$$11^{10}-1    $$
$$ (11^{5})^{2}-1$$
$$ (11^{5}-1)(11^{5}+1 )$$
$$10(11^{4}+11^{3}+11^{2}+11^1+1)(12)(11^4-11^3+11^2-11^1+1)$$
$$5*2^3*3[(11^4+11^2+1)+(11^3+11)]*[(11^4+11^2+1)-(11^3+11)]$$
I wanna write the $[(11^4+11^2+1)+(11^3+11)]*[(11^4+11^2+1)-(11^3+11)]$ as $5k$ with $k$ $\in\mathbb{Z}$.
I'd love any help/hint that would move me forward.

REPLY [1 votes]: Hint: $$11\equiv 1 \mod 10$$ so $$11^{10}\equiv 1^{10}\equiv 1 \mod 10$$


TITLE: Theorem 29.1 in Munkres' TOPOLOGY: A Problem in the Proof of the Uniqueness Part
QUESTION [3 upvotes]: Here is Theorem 29.1 in the book Topology by James R. Munkres, 2nd edition:

Let $X$ be a [topological] space. Then $X$ is locally compact Hausdorff if and only if there exists a [topological] space $Y$ satisfying the following conditions:

(1) $X$ is a subspace of $Y$.

(2) The set $Y - X$ consists of a single point.

(3) $Y$ is a compact Hausdorff space.

If $Y$ and $Y^\prime$ are two spaces satisfying these conditions, then there exists a homeomorphism of $Y$ with $Y^\prime$ that equals the identity map on $X$.

Here is the initial part of Munkres' proof:
Step 1

We first verify uniqueness. Let $Y$ and $Y^\prime$ be two [topological] spaces satisfying these conditions. Define $h : Y \longrightarrow Y^\prime$ by letting $h$ map the single point $p$ of $Y - X$ to the point $q$ of $Y^\prime - X$, and letting $h$ equal the identity on $X$. We show that if $U$ is open in $Y$, then $h(U)$ is open in $Y^\prime$. Symmetry then implies that $h$ is a homeomorphism.

First, consider the case where  $U$ does not contain $p$. Then $h(U) = U$. Since $U$ is open in $Y$ and is contained in $X$, it is open in $X$. Because $X$ is open in $Y^\prime$, the set $U$ is also open in $Y^\prime$, as desired.

Now my question is as follows:

Since $U$ is open in $Y$ and contained in $X$, it is open in $X$ --- when $X$ is regarded as a subspace of $Y$ and not necessarily when $X$ is regarded as a subspace of $Y^\prime$. Because $X$ is open in $Y^\prime$, how does it follow from this that $U$, which is open in the subspace $X$ of $Y$ and not necessarily open in the subspace $X$ of $Y^\prime$, is also open in $Y^\prime$? After all, until the final conclusion of the theorem has actually been established,  $Y$ and $Y^\prime$ are different (i.e. potentially non-homeomorphic) topological spaces.

REPLY [1 votes]: The subspace topologies that $X$ inherits from $Y$ and from $Y'$ are identical, so it's rather trivial that if $U\subseteq X$ is an open subset in one of the topologies, it's open in the other.
As for why this implies openness in $Y'$: In general, given that $X\subseteq Y'$ is open and $U\subseteq X$, the following two are equivalent:

$U$ is open in $X$
$U$ is open in $Y'$

The upward implication is a straight-forward application of the definition of subspace topology, and doesn't use the openness of $X$.
The downward implication may be proven as follows: By the definition of subspace topology, there is an open subset $U'\subseteq Y$ such that $X\cap U'=U$. But the left-hand side is an intersection of two open subsets of $Y'$. So it's open in $Y'$.


TITLE: Local Lipschitz function with compact support
QUESTION [1 upvotes]: Let $f:\mathbb{R}\to \mathbb{R}$ a locally Lipschitz continuous with compact support. Is it possible to say that $f$ is Lipschitz continuous over $\mathbb{R}$? over the set where $f$ is nonzero? It's a fact that if $f$ is locally Lipschitz over a compact $K$ then is Lipschitz over this compact. Is it posibble to conclude a similar fact here in this question? Please any help will be appreciated

REPLY [2 votes]: $f$ is Lispchitz on the whole real line. First note that $f$ is bounded. Let $|f(x)| \leq C$ for all $x$. If $f$ is not Lipschtz then we can find points $x_n,y_n$ such that $|f(x_n)-f(y_n)| >n |x_n-y_n|$ for all $n$. This gives $2C >n |x_n-y_n|$  so $x_n-y_n \to 0$. Suppose $f(x)=0$ for $|x| >M$. Now $f$ is Lipschitz  $[-M-1,M+1]$. If $|f(x)-f(y)| \leq K|x-y|$ on this interval you can easily check that $|f(x_n)-f(y_n)| \leq n |x_n-y_n|$ for all $n$ such that $|x_n-y_n| <1$ and $n>K$. This is a contradiction.

REPLY [1 votes]: We can suppose that the support $S$ is a compact convex subset of $\mathbb{R}^n$.
First show that $f$ is lLc on $S$.
Since $f$ is lLc, for each $x$ there is some open $U$ and some $L$ such that $f$ is Lipschitz with rank $L$ on $U$. We can suppose that $U$ is convex without loss of
generality.
Since $S$ is compact, it is covered by a finite number of open sets $U_1,...,U_m$ with
corresponding ranks $L_1,..,L_m$.
Let $L = \max_i L_i$.
Choose $x,y \in S$ and let $p(t) = x+t(y-x)$ be the straight line joining $x,y$.
I need some notation: Call $[0,T] \subset [0,1]$ a finitely covered interval (FCP) iff
there is a partition $t_0=0 < t_1 < \cdots < t_l = T$ such that each segment $[p(t_k),p(t_{k+1})]$ is contained in some $U_j$.
Let $M = \sup \{T \in [0,1] | [0,T] \text{ is a FCP} \}$. Since there is some $U_i$ with $p(0) = x \in U_i$ we see that $M >0$.
Suppose $M < 1$. Since $p(M)$ is in some $U_q$, we see that there is some $\tau \in [0,M)$
such that $p(\tau) \in U_q$. Furthermore, there is some $M' \in (M,1]$ such that $p(M') \in U_q$. Since $[0,\tau]$ is a FCP (by definition of $T$)
we see that $[0,M']$ is a FCP, which contradicts the definition of $T$. Hence $T=1$.
Finally, let $(t_0,...,t_l)$ be a partition of $[0,1]$ such that $[p(t_k),p(t_{k+1})]$ is contained in $U_{m_k}$, $k=0,...,l-1$.
Then $\|f(x)-f(y)\| \le \sum_{k=0}^{l-1} \|f(p(t_k)) - f(p(t_{k+1}))\| \le L  \sum_{k=0}^{l-1} \|p(t_k) - p(t_{k+1})\| = L \|x-y\|$.
To finish, let $x,y$ be arbitrary and define $p$ as above.
If the segment $[x,y]$ does not intersect $S$ then we have $\|f(x)-f(y)\| = 0 \le L \|x-y\|$.
Otherwise, let $t_1 = \min \{ t \in [0,1] | p(t) \in S \} $ and
$t_2 = \max \{ t \in [0,1] | p(t) \in S \} $. Since $S$ is convex, we see that
$[p(t_1),p(t_2)] \subset S$.
Then
\begin{eqnarray}
\|f(x)-f(y)\| &\le& \|f(p(0))-f(p(t_1))\| + \|f(p(t_1))-f(p(t_2))\| + \|f(p(t_2))-f(p(1))\| \\
&=& \|f(p(t_1))-f(p(t_2))\\
&\le& L \|p(t_1)-p(t_2)\|\\
&\le& L \|p(0)-p(1)\|\\
&= & L \|x-y\|
\end{eqnarray}


TITLE: Show that a positive integer $n \in \mathbb{N}$ is prime if and only if $\gcd(n,m)=1$ for all $0<n<m$.
QUESTION [0 upvotes]: Show that a positive integer $n \in \mathbb{N}$ is prime if and only if $\gcd(n,m)=1$ for all $0<m<n$.
I know that I can write $n=km+r$ for some $k,r \in \mathbb{Z}$ since $n>m$
and also that $1=an+bm$. for some $a,b \in \mathbb{Z}$
Further, I know that $n>1$ if I'm to show $n$ is prime.
I'm not sure how I would go about showing this in both directions though.

REPLY [1 votes]: This should be trivial.
If n is prime it has no factors but 1 and n. So gcd (n,m) can only equal 1 or n.  If gcd(n,m) = n then that means n|m.  So m $\ge$ n.  So if m < n then gcd (n,m)=1.
That's one way.
If gcd (n,m)=1 for all m < n, then no number less than n divides n (other than 1).  As no number larger n divides n, n has no divisors except itself and 1.  So n is prime.
That's the other way.


TITLE: Understanding a question
QUESTION [1 upvotes]: If c is randomly chosen from the integers 20 to 99, inclusive, what is
  the probability that $c^3-c$ is divisible by 12?

I have not got the question that what is implying by c?

How to get the outcomes divisible by 12 ?

REPLY [1 votes]: Think to a table:
$$
\begin{array}{c|cc}
c & c^3-c \\
\hline
20 & 7980 & \bullet \\
21 & 9240 & \bullet \\
22 & 10626 \\
\vdots & \vdots \\
98 & 941094 \\
99 & 970200 & \bullet
\end{array}
$$
How many of the numbers in the right column are divisible by $12$ (marked with $\bullet$)? Let's say they are $d$; assuming that “random” means ”uniformly random”, you have $d$ favorable outcomes out of $80$, so the probability is $d/80$.
Now you have two paths: doing all the computations or finding a cleverer way that involves writing $c^3-c=(c-1)c(c+1)$ and reasoning about it.

REPLY [0 votes]: Hint: factorise $c^3-c$. Observe that the factors are consecutive integers with the middle one being $c$.
Now think about what constraints must apply to $c$ for divisibility by $12=3 × 4$. For example if $c$ is odd then the product of the other two integers is divisible by $4$ so $c$ needs to be an odd multiple of $3$ unless one of the others is an even multiple of $3$ and so forth.


TITLE: kinetic formula question
QUESTION [0 upvotes]: The formula is $K = \frac{1}{2}mv^2$.
Which part is the square supposed to influence? Does it affect just $v$, $mv$ or $\frac{1}{2}mv$?
The problem is $\frac{1}{2} (1.2\cdot 10^5 [kg]) \cdot 40.8^2 \left[\frac{m}{s}\right]$. How would this resolve?

REPLY [1 votes]: One has
$$
\frac 12 mv^2=\frac 12 m\cdot v\cdot v\ne\frac 12 (mv)^2=\frac 12 mv \cdot mv=\frac 12 m^2 \cdot v^2
$$ giving here
$$
K=\frac 12 \cdot 1.2 \cdot 10^5 \cdot (40.8)^2=\cdots,
$$ hope you can finish it.


TITLE: Please help solve the time complexity of recurrence
QUESTION [1 upvotes]: I do not know if I am solving this correctly but what I have done is analyzing the run time for the algorithm by step by step walk through and counting the executed statements. Also, what will be the big-O?
STATEMENTS  STEPS
1   if n = 0 then ▷ Terminal condition. **1**
2   f1 ← ShiftRight(b, 2n−1)    **n-1**
3   f0 ← b ⊕ ShiftLeft(f1, 2n−1)    **n-1**
4   f2 ← f0 ⊕ f1;   **n-1**
5   p2 ← Recursive (f2, n − 1); ▷ p2 is the upper half of binary **t(n/2)**
6   p0 ← Recursive(f0, n − 1); ▷ p0 is the lower half of binary  **t(n/2)**
7   return ShiftLeft(p2, 2n−1)  **n-1**

So, in the worst case, we'll have done 1+ (n−1) + (n−1) + (n−1) +t(n/2) +t(n/2) +n-1 computations, for a total run time.
T(n)= 1+ (n−1) + (n−1) + (n−1) +t(n/2) +t(n/2) +n-1
T(n)=4(n – 1) +2t(n/2) +2

REPLY [1 votes]: Use the Master Theorem: you have $1= \log_2(2)$ and $f(n) = \Theta (n^{c}\log^kn)$ where $k = 0$, thus $T(n) = \Theta(n^{c}\log^{k+1}n)$, i.e., $T(n) = \Theta(n\log n)$.


TITLE: Counter example to $b_1^c : b_2^c \subset (b_1 : b_2)^c$
QUESTION [1 upvotes]: Let $\phi : R \to R^\prime $ be a ring homomorphism between unital commutative rings $R$ and $R^\prime$.
Let $b_1, b_2$ be ideals of $R^\prime$.
It's quite easy to prove the following inclusion conserning contractions and colon ideals:
$$(b_1 : b_2)^c \subset   b_1^c : b_2^c $$
But how about the other direction? What would be an example that shows this inclusion is strict?
I try to start from the right and see where the difficulty arises
$x \in b_1^c : b_2^c$
i.e
$xb_2^c \subset b_1^c$
i.e
$xx_2 \in b_1^c$ $\forall x_2$ s.t. $\phi(x_2)\in b_2$
i.e
$\phi(x)\phi(x_2) \in b_1$ $\forall x_2$ s.t. $\phi(x_2)\in b_2$
I think here, if $\phi$ isn't surjective, we don't have inverse image for all elements of $b_2$ and this test is weaker than the one we get from left hand side ($\phi(x)b_2 \subset b_1$).

REPLY [2 votes]: Counterexample
Let $f:\mathbb{Z}\to\mathbb{Z}[x]$ be the inclusion monomorphism and take $I=0$ and $J=(x)$ ideals in $\mathbb{Z}[x]$. We have $I^c=0$ and $J^c=0$, hence $(I^c:J^c)=\mathbb{Z}$. On the other hand, $(I:J)^c=0$.
Therefore, $\mathbb{Z}=(I^c:J^c)\not\subset(I:J)^c=0$.
In fact, you can take $I$ and $J$ arbitrary ideals in $\mathbb{Z}[x]$.


TITLE: Sum of 4th powers modulo 125
QUESTION [3 upvotes]: I have been trying to evaluate $\sum_{i=1}^{125} i^4\pmod {125}$. My attempt has been somewhat like this so far:
We know that 125 has a primitive root. Let's call it $r$. Now we know that $$r,r^2,\ldots, r^{\phi(125)}$$
is actually congruent to the set of positive integers that are less than 125 and relatively prime to it, i.e. all the numbers not divisible by 5. Also note that $\phi(125)=100$. Thus I write the sum as follows:
$$\sum_{i=1}^{125} i^4=(5^4+10^4+15^4+\ldots + 125 ^4)+(1+2^4+3^4+\ldots+124^4)$$
$$=5^4(1+2^4+3^4+\ldots+25^4)+(1+r^4+r^8+\ldots+r^{396})$$
$$\equiv \frac{r^{400}-1}{r^4-1}\pmod {125}$$
$$\equiv 0\pmod {125}$$
But when I calculate the expression using wolphram alpha, I get the answer is 100. Where am I going wrong? Please point out. Thanks in advance.

REPLY [1 votes]: There is not much number theory needed to evaluate this sum. Note that
$$\sum_{i=0}^{125}i^4 = \sum_{i=0}^4\sum_{j=0}^4\sum _{k=0}^4(25i+5j+k)^4$$
Now we apply the binomial formula to
$$(5(5i+j)+k)^4$$
and get
$$5^4(5i+j)^4+{4\choose1}5^3(5i+j)^3k+{4\choose2}5^2(5i+j)^2k^2+{4\choose3}5(5i+j)k^3+k^4$$
The 1st term is $0\pmod{125}$ and if we sum over $k$ the 2nd, 3rd and 4th term vanishes, too, because
$$\sum_{k=0}^4 k=2\cdot 5$$
$$\sum_{k=0}^4 k^2 =6\cdot 5$$
$$\sum_{k=0}^4 k^3 =4\cdot 5^2$$
so only
$$\sum_{i=0}^4\sum_{j=0}^4\sum _{k=0}^4k^4$$
remains and is
$$\sum_{i=0}^4 1 \sum_{j=0}^4 1 \sum_{i=0}^4 k^3\equiv100\pmod{125}$$


TITLE: Movement of the point $A$ on the cylinder
QUESTION [0 upvotes]: We have a point $A$ on the top of a cylinder with radii $1$.After $2.5$ rolls find the movement of point $A$.(Take $\pi=3$ if needed)

For finding the movement of point $A$ we should use pytagoras to find the movement but I had a disscustion with my teacher about the value of $A'B$ I strongly belive that $A'B=2.5*permiter=2.5*2*\pi=15m$ but our teacher tells that $A'B=2.5*2radii=10m$ I don't know why but I strongly belive my answer.So we decided to ask it here to get an answer .A video will be helpful a lot but I don't know how to make one.Please make for me one or tell me how to make one.Thanks.

REPLY [1 votes]: When a circle (or a cylinder) is rolled, it completes one full cycle when point $A$ gets back to its original position relative to the center of the circle, That means it has rotated $2\pi$ radians from its original position relative to the center of the circle. When this one cycle is completed circle travels a distance that is equal to its circumference. Formula of the circumference of the circle is defined as following:
$$C = 2\pi r$$
Now to calculate the distance the circle has traveled $(D)$ we have to multiply the number of cycles $(n)$ the circle has completed with the circumference of the circle, Thus we get a following formula:
$$D = Cn \rightarrow D=2n\pi r$$
Now to find out what is the distance from $B\rightarrow A`$: We know that Number of cycles $(n)$ is equal to $2.5$ and radius is equal to $r = 1 $, We plug in this parameters into the formula  we derived above:
$$B\rightarrow A` = 2 \pi n =5\pi \approx 15.7 $$
We can derive $d$ from Pythagorean theorem:
$$d=\sqrt{(2r)^2+(B\rightarrow A`)^2} \rightarrow d = \sqrt{250.49} \approx 15.8$$
I do not know why your teacher multiplied the radius with the number of cycles to get the distance the circle traveled, Maybe your teacher was trying to calculate something else.
When this circle is rolled point A's trajectory looks like the following image which is called cycloid:

If you are interested, I suggest you watch this video about Brachistochrone Problem