Random walks

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

3a. Walks, measures

We have learned so far the basics of graph theory and probability, and time now to see if this knowledge can be of any help, in relation with concrete questions. The question that we would like to discuss, which is something very basic, is as follows: \begin{question} Given a graph [math]X[/math], with a distinguished vertex [math]*[/math]:

• What is the number [math]L_k[/math] of length [math]k[/math] loops on [math]X[/math], based at [math]*[/math]?
• Equivalently, what is the measure [math]\mu[/math] having [math]L_k[/math] as moments?

\end{question} To be more precise, we are mainly interested in the first question, counting loops on graphs, with this being notoriously related to many applied mathematics questions, of discrete type. As for the second question, this is a technical, useful probabilistic reformulation of the first question, that we will usually prefer, in what follows.

Actually, in relation with this, the fact that a measure [math]\mu[/math] as above exists indeed is not exactly obvious. But comes from the following result, which is something rather elementary, and which can be very helpful for explicit computations:

Theorem

Given a graph [math]X[/math], with adjacency matrix [math]d\in M_N(0,1)[/math], we have:

[[math]] L_k=(d^k)_{**} [[/math]]

When writing [math]d=UDU^t[/math] with [math]U\in O_N[/math] and [math]D=diag(\lambda_1,\ldots,\lambda_N)[/math] with [math]\lambda_i\in\mathbb R[/math], we have

[[math]] L_k=\sum_iU_{*i}^2\lambda_i^k [[/math]]

and the real probability measure [math]\mu[/math] having these numbers as moments is given by

[[math]] \mu=\sum_iU_{*i}^2\delta_{\lambda_i} [[/math]]

with the delta symbols standing as usual for Dirac masses.

Show Proof

There are several things going on here, the idea being as follows:

(1) According to the usual rule of matrix multiplication, the formula for the powers of the adjacency matrix [math]d\in M_N(0,1)[/math] is as follows:

[[math]] \begin{eqnarray*} (d^k)_{i_0i_k} &=&\sum_{i_1,\ldots,i_{k-1}}d_{i_0i_1}d_{i_1i_2}\ldots d_{i_{k-1}i_k}\\ &=&\sum_{i_1,\ldots,i_{k-1}}\delta_{i_0-i_1}\delta_{i_1-i_2}\ldots\delta_{i_{k-1}-i_k}\\ &=&\sum_{i_1,\ldots,i_{k-1}}\delta_{i_0-i_1-\ldots-i_{k-1}-i_k}\\ &=&\#\Big\{i_0-i_1-\ldots-i_{k-1}-i_k\Big\} \end{eqnarray*} [[/math]]

In particular, with [math]i_0=i_k=*[/math], we obtain the following formula, as claimed:

[[math]] (d^k)_{**}=\#\Big\{\!*-\,i_1-\ldots-i_{k-1}-*\Big\}=L_k [[/math]]

(2) Now since the adjacency matrix [math]d\in M_N(0,1)[/math] is symmetric, by basic linear algebra, that we know from chapter 2, this matrix is diagonalizable, with the diagonalization being as follows, with [math]U\in O_N[/math], and [math]D=diag(\lambda_1,\ldots,\lambda_N)[/math] with [math]\lambda_i\in\mathbb R[/math]:

[[math]] d=UDU^t [[/math]]

By using this formula, we obtain the second formula in the statement:

[[math]] \begin{eqnarray*} L_k &=&(d^k)_{**}\\ &=&(UD^kU^t)_{**}\\ &=&\sum_iU_{*i}\lambda_i^k(U^t)_{i*}\\ &=&\sum_iU_{*i}^2\lambda_i^k \end{eqnarray*} [[/math]]

(3) Finally, the last assertion is clear from this, because the moments of the measure in the statement, [math]\mu=\sum_iU_{*i}^2\delta_{\lambda_i}[/math], are the following numbers:

[[math]] \begin{eqnarray*} M_k &=&\int_\mathbb Rx^kd\mu(x)\\ &=&\sum_iU_{*i}^2\lambda_i^k\\ &=&L_k \end{eqnarray*} [[/math]]

Observe also that [math]\mu[/math] is indeed of mass 1, because all rows of [math]U\in O_N[/math] must be of norm 1, and so [math]\sum_iU_{*i}^2=1[/math]. Thus, we are led to the conclusions in the statement.

■

At the level of examples now, we have already seen some computations in chapter 1, so let us first review that material. We first have the following result, from there:

Theorem

For the circle graph, having [math]N[/math] vertices, the number of length [math]k[/math] loops based at one of the vertices is approximately

[[math]] L_k\simeq\frac{2^k}{N} [[/math]]

in the [math]k\to\infty[/math] limit, when [math]N[/math] is odd, and is approximately

[[math]] L_k\simeq\begin{cases} \frac{2^{k+1}}{N}&(k\ {\rm even})\\ 0&(k\ {\rm odd}) \end{cases} [[/math]]

also with [math]k\to\infty[/math], when [math]N[/math] is even.

Show Proof

This is something that we know from chapter 1, the idea being as follows:

(1) Consider the circle graph [math]X[/math], with vertices denoted [math]0,1,\ldots,N-1[/math]. Since each vertex has valence 2, any length [math]k[/math] path based at 0 will consist of a binary choice at the beginning, then another binary choice afterwards, and so on up to a [math]k[/math]-th binary choice at the end. Thus, there is a total of [math]2^k[/math] such paths, based at 0, and having length [math]k[/math].

(2) But now, based on the obvious “uniformity” of the circle, we can argue that, in the [math]k\to\infty[/math] limit, the endpoint of such a path will become random among the vertices [math]0,1,\ldots,N-1[/math]. Thus, if we want this endpoint to be 0, as to have a loop, we have [math]1/N[/math] chances for this to happen, so the total number of loops is [math]L_k\simeq 2^k/N[/math], as stated.

(3) With the remark, however, that the above argument works fine only when [math]N[/math] is odd. Indeed, when [math]N[/math] is even, the endpoint of a length [math]k[/math] path will be random among [math]0,2,\ldots,2N-2[/math] when [math]k[/math] is even, and random among [math]1,3,\ldots,2N-1[/math] when [math]k[/math] is odd. Thus for getting a loop we must assume that [math]k[/math] is even, and in this case the number of such loops is the total number of length [math]k[/math] paths, namely [math]2^k[/math], approximately divided by [math]N/2[/math], the number of points in [math]\{0,2,\ldots,2N-2\}[/math], which gives [math]L_k=2^k/(N/2)[/math], as stated.

(4) So, this was what we already knew from chapter 1, but in view of our present more advanced knowledge of the segment graph, coming from the computations from chapter 2, we can now say more about all this. And, more on this later in this chapter.

■

Another graph that we studied in chapter 1 was [math]\mathbb Z[/math], the result being as follows:

Theorem

The paths on [math]\mathbb Z[/math] are counted by the binomial coefficients. In particular, the [math]2k[/math]-paths based at [math]0[/math] are counted by the central binomial coefficients,

[[math]] L_{2k}=\binom{2k}{k} [[/math]]

