49
$\begingroup$

I am a research mathematician at a university in the United States. My training is in pure mathematics (geometry). However, for the past couple of months, I have been supervising some computer science undergrads in trying to reproduce DeepMind's research breakthroughs, namely FunSearch and AlphaGeometry.

The students, after making many changes to the code, have succeeded in reproducing both results. I am extremely proud of them, and also want to use this amazing opportunity to perhaps work on some other problems in mathematics.

FunSearch, as I understand it, is useful in constructing mathematical examples that are difficult for human mathematicians to construct. For example, it was able to construct larger cap sets than humans have ever been able to construct before. AlphaGeometry, on the other hand, was built to be able to solve geometry problems in the International Math Olympiad (something that I was quite bad at in my short-lived Olympiad days). My belief (hope?) is that it can also be re-directed to solve actual research level math problems.

I'm looking to compile a list of problems that can perhaps be studied using the techniques in FunSearch and AlphaGeometry. Some fields that would perhaps be most relevant are geometry, combinatorics, mathematical physics, analysis, etc.

I have been made aware that there are other questions on MathOverflow that address the applicability of machine learning to research questions in mathematics (see for example: What are possible applications of deep learning to research mathematics?, Open problems which might benefit from computational experiments, and How can Machine Learning help “see” in higher dimensions? as well as the closed question Mathematical questions or areas amenable to AI). However, note that my question is much narrower, and only specific to the FunSearch and AlphaGeometry algorithms. I am happy to summarize these techniques here if there is interest (although a quick look at the linked articles should do a much better job).

$\endgroup$
12
  • 3
    $\begingroup$ @RyanHendricks As part of your post, can you give more details on what types of problems Funsearch and Alpha Geometry can tackle? A rough description. In what sense is "learning" involved? $\endgroup$ Feb 11 at 21:53
  • 14
    $\begingroup$ for AlphaGeometry: here is an informative argument that it does not go much beyond setting up and solving a linear system of equations for angles. $\endgroup$ Feb 11 at 21:58
  • 3
    $\begingroup$ @RyanHendricks You say that your question is "much narrower" but really, there's no limit to the type of problem that this kind of methodology could be applied to. Pretty much any area of experimental mathematics where you can generate a large enough corpus for training is fair game. $\endgroup$ Feb 11 at 22:13
  • 9
    $\begingroup$ I agree with Timothy Chow that your insistence this question is substantially different from the prior ones is unconvincing, and more generally I don’t want to encourage another question like this to be posted every time some newly hyped AI tool emerges. $\endgroup$ Feb 11 at 22:20
  • 6
    $\begingroup$ @RyanHendricks I’d be happy to suggest some packing and coding theory problems that could be worth trying. To be honest, I see no reason to think Funsearch should work particularly well for them, but I don’t for the cap set problem either, so it would be foolish to be constrained by my lack of intuition here. You/they can send me email (cohn at mit.edu) if interested. Sorry for the comment answer: it’s awkward to post an undergraduate research suggestion publicly, since it’s not nice to knowingly compete with them but also not nice to try to publicly reserve a problem for someone. $\endgroup$
    – Henry Cohn
    Feb 11 at 22:38

1 Answer 1

54
$\begingroup$

This is a bit speculative, and perhaps too challenging for an undergraduate project, but I wonder if an AlphaGeometry type approach might be possible for the task of automatically upper bounding sums or integrals of nonnegative quantities up to constants, a topic which I discuss in this blog post. A typical such question is the one from this previous MathOverflow question: establish the bound $$ \sum_{d=0}^\infty \frac{2d+1}{2h^2 (1 + \frac{d(d+1)}{h^2}) (1 + \frac{d(d+1)}{h^2m^2})^2} \ll 1 + \log(m^2)$$ for all $h, m \geq 1$. I guess to focus the situation one could pose the more specific problem class of establishing estimates of the form $$ \sum_d F(d,m) \ll G(m)$$ for $d, m$ in various standard parameter ranges such as ${\bf Z}^n$ or ${\bf R}^n$ intersected with a polytope, and $F$ and $G$ being various nonnegative "elementary" functions that involve only rational functions, logarithms, and perhaps exponentials. (Actually, one might first want to understand the simpler problem of automatically proving estimates of the form $F(m) \ll G(m)$ first (given some reasonable constraints on the input parameters $m$, such as linear constraints), before dealing with any summations or integrations.) Generally speaking, such estimates are easier to prove than the sharp inequalities one sometimes sees for instance in Olympiad or Putnam problems, where a lot more cleverness is often needed; the freedom to lose constants in bounds allows for solutions that only use a relatively small number of simple techniques.

Somewhat analogous to how AlphaGeometry proceeds by "routine" manipulations of relations between angles and sides, together with a few "inspired" constructions, one could imagine trying to solve these sorts of problems using "obvious" upper bound techniques coupled with a few "inspired" decompositions (or changes of variable, in the case of estimating an integral, or working with multiple sums), or introducing some key quantities that appear repeatedly in the estimate (cf. my previous answer to a MO question). However, the solution methods here seem a bit more varied than they do in the geometry case, and I do not know of any large data set of such estimation problems to train on (though perhaps there are ways to generate large synthetic data sets, as was done in AlphaGeometry), so there are some challenges to getting started here. Still, this looks like a task which is close to already being feasible by existing (non-AI) algorithms (though I am not so familiar with the literature on automated estimate proving), and might only need a small amount of additional AI to obtain reasonable performance.

