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.
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].
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. |
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
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:
...
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:
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)
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:
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 revealed enumeration of simple polynomials in form:
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:
In the paragraphs below a simplified Gauss derivation of this relation is outlined.
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.
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:
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))
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 discriminantQuadratic: (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]
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)
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:
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:
i.e. products of simple polynomials are divisors of expression (x(nk) − x), where n is module and k degree of simple 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 expressionsSymbolic 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]
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 expressionsIf 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
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 coefficientsLet 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³
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 coefficientsIn 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
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 *
...?!?...