R EVUE FRANÇAISE D ’ INFORMATIQUE ET DE
RECHERCHE OPÉRATIONNELLE , SÉRIE ROUGEJ EAN -L OUIS N ICOLAS
Calcul de l’ordre maximum d’un élémentdu groupe symétrique Sn
Revue française d’informatique et de recherche opérationnelle, série rouge, tome 3, no 2 (1969), p. 43-50.
<http://www.numdam.org/item?id=M2AN_1969__3_2_43_0>© AFCET, 1969, tous droits réservés.
L’accès aux archives de la revue « Revue française d’informatique et derecherche opérationnelle, série rouge » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une
infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/

R.I.R.O.
(3e année, N° R-2/1969, p. 43-50)

CALCUL DE L'ORDRE MAXIMUM
D'UN ELEMENT DU GROUPE SYMETRIQUE Snpar Jean-Louis NICOLAS ORésumé. — Soit Sn le groupe des permutations de n objets. On désigne par g{n) Vordre
maximal d'un élément de Sn. Cet article expose un algorithme de construction d'une table
des valeurs de g{n). On calcule pour cela des fonctions gk{ri) par récurrence sur k, et pourk assez grand, on démontre : g(n) = gk{n). Dans les programmes, g(n) gui est un entier trop
gros pour pouvoir être traité comme tel en machine, est considéré comme un réeL On évite
les erreurs de comparaison des nombres en virgule flottante, en constatant que le quotient desnombres à comparer n'est pas trop proche de 1. Les résultats obtenus sont les suivants :1) une table de g(n) jusqu'à n = 8 100, avec la décomposition en facteurs premiers de g(n).
2) Une table des valeurs de n pour lesquelles g(n) est différent de g{n — 1) ainsi que les 8 premiers chiffres de g{n) jusqu'à n = 32 000.

Soit Sn le groupe des permutations de n éléments. L'ordre d'une permutation a € Sn est le plus petit entier m > 1 tel que am soit la permutation identique. E. Landau [1], § 61 définit la fonction :(1)g(n) = max [ordre de a]et démontre log g(ri) ~ V« logn. Dans [2] et [4] nous avons démontré plusieurs propriétés arithmétiques de la fonction g(ri).
L'objet de cet article est d'exposer un algorithme de construction d'une
table de valeurs de g(n).
§ 1. CALCUL THEORIQUE
Un élément a € Sn se décompose en cycles de façon unique. Par exemple,pour n = 9,/l

2 3 4 5 6 7 89\\9 8 7 6 1 2 3 4 5/= (1 9 5)(2 8 4 6)(3 7)0) Ce travail a été rédigé alors que l'auteur était détaché à l'Université de Sherbrooke,
province de Québec, Canada.

44

J.-L. NICOLAS

L'ordre d'un élément est donc le p.p.c.m. des longueurs de ses cycles.
Dans l'exemple ci-dessus, l'ordre est donc 12.
Si G € Sn9 soient nu n2,..., nk les longueurs de ses cycles; on a :n2n =nk

Ordre de a — p.p.c.m. (nl9 /22,..., nk).
D'autre part une partition de n est un système quelconque d'entiers > 1 :{nu n2,..., nk) tels que n = nx + n2 + ... + nk. Par exemple, le nombre n = 5
a 7 partitions :5^4+1=3+2=3+1+1=2+2+1=2+1+1+1-1+1+1+1+1
II est facile de construire une permutation de n objets ayant k cycles delongueur (nu n2,..., nk). A 5 = 2 + 2 + 1, on associe, par exemple :/l

2 3 4 5\\2

1 4 3 5/Si n — n1 + n2 + ... + nk est une partition quelconque de n, il existe
donc un élément de Sn dont l'ordre est : p.p.c.m. (wls n2,..., nk). On a donc :g(n) = max

(2)

ÏT(n)

désignant l'ensemble des partitions de n.
On a les propriétés suivantes : (voir [1])— g(ri) diviser!
— g(n) est croissante (soit G e Sn; l'élément G' € Stt+U qui laisse invariant(n + 1) et coïncide ailleurs avec G a même ordre que a).
— Tableau des valeurs :n

3

4

5

6

7

8

910

111213g(n)

34

6

6

12

15

20

30

30

