text:
\begin{document}
\title{Adaptive SOR methods based on the Wolfe conditions}
\author{
Yuto Miyatake\thanks{Cybermedia Center, Osaka University,
			1-32 Machikaneyama, Toyonaka, Osaka 560-0043, Japan,
\href{mailto:miyatake@cas.cmc.osaka-u.ac.jp}{miyatake@cas.cmc.osaka-u.ac.jp}} ,\
Tomohiro Sogabe\thanks{Department of Applied Physics,
              Graduate School of Engineering,
              Nagoya University,  Furo-cho, Chikusa-ku,
              464-8603 Nagoya, Japan,
\href{mailto:sogabe@na.nuap.nagoya-u.ac.jp}{sogabe@na.nuap.nagoya-u.ac.jp}}
\ and
Shao-Liang Zhang\thanks{Department of Applied Physics,
              Graduate School of Engineering,
              Nagoya University,  Furo-cho, Chikusa-ku,
              464-8603 Nagoya, Japan,
\href{mailto:zhang@na.nuap.nagoya-u.ac.jp}{zhang@na.nuap.nagoya-u.ac.jp}}
}

\maketitle

\begin{abstract}
Because the expense of estimating the optimal value of the relaxation parameter in the successive over-relaxation (SOR) method
is usually prohibitive, the parameter is often adaptively controlled.
In this paper, new adaptive SOR methods are presented that
are applicable to a variety of symmetric positive definite linear systems and do not require additional matrix-vector products when updating the parameter.
To this end, we regard the SOR method as an algorithm for minimising a certain objective function, which yields an interpretation of the relaxation parameter as the step size
following a certain change of variables.
This interpretation enables us to adaptively control the step size based on some line search techniques,
such as the  Wolfe conditions.
Numerical examples demonstrate the favourable behaviour of the proposed methods.
\end{abstract}

\section{Introduction}
\label{sec1}
The successive over-relaxation (SOR) method is
one of the most well-known stationary iterative methods for solving linear systems
\begin{align}
A\bx = \bb ,
\end{align}
where $A \in \bbR^{n\times n}$ and $ \bb \in \bbR^{n}$ are given nonsingular matrix and
vector, respectively.
The SOR method is formulated as
\begin{align}
\bx^{(k+1)} = \Go \bx^{(k)} + \co, \quad k = 0,1,2,\dots,
\end{align}
where
\begin{align}
\Go &= (D+\omega L )^{-1} [ (1-\omega) D - \omega U], \\
\co &= \omega (D+\omega L)^{-1} \bb.
\end{align}
Here, the matrix $A$ is expressed as the matrix sum
\begin{align}
A = D+L+U,
\end{align}
where $D = \diag (a_{11}, a_{22},\dots, a_{nn})$, and $L$ and $U$ are
strictly lower and upper triangular $n\times n $ matrices.

The convergence performance of the SOR method depends on the relaxation parameter $\omega$.
A necessary condition for the SOR method to converge is that $\omega \in (0,2)$,
and this condition is also sufficient for a symmetric positive definite matrix $A$
(for further details of SOR theory see, e.g.,~\cite{ha00,va00}).
The relaxation parameter $\omega$
is ideally chosen such that the spectral radius of the iteration matrix $\Go$ is
as small as possible.
However, the optimal value is rarely available except in some
special cases, such as consistently ordered $p$-cyclic matrices~\cite{va00}.
Thus, in practice a specific value obtained either empirically or heuristically is
often used.
A typical example is $\omega = 2-O(\tilde{h})$, where $\tilde{h}$
is the mesh spacing of the
discretisation of the underlying physical domain.
An alternative approach is to adaptively control the relaxation parameter.
This approach is referred to as an adaptive SOR method.

In this paper, we are concerned with adaptive SOR methods.
To explain our motivation, we first review two standard approaches and their features.
One is to approximate the spectral radius of $\Go$ using the information obtained during iterations~\cite{hy81}.
This approach is based on the observation that
for a consistently ordered coefficient matrix with some additional assumptions,
the spectral radius of $\Go$ is related to that of the Jacobi iteration matrix.
While a highly accurate parameter is often estimated by this method, and
the proportion of the cost of the estimation is small compared with a whole iteration,
the applicability depends on the matrix properties.
The second approach is to approximately minimise the residual instead
of the spectral radius of $\Go$, in order
to handle more general linear systems~\cite{ba03} (see~\cite{me04,rr16} for
some related approaches).
The key observation in~\cite{ba03} is that the residual
can be expanded as a polynomial
in terms of $\omega$, and the authors' approach is to
first approximate or truncate the polynomial by a lower order one,
then
determine the real root of it.
For symmetric positive definite linear systems,
the authors also considered a certain quadratic form instead of the residual.
While the efficiency was reported,
the estimated parameter does not always satisfy the convergence condition, and
several additional matrix-vector products are required to update the parameter.

By taking this background into account, the aim of this paper is
to develop a new type of adaptive SOR method that
is applicable to a variety of symmetric positive definite linear systems,
without additional assumptions or a requirement for additional
matrix-vector products when updating the relaxation parameter.
To achieve this goal, we develop new adaptive SOR methods
based on our previous work~\cite{ms18},
which shows that for any symmetric positive definite linear system
the SOR method can be regarded as an algorithm for solving
a certain minimisation problem.
The consequence of this discussion is that
the relaxation parameter can be interpreted as the step size
following the change of variables $h = 2\omega / (2-\omega)$.
This enables us to apply some line search techniques, developed
in the context of unconditioned optimisation problems.
In~\cite{ms18}, we already tested an approach
based on the steepest descent method,
but this approach requires an additional matrix-vector product
to update the relaxation parameter,
and the convergence could be slow for certain linear systems,
as will be illustrated later.

In this work,
we shall propose two new adaptive SOR methods based on other line search techniques.
One is based on the Armijo condition, which makes the computational cost for updating the parameter inexpensive.
But the estimated parameter sometimes tends to $0$, which delays the convergence. To avoid such a situation, we consider another adaptive SOR method based on the Wolfe conditions, i.e. the curvature condition
is also used in addition to the Armijo condition.
These methods restrict $A$ to be symmetric positive definite,
but do not require additional
assumptions on the coefficient matrix.
Furthermore, they do not require additional matrix-vector products when updating the parameter,
and it is guaranteed that the estimated value always satisfies the convergence condition $\omega \in (0,2)$.

The remainder of this paper is organised as follows.
In Section~\ref{sec2}, the connection between the SOR method and an optimisation problem
is explained, based on~\cite{ms18}.
New adaptive SOR methods are presented in Section~\ref{sec3}, and
numerically
tested in Section~\ref{sec4}.
Finally, concluding remarks are provided in Section~\ref{sec5}.

\section{Connection between the SOR method and an optimisation problem}
\label{sec2}

This section briefly reviews our previous work~\cite{ms18}, which
reveals the connection between the SOR method and an optimisation problem.

\subsection{Unconditioned optimisation problem for a strictly convex objective function}

Let a differentiable function $f:\bbR^n \to  \bbR$ be
strictly convex\footnote{A function $f\in\bbR^n\to\bbR$
is said to be strictly convex if and only if
for all $\bx,\by\in\bbR^n$ ($\bx\neq\by$)
and $\lambda\in(0,1)$, it holds that $f(\lambda \bx + (1-\lambda)\by ) < \lambda f(\bx)
+ (1-\lambda) f(\by)$.} and coercive\footnote{A function $f\in\bbR^n\to\bbR$
is said to be coercive if and only if $f(\bx) \to \infty$ for $\| \bx\| \to\infty$.}.
Let us consider the unconditioned optimisation problem
\begin{align} \label{eq:op}
\min_{\bx\in\bbR^n} f(\bx).
\end{align}
Then, there exists a unique global minimiser $\bx_\ast$ for the function $f$:
\begin{align}
\bx_\ast = \argmin_{\bx\in\bbR^n} f(\bx).
\end{align}
Note that
this minimiser coincides with the unique solution to $\nabla f(\bx ) = \bm{0} $,
and can also be realised as the equilibrium of the
following gradient system:
\begin{align}\label{eq:gs}
\frac{\rmd}{\rmd t}\bx (t) = -P \nabla f(\bx(t)),
\end{align}
where $P\in\bbR^{n\times n}$ is a symmetric positive definite matrix.
More precisely, the solution to \eqref{eq:gs} converges to
the unique minimiser of the function $f$
for any initial vector $\bx(0)=\bx_0$, i.e.,
\begin{align*}
\lim _{t\to \infty} \bx (t) = \argmin_{\bx\in\bbR^n} f(\bx).
\end{align*}

In the following, we discuss algorithms for the optimisation problem \eqref{eq:op}
with an emphasis on the relation to the gradient system \eqref{eq:gs}.
Note that most gradient descent methods
can be interpreted as the explicit Euler method
for the gradient system \eqref{eq:gs}:
\begin{align} \label{eq:eem}
\bx ^{(k+1)} = \bx^{(k)} - h P \nabla f(\bx^{(k)}),
\end{align}
where $h$ denotes the step size.
In particular, \eqref{eq:eem} coincides with the steepest descent method
when $P$ is the identity matrix.

Instead of the explicit Euler method,
we consider an alternative discretisation method for the gradient system \eqref{eq:gs}.
The key is to approximate the gradient using
the so-called discrete gradient~\cite{go96,hl14,ia88,mf14,mq99,mqr98,qm08,qt96}.
We consider a discrete approximation to $\nabla f$,
which will be denoted by $\dg f$.
The function $\dg f : \bbR^n \times \bbR^n \to \bbR$ is defined by
\begin{align}\def\arraystretch{1.3}
\dg f(\bx,\by) =
\begin{bmatrix}
\cfrac{f(x_1,y_2,\dots,y_n)-f(y_1,\dots, y_n)}{x_1-y_1} \\
\cfrac{f(x_1,x_2,y_3\dots,y_n)-f(x_1,y_2,\dots, y_n)}{x_2-y_2} \\
\vdots\\
\cfrac{f(x_1,\dots,x_n)-f(x_1,\dots,x_{n-1}, y_n)}{x_n-y_n}
\end{bmatrix}  \label{eq:ia}
\end{align}
for all $\bx,\by \in \bbR^n$.
This function is called a discrete gradient,
because it is an approximation to the gradient
in the sense that
\begin{align} \label{eq:co}
\lim_{\by \to \bx} \dg f(\bx,\by ) = \nabla f(\bx).
\end{align}
Furthermore, it follows that
\begin{align} \label{dcr}
f(\bx) - f(\by) = \dg f(\bx,\by)^\top (\bx-\by)
\end{align}
for all $\bx,\by \in \bbR^n$.
By utilising the discrete gradient \eqref{eq:ia},
we discretise the gradient system \eqref{eq:gs} as follows:
\begin{align}
\bx ^{(k+1)} = \bx^{(k)} - hP \dg f(\bx^{(k+1)},\bx^{(k)}).

\label{dgscheme}
\end{align}
Here, we have just replaced the gradient in \eqref{eq:eem} with the discrete gradient.
However, there is a significant difference between \eqref{eq:eem} and \eqref{dgscheme} from
the viewpoint of optimisation problems.
For the solution to~\eqref{dgscheme},
the following discrete dissipation property holds:
\begin{align}
\frac{1}{h} \left( f(\bx^{(k+1)}) - f(\bx^{(k)}) \right)
&=   \dg f(\bx^{(k+1)}, \bx^{(k)} ) ^\top \frac{\bx^{(k+1)} - \bx ^{(k)}}{h}  \\
&= - \dg f(\bx^{(k+1)}, \bx^{(k)} ) ^\top P \dg f(\bx^{(k+1)}, \bx^{(k)} ) \leq 0 \label{d:dp}
\end{align}
as long as $h>0$.
Thanks to this property, the sequence obtained by~\eqref{dgscheme} converges to the minimiser.

\begin{proposition}[see, e.g.,~\cite{gr17}] \label{prop:d}
Let a differentiable function $f:\bbR^n\to\bbR$ be strictly convex and coercive.
Then, the sequence $\{ \bx ^{(k)}\}_{k=0}^\infty$ obtained by the iteration~\eqref{dgscheme}
converges to the unique minimiser of the function $f$ for any initial vector $\bx_0$,
i.e.,
\begin{align}
\lim _{k\to\infty} \bx^{(k)} = \argmin _{\bx\in\bbR^n} f(\bx).
\end{align}
\end{proposition}
A rigorous proof of this is given in~\cite{gr17}.

This proposition indicates that the convergence is guaranteed even for a relatively large step size $h$, which is not the case for standard gradient descent methods \eqref{eq:eem}.

Let us mention the case that the step size $h$ is controlled adaptively.
We denote the step size at $k$th iteration by $h^{(k)}$.
In this case, we need to avoid the situation that the step size tends to $0$ or $+\infty$.
The convergence
is guaranteed if $0 < \epsilon < h^{(k)} < M < \infty$ for two positive constants $\epsilon$ and $M$.

