Let us illustrate the diagrammatic expansion of integrals from Lecture 13 in a specific case: we will bring things full circle and look at “Stirling’s quantum field theory.” Going back to the very beginning, start with the Euler integral
Now make the change of variables 
and we’re in position to apply our diagrammatic 
The nice thing about the diagrammatic expansion is that most of it is “universal,” and it is not until the last step that we have to worry about what the smooth function in the exponent of the integrand actually is. In particular, from Lecture 13, we have that the coefficient of 
where 
so that the coefficient of
Note that this has absolutely no dependence on what the integral actually is, so far: this dependence only enters at the last stage, where we plug in the values of the 
as 
For a more involved version of the same procedure, where the “graphs” involved are of a quite different nature, you can check out my lecture yesterday in the UC Berkeley combinatorics seminar. Don’t worry if you don’t understand much; we are going to look at matrix integrals together very soon.
is a smooth function on the line such that the above integral converges, and whose Taylor series is of the form
is a function of the real variable 
which is smooth in a neighborhood of 
then I write 
So it does not make sense to write 
and trade the formal variable 
you get a good approximation to the real number 
in terms of the formal power series 
What we currently know is that 
, with 
the number of fixed point free involutions in 
and 
the conjugacy class in 
and 
So, in completely algebraic language, one could say that we are studying the “Feynman transform”![\mathcal{F} \colon x^3\mathbb{R}[p_1,p_2,p_3,\dots][[x]] \to \mathbb{R}[p_1,p_2,p_3,\dots][[\hbar]]](https://s0.wp.com/latex.php?latex=%5Cmathcal%7BF%7D+%5Ccolon+x%5E3%5Cmathbb%7BR%7D%5Bp_1%2Cp_2%2Cp_3%2C%5Cdots%5D%5B%5Bx%5D%5D+%5Cto+%5Cmathbb%7BR%7D%5Bp_1%2Cp_2%2Cp_3%2C%5Cdots%5D%5B%5B%5Chbar%5D%5D&bg=FFFFFF&fg=000&s=0&c=20201002 "\mathcal{F} \colon x^3\mathbb{R}[p_1,p_2,p_3,\dots][[x]] \to \mathbb{R}[p_1,p_2,p_3,\dots][[\hbar]]")
in the algebra of formal power series in 
with coefficients being polynomials in the 
and the codomain is formal power series in 
with coefficients in the same polynomial ring. The problem then is to simplify the output of the Feynman map as a power series in 
i.e. to determine the coefficient of 
for each 
as the cardinality of 
where again 
and 
is the set of fixed point free involutions in 
Note that 
is the Young diagram with 
rows of length 
Every pair 
is a combinatorial map. Associated to this map are two topological maps, which are dual to one another. To construct these topological maps, we use the following construction. First, for each cycle of 
we draw a polygon whose number of sides is equal to the length of 
and whose edges are labeled counterclockwise in the cyclic order prescribed by 
At the same time, we place into this polygon the corresponding dual object, namely a vertex in the interior of the polygon together with line segments, called “half edges” or “darts,” which emanate from the vertex, one for each edge of the polygon and labeled in the same way. Note that we need only consider the case where 
otherwise, and moreover where all rows of 
have length at least 
meaning that all polygons in this construction have at least three sides, or dually that all stars have degree at least 
Now we glue the sides of the polygons together according to the pairing permutation 
and at the same time pair half edges of stars in the same manner, i.e. using 
This produces a pair of dual topological maps 
on a compact oriented surface 
Our convention is that we view 
as the topological map obtained by glueing stars, and 
as the topological map obtained by glueing polygons. The figure below illustrates this construction for the combinatorial map
are the number of vertices and edges in 
Observe that actually the difference 
depends only on the underlying graph, not actually on its embedding, so that this is a purely combinatorial parameter. Indeed, it is closely related to the so-called 
the circuit rank and 
the number of connected components. This is pretty obvious if you think about it: consider the extremal case where we have one connected component consisting of a tree. In this case the difference 
is obviously equal to zero, and if we start adding edges the circuit rank goes up by one every time we add an edge, and moreover the construction is additive in the number of components (graph theory people – did I get that right?). 
and conjugate it by an arbitrary permutation 
then we get another combinatorial map 
which obviously yields the same topological map when the construction described above is performed, since we have simply relabeled everything by conjugating. Thus we expect that the correspondence between combinatorial and topological maps should be 
-to-one, which would be excellent news, since then the factor
whose conjugation action on the combinatorial map 
of the symmetric group 
and it is the only part of the above construction which actually depends on the generating function 
limit comes from graphs which have minimum vertex degree 
![[a,b] \subseteq \mathbb{R}](https://s0.wp.com/latex.php?latex=%5Ba%2Cb%5D+%5Csubseteq+%5Cmathbb%7BR%7D&bg=FFFFFF&fg=000&s=0&c=20201002 "[a,b] \subseteq \mathbb{R}")
which may be finite or infinite, and let ![S \colon [a,b] \to \mathbb{R}](https://s0.wp.com/latex.php?latex=S+%5Ccolon+%5Ba%2Cb%5D+%5Cto+%5Cmathbb%7BR%7D&bg=FFFFFF&fg=000&s=0&c=20201002 "S \colon [a,b] \to \mathbb{R}")
be a smooth function which attains a global minimum at a unique interior point 
and which is such that the integral 
with 
. Taylor’s theorem with remainder tells us that for any nonnegative integer 
, we have 
depends on 
asymptotic expansion of an integral of the form
the Laplace principle gives us the 
via the Euler integral.
when 
such that 
Writing 
and the product being over the blocks 
of each partition 
An alternative form of the Exponential Formula, which is more useful for our current purpose, arises when we instead write 
In terms of the scaled derivatives 
the formula for 
becomes
can be cyclically ordered in 
ways, we can rewrite the above as
and the product is over the cycles 
of each permutation 
but only their sizes, so that any two permutations of the same cycle type (i.e. any two permutations which are conjugates of one another) give the same contribution to the sum. That is to say, we may rewrite the above as 
is the conjugacy class of permutations of cycle type 
. To simplify the computation, we will make several assumptions on the Laplace side, none of which are essential — these can all be eliminated without too much difficulty and the end result is more or less the same. First, we assume the integration is over the whole real line. Second, we assume that the critical point 
, and that 
Finally, let us assume that the positive number 
is equal to one. 
We factor the integrand as 
. We get the Maclaurin series of 
by integrating this term-by-term against the Gaussian density:
we now want to arrange the sum 
At this point, it is not even clear that the series involves only nonnegative integer powers of 
which seems like it could be negative, but in fact since 
vanishes if 
has more than 
rows. Combining these conditions, we see that the first non-zero exponent of 
, and the only 
which contributes to the sum is 
the diagram with two rows each of length 
in the exponent of 
Since all rows of 
is 
is 
ways to choose the elements in cycles and 
which is ten times smaller than 
).
is equal to the number of pairs 
such that 
is a fixed point free involution and 
is a permutation of cycle type 
with integration over the real vector space 
of 
Hermitian matrices; in this situation we can actually distinguish the genus of the maps which arise. After that we will generalize further to integrating over the real vector space of selfadjoint elements in a finite-dimensional von Neumann algebra.
is itself a smooth function with Taylor expansion of the form
are real numbers such that the corresponding path integral 
as a deformation of 
which corresponds to choosing all 
so that the potential 
and we get the exact evaluation
, which are functions of the parameters 
.
has coefficients 
. The result of our computation should then be a some sort of understanding of the subleading corrections 
, and focus solely on the integrand
of the integrand, and apply the Exponential Formula as in 
. Then we have that the coefficients 
in the expansion 
of 
is the number of ways to cyclically order the subset 
, we have that 
denotes the number of 
, and 
is the total number of cycles. Thus the polynomial 
is a generating function for the permutations in 
, and it is the basic tool in 
is the conjugacy class of permutations of cycle type 
.
is the number of fixed point free involutions in 
, and the number 
is equal to the number of pairs 
in which 
is a fixed point free involution, and 
is a permutation in 
such that 
have length at least 
together with a set 
we can try to embed it on a surface 
, such that the requirements to be a topological map are satisfied (this may not be possible if the connectivity of 
is high and the genus of 
is low, and the minimal genus of 
together with a collection of points on the surface connected by curves meeting only at those points — a topological map. The points 
, i.e. pairs 
such that 
is a product of 
is a 
-cycle. There are thus 
possibilities for 
possibilities for 
combinatorial maps of degree 
, the full forward cycle in 
. These are the following:![A = \left[(1\ 2)(3\ 4), (1\ 2\ 3\ 4) \right],\ B=\left[(1\ 3)(2\ 4), (1\ 2\ 3\ 4) \right],\ C=\left[(1\ 4)(2\ 3), (1\ 2\ 3\ 4) \right].](https://s0.wp.com/latex.php?latex=A+%3D+%5Cleft%5B%281%5C+2%29%283%5C+4%29%2C+%281%5C+2%5C+3%5C+4%29+%5Cright%5D%2C%5C+B%3D%5Cleft%5B%281%5C+3%29%282%5C+4%29%2C+%281%5C+2%5C+3%5C+4%29+%5Cright%5D%2C%5C+C%3D%5Cleft%5B%281%5C+4%29%282%5C+3%29%2C+%281%5C+2%5C+3%5C+4%29+%5Cright%5D.&bg=FFFFFF&fg=000&s=0&c=20201002 "A = \left[(1\ 2)(3\ 4), (1\ 2\ 3\ 4) \right],\ B=\left[(1\ 3)(2\ 4), (1\ 2\ 3\ 4) \right],\ C=\left[(1\ 4)(2\ 3), (1\ 2\ 3\ 4) \right].")
and 
is a generating function for topological maps, with face degrees determined by the Maclaurin series of the potential 
for observations 
, and typically 
. For example, one could take 
, a manifold which is supposed to model our physical experience of “spacetime,” and 
, meaning that our observables are numerical measurements on spacetime, which sounds reasonable and not at all problematic.
is called the “semiclassical parameter” and 
is a functional called the “action.” The total flatness and uniformity of the Lebesgue measure represents entropy, while the density above represents energy in the sense that it leads to measure concentrating near the minimizers of the action, much as we saw when we initially discussed the Laplace method, and as is familiar from the setting of 
is such that an exact evaluation of the corresponding 
is possible, we are looking at what is called a “free theory.” The goal then is to select a new action 
, i.e. 
corresponding to 
are called “quantum terms,” and the sum of all these terms is typically a divergent series, i.e. it has radius of convergence zero. So what this meant by the above is that there is that 
the corresponding space of functions 
in such a way that 
consisting of a single point. Choosing 
is not advisable, since then 
then 
, and we have something non-trivial, namely a 
. Then ![\int\limits_{[a,b]} e^{-\frac{1}{\hbar}S(x)} \mathrm{d}x = e^{-\frac{S(c)}{\hbar}} \sqrt{\frac{2\pi\hbar}{S''(c)}}A(\hbar),](https://s0.wp.com/latex.php?latex=%5Cint%5Climits_%7B%5Ba%2Cb%5D%7D+e%5E%7B-%5Cfrac%7B1%7D%7B%5Chbar%7DS%28x%29%7D+%5Cmathrm%7Bd%7Dx+%3D+e%5E%7B-%5Cfrac%7BS%28c%29%7D%7B%5Chbar%7D%7D+%5Csqrt%7B%5Cfrac%7B2%5Cpi%5Chbar%7D%7BS%27%27%28c%29%7D%7DA%28%5Chbar%29%2C&bg=FFFFFF&fg=000&s=0&c=20201002 "\int\limits_{[a,b]} e^{-\frac{1}{\hbar}S(x)} \mathrm{d}x = e^{-\frac{S(c)}{\hbar}} \sqrt{\frac{2\pi\hbar}{S''(c)}}A(\hbar),")
such that 
![\int\limits_{[a,b]} e^{-\frac{1}{\hbar}S(x)} \mathrm{d}x = e^{-\frac{S(c)}{\hbar}} \sqrt{\frac{2\pi\hbar}{S''(c)}}(1+a_1\hbar + \dots +a_k\hbar^k + o(\hbar^k)),](https://s0.wp.com/latex.php?latex=%5Cint%5Climits_%7B%5Ba%2Cb%5D%7D+e%5E%7B-%5Cfrac%7B1%7D%7B%5Chbar%7DS%28x%29%7D+%5Cmathrm%7Bd%7Dx+%3D+e%5E%7B-%5Cfrac%7BS%28c%29%7D%7B%5Chbar%7D%7D+%5Csqrt%7B%5Cfrac%7B2%5Cpi%5Chbar%7D%7BS%27%27%28c%29%7D%7D%281%2Ba_1%5Chbar+%2B+%5Cdots+%2Ba_k%5Chbar%5Ek+%2B+o%28%5Chbar%5Ek%29%29%2C&bg=FFFFFF&fg=000&s=0&c=20201002 "\int\limits_{[a,b]} e^{-\frac{1}{\hbar}S(x)} \mathrm{d}x = e^{-\frac{S(c)}{\hbar}} \sqrt{\frac{2\pi\hbar}{S''(c)}}(1+a_1\hbar + \dots +a_k\hbar^k + o(\hbar^k)),")
). So we are in a position where we have the perfectly well-defined problem of computing the “quantum corrections” 
. At each tick of the clock, the particle makes a random jump to a neighboring lattice site, with equal probability of jumping in any direction. In other words, the particle is executing simple random walk on 
and transient for 
.
, let 
denote the event that simple random walk on 
steps. It is convenient to set 
, corresponding to the fact that the particle is tautologically situated at its initial position at time zero and this should not count as a return. Write 
for the probability of 
the number of length 
.
denote the number of length 
(this is like excluding 
, we have
.
, followed by a (possibly trivial) loop of length 
. 
, which is the total number of 
,
is the probability that the particle is situated at its initial position at time 
and 
, which by definition are the
together with Proposition 1. Now, each of the series 
and 
has radius of convergence at least 
Since the coefficients of 
, and we thus have
approaches 
(recurrence), or 
(transience).
(
for lattice loops, it turns out that the corresponding 
for the exponential generating function of the sequence 
of length 
To be concrete, let us consider what is going on for 
. A walk on 
one corresponding to horizontal steps and the other to vertical steps. Thus, a loop on 
is a shuffle of two loops on 
. More quantitatively, we have 
corresponding to the times at which horizontal steps occur, and finally choose one of the 
one-dimensional 
since we have reduced to the case 
which ought to be straightforward. Indeed, we clearly have
, and if so do we know anything useful about this function? Luckily, the answer turns out to be an emphatic yes: 
, with 
is one of two linearly independent solutions to the second order ODE 
then its Borel transform
behavior of 
large. Now because the integrand here is a Bessel function, it is itself an integral:
and 
is large. We are thus perfectly positioned for an application of the Laplace approximation (end point case),
Polya’s theorem is proved, and if you’re willing to retrace our steps a bit you will find that you have a reasonable idea of what the mechanism is that is responsible for recurrence of simple random walk in dimensions 
and transience in dimensions 
. Indeed, if you want to get your hands dirty you can even try to estimate 
, we have ![\sum\limits_{n=0}^\infty (n!)_d \frac{z^{2n}}{n!n!} = \det [I_{i-j}(2z)]_{i,j=1}^d,](https://s0.wp.com/latex.php?latex=%5Csum%5Climits_%7Bn%3D0%7D%5E%5Cinfty+%28n%21%29_d+%5Cfrac%7Bz%5E%7B2n%7D%7D%7Bn%21n%21%7D+%3D+%5Cdet+%5BI_%7Bi-j%7D%282z%29%5D_%7Bi%2Cj%3D1%7D%5Ed%2C&bg=FFFFFF&fg=000&s=0&c=20201002 "\sum\limits_{n=0}^\infty (n!)_d \frac{z^{2n}}{n!n!} = \det [I_{i-j}(2z)]_{i,j=1}^d,")
is the number of permutations in 
with no decreasing subsequence of length 
.
defined on the region 
: we have 
.
, define 
,
of Young diagrams with 
this is the number of permutations in 
with no decreasing subsequence of length 
, and at 
it is the number of involutions satisfying the same. 
to calculate the asymptotics of 
. The first step is to rewrite the sum defining 
, which as we have discussed in the previous lectures is the canonical self-complementary diagram relative to the twice-longer rectangle 
which appear in Conjecture 1 of 
. Now, the lattice 
partitions 
into cells
, so that 
asymptotics of 
is the partition function of the system of the two-dimensional Coulomb gas we have been discussing. This integral is not particularly easy to evaluate, and to compute it one needs to know some version of the 
and 
is the complement of 
. Repeating the argument above essentially verbatim (change variables from 
to 
in the sum and scale by the mesh volume), we find that 
and 
we get
is really a consequence of the fact that we can describe this combinatorial function as a sum over Young diagrams. One could try various other versions of this. For example, let 
be any fixed permutation, and define 
to the the number of permutations 
. Not much is known about the 
where 
does not depend on 
which is exponential in 
using the usual Stirling formula (Hint: this was already suggested as an Exercise in 
fluctuating around the canonical self-complentary diagram 
(relative to the twice-larger rectangle 
) on a square root scale. Recall that 
, we have 
is
fluctuates on a square root scale, and the fluctuations themselves behave like a 2D Coulomb gas of 
is the 
is the 
is inversely proportional to the distance between them raised to the power 
. So in our usual 
world, 
world the repulsion is proportional to the reciprocal of the distance. Since energy is the integral of force, this accounts for the logarithmic terms in 
symmetric matrices. This is a Euclidean space when equipped with the standard scalar product 
, i.e. the scalar product with respect to which the elementary matrices 
form an orthonormal basis. In particular, one can define the standard Gaussian measure on this Euclidean space by stipulating its density, 
. A random matrix with this distribution will have Gaussian random variables as its entries, and these variables are independent up to the symmetry constraint, as you can see by canonically identifying such a random matrix with a 
dimensional random vector and taking its Laplace transform. However, the eigenvalues of 
of a 
in 
has density proportional to 
is proportional to the ![\det [x_j^{d-i}]_{1 \leq i,j \leq d} = \prod\limits_{1 \leq i<j \leq d} (x_i-x_j).](https://s0.wp.com/latex.php?latex=%5Cdet+%5Bx_j%5E%7Bd-i%7D%5D_%7B1+%5Cleq+i%2Cj+%5Cleq+d%7D+%3D+%5Cprod%5Climits_%7B1+%5Cleq+i%3Cj+%5Cleq+d%7D+%28x_i-x_j%29.&bg=FFFFFF&fg=000&s=0&c=20201002 "\det [x_j^{d-i}]_{1 \leq i,j \leq d} = \prod\limits_{1 \leq i<j \leq d} (x_i-x_j).")
of the traceless random matrix 
. This surprising coincidence of Young diagram formulas and random matrix formulas is just the tip of a huge iceberg linking the two subjects, the culmination of which is the 
can be interpreted as the spectrum of a 
, the relationship is as above: one takes Gaussian complex selfadjoint matrices with entries to get the 
case. For the other values of 
is the 
rectangular Young diagram. This would be excellent, since the asymptotics of the dimension of a very long rectangle of fixed height are easy to deduce from Frobenius’s formula for 
together with Stirling’s approximation of 
we have 
This is exactly what you think it is: if 
, then 
— draw yourself a picture. The basis of our gluing trick was that in the case 
every diagram is self complementary: for 
we have
but for any 
of SYT in which the shape of 
and the shape of 
is the complementary diagram 
and subtracting 
is contained in 
is self-complementary or not,
where the error term is 
reflects the two sources of error in the approximation 
In particular, we have that 
corresponding to Knuth’s theorem, but 
for 
Conjecture 1 says that 
i.e. the rectangle 
So we are hopeful that diagrams in a neighborhood of this rectangle are essentially contributions from a neighborhood of the maximum of 
just like in Laplace’s method.
and 
is a vector such that
-dimensional convex subset of 
, which is in fact a hyperplane slice of the type A 
at possibly non-integral numbers, so we are in effect taking Frobenius’s formula as a way to extend the domain of 
just like Euler’s integral extends the domain of 
in a neighborhood of its maximum.
behaves as 
as we have discussed. We now have to think about the 
, for which we have 
for factorials, which follows from Euler’s integral. Thus 
together with the Maclaurin series of 
to write
is emerging as the right scaling here — do you see why? Assembling all these calculations into one master estimate, we obtain
,
, i.e. as the cardinality of the 
A permutation 
is said to have an increasing subsequence of length 
if 
If instead 
, then we say that 
we define 
we have 
for all 
corresponding to the fact that the identity permutation is the unique permutation with no decreasing subsequence of length 
means counting permutations in 
we have 
we simply have 
). Asymptotic algebraic combinatorics is supposed to deal with cases such as this by supplying useful asymptotic formulas, even when no exact formula is available. The problem we set ourselves is thus to find the analogue of Stirling’s formula for this combinatorial generalization of the factorial: 
a 
are 
denote the set of partitions of 
is called 
of a given partition 
as a row of latex 
as a second row of cells under the first row, etc. (it’s probably best if you just look at a 
if and only if 
be a Young diagram with 
, ends at 
and in which each step consists of adding a single cell. One can encode such a walk by writing the numbers 
This correspondence has the following properties: if 
corresponds to 
; if 
and the maximal length of a longest increasing subsequence in 
denote the number of rows in 
we have
(try it, or at least try writing down this sum). However, there is another way to look at things: before we start plugging in complicated products and trying to figure out what to do with them, we can step back and consider the symmetries in the problem.
are built has 
with 
so that the entries of this augmented 
Now take this augmented 
degrees, and glue it to 
where 
rows, each of length 
This process is clearly reversible (make sure you understand both why and how), and so we have a bijection between permutations in 
It seems like it shouldn’t be too hard to do the single computation of evaluating 
using Frobenius’ formula, and presumably the result of this computation will be 
Before we check this, observe that even before applying the Frobenius formula we have discovered an interesting peculiarity of the universe.
whose longest decreasing subsequence has length exactly 
Indeed, a Young diagram with 
we have
