text:
\begin{document}

\title{Determining role of Krein signature for three-dimensional Arnold tongues of
oscillatory dynamos}

\author{Oleg N. Kirillov}

 \email{kirillov@dyn.tu-darmstadt.de}

\affiliation{
Technische Universit\"at Darmstadt, D-64289 Darmstadt, Germany\\
}

\author{Uwe G\"unther}
\email{u.guenther@fzd.de}
\author{Frank Stefani}
\email{f.stefani@fzd.de}
\affiliation{
Forschungszentrum Dresden-Rossendorf, P.O. Box 510119, D-01314 Dresden, Germany\\
                 }

\date{\today}

\begin{abstract}

Using a homotopic family of boundary eigenvalue problems for the
mean-field $\alpha^2$-dynamo with helical turbulence parameter
$\alpha(r)=\alpha_0+\gamma\Delta\alpha(r)$ and homotopy parameter
$\beta \in [0,1]$, we show that the underlying network of diabolical
points for Dirichlet (idealized, $\beta=0$) boundary conditions
substantially determines the choreography of eigenvalues and thus
the character of the dynamo instability for Robin (physically
realistic, $\beta=1$) boundary conditions. In the
$(\alpha_0,\beta,\gamma)-$space the Arnold tongues of oscillatory
solutions at $\beta=1$ end up at the diabolical points for
$\beta=0$. In the vicinity of the diabolical points the space
orientation of the 3D tongues, which are cones in first-order
approximation, is determined by the Krein signature of the modes
involved in the diabolical crossings at the apexes of the cones. The
Krein space induced geometry of the resonance zones explains the
subtleties in finding $\alpha$-profiles leading to  spectral
exceptional points, which are important ingredients in recent
theories of polarity reversals of the geomagnetic field.

\end{abstract}

\pacs{91.25.Cw, 91.25.Mf, 02.30.Tb, 02.40.Xx, 05.45.-a}

\keywords{oscillatory MHD dynamo, geomagnetic field reversals, exceptional points, Arnold's tongues, perturbation}

\maketitle

\section{Introduction}

Polarity reversals of the Earth's magnetic field have fascinated
geophysicists since their discovery by David and Brunhes
\cite{B1906} a century ago.
While the last reversal occurred approximately
780000 years ago, the mean reversal rate (averaged over the last
few million years) is approximately 4 per Myr.
At least two, but very likely  three \cite{COURTILLOT}
superchrons have been identified
as ''quiet'' periods of some tens of millions of years showing
no reversal at all.

The reality of reversals is quite complex and there
is little hope to understand all their details within a simple
model. Recent computer simulations of the geodynamo in
general and of reversals in particular \cite{G2002,WICHTOLSON,TAKAHASHI}
have progressed much since the first fully coupled  3D simulations
of a reversal by Glatzmaier and Roberts in 1995 \cite{GLRO1995}.
Most interestingly, polarity reversals were also
observed in one \cite{BERHANU} of the recent liquid sodium
dynamo experiments which have flourished during the last decade
\cite{RMP,ZAMM}.

However, it is important to note
that neither in simulations
nor in experiments it is possible to accommodate all
dimensionless parameters of the geodynamo
\cite{GUBBINS}, and many of them are not even well known
\cite{ROGLA2}. In an interesting attempt to bridge the gap
of several orders of magnitude between realistic and numerically
achievable parameters, Christensen and Aubert \cite{CHRAUBERT}
were able to identify remarkable  scaling laws for some appropriate
non-dimensional numbers.

The use of appropriate simplified models
\cite{MELBOURNE,HOYNG,RYAN,LUCA}
represents another attempt to understand better
the basic principle and the typical features of reversals.
Most prominent among those features  are the
distinct asymmetry (with a slow decay and a fast recovery phase)
\cite{VMG2005}, the clustering property of reversal events \cite{C2006},
and the appearance of several maxima (at multiples of ~95 kyr)
of the residence time distribution
which has been explained in terms of a stochastic resonance phenonemon
with the Milankovic cycle of the Earth's orbit excentricity
\cite{CONSOLINI,LORITO}.

One of the simplest reversal models which seems capable to explain
all those three reversal features in a consistent manner \cite{EPJB,IP}
relies basically on
the existence of an exceptional point in the spectrum of the
non-self-adjoint dynamo operator, where two real
eigenvalues coalesce and continue as a complex conjugated pair of
eigenvalues. The importance of the specific
interplay between oscillatory and non-oscillatory modes
for the reversal mechanism had been early expressed by Yoshimura
\cite{YOSHI}, Sarson and Jones \cite{SAJO}, and Gubbins and Gibbons
\cite{GUGI}.
In the framework of a simple mean-field $\alpha^2$-dynamo with
a spherically symmetric helical turbulence parameter $\alpha$
it was possible to identify reversals
as noise-triggered relaxation
oscillations in the vicinity of an exceptional point
\cite{SG2005,EPSL,S2007}.
The key point is that the exceptional point is associated with a nearby
local maximum of the
growth rate situated at a slightly lower magnetic Reynolds number.
It is the negative slope of the growth rate curve between this local
maximum and the exceptional point that makes stationary
dynamos vulnerable to  noise. Then, the instantaneous
eigenvalue is driven towards the exceptional point and beyond into the
oscillatory branch where the sign change of the dipole polarity happens.
Therefore, the existence of an exceptional point
is an essential ingredient for reversals, although non-linear
dynamics and the influence of noise must be invoked for a more
detailed understanding of those events.

From the spectral point of view, the reversal phenomenon of the
geomagnetic field is strongly linked to other fields of physics,
like van-der-Pol like oscillators \cite{vdP1926}, geometric phases
\cite{MKS2005}, $\mathcal{PT}$-symmetric quantum mechanics
\cite{Ben2007,Grae2008}, $\mathcal{PT}$-symmetric optical waveguides
\cite{PT-opt2008}, microwave resonators \cite{D2003}, and
dissipation-induced instabilities \cite{B56,M2005,K2008}.

A particular problem of all those systems in which exceptional
points are involved is a strong sensitivity of the eigenvalues on
boundary conditions (BCs).
As for the geodynamo, the periodic
occurrence of so-called superchrons is usually  attributed to the
changing thermal BCs at the core-mantle boundary \cite{COURTILLOT}, but
the growth of the inner core may also play a role \cite{S2007} by
virtue of a spectral resonance phenomenon \cite{GK2006}.

In this context it is worthwhile to note that
important features of dynamos are most easily understandable when
treated with idealized (i.e. non-physical) boundary conditions.
This was the case for explaining the famous eigenvalue symmetry
between dipole and quadrupole modes as it was done by Proctor in 1977
\cite{PROCTOR1,PROCTOR2}.

Standing in this tradition, the present paper is devoted to a
better understanding of the interplay of BCs, the spectral
resonance phenomenon and oscillatory regimes in  dynamos.

\section{Mathematical setting}

The mean field MHD $\alpha^2-$dynamo \cite{krause-1} in its
kinematic regime is described by a {\em linear} induction equation
for the magnetic field. For spherically symmetric $\alpha-$profiles
$\alpha(r)$ the vector of the magnetic field is decomposed into
poloidal and toroidal components and expanded in spherical harmonics
with degree $l$ and order $m$. After additional time separation, the
induction equation reduces to a set of $l-$decoupled boundary
eigenvalue problems \cite{GK2006}, which we write in a matrix form,
convenient for the implementation of the perturbation theory
\cite{MBO97,KS04}
\be{p1}
{\bf L}\bbf:={\bf l}_0\partial_r^2 \bbf + {\bf l}_1\partial_r\bbf +
{\bf l}_2\bbf=0,\quad \fU\ff=0.
\ee
The matrices in the differential expression $\bf L$ are
\ba{p2}
{\bf l}_0&=&\left(
\begin{array}{cc}
  1 & 0 \\
  -\alpha(r) & 1 \\
\end{array}
\right),\quad
{\bf l}_1=\partial_r {\bf l}_0,\nn \\
{\bf l}_2&=&
\left(
\begin{array}{cc}
  -\frac{l(l+1)}{r^2}-\lambda & \alpha(r) \\
  \alpha(r)\frac{l(l+1)}{r^2} & -\frac{l(l+1)}{r^2} -\lambda\\
\end{array}
\right)
\ea
and $\fU:=[\fA,\fB]\in \CC^{4\times 8}$ in the BCs consists of the
blocks
\be{p3}
\fA=\left(
\begin{array}{cccc}
  1 & 0 & 0 & 0 \\
  0 & 1 & 0 & 0 \\
  0 & 0 & 0 & 0 \\
  0 & 0 & 0 & 0 \\
\end{array}
\right),~~
\fB=\left(
\begin{array}{cccc}
  0 & 0 & 0 & 0 \\
  0 & 0 & 0 & 0 \\
  \beta l + 1 - \beta & 0 & \beta & 0 \\
  0 & 1 & 0 & 0 \\
\end{array}
\right).
\ee
The vector-function $\bbf\in \tilde{\cH}=L_2(0,1)\oplus L_2(0,1)$
lives in the Hilbert space $(\tilde{\cH},(.,.))$  with inner product
$(\bbf,\bg)=\int_0^1 \overline {\bg}^T {\bbf}\, dr$, where the
overbar denotes complex conjugation, and the boundary vector $\ff$
is given as
\be{p4}
\ff^T:=\left(\bbf^T(0),\partial_r\bbf^{T}(0),\bbf^T(1),\partial_r\bbf^{T}(1)\right)\in
\CC^{8}.
\ee

We assume that $\alpha(r):=\alpha_0+\gamma\Delta\alpha(r)$, where
$\Delta\alpha(r)$ is a smooth real function

with $\int_0^1 \Delta\alpha(r)
dr =0$. For a fixed $\Delta\alpha(r)$ the differential expression
$\bf L$ depends on the parameters $\alpha_0$ and $\gamma$, while
$\beta$ interpolates between idealized ($\beta=0$) BCs,
corresponding to an infinitely conducting exterior, and
physically realistic ones ($\beta=1$) corresponding to a
non-conducting exterior of the dynamo region  \cite{krause-1}.

    \begin{figure}
    \begin{center}
    \includegraphics[angle=0, width=0.48\textwidth]{prl-fig1c.eps}
    \end{center}
\caption{$l=0$:  (pink) spectral mesh \rf{p11} for $\gamma=0$,
$\beta=0$;\\ (dashed) eigenvalue parabolas \rf{p12} for $\gamma=0$,
$\beta=1$;\\ (black) eigenvalue branches for $\beta=0.3$,
$\Delta\alpha(r)=\cos(2\pi kr)$, and (a) $k=1$, $\gamma=2.5$, (b)
$k=2$, $\gamma=3$, with resonant overlaps near the locations of the
diabolically crossed modes having (blue) the same and (green)
different Krein signature.}
    \label{fig1}
    \end{figure}

The spectral problem \rf{p1} is not selfadjoint in a Hilbert
space, but in case of idealized BCs $(\beta=0)$ the fundamental
symmetry of the differential expression \cite{GS03,GK2006}
\be{p5}
{\bf L}_0:={\bf L}(\lambda=0)={\bf J}{\bf L}_0^\dagger {\bf J},\qquad
{\bf J}=\left(\begin{array}{cc}0 & 1\\ 1 & 0
 \end{array}\right),
\ee
makes ${\bf L}_0$ selfadjoint in a Krein space $(\cK,[.,.])$
\cite{LT} with indefinite inner product $[.,.]=({\bf J}.,.)$:
\be{p6}
[{\bf L}_0 {\bbf},{\bg}]=[{\bbf},{\bf L}_0 {\bg}], \qquad {\bbf
},{\bg} \in \cK\, .
\ee
For $\beta\neq 0$ the operator ${\bf L}_0$ is not self\-ad\-joint
even in a Krein space.

\section{From diabolic to exceptional points}

In case of constant $\alpha-$profiles $\alpha(r)\equiv
\alpha_0=$const and $\beta=0$ the spectrum and the eigenvectors of
the operator matrix ${\bf L}_0$  are \cite{GK2006}
\ba{p7}
\lambda_n^{\varepsilon}&=&\lambda_n^{\varepsilon}(\alpha_0)=-\rho_n+\varepsilon \alpha_0
\sqrt{\rho_n}\in \RR\, ,\quad \varepsilon=\pm,\nn\\
{\bbf}_n^\varepsilon&=&\left(
\begin{array}{c}
  1 \\
  \varepsilon \sqrt{\rho_n} \\
\end{array}
\right)f_n\in \RR^2\otimes L_2(0,1)\,, \quad n\in \ZZ^+
\ea
with $f_n(r)$ being normalized Riccati-Bessel functions
\be{p8}
f_n(r)=\frac{(2r)^{1/2}J_{l+\frac 12}(\sqrt{\rho_n}r)}{ |J_{l+\frac
32}(\sqrt{\rho_n})|},\quad (f_{n'},f_n)=\delta_{{n'}n}
\ee
and $\rho_n>0$  the squares of Bessel function zeros
\be{p9}
J_{l+\frac{1}{2}}(\sqrt{\rho_n})=0, \qquad
0<\sqrt{\rho_1}<\sqrt{\rho_2}<\cdots \, .
\ee
The eigenvectors $\bbf_n^+,\bbf_n^-\in \cK_\pm\subset \cK\,$
correspond to Krein space states of positive and negative signature
$\varepsilon=\pm$
\be{p10}
[\bbf_{n'}^\pm,\bbf_n^\pm ]=\pm 2 \sqrt{\rho_n}\delta_{{n'}n},~~
[\bbf_{n'}^\pm,\bbf_n^\mp]=0\, .
\ee
The spectral branches $\lambda_n^\pm$ are real-valued linear
functions of the parameter  $\alpha_0$ with signature-defined slopes
$\pm \sqrt{\rho_n}$ and form for all $l=0,1,2,\cdots$ a mesh-like
structure in the $(\alpha_0,\Re \lambda)-$plane. Spectral meshes for
neighboring mode numbers $l$ and $l+1$ have only slightly different
slopes of their branches and behave qualitatively similar under
perturbations \cite{GK2006}. Therefore basic spectral structures for
$l=1,2$ dipole and quadrupole modes can be illustrated by the
simpler but unphysical $l=0$ monopole modes which are given in terms
of trigonometric functions. The $(l=0)-$mesh built from
$\rho_n=\pi^2 n^2$ is depicted as pink lines in Fig. \ref{fig1}.

The intersection of two branches
$\lambda_{n'}^\delta,\lambda_n^\varepsilon$ with $n\neq {n'}$ occurs
at points  $(\alpha_0^{(\nu)},\lambda^{(\nu)})$ with
\be{p11}
\alpha_0^{(\nu)} :=\varepsilon \sqrt{\rho_n}+\delta
\sqrt{\rho_{n'}},\quad
\lambda^{(\nu)}:=\sigma^{(\nu)}\sqrt{\rho_n\rho_{n'}},\quad
\sigma^{(\nu)}:=\varepsilon \delta
\ee
and corresponds to double eigenvalues
$\lambda^{(\nu)}=\lambda_n^{\varepsilon}=\lambda_{n'}^{\delta}$ with
two linearly independent eigenvectors $\bbf_n^{\varepsilon}$ and
$\bbf_{n'}^{\delta}$, i.e. to so-called semi-simple eigenvalues
(diabolical points, DPs) of algebraic and geometric multiplicity two
\cite{KS04,GK2006}.

For the  $(l=0)-$mesh the diabolical crossings of the $(\varepsilon
n)$th and $(\varepsilon n + j)$th modes with the same fixed $|j|\in
\mathbb{Z^+}$ are located on a parabolic curve \cite{GK2006}
\be{p12}
\lambda(\alpha_0)=\frac{1}{4}\left(\alpha_0^2-\pi^2j^2 \right)
\ee
where $\alpha_0=\alpha_0^{(\nu)}=\pi(2n\varepsilon+j)$ and
$\lambda^{(\nu)}=\lambda(\alpha_0^{(\nu)})=\pi^2 n(n+\varepsilon
j)$. Open circles in Fig.~\ref{fig1}(a,b) indicate DPs on the
parabolas $|j|=2$  and $|j|=4$. The Krein signatures \cite{K50} of the
intersecting branches define the intersection index
$\sigma^{(\nu)}=\varepsilon\delta=\sign(\lambda^{(\nu)})$ in eqs.
\rf{p11}. Branches of different signature $\delta\neq \varepsilon$
intersect for both signs of $\alpha_0$ at $\lambda^{(\nu)} <0$
(green circles in Fig. \ref{fig1}), whereas intersections at
$\lambda^{(\nu)}
>0$  are induced by spectral branches of coinciding signatures:
for $\varepsilon=\delta=+$ at $\alpha_0>0$,
and for $\varepsilon=\delta=-$ at $\alpha_0<0$ (blue circles in
Fig.~\ref{fig1}).

For $\gamma=0$ and constant $\alpha(r)=\alpha_0$, the spectrum
remains purely real on the full homotopic family $\beta\in [0,1]$
and passes smoothly in the $(\alpha_0, \Re\lambda)-$plane from the
spectral mesh at $\beta=0$ to non-intersecting branches of simple
real eigenvalues for models with physically realistic BCs at
$\beta=1$. For the monopole model $l=0$ the full spectral homotopy
is described by the characteristic equation $
(1-\beta)\eta\left[\cos\left(\eta\right)-\cos\left(\alpha_0\right)\right]
+ 2\beta\lambda\sin\left(\eta\right)=0, $ where
$\eta(\alpha_0,\lambda)=\sqrt{\alpha_0^2-4\lambda}$, which for
physically realistic BCs $(\beta=1)$ leads to a spectrum consisting
of the countably infinite set of parabolas \rf{p12} labelled by the
index $j\in\ZZ^+$ and depicted in Fig. \ref{fig1} as dashed lines.
The reason for the $(\beta=0)-$DPs \rf{p11} to be located on the
$(\beta=1)-$parabolas \rf{p12} is that the loci of the DPs are fixed
points of the homotopy  $\forall
\beta\in[0,1]$ --- a phenomenon which indicates on their `deep imprint' in the
boundary eigenvalue problem \rf{p1}.

The eigenvalue branches with $\Re\lambda>0,\Im \lambda\neq0$
(important for the reversal mechanism \cite{SG2005,S2007}) can be
induced by deforming the constant $\alpha-$profile into an
inhomogeneous one, $\alpha(r)=\alpha_0+\gamma\Delta\alpha(r)$, with
simultaneous variation of the BCs. This process is governed by a
strong resonant correlation between the Fourier mode number of the
inhomogeneous $\Delta\alpha(r)$ and the parabola index $|j|$. This
is numerically demonstrated in Fig. \ref{fig1} (black branches) for
$\Delta\alpha(r)=\cos(2\pi k r)$ which highly selectively induces
complex eigenvalue segments  in the vicinity of DPs located on the
parabola \rf{p12} with index $j=2k$.

    \begin{figure}
    \begin{center}
    \includegraphics[angle=0, width=0.49\textwidth]{prl-fig2c.eps}
    \end{center}
\caption{$l=0$, $\Delta\alpha(r)=\cos(4\pi r)$: (a) linear
approximation of the 3D Arnold tongues and (b) their projection
onto the $(\alpha_0,\beta)-$plane  indicating the influence of the
intersection index $\sigma^{(\nu)}$ on the inclination of the
cones.}
    \label{fig2}
    \end{figure}

The underlying influence of 'hidden' DPs on real-to-complex
transitions of the spectral branches can be made transparent by
analyzing the perturbative unfolding of the DPs \cite{KS04} at the
mesh-nodes $(\alpha_0^{(\nu)},\lambda^{(\nu)})$ under variation of
the parameters $\alpha_0$, $\beta$, and $\gamma$. In first-order
approximation this gives for the  $(l=0)-$model
\be{p15}
\lambda=\lambda^{(\nu)}-\lambda^{(\nu)}
\beta+\frac{\alpha_0^{(\nu)}}{2}(\alpha_0-\alpha_0^{(\nu)}) \pm
\frac{\pi}{2} \sqrt{D},
\ee
where $\alpha_0^{(\nu)}=\pi(\varepsilon n +\delta {n'})$,
$\lambda^{(\nu)}=\varepsilon\delta\pi^2{n'}n$, and
\ba{p16}
D&:=&\left[(\varepsilon n-\delta
{n'})\left(\alpha_0-\alpha_0^{(\nu)}\right) \right]^2
\nn
\\ &+&
{n'}n\left[(\varepsilon1+\delta1)\gamma A -(-1)^{n+{n'}}(n+{n'})\beta\pi\right]^2\nn \\
&-& {n'}n\left[(\varepsilon1-\delta1)\gamma A
-(-1)^{n-{n'}}(n-{n'})\beta\pi\right]^2
\ea
with $ A:=\int_0^1 \Delta \alpha (r) \cos[(\varepsilon n - \delta
{n'})\pi r]dr. $

For $\gamma=0$ it holds $D\ge0$, confirming that the eigenvalues
remain real under variation of the parameters $\alpha_0$ and $\beta$
only. If, additionally, $\alpha_0=\alpha_0^{\nu}$, then one of the
two simple eigenvalues \rf{p15} remains fixed under first-order
perturbations with respect to  $\beta$: $\lambda=\lambda^{(\nu)}$ in
full accordance with the fixed point nature of the DP loci under the
$\beta-$homotopy. The sign of the first-order increment of the other
eigenvalue $\lambda=\lambda^{(\nu)}-2\lambda^{(\nu)}\beta$ depends
on the sign of $\lambda^{(\nu)}$ and, therefore, via \rf{p11}
directly on the Krein signature of the modes involved in the
crossing $(\alpha_0^{(\nu)},\lambda^{(\nu)})$.

In general, there exist parameter combinations yielding $D<0$ and
thus creating complex eigenvalues. Eq. \rf{p16} implies that in
first-order approximation the domain of oscillatory solutions with
${\Re}\lambda\ne0$ and ${\Im}\lambda\ne0$ in the $(\alpha_0,
\beta,\gamma)$-space is bounded by the
conical surfaces $D=0$ with  apexes at the DPs
$(\alpha_0^{(\nu)},0,0)$, as shown in Fig. \ref{fig2}.
Such domains, especially in case of $r-$periodic $\alpha-$profiles,
are in fact Arnold tongues corresponding to zones of parametric
resonance \cite{K50} in Mathieu-type equations whose analysis in \cite{A83}  was motivated  just by Zeldovich's studies on MHD dynamos.

At the boundary $D=0$ the eigenvalues are twofold degenerate and
non-derogatory, that is they have Jordan chains consisting of an
eigenvector and an associated vector. Thus, DPs in the $(\alpha_0,
\beta,\gamma)$-space unfold into 3D conical surfaces
consisting of  exceptional points (EPs).

The conical zones develop according to resonance selection rules
similar to those discovered in \cite{GK2006} for the case $\beta=0$.
For example, with $\Delta \alpha(r)=\cos(2\pi k r)$,
$k\in\mathbb{Z}$, the constant $A$ in \rf{p16} yields
\be{p18}
A= \left \{\begin{array}{r}
1/2,\quad 2k=\varepsilon n- \delta {n'} \\
0,\quad 2k\ne\varepsilon n- \delta {n'}
\end{array}
 \right.
\ee
so that in  first-order approximation only DPs located on the
$(j=2|k|)-$parabola \rf{p12} show a DP-EP unfolding (in accordance
with numerical results in Fig. \ref{fig1}). The cone apexes
correspond to $2|k|-1$ DPs with negative intersection index \rf{p11}
$\sigma^{(\nu)}=-$ and countably infinite DPs with
$\sigma^{(\nu)}=+$. The two groups are shown in Fig. \ref{fig2} in
green and blue, respectively.

The real parts of the perturbed eigenvalues are given by $\Re
\lambda=\lambda^{(\nu)}(1-
\beta)+\alpha_0^{(\nu)}\left(\alpha_0-\alpha_0^{(\nu)}\right)/2$
and for fixed $\alpha_0$ and increasing $\beta$ they are shifted
(for both groups) away from the original DP positions toward the
$(\Re\lambda=0)-$axis (cf. the numerical results in Fig. \ref{fig1})
--- an effect which is similar to the
self-tuning mechanism of field-reversals uncovered in \cite{SG2005}.

Apart from this similarity, the eigenvalues of the two cone-groups
show significant differences.  The $2|k|-1$ cones of the first
group have non-trivial intersection with the plane $\beta=0$. In
this $(\alpha_0,\gamma)-$plane the zones of decaying oscillatory
modes are $\gamma \rightleftharpoons-\gamma $ symmetric and
defined by the inequality
\be{p19} \left(\alpha_0 \pm 2\pi(n-|k|) \right)^2<
\frac{\gamma^2}{4}\left[ 1- \left(\frac{n-|k|}{|k|}
\right)^2\right],
\ee
where $n=1, 2,\ldots,|k|$. For $k=2$ there are  three primary Arnold
tongues: $4\alpha_0^2<\gamma^2$ and $16\left(\alpha_0 \pm 2\pi
\right)^2<3\gamma^2$.

    \begin{figure}
    \begin{center}
    \includegraphics[angle=0, width=0.49\textwidth]{prl-fig3ca.eps}
    \end{center}
\caption{$l=0$: numerically calculated Arnold tongues for
$\Delta\alpha(r)=\cos(2\pi k r)$, $k=2$, and $\lambda^{(\nu)}<0$
(green) or $\lambda^{(\nu)}>0$ (blue) and their approximations
(dashed lines) (a) in the $(\alpha_0,\gamma)-$plane  and (b) in the
$(\beta,\gamma)-$plane.}
    \label{fig3}
    \end{figure}

The cones of the second group meet the plane $\beta=0$ only at the
apexes, having their skirts located in the sectors
$[\beta>0,\gamma\,\sign(\alpha_0)>0]$ and
$[\beta<0,\gamma\,\sign(\alpha_0)<0]$ (cf. Fig. \ref{fig2}(b)).
Therefore, in models with idealized BCs $(\beta=0)$ complex
eigenvalues occur only in zones \rf{p19} in the
$(\alpha_0,\gamma)$-plane.

The different oscillatory behavior induced by the two cone groups
has its origin in the different Krein-signature defined inclination
of the $(D<0)-$cones with respect to the $(\beta=0)-$plane.

Passing from $\beta=0$ to a parallel $(\beta\neq0)-$plane, the
$(D<0)-$tongues \rf{p19}, corresponding to $\lambda^{(\nu)}<0$
deform into cross-sections bounded by hyperbolic curves (black
dashed lines in Fig.~\ref{fig3}(a))
\ba{p20}
-4k^2(\alpha_0\pm2\pi(n{-}|k|))^2 &+& n(2|k|{-}n)(\gamma\pm 2\pi(n{-}|k|)\beta)^2\nn\\&>&n(2|k|{-}n)4\pi^2\beta^2k^2,
\ea
with $n=1, 2,\ldots,|k|$. Since $n\le|k|$, the lines $\gamma=\pm2\pi
n\beta$ and $\gamma=\pm2\pi (n-2|k|)\beta$, bounding the
cross-sections of the 3D cones by the plane
$\alpha_0^{(\nu)}=\pm2\pi(n-|k|)$, always have the slopes of
different sign. This allows decaying oscillatory modes for $\beta=0$
due to variation of $\gamma$ only.

The $(\beta \neq 0)-$cross-sections of the cones with
$(\lambda^{(\nu)}>0)-$apexes have the form of ellipses (white dashed
lines in Fig.~\ref{fig3}(a))
\ba{p21}
~~4k^2\left(\alpha_0 \pm 2\pi(n{+}|k|) \right)^2&{+}&n(2|k|{+}n)
\left(\gamma \pm 2\pi(n{+}|k|)\beta \right)^2\nn \\ &<&n(2|k|{+}n)4\pi^2\beta^2k^2,
\ea
where $n=1,2,\ldots$.  In the $(\beta\neq 0)-$plane the ellipses are
located inside the stripe with  boundaries
$\gamma=(\alpha_0\pm2\pi|k|)\beta$ (pink lines in
Fig.~\ref{fig3}(a)), while the hyperbolas lie outside this stripe.
Moreover, since in the plane $\alpha_0^{(\nu)}=\pm2\pi(n+|k|)$ the
boundary lines $\gamma=\pm2\pi n\beta$ and $\gamma=\pm2\pi
(n+2|k|)\beta$ have slopes of the same sign, the $\gamma$-axis does
not belong to the instability domains, showing that for growing
oscillatory modes the parameters $\beta$ and $\gamma$ have to be
taken in a prescribed proportion, see Fig.~\ref{fig3}(b).

The amplitude $\gamma$ of the inhomogeneous perturbation of the
$\alpha$-profile $\gamma\Delta\alpha(r)$ is limited both from below
and from above in the vicinity of the DPs with $\sigma^{(\nu)}>0$.
However, numerical calculations indicate that this property can
persist on the whole interval $\beta\in[0,1]$,  see
Fig.~\ref{fig3}(b), in agreement with the earlier findings of
\cite{SG2003}.

\section{Conclusions}

In summary, we have found that the underlying network of DPs and
their intersection indices for
$\beta=0$ substantially determine the choreography of eigenvalues
for $\beta=1$ and, in particular, the loci of EPs which are
important to explain the reversals of the geomagnetic field.
Although this has been exemplified for the unphysical monopole ($l=0$)
mode of a simplified spherically symmetric $\alpha^2$ dynamo model,
the general idea is well generalizable to physical modes and to more
realistic dynamo models. Work in this direction is in progress.

\begin{acknowledgments}
The research of O.N.K. was supported by DFG  grant  HA 1060/43-1
as well as by the Saxon Ministry of Science grant
4-7531.50-04-844-07/8 and that of U.G. and F.S. by DFG
Sonderforschungs\-be\-reich 609.
\end{acknowledgments}

config: arxiv


TITLE: Hilbert spaces of holomorphic functions
QUESTION [2 upvotes]: Could you please give me some examples of Hilbert spaces of holomorphic functions? Or even books or notes on Hilbert spaces of holomorphic functions? I need just a good number of examples and perhaps some general properties. Thanks in advance!

REPLY [0 votes]: The most classical space of holomorphic functions is the hardy space $H^{2}(D)$, where $D$ is the open unit disk $D$ in the complex plane. A holomorphic function on $D$ is in $H^{2}(D)$ iff
$$
                  \|f\|^{2}_{H^{2}}=\sup_{0 < r < 1} \frac{1}{2\pi}\int_{0}^{2\pi}|f(re^{i\theta})|^{2}\,d\theta < \infty.
$$
Every $f \in H^{2}(D)$ automatically has an $L^{2}$ boundary limit
$$
                   f_{1}(e^{i\theta}) = L^{2}-\lim_{r\uparrow 1}f(re^{i\theta}).
$$
Furthermore, $f$ is the Cauchy integral of this boundary function. This space, and various generalizations to other domains have been studied extensively, and have proven useful in a wide wide of applications, including radar, MRI, and sending a missle to chase a target. I mention applications just to make sure Hardy is still turning over in his grave.
Reference: http://en.wikipedia.org/wiki/Hardy_space#Hardy_spaces_for_the_unit_disk


TITLE: Evaluate the limit in $p$ and $q$
QUESTION [2 upvotes]: Evaluate $$\lim_{x \to 1}\left(\frac{p}{1-x^p}-\frac{q}{1-x^q}\right)$$ where $p,q$ are natural numbers. I have run out of ideas on how do I solve the limit. The few ideas I had did not work.

REPLY [2 votes]: If you consider Laurent series built at $x=1$, you have $$\frac{1}{1-x^n}=-\frac{1}{n (x-1)}+\frac{n-1}{2 n}+\left(\frac{1}{12 n}-\frac{n}{12}\right)
   (x-1)+O\left((x-1)^2\right)$$ So $$\frac{p}{1-x^p}-\frac{q}{1-x^q}=\Big(-\frac{1}{x-1}+\frac{p-1}{2}+\left(\frac{1}{12}-\frac{p^2}{12}\right)
   (x-1)+O\left((x-1)^2\right) \Big)-\Big(-\frac{1}{x-1}+\frac{q-1}{2}+\left(\frac{1}{12}-\frac{q^2}{12}\right)
   (x-1)+O\left((x-1)^2\right)\Big)$$ that is to say $$\frac{p}{1-x^p}-\frac{q}{1-x^q}=\frac{p-q}{2}+\frac{q^2-p^2}{12} (x-1) +O\left((x-1)^2\right)$$ which gives not only the limit but also how it is approached.


text:
\begin{document}

\title{Restrictions of Brownian motion}

\author{Rich\'ard Balka}
\address{Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195-4350, USA
and Alfr\'ed R\'enyi Institute of Mathematics, Hungarian Academy of Sciences, PO Box 127, 1364 Budapest, Hungary}
\email{balka@math.washington.edu}

\author{Yuval Peres}

\address{Microsoft Research, 1 Microsoft Way, Redmond, WA 98052, USA}
\email{peres@microsoft.com}

\subjclass[2010]{Primary: 28A78, 60J65.}

\keywords{Brownian motion, Hausdorff dimension, bounded variation, H\"older continuous, restriction.}

\begin{abstract} Let $\{ B(t) \colon 0\leq t\leq 1\}$ be a linear Brownian motion and let $\dim$ denote the Hausdorff dimension.
Let $\alpha>\frac12$ and $1\leq \beta \leq 2$. We prove that, almost surely, there exists no set $A\subset[0,1]$ such that $\dim A>\frac12$
and $B\colon A\to\mathbb{R}$ is $\alpha$-H\"older continuous. The proof is an application of Kaufman's dimension doubling theorem.
As a corollary of the above theorem, we show that, almost surely, there exists
no set $A\subset[0,1]$ such that $\dim A>\frac{\beta}{2}$ and $B\colon A\to\mathbb{R}$ has finite $\beta$-variation.
The zero set of $B$ and a deterministic construction witness that the above theorems give the optimal dimensions.

\bigskip

\begin{center} { \scshape{RESTRICTIONS DU MOUVEMENT BROWNIEN}} \end{center}

\bigskip

\noindent {\scshape{R\'esum\'e}}. On note $\{B(t) \colon  0 \leq t  \leq 1 \}$ un mouvement brownien lin\'eaire et $\dim$ la dimension de Hausdorff.
Pour $\alpha> \frac 12$ et $1 \leq \beta \leq 2$ nous montrons que, presque s\^urement, il n'existe pas d'ensemble $A\subset  [0,1]$ tel que
$\dim A> \frac 12$ et $B\colon A \to \mathbb{R}$ soit $\alpha$-H\"older continue. La preuve est une application du th\'eor\`eme de Kaufman sur le doublement de dimension. Comme corollaire du th\'eor\`eme ci-dessus, nous montrons que, presque s\^urement, il n'existe
pas d'ensemble $A \subset [0,1]$ tel que $\dim A> \frac{\beta}{2}$ et $B\colon A\to\mathbb{R}$ ait une $\beta$-variation finie. L'ensemble des z\'eros de $B$ et une construction d\'eterministe montrent que que les th\'eor\`emes ci-dessus donnent les dimensions optimales.
\end{abstract}

\maketitle

\section{Introduction}

We examine how  large a set can be, on
which linear Brownian motion is $\alpha$-H\"older continuous for some $\alpha>\frac12$ or
has finite $\beta$-variation for some $1\leq \beta\leq 2$.
The main goal of the paper is to prove the following two theorems.

\begin{theorem} \label{t:Holder}
Let $\{ B(t)\colon 0\leq t\leq 1\}$ be a linear Brownian motion and assume that $\alpha>\frac12$.
Then, almost surely, there exists no set~$A\subset[0,1]$ with $\dim A>\frac12$
such that $B\colon A\to\mathbb{R}$ is $\alpha$-H\"older continuous.
\end{theorem}

Recall that for $A\subset [0,1]$ the \emph{$\beta$-variation} of a function $f\colon A\to \mathbb{R}$ is defined as
$$\Var^{\beta} (f)=\sup\left\{\sum_{i=1}^{n} |f(x_{i})-f(x_{i-1})|^{\beta}: x_0<\dots <x_n,~x_i\in A,~n\in \mathbb{N}^+\right\}.$$

\begin{theorem} \label{t:BV} Let $\{ B(t)\colon 0\leq t\leq 1\}$ be a linear Brownian motion and assume that $1 \leq \beta \leq 2$.
Then, almost surely, there exists no set $A\subset[0,1]$ with $\dim A>\frac{\beta}{2}$
such that $B\colon A\to\mathbb{R}$ has finite $\beta$-variation. In particular,
$$\mathbb{P}(\exists A: \dim A> \textstyle \frac 12 \textrm{ and } B|_{A} \textrm{ is increasing})=0.$$
\end{theorem}

Clearly, the above theorems hold simultaneously for a countable dense set of parameters $\alpha,\beta$, thus
simultaneously for all $\alpha,\beta$. Let $\mathcal{Z}$ be the zero set of a linear Brownian motion $B$.
Then, almost surely, $\dim \mathcal{Z}=\frac 12$ and $B|_{\mathcal{Z}}$ is $\alpha$-H\"older continuous for all $\alpha>\frac 12$, so Theorem~\ref{t:Holder} gives the optimal dimension. We prove also that Theorem~\ref{t:BV} is best possible, see Theorem~\ref{t:opt}.

\subsection*{Motivation and related results}
Let $C[0,1]$ denote the set of continuous functions $f\colon [0,1]\to \mathbb{R}$ endowed with the maximum norm.
Elekes proved the following restriction theorem.

\begin{theorem}[Elekes \cite{E}] Let $0<\alpha<1$. For the generic continuous function $f\in C[0,1]$ (in the sense of Baire category)
\begin{enumerate}[(1)]
\item  for all $A\subset [0,1]$, if $f|_{A}$ is $\alpha$-H\"older continuous, then $\dim A\leq 1-\alpha$;
\item for  all $A\subset [0,1]$, if $f|_{A}$ is of bounded variation, then $\dim A\leq \frac 12$.
\end{enumerate}
\end{theorem}

The above theorem is sharp, the following result was proved by Kahane and Katznelson,
and M\'ath\'e independently, by different methods.

\begin{theorem}[Kahane and Katznelson \cite{KK}, M\'ath\'e \cite{Ma}] \label{t:KKM} Let $0<\alpha<1$. For any $f\in C[0,1]$ there are compact sets
$A,D\subset [0,1]$ such that
\begin{enumerate}[(1)]
\item $\dim A=1-\alpha$ and $f|_{A}$ is $\alpha$-H\"older continuous;
\item $\dim D=\frac 12$ and $f|_{D}$ is of bounded variation.
\end{enumerate}
\end{theorem}

Kahane and Katznelson also considered H\"older continuous functions.

\begin{definition} For $A\subset [0,1]$ let $C^{\alpha}(A)$ and $BV(A)$ denote the set of functions $f\colon A\to \mathbb{R}$ that are
$\alpha$-H\"older continuous and of bounded variation, respectively. For all $0<\alpha<\beta<1$ define
\begin{align*} H(\alpha,\beta)&=\sup\{\gamma: \forall \, f\in C^{\alpha}[0,1] \, \exists A\subset [0,1] \textrm{ s.t. }
\dim A=\gamma \textrm{ and } f|_{A}\in C^{\beta}(A) \}, \\
V(\alpha)&=\sup\{\gamma: \forall \, f\in C^{\alpha}[0,1] \, \exists A\subset [0,1] \textrm{ s.t. }
\dim A=\gamma \textrm{ and } f|_{A}\in BV(A)\}.
\end{align*}
\end{definition}

\begin{theorem}[Kahane and Katznelson \cite{KK}] For all $0<\alpha<\beta<1$ we have
$$H(\alpha,\beta)\leq \frac{1-\beta}{1-\alpha} \quad \textrm{and} \quad V(\alpha)\leq \frac{1}{2-\alpha}.$$
\end{theorem}

\begin{question}[Kahane and Katznelson \cite{KK}] \label{q:KK} Is the above result best possible?
\end{question}

As the linear Brownian motion $B$ is $\alpha$-H\"older continuous for all $\alpha< \frac 12$,
our results and Theorem~\ref{t:KKM} imply the following corollary.

\begin{corollary} For all $0<\alpha<\frac 12<\beta<1$ we have
$$H(\alpha,\beta)\leq \frac 12 \quad \textrm{and} \quad V(\alpha)=\frac 12.$$
\end{corollary}

Related results in the discrete setting can be found in \cite{ABP}.

\begin{definition}
Let $d\geq 2$ and $f\colon [0,1] \to \mathbb{R}^d$. We say that $f$ is \emph{increasing} on a set $A\subset [0,1]$
if all the coordinate functions of $f|_{A}$ are non-decreasing.
\end{definition}

\begin{question} Let $d\geq 2$ and let $\{ B(t)\colon 0\leq t\leq 1\}$ be a standard $d$-dimensional Brownian motion. What is the maximal
number $\gamma$ such that, almost surely, $B$ is increasing on some set of Hausdorff dimension $\gamma$?
\end{question}

\section{Preliminaries}

The diameter of a metric space $X$ is denoted by $\diam X$. For all $s \ge 0$ the \emph{$s$-dimensional Hausdorff measure} of $X$ is defined as

\begin{align*}
\mathcal{H}^{s}(X)&=\lim_{\delta\to 0+}\mathcal{H}^{s}_{\delta}(X)
\mbox{, where}\\
\mathcal{H}^{s}_{\delta}(X)&=\inf \left\{ \sum_{i=1}^\infty (\diam
X_{i})^{s}: X \subset \bigcup_{i=1}^{\infty} X_{i},~
\forall i \diam X_i \le \delta \right\}.
\end{align*}
The \emph{Hausdorff dimension} of $X$ is defined as
$$\dim X = \inf\{s \ge 0: \mathcal{H}^{s}(X) <\infty\}.$$
Let $A\subset \mathbb{R}$ and $\alpha>0$. A function $f\colon A\to \mathbb{R}$ is called
\emph{$\alpha$-H\"older continuous} if there exists a constant $c\in (0,\infty)$
such that $|f(x)-f(y)|\leq c|x-y|^{\alpha}$ for all $x,y\in A$.

\begin{fact} \label{f:H} If $f\colon A\to \mathbb{R}$ is $\alpha$-H\"older continuous, then $\dim f(A)\leq \frac{1}{\alpha} \dim A.$
\end{fact}

\section{H\"older restrictions}

The goal of this section is to prove Theorem~\ref{t:Holder}. First we need some preparation.

\begin{definition} A function $g\colon [0,1]\to \mathbb{R}^2$ is called \emph{dimension doubling} if
$$\dim g(A)=2\dim A \quad \textrm{for all } A\subset [0,1].$$
\end{definition}

\begin{theorem}[Kaufman, \cite{K1}, see also \cite{MP}] The two-dimensional Brownian motion is almost surely dimension doubling.
\end{theorem}

The following theorem follows from \cite[Lemma 2]{H} together with the fact that the closed range of the stable subordinator with parameter
$\frac 12$ coincides with the zero set of a linear Brownian motion. For a more direct reference see \cite{K2}.

\begin{theorem} \label{t:zero} Let $A\subset [0,1]$ be a compact set with $\dim A>\frac 12$ and let $\mathcal{Z}$ be the zero set
of a linear Brownian motion. Then $\dim(A\cap \mathcal{Z})>0$ with positive probability.
\end{theorem}

\begin{lemma}[Key Lemma] \label{l:key} Let $\{W(t)\colon 0\leq t\leq1\}$ be a linear Brownian motion. Assume that $\alpha>\frac 12$ and $f\colon [0,1]\to \mathbb{R}$ is a continuous function such that $(f,W)$ is almost surely dimension doubling. Then there is no set $A\subset[0,1]$ such that $\dim A>\frac12$
and $f$ is $\alpha$-H\"older continuous on $A$.
\end{lemma}

\begin{proof} Assume to the contrary that there is a set $A\subset [0,1]$ such that $\dim A>\frac12$
and $f$ is $\alpha$-H\"older continuous on $A$. As $f$ is still $\alpha$-H\"older
continuous on the closure of $A$, we may assume that $A$ itself is closed. Let $\mathcal{Z}$ be the zero set of $W$,
then Theorem~\ref{t:zero} implies that $\dim(A\cap \mathcal{Z})>0$ with
positive probability. Then the $\alpha$-H\"older continuity of $f|_{A}$ and Fact~\ref{f:H} imply that, with positive probability,
\begin{align*} \dim (f,W)(A\cap \mathcal{Z})&=\dim (f(A\cap \mathcal{Z})\times \{0\})=\dim f(A\cap \mathcal{Z})\\
&\leq \frac1{\alpha}\, \dim(A\cap \mathcal{Z}) < 2 \dim(A\cap \mathcal{Z}),
\end{align*}
which contradicts the fact that $(f,W)$ is almost surely dimension doubling.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{t:Holder}]
Let $\{W(t)\colon 0\leq t\leq 1\}$ be a linear Brownian motion which is independent of $B$. By Kaufman's dimension doubling theorem $(B,W)$ is
dimension doubling with probability one, thus applying Lemma~\ref{l:key} for an almost sure path of $B$ finishes the proof.  \end{proof}

\section{Restrictions of bounded variation}

We need the following lemma, which may be obtained by a slight modification of \cite[Lemma~4.1]{ABPR}.
For the reader's convenience we outline the proof.

\begin{lemma} \label{l:BV}
Let $\alpha, \beta >0$. Assume that $A\subset [0,1]$ and the function $f\colon A \to \mathbb{R}$ has finite $\beta$-variation. Then there are sets
$A_n\subset A$ such that for any $n\in \mathbb{N}^+$
$$f|_{A_n} \textrm{ is $\alpha$-H\"older continuous and } \dim \left(A\setminus \bigcup_{n=1}^{\infty} A_n\right)\leq \alpha \beta.$$
\end{lemma}

\begin{proof} For all $n\in \mathbb{N}^+$ let
$$A_n=\{x\in A: |f(x+t)-f(x)|\leq 2t^{\alpha} \textrm{ for all } t\in [0, 1/n]\cap (A-x)\}.$$
As $A$ is bounded, $f|_{A_n}$ is $\alpha$-H\"older continuous for all $n\in \mathbb{N}^+$. Let
$$D=\left\{x\in A: \limsup_{t\to 0+} |f(x+t)-f(x)|t^{-\alpha}>1\right\}.$$
Clearly $A\setminus \bigcup_{n=1}^{\infty} A_n\subset D$, so it is enough to prove that $\dim D\leq \alpha \beta$. Let us fix $\delta>0$ arbitrarily.
Then for all $x\in D$ there is a $0<t_x<\delta$ such that
\begin{equation} \label{eq:tx} |f(x+t_x)-f(x)|\geq t^{\alpha}_x.
\end{equation}
Define $I_x=[x-t_x,x+t_x]$ for all $x\in D$.
By Besicovitch's covering theorem (see \cite[Thm.~2.7]{M}) there is a number $p\in \mathbb{N}^+$ not depending on $\delta$ and countable sets
$S_i\subset D$ ($i\in \{1,\dots, p\}$) such that

\begin{equation} \label{eq:D} D\subset \bigcup_{i=1}^{p} \bigcup_{x\in S_i} I_x \textrm{ and } I_x\cap I_y=\emptyset \textrm{ for all } x,y\in S_i,~x\neq y.
\end{equation}
Applying \eqref{eq:tx} and \eqref{eq:D} implies that for all $i\in \{1,\dots,p\}$
\begin{equation} \label{eq:Var} \sum_{x\in S_i} |I_x|^{\alpha \beta} =2^{\alpha \beta} \sum_{x\in S_i}t_x^{\alpha \beta}\leq 2^{\alpha \beta} \sum_{x\in S_i} |f(x+t_x)-f(x)|^{\beta}  \leq 2^{\alpha \beta} \Var^{\beta} (f).
\end{equation}
Equations~\eqref{eq:D} and \eqref{eq:Var} imply that
$$\mathcal{H}_{\delta}^{\alpha \beta}(D)\leq \sum_{i=1}^{p} \sum_{x\in S_i} |I_x|^{\alpha \beta}\leq p2^{\alpha \beta}\Var^{\beta} (f).$$
As $\Var^{\beta} (f)<\infty$ and $\delta>0$ was arbitrary, we obtain that $\mathcal{H}^{\alpha \beta}(D)<\infty$.
Hence $\dim D\leq \alpha \beta$, and the proof is complete.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{t:BV}]
Assume to the contrary that for some $\varepsilon>0$ there is a random set $A\subset [0,1]$ such that, with positive probability,
$\dim A\geq \beta/2+2\varepsilon$ and $B|_{A}$ has finite $\beta$-variation. Let $\alpha=1/2 +\varepsilon/\beta>1/2$.
Applying Lemma~\ref{l:BV} we obtain that there are sets $A_n\subset A$ such that $B|_{A_n}$ is $\alpha$-H\"older continuous for every $n\in \mathbb{N}^+$ and
\begin{equation} \label{eq:alpha}  \dim \left(A\setminus \bigcup_{n=1}^{\infty} A_n\right)\leq \alpha \beta =\frac{\beta}{2}+\varepsilon.
\end{equation}
As $\alpha>1/2$ and $B|_{A_n}$ are $\alpha$-H\"older continuous,
Theorem~\ref{t:Holder} implies that almost surely $\dim A_n\leq 1/2$ for all $n\in \mathbb{N}^+$,
therefore \eqref{eq:alpha} and the countable stability of the Hausdorff dimension yield that
$\dim A\leq \beta/2+\varepsilon$ almost surely. This is a contradiction, and the proof is complete.
\end{proof}

Theorems~\ref{t:L} and \ref{t:opt} (with $\alpha=\frac 12$) imply that Theorem~\ref{t:BV} is sharp for all $\beta$.

\begin{theorem}[L\'evy's modulus of continuity, \cite{L}, see also \cite{MP}] \label{t:L} For the linear Brownian motion $\{ B(t) \colon 0\leq t\leq 1\}$, almost surely,
$$\limsup_{h\to 0+} \sup_{0\leq t\leq 1-h} \frac{|B(t+h)-B(t)|}{\sqrt{2h \log(1/h)}}=1.$$
\end{theorem}

\begin{theorem}\label{t:opt} Let $0<\alpha\leq 1$ and $0<\beta \leq \frac {1}{\alpha}$ be fixed. Then there is a compact set $A\subset [0,1]$ such that $\dim A=\alpha \beta$ and if $f\colon [0,1]\to \mathbb{R}$ is a function and $c\in (0,\infty)$ such that for all $x,y\in [0,1]$
\begin{equation} \label{eq:mod} |f(x)-f(y)|\leq c|x-y|^{\alpha}\log \frac{1}{|x-y|}, \end{equation}
then $f|_{A}$ has finite $\beta$-variation.
\end{theorem}

\begin{proof} First we construct $A$. For all $n\in \mathbb{N}$ let
$$\gamma_n=2^{-n/(\alpha \beta)}(n+1)^{-(\beta+2)/\beta}.$$

We define intervals $I_{i_1\dots i_n}\subset [0,1]$ for all $n\in \mathbb{N}$ and $\{i_1,\dots, i_n\}\in \{0,1\}^{n}$  by induction.
We use the convention $\{0,1\}^{0}=\{\emptyset\}$. Let $I_{\emptyset}=[0,1]$, and if the interval
$I_{i_1\dots i_n}=[u,v]$ is already defined then let
$$I_{i_1\dots i_n 0}=[u,u+\gamma_{n+1}] \textrm{ and } I_{i_1\dots i_n 1}=[v-\gamma_{n+1},v].$$

Let

$$A=\bigcap_{n=0}^{\infty} \bigcup_{(i_1,\dots,i_n) \in \{0,1\}^n} I_{i_1\dots i_n}.$$

Assume that $f\colon [0,1]\to \mathbb{R}$ is a function satisfying \eqref{eq:mod}. Now we prove that $\Var^{\beta} (f|_{A}) <\infty$. As $\diam I_{i_1\dots i_n}=\gamma_n$,
the definition of $\gamma_n$ and \eqref{eq:mod} imply that for all $n\in \mathbb{N}$ and $(i_1,\dots, i_n)\in \{0,1\}^n$ we have
\begin{equation} \label{eq:beta}
(\diam f(I_{i_1\dots i_n}))^\beta \leq (c \gamma_n^{\alpha} \log \gamma_n^{-1})^{\beta}\leq  c_{\alpha,\beta}2^{-n}(n+1)^{-2},
\end{equation}
where $c_{\alpha,\beta}\in (0,\infty)$ is a constant depending on $\alpha,\beta$ and $c$ only. For all
$x,y\in A$ let $n(x,y)$ be the maximal number $n$ such that $x,y\in I_{i_1\dots i_n}$ for some $(i_1,\dots,i_n)\in \{0,1\}^n$. If $\{x_i\}_{i=0}^{k}$ is a monotone sequence in $A$ and $n\in \mathbb{N}$
then the number of $i\in \{1,\dots,k\}$ such that $n(x_{i-1},x_{i})=n$ is at most $2^n$. Therefore \eqref{eq:beta} implies that
$$\Var^{\beta} (f|_{A}) \leq \sum_{n=0}^{\infty} 2^{n} \left(c_{\alpha,\beta} 2^{-n}(n+1)^{-2}\right)=\sum_{n=1}^{\infty} c_{\alpha,\beta} n^{-2}<\infty.$$
Finally, we prove that $\dim A=\alpha \beta$. The upper bound $\dim A\leq \alpha \beta$ is obvious, thus we show only the lower bound. In the construction of $A$ each $(n-1)$st level interval $I_{i_1\dots i_{n-1}}$ contains $m_n=2$ $n$th level intervals $I_{i_1\dots i_{n-1}i}$, which are separated by gaps of $\varepsilon_n=\gamma_{n-1}-2\gamma_n$. The definition of $\gamma_n$ yields that $0<\varepsilon_{n+1}<\varepsilon_n$ for all $n\in \mathbb{N}^+$
and $\varepsilon_n=2^{-n/(\alpha \beta)+o(n)}$. Applying \cite[Example~4.6]{F} we obtain that
$$\dim A\geq \liminf_{n\to \infty} \frac{\log(m_1\cdots m_{n-1})}{-\log(m_n \varepsilon_n)}=\alpha \beta,$$

and the proof is complete.
\end{proof}

\section*{Acknowledgment} The first author was supported by the
Hungarian Scientific Research Fund grant no.~104178. We thank Russell Lyons and Nicolas Curien for help with the abstract.


TITLE: Find the limit of given function as x approaches infinity
QUESTION [0 upvotes]: $\ lim_{x \to \infty} x^{4}{e^{-x^{2}}} $. Any tip how to start on this problem? I have no idea how to start on this type of problem.

REPLY [1 votes]: Simplify with $$x^4e^{-x^2}=4\left(\frac{x^2}2e^{-x^2/2}\right)^2=4\left(te^{-t}\right)^2$$ where $t\ge0$. Then you can solve just for $te^{-t}$.
L'Hospital will work. You can also use $e^t\ge1+t+\dfrac{t^2}2$ from Taylor.


TITLE: Does quantum mechanics prohibit extraterrestrial life?
QUESTION [1 upvotes]: There is a known thought experiment, connected to quantum immortality: a duel between physicist and a philosopher.
Each turn physicist and philosopher fire at each other with a pistol. The quantum immortality predicts that each of the participants will find themselves alive and the opponent dead after a number of shots.
We can modify the experiment in the following ways:

They do not fire at each other, but it is lightning that shots them. The outcome should not change.
There are not two but more participants.
They are located at separate islands in the ocean.

It seems that even if there are hundreds of participants, each of them will eventually find all others killed by lightning. If he could not observe other isles directly, after he discovers and explores other isles, he will find them uninhabitable.
Now pretend that the participants actually live on separate planets, and in each million years there happens disaster that kills all inhabitants on 1% of all planets. It seems that after years the physicist that lives on one of the planets should discover that all other planets are uninhabitable. Even more: there is even no chance that organic matter on each other planet could actually evolve into anything resembling actual life.
That said the physicist will find out that there is no other inhabitable planet in the Uinverse. On the other hand, this does not mean that extraterrestrial life does not exist. It actually cannot not to exist. But it exists in parallel universes (in terms of MWI) and thus unobservable. Both physicist on planet A and philosopher on planet B exist, but will never meet in the same universe.
Thus, QI it seems predicts one concrete observable consequence that extraterrestrial life can be never detected.
What is your opinion?

REPLY [2 votes]: Dear Anixx, we know very well from the observations - and theory - here on Earth that repeated lightnings are nowhere close to be able to exterminate the life on the planet. Because it's true here and because the laws of physics - including the emergent ones - are at least approximately translationally invariant, it's almost certainly true on similar other planets in the Universe: lightnings are not enough to exterminate life. Your "conclusion" - actually an "assumption" - that the life on other planets has to go extinct because of lightnings is therefore invalid. It is invalid in the whole Universe and this paragraph is a proof that can't be "unproved" by any silly logical game.
It is very obvious that none of those thought experiments can actually determine the real odds - or our rational expectations about them - of having some extraterrestrial life. It's because the emergence of life (whatever its definition is) and its extinction on every celestial body is controlled by the objective laws of physics rather than subjective feelings of an observer who is likely to die soon. So all calculations of an individual that simply "erase" the possibility that he will die from the calculation of odds are subjective and can't be used by other individuals as an objective calculation. So they cannot be used to count the extraterrestrial civilizations.
For this reason, the "quantum immortality" itself is a logical fallacy. From an objective viewpoint, whether an observer dies during a period of time or not is just a well-defined question that can have both answers and eliminating possibilities where he dies is objectively unjustifiable. By the way, the philosophies and religions that believe in "life after death" obtain much more valid figures for the probabilities than Max Tegmark's philosophy that simply denies the possibility that observers die.
No "interpretation" of quantum mechanics or physics, as long as it is consistent with the standard physical predictions, can change anything about the paragraphs above.
By the way, if you find my comment that the fate of life is given by the laws of physics and not games in philosophy controversial, let me mention that this battle between physics and philosophy has been settled since 1687. A general in this physics-philosophy war, philosopher Isaac Newton, published his aptly named "Mathematical Principles of Natural Philosophy" and declared a surrender. Since that time, it was clear that all natural phenomena have to be studied by physics (that he helped to establish) and not by meaningless and logically flawed philosophical games you have presented.
Also, I would respectfully disagree that the answer above is "my opinion". It is the objective answer to your question. Physics is not about personal opinions; it is the scientific method to search (and often find) the objective truth. Also, this server is meant to offer the right physics answers to questions that can be answered as of 2011, rather than an assorted flow of chaotic personal opinions, and yours was surely one of the questions that can be answered today.
I don't claim that the extraterrestrial civilizations have to exist or have to be absent - but I surely do claim that there exists no rational argument based on "quantum immortality" that could influence the odds.


TITLE: Taylor expansion about candidate point $x^*$: $f(x^∗ + h) = f(x^∗) + hf'(x^∗) + O(h^2)$?
QUESTION [1 upvotes]: My textbook, Algorithms for Optimization, by Kochenderfer and Wheeler, says the following:

A point can also be at a local minimum if it has a zero derivative and the second derivative is merely nonnegative:

$f'(x^∗) = 0$, the first-order necessary condition (FONC)
$f''(x^∗) \ge 0$, the second-order necessary condition (SONC)

These conditions are referred to as necessary because all local minima obey these two rules. Unfortunately, not all points with a zero derivative and a zero second derivative are local minima, as demonstrated in figure 1.7.
The first necessary condition can be derived using the Taylor expansion about our candidate point $x^*$:
$$f(x^∗ + h) = f(x^∗) + hf'(x^∗) + O(h^2)$$
$$f(x^∗ − h) = f(x^∗) − hf'(x^∗) + O(h^2)$$
$$f(x^∗ + h) \ge f(x^∗) \Rightarrow hf'(x^∗) \ge 0$$
$$f(x^∗ − h) \ge f(x^∗) \Rightarrow hf'(x^∗) \le 0$$
$$\Rightarrow f'(x^∗)=0$$

Appendix C states the Taylor expansion about $a$ as

$$f(x) \approx f(a) + f'(a)(x - a) + \dfrac{1}{2} f''(a)(x - a)^2$$

So if we want the Taylor expansion about our candidate point $x^*$, as the textbook states, then we have
$$f(x) \approx f(x^*) + f'(x^*)(x - x^*) + \dfrac{1}{2} f''(x^*)(x - x^*)^2,$$
which is not $f(x^∗ + h) = f(x^∗) + hf'(x^∗) + O(h^2)$.
Or if we set $x = x^* + h$, we get
$$f(x^* + h) \approx f(a) + f'(a)(x^* + h - a) + \dfrac{1}{2} f''(a)(x^* + h - a)^2,$$
which is not $f(x^∗ + h) = f(x^∗) + hf'(x^∗) + O(h^2)$.
Or if we set $x = x^* + h$ and take the Taylor expansion about $h$ (rather than $x^*$ as was stated), we get
$$f(x^* + h) \approx f(h) + f'(h)(x^*) + \dfrac{1}{2} f''(h)(x^*)^2,$$
which is not $f(x^∗ + h) = f(x^∗) + hf'(x^∗) + O(h^2)$.
So I'm confused as to how the authors' result makes sense? I would greatly appreciate it if someone would please take the time to clarify this.

REPLY [1 votes]: Have you tried
$$x=x^*+h, a=x^*$$?


TITLE: A matrix's element proof
QUESTION [0 upvotes]: Thanks again for copper.hat and Robert Israel's quick immediate reply. While I am modifying the questions, they've already given the answer. Now in this thread, I've changed it back to the original version, and I put the new version which is more challenging in the following thread:  A hard proof of two matrix's elements. Hopefully, some brilliant experts could give me suggestions.

Given an constant $\alpha \in (0,1)$, and  an $n \times n$ matrix $X$ whose all entries are between 0 and 1, and ${\|X\|}_{\infty} \le 1$. Suppose
$$A=\sum_{i=1}^{\infty} {\alpha}^i X^i ,$$
$$B=\sum_{i=1}^{\infty} \frac {{\alpha}^i}{i!} X^i ,$$
I've done some experiments and found that :

For each entry $(a,b)$, $[A]_{a,b} \ge [B]_{a,b} .$

(Note that I use $[A]_{i,j}$ to denote the $(i,j)$-entry of the matrix $A$)
How can I prove this result mathmetrically? Any suggestions are warmly welcome.

REPLY [4 votes]: Note: This was an answer to the original question:
For each $i$, you have $[\frac {{\alpha}^i}{i!} X^i]_{j,k} \leq [{\alpha}^i X^i]_{j,k}$, since it is divided by $i!$.
Hence you have $[B]_{j,k} = [\sum \frac {{\alpha}^i}{i!} X^i]_{j,k} = \sum [\frac {{\alpha}^i}{i!} X^i]_{j,k} \leq \sum [{\alpha}^i X^i]_{j,k} = [\sum {\alpha}^i X^i]_{j,k} = [A]_{j,k}$.

REPLY [2 votes]: If $\alpha$ and all entries of $X$ are nonnegative, the same goes for all entries of $\alpha^i X^i$ for any nonnegative integer $i$. If $t \ge 0$, $t/i! \le t$.  So each entry of each term of the $B$ series $\le$ the corresponding entry of the corresponding term of the $A$ series.  And since the series converge, we get $B_{i,j} \le A_{i,j}$.


TITLE: Is the charge present only on the outer surface of a spherical conducting sphere or on both inner and outer surfaces?
QUESTION [0 upvotes]: Recently I was taught that in a conductor charge resides only on the surface of the conductor and the net charge inside a conductor is zero and so is the net electric field.
But what if the conductor had two surfaces like in a spherical conducting shell?
Suppose we provide a charge 'Q' to a spherical conducting shell. Is the charge on the inner surface of the shell equal to zero or is the charge divided equally among the two surfaces(Q/2 on the outer surface and Q/2 on the inner surface)? I'm in a dilemma.
NOTE: Initially There is no charge inside the cavity of the shell.

REPLY [1 votes]: Charges repel one another and will get as far apart as they can.  Since the shell is a conductor, nothing is stopping them from moving to the outer surface which is as far apart as they can get from one another.

REPLY [0 votes]: Unless there are charges in the interior of the conducting shell, since the electric field in a conductor must be zero at steady state, Gauss' law requires that there be no charge on the inner surface of the conductor. All of the charge will reside on the outer surface.


TITLE: Does Lagrange interpolation yield a unique polynomial over finite fields?
QUESTION [1 upvotes]: I understand that part of this question has been addressed before (here), but I am confused about the uniqueness of a Lagrange interpolant.
Given any field $F$, I am trying to prove the existence and uniqueness of a Lagrange interpolant in $F[x]$ for any function $f$ from $F$ to itself over a set of distinct $n$ points :$(x_1,f(x_1)) \dots (x_n,f(x_n))$, where each $x_1 \dots x_n$ is unique. Following the proof outlined here, I see that it says the proof for both the existence and uniqueness of a Lagrange interpolant is satisfied for any given field, which implies that it also satisfied for finite fields. However, there are finitely many functions from $F$ to itself and there are infinitely many polynomials in $F[x]$. I also see that from this post, a polynomial function in a finite field can be given by multiple polynomials. Would this not imply that the uniqueness of a Lagrange interpolant need not hold over a finite field?
Any clarification about how the proof of uniqueness for a Lagrange interpolant over a finite field would be much appreciated!

REPLY [4 votes]: You are missing the issue that the interpolation polynomial for $n$ points has degree less than $n$ (or is the zero polynomial, but I won't keep repeating this). That makes the polynomial unique even if the field $F$ is finite.  What keeps things unique given the restriction on the degree being less than $n$ is that polynomials of the form $c_0 + c_1x + \cdots + c_{n-1}x^{n-1}$  and $c_0' + c_1'x + \cdots + c_{n-1}'x^{n-1}$  in $F[x]$ that are equal at $n$ different numbers in $F$ must have $c_i = c_i'$ for all $i$.  This is true for all fields, and notice that when $F$ is finite such a result only makes sense when $n \leq |F|$ since $F$ has at most $|F|$ distinct elements.  For instance, you can't find a polynomial in $\mathbf F_3[x]$ taking specified values at $5$ different elements of  $\mathbf F_3$ since there aren't $5$ different elements of $\mathbf F_3$. (You could look for a polynomial in $\mathbf F_9[x]$ taking specified values at 5 different elements of $\mathbf F_9$, but not at 14 different elements of $\mathbf F_9$, and so on.)
You have concern about losing uniqueness over a finite field, but
even over an infinite field you would lose uniqueness without restricting the degree of the interpolation polynomial to have degree less than  $n$: if the distinct points in $F$ are $a_1, \ldots, a_n$ then you can add to an interpolating polynomial an arbitrary polynomial multiple of $(x-a_1)\cdots(x-a_n)$ without changing the values of the polynomial at $a_1,\ldots,a_n$.  You don't lose uniqueness as long as you require the interpolation polynomial at $n$ different numbers in $F$ to have degree less than $n$.
Here is a correct theorem: for a field $F$, distinct $a_1, \ldots, a_n$ in $F$, and arbitrary $b_1, \ldots, b_n$ in $F$, there is a unique polynomial $f(x) \in F[x]$ of degree less than $n$ such that $f(a_i) = b_i$ for $i = 1, \ldots, n$.


text:
\begin{document}

\begin{flushleft}
{\bf Generalized Shannon inequalities based on Tsallis relative operator entropy}
\end{flushleft}
\vspace{0.2cm}
\begin{flushleft}
Kenjiro Yanagi\footnote{E-mail:yanagi@yamaguchi-u.ac.jp} \\
Department of Applied Science \\
Faculty of Engineering \\
Yamaguchi University \\
Tokiwadai 2-16-1 \\
Ube 755-0811, Japan,
\end{flushleft}
\begin{flushleft}
Ken Kuriyama \footnote{E-mail:kuriyama@yamaguchi-u.ac.jp} \\
Department of Applied Science \\
Faculty of Engineering \\
Yamaguchi University \\
Tokiwadai 2-16-1 \\
Ube 755-0811, Japan
\end{flushleft}
\begin{flushleft}
and
\end{flushleft}
\begin{flushleft}
Shigeru Furuichi \footnote{E-mail:furuichi@ed.yama.tus.ac.jp} \\
Department of Electronics and Computer Science \\
Faculty of Science and Engineering \\
Tokyo University of Science, Yamaguchi \\
Daigaku-Dori 1-1-1 \\
Onoda 756-0884, Japan
\end{flushleft}
\vspace{0.5cm}
\begin{flushleft}
{\sc Abstract}
\end{flushleft}

Tsallis relative operator entropy is defined and then its properties are
given.  Shannon inequality and its reverse one in Hilbert space operators derived by T.Furuta \cite{Fu:par}
 are extended in terms of the parameter of the Tsallis relative operator entropy. Moreover the generalized Tsallis relative operator entropy is introduced and then
several operator inequalities are derived.

\vspace{3mm}

{\bf Keywords : }Operator inequality, Tsallis relative operator entropy, Shannon inequality
\vspace{3mm}

{\bf 2000 Mathematics Subject Classification : } 47A63, 60E15, 26D15

\vspace{0.5cm}
\begin{flushleft}
{\sc Introduction}
\end{flushleft}

Tsallis entropy
$$
S_q(X) = -\sum_{x} p(x)^q \ln_q p(x)
$$
was defined in \cite{Ts:rel} for the probability distribution $p(x)$,
where $q$-logarithm function is defined by
$\ln_q(x)\equiv \frac{x^{1-q}-1}{1-q}$
for any nonnegative real numbers $x$ and $q \neq 1$.
It is easily seen that Tsallis entropy is one parameter extension of
Shannon entropy $S_1(X) \equiv -\sum_x p(x) \log p(x)$ and converges to it as
$q \to 1$.
The study based on Tsallis type entropies has been developed in mainly
statistical physics \cite{AO:re1}.
In the recent work \cite{Ab:re1}, Tsallis type relative entropy in quantum
system,  defined by
\begin{equation}\label{dq}
D_q(\rho\vert \sigma) \equiv \frac{1}{1-q} \left[1- Tr(\rho^q\sigma^{1-q})\right]
\end{equation}
for two density operators $\rho$ and $\sigma$ (i.e., positive operators with unit trace)
and $0\leq q<1$,  was investigated.

  On the other hand, the relative operator entropy was defined by
  J.I.Fujii and E.Kamei in \cite{FuKa:rel}.
Many important results in operator theory and information theory have been
published in the relation to Golden-Thonmpson inequality \cite{HP,BPL}.
We are interested in not only the properties of the Tsallis type relative
entropy  but also the properties before taking a trace, namely,
Tsallis type relative operator entropy which is a parametric extension of
the relative operator entropy.
In this paper, we define the Tsallis relative operator entropy and then show
some properties of Tsallis relative operator entropy. To this end, we slightly change the
parameter $q$ in Eq.(\ref{dq}) to $\lambda$ in our definition which will be
appeared in the following section. Moreover, in order to make our definition
correspond to the definition of the relative operator entropy defined in
\cite{FuKa:rel}, we change the sign of the original Tsallis relative entropy.

\section{Tsallis relative entropy}

As mentioned above, we adopt the slightly modified definition of the Tsallis relative entropy in the following.

\begin{definition}
Let $a = \{a_1,a_2,\ldots,a_n \}$ and $b = \{b_1,b_2,\ldots,b_n \}$
be two probability vectors satisfying $a_j, b_j > 0$. Then for
$0 < \lambda \leq 1$
\begin{equation}\label{our}
S_{\lambda}(a|b) = \frac{\sum_{j=1}^n a_j^{1-\lambda}b_j^{\lambda}-1}{\lambda}
\end{equation}
is called Tsallis relative entropy between $a$ and $b$.
\label{def:definition1}
\end{definition}

We should note that the Tsallis relative entropy is usually defined by
\begin{equation} \label{usually}
 D_q(a\vert b) = \frac{1-\sum_{j=1}^n a_j^q b_j^{1-q}}{1-q},
\end{equation}
with a parameter $q \geq 0$ in the field of statisitical physics \cite{AO:re1}. There is the relation between them
such that $S_{\lambda}(a \vert b)=-D_{1-q}(a \vert b)$.
However, in this paper, we adopt the definition of Eq.(\ref{our}) in stead of Eq.(\ref{usually}),
 to study of the properties of the parametrically extended relative operator entropy as a series of the study of
the relative operator entropy from the operator theoretical point of view.
The opposite sign between the relative entropy defined by Umegaki \cite{Um} and the relative operator entropy led
 us to define the Tsallis relative operator entropy in the above.

Tsallis relative entropy defined in Eq.(\ref{our}) has the following
properties.

\begin{proposition}
We have the following {\rm (1)} and {\rm (2)}.
\begin{description}
\item[(1)] $\displaystyle{S_{\lambda}(a|b) \geq \sum_{j=1}^n a_j \log \frac{b_j}{a_j}}$ for $0 < \lambda \leq 1$.
\item[(2)] $\displaystyle{\lim_{\lambda \to 0} S_{\lambda}(a|b) = \sum_{j=1}^n a_j \log \frac{b_j}{a_j}}$.
\end{description}
\label{prop:proposition1}
\end{proposition}

\begin{flushleft}
{\bf Proof.}  (1)  Since $t^{\lambda}-1 \geq \log t^{\lambda}$, we have
\end{flushleft}
$$
\frac{\sum_{j=1}^n a_j^{1-\lambda}b_j^{\lambda}-1}{\lambda} = \sum_{j=1}^n a_j\frac{(\frac{b_j}{a_j})^{\lambda}-1}{\lambda} \geq \sum_{j=1}^n a_j \log \frac{b_j}{a_j}.
$$

\noindent
(2)
\begin{eqnarray*}
\lim_{\lambda \to 0} \frac{\sum_{j=1}^n a_j^{1-\lambda}b_j^{\lambda}-1}{\lambda} & = & \lim_{\lambda \to 0} \frac{\sum_{j=1}^n a_j(\frac{b_j}{a_j})^{\lambda}-1}{\lambda} \\
& = & \sum_{j=1}^n a_j(\frac{b_j}{a_j})^{\lambda}\log \frac{b_j}{a_j} |_{\lambda = 0} \\
& = & \sum_{j=1}^n a_j \log \frac{b_j}{a_j}.
\end{eqnarray*}
\ \hfill q.e.d.

\begin{proposition}
$$
0 \geq S_{\lambda}(a|b) \geq \frac{(\sum_{j=1}^n \frac{a_j^2}{b_j})^{-\lambda}-1}{\lambda}.
$$
\label{prop:proposition2}
\end{proposition}

\begin{flushleft}
{\bf Proof.} Since
\end{flushleft}
$$
\sum_{j=1}^n a_j^{1-\lambda}b_j^{\lambda} \leq \sum_{j=1}^n \{(1-\lambda)a_j+\lambda b_j \} = (1-\lambda)\sum_{j=1}^n a_j + \lambda \sum_{j=1}^n b_j = 1,
$$
we have
$$
S_{\lambda}(a|b) \leq 0.
$$
We also give another inequality. Since
$$
\sum_{j=1}^n a_j^{1-\lambda}b_j^{\lambda} = \sum_{j=1}^n (\frac{a_j}{b_j})^{-\lambda}a_j \geq \prod_{j=1}^n (\frac{a_j}{b_j})^{-\lambda a_j} = (\prod_{j=1}^n (\frac{a_j}{b_j})^{a_j})^{-\lambda} \geq (\sum_{j=1}^n \frac{a_j^2}{b_j})^{-\lambda},
$$
we have
$$
S_{\lambda}(a|b) \geq \frac{(\sum_{j=1}^n \frac{a_j^2}{b_j})^{-\lambda}-1}{\lambda}.
$$
\ \hfill q.e.d.

\section{Tsallis relative operator entropy}

A bounded linear operator $T$ on a Hilbert space $H$ is said to be positive
(denoted by $T \geq 0$) if $(Tx,x) \geq 0$ for all $x \in H$ and also an
operator $T$ is said to be strictly positive (denoted by $T > 0$) if $T$ is
invertible and positive.  We define Tsallis relative operator entropy
in the following.

\begin{definition}
For $A > 0, B > 0$ and $0 < \lambda \leq 1$,
$$
T_{\lambda}(A|B) = \frac{A^{1/2}(A^{-1/2}BA^{-1/2})^{\lambda}A^{1/2}-A}{\lambda}$$
is called Tsallis relative operator entropy between $A$ and $B$.
\label{def:definition2}
\end{definition}

In this section we give the Shannon type operator inequality and its reverse one satisfied
by Tsallis relative operator entropy.

\begin{theorem}
Let $\{ A_1,A_2,\ldots,A_n \}$ and $\{B_1,B_2,\ldots,B_n \}$ be two sequences
of strictly positive operators on a Hilbert space $H$. If
$\displaystyle{\sum_{j=1}^n A_j = \sum_{j=1}^n B_j = I}$, then
$$
0 \geq \sum_{j=1}^n T_{\lambda}(A_j|B_j) \geq \frac{(\sum_{j=1}^n A_jB_j^{-1}A_j)^{-\lambda}-I}{\lambda}.
$$
\label{th:theorem1}
\end{theorem}

We need a lemma before we prove the main theorem.

\begin{lemma}
For fixed $t > 0$, an inequality of
$\lambda \; (0 < \lambda \leq 1)$ holds.
$$
\frac{t^{\lambda}-1}{\lambda} \leq t-1.
$$
\label{lem:lemma1}
\end{lemma}

\begin{flushleft}
{\bf Proof.}  If $t = 1$, then it is clear. If $t \neq 1$, then
we put $F(\lambda) = \lambda(t-1)-t^{\lambda}+1$. Then we have
$F^{'}(\lambda) = t-1-t^{\lambda}\log t$ and
$F^{''}(\lambda) = -t^{\lambda}(\log t)^2 < 0$. Hence $F(\lambda)$ is concave.
Since $F(0) = F(1) = 0$, we have the result.
\ \hfill q.e.d.
\end{flushleft}

\begin{flushleft}
{\bf Proof of Theorem \ref{th:theorem1}.} It follows from Lemma \ref{lem:lemma1} that
\end{flushleft}
\begin{eqnarray*}
\frac{A^{1/2}(A^{-1/2}BA^{-1/2})^{\lambda}A^{1/2}-A}{\lambda} & = &
A^{1/2} \frac{(A^{-1/2}BA^{-1/2})^{\lambda}-I}{\lambda} A^{1/2} \\
& \leq & A^{1/2}(A^{-1/2}BA^{-1/2}-I)A^{1/2} \\
& = & B-A,
\end{eqnarray*}
where $A > 0, B > 0$ and $0 < \lambda \leq 1$.
Then we have
\begin{eqnarray*}
\sum_{j=1}^n T_{\lambda}(A_j|B_j) & = & \sum_{j=1}^n \frac{A_j^{1/2}(A_j^{-1/2}B_jA_j^{-1/2})^{\lambda}A_j^{1/2}-A_j}{\lambda} \\
& \leq & \sum_{j=1}^n (B_j - A_j) = 0.
\end{eqnarray*}
We also prove another inequality. We apply Proposition 3.1 of
Furuta \cite{Fu:par} by putting $f(x) = -x^{-\lambda}$, $C_j = A_j^{1/2}$ and
$X_j = A_j^{1/2}B_j^{-1}A_j^{1/2}$. Then
$$
-(\sum_{j=1}^n A_j^{1/2}(A^{1/2}B_j^{-1}A_j^{1/2})A_j^{1/2})^{-\lambda} \geq -\sum_{j=1}^n A_j^{1/2}(A_j^{1/2}B_j^{-1}A_j^{1/2})^{-\lambda}A_j^{1/2}.
$$
Hence
$$
(\sum_{j=1}^n A_jB_j^{-1}A_j)^{-\lambda} \leq \sum_{j=1}^n A_j^{1/2}(A_j^{-1/2}B_jA_j^{-1/2})^{\lambda}A_j^{1/2}.
$$
Then we complete the proof. \ \hfill q.e.d. \\

We also obtain the operator version of the Shannon inequality and reverse one given by Furuta \cite{Fu:par}
as a corollary of Theorem \ref{th:theorem1} in the following.

\begin{corollary}[Furuta \cite{Fu:par}]
Let $\{ A_1,A_2,\ldots,A_n \}$ and $\{B_1,B_2,\ldots,B_n \}$ be two sequences
of strictly positive operators on a Hilbert space $H$. If
$\displaystyle{\sum_{j=1}^n A_j = \sum_{j=1}^n B_j = I}$, then
$$
0 \geq \sum_{j=1}^n A_j^{1/2}(\log A_j^{-1/2}B_jA_j^{-1/2})A_j^{1/2} \geq -\log [\sum_{j=1}^n A_jB_j^{-1}A_j].
$$
\label{cor:corollary1}
\end{corollary}

We need the following lemma to prove it.

\begin{lemma}
For $0 < \lambda < 1,  0 < \alpha < \beta$, we have the following {\rm (1)}
and {\rm (2)}.
\begin{description}
\item[(1)]  $\displaystyle{\lim_{\lambda \to +0}\frac{t^{\lambda}-1}{\lambda} = \log t}$  uniformly on $[\alpha,\beta]$.
\item[(2)]  $\displaystyle{\lim_{\lambda \to +0}\frac{t^{-\lambda}-1}{\lambda} = -\log t}$ uniformly on $[\alpha,\beta]$.
\end{description}
\label{lem:lemma2}
\end{lemma}

\begin{flushleft}
{\bf Proof.} We prove it by using Dini's theorem. \ \hfill q.e.d.
\end{flushleft}

\begin{flushleft}
{\bf Proof of Corollary \ref{cor:corollary1}.}  By (1) of Lemma \ref{lem:lemma2},
\end{flushleft}
$$
\lim_{\lambda \to +0} \frac{(A^{-1/2}BA^{-1/2})^{\lambda}-I}{\lambda} = \log A^{-1/2}BA^{-1/2},
$$
where the limit is taken in operator norm. Then
\begin{eqnarray*}
\lim_{\lambda \to +0} \sum_{j=1}^n T_{\lambda}(A_j|B_j) & = & \lim_{\lambda \to +0} \sum_{j=1}^n \frac{A_j^{1/2}(A_j^{-1/2}B_jA_j^{-1/2})^{\lambda}A_j^{1/2}-A_j}{\lambda} \\
& = & \sum_{j=1}^n A_j^{1/2} (\log A_j^{-1/2}B_jA_j^{-1/2})A_j^{1/2}.
\end{eqnarray*}
On the other hand, by (2) of Lemma \ref{lem:lemma2},  we have
$$
\lim_{\lambda \to +0}\frac{(\sum_{j=1}^nA_jB_j^{-1}A_j)^{-\lambda}-I}{\lambda}=-\log[\sum_{j=1}^nA_jB_j^{-1}A_j]$$
Therefore Theorem \ref{th:theorem1} ensures
$$
0 \geq \sum_{j=1}^nA_j^{1/2}(\log A_j^{-1/2}B_jA_j^{-1/2})A_j^{1/2}\geq -\log[\sum_{j=1}^nA_jB_j^{-1}A_j].$$

\ \hfill q.e.d.

Actually the above Corollary \ref{cor:corollary1} is a part of the Corollary 2.4 in \cite{Fu:par}.
We will generalize our Tsallis relative operator entropy and derive some generalized operator inequalities
by the different way from \cite{Fu:par} in the following section.

\section{Generalized Tsallis relative operator entropy}

We remind of the relative operator entropy and its related operator entropy.

\begin{definition}
For $A > 0, B > 0$
$$
S(A|B) = A^{1/2}(\log A^{-1/2}BA^{-1/2})A^{1/2}
$$
is called relative operator entropy between $A$ and $B$. It was defined by
Fujii and Kamei {\rm \cite{FuKa:rel}} originally. For $A > 0, B > 0$ and
$\lambda \in \mathbb{R}$, the generalized relative operator entropy was defined by Furuta in \cite{Fu:par}
$$
S_{\lambda}(A|B) = A^{1/2}(A^{-1/2}BA^{-1/2})^{\lambda}(\log A^{-1/2}BA^{-1/2})A^{1/2}
$$
and
$$
A \natural_{\lambda} B = A^{1/2}(A^{-1/2}BA^{-1/2})^{\lambda}A^{1/2}.
$$
In particular we remark that $S_0(A|B) = S(A|B), A \natural_0 B = A$ and $A \natural_1 B = B$.
\label{def:definition3}
\end{definition}

We generalize the definition of the Tsallis relative operator entropy.

\begin{definition}
For $A > 0, B > 0$, $\lambda, \mu \in \mathbb{R}, \lambda \neq 0$ and
$k \in \mathbb{Z}$,
$$
\tilde{T}_{\mu,k,\lambda}(A|B) = \frac{A \natural_{\mu+k\lambda} B-A \natural_{\mu+(k-1)\lambda} B}{\lambda}
$$
is called generalized Tsallis relative operator entropy. In particular we remark that for $\lambda \neq 0$
$$
\tilde{T}_{0,1,\lambda}(A|B) = \frac{A \natural_{\lambda} B-A \natural_{0} B}{\lambda} = \frac{A^{1/2}(A^{-1/2}BA^{-1/2})^{\lambda}A^{1/2}-A}{\lambda} = T_{\lambda}(A|B).
$$
\label{def:definition4}
\end{definition}

We state the relationship among $S_{\mu \pm k \lambda}(A|B), S_{\mu \pm (k+1)\lambda}(A|B)$ and $\tilde{T}_{\mu,k+1,\pm \lambda}(A|B)$.

\begin{proposition}
If $\lambda > 0, \mu \in \mathbb{R}$ and $k = 0,1,2,\ldots$, then
\begin{description}
\item[(1)]  $\displaystyle{S_{\mu-(k+1)\lambda}(A|B) \leq \tilde{T}_{\mu,k+1,-\lambda}(A|B) \leq S_{\mu-k\lambda}(A|B)}$.
\item[(2)]  $\displaystyle{S_{\mu+k\lambda}(A|B) \leq \tilde{T}_{\mu,k+1,\lambda}(A|B) \leq S_{\mu+(k+1)\lambda}(A|B)}$.
\end{description}
\label{prop:proposition3}
\end{proposition}

\begin{flushleft}
{\bf Proof.}  If $\lambda > 0, \mu \in \mathbb{R}$ and $k = 0,1,2,\ldots$,
then it is easy to give the following inequalities for any $t >0$ :
\end{flushleft}
$$
t^{\mu-(k+1)\lambda}\log t \leq \frac{t^{\mu-(k+1)\lambda}-t^{\mu-k\lambda}}{-\lambda} \leq t^{\mu-k\lambda} \log t,
$$
$$
t^{\mu+k\lambda}\log t \leq \frac{t^{\mu+(k+1)\lambda}-t^{\mu+k\lambda}}{\lambda} \leq t^{\mu+(k+1)\lambda}\log t.
$$
Then replace $t$ by $A^{-1/2}BA^{-1/2}$ and multiply $A^{1/2}$ on both sides so we get the desired results.
\ \hfill q.e.d.

\vspace{0.5cm}

By putting $k = 0$ or $1$,  we get the following.

\begin{corollary}
For $A > 0, B > 0, \mu \in \mathbb{R}$ and $\lambda > 0$,
\begin{eqnarray*}
&  & S_{\mu-2\lambda}(A|B) \leq \tilde{T}_{\mu,2,-\lambda}(A|B) \leq S_{\mu-\lambda}(A|B) \\
& \leq & \tilde{T}_{\mu,1,-\lambda}(A|B) \leq S_{\mu}(A|B) \leq \tilde{T}_{\mu,1,\lambda}(A|B) \\
& \leq & S_{\mu+\lambda}(A|B) \leq \tilde{T}_{\mu,2,\lambda}(A|B) \leq S_{\mu+2\lambda}(A|B).
\end{eqnarray*}
\label{cor:corollary2}
\end{corollary}

In particular by putting $\mu = 0, \lambda = 1$, we get the following.

\begin{corollary}
For $A > 0, B > 0$,
\begin{eqnarray*}
&   & S_{-2}(A|B) \leq \tilde{T}_{0,2,-1}(A|B) \leq S_{-1}(A|B) \\
& \leq & \tilde{T}_{0,1,-1}(A|B) \leq S_{0}(A|B) \leq \tilde{T}_{0,1,1}(A|B) \\
& \leq & S_{1}(A|B) \leq \tilde{T}_{0,2,1}(A|B) \leq S_{2}(A|B).
\end{eqnarray*}
We rewrite the following:
\begin{eqnarray*}
&   & S_{-2}(A|B) \leq AB^{-1}A-AB^{-1}AB^{-1}A \leq S_{-1}(A|B) \\
& \leq & A-AB^{-1}A \leq S(A|B) \leq B-A \\
& \leq & S_{1}(A|B) \leq BA^{-1}B-B \leq S_{2}(A|B).
\end{eqnarray*}
\label{cor:corollary3}
\end{corollary}

Similarly we state the relationship among
$\sum_{j=1}^n S_{\mu \pm k\lambda}(A_j|B_j), \\
\sum_{j=1}^n S_{\mu \pm (k+1)\lambda}(A_j|B_j)$ and
$\sum_{j=1}^n \tilde{T}_{\mu,k+1,\pm \lambda}(A_j|B_j)$, where $A_j > 0, B_j > 0$ \\
satisfying $\sum_{j=1}^n A_j = \sum_{j=1}^n B_j = I$. If
$\lambda > 0, \mu \in \mathbb{R}$ and $k = 0,1,2,\ldots$, then we have the
following:
$$
\sum_{j=1}^n S_{\mu-(k+1)\lambda}(A_j|B_j) \leq \sum_{j=1}^n \tilde{T}_{\mu,k+1,-\lambda}(A_j|B_j) \leq \sum_{j=1}^n S_{\mu-k\lambda}(A_j|B_j),
$$
$$
\sum_{j=1}^n S_{\mu+k\lambda}(A_j|B_j) \leq \sum_{j=1}^n \tilde{T}_{\mu,k+1,\lambda}(A_j|B_j) \leq \sum_{j=1}^n S_{\mu+(k+1)\lambda}(A_j|B_j).
$$

By putting $k = 0$ or $1$, we get the following.

\begin{corollary}
For $A > 0, B > 0, \mu \in \mathbb{R}$ and $\lambda > 0$,
\begin{eqnarray*}
&  & \sum_{j=1}^n S_{\mu-2\lambda}(A_j|B_j) \leq \sum_{j=1}^n \tilde{T}_{\mu,2,-\lambda}(A_j|B_j) \leq \sum_{j=1}^n S_{\mu-\lambda}(A_j|B_j) \\
& \leq & \sum_{j=1}^n \tilde{T}_{\mu,1,-\lambda}(A_j|B_j) \leq \sum_{j=1}^n S_{\mu}(A_j|B_j) \leq \sum_{j=1}^n \tilde{T}_{\mu,1,\lambda}(A_j|B_j) \\
& \leq & \sum_{j=1}^n S_{\mu+\lambda}(A_j|B_j) \leq \sum_{j=1}^n \tilde{T}_{\mu,2,\lambda}(A_j|B_j) \leq \sum_{j=1}^n S_{\mu+2\lambda}(A_j|B_j).
\end{eqnarray*}
\label{cor:corollary4}
\end{corollary}

In particular by putting $\mu = 0, \lambda = 1$, we get the following result which is somewhat different type from Corollary in \cite{Fu:par}.

\begin{corollary}
For $A_j > 0, B_j > 0$ satisfying $\sum_{j=1}^n A_j = \sum_{j=1}^n B_j = I$,
\begin{eqnarray*}
&   & \sum_{j=1}^n S_{-2}(A_j|B_j) \leq \sum_{j=1}^n A_jB_j^{-1}A_j-\sum_{j=1}^n A_jB_j^{-1}A_jB_j^{-1}A_j \\
& \leq & \sum_{j=1}^n S_{-1}(A_j|B_j) \leq I-\sum_{j=1}^n A_jB_j^{-1}A_j \leq \sum_{j=1}^n S(A_j|B_j) \leq 0 \\
& \leq & \sum_{j=1}^n S_{1}(A_j|B_j) \leq \sum_{j=1}^n B_jA_j^{-1}B_j-I \leq \sum_{j=1}^n S_{2}(A_j|B_j).
\end{eqnarray*}
\label{cor:corollary5}
\end{corollary}

\section*{Acknowledgement}
The authours thank Professor T. Furuta for reading our manuscript and for valuable comments.
\vspace{0.5cm}


text:
Coded caching was first introduced in 2012 by Maddah-Ali and Niesen \cite{maddah-ali2012} as a solution to the content distribution problem in a wireless setting.
In order to focus on this new technique, the setup ignored variations in content popularity and limited user-to-cache access to exactly one user connecting to one cache.
The authors showed that conventional caching techniques are inefficient in such a setup.
Instead, one can leverage the broadcast capabilities inherent to wireless communications in order to send a small network-coded message that can serve a large number of users at once.
The setup and ideas became fundamental to much of the following literature on the subject, and so in this chapter we give an overview of the results and insights from \cite{maddah-ali2012}.

\subsection{Setup and Notation}
\label{sec:setupbasic}
We begin by describing the setup studied in the seminal work of Maddah-Ali and Niesen \cite{maddah-ali2012}; see Figure~\ref{coded:fig:setup-basic} for an illustration of the system.
Consider a server hosting a content library with $N$ files, labeled $W_1,\ldots,W_N$, of size $F$ bits each.
There are $K$ users in the network, each of which is equipped with a local cache of size $MF$ bits.
The server is connected to the users via an error-free broadcast link.

\begin{figure}
\centering
\includegraphics[scale=\codedsetupfigsscale]{setup-sl.pdf}
\caption{The basic coded caching problem, with $N$ files, $K$ caches, and one user at every cache.
There is an error-free broadcast link from the server to the users.}
\label{coded:fig:setup-basic}
\end{figure}

The system operates in two phases.
We start with a \emph{placement phase} in which all the user caches are populated with content related to the $N$ files.
No restrictions are posed on this placement phase aside from the cache memory constraint.
In particular, the caches are not restricted to holding just files or parts of files; any function (deterministic or not) of the files can be used, and the caches do not necessarily have to hold the same information.
Crucially, this is done before the user requests are revealed to the system.
Next, we move to the \emph{delivery phase}, which starts with each user making a request for one file from the content library.
Based on the user requests and the content stored in the caches, the server transmits a  message, across the error-free broadcast link, of size $RF$ bits intended to serve the requests of all the users.
Each user then combines this message with the contents of its own cache in order to recover the file that it requested.

Our resources here are the \emph{cache memory} $M$ and the \emph{broadcast rate} $R$.
Clearly there is a trade-off between them: the larger the cache, the smaller the size of the broadcast message needed to serve the users.
The goal is to characterize the optimal trade-off.
Formally, we say that a pair $(R,M)$ is achievable if there exists a caching scheme $\mathcal{S}_F$ for every file size $F$ such that:
\begin{itemize}
\item $\mathcal{S}_F$ uses a cache memory at each user of capacity at most $MF$ bits and a broadcast rate from the server of size at most $RF$ bits; and
\item For any collection of user requests, the probability that each user recovers its requested file without error goes to one as $F\to\infty$.
\end{itemize}
Then, our goal is to find, for every $M\ge0$, the information-theoretically optimal rate defined as
\begin{equation}
\label{coded:eq:optimal-rate}
R^\star(M) = \inf \left\{ R : (R,M) \text{ is achievable} \right\}.
\end{equation}
Note that the infimum in \eqref{coded:eq:optimal-rate} is over all possible caching and delivery schemes, without any restrictions.

We discuss a small example below to illustrate the setup as well as some representative caching and delivery schemes.

\subsection{A Small Illustrative Example}
\label{coded:sec:overview:example}
Consider a special case of the system described above with $N = 2$ files, $K = 2$ users, and $M = 1$ memory at each user.
Denote the two files by $A$ and $B$.
Any caching and delivery scheme has to specify what to store in the caches during the placement phase and what the server should transmit during the delivery phase so that the user requests can be served.

For instance, a natural cache placement strategy is to split file $A$ into two equal parts $A_1,A_2$ and similarly file $B$ into $B_1,B_2$.
Each cache stores one half of each file.
In a conventional caching and delivery system, each cache would store $(A_1,B_1)$ and the server would handle each user request via a separate transmission.
For example, if one user wants file $A$ and the other wants file $B$, the server would transmit $A_2$ to the first user and $B_2$ to the second user, and thus the broadcast message size is equivalent to the size of one file.
This scheme leverages the local presence of a cache at every user: each user has access to the half-file present in its cache, which reduces the message size by that amount per user.
However, using network coding techniques, we can design the cache contents in such a way that each user benefits from the contents of both its cache \emph{and the other user's cache}.

To do so, we consider an alternate placement and delivery strategy whose main idea is to store different file parts in each user's cache in a way that enables sending linear combinations of file parts that are simultaneously useful to both users.
Firstly, in the placement phase the first user's cache stores $(A_1,B_1)$ while the second user's cache stores $(A_2,B_2)$.
Secondly, instead of treating the two user requests separately during the delivery phase, we consider them jointly.
For example, if the first user requests file $A$ and the second user requests file $B$, then the server sends a linear combination $A_2\oplus B_1$ on the shared broadcast link, where $\oplus$ denotes the bitwise-XOR operation.
The first user has $A_1$ available in its local cache and can combine $B_1$ with $A_2\oplus B_1$ in order to recover $A_2$; the second user can similarly obtain both $B_1$ and $B_2$.
Thus the users' requests were both served with a broadcast message of size only half a file.

Note that the above scheme reduces the server transmission rate by a factor of two over a conventional scheme.
The main idea is to carefully design the cache contents so as to maximize the number of coded multicasting opportunities during server transmission, enabling the server to send a single message satisfying multiple users, possibly requesting different files, simultaneously.

\subsection{Achievable rate}
\label{sec:centscheme}
The above ideas were generalized in \cite{maddah-ali2012}, which proposed a new caching and delivery scheme for the general setup described in Section~\ref{sec:setupbasic} and also characterized its achievable rate, as shown in the following result.

\begin{theorem}
\label{coded:thm:singlelevel-achieve}
For the system described in Section~\ref{sec:setupbasic} with $M\in\frac{N}{K}\cdot\{0,1,\ldots,K\}$, there exists a placement and delivery scheme which achieves the following server transmission rate:
\[
R(M) = K \cdot \left( 1 - \frac{M}{N} \right) \cdot \frac{1}{1+KM/N}.
\]
For $M\in[0,N]$, the lower convex envelope of these points can be achieved.
\end{theorem}

A rate of $N-M$ can also be achieved (without coded caching) and is useful when the number of files is small, but in the more relevant case where $N\ge K$, the rate in Theorem~\ref{coded:thm:singlelevel-achieve} is smaller and we will henceforth focus on it.

The scheme achieving this rate is a generalization of the ideas described in Section~\ref{coded:sec:overview:example}, and we describe it below.
Before we do that, we can gain some insights about the achievable rate in Theorem~\ref{coded:thm:singlelevel-achieve} by factoring it into three terms.
The first term, $K$, is the total number of users and represents the rate needed without caching, since in the worst case the server might be required to  transmit $K$ distinct files.
The second term, $1-M/N$, is referred to as the \emph{local caching gain}.
It is the gain obtained by the fact that each user already has a fraction $M/N$ of its requested file stored locally.
The third term, $1/(1+KM/N)$, is referred to as the \emph{global caching gain}.
It is specifically achieved by the fact that the server sends coded multicast messages that are useful to many users at once (more precisely, each bit is used by exactly $1+KM/N$ users).
In effect, the coded multicast allows each user to benefit from the caches of all the other users as well, hence the appearance of the total system memory $KM$ in the expression.
This is the gain that the proposed scheme derives over a conventional caching and delivery scheme which serves the user requests through separate unicast server messages.

The significance of the global caching gain can be captured by noticing that the achievable rate in Theorem~\ref{coded:thm:singlelevel-achieve} can be upper-bounded by
\begin{equation}
\label{coded:eq:singlelevel-ub}
R(M) \le \min\left\{K, \frac{N}{M}\right\}\left( 1 - \frac{M}{N} \right).
\end{equation}
Consequently, as long as the total memory in the network is large enough to hold the entire library (i.e., $KM\ge N$),  the achievable rate is at most $N/M-1$, and is thus \emph{independent of the number of users}!

\begin{proof}[Proof of Theorem~\ref{coded:thm:singlelevel-achieve}] We now describe a placement and delivery scheme for the general system described in Section~\ref{sec:setupbasic}.

\emph{Placement phase}: Denote the files by $W_1, W_2, \ldots, W_N$.
Let $t \overset{\Delta}{=} MK/N$.
From the statement of the theorem, note that $t$ is an integer between $0$ and $K$.
Divide each file $W_i$ into $K \choose t$ equal parts and index them as follows:

$$
W_i = \left(W_i^{S} : S \subseteq \{1,2,\ldots,K\}, |S| = t\right).
$$

Note that each subfile is of size $F / {K\choose t}$.
For any user $i$, its cache stores ${K-1\choose t - 1}$ pieces of each file $W_j$ given by

$$
\left(W_j^{S}: i \in S, S \subseteq \{1,2,\ldots,K\}, |S| = t\right).
$$

The total amount of storage each cache needs to store these pieces is given by

$$
N \cdot {K- 1 \choose t - 1} \cdot \frac{NF}{{K\choose t}} = \frac{Ft}{K} = MF
$$

where the last equality follows from the definition of $t$.
Thus, the storage constraint is satisfied at each cache.

\emph{Delivery phase}: For $t = K$, the memory at each cache is $M = N$ and is sufficient to store the entire file catalogue.
Thus, the required server transmission rate is zero.
Below we consider $t \in \{0,1,2,\ldots,K-1\}$.
Denote by $d_i$ the index of the file requested by user $i$, i.e. user $i$ requests file $W_{d_i}$.
Consider a subset $S \subseteq \{1,2,\ldots,K\}$ of size $t + 1$.
Note that for each $j\in S$, there is a subfile of its requested file $W_{d_j}$, given by $W_{d_j}^{S\backslash \{j\}}$, which is stored in the caches at all the other users in $S$.
Corresponding to this subset $S$, the server transmits the message

\begin{equation}
\label{Eqn:transmittedmsg}
\oplus_{j \in S}  W_{d_j}^{S\backslash \{j\}}.
\end{equation}

We repeat the above procedure for each of the ${K\choose t+1}$ subsets of $\{1,2,\ldots,K\}$ of size $t + 1$.

We now show that the above placement and delivery scheme allows each user $i$ to recover its requested file $W_{d_i}$.
Consider a  subset $S \subseteq \{1,2,\ldots,K\}$ of size $t + 1$ such that $i \in S$.
Note from \eqref{Eqn:transmittedmsg} that amongst the $t+1$ subfiles involved in the transmitted message corresponding to $S$, all except its desired subfile $W_{d_i}^{S\backslash \{i\}}$ is already available in the cache of user $i$.
Thus, the user is able to recover its desired subfile.

Repeating the above argument, user $i$ is able to recover all the subfiles of the form

$$
\left(W_{d_i}^{T} : T \subseteq \{1,2,\ldots,K\} \backslash \{i\}, |T| = t\right).
$$

Furthermore, all the other subfiles of the requested file $W_{d_i}$ are already available in the cache of user $i$.
Thus, the above described placement and delivery strategy represents a feasible scheme for the general system.

To complete the proof of the theorem, we have to evaluate the server transmission rate for the proposed scheme.
From \eqref{Eqn:transmittedmsg}, the size of the transmission corresponding to any subset $S$ of size $t+1$ is $F / {K\choose t}$.
Since there is one such transmission corresponding to each such subset, the total transmission size is given by

$$
{K\choose t + 1} \cdot \frac{F}{{K\choose t}} = \frac{K - t}{t+1} = K \cdot \left( 1 - \frac{M}{N} \right) \cdot \frac{1}{1+KM/N}.
$$

\end{proof}

\paragraph{Decentralized scheme}
Note that the above described scheme carefully orchestrates the placement phase to create simultaneous coded multicasting opportunities during the delivery phase.
In particular, the number of users and their identities are required to ensure that each cache is populated with the right file pieces.
Since this kind of information might not always be available in practice, the authors develop a decentralized placement (and corresponding delivery scheme) scheme in \cite{maddah2015decentralized} where each user randomly samples $MF$ bits from the $NF$ bits in the content library.
The achievable rate of this scheme is characterized in \cite{maddah2015decentralized} and is presented below:

\begin{theorem}
\label{deccoded:thm:singlelevel-achieve}
Consider the system described in Section~\ref{sec:setupbasic}.
For $M\in[0,N]$, there exists a decentralized placement scheme and a corresponding delivery scheme which achieves a server transmission rate arbitrarily close to
\[
R_D(M) = K \cdot \left( 1 - \frac{M}{N} \right) \cdot \min\left\{\frac{N}{KM} \left(1 - (1 - M/N)^K\right), \frac{N}{K}\right\}
\]
for a large enough file size $F$.
\end{theorem}

Although the decentralized scheme cannot control the placement as precisely as the centralized scheme, the authors nevertheless show that the decentralized placement creates almost as many coding opportunities as the centralized placement with very high probability.
In fact, the resulting achievable rates are within a constant multiplicative factor of each other.

\subsection{Approximate Optimality}
\label{sec:approxopt}
Next, we examine how the performance of the centralized placement and delivery scheme proposed in Section~\ref{sec:centscheme}  compares to the optimal scheme for this setup with no restrictions on the placement and delivery phases.
The next theorem \cite{maddah-ali2012} states the approximate optimality of the achievable rate $R(M)$ in Theorem~\ref{coded:thm:singlelevel-achieve} with respect to the optimal rate $R^\star(M)$ as defined in \eqref{coded:eq:optimal-rate}.

\begin{theorem}
\label{coded:thm:singlelevel-orderoptimal}
The rate achieved in Theorem~\ref{coded:thm:singlelevel-achieve} is within a constant multiplicative factor of the optimal rate.
Specifically, for all values of $N$, $K$, and $M$,
\[
1 \le \frac{R(M)}{R^\star(M)} \le 12.
\]
\end{theorem}
Note that the bound is independent of the problem parameters: the achievable rate is within a factor of 12 of the optimum even if $N$ and $K$ are arbitrarily large.
Proving Theorem~\ref{coded:thm:singlelevel-orderoptimal} requires deriving information-theoretic lower bounds on the optimal rate using cut-set based arguments \cite{BookThomasCover}.
We will not cover this here and instead point the interested reader to \cite{maddah-ali2012} for details.
Finally, while the constant gap factor of $12$ is indeed quite large, there have been significant improvements in terms of both the achievable rates \cite{amiri2017fundamental, zhang2018fundamental,wei2017novel} as well as the lower bound arguments \cite{wang2016new, wang2017improved, ghasemi2017improved} which can be used to tighten the gap significantly.
In fact, under the restriction of uncoded placement, the rate proposed in Theorem~\ref{coded:thm:singlelevel-achieve} is shown to be exactly optimal in \cite{yu2018exact, wan2016optimality}.


text:
\begin{definition}[Definition:Morphism]
Let $\mathbf C$ be a [[Definition:Metacategory|metacategory]].
A '''morphism''' of $\mathbf C$ is an [[Definition:Object|object]] $f$, together with:
* A [[Definition:Domain (Category Theory)|domain]] $\operatorname{dom} f$, which is an [[Definition:Object (Category Theory)|object]] of $\mathbf C$
* A [[Definition:Codomain (Category Theory)|codomain]] $\operatorname{cod} f$, also an [[Definition:Object (Category Theory)|object]] of $\mathbf C$
\end{definition}

config: wiki


TITLE: Finding the closed form for a sequence
QUESTION [6 upvotes]: My teacher isn't great with explaining his work and the book we have doesn't cover anything like this. He wants us to find a closed form for the sequence defined by:
$P_{0} = 0$
$P_{1} = 1$
$\vdots$
$P_{n} = -2P_{n-1} + 15P_{n-2}$
I'm not asking for a straight up solution, I just have no idea where to start with it. The notes he gave us say:

We will consider a linear difference equation that gives the
  Fibonacci sequence.
$y(k) + A_1y(k -1) + A_2y(k -2) = \beta$
That's the general form for a difference equation in which each term is formed from the
  two preceding terms. We specialize this for our Fibonacci sequence by setting $A_1 = 1, $ >$
>A_2 = 1,$ and $ \beta = 0$. With some rearrangement, we get
$y(k) = y(k - 1) + y(k - 2)$
which looks more like the general form for the Fibonacci sequence.
To solve the difference equation, we try the solution $y(k) = Br^k$. Plugging that in, we
  obtain
$Br^{k-2} (r^2 - r - 1) = 0$

I have no idea where the $Br^k$ is coming from nor what it means, and he won't explain it in any sort of terms we can understand.
If someone could help me with the basic principle behind finding a closed form with the given information I would be eternally grateful.

EDIT: Using the information given (thank you guys so much) I came up with
$y(k) = \frac{1}{8}(3)^k - \frac{1}{8}(-5)^k$
If anyone has ran through let me know what you found, but I'm in no way asking you guys to do that. It's a lot of work to help some random college student.

REPLY [5 votes]: Since you wrote "I have no idea where the $Br^k$ is coming from" and since Mhenni's solution, though perfectly correct, said to "just assume" such a solution, I think the following may help.  There is a general theorem describing the solutions of linear recurrences of the form $X(n)=a_1X(n-1)+a_2X(n-2)+\dots+a_mX(n-m)$, where $m$ is fixed (in your examples it's $2$) and the $a_i$ are constants.  Part of the theorem says that, if there are $m$ solutions of the special form $X(n)=r^n$ for $m$ different values of $r$, then every solution is obtainable as a linear combination of these $m$ special solutions.  (There's also information in the theorem about what happens if there are not $m$ different solutions of that special form, but that additional information isn't relevant for your examples, so I'll postpone it to the last paragraph of this answer.)
In view of this (part of the) theorem, you can attack recurrence relations of this sort by first trying to find solutions off the special form $X(n)=r^n$.  So plug this $X(n)$ into the recurrence, leaving $r$ unspecified for the time being.  You get an equation that simplifies to $r^m=a_1r^{m-1}+a_2r^{m-2}+\dots+a_m$.  This is a polynomial equation of degree $m$ for the unknown $r$.  If it has $m$ different solutions (as it does in your examples), then you win.  You have enough special solutions $X(n)=r^n$, one for each solution $r$, to invoke the general theorem.  Any solution is a linear combination, with some constant coefficients, of these $m$ special solutions.  You can determine the coefficients by using the initial conditions that were given with the recursion equation.  This part of the job is quite easy, because it comes down to solving a system of linear equations for the unknown coefficients.
If $r^m=a_1r^{m-1}+a_2r^{m-2}+\dots+a_m$ has fewer than $m$ distinct roots, because some of the roots have multiplicity greater than $1$, then your recurrence has additional solutions of the form $X(n)=n^jr^n$, where $j$ ranges from $0$ up to but not including the multiplicity of the root $r$.


TITLE: A problem about conditional probability.
QUESTION [1 upvotes]: This is an exercise of Shiryaev's Probability on page 233:

Let $\xi$ and $\eta$ be independent identically distributed random variables with $E\xi$ defined. Show that $$E(\xi\mid\xi+\eta)=E(\eta\mid\xi+\eta)=\frac{\xi+\eta}{2} \text{(a.s.)}$$

How can I say that for any $A\in\sigma(\xi+\eta)$ we have $E\xi I_A=E\eta I_A$.
Thank you!

REPLY [3 votes]: The distributions of $(\xi,\eta)$ and $(\xi',\eta')=(\eta,\xi)$ coincide hence, for every measurable bounded $u$,
$$
\mathbb E(\xi u(\xi+\eta))=\mathbb E(\xi' u(\xi'+\eta'))=\mathbb E(\eta u(\xi+\eta)).
$$
In particular, if $A$ is in $\sigma(\xi+\eta)$, there exists a Borel subset $B$ such that $A=[\xi+\eta\in B]$ hence, for $u=\mathbf 1_B$, the identity above yields $\mathbb E(\xi\mathbf 1_A)=\mathbb E(\eta\mathbf 1_A)$.