Remainder-call complexity of uniform GCD processes
Follow the latest progress by email.
How many remainder operations are intrinsically needed to derive gcd(a,b) when previously computed values may be reused and the next operands may be chosen freely? This uniform-process model does not charge for finding those choices.
Why it matters and what counts as progress
Why it matters: A short derivation would limit remainder-only lower-bound frameworks without automatically yielding a fast executable gcd algorithm.
What counts as progress: A uniform sublogarithmic derivation bound, such as (6+o(1))log₂a/log₂log₂a, or a lower bound for this same unrestricted-choice process model.
How the problem developed
- 2004 · Conjecture [1]
Lou van den Dries and Yiannis N. Moschovakis Formulated logarithmic worst-case optimality for executable remainder-oracle gcd algorithms; this algorithmic conjecture is related to, but distinct from, later intrinsic-process lower bounds.
- 2012 · Conjecture [2]
Yiannis N. Moschovakis Formulated logarithmic intrinsic lower bounds for uniform remainder-based gcd processes; the 2026 paper identifies this as its target, distinct from the algorithmic conjecture.
- 23 Oct 2026 · Reported claim [2]
Jason Davies and GPT-6 Astra The manuscript claims every positive pair a ≥ b has a uniform remainder-only derivation using at most (6+o(1))log₂(a)/log₂log₂(a) calls, refuting the cited intrinsic-complexity conjectures.
AI contribution
The Euclidean algorithm is not optimal among uniform processes
For every positive integer pair a≥b, gcd(a,b) has a remainder-only derivation using at most (6+o(1)) log₂(a)/log₂log₂(a) remainder calls, uniformly in b. Previously computed values may be reused and the choice of operands is free. This refutes Moschovakis’s stated uniform-process lower-bound conjectures, not the Main Conjecture for algorithms.
Sources
Website timeline
Publication dates and editorial changes.
The Euclidean algorithm is not optimal among uniform processes