November 27, 2021

The End Goal of Math is Efficient Computation

[Nb. this is a very rough draft but I’m sad I’m not writing much these days so I want to get the juices flowing again.]

Mathematicians (especially pop-math book authors) like to wax poetic about math as unveiling the secrets of the universe, or as the furthering of human knowledge. But many mathematicians also denigrate the algorithmic questions in their fields, even if in private they rely on them. The mathematician Irving Kaplansky once said,

[Halmos and I] share a philosophy about linear algebra: we think basis-free, we write basis-free, but when the chips are down we close the office door and compute with matrices like fury.

My view much stronger than the average mathematician, who might say that “knowledge” is the end goal, while efficient algorithms are a nice byproduct. I would say that knowledge is equivalent to efficient algorithms. I don’t mean this in a Curry-Howard sense, that all proofs are programs and vice versa. I mean that mathematical knowledge is defined by its computation-granting abilities. Knowledge exists if and only if you can compute answers to questions exhaustively in the domain of that knowledge.

---

The classification of finite simple groups is a crown jewel of 20th century algebra. It states that every finite simple¹ group is isomorphic to one group in a small number of families, where each family has a known structure or easily-understood parameters and structure. The families are the cyclic groups of prime order Z/pZ, alternating groups A_n where n >= 5 (because for n < 4 only A_3 is simple, and it is isomorphic to Z/3Z), groups of Lie type, and a list of 27 exceptional cases called sporadic groups.

Classification theorems like this are heralded as the most important outcomes of a subfield of mathematical study. They are also considered the “end” of a field of inquiry. Once a sufficiently nice classification theorem has been proved, basically all major open questions are resolved by using the classification. Thurston’s geometrization theorem is an example for Riemannian geometry, and some often taught to undergrads include the classification of discontinuities and the classification of Euclidean plane isometries. There are many others that are not popular enough to warrant a Wikiepdia page.

Classifications are important and “final” because they represent a “complete understanding” of a mathematical theory. More specifically, classification theorems provide an algorithmic solution to the following concrete problem. Given two objects of study (e.g., two finite simple groups) and an agreed definition of what it means for two objects to be the same or different (e.g., is there an isomorphism between the two groups) decide if the two objects the same, or different. So given two finite simple groups presented in some way—for example, by providing a multiplication table—can you determine if the two groups are the same or different?

However, something is missing. Because as every software job applicant knows, you can solve any problem in a dumb way by trying all possibilities. You can try every permutation of the rows of one multiplication table and check if it’s equal to the other table. This does not satisfy mathematicians because it doesn’t produce any understanding. To understand a topic, you must be able to solve the distinguishing problem efficiently the facts used to do that are the knowledge.

On the other hand, an efficient algorithm for distinguishing finite simple groups would be to determine a criteria for a group to be in each of the families, run each test separately to choose the right family, and then use a family-specific algorithm to determine which member of the family is isomorphic to your group. Do this for both groups and output “yes” if the answers agree. For example, to determine if a group is cyclic of prime order, you can check if the width of the multiplication table is prime. For alternating groups, I was not aware of a method before starting this article, but a cursory Google search shows there is at least one method, and naturally it relies on a theorem about alternating groups. The other classes are more exotic, but I am sure that in principle it can be done.

Beyond solving the decision problem, a good classification theorem also constructs a “canonical form” for an object, and proves that the canonical form is unique. The canonical form often organizes the data of the mathematical object in such a way that you can answer almost any question you want efficiently or even trivially once you have the canonical form. For example, in linear algebra the Jordan canonical form classifies operators on a finite-dimensional vector space, though it is not as useful as it could be due to numerical instability.²

---

There is a caveat to this discussion related to AI systems that pattern match mathematical rules from examples. Symbolic integration is a fun one, which I’d like to reproduce some day. Luckily, so far they still fail on simple (but extreme) examples outside of their training domain that would not faze a typical mathematician. Moreover, integration does not have a nice classification theorem (because of Liouville’s theorem) in the sense that not every elementary function has an elementary antiderivative.

It could be said that no human yet has a “full understanding” of integration, or that Liouville’s theorem shows the impossibility of solving this problem completely. And so to add to “can you compute” you must allow a response, “impossible given the constraints.”

In the same vein, it is a hard question to say, “Can one truly understand ZF set theory” if consistency is impossible to determine. But even then, determining what questions are independent of ZF set theory is itself an algorithmic problem, and our furthering of knowledge in logic provides the ability to efficiently answer whether a question can be answered.

---

Mathematicians may not agree with me that knowledge is equivalent to computation, even perhaps with a bit of squinting. It’s a shame, however, that many neglect computation. Computation is, and always has been, a rich source of mathematical insights. Rather than embrace the challenge (and reap the citations!), shifting the burden of computation to practitioners slows everything down. Outsiders (like programmers) have to toil to learn and appreciate the theory, and often enough, at the end of the current theoretical road, there is no clear resolution or application. Enough bad experiences along these lines, and those who could make new discoveries and contributions get sick of the churn and spend their precious free time on something else.

Math has a particularly bad reputation in this regard, and it’s primarily a social problem. Once a field that doesn’t have strong computational roots becomes computational (see, topology becoming algebraic topology), you get mathematicians calling algebra the “devil” and complaining that a subject is no longer beautiful. This isn’t the best example, because algebraic topology is a popular field still today, but some mathematicians really did consider abstract algebra a corrupting influence. Perhaps a better example is Euclidean geometry. Research mathematics considers Euclidean geometry largely solved, but practitioners are constantly designing new algorithms for geometric problems in 2 and 3 dimensions because of computer graphics and game design. De Casteljau only invented Bezier curves because he worked for a car company, and Bezier himself (who formalized and popularized De Casteljau’s curves) was an engineer for most of his career. But plan geometry was considered divine and mysterious until Decartes demystified it with coordinates and systematic algorithms.

To put it another way, previously “interesting” fields of mathematics are usurped from their status because they are considered complete, largely due to computation to some degree. And then specific use cases (like Bezier curves), usually related to the proliferation of computers and the criticality of efficient algorithms, usher in a new age of insights into the as-yet-not-fully-understood topics. Mathematicians should adore working on these kinds of problems. They’re deep, impactful, and stand to benefit much more from the breadth of knowledge mathematicians possess. But somehow so much of mathematics was so far removed from applications that they missed the opportunity. Or those who took the opportunity were reclassified as computer scientists or left academia. Meanwhile, when practitioners approach mathematicians today—this happened to multiple people I spoke with who will remain anonymous—the mathematicians view the problems as trivial and unworthy of investigation, especially if they are considered “solved” but not yet efficient enough for practice.

Fashion appears to be main barrier. And it seems that by changing the fashion—recent advances in machine learning have done a lot in this front—more mathematicians are starting to take computation seriously. I think further experience with writing computer programs could help, as the need for a deep mathematical theory or a new structure theorem becomes painfully clear when you have to wait days or weeks for your computer program to finish.