Quomodocumque

New paper up on the arXiv! With Nicolas Libedinsky, David Plaza, José Simental, Geordie Williamson, and (unofficially) Adam Zsolt Wagner. A bunch of algebraic combinatorists! And this is a combinatorics paper. It came about this way: I went to visit the ICERM semester on categorification and computation in algebraic combinatorics, with the idea of talking to people about problems where machine-aided example-making might produce some interesting results. I had a lot of conversations and we tried a lot of things and a lot of things didn’t work, but one thing did work, and this is it!

What the problem is about, briefly. The d-invariant of a pair of permutations in S_n is a coefficient of a Kazhdan-Lusztig polynomial, and you don’t need to know anything about what that is in order to read the rest of this post; just that it’s an integer which can be computed by a reasonably simple recursion, but this recursion doesn’t tell you much about how big it can be. In particular, people were wondering: what is the maximum value of d(x,y) for x,y in S_n? It’s very easy to get n-1; a clever construction by some of my co-authors got that up to 2n + a constant. Could one do better? This did seem a promising problem for machine learning: a problem where the search space (n! squared) is much too large to search exhaustively, the “score” you’re trying to maximize can be computed swiftly and reliably, and perhaps most important, we really had no well-grounded ideas about where to search for good examples. Beating human performance is way easier when humans haven’t done much performing!

We give a pretty thorough narrative account of our experimental iteration in section 4 of the paper, so let me cut to the denouement and say: we had very good luck with AlphaEvolve, an evolutionary coding agent made by Google DeepMind. AlphaEvolve is the successor to Funsearch, which I have used once or twice. (Hey! I forgot to blog about that last paper! Well, I guess at least I did blog about a talk I gave that drew a lot from it.) Anyway: AlphaEvolve, like Funsearch, uses genetic algorithms with LLMs (now some flavor of Gemini) as the mutation/reproduction mechanism. But it has gotten a lot easier to use and more flexible, and I’m optimistic that as with FunSearch it will be avaiable for general use soon. And open-source imitations are already available.

What it produced, in an overnight run, is a program that, given n, outputs a pair of permutations in S_n. For each n from 10 to 50 (which are the values we tested on) these looked to have d-invariant substantially bigger than the biggest we already knew about. But it was much better than that. Close examination of the permutations showed that they had a natural 2-adic structure, especially for n a power of 2. Namely: if n = 2^m and you think of S_n as the permutations of the length m strings of bits instead of the integers 1 through n, then the two permutations x_m and y_m that the program produced were “reverse the digits” and “reverse the digits and then apply NOT to each digit, swapping 0 and 1.” In particular, both x_m and y_m are involutions. (Note that the program didn’t SAY it was reversing the digits. The program was pretty long and you have to ignore large chunks of code that don’t do anything and figure out how to express what the point of the program is in meaningful terms. Geordie calls this process “decompiling,” which I like a lot.)

It gets better still! The permutations in S_n come with a partial ordering called the Bruhat order, and the d-invariant of x and y is a property of the Bruhat interval [x,y], which is just the set of all those permutations z such that x <= z <= y. If I give you two random permutations, the Bruhat interval between them can be pretty hard to describe. But in the case of these two special involutions x_m and y_m in S_{2^m}, no! The permutations in the interval are exactly cut out by a nice combinatorial criterion. Namely: there are m+1 ways to break the 2^m x 2^m box into 2^m equal rectangles of area 2^m, and we say a permutation is dyadically well-distributed if its permutation matrix has exactly one 1 in each of these (m+1)2^m boxes. Look, here’s a picture of two dwd permutations in S_16, one in red and one in blue:

(And now you see the origin of the Dyadiku game from last week: a Dyadiku is just a list of 2^m dwd permutations, no two of whose permutation matrices have a 1 in common!) (I also see that there’s a typo in the paper, we have two “bocks” and a “blocks!” Despite the traditional error-correcting code of best-2-out-of-3, “blocks” is what we actually meant.)

These permutations are actually not completely novel objects; the permutation matrices, as subsets of the plane, are what people in the field of low-discrepancy sequences call (0,m,2)-nets. But I don’t think any connection with algebraic combinatorics was anticipated! (And no, I don’t think AlphaEvolve was drawing information about (0,m,2)-nets from published literature; at least, nothing in the logs indicates this. But even if it were, that would be a slick move!)

Here’s another way I like to think of the dwd condition. Suppose I put a bunch of points (x,y) in Z_2^2 which obey the law that, for any two distinct points (x_1, x_2), (y_1, y_2) we have

|x_1 – x_2| |y_1 – y_2| > 1/2^m.

I think of this as a kind of “sphere-packing problem” even though this particular function on pairs of points isn’t a distance. Anyway, you can get at most 2^m points packed in this way and the maximal configurations, projected to(Z/2^mZ)^2, are exactly the dwd permutation matrices.

It’s not too hard to compute that there are exactly 2^(m 2^(m-1)) dwd permutations of 2^m letters. That’s kind of a lot, considering that log_2 |S_{2^m}| is already only around m 2^m. We also note that the special permutations x_m and y_m are both dwd (that’s them in the picture)!

Theorem: The Bruhat interval [x_m, y_m] consists exactly of the dwd permutations.

I don’t know any other non-trivial Bruhat interval that has a nice combinatorial description like this! And what’s more, the Bruhat order within this interval is easy to describe:

Theorem: [x_m, y_m] is isomorphic as a poset to a hypercube of dimension m 2^{m-1}.

(The hypercube poset of dimension N is just length-N bit strings where a < b if a_i < b_i for all i. In the paper you can find a nice, explicit, pretty canonical identification of [x_m, y_m] with bit strings.)

My sense is that a hypercube this big in S_n is a wholly unexpected structure, and it is relevant to lots of popular questions about cluster varieties, etc.

This is certainly my favorite outcome from the machine learning experiments I’ve been involved with. It’s one thing to incrementally improve a lower bound for a combinatorial problem, quite another to encounter a mathematical object that I authentically consider worth thinking about. In Shape, back in 2020, I wrote: “Some people imagine a world where computers give us all the answers. I dream bigger. I want them to ask good questions.” There’s is a medium-sized dream I didn’t mention there; that machines will bring to our attention objects worth asking questions about!

I said it at the top of the post, and I’ll say it again, to be clear: Machine learning experiments don’t usually work this well. What you hear about from me and others are the outlyingly successful trials, which makes sense — my goal is not to perform a dispassionate audit of an evolutionary coding agent, it’s to make interesting math and tell you about it. But I do want to avoid giving the impression that it’s magic. On the contrary, it feels less like magic the more you work with it.

(Other accounts of this paper: Slides from a talk by Geordie. Article on ICERM newsletter by Nicolas.)