EDIT: Here is a very toy example of what I have in mind. Suppose one wanted to automatically prove (a weak version of) the arithmetic mean-geometric mean inequality $$ (abc)^{1/3} \ll a+b+c$$ for non-negative $a,b,c$. If one is inspired to split into 3! cases such as $a \leq b \leq c$, then the problem can then be handled by automated methods, since for $a \leq b \leq c$ we see that $a+b+c$ is comparable to $c$, and the implication $$ a \leq b \leq c \implies (abc)^{1/3} \ll c$$ is a linear programming problem (after taking logarithms) that can be handled by standard mathematical packages (and indeed once one has reduced to this situation, one no longer loses a constant). The only "clever" step was to do the splitting, though even in this case one could automate this step by noting that $a+b$ is comparable to $a$ when $a \geq b$ and to $b$ when $a \leq b$, and so one could tell the computer to automatically split all such sums it encounters in such a fashion. Probably all such problems are in principle decidable (it's basically the elementary theory of tropical algebra, which is "just" linear programming), but when many variables are involved, it may become computationally expensive to brute-force all the cases and some clever AI-assisted selection of case splitting may become superior (for instance in the above example, one only needs to split into three cases such as $a,b \leq c$ rather than 3! cases; this is a negligible distinction for three variables, but becomes significant for large numbers of variables). Similarly for the more complex problems proposed above where one is also performing some summation or integration over a range.

EDIT 2: A second example of an estimate that can be proven automatically after one inspired case decomposition is the weak Fenchel-Young inequality $$ ab \ll a \log a + e^b $$ when $a,b$ are real with $a \geq 1$ and $b \geq 0$. Of course one can prove this bound (with sharp constants) using calculus or convexity methods, but let us try to prove it "automatically" by even more elementary techniques. Once one has the "inspiration" to split into the cases $b \leq 2 \log a$ and $b \geq 2 \log a$, the estimate follows automatically from linear programming (after taking logarithms) using the following "obvious" inequalities as input: $$ a \log a \ll a \log a + e^b$$ $$ e^b \ll a \log a + e^b$$ $$ b \leq 2 \log a \implies b \ll \log a$$ $$ b \geq 2 \log a \implies e^{b/2} \gg a$$ $$ b \ll e^{b/2}$$ So the only step that could potentially benefit from AI assistance here is locating the initial case splitting (and maybe the idea to split $e^b$ as $e^{b/2} \times e^{b/2}$).

EDIT 3: Here is how I would imagine a semi-automated approach to prove the stated inequality at the top of this post would proceed. The first "inspired" step is to split into the regimes $d \leq h$, $h \leq d \leq hm$, and $d \geq hm$. In the regime $d \leq h$, come up with the bound $$ \frac{2d+1}{2h^2 (1 + \frac{d(d+1)}{h^2}) (1 + \frac{d(d+1)}{h^2m^2})^2} \ll \frac{d+1}{h^2}$$ and prove it by automated methods. In the regime $h \leq d \leq hm$, similarly come up with the bound $$ \frac{2d+1}{2h^2 (1 + \frac{d(d+1)}{h^2}) (1 + \frac{d(d+1)}{h^2m^2})^2} \ll \frac{1}{d}$$ and prove that by automated methods. In the regime $d \geq hm$, come up with the bound $$ \frac{2d+1}{2h^2 (1 + \frac{d(d+1)}{h^2}) (1 + \frac{d(d+1)}{h^2m^2})^2} \ll \frac{h^4 m^4}{d^5}$$ and prove that by automated methods. Finally, evaluate these simpler sums using some standard library of summation bounds and conclude using further automated estimate-proving tools. Here I imagine the role of AI would be to discover the right splitting, as well as the right expressions to upper bound the summand by in each regime. In this particular case one could perhaps code in some non-AI automated method to achieve these tasks, but for more complex inequalities one may need a machine learning-powered algorithm to find the right splittings and bounds.

$\endgroup$
6
  • $\begingroup$ Thank you Terry for the great suggestion and explanation! We look forward to trying to solve this problem using alpha geometry. $\endgroup$ Feb 12 at 12:55
  • 2
    $\begingroup$ The splitting method (breaking the space into polytopes, then checking the inequality on each of them) is very strong for algebraic inequalities in a fixed number of variables. (Often, on each polytope, you get an inequality that holds tautologically, as all coefficients of the polynomial are nonnegative.) You don't need AI to apply it. $\endgroup$ Feb 12 at 16:11
  • 2
    $\begingroup$ Right; I view the case of estimates of algebraic expressions in a fixed number of variables as a sort of "base case" to start with, and then one can gradually increase the difficulty (for instance by permitting exponentials and logarithms, or introducing summations or integrals) to find some intermediate cases where much of the work can be done by automated tools without AI, and only a small amount of AI assistance is needed to provide a handful of key steps. My understanding is that this is broadly the setting in which AlphaGeometry was successful. $\endgroup$
    – Terry Tao
    Feb 12 at 17:38
  • 5
    $\begingroup$ In any event, even if this undergraduate project develops a tool to automatically verify large classes of estimates that ends up using 0% AI methods (or has the AI essentially relegated to the role of a natural language front-end interface for the tool), this is still a useful tool that I for one would be happy to use, and I believe many other mathematicians in the general area of analysis would be interested in also. $\endgroup$
    – Terry Tao
    Feb 12 at 17:43
  • $\begingroup$ @TerryTao I thought that you and the upvoters might have been more interested in more mathematical machine learning algorithms rather than the hyped FunSearch and language models. Our current language models lack the mathematical interpretability that we need for AI safety. I would rather use an AI algorithm that generalizes well to the complex numbers and quaternions. If we train the AI model twice using different initializations, I would like to get the same thing. I would like to be able to perfectly recover the training data from the trained network. $\endgroup$ May 13 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.