TITLE: Argue that real matrices which are orthogonal form a group
QUESTION [1 upvotes]: Argue that real matrices which are orthogonal form a group with matrix multiplication as the composition.
I know that a group have to satisfy $3$ axioms.
$1.$ $$(a \circ b) \circ c = a \circ (b \circ c)$$
$2.$ $$e \circ a = a \circ e =a$$ where $e$ is identity element
$3.$ $$a \circ a^{-1}=a^{-1} \circ a= e$$
But how should I begin? And is it a finite group?

REPLY [1 votes]: As noted in the comments the key fact here is to prove that the set of orthogonal matrices is closed under multiplication. So, let $A$, $B$ orthogonal matrices, i.e. (by definition) such that $AA^T=I$ and $BB^T=I$. we have:
$$
AB(AB)^T=ABB^TA^T=AA^T=I
$$
so also $AB$ is orthogonal.
Now the other properties are obvious:
1) come from distributivity of matrix multiplication.
2) is true because the identity matrix is orthogonal
3) is proved since  $AA^T=I \Rightarrow A^TA=I \Rightarrow A^-1=A^T$ .


TITLE: First-order Logic with infinite conjunction
QUESTION [1 upvotes]: I have an infinite set of variables X and I want to state that the property that there is a unique variable in X with value 2.
For a finite set, I would write the first-order logic formula:
$$
(x_0 = 2 \wedge x_1 \neq 2 \wedge ... \wedge x_n\neq2)
\vee
(x_0 \neq 2 \wedge x_1 = 2 \wedge ... \wedge x_n\neq2)
\vee
...
$$
For the infinite set X, I could do the same but using infinite conjunction/disjunction.
Alternatively, using second-order logic, I could (if I understand correctly) quantify over X stating.
$$
\exists x\in X. (x=2 \wedge (\forall y\in X. (x=y \vee y\neq 2)))
$$

Is there a name for first-order logic with infinite conjunction/disjunction?
Does the example demonstrate that this logic is then more expressive than first-order logic with finite/binary conjunction/disjunction?

I am clearly not a logician so please don't overwhelm me too much :D

REPLY [1 votes]: The name you are looking for is infinitary logic.
And yes, this is a simple example to show that first order logic cannot do everything.

To makes things a bit more formal: in logic "$X$" is a set of "constant symbols", or "0-ary function symbol", each element of $X$ is an element of your language, and not some set/number.
If you have a set $Y$ of elements of the model(for example, $Y$ is a set of integers), then FOL is enough: $∃y∈Y(y=2)$. But because $X$ is a set of elements of the language, and not the model you are working in you cannot talk about $X$ directly in FOL.


TITLE: Why does the substitution $y=vx^m$ solve an Isobaric ODE?
QUESTION [2 upvotes]: I'd like to know how the substitution $y=vx^m$ makes the equation
$\dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{A(x,y)}{B(x,y)}$ separable.
I am aware that the equation $f(x,y)$ is called isobaric if $f(tx, t^m y)=t^{m-1}f(x,y)$ for some value of $m$.

REPLY [0 votes]: First make the substitution, that is:  $$x^{m}\frac{dv}{dx}+mx^{m-1}v=\frac{A(x,vx^{m})}{B(x,vx^{m})}=\frac{x^{m-1}A(1,v)}{B(1,v)}=x^{m-1}C(v)$$
Which rearranges to $$x^{m}dv+\left(mx^{m-1}v-x^{m-1}C(v)\right)dx=0$$
So $$\frac{dv}{mv-C(v)}+\frac{dx}{x}=0$$


TITLE: Given that a throw with 10 dice produced at least one ace, what is probability p of two or more aces
QUESTION [2 upvotes]: So, the question is:
Given that a throw with 10 dice produced at least one ace, what is probability p of two or more aces?
It is conditional probability problem.
The formula is $$P(A|B) = \frac{P(A\cap B)}{P(B)}$$
P(A) - probability of getting two or more aces in a throw of 10 dice.
P(B) - probability that throw with 10 dice produced at least one ace.
$$P(B) = 1 - \frac{5^{10}}{6^{10}}$$
But, i don't know what should i do further.
The correct answer is: $$1 - \frac{10*5^{9}}{(6^{10} - 5^{10})}$$

REPLY [1 votes]: $P(A)$ is the probability that the throw produced at least $2$ aces, meaning that
$P(AB)$ is the probability that the throw produced at least one ace and at least two aces, which is the same as the probability that the throw produced at least two aces.
You therefore simply need to calculate $P(AB)$ which is the same as $P(A)$.
$P(A)$ is $1-x-y$ where $x$ is the probability that the throw produced no aces and $y$ is the probability that the throw produced precisely one ace.


TITLE: Every prime ideal of a finitely generated $\mathbb{R}$-algebra is an intersection of maximal ideals?
QUESTION [4 upvotes]: Why must every prime ideal of a finitely generated $\mathbb{R}$-algebra (e.g. $\mathbb{R}[X_1,X_2]$) be the intersection of the maximal ideals containing it?

This doesn't follow from the version of the Nullstellensatz I've seen:

if $k$ is an algebraically closed field and $S$ is a finitely generated $k$-algebra and $P$ is a prime ideal of $S$, then $P$ is the intersection of all maximal ideals containing $P$

... since $\mathbb{R}$ isn't algebraically closed! But maybe the same method of proof could work?
Many thanks in advance for any help with this!

REPLY [5 votes]: Let $k$ be a field and $\bar{k}$ its algebraic closure. An algebraic zero of a subset $\Phi$ of $k[x_1,\dots,x_n]$ is an element $(a_1,\dots,a_n) \in \bar{k}^n$ such that $f(a_1,\dots,a_n)=0, \, \forall f \in \Phi$. Then Hilbert's Nullstellensatz says that if $g \in k[x_1,\dots,x_n]$ vanishes at every algebraic zero of $\Phi$, then $g$ is inside the radical of the ideal generated by $\Phi$ (Matsumura, Theorem 5.4).
The next key thing to observe is that given an ideal $I$ of $k[x_1,\dots,x_n]$, there is a $1-1$ correspondence between algebraic zeros of $I$ and maximal ideals of $k[x_1,\dots,x_n]$ that contain $I$. To see that, note that if $m$ is a maximal ideal that contains $I$ and we define $a_i$ to be the class of $x_i$ mod $m$, then $(a_1,\dots,a_n)$ is an algebraic zero of $I$ by the Zariski Lemma. Conversely, if $(a_1,\dots,a_n)$ is an algebraic zero, then $k[a_1,\dots,a_n] = k(a_1,\dots,a_n)$ and the kernel of the $k$-algebra homomorphism $k[x_1,\dots,x_n] \rightarrow k[a_1,\dots,a_n]$ that sends $x_i$ to $a_i$ is a maximal ideal (Matsumura, Theorem 5.1).
Finally, we clearly have that $I \subset \cap_{m \supset I} m$. Conversely, let $f \in \cap_{m \supset I} m$. Then $f$ vanishes at every algebraic zero of $I$ and by Hilbert's Nullstellensatz $f \in \sqrt{I}$.


text:
\begin{document}
\maketitle
\makeatletter
\def\l@subsubsection#1#2{}
\makeatother

\doparttoc
\faketableofcontents

\begin{abstract}
  We consider a commonly studied supervised classification of
  a synthetic dataset whose labels are generated by feeding a one-layer neural network with random \iid inputs.

We study the generalization performances of standard
  classifiers in the high-dimensional regime
  where $\alpha={\nsamples}/{\ndim}$ is kept finite in the limit
  of a high dimension $\ndim$ and number of samples $\nsamples$.

Our contribution is three-fold: First, we prove
  a formula for the generalization error achieved by $\rL_2$ regularized
  classifiers that minimize a convex loss.

  This formula was first
  obtained by the heuristic replica
  method of statistical physics.

 Secondly, focussing on commonly used loss functions and optimizing
 the $\rL_2$ regularization strength, we
  observe that while ridge regression performance is
  poor, logistic and hinge regression are surprisingly able to
  approach the Bayes-optimal generalization error extremely closely.

  As $\alpha \to \infty$ they lead to Bayes-optimal rates, a fact that does
  not follow from predictions of margin-based generalization error bounds.

Third, we design an optimal loss and regularizer that provably leads to Bayes-optimal
  generalization error.
\end{abstract}

\newpage

\section{Introduction}
\input{files/introduction.tex}

\section{Main technical results}
\input{files/technical.tex}

\section{Generalization errors}
\input{files/applications.tex}

\section{Reaching Bayes optimality}
\input{files/optimality.tex}

\newpage
\section*{Acknowledgments}
\input{files/acknowledgment.tex}

\bibliographystyle{unsrt}
\bibliography{assets/refs}

\newpage

\appendix
\input{appendix.tex}

\end{document}

config: arxiv


