© Éditions H&K
Mines Maths 1 PC 2018 -- Corrigé
Ce corrigé est proposé par Hervé Diet (professeur agrégé) ; il a été relu par
Théo
Lenoir (ENS Ulm) et Florian Metzger (docteur en mathématiques).
Ce sujet porte sur l'espace de Rademacher, défini comme le sous-ensemble q,n
de Mq,n (R) constitué des matrices à coefficients dans {-1, 1}. On prouve le
théorème
de Komlós qui s'énonce ainsi : si M(n) est une variable aléatoire à valeurs
dans n,n
qui suit la loi uniforme, alors
lim P(det(M(n) ) = 0) = 0
n+
En d'autres termes, une matrice aléatoire est inversible avec forte probabilité
lorsque
n est grand.
Le sujet fait largement appel aux matrices et aux probabilités. Il se compose de
six parties connectées les unes aux autres.
· La première établit quelques majorations sur les coefficients binomiaux à
l'aide
de raisonnements classiques (équivalents, récurrences, etc.). Ces majorations
permettront de calculer des limites dans la suite du sujet.
· La partie B étudie de manière exhaustive le cas de la dimension 2.
· La partie C donne quelques bornes sur les probabilités qui seront utilisées
ultérieurement. Ces résultats sont établis en travaillant sur des espaces
vectoriels.
· La partie D porte sur des aspects ensemblistes (cardinal, dénombrement) et sur
les anti-chaînes qui sont les sous-ensembles de P({1, ..., n}) dont les éléments
sont incomparables (ni A B ni B A si A 6= B). On démontre alors un
théorème d'Erdös-Littlewood-Offord : si v Rn tel que |vj | 6 1 pour tout
j [[ 1 ; n ]], si J est un intervalle de R de longueur 2 et si n est assez
grand,
1
(n)
P hL1 , vi J 6
n
(n)
où L1
désigne la première ligne de la matrice aléatoire M(n) .
· Ce théorème est exploité dans la partie E. Cela permet de prouver des
majorations nécessaires pour la suite.
· La dernière partie est consacrée à la démonstration du théorème de Komlós.
On y exploite tous les résultats établis précédemment.
Le sujet est assez difficile pour la filière PC. Il comporte des raisonnements
qui
peuvent être déstabilisants et la manipulation des probabilités requiert
beaucoup de
rigueur. Comme le sujet suit une progression linéaire, il n'est pas judicieux
de passer
une partie puisqu'elle servira à coup sûr pour la suite. Cela en fait un sujet
utile en
fin de révision car il couvre nombre de thèmes d'algèbre au programme.
© Éditions H&K
Indications
n
n
1 Étudier le rapport
/
. Étendre la propriété à k > n/2 par symétrie
k+1
k
des coefficients binomiaux.
2 Différencier les cas n pair
puis utiliser la formule de Stirling pour cher et impair
n
cher un équivalent de
.
n/2
3 Traiter le cas k = 0 à part. Faire un raisonnement par récurrence sur k.
4 Prouver que 1,n engendre tous les éléments de la base canonique de Rn .
5 Calculer l'espérance de E(M1,1 ) puis utiliser les propriétés de l'espérance.
6 Appliquer la formule de transfert.
8 Commencer par déterminer les valeurs de
P(Mi,j = Mk,l ) et P(Mi,j = -Mk,l ) avec (i, j) 6= (k, l)
On pourra ensuite poursuivre les calculs et noter que det(M(n) ) = 0 lorsque les
colonnes L1 et L2 sont liées.
9 Utiliser l'équivalence démontrée pour décomposer l'événement det(M(n) ) = 0 .
10 Définir une base de H et la relier aux i,j .
11 La méthode du pivot de Gauss donne les n - d pivots, et les colonnes sans
pivot
donnent les indices 1 6 j1 < j2 < · · · < jd 6 n. 12 Attention à tourner la page du sujet pour voir les indications. 13 Exploiter la méthode d'orthogonalisation de Gram-Schmidt sans normaliser les vecteurs pour construire le vecteur voulu. 15 Étudier la restriction de à {1, . . . , |A|}. 17 Utiliser la question précédente pour décomposer l'ensemble A. P P 19 Étudier la différence vj - vj pour montrer qu'il reste au moins un élément jB jA et en déduire une minoration. 20 Prouver d'abord que AJ = {A P({1, . . . , n}) | sA J} est une anti-chaîne. 21 Écrire la négation de la définition proposée. 23 Trouver une majoration de la probabilité désirée qui ne dépende que de n. Étudier la limite du produit de ce terme et de n pour conclure. 24 Raisonner par l'absurde sur le nombre de coordonnées non nulles de v. 25 Choisir une suite d'indices 1 6 j1 < j2 < · · · < jk 6 n tels que l'on puisse ramener le problème de 1,n à 1,m et appliquer le résultat de la question 20. 27 Scinder la somme obtenue en deux morceaux, de 1 à n - tn puis de n - tn + 1 à n - 1 et majorer chaque partie. Choisir une suite (tn ) à croissance moins rapide que ( ln n), par exemple (ln n)1/4 . © Éditions H&K A. Coefficients binomiaux n 1 Soit n N et k un entier tel que k + 1 6 n/2. Le coefficient binomial est k non nul, ce qui permet de considérer n k+1 n! k!(n - k)! = × (k + 1)!(n - k - 1)! n! n k n-k n+1 = = -1 k+1 k+1 La fonction x 7 1/x est décroissante sur R+ et k +1 est inférieur à n/2 donc à n/2. On en déduit que 1 1 2 >
=
k+1
n/2
n
soit
d'où
n
k+1
2
2
2
> (n + 1) - 1 = 2 + - 1 = 1 + > 1
n
n
n
n
k
n
L'application k
7
est croissante sur {0, . . . , n/2}.
k
D'après le résultat précédent, on a
n
j n ko
n
n
k 0, . . . ,
6
k
n/2
2
n
n
Il suffit alors de remarquer que
=
donc, si k > n/2 alors
k
n-k
jnk
n
n
= n - k < = n - k 6 k>
2
2
2
n
car n - k est entier. Par croissance de k 7
sur [[ 0 ; n/2 ]], on obtient
k
jnk
n
n
n
=
6
si k >
k
n-k
n/2
2
La majoration est aussi vraie lorsque k > n/2. En conclusion,
k {0, . . . , n}
n
n
6
k
n/2
2 Soit n N, on va faire l'étude selon la parité de n.
· Considérons le cas où n est pair. Soit p N tel que n = 2p. Alors
(2p)!
n
=
n/2
p!2
© Éditions H&K
On peut maintenant utiliser la formule de Stirling et écrire
2p
2p
2 × 2p
22p
e
n
=
2p
p
n/2
p
2p
e
et finalement, lorsque n est pair,
r
2
2n
n
×
n/2
n
· Voyons maintenant le cas n impair. Soit p N tel que n = 2p + 1 ; alors
jnk
1
(2p + 1)!
n
2p + 1
= p+
=p
d'où
=
=
n/2
p
2
2
p!(p + 1)!
On peut astucieusement réutiliser le travail précédent en remarquant que
r
(2p + 1)!
2 22p+1
2p + 1 (2p)!
22p
=
·
2
·
=
·
p!(p + 1)!
p+1
p!2
p
2p
Ainsi, en remarquant que 2p 2p + 1, il vient à nouveau
r
r
2
22p+1
2
2n
n
·
=
×
n/2
n
2p + 1
En conclusion,
On a
r
r
2
2n
n
× .
n/2 n+
n
2
< 1 puisque 2 < . L'équivalent précédent implique alors que 2n n n0 N n > n0
=
6
n/2
n
3 Soit n N, la propriété attendue se démontre aisément pour k = 0 puisque
1
1
n -1
2 = 1 × = < 1 = n0 0 2 2 Montrons par récurrence sur k {1, . . . , n} que la propriété n k-1 P(k) : 2 6 nk k est vraie pour tout k {1, . . . , n}. n 0 · P(1) est vraie car 2 = n × 1 = n = n1 . 1 · P(k) = P(k + 1) : supposons que pour tout k [[ 1 ; n-1 ]] la propriété P(k) est vraie. Alors n! n! 2(n - k) n 2k = 2k = 2k-1 × k+1 (k + 1)!(n - k - 1)! k!(n - k)! k+1