131 Développements pour l’oral

Ce livre paru en août 2020 aux éditions Dunod est un formidable compagnon de l’agrégatif.
Consulter la page du livre sur le site de l’éditeur.

Erratum

Les auteurs remercient chaleureusement les personnes rapportant toute erreur, même minime.
Pour ce faire, merci d’envoyer un e-mail à l’adresse ou de laisser un commentaire ci-dessous.

L’erratum officiel se trouve ici.

Nous remercions notamment Antoine Dequay, Armande Dimey, Quentin Dupré, Henri Gauthier et Thierry Lamberthod pour nous avoir signalé certains des points ci-dessous. ### Liste des notations * **Page xiii.** *Remplacer $\delta_{a=b}$ par $\delta_{a,b}$.* Le symbole de Kronecker $\delta$ est utilisé avec une forme assez libre dans la littérature comme fonction caractéristique d’une condition : $\delta_\mathcal{P}$ vaut 1 si $\mathcal{P}$ est vraie et 0 sinon. Des raccourcis sont utilisés pour les cas les plus usuels : $\delta_a$ pour la propriété $a=0$, $\delta_{a,b}$ pour la propriété $a=b$, etc. Ce sont ceux utilisés dans l’ouvrage et c’est sous cette forme qu’ils doivent apparaître dans la liste des notations. On trouve parfois les notations (souvent fonctionnelles) $\mathbf{1}$ ou $\chi$ utilisées de manière similaire. ### 5. Paires génératrices de sous-groupes de $\mathfrak{S}_n$ * **Page 23.** *Les conventions implicites sont $0!=1$, $t_0=1$ et $\prod_\varnothing = 1$.* Il est fréquent d’utiliser des conventions pour simplifier l’écriture des formules et inclure les cas particuliers, notamment en combinatoire. Il s’agit d’un équilibre entre clarté et concision, parfois délicat. Ici, l’ensemble vide peut survenir parmi les $A_j$ et faire en sorte que $a_j = 0$. Il faut donc donner un sens à $t_0$ dans la formule au bas de la page 23. Ces ensembles vides sont « virtuels », dans le sens où ils n’interviennent pas dans la décomposition de $\llbracket 1, n\rrbracket$, mais ont été introduits pour uniformiser les calculs (autrement, le nombre d’ensembles $A_j$ dépendrait de la partition choisie). Le guide dans ces situations et que ce qui n’intervient pas dans la situation (les $A_j=\varnothing$) ne doit pas intervenir dans les formules. Puisqu’il s’agit d’un produit, on choisit donc l’élément neutre $1$ pour la valeur conventionnelle de $0!t_0$. De même, les produits vides valent $1$ et les sommes vides valent $0$. * **Page 24.** *Le produit des $X^{in_i}$ est à l’intérieur des parenthèses dans (1).* Le passage entre la première et la deuxième ligne du calcul de série formelle se fait en décomposant $X^n$ grâce à la décomposition $n = \sum_i in_i$, puis en distribuant chaque $X^{in_i}$ dans le premier produit. Cela permet de reconnaître une formule de distributivité pour les sommes et les produits généraux, à droite de l’équation (1). Bien évidemment, puisque ces $n_i$ n’ont de sens qu’à l’intérieur de la somme, le produit des $X^{in_i}$ doit également être à l’intérieur des parenthèses. * **Page 24.** *Indexation à partir de $i=1$.* Dans l’équation (1) et dans la ligne suivante, les produits ainsi que la dernière somme ont été indexés à partir de $i=0$, mais cela doit être $i=1$. Dans certaines situations, ainsi au bas de la page 23, cela n’a pas d’influence : le terme correspondant à $i=0$ est l’identité. Toutefois ici, la présence de $n_0$ empêche cette liberté formelle : il s’agit du nombre des $A_j$ qui sont vides, et il peut être supérieur à $2$. * **Page 24.** *Deux sommes sont indexées par le même indice.* Dans l’expression de dérivation des séries formelles, il faut indexer la première somme de chaque ligne par $j$ et non par $i$, variable déjà utilisée dans la seconde somme. Ainsi, la première somme doit être $$\sum_{j \geqslant 1} j \cdot j! t_j X^{j-1}.$$ ### 11. Théorème $p^a q^b$ de Burnside * **Page 55.** *Les autres racines de $P$ dans $\mathbb{C}$ sont les conjugués de $\chi(g)/\chi(1)$, et non de $\chi(g)$.* Puisque $\chi(1)$ est un entier (la dimension de la représentation), ces conjugués sont les conjugués de $\chi(g)$ divisés par $\chi(1)$. Puisque les conjugués de $\chi(g)$ sont aussi des racines de l’unité, cela conclut. * **Page 57.** *Ajouter à la propriété en bas de page : « Si $x$ est un nombre algébrique et $r$ un rationnel, alors les conjugués de $rx$ sont les $rx'$ où $x'$ est un conjugué de $x$ ».* Cette propriété est en effet également requise pour expliquer l’argument ci-dessous (pour pouvoir diviser par $\chi(1)$. La preuve d’un tel résultat est, ainsi qu’expliqué dans les commentaires, immédiate en utilisant la théorie de Galois. Il est également possible de trouver des preuves, plus fastidieuses, n’utilisant que des considérations élémentaires. Voir par exemple Pollar-Diamond, *The Theory of Algebraic Numbers*, Chapitre 5, Section 3, Théorème 5.10 (qui relie la notion de conjugué comme "autres racines du polynôme minimal" et une autre notion de conjugué, pour laquelle ces propriétés sont immédiates). ### 13. Lemme de Hensel * **Page 69-70.** *Les réponses devraient être numérotées **a)**(*i*), **a)**(*ii*) et **b)**.* La notation des questions n’est pas cohérente entre l’énoncé et le corrigé. Le corrigé devrait utiliser les mêmes notations que l’énoncé. Cela ne change en rien l’ordre des réponses ni leurs contenus. ### 14. Méthodes polynomiales en combinatoire * **Page 75.** *Remplacer « au moins égal » par « au plus égal » à la question **d)**.* A la cinquième ligne de la correction de la question **d)**, le degré de $g_ih_i$ est au plus égal à celui de $M$ vu que $\text{deg}(g_ih_i)\leqslant \text{deg}(P) = \text{deg}(M)$. * **Page 77.** *Remplacer $d$ par $p$ à la question 5.* Faute de frappe à la troisième ligne de la question 5. ### 15. $\mathbb{C}$ est algébriquement clos * **Page 96.** *Les racines de $P\overline{P}$ ne sont pas nécessairement racines de $P$.* Si $z$ est racine de $P\overline{P}$, alors $z$ ou $\overline{z}$ est racine de $P$. La validité de la question et le reste de l’exercice ne sont pas affectés. ### 20. Automorphismes sauvages de $\mathbb{C}$ * **Page 102.** *Remplacer « totalement ordonné » par « bien ordonné ».* Il est possible de construire une fonction de choix dans le cas où chaque ensemble est *bien* ordonné, en choisissant le minimum de chaque ensemble. Le caractère bien ordonné garantit l’existence du minimum, alors que le caractère totalement ordonné ne serait pas suffisant (ainsi, $\mathbb{Z}$ est totalement ordonné mais ne possède pas de minimum). ### 21. Théorème d’Artin * **Page 105.** *Question d) : remplacer « linéairement indépendant » par « linéairement dépendant ».* C'est en effet cette propriété qui est prouvée dans la suite de la question, et qui entre en contradiction avec le fait que $(\alpha_i)_i$ est une base de $E/E^G$. ### 40. Billards circulaires * **Page 224.** *Supprimer la question 10(e).* Il s’agit d’un doublon de la question 10(b). ### 74. Méthode de descente de gradient * **Page 441.** *Dans l’énoncé de a), il faut montrer que $(f(x_k))_k$ est décroissante, et non $(x_k)_k$.* Dire que la suite $(x_k)_k$ est décroissante n’a pas de sens, puisqu’il s’agit d’une suite de vecteurs. De plus, le résultat n’est même pas vrai dans le cas de la dimension $1$, où la décroissance aurait un sens. L'inégalité prouvée après l’équation (1) prouve que la suite $(f(x_k))_k$, elle, est décroissante. C'est la bonne formulation à retenir pour l’énoncé. * **Page 442.** *La phrase « Par continuité, la suite $(x_k)_k$ doit converger » est erronée.* L'argument de continuité (de la fonction $x \mapsto x - \nabla f(x)$, pas de $f$ : c’est une imprécision du texte) ne prouve pas que la suite converge. Toutefois cette continuité est importante pour dire que, *si la suite converge*, alors elle converge vers un point fixe de $x \mapsto x - \nabla f(x)$, c’est à dire un point où $\nabla f(x^\star) = 0$, i.e. un point critique de $f$. Par stricte convexité, il n’y en a qu’un (le minimum). * **Page 442.** *L'argument à la fin de a) ne suffit pas à prouver que $(x_k)_k$ converge.* Cela n’est pas dérangeant, puisque seule la décroissance de la suite $(f(x_k))_k$ est suffisante pour les arguments de la question **b)**, qui concluent à la convergence (et à sa vitesse). ### 77. Méthode de Kaczmarz * **Page 455.** *Remplacer 162 par 160 dans le chapeau du développement.* À la deuxième apparition de 162, il faut remplacer la leçon 162 par la leçon 160. * **Page 456.** *Remplacer une norme double par une norme triple à la question **c)**.* Dans la correction de la question **c)**, dans la deuxième formule centrée, il faut mettre des triples barres autour de $M_i$. En effet, on parle de la norme d’opérateur de $M_i$. La bonne inégalité est donc $$\|\varepsilon_{n+1}\| \leqslant |\!|\!|M_i|\!|\!| \cdot \|\varepsilon_n\| \leqslant \|\varepsilon_n\|.$$ * **Page 458.** *Remplacer $x_0$ par $\overline{x}$ dans le troisième commentaire.* À la neuvième ligne du troisième commentaire, il faut remplacer $S = x_0 + S'$ par $S = \overline{x} + S'$. * **Page 458.** *Remplacer une norme double par une norme triple dans le cinquième commentaire.* À la première équation centrée du cinquième commentaire, il faut écrire $$\dfrac{\|\varepsilon_{n+1}\|}{\|\varepsilon_n\|} \leqslant |\!|\!|M_i|\!|\!| < 1.$$ * **Page 459.** *Remplacer $\langle u,x,u\rangle$ par $\langle u,x\rangle u$.* Faute de frappe à la première question dans le projeté orthogonal de $x$ sur l’hyperplan vectoriel $\mathrm{Vect}(u)^{\bot}$. Il faut remplacer $\langle u,x,u\rangle$ par $\langle u,x\rangle u$. * **Page 459.** *Remplacer une norme double par une norme triple dans la deuxième question.* À la deuxième question, il faut remplacer $\|f(x)\| = \|f\|\cdot \|x\|$ par $\|f(x)\| = |\!|\!|f|\!|\!|\cdot \|x\|$. ### 81. Espace des formes modulaires * **Page 477.** *Remplacer $[-1,1]$ par $[-1/2,1/2]$.* Dans la définition de l’espace $\mathcal D$, il faut remplacer $\mathrm{Re}(z) \in [-1,1]$ par $\mathrm{Re}(z) \in [-1/2,1/2]$, comme on peut le voir dans la figure 2.34. Cela correspond par ailleurs un choix raisonnable de domaine fondamental de la surface modulaire $\mathcal{H} / \mathrm{SL}_2(\mathbb{Z})$ : en effet, $\mathrm{SL}_2(\mathbb{Z})$ contient la translation $z \mapsto z+1$. * **Page 477.** *Remplacer $\frac{k\pi}{6}$ par $i\frac{k\pi}{6}$ à la question **b)** (*ii*).* Dans l’énoncé de la question **b)** (*ii*), la limite est en fait $i\frac{k\pi}{6}$. C'est bien le résultat que l’on trouve en appliquant le théorème des petits arcs. * **Page 480.** *Rajouter un « - » à la question **b)** (*ii*).* À la dernière ligne du calcul à la question **b)** (*ii*), il manque un $-1$ en facteur de l’intégrale $\displaystyle \int_{\tilde \gamma} \dfrac{dz}{z}$. * **Page 480.** *Remplacer $\frac{k\pi}{6}$ par $i\frac{k\pi}{6}$ dans le résultat de **b)** (*ii*).* À la dernière ligne du calcul à la question **b)** (*ii*), la limite tend vers $i\frac{k\pi}{6}$ et non $\frac{k\pi}{6}$. * **Page 482.** *Remplacer « dimension » par « poids » dans le troisième commentaire.* Dans le commentaire qui parle de dim $M_k$, il faut remplacer deux fois le mot « dimension » par « poids ». En effet, on cherche à calculer la dimension de $M_k$ pour les poids $k = 6,8,10$, puis à partir du poids $k = 12$. ### 86. Théorème de Plancherel * **Page 518.** *Enlever une étoile de difficulté dans le premier commentaire.* Remplacer $\bigstar\bigstar\bigstar$ par $\bigstar \bigstar$ dans le premier commentaire. ### 114. Théorème de Turán * **Page 724.** *Remplacer $\leqslant$ par $\geqslant$ dans (1).* On cherche à montrer qu’en moyenne, l’ensemble indépendant $S$ construit est assez grand. Il s’agit donc bien d’une minoration de $\mathbb{E}(|S|)$ et non d’une majoration. Ceci ne change rien à la solution proposée. * **Page 724-725.** *Dans la question **a)**(*i*), remplacer « calculer $\mathbb{P}(v\in S)$ » par « montrer que $\mathbb{P}(v\in S)\geqslant\frac{1}{d(v)+1}$ ». Remplacer les égalités par des inégalités dans la correction.* L'inégalité est toujours vraie (et suffisante pour la suite de l’exercice), mais n’est pas nécessairement une égalité. En effet, un sommet apparaissant dans $\sigma$ avant ses voisins sera nécessairement présent dans $S$. La réponse montre que la probabilité de cet évenement est égale à $\frac{1}{d+1}$, ce qui permet bien d’obtenir la minoration de $\mathbb{P}(v\in S)$ souhaitée. En revanche, la réciproque est fausse en général : $S$ peut contenir des sommets placés après leurs voisins dans $\sigma$. Un chemin à trois sommets $u_1,u_2,u_3$ fournit un contre-exemple : le processus aléatoire construit $S=\{u_2\}$ si $\sigma$ place $u_2$ en première position et $S=\{u_1,u_3\}$ sinon. En particulier $S$ peut contenir $u_1$ même si $\sigma$ le place après son voisin $u_2$. Sur cet exemple, on a l’inégalité stricte $\mathbb{P}(u_1\in S)=\frac{2}{3}>\frac{1}{2}=\frac{1}{d(u_1)+1}$. ### 104. Distance de Kendall et tri par insertion * **Page 640.** *Remplacer $x$ par $t_i$ dans l’énoncé.* Faute de frappe dans le premier paragraphe de l’énoncé, il faut remplacer $x$ par $t_i$. * **Page 642.** *Remplacer $i$ par $i-1$ dans la relation de récurrence.* Il faut remplacer la relation de récurrence $M_i = 1+ \max\{M_k\,:\, k \in \llbracket 0, i \rrbracket, t_k < t_i\}$ par $M_i = 1+ \max\{M_k\,:\, k \in \llbracket 0, i-1 \rrbracket, t_k < t_i\}$. ### 109. Turing-calculable implique $\mu$-récursive * **Page 687.** *Remplacer $g_i$ par $d_i$.* Dans la représentation de la configuration dans l’énoncé, il faut remplacer $g_i$ par $d_i$. * **Page 689.** *Remplacer « utilise » par « n’utilise ».* À la question **e)**, il manque un « n’ » dans la phrase « La fonction somme est primitive récursive car elle n’utilise qu’une minimisation bornée [...] ». ### 111. $\mu$-récursive implique $\lambda$-définissable * **Page 698.** *Remplacer $\sim_\beta$ par $=$ à la question **d)**.* À la question **d)**, pour la définition du schéma de minimisation non bornée, il faut écrire $\varphi(\vec n) = \mu_k (\chi(\vec n, k) = 0)$ et non pas $\varphi(\vec n) \sim_\beta \mu_k (\chi(\vec n, k) = 0)$. En effet, ici on parle de fonction $\mu$-récursive et non de $\lambda$-calcul. * **Page 698.** *Enlever une parenthèse fermante.* À la question **d)**, pour la définition de $H$, il y a une parenthèse fermante de trop. ### 122. Algorithme de Cocke-Younger-Kasami * **Page 781.** *Remplacer $S \in E_{1,n}$ par $w \in E_{1,n}$.* Faute de frappe dans l’algorithme 31 à la ligne 12, il faut remplacer $S$ par $w$. ### 124. Théorème de Cook-Levin * **Page 795.** *Remplacer « $\nu(x_{i,ja}) = \top$ » par « $\nu(x_{i,j,a}) = \top$ ».* A la fin de la correction de la question **b)** (*v*), dans la preuve de « $w\in L$ implique $\varphi_w$ est satisfiable », il manque une virgule dans la variable propositionnelle $x_{i,j,a}$. ### 125. Transformation de Tseitin * **Page 801.** *Remplacer « $(\neg x_{n-2} \vee x_{n-1} \vee x_n)$ » par « $(\neg y_{n-2} \vee x_{n-1} \vee x_n)$ ».* Dans le quatrième commentaire, lors de la transformation d’une clause à $n$ littéraux en conjonction de clauses à trois littéraux, la dernière clause est $(\neg y_{n-2} \vee x_{n-1} \vee x_n)$. En effet, le premier littéral de cette clause est la négation de $y_{n-2}$ qui est une variable fraîche et non $x_{n-2}$ qui est un littéral de la formule de départ. ### 131. Équivalence entre deux sémantiques * **Page 832.** *Remplacer « récurrence forte » par « récurrence classique ».* À la question **b)** (*i*), on peut enlever le « forte » de « récurrence forte ». En effet, on n’a besoin de l’hypothèse de récurrence qu’au rang $k-1$ et non à tous les rangs précédents.