On the Sign of a Trigonometric Expression

We propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the form F=Σ_k^d=0fkΕZd‹ n, for a fixed nin>0:ΕZ > 0: computing the sign of such an expression, evaluating it numerically and computing its minimal polynomial in Q[x]. As critical byproducts, we propose simple and efficient algorithms for performing arithmetic operations (multiplication, division, gcd) on polynomials expressed in a Chebyshev basis (with the same bit-complexity as in the monomial basis) and for computing the minimal polynomial of 2 cos π over n in Õ(n₀²) bit operations with n₀ ≤ n is the odd squarefree part of n. Within such a framework, we can decide if F=0 in Õ(d(τ+d)) bit operations, compute the sign of F in Õ(d²τ) bit operations and compute the minimal polynomial of F in Õ(n³τ) bit operations, where τ denotes the maximum bitsize of the f ^k's.