60

60'S

3

42,31,2,33,4
63, 5
3,5 4,5 2,3,5 1, 2,5,6 3 4 5 1, 3, 4, 5

ORDRE MAXIMUM D'UN ELEMENT DU GROUPE SYMETRIQUE Sn

45

La troisième ligne indique la (ou les) partition(s) de n d'ordre g{n).
— g(n) n'est pas strictement croissante : g(l2) = g(13).
— Pour n — 6, n = 11, on constate que plusieurs partitions sont d'ordreg(n) (on appelle ordre d'une partition l'ordre d'un élément a de Sn associé).
— Parmi les partitions d'ordre g(n), il en existe une, telles que les (nt)L<isoient des puissances de nombres premiers ou des 1. En effet si :^n = nt + n2 + ... + nk
^t si nt — ab, avec a > 1, b > 1, (a, b) = 1, a, b € N, on a :a£ _ ( a + fe) = (a _ i)(i — 1) — 1 ^ 0et les partitions :n - a + b + n2 + ... + nk + 1 + 1 + ~* + 1 - ab + n2 + ... + n*
ab-(a + b)

ont même ordre, les multiples de ab étant les mêmes que ceux de a et b puisqueDans la formule (2) on peut donc se restreindre au cas où n( =(3)g(n) = max 1 1 /le « max » s'étendant à tous les systèmes de couples p,r(p premier, r € N)de somme 2/?r ^ n.
Nous allons maintenant définir une fonction arithmétique / à laquelle g(ri)est attachée de façon simple.
Définition : Soit / : N* -> N définie par1(1) = 0(4){n*H*premier et a£ entier

Autrement dit, pour calculer l(n), on écrit la décomposition en facteurs
premiers de n et on ajoute les facteurs ainsi écrits.
Par exemple pour n = 36 = 22 • 3 2 ? on a :/(«) = 4 + 9 = 13.
La fonction arithmétique / est additive :(m, w) = 1 => /(m, «) — /(m) + /(«)
et sa restriction aux nombres/?* (p premier, a ^ 1) est l'application identique.
On a l(n) ^ w pour tout n et /(«) = n entraîne n = ^ a .

46J.-L. NICOLAS

La formule (3) devient alors :(5)g(n) = max j
On remarque que cette formule permet de définir g(0) = 1 et que l'on apour tout n :(6)l(g(n)) < ».
La formule (5) nous servira désormais de définition de g(n).

Les fonctions gk(n)On désigne par pk le fc-ième nombre premier (px = 2,p2 = 3,...) et par Hk
l'ensemble des nombres entiers qui n'ont pas d'autres diviseurs premiers que
Pu Pi, ->Pk- Ainsi Hx = { 1, 2, 4, 8, 16,... } ,H2 = { 1, 2, 3, 4, 6, 8, 9, 12, 16, 24,... } .
On définit alors :(7)&(«) = max jKj) < njH

On constate que gx(0) = 1 et que, pour n ^ 1, g^ri) est la puissance de 2
immédiatement inférieure ou égale à n.
Calcul de g2.
H2 = I I H2\Écrivonsavec# £ = Hu H2l = 3# l 5 etc , ...„Hi^VH,= {3^2-3^4.3^..}On aura :(8)g2(n) = max 7 = max ƒ max 7^
Si Ï = 0,max 7 = max 7 = g^n)
Si Ï > 0,max j = 3l • max= 3lg1(« — 3')

La formule (8) devient :1g2(n) = max [gl(n)9 3gl(n — 3), 9gl(n - 9), ...s $gx{n — 3 )le dernier terme du crochet étant tel que 3* < «.
Exemple g2(18) = max [16, 3 • 8, 9 • 8] = 72.

ORDRE MAXIMUM D*UN ELEMENT DU GROUPE SYMETRIQUE Sn

AlFormule de récurrence. Par la même méthode, on démontre que, pourtout k ^ 2, on a :(9)gk(n) = max [gk-x{n\ pkgk-x(n —pk), ...,/^-^/f —/£)]
Cette formule nous permet de calculer de proche en proche les gk(n).
Calcul de g(n). Soit p = />* le plus grand nombre premier divisant g(n).
Alors pour k' ^ k, gk<(n) = g(n). En effet :g(n)= maxyetg(n)£Hk,donc :io*)<»g(n) = max j = &,(»)
La formule (3) ou la formule (6) indiquent : p ^ n. En fait, on démontre(voir [2] ou [4] que / > ~ V» logn et il est possible d'adapter la démonstration
pour montrer que p < a\/n log n avec « > 1. Pour dresser la table de g(ri)pour n — 1 à N, il suffit donc de calculer #k(«) de n = 1 à N avec k assez grand.
Pour JV = 32 000, VNlogN = 575, on prend A: = 140, /?ft = 809 ce quicorrespond à : a = 1,4. En fait le plus grand nombre premier utilisé est
641 =j?ii6 ce qui fait que :pour n < 32 000,g(n) = gtl6(n) = gk{n) pour k > 116§ 2. PROGRAMME DE CALCUL POUR gk(n)EN LANGAGE FORTRAN
Au début du programme, la machine a en mémoire les nombres premiersP(K) deK=lk
KMAXet G(N) est égal à gt(N) de N = 1 àZ) 0 12 ^ = 2, ^M^JTN=NMAX5 ƒ =1
Z = P(K)
6 IF(G(N) — Z*G(N — Z))9,9,8
9G(N)=^Z*G(N—Z)
8 ƒ=ƒ+ 1
16 IF{N—Z) 11,11,6
11 N=N—l
17 IF(N—P(K)) 12,80,580 IF(K*EQ*2) G(3) =12 CONTINUE

48

J.-L. NICOLAS

II est commode de faire décroître N (Instruction étiquetée 11). En effet, lecalcul étant arrivé à K = Ko et N = No, l'ordinateur a en mémoire pour G(N) :si N> Nosi

G(N) - gK0(N)N^N0

En particulier, dans l'instruction étiquetée 6, G(N—Z) représente
gK-i(N—Z) et G(N) représente le nombre que l'on augmente petit à petit(lorsque I augmente) par l'instruction étiquetée 9, pour devenir gK(N).
L'instruction étiquetée 80 est introduite pour compenser la lacune suivante.
Le programme précédent ne tient pas compte du cas n = pi de la formule derécurrence (9). Si dans cette formule, c ' e s t / ^ ^ ( O ) qui réalise le maximum,alors gk(n) est une puissance exacte de nombre premier. On montre facilementque ça n'arrive pour k ^ 2 que lorsque k = 2 et n = 3.
Enfin, lorsque pi ^ NMAX, la formule de récurrence (9) devient :gk(n) = max [gk-x(n)9 Pugu-^n —pk)]
et le programme se simplifie.
§ 3. PROGRAMME G 32000
L'ordinateur utilisé 'est le C.D.C. 3600 de l'Institut Biaise-Pascal de laFaculté des Sciences de Paris. Sa mémoire est de 32 767 mots de 48 bits.
On fixe NMAX = 32 000, KMAX = 140, P(140) = 809. On prend G(N)en virgule flottante. La comparaison étiquetée 6 peut être douteuse. On laremplace par :6 IF(G(N) — A*Z*G(N — Z)) 7,7,8
7 IF(G(N) — B*Z* G(N — Z)) 9, 9, 10
On prend initialement A = 1.01 et B = 1/A. Si l'on arrive à l'instructionétiquetée 7 et si le nombre G(N) — B*Z*G(N— Z) est positif, c'est que lequotient G(N)/Z*G(N— Z) est compris entre B et A. Dans l'instructionétiquetée 10 et les suivantes, on imprime les nombres K, N, Z et le quotient
G(N)/Z* G(N—Z) et l'on remplace A et B par des valeurs plus voisines de 1.
La valeur finale de A est : AMIN = 1,000 009 299 3, ce qui fait que tous lesquotients sont ou bien supérieurs à AMIN ou inférieurs à IJAMIN.
On détermine également pour chaque i la plus petite valeur mk(i) de n telleque plk divise gk(n). C'est la plus petite valeur de n pour laquelle l'instructionétiquetée 9 est utilisée. Il suffit de rajouter après l'instruction étiquetée 9 l'instruction suivante :M(I) - Net d'imprimer M(I) avant d'augmenter K. C'est ainsi que l'on voit que lesnombres premiers au-delà de 641 ne servent pas.

ORDRE MAXIMUM D'UN ELEMENT DU GROUPE SYMETRIQUE Sn

49

Enfin, cette table permet de déterminer les intervalles sur lesquels g(n) estconstante. En effet, on peut montrer que si les nombres g(ri) et g(n — 1) sontdifférents, alors,• > AM1N. On pose A =^et on imprimeg{n — 1)
2
Net G(N) lorsque G(N) ^ A* G(N— 1). La table contient ainsi 10 923 valeursdifférentes de g(«). On obtient :g(32 000) = £(31 999) - 2,785 921 329 • 10261§ 4- PROGRAMME G 8100
Dans ce programme, on limite la table à NMAX = 8 100 et KMAX = 90.
(En fait les résultats du programme précédent auraient permis de prendre
KMAX = 63.) Mais on va obtenir la décomposition en facteurs premiersde g(ri). Cette décomposition va être inscrite sur trois nombres entiers :MUl(N), MU2(N), MU3(N). Si la décomposition en facteurs premiers de g(n)s'écrit :g(n) = 2 3 , ...pk ...,On a :2 a i ^ 8 100, 3 a3 < 8 100, .../>£* < 8 100, d'après (6)On a donc : ax < 12, a 2 < 9,..., a 14 < 9 ;/715 = 47= 193

doncdonc

a 15 < 2, ..., a 43 ^ 2
a 4 4 ^ 1,..., oc90 ^ 1

MUl(N) représente le nombre dont les chiffres décimaux sont <x.l9 oc2,..., oc14.
MU2(N) sera écrit en base 3 et MU3(N) en base 2. On aura :144390

fc=l

fe=15& = 43M£/l(AO = £a fe 10 14 ~ fc ; MU2(N)= £ a f c 3 4 3 ^ ; MU3(N) = £ a fe 2 90 ^Le calcul de ces nombres se fait en posant initialement :MUl(N) = lOngt(N)et

MU2(N) - MU3(N) = 0.

On sépare la boucle K en 3 parties : K = 2 à 14; de 15 à 43; de 44 à 90. Et àchaque fois que l'on modifie la valeur de G(N) par l'instruction étiquetée 9,
on modifie la valeur de MUl :— Z)Z)+

