Cosine integral domains.
Version of Saturday 26 March 2016.
Dave Barber's other pages.

§ 0. In this report is defined a family of integral domains employing the cosine function of elementary trigonometry. Each of these is termed a cosine integral domain, or more briefly a CID (upper case letters). An object of a CID type is a cid (lower case letters).

At the end of this report is described a program in the C++11 language which is provided to aid the reader in performing calculations. Everyone is welcome to download, use, modify, and republish it. It uncompresses from 15 kb to 64 kb.

§ 1. The following bold-C notation for some essential constants will decongest subsequent expressions:

Cm/n = 2 cos (½ mπ / n)

The factors 2 and ½ greatly simplify the multiplication rules given below. A bold-S notation could equally well have been chosen:

Sm/n = 2 sin (½ mπ / n) = C(nm)/n

There are two requirements for a Cm/n to be used in any of these CIDs:

• m must be an integer greater than zero but less than n;
• n must be a positive integer that is not a power of two.

Because Cm/n is based on the cosine, it would without special provisions be a periodic function. However, when the two above requirements are fulfilled, Cm/n is restricted to a domain where it is one-to-one, and thus not periodic. In that case, this assertion is valid:

Cm/n = Cp/q if and only if m ÷ n = p ÷ q

Given the following integers serving as coefficients:

a1, a2, a3an−1

a cid named A, of order n, is defined to be:

A = a1C1/n + a2C2/n + a3C3/n + … + an−1C(n−1)/n

Any integers may be chosen as coefficients. One way to write a cid uses shallow angle brackets enclosing a comma-separated list of coefficients:

A = ⟨ a1, a2, a3an−1

A cid of order n has n−1 terms, so the this notation is unambiguous with respect to order.

§ 2. Every cid is a real number. As a result, there is no choice in how to define addition, subtraction, and multiplication of two cids. The same applies to division, when the quotient exists. Division by zero is always barred, and in many other cases a candidate quotient of two cids fails because the coefficients, while rational, are not integers. (Incidentally, if rational coefficients were permitted, a field would result.)

As with any real numbers, addition and multiplication of cids are associative and commutative; and multiplication distributes over addition. Any cid whose real-number value is zero is an additive identity; the multiplicative identity is explained later.

The notion of equality is also taken from the real numbers. Specifically, cid A equals cid B if and only if their real-number values are equal. They need not be of the same order; and even if of the same order, they need not have the same coefficients. On the other hand, if two cids of the same order do have the same coefficients throughout, they are termed isomers and are certainly equal. Here are some relational symbols:

table 2A
notation A is equal to B A is isomeric to B
A == Byesyes
A = Byesdk-dc
A =≠ Byesno
ABdk-dcno
A ≠≠ Bnono
"dk-dc" means don't know or don't care

Also in accord with the real numbers are the greater-than and less-than relations, but they turn out to be of limited usefulness. Because cosines are usually irrational, there is in general no simple way to evaluate equality or inequalities by manipulation of coefficients.

§ 3. Of most operations that appear in this report, all the inputs, and the output, will be cids of the same order. Mixing orders rarely gives interesting (or convenient) results, although sometimes possible are conversions where the real-number value of the cid does not change:

• If q is a multiple of p, a cid of order p can always be converted to order q.
• If q is a factor of p, a cid of order p can be converted to order q if appropriate coefficients in the source cid are zero.

When A and B are of the same order, addition and subtraction are in parallel:

A + B = ⟨ a1 + b1, a2 + b2, a3 + b3an−1 + bn−1
AB = ⟨ a1b1, a2b2, a3b3an−1bn−1

For any integer k, scalar multiplication, which corresponds to repeated addition or subtraction, is thus:

kA = ⟨ ka1, ka2, ka3kan−1

In every integral domain there had better be a multiplicative identity, and for CIDs it is the real number one, which can be written a variety of ways. This works because of some very fortuitous trigonometric identities. Examples:

table 3A
order is an odd number
31 = C2/3
51 = C2/5C4/5
71 = C2/7C4/7 + C6/7
91 = C2/9C4/9 + C6/9C8/9
111 = C2/11C4/11 + C6/11C8/11 + C10/11
131 = C2/13C4/13 + C6/13C8/13 + C10/13C12/13
order is two times an odd number
61 = C4/6
101 = C4/10C8/10
141 = C4/14C8/14 + C12/14
181 = C4/18C8/18 + C12/18C16/18
221 = C4/22C8/22 + C12/22C16/22 + C20/22
261 = C4/26C8/26 + C12/26C16/26 + C20/26C24/26
order is four times an odd number
121 = C8/12
201 = C8/20C16/20
281 = C8/28C16/28 + C24/28
361 = C8/36C16/36 + C24/36C32/36
441 = C8/44C16/44 + C24/44C32/44 + C40/44
521 = C8/52C16/52 + C24/52C32/52 + C40/52C48/52
all of these are canonical as described below

Within an order, there can be many ways to write the multiplicative identity:

table 3B
order 15
1 = C10/15 compare order three: 1 = C2/3
1 = C6/15C12/15 compare order five: 1 = C2/5C4/5
1 = C2/15C4/15 + C6/15C8/15 + C10/15C12/15 + C14/15
1 = C2/15C4/15 + 2C6/15C8/15 − 2C12/15 + C14/15
1 = 3C2/15 − 3C4/15 − 3C8/15 + 4C10/15 + 3C14/15
1 = − 13C2/15 + 13C4/15 + 13C8/15 − 12C10/15 − 13C14/15

Consequently, there are multiple ways to write the additive identity. From the first two rows of table 3B for instance, (C6/15C12/15) − C10/15 = 1 − 1 = 0.

For each CID, one version of the multiplicative identity is termed canonical, as follows. Let n be the CID's order. Then there exist unique nonnegative integer p and unique positive odd integer q such that n = 2p · q. With that, the canonical multiplicative identity is of this form:

+ C(2 · 2p)/nC(4 · 2p)/n + C(6 · 2p)/nC(8 · 2p)/n … ± C(2i · 2p)/n
… terminating when 2i · 2p would be equal to or greater than n

This series does not give an identity when n is a power of two; an open question is whether there is a good alternative. Therefore, any order that is a power of two is excluded from this report.

It is cumbersome to write the CID multiplication rule for the general case, but the underlying formulas are these standard trigonometric identities:

2 cos (θ) cos (φ) = cos (θφ) + cos (θ + φ)
cos (π − θ) = − cos (θ)
cos (− θ) = cos (θ)
cos (0) = 1

Whence this multiplication rule:

table 3C
Cp/n · Cq/n if pq < 0 if pq = 0 if pq > 0
if p + q < n C(qp)/n + C(p+q)/n 2 + C(p+q)/n C(pq)/n + C(p+q)/n
if p + q = n C(qp)/n 2 C(pq)/n
if p + q > n C(qp)/n − C(2npq)/n 2 − C(2npq)/n C(pq)/n − C(2npq)/n

As full examples, the multiplication table of orders 6 and 7 appear below. The red cells are squares, the blue cells are antisquares, and a purple cell is both. The number 2 is used as a shorthand to simplify the square entries, which for higher orders would often be lengthy. Numerical approximations are included.

table 3D
multiplication
order 6
C1/6
1.931852
C2/6
1.732051
C3/6
1.414214
C4/6
1.000000
C5/6
0.517638
C1/6
1.931852
2 + C2/6
3.732051
C1/6 + C3/6
3.346065
C2/6 + C4/6
2.732051
C3/6 + C5/6
1.931852
C4/6
1.000000
C2/6
1.732051
C1/6 + C3/6
3.346065
2 + C4/6
3.000000
C1/6 + C5/6
2.449490
C2/6
1.732051
C3/6C5/6
0.896575
C3/6
1.414214
C2/6 + C4/6
2.732051
C1/6 + C5/6
2.449490
2
2.000000
C1/6C5/6
1.414214
C2/6C4/6
0.732051
C4/6
1.000000
C3/6 + C5/6
1.931852
C2/6
1.732051
C1/6C5/6
1.414214
2 − C4/6
1.000000
C1/6C3/6
0.517638
C5/6
0.517638
C4/6
1.000000
C3/6C5/6
0.896575
C2/6C4/6
0.732051
C1/6C3/6
0.517638
2 − C2/6
0.267949
2 = 2C4/6

