Enumerace počtu druhů v G-systémech je shodná s enumerací počtu tříd rovnic v Gaussově obecné teorie rovnic. K.F.Gauss byl pravděpodobně první, kdo znal a popsal tyto matematické konstrukce. Stejný výraz pro počet druhů je možné určit také pomocí Pólyovy enumerace.
V následujících odstavcích se pokusíme porovnat teorii G-systémů s originální Gaussovu teorií prostých polynomů (funkcí). V obou teoriích se objevuje tentýž algoritmus enumerace:
| Prostých polynomů stupně k podle modulu n je právě tolik, kolik je vlastních druhů v systému G(n,k). Existuje nějaký vztah mezi koeficienty prostých polynomů a instancemi vlastních druhů?! |
Originální Gaussova pojednání jsou čerpána z §330-§347 kapitoly II. (Obecná pojednání o kongruencích) Gaussovy Nauky o zbytcích. [Gauss,II].
Polynomy nazveme prosté (nerozložitelné, ireducibilní) jestliže se nerozpadají na žádné polynomy nižšího stupně. Libovolný polynom je buď prostý, nebo sestavený z prostých polynomů nižších stupňů. Každý polynom může být sestaven z prostých polynomů jedině jedním způsobem.
Všechny polynomy prvního stupně jsou prosté. Ze všech prostých polynomů mohou sloužit k nalezení reálných kořenů jen polynomy prvního stupně.
Polynomy druhého stupně jsou buď prosté nebo sestavené ze dvou polynomů prvního stupně. Polynomy (v oboru komplexních) stupně vyššího než prvého (v důsledku základní věty algebry) jsou všechny rozložitelné (reducibilní).
Eisenstein Gotthold| Eisenstein Gotthold, [], 1823-1852, německý matematik. Zabýval se teorií čísel, teorií eliptických funkcí, eliptickými integrály a teorií forem. |
Polynom s koeficienty
[an,an−1,...a1,a0] z oboru Z
je prostý v případě, kdy an=1,
p|an−1,...,a0, ale nikoliv p² |
a0.
Např. x²+6x+3 je prostý, zatímco x²+6x+9
nikoliv.
Někdy je k použití kriteria nutné polynom nejprve upravit.
Např. x²+x+1 je prostý proto, že po substituci x =(t+1) přejde
na: (t+1)²+(t+1)+1 = t² + 3t+ 3, tj. na polynom, u
kterého je možné podle Eisensteinova kriteria nerozložitelnost určit.
Stejné pojmenování použijeme i v případě, kdy polynomy nepoužíváme k výstavbě rovnic, ale kongruencí P(x)≡0 (mod r).
Např. polynomy x² +2x +1 a x² +x +2 podle modulu n=3.
Polynom F (mod 3) F(0) F(1) F(2)
───────────────────────────────────────────
x² +x +2 2 1 2
x² +2x +1 1 1 0
Polynom P(x) (stupně vyššího než prvního) je prostý, když kongruence P(x)≡0 (mod r) nemá reálné kořeny. Dosazujeme-li za x postupně hodnoty 0,1,..,(n−1) je prostý polynom ten, který pro žádnou z hodnot nedá (podle modulu n) výsledek 0.
Polynom x² +x +2 (mod 3) je prostý, x² +2x +1 (mod 3) nikoliv.
Když P(x)≡ [Q(x)]² − z (mod r) tak P(x) je prostý, když číslo z není kvadratickým zbytkem (mod r).
Např. polynom x²+x+1 (mod 5) je prostý, protože x²+x+1≡(x−2)²−3 (mod 5) a 3 je kvadratický nezbytek podle modulu 5 (je v druhém řádku 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
V dalším textu omezíme zkoumání na na polynomy, jejichž nejvyšší člen má koeficient ak=1. Všechny proměnlivé členy polynomu (tj. členy kromě prvního) nazveme určující členy. V polynomu Pk(x) = xk + ak−1∙xk−1 + ak−2∙xk−2 + ... je k koeficientů ai, z nichž každý může nabývat (podle modulu n) n hodnot 0,1,..n−1, tj. ai ≡ 0,1,2,3,...,n−1 (mod n),
Počet všech různých polynomů Pk(x) (mod n) je roven nk.
Přitom existuje:
n různých polynomů prvního stupně (x,x+1,x+2,...,x+n−1) n² různých polynomů druhého stupně...
nk různých polynomů k-tého stupněZajímá nás počet všech různých (nekongruentních) prostých polynomů každého stupně. Přitom zavedeme následující označení počtu polynomů:
(1) prosté prvního stupně, (2) prosté druhého stupně atd.,
(1²) sestavené ze dvou prostých polynomů prvního stupně
(1)(2³) sestavené z jednoho prostého polynomu prvního stupně a tří prostých polynomů druhého stupně
Všechny polynomy prvního stupně jsou prosté:
Polynomy Počet Označení
──────────────────────────────────────────
1. stupně celkem n n1
Prosté 1. stupně n (1)
Všechny polynom druhého stupně jsou buď sestaveny ze dvou polynomů prvního stupně, nebo jsou prosté. Počet dvojic sestavených z p různých předmětů (včetně kombinací stejných předmětů) je n(n+1)/2. Prostých polynomů je proto n²−n(n+1)/2=1/2(n²−n).
Polynomy Počet Označení
───────────────────────────────────────────────────────────────
2. stupně celkem n² n²
Ze dvou prostých polynomů 1.stupně n(n+1)/2 (1²)
Prosté 2. stupně 1/2 (n²−n) (2)
Pro n=3 (tj. mod 3) ,k=2 (z celkového počtu 3² = 9-ti polynomů) existují 3 prosté polynomy: x²+1, x² +x+2, x² +2x +2:
Systém 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 *
V systému G(3,2) jsou právě 3 vlastní druhy:
0 00 1 3 01 10 * 2 6 02 20 * 4 11 5 7 12 21 * 8 22
Existuje nějaký vztah mezi koeficienty (01,12,22) a vlastními druhy G(3,2)?!
Polynomy Počet Označení ───────────────────────────────────────────────────────────────────── 3. stupně celkem n³ n³ Ze třech prostých polynomů 1.stupně n(n+1)(n+2)/6 (1³) Obsahující prostý polynom 2.stupně n ∙ 1/2(n²−n) (1)(2) ───────────────────────────────────────────────────────────────────── Prosté 3. stupně 1/3 (n³−n) (3)
Gauss předložil vztahy pro vyčíslení počtu prostých polynomů ve tvaru:
Např.:
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
tj. v naší terminologii (viz G-systémy):
V následujících odstavcích je nastíněno Gaussovo odvození tohoto vztahu.
Výraz (1h1 2h2 3h3...) vyjadřuje
počet polynomů, složených z h1 prostých polynomů 1. stupně, h2 prostých
polynomů 2. stupně, h3 prostých polynomů 3. stupně, ... Stupeň každého z
těchto polynomů je h1+2h2+3h3+... (viz
Polynomické výrazy).
Souhrn všech výrazů (1h1)(2h2)(3h3)...,
pro které h1+2h2+3h3+... ...=k,
vyčerpává všechny polynomy k-tého stupně a proto je roven
nk.
Nejvyšší člen výrazu (n) je roven nk/k, a jestliže k je prvočíslo, tak se od tohoto členu odečítá n/k:
Polynomy Počet Označení ──────────────────────────────────────────── Prosté 1. stupně n (1) Prosté 2. stupně 1/2 (n²−n) (2) Prosté 3. stupně 1/3 (n³−n) (3)
Z těchto vztahů plyne celkový počet polynomů (pro kεP):
Pro n=3:
Typ polynomů Polynomy Počet
──────────────────────────────────────────────────────────────
Linear prosté (k=1) x, x+1, x+2 (1) = 3
──────────────────────────────────────────────────────────────
Kvadratické složené (k=2) x², x²+x, x²+2x (1²) = 6
x²+2, x²+x+1, x²+2x+1
───────────────────────────────────────────────────────────────
Kvadratické prosté (k=2) x²+1, x²+x+2, x²+2x+2 (2) = 3
Platí:
n² =(1²) + (2) = 6 + 3 = 9
n² = 2(2)+(1) = 2∙3+3 = 9 (tj. 2∙v(3,2) + v(3,1))
Jestliže a,b,c,d,.. jsou děliteli čísla k, tak
nk = a(a)+b(b)+...
Mezi dělitele čísla k vždy patří 1 a k. Jestliže tedy 1,d,d',...,k jsou všechny možné dělitele čísla k tak:
nk = (1)+d(d)+d'(d')+...+k(k)
Součin (k) prostých polynomů, které mají stupeň k, bude mít stupeň k(k) a tak tomu bude i u ostatních součinů. Proto součin všech prostých polynomů stupňů 1,d,d',..,k má stupeň nk.
Poznámky k diskriminantuKvadratické: (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]
Kubické: (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]
Uvažujme rovnice s-tého stupně, jejichž kořeny jsou čísla
1,2,3,...s.
Takové rovnice vznikají součinem polynomů:
(x−1)(x−2)(x−3).....(x−s)
Začněme násobit postupně zleva:
s Součinitelé Rovnice ────────────────────────────────────────────────────────── 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
Koeficienty rovnic jsou Stirlingova čísla (viz Rekurentní posloupnosti)
Když číslo p=s+1 je prvočíslo, tak uvedené součiny obsahují všechny prosté polynomy podle modulu p:
k Součinitelé Kongruence ──────────────────────────────────────────────────────────────────────── 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)
Podle malé Fermatovy věty jsou prosté polynomy (podle modulu n) děliteli výrazu xp−x = x ∙ (xp−1 − 1), tj. platí:
Vypočítáme součin všech prostých polynomů stupně 1 a 2 (tj. lineárních a kvadratických) podle modulu n=2 a 3.
Modul 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
Modul 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
Platí:
tj. součiny prostých polynomů jsou děliteli výrazu (x(nk) − x), kde n je modul a k stupeň prostých polynomů.
Zajímá nás, co se odehrává při umocňování výrazu (a+b+c ...)k s prvky v závorce.
Pro k≤n (kde n je počet prvků a,b,c,..) ve vazbách 'reaguje' vždy
právě k prvků.
Např. při k=2 a n=2,3:
k-tá mocnina n-členu Symbolický zápis ───────────────────────────────────────────────────────────────── (a+b)² = a² + 2ab + b² 2[x²]+ 1[2xy] (a+b+c)² = a² + 2ab + b² + 2bc + c² + 2ca 2[x²]+ 3[2xy]
Přitom koeficienty jsou pro dané k a různá n stejné. Např. členu 2ab z G(2,2) odpovídají analogické členy 2ab+2bc+2ca v G(3,2). Výrazy tak můžeme zapisovat symbolicky (např. pomocí x,y,z,..) přičemž za jednotlivé symboly je možné dosadit permutace a,b,c,d...
Symbolické zápisySymbolické zápisy pro 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]
Každý jednotlivý výraz z rozpisu (a+b+c ...)k má součet
exponentů k.
Např. pro k=3 v (a+b+c)³ mají jednotlivé členy a³,
3ab², 6abc,... součet exponentů 3=1+2=1+1+1,...).
Koeficienty u jednotlivých členů (pro k<n) jsou určeny počtem permutací s opakováním symbolů, tj. vztahem:
n! ────────── h1! .. hn!
kde h1,...hn jsou exponenty členů.
Koeficientů je pro dané k vždy tolik, kolik existuje různých rozkladů se součtem k. Např. pro k=4 existuje 5 rozkladů: 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
Koeficient v (a+b+c+...)4 u x³y je 4, protože 4!/3!1! = 4.
Složení výrazůJsou-li exponenty u p,q,r ve členech výrazů postupně h1,h2,h3 tak platí:
pro xk+yk: h1+2h2 = k, pro xk+yk+zk: h1+2h2+3h3 = k,Např. pro k=3 je:
Člen a b c a+2b+3c ───────────────────────────── p³ 3 0 0 3 3pq 1 1 0 3 3r 0 0 1 3
Obecně má výraz sestavený ze symetrických funkcí p,q,r,s,.. právě
tolik členů, kolik je možných rozkladů čísla k na součet:
h1+2h2+3h3+.
Např. pro k=5 existuje 5 rozkladů [a,b,c]: [5,0,0], [3,1,0], [2,0,1], [1,2,0], [0,1,1]
Zápis x5+y5+z5 pomocí symetrických polynomů p,q,r musí proto obsahovat členy p5, p³q, p²r, pq² a qr.
| Ramanujan, Srinivasa Aaiyangar [], 1887-1920, geniální indický matematik, samouk. Věnoval se teorii čísel, zvláště číselným uspořádáním. Během svého krátkého pobytu v Anglii publikoval řadu prací, některé ve spolupráci s anglickým matematikem G.H.Hardym (na jehož pozvání přicestoval). |
Úlohu o rozdělení čísla do sčítanců (o rozměnění bankovky,"partiton numerorum",...) řešil již Euler.
Jestliže p(k) je počet možných rozdělení, tak platí
(viz Vytvořující funkce): 1+p(1)x+p(2)x²+... = 1/((1−x)(1−x²)(1−x³)...).
Pro hodnotu p(k) odvodili S.Ramanujan a G.H.Hardy (r.1917) asymptotický vztah: 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
Při n=k dochází k nasycování koeficientů na hodnotu n!:
k\n 2 3 4 ──────────────────────── 2 2xy 3 3x²y 6xyz 4 4x³y 12x²yz 24xyzv
Systémy s n=k nazveme nasycené.
Znázornění koeficientůKoeficienty mocnin polynomů uspořádáme do tvaru n-bokého jehlanu s k vrstvami. V každé j-té vrstvě 'reaguje' právě j symbolů.
Pohled shora:
c³
c²
3ac² 3bc²
2ac c 2bc
a b
3a²c 2ab 3b²c
a² b²
a³ 3a²b 3ab² b³
Vrstva 1(2):
c
(2ac) (2bc)
a (2ab) b
Vrstva 2(3):
c²
2ac (6abc) 2bc
a² 2ab b²
Vrstva 3(4)
c³
3ac² 3bc²
(12abc²)
6abc
3a²c (12a²bc)(12ab²c) 3b²c
a³ 3a²b 3ab² b³
Např. pro n=2, k=2 je (z celkového počtu 2² = 4 polynomů) prostý jen polynom x²+x+1.
Systém G(2,2):
Koeficienty Polynom 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
Přitom x²≡x∙x, x²+x≡x(x+1) a x²+1≡(x+1)(x+1) (mod 2).
Přiřazení hodnot koeficientůmV případě kubických polynomů (k=3) podle modulu 3 (n=3) přiřadíme koeficientům (vlevo) hodnoty (vpravo):
System G(3,3):
Polynom Koeficienty Hodnoty ─────────────────────────────────────────────────────────── 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*
Systémy ve kterých n=k nazýváme nasycené (viz G-systémy). Vezmeme-li koeficienty polynomů z G(n,n), jsou funkční hodnoty pro x=0,1,..(n−1) také z G(n,n). Hodnoty prostých polynomů najdeme v dolní části G-systému hodnot: Hodnoty polynomů z 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
Podle funkčních hodnot F(0), F(1), F(2) můžeme polynom vycházející z koeficientů G(3,2) rozdělit do tří druhů:
Polynom Hodnoty
────────────────────────────────────────────────
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
Hodnoty vytvářejí nové instance tvořené n-buňkami z n-prvků. Prosté polynomy jsou v řádku označeném hvězdičkou.
Všechny instance patří systému G(n,n) a pokrývají některé jeho
druhy.
Např. prosté polynomy z G(3,2) tvoří 1 druh, tj. 3 instance {122,212,221}
z G(3,3). V G(5,2) najdeme 10 prostých polynomů; jejich hodnoty pokrývají
2 druhy z G(5,5):
Polynom
──────────────────────────────────────────
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 *
Hodnoty
──────────────────────────────────────
23113 13231 31132 32311 11323 *
34224 24342 42243 43422 22434 *
Od jednotlivých hodnot prostých polynomů bychom mohli také odečíst
jedničku a hledat odpovídající druhy v G(n−1,n).
Hodnoty prostých polynomů z G(5,2) tak můžeme zařadit do G(4,5):
12002 02120 20021 21200 00212 *
23112 13231 31132 32311 11323 *
...?!?...