OpenAI's Sébastien Bubeck reports GPT-5.5-pro proved a conditional computational lower bound for the furthest-pair problem

(to be clear the great @wjmzbmr1 had already proved this result for a dimension growing sufficiently fast with n, the improvement is that now there is no condition besides d going to infinity with n)

Interestingly, the proof was discovered by ChatGPT 5.5 Pro entirely. It was a 20+ page proof, probably the longest of any AI-generated proofs I have seen so far. The proof was verified using Lean formalization through Aristotle along with manual verification.

Given a set of n points in d dimensions, the problems of finding the furthest pair and the closest pair require no explanation even to laymen. However, while finding the closest pair has a much more efficient algorithm,

.The starting point of the proof is the OpenAI breakthrough on the unit distance problem. We realized the techniques there could be useful for this problem, and indeed, they were.

the best-known algorithm for the furthest pair is sub-quadratic only when d is constant. We show that algorithm is essentially optimal, that is there is no subquadratic algorithm for further pair for super-constant dimension (under SETH).

@SebastienBubeck that is actually wild, the math behind this sounds super deep.