text:
\begin{document}

\title[Stable polynomials, orientations and matchings]{Short survey on \\ stable polynomials, orientations and matchings}

\author[P. Csikv\'ari]{P\'{e}ter Csikv\'{a}ri}

\address{Alfr\'ed R\'enyi Institute of Mathematics, H-1053 Budapest Re\'altanoda utca 13/15 \and ELTE: E\"{o}tv\"{o}s Lor\'{a}nd University \\ Mathematics Institute, Department of Computer
Science \\ H-1117 Budapest
\\ P\'{a}zm\'{a}ny P\'{e}ter s\'{e}t\'{a}ny 1/C}

\email{peter.csikvari@gmail.com}

\author[\'A. Schweitzer]{\'Ad\'am Schweitzer}

\address{E\"{o}tv\"{o}s Lor\'{a}nd University \\ Mathematics Institute \\ H-1117 Budapest
\\ P\'{a}zm\'{a}ny P\'{e}ter s\'{e}t\'{a}ny 1/C \\ Hungary
}

\email{adamschweitzer1@gmail.com}

\thanks{The first author  is supported by the Counting in Sparse Graphs Lend\"ulet Research Group of the Alfr\'ed R\'enyi Institute of Mathematics. The second author is partially supported by the EFOP program (EFOP-3.6.3-VEKOP-16-2017-00002).}

 \subjclass[2010]{Primary: 05C30. Secondary: 05C31, 05C70}

 \keywords{stable polynomials, orientations, matchings}

\begin{abstract} This is a short survey about the theory of stable polynomials and its applications. It gives  self-contained proofs of two theorems of Schrijver.
One of them asserts that for a $d$--regular bipartite graph $G$ on $2n$ vertices, the number of perfect matchings, denoted by $\prm(G)$,  satisfies
$$\prm(G)\geq \bigg( \frac{(d-1)^{d-1}}{d^{d-2}} \bigg)^{n}.$$
The other theorem claims that for even $d$ the number of Eulerian orientations of a $d$--regular graph $G$ on $n$ vertices, denoted by $\e(G)$, satisfies
$$\e(G)\geq \bigg(\frac{\binom{d}{d/2}}{2^{d/2}}\bigg)^n.$$
To prove these theorems we use the theory of stable polynomials, and give a common generalization of the two theorems.
\end{abstract}

\maketitle

\section{Introduction}

In this paper we will give new proofs for the following theorems of Schrijver. The first theorem is about perfect matchings of regular bipartite graphs.

\begin{Th}[Schrijver \cite{Sch2}] \label{matching}
Let $G=(A,B,E)$ be $d$--regular bipartite graph on $2n$ vertices. Let $\prm(G)$ denote the number of perfect matchings of $G$. Then
$$\prm(G)\geq \bigg( \frac{(d-1)^{d-1}}{d^{d-2}} \bigg)^{n}.$$
\end{Th}

The next theorem is about Eulerian orientations of regular graphs. Recall that an orientation of a graph $G$ is Eulerian if the in-degree and out-degree are equal at each vertex. (In particular, the degree of a vertex must be even.)

\begin{Th}[Schrijver \cite{Sch1}] \label{orientation}
Let $G$ be a graph, where the degree of the vertex $v$ is $d_v$. Suppose that $d_v$ is even for each $v$. Let $\e(G)$ denote the number of Eulerian orientations of the graph $G$. Then
$$\e(G)\geq \prod_{v\in V(G)}\frac{\binom{d_v}{d_v/2}}{2^{d_v/2}}.$$
\end{Th}

The main goal of this paper is to show that these two theorems have a common generalization. To spell out this generalization we will count the number of orientations in a graph with prescribed in-degree sequence.

\begin{Def}
Let $\underline{r}=(r_v)_{v\in V(G)}\in \mathbb{Z}^{V(G)}$. Let $\e_{\underline{r}}(G)$ denote the number of those orientations of the graph $G$, where the in-degree of the vertex $v$ is $r_v$.
\end{Def}

Observe that if we have a $d$--regular bipartite graph $G=(A,B,E)$, then the perfect matchings are in bijection with those orientations of the graph, where the in-degree of the vertices in $A$ is $1$, and is $d-1$ in case of the vertices of $B$. Indeed, simply orient each edge of a perfect matching towards $A$, and every other edge towards $B$. Clearly, if we have such an orientation, then the edges oriented towards $A$ form a perfect matching.
\bigskip

The following theorem might look technical, but it easily implies both  Theorem~\ref{matching} and \ref{orientation}.

\begin{Th} \label{general}
Let $G=(V,E)$ be a graph with degree $d_v$ at vertex $v$, and let
$\e_{\underline{r}}(G)$ denote the number of orientations of the graph $G$, where the in-degree of the vertex $v$ is $r_v$.  Then
$$\e_{\underline{r}}(G)\geq \prod_{v\in V(G)}\binom{d_v}{r_v}\bigg(\frac{r_v}{d_v}\bigg)^{r_v}\bigg(\frac{d_v-r_v}{d_v}\bigg)^{d_v-r_v}\cdot \inf_{x_u>0}\frac{\prod_{(u,v)\in E(G)}(x_u+x_v)}{\prod_{u\in V(G)}x_u^{r_u}}.$$
\end{Th}

We remark that the role of the multivariate polynomial $P_G(\underline{x}):=\prod_{(u,v)\in E(G)}(x_u+x_v)$ in the theorem comes from the fact that
$$\prod_{(u,v)\in E(G)}(x_u+x_v)=\sum_{\underline{r}}\e_{\underline{r}}(G)\prod_{u\in V(G)}x_u^{r_u}.$$
In other words, this theorem is about how to give a lower bound on a coefficient of a multivariate polynomial in terms of the polynomial. It turns out that this lower bound is possible, because the polynomial $P_G(\underline{x})$ is a real stable polynomial. The definition of real stability is the following.

\begin{Def}
A multivariate polynomial $P(x_1,\dots ,x_n)$ with complex coefficients is stable if $P(z_1,\dots ,z_n)\neq 0$ whenever $\mathrm{Im}(z_i)>0$ for $i=1,\dots ,n$. A polynomial is called real stable if it is stable and its coefficients are real.
\end{Def}

Note that a univariate polynomial with real coefficients is  stable if and only if it is real-rooted. So real stability is a generalization of real-rootedness for multivariate polynomials.

We remark that Gurvits \cite{Gur1} already gave a  proof of Theorem~\ref{matching} using real stable polynomials. He used the polynomial
$$Q(\underline{x})=\prod_{v\in B}\bigg(\sum_{u\in A}x_u\bigg)$$
in his proof. In this case the coefficient of $\prod_{u\in A}x_u$ is exactly $\prm(G)$. In fact, we will follow exactly the strategy of Gurvits.  This strategy is based on two concepts, the real stability and the capacity of a polynomial. The latter was invented by Gurvits himself. We will review these concepts in the next section.
\bigskip

\noindent \textbf{What is new in this paper?} The proof
of Theorem~\ref{coefficient theorem} is new, the theorem itself appeared in \cite{Gur3} in a slightly different form.
The use of the polynomial $P_G(\underline{x})$ in these proofs also seems to be new, although variants of this polynomial appeared in \cite{Gur3}, but never exactly this one. Proving Theorem~\ref{orientation} via stable polynomials is also new. On the other hand, the general strategy is not new at all. In fact, one of our main goals is to advertise this theory, so this paper can be considered as a mini survey.
\bigskip

\noindent \textbf{This paper is organized as follows.} In the next section we collect the basic facts about real stable polynomials and capacity. In Section 3 we prove Theorem~\ref{general} and derive Theorem~\ref{matching} and \ref{orientation} from it. In Section 4 we collected pointers to the literature.

\section{Real stability and capacity}

In this section we review the basic properties of real stability and capacity. To keep this paper  self-contained we will prove every result that we use apart from the Hermite-Sylvester criterion.

\subsection{Stability} Recall that a multivariate polynomial $P(x_1,\dots ,x_n)$ is real stable if it has real coefficients, and $P(z_1,\dots ,z_n)\neq 0$ whenever $\mathrm{Im}(z_i)>0$ for $i=1,\dots ,n$. We have seen that real stability is a generalization of univariate real-rooted polynomials. As the next lemma shows there is a more direct connection between the two concepts.

\begin{Lemma} \label{stable-real-rooted} A multivariate polynomial $P(z_1,\dots ,z_n)\in \R[z_1,\dots ,z_n]$ is stable if and only if for all $\underline{v}=(v_1,\dots, v_n)\in \R^n$ and $\underline{u}=(u_1,\dots ,u_n)\in \R^n_{>0}$, the univariate polynomial $g(t)=P(v_1+tu_1,\dots ,v_n+tu_n)$ is real-rooted.
\end{Lemma}

\begin{proof} Let $\mathbb{H}=\{z \ |\ \mathrm{Im}(z)>0\}$. First suppose that $g(t)$ is not real rooted, then it has a root $a+bi\in \C$, where $b\neq 0$. Since the coefficients of $g$ are real, $a\pm bi$ are both zeros of $g$. So we can assume that $b>0$. But then $\mathrm{Im}(v_j+u_j(a+bi))=bu_j>0$ shows that the numbers $z_j=v_j+u_j(a+bi) \in \HH$ for $j=1,\dots ,n$ and $P(z_1,\dots ,z_n)=0$, thus $P$ is not stable.

Next suppose that $P$ is not stable, it has some zero $(z_1,\dots ,z_n)\in \HH^n$. Let $z_j=a_j+b_ji$. Then $b_j>0$. Then the polynomial
$g(t)=P(a_1+tb_1,\dots ,a_n+tb_n)$ satisfies that $(a_1,\dots ,a_n)\in \R^n$ and $(b_1,\dots ,b_n)\in \R^n_{>0}$ and has a non-real zero, namely $i$.
\end{proof}

We will also need the following lemma.

\begin{Lemma} \label{real-rooted-convergence}
Given a polynomial $P(x)$ and suppose that $(P_n(x))_n$ is a sequence of real-rooted  polynomials such that
$\lim_{n\to \infty}P_n(x)=P(x)$ coefficientwise. Then $P(x)$ is real-rooted.
\end{Lemma}

Lemma~\ref{real-rooted-convergence} is a simple consequence of the well-known Hermite-Sylvester criterion. For a short, simple proof see that paper \cite{Nat}.

\begin{Lemma}[Hermite-Sylvester criterion] \label{HS-criterion}
Let $P(x)$ be a non-constant polynomial of degree $d$ with real coefficients and $\lambda_1,\dots ,\lambda_d$ not necessarily distinct zeros. Let $m_k=\sum_{j=1}^d\lambda_j^k$. Then $P(x)$ is real-rooted if and only if the $d\times d$ matrix $(m_{i+j-2})_{i,j=1,\dots ,d}$ is positive semi-definite.
\end{Lemma}

Note that $m_k$ can be computed from the coefficients by the Newton-Girard identities, so they are continuous functions of the coefficients. Hence the  Hermite-Sylvester criterion implies Lemma~\ref{real-rooted-convergence}.

Next we collect some operations that preserve stability. A general theory of stability preserver operations is developed by Borcea and Br\"and\'en \cite{BoBr}. We also recommend the paper of Choe, Oxley, Sokal and Wagner \cite{COSW} for a comprehensive list of operations that preserves stability.

\begin{Th}
Let $P(x_1,\dots ,x_n)$ be a real stable polynomial. Suppose that the degree of $x_1$ in $P$ is $d$. Then the following hold true.\\
(a) The polynomial $x_1^dP(-1/x_1,x_2,\dots x_n)$ is real stable.\\
(b) If $a\in \mathbb{R}$, then $P(a,x_2,\dots ,x_n)$ is real stable or the constant $0$ polynomial.\\
(c) The polynomial $\frac{\partial}{\partial x_1}P$ is real stable or the constant $0$ polynomial.\\
\end{Th}

\begin{proof}
As before let $\mathbb{H}=\{z \ |\ \mathrm{Im}(z)>0\}$. Then the first claim is trivial since $z\mapsto \frac{-1}{z}$ maps $\mathbb{H}$ to $\mathbb{H}$.
\medskip

Next we prove part (b). By Lemma~\ref{stable-real-rooted} the polynomial $P(a+\varepsilon t,v_2+tu_2,\dots ,v_n+tu_n)$ is real-rooted for every $\varepsilon,u_2,\dots u_n\in \R_{>0}$ and $a,v_2,\dots ,v_n\in \R$. Let $\varepsilon \to 0$, then by Lemma~\ref{real-rooted-convergence} we get that $P(a,v_2+tu_2,\dots ,v_n+tu_n)$ is real-rooted or the constant $0$ function for every $u_2,\dots ,u_n\in \R_{>0}$ and $v_2,\dots ,v_n$. Now using the  other direction of Lemma~\ref{stable-real-rooted} we get that $P(a,x_2,\dots ,x_n)$ is a real stable polynomial.

Next we prove part (c). Let
$$P(x_1,\dots ,x_n)=\sum_{k=0}^dP_k(x_2,\dots ,x_n)x_1^k.$$
First we show that $P_d(x_2,\dots ,x_n)$ is a real stable polynomial. By part (a)
$$R(x_1,\dots ,x_n):=x_1^dP(-1/x_1,x_2,\dots x_n)=\sum_{k=0}^dP_k(x_2,\dots ,x_n)(-1)^kx_1^{d-k}$$
is real stable. Then $R(0,x_2,\dots ,x_n)=(-1)^dP_d(x_2,\dots ,x_n)$ is real stable, and so $P_d(x_2,\dots ,x_n)$ is real stable.

Now let $Q=\frac{\partial}{\partial x_1}P$, and let $\underline{a}=(a_1,a_2,\dots, a_n)\in \mathbb{H}^n$. We show that if $Q\not\equiv 0$, then $\mathrm{Im}\left(\frac{Q(\underline{a})}{P(\underline{a})}\right)<0$. Note that here we use that $P$ is stable, so $P(\underline{a})\neq 0$, and we can divide with it. If $d=0$ then $Q\equiv 0$. We can assume that $d\geq 1$. Let
$$g(x):=P(x,a_2,\dots ,a_n)=\sum_{k=0}^dP_k(a_2,\dots ,a_n)x^k.$$
Note that $P_d(a_2,\dots ,a_n)\neq 0$ since $P_d$ is real-stable. So $g(x)$ has degree $d\geq 1$. Then
$g(x)=c\prod_{i=1}^d(x-\rho_i)$, and we have
$$\frac{g'(x)}{g(x)}=\sum_{i=1}^d\frac{1}{x-\rho_i}.$$
Note that $\mathrm{Im}(\rho_i)\leq 0$, otherwise $P(\rho_i,a_2,\dots ,a_n)=0$ would yield a zero in $\mathbb{H}^n$. Hence
$$\mathrm{Im}\left(\frac{Q(\underline{a})}{P(\underline{a})}\right)=\mathrm{Im} \left(\frac{g'(a_1)}{g(a_1)}\right)=\mathrm{Im} \left(
\sum_{i=1}^d\frac{1}{a_1-\rho_i}\right)<0.$$
In particular, this shows that $Q(\underline{a})\neq 0$. Hence $Q$ is stable. (Remark: we essentially repeated the proof of Gauss--Lucas theorem that asserts that the zeros of the derivative of a polynomial lie in the convex hull of the zeros of the polynomial.)
\medskip

\end{proof}

\subsection{Capacity of a polynomial} In this section we introduce the concept capacity.

\begin{Def}[Gurvits \cite{Gur1}]
Let $P(x_1,\dots ,x_n)$ be a multivariate polynomial with non-negative coefficients. Let $\underline{\alpha}=(\alpha_1,\dots ,\alpha_n)$ be a non-negative vector. Then the $\underline{\alpha}$-capacity of the polynomial $P(x_1,\dots ,x_n)$ is
$$\mathrm{cap}_{\underline{\alpha}}(P)=\inf_{x_1,\dots ,x_n>0}\frac{P(x_1,\dots ,x_n)}{\prod_{i=1}^nx_i^{\alpha_i}}.$$
\end{Def}

Note that if the numbers $\alpha_i$ are integers, then the capacity is an upper bound for the coefficient of the term $\prod_{i=1}^nx_i^{\alpha_i}$.

So in Theorem~\ref{general} we had $\mathrm{cap}_{\underline{r}}(P_G)$ in the statement.
In the definition of capacity we never used that $P$ is real stable, but it turns out that this concept is especially useful when we study stable polynomials. The main reason for this phenomenon is that one can often govern the capacity for stability preserver operators. A general theory of capacity preserver linear operators was developed in the  paper of Leake and Gurvits \cite{LeGu}.   The following theorem is a special case of their theory.

\begin{Th} \label{capacity preserving}
Let $P(x_1,\dots ,x_n)$ be a real stable polynomial with non-negative coefficients. Suppose that the degree of $x_1$ in $P$ is $d$. Let
$$Q=\frac{1}{r!}\bigg( \frac{\partial^r}{\partial x_1^r}P\bigg)\bigg|_{x_1=0}.$$
In other words, if we expand $P$ as a polynomial of $x_1$, then $Q$ is the coefficient of $x_1^r$. \\
Let $\underline{\alpha}=(\alpha_1,\dots ,\alpha_n)$, where $\alpha_1=r$, and $\underline{\alpha}'=(\alpha_2,\dots ,\alpha_n)$. Then
$$\mathrm{cap}_{\underline{\alpha}'}(Q)\geq \binom{d}{r}\bigg(\frac{r}{d}\bigg)^{r}\bigg(\frac{d-r}{d}\bigg)^{d-r}\mathrm{cap}_{\underline{\alpha}}(P).$$
\end{Th}

An immediate corollary of Theorem~\ref{capacity preserving} is the following theorem.

\begin{Th}[Coefficient lemma for  stable polynomials with non-negative coefficients] \label{coefficient theorem}
Let $P(x_1,\dots ,x_n)$ be a real stable polynomial with non-negative coefficients. Suppose that the degree of $x_i$ in $P$ is at most $d_i$ for $i=1,\dots ,n$. Let $\underline{r}=(r_1,\dots ,r_n)$ and $a_{\underline{r}}$ be the coefficient of $\prod_{i=1}^nx_i^{r_i}$ in $P$. Then
$$a_{\underline{r}}\geq \prod_{i=1}^n\binom{d_i}{r_i}\bigg(\frac{r_i}{d_i}\bigg)^{r_i}\bigg(\frac{d_i-r_i}{d_i}\bigg)^{d_i-r_i}\mathrm{cap}_{\underline{r}}(P).$$
\end{Th}

If we apply Theorem~\ref{coefficient theorem} to the real stable polynomial  $P_G(\underline{x})=\prod_{(u,v)\in E(G)}(x_u+x_v)$ we get Theorem~\ref{orientation}.

The key lemma to prove the above theorems is the following.

\begin{Lemma} \label{main lemma}
Let $p(z)=\sum_{k=0}^da_kz^k$ be a real-rooted polynomial with non-negative coefficients. Then
$$a_r\geq \binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}\inf_{t>0}\frac{p(t)}{t^r}.$$
\end{Lemma}

We remark that this lemma for $r=1$ was the main ingredient of the proof of Gurvits for Theorem~\ref{matching}.

We will derive Lemma~\ref{main lemma} from the following statement.

\begin{Lemma} \label{main lemma2}
Let $p(z)=\sum_{k=0}^da_kz^k$ be a real-rooted polynomial with non-negative coefficients. Suppose that $p(1)=1$ and $p'(1)=r$ is an integer. Then
$$a_r\geq \binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}.$$
\end{Lemma}

We remark that Lemma~\ref{main lemma2} is a special case of the following theorem of Hoeffding \cite{Hoe}. Nevertheless to keep our paper self-contained we will give a proof of Lemma~\ref{main lemma2}. The intuitive meaning of Hoeffding's theorem is that among probability distributions coming from real-rooted polynomials and fixed expected value the binomial distribution is the least concentrated around its expected value.

\begin{Th}[Hoeffding \cite{Hoe}] \label{Hoeffding} Let $p(z)=\sum_{k=0}^dp_kz^k$ be a real-rooted polynomial with $p_k\geq 0$, and $p(1)=1$, that is, $\sum_{k=0}^dp_k=1$. Let $s$ be defined by the equation $\sum_{k=0}^dkp_k=ds$.
Suppose that for non-negative integers $b$ and $c$ we have $b\leq ds\leq c$. Then
$$\sum_{k=b}^cp_k\geq \sum_{k=b}^c\binom{d}{k}s^k(1-s)^{d-k}.$$
\end{Th}

 It is  easy to see that Lemma~\ref{main lemma2} is a special case of Lemma~\ref{main lemma}, but as the following proof shows they are actually equivalent statements.

\begin{proof}[Proof of Lemma~\ref{main lemma} from Lemma~\ref{main lemma2}.]
Suppose that $p(z)=\sum_{k=m}^Ma_kz^k$, where $a_m,a_M>0$.
If $r<m$ or $r>M$, then $\inf_{t>0} \frac{p(t)}{t^r}=0$ so the claim is true in this case. If $r=m$, then $\inf_{t>0} \frac{p(t)}{t^r}=a_m$ so the claim is again true. If $r=M$, then  $\inf_{t>0} \frac{p(t)}{t^r}=a_M$ so we are again done.
Thus we can assume that $m<r<M$.
Observe that $\frac{tp'(t)}{p(t)}$ is monotone increasing, $\frac{tp'(t)}{p(t)}\big|_{t=0}=m$ and $\lim_{t\to \infty} \frac{tp'(t)}{p(t)}=M$. So we can choose $t_r>0$ in such a way that $\frac{t_rp'(t_r)}{p(t_r)}=r$. Let us consider the probability distribution $q_j=\frac{a_jt_r^j}{p(t_r)}$. Then $\sum_k kq_k=r$, and $\sum_{j=0}^dq_jz^j$ is still a real-rooted polynomial.
Next let us apply Lemma~\ref{main lemma2}. Then
$$\frac{a_rt_r^r}{p(t_r)}=q_r\geq \binom{d}{r}\left(\frac{r}{d}\right)^r\left(\frac{d-r}{d}\right)^{d-r}.$$
In other words,
$$a_r\geq \binom{d}{r}\left(\frac{r}{d}\right)^r\left(\frac{d-r}{d}\right)^{d-r}\frac{p(t_r)}{t_r^r}\geq \binom{d}{r}\left(\frac{r}{d}\right)^r\left(\frac{d-r}{d}\right)^{d-r}\inf_{t>0}\frac{p(t)}{t^r}.$$
\end{proof}

Before we prove Lemma~\ref{main lemma2} we show that Lemma~\ref{main lemma} indeed implies Thorem~\ref{capacity preserving}.

\begin{proof}[Proof of Theorem~\ref{capacity preserving}]
For fixed $a_2,\dots ,a_n$ consider the polynomial
$$g(x)=P(x,a_2,\dots ,a_{n}).$$
Clearly, $\frac{1}{r!}\frac{d^r}{dx^r}g(x)\Big|_{x=0}=Q(a_2,\dots ,a_{n})$. Since $P$ is stable, and we substituted $a_i\in \mathbb{R}$ into it, $g(x)$ is stable. In other words, it is real-rooted. Thus we can use Theorem~\ref{main lemma}:
$$a_r \geq  \binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\Bigg)^{d-r}\inf_{x>0}\frac{g(x)}{x^r}.$$
Hence we have
\begin{align*}
\frac{Q(a_2,\dots ,a_{n})}{\prod_{i=2}^{n}a_i^{\alpha_i}}=\frac{\frac{1}{r!}\frac{d^r}{dx^r}g(x)\Big|_{x=0}}{\prod_{i=2}^{n}a_i^{\alpha_i}}&\geq \binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}\frac{1}{\prod_{i=2}^{n}a_i^{\alpha_i}}\inf_{x>0}\frac{g(x)}{x^r}\\
                            &= \binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}\inf_{x>0} \frac{P(x,a_2,\dots ,a_{n})}{x^r\cdot \prod_{i=2}^{n} a_i^{\alpha_i}}\\
							 &\geq \binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}\mathrm{cap}_{\underline{\alpha}}(P).
\end{align*}
Taking infimum on the left side we get that
$\mathrm{cap}_{\underline{\alpha}'}(Q)\geq \binom{d}{r}\big(\frac{r}{d}\big)^r\big(\frac{d-r}{d}\big)^{d-r}\mathrm{cap}_{\underline{\alpha}}(P)$.
\end{proof}

\subsection{Proof of Lemma~\ref{main lemma2}}
In this section we prove Lemma~\ref{main lemma2}. The condition on the non-negativity of the coefficients and $p(1)=1$ implies that $p(z)$ can be written as follows:
$$p(z)=\prod_{i=1}^d(1-\alpha_i+\alpha_iz),$$
where $0\leq \alpha_i\leq 1$. Indeed, as all coefficients are non-negative, there can be no positive roots, thus using $p(1)=1$ the polynomial can be rewritten in the following way:
$$p(z)=a_n\prod_{i=1}^d(z+\rho_i)=\prod_{i=1}^d\left(\frac{z+\rho_i}{1+\rho_i}\right)=\prod_{i=1}^d(1-\alpha_i+\alpha_iz),$$
where $\alpha_i=\frac{1}{1+\rho_i}$.
Note that
$$r=p'(1)=\sum_{i=1}^d \alpha_i\prod_{j\not=i}(\alpha_j+1-\alpha_j)=\sum_{i=1}^d \alpha_i.$$
Consider the domain
$$D_{d,r}=\left\{(\alpha_1,\dots ,\alpha_d)\in \mathbb{R}^d\ \Big|\ 0\leq \alpha_i\leq 1\ (i=1,\dots ,d),\ \sum_{i=1}^d\alpha_i=r\right\}.$$
Clearly, the coefficient $a_r$ of $z^r$ in $p(z)$ can be expressed as
$$a_{r}=\sum_{\substack{K\subset[n]\\ |K|=r}}\prod_{j\in K}\alpha_j\prod_{j\not\in K}(1-\alpha_j).$$
So let us introduce the function
$$f_{d,r}(x_1,\ldots,x_d)=\displaystyle\sum_{\substack{K\subset[n]\\ |K|=r}}\prod_{j\in K}x_j\prod_{j\not\in K}(1-x_j).$$
Clearly, the statement of Lemma~\ref{main lemma2} is equivalent with
$$\min_{\underline{x}\in D_{d,r}}f_{d,r}(\underline{x})=f_{d,r}\left(\frac{r}{d},\dots ,\frac{r}{d}\right)=\binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}.$$
We will prove this statement by induction on $d$. The case $d=1$ and $r=0$ or $r=1$ is trivial. In general, the case $r=0$ or $r=d$ is trivial since $D_{d,r}$ consists of only one point in this case. So we can always assume that $0<r<d$. First we prove that the statement is true for the boundary $\partial D_{d,r}$. Then we will prove that  if $\underline{x}\neq \left(\frac{r}{d},\dots ,\frac{r}{d}\right)$, then we either have a point $\underline{y}\in \partial D_{d,r}$ for which $f_{d,r}(\underline{x})\geq f_{d,r}(\underline{y})$ or there exists an $\underline{x}'\in D_{d,r}$ such that $f_{d,r}(\underline{x})> f_{d,r}(\underline{x}')$.
 The compactness of $D_{d,r}$ then implies that $\min_{\underline{x}\in D_{d,r}}f_{d,r}(\underline{x})=f_{d,r}\left(\frac{r}{d},\dots ,\frac{r}{d}\right)$.

So let us first prove that for $\underline{x}\in \partial D_{d,r}$ we have $f_{d,r}(\underline{x})\geq f_{d,r}\left(\frac{r}{d},\dots ,\frac{r}{d}\right)$.
Clearly, if $\underline{x}\in \partial D_{d,r}$ then one of its coordinates is $0$ or $1$. If we delete this coordinate, then the obtained vector $\underline{x}'$ is in $D_{d-1,r}$ in the first case, and in $D_{d-1,r-1}$ in the second case. Furthermore, $f_{d,r}(\underline{x})=f_{d-1,r}(\underline{x}')$ in the first case, and $f_{d,r}(\underline{x})=f_{d-1,r-1}(\underline{x}')$ in the second case. By induction we know that we have
$$f_{d-1,r}(\underline{x}')\geq \binom{d-1}{r}\bigg(\frac{r}{d-1}\bigg)^r\bigg(\frac{d-1-r}{d-1}\bigg)^{d-1-r}$$
for $\underline{x}'\in D_{d-1,r}$, and
$$f_{d-1,r-1}(\underline{x}')\geq \binom{d-1}{r-1}\bigg(\frac{r-1}{d-1}\bigg)^{r-1}\bigg(\frac{d-r}{d-1}\bigg)^{d-r}$$
for $\underline{x}'\in D_{d-1,r-1}$. Let us introduce the function $\ell_{n,k}=x^k(1-x)^{n-k}$. It is easy to see that it takes its maximum at the value $x=k/n$ in the interval $[0,1]$ as its derivative is $(k-nx)x^{k-1}(1-x)^{n-k-1}$. Hence
\begin{align*}
\binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}&=\binom{d-1}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r-1}\\
&=\binom{d-1}{r}\ell_{d-1,r}\left(\frac{r}{d}\right)\\
&<\binom{d-1}{r}\ell_{d-1,r}\left(\frac{r}{d-1}\right)\\
&=\binom{d-1}{r}\bigg(\frac{r}{d-1}\bigg)^r\bigg(\frac{d-1-r}{d-1}\bigg)^{d-1-r}
\end{align*}
and
\begin{align*}
\binom{d}{r}\bigg(\frac{r}{d}\bigg)^r\bigg(\frac{d-r}{d}\bigg)^{d-r}&=\binom{d-1}{r-1}\bigg(\frac{r}{d}\bigg)^{r-1}\bigg(\frac{d-r}{d}\bigg)^{d-r}\\
&=\binom{d-1}{r-1}\ell_{d-1,r-1}\left(\frac{r}{d}\right)\\
&<\binom{d-1}{r-1}\ell_{d-1,r-1}\left(\frac{r-1}{d-1}\right)\\
&=\binom{d-1}{r-1}\bigg(\frac{r-1}{d-1}\bigg)^{r-1}\bigg(\frac{d-r}{d-1}\bigg)^{d-r}.
\end{align*}
Hence for $\underline{x}\in \partial D_{d,r}$ we have $f_{d,r}(\underline{x})\geq f_{d,r}\left(\frac{r}{d},\dots ,\frac{r}{d}\right)$.

Next we show that if $\underline{x}\neq \left(\frac{r}{d},\dots ,\frac{r}{d}\right)$, then either
we have a point $\underline{y}\in \partial D_{d,r}$ for which $f_{d,r}(\underline{x})\geq f_{d,r}(\underline{y})$ or
there exists an $\underline{x}'\in D_{d,r}$ such that $f_{d,r}(\underline{x})> f_{d,r}(\underline{x}')$. Since $\underline{x}\neq \left(\frac{r}{d},\dots ,\frac{r}{d}\right)$ there exists $i$ and $j$ such that $x_i\neq x_j$. Let $x_i+x_j=u$ and
$$\prod_{k\neq i,j}(1-x_k+x_kz)=\sum_{m=0}^{d-2}b_mz^m.$$
Then $f_{d,r}(\underline{x})$ is the coefficient of $z^r$ in the polynomial
$$\left(\sum_{m=0}^{d-2}b_mz^m\right)(1-x_i+zx_i)(1-(u-x_i)+z(u-x_i)).$$
A little computation shows that
$$f_{d,r}(\underline{x})=x_i(u-x_i)(b_{r-2}-2b_{r-1}+b_r)+(rb_{r-1}+(1-r)b_r).$$
If $b_{r-2}-2b_{r-1}+b_r<0$, then we get a strictly smaller value for $f_{d,r}(\underline{x})$ if we replace $(x_i,x_j)$ with $(u/2,u/2)$. If $b_{r-2}-2b_{r-1}+b_r\geq 0$, then we can replace $(x_i,x_j)$ with $(0,u)$ or $(1,u-1)$ depending on $u\in [0,1]$ or $[1,2]$ yielding a boundary point $\underline{y}$ for which $f_{d,r}(\underline{x})\geq f_{d,r}(\underline{y})$. This completes the proof.

\section{Capacity of the polynomial $P_G$}

In this section we prove Theorems~\ref{matching} and \ref{orientation} by computing the capacity of $P_G(\underline{x})=\prod_{(u,v)\in E}(x_u+x_v)$ with respect to various vectors $\underline{\alpha}$.

\begin{Lemma} \label{lemma-matching} Let $G=(A,B,E)$ be a $d$--regular bipartite graph on $2n$ vertices. Let $\underline{\alpha}$ be the vector that takes value $1$ at a vertex $u\in A$, and value $d-1$ at a vertex $v\in B$. Then
$$\capp_{\underline{\alpha}}(P_G) = \frac{d^{nd}}{(d-1)^{n(d-1)}}.$$
\end{Lemma}

\begin{proof} For sake of convenience let us denote the variables by $x_u$ if $u\in A$, and $y_v$ if $v\in B$. Then
$$\capp_{\underline{\alpha}} (P_G)=\inf_{x_u,y_v>0 \atop u\in A, v\in B} \frac{ \prod_{(u,v)\in E(G)}(x_u+y_v)}{\prod_{u\in A}x_u \cdot  \prod_{v\in B}y_v^{d-1}}=\inf_{x_u,y_v>0 \atop u\in A, v\in B}\prod_{(u,v)\in E(G)}\frac{x_u+y_v}{x_u^{1/d}y_v^{(d-1)/d}}.$$
Note that
$$x_u+y_v=\frac{1}{d}(dx_u)+\frac{d-1}{d}\left(\frac{dy_v}{d-1}\right)\geq (dx_u)^{1/d}\left(\frac{dy_v}{d-1}\right)^{(d-1)/d}$$
by weighted arithmetic-geometric mean inequality. In other words,
$$\frac{x_u+y_v}{x_u^{1/d}y_v^{(d-1)/d}}\geq \frac{d}{(d-1)^{(d-1)/d}}.$$
Hence
$$\capp_{\underline{\alpha}} (P_G)\geq \left(\frac{d}{(d-1)^{(d-1)/d}}\right)^{nd}=\frac{d^{nd}}{(d-1)^{n(d-1)}}.$$
Observe that if $x_u=1$ and $y_v=d-1$ for all $u\in A$ and $v\in B$ then this bound is sharp.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{matching}]
As before let  $\underline{\alpha}$ be the vector that takes value $1$ at a vertex $u\in A$, and values $d-1$ at a vertex $v\in B$.
By Theorem~\ref{general} we have
$$\prm(G)\geq  \prod_{v\in A}\binom{d}{1}\bigg(\frac{1}{d}\bigg)^{1}\bigg(\frac{d-1}{d}\bigg)^{d-1}\cdot \prod_{v\in B}\binom{d}{d-1}\bigg(\frac{d-1}{d}\bigg)^{d-1}\bigg(\frac{1}{d}\bigg)^{1}\cdot \mathrm{cap}_{\underline{\alpha}}(P_G).$$
Then by Lemma~\ref{lemma-matching} we have
$$\prm(G)\geq \left(d\bigg(\frac{d-1}{d}\bigg)^{d-1}\right)^{2n}\frac{d^{nd}}{(d-1)^{n(d-1)}}=\bigg( \frac{(d-1)^{d-1}}{d^{d-2}} \bigg)^{n}.$$
\end{proof}

\begin{Lemma} \label{lemma-orientation} Let $\underline{\alpha}=(d_1/2,\dots ,d_n/2)$, where $d_j$ is the degree of the vertex $j$. Then
$\capp_{\underline{\alpha}} (P_G) = 2^{e(G)}$,
where  $e(G)$ is the number of edges.
\end{Lemma}

\begin{proof}
First we will prove that $\capp_{\underline{\alpha}}(P_G) \leq 2^{e(G)}$.
Indeed, if we substitute $\underline{1}$ as $\underline{x}$, then we get
$$\frac{P_G(1,1, \dots 1)}{\prod_{v\in V(G)}1^{d_v/2}}=\prod_{(i,j)\in E(G)}(1+1)=2^{e(G)}.$$
Next we will prove the other direction: $\capp _{\underline{\alpha}}(P_G) \geq 2^{e(G)}$.
Using that $x_i+x_j\geq 2\sqrt{x_ix_j}$ we get that
$$\frac{\prod_{(u,v)\in E}(x_u+x_v)}{\prod_{v\in V(G)}x_v^{d_v/2}} \geq \frac{\prod_{(i,j)\in E(G)} 2\sqrt{x_ix_j}}{\prod_{v\in V(G)}x_v^{d_v/2}}=2^{e(G)}.$$
Thus $\capp_{\underline{\alpha}} (P_G) = 2^{e(G)}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{orientation}]
As before let $\underline{\alpha}=(d_1/2,\dots ,d_n/2)$, where $d_j$ is the degree of the vertex $j$.
By Theorem~\ref{general} we have
$$\e(G)\geq  \prod_{v\in V}\binom{d_v}{d_v/2}\bigg(\frac{d_v/2}{d_v}\bigg)^{d_v/2}\bigg(\frac{d_v/2}{d_v}\bigg)^{d_v/2}\cdot \mathrm{cap}_{\underline{\alpha}}(P_G).$$
Then by Lemma~\ref{lemma-orientation} we have
$$\e(G)\geq \prod_{v\in V}\frac{\binom{d_v}{d_v/2}}{2^{d_v}}\cdot 2^{e(G)}=\prod_{v\in V}\frac{\binom{d_v}{d_v/2}}{2^{d_v/2}}.$$
\end{proof}

\begin{Rem}
For $d$--regular graphs Las Vergnas \cite{Ver1} improved Theorem~\ref{orientation} as follows:
$$\e(G)\geq \frac{2^d}{\binom{d}{d/2}}\left(\frac{\binom{d}{d/2}}{2^{d/2}}\right)^n.$$
(At Proposition 5.3 of \cite{Ver1} there is a typo as it is pointed out in another paper of Las Vergnas  in the footnote of the first page of \cite{Ver2}.) This strengthening can be obtained by our method too: all we have to note that we only need to apply Theorem~\ref{capacity preserving} to $n-1$ variables corresponding to vertices of $P_G(\underline{x})$: at the very end we should get a polynomial of the form $cx_n^{d_n/2}$ since throughout the process we get homogeneous polynomials. For this univariate polynomial there is no need to apply Theorem~\ref{capacity preserving} once more, so we get a $2^d/\binom{d}{d/2}$ improvement. This argument applies to non-regular graphs too thereby saving a factor $2^{\Delta}/\binom{\Delta}{\Delta/2}$, where $\Delta$ is the largest degree.

\end{Rem}

\section{Beyond this paper}

In this section we collected some pointers to the literature.

Stable polynomials have a huge literature.
If someone is interested in a  comprehensive introduction to the this theory, then the paper of Choe, Oxley, Sokal and Wagner \cite{COSW} or Wagner's survey \cite{Wag} might be a good choice. Another excellent survey of the area is the paper of Vishnoi \cite{Vis}.  For capacity preserver operations the paper of  Gurvits and Leake \cite{LeGu} gives a treatment that is both very general and very readable. Statements on capacity often boils down to some statement about coefficients of univariate real-rooted polynomials often with a probabilistic flavour like Hoeffding's theorem \cite{Hoe}. A good source of such inequalities and results is Pitman's survey \cite{Pit}. The coefficient lemma, Theorem~\ref{coefficient theorem}, already appeared in the paper \cite{Gur3}. Interestingly this paper also considers various versions of the polynomial $P_G(\underline{x})=\prod_{(u,v)\in E(G)}(x_u+x_v)$, but never exactly this form. The coefficient lemma could have been easily derived from the work of  Gurvits and Leake \cite{LeGu} too.

There are many different proofs and generalizations of Theorem~\ref{matching}. The original proof of Schrijver \cite{Sch2} is elementary, but involved. The first proof based on stable polynomials and capacity is due to Gurvits \cite{Gur1}, his proof is simplified in the paper of Laurent and Schrijver \cite{LaSc}. Another proof based on the theory of graph covers is given by Csikv\'ari \cite{Csik}. (The relationship between the theory of graph covers and the theory of stable polynomials is not yet well-understood.) Theorem~\ref{matching} has a very natural generalization for permanents of non-negative matrices. This generalization was derived by Gurvits \cite{Gur2} from the original paper of Schrijver \cite{Sch2}. Subsequently, Anari and Oveis-Gharan \cite{A-OG} and Straszak and Vishnoi \cite{StVi} gave a proof that only relies on the theory of stable polynomials. Another possible generalization considers counting matchings of fixed size in bipartite graphs instead of perfect matchings. This question was treated in the papers Csikv\'ari \cite{Csik}, Lelarge \cite{Lela} and Gurvits and Leake \cite{LeGu} (this last one uses only stable polynomials).

Concerning Eulerian orientations, Theorem~\ref{orientation} has many different proofs either. The original proof of Schrijver is very elegant and simple. Las Vergnas \cite{Ver1}  gave another proof building on the theory of Martin's polynomial that gives a slightly stronger result. Borb\'enyi and Csikv\'ari \cite{BoCs} gave a proof using gauge transformation. The proof presented here is the first one using stable polynomials, but we remark that this result could have been easliy deduced from the paper of Straszak and Vishnoi \cite{StVi} too that uses stable polynomials.

Both Theorems~\ref{matching} and \ref{orientation} can be interpreted as a correlation inequality. If we divide by $2^{e(G)}=\prod_{v\in V(G)} 2^{d_v/2}$ in Theorem~\ref{orientation}, then the the right hand side of the inequality
$$\frac{\e(G)}{2^{e(G)}}\geq \prod_{v\in V(G)}\frac{\binom{d_v}{d_v/2}}{2^{d_v}}$$
is the probability that a random orientation is Eulerian, while on the left hand side the term $\frac{\binom{d_v}{d_v/2}}{2^{d_v}}$ is the probability that a random orientation is balanced at vertex $v$. So this inequality can be interpreted as a positive correlation inequality. Similarly, if $G=(A,B,E)$ is a $d$--regular bipartite graph, then we can consider the probability space where for each vertex $u$ in $A$ we pick exactly one of the edges incident to $u$ uniformly at random. This way we picked $n$ edges.  For a vertex $v\in B$ let $E_v$ be the event that we picked exactly one of the edges incident to $v$. Then $\mathbb{P}(\cap_{v\in B}E_v)=\frac{\prm(G)}{d^n}$ while $\mathbb{P}(E_v)=d\cdot \frac{1}{d}\left(1-\frac{1}{d}\right)^{d-1}=\left(\frac{d-1}{d}\right)^{d-1}$. Hence Theorem~\ref{matching} is equivalent with $\mathbb{P}(\cap_{v\in B}E_v)\geq \prod_{v\in B}\mathbb{P}(E_v)$. It seems that many results on capacity are indeed fuelled by positive correlation inequalities, often in a very disguised way. This connection is the most explicit in the paper \cite{StVi} where the authors introduce the iterated positive correlation property and connect it with stable polynomials. Surprisingly it is also possible to build out a theory of negative correlation based on stable polynomials, for details see the paper  \cite{Pem}.

One might wonder whether there is a deeper connection between Theorems~\ref{matching} and \ref{orientation}. It turns out that both theorems fall into a pattern that is about the so-called Bethe approximation. Hans Bethe  was a Nobel-prize laurate physicist. Among many other achievements he introduced the concept that is now known as Bethe--approximation. Originally this was a highly heuristic concept that approximates well quantities coming from counting objects with local constraints like perfect matchings and Eulerian orientations. For a long time it was overlooked by the mathematics community, then Bethe approximation showed up in two different lines of research. In the work of Dembo, Montanari and their coauthors \cite{DeMa,DeMa2,DMS,DMSS} about graph limit theory of sparse graphs, an appropriate version of Bethe approximation played the role of the limit value of certain graph parameters. Another line of research emerged from the work of Gurvits establishing inequalities between a graph parameter and its Bethe approximation. In many cases Bethe approxiation turns out to be a lower bound for the corresponding graph parameter. Theorem~\ref{matching} and \ref{orientation} belong to this line of research. This area almost exclusively relies on stable polynomials \cite{A-OG,StVi} and graph covers \cite{Csik,Ruo,Lela,Von}.
\bigskip

