text:
\begin{document}
\parskip 6pt

\pagenumbering{arabic}
\def\sof{\hfill\rule{2mm}{2mm}}
\def\ls{\leq}
\def\gs{\geq}
\def\SS{\mathcal S}
\def\qq{{\bold q}}
\def\MM{\mathcal M}
\def\TT{\mathcal T}
\def\EE{\mathcal E}
\def\lsp{\mbox{lsp}}
\def\rsp{\mbox{rsp}}
\def\pf{\noindent {\it Proof.} }
\def\mp{\mbox{pyramid}}
\def\mb{\mbox{block}}
\def\mc{\mbox{cross}}
\def\qed{\hfill \rule{4pt}{7pt}}
\def\block{\hfill \rule{5pt}{5pt}}

\begin{center}
{\Large\bf  On a conjecture about enumerating $(2+2)$-free posets  }
\vskip 6mm
\end{center}

\begin{center}
{\small   Sherry H. F. Yan \\[2mm]
 Department of Mathematics, Zhejiang Normal University, Jinhua
321004, P.R. China
\\[2mm]
 huifangyan@hotmail.com
  \\[0pt]
}
\end{center}

\noindent {\bf Abstract.} Recently, Kitaev and Remmel posed
 a conjecture concerning  the   generating function for the number
 of unlabeled
$(2+2)$-free posets  with respect to number of elements  and number
of minimal elements.  In this paper, we   present    a combinatorial
proof of  this conjecture.

\noindent {\sc Key words}:   $(2+2)$-free poset, minimal element.

\noindent {\sc AMS Mathematical Subject Classifications}: 05A05,
05C30.

\section{Introduction}
A  poset is said to be $(2+2)$-free if it does not contain an
induced subposet that is isomorphic to $2+2$, the union of two
disjoint $2$-element chains. In a poset, let $D(x)$ be the set of
{\em predecessors} of  an element $x$ (the strict down-set of $x$).
Formally, $D(x)=\{y: y<x\}$.  A poset $P$  is $(2+2)$-free if and
only if its sets of predecessors, $D(P)=\{D(x): x\in P\}$ can be
 written as
  $$
  D(P)=\{D_0, D_1, \ldots, D_k \}
 $$
where $\emptyset=D_0\subset D_1\subset\ldots \subset D_k$, see
\cite{Bog, melon}. In such context, we say that $x\in P$ has {\em
level} $i$ if $D(x)=D_i$.  An element $x$ is said to be a {\em
minimal} element if $x$ has level $0$.

Let $p_n$ be the number of unlabeled  $(2+2)$-free posets on $n$
elements. EI-Zahar \cite{zahar} and Khamis \cite{khamis} used a
recursive description of  $(2+2)$-free posets to derive a pair of
functional equations that define the generating function for the
number $p_n$. But they did not solve these equations. Recently,
using functional equations and the Kernel method,
Bousquet-M$\acute{e}$lou et al. \cite{melon} showed that the
generating function for the number $p_n$ of unlabeled  $(2+2)$-free
posets on n elements is given by
\begin{equation} \label{pt}
P(t)= \sum_{n\geq 0}p_{n} t^n =  \sum_{n\geq
0}\prod_{i=1}^{n}(1-(1-t)^{i} ).
\end{equation}
Note that throughout this paper, the empty product as usual is taken
to be $1$.  In fact, they studied a more general function of
unlabeled $(2+2)$-free posets according to number of elements,
number of levels and level of minimum maximal elements. Zagier
\cite{zag} proved that Formula (\ref{pt}) is also the generating
function for certain involutions introduced by Stoimenow
\cite{Stoi}.

Given a sequence of integers   $x=(x_1,x_2,\ldots, x_n)$, we say
that the sequence $x$ has an ascent at position $i$ if
$x_i<x_{i+1}$. The number of ascents of $x$ is denoted by $asc(x)$.
A sequence $x=(x_1,x_2, \ldots, x_n)$ is said to be an {\em ascent
sequence of length $n$} if it satisfies $x_1=0$ and $0\leq x_i\leq
asc(x_1,x_2,\ldots, x_{i-1})+1$ for all $2\leq i\leq n$. Ascent
sequences were introduce by Bousquet-M$\acute{e}$lou et al.
\cite{melon}  to unify three combinatorial structures.
Bousquet-M$\acute{e}$lou et al. \cite{melon} constructed bijections
between unlabeled  $(2+2)$-free posets and ascent sequences, between
ascent sequences and permutations avoiding a certain pattern,
between unlabeled $(2+2)$-free posets and a class of involutions
introduced by Stoimenow \cite{Stoi}.

Recently, Kitaev and Remmel \cite{Kitaev} extended the work of
Bousquet-M$\acute{e}$lou et al. \cite{melon}. They found generating
function for unlabeled  $(2+2)$-free posets when four statistics are
taken into account, one of which is the number of minimal elements
in a poset. The key strategy used by Bousquet-M$\acute{e}$lou et al.
\cite{melon} and Kitaev and Remmel \cite{Kitaev}  is to translate
statistics on $(2+2)$-free posets to statistics on ascent sequences
using  the bijection between unlabeled  $(2+2)$-free posets and
ascent sequences given by Bousquet-M$\acute{e}$lou et al.
\cite{melon}. Let $p_{n,k}$ be the number of $(2+2)$-free posets on
$n$ elements with $k$ minimal elements, with the assumption
$p_{0,0}=1$. Under the bijection between unlabeled $(2+2)$-free
posets and ascent sequences, the number of unlabeled $(2+2)$-free
posets on $n$ elements with $k$ minimal elements is equal to that of
ascent sequences of length $n$ with $k$ zeros. Kitaev and Remmel
\cite{Kitaev} derived that the generating function for the number
$p_{n,k}$ is given by
$$
P(t,z)=\sum_{n\geq 0, k\geq 0}p_{n,k}z^kt^n= 1+ \sum_{n\geq
0}{zt\over (1-tz)^{n+1}}\prod_{i=1}^{n}(1-(1-t)^i),
$$
by counting ascent sequences with respect to  length and number of
zeros. Moreover, they conjectured the function $P(t,z)$ can be
written in a simpler form.

\begin{conjecture}\label{conjecture}

\begin{equation}\label{identity}
P(t,z)=\sum_{n\geq 0, k\geq 0}p_{n,k}z^kt^n= \sum_{n\geq
0}\prod_{i=1}^{n}(1-(1-t)^{i-1}(1-zt)).\end{equation}
\end{conjecture}

   The objective of this paper  is to give a combinatorial proof
of Conjecture \ref{conjecture}.  In order to prove the conjecture,
we need  two more  combinatorial structures: upper triangular
matrices with non-negative  integer entries such that all rows and
columns contain at least one non-zero entry, which was introduced by
Dukes and Parviainen \cite{Duck},  and upper triangular
$(0,1)$-matrices in which all columns contain at least one non-zero
entry.

  Let
$\mathcal{A}_n$ be the collection of upper triangular matrices with
non-negative integer entries which sum to $n$.   A {\em
$(0,1)$-matrix} is a matrix in which each entry is either  $0$ or
$1$. Let $\mathcal{M}_n$ be the set of $(0,1)$-matrices in
$\mathcal{A}_n$ in which  all columns contain at least one non-zero
entry. Denote by $\mathcal{I}_n$ the set of matrices in
$\mathcal{A}_n$ in which all rows and columns contain at least one
non-zero entry.  Given a matrix $A$, denoted  by $A_{i,j}$ the entry
in row $i$ and column $j$.  Let $dim(A)$ be the number of rows in
the matrix $A$. The sum of all entries in row $i$ is called the {\em
row sum}  of row $i$, denoted by $rsum_i(A)$. The {\em column sum}
of column $i$, denoted by $csum_i(A)$,  can be defined similarly. A
row is said to be {\em zero} if its row sum is zero.

Let $A$ be a matrix in $\mathcal{M}_n$, define  $min_i(A)$  to be
the least   value of $j$ such $A_{j,i}$ is non-zero. A column $i$ of
$A$ is said to be {\em improper} if it satisfies one of the
following two cases: (1) $csum_i(A)\geq 2$; (2) for $1<i\leq
dim(A)$,  we have $csum_i(A)=1$, $rsum_i(A)=0$, and
$min_i(A)<min_{i-1}(A)$. Otherwise, column $i$ is said to be {\em
proper}. The matrix $A$ is said to be {\em improper} if there  is at
least one improper column in $A$; otherwise, the matrix $A$ is said
to be {\em proper}. Given an improper matrix $A\in \mathcal{M}_n$,
 define $index(A)$ to be the  largest  value   $i$ such that
 column
 $i$ is improper. Denote by $\mathcal{PM}_n$ the set of proper
 matrices in $\mathcal{M}_n$.

\begin{example}
Consider the following matrix $A\in \mathcal{M}_8$:
$$
A=\begin{bmatrix}
1 &0  &1  &0 &0& 1   \\
0 & 1 &0  & 1 &1& 0  \\
0 & 0& 0 & 0 &0 &0  \\
0 & 0 & 0& 0 & 0 &1  \\
0 & 0 & 0& 0 & 0& 0  \\
0 & 0& 0 &0 &0& 1  \\
\end{bmatrix}.
$$
We have $dim(A)=6, min_1(A)=1, min_2(A)=2, min_3(A)=1, min_4(A)=2,
min_5(A)=2, min_6(A)=1 $.  There are two improper columns, that is,
columns $3$  and  $6$.  Hence,  we have $index(A)=6$.
\end{example}

Denote by $\mathcal{PM}_{n,k}$ the set of matrices $A\in
\mathcal{PM}_n$ with $rsum_1(A)=k$ and $\mathcal{I}_{n,k}$ the set
of matrices $A\in \mathcal{I}_n$ with $rsum_1(A)=k$. Dukes and
Parviainen \cite{Duck} constructed a recursive  bijection between
the set $\mathcal{I}_n$ and the set of ascent sequences of length
$n$.    Under their bijection, they showed that the number of upper
triangular matrices $A\in \mathcal{I}_{n}$ with $rsum_1(A)=k$ is
equal to the number of ascent sequences of length $n$ with $k$
zeros, which implies that the cardinality of $\mathcal{I}_{n,k}$ is
also given by $p_{n,k}$. In this paper, we will prove Conjecture
\ref{conjecture} by showing that the generating function for the
number of matrices in $\mathcal{I}_{n,k}$ is given by the right-hand
side of Formula (\ref{identity}).

  In Section 2, we present a parity reversing and weight
preserving involution on the set  $\mathcal{M}_n\setminus
\mathcal{PM}_n$.   In Section 3, we  prove that the right-hand side
of Formula (\ref{identity}) is the generating function for the
number of matrices in $\mathcal{PM}_{n,k}$.   Moreover,  we show
that there is a bijection between the set $\mathcal{PM}_{n,k}$ and
the set $\mathcal{I}_{n,k}$ in answer to Conjecture
\ref{conjecture}.

\section{A parity reversing and weight preserving  involution}

In this section, we will construct a parity reversing and weight
preserving  involution on   the set $\mathcal{M}_n\setminus
\mathcal{PM}_n$. Before constructing the involution, we need some
definitions.

Given a matrix $A\in \mathcal{M}_n$, the {\em weight } of the matrix
 $A$ is assigned by
   $ z^{rsum_1(A)}$.
    Given  a subset $S$ of  the set $\mathcal{M }_n$, the {\em weight} of  $S$, denoted by $W(S)$,  is the  sum of the weights
 of all matrices in $S$.   We define the {\em parity} of the matrix $A$ to be
 the parity of the number $n-dim(A)$. Denote by $\mathcal{EM}_n$ (resp. $\mathcal{OM}_n$ ) the
 set of matrices in
 $\mathcal{M}_n$ whose parity are even (resp. odd).

 \begin{theorem}\label{involution}
There is a parity reversing  and weight preserving involution $\Phi$
on the set $\mathcal{M}_n\setminus\mathcal{PM}_n$. Furthermore, we
have
$$
W(\mathcal{EM }_n)-W(\mathcal{OM }_n)=W(\mathcal{PM}_n).
$$
\end{theorem}
\pf Given a matrix $A\in \mathcal{M}_n\setminus\mathcal{PM}_n $,
suppose that  $index(A)=i$.  We now have two cases. (1) We have
$csum_i(A)\geq 2$. (2) We have $1<i\leq dim(A)$, $csum_i(A)=1$,
$rsum_i(A)=0$, and $min_{i}(A)<min_{i-1}(A)$.

For Case (1), we obtain a new matrix $\Phi(A)$ from the matrix $A$
in the following way.  In A, replace the entry in row $min_i(A)$ of
column $i$ with zero. Then, insert a new zero row between row $i$
and row $i+1$ and insert a new column between column $i$ and $i+1$.
Let the new column be filled with all zeros except that the  entry
in row $min_i(A)$   is filled with $1$. In this case, we have
$\Phi(A)\in \mathcal{M}_n\setminus\mathcal{PM}_n $ with
$index(\Phi(A))=i+1$, $dim(\Phi(A))=dim(A)+1$ and
$rsum_1(\Phi(A))=rsum_1(A)$.

For Case (2), we may obtain a new matrix $\Phi(A)$ by reversing the
construction for Case  (1) as follows.  In $A$, replace the entry in
row $min_i(A)$ of column $i-1$ with  1. Then remove column $i$ and
row $i$. In this case, we have $\Phi(A)\in
\mathcal{M}_n\setminus\mathcal{PM}_n $ with $index(\Phi(A))=i-1$,
$dim(\Phi(A))=dim(A)-1$ and $rsum_1(\Phi(A))=rsum_1(A)$.

In both cases, the map $\Phi$ reverse the  parities   and preserve
the
  the weights of the matrices.  Hence, we obtain a desired
 parity reversing and weight preserving  involution on the set
$\mathcal{M}_n\setminus\mathcal{PM}_n$.   Note that if a matrix
$A\in
 \mathcal{M}_n$ is proper, then    there is exactly one $1$ in
 each column. Hence for each $A\in
 \mathcal{PM}_n$,  the parity of $A$ is even.
By applying  the involution, we can deduce that
$$ W(\mathcal{EM }_n)-W(\mathcal{OM }_n)=W(\mathcal{PM}_n).
$$

\qed

\begin{example}
Consider the following two matrices in $\mathcal{M}_6$:
$$
A=\begin{bmatrix}
1 &1   &0  & 0    \\
0 & 1   & 1 & 0  \\