and [math]\mu[/math] is the centered measure having these numbers as even moments.

Show Proof

This is something elementary, the idea being as follows:

(1) Let us try to count the length [math]k[/math] paths on [math]\mathbb Z[/math], based at [math]0[/math]. At [math]k=1,2,3,4[/math] the count results can be pictured as follows, in a self-explanatory way:

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &&1&&1 } [[/math]]

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &1&&2&&1 } [[/math]]

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &1&&3&&3&&1 } [[/math]]

[[math]] \xymatrix@R=5pt@C=15pt{ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\bullet\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\\ &1&&4&&6&&4&&1 } [[/math]]

(2) We recognize here the Pascal triangle, and the rest is just a matter of finishing. For instance we can argue that the number [math]C_k^l[/math] of length [math]k[/math] loops [math]0\to l[/math] is subject, due to the binary choice at the end, to the following recurrence relation:

[[math]] C_k^l=C_{k-1}^{l-1}+C_{k-1}^{l+1} [[/math]]

But this is exactly the recurrence relation for the Pascal triangle, as desired. As for the last assertion, this is more of an empty statement, with [math]\mu[/math] still to be computed.

■

3b. Catalan numbers

As a third example, let us try to count the loops of [math]\mathbb N[/math], based at 0. This is something less obvious, and at the experimental level, the result is as follows:

Proposition

The Catalan numbers [math]C_k[/math], counting the loops on [math]\mathbb N[/math] based at [math]0[/math],

[[math]] C_k=\#\Big\{0-i_1-\ldots-i_{2k-1}-0\Big\} [[/math]]

are numerically [math]1,2,5,14,42,132,429,1430,4862,16796,58786,\ldots[/math]

Show Proof

To start with, we have indeed [math]C_1=1[/math], the only loop here being [math]0-1-0[/math]. Then we have [math]C_2=2[/math], due to two possible loops, namely:

[[math]] 0-1-0-1-0 [[/math]]

[[math]] 0-1-2-1-0 [[/math]]

Then we have [math]C_3=5[/math], the possible loops here being as follows:

[[math]] 0-1-0-1-0-1-0 [[/math]]

[[math]] 0-1-0-1-2-1-0 [[/math]]

[[math]] 0-1-2-1-0-1-0 [[/math]]

[[math]] 0-1-2-1-2-1-0 [[/math]]

[[math]] 0-1-2-3-2-1-0 [[/math]]

In general, the same method works, with [math]C_4=14[/math] being left to you, as an exercise, and with [math]C_5[/math] and higher to me, and I will be back with the solution, in due time.

■

Obviously, computing the numbers [math]C_k[/math] is no easy task, and finding the formula of [math]C_k[/math], out of the data that we have, does not look as an easy task either. So, we will do what combinatorists do, let me teach you. The first step is to relax, then to look around, not with the aim of computing your numbers [math]C_k[/math], but rather with the aim of finding other objects counted by the same numbers [math]C_k[/math]. With a bit of luck, among these objects some will be easier to count than the others, and this will eventually compute [math]C_k[/math].

This was for the strategy. In practice now, we first have the following result:

Theorem

The Catalan numbers [math]C_k[/math] count:

• The length [math]2k[/math] loops on [math]\mathbb N[/math], based at [math]0[/math].
• The noncrossing pairings of [math]1,\ldots,2k[/math].
• The noncrossing partitions of [math]1,\ldots,k[/math].
• The length [math]2k[/math] Dyck paths in the plane.

Show Proof

All this is standard combinatorics, the idea being as follows:

(1) To start with, in what regards the various objects involved, the length [math]2k[/math] loops on [math]\mathbb N[/math] are the length [math]2k[/math] loops on [math]\mathbb N[/math] that we know, and the same goes for the noncrossing pairings of [math]1,\ldots,2k[/math], and for the noncrossing partitions of [math]1,\ldots,k[/math], the idea here being that you must be able to draw the pairing or partition in a noncrossing way.

(2) Regarding now the length [math]2k[/math] Dyck paths in the plane, these are by definition the paths from [math](0,0)[/math] to [math](k,k)[/math], marching North-East over the integer lattice [math]\mathbb Z^2\subset\mathbb R^2[/math], by staying inside the square [math][0,k]\times[0,k][/math], and staying as well under the diagonal of this square. As an example, here are the 5 possible Dyck paths at [math]n=3[/math]:

[[math]] \xymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ&\circ&\circ\ar@{-}[u]&\circ\\ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ\\ \circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ} [[/math]]

(3) Thus, we have definitions for all the objects involved, and in each case, if you start counting them, as we did in Proposition 3.5 with the loops on [math]\mathbb N[/math], you always end up with the same sequence of numbers, namely those found in Proposition 3.5:

[[math]] 1,2,5,14,42,132,429,1430,4862,16796,58786,\ldots [[/math]]

(4) In order to prove now that (1-4) produce indeed the same numbers, many things can be said. The idea is that, leaving aside mathematical brevity, and more specifically abstract reasonings of type [math]a=b,b=c\implies a=c[/math], what we have to do, in order to fully understand what is going on, is to etablish [math]\binom{4}{2}=6[/math] equalities, via bijective proofs.

(5) But this can be done, indeed. As an example here, the noncrossing pairings of [math]1,\ldots,2k[/math] from (2) are in bijection with the noncrossing partitions of [math]1,\ldots,k[/math] from (3), via fattening the pairings and shrinking the partitions. We will leave the details here as an instructive exercise, and exercise as well, to add (1) and (4) to the picture.

(6) However, matter of having our theorem formally proved, I mean by me professor and not by you student, here is a less elegant argument, which is however very quick, and does the job. The point is that, in each of the cases (1-4) under consideration, the numbers [math]C_k[/math] that we get are easily seen to be subject to the following recurrence:

[[math]] C_{k+1}=\sum_{a+b=k}C_aC_b [[/math]]

The initial data being the same, namely [math]C_1=1[/math] and [math]C_2=2[/math], in each of the cases (1-4) under consideration, we get indeed the same numbers.

■

Now we can pass to the second step, namely selecting in the above list the objects that we find the most convenient to count, and count them. This leads to:

Theorem

The Catalan numbers are given by the formula

[[math]] C_k=\frac{1}{k+1}\binom{2k}{k} [[/math]]

with this being best seen by counting the length [math]2k[/math] Dyck paths in the plane.

Show Proof

This is something quite tricky, the idea being as follows:

(1) Let us count indeed the Dyck paths in the plane. For this purpose, we use a trick. Indeed, if we ignore the assumption that our path must stay under the diagonal of the square, we have [math]\binom{2k}{k}[/math] such paths. And among these, we have the “good” ones, those that we want to count, and then the “bad” ones, those that we want to ignore.

(2) So, let us count the bad paths, those crossing the diagonal of the square, and reaching the higher diagonal next to it, the one joining [math](0,1)[/math] and [math](k,k+1)[/math]. In order to count these, the trick is to “flip” their bad part over that higher diagonal, as follows:

[[math]] \xymatrix@R=6pt@C=6pt {\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ \circ&\circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[r]\ar@{.}[u]&\circ\\ \circ&\circ\ar@{.}[r]&\circ\ar@{.}[r]&\circ\ar@{.}[r]\ar@{-}[u]&\circ\ar@{.}[u]&\circ\\ \circ&\circ\ar@{.}[u]&\circ&\circ\ar@{-}[u]&\circ&\circ\\ \circ&\circ\ar@{-}[r]\ar@{.}[u]&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ\\ \circ&\circ\ar@{-}[u]&\circ&\circ&\circ&\circ\\ \circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ&\circ&\circ} [[/math]]

(3) Now observe that, as it is obvious on the above picture, due to the flipping, the flipped bad path will no longer end in [math](k,k)[/math], but rather in [math](k-1,k+1)[/math]. Moreover, more is true, in the sense that, by thinking a bit, we see that the flipped bad paths are precisely those ending in [math](k-1,k+1)[/math]. Thus, we can count these flipped bad paths, and so the bad paths, and so the good paths too, and so good news, we are done.

(4) To finish now, by putting everything together, we have:

[[math]] \begin{eqnarray*} C_k &=&\binom{2k}{k}-\binom{2k}{k-1}\\ &=&\binom{2k}{k}-\frac{k}{k+1}\binom{2k}{k}\\ &=&\frac{1}{k+1}\binom{2k}{k} \end{eqnarray*} [[/math]]

Thus, we are led to the formula in the statement.

■

We have as well another approach to all this, computation of the Catalan numbers, this time based on rock-solid standard calculus, as follows:

Theorem

The Catalan numbers have the following properties:

• They satisfy [math]C_{k+1}=\sum_{a+b=k}C_aC_b[/math].
• The series [math]f(z)=\sum_{k\geq0}C_kz^k[/math] satisfies [math]zf^2-f+1=0[/math].
• This series is given by [math]f(z)=\frac{1-\sqrt{1-4z}}{2z}[/math].
• We have the formula [math]C_k=\frac{1}{k+1}\binom{2k}{k}[/math].

Show Proof

This is best viewed by using noncrossing pairings, as follows:

(1) Let us count the noncrossing pairings of [math]\{1,\ldots,2k+2\}[/math]. Such a pairing appears by pairing 1 to an odd number, [math]2a+1[/math], and then inserting a noncrossing pairing of [math]\{2,\ldots,2a\}[/math], and a noncrossing pairing of [math]\{2a+2,\ldots,2k+2\}[/math]. Thus we have, as claimed:

[[math]] C_{k+1}=\sum_{a+b=k}C_aC_b [[/math]]

(2) Consider now the generating series of the Catalan numbers, [math]f(z)=\sum_{k\geq0}C_kz^k[/math]. In terms of this generating series, the above recurrence gives, as desired:

[[math]] \begin{eqnarray*} zf^2 &=&\sum_{a,b\geq0}C_aC_bz^{a+b+1}\\ &=&\sum_{k\geq1}\sum_{a+b=k-1}C_aC_bz^k\\ &=&\sum_{k\geq1}C_kz^k\\ &=&f-1 \end{eqnarray*} [[/math]]

(3) By solving the equation [math]zf^2-f+1=0[/math] found above, and choosing the solution which is bounded at [math]z=0[/math], we obtain the following formula, as claimed:

[[math]] f(z)=\frac{1-\sqrt{1-4z}}{2z} [[/math]]

(4) In order to compute this function, we use the generalized binomial formula, which is as follows, with [math]p\in\mathbb R[/math] being an arbitrary exponent, and with [math]|t| \lt 1[/math]:

[[math]] (1+t)^p=\sum_{k=0}^\infty\binom{p}{k}t^k [[/math]]

To be more precise, this formula, which generalizes the usual binomial formula, holds indeed due to the Taylor formula, with the binomial coefficients being given by:

[[math]] \binom{p}{k}=\frac{p(p-1)\ldots(p-k+1)}{k!} [[/math]]

(5) For the exponent [math]p=1/2[/math], the generalized binomial coefficients are:

[[math]] \begin{eqnarray*} \binom{1/2}{k} &=&\frac{1/2(-1/2)(-3/2)\ldots(3/2-k)}{k!}\\ &=&(-1)^{k-1}\frac{1\cdot 3\cdot 5\ldots(2k-3)}{2^kk!}\\ &=&(-1)^{k-1}\frac{(2k-2)!}{2^{k-1}(k-1)!2^kk!}\\ &=&\frac{(-1)^{k-1}}{2^{2k-1}}\cdot\frac{1}{k}\binom{2k-2}{k-1}\\ &=&-2\left(\frac{-1}{4}\right)^k\cdot\frac{1}{k}\binom{2k-2}{k-1} \end{eqnarray*} [[/math]]

(6) Thus the generalized binomial formula at exponent [math]p=1/2[/math] reads:

[[math]] \sqrt{1+t}=1-2\sum_{k=1}^\infty\frac{1}{k}\binom{2k-2}{k-1}\left(\frac{-t}{4}\right)^k [[/math]]

With [math]t=-4z[/math] we obtain from this the following formula:

[[math]] \sqrt{1-4z}=1-2\sum_{k=1}^\infty\frac{1}{k}\binom{2k-2}{k-1}z^k [[/math]]

(7) Now back to our series [math]f[/math], we obtain the following formula for it:

[[math]] \begin{eqnarray*} f(z) &=&\frac{1-\sqrt{1-4z}}{2z}\\ &=&\sum_{k=1}^\infty\frac{1}{k}\binom{2k-2}{k-1}z^{k-1}\\ &=&\sum_{k=0}^\infty\frac{1}{k+1}\binom{2k}{k}z^k \end{eqnarray*} [[/math]]

(8) Thus the Catalan numbers are given by the formula the statement, namely:

[[math]] C_k=\frac{1}{k+1}\binom{2k}{k} [[/math]]

So done, and note in passing that I kept my promise, from the proof of Proposition 3.5. Indeed, with the above final formula, the numerics are easily worked out.

■

Many other things can be said about the Catalan numbers, as a continuation of the above, and about the central binomial coefficients too. We will be back to this.

In relation now with Question 3.1, we are led to the following questions: \begin{question} What are the following centered measures?

• The measure having the central binomial coefficients as even moments.
• The measure having the Catalan numbers as even moments.

\end{question} We will solve in what follows this question, which is of key importance.

3c. Stieltjes inversion

As explained above, the problem is now, how to recover a probability measure out of its moments. And the answer here, which is something non-trivial, is as follows:

Theorem

The density of a real probability measure [math]\mu[/math] can be recaptured from the sequence of moments [math]\{M_k\}_{k\geq0}[/math] via the Stieltjes inversion formula

[[math]] d\mu (x)=\lim_{t\searrow 0}-\frac{1}{\pi}\,Im\left(G(x+it)\right)\cdot dx [[/math]]

where the function on the right, given in terms of moments by

[[math]] G(\xi)=\xi^{-1}+M_1\xi^{-2}+M_2\xi^{-3}+\ldots [[/math]]