\noindent \textbf{Acknowledgment.} The first author thanks Jonathan Leake for the discussions on the topic of this paper.
The authors are very grateful to the anonymous referee for his/her suggestions that greatly improved the paper.


TITLE: Direct and reverse waves
QUESTION [5 upvotes]: let's consider a generic wave that propagates in space and time, expressed in frequency domain:
$$V(x)=A\cdot e^{-kx} + B\cdot e^{kx}$$
It may represent the voltage along a transmission line, or any physical quantity that appears in a second order differential equation that satisfies the oscillation conditions.
In time - domain it becomes something like that:
$$V(x)=A\cdot cos(-kx+\omega t) + B\cdot cos(kx+\omega t)$$
The first term is usually called direct or incident wave, while the second one is called reverse or reflected wave. They are two waves that moves in space and time, and precisely the first one moves towards x axis, while the second one moves in the opposite direction to the x axis.
My question is about this last statement: why are the term with "-kx" the direct wave and the term  with "kx" the reverse wave?
I tried to answer my question by using the concept of phase velocity. The phase velocity of a wave is defined as the velocity an observer should have in order not to see any difference of phase, i.e. such that:
$$d\cdot (-kx+\omega t) = 0$$ for the first term;
$$d\cdot (kx+\omega t) = 0$$ for the second term;
So we get:
$$-kdx + \omega dt = 0$$ for the first term;
$$kdx + \omega dt = 0$$ for the second term;
and finally:
$$v_{1} = dx/dt = \omega/k$$ for the first term;
$$v_{2} = dx/dt = - \omega/k$$ for the second term;
So the phase velocity of the first term is positive (so, towards x axis), while that of the second term is negative (so, opposite to x axis).
What does not convince me of this explanation is the fact that as far as I know the phase velocity does not represent the propagation velocity of the wavefront, but is simply the velocity corresponding to a zero phase difference. And thanks to the fact that it is not a propagation speed, it follows that it can be even greater than the speed of light (it is a known result of the analysis of waveguides, for instance).

REPLY [0 votes]: I think your concern is "because the negative sign applies to the spatial bit within the cosine and not to the time part, then how can it be that such becomes a time reversal (i.e. backward propagation)?"
This is simple. Note that $\cos$ is an even function.
$$\begin{align}
u_\mathrm{dir}(x, t) &:= A \cos(-kx + \omega t)\\
&= A \cos(-[-kx + \omega t])\\
&= A \cos(kx - \omega t)\end{align}$$
Thus, it is quite evident now that the "reflected wave"
$$u_\mathrm{ref}(x, t) := A \cos(kx + \omega t)$$
is the time reversal of the "direct wave", i.e.
$$u_\mathrm{ref}(x, t) = u_\mathrm{dir}(x, -t)$$
(ignoring the amplitude difference).
viz. it is travelling the other way. As for why we call the negative one reverse instead of calling the positive one - it is because there is a tendency to imagine the wave travelling toward the right. The term with negative $kx$ (or negative $\omega t$) term travels to the right.


TITLE: Hausdorff open image of a Polish space
QUESTION [9 upvotes]: Let $f\colon X\to Y$ a continuous open and surjective function, where   $X$ is Polish.
It is known that $Y$ is Polish if: $f$ is closed or $Y$ is metric.
Suppose that we know that $Y$ is Hausdorff, does it implies that $Y$ is Polish? or Regular?
I think no, but i have not been able to find a counterexample.

REPLY [4 votes]: As a counterexample one can consider the projective space $P\mathbb R^\omega$ of the countable product of lines. This is a quotient space of the Polish space $\mathbb R^\omega_\circ=\mathbb R^\omega\setminus\{0\}^\omega$ by the equivalence relation $x\sim y$ iff $\mathbb Rx=\mathbb Ry$.
It is easy to see that the quotient map $q:\mathbb R^\omega_\circ\to P\mathbb R^\omega$ is open and the space $P\mathbb R^\omega$ is Hausdorff but not Urysohn and hence is not metrizable and not Polish.
Moreover, the space $P\mathbb R^\omega$ is superconnected in the sense that for any nonempty open sets $U_1,\dots,U_n$ in $P\mathbb R^\omega$ the intersection of thier closures $\bar U_1\cap\dots\cap\bar U_n$ is not empty.


text:
\section{Limitations and future work}
\label{sec:limitations}
\input{figures/convergence}

There are two aspects of this work that we would like to understand better. The first is the role of the weight clipping threshold $\sigma^*$ (see Algorithm \ref{alg:madam}). Figure \ref{fig:loss_compare} shows a comparison between an SGD baseline and Madam with different weight clipping thresholds. As can be seen, a reduced clipping threshold seems to both \textit{stabilise} and \textit{regularise} the test loss. The stabilising role of weight clipping may be understood as follows: at the end of training, a learning algorithm can overfit the training set by simply scaling up the learnt weights (amplifying confidence on its current predictions). Since Madam can increase the weights \textit{exponentially} (via compound growth over a number of iterations), this effect is particularly unstable and motivates explicit weight clipping. Still, needing to tune this clipping threshold is undesirable, and it would be better if there were a way to avoid it.

The second is the slight deterioration of Madam compared to Adam and SGD in Table \ref{tab:madam-results}. It is not immediately clear where this deterioration comes from. One possibility is that, since Madam freezes the sign pattern of weights from initialisation, the network is not expressive enough to represent the very best solutions. A workaround to this potential problem could involve finding a better way to initialise the sign pattern of the weights at the start of training. More generally, it is possible that we are missing some key idea that would close this performance gap.

config: arxiv


TITLE: Proving that an inequality holds
QUESTION [0 upvotes]: A while ago, the following question was posted by the OP, who requested for help in proving the following inequality:
Let $a,b,c,d$ be positive reals such that $a+b+c+d=1$. Prove that:
$$\frac{a^3}{b+c}+\frac{b^3}{c+d}+\frac{c^3}{a+d}+\frac{d^3}{a+b} \ge \frac{1}{8}.$$
This was the original problem as stated by the OP.
I have added the extra condition that $a,b,c,d$ must all be positive reals, since the given inequality by itself would not hold otherwise, as another user has pointed out in the comments. Since the original post has been closed (in all fairness to the OP, the condition of positive reals could be implied, especially if this was a competition math problem), I decided to open a new post in order to provide a possible solution for the OP, as well as inquire if there are other possible means to prove this inequality. My solution involves AM-GM, so it would be nice to see other methods that work as well.

REPLY [2 votes]: Also, by C-S and AM-GM we obtain:
$$\sum_{cyc}\frac{a^3}{b+c}=\sum_{cyc}\frac{a^4}{ab+ac}\geq\frac{(a^2+b^2+c^2+d^2)^2}{\sum\limits_{cyc}(ab+ac)}=$$
$$=\frac{(a^2+b^2+c^2+d^2)^2}{(a+c)(b+d)+2(ac+bd)}\geq\frac{(a^2+b^2+c^2+d^2)^2}{\left(\frac{a+c+b+d}{2}\right)^2+a^2+c^2+b^2+d^2}=$$
$$=\frac{(a^2+b^2+c^2+d^2)^2}{\frac{1}{4}+a^2+c^2+b^2+d^2}.$$
Id est, it's enough to prove that:
$$\frac{(a^2+b^2+c^2+d^2)^2}{\frac{1}{4}+a^2+c^2+b^2+d^2}\geq\frac{1}{8}$$ or
$$32(a^2+b^2+c^2+d^2)^2-4(a^2+b^2+c^2+d^2)-1\geq0$$ or
$$(4(a^2+b^2+c^2+d^2)-1)(8(a^2+b^2+c^2+d^2)+1)\geq0$$ or
$$4(a^2+b^2+c^2+d^2)\geq1,$$ which is true by C-S:
$$4(a^2+b^2+c^2+d^2)=\sum_{cyc}1^2\sum_{cyc}a^2\geq(a+b+c+d)^2=1.$$


TITLE: Is there an elegant way to prove a function is linear?
QUESTION [22 upvotes]: I'm reading Hoffman and Kunze's linear algebra book and on page 73 in the exercise 7, they ask to verify this function

$$T(x_1,x_2,x_3)=(x_1-x_2+2x_3,2x_1+x_2,-x_1-2x_2+2x_3)$$
  is a linear transformation.

This exercise is really simple, but a little bit tedious. We have to define arbitrary $u=(x_u,y_u,z_u)$ and $v=(x_v,y_v,z_v)$ elements of $F^3$ and show $T(u+v)=T(u)+T(v)$ and $T(ku)=kT(u)$ for $k\in F$. (we can see $F$ as $\mathbb R$ or $\mathbb C$)
Is there a way more elegant to prove this function is linear?

REPLY [1 votes]: The lazyman's solution: every expression in the given is a linear combination. Linear combinations are well-known to be linear.


