An Israeli AI startup says it cracked a 38 year old graph theory bound for $2,000

Under $2,000 in compute. No human steering the math. That's what it took for doubleAI's autonomous system to beat a bound in error correcting codes that stood since 1988, with every step written in Lean for other mathematicians to verify.

Forget the "Longest Path problem." That claim, which has been circulating in AI forums like r/singularity this month, misstates what doubleAI actually announced. Calcalist reported the real result. It's narrower, and more interesting for it: the Israeli startup's "Double Agent" system found a new explicit construction in extremal graph theory that improves a bound nobody had moved since 1988. It did the whole thing autonomously, for under $2,000 in compute.

The problem concerns the girth of regular graphs, essentially how far you can travel from any point in a graph before you run back into a cycle. Since 1988, the best explicit constructions, built by Gregory Margulis and separately by Alexander Lubotzky, Ralph Phillips and Peter Sarnak, topped out at a girth coefficient of 4/3, with the theoretical ceiling sitting at 2. Double Agent pushed that number to 8/5. It found a new algebraic construction and proved the improved bound holds for infinitely many graph degrees, not just a handful of cases, according to Calcalist's report.

Why does girth matter to anyone outside a graph theory seminar? Larger girth means a graph looks more like a tree in the neighborhood around any given vertex. That property is exactly what makes certain graphs useful for building low-density parity-check codes: the error-correcting codes behind everything from satellite links to, eventually, more reliable quantum computation. Margulis's original work on this problem already fed directly into LDPC code design. An improvement here is not an abstract curiosity. It's a better raw material for a specific kind of engineering.

Here's the detail that separates this from most AI math claims flooding social media right now: doubleAI formalized the full proof in Lean, the proof assistant mathematicians use to verify logic mechanically, symbol by symbol, with no room for a model to bluff its way past a gap. That's not peer review. But it's a much harder bar than a plausible-sounding PDF. Any mathematician with Lean installed can go check the proof's logical steps today rather than take the company's word for it.

Compare that to the mess OpenAI is still cleaning up. In September, OpenAI said an internal model had solved a piece of the Navier-Stokes problem, one of the six unsolved Millennium Prize problems, in 88 hours using roughly 10,000 AI agents. NYU mathematician Tristan Buckmaster accused the company of drawing on his own unpublished research, which he says was sitting inside OpenAI's Codex product while he and collaborator Alpöge worked the same approach for nearly a year. The Clay Mathematics Institute still hasn't accepted the proof. Fortune reported the episode has left mathematicians openly questioning whether OpenAI can be trusted with credit attribution at all. doubleAI's quieter, Lean-verified, dollar-figure-attached approach reads almost like a direct rebuttal to that fiasco, intentional or not.

doubleAI is the newer venture from Amnon Shashua, the Mobileye co-founder and Hebrew University computer scientist who has spent two decades building and selling AI companies. Time named him among the 100 most influential people in AI. His pitch for doubleAI is sometimes framed internally as building "artificial expert intelligence." It's narrower than a general chatbot: train systems to operate as working specialists in domains like mathematics, where the output is either correct or it isn't, rather than systems optimized to sound convincing across any topic you throw at them.

That framing is also the honest caveat here. Nothing about this result has gone through peer review yet, and extremal graph theory is a field with a small number of experts who will need time to pick the construction apart, Lean formalization or not. A formal proof checker confirms the logic is internally consistent. It doesn't confirm the theorem is stated the way the field actually cares about, or that the construction is genuinely new rather than a dressed-up version of something already known. Treat the "first improvement in 38 years" framing as doubleAI's claim until independent mathematicians weigh in publicly.

Still, the $2,000 figure is the detail worth sitting with. A problem that resisted some of the sharpest minds in combinatorics for nearly four decades reportedly got moved by a system that cost less than a decent laptop to run for one attempt. Whether or not this particular proof survives scrutiny, that price tag is the real story: it's a preview of what happens to the economics of mathematical research once the bottleneck stops being human hours and starts being compute credits.

Also read: Anthropic Is Now Paying Subscribers to Stay as Rivals Close the Gap • TSMC posts record profit as AI chip demand defies market debt fears • Andreessen Horowitz guts its own recruiting team, a tell on AI and jobs

This article is posted in AI News, check it out for more related stories.