multiple zeta values

Today I learned about Multiple Zeta Values in my department's graduate student "pizza" seminar. The speaker was Sarah Carr; the link is to her notes. Some of what follows basically rehashes definitions and conjectures from her notes; some of this is my own thoughts. In the future, you might expect to find math that I don't really understand but am pretending to on Fridays, because that's when this seminar meets.

One can define the "multiple zeta value" of a sequence of positive integers (k₁, ..., k_d), with k₁ ≥ 2 (a condition which is needed for convergence), in the following way:


The ordinary Riemann zeta function is just the special case where d=1.

It turns out that these obey certain nice relations which can be found basically by just looking at the sums, for example

ζ(a) ζ(b) = ζ(a, b) + ζ(b, a) + ζ(a+b).

This allows one to compute some of these values; for example, if a = b = 2, we get

ζ(2)² = 2 ζ(2, 2) + ζ(4)

and using a certain well-known results of Euler, namely that ζ(2) = π²/6 and ζ(4) = π⁴/90, we get ζ(2,2) = π⁴/120. Of course, one doesn't want to write ζ over and over again when studying these things, so we'd write something like

(a) * (b) = (a, b) + (b, a) + (a+b)

and this "*" is an example what's called the "stuffle product". (I swear I'm not making this name up!) You can read Carr's notes for the definition in general.

There's a natural way in which we can view sequences of integers as sequences of 0's and 1's; namely, replace each occurence of a by a-1 0's followed by a 1, so, for example, the sequence (2, 3) becomes (0, 1, 0, 0, 1). On these sequences one can define a relation called the "shuffle product", on which one has, for example,

(0, 1) Ш (0, 1) = 2(0, 1, 0, 1) + 4(0, 0, 1, 1)

or, in the original notation,

(2) Ш (2) = 2(2, 2) + 4(3, 1).

Sticking the ζs back in and turning Ш into multiplication is allowed; this is a result of Kontsevich. The proof hinges on a representation of ζ values as integrals, which is pretty natural; the integrals in question have nice power series expansions that coincide with the definition of the ζ values. Doing this, you get

ζ(2)² = 2ζ(2,2) + 4ζ(3,1)

from which we conclude that ζ(3,1) = ζ(4)/4 = π⁴/360.

It turns out, though, that the relations one gets from considering the * and Ш operations are graded, in the sense that given a relation among the ζ values, the sum of the arguments in each term of that relation (the "weight" of each term) will be the same. For example, in the relation

ζ(2)² = 2ζ(2,2) + 4ζ(3,1)

the three terms have weight 2+2, 2+2, and 3+1 respectively. It's conjectured that all the relations among ζ values come from * and Ш, from which it would follow are no relations among ζ values of different weight; this would mean that all ζ values are transcendental. Since putting a sequence which sums to m and one which sums to n into either * or Ш gives a sequence which sums to m+n, this would mean that the ζ values form a graded algebra.

I also don't know how many relations there are among ζ values of the same weight; one might hope that there are enough that we can find all the ζ values of even weight exactly by purely algebraic means, given that we know ζ(2n)? (In particular, this would imply that ζ of any sequence summing to 2n is π²ⁿ times some rational number; above, we see that ζ(4), ζ(3,1) and ζ(2,2) are all rational multiples of π⁴. But I don't have too much hope for that conjecture, because I can't even find ζ(2,1,1) that way! (I think that my inability to do this would follow from a conjecture of Zagier mentioned in Carr's notes, on the dimension of the grade-n part of the algebra of ζ values, but I don't trust myself.)

CORRECTION, Monday, September 17: There's a missing relation that I didn't know about. See this post.

profiles of interconnection networks

Flajolet and Sedgewick's Analytic Combinatorics (link goes to 12 MB PDF of the book, which is still in progress) is a most interesting book. I took a course based on the first three chapters of the book last fall; the purpose of the class was basically to teach us how to translate combinatorial structures into generating functions, in a fairly routine way. Unfortunately, we didn't get to the part of the text where we could then tell things about the asymptotics of those combinatorial structures, which is a tremendously useful thing to do.

So I've been working through parts of the book lately. In example V.8 Flajolet and sedgewick talk about a problem considered by Lagarias, Odlyzko and Zagier in their paper On The Capacity of Disjointly Shared Networks (although not quite in the same language). Flajolet and sedgewick ask: "There are 2n points on a line, with n point-to-point connections between pairs of points. What is the probable behavior of the width of such an interconnection network?" The width is defined in the following way: imagine the connections as circular arcs between the points on a horizontal line; let a vertical line sweep from left to right; then the width is the maximum number of arcs encountered by such a line.

For example, if we have n = 6 (and thus 12 points), we might make the connections 9-12, 5-10, 1-2, 6-8, 3-11, 4-7; as the line sweeps between 6 and 7 there are four open connections (and never are there more), so the width is 4. The "profile" of this network is the sequence given by the number of open connections just after the line sweeps past 0, past 1, past 2, and so on (call these a₀, a₁, a₂, ...); this is the sequence

0, 1, 0, 1, 2, 3, 4, 3, 2, 3, 2, 1, 0

and in general this sequence increases to somewhere around n/2 and then decreases. Flajolet and sedgewick says that Louchard proved this, but I haven't looked at that paper. What surprised me, when I saw this problem, is that the profile actually looks something like a parabola, as you can see from the simulations at the top of p. 311 in Flajolet and sedgewick. Louchard proved that the profile "conforms asymptotically to a deterministic parabola 2nx(1-x)... to which are superimposed random fluctuations of O(√n)". So, for example, in such a network with one thousand nodes (n = 500), the profile goes as high as 250 (when x = 1/2) before going back down to zero.

Why should this be?

Imagine that you're putting together a random interconnection network. The profile sequence clearly has the property that each member a_k is one more or one less than the last one. It'll be one more if k is the first member of one of the pairs, and one less if it's the second member. What's the probability that k is the first (i. e. smaller) member of its pair? If k is small, it'll be large; if k is near 2n then it'll be small. In fact, if we know k is a member of some pair, the other member of the pair is equally likely to be any integer from 1 to 2n except k; thus the probability that k is the smaller member of its pair is approximately 1 - k/2n, and the probability that it's the larger member is approximately k/2n.

Thus a_k = a_k-1 + 1 with probability 1 - k/2n, and a_k = a_k-1 - 1 the rest of the time. The expected value of a_k - a_k-1 is approximately (1-k/2n) - (k/2n), or 1-k/n. So, for example, one-fourth of the way through the process, when k = n/2, we expect a_k to increase by about one-half each time we increase k by one.

Integrating with respect to n, we get

a_t ≈ ∫₀^t (1-k/n) dk = t - t²/2n

which is just a rescaling of Louchard's parabola. Flajolet and sedgewick's book is full of examples of things like this, where some apparently random structure turns out to have a lot of order when you "zoom out".