Schematická algebra - G-Systémy

g_system_2_4

G-Systémy - Algebraická teorie hudebních struktur

V tomto textu je představena algebraická teorie souzvukových druhů. Každé uskupení tónů je zobrazeno jako instance takzvaného G-systému. Cílem je opatřit jednoduchý algoritmus pro generování hudebních struktur. Mohl by být užitečný pro programátory zabývající se počítačovou hudbou nebo analýzou hudby. Teorie G-systemů dává některé známé matematické výsledky jednoduchým a jasně uspořádaným způsobem. Proto by mohla být inspirující pro matematiky studující metody enumerací, teorii grup, algebraická řešení kombinatorických problémů a jiné oblasti (Fermatovy věty, Gaussova theorie tříd rovnic, Polyova enumerace, Sylowovy grupy,..).

1.G-systémy a jejich instance

1.1 Základní definice

Uvažujme uspořádání n prvků do k buněk. Nechť A je množina s n členy (prvky) a množina E(A) = {0, 1, .., n-1} báze množiny A. Nechť B je množina s k členy (buňkami) a ξ relace z E(B) do E(A).

                    ξ
   (buňky)  E(B)  -------------  E(A)  (prvky)
  

Nechť čísla E(B) jsou pozice čísel (číslic) z E(A). Přepisem do n-kové soustavy získáme nk možných čísel. Označme množinu všech těchto čísel be M()=M(n,k). Členy této množiny jsou tzv. instance.
Např. množiny A={p, q}, B={x, y, z} mají báze E(A)={0, 1}, E(B)={0, 1, 2}. Systém M(2,3) má 23=8 instancí {000, 001,.., 111}.

