[GAP Forum] Thue's Lemma

[Sergey Shpectorov]

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-bounces at gap-system.org [forum-bounces at gap-system.org] on behalf of Juergen Mueller [juergen.mueller at math.rwth-aachen.de]
Sent: Saturday, July 30, 2016 10:20 AM
To: forum at 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 at mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum