Sharing AI progress on mathematics (amazing); and my lecture plans

With Danny and Sharon Kleitman and Michel Goemans at the MIT Endicott house.

Update: There are many reactions and emerging details on the new 700 or so papers released by Open AI. On Persiflage there is a very interesting post with analysis of eight results related to number theory and an earlier post with a list of expectations from AI.  On SO ten results in computer science and computability are described.

Sharing AI progress on mathematics (OpenAI) #

A few hours ago, Open AI shared solution to a few hundred mathematical problems. Certainly this is an amazing milestone for mathematics, and the results will needs to be verified and digested by human mathematicians in the months to come. Several of the problems were discussed here on the blog over the past two decades and I will try to give a more detailed update regarding these problems and other “Math for AI” achievements.  This is an amazing development!

At the end of the post I described early blog posts with some background on 26 of the new results. Both the Open AI list and some news from colleagues from the last days are relevant to my lecture around Borsuk’s conjecture on Friday in Jeff-Fest.

My Lecture Tour #

I am currently in the middle of a nostalgic and hectic tour, visiting Brown University, MIT, Yale, IAS, Rutgers (for Jeff Kahn’s conference celebration), and Princeton University. It is a pleasure to meet old friends and (both young and old) mathematicians that I did not meet before. I truly love both mathematics and the community of mathematicians, and I hope my lectures and posts reflect this feeling.

Right now I am writing from Avi and Edna’s home at the IAS, having just returned from a lovely mathematics department event welcoming the new academic year. Tomorrow, I will be speaking here about intersection homology and combinatorics. Later in the evening, I am giving a short lecture in the “discussion series” about my work on quantum computation, which I hope will spark an engaging conversation. It will be quite a challenge to present quantum computation and my two decades of research on the subject in a 20-to-30-minute lecture tailored for a general audience.

I also have a rather intense blogging plans: I am planning three posts based on my lectures: one on algebraic shifting at MIT, one on intersection homology and combinatorics at the IAS, and one on problems around Borsuk’s conjecture at “Jeff Fest.” Here is how I plan to go about it: I will feed an AI tool my abstract and a rough outline of the talk, and let it prepare detailed lecture notes that I can use for the presentation itself. (For the MIT talk, I only thought of this approach after the fact!) Later on, I will edit those lecture notes into blog posts. It is quite interesting—and a little amusing—to note that the AI writes not only about the technical matters but also attempts to capture “my” feelings and hopes.

I also plan a post with a candidate for “the most outrageous conjecture,” alongside an entertaining double-feature “test your intuition” post.

OpenAI’s New Mathematical Results: Connections to Earlier Posts #

As I mentioned above, OpenAI released an impressive collection of mathematical results produced by an internal AI model: 722 manuscripts grouped into 372 families. Many of these concern problems that have appeared on this blog over the years.

Three disclaimers: first, the collection includes results with different stages of verification; their proofs will need to be checked and digested by the mathematical community. Second, even Lean verification may have issues, and third, there were a variety of other AI based results, also related to earlier blog posts that I did not collected; among those let me mention the Irrationality of , the Navier Stoke problem, The Komlos conjecture, Chvatal’s conjecture, and the KLS conjecture.

Here are twenty connections to earlier posts, with related results occasionally grouped together.

