text:
\section{Main results}
\label{Main results and discussion}

We now present our main results: an achievable minimax MSE for the $\pdf$ estimation method in Algorithm \ref{Algorithm: Density Estimation}, and minimax lower bounds on estimation of the skill parameters $\alpha_i, i \in [n]$ from $Z$ (i.e., Step 1 of Algorithm \ref{Algorithm: Density Estimation}) for {\em any} method. This collectively establishes the near-optimality of our proposed method as $\eta \to \infty$, i.e., as the density becomes smooth ($\mathcal{C}^{\infty}$). To this end, we first establish minimax rates for skill parameter estimation, and then derive minimax rates for PDF estimation.

\noindent{\bf Tight minimax bounds on skill parameter estimation.} To obtain tight $\pdf$ estimation, it is
essential that we have tight skill parameter estimation. Hence, we show that the parameter estimation step performed in \eqref{Eq: Empirical Stat Dist} has minimax optimal rate. Specifically, we define the ``canonically scaled'' skill parameters $\pi \in \S_n$ with $i$th entry given by:
\begin{equation}
\label{Eq: Canonically scaled merit parameters}
\forall i \in [n], \enspace \pi(i) \triangleq \frac{\alpha_i}{\alpha_1 + \cdots + \alpha_n} \, .
\end{equation}
Building upon \cite[Theorem 3.1]{Chenetal2019}, the ensuing theorem portrays that the \emph{minimax relative $\ell^{\infty}$-risk} of
estimating \eqref{Eq: Canonically scaled merit parameters} based on $Z$ is
$\tilde{\Theta}(n^{-1/2})$ (see \tabref{Table: Technical Contributions}). For simplicity,
we will assume throughout this subsection on skill parameter estimation that $\delta$, $p$, and $k$ are $\Theta(1)$.

\begin{theorem}[Minimax Relative $\ell^{\infty}$-Risk]
\label{Thm: Minimax Relative l^infty-Risk}
For sufficiently large constants $c_{14},c_{15} > 0$ (which depend on $\delta$, $p$, and $k$), and for all sufficiently large $n \in \N$:
$$ \frac{c_{14}}{\log(n)\sqrt{n}} \leq \inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right]}} \leq \sup_{\pdf \in \pdfs}{\E\!\left[\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right]} \leq c_{15} \sqrt{\frac{\log(n)}{n}} $$
where the infimum is over all estimators $\hat{\pi} \in \S_n$ of $\pi$ based on $Z$, and $\hat{\pi}_* \in \S_n$ is defined in \eqref{Eq: Empirical Stat Dist}.
\end{theorem}
The proof of \thmref{Thm: Minimax Relative l^infty-Risk} can be found in Appendix \ref{Proof of Thm Minimax Relative l^infty-Risk}. \thmref{Thm: Minimax Relative l^infty-Risk} states that the rank centrality estimator $\hat{\pi}_*$ achieves an extremal Bayes relative $\ell^{\infty}$-risk of $\tilde{O}(n^{-1/2})$, and no other estimator can achieve a risk that decays faster than $\tilde{\Omega}(n^{-1/2})$. In the same vein, we show that the \emph{minimax (relative) $\ell^{1}$-risk} (or total variation distance risk) of estimating
\eqref{Eq: Canonically scaled merit parameters} based on $Z$ is also $\tilde{\Theta}(n^{-1/2})$ (see \tabref{Table: Technical Contributions}).
\begin{theorem}[Minimax $\ell^1$-Risk]
\label{Thm: Minimax l^1-Risk}
For sufficiently large constants $c_{17},c_{18} > 0$ (which depend on $\delta$, $p$, and $k$), and for all sufficiently large $n \in \N$:
$$ \frac{c_{17}}{\log(n)\sqrt{n}} \leq \inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E\!\left[\left\|\hat{\pi} - \pi\right\|_{1}\right]}} \leq \sup_{\pdf \in \pdfs}{\E\!\left[\left\|\hat{\pi}_* - \pi\right\|_{1}\right]} \leq \frac{c_{18}}{\sqrt{n}} \, . $$
\end{theorem}

\thmref{Thm: Minimax l^1-Risk} is established in Appendix \ref{Proof of Thm Minimax l^1-Risk}. The upper bounds in Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk} follow from \cite[Theorems 3.1 and 5.2]{Chenetal2019} after some calculations, but the \emph{lower bounds are novel contributions}. We prove them by first lower bounding the minimax risks in terms of Bayes risks in order to circumvent an involved analysis of the infinite-dimensional parameter space $\pdfs$. In particular, we \emph{set $\pdf \in \pdfs$ to be the uniform PDF} over $[\delta,1]$, denoted $\unif([\delta,1]) \in \pdfs$. We then lower bound the Bayes risks using a recent generalization of \emph{Fano's method} \cite{Khasminskii1979,IbragimovKhasminskii1977} (cf. \cite{Yu1997,Tsybakov2009}), which was specifically
developed to produce such lower bounds in the setting where the parameter space is a continuum, e.g., $[\delta,1]$,
instead of a finite set \cite{Zhang2006,DuchiWainwright2013,ChenGuntuboyinaZhang2016,XuRaginsky2017}; see Appendices \ref{Generalized Fano's method} and \ref{Auxiliary lemmata 2}.

The principal analytical difficulty in executing the generalized Fano's method is in deriving a tight upper bound on the
\emph{mutual information} between $\pi$ and $Z$, denoted $I(\pi;Z)$ (see \eqref{Eq: MI Def} in Appendix \ref{App: Covering numbers} for a formal definition),
where the probability law of $\pi$ is defined using $\pdf = \unif([\delta,1])$. The ensuing proposition presents
our upper bound on $I(\pi,Z)$.

\begin{proposition}[Covering Number Bound on Mutual Information]
\label{Prop: Upper Bound on MI}
For all $n \geq 2$, we have:
$$ I(\pi;Z) \leq \frac{1}{2} n \log(n) + \frac{(1-\delta)^2}{8 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) k p n \, . $$
\end{proposition}

\propref{Prop: Upper Bound on MI} is proved in Appendix \ref{App: Covering numbers}. We note that although standard information inequalities, e.g. \cite[Equation (44)]{ChenGuntuboyinaZhang2016}, typically suffice to obtain minimax rates for various estimation problems, they only produce a sub-optimal estimate $I(\pi;Z) = O(n^2)$ in our problem, as explained at the end of Appendix \ref{App: Covering numbers}, cf. \eqref{Eq: Last Quadratic Upper Bound}. So, to derive the sharper estimate $I(\pi;Z) = O(n \log(n))$
in \propref{Prop: Upper Bound on MI}, we execute a careful covering number argument that is inspired by the
techniques of \cite{YangBarron1999} (also see the distillation in \cite[Lemma 16.1]{Wu2019}).

We make two further remarks. Firstly, it is worth juxtaposing our results with \cite[Theorem 5.2]{Chenetal2019} and \cite[Theorems 2 and 3]{NegahbanOhShah2017}, which state that the minimax relative $\ell^2$-risk of estimating $\pi$ is $\Theta(n^{-1/2})$. This result holds under a worst-case merit parameter value model as opposed to the worst-case prior distribution model of this paper. Secondly, both Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk} hold verbatim if $\pdfs$ is replaced by any set of probability measures with support in $[\delta,1]$ that contains $\unif([\delta,1])$.

\noindent{\bf Tight minimax bound on skill PDF $\pdf$ estimation.} We now state our main result concerning the estimation error for $\pdf$. In particular, we
argue that the MSE risk of our estimation algorithm (see \eqref{Eq: Robust PR Estimator}) scales as $\tilde{O}(n^{-\eta/(\eta+1)})$ for any $\pdf \in \pdfs$.

\begin{theorem}[MSE Upper Bound]
\label{Thm: MSE Upper Bound}
Fix any sufficiently large constants $c_2,c_3 > 0$ and suppose that $p \geq c_2 \log(n)/(\delta^5 n)$, $b \geq c_3 \sqrt{\log(n)/n}$, $\epsilon \geq 5\log(n)/(bn)$, and $\lim_{n \rightarrow \infty}{\delta^{-1} (n p k)^{-1/2} \log(n)^{1/2}} = 0$. Then, for any $L_2$-Lipschitz continuous kernel $K:[-1,1] \rightarrow \R$ of order $\lceil \eta \rceil - 1$, there exists a sufficiently large constant $c_{12} > 0$ (that depends on $\gamma$, $\eta$, $B$, $L_1$, $L_2$, and $K$) such that for all sufficiently large $n \in \N$:
$$ R_{\mathsf{MSE}}(n) \leq \sup_{\pdf \in \pdfs} \E\!\left[\int_{\R}{\left(\ests(x) - \pdf(x)\right)^{ 2}\diff{x}}\right] \leq c_{12} \max\!\left\{ \left(\frac{1}{\delta^2 p k}\right)^{\!\frac{\eta}{\eta + 1}},1\right\} \! \left(\frac{\log(n)}{n}\right)^{\!\frac{\eta}{\eta + 1}} . $$
\end{theorem}

\thmref{Thm: MSE Upper Bound} is established in Appendix \ref{Proof of MSE Upper Bound}. We next make several pertinent remarks. Firstly, the condition $p \geq c_2 \log(n)/(\delta^5 n)$ is precisely the critical scaling that ensures that $\G(n,p)$
is connected almost surely, cf. \cite[Theorem 8.11]{BlumHopcroftKannan2020}, \cite[Section 7.1]{Bollobas2001}.
This is essential to estimate $\alpha_1,\dots,\alpha_n$ in Step 1 of Algorithm \ref{Algorithm: Density Estimation},
since we cannot reasonably compare the skill levels of disconnected players. Secondly, while $\ests$ can be negative,
the non-negative truncated estimator $\estsp(x) = \max\{\ests(x),0\}$ achieves smaller MSE risk than $\ests$, cf. \cite[p.10]{Tsybakov2009}. So it is easy to construct good non-negative estimators. Thirdly, there exists a constant $c_{13} > 0$ (depending on $\eta,L_1$) such that for all sufficiently large $n \in \N$, the following minimax lower bound holds, cf. \cite[Theorem 6]{Wasserman2019}, \cite[Exercise 2.10]{Tsybakov2009}:
\begin{equation}
\label{Eq: Density Estimation Minimax Lower Bound}
R_{\mathsf{MSE}}(n) \geq \inf_{\hat{P}_{\alpha^n}(\cdot)}\,{ \sup_{\pdf \in \pdfs}{ \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}(x) - \pdf(x) \right)^2 \diff{x}} \right] } } \geq c_{13} \left(\frac{1}{n}\right)^{\frac{2\eta}{2\eta + 1}}
\end{equation}
where the infimum is over all estimators $\hat{P}_{\alpha^n} : \R \rightarrow \R$ of $P_{\alpha}$ based on
$\alpha_1,\dots,\alpha_n$, and the first inequality holds because the infimum in \eqref{Eq: Minimax MSE Formulation}
is over a subset of the class of estimators used in the infimum in \eqref{Eq: Density Estimation Minimax Lower Bound};
indeed, given $\alpha_1,\dots,\alpha_n$, one can simulate $Z$ via \eqref{Eq: BT model} and estimate $P_{\alpha}$
from $Z$. Thus, when $\eta = 1$, \thmref{Thm: MSE Upper Bound} and \eqref{Eq: Density Estimation Minimax Lower Bound}
show that $R_{\mathsf{MSE}}(n) = \tilde{O}(n^{-1/2})$ and $R_{\mathsf{MSE}}(n) = \Omega(n^{-2/3})$. Likewise, when ($\eta \rightarrow \infty$ and) $P_{\alpha}$ is smooth, i.e., \emph{infinitely differentiable} with all derivatives bounded by $L_1$, \thmref{Thm: MSE Upper Bound} holds for all
$\eta > 0$, and an $\Omega(n^{-1})$ lower bound analogous to \eqref{Eq: Density Estimation Minimax Lower Bound} holds \cite{IbragimovKhasminskii1982}. Letting $\varepsilon = (\eta + 1)^{-1}$, these results yield the first row of \tabref{Table: Technical Contributions}. Lastly,
we note that similar analyses to \thmref{Thm: MSE Upper Bound} can be carried out for, e.g., \emph{Nikol'ski}
and \emph{Sobolev classes} of PDFs, cf. \cite[Section 1.2.3]{Tsybakov2009}.

We emphasize that the key technical
step in the proof of \thmref{Thm: MSE Upper Bound} is the ensuing intermediate result.

\begin{proposition}[MSE Decomposition]
\label{Prop: MSE Decomposition}
Fix any sufficiently large constants $c_2,c_3,c_8,c_9 > 0$ and suppose that $p \geq c_2 \log(n)/(\delta^5 n)$, $b \geq c_3 \sqrt{\log(n)/n}$, $\epsilon \geq 5\log(n)/(bn)$, and $\lim_{n \rightarrow \infty} \delta^{-1} \allowbreak (n p k)^{-1/2} \log(n)^{1/2} = 0$. Then, for any $\pdf \in \pdfs$, any $L_2$-Lipschitz continuous kernel $K:[-1,1] \rightarrow \R$, any bandwidth $h \in (0,1]$ with $h = \Omega\big(\!\max\{1/(\delta \sqrt{p k}),1\} \sqrt{\log(n)/n}\big)$, and any sufficiently large $n \in \N$:
$$ \E\!\left[\int_{\R}{\!\!\left(\!\ests(x) -\pdf(x)\!\right)^{\! 2}\!\!\diff{x}}\right] \!\leq 2 \E\!\left[\int_{\R}{\!\!\left(\!\hat{P}_{\alpha^n}^*(x) - \pdf(x)\!\right)^{\! 2}\!\!\diff{x}}\right] + \frac{c_8 B^2 L_2^2}{h^2} \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] + \frac{c_9 L_2^2}{n^5 h^4} $$
where $\hat{P}_{\alpha^n}^*:\R \rightarrow \R$ denotes the classical PR kernel density estimator of $P_{\alpha}$ based on the true samples $\alpha_1,\dots,\alpha_n$ (if they were made available by an oracle) \cite{Rosenblatt1956,Parzen1962}:
\begin{equation}
\label{Eq: True PR estimator}
\forall x \in \R, \enspace \hat{P}_{\alpha^n}^*(x) \triangleq \frac{1}{n h} \sum_{i = 1}^{n}{K\!\left(\frac{\alpha_i - x}{h}\right)} \, .
\end{equation}
\end{proposition}

