CNB10 Multiplication of two cycle-numbers
12 September 2012
A number system would be sadly lacking in interest if you couldn’t ‘do things’ with the numbers, wouldn’t it? So far I have only shown you how we can look for (0,1)-patterns in triangle T, or in the matrix C. In this Blog I will introduce a way of multiplying two cycle-numbers, say m and n.
This operation has one obvious requirement, that the result shall be a cycle-number (say k) which has its number of (0,1) -symbols equal to mxn. For the new product, we shall write mΛn = k , where Λ (lambda or cap) is the symbol for our new multiplication operation. In the definition of cap, given below, it will be observed that we first work with the fundamental cycles of m and n , to obtain k‘ (the f.c. of k); and then, of course, we cycle it indefinitely to achieve the cycle-number k. Observe also that we shall have occasion to multiply pairs of (0,1)-symbols from within two cycle-numbers, and for this we shall use the same symbol Λ which then follows the multiplication rules: 0Λ0 = 0, 0Λ1 = 0, 1Λ0 = 0, and 1Λ1 = 1. That is a very simple Boolean multiplication table to remember! It follows the same rules as for ordinary multiplication of 0s and 1s.
Definition: The ‘cap product’ (we sometimes write ‘Boolean Product’, or BP, for this) of two cycle-numbers, is given by the following formula: (mΛn)‘ = k‘ ≡ [n*(m‘)] Λ [m*(n‘)] , where * is the ‘conjoin’ operation for strings. Then cycling of k‘ results in the cycle-number k. The expressions in the square brackets both have length mn, so they can be cap multiplied, taking corresponding elements from the brackets and multiplying them together, using the 0,1 multiplication rules given above (c.f. any element-wise operation on two vectors of equal length).
An example will make the product definition clear.
Let m‘ = (10)’ = 2‘ , and n‘ = (110)’ = 3‘. We shall set out the cap product operation by writing the first [-] expression from the definition on an upper line, and the second [-] expression directly below it on a lower line. Then we shall compute the element-wise operations on each of the vertical two-vector pairs, thereby obtaining the string which is k‘
n*2′ = 1 0,1 0,1 0 (3 conjoins of the f.c. of 2 ; commas not generally shown)
m*3‘ = 1 1 0, 1 1 0 (2 conjoins of the f.c. of 3 ; commas not generally shown)
Λ = 1 0 0 0 1 0 = k‘ = 6‘ .
This looks much like our long multiplication procedure with decimal numbers, doesn’t it? But now everything is much simpler, since we only have to multiply pairs of binary digits, arranged vertically in 2-vecs. Each product yields a result 0 or 1, so there is no ‘carrying’ to be done.
The so-called 2-vecs: In obtaining the final line of this calculation, we applied Λ to six (0,1)– pairs arranged vertically. These pairs are:
1 , 0 , 1 , 0 , 1 , 0
1 , 1 , 0 , 1 , 1 , 0 .
In order to classify these 2-vecs, we observe that only 4 different such vectors are possible, with the two-element alphabet {0,1}, and we label these by the letters d,e,f,g thus:
Labels: d = (0,0)’ ; e = (0,1)’ ; f = (1,0)’ ; g = (1,1)’ (here we use the prime symbol ‘ to denote vector transposition).
Counting the frequencies of 2-vecs in a product:
Given any pair m, n of cycle-numbers, it is possible to compute the frequencies of the types of 2-vecs in their cap product. (These counts prove to be a very useful tool in a later study of cycle-numbers.) We shall call these frequencies #d, #e, #f, #g respectively, and give, without proof, the formulae for obtaining them. Thus: let m0 and m1 be respectively the number of 0s and the number of 1s in m‘, and similarly let n0 and n1 be respectively the number of 0s and the number of 1s in n‘ : then the required formulae are:
#d = m0xn0 ; #e = m0xn1 ; #f = m1xn0 ; #g = m1xn1 .
N.B. These formulae are attractive and simple, for they follow exactly the pattern of rules given above for the cap product on {0,1}. I gave a general proof for my cap product of any two (0,1)-strings, in Ref.[1]. It is long and messy! I am sure there must be a much simpler way of going about it.
To demonstrate, using the example for m = 2 and n = 3 given above, we see that:
for m‘ = 1 0 , m0 = 1 and m1 = 1 : whereas for n‘ = 1 1 0 , n0 = 1 and n1 = 2 .
Therefore: #d = m0xn0 = 1 ; #e = m0xn1 = 2 ; #f = m1xn0 = 1 ; #g m1xn1 = 2 .
We check this by writing out again the 2-vec table, and writing the d,e,f,g classifications below each column; then counting the different types. Thus:
1 , 0 , 1 , 0 , 1 , 0
1 , 1 , 0 , 1 , 1 , 0
g , e , f , e , g , d … so there are indeed, one d, two es, one f and two gs.
This Blog contains more than enough material for a blog; but it is vital stuff for cycle-number theory.
Bye for now.
[see CNB12 for more info. on the 2-vecs]