1. The Mahler conjectures. I discussed the symmetric Mahler conjecture and its connections to symplectic geometry and myconjectures on faces and flags . The release announces proofs of both thesymmetric andgeneral Mahler conjectures in every dimension, including the equality cases of Hanner polytopes and simplices, respectively.
2. Borsuk’s problem in dimension nine. The question of the smallest dimension admitting a counterexample to Borsuk’s conjecture has appeared here repeatedly, including inthis 2023 update . Thenew manuscript gives a compact set in nine-dimensional Euclidean space that cannot be covered by ten sets of smaller diameter.
3. Hadwiger’s conjecture. InCombinatorics News I discussed Hadwiger’s conjecture, which relates graph coloring to complete minors, while reporting the disproof of its odd-minor strengthening. Thenew announcement gives counterexamples to the original conjecture, even among graphs with independence number at most two.
4. The chromatic number of the plane. In2018 I reported Aubrey de Grey’s breakthrough showing that five colors are necessary to avoid monochromatic pairs at distance one. Thenew manuscript raises the lower bound to six, leaving six and seven as the two possible answers.
5. The Kakeya problem. Mypost on Hong Wang and Joshua Zahl’s breakthrough discussed the three-dimensional Kakeya set conjecture and the stronger maximal-function problem. The release announces themaximal conjecture in three dimensions and theHausdorff-dimension conjecture in four dimensions .
6. Periodic tiling in dimension three. InAn Aperiodic Monotile I also mentioned Greenfeld and Tao’s disproof of the periodic translational tiling conjecture. Thenew construction gives a finite translational tile in that admits no fully periodic tiling, reaching the smallest possible dimension for the lattice problem.
7. Covering density of convex bodies. I described the breakthrough of Ordentlich, Regev, and Weiss on efficient lattice coveringsin this post . OpenAI announces auniversal lattice-covering bound andmatching examples even for unrestricted translative coverings , determining the worst-case order over convex bodies.
8. Distinct distances and unit distances. These problems featured inJános Pach’s guest post on Guth and Katz and inmy earlier extremal-combinatorics post . The release includes thesharp-order bound for distinct distances in every fixed dimension and animproved planar unit-distance bound for some absolute .
9. Erdős’s arithmetic-progression conjecture. Mypost on Bloom and Sisask’s breakthrough discussed the three-term case of the assertion that divergent reciprocal sums force arithmetic progressions. Thenew result covers every finite length: any set of positive integers with divergent reciprocal sum contains arbitrarily long arithmetic progressions, with quasipolynomial quantitative bounds in Szemerédi’s theorem.
10. Sidorenko’s conjecture. I describedSidorenko’s conjecture , which predicts that a fixed bipartite graph has at least the density it would have in a random graph of the same edge density. Theannounced counterexample has 35 vertices and 66 edges and also disproves the related forcing conjecture.
11. Ryser’s covering conjecture. I discussedRyser’s conjecture in my birthday post for Ron Aharoni, including his proof of the tripartite case. Thenew counterexamples are intersecting -partite, -uniform hypergraphs requiring vertices to meet every edge, whereas the conjecture predicts .
12. Crossing numbers of complete and complete bipartite graphs. These problems appearedin my discussion of Turán’s mathematics . The release reports proofs of theHarary–Hill andZarankiewicz formulas, determining the minimum number of crossings in plane drawings of complete and complete bipartite graphs.
13. Barnette’s Hamiltonian-cycle conjecture. InColoring Simple Polytopes and Triangulations I discussed Barnette’s conjecture that every cubic, bipartite, 3-connected planar graph has a Hamiltonian cycle. Thenew manuscript announces a proof of this conjecture.
14. Combinatorial invariance of Kazhdan–Lusztig polynomials. This was Problem 11 in my discussions of the G-programme, and I returned to it ina 2021 post about DeepMind’s mathematical work . Theannounced theorem says that isomorphic Bruhat intervals have the same equal-parameter Kazhdan–Lusztig polynomial, even when the intervals come from different Coxeter systems.
15. Ramanujan graphs and higher-dimensional expanders. The subject ofNew Ramanujan Graphs! returns with adeterministic polynomial-time construction of nonbipartite Ramanujan graphs, for every fixed degree at least three and every sufficiently large even number of vertices. In higher dimensions, the release announcesbounded-vertex-degree coboundary expanders over in every dimension at least three, continuing the theme ofmy introductory posts .
16. The second Kahn–Kalai conjecture and Talagrand’s conjectures. The release reports proofs of thesecond Kahn–Kalai conjecture , which bounds graph-containment thresholds using subgraph expectations, and ofTalagrand’s discrete convexity conjecture , both discussed inmy account of Jinyoung Park’s ICM lecture . A companion result makesintegral and fractional expectation thresholds equivalent up to a universal constant .
17. The Friedgut–Kalai sharp-threshold conjecture. Sharp thresholds and the role of symmetry were central themes ofBoolean Functions: Influence, Threshold, and Noise . The release announces the threshold-width bound for monotone graph properties between fixed intermediate probabilities, where counts vertices, together with theconjectured extension to uniform hypergraphs .
18. Unique Games and 2-to-1 Games. My2018 post on the 2-to-2 Games Theorem discussed progress toward Khot’s conjectures and the issue of perfect completeness. The release announces a proof of theUnique Games Conjecture and, separately, the2-to-1 Games Conjecture with perfect completeness .
19. Matrix multiplication. My postCap Sets, Sunflowers, and Matrix Multiplication explored the connections between these problems. Thenew bound is over the complex numbers , a substantial advance toward the conjecture .
20. Percolation: criticality and nonuniqueness. The release includesabsence of infinite critical clusters for bond percolation on infinite connected locally finite quasi-transitive graphs with , extending the setting ofmy recent post on an AI proof of critical nonpercolation . It also announces for nonamenable graphs in this class , resolving the Benjamini–Schramm nonuniqueness conjecture discussedhere in 2009 .

