﻿ Schematic algebra - Nesting

# Schematic algebra - Nesting

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

## Nesting of G-systems

### Self and nested classes

For each d|k there exists system G(n,d) nested into G(n,k). Nested class g' v G(n,k) is similar to original class g from G(n,d).  (Similarity is given by the same number of transpositions and an analogous inner structure of instances).  Really-original classes are called self classes. 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 quotient of nesting defined:

#### c(k,d) = (nk−1) / (nd−1)

Into system G(2,4)  systems G(2,1) a G(2,2) nests.

E.g. class g(2) = 1 from G(2,2) enter into G(2,4) as g(4) = 5 with quotient of nesting 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 ```

Coefficients of nesting:
G(2,1) − G(2,2): c(1,2) = (2² −1) / (21 −1) = 3
G(2,2) − G(2,4): c(2,4) = (24 −1) / (2² −1) = 5 System G(n,k) has nk instances. All classes g relative prime to r=nk−1 (i.e. (g,r)=1) are self-classes. Into system G(n,p), p ε P,  n instances (from G(n,1)) are nested . All other instances are self and have k transpositions. Therefore so called Little Fermat’s theorem holds for integers n: p\(np−n), i.e.:

#### np − n ≡ 0 (mod p)

Euler (1736) was the first who proved little Fermat theorem.  On the picture is G(2,5), where 5 \ (25−2) i.e. 5 \ 30.

From Little Fermat’s theorem a similar theorem for cyclical numbers follows:
(2³−2)+(5³−5)α³ ≡ 0 (mod 3)  => (2+5α)³ −(2+5α³) ≡ 0 (mod 3)

### Enumeration of classes

Problem of enumeration of classes was solved by K.F.Gauss in algebraic theory of equation classes [Gauss,II]. Polya has shown combinatorial solution – he derived theorem for enumeration of classes with regard to given operations of symmetry [Preparata,1974]. G-systems are based on one operation only – rotation. That makes possible to use simpler and more transparent algebraic relations.

Let v(n,k), w(n,k) a m(n,k) are numbers of self, nested and all classes in G(n,k).

Recurrent relations:

where

and

#### w(n,k) = ∑ v(n,d) (sum for d\k)

Specially for prime order p:

#### w(n,p) = n

Systems G(2,1), G(2,2) a G(2,3) are nested into systems G(2,6) , G(2,1) is nested also into G(2,2) a G(2,3). From total 14 classes 9 classes are self and 5 are nested.

```Self classes                                 Nested classes
─────────────────────────────────────────────────────────────────────────────────
v(2,1)=2/1=2                                 w(2,1)= 0
v(2,2)=(2²−v(2,1))/2=1                       w(2,2)= v(2,1) = 2
v(2,3)=(2³−v(2,1))/3=2                       w(2,3)= v(2,1) = 2
v(2,6)=(26−v(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.

Numbers of self classes v(n,k) written as functions of variable n:

 ``` k v(n,k) ───────────────────────────────────── 1 1/1(n) = n 2 1/2(n²−n) 3 1/3(n³−n) 4 1/4(n4−(n²−n)−n)=¼(n4−n²) 5 1/5(n5−n) 6 1/6(n6−(n³−n)−(n²−n)−n)=1/6(n6−n³−n²+n) 7 1/7(n7−n) 8 1/8(n8−(n4−n²)−(n²−n)−n)=1/8(n8−n4) 9 1/9(n9 −n³) 10 1/10(n10−n5−n²+n) 11 1/11(n11−n) 12 1/12(n12−n6−n4+n²) 13 1/13(n13−n) ``` ``` 1 2 3 4 5 6 7 8 ────────────────────────────────────────── 1 2 3 4 5 6 7 8 0 1 3 6 10 15 21 28 0 2 8 20 40 70 112 168 0 3 18 60 150 315 588 1008 0 6 48 204 624 1554 3360 6552 0 9 116 670 2580 7735 19544 43596 0 18 312 2340 11160 39990 117648 299592 0 30 810 8160 48750 209790 720300 2096640 0 56 ... 0 99 ... 0 186 ... 0 335 ... 0 ... ```

For prime p is:

#### v(p,p) = pp−1−1

i.e. v(p,p)≡−1 mod p. Quotient v(n,p)/n (pεP) corresponds to Fermat’s quotients.

Numbers of nested classes w(n,k) written as functions of variable n:

 ``` k w(n,k) ───────────────────────────────────── 1 0 2 n 3 n 4 1/2(n²−n)+1/1(n)= 1/2(n²+ n) 5 n 6 1/3(n³−n)+1/2(n²−n)+1/1(n)=1/6(2n³+3n²+n) 7 n 8 1/4(n4−n²)+1/2(n²−n)+n = 1/4(n4+n²+2n) ``` ``` 1 2 3 4 5 6 7 8 ───────────────────────────────────── 0 0 0 0 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 6 10 15 21 28 36 1 2 3 4 5 6 7 8 1 5 14 30 55 91 140 204 1 2 3 4 5 6 7 8 1 6 24 70 165 336 616 1044 ```

Let us unfold given recurrent relations for number of all classes. Numbers of all classes m(n,k) written as functions of variable n:

 ``` k m(n,k) ───────────────────────────────────────── 1 1/1(n) + 0 = n 2 1/2(n²− n)+ n = 1/2 (n²+n) 3 1/3(n³−n)+ n = 1/3 (n³+ 2n) 4 1/4(n4−n2)+ 1/2 (n²+n)=1/4 (n4+ n²+2n) 5 1/5(n5−n) + n = 1/5 (n5+ 4n) 6 1/6(n6−n³−n²+n+2n³+3n²+n)=1/6(n6+n³+2n²+2n) 7 1/7(n7−n) + n = 1/7 (n7+ 6n) 8 1/8(n8−n4)+1/4(n4+n²+2n)=1/8(n8+n4+2n²+4n) ``` ``` 1 2 3 4 5 6 7 8 ───────────────────────────────────────── 1 2 3 4 5 6 7 8 1 3 6 10 15 21 28 36 1 4 11 24 45 76 119 176 1 6 24 70 165 336 616 1044 1 8 51 208 629 1560 3367 6560 1 14 130 700 2635 7826 19684 43800 1 20 315 2344 11165 39996 117655 299600 1 36 834 8230 48915 210126 720916 209768 ```

Expressions in brackets on the right (n, n²+n, n³+ 2n, n5+ 4n,..) have no absolute member, therefore it holds:

#### k∙m(n,k) ≡ 0 (mod n)

For prime p it holds:

#### m(p,p) = pp−1+p−1

i.e. m(p,p)≡−1 mod p.

### Differential sequences v G-systemech

Sequences v(n,k) and m(n,k) (n=1,2,3..) makes for any k arithmetical sequences of order k.
Value of constant of the last differential sequences is:

·   For v(n,k): d(k) = (k−1)!

·   For m(n,k): d(k) = k!

The first differential sequence m(n,k) is similar to sequences nk−1.

``` m(n,3)                     n²
────────────────────       ──────────────────
1,4,11,24,45,76,...         .......
3,7,13,21,31,...           1,4,9,16,25,36,...
4,6, 8,10,...              3,5,7,9,11,..
2,2,2,,....                2,2,2,2,...
```

Orders k as well as constant d(k) of these sequences are equal.

For number of self classes in G-system G(p) it holds:

#### v(p,i+p) + (−1)p ∙ v(p,i) ≡ −1 (mod p)

E.g. for p = 5, a(i)=v(5,i): a(0) = 0; a(1) = 6; a(2) = 48; a(3) = 204; a(4) = 624; a(5) = 1554;
i.e. a(5)−a(0)= 1554 ≡ (−1) mod 5  (see periodic sequences).

 Messiaen Olivier [], 1908-1992, French composer of mystical music with expressive melodies. He worked with the modalities which have a limited number of transpositions.

There are 17 classes nested into system G(2,12) and 2∙1+1∙2+2∙3+3∙4+9∙6 = 76 instances in these classes.

```System  Distance schema  Example                    Name
────────────────────────────────────────────────────────────────────────
G(2,1):
0 0(0)                                       Silence
4095 11111…1(1)     c,c#,d,d#,e,…,a#,h          12-sound
G(2,2):
1365 22222(2)       c,d,e,f#,g#,a#              Wholetone scale
G(2,3):
1755 1212121(2)     c,c#,d#,e,f#,g,a,a#         Inverse dim. tetrad
G(2,4):
819 13131(3)       c,c#,e,f,g#,a
1911 11211211(2)    c,c#,d,e,f,f#,g#,a,a#       Inverse augm. triad
G(2,6):
65 6(6)           c,f#                        Tritonus
195 151(5)         c,c#,f#,g                   .
325 242(4)         c,d,f#,g#                   ..
455 11411(4)       c,c#,d,f#,g,g#              Messiaen‘s modes
715 12312(3)       c,c#,d#,f#,g,a              of limited transpositions
845 21321(3)       c,d,d#,f#,g#,a              ...
975 1113111(3)     c,c#,d,d#,f#,g,g#,a         ..
1495 1122112(2)     c,c#,d,e,f#,g,g#,a#         .
2015 111121111(2)   c,c#,d,d#,e,f#,g,g#,a,a#    Inversion of tritone
```
 Janeček Karel, 1903-1974, Czech music theorist and composer (creator of piano, chamber, vocal and orchestral music). One of the biggest Czech music theorists, systematist. He was interested in the theory of composition and in harmony of music, both classical and modern. Systematically listed all possible chords of 12-tone system and rated it by several characteristics. He devoted to musical tectonics, to musical forms, to the theory of melody, to analyze of musical compositions and also to issues of compositional imagination, talent ... He generalized and precisely formulated thoughts of his predecessors and documented principles by excerpts from the musical works.

### Number of chord classes

From relations above we in case n=2 get these values:

``` k   v(2,k)   w(2,k)  m(2,k)
──────────────────────────
1      2       0       2
2      1       2       3
3      2       2       4
4      3       3       6
5      6       2       8
6      9       5      14
7     18       2      20
8     30       6      36
9     56       4      60
10     99       9     108
11    186       2     188
12    335      17     352
```

There is 4096−76=4020 self instances, i.e. groupings having all 12 transpositions in 12-tone musical system. These instances make 4020/12 = 335 classes. Therefore there is together 335+17 = 352 classes in 12-tone musical system.

### Number of classes in large systems

In small systems G(2,k) number of classes corresponds approximately to number of possibilities p(k) to partition number k into sum of positive integers (see Partition of numbers into sums):

#### m(2,k) ~ p(k)

E.g. system G(2,4) (see Binary G-systems/ Distance schemas) is composed of classes corresponding to sums: 4,3+1,2+2,2+1+1,1+1+1+1 and of zero class.
For higher value k, number m(2,k)  grows more quickly than  p(k).
E.g. in G(2,6) sum 2+2+1+1 decay into two classes: 1,2,1,2 and 1,1,2,2. Therefore m(2,k) > p(k).

To estimate number of classes in larger G-systems we will try to apply prime-number theorem.

For bigger r it holds approximately:
π(r) = r/ln(r),   π(r)∙ln(r)  = r,   eln(r)∙π(r) = er
(eln(r))π(r) = er,  rπ(r) = er

i.e.:

#### r ~ ln(rπ(r))

Now let us consider case r=nk. After substitution and computation of k-th radical:
rπ(r) = er,   (nk)π(nk) = e(nk),    n(k∙π(nk)) = e(nk),
nπ(nk)     = e(nk/k)

The expression nk/k gives for higher r approximately number of all classes m in system G(n,k).

So it holds approximately:
nπ(r) = em,     ln(nπ(r)) = m

#### m ~ π(r)∙ ln(n)

where n is base, r module and m number of classes in system G(n,k).

E.g. for n=10, k=3, i.e. r=1000 a π(r)=168. Raw estimate for number of classes in G(10,3) is m=π(r)∙ ln(n)=168 ∙ ln(10) = 387.

## Polya‘s enumeration

Polya’s enumeration determines number of possible partitions of given set into classes of equivalence. It was applied to chemical structures…

It enables computation of numbers of equivalence classes.

### Method of computation

Method of determination of total number of classes according to Polya’s theory:

·   to select operations of symmetry (rotation, inverse, axial symmetry,...)

·   to find number of fixed instances for each operation, i.e. instances that stay (after application of the operation) unchanged (fixed)

·   to assembly (according to given rules) so called cycle index (polynomial of cycles),

·   to set values into cycle index, result gives total number of classes

Polya’s theory in case of rotation gives result [Beckenbach]:

#### m(n,k)=1/k ∑φ(d)∙ nk/d  for d|k, d≤k

where φ is Euler function.

 Pólya, Győrgy [poja], 1887-1985 Hungarian mathematician of liberal education and personal style of interpretation. His mathematical work is extensive and affects a wide range of disciplines. Well known is his enumeration theorem of 1937. He studied the methods of teaching mathematics.

The base of the relation is the following schema of fixed instances:

```   0   *   *   *
1   2   4   8
3   6  12   9
5  10   *   *
7  14  13  11
15   *   *   *
```

Existing instances (given by numbers) are completed by these marked by asterisk (i.e. the sum on the right side).

All S instances make rectangle having width k and height m, therefore m = S/k.

Value m(n,k) (i.e. total number of classes) is called (in Polya’s theory) number of cyclical permutations of k-th class from n elements with repetition.

### Characteristics of permutations

Polynomial composed of cycle type is indicator of permutation cycles.  Length d of each cycle is index and number of cycles p of given length is exponent of expression (xdp).

Indicator of cycles of group I(x) is sum of indicators of particular permutations.

E.g. elements of permutation groups of 3 degree have the following characteristics:

```Permutation    Cycle and order  Lengths  Parity    Type and indicator
──────────────────────────────────────────────────────────────
p0    123     (1)(2)(3)         1 1 1    even (+)    (3,0,0)
123      1                                     x1³
──────────────────────────────────────────────────────────────
p1    123     (1) (2,3)         1 2      odd  (−)    (1,1,0)
132      2                                     x11+x21
──────────────────────────────────────────────────────────────
p2    123     (1,2,3)           3        even (+)    (0,0,1)
231      3                                     x31
───────────────────────────────────────────────────────────────
p3    123     (2) (1,3)         1 2      odd  (−)    (1,1,0)
321      2                                     x11+x21
───────────────────────────────────────────────────────────────
p4    123     (1,3,2)           3        even (+)    (0,0,1)
312      3                                     x31
──────────────────────────────────────────────────────────────
p5    123     (3) (1,2)         1 2      odd  (−)    (1,1,0)
213      2                                     x11+x21
```

### Indicator of cycles

We mark in case of permutation group indicator of cycles T(x).
For P(3) is:
T3(x)= (x1³)+ (x11 +x21)+ (x31)+ (x11 +x21)+ (x31) + (x11 +x21)
i.e.T3(x) = x1³ + 3x1x2 + 2x3

Generally for P(k) we get the following relations:
T1(x) = x1
T2(x) = x1² + x2
T3(x) = x1³ + 3x1∙x2 + 2x3
T4(x) = x14 + 6x1²∙x2 + 3x2² + 8x1∙x3 + 6x4
T5(x) = x15 + 10x1³∙x2 +15x1∙x2² +20x1²∙x3 + 20x2∙x3 + 30x1∙x4 + 24x5

Coefficients of these polynomials come from so called Cauchy’s formula (se below).

### Derivation of indicator of cycles

For partial derivation of given polynomials according to x1,x2,.. some relations hold.
Let us compute partial derivations of indicator of cycles in P(3):
d(x1³ + 3x1∙x2 + 2x3)/ dx3 = 2      [=(3−1)!]
d(x1³ + 3x1∙x2 + 2x3)/ dx2 = 3x1    [=3∙(3−2)!x1]
d(x1³ + 3x1∙x2 + 2x3)/ dx1 = 3x1²+ 3x2       [...]

Generally it holds e.g. [Riordan]:
dT(x)/dxn   = (n−1)!
dT(x)/dxn−1 = n∙(n−2)!x1

### Cyclic index

Sum of indicators of particular permutations is (in our example of rotations) P(x) = x1³ + 2∙x3 (see even permutation in the previous table).

Mentioned permutations keep sequences of elements 1−2−3−1−... and therefore correspond to rotations (G-systems are based on rotations).

According to Polya’s enumeration is number of classes determined by so called cycle index.

Cycle index of group M(x) is cycle indicator of group divided by order of group, i.e.

#### M(x) = P(x)/k

where k is number of operations of symmetry. In our example we have three rotations (k=3). Then number of elements (n) will be substituted to x.

So in G(n,3) twe get:  m(n,3) =  (n³ + 2∙n)/3.

For n=2 resp.3 is therefore:   m(2,3) = (8+4)/3 = 4, resp. m(3,3) = (27+6)/3 = 11.

This result corresponds to values obtained by recurrent algorithm of G-systems (see paragraph Enumeration of classes/Number of all classes).

### Nature of enumeration

Partition of elements in k-apexes is fixed with regard to certain operation, if each apex keep (after application of this operation) the same element as before. In the given relation m(n,3) = (n³ + 2∙n)/3  determine fixed instances the term 2∙n.

There are 4 fixed instances (marked by asterisks) in system G(2,3):

```  0  *  *
1  2  4
3  6  5
7  *  *
```

## Composition of R-systems

### R-systems with given module

For prime module there exist always two trivial systems and several pairs of dual systems.

E.g. for r=13 we have trivial systems R(1,1,13), R(12,2,13) and dual systems with degrees nε{1..r−1} written below (ordered by k)

```    R(3,3,13)         R(9,3,13)

0                 0
1   3   9         1   9   3
2   6   5         2   5   6      φ(3)=2
4  12  10         4  10  12
7   8  11         7  11   8
13               13
```
```    R(5,4,13)          R(8,4,13)

0                  0
1   5  12   8      1   8  12   5
2  10  11   3      2   3  11  10     φ(4)=2
4   7   9   6      4   6   9   7
13                 13
```
```    R(4,6,13)                    R(10,6,13)

0                            0
1   4   3  12  9  10         1  10   9   12   3   4
2   8   6  11  5   7         2   7   5   11   6   8   φ(6)=2
13                          13
```
```    R(2,12,13)
0
1   2   4   8   3   6  12  11   9   5  10   7
13
R(6,12,13)
0
1   6  10   8   9   2  12   7   3   5   4  11
13                                               φ(12)=4

R(7,12,13)
0
1   7  10   5   9  11  12   6   3   8   4   2
13
R(11,12,13)
0
1  11   4   5   3   7  12   2   9   8  10   6
13
```

The highest order for prime rεP is k= r−1.

Orders of particular systems are numbers k, that divide number r−1: k|(r−1). In our case these are divisors of numbers 12, i.e. 1,2,3,4,6 and 12.

Number of systems with given order k is φ(k):
k  1  2  3  4  6  12
φ(k)   1  1  2  2  2   4

### Permutations of R-systems

All systems of the same order are similar. Numbers in rows does not change, they only reorder.

E.g. systems  R(3,3,13) and R(9,3,13) differ only in order of the second and third column.
R(3,3,13):   R(9,3,13):
0     0
1   3   9   1   9   3
...   ...

Reordering of number {1,3,9} and {1,9,3} is composed of two cycles: one elementary (length 1) and one of length 2.

This permutation we will write symbolically [3,9].
Similarly for next orders k:

```R(3,3,13):    1   3   9                     k = 3
R(9,3,13):    1   9   3
cycles: [3,9]
───────────────────────────────────
R(5,4,13):    1   5  12   8                 k = 4
R(8,4,13):    1   8  12   5
cycles: [5,8]
───────────────────────────────────
R( 4,6,13):   1   4   3  12   9  10         k = 6
R(10,6,13):   1  10   9  12   3   4
cycles: [3,9][4,10]
───────────────────────────────────────────────────────────
R( 2,12,13):  1   2   4   8   3   6  12  11   9   5  10   7
R( 6,12,13):  1   6  10   8   9   2  12   7   3   5   4  11        k = 12
R( 7,12,13):  1   7  10   5   9  11  12   6   3   8   4   2
R(11,12,13):  1  11   4   5   3   7  12   2   9   8  10   6
cycles: [3,9][5,8][4,10][2,6,11,7]
```

### Theorem about composition of R-systems

Let d is divisor of order k, d|k. Cycles in system R(n,d,r) are subsets of cycles R(n,k,r).
E.g. [3,9] (d=3) is subset [3,9][4,10] (k=6) because d|k.

Numbers in brackets are bases of systems being permutated. They contains bases of nested systems and also self permutation of bases of given order.
For k=12 there exists nested permutation [3,9][5,8][4,10] a self permutation [2,6,11,7].

 Euler, Leonard [ojler], 1707-1783, Swiss mathematician and physicist, one of the greatest mathematicians of all time. He was interested in theoretical mathematics and its applications (mechanics, astronomy, optics, cartography, music theory ...) He studied number theory, differential, integral calculus and calculus of variations. Discovered a method of solving biquadratic equation. He affected all areas of mathematics, often by a quite original way. Many symbols introduced by him are still in use (i = √-1, Σf(x), ...). After blindness in y.1766 he dictated his work.

Because there is always only one self permutation, there is σ(k) of particular cycles, where σ(k) is number of divisors of numbers k.

For k=12 is σ(12) = 6 and the following permutations correspond to particular divisors:

```    d= 1:         φ( 1) = 1
d= 2:        φ( 2) = 1
d= 3: [3,9]      φ( 3) = 2
d= 4: [5,8]      φ( 4) = 2
d= 6: [4,10]     φ( 6) = 2
d=12: [2,6,11,7] φ(12) = 4
```

Each self permutation of order k has just φ(k) elements. Every element is base of one system.

For k=12 is φ(12) = 4:

```    R( 2,12,13):    2    6   11     7
R( 6,12,13):    6    2    7    11
R( 7,12,13):    7   11    6     2
R(11,12,13):   11    7    2     6
```

Values φ(d) particular divisors d|k compose gradually order k.

For k=12 is: φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = r−1 =12.

Generally it holds (Euler-Gauss) theorem, that we will call theorem about composition of R-systems:

#### ∑(φ(d)) = a; for d|a (d>0)

i.e. each number a is sum φ(d) of all its divisors.

## Nesting of R-systems

### Comparison with G-systems

Similarly as in G-systems also in R-systems set of all instances {0..r} is separated by congruence (G-relation) into classes.

There are also self and nested classes and similar rules of composition.

Let us start with example, when nεP and numbers r ar not multiples of n (i.e. not  n|r) [Gauss II].

Let us have e.g. r=63 and let us compare R-system R(13,6,63) and G-system G(2,6)= R(2,6,63):

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

Modules of both systems (r=63) are the same. Why and in what these systems differ? What classes are nested into R(13,6,63)?

### Principle of nesting Nesting of G-systems is determined by quotient of nesting c(k,d)=(nk−1)/(nd−1) = r/(nd−1)

For G(2,6) is c(d,6)= r/(2d−1), where d=1,2 or 3. For R(13,6,63) but values (13d−1) number r=63 nedělí...

Number r=63 is divisible with value (13d−1) until it is possible and it is decided by greatest common divisor (r,13d−1):
(131−1,r)= (13−1,63)  = (12,63)  =  3
(13²−1,r)= (169−1,63) = (168,63) = 21
(13³−1,r)= (2197−1,63)= (2196,63)=  9

Into system R(13,6,63)  the following 3 systems are nested:

``` r=3: (q=21)                      r=21: (q=3)
0                         0
1                         1  13
2                         2   5
3                         3  18
4  10
r=9: (q=7)                        6  15
0                         7
1  4  7                   8  20
2  8  5                   9  12
3                        11  17
6                        14
9                        16  19
21
```

### Quotient of nesting

We define quotient of nesting c(k,d) for nesting of systems with order d | k into R-system R(n,k,r):

#### c(k,d) = r / (nd−1,r)

In our example R(13,6,63) is:
c(6,1) = 63 / (131−1,r) = 63/3  = 21
c(6,2) = 63 / (13²−1,r) = 63/21 =  3
c(6,3) = 63 / (13³−1,r) = 63/9  =  7

### Nested instance

Započítáme-li do vnořovaných systems G(2,6) all instance, i.e. i instance nested from lower systems we get:
for d=1: 21=2 instances:   0,63
for d=2: 2²=4 instances:   0,21,42,63
for d=3: 2³=8 instances:   0,9,18,27,36,45,54,63

 If ν=63 a p=13, then m=6. Therefore x63−1 will have according to module 13 simple coefficients of the sixth, third, second and first degree. But power of factors of the first degree is a common divisor (of higher degree) of functions x63−1 and x12−1, i.e.x³−1. Therefore there exist 3 coefficients of the first degree. Product of all prime factors of the second and of the first degree will be common divisor of functions x63−1 and x168−1, i.e. equal to x21−1; so there exists (21−3)/2=9 members of second degree. Product of prime factors of the third and of the first degree will be common divisor of functions  x63−1 a x2196−1, i.e. equal to x9 −1; so there exists (9−3)/3=2 members of the third degree. Finally the others are of sixth degree and their number is similarly equal to (63−6−18−3)/6, i.e. 6.

In R(13,6,63) we find similarly:
for d=1: 4 instances:   0,21,42,63
for d=2: 22 instances:  0,3,6,9,12,...54,57,60,63
for d=3: 10 instances:  0,7,14,21,28,35,42,49,56,63

These are for d=1,2 resp. 3  multiples of 21,3 resp. 7.

### Enumeration of number of classes

Method for enumeration of classes in systems R(n,k,r) [GaussII] follows

from the previous paragraph.

K.F.Gauss (in distinction from our convention) does not include number 0 into number of classes.

## Nesting of M-systems

Systems of order k=1
``` M(4,3)
0
1 4 16
2 8 11
3 12 6
5 20 17
7
9 15 18
10 19 13
14
21
```

For k=1 is always r=(n1−1)/(n−1)=1 and all systems M(n,1) are the same, they have 2 instances {0,1}. But their nesting is not the same as in case of G-systems. System M(4,3), i.e. k=3 nests four instances {0,7,14,21} from the system M(4,1): Generally always w1 classes from M(n,1) nest into system M(n,k), where:

#### w1 = (n−1,k)+1

In case n=2 (G-systems) is w1 =(1,k)+1 = 1+1 = 2 (= n).

Nesting of M-systems M(n,d) with order d|k into system M(n,k) is analogous to nesting of G-systems only in case (n−1,k)=1.

In this case M-systems of lower orders d nests into M-systems of higher order k:
M(4,1) →  M(4,2) →  M(4,4) →  M(4,8)
M(3,1) →  M(3,3) →  M(3,9) ...

In case of prime k, M-system has all classes self, except 2 classes nested from system 1.
E.g. M(3,3)
0
1   3   9
2   6   5
4  12  10
7   8  11
13

It has therefore together (nk−1)/(n−1)+1−2 =(nk−1)/(n−1) −1 = (nk−n)/(n−1) self instances and (nk−n)/(n−1)/k self classes.

```    0
13   65
26  130
39
52  104
78
91  143
117
156
```

If condition (n−1,k)=1 is not satisfied, then into given M-system nests generally other number of classes than any M-system can have. In some trivial cases is M-system M(n,d) replaced by G-system G(n,d)

E.g.  M(3,2) + G(3,3)   M(3,6),  G(4,2) + M(4,3) =>  M(4,6).

But generally - nested structure needn’t to have form of neither M-system nor G-system.

E.g. M(5,4) has 13 nested classes, that doesn’t make neither M system M(5,2), having (5²−1)/(5−1)+1 = 24/4+1 = 7 instances nor G-system G(5,2) having 5² = 25 instances.

### Quotient of nesting

In our example of classes nested into system M(5,4), we can see, that classes from system of order k= 1 nest with quotient c(4,1)= 39 and classes from system of order k= 2 with quotient c(4,2)= 13.

From this we guess relation like:

#### c(k,d)= (nk−1)/(nd−1)/(n−1,k/d)

In our case:
c(4,1)= (54−1)/(51−1)/(5−1,4/1) = 624/4/(4,4)  = 624/16 = 39
c(4,2)= (54−1)/(5²−1)/(5−1,4/2) = 624/24/(4,2) = 624/48 = 13

In chapter abou R-systems we have formulated Gauss' general relation for quotient  of nesting:

#### c(k,d) = r / (nd−1,r)

For M-systems is r = (nk−1)/(n−1).

In our case is r = (54−1)/(5−1) = 624/4 = 156.
c(4,1)= r/(51−1,r) = 156/(4,156)  = 156/4  = 39
c(4,2)= r/(5²−1,r) = 156/(24,156) = 156/12 = 13

### Comparison

Now (from the previous paragraph) we have two relations for quotient of nesting. If they both were true, the following relation follows:
(nk−1)/(nd−1)/(n−1,k/d) = (nk−1)/(n−1)/(nd−1,(nk−1)/(n−1))
i.e. (n−1,k/d) = (nd−1,(nk−1)/(n−1)) / ((nd−1)/(n−1)).

Let us mark r(i) = (ni−1)/(i−1) and rewrite this relation to form:

### Enumeration of classes

System M(3,6) has these nested classes from systems M(n,d), d|k:

```    0
14  42 126
28  84 252
56 168 140
70 210 266
91 273
98 294 154
112 336 280
182
196 224 308
238 350 322
364
```

Total m1=(n−1,k)+1 = (2,6)+1 = 3 instances i.e. 3 classes with one transposition come from the system of order d=1:
0
182
364

For system of order d=2 is value t=(n−1)/(n−1,k/d) =2/(2,3) = 2. Nested schema has altogether m2= (nd−1)/t+1 = (3²−1)/2+1 = 5 instances:
0
91  273
182
364

Because t=n−1, nested schema makes M-system M(3,2). But three instances became (as we have seen above) to system of order d=1. Therefore we add only 5−3=2 new instances, that makes 2/d = 1 class.

```    0
14  42 126
28  84 252
56 168 140
70 210 266
98 294 154
112 336 280
182
196 224 308
238 350 322
364
```

In system of order d=3 is parameter t=(n−1)/(n−1,k/d) =2/(2,2) = 1. Nested schema has altogether m3= (nd−1)/t+1 = (3³−1)/1+1 = 27 instances.

Because t=1, make nested schema G-system G(3,3). But again three instances are from system of order d=1. So we add 27−3=24 new instances, that make 24/d = 8 classes. Now we know, that into system M(3,6) come 3+1+8 = 12 classes, that make 3∙1 + 1∙2 + 8∙3 = 3+2+24 = 29 instances. Given M-system has altogether m6 = (nk−1)/(n−1)+1 = (36−1)/2+1 = 365 instances. (We needn’t compute the parameter t, in case of M-system it is always t=n−1.) After subtraction of nested instances we get 365−29 = 336 instances separated into 336/k = 56 classes. System M(3,6) has therefore 56 self and 12 nested classes, i.e. altogether 68 classes.

``` v(n):
k\n    1  2   3    4     5      6      7       8
─────────────────────────────────────────────────
1
2       1   1    2     2      3      3       4
3       2   4    6    10     14     18      24
4       3   8   20    36     63     96     144
5       6  24   68   156    310    560     936
6       9  56  222   640   1547   3246    6228
w(n):
k\n    1  2   3    4     5      6      7      8
─────────────────────────────────────────────────
1
2       2   3    2     3      2      3      2
3       2   2    4     2      2      4      2
4       3   6    4     9      5     10      6
5       2   2    2     2      6      2      2
6       5  12   16    25     19     52     30
m(n):
k\n    1  2   3    4     5      6      7       8
─────────────────────────────────────────────────
1
2       3   4    4     5      5      6       6
3       4   6   10    12     16     22      26
4       6  14   24    45     68    106     150
5       8  26   70   158    316    562     938
6      14  68  238   665   1566   3298    6258
```

## Nesting of F-systems

### Self classes

Self classes in F-systems have 2h transpositions. (Therefore we use from the beginning letter h in exponent instead of k).

For order k of F-system F(n,h)= R(n,k,r) it holds:

#### k=2h

System R(n,k,r) cannot have more than φ(r) transpositions, therefore 2h ≤ φ(nh+1).

### Systems with exponent h=2t

There exists w = 2+(n mod 2) nested classes in these systems.

### Systems with prime exponents

#### w = 2+ (n+1) div 2

Into systems with prime h this number of classes nests:

#### v = (nh−n)/2h

Number of self classes:

E.g. v F(2,11) is n=2, h=11 a r=211+1 = 2049. Into system w = 2+ (n+1) div 2 = 2 + 1 = 3 classes are nested. And there is v = (nh−n)/2h = (2048−2)/22 = 93 self classes.

### Systems with prime module

If r=(nh+1) ε P then:

#### v = nh/2h

Therefore for (n,h)= 1 can never be rεP.

## Nesting of multiplicative tables

### Multiplicative tables

Tables T(k) of numbers m*n mod k, e.g.:

```T1      T2     T3     T4          T5
1       1 2        1 2 3       1 2 3 4
2 1        2 0 2       2 4 1 3
3 2 1       3 1 4 2
4 3 2 1
```
```T6                T7                  T8
1 2 3 4 5        1 2 3 4 5 6         1 2 3 4 5 6 7
2 4 0 2 4        2 4 6 1 3 5         2 4 6 0 2 4 6
3 0 3 0 3        3 6 2 5 1 4         3 6 1 4 7 2 5
4 2 0 4 2        4 1 5 2 6 3         4 0 4 0 4 0 4
5 4 3 2 1        5 3 1 6 4 2         5 2 7 4 1 6 3
6 5 4 3 2 1         6 4 2 0 6 4 2
7 6 5 4 3 2 1
```
```T9                        T10
1  2 3 4  5 6 7  8           1 2 3  4 5 6  7 8 9
2  4 6 8  1 3 5  7           2 4 6  8 0 2  4 6 8
3  6 0 3  6 0 3  6           3 6 9  2 5 8  1 4 7
4  8 3 7  2 6 1  5           4 8 2  6 0 4  8 2 6
5  1 6 2  7 3 8  4           5 0 5  0 5 0  5 0 5
6  3 0 6  3 0 6  3           6 2 8  4 0 6  2 8 4
7  5 3 1  8 6 4  2           7 4 1  8 5 2  9 6 3
8  7 6 5  4 3 2  1           8 6 4  2 0 8  6 4 2
9 8 7  6 5 4  3 2 1
```
```T11                               T12
1  2  3  4  5  6  7  8  9 10     1  2  3  4  5  6  7  8  9 10 11
2  4  6  8 10  1  3  5  7  9     2  4  6  8 10  0  2  4  6  8 10
3  6  9  1  4  7 10  2  5  8     3  6  9  0  3  6  9  0  3  6  9
4  8  1  5  9  2  6 10  3  7     4  8  0  4  8  0  4  8  0  4  8
5 10  4  9  3  8  2  7  1  6     5 10  3  8  1  6 11  4  9  2  7
6  1  7  2  8  3  9  4 10  5     6  0  6  0  6  0  6  0  6  0  6
7  3 10  6  2  9  5  1  8  4     7  2  9  4 11  6  1  8  3 10  5
8  5  2 10  7  4  1  9  6  3     8  4  0  8  4  0  8  4  0  8  4
9  7  5  3  1 10  8  6  4  2     9  6  3  0  9  6  3  0  9  6  3
10  9  8  7  6  5  4  3  2  1    10  8  6  4  2  0 10  8  6  4  2
11 10  9  8  7  6  5  4  3  2  1
```

### Self instances

Here we can select also (similarly as in G-systems) such numbers, which are self, not nested.
(See above - rows and columns, which do not have number 0.) Tables of self instances have φ(k) rows and columns, where φ is Euler function.

```  T1      T2
x        1

T3       T4        T6
1 2       1 3       1 5
2 1       3 1       5 1
```
```  T5          T8          T10        T12
1 2 3 4     1 3 5 7     1 3 7 9     1  5  7 11
2 4 1 3     3 1 7 5     3 9 1 7     5  1 11  7
3 1 4 2     5 7 1 3     7 1 9 3     7 11  1  5
4 3 2 1     7 5 3 1     9 7 3 1    11  7  5  1
```
```  T7               T9
1 2 3 4 5 6       1 2 4 5 7 8
2 4 6 1 3 5       2 4 8 1 5 7
3 6 2 5 1 4       4 8 7 2 1 5
4 1 5 2 6 3       5 1 2 7 8 4
5 3 1 6 4 2       7 5 1 8 4 2
6 5 4 3 2 1       8 7 5 4 2 1
```
```T11
1  2  3  4  5  6  7  8  9 10
2  4  6  8 10  1  3  5  7  9
3  6  9  1  4  7 10  2  5  8
4  8  1  5  9  2  6 10  3  7
5 10  4  9  3  8  2  7  1  6
6  1  7  2  8  3  9  4 10  5
7  3 10  6  2  9  5  1  8  4
8  5  2 10  7  4  1  9  6  3
9  7  5  3  1 10  8  6  4  2
10  9  8  7  6  5  4  3  2  1
```