0 & 0 & 1 &  0  \\
0 &  0 &0 & 1  \\
\end{bmatrix},
\,\,\, B= \begin{bmatrix}
1 &1   &0  &0& 0    \\
0 & 1   &0& 1 & 0  \\

0 & 0 & 1 &0&  0  \\
0 & 0 & 0 &0&  0  \\

0 &  0 &0 &0 &1  \\
\end{bmatrix}.
$$

For matrix $A$,  we have $index(A)=3$. Thus we have
$$
 \Phi(A)= \begin{bmatrix}
1 &1   &0  &\bf{0}& 0    \\
0 & 1   &0& \bf{1} & 0  \\

0 & 0 & 1 &\bf{0}&  0  \\
\bf{0} &\bf{ 0} & \bf{0} &\bf{ 0} &  \bf{0 } \\

0 &  0 &0 &\bf{0} &1  \\
\end{bmatrix},
$$
where the new inserted row and column are illustrated in bold.

For matrix $B$, we have $index(B)=4$.  Thus we have
$$
\Phi(B)=\begin{bmatrix}
1 &1   &0  & 0    \\
0 & 1   & 1 & 0  \\

0 & 0 & 1 &  0  \\
0 &  0 &0 & 1  \\
\end{bmatrix}.
$$
In fact, we have $\Phi(A)=B$ and $\Phi(B)=A$.
\end{example}

\section{Proof of  Conjecture \ref{conjecture}}
In this section, we will  show that the right-hand side of Formula
\ref{identity} is the generating function for the number of matrices
in $\mathcal{PM}_{n,k}$. Furthermore, we prove that there is a
bijection between the set $\mathcal{PM}_{n,k}$ and the set
$\mathcal{I}_{n,k}$, which implies Conjecture \ref{conjecture}.

Let
$$
A(t,z)= \sum_{n\geq 0}\prod_{i=1}^{n}(1-(1-t)^{i-1}(1-zt)).
$$
With the assumption that the empty product is as usual taken to be
$1$,    we have
$$
 A(t,z)=1+\sum_{n\geq 1}\prod_{i=1}^{n}
\sum_{j=1}^{i-1} ({i-1\choose j}+z{i-1\choose j-1})(-1)^{j-1}t^{j}.
$$
Define $A_n(z)$ to be the coefficient of $t^n$ in $A(t,z)$ for
$n\geq 1$, that is
\begin{equation}\label{A_n}
A(t,z)=1+\sum_{n\geq 1}A_n(z)t^n.\end{equation}
  Thus we have
$$
A_n(z)= \sum_{d=1}^{n}\sum_{ n_1+n_2+\ldots+n_d=n
}(-1)^{n-d}\prod_{j=1}^{d}({j-1\choose n_j}+z{j-1\choose n_j-1}),
$$
where the second summation is over all  compositions
$n_1+n_2+\ldots+n_d=n$ such that $n_j\geq 1$ for $j=1,2,\ldots, d$.
\begin{lemma}\label{A_n(z)}
For $n\geq 1$, we have
$$
A_n(z)=W(\mathcal{EM }_n)-W(\mathcal{OM }_n).
$$
\end{lemma}
\pf  Let $\mathcal{M}(n_1, n_2, \ldots, n_d)$ be the set of matrices
in $\mathcal{M}_n$ with $d$ columns   in which the column sum of
column $j$ is equal to $n_j$ for all $1\leq j\leq d$. In order to
get a matrix $A\in \mathcal{M}(n_1, n_2, \ldots, n_d)$, we should
choose $n_j$ places in column $j$ form $j$ places to arrange $1's$
for all $1\leq j\leq d$. we have two cases. (1) If $A_{1,j}=0$, then
we have ${j-1\choose n_j}$ ways to arrange $1$'s in column $j$. (2)
If $A_{1,j}=1$, then we have ${j-1\choose n_j-1}$ ways to arrange
the remaining $1$'s in column $j$. In the former case, column $j$
contributes $1$ to the weight of $A$. While in the latter case,
column $j$ contributes $z$ to the weight of $A$. Altogether, column
$j$ contributes ${j-1\choose n_j}+z{j-1\choose n_j-1}$ to the weight
of $\mathcal{M}(n_1, n_2, \ldots, n_d)$, which implies that $$
W(\mathcal{M}(n_1, n_2, \ldots, n_d))=\prod_{j=1}^{d}({j-1\choose
n_j}+z{j-1\choose n_j-1}).$$  It is clear that the parity of each
matrix in $\mathcal{M}(n_1, n_2, \ldots, n_d)$ is the parity of the
number $n-d$. When $d$ ranges from $1$ to $n$ and $n_1, n_2, \ldots,
n_d$ range over all compositions $n_1+n_2+\ldots+n_d=n$  such that
$n_j\geq 1$ for all $1\leq j\leq d$, we
   get the desired
result. \qed

Denote by $a_{n,k}$ the cardinality of the set $\mathcal{PM}_{n,k}$.
Assume that $a(0,0)=1$.

\begin{theorem}\label{A(t,z)}
 We have $$A(t,z)= \sum_{n\geq 0, k\geq
0}a_{n,k}z^kt^n=  \sum_{n\geq
0}\prod_{i=1}^{n}(1-(1-t)^{i-1}(1-zt)).$$
\end{theorem}
\pf  Combining Theorem  \ref{involution} and Lemma \ref{A_n(z)}, we
deduce that $A_n(z)=W(\mathcal{PM}_n)$ for $n\geq 1$.  Note that
$W(\mathcal{PM}_n)=\sum_{k=1}^{n}a_{n,k}z^k$  for $n\geq 1$.  Hence
we have  $$A(t,z)=1+\sum_{n\geq 1}A_n(z)t^n= \sum_{n\geq 0, k\geq
0}a_{n,k}z^kt^n, $$ which implies the desired result. \qed

From Theorem \ref{A(t,z)},   in order to prove Conjecture
\ref{conjecture}, it suffices to prove that $a_{n,k}=p_{n,k}$. In  a
matrix $A$, the operation of adding column $i$ to column  $j$ is
defined by increasing  $A_{k,j}$ by $A_{k,i}$  for each
$k=1,2,\ldots, dim(A)$. Note that a matrix $A\in \mathcal{M}_n$ is
proper if and only if it satisfies
\begin{itemize}
\item each column has exactly one $1$;
\item if $rsum_i(A)=0$, then we have $min_i(A)\geq min_{i-1}(A)$ for
$2\leq i\leq dim(A)$.
\end{itemize}
This observation will be  essential in the construction  of the
bijection between the set $\mathcal{PM}_{n,k}$ and the set
$\mathcal{I}_{n,k}$.

\begin{theorem}\label{bijection}
 There is  a bijection between the set $\mathcal{PM}_{n,k}$
and the set $\mathcal{I}_{n,k}$.
\end{theorem}

\pf Let $A$ be a matrix in the $\mathcal{PM}_{n,k}$, we can
construct  a matrix $A'$ in $\mathcal{I}_{n,k}$.  If there is no
zero rows in $A$, then we do nothing for $A$ and let $A'=A$. In this
case, the resulting matrix $A'$ is contained in $\mathcal{I}_{n,k}$.
Otherwise, we can construct a new upper triangular matrix  $A'$ by
the following {\em removal}  algorithm.
\begin{itemize}
\item Find the  least value $i$ such that row $i$ is a zero
 row. Then we obtain a new  upper triangular matrix by  adding column $i$
to  column  $i-1$ and remove column $i$ and row $i$.
\item Repeat the above procedure for the resulting matrix until
there is no zero row  in the resulting matrix.
\end{itemize}

 Clearly, the obtained matrix $A'$ is a matrix in
$\mathcal{I}_n$. Since the algorithm preserves the  sums of entries
in each non-zero rows of $A$, we have $rsum_1(A')=rsum_1(A)$. Hence,
the resulting matrix $A'$ is in $\mathcal{I}_{n,k}$.

Conversely, we can construct a matrix in $\mathcal{PM}_{n,k}$ from a
matrix in $\mathcal{I}_{n,k}$. Let $B$ be a matrix in the
$\mathcal{I}_{n,k}$. If the sum of entries in each  column is equal
to $1$, then we do nothing for $B$ and let $B'=B$. Otherwise, we can
construct a new upper triangular matrix  $B'$  by the following {\em
addition} algorithm.
\begin{itemize}
\item Find the  largest  value $i$ such that $csum_i(B)\geq 2$. Then we obtain a new  upper triangular matrix
by     decreasing    the entry in row $max_i(B)$ of column $i$ by
$1$, where $max_i(B)$ is defined to be the largest value $j$ such
that $B_{j,i}$ is non-zero.  Since $B$ is upper triangular, we have
$max_i(B)\leq i$.
\item Insert  one column between column $i$ and column $i+1$ and one zero
row between row $i$ and row $i+1$ such that the new inserted column
is filled with all zeros except that the entry on row $max_i(B)$ is
filled with $1$.
\item Repeat the above procedure for the resulting matrix until
there is no column  whose column sum is lager than $1$.
\end{itemize}
Clearly, the obtained matrix $B'$ is a matrix in $\mathcal{M}_n$.
From the construction of the above algorithm we know that the column
sum of each column  in $B'$ is equal to $1$. Furthermore, if row $j$
is a zero row, then we must have $min_j(B')\geq min_{j-1}(B')$.
Thus, the resulting matrix $B'$ is proper.
   Since the algorithm preserves the sums of entries in each
