3SUM and APSP and ETH, Oh My! (Throughout this post I will assume that the recent results by OpenAI and Anthropic contain correct proofs of what they claim.) I wrote the following about 2 years ago but did not post it. It's dated, but that's the point. BEGIN DOCUMENT FROM TWO YEARS AGO Why do we think \(P\ne NP\)? a) Lots of people have worked on SAT and other NP-complete problems, without getting them in P. This is not mathematical evidence but it is worth noting. b) If SAT is in P then all problems in NP are in P. This implication is one reason I think \(P\ne NP\) is true. I find this more compelling than (a), though it's still not a proof. c) Just my opinion: I think SAT is not in P. ------------------------- 3SUM is the following problem: Given integers \(a_1,\ldots,a_n\) is there a triple of indices \(i< j < k \) such that \(a_i + a_j + a_k = 0\)? There is a clever algorithm for this problem that takes \(O(n^2)\) time. It is conjectured that 3SUM has no subquadratic algorithm (that is, for every fixed \(\epsilon>0\) there is no \(O(n^{2-\epsilon})\) algorithm). (My spellcheck doesn't think subquadratic is a word. Are they right?) This conjecture is widely believed. There is a notion of 3SUM-hardness and 3SUM-completeness. \( A \le B \) if there is a linear time function \(f\) such that \(x\in A\) iff \(f(x)\in B\). A problem \(A\) is 3SUM-complete if both \(A\le 3SUM\) and \(3SUM \le A\). There are around 15-20 3SUM-complete problems. Either they are all subquadratic (which includes 3SUM being subquadratic) or none are subquadratic. Given the conjecture, none of them are subquadratic. That is the common belief. Why do we think 3SUM has no subquadratic algorithm? a) Lots of people have worked on 3SUM without getting it into subquadratic time. This is not mathematical evidence but it is worth noting. b) Darn! There is no Cook-Levin-type theorem for 3SUM. c) Just my opinion: I think 3SUM is not subquadratic. I only wish there were a Cook-Levin-type theorem for this belief. I doubt this is possible. -------------------------- APSP (All Pairs Shortest Paths) is the following problem: Given a weighted graph \(G\), find, for all pairs, the cost of the shortest path. There is an \(O(n^3\)) algorithm for APSP. It is widely believed that there is no subcubic algorithm for APSP (that is, for every fixed \(\epsilon>0\) there is no \(O(n^{3-\epsilon})\) algorithm). This conjecture is widely believed. There is a notion of APSP-hardness and APSP-completeness. \( A \le B \) if there is a linear time function \(f\) such that \(x\in A\) iff \(f(x) \in B\). A problem \(A\) is APSP-complete if both \(A\le APSP\) and \(APSP \le A\). (My spellcheck doesn't think subcubic is a word. Are they right?) There are around 15-20 problems that are APSP-complete. Either they are all subcubic (which includes APSP being subcubic) or none are subcubic. Given the conjecture, none of them are subcubic. That is the common belief. Why do we think APSP has no subcubic algorithm? (a) and (b) similar to that for 3SUM. I state (c) c) Just my opinion: I think APSP is not subcubic. I only wish there were a Cook-Levin-type theorem for this belief. I doubt this is possible. --------------------------- ETH (Exponential Time Hypothesis) Not only is 3SAT not in P but 3SAT on \(n\) variables requires \(2^{\Omega(n)}\) time. ETH is widely believed. Informally, if ETH is true, and \(A\) is NP-complete by a linear reduction, then \(A\) requires exponential time. There are many such NP-complete problems. (a) and (b) similar to that for 3SUM. I state (c) c) Just my opinion: I think 3SAT requires \(2^{cn}\) time for some \(c\). I only wish there was a Cook-Levin-type theorem for this belief. I doubt this is possible. END DOCUMENT FROM TWO YEARS AGO Three of my favorite hardness assumptions had a bad month. I'm glad the Unique Game Conjecture was proven true so I am 1-for-4 rather than 0-for-3 (if it were still open) or 0-for-4 (if it was refuted). 1) Anthropic has obtained an \(O(n^{1.9992})\) algorithm for 3SUM. Darling thinks this result is hilarious. A writeup of this by J. Alman and V.V. Williams is here. 2) Anthropic has obtained an \(O(n^{2.9995})\) algorithm for APSP with integer weights (with no negative cycles). Darling, thinks this result is hilarious. (Spell check thinks Antrhopic is a word. Are they right?) The same writeup in item (1) also contains this result. 3) OpenAI has obtained a \(2^{O(n\log\log n/\sqrt{\log n})}\) algorithm for 3SAT Darling thinks this result is hilarious. I agree with her. (My spellcheck things OpenAI is not a word. Are they right?) OpenAI's announcement is here. Lance blogged about it here. So now what? 0) All of these results are being looked at by experts. 1) 1.9992 is close to 2. And we still think 3SUM can't get that much better. could conjecture that, for every fixed \(\epsilon\), there is no \(O(n^{1.5-\epsilon})\) algorithm for \(3SUM\). Assuming the conjecture, for every fixed \(\epsilon\), for every 3SUM-complete problem \(A\) there is no \(O(n^{1.5-\epsilon})\) algorithm for \(A\). At least until AI gives an \(O(n^{1.499999})\) algorithm for 3SUM. 2) Similar for APSP and, say, \(O(n^{2.5})\). 3) ETH. Replace with the following: there exists \(0

The Exponential Time Refutation In this week's big news (though it's only Wednesday), OpenAI announced a proof that the exponential-time hypothesis is false, with a Lean proof. Later Anthropic released their own paper. Ryan O'Donnell and Shiva Kintali posted follow-up proofs, smartly focusing on simplicity rather than getting the best bounds. OpenAI will partner with three of my favorite complexity theorists, Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify and study the proof. I have not verified the proof myself, but it is safe to assume now that the exponential-time hypothesis is toast. Recall 3-SAT, the problem of determining whether a Boolean formula that is an AND of ORs of three variables or their negations has a satisfying assignment. 3-SAT is the prototypical NP-complete problem from which we derive all the others. The exponential-time hypothesis (ETH), introduced by Impagliazzo and Paturi in 1999, building on their work with Francis Zane, states that there is a \(c > 0\) such that every algorithm solving 3-SAT requires time \(2^{cn}\), where \(n\) is the number of variables. There's also a strong exponential-time hypothesis (SETH) which says that for every \(\epsilon > 0\) there is a \(k\) such that \(k\)-SAT cannot be solved in time \(2^{(1-\epsilon)n}\). The OpenAI paper gives an algorithm that, for every fixed \(k\), determines whether a \(k\)-CNF formula with \(n\) variables and \(m\) clauses is satisfiable, and even counts the number of solutions, in time \((n+m)^{O(1)}\,2^{O(n\log\log n/\sqrt{\log n})}\) (their Lean proof gives a slightly weaker bound). This refutes ETH, and hence SETH, which implies ETH. If you want to understand the proof, I suggest starting with Ryan O'Donnell's paper. Ryan also mentions Bernardo Subercaseaux's observation that we get a nontrivial simulation of nondeterministic time on multitape Turing machines, \[\mathrm{NTIME}(T) \subseteq \mathrm{DTIME}\left(2^{O(T(\log\log T)^3/\sqrt{\log T})}\right).\] Researchers studied ETH and SETH because they implied many other hardness results, for example If ETH is true then Clique requires time \(2^{\Omega(n)}\) on \(n\)-vertex graphs, or \(2^{\Omega(\sqrt{m})}\) on graphs with \(m\) edges. If ETH is true then finding a clique of size \(k\) cannot be done in time \(f(k)\,n^{o(k)}\) for any computable function \(f\), so the trivial \(n^{O(k)}\) algorithm is essentially optimal. If SETH is true then the orthogonal vectors problem on \(n\) vectors of dimension \(\omega(\log n)\) cannot be solved in time \(n^{2-\epsilon}\) for any \(\epsilon > 0\). Bill's new (badly timed) book with Erik Demaine and Mohammad Hajiaghayi has details. The fact that ETH and SETH fail doesn't mean their implications are false. Keep in mind that the OpenAI algorithm applies to \(k\)-SAT but not to NP problems in general. It gives nothing new for Subset Sum or Traveling Salesman, whose best algorithms still take roughly \(2^{n/2}\) and \(2^n\) time, because the reductions from those problems to 3-SAT blow up the number of variables too much. Getting subexponential algorithms for all of NP would require solving 3-SAT in time \(2^{n^{o(1)}}\mathrm{,}\) which the OpenAI result doesn't get close to achieving. https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html #eth #ryan #omega #openai #shivakintali #mohanpaturi #russellimpagliazzo #lean #ryanwilliams #sat #rss #feeds #linksharing #qwibbit