is the Cauchy transform of the measure [math]\mu[/math].

Show Proof

The Cauchy transform of our measure [math]\mu[/math] is given by:

[[math]] \begin{eqnarray*} G(\xi) &=&\xi^{-1}\sum_{k=0}^\infty M_k\xi^{-k}\\\ &=&\int_\mathbb R\frac{\xi^{-1}}{1-\xi^{-1}y}\,d\mu(y)\\ &=&\int_\mathbb R\frac{1}{\xi-y}\,d\mu(y) \end{eqnarray*} [[/math]]

Now with [math]\xi=x+it[/math], we obtain the following formula:

[[math]] \begin{eqnarray*} Im(G(x+it)) &=&\int_\mathbb RIm\left(\frac{1}{x-y+it}\right)d\mu(y)\\ &=&\int_\mathbb R\frac{1}{2i}\left(\frac{1}{x-y+it}-\frac{1}{x-y-it}\right)d\mu(y)\\ &=&-\int_\mathbb R\frac{t}{(x-y)^2+t^2}\,d\mu(y) \end{eqnarray*} [[/math]]

By integrating over [math][a,b][/math] we obtain, with the change of variables [math]x=y+tz[/math]:

[[math]] \begin{eqnarray*} \int_a^bIm(G(x+it))dx &=&-\int_\mathbb R\int_a^b\frac{t}{(x-y)^2+t^2}\,dx\,d\mu(y)\\ &=&-\int_\mathbb R\int_{(a-y)/t}^{(b-y)/t}\frac{t}{(tz)^2+t^2}\,t\,dz\,d\mu(y)\\ &=&-\int_\mathbb R\int_{(a-y)/t}^{(b-y)/t}\frac{1}{1+z^2}\,dz\,d\mu(y)\\ &=&-\int_\mathbb R\left(\arctan\frac{b-y}{t}-\arctan\frac{a-y}{t}\right)d\mu(y) \end{eqnarray*} [[/math]]

Now observe that with [math]t\searrow0[/math] we have:

[[math]] \lim_{t\searrow0}\left(\arctan\frac{b-y}{t}-\arctan\frac{a-y}{t}\right) =\begin{cases} \frac{\pi}{2}-\frac{\pi}{2}=0& (y \lt a)\\ \frac{\pi}{2}-0=\frac{\pi}{2}& (y=a)\\ \frac{\pi}{2}-(-\frac{\pi}{2})=\pi& (a \lt y \lt b)\\ 0-(-\frac{\pi}{2})=\frac{\pi}{2}& (y=b)\\ -\frac{\pi}{2}-(-\frac{\pi}{2})=0& (y \gt b) \end{cases} [[/math]]

We therefore obtain the following formula:

[[math]] \lim_{t\searrow0}\int_a^bIm(G(x+it))dx=-\pi\left(\mu(a,b)+\frac{\mu(a)+\mu(b)}{2}\right) [[/math]]

Thus, we are led to the conclusion in the statement.

■

Before getting further, let us mention that the above result does not fully solve the moment problem, because we still have the question of understanding when a sequence of numbers [math]M_1,M_2,M_3,\ldots[/math] can be the moments of a measure [math]\mu[/math]. We have here:

Theorem

A sequence of numbers [math]M_0,M_1,M_2,M_3,\ldots\in\mathbb R[/math], with [math]M_0=1[/math], is the series of moments of a real probability measure [math]\mu[/math] precisely when:

[[math]] \begin{vmatrix}M_0\end{vmatrix}\geq0\quad,\quad \begin{vmatrix} M_0&M_1\\ M_1&M_2 \end{vmatrix}\geq0\quad,\quad \begin{vmatrix} M_0&M_1&M_2\\ M_1&M_2&M_3\\ M_2&M_3&M_4\\ \end{vmatrix}\geq0\quad,\quad \ldots [[/math]]

That is, the associated Hankel determinants must be all positive.

Show Proof

This is something a bit more advanced, the idea being as follows:

(1) As a first observation, the positivity conditions in the statement tell us that the following associated linear forms must be positive:

[[math]] \sum_{i,j=1}^nc_i\bar{c}_jM_{i+j}\geq0 [[/math]]

(2) But this is something very classical, in one sense the result being elementary, coming from the following computation, which shows that we have positivity indeed:

[[math]] \begin{eqnarray*} \int_\mathbb R\left|\sum_{i=1}^nc_ix^i\right|^2d\mu(x) &=&\int_\mathbb R\sum_{i,j=1}^nc_i\bar{c}_jx^{i+j}d\mu(x)\\ &=&\sum_{i,j=1}^nc_i\bar{c}_jM_{i+j} \end{eqnarray*} [[/math]]

(3) As for the other sense, here the result comes once again from the above formula, this time via some standard functional analysis.

■

As a basic application of the Stieltjes formula, let us solve the moment problem for the Catalan numbers [math]C_k[/math], and for the central binomial coefficients [math]D_k[/math]. We first have:

Theorem

The real measure having as even moments the Catalan numbers, [math]C_k=\frac{1}{k+1}\binom{2k}{k}[/math], and having all odd moments [math]0[/math] is the measure

[[math]] \gamma_1=\frac{1}{2\pi}\sqrt{4-x^2}dx [[/math]]

called Wigner semicircle law on [math][-2,2][/math].

Show Proof

In order to apply the inversion formula, our starting point will be the formula from Theorem 3.8 for the generating series of the Catalan numbers, namely:

[[math]] \sum_{k=0}^\infty C_kz^k=\frac{1-\sqrt{1-4z}}{2z} [[/math]]

By using this formula with [math]z=\xi^{-2}[/math], we obtain the following formula:

[[math]] \begin{eqnarray*} G(\xi) &=&\xi^{-1}\sum_{k=0}^\infty C_k\xi^{-2k}\\ &=&\xi^{-1}\cdot\frac{1-\sqrt{1-4\xi^{-2}}}{2\xi^{-2}}\\ &=&\frac{\xi}{2}\left(1-\sqrt{1-4\xi^{-2}}\right)\\ &=&\frac{\xi}{2}-\frac{1}{2}\sqrt{\xi^2-4} \end{eqnarray*} [[/math]]

Now let us apply Theorem 3.10. The study here goes as follows:

(1) According to the general philosophy of the Stieltjes formula, the first term, namely [math]\xi/2[/math], which is “trivial”, will not contribute to the density.

(2) As for the second term, which is something non-trivial, this will contribute to the density, the rule here being that the square root [math]\sqrt{\xi^2-4}[/math] will be replaced by the “dual” square root [math]\sqrt{4-x^2}\,dx[/math], and that we have to multiply everything by [math]-1/\pi[/math].

(3) As a conclusion, by Stieltjes inversion we obtain the following density:

[[math]] d\mu(x) =-\frac{1}{\pi}\cdot-\frac{1}{2}\sqrt{4-x^2}\,dx =\frac{1}{2\pi}\sqrt{4-x^2}dx [[/math]]

Thus, we have obtained the mesure in the statement, and we are done.

■

We have the following version of the above result:

Theorem