10** (14 — K)*I

Lorsque 15 < K < 43, cela devient :109 G(JV) = Z * G(iV — Z)

MU\(N) ^ MU\{N — Z)
MU2(N) = MU2{N—Z) + 3* *(43 — K,+I50

J.-L. NICOLAS

Résultats. — Là encore, on n'imprime pas G(N) si G(N) = G(N— 1)
c'est-à-dire si MUt(N) = MU^N— 1) pour i = 1, 2, 3. Au moment de l'impression, on décodifie MUl, MU2, MU3 pour avoir les valeurs de otfe. Ontrouve ainsi pour n = 8 003, g(n) = 4,465 189 084 • 10120
ai = 5, a 2 = 4, oc3 = 2, oc4 = 2, a 5 = 2, a 6 = a 7 = ... = oc56 = 1,oc57 = 0, a 58 = a 59 = 1, or60 = 1, a 6 1 = 0 a 6 2 = 1,et pour k > 62, oc& = 0. On remarque que 269 = p57 et 283 = / ^ i ne divisentpas #(8 003).
Il me reste à remercier M, le professeur R. de Possel qui a dirigé ce travail
qui constituait mon deuxième sujet de thèse et M. Tréhel qui a bien voulu
relire mon manuscrit.
REFERENCES[1] E. LANDAU, «Handbuch der Lehre Von der Yerteilung der Primzahlen» Leipzig
und Berlin, B. G. Teubner 1909 (2* Auflage, New York, 1953).
[2] J. L. NICOLAS, « Sur Tordre maximum d'un élément dans le groupe Sn des permutations », Acta Arithmetica (14), 1968, pp. 315-332.
[3] J. L. NICOLAS, Ordre maximal d'un élément du groupe des permutations etnombres très hautement abondants », C.R. Acad. Se. Paris (266), 1968, p. 513-515.
[4] J. L. NICOLAS, «Ordre maximal d'un élément du groupe des permutations ethighly composite numbers » (Thèse) à paraître au Bulletin de la Soc. Math, deFrance (1969).