When is it plausible that a result is optimal? (Lance and Bill did a vidcast about the OpenAI Document Drop. See here. My spellcheck thinks that vidcast and OpenAI are not words.) The Metric TSP problem is TSP where, for all vertices \(x,y,z\), \(w(x,z) \le w(x,y) + w(y,z) \). In 1976 Christofides and Serdyukov (independently of each other) showed that there is a poly time algorithm for a 1.5-approx to Metric TSP. Some people thought the 1.5 could be improved. Some people thought that 1.5 is optimal. 1.5 is a natural number. Hmm, that's not quite right. 1.5 is a pretty number. It would not be a surprise if someone had proven If there is a poly time (\(1.5-\epsilon\)) approx then P=NP. Indeed, people tried to prove that. In 2020 Karlin, Klein, Gharan, and Oveis proved there is a poly time (\(1.5-\frac{1}{10^{36}}\)) approximation algorithm. Darling thinks this result is hilarious. I tried to tell her that the result is important since a) We now know that 1.5 is NOT optimal. b) One of the authors, Nathan Klein, had been in my REU program in 2015. She was not impressed. Nobody believes that \(1.5-\frac{1}{10^{36}}\) is optimal. Is there a current conjecture? Klein told me he thinks 4/3. A pretty number. The recent results on Matrix Mult and Int Mult give a contrast involving pretty runtime and ugly runtimes. MATRIX MULT Let \(\omega\) be the least \(a\) such that two \(n\times n\) matrices can be multiplied together with \(O(n^a)\) operations. This definition is not quite right for two reasons: (i) It is possible (though I think unlikely) that there is no least \(a\), For example, if there is a sequence of algorithms with runtime \(O(n^{2.1})\), \(O(n^{2.01})\), \(O(n^{2.001})\), \(\ldots\), then there is no least \(a\), (ii) It is possible (though I thought unlikely before Oct 6, 2026), that the runtime may be different over different fields. We keep the incorrect definition to prove that ChatGPT is not the boss of me. Here are some known results. I may have missed some: The traditional algorithm: \(\omega\le 3\). Strassen's Algorithm (1969): \(\omega\le \log_2 7 = 2.807\ldots \). Coppersmith-Winograd (1990): \(\omega \le 2.376\ldots \). Stothers (2010): \(\omega \le 2.3736\ldots\). V.V. Williams (2012): \(\omega \le 2.3728642\ldots \). (Stothers and V.V. Williams were independent.) Alman and V.V. Williams (2020): \(\omega < 2.3728596\). Alman, Duan, V.V. Williams, Y. Xu, Z. Xu, and Zhou (2024): \(\omega < 2.371339 \). (The preprint was in 2024. The published paper was in 2025.) Google DeepMind's AI-based optimizer (August 2026): \(\omega < 2.371177\). The value 2.371177 was the best upper bound on \(\omega\) for about 2 months. The Chrysler Building was the tallest building in the world for about 11 months: from May 27, 1930 until May 1, 1931. The Empire State Building was the new champion. After May 1, 1931, the Chrysler Building wasn't even the tallest building in Manhattan. Fame is fleeting in both mathematics and architecture. Note: a) I believe that all of the algorithms above work over any field. Google AI agrees with that, but ChatGPT correctly reminded me that Google AI's opinion is not a proof and that I should seek a citation or a counterexample. If you know of a citation to confirm the any-field statement, or a counterexample to the any-field statement, please leave a comment. b) After 1990 the improvements are really small. c) None of these bounds is a pretty candidate for the true exponent. We need notation that makes the field explicit. Let \(\mathbb{F}\) be a field. Let \(\omega(\mathbb{F})\) be the least \(a\) such that two \(n\times n\) matrices over \(\mathbb{F}\) can be multiplied together with \(O(n^a)\) operations. (ChatGPT is still not the boss of me.) OpenAI showed the following: a) \(\omega(\mathbb{C})\le 2.25\). 2.25 is a very pretty number. It makes my heart go pitter-patter. b) For every field \(\mathbb{F}\) they have \(\omega(\mathbb{F}) < 2.371054886006746\). Lean-formalized. A separate GitHub project claims to extend the 2.25 bound to every field with a Lean-checked proof. I have not checked the extension (as opposed to all of the new results OpenAI has dropped, which I have checked line by line with a quill pen and inkwell by the light of an oil lamp). The project is here. Back to the issue at hand. The drop from \(\omega \le 2.37\) to \(2.25\) is a Bob Beamon moment. Recall that before the 1968 Summer Olympics in Mexico City, the world record for the long jump was 27 feet, 4.75 inches (8.35 meters). During those Olympics, Bob Beamon jumped 29 feet, 2.5 inches (8.9 meters). A massive improvement. His record stood until 1991, when Mike Powell jumped 29 feet, 4.5 inches (8.95 meters). Gee, only two inches more! Mike Powell's jump still holds the record. So Beamon had the record for 23 years, and Powell has the record for 35 years. If matrix multiplication follows the same pattern, we may wait 23 years for the next improvement and 35 more years for the one after that. However, since we are dealing with silicon instead of carbon, it may be 23 days and 35 days. I am happy that the new upper bound on \(\omega\) is a pretty number and hence a plausible candidate for optimal. If no one improves the result within 23 days, I will think 2.25 is optimal. INT MULT Improved Algorithms for Integer Multiplication of two \(n\)-bit numbers. In 1971 Schonhage and Strassen conjectured that there is an algorithm for integer multiplication that takes \(O(n\log n)\) bit operations. In 2019, Harvey and van der Hoeven proved this conjecture. Is there an algorithm that takes less time? Or is \(O(n\log n)\) optimal? OpenAI obtained an algorithm that takes \(O(n(\log n)^{1-\kappa})\) bit operations, where \(\kappa=2^{-82}\). Really? \(2^{-82}\)? I declined to tell Darling about this one. Google tells me that OpenAI did not lean-verify this one but open-source contributors later completed an independent Lean verification of the algorithm and improved the bound. The link is here. The improvement first pushed the small term to \(2^{-34}\) and then to \(2^{-14.38}\). I won't tell Darling these results until its down to \(2^{-1}\). Note the contrast between matrix multiplication and integer multiplication. Matrix multiplication went from a runtime too ugly to be optimal---(O(n^{2.371\ldots})\)---to one pretty enough to be optimal---\(O(n^{2.25})\). Integer multiplication went from a runtime pretty enough to be optimal---\(O(n\log n)\)---to one too ugly to be optimal---\(O(n(\log n)^{1-\kappa})\), where \(\kappa=2^{-14.38}\) https://blog.computationalcomplexity.org/2026/10/when-is-it-plausible-that-result-is.html #metrictsp #building #optimal #documentdrop #may #williams #chryslerbuilding #result #algorithm #klein #rss #feeds #linksharing #qwibbit