TITLE: "Uncertainty principle" for self-adjoint operators in a finite von Neumann algebra
QUESTION [5 upvotes]: Let $M\subset B(\mathcal H)$ be a finite von Neumann algebra of bounded operators on a Hilbert space $\mathcal H$., let $P\in M$ be a self-adjoint operator with a pure-point spectrum (for example a projection), and let $T\in M$ be another self-adjoint operator.
The question will be formulated in the case of $P$ being a projection. Let $\mathcal H_0$ and $\mathcal H_1$ be the eigenspaces of $P$.

Question: Is there a well-studied condition on $P$ and $T$ which would imply that there exists $\epsilon$ such that whenever $U\subset \mathcal H$ is a "generalized eigenspace" of $T$ (i.e. the image of a spectral projection of $T$) then there exists $u\in U$ of norm $1$ such that $u=h_1+h_2$, $h_1\in \mathcal H_1$, $h_2\in \mathcal H_2$, and the norm of $h_2$ is at least $\epsilon$?

In particular (EDIT: the previous version had a weeker ergodicity assumption, in which case the answer is negative, by the answer of Steven Deprez below)

Question: If a discrete group $\Gamma$ acts freely and in a measure preserving way  on a probablity measure space $X$, each element of $\Gamma$ acts ergodically, $M=L^\infty(X) \rtimes \Gamma$, $P$  is the characteristic function of some subset of $X$ of positive measure, and $T = \sum_{\gamma\in \Gamma} f_\gamma \gamma$, where $f_\gamma$ are real-valued positive functions on $X$ such that $\sum f_\gamma=1$; do $T$ and $P$ fulfill the property from the question?

REPLY [2 votes]: A refinement of the argument from my previous answer:
For any free, pmp, ergodic action of any non-trivial countable group, $\Gamma\curvearrowright (X,\mu)$, there is a projection $P\in L^\infty(X,\mu)$ and a $T=\sum_{\gamma\in\Gamma}f_\gamma\gamma$ such that the $f_\gamma$ are positive functions adding to $1$, and such that $T$ and $P$ do not fulfill the property from the question.
We can assume that every nontrivial element of $\Gamma$ acts ergodically on $X$. In particular, $\Gamma$ does not have any finite subgroups and sice the action is free, $X$ is non-atomic.
Let $e\not=g\in \Gamma$ be any element. Take any non-trivial subset $U_0\subset X$. Since $gU_0\not=U_0$, we see that $U_1=U_0\setminus gU_0$ is a non-null set. Now we know that $U_1\cap g^{-1}U_1=\emptyset$. Choose a subset $U\subset U_1$ with measure $\mu(U)<\frac14$. This set still satisfies $U\cap g^{-1}U=\emptyset$. Denote $V=X\setminus (U\cup g^{-1}U)$ and $W=V\cap gV$. Observe that $\mu(W)\geq 1-4\mu(U)>0$.
Now, set $T=\chi_V + \chi_U u_g + \chi_{g^{-1}}u_g^\ast$ and $P=1-\chi_W$. Observe that $T\chi_W=\chi_W$. It follows that every vector $\xi\in Ran(\chi_W)$ is an eigenvector of $T$ with eigenvalue $1$. For any subset $A$ of the spectrum of $T$, denote the corresponding spectral projection by $p_{T,A}$. It follows that $p_{T,A}\leq 1-\chi_W=P$ for every subset $1\not\in A\subset \sigma(T)$ of the spectrum, not containing $1$. This contradicts the property from the question.


TITLE: Prove the following Statement is a tautology
QUESTION [0 upvotes]: I need to prove the following statement is a tautology
[¬Q∧(P→Q)]→¬P
So far this is what i have but now i am stuck any advice on further finishing this problem would be helpful.
[¬Q∧(P→Q)]→¬P
[¬Q∧(¬P∨Q)]→¬P
[(¬Q∧¬P)∨(¬Q∧Q)]→¬P
¬[(¬Q∧¬P)∨(¬Q∧Q)]∨¬P
((Q∨P)∧(Q∨¬Q))∨¬P
[(Q∨P)∧T]∨¬P

And that's all i have so far. I can't figure out how to go from there. I can't use truth tables i must prove it using a series of logical equivalences.
Any help or ideas going on with this problem?
EDIT1:
I somewhat notice now can i do this?
[(Q∨P)∧T]∨¬P
(Q∨P)∧(¬P∨T)
Q∨T∨T
True!?!

REPLY [1 votes]: i think what you did until here:
[(Q∨P)∧T]∨¬P
is correct. But then you can simply forget about the T; the formula above is logically equivalent to
(Q∨P)∨¬P
which is simply
Q∨P∨¬P
Q∨T
T.


text:
{\bf Problem.} John is 24 years younger than his dad. The sum of their ages is 68 years. How many years old is John?
{\bf Level.} Level 1
{\bf Type.} Algebra
{\bf Solution.} Let $j$ be John's age and $d$ be his dad's age. We are trying to find the value of $j$. We can create a system of two equations to represent the given information. They are

\begin{align*}
j &= d - 24 \\
j + d &= 68 \\
\end{align*}We want to find $j$, so we need to eliminate $d$ from the equations above. Rewriting the first equation we get $d = j+24$. Substituting this into the second equation to eliminate $d$, we have $j+(j+24)=68$, or $j=22$. Thus, John is $\boxed{22}$ years old.

set_name: MATH


TITLE: Riemann Zeta Function-like Integral with Generalized Lower Bound
QUESTION [0 upvotes]: During my studies, I've encountered the following integral where $a \in \mathbb{R}_{\ge0}$

$$\int_{a}^{\infty}\frac{\sqrt{x}}{e^{x}-1} dx$$

I know if $a=0$, this evaluates to $\Gamma(\frac{3}{2})\zeta(\frac{3}{2})$, but I'm not sure how to handle the generalized lower bound.
Appreciated.

REPLY [1 votes]: I shall assume $a>0$.
Write
$$\frac{\sqrt{x}}{e^{x}-1}=\sum_{n=0}^\infty  \sqrt{x}\,  e^{-(n+1) x}$$
$$\int_a^\infty \sqrt{x}\,  e^{-(n+1) x}\,dx=\sqrt{a}\,\,\frac{ e^{-a (n+1)}}{n+1}+\frac{\sqrt{\pi }}{2}\frac{\text{erfc}\left(\sqrt{a (n+1)}\right)}{(n+1)^{3/2}}$$
$$\color{red}{\int_a^\infty \frac{\sqrt{x}}{e^{x}-1}= \Gamma \left(\frac{3}{2}\right)\zeta \left(\frac{3}{2}\right)-\sqrt{a} \log
   \left(1-e^{-a}\right)-}$$ $$\color{red}{\frac{\sqrt{\pi }}{2}\sum_{n=0}^\infty \frac{\text{erf}\left(\sqrt{a (n+1)}\right)}{(n+1)^{3/2}}}$$


TITLE: In which sense "closure" is a closure?
QUESTION [3 upvotes]: In predicate and first-order logic, if $\phi$ is a sentence, then $\forall X . \phi$ is said to be the (universal) closure of $\phi$. Is the use of the word "closure" incidental, or is there a connection with closure as meant in topology, or in lattice theory, or whatever? In the latter case, what is the exact connection?

REPLY [2 votes]: The notion of an algebra with an existential quantifier $\exists$ has been algebraized to the notion of a monadic algebra and a monadic algebra is a Boolean algebra with a closure operator on it such that the closed sets form a Boolean subalgebra.
A closure operator on a poset $X$ is a mapping $C:X\rightarrow X$ such that $x\leq C(x)=C(C(x))$ whenever $x\in X$ and $x\leq y\rightarrow C(x)\leq C(y)$.
It was shown by Kuratowski that the closure operators for the topologies on a set $X$ are precisely the closure operators $C:P(X)\rightarrow P(X)$ such that $C(0)=0$ and $C(R\cup S)=C(R)\cup C(S)$, but closure operators appear in all areas of mathematics.
A monadic algebra is a pair $(B,\exists)$ such that $B$ is a Boolean algebra and $\exists:B\rightarrow B$ is a closure operator on $B$ such that $\exists(x\vee y)=\exists x\vee\exists y$ and $(\exists x)\wedge y=0$ if and only if $x\wedge\exists y=0$. Monadic algebras are useful in algebra since the monadic algebras are in a one-to-one correspondence with the relatively complete Boolean subalgebras of a Boolean algebra. Furthermore, Monadic algebras satisfy the rule $C(R\cup S)=C(R)\cup C(S)$, so monadic algebras can be thought of as special kinds of $``$topological$"$ closure operators on Boolean algebras.
Finally, I should mention that the monadic algebras of the form $(P(X),\exists)$ are precisely the algebras where there exists some equivalence relation $E$ on $X$ so that $\exists R=E[R]$ for all $R\subseteq X$. In this case, monadic algebras are the trivial topological closure operators.


TITLE: Unbounded Random Variable
QUESTION [2 upvotes]: 1) Is there such thing as an unbounded random variable? Can a variable attain values of infinity (I thought this was only something you could tend towards)? Or would the probability of reaching infinity just be zero?
2) If so, can a random variable have unbounded expectation or variance?
Simple examples are much appreciated, thanks!

