Basic trigonometry provides the means to compute the values of Sin and Cos of the sum of (or difference between) two angles from their values at the two angles. We can use this to compute the Sin and Cos of any multiple of an angle from the Sin and Cos of that angle. This will inevitably give us polynomials in two free variables which, when fed the base angle's Sin and Cos as values for those, will yield the Sin and Cos of each multiple. It turns out that these polynomials can (by exploiting the fact that the squares of Sin(a) and Cos(a) sum to 1 for any angle a) be expressed in terms of two families, S and C, of polynomials – in only one free variable, the base angle's Cos – as follows: for any angle t and any natural n,
(and, apparently, (|C:) are known as the Chebychev polynomials, with T=C and U=S, so the following isn't novel; see also de Moivre's formula). The first few of these polynomials are given by:
| n | S(n, u) | C(n, u) |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2.u | u |
| 2 | 4.u.u −1 | 2.u.u −1 |
| 3 | 4.u.(2.u.u −1) | u.(4.u.u −3) |
| 4 | 4.u.u.(4.u.u −3) + 1 | 8.u.u.(u.u −1) + 1 |
| 5 | 2.u.(4.u.u −1).(4.u.u −3) | u.(4.u.u.(4.u.u −5) + 5) |
| 6 | 8.u.u.(2.u.u.(4.u.u −5) + 3) −1 | (2.u.u −1).(16.u.u.(u.u −1) + 1) |
For the sake of definiteness, define a function power by:
power(n+m,u) = power(n,u).power(m.u) and power(1,u) = u, with power(0,u) = 1; in
particular, power(n,−1) is −1 if n is odd, +1 if n is even: thus
power(n,x) is what's commonly written xn, power(2,u) = u.u, etc. The
polynomial sequences S, C and (see below) K are implemented by the
study.maths.multiangle module of my python study package.
It is immediately apparent that, at least for n = 0 through 6:
We also know that Sin is zero at all multiples of a half-turn and Cos is zero at all odd multiples of a quarter turn. Introduce left = +turn/4 (the positive right angle) and we can express this as Sin(2.i.left) = 0 = Cos((2.i+1).left) for every integer i. For any natural n, Cos(n.t) will be zero if n.t/left is 2.i+1 for some integer i; in particular, i in n will give t = (2.i+1).left/n with 0.turn < t < 2.left = turn/2 and Cos(n.t) = 0; for odd n, one of these values is t = left with Cos(t) = 0. Since Cos is monotonically decreasing from 0.turn to turn/2, these n values for t all give distinct values for Cos(t), hence for u with −1≤u≤1 and C(n,u) = 0. Thus the polynomial C(n) has n roots between −1 and 1; for odd n, one of these roots is u = 0. In similar manner, Sin(i.turn/2) = 0 for positive i in n yields t = i.turn/2/n with 0.turn < t < turn/2 and Sin(n.t) = 0. These give us, as Cos(t), n−1 distinct values of u for which S(n−1,u) = 0; so S(n−1) has n−1 roots between −1 and 1; for even n, one of these roots is at u = 0. In each case, the roots are distinct and symmetrically arranged around zero.
From the definitions, we can infer that u between −1 and 1 implies C(n,u) also lies in that range; while S(n−1,u) may be as big as n (which is the limit Sin(n.t)/Sin(t) approaches as t tends to zero). We can equally infer, for any natural n and m and any u between −1 and 1,
The above-mentioned angle-addition formulae imply:
Of course, since these are polynomial equations and apply for all u from −1 to 1, they must also apply for all real (and, indeed, complex) u.
From these addition formulae and knowledge that S(n) and C(n) have rank n at least for n = 0, 1, 2, we can induce that S(n) and C(n) have rank at most n for every natural n. We've already seen that each has n distinct zeros between −1 and 1, telling us that each has rank at least n, so we can infer that our polynomials have no other zeros and do have rank exactly n. We know that, for odd n, S(n) and C(n) have a zero at 0, confirming the pattern noticed earlier, with u as a factor of C(n,u) and S(n,u) for each odd n. Thus properties 1 and 2, in the list above, are established for all n.
Since their zeros are symmetrically arranged either side of 0, we can factorise each S(n,u) or C(n,u) into a product of terms of form (u+r).(u−r), with r one of the zeros, with an extra factor of u when n is odd and an overall scalar factor in any case; but (u+r).(u−r) is just u.u−r.r, with no linear term; thus we establish property 3. In particular, this implies that −u ←u has no effect on these quadratic factors and only affects C(n) or S(n) via the factor of u when n is odd; thus
The addition formulae, and property 5's truth for small n, suffice to establish that all contributions to the leading-order term in S(n+m−1) or C(n+m) will indeed have positive sign, and all contributions to any term of any order will be integral, thus establishing property 5 inductively for all n. When multiplying two polynomials with properties 1 through 5, a term from one with degree 2.i less than that polynomial's highest, and one from the other of degree 2.j less than its highest, will have coefficients whose sign is the same if i+j is even or different if i+j is odd; thus any term in the product, of degree 2.k less than its highest degree, will get contributions only of sign power(k,−1), ensuring that the product satisfies property 4; the angle-addition formulae (and the already-established truth of the rest of 1 through 5 for all n) then suffice to establish property 4 inductively for all n.
The product rule formulae, taken with C(2) and S(1), imply that C(2.n) and S(2.n−1) have property 6 for all n; but the (u.u−1) factor in C's addition formula makes it hard to prove more generally.
Note that the factor of u in C(odd, u) and S(odd, u) yields, in Tan(n.t) = Sin(n.t).S(n−1, Cos(t))/C(n, Cos(t)), an overt factor of Tan(t) for odd n and a factor of Sin(t).Cos(t) = Tan(t).Cos(t).Cos(t) for even n; aside from these factors, Tan(n.t) is then a function of Cos(t).Cos(t) = 1/(Tan(t).Tan(t) +1), so that Tan(n.t) can be expressed solely in terms of Tan(t) and rational polynomials.
Thus we can write S(n,u) and C(n,u) as polynomials in −2.u.u, with a factor of u thrown in for odd n. Since the leading term is always positive, we need to take account of sign when we define the new families that result; but when we do, we'll get all coefficients positive throughout, thanks to properties 1 through 5 above. If these coefficients are all integral, then property 6 necessarily does hold, after all. (I'll also take a factor of 2 off one polynomial because it has one – and its removal makes for better tidiness later.) We can define polynomial functions A, B, R and Q by:
From the above, we know there are 2.n non-zero distinct roots of C(2.n), between −1 and +1, symmetrically placed about zero; and likewise for S(2.n). This implies n distinct roots each for A(n) and Q(n), all between −2 and 0. C(2.n+1) has one zero root and 2.n distinct non-zero roots symmetrically placed around 0; as has S(2.n+1); likewise, this implies n distinct roots for each of B(n) and R(n), again between −2 and 0. Since C(2.n) lies between −1 and +1 if its input does, we can infer that A(n) falls in the same range if its input lies between −2 and 0.
Substitute in n=0 for each of the above, look up the appropriate 0 or 1 member of the C or S family, infer the 0-member of each of A, B, Q and R: all are the constant polynomial 1←u. (This is why R's definition pushed out a factor of 2.)
Substituting these into the addition rules for S and C, above, we obtain:
Or we can split 2.n+2.m as (2.n+1)+(2.m−1), to obtain
(note the −2 introduced by R using m−1). The alternative subdivision of 2.n+2.m+1 simply interchanges n and m in this.
but, again, we have an alternate way to cut the pie:
In which the alternate sub-division merely interchanges the rôles of m and n.
From these I infer
Given that A(0), B(0), Q(0) and R(0) are all 1←v, of rank 0, and all co-efficients in the above are positive, one may prove (inductively) that, for each n, A(n), B(n), Q(n) and R(n) are of rank n; and that every power up to n appears in each with positive co-efficient. In particular, none of these polynomials is a multiple of v←v (the constant term is positive), and each of them can (since we know it has n roots between −2 and 0) be factorised completely over the reals. Furthermore, notice that we may infer all members of the A and R families (which tell us cos and sin of even multiples of an angle) without reference to the B and Q families (which tell us about odd multiples). This should be no surprise. Later we shall see that, given only R(0) and A(1), we may likewise infer B and Q without (further) reference to R and A.
The four cases which don't involve division suffice to let us infer all members of all four families from their common start-point. These four rules only add and multiply together earlier polynomials in the formation of later ones; and we start from polynomials whose coefficients are all integers. We may induce that all the coefficients we shall see shall be integers (we already know they are positive). Thus, finally, property 6 (above) is proven.
The first few of each family are:
| n | A(n,x) | B(n,x) | Q(n,x) | R(n,x) |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1+x | 3+2.x | 1+2.x | 2.(1+x) |
| 2 | 1+2.x.(2+x) | 5+2.x.(5+2.x) | 1+2.x.(3+2.x) | (1+2.x).(3+2.x) |
| 3 | (1+x).(1+4.x.(2+x)) | 7+2.x.(14+2.x.(7+2.x)) | 1+4.x.(3+2.x).(1+x) | 4.(1+x).(1+2.x.(2+x)) |
Feeding some of these back into the induction formulae, by substituting a small value for m or n, we see:
In particular note that the first formula from each ?(n+1,x) case allow us to separate R and A from B and Q. By reading our inference rules `backwards', we can examine the case n<0:
Now, experiment (with a python module which uses polynomials neatly) reveals that S(n,x+1) = R(n,x) and C(n,x+1) = A(n,x), at least for n up to 6, hinting that we should be able to somewhat simplify the above. Furthermore, factorising Q(n) and B(n) via Q(1) and B(1), respectively, yields simpler polynomials than the Q and B series; and the two resulting series differ only in the sign of some of their terms. It is clear that we should thus be able to obtain a tidier refactoring.
First let's look at C and R in the light of this. The first thing to notice is that if R's or A's parameter is x = −2.u.u, then 1+x = 1−2.u.u = −C(2,u). Among the simple properties noted above, remember the formulae for S(n.m−1) and C(n.m); and that C(n,−u) is power(n,−1).C(n,u) and likewise for S. Thus
whence we can infer A(n,x) = C(n, 1+x) at least for all x between −2 and 0; but, as this is an equation between polynomials, it must thus apply for all x.
since S(1,u) is 2.u; as before we can now infer R(n,x) = S(n,1+x).
Thus we can go back to the start of our re-factoring, exploit C(2.n,u) = C(n,2.u.u−1) and S(2.n+1,u) = 2.u.S(n, 2.u.u−1) to make A and R redundant, then see what we need to say in place of B and Q. In the above, I derived recurrence relations for these, which I can re-write as:
So now let me introduce an inductive hypothesis: namely,
and notice that it is trivially true, given B(0) = (:1←u:) = Q(0), for n = 0. Now, suppose it is true for n=i, for some given i, and apply the recurrence relations to induce:
using the inductive hypothesis with x = u in the first term and x = −u in the second, whence
Thus the inductive hypothesis holds for n=i+1 if it holds for n=i; given that it holds for n = 0, I can thus induce that it holds true for all n. Furthermore, each power of x in each member of the B and Q series has as many powers of 2 as of x, which may as well be incorporated into the parameter. A bit of gentle experimentation reveals that it is worth introducing a polynomial K defined by
Substituting into the definitions of B and Q, we obtain:
along with the recurrence relation
which we can combine with the doubling-recurrences of S and C and K's relationship with S and C to obtain
with
From the addition formulae for S and C, we can infer
whence, substituting x = 1−4.u.u,
and substituting x = 4.u.u −3 into this yields the same as the earlier S-result.
From various multi-angle formulae, we know that
which we can re-write, via x = 1−4.u.u, as
which we can re-write, via x = 4.u.u−3, as
Comparing that with the previous, K(n) must map (x+3).power(2, K(m, x)) −3 and 1 −(1−x).power(2, K(m, −x−2)) to equal values; this suggests 4+(x−1).power(2, K(m, −x−2)) = (x+3).power(2, K(m, x)), which does appear to be true (experimentally), and can be re-written as 4+(x−3).power(2, K(m, −x)) = (x+1).power(2, K(m, x−2)).
whence we can infer, exploiting 1−power(2, 4.u.u−2) = (1−4.u.u).(4.u.u−3) and substituting x = 4.u.u−1,
which we can re-write, via x = 4.u.u−1 and an over-all scaling by 4, as
and substituting 2−x in place of x preserves the form of this, albeit with an over-all negation and swapping the two right-hand terms. We have earlier seen that these two terms differ by 4, so it would appear that
However, the equality of 4+(x−3).power(2, K(n, −x)) and (x+1).power(2, K(n, x−2)) is thus far merely an observed truth for small n. Note that u = x−1 turns this into 4+(u−2).power(2, K(n, −u−1)) = (u+2).power(2, K(n, u−1)). Our recurrence relations suffice to imply
so this combination of K's squares doesn't depend on n; since it's zero for n = 0, K(0) = (: 1←x :), it must therefore be zero for all n. This suffices to prove the equality noticed above and confirm the equalities inferred from it. We thus have (rearranging terms for clarity)
Now, can I refine K's recurrence relation ? power(2, K(n, −u−1).(u−2)) = power(2, K(n, u−1)).(u.u−2) −4.(u−2) 2.K(n+1, u−1) = u.K(n, u−1) +√((power(2, K(n, u−1)).(u+2) −4).(u−2)) 2.K(n+1, −u).power(n+1, −1) = (u+1).K(n, u−2) +(u−1).K(n, −u).power(n, −1)
Written by Eddy.