The real measure having as sequence of moments the Catalan numbers, [math]C_k=\frac{1}{k+1}\binom{2k}{k}[/math], is the measure

[[math]] \pi_1=\frac{1}{2\pi}\sqrt{4x^{-1}-1}\,dx [[/math]]

called Marchenko-Pastur law on [math][0,4][/math].

Show Proof

As before, we use the standard formula for the generating series of the Catalan numbers. With [math]z=\xi^{-1}[/math] in that formula, we obtain the following formula:

[[math]] \begin{eqnarray*} G(\xi) &=&\xi^{-1}\sum_{k=0}^\infty C_k\xi^{-k}\\ &=&\xi^{-1}\cdot\frac{1-\sqrt{1-4\xi^{-1}}}{2\xi^{-1}}\\ &=&\frac{1}{2}\left(1-\sqrt{1-4\xi^{-1}}\right)\\ &=&\frac{1}{2}-\frac{1}{2}\sqrt{1-4\xi^{-1}} \end{eqnarray*} [[/math]]

With this in hand, let us apply now the Stieltjes inversion formula, from Theorem 3.10. We obtain, a bit as before in Theorem 3.12, the following density:

[[math]] d\mu(x) =-\frac{1}{\pi}\cdot-\frac{1}{2}\sqrt{4x^{-1}-1}\,dx =\frac{1}{2\pi}\sqrt{4x^{-1}-1}\,dx [[/math]]

Thus, we are led to the conclusion in the statement.

■

Regarding now the central binomial coefficients, we have here:

Theorem

The real probability measure having as moments the central binomial coefficients, [math]D_k=\binom{2k}{k}[/math], is the measure

[[math]] \alpha_1=\frac{1}{\pi\sqrt{x(4-x)}}\,dx [[/math]]

called arcsine law on [math][0,4][/math].

Show Proof

We have the following computation, using some standard formulae:

[[math]] \begin{eqnarray*} G(\xi) &=&\xi^{-1}\sum_{k=0}^\infty D_k\xi^{-k}\\ &=&\frac{1}{\xi}\sum_{k=0}^\infty D_k\left(-\frac{t}{4}\right)^k\\ &=&\frac{1}{\xi}\cdot\frac{1}{\sqrt{1-4/\xi}}\\ &=&\frac{1}{\sqrt{\xi(\xi-4)}} \end{eqnarray*} [[/math]]

But this gives the density in the statement, via Theorem 3.10.

■

Finally, we have the following version of the above result:

Theorem

The real probability measure having as moments the middle binomial coefficients, [math]E_k=\binom{k}{[k/2]}[/math], is the following law on [math][-2,2][/math],

[[math]] \sigma_1=\frac{1}{2\pi}\sqrt{\frac{2+x}{2-x}}\,dx [[/math]]

called modified arcsine law on [math][-2,2][/math].

Show Proof

In terms of the central binomial coefficients [math]D_k[/math], we have:

[[math]] E_{2k}=\binom{2k}{k}=\frac{(2k)!}{k!k!}=D_k [[/math]]

[[math]] E_{2k-1}=\binom{2k-1}{k}=\frac{(2k-1)!}{k!(k-1)!}=\frac{D_k}{2} [[/math]]

Standard calculus based on the Taylor formula for [math](1+t)^{-1/2}[/math] gives:

[[math]] \frac{1}{2x}\left(\sqrt{\frac{1+2x}{1-2x}}-1\right)=\sum_{k=0}^\infty E_kx^k [[/math]]

With [math]x=\xi^{-1}[/math] we obtain the following formula for the Cauchy transform:

[[math]] \begin{eqnarray*} G(\xi) &=&\xi^{-1}\sum_{k=0}^\infty E_k\xi^{-k}\\ &=&\frac{1}{\xi}\left(\sqrt{\frac{1+2/\xi}{1-2/\xi}}-1\right)\\ &=&\frac{1}{\xi}\left(\sqrt{\frac{\xi+2}{\xi-2}}-1\right) \end{eqnarray*} [[/math]]

By Stieltjes inversion we obtain the density in the statement.

■

All this is very nice, and we are obviously building here, as this book goes by, some solid knowledge in classical probability. We will be back to all this later.

3d. Circular measures

With the above done, we can come back now to walks on finite graphs, that we know from the above to be related to the eigenvalues of the adjacency matrix [math]d\in M_N(0,1)[/math]. But here, we are led to the following philosophical question, to start with: \begin{question} What are the most important finite graphs, that we should do our computations for? \end{question} Not an easy question, you have to agree with me, with the answer to this obviously depending on your previous experience with mathematics, or physics, or chemistry, or computer science, or other branch of science that you are interested in, and also, on the specific problems that you are the most in love with, in that part of science.

So, we have to be subjective here. And with me writing this book, and doing some sort of complicated quantum physics, as daytime job, I will choose the ADE graphs. It is beyond our scope here to explain where these ADE graphs exactly come from, and what they are good for, but as a piece of advertisement for them, we have:

\begin{advertisement} The ADE graphs classify the following:

• Basic Lie groups and algebras.
• Subgroups of [math]SU_2[/math] and of [math]SO_3[/math].
• Singularities of algebraic manifolds.
• Basic invariants of knots and links.
• Subfactors and planar algebras of small index.
• Subgroups of the quantum permutation group [math]S_4^+[/math].
• Basic quantum field theories, and other physics beasts.

\end{advertisement} Which sounds exciting, doesn't it. So, have a look at this, and with the comment that some heavy learning work is needed, in order to understand how all this works. And with the extra comment that, in view of (7), tough physics, no one really understands how all this works. A nice introduction to all this is the paper of Jones .

Getting to work now, we first need to know what the ADE graphs are. The A graphs, which are the simplest, are as follows, with the distinguished vertex being denoted [math]\bullet[/math], and with [math]A_n[/math] having [math]n\geq2[/math] vertices, and [math]\tilde{A}_{2n}[/math] having [math]2n\geq2[/math] vertices:

[[math]] A_n=\bullet-\circ-\circ\cdots\circ-\circ-\circ\hskip18mm A_{\infty}=\bullet-\circ-\circ-\circ\cdots\hskip7mm [[/math]]

\vskip-3mm

[[math]] \ \ \ \ \ \ \ \tilde{A}_{2n}= \begin{matrix} \circ&\!\!\!\!-\circ-\circ\cdots\circ-\circ-&\!\!\!\!\circ\\ |&&\!\!\!\!|\\ \bullet&\!\!\!\!-\circ-\circ-\circ-\circ-&\!\!\!\!\circ\\ \\ \\ \end{matrix}\hskip20mm \tilde{A}_\infty= \begin{matrix} \circ&\!\!\!\!-\circ-\circ-\circ\cdots\\ |&\\ \bullet&\!\!\!\!-\circ-\circ-\circ\cdots\\ \\ \\ \end{matrix} \hskip15mm [[/math]]

\vskip-7mm These A graphs do not actually look that scary, because we already met all of them in the above, and as a comment on them, summarizing the situation, we have: \begin{comment} With the [math]A[/math] graphs we are not really lost into quantum physics, because all these graphs are quite familiar to us, as follows:

• [math]A_n[/math] is the segment.
• [math]A_\infty[/math] is the [math]\mathbb N[/math] graph.
• [math]\tilde{A}_{2n}[/math] is the circle.
• [math]\tilde{A}_\infty[/math] is the [math]\mathbb Z[/math] graph.

\end{comment} You might probably say, why not stopping here, and doing our unfinished business for the segment and the circle, with whatever new ideas that we might have. Good point, but in answer, these ideas will apply as well, with minimal changes, to the D graphs, which are as follows, with [math]D_n[/math] having [math]n\geq3[/math] vertices, and [math]\tilde{D}_n[/math] having [math]n+1\geq5[/math] vertices:

[[math]] D_n=\bullet-\circ-\circ\dots\circ- \begin{matrix}\ \circ\\ \ |\\ \ \circ \\ \ \\ \ \end{matrix}-\circ\hskip71mm [[/math]]

\vskip-7mm

[[math]] \hskip7mm\tilde{D}_n=\bullet- \begin{matrix}\circ\\ |\\ \circ\\ \ \\ \ \end{matrix}-\circ\dots\circ- \begin{matrix}\ \circ\\ \ |\\ \ \circ \\ \ \\ \ \end{matrix}-\circ\hskip18mm [[/math]]

\vskip-7mm

[[math]] \hskip50mm D_\infty=\bullet- \begin{matrix}\circ\\ |\\ \circ\\ \ \\ \ \end{matrix}-\circ-\circ\cdots [[/math]]

\vskip-7mm As mentioned above, it is beyond our scope here to explain what the ADE graphs really stand for, but as an informal comment on these latter D graphs, we have: \begin{comment} The D graphs are not that scary either, and they can be thought of as being certain technical versions of the A graphs. \end{comment} So, this is the situation, you have to trust me here, and for more on all this, check for instance the paper of Jones . In what concerns us, we will just take the above D graphs as they come, and do our loop count work for them, without questions asked.

As another comment, the labeling conventions for the AD graphs, while very standard, can be a bit confusing. The first graph in each series is by definition as follows:

[[math]] A_2=\bullet-\circ\hskip13mm \tilde{A}_2=\begin{matrix} \circ\\ ||\\ \bullet\\ &\\ &\\ \end{matrix}\hskip13mm D_3=\begin{matrix}\ \circ\\ \ |\\ \ \bullet \\ \ \\ \ \end{matrix}-\circ \hskip13mm \tilde{D}_4=\bullet-\!\!\!\!\!\begin{matrix} \circ\hskip5mm \circ\\ \backslash\ \,\slash\\ \circ\\ &\\ &\\ \end{matrix}\!\!\!\!\!\!\!\!\!\!-\circ [[/math]]

\vskip-7mm Finally, there are also a number of exceptional ADE graphs. First we have:

[[math]] E_6=\bullet-\circ- \begin{matrix}\circ\\ |\\ \circ\\ \ \\ \ \end{matrix}- \circ-\circ\hskip71mm [[/math]]

\vskip-13mm

[[math]] E_7=\bullet-\circ-\circ- \begin{matrix}\circ\\ |\\ \circ\\ \ \ \\ \ \end{matrix}- \circ-\circ\hskip18mm [[/math]]

\vskip-15mm

[[math]] \hskip30mm E_8=\bullet-\circ-\circ-\circ- \begin{matrix}\circ\\ |\\ \circ\\ \ \\ \ \end{matrix}- \circ-\circ [[/math]]

\vskip-5mm Then, we have extended versions of the above exceptional graphs, as follows:

[[math]] \tilde{E}_6=\bullet-\circ-\begin{matrix} \circ\\ | \\ \circ\\ |&\\ \circ&\!\!\!\!-\ \circ\\ \ \\ \ \\ \ \\ \ \end{matrix}-\circ\hskip71mm [[/math]]

\vskip-22mm

[[math]] \tilde{E}_7=\bullet-\circ-\circ- \begin{matrix}\circ\\ |\\ \circ\\ \ \\ \ \end{matrix}- \circ-\circ-\circ\hskip18mm [[/math]]

\vskip-15mm

[[math]] \hskip30mm \tilde{E}_8=\bullet-\circ-\circ-\circ-\circ- \begin{matrix}\circ\\ |\\ \circ\\ \ \\ \ \end{matrix}- \circ-\circ [[/math]]

\vskip-5mm And good news, that is all. Hard job for me to come now with a comment on these latter E graphs, along the lines of Comments 3.18 and 3.19, and here is what I have: \begin{comment} The E graphs naturally complement the AD series, by capturing the combinatorics of certain “exceptional” phenomena in mathematics and physics. \end{comment} So long for difficult definitions and related informal talk, and as already mentioned in the above, for more on all this, have a look at the paper of Jones . Getting now to work, we have some new graphs, and here is the problem that we would like to solve: \begin{problem} How to count loops on the ADE graphs? \end{problem} In answer, as mentioned in Comment 3.18, we are already familiar with two of the ADE graphs, namely [math]A_\infty[/math] and [math]\tilde{A}_\infty[/math], which are respectively the graphs that we previously called [math]\mathbb N[/math] and [math]\mathbb Z[/math]. So, based on our work for these graphs, where the combinatorics naturally led us into generating series, let us formulate the following definition:

Definition

The Poincaré series of a rooted bipartite graph [math]X[/math] is

[[math]] f(z)=\sum_{k=0}^\infty L_{2k}z^k [[/math]]

where [math]L_{2k}[/math] is the number of [math]2k[/math]-loops based at the root.

To be more precise, observe that all the above ADE graphs are indeed bipartite. Now the point is that, for a bipartite graph, the loops based at any point must have even length. Thus, in order to study the loops on the ADE graphs, based at the root, we just have to count the above numbers [math]L_{2k}[/math]. And then, considering the generating series [math]f(z)[/math] of these numbers, and calling this Poincaré series, is something very standard.

Before getting into computations, let us introduce as well:

Definition

The positive spectral measure [math]\mu[/math] of a rooted bipartite graph [math]X[/math] is the real probability measure having the numbers [math]L_{2k}[/math] as moments:

[[math]] \int_\mathbb Rx^kd\mu(x)=L_{2k} [[/math]]

Equivalently, we must have the Stieltjes transform formula

[[math]] f(z)=\int_\mathbb R\frac{1}{1-xz}\,d\mu(x) [[/math]]

where [math]f[/math] is the Poincaré series of [math]X[/math].

Here the existence of [math]\mu[/math], and the fact that this is indeed a positive measure, meaning a measure supported on [math][0,\infty)[/math], comes from the following simple fact:

Theorem

The positive spectral measure of a rooted bipartite graph [math]X[/math] is given by the following formula, with [math]d[/math] being the adjacency matrix of the graph,

[[math]] \mu=law(d^2) [[/math]]

and with the probabilistic computation being with respect to the expectation

[[math]] A\to \lt A \gt [[/math]]

