Lance blogged on the OpenAI solutions to many problems here and also created a website of the TCS-related problems OpenAI claims to have solved here.
Scott blogged about it here.
Terry Tao seems to have had an infinite number of guest bloggers talking about AI and Math even before the OpenAI .... WE NEED A WORD FOR IT.
Now it's my turn. For now I will just discuss some of the results without getting into what it means for the future of mathematics, the future of academia, and the future of humanity.
--------------------------------
1) Let \(G\) be the graph whose vertex set is \(\mathbb{R}^2\), with an edge between every pair of points exactly a unit distance apart. The chromatic number \(\chi(G)\) is called the chromatic number of the plane. For nearly 70 years, all that was known was \( 4\le \chi\le 7\).
The proof that \(\chi\ge 4\) is easy.
The proof that \(\chi\le 7\) is easy.
The proof that \(\chi\ge 5\) is hard: it involves a 1,581-vertex graph, later reduced to 509 vertices by Jaan Parts, who probably did it in parts.
The new result by OpenAI: \( 6\le \chi\). Lean-formalized.
When I first heard that OpenAI had solved this, I thought they did a clever search for a larger graph.
I was wrong.
OpenAI's proof took an entirely different approach. They proved the following:
a) If there is a proper 5-coloring of \(\mathbb{R}^2\), then there is a weak measurable proper 5-coloring.
b) There is no weak measurable proper 5-coloring of \(\mathbb{R}^2\). Therefore, there is no proper 5-coloring of \(\mathbb{R}^2\).
Was the idea of using measurable colorings new? No.
Measurable colorings had been studied before. Falconer showed that any measurable proper coloring of \(\mathbb{R}^2\) requires at least five colors. This result rules out a measurable proper 4-coloring but allows the possibility of a measurable proper 5-coloring. OpenAI's result rules out a proper 5-coloring even without a measurability assumption. OpenAI used the notion of weak measurable colorings to obtain a result about all colorings. That is new.
This is a clear case of Searching has reached its limits; we need a new approach and OpenAI found one.
-----------------------------------------
2) The Erdős-Turán Conjecture. Let \(A=\{a_1<a_2<\cdots \}\) be a set of positive integers such that \(\sum_{i=1}^\infty \frac{1}{a_i}\) diverges. Then \(A\) has arbitrarily long arithmetic progressions.
What was known? In 2020, Bloom and Sisask showed that \(A\) contains a 3-term arithmetic progression. See here.
The general result for 4-term progressions was open.
This is widely considered a very hard problem. I didn't think this conjecture would be solved soon. But it has been solved and Lean-formalized. I hope it soon becomes people-understood.
The \(k=3\) case was hard. I thought that
(a) people might go on to prove the \(k=4\) case, but
(b) anything beyond that was out of reach.
So I am very surprised to see a proof for all \(k\).
In my view, this is the most important and impressive of the new results. Why? Of the results discussed, this one seemed least likely to be solved by humans and most likely to depend on deep mathematics.
------------------------------
3) Let W(k,r) be the least W such that, for every \(r\)-coloring of \(\{1,\ldots,W\}\), there is a monochromatic arithmetic progression of length \(k\). The upper bounds on \(W(k,r)\) are enormous. It was known that, for large \(k\), \(W(k,r)\ge r^k/(ekr)\).
The improvement: there is an absolute constant \(c\) such that, for every \(r\ge 2\) and sufficiently large \(k\), \(W(k,r)> k^{ck\lfloor \log_2 r\rfloor}\). Lean-formalized.
I am not surprised at the result. I am surprised that the result has been proved. For a long time, the best lower bound was \(r^k\), up to polynomial factors.
The lower and upper bounds are still in different zip codes, but at least now they can send each other postcards.
-----------------------------------
4) Let \(g_d(n)\) be the minimum number of distinct distances determined by an \(n\)-point set in \(\mathbb{R}^d\). Erdős made two conjectures about \(g_d(n)\).
CONJECTURE ONE:
\(g_2(n)=\Omega(n/\sqrt{\log n}) \). This matches the upper bound achieved by the points in a \(\sqrt{n} \times \sqrt{n}\) grid. Guth and Katz showed in 2010 that \(g_2(n)=\Omega(n/\log n) \).
CONJECTURE TWO:
What happens for general \(d\)?
Erdős proved that, for all \(d\ge 3\), \(g_d(n) = O(n^{2/d})\).
Erdős conjectured that, for all \(d\ge 3\), \(g_d(n) = \Theta(n^{2/d})\).
In 2008, Solymosi and Vu proved that, for all \(d\ge 4\), \(g_d(n)=\Omega(n^{2/d-2/(d(d+2))})\), and \(g_3(n)=\Omega(n^{0.5643})\).
OPENAI SOLVES CONJECTURE TWO
There had been improvements in low dimensions since then, most notably Tidor, Yu, and Zakharov's proof that \(g_3(n)\ge n^{2/3-o(1)}\), but the conjecture remained open for general \(d\).
OpenAI showed that, for all \(d\ge 3\), \(g_d(n)=\Omega(n^{2/d})\).
So now we know that, for all \(d\ge 3\), \(g_d(n)=\Theta(n^{2/d})\).
Or do we? The result has not been Lean-formalized (as of October 9, 2026).
I wonder if AI will close the small gap in the upper and lower bounds for \(g_2(n)\).
------------------------
5) Hilbert's Tenth Problem over \(\mathbb{Q}\)
Hilbert's Tenth Problem over \(\mathbb{Z}\), the standard version, is the following decision problem:
Find an algorithm that will, given a polynomial \(p\in \mathbb{Z}[x_1,\ldots,x_n]\), determine whether there are integers \(a_1,\ldots,a_n\in \mathbb{Z}\) such that \(p(a_1,\ldots,a_n)=0\).
Hilbert likely intended this problem to stimulate research in number theory. It did to some extent. Davis-Putnam-Robinson and Matiyasevich showed the problem was undecidable. In my view, the proof used clever number theory but not deep number theory.
Since the problem over \(\mathbb{Z}\) is undecidable, it is natural to ask the question over \(\mathbb{Q}\). Perhaps that will be decidable and lead to interesting work in number theory. First, here is the formulation:
Find an algorithm that will, given a polynomial \(p\in \mathbb{Z}[x_1,\ldots,x_n]\), determine whether there are rationals \(a_1,\ldots,a_n\in \mathbb{Q}\) such that \(p(a_1,\ldots,a_n)=0\).
OpenAI showed that this problem is also undecidable. It has not been Lean-formalized.
Judging from the table of contents, the proof looks like it uses deep math. So maybe the problem did lead to interesting number theory, as Hilbert would have wanted.
--------------------------------------------
6) Is there a non-trivial automorphism of the Turing degrees?
Let TD be the set of all Turing degrees.
An automorphism of the Turing degrees is a bijection \(f\) from TD to TD such that
\( a \le_T b \) if and only if \( f(a) \le_T f(b) \).
A non-trivial automorphism is one that is not the identity function.
In the mid-1960s Hartley Rogers posed the question:
Are there any non-trivial automorphisms of TD?
Slaman and Woodin wrote an unpublished manuscript titled Definability in Degree Structures where they prove that the number of automorphisms of TD is countable. (The bibliography of the OpenAI article on this problem gives 2005 for the year.)
This is a hard manuscript to find (I can't find it---if you can then leave a comment).
This is a hard manuscript to read (I've heard).
The manuscript uses models of set theory to prove results in recursion theory.
There are very few people working on this problem. It may take a while to get it human-understood.
No comments:
Post a Comment