What was already known
Shallit and Sorenson’s 1994 paper posed the sum-of-squares statement as a conjecture at the end of Section 6. The project formalizes their earlier proved results separately and adds the minimizer proof and uniqueness. Its limited literature search did not establish historical priority.
AI involvement
The project states that GPT-6 Astra wrote the Lean definitions, statements and proofs; Jason Davies selected the source paper and directed the work. The sum-of-squares conjecture has no supplied proof in that paper, and the project explicitly identifies its proof as new to this development. Claude Opus 5.5 packaged and refactored the formalization. This supports AI-led proof development, with human direction retained.
Importance
Supplies a mechanically checked proof of a specific extremal-input property of an established GCD algorithm.
Limitations
Historical priority has not been established, and no independent human proof review is reported. The printed recurrence gives denominators of convergents to √3 despite the older paper’s numerator wording. Empirical hardware timing and average iteration counts are outside this theorem.
Technical verification
The exact pinned challenge states both the minimizer theorem and its uniqueness for n≥2, with positive ordered inputs and the specified iteration rule. The versioned Palomar record and successful checking run report protected comparison and Lean, NanoDa and con-ron kernel checks under only the three standard axioms.
Formal checking
The exact pinned challenge states both the minimizer theorem and its uniqueness for n≥2, with positive ordered inputs and the specified iteration rule. The versioned Palomar record and successful checking run report protected comparison and Lean, NanoDa and con-ron kernel checks under only the three standard axioms.
- Checker
- Palomar: Lean, NanoDa and con-ron
- Scope
- For each n≥2, among ordered positive integer inputs u≥v>0 taking exactly n iterations of the Shallit–Sorenson left-shift binary GCD algorithm, u²+v² has a unique minimum at (p[n−1],p[n−2]). Here p[0]=1, p[1]=3, and p[j+2]=p[j+1]+p[j] for even j, or 2p[j+1]+p[j] for odd j.
- Basis
- Reported by the linked checker
- Check date
- 2026-10-22
Checking a formal statement does not establish that it matches the original problem.
Human understanding
Few is the default when evidence for a higher level is insufficient. The source documents model-produced proofs and no independent human review. A named human explanation of the central minimization argument is not established; Few is the documentation default.
Correction and publication history
Added the reviewed, scoped AI contribution with its prior work and checking limits.
Read this published revision