﻿ Schematic algebra - Gauss' enumeration

# Schematic algebra - Gauss' enumeration

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

Enumeration of classes in G-systems is equivalent to enumeration of equation classes in Gauss general theory of equations.

C.F.Gauss was probably the first who knew and described these mathematical constructions.

Equivalent expression for number of classes can be derived also with help of Pólya’s enumeration.

## Enumeration of simple polynomials

In the following paragraphs we will try to compare theory of G-systems with original Gauss theory of simple polynomials (functions). There appears the same algorithm of enumeration in both theories:

 Number of simple polynomials of degree k according to module n is the same as number of self classes in system G(n,k). Is there any relation between coefficients of simple polynomials and numbers of instances of self classes?!

Original Gauss treatise are get from §330-§347 of chapter II. (General treatise on congruences) of the Gauss Theory on  residues. [Gauss,II].

### Simple polynomials

Polynomials P(x) are called simple (indecomposable, irreducible) if  they does not break-up to polynomials of lower degree. Any polynomial is simple or composed from simple polynomials of lower degrees. Any polynomial can be composed from simple polynomials just one way. All polynomials of the first degree are simple.

Considering all simple polynomials, only polynomials of the first degree can serve for determination of real roots of equations. Polynomials of the second degree are simple or composed of two polynomials of the first degree. Polynomials (on field of complex numbers) of degree higher then the first are (as consequence of fundamental theorem of algebra) all reducible (decomposable).

 Eisenstein Gotthold [], 1823-1852 German mathematician. He studied number theory, theory of elliptic functions, elliptic integrals and the theory of forms.

Polynomial with coefficients [an,an−1,...a1,a0]  from field Z is simple in case when an=1, p|an−1,...,a0, but not p² | a0.
E.g. x²+6x+3 is simple, but x²+6x+9 in not simple (with regard to p=3).

In some cases a correction of polynomial is necessary.

E.g. x²+x+1 is simple, but to determine it by Eisenstein’s criterion, substitution x =(t+1)  is needed.

We get (t+1)²+(t+1)+1 = t² + 3t+ 3,  and only now (with regard to p=3) it is clear.

For congruences P(x)≡0 (mod r) analogous terms will be held as for equations.

Polynomial P(x) (of degree higher then first) is simple, if congruence P(x)≡0 (mod r) has no real roots.

E.g. from polynomials x² +2x +1 and x² +x +2 according to module n=3 only the first is simple.

```    Polynom  F (mod 3)   F(0)  F(1)  F(2)
───────────────────────────────────────────
x²  +x        +2        2     1     2
x² +2x        +1        1     1     0
```

Let us substitute to x gradually values 0,1,..,(n−1) .  The polynomial, that gives for no value (according to module n) result 0, is simple polynomial.

Therefore polynomial x² +x +2 (mod 3) is simple and polynomial x² +2x +1 (mod 3) is not simple.

If P(x)≡ [Q(x)]² − z (mod r) and number z is not quadratic residue (mod r) then P(x) is simple.

E.g. polynomial x²+x+1 (mod 5) is simple, because x²+x+1≡(x−2)²−3 (mod 5) and 3 is quadratic non-residue according to module 5, i.e. 3 is in the second row of the system R(4,2,5):

```    R(4,2,5)
0           x²+x
1  4        x²+x+1  x²+x+4
2  3        x²+x+2  x²+x+3
5           x²+x+5
```

### Total number of polynomials

In the following text we will restrict to polynomials with coefficient ak=1. Let us call governing members all the variable members of the polynomial (i.e. all members except the first) .

There are k coefficients ai  in polynomial Pk(x) = xk + ak−1∙xk−1 + ak−2∙xk−2 + ... . Any polynomial can (according to module n) have n values 0,1,..n−1,

i.e. ai ≡ 0,1,2,3,...,n−1 (mod n),

Number of all distinct polynomials Pk(x) (mod n) is equal to nk.

There exists:

• n distinct polynomials of the first degree (x,x+1,x+2,...,x+n−1)
• n² distinct polynomials of the second degree

...

• nk distinct polynomials k-th degree

### Number of simple polynomials

• We are looking for number of all distinct (not-congruent) simple polynomials of each degree.

Let us use the following denomination for number of polynomials:

• (1)simple of the first degree, (2) simple of the second degree, and so on
• (1²)  composed of two simple polynomials of the first degree
• (1)(2³) composed of one simple polynomial of the first degree and three simple polynomials of the second degree