non-zero row of $B$,  we have   $rsum_1(B')=rsum_1(B)$. Hence, the
resulting matrix $B'$ is in $\mathcal{PM}_{n,k}$. This completes the
proof.

 \qed

\begin{example}
Consider a matrix $A\in \mathcal{PM}_{6,3}$. By applying the removal
algorithm, we get
$$
A=\begin{bmatrix}
1 &1   &\bf{0 } & 1 &0&0  \\
0 & 0   & \bf{1} & 0 &0&0 \\
{\bf0} & \bf{0}   & \bf{0} & \bf{0} &\bf{0}&\bf{0} \\
0 & 0   & \bf{0} & 0 &1&1 \\
0 & 0   & \bf{0} & 0 &0&0 \\
0 & 0   & \bf{0} & 0 &0&0 \\
\end{bmatrix}
\leftrightarrow  \begin{bmatrix}
1 &1   & 1 &\bf{0}&0  \\
0 & 1  & 0 &\bf{0}&0 \\

0 & 0  & 0 &\bf{1}&1 \\
\bf{0} & \bf{0}  & \bf{0 }&\bf{0}&\bf{0 }\\
0 & 0  & 0 &\bf{0}&0 \\
\end{bmatrix}
\leftrightarrow  \begin{bmatrix}
1 &1   & 1  &\bf{0}  \\
0 & 1  & 0  &\bf{0} \\

0 & 0  & 1  &\bf{1} \\

\bf{0} & \bf{0}  & \bf{0}  &\bf{0} \\
\end{bmatrix}
\leftrightarrow  A'=\begin{bmatrix}
1 &1   & 1     \\
0 & 1  & 0    \\
0 & 0  & 2    \\
\end{bmatrix},
$$
where the removed rows and columns are illustrated in bold at each
step of the removal algorithm. Conversely, given $A'\in
\mathcal{I}_{6,3}$, by applying addition algorithm, we can get $A\in
\mathcal{PM}_{6,3}$, where the inserted new rows and columns are
illustrated in bold at each step of the addition algorithm.
\end{example}

 Combining Theorems \ref{involution}, \ref{A(t,z)} and \ref{bijection},  we obtain
a combinatorial proof of Conjecture \ref{conjecture}. Note that
specializing $z=1$ implies a combinatorial proof of Formula
(\ref{pt}), which was proved by Bousquet-M$\acute{e}$lou et al.
\cite{melon} by using functional equations and the Kernel method.
 \vskip 5mm

\noindent{\bf Acknowledgments.}   The   author was supported by the
National Natural Science Foundation of China (no.10901141).


TITLE: How are the definitions of a coherent state equivalent?
QUESTION [11 upvotes]: I am trying to understand coherent states. As far as I could find there are three equivalent definitions and in general many sources start from a different one, still I fail to see their equivalence. I restate the definitions and their equivalences given in the Wikipedia page:

Eigenstate of annihilation operator: $$a|\alpha \rangle =\alpha|\alpha \rangle$$
Displacement operator of the vacuum: $$ |\alpha \rangle =e^{\alpha a^{\dagger}-\alpha^{*} a}|0 \rangle $$
State of minimal Uncertainty: $$ \Delta X= \Delta P = \frac{1}{\sqrt{2}} $$

I fail to see how they are the same!
Can someone please explain how to derive these from one another?

REPLY [13 votes]: Refer to the nice complement on coherent states in the book  by Cohen-Tannoudji, Diu and Laloë, volume 1. It starts off defining coherent states as neither of the ones you mention, and then derives all properties.
To answer the question, if you start with definition 2, you can easily show 1, and then from 2, 3. First expand the exponential using Baker-Campbell-Hausdorff formula:
$$
e^{\alpha a^\dagger -\alpha^* a}=e^{\alpha a^\dagger}e^{-\alpha^* a}e^{\frac{-1}{2}|\alpha|^2[a^\dagger,-a]}
$$
and let it act on the vacuum state $|0\rangle$ to get
$$
|\alpha \rangle =  e^{-|\alpha|^2/2}e^{\alpha a^\dagger}e^{-\alpha^* a}|0\rangle \\
= e^{-|\alpha|^2/2}e^{\alpha a^\dagger}|0\rangle \\
= e^{-|\alpha|^2/2} \sum_{n=0}^{\infty}\frac{\alpha^n}{\sqrt{n!}} |n\rangle
$$
Now that you have the expression for $|\alpha \rangle$ in terms of states you already know, you can operate $a$ on it to find that it is indeed an eigenstate of the lowering operator, showing that definition 2 implies definition 1.
Property 3 follows from finding $\langle X^2 \rangle$ and $\langle P^2 \rangle$ for this state, by expressing the operators in terms of $a$ and $a^\dagger$, a fairly standard exercise.


TITLE: Integral of $\cos(x)\exp(-x^2/2\sigma^2)$
QUESTION [2 upvotes]: I have to evaluate $<cos(x)>$ with $x$ distributed according to $Q^{-1}e^-{\frac{x^2}{2\sigma^2}}$.
I have gone this far:
$$<cos(x)>=\frac{\int\limits_{-\infty}^\infty \cos (x)  Q^{-1}e^{-\frac{x^2}{2\sigma^2}} \mathrm{d}x}{\int\limits_{-\infty}^\infty Q^{-1}e^{-\frac{x^2}{2\sigma^2}}\mathrm{d}x}=\sigma\sqrt{2\pi}\int\limits_{-\infty}^\infty \cos (x)  e^{-\frac{x^2}{2\sigma^2}}\mathrm{d}x$$
How to deal with this integral? I considered partial integration, but that seems impossible because I would have to evaluate $\cos(x)$ at infinity.

REPLY [2 votes]: Since $\sin(x)$ is an odd function, we have $\int_{-\infty}^{\infty}\sin(x)\exp\{-\frac{x^2}{2\sigma^2}\}dx = 0$. Therefore, after simple algebra
$$\int_{-\infty}^{\infty}\cos(x)\exp\{-\frac{x^2}{2\sigma^2}\}dx = \int_{-\infty}^{\infty}\exp\{i x\}\exp\{-\frac{x^2}{2\sigma^2}\}dx \\
= e^{-\frac{\sigma^2}{2}} \int_{-\infty}^{\infty}\exp\{-\frac{1}{2\sigma^2}(x-i\sigma)^2\}dx\\
= \sqrt{2\pi}\sigma e^{-\frac{\sigma^2}{2}} $$


TITLE: How do I prove when $2\sin^2x$ is greater than $\sin x $?
QUESTION [1 upvotes]: I need to show when
$2\sin^2x \geq \sin x $ for $x$ between $0$ and $2\pi$.
I see that for values $\pi/6$ and $5\pi/6$ and after $\pi$. How do I prove or reason out these answers?

REPLY [1 votes]: Consider $f(x) := 2\sin^2(x) - \sin(x)$. Essentially, your quesion boils down to finding where $f(x) \ge 0$. We will first find where $f(x)$ is zero. As you have already observed,
$$f(x) = 0 \Rightarrow 2\sin^2(x) - \sin(x) = 0 \Rightarrow (2\sin(x) - 1)\sin(x) = 0$$
Which means that $x = 0, \pi/6, 5\pi/6, \pi$, and $2\pi$ are our "critical points". Since these are the only points where $f$ is zero, the continuity of $f$ implies that it must be strictly positive or negative on the intervals $(0, \pi/6)$, $(\pi/6, 5\pi/6)$, $(5\pi/6, \pi)$, and $(\pi, 2\pi)$. Simply choose one "test point" inside these intervals, and you will know immediately whether each respective interval is positive or negative.
You'll find that both $[\pi/6, 5\pi/6]$ and $[\pi, 2\pi]$ are positive (we have closed brackets here because we allow $f$ to be equal to zero as well). Hence, your inequality is satisfied on $[\pi/6, 5\pi/6]$ and $[\pi, 2\pi]$.


TITLE: Show $a_n=\frac{3^n}{n!}$ is decreasing and bounded below
QUESTION [3 upvotes]: I want to show $a_n=\frac{3^n}{n!}$ is decreasing and bounded below.
I tried with $\frac{a_{n+1}}{a_n}$, but it only got me $\frac{3}{n+1}$ after cancel out everything and I can't determine this to be less than 1, never to say the bounded below part.

REPLY [0 votes]: Let $n\geq 2$. By induction,  $$a_{n+1}-a_n=\frac{3^{n+1}}{(n+1)!}-\frac{3^n}{n!}=\frac{3}{n+1}a_n-\frac{3}{n}a_{n-1}\leq \frac{3}{n}(a_{n}-a_{n-1})\leq 0.$$


text:
\section{Howe curves and their superspeciality}\label{sec:Howe}
In this section,
we recall the definition of Howe curves, show that they are canonical,
and give a computational criterion for their superspeciality.

Let $K$ be an algebraically closed field of characteristic $p\neq 2$.
A \emph{Howe curve} over $K$ is a curve which is isomorphic to the desingularization of
the fiber product $E_1 \times_{{\bbP}^1} E_2$ of two genus-$1$ double covers
$E_i\to {\bbP}^1$ ramified over $S_i$, where
each $S_i$ consists of 4 points and where $|S_1\cap S_2|=1$.

Given a Howe curve, there is an automorphism of $\bbP^1$ that takes the common ramification point
of the two genus-$1$ double covers to infinity. Then the curves $E_i$ can be written
$w^2 = f_1$ and $z^2 = f_2$ for separable monic cubic polynomials $f_i\in K[x]$ that
are coprime to one another, where $x$ generates the function field of~$\bbP^1$.

\begin{lemma}\label{HoweIsCanonical}
Every Howe curve is a canonical curve of genus $4$.
\end{lemma}
\begin{proof}
Let $H$ be a Howe curve, normalized as above so that it is given as the fiber product
of $w^2 = f_1$ and $z^2 = f_2$ for coprime separable monic cubic polynomials $f_1$ and~$f_2$.
For each $i$ let $f_i^{(\rm h)}\coloneqq y^3 f_i(x/y)\in K[x,y]$ be the homogenous cubic obtained
from $f_i$, and let $H'$ be the curve defined in $\bbP^3=\Proj K[x,y,z,w]$ by
\begin{align*}
z^2-w^2 &= q(x,y)\\
z^2y &= f_1^{(\rm h)}(x,y),
\end{align*}
where $q(x,y)$ is the quadratic form
\[
q(x,y) = (f_1^{(\rm h)}(x,y)-f_2^{(\rm h)}(x,y))/y.
\]
Note that $H'$ and $E_1\times_{\bbP^1} E_2$ are isomorphic if
the locus $y=0$ is excluded.
It is straightforward to see that $H'$ is nonsingular,
since $f_1$ and $f_2$ are separable and are coprime.
Hence $H$ and $H'$ are isomorphic to one another (cf.\,\cite[Proposition~II.2.1]{Sil}).

It is well-known that any nonsingular curve defined by
a quadratic form and a cubic form in $\bbP^3$
is a canonical curve of genus $4$ \cite[Example~IV.5.2.2]{Har}.
\end{proof}

To study the superspeciality of Howe curves, we first look at the decomposition of
their Jacobians. Let $f_1$ and $f_2$ be coprime separable monic cubic polynomials, as above.
Let $f = f_1 f_2$ and consider the hyperelliptic curve $C$ of genus $2$ defined by
$u^2 = f.$
By~\cite[Theorem~2.1]{Howe}, there exist two isogenies
\begin{align*}
\varphi&\colon  J(H) \longrightarrow E_1 \times E_2 \times J(C)\\
\psi&\colon E_1 \times E_2 \times J(C) \longrightarrow J(H)
\end{align*}
such that $\varphi\circ\psi$ and $\psi\circ\varphi$ are both multiplication by $2$.

Suppose now that the characteristic $p$ of $K$ is an odd prime.
Then
$\psi\circ\varphi$ is an automorphism of the $p$-kernel of $J(H)$
and
$\varphi\circ\psi$ is an automorphism of the $p$-kernel of $E_1 \times E_2 \times J(C)$,
so $J(H)[p]$ and $E_1[p] \times E_2[p] \times J(C)[p]$ are isomorphic.
Hence $H$ is superspecial if and only if $E_1$ and $E_2$ are supersingular and $C$ is superspecial.

Now we recall a criterion for the superspeciality of $C$.
Let $\gamma_i$ be the coefficient of $x^i$ in $f^{(p-1)/2}$, and set
\[
a=\gamma_{p-1},\quad
b=\gamma_{2p-1},\quad
c=\gamma_{p-2}\quad \text{and}\quad
d=\gamma_{2p-2}.
\]
Let $M$ be the matrix
\begin{equation}\label{Cartier-Manin matrix}
M \coloneqq \begin{pmatrix}
a^p & c^p \\
b^p & d^p
\end{pmatrix}.
\end{equation}
Then $M$ is a Cartier--Manin matrix for $C$, that is, there is a basis for
$H^0(C,\Omega_C^1)$ so that left multiplication by $M$ represents the (semi-linear)
action of the Cartier operator; here $\Omega_C^1$ is the sheaf of differential $1$-forms on $C$.
(For information about Cartier--Manin matrices, see~\cite{AH}, which addresses issues with
earlier literature, including the standard reference~\cite[\S 2]{Yui}.)

\begin{lemma}\label{lem:ssp}
Let $H$ be a Howe curve as above.
Then $H$ is superspecial if and only if $E_1$ and $E_2$ are supersingular and $a=b=c=d=0$.
\end{lemma}

\begin{proof}
We already noted that $H$ is superspecial if and only if $E_1$ and $E_2$
are supersingular and $C$ is superspecial. But $C$ is
superspecial if and only if the Cartier operator acts trivially on $H^0(C,\Omega_C^1)$
\cite[Theorem~4.1]{Nygaard}.
\end{proof}

config: arxiv


TITLE: Logistic growth of a population
QUESTION [0 upvotes]: while studying for my math exam coming up, I stumbled upon this exercise.
A certain product is sold on a market with 1 000 000 potential customers. We assume that the number of people p that have bought the product is growing logistically. So, the function p(t) (where time t is measured in years) satisfies a differential equation of the form
$$\frac{dp}{dt}= \frac{k}{N} p(N - p)$$$, with N the value of p in the long run and k some positive number. It is expected that in three years’ time, a quarter of the potential customers will have acquired the product, that in five years’ time, half of them will and in the long run everybody will.
If I understand correctly we can say that
p(3) = 1/4 * 1 000 000 ,
p(5) = 1/2 * 1 000 000 ,
N = 1 000 000
The question asked is :
Find the equation of the function p(t)
I can't seem to find the right solution
Can somebody enlighten me?
Many thanks!

REPLY [1 votes]: To solve the differential equation, rewrite it as
$$kdt = {dp\over p} + {dp\over{N - p}}.$$
By integrating and re-arranging we get $p = N/(1 + ce^{-kt})$, where $c$ is a constant. The values of $c$ and $k$ can then be found from the information that $p(3) = N/4$ and $p(5) = N/2$.


TITLE: What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?
QUESTION [0 upvotes]: Let $L = L((00 + 1)^∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$?

In this context "$+$" means "$\cup$". So the language $L$ is all the words above $\Sigma = \{ 00,1 \}$. Right?
Now, I think I don't understand something fundamental here because take for example $w = 00001 \in L$. What is $h^{-1}(w)?$

REPLY [2 votes]: By definition, $h^{-1}(w)$ is the set: $$\{v \in \{a,b\}^* \mid h(v) = w\}$$
Depending on your definitions, this can be an abuse of notation, because $h^{-1}$ might not be a mapping. However, it is convenient to omit the inner braces in the formally more correct $h^{-1}(\{w\})$.
As to the set itself: Because there is no possibility for $h$ to yield three consecutive zeroes, it follows that $h^{-1}(w)$ is empty.
Similarly, there is no possibility for an image of $h$ to have three consecutive ones.
With this information, can you identify the words, if indeed there exist any, that can occur as an image of $h$?
This is the key to the solution; it amounts to describing the set: $$\operatorname{im} h \cap L$$
and subsequently to find its preimage under $h$.


TITLE: Analytic approach to geodesic connectedness in Semi-Riemannian manifolds
QUESTION [0 upvotes]: Can you point out a reference (or references) that deal with analytical methods (rather than methods from differential geometry) for the study of geodesic connectedness on Semi-Riemannian manifolds?

REPLY [1 votes]: I'd recommend taking a look at the following monograph and surveys (and at the references cited therein):

Masiello, Antonio, Variational methods in Lorentzian geometry, Pitman Research Notes in Mathematics Series. 309. Harlow, Essex: Longman Scientific & Technical. New York, NY: Wiley. xix, 175 p. (1994). ZBL0816.58001.
Masiello, Antonio, Applications of calculus of variations to general relativity, Casciaro, B. (ed.) et al., Recent developments in general relativity. Proceedings of the 13th Italian conference on general relativity and gravitational physics, Cala Corvino-Monopoli, (Bari), Italy, September 21-25, 1998. Milan: Springer. 173-195 (2000). ZBL0995.83015.
Masiello, Antonio, Some variational problems in semi-Riemannian geometry, Frauendiener, Jörg (ed.) et al., Analytical and numerical approaches to mathematical relativity. Papers based on the presentation at the 319th WE-Heraeus seminar `Mathematical relativity: New ideas and developments’, Bad Honnef, Germany, March 1--5, 2004. With a foreword by Roger Penrose. Berlin: Springer (ISBN 3-540-31027-4/pbk). Lecture Notes in Physics 692, 51-77 (2006). ZBL1100.58006.
Candela, Anna Maria; Sánchez, Miguel, Geodesics in semi-Riemannian manifolds: geometric properties and variational tools, Alekseevsky, Dmitri V. (ed.) et al., Recent developments in pseudo-Riemannian geometry. Zürich: European Mathematical Society (ISBN 978-3-03719-051-7/pbk). ESI Lectures in Mathematics and Physics, 359-418 (2008). ZBL1204.53034.


TITLE: Complex Math- Programming question
QUESTION [0 upvotes]: You have a matrix of N rows and M columns.
There are 3 possible outcomes in every position.
A) There can be a dot, which means that you can go on this position
B) There can be a plus sign (+) , which means you went to see an autoshow
C) There can be a ladder sign, which represents the not available position to proceed in.
Something like this : http://prntscr.com/8d2zrl
You start from position 1,1 (upper left corner) and your goal is to went to most possible autoshows (plus signs) by going to position N, M (lower right corner, which is a Pit-stop (a turnaround) to return back to position 1,1.
Something like this : http://prntscr.com/8d31go
The solution should work for every given matrix of any dimensions.
When you are going from position 1,1 to position N,M you can only go down or right, and when you are going back (from position N,M to position 1,1) you can only go up or left. On the way back you are allowed to reuse positions you used on the way down, but there is no additional reward (autoshow) if you picked it up previously. You can assume that it will always be possible to reach (N,M) from (1,1) (and hence to get back).

REPLY [1 votes]: Michael's answer can be extended to the whole tour, using the idea that any path from (1,1) to (N,M) to (1,1) can be reversed. (The reversal caters to the updating necessary when you pick up a reward and update the square it is on.) But it needs to be extended a bit, because at the start there are no previous values. You calculate those as you go.
Here is how it works, by stepping the path backwards. There are (at most) two squares from which you can reach (1,1): (1,2) and (2,1). Both of them pick up any reward at (1,1). So which one you pick is immaterial (so far).
At the next layer, there are (at most) three squares at a distance of 2 from (1,1): (1,3) --- in which case you must go to (1,2) and pick up any reward there; (3,1) --- going to (2,1) and picking up the reward at (2,1); (2,2) --- in which case you have the choice of going to (1,2) or (2,1). Pick the one with the larger reward and make a record of which way you went, as well as the remaining rewards at each node.
At the next layer, there are four squares a distance of 3 from (1,1): (1,4), (2,3), (3,2) and (4,1). From (4,1) you can only go to (3,1), adding the reward at (3,1) to the additional rewards you can pick up when moving from (3,1) to (1,1). Similarly you treat (1,4). From (3,2) and (2,3) you have two choices. Pick the one with the larger reward (including what you pick up at the next step --- (3,1) or (2,2) from (3,2), (2,2) or (1,3) from (2,3). Continue this idea until you reach (N,M). Update the rewards fro the way back to (1,1) and repeat the procedure from (N,M) back to (1,1). Once you have the complete path, reverse the steps, as stated at the outset.


TITLE: How to determine long-run probability using conditional probability?
QUESTION [1 upvotes]: How to determine long-run probability on a calculator and manually?
For example:
Ben plays a tennis match every day.
If he wins on one particular day, the probability that he wins the next day is 0.8
If he loses one day, the probability that he loses the next day is 0.6
The long-run probability that Ben wins a match is:
How to calculate this "by hand" and "by a calculator"
What I have gathered using my knowledge on conditional probability:

$P(w_2|w_1) = 0.8$
$P(w_2'|w_1')= 0.6$

Trying to find P(Ben wins a match in the long run) = ?
I know the answer, but am unsure how to get there.

REPLY [3 votes]: Let $W_t$ be win today, $W_y$ be win yesterday, $L_t$ be lose today and $L_y$ be lose yesterday.
We have $P(W_t)=P(W_t|W_y)\cdot P(W_y)+P(W_t|L_Y)\cdot P(L_Y)$.
From the given information, this becomes $P(W_t)=.8P(W_y)+.4P(L_y)$.
If the probabilities are to be stable (long-term), we should have $P(W_y)=P(W_t)$ and $P(L_y)=P(L_t)$.
Thus $P(W_t)=.8P(W_t)+.4P(L_t)$.  Also $P(W_t)+P(L_t)=1$, which should be enough information to solve the problem.
Another approach would be to set up a Markov transition matrix, and find the stable probability vector.


TITLE: Analyticity of Laplace transform
QUESTION [3 upvotes]: Let $f(x)$ be a bilateral Laplace transform of a measure $\mu$:
$$
f(x)=\int_{-\infty}^{+\infty} e^{-xt} d\mu(y).
$$
Suppose that $f(x)$ converges absolutely in $(a,b)$, and $(a,b)$ do not contain the origin.
It is always true that $f(x)$ is analytic in $(a,b)$? Or it is true just for finite measure $\mu$?
Moreover, if the measure $\mu$ is finite, then $(a,b)$ must contain the origin?
Thank you!

REPLY [1 votes]: The following references investigate the Moment Generating Function (finite measure):
There is a classical reference for the case where the interval $(a,b)$ contains the origin and a recent extension to the case of a general open interval $(a,b)$. This paper that gives a nice overview and proves the converse to Curtiss's theorem in the general case.
Refs:
Curtiss, J.H., 1942. A note on the theory of moment generating functions, 1,
Ann. of Math. Statist, 13 (4) : 430-433.
Mukherjea, A., Rao, M. and Suen, S., 2006. A note on moment generating
functions, Statistics & Probability Letters, 76 : 1185-1189.
P. Chareka. \The converse to Curtiss theorem for one-sided moment generating functions" (2008). arXiv:
0807.3392 [quant-ph].


TITLE: Prerequisites for studying Introduction to probability theory by William Feller,vol 1 & vol 2?
QUESTION [0 upvotes]: I know calculus, real analysis, discrete mathematics and applied probability, and want to know what else do I need to know to self-study both the probability books by Feller?

REPLY [0 votes]: Calculus - specifically integration - is also necessary to understand Feller. Some people cover this is applied probability, but some do not.


TITLE: How to find all the elements of the group $S_4$
QUESTION [0 upvotes]: I know how to find all the elements up till $S_3$ but for $S_4$ I am not sure how to do that systematically.

REPLY [1 votes]: Georege Law's answer tells us how to list them by various types. There is an alternative way (based on your question).
As you have listed already all permutations of $1,2,3$, we can use that to get the permutations of $1,2,3,4$.
Write out a single permutation of 1,2,3 in a piece of paper well spaced out.
Now insert 4 at front, and then at all gaps, and then finally at the end. There are 4 possible insertion slots. Each leads to a new permutation of 4 symbols.
Example from 3 1 2
4 3 1 2;  3 4 1 2;  3 1 4 2;  3 1 2 4
Now do this  for every element of $S_3$.
This method applies to listing permutations of $S_{n+1}$ from $S_n$.
This has the advantage that it can be converted into a computer program (may not be the most efficient; that is a different story).


TITLE: Prove $(1 + \frac{1}{n})^n$ is bounded above
QUESTION [13 upvotes]: I've checked similar questions on the site but couldn't find satisfactory solutions or hints.
Also, is there a more general approach to proving whether a given sequence is bounded below or above?

REPLY [0 votes]: Just for the heck of it.
If $x > 0$
then
$\begin{array}\\
\ln(1+x)
&=\int_0^x \dfrac{dt}{1+t}\\
&\lt x\\
\text{so}\\
n\ln(1+\frac1{n})
&\lt n(\frac1{n})\\
&=1\\
\text{so}\\
(1+\frac1{n})^n
&\lt e\\
\end{array}
$


TITLE: Proof that $a|b \iff ac|bc$
QUESTION [2 upvotes]: I have to prove, using the concept of divisibility (and no division), that if $c\ne 0$ then $a\mid b \leftrightarrow ac\mid bc$. I first proved $a \mid b \to ac\mid bc$, then got stuck on the opposite process. Here's what I did on the first part (please assume all numbers to be integers):
$$a\mid b$$
$$b=ka$$
$$bc=kac$$
$$ac\mid bc$$
Is this right?
As for $ac\mid bc \implies a\mid b$, I can't figure out a way to remove $c$ from $b$ without messing everything on $a$'s side.
Googling for an answer, I only found solutions that used division itself, which was of no help. Thanks in advance for your help!

REPLY [2 votes]: Strong Hint:$$\begin{align}ac&=bc\\ \Leftrightarrow\quad \bigg(\frac 1c\bigg)ac&= \bigg(\frac 1c\bigg)bc \\ \Leftrightarrow\space\, \bigg(\frac 1c\cdot c\bigg)a&= \bigg(\frac 1c\cdot c\bigg)b \\ \Leftrightarrow\quad\quad\:\, 1\cdot a&=1\cdot b \\ \Leftrightarrow\quad\quad\quad\,\,\, a&=b\end{align}$$ This is known as the $\color{green}{\text{Multiplicative Cancellation Law}}$.


TITLE: P(a and b) + P(a and not(b)) = P(a)
QUESTION [0 upvotes]: What would be an easy way of proving
$$ P(a\land b) + P(a\land \lnot b) = P(a) $$?
I think I managed something by applying the inclusion-exclusion principle in the form $ P(x) + P(y) = P(x \lor y) + P(x \land y)$ to the left-hand side (with $x=a \land b$ and $y=a \land \lnot b$) and then the $x\land y$ is always false and the $x\lor y$ seems to reduce to just $a$, but isn't there a more straightforward proof?

REPLY [0 votes]: From the kolmogorov axioms we know $P(B \cap B^\mathsf{c}) = P(\Omega )$. For any subset $A$ of $\Omega$:
$P(A \cap \Omega)=P(A)$


TITLE: Find number of continuous functions satisfying the equation $4\int_{0}^{\frac{3}{2}}f(x)dx+125\int_{0}^{\frac{3}{2}}\frac{dx}{\sqrt{f(x)+x^2}}=108$
QUESTION [1 upvotes]: The number of continuous functions $f:\left[0,\frac{3}{2}\right]\rightarrow (0,\infty)$ satisfying the equation$$4\int_{0}^{\frac{3}{2}}f(x)dx+125\int_{0}^{\frac{3}{2}}\frac{dx}{\sqrt{f(x)+x^2}}=108$$
is
(A)$0$
(B)$1$
(C)$2$
(D)greater than $2$
My Attempt:
Given equation can be written as
$$4\int_{0}^{\frac{3}{2}}(f(x)+x^2)dx+125\int_{0}^{\frac{3}{2}}\frac{dx}{\sqrt{f(x)+x^2}}=\frac{225}{2}$$
Now I am trying to use some inequality like AM-GM or CS so that a unique function happens so that inequality is valid only when equality holds but am not able to get it.

REPLY [4 votes]: Let $g(x)=f(x)+x^2$ first of all. Also note that $g(x)\geq 0$. Now,
$$4\int_0^{3/2}g(x)\textrm dx+125\int_0^{3/2}\dfrac{1}{2\sqrt{g(x)}}\textrm dx+125\int_0^{3/2}\dfrac{1}{2\sqrt{g(x)}}\textrm dx$$
$$\geq3\int_0^{3/2}\left(4g(x)\cdot\dfrac{125}{2\sqrt{g(x)}}\cdot\dfrac{125}{2\sqrt{g(x)}}\right)^{1/3}\textrm dx$$
Hope this helps. BTW I also took the same exam. ;)


TITLE: Prove that $\frac{du}{dt}=\delta(t)$ where $u(t)$ is Unit step function, $\delta(t)$ is impulse function
QUESTION [0 upvotes]: I want to prove that $$\frac{du}{dt}=\delta(t)$$
To do that I want to use the following:
$$\int_{-\infty}^{\infty}\phi(t) * g^{(n)}(t)dt = (-1)^n\int_{-\infty}^{\infty}\phi^{(n)}(t)*g(t)dt$$
What I tried is to assign $u'(t)$ in $g'(t)$:

$$... = (-1)^n\int_{-\infty}^{\infty}\phi'(t)*u(t)dt$$

Notes:  $u(t)$ is Unit Step, $\delta(t)$ is impulse function, $g(t)$ is random function

I guess I need to use the unit step features but I dont know to continue.
Any suggestion are welcomed! thanks.

REPLY [0 votes]: First of all, in the classical sense, that derivative doesn't exist. So what you're looking for a distributional derivative.
So let $\phi \in C_c^{\infty}(\mathbb{R})$, then $\int_{-\infty}^{\infty} u'\phi dx=-\int_{-\infty}^{\infty}u\phi' dx=-\int_0^{\infty}\phi' dx=-\phi\big|_0^{\infty}=\phi(0)$
That is, distributionally, $u'=\delta(x)$.


text:
\begin{document}

\title{A combinatorial identity for studying Sato-Tate type problems}

\author{Steven J. Miller}\email{Steven.J.Miller@williams.edu}
\address{Department of Mathematics and Statistics, Williams College, Williamstown, MA 01267}

\author{M. Ram Murty}\email{murty@mast.queensu.ca}
\address{Department of Mathematics, Queen's University,
Kingston, Ontario, K7L 3N6, Canada}

\author{Frederick Strauch}\email{fws1@williams.edu}
\address{Department of Physics, Williams College, Williamstown, MA 01267}

\subjclass[2000]{05A40, 05A10 (primary) 33C05, 11K38, 14H52, 11M41 (secondary).} \keywords{Binomial Identities, Hypergeometric Function, Sato-Tate, Erd\"{o}s-Turan, Effective Equidistribution}

\thanks{The first named author would like to thank Cameron and Kayla Miller for quietly sleeping on him while many of the calculations were done. Much of this paper was written when the first two authors attended the Graduate Workshop on $L$-functions and Random Matrix Theory at Utah Valley University in 2009, and it is a pleasure to thank the organizers. The first named author was partly supported by NSF grant DMS0600848. The second named author was partially supported by an NSERC Discovery grant.}

\maketitle

\begin{abstract} We derive a combinatorial identity which is useful in studying the distribution of Fourier coefficients of $L$-functions by allowing us to pass from knowledge of moments of the coefficients to the distribution of the coefficients.
\end{abstract}

\section{Introduction}

Recently M. Ram Murty and K. Sinha \cite{MS} proved effective equidistribution results showing the eigenvalues of Hecke operators on the space of cusp forms of weight $k$ and level $N$ agree with the Sato-Tate distribution. Their proof relied on bounding the discrepancy through an application of the Erd\"os-Turan inequality and estimates of exponential sums. In \cite{MM} the first two authors generalized their techniques to the Fourier coefficients of families of elliptic curves. The purpose of this note is to describe an interesting combinatorial identity needed in that analysis.

We first describe the problem that motivated this work. Recall that if $E: y^2 = x^3 + Ax + B$ with $A, B \in \Z$ is an elliptic curve over $\Q$, the associated $L$-function is \be L(E,s)\ =\ \sum_{n=1}^\infty \frac{a_E(n)}{n^s} \ = \ \prod_p \left(1 - \frac{a_E(p)}{p^s} + \frac{\chi_0(p)}{p^{2s-1}}\right)^{-1},\ee with $\Delta=-16(4A^3+27B^2)$ the discriminant of $E$, $\chi_0$ the principal character modulo $\Delta$, and \bea a_E(p) & \ =\ & p - \#\{(x,y) \in (\Z/p\Z)^2:  y^2 \equiv x^3 + Ax + B \bmod p\} \nonumber\\ &=& - \sum_{x\bmod p} \js{x^3 + Ax + B}. \eea By Hasse's bound we know $|a_E(p)| \le 2\sqrt{p}$, so we may write $a_E(p) = 2\sqrt{p} \cos \theta_E(p)$, where we may choose $\theta_E(p) \in [0,\pi]$. The distribution of the $a_E(p)$'s are related to numerous problems of interest; for example, by the Birch and Swinnerton-Dyer conjecture the order of vanishing of $L(E,s)$ at the central point $s=1/2$ is conjecturally equal to the group of rational solutions of $E$. See \cite{Sil1,Sil2,ST} for more on elliptic curves.

In the analysis in \cite{MM}, one needs to understand sums of $\cos(m\theta_n)$, with $n$ ranging over a family of $L$-functions. Such estimates exist \cite{Ka,Mic,Ni}, and have been used by others to prove effective equidistribution results for two-parameter families of elliptic curves \cite{BS,Sh1,Sh2}. It is possible to avoid these estimates if instead one uses results of Birch \cite{Bi} for sums of the moments, i.e., sums of $\cos^r(\theta_n)$. While typically these lead to worse results, as there may be situations in future research where only the moments are known  we describe how one may prove effective equidistribution results concerning the distribution of the Fourier coefficients of $L$-functions using just the moments and combinatorics.

The key combinatorial ingredient in \cite{MM} is the following, which is the main result of this paper.

\begin{thm}\label{keycombinatoriallemmaforsuns} Let $m$ be an integer greater than or equal to 1. Then \be \twocase{\sum_{r=0}^m (-1)^r \ncr{m}{r} \ncr{m+r}{r} \frac1{(r+1)(m+r)} \ = \ }{1/2}{{\rm if} $m=1$}{0}{{\rm if} $m \ge 2$.} \ee \end{thm}

We prove this theorem in \S\ref{sec:combidentities}, and then discuss its application to effective equidistribution in \S\ref{sec:preliminaries}.

\section{Combinatorial Identities}\label{sec:combidentities}

Below we give two different proofs of Theorem \ref{keycombinatoriallemmaforsuns}, each highlighting a different approach to proving combinatorial identities. We first state some needed properties of the binomial coefficients. For $n, r$ non-negative integers we set $\ncr{n}{k} = \frac{n!}{k!(n-k)!}$. We generalize to real $n$ and $k$ a positive integer by setting \be \ncr{n}{k} \ = \ \frac{n(n-1)\cdots (n-(k-1))}{k!}, \ee which clearly agrees with our original definition for $n$ a positive integer and vanishes when $n$ is a non-negative integer less than $k$. Finally, we set $\ncr{n}{0} = 1$ and $\ncr{n}{k} = 0$ if $k$ is a negative integer.

To prove our main result we need the following two lemmas; we follow the proofs in \cite{Ward}.

\begin{lem}[Vandermonde's Convolution Lemma] Let $r,s$ be any two real numbers and $k, m, n$ integers. Then \be \sum_k \ncr{r}{m+k} \ncr{s}{n-k} \ = \ \ncr{r+s}{m+n}. \ee
\end{lem}

\begin{proof} Note that the summand is zero if either $m+k > r$ or $n-k > s$, and thus it is a finite sum over $k$. It suffices to prove the claim when $r, s$ are integers. The reason is that both sides are polynomials, and if the polynomials agree for an infinitude of integers then they must be identical. By changing $n$ and $k$, we see it suffices to consider the special case $m=0$, in which case we are reduced to showing \be\label{eq:ncrcombidentityvandermonde} \sum_k \ncr{r}{k} \ncr{s}{n-k} \ = \ \ncr{r+s}{n}. \ee Consider the polynomial \be\label{eq:usefulpolyvandermondeconv} (x+y)^r (x+y)^s\ =\ (x+y)^{r+s}.\ee If we use the binomial theorem to expand the left hand side of \eqref{eq:usefulpolyvandermondeconv}, we get the coefficient of the $x^n y^{r+s-n}$ is the left hand side of \eqref{eq:ncrcombidentityvandermonde}; this follows from looking at all the ways we could get an $x^n y^{r+s-n}$, which involves summing over the coefficients of $x^{k} y^{r-k}$ times the coefficients of $x^{n-k} y^{s-n+k}$. Similarly, if we use the binomial theorem we find the coefficient of $x^n y^{r+s-n}$ is the right hand side of \eqref{eq:usefulpolyvandermondeconv}. This proves \eqref{eq:ncrcombidentityvandermonde}, which completes the proof.
\end{proof}

\begin{lem}\label{lem:neededlemcomb} Let $\ell, m, s$ be non-negative integers. Then \be \sum_k (-1)^k \ncr{\ell}{m+k} \ncr{s+k}{n} \ = \ (-1)^{\ell+m} \ncr{s-m}{n-\ell}. \ee \end{lem}

\begin{proof} Using $\ncr{a}{b} = \ncr{a}{a-b}$, we rewrite $\ncr{s+k}{n}$ as $\ncr{s+k}{s+k-n}$, and we then rewrite $\ncr{s+k}{s+k-n}$ as $(-1)^{s+k-n} \ncr{-n-1}{s+k-n}$ by using the extension of the binomial coefficient, where we have pulled out all the negative signs in the numerators. The advantage of this simplification is that the summation index is now only in the denominator; further, the power of $-1$ is now independent of $k$. Factoring out the sign, our quantity is equivalent to \bea & & (-1)^{s-n} \sum_k \ncr{\ell}{m+k} \ncr{-n-1}{s+k-n} \ = \ (-1)^{s-n} \sum_k \ncr{\ell}{\ell-m-k} \ncr{-n-1}{s+k-n},\nonumber\\ \eea where we again use $\ncr{a}{b} = \ncr{a}{a-b}$. By Vandermonde's Convolution Lemma, this equals $(-1)^{s-n}$ $\ncr{\ell-n-1}{\ell-m-n+s}$. Using $\ncr{s-m}{\ell-m-n+s}  = \ncr{s-m}{n-\ell}$ and collecting powers of $-1$ completes the proof (note $(-1)^{\ell-m} = (-1)^{\ell+m}$).
\end{proof}

Using the above two lemmas, we can now prove our main result.

\begin{proof}[First Proof of Theorem \ref{keycombinatoriallemmaforsuns}] The case $m=1$ follows by direct evaluation. Consider now $m \ge 2$.
We have \bea S_m & \ = \ & \sum_{r=0}^m (-1)^r \ncr{m}{r} \ncr{m+r}{r} \frac1{(r+1)(m+r)} \nonumber\\ &= \ & \sum_{r=0}^m (-1)^r \ncr{m}{r} \frac{m+1}{m+1} \ncr{m+r}{r} \frac1{(r+1)(m+r)} \nonumber\\ &\ = \ &
\sum_{r=0}^m (-1)^r \frac{m! (m+1)}{(r+1)\cdot r!m!} \frac1{m+1} \ \frac{(m+r)(m+r-1)!}{r! m \cdot (m-1+r)!}  \frac1{m+r} \nonumber\\ &\ = \ & \sum_{r=0}^m (-1)^r \ncr{m+1}{r+1} \ncr{m-1+r}{r} \frac{1}{m(m+1)}  \nonumber\\ &\ = \ & \frac1{m(m+1)} \sum_{r=0}^m (-1)^r \ncr{m+1}{r+1} \ncr{m-1+r}{m-1}. \eea We change variables and set $u=r+1$; as $r$ runs from $0$ to $m$, $u$ runs from $1$ to $m+1$. To have a complete sum, we want $u$ to start at $0$; thus we add in the $u=0$ term, which is $\ncr{m-2}{m-1}$. As $m \ge 2$, this is 0 from the extension of the binomial coefficient (this is the first of two places where we use $m \ge 2$). Our sum $S_m$ thus equals \bea S_m & \ = \ & -\frac1{m(m+1)} \sum_{u=0}^{m+1} (-1)^u \ncr{m+1}{u} \ncr{m-2+u}{m-1}. \eea We now use Lemma \ref{lem:neededlemcomb} with $k=u$, $m=0$, $\ell = m+1$, $s=m-2$ and $n=m-1$; note the conditions of that lemma require $s$ to be a non-negative integer, which translates to our $m \ge 2$. We thus find \be S_m \ = \ -\frac1{m(m+1)} (-1)^{m+1} \ncr{m-2}{-2} \ = \ 0, \ee which completes the proof.
\end{proof}

We give another proof of Theorem \ref{keycombinatoriallemmaforsuns} below using hypergeometric functions, highlighting other approaches to proving combinatorial identities.

\begin{proof}[Second Proof of Theorem \ref{keycombinatoriallemmaforsuns}] Consider
the hypergeometric function \be\label{eq:hypergeodef} {}_2F_1(a,b,c;z) \ = \
\frac{\Gamma(c)}{\Gamma(b)\Gamma(c-b)} \int_0^1 \frac{t^{b-1} (1-t)^{c-b-
1}dt}{(1-tz)^a}. \ee The following identity for the normalization constant of the
Beta function is crucial in the expansions: \be B(x,y) \ = \ \int_0^1 t^{x-1} (1-
t)^{y-1}dt \ = \ \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}. \ee We can use the
geometric series formula to expand \eqref{eq:hypergeodef} as a power series in
$z$ involving Gamma factors,
\be \label{eq:hypergeodef2} {}_2F_1(a,b,c;z) \ = \ \frac{\Gamma(c)}{\Gamma(a)
\Gamma(b)} \sum_{n=0}^{\infty}
\frac{\Gamma(a+n)\Gamma(b+n)}{\Gamma(c+n)} \frac{z^n}{n!}. \ee
Rewriting $\ncr{m}{r}$ as $(-1)^r \ncr{r-m-1}{r}$,  $S_m$ can be written
\be S_m\ =\ \frac{1}{m! (-m-1)!} \sum_{r=0}^{\infty} \frac{(r-m-1)! (r+m-
1)!}{(r+1)!} \frac{1}{r!}, \ee where we have formally extended the series to
$\infty$ as the coefficients will vanish for $r \ge m+1$.  By comparing the two
infinite series and using the fact that $z! = \Gamma(z+1)$, we see that if we take $a=-m$,
$b=m$, $c=2$, $n=r$ and $z=1$, after some simple algebra we obtain
\be\label{eq:hypergeomprooflemmaa3} S_m\ =\ \frac{\Gamma(m) {}_2F_1(-
m,m,2;1)}{\Gamma(2) \Gamma(1+m)} \ = \ \frac{\Gamma(m)}{\Gamma(1+m)
\Gamma(2+m) \Gamma(2-m)}, \ee where the last step uses \be
{}_2F_1(a,b,c;1)\ =\ \frac{\Gamma(c) \Gamma(c-a-b)}{\Gamma(c-a)
\Gamma(c-b)}, \ee which follows from the normalization constant of the Beta
function. Note that the right hand side of \eqref{eq:hypergeomprooflemmaa3} is
$1/2$ when $m=1$ and $0$ for $m \ge 2$ because for such $m$,
$1/\Gamma(2-m) = 0$ due to the pole of $\Gamma(2-m)$.

\end{proof}

\begin{rek} It is also possible to prove Theorem \ref{keycombinatoriallemmaforsuns} through symbolic
manipulations. Using the results from \cite{PS,PSR}, one may input this into a
Mathematica package, which outputs a proof (though not all the steps).  The
reasoning behind this automated proof method is described in \cite{PWZ}, and many
of the identities for hypergeometric functions can be interpreted in a very
computational manner.  These results are also useful in random walk
calculations in physics (quantum and classical), and reduction to the
hypergeometric function is a convenient first step towards continuum limits or
long-time asymptotics.

\end{rek}

\section{Effective Equidistribution}\label{sec:preliminaries}

For a sequence of numbers $x_n$ modulo 1, a measure $\mu$ and an interval $I \subset [0,1]$, let \bea N_I(V_p) & \ = \ & \#\{n \le V_p: x_n \in I\} \nonumber\\ \mu(I) & \ =\ & \int_I \mu(t) dt. \eea The discrepancy $D_{I,V_p}(\mu)$ is \bea D_{I,V_p}(\mu) & \ =\  & \left|N_I(V_p) - V_p \mu(I)\right|; \eea with this normalization, the goal is to obtain the best possible estimate for how rapidly $D_{I,V_p}(\mu)/V_p$ tends to 0. A standard approach is to use exponential sums and the Erd\"os-Turan theorem. Modifying the ideas in \cite{MS} (see \cite{MM} for the details), one finds

\begin{thm}\label{thm:MSmainmodified} Let $\{x_n\} \subset [0,1]$ and let the notation be as above. Let $\{c_m\}$ be a sequence of numbers such that $\sum_{m=-\infty}^\infty |c_m|  <  \infty$. Let $||\mu|| = \sup_{x \in [0,1]} |F(x)|$ with $\mu = F(-x)dx$.  Then for any $V_p$ and $M$ the discrepancy satisfies \bea\label{eq:definitiondiscdistanceUS} D_{I,V_p}(\mu)  \le \frac{V_p||\mu||}{M+1}  + \sum_{1 \le m \le M} \left(\frac1{M+1} + \min\left(b-a,\frac{1}{\pi|m|}\right)\right) \left|\sum_{n=1}^{V_p} e(mx_n) - V_p c_m\right|. \nonumber\\ \eea  \end{thm}

Let $\must = F(-x)dx$ be the normalized Sato-Tate distribution on $[0,1]$. Its density is \be 2\sin^2(\pi x) \ = \ 1 - \frac12 \left(e(x) + e(-x)\right),\ee which implies that the coefficients of $\must$ are $c_0 = 1$, $c_{\pm 1} = -1/2$ and $c_m = 0$ for $|m| \ge 2$.

We consider the family of all elliptic curves modulo $p$ for $p \ge 5$. We may write these curves in Weierstrass form as $y^2 = x^3 - ax - b$ with $a,b \in \Z/p\Z$ and $4a^3 \neq 27b^2$. The number of pairs $(a,b)$ satisfying these conditions\footnote{If $a = 0$ then the only $b$ which is eliminated is $b=0$. If $a$ is a non-zero perfect square there are two $b$ that fail, while if $a$ is not a square than no $b$ fail. Thus the number of bad pairs of $(a,b)$ is $p$.} is \be V_p \ := \ p(p-1).\ee We use Birch's \cite{Bi} results on the moments of the family of all elliptic curves modulo $p$ (there are some typos in his explicit formulas; we correct these in \cite{MM}); unfortunately, these are results for quantities such as $(2 \sqrt{p} \cos \theta_n)^{2R}$, and the quantity which naturally arises when applying Theorem \ref{thm:MSmainmodified} is $e(mx_n)$ (with $x_n$ running over the normalized angles $\theta_{a,b}(p)/\pi$), specifically \be \left| \sum_{n = 1}^{V_p} e(mx_n) - V_p c_m \right|. \ee By applying some combinatorial identities we are able to rewrite our sum in terms of the moments, which allows us to use Birch's results. The point of this section is not to obtain the best possible error term but rather to highlight how one may generalize and apply the framework from \cite{MS}.

We first set some notation. Let $\sigma_k(T_p)$ denote the trace of the Hecke operator $T_p$ acting on the space of cusp forms of dimension $-2k$ on the full modular group. We have $\sigma_{k+1}(T_p) = O(p^{k + c + \gep})$, where from \cite{Sel} we see we may take $c = 3/4$ (there is no need to use the optimal $c$, as our final result, namely \eqref{eq:Mgivenc}, will yield the same order of magnitude result for $c=3/4$ or $c=0$). Let $\mathcal{M}_p(2R)$ denote the $2R$\textsuperscript{th} moment of $2\cos(\theta_n) = 2\cos(\pi x_n)$ (as we are concerned with the normalized values, we use slightly different notation than in \cite{Bi}): \be \mathcal{M}_p(2R) \ = \ \frac1{V_p} \sum_{n=1}^{V_p} \left(2 \cos(\pi  x_n)\right)^{2R}. \ee

\begin{lem}[Birch]\label{lem:birch} Notation as above, we have \be \mathcal{M}_p(2R) \ = \ \frac1{R+1}\ncr{2R}{R} + O\left(2^{2R} V_p^{-\frac{1-c-\gep}2}\right);\ee we may take $c = 3/4$ and thus there is a power saving.\footnote{Note $\frac1{R+1}\ncr{2R}{R}$ is the $R$\textsuperscript{th} Catalan number. The Catalan numbers are the moments of the semi-circle distribution, which is related to the Sato-Tate distribution by a simple change of variables.}
\end{lem}

\begin{proof} The result follows from dividing the equation for $S_R^\ast(p)$ on the bottom of page 59 of \cite{Bi} by $p^R$, as we are looking at the moments of the normalized Fourier coefficients of the elliptic curves, and then using the bound $\sigma_{k+1}(T_p) = O(p^{k+c+\gep})$, with $c = 3/4$ admissible by \cite{Sel}. Recall $V_p=p(p-1)$ is the cardinality of the family. We have \bea \mathcal{M}_p(2R) & \ = \ & \frac1{R+1}\ncr{2R}{R} \frac{p(p-1)}{V_p} \nonumber\\ & & \ \ + \ O\left(\sum_{k=1}^R \frac{2k+1}{R+k+1} \ncr{2R}{R+k} \frac{p^{1+c+\gep}}{V_p} + \frac{p}{p^R V_p}\right) \nonumber\\ & = & \frac1{R+1}\ncr{2R}{R} + O\left(2^{2R} V_p^{-\frac{1-c-\gep}2}\right)\eea since $V_p = p(p-1)$.
\end{proof}

A simple argument\footnote{To see that we may match the angles as claimed for the family of all elliptic curves, consider the elliptic curve $y^2 = x^3-ax-b$ with $4a^3\neq 27b^2$. Let $c$ be any non-residue modulo $p$, and consider the curve $y^2 = x^3 - ac^2x - bc^3$. Using the Legendre sum expressions for $a_E(p)$ and $a_{E'}(p)$, using the automorphism $x \to cx$ we see the second equals $\js{c}$ times the first; as we have chosen $c$ to be a non-residue, this means $2\sqrt{p}\cos(\theta_{E'}(p)) = -2\sqrt{p}\cos(\theta_E(p))$, or $\theta_{E'}(p)=\pi-\theta_E(p)$ as claimed.} shows that the normalized angles are symmetric about $1/2$. This implies \be \sum_{n=1}^{V_p} e(mx_n) \ = \ \sum_{n=1}^{V_p} \cos(2\pi mx_n) + i  \sum_{n=1}^{V_p} \sin(2\pi mx_n) \ = \ \sum_{n=1}^{V_p} \cos(2m\theta_n),\ee where the sine piece does not contribute as the angles are symmetric about $1/2$. Thus it suffices to show we have a power saving in \be \left| \sum_{n=1}^{V_p} \cos(2m\theta_n) - V_p c_m\right|. \ee By symmetry, it suffices to consider $m \ge 0$.

\begin{lem}Let $c_0 = 1$, $c_{\pm 1} = -1/2$ and $c_m = 0$ otherwise. There is some $c < 1$ such that \be \left| \sum_{n=1}^{V_p} \cos(2m\theta_n) - V_p c_m\right| \ \ll \ \left(m^2 2^{3m} V_p^{-\frac{1-c-\gep}2}\right); \ee by the work of Selberg \cite{Sel} we may take $c = 3/4$.
\end{lem}

\begin{proof}
The case $m=0$ is trivial. For $m=1$ we use the trigonometric identity $\cos(2\theta_n) = 2 \cos^2(\theta_n) - 1$. As $c_{\pm 1} = -1/2$ we have \bea \sum_{n=1}^{V_p} \cos(2\theta_n) - \frac{V_p}2 & \ = \ & \sum_{n=1}^{V_p} \left[ \left(2\cos^2 \theta_n - 1\right) + \frac12\right] \nonumber\\ & = & \frac12 \sum_{n=1}^{V_p} \left((2 \cos \theta_n)^2 - 1\right) \nonumber\\ & = & \frac12 \sum_{n=1}^{V_p} \left(\frac{(2\sqrt{p}\cos\theta_n)^2}{p} - 1\right). \eea Note the sum of $(2\sqrt{p}\cos \theta_n)^2$ is the second moment of the number of solutions modulo $p$. From \cite{Bi} we have that this is $p + O(1)$; the explicit formula given in \cite{Bi} for the second moment is wrong; see \cite{MM} for the correct statement. Substituting yields \bea \left|\sum_{n=1}^{V_p} \cos(2\theta_n) - \frac{V_p}2\right| & \ \ll \ & O(1). \eea

The proof is completed by showing that $\sum_{n=1}^{V_p} \cos(2m\theta_n) = O_m(V_p^{1/2})$ provided $2 \le m \le M$. In order to obtain the best possible results, it is important to understand the implied constants, as $M$ will have to grow with $V_p$ (which is of size $p^2$). While it is possible to analyze this sum for any $m$ by brute force, we must have $M$ growing with $p$, and thus we need an argument that works in general. As $c_{\pm 1} \neq 0$ but $c_m = 0$ for $|m| \ge 2$, we expect (and we will see) that the argument below does break down when $|m| = 1$.

There are many possible combinatorial identities we can use to express $\cos(2m\theta_n)$ in terms of powers of $\cos(\theta_n)$. We use the following (for a proof, see Definition 2 and equation (3.1) of \cite{Mil}): \be\label{eq:sjmexpansiontwocos2mtheta} 2\cos(2m\theta_n) \ = \ \sum_{r=0}^{m} c_{2m,2r} (2 \cos \theta_n)^{2r}, \ee where $c_{2r} = (2r)!/2$, $c_{0,0} = 0$, $c_{2m,0} = (-1)^m 2$ for $m\ge 1$, and for $1 \le r \le m$ set \be c_{2m,2r} \ = \ \frac{(-1)^{r+m}}{c_{2r}}\prod_{j=0}^{r-1} (m^2 - j^2) \ = \  \frac{(-1)^{m+r}}{c_{2r}}\frac{m \cdot (m+r-1)!}{(m-r)!}. \ee We now sum \eqref{eq:sjmexpansiontwocos2mtheta} over $n$ and divide by $V_p$, the cardinality of the family. In the argument below, at one point we replace $2^{2r}$ in an error term with $2012\frac1{r+1}\ncr{2r}{r} \cdot m^2$; this allows us to pull the $r$\textsuperscript{th} Catalan number, $\frac{1}{r+1}\ncr{2r}{r}$, out of the error term.\footnote{The reason this is valid is that the largest binomial coefficient is the middle (or the middle two when the upper argument is odd). Thus $2^{2r} = (1+1)^{2r} \le (2r+1) \ncr{2r}{r} \le 2(m+1)\ncr{2r}{r}$ (as $m \le r$), and the claim follows from $\frac{2012m^2}{r+1} \ge 2(m+1)$ for $m \ge 2$ and $0 \le r \le m$.} Using
Lemma \ref{lem:birch} we find \bea & & \frac1{V_p} \sum_{n=1}^{V_p} 2\cos(2m\theta_n)  \ = \  \sum_{r=0}^m c_{2m,2r} \frac1{V_p} \sum_{n=1}^{V_p} (2 \cos \theta_n)^{2r} \nonumber\\ & = & \sum_{r=0}^m \left( \frac1{r+1}\ncr{2r}{r} + O\left(2^{2r} V_p^{-\frac{1-c-\gep}2}\right) \right) c_{2m,2r}\nonumber\\ &=& \sum_{r=0}^m \left( \frac1{r+1}\frac{(2r)!}{r!r!} \frac{(-1)^{m+r} 2}{(2r)!}  \frac{m \cdot (m+r)!}{(m-r)! \cdot (m+r)} \right)\nonumber\\ & & \ \ \ \cdot \ \left(1 + O\left(m^2 V_p^{-\frac{1-c-\gep}2} \right)\right) \nonumber\\ & = & (-1)^m 2m \sum_{r=0}^m \left((-1)^r\frac{m!}{r!(m-r)!}   \frac{(m+r)!}{m!r!}\frac{1}{(r+1)(m+r)} \right)\nonumber\\ & & \ \ \ \cdot \ \left(1 + O\left(m^2 V_p^{-\frac{1-c-\gep}2} \right)\right)  \nonumber\\ & = & (-1)^m 2m \sum_{r=0}^m \left((-1)^r\ncr{m}{r}  \ncr{m+r}{r}\frac{1}{(r+1)(m+r)} \right)\nonumber\\ & & \ \ \ \cdot \ \left(1 + O\left(m^2 V_p^{-\frac{1-c-\gep}2} \right)\right). \eea We first bound the error term. For our range of $r$, $\ncr{m+r}{r} \le \ncr{2m}{m} \le 2^{2m}$. The sum of $\ncr{m}{r}$ over $r$ is $2^m$, and we get to divide by at least $m+r \ge m$. Thus the error term is bounded by \be O\left(m^2 2^{3m} V_p^{-\frac{1-c-\gep}2} \right). \ee We now turn to the main term. It it just $(-1)^m 2m$ times the sum in Theorem \ref{keycombinatoriallemmaforsuns}, which is shown in that theorem to equal 0 for any $|m| \ge 2$. Note that without Theorem \ref{keycombinatoriallemmaforsuns}, our combinatorial expansion would be useless.
\end{proof}

\begin{rek} It is possible to get a better estimate for the error term by a more detailed analysis of $\sum_{r\le m} \ncr{m}{r} \ncr{m+r}{r}$; however, the improved estimates only change the constants in the discrepancy estimates, and not the savings. This is because this sum is at least as large as the term when $r \approx m/2$, and this term contributes something of the order $3^{3m/2} / m$ by Stirling's formula. We will see that any error term of size $3^{am}$ for a fixed $a$ gives roughly the same value for the best cutoff choice for $M$, differing only by constants. Thus we do not bother giving a more detailed analysis to optimize the error here. \end{rek}

We now prove effective equidistribution for the family of all elliptic curves.

\begin{thm}\label{thm:allellipticcurves} For the family of all elliptic curves modulo $p$, as $p\to\infty$ we have \be D_{I,V_p}(\must) \ \le\ C \frac{V_p}{\log V_p} \ee for some computable $C$. \end{thm}

\begin{proof} We must determine the optimal $M$ to use in \eqref{eq:definitiondiscdistanceUS}: \bea  D_{I,V_p}(\must) & \ \ll \ & \frac{V_p}{M+1}  + \sum_{1 \le m \le M} \left(\frac1{M+1} + \frac1{m} \right) \left(m^2 2^{3m} V_p^{-\frac{1-c-\gep}2}\right) \nonumber\\ & \ll & \frac{V_p}{M} +  M 2^{3M} V_p^{-\frac{1-c-\gep}2} \nonumber\\ \eea as $\frac{1}{M+1} \ll \frac1{m}$ and $\sum_{m \le m} 2^{3m} \ll 2^{3M}$. For all $c > 0$ we find the minimum error by setting the two terms equal to each other, which yields \be V_p^{\frac{3-c-\gep}{2}} \ = \ M^2 2^{3M}. \ee For ease of exposition we replace $M^2 2^{3M}$ with $e^{3M}$; this worsens our constant slightly, but does not qualitatively change the result. Equating these errors means we are looking for $M$ such that \be e^{3M} \ = \ e^{\frac{3-c-\gep}{2} \log V_p}, \ee which implies \be\label{eq:Mgivenc} M \ = \ \frac{3-c-\gep}{6} \log V_p. \ee We thus see that we may find a constant $C$ such that \be D_{I,V_p}(\must) \ \le \ C \frac{V_p}{\log V_p}.\ee This yields a logarithm savings in the discrepancy, and proves effective equidistribution.
\end{proof}


TITLE: Torsion formula derivation
QUESTION [2 upvotes]: I am trying to derive the formula for torsion of a curve. In many example proofs I've seen the final step is that $\kappa=\|\dot{\lambda}\times\ddot{\lambda}\|$. However I thought curvature was defined to be $\kappa=\frac{\|\dot{\lambda}\times\ddot{\lambda}\|}{\|\dot{\lambda}\|^3}$ or $\kappa=\|\ddot{\lambda}\|$ if $\lambda$ is unit-speed. However, I would like to note, I have only assumed that $\lambda$ is a regular curve with non-zero curvature.
Edit: essentially how does one derive the formula in the screenshot.

REPLY [1 votes]: We must use the Frenet formulas for regular curves:
$$
\begin{align*}
T' &= v\kappa N\\
N' &= -v\kappa T + v \tau B\\
B' &= -v\tau N.
\end{align*}
$$
Here $T, N, B$ is the Frenet frame along the curve $\gamma$, $v = \|\gamma'\|$ is the speed and $\kappa$ and $\tau$ are of course the curvature and torsion.
By definition of $v$ we have
$$
 \gamma' = vT.
$$
The second derivative of $\gamma$ is
$$
 \gamma'' = v'T + vT' = v' T + v^2\kappa N.
$$
The cross product $\gamma'\times \gamma''$ becomes
$$
 \gamma' \times \gamma'' = \kappa v^3 B.
$$
If we take the norm of both sides, we obtain
$$
 \kappa = \frac{\|\gamma'\times\gamma''\|}{v^3} = \frac{\|\gamma'\times \gamma''\|}{\|\gamma'\|^3}. \tag{1}
$$
The binormal vector $B$ is a unit vector perpendicular to $T$ and $N$. From the expressions for $\gamma'$ and $\gamma''$, it follows that $B$ points in the same direction as $\gamma'\times \gamma''$, so
$$
 B = \frac{\gamma'\times\gamma''}{\|\gamma'\times\gamma''\|}. \tag{2}
$$
Deriving one more time gives $\gamma'''$:
$$
\begin{align*}
 \gamma''' &= v'' T + v'T' + (v^2\kappa)'N + v^2\kappa N' \\
          &= v''' T + (v'v\kappa  + (v^2\kappa)')N + v^3\kappa (-\kappa T + \tau B).
\end{align*}
$$
Take the inner product with $B$ and obtain $\gamma'''\cdot B = v^3\kappa \tau$. Combined with $(2)$ this gives
$$
 \tau = \frac{\gamma''' \cdot \gamma'\times\gamma''}{\|\gamma'\times\gamma''\|v^3\kappa}.
$$
Finally, using $(1)$, we may conclude that the torsion is given by
$$
  \tau = \frac{\gamma'\times\gamma''\cdot\gamma'''}{\|\gamma'\times\gamma''\|^2}.
$$


TITLE: Decomposition of induced representation from index 2 subgroup
QUESTION [0 upvotes]: Let $G$ be a finite group, $N$ a subgroup of index $2$, and $V$ an irreducible representation of $N$.
Question: How $\mathrm{Ind}_{N}^{G}(V)$ decomposes? Can we write explicitly the irreducible components?

Context: this question is motivated by a dual version of Ore's theorem. Let $[H,G]$ be a boolean interval of finite groups and $N \in [H,G]$ with $|G:N| = 2$ and $[H,N]$ linearly primitive (as interval). Then the answer of Derek Holt helped me to prove that $[H,G]$ is also linearly primitive.

REPLY [2 votes]: Corollary (6.19) of Isaacs, Character Theory of Finite Groups says that, if $N$ is normal in $G$ with $|G:N|=p$ prime and $\chi \in {\rm Irr}(G)$, then $\chi_N$ is either irreducible or a sum of $p$ distinct conjugate irreducible characters.
Let $\psi \in {\rm Irr}(N)$.
If $\psi = \chi_N$ for some $\chi \in {\rm Irr}(G)$, then $\psi^G$ is the sum of $p$ distinct irreducible characters of $G$, all having restriction $\psi$. Conversely, if $\psi^G$ is the sum of $p$ irreducible characters of $G$, then by frobenius reciprocity they must all reduce to $\psi$. In this case $\psi$ is fixed by conjugation by all elements of $G$.
Otherwise $\psi^G=\chi$ is irreducible. Then the second case of the result in Isaacs must apply to $\chi$, so $\chi$ has $p$ distinct conjugates under $G$.
This is all assuming that we are talking about complex representations. In the more general case it could be possible that $\psi^G$ was irreducible and reduced to to the sum of two copuies of $\psi$, but I have not thought about that.


TITLE: Why did Riemann believe that all non-trivial zeros of the zeta function lie on the critical line?
QUESTION [5 upvotes]: Bear with me, I'm fresh out of high school so my level of mathematical knowledge is quite low (probably too low to be trying to understand the Riemann hypothesis, but at least I'm trying).
At this current time, I'm trying to make sense of John Derbyshire's (fantastic) book Prime Obsession. One thing that hasn't been explained in the book and to which I cannot find answers within the bounds of my understanding through research, is why exactly Riemann thought his hypothesis was true.
From what I understand, Bernhard Riemann was a very intuitive mathematician so it's quite possible that although he did not have a proof for his hypothesis, it made sense to him intuitively. I guess my question is, How does it intuitively make sense that all non-trivial zeros of the zeta function lie on the critical line and not somewhere else?

REPLY [4 votes]: From Riemann's Zeta Function, By Harold M. Edwards:


TITLE: Line integrals along a line
QUESTION [1 upvotes]: Compute the following integrals:

$$\int_{\overline {AB}}^{ }\left(\cos\left(2y\right)dx-2x\sin\left(2y\right)dy\right)$$
$$\int_{\overline {AB}}^{ }\left(\tan\left(y\right)dx+x\sec^{2}\left(y\right)dy\right)$$

Where $A=(1,\frac{\pi}{6}), B=(2,\frac{\pi}{4})$.

The line can be parameterized as $$C: r(t)=(t,\frac{\pi}{12}(t+1)), \;\;\; t \in [1,2]$$
So:$$\int_{\overline {AB}}^{ }\left(\cos\left(2y\right)dx-2x\sin\left(2y\right)dy\right)$$$$=\frac{6}{\pi}\int_{\frac{\pi}{3}}^{\frac{\pi}{2}}\left(\cos\left(t\right)+\left(-t+\frac{\pi}{6}\right)\sin\left(t\right)\right)dt$$$$=\frac{6}{\pi}\left(1-\frac{\sqrt{3}}{2}-\frac{\pi}{6}-1+\frac{\sqrt{3}}{2}+\frac{\pi}{12}\right)$$$$=-1/2$$

$$\int_{\overline {AB}}^{ }\left(\tan\left(y\right)dx+x\sec^{2}\left(y\right)dy\right)$$$$=\int_{1}^{2}\left(\tan\left(\frac{\pi}{12}\left(t+1\right)\right)+t\sec^{2}\left(\frac{\pi}{12}\left(t+1\right)\right)\frac{\pi}{12}\right)dt$$$$=\frac{12}{\pi}\int_{\frac{\pi}{6}}^{\frac{\pi}{4}}\left(\tan\left(t\right)+\left(t-\frac{\pi}{12}\right)\sec^{2}\left(t\right)\right)dt$$$$=\frac{\sqrt{12}-1}{\sqrt{3}}$$
I want to know how much of my work is correct.

REPLY [1 votes]: Please note that both vector fields are conservative and are gradients of a scalar function.
$\vec F = \nabla f(x,y)$
So by Fundamental Theorem of Line Integral,
$\displaystyle \int_C (\nabla f) \cdot dr = f(b) - f(a), \ $ where $a$ and $b$ are start and end points respectively.
For the first one, $\vec F = \langle\cos(2y), -2x\sin(2y)\rangle = \nabla (x \cos (2y))$
Hence the line integral for the first one is $ \  2 \cos(\frac{\pi}{2}) - \cos (\frac{\pi}{3}) = - \dfrac{1}{2}$
For the second one, note that $\vec F = \nabla (x \tan y)$ so you can again apply fundamental theorem of line integral.


text:
\chapter{The Innovations Approach}

\noindent Let $X_t\in\mathcal S$ be a Markov process with generator $Q$. Let the domain of $Q$ be denoted by $\mathcal B(Q)$, and let $\mathcal B_b(Q)$ denote the subset of bounded functions in $\mathcal B(Q)$. For any function $g(x)\in\mathcal B_b(Q)$ we have the following limit:
\[\frac{\mathbb E[g(X_{t+\Delta t})|X_t=x]-g(x)}{\Delta t} \rightarrow Qg(x)\]
as $\Delta t\searrow 0$, for any $x\in\mathcal S$. If $Q$ is densely-defined and its resolvent set includes all positive real numbers, then the Hille-Yosida theorem applies, allowing us to write the the distribution of $X_t$ with a contraction semi-group. In these notes we assume that such conditions hold and that the transition density/mass is generated by an operator semigroup denoted by $e^{Q^*t}$.

A standard nonlinear filtering problem in SDE theory assumes that $X_t$ is unobserved and that a process $Y_t$ is given by an SDE
\begin{eqnarray}
\label{eq:dY}
dY_t&=&h(X_t)dt+\gamma dW_t\qquad\hbox{observed}
\end{eqnarray}
where $W_t$ is an independent Wiener process, $\gamma>0$ and we assume that the $h$ is bounded. Let the filtration $\mathcal F_t^Y=\sigma\{Y_s:s\leq t\}$ so that for an integrable function $g(x)$ we have
\[\hat g_t\doteq \mathbb E[g(X_t)|\mathcal F_t^Y]\]
for all $t\in[0,T]$.

\section{Innovations Brownian Motion}
Let $\nu_t$ denote the \textit{innovations process} whose differential is given as follows
\[d\nu_t = dY_t - \hat h_tdt.\]
with $\nu_0=0$, and where $\hat h_t = \mathbb E[h(X_t)|\mathcal F_t^Y]$.

\begin{proposition} The process $\nu_t/\gamma$ is an $\mathcal F_t^Y$ Brownian motion. \end{proposition}

\begin{proof} Is is clear that $\nu_t$ is (i) $\mathcal F_t^Y$-measurable, continuous and square integrable on $[0,T]$. To show that it is a local martingale, we take expectations for any $s\leq t$ as follows
\[\mathbb E[\nu_t|\mathcal F_s^Y]-\nu_s=\mathbb E\left[Y_t-\int_0^t\hat h_\tau d\tau\Big|\mathcal F_s^Y\right]-\left(Y_s-\int_0^s\hat h_\tau d\nu_\tau\right)\]

\[=\mathbb E\left[\gamma(W_t-W_s)+\int_s^th(X_\tau)d\tau\Big|\mathcal F_s^Y\right]-\mathbb E\left[\int_0^t\hat h_\tau d\tau\Big|\mathcal F_s^Y\right]+\int_0^s\hat h_\tau d\nu_\tau\]

\[=\mathbb E\left[\gamma(W_t-W_s)+\int_s^th(X_\tau)d\tau\Big|\mathcal F_s^Y\right]-\mathbb E\left[\int_s^t\hat h_\tau d\nu_\tau\Big|\mathcal F_s^Y\right]\]

\[=\gamma\mathbb E\left[W_t-W_s\Big|\mathcal F_s^Y\right]+\mathbb E\left[\int_s^th(X_\tau)d\tau-\int_s^t\hat h_\tau d\nu_\tau\Big|\mathcal F_s^Y\right]=0.\]
Furthermore, the cross-variation of $\nu_t/\gamma$ is the same as the cross-variation of $W_t$, and so by the L\'evy characterisation of Brownian motion (see Karatzas and Shreve \cite{K-S}), $\nu_t/\gamma$ is also $\mathcal F_t^Y$ Brownian motion.

\end{proof}

Given that $\nu_t$ is $\mathcal F_t^Y$-Brownian motion, it may seem obvious that any $L^2$-integrable and $\mathcal F_T^Y$ measurable random variable has an integrated representation in terms of $\nu$, but it is not easily seen that $\mathcal F_t^Y = \sigma\{\nu_s:s\leq t\}$. The following proposition provides a proof to verify that it is indeed true.
\begin{proposition}
\label{prop:martRep}
Every square integrable random variable $N$ that is $\mathcal F_T^Y$-measurable, has a representation of the form
\[N=\mathbb EN+\frac{1}{\gamma}\int_0^T f_sd\nu_s\]
where $f = \{f_s:s\leq T\}$ is progressively measurable and $\mathcal F_t^Y$-adapted and $\mathbb E\left[\int_0^Tf_s^2ds\right]<\infty$.
\end{proposition}
\begin{proof} For all $t\in[0,T]$, define $Z_t\doteq \exp\left\{ -\frac{1}{\gamma^2}\int_0^t\hat h_sd\nu_s-\frac{1}{2\gamma^2}\int_0^t\hat h_s^2ds\right\}$. Clearly, $Z_t$ is an $\mathcal F_t^Y$-martingale, and so we can define an equivalent measure $\tilde{\mathbb P}$ with the following Radon-Nikodym derivative,
\[\frac{d\tilde{\mathbb P}}{d\mathbb P} = Z_T.\]
As a consequence of the Girsanov theorem, $Y_t/\gamma$ is a $\tilde{\mathbb P}$-Brownian motion. Then apply the martingale representation theorem,
\[Z_T^{-1}N = \tilde{\mathbb E}[Z_T^{-1}N]+\frac{1}{\gamma}\int_0^Tq_sdY_s\]

\[=\tilde{\mathbb E}[Z_T^{-1}N]+\frac{1}{\gamma}\int_0^Tq_sd\nu_s+\frac{1}{\gamma}\int_0^Tq_s\hat h_sds\]
where $q = \{q_s:s\leq T\}$ is adapted and $\tilde{\mathbb P}\left(\int_0^tq_s^2<\infty\right)=\mathbb P\left(\int_0^tq_s^2<\infty\right)=1$. From here we can construct a $\tilde{\mathbb P}$-martingale from $Z_T^{-1}N$,
\[\tilde N_t \doteq \tilde{\mathbb E}[Z_T^{-1}N|\mathcal F_t^Y]\]
and applying It\^o's lemma to $\tilde N_tZ_t$ we have
\[d\left( \tilde N_tZ_t \right)=-\frac{1}{\gamma^2}Z_t\tilde N_t\hat h_td\nu_t+\frac{1}{\gamma}Z_tq_td\nu_t+\frac{1}{\gamma}Z_t\hat h_tq_tdt-\frac{1}{\gamma}Z_t\hat h_tq_tdt\]

\[=-\frac{1}{\gamma^2}Z_t\tilde N_t\hat h_td\nu_t+\frac{1}{\gamma}Z_tq_td\nu_t.\]
Integrating from $0$ to $t$, we have
\[\tilde N_tZ_t = \mathbb EN+\frac{1}{\gamma}\int_0^t\left(q_s-\frac{1}{\gamma}\tilde N_s\hat h_s\right)Z_sd\nu_s,\]
and therefore, setting $f_t =\left ( q_t-\frac{1}{\gamma}\tilde N_t\hat h_t\right)Z_t$ for all $t\in [0,T]$, we have a unique $\mathcal F_t^Y$-adapted representation in terms of $\nu$, and the proposition is proved.

\end{proof}
\begin{remark} For a more general proof of proposition \ref{prop:martRep}, see proposition 2.31 on page 34 of Bain and Crisan \cite{bainCrisan}. They present the proof for generalized systems on unbounded time intervals, with merely the conditions that $\mathbb E\left[\int_0^th^2(X_s)ds\right]<\infty$ and $\mathbb P\left(\int_0^t\hat h_s^2ds<\infty\right)=1$ for all $t<\infty$.
\end{remark}

\section{The Nonlinear Filter}
In deriving the nonlinear filter with the innovations Brownian motion, it will be important to use the following martingale for any given $g\in \mathcal B_b(Q)$:
\[N_t\doteq \hat g_t - \int_0^t\widehat{Q g}_sds\]
for all $t\in [0,T]$.

\begin{lemma} $N_t$ is an $\mathcal F_t^Y$-adapted martingale.
\end{lemma}

\begin{proof}
It suffices to show that $\mathbb EN_t = N_0$ for any $t\in [0,T]$, which we do as follows:
\[\mathbb EN_t = \mathbb E\left[\hat g_t- \int_0^t\widehat{Q g}_sds\right]=\mathbb Eg_t-\int_0^t\mathbb E\left[\mathbb E[Qg(X_s)|\mathcal F_s]\right]ds\]

\[=\mathbb Eg_t-\int_0^t\mathbb EQg(X_s)ds=\mathbb E\left[g_t-\int_0^tQg(X_s)ds\right]=\mathbb Eg(X_0)=N_0.\]
\end{proof}
Knowing that $\hat g_t-\int_0^t\widehat{Qg}_sds$ is an $\mathcal F_t^Y$-martingale, we will apply proposition \ref{prop:martRep} as follows
\[\hat g_t-\int_0^t\widehat{Qg}_sds =\hat g_0+\frac{1}{\gamma} \int_0^tf_sd\nu_s\]
where $f_t$ is an $\mathcal F_t^Y$-predicable process for any $t\in [0,T]$. From here, the main point in the derivation of the nonlinear filter is in finding the function $f_t$ in terms of quantities that are more readily computable.

\begin{theorem} \textbf{The Nonlinear Filter.} \label{thm:nlf}
For any function $g\in \mathcal B_b(Q)$, the nonlinear filter is given by the following SDE
\[d\hat g_t = \widehat{Qg}_tdt+ \frac{\widehat{gh}_t-\hat g_t\hat h_t}{\gamma^2}d\nu_t\]
for all $t\in [0,T]$.
\end{theorem}

\begin{proof} We can apply proposition \ref{prop:martRep} to $N_t$ and we get
\[N_t = \mathbb EN_0+\frac{1}{\gamma}\int_0^tf_sd\nu_s=\hat g_0+\frac{1}{\gamma}\int_0^tf_sd\nu_s,\]
thus defining the conditional expectation at time $t$ as
\[\hat g_t = \hat g_0+\int_0^t\widehat{Qg}_sds+\frac{1}{\gamma}\int_0^tf_sd\nu_s.\]
From here, to complete the proof only requires us to identify $f_t$ explicitly. For some process $\psi\in L^\infty[0,T]$, define $\xi_t$ such that
\[d\xi_t = \frac{i}{\gamma}\xi_t\psi_tdY_t\]
with $\xi_0=1$. We then apply It\^o's lemma to the following
\begin{eqnarray}
\label{eq:d1}
d\left(\hat g_t\xi_t \right)&=& \widehat{Qg}_t\xi_tdt+\frac{1}{\gamma}f_t\xi_td\nu_t+\frac{i}{\gamma}\hat g_t\xi_t\psi_t\left(d\nu_t+\hat h_tdt\right)+i\xi_t\psi_tf_tdt\\
\label{eq:d2}
d\mathbb E[g(X_t)\xi_t] &=& \mathbb E\left[Qg(X_t)\xi_t\right]dt+\frac{i}{\gamma}\mathbb E\left[g(X_t)\xi_t\psi_th(X_t)\right]dt.
\end{eqnarray}
If we integrate the integrands in (\ref{eq:d1}) and (\ref{eq:d2}) from time $0$ to time $t$, take expectations, multiply both sides by $\gamma$, and then subtract one from the other, and we are left with
\[\int_0^ti\psi_s\mathbb E\left[\xi_s\left(\gamma f_s-g(X_s)h(X_s)+\hat g_s\hat h_s\right)\right]ds=0.\]
Hence, for almost every $t\in[0,T]$, we have
\[\mathbb E\left[\xi_t\left(\gamma f_t-g(X_t)h(X_t)+\hat g_t\hat h_t\right)\right]=0=\mathbb E\left[\xi_t\left(\gamma f_t-\mathbb E[g(X_t)h(X_t)|\mathcal F_t^Y]+\hat g_t\hat h_t\right)\right]\]
and since $\xi_t$ belongs to a complete set, must have
\[f_t =\frac{ \mathbb E[g(X_t)h(X_t)|\mathcal F_t^Y]-\hat g_t\hat h_t}{\gamma}=\frac{\widehat {gh}_t-\hat g_t\hat h_t}{\gamma}\]
which proves the theorem.
\end{proof}
Existence of the solutions to the filtering SDE in theorem \ref{thm:nlf} is consequence of the fact that $\hat g_t$ is on such solution. The uniqueness of solutions to the filtering SDE can be grouped in with proofs for uniqueness of Zakai equation (see Kurtz and Ocone \cite{kurtzOcone1988} or Rozovsky \cite{rozovsky1992}) because there is a one-to-one relationship between measure-valued solutions of the two SDEs.

\subsection{Correlated Noise Filtering}
Suppose that $W_t$ and $X_t$ are correlated so that for any function $g\in \mathcal B_b(Q)$ we have

\[\frac{1}{\gamma}\sum_n\Delta Y_{t_n}\Delta g( X_{t_n})\stackrel{p}{\longrightarrow}\left<W,g(X)\right>_t\doteq\int_0^t \rho_s^gds\]
where $0=t_0<t_1<\dots<t_n=t$ and the limit is taken as $\sup_n(t_{n+1}-t_n)\rightarrow 0$. Then there is an added term in equation (\ref{eq:d2}),

\[d\mathbb E[g(X_t)\xi_t] = \mathbb E\left[Qg(X_t)\xi_t\right]dt+\frac{i}{\gamma}\mathbb E\left[g(X_t)\xi_t\psi_th(X_t)\right]dt+i\mathbb E\left[\xi_t\psi_t\rho_t^g \right]dt\]
and so for almost every $t\in[0,T]$ we have
\[\mathbb E\left[\xi_t\left(\gamma f_t-\mathbb E[g(X_t)h(X_t)|\mathcal F_t^Y]+\hat g_t\hat h_t-\gamma\hat \rho_t^g\right)\right]=0\]
and so $f_t = \frac{1}{\gamma}(\widehat{gh}_t-\hat g_t\hat h_t+\gamma\hat \rho_t^g)$, and the nonlinear filter is

\[d\hat g_t = \widehat{Qg}_tdt+\frac{\widehat{gh}_t-\hat g_t\hat h_t+\gamma\hat \rho_t^g}{\gamma^2}d\nu_t.\]

\subsection{The Kalman-Bucy Filter}
Another big advantage to the innovations approach is in linear filtering. In particular, the case when the filtering problem consists of a system of linear SDEs. In this case, one needs to take some steps to verify that the filtering distribution is normal, but after doing so it is straight-forward to derive equations for the posterior's first and second moments.

Consider a non-degenerate linear observations model such that $h(x)=h\cdot x$ and $\gamma>0$, with $X_0$ being Gaussian distributed, and with state-space generator
\[Q = \frac{\sigma^2}{2}\frac{\partial^2}{\partial x^2}~\cdot~+ax\frac{\partial}{\partial x}~\cdot~\]
for all functions $g\in C^2(\mathbb R)$, where $\sigma $ and $a$ are constant coefficients. The process
\[N_t \doteq \widehat X_t - \int_0^t\widehat{QX}_sds = \widehat X_t-a\int_0^t\widehat X_sds \]
is square-integrable and a martingale, and if we extend proposition \ref{prop:martRep} for $h(x) = h\cdot x$ (see proposition 2.31 on page 34 of Bain and Crisan \cite{bainCrisan}), we can then write $N_t$ using innovations Brownian motion,
\[N_t =\widehat X_0+\frac{1}{\gamma}\int_0^tf_sd\nu_s\]
where $f_t\in L^2[0,T]$ and is $\mathcal F_t^Y$-adapted. Now, by simple stochastic calculus we can verify that $X_t$ is given by
\[X_t = e^{at}X_0+\sigma\int_0^te^{a(t-s)}dB_s\]
where $B_t\perp W_t$ (i.e. the state-space noise is independent of the observation noise). Defining the estimation error $\epsilon_t$ as
\[\epsilon_t\doteq X_t-\widehat X_t.\]
and applying It\^o's lemma, we have
\[d\epsilon_t = a\epsilon_tdt+\sigma dB_t-\frac{1}{\gamma}f_td\nu_t,\]
which has a solution given by the integrating factor,
\[\epsilon_t =e^{at}\epsilon_0+\sigma\int_0^te^{a(t-s)}dB_s-\frac{1}{\gamma}\int_0^te^{a(t-s)}f_sd\nu_s,\]
which is Gaussian distributed and uncorrelated with $Y$
\[\mathbb E[Y_s\epsilon_t] =\mathbb E[Y_s(X_t-\widehat X_t)] =\mathbb E[Y_s\mathbb E[X_t-\widehat X_t|\mathcal F_t^Y]]=0\]
for all $s\leq t$. Now observe the following:
\begin{itemize}
\item $(X_t,Y_s)$ are jointly Gaussian for any $s\leq t$,
\item $\widehat X_t$ is Gaussian and a linear function of $\{Y_s\}_{s\leq t}$,
\item therefore, $(X_t,\widehat X_t,Y_s)$ are jointly Gaussian for any $s\leq t$
\item in particular $(\epsilon_t,Y_s)$ are jointly Gaussian and uncorrelated for any $s\leq t$.
\end{itemize}
Therefore, $\epsilon_t$ is independent of $\mathcal F_t^Y$ (for a more detailed discussion see \cite{bainCrisan,oxendale}), and so the filter is Gaussian .

If we apply the filter in theorem \ref{thm:nlf} with $g(x)=x$, it yields $f_t = \frac{1}{\gamma}\mathbb E[\epsilon_t^2|\mathcal F_t^Y]=\frac{1}{\gamma} \mathbb E\epsilon_t^2$, and an SDE for the evolution of the first filtering moment
\begin{eqnarray}
\label{eq:KF}
d\widehat X_t&=&a\widehat X_tdt+\frac{h\cdot\mathbb E\epsilon_t^2}{\gamma^2}d\nu_t.
\end{eqnarray}
We can also apply It\^o's lemma and then take expectations, which will result in a Riccati equation for the evolution of the filter's covariance,
\begin{eqnarray}
\nonumber
d\mathbb E[\epsilon_t^2]&=&2a\mathbb E[\epsilon_t^2]dt+\sigma^2dt+\mathbb E[f_t^2]dt\\
\nonumber
&&\\
\label{eq:Riccati}
&=&2a\mathbb E[\epsilon_t^2]dt+\sigma^2dt-\frac{h^2\cdot\mathbb E[\epsilon_t^2]^2}{\gamma^2}dt
\end{eqnarray}
where we have used the fact that $d\nu_t\cdot dB_t=0$, and $\mathbb E[f_t^2]=\frac{1}{\gamma^2}\mathbb E\left[\mathbb E[\epsilon_t^2]\mathbb E[ \epsilon_t^2]\right]=\frac{1}{\gamma^2}\mathbb E[\epsilon_t^2]^2$. Equations (\ref{eq:KF}) and (\ref{eq:Riccati}) are the Kalman filter.


TITLE: Euler formula, trigonometry.
QUESTION [1 upvotes]: Prove with Euler formula that
$$
\cos(x-y) = \cos(x)\cos(y) - \sin(x)\sin(y).
$$
I know how to find $\cos(x+y)$, but as for $\cos(x-y)$, I'm clueless.
Thanks.

REPLY [1 votes]: \begin{align*}
e^{ix} & = \cos x+ i \sin x\\
e^{i(x-y)} & = \frac{e^{ix}}{e^{iy}}\\
\frac{e^{ix}}{e^{iy}} & =\frac{\cos x + i \sin x}{\cos y+i\sin y}\\
\frac{\cos x + i \sin x}{\cos y+i\sin y} & =\frac{\cos x + i \sin x}{\cos y+i\sin y}\frac{\cos y - i \sin y}{\cos y -i\sin y}\\
& =\frac{\cos x \cos y+i\sin x\cos y-i\cos x\sin y+\sin x \sin y}{\cos^2 y+ \sin^2 y}\\
& ={\sin x\sin y + \cos x \cos y+i(\cos x \sin y -\sin x \cos y)}
\end{align*}
Equating real and imaginary parts:
$$\boxed{\cos [x-y]=\sin x\sin y + \cos x \cos y \text{  and   } \sin[x-y]=\cos x \sin y -\sin x \cos y}$$


TITLE: What is 'identifying restricted Boltzmann machine'?
QUESTION [0 upvotes]: Currently, I am going through Geometry of the Restricted Boltzmann Machine by Cueto et al.
In this paper (in the abstract, multiple places in Section 1, etc.), the authors use the concept of the identification of restricted Boltzmann machine.
What does 'identification' mean in this context? Thanks.

REPLY [1 votes]: "Identifiability" means you can find a unique solution that generates your observations. Unidentifiable models have multiple solutions that are equivalent.


TITLE: Simple modules of an algebra
QUESTION [0 upvotes]: How can we find the simple modules of this algebra $$
\begin{pmatrix}
k & 0 &0  \\
k & k & 0 \\
k&0&k
\end{pmatrix}
$$
And why this algebra is not semisimple(i,e it is isomorphic to the algebra $k^{5}$????)
I know that his radical is $$
\begin{pmatrix}
0& 0&0 \\
k& 0&0 \\
k&0&0
\end{pmatrix}$$
Thank you!

REPLY [1 votes]: How can we find the simple modules of this algebra

Denoting this algebra as $R$, the simple $R$ modules are exactly the simple $R/J(R)$ modules, where $J(R)$ is the Jacobson radical you have found. This is isomorphic to the product ring $k^3$. Now you just need to conclude what the isoclasses of simple modules over that ring are.
The same strategy was applied at this solution, for example: https://math.stackexchange.com/a/147195/29335

And why this algebra is not semisimple

You just said that the Jacobson radical is some nonzero set, but the Jacobson radical of a semisimple ring is zero.

i,e it is isomorphic to the algebra $k^5$????)

There is more than one semisimple $k$ algebra than $k^5$. It could have been $M_2(k)\times k$ or $Q\times k$ if $k$ admits a $4$-dimensional quaternion $k$-algebra other than $M_2(k)$.


TITLE: What is an n-oriented graph?
QUESTION [5 upvotes]: I was reading Allen Hatcher's Algebraic Topology, and he mentioned a 2-oriented graph while describing the covering spaces of S1∨S1. What is a 2-oriented graph? Can you give an examples of 2-oriented, 3-oriented, and 4-oriented graphs?

REPLY [4 votes]: A $2$-oriented graph is a $2$-labelled (each edge has one of two labels from some labelset $L_2=\{\alpha,\beta\}$), oriented graph, such that each vertex has degree four, with the indegree of $\alpha$ edges being one and the outdegree of $\alpha$ edges being one at each vertex, and similarly for $\beta$.
An $n$-oriented graph is similarly defined with the labelset $L_n$ having cardinality $n$, and such that each vertex has degree $2n$ and has exactly one ingoing and one outgoing edge of each label from the labelset $L_n$. (For the purposes of this definition, a loop counts as both an ingoing and outgoing edge of the same label).

It is an exercise to show that each graph $G$ with constant vertex degree $2n$ can be $n$-oriented (Hint: show that $G$ admits an Eulerian circuit)