REPLY [3 votes]: Consider random variable defined on set of atural numbers $\mathbb N$ as,
$X:\mathbb N \to \mathbb R$ and $X(n)=n$
Note that above random variable is unbounded and also its expectation is infinity.
If you know concept of measure then random variable is just a measurable function.


text:
\subsection{The Distributed Kaczmarz Algorithm with Relaxation}
Each iteration of the distributed Kaczmarz algorithm begins with an estimate $\vec{x}^{(n)}$ at the root of the tree; the superscript indicates the number of times that we iterated through the tree to obtain the estimate for some given initial estimate $\vec{x}^{(0)}$. An iteration of the algorithm occurs in two stages: {\em dispersion} followed by {\em pooling}. In the dispersion stage, a new estimate is first calculated at the root using the Kaczmarz update with the relaxation parameter $\omega_r$,
\[
\vec{x}_r^{(n)} = \vec{x}^{(n)} + \omega_r\dfrac{b_r - \vec{a}_r^*\vec{x}^{(n)}}{\|\vec{a}_r\|^2}\vec{a}_r =: Q_r^{\vec{\omega}}\vec{x}^{(n)}.
\]
Each subsequent vertex $v \neq r$ receives an input estimate $\vec{x}^{(n)}_u$ from its parent $u$ (i.e., $u \leftarrow v$), and a new estimate is calculated at the vertex $v$ using the Kaczmarz update with relaxation parameter $\omega_v$,
\[
\vec{x}^{(n)}_v = \vec{x}^{(n)}_u + \omega_v\frac{b_v-\vec{a}_v^*\vec{x}_u^{(n)}}{\lVert \vec{a}_v\rVert ^2}\vec{a}_v =: Q^{\vec{\omega}}_v\vec{x}^{(n)}_u.
\]
Each leaf $\ell$ then has its own estimate $\vec{x}^{(n)}_\ell$ at the end of the dispersion stage.

In the pooling stage, we back-propagate the leaf estimates, weighting along the edges, to obtain the next iterate in the algorithm,
\[
\vec{x}^{(n+1)} = \sum_{\ell \in \mathcal{L}}w(r,\ell)\vec{x}^{(n)}_\ell.
\]

It was shown in \cite{Hegde2019} that the distributed Kaczmarz algorithm with fixed relaxation parameters $\omega_v = \omega \in (0,2)$ converges to the solution of minimal norm when the system is consistent and converges to an approximate solution related to some weighted least-squares solution, dependent on the parameters and the network topology, when the system is inconsistent.


TITLE: How to find estimated total time, based on time elapsed and bytes downloaded?
QUESTION [0 upvotes]: I'm doing C programming exercise for college, and couldn't figure out how to calculate the following value based on four values (2 of each from one type of variable). The exercise is to write a program for a progress bar for downloading a file.
Given values/variables:

time: the current time
startTime: the download start time
bytes: the number of bytes downloaded
totalBytes: the total file size in bytes

The program needs to calculate the Elapsed_Time, Percent_Completed, Download_Speed, Total_Time and Remaining_Time.
I can't figure out the formula for Total_Time. That is the estimated total time to download the file.
I used this, but didn't work:
(time - startTime) / (totalBytes - bytes)
Any help is appreciated. Cheers

REPLY [1 votes]: You have spent time-startTime downloading bytes.  So you would estimate the rate of download as $\frac {\text{bytes}}{\text{time-startTime}}$.  Then the total estimated time is totalBytes divided by this.  $\text {Total_Time}=\frac{\text{totalBytes(time-startTime)}}{\text{bytes}}$


TITLE: Topology on $X$ that is $T_0$ but not $T_1$
QUESTION [1 upvotes]: Show that if $\text{card}(X) \geq 2$, there is a topology on $X$ that is $T_0$ but not $T_1$
Consider the point set $\{a,b\}$  where $b>a$. Then, the topological space of this set is $T_0$ as there is an open neighborhood of one that does not contain the other. But this is not $T_1$ as $b$ won't be closed. By induction, the following holds for  $\text{card}(X) \geq 2$. Is this okay?

REPLY [1 votes]: No induction needed. Let $p$ and $q$ be distinct points of $X$.
Define $\mathcal{T} = \{A \subseteq X: p \in A\} \cup \{\emptyset\}$, which is a topology (the included point topology).
Then $(X,\mathcal{T})$ is $T_0$ (if $x \neq y$ then one of them is not $p$ (say $x$) and then $X\setminus\{x\}$ is open and contains $y$ and not $x$), but not $T_1$ as $\{p\}$ is not closed, as $X\setminus \{p\}$ is not open (it's non-empty because of $q$ and does not contain $p$, so it's not in $\mathcal{T}$).
As an alternative, put a linear order on $X$ (uses axiom of choice) and we have two points $p < q$ WLOG.
Define the topology (upper topology) by $\mathcal{T}_u=\{\emptyset,X\} \cup\{(x,\infty): x \in X\}$, where $(x,\infty) = \{p \in X: x < p\}$.
This is $T_0$ because if $x \neq y$, then $x < y$ (WLOG) and then $y \in (x,\infty)$ and $x$ is not in that set. It is not $T_1$, e.g. because $p$ will always be in the closure of $\{q\}$ when $p < q$ (as chosen above).


TITLE: Absolute value of a complex exponential
QUESTION [0 upvotes]: I want to prove that  $ \left|e^{2iRe^{it}}\right| = e ^{ -2R\sin(t)} $  for some constant R.
I know that  $  e ^{ -2R\sin(t)}= e^{-2R\times\text{Im}(e^{it})}  $   where Im denotes the imaginary part, so i just need to prove that
$$ \left|e^{2iRe^{it}}\right| =  e^{-2R\times\text{Im}(e^{it})} $$
but i can not find the relation between the complex modulus and the imaginary part.

REPLY [2 votes]: Hint: $\left| e^{x+iy} \right| =  \left| e^{x} \right| \left| \cos y + i\sin y\right| = e^x$ for $x, y \in \mathbb{R}$.


TITLE: "Logical identity" as defined in Munkres
QUESTION [0 upvotes]: The following passage, on a concept which should be rather straightforward, is directly out of Munkres's Topology:

The equality symbol $=$ is used throughout this book to mean logical identity. Thus, when we write $a = b$, we mean that "$a$" or "$b$" are symbols for the same object.

I haven't ever heard of the term "logical identity." The only other use of it I have been able to find is in reference to propositions $p$ and $q$, in the context of writing $p \iff q$. It makes sense to say that if $a = b$, then we have $a \iff b$ in the sense that if something is equal to $a$, it is also equal to $b$. Is this what Munkres is getting at? Is there a clearer way of thinking about this?

REPLY [2 votes]: $a=b$ is certainly not the same as $a \Leftrightarrow b$
$a =b$ is about the identity of objects.
$a \Leftrightarrow b$ is about the logical equivalance of claims.
Note that $a=b$ is a claim, but $a$ and $b$ need not be claims themselves; they can be any object. And even if they happen to be claims then we mean to say that they are the exact same claim, not merely logically equivalent claims. So, for example, if $a$ refers to the claim $P$ and $b$ also refers to the claim $P$, then we have $a=b$, but with $a$ being $P$ and $b$ being $\neg \neg P$, we do not have $a=b$, but we do have $a \Leftrightarrow b$
But again, $a$ and $b$ need not refer to claims at all, and often when used in logic expressions they do not. They could, for example, refer to numbers, and then $a=b$ makes the claim that $a$ and $b$ are the same number. And, in that case, $a \Leftrightarrow b$ makes no sense at all: logical equivalence does not apply to numbers.
The author probably uses the term logical identity to stress the fact that the = is a logical symbol (a symbol of the language of logic) and thus has a fixed interpretation ... namely the interpretation of identity.


TITLE: Objects of which Grothendieck abelian categories have elements?
QUESTION [9 upvotes]: The Freyd-Mitchell embedding theorem is a very useful tool for dealing with small abelian categories. However, it does not allow to use "elements" of objects of an abelian category $A$ in those statements that involve "infinite constructions".
So I wonder: for which Grothendieck abelian $A$ (this certainly implies that $A$ is not small if it is non-zero) there exists an exact conservative functor $F$  into abelian groups (this is a certain weak substitute of "having elements")?  Does the Gabriel-Popescu theorem help here (so, what can one say if $A$ is described as a "nice" localization of certain category of modules)?
Also, how would you call a functor $F$ possessing this property; does "a stalk functor" sound fine? What is the relation of the existence of $F$ condition to the existence of compact generators for $D(A)$? If $A$ is a category of sheaves for certain Grothendieck topology then can one relate $F$ to the points of this topology?
Any hints, references or examples are very welcome!

REPLY [1 votes]: I am not an expert of the abelian world, but I think I can answer.
Since my background is not precisely abelian, I will start with an example in category theory.

