Algorithms for Trigonometric Polynomials

Jamie Mulholland

Department of Mathematics University of British Columbia

Vancouver, B.C. Canada, V6T 1Z2

jmulholl@cecm.sfu.ca

Michael Monagan

Department of Mathematics Simon Fraser University Burnaby, B.C. Canada, V5A 1S6

monagan@cecm.sfu.ca

ABSTRACT

In this paper we present algorithms for simplifying ratios of trigonometric polynomials and algorithms for dividing, factoring and computing greatest common divisors of trigonometric polynomials, that is, polynomials in sin(x) and cos(x).

1. INTRODUCTION

Let s and c denote sin(x) and cos(x) respectively. We are interested in methods for simplifying ratios of trigonometric polynomials, that is, elements of the ring ℚ[s, c]/⟨s^{2}+c^{2}−1⟩. For example, we would like to make the simplification

\frac{(1 + c) s + 1 − c^{2}}{s − 2 c^{2} + c^{4} + 1} → \frac{1 + s + c}{(1 − c^{2}) s + 1} .

Such simplification problems occur naturally in engineering applications. They will also occur in any computation with trigonometric polynomials that assumes a field, for example, if Gaussian elimination were applied to a matrix of trigonometric polynomials.

One approach to this problem is to try to cancel out a greatest common divisor (GCD) from the numerator and denominator trigonometric polynomials. In the above example the simplified result was obtained by cancelling out the common divisor s. What makes this problem non-trivial is that the quotient ring ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ is not a unique factorization domain, thus GCDs are not unique in general. In our example the numerator trigonometric polynomial has the following two irreducible factorizations

(1 + c)s + 1 − c^{2} = s(1 + s + c) = (1 + c)(1 + s − c)

and the denominator polynomial the following two

(1 + s − 2c^{2} + c^{4}) = s(1 + s)(2 − s − c^{2})
= \frac{1}{2} (1 + s + c)(1 + s − c)(2 − s − c^{2}).

Thus we could also have cancelled out the common factor 1 + s + c or the common factor 1 + s − c.

The non-uniqueness of factorization in ℚ[s, c]/⟨s^{2} +c^{2} −1⟩ is pointed out by Trotter in [3] though no algorithms are given. In [2], Roach studies this problem in the context of indefinite integration of functions of sin(x) and cos(x). Roach’s method for simplifying ratios of trigonometric polynomials is simply to convert to complex exponentials, compute and cancel out the GCD in ℚ(i)[e] where e = e^{ix}, and then recover a trigonometric form for the simplified expression in ℚ(i)(e) by inverting the complex exponential map. Unfortunately this approach does not always work and the reason is subtle. When applied to our example one obtains (e − 1)(e + 1)(e + i) for the GCD in ℚ(i)[e] but this polynomial does not come from a trigonometric polynomial in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. The images of the common factors s, 1 + s − c and 1 + s + c have the factors (e − 1)(e + 1), (e − 1)(e + i) and (e + 1)(e + i) respectively.

In this paper we will show how to compute greatest common divisors of trigonometric polynomials in all cases. To do this we must first understand factorization in the ring ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. We study this in section 2. We show that ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ is an integral domain and how to do division in it. This facilitates algorithms like fraction-free Gaussian elimination. Next we characterize irreducibles in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ and show how to determine all distinct factorizations of a element of this ring. An application for factoring trigonometric polynomials would be solving equations involving trigonometric polynomials.

In section 3 we study how to simplify ratios of trigonometric polynomials, i.e. elements of the fraction field of ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. We define and show how to compute greatest common divisors in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ which gives one solution to the simplification problem, but, surprisingly, this does not always lead to the simplest result. We give a more direct approach which always yields the simplest result. The ability to simplify ratios of trigonometric polynomials to lowest terms means that algorithms which work over a field can be applied to trigonometric polynomials without “blowing up”.

2. DIVISION AND FACTORIZATION

To study trigonometric polynomials we consider the ring of polynomials ℚ[s, c] modulo s^{2} + c^{2} − 1 = 0.

Definition 1. Define the relation ≡ on ℚ[s, c] by p ≡ q ⇔ s^{2} + c^{2} − 1 | p − q.

It is well known that ≡ is an equivalence relation on ℚ[s, c]. For each p ∈ ℚ[s, c] the equivalence class [p] = {q ∈ ℚ[s, c] : p ≡ q}. When we speak of a trigonometric polynomial q we mean a representative of the equivalence class [q] in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩.

Definition 2. Define ϕ : ℚ[s, c] ⟶ ℚ[s, c] by ϕ(p) = p mod s^{2} + c^{2} − 1 where s^{2} is replaced by 1 − c^{2}.

Thus ϕ(p) is an element of the equivalence class [p] which is at most linear in s. The following lemma shows that it is unique.

Lemma 1. Let p ∈ ℚ[s, c]. Then ϕ(p) is the unique element in ℚ[s, c] of the form A(c)s + B(c) equivalent to p.

Proof: Clearly ϕ(p) is linear in s by definition and ϕ(p) ≡ p. Let q = A(c)s + B(c) such that q ≡ p. Write ϕ(p) = a(c)s + b(c). Then ϕ(p) ≡ q and so s^{2} + c^{2} − 1 | (A − a)s + (B − b). This is impossible in ℚ[s, c] unless A = a and B = b. ■

We now show that ℚ[s, c]/⟨s^{2} +c^{2} −1⟩ is an integral domain and identify units.

Definition 3 (Trigonometric polynomial degree). For p ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ we define the trigonometric degree of p to be TD(p) = deg_{s,c}(ϕ(p)).

Example: The polynomial p = s^{2} +c^{2} has total degree 2 in ℚ[s, c] but considered as a trigonometric polynomial it has trigonometric degree 0 since ϕ(p) = 1.

Lemma 2 (Trigonometric degree-sum formula). Let p, q ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. Then TD(pq) = TD(p) + TD(q).

Proof: Write ϕ(p) = A(c)s + B(c) and ϕ(q) = a(c)s + b(c). Let n_{1} = deg_{c}(A) + 1 , m_{1} = deg_{c}(B), n_{2} = deg_{c}(a) + 1 , and m_{2} = deg_{c}(b). Now

ϕ(ϕ(p)ϕ(q)) = (Ab + aB)s + (Bb + Aa − Aac^{2}).

We claim that

deg(ϕ(ϕ(p)ϕ(q))) = deg(ϕ(p)) + deg(ϕ(q)).

This is easy to verify except for the case when m_{1} = n_{1}, m_{2} = n_{2}. To determine deg(ϕ(ϕ(p)ϕ(q))) in this case we argue as follows. Let A(c) = ∑_{i=0}^{n_{1}−1} A_{i}c^{i}, B(c) = ∑_{i=0}^{m_{1}} B_{i}c^{i}, a(c) = ∑_{i=0}^{n_{2}−1} a_{i}c^{i}, and b(c) = ∑_{i=0}^{m_{2}} b_{i}c^{i}. The leading coefficient in Ab + aB is A_{n_{1}−1}b_{m_{2}} + a_{n_{2}−1}B_{m_{1}}, and the leading coefficient of Bb+Aa−Aac^{2} is B_{m_{1}}b_{m_{2}} −A_{n_{1}−1}a_{n_{2}−2}. If the claim were false then both these coefficients must be zero. The solutions of the system

{A_{n_{1}−1}b_{m_{2}} + a_{n_{2}−1}B_{m_{1}} = 0, B_{m_{1}}b_{m_{2}} − A_{n_{1}−1}a_{n_{2}−1} = 0}

are the two zero solutions

{A_{n_{1}−1} = 0, B_{m_{1}} = 0}, {a_{n_{2}−1} = 0, b_{m_{1}} = 0}

and the two complex solutions

{a_{n_{2}−1} = ±ib_{m_{2}}, A_{n_{1}−1} = ∓iB_{m_{1}}}.

The former contradict the degree of p and q respectively and the latter are not solutions in ℚ. Therefore deg(ϕ(ϕ(p)ϕ(q))) = n_{1} + m_{2} and the claim is true for this case.

Note that p ≡ ϕ(p), q ≡ ϕ(q), pq ≡ ϕ(pq) implies ϕ(p)ϕ(q) ≡ pq ≡ ϕ(pq). Therefore TD(ϕ(p)ϕ(q)) = deg(ϕ(pq)). Therefore

TD(pq) = deg(ϕ(pq))
= TD(ϕ(p)ϕ(q))
= deg(ϕ(ϕ(p)ϕ(q)))
= deg(ϕ(p)) + deg(ϕ(q))
= TD(p) + TD(q).  ■

It follows that ℚ[s, c]/⟨s^{2} +c^{2} −1⟩ has no zero divisors hence ℚ[s, c]/⟨s^{2} +c^{2} −1⟩ is an integral domain with units ℚ\{0}.

2.1 Tan-half substitution

To simplify ratios of trigonometric polynomials, and to study factorization in the ring ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ we will use the the tan-half substitution

sin(x) = \frac{2 tan(x/2)}{1 + tan(x/2)^{2}} , cos(x) = \frac{1 − tan(x/2)^{2}}{1 + tan(x/2)^{2}} .

For the rest of this paper we will denote tan(x/2) by t. This substitution converts trigonometric polynomials into polynomials in ℚ[t] divided by powers of (1 + t^{2}). We employ the tan half-angle substitution instead of the complex exponential mapping simply because it avoids computing in ℚ(i) which is more expensive than computing over ℚ, but otherwise the complex exponential mapping could be used.

Definition 4 (t-substitution). Define

ψ_{t} : ℚ[s, c] → ℚ(t) by ψ_{t}(p(s, c)) = p( \frac{2t}{1 + t^{2}} , \frac{1 − t^{2}}{1 + t^{2}} ).

We recall the following well known results.

Lemma 3. ψ_{t} : ℚ[s, c] ⟶ ℚ(t) is a ring morphism and the kernel of ψ_{t} is the principle ideal generated by s^{2} +c^{2} −1.

Lemma 4. Let p ∈ ℚ[s, c]/ < s^{2} + c^{2} − 1 > with TD(p) = d. Then ψ_{t}(p) = \frac{a(t)}{(1+t^{2})^{d}} where a(t) ∈ ℚ[t] such that deg_{t}(a) ≤ 2d and 1 + t^{2} ∤ a(t).