Reading Messy Proofs In fall of 1985 when I started graduate school, my advisor Michael Sipser asked me to read an early handwritten manuscript by Johan Håstad of his switching lemma. I spent many hours decoding the notation and working through the messy conditional probabilities until I felt I had checked every step of the proof. When I started presenting this to Sipser, he stopped me and said he didn't want the details but instead the intuition of the proof. I had nothing. I'm reminded of this story as I hear the complaints of how badly OpenAI wrote the 712 papers released on October 6th, as though humans wrote crystal-clear proofs beforehand, definitely not the case in general, especially in the early versions. Noam Nisan once told me that reading a badly written proof leads to better understanding since you really need to figure out the details instead of having them neatly spelled out. Perhaps, but do not use this as an excuse for not taking the time to write the details properly. I approach reading the proof of a new result by assuming the proof is wrong until I'm convinced otherwise. Working my way through early versions of Immerman-Szelepcsényi and Toda's theorem definitely forced me to understand these proofs well so I could explain them to others. I just gave up on fully understanding some results like the original PCP theorem and Ran Raz's Parallel Repetition Theorem, despite seeing the authors give talks on the papers. Sometimes you have to trust the authors and others who hopefully have read the paper. Don't even get me started on László Babai's Graph Isomorphism in quasipolynomial time. And some papers, like Primes in P, require mathematical results in other subfields that I just have to accept. Sometimes you'll just get better versions of proofs, most famously Irit Dinur's combinatorial proof of the PCP theorem. I only really understood the switching lemma years later when Sophie Laplante and I wrote a Kolmogorov complexity-based proof building on a then-new proof of Alexander Razborov. When I get stuck in a proof, I sometimes ask the authors, but usually as a last resort unless I can talk to them in person. That's an advantage we have now: you can ask AI to get you over a hurdle in a proof. Claude, while maybe not as good at proving theorems as the unreleased OpenAI model, does a better job writing them up. And one hopes that we'll see simplified and possibly strengthened versions of some of these important results, written by humans or human-AI collaborations. Maybe we'll even get the intuition Sipser told me to seek all those years ago. https://blog.computationalcomplexity.org/2026/10/reading-messy-proofs.html #michaelsipser #johanhastad #pcp #sometimes #parallelrepetition #ranraz #laszlobabai #rss #feeds #linksharing #qwibbit

