L'ordre maximal d'un élément de G

Difficulté: 10/20

7 Mars

Préface Auteur: morphocode
Année: 2014

Le but de cet article c'est démontrer mathématiquement l'ordre maximal dmax d'un élément de G (ou l'ordre maximal d'une formule) est 1260
Beaucoup de gens en parlent , mais souvent c'est vague, pas de démontration et on ne sait toujours pas pourquoi ça vaut 1260.
Il existe des algorithmes qui calculent tous les ordres de G, et on trouve évidemment le plus grand c'est 1260
Mais ce qu'on veut c'est une démontration mathématique ...

Définitions et notations

Rappel
G+ = S12 x Z212 x S8 x Z38 le groupe étendu de G
Le groupe du Rubik's Cube G est l'ensemble des éléments (u,x,v,y) de G+ vérifiant:
1. ∑ xi = 0 (mod 2) où x = (x1,x2,...,x12)
2. ∑ yi = 0 (mod 3) où y = (y1,y2,...,y8)
3. sig(u)=sig(v)

L'ordre
L'ordre d'une permutation v , c'est le plus petit entier positive d tel que vd = 1 (ici 1 représente l'identité=id) et on le note |v| = d
NOTE Si v est composé de cycles disjoints son ordre vaut le ppcm des cycles
v = (a-cycle)(b-cycle)(c-cycle)
alors
|v| = d = ppcm(a,b,c)

Théorème central:
On pose:
m=ppcm(a,b) et
A = {m'=ppcm(a',b') avec a'|a et b'|b}
B = {k / k|m }
Aors A=B

Div(m) = {ppcm(Div(a), Div(b))} , Div(a)=l'ensemble des diviseurs de a

Démontration
On va raisonner sur un exemple.
a=p3 q2
b=p2 r3
Div(a)={ (1+p+p²+p3)(1+q+q²) } = {a'=pi qj ; 0≤i≤3, 0≤j≤2 }
Div(b)={ (1+p+p²)(1+r+r²+r3) } = {b'=pk rt ; 0≤k≤2, 0≤t≤3 }
m=ppcm(a,b)= p3 q2 r3 ; tout et plus grande puissance
Div(m) = {(1+p+p²+p3)(1+q+q²)(1+r+r²+r3) }= {x=pf qg rh ; 0≤f≤3, 0≤g≤2 , 0≤h≤3 }

a' = pi qj , a'∈Div(a)
b' = pk rt , b'∈Div(b)
m'=ppcm(a',b') = pi qj rt en supposant que i absorbe k, k < i
et x=pf qg rh un divideur de m, on voit que m'=pi qj rt et x ont de la même forme, et les puissances (f,g,h),(i,j,t) varient de la même façon donc ces deux ensembles sont égaux A=B
m'∈A ⇒ m'=ppcm(a',b')=pi qj rt , même forme que x donc ⇒ m'∈B ⇒ A ⊂ B
x∈B ⇒ x = pf qg rh, même forme que m' donc x provient d'un ppcm ⇒ x=ppcm(a',b') ⇒ x∈A ⇒ B ⊂ A
finalement A=B


Un sommet est repésenté par, (v,y)∈S8 x Z38 et la loi de compsition donne
(v,y)(w,z) = (vw, y + v(z) )
donc pour
(v,y)² = (v², y + v(y) )
(v,y)3 = (v3, y + v(y) + v²(y) )
....
(v,y)b = (vb, y + v(y) + v²(y) + ...+vb-1(y) )

par définition on note
y + v(y) + v²(y) + ...+vb-1(y) = yb
d'ou
(v,y)b = (vb, yb)

On appelle l'ordre du vecteur y (en v) c'est le plus petit entier positif b tel que
y + v(y) + v²(y) + ...+vb-1(y) = 0
et on le note |y| = b

Big théorème.

On a le théorème suivant

Théorème
L'ordre du vecteur d'orientation y (en v) est un diviseur de 3|v|
|y| | 3|v|
de même pour les arêtes
L'ordre du vecteur d'orientation x (en u) est un diviseur de 2|u|
|x| | 2|u|

Remarque
3|v| ==> 3 parce qu' un sommet a 3 orientations
2|u| ==> 2 parce qu' une arête a 2 orientations
L'ordre de l'orientation ne dépend que de l'ordre de la permutation

On va faire la démontration pour les sommets (v,y)∈S8 x Z38 , pour les arrêtes c'est pareil. Mais avant on va étudier un polynôme nécessaire à la démontration.

Posons: Pd(v) = 1 + v + v² + ...+vd-1 un polynôme en v et P0(v) = 0
Commençons par avoir quelques propriétés de ce polynôme
P1. Pab(v) = Pa(vb) Pb(v)
P2. Pab+r(v) = vrPab(v) + Pr(v)
P3. P3|v|(v) = 3P|v|(v)

Démontration P1
Posons w = vb
Pa(w) = 1 + w + w² + ...+wa-1
Pb(v) = 1 + v + v² + ...+vb-1



1 + v + v² + ...+ vb-1
+vb + vb+1 +...+ v2b-1
+v2b + v2b+1 +...+ v3b-1
+v3b + v3b+1 +...+ v4b-1
...
+v(a-1)b + v(a-1)b+1 +...+ vab-1
= Pab(v)

Démontration P2
Pab+r(v) - Pr(v) = vr + vr+1 + vr+2...+ vab+r - 1
= vr(1 + v + v2...+ vab-1)
= vr( Pab(v) )

Démontration P3
P3|v|(v) = P3(v|v|) P|v|(v) ; d'après P1
= P3(1) P|v|(v) ; car |v| est l'ordre de v
= 3P|v|(v)

Démontration de théorème
L'ordre du vecteur y est un diviseur de 3|v|
donc soit d = l'ordre de y càd le plus petit entier tel que
y + v(y) + v²(y) + ...+vd-1(y) = 0 (*)
il faut donc démontrer que d divise 3|v|

on divise 3|v| par d donc 3|v|=kd+r avec 0 ≤ r < d
P3|v|(v) = Pkd+r(v)
3P|v|(v) = vrPkd(v) + Pr(v)
3P|v|(v) = vr( Pk(vd) Pd(v) ) + Pr(v)
appliquons à y
3P|v|(v)(y) = vr( Pk(vd) Pd(v)(y) ) + Pr(v)(y)

3P|v|(v)(y) = P|v|(v)(3y) = 0 car y∈Z38
Pd(v)(y) = 0 car d est l'ordre de y
d'où
Pr(v)(y) = 0
mails alors comme d est le plus petit entier qui verifie (*) donc ca force r=0
finalement on a donc
P3|v|(v) = Pkd+0(v) d'ou 3|v|=kd ca signifie que d divise 3|v|

[1] 2

Accueil

DMJ: 27/02/2017







Facile

Moyen

Difficile

Les Crazy

Les Stars

Divers

Théorie des Twists

Quiz (Master Cube)