﻿ Schematic algebra - G-Systems

# Schematic algebra - G-Systems

You're reading an English translation of the original Czech page.

## G-Systems - An algebraic theory of musical structures

Combinatorics of necklaces...

An algebraic theory of chord structures is being presented in this paper. Every tone grouping is depicted as an instance of the so-called G-system. The aim is to provide a simple algorithm for a generation of musical structures. It should be useful for programmers of computer music as well as for those interested in musical analysis. The theory of G-systems gives some known mathematical results in a simple and clearly organized way. Therefore it might be inspiring for mathematicians studying methods of enumeration, theory of groups, algebraic solutions of combinatorial problems and other areas (Fermat's theorems, Gauss' theory of equation classes, Polya's enumeration, Sylowov's groups,..).

#### 1.G-system and its instances

The area we are studying here is in the combinatorial theory known as Combinatorics of necklaces.

#### 1.1 Elementary definitions

Let us think about arranging n elements into k cells. Let A be a set with n members (elements) and the set E(A) = {0, 1, .., n-1} the base of A. Let B be a set with k members (cells) and ξ relation from E(B) to E(A).

```                       ξ
(cells)  E(B)  -------------  E(A)  (elements)
```

Let numbers E(B) be positions of numbers (digits) from E(A). Written in n-number system we obtain nk possible numbers. Let the set of all these numbers be marked M()= M(n,k). Members of this set are so called instances.
E.g. the sets A={p, q}, B={x, y, z} have E(A)={0, 1}, E(B)={0, 1, 2} as their bases. The system M(2,3) has 23=8 instances {000, 001,.., 111}.

Let us call the set M()=M(n,k) (with relation ξ) system of degree n and order k. If ξ is equivalence relation one can distinguish some instance classes. The classes are the result of decay M()/ξ. Each class has its representative number. Number of transpositions means the number of members in a class.
In case of 12-tone tempered musical system we have n=2, k=12. E.g. let A={exist, non-exist} and B={c, c#, d, d#, e, f, f#, g, g#, a, a#, h} . The bases E(A)={0, 1}, E(B)={0, 1, .., 11} and the ξ relation forms the system M(2,12). The instance 001001001001 represents tone groupings [c, d#, f#, a] and has two transpositions 010010010010, i.e. [c#, e, g, a#] and 100100100100 i.e. [d, f, g#, h]. The diminished seventh chord is a class of M(2,12) with 3 transpositions.

#### 1.2 G-relation

Let relation G, defined as follows, be called G-relation.

#### u(i,j) = nj * g(i) ( mod(r-1))

Number r is (in this article) always assumed to be equal to the total number of instances, i.e. r = nk. Number g(i) is representative number, u(i,j) are instance numbers.

Systems with the G-relation we name G-systems, G()=G(n,k). Every G(n,k) has m(n,k) classes marked g(i), i=1..m.

#### 1.3 Instance numbers

Let us write an outline of all instances ordered by classes. The outline of G(n,k) has k columns (k is the maximum transposition count). The 16 instances of G(2,4) make 6 classes.

Instances of G(2,4)

 1 ``` 0 0 0000 0 0 0``` 2 ``` 0 0 0 1 1 0 0 0 0001 0010 0100 1000 1 2 4 8 0 1 0 0 0 0 1 0``` 3 ``` 0 1 1 1 1 0 0 0 0011 0110 1100 1001 3 6 12 9 0 1 0 0 1 0 1 1``` 4 ``` 1 0 0 1 0101 1010 5 10 0 1 1 0``` 5 ``` 1 1 1 1 1 0 0 1 0111 1110 1101 1011 7 14 13 11 0 1 1 0 1 1 1 1``` 6 ``` 1 1 1111 15 1 1```

#### 1.4 Generation of instance numbers

The algorithm is similar to the Eratosthenes' sieve for separating primes from natural numbers. In our case we separate numbers of classes representatives from all instance numbers. Instance transpositions are analogies of prime multiples in Eratosthenes' sieve.

```        empty set M
↓
+--+- for g=0 to (nk-1-1) -- write the last class
|  |          |                     g=nk-1
|  ↑   is class g in M ?
|  |          |
|  +- YES-----+
|             |NO
|             |
|        write g to M
|             ↓
|     instance u <- g
|             |
|+---> while not u in M ----+
||            |             |
||       write u to M       |
||            |             |
||   instance transposition |
||        u <- n * u        |
|+------<-----+             |
+-------------<-------------+
```

Examples of the output:

```G(2,1)          G(3,1)           G(4,1)
0            0              0
1            1              1
2              2
3
```
```G(2,2)         G(3,2)          G(4,2)
0             0              0             6  9
1  2          1  3           1  4          7 13
3             2  6           2  8         10
4              3 12         11 14
5  7           5            15
8
```
```G(2,3)         G(3,3)          G(4,3)
0             0              0             21
1  2  4       1  3  9        1  4 16       22 25 37
3  6  5       2  6 18        2  8 32       23 29 53
7             4 12 10        3 12 48       26 41 38
5 15 19        5 20 17       27 45 54
7 21 11        6 24 33       30 57 39
8 24 20        7 28 49       31 61 55
13              9 36 18       42
14 16 22       10 40 34       43 46 58
17 25 23       11 44 50       47 62 59
26             13 52 19       63
14 56 35
15 60 51
```

#### 1.5 Divisibility in G(n,k)

Instance number u(i,j) is prime relative to r -1 = nk -1 only if corresponding class number g(i) is prime relative to r -1. The number of all instances that are primes relative to r -1 is φ(r), where φ is the Euler function. If g(i) is prime relative to r -1, then its class must be the self class (not nested) and such class has k instances.
Therefore: φ(nk -1)= 0 (mod k)
In G(2,4) only these instances are prime numbers relative to 24 -1=15: (1, 2, 4, 8) and (7, 14, 13, 11). And φ(24 -1) = φ(15) = 8; 8 = 0 (mod 4).

#### 2.Enumeration of classes

One of the first solutions to the problem we are studying was published by Gauss in his algebraic theory of equation classes [Gauss,1959]. Polya presented a general combinatorial solution of counting structures. His theorem of enumeration [Preparata,1974] was designed for counting of classes with regard to arbitrary operations of symmetry. Musical chord structures have only one such operation - rotation. This fact allows us to apply a simple algorithm.

#### 2.1 Nesting

For each d|k there exists a system G(n,d) nested to the G(n,k). The nested class g' in G(n,k) is similar to its original class g from G(n,d). Truly original classes are called self-classes. The similarity to the original classes means the same number of transpositions and similar instance structures. The system G(n,p), p is prime, has just one nested system G(n,1). For g from G(n,d), g' from G(n,k), d|k it holds: g' = c . g where c is nesting quotient defined as follows:
c(d,k) = (nk-1) / (nd-1). For example, the system G(2,6) inherits the nested systems G(2,1), G(2,2) a G(2,3);
G(2,1) is also nested into G(2,2) and G(2,3).

Other example: the system G(2,4) inherits the nested systems G(2,1) and G(2,2); see e.g. class g(2) = 1 in G(2,2) and its corresponding class g(4) = 5 in G(2,4) with nesting quotient c(2,4) = 5.

```G(2,1):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1
```
```G(2,2):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1 u(1,2)= 2
g(3)= u(0,3)= 3
```
```G(2,4):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1   u(1,2)= 2    u(2,2)= 4   u(3,2)= 8
g(3)= u(0,3)= 3   u(1,3)= 6    u(2,3)=12   u(3,3)= 9
g(4)= u(0,4)= 5   u(1,4)=10
g(5)= u(0,5)= 7   u(1,5)=14    u(2,5)=13   u(3,5)=11
g(6)= u(0,6)=15
```
Nesting quotients:
``` G(2,1) - G(2,2): c(1,2) = (22 -1) / (21  -1) = 3
G(2,2) - G(2,4): c(2,4) = (24 -1) / (22 -1) = 5
```

#### 2.2 Recurrent relations

Let v(n,k), w(n,k) and m(n,k) be the number of self, nested and all classes in G(n,k). It is hold:

Specially for prime p is:

E.g. The system G(2,6) has 14 classes (9 self-classes + 5 nested-classes):

Counting of classes in G(2,6)

 Self classes Nested classes v(2,1)=2/1=2 w(2,1) = 0 v(2,2)=(22-1v(2,1))/2= 1 w(2,2) = v(2,1) = 2 v(2,3)=(23-1v(2,1))/3= 2 w(2,3) = v(2,1) = 2 v(2,6)=(26-1v(2,1)-2*v(2,2)-3*v(2,3))/6 = 9 w(2,6) = v(2,1)+v(2,2)+v(2,3)= 5

Therefore m(2,6)= v(6) +w(6) = 9 +5 = 14 classes.

Gauss [CG1} has put the previous recurrent equations in an elegant, compact form: nk = ∑ d(d) i.e. in our terminology: nk = ∑{d|k} d*v(n,d).

#### 2.3 Simplifying

Let us evaluate the totals of all classes m(n,k) for particular orders k as functions of n:

```k=1: m(n,1)= 1/1 (n) + 0 = n
k=2: m(n,2)= 1/2 (n2- n)+ n = 1/2 (n2+n)
k=3: m(n,3)= 1/3 (n3-n)+ n = 1/3 (n3+ 2n)
k=4: m(n,4)= 1/4 (n4-n2)+ 1/2 (n2+n) = 1/4 (n4+ n2+2n)
k=5: m(n,5)= 1/5 (n5-n) + n = 1/5 (n5+ 4n)
k=6: m(n,6)= 1/6 (n6-n3-n2+n)+1/6(2n3+3n2+n)= 1/6 (n6+n3+2n2+2n)
k=7: m(n,7)= 1/7 (n7-n) + n = 1/7 (n7+ 6n)
k=8: m(n,8)= 1/8 (n8-n4)+ 1/4(n4+n2+2n)=1/8(n8+n4+2n2+4n)
```

In case of rotational operations Polya's theory gives this result [Beckenbach,1964]:

#### m(n,k) = 1/k ∑{d|k} φ(d)* nk/d (including d=k),

where φ is the Euler function.

#### 3.1 Segmentation

The nesting (shown in the previous paragraphs) is a matter of G-systems with constant n.
Now we are going to study G-systems with constant k. These systems also have something in common.
E.g. let us see the systems G(2,2) and G(3,2). The latter is only an extension of the former.

G(3,2) as an extension of G(2,2)

 ``` G(2,2) = G(3,2) 0 0 1 2 1 3 3 4 6 2 7 5 8 ```

Every G(n,k) has n classes nested from G(n,1). Let us assume, these classes separate the G-system into segments. Let s (s<n )="" such="" a="" representative="" of="" this="" segment="" s="" is="" the="" number="">
g(s) = (n-s) * (nk-1) / (n-1).
If a segment exists in G(n,k) then a similar segment exists also in G(n+1,k). This idea becomes clearer if we rewrite all the numbers u with the numbers (nk-1)-u.

Segmentation of G(3,3)

 ``` u ``` ``` 0 segment 2 1 3 9 2 6 18 4 12 10 5 15 19 7 21 11 8 24 20 ------------------ 13 segment 1 14 16 22 17 25 23 ------------------ 26 segment 0 ``` ``` (nk-1)-u = 27-u ``` ``` 0 segment 0 ------------------ 9 1 3 12 10 4 13 segment 1 ------------------ 18 2 6 19 5 15 21 11 7 22 14 16 24 20 8 25 23 17 26 segment 2 ```

#### 3.2 Number systems

Let us write the numbers nk-1-u from the previous table as functions of n and take interest in quotients of the polynomials:

```k=2                      k=3
segment 0                      segment 0
1                        1
segment 1                      segment 1
n       1                n2            1        n
n+1                      n2+n          n2+1    n +1
n2+n+1
```
The quotients of these polynomials are:
```k=2                      k=3
segment 0                      segment 0
0 0                       0 0 0
segment 1                      segment 1
1 0    0 1                1 0 0      0 0 1      0 1 0
1 1                       1 1 0      1 0 1      0 1 1
1 1 1
```

Each G-system is a set of numbers from the n-th number system. The G-relation separates G(n,k) into n segments, where every segment s uses always just s symbols, s=0..n-1.

Compositions of G-systems

 ```G(1,2) 00 00 00 ---------------------------- 10 01 10 01 10 01 G(2,2) 11 11 11 ---------------------------- 20 02 20 02 20 02 21 12 21 12 21 12 G(3,2) 22 22 22 ---------------------------- 30 03 30 03 31 13 31 13 32 23 32 23 G(4,2) 33 33 ---------------------------- 40 04 41 14 42 24 43 34 G(5,2) 44 ---------------------------- ``` ```G(1,3) 000 000 000 -------------------------------------------- 100 001 010 100 001 010 100 001 010 110 101 011 110 101 011 110 101 011 G(2,3) 111 111 111 -------------------------------------------- 200 002 020 200 002 020 201 012 120 201 012 120 210 102 021 210 102 021 211 112 121 211 112 121 220 202 022 220 202 022 221 212 122 221 212 122 G(3,3) 222 222 -------------------------------------------- 300 003 030 301 013 031 302 023 032 310 103 130 311 113 131 312 123 132 320 203 230 321 213 231 322 223 232 330 303 330 331 313 331 332 323 332 G(4,3) 333 -------------------------------------------- ```

The sum of polynomial quotients is the same for all instances of a given class (the instances of a class have the same level).

#### 4.Binary G-systems

Binary system G(2,k) is a special case of G-system, n=2. It is suitable for classification of musical structures.

#### 4.1 Distance schema

In a binary system (base E(A) ={0, 1}) it is easy to express structure of instances.
Let level of class L be the number of digits "1" in an instance and let interval be the distance between two digits "1". Distance schema is the list of all neighboring intervals, last interval in brackets, [Janecek,1959].

Distance schema of instances in G(2,4))

 ```i g(i) Instance numbers (binary) Schema Level ------------------------------------------------------ 1 0 0000 (0) 0 2 1 0001 0010 0100 1000 (4) 1 3 3 0011 0110 1100 1001 1(3) 2 4 5 0101 1010 2(2) 2 5 7 0111 1110 1101 1011 1 1(2) 3 6 15 1111 1 1 1 (1) 4 ```