table 3E
multiplication
order 7
C1/7
1.949856
C2/7
1.801938
C3/7
1.563663
C4/7
1.246980
C5/7
0.867767
C6/7
0.445042
C1/7
1.949856
2 + C2/7
3.801938
C1/7 + C3/7
3.513519
C2/7 + C4/7
3.048917
C3/7 + C5/7
2.431430
C4/7 + C6/7
1.692021
C5/7
0.867767
C2/7
1.801938
C1/7 + C3/7
3.513519
2 + C4/7
3.246980
C1/7 + C5/7
2.817623
C2/7 + C6/7
2.246980
C3/7
1.563663
C4/7C6/7
0.801938
C3/7
1.563663
C2/7 + C4/7
3.048917
C1/7 + C5/7
2.817623
2 + C6/7
2.445042
C1/7
1.949856
C2/7C6/7
1.356896
C3/7C5/7
0.695895
C4/7
1.246980
C3/7 + C5/7
2.431430
C2/7 + C6/7
2.246980
C1/7
1.949856
2 − C6/7
1.554958
C1/7C5/7
1.082088
C2/7C4/7
0.554958
C5/7
0.867767
C4/7 + C6/7
1.692021
C3/7
1.563663
C2/7C6/7
1.356896
C1/7C5/7
1.082088
2 − C4/7
0.753020
C1/7C3/7
0.386193
C6/7
0.445042
C5/7
0.867767
C4/7C6/7
0.801938
C3/7C5/7
0.695895
C2/7C4/7
0.554958
C1/7C3/7
0.386193
2 − C2/7
0.198062
2 = 2C2/7 − 2C4/7 + 2C6/7

Because real-number multiplication distributes over addition, table 3E is sufficient to multiply any two order-7 cids.

§ 4. From any CID it is possible to form a cosine integral subdomain (CISD, upper case) by selecting a suitable subset of the Cm/n values. An object in a CISD is called a cisd (lower case). Although a CISD is certainly an integral domain, it might not be a cosine integral domain as defined here.

From every CID can be obtained a step-2 CISD created by restricting m in Cm/n to the even numbers. If the CID is of even order, this CISD will be a CID; if the CID is instead of odd order, this CISD will not be a CID.

Recall that an ordinary (step-1) CID can be written this way:

A = ⟨ a1, a2, a3an−1

A step-2 CISD of even order can be written with double shallow angle brackets; note exclusion of the bn term:

B = ⟨⟨ b2, b4, b6bn−2 ⟩⟩n

A step-2 CISD of odd order can be written with the same syntax but slightly different subscripting:

C = ⟨⟨ c2, c4, c6cn−1 ⟩⟩n

The subscript after the double closing bracket resolves an ambiguity for cisds, because step-2 cisds of order 2n and order 2n−1 have the same number of components. Not yet established is a notation for writing a CISD of higher step.

Table 4A is a multiplication table for a step-2 CISD of order seven; it turns out to be an excerpt of table 3E:

table 4A
multiplication
order 7, step-2
C2/7
1.801938
C4/7
1.246980
C6/7
0.445042
C2/7
1.801938
2 + C4/7
3.246980
C2/7 + C6/7
2.246980
C4/7C6/7
0.801938
C4/7
1.246980
C2/7 + C6/7
2.246980
2 − C6/7
1.554958
C2/7C4/7
0.554958
C6/7
0.445042
C4/7C6/7
0.801938
C2/7C4/7
0.554958
2 − C2/7
0.198062
2 = 2C2/7 − 2C4/7 + 2C6/7

To begin another example, table 4B is the multiplication table for the full CID of order 9:

table 4B
multiplication
order 9, step-1
C1/9 C2/9 C3/9 C4/9 C5/9 C6/9 C7/9 C8/9
C1/9 2 + C2/9 C1/9 + C3/9 C2/9 + C4/9 C3/9 + C5/9 C4/9 + C6/9 C5/9 + C7/9 C6/9 + C8/9 C7/9
C2/9 C1/9 + C3/9 2 + C4/9 C1/9 + C5/9 C2/9 + C6/9 C3/9 + C7/9 C4/9 + C8/9 C5/9 C6/9C8/9
C3/9 C2/9 + C4/9 C1/9 + C5/9 2 + C6/9 C1/9 + C7/9 C2/9 + C8/9 C3/9 C4/9C8/9 C5/9C7/9
C4/9 C3/9 + C5/9 C2/9 + C6/9 C1/9 + C7/9 2 + C8/9 C1/9 C2/9C8/9 C3/9C7/9 C4/9C6/9
C5/9 C4/9 + C6/9 C3/9 + C7/9 C2/9 + C8/9 C1/9 2 − C8/9 C1/9C7/9 C2/9C6/9 C3/9C5/9
C6/9 C5/9 + C7/9 C4/9 + C8/9 C3/9 C2/9C8/9 C1/9C7/9 2 − C6/9 C1/9C5/9 C2/9C4/9
C7/9 C6/9 + C8/9 C5/9 C4/9C8/9 C3/9C7/9 C2/9C6/9 C1/9C5/9 2 − C4/9 C1/9C3/9
C8/9 C7/9 C6/9C8/9 C5/9C7/9 C4/9C6/9 C3/9C5/9 C2/9C4/9 C1/9C3/9 2 − C2/9
2 = 2C2/9 − 2C4/9 + 2C6/9 − 2C8/9 = C6/9

Table 4C is the multiplication table for the step-2 CISD of order 9, which is not a CID:

table 4C
multiplication
order 9, step-2
C2/9 C4/9 C6/9 C8/9
C2/9 2 + C4/9 C2/9 + C6/9 C4/9 + C8/9 C6/9C8/9
C4/9 C2/9 + C6/9 2 + C8/9 C2/9C8/9 C4/9C6/9
C6/9 C4/9 + C8/9 C2/9C8/9 2 − C6/9 C2/9C4/9
C8/9 C6/9C8/9 C4/9C6/9 C2/9C4/9 2 − C2/9
2 = 2C2/9 − 2C4/9 + 2C6/9 − 2C8/9 = C6/9

Table 4D contains the multiplication table for the step-3 CISD of order 9, which happens to be the same as the (step-1) CID of order 3, shown beside it for comparison:

table 4D
multiplication
order 9, step-3
C3/9
1.732051
C6/9
1.000000
multiplication
order 3, step-1
C1/3
1.732051
C2/3
1.000000
C3/9
1.732051
2 + C6/9
3.000000
C3/9
1.732051
C1/3
1.732051
2 + C2/3
3.000000
C1/3
1.732051
C6/9
1.000000
C3/9
1.732051
2 − C6/9
1.000000
C2/3
1.000000
C1/3
1.732051
2 − C2/3
1.000000
2 = C6/9   2 = 2C2/3

As a recap, table 4E is a summary of the valid Cm/n symbols for several smaller orders:

table 4E
orderCID (step 1)CISD (step 2)
1, 2excluded
3 C1/3, C2/3 C2/3
4excluded
5 C1/5, C2/5, C3/5, C4/5 C2/5, C4/5
6 C1/6, C2/6, C3/6, C4/6, C5/6 C2/6, C4/6
7 C1/7, C2/7, C3/7, C4/7, C5/7, C6/7 C2/7, C4/7, C6/7
8excluded
9 C1/9, C2/9, C3/9, C4/9,
C5/9, C6/9, C7/9, C8/9
C2/9, C4/9, C6/9, C8/9
10 C1/10, C2/10, C3/10, C4/10, C5/10,
C6/10, C7/10, C8/10, C9/10
C2/10, C4/10, C6/10, C8/10
11 C1/11, C2/11, C3/11, C4/11, C5/11,
C6/11, C7/11, C8/11, C9/11, C10/11
C2/11, C4/11, C6/11, C8/11, C10/11
12 C1/12, C2/12, C3/12, C4/12, C5/12, C6/12,
C7/12, C8/12, C9/12, C10/12, C11/12
C2/12, C4/12, C6/12, C8/12, C10/12