Thm. Let $\mathcal{K}$ be a locally $\kappa$-presentable category, then there is a faithful and conservative functor to Set that preserves $\kappa$-directed colimits.

Proof. Since $\mathcal{K}$ is a locally $\kappa$-presentable category, it has a strong generator $\mathcal{G}$ made by $\kappa$-presentable objects. Then, the functor $\coprod_{G \in \mathcal{G}} \text{hom}_{\mathcal{K}}(G, \_)$ is faithful and conservative. Moreover it preserves $\kappa$-directed colimits and connected limits.
It looks to me that with the same argument one can prove the following statement.

Thm. Let $\mathcal{A}$ be an abelian category with a strong projective generator, then it has an exact, faithful and conservative functor into $\mathbb{Ab}$. Moreover, if the generator is made by $\kappa$-presentable objects, the functor preserves $\kappa$-directed colimits.

Observe that the functor is left exact because $\mathbb{Ab}$ is AB4.
Moreover, the following holds.

Thm. Let $\mathcal{A}$ be a Grothendieck category with a faithful and conservative functor in $\mathbb{Ab}$ which is accessible, exact and preserve connected limits. Then $\mathcal{A}$ has a  projective strong generator.

Proof. Call $F$ such a functor, then it must have a multiadjoint. This is equivalent to the fact that $F \cong \coprod_{G \in \mathcal{G}} \text{hom}_{\mathcal{A}}(G, \_)$ for a small family $\mathcal{G}$. Since $F$ is faithful and conservative, $\mathcal{G}$ must be a strong generator.


TITLE: Convergence of Fibonacci quotients
QUESTION [1 upvotes]: Let $F_n=F_{n-1}+F_{n-2},~ F_0=0,~F_1=1~$ be the Fibonacci numbers.
Then it is well known that $\lim_n \frac{F_{n+1}}{F_n}=\frac{1+\sqrt{5}}{2}$.
However, many textbooks proved the above by using only the property $S_{n+1}=1+{S_{n}}^{-1}$ where $S_n=\frac{F_{n}}{F_{n-1}}$. I think this proof should first assume the convergence of $S_n$. How can I get the convergence of the quotients?
Any help will be appreciated.

REPLY [3 votes]: From the identity $F_n^2 - F_{n+1}F_{n-1} = (-1)^{n-1}$, we get
$$
\left| \frac{F_{n+2}}{F_{n+1}} - \frac{F_{n+1}}{F_n}\right| = \frac{1}{F_nF_{n+1}}\le \frac{F_{n+1}-F_n}{F_nF_{n+1}} = \frac{1}{F_n} - \frac{1}{F_{n+1}}
$$
for $n\ge 2$, so for $m>n\ge 2$ we get
$$
\left| \frac{F_{m+1}}{F_m} - \frac{F_{n+1}}{F_n} \right| \le \frac{1}{F_n} -\frac{1}{F_m}
$$
You can check that $F_n\to\infty $ as $n\to\infty$, so the above inequality says that $\langle F_{n+1}/F_n\rangle$ is a Cauchy sequence.


TITLE: Derivation of Gordon identity from Srednicki
QUESTION [2 upvotes]: On srednicki page 240 (print) there is a derivation of the Gordon identity, and it starts with stating that
$$
\require{cancel} \gamma^{\mu}\cancel{p} = \frac{1}{2} \big\{\gamma^{\mu},\cancel{p} \big\} + \frac{1}{2} \big[ \gamma^{\mu},\cancel{p} \big] = -p^{\mu} -2iS^{\mu\nu}p'_\nu{}
$$
Where exactly does this come from?

REPLY [4 votes]: Let $\gamma^\mu$ be a gamma matrix, i.e.,
$$
\frac{1}{2}(\gamma^\mu\gamma^\nu+\gamma^\nu\gamma^\mu)=-\eta^{\mu\nu} \tag{1}
$$
Let
$$
S^{\mu\nu}\equiv\frac{i}{4}(\gamma^\mu\gamma^\nu-\gamma^\nu\gamma^\mu) \tag{2}
$$
Let us write
$$
\gamma^\mu\gamma^\nu=\frac{1}{2}(\gamma^\mu\gamma^\nu+\gamma^\mu\gamma^\nu) \tag{3}
$$
(note that I did nothing yet)
Next, write
$$
0=\frac{1}{2}(\gamma^\nu\gamma^\mu-\gamma^\nu\gamma^\mu) \tag{4}
$$
and add it to $(3)$:
$$
\gamma^\mu\gamma^\nu=\frac{1}{2}(\gamma^\mu\gamma^\nu+\gamma^\mu\gamma^\nu)+\frac{1}{2}(\gamma^\nu\gamma^\mu-\gamma^\nu\gamma^\mu)=\frac{1}{2}(\gamma^\mu\gamma^\nu+\gamma^\nu\gamma^\mu)+\frac{1}{2}(\gamma^\mu\gamma^\nu-\gamma^\nu\gamma^\mu)
\tag{5}
$$
where I just rearranged the terms.
Finally, plug $(1)$ and $(2)$ into $(5)$:
$$
\gamma^\mu\gamma^\nu=-\eta^{\mu\nu}-2iS^{\mu\nu} \tag{6}
$$
This is all we need to prove the relation given by Srednicki:
$$
\gamma^\mu\not p\equiv p_\nu\gamma^\mu\gamma^\nu=p_\nu(-\eta^{\mu\nu}-2iS^{\mu\nu})=-p^\mu-2iS^{\mu\nu}p_\nu \tag{7}
$$

Note that this can be slightly generalised: let $a^\mu,b^\mu$ be any two objects (vector, matrices, operators, etc.)
With this
$$
a^\mu b^\nu=\frac{1}{2}\{a^\mu,b^\nu\}+\frac{1}{2}[a^\mu,b^\nu] \tag{8}
$$
as can be easiliy checked by expanding the commutators. In this case, $a^\mu=b^\mu=\gamma^\mu$, so that $(6)$ follows after realising that $\{\gamma^\mu,\gamma^\nu\}=-2\eta^{\mu\nu}$ by definition of the gamma matrices, and $[\gamma^\mu,\gamma^\nu]=-4iS^{\mu\nu}$ by definition of $S^{\mu\nu}$.


text:
\DOC gcd

\TYPE {gcd : int -> int -> int}

\SYNOPSIS
Computes greatest common divisor of two integers.

\DESCRIBE
The call {gcd m n} for two integers {m} and {n} returns the (nonnegative)
greatest common divisor of {m} and {n}. If {m} and {n} are both zero, it
returns zero.

\FAILURE
Never fails.

\EXAMPLE
{
  # gcd 10 12;;
  val it : int = 2

  # gcd 11 27;;
  val it : int = 1

  # gcd (-33) 76;;
  val it : int = 1

  # gcd 0 99;;
  val it : int = 99

  # gcd 0 0;;
  val it : int = 0
}

\SEEALSO
gcd_num, lcm_num.

\ENDDOC

subset_name: curated


TITLE: Limits in Double Integration
QUESTION [3 upvotes]: can someone please help me understand how to find the 'new' limits for double integration. I know that you have to split up the area and fix x or y. If you can go through an example with me then I would be grateful as I keep getting this wrong. We have only been taught how to work out the area of a triangle and so a quadrilateral makes no sense to me.... Btw please don’t give 'genera;' advice because I seriously won’t get it. I have looked in my books/lecture notes but it’s all just general theory which isn’t helpful.
Example question: By making an appropriate substitution, find the area of D and check the substitution is a 1-1 transformation by finding the inverse explicitly.
$$ \iint_D \exp{[xy(x-y)]} (x^2-y^2) {\rm d}x\, {\rm d}y$$
Here is the diagram:

Thanks for the help!

REPLY [7 votes]: You don't have to split up the area. The boundary curves of $D$ are given by constant values of $x-y$ and $xy$. Thus, it makes sense to transform to new variables $u=x-y$ and $v=xy$; then the integration region will turn into an axis-parallel rectangle, and you can just perform the integration without further worrying about the integration limits.


TITLE: prove that $B(\mathbb{R}) = \mathcal{F}(L^1(\mathbb{R}))$
QUESTION [1 upvotes]: For $p=1,2,$ let $L^p(\mathbb{R})$ be the set of Lebesgue measurable functions $f:\mathbb{R}\to\mathbb{C}$ so that $\lVert f\rVert_p < \infty,$ where $\lVert f\rVert_1 := \int_{\mathbb{R}} |f(x)|dx$ and $\lVert f\rVert_2 := (\int_{\mathbb{R}} |f(x)|^2dx)^{1/2}$. Let for $f,g\in L^2(\mathbb{R}), f\star g = \int_{\mathbb{R}} f(y)g(x-y) dy.$ Let $B(\mathbb{R}) = \{f\star g :f,g\in L^2(\mathbb{R})\}.$ Prove $B(\mathbb{R}) = \mathcal{F}(L^1(\mathbb{R}))$, where $\mathcal{F}(f) = \hat{f}, \hat{f}(t) = \int_{\mathbb{R}} f(x) e^{-itx} dx$ for all $f\in L^1(\mathbb{R})$.

