[GAP Forum] Checking whether given number is an algebraic number of degree N

[Bill Allombert]

On Wed, Oct 21, 2009 at 12:03:15AM +0200, Michał Olejnik wrote:
> Hello,
> 
> I'm a beginner to GAP, so forgive me if my question is trivial.
> 
> I would like to know if there is an easy way in GAP to write a function
> which will check wheter passed number is an algebraic number of degree N. Is
> something like that available in GAP or one of the extending packages?

How do you input your number ? GAP has no floating point numbers, so
in that case it is probably simpler to use the algdep function of PARI/GP,
for example:
? algdep(cos(2*Pi/7),3)
%1 = 8*x^3 + 4*x^2 - 4*x - 1

Now, GAP has LLL, so it is possible to write an algdep routine for numbers
given by a rational approximation (which is what floating points numbers
are anyway) in GAP:

Algdep:= function(x,n,prec)
  local M,p,q,Q,qerr;
  p:=NumeratorRat(x);  q:=DenominatorRat(x);
  Q:=q^(n-1); qerr:=1/(q*prec);
  M:=IdentityMat(n+1);
  M[n+1]:=List([0..n],e->EuclideanQuotient(p^e*q^(n-e),Q)*qerr);
  return LLLReducedBasis(TransposedMat(M),"linearcomb").transformation[1];
end;

Algdep(x,n,prec) is looking for a polynomial of degree <=n whose root alpha
verify |alpha-x|<prec.

Examples:
Algdep(778085762274086750445/1247952668920125525979,3,10^-20);
[ -1, -4, 4, 8 ]
Algdep(1908304252230311410894/2155165470608815381879,6,10^-20);
[ -1, 6, 24, -32, -80, 32, 64 ]
Algdep(Fibonacci(101)/Fibonacci(100),2,10^-30);
[ -1, -1, 1 ]

Cheers,
Bill.