On the sign of a trigonometric expression
Résumé
We propose a set of simple and fast algorithms for evaluating and using trigonometric
expressions in the form $F=\sum_{k=0}^df_k\cos k\frac{\pi}{n}$,
$f_k\in\ZZ$, $d0}$:
computing the sign of such an expression,
evaluating it numerically and computing its minimal polynomial
in $\QQ[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 \frac{\pi}{n}$ in $\tcO(n_0^2)$ bit operations
with $n_0 \leq n$ is the odd squarefree part of $n$.
Within such a framework, we can decide if $F=0$ in $\tcO(d(\tau+d))$
bit operations, compute the sign of $F$ in $\tcO(d^2\tau)$ bit
operations and compute the minimal polynomial of $F$
in $\tcO(n^3\tau)$ bit operations, where $\tau$ denotes the maximum bitsize of the $f_k$'s.