Množinu M()=M(n,k) (s relací ξ) budeme nazývat systém stupně n a řádu k. Jestliže ξ je relace ekvivalence, je možné rozlišit druhy instancí. Druhy jsou výsledkem rozkladu M()/ξ. Každý druh má své reprezentanty. Počet transpozic znamená počet členů druhu.
V případě 12-ti tónového temperovaného hudebního systému máme n=2, k=12. Např. nechť A={existuje, neexistuje} a B={c, c#, d, d#, e, f, f#, g, g#, a, a#, h}. Báze E(A)={0,1}, E(B)={0, 1, .., 11} a relace ξ utvářejí system M(2,12). Instance 001001001001 representuje tónové uskupení [c, d#, f#, a] a má dvě transpozice 010010010010, tj. [c#, e, g, a#] a 100100100100 tj. [d, f, g#, h]. Zmenšený septimový akord je druh z M(2,12) s 3-mi transpozicemi.

1.2 G-relace

Budiž relace G, definována následovně, nazývána G-relace.

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

Číslo r je (v tomto článku) vždy předpokládáno rovné celkovému počtu instancí, tj. r = nk. Číslo g(i) is číslo reprezentanta, u(i,j) jsou čísla instancí.

Systemy s G-relací nazýváme G-systemy, G()=G(n,k). Každý G(n,k) má m(n,k) druhů označených g(i), i=1..m.

1.3 Čísla instancí

Zapišme přehled všech instancí uspořádaný podle druhů. Přehled pro G(n,k) má k sloupců (k je nejvyšší možný počet transpozic). 16 instancí z G(2,4) vytváří 6 druhů.

Instance 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 Generování čísel instancí

Algoritmus je podobný Eratosthenovu sítu pro vyčlenění prvočísel z přirozených čísel. V našem případě vyčleňujeme čísla representantů druhů z čísel všech instancí. Transpozice instancí jsou analogie prvočíselných násobků v Eratosthenově sítu.

        vyprázdni množinu M
                ↓
  +--+- pro g=0 až (nk-1-1) -- zapiš poslední druh
  |  |          |                     g=nk-1
  |  ↑   je druh g v M ?
  |  |          |
  |  +- ANO-----+
  |             |NE
  |             |
  |        zapiš g do M
  |             ↓
  |     instance u <- g
  |             |
  |+---> dokud není u v M ----+
  ||            |             |
  ||       zapiš u do M       |
  ||            |             |
  ||   transpozice instance   |
  ||        u <- n * u        |
  |+------<-----+             |
  +-------------<-------------+

Příklady výstupu:

G(n,1)
G(2,1)          G(3,1)           G(4,1)
    0            0              0
    1            1              1
                 2              2
                                3
G(n,2)
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(n,3)
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 Dělitelnost v G(n,k)

Číslo instance u(i,j) je relativním prvočíslem s r -1 = nk -1 jen když odpovídající číslo druhu g(i) je relativním prvočíslem s r -1. Počet všech instancí, která jsou relativními prvočísly s r -1 je φ(r), kde φ je Eulerova funkce. Jestliže g(i) relativním prvočíslem s r -1, pak jeho druh musí být vlastní (ne vnořený) a takový druh má k instancí.
Proto: φ(nk -1)= 0 (mod k)
V G(2,4) jen tyto instance jsou relativní prvočísla s 24 -1=15: (1, 2, 4, 8) a (7, 14, 13, 11). A φ(24 -1) = φ(15) = 8; 8 = 0 (mod 4).

2.Enumerace druhů

Jedno z prvních řešení problému, který studujeme, bylo publikováno Gaussem v jeho algebraické theorii tříd rovnic [Gauss,1959]. Polya předvedl obecné kombinatorické řešení pro počítání struktur. Jeho enumerační věta [Preparata,1974] byla navržena pro počítání tříd s ohledem na libovolné operace symmetrie. Akordické hudební struktury mají jen jednu takovou operaci - rotaci. Tento fakt nám umožňuje použít jednoduchý algoritmus.

2.1 Vnořování

Pro každé d|k existuje system G(n,d) vnořený do G(n,k). Vnořený druh g' v G(n,k) je podobný svému výchozímu druhu g z G(n,d). Skutečně původní druhy jsou nazývány vlastní druhy. Podobnost s výchozími druhy znamená týž počet transpozic a podobné instanční struktury. System G(n,p), p je prvočíslo, má právě jeden vnořený system G(n,1). Pro g z G(n,d), g' z G(n,k), d|k platí: g' = c . g kde c ke keficient vnoření definovaný následovně:
c(d,k) = (nk-1) / (nd-1). Např. systém G(2,6) získává (dědí) vnořené systémy G(2,1), G(2,2) a G(2,3);
G(2,1) je také vnořený do G(2,2) a G(2,3).
g_nest

Jiný příklad: systém G(2,4) dědí vnořené systémy G(2,1) a G(2,2); viz např. druh g(2) = 1 v G(2,2) a jí odpovídající druh g(4) = 5 v G(2,4) s koeficientem vnoření 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
Koeficienty vnoření:
 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

více

2.2 Rekurentní vztahy

Nechť v(n,k), w(n,k) a m(n,k) jsou počty vlastních, vnořených a všech druhů v G(n,k). Platí:
g_rec1
Specielně pro prvočíslo p je:
g_rec2
Např. System G(2,6) má 14 druhů (9 vlastních + 5 vnořených):

Počítání druhů v G(2,6)

Vlastní druhy

Vnořené druhy

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


Proto m(2,6)= v(6) +w(6) = 9 +5 = 14 druhů.

Gauss [CG1} předložil předchozí rekurentní rovnice v elegantním, kompaktním tvaru: nk = ∑d(d) tj. v naší terminologii: nk = ∑{d|k} d*v(n,d).

2.3 Zjednodušování

Vyčísleme součty všech druhů m(n,k) pro jednotlivé řády k jako funkce 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)

V případě rotačních operací dává Polyova teorie tento výsledek [Beckenbach,1964]:

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


kde φ je Eulerova funkce.

3.Skladba G-systémů

3.1 Segmentace

Vnořování (ukázané v předchozích odstavcích) je záležitostí G-systemů s konstantním n.
Nyní budeme vyšetřovat G-systemy s konstantním k. Tyto systémy také mají něco společného.
Např. podívejme se na systémy G(2,2) a G(3,2). Druhý je jen rozšířením prvního.

G(3,2) jako rozšíření G(2,2)

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

Každý G(n,k) má n druhů vnořených z G(n,1). Předpokládejme, tyto druhy rozdělují G-system do segmentů. Nechť s (s<n )="" takov="" segment="" representantem="" tohoto="" segmentu="" s="" je="" číslo="">
g(s) = (n-s) * (nk-1) / (n-1).
Jestliže nějaký segment existuje v G(n,k), pak podobný segment existuje také v G(n+1,k). Tato myšlenka se objasní, když přepíšeme všechna čísla u čísly (nk-1)-u.

Segmentace 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 Číselné soustavy

Zapišme čísla nk-1-u z předchozí tabulky jako funkce n a podívejme se na koeficienty polynomů:

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

Každý G-system je množinou čísel z n-kové číselné soustavy. G-relace rozděluje G(n,k) do n segmentů, kde každý segment s užívá právě s symbolů, s=0..n-1.

Skladba G-systemů

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
--------------------------------------------
--------------------------------------------


více

Součet polynomických koeficientů je stejný pro všechny instance daného druhu (instance téhož druhu mají stejnou úroveň).