#### 4.2 Triangles

The last column in the previous table displays the level of the corresponding class i.e. level of instances of the class. Let us count how many instances and classes there are on each level.

Counting in G(2,4)

 ```Level 0 1 2 3 4 ----------------------------------------- All instances 1 4 6 4 1 Nested instances 1 0 2 0 1 Self instances 0 4 4 4 0 ----------------------------------------- All classes 1 1 2 1 1 Nested classes 1 0 1 0 1 Self classes 0 1 1 1 0 ```

The following diagrams display the same (structured into triangles) for all G(2,k). The first column displays the order k of given G-system, in the next columns are the counts for particular levels. The last columns have the totals of instances or classes. The triangles are symmetrical, we write only half of them.
E.g. in 12-tone music there are 220 triads in 19 classes. These 19 classes mean that 19 types of triads exist (minor, major, augmented, diminished, ...). One class only (the augmented triad) is nested. This class has 4 instances. Therefore there is 220-4=216 self-instances of triads and 216/12 = 19-1 = 18 self-classes of triads.

``` k  (0)(1)(2)(3) (4) (5) (6) (7) (8) (9)(10)(11)(12)
----------------------------------------------------------------------
12   1  12 66 220 495 792 924 792 495 220 66  12  1    all instances
----------------------------------------------------------------------
1   1                                            1
2   0                      2                     0
3   0              3               3             0    nested instances
4   0          4           4           4         0
6   0      6      12      18      12      6      0
----------------------------------------------------------------------
12   0  12 60 216 480 792 900 792 480 216 60  12  0    self instances
12   0   1  5  18  40  66  75  66  40  18  5   1  0    self classes
----------------------------------------------------------------------
1    1                                            1
2    0                      1                     0
3    0              1               1             0    nested classes
4    0          1           1           1         0
6    0      1       2       3       2      1      0
----------------------------------------------------------------------
12   1   1  6  19  43  66  80  66  43  19  6   1  1    all classes
```