Prove that $B(\mathbb{R}) = \mathcal{F}(L^1(\mathbb{R}))$.

Prove that $B(\mathbb{R})$ is dense in $C_0(\mathbb{R})$.

I know some properties of $f\star g$ such as the fact that $\lVert f\star g\rVert_p \leq \lVert f\rVert_p \lVert g\rVert_1$ for $p=1,2$. Also, the set of continuous compactly supported functions on $\mathbb{R}$ is dense in $L^p(\mathbb{R})$ and it's usually easier to work with these functions when integrating (E.g. Fubini's theorem applies). Also, I know that $f(x) = \lim\limits_{A\to\infty} \dfrac{1}{2\pi} \int_{-A}^A \hat{f}(t) e^{itx} dx$ for almost every $x$ when $f\in L^2(\mathbb{R})$ and $\hat{f}(x) = \lim\limits_{A\to\infty} \int_{-A}^A f(t) e^{-itx} dx$ for almost every $x$ when $f\in L^2(\mathbb{R})$ .

REPLY [1 votes]: The  Fourier transform is an isometry onto $L^2(\mathbb R)$ (up to a constant factor), see https://en.wikipedia.org/wiki/Plancherel_theorem.
Moreover, the Fourier transform maps convolution to multiplication, see https://en.wikipedia.org/wiki/Convolution_theorem. Thus the question is equivalent to showing that
$$\{h u \, :\,  h,u\in L^2(\mathbb{R})\}=L^1(\mathbb{R}) .$$
Given $h,u\in L^2(\mathbb{R})$,the Cauchy-Schwarz inequality implies that
$hu \in L^1(\mathbb{R}) .$ Conversely, given $\psi \in L^1(\mathbb{R}) ,$
take $h=\text{sgn}(\psi)\cdot \sqrt{|\psi|}$ and $u=  \sqrt{|\psi|}$ so that
$h,u\in L^2(\mathbb{R})$.


text:
\section{Algorithmic AMP phase transition regime}\label{app:AMPregime}

In this appendix we show that the right-hand side of the bound in theorem~\ref{AMP-theorem} for signal strength and sparsity scaling like $\lambda_n \rho_n^2= w$
and $\rho_n = \Omega((\ln n)^{-\alpha})$ with $w, \alpha\in \mathbb{R}_{+}$, tends to zero as $n\to +\infty$. We focus on the Bernoulli prior case but the arguments generalizes to Bernoulli-Rademacher prior.

Let us first upper bound $\gamma_n^{t}$ in terms of $\lambda_n$ and $\rho_n$ in the Bernoulli case. First we use the bound $\vert f_t^\prime(x)\vert \leq \sqrt{\lambda_n}$ (see lemma~\ref{lem:PL_cond}) to bound
$$\max\{1, \hat{\textsf{b}}_1\}  \max\{1, \hat{\textsf{b}}_2\} \cdots  \max\{1, \hat{\textsf{b}}_{t-1}\} \leq \lambda_n^{\frac{t-1}{2}}.$$
From the explicit AMP iteration (see appendix G second formula for example) we have
$\tau^n_{t} \leq \rho_n$. Since $\nu_n = 12\rho_n$ we get
$(\nu^n +  \tau^n_{1})  (\nu^n +  \tau^n_{1} +  \tau^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \tau^n_{i}) \leq (12\rho_n + \rho_n) (12\rho_n + 2\rho_n) \cdots (12\rho_n + t \rho_n) \leq \frac{1}{6} (12+t)! \rho_n^{t}$.
Putting everything  together we get:
$$
\gamma_n^t \leq \frac{1}{6} (12+t)! \rho_n^{t} \lambda_n^{2t  -1+ \frac{t-1}{2}} .
$$
Now we use the scaling (which is the correct scale for the phase transition to happen) $\lambda_n = w \rho_n^{-2}$ and get:
$$
\gamma_n^t \leq \frac{1}{6} (12+t)! \frac{w^{\frac{5t -3}{2}}}{\rho_n^{4t-3}} .
$$
Therefore
$$
\textsf{bound}_t \leq  C C_{t} \exp\Big\{ - \frac{6c}{w^\frac{5t -3}{2}} \frac{c_{t} }{(12 + t)!} \rho_n^{4t-3} n \epsilon^2 \Big\}.
$$
Now the $t$ dependence in the constant $c_t=[C^t (t!)^C]^{-1}$ (from now on $C$ is a generic positive constant) and using Stirling's approximation $t! \approx \sqrt{2\pi t} \, t^t \, e^{-t}$ this scales at dominant order as $[C^t (t^t)^C]^{-1}$. So we have at dominant order
$$
\textsf{bound}_t \approx  C C_{t} \exp\{ - C e^{\pm Ct - C t \ln t} e^{(4t-3)\ln(\rho_n)} e^{\ln n} \epsilon^2 \}.
$$
Now set the number of iterations to $t = o(\frac{\ln n}{\ln\ln n})$. We get $t\ln t = o(\ln n)$ so $\pm Ct - C t \ln t = o(\ln n)$ and
\begin{align}
\textsf{bound}_t \approx  C C_{t} \exp\{ - C e^{- o(\ln n)} e^{ o(\frac{\ln n}{\ln\ln n}) \ln(\rho_n)} e^{\ln n} \epsilon^2 \}.\label{worsen}
\end{align}
We set $\rho_n = \Theta\big( \frac{1}{(\ln n)^\alpha}\big) = \frac{C}{(\ln n)^\alpha}$. Then
$\ln\rho_n = \ln C - \alpha\ln\ln n$ and we get
$$
\textsf{bound}_t \approx  C C_{t} \exp\{ - C e^{- o(\ln n)} e^{ o(\frac{\ln n}{\ln\ln n}) (C - \alpha\ln\ln n)} e^{\ln n} \epsilon^2 \}.
$$
This leads to
\begin{align*}
\textsf{bound}_t & \approx  C C_{t} \exp\{ - C e^{- o(\ln n) + C o(\frac{\ln n}{\ln\ln n}) - \alpha o(\ln n)} e^{\ln n}
\epsilon^2 \}
\nonumber \\ &
\approx  C C_{t} \exp\{ - C e^{(\ln n) - (1+ \alpha) o(\ln n) + C o(\frac{\ln n}{\ln\ln n})}
\epsilon^2 \}
\nonumber \\ &
\approx  C C_{t} \exp\{ - C e^{(\ln n)[ 1 - (1+ \alpha) o(1)] + C o(\frac{1}{\ln\ln n})}
\epsilon^2 \}
\nonumber \\ &
\approx  C C_{t} \exp\{ - C n^{1 - o_\alpha(1)}
\epsilon^2 \}.
\end{align*}
One can check that the prefactor $C_t=[C^t (t!)^C]$ does not change the dominant order for $t = o(\frac{\ln n}{\ln\ln n})$. This shows that the bound vanishes as $n\to+\infty$ for $\lambda = w \rho_n^{-2}$ and $\rho_n =\Theta(\frac{1}{(\ln n)^\alpha})$ for any $\alpha\ge 0$. {As seen from \eqref{worsen} the bound worsen with decreasing $\rho_n$. So the result extends to $\rho_n=\Omega(\frac{1}{(\ln n)^\alpha})$.}

Note also that in the case of the rescaled bound of remark 1 below theorem~\ref{AMP-theorem}, the previous derivation is unchanged, up to the constant appearing in the $o_\alpha(1)$ that is changed some other $o_\alpha(1)$ (for $n$ big enough). Indeed, because $\rho_n =\Omega(\frac{1}{(\ln n)^\alpha})$ the $\rho_n^2$ or $\rho_n^4$ appearing in the rescaled bound can be absorbed in the $o_\alpha(1)$ of the previous derivation, for $n$ large enough.


TITLE: Given $x_1=1,x_2=2,x_{n+2}=3x_{n+1}-x_n\forall n\in\mathbb N$. Find $x_n$.
QUESTION [2 upvotes]: Given $x_1=1,x_2=2,x_{n+2}=3x_{n+1}-x_n\forall n\in\mathbb N$. Find $x_n$.

I tried to find ways to telescope, but failed. Please help. Thank you.