\begin{remark}
In the context of numerical ordinary differential equations,
a function satisfying both \eqref{eq:co} and \eqref{dcr} is called a discrete gradient,
and is used to simulate systems of ordinary differential equations such as gradient systems and Hamiltonian systems.
Such a function is not unique in general, and \eqref{eq:ia} is just an example, which was
introduced by Itoh--Abe~\cite{ia88}.
See, e.g.,~\cite{go96,hl14,ia88,mf14,mq99,mqr98,qm08,qt96}
for further details regarding the discrete gradient method.
\end{remark}

\subsection{SOR method as an optimisation solver}

We now show that the SOR method
can be regarded as an algorithm to solve a certain optimisation problem.

Let
\begin{align} \label{qf}
f(\bx) = \frac12 \bx^\top A \bx  - \bx^\top \bb.
\end{align}
If $A$ is symmetric positive definite, then the function $f$ is strictly convex and coercive,
and thus it yields the unique minimiser
$\bx_\ast = A^{-1}\bb$ (note that $\nabla f(\bx) = A\bx - \bb$).
In particular,
when $P=D^{-1}$
the scheme \eqref{dgscheme} is written as
\begin{align}\label{dgscheme1}
\bx^{(k+1)} = \bx^{(k)} -hD^{-1} \dg f(\bx^{(k+1)}, \bx^{(k)}),
\end{align}
where
the $i$th component of the discrete gradient is calculated to be
\begin{align}
(\dg f(\bx,\by))_i &= \frac{f(x_1,\dots,x_i,y_{i+1},\dots,y_n)-f(x_1,\dots,x_{i-1},y_i,\dots, y_n)}{x_i-y_i} \\
&= \sum_{j<i} a_{ij}x_j + a_{ii}\frac{x_i+y_i}{2} + \sum_{j>i} a_{ij}y_j - b_i.
\end{align}

Our previous work~\cite{ms18} proves the following equivalence result.
\begin{theorem}[\cite{ms18}]
\label{th:cond}
The SOR method and the scheme \eqref{dgscheme1} are equivalent
if
\begin{align}\label{cond1}
h = \frac{2\omega}{2-\omega}.
\end{align}
In other words, under the relation \eqref{cond1} the sequences generated by
the SOR method and the scheme \eqref{dgscheme1} coincide with each other
as long as the same initial vector $\bx_0$ is used.
\end{theorem}

Therefore, the SOR method can be regarded as an algorithm solving the optimisation problem
for the function \eqref{qf}.

\begin{remark}
It is well known that the SOR method applied to symmetric positive definite linear systems converges
if and only if $\omega \in (0,2)$.
In the standard SOR theory,
this condition is obtained by analysing the spectral radius of
$\Go$.
However, this condition can also be proved in a completely different manner based on the above discussion.
The convergence condition in terms of $h$ is $h>0$ (as discussed in the previous subsection),
and $h>0$ is equivalent to
$\omega \in (0,2)$ under the relation \eqref{cond1}.
\end{remark}

\section{Adaptive SOR methods}
\label{sec3}

Based on
the interpretation of the SOR method discussed in the previous section,
we develop some new adaptive SOR methods.
The key idea is to control the step size instead of the relaxation parameter.
In the following, the coefficient matrix $A$ is always assumed to be symmetric positive definite.

Note that the step size could be adaptively controlled
in many different ways.
For example, several step size control techniques have been developed in the context of the numerical
analysis of ordinary differential equations~\cite{hw96}, and thus
applying such techniques would be a possibility~\cite{hw96}.
However, this merely provides an efficient strategy, because
such step size control techniques aim to integrate ODEs as precisely as possible,
but do not aim to find an equilibrium as quickly as possible.

Alternatively, we consider some line search strategies, developed in the context of unconditioned optimisation problems.
At each iteration, after defining the step direction $\bp^{(k)}$, for example as
the direction of steepest descent
$\bp_k = -\nabla f(\bx^{(k)})$,
line search methods seek to determine the step size such that it minimises
$f(\bx + h^{(k)} \bp^{(k)})$.
However, because this task is often computationally expensive for a general function $f$,
most line search methods seek to approximate the optimal step size at a low cost.
Among these, methods employing the Armijo condition or Wolfe conditions are popular.
We hope to apply such line search methods to the SOR method.
However, such line search methods cannot be directly incorporated with the SOR method
because the step direction, i.e., the discrete gradient $\dg f (\bx^{(n+1)},\bx^{(n)})$,
depends on the choice of the step size (note that $\bx^{(n+1)}$
depends on the step size).
Therefore,
slight modifications are required
to apply the aforementioned line search methods to the SOR method.
To achieve this task, we shall directly use the approach proposed in~\cite{rl17}.

In the following, in order to simplify the presentation
we assume without loss of generality that $D=I$. That is,
the coefficient matrix $A$ is preconditioned
such that its diagonal matrix coincides with the identity matrix.
This can be achieved by $D^{-1/2} A D^{-1/2}$.

\subsection{Approach based on the locally optimal step size of the steepest descent method}

Our previous work~\cite{ms18} considers an adaptive SOR method
that employs the locally optimal step size of the steepest descent method.
We review this method
before presenting new approaches.

The locally optimal step size of the steepest descent method is obtained by solving
\begin{align}  \label{sorsizeprob}
\min _{h^{(k)} > 0} f(\bx^{(k)} + h^{(k)} \bp^{(k)}), \quad
\bp^{(k)} = - \nabla f(\bx^{(k)}).
\end{align}
For the function \eqref{qf}, the locally optimal step size
is given explicitly by
\begin{align} \label{oph}
h^{(k)} = \frac{(\br^{(k)}) ^\top  \br^{(k)}}{(\br^{(k)})^\top A\br^{(k)}},
\end{align}
where $\br^{(k)} = \bb - A\bx^{(k)}$.
The main idea presented in our previous paper~\cite{ms18}
is to adopt \eqref{oph}
as the step size of the SOR method.
This approach is summarised in Algorithm~\ref{algo:adap1}.

\begin{algorithm}
\caption{Adaptive SOR method based on the steepest descent method}
\begin{algorithmic}
\label{algo:adap1}
\STATE $\br^{(0)} := \bb - A\bx^{(0)}$;
\FOR{$k=0,1,2,\dots$ \textbf{until} $\| \br^{(k)} \| \leq \epsilon \| \bb\|$}
\STATE $\displaystyle h^{(k)} := \frac{(\br^{(k)}) ^\top  \br^{(k)}}{(\br^{(k)})^\top A\br^{(k)}}$;
\STATE $\displaystyle \omega^{(k)} := \frac{2h^{(k)}}{2+h^{(k)}}$;
\STATE $\bx^{(k+1)} := G_{\omega^{(k)}}\bx^{(k)} + \bc$;

\STATE $\br^{(k+1)} := \bb - A\bx^{(k+1)}$;
\ENDFOR
\end{algorithmic}
\end{algorithm}

This algorithm does not contain any parameters to be predetermined.
It is observed in~\cite{ms18} that
this algorithm performs well for the Poisson equation:
the number of iterations required for this algorithm is under two times that of
the SOR method with the optimal parameter.
It should be noted that
there is only one additional matrix-vector product per iteration,
i.e., the calculation of
$A \br^{(k)}$ appearing in the denominator of \eqref{oph}. This is
in contrast to some existing approaches, such as~\cite{ba03},
for which additional matrix-vector products are required.

However, it turns out that this approach does not always work perfectly
when tested with other linear systems,
as illustrated in the next section.
Moreover, it is hoped that the cost for estimating the parameter can be reduced further.

\begin{remark} \label{rem1}
The computational effort for updating the step size (or the relaxation parameter)
could be reduced if the frequency of the update is decreased, and this idea can be applied to
any adaptive SOR method, including those presented in this paper.
\end{remark}

\subsection{New adaptive SOR methods}

Instead of using the step size \eqref{sorsizeprob},
we propose new strategies utilising the Armijo condition or Wolfe conditions
with slight modifications.

Let us start the discussion by applying the Armijo condition,
which is motivated by the recent paper~\cite{rl17}.
As explained in~\cite{rl17},
if $\bx^{(k+1)}$ satisfies
\begin{align} \label{armijo1}
f(\bx^{(k+1)}) \leq f(\bx^{(k)}) + c_1 \nabla f (\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)})
\end{align}
for a predetermined constant $c_1 \in (0,1)$,
then the step size is deemed to be good, and increased for the next iteration by a factor of $\lambda_1 >1$:
$h^{(k+1)} = \lambda_1 h^{(k)}$.
If the condition \eqref{armijo1} is not satisfied, then the step size is decreased for the next iteration by a
factor of $\rho_1 \in(0,1)$: $h^{(k+1)} = \rho_1 h^{(k)}$.
This approach has the following distinguished features.
\begin{itemize}
\item
In contrast to the standard application of the Armijo condition,
the condition \eqref{armijo1} is not used for calculating the current step size $h^{(k)}$,
but rather for calculating the next step size $h^{(k+1)}$.
This is because whether or not the condition is satisfied, the dissipation property
$f(\bx^{(k+1)}) \leq f(\bx^{(k)})$ always follows.
\item
Assume that the residual $\br^{(k)} = \bb - A\bx^{(k)}$ is calculated and checked at each iteration
(note that this can be obtained without calculating additional matrix-vector products, because
$L\bx^{(k)}$ and $U\bx^{(k)}$ are obtained in the preceding SOR iteration).
Then, there are no additional matrix-vector products required to calculate $f(\bx^{(k)})$
and $\nabla f(\bx^{(k)}) = -\br^{(k)}$.
Thus, the additional costs for checking the condition \eqref{armijo1} consist of only a few
inner product calculations.
\end{itemize}

\begin{remark}
In the condition \eqref{armijo1}, one might think that
the gradient $\nabla f (\bx^{(k)})$ should be replaced by the
discrete gradient $\dg f (\bx^{(k+1)},\bx^{(k)})$.
However,
considering the condition
\begin{align}
f(\bx^{(k+1)}) \leq f(\bx^{(k)}) + c_1 \dg f (\bx^{(k+1)},\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)})
\end{align}
is meaningless, because this condition is always satisfied:
\begin{align}
f(\bx^{(k+1)})
&= f(\bx^{(k)}) +\dg f (\bx^{(k+1)},\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)}) \\
&\leq f(\bx^{(k)}) + c_1 \dg f (\bx^{(k+1)},\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)}).
\end{align}
The equality follows thanks to \eqref{dcr}, and
the inequality follows from the fact that $f (\bx^{(k+1)},\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)})\leq 0$ (see~\eqref{d:dp})
 and the assumption $c_1 \in (0,1)$.
 \end{remark}

Our preliminary numerical experiments show that the above approach performs well
for many linear systems.
However, the step size detected using the above approach may become close to zero
or quite large, which delays the convergence.
In other words, in terms of the relaxation parameter $\omega$,
$\omega^{(k)}$ sometimes takes a value close to $0$ or $2$.
To avoid this situation, we need to set the maximum and minimum values
($M_\omega$ and $\epsilon_\omega$) that the relaxation parameter is allowed to take,
and if this is violated
we reset the relaxation parameter and the step size.

The above algorithm is summarised in Algorithm~\ref{algo:adap2}.
Here, the step size is initially set to $2$, which indicates that the relaxation parameter
is initially set to $1$, and if $\omega^{(k+1)} \notin (\epsilon_\omega , M_\omega)$ then
the step size and relaxation parameter are reset to $1$ and $2$, respectively.

\begin{algorithm}
\caption{Adaptive SOR method based on the Armijo condition}
\begin{algorithmic}
\label{algo:adap2}
\STATE Set parameters $c_1 \in (0,1)$, $\lambda_1 > 1$,
$\rho_1 \in (0,1)$;
\STATE $\br^{(0)} := \bb - A\bx^{(0)}$;
\STATE $h^{(0)} := 2$;
\STATE $\omega^{(0)}:=1$;
\FOR{$k=0,1,2,\dots$ \textbf{until} $\| \br^{(k)} \| \leq \epsilon \| \bb\|$}
\STATE $\bx^{(k+1)} := G_{\omega^{(k)}}\bx^{(k)} + \bc$;

\STATE $\br^{(k+1)} := \bb - A\bx^{(k+1)}$;
\IF{$f(\bx^{(k+1)}) \leq f(\bx^{(k)}) + c_1 \nabla f (\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)})$}
\STATE $h^{(k+1)} := \lambda_1 h^{(k)}$;
\ELSE
\STATE $h^{(k+1)} := \rho_1 h^{(k)}$
\ENDIF
\STATE $\displaystyle \omega^{(k+1)} := \frac{2h^{(k+1)}}{2+h^{(k+1)}}$;
\IF{$\omega^{(k+1)} \notin (\epsilon_\omega , M_\omega)$}
\STATE  $h^{(k+1)} = 2$;
\STATE  $\omega^{(k+1)} = 1$;
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

