靀֫;￿㮐ۃҰ㮐ۃ쉸m԰٨X(h㮐ۃҰ ...㮐ۃ쉸m԰٨V&Ó㮐ۃҰ㮐ۃҰ㮐ۃҰ㮐ۃҰ㮐ۃҰ￿㮐ۃҰ 㮐ۃҰ 210㮐ۃҰ 105￿￿㮐ۃҰ 0Ľ㮐ۃҰ㮐ۃҰ 26 ￿㮐ۃҰ

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
Eisenstein Gotthold [], 1823-1852 German mathematician. He studied number theory, theory of elliptic functions, elliptic integrals and the theory of forms.
Eisenstein‘s criterion

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.

Polynomials and congruences

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:

Number of simple polynomials


Linear polynomials

All polynomials of the first degree are simple:

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

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)?!


Cubic polynomials

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.

Notes on discriminant

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:

 P(x) | (xp−1 − 1) 

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

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.

Composition of expressions

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
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).
Partition of number to summands

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.

Illustration of coefficients

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

Assignment of values to coefficients

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* 
Saturated G-systems

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 
Covering of other systems

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    *
    ...?!?...