back
391 comments
I know a bit about this field. This conjecture reads as somewhat more niche than the cyclic double cover conjecture recently proved by OpenAI, but nevertheless represents a real contribution.

You want to know how long it takes to solve an optimization problem, in this case over convex, lipschitz functions. (The restriction to a spherical domain is not really a restriction, you can just change variables for any bounded domain.) Anyway, showing upper bounds on time complexity is "easy" because it's just the runtime of your algorithm. Showing (nontrivial) lower bounds is usually much harder because it requires constraining all algorithms.

This proof apparently shows that the lower bound time complexity is equal to the time complexity of an existing 30-year old algorithm: it requires Omega(d^2) function evaluations to solve over this class of functions.

My gut says likely implies that d is the minimal number of evaluations if you have a gradient oracle because you can approximate a gradient with d function evaluations, but I'm not sure how hard it is to make that rigorous.

Sometimes I read a comment on HN that is so advanced that it's just as readable to me as Greek. Love reading it just to see someone work though!
It should be noted that optimization of a convex bounded lipschitz function is exactly what most modern statistical learning (AI) models are based on.
Yes, order d is the minimal number of evaluations of gradients needed for the same problem! That has actually been known since 1979 (Nemirovsky and Yudin showed that), and there are methods with the same complexity so this question in the gradient model has been solved for a long time. "because you can approximate a gradient with d function evaluations" was exactly why d^2 made sense as a lower bound for this case! Basically, the lower bound question can also be thought about as "can you do better than approxing a gradient?", so this result says no.
Any implications for discrete/integer optimization?
> I don't think researchers in math/TCS will be made obsolete, but I think it will instead no longer make sense to work on any low-hanging, or even medium-hanging (you know what I mean) fruit. We'll be needed for problems where actual novel approaches are needed.

I wonder how this compares to what we see happening with "juniors" in software development? In math research, do you also get the training for the profession from working on the low hanging fruits for a while, to then move to the medium-hanging, and later go on to work on previously unsolved stuff?

Around here AI isn't really more of a threat to juniors than it is to seniors. It's a threat to the people who have been taught "recipies" rather than applied computer science. You can have excellent seniors who can do TDD, DRY, SOLID and so on, who also happen to have no idea what a L1 cache miss is. The current AI models know all of those things, but they struggle applying them correctly without someone piloting them. Even in the energy industry where I work, where you'd think it would be obvious from the context that you should prioritize runtime safety over debug safety, the current AI models struggle to do so. As far as seniority goes, though. If we can find a young developer with little experience who actually knows computer science, we're much more likely to hire them... Since they are cheaper.

This isn't something which is unique to software development though. We're currently building enterprise AI apps that we can deploy into the AI agents working for anyone of our employees. The key thing we're currently seeing is that the people in a team who are the ones that everyone turn to for advice, are the only people who aren't in "danger". Even people who are great at their jobs are being outperformed by AI in many cases.

I think it'll be a massive challenge for our society in the coming years. Maybe we're even going to get to the point where the AI will also be capable of replacing a lot of the "domain experts". Right now that seems far out, but then, if you had asked me about AI four months ago I would've told you it was all hype.

I was trained as a mathematician and worked as a math researcher for a little while (now working as a private tutor), and based on my experience I'd say this description is basically right, with one extra wrinkle.

In order to get a Ph.D., you have to do some sort of original research, so in that sense you're working on "previously unsolved stuff" basically right from the start. But that doesn't entail doing anything all that ground-breaking; most Ph.D. dissertations (very much including mine!) contain work that a more senior researcher in the same subfield could probably have produced without too much difficulty. The software development analogy is a pretty good one: a lot of the point of getting junior researchers to do research is to help train them to one day become senior researchers, and often the work itself is nothing all that special.

Given the trajectory of these LLM proofs, this seems like it's going to have to change pretty soon, and to be honest I'm pretty grateful that I'm not in charge of deciding what that's going to look like, because I don't have any good ideas! I'm actually pretty worried about the future of the field.

My experience may not be entirely representative because to be entirely honest I’m not exactly a great researcher and there are brilliant PhD students. That said it indeed was my experience that in the pre-PhD / early PhD period ( or even longer … ) your advisor proposes (gives) you pretty low hanging stuff that he mostly already knows how to solve, at least at a high level, with the expectation that it will teach you to use the mathematical tools you need.
This apparently required a 10-page prompt. It seems like someone needs to know enough to write it?
Math is way more automatable than programming.

In math, a proof is a proof. We don't know if we can get there and so getting there is the hard part.