The proof of \propref{Prop: MSE Decomposition} can be found in Appendix \ref{App: MSE decomposition}. This result decomposes the MSE between $\ests$ (with general $h$) and $\pdf$ into two dominant terms: the MSE of estimating $\pdf$
using \eqref{Eq: True PR estimator}, which can be analyzed using a standard bias-variance tradeoff
(see \lemref{Lemma: Bias-Variance Tradeoff} in Appendix \ref{Proof of MSE Upper Bound} \cite{Tsybakov2009,Wasserman2019}),
and the squared $\ell^{\infty}$-risk of estimating $\alpha_1,\dots,\alpha_n$ using \eqref{Eq: Estimates of merit parameters}.
To analyze the second term, we use a relative $\ell^{\infty}$-norm bound from \cite[Theorem 3.1]{Chenetal2019}
(see \lemref{Lemma: Relative ell^infty-Loss Bound} in Appendix \ref{App: MSE decomposition}); the same bound was also used to obtain the upper bound in \thmref{Thm: Minimax Relative l^infty-Risk}.


TITLE: Limit point of A if and only if there exists a sequence converging to it
QUESTION [3 upvotes]: I have the following definition of a limit point:
$ x \in \mathbb{R} $ is a limit point of $A \subseteq \mathbb{R}$ iff $\forall \epsilon > 0 , \exists a \in A : 0 < |a - x| < \epsilon$
I want to prove that $x$ is a limit point of A if and only if there exists a sequence in A whose limit is $x$ and none of the terms are equal to $x$.
I can prove it one way assuming the existence of a sequence but I'm having some trouble proving the existence of the required sequence by supposing that $x$ is a limit point.
How do I construct a sequence from a single $a$ ?

REPLY [4 votes]: Let $\varepsilon = \frac1n$where $n\in \mathbb{N}$. As $x$ is a limit point, for every $n\in \mathbb{N}$ there exist an $a_n \in A-\{x\}$ such that $|a_n-x|<\varepsilon$. And this sequence $a_n$  converges to $x$.


text:
\begin{document}

\title{Group actions and Helly's theorem}
\author{Benson Farb\thanks{Supported in part by the NSF.  The results of
this paper were first presented in May 2000 at MSRI.}}

\maketitle

\begin{abstract}
We describe a connection between the combinatorics of generators for
certain groups and the combinatorics of Helly's 1913 theorem on convex
sets.  We use this connection to prove fixed point theorems for actions
of these groups on nonpositively curved metric spaces.  These results are encoded in a
property that we introduce called ``property $\FA_r$'',
which reduces to Serre's property $\FA$ when $r=1$.  The method
applies to $S$-arithmetic groups in higher $\Q$-rank, to
simplex reflection groups (including some non-arithmetic ones), and to
higher rank Chevalley groups over polynomial and other rings
(for example $\SL_n(\Z[x_1,\ldots ,x_d]), n>2$).

\end{abstract}

\section{Introduction}

Serre proved \cite{Se1,Se2} that $\Gamma=\SL_3\Z$ has {\em
property} $\FA$: any $\Gamma$-action on any simplicial
tree $T$ has a global fixed
point.  Serre's result was extended to arithmetic and $S$-arithmetic lattices in
higher rank semisimple groups by Margulis \cite{Ma}, to groups
with property T by Alperin and Watatani \cite{Al}, and to many
higher-rank Chevalley groups over certain commutative rings
by Serre, Tits and Fukunaga \cite{Fu}.

These beautiful theorems unfortunately give only a rank one/higher rank
dichotomy.  While nontrivial actions of higher-rank groups on trees do
not exist at all, these groups have many nontrivial actions on
higher-dimensional simplicial complexes of nonpositive curvature (in the
$\CAT(0)$ sense).  For example, the group $\SL_n\Z[1/p]$ acts without a
global fixed point on the affine building associated to
$\SL_n(\Q_p)$; this building is
an $(n-1)$-dimensional, nonpositively curved simplicial
complex.  Such actions were used by Quillen and Soul\'{e} (see
\cite{So}) to prove that such groups are pushouts of
``$(n-1)$-simplices of groups'' .

Since $\SL_n\Z[1/p]$ acts (without a global fixed point) on a
nonpositively curved simplicial complex of
dimension $n-1$ but not one of dimension $1$,
it is natural to ask if it admits such an action in dimension
$m$ with $1<m<n-1$. A related question: can $\SL(n,\Z[1/p])$ be written as a
(nice) pushout of a diagram of dimension $<n-1$?  We prove below that
the answer to these questions is ``no'', but first it
is useful to make the following:

\begin{Definition}[Property $\FA_n$]
Let $n\geq 1$.  A group $\Gamma$ is said to have {\em property $\FA_n$} if
any isometric $\Gamma$-action on any $n$-dimensional, $\CAT(0)$
cell complex $X$ has a global fixed point.
\end{Definition}

The property $\FA_1$ corresponds with Serre's property $\FA$.  If a group
$\Gamma$ has $\FA_n$ then it has $\FA_m$ for all $m<n$.  In this paper,
all complexes $X$ are complete and have finitely many isometry types of
cells, and all actions are by isometries. We emphasize
that $X$ need not be locally finite, and the putative action is allowed
to have infinite stabilizers and to be nonfaithful.  These possibilities
are important for applications.

There is an even stronger notion which we shall find useful.

\begin{Definition}[Strong $\FA_n$]
A group $\Gamma$ is said to satisfy the {\em strong $\FA_n$ property} if
any $\Gamma$-action on a complete $\CAT(0)$ space $X$ satisfying the following properties
has a global fixed point.

\medskip
\noindent
{\bf \boldmath$n$-dimensionality: }$\widetilde{H}_n(Y)=0$ for all open subsets
$Y\subseteq X$.

\smallskip
\noindent
{\bf Semisimplicity: }The action of $\Gamma$ on $X$ is {\em semisimple}, i.e.\
the translation length (see below) of each $g\in \Gamma$ is realized by some $x\in X$.
\end{Definition}

\bigskip
Bridson proved (see \cite{BrH}) that any isometric action on a cell complex as above must be semisimple, so that strong $\FA_n$ implies $\FA_n$.

When $\Gamma$ is an irreducible lattice in a semisimple Lie group, the
problem of determining when a $\Gamma$-action on a singular $\CAT(0)$
space $X$ must have a global fixed point has been studied for $X$ a tree
(Margulis \cite{Ma}), $X$ a Euclidean building
(Margulis \cite{Ma2}, Gromov-Schoen \cite{GS}), and $X$ a $\CAT(-1)$
space (Burger-Mozes \cite{BM}, Gao \cite{Ga}).  These papers have used
either ergodic-theoretic or harmonic maps techniques.
In this paper we introduce a new method, which reduces to Serre's \cite{Se1,Se2} in the case of trees.
One advantage to our method is that it applies to many
finitely-generated groups which are not lattices in any locally compact
topological group.

\bigskip
\noindent
{\bf Statement of results. }Our first main results give an
extension of the Serre-Tits-Margulis theorems.  For the definitions in the statement of the following theorem, see Subsection \ref{subsection:arithmetic} below.

\begin{theorem}[Fixed point theorem for $S$-arithmetic groups]
\label{theorem:rigidity}
Let $k$ be an algebraic number field, and let
$G$ be an absolutely almost simple, simply-connected, connected,
algebraic $k$-group.
Suppose that $r=\rank_k(G)\geq 2$.  Let $S$ be a finite set of valuations of
$k$ containing all the archimedean valuations.
Let $\Gamma$ be an $S$-arithmetic subgroup of
$G$.  Then $\Gamma$ has the strong property $\FA_{r-2}$
\end{theorem}

As a special case we highlight the following.

\begin{corollary}
\label{corollary:rigidity}
Let $n\geq 3$.  Then any finite index subgroup of $\SL_n\Z$ or of
$\SL_n\Z[1/p]$ has the strong property $\FA_{n-2}$.
\end{corollary}

The dimension in Theorem \ref{theorem:rigidity} and Corollary \ref{corollary:rigidity}
is sharp, as can be seen from the
action of $\SL(n,\Z[1/p])$ on the affine building for $\SL(n,\Q_p)$.   For $\SL(n,\Z)$ the
result is not sharp: an argument of Y. Shalom combined with some
elementary arguments (see also \cite{Pa}) gives that $\SL(n,\Z),
n\geq 3$ has strong $\FA_n$ for all $n$.
We also would like to emphasize that our
method of proof uses unipotents in a strong way, so that (unlike
many of the other methods) we can say nothing about the $k$-rank zero case.

Our next interest is in understanding actions of Chevalley groups over finitely generated commutative rings, for example $\SL(n,\Z[x_1,\ldots ,x_d])$.  These groups are typically not lattices in any locally compact toplogical group, and so the usual methods do not seem to apply.

For the basics of Chevalley groups, we refer the reader to \cite{St,Ste}.  Let $\Phi$ be a reduced, irreducible root system and let $R$ be a commutative ring.  Let $G(\Phi,R)$ be a Chevalley group of type $\Phi$ over $R$, and let $E(\Phi,R)$ denote its elementary subgroup.
Our second main result extends Fukunaga's theorem \cite{Fu} from $\FA_1$ to $\FA_n$.

\begin{theorem}[Fixed point theorem for Chevalley groups]
\label{theorem:chevalley}
Suppose $\Phi$ has rank $r\geq 2$.
Then the group $E(\Phi,R)$ has the strong property $\FA_{r-1}$.
\end{theorem}

Since $\SL(n,Z[x])$ surjects onto $\SL(n,\Z[1/p])$, the example above gives that
the dimension in Theorem \ref{theorem:chevalley} is sharp.

It is a major problem in $K$-theory to determine when $G(R)=E(R)$.  This is known for many rings, for example for polynomial or Laurent series rings over a field or over $\Z$ (this is a famous theorem of Suslin).
We thus obtain, for example, the following.

\begin{corollary}
Let $R$ be the ring of polynomials or Laurent series over $\Z$ or over a field, and let $n\geq 3$.
Then $\SL(n,R)$ has the strong property $\FA_{n-2}$.
\end{corollary}

Note that there
is also overlap between the above theorems: for example $SL_n(\Z[x])$ surjects
onto $\SL_n(\Z[1/p])$, so the theorem for the former group implies it for
the latter.  However, Theorem \ref{theorem:chevalley} can be used to deduce the corresponding result for $S$-arithmetic lattices only in those $G$ which are $k$-split .

After proving Theorem \ref{theorem:chevalley}, we wondered if
$G(\Phi,R)/E(\Phi,R)$ is always solvable when $\rank(\Phi)\geq 2$, and asked R. Hazrat and N. Vavilov,
who then answered this question affirmatively in \cite{HV}, as long as $R$ has finite Bass-Serre dimension.  Together with Theorem \ref{theorem:chevalley}, this immediately
gives the following.

\begin{corollary}
Let $G(\Phi,R)$ be a Chevalley group of type $\Phi$ over a finitely generated
commutative ring $R$ with finite Bass-Serre dimension.  Suppose $\Phi$ has rank $r\geq 2$.
Then any action of $G(R)$ on an
$m$-dimensional space satisfying the axioms of the strong property $\FA_m$
with $m<r$ factors through the action of the
solvable group $G(R)/E(R)$.
\end{corollary}

Our method also applies to certain reflection groups.

\begin{theorem}[Reflection groups]
\label{theorem:reflection}
Let $\Gamma_n$ be any discrete group generated by reflections in the sides of
a finite volume $n$-simplex in $\R^n$ or $\hyp^n$.  Then
$\Gamma_n$ has the strong property $\FA_{n-1}$.
\end{theorem}

The dimension $n-1$ in Theorem \ref{theorem:reflection} is
sharp.  Also, the conclusion of this theorem is never true for polyhedra
which are not simplices; groups generated by reflections in the faces of
such polyhedra admit nontrivial actions on simplicial trees.  A. Barnhill \cite{Bar} has used
the methods introduced in this paper to classify such actions, and to begin a
classification for actions on higher-dimensional spaces.  We will
use Theorem
\ref{theorem:reflection} to prove that the $\Gamma_n$ above,
even non-arithmetic examples, have properties in common with arithmetic
groups.

As a final example, we would like to mention that M. Bridson has used the method introduced in this paper to prove strong fixed point theorems for automorphism groups of free groups.

\bigskip
\noindent
{\bf Integrality and finiteness. }Representations of groups with
property $\FA_n$ are quite constrained.  Replacing ``2'' by ``n'' in
6.2.22 of \cite{Se2}, and noting that the affine building attached to
$\GL_n$ of a field with discrete valuation is a nonpositively curved
$(n-1)$-complex, immediately gives the following theorem.

\begin{theorem}[Integral eigenvalues]
\label{theorem:integral}
Suppose $\Gamma$ has property $\FA_{n-1}$.  Let $\rho:\Gamma\rightarrow
\GL(n,k)$ be
any representation of degree $n$ over the field $k$.  Then the
eigenvalues of each of the matrices in $\rho(\Gamma)$ are integral. In
particular they are algebriac integers if $\chr(k)=0$ and are roots of
unity if $\chr(k)>0$.
\end{theorem}

The general theory of groups with this property was introduced and
studied by Bass \cite{Ba}, who called them groups of {\em integral
$n$-representation type}. We thus have:

\begin{center}
{\it If $\Gamma$ has $\FA_{n-1}$ then $\Gamma$ is of integral
$n$-representation type.}
\end{center}

Bass proved a finiteness theorem (Proposition 5.3 of \cite{Ba})
for groups of integral $n$-representation type, which immediately gives
the following.

\begin{theorem}[Finiteness of the character variety]
\label{theorem:finiteness}
Suppose $\Gamma$ has property $\FA_{n-1}$.  Then there are only finitely
many conjugacy classes of irreducible representations of $\Gamma$ into
$\GL_n(K)$ for any algebraically closed field $K$.
\end{theorem}

By Theorem \ref{theorem:reflection},
groups of reflections in the faces of an $(n+1)$-simplex in
$\H^n$ satisfy the conclusions of Theorem
\ref{theorem:integral} and Theorem \ref{theorem:finiteness}.  Note that
there are non-arithmetic examples of such reflection groups acting on
$\H^n, n=3,4,5$ (see \cite{Vi}).
We also note that, for reflection
groups, there are examples where the finite number in the conclusion of
Theorem \ref{theorem:finiteness} can be made arbitrary large.

As a concrete example consider one of the reflection groups $\Gamma_n$;
it is a lattice in $\O(n,1)$ and has property $\FA_{n-1}$.
Hence any there are only finitely many conjugacy classes of
representation $\rho:\Gamma \rightarrow O(n,m)$ for $m<n$.

\bigskip
\noindent
{\bf Acknowledgements. }It is a pleasure to thank Dave Witte Morris for useful conversations.

\section{Group actions on $\CAT(0)$ spaces}

{\bf Standing assumptions. }Henceforth we will assume that $X$
satisfies the properties as in the definition of strong property $\FA_n$.
So $X$ is a metrically complete, $n$-dimensional, $\CAT(0)$ space,
and all actions on $X$ are isometric and semisimple.

\subsection{Some $\CAT(0)$ preliminaries}

We first recall some facts about $\CAT(0)$ spaces.  A nice reference
for background and definitions is \cite{BrH}.

For any $g\in \Isom(X)$, let $$\minset(g)=\{x\in X: d(x,gx)\leq d(y,gy)\
\forall y\in X\}$$ and let $\tau(g)=\inf_{x\in X}d(x,gx)$.  The isometry
$g$ is called {\em semisimple} if the infimum in the definition of
$\tau(g)$ is realized by some $x$.
Under our standing assumptions, every $g\in
\Isom(X)$ is semisimple, and is
one of two possible types: {\em elliptic}, which means that the fixed
set $\Fix(g)\neq \emptyset$; or {\em hyperbolic}, which means that
$\minset(g)\neq \emptyset$ is the unique nonempty $g$-invariant set with
every point $x\in \minset(g)$ translated a distance $\tau(g)$.

For hyperbolic $g$, the set $\minset(g)$ may be realized as a union of
parallel {\em axes} $A_g$, each of which is a $g$-invariant, bi-infinite
geodesic line in $X$ on which $g$ acts by translation by $\tau(g)$.
For elliptic or hyperbolic $g$, the set
$\minset(g)$ is a closed, convex subset of $X$.

\subsection{Finite group actions}

One of the basic results on group actions on a complete
$\CAT(0)$ space $X$ is the following lemma.

\begin{lemma}[Bruhat-Tits Fixed Point Theorem]
\label{lemma:finite}
Any finite group action on a $\CAT(0)$ space $X$ has a global fixed point.
\end{lemma}

The idea of the proof is that the orbit of any
point under the group is a bounded set in $X$, hence has a unique
center of mass which must be fixed by the group.  For a detailed proof
see, for example, \cite{BrH}.

\subsection{General results on $\FA_n$}
\label{subsection:general}

We now record several elementary facts.  Each holds with ``$\FA_n$'' replaced by ``strong $\FA_n$''.

\begin{enumerate}
\item If $G$ has property $\FA_n$ then $G$ has $\FA_m$ for all $m\leq
n$.
\label{item:lessthan}

Proof: Fixing a triangulation on each $\R^n$, one can easily convert an
action on a $\CAT(0)$ $m$-complex $X$ to an action on a $CAT(0)$
$n$-complex $Y=X\times \R^{n-m}$.  A global fixed point for the second
action gives one for the first.

\item  If $G$ has $\FA_n$ then so does every quotient of $G$.

Proof: This is obvious.

\item Let $H$ be a normal subgroup of $G$. If $H$ and $G/H$ have $\FA_n$
then so does $G$.

Proof: Suppose $G$ acts on a $\CAT(0)$ $n$-complex $X$.  Then
$\Fix(H)$ is a nonempty convex subset of $X$, hence is a
$\CAT(0)$ $m$-complex for $m\leq n$.  As $H$ is normal,
$G$ acts on $\Fix(H)$ and this action factors through $G/H$, which by
hypothesis and (\ref{item:lessthan}) above has a fixed point $y\in \Fix(H)$.
Hence $G$ fixes $y$.

\item If some finite index subgroup $H$ of $G$ has $\FA_n$, then so does
$G$.
\label{item:index}

Proof: Suppose $G$ acts on a $\CAT(0)$ $n$-complex $X$.
Then $Hx=x$ for some $x\in X$.
Let $N$ be a finite index normal subgroup of $G$ which is
contained in $H$. So $N$ fixes $x$ and $G/N$ acts on $\Fix(N)$.  As
$G/N$ is finite, we are done by Lemma \ref{lemma:finite}.

\end{enumerate}

Note that the converse to (\ref{item:index}) is not true, even when $n=1$; see,
e.g. \cite{Se2}, 6.3.5.

\subsection{Actions of nilpotent groups}

In order to understand actions of more complicated groups on $\CAT(0)$
spaces, we first need to understand actions of nilpotent groups.
Actions of abelian groups by semisimple isometries on $\CAT(0)$ spaces
are completely understood.  The key property of such group actions is
that they have an invariant flat.  Recall that a {\em flat} in $X$ is an
isometrically embedded copy of some Euclidean space $\R^m,m\geq 0,$ in $X$.

The following proposition is well known; in this form it is (except for
the last sentence, which we prove below) Theorem 7.20 of \cite{BrH}.

\begin{proposition}[Abelian groups]
\label{proposition:abelian}
Let $\Gamma$ be a finitely generated abelian group acting by semisimple
isometries on a $\CAT(0)$ space $X$.  Then
\begin{enumerate}
\item $\Minset(\Gamma)=\cap_{\gamma\in\Gamma}\Minset(\gamma)$ is nonempty and
splits as a product $Y\times \R^n,n\geq 0$ with $Y$ nonempty and convex.
\item $\Gamma$ leaves $\Minset(\Gamma)$ invariant, preserves the product
structure, acts trivially on the first factor, and acts cocompactly by
translations on the $\R^n$ factor. Further $n\leq \rank_{\Q}\Gamma$.
\item Any $g\in\Isom(X)$ which normalizes $\Gamma$ leaves $\Minset(\Gamma)$
invariant and preserves the isometric splitting $Y\times \R^n$. If $g$
in fact centralizes $\Gamma$, then the induced action on the $\R^n$
factor is by translations.
\end{enumerate}
\end{proposition}

\proof
As mentioned above, we need only prove the last claim.  By item (2), the
action of $g$ on the $\R^n$ factor
commutes with a cocompact group of translations.  But any such isometry
$g$ of Euclidean space must itself be a translation: if $A$ is the
linear part of $g$ then we would have $A(v+b)=Av+b$ for all $v\in \R^n$
and for every $b$ in some basis, from which it follows that $A$ is the
identity.
\endproof

Using Proposition \ref{proposition:abelian}, we can understand nilpotent
groups acting on $\CAT(0)$ spaces.  The following is likely well-known,
and is a simple variation of the
usual theorems on properly discontinuous actions; it was proven in the
case of isometry groups of trees by Serre (see \S 6.5 of \cite{Se2}).
We include a proof
here for completeness.

\begin{proposition}[Nilpotent groups]
\label{proposition:nilpotent}
Let $N$ be a finitely-generated, torsion-free nilpotent group acting
by semisimple isometries on a $\CAT(0)$ space $X$.  Then either
\begin{enumerate}
\item there is an $N$-invariant flat $\R^n, n>0$ on which $N$ acts by
translations, hence factoring through an abelian group, or
\item $N\cdot x=x$ for some $x\in X$.
\end{enumerate}
\end{proposition}

Note that case (2) is simply case (1) with $n=0$; we separate the
cases in the statement of the proposition for pedagogical reasons.

\proof
We prove the proposition by induction on the length $d$ of the lower central
series for $N$.  When $d=1$ then
$N$ is abelian, and this is simply a restatement of
Proposition \ref{proposition:abelian}, the case $n=0$ giving a global fixed point.

Now consider an arbitrary nilpotent $N$ with lower central series of
length $d\geq 2$, and assume we know the proposition for nilpotent groups with
lower central series of length less than $d$.

Apply Proposition \ref{proposition:abelian} to the center $Z(N)\neq N$. So
$\Fix(\Z(N))=Y\times \R^n, n\geq 0$, where $Y$ is a nonempty
convex subset of $X$ (hence is a complete $\CAT(0)$ space).  As $N$
centralizes $Z(N)$, it leaves $\Minset(Z(N))$ invariant, preserves the
product decomposition $Y\times \R^n$, and acts by translations on the
$\R^n$ factor.  In other words, the $N$-action on
$\Minset(Z(N))$ is a product action $\rho=\rho_1\times \rho_2$, where
$\rho_1:N\rightarrow \Isom(Y)$ and $\rho_2:N\rightarrow \Isom(\R^n)$.

Since $\Fix(Z(N))=Y\times \R^n$, we have $\rho_1(Z(N))={\rm Id}$, so
$\rho_1$ factors through an $N/Z(N)$ action on the $\CAT(0)$ space $Y$.
Note that $N/Z(N)$ is nilpotent of degree less than $d$, so we can
apply the inductive hypothesis to this action.  So $\rho_1(N/Z(N))$
leaves invariant some flat $\R^m$ in $Y$ on which it acts by
translations (the case $m=0$ being that
$\rho_1(N/Z(N))$ has a global fixed point in $Y$). Hence
$\rho(N)=\rho_1(N)\times\rho_2(N)$ leaves invariant the flat
$\R^m\times\R^n$ in $\Minset(Z(N))$, and acts on it via translations.
\endproof

Proposition \ref{proposition:nilpotent} gives the following simple
criterion for an element in a nilpotent group $N$ to have a fixed point,
and for a nilpotent group $N$ to have a global fixed point.

\begin{corollary}[Fixed points for nilpotent groups]
\label{corollary:nilpotent:global}
\label{corollary:commutator}
Let $N$ be a finitely-generated, torsion-free nilpotent group acting by
semisimple isometries on a $\CAT(0)$ space $X$.  Then
\begin{enumerate}
\item If $g^m\in [N,N]$ for some $m>0$, then $g$ has a fixed point.
\item If $N$ is generated by elements each of which
has a fixed point, then $N$ has a global fixed point.
\end{enumerate}
\end{corollary}

\proof
Item (1) follows from Item (1) of Proposition
\ref{proposition:nilpotent}, since the translation subgroup of $\R^n$ is abelian and so $g$
must be in the kernel of the $N$-action on $\R^n$.  For Item (2), note that if (1) of Proposition
\ref{proposition:nilpotent} were to hold, then $N$ would contain some generator
of hyperbolic type, contradicting the given.  Thus (2) of Proposition \ref{proposition:nilpotent}
holds, and we are done.
\endproof

\section{Helly's theorem}

One of the most basic results of convexity theory is Helly's Theorem.

\begin{theorem}[Helly, 1913]
\label{theorem:helly:original}
Let $\{X_i\}$ be any finite collection of nonempty, open convex sets in
$\R^n$.  If $$X_{i_1}\cap \cdots \cap X_{i_{n+1}}\neq \emptyset$$
for every $i_1<\cdots <i_{n+1}$, then $\bigcap_i X_i\neq \emptyset$.
\end{theorem}

We will need a generalization of this theorem to convex subsets of
$\CAT(0)$ $n$-complexes.  The standard proof of
Helly's theorem use {\em Radon's Theorem}: any set of at least $n+2$ points in
$\R^n$ can be divided into two nonempty subsets whose convex hulls
intersect.  However, Radon's Theorem is {\em false} when $\R^n$ is
replaced by a $\CAT(0)$ $n$-complex $X$, as can be seen even
when $n=1$ and $X$ is a tree.