In the context of nonlinear optimisation problems,
the Wolfe conditions, which consist of the Armijo condition and the so-called curvature condition,
is often employed to avoid the step size becoming close to $0$.
In the following, we consider another algorithm, which is based on
the Wolfe conditions.

Here, we consider the following curvature condition:
\begin{align}\label{wolfe1}
c_2 \nabla f (\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)} )\leq \nabla f(\bx^{(k+1)})^\top (\bx^{(k+1)}-\bx^{(k)})
\end{align}
for a predetermined constant $c_2\in (c_1,1)$.
If the two conditions \eqref{armijo1} and \eqref{wolfe1} are satisfied,
then the step size for the next iteration is increased by $h^{(k+1)} = \lambda_1 h^{(k)}$, as in Algorithm~1.
However, if the condition \eqref{wolfe1} is not satisfied, then the current step size is deemed too small
and increased for the next iteration by a larger factor of $\lambda_2>\lambda_1 (>1)$:
$h^{(k+1)} = \lambda_2 h^{(k)}$.

The above approach is summarised in Algorithm~\ref{algo:adap3}.

\begin{algorithm}
\caption{Adaptive SOR method based on the Wolfe conditions}
\begin{algorithmic}
\label{algo:adap3}
\STATE Set parameters $c_1 \in (0,1)$, $c_2 \in (c_1, 1)$, $\lambda_1 > 1$,
$\lambda_2 > \lambda_1$, $\rho_1 \in (0,1)$;
\STATE $\br^{(0)} := \bb - A\bx^{(0)}$;
\STATE $h^{(0)} := 2$;
\STATE $\omega^{(0)}:=1$;
\FOR{$k=0,1,2,\dots$ \textbf{until} $\| \br^{(k)} \| \leq \epsilon \| \bb\|$}
\STATE $\bx^{(k+1)} := G_{\omega^{(k)}}\bx^{(k)} + \bc$;
\STATE $\br^{(k+1)} := \bb - A\bx^{(k+1)}$;
\IF{$f(\bx^{(k+1)}) \leq f(\bx^{(k)}) + c_1 \nabla f (\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)})$}
\IF{$c_2 \nabla f (\bx^{(k)}) ^\top (\bx^{(k+1)} - \bx^{(k)} )\leq \nabla f(\bx^{(k+1)})^\top (\bx^{(k+1)}-\bx^{(k)})$}
\STATE $h^{(k+1)} := \lambda_1 h^{(k)}$;
\ELSE
\STATE $h^{(k+1)} := \lambda_2 h^{(k)}$;
\ENDIF
\ELSE
\STATE $h^{(k+1)} := \rho_1 h^{(k)}$
\ENDIF
\STATE $\displaystyle \omega^{(k+1)} := \frac{2h^{(k+1)}}{2+h^{(k+1)}}$;
\IF{$\omega^{(k+1)} \notin (\epsilon_\omega , M_\omega)$}
\STATE  $h^{(k+1)} = 2$;
\STATE  $\omega^{(k+1)} = 1$;
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

\section{Numerical experiments}
\label{sec4}

In this section, the proposed adaptive SOR methods are tested
for a variety of symmetric positive definite linear systems.
The main aim of this section is
to numerically verify the convergence of the proposed methods.
Note that the computational costs required for updating the step size
were discussed from the viewpoint of the number of matrix-vector products
in the previous section,
and the actual computation time depends on
the frequency of the updates, as explained in Remark~\ref{rem1}.
Therefore, we do not check the actual computational time, and in all
numerical experiments the step size is updated at every iteration, for a
fair comparison with Algorithms~\ref{algo:adap1},~\ref{algo:adap2},
and \ref{algo:adap3}.
We also note that a comparison with other types of adaptive SOR methods or linear solvers,
such as the conjugate gradient method, is beyond the scope of this study,
because of the difficulty in setting a
fair gauge for a head-to-head comparison owing to quite different mathematical
features.
All numerical experiments are conducted
after the coefficient matrix $A$ is preconditioned
such that its diagonal matrix coincides with the identity matrix.
All the computations are performed in a computation environment with
3.5 GHz Intel Core i5, 8 GB memory, and OS X 10.10.5. We employ MATLAB (R2015a).
Below, the
results are often displayed after thinning out the data to highlight the behaviour of each algorithm and reduce
the file size.

Note that in Algorithms~\ref{algo:adap2} and~\ref{algo:adap3}
there are several constants and factors to be predetermined.
Instead of finding optimal values for each linear system,
which seems more difficult than
determining the optimal relaxation parameter of the SOR method,
we fix them as $(c_1,c_2,\lambda_1,\lambda_2,\rho_1)
= (0.89, 0.95,1.15,1.4,0.85 )$,
and this combination is employed for different linear systems.

\subsection{Poisson equation}
The first problem arises from the finite difference discretisation of
the Poisson equation
\begin{align}
-\triangle u  &= f \quad \text{in }\Omega, \\
u&=0 \quad \text{on }\partial \Omega,
\end{align}
where $\Omega = (0,1)^2\subset \bbR^2$, $\triangle$
denotes the Laplace operator
and $f:\Omega \to \bbR$.
The standard finite difference discretisation on a uniform mesh $N\times N$
leads to a symmetric positive definite linear system
for which the coefficient matrix $A$ is given by
\begin{align}
A = \frac{1}{\Delta x^2} \left(-I \otimes I + \frac{1}{4} B\otimes I + \frac{1}{4} I \otimes B \right) ,
\end{align}
where $I\in\bbR^{(N-1)\times (N-1)}$ is the identity matrix,
\begin{align*}
B = \begin{bmatrix}
0 & 1 & &  \\
1 & \ddots & \ddots& \\
& \ddots & \ddots & 1 \\
& &1 & 0
\end{bmatrix} \in \bbR^{(N-1)\times (N-1)},
\end{align*}
and $\otimes$ denotes the Kronecker product.
The optimal relaxation parameter for this matrix $A$ is well known,
and is expressed in terms of $h=1/(N+1)$ as
\begin{align*}
\omega_{\text{opt}} = \frac{2}{1+\sqrt{1-\cos^2 (\pi h)}}.
\end{align*}

Fig.~\ref{fig:poisson} illustrates the numerical results
for a test problem $f(x,y) = \sin(\pi x) \sin (\pi y)$.
The left figures show the relative residual 2-norm.
The convergence of Algorithm~\ref{algo:adap1}
is slower than that of the SOR method with the optimal parameter,
but is considerably faster than that of the Gauss-Seidel method. Furthermore,
the number of iterations required for convergence is less than two times
that of the SOR method with the optimal parameter.
In this sense, as discussed in our previous report~\cite{ms18},
Algorithm~\ref{algo:adap1} appears to be flexible.
However, as previously explained,
the computational cost per iteration of Algorithm~\ref{algo:adap1}
is almost twice as expensive as that of the SOR method.
Keeping this in mind,
let us discuss the behaviour of Algorithms~\ref{algo:adap2} and~\ref{algo:adap3}.
For $N=60$, both algorithms perform satisfactorily compared
with Algorithm~\ref{algo:adap1}.
However, for $N=100$ and $N=120$ there are substantial differences.
While the results for Algorithm~\ref{algo:adap3} still remain satisfactory, the
convergence of Algorithm~\ref{algo:adap2} appears to deteriorate.
These differences can also be explained from the right-side figures,
which show the variations of $\omega^{(k)}$.
In particular, the difference is remarkable when $N=100$.
Here, $\omega^{(k)}$ of Algorithm~\ref{algo:adap2}
tends to $0$, even after it is reset to $1$ at around the $1500$th iteration.

\input{fig_poisson.tex}

\subsection{Additional examples}

