Most efficient way to determine conclusively whether an algebraic number is zero

Question

Let x be an algebraic number of unspecified degree, expressed using arithmetic, rational powers, and algebraic integers (edit: Root[...] constructs). I would like to test conclusively whether it is zero.

I don't know whether any of the following are guaranteed to work:

x==0
Simplify[x]==0
FullSimplify[x]==0
PossibleZeroQ[x,Method->"ExactAlgebraics"]

The following should work, but seems unlikely to be efficient:

MinimalPolynomial[x][y]===y

I don't want to use numerical approximation unless the answer is guaranteed to be correct.

Do any of the first four lines above guarantee a correct answer?

What is the best way to perform this test in Mathematica?

Answer 1

Sometimes the only conclusive way of the four methods considered in the question can be PossibleZeroQ[ x, Method->"ExactAlgebraics"], it appears to be the most efficient as well. Dealing with explicitly algebraic numbers in almost all tests it is faster than FullSimplify. The main reason for this issue seems to be that FullSimplify is assumed to work with special functions, transcendental numbers and so on, thus there is a broader range of possible transformations while the option Method->"ExactAlgebraics" restricts to specific polynomial (algebraic) transformations. Moreover FullSimplify being able to transform given expressions involes drawbacks with respect to efficiency comparing it to PossibleZeroQ only performing tests yielding two values : True or False.

Explicit algebraic numbers

At first we need at least a few algebraic numbers i.e. roots of univariate non-zero polynomials with rational coefficients which are not explictly zero. We can provide a desired list of algebraic numbers using RootReduce to any nested radicals.

{x1, x2, x3, x4, x5, x6} = 
{
 (Sqrt[2] + Sqrt[3] + Sqrt[6] + 3)/Sqrt[5 + 2 Sqrt[6]] - 1 - Sqrt[3], 

 (-72 (1 - I Sqrt[3]))^(1/4) - 3 - I Sqrt[3], 

 Root[1 + #1^4 &, 4]
 - ((7 - 2I)/(1 + I Sqrt[2]) + (4 + 14I)/(Sqrt[2] + 2I) - 8 + 2I)^(1/4),

 ((1 - 5 I)/(1 + I) - 5 (1 + 2 I)/(2 - I) + 2)^(1/3) - Root[16 - 4 #1^2 + #1^4 &, 3],

 ((-2 + 2 Sqrt[3] I)/(2 + I Sqrt[5]) - 5 (Sqrt[3] + I)/(2 Sqrt[5] + 5 I))^(1/4) 
 - Root[4 + 2 #1^4 + #1^8 &, 8],

 - Root[ 65536 + 16384 #1^2 - 1024 #1^6 - 256 #1^8 - 64 #1^10 + 4 #1^14 + #1^16 &, 15] 
 + (512 (1 - I Sqrt[3]))^(1/10) };

We do not test the first two ways (i.e. x == 0 and Simplify[x] == 0) since they certainly cannot guarantee that an algebraic number is zero e.g. we can check it with x == x1. One can see that neither x1 == 0 nor Simplify[x1] == 0 yield any constructive answers. While the other two methods work well.

Let's define a testing function :

rT[x_] := 
  Module[{a, b},
          a = AbsoluteTiming[ PossibleZeroQ[x, Method -> "ExactAlgebraics"]];
          b = AbsoluteTiming[ FullSimplify[x] == 0];
          If[ Last[a] ~ And ~ Last[b], First[a]/First[b]] ]

and it yields :

rT /@ {x1, x2, x3, x4, x5, x6} // Column

0.01111
0.1364
0.455
0.1667
1.222
0.48927   

when we quit the kernel and try a twin function (reveresd the order of evaluation) :

rT1[x_] := 
  Module[{a, b},
          b = AbsoluteTiming[ FullSimplify[x] == 0]; 
          a = AbsoluteTiming[ PossibleZeroQ[x, Method -> "ExactAlgebraics"]];
          If[ Last[a] ~ And ~Last[b], First[a]/First[b]] ]

we can see even much better ratios :

rT1 /@ {x1, x2, x3, x4, x5, x6} // Column

0.00448
0.0435
0.364
0.0769
0.667
0.41071    

Non-explicit algebraics

Let's consider another example (see How to get exact roots of this polynomial ?) where the numbers Cos[2 (6 - k) π/11] for k ∈ Range[5] are not explicitely algebraic, but Mathematica simply decides they are indeed algebraic.

And @@ FullSimplify @ Table[ Cos[2 (6 - k) π/11] ∈ Algebraics, {k, 5}]

 True

And @@ ( PossibleZeroQ[#, Method -> "ExactAlgebraics"]& /@ 
         Table[ Root[1 + 6 #1 - 12 #1^2 - 32 #1^3 + 16 #1^4 + 32 #1^5 &, k] -
                Cos[2 (6 - k) π/11],  {k, 5}])

 True

however FullSimplify[Table[...]] is not sufficient here even though we could prove that numbers are zero with RootReduce. One should point out that using options in FullSimplify we could prove as well that the above algebraics are zeros but in general it is difficult to guess which option (what ComplexityFunction or TransformationFunctions) can be helpful.

Let's consider the last example :

xa = RootSum[ 3 - 2 #1 + #1^7 &, (PolyGamma[0, -#1] #1)/(-2 + 7 #1^6) &];
xb = RootSum[2 + 5 #1 + 21 #1^2 + 35 #1^3 + 35 #1^4 + 21 #1^5 + 7 #1^6 + #1^7 &, 
                (PolyGamma[0, -#1] + PolyGamma[0, -#1] #1)/(5 + 42 #1 + 105 #1^2 
                  + 140 #1^3 + 105 #1^4 + 42 #1^5 + 7 #1^6) &];
x = xa - xb;

We can't prove with Mathematica whether xa and xb are algebraic numbers.

PossibleZeroQ[ x1, Method -> "ExactAlgebraics"]

 PossibleZeroQ::ztest1: Unable to decide whether numeric quantity 
RootSum[3-2 #1+#1^7&,(PolyGamma[0,-#1] #1)/(-2+7 Power[<<2>>])&] - RootSum[2+5 #1+...])&]
 is equal to zero. Assuming it is. >>

  True

We can see that PossibleZeroQ is not powerful enough to yield a definitive answer but FullSimplify cannot do it at all.
Nonetheless one can prove that x1 is indeed 0.

To sum up PossibleZeroQ[ x, Method -> "ExactAlgebraics"] is clearly faster than FullSimplify as well as more connvenient and universal in tests. However the latter can simplify expressions while the former one cannot.