A few more related posts #

1. The logarithmic Brunn–Minkowski conjecture. My postThe Logarithmic Minkowski Problem (2021) discussed the closely related existence problem for convex bodies with prescribed cone-volume data. The release announcesa proof of the logarithmic Brunn–Minkowski conjecture for origin-symmetric convex bodies in every dimension.
2. The two-point Chowla conjecture. InEDP Reflections and Celebrations (2015), I discussed Tao’s logarithmically averaged Chowla and Elliott results and their role in solving the Erdős discrepancy problem. Thenew manuscript announces the ordinary two-point Chowla conjecture, giving cancellation in the Liouville correlations (\sum_{n\le X}\lambda(n)\lambda(n+h)=o(X)) for every fixed (h\ge1).
3. High-dimensional expanders. InHigh Dimensional Expanders: Introduction I (2011), I discussed several notions of expansion for simplicial complexes, including coboundary expansion. Thenew construction gives arbitrarily large complexes in every dimension (d\ge3), with bounded vertex degrees and uniform (\mathbb F_2) coboundary expansion in every degree below (d).
4. Amenability of Thompson’s group (F). My postThe Thompson Group (2009) introduced the group of dyadic piecewise-linear homeomorphisms of the interval and highlighted the question of whether it is amenable. Thenew manuscript announces that Thompson’s group (F) is nonamenable.
5. Flat and ultraflat Littlewood polynomials. InFlat polynomials exist! (2019), I described the breakthrough of Balister, Bollobás, Morris, Sahasrabudhe, and Tiba and emphasized the remaining ultraflat problem for coefficients (\pm1). Thenew manuscript announces polynomials with (N) such coefficients whose modulus is ((1+o(1))\sqrt N) uniformly on the entire unit circle, answering that stronger question.
6. First-passage percolation. InAnalysis of Boolean Functions week 5 and 6 (2013), I discussed passage-time fluctuations and the challenge of improving variance bounds in first-passage percolation. The release announcesabsence of doubly infinite geodesics in the planar model for i.i.d. nonnegative nonatomic weights whose minimum over four independent samples has finite second moment, andstrict convexity and a continuously differentiable limit-shape boundary for exponential weights.
7. Stochastic games and the backgammon question. (added Oct. 22) InIs Backgammon in P? (2011), I discussed the problem of finding polynomial-time algorithms for two-player zero-sum stochastic games with perfect information. Thenew manuscript announces a deterministic quasipolynomial-time algorithm for the exact value-threshold problem in turn-based stochastic mean-payoff games, making progress toward the polynomial-time goal.