§ 5. The principal ingredient of the C++11 program to manipulate CIDs is this class:

template <int order, typename coef, int step>
class cos_int_dom;

The code is in these files:

• misc.h contains class offset_array, and odds and ends.
• cid_A.h contains most members of cos_int_dom.
• cid_B.h contains the cos_int_dom members supporting division.
• cid_C.h contains the cos_int_dom members supporting HTML for the multiplication tables shown above.
• cid_D.h contains non-member functions for type conversion involving order and step.
• demo_1.h through demo_5.h contain simple examples.
• main.cpp pulls it all together.

The template parameters:

• order is the order as described above. It must be a positive integer that is not a power of two.
• coef is the type of the coefficients, which should be a signed integer type.
• step:
• When step == 1, each object is a cid.
• When step == 2, each object is a step-2 cisd.
• Other values for step are not supported by this code.

For serious research, it is necessary to instantiate coef with an extended-precision integer class, which is not furnished here. Instead, the programmer can use his/her favorite signed big integer package.

Extended precision is required because the division operator often requires huge numbers for its intermediate results, as it performs Gaussian elimination in exact arithmetic. Because extended-precision integer classes typically perform overflow checking (often allocating more memory when overflow would otherwise occur), class cos_int_dom omits overflow checking to avoid redundancy.

Still, a fair amount of informative experimentation can be done using an ordinary 64-bit signed integer, and that is what the present author used for most testing. If the division operation is never to be invoked, a 32-bit signed integer might suffice.

There are six constructors in total. The copy and move constructors are ordinary:

cos_int_dom (cos_int_dom const &) = default;
cos_int_dom (cos_int_dom &&) = default;

The four other constructors are:

• explicit cos_int_dom (coef const & v); // ctor_1

which creates a cid or cisd whose real value is the integer v. If v is 1, the result is the multiplicative identity in canonical form.
• explicit cos_int_dom (initializer_list<coef> ili); // ctor_2

which creates a cid or cisd from the supplied initializer_list.
• When step == 1, the number of initializers must be 1 less than the order.
• When step == 2:
• and order is even, the number of initializers must equal ½ (order − 2);
• and order is odd, the number of initializers must equal ½ (order − 1).
• template <int src_order>
explicit cos_int_dom (cos_int_dom<src_order,coef,step> const & o); // ctor_3

which converts a lower-order cid or cisd to one of higher order, if the higher order is a multiple of the lower.
• template <int src_step>
explicit cos_int_dom (cos_int_dom<order, coef, src_step> const & o); // ctor_4

which converts a cisd to a cid having the same order and the same real-number value. The resultant cid will contain numerous zeroes.

Almost a constructor is this:

static cos_int_dom single (int const p);
which creates a cid or cisd with exactly one nonzero coefficient, with the value 1, at position p.

The copy-assignment and move-assignment operators are ordinary, as is the destructor:

cos_int_dom & operator= (cos_int_dom const &) = default;
cos_int_dom & operator= (cos_int_dom &&) = default;
~cos_int_dom () = default;

coef & at (int const n);
coef at (int const n) const;
offset_array const & at () const;
The at functions communicate with class offset_array which is where the coefficients are stored. Subscripting differs substantially from that of the C++ language. For example, if x is a cid of order 7, valid subscripts are:
x.at(1)    x.at(2)    x.at(3)    x.at(4)    x.at(5)    x.at(6)
and enough memory is allocated for exactly 6 coefficients. If y is a step-2 cisd of order 7, valid subscripts are:
y.at(2)    y.at(4)    y.at(6)
and enough memory is allocated for exactly 3 coefficients.

For all cids and cisds, the exact number of coefficients needed is calculated at compile time, to minimize the need for dynamic memory allocation, which can be slow. The offset_array class manages all this.

Output is produced by this function:

void view (ostream & o) const;
which includes an explicit indication of the order (in square brackets) followed by a decimal approximation. For example, the order-6 cid ⟨ +2, +4, −6, −8 +10 ⟩ is printed thus:
<  +2   +4   -6   -8  +10  [6]    -0.516994 >
and the order-10 step-2 cisd ⟨⟨ +124, −74, −76, −66 ⟩⟩10 is printed thus:
<< +124  -74  -76  -66  [10]   -14.006101 >>

Arithmetic functions are in the usual C++ format:

cos_int_dom operator+ () const;
cos_int_dom operator- () const;

cos_int_dom operator+ (cos_int_dom const &) const;
cos_int_dom operator- (cos_int_dom const &) const;
cos_int_dom operator* (cos_int_dom const &) const;
cos_int_dom operator/ (cos_int_dom const &) const;
cos_int_dom operator* (coef const &) const; // scalar multiplication

cos_int_dom & operator+= (cos_int_dom const &);
cos_int_dom & operator-= (cos_int_dom const &);
cos_int_dom & operator*= (cos_int_dom const &);
cos_int_dom & operator/= (cos_int_dom const &);
cos_int_dom & operator*= (coef const &); // scalar multiplication
Division by zero will throw an exception. If division yields a non-integer quotient, an exception will also be thrown, but only after indicating what the rational values would be. As an example, the attempt to divide ⟨ +2, +4, −6, −8, +10 ⟩ by ⟨ +11, −12, +13, −14, +15 ⟩ will generate the following report:
cos_int_dom ... non-integral quotient:
C1/6 = -72713 / +99442 approx -0.731210
C2/6 = +5362 / -7103 approx -0.754892
C3/6 = +100769 / +99442 approx 1.013344
C4/6 = +9212 / +7103 approx 1.296917
C5/6 = +9775 / -99442 approx -0.098299
real value: -0.040982
*** fail *** cos_int_dom::operator/ ...quotient not an integer ***
which in better typography is:

 C1/6 = −72,713 ÷ +99,442 ≈ −0.731210 C2/6 = +5,362 ÷ −7,103 ≈ −0.754892 C3/6 = +100,769 ÷ +99,442 ≈ 1.013344 C4/6 = +9,212 ÷ +7,103 ≈ 1.296917 C5/6 = +9,775 ÷ −99,442 ≈ −0.098299 real value ≈ −0.040982

These figures may help the researcher diagnose unexpected results.

Support is provided for arithmetic with two operands of different order but the same step. For instance, if a cid of order 3 is added to a cid of order 5, the order of the result will be the least common multiple of 3 and 5, namely 15:

⟨ 1, 2 ⟩ + ⟨ 3, 4, 5, 6 ⟩ = ⟨ 0, 0, 3, 0, 1, 4, 0, 0, 5, 2, 0, 6, 0, 0 ⟩.

Support is also provided for arithmetic with two operands of different step but the same order. The result will be of step 1.

There is not a test for equality, as this depends on real numbers, which are represented only approximately by the double-precision floating-point numbers of C++. A user must provide his/her own strategy for managing error if one is needed.

On the other hand, there are non-member functions to test for isomericity:

template <int order, typename coef, int step>
bool isomeric (
cos_int_dom<order,coef,step> const &,
cos_int_dom<order,coef,step> const &
);

template <int order, typename coef, int step>
bool anisomeric (
cos_int_dom<order,coef,step> const &,
cos_int_dom<order,coef,step> const &
);

// anisomeric == ! isomeric

An unusual operation has been provided. Named dot, it resembles the standard inner product of linear algebra, but it is not quite the same. If cids A and B are of the same order; then by definition:

 dot (A, B) ⇔ A · B = ⟨ a1b1 (C1/n)2 + a2b2 (C2/n)2 + a3b3 (C3/n)2 + … + an−1bn−1 (C(n−1)/n)2 ⟩

If the inputs are cisds, appropriate terms in the series are skipped. The result will be a step-2 cisd, even if the inputs were step-1 cids.

The C++ definition of the function is:

template <int order, typename coef, int step>
cos_int_dom<order,coef,2> dot (
cos_int_dom<order,coef,step> const & a,
cos_int_dom<order,coef,step> const & b
);