However Helly's original proof , which seems to have been almost
completely forgotten \footnote{In fact a number of the
``generalizations'' of Helly's theorem in the literature follow
immediately from Helly's original proof.}, does generalize to this
context.  To state Helly's actual result in modern terminology, recall
that a {\em homology cell} is a nonempty space $X$ whose singular
homology groups are isomorphic to those of a point, that is the reduced
homology $\widetilde{H}_q(X)=0$ for all $q\geq 0$.  Helly's original result
and proof, restated in modern terminology by
Debrunner (see Theorem 2 of
\cite{De}), is:

\begin{theorem}[Topological Helly Theorem]
\label{theorem:helly:topological}
Let $X$ be a normal topological space with the property that every
nonempty open subset $Y\subseteq X$ has $\tilde{H}_q(Y)=0$ for all $q\geq n$.
Let $\{X_i\}$ be any finite collection of nonempty closed homology cells
in $X$.  If the intersection of any $r$ sets of this family is nonempty
for $r\leq n+1$, and is a homology cell for $r\leq n$, then
$\bigcap_i X_i$ is a homology cell, in particular is nonempty.
\end{theorem}

Note that nonempty convex subsets of $\R^n$ are homology cells,
as are intersections of convex sets.  Hence Theorem
\ref{theorem:helly:topological} immediately implies Theorem
\ref{theorem:helly:original}.

Although Theorem \ref{theorem:helly:topological} is stated in \cite{De}
only in the case when $X=\R^n$, the only property of $\R^n$ used in his
proof (see Lemma $B_n$ of \cite{De}) is that every nonempty open subset
$Y\subseteq X$ has $\tilde{H}_q(Y)=0$ for all $q\geq n$.  Note that
this property holds for all contractible,
$n$-dimensional simplicial complexes, even
ones that are not locally finite.  The proof is exactly the same as the one
given in \cite{De} for $\R^n$.

Theorem \ref{theorem:helly:topological} is stated
in \cite{De} for open sets $X_i$; however, for a normal
topological space, e.g. a metric space, the theorem implies the version
for closed sets $X_i$.  This is because, for a finite collection of closed
sets in a normal topological space, there exist regular neighborhoods
around each of the sets with the property that whenever two of the sets
are disjoint so are their regular neighborhoods.

While Theorem \ref{theorem:helly:topological} suffice for
our applications, it is actually a very special case (when $X$ is a CW complex) of the following
old theorem of Leray (see, e.g.\ \cite{Br} Theorem VII.4.4).

\begin{theorem}[Leray]
Let $\{X_\alpha\}$ be a family of non-empty subcomplexes of a CW complex $X$.
Suppose that every non-empty, finite
intersection of the $X_\alpha$ is acyclic.  Then
$$H_{\ast}(\cup_i X_i)=H_\ast ({\cal N}(\{X_i\}))$$
where ${\cal N}(\{X_\alpha\})$ is the nerve of the cover $\{X_\alpha\}$.
\end{theorem}

In particular, if $\{X_i\}$ is any collection of convex subsets of an
$n$-dimensional metric space, and if we know the nerve of the covering
has nonvanishing $n$-th homology, then further intersections are
forced. Theorem \ref{theorem:helly:topological} is the very special case
when the nerve is the boundary of an $n$-simplex, in which case the
full $n$-simplex must be part of the nerve, that is the sets have a
common intersection.  Thus Leray's theorem
gives a vast generalization of Helly's original theorem.

It should be possible to apply the techniques of this paper to a much
wider class of groups than we consider here, replacing our use of Helly's
Theorem by Leray's Theorem.

\section{Combinatorics of generators of $S$-arithmetic and Chevalley groups}

\subsection{Generators for $S$-arithmetic groups}
\label{subsection:arithmetic}

We begin by recalling some definitions.  An algebraic $k$-group $G$
is {\em connected} if it is connected in the Zariski topology.
Every algebraic $k$-group is an extension of a connected algebraic $k$-group by a finite group.
$G$ is called {\em absolutely almost simple} if any proper algebraic normal subgroup of $G$ is
trivial.  A conencted $G$ is {\em simply connected} if every central isogeny $G'\to G$ from a connected
algebraic $k$-group $G'$ is an algebraic group isomorphism.  The special linear group and the symplectic group are examples of
absolutely almost simple, connected, simply-connected algebraic $k$-groups.

The goal of this subsection is to prove the following.

\begin{theorem}[Combinatorics of generators]
\label{theorem:generators}
Let $k$ be an algebraic number field, and let
$G$ be an absolutely almost simple, simply-connected, connected,
algebraic $k$-group.
Suppose that $r=\rank_k(G)\geq 2$.  Let $S$ be a finite set of valuations of
$k$ containing all the archimedean valuations.
Let $\Gamma$ be an $S$-arithmetic subgroup of
$G$.  Then there exists a set $C=\{\Gamma_1,\ldots
,\Gamma_{r+1}\}$ of finitely generated nilpotent subgroups of
$\Gamma$ which has the following properties:
\begin{enumerate}
\item $C$ generates a finite index subgroup of $\Gamma$.
\item Any proper subset of $C$ generates a nilpotent subgroup of
$\Gamma$.
\item There exists $m\in \Z^+$ so that for each $\Gamma_i\in C$ there is
a nilpotent subgroup $N<\Gamma$ so that $r^m\in [N,N]$ for all $r\in \Gamma_i$.
\end{enumerate}

\end{theorem}

\proof

Fix a maximal $k$-split torus $T$ in $G$, and let $X(T)$ denote the
group of characters on $T$.  Consider the adjoint action of $T$ on
the Lie algebra ${\mathfrak g}$ of $G$.  Let $\Phi=\Phi_k(T,G)$  be the system of
$k$-roots with respect to $T$.  For $\alpha\in X(T)$ let
$${\mathfrak g}_\alpha=\{X\in {\mathfrak g}: Ad(t)X=\alpha(t)X \ \forall
t\in T\}$$
As $G$ is simple $\Phi$ is irreducible.  Let $\Delta\subset \Phi$ be a
system of simple roots and let $\Phi^+$ (resp. $\Phi^-$) be the
corresponding system of positive (resp. negative) roots.  For each
$\alpha\in \Phi$, let $U_\alpha$ be the
unique $T$-stable subgroup of $G$ having Lie
algebra the span of the root spaces $\{{\mathfrak g}_{r\alpha}:r\in\Z^+\}$.
The group $U_\alpha$ is a unipotent
$k$-subgroup of $G$, and is thus nilpotent.

Let ${\cal O}_S$ be the ring of $S$-integers
in $k$, and for any subgroup $H<G$ define $H({\cal O}_S):=H\cap \GL(n,{\cal O}_S)$.  For any
ideal $\mathfrak a\neq 0$ in
${\cal O}_S$, let
$$H({\mathfrak a})=\{x\in H({\cal O}_S): x\congruent {\rm Id} (\mbox{mod\ }
{\mathfrak a})\}$$

We will make essential use of the following theorem of Raghunathan, also
proved by Margulis.

\begin{theorem}[\cite{Ra}, Theorem 1.2]
\label{theorem:raghunathan}
With notation as above, let $\mathfrak a$ be any nonzero ideal of ${\cal
O}_S$.  Then the group $E({\mathfrak a})$
generated by $\{U_\alpha({\mathfrak a}):\alpha \in \Phi\}$
has finite index in $G({\mathfrak a})$.
\end{theorem}

Now suppose we are given an $S$-arithmetic lattice $\Gamma$ as in the
hypothesis of the theorem.  As
$\Gamma$ is $S$-arithmetic it contains $E({\mathfrak a})$ for some ${\mathfrak a}$.  By
Theorem \ref{theorem:raghunathan}, this containment is finite index.  By
(\ref{item:index}) on page \pageref{item:index}, it suffices to prove
the theorem for this finite index subgroup, which we will now denote by
$\Gamma$.

Let $\Gamma_\alpha=U_\alpha({\mathfrak a})$.  Then $\Gamma_\alpha$, being an $S$-arithmetic subgroup of
the $k$-group $U_\alpha$, is a finitely generated nilpotent group.
Note that $\Gamma_\alpha$ is nilpotent since it
is a subgroup of the nilpotent group $U_\alpha$.

As $\Phi$ is irreducible, there is a unique longest root $\beta'$ with
respect to $\Delta$.  Let $\beta=-\beta'$. We now set
$$C=\{\Gamma_\alpha: \alpha\in \Delta\}\cup
\{\Gamma_\beta\}$$ Note that $$|C|=|\Delta|+1=r+1$$ We claim that $C$ has
the required properties.

\bigskip
\noindent
{\bf Proof of (1): }We first show that
$C$ generates a finite index subgroup of $\Gamma=G({\mathfrak a})$.
For roots $\alpha,\beta$, let
$$[\alpha,\beta]=\Phi\cap \{m\alpha +n\beta :m,n\in \Z^+\}$$

We will need the following lemma, which is the lattice analog of a
well-known fact about commutators of root groups in algebraic groups.

\begin{lemma}[\cite{Ab}, Proposition 7.2.4]
\label{lemma:abels}
For any $\alpha,\beta\in \Phi$, let $N$ denote the group generated by
$\Gamma_\alpha$ and $\Gamma_\beta$.  Then the commutator subgroup
$[N,N]$ contains a finite index subgroup of $\Gamma_\phi$
for each $\phi\in [\alpha,\beta]$.
\end{lemma}

Let $<C>$ denote the smallest subgroup of $\Gamma$ containing each group
in $C$.
Since $$<C>\supset \Gamma_{\Delta}:=<\{\Gamma_\alpha: \alpha \in \Delta\}>$$
it follows from Lemma \ref{lemma:abels} that
$\Gamma_\Delta$ contains a
finite index subgroup $\Gamma'_{\alpha}$ of $\Gamma_\alpha$ for each $\alpha
\in \Phi^+$.

We claim that $<C>$ also contains a finite index subgroup
$\Gamma'_{\alpha}$ of $\Gamma_\alpha$ for each $\alpha\in \Phi^-$.
To prove this, first note that since $-\beta$
is the unique maximal root, we can write (see \cite{Hu}, 10.4 Lemma A)
$$\beta=\sum_{\alpha\in \Delta} k_\alpha \alpha \mbox{\ \ with each \ }
k_\alpha<0$$

By definition, $<C>$ contains (a finite index subgroup of)
$\Gamma_{\alpha}$ for each $\alpha \in \Delta$, so by repeatedly applying
Lemma \ref{lemma:abels} we see that $<R>$ contains a finite index
subgroup $\Gamma'_{\alpha}$ of $\Gamma_\alpha$
for each $\alpha \in [\beta,\Delta]\supseteq \{-\tau: \tau \in
\Delta\}$, the final containment following from the fact that each
$k_\alpha<0$.

By the same argument as above which showed that the group generated by
the $\Gamma'_\alpha, \alpha\in \Delta$ contains a finite index subgroup
of each $\Gamma_\alpha, \alpha\in \Phi^+$, we deduce that $<C>$ contains
a finite index subgroup of each $\Gamma_\alpha, \alpha\in \Phi^-$,
proving the claim.

Now for each
$\alpha\in \Phi$, the finite index subgroup $\Gamma'_\alpha$ of the
nilpotent group $\Gamma_\alpha$ determines an ideal ${\mathfrak a}_\alpha$
of the finitely-generated $\Z$-algebra of $S$-integers.
Let ${\mathfrak a}_\Phi$ denote the intersection in the ring of
$S$-integers of these finitely many ideals.  Then the group generated by
all of the $\Gamma'_{\alpha}, \alpha\in \Phi$ contains the group
$\Lambda({\mathfrak a}_\Phi)$ generated by all the subgroups of the $U_\alpha$ with
entries in ${\mathfrak a}_\Phi$.  Hence $<C>$ contains
$\Lambda({\mathfrak a}_\Phi)$.  By Theorem \ref{theorem:raghunathan},
$\Lambda({\mathfrak a}_\Phi)$ has finite index in $\Gamma$, and we have
shown that $C$ generates a finite index subgroup of $\Gamma$.

\bigskip
\noindent
{\bf Proof of (2): } To prove property (2), consider any proper subset
$Q$ of $C$.  As $<Q>$ is a subgroup of $<\{U_\alpha: \alpha\in Q\}>$, it
suffices to prove that this latter group is nilpotent.  As the root
groups corresponding to any collection of positive roots generate a
unipotent subgroup of $G$ (see, e.g.. \cite{Ma2},p.37), it suffices to
prove the following.

\begin{lemma}
\label{lemma:roots2}
Any subset of $|C|-1$ elements of $\Delta \cup\{\beta\}$ is a
subset of the positive roots with respect to some basis of the root
space.
\end{lemma}

\proof
By definition this holds for the subset $\Delta$.  So fix any
$\alpha_i \in \Delta$ and consider the collection $B=(\Delta \setminus
\alpha_i)\cup \beta$, which for convenience we will write as
$\{v_1,\ldots ,v_r=\beta\}$.

Let $(\ ,\ )$ denote the inner product on the root space.  Note that $B$
is a linearly independent set of vectors as $\{v_1,\ldots ,v_{r-1}\}$ is
part of a basis and $\beta$ has a nontrivial component in the direction
of a vector (namely $\alpha_i$) which completes that basis.
Further we have that
$$(v_i,v_j)\leq 0 \mbox{\ for all\ }i,j$$
since for
$i\neq r$ we have $v_i\in \Delta$ and $v_r$ is the negative of the maximal
root and so has inner product $\leq 0$ with each element of $\Delta$. We
now claim there is a regular vector $\gamma$ such that $(\gamma,v_i)<0$
for all $i$; in other words all of the $v_i$'s lie {\em strictly} on the
same side of the hyperplane $\gamma^{\perp}$ orthogonal to $\gamma$.

\begin{lemma}
\label{lemma:basic:linalg}
Let $A=\{v_1,\ldots ,v_r\}$ be a set of linearly independent vectors in an
$r$-dimensional inner product space $(V,(\ ,\ ))$.  Suppose $v\in V$ is a
nonzero vector with $(v,v_i)\leq 0$ for all $i$.  Then there exists
a vector $\gamma$ with $(\gamma,v_i)<0$ for each $i$.  Further, $\gamma$
can be chosen so that it
does not lie in any subspace spanned by any proper subset of $A$.
\end{lemma}

\proof
Consider $v_j\in v^\perp$; if no such $v_i$ exists then we are done.
Let
$$W=\spn\{v_i: v_i\in v^\perp, i\neq j\}$$
Write $v_j=u+u'$ with $u\in \spn\{v^\perp\}\cap W$ and with $u'\in
\spn\{v^\perp\}\cap W^\perp$.  By linear independence of $A$, we have
$u'\neq 0$.  Let $\epsilon>0$, and let
$$\gamma=v-\epsilon u'$$
Then
$$
\begin{array}{rl}
(\gamma,v_j)&=(v-\epsilon u',u+u')\\
&=(v,u)+(v,u')-\epsilon (u',u)-\epsilon(u',u')\\
&=0+0-0-\epsilon||u'||^2\\
&<0
\end{array}$$
and for every $w\in W$
$$
\begin{array}{rl}
(\gamma,w)&=(v-\epsilon u',w)\\
&=(v,w)-\epsilon (u',w)\\
&=(v,w)
\end{array}$$

In other words, by replacing $v$ with $\gamma$ we have made the inner
product with $v_j$ strictly negative while keeping the inner product
with each $v_i\in W$ nonpositive.  Further, since there is a fixed bound
away from zero for $(v,v_k)$ with $v_k\not\in W$, by taking $\epsilon$
sufficiently small we may guarantee that $(\gamma,v_k)<0$ for each
$v_k\not\in W$.

Repeating the above process until $W$ is empty completes the proof of
the first claim of the lemma.  The second claim is clear.
\endproof

Lemma \ref{lemma:basic:linalg} clearly implies the claim; the last claim
of the lemma giving that $\gamma$ is regular.

Continuing with the proof of Lemma \ref{lemma:roots2}, for any regular vector $\gamma$ let
$$\Phi^+(\gamma)=\{\alpha\in \Phi: (\alpha,\gamma)>0\}$$
Then (see, e.g.\  Theorem 10.1 of \cite{Hu}) the set of all
indecomposable roots in $\Phi^+(\gamma)$ is a root basis of $\Phi$, so
in particular every element of $\Phi^+(\gamma)$ is a positive root with
respect to that basis.  Choosing $\gamma$ as above, we have shown that
$B\subseteq \Phi^+(\gamma)$, and we are done.
\endproof

\bigskip
\noindent
{\bf Proof of (3): }  Let $\alpha\in \Delta\cup \{\beta\}$ be given (in fact we will only use that
$\alpha\in \Phi$).  As $\Phi$ is irreducible and has rank at least $2$,
there exists $\sigma\in \Phi$ which is not proportional to $\alpha$ and
so that $(\alpha,\sigma)>0$.  Then (see, e.g.\ \cite{Hu}, Lemma 9.4)
$\alpha-\sigma\in \Phi$.  Now the group $N$ generated by
$\Gamma_{\sigma}$ and $\Gamma_{\alpha-\sigma}$ is nilpotent by the proof
of (2), since any
two nonproportional roots lie strictly on the same
side of the hyperplane orthogonal to some regular vector; here again we
are using that $\Phi$ is irreducible of rank at least $2$.
Further, by Lemma \ref{lemma:abels}, the
commutator subgroup $[N,N]$ contains a finite index subgroup of
$\Gamma_{\sigma+\alpha-\sigma}=\Gamma_{\alpha}$.  In particular some
positive power of the generator $g_\alpha\in \Gamma_\alpha$ lies in
$[N,N]$.
\endproof

\subsection{Chevalley groups over commutative rings}

\bigskip
\noindent
{\bf Basics of Chevalley groups.  }We now recall the definition and basic properties of
Chevalley groups.  The reader is referred to \cite{Hur,St,Ste} for
details.

Let $R$ be any commutative ring (with unit) which is finitely-generated
as a $\Z$-algebra.  Let $\Phi$ be a reduced, irreducible root system,  $\Delta$
a base for $\Phi$, and $\Phi^+$ the set of positive roots with respect
to $\Delta$.  Each such $\Phi$ determines a unique Lie algebra
$\mathfrak{g}(\Phi)$ over $\C$.  Fixing a faithful,
finite-dimensional, complex representation of $\mathfrak{g}(\Phi)$
determines a {\em Chevalley-Demazure group scheme}, or {\em Chevalley
group}, $G(\Phi,R)=G_\rho(\Phi,R)$ over $R$.  We always assume that
$G(\Phi,\C)$ is simply connected.

For each root $\alpha\in \Phi$ there is a group isomorphism
$$t\mapsto x_{\alpha}(t)$$
from $R$ onto a subgroup $X_\alpha$ of $G(\Phi,R)$, called the {\em root
subgroup} of $G(\Phi,R)$ corresponding to $\alpha$.  The group generated
by $\{X_\alpha: \alpha\in \Phi\}$ is called the group of {\em elementary
matrices}, and is denoted by $E(\Phi,R)$.  We also let $U(\Phi,R)$ be
the group generated by $\{X_\alpha: \alpha\in \Phi^+\}$.  Then
$U(\Phi,R)$ is nilpotent (see, e.g. \cite{Ste,St}).

There are two fudnamental formulas that hold in a Chevalley group.  The first is elementary:
for all $s,t\in R$ and $\alpha \in \Phi$ we have

\begin{equation}
x_\alpha(s)x_\alpha(t)=x_\alpha(s+t)
\end{equation}
The second formula, which holds when $\Phi$ has rank at least $2$,
is the {\em Chevalley Commutator Formula}: for $s,t\in R$ and for
linearly independent $\alpha,\beta \in \Phi$,
\begin{equation}
\label{eq:chevalley}
[x_\alpha(s),x_\beta(t)]=\prod_{i\alpha+j\beta \in
\Phi}x_{i\alpha+j\beta}(N_{\alpha,\beta,i,j}s^it^j)
\end{equation}
where $i,j>0$ and $N_{\alpha,\beta,i,j}$ are certain integers.

\bigskip
\noindent
{\bf A nice generating set for $E(\Phi,R)$.  }
We assume henceforth that $\Phi$ is reduced, irreducible, and has rank
at least $2$.  Let $\{r_1,\ldots ,r_n\}$ be a generating set for $R$.
As $\Phi$ is irreducible it has a unique maximal root $\beta$ (see,
e.g., Lemma 10.4.A of \cite{Hu}).  Let
$$C=\Delta \cup \{\beta\}$$
Note that $$|C|=\rank(\Phi)+1$$
For each $\alpha \in \Delta \cup \{\beta\}$, let $\Gamma_\alpha$ denote the subgroup
of $E(\Phi,R)$ generated by $\{x_\alpha(1),x_\alpha(r_1),\ldots
,x_\alpha(r_n)\}$.

The following proposition combines several results of Fukunaga \cite{Fu}.

\begin{proposition}[Combinatorics of generators for Chevalley groups]
\label{proposition:fukunaga}
With notation as in the previous paragraph, the following holds.
\begin{enumerate}
\item $E(\Phi,R)$ is generated by $\{\Gamma_\alpha: \alpha\in C\}$.
\item For each $\alpha\in C$ and each $r\in \Gamma_\alpha$, there
exists $p=1,2,3$ or $6$ so that $r^p\in [U,U]$ for some nilpotent
subgroup $U\subset E(\Phi,R)$.
\item For any proper subset $C'\subset C$, the group generated by
$\{\Gamma_\alpha: \alpha\in C'\}$ is nilpotent.
\end{enumerate}
\end{proposition}

\proof
Since $\Phi$ is irreducible and $\rank(\Phi)\geq 2$, we may apply
Proposition 2 of \cite{Fu}, which states that for each $t\in R$ and each
$\alpha\in \Phi$, there exists $p=1,2,3$ or $6$ and some base $\Delta'$
so that $x^p_\alpha(t)\in [U,U]$, where $U=U(\Phi,\Delta')$, which is
nilpotent.  This immediately gives (2).  We may also apply Proposition 4 of \cite{Fu}, which
gives precisely (1).   The proof of item (2) of Theorem \ref{theorem:generators} above, in particular Lemma \ref{lemma:roots2}, immediately gives (3).
\endproof

\section{Finishing the proofs of the main theorems}

\subsection{A general fixed point theorem}

Our results on both $S$-arithmetic groups and Chevalley grops admit a common generalization.

\begin{theorem}
\label{theorem:general}
Let $\Gamma$ be a finitely generated group, and let $C=\{\Gamma_1,\ldots ,\Gamma_{r+1}\}$ be a collection of finitely generated nilpotent subgroups of $\Gamma$.  Suppose that:
\begin{enumerate}
\item $C$ generates a finite index subgroup of $\Gamma$.
\item Any proper subset of $C$ generates a nilpotent group.
\item There exists $m>0$ so that for any element $r$ of any $\Gamma_i$ there is a nilpotent subgroup
$N<\Gamma$ with $r^m\in[N,N]$.
\end{enumerate}
Then $\Gamma$ has Property $\FA_{r-1}$.
\end{theorem}

\proof
Suppose that $\Gamma$ acts on an $(r-1)$-dimensional $\CAT(0)$ complex $X$.   By item \ref{item:index} in Section \ref{subsection:general},
assumption (1) of the theorem gives that
it suffices to prove that the subgroup generated by $C$, which we will by abuse call
$\Gamma$, fixes some point of $X$.

By assumption (3) of the theorem, we may apply part (1) of
Corollary \ref{corollary:commutator}
to give that $\Fix(r)\neq \emptyset$ for each $r$ in each $\Gamma_i$, and then we may apply part (2)
of that corollary to give that $\Fix(\Gamma_i)\neq\emptyset$ for each $1\leq i\leq r+1$.
Hence we have a collection $\{\Fix(\Gamma_i)\}$ of $r+1$
nonempty, closed convex sets.  As each $\Fix(\Gamma_i)$ is convex it is contractible.  Since
$C$ generates $\Gamma$ it is enough to show that the intersection of these
$r+1$ sets is nonempty, thus giving a global fixed point for $\Gamma$.

Let $U$ be any subgroup of $\Gamma$ generated by any subset $Q\subset C$ of
$|C|-1=r$ elements.  By assumption (2),  $U$ is
nilpotent.  By the previous paragraph, $U$ is generated by elements each of which has a fixed
point.  Corollary \ref{corollary:nilpotent:global} now implies that
$\Fix(U)$ is a nonempty convex set.

We thus have $r+1$ contractible sets $\{\Fix(\Gamma_i)\}$ in the contractible space $X$, and the intersection of any $r$ of these sets is nonempty.  Applying the topological Helly theorem
(Theorem \ref{theorem:helly:topological}) then gives $\bigcap_{i=1}^r \Fix(\Gamma_i)
\neq \emptyset$, and we are done.
\endproof

\subsection{Proof of Theorem \ref{theorem:rigidity}}

Item (1) of Theorem \ref{theorem:rigidity} follows immediately from
Theorem \ref{theorem:generators} together with Theorem \ref{theorem:general}.
Item (3) of Theorem \ref{theorem:rigidity} follows immediately from Proposition
\ref{proposition:fukunaga} together with Theorem \ref{theorem:general}.  Item (2) of Theorem
\ref{theorem:rigidity} follows from item (3) together with the theorem of Suslin-Abe that
for these rings $R$, we have $G(R)=E(R)$.
\endproof

\subsection{Reflection groups}

Let $\Gamma_n$ be a discrete group generated by reflections in the faces
of a compact $n$-simplex $P$ in the space $Y=\R^n$ or
$Y=\H^n$.  As $\Gamma_n$ is discrete, the subgroup $H_v$ of $\Gamma_n$
stabilizing any one of the $n+1$ vertices $v_i$ of $P$ is a finite group.  Note that
the groups $\{H_v:v\in P\}$ generate all of $\Gamma_n$.  Any proper
subcollection of stabilizers of the
$v_i$ generates a group which stabilizes some face of $P$, and is therefore finite.

Now suppose that $\Gamma_n$ acts on an $m$-dimensional space $X$ with
$m\leq n-1$, satisfying the axioms in the definition of strong property $\FA_m$.  Then by the previous paragraph,  and by the Bruhat-Tits Fixed Point Theorem (Lemma \ref{lemma:finite} above), each stabilizer of a
vertex $v_i$ in $P$ has nonempty fixed set, as does the intersection of the stabilizers of the
vertices in any codimension one face of $P$.  It follows that the nerve of the cover of fixed sets
is an $n$-simplex.  Since $\dim(X)=m<n$, it follows just as in the proof of
Theorem \ref{theorem:general}  that the intersection of these fixed sets is nonempty, and we are done.
\endproof

config: arxiv


TITLE: Lift roots of a polynomial from $\mathbb{F}_p$ to $\mathbb{Q}_p$
QUESTION [1 upvotes]: I was trying to prove a counterexample to Hasse's principle. To do this, I was trying to prove that the equation $x^4-17=2y^2$ has no solutions on $\mathbb{Q}$ but has solutions in $\mathbb{Q}_p$ for every prime $p$.
I was able to prove that the equation has no solutions on $\mathbb{Q}$, but I was not able to do the second part. What I've done was to prove (using Riemman-Hurwitz) that  $x^4-17=2y^2$ defines an elliptic curve and thus Hasse's theorem gives us that the curve is non empty over $\mathbb{F}_p$ (i.e. the equation has at least one solution over $\mathbb{F}_p$). The cases $p=2,17$ are special, but these are easily checked.
From here I know that I have to use Hensel's lemma to lift the solution to $\mathbb{Q}_p$. This is the Hensel's lemma I was trying to use (maybe it is not the correct form of Hensel's lemma):
Let $(K,|\cdot|)$ be a complete valuation field, $f\in R[X]$ and $a_0\in R$ such that $|f(a_0)|<|f'(a_0)|^2$, where $R=\lbrace x\in K\mid|x|\leq 1\rbrace$. Then, there exists a unique $a\in R$ such that $f(a)=0$ and $a-a_0\in\mathcal{M}$, where $\mathcal{M}=\lbrace x\in K\mid|x|< 1\rbrace$.
I'm not sure how to use this, since the theorem involves a polynomial in $x$, but I'm working with a polynomial in $x$ and $y$. Also, I'm not sure how to relate roots in $\mathbb{F}_p$ and roots in $\mathbb{Q}_p$. I know that the residual field of $\mathbb{Q}_p$ is $\mathbb{F}_p$ (i.e. $R/\mathcal{M}\cong\mathbb{F}_p$) but I'm not sure how this relates with Hensel's lemma.
Any hints or help will be thanked.

REPLY [1 votes]: Let me just fill in the details of KCd's comment for completeness. First assume $p\neq 2,17$, and let $(a+p\mathbb{Z},b+p\mathbb{Z})$ be a root of our polynomial in $\mathbb{F}_p$. Then at least one of $a$ and $b$ is non-zero mod $p$; otherwise $17$ would be zero mod $p$, a contradiction. So we have two cases.
First suppose $a\notin p\mathbb{Z}$. Consider the polynomial $g(x)=x^4-(17+2b^2)$. Then $g(a)\equiv 0$ mod $p$ and $g'(a)=4a\not\equiv 0$ mod $p$, so by Hensel's lemma there is a root $a'$ of $g$ in $\mathbb{Q}_p$. Now $(a',b)$ is a $\mathbb{Q}_p$-rational point of our curve.
Now suppose $b\notin p\mathbb{Z}$. Then consider the polynomial $h(y)=2y^2+(17-a^4)$. Then $h(b)\equiv 0$ mod $p$ and $h'(b)=4b\not\equiv 0$ mod $p$, so by Hensel's lemma there is a root $b'$ of $g$ in $\mathbb{Q}_p$. Now $(a,b')$ is a $\mathbb{Q}_p$-rational point of our curve. Either way, we are done.

For the case $p=17$, you can use almost an identical argument as above; we just need to find an non-zero $\mathbb{F}_{17}$-rational point of the polynomial to work. (Why does this suffice?) For example, take $(1+17\mathbb{Z},3+17\mathbb{Z})$. Finally, for the case $p=2$, it would suffice to show that $17$ is a fourth power in $\mathbb{Q}_2$, and by Hensel's lemma it suffices for this to show that $17$ is a fourth power mod $2^5$. (Why?) But $3^4=81$ is congruent to $17$ mod $2^5$, as needed.


TITLE: "Proof" of an Algebraic property of OLS Estimators
QUESTION [0 upvotes]: I'm having a bit of trouble proving  $\sum (x_i - \bar{x})\hat{e_i} = 0$. What I know so far is that the total sum of $\hat{e_i}$'s is zero by property of OLS so when you distribute the $\hat{e_i}$ in, one term "cancels out" and you are left with $\sum x_i\hat{e_i}$ which is equivalent to $\sum x_i(y_i-b_1-b_2x_i)$
When I attempt to simplify more, I keep getting stuck. What I'm doing so far is:
$\sum x_iy_i - b_1\sum x_i - b_2 \sum x_i^2$
= $\sum x_iy_i -(\bar{y}-b_2 \bar{x})\sum x_i - b_2 \sum x_i^2$
= $\sum x_iy_i - \bar{y}\sum x_i + b_2\bar{x}\sum x_i - b_2 \sum x_i^2$. And at this point I get stuck. Is there an easier trick? An OLS property I am forgetting? Thanks!

REPLY [2 votes]: Assume you have a model of the following form: $y=X\beta+\epsilon$ where $X$ is a $n$ by $K$ matrix of $K$ explanatory variables and $n$ observations of each variable. $y$ a column vector consisting of the $n$ observations of the dependent variable and $\epsilon$ is a column vector consisting of the error terms. In your case it seems like you have a model where $X=[1,X_1]$ (i.e. one explanatory variable and an intercept). Now, I assume you know how to find the normal equation when solving for the least squares estimate $b$ of $\beta$. The normal equation reads: $$X^te=0$$  where $e=y-Xb$. Now by simply multiplying out the normal equation above your claim follows, since $0=X^te=[\sum{e_i},\sum{x_ie_i}]^t$. Hence $\sum{(x_i-\bar{x})e_i}=\sum{x_ie_i}-\bar{x}\sum{e_i}=0$.
Also note that the result above applies to any multivariate linear regression model as long as you have an intercept term. However without the intercept term (also called a regression through the origin) we can not be sure that $\sum{e_i}=0$ and hence your claim may no longer be true.


TITLE: Parameters of a Cylinder
QUESTION [0 upvotes]: We know that cylinder is a 3D figure, and that 3D figures have 3 dimensions each. Different shapes have different parameters as well.
For example, parameters of the following:

Cuboid - Length, Breadth, Height
Cone - Radius, Height, Slant Height

Similary, what are the parameters of a cylinder. I know 2 of them - Height & Radius. What is the third (or any other) one?
Update: I meant to say parameters instead of dimensions

REPLY [1 votes]: You're confusing 3 dimensions and the number of parameters a 3D object may have.
Every 3D object has a set of parameters that need to be determined to uniquely determine the magnitude of the object's dimensions. For a cuboid, there's three - length, height and breadth. For a cone and cylinder, you only need two. For a sphere, it's just one (its radius).
However, every 3D object extends in all 3 dimensions - x, y, and z - no matter how many parameters they have.
Hope that helps!

Updated:
As I said earlier, a cone also has only two parameters. And as you determined yourself even a cylinder has only two. As I've proved above in my answer a 3D object may not necessarily have 3 parameters as well.


TITLE: Annihilator of tensor product when $R$ is domain
QUESTION [1 upvotes]: Let $R$ be a Noetherian domain and $M$ and $N$ be two faithful $R$-modules. Is it true that $\operatorname{Ann}_R(M\otimes_R N)=0$?

REPLY [5 votes]: No. $\mathbb{Q}$ and $\mathbb{Q}/\mathbb{Z}$ are faithful $\mathbb{Z}$-modules, but $\ \mathbb{Q}\otimes _{\mathbb{Z}}\mathbb{Q}/\mathbb{Z}=0$. However this is true if $M$ and $N$ are finitely generated (no noetherian hypothesis needed), see e.g. Bourbaki Commutative Algebra II, §4, Proposition 18.


TITLE: A criterion for complete intersection in terms of the Hilbert series?
QUESTION [3 upvotes]: Let $(R, \mathfrak{m})$ be a complete local ring (of dimension $2$ if that makes a difference). I would like to be able to decide whether or not $R$ is a complete intersection (meaning, a quotient of a regular local ring by a regular sequence).
The information that I allow myself is the knowledge of the Hilbert series, that is, of the function
$$n \mapsto \mathrm{length}_R (R/\mathfrak{m}^n).$$
Is such a thing possible? More precisely, is there a criterion for $R$ to be a complete intersection in terms of the Hilbert function? More loosely, is there a sufficient (but perhaps not necessary) condition on the Hilbert function that would ensure that $R$ is a complete intersection (I am not interested in criteria that also force regularity of $R$)?
If a criterion for complete intersection is not possible, I would be willing to relax the assumptions: I would also be interested in criteria for $R$ to be Gorenstein or merely Cohen-Macaulay. Although I have found some literature on similar questions in the case when $R$ is assumed to be graded at the outset, I am not really interested in the graded case.

REPLY [2 votes]: I believe that this is an open problem and in fact one that is considered to be quite hard. See for instance this survey for an idea of what is known (you'll notice that even much easier question than the one you are asking are still wide open).


TITLE: Injection of $\mathbb N$ into proper classes
QUESTION [1 upvotes]: In ZFC, given a proper class, is it possible to prove there is injection of the natural numbers $\mathbb N$ into it?
If not, are there proper classes which do not have such injection?

REPLY [1 votes]: The answer is yes.
Recall the cumulative hierarchy: $V_0=\emptyset$, $V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha$ for $\lambda\in ON$ a limit, and $V_{\alpha+1}=\mathcal{P}(V_\alpha)$.
ZF alone proves (the crucial axioms are Foundation and Replacement) that $V=\bigcup_{\alpha\in ON} V_\alpha$, and that each $V_\alpha$ is a set. EDIT: the symbol "$V$" denotes the whole set-theoretic universe; so what I wrote above really means "ZF proves that every set $x$ is in some $V_\alpha$." So if $C$ is a proper class, we must have that for every $\alpha\in ON$ there is a $\beta>\alpha$ such that $C\cap (V_\beta\setminus V_\alpha)\not=\emptyset$, that is, any proper class has elements of arbitrarily high rank.
So - without choice! - we can define an $\omega$-sequence of ordinals $\alpha_0<\alpha_1<\alpha_2< . . . $ such that for each $i$, there is an element of $C$ in $V_{\alpha_i+1}\setminus V_{\alpha_i}$. This in turn gives us - again without choice! - an $\omega$-sequence of sets $X_i$ such that

$X_i\subset C$ and is nonempty for every $i$, and
$X_i\cap X_j=\emptyset$ for $i\not=j$.

Now, apply choice to this sequence.

Note that there's no special role played by $\omega$ here; more generally, ZF proves that for any proper class $C$ and any ordinal $\gamma$, there is a sequence $\langle X_\alpha: \alpha<\gamma\rangle$ such that

$X_\alpha\subset C$ and is nonempty for every $\alpha$, and
$X_\alpha\cap X_\beta=\emptyset$ for $\alpha\not=\beta$.

Then, in the presence of choice we can extract an embedding from $\gamma$ into $C$.

And choice is, so far as I know, necessary. I suspect there is a model $W\models ZF$ and a definable-without-parameters proper class $C\subset W$ such that $W$ contains no injection from $\omega$ into $C$; put another way, for each set $x\in W$ the set $x\cap C$ is Dedekind-finite. However, I currently cannot show this.
Another observation is that in fact ZF alone proves that any proper class surjects onto the ordinals (exercise, use the argument above). However, the ordinals need not inject into every proper class, even with choice! There are models of ZFC in which there are proper classes into which the ordinals do not embed. Instead, global choice is needed here.


TITLE: The electric potential and the electric field
QUESTION [1 upvotes]: I'm preparing for my school exam in physics and I found that I don't understand the derivation of $E = -\nablaφ$. Here is a derivation from my book:

1) Imagine that 1 and 2 are infinitely close points with coordinates $x_1$ and $x_2$. They are so close that the electric field is a constant.
2) $dx = x_2 - x_1$
3) $-dφ = φ_1 - φ_2$
4) $Edx = -dφ \Rightarrow E = -\frac{dφ}{dx}$. Then we can generalize it on other coordinates (y and z) and be happy.

But I can't understand why $dφ$ does not equal $0$. It decreases more slowly than the electric field. So if the electric field is constant, the electric potential must be constant too.

REPLY [2 votes]: As far as I can tell, this "argument" is not a meaningful derivation of $\mathbf E = -\nabla \Phi$.  In step 4, one seems to assume that $Edx = -d\phi$ which is essentially what one is trying to prove in the first place, so the argument seems circular.
The precise derivation of this fact relies on the crucial fact that the electric field is a conservative vector field which then immediately guarantees the existence of a scalar function $\Phi$ for which $\mathbf E = -\nabla\Phi$.
As for your assertion

if electric field is a constant, electric potential must be a constant too.

Notice that if the electric field is constant in some region then the gradient of $\Phi$ is a constant there.  In particular its partial derivatives satisfy
$$
  \partial_x\Phi = -E_x, \qquad \partial_y\Phi = -E_y, \qquad \partial_z\Phi = -E_z
$$
The $x$ equation gives
$$
  \Phi(x,y,z) = -E_x x + f(y,z)
$$
Then the $y$ equation gives $\partial_yf = -E_y$ which implies $f(y,z) = -E_y y + g(z)$ and finally the $z$ equation gives $\partial_z g = -E_z$ so that $g(z) = -E_z z + c$.  Putting this all together gives
$$
  \Phi(x,y,z) = -\mathbf E \cdot \mathbf x + c
$$
In particular, the electric field being constant does not imply that the electric potential is constant, it means that it has the general form written in this last equation.

REPLY [1 votes]: Since you are a high school student I'm going to make this as simple as possible. This should be read in addition to joshphysics's (correct) answer. The purpose of my own answer is to specifically fill in the steps that the book left out, but which are nevertheless correct.
First, I will take a guess that you have seen basic integral calculus and that your book has already defined the electric potential (in one dimension, for example $x$) in the following way:
$$\int_{x_1}^{x_2}E(x)dx=-\Phi(x_2)+\Phi(x_1).$$
For any well-behaved function
$$\lim_{\Delta a \rightarrow 0}\int_{a}^{a+\Delta a}f(x)dx=\lim_{\Delta a \rightarrow 0}f(a)\Delta a,$$
since we are evaluating the area of one thin rectangle with height $f(a)$ and width $\Delta a$. Anyway, this leads to, when $x_2$ is very close to $x_1$ (so that $x_2 = x_1 + \Delta x$ with $\Delta x$ becoming small):
$$\lim_{\Delta x \rightarrow 0}\int_{x_1}^{x_1+\Delta x}E(x)dx=\lim_{\Delta x \rightarrow 0}E(x_1)\Delta x=\lim_{\Delta x \rightarrow 0}\left(-\Phi(x_1+\Delta x)+\Phi(x_1)\right).$$
Continuing with this last step, we find
$$E(x_1)=\lim_{\Delta x \rightarrow 0}\left(-\frac{\Phi(x_1+\Delta x)-\Phi(x_1)}{\Delta x}\right)$$
or, since $x_1$ was arbitrary,
$$E(x)=\lim_{\Delta x \rightarrow 0}\left(-\frac{\Phi(x+\Delta x)-\Phi(x)}{\Delta x}\right)=-\frac{d\Phi(x)}{dx}.$$
The book is right that this can be extended to the variables $y$ and $z$.


TITLE: Equality in Young's inequality for convolution
QUESTION [10 upvotes]: I am trying to understand how sharp Young's inequality for convolution is. The inequality says $||f \ast g||_r \leq ||f||_p ||g||_q$ where as $1/p+1/q = 1+1/r$.
Actually, there are a couple of papers (for example: Sharpness in Young's inequality for convolution) talking about the case of $p, q>1$, and the answer is that we can find a constant $C<1$ such that $||f \ast g||_r \leq C||f||_p ||g||_q$
However, I believe that when $f\in L^1$ and nonnegative, we will have a sharp $||f \ast g||_p \leq ||f||_1 ||g||_p$. Does anyone know a proof of this?
To be more precise, can we construct a sequence $\{g_n\}$ of $L^p$ functions, such that $||f\ast g_n||_p/||g_n||_p\rightarrow ||f||_1$ as $n\rightarrow \infty$?

REPLY [2 votes]: I don't know if you can construct a sequence as you've proposed above, but I do know that the inequality you proposed is sharp. Proof of this is neatly presented in Becker's "Inequalites in Fourier Analysis'' (1975):
http://www.jstor.org/stable/1970980
The sharp Young's inequality reads:
$$\|f \ast g \|_r \leq \left( A_p A_q A_{r'} \right)^n \|f\|_p\|g\|_q$$
where $A_s = \left( \frac{s^{1/s}}{s'^{1/s'}} \right)$, $\frac{1}{s} + \frac{1}{s'} = 1$, $f$ and $g$ are functions on $n$ dimensions, and $1 \leq p,\,q,\,r\leq \infty$, as usual. In order to show that your inequality is sharp, it's only necessary to note that $A_s A_{s'}=A_1=1$.
This inequality is saturated whenever $f$ and $g$ are both Gaussians, according to the paper.


TITLE: Surface covered by hyperbolic plane admits a hyperbolic metric
QUESTION [0 upvotes]: Let $S$ be a surface. Is it true that if $S$ is covered by the hyperbolic plane (or a subset thereof) then it admits a Riemannian metric of constant negative curvature? How does the metric (or multiple metrics) arise?
Is the converse true? Again, how do we construct the covering(s)?
Relevant references would be much appreciated.

REPLY [3 votes]: The statement is not true. The universal covering of $T^2$ is homeomorphic to $\mathbb R^2$, and $\mathbb R^2$ is homeomorphic to $\mathbb H^2$, so there exists a universal covering map $\mathbb H^2 \to T^2$. But $T^2$ does not have a hyperbolic metric, by the Gauss-Bonnet theorem.
The correct statement is that if there exists a covering map $f : \mathbb H^2 \to S$ such that the deck transformation action of $\pi_1(S)$ on $\mathbb H^2$ is an action by isometries of $\mathbb H^2$ then $S$ admits a Riemannian metric of constant negative curvature.
The proof is to take any open subset $U \subset S$ which is evenly covered by $f$, choose an open subset $\tilde U \subset \mathbb H^2$ such that $f$ maps $\tilde U$ to $U$ by a homeomorphism, and define the Riemannian metric on $U$ as the pushforward via the map $f$ of the Riemannian metric on $\tilde U$. The hypothesis that the deck action is by isometries is needed here to show that the Riemannian metric on $U$ is well-defined independent of the choice of $\tilde U$.
The converse is only true with an additional hypothesis as well, namely that the Riemannian metric on $S$ is geodesically complete. The proof takes some work, but you can find it carefully written up in textbooks on hyperbolic geometry.


TITLE: Hypothesis testing
QUESTION [1 upvotes]: I have been given the data set:
42 36 46 43 41 35 43 45 40 39
The null hypothesis is that $\mu=42$ and alternative hypothesis is that $\mu<42.$
I have found that $s=3.59011, \bar X=41$.
I have then used this to find the test statistic by doing the following:
$$t=\frac{\sqrt{10}(41-42)}{3.59011}=-0.8808$$
Now in order to find the p-value I have found $$\mathbb{P}(T<-0.8808)=\mathbb{P}(T>0.8808)=1-\mathbb{P}(T<0.8808)=1-0.7993325=0.2006675.$$
This all looks correct to me but when I try to find the p-value using R it says that the p-value should be $0.4013$
Any ideas where I'm going wrong?
I am given that we want a significance level, $\alpha=0.05$.
Also, am I right in saying that the critical region  $C=\{T<c^*\}$ where $c^*=1.833113$?
From my p-value I wouldn't reject the null hypothesis as my p-value is greater than 0.05. However, it lies within this region so that would say do reject it. Am I missing something?

REPLY [1 votes]: Your critical region is incorrect.  For a one-sided (left-tailed) test where the alternative hypothesis is that the true mean is less than some value, the critical region would correspond to a $t$-statistic that is less than the lower $100\alpha$ percentile of the student's $t$ distribution with $n-1$ degrees of freedom.  Your critical region is way too big because the critical value you have chosen is the wrong sign:  it should be $-1.833113$.


TITLE: Subset is normal subgroup iff its cosets inherit natural composition
QUESTION [2 upvotes]: Here I use the term coset more loosely to mean the sets obtained by composition with any subset (not necessarily a subgroup).
Let $G$ be a group and $U$ a subset. If $U$ is a normal subgroup then its cosets satisfy $gUhU$=$ghU$. I call this the "natural" composition of cosets (which is well defined for a normal subgroup).
Is the converse statement also true? I.e. if the cosets of a subset, $U$, satisfy $gUhU$=$ghU$ is $U$ necessarily a normal subgroup?
I've already attempted to solve this. It seems that one need only show $uU=U$. After which it is easy to show $U$ partitions $G$ and must therefore be a subgroup. It then follows by the "natural" composition condition that $U$ is normal.
Thanks in advanced for any help.
Addendum:
Here is the full proof:
For infinite groups, this is in general false. Take a submonoid which is not a subgroup of a group (e.g. $(\mathbb{N}_0,+)$ in $(\mathbb{Z},+)$) and verify that it satisfies the natural composition.
For finite groups, this is true. Take a subset, $U$, of a finite group, $G$, which satisfies the natural composition. Since $gUhU$=$ghU$, setting $g=h=e$, one gets $UU=U$ and with this $uU\subseteq{}U$, $u\in{}U$.
Left composition (i.e. $\phi_g:h\mapsto{gh}$) is an isomorphism and, in particular, bijective. This implies $U$ partitions $G$, since for $gU\cap{hU}\neq{\emptyset}$ there exists $u,u'\in{U}$ such that $gu=hu'$ and as such $gU=g(uU)=(gu)U=(hu')U=hU$.
Finally, since $uU=U$, it must be that $e\in{U}$ and, consequently, $U$ contains inverses. Therefore $U$ is a subgroup. To show U is normal, notice that since $e\in{U}$, then $gUg^{-1}\subseteq{gUg^{-1}U}=U$.

REPLY [3 votes]: It does not hold in general. For example, if $G$ is an abelian group, then the defining equation becomes $UU=U$. Just take $U$ to be a sub-monoid that is not a subgroup. (This cannot happen in a finite group.)
(For example, take $G$ to be the integers with addition, and $U$ the non-negative integers.)


text:
\section{Terms in the spatial discretization}\label{appendix_cdomain}
For the first term in (\ref{L_operator}), we have
\begin{align*}
{Q}_l^{2h}({N}_{ll}^{2h}){\bf c} := \left(\begin{array}{c}
({Q}_l^{2h}({N}_{ll}^{2h}){\bf c})_1 \\
({Q}_l^{2h}({N}_{ll}^{2h}){\bf c})_2 \\
({Q}_l^{2h}({N}_{ll}^{2h}){\bf c})_3
\end{array}\right), \quad ({Q}_l^{2h}({N}_{ll}^{2h}){\bf c})_p = \sum_{q = 1}^{3} Q_l^{2h}(N_{ll}^{2h}(p,q)) {c}^{(q)},\quad p = 1,2,3,
\end{align*}
where we have used a matlab notation $N_{ll}^{2h}(p,q)$ to represent the $p$-th row and $q$-th column of the matrix $N_{ll}^{2h}$; $Q_l^{2h}(N_{ll}^{2h}(p,q)){ c}^{(q)}$ is the central difference operator in direction $r^{(l)}$ for spatial second derivative with variable coefficient. For the second term in (\ref{L_operator}), we have
\begin{align*}
\wt{{G}}_3^{2h}({N}_{33}^{2h}){\bf c} := \left(\begin{array}{c}
(\wt{{G}}_3^{2h}({N}_{33}^{2h}){\bf c})_1 \\
(\wt{{G}}_3^{2h}({N}_{33}^{2h}){\bf c})_2 \\
(\wt{{G}}_3^{2h}({N}_{33}^{2h}){\bf c})_3
\end{array}\right), \quad (\wt{{G}}_3^{2h}({N}_{33}^{2h}){\bf c})_p = \sum_{q = 1}^{3} \wt{G}_3^{2h}(N_{33}^{2h}(p,q)) {c}^{(q)},\quad p = 1,2,3,
\end{align*}
where $\wt{G}_3^{2h}(N_{33}^{2h}(p,q)) {c}^{(j)}$ is the second derivative SBP operator  defined in (\ref{sbp_2nd_1}) for direction $r^{(3)}$. For the third term in (\ref{L_operator}), we have
\begin{align*}
{D}_l^{2h}({N}_{lm}^{2h}{D}_m^{2h}{\bf c}) := \left(\begin{array}{c}
(D^{2h}_l(N^{2h}_{lm}D_m^{2h}{\bf c}))_1 \\
(D^{2h}_l(N^{2h}_{lm}D_m^{2h}{\bf c}))_2 \\
(D^{2h}_l(N^{2h}_{lm}D_m^{2h}{\bf c}))_3
\end{array}\right), (D^{2h}_l(N^{2h}_{lm}D_m^{2h}{\bf c}))_p = \sum_{q = 1}^{3} D^{2h}_l(N^{2h}_{lm}(p,q)D_m^{2h}{c}^{(q)}), p = 1,2,3.
\end{align*}
Here, $D_m^{2h}c^{(q)}$ is a central difference operator in direction $r^{(m)}$ for the spatial first derivative, and $D_3^{2h}c^{(q)}$ is the SBP operator defined in (\ref{first_sbp}) for direction $r^{(3)}$.

For the second term in (\ref{Lf_operator}), we have
\begin{align*}
{{G}}_3^{h}({N}_{33}^{h}){\bf f} := \left(\begin{array}{c}
({{G}}_3^{h}({N}_{33}^{h}){\bf f})_1 \\
({{G}}_3^{h}({N}_{33}^{h}){\bf f})_2 \\
({{G}}_3^{h}({N}_{33}^{h}){\bf f})_3
\end{array}\right), \quad ({{G}}_3^{h}({N}_{33}^{h}){\bf f})_p = \sum_{q = 1}^{3} {G}_3^{h}(N_{33}^{h}(p,q)) {f}^{(q)},\quad p = 1,2,3.
\end{align*}
Here, ${G}_3^{h}(N_{33}^{h}(p,q)) {f}^{(q)}$ is the SBP operator defined in (\ref{sbp_2nd_2}) for direction $r^{(3)}$.

For the continuity of traction (\ref{continuous_traction}), we have \[\wt{\mathcal{A}}^{2h}_3{\bf c} = N_{31}^{2h}D_1^{2h}{\bf c}+N_{32}^{2h}D_2^{2h}{\bf c}+N_{33}^{2h}\wt{\mathcal D}_3^{2h}{\bf c},\]
where
\begin{align*}
{N}_{3l}^{2h}D_l^{2h}{\bf c} := \left(\begin{array}{c}
({N}_{3l}^{2h}D_l^{2h}{\bf c})_1 \\
({N}_{3l}^{2h}D_l^{2h}{\bf c})_2 \\
({N}_{3l}^{2h}D_l^{2h}{\bf c})_3
\end{array}\right), \quad ({N}_{3l}^{2h}D_l^{2h}{\bf c})_p = \sum_{q = 1}^{3} N_{3l}^{2h}(p,q)D_l^{2h}{c}^{(q)},\quad l = 1,2, \quad p = 1,2,3
\end{align*}
with $D_l^{2h}{c}^{(q)}$ to be a central difference operator for first spatial derivative in direction $r^{(l)}$, and
\begin{align*}
{N}_{33}^{2h}\wt{\mathcal{D}}_3^{2h}{\bf c} := \left(\begin{array}{c}
({N}_{33}^{2h}\wt{\mathcal{D}}_3^{2h}{\bf c})_1 \\
({N}_{33}^{2h}\wt{\mathcal{D}}_3^{2h}{\bf c})_2 \\
({N}_{33}^{2h}\wt{\mathcal{D}}_3^{2h}{\bf c})_3
\end{array}\right), \quad ({N}_{33}^{2h}\wt{\mathcal{D}}_3^{2h}{\bf c})_p = \sum_{q = 1}^{3} N_{33}^{2h}(p,q)\wt{\mathcal{D}}_3^{2h}{c}^{(q)},\quad p = 1,2,3
\end{align*}
with $\wt{\mathcal{D}}_3^{2h}{c}^{(q)}$ to be the difference operator for first spatial derivative in direction $r^{(3)}$ defined as in the second equation of (\ref{sbp_1st_1}); and
\[\mathcal{A}_3^h{\bf f} = N_{31}^hD_1^h{\bf f}+N_{32}^hD_2^h{\bf f}+N_{33}^h\mathcal{D}_3^h{\bf f},\]
where
\begin{align*}
{N}_{33}^h\mathcal{D}_3^h{\bf f} := \left(\begin{array}{c}
({N}_{33}^h\mathcal{D}_3^h{\bf f})_1 \\
({N}_{33}^h\mathcal{D}_3^h{\bf f})_2 \\
({N}_{33}^h\mathcal{D}_3^h{\bf f})_3
\end{array}\right), \quad ({N}_{33}^h\mathcal{D}_3^h{\bf f})_p = \sum_{q = 1}^{3} N_{33}^h(p,q)\mathcal{D}_3^h{f}^{(q)},\quad p = 1,2,3
\end{align*}
with $\mathcal{D}_3^h{f}^{(q)}$ to be the SBP operator for first spatial derivative in direction $r^{(3)}$ defined as in the first equation of (\ref{sbp_1st_2}). And $N_{3l}^hD_l^h{\bf f}, l=1,2$ are defined similar as those in $\wt{\mathcal{A}}_3^{2h}{\bf c}$.

\section{Bilinear form}\label{appendix_bf}
The term $\mathcal{S}_{2h}({\bf c}_t,{\bf c})$ in \eqref{coarse_simple} is given by
\begin{multline*}
\mathcal{S}_{2h}({\bf c}_t,{\bf c}) = ({D}_1^{2h}{\bf c}_t,{N}_{11}^{2h}{D}_1^{2h}{\bf c})_{2h} +  ({D}_1^{2h}{\bf c}_t,{N}_{12}^{2h}{D}_2^{2h}{\bf c})_{2h} +  ({D}_1^{2h}{\bf c}_t,{N}_{13}^{2h}{D}_3^{2h}{\bf c})_{2h}\\
+  ({D}_2^{2h}{\bf c}_t,{N}_{21}^{2h}{D}_1^{2h}{\bf c})_{2h}
+  ({D}_2^{2h}{\bf c}_t,{N}_{22}^{2h}{D}_2^{2h}{\bf c})_{2h} +  ({D}_2^{2h}{\bf c}_t,{N}_{23}^{2h}{D}_3^{2h}{\bf c})_{2h} \\
+  ({D}_3^{2h}{\bf c}_t,{N}_{31}^{2h}{D}_1^{2h}{\bf c})_{2h}
+  ({D}_3^{2h}{\bf c}_t,{N}_{32}^{2h}{D}_2^{2h}{\bf c})_{2h} +  ({D}_3^{2h}{\bf c}_t,{N}_{33}^{2h}{D}_3^{2h}{\bf c})_{2h}\\
+ ({\bf c}_t, P^{2h}_1(N_{11}^{2h}){\bf c})_{2hr} + ({\bf c}_t, P^{2h}_2(N_{22}^{2h}){\bf c})_{2hr} + ({\bf c}_t, P^{2h}_3(N_{33}^{2h}){\bf c})_{2hr},
\end{multline*}
where $P_3^{2h}(N_{33}^{2h})$ is a positive semi-definite operator defined in \eqref{sbp_2nd_1} for direction $r^{(3)}$; $P_1^{2h}(N_{11}^{2h}), P_2^{2h}(N_{22}^{2h})$ are analogue to $P_3^{2h}(N_{33}^{2h})$.

The term $\mathcal{S}_{h}({\bf f}_t,{\bf f})$ is defined as
\begin{multline*}
\mathcal{S}_{h}({\bf f}_t,{\bf f}) = ({D}_1^{h}{\bf f}_t,{N}_{11}^{h}{D}_1^h{\bf f})_{h} +  ({D}_1^{h}{\bf f}_t,{N}_{12}^{h}{D}_2^h{\bf f})_{h} +  ({D}_1^{h}{\bf f}_t,{N}_{13}^{h}{D}_3^h{\bf f})_{h}\\
+  ({D}_2^{h}{\bf f}_t,{N}_{21}^{h}{D}_1^h{\bf f})_{h}
+  ({D}_2^{h}{\bf f}_t,{N}_{22}^{h}{D}_2^h{\bf f})_{h} +  ({D}_2^{h}{\bf f}_t,{N}_{23}^{h}{D}_3^h{\bf f})_{h} \\
+  ({D}_3^{h}{\bf f}_t,{N}_{31}^{h}{D}_1^h{\bf f})_{h}
+  ({D}_3^{h}{\bf f}_t,{N}_{32}^{h}{D}_2^h{\bf f})_{h} +  ({D}_3^{h}{\bf f}_t,{N}_{33}^{h}{D}_3^h{\bf f})_{h}\\
+ ({\bf f}_t, P^{h}_1(N_{11}^h){\bf f})_{hr} + ({\bf f}_t, P^{h}_2(N_{22}^h){\bf f})_{hr} + ({\bf f}_t, P^{h}_3(N_{33}^h){\bf f})_{hr}.
\end{multline*}
Here, $P_l^h(N_{ll}^h)$ are defined similar as $P_l^{2h}(N_{ll}^{2h})$ in $\mathcal{S}_{2h}({\bf c}_t,{\bf c})$.


TITLE: Matrix factorization as a product of triangular matrices
QUESTION [3 upvotes]: Is it true that any square matrix $A $ can be factorized as a product of only triangular matrices?
That is, can we write $A $ as $\prod_{i=1}^k B_i$, where every $B_i$ is either a lower or an upper triangular matrix (for some natural $ k $)?
Note $ k $ is not assumed to be 2 above. So the question is not (directly) about the $LU$ decomposition.
Comment: We know that for any square matrix $A$ we have: $A=PLU$ where $P$
is a permutation matrix, $L$ is a lower triangular matrix and $U$ is an upper triangular matrix. So the question possibly boils down to whether any permutation matrix can be factorized to triangular matrices.

REPLY [5 votes]: The answer to your question is yes. A permutation matrix is in fact a product of permutation matrices associated to transpositions, which means a matrix obtained from the identity matrix by interchanging two rows. Reduce the problem to this case and notice that this case can be easily deduced from the case of the $2\times 2$ matrix $$\left(\begin{array}10 & 1 \\ 1 & 0\end{array}\right).$$
This matrix can be transformed into the identity matrix by using the following elementary transformations (which correspond to triangular matrices): add the second row to the first, substract the first column from the second, substract the first row from the second, and last multiply the second row by $-1$.
Moreover, in the paper of Nagarajan et al., Products of three triangular matrices, Linear Algebra and its Applications, 292(1999), 61-71 it is proved that any matrix $n\times n$ over a field is a product of at most three triangular matrices.


TITLE: Time-reversed twin paradox
QUESTION [1 upvotes]: This started with wondering about the nature of certain physical quantities under time-reversal - chiefly, that acceleration retains its magnitude and direction at a given time regardless of the 'direction of time' used; this is different to say momentum, which may be reversed under time-reversal (in the sense that we are integrating forward in time from our perspective, along the backward direction in time).
There may be already agreed-upon conventions I'm not aware of regarding which quantities would be reversed, but the essence of the idea is that some quantities or some combinations of quantities need to be reversed, while others (such as acceleration) don't.
With respect to the twin paradox, this got me wondering if it works under non-trivial time reversal regarding the acceleration periods of the paradox. That is, suppose it isn't enough to simply reverse the order of events; if we assume everything runs in reverse, could we start off with two people of different ages, and due to relative reverse motion cause one twin to 'catch up' in 'getting younger' such that at some future (ie their past) they are of the same age?
-PS
To put the question more simply:
Given that acceleration retains direction going forward and backward in time while velocity (or momentum) may not, do the relativistic effects remain the same (and do they make physical sense) from the perspective of a forward-time observer watching events unfold in reverse?
More generally:
By virtue of acceleration having the same magnitude in both directions of time, does it mean it is impossible to discern a direction of time from any measurable acceleration alone? (further questions tempt relevance)

REPLY [0 votes]: You can have a situation where two people start out next to each other with different ages, then move apart and reunite later so that they are the same age when they meet, with the one that started out younger moving inertially between meetings and the one that started out older accelerating during the journey. If they carried clocks that showed, say "100 years minus my current age", then if you played the movie of this backwards, you would have a situation where their clocks initially show the same reading, then both clocks tick "forward" as the movie continues to play backwards, with the inertial twin's clock showing a greater reading when the twins are again next to each other at the end of the time-reversed movie. So just looking at their clocks, this would look just like a movie of the standard twin paradox scenario, and if the movie showed the rate each clock was ticking in some inertial frame at each point in the journey, this rate would be $\sqrt{1 - v^2/c^2}$ slower than a clock at rest in this inertial frame, just like in the standard twin paradox. If the movie didn't show any thermodynamically irreversible processes (or any of the rare particle interactions that violate T-symmetry), there would be no way of knowing you were watching a movie being played backwards.


TITLE: Deterministic Integral of a Predictable Process is Predictable
QUESTION [1 upvotes]: I was reviewing a proof of existence of solutions to stochastic evolution equations which takes the form of a fixed point argument on the space of predictable processes such that
$$
\sup_{t\leq T}\mathbb{E}[\|X(t)\|]<\infty.
$$
This space is certainly Banach under the above norm.  I noticed that in the contraction mapping argument, no one ever seems to comment on the deterministic integral that could appear, of the form
$$
\int_0^t f(s,X(s))ds
$$
for $f$, say, a globally Lipschitz continuous mapping. While this is certainly well defined in the above norm, to fully address the fixed point argument, one would need to know that this process, denoted $Y(t)$, is also predictable.  My question is, is this obvious?  The argument that springs to mind is to approximate it by a left Riemann sum which will certainly be predictable and in this Banach space, and then use the completeness of the space - is that correct? Is there another argument that one would make?

REPLY [2 votes]: I think you only need the Borel measurability of $f$ for the predictability of $Y_t=f(t,X_t)$.
$Y$ can be decomposed into
$$
[0,\infty)\times\Omega\overset{\phi_X}{\rightarrow}[0,\infty)\times\mathbb R
\overset{f}{\rightarrow}\mathbb R,
$$
so predictability follows once the $\mathcal P/\mathcal B([0,\infty)\times\mathbb R)$-measurability of $\phi_X$ is established, where $\phi_X(t,\omega):=(t,X_t(\omega))$. And to establish the last measurability it suffices to consider measurable sets of the form $[0,\tau]\times B$, $\tau\in[0,\infty)$, $B\in\mathcal B(\mathbb R)$, which generate $\mathcal B([0,\infty)\times\mathbb R)\equiv \mathcal B([0,\infty))\otimes\mathcal B(\mathbb R)$. So look at
$$
\{(t,\omega)\in[0,\infty)\times\Omega:
(t,X_t(\omega))\in[0,\tau]\times B
\}
=([0,\tau]\times\Omega)\cap X^{-1}(B).
$$
$X^{-1}(B)$ is in $\mathcal P$ by the assumption $X$ is predictable; and $([0,\tau]\times\Omega)$, too, is in $\mathcal P$ as $1_{t\in[0,\tau]}(t,\omega)$ is an adapted caglad process.


TITLE: A special linear transformation
QUESTION [1 upvotes]: Does there exist infinite dimensional vector space V with a linear transformation on V such that nullityT = rank T = dimV

REPLY [1 votes]: Let $V$ be the real vector spaces of terminal sequences, that is $V=\left\{(a_n)_{n\in \mathbb{N}}\mid \exists M\in \mathbb{N}: a_n=0, \forall n\geq N\right\}$. A basis for space is given by the standard sequences $e_i\in V$, i.e. $(e_i)_j=\delta_{ij}$. Now define a map $T$ by $T(e_{2i+1})=e_{2i+1}$ and $T(e_{2i})=0$. This map $T$ satisfies the claim.
Edit: This is almost the exact same example as Martin Argerami gave you but there is one difference. The vector space of terminal sequences has a countable basis whereas the vector space of bounded sequences has an uncountable basis. This might complicate certain calculations and reasonings as you can not find a basis for the bounded sequences explicitly (it uses the axiom of choice).


TITLE: Non-invertible linear transformation
QUESTION [2 upvotes]: I'm trying to show the composition $S\circ T$ with $T:\mathbb{R}^3 \rightarrow \mathbb{R}^2$ and $S:\mathbb{R}^2\rightarrow \mathbb{R}^3$ is noninvertible. What would be the best way to show this since I don't believe it's sufficient to just say since $S$ and $T$ aren't invertible, $S\circ T$ isn't invertible.

REPLY [1 votes]: $\text{Im}(T)\subset\mathbb{R}^2$ $\Rightarrow$ $\text{rank}(T)\le 2$ $\Rightarrow$ $\text{rank}(S\circ T)\le 2<3$ $\Rightarrow$ not invertible.


TITLE: Problem with an Already Asked Question
QUESTION [1 upvotes]: This question already exists on this site -
Show that if $x,x^{'}\in C$ then $C_x=C_{x^{'}}$..

Let $C$ be a closed convex set in $\Bbb R^2$.
Define $C_x=\{y:x+ty\in C\forall t \geq 0\}$.
Show that if $x,x^{'}\in C$ then $C_x=C_{x^{'}}$.

Can anyone please help me with this? My initial idea was to show that $C_x$ are the connected components, but I am not sure if I am on the right path to solving this problem. A rigorous solution is what I am trying to get at. Thanks for any help.

REPLY [3 votes]: Let  $x+ty\in C$ for every $t\geq0$, let $x'\in C$ and let $t_0>0$.
It is our aim (and that is enough) to prove that $x'+t_0y\in C$, and since $C$ is closed we can do that by finding a sequence in $C$ that converges to $x'+t_0y\in C$.
Since $C$ is convex for every $t>0$ the triangle with vertices $x,x',x+ty$ will be a subset of $C$.
Then $\lambda(x+ty)+(1-\lambda)x'\in C$ for every $\lambda\in[0,1]$.
Now let $t_n\to\infty$ and let $t_0=\lambda_n t_n$.
Then consequently $\lambda_n\to0$ so that: $$\lambda_n(x+t_ny)+(1-\lambda_n)x'=x'+t_0y+\lambda_n(x-x')\to x'+t_0y$$


TITLE: An integral with integration span going to $0$, inside a limit...
QUESTION [0 upvotes]: Let's say I need to calculate this one, it is inside a limit, I saw the result is: $x^2 + o(x^4)$
$ \lim_{x \rightarrow 0} -2\int_{0}^{\ x^{2}} \cos t^{2} \, dt$
Obviously, has to do with McLaurin but...
What I need to do, in this scenario? The stopping degree of the expansion $(x^4)$ has to do with the entire exercise and is not relevant.

REPLY [0 votes]: This one is damn simple. If $x$ is small such that $0< x^{2}<1$ then obviously $0<\cos t^{2}<1$ for $0<t<x^{2}$ and hence we can see that $$0<\int_{0}^{x^{2}}\cos t^{2}\,dt<x^{2}$$ By Squeeze Theorem the integral above tends to $0$ as $x\to 0$ and hence the desired limit is $0$. There is no need to use any Taylor series for cosine function.