TITLE: How do I find this Expectation?
QUESTION [2 upvotes]: I have an expectation given as:
$\mathbb{E}\left(S_{T}\mathbb{1}_{S_{T}\geq K} \right)$
where $K$ is just an arbitrary number (i.e. the strike price, but that's unimportant) and $S$ can be modelled by the equation $S_{t} = \exp((r-\frac{1}{2})t + \sigma W_{t})$. Also, the expectation is under the $\mathbb{P}$-measure, not the $\mathbb{Q}$-measure, so effectively this expectation is $\mathbb{E}^{\mathbb{P}}\left(S_{T}\mathbb{1}_{S_{T}\geq K} \right)$
Now, when trying to evaluate $\mathbb{E}\left(\mathbb{1}_{S_{T}\geq K} \right)$ under the $\mathbb{Q}$-measure, then solving this expectation is fairly easy, since you can integrate the SDE and take the $\log$ of $S$ to get $\log(S_{T}) = \log(S_{0}) + (r-\frac{1}{2})T + \sigma\sqrt{T}N(0,1)$ (since $W_{t}\approx \sqrt{T}N(0,1)$) and thus we have for $\mathbb{E}\left(\mathbb{1}_{S_{T}\geq K} \right) = \mathbb{P}({S_{T}\geq K})$:
$\log(S_{T}) = (r-\frac{1}{2})T + \sigma\sqrt{T}N(0,1) > \log(K)$ and thus rearranging this equation gives
$N(0,1) > \frac{\log(K/S_{0}) - (r-\frac{1}{2}\sigma^{2})T}{\sigma\sqrt{T}}$
and through a little bit more rearrangement (i.e. knowing that $N(0,1)<-x = 1 - N(x)$ we get finally $d_{2} = \frac{(r-\frac{1}{2}\sigma^{2})T + \log(S_{0}/K)}{\sigma\sqrt{T}}$ and thus $\mathbb{E}\left(\mathbb{1}_{S_{T}\geq K} \right) = N(d_{2})$.
The problem I have now however is that I'm a bit unsure how to find  $\mathbb{E}\left(S_{T}\mathbb{1}_{S_{T}\geq K} \right)$, I honestly don't really know how to calculate it, so if someone could help me out I'd really appreciate it. Thanks in advance.

REPLY [1 votes]: You could take a look at the derivation of the Black-Scholes formula, in which a central part is computing the above expectation. Take a look here: Proof of the Black - Scholes pricing formula for European Call Option.
If you define $Z=\log S_T$ then $Z$ is a certain normally-distributed random variable (check yourself) with density $f(z)$, and you can then compute
$\mathbb{E}\left(S_{T}\mathbb{1}_{S_{T}\geq K} \right)
=
\mathbb{E}\left(\exp(Z)\mathbb{1}_{Z\geq \log K} \right)
=
\int_{\log K}^\infty \, e^z \, f(z) \, \, \mathrm{d}z,
$
which is done in a more general set-up in one of the answers in the above link. You should end up with (here $\Phi$ denotes the distribution function of a $\mathcal{N}(0,1)$-variable):
$\Phi\left(\frac{\log\frac{S_0}{K}+\left(r+\frac{\sigma^2}{2}\right)T}{\sigma\sqrt{T}}\right)$.


text:
\begin{document}
\title[Sampling Theorems for Sturm Liouville Problem]{Sampling Theorems for
Sturm Liouville Problem with Moving Discontinuity Points}
\author{Fatma H\i ra}
\address[F. H\i ra \ and N. Alt\i n\i \c{s}\i k]{The University of Ondokuz
May\i s, Science and Arts Faculty, Department of Mathematics,Samsun, Turkey\\
}
\email[Corresponding author: F. H\i ra]{fatma.hira@omu.edu.tr}
\urladdr{}
\thanks{}
\author{Nihat Alt\i n\i \c{s}\i k}
\curraddr{ }
\email[N.~Alt\i n\i \c{s}\i k]{anihat@omu.edu.tr}
\address{ }
\subjclass[2000]{ 34B24, 34B27; 94A20}
\keywords{Symmetric and Moving Discontinuities; Discontinuous
Sturm-Liouville Problem; Green's Function; Sampling Theory}

\begin{abstract}
In this paper, we investigate the sampling analysis for a new
Sturm-Liouville problem with symmetrically located discontinuities which are
defined to depending on a neighborhood of a midpoint of the interval. Also
the problem has transmission conditions at these points of discontinuity and
includes an eigenparameter in a boundary condition. We establish briefly the
needed relations for the derivations of the sampling theorems and construct
Green's function for the problem. Then we derive sampling representations
for transforms whose kernels are either solutions or Green's functions.
\end{abstract}

\maketitle

\section{Introduction}

Throughout this study we consider Sturm Liouville problem:
\begin{equation}
\tau \left( u\right) :=-u^{\shortparallel }\left( x\right) +q\left( x\right)
u\left( x\right) =\lambda u\left( x\right) ,~~\ \ \ \ x\in I,  \tag{1.1}
\label{1.1}
\end{equation}
with an eigenparameter dependent on a boundary condition;
\begin{equation}
B_{a}\left( u\right) :=\beta _{1}u\left( a\right) +\beta _{2}u^{\prime
}\left( a\right) =0,  \tag{1.2}  \label{1.2}
\end{equation}
\begin{equation}
B_{b}\left( u\right) :=\lambda \left( \alpha _{1}^{\prime }u\left( b\right)
-\alpha _{2}^{\prime }u^{\prime }\left( b\right) \right) +\left( \alpha
_{1}u\left( b\right) -\alpha _{2}u^{\prime }\left( b\right) \right) =0,
\tag{1.3}  \label{1.3}
\end{equation}
and transmission conditions at two points of discontinuity depending on a
neighborhood of $\ \theta ,$ that are $\theta _{-\varepsilon }$ and $\theta
_{+\varepsilon }$;
\begin{equation}
T_{-\varepsilon }\left( u\right) :=u\left( \theta _{-\varepsilon }-\right)
-\delta u\left( \theta _{-\varepsilon }+\right) =0,  \tag{1.4}  \label{1.4}
\end{equation}
\begin{equation}
T_{-\varepsilon }^{\prime }\left( u\right) :=u^{\prime }\left( \theta
_{-\varepsilon }-\right) -\delta u^{\prime }\left( \theta _{-\varepsilon
}+\right) =0,  \tag{1.5}  \label{1.5}
\end{equation}
\begin{equation}
T_{+\varepsilon }\left( u\right) :=\delta u\left( \theta _{+\varepsilon
}-\right) -\gamma u\left( \theta _{+\varepsilon }+\right) =0,  \tag{1.6}
\label{1.6}
\end{equation}
\begin{equation}
T_{+\varepsilon }^{\prime }\left( u\right) :=\delta u^{\prime }\left( \theta
_{+\varepsilon }-\right) -\gamma u^{\prime }\left( \theta _{+\varepsilon
}+\right) =0,  \tag{1.7}  \label{1.7}
\end{equation}
where $I=\left[ a,\theta _{-\varepsilon }\right) \cup \left( \theta
_{-\varepsilon },\theta _{+\varepsilon }\right) \cup \left( \theta
_{+\varepsilon },b\right] ;$ $\lambda $ is a complex spectral parameter, $
q\left( x\right) $ is a given real valued function which is continuous in $
\left[ a,\theta _{-\varepsilon }\right) ,~\left( \theta _{-\varepsilon
},\theta _{+\varepsilon }\right) ,~$and $\left( \theta _{+\varepsilon },b
\right] $ and has a finite limit $q\left( \theta _{-\varepsilon }\pm \right)
$ and $q\left( \theta _{+\varepsilon }\pm \right) $; $\beta _{i},\alpha
_{i},\alpha _{i}^{\prime },\delta ,\gamma \in

\mathbb{R}

$ $\left( i=1,2\right) $; $\left\vert \beta _{1}\right\vert +\left\vert
\beta _{2}\right\vert \neq 0,$ $\delta \neq 0,$ $\gamma \neq 0;$ $\theta
:=\left( a+b\right) /2,$ $\theta _{\pm \varepsilon }\pm :=\left( \theta \pm
\varepsilon \right) \pm 0,$ $0<\varepsilon <\left( b-a\right) /2$ and
\begin{equation}
\rho :=\left( \alpha _{1}^{\prime }\alpha _{2}-\alpha _{1}\alpha
_{2}^{\prime }\right) >0.  \tag{1.8}  \label{1.8}
\end{equation}

In the literature, the Whittaker-Kotel'nikov-Shannon (WKS) sampling theorem
and generalization of the WKS sampling theorem (see$\left[ 1-3\right] )$ has
been investigated extensively (see $\left[ 4-8\right] ).$ Sampling theorems
associated with Sturm-Liouville problems were investigated in $\left[ 9-13
\right] .$ Also, $\left[ 14-17\right] $ and $\left[ 18-21\right] $ are the
examples works in direction of sampling analysis associated with continuous
and discontinuous eigenproblems, respectively. In $\left[ 20\right] $ the
author investigated the sampling analysis associated with discontinuous
Sturm Liouville problems which has transmission conditions at the point of
discontinuity and contains an eigenparameter in two boundary canditions. In
the present study, we introduce a new Sturm Liouville problem which has
symmetrically located discontinuities which are defined to depending on a
neighborhood of a midpoint of the interval. $\varepsilon $ is a parameter
controling the change of neighborhood process (it can be called tuning
parameter) and by using the change of this $\varepsilon $ parameter it's
possible to determine points of discontinuity. That is, two points of
discontinuity can be determined in interval $\left[ a,b\right] $ for each $
\varepsilon $ value in interval $0<\varepsilon <\left( b-a\right) /2.$ This
is the difference between the problem $\left( 1.1\right) -\left( 1.7\right) $
and Sturm Liouville eigenvalue problem studied extensively in the literature
(see $\left[ 22-28\right] ).$ The main result is that points of
discontinuity can be determined and moved by changing $\varepsilon $
parameter. A similar problem in more detail was presented in $\left[ 28
\right] .$ This study is the first to investigate that sampling analysis
associated with eigenproblems with moving discontinuity points . To derive
sampling theorems for the problem $\left( 1.1\right) -\left( 1.7\right) ,$
we establish briefly the spectral properties and construct Green's function
of the problem $\left( 1.1\right) -\left( 1.7\right) $. Then we derive two
sampling theorems using solutions and Green's function, respectively.

\section{An Operator Formulation and Asymptotic Formulas}

To formulate a theoretic approach to the problem (1.1)-(1.7) we define the
Hilbert space $H=L_{2}\left( a,b\right) \oplus

\mathbb{C}

$ with an inner product
\begin{equation}
\left\langle \text{f}\left( .\right) ,\text{g}\left( .\right) \right\rangle
_{H}:=\underset{a}{\overset{\theta _{-\varepsilon }}{\int }}f\left( x\right)
\overline{g}\left( x\right) dx+\delta ^{2}\underset{\theta _{-\varepsilon }}{
\overset{\theta _{+\varepsilon }}{\int }}f\left( x\right) \overline{g}\left(
x\right) dx+\gamma ^{2}\underset{\theta _{+\varepsilon }}{\overset{b}{\int }}
f\left( x\right) \overline{g}\left( x\right) dx+\frac{\gamma ^{2}}{\rho }h
\overline{k},  \tag{2.1}  \label{2.1}
\end{equation}
where f$\left( x\right) =\left(
\begin{array}{c}
f\left( x\right) \\
h
\end{array}
\right) ,$ g$\left( x\right) =\left(
\begin{array}{c}
g\left( x\right) \\
k
\end{array}
\right) \in H,$ $f\left( .\right) ,g\left( .\right) \in L_{2}\left(
a,b\right) ,$ $h,k\in

\mathbb{C}

.$ For convenience we put
\begin{equation}
R\left( u\right) :=\alpha _{1}u\left( b\right) -\alpha _{2}u^{\prime }\left(
b\right) ,\text{ \ \ }R^{\prime }\left( u\right) :=\alpha _{1}^{\prime
}u\left( b\right) -\alpha _{2}^{\prime }u^{\prime }\left( b\right) .
\tag{2.2}  \label{2.2}
\end{equation}

Let $D\left( A\right) \subseteq H$ be the set of all f$\left( x\right)
=\left(
\begin{array}{c}
f\left( x\right) \\
h
\end{array}
\right) \in H$ such that $f$ and $f^{\prime }$ are absolutely continuous on $
\left[ a,b\right] $ and $\tau \left( f\right) \in L_{2}\left( a,b\right) ,$ $
h=R^{\prime }\left( f\right) ,$ $B_{a}\left( f\right) =0,$ $T_{\pm
\varepsilon }\left( f\right) =T_{\pm \varepsilon }^{\prime }\left( f\right)
=0.$ Define the operator $A:D\left( A\right) \rightarrow H$ by
\begin{equation}
A\left(
\begin{array}{c}
f\left( x\right) \\
R^{\prime }\left( f\right)
\end{array}
\right) =\left(
\begin{array}{c}
\tau \left( f\right) \\
-R\left( f\right)
\end{array}
\right) ,\text{ \ \ }\left(
\begin{array}{c}
f\left( x\right) \\
R^{\prime }\left( f\right)
\end{array}
\right) \in D\left( A\right) .  \tag{2.3}  \label{2.3}
\end{equation}

The operator $A:D\left( A\right) \rightarrow H$ is equivalent to the
eigenvalue problem (1.1)-(1.7) in the sense that the eigenvalues of $A$ are
exactly those of the problem (1.1)-(1.7).

We can prove in a manner similar to that of $\left[ 23,25,26,28\right] $
that $A$ is symmetric in $H,$ all eigenvalues of the problem are real.

Let $\phi _{\lambda }\left( .\right) $ and $\chi _{\lambda }\left( .\right) $
be two solutions of (1.1) as
\begin{equation}
\phi _{\lambda }\left( x\right) =\left\{
\begin{array}{l}
\phi _{-\varepsilon ,\lambda }\left( x\right) ,\text{ \ \ }x\in \left[
a,\theta _{-\varepsilon }\right) , \\
\phi _{\varepsilon ,\lambda }\left( x\right) ,\text{ \ }x\in \left( \theta
_{-\varepsilon },\theta _{+\varepsilon }\right) , \\
\phi _{+\varepsilon ,\lambda }\left( x\right) ,\text{ \ \ }x\in \left(
\theta _{+\varepsilon },b\right] ,
\end{array}
\right. \text{ \ \ \ }\chi _{\lambda }\left( x\right) =\left\{
\begin{array}{l}
\chi _{-\varepsilon ,\lambda }\left( x\right) ,\text{ \ \ }x\in \left[
a,\theta _{-\varepsilon }\right) , \\
\chi _{\varepsilon ,\lambda }\left( x\right) ,\text{ \ }x\in \left( \theta
_{-\varepsilon },\theta _{+\varepsilon }\right) , \\
\chi _{+\varepsilon ,\lambda }\left( x\right) ,\text{ \ \ }x\in \left(
\theta _{+\varepsilon },b\right] ,
\end{array}
\right.  \tag{2.4}  \label{2.4}
\end{equation}
satisfying the following conditions, respectively;
\begin{equation}
\phi _{-\varepsilon ,\lambda }\left( a\right) =\beta _{2},\text{\ \ \ \ \ }
\phi _{-\varepsilon ,\lambda }^{\prime }\left( a\right) =-\beta _{1},
\tag{2.5}  \label{2.5}
\end{equation}
\begin{equation}
\phi _{\varepsilon ,\lambda }\left( \theta _{-\varepsilon }\right) =\delta
^{-1}\phi _{-\varepsilon ,\lambda }\left( \theta _{-\varepsilon }-\right) ,
\text{ \ \ \ \ \ }\phi _{\varepsilon ,\lambda }^{\prime }\left( \theta
_{-\varepsilon }\right) =\delta ^{-1}\phi _{-\varepsilon ,\lambda }^{\prime
}\left( \theta _{-\varepsilon }-\right) ,  \tag{2.6}  \label{2.6}
\end{equation}
\begin{equation}
\phi _{+\varepsilon ,\lambda }\left( \theta _{+\varepsilon }\right) =\delta
\gamma ^{-1}\phi _{\varepsilon ,\lambda }\left( \theta _{+\varepsilon
}-\right) ,\text{ \ \ \ \ }\phi _{+\varepsilon ,\lambda }^{\prime }\left(
\theta _{+\varepsilon }\right) =\delta \gamma ^{-1}\phi _{\varepsilon
,\lambda }^{\prime }\left( \theta _{+\varepsilon }-\right) ,  \tag{2.7}
\label{2.7}
\end{equation}
and
\begin{equation}
\chi _{+\varepsilon ,\lambda }\left( b\right) =\lambda \alpha _{2}^{\prime
}+\alpha _{2},\text{ \ \ \ \ }\chi _{+\varepsilon ,\lambda }^{\prime }\left(
b\right) =\lambda \alpha _{1}^{\prime }+\alpha _{1}\text{,}  \tag{2.8}
\label{2.8}
\end{equation}
\begin{equation}
\chi _{\varepsilon ,\lambda }\left( \theta _{+\varepsilon }\right) =\gamma
\delta ^{-1}\chi _{+\varepsilon ,\lambda }\left( \theta _{+\varepsilon
}+\right) ,\text{ \ \ \ }\chi _{\varepsilon ,\lambda }^{\prime }\left(
\theta _{+\varepsilon }\right) =\gamma \delta ^{-1}\chi _{+\varepsilon
,\lambda }^{\prime }\left( \theta _{+\varepsilon }+\right) ,  \tag{2.9}
\label{2.9}
\end{equation}
\begin{equation}
\chi _{-\varepsilon ,\lambda }\left( \theta _{-\varepsilon }\right) =\delta
\chi _{\varepsilon ,\lambda }\left( \theta _{-\varepsilon }+\right) ,\text{
\ \ \ }\chi _{-\varepsilon ,\lambda }^{\prime }\left( \theta _{-\varepsilon
}\right) =\delta \chi _{\varepsilon ,\lambda }^{\prime }\left( \theta
_{-\varepsilon }+\right) .  \tag{2.10}  \label{2.10}
\end{equation}
These functions are entire in $\lambda $ for all $x\in \left[ a,b\right] .$

Let $W\left( \phi _{\lambda },\chi _{\lambda };x\right) $ be the Wronskian
of $\phi _{\lambda }$ and $\chi _{\lambda }$ which is independent of $x,$
since the coefficient of $y^{\prime }$ in the equation $\left( 1.1\right) $
is zero. Let \ \
\begin{eqnarray}
\omega \left( \lambda \right) &:&=\text{ \ }W\left( \phi _{\lambda },\chi
_{\lambda };x\right) =\phi _{\lambda }\left( x\right) \chi _{\lambda
}^{\prime }\left( x\right) -\phi _{\lambda }^{\prime }\left( x\right) \chi
_{\lambda }\left( x\right) \text{ \ }  \notag \\
\text{ \ \ \ \ \ \ } &=&\omega _{-\varepsilon }\left( \lambda \right)
=\delta ^{2}\omega _{\varepsilon }\left( \lambda \right) =\gamma ^{2}\omega
_{+\varepsilon }\left( \lambda \right) .\text{ \ }  \TCItag{2.11}
\label{2.11}
\end{eqnarray}

Then $\omega \left( \lambda \right) $ is an entire function of $\lambda $
whose zeros are precisely the eigenvalues of the operator $A.$ Using
techniques similar of those established by Titchmarsh in $\left[ 22\right] ,$
see also $\left[ 25,26,28\right] $ the zeros of $\omega \left( \lambda
\right) $ are real and simple and if $\lambda _{n},n=0,1,2,...$ denote the
zeros of $\omega \left( \lambda \right) ,$ then the two component vectors
\begin{equation}
\Phi _{n}\left( x\right) :=\left(
\begin{array}{c}
\phi _{\lambda _{n}}\left( x\right) \\
R^{\prime }\left( \phi _{\lambda _{n}}\right)
\end{array}
\right)  \tag{2.12}  \label{2.12}
\end{equation}
are the corresponding eigenvectors of the operator $A$ satisfying the
orthogonality relation
\begin{equation}
\left\langle \Phi _{n}\left( .\right) ,\Phi _{m}\left( .\right)
\right\rangle _{H}=0,\text{ for }n\neq m.  \tag{2.13}  \label{2.13}
\end{equation}

Here $\left\{ \phi _{\lambda _{n}}\left( .\right) \right\} _{n=0}^{\infty }$
will be the sequence of eigenfunctions of the problem (1.1)-(1.7)
corresponding to the eigenvalues $\left\{ \lambda _{n}\right\}
_{n=0}^{\infty }$ . We denote by
\begin{equation}
\Psi _{n}\left( x\right) :=\frac{\Phi _{n}\left( x\right) }{\left\Vert \Phi
_{n}\left( .\right) \right\Vert _{H}}=\left(
\begin{array}{c}
\Psi _{n}\left( x\right) \\
R^{\prime }\left( \Psi _{n}\right)
\end{array}
\right) .  \tag{2.14}  \label{2.14}
\end{equation}

Let $k_{n}\neq 0$ be the real constants for which
\begin{equation}
\chi _{\lambda _{n}}\left( x\right) =k_{n}\phi _{\lambda _{n}}\left(
x\right) ,\text{ \ \ \ }x\in I,\text{ }n=0,1,2,....  \tag{2.15}  \label{2.15}
\end{equation}

The asymptotics of the eigenvalues and eigenfunctions can be derived similar
to the classical techniques of $\left[ 23,25,26,28\right] .$ We state the
results briefly.

$\phi _{\lambda }\left( .\right) $ is the solution determined by equations
(2.5)-(2.7) above then the following integral equations hold for $k=0$ and $
k=1:$
\begin{eqnarray}
\dfrac{d^{k}}{dx^{k}}\phi _{-\varepsilon ,\lambda }\left( x\right) &=&\beta
_{2}\dfrac{d^{k}}{dx^{k}}\left( \cos \sqrt{\lambda }\left( x-a\right)
\right) -\frac{\beta _{1}}{\sqrt{\lambda }}\dfrac{d^{k}}{dx^{k}}(\sin \sqrt{
\lambda }\left( x-a\right) +  \notag \\
&&\frac{1}{\sqrt{\lambda }}\underset{a}{\overset{x}{\int }}\dfrac{d^{k}}{
dx^{k}}\left( \sin \sqrt{\lambda }\left( x-y\right) \right) q\left( y\right)
\phi _{-\epsilon ,\lambda }\left( y\right) dy,  \TCItag{2.16}  \label{2.16}
\end{eqnarray}
\begin{eqnarray}
\dfrac{d^{k}}{dx^{k}}\phi _{\varepsilon ,\lambda }\left( x\right) &=&\delta
^{-1}\phi _{-\epsilon ,\lambda }\left( \theta _{-\epsilon }-\right) \dfrac{
d^{k}}{dx^{k}}\left( \cos \sqrt{\lambda }\left( x-\theta _{-\epsilon
}\right) \right) -  \notag \\
&&\frac{\delta ^{-1}}{\sqrt{\lambda }}\phi _{-\epsilon ,\lambda }^{\prime
}\left( \theta _{-\epsilon }-\right) \dfrac{d^{k}}{dx^{k}}(\sin \sqrt{
\lambda }\left( x-\theta _{-\epsilon }\right) +  \notag \\
&&\frac{1}{\sqrt{\lambda }}\underset{\theta _{-\varepsilon }}{\overset{x}{
\int }}\dfrac{d^{k}}{dx^{k}}\left( \sin \sqrt{\lambda }\left( x-y\right)
\right) q\left( y\right) \phi _{\epsilon ,\lambda }\left( y\right) dy,
\TCItag{2.17}  \label{2.17}
\end{eqnarray}
\begin{eqnarray}
\dfrac{d^{k}}{dx^{k}}\phi _{+\varepsilon ,\lambda }\left( x\right) &=&\delta
\gamma ^{-1}\phi _{\varepsilon ,\lambda }\left( \theta _{+\varepsilon
}-\right) \dfrac{d^{k}}{dx^{k}}\left( \cos \sqrt{\lambda }\left( x-\theta
_{+\epsilon }\right) \right) -  \notag \\
&&\frac{\delta \gamma ^{-1}}{\sqrt{\lambda }}\phi _{\varepsilon ,\lambda
}^{\prime }\left( \theta _{+\varepsilon }-\right) \dfrac{d^{k}}{dx^{k}}(\sin
\sqrt{\lambda }\left( x-\theta _{+\epsilon }\right) +  \notag \\
&&\frac{1}{\sqrt{\lambda }}\underset{\theta _{+\varepsilon }}{\overset{x}{
\int }}\dfrac{d^{k}}{dx^{k}}\left( \sin \sqrt{\lambda }\left( x-y\right)
\right) q\left( y\right) \phi _{+\varepsilon ,\lambda }\left( y\right) dy,
\TCItag{2.18}  \label{2.18}
\end{eqnarray}
sufficiently large $\lambda $ and $\phi _{\lambda }\left( .\right) $ have
the following asymptotic representations for $\left\vert \lambda \right\vert
\rightarrow \infty ,$ which hold uniformly for $x\in I$:
\begin{equation}
\dfrac{d^{k}}{dx^{k}}\phi _{-\varepsilon ,\lambda }\left( x\right) =\beta
_{2}\dfrac{d^{k}}{dx^{k}}\left( \cos \sqrt{\lambda }\left( x-a\right)
\right) +O\left( \left( \sqrt{\lambda }\right) ^{k-1}e^{\left\vert
t\right\vert \left( x-a\right) }\right) ,  \tag{2.19}  \label{2.19}
\end{equation}
\begin{equation}
\dfrac{d^{k}}{dx^{k}}\phi _{\varepsilon ,\lambda }\left( x\right) =\beta
_{2}\delta ^{-1}\dfrac{d^{k}}{dx^{k}}\left( \cos \sqrt{\lambda }\left(
x-a\right) \right) +O\left( \left( \sqrt{\lambda }\right)
^{k-1}e^{\left\vert t\right\vert \left( x-a\right) }\right) ,  \tag{2.20}
\label{2.20}
\end{equation}
\begin{equation}
\dfrac{d^{k}}{dx^{k}}\phi _{+\varepsilon ,\lambda }\left( x\right) =\beta
_{2}\gamma ^{-1}\dfrac{d^{k}}{dx^{k}}\left( \cos \sqrt{\lambda }\left(
x-a\right) \right) +O\left( \left( \sqrt{\lambda }\right)
^{k-1}e^{\left\vert t\right\vert \left( x-a\right) }\right) ,  \tag{2.21}
\label{2.21}
\end{equation}
if $\beta _{2}\neq 0,$
\begin{equation}
\dfrac{d^{k}}{dx^{k}}\phi _{-\varepsilon ,\lambda }\left( x\right) =-\frac{
\beta _{1}}{\sqrt{\lambda }}\dfrac{d^{k}}{dx^{k}}\left( \sin \sqrt{\lambda }
\left( x-a\right) \right) +O\left( \left( \sqrt{\lambda }\right)
^{k-2}e^{\left\vert t\right\vert \left( x-a\right) }\right) ,  \tag{2.22}
\label{2.22}
\end{equation}
\begin{equation}
\dfrac{d^{k}}{dx^{k}}\phi _{\varepsilon ,\lambda }\left( x\right) =-\frac{
\beta _{1}\delta ^{-1}}{\sqrt{\lambda }}\dfrac{d^{k}}{dx^{k}}\left( \sin
\sqrt{\lambda }\left( x-a\right) \right) +O\left( \left( \sqrt{\lambda }
\right) ^{k-2}e^{\left\vert t\right\vert \left( x-a\right) }\right) ,
\tag{2.23}  \label{2.23}
\end{equation}
\begin{equation}
\dfrac{d^{k}}{dx^{k}}\phi _{+\varepsilon ,\lambda }\left( x\right) =-\frac{
\beta _{1}\gamma ^{-1}}{\sqrt{\lambda }}\dfrac{d^{k}}{dx^{k}}\left( \sin
\sqrt{\lambda }\left( x-a\right) \right) +O\left( \left( \sqrt{\lambda }
\right) ^{k-2}e^{\left\vert t\right\vert \left( x-a\right) }\right) ,
\tag{2.24}  \label{2.24}
\end{equation}
if $\beta _{2}=0.$

Then we obtain four distinct cases for the asymptotic behaviour of $\omega
\left( \lambda \right) $ as $\left\vert \lambda \right\vert \rightarrow
\infty ,$ namely;
\begin{equation}
\omega \left( \lambda \right) =\left\{
\begin{array}{l}
\lambda \sqrt{\lambda }\alpha _{1}^{\prime }\beta _{2}\gamma \sin \sqrt{
\lambda }\left( b-a\right) +O\left( \lambda e^{\left\vert t\right\vert
\left( b-a\right) }\right) ,\text{ \ \ if }\beta _{2}\neq 0,\alpha
_{1}^{\prime }\neq 0, \\
\\
\lambda \alpha _{2}^{\prime }\beta _{2}\gamma \cos \sqrt{\lambda }\left(
b-a\right) +O\left( \sqrt{\lambda }e^{\left\vert t\right\vert \left(
b-a\right) }\right) ,\text{ \ \ \ if }\beta _{2}\neq 0,\alpha _{1}^{\prime
}=0, \\
\\
\lambda \alpha _{1}^{\prime }\beta _{1}\gamma \cos \sqrt{\lambda }\left(
b-a\right) +O\left( \sqrt{\lambda }e^{\left\vert t\right\vert \left(
b-a\right) }\right) ,\text{ \ \ \ if }\beta _{2}=0,\alpha _{1}^{\prime }\neq
0, \\
\\
-\sqrt{\lambda }\alpha _{2}^{\prime }\beta _{1}\gamma \sin \sqrt{\lambda }
\left( b-a\right) +O\left( e^{\left\vert t\right\vert \left( b-a\right)
}\right) ,\text{ \ \ \ \ if }\beta _{2}=0,\alpha _{1}^{\prime }=0.
\end{array}
\right.  \tag{2.25}  \label{2.25}
\end{equation}

Consequently if $\lambda _{0}<\lambda _{1}<...,$ are the zeros of $\omega
\left( \lambda \right) ,$ then we have for sufficiently large $n$ the
following asymptotic formulas
\begin{equation}
\sqrt{\lambda _{n}}=\left\{
\begin{array}{l}
\frac{\left( n-1\right) \pi }{b-a}+O\left( n^{-1}\right) ,\text{ \ \ \ \ \ \
if }\beta _{2}\neq 0,\alpha _{1}^{\prime }\neq 0,\text{\ \ } \\
\\
\frac{\left( n-1/2\right) \pi }{b-a}+O\left( n^{-1}\right) ,\text{ \ \ \ \
if }\beta _{2}\neq 0,\alpha _{1}^{\prime }=0, \\
\\
\frac{\left( n-1/2\right) \pi }{b-a}+O\left( n^{-1}\right) ,\text{ \ \ \ \
if }\beta _{2}=0,\alpha _{1}^{\prime }\neq 0, \\
\\
\frac{n\pi }{b-a}+O\left( n^{-1}\right) ,\text{ \ \ \ \ \ \ \ \ \ \ if }
\beta _{2}=0,\alpha _{1}^{\prime }=0.
\end{array}
\right.  \tag{2.26}  \label{2.26}
\end{equation}

\section{Green Function}

To study the completeness of the eigenvectors of $A,$ and hence the
completeness of the eigenfunctions of the problem (1.1)-(1.7), we construct
the resolvent of $A$ as well as Green's function of the problem (1.1)-(1.7).
We assume without any loss of generality that $\lambda =0$ is not an
eigenvalue of $A.$ Now let $\lambda \in

\mathbb{C}

$ not be an eigenvalue of $A$ and consider the inhomogenous problem for f$
\left( x\right) =\left(
\begin{array}{c}
f\left( x\right) \\
f_{1}
\end{array}
\right) \in H,$ u$\left( x\right) =\left(
\begin{array}{c}
u\left( x\right) \\
R^{\prime }\left( u\right)
\end{array}
\right) \in D\left( A\right) ,$
\begin{equation}
\left( \lambda \text{I}-A\right) \text{u}\left( x\right) =\text{f}\left(
x\right) ,\text{ }x\in I,  \tag{3.1}  \label{3.1}
\end{equation}
and I is the identity operator. Since
\begin{equation}
\left( \lambda \text{I}-A\right) \text{u}\left( x\right) =\lambda \left(
\begin{array}{c}
u\left( x\right) \\
R^{\prime }\left( u\right)
\end{array}
\right) -\left(
\begin{array}{c}
\tau \left( u\right) \\
-R\left( u\right)
\end{array}
\right) =\left(
\begin{array}{c}
f\left( x\right) \\
f_{1}
\end{array}
\right)  \tag{3.2}  \label{3.2}
\end{equation}
then we have
\begin{equation}
\left( \lambda \text{I}-\tau \right) \text{u}\left( x\right) =\text{f}\left(
x\right) ,\text{ }x\in I,  \tag{3.3}  \label{3.3}
\end{equation}
\begin{equation}
\lambda R^{\prime }\left( u\right) +R\left( u\right) =f_{1}.  \tag{3.4}
\label{3.4}
\end{equation}

Now we can represent the general solution of homogeneous differential
equation (1.1), appropriate to equation (3.3) in the following form:
\begin{equation*}
u\left( x,\lambda \right) =\left\{
\begin{array}{c}
c_{1}\phi _{-\varepsilon ,\lambda }\left( x\right) +c_{2}\chi _{-\varepsilon
,\lambda }\left( x\right) ,\text{ \ \ }x\in \left[ a,\theta _{-\varepsilon
}\right) , \\
\\
c_{3}\phi _{\varepsilon ,\lambda }\left( x\right) +c_{4}\chi _{\varepsilon
,\lambda }\left( x\right) ,\text{ \ \ }x\in \left( \theta _{-\varepsilon
},\theta _{+\varepsilon }\right) , \\
\\
c_{5}\phi _{+\varepsilon ,\lambda }\left( x\right) +c_{6}\chi _{+\varepsilon
,\lambda }\left( x\right) ,\text{ \ \ \ }x\in \left( \theta _{+\varepsilon
},b\right] ,
\end{array}
\right.
\end{equation*}
in which $c_{i}$ $\left( i=\overline{1,6}\right) $ are arbitrary constants.
By applying the method of variation of the constants, we shall search the
general solution of the non-homogeneous linear differential equation (3.3)
in the following form:
\begin{equation}
u\left( x,\lambda \right) =\left\{
\begin{array}{c}
c_{1}\left( x,\lambda \right) \phi _{-\varepsilon ,\lambda }\left( x\right)
+c_{2}\left( x,\lambda \right) \chi _{-\varepsilon ,\lambda }\left( x\right)
,\text{ \ \ }x\in \left[ a,\theta _{-\varepsilon }\right) , \\
\\
c_{3}\left( x,\lambda \right) \phi _{\varepsilon ,\lambda }\left( x\right)
+c_{4}\left( x,\lambda \right) \chi _{\varepsilon ,\lambda }\left( x\right) ,
\text{ \ \ }x\in \left( \theta _{-\varepsilon },\theta _{+\varepsilon
}\right) , \\
\\
c_{5}\left( x,\lambda \right) \phi _{+\varepsilon ,\lambda }\left( x\right)
+c_{6}\left( x,\lambda \right) \chi _{+\varepsilon ,\lambda }\left( x\right)
,\text{ \ \ \ }x\in \left( \theta _{+\varepsilon },b\right] ,
\end{array}
\right.  \tag{3.5}  \label{3.5}
\end{equation}
where the functions $c_{i}\left( x,\lambda \right) $ $\left( i=\overline{1,6}
\right) $ satisfy the linear system of equation
\begin{equation}
\left\{
\begin{array}{l}
c_{1}^{\prime }\left( x,\lambda \right) \phi _{-\varepsilon ,\lambda }\left(
x\right) +c_{2}^{\prime }\left( x,\lambda \right) \chi _{-\varepsilon
,\lambda }\left( x\right) =0, \\
\\
c_{1}^{\prime }\left( x,\lambda \right) \phi _{-\varepsilon ,\lambda
}^{\prime }\left( x\right) +c_{2}^{\prime }\left( x,\lambda \right) \chi
_{-\varepsilon ,\lambda }^{\prime }\left( x\right) =f\left( x\right) ,
\end{array}
\right. \text{ \ for \ }x\in \left[ a,\theta _{-\varepsilon }\right)
\tag{3.6}  \label{3.6}
\end{equation}
\begin{equation}
\left\{
\begin{array}{l}
c_{3}^{\prime }\left( x,\lambda \right) \phi _{\varepsilon ,\lambda }\left(
x\right) +c_{4}^{\prime }\left( x,\lambda \right) \chi _{\varepsilon
,\lambda }\left( x\right) =0, \\
\\
c_{3}^{\prime }\left( x,\lambda \right) \phi _{\varepsilon ,\lambda
}^{\prime }\left( x\right) +c_{4}^{\prime }\left( x,\lambda \right) \chi
_{\varepsilon ,\lambda }^{\prime }\left( x\right) =f\left( x\right) ,
\end{array}
\right. \text{ \ for \ }x\in \left( \theta _{-\varepsilon },\theta
_{+\varepsilon }\right)  \tag{3.7}  \label{3.7}
\end{equation}
\begin{equation}
\left\{
\begin{array}{l}
c_{5}^{\prime }\left( x,\lambda \right) \phi _{+\varepsilon ,\lambda }\left(
x\right) +c_{6}^{\prime }\left( x,\lambda \right) \chi _{+\varepsilon
,\lambda }\left( x\right) =0, \\
\\
c_{5}^{\prime }\left( x,\lambda \right) \phi _{+\varepsilon ,\lambda
}^{\prime }\left( x\right) +c_{6}^{\prime }\left( x,\lambda \right) \chi
_{+\varepsilon ,\lambda }^{\prime }\left( x\right) =f\left( x\right) ,
\end{array}
\right. \text{ \ for \ }x\in \left( \theta _{+\varepsilon },b\right] .
\tag{3.8}  \label{3.8}
\end{equation}

Since $\lambda $ is not an eigenvalue and $\omega _{-\varepsilon }\left(
\lambda \right) \neq 0,$ $\omega _{\varepsilon }\left( \lambda \right) \neq
0,$ $\omega _{+\varepsilon }\left( \lambda \right) \neq 0,$ each of the
linear systems in (3.6)-(3.8) have a unique solution which leads
\begin{equation}
\left\{
\begin{array}{l}
c_{1}\left( x,\lambda \right) =\frac{1}{\omega _{-\varepsilon }\left(
\lambda \right) }\underset{x}{\overset{\theta _{-\varepsilon }}{\int }}\chi
_{-\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+c_{1}\left(
\lambda \right) , \\
c_{2}\left( x,\lambda \right) =\frac{1}{\omega _{-\varepsilon }\left(
\lambda \right) }\underset{a}{\overset{x}{\int }}\phi _{-\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+c_{2}\left( \lambda \right) ,
\end{array}
\right. \text{ for \ }x\in \left[ a,\theta _{-\varepsilon }\right)  \tag{3.9}
\label{3.9}
\end{equation}
\begin{equation}
\left\{
\begin{array}{l}
c_{3}\left( x,\lambda \right) =\frac{1}{\omega _{\varepsilon }\left( \lambda
\right) }\underset{x}{\overset{\theta _{+\varepsilon }}{\int }}\chi
_{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+c_{3}\left(
\lambda \right) , \\
c_{4}\left( x,\lambda \right) =\frac{1}{\omega _{\varepsilon }\left( \lambda
\right) }\underset{\theta _{-\varepsilon }}{\overset{x}{\int }}\phi
_{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+c_{4}\left(
\lambda \right) ,
\end{array}
\right. \text{ \ for \ }x\in \left( \theta _{-\varepsilon },\theta
_{+\varepsilon }\right)  \tag{3.10}  \label{3.10}
\end{equation}
\begin{equation}
\left\{
\begin{array}{l}
c_{5}\left( x,\lambda \right) =\frac{1}{\omega _{+\varepsilon }\left(
\lambda \right) }\underset{x}{\overset{b}{\int }}\chi _{+\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+c_{5}\left( \lambda \right) ,
\\
c_{6}\left( x,\lambda \right) =\frac{1}{\omega _{+\varepsilon }\left(
\lambda \right) }\underset{\theta _{+\varepsilon }}{\overset{x}{\int }}\phi
_{+\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+c_{6}\left(
\lambda \right) ,
\end{array}
\right. \text{ \ for \ }x\in \left( \theta _{+\varepsilon },b\right]
\tag{3.11}  \label{3.11}
\end{equation}
where $c_{i}\left( \lambda \right) $ $\left( i=\overline{1,6}\right) $ are
arbitrary constants. Substituting (3.9)-(3.11) into (3.5), we obtain the
solution of the equation (3.3)
\begin{equation}
u\left( x,\lambda \right) =\left\{
\begin{array}{l}
\frac{\phi _{-\varepsilon ,\lambda }\left( x\right) }{\omega _{-\varepsilon
}\left( \lambda \right) }\underset{x}{\overset{\theta _{-\varepsilon }}{\int
}}\chi _{-\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{
\chi _{-\varepsilon ,\lambda }\left( x\right) }{\omega _{-\varepsilon
}\left( \lambda \right) }\underset{a}{\overset{x}{\int }}\phi _{-\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+ \\
c_{1}\left( \lambda \right) \phi _{-\varepsilon ,\lambda }\left( x\right)
+c_{2}\left( \lambda \right) \chi _{-\varepsilon ,\lambda }\left( x\right) ,
\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x\in \left[ a,\theta
_{-\varepsilon }\right) , \\
\\
\frac{\phi _{\varepsilon ,\lambda }\left( x\right) }{\omega _{\varepsilon
}\left( \lambda \right) }\underset{x}{\overset{\theta _{+\varepsilon }}{\int
}}\chi _{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{
\chi _{\varepsilon ,\lambda }\left( x\right) }{\omega _{\varepsilon }\left(
\lambda \right) }\underset{\theta _{-\varepsilon }}{\overset{x}{\int }}\phi
_{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+ \\
c_{3}\left( \lambda \right) \phi _{\varepsilon ,\lambda }\left( x\right)
+c_{4}\left( \lambda \right) \chi _{\varepsilon ,\lambda }\left( x\right) ,
\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x\in \left( \theta
_{-\varepsilon },\theta _{+\varepsilon }\right) , \\
\\
\frac{\phi _{+\varepsilon ,\lambda }\left( x\right) }{\omega _{+\varepsilon
}\left( \lambda \right) }\underset{x}{\overset{b}{\int }}\chi _{+\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+\frac{\chi _{+\varepsilon
,\lambda }\left( x\right) }{\omega _{+\varepsilon }\left( \lambda \right) }
\underset{\theta _{+\varepsilon }}{\overset{x}{\int }}\phi _{+\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+ \\
c_{5}\left( \lambda \right) \phi _{+\varepsilon ,\lambda }\left( x\right)
+c_{6}\left( \lambda \right) \chi _{+\varepsilon ,\lambda }\left( x\right) ,
\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x\in \left( \theta
_{+\varepsilon },b\right] .
\end{array}
\right.  \tag{3.12}  \label{3.12}
\end{equation}

Then from the boundary conditions (3.4) and (1.2) and the transmission
conditions (1.4)-(1.7) we get
\begin{equation}
\begin{array}{l}
c_{1}\left( \lambda \right) =\frac{1}{\omega _{\varepsilon }\left( \lambda
\right) }\underset{\theta _{-\varepsilon }}{\overset{\theta _{+\varepsilon }}
{\int }}\chi _{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+
\frac{1}{\omega _{+\varepsilon }\left( \lambda \right) }\underset{\theta
_{+\varepsilon }}{\overset{b}{\int }}\chi _{+\varepsilon ,\lambda }\left(
y\right) f\left( y\right) dy+\frac{f_{1}}{\omega _{+\varepsilon }\left(
\lambda \right) }, \\
\\
c_{2}\left( \lambda \right) =0,\text{ \ \ \ \ \ \ }c_{3}\left( \lambda
\right) =\frac{1}{\omega _{+\varepsilon }\left( \lambda \right) }\underset{
\theta _{+\varepsilon }}{\overset{b}{\int }}\chi _{+\varepsilon ,\lambda
}\left( y\right) f\left( y\right) dy+\frac{f_{1}}{\omega _{+\varepsilon
}\left( \lambda \right) }, \\
\\
c_{4}\left( \lambda \right) =\frac{1}{\omega _{-\varepsilon }\left( \lambda
\right) }\underset{a}{\overset{\theta _{-\varepsilon }}{\int }}\phi
_{-\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy,\text{ \ \ \ \
\ \ \ \ \ \ }c_{5}\left( \lambda \right) =\frac{f_{1}}{\omega _{+\varepsilon
}\left( \lambda \right) }, \\
\\
c_{6}\left( \lambda \right) =\frac{1}{\omega _{-\varepsilon }\left( \lambda
\right) }\underset{a}{\overset{\theta _{-\varepsilon }}{\int }}\phi
_{-\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{1}{\omega
_{\varepsilon }\left( \lambda \right) }\underset{\theta _{-\varepsilon }}{
\overset{\theta _{+\varepsilon }}{\int }}\phi _{\varepsilon ,\lambda }\left(
y\right) f\left( y\right) dy.
\end{array}
\tag{3.13}  \label{3.13}
\end{equation}

Substituting (3.13) and (2.11) into (3.12), then (3.12) can be written as
\begin{equation}
u\left( x,\lambda \right) =\left\{
\begin{array}{l}
\frac{\phi _{-\varepsilon ,\lambda }\left( x\right) }{\omega \left( \lambda
\right) }\underset{x}{\overset{\theta _{-\varepsilon }}{\int }}\chi
_{-\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{\chi
_{-\varepsilon ,\lambda }\left( x\right) }{\omega \left( \lambda \right) }
\underset{a}{\overset{x}{\int }}\phi _{-\varepsilon ,\lambda }\left(
y\right) f\left( y\right) dy+ \\
\frac{\delta ^{2}\phi _{-\varepsilon ,\lambda }\left( x\right) }{\omega
\left( \lambda \right) }\underset{\theta _{-\varepsilon }}{\overset{\theta
_{+\varepsilon }}{\int }}\chi _{\varepsilon ,\lambda }\left( y\right)
f\left( y\right) dy+\frac{\delta ^{2}\phi _{-\varepsilon ,\lambda }\left(
x\right) }{\omega \left( \lambda \right) }\underset{\theta _{+\varepsilon }}{
\overset{b}{\int }}\chi _{+\varepsilon ,\lambda }\left( y\right) f\left(
y\right) dy+ \\
\frac{\gamma ^{2}f_{1}}{\omega \left( \lambda \right) }\phi _{-\varepsilon
,\lambda }\left( x\right) ,\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x\in \left[
a,\theta _{-\varepsilon }\right) , \\
\\
\frac{\delta ^{2}\phi _{\varepsilon ,\lambda }\left( x\right) }{\omega
\left( \lambda \right) }\underset{x}{\overset{\theta _{+\varepsilon }}{\int }
}\chi _{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{
\delta ^{2}\chi _{\varepsilon ,\lambda }\left( x\right) }{\omega \left(
\lambda \right) }\underset{\theta _{-\varepsilon }}{\overset{x}{\int }}\phi
_{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+ \\
\frac{\gamma ^{2}\phi _{\varepsilon ,\lambda }\left( x\right) }{\omega
\left( \lambda \right) }\underset{\theta _{+\varepsilon }}{\overset{b}{\int }
}\chi _{+\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{
\chi _{\varepsilon ,\lambda }\left( x\right) }{\omega \left( \lambda \right)
}\underset{a}{\overset{\theta _{-\varepsilon }}{\int }}\phi _{-\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+ \\
\frac{\gamma ^{2}f_{1}}{\omega \left( \lambda \right) }\phi _{\varepsilon
,\lambda }\left( x\right) ,\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x\in \left(
\theta _{-\varepsilon },\theta _{+\varepsilon }\right) , \\
\\
\frac{\gamma ^{2}\phi _{+\varepsilon ,\lambda }\left( x\right) }{\omega
\left( \lambda \right) }\underset{x}{\overset{b}{\int }}\chi _{+\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+\frac{\gamma ^{2}\chi
_{+\varepsilon ,\lambda }\left( x\right) }{\omega \left( \lambda \right) }
\underset{\theta _{+\varepsilon }}{\overset{x}{\int }}\phi _{+\varepsilon
,\lambda }\left( y\right) f\left( y\right) dy+ \\
\frac{\chi _{+\varepsilon ,\lambda }\left( x\right) }{\omega \left( \lambda
\right) }\underset{a}{\overset{\theta _{-\varepsilon }}{\int }}\phi
_{-\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+\frac{\delta
^{2}\chi _{+\varepsilon ,\lambda }\left( x\right) }{\omega \left( \lambda
\right) }\underset{\theta _{-\varepsilon }}{\overset{\theta _{+\varepsilon }}
{\int }}\phi _{\varepsilon ,\lambda }\left( y\right) f\left( y\right) dy+ \\
\frac{\gamma ^{2}f_{1}}{\omega \left( \lambda \right) }\phi _{+\varepsilon
,\lambda }\left( x\right) ,\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }x\in \left(
\theta _{+\varepsilon },b\right] .
\end{array}
\right.  \tag{3.14}  \label{3.14}
\end{equation}

Hence, we have
\begin{eqnarray}
\text{u}\left( x\right) &=&\left( \lambda \text{I}-A\right) ^{-1}\text{f}
\left( x\right)  \notag \\
&=&\left( \underset{{\Large R}^{\prime }\left( u\right) }{
\begin{array}{c}
\underset{a}{\overset{\theta _{-\varepsilon }}{\int }}G\left( x,y,\lambda
\right) f\left( y\right) dy+\delta ^{2}\underset{\theta _{-\varepsilon }}{
\overset{\theta _{+\varepsilon }}{\int }}G\left( x,y,\lambda \right) f\left(
y\right) dy+ \\
\gamma ^{2}\underset{\theta _{+\varepsilon }}{\overset{b}{\int }}G\left(
x,y,\lambda \right) f\left( y\right) dy+\dfrac{\gamma ^{2}}{\omega \left(
\lambda \right) }f_{1}\phi _{\lambda }\left( x\right) \text{ \ \ \ \ \ \ \ \
\ \ \ \ \ }
\end{array}
}\right)  \TCItag{3.15}  \label{3.15}
\end{eqnarray}
where
\begin{equation}
G\left( x,y,\lambda \right) =\frac{1}{\omega \left( \lambda \right) }\left\{
\begin{array}{l}
\chi _{\lambda }\left( x\right) \phi _{-\varepsilon ,\lambda }\left(
y\right) ,\text{ \ \ \ \ \ }a\leq y\leq x\leq \theta _{-\varepsilon }, \\
\\
\chi _{\lambda }\left( y\right) \phi _{-\varepsilon ,\lambda }\left(
x\right) ,\text{ \ \ \ \ \ }a\leq x\leq y\leq \theta _{-\varepsilon }, \\
\\
\chi _{\lambda }\left( x\right) \phi _{\lambda }\left( y\right) ,\text{ \ \
\ \ \ }\theta _{-\varepsilon }\leq y\leq x\leq \theta _{+\varepsilon }, \\
\\
\chi _{\lambda }\left( y\right) \phi _{\lambda }\left( x\right) ,\text{ \ \
\ \ \ }\theta _{-\varepsilon }\leq x\leq y\leq \theta _{+\varepsilon }, \\
\\
\chi _{+\varepsilon ,\lambda }\left( x\right) \phi _{\lambda }\left(
y\right) ,\text{ \ \ \ \ \ }\theta _{+\varepsilon }\leq y\leq x\leq b, \\
\\
\chi _{+\varepsilon ,\lambda }\left( y\right) \phi _{\lambda }\left(
x\right) ,\text{ \ \ \ \ \ }\theta _{+\varepsilon }\leq x\leq y\leq b,
\end{array}
\right.  \tag{3.16}  \label{3.16}
\end{equation}
is Green's function of the problem (1.1)-(1.7).

\section{The Sampling Theorem}

In this section we derive two sampling theorems associated with the problem
(1.1)-(1.7). For convenience we may assume that the eigenvectors of $A$ are
real valued.

\begin{theorem}
Consider the problem (1.1)-(1.7), and let
\begin{equation}
\phi _{\lambda }\left( x\right) =\left\{
\begin{array}{l}
\phi _{-\varepsilon ,\lambda }\left( x\right) ,\text{ \ \ }x\in \left[
a,\theta _{-\varepsilon }\right) , \\
\phi _{\varepsilon ,\lambda }\left( x\right) ,\text{ \ }x\in \left( \theta
_{-\varepsilon },\theta _{+\varepsilon }\right) , \\
\phi _{+\varepsilon ,\lambda }\left( x\right) ,\text{ \ \ }x\in \left(
\theta _{+\varepsilon },b\right] ,
\end{array}
\right.  \tag{4.1}  \label{4.1}
\end{equation}
\textit{be the solution defined above. Let }$g\left( .\right) \in
L_{2}\left( a,b\right) $\textit{\ and }
\begin{equation}
F\left( \lambda \right) =\underset{a}{\overset{\theta _{-\varepsilon }}{\int
}}g\left( x\right) \phi _{-\varepsilon ,\lambda }\left( x\right) dx+\delta
^{2}\underset{\theta _{-\varepsilon }}{\overset{\theta _{+\varepsilon }}{
\int }}g\left( x\right) \phi _{\varepsilon ,\lambda }\left( x\right)
dx+\gamma ^{2}\underset{\theta _{+\varepsilon }}{\overset{b}{\int }}g\left(
x\right) \phi _{+\varepsilon ,\lambda }\left( x\right) dx.  \tag{4.2}
\label{4.2}
\end{equation}
\end{theorem}

\textit{Then }$F\left( \lambda \right) $\textit{\ is an entire function of
exponential type }$(b-a)$\textit{\ that can be reconstructed from its values
at the points }$\left\{ \lambda _{n}\right\} _{n=0}^{\infty }$\textit{\ \ \
via the sampling formula}
\begin{equation}
F\left( \lambda \right) =\overset{\infty }{\underset{n=0}{\sum }}F\left(
\lambda _{n}\right) \frac{\omega \left( \lambda \right) }{\left( \lambda
-\lambda _{n}\right) \omega ^{\prime }\left( \lambda _{n}\right) }.
\tag{4.3}  \label{4.3}
\end{equation}

\textit{The series (4.2) converges absolutely on }$

\mathbb{C}

$\textit{\ and uniformly on compact subset of }$

\mathbb{C}

.$\textit{\ Here }$\omega \left( \lambda \right) $\textit{\ is the entire
function defined in (2.11).}

\begin{proof}
...
\end{proof}

\begin{remark}
To see that expansion (4.3) is a Lagrange type interpolation, we may replace
$\omega \left( \lambda \right) $ by the canonical product
\begin{equation}
\widetilde{\omega }\left( \lambda \right) =\left\{
\begin{array}{c}
\overset{\infty }{\underset{n=0}{\Pi }}\left( 1-\dfrac{\lambda }{\lambda _{n}
}\right) ,\text{ if zero is not an eigenvalue,} \\
\\
\lambda \overset{\infty }{\underset{n=1}{\Pi }}\left( 1-\dfrac{\lambda }{
\lambda _{n}}\right) ,\text{ if }\lambda _{0}=0\text{ is an eigenvalue.}
\end{array}
\right.  \tag{4.26}  \label{4.26}
\end{equation}
\end{remark}

From Hadamard's factorization theorem, see $\left[ 31\right] ,$ $\omega
\left( \lambda \right) =h\left( \lambda \right) \widetilde{\omega }\left(
\lambda \right) ,$ where $h\left( \lambda \right) $ is an entire function
with no zeros. Thus,
\begin{equation}
\frac{\omega \left( \lambda \right) }{\omega ^{\prime }\left( \lambda
_{n}\right) }=\frac{h\left( \lambda \right) \widetilde{\omega }\left(
\lambda \right) }{h\left( \lambda _{n}\right) \widetilde{\omega }^{\prime
}\left( \lambda _{n}\right) }  \tag{4.27}  \label{4.27}
\end{equation}
and (4.2), (4.3) remain valid for the function $F\left( \lambda \right)
/h\left( \lambda \right) .$ Hence
\begin{equation}
F\left( \lambda \right) =\overset{\infty }{\underset{n=0}{\sum }}F\left(
\lambda _{n}\right) \frac{h\left( \lambda \right) \widetilde{\omega }\left(
\lambda \right) }{\left( \lambda -\lambda _{n}\right) h\left( \lambda
_{n}\right) \widetilde{\omega }^{\prime }\left( \lambda _{n}\right) }.
\tag{4.28}  \label{4.28}
\end{equation}

We may redefine (4.2) by taking kernel $\phi _{\lambda }\left( .\right)
/h\left( \lambda \right) =\widetilde{\phi }_{\lambda }\left( .\right) $ to
get
\begin{equation}
\widetilde{F}\left( \lambda \right) =\frac{F\left( \lambda \right) }{h\left(
\lambda \right) }=\overset{\infty }{\underset{n=0}{\sum }}\widetilde{F}
\left( \lambda _{n}\right) \frac{\widetilde{\omega }\left( \lambda \right) }{
\left( \lambda -\lambda _{n}\right) \widetilde{\omega }^{\prime }\left(
\lambda _{n}\right) }.  \tag{4.29}  \label{4.29}
\end{equation}

The next theorem is devoted to give interpolation sampling expansions
associated with the problem (1.1)-(1.7) for integral transforms whose
kernels defined in terms of Green's function (see $\left[ 20,32\right] )$.
As we see in (3.16), Green' function $G\left( x,y,\lambda \right) $ of the
problem (1.1)-(1.7) has simple poles at $\left\{ \lambda _{n}\right\}
_{n=0}^{\infty }.$

Define the function $G\left( x,\lambda \right) $ to be $G\left( x,\lambda
\right) :=\omega \left( \lambda \right) G\left( x,y_{0},\lambda \right) ,$
where $y_{0}\in I$ is a fixed point and $\omega \left( \lambda \right) $ is
the function defined in equation (2.11) or it is the canonical product
(4.26).

\begin{theorem}
Let g$\left( .\right) \in L_{2}\left( a,b\right) $ and $F\left( \lambda
\right) $ the integral transform
\begin{equation}
F\left( \lambda \right) =\underset{a}{\overset{\theta _{-\varepsilon }}{\int
}}G\left( x,\lambda \right) \overline{g}\left( x\right) dx+\delta ^{2}
\underset{\theta _{-\varepsilon }}{\overset{\theta _{+\varepsilon }}{\int }}
G\left( x,\lambda \right) \overline{g}\left( x\right) dx+\gamma ^{2}\underset
{\theta _{+\varepsilon }}{\overset{b}{\int }}G\left( x,\lambda \right)
\overline{g}\left( x\right) dx.  \tag{4.30}  \label{4.30}
\end{equation}
\end{theorem}

\textit{Then }$F\left( \lambda \right) $\textit{\ is an entire function of
exponential type }$(b-a)$\textit{\ which admits the sampling representation}
\begin{equation}
F\left( \lambda \right) =\overset{\infty }{\underset{n=0}{\sum }}F\left(
\lambda _{n}\right) \frac{\omega \left( \lambda \right) }{\left( \lambda
-\lambda _{n}\right) \omega ^{\prime }\left( \lambda _{n}\right) }.
\tag{4.31}  \label{4.31}
\end{equation}

\textit{Series (4.31) converges absolutely on }$

\mathbb{C}

$\textit{\ and uniformly on compact subset of }$

\mathbb{C}

.$\textit{\ }

\begin{proof}
...
\end{proof}


TITLE: How to prove that $x^{\frac{1}{\log_a(x)}}$ is a constant?
QUESTION [1 upvotes]: Are the following lines a valid proof that $x^{\frac{1}{\log_a(x)}}$ is a constant?
$$K = x^{\frac{1}{\log_a(x)}}$$
$$\log_a(K) = \frac{\log_a(x)}{\log_a(x)} = 1, \text{ for } x \notin \{0, 1\}$$
$$K = a$$
If not, how does one prove this?

REPLY [2 votes]: Using change of base formula (i.e. $\log_p(q)=\frac{\log q}{\log p}$), we can show that $\frac{1}{\log_p (q)}=\log_q (p)$.
This means $K=x^{\log_x (a)}=a$


TITLE: Given quadratic integral relations for $y$ and $z$, find explicit integral relations for $y+z$ and $yz$
QUESTION [1 upvotes]: $A$ $\subset$ $B$ is a ring extension. If $y,z \in B$ satisfy quadratic integral dependence relations $y^2+ay+b=0$ and $z^2+cz+d=0$ over $A$, find explicit integral dependence relations for $y+z$ and $yz$

I used the hint provided and assumed that $1/2 \in A$, and used the quadratic formula for obtaining $y$ and $z$. Then I calculated $y+z$. After a really cumbersome calculation (trivial though) I managed to obtain an integral relation for $y+z$. However, for $yz$, I think there should be an easier way because even for $y+z$, which includes two square roots the calculation was long. I appreciate any solution or hint.

REPLY [1 votes]: Let $y=y_1$, $y_2$ the roots of the first equation and $z=z_1$, $z_2$ the roots of the second equation. Then $x=y+z$ is a root of
$$(X-(y_1+z_1))(X-(y_1+z_z))(X-(y_2+z_1))(X-(y_2+z_2))$$
Expand and express the coefficients of this polynomial in terms of $a$,$b$, $c$, $d$.
If you just want a quick result, use elimination with Groebner bases and some software. The result is fairly long, an equation of degree $4$ in $x$. See results with WA here.


TITLE: Show $(n_{i}+g_{i}-1)!\simeq(g_{i}-1)! g_{i}^{n_{i}}$
QUESTION [1 upvotes]: I can' t comprehend why the the following is true:
$$n_{i}<<g_{i}$$
$$(n_{i}+g_{i}-1)!\simeq(g_{i}-1)! g_{i}^{n_{i}}$$

REPLY [2 votes]: $$
(n+g-1)!=(n-1+g)!=(n-1+g)(n-2+g)\ldots(1+g)g(g-1)!
$$
and using $n << g$ approximate $(n-1+g)$ etc. by $g$:
$$
(n-1+g) \approx g\\
(n-2+g) \approx g\\
\vdots\\
(1+g) \approx g
$$
so
$$
(n+g-1)!=g\,g\,\ldots g\,g\,(g-1)!
$$
where there are $n$ terms in $g$, giving your result.
For a specific example if $g=1000$ and $n=10$ the approximations being made are
$$
1009\approx 1000\\
1008\approx 1000\\
\vdots \\
1001 \approx 1000
$$


TITLE: Dimension and basis of bounded linear maps (products)
QUESTION [1 upvotes]: Let $X, Y, Z$ be finite dimensional normed spaces with bases $\{x_1,...,x_l\}$, $\{y_1,...,y_m\}$, $\{z_1,...,z_n\}$ respectively.

What is the dimension of $\mathcal{L} \{X \times Y; Z\}$ and give an example of a basis.
What is the dimension of $\mathcal{L^2} \{X, Y; Z\}$ and give an example of a basis.

I'm not entirely sure what the question means. But for 1. I said the dimension is l*m  (I used matrix multiplication). For the basis is it the column vectors? $(x_1y_1,....,x_ly_1)^T \ldots (x_1y_m,....,x_ly_m)^T$.
I am not sure about 2

REPLY [1 votes]: Hint: $L(X \times Y;Z)$ is the vector space of linear maps $T: X \times Y \rightarrow Z$.
For each you need to find a set of linear maps that form a basis of the respective spaces.
So for $L(X \times Y;Z)$ you need to find a collection of linear maps $T: X \times Y \rightarrow Z$ that form a basis of the vector space $L(X \times Y;Z)$. The number of such linear maps is the dimension of the space $L(X \times Y;Z)$.
For question $1$ your collection of column vectors are not linear maps and thus do not form a basis.


TITLE: How to calculate $\sqrt{\frac{-3}{4} - i}$
QUESTION [4 upvotes]: Possible Duplicate:
How do I get the square root of a complex number?

I know that the answer to $\sqrt{\dfrac{-3}{4} - i}$ is $\dfrac12 - i$. But how do I calculate it mathematically if I don't have access to a calculator?

REPLY [2 votes]: Another method is polar coordinates.  $|-3/4-i| = 5/4$ and
$$
-\frac{3}{4} - i = \frac{5}{4}\;\exp(i\theta)
$$
where $\cos(\theta) = -3/5 $ and $\sin(\theta) = -4/5 $.  Use half-angle formulas to get $\cos(\theta/2)$ and $\sin(\theta/2)$, actually two choices, then your answer is
$$
\sqrt{\frac{5}{4}}\;\exp\left(\frac{i\theta}{2}\right)
$$