4.Binární G-systémy

Binarní systém G(2,k) is zvláštní případ G-systemu, n=2. Je vhodný pro klassifikaci hudebních struktur.

4.1 Distanční schema

V binarním systému (base E(A) ={0, 1}) je snadné vyjádřit strukturu instancí.
Nechť úroveň druhu L je počet číslic "1" v instanci a nechť interval je vzdálenost mezi dvěma číslicemi "1". Distanční schéma je výpis všech sousedících intervalů, poslední interval v závorkách, [Janecek,1959].

Distanční schéma instancí v G(2,4))

i  g(i) Instance čísla (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


více

4.2 Trojúhelníky

Poslední sloupec předchozí tabulky zobrazuje úroveň odpovídajícího druhu, tj. úroveň instancí druhu. Spočítejme kolik instancí a druhů je na každé úrovni.

Počítání v G(2,4)

Úroveň                0    1    2    3    4
--------------------------------------------
Všechny instance      1    4    6    4    1
Vnořené instance      1    0    2    0    1
Vlastní instance      0    4    4    4    0
--------------------------------------------
Všechny druhy         1    1    2    1    1
Vnořené druhy         1    0    1    0    1
Vlastní druhy         0    1    1    1    0

Následující schemata zobrazují totéž (strukturováno do trojúhelníků) pro všechna G(2,k). První sloupec zobrazuje řád k daného G-systemu, v dalších sloupcích jsou počty pro jednotlivé úrovně. Poslední sloupce obsahují součty instancí a druhů. Trojúhelníky jsou symmetrické, zapisujeme jen jejich polovinu.
Např. v 12-ti tónové hudbě je 220 trojzvuků, 19-ti druhů. Těchto 19 druhů znamená, že existuje 19 typů trojzvuků (moll, dur, zvětšený, zmenšený, ...). Jeden jediný druh (zvětšený trojzvuk) je vnořený. Tento druh má 4 instance. Proto je 220-4=216 vlastních instancí trojzvuků a 216/12 = 19-1 = 18 vlastních druhů trojzvuků.

 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    všechny instance
----------------------------------------------------------------------
 1   1                                            1
 2   0                      2                     0
 3   0              3               3             0    vnořené instance
 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    vlastní instance
12   0   1  5  18  40  66  75  66  40  18  5   1  0    vlastní druhy
----------------------------------------------------------------------
1    1                                            1
2    0                      1                     0
3    0              1               1             0    vnořené druhy
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    všechny druhy

Trojúhelník vlastních instancí a vlastních druhů

g_t1

g_t2

Trojúhelník vnořených instancí a vnořených druhů

g_t3

g_t4

Trojúhelník všech instancí (Pascalův) a všech druhů

g_t5

g_t6

Celkový počet vnořených instancí stejně tak jako vnořených druhů v systému s prvočíselným k je roven 2. Počet vlastních instancí je vždy k-násobkem počtu vlastních druhů.
více

Závěr

V článku byl představen náhled do problému hudebních structur. Výsledky byly porovnány s podobnými výsledky získanými Gaussem a Polyou. Teorie G-systémů má také vazby do jiných matematických oblastí.
Např. omezení systemů (r<nk) vede k teorii primitivních kořenů; rozložení prvočísel v jednotlivých druzích by mohlo poskytnout nějaké informace o prvočíslech;...
Zvláště trojúhelník vlastních druhů by mohl být zajímavý. S jeho strukturou jsou spojeny některé věty o prvočíslech (Wilsonova věta,...). Trojúhelník se zdá být obecnější než Pascalův trojúhelník - Pascalův může být získán integrací jeho členů.

Teorie byla prezentována v poster-sekci Conference on Computational and Mathematical Methods in Music, ve Vídni, 1.-4.prosince 1999 (Diderot Forum on Mathematics and Music). Text, jenž následuje, pokrývá a rozšiřuje text otištěný ve sborníku konference.
Na začátku jsem nazýval tyto systémy pojmem "Genetické systémy", pro jistou analogii s dědičností (viz Vnořování G-systemů). Později jsem jméno zkrátil na "G-systemy". Na teorii jsem pracoval převážně v letech 1990-1992. V letech následujících, 1993-1996, pak hledal podobné teorie v literatuře.
Enumerace celkového počtu druhů v G-systemu je shodná s enumerací celkového počtu tříd rovnic, která byla studována Carl Fridrichem Gaussem zhruba před 200 lety. Takže písmeno G ve jménu "G-system" by mohlo být spojeno s Gauss. Byl pravděpodobně první, kdo znal a popsal tyto matematické konstrukce.

Literatura

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.