To make use of this ring morphism we need to be able to invert the t-substitution. We now show how to do this and give some results about the inversion. The inverse t-substitution given by t = \frac{1−c}{s} can be used to convert a rational polynomial in t of the correct form back into a trigonometric polynomial. Two questions arise: (i) What is the correct form? (ii) Does direct substitution of the formula for t always return a trigonometric polynomial? The second question is more involved then it seems. After making the t = \frac{1−c}{s} substitution we have a rational trigonometric polynomial and so to get a trigonometric polynomial we need to do trigonometric polynomial division. This is a problem in its own right. There are simple ways to do the division in this case but we will not consider them since we can answer both questions by cleverly making the inverse t-substitution using resultants. How we do this is illustrated in the following theorem and subsequent comments. However, first we must state the following useful lemma.

Lemma 5. Let a(t) = ∑_{i=0}^{2n} v_{i}t^{i} such that v_{2n} = ∑_{i=1}^{n}(−1)^{i+1}v_{2(n−i)} and v_{2n−1} = ∑_{i=1}^{n−1}(−1)^{i+1}v_{2(n−i)−1} then 1 + t^{2} | a(t).

Proof: Consider b(t) = ∑_{i=0}^{2n−2} b_{i}t^{i} where b_{i} = ∑_{k=0}^{i/2}(−1)^{k}v_{i−2k} if i even and b_{i} = ∑_{k=0}^{(i−1)/2}(−1)^{k}v_{i−2k} if i odd. We leave it to the reader to verify a(t) = (1 + t^{2}) · b(t). ■

Lemma 6. Let n ∈ ℕ. For each polynomial a(t) with 1 + t^{2} ∤ a(t) and deg_{t}(a) ≤ 2n, the resultant

res_{t}(a(t) − X(1 + t^{2})^{n}, st + (c − 1)) = p(s, c)X + q(s, c)

where p(s, c), q(s, c) ∈ ℚ[s, c]. Moreover, ϕ(p) = −2^{n}(1 − c)^{n} and ϕ(p)|ϕ(q) in ℚ[s, c] and TD(q(s, c)) = 2n.

Proof: Write a(t) = ∑_{i=0}^{2n} v_{i}t^{i}, where of course if deg_{t}(a) < 2n then v_{i} = 0 for i > deg_{t}(a(t)). The resultant in the lemma is the determinant of Sylvesters’ matrix

S = [\begin{matrix}v_{2n} − \binom{n}{0}X & v_{2n−1} & v_{2n−2} − \binom{n}{1}X & v_{2n−3} & … \\ s & c − 1 & 0 & 0 & … \\ 0 & s & c − 1 & 0 & … \\ 0 & 0 & s & c − 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}]

The reader can verify that det(S) = p(s, c)X + q(s, c) where ϕ(p(s, c)) = −2^{n}(1−c)^{n} and ϕ(q(s, c)) = (1−c)^{n}[∑_{i=0}^{n} v_{2(n−i)} (1 + c)^{i}(1 − c)^{n−i} + ∑_{i=0}^{n−1} v_{2(n−i)−1}s(1 + c)^{i}(1 − c)^{n−i−1}]. The only thing left to show is that TD(q(s, c)) = 2n, that is, deg_{s,c} ϕ(q(s, c)) = 2n. If the total degree of ϕ(q(s, c)) is < 2n then the both the coefficient of c^{n} and sc^{n} must be zero in the second factor of ϕ(q(s, c)). This means that v_{2n} = ∑_{i=1}^{n}(−1)^{i+1}v_{2(n−i)} and v_{2n−1} = ∑_{i=1}^{n−1}(−1)^{i+1}v_{2(n−i)−1}, and by Lemma 5 1 + t^{2} divides a(t). This is a contradiction. Therefore TD(q(s, c)) = 2n. ■

Theorem 1. Let n ∈ ℕ. Let a(t) be a polynomial such that 1 + t^{2} ∤ a(t) and deg_{t}(a) ≤ 2n. Then there exists a unique trigonometric polynomial â of trigonometric degree n such that ψ_{t}(â) = \frac{a(t)}{(1+t^{2})^{n}}.

Proof: From the previous lemma we have that

res_{t}(a(t) − X(1 + t^{2})^{n}, st + (c − 1)) = p(s, c)X + q(s, c)

where ϕ(p)|ϕ(q) in ℚ[s, c], TD(p) = n and TD(q) = 2n. Solving p(s, c)X + q(s, c) = 0 for X in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ we get

X = \frac{ϕ(q)}{ϕ(p)} ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩.

Now X ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ has trigonometric degree n and from the definition of the resultant we have

ψ_{t}(X) = \frac{a(t)}{(1 + t^{2})^{n}} .

To show uniqueness, let â, b̂ ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ such that ψ_{t}(â) = ψ_{t}(b̂) = \frac{a(t)}{(1+t^{2})^{n}}. Since ψ_{t} is a ring morphism then

ψ_{t}(â − b̂) = 0 so â − b̂ ∈ kerψ_{t} = ⟨s^{2} + c^{2} − 1⟩, thus â = b̂. ■

This theorem says that every rational polynomial of the form \frac{a(t)}{(1+t^{2})^{n}} where a ∈ ℚ[t], 1 + t^{2} ∤ a(t)and deg_{t}(a) ≤ 2n is the image under ψ_{t} of a trigonometric polynomial of degree n. In what follows we denote ψ_{t}^{−1}( \frac{a(t)}{(1+t^{2})^{n}}) = X(s, c), where X(s, c) is the unique polynomial discussed in the previous theorem.

