Three-Toed Sloth

Books to Read While the Algae Grow in Your Fur, March 2025

Attention conservation notice: I have no taste, and no qualification to opine on pure mathematics, sociology, or adaptations of Old English epic poetry. Also, most of my reading this month was done at odd hours and/or while chasing after a toddler, so I'm less reliable and more cranky than usual.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics [doi:10.1017/CBO9780511801655]

I should begin by admitting that I have never learned much combinatorics, and never really liked what I did learn. To say my knowledge topped out at Stirling's approximation to $n!$ is only a mild exaggeration. Nonetheless, after reading this book, I think I begin to get it. I'll risk making a fool of myself by explaining.

We start with some class $\mathcal{A}$ of discrete, combinatorial objects, like a type of tree or graph obeying some constraints and rules of construction. There's a notion of "size" for these objects (say, the number of nodes in the graph, or the number of leaves in the tree). We are interested in counting the number of objects of size $n$. This gives us a sequence $A_0, A_1, A_2, \ldots A_n, \ldots$.

Now whenever we have a sequence of numbers $A_n$, we can encode it in a "generating function" \[ A(z) = \sum_{n=0}^{\infty}{A_n z^n} \] and recover the sequence by taking derivatives at the origin: \[ A_n = \frac{1}{n!} \left. \frac{d^n A}{dz^n} \right|_{z=0} \] (I'll claim the non-mathematician's privilege of not worrying about whether the series converges, the derivatives exist, etc.) When I first encountered this idea as a student, it seemed rather pointless to me --- we define the generating function in terms of the sequence, so why do we need to differentiate the GF to get the sequence?!? The trick, of course, is to find indirect ways of getting the generating function.

Part A of the book is about what the authors call the "symbolic method" for building up the generating functions of combinatorial classes, by expressing them in terms of certain basic operations on simpler classes. The core operations, for structures with unlabeled parts, are disjoint union, Cartesian product, taking sequences, taking cycles, taking multisets, and taking power sets. Each of these corresponds to a definite transformation of the generating function: if $\mathcal{A}$s are ordered pairs of $\mathcal{B}$s and $\mathcal{C}$s (so the operation is Cartesian product), then $A(z) = B(z) C(z)$, while if $\mathcal{A}$s are sequences of $\mathcal{B}$s, then $A(z) = 1/(1-B(z))$, etc. (Chapter I.) For structures with labeled parts, slightly different, but parallel, rules apply. (Chapter II.) These rules can be related very elegantly to constructions with finite automata and regular languages, and to context-free languages. If one is interested not just in the number of objects of some size $n$, but the number of size $n$ with some other "parameter" taking a fixed value (e.g., the number of graphs on $n$ nodes with $k$ nodes of degree 1), multivariate generating functions allow us to count them, too (Chapter III). (Letting $k$ vary for fixed $n$ of course gives a probability distribution.) When the parameters of a complex combinatorial object are "inherited" from the parameters of the simpler objects out of which it is built, the rules for transforming generating functions also apply.

In favorable cases, we get nice expressions (e.g., ratios of polynomials) for generating functions. In less favorable cases, we might end up with functions which are only implicitly determined, say as the solution to some equation. Either way, if we now want to decode the generating function $A(z)$ to get actual numbers $A_1, A_2, \ldots A_n, \ldots$, we have to somehow extract the coefficients of the power series. This is the subject of Part B, and where the "analytical" part of the title comes in. We turn to considering the function $A(z)$ as a function on the complex plane. Specifically, it's a function which is analytic in some part of the plane, with a limited number of singularities. Those singularities turn out to be crucial: "the location of a function's singularities dictates the exponential growth of its coefficients; the nature of a functions singularities determine the subexponential factor" (p. 227, omitting symbols). Accordingly, part II is a crash course in complex analysis for combinatorists, the upshot of which is to relate the coefficients in power series to certain integrals around the origin. One can then begin to approximate those integrals, especially for large $n$. Chapter V carries this out for rational and "meromorphic" functions, ch. VI for some less well-behaved ones, with applications in ch. VII. Chapter VIII covers a somewhat different way of approximating the relevant integrals, namely the saddle-point method, a.k.a. Laplace approximation applied to contour integrals in the complex plane.

Part C, consisting of Chapter IX, goes back to multivariate generating functions. I said that counting the number of objects with size $n$ and parameter $k$ gives us, at each fixed $n$, a probability distribution over $k$. This chapter considers the convergence of these probability distributions as $n \rightarrow \infty$, perhaps after suitable massaging / normalization. (It accordingly includes a crash course in convergence-in-distribution for combinatorists.) A key technique here is to write the multivariate generating function as a small perturbation of a univariate generating function, so that the asymptotics from Part B apply.

There are about 100 pages of appendices, to fill gaps in the reader's mathematical background. As is usual with such things, it helps to have at least forgotten the material.

This is obviously only for mathematically mature readers. I have spent a year making my way through it, as time allowed, with pencil and paper at hand. But I found it worthwhile, even enjoyable, to carve out that time. §

(The thing which led me to this, initially, was trying to come up with an answer to "what on Earth is the cumulative generating function doing?" If we're dealing with labeled structures, then the appropriate generating function is what the authors call the "exponential generating function", $A(z) = \sum_{n=0}^{\infty}{A_n z^n / n!}$. If $A$'s are built as sets of $B$'s, then $A(z) = \exp(B(z))$. Turned around, then, $B(z) = \log{A(z)}$ when $A$'s are composed as sets of $B$'s. So if the moments of a random variable could be treated as counting objects of a certain size, so $A_n = \mathbb{E}\left[ X^n \right]$ is somehow the number of objects of size $n$, and we can interpret these objects as sets, the cumulant generating function would be counting the number of set-constituents of various sizes. I do not regard this as a very satisfying answer, so I am going to have to learn even more math.)

Arthur L. Stinchcombe, Information and Organizations [Open access]

A series of essays on organizations --- mostly for-profit corporations, but also universities --- as information-processing systems. The main thesis is that organizations "[grow] toward sources of news, news about the uncertainties that most affect their outcomes" (pp. 5--6), and then react to that news on an appropriate (generally, quick) time-scale. This is a functionalist idea, but Stinchcombe is careful to try to make it work, making arguments about how an organization's need to perform these functions comes to be felt by actual people in the organization, people who are in positions to do something about it. (Usually, his arguments on this score are persuasive.) This is by far the best thing I've seen in sociology about social structures as information-processing systems; I'm a bit disappointed in myself that I didn't read it a long time ago. §

Zach Weinersmith and Boulet, Bea Wolf

The first part of Beowulf, through the defeat of Grendel, adapted into a comic-book about joyously ill-behaved kids in an American suburb. Rather incredibly, it works.

(Thanks to Jan Johnson for the book.)

Books to Read While the Algae Grow in Your Fur; Mathematics; Automata and Calculating Machines; Enigmas of Chance; Commit a Social Science; The Dismal Science; The Collective Use and Evolution of Concepts; The Commonwealth of Letters