All polynomials of the first degree are simple:

```    Polynomials             Number    Designation
────────────────────────────────────────────────
All of 1. degree          n         n1
Simple of 1.  degree      n         (1)
```

Polynomial of the second degree are composed from two polynomials of the first degree or are simple. Number of pairs made from p distinct things (including combinations of equal things) is n(n+1)/2. So there is n²−n(n+1)/2=1/2(n²−n) simple polynomials of he second degree.

```    Polynomials                              Number          Designation
─────────────────────────────────────────────────────────────────────
All of 2.degree                          n²                 n²
From two simple polynomials of 1.degree  n(n+1)/2          (1²)
Simple of 2.degree                       1/2 (n²−n)        (2)
```

### Comparison to self classes

For n=3 (i.e. mod 3) k=2 (from total number of 3² = 9 polynomials) there exists 3 simple polynomials: x²+1, x² +x+2, x² +2x +2:

#### (2) = 1/2(n2−n) = 1/2(32−3)= 3

System G(3,2):

```Coef.  F(x) mod 3  F(0) F(1) F(2)
──────────────────────────────────
00     x²           0    1    1
01     x²     +1    1    2    2  *
10     x²  +x       0    2    0
02     x²     +2    2    0    0
20     x² +2x       0    0    2
11     x²  +x +1    1    0    1
21     x² +2x +1    1    1    0
12     x²  +x +2    2    1    2  *
22     x² +2x +2    2    2    1  *
```

There are 3 self classes in system G(3,2) :

```  0             00
1     3       01   10   *
2     6       02   20   *
4             11
5     7       12   21   *
8             22
```

Is there any relation of coefficients (01,12,22) and self classes G(3,2)?!

Similarly as in case of quadratic polynomials:

```Polynomials                                 Number       Designation
─────────────────────────────────────────────────────────────────────
All of 3. degree                            n³               n³
From three simple polynomials of 1.degree   n(n+1)(n+2)/6   (1³)
Containing simple polynomial of 2.degree    n ∙ 1/2(n²−n)   (1)(2)
─────────────────────────────────────────────────────────────────────
Simple of 3. degree                         1/3 (n³−n)      (3)
```

### Gauss‘s formula

Gauss revealed enumeration of simple polynomials in form:

#### nk = ∑d(d), d|k

E.g.:

```  n     = (1)                         = (1)
n2 = (12)+ (2)                      = 2(2) + (1)
n3 = (13)+ (1∙2)+ (3)               = 3(3) + (1)
n4 = (14)+ (12∙2)+ (1∙3)+ (22)+ (4)  = 4(4) + 2(2) + (1)
```
where
``` (1)    =  n              (2) = 1/2(n²−n)          (3) = 1/3(n³−n)
(1²)   =  n(n+1)/2   ...
(1³)   =  n(n+1)(n+2)/6
```

i.e. in our terminology:

#### nk = ∑ d∙v(n,d); for d|k

In the paragraphs below a simplified Gauss derivation of this relation is outlined.

### Total number of polynomials

Expression (1h1 2h2 3h3...) expresses number of polynomials, composed from h1 simple polynomials of 1.degree, h2 simple polynomials of 2.degree, h3 simple polynomials of 3.degree, ... Degree of such polynomials is h1+2h2+3h3+... (see Polynomial expressions).
Summary of all expressions (1h1)(2h2)(3h3)..., for that h1+2h2+3h3+... ...=k, cover all polynomials of the k-th degree and therefore it is equal to nk.

### Nesting of polynomials

Highest member of expression  (n) is equal to nk/k, and if k is prime, then term n/k have to be substracted:

``` Polynomials          Number    Designation
────────────────────────────────────────────
Simple 1. degree      n          (1)
Simple 2. degree     1/2 (n²−n)  (2)
Simple 3. degree     1/3 (n³−n)  (3)
```

From these relations total number of polynomials (for kεP) follows:

#### n=(1)   n²=2(2)+(1)   n³=3(3)+(1)

For n=3:

``` Types of polynomials       Polynomials             Number
──────────────────────────────────────────────────────────────
Linear simple      (k=1)    x,    x+1,    x+2       (1)  = 3
──────────────────────────────────────────────────────────────
Quadratic composed (k=2)   x²,   x²+x,    x²+2x     (1²) = 6
x²+2, x²+x+1,  x²+2x+1
───────────────────────────────────────────────────────────────
Quadratic simple  (k=2)    x²+1, x²+x+2,  x²+2x+2   (2)  = 3
```