In software, we always know that we can solve the problem. So HOW to solve the problem is the hard part. Because the type of solution involves maintainability, which involves planning, LLMs suck at it. This leads to "LLM slop code" whereby the LLM creates ad-hoc convoluted logic with redundancies and no reuse of existing standard library batteries.

Unless you're a Grothendieck who gets mad at Deligne for not solving the Weil's conjecture "THE RIGHT WAY", software is fundamentally different than math in this respect.

So I'll say it again, AI will win a fields medal for before managing a McDonald's simply because there are enough big problems within arms reach than their current capacity to plan over time

I would agree with your take. I (author of the post & paper) learned a ton from working on small parts of problems my PhD advisor was doing a lot of the heavy lifting on, and later also from getting some results that were essentially putting together the right pieces that already existed followed by some deep-in-the-weeds analysis.
So if you dig down a bit it turns out the author had been trying to solve that problem for a year with GPT 5.4 and 5.5 and he fed all that information to the prompt he gave to Sol Pro which may or may not had direct access to the author's chat history. So the claimed "148 minutes" was really "a year plus 148 minutes".

Moreover, it seems the prompt included the technique used to solve the problem:

https://old.reddit.com/r/math/comments/1uxj3cy/after_openais...

In the prompt I basically just throw all reasonable approaches at it, without making a big distinction for what to explore most, and these approaches would all be reasonable for someone who knows the area. Sol helped me with the prompt as well, for which I gave it the CDC prompt, some ideas and specifications, a crystal clear problem description, and then modified things slightly myself after. One thing I do wonder is how much it accessed memory of previous chats, since as mentioned I had worked with 5.5 and 5.4 on this previously, and the main construction is not so different from something I discussed there. But, the function class max of affine functions that worked in the end was also in my prompt, so I'm not totally sure.

So it's not clear to me the degree to which "GPT-5.6 used a prompt" to close the gap etc, or the author basically did all the work himself and assigned it to GPT-5.6 out of enthusiasm.

I (author of the original post and paper) can add a few things here: 1. My previous approaches with GPT 5.5 were really not very sophisticated in terms of my input. I threw the problem at it, and just kept encouraging it to go iterate through ideas without any success. 2. The approaches that are in the prompt, though they will seem cryptic to someone not in the field, are relatively natural ideas. In fact, the construction that worked was something that even 5.5 initially looked at but was just too weak to see how to make it work. From my view, I would have never gotten this result myself. Imagine you are telling a contractor to build the empire state building, and you say: "You should explore approaches that can include building materials like steel, wood, concrete, or clay, and any combinations of those. You can use arcs, columns, supportive beams, and anything else you can think of to solve load-bearing issues. Do not stop until you've completed a viable plan to construct the empire state building." And then the contractor shows you the finished empire state building using reinforced concrete and steel beams with all kinds of crazy ways of making everything stable; that's kinda how I feel.
> Moreover, it seems the prompt included the technique used to solve the problem:

I don't believe this is true. The author sent techniques he used, but I don't believe any of those were ultimately what GPT-5.6 used.

GPT-5.6 also provided the Lean formalization, which was not provided at all by the author.

sounds like a feature, not a bug

it might imply using weaker models to attempt the problem first is a good supplementary prompt to a more advanced model trying to do the same

In the Reddit post there was clarification that this was done with Sol Pro not Ultra - curious what is everyone’s mental model of the difference.

My understanding is that ChatGPT Pro is effectively a multi agent system, or somehow uses multiple LLMs in parallel and selects a best answer. And Ultra is more similar to Claude-Code UltraCode where the main agent can choose to create a dynamic JS workflow that deterministically orchestrates multiple agents to handle different parts of a task and have adversarial checkers etc.

Is that more or less the difference? Any substantiating sources would be great to see.

ultra in codex is just a way to run multi agent system, pro is similar to other pro models like 5.5
If I recall correctly there was a proposed proof to the abc conjecture by Mochizuki https://en.wikipedia.org/wiki/Abc_conjecture#Claimed_proofs which was rejected due to being rather inpenetrable to humans. Shouldn't this be an ideal target for LLMs?
It was rejected for being wrong (or most charitably, incomplete).
There was recently an announcement that a group trying to formalize it found a gap exactly where other mathematicians were pointing. So to the extent there was any doubt, it should be gone now--the proof was incorrect.

But I agree LLMs have a lot of potential for checking proofs--both informally (they can read quickly and find gaps) and formally (by attempting to formalize).

Crazy how intelligence is cheap, efficient and commonplace now. We humans better refocusing our energy on our core values/principles, given most of our skills are becoming irrelevant
Two points:

- Hasn't been peer reviewed yet, so take with a grain of salt. This applies to all claimed proofs, not just AI-generated ones. Even humans hallucinate proofs too!