Self-instance and self-classes triangle

Nested instance and nested classes triangle

All instance (Pascal triangle) and all classes triangle

The total number of nested instances as well as nested classes in a system with prime k is equal to 2. Number of self-instances is always the k-multiple of the number of self-classes.
more

#### Conclusion

In this paper we presented an insight into the problem of musical structures. Our results were compared with similar results obtained by Gauss and by Polya. The theory of G-systems also has some connections to others mathematical areas.
E.g. a restriction of G-systems (r<nk) leads to the theory of primitive roots; the distribution of prime numbers in particular classes might give some information about primes;...
Particularly, the triangle of self-classes might be interesting. Some theorems about primes (Wilson theorems,...) are connected with its structure. The triangle seems to be more general then Pascal triangle - the latter can be obtained by an integration of members from the former.

The theory of G-systems was presented at the poster session of the Conference on Computational and Mathematical Methods in Music, Vienna, December 1-4, 1999 (Diderot Forum on Mathematics and Music). The text, which follows, covers and extends the one printed in the conference proceedings.
At the beginning I called these systems by a term "Genetic systems", because of certain analogy with inheritance (see Nesting of G-systems). Later I have shortened the name to "G-systems". I worked on this theory mostly in the years 1990-1992. In the following years, 1993-1996, I looked for a similar theories in the literature.
The enumeration of total number of G-system classes is the same as the enumeration of total number of equation classes, which was studied by Carl Fridrich Gauss nearly 200 years ago. So the letter G in the name "G-system" would be connected with Gauss. He was probably the first one who knew and described these mathematical constructions.

#### Bibliography

Gauss,1959 Gauss Carl Fridrich: Trudy po teorii cisel (Ucenie o vycetach II),p.782) (Works on Theory of Numbers; in Russian), Moscow 1959.
Janecek,1959 Janeček Karel: Základy moderní harmonie (Fundamentals of Modern Harmony; in Czech), Prague 1965.
Beckenbach,1964 Edwin F.Beckenbach, George Polya: Applied Combinatorial Mathematics University of California, John Wiley and Sons,Inc , New York, 1964.
Preparata,1974 Franco P.Preparata, Raymond T.Yeh Introduction of Discrete Structures Addison-Wesley Publishing Company Inc., U.S.A., 1974.