It holds:

```    n² =(1²) + (2) = 6 + 3 = 9
n² = 2(2)+(1) = 2∙3+3 = 9     (i.e. 2∙v(3,2) + v(3,1))
```

### Sums going through divisors

If a,b,c,d,.. are divisors of number k, then

nk = a(a)+b(b)+...

Divisors of number k always contain number 1 and k. So if 1,d,d',...,k are all divisors of number k then:

nk = (1)+d(d)+d'(d')+...+k(k)

Product (k) of simple polynomials of degree k, will have degree k(k) and so it is with other products.

So product of all simple polynomials of degrees 1,d,d',..,k has degree nk.

Quadratic:      (b∙b−4∙c) mod p = 2

```    3:[ 0, 1],[ 1, 2],[ 2, 2]
5:[ 0, 2],[ 1, 1],[ 2, 3],[ 3, 3],[ 4, 1]
6:[ 0, 1],[ 0, 4],[ 2, 2],[ 2, 5],[ 4, 2],[ 4, 5]
7:[ 0, 3],[ 1, 5],[ 2, 4],[ 3, 0],[ 4, 0],[ 5, 4],[ 6, 5]
```

Cubic:     (4∙b∙b∙b+27∙c∙c) mod p = 2

```    3:[ 2, 0],[ 2, 1],[ 2, 2],
5:[ 0, 1],[ 0, 4],[ 1, 2],[ 1, 3],[ 2, 0],
6:[ 2, 0],[ 2, 2],[ 2, 4],[ 5, 0],[ 5, 2],[ 5, 4],
7:[ 1, 3],[ 1, 4],[ 2, 3],[ 2, 4],[ 3, 1],[ 3, 6],[ 4, 3],[ 4, 4],[ 5, 1],[ 5, 6],[ 6, 1],[ 6, 6]
```

## Products of polynomials

### Stirling‘s equations

Let us consider equations of s-th degree, having numbers 1,2,3,...s as their roots.
Such equations come from products of polynomials: (x−1)(x−2)(x−3).....(x−s)

Let us start to multiply expressions from the left:

```  s  Factors                Equation
──────────────────────────────────────────────────────────
1  (x−1)                  x−1  = 0
2  (x−1)(x−2)             x²−3x+2    = 0
3  (x−1)(x−2)(x−3)        x³−6x²+11x−6    = 0
4  (x−1)(x−2)(x−3)(x−4)   x4−10x³+35x²−50x+24 = 0
```

Coefficients of equations are Stirling’s numbers (see Reccurent sequences)

### Products of simple polynomials of 1.degree

If number p=s+1 is prime, then mentioned products contains all simple polynomials according to module p:

``` k  Factors                Congruence
───────────────────────────────────────────────────────────────────────
2  (x−1)                  x−1  ≡ x −1 (mod 2)
3  (x−1)(x−2)             x²−3x+2     ≡ x²−1 (mod 3)
5  (x−1)(x−2)(x−3)(x−4)   x4−10x³+35x²−50x+24 ≡ x4−1 (mod 5)
```

Simple polynomials are according to little Fermat theorem (with regard to module n) divisors of expression xp−x = x ∙ (xp−1 − 1),

i.e. it holds:

### Products of simple polynomials

Let us compute product all simple polynomials of degree 1 and 2 (i.e. linear and quadratic) according to modules n=2 and 3.

Module n=2:

``` G(2,1):   x(x−1)         ≡ x²−x
G(2,2):  (x²+x+1)        ≡ x²+x+1
(x²−x)∙(x²+x+1) ≡ x4− x
```

Module n=3:

```  G(3,1):   x(x−1)(x−2)                  ≡ x³−x
G(3,2):  (x²+1)(x²+x+2)(x²+2x+2)       ≡ x6+x4+x²+1
(x³−x)∙(x6+x4+x²+1) ≡ x9 − x
```

It holds:

#### ∏P(x) | (x(nk)−x)

i.e. products of simple polynomials are divisors of expression (x(nk) − x),  where n is module and k degree of simple polynomials.

## Saturated systems

### Powers of polynomials

Let us observe powers of expression (a+b+c ...)k .  For k≤n (where n is number of elements a,b,c,..) always k elements  'interact' in bindings.
E.g. for k=2 and n=2,3:

``` k-th power n-member                       Symbolic denotation
──────────────────────────────────────────────────────────────
(a+b)²   = a² + 2ab + b²                    2[x²]+ 1[2xy]
(a+b+c)² = a² + 2ab + b² + 2bc + c² + 2ca   2[x²]+ 3[2xy]
```

Coefficients for given k and distinct n are the same. E.g. the term 2ab from G(2,2) has analogous members 2ab+2bc+2ca in G(3,2).

Expressions can be written symbolically (e.g. with help of x,y,z,v..) and  then particular symbols can be substituted  by permutations of a,b,c,d...

Symbolic expressions for n=2..4:

```    k=2:
(a+b)2       2∙[x²]+ 1∙[2xy]
(a+b+c)2     2∙[x²]+ 3∙[2xy]
(a+b+c+d)2   2∙[x²]+ 6∙[2xy]
─────────────────────────────────
k=3:
(a+b)3       3∙[x³]+  2∙[3x²y]
(a+b+c)3     3∙[x³]+  6∙[3x²y]+ 1∙[6xyz]
(a+b+c+d)3   3∙[x³]+ 12∙[3x²y]+ 4∙[6xyz]
─────────────────────────────────────────────
k=4:
(a+b)4       4∙[x4]+  2∙[4x³y]+ 1∙[6x²y²]
(a+b+c)4     4∙[x4]+  6∙[4x³y]+ 3∙[6x²y²]+  3∙[12x²yz]
(a+b+c+d)4   4∙[x4]+ 12∙[4x³y]+ 6∙[6x²y²]+ 12∙[12x²yz]+ 1∙[24xyzv]
```

### Polynomic expressions

Every particular expression from breakdown (a+b+c ...)k  have sum of exponents equal to k.
E.g. for k=3  particular members a³, 3ab², 6abc,... of  (a+b+c)³  have sum of exponents 3=1+2=1+1+1,....

Coefficients of particular members (for k<n) are determined by number of permutations with repetition of symbols, i.e. by relation:

```   n!
──────────
h1! ..    hn!
```

where h1,...hn are exponents of members.

Number of coefficients for given k is equal to number of distinct partition with sum k.

E.g. for k=4 there exists 5 partitions: 4= 3+1= 2+2= 2+1+1= 1+1+1+1.

```  k   Coefficients         Partitions
──────────────────────────────────────────────────
1:  1                    1
2:  1 2                  2,1+1
3:  1 3  6               3,2+1,1+1+1
4:  1 4  6 12 24         4,3+1,2+2,2+1+1,1+1+1+1.
5:  1 5 10 20 30 60 120  5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1
```

Coefficient of x³y in (a+b+c+...)4 is 4, because 4!/3!1! = 4.

If exponents of p,q,r in members of expressions are h1,h2,h3 then it holds:

for xk+yk: h1+2h2 = k, for xk+yk+zk: h1+2h2+3h3 = k,

E.g. for k=3 is:

```   Member    a   b   c   a+2b+3c
─────────────────────────────
p³        3   0   0     3
3pq       1   1   0     3
3r        0   0   1     3
```

Expression composed of symmetrical functions p,q,r,s,.. has so much members, how many there is partitions of number k to sum: h1+2h2+3h3+.

E.g. for k=5 there exists 5 partitions [a,b,c]:

[5,0,0], [3,1,0], [2,0,1], [1,2,0], [0,1,1]

So notation x5+y5+z5 with help of symmetric polynomials p,q,r have to contain members p5, p³q, p²r, pq² and qr.

 Ramanujan, Srinivasa Aaiyangar [], 1887-1920 brilliant Indian mathematician, self taught. He was interested in number theory, especially numerical arrangement. During his short stay in England he published a series of works, some in collaboration with the English mathematician G.H.Hardy (on whose invitation he arrived).

Task to partition number into summands ("partition numerorum")  was solved by Euler.

If p(k) is number of such partitions, then it holds (see Generating functions):

1+p(1)x+p(2)x²+... = 1/((1−x)(1−x²)(1−x³)...).

For value p(k) S.Ramanujan and G.H.Hardy (y.1917) derived asymptotic relation:

p(k) ~ (eφ√(2k/3))/4k√3

### Saturated G-systems