2.2 Division in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩

The following theorem shows when one trigonometric polynomial divides another in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ and the proof shows how to compute the quotient.

Theorem 2. For a, b ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩

a|b ⇔ (i) TD(a) ≤ TD(b)
(ii) numer(ψ_{t}(a))|numer(ψ_{t}(b)) in ℚ[t]
(iii) deg(numer(ψ_{t}(b))) − deg(numer(ψ_{t}(a)))
≤ 2(TD(b) − TD(a))

Proof: (⇒) Let q be such that b = qa in ℚ[s, c]/⟨s^{2}+c^{2}−1⟩. Then ∃r ∈ ℚ[s, c] such that b = qa + r(s^{2} + c^{2} − 1) in ℚ[s, c]. By the trig degree-sum formula, Lemma 2, TD(b) = TD(q) + TD(a). Moreover,

ψ_{t}(b) = ψ_{t}(qa + r(s^{2} + c^{2} − 1))
= ψ_{t}(q)ψ_{t}(a) + ψ_{t}(r) · 0
= ψ_{t}(q)ψ_{t}(a).

Expanding this equation we have

\frac{numer(ψ_{t}(b))}{(1 + t^{2})^{d_{b}}} = \frac{numer(ψ_{t}(q))}{(1 + t^{2})^{d_{q}}} · \frac{numer(ψ_{t}(a))}{(1 + t^{2})^{d_{a}}}

where d_{x} = TD(x) for x = a, b, q. Since d_{b} = d_{q} + d_{a} then numer(ψ_{t}(b)) = numer(ψ_{t}(q)) · numer(ψ_{t}(a)). Moreover,

deg(numer(ψ_{t}(b))) − deg(numer(ψ_{t}(a)))

= deg(numer(ψ_{t}(q)))
≤ 2TD(q)
= 2(TD(b) − TD(a)).

This proves (⇒). For (⇐) suppose that the three conditions hold as stated in the theorem. Then numer(ψ_{t}(b)) = q(t) · numer(ψ_{t}(a)) for some q ∈ ℚ[t]. So

\frac{numer(ψ_{t}(b))}{(1 + t^{2})^{d_{b}}} = \frac{q(t)}{(1 + t^{2})^{d_{b}−d_{a}}} · \frac{numer(ψ_{t}(a))}{(1 + t^{2})^{d_{a}}} .

Since