REPLY [0 votes]: The set of sequences of complex numbers (actually any field, but let's keep things simple) $(x_n)$ satisfying
$$
\begin{cases}
x_0=a\\
x_1=b\\
x_{n+2}=rx_{n+1}+sx_{n}
\end{cases}
$$
can be made into a vector space by defining addition componentwise and multiplication by scalars as multiplying each term by the scalar. Since a sequence is determined as soon as the $0$ and $1$ term are fixed, this vector space has dimension $2$.
Let's try finding two linearly independent sequences in it, by first looking at the simplest kind, that is, geometric progressions. So, when does the sequence $(t^n)$ belong to the vector space? It should satisfy
$$
t^{n+2}=rt^{n+1}+st^n
$$
for all $n$, in particular for $n=0$, that is,
$$
t^2-rt-s=0.
$$
Conversely, if $t$ satisfies this equation, the corresponding geometric progression belongs to the vector space.
If the polynomial $X^2-rX-s$ has distinct roots $\alpha$ and $\beta$, we want to show that the sequences $(\alpha^n)$ and $(\beta^n)$ are linearly independent. If
$$
p(\alpha^n)+q(\beta^n)=(0)
$$
where $(0)$ denotes the constant zero sequence, we have, in particular
$$
\begin{cases}
p+q=0\\
p\alpha+q\beta=0
\end{cases}
$$
and the determinant of the system is
$$
\det\begin{bmatrix}1 & 1\\\alpha&\beta\end{bmatrix}=\beta-\alpha\ne0,
$$
so the system has a unique solution, with $p=q=0$.
Therefore, for any sequence $(x_n)$ in the vector space there are coefficients $p$ and $q$ such that
$$
x_n=p\alpha^n+q\beta^n \qquad \text{for all $n\ge0$}
$$
and $p$ and $q$ can be uniquely determined by plugging in the given values for $x_0$ and $x_1$.
If the polynomial has only one (double) root $\alpha$, then we can see that the sequences $(\alpha^n)$ and $(n\alpha^n)$ are linearly independent: the linear system to look at is
$$
\begin{cases}
p=0\\
p\alpha+q\alpha=0
\end{cases}
$$
that surely is satisfied for $p=q=0$. Notice that $\alpha\ne0$, unless the recurrence is the trivial one $x_{n+2}=0$.
Of course this can be generalized to any linear recurrence equation.


text:
\section{Lower Bounds on \Stabname}

\label{sec:LowerBounds}

In this section we provide matching lower bounds for the previously studied first-order methods. These lower bounds show that our analyses are tight, up to absolute constant factors.

We note that it is possible to prove a general purpose lower bound on stability by appealing to sample complexity lower bounds for stochastic convex optimization \citep{nemirovsky1983problem}.

This approach in the smooth convex case was first studied in \citep{Chen:2018}; there, these lower bounds are sharp.
However, in the nonsmooth case they are very far from bounds in the previous section.
The idea is that for sufficiently small step size,
a first-order method must incur $\Omega(LT\eta/n)$ uniform stability.
\ifthenelse{\boolean{fullver}}{
\begin{obs} \label{obs:base_lb}
\input{gen_LB_FOM.tex}
\end{obs}
}{
Details of this lower bound can be found on Appendix \ref{app:gen_LB_FOM}.
}
This reasoning leads to an
$\Omega(LT\eta/n)$ lower bound on \stabname, that can be added to any other lower bound we can prove on specific algorithms that enjoy rates as of gradient descent.

Next we will prove finer lower bounds on the \UHS of specific algorithms.
For this, note that the objective functions we use are polyhedral, thus the subdifferential is a polytope at any point. Since the algorithm should work for
any oracle, we will let the subgradients provided to be extreme points, $\nabla f(x,z)\in\mbox{ext}(\partial f(x,z))$. Moreover, we can make adversarial choices of the chosen subgradient.

\subsection{Lower Bounds for Full Batch GD}

\begin{thm} \label{thm:LB_GD_basic}
Let $\X={\cal B}(0,1)$, ${\cal F}={\cal F}_{\X}^0(1)$ and $d\geq \min\{T,1/\eta^2\}$. For the full-batch gradient descent (Alg.~\ref{alg:batchGD}) with constant step size $\eta>0$, there exist $S\simeq S'$ such that the \UHS is lower bounded as
$\delta_{\A_{\sf GD}(S, S')}=\Omega(\min\{1,\eta\sqrt{T}+\eta T/n\}).$
\end{thm}

\ifthenelse{\boolean{fullver}}{
\input{proof_LB_GD_basic.tex}

}{
The proof of this result is deferred to Appendix \ref{app:LB_GD_basic}, due to space considerations.
}

\subsection{Lower Bounds for SGD Sampled with Replacement}

We use a similar construction as from the previous result to prove a sharp lower bound on the
\stabname for stochastic gradient descent where the sampling is with replacement.

\begin{thm} \label{thm:LB_rSGD_basic}
Let $\X={\cal B}(0,1)$, ${\cal F}={\cal F}_{\X}^0(1)$, and $d\geq \min\{T,1/\eta^2\}$. For the sampled with replacement stochastic gradient descent (Algorithm \ref{alg:repl_SGD}) with constant step size $\eta>0$, there exist $S\simeq S^{\prime}$ such that the \stabname satisfies
$\EE[\delta_{\A_{\sf rSGD}}(S,S^{\prime})]=
\Omega\Big(\min\Big\{1,\frac{T}{n}\Big\}\eta\sqrt T +\frac{\eta T}{n}\Big).$
\end{thm}

\begin{proof}
Let $D\triangleq\min\{T,1/\eta^2\}\leq d$, and $\nu>0$, $K\geq \sqrt D$. Consider ${\cal Z}=\{0,1\}$ and define
$$
f(x,z) =
\left\{
\begin{array}{ll}
\max\{0,x_1-\nu,\ldots,x_D-\nu\}           & \mbox{ if } z=0 \\
\langle r,x\rangle/K& \mbox{ if } z=1,
\end{array}
\right.
$$
where $r=(-1,\ldots,-1,0,\ldots,0)$ (i.e., supported on the first $D$ coordinates).
Let the random sequence of indices used by the algorithm: $(\bI_t)_{t\geq 0} \stackrel{i.i.d.}{\sim}\mbox{Unif}([n])$.
Let $S=(1,0,\ldots,0)$ and $S^{\prime}=(0,0,\ldots,0)$ be neighboring datasets, and denote by $(x^t)_t$ and $(y^t)_t$ the respective stochastic gradient descent trajectories on $S$ and $S^{\prime}$, initialized at $x^1=y^1=0$. It is easy to see that under $S^{\prime}$, we have $y^t=0$ for all $t\in[T]$. Now, suppose that $\nu<\eta/K$. Then, we only have $x^t=0$ for all $t\leq \tau$, where $\tau:=\inf\{t\geq 1:\,\bI_t=1 \}$. After time $\tau$, $x^{\tau+1}=-\eta r/K$, and consequently
$x^{\tau+1+j}=-\frac{\eta \bk(\tau+j)}{K} r - \eta \sum_{s=1}^{j-\bk(\tau+j)+1} e_{s},$ for all $j \in [D+\mathbf{k}(\tau+j)-1]$, where $\mathbf{k}(t)\triangleq |\{s\in[t]:\bI_s=1\}|$. Note that conditioned on any fixed value for $\tau,$ ~$\bk(\tau+j)\leq j+1$.

Let $\delta_T=\|x^T-y^T\|=\|x^T\|$. Hence, we have $\delta_T\geq\eta\|\sum_{s=1}^{T-\tau-\mathbf{k}(T-1)}e_s\|-\eta \mathbf{k}(T-1)\sqrt{D}/K\geq \eta\sqrt{T-\mathbf{k}(T-1)-\tau}-\eta T \sqrt D /K$.
Let $\mathbf{k}=\mathbf{k}(T-1)$ from now on.
Note that conditioned on any value for $\tau,$ ~$\bk-1$ is a binomial random variable taking values in $\{0, \ldots, T-1-\tau\}$. Hence, conditioned on $\tau=t$, by the binomial tail, we always have  $\PP[\mathbf{k}>T/2~|~\tau=t]\leq\exp(-T/4)$ for all $t\in [T]$ (in particular, this conditional probability is zero when $t\geq T/2$). Also, note that the same upper bound is valid without conditioning on $\tau$.

Hence, by the law of total expectation, we have
\begin{eqnarray*}
\EE[\delta_T]
&=& \EE[\delta_T| ~\bk\leq T/2]\cdot\PP[\bk\leq T/2]+\EE[\delta_T | ~\bk> T/2]\cdot\PP[\bk> T/2]

\geq c\,\EE[\delta_T | ~\bk\leq T/2]

\end{eqnarray*}
where $c=(1-\exp(-T/4))=\Omega(1)$. Hence,
\begin{eqnarray*}
\EE[\delta_T]&\geq& c \sum_{t=1}^{T/2} \EE[\delta_T|\tau=t,~ \bk\leq T/2]\,\PP[\tau=t | ~\bk\leq T/2]\\

&\geq& c^2\sum_{t=1}^{T/2} \EE[\delta_T|\tau=t,~ \bk\leq T/2]\,\PP[\tau=t]\\
&\geq& c^2\frac{\eta}{n}\sum_{t=1}^{T/2} \sqrt{T-T/2-t}\big(1-\frac1n\big)^{t-1}-c^2\eta \sqrt D T/K.
\end{eqnarray*}
We choose $K$ sufficiently large such that
$\eta \sqrt D T/K=o(\eta\min\{T^{3/2}/n,\sqrt{T}\})$.
\ifthenelse{\boolean{fullver}}{
If $T\leq n$ then
$$ \EE[\delta_T] \geq c^2\frac{\eta}{n} \sum_{t=1}^{T/2} \sqrt{t} \big(1-\frac1n\big)^{n-2}-c^2\frac{\eta \sqrt D T}{K}
\geq c^2\frac{\eta e^{-1}}{n}\sum_{t=1}^{T/2} \sqrt{t}-o(\frac{\eta T^{3/2}}{n})
= \Omega\Big( \frac{\eta T^{3/2}}{n} \Big)$$

and if $T>n$ then
$$ \EE[\delta_T]
\geq c^2\frac{\eta}{n} \sum_{t=1}^{n/4} \sqrt{T/2-n/4} \, e^{-1} -o(\eta\sqrt{T})
= \Omega( \eta\sqrt{T})$$

}{
Hence, we have
$$
\EE[\delta_T]\geq
\left\{
\begin{array}{ll}
\frac{c^2\eta}{n} \sum_{t=1}^{T/2} \sqrt{t} \big(1-\frac1n\big)^{n-2}-\frac{c^2\eta \sqrt D T}{K}
\geq \frac{c^2\eta e^{-1}}{n}\sum_{t=1}^{T/2} \sqrt{t}-o(\frac{\eta T^{3/2}}{n})
= \Omega\Big( \frac{\eta T^{3/2}}{n} \Big) & \mbox{ if } T\leq n\\
\frac{c^2\eta}{n} \sum_{t=1}^{n/4} \sqrt{T/2-n/4} \, e^{-1} -o(\eta\sqrt{T})
= \Omega( \eta\sqrt{T}) &\mbox{ if }
T>n.
\end{array}
\right.
$$
}
This gives a lower bound on $\EE[\delta_T]$. Proving that $\overline{x}^T$ satisfies the same lower bound is analogous to the proof in Theorem~\ref{thm:LB_GD_basic}. Finally, $\Omega(\eta T/n)$ can be added to the lower bound by \ifthenelse{\boolean{fullver}}{Observation \ref{obs:base_lb}}{Appendix \ref{app:gen_LB_FOM}}.
\end{proof}

\subsection{Lower Bounds for the Fixed Permutation Stochastic Gradient Descent}

Finally, we study fixed permutation SGD. \ifthenelse{\boolean{fullver}}{}{The proof of this result is deferred to Appendix \ref{app:LB_perm_SGD_basic}.}

\begin{thm} \label{thm:LB_perm_SGD_basic}
Let $\X={\cal B}(0,1)$, ${\cal F}={\cal F}_{\X}^0(1)$ and $d\geq \min\{T,1/\eta^2\}$. For the fixed permutation stochastic gradient descent (Algorithm \ref{alg:perm_SGD}) with constant step size $\eta>0$, there exist $S\simeq S^{\prime}$ such that the \stabname is lower bounded by
$\EE[\delta_{\A_{\sf PerSGD}}(S,S^{\prime})]=
\Omega\Big(\min\Big\{1,\frac{T}{n}\Big\}\eta\sqrt T +\frac{\eta T}{n}\Big).$
\end{thm}

\ifthenelse{\boolean{fullver}}{
\input{proof_LB_perm_SGD_basic.tex}
}{}


TITLE: Decomposition group and inertia group
QUESTION [9 upvotes]: Let $L/K$ be a Galois extension with Galois group $G$. Let $O_K$ and $O_L$ be the ring of algebraic integers of $K$ and $L$ respectively. Let $P\subseteq O_K$ be a prime. Let $Q\subseteq O_L$ be a prime lying over $P$ with ramification index e$(Q|P)=e$ and inertia degree f$(Q|P)=f$.

Let $D(Q|P)$ be the decomposition group of $Q$. In other words
  $$D(Q|P)=\lbrace\sigma\in G\text{ }|\text{ }\sigma(Q)=Q\rbrace$$
   Let $L_D$ be the decomposition field (the fixed field of $D(Q|P)$). Define $Q_D=Q\cap L_D$.
The inertia group is $$E(Q|P)=\lbrace \sigma\in D(Q|P):\sigma(x)\equiv x\text{ mod } Q\text{ for all } x\in O_L\rbrace$$
  Let $L_E$ be the inertia field (the fixed field of $E(Q|P)$). Define $Q_E=Q\cap L_E$.

From algebraic number theory we know the following

e$(Q_D|P)=1$ and f$(Q_D|P)=1$
e$(Q_E|P)=1$ and f$(Q_E|P)=f$

I want to find a prime $Q_D'$ of $L_D$ lying over $P$ such that e$(Q_D'|P)\neq1$ and f$(Q_D'|P)\neq1$.
Similarly, is there any prime $Q_E'$ of $L_E$ lying over $P$ such that  e$(Q_E'|P)\neq1$ and f$(Q_E'|P)\neq f$ ?
What we know for sure is that to find such $Q_D'$ (resp. $Q_E'$), we must choose $P$ and $Q$ such that $D(Q|P)$ (resp. $E(Q|P)$) is not normal in $G$. (Corollary 2 of Theorem 28, Number fields, Daniel A Marcus)

REPLY [4 votes]: We are looking for a collection of ramification and splitting behaviours over a single prime $P$, all of which are possible, but rarely combine in a single easily-calculated example. I have produced a case where each of the things you ask for does indeed occur, in order to illustrate the general case. But I should point out that it is easy to produce individual lower-degree examples demonstrating separately each of the requirements you have placed on the primes above $P$.
Recall the well-known formula describing the splitting of a prime $P$ in an extension $L/K$ in terms of its ramification and residue field extension indices:
\begin{equation*}
\Sigma_{Q\mid P}\ e_{Q}f_{Q} = [L:K].
\end{equation*}
As you have pointed out, when the extension is Galois all of the $e_Q$ are equal to some fixed $e$, and all of the $f_Q$ are equal to a fixed value $f$; so this reduces to
\begin{equation}
efg = [L:K].
\end{equation}
where we have used the standard notation $g$ for the number of primes of $L$ above the prime $P$ of $K$ in a Galois extension.
We would like to see different types of behaviour at each of the levels $L$, $L_D$ and $L_E$ for some prime $Q$ of $L$ above $P$, which implies that we need $e\geq2$ and $f\geq2$. Moreover in order to have any chance of seeing different outcomes above the same prime $P$, we need that $P$ split into at least 2 distinct primes at the level $L_D$, otherwise $L_D=K$. Hence we also need $g\geq2$. So the degree of the extension $L/K$ needs to be at least 8.
Finally, as you also point out, we need that the Galois group Gal($L/K$) contain non-normal subgroups in order that any prime have a chance that the fixed field of its decomposition and/or inertia groups be non-Galois; otherwise we are just in a lower-degree version of the above formula. It is not sufficient, by the way, that the extension simply be non-Abelian, since for example the quaternion group Q8 is non-Abelian but has no non-trivial non-normal subgroups.
All of this forces the extension to have degree at least 16 (the non-normal subgroups of the dihedral group D4 of order 8 do not allow enough varied behaviour). We also would like an extension whose Galois group is furnished with lots of non-normal subgroups. So the easiest place to start would be something with Galois group S4. In order to simplify things let us assume that $K=\mathbb{Q}$, and take some "general" quartic extension, the simplest interesting one of which might be the splitting field $L$ of the polynomial $q(x) = x^4+x+1$.
I used MAGMA for the following calculations. This extension $L/\mathbb{Q}$ is ramified only above $P=229$, splitting into six primes with residue field extension (="inertia") degree $f=2$ and ramification degree $e=2$. Choosing any of these primes $Q$ say we have an inertia group $E(Q\mid P)$ which is cyclic of order 2 ($\cong C_2$) and a decomposition group $D(Q\mid P)$ which is isomorphic to $C_2^2$.
We then calculate that there is always a prime $Q_D'$ of $L_D$ over $P$ with $e_{Q_D'}=f_{Q_D'}=2$.
Similarly there is always a prime $Q_E'$ of $L_E$ over $P$ with $e_{Q_E'}=2$ and $f_{Q_E'}=1$.


TITLE: Time evolution of scalar field
QUESTION [1 upvotes]: Consider the quantized real scalar field acting on the vacuum state $\vert 0 \rangle $. We can interpret the state $\phi(\textbf{x})\vert 0 \rangle $ (defined in the Schrodinger picture at $t=0$) as a particle created at $(t=0,\textbf{x})$.
Peskin and Schroeder say that the state $\phi(x)\vert 0 \rangle $ is particle prepared at spacetime point $x$. I see how this works in the Heisenberg picture. But I want to work in the Schrodinger picture to convince myself of whats going on. So I time evolve the state $\phi(\textbf{x})\vert 0 \rangle $ by acting with the time evolution operator $U=e^{-iHt}$. However this time evolution gives an incorrect expression, in particular instead of having $e^{iEt}$ which is what I need, I have a $e^{-iEt}$ term which doesn't coincide with the Heisenberg picture result (or the result you get from just solving the Klein Gordon equation).
What's the problem?
Edit: A more in depth explanation;
We have $\phi(\textbf{x})\vert 0 \rangle = \displaystyle\int\frac{d^3p}{(2\pi)^3}\frac{1}{\sqrt{2E_\textbf{p}}}e^{-i\textbf{p}.\textbf{x}}a^\dagger_\textbf{p} \vert 0 \rangle$. In the Heisenberg picture we can show that at time $t$ we have
$\phi(x)\vert 0 \rangle = e^{iHt}\phi(\textbf{x})e^{-iHt}\vert 0 \rangle$.
Expanding $e^{-iHt}$ as a Taylor series and since the state $\vert 0 \rangle$ is such that $H\vert 0 \rangle=0$ we have $e^{-iHt}\vert 0 \rangle=\vert 0 \rangle$. This gives us
$\phi(x)\vert 0 \rangle = e^{iHt}\phi(\textbf{x})\vert 0 \rangle$. Using the commutation relations between the ladder operators and $H$ we obtain the correct result.
The problem is that if I take the state $\phi(\textbf{x})\vert 0 \rangle$ and time evolve with the time evolution operator $U=e^{-iHt}$ we obtain $\phi(x)\vert 0 \rangle = e^{-iHt}\phi(\textbf{x})\vert 0 \rangle$. Comparing our expressions we have $e^{-iHt}=e^{iHt}$ implying $t=0$ or $H=0$, the former coinciding with the fact that the pictures agree at $t=0$.
Why am I not obtaining the same result in the Schrodinger picture?

REPLY [1 votes]: This problem arises because you cannot compare states in the Heisenberg picture and states in the Schrödinger picture (except for $t=0$) because they are physically different objects.
The only thing that coincides and can be compared are matrix elements or expectation values. If you have a look at expectation values, you will see (quite trivially) that there is no difference.


TITLE: Preimages of prime ideals when only one of the rings is commutative
QUESTION [1 upvotes]: Given a ring homomorphism between noncommutative rings, the preimage of a prime ideal is not necessarily prime. On the other hand, the preimage of a prime ideal is always prime if both rings are commutative, which is why the usual prime spectrum $\operatorname{Spec}$ is functorial on commutative rings.
I am just curious what happens if only one of the rings involved is commutative. Suppose we have a pair of rings $R$ and $K$, where $K$ is commutative, and $R$ is not.
If we have a ring homomorphism $f: R \to K$, is the preimage of every prime ideal in $K$ prime?
Likewise, if we have a ring homomorphism $g: K \to R$, Is the preimage of every prime ideal in $R$ prime?

REPLY [3 votes]: An ideal $P\subset R$ is prime iff $R/P$ is a prime ring.  So modding out the prime ideal and its preimage, you can assume your homomorphism is injective and the question is whether a subring of a prime ring is prime, when you know one of the rings is commutative.
In the case of $f:R\to K$, a commutative prime ring is just an integral domain, and a subring of an integral domain is an integral domain.  So the answer is yes, the preimage of a prime ideal is prime.  Another way to think about this case is that the inverse image of a completely prime ideal is always completely prime, where $P$ is completely prime if $ab\in P$ implies $a\in P$ or $b\in P$ (the proof is easy).  Since prime ideals in commutative rings are completely prime, the inverse image of a prime ideal in a commutative ring is always prime (in fact, completely prime).
In the case of $g:K\to R$, the answer is no in general.  For instance, if $A$ is an integral domain, then $R=M_2(A)$ is a prime ring, but the subring $A\times A$ of diagonal matrices is commutative and not prime.


TITLE: Baby Rudin vs. Abbott
QUESTION [29 upvotes]: I am considering Stephen Abbott's Understanding Analysis and Walter Rudin's Principles of Mathematical Analysis. I am looking for a comparison between the two that addresses both of the following matters,

Is one of the two substantially more mathematically rigorous than the other?
Does one include substantially more challenging problems?
Which provides a better introduction to Real Analysis?

Follow-up question:

Would someone who has worked through Abbott's book be at a disadvantage compared to someone who has completed Rudin's text?

REPLY [25 votes]: You think you are asking just a simple question but you are adding kerosene to the flame of  Pro-Rudins vs Anti-Rudins :)
Any ways I have read both books and here are my feelings
(1) Rudin definitely has really good, challenging problems
(2) Rudin goes directly to the point
(3) Rudin gives you the opportunity to think on your feet and fill the gaps
That said coming from a normal math background, Rudin was a tough read
for me. Abbott's book was quite a good supplement for some chapters.
But for me Pugh's Real Analysis and Apostol Analysis was the best supplement.
My strategy was to read and re-read Rudin and give some critical time $t_{c}$
to see if I understand a concept. If that doesn't happen $t>t_{c}$, I refered to
the other books. Towards the end of the course, I came to know Terry Tao's book
and I have to say it was a pleasure to read. Good luck, you can always pick one
book and refer to the others when you need to. You need to have a general idea
of where you are going but you don't have to follow every route


TITLE: Inverting lower triangular matrix in time $n^2$
QUESTION [32 upvotes]: I have a lower $n\times n$ triangular matrix called $A$ and I want to get $A^{-1}$ solved in $O(n^2)$. How can I do it?
I tried using a method called "forward substitution", but the inversion is solved in $O(n^3)$ for full $n\times n$ matrix.

REPLY [90 votes]: No such method is known at present.
If one could invert lower triangular $n \times n$ matrices in time $O(n^2)$
then one could multiply $N \times N$ matrices in time $O(N^2)$.
Indeed let $n=3N$ and apply the putative inversion algorithm to
the block matrix
$$
\left(
  \begin{array}{ccc} I & 0 & 0 \cr B & I & 0 \cr 0 & A & I \end{array}
\right)
$$
for any $N\times N$ matrices $A,B$: the inverse is
$$
\left(
   \begin{array}{rrr} I & 0 & 0 \cr -B & I & 0 \cr AB & \!\!\! -A & I \end{array}
\right) \, ,
$$
so you could read $AB$ off the bottom left block.
It is still an open problem whether general matrix multiplication
can be done in time $O(N^2)$, or even $O(N^{2+o(1)})$.  In particular
it follows that no method is known to do what you are asking.
In fact it is known that conversely an algorithm that takes
$O(N^2)$ or $O(N^{2+o(1)})$ time to multiply $N \times N$ matrices
would let us also invert $n \times n$ matrices in time
$O(n^2)$ or $O(n^{2+o(1)})$ respectively
(with a different $O$-constant, and not limited to triangular matrices).
So your question is in fact equivalent to the open question about
fast matrix multiplication.  See for instance page 3 of
these
lecture notes by Garth Isaak, which also shows the block-diagonal trick
(in the upper- instead of lower-triangular setting).
POSTSCRIPT Strictly speaking, the reduction from
$O(N^c)$ matrix multiplication to $O(n^c)$ inversion of
triangular matrices means only that either we don't know how to attain
$c=2$ or $c=2+o(1)$ in the latter problem, or such an algorithm is known
but somehow nobody has noticed that this solves the former problem.
But the second possibility seem most unlikely, because fast matrix
multiplication is such a celebrated problem, and its reduction to
triangular-matrix inversion is quite well known.


TITLE: Help with evaluating this integral
QUESTION [2 upvotes]: I'm learning integrals and I'm having trouble with evaluating this one:
$$
 \int_0^{8 \pi} \sqrt{ 4 - 4 \cos(t)} \mathrm{d} t
$$
The end result is  $32  \sqrt{2}$.
I tried this by changing the form of the integral to
$\sqrt{8 \cdot \sin^2(t/2)}$
but I can't get the end result, which I specified above.
Any help is greatly appreciated, especially if explained in steps.

REPLY [4 votes]: So first rewrite your integral as you did as
\[ \int_0^{8\pi} \sqrt{4 - 4\cos t} \, dt = \int_0^{8\pi} \sqrt{8\sin^2 \frac t2}\, dt \]
Now we get rid of the $\frac 12$ letting $s = \frac t2$ and obtain
\[ \int_0^{8\pi} \sqrt{8\sin^2 \frac t2}\, dt = 2\int_0^{4\pi} \sqrt{8\sin^2 s }\, ds \]
Now $\sqrt{\sin^2 s} = |\sin s|$ and $\sqrt{8} = 2\sqrt 2$. More over the function $s \mapsto |\sin s|$ is periodic with period $\pi$, so the integral over $[0,4\pi]$ equals four times the integral over $[0,\pi]$. We obtain
\[ 2\int_0^{4\pi} \sqrt{8\sin^2 s }\, ds  = 4\sqrt 2 \int_0^{4\pi}|\sin s|\, ds = 16\sqrt 2 \int_0^\pi \sin s \, ds \]
where in the last step we also used $\sin s \ge 0$ for $s \in [0,\pi]$. Now the last integral is 2, so altogether we obtained
\[ \int_0^{8\pi} \sqrt{4 - 4\cos t} \, dt = 32\sqrt 2.\]