- The prompt is on page 27 here[1]. It is ten pages of advanced mathematics priming the model in the right direction, apparently informed by a year of prior research. That doesn't invalidate the result if it is genuine, but it is worth noting that this wasn't a matter of "ChatGPT, solve this unsolved problem. Make no mistakes." and required substantial domain expertise and human research beforehand.

[1]https://arxiv.org/pdf/2607.13335

The problem is that we're going to have another deepseek moment when someone uses GLM or Kimi K3 to do this.
What I'm feeling is that there's a need to study how to use AI well. I've seen professors using AI, and it was amazing. In that sense, I think AI prompt input will become stratified. In the past, implementation skills were very important, but these days, concepts feel more important this is one of those things.

It's not that AI brings equality, but rather that the output varies depending on how much background knowledge you have. You could call it a stratification of input

I'm starting to feel like there's no place left for programmers like me who focus on quickly churning out MVPs.

Not yet peer reviewed
We have a non peer reviewed proof in a niche area of mathematics claiming to have been "co-written" by an LLM. What are the comments about? Lamenting or celebrating humanity's intellectual death... Very insightful.
I tried using AI to solve some advanced math problems. One thing I see is that they can throw an enormous amount of brute force into a problem. When mathematical logic can be brute forced we will see some interesting advances.
The amount of people several months ago stating that no one cares about the "unsolved" mathematical problems that AI is able to solve is funny.
Can't wait for GPT to prove that P=NP (or not)!
could machine-learning even handle a TEN PAGE PROMPT just a year ago?

this is changing my mind, at least about experts using advanced tools like any profession where it's like the magic of watching a lifetime of hard-earned skill at work

> After seeing OpenAI’s CDC result, I wrote a much more elaborate prompt following the same general methodology. My prompt is about ten pages long and attached at the end of the preprint (see collection of links below). There is a lot baked into this prompt, on approaches to try and also on how exactly the model should proceed, but it's built exactly in the style of OpenAI's CDC prompt. One note is that I gave it a relatively small error requirement, to prove the quadratic lower bound under order d⁻⁴ accuracy.

> After 148 minutes, GPT-5.6 Sol Pro returned a proposed proof resolving the quadratic dimension dependence at accuracy of order d⁻³. After checking things myself, I formally verified the proof in Lean, and it passed the formal verification check.

Basically, he proved that *information is power.* If you don't know which way to go (the subgradient), you're gonna be calculating forever!
I can't see this article as Reddit doesn't allow me to view it. Do we have to use Reddit though? It's a horrible website.
Genuinely asking... How do you get chatgpt to work for 148 mins when I can't get gemini to think for even a minute at a time?
It says I've been "blocked by network security". MSIE on Windows. Reddit must really be circling the drain.
Waiting for comments saying that LLMs can't produce anything new and general goalpost moving.
This is all a depressing and bleak future that I don’t look forward to.

One solution is to ban LLM’s, to artificially create a demand for human thought, that just feels like living in an artificially constructed zoo.

Another solution is humans don’t do anything that AI can do better , / doesn’t need the human touch. So I suppose we will all become artists, sportsmen or politicians, the only jobs that will remain except for select few. Maybe this is ok, I don’t know.

Another solution is we find a way to mind-meld with AI so that human + Ai >> AI alone. This is dystopian, who gets to decide who mind melds with AI, how much will it cost etc etc.

For the stupid copes that the prompt required human ingenuity, let me first add that the author used GPT5.6 to write most of the prompt. He just gave some mild direction. That amount of direction does not require deep expertise and the expertise required will keep falling with time, eventually an undergrad can create this loop and then maybe a high school student.

  And prompt engineering / loop engineering nonsense is not real. Calling it engineering is a psy-op because it is something simple, imprecise and future models will be much better at it than you.
In fact, in the future the most likely outcome is you tell the agent what you want (I want this app, or I want this theorem solved) and it will set up the loop, or loop of loops and use all its computing effort to come up with a result. This is completely dystopian to a human life.
Genuine question: If you still or did think LLMs are just stochastic parrots that just summarize everything and have no form of creativity, what do you think after seeing results like this?

I'm very curious how people reconcile their fear/hatred of AI with actual objective reality. This is actually what interests me most about the whole AI thing. How we tell ourselves what we tell ourselves.

nah, scientist with the name Shakey Onail found this and all creds are given to LLMs is crazy
Except solving problem is probably the least (even though it's important) interesting thing in research...

The most interesting thing in research is finding new questions, that we understand and that we know why they are important. And that's something that humans need to do (by definition)

Is this interesting? AI does what we made it to do, news at 8?