Acta Math Hung

Description

Niveau: Secondaire, Lycée, Terminale
Acta Math. Hung. 45(1--2) (1985), 69--84. DISTRIBUTION STATISTIQUE DE L'ORDRE D'UN ELEMENT DU GROUPE SYMETRIQUE J. L. NICOLAS (Limoges) I. Introduction (1) avec Soit S. le groupe des permutations de n objets. P. Erd6s et P. Turfin ont d6- montr& (cf. \[5\]) lira Pr0b \[ log (ordre de a)-(1/2) log 2 n 1 / e -t~/2 dt _ = en mettant sur S. la mesure d'dquiprobabilit6. P Erd6s et P. Turfin annoncent qu'il est possible d'obtenir un terme d'erreur dans la formule (1). Pour chaque permutation aCS. , nous d6signerons par n I <: 17 2 ~. . . -< n k les diff6rentes longueurs de cycles de a, et par mz ... . ,mk leur mulfiplicit6, de telle sorte que Z tll i n i ~- n . La d~monstration de (1) est bas6e d'abord sur le r~sultat (cf. \[4\]): except6 o(n !) permutations, tousles 61~ments a~ S~ v6rifient: (2) exp ( - 3 log n (log log n) 4) _<- ordre de o- <= 1 tl 1112, .

• ica hunga'


• notations de la propo- sition pr6c6dente


• ddsigne ia constante d'euler


• acta mathemat ica

Sujets

• Mathématiques
• Première
• Szalay
• Symétrie

Informations

• Publié par: profil-ziem-2012
• Nombre de lectures: 14
• Langue: Français

Extrait

Acta Math.
45(1--2) 69--84.
DISTRIBUTION STATISTIQUE DE L'ORDRE D'UN
ELEMENT DU GROUPE SYMETRIQUE
J. L. NICOLAS (Limoges)
I. Introduction
Soit S. le groupe des permutations de objets. P. Erd6s et P. Turfin ont d6-
montr& (cf.
lira Pr0b log (ordre de a)-(1/2) log (1)
avec
_=
en mettant sur S. la mesure d'dquiprobabilit6. P. Erd6s et P. Turfin annoncent qu'il
est possible d'obtenir un terme d'erreur dans la formule (1).
Pour chaque permutation aCS., nous d6signerons par
<: ~...-<
les diff6rentes longueurs de cycles de a, et par .... ,mk leur mulfiplicit6, de telle
sorte que
tll ~- n.
La d~monstration de (1) est bas6e d'abord sur le r~sultat (cf. [4]): except6
o(n permutations, tousles 61~ments a~ v6rifient:
(2) exp (- log (log log n) ordre de
tl 1112, ..
et ensuite sur la distribution des valeurs de la fonction
f(a)= Iogn~
l~i~k
l'aide de sa fonction caract~ristique.
Par la suite, M. R. Best et J. D. Bovey ont red~montr~ la loi limite v~rifi6e
par fi par des m6thodes plus dl6mentaires.
Nous allons d6montrer le th~or~me suivant, qui am61iore (2):
celles qui restent vdrifient
log (ordre de a) f(a) log log log (log log log tog n).
Acta Mathematica H~ngarica 45, 1985
n 1 [ I Z !) 3 mz : n e 2 2 k n n i 1 [5]) Hung. dt / = ~ - + n i (1985), n [2] O n n n
[1]
171~
<= o- _<- 4)
S~
17
-t~/2 La d6monstration du th6or6me repose sur l'id6e suivante, fournie par P. Erd6s:
dans une permutation al6atoire, la moiti6 des cycles est de longueur paire, un tiers des
cycles est de longueur multiple de etc.., et le hombre de cycles 6tant environ log
la contribution des nombres premiers p<-logn dans la diff6rence f(a)-
-log (ordre de a) est approximativement:
logp logn logn(loglogn+O(1)).
La contribution des nombres premiers nest n6gligeable. La proposition
permet d'6valuer tr6s pr6cisement le nombre de ire qui ont exactement cycles
de longueur multiple de et je remercie M. Szalay, qui m'a signal6 la r6f6rence
La proposition 2, qui rn'a par A. Odlyzko, majore le hombre de aES~
pour lesquelles est divisible par une puissance assez grande d'un produit
de nombres premiers.
Nous montrerons ensuite
On uniformdment en xER:
Prob f(a_~)-( U2)l~
x} =qS(x)+O(1/l/~ogn):
La d6monstration du th6orSme reprend les calculs originauxde P. Erd6s et
P. En fait un calcul similaire fait dans [10], pour 6tudier une fonction
voisine de f, sur l'ensemble des polyn6mes unitaires de degr6 sur un
corps
On d6duit imm6diatement des th6orSmes et 2:
On uniformdment xER:
~/~>'0~"' ,o~'. ~o~. ~o~. ~> )~o~ ,o.
)"
Nous conjecturons que l'on peut supprhner le log log log dans le reste du
th6or6me et du th6or6me
Nous 6crirons, pour simplifier
l=logn; 12=loglogn; Iz=logloglogn.
Pour et pour fix6, nous poserons: N(v)= le hombre de Ion-
i=1
gueurs distinctes de cycles de multiples de La lettre p, ou non d6signera
toujours un nombre premie r. Enfin nous noterons la partie enti6re de x.
Acta Matherna$ica Hunga'r~ca
a o 2. 2 6t6 l<-v<=n, L ~ ~ 9 ~or~o (1/]/3-)logZ/2n {~o~ 45, n n ~ro~ p k [X] en n, n~n~...n 1 a : ,o~ fini. sugg6r6e o-ES, Tur~in. ~-log ~'~ a O ~ } P i _ + a 1 [ ~, d6finie ] 3, 1985 ~ 1 < k indic6e 6t6 [11]. 1 +
[x]
v.
1,
NOXAX~ONS.
3. 1,
~o~ -~1/~> o>
3. TH~ORI~ME
") F~
TH~OR~ME
S~
p_~logn
NICOLAS J. 70 DISTRIBUTION STATISTIQUE DE L'ORDRE D'UN ELEMENT DU GROUPE
IL D6monstrafion du
Enonqons d'abord quelques lemmes:
Soit x>0. On a:
pour
m! -- m~u
etpour O<v<--x:
z~ m! <-
Elle est facile (cf. p.
Soit <--vl<v2<... <vr avec Le hombre de permutations de
i=1
ayant au moins un cycle de longueur vl, un cycle de longueur .... un cycle de
longueur est n!/(vlv2...Vr).
n!
Vl!V2l...Vrl(n--Vl--V -- ...--V,)[
fagons de choisir parties de 2, ..., n} de cardinal vl .... v,. Dans chacune de
parties on doit avoir une permutation circulaire ce qui donne (vl-1)!...(vr-1)!
choix possibles. Dans ce qui reste, n'importe quelle permutation marche, il en
(n-va-...-vr)!. Cette d6monstration est voisine de celle de la formule de, Cauchy
(cf t.2, p. 75).
Soit rdel v~rifiant 0<~<1. On a:
pNx
logp logx+O(1); logp _logx+O(1).
pra
Si etsi on a:
(logx)xX-1
Soit 0(x)= ~,logp la fonction de ~ebygev. On a, par
l'int6grale de Stieltjes
2-1~ ff_~ ~/ ~20(0
Acta Mathematica Hungariea
~ , x>=2 "ces 1 + 149). 3. p>--x SY,'CLETRIQUE r 2 ~=>2, 45, < 1985 2 S / = ~ vi<=n. n ~ y 71 a [3], 1 l 3 ~ = 2. 9 a P = [8], P 9 th6or~me , x - I1 < y pm<- u>=x: ~ Z _
-at d[O(O]?. p<=x~'
p<=x
DI~MONSTRATION.
p<=x
LEMME
{1,
Dt~MONSTRATION.
<- v~
v~.
LEMME
DI~MONSTRATION.
(71
1. LEMME et comme O(t) O(t), cette quantit6 est:
Pour 6valuer z~ (logP)P -a", on proc~de de m~me en remplar O(x) par
pm~x
~k(x)= logp, la seconde fonction de Ceby~ev. L'estimation de (log p)/p est
pm~x p~x
classique (cf. ch. 22).
De m~me, soit 7r(x)= 1; on a:
p~x
~(x)-i += ;L~(O
~-J t--/rTr- at.
p>=x
Or on sait que t) pour tout t, donc
3/2
-- 2t dt
log (log x)x ~-~
4. Soit o92~n. Si l'on de nombre de permutations
les permulations restantes ont la propridtd suivante: les cycles de
~3n!
longueur sont uniques et les cycles de ont une multiplicit6
Ce lemme est le lemme III de
Soit:
(1/n!)Card{aES,; m, =j}
la probabilitd qu'une permutation de exactement cycles dont les sont
multiples de Alors, si on pose r=[n/~], on a:
~1 Is(r,k)l (~)(~_l)k_
Cj
s(r, k) d&igne le nombre de Stirring de et on la majoration, pour
HJ-1
cj -1/~ j!a)'" (j+H)
olt constante d'Euler, et H= +-f +...
D'apr6s la formule 0.27, p. de on a:
ci -1. ~+r
j=o
Acta Mathematica Hungar~ca 45, 1985
1 NICOLAS LO91 j 3 = ~ Z " [9], [4]. Iongueurs 7 ~ _ Z esp~ce, f ~ i x x p-~" = 1 longueur 0 + 20<=o9~, i x l c - J. # a ~ rc(t)<-_(3/2)(t/log J + n x J [11], S = 1 1 183 o92!1 >o91 ddsigne Ia L. f enlOve un i = air
Dt~MONSTRATION.
r-'----'T"
e~r <--
r>=2
ere oi~
l" ~,.
S~
O~[ll
1. PROPOSITION
D~MONSTRAT~ON.
~_o9~. <=o9~,
1__~__|,
LEMME
p__>~
"<= -~" "<
['~
at-*dt)=
2C DISTRIBUTION STATISTIQUE DE L'ORDRE D'UN ELEMENT DU GROUPE SYMETRIQUE 73
et d'apr6s la d6finition des nombres de Stifling de premi6re le deuxi6me
membre ci-dessus est 6gal t.2, p.
(x+ ~-- 1) __
k)[- j=O ~J
ZXSZr!,
j=o k=j
Ce qui nous donne la premi6re formule de la proposition.
On utilise ensuite la majoration:
(n_l)![l+l+...+ ]k-~
is(n, k)l (k-l)!
Cette majoration peut &re d6montr6e par r6currence en utilisant la formule:
]s(n+l, k+l)] k)l+nls(n, k+l)l.
On obfient alors:
cj (r-l)! Hk_z k!
r! j!(k-j)! 1-
et en posant i= k-j,
j-1 Hi(1
Fj!~ (i+j).
La sommation est major6e par:
(HO-1/~))'
i! (i +j) (H(t l/a) +j) exp (H(1 1/~)).
Compte tenu de ce que
H= l+~+...+-- 7+logr
F--I --
on obtient le r6sultat annonc6.
Si enl~ve de S. de O(n!/(logn)2),
restantes ont la Pour tout de la
gueurestmultipledec~est log,,~ +O(~__~10,
Fixons d'abord On pose, avec les notations de la propo-
sition pr6c6dente, x=H/a, jo=x-x jl=x+xU+ On choisira u=0,8. Le hombre
de permutations enlever, celles qui ont moins de (ou plus de Jl) cycles
dont la longueur est multiple de vaut:
ej+ cj
j_ o'fl. (i--l)!)
Acta Mathematica Hungar~ca
" Is(n, 1 propriOtd: k 1 - ~ esp6ce, 48) = le k=j nombre = = 1 cycles (cf. dont r-70~=~, ] - lon- k - ~ 1 H l'on Is(r, S (c~-S1)i nombre J~:Jo = 1 ~ 2e~r k [3], h ~ c'est-~t-dire un ~ ~ 3 i = ~. i ~ celles ~, I permutations
1985 45,
J~=J,
"~ +j~= -1/~ <=
J0
1. ",
D~MONSTRATION.
s.
~<=I/l~,
COROLLAIRE.
<-
,=o
i=0 c2<=
1~cO -~J
(k--1)----------~
<_-
n---2-T) <=
czk o~=,Z ~--f.
~t: J.L.
et, par le lemme
ex ex /1
Or on a:
jolog (ex/jo) x-T O(x
9. Jl l) log (ex/(jl x- x- (x
Ce qui nous donne:
pour un certain >0. On remarque ensuite que
+T+ ... +~--i-- log r+O(1)
etdonc e~=O(rl/~). Enfin, comme r=[n/a], on a:x=(1/a)(l+O(12)); comme
a<=l/l~, on voit que x>=l~/2 pour assez grand, etdonc
(exp (- (l-S)
en choisissant 0,8.
En faisant le mSme raisonnement pour tousles on obtient qu'except6
O(n!/l permutations, le nombre de cycles dont la longueur est multiple de est
compris entre x-x" et x+xU+ ce qui ach~ve la d6monstration du corollaire.
Pour d6montrer le th6or6me nous allons construire des sous-ensembles S,
S,,..., St, a)c S~ tous tels que Card (S,- S~ (n
Construction de On utilise le lemme avec ~o1= loI/]~] et On
bien:
et les aC S, ont l