with [math] \lt A \gt [/math] being the [math](*,*)[/math]-entry of a matrix [math]A[/math], where [math]*[/math] is the root.

Show Proof

With the above conventions, we have the following computation:

[[math]] \begin{eqnarray*} f(z) &=&\sum_{k=0}^\infty L_{2k}z^k\\ &=&\sum_{k=0}^\infty\left \lt d^{2k}\right \gt z^k\\ &=&\left \lt \frac{1}{1-d^2z}\right \gt \end{eqnarray*} [[/math]]

But this shows that we have [math]\mu=law(d^2)[/math], as desired.

■

The above result shows that computing [math]\mu[/math] might be actually a simpler problem than computing [math]f[/math], and in practice, this is indeed the case. So, in what follows we will rather forget about loops and Definition 3.22, and use Definition 3.23 instead, with our computations to follow being based on the concrete interpretation from Theorem 3.24.

However, even with this probabilistic trick in our bag, things are not exactly trivial. So, following now , let us introduce as well the following notion:

Definition

The circular measure [math]\varepsilon[/math] of a rooted bipartite graph [math]X[/math] is given by

[[math]] d\varepsilon(q)=d\mu((q+q^{-1})^2) [[/math]]

where [math]\mu[/math] is the associated positive spectral measure.

To be more precise, we know from Theorem 3.24 that the positive measure [math]\mu[/math] is the spectral measure of a certain positive matrix, [math]d^2\geq0[/math], and it follows from this, and from basic spectral theory, that this measure is supported by the positive reals:

[[math]] supp(\mu)\subset\mathbb R_+ [[/math]]

But then, with this observation in hand, we can define indeed the circular measure [math]\varepsilon[/math] as above, as being the pullback of [math]\mu[/math] via the following map:

[[math]] \mathbb R\cup\mathbb T\to\mathbb R_+\quad,\quad q\to (q+q^{-1})^2 [[/math]]

As a basic example for this, to start with, assume that [math]\mu[/math] is a discrete measure, supported by [math]n[/math] positive numbers [math]x_1 \lt \ldots \lt x_n[/math], with corresponding densities [math]p_1,\ldots,p_n[/math]:

[[math]] \mu=\sum_{i=1}^n p_i\delta_{x_i} [[/math]]

For each [math]i\in\{1,\ldots,n\}[/math] the equation [math](q+q^{-1})^2=x_i[/math] has then four solutions, that we can denote [math]q_i,q_i^{-1},-q_i,-q_i^{-1}[/math]. And with this notation, we have:

[[math]] \varepsilon=\frac{1}{4}\sum_{i=1}^np_i\left(\delta_{q_i}+\delta_{q_i^{-1}}+\delta_{-q_i}+\delta_{-q_i^{-1}}\right) [[/math]]

In general, the basic properties of [math]\varepsilon[/math] can be summarized as follows:

Theorem

The circular measure has the following properties:

• [math]\varepsilon[/math] has equal density at [math]q,q^{-1},-q,-q^{-1}[/math].
• The odd moments of [math]\varepsilon[/math] are [math]0[/math].
• The even moments of [math]\varepsilon[/math] are half-integers.
• When [math]X[/math] has norm [math]\leq 2[/math], [math]\varepsilon[/math] is supported by the unit circle.
• When [math]X[/math] is finite, [math]\varepsilon[/math] is discrete.
• If [math]K[/math] is a solution of [math]d=K+K^{-1}[/math], then [math]\varepsilon=law(K)[/math].

Show Proof

These results can be deduced from definitions, the idea being that (1-5) are trivial, and that (6) follows from the formula of [math]\mu[/math] from Theorem 3.24.

■

Getting now to computations, remember our struggle from the above, with the circle graph? We can now solve this question, majestically, as follows:

Theorem

The circular measure of the basic index [math]4[/math] graph, namely

[[math]] \begin{matrix} &\circ&\!\!\!\!-\circ-\circ\cdots\circ-\circ-&\!\!\!\!\circ\cr \tilde{A}_{2n}=&|&&\!\!\!\!|\cr &\bullet&\!\!\!\!-\circ-\circ-\circ-\circ-&\!\!\!\!\circ\cr\cr\cr\end{matrix} [[/math]]

\vskip-7mm is the uniform measure on the [math]2n[/math]-roots of unity.

Show Proof

Let us identify the vertices of [math]X=\tilde{A}_{2n}[/math] with the group [math]\{w^k\}[/math] formed by the [math]2n[/math]-th roots of unity in the complex plane, where [math]w=e^{\pi i/n}[/math]. The adjacency matrix of [math]X[/math] acts then on the functions [math]f\in C(X)[/math] in the following way:

[[math]] df(w^s)=f(w^{s-1})+f(w^{s+1}) [[/math]]

But this shows that we have [math]d=K+K^{-1}[/math], where [math]K[/math] is given by:

[[math]] Kf(w^s)=f(w^{s+1}) [[/math]]

Thus we can use Theorem 3.24 and Theorem 3.26 (6), and we get:

[[math]] \varepsilon=law(K) [[/math]]

But this is the uniform measure on the [math]2n[/math]-roots of unity, as claimed.

■

All this is very nice, so, before going ahead with more computations, let us have an excursion into subfactor theory, and explain what is behind this trick. Following Jones , we can introduce the theta series of a graph [math]X[/math], as a version of the Poincaré series, via the change of variables [math]z^{-1/2}=q^{1/2}+q^{-1/2}[/math], as follows:

Definition

The theta series of a rooted bipartite graph [math]X[/math] is

[[math]] \Theta(q)=q+\frac{1-q}{1+q}f\left(\frac{q}{(1+q)^2}\right) [[/math]]

where [math]f[/math] is the Poincaré series.

The theta series can be written as [math]\Theta(q)=\sum a_rq^r[/math], and it follows from the above formula, via some simple manipulations, that its coefficients are integers:

[[math]] a_r\in\mathbb Z [[/math]]

In fact, we have the following explicit formula from Jones' paper , relating the coefficients of [math]\Theta(q)=\sum a_rq^r[/math] to those of the Poincaré series [math]f(z)=\sum c_kz^k[/math]:

[[math]] a_r=\sum_{k=0}^r(-1)^{r-k}\frac{2r}{r+k}\begin{pmatrix}r+k\cr r-k\end{pmatrix}c_k [[/math]]

As an important comment now, in the case where [math]X[/math] is the principal graph of a subfactor [math]A_0\subset A_1[/math] of index [math]N \gt 4[/math], it is known from that the numbers [math]a_r[/math] are certain multiplicities associated to the planar algebra inclusion [math]TL_N\subset P[/math], as explained there. In particular, the coefficients of the theta series are in this case positive integers:

[[math]] a_r\in\mathbb N [[/math]]

In relation now with the circular measure, the result here, which is quite similar to the Stieltjes transform formula from Definition 3.23, is as follows:

Theorem

We have the Stieltjes transform type formula

[[math]] 2\int\frac{1}{1-qu^2}\,d\varepsilon(u)=1+T(q)(1-q) [[/math]]

where the [math]T[/math] series of a rooted bipartite graph [math]X[/math] is by definition given by

