TITLE: Divisibility of determinant.
QUESTION [0 upvotes]: If the three digit numbers: $x17, 3y6, 12z$ where $x,y,z$ are integers from $0-9$ are divisible by a fixed constant $k,$ then the determinant
$$\left|\begin{matrix} x & 3 & 1 \\ 7 & 6 & z \\ 1 & y & 2\end{matrix}\right|$$
must be divisible by?

REPLY [1 votes]: Adding to the second row $100$ hundred times the first one and $10$ times the third one we get:
$$\left|\begin{matrix} x & 3 & 1 \\ 7 & 6 & z \\ 1 & y & 2\end{matrix}\right|=\left|\begin{matrix}x & 3 & 1 \\ 100x+10+7 &  300+10y+6 & 100+20+z \\ 1 & y & 2\end{matrix}\right|.$$
Now the elements of the second row are all multiple of $k$ by assumption. Since all the elements in the determinant are integer numbers the determinant must be a multiple of $k.$


TITLE: Equivalent definitions of Bezout domain
QUESTION [1 upvotes]: We are in integral domain.
How can i prove equivalent of definitions for bezout domain.
Thats mean
sum of two principal ideals is principal ideal
vs
bezout identity holds.

REPLY [2 votes]: Suppose $(a),\ (b)$ are principal ideals. Bezout then gives $x,y$ such that $ax+by=\gcd(a,b).$ So if $d$ denotes $\gcd(a,b)$ we can get that the principal ideal $(d)$ is the same as $(a)+(b)$ by using the $x,y$ from Bezout. I'll leave the other direction of if and only if to you, as well as filling this sketch in a bit more.


TITLE: Let $f:G \longrightarrow G'$ be a group homomorphism. Prove that $\operatorname{Im}(f)$ is a subgroup of $G'$.
QUESTION [2 upvotes]: Can someone please verify this?

Let $f:G \longrightarrow G'$ be a group homomorphism. Prove that $\operatorname{Im}(f)$ is a subgroup of $G'$.

Let $a,b \in \operatorname{Im}(f)$. Then, there exist elements $x$ and $y$ in $G$ such that $f(x)=a$ and $f(y)=b$. Since $f$ is a homomorphism,
\begin{equation}
f(x \cdot y) \in \operatorname{Im}(f)
\end{equation}
That is, \begin{eqnarray}
f(x) \cdot f(y) &\in& \operatorname{Im}(f) \\
a \cdot b &\in& \operatorname{Im}(f)
\end{eqnarray}
This shows that $\operatorname{Im}(f)$ is closed under the operation $\cdot$. Also, since $f$ is a homomorphism, the identity element $e'$ of $G'$ belongs to $\operatorname{Im}(f)$ (a fact proved earlier). Moreover, every element $g$ in $\operatorname{Im}(f)$ has an inverse in $\operatorname{Im}(f)$ (a fact proved earlier). This completes the proof.

REPLY [1 votes]: As Marc said, this looks good. However, I would change the statement

Since $f$ is a homomorphism, $f(x\cdot y) \in \operatorname{Im}(f)$.

Is this really because $f$ is a homomorphism? Maybe it is and I just can't see it. I would argue that it follows because $G$ is a group under $\cdot$. As $x, y \in G$, $x\cdot y \in G$ so $f(x\cdot y) \in \operatorname{Im}(f)$.
Also, you shouldn't use $\cdot$ to denote the group operation in both $G$ and $G'$ as they could have different operations (i.e. $\phi: (\mathbb{R}, +) \to (\mathbb{R}_+, \cdot)$, $\phi(x) = e^x$).


TITLE: Slightly different results to an ODE system - hand calculation vs Mathematica
QUESTION [4 upvotes]: This has been driving me mad for the last few days. I have a a pair of ODEs:
$$\frac{d^2 M_N}{d x^2}=\lambda_{N}^2 M_N$$
$$\frac{d^2 M_{N-1}}{d x^2}=\lambda_{N-1}^2 M_{N-1}-\frac{f}{d_{N-1}}M_N$$
With BCs
$$M_N(1)=M_{N-1}(1)=0,\ \frac{d M_{N}}{d x}(0)=h,\ \frac{d M_{N-1}}{d x}(0)=0$$
The solution to $M_N$ is:
$$M_N(x)=\frac{h}{\lambda_N}\text{sech}(\lambda_N)\sinh(\lambda_N(x-1))$$
No surprises there.
The trouble comes when I solve $M_{N-1}$. I get:
$$M_{N-1}=\frac{fh}{d_{N-1}\lambda_{N}^2}\left(\frac{1}{\lambda_N}\text{sech}(\lambda_N)\sinh(\lambda_N(x-1))-\frac{1}{\lambda_{N-1}}\text{sech}(\lambda_{N-1})\sinh(\lambda_{N-1}(x-1))\right)$$
However, Mathematica gets
$$M_{N-1}=\frac{fh}{d_{N-1}(\lambda_{N-1}^2-\lambda_{N}^2)}\left(\frac{1}{\lambda_N}\text{sech}(\lambda_N)\sinh(\lambda_N(x-1))-\frac{1}{\lambda_{N-1}}\text{sech}(\lambda_{N-1})\sinh(\lambda_{N-1}(x-1))\right)$$
Now, I can say for certain that $|\lambda_N| \ne |\lambda_{N-1}|$. I realise Mathematica doesn't know this, and I suspect that could have something to do with this. But I simply can't find a way to come up with the same result by hand.
I know this is a selfish question, but can someone step through the process and show me how to come up with Mathematica's answer please!

REPLY [2 votes]: The general solution to the ODE

$$
u''(x) = a^2\,u(x)
$$
  for $a \in \mathbb{R}$ is
  $$
u(x) = A\sinh(ax) + B\cosh(ax)
$$

The BC

$$u(1) = 0$$

then requires
$$
B = -A\tanh(a)
$$
so
$$
u(x) = A \left[\, \sinh(ax) - \tanh(a)\cosh(ax) \,\right]
     = A\operatorname{sech}(a) \sinh[\,a\,(x-1)\,]
$$
and
$$
u'(x) = Aa\operatorname{sech}(a) \cosh[\,a\,(x-1)\,]
$$
The BC

$$u'(0) = h$$

then implies
$$
h = Aa\operatorname{sech}(a) \cosh(a) = Aa
$$
so $A = h/a$ and the solution is:

$$
u(x) = \frac{h}{a}\,\operatorname{sech}(a) \sinh[\,a\,(x-1)\,]
$$

The solution to the non-homogeneous ODE
$$
v''(x) = b^2\,v(x) + c\,u(x)
$$
where $b,c \in \mathbb{R}$, subjected to the BCs $v(1) = v'(0) = 0$, is the sum of the general solution of its homogeneous counterpart and a particular solution. The general solution of the homogeneous ODE $v''(x) = b^2\,v(x)$ is, as
before,
$$
v(x) = C\sinh(bx) + D\cosh(bx)
$$
As for a particular solution of $v''(x) = b^2\,v(x) + c\,u(x)$, let's try
$$
v(x) = E\,u(x)
$$
where $E$ is a constant. Then,
$$
v''(x) = b^2\,v(x) + c\,u(x)
\implies
E\,u''(x) = b^2\,E\,u(x) + c\,u(x)
$$
But $u''(x) = a^2\,u(x)$ and we find
$$
E = \frac{c}{a^2 - b^2}
$$
Thus, the general solution of $v''(x) = b^2\,v(x) + c\,u(x)$ is
$$
v(x) = C\sinh(bx) + D\cosh(bx) + \frac{c}{a^2 - b^2}\,u(x)
$$
assuming $a \ne b$. Applying the BC $v(1) = 0$, and using $u(1) = 0$, it follows
$$
D = -C\tanh(b)
$$
so
$$
v(x) = C\operatorname{sech}(b) \sinh[\,b\,(x-1)\,] + \frac{c}{a^2 - b^2}\,u(x)
$$
and
$$
v'(x) = Cb\operatorname{sech}(b) \cosh[\,b\,(x-1)\,] + \frac{c}{a^2 - b^2}\,u'(x)
$$
The BCs $v'(0) = 0$ and $u'(0) = h$ then imply
$$
0 = Cb + \frac{ch}{a^2 - b^2}
$$
from which
$$
C = - \frac{ch}{b}\frac{1}{a^2 - b^2} = \frac{ch}{b}\frac{1}{b^2 - a^2}
$$
Therefore,
$$
v(x) = \frac{ch}{b}\frac{1}{b^2 - a^2}\,\operatorname{sech}(b) \sinh[\,b\,(x-1)\,] + \frac{c}{a^2 - b^2}\,u(x)
$$
which can be rearranged as

$$
v(x) = -\frac{ch}{b^2 - a^2}\,
\left\{\,
\frac{1}{a}\,\operatorname{sech}(a) \sinh[\,a\,(x-1)\,] -
\frac{1}{b}\,\operatorname{sech}(b) \sinh[\,b\,(x-1)\,]
\,\right\}
$$
  where the first term comes from $u(x)$.

The identifications
$$
u \quad\leftrightarrow\quad M_N
$$
$$
a \quad\leftrightarrow\quad \lambda_N
$$
$$
v \quad\leftrightarrow\quad M_{N-1}
$$
$$
b \quad\leftrightarrow\quad \lambda_{N-1}
$$
$$
c \quad\leftrightarrow\quad -\frac{f}{d_{N-1}}
$$
then lead to the result obtained by Mathematica.


TITLE: Definition of functionality
QUESTION [2 upvotes]: Suppose we have the Cartesian product of sets $A$ and $B$. Let $f$ be a subset of $A\times B$. The usual textbook approach to proving that $f$ is a function mapping $A$ to $B$ is to prove that for all $x\in A$, there exists a unique $y \in B$ such that $(x,y)\in f$.
Should you not also have to prove that $A$ is empty or $B$ is non-empty?

REPLY [5 votes]: No. If $A=\varnothing$, then certainly any statement of the form "for all $x\in A$, ____" is true, so any subset of $A\times B=\varnothing\times B=\varnothing$ is a function. Thus, consider the case when $A\neq\varnothing$, i.e. $\exists a\in A$ for some $a$. If one has proven that "for all $x\in A$, there exists a unique $y\in B$ such that $(x,y)\in f$", then in particular, there exists a unique $b\in B$ such that $(a,b)\in f$. For our purposes, we don't care about uniqueness: the fact remains that we have proven that there does exist some $b\in B$, thereby demonstrating that $B\neq\varnothing$.
Thus, proving that "for all $x\in A$, there exists a unique $y\in B$ such that $(x,y)\in f$" does indeed suffice to prove that $f$ is a function: if $A$ is empty, there is no problem, and if $A$ is non-empty, then we can deduce that $B$ is non-empty. So we don't need to prove that "$A$ is empty or $B$ is non-empty" separately.


TITLE: Consecutive integers with no large prime factors
QUESTION [2 upvotes]: I need answer of following Question for my study of an irrational number.
(The raw problem is slightly different.)
Let $k$ be an arbitrary large positive integer, and let $A$ is a positive integer satisfying
$Ce^{2^k}\le A\le Ce^{2^k}$ and have no prime factor larger than $2^k$.(Conventionally, $C$'s are certain positive constants.) Let $y_0$ be a positive integer which suffices $y_0< A$. We now think about $2^k$ products
$$P_s=(y_0+As+1)(y_0+As+2)\cdots(y_0+As+k)\qquad (0\le s< 2^k).$$
Question is "Can we find some $s$'s such that $P_s$ has no prime factor larger than $2^k$?".
It is helpful not only answer for this question, but also introducing relating paper or research.(I can't discover relating research.)
If this question is nonsense or ridicurous, sorry for asking this question.
Sorry, I got some help which asserts some mistakes in my previous question.So probably, this question contains some mistakes. If you discover some of mistakes, it's helpful asserting that.

REPLY [0 votes]: Yuta is correct, Størmer's method, or preferably, D.H. Lehmer's 1963 refinement of that method, applies to a finite set of primes.  If the set contains $k$ primes, then you have $2^k-1$ Pell equations to solve (Størmer's original method involved solving $3^k$ Pell's.

I have had a particular interest in this subject for some years, and have provided most of the high-end values at OEIS, see http://oeis.org/A002072.  I intend to raise some questions arising from this work in a new posting here at mathoverflow.
But to Yuta's original question, the only way I can think of to identify smooth numbers in a particular range is to use a smart sieving algorithm. But if the interval is really large, and the number of primes is also very large, this may not be practical.
By the way, in Lehmer's paper, "Størmer"  appears as "Störmer", I have yet to determine which is correct! I suspect Lehmer was probably correct.


TITLE: How to define $-\infty$?
QUESTION [1 upvotes]: I think I understand the fundamental concept of infinity.
Elementary mathematics define $\infty := \frac{x}{0}$, for every $x$.
And also $\infty := \frac{-x}{0}$ for every $x$.
I know only one definition of $-\infty$ as $-\infty= 0-(\infty)$.
Is there any other way to define $-\infty$?

REPLY [7 votes]: Infinity is not defined in the way you described; something similar can be defined with limits but I think it is a confusing approach.
Here's a more formal definition: $\infty$ and $-\infty$ are points added to $\mathbb{R}$ in such a way the for all $a\in\mathbb{R}$ we have $-\infty < a < \infty$. Topologically speaking, open balls around $\infty$ are subsets of the form $\{x\in\mathbb{R}|x>a\}$ for a given $a$, and open balls around $-\infty$ are subsets of the form $\{x\in\mathbb{R}|x<a\}$.
This allows to formally define concepts like tending to $\infty$ or $-\infty$ with the usual topological approach, and the extanded $\mathbb{R}$ is still a linearly ordered set (although it is no longer a field since arithmetic involving $\infty$ will no longer preserve the nice properties it has in $\mathbb{R}$).

REPLY [3 votes]: $-\infty$ can be defined as the surreal number $\{\emptyset|-\mathbb{N}\}$.

REPLY [0 votes]: In the real line you can "define" $\infty = \frac{1}{0^+}$ and $-\infty = \frac{1}{0^-}$, but these are really limits:  $$-\infty = \lim_{x\to0^-} \frac 1x$$ Here $x\to0^-$ means that $x$ approaches $0$ from the left, i.e., using negative numbers.


TITLE: Is it true that an object, in course of its motion, always seeks the position of minimum potential energy?
QUESTION [0 upvotes]: I have heard the statement, in a Classical mechanics course, that the motion of an object is always toward the position of minimum potential energy. I don't think that this statement correct because I can immediately think of a counter-example. Consider the swing of the bob of a pendulum from the lowest position to one extreme position. During this part of its trajectory, the bob is moving to positions of higher potential energy than the minimum (at the lowest point) due to inertia.
Am I correct? Isn't this statement wrong?

REPLY [3 votes]: In the generality that you stated it, this statement is false. What is true is that on an object always acts a force $F = - \nabla \Phi$ that is the gradient of the Potential. For an object at point $\vec{p}$, the negative gradient points towards a local minimum of the potential. This minimum isn't neccesarily the nearest minimum of the potential, and it's not even given that the potential has a minimum.
However, there is a case in which the statement is true: If you have a dissipative system, that means, the kinetic energy of your object can not only be transfered to potential energy as your object moves in a conservative force-field, but it can also dissipate and just dissappear (due to friction with the ground or surrounding objects or whatever).
In all this cases, your object will eventually come to halt at the position with the lowest potential energy: For example, your pendulum is able to move away from the lowest position, but if you let it swing, it will somewhen stop exactly at the position of minimum potential.
In that sense you could say that "the motion is toward the position of minimum potential energy".


TITLE: How can I give the solutions of $\ x^5-7$?
QUESTION [0 upvotes]: I'm trying to solve the equation $\ x^5-7$, which have complex solutions, how can I calculate the solutions of the equation?
Thank you.

REPLY [0 votes]: Alternative hint (without polar forms and trig):  let $x = \sqrt[5]{7}\,z\,$, then the equation becomes:
$$
z^5 - 1 = 0 \;\;\iff\;\; (z-1)(z^4 + z^3+z^2+z+1) = 0
$$
This gives the root $z=1\,$, and the other $4$ roots can be found by solving the quartic, which reduces to a quadratic in $z+\cfrac{1}{z}\,$:
$$
z^2+z+1+\frac{1}{z}+\frac{1}{z^2}=0 \;\;\iff\;\; \left(z+\frac{1}{z}\right)^2+\left(z+\frac{1}{z}\right)-1=0
$$


TITLE: recureence relation $T(n,m) = 2T(\frac{3n}{2},\frac{m}{2})+O( n^2 )$
QUESTION [1 upvotes]: What is asymptotic order of $T(n,m)$ where
$$T(n,m) = 2T\left(\frac{3n}{2},\frac{m}{2}\right)+O( n^2 )$$

REPLY [1 votes]: If we expand the recurrence relation, we have:
$$T(n, m) = n^2 + 2*(\frac{3}{2})^2*n^2 + 2^2*(\frac{3}{2})^3*n^2 + \dots + 2^{\lg{m}}*((\frac{3}{2})^{\lg{m}})^2*n^2$$
So
$$T(n, m) = n^2 * \Big(\sum_{i = 0}^{\lg{m}}{2^i*\big((\frac{3}{2})^i\big)^2\Big)}=n^2 * \Big(\frac{3*(1-(\frac{3}{2})^{\lg{m}})}{1-\frac{3}{2}}\Big)$$
In the above equation the summation is a geometric series and all log operations are based on 2. At last:
$$T(n, m) = n^2 * \Big(6*\big((\frac{3}{2})^{\lg{m}}-1\big)\Big)=\Theta\Big(n^2*(\frac{3}{2})^{\lg{m}}\Big)$$


text:
\paragraph{Properties of $\OT_{\sigma}$.}

\Cref{thm:otclosedform} shows that $\pi$ has a Gaussian density. \Cref{prop:bures_sinkhorn_matrix_problem} allows to reformulate this optimization problem over couplings in $\RR^{d\times d}$ with a positivity constraint.

\begin{proposition}\label{prop:bures_sinkhorn_matrix_problem}
Let $\alpha = \Ncal(0, \bA), \beta = \Ncal(0, \bB)$, and $\sigma^2 > 0$. Then,

\begin{align}
\OT_\sigma(\alpha, \beta) &=\hspace{-1.5em} \underset{\bC : \left(\begin{smallmatrix} \bA & \bC \\ \bC^T & \bB \end{smallmatrix}\right) \geq 0}{\min}\! \Big\{ \tr(\bA) + \tr(\bB) - 2\tr(\bC) + \sigma^2( \log\det \bA\bB -  \log\det\left(\begin{smallmatrix} \bA & \bC \\ \bC^T & \bB \end{smallmatrix}\right)) \Big\}\label{eq:ent_bures}\\
 &= \underset{\bK \in \RR^{d\times d} : \|\bK\|_{\text{op}} \leq 1}{\min} \tr\bA + \tr\bB - 2 \tr{\bA\rt \bK \bB\rt} - \sigma^2 \ln \det(\Id - \bK \bK^\top).\label{eq:primal_K}
\end{align}

Moreover, both \eqref{eq:ent_bures} and \eqref{eq:primal_K} are convex problems.
\end{proposition}

We now study the convexity and differentiability of $\OT_{\sigma}$, which are more conveniently derived from the dual problem of \eqref{eq:ent_bures} given as a positive definite program:

\begin{proposition}\label{prop:dual_problem}
The dual problem of \eqref{eq:ent_bures} can be written with no duality gap as

\begin{align}\label{eq:dual_ent_bures}
&\underset{\bF, \bG \succ 0}{\max}\Big\{
   \dotp{\Id - \bF}{\bA}  + \dotp{\Id - \bG}{\bB} + \sigma^2\log\det\left(\frac{\bF\bG - \Id}{\sigma^4}\right)  + \sigma^2 \log\det\bA \bB  + 2d\sigma^2\Big\}.
\end{align}

\end{proposition}

\citet{feydy2019} showed that on compact spaces, the gradient of $\OT_{\sigma}$ is given by the optimal dual potentials. This result was later extended by \citet{janati20} to sub-Gaussian measures with unbounded supports. The following proposition re-establishes this statement for Gaussians.
\begin{proposition}\label{prop:envelop_theorem}
Assume $\sigma > 0$ and consider the pair $\bU, \bV$ of \Cref{cor:closedform-potentials}. Then

\begin{itemize}

\item[(i)] The optimal pair $(\bF^*, \bG^*)$ of \eqref{eq:dual_ent_bures} is a solution to the fixed point problem \eqref{eq:optim-fg},

\item[(ii)]
$\mathfrak{B}_{\sigma^2}$ is differentiable and: $\nabla \mathfrak{B}_{\sigma^2}(\bA, \bB) = -(\sigma^2\bU, \sigma^2\bV)$. Thus:
$\nabla_\bA \mathfrak{B}_{\sigma^2}(\bA, \bB) = \Id - \bB\rt\left((\bB\rt\bA\bB\rt + \frac{\sigma^4}{4}\Id)\rt + \frac{\sigma^2}{2}\Id\right)^{-1}\bB\rt$,
\item[(iii)] $(\bA, \bB) \mapsto \mathfrak{B}_{\sigma^2}(\bA, \bB)$ is convex in $\bA$ and in $\bB$ but not jointly.
\item[(iv)] For a fixed $\bB$ with its spectral decomposition $\bB = \bP\Sigma\bP^\top$, the function $\phi_\bB: \bA \mapsto \mathfrak{B}_{\sigma^2}(\bA, \bB)$ is minimized at $\bA_0 = \bP(\Sigma - \sigma^2\Id)_+\bP^\top$ where the thresholding operator $_+$ is defined by $x_+ = \max(x, 0)$ for any $x \in \RR$ and extended element-wise to diagonal matrices.
\end{itemize}
\end{proposition}
When $\bA$ and $\bB$ are not singular, by letting $\sigma\to 0$ in $\nabla_\bA \mathfrak{B}_{\sigma^2}(\bA, \bB)$, we recover the gradient of the Bures metric given in \eqref{eq:bures-gradient}. Moreover, (iv) illustrates the entropy bias of $\mathfrak{B}_{\sigma^2}$. \citet{feydy2019} showed that it can be circumvented by considering the Sinkhorn divergence:
\begin{align}
    \label{eq:def-div}
S_\sigma: (\alpha, \beta) \mapsto \OT_{\sigma}(\alpha, \beta) - \frac{1}{2}( \OT_{\sigma}(\alpha, \alpha) + \OT_{\sigma}(\beta, \beta))
\end{align}
which is non-negative and equals 0 if and only if $\alpha = \beta$. Using the differentiability and convexity of $S_\sigma$ on sub-Gaussian measures~\citep{janati20}, we conclude this section by showing that the debiased Sinkhorn barycenter of Gaussians remains Gaussian:

\begin{theorem}
\label{thm:barycenters}
Consider the restriction of $\OT_\sigma$ to the set of sub-Gaussian measures $\Gcal \defeq \{\mu \in \Pcal_2 | \exists q > 0,\, \Esp_\mu(e^{q\|X\|^2}) < +\infty\}$ and let $K$ Gaussian measures $\alpha_k \sim \Ncal(\ba_k, \bA_k)$ with a sequence of positive weights $(w_k)_k$ summing to 1. Then, the weighted debiased barycenter defined by:
\begin{equation}
\label{eq:def-bar}
    \beta \defeq \argmin_{\beta \in \Gcal} \sum_{k=1}w_k S_\sigma(\alpha_k, \beta)
\end{equation}
is a Gaussian measure given by $\Ncal\left(\sum_{k=1}^K w_k\ba_k, \bB\right)$ where $\bB \in \Scal^d_+$ is a solution of the equation:
\begin{equation}
    \label{eq:bar-fixed-point}
    \sum_{k=1}^K w_k (\bB\rt \bA_k\bB\rt + \frac{\sigma^4}{4}\Id)\rt = (\bB^2 + \frac{\sigma^4}{4}\Id)\rt
\end{equation}
\end{theorem}

config: arxiv


TITLE: Difference in the interpretation of cross-correlation and convolution?
QUESTION [1 upvotes]: I'm confused on the interpretation between convolution and cross-correlation integral transforms. The convolution integral is defined as
$f (t) \otimes g (t) = \int f(\tau) g(t-\tau) d\tau$
and the cross-correlation is defined as
$f (t) * g(t) = \int f^{*}(\tau)g(t+\tau)$
However, when looking up the final interpretation of this result, convolution is cited as saying it is "how one function is shaped by another one" while cross-correlation is "measure of similarity", yet I am confused as to how you can extract two seemingly different interpretations from the formulas above since the difference seems quite small (complex conjugate and no reflection of function $g$).
I've taken a look at it and all I see is that convolution seems to be totally symmetric, since $f\otimes g = g\otimes f$ where as this is not necessarily the case for cross-correlation. Is convolution just a measure of the similarity of the shape only while cross-correlation encompasses both the correlation of the shape and the order at which they come by? I see on wikipedia that cross correlation is the convolution of an adjoint $f$ function but this doesn't help me.

REPLY [1 votes]: I don't know where you got these interpretations from and the context within which they are discussed. On their own, they make little sense indeed. However, they are motivated by the applications that these integrals are used or encountered.
The convolution integral naturally appears in signals and systems theory, when a signal $x(t), t \in \mathbb{R},$ passes through a "linear time invariant filter" (or "channel") with, so called, impulse response $g(t), t \in \mathbb{R}$. The convolution integral provides the output for all $t\in \mathbb{R}$. Many operations in nature such as propagation of electromagnetic signals over a medium have this mathematical representation.
The cross-correlation integral is essentially the inner product of the "vector" $x(\tau), \tau \in \mathbb{R}$ and the "vector" $g(\tau), \tau \in \mathbb{R}$, shifted by $t$. Recall from elementary linear algebra that the inner product of two vectors is a measure of their similarity, thus it makes sense to interpret cross-correlation as such.
Clearly, the two operations are equivalent in the sense that you can always treat cross-correlation as a convolution with an adjoint version of the second function, and vice versa. However, the applications these operations correspond to are so common that it turns out it is more convenient to use both terms to clearly identify what we are talking about.


TITLE: Compute the probability that $\Pr(\tau<\infty)$.
QUESTION [3 upvotes]: Let $B$ and $W$ be independent symmetric random walks starting at $0$ with filtration $\mathcal F_0=\{\emptyset,\Omega\}$ and $\mathcal F_n=\sigma(B_1,...,B_n,W_1,...,W_n)$.
Define $\mathcal E(B)_n=e^{B_n}(\cosh 1)^{-n}$ and $\mathcal E(W)_n=e^{W_n}(\cosh 1)^{-n}$ for all $n\ge 0$.
Also let $\tau=\inf\{n:\mathcal E(B)_n\le\frac 12\},\sigma=\inf\{n:\mathcal E(W)_n\ge 2\}$.
(a) Calculate $\Pr(\tau<\infty)$ and show that $\Pr(\sigma<\infty)\in (0,1)$.
(b) Which of the following three processes are uniformly integrable martingales:
$$\mathcal E (B)^{\sigma\wedge\tau},\mathcal E(W)^{\sigma\wedge\tau},\mathcal E (B)^{\sigma\wedge\tau}\mathcal E(W)^{\sigma\wedge\tau}.$$

We can write
\begin{align}
\Pr(\tau<\infty)&=1-\Pr(\mathcal E(B)_n>\frac 12\text{ for all }n).
\end{align}
But then how to proceed. I have no idea why we are trying to compute $\mathcal E(B)_n$ and neither do I know how to compute this probability. Can someone give me a hint? Thank you!

Edit:
I have a rough idea but it still does not work. We need to involve $\Pr(\tau<\infty)$.
Firstly, it is easy to show that $\mathcal E(B)_n,\mathcal E(W)_n$ are martingales. Secondly, it is easy to see that $\tau,\sigma$ are stopping times with respect to the filtration $\mathcal \{F_n\}_{n\in\mathbb Z_{>0}} $ . So I want to use the Optimal Stopping Theorem. Note that
\begin{align}
\mathbb E[\mathcal E(B)_\tau]&=\mathbb E[\lim_{n\to\infty}\mathcal E(B)_{n\wedge\tau}].
\end{align}
By Fatou's lemma, $$\mathbb E[\lim_{n\to\infty}\mathcal E(B)_{n\wedge\tau}]\le\liminf_{n\to\infty}\mathbb E[\mathcal E(B)_{n\wedge\tau}].$$
Since $\mathcal E(B)_n$ is a martingale, we have
$$ \mathbb E[\mathcal E(B)_{n\wedge\tau}]=\mathbb E[\mathcal E(B)_{0\wedge\tau}]=1. $$
So $1\ge \mathbb E[\mathcal E(B)_\tau].$
Write $\mathbb E[\mathcal E(B)_\tau]=\mathbb E[\mathcal E(B)_\tau 1_{\tau<\infty}+\mathcal E(B)_\tau 1_{\tau=\infty}]=\mathbb E[\mathcal E(B)_\tau;\tau<\infty]+\mathbb E[\mathcal E(B)_\tau;\tau=\infty].$

Remark: Note that we have applied Fatou's lemma, but we cannot apply the dominated convergence to get equality, since the random walk can visit any big number before it returns to some point such that $\mathcal E(B)_n\le\frac 12$.

REPLY [2 votes]: I will write $M_n$ for $\mathcal{E}(B)_n$ to save typing.  I claim $M_n \to 0$ almost surely.
Note that $M_n$ is a positive martingale so it converges almost surely to some limiting nonnegative random variable $M$.  On the event $\{M > 0\}$, we have $\frac{M_{n+1}}{M_n} \to 1$ a.s.  But $\frac{M_{n+1}}{M_n}$ can only have the values $\frac{1}{\cosh 1} e^{\pm 1}$ so it cannot converge to 1.  Therefore $P(M > 0) = 0$ and so $M_n \to 0$ almost surely.
In particular, almost surely we have $M_n \le 1/2$ for all sufficiently large $n$, and thus $\tau < \infty$.
As for $\sigma$ (which I will think of as a stopping time for $B$ instead of $W$), by optional stopping we have $E[M_{\sigma \wedge n}] = 1$, and so by dominated convergence $E[\lim_{n \to \infty} M_{\sigma \wedge n}] = 1$ as well.  If $\sigma < \infty$ a.s., we have $M_{\sigma \wedge n} \to M_\sigma \ge 2$ and this is absurd, as you noted.  If $\sigma = \infty$ a.s., we have $\lim_{n \to \infty} M_{\sigma \wedge n} = \lim_{n \to \infty} M_n =0$ which is also absurd.

Some hints on (b):

Suppose $\mathcal{E}(B)^{\sigma \wedge \tau}$ were uniformly integrable. Since $\sigma$ is independent of $B$ and $\tau$, for each $0 \le k \le \infty$ we have $E[\mathcal{E}(B)^{\sigma \wedge \tau}_\infty \mid \sigma=k] = E[\mathcal{E}(B)_\infty^{k \wedge \tau}]$.  Compute this for each $k$ and write $$E[\mathcal{E}(B)_\infty^{\sigma \wedge \tau}] = \sum_{0 \le k \le \infty} E[\mathcal{E}(B)^{\sigma \wedge \tau}_\infty \mid \sigma=k] P(\sigma = k).$$

$\mathcal{E}(W)^\sigma$ is uniformly integrable, and $\sigma \wedge \tau \le \sigma$.

No ideas about the third one.


TITLE: Is $\text{rank}((T^*T)^{\frac{1}{2}})=\text{rank}(T)$?
QUESTION [1 upvotes]: I've come across the following while solving a specific problem. To conclude that original problem I need to (dis)prove the following:

Suppose $\mathcal{H}$ is a complex Hilbert space and $T \in \mathcal{B}(\mathcal{H})$. Then is it true that $$\text{rank}((T^*T)^{\frac{1}{2}})=\text{rank}(T)$$

I haven't done any satisfactory progress here. Any help is appreciated. Thank you.
Edit. Let me mention how did I come to this problem:
Initially wanted to find all $T \in \mathcal{B}(\mathcal{H})$ such that $T$ is Hilbert-Schmidt operator and $||T||_{op}=||T||_{2}$, where $||T||_{2}$ denotes the Hilbert-Schmidt norm of $T$.
The 'rank one' operators are such operators. But I wonder whether these are the only such operators.
So I assumed $T\in \mathcal{B}(\mathcal{H})$ such that $||T||_{op}=||T||_{2}<\infty$ and then my claim is rank$(T)=1$.
I've managed to prove this under the additional assumption that '$T$ is self-adjoint': i.e., if $T^*=T$ and $||T||_{op}=||T||_{2}<\infty$ then rank$(T)=1$.
For the general case, I considered $A:=(T^*T)^{1/2}$. Then by the assumption on $T$ (i.e., $||T||_{op}=||T||_{2}<\infty$) have
$$||A||_{op}=||T||_{op}=||T||_2=||A||_2$$. Then I concluded that $\text{rank}((T^*T)^{1/2})=\text{rank}(A)=1$ (since $A$ is self-adjoint and satisfies $||A||_{op}=||A||_2<\infty$). But does this imply $\text{rank}(T)=1$?

REPLY [0 votes]: It's true.  Let $\operatorname{Dom}(T) = \operatorname{Ker}(T)^\perp$.  Then any bounded operator has a polar decomposition $T=U|T|$ where $|T|=\sqrt{T^* T}$ is positive semi-definite and $\operatorname{Dom}(|T|)=\operatorname{Dom}(T)$.  $U$ is a partial isometry from $\operatorname{Dom}(T)$ to $\operatorname{closure}(\operatorname{Range}(T))$.
Edit: The part you need is simple to show.  For any vector $x$
$$||Tx||^2 = \langle Tx,Tx\rangle=\langle T^*Tx,x\rangle=\langle |T|^2x,x\rangle=\langle |T|x,|T|x \rangle=|| |T|x||^2$$
which proves that $\operatorname{Ker}(T)=\operatorname{Ker}(|T|)$ so $T$ and $|T|$ have the same domain.  You can also see from this identity that if a $U$ exists that maps $|T|x$ to $Tx$, it has to be an isometry because they have the same norm.  The rank you are taking about is the dimension of the domain or the dimension of the closure of the range.  They are the same dimension, even if infinite.


TITLE: Behaviour of conductor moving in a magnetic field after a long time
QUESTION [0 upvotes]: In the above figure, we have a rod moving with some speed in $v$ in a magnetic field $B$, it is said that when at equilibrium the rod generates a surface charge density such that the magnetic field must be cancelled off.
However, I do not understand why this must be the equilibrium state, so this leads to my question, How do you prove that  the equilibrium condition for the system is that a charge density is developed on the body of conductor such that the electrostatic force on conductor cancels the magnetic force?
related
Addendum: Ignore fringe effects and Eddie currents

REPLY [0 votes]: If the magnetic force is not cancelled by the electric force there is no equilibrium, so the charges will move until there is.


TITLE: Negative inverse trig functions
QUESTION [1 upvotes]: I was practising my integration earlier and for one question I got $-\arccos(x - 2)$, while the book has $\arccos(2 - x)$.
The answers seems so close and I was wondering (a) am I right? But more importantly, (b) is there some relationship between $-\arccos(-x)$ and $\arccos x$. More generally, is there a relationship between inverse trig functions and their negatives and what is it?

REPLY [0 votes]: Inorder to understand the relationship between $\text{trig}^{-1}(x)$ and $\text{trig}^{-1}(-x)$ where $\text{trig}(x)$ is any fundamental trigonometric function, one must first come to terms with the relationship between $\text{trig(x)}$ and $\text{trig}(-x)$ which is as follows:
$$\sin(-x) = -\sin(x)\\
\cos(-x) = \cos(x)\\
\tan(-x) = -\tan(x)$$
The above is a direct result of the trig functions being either even or odd functions.
For an even function (where graph is symmetric about the y-axis), $f(-x) = f(x)$ while for an odd function (where graph is symmetric about the origin): $f(-x) = -f(x)$
If you are to draw the inverse of the graphs of the above function (Just constrict to suitable domain and reflect about $y=x$ line)http://www.purplemath.com/modules/invrsfcn.htm
Then, hopefully the relationships will be obvious from the graphs.


TITLE: Eigenvalues and eigenvectors of $I+uv^T$
QUESTION [0 upvotes]: Let u and v be two non-zero vectors in $R^n$.
Let A=I+u$v^T$.
First we show that u$v^T$ is symmetric iff u=cu.
Second question: Assume $v^T$u=-1, Find the spectrum of A=I+u$v^T$ in addition to its corresponding eigenvectors and conclude that the matrix A is not invertible.
How to solve the second question?
I started with (I+u$v^T$)(I-u$v^T$)=I+u$v^T$ after using the assumption..

REPLY [1 votes]: First of all note that $u$ is an eigenvector of $A$
$$Au=(I+uv^T)u=(1+v^Tu)u$$
Now think about what happens when $v^Tu=-1$.
Note. Other eigenvectors are the vectors that are orthogonal to $v$ with eigenvalue $1$.


TITLE: A small doubt related to Hatcher Example 2.31.
QUESTION [0 upvotes]: I have a small doubt related to the example 2.31. of Hatcher Algebraic Topology. I am wariting the passage below.
Let $k\in \Bbb N$ and $q:S^n\to {\large\lor}_kS^n$ be the quotient map obtained by collapsing the complement of $k$ disjoint open balls $B_i$ in $S^n$ to a point. Also let $p:{\large\lor}_kS^n\to S^n$ identify all the summands to a single sphere. Consider $f=pq$. Now for almost all $y\in S^n$ we have $f^{-1}(y)$ consisting of one point $x_i$ in each $B_i$.
My question is the words almost all can be replaced by the words all but one. I mean we can write, for all but one point (here one refers to the wedge point) $y\in S^n$ we have $f^{-1}(y)$ consisting of one point $x_i$ in each $B_i$. Am I right? Thanks in advance.

REPLY [1 votes]: This community wiki solution is intended to clear the question from the unanswered queue.
Yes, you are right.


text:
\begin{document}

\begin{abstract}
Using the pfaffian structure of the generating series for locally orientable maps, we show that the generating series satsifies a nonlinear differential
equation called the BKP equation. Using this we are able to derive a cubic differential equation which is satisfied by the generating series for
locally orientable triangulations. As a result, we prove a conjecture of Garoufalidis and Mari\~no concerning the constant $p_g$ which appears in
asymptotic formulas for a variety of rooted maps on non-orientable surfaces. This allows one to determine the asymptotic expansion for $p_g$ up to
an unknown Stokes constant.
\end{abstract}

\maketitle

\section{Introduction}

A map is a connected graph embedded in a compact connected surface in such a way that the regions delimited by the graph, called faces, are homeomorphic to open discs.
Loops and multiple edges are allowed. A rooted map is one in which an angular sector incident to a vertex is distinguished, and the latter is called the root vertex.
The root edge is the edge encountered when traversing the distinguished angular sector clockwise around the root vertex. We say that a map is orientable, non-orientable
or locally orientable if the same is true of the underlying surface.

In \cite{BC86}, Bender and Canfield studied the number $T_g(n)$ of $n$-edged rooted maps on an orientable surface of type $g$ and the number $P_g(n)$ of $n$-edged rooted
maps on a non-orientable surface of type $g$. They showed that asymptotically the numbers behaved as
	\begin{align*}
		T_g(n)	&\sim t_g n^{5(g-1)/2} 12^n, \\
		P_g(n)  &\sim p_g n^{5(g-1)/2} 12^n, \mbox{ when } g > 0,
	\end{align*}
where $t_g$ and $p_g$ are constants which depend only on $g$. Unfortunately, determining the constants $t_g$ and $p_g$ proved to be very difficult. Later, Gao\cite{G93}
showed that if $C$ denotes a class of rooted maps (for example, 2-connected, triangulations and $2d$-regular) and $M_g(C,n)$ is the number of maps in class $C$ which
are of type $g$ and which have $n$ edges then for many such classes,
	\[ M_g(C,n) \sim \al t_g (\be n)^{5(g-1)/2}\ga^n, \]
if the maps are orientable and
	\[ M_g(C,n) \sim \al p_g (\be n)^{5(g-1)/2}\ga^n, \]
if the maps are non-orientable. Here $\al, \be$ and $\ga$ depend on the class of maps considered.

Goulden and Jackson\cite{GJ08} showed that the number of rooted orientable triangulations satisfies a quadratic recurrence equation. Equivalently, this
implies that the generating series for rooted orientable triangulations satisfies a quadratic differential equation. Goulden and Jackson proved this using the
fact that the generating series for rooted maps with respect to vertex degrees satisfies a family of differential equations known as the KP hierarchy,
essentially coming from the fact that the generating series in question has a determinantal structure (the Schur function expansion has coefficients which
satisfy the Pl\"ucker relations). Using this quadratic differential equation and the fact that the class of triangulations has the asymptotic behaviour described
by Gao, it was shown by Bender, Richmond and Gao\cite{BRG08} that the map asymptotics constants $t_g$ satisfied a quadratic recurrence. It was then shown by
Garoufalidis, L\^e and Mari\~no\cite{GLM08} that the scaled generating series for the map asymptotics constant $t_g$ satisfied a quadratic
differential equation equivalent to the Painlev\'e I equation. In particular they showed that if $u_g = - 2^{g-2} \Gamma\left( \frac{5g-1}{2} \right) t_g$ then the series
	\[ u(z) = z^{1/2} \sum_{g=0}^\infty u_g z^{-5g/2}, \]
satisfies
	\[ u^2 - \frac{1}{6}u'' = z. \]

By analogy to the orientable case and motivated by some results in mathematical physics concerning integrals over real symmetric matrices, Garoufalidis and Mari\~no\cite{GM10}
conjecture that similar to the series $u(z)$ above, the scaled generating series for the non-orientable map asymptotics constants also satisfies a simple differential
equation. The main result of this paper is the following which appears as Conjecture 1 in Garoufalidis and Mari\~no\cite{GM10}.
\begin{thm}\label{p_gTheorem}
	Let
		\[ v_g = 2^{\frac{g-3}{2}} \Gamma\left( \frac{5g-1}{4} \right) p_{\frac{g+1}{2}}. \]
	The series
		\[ v(z) = z^{1/4}\sum_{g=0}^\infty v_g z^{-5g/4} \]
	satisfies the differential equation
		\[ 2v' - v^2 + 3u = 0, \]
	where the series $u$ is the same as the series $u$ above.
\end{thm}

One of the main advantages to the differential equations satisfied by the generating series for the $t_g$ and $p_g$ constants is that they can be used to determine
the corresponding asymptotic behaviour. The differential equation for $u(z)$ was used by Garoufalidis, L\^e and Mari\~no\cite{GLM08} to determine the asymptotic
behaviour of $t_g$ to all orders. In particular, the following Theorem is proven in Appendix A of \cite{GLM08}.
\begin{thm}\label{t_gTheorem}
Suppose the series
	\[ u(z) = z^{1/2} \sum_{g=0}^\infty u_g z^{-5g/2} \]
satisfies
	\[ u^2 - \frac{1}{6}u'' = z. \]
Then as $g \to \infty$,
	\[ u_g \sim A^{-2g + \frac{1}{2}} \Gamma\left( 2g - \frac{1}{2} \right) \frac{S}{2\pi i} \left\{ 1 + \sum_{\ell = 1}^\infty \frac{\mu_\ell A^\ell}{\prod_{m=1}^\ell (2g - 1/2 - m)} \right\}, \]
where $A = \frac{8\sqrt{3}}{5}, S = -i\frac{3^{\frac{1}{4}}}{\sqrt{\pi}}$ and the $\mu_\ell$ are defined by the recursion relation
	\[ \mu_\ell = \frac{5}{16 \sqrt{3}\ell} \left\{ \frac{192}{25} \sum_{k=0}^{\ell - 1} \mu_k u_{(\ell - k + 1)/2} - \left( \ell - \frac{9}{10} \right)\left( \ell - \frac{1}{10} \right)\mu_{\ell-1} \right\}, \qquad \mu_0 = 1, \]
with the convention that $u_{n/2} = 0$ if $n$ is odd.
\end{thm}

Similarly, the differential equation in Theorem~\ref{p_gTheorem} was used by Garoufalidis and Mari\~no\cite{GM10} to determine the complete asymptotic behaviour of $v_g$ and hence,
by Theorem~\ref{p_gTheorem}, $p_g$ up to an unknown constant $S'$. The complete details can be found in Garoufalidis and Mari\~no\cite{GM10} and the following
appears as Theorem 1 in \cite{GM10}.
\begin{thm}\label{p_gAsymptotics}
Suppose the series
	\[ v(z) = z^{1/4}\sum_{g=0}^\infty v_g z^{-5g/4} \]
satisfies the differential equation
	\[ 2v' - v^2 + 3u = 0, \]
where $u(z)$ is the series described in Theorem~\ref{t_gTheorem}. Then the sequence $v_g$ has an asymptotic expansion of the form
	\[ v_g \sim (A/2)^{-g} \Gamma(g) \frac{S'}{2 \pi i} \left\{ 1 + \sum_{\ell = 1}^\infty \frac{\nu_\ell(A/2)^\ell}{\prod_{m=1}^\ell (g-m)} \right\}, \]
where $A$ is given in Theorem~\ref{t_gTheorem}, $S' \not = 0$ is some non-zero Stokes constant, and the sequence $\nu_\ell$ is defined by the recursion relation
	\[ \nu_\ell = -\frac{4}{5\ell} \sum_{k=0}^{\ell-1} v_{\ell + 1 - k}\nu_k, \qquad \nu_0 = 1. \]
\end{thm}

The rest of this paper is organized as follows. In Section 2 we discuss how the generating series for locally orientable maps (a combination of both orientable and
non-orientable) has a pfaffian structure. This is in analogy with the generating series for orientable maps which has a determinantal structure. As a result we
show that the locally orientable map series satisfies the BKP equation, a pfaffian analog of the KP equation. In addition, we discuss some linear differential
equations which are satisfied by the locally orientable map series which follow by considering the removal of vertices with degree one or two. In Section 3 we
use the differential equations described in Section 2 to derive a cubic differential equation for the specialization of the locally orientable map series to
triangulations. In Section 4 we give a structural result for $\Lt_g(z)$, the generating series for locally orientable triangulations. In particular, we show that
it can be written as a rational series in terms of an auxilliary algebraic series. This type of structure seems to arise frequently in map enumeration and in
permutation factorization problems as in, for example, Goulden, Guay-Paquet and Novak's work on monotone Hurwtiz numbers\cite{GGN13}, however the reason for this
is not clear. Lastly, in Section 5, we combine the structure theorem and the cubic differential equation to derive some results about the asymptotic behaviour
of locally orientable triangulations. As an application, we are able to prove Garoufalidis and Mari\~no's conjecture about the non-orientable map asymptotics constants.

\section{Symmetric Matrix Integrals and Locally Orientable Maps}

We define an averaging (expectation) operator over $\bbR^N$ as follows:
	\[ \langle f(\lambda) \rangle_N = \frac{1}{N!} \int_{\bbR^N} |V(\la)| f(\lambda) \exp \left( \frac{-p_2(\la)}{4} \right) d\lambda. \]
Here $V(\lambda)$ is the Vandermonde determinant and $p_k(\lambda)$ is the $k$th power sum symmetric function. They are given by
	\[ V(\lambda) = \prod_{1 \leq i < j \leq N} (\la_i - \la_j) \qquad \mbox{ and } \qquad p_k(\lambda) = \sum_{1 \leq i \leq N} \la_i^k. \]
This averaging operator is related to a similar operator over the vector space $W_N$ of all $N \times N$ real symmetric matrices $M \in W_N$ with measure
$e^{-\Tr M^2/4}$. In fact, up to a multiplicative constant,
	\[ \langle f(\lambda) \rangle_{N} = \int_{W_N} f(M) e^{-\Tr M^2/4} dM. \]
This relationship follows from the fact that the integrand is conjugation invariant and so we may use the polar decomposition for real symmetric matrices
to reduce the integral to one over $\bbR^N$.

\begin{thm}[Kakei\cite{K99}, Van de Leur\cite{VdL01}, Adler and Moerbeke\cite{AM01}] \label{BKP}
	Suppose
		\[ Z_N = \left\langle \exp\left( \sum_{k \geq 1} \frac{p_k(\lambda)}{2k} t_k \right) \right\rangle_N. \]
	Then
		\[ (\del_1^4 + 3\del_2^2 + 3\del_3\del_1) \log Z_N + 6(\del_1^2 \log Z_N)^2 = 3 \frac{Z_{N+2} Z_{N-2}}{Z_N^2}. \]
\end{thm}
\begin{proof}
	The differential equation which $Z_N$ satisfies is known as the BKP equation and is one of many in the BKP hierarchy. Adler and Moerbeke\cite{AM01} showed that for
	even $N$ the $Z_N$ satisfies each of the differential equations in the BKP hierarchy. Van de Leur\cite{VdL01} then generalized this result to any $N$. In both cases
	the authors used the Fock space approach to integrable hierarchies. For our purposes it will suffice to show that for even $N$,  $Z_N$ satisfies the BKP equation.
	In this case there is a direct proof as shown by Kakei\cite{K99} and which can also be found in Hirota\cite{H04}.

	For the remainder of this proof we will work with $2N$ rather than $N$. Note that this is sufficient for our purposes since the particular integral which
	we are interested in (Theorem~\ref{MtxIntegral}) is a series with coefficients which are polynomial in $N$ (see Remark~\ref{polynomiality}).
	Recall that given a $2N \times 2N$ antisymmetric matrix $A_{2N} = [a_{i,j}]_{1 \leq i,j \leq 2N}$ we may define the pfaffian as
		\[ \Pf(A_{2N}) = \sum \sgn\left( \begin{array}{cccc} 1 & 2 & \cdots & 2N \\ j_1 & j_2 & \cdots & j_{2N} \end{array} \right) a_{j_1,j_2} a_{j_3,j_4} \cdots a_{j_{2N-1},j_{2N}}, \]
	where the summation is over all $(j_1, \cdots j_{2N})$ such that $j_1 < j_3 < \cdots < j_{2N-1}$ and $j_1 < j_2, \cdots, j_{2N-1} < j_{2N}$. For our purposes
	it will be more convenient to write the pfaffian in a different way. Given a pairing $(i,j)$ we define a pfaffian corresponding to a sequence $(a_1, a_2, \cdots, a_{2m})$ as
		\[ (a_1, a_2, \cdots, a_{2m}) = \sum_{j=2}^{2m} (-1)^j (a_1, a_j)(a_2, a_3, \cdots, \widehat{a_j}, \cdots, a_{2m}), \]
	where $\widehat{a_j}$ means that $a_j$ is omitted.

	Using a Theorem of de Bruijn\cite{dB55} (this can also be found in Mehta\cite{M04}), we may write $Z_{2N}$ as a pfaffian. In particular,
		\[ Z_{2N} = \Pf \left[ \mu_{i,j}(t) \right]_{1 \leq i,j \leq 2N}, \]
	where
		\[ \mu_{i,j}(t) = \mathop{\int \int}_{x < y} \left( x^{i-1} y^{j-1} - y^{i-1} x^{j-1} \right) \exp \left( \frac{-x^2 - y^2}{4} + \sum_{k \geq 1} \frac{x^k + y^k}{2k} t_k \right). \]
	Similarly, we may write
		\[ Z_{2N} = (1, 2, \cdots, 2N), \]
	with the pairing given by $(i,j) = \mu_{i,j}(t)$.

	We may also check that for any positive integer $k$,
		\[ 2k \frac{\del}{\del t_k} \mu_{i,j}(t) = \mu_{i+k,j}(t) + \mu_{i,j+k}(t). \]
	Using the linear differential equation satisfied by the entries of the pfaffian corresponding to $Z_{2N}$ we may find identities which are satisfied by $Z_{2N}$ itself. In particular,
	it follows that
		\[ 2k \frac{\del}{\del t_k} (a_1, a_2, \cdots, a_{2N}) = \sum_{j = 1}^{2N} (a_1, a_2, \cdots, a_{j+k}, \cdots, a_{2N}). \]

	Furthermore, it is straightforward to show that pfaffians satisfy the identities
		\begin{align*}
			(a_1, a_2, \cdots, a_{2m}, & 1, 2, \cdots, 2n)(1, 2, \cdots, 2n) = \\
									   & \sum_{j=2}^{2m} (-1)^j (a_1, a_j, 1, 2, \cdots, 2n)(a_2, a_2, \cdots, \widehat{a_j}, \cdots, a_{2m}, 1, 2, \cdots, 2n),
		\end{align*}
	where $\widehat{a_j}$ means that $a_j$ is omitted. Using this pfaffian identity and the linear differential equations satisfied by $Z_{2N}$ the result follows.
\end{proof}

\begin{thm}[Mehta\cite{M04}, Van de Leur\cite{VdL01}, Adler and Moerbeke\cite{AM01}] \label{Virasoro}
	Suppose
		\[ Z_N = \left\langle \exp\left( \sum_{k \geq 1} \frac{p_k(\lambda)}{2k} t_k \right) \right\rangle_N. \]
	Then
		\[ \del_1 \log Z_N = \sum_{i \geq 1} i t_{i+1} \del_i \log Z_N + \frac{N t_1}{2}, \]
	and
		\[ \del_2 \log Z_N = \sum_{i \geq 1} \frac{i}{2} t_i \del_i \log Z_N + \frac{N(N+1)}{4}. \]
\end{thm}
\begin{proof}
	This can be shown directly using the fact that the integration measure is translation invariant and the details of this method can be found in Mehta\cite{M04}. Alternate proofs using
	Fock space methods can be found in Van de Leur\cite{VdL01} and Adler and Moerbeke\cite{AM01}.

	For our purposes, via Theorem~\ref{MtxIntegral}, the series of interest is a generating series for rooted maps. In this case, the two equations correspond to adding / removing
	a vertex of degree one and adding / removing a vertex of degree two.
\end{proof}

Let $\ell_{k,\al}$ be the number of locally orientable maps with $k$ faces and vertex partition given by $\al$. Then the genus series for maps in locally orientable surfaces is defined to be
	\[ L(t;y) = \sum_{k \geq 1} \sum_{\al} \ell_{k,\al} y^k t_\al. \]
\begin{rmk} \label{polynomiality}
	Let \[ \ell_\al(y) = [t_\al] L(t;y) = \sum_{k\geq 1} \ell_{k,\al}y^k. \] Then, since for any fixed map the sum of the vertex degrees is equal to the sum of the face degrees, we must
	have $k \leq |\al|$. Thus, each $\ell_{\al}(y)$ is a polynomial in $y$.
\end{rmk}

\begin{thm}[Goulden and Jackson\cite{GJ97}] \label{MtxIntegral}
	For any positive integer $N$,
		\[ L(t; N) = 2 E \log \left\langle \exp\left( \sum_{k \geq 1} \frac{p_k(\lambda)}{2k} t_k \right) \right\rangle_N, \]
	where
		\[ E = \sum_{k \geq 1} k t_k \del_k. \]
\end{thm}

In particular, Theorem~\ref{MtxIntegral} above implies that the differential equations in Theorem~\ref{BKP} and Theorem~\ref{Virasoro} are also satisfied by the generating
series for locally orientable maps. This collection of differential equations is the primary tool used in the remainder of this paper.

\section{A Cubic Differential Equation for Triangulations}

Let $\Lt(x,y) = \left. L(t;y) \right|_{t_i = x \delta_{i,3}}$. That is, let $\Lt(x,y)$ be the generating series for locally orientable cubic maps. Similarly, let $\Lt(x;w)$ be the generating series
for locally orientable cubic maps with vertices marked by $x$ and Euler characteristic marked by $w$. By Euler's formula,
	\[ \Lt(x;w) = w^2 \left. \Lt(x,y) \right|_{x \mapsto xw^{1/2}, y \mapsto w^{-1}}. \]
We begin by using Theorem~\ref{BKP} and Theorem~\ref{Virasoro} to derive a cubic differential equation for $\Lt(x;w)$.

\begin{thm} \label{MasterEquationGenus}
	Let
	\begin{align*}
		T &= \Lt(x;w) + w + 1 - \frac{1}{2x^2}, \\
		V &= w^{-2}\left( (1+2w)^2 \Lt\left( x(1+2w)^{1/2}, \frac{w}{1+2w} \right) \right. \\
		  & \qquad \left. + (1-2w)^2 \Lt\left(x(1-2w)^{1/2}, \frac{w}{1-2w}\right) - 2\Lt(x;w) \right).
	\end{align*}
	Then
	\begin{align*}
		4x^4 & w^2 (D+12)^2 (D+8)(D+4)T - (D+6)DT + 12x^4(D+12)((D+4)T)^2 \\
					 &= V \left( 2x^4w^2(D+12)(D+8)(D+4)T - \frac{1}{2}(D+6)T + 6x^4((D+4)T)^2 \right).
	\end{align*}
\end{thm}
\begin{proof}
	Recall from Theorem~\ref{Virasoro} that if
		\[ Z_N = \left\langle \exp\left( \sum_{k \geq 1} \frac{p_k(\lambda)}{2k} t_k \right) \right\rangle_N, \]
	then
		\begin{align*}
			\del_1 \log Z_N	&= \sum_{i \geq 1} i t_{i+1} \del_i \log Z_N + \frac{N t_1}{2}, \\
			\del_2 \log Z_N &= \sum_{i \geq 1} \frac{i}{2} t_i \del_i \log Z_N + \frac{N(N+1)}{4},
		\end{align*}
	and (from Theorem~\ref{BKP}) that
		\[ (\del_1^4 + 3\del_2^2 - 3\del_3\del_1)\log Z_N + 6(\del_1^2 \log Z_N)^2 = \frac{3}{4} \frac{Z_{N+2}Z_{N-2}}{Z_N^2}. \]
	Let $Y_N = \left. \log Z_N \right|_{t_i = 0, i > 3}$. Then the equations above imply that
		\begin{align}
			\del_1 Y_N &= t_2 \del_1 Y_N + 2 t_3 \del_2 Y_N + \frac{N t_1}{2}, \label{Vir1} \\
			\del_2 Y_N &= \frac{1}{2} t_1 \del_1 Y_N + t_2 \del_2 Y_N + \frac{3}{2} t_3 \del_3 Y_N + \frac{N(N+1)}{4}, \label{Vir2} \\
			\del_1^4 Y_N &+ 3\del_2^2 Y_N - 3\del_3 \del_1 Y_N + 6(\del_1^2 Y_N)^2 = \frac{3}{4} \exp(Y_{N+2} + Y_{N-2} - 2Y_N). \label{BKP2}
		\end{align}
	The $\del_2 Y_N$ term can be eliminated from \eqref{Vir1} using \eqref{Vir2} and similarly the $\del_1 Y_N$ term can be eliminated from \eqref{Vir2} using \eqref{Vir1}. Letting $D = 3 t_3 \del_3$ this gives
		\begin{align}
			\del_1 Y_N	&= \frac{t_3}{A(1-t_2)} D Y_N + C, \label{mVir1} \\
			\del_2 Y_N  &= \frac{1}{2A} D Y_N + \frac{B}{A}, \label{mVir2}
		\end{align}
	where
		\begin{align*}
			A	&= 1 - \frac{t_1 t_3}{1 - t_2} - t_2, \\
			B	&= \frac{Nt_1^2}{4(1-t_2)} + \frac{N(N+1)}{4},
		\end{align*}
	and
		\[ C = \frac{2t_3B}{A(1-t_2)} + \frac{Nt_1}{2(1-t_2)}. \]
	Letting $T = \left. 2DY_n \right|_{t_i = x\delta_{i,3}} + N(N+1) - \frac{N}{2x^2} = L^{(3)}(x,N) + N(N+1) - \frac{N}{2x^2}$ (the second equality follows from Theorem~\ref{MtxIntegral}), \eqref{mVir1} and
	\eqref{mVir2} can be used to determine
		\begin{align}
			\left. \del_1^2 Y_N \right|_{t_i = x \delta_{i,3}}	&= \frac{x^2}{2}(D+4)T, \label{Y11} \\
			\left. \del_1^4 Y_N \right|_{t_i = x \delta_{i,3}}	&= \frac{x^4}{2}(D+12)(D+8)(D+4) T, \label{Y1111} \\
			\left. \del_2^2 Y_N \right|_{t_i = x \delta_{i,3}}	&= \frac{1}{8}(D+2)T - \frac{N}{4x^2}, \label{Y22} \\
			\left. \del_1\del_3 Y_N \right|_{t_i = x \delta_{i,3}} &= \frac{1}{6}(D+3)T - \frac{N}{4x^2}, \label{Y13}
		\end{align}
	where now $D = 3x\del_x$. Using the equations above, \eqref{BKP2} becomes
		\begin{align*}
			\frac{x^4}{2} & (D+12) (D+8)(D+4)T + \frac{3}{8}(D+2)T - \frac{3}{4}\frac{N}{x^2} - \frac{1}{2}(D+3)T + \frac{3}{4}\frac{N}{x^2} \\
			                     & + 6\left( \frac{x^2}{2}(D+4)T \right)^2 = \frac{3}{4} \left( \left. Y_{N+2} \right|_{t_i = x\delta_{i,3}} + \left. Y_{N-2} \right|_{t_i = x\delta_{i,3}} - \left. 2Y_N \right|_{t_i = x\delta_{i,3}} \right).
		\end{align*}
	Simplifying, this becomes
		\begin{align*}
			2x^4(D+12) & (D+8)(D+4)T - \frac{1}{2}(D+6)T + 6x^2((D+4)T)^2 \\
			           &= \frac{3}{4} \left( \left. Y_{N+2} \right|_{t_i = x\delta_{i,3}} + \left. Y_{N-2} \right|_{t_i = x\delta_{i,3}} - \left. 2Y_{N} \right|_{t_i = x\delta_{i,3}} \right).
		\end{align*}
	Applying the operator $2D$ to both sides of this equation gives
		\begin{align}
			4x^4 & (D+12)^2(D+8)(D+4)T - (D+6)DT + 12x^4(D+12)((D+4)T)^2 \notag \\
									& = V(2x^4(D+12)(D+8)(D+4)T - \frac{1}{2}(D+6)T + 6x^4((D+4)T)^2), \label{mEquation1}
		\end{align}
	where
		\begin{align*}
			V	&= 2D\left. Y_{N+2} \right|_{t_i = x\delta_{i,3}} + 2D \left. Y_{N-2} \right|_{t_i = x\delta_{i,3}} - 4D \left. Y_{N} \right|_{t_i = x\delta_{i,3}} \\
				&= L^{(3)}(x,N+2) + L^{(3)}(x,N-2) - 2L^{(3)}(x,N).
		\end{align*}
	Now, using the fact that the coefficient of $x^n$ in $L^{(3)}(x,y)$ is a polynomial in $y$ (see Remark~\ref{polynomiality}), we may extract coefficients in \eqref{mEquation1} to get a countable number
	of polynomial identities which are satisfied and thus equation~\eqref{mEquation1} holds with
		\begin{align*}
			T &= \Lt(x,y) + y(y+1) - \frac{y}{2x^2}, \\
			V &= \Lt(x,y+2) + \Lt(x, y-2) - 2\Lt(x,y).
		\end{align*}
	Recall that
		\[ \Lt(xw^{1/2}, w^{-1}) = w^{-2}\Lt(x;w). \]
	We have
		\begin{align*}
			\Lt(xw^{1/2},w^{-1} + 2)	&= \Lt\left(x(1+2w)^{1/2} \left( \frac{w}{1+2w} \right)^{1/2}, \left( \frac{w}{1+2w} \right)^{-1} \right) \\
										&= w^{-2} (1+2w)^2 \Lt\left( x(1+2w)^{1/2}, \frac{w}{1+2w} \right).
		\end{align*}
	Similarly,
		\[ \Lt(xw^{1/2}, w^{-1} - 2) = w^{-2} (1-2w)^2 \Lt\left( x(1-2w)^{1/2}, \frac{w}{1-2w} \right). \]
	Making the change of variables $x \mapsto w^{1/2}x$, setting $y = w^{-1}$ and then simplifying gives the desired result.
\end{proof}

Since any cubic map must have an even number of vertices, we let $x = z^{1/2}$. Note that in this case $D$ becomes $D = 6z\del_z$. Also, let
	\[ \Lt_g(z) = [w^g]\Lt(z^{1/2};w), \]
and let
	\[ T_g(z) = [w^g]\left(\Lt(z^{1/2};w) + w + 1 - \frac{1}{2z}\right) = \Lt_g(z) + \delta_{g,1} + \left( 1 - \frac{1}{2z} \right)\delta_{g,0}. \]
\begin{cor} \label{MasterEquationGenusRefined}
	For $g \geq 0$,
		\begin{align*}
			4z^2 & (D+12)^2(D+8)(D+4)T_{g-2} - (D+6)DT_g \\
			     & \qquad + 12z^2(D+12)\left( \sum_{i=0}^g \left\{ (D+4)T_i \right\} \left\{ (D+4)T_{g-i} \right\} \right) \\
				 &= \sum_{k=0}^g V_k \left\{ 2z^2(D+12)(D+8)(D+4)T_{g-k-2} \right. \\
				 &  \qquad \qquad \left. - \frac{1}{2}(D+6)T_{g-k} + 6z^2\left( \sum_{i=0}^{g-k} \left\{ (D+4)T_i \right\} \left\{ (D+4)T_{g-k-i} \right\} \right) \right\},
		\end{align*}
	where
		\[ V_k = \sum_{t=0}^k 2^{k-t+2} (1 + (-1)^{k-t}) \sum_{i=0}^{k-t+2} \binom{2-t}{k-t-i+2} \frac{z^i}{i!} \del_z^i \Lt_t(z). \]
\end{cor}
\begin{proof}
	This follows after making the substitution $x = z^{1/2}$ in Theorem~\ref{MasterEquationGenus} and extracting the coefficient of $w^g$.
\end{proof}

\section{A Structure Theorem for $\Lt_g(z)$}

In \cite{G91} Gao studied the generating series for rooted triangulations on arbitrary surfaces. Using a Tutte type equation for the generating series he was able to find
compact representations of the generating series in the projective plane, sphere and torus cases. In each case the generating series is rational in the auxilliary, algebraic
series $s = s(x)$ which is the unique power series solution to $z = \frac{1}{2}s(1-s)(1-2s)$ with $s(0) = 0$. In particular, Gao proves Theorem~\ref{GaoTheorem} below.
Using this same method we show in Theorem~\ref{AlgebraicSeriesTheorem} that the generating series for a surface of any type is always rational when expressed in terms of
the series $s$. Note that the method used below is essentially the same as the method used in \cite{G91} and also in \cite{BC86}. The difference is that here we consider
cubic maps enumerated with respect to the number of vertices and in \cite{G91} Gao consideres triangulations with respect to the number of vertices.

To simplify some of the expression below we let $\eta = 1 - 6s + 6s^2$.

\begin{thm}[Gao\cite{G91}] \label{GaoTheorem}
	The generating series $\Lt_0(z)$ and $\Lt_1(z)$ are given in terms of $s$ by
		\begin{align*}
			\Lt_0(z)	&= \frac{2s(1-4s+2s^2)}{(1-s)(1-2s)^2}, \\
			\Lt_1(z)	&= \frac{(1-2s)(1-s+s^2) - (1-6s+6s^2)^\frac{1}{2}}{s(1-s)(1-2s)}.
		\end{align*}
\end{thm}

\begin{thm}\label{AlgebraicSeriesTheorem}
	For $g \geq 0$ the series $\Lt_g$ is a polynomial in $\eta^{\frac{1}{2}}$ with coefficients which are rational series in $s$.
\end{thm}
\begin{proof}
	Let $t_g(n, k, u_1, u_2, \cdots)$ be the number of locally orientable maps with Euler characteristic $g$ which have $n$ vertices, whose root face has degree $k$,
	which have a finite number of distinguished faces the $i$th of which has degree $u_i$ and where every other face has degree three. Let $I = \{i_1 < i_2 < \cdots \}$ be
	a finite set and let
		\[ T_g(x, y, I) = \sum t_g(n, k, u_1, u_2, \cdots) x^n y^k z_{i_1}^{u_1} \cdots. \]
	The series of near-triangular maps ($T_g$) was studied by Gao\cite{G91} using a Tutte type recursion. Here we repeat part of the argument in order to prove the Theorem
	but we refer to the paper for more details. Recall the Tutte type recursion, letting $I$ be a finite set and $w \not \in I$ an integer, then
		\begin{align}
			T_g(x,y,I)	&= y^2 \sum_{j=0/2}^{g} \sum_{S \subseteq I} T_j(x,y,S)T_{g-j}(x,y,I-S) \notag \\
						& \qquad + 2y^3 \left. \frac{\del}{\del z_w} T_{g-1}(x,y,I+\{w\}) \right|_{z_w = y} \notag \\
						& \qquad + y^2 \frac{\del}{\del y} \left( yT_{g-\frac{1}{2}}(x,y,I) \right) \label{ACT.MainEquation} \\
						& \qquad + y^{-1} \left[ T_g(x,y,I) - \delta_{0,g} \delta_{\emptyset, I} x - yT^1_g(x,I) \right] \notag \\
						& \qquad + \sum_{i \in I} \frac{y z_i}{z_i - y} \left[ z_i T_g(x,z_i,I-\{i\}) - yT_g(x,y,I-\{i\}) \right] \notag \\
						& \qquad + \delta_{0,g} \delta_{\emptyset, I} x, \notag
		\end{align}
	where here the summation index beginning at $0/2$ means to sum over half integers from $0$ to $g$ and where $T^1_g(x,I) = [y]T_g(x,y,I)$. Note also that if we let
	$T^3_g(x,I) = [y^3] T_g(x,y,I)$ then
		\[ T_0^3(x,\emptyset) = T_0^1(x, \emptyset) - x^2, \qquad T_{\frac{1}{2}}^3(x,\emptyset) = T_{\frac{1}{2}}^1(x,\emptyset) - x, \]
	and
		\[ T_g^3(x,\emptyset) = T_g^1(x,\emptyset) \mbox{ for } g \geq 1. \]

	Let
		\begin{align*}
			A(x,y)	&= 2y^3 T_0(x,y,\emptyset) + 1 - y, \\
			B(x,y)  &= (1-y)^2 + 4y^3(x - xy + yT_0^1(x,\emptyset)).
		\end{align*}
	Then \eqref{ACT.MainEquation} when $(g,I) = (0,\emptyset)$ is equivalent to
		\[ A(x,y)^2 = B(x,y), \]
	and for $(g,I) \not = (0, \emptyset)$ \eqref{ACT.MainEquation} is equivalent to
		\begin{align*}
			-A(x,y)T_g(x,y,I)	&= y^3 \mathop{\sum_{j=0/2}^{g} \sum_{S \subseteq I}}_{(j,S) \not = (0, \emptyset), (g, I)} T_j(x,y,S)T_{g-j}(x,y,I-S) \\
								& \qquad + 2y^4 \left. \frac{\del}{\del z_w} T_{g-1}(x,y,I+\{w\}) \right|_{z_w = y} \\
								& \qquad + y^3 \frac{\del}{\del y} \left( yT_{g-\frac{1}{2}}(x,y,I) \right) \\
								& \qquad + y^2 \sum_{i \in I} \frac{z_i}{z_i - y} \left[ z_i T_g(x,z_i,I-\{i\}) - yT_g(x,y,I-\{i\}) \right] \\
								& \qquad -yT_g^1(x,I),
		\end{align*}
	as in \cite{G91}. Let $f(x)$ be a series such that $A(x,f(x)) = 0$. Then, if we define $F^{(k)} = \left. \left( \frac{\del^k F}{\del y^k} \right) \right|_{y = f}$ we see that
		\begin{align*}
			B^{(0)} = (1-f)^2 + 4f^3(x-xf+fT_0^1(x,\emptyset)) = 0, \\
			B^{(1)} = -2(1-f) + 4f^2(3x - 4xf + 4fT_0^1(x,\emptyset)) = 0.
		\end{align*}
	Solving this and setting $f = \frac{1}{1-s}$ we get
		\[ x = \frac{1}{2}s(1-s)(1-2s), \]
	and
		\[ T_0^1(x,\emptyset) = \frac{1}{4}s^2(1-s)(1-3s). \]
	This implies that
		\[ T_0^3(x,\emptyset) = \frac{1}{2}s^3(1-s)(1-4s+2s^2). \]
	By a Theorem of Brown\cite{B65}, since $B(x,y)$ is a square it can be uniquely written as
		\[ B(x,y) = Q(x,y)^2 R(x,y), \]
	where $Q(x,y)$ and $R(x,y)$ are polynomials in $y$ and where
		\[ R(x,0) = 1. \]
	We may suppose that $B(x,y) = (1 + yQ_1)^2(1 + R_1 y + R_2 y^2)$ where $Q_1, R_1, R_2$ are rational series in $s$. Solving this gives
		\[ Q_1 = s-1, \qquad R_1 = -2s, \qquad \mbox{ and } R_2 = -2s + 3s^2. \]
	It follows by the same argument as in \cite{G91} that $T_g(x,y,I)$ is a polynomial in $R^{\frac{1}{2}}(x,y)$, $R^{\frac{1}{2}}(x,z_i), i \in I$ and $R^{\frac{1}{2}}\left(x,\frac{1}{1-s}\right)$
	with coefficients which are rational series in $x, y, z_i, i \in I, R_1, R_2$ and $\frac{1}{1-s}$. More specifically, if $T_g(x) = [y^3] T_g(x,y,\emptyset)$ then
	$T_g(x)$ is a polynomial in $R^{\frac{1}{2}}\left( x, \frac{1}{1-s} \right)$ with coefficients which are rational series in $s$. Since
	$R^{\frac{1}{2}}\left( x, \frac{1}{1-s} \right) = \frac{\eta^{\frac{1}{2}}}{1-s}$ it follows that $T_g(x)$ is a polynomial in $\eta^{\frac{1}{2}}$ with coefficients
	which are rational series in $s$. The result then follows from the fact that $\Lt_g(x) = x^{2g-2}T_g(x)$.
\end{proof}

We will now make use of Theorem~\ref{AlgebraicSeriesTheorem} and Theorem~\ref{MasterEquationGenus} to prove a stronger structure theorem for $\Lt_g(z)$. In addition, we will
show that the recurrence implied by Theorem~\ref{MasterEquationGenus} can be used to determine $\Lt_g(z)$ inductively.
It will be convenient for what follows to define a basis with which to work. For $i \geq 0$, define
	\[ \psi_i = \begin{cases} \frac{(1-2s)}{\eta^{\frac{i}{2}+1}}, & \mbox{ if } i \mbox{ is odd}, \\ \frac{1}{\eta^{\frac{i}{2}+1}}, & \mbox{ if } i \mbox{ is even}. \end{cases} \]
\begin{pro}\label{PsiBasis}
	The basis $\psi_i$ defined above satisfies the multiplicative identity,
		\[ \psi_i \psi_j = \chi(i,j) \psi_{i+j+2} + (1 - \chi(i,j))\psi_{i+j}, \]
	where
		\[ \chi(i,j) = \begin{cases} 1, & \mbox{ if either } i \mbox{ or } j \mbox{ is even}, \\ \frac{1}{3}, & \mbox{ if both } i \mbox{ and } j \mbox{ are odd}. \end{cases} \]
	Also, the action of the operator $D$ on the $\psi_i$ basis is given by
		\[ D\psi_i = \begin{cases} (i+2)\psi_{i+4} + (i+2)\psi_{i+2} - 2(i+2)\psi_i, & \mbox{ if } i \mbox{ is even}, \\ (i+2)\psi_{i+4} + i\psi_{i+2} - 2(i+1)\psi_i, & \mbox{ if } i \mbox{ is odd}. \end{cases} \]
\end{pro}
\begin{proof}
	Each of these identites follow from the definition of $\psi_i$, $\eta$, $s$ and $D$.
\end{proof}

\begin{thm}\label{StructureTheorem}
	For $g \geq 2$ the generating series for locally orientable cubic maps is of the form
		\[ \Lt_g = \sum_{i = 0}^{5g - 8} \mu_g(i) \psi_i. \]
	Furthermore, $\Lt_g$ for $g \geq 2$ can be determined recursively using the equation given in Corollary~\ref{MasterEquationGenusRefined}.
\end{thm}
\begin{proof}
	Using Theorem~\ref{GaoTheorem}, Corollary~\ref{MasterEquationGenusRefined} can be rearranged so that when written in the $\psi_i$ basis we have
	\[
		\left\{ \frac{4}{3} D^2 \right. \left. - 4(g\psi_2 + \psi_0 - 4)D - \frac{4}{3}(2\psi_4 + 9g(3-g)\psi_2 + 12\psi_0 - 32) \right\} \Lt_g = R_g(s),
	\]
	where $R_g(s)$ depends only on $\Lt_i$, $i = 0 \cdots g-1$. That $\Lt_g = \sum_{i=0}^{5g-8} \mu_g(i) \psi_i$ then follows by induction by directly computing
	the base case
		\[ \Lt_2 = \frac{23}{12} \psi_0 - 3 \psi_1 + \frac{13}{12} \psi_2, \]
	and then showing that
		\[ R_g(s) = \sum_{i=0}^{5g} r_g(i) \psi_i, \]
	for $g \geq 3$. Proving that $R_g(s)$ has this structure is a lengthy yet straightforward computation. One writes each of the parts in Corollary~\ref{MasterEquationGenusRefined}
	in terms of the $\psi_i$ basis and then using the identities in Proposition~\ref{PsiBasis} shows that $R_g(s)$ has an expansion in the $\psi_i$ basis and that the appropriate
	degree bounds hold. The result then follows using Theorem~\ref{AlgebraicSeriesTheorem}, expanding by partial fractions and then checking coefficients.
\end{proof}

\section{Asymptotic Behaviour}

In this final section we will consider some of the implications of the results above. In particular, we examine the leading coefficient in the $\psi$ basis
expansion of $\Lt_g(z)$ for each $g$. Using Theorem~\ref{MasterEquationGenusRefined} we can determine a recursion which the leading coefficients satisfy. Since the
asymptotic behaviour of each element in the $\psi$ basis can be determined, this allows us to determine the asymptotic behaviour of the series $\Lt_g(z)$ itself.
In what follows we will let \[ \al_g = \mu_g(5g - 8), \] i.e., $\al_g$ is the leading coefficient of $\Lt_g$ in the $\psi$ basis. Let
	\[ \be_k = \begin{cases} \frac{(5k-6)}{\sqrt{3}} \al_g, & \mbox{ if } k \mbox{ is odd}, \\ (5k-6) \al_g, & \mbox{ if } k \mbox{ is even}.\end{cases} \]

\begin{thm}
	For all $g > 1$,
		\begin{align*}
			\frac{8}{3} (g-1) \be_g	&= \frac{1}{162}(5g-8)(5g-12)(5g-6)\be_{g-2} \\
									&\qquad - \frac{1}{3^6 5!} (5g-6)(5g-10)(5g-14)(5g-18)(5g-22)\be_{g-4} \\
								    &\qquad + \frac{8(5g-6)}{432} \sum_{i=1}^{g-1} \be_i \be_{g-i} - \frac{(5g-6)}{2^3 3^6} \sum_{i=2}^{g-1} (5i-8)(5i-12) \be_{i-2} \be_{g-i} \\
								    &\qquad - \frac{1}{2^3 3^5} \sum_{i=1}^{g-1} \sum_{j=1}^{g-i-1} (5i-2) \be_i \be_j \be_{g-i-j}.
		\end{align*}
\end{thm}
\begin{proof}
	Using the notation in the proof of Theorem~\ref{StructureTheorem}, we have
		\[ p_g(D) \Lt_g = \sum_{i=0}^{5g} r_g(i) \psi_i, \]
	where
		\[ p_g(D) = \frac{4}{3} D^2 - 4(g\psi_2 + \psi_0 - 4)D - \frac{4}{3}(2\psi_4 + 9g(3-g) \psi_2 + 12\psi_0 - 32). \]
	Now,
		\begin{align*}
			[\psi_{5g}] p_g(D) \Lt_g
										&= \frac{4}{3} (5g-2)(5g-6) \al_g - 4g(5g-6)\al_g \\
										&= \frac{8}{3}(5g-6)(g-1)\al_g.
		\end{align*}
	So,
		\[ \frac{8}{3}(5g-6)(g-1)\al_g = r_g(5g). \]
	As in the proof of Theorem~\ref{StructureTheorem}, if we write out each term in Corollary~\ref{MasterEquationGenusRefined} in terms of the $\psi_i$
	basis and then simplify using the identities in Proposition~\ref{PsiBasis}, then after a very lengthy computation we can show that if we let $w_k = (5k-6)\al_k$ then
		\begin{align*}
			\frac{8}{3}(g-1)w_g	&= r_g(5g), \\
								&= \frac{1}{162} (5g-8)(5g-12)(5g-6)w_{g-2} \\
								& \qquad - \frac{1}{3^6 5!} (5g-6)(5g-10)(5g-14)(5g-18)(5g-22)w_{g-4} \\
								& \qquad + \frac{(5g-6)}{54} \sum_{i=1}^{g-1} \chi(i,g-i) w_i w_{g-i} \\
								& \qquad - \frac{(5g-6)}{2^3 3^6} \sum_{i=2}^{g-1} \chi(i,g-i) (5i-8)(5i-12) w_{i-2} w_{g-i} \\
								& \qquad - \frac{1}{9 \cdot 216} \sum_{i=1}^{g-2} \sum_{j=1}^{g-i-1} (5i-2)\chi(i,g-i)\chi(j,g-i-j)w_i w_j w_{g-i-j},
		\end{align*}
	where here
		\[ \chi(i,j) = \begin{cases} 1, & \mbox{ if either } i \mbox{ or } j \mbox{ is even}, \\ \frac{1}{3}, & \mbox{ if both } i \mbox{ and } j \mbox{ are odd}. \end{cases} \]
	If we make the substitution
		\[ w_k = 	\begin{cases}
						\sqrt{3} \beta_k, & \mbox{ if } k \mbox{ is odd}, \\
						\beta_k, & \mbox{ if } k \mbox{ is even},
					\end{cases} \]
	then it is straightforward to check that if $g$ is even, $\chi(i,g-i)w_i w_{g-i} = \be_i \be_{g-i}$ and $\chi(i,g-i)\chi(j,g-i-j)w_i w_j w_{g-i-j} = be_i \be_j \be_{g-i-j}$ for any $i$ and $j$ and that
	if $g$ is odd then $\chi(i,g-i)w_i w_{g-i} = \sqrt{3} \be_i \be_{g-i}$ and $\chi(i,g-i)\chi(j,g-i-j) w_i w_j w_{g-i-j} = \be_i \be_j \be_{g-i-j}$. So, taking the recursion for $w_g$ above and making the
	substitution, we get (after dividing by $\sqrt{3}$ if $g$ is odd) the desired result.
\end{proof}

Let
	\[ \be(z) = \sum_{n \geq 0} \be_n \left( \frac{3}{2} \right)^n z^{-\left( \frac{5n-2}{4} \right)}, \]
with $\be_0 = -36$ and $\be_1 = \frac{18}{\sqrt{3}}$.

\begin{cor} \label{AsymptoticDE}
	The generating series $\be(z)$ satisfies the differential equation
		\[ - \frac{8}{15} z \be'(z) - \frac{16}{15}\be(z) + \frac{8}{135}\be'''''(z) + \frac{2}{81}\be''(z)\be'(z) + \frac{2}{81}\be'''(z)\be(z) + \frac{1}{486} \be(z)^2\be'(z) = 0. \]
\end{cor}
\begin{proof}
	That the differential equation above is equivalent to the recursion for the coefficients $\be_k$ is easily checked by extracting coefficients.
\end{proof}

From the structure theorem for $\Lt_g$, we know that
	\[ \Lt_g \approx \begin{cases} \frac{\al_g}{\eta^{\frac{5g-6}{2}}}, & \mbox{ if } g \mbox{ is even}, \\ \frac{\al_g(1-2s)}{\eta^{\frac{5g-6}{2}}}, & \mbox{ if } g \mbox{ is odd}. \end{cases} \]
Further, it is a result of Gao\cite{G91} that
	\[ \eta \approx \left( \frac{\sqrt{6}}{2} \right)^{\frac{5g-6}{2}} \left( 1 - 12\sqrt{3}z \right)^{-\frac{(5g-6)}{4}}. \]
Darboux's theorem then implies that
	\[ \ell_g(n) = [z^n]\Lt_g \sim \frac{\be_g}{5g-6} \left( \frac{3}{2} \right)^{\frac{5g-6}{4}} \frac{n^{\frac{5(g-2)}{4}}}{\Gamma\left( \frac{5g-6}{4} \right)}\left( 12\sqrt{3} \right)^n. \]
In terms of the orientable map asymptotics constant $t_g$ and the nonorientable map asymptotics constant $p_g$, it is straightforward to show that
	\[ \be_k = \left( \frac{2}{3} \right)^k 9 \left( (5k-6)v_{k-1} - 4u_{k/2} \right), \]
where
	\begin{align*}
		u_n	&= 2^{n-2} \Gamma\left( \frac{5n-1}{4} \right)t_n, \\
		v_n &= 2^{\frac{n-3}{2}} \Gamma\left( \frac{5n-1}{4} \right) p_{\frac{n+1}{2}},
	\end{align*}
and we adopt the convention that $u_n = 0$ if $n$ is not an integer. In particular, $u_0 = 1$ and $v_0 = -\sqrt{3}$

Let
	\begin{align*}
		u(z)	&= z^{\frac{1}{2}} \sum_{n \geq 0} u_n z^{-\frac{5n}{2}}, \\
		v(z)	&= z^{\frac{1}{4}} \sum_{n \geq 0} v_n z^{-\frac{5n}{2}}.
	\end{align*}
Bender, Richmond and Gao\cite{BRG08} showed that $u(z)$ satisfies the ordinary differential equation
	\[ u^2 - \frac{1}{6} u'' = z. \]
Using the differential equation for $u$ and Corollary~\ref{AsymptoticDE} we can now prove Theorem~\ref{p_gTheorem} (Conjecture 1 of Garoufalidis and Mari\~no\cite{GM10}).
\begin{proof}[Proof of Theorem~\ref{p_gTheorem}]
	Let $v_n$ be the unique sequence of numbers such that the generating series \[v(z) = z^{1/4} \sum_{n \geq 0} v_n z^{-5n/4}\] satisfies the differential equation $2v' - v^2 + 3u = 0$ and with $v_0 = -\sqrt{3}$.
	Let \[ \beta(z) = -36(u(z) + v'(z)).\] Substituting this $\beta$ into the differential equation in Corollary~\ref{AsymptoticDE} and reducing using the relations $u^2 - \frac{1}{6} u'' = z$ and
	$2v' - v^2 + 3u = 0$ we find that $\beta$ is a solution.

	Also, checking $\be_0$ and $\be_1$ we see that this is the unique solution which determines the map asymptotics constants.
\end{proof}

\bibliographystyle{plain}
\bibliography{document}

\end{document}


TITLE: What else is needed to establish this functional series converges to strictly increasing function?
QUESTION [2 upvotes]: I have a functional series
$$
f(z)=\sum_{n=1}^\infty f_n(z)
$$
and am trying to prove that $f(z)$ is strictly increasing for all $z\geq 0$.  So far I have proven that

The series is absolutely and uniformly convergent for all $z\geq 0$.
The series is bounded for all $z\geq 0$, i.e. $0\leq f(z)< \infty$.
$f_n(z)>0,\quad \forall n\ \ \land \ \ \forall z\geq 0$.
$f_n^\prime(z)>0,\quad \forall n\ \ \land \ \ \forall z\geq 0$.

What else do I need to prove $f(z)$ is strictly increasing?

According to Fubini's theorem on differentiation I know that
$$
f^\prime(z)=\sum_{n=1}^\infty f_n^\prime(z).
$$
Since I have already shown $f_n^\prime(z)>0$ do I need to prove any other facts to conclude $f^\prime(z)>0$ on $z\geq 0$? It would seem that I am done but am posting this as a sanity check.

REPLY [0 votes]: You are pretty much already done. By uniform convergence, term by term differentiation is legitimate, hence by 4, $f'(z)=\sum_{n=1}^{\infty} f_n'(z) \gt 0$ and therefore $f(z)$ is strictly increasing.


TITLE: How to determine intervals where $f$ is greater than $g$?
QUESTION [0 upvotes]: I have two functions, $f(x) = 2x$ and $g(x) = \frac{x^3}{3}$.  I solved for $x$ where $f = g$, finding $x = \pm 6^{1/2}$, then solved for $x$ where $f > g$, $x > \pm 6^{1/2}$, and where $f < g$, $x < \pm 6^{1/2}$. However it is clear there is overlap for where I have stated $f > g$ and $f < g$. How do I show that $f > g$ only when $x \in (0, 6^{1/2})$ and $f < g$ only when $x \in (- 6^{1/2}, 0)$ without graphing?
Completely different approaches from mine are welcomed!

REPLY [0 votes]: Solve the inequality
$$
2x>\frac{x^3}{3}
$$
that can be rewritten as
$$
x(x-\sqrt{6})(x+\sqrt{6})<0
$$
The expression on the left changes sign only at $-\sqrt{6}$, $0$ and $\sqrt{6}$ (where it vanishes). Since its value at $1$ is $-5$ you have the diagram
$$
\begin{array}{ccccccc}
\_\!\_\!\_\!\_\!\_\!\_\!\_  & -\sqrt{6} &
\_\!\_\!\_\!\_\!\_\!\_\!\_ & 0 &
\_\!\_\!\_\!\_\!\_\!\_\!\_ & \sqrt{6} &
\_\!\_\!\_\!\_\!\_\!\_\!\_ \\
& & & & <0 &
\end{array}
$$
and you can complete it by changing sign at the stated points
$$
\begin{array}{ccccccc}
\_\!\_\!\_\!\_\!\_\!\_\!\_  & -\sqrt{6} &
\_\!\_\!\_\!\_\!\_\!\_\!\_ & 0 &
\_\!\_\!\_\!\_\!\_\!\_\!\_ & \sqrt{6} &
\_\!\_\!\_\!\_\!\_\!\_\!\_ \\
<0 & =0 & >0 & =0 & <0 & =0 & >0
\end{array}
$$
So the intervals where the original inequality holds are $(-\infty,-\sqrt{6})$ and $(0,\sqrt{6})$.