doubleAI’s ‘Double Agent’ claims explicit regular graphs of girth (8/5)·log n, beating the 4/3 constant of Margulis and Lubotzky–Phillips–Sarnak (1988)
Awaiting review
The takeaway
Amnon Shashua’s start-up doubleAI posted a 40-page paper credited only to its AI ‘Double Agent’: for every prime power q, explicit (q³+1)-regular graphs with girth ≥ (8/5)·log_{q³} n − O(1), improving the 4/3 constant that had stood since 1988. A Lean proof is posted; the company says it ran autonomously for under $2,000 of compute. Not peer-reviewed.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Peer-reviewed
- Importance
- 3 of 5
- Last verified
- 15 October 2026
Your AI and this story
- GPT-6 Astra159 days after its cutoff
- Claude Opus 5.598 days after its cutoff
- Gemini 4 Argon189 days after its cutoff
- Grok 4.7128 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 98 days before it.
Key facts
- Paper: ‘d-Regular Graphs of Girth 8/5 log_{d−1} n’, Double Agent, doubleAI, October 2026, 40 pages (doubleai.com/papers/girth85.pdf); Lean proof as a zip (doubleai.com/papers/girth85-lean.zip); no arXiv version found
- Abstract: ‘For every prime power q we construct an explicit infinite family of (q³+1)-regular graphs whose girth satisfies girth ≥ 8/5 log_{q³} n − O(1) … This improves the constant 4/3 of Margulis and of Lubotzky, Phillips and Sarnak, which has been the best known since 1988.’ Degrees: 9, 28, 65, … (q = 2, 3, 4, …)
- Method: quotients of the Bruhat–Tits tree of SU in four variables of Witt index one, by congruence subgroups of an arithmetic group from a degree-4 division algebra with an involution of the second kind; the girth bound ‘rests on a certificate’ bounding det(w − I) for congruence elements
- For one explicit family of 28-regular graphs the paper also proves a matching upper bound: girth = (8/5)·log₂₇ n + O(1)
- Company claims (Calcalist, 8 Oct; Startup Fortune, 15 Oct): ‘the first improvement in 38 years on a central problem in extremal graph theory’; produced autonomously, ‘No human steering the math’, for under $2,000 of compute. The paper lists no human authors and does not describe the process
- Startup Fortune notes that Lean checks logical consistency, not whether the theorem is stated as the field intends or whether the construction is new, and that the result is not peer-reviewed; Calcalist presents it as a company claim
- Reach: an HN submission of the PDF (7 Oct) drew 1 point; no expert reactions found as of 15 Oct
What happened
doubleAI, which so far had been known for its WarpSpeed GPU-kernel optimizer and the FormulaOne benchmark, posted a 40-page paper whose only listed author is its AI system, “Double Agent”. The paper builds explicit infinite families of regular graphs whose shortest cycle (girth) grows like (8/5)·log n. The previous record for explicit constructions, 4/3, came from the Ramanujan graphs of Margulis and of Lubotzky, Phillips and Sarnak in 1988. A Lean formalization is offered as a download. The company told Calcalist that the system worked autonomously for under $2,000 of compute.
We found the result through a 15 Oct Startup Fortune article in the news sweep, nine days after the announcement. There was no arXiv preprint, the HN post got no traction, and the company’s page has no human authors to search for.
Why it matters
High-girth regular graphs are used in coding theory (LDPC codes) and in expander constructions, and the 4/3 constant was a long-standing benchmark. If experts confirm the result, it is a solo AI result on a classic problem from a small company, outside the big US labs. Until then it remains a company claim, formally checked by the company’s own Lean files.
What is disputed or not yet verified
| Verification | Lean proof published by the company (not independently built by us); not peer-reviewed; no expert assessment yet |
|---|
Sources
5 sources from 3 sites. Numbers match the chips in the text.
5 sources: 3 primary, 2 press
Primary
- doubleAI: Advancing a decades-old problem in extremal graph theorydoubleai.com, official
- Paper (PDF): d-Regular Graphs of Girth 8/5 log_{d−1} ndoubleai.com, paper
- Lean proof (zip)doubleai.com, code
Press
Changes
- Filed (Startup Fortune; read the doubleAI paper PDF, research page and Calcalist)