text:
\begin{document}

\newcommand{\Ima}{\operatorname{Im}}
\newcommand{\Irr}{\operatorname{Irr}}
\newcommand{\sss}{\mathfrak{s}}
\newcommand{\Cusp}{\operatorname{Cusp}}
\newcommand{\Temp}{\operatorname{Temp}}
\newcommand{\Std}{\operatorname{Std}}
\newcommand{\Cyc}{\operatorname{Cyc}}
\newcommand{\JH}{\operatorname{JH}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\Mult}{\operatorname{Mult}}
\newcommand{\std}[1]{\mathfrak{z}(#1)}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\MS}[1]{\N({#1})}
\newcommand{\id}{\operatorname{id}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\Seg}{\operatorname{Seg}}
\newcommand{\Reps}{\operatorname{Rep}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\supp}{\operatorname{supp}}
\newcommand{\m}{\mathfrak{m}}
\newcommand{\n}{\mathfrak{n}}
\newcommand{\soc}{\operatorname{soc}}
\newcommand{\indu}{\operatorname{Ind}}
\newcommand{\cosoc}{\operatorname{cosoc}}
\newcommand{\lshft}[1]{\overset{\leftarrow}{#1}}
\newcommand{\rshft}[1]{\overset{\rightarrow}{#1}}
\newcommand{\abs}[1]{\left|{#1}\right|}
 \newcommand{\Symm}{\mathcal{S}}

\newcommand{\rest}{\big|}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{question}{Question}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{claim}[theorem]{``Claim''}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{wassumption}[theorem]{Working Assumption}

\newcommand{\Alberto}[1]{{\color{red}{#1}}}
\newcommand{\Max}[1]{{\color{blue}{#1}}}

\title[Cyclic representations of general linear $p$-adic groups]
{Cyclic representations of general linear $p$-adic groups}
\author{Maxim Gurevich}
\address{Department of Mathematics, Technion - Israel Institute of Technology, Haifa, Israel, 3200003.}
\email{maxg@technion.ac.il}

\author{Alberto M\'inguez}
\address{Fakultät für Mathematik, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Wien (Austria).}
\email{alberto.minguez@univie.ac.at}

\date{\today}

\begin{abstract}
Let $\pi_1,\ldots,\pi_k$ be smooth irreducible representations of $p$-adic general linear groups. We prove that the parabolic induction product $\pi_1\times\cdots\times \pi_k$ has a unique irreducible quotient whose Langlands parameter is the sum of the parameters of all factors (cyclicity property), assuming that the same property holds for each of the products $\pi_i\times \pi_j$ ($i<j$), and that for all but at most two representations $\pi_i\times \pi_i$ remains irreducible (square-irreducibility property). Our technique applies the recently devised Kashi\-wara-Kim notion of a normal sequence of modules for quiver Hecke algebras.

Thus, a general cyclicity problem is reduced to the recent Lapid-M\'inguez conjectures on the maximal parabolic case.

\end{abstract}

\maketitle

\section{Introduction}

Parabolic induction is a pivotal part of the smooth representation theory of reductive $p$-adic groups. In this note, we consider the fundamental case of the group $G = \GL_n(F)$, for a non-Archimedean local field $F$. Each Levi subgroup $M<G$ is isomorphic to a product of the form $\GL_{n_1}(F)\times \cdots \times \GL_{n_k}(F)$, with $n_1+\ldots+n_k = n$. An irreducible representation of $M$ takes the form $\pi_1\otimes \cdots\otimes\pi_k$, where each $\pi_i$ is an irreducible $\GL_{n_i}(F)$-representation.

We view parabolic induction as a product operation -- the so-called Bernstein-Zelevinsky product:
\[
\pi_1\times \cdots \times \pi_k : = \indu(\pi_1\otimes\cdots\otimes \pi_k)\;.
\]

While such products are known to be of finite length, information of higher precision on the nature of the resulting product representation remains elusive. One desired goal of the theory would be a satisfactory understanding of the subrepresentations lattice of the induced representation.

In parallel development similar questions have been explored in the setting of representations of quiver Hecke algebras \cite{MR3314831,MR3758148} and of quantum affine algebras \cite{MR3916087}. In fact, when fixing type $A$ Lie data, those settings are closely related to the context of our problems through various known categorial equivalences.

The  Zelevinsky classification (in its dual/Langlands form, see Section \ref{sec:seg}), is a bijection $\m \mapsto L(\m)$ between multisegments -- an essentially combinatorial object -- and irreducible representations of $G$. The representation $L(\m)$ is  defined as the unique quotient (the Langlands quotient) of the \textit{standard} representation attached to $\m$.

A basic property of this classification is that for any multisegments $\m_1, \dots, \m_k$ the representation $L(\m_1+\dots+\m_k)$ occurs with multiplicity one in the Jordan--H\"older sequence of the representation $L(\m_1) \times\dots\times L(\m_k)$.

Therefore it appears natural to ask the following questions:
\begin{enumerate}
  \item When is $L(\m_1+\dots+\m_k)$ a quotient of $L(\m_1) \times\dots\times L(\m_k)$?
  \item When is it the unique irreducible quotient?
\end{enumerate}

This latter property is a particular case of a more general notion of cyclicity, which we import from the quantum affine setting \cite{MR3916087}. We call a (possibly reducible) representation $\pi$ of $G$ \textit{cyclic}, if $\pi$ can be realized as a quotient of a standard representation.

Lapid and the second-named author have stated a series of geometric conjectures \cite{LM-conj   } addressing the two properties from above, in the case of $k=2$.

Meanwhile, in the domain of quiver Hecke algebras, Kashiwara-Kim \cite{MR4016058} introduced the notion of a \textit{normal sequence} of simple modules. Translated to our setting, normal sequences would constitute sequences of certain representations $\pi_1,\ldots,\pi_k$ with the additional assumption that $\pi_i\times \pi_i$ are irreducible (a key condition coined as \textit{square-irreducible} \cite{MR3866895}, or \textit{real} \cite{MR3314831}). Normal sequences possess the property that the product $\pi_1\times \cdots \times \pi_k$ has a unique irreducible quotient.

The prominence of the square-irreducible property has been growing in the domain of $p$-adic groups as well. In fact, the conjectures of \cite{LM-conj} were motivated and proved in certain cases with the additional assumption that at least one the two representations is square-irreducible.

In this note we reduce the above-mentioned questions from the case of $k>2$ to the case of $k=2$, again with an assumption on square-irreducibility: We need to assume it on all factors, but at most two.

Our main theorem, Theorem \ref{thm:main-sqirr}, states that a relative cyclicity condition on a sequence of square-irreducible representations is sufficient to fulfil the requirement for a normal sequence, in the language of \cite{MR4016058}. In particular we obtain in Corollary \ref{cor:main},  a simple proof to the fact that under square-irreducibility assumptions, $\pi_1 \times \cdots\times \pi_k$ is irreducible, if and only if, $\pi_i\times \pi_j$, $i\neq j$ are irreducible.

An attempt to resolve similar questions in the absence of square-irreducibility assumptions is expected to require methods that are different from what is used in this note, and may follow the lines of the mentioned work of Hernandez \cite{MR3916087}. We leave this task for future efforts.

A particular application of that Theorem \ref{thm:main-sqirr} surfaced recently in the work of the first-named author \cite{me-restriction} in the proof of non-tempered Gan-Gross-Prasad branching laws \cite{ggp-non}. The techniques used in that work required some non-trivial categorical equivalences that translate $p$-adic problems into the quantum affine algebras realm. Since all products that appear in that context are built out of square-irreducible representations, our new ``native" $p$-adic proof considerably simplifies the proof of the criterion used in \cite{me-restriction}.

\subsection*{Acknowledgements}

We would like to thank David Hernandez, David Kazhdan, Erez Lapid and Marko Tadi\'c for useful discussions.
We also thank Guy Henniart for pointing out an embarrassing error in a previous version of this note.

The first-named author is partially supported by the Israel Science Foundation (grant No. 737/20). This work was begun while the first-named author was a research fellow at the National University of Singapore, supported by MOE Tier 2 grant 146-000-233-112. The first-named author would like to thank Wee Teck Gan and Lei Zhang for support during that fellowship, and the University of Vienna for their hospitality and support.

\section{Preliminaries}
\subsection{Representation theory of non-Archimedean $\GL_n$}

Let $F$ be a fixed non-Archime\-dean locally compact field of residue characteristic $p$.

For $n\in \mathbb{Z}_{\ge1}$, let $\Reps_n$ denote the abelian category of complex, smooth, finite length representations of the group $G_n:=\GL_n(F)$. Let $\Irr_n$ denote the set of isomorphism classes of irreducible elements in $\Reps_n$. Set  $\Reps=\oplus_{n\ge0}\Reps_n$ and $\Irr=\coprod_{n\ge0}\Irr_n$. Here we treat $\Reps_0$ as the trivial group.

For any $\pi\in \Reps_n$ and any $s\in \mathbb{C}$, we write $\pi(s)$ for the twist of $\pi$ by  $|{\rm det}|^s_{F}$, where  $|\ |_{F}$ is the normalized absolute value on $F$. We denote by $\pi^\vee$ the contragredient (smooth dual) representation of $\pi \in \Reps$.

We will sometimes refer to the underlying complex vector space of a representation $\pi\in \Reps$ by the same notation $\pi$.

Let $\mathcal{R}_n$ be Grothendieck group of $\Reps_n$. We denote by $\pi\mapsto [\pi]$ the natural semi-simplification map $\Reps_n \to \mathcal{R}_n$.
We write $\tau_1\leq \tau_2$ for elements $\tau_1,\tau_2\in \mathcal{R}_n$, if $\tau_2-\tau_1 = [\sigma]$, for a representation $\sigma \in \Reps_n$.

\subsection{Parabolic induction}

For $n\in \mathbb{Z}_{\ge1}$, let $\alpha = (n_1, \ldots, n_r)$ be a composition of $n$. Let $M_\alpha$ be the subgroup of $G_n$ isomorphic to $G_{n_1} \times \cdots \times G_{n_r}$ consisting of matrices which are diagonal by blocks of size $n_1, \ldots, n_r$. Let $P_\alpha$ the subgroup of $G_n$ generated by $M_\alpha$ and the upper
unitriangular matrices. A standard parabolic subgroup of $G_n$ is a subgroup of the form $P_\alpha$ and its standard Levi factor is $M_\alpha$.

For given representations $\pi_i\in \Reps_{n_i}$, $i=1,\ldots,r$, we write
\[
\pi_1\times\cdots\times \pi_r\in \Reps_{n_1+ \ldots +n_r}
\]
to be the representation obtained by normalized parabolic induction (through $P_\alpha$) of the representation $\pi_1\otimes\cdots\otimes \pi_r$ of the group $M_\alpha$, where $\alpha = (n_1,\ldots,n_r)$.

We write $\Cusp$ the subset of $\Irr$ made of cuspidal representations, that is irreducible representations which are not quotients of proper induced representations.

Recall that $\times$ gives an associative product structure on the group $\oplus_{n \ge0} \mathcal{R}_n$. Moreover,

the product is commutative, in the sense that $[\pi_1\times\pi_2] = [\pi_2 \times \pi_1]$, for all $\pi_1, \pi_2 \in \Reps$. In particular, if $\pi_1\times\pi_2 \in \Irr$ then $\pi_1\times\pi_2 \simeq \pi_2 \times \pi_1$.

On the categorical level, the product functor $(\pi_1,\ldots, \pi_1) \mapsto \pi_1\times \cdots\times \pi_r$ is exact in each variable. In particular, when $\tau$ is a subrepresentation of $\pi_1$, $\tau\times \pi_2$ is viewed naturally as a sub-representation of $\pi_1\times \pi_2$.

One symmetry of the categories involved in $\Reps$ is often referred to as the Gelfand-Kazhdan duality \cite{MR0404534}. We will state here one corollary of this symmetry which will be useful for our purposes.

\begin{proposition}\label{prop:GK}
For all $\pi_1,\ldots,\pi_t \in \Irr$, the socle (maximal semisimple subrepresentation) of $\pi_1\times \cdots\times \pi_t$ is isomorphic to the co-socle (maximal semisimple quotient) of $\pi_t\times \cdots\times \pi_1$ .

\end{proposition}

\subsection{Intertwining operators}
We recall here some well known facts about intertwining operators \cite[\textsection IV.1]{MR1989693}.
For $\pi_1,\pi_2\in \Reps$ and $s\in \mathbb{C}$, we write $M_{\pi_1,\pi_2}(s)$ for the standard intertwining operator
\[
M_{\pi_1,\pi_2}(s):\pi_1(s)\times\pi_2\rightarrow\pi_2\times\pi_1(s)\;.
\]

It depends on the choice of a Haar measure, but this dependence will not play a role in our discussion.

For representations $\pi_1,\pi_2\in \Reps$, let $d_{\pi_1,\pi_2}\ge0$ be the order of the pole of $M_{\pi_1,\pi_2}(s)$ at $s=0$ and let
\[
R_{\pi_1,\pi_2}=\lim_{s\rightarrow0}s^{d_{\pi_1,\pi_2}}M_{\pi_1,\pi_2}(s).
\]
Thus, $R_{\pi_1,\pi_2}$ is a non-zero intertwining operator from $\pi_1\times\pi_2$ to $\pi_2\times\pi_1$.

The following properties are known to hold \cite[Lemma 2.3]{MR3866895}\footnote{In parts (6) and (7) of Lemma 2.3 \cite{MR3866895}, one needs to require that $\pi_1$ and $ \pi_2$ are irreducible.}.
\begin{lemma} \label{lem:intert}
Let $0\ne\pi_i\in\Reps(G_{n_i})$, $i=1,2,3$ and let $\tau$ de a subrepresentation of $\pi_1$. Then
\begin{enumerate}
\item\label{part: nonzeroR} The operator $R_{\pi_1,\pi_2}$ restricts to an intertwining operator $\tau\times\pi_2\rightarrow\pi_2\times\tau$. More precisely,
\[
R_{\pi_1,\pi_2}\rest_{\tau\times\pi_2}=\begin{cases}R_{\tau,\pi_2}&\text{if }\tau\ne0\text{ and }d_{\pi_1,\pi_2}=d_{\tau,\pi_2},\\
0&\text{otherwise.}\end{cases}
\]

\item\label{part: ifisom} The inequality $d_{\pi_1\times\pi_2,\pi_3}\le d_{\pi_1,\pi_3}+d_{\pi_2,\pi_3}$ holds, together with the equality
\[
(R_{\pi_1,\pi_3}\times\id_{\pi_2})\circ(\id_{\pi_1}\times R_{\pi_2,\pi_3})=
\begin{cases}R_{\pi_1\times\pi_2,\pi_3}&\text{if }d_{\pi_1\times\pi_2,\pi_3}=d_{\pi_1,\pi_3}+d_{\pi_2,\pi_3},\\0&\text{otherwise.}\end{cases}
\]
Moreover, $d_{\pi_1\times\pi_2,\pi_3}=d_{\pi_1,\pi_3}+d_{\pi_2,\pi_3}$ when at least one of $R_{\pi_i,\pi_3}$, $i=1,2$ is an isomorphism.
\end{enumerate}
\end{lemma}

\section{Cyclicity}\label{sect:cycl}
\subsection{The theory of segments}\label{sec:seg}
Let us briefly recall the Langlands-Zelevinsky theory \cite{MR584084} of the classification of the elements of $\Irr$.

A \emph{segment} is a nonempty finite set of the form
\[
[a,b]_\rho=\{\rho(a),\rho(a+1), \dots,\rho(b)\}
\]
where $\rho \in\Cusp$ and $a \leq b$ are some integers.
For any such $[a,b]_\rho$ we set $L([a,b]_\rho)\in \Irr$ the unique irreducible quotient of:
\[
\rho(a) \times \rho(a+1)\times\dots \times\rho(b).
\]
We say that $[a',b']_{\rho'}$ \emph{precedes} $[a,b]_{\rho}$ if $\rho(b) \notin [a',b']_{\rho'}$, $\rho'(b')  \in[a-1,b-1]_{\rho}$ and
$\rho'(a') \notin [a,b]_{\rho}$.

A \emph{multisegment} is a formal sum $\m= \Delta_1 +\dots+\Delta_N$ of segments. We denote $\Mult$ the set of multisegments. To each multisegment $\m$ we attach a representation $\Sigma(\m)\in \Reps$ in the following way. We choose a sequence of segments $\Delta_1, \dots, \Delta_N$ such that for all $i<j$, $\Delta_i$ does not precede $\Delta_j$  and $\m=\Delta_1 +\dots+\Delta_N$. The sequence $\Delta_1, \dots, \Delta_N$ always exists but is not defined uniquely. However the induced representation
$$\Sigma(\m):= L(\Delta_1)\times\dots\times L(\Delta_N)$$
is uniquely determined by $\m$ and is called the \emph{standard representation} attached to $\m$. We denote $\Std$ the set of standard representations.

For every $\m\in \Mult$, we denote by $L(\m)$ the unique irreducible quotient of $\Sigma(\m)$. The Zelevinsky classification (in its dual form) states that the map $\m \mapsto L(\m)$ is a bijection from $\Mult$ to $\Irr$.

We will also write $\Sigma(\pi):= \Sigma(\m)\in \Std$, when $\pi=L(\m)\in \Irr$.

The sum of multisegments induces a additive structures $\ast$ and $\diamond$ in $\Irr$ and $\Std$, respectively. Precisely, if $\m,\m'\in \Mult$, then $L(\m)\ast L(\m'):=L(\m+\m')$ and $\Sigma(\m)\diamond \Sigma(\m'):=\Sigma(\m+\m')$. We say that $L(\m)\preceq L(\m')$,
when $[L(\m)]\leq [\Sigma(\m')]$ (i.e. the isomorphism class of $L(\m)$ appears as a subquotient in $\Sigma(\m')$). This relation puts a partial order on $\Irr$ \cite[\textsection 7]{MR584084}.

\begin{remark}\label{rem:sum}
\begin{enumerate}
  \item As a consequence of the commutativity of the parabolic induction on the Grothendieck group level, it is easy to see that $[\Sigma_1\diamond \Sigma_2] = [\Sigma_1\times \Sigma_2]$, for all $\Sigma_1,\Sigma_2\in \Std$.

  \item\label{it:sum2}
It is known (see, for example, \cite[Theorem 2.6]{MR3573961}) that $\pi_1\ast \cdots \ast \pi_r$ appears with multiplicity $1$ in the Jordan-H\"{o}lder series of $\pi_1\times\cdots \times \pi_r$, for all $\pi_1,\ldots,\pi_r\in \Irr$. In particular, when $\pi_1\times\cdots \times \pi_r$ is irreducible, we necessarily have $ \pi_1\times\cdots \times \pi_r \cong \pi_1\ast\cdots \ast \pi_r$.

\end{enumerate}
\end{remark}

\subsection{Cyclic representations}
\begin{definition}
We say that a representation $\pi\in \Reps$ is \textit{cyclic}, if there is a standard representation $\Sigma\in \Std$ with a surjective homomorphism $\Sigma \to \pi$.
\end{definition}

Our choice of terminology for this definition is based on the analogous notion in the quantum affine setting \cite{MR3916087}, where cyclic representations are those that are generated by their highest weight vector. In both settings the notion differs from the purely algebraic notion of being generated by a  single vector.

Yet, let us mention that it is known (\cite[Proposition XI.2.6(4)]{MR1721403}) that for cyclic representations in our sense there is indeed a (choice of a) generating vector.

\begin{definition}
We say that a tuple of representation $\pi_1,\ldots,\pi_k \in \Reps$ satisfies $\Cyc(\pi_1,\ldots,\pi_k)$, if $\pi_1\times\cdots\times \pi_k$ is cyclic.

\end{definition}

All irreducible representations in $\Reps$ are cyclic by the Zelevinsky classification. In particular, if $\pi_1\times \cdots \times \pi_k$ is irreducible for $\pi_1,\ldots,\pi_k\in \Irr$, then $\Cyc(\pi_1,\ldots,\pi_k)$ holds. More explicitly, in this case we have a surjection
\[
\Sigma(\pi_1) \diamond\cdots \diamond \Sigma(\pi_k) \to \pi_1 \ast \cdots\ast \pi_k\cong \pi_1\times\cdots \times \pi_k\;.
\]

\begin{proposition}\label{prop:cyclic}
For representations $\pi_1 ,\ldots, \pi_k\in \Irr$, the following are equivalent:
\begin{enumerate}
  \item Property $\Cyc(\pi_1,\ldots,\pi_k)$ holds.\label{it:1}
  \item The product $\pi_1\times\cdots \times \pi_k$ is isomorphic to a quotient of the standard representation $\Sigma(\pi_1) \diamond \cdots \diamond \Sigma(\pi_k)$.\label{it:2}
  \item The representation $\pi_1\times\cdots \times \pi_k$ has a unique irreducible quotient, and that quotient is isomorphic to $\pi_1\ast \cdots\ast \pi_k$.\label{it:3}
\end{enumerate}
\end{proposition}

\begin{proof}

Clearly, \eqref{it:2} implies \eqref{it:1}. The fact that \eqref{it:3} implies \eqref{it:2} was shown in \cite[Lemma 4.2.(5)]{MR3573961}. Let us prove that  \eqref{it:1} implies \eqref{it:3}.

Suppose $\Cyc(\pi_1,\ldots,\pi_k)$ holds.  Then, $\pi_1\times\cdots\times \pi_k$ is a quotient of $\Sigma(\n)\in \Std$, for $\n\in \Mult$. By Remark \ref{rem:sum}, this means that $\pi_1\ast\cdots\ast \pi_k \preceq L(\n)$. On the other hand, since $L(\n)$ is the unique irreducible quotient of $\Sigma(\n)$, we obtain that
\[
[L(\n)] \leq [\pi_1\times\cdots \times \pi_k] \leq [\Sigma(\pi_1)\times \cdots \times \Sigma(\pi_k)] = [\Sigma(\pi_1)\diamond \cdots \diamond \Sigma(\pi_k)] = [\Sigma(\pi_1\ast\cdots\ast \pi_k)]\;,
\]
which implies that $L(\n) \preceq \pi_1\ast\cdots\ast \pi_k$. Hence, $L(\n) = \pi_1\ast\cdots\ast \pi_k$ and so $\pi_1\ast\cdots\ast \pi_k$ is the unique irreducible quotient of $\Sigma(\n)$ and hence of  $\pi_1\times\cdots\times \pi_k$.

\end{proof}
\begin{remark}
For given $\pi,\pi'\in \Irr$, we have therefore $\Cyc(\pi,\pi')$ if and only if ${\rm SSA}(\m,\m')$ in the sense of \cite[Definition 2]{LM-conj}, where $\m$ and $\m'$ are the Zelevinsky multisegments corresponding respectively to $\pi$ and $\pi'$. Through this identification, further aspects of cyclic representations are explored in \cite{LM-conj}.

We prefer our terminology in this setting because of the clear analogy to the quantum affine setting and the work of Hernandez in \cite{MR3916087}.
\end{remark}

\subsection{Cyclic representations and intertwining operators}

\begin{lemma}\label{lem:Rcyclic}
Suppose that $\Cyc(\pi_1,\pi_2)$ holds for $\pi_1,\pi_2\in \Irr$. Then, the image of $R_{\pi_1,\pi_2}$ is an irreducible representation given by $\pi_1\ast \pi_2$.
Moreover, up to a scalar, $R_{\pi_1,\pi_2}$ is the only non-zero intertwining operator from $\pi_1\times \pi_2$ to $\pi_2\times \pi_1$.
\end{lemma}
\begin{proof}

By Proposition \ref{prop:cyclic}, $\pi_1\ast \pi_2$ is the unique irreducible quotient of $\pi_1\times \pi_2$. Through Proposition \ref{prop:GK}, we also know that $\pi_1\ast\pi_2$ is the unique irreducible subrepresentation of $\pi_2\times \pi_1$.

Now, suppose that $T:\pi_1\times \pi_2\to \pi_2\times \pi_1$ is a non-zero intertwining operator. We write $K = \Ima T$. Then, $K$ must have both a unique irreducible quotient (as a quotient of $\pi_1\times \pi_2$) and a unique irreducible subrepresentation (as a subrepresentation of $\pi_2\times\pi_1$). In particular, both the quotient and the sub-representation must be isomorphic to $\pi_1\ast\pi_2$. However, by Remark \ref{rem:sum}\eqref{it:sum2}, $\pi_1\ast\pi_2$ cannot appear in $K$ with multiplicity. Thus, $K\cong \pi_1\ast\pi_2$.

Again, by the same multiplicity-one property, we see that the kernel and (irreducible) image of $T$ are uniquely determined. It follows by Schur's lemma that $T$ is unique, up to a scalar. Since $R_{\pi_1,\pi_2}$ is non-zero the result follows.
\end{proof}

Let  $\pi_1,\ldots,\pi_k\in \Irr$. For a simple transposition $\epsilon_i = (i\,i+1)\in \Symm_k$, we denote:
\[
R^{i}=  \id \times R_{\pi_i,\pi_{i+1}}\times \id
\]
for the operator between
\[
\pi_1\times \cdots \times \pi_{i-1} \times \pi_i\times \pi_{i+1}\times \pi_{i+2}\times \cdots \times \pi_k \;\to\; \pi_1\times \cdots \times \pi_{i-1} \times \pi_{i+1}\times \pi_{i}\times \pi_{i+2}\times \cdots \times \pi_k \;.
\]

\begin{proposition}\label{prop:nontriv-intert}
Suppose that $\pi_1,\ldots,\pi_k\in \Irr$ are representations, for which $\Cyc(\pi_i,\pi_j)$ holds for all $1\leq i< j\leq k$.

Let $\omega = \epsilon_{i_t}\cdots \epsilon_{i_1}\in \Symm_k$ be a permutation given in terms of a reduced decomposition into simple transpositions.

Then, the image of the operator
\[
R: = R^{i_t}\circ \cdots\circ R^{i_1}: \pi_1\times\cdots\times \pi_k \to \pi_{\omega^{-1}(1)}\times\cdots\times \pi_{\omega^{-1}(k)}
\]
contains $\pi_1\ast\cdots\ast \pi_k$ as an irreducible subquotient. In particular, $R$ is non-zero.
\end{proposition}

\begin{proof}
We prove it by induction on the length of $\omega$, that is, $t$.

By the induction hypothesis for $\omega':= \epsilon_{i_t}\omega$, the image $R^{i_{t-1}}\circ \cdots\circ R^{i_1}$ has $\Pi:=\pi_1\ast \cdots\ast \pi_k$ as a subquotient. Thus, it is enough to prove that $\Pi$ does not appear in the kernel of $R^{i_t}$.

By Remark \ref{rem:sum}\eqref{it:sum2}, $\Pi$ appears in $\pi_{\omega'^{-1}(1)}\times\cdots\times \pi_{\omega'^{-1}(k)}$ with multiplicity $1$. Hence, it is enough to show that $\Pi$ appears in the image of $R^{i_t}$. Indeed, since the given decomposition of $\omega$ is reduced, we know that $\omega^{-1}(i_t) < \omega^{-1}(i_{t+1})$ and $\Cyc(\pi_{\omega^{-1}(i_t)},\pi_{\omega^{-1}(i_{t+1})})$ holds. Thus, by Lemma \ref{lem:Rcyclic}, $\Ima R^{i_t}$ is given as
\[
\pi_{\omega^{-1}(1)}\times \cdots \times \pi_{\omega^{-1}(i_t)}\ast \pi_{\omega^{-1}(i_{t+1})} \times\cdots \times \pi_{\omega^{-1}(k)}\;.
\]
In particular, again by Remark \ref{rem:sum}\eqref{it:sum2}, it contains $\Pi$.
\end{proof}

\section{Proof of the main theorem}
Following the terminology of \cite{MR3866895}, we say that $\pi \in \Irr$ is a \textit{square-irreducible} representation, if $\pi\times \pi$ is irreducible.
We recall \cite[Corllary 2.5]{MR3866895} that those representations can be characterized by means of standard intertwining operators: A representation $\pi\in \Irr$ is square-irreducible, if and only if, $R_{\pi,\pi}$, as an intertwining operator from the space of $\pi\times \pi$ to itself, is a scalar operator.

Our main tool for exploiting the property of square-irreducibility will be the following potent lemma that was devised by Kang-Kashiwara-Kim-Oh, and was naturalized in our setting in \cite{MR3866895}. We state a reversed version of it here.

\begin{lemma}\cite[Lemma 3.1]{MR3314831}\cite[Corollary 2.2]{MR3866895}\label{lem:kkko}
Let $\pi_i\in\Reps(G_{n_i})$, $i=1,2,3$.
Let $\sigma$ (resp., $\lambda$) be a subrepresentation of $\pi_1\times\pi_2$ (resp., $\pi_2\times\pi_3$).
Assume that $\pi_1\times\lambda\subset \sigma\times\pi_3$. Then there exists a subrepresentation $\kappa$ of $\pi_2$ such that
$\pi_1\times\kappa\subset \sigma$ and $\lambda\subset\kappa\times\pi_3$.

\end{lemma}

Theorem \ref{thm:main-sqirr} below may be viewed as a corollary of Proposition \ref{prop:nontriv-intert} and the analog of \cite[Lemma 2.6]{MR4016058} or \cite[Proposition 3.2.14]{MR3758148}, when translated to our setting. Since the suitable translation from the representation theory of quiver Hecke algebras is rather involved, we prefer to construct a native proof relying on ideas that were already naturalized in our setting through previous literature.

\begin{theorem}\label{thm:main-sqirr}
Let $\pi_1,\ldots, \pi_n\in \Irr$, such that $\Cyc(\pi_i,\pi_j)$ holds, for all $1\leq i< j\leq n$. Assume that $\pi_1,\ldots, \pi_{n-2}$ are square-irreducible representations.

Then, $\Cyc(\pi_1,\ldots,\pi_n)$ holds as well.
\end{theorem}

\begin{proof}

We reason by induction on $n$. Hence, we assume that $\Cyc(\pi_2,\ldots,\pi_n)$ holds. Let us write $\Pi= \pi_2\times \cdots \times \pi_n$. By Proposition \ref{prop:cyclic}, $\Pi$ has a unique irreducible quotient, which is isomorphic to $\Theta'= \pi_2\ast \cdots \ast \pi_n$.
Let $\eta$ denote the sub-representation of $\Pi$, which is the kernel of $\Pi \to \Theta'$. It is the unique maximal proper sub-representation of $\Pi$.

Again, from Proposition \ref{prop:cyclic}, we know that it is enough to prove that $\pi_1\times \Pi$ has a unique irreducible quotient, which is isomorphic to $\Theta= \pi_1 \ast \Theta'$. In other words, we need to show that any proper subrepresentation $\tau \subset \pi_1\times \Pi$, does not contain $\Theta$ as a subquotient.

Let $\tau \subset \pi_1\times \Pi$ be a proper sub-representation. We consider the intertwining operator
\[
R_{\pi_1,\pi_1\times \Pi}: \pi_1 \times \pi_1 \times \Pi \to \pi_1 \times \Pi \times \pi_1\;.
\]
Restricting to $\tau$, we obtain an operator $\pi_1\times \tau \to \tau \times \pi_1$, by Lemma \ref{lem:intert}\eqref{part: nonzeroR}.

By assumption, $R_{\pi_1,\pi_1}$ is a scalar operator. Hence, by Lemma \ref{lem:intert}\eqref{part: nonzeroR}, $R_{\pi_1,\pi_1\times \Pi} = \lambda( \id_{\pi_1}\times R_{\pi_1,\Pi})$, for a non-zero $\lambda\in \mathbb{C}$. This identity gives us the following inclusion of subrepresentations of $\pi_1\times \Pi \times \pi_1$:
\[
\pi_1 \times R_{\pi_1,\Pi}(\tau) \subset\tau \times \pi_1\;.
\]
At this point, we can apply Lemma \ref{lem:kkko} to obtain a subrepresentation $\kappa \subset \Pi$, such that both inclusions $R_{\pi_1,\Pi}(\tau) \subset \kappa \times  \pi_1$ and $ \pi_1\times \kappa\subset \tau$ hold.

The latter inclusion implies that $\kappa$ is a proper subrepresentation of $\Pi$, hence, $\kappa \subset \eta$. The former inclusion then implies that $R_{\pi_1,\Pi}(\tau) \subset \eta \times  \pi_1$.

Now, recall that $\Theta$ appears in $\Pi \times\pi_1$ with multiplicity one, and that it must also appear in $\Theta' \times \pi_1$. Thus, by exactness of parabolic induction $\eta \times \pi_1$, and its subrepresentation $R_{\pi_1,\Pi}(\tau)$, cannot contain a subquotient isomorphic to $\Theta$.

On the other hand, applying Proposition \ref{prop:nontriv-intert} and Lemma \ref{lem:intert}\eqref{part: nonzeroR}, we see that $R_{\pi_1,\Pi}$ must be a non-zero operator, whose image contains $\Theta$ as a subquotient. Using the multiplicity-one property again, we conclude that $\ker R_{\pi_1,\Pi}$ cannot contain $\Theta$ as a subquotient.

If both $\ker R_{\pi_1,\Pi}$ and $ R_{\pi_1,\Pi}(\tau)$ cannot contain $\Theta$ as a sub-quotient, neither can $\tau$.

\end{proof}

\begin{comment}
\begin{remark}

In the setting of representations of quiver Hecke algebras there is a known property stated in \cite[Proposition 3.2.14]{MR3758148}, which is fully translatable to our setting through the methods exemplified in \cite[Section 2]{MR3866895}. With this view in mind, Theorem \ref{thm:main-sqirr} directly follows from Proposition \ref{prop:nontriv-intert} and the said property. Yet, our preference for the proof above was to give explicit arguments specializing to the case at hand.
\end{remark}
\end{comment}

The following corollary generalizes \cite[Corollary 6.9]{MR3573961}.

\begin{corollary}\label{cor:main}
Let $\pi_1, \dots ,\pi_n \in \Irr$ be given. Assume that all but at most two are square irreducible.
Then, $\pi_i \times \pi_j$ is irreducible for all $1\leq i < j\leq n$, if and only if, $\pi_1  \times \dots \times \pi_n$ is irreducible.
\end{corollary}
\begin{proof}
One direction is obvious by exactness of parabolic induction. Let us prove the converse.
Recall that, for all $i< j$, since $\pi_i\times \pi_j\in \Irr$, we have $\pi_j\times \pi_i\cong \pi_i\times \pi_j$. In particular, we can assume that $\pi_1, \dots, \pi_{n-2}$ are square irreducible and $\Cyc(\pi_i,\pi_j)$ holds, for $i\neq j$. Thus, by Theorem \ref{thm:main-sqirr}, both $\Lambda = \pi_1\times\cdots \times \pi_n$ and $\Lambda'= \pi_1^\vee \times\cdots \times \pi_n^\vee$ are cyclic.

Therefore, $\Pi=\pi_1\ast\cdots \ast \pi_n$ appears as a unique irreducible quotient of  $\Lambda$ and $\Pi^\vee=\pi_1^\vee\ast\cdots \ast \pi_n^\vee$ appears as a unique irreducible quotient of $\Lambda'$. By applying the contragredient functor, we find that $\Pi$ appears also as a unique irreducible subrepresentation of $\Lambda$.
By Remark \ref{rem:sum}\eqref{it:sum2}, this forces $\Lambda$ to be irreducible.

\end{proof}

\bibliographystyle{amsalpha}
\bibliography{../Bibfiles/all,../propo2}

\begin{comment}

\end{comment}

\end{document}


TITLE: Low dimensional topological manifolds
QUESTION [15 upvotes]: There is a well known result that every one dimensional topological manifold without boundary is homeomorphic either to the circle or to the whole real line. However there is one detail hidden: manifold is understood to be second countable (or paracompact). If we drop this assumption it becomes possible to construct different example, so called open long line or Aleksandroff line. It is defined as $\omega_1 \times [0,1) \setminus \{(0,0)\}$ with suitable order topology. What might be surprising, is that replacing $\omega_1$ by bigger ordinal does not produce manifold anymore (this would produce points with uncountable neighbourhood system). There is also a variant of long line "in both directions". So the natural question is: if we drop the assumption for (one dimensional) manifolds to be second countable, is it possible to characterise all of them?$
Edit: what about two dimensional case?

REPLY [16 votes]: The one-dimensional case is well known: you have the circle, the line $\mathbb{R}$, the long line $L$ and the long ray $R$. The proof is not that easy to find in the literature since non-metrizable manifolds are (in my opinion) underestimated. It is described in a previous answer, so let me give a few pointers for the two-dimensional case. Before that, let me stress that there is another hypothesis in the usual definition of manifolds that is often overlooked: being Hausdorff. Non-Hausdorff manifolds are interesting too because they appear naturally, e.g. space of leaves of a foliation. I do not know if anyone has studied non-Hausdorff non-metrizable manifolds. That would really be looking for trouble.
Back to the point. There is very, very little hope to classify non-metrizable surfaces: there are many of them, and of various kind.
First one think about easy examples: product of two one-dimensional non-metrizable manifolds; that makes 4 examples.
But there are more: take the first octant of the product of two long lines (i.e. $\{(x,y)\in R\times R | y \le x \}$). Or glue a bunch of octants together along their edges. This already makes you a (small) bunch of examples. At that point, I should stress that in the product of two long lines, the diagonal is very different from the coordinate axes. Each axis $A$ is homotopic to a copy of $L$ that is disjoint from  $A$, while any embedding of $L$ which is homotopic to the diagonal must meet it on an unbounded set. This comes from the homotopy theory of $L$ and $R$: e.g. there are two homotopy classes of maps $R\to  R$: the ones homotopic to a constant, which are exactly the bounded maps, and the ones homotopic to identity, which have an unbounded set of fixed points.
But there are more: one can produce many different "long pipes", which are obtained as increasing unions of annuli indexed by $\omega_1$, where at each non-limit ordinal the inclusion is as trivial as one might want, but at each limit ordinal the lower annuli can accumulate to a circle with a segment attached, or to something worse. By choosing the shape of such singularities, and at which limit ordinal they do appear gives you a very large range of long pipes.
The good news is that classifying long pipes is sufficient to get a classification of $\omega$-bounded surfaces (i.e. surfaces in which any countable sequence has an accumulation point; e.g. the long line is $\omega$-bounded but the long ray is not). This is thank to the beautiful "bagpipe theorem" of Nyikos (The theory of non-metrizable manifolds, in K. Kunen and J. Vaughan, eds, “Handbook of Set-Theoretic Topology” (Elsevier, 1984), 633–684) which says that any $\omega$-bounded surface is obtained by gluing finitely many long pipes (the pipes, obviously) to a compact surface with some disks removed (the bag). The bad news is that even a classification of long pipes seems out of reach. If I remember well, it is an open question whether every long pipe contains an embedded long line.
The worse news is: but there are more. $\omega$-bounded surfaces are a very particular kind of surfaces. A non-metrizable surface which is very different from everything above is the Prüfer manifold. Basically, you glue a bunch (i.e., one for each real number) of planes to a half plane in a way that maps half infinite strips to cones, so that the different planes do not interfere two much one with the other. This is a huge, weird space.
But I guess that there are more (if I remember well, it has been proved that there are $2^{\aleph_1}$ pairwise non-homeomorphic non-metrizable surfaces, but I do not know in which axiom system it holds).


TITLE: Help understanding the equivalence of these two statements
QUESTION [1 upvotes]: Help understanding the equivalence of these two statements
Let $\Omega $ and $S $ be sets and $Y : \Omega \mapsto S $
$\Sigma $ is a $\sigma $-algebra on $S $
$X: \Omega \mapsto \mathbb R $
Now I have a theorem that says:

$X $ is $\sigma (Y) $-measurable only if
$X = f(Y) $
where $f $ is a $\Sigma $-measurable function from $S $ to $\mathbb R $

[Actually is it if and only if, but the if part is only a trivial result of composition ]
It is claimed that it is sufficient to prove that
$X  \in $b$\sigma (Y) $ if and only if $\exists f \in $b$\Sigma $ such that $X= f(Y) $
I cannot see how this second statement is sufficient for the original claim. (The proof of the second claim is in my book)
(b$\Sigma $ is the set of bounded $\Sigma $-measurable functions)
Thanks in advance!

REPLY [1 votes]: If $X$ is non-negative and $\sigma(Y)$ measurable but not necessarily bounded, take $X_n:=X\chi\{X\leqslant n\}$, which is $\sigma(Y)$ measurable and bounded.
If the theorem holds for measurable bounded functions, then we have $X_n=f_n(Y)$ for some $f_n\colon S\to\mathbb R$ which is bounded and $\Sigma$-measurable (and can be chosen non-negative). Then take $f:=\sup_n f_n$.
If $\omega\in \Omega$ and $X(\omega)\in (k-1,k]$, then $X_n(\omega)=f_n(Y(\omega))=0$ if $n\leqslant k-1$ and $X_n(\omega)=X(\omega)$ otherwise hence $\sup_nf_n(\omega)=X(\omega)$.
The function $f$ is $\Sigma$-measurable as an non-decreasing sequence of such functions.


text:
\vspace{-4mm}
\section{Introduction}
\vspace{-2.5mm}
In modern data-intensive applications like image recognition, conversational AI and recommendation systems, the size of training datasets has grown in such proportions that distributed computing have become an integral part of machine learning. To this end, a fairly common distributed learning framework, namely \emph{data parallelism}, distributes the (huge) data-sets over multiple \emph{worker machines} to exploit the power of parallel computing. In many applications, such as Federated Learning \cite{federated}, data is stored in users' personal devices and judicious exploitation of the on-device machine intelligence can speed up computation. Usually, in a distributed learning framework, computation (such as processing, training) happens in the worker machines and the local results are communicated to a \emph{center machine} (ex., a parameter server). The center machine updates the model parameters by properly aggregating the local results.

Such distributed frameworks face the following two
fundamental challenges: First, the parallelism gains are often bottle-necked by the heavy communication overheads between worker and the center machines. This issue is further exacerbated where large clusters of worker machines are used for modern deep learning applications using models with millions of parameters (NLP models, such as BERT~\cite{devlin2018bert}, may have well over 100 million parameters). Furthermore, in Federated Learning, this uplink cost is tied to the user's upload bandwidth. Second, the worker machines might be susceptible to errors owing to data crashes, software or hardware bugs, stalled computation or even malicious and co-ordinated attacks. This inherent unpredictable (and potentially adversarial) nature of worker machines is typically modeled as Byzantine failures. As shown in \cite{lamport}, Byzantine behavior a single worker machine can be fatal to the learning algorithm.

Both these challenges, communication efficiency and Byzantine-robustness, have been addressed in a significant number of recent works, albeit mostly separately. For communication efficiency, several recent works \cite{atomo,dme,signsgd,vqsgd,qsgd,terngrad,errorfeed} use quantization or sparsification schemes to compress the message sent by the worker machines to the center machine. An  alternative, and perhaps more natural way  to reduce the  communication  cost (via reducing the  number of iterations) is to use second order optimization algorithms;  which  are  known  to  converge  much  faster  than their first order counterparts. Indeed, a handful of algorithms has been developed using this philosophy, such as DANE \cite{dane}, DISCO \cite{disco}, GIANT \cite{giant} , DINGO \cite{dingo}, Newton-MR \cite{newtonmr}, INEXACT DANE and AIDE \cite{aide}. In a recent work \cite{sparsedingo}, second order optimization and compression schemes are used simultaneously for communication efficiency.
On the other hand, the problem of developing Byzantine-robust distributed algorithms has also been considered recently (see  \cite{su,feng,chen,dong,dong1,ghosh2019robust,blanchard2017byzantine} ). However, \emph{all} of these papers analyze different variations of the gradient descent, the standard first order optimization algorithm.

In this work, we propose \textsf{COMRADE}, a distributed approximate Newton-type algorithm that communicates less and is resilient to Byzantine workers. Specifically, we consider a distributed setup with $m$ worker machines and one center machine. The goal is to minimize a regularized convex loss $f: \R^d\to \R$, which is additive over the available data points. Furthermore, we assume that $\alpha$ fraction of the worker machines are Byzantine, where $\alpha \in [0,1/2)$. We assume that Byzantine workers can send any arbitrary values to the center machine. In addition, they may completely know the learning algorithm and are allowed to collude with each other. To the best of our knowledge, this is the first paper that addresses the problem of Byzantine resilience in second order optimization.

In our proposed algorithm, the worker machines communicate \emph{only once} per iteration with the center machine. This is in sharp contrast with the state-of-the-art distributed second order algorithms (like GIANT \cite{giant}, DINGO \cite{dingo}, Determinantal Averaging \cite{deter}), which sequentially estimates functions of local gradients and Hessians and communicate them with the center machine. In this way, they end up communicating twice per iteration with the center machine. We show that this sequential estimation is redundant. Instead, in \textsf{COMRADE}, the worker machines only send a $d$ dimensional vector, the product of the inverse of local Hessian and the local gradient. Via sketching arguments, we show that the empirical mean of the product of local Hessian inverse and local gradient is close to the global Hessian inverse and gradient product, and thus just sending the above-mentioned product is sufficient to ensure convergence. Hence, in this way, we save $\mathcal{O}(d)$ bits of communication per iteration. Furthermore, in Section~\ref{sec:compress}, we argue that, in order to cut down further communication, the worker machines can even compress the local Hessian inverse and gradient product. Specifically, we use a (generic) $\rho$-approximate compressor (\cite{errorfeed}) for this, that encompasses sign-based compressors like QSGD \cite{qsgd} and top$_k$ sparsification \cite{stich2018sparsified}.

For Byzantine resilience, \textsf{COMRADE} employs a simple thresholding policy on the norms of the local Hessian inverse and local gradient product. Note that norm-based thresholding is computationally much simpler in comparison to existing co-ordinate wise median or trimmed mean (\cite{ dong}) algorithms. Since the norm of the Hessian-inverse and gradient product determines the \emph{amount} of movement for Newton-type algorithms, this norm corresponds to a natural metric for identifying and filtering out Byzantine workers.

\vspace{-3mm}
\paragraph{Our Contributions:}
We propose a communication efficient Newton-type algorithm that is robust to Byzantine worker machines. Our proposed algorithm, \textsf{COMRADE} takes as input the local Hessian inverse and gradient product (or a compressed version of it) from the worker machines, and performs a simple thresholding operation on the norm of the said vector to discard $\beta > \alpha$ fraction of workers having largest norm values. We prove the linear-quadratic rate of convergence of our proposed algorithm for strongly convex loss functions. In particular, suppose there are $m$ worker machines, each containing $s$ data points; and let $\mathbf{\Delta}_t = \w_t - \w^*$, where $\w_t$ is the $t$-th iterate of \textsf{COMRADE}, and $\w^*$ is the optimal model we want to estimate. In Theorem 2, we show that

\begin{align*}
\| \mathbf{\Delta}_{t+1}\| \leq \max \{ \Psi^{(1)}_t \| \mathbf{\Delta}_{t}\|, \Psi^{(2)}_t \| \mathbf{\Delta}_{t}\|^2  \}+ (\Psi^{(3)}_t +\alpha) \sqrt{\frac{1}{s}},
\end{align*}
where $\{\Psi^{(i)}_t\}_{i=1}^3$ are quantities dependent on several problem parameters. Notice that the above implies a quadratic rate of convergence when $ \| \mathbf{\Delta}_{t}\| \geq \Psi^{(1)}_t/\Psi^{(2)}_t$. Subsequently, when $\| \mathbf{\Delta}_{t}\|$ becomes sufficiently small, the above condition is violated and the convergence  slows down to a linear rate. The error-floor, which is $\mathcal{O}(1/\sqrt{s})$ comes from the Byzantine resilience subroutine in conjunction with the simultaneous estimation of Hessian and gradient. Furthermore, in Section~\ref{sec:compress}, we consider worker machines compressing the local Hessian inverse and gradient product via a $\rho$-approximate compressor \cite{errorfeed}, and show that the (order-wise) rate of convergence remain unchanged, and the compression factor, $\rho$ affects the constants only.

We experimentally validate our proposed algorithm, \textsf{COMRADE}, with several benchmark data-sets. We consider several types of Byzantine attacks and observe that \textsf{COMRADE} is robust against Byzantine worker machines, yielding better classification accuracy compared to the existing state-of-the-art second order algorithms.

A major technical challenge of this paper is to approximate local gradient and Hessian simultaneously in the presence of Byzantine workers. We use sketching, similar to \cite{giant}, along with the norm based Byzantine resilience technique. Using \emph{incoherence} (defined shortly) of the local Hessian along with concentration results originating from uniform sampling, we obtain the simultaneous gradient and Hessian approximation. Furthermore, ensuring at least one non-Byzantine machine gets trimmed at every iteration of \textsf{COMRADE}, we control the influence of Byzantine workers.

\vspace{-2mm}
\paragraph{Related Work:} \textit{Second order Optimization:} Second order optimization has received a lot of attention in the recent years in the distributed setting owing to its attractive convergence speed. The fundamentals of second order optimization is laid out in \cite{dane}, and an extension with better convergence rates is presented in \cite{aide}. Recently, in GIANT \cite{giant} algorithm, each worker machine computes an approximate Newton direction in each iteration and the center machine averages them to obtain a \emph{globally improved} approximate Newton direction.  Furthermore, DINGO \cite{dingo} generalizes second order optimization beyond convex functions by extending the Newton-MR \cite{newtonmr} algorithm in a distributed setting. Very recently, \cite{deter} proposes Determinantal averaging to correct the inversion bias of the second order optimization. A slightly different line of work (\cite{wangsketched}, \cite{oversketched}, \cite{newtonsketch}) uses Hessian sketching to solve a large-scale distributed learning problems.

\textit{Byzantine Robust Optimization:} In the seminal work of \cite{feng},  a generic framework of one shot median based robust learning has been proposed and analyzed in the distributed setting.  The issue of Byzantine failure is tackled by grouping the servers in batches and computing the median of batched servers in
\cite{chen} (the median of means algorithm). Later in \cite{dong,dong1}, co-ordinate wise median, trimmed mean and iterative filtering based algorithm have been proposed and
optimal statistical error rate is obtained. Also,  \cite{mhamdi2018hidden,Damaskinos} consider adversaries may steer convergence to bad local minimizers for non-convex optimization problems.
Byzantine resilience with gradient quantization has been addressed in the recent works of \cite{anima,ghosh2019communication}.

\paragraph*{Organization:} In Section~\ref{sec:one}, we first analyze \textsf{COMRADE} with \emph{one round} of communication per iteration. We assume $\alpha =0$, and focus on the communication efficiency aspect only. Subsequently, in Section~\ref{sec:byz}, we make $\alpha \neq 0$, thereby addressing communication efficiency and Byzantine resilience simultaneously. Further, in Section~\ref{sec:compress} we augment a compression scheme along with the setting of Section~\ref{sec:byz}. Finally, in Section~\ref{sec:exp}, we validate our theoretical findings with experiments. Proofs of all theoretical results can be found in the supplementary material.

\paragraph*{Notation:} For a positive integer $r$, $[r]$ denotes the set $\{1,2,\ldots,r\}$. For a vector $v$, we use $\|v\|$ to denote the $\ell_2$ norm unless otherwise specified. For a matrix $X$, we denote $\|X\|_{2}$ denotes the operator norm, $\sigma_{max}(X)$ and $\sigma_{min}(X)$ denote the maximum and minimum singular value. Throughout the paper, we use $C,C_1,c,c_1$ to denote positive universal constants, whose value changes with instances.

config: arxiv


TITLE: Why doesn't the energy of an incident photon impact the angle of reflection?
QUESTION [1 upvotes]: Note that I am not asking why the angle of reflection is what it is. That is a different question.
I am asking why the energy of the incident photon does not affect the interaction in question at all, which is not the case for light interacting in other cases, such as Compton Scattering, and when light traverses certain mediums.
It's actually quite strange when you think about it, because even if you view the interaction as the result of a "collision" of sorts between the incident light and the mirror, you'd think, intuitively, that a higher energy light source would have a more pronounced interaction with the surface of the mirror, producing some kind of different behavior, but that's clearly not what happens.
In short, why does the equation of interaction that governs reflection require less information than the equation of interaction that governs light traveling through a prism? Or Compton Scattering?
In all cases, what must be taking place is an exchange of momentum between the photons and some other system, yet in the case of reflection, the total momentum of the photon is irrelevant, whereas in Compton Scattering, the total momentum of the photon is relevant, yet the same physical mechanics must be taking place in each case.
Moreover, in Compton Scattering, the photon loses energy. In reflection, it cannot be the case that any meaningful energy is lost by the photon, otherwise mirrors wouldn't reproduce images accurately.
What is driving this difference in behavior?
It seems that light has three ways of interacting:
Exchanging momentum in a manner in which its total momentum is irrelevant (reflection);
Exchanging momentum in a manner in which its total momentum is relevant, but no energy is lost (refraction); and
Exchanging momentum in a manner in which its total momentum is relevant, and some energy is lost (Compton Scattering).
What I'm looking for is an explanation as to why a photon would require more than one equation of interaction for when it exchanges momentum with another system.

REPLY [0 votes]: You have asked several questions here.
(1)The title question asks about the angle of reflection.
(2) Then you ask why doesn’t the energy of a photon affect the interaction of a reflection?
(3) why do photons in Compton scattering loose energy but not during reflection?
(1) The angle of reflection is not determined by single photons. Billions of photons are absorbed across the surface and  re- emitted in random directions.
(2) The energy of individual photons DOES affect the colors of the reflection.
(3) During reflection photons are absorbed raising the energy levels of electrons. Then new photons are emitted with a frequencies based on those energy levels. During Compton scattering the photons are not absorbed. Instead they barely skip off the edge the electrons and loose some of their energy as their frequencies are slowed down.


TITLE: Cyclics groups and Lagrange Theorem
QUESTION [1 upvotes]: Let $G=\langle y\rangle$ be a cyclic group of order $n$. Prove that $\langle y^k\rangle \subseteq\langle y^m\rangle $ if and only if $\gcd(n,m)$ divides $\gcd(n,k)$.

So I think I was able to prove one direction. I argued that:
Since $<y^k>\subseteq <y^m>$ and $<y^m>$ is a cyclic group, we know that $<y^k>$ is a cyclic subgroup of $<y^m>$. This implies via lagrange theorem that the order of $<y^m>$ must be divisible by the order of $<y^k>$. The order of $<y^m>$ equals $\frac{n}{gcd(n,m)}$ and the order of $<y^k>$ equals $\frac{n}{gcd(n,k)}$. We know that $\frac{|<y^m>|}{|<y^k>|}=\frac{\frac{n}{gcd(n,m)}}{\frac{n}{gcd(n,k)}}=\frac{gcd(n,k)}{gcd(n,m)}$. Hence, gcd(n,m) divides gcd(n,k).
I was having difficulties in trying to prove the other side. Any suggestions or help?
Thank You.

REPLY [1 votes]: The main point is indeed that the order of $y^{k}$, and thus of the subgroup it spans, is
$$
\frac{n}{\gcd(n, k)}.\tag{formula}
$$
Then your statement follows from the fact that $G$ has exactly one subgroup for each divisor of its order, so $$
\langle y^ {k} \rangle \le \langle y^ {m} \rangle \text{ iff } \frac{n}{\gcd(n, k)} \text{ divides } \frac{n}{\gcd(n, m)} \text{ iff } \gcd(n, m) \text{ divides }\gcd(n, k).
$$
To prove (formula), note that if $(y^{k})^{t} = 1$, with $t > 0$, then $n$ divides $kt$, and thus $n/\gcd(n, k)$ divides $t$.


TITLE: Solving $x^2 \equiv 3 \pmod{2003}$
QUESTION [0 upvotes]: Solving $x^2 \equiv 3 \pmod{2003}$

I think it is like solving $x^2 \equiv 2006 \pmod{2003}$ because $2006 \equiv 3 \pmod{2003}$. The possible value for $x$ are from $1$ to $2002$, so I can just insert $x$ to check until I get the right answers, but that only works for small modulo, this modulo is very big, which is impossible to check from $1$ to $2002$. Any hints to solve this equation? Thanks!

REPLY [3 votes]: Parcly has correctly deduced that $3^{501}$ will be a solution, and now we show how this can be reduced by hand. Note that $3^{512} = 6561^{64} \equiv 552^{64} = 204704^{32} \equiv 248^{32} = \dots = 555 \mod 2003.$
Now $3|2004,$ so we obtain $t = 3^{-1} = 2004/3 = 668 \mod 2003.$ Lastly, another round of repeated squaring using $11_{10} = 1011_2$ gives $t^{11} \equiv -524 \mod 2003.$
Thus, at last $3^{501} \equiv 3^{512} \cdot t^{11} \equiv 555 \cdot -524 = -290820 \equiv -385 \mod 2003.$

REPLY [1 votes]: Lucky for you, $2003$ is a prime $\equiv3\bmod4$. If a solution $x$ exists, $x\equiv\pm3^{(2003+1)/4}\bmod2003$. We compute the modular exponent as $385\bmod2003$, which indeed squares to $3\bmod2003$. So $x\equiv\pm385\bmod2003$.


TITLE: Double coset decomposition
QUESTION [0 upvotes]: I came across the following nice isomorphism: consider $G$ a group and let $H, K$ two subgroups then
\begin{equation}
G/H\times G/K \cong \coprod_{H\backslash G/H}G/(H^g\cap K).
\end{equation}
Unfortunately I could not find the proof. I tried to write it down on my own but I have some problem. My first idea was to simply write down two explicit maps which are inverses, but I cannot do that.
From the LHS to the RHS: we start a pair of cosets $(aH, bK)$ and clearly the want to sent it to the component indexed by the double coset $Ha^{-1}bK$, but what should be the coset with respect to $H^{a^{-1}b}\cap K$ individuated by the pair? My problem is that I cannot come up with a formula using $aH$ and $bK$ which well defined.
If I want to define a map in the opposite direction my bet would be sending $xH^{g}\cap K$ to $(gxg^{-1}H, xK)$: it is easy to verify that it does not depend on the choice of the representative $x$ but I cannot prove the same for the representative $g$ of the double coset $HgK$.
Any suggestion is welcomed.

REPLY [1 votes]: Another way of approaching this is using a well-known $G$-equivariant isomorphism
$$
G/H\times X\cong G\times_H X
$$
where $X$ has a left $G$-action and the product on the left has the diagonal action. The isomorphism is given by sending the pair $(gH,x)$ to the equivalence class $[g,g^{-1}x]_H$.
Then working with the rhs, the stabilizer of the equivalence class $[1,xK]_H$ is $H\cap xKx^{-1}$ so its orbit is $G/H\cap xKx^{-1}$.
I think this gives an equivalent description.


TITLE: What is the meaning of $\rho$ and $\sigma$ in the symmetric group?
QUESTION [1 upvotes]: In the symmetric group the elements are given as $\sigma_{1}, \sigma_{2} ,\dots$ and $\rho, \rho^{2},\dots$.
In my notes I am only given what each one is equal to in a certain symmetry group.
Is this standard notation to represent permutations that are ordered in a certain way? If so what does each represent with their given index/power.

REPLY [1 votes]: Geometrically $\rho$ is a rotation, and $\sigma$ is a reflection (from German Spiegelung).
The permutations in $S_3$ correspond to 2 rotations over $120^\circ$ respectively $240^\circ$, 3 reflections, and identity. They are the symmetries of an equilateral triangle.
When we pick $\rho$ to represent either of the rotations (123) or (321), and $\sigma$ to represent one of the reflections (12), (23), or (31), all other permutations can be written as the combination of these 2.


TITLE: Why might this answer to a differential question be false? Is there a more rigorous proof or counterexample?
QUESTION [1 upvotes]: I'm trepidatious to accept an answer here because there's a couple points the author hasn't cleared up
Why doesn't this differential technique work?
$y''/y$ certainly exists if the solution exists wherever $y \neq 0$, and it is integrable.
Secondly, $y''/y = t$ which is an invertible function. In the worst case scenario, suppose we define a new function, the inverse Airy function's derivative over a compact set $Ai'^{-1}(t).$
We can represent $t$ then as $Ai'^{-1}(Ai'(t)) = t$ over varying compact intervals corresponding to the appropriate branch of its inverse, so clearly an antiderivative does exist in terms of $y',$ though it is then still an open-question as to how we derive it.
What are the flaws in our reasonings here?

REPLY [1 votes]: In a nice answer to the post you are referring to it was demonstrated that $y''/y$ is not the first derivative of a function $f(y,y')\,.$ That's the reason we can't separate variables when we solve the ODE $y''=y\,g(x)\,.$
This is maybe not the end of the world. Apparently,
$$
\frac{y''}{y}-\frac{y'^2}{y^2}
$$
is the second derivative of the function $f(y)=\log y\,.$ More generally, for arbitrary twice differentialbe $f\,,$
$$
\frac{d}{dx}f(y)=f'(y)\,y'\,,\quad\frac{d^2}{dx^2}f(y)=f'(y)\,y''+f''(y)\,y'^2\,.
$$
When $f$ is invertible this means that the ODE
\begin{align}\tag{1}
f'(y)\,y'&=g(x)\,,\\[3mm]
\end{align}
has the solution
\begin{align}
\textstyle y=f^{-1}\Big(\int_0^x g(z)\,dz\Big)+\Big(y(0)-f^{-1}(0)\Big)\,.
\end{align}
For the ODE
\begin{align}
f'(y)\,y''+f''(y)\,y'^2&=g(x)\tag{2}
\end{align}
we get first
$$
f'(y)\,y'=\textstyle\int g(x)\,dx=:h(x)
$$
which is an ODE of the form (1) and has a known solution.
I believe the old Book Differntialgeleichungen by E. Kamke (not sure if it was ever translated) is a good reference for such "non ordinary" ODEs.


TITLE: Show that this polynomial (involving n-th roots of unity) has rational coefficients
QUESTION [1 upvotes]: I am tasked with showing that the polynomial $\Phi(x) = \prod_{i=0}^{\phi(n)} (x - \omega_i)$ contains only rational coefficients.
To give you an example, if $n = 10$, the polynomial is just $\Phi(x) = (x - \omega^1)(x - \omega^3)(x - \omega^7)(x - \omega^9)$.
Upon working this out, I do get that the coefficients are rational numbers.
How would I go about proving the general case?
Some things I know are that the n-th cyclotomic extension (the splitting field for $x^n - 1$) has $\phi(n)$ distinct generators when viewed as a multiplicative group.  I'm not sure how that helps though.

REPLY [1 votes]: Suppose we seek to show that
$$\Phi_n(x) =
\prod_{k=1, \; \gcd(k,n)=1}^n (x - \exp(2\pi i k/n))$$
has integer coefficients.
First observe that for $n\ge 2$
$$\sum_{k=1, \; \gcd(k,n)=1}^n k
= \frac{1}{2} \varphi(n) n.$$
This implies that
$$[x^0] \Phi_n(x) = \Phi_n(0)
= (-1)^{\varphi(n)} \exp(2\pi i \times \varphi(n)n/2/n)
\\ = (-1)^{\varphi(n)} \exp(\pi i \times \varphi(n))
= (-1)^{2\varphi(n)} = 1.$$
Observe that
$$x^n - 1 = \prod_{k=1}^n (x - \exp(2\pi i k/n))
= \prod_{d|n} \prod_{k=1, \; (k,n)=d}^n (x - \exp(2\pi i k/n))
\\ = \prod_{d|n}
\prod_{q=1, \; (qd,n)=d}^{n/d} (x - \exp(2\pi i qd/n))
= \prod_{d|n}
\prod_{q=1, \; (q,n/d)=1}^{n/d} (x - \exp(2\pi i q/(n/d)))
\\ = \prod_{d|n} \Phi_{n/d}(x) = \prod_{d|n} \Phi_d(x).$$
We now prove the claim by induction, it holds when $n=1$ where we have
$\Phi_1(x) = x - 1.$ Write
$$x^n - 1 = \Phi_n(x) \prod_{d|n, \; d \lt n} \Phi_d(x)
= \Phi_n(x) g_n(x).$$
Note that the constant coefficient of $g_n(x)$ is
$$[x^0] g_n(x) = \prod_{d|n, \; d \lt n} \Phi_d(0)
= -1 \times \prod_{d|n, \; 1\lt d \lt n} \Phi_d(0)
= -1.$$
Let $\Phi_n(x)  =  \sum_{q=0}^{\varphi(n)} c_q x^q$
and $g_n(x) = \sum_{q=0}^{n-\varphi(n)} a_q x^q$
and suppose  to the contrary  that there is a  non-integer coefficient
$c_k = [x^k] \Phi_n(x)$ in  $\Phi_n(x)$ with $k$ being the smallest to
produce such a  coefficient. Here $k\ge 1$ since  we know the constant
coefficient is an integer.
This would imply
$$[x^k] (x^n-1) = [x^k] \Phi_n(x) g_n(x)
= \sum_{q=0}^{\min(k,\varphi(n))} c_q a_{k-q}.$$
With $k\le \varphi(n)$ by definition we thus have
$$[x^k] (x^n-1)
= \sum_{q=0}^{k} c_q a_{k-q}.$$
The  first $k$ terms  in this  sum are  integers by  construction (the
$c_q$ precede $c_k$ and the  $a_{k-q}$ are integers by induction). The
last term is $c_k [x^0] g_n(x) =  - c_k,$ which is not an integer. The
sum of a  series of integers and a single  non-integer fraction is not
an integer. We now have a contradiction because the coefficient $[x^k]
(x^n-1)$ is always an integer, QED.  (Here some of the $a_{k-q}$ could
potentially  be  zero for  small  $q$ but  this  does  not affect  the
argument.)
Source. This  introductory lecture  / textbook style  proof was
found at the following
Internet link.


TITLE: How can I use set-builder notation for creating lists?
QUESTION [0 upvotes]: I am trying to formalize an algorithm using the set-builder notation.
Having an array B of values $d$:
$$
B = [d_1,d_2, \ldots,d_n]
$$
For instance, I want to define a new list $A$ containing the values $d$ that are greater than a value $h$. The order is important and there could be also values with the same distances. So the following expression using the set-builder notation is wrong:
$$
A = \{\ d_i \ |\ d_i  \in\ B , \ d_i >h \}
$$
Can I use the set-builder notation for creating list of values? So far I though this could be a solution, but I don't know if it is acepted:
$$
A = (\ d_i \ |\ d_i  \in\ B , \ d_i >h )
$$

REPLY [3 votes]: Ultimately notation is not so much about being technically correct, it is about being understood. Set builder notation is so standard, that any mathematically educated person reading it will understand what it means, which makes it a good notation (this is also what makes it meaningful to speak of "correct" and "incorrect" set builder notation).
Since you are not looking to define a set, set builder notation is not really what you are looking for. The question is: how can you succinctly express what you are going for without being confusing?
Your original notation
$$
A = (d_i \mid d_i \in B, d_i > h)
$$
is not standard. However, I would likely understand it if it was clear from context that $A$ should be an array (or sequence) and that the ordering of $A$ matters. Personally I think this notation could be improved by replacing $d_i \in B$ with $1 \leq i \leq n$; because $B = [d_1\ \ldots d_n]$, the fact that $d_i \in B$ is essentially redundant, and anyway $d_i \in B$ is not really standard notation when $B$ is not a set.
An equally formal definition of $A$ would be: "$A$ is the subsequence of $B$ consisting of all entries in $B$ which are larger than $h$". Since there is less possibility of misunderstanding in this English sentence than in the mathematical expression, this is arguably more formal, not less, even though it is written in natural language rather than in mathematical symbols.


TITLE: If $B$ is a small perturbation of positive-definite matrix $A$, then do we have $B>\epsilon A$?
QUESTION [2 upvotes]: Suppose $A=(a_{ij})$ is a (symmetric) positive-definite matrix, and $B$ is another symmetric matrix.

Question: If $B$ is in a small neighborhood $U$ of $A$, then it seems that $B$ should also be positive-definite. Moreover for what value of $\epsilon>0$ we can find a neighborhood $U$ so that $B>\epsilon A$?

If both $A$ and $B$ are diagonal matrices, then this is trivial. But in general since we can only diagonalize one of them and I am afraid there will be some issue.

REPLY [1 votes]: If you consider $\mathbb{R}^{n^2}$, then that does not work because $B$ may be non-symmetric. Thus we assume that $B=A+H$ where the small matrix $H$ goes through the vector space of symmetric matrices.
Let $spectrum(A)=\{\lambda_1\leq\cdots \leq \lambda_n\}$ (note that $\lambda_1>0$). Let $\epsilon\in[0,1)$ and $\alpha >0$ (to be determined). Since the norms are equivalent, we'll use the spectral norm defined, on the symmetric matrices, by $||S||=\rho(S)$ (the spectral radius of $S$).
We assume that $||H||<\alpha$, that implies $x^TBx\geq x^TAx-\alpha$ when $||x||_2^2=1$ (that we suppose in the sequel).
We choose $\alpha<\lambda_1$. Then $x^TBx\geq \lambda_1-\alpha >0$ and $B$ is symmetric$>0$.
Now $x^T(B-\epsilon A)x\geq x^TAx(1-\epsilon)-\alpha\geq \lambda_1(1-\epsilon)-\alpha$.
We choose $\alpha<\lambda_1(1-\epsilon)$. Then $B>\epsilon A$.


TITLE: Let $G$ be a finite group and $K$ a normal subgroup of $G$. Suppose $|K|^2 \nmid |G|$, show $K$ is characteristic subgroup
QUESTION [2 upvotes]: Let $G$ be a finite group and $K$ a normal subgroup of $G$. Suppose $|K|^2 \nmid |G|$ and $K$ is simple, Prove $G$ does not have any subgroup isomorphic to $K$ except $K$. Show $K$ is a characteristic subgroup.

REPLY [3 votes]: Hint: if $H$ and $K$ are normal subgroups then $HK$ is  a normal subgroup and $|HK|=\frac{|H| \cdot |K|}{|H \cap K|}$.


TITLE: The space of distributions endowed with the topology of uniform convergence on bounded sets is not Fréchet.
QUESTION [2 upvotes]: I found a state, that the space of distributions on (here:) $\mathbb{R}^{n}$, which is equipped with the topology of uniformly convergence on bounded subsets is not a Fréchet space. As far as i can remember the topology of uniformly convergence is induced by the uniform norm ; which is translation invariant. So to prove that the space is not Fréchet, i have to figure out, that the space is not locally convex or is not a complete metric space. But i have no idea how to prove this.

REPLY [1 votes]: This is not a separate answer. I only add here the details missing in Jochen's answer. I use here the notation of the post Topology of the Space of Test Functions.
Let $\Omega \subseteq \mathbb{R}^n$ be a non-empty open set, and consider the space of test functions $\mathcal{D}(\Omega)$, and let $\mathcal{D'}(\Omega)$ be the set of all continuous linear functionals on $\mathcal{D}(\Omega)$.
Let denote with $\tau'$ the topology of $\mathcal{D'}(\Omega)$ induced by the system of seminorms $p_B(\Lambda)=\sup \{|\Lambda(\phi)|: \phi \in B \}$, where $B$ is any bounded set of $\mathcal{D}(\Omega)$. With this topology, $\mathcal{D'}(\Omega)$ is a Hausdorff locally convex topological vector space (which is called the strong dual of $\mathcal{D}(\Omega)$ in the language of Bourbaki). Moreover, $\mathcal{D'}(\Omega)$ with the topology $\tau'$ is sequentially complete, as you can prove by using the Banach-Steinhaus theorem (see e.g. Rubin, Functional Analysis, Theorem 6.17) or by noting as Jochen did that $\mathcal{D}(\Omega)$ is bornological (see e.g. Bourbaki, Topological Vector Spaces, III, $\S 2$, Proposition 1 (ii') and then use point (iii') of the same Proposition or directly apply Corollary 1 in III, $\S 3$, Section 8).
Now, we show that $\mathcal{D'}(\Omega)$ with the topology $\tau'$ is not metrizable. First of all, not that if $K$ is a compact subset of $\Omega$ with non-empty interior, then by using the property proved in Smooth Functions with Compact Support, we can easily deduce that no neighborhood of $0$ in the space $\mathcal{D}_K$ is bounded. So by a well known result (see e.g. Rubin, Functional Analysis, Theorem (1.39)), $\mathcal{D}_K$ (which is a Fréchet space) is not normable. Then from the result proved in the post Bounded Sets in Fréchet Spaces (see also Bourbaki, Topological Vector Spaces, III, Exercise $\S 1$ Number 14) we conclude that the canonical bornology of $\mathcal{D}_K$ (that is the collection of all bounded sets of $\mathcal{D}_K$) does not have a countable base. Since the topology $\tau_K$ of $\mathcal{D}_K$ coincides with the topology induced on $\mathcal{D}_K$ by the topology $\tau$ of $\mathcal{D}(\Omega)$, we conclude that the canonical bornology of $\mathcal{D}(\Omega)$ has no countable base.
Now, assume that $\mathcal{D'}(\Omega)$ with the topology $\tau'$ is metrizable. Then it would have a countable local base at $0$. Since the collection of all finite intersections of sets of the form
\begin{equation}
\{ \Lambda \in \mathcal{D'}(\Omega) : p_B(\Lambda) < 1/n \},
\end{equation}
where $B$ is a bounded set of $\mathcal{D}(\Omega)$ and $n$ is any positive integer, is a local base at $0$, we conclude that there exists a sequence $(B_j)_{j=1}^{\infty}$ of bounded subsets of $\mathcal{D}(\Omega)$ such that the collection of all finite intersections of sets of the form
\begin{equation}
W_{B_j,n}= \{ \Lambda \in \mathcal{D'}(\Omega) : p_{B_j}(\Lambda) < 1/n \},
\end{equation}
where $j, n$ are positive integers, is a local base at $0$.  For any positive integer m, let $A_m$ be the closed convex balanced envelope of the bounded set $(m+1)(\cup_{j=1}^{m} B_j) = \{ (m+1) \phi : \phi \in\cup_{j=1}^{m} B_j \} $ . Then every $A_m$ is bounded, since the canonical bornology is adapted (see Bourbaki, Topological Vector Spaces, III, $\S 1$, Section 2). Moreover, since there exists no countable base for the canonical bornology of $\mathcal{D}(\Omega)$, we know there exists a bounded subset $B$ of $\mathcal{D}(\Omega)$ such that $B$ is not contained in $A_m$ for any $m$. So fix a positive integer $m$, and let $\phi_{0} \in B \backslash A_m$. From the Hahn-Banach Theorem (in the form given e.g. in Rudin, Functional Analysis, Theorem 3.7), we know there exists $\Lambda \in \mathcal{D'}(\Omega)$ such that $ | \Lambda(\phi_{0})| > 1$ and $| \Lambda(\phi)| \leq 1$ for all $\phi \in A_m$. We conclude that $\Lambda \notin W_{B,1}$, but $\Lambda \in W_{B_1,m} \cap \dots W_{B_m,m}$. So $W_{B_1,m} \cap \dots W_{B_m,m}$ is not contained in $W_{B,1}$. Since for any positive integers $k, j_1,...,j_k$, if we set $m = \max \{ m, j_1,\dots, j_k \}$, we have
\begin{equation}
W_{B_1,m} \cap \dots W_{B_m,m,} \subseteq W_{B_1,j_1} \cap \dots W_{B_k,j_k},
\end{equation}
we conclude that $W_{B_1,j_1} \cap \dots W_{B_k,j_k}$ is not contained in $W_{B,1}$, against the fact that collection of all finite intersections of sets of the form
\begin{equation}
W_{B_j,n}= \{ \Lambda \in \mathcal{D'}(\Omega) : p_{B_j}(\Lambda) < 1/n \},
\end{equation}
where $j, n$ are positive integers, is a local base at $0$. This concludes the proof.
Let us finally note that the argument we have used to prove that $\mathcal{D'}(\Omega)$ is not metrizable since the canonical bornology of $\mathcal{D}$ has no countable base is completely general and it can be used to prove the following general result.
Theorem
Let $E$ be a Hausdorff locally convex (complex or real) topological vector space, and $E'$ the set of continuous linear functionals on $E$. Let $\tau'$ be the topology on $E'$ induced by the family of seminorms $(p_B)$, where $B$ ranges over all the bounded sets of $E$ and $p_B(\Lambda) = \sup \{ |\Lambda(\phi) | : \phi \in B \}$. Then the space $E'$ with this topology (which is called the strong dual of $E$) is metrizable if and only if the canonical bornology of $E$ has a countable base.
Proof. If the canonical bornology of $E$ has a countable base $(B_j)_{j=1}^{\infty}$, then the topology $\tau'$ is induced by the family of seminorms $(p_{B_j})_{j=1}^{\infty}$, and so it is metrizable. The converse follows from the same argument given above.
QED
This theorem is a special case of Bourbaki, Topological Vector Spaces, III, Exercise $\S 3$ Number 2 (c).
PS For the characterization of the metrizability of the weak dual of $E$ (that is $E'$ considered with the weak*-topology), see my post Metrizability of the Weak Dual.


TITLE: solutions of $a+b=c^2 , a^2+c^2=b^2$ ; $a,b,c$ are natural numbers
QUESTION [9 upvotes]: So it all started with a fun observation, $12+13=5^2$ and these are Pythagorean triplets($5,12,13$), so I thought are there more such numbers?
with brute force I was able to get $(24,25,7)$ and $(40,41,9)$.
Then I was able to find 3 families of solutions.
$(50k^2+50k+12 , 50k^2+50k+13 , 10k+5)$
$(10k+4 , 10k+5 , \sqrt{20k+9})$
$(10k, 10k+1 , \sqrt{20k+1})$
ps: I found these by using the property of Pythagorean triplets that they have at least one multiple of 5 in it.
My question is are there more sets of solution and how do I know I haven't missed any?

REPLY [2 votes]: $a^2 + c^2 = b^2$
$c^2 = b^2 - a^2 = (b-a)(a+b)$ but $a+b = c^2$ so if we assume $a+b \ne 0$, we have $b-a = 1$ and $b = a+1$ and we have
$a^2 + c^2 = (a+1)^2$ and $2a + 1 = c^2$
If we replace $c^2$ with $2a+1$ we have $a^2 + 2a + 1 = (a+1)^2$ which is always true.  So $2a+1=c^2$ can be any number that is both; an odd number at least equal to $3$ ($a \ge 1$); and a perfect square, and $c=\sqrt {2a+1}$ is a square root of an odd perfect square greater than $3$ which can be any odd integer greater than $1$.
So for any $k \in \mathbb N$ we can have $c = 2k +1$, $a=  \frac {c^2 -1}2= 2k(k+1)$  and $b = \frac {c^2  +1}2 = 2k^2 + 2k + 1$.
Those are all of them.
If $k\equiv 0,4 \pmod 5$ then $a\equiv 0 \pmod 5$.  If $k\equiv 1,3\pmod 5$ then $b\equiv 0 \pmod 5$ and if $k \equiv 2\pmod 5$ then $c \equiv 0 \pmod 5$.


TITLE: Olympiad question: How many permutations with no fixed letters does BHARAT have?
QUESTION [0 upvotes]: We will say that a rearrangement of the letters of a word has no fixed letters if, when the rearrangement is placed directly below the word, no column has the same letter repeated.  For instance, HBRATA is a rearrangement with no fixed letters of BHARAT.  How many distinguishable rearrangements with no fixed letters does BHARAT have?  (The two As are considered identical.)

A p&c question is given with its solution which was asked in mathematics olympiad , but the solution is very tricky to understand so how will we understand the solution ?

REPLY [0 votes]: There are $\binom4 2$  ways = $6$ ways in which the two $A's$ are out of position.
The remaining $4$ distinct letters with $2$ of them (call them $X$ and $Y$) "in position"
We now apply inclusion-exclusion, to find total permutations minus those with at least $X$ still in position minus at least $Y$ still in position plus both $X$ and $Y$ still in position (because we subtracted such cases twice), thus
$4!-3!-3!+2! = 14$ and multiply by $6$


TITLE: What type of number is the next expression?
QUESTION [0 upvotes]: Which is the result for:
$\sqrt{3-\sqrt{5}+\sqrt{{9-4\sqrt{5}}}}$?
It is a natural number?

REPLY [5 votes]: HINT : $$9-4\sqrt 5=9-2\sqrt{20}=5+4-2\sqrt{5\cdot 4}=(\sqrt 5-\sqrt 4)^2.$$


TITLE: How to find a primitive root modulo $5^{10}$?
QUESTION [2 upvotes]: I know how to find primitive roots of relatively small primes. But how can one possibly find a primitive root modulo $5^{10}$? I can't test every single number less than $5^{10}$. Is there a fast way to locate just one primitive root of $5^{10}$?

REPLY [5 votes]: Find a primitive root mod $5$. I notice $3$ is a primitive root mod $5$.

Either $3$ or $3 + 5 = 8$ will be a primitive root mod $25$. A quick check shows that $3$ is still a primitive root mod $25$.

A primitive root mod $25$ will be a primitive root mod $5^k$ for all $k \geq 1$.

This works because of a few fundamental ideas concerning primitive roots.

Lemma: If $g$ is a primitive root mod an odd prime $p$, then either $g$ or $g + p$ is a primitive root mod $p^2$.
Proof: This is the theorem in this answer, although the phrasing is a little bit different.

And also,

Lemma: If $g$ is a primitive root mod $p^2$ where $p$ is an odd prime, then $g$ is a primitive root mod $p^k$ for all $k \geq 1$.
Proof: See this question and its answers.


TITLE: Temperature relation to Archimedes principle
QUESTION [1 upvotes]: I have a probably very simple problem which I cant solve. I am weighing animals in seawater by placing them on a small PVC arm that is fixed on a balance and reaches into a beaker of seawater. On the arm, I place an organism and measure the specific weight of the animal. Now, the weight of the animal changes a lot between days which cannot be explained by physiological processes. I believe this might be due to the water temperature which I also collect alongside. Can anybody tell me how to correct for water temperature if I dont know the volume of the organism?
Sample data:

REPLY [0 votes]: It is highly unlikely the differences you are seeing are due to temperature unless this is occuring outdoors.
As you can see on this page, the density of water changes less than 1% between -20 and +20 C. If you are indoors, it is highly unlikely it's changing outside +15 to +25, which would be much less than 1%.
Even outdoors, even day/night changes would be unlikely to have a measurable effect, and a full winter/summer change would only be 2 or 3%.
What sort of differences are you actually measuring?


TITLE: How is Bayes' theorm different from the theorem of conditional probability?
QUESTION [0 upvotes]: The theorem of conditional  probability states that
$$P(A \mid B)=\frac{P(A \cap B)}{P(B)}$$
Bayes' theorem on the other hand tells us the probability that a prior condition is true if a given event has taken place is
$$P(B \mid A)= \frac{P(B \cap A)}{P(A\mid B)P(B)+P(A\mid B^C)P(B^C),
}$$
However, what I'm unable to understand is why it's not simply not
$$\frac{P(B \cap A)}{P(A)}$$

REPLY [2 votes]: Everything you write is equivalent. Bayes' theorem can be proved as follows:
$$
P(B\mid A)=\frac{P(A\cap B)}{P(A)}=\frac{P(A\mid B)P(B)}{P(A)},
$$
where in the second line we used that
$$
P(A\mid B)=\frac{P(A\cap B)}{P(B)}\implies P(A\cap B)=P(A\mid B)P(B).
$$
For the expression you give for Bayes', it is just a rewriting with the law of total probability:
$$
P(A)=P(A\mid B)P(B)+P(A\mid B^C)P(B^C).
$$


TITLE: Numerically Integrate Matrix Equation in Matlab / Octave
QUESTION [1 upvotes]: How do I integrate a matrix numerically in Octave / Matlab?
I am trying to do the following integration numerically in Matlab
$\int_a^b T(x)^{-1} B dx$
where $T(x)$ returns an 8x8 matrix. The vector B is a constant.
B = [0 0 0 0 -2*pi*r*fz -2*pi*r*ft -2*pi*r*fr 0]';
a = 5;
b = 20;

function y = f(x, a, B)
   y = T(a,x)^(-1)*B
endfunction

[q, ier, nfun, err] = quad(@(x) f(x,a,B), a, b)

I can see that y is being calculated as a 8x1 vector but q is returned as a scalar value.
Is there a suggested way for integrating an array in Octave or Matlab?

REPLY [0 votes]: You essentially have eight independent quadrature problems (the rows of T). You have several options. Since you didn't provide runnable code, some of the code below may need to be tweaked. And if other issues crop up you'll have to deal with those.
1.
Break up the problem and iterate over the rows using a for loop and quad (you might also try quadgk which performs better in many cases):
function y = f1(x,idx,a,B)
    % Integration function
    Tinv = T(a,x)^-1;
    y = Tinv(idx,:)*B; % Extract row
end

...
B = [0 0 0 0 -2*pi*r*fz -2*pi*r*ft -2*pi*r*fr 0]';
a = 5; b = 20;
fun = @(x,idx)f1(x,idx,a,B); % Anonymous function, pass a and B as parameters
q = zeros(8,1)
for i = 1:8
    % Iterate quadrature over each row
    [q(i),ier,nfun,err] = quad(@(x)fun(x,i), a, b);
end

2.
Use vectorized quadrature via the quadv function:
function y = f2(x,a,B)
    % Integration function
    y = T(a,x)^-1*B;
end

...
B = [0 0 0 0 -2*pi*r*fz -2*pi*r*ft -2*pi*r*fr 0]';
a = 5; b = 20;
fun = @(x)f2(x,a,B); % Anonymous function, pass a and B as parameters
[q,nfun] = quadv(fun, a, b);

Note that the Matlab quadv function is scheduled to be removed in a future release.
3.
Use Matlab and the newer integral function (uses adaptive Gauss-Kronrod quadrature like quadgk) with the 'ArrayValued' option:
...
B = [0 0 0 0 -2*pi*r*fz -2*pi*r*ft -2*pi*r*fr 0]';
a = 5; b = 20;
fun = @(x)f2(x,a,B); % Anonymous function, pass a and B as parameters
q = integral(fun, a, b, 'ArrayValued', true);

One final thing. Do you really need to be calculating an explicit inverse of a matrix? This is very rarely necessary. It leads to less numerical precision and, in some cases, numerical instability. You might look at you can modify your problem to use typical linear solution methods, e.g., \ (mldivide) or linsolve.


TITLE: Is it in NP to check if the convex hull contains the unit ball?
QUESTION [10 upvotes]: Given a set of $n$ points in $d$ dimensional Euclidean space, the problem is to determine if the convex hull contains the unit ball centered at the origin.

Is this problem in NP?

It is in co-NP as one can give a point in the ball outside the convex hull as a witness and verify this fact using linear programming.
My focus here is not in computer precision relating to square roots although this may also be interesting.
(Related to https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)

REPLY [7 votes]: The problem is NP-hard; see my answer at mathoverflow. Thus there is no polynomial-size certificate that the unit ball is contained in the convex hull of given points unless $\text{NP} = \text{co-NP}$ (if $\text{NP} = \text{co-NP}$ then the polynomial hierarchy collapses).


TITLE: Why is the Poynting Vector Symmetric in E and H?
QUESTION [7 upvotes]: Why is the Poynting Vector symmetric in E and H? I always thought that E and B were the analogous fields, so I would think that any equation using magnetic and electric fields should be symmetric in E/B or D/H. I've seen the derivation, but I have yet to find the point where my want for symmetry is being broken.

REPLY [1 votes]: The electromagnetic stress-energy tensor is
$$T^{\mu\nu} = \frac{1}{\mu_0} \left[ F^{\mu \alpha}F^\nu{}_{\alpha} - \frac{1}{4} \eta^{\mu\nu}F_{\alpha\beta} F^{\alpha\beta}\right]\text{.}$$
Its terms are antisymmetric, e.g.,:
$$\begin{eqnarray*}
T_0{}^0 &=& -\frac{1}{2}\left[\epsilon_0 E^2 + \frac{1}{\mu_0}B^2\right]\text{,}\\
T_a{}^0 &=& \epsilon_0\left[\mathbf{E}\times\mathbf{B}\right]\text{,}\\
T_0{}^a &=& \frac{1}{\mu_0}\left[\mathbf{B}\times\mathbf{E}\right]\text{.}
\end{eqnarray*}$$
However, if one applies the following definitions of the auxilary fields $\mathbf{D}$, $\mathbf{H}$ (thus there is no need to assume a linear dielectric, etc.):
$$\begin{eqnarray*}
\epsilon_0\mathbf{E} = \mathbf{D}-\mathbf{P},&\quad&\frac{1}{\mu_0}\mathbf{B} = \mathbf{H} + \mathbf{M}
\end{eqnarray*}$$
to separate free and bound charges, the stress-energy tensor decomposes into (the first and second square-bracketed terms correspond to the free and bound terms, respectively):
$$\begin{eqnarray*}
-T_0{}^0 &=& \frac{1}{2}\left[\mathbf{E}\cdot\mathbf{D} + \mathbf{B}\cdot\mathbf{H}\right] + \frac{1}{2}\left[-\mathbf{E}\cdot\mathbf{P}+\mathbf{B}\cdot\mathbf{M}\right]\text{,}\\
+T_a{}^0 &=& \left[\mathbf{D}\times\mathbf{B}\right] + \left[-\mathbf{P}\times\mathbf{B}\right]\text{,}\\
-T_0{}^a &=& \left[\mathbf{E}\times\mathbf{H}\right] + \left[\mathbf{E}\times\mathbf{M}\right]\text{,}
\end{eqnarray*}$$
as well as a more complicated "Maxwell stress" terms in the space-space components.
Thus, fundamentally situation is (anti)symmetric, but the apparent break is due to a conventional decomposition to free and bound charges. In terms of the full stress-tensor tensor, $\mathbf{D}\times\mathbf{B}$ is part of the field momentum density, while $\mathbf{E}\times\mathbf{H}$ is part of energy flux density. The latter is the standard Poynting vector, but because of antisymmetry, the choice of which to use is actually arbitrary, so long as it's consistently applied.


TITLE: Synthesizing a Polynomial of least degree with integer coefficients that has $5-2i$, $\sqrt{3}$, $0$, and $-1$ as zeros.
QUESTION [1 upvotes]: I have been struggling to create a polynomial that adheres to the following guidelines and I am hoping someone can help me out. I have a series of questions regarding the polynomial and I am struggling to get past the first step, creating the polynomial itself.

Create a polynomial in standard form of least degree with integer coefficients that has 5 – 2i, √3, 0, and -1 as zeros. Show your work.
Check that your answer is correct by using division. Show your work, and make it clear and organized.
Show that 1 is not a zero of the polynomial
What is the end behavior of your polynomial?
How many real zeros, irrational zeros, and imaginary zeros does it have, respectively?
What is the degree of your polynomial?
Use your calculator to determine the

a. Relative maxima
b. Relative minima
c. Intervals over which the polynomial is increasing
d. Intervals over which the polynomial is decreasing

Does your polynomial have an absolute maximum? If so, what is it?
Does your polynomial have an absolute minimum? If so, what is it?

REPLY [1 votes]: Conjugate Theorem: Given a root of the polynomial $f(x)$ is $x=a-bi$, another root is its conjugate: $\overline{a-bi}=a+bi$.
Irrational Root Theorem: Given an irrational root say, $x=a+b\sqrt{c}$, another root will be $x=a-b\sqrt{c}$.

With that in mind, let's construct our polynomial. We can build our polynomial by starting with its roots in expanded form, and multiplying everything out at the end.

For $5-2i$:

By the conjugate theorem, $5+2i$ is another root. Hence, we have a quadratic$$(x-(5-2i))(x-(5+2i))=\color{red}{x^2-10x+29}\tag1$$

For $\sqrt3$:

And by the irrational root theorem, we have $x=-\sqrt3$ as a root. Hence, its minimal polynomial is $\color{blue}{x^2-3}$.

Thus, our polynomial is$$\begin{align*}f(x) & =x(x+1)(\color{red}{x^2-10x+29})(\color{blue}{x^2-3})\tag2\\ & =x^6-9x^5+16x^4+56x^3-57x^2-87x\tag3\end{align*}$$
I'll let you solve the rest of the problems. If you need help with any of them, ask me and I'll reply with a hint.


TITLE: Why the dramatic difference in the arc tangent?
QUESTION [1 upvotes]: Why are the two following calculations so dramatically different in results?
Given ATAN(y2 - y1 / x2 - x1)
Atan(165.377838 - 240 / 57.234100 - 160) = 0.8696708890423176

Atan(159.340393 - 240 / 61.901459 - 160) = -1.3538428308947705

I am calculating all of the points on a circle, and when I reach from approximately 45 to 135 degrees, rotating counterclockwise, all of my results go from positive to negative, and giving me sparatic results, such as above.  The result of the arctangent, every where else in the rotation, is around a 1.43 to 1.53, but in this area they go negative and drop full integer.
Any ideas why this is happening?

REPLY [0 votes]: Take a look at a plot of the tangent function, e.g. http://commons.wikimedia.org/wiki/File:Tangent-plot.svg.
Here's a definition of tangent tan(x) = sin(x)/cos(x). For each x with cos(x)=0: tan(x) is undefined. That happens each half circle (180° or pi which is about 3.14159265).
Arctangent is supposed to revert this strange thing. It's plot looks like this:
http://en.wikipedia.org/wiki/File:Arctangent_Arccotangent.svg
Your formulas can be resolved to atan(1.18453366) and atan(-4.53673694), because of the missing parentheses. Taking a look at the plot of arctangent again, I'd say, you got exactly what you asked for. You provided values differing by about 5.5. A difference of about 1.5 isn't as dramatic.
You can go with the correct parentheses set by Shaun Ault. However you have to expect atan to "jump" from -pi/2 to pi/2 (by about 3.14159265) and back for x2-x1 "swinging" around 0. That's the way atan works. Look at the plot and keep in mind 1/0is undefined for mathematicians or +/-infinity for engineers. So for "anything / something close to zero" you can go from the far left side of the plot directly to the far right.
The solution may be in the comment by J.M.

Actually, if he's doing what I think he's doing, the two-argument arctangent might be a better thing to use: atan2(y2 - y1, x2 - x1)

Here's the definition:
http://en.wikipedia.org/wiki/Atan2#Definition_and_computation


TITLE: Is there an intuitive explanation for Fermat's Last Theorem?
QUESTION [2 upvotes]: Does a heuristic explanation exist why $x^n+y^n=z^n \;\forall x,y,n,z\in \mathbb{Z},n>2$ doesn't have any solutions?
I'm not asking for an elementary proof or for an explanation of Wile's proof but maybe there is some kind of intuitive reasoning why the proposition should be true. Why did Fermat and many other mathematicians think that it was true? Did they just try a lot of different values?

REPLY [1 votes]: I don't know whether the early pioneers have thought this way, but they might have.
If you write $ x^n - z^n = w $ and look at the prime-factorization of $w$ then you can use Fermat's little theorem to deduce that the exponents of the primefactors of $w$ grow only logarithmically with $n$. So it is very unlikely, that for larger $n$ we could have $w = p^n \cdot q^n \cdot \ldots \cdot u^n $ where $p \ldots u$ are the primefactors of $w$ - and this might have been very obvious to Fermat himself and also to Euler, who had analyzed this so-called "cyclotomic expression"s on the lhs and had generalized Fermat's little theorem to his "totient"-formula.
So ... this might have been a heuristic evidence for them pioneers ...