Table~\ref{tab:matrix_data} presents the matrix data used in
the numerical experiments,
which were obtained from
the Matrix Market (\url{https://math.nist.gov/MatrixMarket/})
and the ELSES Matrix Library (\url{http://www.elses.jp/matrix/}).
In the following numerical experiments,
the right-hand vector was set to $\bb = (1,\dots,1)^\top$.

The results are illustrated in Figs.~\ref{fig:bcsstk04},~\ref{fig:bcsstk05},~\ref{fig:bcsstk07}, and~\ref{fig:icnt1800}.
In the left-hand figures, in addition to Algorithms~\ref{algo:adap1},~\ref{algo:adap2}, and~\ref{algo:adap3}
we plot the results for the Gauss--Seidel method (dashed line),
the SOR method with $\omega=1.8$ (dotted line),
and the SOR method, for which the convergence is the fastest in $\omega = 0.1,0.2,\dots, 1.9$
(black line).
In Fig.~\ref{fig:icnt1800}, the results for the Gauss--Seidel method
are illustrated by the solid black line rather than the dashed one,
because the Gauss--Seidel method performed best.

Although the results differ for each problem,
Algorithm~\ref{algo:adap3} is faster than
Algorithms~\ref{algo:adap1} and~\ref{algo:adap2} under all settings.
Note that from Fig.~\ref{fig:icnt1800} one might infer that
Algorithm~\ref{algo:adap1} is the fastest,
but if we take the computational cost at each iteration into account
Algorithms~\ref{algo:adap2} and~\ref{algo:adap3} are superior.
The number of iterations required to converge for Algorithm~\ref{algo:adap3} is less than
three times as big as that for the SOR method, for which the convergence
is the fastest in $\omega = 0.1,0.2,\dots, 1.9$.
Furthermore, in the results shown in Fig.~\ref{fig:bcsstk07}, Algorithm~\ref{algo:adap3}
is the fastest.
We observed similar behaviours for the other problems
obtained from the Matrix Market and the ELSES Matrix Library.

\begin{table}
\centering
\caption{Matrix data.}
\label{tab:matrix_data}
\begin{tabular}{c|c|c}
\hline
 Data & $n$ & {\#}nz\\
\hline
 BCSSTK04 & 132 & 3648 \\
 \hline
 BCSSTK05 & 153 & 2423 \\
 \hline
 BCSSTK07 & 420 & 7860 \\
 \hline
 ICNT1800 & 1800 & 574960 \\
\end{tabular}
\end{table}

\input{fig_bcsstk04.tex}

\input{fig_bcsstk05.tex}

\input{fig_bcsstk07.tex}

\input{fig_icnt1800.tex}

\section{Concluding remarks}
\label{sec5}

In this paper, we proposed two adaptive SOR methods based on line search techniques.
One is based on the Armijo condition, and the other on the Wolfe conditions.
The features of the proposed methods are summarised as follows:
\begin{itemize}
\item They are applicable to any symmetric positive definite linear system,
in the sense that the convergence condition is always satisfied.
\item No additional matrix-vector products are required to update the relaxation parameter.
\item There are several factors and parameters in the algorithms.
While these should be predetermined and the optimal combination is difficult to obtain,
for the adaptive SOR method based on the Wolfe conditions (Algorithm~\ref{algo:adap3}),
the empirical combination  $(c_1,c_2,\lambda_1,\lambda_2,\rho_1)
= (0.89, 0.95,1.15,1.4,0.85 )$
employed in this paper can perform well for many symmetric positive definite
linear systems.
\item The convergence is slower than that of the SOR method using the optimal parameter,
but is faster than naive choices such as $\omega = 1$ (the Gauss--Seldel method) and $\omega=1.8$ in most cases.
Furthermore, the number of iterations required for convergence is less than two times that of
the SOR method with the optimal parameter in most cases,
which indicates that the computational cost is also less than double that of
the SOR method with the optimal parameter.
\end{itemize}

We mention several directions for future work.
In this paper, among the infinite number of combinations of parameters that are to be
predetermined,
the results obtained by the chosen empirical combination were presented, but
it would be interesting to study a strategy of tuning the combination
to find broad applications.
We are also currently attempting to extend the presented approach to more general linear systems.

\bibliographystyle{plain}
\bibliography{references}
\end{document}

config: arxiv


TITLE: Population Variation with two variables
QUESTION [3 upvotes]: I have a dataset with two variables. I want to treat my dataset as a population not a sample. I am wondering if I can just use the formula for population variance as below:
$$\frac{\sum(X-\mu)^2}{N}$$
Here, do I need to think about the degree of freedom?
Does the degree of freedom have anything with the number of variables?
If you have expertise in this, please let me have an idea.
Thank you.

REPLY [1 votes]: If your population has $N$ equally probable outcomes (so each has probability $1/N$) and a value of the variable $X$ is assigned to each outcome, and $\mu$ is the average of those $N$ values of $X$, then the expression you wrote is the variance of $X$.


TITLE: Cardinal exponentation
QUESTION [2 upvotes]: Let $\lambda, \kappa$ be infinite cardinals. Does it follow from the inequality $\kappa\lt2^\lambda$ that $2^\kappa\lt2^{2^\lambda}$?

REPLY [6 votes]: No.
Suppose $2^{\aleph_0}=\aleph_2$ and $2^{\aleph_1}=2^{\aleph_2}=\aleph_3$.
Let $\lambda=\aleph_0$ and $\kappa=\aleph_1$, now we have $2^\kappa=2^{2^\lambda}$.


text:
\begin{document}
\maketitle

\begin{abstract}
We show that, for an abelian variety defined over a $p$-adic field $K$
which has potential good reduction,
its torsion subgroup with values in the composite field of $K$ and
a certain Lubin-Tate extension over a $p$-adic field is finite.
\end{abstract}

\section{Introduction}

Let $p$ be a prime number and $A$ an abelian variety over a  $p$-adic field $K$
(here, a {\it $p$-adic field} is a finite extension of $\mbb{Q}_p$).
For an algebraic extension $L/K$, we denote by $A(L)$ the group of
$L$-rational points of $A$ and also denote by $A(L)_{\mrm{tor}}$ its torsion subgroup.
We are interested in determining whether $A(L)_{\mrm{tor}}$ is finite or not.

The most basic result is given by Mattuck \cite{Ma};
$A(L)_{\mrm{tor}}$ is finite if  $L$ is a finite extension of $K$.
Thus our main interest is the case where $L$ is an infinite algebraic extension of $K$.
For this, Imai's result \cite{Im} is well-known.
He showed that $A(K(\mu_{p^{\infty}}))_{\mrm{tor}}$ is finite if
$A$ has potential good reduction,
where $\mu_{p^{\infty}}$ denotes the group of $p$-power roots of unity
in a fixed separable closure $\overline{K}$ of $K$.
Since the field $K(\mu_{p^{\infty}})$ is the composite field of $K$ and the Lubin-Tate extension
over $\mbb{Q}_p$ associated with a uniformizer $p$ of $\mbb{Q}_p$,
we naturally have the following question.

\begin{question}
Let $A$ be an abelian variety over a $p$-adic field $K$.
Let $k_{\pi}$ be  the Lubin-Tate extension associated with a uniformizer $\pi$ of a $p$-adic field $k$.
Then, is $A(Kk_{\pi})_{\mrm{tor}}$ finite?
\end{question}

\noindent
In the case of Imai's theorem ($k=\mbb{Q}_p$ and $\pi=p$),
the answer of the question is affirmative for good reduction cases.
However, the question sometimes has a negative answer.
For example, if $A$ is a Tate curve over $K$, $k=\mbb{Q}_p$ and $\pi=p$,
then $A(Kk_{\pi})[p^{\infty}]=A(K(\mu_{p^{\infty}}))[p^{\infty}]$ is clearly infinite.
We also have an example even  for good reduction cases as given  in Remark \ref{normcondi}.

The aim of this paper is to give a sufficient condition
on $k$ and $\pi$ so that the question has an affirmative answer
for good reduction cases.
Let $k, \pi$ and $k_{\pi}$ be as above.
Let $q$ be the order of the residue field of $k$.
We denote by $k_G$ the Galois closure of $k/\mbb{Q}_p$.
We put $d_G=[k_G:\mbb{Q}_p]$ and denote by $e_G$
the ramification index of the extension $k_G/k$.
Our main result is as follows
(see  Definitions \ref{Weil1} and \ref{Weil2} for some undefined  notion).

\begin{theorem}
\label{MC}
Let $A$ be an abelian variety over a $p$-adic field $K$ with potential good reduction.
If $\mrm{Nr}_{k/\mbb{Q}_p}(\pi)$
is not a $q$-Weil integer of weight

$sd_G/t$ for some integers $1\le s\le e_G$ and $1\le t \le sd_G$,
then $A(Kk_{\pi})_{\mrm{tor}}$ is finite.
\end{theorem}

\noindent
Applying Theorem \ref{MC} to the case where $k=\mbb{Q}_p$ and $\pi=p$,
we can recover Imai's theorem.
We should note that there is an another generalization of Imai's theorem
which is given by Kubo and Taguchi \cite{KT}.
The main result of {\it loc.\ cit.} states that
the torsion subgroup of $A(K(K^{1/p^{\infty}}))$ is finite, where
$A$ is an abelian variety over  $K$ with potential good reduction and
$K(K^{1/p^{\infty}})$ is the extension field of $K$
by adjoining all $p$-power roots of all elements of $K$.

For the proof of the above theorem,

the essential difficulty appears in the finiteness
of the $p$-power torsion part $A(Kk_{\pi})[p^{\infty}]$ of $A(Kk_{\pi})_{\mrm{tors}}$.

For this, we proceed our arguments in more general settings.
We study not only abelian varieties but also \'etale cohomology groups
of proper smooth varieties.

\begin{theorem}
\label{MTp:var}
Let $X$ be a proper smooth variety over a $p$-adic field $K$
with potential good reduction.
Let $V$ be a $\mrm{Gal}(\overline{K}/K)$-stable subquotient of
$H^i_{\aet}(X_{\overline{K}},\mbb{Q}_p(r))$ with $i\not=2r$.
Assume that $V^{\mrm{Gal}(\overline{K}/L)}\not=0$ for some finite extension $L/Kk_{\pi}$.
Then  $\mrm{Nr}_{k/\mbb{Q}_p}(\pi)$
is a $q$-Weil number of weight $-(i-2r)/h$
for some non-zero $h\in [-i+r,r]\bigcap \left( \bigcup_{1\le s\le e_G} (1/sd_G) \mbb{Z}\right)$.
Moreover,
$q^r\mrm{Nr}_{k/\mbb{Q}_p}(\pi)^{-h}$ is an algebraic integer.
\end{theorem}

\noindent
Applying Theorem \ref{MTp:var} to the case where $k=\mbb{Q}_p$ and $\pi=p$,
we obtain \cite[Theorem 1.5]{CSW} for $0$-th cohomology groups.
The assumption $i \not=2r$ in Theorem \ref{MTp:var} is essential
as explained in the Introduction of \cite{KT}.
The key ingredients for our proof are the theory of locally algebraic representations
(cf.\ \cite{Se})
and some ``weight arguments''
of eigenvalues of Frobenius on various objects.
For weight arguments, we use $p$-adic Hodge theory related with Lubin-Tate characters
and results on weights of a Frobenius operator on crystalline cohomologies (cf.\ \cite{CLS}, \cite{KM}, \cite{Na}).

\vspace{5mm}
\noindent
{\bf Notation :}
In this paper, we fix algebraic closures $\overline{\mbb{Q}}$ and $\overline{\mbb{Q}}_p$
of $\mbb{Q}$ and $\mbb{Q}_p$, respectively, and
we fix an embedding $\overline{\mbb{Q}}\hookrightarrow \overline{\mbb{Q}}_p$.

If $F$ is a $p$-adic field,
we denote by  $G_F$ and  $U_F$
the absolute Galois group $\mrm{Gal}(\overline{\mbb{Q}}_p/F)$ of $F$
and the unit group of the integer ring of  $F$,
respectively.
We also denote by
$F^{\mrm{ur}}$  and $I_F$
the maximal unramified extension of $F$ in $\overline{\mbb{Q}}_p$ and
the inertia subgroup $\mrm{Gal}(\overline{\mbb{Q}}_p/F^{\mrm{ur}})$ of $G_F$,
respectively.
We set $\Gamma_F:=\mrm{Hom}_{\mbb{Q}_p}(F,\overline{\mbb{Q}}_p)$.
If $F'/F$ is a finite extension,
we denote by $f_{F'/F}$ the residual extension degree of $F/F'$.
that is, the extension degree of the residue fields corresponding to
$F'/F$.
We put $f_{F}=f_{F/\mbb{Q}_p}$.

\begin{acknowledgments}
The author would like to express his sincere gratitude to Professor Yuichiro
Taguchi for giving him useful
advices, especially Remark 2.10.
\end{acknowledgments}

\section{Proofs of main theorems}

Our goal is to prove results in the Introduction.
Let $K,k$ and $E$ be a finite extension of $\mbb{Q}_p$.
Let $\pi$ be a uniformizer of $k$ and
$k_{\pi}$ the Lubin-Tate extension of $k$ associated with $\pi$.
We denote by $\chi_{\pi}\colon G_k \to k^{\times}$ the Lubin-Tate character
associated with $\pi$.
If we regard $\chi_{\pi}$ as a continuous
character $k^{\times}\to k^{\times}$
by the local Artin map with arithmetic normalization,
then $\chi_{\pi}$ is characterized by the property that $\chi_{\pi}(\pi)=1$
and $\chi_{\pi}(u)=u^{-1}$ for any $u\in U_k$.
\begin{definition}
\label{Weil1}

Let $q_0>1$ be an integer.
A {\it $q_0$-Weil number {\rm (}resp.\ $q_0$-Weil integer{\rm )} of weight $w$}
is an algebraic number (resp.\ algebraic integer) $\alpha$
such that $|\iota (\alpha)|=q_0^{w/2}$ for all embeddings
$\iota\colon \mbb{Q(\alpha)}\hookrightarrow \mbb{C}$.

\end{definition}

\begin{definition}
\label{Weil2}
Let $F$ be a finite extension of $\mbb{Q}_p$
with residual extension degree $f=f_F$
and $F_0/\mbb{Q}_p$ the maximal
unramified subextension of $F/\mbb{Q}_p$.

\noindent
(1)
Let $D$ be a $\vphi$-module over $F$, that is,
a finite dimensional $F_0$-vector space with
$\vphi_{F_0}$-semilinear map $\vphi \colon D\to D$.
Then $\vphi^f\colon D\to D$ is a $F_0$-linear map.
We call $\mrm{det}(T-\vphi^f\mid  D)$
the {\it characteristic polynomial of $D$}.

\noindent
(2)
For  a $\mbb{Q}_p$-representation $U$ of $G_F$,
we set $D^F_{\mrm{cris}}(U):=(B_{\mrm{cris}}\otimes_{\mbb{Q}_p} U)^{G_F}$
and $D^F_{\mrm{st}}(U):=(B_{\mrm{st}}\otimes_{\mbb{Q}_p} U)^{G_F}$,
which are filtered $\vphi$-modules over $F$.
Here, $B_{\mrm{cris}}$ and $B_{\mrm{st}}$ are usual $p$-adic period rings.
Note that we  have $D^F_{\mrm{cris}}(U)=D^F_{\mrm{st}}(U)$ if $U$ is crystalline.

\noindent
(3)
 Let $S$ be a set of rational numbers.
Let $U$  be a  potentially semi-stable $\mbb{Q}_p$-representation of $G_F$.
Suppose that $U|_{G_{F'}}$ is semi-stable for a finite extension $F'$ of $F$
with residue field $\mbb{F}_{q'}$.
We say that $U$ has {\it Weil weights in $S$} if
any root of the characteristic polynomial of $D^{F'}_{\mrm{st}}(U)$
is a $q'$-Weil number of weight $w$ for some $w\in S$.
(Note that this definition does not depend on the choice of $F'$.)
\end{definition}

The following theorem is a key to the proof of our main results.

\begin{theorem}
\label{MTp}
Let $S$ be a subset of $\mbb{Q} \smallsetminus  \{0 \}$.
Let $V$ be a
semi-stable $\mbb{Q}_p$-representation of $G_K$ with
Hodge-Tate weights in $[h_1,h_2]$.

Assume that $V$ has Weil weights in $S$ and
$V^{\mrm{Gal}(\overline{K}/L)}\not=0$ for some finite extension $L/Kk_{\pi}$. Then

\noindent
{\rm (1)}  $\mrm{Nr}_{k/\mbb{Q}_p}(\pi)$
is a $q$-Weil number of weight $-w/h$
for some $w\in S$ and some non-zero
$h\in [h_1,h_2]\bigcap \left( \bigcup_{1\le s\le e_G} (1/sd_G) \mbb{Z}\right)$.

\noindent
{\rm (2)} If the coefficients of
the characteristic polynomial of $D^K_{\mrm{st}}(V(-r))$
are algebraic integers for some integer $r$, then
we can choose $h$ in (1) so that
$q^r\mrm{Nr}_{k/\mbb{Q}_p}(\pi)^{-h}$ is an algebraic integer.
\if0
Assume that $V$ has Weil weights in $S$ and
$\mrm{Nr}_{k/\mbb{Q}_p}(\pi)$
is not a $q$-Weil number of weight $-w/h$
for some $w\in S$ and
$h\in [h_1,h_2]\bigcap \left( \bigcup_{1\le s\le e_G} (1/sd_G) \mbb{Z}\right)$.
Then we have
$V^{\mrm{Gal}(\overline{K}/L)}=0$ for any finite extension $L/Kk_{\pi}$.
\fi
\end{theorem}

\subsection{Proof of Theorem \ref{MTp}}

In this section, we prove Theorem \ref{MTp}. We begin with some lemmas.

\begin{lemma}
\label{lem0}
Let $F$ be a $p$-adic field and
$(n_{\sigma})_{\sigma\in \Gamma_F}$  a family of integers.
If there exists an open subgroup $U$ of $U_F$ with the property that
$\prod_{\sigma\in \Gamma_F} \sigma(x)^{n_{\sigma}}=1$ for any $x\in U$,
then we have $n_{\sigma}=0$ for any $\sigma\in \Gamma_F$.
\end{lemma}

\begin{proof}
Replacing $U$ by a finite index subgroup,
we may assume that the $p$-adic logarithm map is defined on $U$.
Then we have $\sum_{\sigma\in \Gamma_F} n_{\sigma}\sigma(\log x)=0$ for any $x\in U$.
Since $\log U$ is an open ideal of the ring of integers of $F$,
we obtain
 $\sum_{\sigma\in \Gamma_F} n_{\sigma} \sigma (y)=0$ for any $y\in F$.
Although the desired fact $n_{\sigma}=0$ for any $\sigma\in \Gamma_F$
follows from  Dedekind's theorem \cite[\S 6, no. 2, Corollaire 2]{Bo} immediately,
we also give a direct proof for this.
Take any $\alpha\in F$ such that $F=\mbb{Q}_p(\alpha)$
and let $\Gamma_F=\{\sigma_1=\mrm{id}, \sigma_{2},\dots ,\sigma_c \}$
where $c:=[F:\mbb{Q}_p]$.
Then we have
$(n_{\sigma_1}, n_{\sigma_2},\dots ,n_{\sigma_c})X=\mbf{0}$
where $X$ is the $c\times c$ matrix with $(i,j)$-th component
$\sigma_i(\alpha)^{j-1}$.
Since $\mrm{det}\ X=\prod_{j>i} (\sigma_j(\alpha)-\sigma_i(\alpha))\not =0$,
we obtain $n_{\sigma_1}=n_{\sigma_2}=\cdots =n_{\sigma_c}=0$.
\end{proof}

\begin{lemma}
\label{lem1}
Let $E$ be a $p$-adic field and
$V$ an $E$-representation of $G_K$.
Assume that $k/\mbb{Q}_p$ is Galois,
$V$ is Hodge-Tate and
 the $G_{Kk_{\pi}}$-action on $V$ factors through a finite quotient.
Then, there exist finite extensions $K'/K$ and $E'/E$ with $K',E'\supset k$
such that any Jordan-H\"ollder factor of $(V\otimes_E E')|_{G_{K'}}$
is of the form
$E'(\prod_{\sigma \in \Gamma_k}\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi})$
for some $r_{\sigma}\in \mbb{Z}$.
Moreover, $r_{\sigma}$ is a Hodge-Tate weight of $V$.
\end{lemma}

\begin{proof}
Replacing $K$ by a finite extension,
we may assume that
$G_{Kk_{\pi}}$ acts on $V$ trivial
and $K$ is a finite Galois extension of $k$.
Since the $G_K$-action on $V$ factors through the abelian group $\mrm{Gal}(Kk_{\pi}/K)$,
it follows from Schur's lemma that, for a finite extension $E'/E$ large enough,
any  Jordan-H\"ollder factor $W$ of $V\otimes_E E'$ is of dimension $1$.
Our goal is to show that $W$ is of   the required form.
We may assume  $E'=E\supset K$.

Let $\rho\colon G_K\to GL_E(W)\simeq E^{\times}$
be the continuous homomorphism given by the $G_K$-action on $W$.
Let $\tilde{E}$ be the Galois closure of $E/\mbb{Q}_p$ and take any
finite extension $K''/K$ which contains $\tilde{E}$.
Since $W$ is Hodge-Tate,
it follows from \cite[Chapter III,\ A.\ 5, Theorem 2]{Se} that
there exists an open subgroup $I$ of $I_{K''}$
such that $\rho=\prod_{\sigma\in \Gamma_{E}} \sigma^{-1}\circ \chi_{\sigma E}^{n_{\sigma}}$
on $I$ for some integer $n_{\sigma}$.
Here, $\chi_{\sigma E}\colon G_{\sigma E}\to U_{\sigma E}$ is the
Lubin-Tate character associated  with $\sigma E$
(it depends on the choice of a uniformizer of $\sigma E$,
but its restriction to the inertia subgroup does not).
Put $\tilde{\rho}=\prod_{\sigma\in \Gamma_{E}} \sigma^{-1}\circ \chi_{\sigma E}^{n_{\sigma}}$,
considered as a character of $G_{K''}$.
Replacing $K''$ by a finite extension,
we may assume the following:
\begin{itemize}
\item[--] $K''/\mbb{Q}_p$ is Galois,
$\mrm{Gal}(k_{\pi}/(k_{\pi}\cap K''))$ is torsion free and $\rho=\tilde{\rho}$ on $I_{K''}$.
\end{itemize}
Since  $\rho|_{G_{Kk_{\pi}}}$ is trivial,
we have that $\tilde{\rho}$ is trivial on $I_{K''}\cap G_{Kk_{\pi}}
=G_{(K'')^{\mrm{ur}}k_{\pi}}$.
Hence, putting  $N'=\mrm{Gal}((K'')^{\mrm{ur}}k_{\pi}/(K'')^{\mrm{ur}})$,
 we may regard $\tilde{\rho}|_{I_{K''}}$
as a representation of $N'$.
Put $N=\mrm{Gal}(k^{\mrm{ur}}k_{\pi}/k^{\mrm{ur}})$.
Then $N'$ is canonically isomorphic to
a torsion free finite index subgroup of $N\simeq U_k$, and thus
we regard $N'$ as a  subgroup of $N$.

Now we claim that $\tilde{\rho}\colon N'\to \tilde{E}^{\times}$ extends to
a continuous character $\hat{\rho}\colon N\to \overline{\mbb{Q}}_p^{\times}$.
It follows from the theory of elementary divisors that
we may regard
$N=N_{\mrm{tor}}\oplus (\oplus^d_{i=1} \mbb{Z}_p)\supset
\{ 0 \}\oplus (\oplus^d_{i=1} p^{m_i}\mbb{Z}_p)=N'$
with some integer $m_i\ge 0$. Here, $N_{\mrm{tor}}$ is the torsion subgroup of $N$
and $d:=[k:\mbb{Q}_p]$.
Hence it suffices to show that
any continuous character $p^m\mbb{Z}_p\to \overline{\mbb{Q}}_p^{\times}$ with $m>0$
extends to $\mbb{Z}_p\to \overline{\mbb{Q}}_p^{\times}$, but this is clear.
\if0
This follows immediately from the inflation-restriction sequence
$$
0\to H^1(\mbb{Z}_p/p^m\mbb{Z}_p, \overline{\mbb{Q}}_p^{\times})
\to H^1(\mbb{Z}_p, \overline{\mbb{Q}}_p^{\times})
\to H^1(p^m\mbb{Z}_p, \overline{\mbb{Q}}_p^{\times})
\to H^2(\mbb{Z}_p/p^m\mbb{Z}_p, \overline{\mbb{Q}}_p^{\times})
$$
and
$H^2(\mbb{Z}_p/p^m\mbb{Z}_p, \overline{\mbb{Q}}_p^{\times})
\simeq \overline{\mbb{Q}}_p^{\times}/(\overline{\mbb{Q}}_p^{\times})^{p^m}=\{1\}$.
This finishes a proof of the claim.
\fi

By local class field theory,
we may regard $\tilde{\rho}|_{I_{K''}}$ and $\hat{\rho}$
as characters of  $U_{K''}$ and $U_k$, respectively.
It follows from the construction of $\hat{\rho}$
that
we have $\tilde{\rho}(x)=\hat{\rho}(\mrm{Nr}_{K''/k}(x))$ for $x\in U_{K''}$.
In particular, we have
\begin{equation}
\label{eq:1}
\tilde{\rho}(x)=\tilde{\rho}(\tau x)\
\end{equation}
for  $x\in U_{K''}$ and $\tau\in \mrm{Gal}(K''/k)$.
On the other hand, by definition of $\tilde{\rho}$
and the condition that $K''/\mbb{Q}_p$ is Galois,
we have
\begin{equation}
\label{eq:2}
\tilde{\rho}(x)  = \prod_{\sigma\in \Gamma_{E}}
\sigma^{-1}\mrm{Nr}_{K''/\sigma E}(x^{-1})^{n_{\sigma}}
=\prod_{\tilde{\sigma}\in \Gamma_{K''}}
\tilde{\sigma}^{-1}(x^{-1})^{n_{\tilde{\sigma}}}
\end{equation}
for  $x\in U_{K''}$ where $n_{\tilde{\sigma}}:=n_{\sigma}$ if $\tilde{\sigma}|_E=\sigma$.

We claim that $n_{\tilde{\sigma}}=n_{\tilde{\sigma}'}$ if
$\tilde{\sigma}|_k=\tilde{\sigma}'|_k$.
By \eqref{eq:1} and \eqref{eq:2},
we have
\begin{equation}
\label{eq:3}
\prod_{\tilde{\sigma}\in \Gamma_{K''}}
\tilde{\sigma}^{-1}(x^{-1})^{n_{\tau\tilde{\sigma}}}
=\prod_{\tilde{\sigma}\in \Gamma_{K''}}
\tilde{\sigma}^{-1}(x^{-1})^{n_{\tilde{\sigma}}}
\end{equation}
for  $x\in U_{K''}$ and $\tau\in \mrm{Gal}(K''/k)$.
Choosing a lift $\hat{\sigma}\in \Gamma_{K''}$ for each element
of $\mrm{Gal}(k/\mbb{Q}_p)$,
we have a decomposition
$\Gamma_{K''}= \bigcup_{\hat{\sigma}} \hat{\sigma} \mrm{Gal}(K''/k)$.
Since $k/\mbb{Q}_p$ is Galois,
we see that  $\mrm{Gal}(K''/k)$ acts on
$\hat{\sigma} \mrm{Gal}(K''/k)$ stable and this action is
transitive.
By Lemma \ref{lem0}, we know that
the family $(n_{\tilde{\sigma}})_{\tilde{\sigma}\in \Gamma_{K''}}$
is determined uniquely by the restriction of
$\prod_{\sigma\in \Gamma_{K''}}
(\tilde{\sigma}^{-1})^{n_{\tilde{\sigma}}}$
to any open subgroup of $U_{K''}$.
Hence the equation \eqref{eq:3} gives  $n_{\tilde{\sigma}}=n_{\tilde{\sigma}'}$ if
$\tilde{\sigma}|_k=\tilde{\sigma}'|_k$ as desired.

For any $\sigma\in \Gamma_k$, we define
$r_{\sigma}:=n_{\tilde{\sigma}}$ for a lift $\tilde{\sigma}\in \Gamma_{K''}$
 of $\sigma$, which is independent of the choice of $\tilde{\sigma}$
by the claim just above.
Then we see
$
\tilde{\rho}(x)
=\prod_{\tilde{\sigma}\in \Gamma_{K''}}
\tilde{\sigma}^{-1}(x^{-1})^{n_{\tilde{\sigma}}}
= \prod_{\sigma\in \Gamma_k}
\sigma^{-1}\mrm{Nr}_{K''/k}(x^{-1})^{r_{\sigma}}
$
for  $x\in U_{K''}$. This implies
$$
\tilde{\rho}=
\prod_{\sigma\in \Gamma_k}
\sigma^{-1}\circ \chi_{\pi}^{r_{\sigma}}
$$
on $I_{K''}$.
Now we define  $\psi \colon G_K\to E^{\times}$
by $\psi:= \rho\cdot \left(\prod_{\sigma\in \Gamma_k}
\sigma^{-1}\circ \chi_{\pi}^{r_{\sigma}}\right)^{-1}$.
Then $\psi$ is trivial on $I_{K''}$ since $\rho=\tilde{\rho}=\prod_{\sigma\in \Gamma_k}
\sigma^{-1}\circ \chi_{\pi}^{r_{\sigma}}$ on $I_{K''}$.
Furthermore,  $\psi$ is trivial on $G_{Kk_{\pi}}$ since
$\chi_{\pi}$ and $\rho$ is trivial on $G_{Kk_{\pi}}$.
Therefore, putting $K'=(K'')^{\mrm{ur}}\cap Kk_{\pi}$,
then $K'/K$ is a finite extension and $\psi$ is trivial on $G_{K'}$.

Finally, we note that $r_{\sigma}$ is a Hodge-Tate weight of $V$
by \cite[Chapter III,\ A.5,\ Theorem 2]{Se}.
This is the end of the proof.
\end{proof}

\begin{lemma}
\label{lem1'}
Let $E$ be a $p$-adic field and
$V$ an $E$-representation of $G_K$.
Assume that $k/\mbb{Q}_p$ is Galois,
$V$ is potentially semi-stable with
Hodge-Tate weights in $[h_1,h_2]$ and
the $G_{Kk_{\pi}}$-action on $V$ factors through a finite quotient.
Then, there exists a finite extension $K'/Kk$
which satisfy the following property:
$V|_{G_{K'}}$ is semi-stable and,
for any root $\alpha$ of  the characteristic polynomial
of $D^{K'}_{\mrm{st}}(V)$,
we have
$$
\alpha=a^{f_{K'/k}},\quad
a=\prod_{\tau\in \Gamma_k} \tau(\pi)^{-n_{\tau}}
$$
for some integers $(n_{\tau})_{\tau\in \Gamma_k}$ such that
 $dh_1\le \sum_{\tau\in \Gamma_k} n_{\tau} \le dh_2$.
Here,  $d:=[k:\mbb{Q}_p]$.
\end{lemma}

\begin{proof}

By Lemma \ref{lem1}, there exist  finite extensions $K'/K$ and $E'/E$
with $E',K'\supset k$
which satisfy the following:
\begin{itemize}
\item[--] $V|_{G_{K'}}$ is semi-stable and any Jordan-H\"ollder factor $W$ of $(V\otimes_{E} E')|_{G_{K'}}$
is of the form
$E'(\prod_{\sigma \in \Gamma_k}\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi})$
for some $r_{\sigma}\in [h_1,h_2]$.
In particular, $W$ is crystalline.
\end{itemize}

Replacing $E$ by a finite extension, we may assume $E'=E$.
Now we take a root $\alpha$ of  the characteristic polynomial
of $D^{K'}_{\mrm{st}}(V)$,
and choose $W$ so that $\alpha$ is a root of the
 the characteristic polynomial
of $D^{K'}_{\mrm{cris}}(W)$.

To study $\alpha$,  we  first consider the characteristic polynomial

of $D^{K'}_{\mrm{cris}}(E(\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi}))$
for $\sigma\in \Gamma_k$.
Let $K_0'$ be the maximal unramified subextension of $K'/\mbb{Q}_p$
and put  $q'=p^{f_{K'}}$.
We note that we have an isomorphism
$k(\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi})^{\mrm{ss}}
\simeq k(\chi^{r_{\sigma}}_{\pi})^{\mrm{ss}}$
of $\mbb{Q}_p[G_{K'}]$-modules (here, ``$\mrm{ss}$'' stands for the semi-simplification of $\mbb{Q}_p[G_{K'}]$-modules).
In fact, for any $g\in G_{K'}$, we have
\begin{align*}
\mrm{Tr}_{\mbb{Q}_p}(g \mid k(\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi}))
& = \mrm{Tr}_{k/\mbb{Q}_p}
(\mrm{Tr}_{k}(g \mid k(\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi}))
= \mrm{Tr}_{k/\mbb{Q}_p}(\sigma^{-1}\chi^{r_{\sigma}}_{\pi}(g)) \\
& = \mrm{Tr}_{k/\mbb{Q}_p}(\chi^{r_{\sigma}}_{\pi}(g))
 = \mrm{Tr}_{k/\mbb{Q}_p}
(\mrm{Tr}_{k}(g \mid k(\chi^{r_{\sigma}}_{\pi}))
= \mrm{Tr}_{\mbb{Q}_p}(g \mid k(\chi^{r_{\sigma}}_{\pi})).
\end{align*}
(Here, for a representation $U$ of a group $G$ over a field $F$ and $g\in G$,
we denote by $\mrm{Tr}_F(g \mid U)$ the trace of the $g$-action on the
$F$-vector space $U$.)
Therefore, we have
\begin{equation}
\label{char2}
\mrm{det}(T-\vphi^{f_{K'}} \mid D^{K'}_{\mrm{cris}}(E(\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi})))

=\mrm{det}(T-\vphi^{f_{K'}} \mid D^{K'}_{\mrm{cris}}(k(\chi^{r_{\sigma}}_{\pi})))^{[E:k]}.
\end{equation}
To study the roots of \eqref{char2}, we recall the explicit description of
$D^k_{\mrm{cris}}(k(\chi^{-1}_{\pi}))$ (cf.\ \cite[Proposition B.4]{Con}.
See also \cite[Proposition 9.10]{Col}).
Let $k_0$ be the maximal unramified subextension of $k/\mbb{Q}_p$.
By definition, we have $f_k=[k_0:\mbb{Q}_p]$ and $q=p^{f_k}$.
Then $D^k_{\mrm{cris}}(k(\chi^{-1}_{\pi}))$ is a free $(k_0 \otimes_{\mbb{Q}_p} k)$-module
of rank one, and we can take a basis $\mbf{e}$ of  $D^k_{\mrm{cris}}(k(\chi^{-1}_{\pi}))$
such that $\vphi^{f_k}(\mbf{e})=(1\otimes \pi)\mbf{e}$.
We claim
\begin{equation}
\label{char}
\mrm{det}(T-\vphi^{f_k} \mid D^k_{\mrm{cris}}(k(\chi^{-1}_{\pi})))=\prod_{0\le i\le f_k-1}E^{\vphi^i}(T)
\end{equation}
where $E(T)=T^e+\sum^{e-1}_{j=0}a_jT^j \in k_0[T]$ is the minimal polynomial
of $\pi$ over $k_0$ and $E^{\vphi^i}(T)=T^e+\sum^{e-1}_{j=0}\vphi^i(a_j)T^j$.

To show this, it suffices to show that
the characteristic polynomial of the homomorphism
$1\otimes \pi\colon k_0\otimes_{\mbb{Q}_p} k \to k_0\otimes_{\mbb{Q}_p} k $
of  $k_0$-modules
coincides with the right hand side of \eqref{char}.
(Here, the $k_0$-action on  $k_0\otimes_{\mbb{Q}_p} k$
is given by $a.(x\otimes y):=ax\otimes y$ for $a,x\in k_0$ and $y\in k$.)
We consider a natural isomorphism
$$
k_0\otimes_{\mbb{Q}_p} k_0\simeq \oplus_{j\in \mbb{Z}/f_k\mbb{Z}} k_{0,j},\ a\otimes b\mapsto (a\vphi^j(b))_{j}
$$
where $k_{0,j}=k_0$. For $0\le s\le f_k-1$, let $e_s\in k_0\otimes_{\mbb{Q}_p} k_0$ be the element
which corresponds to $(\delta_{sj})_j\in \oplus_{j\in \mbb{Z}/f_k\mbb{Z}} k_{0,j}$
where $\delta_{sj}$ is the Kronecker delta.
Then $\{e_j(1\otimes \pi^i) \mid 0\le j\le f_k-1,\ 0\le i\le e-1\}$
is a $k_0$-basis of $k_0\otimes_{\mbb{Q}_p} k$.
We see that
the matrix of   $1\otimes \pi\colon k_0\otimes_{\mbb{Q}_p} k \to k_0\otimes_{\mbb{Q}_p} k $
associated with the ordered basis
$
\langle e_0,\dots ,e_{f_k-1},e_0(1\otimes \pi),\dots ,e_{f_k-1}(1\otimes \pi),
\dots ,e_0(1\otimes \pi^{e-1}),\dots ,e_{f_k-1}(1\otimes \pi^{e-1}) \rangle
$
is
$$
\left(
\begin{array}{cccc}
O  & O & \cdots & -A_0\\
I_{f_k}  & O & \cdots  & -A_1 \\
\vdots    & \ddots    &    & \vdots \\
O    & \cdots    &    I_{f_k}  & -A_{e-1}
\end{array}
\right)
$$
where $I_{f_k}$ is the $f_k\times f_k$ identity matrix and
$A_i$ is the $f_k\times f_k$ diagonal matrix
with diagonal entries $a_i,\vphi(a_i),\dots ,\vphi^{f_k-1}(a_i)$.
Now it is an easy exercise to check that the characteristic polynomial of this matrix
is $\prod_{0\le i\le f_k-1}E^{\vphi^i}(T)$ as desired.

By the claim \eqref{char}, we know that any root of the characteristic polynomial of
$D^{K'}_{\mrm{cris}}(k(\chi_{\pi}))$ is of the form $\tau(\pi)^{-f_{K'/k}}$
for some $\tau\in \Gamma_k$.
Hence, by \eqref{char2},
any root of the characteristic polynomial of
$D^{K'}_{\mrm{cris}}(E(\sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi}))$
is of the form $\prod_{\tau\in \Gamma_k} \tau(\pi)^{-f_{K'/k}n^{\sigma}_{\tau}}$
with $\sum_{\tau\in \Gamma_k} n^{\sigma}_{\tau} =r_{\sigma}$.
Therefore,
since $\alpha$ is a root of the characteristic polynomial of
$D^{K'}_{\mrm{cris}}(W)=
D^{K'}_{\mrm{cris}}(E(\prod_{\sigma\in \Gamma_k} \sigma^{-1}\circ \chi^{r_{\sigma}}_{\pi}))$,
we have
$$
\alpha=\prod_{\tau\in \Gamma_k} \tau(\pi)^{-f_{K'/k}n_{\tau}}
$$
with $-\sum_{\tau\in \Gamma_k} n_{\tau}
=-\sum_{\sigma\in \Gamma_k}r_{\sigma}=:R$.
We note that
$R$ is an integer such that $-dh_2\le R\le -dh_1$
since we have $r_{\sigma}\in [h_1,h_2]$.
This completes the proof.
\end{proof}

We need the following two standard lemmas which describe inclusion properties of
two Lubin-Tate extensions.

\begin{lemma}
\label{lemma:LText}
Let $k_2/k_1$ be a finite extension of $p$-adic fields
with residual extension degree $f$.
For $i=1,2$, let $\pi_i$ be a uniformizer of $k_i$
and $k_{i,\pi_i}/k_i$
the Lubin-Tate extension associated with $\pi_i$.

\noindent
{\rm (1)} We have $\mrm{Nr}_{k_2/k_1}(\pi_2)=\pi_1^{f}$
if and only if  $k_{1,\pi_1}\subset k_{2,\pi_2}$.

\noindent
{\rm (2)}  $\pi_1^{-f} \mrm{Nr}_{k_2/k_1}(\pi_2)$ is a root of unity
if and only if
there exists a finite extension $M/k_{2,\pi_2}$
such that
$k_{1,\pi_1}\subset M$.
If this is the case, we can take $M$ to be
the degree $\sharp \mu_{\infty}(k_1)$ subextension in $k^{\mrm{ab}}_2/k_{2,\pi_2}$.
Here, $\mu_{\infty}(k_1)$ is the set of roots of unity in $k_1$,
\end{lemma}

\begin{proof}
For $i=1,2$, we  denote by
$k_i^{\mrm{ur}}$ and $k_i^{\mrm{ab}}$ the maximal unramified extension of $k_i$
and the maximal abelian extension of $k_i$, respectively.
We recall that
the Artin map $\mrm{Art}_{k_i}\colon k_i^{\times}\to  \mrm{Gal}(k_i^{\mrm{ab}}/k_i)$
associated with $k_i$
satisfies
$\mrm{Art}_{k_i}(\pi_i)|_{k_{i,\pi_i}}=\mrm{id}$ and
$\mrm{Art}_{k_i}(\pi_i)|_{k_i^{\mrm{ur}}}=\mrm{Frob}_{k_i}$,
where $\mrm{Frob}_{k_i}$ is the geometric Frobenius of $k_i$.

\noindent
(1)
Suppose  $\mrm{Nr}_{k_2/k_1}(\pi_2)=\pi_1^{f}$.
For any lift $\sigma\in G_{k_2}$ of $\mrm{Art}_{k_2}(\pi_2)$, we have
$$
\sigma|_{k_{1,\pi_1}}
=(\mrm{Art}_{k_2}(\pi_2)|_{k_1^{\mrm{ab}}})|_{k_{1,\pi_1}}
=\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2))|_{k_{1,\pi_1}}
=\mrm{Art}_{k_1}(\pi_1)^f|_{k_{1,\pi_1}}
=\mrm{id}
$$
Since the intersection of the fixed fields (in $\overline{\mbb{Q}}_p$)
of such $\sigma$'s is $k_{2,\pi_2}$,
we obtain the desired result.

Conversely, suppose $k_{1,\pi_1}\subset k_{2,\pi_2}$. Then we have
$$
\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2))|_{k_{1,\pi_1}}
=\mrm{Art}_{k_2}(\pi_2)|_{k_{1,\pi_1}}
=(\mrm{Art}_{k_2}(\pi_2)|_{k_{2,\pi_2}})|_{k_{1,\pi_1}}
=\mrm{id}
$$
and
$$
\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2))|_{k_1^{\mrm{ur}}}
=\mrm{Art}_{k_2}(\pi_2)|_{k_1^{\mrm{ur}}}
=(\mrm{Art}_{k_2}(\pi_2)|_{k_2^{\mrm{ur}}})|_{k_1^{\mrm{ur}}}
=\mrm{Frob}_{k_2}|_{k_1^{\mrm{ur}}}
=\mrm{Frob}^f_{k_1}.
$$
Thus we have
$\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2))
=\mrm{Art}_{k_1}(\pi_1^f)$, which shows  $\mrm{Nr}_{k_2/k_1}(\pi_2)=\pi_1^{f}$.

\noindent
(2) A very similar proof to that of (1) proceeds.
Suppose that $\pi_1^{-f} \mrm{Nr}_{k_2/k_1}(\pi_2)$ is a root of unity.
If we denote by $h$ the order of the set of roots of unity in $k_1$,
then we have $\mrm{Nr}_{k_2/k_1}(\pi_2^h)=\pi_1^{fh}$.
We see that
any lift $\sigma\in G_{k_2}$ of $\mrm{Art}_{k_2}(\pi_2^h)$ fixes $k_{1,\pi_1}$.
This implies that $k_{1,\pi_1}$ is contained in the degree $h$ subextension in
$k^{\mrm{ab}}_2/k_{2,\pi_2}$.

Suppose that there exists a finite extension $M/k_{2,\pi_2}$
such that $k_{1,\pi_1}\subset M$. Then $M':=k_{1,\pi_1}k_{2,\pi_2}$ is
a finite subextension in  $k^{\mrm{ab}}_2/k_{2,\pi_2}$.
Put $h=[M':k_{2,\pi_2}]$.
Since $\mrm{Art}_{k_2}(\pi_2^h)|_{M'}$ is the identity map,
we have
$
\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2^h))|_{k_{1,\pi_1}}
=\mrm{id}
$
and
$
\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2^h))|_{k_1^{\mrm{ur}}}
=\mrm{Frob}^{fh}_{k_1}.
$
Thus we have
$\mrm{Art}_{k_1}(\mrm{Nr}_{k_2/k_1}(\pi_2^h))
=\mrm{Art}_{k_1}(\pi_1^{fh})$, which shows
$\mrm{Nr}_{k_2/k_1}(\pi_2^h)=\pi_1^{fh}$.

\end{proof}

We recall that  $k_G$ is the Galois closure of
$k/\mbb{Q}_p$ and $d_G:=[k_G:\mbb{Q}_p]$.

\begin{lemma}
\label{lemma:gal}
There exist a finite unramified extension $k'/k_G$
and a uniformizer $\pi'$ of $k'$
which satisfy the following.
\begin{itemize}
\item $\mrm{Nr}_{k'/k}(\pi')=\pi^{f_{k'/k}}$,
\item $k_{\pi}\subset k'_{\pi'}$, where $k'_{\pi'}$ is the Lubin-Tate extension of $k'$
associated with $\pi'$,
\item the extension $k'/\mbb{Q}_p$ is Galois, and
\item $[k':\mbb{Q}_p]=sd_G$ for some integer $1\le s\le e_G$.
\end{itemize}
\end{lemma}

\begin{proof}
Let $k_{G,0}/k$ be the maximal unramified subextension in $k_G/k$.
By \cite[Chapter V, \S 6, Proposition 10]{Se},
there exists an unramified extension $\tilde{k}_0$ over $k_{G,0}$
of degree at most $[k_G:k_{G,0}](=e_G)$ such that
$\pi=\mrm{Nr}_{k'/\tilde{k}_0}(\pi')$
for some $\pi'\in (k')^{\times}$, where
$k':=k_G\tilde{k}_0$.
Since $k_G/\mbb{Q}_p$ is Galois and
$k'/k_G$ is unramified,
we see that $k'/\mbb{Q}_p$ is Galois.
We also see that $\pi'$ is a uniformizer of $k'$.
Since $k_G\cap \tilde{k}_0=k_{G,0}$,
we have $[k':k_G]=[\tilde{k}_0:k_{G,0}]\le e_G$.
Thus we obtain $[k':\mbb{Q}_p]=[k':k_G][k_G:\mbb{Q}_p]=sd_G$
for some integer $1\le s\le e_G$.
Furthermore, we have
$\mrm{Nr}_{k'/k}(\pi')
=\mrm{Nr}_{\tilde{k}_0/k}(\mrm{Nr}_{k'/\tilde{k}_0}(\pi'))
=\mrm{Nr}_{\tilde{k}_0/k}(\pi)
=\pi^{f_{k'/k}}$.
By Lemma \ref{lemma:LText},
we have $k_{\pi}\subset k'_{\pi'}$.
\end{proof}

Now we are ready to prove Theorem \ref{MTp}.

\begin{proof}[Proof of Theorem \ref{MTp}]
First we consider the case where $k/\mbb{Q}_p$ is Galois.
Replacing $L$ by a finite extension,
we may assume that
$L/K$ is Galois. Then $V^{G_L}$ is a $G_K$-stable submodule of $V$.
By Lemma \ref{lem1'},
there exists a finite extension  $K'/Kk$
such that
any root $\alpha$
of the characteristic polynomial of
$D^{K'}_{\mrm{st}}(V^{G_L})$
is of the form
$$
\alpha=a^{f_{K'/k}},\quad
a=\prod_{\tau\in \Gamma_k} \tau(\pi)^{-n_{\tau}}
$$
with some integers $(n_{\tau})_{\tau\in \Gamma_k}$
such that $dh_1\le \sum_{\tau\in \Gamma_k} n_{\tau}\le dh_2$.
Here, $d:=[k:\mbb{Q}_p]$.
Put $R:=-\sum_{\tau\in \Gamma_k} n_{\tau}$.
Then we have
\begin{equation}
\label{norm}
\prod_{\sigma\in \Gamma_k} \sigma(a)=
\prod_{\tau\in \Gamma_k} \prod_{\sigma\in \Gamma_k} \sigma \tau(\pi)^{-n_{\tau}}
=\prod_{\tau\in \Gamma_k} \mrm{Nr}_{k/\mbb{Q}_p}(\pi)^{-n_{\tau}}
=\mrm{Nr}_{k/\mbb{Q}_p}(\pi)^R.
\end{equation}
Since $V^{G_L}$ has Weil weights in $S$,
we see that $\sigma(a)$ is a $q$-Weil number of weight $w\in S$
for any $\sigma\in \Gamma_k$.
Thus it follows from the condition $w\not=0$ and the equation \eqref{norm}
that we have $R\not=0$.
Therefore, we obtain that
$\mrm{Nr}_{k/\mbb{Q}_p}(\pi)$ is a $q$-Weil number of weight $-w/h$
where $h:=-R/d\in [h_1,h_2]\cap (1/d)\mbb{Z}$.
This shows Theorem \ref{MTp} (1).
Now Theorem \ref{MTp} (2) follows from the fact that we have
$(q^r\mrm{Nr}_{k/\mbb{Q}_p}(\pi)^{-h})^d=\mrm{Nr}_{k/\mbb{Q}_p}(q^ra)$
and $(q^ra)^{f_{K'/k}}=q_{K'}^r\alpha$ is a root of
the characteristic polynomial of $D^K_{\mrm{st}}(V(-r))$.
Thus we obtained a  proof of Theorem \ref{MTp} in the case where $k/\mbb{Q}_p$ is Galois.

Next we consider the case where $k/\mbb{Q}_p$ is not necessarily Galois.
Take a finite extension $k'/k_G$ and a uniformizer $\pi'$ of $k'$
as in Lemma \ref{lemma:gal}.
Put $d'=[k':\mbb{Q}_p]$.
We have $d'=sd_G$ for some $1\le s\le e_G$.
Let $q'$ be the order of the residue field of $k'$.
Let $L'$ be the composite field of $L$ and $k'_{\pi'}$,
which is a finite extension of $Kk'_{\pi'}$.
Assume that $V^{G_L}$ is not zero.
Since $V^{G_{L'}}$ is also not zero
and the extension $k'/\mbb{Q}_p$ is Galois,
we know that
$\mrm{Nr}_{k'/\mbb{Q}_p}(\pi')$
is a $q'$-Weil number of weight  $-w/h$
for some $w\in S$ and $h \in [h_1,h_2]\cap (1/d')\mbb{Z}$.
By the equation $\mrm{Nr}_{k'/k}(\pi')=\pi^{f_{k'/k}}$,
we have $\mrm{Nr}_{k'/\mbb{Q}_p}(\pi')
=(\mrm{Nr}_{k/\mbb{Q}_p}(\pi))^{f_{k'/k}}$,
and hence
$\mrm{Nr}_{k/\mbb{Q}_p}(\pi)$
is a $q$-Weil number of weight
$-w/h$.
Furthermore, we have
$q'^{r}\mrm{Nr}_{k'/\mbb{Q}_p}(\pi')^{-h}
=(q^{r}\mrm{Nr}_{k/\mbb{Q}_p}(\pi)^{-h})^{f_{k'/k}}$.
This completes the proof of
Theorem \ref{MTp}.
\end{proof}

\subsection{Proofs of Theorems \ref{MC} and  \ref{MTp:var}}
We  prove Theorems \ref{MC} and  \ref{MTp:var} in the Introduction.
We start with a proof of Theorem \ref{MTp:var}.

\begin{proof}[Proof of Theorem \ref{MTp:var}]
Let the notation be as in the theorem.
Replacing $K$ by a finite extension,
we may assume that $X$ has good reduction over $K$.
Then  we know that $V$ is crystalline
with Hodge-Tate weights in $[-i+r,r]$.
Let $K_0$ be the maximal unramified subextension of $K/\mbb{Q}_p$.
Put $q_K=p^{f_{K}}$, the order of the residue field of $K$.
By Theorem \ref{MTp},
it suffices to show that the characteristic polynomial of
$D^{K}_{\mrm{cris}}(H^i_{\aet}(X_{\overline{K}},\mbb{Q}_p))$
has integer coefficients and its roots are $q_K$-Weil numbers of weight $i$.
Let $Y$ be the special fiber of
a proper smooth model of $X$ over the integer ring of $K$.
By the crystalline conjecture shown by Faltings (cf.\ \cite{Fa}),
we have an isomorphism
$D^{K}_{\mrm{cris}}(H^i_{\aet}(X_{\overline{K}},\mbb{Q}_p))
\simeq K_0\otimes_{W(\mbb{F}_{q_K})} H^i_{\mrm{cris}}(Y/W(\mbb{F}_{q_K}))$
of $\vphi$-modules over $K_0$.
It follows from Corollary 1.3 of \cite{CLS}
(cf.\ \cite[Theorem 1]{KM} and \cite[Remark 2.2.4 (4)]{Na})
that the characteristic polynomial of
$K_0\otimes_{W(\mbb{F}_{q_K})} H^i_{\mrm{cris}}(Y/W(\mbb{F}_{q_K}))$ coincides with
$\mrm{det}(T-\mrm{Frob}_{\mbb{F}_{q_K}}\mid H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell}))$
for any prime $\ell \not =p$.
Hence the result follows by the Weil Conjecture (cf.\ \cite{De1}, \cite{De2}).
\end{proof}

Finally, we prove Theorem \ref{MC}.
Let
$A$ be an abelian variety over a $p$-adic field $K$ and let $\ell$ be any prime number.
We denote by $T_{\ell}(A)$  the $\ell$-adic Tate module of $A$
and set $V_{\ell}(A):=T_{\ell}(A)\otimes_{\mbb{Z}_{\ell}} \mbb{Q}_{\ell}$.
It is well-known that
we have   $G_K$-equivalent isomorphisms
$V_{\ell}(A)\simeq H^1_{\aet}(A_{\overline{K}},\mbb{Q}_{\ell})^{\vee}$

and $V_{\ell}(A)/T_{\ell}(A)\simeq A(\overline{K})[\ell^{\infty}]$.
Here, $g$ is the dimension of $A$ and
 $A(\overline{K})[\ell^{\infty}]$
is the $\ell$-power torsion subgroup of $A(\overline{K})$.
Furthermore, for an algebraic extension $L/K$,
the $\ell$-power torsion subgroup $A(L)[\ell^{\infty}]$ of $A(L)$ is finite
if and only if $V_{\ell}(A)^{G_L}=0$.
Below we denote by $L$ any finite extension of $Kk_{\pi}$.
Assume that $A$ has potential good reduction
and $N_{k/\mbb{Q}_p}(\pi)$ satisfies the condition in the statement of Theorem  \ref{MC}.
For the proof of Theorem  \ref{MC}, it is enough to show that
both the $p$-part and
the prime-to-$p$ part of $A(L)_{\mrm{tor}}$ are finite. \\

\noindent
{\bf Finiteness of the $p$-part of $A(L)_{\mrm{tor}}$ : }
If we put $W=V_p(A)^{G_L}$, then it is enough to show $W=0$.
Replacing $L$ by a finite extension,
we may suppose that the extension $L/K$ is Galois.
Then the $G_K$-action on $V_p(A)$ preserves  $W$, and thus
the dual representation $W^{\vee}$ of $W$ is a quotient
representation of $H^1_{\aet}(A_{\overline{K}},\mbb{Q}_p)$.
By Theorem \ref{MTp:var}, we have $W^{\vee}=(W^{\vee})^{G_L}=0$,
which implies $W=0$ as desired. \\

\noindent
{\bf Finiteness of the prime-to-$p$ part of $A(L)_{\mrm{tor}}$ : }
The finiteness of the prime-to-$p$ part of $A(L)_{\mrm{tor}}$
immediately  follows from the following more general proposition.

\begin{proposition}
\label{ell-adic}
Let $X$ be a proper smooth variety over  a $p$-adic field $K$
with potential good reduction.
For any prime number $\ell\not=p$,
let  $V$ be a $G_K$-stable subquotient of
$H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell}(r))$.
Let $L/\mbb{Q}_p$ be an algebraic extension with finite residue field.
Assume $i\not=2r$.

\noindent
{\rm (1)} We have $V^{G_L}=0$ for any $\ell \not=p$.

\noindent
{\rm (2)} Let $T$ be a  $G_K$-stable $\mbb{Z}_{\ell}$-lattice of $V$.
Then we have $(V/T)^{G_L}=0$ for almost all $\ell$.
\end{proposition}

\begin{proof}
This is essentially shown in Section 4 of \cite{KT}
but we give a proof here for the sake of completeness.
Replacing $K$ and $L$ by finite extensions,
we may assume that $X$ has good reduction over $K$.

The $G_L$-action on $V$ factors through
$G_{\mbb{F}_{q_L}}$ where $q_L$ is the order of the residue field of
$L$.
Let
$\mrm{Frob}_{L}\in G_{\mbb{F}_{q_L}}$ be the geometric Frobenius.
Put $P_{\ell}(T)=\mrm{det}(T-\mrm{Frob}_L\mid V)$ and
$Q_{\ell}(T)=\mrm{det}(T-\mrm{Frob}_L\mid H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell}(r)))$.
Clearly $P_{\ell}(T)$ divides $Q_{\ell}(T)$.
By the Weil Conjecture, $Q_{\ell}(T)$ is independent of the choice of $\ell\not=p$,
the coefficients of $Q_{\ell}(T)$  are in $\mbb{Z}[1/q_L]$
and the roots of $P(T)$ are $q_L$-Weil numbers of weight $i-2r$.
Since $i\not= 2r$, we know $Q_{\ell}(1)\not=0$ and then $P_{\ell}(1)\not=0$.
This in particular shows (1).
To show (2),  it suffices to show
$(T/\ell T)^{G_L}=0$ for almost all $\ell\not =p$.
Take  any prime number $\ell \not=p$ which is prime to $P_{\ell}(1)$.
For any root $\alpha$ of $P_{\ell}(T)$, we know that $\alpha-1$ is a rational number
and is an $\ell$-adic unit.
It follows from this fact that
the action of $\mrm{Frob}_{L}$ on $T/\ell T$
does not have eigenvalue one, which implies $(T/\ell T)^{G_L}=0$.
\end{proof}

Therefore, we obtained the proof of Theorem  \ref{MC}.

\begin{remark}
\label{normcondi}
(This is pointed out by Yuichiro Taguchi.)
We can construct an example which gives a negative answer
to the question given in the Introduction for good reduction case.
Let $E$ be an elliptic curve over $\mbb{Q}$ with complex multiplication
by the full ring of integers $\cO_F$ of an imaginary quadratic field $F$.
Let $\psi=\psi_{E/F}$ be the Gr\"ossencharacter
associated with $E$.
Let $p$ be a prime number such that $E$ has good ordinary reduction
and $\mfrak{p}$ a prime ideal of $\cO_F$ above $p$.
If we set $\pi:=\psi(\frak{p})$, then
$\pi$  is a generator of $\mfrak{p}$  and we have $p=\pi \bar{\pi}$.
Here, $\bar{\pi}$ is the complex conjugation of $\pi$.
Note that $\pi$ is a $p$-Weil number of weight $1$.
Let $K=k$ be the completion of $F$ at $\mfrak{p}$.
By definition, we have  $K=k=\mbb{Q}_p$
and $\pi$ is a uniformizer of them.
If we identify a decomposition group of $G_F$ at $\mfrak{p}$ with $G_K$,
then the action of $G_K$ on the set of $\pi$-power torsion points of $E(\overline{K})$
is given by the Lubin-Tate character $\chi_{\pi}$ associated with $\pi$.
In particular, we see that $E(Kk_{\pi})[p^{\infty}]$ is infinite.
\end{remark}

\if0
\begin{proposition}
\label{ell-adic}
Let $X$ be a proper smooth variety over  a $p$-adic field $K$
with potential good reduction.
For any prime number $\ell\not=p$ and any integer $i\not=0$,
let  $V$ be a $G_K$-stable subquotient of either
$H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell})$
 or $H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell})^{\vee}$.
Let $L/\mbb{Q}_p$ be an algebraic extension with finite residue field.

\noindent
{\rm (1)} We have $V^{G_L}=0$ for any $\ell \not=p$.

\noindent
{\rm (2)} Let $T$ be a  $G_K$-stable $\mbb{Z}_{\ell}$-lattice of $V$.
Then we have $(V/T)^{G_L}=0$ for almost all $\ell$.
\end{proposition}

\begin{proof}
This is essentially shown in Section 4 of \cite{KT}
but we give a proof here for the sake of completeness.
We consider only the case where $V$ is a
$G_K$-stable subquotient of
$H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell})$.
(A proof for the case where $V$ is a
$G_K$-stable subquotient of
$H^i_{\aet}(X_{\overline{K}},\mbb{Q}_p)^{\vee}$
proceeds by almost the same argument.)
We may assume $0<i\le 2\mrm{dim}(X)$.
We may reduce a proof to the case where
 $X$ has good reduction over $K$.

Then the $G_L$-action on $V$ factors through
$G_{\mbb{F}_{q_L}}$ where $q_L$ is the order of the residue field of
$L$.
Let
$\mrm{Frob}_{L}\in G_{\mbb{F}_{q_L}}$ be the geometric Frobenius.
Put
$P(T)=\mrm{det}(T-\mrm{Frob}_L\mid H^i_{\aet}(X_{\overline{K}},\mbb{Q}_{\ell}))$.
By the Weil Conjecture, $P(T)$ is independent of the choice of $\ell\not=p$,
the coefficients of $P(T)$  are integers
and the roots of $P(T)$ are $q_L$-Weil numbers of weight $i$.
Put $P_{\ell}(T)=\mrm{det}(T-\mrm{Frob}_L\mid V)$.
Clearly $P_{\ell}(T)$ divides $P(T)$.
Since $i\not= 0$, we know $P(1)\not=0$ and then $P_{\ell}(1)\not=0$.
This in particular shows (1).
To show (2),  it suffices to show
$(T/\ell T)^{G_L}=0$ for almost all $\ell\not =p$.
Take  any prime number $\ell$ which is prime to $P(1)$.
For any root $\alpha$ of $P(T)$, we know that $\alpha-1$ is prime to $\ell$.
It follows from this fact that
the action of $\mrm{Frob}_{L}$ on $T/\ell T$
does not have eigenvalue one, which implies $(T/\ell T)^{G_L}=0$.
\end{proof}
\fi


TITLE: A question on measure space and measurable function
QUESTION [2 upvotes]: Let $(X,\mu)$ be a measure space and $\mu(X)< + \infty$, $\phi$ be a bounded linear functor on  $L^1(\mu)$. Prove that there exists a positive measure $\lambda$ on $X$ such that $\phi(f) = \int_X f d\lambda$ for any $f \in L^1(\mu)$.

This appears like Riesz representation theorem to me. But I don't know how to do it.
Thank you very much.

REPLY [2 votes]: If $\lambda$ works, then $\lambda(A)=\phi(\chi_A)$ for all $A$ measurable (as the measure is finite, $\chi_A\in L^1(\mu)$).
So we define $\lambda(A):=\phi(\chi_A)\geqslant 0$. It defines a set function, with $\lambda(\emptyset)=0$. $\sigma$-additivity is a consequence of monotone convergence theorem.


TITLE: Prove that $f$ having a limit at $0$ implies that $f$ has a limit at every real number
QUESTION [5 upvotes]: Assume $ f: \mathbb{R} \to \mathbb{R}$ is such that $f(x+y)=f(x)f(y)$ ( The class of exponential functions has this property). Prove that $f$ having a limit at $0$ implies that $f$ has a limit at every real number and is one, or $f$ is identically $0$ for every $ x \in \mathbb{R}$
This is what I have so far. I know we can demonstrate this using the exponential function where $$f(0)=a^0=1$$
Hence $$f(x+0)=f(x)f(0)=a^x*a^0=a^x=f(x)$$
If $f$ is continuous at $0$ then $$\lim_{h\to 0}f(x+h)=\lim_{h\to 0}f(x)f(h)=f(x)$$
Making $f$ continuous.
Can someone please guide me?

REPLY [1 votes]: For the second, set $y=0$ and get $\forall xf(x)=f(x)f(0)$.  If there is any number $x$ such that $f(x) \ne 0$ we get that $f(0)=1$


TITLE: Trace of non-commutable matrices
QUESTION [11 upvotes]: Let $M_1$ and $M_2$ be two symmetric $d\times d$ matrices. What is the relationship between
$tr(M_1M_2M_1M_2)$ and $tr(M_1^2 M_2^2 )$?
P.S. I tried a few examples and found
$$
tr(M_1M_2M_1M_2) \le tr(M_1^2 M_2^2 )
$$
seems always true. Is there a theorem?

REPLY [10 votes]: Not to take anything away from Suvrit's answer, but this is actually much simpler. First, we can assume $M_1$ is diagonal. Call it $diag(x_1, \dotsc, x_i).$
Then the difference between the LHS and the RHS is
$$\sum_{i> j} a_{ij}^2 (x_i - x_j)^2,$$
where the $a_{ij}$ are the entries of $M_2.$


TITLE: Proving that inversions are isometries with respect to the hyperbolic metric.
QUESTION [3 upvotes]: I'd like to prove that the standard inversion $$(r,\theta)\mapsto\left(\frac{1}{r},\theta\right)$$ is an isometry with respect to the hyperbolic metric on the upper half-plane, and it would be nice to me to do the calculations using polar coordinates. First of all, I compute the length element in polar coordinates:
since $x=r\cos\theta$ and $y=r\sin\theta$ we get $dx=dr\cos\theta-r\sin\theta d\theta$ and $dy=dr\sin\theta+r\cos\theta d\theta$, so that $$\frac{dx^2+dy^2}{y^2}=\frac{dr^2+r^2d\theta^2}{r^2\sin^2\theta}.$$
Now, call $(u,v)=\left(1/r,\theta\right)$ and compute $du=-dr/r^2$ and $dv=d\theta$. Therefore, the new length element expressed in polar coordinate is
$$\frac{du^2+dv^2}{v^2}=\left(\frac{dr^2}{r^4}+d\theta^2\right)\frac{1}{d\theta^2}=\frac{dr^2+r^4d\theta^2}{r^4d\theta^2},$$ which is not equal to the previous one. I guess that I'm wrong when I define $(u,v)$ directly in terms of polar coordinates, but I don't know how to fix it.
Could you help me with that? Thanks.

REPLY [2 votes]: You wouldn't compute $(dr^2+d\theta^2)/\theta^2$ for anything, so why would you compute $(du^2+dv^2)/v^2$ as you've defined the variables? Instead, you want your hyperbolic formula with $u,v$ replacing $r,\theta$:
$$u=\frac{1}{r},\; v=\theta:\quad \frac{du^2/u^2+dv^2}{\sin^2v} \;\text{ while }\; du^2\frac{1}{u^2}=\left(-\frac{dr}{r^2}\right)^2\frac{1}{(1/r)^2}=\frac{dr^2}{r^2} \;\text{ and }\; dv=d\theta. $$


TITLE: Interchange between Integral and Sup?
QUESTION [6 upvotes]: What is the analysis theorem that gives interchange between Integral and Sup. In particular, let $f_r (t)$ be a function on the circle $U = \{z\in \mathbb C: | z | = 1\}$, which condition must check $f_r (t)$ so that we can interchange Integral and sup:
$$\sup_{0\leq r<1}\int_{\mathbb U}f_r(t)  \, dt = \int_{\mathbb U}\,  \sup_{0\leq r<1} f_r(t)  \, dt\quad ?$$
Thank you in advance

REPLY [1 votes]: We have from the property of $\sup$:
$$\forall r\in[0,1):~~~f_r(t)=\sup_{0\leq r<1}f_r(t)$$
in your question you suppose that the supremum of integrable functions is integrable, then with integration over $U$
$$\forall r\in[0,1):~~~\int_{U}f_r(t)dt=\int_{U}\sup_{0\leq r<1}f_r(t)dt$$
this gives
$$\sup_{0\leq r<1}\int_{U}f_r(t)dt=\int_{U}\sup_{0\leq r<1}f_r(t)dt$$
because $\int_{U}\sup_{0\leq r<1}f_r(t)dt$ is an upper bound for $\int_{U}f_r(t)dt$ where $0\leq r<1$.