AI, Math, the document-drop. Non-Tech Thoughts So what to make of OpenAI and the future of Math? Here are some points I've either: thought of myself or heard from a human or read from an AI. Throughout this post I use the term AI to mean an AI system that produces mathematical results. I decline to say OpenAI or Anthropic as generic terms since about 20 years ago I used Intrade as a generic term for Betting Markets---then Intrade went out of business. I wish I had bet on that happening. Oh well. 1) Some of the proofs were Lean-formalized and some were not. If a proof is Lean-verified do we know the proof is valid? The issue is not bugs in Lean. The issue is that coding a theorem/proof into Lean may be done incorrectly. So Lean might be verifying a proof of a theorem different than what was intended. Peter Woit, is a string-theory skeptic and a Lean-skeptic. See here Alexander Bastounis, Fabian Circelli, Anders Hansen argue that the Lean formalization does not correspond to the natural-language proof. See here My impression/predictions are: (1) Lean has a good track record BUT we are in uncharted territory here. (2) In the end humans will read, understand, and fix the proofs if necessary. This will take time. (3) Humans will produce readable writeups that are enlightening. This will take time. (4) Some bugs in Lean will be discovered and fixed. This will take time. (5) Humans will learn how to better code theorems and proofs into the Lean language. This will take time. 2) Most (all?) of the papers were hard to read, even by experts. Lance asked Claude for a better written version of UGC and he got one: here. Why didn't OpenAI ask Claude for better writeups? 3) A History of my thought on the Unique Game Conjecture: In 2006 I thought the Unique Game Conjecture would be proved by 2011. I was wrong. In 2016 I thought the Unique Game Conjecture would be proved by 2026. I was right. In 2026 I thought the Unique Game Conjecture would be proved by 2046. I was right literally but wrong really since in January 2026 I was thinking 10-20 years, not 7 months. 4) Right now AI is merely combining known ideas and writing up the proofs badly as opposed to most mathematicians who come up with new ideas and they write them up well. I am, of course, kidding. 5) There have been barrier results along the lines of Technique X will not suffice to prove Y' Some papers say this informally, e.g., our methods cannot be extended and some papers say this formally, e.g., since there are oracles that force P=NP and oracles that force \(P\ne NP\), relativizing techniques do not suffice to resolve P versus NP (My PhD is on oracles, yet I replaced recursion-theoretic techniques with relativizing techniques because ChatGPT is the boss of me.) What we really want to prove is that known techniques won't solve a problem, hence we need to look for new techniques. If problem X has not been solved within 10 years by AI, then is it safe to assume that known techniques will not suffice? Probably not: a) AI will not make all connections between all the parts of math within 10 years, maybe not ever. b) AI companies might stop having their machines work on math problems. I'm surprised they are doing that now since mathematicians who want to solve open problems are not a big market. Then again, they could advertise as follows: Buy Our Theorem Prover and you Might Solve a $1,000,000 Math Problem!!! or a Salmon (see here)!!! 6) The notion that AI is combining known ideas is true but is not a problem. However, might the following happen: What if within 10 years all math that can be done with known techniques will have been done. Then either a) Humans will step up to the plate and come up with new ideas. Let's hope they never stopped. b) Humans will have lost the ability to come up with new ideas because they will have been spoiled by AI. Like if Lance and I had to become hunter-gatherer. Lance's initials would then stand for Lion Food, and Bill's initials would stand for Bear Grub. (I came up with Lion Food, but I asked Gemini for Bear Grub. I doubt you care. AI-disclosure can be stupid.) c) AI will be able to come up with new ideas. The current LLM models probably can't do that but they may help design something that can. d) As noted in comments 5, AI companies might give up on this line of work. 7) When Deep Blue beat Kasparov an ordinary citizen could not purchase a computer that would play grandmaster-level chess. Now an ordinary citizen can download for free a chess playing program that can beat the world chess champion. Will this happen with AI for Math? Will an ordinary citizen be able to download for free, or pay a reasonable price for, an AI program that can prove hard theorems? 8) AI-assisted vs AI-generated may be a big distinction. Or not. Or it may be hard to tell the difference. I can imagine working on a project where I do some, an AI does some, and I don't really want to figure out and report on who did what part. Similar to human co-authors today. This comes up when one of my HS students enters the Regeneron Science Talent Search and the forms ask in 16 different ways What was their contribution and What was your contribution? In the future will they ask What was the AI contribution? 9) Hypothetical: I ask AI to prove \(P\ne NP\) and it gives me a proof that I rewrite to be readable. I submit it to STOC, honestly acknowledging what my contribution was, which is mostly exposition. Assume I meet the ACM authorship criteria. a) Is the fact that I used AI held against me? b) Should the paper get in? c) Do I get the Millennium Prize and hence $1,000,000? d) Do I win a Turing Award and hence another $1,000,000? 10) How is OpenAI making money on this? Three sources that I know of, New Scientist, Science Magazine, and Crypto Briefing (I am having trouble getting the links to work) put the cost at around 15 million dollars. After OpenAI spent that much money solving a Millennium problem, they stated that they would not try to collect the $1,000,000 (it's not clear they would have qualified for it). That seems odd. What is their business model? To generate buzz? If so then note the following: I have asked my non-math friends (Lance is surprised I have non-math friends) if they have heard about the OpenAI Document Drop. No. Some had vaguely heard that AI solved an important problem that was worth some money, I assume that's Navier-Stokes, but that's it. No buzz. The Atlantic Monthly has published an article about this titled OpenAI Just Carpet-Bombed Mathematics (see here) This will give OpenAI more publicity. Is it good or bad publicity? There is a famous quote there is no such thing as bad publicity. Is it true? See here. As I finish this post (Translation: As I argue with Chatty about this post) OpenAI has announced that it will give $5 million to the Simons Foundation initiative to help mathematicians examine, understand, and build on results produced by AI. That may help explain its community engagement, but the existence of a business model is still an open question. As I finish this post (Translation: As I argue with my AI-skeptical proofreader) my proofreader announced that he knows OpenAI's business model: Delusion and IPO or Delusion plus PR to get more funding. The IPO is looking less likely. Is he right? Is that really a business model? Here is a link about the business model: here. I wrote most of this blog post on Tuesday Oct 13, 2026. I posted it on Oct 18, 2026. Between Oct 13 and Oct 18 the post aged: at a funeral I went to today (Oct 16, 2026-Boss's day!) non-math people asked me Now that OpenAI can solve open math problems, how do you stop your students from cheating on homework? So non-math people have heard the news, though they don't quite understand it. 11) I told my Mom that AI had solved some problems that I cared about and that I was happy about that. She asked Can AI fix my answering machine and then have Lean verify that it works? 12) On Scott's blog (see here), comment number 12 by Tristan, perhaps unintentionally, raised an interesting question. Here are some quotes from Tristan's comment: But perhaps the occasion calls for a little reflection. If a pattern-interpolating autocomplete can produce your theorem quite so readily, one is entitled to wonder how intellectually demanding the enterprise was to begin with. Perhaps what you took for creativity and insight was, on closer inspection, neither. Algebraic geometry [Tristan's field] is, mercifully, a field in which genuine creativity remains indispensable: one must actually conceive and construct new mathematical objects, rather than rearrange familiar patterns and dignify the exercise with the word `discovery'. It is precisely this sort of work that lies beyond the capacities of a glorified autocomplete. a) Such elegant arrogance! Such elegant nonsense! Such arrogant nonsense! b) This is the kind of quote that will age badly once OpenAI begins solving problems in Algebraic Geometry. c) I disagree with him: there are easy and hard problems in all fields of math. Algebraic Geometry is an older field, so perhaps there is less low-hanging fruit. But this is a minor point and not the fundamental difference he makes it out to be. And I hardly call the Unique Game Conjecture or L=RL low hanging fruit. d) Still, to turn his thoughts into an intelligent question: What types of math problems are more prone to have AI solve them? e) Scott later left the comment: LOL! That was a delightful parody (at least, I assume it's a parody) of what I've now heard dozens of times in earnest. Bill here: I FELL FOR IT. f) Anon later left a comment that flagged Tristan's post as AI-generated by running it through an AI program to detect AI-generated writings: here. Bill here: I NEVER SUSPECTED IT WAS AI. FROM NOW ON I WILL SUSPECT EVERYTHING IS AI. 13) A 1985 article in Kvant, a Soviet Mathematics Magazine, by Uspenskii and Semenov, titled Solvable and Unsolvable Algorithmic Problems, contained the following quote: Tarski's result [that elementary geometry is decidable] appears to be, and actually is, extremely powerful and even paradoxical. There is a very extensive area of classical mathematics (namely elementary geometry) which is traditionally thought to require a subtle intellect and which can by no means be reduced to carrying out routine computations, and yet, at the same time, there is an algorithm that can verify the truth of theorems in the area (and provide the proofs). We can console ourselves only in the fact that Tarski's algorithm is not realistic: it requires an inconceivably great amount of time for its implementation. I leave it to the reader to adapt this quote to the current situation. Or not. 14) So what now for mathematicians? For Math grad students? a) OpenAI says its model attempted roughly 4000 problems and reported results for 372 families, some full and some partial. So there is still plenty that OpenAI can't do. But who knows what the future will bring? b) There are plenty more problems that OpenAI was not given. c) There is a lot more to research than research. (Both ChatGPT and my proofreader think the last sentence was a typo. It's not.) There are surveys, blogs, raising questions, and rewriting proofs so they are readable. Will Tenure committees, the NSF, and others, see it that way? e) I wonder if in the future the quality of exposition may be more important since the journals and conferences will just assume that the brilliant ideas were done by AI and give the human less credit. If Math dissertations end up being more readable, I call that a win. https://blog.computationalcomplexity.org/2026/10/ai-math-document-drop-non-tech-thoughts.html #uniquegame #gameconjecture #lean #math #intrade #openai #bettingmarkets #ai #rss #feeds #linksharing #qwibbit

Conjectures that I thought would not be proved in my lifetime....were 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. 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. My proofreader suggests GARBARGE DUMP. I prefer the more neutral DOCUMENT DUMP. Scott blogged about what he calls the Mathocalypse Peter Woit weighted in on what he calls the Slopocalypse. He has many astute observations. Among them: he has good reasons to think that Lean-formalized does not necessarily mean that a proof is correct. For another skeptical-of-Lean viewpoint see here. Now it's my turn to comment on the DOCUMENT DUMP. 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\). We denote \(\chi(G)\) by \(\chi\). The proof that \(4 \le\chi\) is easy. The proof that \(\chi\le 7\) is easy. In 2018, Aubrey de Grey improved the lower bound to 5. The proof that \(5\le \chi\) 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 improved the lower bound 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 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 roughly \(r^{k-1}\). Is this a big improvement? We think of \(r\) as small and \(k\) as big so yes. The paper that OpenAI put out on this misquotes the prior result as \(W(k,r)\ge \beta r^k \). If they got that wrong, I wonder what else they got wrong. But I will assume their proof is correct. 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 PROVED 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 OpenAI or Anthropic or some young scrappy upstart 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 other domains such as \(\mathbb{Q}\). For the domains \(\mathbb{R}\) and \(\mathbb{C}\) the problem is known to be decidable (see later in this entry). But for \(\mathbb{Q}\) it was open. If it is decidable then that might lead to interesting number theory. (THANKS to a commenter who pointed out I should ask about other domains.) 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. A table of what is known over other domains is here. -------------------------------------------- 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 u 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). ADDED LATER: a commenter DID find it and left a comment. GOOD NEWS: the manuscript is here. BAD NEWS: Now I don't have an excuse to not read it. ODD POINT: There are still times when asking a set of people is better than asking Google or even Google AI. This is a hard manuscript to read (I've heard). The manuscript uses models of set theory to prove results in recursion theory. OpenAI showed that there are no non-trivial automorphisms of TD. Lean-formalized. There are very few people working on this problem. It may take a while to get it human-understood. https://blog.computationalcomplexity.org/2026/10/conjecture-that-i-thought-would-not-be.html

Complexity and Lean In the OpenAI Math Drop some papers have Lean proofs, others don't, including L = RL = BPL. Why is it hard to formalize results on complexity classes? Let's consider an example, Lautemann's proof that BPP is in \(\Sigma^p_2\). It's a beautiful proof because it comes down to a single formula. I gave the full proof in a 2025 post, but to remind you, here is the setup. Let \(B\) be in BPP, accepted by a probabilistic polynomial-time Turing machine \(M\) with error bounded by \(2^{-n}\). Let \(A(x,r)\) be true iff \(M(x)\) using random tape \(r\) accepts. \(A(x,r)\) is deterministically polynomial-time computable. We can assume \(|r|=|x|^k\) for some \(k\). Here is the \(\Sigma^p_2\) expression for input \(x\) of length \(n\). All quantification is over binary strings of length \(n^k\). Let \(\oplus\) be bitwise parity (XOR) and \(\vee\) be logical OR. \[\exists z_1,\ldots,z_{n^k}\ \forall y\ \ A(x,z_1\oplus y) \vee \cdots \vee A(x,z_{n^k}\oplus y)\] The hard part of the proof, besides coming up with this formula itself, is the probabilistic argument to show you always get the right answer. So this seems simple enough to give a full Lean proof. And it is not too hard (for Claude) to get Lean to formalize the probabilistic argument, though even there Lean makes you deal with details we wave away on paper. When \(x\not\in B\) the argument needs \(n^k2^{-n}<1\), which fails for small \(n\), so short inputs need separate handling. But you also need to show the following: Let \(A(x,r)\) be polynomial-time computable. Then given \(x\), \(y\) and the \(z_i\) as inputs, you can compute \(A(x,z_1\oplus y) \vee \cdots \vee A(x,z_{n^k}\oplus y)\) in polynomial time, where \(u\oplus v\) is bitwise parity. There is nothing challenging about this statement. It is so painfully obviously true that I didn't even bring up this point in the 2025 post. But proving you can do this in polynomial time on a Turing machine, even though the only operations are bitwise parity, ORs and composition, is just very complicated to formalize in Lean. Some suggest that using Cobham's characterization might be easier. But see below for what you need to do for bitwise parity alone. Imagine how complicated it would all get for something like Toda's theorem. Update: Since I first drafted this post, OpenAI dropped a claimed Lean proof of L = RL = BPL, so maybe ignore this whole post? Cobham defined his class as the smallest set of functions on the natural numbers (viewed as binary strings, with \(|x|\) the length of \(x\) and \(|0|=0\)) that contains the constant zero, the projections, the two successor functions \(s_0(x)=2x\) and \(s_1(x)=2x+1\), and the smash function \(x\#y=2^{|x|\cdot|y|}\), and that is closed under composition and bounded recursion on notation. The second operation defines a new function \(f\) from functions \(g\), \(h_0\), \(h_1\) in the class by \[\begin{aligned} f(0,\vec{y})&=g(\vec{y})\\ f(s_i(x),\vec{y})&=h_i(x,\vec{y},f(x,\vec{y})) \end{aligned}\] for \(i\in\{0,1\}\) and \(s_i(x)\neq 0\), provided that \(f(x,\vec{y})\leq k(x,\vec{y})\) for some \(k\) already in the class. The recursion runs over the bits of \(x\), so it takes only \(|x|\) steps. The smash function gives the outputs polynomial growth in their lengths, and the bound \(k\) keeps that growth from compounding over the recursion. Cobham's theorem says that this class is exactly the set of functions computable in polynomial time. As an example, consider bitwise XOR, \(f(x,y)=x\oplus y\). The difficulty is that bounded recursion on notation peels bits off only one argument, while XOR has to move through \(x\) and \(y\) together. The fix is to recurse on a long enough counter \(T\) and extract the bits of \(x\) and \(y\) by shifting. We first need four helper functions, each defined by a single bounded recursion on notation: \[\begin{aligned} \mathrm{par}(0)=\mathrm{par}(s_0(x))&=0, & \mathrm{par}(s_1(x))&=1\\ \mathrm{half}(0)&=0, & \mathrm{half}(s_i(x))&=x\\ \mathrm{msp}(0,x)&=x, & \mathrm{msp}(s_i(w),x)&=\mathrm{half}(\mathrm{msp}(w,x))\\ C(0,u,v)=C(s_0(a),u,v)&=u, & C(s_1(a),u,v)&=v \end{aligned}\] with bounds \(1\), \(x\), \(x\) and \(s_1(u)\#s_1(v)\) respectively. Here \(\mathrm{msp}(w,x)=\lfloor x/2^{|w|}\rfloor\), so bit \(j\) of \(x\) is \(\mathrm{par}(\mathrm{msp}(w,x))\) for any \(w\) with \(|w|=j\). \(C\) is a conditional on the low bit of \(a\). Composition then gives the XOR of the low bits of \(a\) and \(c\), \(\beta(a,c)=C(a,\mathrm{par}(c),C(c,1,0))\), and appending the low bit of \(b\) to \(z\), \(\mathrm{app}(b,z)=C(b,s_0(z),s_1(z))\). Now we recurse on \(w\) with \(T\), \(x\) and \(y\) as parameters, building the answer from the top bit down. Let \(m_i=\mathrm{msp}(s_i(w),T)\), which has length \(|T|-|w|-1\), the position of the next bit to append, and let \(b_i=\beta(\mathrm{msp}(m_i,x),\mathrm{msp}(m_i,y))\) be that bit of \(x\oplus y\). Then \[\begin{aligned} G(0,T,x,y)&=0\\ G(s_i(w),T,x,y)&=\mathrm{app}(b_i,G(w,T,x,y)) \end{aligned}\] By induction, \(G(w,T,x,y)\) is \(x\oplus y\) shifted right by \(|T|-|w|\) bits, so it is bounded by \(s_1(x)\#s_1(y)\). Finally we set \[f(x,y)=G(T,T,x,y)\quad\text{where } T=s_1(x)\#s_1(y).\] The smash gives \(|T|=(|x|+1)(|y|+1)+1\geq\max(|x|,|y|)\), so the recursion starts above the high bits of both arguments, where every bit is zero. \(T\) is much longer than it needs to be, but that costs only polynomially many extra steps. https://blog.computationalcomplexity.org/2026/10/complexity-and-lean.html