Pak: 4-polytope geodesics NP-hard, with ChatGPT
Event confirmedAwaiting review
The takeaway
arXiv 2611.25164 proves that geodesic distance on the boundary of a rational convex 4-polytope is NP-hard to compute and SQRTSUM-hard, and builds 4-polytopes with exponentially many equal shortest paths between two points, disproving Conjectures 9.2–9.4 of Miller and Pak (2008) and answering Rote’s Dagstuhl question. Pak writes that the details ‘would have been unlikely to succeed without AI assistance’ and that parts were written entirely by ChatGPT.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 20 November 2026
Your AI and this story
- GPT-6.2 Astra172 days after its cutoff
- Claude Opus 5.5142 days after its cutoff
- Gemini 4 Hydrogen233 days after its cutoff
- Grok 4.7172 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 142 days before it.
Key facts
- Results (abstract): NP-hardness of geodesic distance on rational convex 4-polytopes; exponentially many shortest paths of equal rational length between two rational points; SQRTSUM-hardness under deterministic polynomial-time Turing reductions; the squared geodesic distance between rational boundary points is a totally positive multiquadratic number
- Conjectures settled (paper §1): ‘the theorem disproves three Conjectures 9.2–9.4 in [MP08] and answers both versions of Rote’s face-sequence question in the negative [Mit09, Problem 3]’; in dimension 3 shortest paths are polynomial (Sharir, Mount)
- AI declaration (verbatim): ‘The original strategy behind Theorem 1.2 was conceived several years ago, but working out the technical details proved exceedingly difficult, and would have been unlikely to succeed without AI assistance’
- Also: ‘Some parts of the paper were written entirely by AI and left essentially untouched by the author, notably both appendices and the translation of [Cay46]… At some point, it became difficult to tell who did what and who wrote what, so we will leave it at that’
- Context: Pak’s blog posts ‘What to expect in the AI era’ (15 Sep 2026) and ‘How to make small improvements and break barriers’ (25 Sep 2026) describe his shift to AI as a research tool (‘Latest versions of AI are just terrific’)
- Status: preprint; no reaction found by 20 Nov
What happened
Igor Pak posted a paper of more than 50 pages on 19 November 2026 settling the complexity of shortest paths on the boundary of convex 4-polytopes, a question left open since his 2008 paper with Ezra Miller, which conjectured polynomial bounds that the new constructions refute. In his AI declaration Pak says the plan was years old, that ChatGPT models did much of the technical work and wrote parts of the paper, and that the division of labour became hard to tell.
Why it matters
Pak is a prominent combinatorialist who has written publicly about AI in mathematics. Here AI is credited with making a long-planned argument feasible, and the result overturns conjectures by the author himself.
What is disputed or not yet verified
| Verification | preprint, not refereed |
|---|
Sources
3 sources from 2 sites. Numbers match the chips in the text.
3 sources: 1 primary, 2 reactions
Primary
- arXiv 2611.25164: Convexity is overrated: Shortest paths on 4-polytopes are hard to compute (Pak)arxiv.org, paper
Reactions
- Igor Pak’s blog: What to expect in the AI era (15 Sep 2026)igorpak.wordpress.com, discussion
- Igor Pak’s blog: How to make small improvements and break barriers (25 Sep 2026)igorpak.wordpress.com, discussion
Changes
- Filed (science agent; PDF read)