deg_{t}(q) = deg(numer(ψ_{t}(b)) − deg(numer(ψ_{t}(a)))
≤ 2(TD(b) − TD(a)) from (ii),
= 2(d_{b} − d_{a})

we are guaranteed (by Theorem 1) that

q̂ = ψ_{t}^{−1}( \frac{q(t)}{(1 + t^{2})^{d_{b}−d_{a}}}) ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩

Therefore, a = q̂· b in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. ■

Corollary 1. Let p ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ such that TD(p) ≥ 1. If deg(numer(ψ_{t}(p))) ≤ 2TD(p)−2 then c+1|p.

Proof: Since ψ_{t}(c + 1) = \frac{2}{1+t^{2}} , then from the previous theorem we have

c + 1|p ⇔ (i) 1 ≤ TD(p)
(ii) 2|numer(ψ_{t}(p))
(iii) deg(numer(ψ_{t}(p))) ≤ 2(TD(p) − 1).

Since (i),(ii),(iii) are all true then c + 1|p. ■

2.3 Irreducibility in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩

In this section we will identify irreducibles in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. Since the units in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ are the nonzero rational numbers, this leads to the following definition of the irreducibles in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩.

Definition 5. A non-zero element p ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ is irreducible if

(a) p is not in ℚ (i.e. p is not a unit)

(b) whenever p = ab either a or b is in ℚ.

Theorem 3. Let p ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ such that p is not a unit (i.e. TD(p) ≥ 1),

(a) if TD(p) = 1 then p is irreducible.

(b) if TD(p) > 1 then p is irreducible ⇔

(i)  deg_{t}(numer(ψ_{t}(p))) ≥ 2TD(p) − 1,
(ii) numer(ψ_{t}(p)) is irreducible in ℚ[t] or

numer(ψ_{t}(p)) is a product of two irreducible polynomials in ℚ[t] each of odd degree.

Proof: If TD(p) = 1 then p is irreducible by the trig degreesum formula. Now suppose TD(p) ≥ 2. (⇒) Suppose that (i) or (ii) does not hold. If (i) does not hold then c + 1|p by Corollary 1, so p is reducible. So suppose (i) holds but (ii) does not hold, then we must have numer(ψ_{t}(p)) is reducible but is not the product of two irreducible polynomials in ℚ[t] of odd degree. Write

numer(ψ_{t}(p)) = q_{1}(t) · q_{2}(t),

for some q_{1}, q_{2} ∈ ℚ[t] such that deg(q_{1}), deg(q_{2}) ≥ 1, q_{1} irreducible and if q_{2} irreducible then deg(q_{1}), deg(q_{2}) cannot both be odd. Since (i) holds we have two case to consider, namely (1) deg_{t}(numer(ψ_{t}(p))) = 2d or

(2) deg_{t}(numer(ψ_{t}(p))) = 2d − 1.

Case (1): If degrees of q_{1} and q_{2} are both even then we can split up ψ_{t}(p) as

ψ_{t}(p) = \frac{q_{1}}{(1 + t^{2})^{d_{1}}} · \frac{q_{2}}{(1 + t^{2})^{d_{2}}}

where d_{i} = (1/2) deg_{t}(q_{i}) for i = 1, 2. If degrees are both odd then q_{2} must be reducible. Moreover, q_{2} must have an irreducible factor of odd degree, say q_{3}. Write q_{2} = q_{3} · q_{4} (note deg_{t}(q_{4}) even). We can split up ψ_{t}(p) as

ψ_{t}(p) = \frac{q_{1} · q_{3}}{(1 + t^{2})^{d_{1}}} · \frac{q_{4}}{(1 + t^{2})^{d_{2}}}

where d_{1} = (1/2)(deg_{t}(q_{1})+deg_{t}(q_{3})) and d_{2} = (1/2) deg_{t}(q_{4}).

Case (2): Exactly one of q_{1} and q_{2} is of odd degree, say q_{1}. Split up ψ_{t}(p) as

ψ_{t}(p) = \frac{q_{1}}{(1 + t^{2})^{d_{1}}} · \frac{q_{2}}{(1 + t^{2})^{d_{2}}}

where d_{1} = (1/2)(deg_{t}(q_{1}) + 1) and d_{2} = (1/2)(deg_{t}(q_{2})).

In either case we can split up ψ_{t}(p) as

ψ_{t}(p) = \frac{q̂_{1}}{(1 + t^{2})^{d_{1}}} · \frac{q̂_{2}}{(1 + t^{2})^{d_{2}}}

where 2d_{i} ≥ deg_{t}(q̂_{i}) and d_{i} ≥ 1, i = 1, 2. By Theorem 1 both of these correspond to trigonometric polynomials in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ with degrees d_{1} and d_{2} respectively, where d_{1}, d_{2} ≥ 1. Thus p is reducible.

(⇐) Suppose (i) and (ii) hold. Towards a contradiction suppose p is reducible. Write p = a · b where a, b ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ , and TD(a) ≥ 1, TD(b) ≥ 1. Now

ψ_{t}(p) = ψ_{t}(a) · ψ_{t}(b)
= \frac{numer(ψ_{t}(a))}{(1 + t^{2})^{d_{a}}} · \frac{numer(ψ_{t}(b))}{(1 + t^{2})^{d_{b}}}

where d_{a} = TD(a) and d_{b} = TD(b). By the trig degree-sum formula d_{a} + d_{b} = TD(p). If deg_{t}(numer(ψ_{t}(a))) = 0 then

deg_{t}(numer(ψ_{t}(p))) = deg(numer(ψ_{t}(b)))
≤ 2d_{b}
= 2(TD(p) − d_{a})
= 2TD(p) − 2d_{a}
≤ 2TD(p) − 2 since d_{a} ≥ 1
< 2TD(p) − 1.

This contradicts (i). Similarly if deg_{t}(numer(ψ_{t}(b))) = 0. So numer(ψ_{t}(a)), numer(ψ_{t}(b)) ∉ ℚ. Thus numer(ψ_{t}(p)) is reducible in ℚ[t]. Since (ii) holds and numer(ψ_{t}(p)) is reducible then both numer(ψ_{t}(a)), numer(ψ_{t}(b)) are irreducible and deg_{t}(numer(ψ(a))), deg_{t}(numer(ψ(b))) are odd. Let d̂_{a} = deg_{t}(numer(ψ(a))) and d̂_{b} = deg_{t}(numer(ψ(b))). Since d̂_{a}, d̂_{b} are both odd and ≤ 2d_{a} and 2d_{b} respectively then d̂_{a} ≤ 2d_{a} − 1 and d̂_{b} ≤ 2d_{b} − 1.

Since (i) holds then

deg_{t}(numer(ψ_{t}(p))) = 2d or 2d − 1.

If deg_{t}(numer(ψ(p))) = 2d then 2d = d̂_{a} + d̂_{b} < 2d_{a} + 2d_{b} = 2d. If deg_{t}(numer(ψ(p))) = 2d − 1 then 2d − 1 = d̂_{a} + d̂_{b} < 2d_{a} + 2d_{b} − 2 = 2d − 2 which implies 2d ≤ 2d − 1. In each case we get a contradiction. Therefore p is irreducible. ■

2.4 Factorization in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩

It follows from Theorem 3 that s, 1 + c and 1 − c are all irreducible in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩, hence the trigonometric polynomial s^{2} = 1 − c^{2} has two distinct factorizations, namely, s × s and (1 + c)(1 − c), thus ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ is not a UFD. In this subsection we will sketch, by way of examples, an algorithm for determining all factorizations of a trigonometric polynomial.

Theorem 3 characterizes the irreducible trigonometric polynomials in terms of their images under the t-substitution. So to find all factorizations of a trigonometric polynomial we need to factor the numerator and look at combinations of pairs of the odd degree factors, and also take into account the possibility of (1 + c) factors.

Example 1: Let p = sc. First we find the image of p under ψ_{t}:

ψ_{t}(p) = ψ_{t}(sc) = \frac{2t(1 + t)(1 − t)}{(1 + t^{2})^{2}} .

Each factor of p, under ψ_{t}, must have denominator 1 + t^{2} to some power, thus p can have at most two factors since the power of 1 + t^{2} in the denominator of ψ_{t}(p) is 2. Applying Theorem 3 we see that the possible factorizations of ψ_{t}(p) are:

2 \frac{t}{1 + t^{2}} · \frac{(1 + t)(1 − t)}{1 + t^{2}} , 2 \frac{1 + t}{1 + t^{2}} · \frac{t(1 − t)}{1 + t^{2}} , and

2 \frac{1 − t}{1 + t^{2}} · \frac{t(1 + t)}{1 + t^{2}} .

These correspond to the three distinct factorizations of p

2(1/2s) · c = sc, 2(1/2(c + s + 1)) · (1/2(c + s − 1))

= 1/2(c + s + 1)(c + s − 1), and

2(1/2(c − s + 1)) · (1/2(−c + s + 1))

= 1/2(c − s + 1)(s − c + 1). □

Example 2 (from the introduction): Let p = (1+c)s+1−c^{2}. Again, we first find the image of p under ψ_{t}:

ψ_{t}(p) = \frac{4t(1 + t)}{(1 + t^{2})^{2}} .

Each factor of p, under ψ_{t}, must have denominator 1 + t^{2} to some power, thus p can have at most two factors. A possible factorization of ψ_{t}(p) is

4 \frac{t}{1 + t^{2}} · \frac{1 + t}{1 + t^{2}} .

However, there is still another factorization

4 \frac{1}{1 + t^{2}} · \frac{t(1 + t)}{1 + t^{2}} .

This factorization follows from Corollary 1. We can easily see that there are no other factorizations of ψ_{t}(p) in which each factor corresponds to a trigonometric polynomial. Therefore the two distinct factorizations of p are:

4(1/2s)(1/2(c + s + 1)) = s(c + s + 1),

4(1/2(1 + c))(1/2(s − c + 1)) = (1 + c)(s − c + 1). □

We have not presented an explicit algorithm for finding all irreducible factors or factorizations of a given trigonometric polynomial because the details are many and messy. One must consider partitions of the set of factors of odd degree and balance the number of 1+t^{2} factors in the denominator. A Maple code for doing this is available from the authors.

We end this section by noting that the number of distinct factorizations grows exponentially with the number of distinct odd degree factors of a(t). For example, if a(t) factors into 2d distinct linear factors then there are 1 × 3 × 5 × ... × 2d − 1 distinct factorizations.

3. GCDS AND SIMPLIFICATION

In this section we define the trigonometric GCD of two trigonometric polynomials and give an algorithm for computing it. The classical definition of GCD for a commutative ring R, as stated, for example, by Hungerford in [1], is

Definition 6 (classical GCD). Let R be a commutative ring and let a, b ∈ R. An element g ∈ R is a greatest common divisor of a and b if

(i) g|a and g|b, and

(ii) if p|a and p|b then p|g.

Example 3 below shows that under this definition a GCD may not exist even when common divisors exist. This is not useful for computational purposes so we are led to consider the following definition for a GCD. The two definitions are equivalent when we are in a UFD.

Definition 7 (alternative GCD). Let R be a commutative ring and let a, b ∈ R. An element g ∈ R is a greatest common divisor of a and b if

(i) g|a and g|b, and

(ii) if p|(a/g) and p|(b/g) then p is a unit.

Example 3: Let a = s(1 + c), b = −c^{2} + cs + s + 1. Using the methods of Section 2.4 we find that a and b have exactly the following factorizations:

a = s(c + 1),
b = (c + s + 1)s = (−c + s + 1)(1 + c).

Now, s and 1 + c divide both a and b, hence under the classical definition of GCD we would have that the GCD g, if it exists, of a and b is divisible by both s and 1 + c.

Thus, s, 1 + c | g and g | a = s(1 + c) so g = s(1 + c) (up to multiplication by a unit). But g = s(1 + c) ∤ b, a contradiction. However, we have that both s and 1 + c are GCDs of a and b according to the alternative definition. □

The previous example shows that GCDs are not unique. The next example shows that two GCDs may not even have the same trigonometric degree.

Example 4: Let a = −5c^{3} + 5sc^{2} − 5c^{2} + 2cs + c + 9s + 9, b = −c^{5} + 17c^{4} − 7sc^{4} + 6c^{3} − 16sc^{3} + 2c^{2} − 14sc^{2} − 21c − 24cs − 3 − 3s. The images of a and b under ψ_{t} are:

ψ_{t}(a) = 8 \frac{t(t + 1)(t^{3} + 2)(t + 2)}{(1 + t^{2})^{3}} ,

ψ_{t}(b) = 32 \frac{t(t + 1)(t^{3} + 2)(t^{5} − 2)}{(1 + t^{2})^{5}} .

We cannot take the image of the GCD to be t(t+1)(t^{3}+2) for if we did we cannot partition the three (1+t^{2}) factors in the denominator of ψ_{t}(a) between t(t+1)(t^{3}+2) and the cofactor image (t + 2) so that both are images of a trigonometric polynomials. We can split these images of trigonometric polynomials as follows:

ψ_{t}(a) = 8 \frac{t(t + 1)}{1 + t^{2}} · \frac{(t^{3} + 2)(t + 2)}{(1 + t^{2})^{2}} and

ψ_{t}(b) = 32 \frac{t(t + 1)}{1 + t^{2}} · \frac{(t^{3} + 2)(t^{5} − 2)}{(1 + t^{2})^{4}} .

We can also split them as:

ψ_{t}(a) = 8 \frac{t(t^{3} + 2)}{(1 + t^{2})^{2}} · \frac{(t + 1)(t + 2)}{1 + t^{2}} and

ψ_{t}(b) = 32 \frac{t(t^{3} + 2)}{(1 + t^{2})^{2}} · \frac{(t + 1)(t^{5} − 2)}{(1 + t^{2})^{3}} .

The first way we have the common factor \frac{t(t+1)}{1+t^{2}} which corresponds to the GCD s−c+1 of a and b whereas in the second way we have the common factor \frac{t(t^{3}+2)}{(1+t^{2})^{2}} which corresponds to the GCD c^{2} + 2cs − 2c + 2s + 1. □

This example shows that two GCDs may have different trigonometric degrees. It seems reasonable that a GCD of highest trigonometric degree is the one we really are interested in. This motivates the following definition for a GCD in ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩.

Definition 8 (trigonometric GCD). Let a, b ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩. An element g ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ is called a trigonometric greatest common divisor (trig GCD) of a and b if

(i) g|a and g|b, and

(ii) if p|(a/g) and p|(b/g) then p is a unit.

(iii) if h satisfies (i) and (ii) then TD(g) ≥ TD(h)

Following the method in the previous example we now present an algorithm for computing trigonometric greatest common divisors.

Algorithm [trig GCD]

Input: Two trigonometric polynomials a and b.

(da, db) ← (TD(a), TD(b))
(a_{t}, b_{t}) ← (ψ_{t}(a) · (1 + t^{2})^{da}, ψ_{t}(b) · (1 + t^{2})^{db})
g_{t} ← gcd(a_{t}, b_{t})
(ā_{t}, b̄_{t}) ← (a_{t}/g_{t}, b_{t}/g_{t})
l ← min(da − ⌈deg_{t}(ā_{t})/2⌉, db − ⌈deg_{t}(b̄_{t})/2⌉)
if deg_{t}(g_{t}) > 2 · l then

f ← a smallest odd degree factor of g_{t}. g_{t} ← g_{t}/f, ā_{t} ← ā_{t} · f, b̄_{t} ← b̄_{t} · f. l ← min(da − ⌈deg_{t}(ā_{t})/2⌉, db − ⌈deg_{t}(b̄_{t})/2⌉).

g ← ψ_{t}^{−1}( \frac{g_{t}}{(1+t^{2})^{l}})
RETURN(g). ♦

In the algorithm there is an extra adjustment that has to be done if the degree of g_{t} is too big. Example 4 illustrated this. Note that with condition (iii) the GCD is still non-unique as illustrated by example 3.

Note, in the algorithm we may need to remove from p ∈ ℚ[t] a factor of least odd degree. This can be done by factoring p over ℚ but it makes the trigonometric GCD algorithm relatively expensive. In some applications it will be worthwhile computing any linear factors of p before attempting a full factorization of p.

Since we now know how to compute trig GCDs it should seem rather straight forward on how to simplify rational trigonometric polynomials: divide out by a trig GCD. However, it turns out that we may be able to simplify the ratio further than by dividing out by a trig GCD.

Example: Let a = 5c^{3} + 21c^{2} + 4cs + 23c + 15 + 12s, b = 7c^{3} − c^{2}s + 31c^{2} + 2cs + 37c + 15s + 21. The images under the t-substitution are:

ψ_{t}(a) = \frac{8(t^{2} + 2)(t^{3} + 2)(t + 2)}{(1 + t^{2})^{3}}

and

ψ_{t}(b) = \frac{8(t^{2} + 2)(t^{3} + 2)(t + 3)}{(1 + t^{2})^{3}} .

Now,

\frac{ψ_{t}(a)}{ψ_{t}(b)} = \frac{t + 2}{t + 3} = \frac{\frac{t+2}{1+t^{2}}}{\frac{t+3}{1+t^{2}}} .

Converting both the numerator and the denominator back to trigonometric polynomials we get,

\frac{a}{b} = \frac{2c + s + 2}{3c + s + 3} .

So \frac{a}{b} can be simplified to a ratio of two degree 1 trigonometric polynomials. This suggests that a trigonometric polynomial of trigonometric degree 2 must have been cancelled out from both a and b. But the only trigonometric GCD of a and b is c + 3 which has trigonometric degree 1. There is no common divisor of a and b with trigonometric degree greater than 1. This implies that 2c + s + 2 does not divide a and 3c + s + 3 does not divide b. □

The previous example illustrates that simplifying rational trigonometric polynomials done via the t-substitution may produce a rational trigonometric polynomial where the trigonometric degrees of the numerator and denominator have dropped more than that of just cancelling the trigonometric GCD. In fact, simplifying this way we are guaranteed that we will not do any worse than if we had cancelled a trigonometric GCD. We prove this in the theorem following the statement of the algorithm. Notice also that we do not need to factor in ℚ[t] as we might have to if we attempt to cancel a trig GCD. We now present the algorithm for simplifying rational trigonometric polynomials done via the t-substitution.

Algorithm [trig simplify] Input: A rational trigonometric polynomial \frac{a}{b}.

(da, db) ← (TD(a), TD(b))

(a_{t}, b_{t}) ← (ψ_{t}(a) · (1 + t^{2})^{da}, ψ_{t}(b) · (1 + t^{2})^{db})

g_{t} ← gcd(a_{t}, b_{t})

(ā_{t}, b̄_{t}) ← (a_{t}/g_{t}, b_{t}/g_{t})

if da ≤ db then

ā_{t} ← ā_{t}(1 + t^{2})^{db−da} else

b̄_{t} ← b̄_{t}(1 + t^{2})^{da−db}

l ← max(⌈deg_{t}(ā_{t})/2⌉, ⌈deg_{t}(b̄_{t})/2⌉)

ā ← ψ_{t}^{−1}(ā_{t}/(1 + t^{2})^{l})

b̄ ← ψ_{t}^{−1}(b̄_{t}/(1 + t^{2})^{l})

RETURN( \frac{ā}{b̄}). ♦

Theorem 4. Let f, g ∈ ℚ[s, c]/⟨s^{2} + c^{2} − 1⟩ be non-zero trigonometric polynomials. Let p/q be the output of algorithm trig simplify. Then there does not exist trigonometric polynomials a, b satisfying a/b = p/q and TD(a) + TD(b) < TD(p) + TD(q).

Proof: Let dp = TD(p), dq = TD(q). Let p_{t} = ψ_{t}(p)(1 + t^{2})^{dp} and q_{t} = ψ_{t}(q)(1 + t^{2})^{dq}. We claim that the output of algorithm trig simplify satisfies GCD(p_{t}, q_{t}) = 1 and either (i) deg p_{t} > 2dp − 2 or (ii) deg q_{t} > 2dq − 2, that is p and q are not both divisible by 1 + c. Let da = TD(a), db = TD(b) and let a_{t} = ψ_{t}(a)(1 + t^{2})^{da} and b_{t} = ψ_{t}(b)(1 + t^{2})^{db}. Now a/b = p/q implies

b_{t}p_{t}(1 + t^{2})^{dq−dp} = q_{t}a_{t}(1 + t^{2})^{db−da}.

Since 1 + t^{2} is relatively prime to a_{t}, b_{t}, p_{t}, q_{t} then dq − dp = db − da, that is,

dq + da = db + dp.

Next we note that because GCD(p_{t}, q_{t})=1 and GCD(p_{t}, 1 + t^{2})=1 then p_{t}|a_{t}. In case (i) we have deg p_{t} > 2dp−2. Since p_{t}|a_{t} then we have 2da ≥ deg a_{t} ≥ deg p_{t} > 2dp − 2, hence da ≥ dp, equivalently −da ≤ −dp. Adding this to the above equation yields dq ≤ db hence the theorem follows for this case. A similar argument will hold for (ii). ■

4. CONCLUSIONS AND FINAL REMARKS

The main result of our paper is a way to simplify ratios of trigonometric polynomials. We have also shown how to divide, factor and compute GCDs of trigonometric polynomials. Though we have not given the algorithmic details for dividing and factoring trigonometric polynomials in the paper, we have implemented all of these operations in Maple. Our Maple code is available from the authors.

The theory for factorization of trigonometric polynomials which we developed over ℚ holds for any constant field k provided i = \sqrt{−1} ∉ k. If i ∈ k then s + ic and s − ic are units as (s + ic)(s − ic) = 1 and consequently the trigonometric degree sum formula that we gave no longer holds. We have not modified the theory for this case but we note that it will be simpler because ℚ(i)[s, c]/ < s^{2} + c^{2} − 1 > is a UFD, thus GCDs are unique up to multiplication by units. Consequently simplification can be accomplished by cancelling a GCD.

The approach taken by Maple 6’s simplify command when given a ratio of trigonometric polynomials is the following. Replacing s by \sqrt{1 − c^{2}} we may view a ratio of trigonometric polynomials as an algebraic function, that is, an element of the function field ℚ(c, \sqrt{1 − c^{2}}). One standard form for algebraic functions is to clear \sqrt{1 − c^{2}} from the denominator. Replacing \sqrt{1 − c^{2}} back by s yields a result of form a(c) + b(c)s where a(c) and b(c) are in ℚ(c). When applied to the simplification problem in the introduction this yields the following result

\frac{(c^{2} + c − 1)}{c (c^{4} − 3 c^{2} + 3)} s − \frac{(1 + c) (c^{2} − c − 1)}{c (c^{4} − 3 c^{2} + 3)} .

We observe that the trigonometric degree of the numerator is 3 and that of the denominator is 5 which is greater than that of the input, thus no simplification is achieved. Thus our result can also be applied to simplify an element of the algebraic function field ℚ(c, \sqrt{1 − c^{2}}).

Acknowledgement

We acknowledge helpful discussions with our colleagues, in particular Hans Bauck, Petr Lisonek and Mark van Hoeij.

5. REFERENCES

[1] Hungerford, T.W. (1980) Algebra, second edition, Graduate Texts in Mathematics, Springer-Verlag.

[2] Roach, K. (1992), Trigonometric Factorization and Integration, Unpublished manuscript. Presented at the Maple Retreat, June, 1992.

[3] Trotter, H.F. (1989), An Overlooked Example of Nonunique Factorization, American Mathematical Monthly, 95(4), 339–342.