# How to check an algebraic number for membership in a list

I need to check an algebraic number for membership in a list of algebraic numbers. The numbers can be expressed in different forms (combinations of radicals, Root objects, trig functions), but the check should be exact. Now I use the following code:

ContainsAlgebraicQ[list_, a_] :=
MatchQ[Intersection[ list, {a}, SameTest -> (MinimalPolynomial[#1 - #2] === (#&) &)], {_}]


but in some cases evaluation of MinimalPolynomial takes significant time, although I only want to check the difference for zero. Is there a better approach for my task?

• PossibleZeroQ might be of some help. Jun 5, 2013 at 19:46
• Consider MemberQ[{Sqrt, Sqrt, Sin[\[Pi]/5], GoldenRatio, Root[#^3 - 2 &, 1]}, x_ /; RootReduce[x - 2^(1/3)] == 0]... Jun 5, 2013 at 19:47
• I'd do this with PossibleZeroQ[ # - a, "ExactAlgebraics"]@list, or just MemberQ[PossibleZeroQ[ #, Method -> "ExactAlgebraics"]& @ list, True]. This post is closely related: Most efficient way to determine conclusively whether an algebraic number is zero Jun 5, 2013 at 21:42

PossibleZeroQ[ #, Method -> "ExactAlgebraics"] provides the most efficient and exact test whether two algebraics are equal, (see e.g. Most efficient way to determine conclusively whether an algebraic number is zero for some benchmarks). It is Listable so we can define the following function:

ContainsAlgebraicQ[list_, a_] :=
MemberQ[PossibleZeroQ[list - a, Method -> "ExactAlgebraics"], True]


E.g. check if 1 + Sqrt is an element of

list = { Root[4 + 2 #1^4 + #1^8 &, 8],
(Sqrt + Sqrt + Sqrt + 3)/Sqrt[5 + 2 Sqrt],
((7 - 2 I)/(1 + I Sqrt) + (4 + 14 I)/(Sqrt + 2 I) - 8 + 2 I)^(1/4) };

ContainsAlgebraicQ[ list, 1 + Sqrt]

True


but

ContainsAlgebraicQ[ list, Root[4 + 2 #1^4 + #1^8 &, 7]]

False


and of course

ContainsAlgebraicQ[ list, Root[4 + 2 #1^4 + #1^8 &, 8]]

True

• Thanks! Based on my observations of how this code works, I assume that trig functions of rational multiples of π are not considered explicit algebraics by Mathematica. So I added a step that invokes RootReduce on expressions containing any trig functions before passing them to PossibleZeroQ. Please let me know if you are aware of a better approach. Jun 6, 2013 at 1:32
• I think you need not to use RootReduce before PossibleZeroQ. Though Daniel Lichtblau has been surprised that PossibleZeroQ[ #, Method -> "ExactAlgebraics"]& worked for non-explicit algebraics. But for a more reliable approach it might be safer. Jun 6, 2013 at 9:54

If list has sufficiently many repeated subexpressions, it becomes efficient to convert the elements to explicit algebraic numbers in a common number field.

list=ToNumberField[list,All]


Performance testing suggests that ToNumberField memoizes evaluations of subexpressions. Evaluation is fast when the input is an algebraic combination of previously evaluated subexpressions.

(* all elements of list must be explicit algebraic numbers in a common number field *)
ContainsAlgebraicQ[{},a_,extension_]= False
ContainsAlgebraicQ[list_,a_,extension_]:=
Quiet[MemberQ[list,ToNumberField[a,AlgebraicNumberPolynomial[list[]]]]]


Here, Quiet suppresses a message that occurs when a is not in the number field generated by extension. I'm not sure what performance is like in this case; your application may allow better options for choice of extension.