The logarithmic spiral is optimal for shoreline search (Baeza-Yates–Culberson–Rawlins conjecture)
A ship starts at a point of the plane and moves at unit speed; it must reach an unknown straight shoreline, of which neither the distance nor the direction is known. The competitive ratio of a search path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and Rawlins proposed a logarithmic spiral, with ratio , and conjectured that it is optimal. Is that the smallest competitive ratio any path can achieve?
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Computation
- Field
- Search theory
- Posed by
- Baeza-Yates, Culberson and Rawlins, "Searching in the plane" (1993)
- Year posed
- 1993
- Years open
- 33y
- Solved
- 2026-09-21
- Model
- GPT 6 Astra, Claude Fable 5.1, Claude Opus 5
- Vendor
- OpenAI; Anthropic
- Collaborators
- Alexander Temerev
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Every search path has competitive ratio at least , so the logarithmic spiral is optimal and the optimal ratio is exactly . Paths are arbitrary: the distance from the start and the polar angle may both decrease. The proof is computer-assisted: a reduction to a three-state relaxed control problem, closed by an explicit storage function whose dissipation inequalities are verified in interval arithmetic and are tight only at the spiral.
What the AI did
Per the paper's title footnote, large language models were used throughout the work: to find the reduction, to search for the storage function, and to write the accompanying Lean 4 development and the two verifiers. Section 10 of the paper states what is machine-checked and what is not.
Verification
Kept from the submission, which is accurate, with the checks named. Not independently reviewed. The storage function's dissipation inequalities are verified in Arb ball arithmetic, about 10^6 boxes, with an exact jet and an interval Hessian at the spiral, by two independent implementations. Eight Lean 4 modules carry no sorry and depend only on propext, Classical.choice and Quot.sound, and check lemmas of the reduction, but the argument is NOT formalised end to end: Section 10 of the paper lists what is machine-checked and what is not, and the entry does not claim more. Checked here on 30 September 2026: the arXiv abstract states the ratio as 13.8111351794611... and the paths as arbitrary, with both the radius and the polar angle allowed to decrease, which is the general case the conjecture is about. The ancillary directory holding the Lean modules, the two verifiers and the certified coefficient table was not rebuilt here.
Source
- PaperarXiv preprint
Submitted by FrostyStoat805 on