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

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?

-
Numeric approximation via N[algnum,digits] is guaranteed in the sense that it can tell you if a number is not zero. If it gives a result with no accuracy (because it is dealing with a zero or did not have sufficient precision to determine otherwise) then the test is inconclusive. So there's no incorrect case. Maybe then a next step would be your PossibleZeroQ route. –  Daniel Lichtblau Jan 24 '13 at 21:08
@Daniel I was always wondering, how accurate is Mathematica's precision tracking? I.e. if it gives me a result with a Precision of 10, does that guarantee that at least 10 digits are correct (assuming that there are no bugs in the software), or should I take it only as a guideline (an estimate)? –  Szabolcs Jan 25 '13 at 4:48
@Szabolcs it uses first-order error propagation assuming uncorrelated errors, as in this answer (in which I need to fix a mistake; Mathematica's implementation is actually fully correct to first order but I am not comparing like with like in my example). So, no, it isn't in any sense a guarantee, but rather an estimate--about as good as you'll get elsewhere, but by no means rigorous. For values with very little precision it'll probably be fairly inaccurate. –  Oleksandr R. Jan 25 '13 at 14:28
@Szabolcs Part I It depends on the computations being done. For addition/subtraction it is full accurate up to the granularity with which precision is recorded (machine double prec). For multiplication/division/powering it is a first order error model. Still very good in a sense, if you have more digits than the granularity of the precision field, insofar as second order error will be at most comparable to the "error error" from having discrete gradations in the precision. For other computations it will depend on method used both to compute and to estimate error. –  Daniel Lichtblau Jan 25 '13 at 15:08
@Szabolcs Part II More detail can be found in "Precise numerical computation" by Sofroniou and Spaletta. J. Log. Algebr. Program. 64(1): 113-134 (2005) –  Daniel Lichtblau Jan 25 '13 at 15:13

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.

-
Help > Documentation > PossibleZeroQ > Details item 2: "With the setting Method->"ExactAlgebraics", PossibleZeroQ will use exact guaranteed methods in the case of explicit algebraic numbers." Your example with the cosine terms does not give explicit algebraic numbers. Ergo no foul was committed by PossibleZeroQ. The last erxample is probably further removed from algebraics in the sense that quite possibly the input cannot be expressed as such even in theory. –  Daniel Lichtblau Jan 24 '13 at 21:42
@DanielLichtblau One can easily verify that Cos[2(6 - k)π/11] for k in {1,2,3,4,5} are algebraic numbers even though they are not explicit. x1 is 0 while the first RootSum and the second one probably are not algebraic numbers. –  Artes Jan 24 '13 at 22:08
Yes, those are (nonexplicit) algebraic numbers. I think I had implicitly implied that. (I guess I could have explicitly explied it.) Anyway, does not change the situation: the ExactAlgebraics method setting will be of no avail to PZQ. –  Daniel Lichtblau Jan 24 '13 at 22:15
@DanielLichtblau PossibleZeroQ[ x1, Method -> "ExactAlgebraics"] works well here, I was mislead because it is not Listable using it this way Table[...]// PossibleZeroQ[#, Method -> "ExactAlgebraics"] &. Thanks for drawing my attention to it. I have to update my answer. –  Artes Jan 24 '13 at 22:23
I'm surprised. Of course it's always a pleasant surprise when something works more generally than what's documented. –  Daniel Lichtblau Jan 24 '13 at 22:31