[[math]] T(q)=\frac{\Theta(q)-q}{1-q} [[/math]]

with [math]\Theta[/math] being the associated theta series.

Show Proof

This follows by applying the change of variables [math]q\to (q+q^{-1})^2[/math] to the fact that [math]f[/math] is the Stieltjes transform of [math]\mu[/math]. Indeed, we obtain in this way:

[[math]] \begin{eqnarray*} 2\int\frac{1}{1-qu^2}\,d\varepsilon(u) &=&1+\frac{1-q}{1+q}f\left(\frac{q}{(1+q)^2}\right)\\ &=&1+\Theta(q)-q\\ &=&1+T(q)(1-q) \end{eqnarray*} [[/math]]

Thus, we are led to the conclusion in the statement.

■

Summarizing, we have a whole menagery of subfactor, planar algebra and bipartite graph invariants, which come in several flavors, namely series and measures, and which can be linear or circular, and which all appear as versions of the Poincaré series.

In order to discuss all this more systematically, let us introduce as well:

Definition

The series of the form

[[math]] \xi(n_1,\ldots,n_s:m_1,\ldots,m_t)=\frac{(1-q^{n_1})\ldots(1-q^{n_s})}{(1-q^{m_1})\ldots(1-q^{m_t})} [[/math]]

with [math]n_i,m_i\in\mathbb N[/math] are called cyclotomic.

It is technically convenient to allow as well [math]1+q^n[/math] factors, to be designated by [math]n^+[/math] symbols in the above writing. For instance we have, by definition:

[[math]] \xi(2^+:3)=\xi(4:2,3) [[/math]]

Also, it is convenient in what follows to use the following notations:

[[math]] \xi'=\frac{\xi}{1-q}\quad,\quad \xi''=\frac{\xi}{1-q^2} [[/math]]

The Poincaré series of the ADE graphs are given by quite complicated formulae. However, the corresponding [math]T[/math] series are all cyclotomic, as follows:

Theorem

The [math]T[/math] series of the ADE graphs are as follows:

• For [math]A_{n-1}[/math] we have [math]T=\xi(n-1:n)[/math].
• For [math]D_{n+1}[/math] we have [math]T=\xi(n-1^+:n^+)[/math].
• For [math]\tilde{A}_{2n}[/math] we have [math]T=\xi'(n^+:n)[/math].
• For [math]\tilde{D}_{n+2}[/math] we have [math]T=\xi''(n+1^+:n)[/math].
• For [math]E_6[/math] we have [math]T=\xi(8:3,6^+)[/math].
• For [math]E_7[/math] we have [math]T=\xi(12:4,9^+)[/math].
• For [math]E_8[/math] we have [math]T=\xi(5^+,9^+:15^+)[/math].
• For [math]\tilde{E}_6[/math] we have [math]T=\xi(6^+:3,4)[/math].
• For [math]\tilde{E}_7[/math] we have [math]T=\xi(9^+:4,6)[/math].
• For [math]\tilde{E}_8[/math] we have [math]T=\xi(15^+:6,10)[/math].

Show Proof

These formulae were obtained in , by counting loops, and then by making the following change of variables, and factorizing the resulting series:

[[math]] z^{-1/2}=q^{1/2}+q^{-1/2} [[/math]]

An alternative proof for these formulae can be obtained by using planar algebra methods, along the lines of the paper of Jones . For details here, see .

■

In order to formulate our final results, we will need more theory. First, we have:

Definition

A cyclotomic measure is a probability measure [math]\varepsilon[/math] on the unit circle, having the following properties:

• [math]\varepsilon[/math] is supported by the [math]2n[/math]-roots of unity, for some [math]n\in\mathbb N[/math].
• [math]\varepsilon[/math] has equal density at [math]q,q^{-1},-q,-q^{-1}[/math].

As a first observation, it follows from Theorem 3.26 and from Theorem 3.31 that the circular measures of the finite ADE graphs are supported by certain roots of unity, hence are cyclotomic. We will be back to this in a moment, with details, and computations.

At the general level now, let us introduce as well the following notion:

Definition

The [math]T[/math] series of a cyclotomic measure [math]\varepsilon[/math] is given by

[[math]] 1+T(q)(1-q)=2\int\frac{1}{1-qu^2}\,d\varepsilon(u) [[/math]]

with [math]\varepsilon[/math] being as usual the circular spectral measure.

Observe that this formula is nothing but the one in Theorem 3.29, written now in the other sense. In other words, if the cyclotomic measure [math]\varepsilon[/math] happens to be the circular measure of a rooted bipartite graph, then the [math]T[/math] series as defined above coincides with the [math]T[/math] series as defined before. This is useful for explicit computations.

Good news, with the above technology in hand, and with a computation already done, in Theorem 3.27, we are now ready to discuss the circular measures of all ADE graphs. The idea will be that these measures are all cyclotomic, of level [math]\leq 3[/math], and can be expressed in terms of the basic polynomial densities of degree [math]\leq 6[/math], namely:

[[math]] \alpha=Re(1-q^2) [[/math]]

[[math]] \beta=Re(1-q^4) [[/math]]

[[math]] \gamma=Re(1-q^6) [[/math]]

To be more precise, we have the following final result on the subject, with [math]\alpha,\beta,\gamma[/math] being as above, with [math]d_n[/math] being the uniform measure on the [math]2n[/math]-th roots of unity, and with [math]d_n'=2d_{2n}-d_n[/math] being the uniform measure on the odd [math]4n[/math]-roots of unity:

Theorem

The circular measures of the ADE graphs are given by:

• [math]A_{n-1}\to\alpha_n[/math].
• [math]\tilde{A}_{2n}\to d_n[/math].
• [math]D_{n+1}\to\alpha_n'[/math].
• [math]\tilde{D}_{n+2}\to (d_n+d_1')/2[/math].
• [math]E_6\to\alpha_{12}+(d_{12}-d_6-d_4+d_3)/2[/math].
• [math]E_7\to\beta_9'+(d_1'-d_3')/2[/math].
• [math]E_8\to\alpha_{15}'+\gamma_{15}'-(d_5'+d_3')/2[/math].
• [math]\tilde{E}_{n+3}\to (d_n+d_3+d_2-d_1)/2[/math].

Show Proof

This is something which can be proved in three steps, as follows:

(1) For the simplest graph, namely the circle [math]\tilde{A}_{2n}[/math], we already have the result, from Theorem 3.27, with the proof there being something elementary.

(2) For the other non-exceptional graphs, that is, of type A and D, the same method works, namely direct loop counting, with some matrix tricks. See .

(3) In general, this follows from the [math]T[/math] series formulae in Theorem 3.31, via some manipulations based on the general conversion formulae given above. See .

■

We refer to and the subsequent literature for more on all this. Also, let us point out that all this leads to a more conceptual understanding of what we did before, for the graphs [math]\mathbb N[/math] and [math]\mathbb Z[/math]. Indeed, even for these very basic graphs, using the unit circle and circular measures as above leads to a better understanding of the combinatorics.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].