• Machines for Math


    I came across this article today while looking for information on how Jensen and Williamson implemented an algorithm for computing the $p$-canonical basis. Not recognizing any of the co-authors I assumed it was a group of students until coming across this paragraph.

    In this work we prove a new formula Kazhdan-Lusztig polynomials for symmetric groups. Our formula was discovered whilst trying to understand certain machine learning models trained to predict Kazhdan-Lusztig polynomials from Bruhat graphs. The new formula suggests an approach to the combinatorial invariance conjecture for symmetric groups.

    Turns out the co-authors are Google I mean DeepMind people. This seemed kind of wild to me — to throw machine learning at something like computing KL polynomials, and I guess it is sort of radical. At least enough that they published another paper in Nature describing this and other efforts at using machine learning to formulate or solve conjectures. And U. Sydney is going on a PR push about it.

    Reading the Nature article, it is clear that this isn’t really the doomsday scenario we worry about where machines can prove all the theorems and we mortals are useless to them. It sounds like there’s still a high degree of specialized knowledge and intuition that goes into training the supervised learning model. At least that’s my sense from this paragraph:

    We took the conjecture as our initial hypothesis, and found that a supervised learning model was able to predict the KL polynomial from the Bruhat interval with reasonably high accuracy. By experimenting on the way in which we input the Bruhat interval to the network, it became apparent that some choices of graphs and features were particularly conducive to accurate predictions. In particular, we found that a subgraph inspired by prior work may be sufficient to calculate the KL polynomial, and this was supported by a much more accurate estimated function.

    I know not much about machine learning, and the second sentence doesn’t give a clear sense of how the “experimenting on” inputting went, but I would be surprised if the machine was able to actually pull out hypercube decompositions and diamond completeness as the features it needed to really predict the KL polynomials. That is, it sounds like ML could be a useful interactive tool for discovering and verifying ideas, like interactive theorem proving seeks to be, but they’re still not doing the math for us. Not to mention the proof of the main formula of the paper involves some layers of categorification and pretty heavy geometry.

    Still, all in all, it looks like we’re gonna all have to learn how machines learn sooner or later.

  • Also this

    My poor imagination can only think of making a long camel trip across the desert and getting close to a destination, but you can really feel the bobbing in these songs. This version appears to be recorded from a cassette which somehow makes it sound even better. Maybe its an old jeep trip instead.

  • Study Music

    I often listen to music while doing math. I’ve never been one to pay strict attention to lyrics, so it doesn’t usually matter too much whether the music is instrumental or not. I remember listening to a lot of Kanye West while studying for quals for instance, which seems kind of weird in retrospect but I guess it worked out. Usually I get stuck in music ruts, which is kind of fine for doing work to because you don’t necessarily want to be challenged by unfamiliar music while you’re busy doing heavy mental lifting.

    Gnawa music has origins in Sufi mysticism, and is apparently supposed to be for exorcising jinns, possessive spirits. It later caught on with some American jazz musicians and is now identified with Morocco as sort of a “national music” (though there is more socio-political subtext to that story than I realized). In any case, it is great math music because it has good impulse but is also kind of drone-y so it keeps you sort of cruising along in the zone. I think this album from Mahmoud Guinia was my first exposure, and one I still come back to regularly.

    Whenever I’m really stuck but I want some study music, Zuckerzeit from early German electronic duo Cluster is another album I go for regularly. The title means “sugar time,” which, coincidentally, is often math time as well. Bring on the cookies.
  • Knuth on P v NP, god(s)

    I don’t remember exactly how I got there, but reading through a short profile on Don Knuth I was glad to learn that my worldview roughly coincides.

    Taking the interview for this article as a mini-instance of “All Questions Answered,” this reporter asked about the question of P versus NP. “It’s probably true that P equals NP, but we will never know why,” Knuth answered. The question has two aspects, he explained. The first: Given a computational problem, does there exist a polynomial-time algorithm for its solution? And the second: Is that algorithm knowable—that is, can we actually write it down? “What I suspect is that there is some algorithm, it’s out there, but it’s so complicated that for practical purposes, it makes no difference because nobody will ever know what it is,” he said. A suggestive example comes from the Robertson-Seymour theorem, which says that for any minor-closed family of graphs, there exists a polynomial-time algorithm to recognize whether a given graph belongs to the family. But “almost never do we know what the algorithm is.”

    But just because something is hard doesn’t mean we should give up!

    Also worth noting that this appears in the middle of a piece which characterizes the early 21st century mainstream North American academic position on diversity pretty well. Knuth is being praised for his contributions to diversity for giving money that allowed MathSciNet to add authors’ names typeset in their native languages instead of just transliterating to English. I am for this, but the tenor hews a little too close to the willful ignorance of claiming mathematics is a diverse and inclusive field because it is international. How eager we were to “celebrate diversity.” Oops!

    Also, if your read further, it talks about Knuth’s lectures on religion and coming out as a Christian. I think all I can say about that is that I appreciate the acknowledgement that “God” is really a just a catch-all for mystery. It makes more sense to me as a metaphor though.

  • describe your research iii

    So how much more complicated can this game get? What motivation do we have to study other homogeneous spaces of higher dimensions? How is combinatorics involved?

    I think the first and second questions need to be answered together, as there is constant tension between the impulse to add additional complexity to mathematical structure and the need to explain to other people why they should care. Mathematicians have for the most part chosen a sort of middle path which is to build the tools that would enable the study of arbitrarily complicated spaces by classifying the components of which they can be built. Then, whenever motivation to study a particular case of these things comes along from physics, economics, computing, or other parts of mathematics (most often), the motivated researcher has some footing to make progress by putting together the pieces.

    You could think of it sort of like being a plumber going to the hardware store looking for the right fittings for some pipes. Maybe you’re a physicist and you’re trying to study a system of particles that obey certain symmetries. So what do you do? You go to the group store of course, and see if they have the right group. Sometimes they don’t have the perfect one, but they have the right parts and documentation so that you can assemble the right one yourself without too much difficulty. Now that you have a sensible way to keep track of symmetries in your system, you can go back to worrying about predicting how the universe behaves.

    It is on the one hand wonderfully remarkable that the business of classifying the simple pieces of which geometric spaces can be built is a tractable pursuit at all. On the other hand, it is a mathematicians job to make it tractable. If some definition of what constitutes a “simple piece” leads to an impossible classification, then it is not the right definition. While some people might have you believe that theorems like the classification of finite simple groups or semi-simple Lie algebras are miracles from gods, they have also come through people toying with and massaging definitions until the classification task began to seem sensible (though still possibly monumental).

    I don’t mean to demean the examples above; I too am enamored of them, and most of my published research uses the classification of simple Lie algebras as sort of a starting point. But I think of integer factorization as the proto-problem for these deconstructive classification quests. The fact that natural numbers all break down into prime factors (they are “classified” by their prime divisors) really does seem like a miraculous piece of order in the universe, or at least an inescapable part of how human consciousness interprets it. That we don’t have a very efficient way to take a number and break it down into factors is astonishing given how fundamental this problem is.

    There is a dilemma tied to the practicalites of trying to have a career. We are incentivized to mathematician not to work on old, very difficult problems, but rather to invent new theories (or more likely work on the pet theories of the prior generation), asking questions possibly nobody else is asking and solving problems that aren’t necessarily super difficult — just no one’s been around to bother with them yet. This is a cynical view of what could also be romanticized as a tremendous freedom and creativity afforded to the profession by the fact that we’ve managed to convince the rest of the scientific and engineering fields that they need us to teach them calculus, statistics, and the like. (See: Mackey’s lecture on what it is to be a mathematician.) But there are also cases where solutions to old, difficult problems have eventually come through extended scenic detours.

    Moreover, I don’t want to diminish the amount of work that has gone in to building up the vast amount of theory that exists today. It is not that it comes so easily, but rather that it comes at all that appeals to the hungry mathematician. It can be a joyous experience to sit down with a problem, toy with it for hours, weeks or months, and then to finally resolve it. And it is sort of incredible that human intellect is suited to the process of assimilating abstract information, experimenting, ordering it, and manipulating it in a way that reveals a underlying structure. The pleasure that comes with this experience is, I guess, probably the main force behind the proliferation of mathematical theory. It is a good thing that we will never run out of problems.

    But now I haven’t said anything about combinatorics.