Dear Juergen, Thanks for providing these details! I certainly have no first-hand knowledge of the origin of this fact. I found it attributed to Thue on Wikipedia, and am just very happy that the algorithm is available in GAP!
Best, Sergey ________________________________________ From: forum-boun...@gap-system.org [forum-boun...@gap-system.org] on behalf of Juergen Mueller [juergen.muel...@math.rwth-aachen.de] Sent: Saturday, July 30, 2016 10:20 AM To: fo...@gap-system.org Subject: Re: [GAP Forum] Thue's Lemma Dear Sergey, dear Frank, just a short additional comment on this: Actually, I did not know either that this Lemma has a name attached to it, in my eyes it was part of mathematical folklore. Anyway, the standard algorithmic solution (which is the one Frank has implemented, as far as I see) is also known as Gauss's algorithm finding a shortest vector in a lattice of rank 2 in Euclidean space (applied to the lattice spanned by [n,0] and [x,1]). As such, it as a variant of the Euclidean algorithm in Z, and a predecessor of the LLL algorithm. And indeed, as it is essentially the Euclidean algorithm running, this works efficiently for HUGE numbers, as you have observed. For more details, see for example Algorithm 1.3.14 in Cohen's book `A course in computational algebraic number theory'. Best wishes, Jürgen (Müller) _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