``` G(1,1):               G(3,3):
0     a               000             a3
1     b               100 001 010     3a2b
110 101 011     3ab2
G(2,2):                111             b3
00      a2            200 002 020     3a2c
01 10   2ab           201 012 120     3bac
11      b2            210 102 021     3abc
211 112 121     3b2c
220 202 022     3ac2
221 212 122     3bc2
222             c3

```

In case n=k coefficients saturates to value n!:

```k\n   2      3      4
────────────────────────
2   2xy
3   3x²y   6xyz
4   4x³y  12x²yz  24xyzv
```

Systems with n=k are called saturated.

Let us order coefficients of polynomial powers into form of n-side pyramid with k layers.

In each j-th layer just j symbols 'interacts'.  Pyramid layers are viewed from above:

```              c³
c²
3ac²        3bc²
2ac  c  2bc
a       b
3a²c      2ab      3b²c
a²        b²
a³      3a²b   3ab²     b³
```
```Layer 1(2):
c
(2ac) (2bc)
a (2ab) b
```
```Layer 2(3):
c²
2ac (6abc) 2bc
a² 2ab b²
```
```Layer 3(4)
c³
3ac² 3bc²
(12abc²)
6abc
3a²c (12a²bc)(12ab²c) 3b²c
a³ 3a²b 3ab² b³
```

### Simple polynomials

E.g. for n=2, k=2  (from total number 2² = 4 polynomials) only polynomial x²+x+1 is simple.

System G(2,2):

```Coefficients  Polynomial F(x)(mod 2)   F(0)  F(1)
──────────────────────────────────────────────────
00           x²                       0     1
01           x²     +1                1     0
10           x²  +x                   0     0
11           x²  +x +1                1     1   *    1/2(n²−n) = 1/2(2²−2) = 1
```

Here x²≡x∙x, x²+x≡x(x+1) and x²+1≡(x+1)(x+1) (mod 2).

In case of cubic polynomials (k=3) according to module 3 (n=3) assign coefficients (left) values (right):

System G(3,3):

```   Polynomial               Coefficients      Values
───────────────────────────────────────────────────────────
x³                       000               012
x³ +1 x³ +x  x³+ x²      001  010  100     120  021  020
x³ +...                  002  020  200     201  000  001
x³ +...                  011  110  101     102  002  101
x³ +...                  012  120  201*    210  011  112*
x³ +...                  021* 210  102*    111* 010  212*
x³ +...                  022* 220  202     222* 022  220
x³ +...                  111               110
x³ +...                  112* 121* 211*    221* 122* 121*
x³+ x²+2x+2 ...          122  221  212     200  100  202
───────────────────────────────────────────────────────────
x³+2x²+2x+2              222*              211*
```

Systems with n=k are called saturated.  If we take coefficients of polynomials from G(n,n), then  functional values for x=0,1,..(n−1) are also from G(n,n).

We find values of simple polynomials in bottom part of G-system of values:

Values of polynomials from G(3,3):

```    000
001  010  100
....
022  220  202
```
Simple polynomials makes G(2,3)
```    111*                 000
112* 121* 211*   =>  001 010 100
122* 221* 212*       011 110 101
222*                 111
```

Polynomial coming from coefficients of G(3,2) can be (according to functional values F(0), F(1), F(2)) separated into three classes:

```    Polynomial                    Values
────────────────────────────────────────────────
x²     x²+x+1   x²+2x+1       011 101 110
x²+1   x²+x+2   x²+2x+2       122 212 221  *
x²+2   x²+x     x²+2x         200 020 002
```

The values make new instances with n-cells from n-elements. Rows with simple polynomials are marked by asterisk.

All given instances become to system G(n,n) and cover some its classes.
E.g. simple polynomials z G(3,2) make 1 class, i.e.. 3 instances {122,212,221} from G(3,3).

In G(5,2) we find 10 simple polynomials; their values cover 2 classes from G(5,5):

```    Polynomial
──────────────────────────────────────────
x²+2  x²+x+1  x²+2x+3  x²+3x+3  x²+4x+1   *
x²+3  x²+x+2  x²+2x+4  x²+3x+4  x²+4x+2   *
Values
──────────────────────────────────────
23113  13231  31132  32311  11323    *
34224  24342  42243  43422  22434    *
```

If we subtract number 1 from the all these particular values we can shift to classes of the system G(n−1,n).
So values from simple polynomials of G(5,2) can be put to G(4,5):

```    12002  02120  20021  21200  00212    *
23112  13231  31132  32311  11323    *
...?!?...
```