5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ PossibleZeroQ might be of some help. $\endgroup$
    – Spawn1701D
    Jun 5, 2013 at 19:46
  • $\begingroup$ Consider MemberQ[{Sqrt[2], Sqrt[3], Sin[\[Pi]/5], GoldenRatio, Root[#^3 - 2 &, 1]}, x_ /; RootReduce[x - 2^(1/3)] == 0]... $\endgroup$
    – J. M.'s persistent exhaustion ♦
    Jun 5, 2013 at 19:47
  • $\begingroup$ 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 $\endgroup$
    – Artes
    Jun 5, 2013 at 21:42

2 Answers 2

Reset to default
4
$\begingroup$

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[3] is an element of 

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

ContainsAlgebraicQ[ list, 1 + Sqrt[3]]

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
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Vladimir Reshetnikov
    Jun 6, 2013 at 1:32
  • $\begingroup$ 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. $\endgroup$
    – Artes
    Jun 6, 2013 at 9:54
1
$\begingroup$

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[[1]]]]]]

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.