Function: thue
Section: polynomials
C-Name: thue
Prototype: GGDG
Help: thue(tnf,a,{sol}): solve the equation P(x,y)=a, where tnf was created
 with thueinit(P), and sol, if present, contains the solutions of Norm(x)=a
 modulo units in the number field defined by P. If tnf was computed without
 assuming GRH (flag 1 in thueinit), the result is unconditional. If tnf is a
 polynomial, compute thue(thueinit(P,0), a).
Doc: returns all solutions of the equation
 $P(x,y)=a$ in integers $x$ and $y$, where \var{tnf} was created with
 $\kbd{thueinit}(P)$. If present, \var{sol} must contain the solutions of
 $\Norm(x)=a$ modulo units of positive norm in the number field
 defined by $P$ (as computed by \kbd{bnfisintnorm}). If there are infinitely
 many solutions, an error is issued.

 It is allowed to input directly the polynomial $P$ instead of a \var{tnf},
 in which case, the function first performs \kbd{thueinit(P,0)}. This is
 very wasteful if more than one value of $a$ is required.

 If \var{tnf} was computed without assuming GRH (flag $1$ in \tet{thueinit}),
 then the result is unconditional. Otherwise, it depends in principle of the
 truth of the GRH, but may still be unconditionally correct in some
 favorable cases. The result is conditional on the GRH if
 $a\neq \pm 1$ and $P$ has a single irreducible rational factor, whose
 attached tentative class number $h$ and regulator $R$ (as computed
 assuming the GRH) satisfy

 \item $h > 1$,

 \item $R/0.2 > 1.5$.

 Here's how to solve the Thue equation $x^{13} - 5y^{13} = - 4$:
 \bprog
 ? tnf = thueinit(x^13 - 5);
 ? thue(tnf, -4)
 %1 = [[1, 1]]
 @eprog\noindent In this case, one checks that \kbd{bnfinit(x\pow13 -5).no}
 is $1$. Hence, the only solution is $(x,y) = (1,1)$ and the result is
 unconditional. On the other hand:
 \bprog
 ? P = x^3-2*x^2+3*x-17; tnf = thueinit(P);
 ? thue(tnf, -15)
 %2 = [[1, 1]]  \\ a priori conditional on the GRH.
 ? K = bnfinit(P); K.no
 %3 = 3
 ? K.reg
 %4 = 2.8682185139262873674706034475498755834
 @eprog
 This time the result is conditional. All results computed using this
 particular \var{tnf} are likewise conditional, \emph{except} for a right-hand
 side of $\pm 1$.
 The above result is in fact correct, so we did not just disprove the GRH:
 \bprog
 ? tnf = thueinit(x^3-2*x^2+3*x-17, 1 /*unconditional*/);
 ? thue(tnf, -15)
 %4 = [[1, 1]]
 @eprog
 Note that reducible or non-monic polynomials are allowed:
 \bprog
 ? tnf = thueinit((2*x+1)^5 * (4*x^3-2*x^2+3*x-17), 1);
 ? thue(tnf, 128)
 %2 = [[-1, 0], [1, 0]]
 @eprog\noindent Reducible polynomials are in fact much easier to handle.

 \misctitle{Note} When $P$ is irreducible without a real root, the default
 strategy is to use brute force enumeration in time $|a|^{1/\deg P}$ and
 avoid computing a touch \var{bnf} attached to $P$, see \kbd{thueinit}.
 Besides reusing a quantity you might need for other purposes, the
 default argument \emph{sol} can also be used to use a different strategy
 and prove that there are no solutions; of course you need to compute a
 \var{bnf} on you own to obtain \emph{sol}. If there \emph{are} solutions
 this won't help unless $P$ is quadratic, since the enumeration will be
 performed in any case.
