\documentclass[a4paper, 11pt]{article}

% Math symbols, notation, etc.
% Apparently, must be loaded earlier than mathspec?
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{amsthm}
\usepackage{tikz-cd}
\usepackage{algorithm,caption}
\usepackage{algpseudocode}

% Locale/encoding with XeTeX: UTF-8 by default, use fontspec
\usepackage{unicode-math}
\usepackage[frenchb]{babel}
\usepackage{csquotes} % guillemets

% TeX Gyre Pagella = URW Palladio (free Palatino) extended
\setmainfont[Mapping=tex-text]{TeX Gyre Pagella}
\setmathfont{Asana Math}

% Other
\usepackage{fullpage}
%\usepackage{enumerate}
%\usepackage{graphicx}

% References
\usepackage{nameref}
\usepackage[colorlinks]{hyperref}

% Macros de Jill-Jênn
\def\A{{\cal{A}}}
\def\F{\mathbb{F}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\U{\mathbb{U}}
\def\K{\mathbb{K}}
\def\P{\mathbb{P}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\L{{\cal{L}}}
\def\S{{\cal{S}}}
\def\V{{\cal{V}}}
\def\T{{\cal{T}}}
\def\O{{\cal{O}}}
\def\Fs{{\cal{F}}}
\def\Ps{{\cal{P}}}
\def\Cf{{\cal{C}}}
\def\M{\mathcal{M}}
\def\MnK{{\cal M}_n(\K)}
\def\Tr{\textnormal{Tr}}
\def\Sp{\textnormal{Sp}}
\def\Re{\textnormal{Re}}
\def\Vect{\textnormal{Vect}}
\def\car{\textnormal{car}}
\def\pgcd{\textnormal{pgcd}}
\def\ppcm{\textnormal{ppcm}}
\def\Sigmap{\mathfrak{S}}
\def\prog{\texttt{prog}}

% Ajout personnel
\def\E{\mathbb{E}}
\def\Var{\textnormal{Var}}
\def\Ker{\textnormal{Ker}}
\def\Indic{\mathbb{1}}
\def\GL{\mathrm{GL}}
\def\SL{\mathrm{SL}}
\def\PSL{\mathrm{PSL}}
\def\Aut{\mathrm{Aut}}
\def\Vol{\mathrm{Vol}}
\def\Diag{\mathrm{Diag}}

\newtheorem*{definition}{Définition}
\newtheorem*{example}{Exemple}
\newtheorem*{proposition}{Proposition}
\newtheorem*{theorem}{Théorème}
\newtheorem*{application}{Application}
\newtheorem*{algo}{Algorithme}
\newtheorem*{lemma}{Lemme}
\newtheorem*{remark}{Remarque}
\newtheorem*{corollary}{Corollaire}

\algtext*{EndProcedure}
\algtext*{EndWhile}
\algtext*{EndFor}
\algtext*{EndIf}
\algrenewcommand\algorithmicprocedure{\textbf{procédure}}
\algrenewcommand\algorithmicif{\textbf{si}}
\algrenewcommand\algorithmicthen{\textbf{alors}}
\algrenewcommand\algorithmicelse{\textbf{sinon}}
\algrenewcommand\algorithmicfor{\textbf{pour}}
\algrenewcommand\algorithmicwhile{\textbf{tant que}}
\algrenewcommand\algorithmicdo{\textbf{faire}}
\algrenewcommand\algorithmicreturn{\textbf{renvoyer}}


\begin{document}

\title{Mes développements pour l'agrég de maths\\
  (leçons d'algèbre et analyse, option informatique)}
\author{Nguyễn Lê Thành Dũng (ENS Ulm, département informatique, promo 2012)}
\date{Préparation à l'agrégation de l'ENS Paris-Saclay, 2016--2017}
\maketitle

Ce document recense les développements que j'ai travaillés et rédigés pendant mon
année de prépa agrég, en vue de l'oral de leçon de mathématiques. (En option D,
il y a un unique oral \enquote{Mathématiques pour l'informatique} où peuvent
tomber à la fois des leçons d'algèbre et des leçons d'analyse.)\\

Parmi ceux-ci, un certain nombre sont originaux, voire exotiques. On ne les
trouvera pas dans les livres classiques de l'agrég, mais j'ai tout de même
essayé d'indiquer des références livresques quand c'était possible.
\begin{itemize}
\item \nameref{dual}
\item \nameref{zigzag} (tiré des développements de Paul Melotti)
\item \nameref{gram}
\item \nameref{s6}
\item \nameref{monotone}
\item \nameref{theta} (inabouti, il reste une arnaque à régler, qui pourra
  constituer un exercice pour la lectrice ; envoyez vos suggestions de preuve à
  \texttt{nltd@nguyentito.eu})
\end{itemize}
D'autres sont des développements \enquote{classiques} mais pour lesquels je
propose des preuves améliorées.
\begin{itemize}
\item \nameref{conv-ortho} : au niveau agrég, on est censé avoir entendu parler
  de décomposition en valeurs singulières
\item \nameref{tauber} (saviez-vous qu'il était dû à Littlewood sans Hardy ?) :
  on découpe moins d'$\varepsilon$ en invoquant les sommes de Riemann
\item \nameref{stable} (ou \enquote{théorème de Liapounov} ; saviez-vous qu'il
  était dû à Perron ?) : preuve plus
  directe et concise que celle proposée par le Rouvière
\end{itemize}
Le reste est relativement classique.
On trouvera également une section \nameref{exclu}.\\

On pourra consulter l'excellent \emph{Histoires hédonistes de groupes et de
  géométries, tome premier} de Caldero et Germoni pour y trouver d'autres
développements pour lesquels j'ai une grande affection, mais que je n'ai pas
pris la peine de taper, notamment :
\begin{itemize}
\item Revêtement universel $\mathrm{SU}(2) \to \mathrm{SO}(3)$ via les
  quaternions
\item Réciprocité quadratique par double comptage d'une conique sur $\F_q^p$
  (trop beau !)
\item Existence de la réduction de Frobenius (utilisant l'orthogonalité duale)
\end{itemize}
Le développement \nameref{non-iso} est également issu de H2G2 tome 1, mais la
preuve qui y est donnée est légèrement fausse, c'est pourquoi une version
corrigée est rédigée ici. Ce développement gagnerait d'ailleurs à être plus
connu, étant donné qu'il se recase dans de nombreuses leçons d'algèbre, faisant
intervenir à la fois la réduction des endomorphismes nilpotents, les groupes
finis, et les corps finis.

\newpage

\tableofcontents

\newpage

\section{Algèbre/géométrie et analyse}

\subsection{Dualité lagrangienne et extrema liés en optimisation convexe}
\label{dual}

On montre ici un théorème fondamental en \emph{recherche opérationnelle},
variante du théorème des extrema liés où :
\begin{itemize}
\item on a des multiplicateurs de Lagrange \emph{positifs} correspondant à des
  contraintes d'\emph{inégalité} (on ne pourra donc pas invoquer les
  sous-variétés) ;
\item les conditions nécessaires du premier ordre sont également
  \emph{suffisantes} grâce à la convexité.
\end{itemize}
Il est recommandé d'avoir quelques connaissances en optimisation
(notamment, l'application à la dualité en programmation linéaire et
programmation semi-définie) si on veut présenter ce développement.

Soient $f,g_1,\ldots,g_k : \R^n \to \R$ des fonctions \emph{convexes}.
On considère le problème de minimisation
\[ p = \inf_{x \in F} f(x) \qquad F = \left\{ x \in \R^n \mid
  g_i(x) \leq 0,\; i = 1,\ldots,k \right\} \]
(Vocabulaire : $f$ est la \emph{fonction objectif}, les $g_i$ sont des
\emph{contraintes}, $F$ est l'ensemble des \emph{solutions réalisables}).

On appelle \emph{condition de Slater} l'existence d'un $x_0 \in \R^n$
\emph{strictement réalisable}, c'est-à-dire tel que $g_i(x_0) < 0$ pour tout
$i$.

\begin{theorem}[Karush--Kuhn--Tucker]
  On suppose ici que $f, g_1, \ldots, g_k$ sont $\Cf^1$, et que la condition de
  Slater est vérifiée. Alors pour tout $x \in \F$, $f(x) = p$ si et seulement
  s'il existe $\mu_1, \ldots, \mu_k \geq 0$ tels que
  \[ \nabla f(x) + \sum_{i=0}^k \mu_i \nabla g_i(x) = 0 \quad \text{et} \quad
    \mu_i g_i(x) = 0\; \forall i
  \]
\end{theorem}

Afin de montrer cela, introduisons le \emph{lagrangien} $\L : \R^n \times
\R_+^k \to \R$ et le problème dual associé :
\[ \L(x, \mu) = f(x) + \sum_{i=1}^k \mu_i g_i(x) \qquad
  d = \sup_{\mu \in \R_+^k} \inf_{x \in \R^n} \L(x,\mu) \]

\begin{remark} $\displaystyle p = \inf_{x \in \R^n} \sup_{\mu \in \R_+^k}
  \L(x,\mu)$.
\end{remark}
\begin{proof}
  En effet, si $x \not\in F$, alors il existe $i$ tel que $g_i(x) > 0$.
  $\L(x,(0, \ldots, \mu_i, \ldots, 0)) \to +\infty$ quand $\mu_i \to
  +\infty$. Donc $\sup_{\mu \in \R_+^k} \L(x,\mu) = +\infty$ dès que $x \not\in
  F$, et si $x \in F$, le sup est atteint pour $\mu = 0$ soit $\L(x,\mu) =
  f(x)$.
\end{proof}
\begin{corollary}[Dualité faible]
  $d \leq p$.
\end{corollary}
\begin{proof}
  Il s'agit simplement de voir que pour tout $x, \mu$,
  \[ \inf_{y} \L(y, \mu) \leq \L(x,\mu) \leq \sup_{\nu} \L(x,\nu) \]
  puis de prendre le sup sur $\mu$ à gauche et l'inf sur $x$ à droite.
\end{proof}

\begin{theorem}[Dualité forte]
  On suppose seulement que $f, g_1, \ldots, g_k$, et que la condition de Slater
  est satisfaite. Alors $p = d$ et le supremum dual est atteint.
\end{theorem}
\begin{proof}
  Si $p = -\infty$, la dualité faible permet de conclure directement que $d =
  -\infty$.
  
  Sinon, il suffit de montrer $p \leq d$, donc de trouver $\mu_1, \ldots, \mu_k
  \geq 0$ tels que pour tout $x \in \R^n$, $\L(x,\mu) \geq p$.

  Posons $A, B \subset \R^{k+1}$ définis par
  \[ A = \left\{ (y_1, \ldots, y_k, z) \mid \exists x \in \R^n\,/\,
    y_i \geq g_i(x),\; z \geq f(x) \right\}
    \qquad B = \left\{ (y_1, \ldots, y_k, z) \mid y_i < 0,\;z < p \right\}\]

  Si $(y_1,\ldots,y_k,z) \in A \cap B$, alors il existe $x$ tel que $g_i(x) \leq
  y_i < 0$ pour tout $x$, donc $x \in F$, et $f(x) \leq z < p$. C'est impossible
  par définition de $p$. Ainsi, $A$ et $B$ sont disjoints, avec $B$ ouvert.
  
  Donc il existe un hyperplan séparateur\footnote{Il faut faire attention aux
    hypothèses topologiques de la version de Hahn-Banach qu'on utilise ici.
    Sinon, on pourrait invoquer le théorème de séparation des convexes en
    dimension finie de Minkowski, qui demande seulement que les deux convexes
    soient disjoints.} i.e. une forme linéaire $\varphi$ telle que $\varphi(a) \geq
  \varphi(b)$ pour tout $a \in A$ et $b \in B$. En coordonnées, $\varphi$ s'écrit
  \[ \varphi(y_1, \ldots, y_k, z) = \mu_1 y_1 + \ldots + \mu_k y_k + \nu z
    \quad \text{avec} \quad (\mu_1, \ldots, \mu_k, \nu) \neq (0, \ldots, 0)
  \]
  
  Pour tout $x$, en prenant $a = (g_1(x), \ldots, g_k(x), f(x))$, et $b = (0,
  \ldots, 0, p) \in \overline{B}$, on a
  \[ \sum_{i=1}^k \mu_i g_i(x) + \nu f(x) \geq \nu p \]
  On montre que $\nu > 0$ par disjonction de cas :
  \begin{itemize}
  \item si $\mu = (\mu_1, \ldots, \mu_k) \neq 0$, alors l'inégalité ci-dessus,
    appliquée à $x_0$ strictement réalisable, nous donne $\nu f(x_0) > \nu p$ ;
  \item sinon, $\varphi(g_1(x_0), \ldots, g_k(x_0), f(x_0)) > \varphi(0, \ldots,
    0, p-1)$ nous donne $\nu f(x_0) > \nu(p-1)$.
  \end{itemize}
  En divisant par $\nu$, on a finalement : $\L(x, \mu_1/\nu, \ldots, \mu_k/\nu)
  \geq p$.
\end{proof}

Supposons maintenant que $f, g_1, \ldots, g_k$ sont $\Cf^1$. 
\begin{proof}[Les conditions KKT sont nécessaires]
  Fixons $\mu_1, \ldots, \mu_k$ maximisant le dual : $\inf_x \L(x, \mu) = d =
  p$. Soit $x$ tel que $f(x) = p$. Alors
  \[ f(x) = p = d \leq \L(x, \mu) = f(x) + \sum_{i=0}^k \mu_i g_i(x) \] Comme
  $g_i(x) \leq 0$ et $\mu_i \geq 0$ pour tout $i$, ce qui entraîne l'inégalité
  réciproque, on a en fait $\mu_i g_i(x) = 0$ pour tout $i$. Ainsi, en $x$,
  $\L(-, \mu)$ atteint la valeur $d$ qui est son minimum, son gradient s'annule
  donc. Ceci donne immédiatement la condition au premier ordre.
\end{proof}

\begin{proof}[Les conditions KKT sont suffisantes]
Soient $x \in F$ et $\mu \in \R_+^k$ vérifiant ces conditions. Alors, comme
$\L(-,\mu)$ est convexe, ses points stationnaires sont ses minima globaux, donc
elle atteint son minimum en $x$. Comme $\mu_i g_i(x) = 0$ pour tout $i$, le
lagrangien vaut $f(x)$ :
\[ f(x) = \L(x,\mu) = \inf_{x'} \L(x',\mu) \leq \sup_{\mu'} \inf_{x'}
  \L(x',\mu') = p
\]
donc $x$ minimise bien $f$ sur $F$.
\end{proof}

\paragraph{Ci-dessous, une tentative de prouver autrement la dualité forte…}
comme corollaire du \emph{théorème du minimax de Sion} ; ce théorème pourrait
d'ailleurs faire l'objet d'un développement fort intéressant. L'intérêt étant de
voir un lien entre condition de Slater et compacité. On suppose donc qu'il
existe $x_0$ strictement réalisable.

On a besoin comme hypothèse supplémentaire que $d > -\infty$ (comment s'en
passer ?). On rappelle qu'un sup de fonctions semi-continues inférieurement
l'est, et qu'une telle fonction admet un minimum sur tout compact.

Fixons $R > 0$ et posons $\bar{B}_R = \bar{B}(x_0,R)$, qui est convexe compact.
Soit
\[ p_R = \min_{x \in \bar{B}_R} \sup_{\mu \in \R_+^k} \L(x,\mu)
       = \sup_{\mu \in \R_+^k} \min_{x \in \bar{B}_R} \L(x,\mu) \]
l'égalité résultant du théorème du minimax.

La première expression donne $p_R = \min_{x \in F \cap \bar{B}_R} f(x)$
(l'ensemble étant non vide puisque $x_0$ y est).

D'autre part, par la seconde expression, $p_R \geq d$. Comme $x_0$ est
strictement réalisable, quand $\|\mu\| \to +\infty$ en restant dans $\R_+^k$,
$\L(x_0, \mu) \to +\infty$ . Il existe donc un compact $K \subset \R_+^k$ tel
que $\forall \mu \in \R_+^k \setminus K,\; \L(x_0, \mu) < d \leq p_R$ (et $K$
est indépendant de $R$, c'est important !). D'où
\[ p_R = \max_{\mu \in K} \min_{x \in \bar{B}_R} \L(x,\mu) =
  \min_{x \in \bar{B}_R} \max_{\mu \in K} \L(x,\mu) \]
Quand $R \to +\infty$, on trouve
\[ \inf_{x \in F} f(x) = \inf_{x \in \R^n} \max_{\mu \in K} \L(x,\mu) 
  = \max_{\mu \in K} \inf_{x \in \R^n} \L(x,\mu)  \]
où, cette fois-ci, on a utilisé la compacité de $K$ pour appliquer le théorème
du minimax à $-\L$ ! Tout ceci fonctionnant encore avec n'importe quel convexe
compact $K' \supseteq K$, en épuisant $\R_+^k$ avec des compacts, on a
finalement $p = d$, et de plus, on sait qu'une solution duale optimale $\mu^*$
existe.

Question ouverte : peut-on montrer $d > -\infty$ sans utiliser un argument
d'hyperplan séparateur ?


\newpage

\subsection{Enveloppe convexe du groupe orthogonal}
\label{conv-ortho}

Je propose ici une démonstration bien plus expéditive que celle qu'on trouve
par-ci par-là dans des PDF sur Internet, relativement autosuffisante avec le
programme de math spé (pas besoin de théorèmes un peu compliqués à démontrer
comme Hahn-Banach géométrique, donc). Mais du coup c'est peut-être un peu court…

On considère $\R^n$ muni de sa norme euclidienne canonique $\|\cdot\|$, $O(n)$
le groupe orthogonal.

Le seul prérequis sera le suivant :

\begin{theorem}[Décomposition en valeurs singulières]
  Soit $M \in \M_n(\R)$, alors il existe $U, V \in O(n)$ et $D$ diagonale à
  coefficients positifs tels que $M = UDV$.
\end{theorem}
\begin{proof}
  On s'est placé dans le cas particulier des matrices carrées, donc il suffit
  d'enchaîner décomposition polaire et théorème spectral.
\end{proof}

Énonçons également un petit lemme qu'il sera bon d'illustrer avec un
\textbf{dessin} dans $\R^2$ :
\begin{lemma}
  $\mathrm{Conv}(\{-1,1\}^n) = [-1,1]^n$.
\end{lemma}
\begin{proof}
  On aimerait parachuter une formule explicite, mais c'est sans doute pénible,
  vu que ça devra impérativement faire intervenir tous les $2^n$ sommets de
  l'hypercube… Sinon, il est clair que $\mathrm{Conv}({-1,1}) = [-1,1]$, d'où
  l'on déduit que
  \[ \bigcup_{x \in [-1,1]}
  \mathrm{Conv}(\{x\} \times \{-1,1\}^{n-1}) \subseteq
  \mathrm{Conv}(\{-1,1\}^n) \]
  puis on conclut par récurrence.
\end{proof}


Maintenant, soit $||| \cdot |||$ la norme subordonnée sur $\M_n(\R)$ et $B$ la
boule unité \emph{fermée} de $\M_n(\R)$ pour cette norme.

\begin{theorem}
  $B$ est l'enveloppe convexe de $O(n)$. 
\end{theorem}

\begin{proof}
  Tout d'abord, il est clair que les matrices orthogonales, étant des
  isométries, sont de norme 1, donc $O(n) \subset B$. $B$ étant convexe, il
  contient également l'enveloppe convexe de $O(n)$.

  Soit $M \in B$. Écrivons sa SVD : $M = UDV$ où $U, V \in O(n)$ et $D =
  \Diag(d_1, \ldots, d_n)$. Comme $|||D||| \leq 1$, on a $|d_i| \leq 1$ pour
  tout $i$. Le lemme précédent nous permet donc d'écrire $D$ comme barycentre de
  la forme $\Diag(\pm 1, \ldots, \pm 1)$. Ces matrices sont des symétries
  orthogonales, elles sont dans $O(n)$. En multipliant par $U$ à gauche et $V$ à
  droite, on a $M \in \mathrm{Conv}(O(n))$.
\end{proof}

Le théorème est donc en fait simplement la conséquence du fait que la plus
grande valeur singulière est égale à la norme subordonnée.

\begin{theorem}
  $O(n)$ est l'ensemble des \emph{points extrêmes} de $B$, c'est-à-dire des
  points qui ne peuvent pas s'écrire comme barycentres d'autres points de $B$.
\end{theorem}

Ce résultat découle du précédent via le théorème de Krein-Milman\footnote{En
  réalité, on n'a besoin que de la version en dimension finie, plus simple, et
  démontrée par Minkowski. Cette version nécessite quand même l'existence des
  hyperplans d'appui, donc utilise le théorème de séparation des convexes (dont
  la généralisation en dimension infinie est le théorème de Hahn-Banach).}, mais
celui-ci est difficile à montrer.

\begin{proof}[Preuve élémentaire] Vu le résultat précédent, tout point extrême
  est forcément une matrice orthogonale. Réciproquement, soit $U \in O(n)$.

Posons $\varphi : M \mapsto \Tr(U^{-1}M)$, $\varphi \in \M_n(\R)^*$. Pour
tout $M \in B$, on a (puisque $\| U^{-1}M e_i \| \leq 1$)
\[ \varphi(M) = \Tr(U^{-1}M) = \sum_{i=1}^n \langle U^{-1}M e_i \mid e_i \rangle
  \leq \sum_{i=1}^n \| U^{-1}M e_i \| \cdot \| e_i \| \leq n \]

et on a égalité si et seulement si, pour tout $i$,
\begin{itemize}
\item $\| U^{-1}M e_i \| = 1$
\item (Cauchy-Schwarz) $U^{-1}M e_i$ et $e_i$ sont positivement liés
\end{itemize}
soit $U^{-1}M e_i = e_i$ pour tout $i$. Ce qui est équivalent à $U^{-1}M = I$ ou
encore à $M = U$.

Ainsi, d'une part $\varphi(U) = n$, d'autre part, pour tout barycentre $G =
\sum_{i=1}^k \alpha_i M_i$ avec $M_i \in B \setminus \{U\}$, on a $\varphi(M_i) <
n$ pour tout $i$ donc $\varphi(G) < n$. Forcément $U \neq G$ : $U$ est un point
extrême.
\end{proof}

Conséquence de la preuve : pour chaque point extrême, il existe un hyperplan
d'appui intersectant $B$ uniquement en ce point. Ce n'est pas vrai pour tout
convexe (faire un dessin).

% \paragraph{Enveloppe convexe de $O(n)$} Nous voulons montrer que
% $\mathrm{Conv}(O(n)) = B$, sachant qu'une inclusion a déjà été montrée.
% À ce stade, nous pourrions conclure directement en invoquant le théorème de
% Krein-Milman, mais il est difficile à démontrer. Procédons autrement, avec les
% résultats suivants :

% \begin{theorem}[Carathéodory]
%   Soit $X$ une partie d'un espace affine de dimension $n$. tout point
%   $\mathrm{Conv}(X)$ s'écrit comme barycentre d'au plus $n+1$ points de $X$.
% \end{theorem}
% \begin{corollary}
%   Si $K$ est une partie compacte d'un espace affine de dimension finie,
%   $\mathrm{Conv}(K)$ est compacte.
% \end{corollary}

% Ce qui nous permet d'affirmer que $\mathrm{Conv}(O(n))$ est compact (comme quoi,
% ce n'est pas si trivial que ça).

% \begin{theorem}
%   Dans un espace affine de dimension finie, si $K$ est convexe fermé et $x
%   \not\in K$, alors il existe un hyperplan séparant strictement $x$ et $K$.
% \end{theorem}
% \begin{proof}
%   On peut appliquer directement le théorème de Hahn-Banach géométrique ($\{x\}$
%   étant convexe compact), ou bien utiliser la projection sur un convexe fermé
%   dans un espace de Hilbert.
% \end{proof}

% Supposons par l'absurde qu'il existe $M \in B \setminus \mathrm{Conv}(O(n))$.
% Alors il existe un hyperplan séparateur, fourni par une forme linéaire $\phi$
% telle que pour tout $U \in \mathrm{Conv}(O(n))$, $\phi(U) < \phi(M)$. Comme
% $\Tr(- \times -)$ est une forme bilinéaire non dégénérée, en fait,
% \[ \exists A \in \M_n(\R) \,/\, \forall U \in O(n),\, \Tr(AU) < Tr(AM) \]


\newpage



\subsection{Fonction tangente et permutations zigzag}
\label{zigzag}

Cf. Richard P. Stanley, \emph{A Survey of Alternating Permutations}. Le
développement lui-même est tiré du PDF de Paul Melotti.

Le terme \enquote{permutation alternante} pouvant induire en confusion avec le
groupe alterné, nous parlerons ici de \emph{permutation zigzag}. Plus
précisément, on dira que $\sigma \in \Sigmap_n$ est :
\begin{itemize}
\item \emph{haut-bas} si $\sigma(1) > \sigma(2)$, $\sigma(2) < \sigma(3)$,
  \ldots
\item \emph{bas-haut} si $\sigma(1) < \sigma(2)$, $\sigma(2) > \sigma(3)$,
  \ldots
\item \emph{zigzag} si elle est haut-bas ou bas-haut, ou de façon équivalente si
  $(\sigma(i) - \sigma(i-1))(\sigma(i+1) - \sigma(i)) < 0$ pour tout $i$.
\end{itemize}
(Faire un dessin pour illustrer.) On notera leurs ensembles respectifs $Z_n^+$,
$Z_n^-$ et $Z_n = Z_n^+ \cup Z_n^-$, et on prendra comme convention, pour $n \in
\{0,1\}$, $Z_n^+ = Z_n^- = \Sigmap_n$ qui est un singleton.

Notre but est de montrer le résultat inattendu suivant :

\begin{theorem}[Désiré André]
  La série génératrice exponentielle des permutations haut-bas est\\
  $G(z) = \tan(z)+\sec(z)$.
\end{theorem}

En fait, au lieu d'utiliser la série génératrice pour dénombrer nos objets comme
d'habitude, ici le sens utile est plutôt l'obtention d'un algorithme pour
obtenir les coefficients des séries entières des fonctions tangente et sécante.
Il faudrait pour cela dénombrer d'une autre façon les permutations haut-bas, ce
qu'on ne fera pas ici.

\begin{proposition}
  Pour tout $n \in \N$, $Z_n^+ \simeq Z_n^-$, et si $n \geq 2$, alors $Z_n^+
  \cap Z_n^- = \emptyset$.
\end{proposition}
\begin{proof}
  Pour $n \leq 1$, on a égalité. Sinon, la bijection entre $Z_n^+$ et $Z_n^-$
  est réalisée par $\sigma \mapsto (i \mapsto \sigma(n-i+1))$ (visuellement,
  c'est une réflexion par rapport à un axe horizontal).
  
  Dès qu'il existe deux éléments dans l'ensemble, on ne peut pas avoir à la fois
  $\sigma(1) > \sigma(2)$ et $\sigma(1) < \sigma(2)$.
\end{proof}

\begin{proposition}
  Pour $n \in \N$, $\displaystyle Z_{n+1} \simeq \bigsqcup_{G \sqcup D =
    \llbracket 1,n \rrbracket} Z_{|G|}^- \times Z_{|D|}^+$.
\end{proposition}
\begin{proof}
  Soit $\sigma \in Z_{n+1}$ et soit $m = \sigma^{-1}(n+1)$. Posons $G =
  \sigma(\llbracket 1,m-1 \rrbracket) = \{g_1, \ldots, g_p\}$ et $D =
  \sigma(\llbracket m+1,n-1 \rrbracket) = \{d_1, \ldots, d_q\}$ ($p = m-1$, $q =
  n-m+1$).

  On peut maintenant définir $\sigma_g \in Z_p$ par $\sigma(m-i) =
  g_{\sigma_g(i)}$, et $\sigma(m+i) = d_{\sigma_d(i)}$. Il faut voir ce qui se
  passe sur un dessin : à gauche de $m$, on lit $\sigma_g$ de droite à gauche,
  et à droite de $m$, on lit $\sigma_d$ de gauche à droite.

  Comme la suite $\sigma(m), \sigma(m-1), \sigma(m-2)$ est zigzag et $\sigma(m)$
  est maximal, $\sigma_g \in Z_p^-$ ; de même, $\sigma_d \in Z_q^+$. Si $p \leq
  1$ ou $q \leq 1$, on peut se convaincre que ça marche toujours avec la
  définition choisie de $Z_p^-$ et $Z_q^+$.

  On a ainsi défini une application $Z_{n+1} \longrightarrow \bigsqcup_{G \sqcup
    D = \llbracket 1,n \rrbracket} Z_{|G|}^- \times Z_{|D|}^+$, dont on peut se
  convaincre qu'elle est bijective.
\end{proof}

Nous pouvons maintenant passer au dénombrement. Posons $a_n = |Z_n^+| = |Z_n^-|$
et $b_n = a_n/n!$ ; la série génératrice exponentielle s'écrit alors $G(z) =
\sum_{n \in \N} b_n z^n$. Comme $0 \leq b_n \leq |\Sigmap_n| / n! = 1$, $G$ est
de rayon de convergence au moins 1.

La relation de récurrence se réécrit, avec les cardinaux,
\[ |Z_{n+1}| = \sum_{G \sqcup D = \llbracket 1,n \rrbracket} a_{|G|} \cdot
  a_{|D|} = \sum_{k = 1}^n \binom{n}{p} a_k a_{n-k}
  = \sum_{k = 1}^n n! \frac{a_k}{k!} \frac{a_{n-k}}{k!} \quad \text{d'où} \quad
  \frac{|Z_{n+1}|}{n!} = \sum_{k = 1}^n b_k b_{n-k}
\]

On voit donc apparaître une convolution, ce qui nous donne envie de reformuler
l'identité avec des séries entières. Mais attention au terme $n = 0$ ! Pour $n
\geq 1$, comme $Z_{n+1}^+ \cap Z_{n+1}^- = \emptyset$, on a $|Z_{n+1}| =
2a_{n+1}$ soit $|Z_{n+1}|/n! = 2(n+1)b_{n+1}$. Pour $n = 0$, $|Z_1|/0! = 1 =
2 \times 1 \times b_1 - 1$. Ainsi :
\[ \sum_{n \in \N} \frac{|Z_{n+1}|}{n!}z^n = \sum_{n \in \N} 2(n+1)b_{n+1}z^n - 1
  = 2G'(z) - 1
\]
le rayon de convergence étant au moins 1 pour la même raison que précédemment.

À droite de l'égalité, la convolution devient un produit de Cauchy en prenant la
série génératrice ; finalement, on trouve que $G$ est une solution de l'équation
différentielle
\[ 2y' = y^2 + 1 \qquad \text{avec condition initiale} \quad y(0) = 1 \]

Par Cauchy-Lipschitz, il existe une unique solution maximale à ce problème. Il
suffit donc d'en exhiber une autre définie sur $]-1,1[$ pour déterminer $G$ sur
cet intervalle. Parachutons donc $f(x) = \tan(x) + \sec(x)$ ; il ne reste qu'à
calculer pour conclure.


\begin{corollary}
  $a_n = \sec^{(n)}(0)$ si $n$ est pair, $a_n = \tan^{(n)}(0)$ sinon.
\end{corollary}
\begin{proof}
  La fonction tangente est impaire tandis que la sécante est paire.
\end{proof}

\newpage

\subsection{Lemme de Morse}

Béni soit ce développement, car il permet de remplir la leçon
\enquote{Applications des formules de Taylor} en faisant autre chose qu'un
développement asymptotique. Référence : exercices 66 et 114 dans Rouvière,
\emph{Petit guide de calcul différentiel}.

On note $S_n(\R)$ l'espace des matrices symétriques réelles de taille $n$.

\begin{proposition}
  Soit $A \in S_n(\R) \cap \GL_n(\R)$. Il existe un voisinage $V \ni A$ et $P
  \in \Cf^\infty(V, \GL_n(\R))$ tel que $M = P(M)^T A \, P(M)$ pour
  tout $M \in V$.
\end{proposition}

\begin{proof}
  Considérons $(A^{-1})S_n(\R) = \{A^{-1}M \mid M \in S_n(\R)\}$. C'est un
  $\R$-espace vectoriel de dimension finie $n(n+1)/2$. $U = \GL_n(\R) \cap
  (A^{-1})S_n(\R)$ en est une partie ouverte.
  
  On considère l'application $\psi : P \in U \mapsto P^T A \, P \in S_n(\R)$.
  $\psi$ est une application $\Cf^\infty$ (car polynomiale) entre deux espaces
  de même dimension. Il s'agit de construire un inverse (à droite) de $\psi$ au
  voisinage de $A$ ; on voudrait donc appliquer le théorème d'inversion locale.
  Il suffit pour cela de vérifier que la différentielle est inversible.

  Calculons-la : $D\psi(I)(H) = H^TA + AH$. Cette formule montre que si $H \in
  \Ker(D\psi(I))$, $AH$ est antisymétrique ; or $AH$ est symétrique (car $H \in
  (A^{-1})S_n(\R)$, et l'on comprend pourquoi s'être restreint à cet espace !)
  donc $AH = 0$ soit $H = 0$ ($A$ inversible). $D\psi(I)$ est donc inversible.
\end{proof}

\begin{corollary}[Réduction $\Cf^\infty$ des formes quadratiques]
  Soit $(p,q)$ la signature de $A$ en tant que forme quadratique non dégénérée.
  Il existe $Q \in \Cf^\infty(V, \GL_n(\R))$ telle que pour tout $M \in V$,
  \[M = Q(M)^T \Diag(I_p, -I_q)\, Q(M). \]
\end{corollary}
\begin{proof}
  Il suffit de combiner le théorème précédent avec la loi d'inertie de
  Sylvester.
\end{proof}

\begin{theorem}[\enquote{Lemme} de Morse]
  Soit $f \in \Cf^3(U, \R^n)$ ($U \subseteq \R^n$ ouvert) telle que $f(0) = 0$,
  $Df(0) = 0$, et $D^2f(0)$ soit non dégénérée de signature $(p,n-p)$. Alors il
  existe un changement de coordonnées local $\Cf^1$ $x \mapsto u$ tel que
  \[ f(x) = u_1^2 + \ldots + u_p^2 - u_{p+1}^2 - \ldots - u_n^2 \]
\end{theorem}
\begin{proof}
  On part de la formule de Taylor avec reste intégral\footnote{LE RESTE INTÉGRAL
    !}. En écriture matricielle,
  \[ f(x) = \int_0^1 (1-t)x^T H_f(tx) x\, dt = x^TA(x)x
    \quad \text{où} \quad A(x) = \int_0^1 (1-t) H_f(tx) \,dt  \]
  $H_f(x)$ étant la hessienne de $f$ en $x$ (formule valable pour $x$ dans un
  voisinage convexe de 0). $f$ étant $\Cf^3$, par dérivation sous le signe
  somme, $A$ est $\Cf^1$.

  $A(0) = H_f(0)$ et cette dernière est inversible par hypothèse. Le théorème
  démontré précédemment nous donne un voisinage $V$ de $A(0)$ dans $S_n(\R)$ et
  $Q \in \Cf^\infty(V, \GL_n(\R))$ tels que si $A(x) \in V$, $A(x) = Q(A(x))^T
  \Diag(I_p, -I_{n-p})\, Q(A(x))$. Et comme $A$ est continue à valeurs dans
  $S_n(\R)$, $U = A^{-1}(V)$ est un voisinage de $0$.

  Sur ce voisinage, on a donc :
  \[ f(x) = x^T \cdot Q(A(x))^T\Diag(I_p, -I_{n-p})\,Q(A(x)) \cdot x
    = u^T \Diag(I_p, -I_{n-p})\, u \quad \text{avec} \quad
    u = Q(A(x)) \cdot x
  \]
  et c'est bien l'écriture qu'on voulait avoir. L'application $x \in U \mapsto
  u$ est-elle bien un difféomorphisme ? Elle est $\Cf^1$, et sa différentielle
  en 0 vaut $h \mapsto Q(A(0)) \cdot h$, qui est inversible. Quitte à
  restreindre plus le voisinage de 0, on peut donc avoir un
  $\Cf^1$-difféomorphisme par inversion locale.
\end{proof}

\newpage

\subsection{Méthode de Kaczmarz}

Référence : à trouver.

Soient $A \in \M_{m,n}(\R)$, et $b \in \R^m$. On veut résoudre $Ax = b$ ($x \in
\R^n$) itérativement. Pour cela, on pose $(l_1, \ldots, l_m)$ les lignes de $A$,
et $p_i$ le projecteur orthogonal sur l'hyperplan affine $H_i$ d'équation $l_ix
= b_i$ ($i \in \{1, \ldots, m\}$). À partir de $x_0 \in \R^n$ quelconque, on
définit par récurrence
\[ x_{k+1} = p_{(k+1\, \textnormal{mod}\, n)}(x_k) \]
(faire un dessin !). On va montrer que la suite $(x_k)$ converge vers une
solution (sous réserve d'existence), et même mieux :

\begin{proposition}
  Soit $S$ le sous-espace affine des solutions. Supposons que $S$ soit non vide.
  Alors la suite $(x_k)$ tend vers la solution de $Ax = b$ la plus proche de
  $x_0$, soit le projeté orthogonal de $x_0$ sur $S$.
\end{proposition}

En particulier, s'il existe une unique solution et $(x_k)$ converge vers elle.
Par contre, s'il n'y a pas de solutions, on peut voir que la suite ne converge
pas.

\begin{proof}
  On a $S = \bigcap_{i=1}^n H_i$. Ainsi, $S$ est aussi l'ensemble des points
  fixes communs de $p_1, \ldots, p_m$. Soit $x^*$ le projeté orthogonal de $x_0$
  sur $S$ ; il s'agit de montrer que $x_k \longrightarrow x^*$ quand $k \to
  +\infty$.

  En posant $y_k = x_k - x^*$, cela revient à montrer $y_k \longrightarrow 0$.
  On voit que
  \[ y_{k+1} = p_i(x_k) - x^* = p_i(x_k) - p_i(x^*) = \pi_i(y_k) \]
  où $\pi_i$ est la partie linéaire de $p_i$, soit la projection orthogonale sur
  $\Ker(l_i)$.

  Notons également $H'_i$ la direction de $H_i$ (qui est un hyperplan
  vectoriel), et $S' = \bigcap_{i=1}^n H'_i$ la direction de $S$. Comme tous les
  $\pi_i$ stabilisent $S'$, ils stabilisent aussi $F = S'^\perp$. Par
  récurrence, $y_k \in F$ pour tout $k \in \N$.

  Pour montrer que $y_k \longrightarrow 0$, on va établir que $\|\Pi_{|F}\| < 1$
  où $\Pi = \pi_n \circ \ldots \circ \pi_1$. Ensuite, comme $\|\pi_i\| = 1$, on
  aura $\|y_k\| \leq \|\Pi_{|F}\|^{\lfloor p/n \rfloor} \|y_0\|$, d'où
  convergence linéaire.

  Soit $z \in F$. On a $\|\pi_i(z)\| = \|z\|$ si et seulement si $\pi(z) = z$
  soit $z \in \Ker(l_i)$, et $\|\pi_i(z)\| < \|z\|$ sinon (par théorème de
  Pythagore…). Donc $\Pi(z) = z \Leftrightarrow z \in \bigcap_{i=1}^n \Ker(l_i)
  = S'$. Comme $F \perp S'$, dès que $z \neq 0$, $\|\Pi(z)\| < \|z\|$. Comme
  nous sommes en dimension finie, ceci implique que $\|\Pi_{|F}\| < 1$ (par
  compacité de la sphère unité).
\end{proof}

\newpage

\section{Algèbre (et géométrie)}

\subsection{Points à distances impaires, avec le déterminant de Gram}
\label{gram}

Le résultat suivant est tiré d'un petit article : \emph{Are there $n+2$ points
  in $E^n$ with odd integral distances}, Graham, Rothschild \& Straus. Il a été
posé comme exercice à l'oral de l'ENS Lyon en 2015. (Peut-être se trouve-t-il
dans l'un des Francinou--Gianella…)
\begin{theorem}
  Soit $n \in \N^*$. Il existe $n+2$ points distincts à distances entières
  impaires dans $\R^n$ si et seulement si $n+2 \equiv 0 \mod 16$.
\end{theorem}

La preuve originale utilise le \emph{déterminant de Cayley-Menger}, qui permet
de calculer le volume de simplexes et généralise ainsi la formule de Héron. On
trouvera des détails sur ce fameux déterminant dans le Zavidovique. Nous allons
utiliser ici le déterminant de Gram, plus connu, pour éviter des calculs avec
des opérations élémentaires sur les lignes et les colonnes.

\paragraph{Preuve du sens direct}

Soit $n \in \N$ et $x_0, \ldots, x_{n+1}$ des points dans $\R^n$ tels que pour
tout $i \neq j$, $\|x_i - x_j\| \in 2\Z + 1$. Quitte à translater, on peut
prendre $x_0 = 0$.

Notons $G = (\langle x_i, x_j \rangle)_{1 \leq i,j \leq n+1}$ la matrice de Gram
de $x_1, \ldots, x_{n+1}$, $J$ la matrice carrée de taille $n+1$ dont tous les
coefficients valent 1, et $A = (a_{ij})_{1 \leq i,j \leq n+1} = I+J$.

\begin{proposition}
  $\det G = 0$.
\end{proposition}
\begin{proof}
  Le déterminant de Gram d'une famille liée est toujours nul, et les $x_1,
  \ldots, x_{n+1}$ sont dans $\R^n$ donc sont liés. En effet, si $M$ est la
  matrice des $(x_i)$ dans une base orthonormale (de taille $n \times (n+1)$),
  alors $G = M^T M$ a un rang majoré par celui de $M$, qui est le rang de la
  famille de vecteurs.
\end{proof}

\begin{proposition}
  $\det A = n+2$.
\end{proposition}
\begin{proof}
  $J$ est de rang 1 donc a pour valeur propre 0 avec multiplicité $n$. On
  vérifie que $(1,\ldots,1)$ est vecteur propre pour la valeur propre $n+1$, ce
  qui achève de déterminer le spectre de $J$. Les valeurs propres de $A = I+J$
  sont donc $1, \ldots, 1, n+2$, leur produit vaut donc $n+2$.
\end{proof}

On va prouver $\det 2G \equiv \det A \mod 16$, ce qui suffira à conclure avec
les deux propositions ci-dessus. Pour cela, regardons ce qu'on peut dire sur
$2G$ modulo 16.

\begin{remark}
  Si $m$ est impair, $m^2 \equiv 1 \mod 8$ et $2m^2 \equiv 2 \mod 16$.
\end{remark}
\begin{proof}
  Facile à vérifier à la main ; le second résultat se déduit du premier, pas
  besoin d'examiner 8 classes de congruence.
\end{proof}

Ainsi, l'identité de polarisation $2 \langle x_i, x_j \rangle = \|x_i\|^2 +
\|x_j\|^2 - \|x_i - x_j\|^2$ entraîne que les coefficients non diagonaux de $2G$
sont congrus à 1 modulo 8 (remarquer que $\|x_i\|^2 = \|x_i - x_0\|^2$ est bien
le carré d'un nombre impair). Quant aux coefficients diagonaux, de la forme
$2\|x_i\|^2$, ils sont congrus à 2 modulo 16. Ainsi
\[ 2G \equiv A + B \mod 16, \qquad B = (b_{ij})_{1 \leq i,j \leq n+1} \in
  S_{n+1}(\Z),\; b_{ii} = 0,\; b_{ij} \in \{0,8\} \]
Donc $\det 2G \equiv \det(A+B) \mod 16$ car le déterminant est un polynôme à
coefficients entiers en les coefficients de la matrice. Reste à prouver
$\det(A+B) \equiv \det A \mod 16$.

Écrivons la formule de Leibniz :
\[ \det(A+B) = \sum_{\sigma \in \Sigmap_{n+1}} \varepsilon(\sigma) T_\sigma,
  \quad T_\sigma = \prod_{i=1}^{n+1} (a_{i \sigma(i)} + b_{i \sigma(i)}) \]
$A+B$ étant une matrice symétrique, $T_\sigma = T_{\sigma^{-1}}$ pour tout
$\sigma \in \Sigmap_n$ (et en général $\varepsilon(\sigma) =
\varepsilon(\sigma^{-1})$), et
\[ T_\sigma \equiv \prod_{i=1}^{n+1} a_{i \sigma(i)} \mod 8 \quad \text{donc}
  \quad T_\sigma + T_{\sigma^{-1}} = 2 T_\sigma \equiv 2 \prod_{i=1}^{n+1} a_{i
    \sigma(i)} \mod 16. \]

On peut ainsi regrouper les termes de la somme dans $\det(A+B)$ par deux pour
montrer la congruence voulue… à l'exception des termes pour $\sigma =
\sigma^{-1}$, c'est à dire $\sigma$ involutif.

Fixons $\sigma$ une involution et développons $T$. Étudions les termes
comportant au moins un facteur $b_i$. S'il y en a deux, alors le terme est
divisible par 64, donc congru à 0 mod 16. Donc
\[ T_\sigma \equiv \prod_{i=1}^{n+1} a_{i \sigma(i)} + \sum_{i=1}^{n+1} t_i
  \mod 16 \qquad t_i = b_{i \sigma(i)} \prod_{j \neq i} a_{j \sigma(j)}
  \equiv 0 \mod 8 \]
Pour $i \in \{1, \ldots, n+1\}$, alors :
\begin{itemize}
\item si $i$ est un point fixe de $\sigma$, alors $b_{i \sigma(i)} = b_{ii} = 0$
  donc $t_i = 0$ ;
\item sinon, $\sigma$ transpose $i$ et $\sigma(i)$, et $t_i = t_{\sigma(i)}$,
  toujours par symétrie des matrices $A$ et $B$.
\end{itemize}
Finalement, on peut toujours regrouper les termes non nuls par deux, et obtenir
que
\[ T_\sigma \equiv \prod_{i=1}^{n+1} a_{i \sigma(i)} \mod 16 \]
En fin de compte, on a :
\[ \det(A+B) \equiv \sum_{\sigma \in \Sigmap_{n+1}} \varepsilon(\sigma)
  \prod_{i=1}^{n+1} a_{i \sigma(i)} \equiv \det A \mod 16 \]
ce qu'il fallait démontrer.

\paragraph{Preuve du sens réciproque}

Soit $n = 16m - 2$, $m \in \N^*$, plaçons-nous dans l'espace euclidien de
dimension $n$. Soit $H$ un hyperplan et $P_1, \ldots, P_n \in H$ les sommets
d'un simplexe régulier de centre $O$, avec $P_iP_j = n/2 = 8m-1$. On va rajouter
à cette famille deux points symétriques par rapport à $H$, $Q$ et $Q'$, de sorte
que le milieu de $[QQ']$ soit $O$. En prenant $QQ' = 4m - 1$, on peut montrer
que $QP_i = Q'P_i = 6m - 1$ pour tout $i$ : on a bel et bien $n+2$ points à
distances impaires.


\newpage


\subsection{Étude des automorphismes extérieurs de $\Sigmap_6$}
\label{s6}

(Inspiré d'un billet de blog de David Madore.)

Supposons qu'on ait prouvé l'existence d'un automorphisme extérieur (voir à la
fin pour une construction). À quoi ressemble l'ensemble de ces automorphismes
extérieurs ? Peut-on les décrire tous, de façon combinatoire ? On va présenter
ici une description inspirée de celle faite par Sylvester vers 1844 ; au lieu de
parler de synthèmes, on utilisera des triples transpositions, qui sont la même
chose avec de la structure algébrique en plus.

Pour $x \in \{1, \ldots, 6\}$, on note $e(x) = (x\;y_1)\ldots(x\;y_5) \in
\Sigmap_6$ où $\{ y_1, \ldots, y_5 \} = \{1, \ldots, 6\}\setminus\{x\}$. Les
éléments la forme $e(x)$ sont appelés \emph{étoiles} et leur ensemble est noté
$E$. $e$ réalise une bijection canonique entre $\{1, \ldots, 6\}$ et $E$.

\begin{proposition}
  Toute famille de 5 transpositions distinctes ne commutant pas deux à deux est
  une étoile.
\end{proposition}
\begin{proof}
  Soit $\{\tau_1, \ldots, \tau_5\}$ une telle famille. $\tau_1$ et $\tau_2$ ne
  commutent pas donc $\tau_1 = (a\;b)$, $\tau_2 = (a\;c)$ avec $b \neq c$. De
  même $\tau_3 = (a'\;b')$, $\tau_4 = (a'\;c')$ avec $b' \neq c'$. $\tau_1$ et
  $\tau_3$ ne commutent pas non plus, et par l'absurde, si $a' = b$, alors on
  trouve que $\tau_2$ et $\tau_3$ commutent, contradiction. De même on ne peut
  pas avoir $a = b'$. Donc $a' = b$. Ainsi $\tau_1, \ldots, \tau_4$ ont un
  élément commun, et on montre facilement que $\tau_5$ aussi. Donc $\{\tau_1,
  \ldots, \tau_5\} = e(a) \in E$.
\end{proof}

\begin{corollary}
  Tout automorphisme qui envoie les transpositions sur des transpositions est
  intérieur.
\end{corollary}
\begin{proof}
  Soit $\varphi$ cet automorphisme. $\varphi(E) = E$, car \enquote{ne pas commuter}
  est préservé par automorphisme. Posons $g : x \mapsto e^{-1}(\varphi(e(x)))$, $g
  \in \Sigmap_6$, de sorte que $\varphi(e(x)) = e(g(x))$. Pour tout $a \neq b$,
  comme $\{(a\;b)\} = e(a) \cap e(b)$, on a $\varphi((a\;b)) = (g(a)\;g(b))$.
  $\varphi$ coïncide donc avec $\sigma \mapsto g\sigma g^{-1}$ sur les
  transpositions, qui engendrent $\Sigmap_6$, donc $\varphi$ est intérieur.
\end{proof}

\begin{proposition}
  Les automorphismes extérieurs de $\Sigmap_6$ échangent transpositions et
  triples transpositions.
\end{proposition}
\begin{proof}
  En effet, ce sont les seules classes de conjugaison d'ordre 2 dont les
  permutations ont pour signature $-1$. (Les automorphismes stabilisent
  $\mathfrak{A}_6$ car c'est le seul sous-groupe distingué non trivial.)
\end{proof}

On peut déjà en déduire que :

\begin{theorem}
  $\Aut(\Sigmap_6)/\mathrm{Int}(\Sigmap_6) \simeq \Z/2\Z$.
\end{theorem}
\begin{proof}
  Si $\varphi \in \Aut(\Sigmap_6) \setminus \mathrm{Int}(\Sigmap_6)$ et
  $\tau$ est une transposition, $\varphi(\tau)$ est une triple transposition et
  $\varphi^2(\tau)$ est une transposition. Ainsi, $\varphi^2 \in
  \mathrm{Int}(\Sigmap_6)$.
\end{proof}

En fait, on a même un produit semi-direct, mais on va s'intéresser à autre
chose.

Soit $F$ l'ensemble des familles de 5 triples transpositions qui ne commutent
pas, qu'on appellera \emph{co-étoiles}. Alors $\widehat{\varphi} : X \in E \mapsto
\varphi(X) \in F$ est une bijection.

\begin{proposition}
  Pour tout $g \in \Sigmap_6$, le diagramme suivant est commutatif :
  \begin{center}
  \begin{tikzcd}[column sep=large]
    \{1,\ldots,6\} \ar[d, "g"] \ar[r, "e"] & E \ar[d, "g(-)g^{-1}"]
    \ar[r, "\widehat{\varphi}"] & F \ar[d, "\varphi(g)(-)\varphi(g)^{-1}"] \\
    \{1,\ldots,6\} \ar[r, "e"] & E \ar[r, "\widehat{\varphi}"] & F
  \end{tikzcd}
  \end{center}
\end{proposition}
\begin{proof}
  Le carré de gauche signifie que la conjugaison sur les étoiles correspond à
  l'action sur les points, ce qu'on a déjà vu précédemment.
  
  Dans le carré de droite, on veut prouver que $\varphi(gXg^{-1}) =
  \varphi(g)\varphi(X)\varphi(g^{-1})$, où $X \in E$, donc $X \subset \Sigmap_6$. Mais
  c'est simplement la propriété de morphisme.
\end{proof}
On en déduit ce diagramme :
\begin{tikzcd}[column sep=large]
  \{1,\ldots,6\} \ar[d, "g"] \ar[r, "\widehat{\varphi^{-1}} \circ e"] 
  & F \ar[d, "g(-)g^{-1}"] \\
  \{1,\ldots,6\}\ar[r, "\widehat{\varphi^{-1}} \circ e"] & F 
\end{tikzcd}

Ainsi, tout automorphisme extérieur peut s'écrire sous la forme $\varphi(g)(x) =
f^{-1}(gf(x)g^{-1})$ avec $f : \{1, \ldots, 6\} \xrightarrow{\sim} F$ bijective.
Or, il y a autant d'automorphismes extérieurs qu'intérieurs
(puisque\footnote{Une utilisation du théorème de Lagrange se cache ici. Il faut
  bien voir que dans tout le développement, on utilise de la théorie des groupes
  pour éviter d'avoir à faire des dénombrements \enquote{à la main}…} le
quotient est $\Z/2\Z$), et $\mathrm{Int}(\Sigmap_6) \simeq \Sigmap_6$ (car on
peut retrouver la permutation d'origine à partir de la conjugaison en agissant
sur les étoiles !) : il y en a donc $6!$, autant que de bijections $\{1, \ldots,
6\} \xrightarrow{\sim} F$. Donc :
\begin{itemize}
\item pour tout $f$, le $\varphi$ ainsi défini est bien un automorphisme
  extérieur~;
\item pour tout $\varphi$, le $f$ qui convient est unique.
\end{itemize}

\paragraph{Conclusion} Tout automorphisme extérieur de $\Sigmap_6$ se factorise
en fait comme la composition de deux isomorphismes entre $\Sigmap_6$ et
$\Sigmap(F)$ : l'action par conjugaison de $\Sigmap_6$ sur $F$, et un transfert
de structure via une bijection. On a en fait un isomorphisme (qui n'est pas
endo) tout à fait canonique entre deux groupes de permutations sur 6 éléments,
mais dont les ensembles sous-jacents ne peuvent être identifiés que par un choix
non canonique de bijection, induisant alors un automorphisme extérieur.

En langage catégorique, on pourra résumer élégamment tout ceci en disant que
l'endofoncteur du groupoïde des ensembles de cardinal 6 qui a tout ensemble $X$
associe les co-étoiles de $\Sigmap(X)$ n'est pas naturellement isomorphe à
l'identité.


\paragraph{Une dernière remarque} Si deux triples transpositions partagent une
transpositions, elles commutent. (En effet, dans $\mathfrak{A}_4$, les doubles
transpositions et l'identité forment un sous-groupe isomorphe à $(\Z/2\Z)^2$,
qui est abélien.) Ainsi, les co-étoiles correspondent aux partitions du graphe
complet à 6 éléments en 5 triplets d'arêtes disjointes, c'est-à-dire aux
\emph{1-factorisations} (un \emph{1-facteur}, aussi appelé \emph{couplage
  parfait}, est un ensemble d'arêtes tel que chaque sommet soit incident à
exactement une arête du couplage ; ici, cela correspond donc aux
triples transpositions).

\paragraph{Annexe : construction d'un automorphisme extérieur de $\Sigmap_6$} La
construction présentée ici est tirée de Perrin, \emph{Cours d'algèbre},
proposition I.8.11.

\begin{remark}
  Il revient au même trouver un isomorphisme $\varphi : \Sigmap_6
  \xrightarrow{\sim} \Sigmap(E)$ qui n'est induit par aucune bijection
  $\{1,\ldots,6\} \to E$.
\end{remark}
(Et remarquons que plus haut, on a bien construit un tel isomorphisme, vers le
groupe de permutation des co-étoiles !)
\begin{proof}
  En effet, si $E = \{1,\ldots,6\}$, l'isomorphisme (automorphisme, donc)
  $\Sigmap_6 \to \Sigmap_6$ induit par une permutation $\sigma$ de
  $\{1,\ldots,6\}$ est exactement la conjugaison par $\sigma$ (penser à l'action
  de la conjugaison sur la décomposition en cycles disjoints). On retrouve ainsi
  les automorphismes intérieurs.

  Réciproquement, si $\varphi : \Sigmap_6 \to \Sigmap(E)$ n'est pas induit par une
  bijection, on a tout de même une égalité de cardinaux entraînant l'existence
  d'une bijection $f : \{1,\ldots,6\} \to E$, et alors quelle que soit $f$, on
  vérifie que $\varphi \circ \Sigmap(f)^{-1}$ est un automorphisme extérieur.
\end{proof}

Nous allons construire une telle bijection à partir du lemme ci-dessous.

\begin{lemma}
  Il existe un sous-groupe $H < \Sigmap_6$ d'indice 6 agissant transitivement
  sur $\{1,\ldots,6\}$ (pour l'action canonique de $\Sigmap_6$, bien entendu).
\end{lemma}
En fait, la situation est la suivante : dans $\Sigmap_n$ pour $n \neq 6$, de
tels sous-groupes n'existent pas et les sous-groupes d'indices $n$ sont ceux qui
stabilisent un point. Dans $\Sigmap_6$, on a aussi ceux qui stabilisent une
co-étoile. La vérification de tout ceci est laissée à la lectrice.

Dans le but d'éviter les raisonnements circulaires, une autre construction de
$H$ est présentée ci-dessous.
\begin{proof}
  Faisons agir $\Sigmap_5$ sur ses 5-Sylow par conjugaison. Ceci donne un
  morphisme de $\Sigmap_5$ dans le groupe des permutations de ces 5-Sylow, qui
  sont au nombre de 6. Le morphisme est injectif car son noyau ne peut être ni
  $\Sigmap_5$, ni $\mathfrak{A}_5$ : $\Sigmap_5$ s'identifie donc à un
  sous-groupe $H$ de $\Sigmap_6$, d'indice 6. La transitivité de l'action est
  garantie par les théorèmes de Sylow.
\end{proof}

Posons maintenant $E = \Sigmap_6/H$ l'ensemble des classes à gauche. $\Sigmap_6$
agit dessus par translation ce qui donne un morphisme $\varphi : \Sigmap_6 \to
\Sigmap(E)$. $\Ker(\varphi)$ est distingué dans $\Sigmap_6$, et d'indice au moins 6
(taille d'une orbite), donc c'est $\{\textnormal{id}\}$. $\varphi$ est ainsi
injective, et même bijective entre groupes de même cardinal.

Si $f$ était telle que $\varphi = \Sigmap(f)$, alors le stabilisateur de $H \in E$
pour l'action $\varphi$ serait le groupe des permutations ayant pour point fixe
$f^{-1}(H) \in \{1,\ldots,6\}$. Or ici, le stabilisateur de $H$ contient $H$, vu
comme sous-groupe de $\Sigmap_6$, qui agit transitivement donc dont les éléments
n'ont aucun point fixe commun. L'existence d'une telle $f$ est donc impossible.
$\varphi$ est donc un isomorphisme qui n'est pas induit par une bijection.

\newpage

\subsection{Non-isomorphisme exceptionnel (avec la réduction de Jordan)}
\label{non-iso}

Dans H2G2 tome 1, ou encore dans le Perrin exercice IV.5.1. Le premier contient
des erreurs et le second est un exercice sans correction…

Posons $G = \PSL_4(\F_2)$ et $H = \PSL_3(\F_4)$. On va montrer que :
\begin{itemize}
\item $|G| = |H| = 20160$ ;
\item $G$ possède plusieurs classes de conjugaison d'éléments d'ordre 2 ;
\item $H$ n'en possède qu'une seule.
\end{itemize}
En conséquence de ces deux derniers points, $G \not\simeq H$. De plus, on sait
que :
\begin{theorem}
  $\PSL_n(\F_q)$ est simple sauf pour $n = 2$ et $q = 2,3$.
\end{theorem}
\begin{proof}
  C'est long…
\end{proof}
Une fois que nous aurons démontré les affirmations précédentes, ce dernier
théorème nous permettra de dire que $G$ et $H$ sont tous deux simples, de même
cardinal, et pourtant non isomorphes.

\paragraph{Comment compter les classes de conjugaison ?} Rappelons que sur tout
corps (pas forcément algébriquement clos), les matrices nilpotentes sont
classifiées à similitude près par la réduction de Jordan.

\begin{lemma}
  Les classes de similitudes de matrices nilpotentes d'indice 2 dans $\M_n(K)$
  sont en bijection avec $\{1, \ldots, \lfloor n/2 \rfloor\}$.
\end{lemma}
\begin{proof}
  Soit une telle classe, elle admet un unique représentant $N =
  \Diag(J_1, \ldots, J_k)$ où les $J_i$ sont des blocs de Jordan, de
  taille décroissante. $N^2 = 0$ signifie que $J_i^2 = 0$ pour tout $i$. Les
  blocs de Jordan sont donc de taille 1 ou 2. On réalise donc la bijection en
  comptant les blocs d'ordre 2 : il y en a forcément au moins un, sinon $N = 0$,
  et il peut y en avoir n'importe quel nombre jusqu'à $\lfloor n/2 \rfloor$ ($N$
  étant de taille $n$).
\end{proof}
\begin{corollary}
  Si $K$ est de caractéristique 2, il y a $\lfloor n/2 \rfloor$ classes de
  conjugaison d'ordre 2 dans $\GL_n(K)$.
\end{corollary}
\begin{proof}
  Soit $A \in \GL_n(K)$. $A$ est d'ordre deux ssi $A \neq I$ et $A^2 = I$, ce
  qui se réécrit aussi $A^2 - I = 0$ i.e. $(A-I)^2 = 0$ ($K[A]$ étant un anneau
  commutatif de caractéristique 2), i.e. $A-I$ nilpotente d'indice 2. Et $A$ est
  conjugué à $B$ (comme éléments du groupe) ssi $A-I$ est semblable à $B-I$
  (comme matrices). On est donc ramenés au lemme précédent.
\end{proof}
On a en fait classifié des orbites pour la conjugaison dans $\GL_n(K)$ en
prolongeant cette action de groupe à l'espace $\M_n(K)$…

\paragraph{Étude de $G$}

On a $G = \SL_4(\F_2)$ car $I$ est la seule homothétie, puis $G = \GL_4(\F_2)$
car $\det A \neq 0 \Leftrightarrow \det A = 1$ (tout ceci parce que $\F_2^* =
\{1\}$). Ainsi, 
\[ |G| = (2^4 - 1)(2^4 - 2)(2^4 - 2^2)(2^4 - 2^3) = 20160. \]
D'autre part, on peut directement appliquer le lemme précédent : il y a $\lfloor
4/2 \rfloor = 2$ classes de conjugaison d'ordre 2.

\paragraph{Étude de $H$}

On a tout d'abord $\GL_3(\F_4)/\SL_3(\F_4) \simeq \F_4^*$, puis $H \simeq
\SL_3(\F_4)/Z(\SL_3(\F_4))$ avec $Z(\SL_3(\F_4)) \simeq \F_4^*$. En effet,
toutes les homothéties sont dans $\SL_3(\F_4)$ : pour tout $\lambda \in \F_4^*$,
$\det \lambda I = \lambda^3 = 1$ car $\F_4^*$ est un groupe d'ordre 3. Le compte
donne
\[ |H| = \frac{(4^3 - 1)(4^3 - 4)(4^3 - 4^2)}{3^2} = 20160. \]

Dans $\GL_3(\F_4)$, il y a $\lfloor 3/2 \rfloor = 1$ classe de conjugaison
d'ordre 2. Si $A \in \SL_3(\F_4)$ est d'ordre 2, il est donc conjugué à la
transvection
\[ T = \left[\begin{matrix}
      1 & 1 & 0 \\
      0 & 1 & 0 \\
      0 & 0 & 1
    \end{matrix}\right] \]
ce qui s'écrit $A = PTP^{-1}$ avec $P \in \GL_3(\F_4)$. Peut-on choisir $P$ dans
$\SL_3(\F_4)$ ? Oui, quitte à la multiplier à droite par $\Diag(1,1,\det
P^{-1})$. Tout élément d'ordre 2 est donc conjugué à $T$ dans $\SL_3(\F_4)$.

Passons maintenant au quotient dans $H = \PSL_3(\F_4)$. Soit $A \in \SL_3(\F_4)$
tel que $\overline{A}^2 = \overline{I}$ dans $H$, c'est-à-dire $A^2 \in
Z(\SL_3(\F_4))$. Il existe donc $\lambda \in \F_4^*$ tel que $A^2 = \lambda I$.
Soit $\mu$ une racine carrée de $\lambda$ ; il en existe (exactement) une car $x
\mapsto x^2$ est un automorphisme (caractéristique 2 + finitude du corps). En
posant $B = \mu^{-1}A$, on a $\overline{A} = \overline{B}$ dans $H$, et $B^2 =
I$. $B$ est alors conjugué à $T$, et en projetant sur le quotient,
$\overline{A}$ est conjugué à $\overline{T}$ : la classe de conjugaison de ce
dernier est donc la seule, CQFD.

\newpage

\subsection{Sous-groupe de Frattini et théorème de la base de Burnside}

C'est le problème 3 dans Zavidovique, \emph{Un max de maths}. On propose ici une
façon plus courte d'établir les résultats du début.

\begin{theorem}[de la base de Burnside]
  Toutes les familles génératrices minimales (pour l'inclusion) d'un $p$-groupe
  ont même cardinal.
\end{theorem}

\begin{lemma}
  Soient $H_1, \ldots, H_n \trianglelefteq G$ tels que $G/H_i$ soit abélien pour
  tout $i$. Alors $G/\bigcap_i H_i$ est abélien.
\end{lemma}
\begin{proof}
  En effet, $G/H$ est abélien si et seulement si $D(G) \subseteq H$, où $D(G)$
  est le groupe dérivé.
\end{proof}

Fixons maintenant $G$ un $p$-groupe, c'est-à-dire que $|G| = p^m$ avec $p$
premier.

\begin{lemma}
  Soit $H < G$ un sous-groupe strict \emph{maximal}. Alors $H \triangleleft G$
  et $G/H \simeq \Z/p\Z$.
\end{lemma}
\begin{proof}
  Soit $N_G(H)$ le normalisateur de $H$ dans $G$. On a $H \subseteq N_G(H)
  \subseteq G$, or $H$ est maximal, donc soit $N_G(H) = H$, soit $N_G(H) = G$
  i.e. $H \triangleleft G$.

  Supposons par l'absurde que $N_G(H) = H$. L'équation aux classes pour l'action
  de $H$ sur $C(H) = \{gHg^{-1} \mid g \in G\}$ s'écrit :
  \[ [G : H] = [G : N_G(H)] = |C(H)| = \sum_g [H : N_H(gHg^{-1})] \]
  Or $[H : N_H(gHg^{-1})] = 1 \Leftrightarrow g \in H$, et sinon $p \mid [H :
  N_H(gHg^{-1})]$ ; en effet,
  \[ N_H(gHg^{-1}) = N_G(gHg^{-1}) \cap H = g N_G(H) g^{-1} \cap H = gHg^{-1}
  \cap H \]
  En réduisant modulo $p$ l'équation aux classes, on a ainsi $0 \equiv 1 \mod
  p$, contradiction.

  On a donc établi $H \triangleleft G$. $G/H$ est un groupe de cardinal $p^k$
  avec $k \geq 1$. Si $k > 1$, alors en prenant $x \in G/H$ d'ordre $p$, on a
  $\{1\} \subsetneq \langle x \rangle \subsetneq G/H$, qu'on relève par la
  projection canonique $\pi$ en $H \subsetneq \pi^{-1}(\langle x \rangle)
  \subsetneq G$, contredisant la maximalité de $H$. Donc $|G/H| = p$.
\end{proof}

Posons maintenant $F(G)$ l'intersection des sous-groupes maximaux de $G$,
qui porte le petit nom de \emph{sous-groupe de Frattini}.
D'après ce qui précède, on a immédiatement que $F(G) \triangleleft G$ et
$G/F(G)$ est abélien. On notera donc additivement :
\[ \overline{g} + \overline{g'} = \overline{gg'} \qquad
   \overline{g},\overline{g'} \in G/F(G) \]

\begin{proposition}
  Pour tout $\overline{g} \in G/F(G)$, $\overline{g^p} = \overline{1}$.
\end{proposition}
\begin{proof}
  Soit $g \in G$ un représentant de $\overline{g}$. Pour $H < G$ maximal, notons
  $[g]_H$ sa classe dans $G/H$. Comme $G/H \simeq \Z/p\Z$, on a $[g]_H^p =
  [1]_H$, soit $g^p \in H$. Ainsi, $g^p \in \bigcap_H H = F(G)$.
\end{proof}

On peut donc définir la loi externe
\[ \overline{n} \cdot \overline{g} = \overline{g^n} \qquad
  \overline{n} \in \Z/p\Z,\, \overline{g} \in G/F(G)
\]
dont on vérifie\footnote{Les amateurs d'algèbre commutative auront compris qu'il
  s'agit de passer au quotient sur la structure de $\Z$-module d'un groupe
  abélien dont l'annulateur contient l'idéal $p\Z$.} qu'il munit $G/F(G)$ d'une
structure de $\Z/p\Z$-espace vectoriel ! Plus explicitement, on a :
\[ \forall (n_i) \in \Z/p\Z,\, \forall (\overline{g_i}) \in G/F(G), \quad
  \sum_i \overline{n_i} \cdot \overline{g_i} = \overline{\prod_i g_i^{n_i}} \]
et cette écriture rend évidente la proposition suivante :

\begin{proposition}
  Pour tous $\overline{g_1}, \ldots, \overline{g_k} \in G/F(G),\,
  \Vect_{\F_p}  \{\overline{g_1}, \ldots, \overline{g_k}\} =
  \langle \overline{g_1}, \ldots, \overline{g_k} \rangle$.
\end{proposition}

Ainsi, les parties génératrices minimales de $G/F(G)$ sont des \emph{bases}, la
théorie de la dimension nous dit donc qu'elles ont toutes le même cardinal, soit
$d = \dim_{\F_p} G/F(G)$.

Pour conclure, il ne reste plus qu'à montrer ceci :

\begin{proposition}
  Si $\{g_1, \ldots, g_k\}$ est une partie génératrice minimale de $G$, alors
  $\{ \overline{g_1}, \ldots, \overline{g_k} \}$ est une base de $G/F(G)$ sur
  $\F_p$.
\end{proposition}
\begin{proof}
  $\{ \overline{g_1}, \ldots, \overline{g_k} \}$ est évidemment une famille
  génératrice ; supposons par l'absurde qu'elle ne soit pas libre.

  Dans ce cas, $k > d$ et on peut extraire une base ; sans perte de généralité,
  disons que $\{ \overline{g_1}, \ldots, \overline{g_d} \}$ est une base de
  $G/F(G)$, et en particulier engendre $G/F(G)$ comme groupe abélien. On a alors
  $\langle \{g_1, \ldots, g_d\} \cup F(G) \rangle = G$.

  Remarquons cependant que $\langle g_1, \ldots, g_d \rangle \neq G$ par
  minimalité ; il existe donc $H < G$ maximal contenant $\langle g_1, \ldots,
  g_d \rangle$. Comme $F(G) \subseteq H$ par définition, on a $\langle \{g_1,
  \ldots, g_d\} \cup F(G) \rangle \subseteq H$ : contradiction.
\end{proof}

\newpage

\subsection{Théorème de Lie-Kolchin}

Un long exercice dans H2G2 tome 1, corrigé dans la nouvelle édition (p. 238).

\begin{definition}
  Le \emph{groupe dérivé} $D(G)$ d'un groupe $G$ est le sous-groupe engendré par
  les commutateurs $[g,h]= ghg^{-1}h^{-1}$. $G$ est dit \emph{résoluble} s'il
  existe $l$ tel que $D^l(G) = \{1\}$.
\end{definition}
\begin{proposition}
  Pour tout $k \in \N$, $D^k(G) \trianglelefteq G$.
\end{proposition}
\begin{proof}
  On montre par récurrence que $D^k(G)$ est stable par tout $\varphi \in
  \Aut(G)$. Le cas de base $k=0$ est immédiat. Supposons que $\varphi(D^k(G)) =
  D^k(G)$ ; alors $\varphi$ se restreint en un automorphisme de $D^k(G)$ et la
  formule $\varphi([g,h]) = [\varphi(g),\varphi(h)]$ ($g,h \in D^k(G)$) montre
  qu'il stabilise $D^{k+1}(G)$.

  Il suffit pour conclure d'appliquer ceci à un automorphisme intérieur de $G$
  (mais attention, l'automorphisme restreint sur $D^k(G)$ n'est pas forcément
  intérieur, d'où la nécessité d'une hypothèse de récurrence plus forte que
  $D^k(G) \trianglelefteq G$).
\end{proof}


L'objectif est de montrer :

\begin{theorem}[Lie--Kolchin]
  Soit $G$ un sous-groupe résoluble connexe de $\GL_n(\C)$. Les matrices de $G$
  sont cotrigonalisables. De façon équivalente, $G$ est conjugué à un
  sous-groupe des matrices triangulaires inversibles.
\end{theorem}

Si $G$ est abélien, la conclusion est bien connue. Sinon, $n \geq 2$ et il
suffit de montrer que $G$ admet un sous-espace stable non triviale : ainsi, on
pourra trigonaliser par blocs et conclure par récurrence forte sur $n$.
Attention, la récurrence nécessite d'utiliser le fait que l'extraction d'un bloc
diagonal est un morphisme de groupes continu, et d'utiliser la propriété
suivante (admise) :
\begin{proposition}
  L'image par un morphisme d'un groupe résoluble est résoluble.
\end{proposition}

Supposons donc $G$ non abélien. Soit $l$ minimal tel que $D^l(G) = \{1\}$, alors
$l \geq 2$ et $H = D^{l-1}(G)$ est abélien.

$H$ est donc cotrigonalisable, et admet donc un vecteur propre commun $v$. On
pose $V = \Vect(Gv)$ où $Gv = \{Mv \mid M \in G\}$. C'est bien un sous-espace
stable par $G$, et non réduit à $\{0\}$ ; reste à montrer que $V \neq \C^n$.

Montrons que $H$ agit par homothéties sur $V$. Fixons $A \in H$. Pour tout $P
\in G$, $P^{-1}AP \in A$ ($A = D^{l-1}(G) \triangleleft G$) ; $v$ étant vecteur
propre commun $P^{-1}APv = \lambda_P v$ pour un certain $\lambda_P \in \C$, ce
qui s'écrit aussi $APv = \lambda_P Pv$.

Maintenant, $\lambda_P$ est une fonction continue de $P$ : en effet, elle
s'écrit $\langle APv, Pv \rangle / \|Pv\|^2$ en utilisant le produit hermitien
canonique. L'ensemble $\{ \lambda_P \mid P \in G \}$ est donc connexe puisque
$G$ l'est. Or les $\lambda_P$ sont inclus dans le spectre de $A$, invariant par
conjugaison, et discret. Donc $\lambda_P$ est constant. $A$ est donc une
homothétie sur $Gv$, puis sur $V$.

Si maintenant $V = \C^n$, alors $A \subseteq \C^*I$. Comme $A$ est un groupe
dérivé (car $G$ non abélien !) et $\det\,[g,h] = 1$, $\det = 1$ sur $A$. D'où $A
\subset \mathbb{U}_nI$, or $A$ est connexe, donc $A$ est le groupe trivial.
Contradiction. Ainsi, $\{0\} \subsetneq V \subsetneq \C^n$, et on peut enchaîner
sur la récurrence.

Dans cette dernière étape, on a besoin de la propriété suivante :
\begin{proposition}
  Le groupe dérivé d'un groupe connexe est connexe.
\end{proposition}
\begin{proof}
  Admis.
\end{proof}

\newpage


\subsection{Constructibilité des polygones réguliers}

Rappelons que l'ensemble des nombres \emph{constructibles} est la clôture
quadratique de $\Q$, et qu'il correspond, d'après le théorème de Wantzel, à
l'ensemble des affixes dans $\C$ des points repérables par une construction à la
règle non graduée et au compas à partir des points 0 et 1.

\begin{theorem}[Gauss--Wantzel]
  Soit $p$ un nombre premier impair. $\zeta_p = e^{2\pi i / p}$ est
  constructible si et seulement si $p$ est de la forme $2^n + 1$.
\end{theorem}

Dire que $\zeta_p$ est constructible revient à dire qu'on peut construire le
polygone régulier à $p$ côtés à la règle et au compas.

\begin{remark}
  Dans ce cas, $p$ est appelé \emph{nombre premier de Fermat} et on montre qu'il
  s'écrit forcément comme $p = 2^{2^m} + 1$.
\end{remark}

\begin{proposition}
  Le polynôme minimal de $\zeta_p$ est $\Phi_p(X) = X^{p-1} + \ldots + 1$.
\end{proposition}
\begin{proof}
  On a bien $\Phi_p(\zeta_p) = 0$, et on vérifie l'irréductibilité en appliquant
  à $\Phi_p(X+1)$ le critère d'Eisenstein.
\end{proof}
\begin{corollary}
  $\deg \zeta_p = [\Q(\zeta_p) : \Q] = p - 1$.
\end{corollary}

\begin{proof}[Preuve du sens direct du théorème]
  Si $\zeta_p$ est constructible, alors il est inclus dans une tour d'extensions
  quadratiques : $\zeta_p \in K_m \supset K_{m-1} \supset \ldots \supset K_0 =
  \Q$ avec $[K_m : K_{m-1}] = 2$. Ainsi, $p - 1 = \deg \zeta_p \mid [K_m :
  K_{m-1}] \times \ldots \times [K_1 : K_0] = 2^m$, donc $p = 2^n + 1$ avec $n
  \leq m$.
\end{proof}

Pour le sens réciproque, nous allons considérer le groupe
$\mathrm{Gal}(\Q(\zeta_p))/\Q$ des automorphismes de $\Q(\zeta_p)$.

\begin{proposition}
  $\mathrm{Gal}(\Q(\zeta_p))/\Q \simeq (\Z/p\Z)^\times \simeq \Z/(p-1)\Z$.
\end{proposition}
\begin{proof}
  Tout d'abord, tout automorphisme $\sigma \in \mathrm{Gal}(\Q(\zeta_p))/\Q$ est
  uniquement déterminé par l'image de $\zeta_p$. Cette image est forcément une
  racine de $\Phi_p$. Réciproquement, toute racine $z$ de $\Phi_p$ détermine un
  automorphisme de $\Q(\zeta_p)$ par composition des isomorphismes canoniques
  $\Q(\zeta_p) \simeq \Q(X)/(\Phi_p) \simeq \Q(z)$.

  De plus, les racines de $\Phi_p$, i.e. les racines primitives de l'unité, sont
  en bijection avec $(\Z/p\Z)^\times$, via $\bar{k} \mapsto \zeta_p^k$. Ainsi,
  $\bar{k} \mapsto (\phi_k : \zeta_p \mapsto \zeta_p^k)$ est une bijection vers
  $\mathrm{Gal}(\Q(\zeta_p))/\Q$, et on vérifie que c'est un morphisme.
\end{proof}

\begin{proof}[Preuve du sens réciproque]
  Supposons que $p = 2^n + 1$. Alors $\mathrm{Gal}(\Q(\zeta_p)/\Q) \simeq
  \Z/2^n\Z$. Soit $\sigma$ un générateur du groupe, alors en notant $G_l =
  \langle \sigma^{2^l} \rangle$, on a
  \[ \{1\} = G_n \subset G_{n-1} \subset \ldots \subset G_0 =
    \textnormal{Gal}(\Q(\zeta_p)/\Q) \]
  Puis, en posant $K_l = \{x \in \Q(\zeta_p) \mid \sigma^{2^l}(x) = x\}$,
  qui est un sous-corps, on a :
  \[ \Q(\zeta_p) = K_n \supseteq K_{n-1} \supseteq \ldots \supseteq K_0 = \Q \]

  À ce stade, on peut conclure immédiatement avec la correspondance de Galois :
  on a $[K_l : K_{l-1}] = [G_{l-1} : G_l] = 2$, donc on a bien obtenu une tour
  d'extensions quadratiques correspondant à notre tour de sous-groupes. Ainsi,
  le résultat est trivial d'un point de vue galoisien.

  Pour se passer du théorème fondamental de la théorie de Galois, qui est
  difficile, on va montrer $[K_l : K_{l-1}] > 1$, puis la multiplicativité des
  degrés permettra de conclure. Posons $x = \sum_{\tau \in G_l} \tau(\zeta_p)$ ;
  il est clair que $x \in K_l$. Supposons par l'absurde que $x \in K_{l-1}$.
  Alors, en notant $\rho = \sigma^{2^l}$,
  \[ \sum_{\tau \in G_l} \tau(\zeta_p) = x = \rho(x) = \sum_{\tau \in \rho G_l}
    \tau(\zeta_p) \]
  Or, $G_l \cap \rho G_l = \emptyset$ puisque $\rho \notin G_l$, et on a vu tout
  à l'heure que $(\tau(\zeta_p),\;\tau \in \mathrm{Gal}(\Q(\zeta_p)/\Q))$ est la
  famille des racines de $\Phi_p$ énumérée sans répétition. Cette famille est
  égale à $(\zeta_p, \ldots, \zeta_p^{p-1})$, qui est une base de $\Q(\zeta_p)$,
  donc en particulier est libre. La relation de liaison obtenue plus haut et
  donc impossible ; contradiction.
\end{proof}


\newpage

\section{Analyse}

\subsection{Les fonctions monotones (continues) sont dérivables presque partout}
\label{monotone}

Un joli résultat suggéré par le rapport de jury d'agrég… mais c'est long !
(Peut-être trop pour 15 minutes ?) Ce qui suit est une tentative de
démonstration qui s'inspire princpalement des \emph{Leçons d'analyse
  fonctionnelle} de Riesz \& Szokefalvi-Nagy, la fin étant tirée de \emph{Real
  Analysis}, Royden (ou Royden \& Fitzpatrick pour la dernière édition). À la
fin de la section, on trouvera des compléments culturels.

On va se restreindre ici aux fonctions monotones \emph{continues}. Même avec
cette hypothèse, ça reste technique, attention !
\begin{theorem}
  Soit $f : [0,1] \to \R$ une fonction continue croissante. Alors $f$ est
  dérivable presque partout.
\end{theorem}

\begin{definition}
  On notera $\displaystyle \Delta f(x,y) = \frac{f(y) - f(x)}{y - x}$ pour $x
  \neq y$ et $f : \R \to \R$.
\end{definition}
Notation dont l'utilité ne fait aucun doute s'agissant de parler de dérivation
d'une fonction d'une variable réelle.

\paragraph{Résultats préliminaires} Commençons par deux petites propositions.
Pour $U \subseteq \R$ un ouvert, notons $CC(U)$ l'ensemble de ses composantes
connexes.
\begin{proposition}
  Les composantes connexes de $U$ sont des intervalles ouverts disjoints,
  en nombre au plus dénombrable, dont la réunion est égale à $U$.
\end{proposition}
\begin{proof}
  Admis, mais c'est classique et facile, donc à savoir démontrer sans hésiter.
\end{proof}
\begin{proposition}
  Soit $f : [a,b] \to \R$ croissante et $U \subset [a,b]$ ouvert dans $\R$.
  Alors
  \[ \sum_{]c,d[ \in CC(U)} (f(d)-f(c)) \leq f(b) - f(a) \]
  les termes de la somme étant positifs.
  Autrement dit, la \textnormal{variation totale} de $f$ sur $[a,b]$ est
  $f(b) - f(a)$.
\end{proposition}
\begin{proof}
  
  Supposons dans un premier temps $|CC(U)| < \infty$, soit $CC(U) =
  \{]c_1,d_1[,\ldots,]c_n,d_n[\}$ avec $c_1 < d_1 \leq c_2 < \ldots \leq d_n$.
  Alors pour tout $i$, $f(d_i) \leq f(c_{i+1})$ car $f$ croissante, donc
  \[ \sum_{i=1}^n (f(d_i) - f(c_i)) = - f(c_1) + (f(d_1) - f(c_2)) + \ldots +
    (f(d_{n-1}) - f(c_n)) + f(d_n) \leq f(d_n) - f(c_1) \]
  Dans le cas $CC(U)$ dénombrable, il suffit de passer à la limite sur les
  sous-familles finies.
\end{proof}

Le lemme qui suit est fondamental dans la preuve du théorème.

\begin{lemma}[des rayons du soleil]
  Soit $f : [a,b] \to \R$ continue et soit $\alpha \in \R$. Posons
  \[ O_g(]a,b[,\alpha)  = \left\{ x \in ]a,b[ | \exists y \in ]a,x[\,/\,
      \Delta f(x,y) < \alpha \right\} \]
  \[ O_d(]a,b[,\alpha) = \left\{ x \in ]a,b[ | \exists y \in ]x,b[\,/\,
      \Delta f(x,y) > \alpha \right\}
  \]
  Alors $O_g(]a,b[,\alpha)$ et $O_d(]a,b[,\alpha)$ sont ouverts dans $\R$ et
  \begin{enumerate}
  \item Pour tout $]c,d[ \in CC(O_g(]a,b[,\alpha))$,
    $\displaystyle \Delta f(c,d) \leq \alpha$.
  \item Pour tout $]c',d'[ \in CC(O_d(]a,b[,\alpha))$,
    $\displaystyle \Delta f(c',d') \geq \alpha$.
  \end{enumerate}
\end{lemma}
Il faut \textit{\textbf{faire un dessin}} pour voir ce qui se passe :
l'hypographe de $f$ est éclairé par un faisceau de rayons parallèles de pente
$\alpha$ provenant de la gauche dans le cas 1, la droite dans le cas 2, et les
ensembles définis sont les zones à l'ombre (la lumière passant à travers les
points de tangence). On peut constater visuellement qu'il y a en fait égalité
sauf éventuellement pour $d = b$ ou $c' = a$, mais nous n'aurons pas besoin de
le prouver formellement.

Remarquons que (1) découle de (2) appliqué à $x \mapsto -f(-x)$, et qu'on peut
se ramener à $\alpha = 0$ quitte à soustraire une fonction linéaire. (Et en
considérant $-f$, on peut obtenir deux autres cas, consistant à éclairer
l'épigraphe au lieu de l'hypographe.) Ce dernier cas est celui généralement
énoncé dans la littérature sous le nom de \enquote{rising sun lemma} (en effet,
$\alpha = 0$ revient à placer le soleil à l'horizon(tale), et les rayons
viennent de la droite i.e. de l'est).

\begin{proof}[Démonstration du \enquote{rising sun lemma}]
  $U$ est ouvert car les inégalités strictes de fonctions continues définissent
  des ouverts, et une projection linéaire d'un ouvert sur une coordonnée
  est un ouvert\footnote{Banach--Schauder en dimension finie !}.

  Soit $]c,d[ \in CC(U)$, on veut maintenant montrer que $f(d) - f(c) \geq 0$.
  Fixons $\varepsilon > 0$. Par compacité, $f$ atteint son maximum sur
  $[c+\varepsilon, d]$ en un point $x$. En particulier $f(x) \geq f(d)$. Or
  $f(d) \geq f(z)$ pour tout $z > d$ car $d \not\in U$. Ainsi $f(x) \geq f(y)$
  pour tout $y > x$, bref, aucun point ne peut faire de l'ombre à $x$ : $x
  \not\in U$. Or $[c+\varepsilon,d[ \subset U$, donc $x = d$. Autrement dit le
  maximum est atteint en l'unique point $d$, d'où $f(c+\varepsilon) < f(d)$, et
  en passant à la limite $f(c) \leq f(d)$.
\end{proof}

Ceci étant établi, c'est parti pour commencer à parler du théorème principal.

\paragraph{Stratégie d'attaque du théorème}
Soit $f : [0,1] \to \R$ continue croissante.
Définissons ses \emph{dérivées de Dini}
\[ D^+f(x) = \limsup_{y \to x^+} \Delta f(x,y) \qquad
  D^-f(x) = \limsup_{y \to x^-} \Delta f(x,y) \]
\[  D_+f(x) = \liminf_{y \to x^+} \Delta f(x,y) \qquad
  D_-f(x) = \liminf_{y \to x^-} \Delta f(x,y) \]

$f$ est dérivable en un point $x$ si et seulement si ces quatre limites (1)
coïncident et (2) sont finies. Nous allons établir que c'est le cas presque
partout. Mais d'abord, faisons le lien avec tout ce dont nous avons parlé avant.

\begin{remark}
  Soient $a < b$, $x \in ]a,b[$ et $\alpha < D_+f(x)$. Alors $x \in O_d(]a,b[,
  \alpha)$. De même, si $\alpha > D_-f(x)$, alors $x \in O_g(]a,b[, \alpha)$.
\end{remark}
\begin{proof}
  $\limsup_{y \to y^+} \Delta f(x,y) > \alpha$ et $]x,b[$ est un voisinage à
  droite de $x$ donc il existe $y \in ]x,b[$ tel que $\Delta(x,y) > \alpha$ :
  c'est exactement la condition d'appartenance à $O_d(]a,b[,\alpha)$.
\end{proof}

On dispose enfin de tous les outils pour attaquer le cœur de la preuve !

\begin{proof}[(1) Existence p.p. de la limite]
Montrons dans un premier temps que $D^+f \leq D_-f$ presque partout. Pour cela,
fixons $\alpha < \beta$ quelconques et posons
\[ S_{\alpha,\beta} = \{ x \in ]0,1[ \mid D_-f(x) < \alpha < \beta < D^+f \} \]
On veut montrer que $S_{\alpha,\beta}$ est de mesure nulle.

En partant de $E_0 = ]0,1[$, nous allons définir par récurrence deux suites de
parties de $\R$ : pour $n \in \N$,
\[ F_n = \bigcup_{I \in CC(E_n)} O_g(I, \alpha) \qquad
   E_{n+1} = \bigcup_{I \in CC(F_n)} O_d(I, \beta) \]
On a $E_0 \supset F_0 \supset E_1 \ldots$ et le lemme des rayons du soleil (à
l'aide une récurrence triviale) garantit que ce sont des ouverts. 

Si $x \in S_{\alpha,\beta}$, la remarque établie plus haut nous dit que comme
$D_-f(x) < \alpha$, $x \in F_0$, puis comme $D^+f(x) > \beta$, $x \in E_1$, et
ainsi de suite… Au bout du compte, $S_{\alpha,\beta} \subset \bigcap_{n \in \N}
E_n$ et nous allons montrer que ce dernier ensemble est négligeable.

Soit $n \in \N$. Soit $]a,b[ \in CC(F_n)$, le cas 1 du lemme nous dit que
$f(b) - f(a) \leq \alpha(b-a)$. Si maintenant $]c,d[ \in CC(E_{n+1} \cap
]a,b[)$, alors le cas 2 du lemme donne $f(d)-f(c) \geq \beta(d-c)$. En sommant
et en appliquant notre majoration de la variation totale, on a :
\[ \beta\mu(E_{n+1} \cap ]a,b[) = \sum_{]c,d[} \beta\mu(]c,d[) \leq \sum_{]c,d[}
  (f(d) - f(c)) \leq f(b) - f(a) \leq \alpha\mu(]a,b[) \]
\[ \mu(E_{n+1}) \leq \frac{\alpha}{\beta} \sum_{]a,b[} \mu(]a,b[) =
  \frac{\alpha}{\beta} \mu(F_n) \leq \frac{\alpha}{\beta} \mu(E_n) \] où $\mu$
est la mesure de Lebesgue. Comme $\alpha/\beta < 1$ et $E_0 = [0,1]$ est de
mesure finie,
\[ \mu(S_{\alpha,\beta}) \leq \mu \left( \bigcap_{n=0}^\infty E_n \right)
  \leq \lim_{n \to \infty} \left( \frac{\alpha}{\beta} \right)^n \mu(E_0) = 0 \]
\[ \mu\left( \{x \in ]0,1[ \mid  D^+f(x) > D_-f(x) \} \right)
  = \mu\left( \bigcup_{\alpha, \beta \in \Q} S_{\alpha,\beta} \right)
  = 0 \]
De façon analogue on peut montrer que $D^-f \leq D_+f$ p.p., ce qui suffit à
obtenir l'égalité p.p. des quatre dérivées de Dini : en effet, on sait que
$\liminf \leq \limsup$ donc $D_+f \leq D^+f$ et $D_-f \leq D^-f$.
\end{proof}

Notons $f'(x)$ cette limite commune qui existe pour tout $x$ hors d'un ensemble
de mesure nulle : on définit ainsi une fonction $f'$, qu'on étend arbitrairement
à $\R$. $f'$ est à valeurs dans $\R_+ \cup \{+\infty\}$. En effet, $f$ étant
croissante, ses taux d'accroissements sont positifs ; et rien ne garantit a
priori que la limite de ces taux d'accroissements soit finie. Reste à montrer :

\begin{proof}[(2) Finitude p.p. de la dérivée]
Calculons d'abord, en prolongeant $f$ par $f(1)$ sur $]1,+\infty[$,
\[
  \int_0^1 \frac{f(x+h) - f(x)}{h}dx =
    \frac{1}{h} \int_1^{1+h} f(x)\,dx - \frac{1}{h} \int_0^h f(x)\,dx
    \xrightarrow[h \to 0^+] f(1) - f(0)
\]
où la dernière égalité est vraie par continuité de $f$. Comme $f'$ est mesurable
(en tant que limite de fonctions mesurables) et positive, on peut l'intégrer et
le lemme de Fatou nous donne
\[ \int_0^{1} f'(x)\,dx \leq \lim_{h \to 0^+}
  \int_0^{1} \frac{f(x+h) - f(x)}{h}dx =
  f(1)- f(0) < +\infty \]
Ainsi, $f'$ est positive et intégrale, elle est donc finie presque partout.
\end{proof}

\paragraph{Conclusion} En excluant d'abord les points où le taux d'accroissement
n'a pas de limite, puis ceux où la limite est $+\infty$, on ne s'est privé que
d'en semble de mesure nulle, donc : $f$ est dérivable presque partout !

Le théorème se généralise évidemment à un intervalle de définition quelconques
(par union dénombrable de segments compacts), et il est tout aussi clair que
l'énoncé s'applique aussi pour $f$ décroissante. Par contre, attention, il n'est
pas facile de généraliser à $f$ discontinue !

\paragraph{À propos de l'hypothèse de continuité} Cette hypothèse était présente
dans la première démonstration de ce théorème par Lebesgue en 1904.

Quand $f$ est discontinue, on pourrait vouloir se restreindre à ses intervalles
de continuité pour se ramener au cas qu'on a prouvé. Un contre-exemple à cette
stratégie naïve est donné par la fonction $f : x \mapsto \sum_{n \in \N} 2^{-n}
\Indic_{[x \geq q_n]}$ où $(q_n)_{n \in \N}$ est une énumération des rationnels.
Il faut donc traiter le cas de ce genre de \emph{fonctions de saut} (et en fait,
toute fonction monotone est la somme d'une fonction continue et d'une fonction
de saut, puisqu'une fonction monotone a un nombre au plus dénombrable de points
de discontinuité).

On trouvera chez Royden une preuve directe du cas général ($f$ potentiellement
discontinue) utilisant le lemme de recouvrement de Vitali. Dans ce livre, ce
théorème est le premier d'une séquence qui aboutit à montrer que pour les
fonctions d'une variable réelle la dérivation est bien l'opération inverse de
l'intégrale de Lebesgue (presque partout, évidemment).

\paragraph{Dernière remarque culturelle}

En utilisant la majoration de la variation totale et le lemme des rayons du
soleil, on peut aussi démontrer (et ça a quasiment déjà été fait !) que
\[ \mu\left( \left\{ x \in ]0,1[ \mid D^+f(x) \geq \beta \right\} \right)
  \leq \frac{f(1)-f(0)}{\beta} \]
ce qui aurait pu permettre de traiter la partie finitude (exercice pour la
lectrice). Ce résultat est à comparer avec le suivant, utilisé pour démontrer
d'autres théorèmes de dérivation presque partout dans le même esprit (cf. par
exemple \emph{An introduction to measure theory} de Terence Tao) :
\begin{theorem}[Inégalité maximale de Hardy--Littlewood]
  Soit $f \in L^1(\R)$, et soit $\beta > 0$. Alors
  \[ \mu\left( \left\{ x \in \R \;\middle|\; \sup_{h > 0} \frac{1}{h} \int_x^{x+h}
        |f(t)|\,dt \geq \beta \right\} \right)
    \leq \frac{1}{\beta} \int_\R |f(t)|\,dt \]
\end{theorem}

À ce propos, le lecteur est invité à se pencher sur l'énoncé d'un exercice qui
m'a été posé au concours d'entrée des ENS, en 2012 :
\begin{enumerate}
\item Montrer que tout ouvert de $\mathbb{R}$ est une réunion disjointe dénombrable d'intervalles ouverts.
\item On prend une fonction continue sur un intervalle de $\mathbb{R}$ et on desssine son graphe. On fait arriver de la droite ($x = +\infty$) un faisceau lumineux de rayons parallèles à l'axe des abscisses. Ce faisceau éclaire certaines parties du graphe, le reste étant dans l'ombre (on considérera qu'un rayon arrivant tangent en un extrémum n'est pas bloqué). Montrer que l'ensemble des abscisses des points à l'ombre est une union disjointe d'intervalles ouverts.
\item Soit $(u_n)_{n \in \mathbb{Z}} \in \mathbb{R}^{\mathbb{Z}}$ une suite \emph{sommable}. On pose $u^*_N = \displaystyle \sup_{n \in \mathbb{N}^*} \frac{1}{n} \sum_{k=0}^{n-1} u_{N+k}$.\\ Montrer que $\displaystyle \sum_{\underset{u_N^* > 0}{N \in \mathbb{Z}}} u_N \geq 0$.
\end{enumerate}
L'examinateur affirmait que les question (2) et (3) étaient liées. Quatre ans se
sont écoulés avant que je ne comprenne ce lien, en travaillant le développement
ci-dessus… (Il est toutefois possible de résoudre l'exercice sans voir le lien.)
On admirera au passage les contorsions nécessaires pour contourner l'absence de
l'intégrale de Lebesgue au programme des classes préparatoires.

\newpage



\subsection{Lemme de Hoeffding}

Il existe deux versions de ce lemme : une faible qui s'applique aux variables
aléatoires $X$ avec $-c \leq X \leq c$ p.s., et une autre plus forte qui suppose
que $a \leq X \leq b$ p.s. La première se démontre simplement par des inégalités
de convexité. La seconde admet une preuve plus compliquée, qui présente
l'intérêt de se recaser dans la leçon sur les intégrales à paramètre. Dans les
deux cas, on peut en déduire une inégalité de concentration, \emph{l'inégalité
  de Hoeffding}.

Rappelons que pour $X$ une variable aléatoire réelle, la \emph{fonction
  génératrice des moments} et la \emph{fonction génératrice des cumulants} sont
définies respectivement par
\[ M_X(t) = \E\left[ e^{tX} \right] \quad \text{et} \quad K_X(t) = \ln M_X(t) \]
Si $X$ est bornée p.s., ces fonctions sont définies et même $\Cf^\infty$ sur
$\R$. De plus, $X$ admet des moments à tout ordre, et $M_X$ est la série
génératrice exponentielle des moments, d'où le nom. De même, on appelle
\emph{cumulants} les quantités $\kappa_n = K_X^{(n)}(0)$.

\begin{proposition}
  $\kappa_1 = \E[X]$ et $\kappa_2 = \Var(X)$.
\end{proposition}
\begin{proof}
  Calculer en utilisant la dérivation sous le signe $\int$ (ou plutôt $\E$).
\end{proof}

Fixons à partir de maintenant $a < b$, et $X$ une v.a. réelle avec $a \leq X
\leq b$ presque sûrement.

\begin{proposition}[Inégalité de Popoviciu]
  $\displaystyle \Var(X) \leq \frac{(b-a)^2}{4}$.
\end{proposition}
\begin{proof}
  $\E[(X - \mu)^2]$ atteint son minimum $\Var(X)$ en $\mu = \E[X]$ ; prendre
  $\mu = (a+b)/2$ pour obtenir l'inégalité.
\end{proof}

\begin{lemma}[Hoeffding]
  $K_X(t) \leq t\E[X] + t^2(b-a)^2/8$.
\end{lemma}
\begin{proof}
  Fixons $t \in \R$. On peut voir que $K_X(t+s) = K_X(t) + K_{Y_t}(s)$ où $Y_t$
  est telle que
  \[ \P_{Y_t} \ll \P_X, \quad \frac{\mathrm{d}\P_{Y_t}}{\mathrm{d}\P_X} =
    \frac{e^{tX}}{\E\left[ e^{tX} \right]}\]
  ($\P_{Y_t}, \P_X$ étant les mesures images sur $\R$). En particulier $a \leq
  Y_t \leq b$ p.s. En dérivant par rapport à $s$ deux fois,
  \[ K_X''(t) = K_{Y_t}''(0) = \Var(Y_t) \leq \frac{(b-a)^2}{4} \]
  On considère maintenant $t$ variable et on intègre deux fois ; l'énoncé du
  lemme en découle immédiatement.
\end{proof}

On complète le développement en présentant l'application à l'inégalité de
Hoeffding.

\newpage

\subsection{Polynômes de Bernstein}

Référence : Zuily--Quéffélec, \emph{Éléments d'analyse pour l'agrégation}.

\begin{theorem}[Bernstein]
  Soit $f \in \Cf([0,1], \R)$.
  
  Pour $n \in \N$ et $x \in \R$, on pose $B_n(x) = \E[f(X_{n,x})]$ où $X_{n,x}
  \sim \textnormal{Binom}(n,x)$. Alors :
  \begin{enumerate}
  \item Pour tout $n \in \N$, $B_n : [0,1] \to \R$ est une fonction polynomiale.
    ($B_n$ est appelé le $n$-ième polynôme de Bernstein de $f$.)
  \item $\|B_n - f\|_\infty \underset{n \to \infty}{=} O\left(
      \omega_f(n^{-1/2}) \right)$.
  \end{enumerate}
\end{theorem}

On rappelle que $\omega_f$ est le \emph{module de continuité uniforme} de $f$ :
\[ \omega_f(h) = \sup_{|x-y| \leq h} |f(x) - f(y)| \]

\begin{corollary}[Théorème de Weierstrass]
  Les fonctions polynomiales sont denses dans $\Cf([0,1])$.
\end{corollary}

Notons qu'il est utile de connaître le théorème de Stone-Weierstrass plus
général pour répondre aux questions sur le développement.

\begin{proof}[Preuve du corollaire]
  Soit $f \in \Cf([0,1])$. D'après le théorème de Heine, $f$ est uniformément
  continue, ce qui est équivalent à dire que $\omega_f(x) \to 0$ quand $x \to
  0^+$. Ainsi, $\|B_n - f\| \to 0$ quand $n \to +\infty$.
\end{proof}

\begin{lemma}
  Pour tous $\lambda, h > 0$,
  $\omega_f(\lambda h) \leq \lceil \lambda \rceil \omega_f(h)$.
\end{lemma}
\begin{proof}[Preuve du lemme]
  On montre d'abord que $\omega_f$ est croissante (c'est évident) et
  sous-additive (par inégalité triangulaire), puis le lemme en découle
  facilement.
\end{proof}

\begin{proof}[Preuve du théorème]
  La polynomialité de $B_n$ est immédiate en écrivant la formule de l'espérance.

  Fixons $x \in [0,1]$. On a
  \[ |B_n(x) - f(x)| = \left| \E\left[ f(X_{n,x}) - f(x) \right] \right|
    \leq \E\left[ \left| f(X_{n,x}) - f(x) \right| \right]
    \leq \E[\omega_f(|X_{n,x} - x|)]\]
  puis en utilisant le lemme,
  \[ |B_n(x) - f(x)| \leq \E\left[ \left\lceil \sqrt{n} |X_{n,x} - x| \right\rceil
    \omega_f\left( \frac{1}{\sqrt{n}} \right) \right]
    \leq \omega_f\left( \frac{1}{\sqrt{n}} \right)
    \E\left[ \sqrt{n} |X_{n,x} - x| + 1 \right]\]

  Par inégalité de Cauchy-Schwarz (ou convexité de $t \mapsto t^2$, au choix),
  \[  \E\left[ \sqrt{n} |X_{n,x} - x| \right]^2 \leq
    \E\left[ n (X_{n,x} - x)^2 \right] = n \Var(X_{n,x}) = x(1-x) \leq \frac{1}{4} \]
  (on rappelle que $X_{n,x} \sim \textnormal{Binom}(n,x)$, et on connaît la
  variance d'une loi binomiale).

  Finalement, on a :
  \[ \forall x \in [0,1],\quad |B_n(x) - f(x)|
    \leq \frac{3}{2}  \omega_f\left( \frac{1}{\sqrt{n}} \right) \]
  et le majorant étant indépendant de $x$, c'est fini.
\end{proof}

\begin{proposition}
  La majoration de la vitesse de convergence est optimale à un facteur près.
\end{proposition}
Zuily--Quéffelec fait ça avec l'inégalité de Khintchine, mais on peut aussi
invoquer le théorème central limite (qui est plus difficile, mais plus connu)~;
en fait, on n'a besoin que de la version pour les variables de Bernouilli,
appelée \enquote{théorème de Moivre--Laplace} et qui peut être prouvée sans
fonctions caractéristiques.
\begin{proof}
  Soit $f : x \in [0,1] \mapsto |x - 1/2|$, on va montrer que $|f(1/2) -
  B_n(1/2)| = \Omega(\omega_f(n^{-1/2}))$. Remarquons d'abord que $f$ est
  1-lipschitzienne, donc $\omega_f(h) \leq h$.

  Pour cela, posons $X_n = X_{n,1/2}$.
  Le TCL nous dit que $2\sqrt{n}(X_n - 1/2)
  \xrightarrow{\textnormal{loi}} \mathcal{N}(0,1)$. Donc
  \[ \sqrt{n} \left| B_n\left( \frac{1}{2} \right) - f\left( \frac{1}{2} \right)
    \right| = \E\left[ \sqrt{n} \left| X_n - \frac{1}{2} \right| \right]
    \xrightarrow[n \to +\infty]{} \frac{1}{2} \E[|Y|] > 0 \quad
    \textnormal{avec}\; Y \sim \mathcal{N}(0,1).
  \]
\end{proof}

\newpage


\subsection{Récurrence d'une marche aléatoire via séries de Fourier}

Un théorème célèbre, avec une preuve étrangement moins célèbre et pourtant
stylée, que j'ai découverte dans le cours de processus aléatoires de Josselin
Garnier et qui est également trouvable sur Internet.

\begin{theorem}[Pólya]
  La marche aléatoire symétrique sur $\Z^d$ est \emph{récurrente} si et
  seulement si $d \leq 2$.
\end{theorem}

Précisons ce que signifie \enquote{récurrente}. Cette marche aléatoire est
définie par la suite de v.a. $S_n = X_1 + \ldots + X_n$ où les $(X_i)$ sont iid
uniformes parmi $\{\pm e_1, \ldots, \pm e_d\}$. Soit $N$ le nombre de passages à
l'origine : $N = \mathrm{Card}\left\{n \in \N \mid S_n = 0\right\}$. On dit que
la marche est récurrente quand $\E[N] = +\infty$.


\paragraph{Premières remarques} On a $\displaystyle \E[N] = \E\left[
  \sum_{n=0}^\infty \Indic_{\{S_n = 0\}} \right] =
\sum_{n=0}^\infty \P(S_n = 0)$.\\
On peut ne garder que les termes pairs dans cette somme. En effet, pour tout $n
\in \N$, on établit facilement que $\sum_{i=1}^d \langle S_n, e_i \rangle \equiv
n \mod 2$, ce qui entraîne que $S_n \neq 0$ quand $n$ est impair.\\
On cherche donc une expression pour $\P(S_n = 0)$, $n = 2m$ avec $m \in \N$.

\paragraph{Utilisation de la fonction caractéristique}

Si $\varphi$ est la fonction caractéristique de $X_1$, alors celle de $S_n$
est égale à $\varphi^n$ (somme de v.a. indépendantes).

\[ \forall x \in \R^d,\quad \varphi(x) = \E\left[ e^{i \langle x, X_1 \rangle}
  \right]
  = \sum_{j=1}^d \left( \frac{1}{2d}e^{ix_j} + \frac{1}{2d}e^{-ix_j}\right)
  = \frac{1}{d} \sum_{j=1}^d \cos(x_i) \]

Pour en déduire les probabilités recherchées on utilise :
\begin{lemma} Soit $k = (k_1, \ldots, k_d) \in \Z^d$. On a la formule des
  coefficients de Fourier :
  \[ \displaystyle \P(S_n = k) = \frac{1}{(2\pi)^d} \int_{[-\pi,\pi]^d}
    \varphi_n(x)e^{-i\langle k,x \rangle} \]
\end{lemma}
En fait, $\varphi_n$ est une série de Fourier $d$-dimensionnelle normalement
convergente dont les coefficients sont les $\P(S_n = (k_1, \ldots, k_d))$. Ce
n'est pas anecdotique : la preuve qu'on est en train de dérouler repose
fondamentalement sur un passage au domaine de Fourier\footnote{Ici les
  \enquote{fréquences} (le dual) sont dans le tore et le \enquote{temps} (le
  primal) est discret ; on est habitués à l'autre sens, mais c'est juste
  l'involutivité de la dualité de Pontriaguine. Les anglophones parlent de
  \enquote{discrete-time Fourier transform}, à ne pas confondre avec la
  transformée de Fourier discrète d'un signal \emph{fini}.} pour convertir une
convolution de mesures en produit de fonctions, c'est complètement dans l'esprit
de l'analyse de Fourier. Mais ici, pas besoin de toute cette théorie, il suffit
de calculer :
\begin{proof}[Preuve du lemme]
  \[ \int_{[-\pi,\pi]^d} \varphi_n(x)e^{-i\langle k,x \rangle} dx =
    \int_{[-\pi,\pi]^d} \E\left[ e^{i\langle S_n, x \rangle} e^{-i\langle k,x
        \rangle}\right] dx
    = \E\left[ \int_{[-\pi,\pi]^d} e^{i\langle S_n - k, x \rangle} dx \right]
    = \E\left[ (2\pi)^d \Indic_{\{S_n = k\}} \right] \]
  où on a pu intervenir $\int$ et $\E$ grâce au théorème de Fubini appliqué à
  une fonction bornée, donc intégrable sur un produit d'espaces de mesure finie.
\end{proof}
Ainsi, en se souvenant que $\varphi$ est à valeurs réelles, ses puissances
paires sont positives (!), et
\[ (2\pi)^d \E[N] = \sum_{m=0}^{\infty} \int_{[-\pi,\pi]^d} \varphi(x)^{2m} dx
  = \int_{[-\pi,\pi]^d} \frac{dx}{1 - \varphi(x)^2}\]
par convergence monotone, l'expression finale étant valable parce que
$|\varphi(x)| < 1$ presque partout. (Si on avait gardé les termes impairs (qui
peuvent être négatifs), comme c'est le cas dans certaines références,
l'interversion série-intégrale aurait été plus dure à justifier ; il faut une
astuce dans ce cas…)

\paragraph{Étude d'une intégrale et conclusion} Il s'agit donc de savoir si
cette intégrale est finie ou non. $1/(1-\varphi^2)$ part à l'infini exactement
aux points où il y a un problème de convergence à savoir $|\varphi| = 1$ , soit
$(0,\ldots,0)$ ainsi que les $2^d$ points $(\pm \pi, \ldots, \pm \pi)$ ; et elle
est continue en-dehors de ces points. Ces derniers points sont des anti-périodes
de $\varphi$, donc des périodes de $1/(1-\varphi^2)$ : il suffit donc d'étudier
l'intégrabilité en 0, sur un voisinage $B(0,\varepsilon)$ où $0 < \varepsilon <
\pi$.

Pour $x \to 0$,
\[ 1 - \varphi(x) = \frac{1}{d} \sum_{j=1}^d (1 - \cos x_j) \sim
  -\frac{1}{d}(x_1^2 + \ldots + x_d^2) \] d'où
\[\frac{1}{1 - \varphi(x)^2} = \frac{1}{(1 + \varphi(x))(1 - \varphi(x))} \sim
  \frac{2d}{\|x\|^2} \]
Finalement, reste à étudier l'intégrabilité de $\|x\|^{-2}$. Un passage en
coordonnées polaires et le théorème de Tonelli donnent
\[ \int_{B(0,\varepsilon)} \|x\|^{-2}\,dx = \int_{]0,\varepsilon[ \times S^{d-1}}
  r^{-2} \cdot r^{d-1}\,dr\,d\omega = \Vol(S^{d-1}) \int_0^\varepsilon
  r^{d-3}\,dr \]
Ce qui est infini exactement quand $d < 3$, CQFD.

Petit détail : le cas $d=1$ semble nécessiter un traitement particulier,
mais le calcul est bien légal à condition de considérer que $S^0 = \{\pm 1\}$
(c'est bien la convention habituelle) et de prendre pour mesure 0-dimensionnelle
la mesure de comptage. Les \enquote{coordonnées polaires} correspondent alors à
la décomposition en signe et valeur absolue, qui est bien un
difféomorphisme entre $\R^*$ et $S^0 \times \R_+^*$ !

\paragraph{Si le temps permet…} On expliquera pourquoi dans une chaîne de Markov
irréductible, un état est récurrent si et seulement si tous le sont, et que dans
ce cas, tous les états sont presque sûrement atteints. Ainsi, on a montré qu'un
ivrogne qui se déplace dans le plan peut être (presque) sûr de rentrer chez lui.

\newpage

\subsection{Gaussiennes, inversion de Fourier et théorème de continuité de Lévy}

Notre but est de montrer, dans le cas $d = 1$ (mais toutes les preuves se
généralisent sans mal à $d$ quelconque) :

\begin{theorem}[Inversion de Fourier]
  Soit $f \in L^1(\R^d)$. Si $\hat{f} \in L^1(\R^d)$, on a pour presque
  tout $x \in \R^d$ :
\[ f(x) = \frac{1}{(2\pi)^d} \int_\R \hat{f}(\xi) e^{i\xi \cdot x} \,d\xi =
  \hat{\hat{f}}(-x). \]
\end{theorem}

En soi, la démonstration est un peu courte, donc on combine généralement ça avec
le calcul de la transformée de Fourier d'une gaussienne (résultat utilisé dans
la preuve). C'est utile pour faire rentrer le développement dans la leçon
\enquote{Illustrer par des exemples quelques méthodes de calcul d'intégrales …},
mais pour les autres circonstances, on propose ici un autre complément (suggéré
par N. Clozeau) : appliquer la formule d'inversion pour prouver le théorème de
continuité de Lévy (sur une variable aléatoire dans $\R$ quelconque, pas
forcément à densité !).

\paragraph{Préliminaires sur les gaussiennes}
On définit la gaussienne d'écart-type $\sigma > 0$ comme $g_\sigma : x \mapsto
(\sigma\sqrt{2\pi})^{-1}\exp(-x^2/2\sigma^2)$. On a $g_\sigma \in \S(\R)$, donc
elle est intégrable tout comme toutes ses dérivées.

\begin{lemma}
  Pour tout $f \in L^1(\R)$,
  $g_\sigma * f \xrightarrow[\sigma \to 0]{} f$ dans $L^1(\R)$.
\end{lemma}
\begin{proof}
  Admis. Cette propriété découle du fait que les gaussiennes sont des
  approximations de l'unité.
\end{proof}

Attention, convergence $L^p$ n'entraîne pas convergence presque partout ! Par
contre, d'une suite qui converge dans $L^p$, on peut extraire une sous-suite qui
converge vers la même limite presque partout, d'où :
\begin{corollary}
  Il existe une suite $\sigma_n$ décroissante tendant vers 0 telle que
  $g_{\sigma_n} * f \rightarrow f$ p.p.
\end{corollary}
(Rappel : toute série absolument convergente dans $L^p$ converge p.p., ça
sert dans la preuve de complétude.)

\begin{proposition}[Transformée de Fourier des gaussiennes]
  $\displaystyle \widehat{g_\sigma}(\xi) =
  \exp\left(- \frac{\sigma^2 \xi^2}{2} \right) =
  \frac{\sqrt{2\pi}}{\sigma} g_{1/\sigma}(\xi)$.
\end{proposition}
\begin{proof}
  Il y en a plein, choisissez celle qui vous plaît. Une façon simple est
  d'utiliser le théorème de dérivation sous le signe intégral pour montrer que
  c'est une solution de l'équation différentielle $y' = -\sigma^2xy $. Comme
  $\widehat{g_\sigma}(0) = 1$ on peut parachuter la solution $\sqrt{2\pi}/\sigma
  \cdot g_{1/\sigma}$, Cauchy-Lipschitz linéaire assurant l'unicité.
\end{proof}

En itérant deux fois, on a bien $\widehat{\widehat{g_{\sigma}}} = 2\pi g_\sigma$
(le signe moins a disparu car $g_\sigma$ est paire) : la formule d'inversion de
Fourier est vérifiée par les gaussiennes.

\paragraph{Inversion de Fourier, cas général}

Soit $f \in L^1(\R)$ telle que $\hat{f} \in L^1(\R)$. On pose
\[ F_\sigma(x) = \int_\R \widehat{g_\sigma}(\xi)\hat{f}(\xi)e^{i\xi x} d\xi \]
Un calcul rapide (on écrit la formule intégrale pour $\hat{f}$, puis on utilise
Fubini) entraîne que
\[ F_\sigma(x) = \widehat{\widehat{g_\sigma}} * f(\xi) \]

On observe que $\widehat{g_\sigma} \longrightarrow 1$ ponctuellement quand
$\sigma \to 0$ ; en passant à la limite sur la suite $\sigma_n$ du lemme
préliminaire, on trouve l'égalité presque partout de la formule d'inversion de
Fourier. Pour ce faire on a besoin crucialement que $\hat{f} \in L^1(\R)$ pour
que le théorème de convergence dominée s'applique.

\paragraph{Application : théorème de continuité de Lévy} Rappelons tout d'abord
que pour vérifier une convergence en loi, il suffit de tester sur un ensemble de
fonctions dont l'adhérence contient $\Cf_c(\R)$, espace de fonctions continues
à support compact, alors que la définition de cette convergence fait intervenir
les fonctions continues bornées. C'est moralement un argument de densité mais
attention, $\Cf_c(\R)$ n'est pas dense dans $\Cf_b(\R)$ pour la norme uniforme !

\begin{theorem}[Lévy]
  Soit $X$ une variable aléatoire réelle de fonction caractéristique $\varphi$, et
  $(X_n)_{n \in \N}$ une suite de v.a. réelles dont on notera les fonctions
  caractéristiques $\varphi_n$ pour $n \in \N$. Alors $X_n \rightarrow X$ en loi si
  et seulement si $\varphi_n \rightarrow \varphi$ simplement.
\end{theorem}
\begin{proof}
  Le sens direct est évident, prouvons la réciproque. Soit $f \in
  \Cf^\infty_c(\R)$ (qui est bien dense dans $\Cf_c(\R)$), alors en particulier
  $f \in \S(\R)$ donc $f$ et $\hat{f}$ sont intégrables. Par conséquent, on peut
  écrire la formule d'inversion de Fourier sur $f$, puis prendre une espérance :
  \[ \forall n \in \N,\; \E[ f(X_n) ] = 
    \E\left[ \frac{1}{2\pi} \int_\R \hat{f}(\xi) e^{i\xi X_n}\,d\xi \right] =
    \frac{1}{2\pi} \int_\R \E\left[ \hat{f}(\xi) e^{i\xi X_n} \right] d\xi =
    \frac{1}{2\pi} \int_\R \hat{f}(\xi) \varphi_n(\xi)\, d\xi
  \]
  où l'on a interverti espérance et intégrale par le théorème de Fubini (à
  justifier). (Au fond, on n'a fait que constater que la transformation de
  Fourier préserve le produit scalaire.) On peut faire le même calcul pour
  $\E[f(X)]$, puis comme $|\varphi_n| \leq 1$ et $\hat{f} \in L^1(\R)$, le théorème
  de convergence dominée et notre  hypothèse de convergence des $\varphi_n$ nous
  donnent
  \[ \E[ f(X_n) ] \xrightarrow[n \to \infty]{}
    \frac{1}{2\pi} \int_\R \hat{f}(\xi) \varphi(\xi)\, d\xi = \E[f(X)].  \]
\end{proof}

\newpage

\subsection{Formule de Poisson et formule d'inversion de la fonction thêta}
\label{poisson}

On commence par un résultat qui lie séries de Fourier et transformée de Fourier :
$2\pi$-périodiser une fonction revient à garder ses pulsations entières. (Existe
aussi en version \enquote{1-périodiser = garder les fréquences entières}.)

\begin{theorem}[Formule sommatoire de Poisson]
  $\displaystyle \forall f \in \S(\R),\; \forall t \in \R,\; \sum_{n \in \Z} f(t
  + 2\pi n) = \frac{1}{2\pi} \sum_{n \in \Z} \hat{f}(n)e^{int}$.
\end{theorem}

\begin{remark}
  Cette égalité se lit aussi comme la transformée de Fourier du peigne de Dirac.
\end{remark}

\begin{proof}
  On vérifie sans difficulté que la série à gauche est normalement convergente
  sur tout compact, et qu'il en va de même de sa dérivée. Elle définit donc une
  fonction de $\Cf^1(R/2\pi\Z)$ ; celle-ci est donc égale à sa série de Fourier.

  Il suffit ensuite de calculer les coefficients de Fourier, une interversion
  série-intégrale (permise par la convergence normale) faisant apparaître la
  transformée de Fourier de $f$.
\end{proof}

Voici maintenant une application classique à la \emph{fonction $\theta$ de
  Jacobi}. On peut notamment en déduire l'équation fonctionnelle de la fonction
$\zeta$ de Riemann ; cf. le développement suivant pour une autre conséquence
surprenante.

\begin{theorem}
  Soit $\theta : x \mapsto \sum_{n \in \Z} e^{-\pi n^2 x}$.
  Alors $\theta(1/x) = \sqrt{x}\theta(x)$ pour tout $x \in \R_+^*$.
\end{theorem}
\begin{remark}
  La fonction $\theta$ est analytique sur le demi-plan $\{\Re(z) > 0\}
  \subset \C$, et l'identité s'étend par unicité du prolongement analytique à ce
  demi-plan, où il existe une unique détermination de la racine carrée
  coïncidant avec celle sur $\R^*_+$.
\end{remark}

La preuve fera intervenir les gaussiennes $g_\sigma : t \mapsto
(\sigma\sqrt{2\pi})^{-1} \exp(-t/2\sigma^2)$, et on utilisera (cf. développement
\enquote{inversion de Fourier}) :
\begin{proposition}[Transformée de Fourier d'une gaussienne]
  $\displaystyle \widehat{g_\sigma}(\omega) = \exp\left(- \frac{\sigma^2
      \omega^2}{2} \right)$. % $ = \frac{\sqrt{2\pi}}{\sigma} g_{1/\sigma}(\xi)$.
\end{proposition}

\begin{proof}[Preuve de l'équation fonctionnelle]
  Fixons $x \in \R_+^*$.
  \[ \theta(x) = \sum_{n \in \Z} \sigma(x)\sqrt{2\pi}
    \cdot g_{\sigma(x)}(2\pi n) \quad \text{où} \quad
    \sigma(x)^2 = \frac{2\pi}{x}.
  \]
  $g_{\sigma(x)}$ étant dans $\S(\R)$, la formule de Poisson peut s'appliquer :
  \[ \theta(x) =
    \frac{\sigma(x)\sqrt{2\pi}}{2\pi} \sum_{n \in \Z}
    \widehat{g_{\sigma(x)}}(n) =
    \frac{\sigma(x)}{\sqrt{2\pi}} \sum_{n \in \Z}
    \exp\left(-\frac{\sigma(x)^2 n^2}{2} \right) =
    \frac{1}{\sqrt{x}} \sum_{n \in \Z} \exp\left( -\frac{\pi n^2}{x} \right)
    = \frac{\theta(1/x)}{\sqrt{x}}.
  \]
\end{proof}

\begin{application}[Un développement asymptotique]
  $\displaystyle \sum_{n \in \Z} x^{n^2} \underset{x \to 1^-}{\sim}
  \sqrt{\frac{\pi}{- \ln x}}$
\end{application}
\begin{proof}
  On a une série entière de rayon de convergence 1, donc elle est bien définie
  au voisinage à droite de 1. Écrivons l'équation fonctionnelle pour $x \in
  ]0,1[$
  \[ \sum_{n \in \Z} x^{n^2} = \theta\left( \frac{- \ln x}{\pi} \right) =
      \sqrt{\frac{\pi}{- \ln x}} \theta\left( \frac{\pi}{- \ln x} \right)
  \]
  Il suffit de vérifier que $\displaystyle \theta(u) = 1 + 2 \sum_{n=1}^\infty
  e^{-\pi n^2 u}\to 1$ quand $u \to +\infty$ ($u = -\pi/\ln x$) et c'est bon…
\end{proof}

\newpage

\subsection{Équivalent asymptotique de la fonction thêta et sommes de Gauss}
\label{theta}

…ou comment caser un morceau de preuve de la réciprocité quadratique (!) dans
des leçons d'analyse. Référence livresque : Richard Bellman\footnote{Un analyste
  qui a aussi eu une carrière fructueuse de mathématicien appliqué : il est
  l'inventeur de la \emph{programmation dynamique}, qui est au programme de
  l'agrég option D en algorithmique, mais intervient aussi en recherche
  opérationnelle et théorie du contrôle.}, \emph{A brief introduction to theta
  functions}. Voir aussi l'article d'Anders Karlsson, \emph{Applications of heat
  kernels on abelian groups: $\zeta(2n)$, quadratic reciprocity, Bessel
  integrals}, qui raconte également d'autres applications fort jolies de cette
fameuse fonction thêta. Cependant, aucun des deux ne fournit de preuve
rigoureuse complète.\\

On renvoie au développement précédent (\nameref{poisson}) pour la définition de
la fonction $\theta$ de Jacobi et son équation fonctionnelle. Dans tout ce qui
suit, on fixe $p, q \in \N^*$ premiers entre eux. La \emph{somme de Gauss}
associée est :
\[S(p,q) = \sum_{k \in \Z/q\Z} \exp(-i\pi k^2 p/q) \]

On va montrer le résultat suivant, à partir duquel la loi de réciprocité
quadratique (!) se déduit :

\begin{theorem}[Réciprocité des sommes de Gauss]
  $\sqrt{p}S(p,q) = e^{-i\pi/4}\sqrt{q}\overline{S(q,p)}$, i.e.
  \[ \frac{1}{\sqrt{q}} \sum_{k \in \Z/q\Z}
    \exp\left(\frac{-i\pi k^2 p}{q}\right) =
    \ \frac{e^{-i\pi/4}}{\sqrt{p}} \sum_{k \in \Z/p\Z}
    \exp\left(\frac{i\pi k^2 q}{p}\right) \]
\end{theorem}

Cette identité exacte peut en fait être obtenue à partir d'un équivalent
asymptotique de $\theta(x + ip/q)$ pour $x \to 0^+$.

\begin{lemma} Soit $k \in \N^*$. Quand $x \to 0^+$,
  $\displaystyle \sum_{l = 0}^{+\infty} \exp(-\pi(k+lq)^2x)
  \sim \frac{1}{2q\sqrt{x}}$.
\end{lemma}

\begin{proof}
  La fonction $f : t \mapsto \exp(-\pi(k+tq)^2x)$ est décroissante et intégrable
  sur $\R_+$, donc par comparaison série-intégrale,
 \[ \sum_{l \geq 1} f(l) \leq \int_0^{+\infty} f(t)\,dt \leq
   \sum_{l \geq 0} f(l) \quad \text{soit} \quad
   0 \leq \sum_{l \geq 0} f(l) - \int_0^{+\infty} f(t)\,dt \leq f(0) =
   e^{-\pi k^2 x} \leq 1
 \]
 Calculons l'intégrale :
 \[ \int_0^{+\infty} \exp(-\pi(k+tq)^2x)\,dt =
   \frac{1}{q\sqrt{\pi x}} \int_{k\sqrt{\pi x}}^{+\infty} e^{-u^2}\,du
    \underset{x \to 0^+}{\sim} \frac{1}{2q\sqrt{x}}
   \qquad
  (u = \sqrt{\pi x}(k + tq))
\]
\end{proof}

\begin{proposition}
  Quand $x \to 0^+$,
  $\displaystyle \theta\left( x + i\frac{p}{q} \right)
  \sim \frac{S(p,q)}{q\sqrt{x}}$.
\end{proposition}

\begin{proof}
  Par une interversion de sommes, justifiée par la sommabilité
  de la famille considérée, on obtient facilement que
  \[ \sum_{n \in \N^*} \exp\left(-\pi n^2 \left( x + i\frac{p}{q}  \right)\right)
    = \sum_{k = 1}^q \left( \sum_{l \in \N} \exp(-\pi(k+lq)^2x) \right)
    \exp\left(\frac{-i\pi k^2 p}{q} \right)
  \]
  Grâce au lemme, on sait que les sommes intérieures sont équivalentes à
  $1/2q\sqrt{x}$, donc
\[ \theta\left( x + i\frac{p}{q} \right) = 1 + 2 \sum_{n \in \N^*}
  \exp\left(-\pi n^2 \left( x + i\frac{p}{q} \right)\right)
      \underset{x \to 0^+}{\sim} \frac{S(p,q)}{q\sqrt{x}}
\]
\end{proof}

Maintenant, écrivons l'équation fonctionnelle de $\theta$ :
  \[ \theta\left( \frac{1}{x + ip/q} \right) =
    \sqrt{x + i\frac{p}{q}} \times \theta\left( x + i\frac{p}{q} \right)
    \underset{x \to 0^+}{\sim} e^{i\pi/4} \sqrt{\frac{p}{q}}
    \times \frac{S(p,q)}{q\sqrt{x}}
  \]
D'autre part, on a
  \[ \frac{1}{x - ip/q} \underset{x \to 0^+}{=}
    x\frac{q^2}{p^2} + i \frac{q}{p} + O(x^2)  \]
\emph{Arnaquons maintenant allègrement} en considérant que notre équivalent
asymptotique, valable quand $z \to ip/q$ en suivant une demi-droite parallèle à
$\R_+$, le reste en suivant un courbe qui finit par être tangente à cette
demi-droite. Alors
\[ \theta\left( \frac{1}{x + ip/q} \right)
  = \overline{\theta\left( \frac{1}{x - ip/q} \right)}
    \underset{x \to 0^+}{\sim} \frac{\overline{S(q,p)}}{p\sqrt{xq^2/p^2}}
  \]
  On voit donc apparaître du $S(q,p)$ ! En simplifiant et en comparant nos deux
  équivalents asymptotiques, on obtient l'identité arithmétique désirée.

Pour que ça marche vraiment, il faudrait étendre le cadre de validité du lemme,
en faisant une comparaison série-intégrale plus subtile, peut-être en utilisant
une formule du genre
  \[ \int_0^{+\infty} f(t)\,dt - \sum_{n=1}^{+\infty} f(n) =
    \int_0^{+\infty} (t - \lfloor t \rfloor)f'(t)\,dt
  \]
  On pourrait dire qu'en fin de compte, on obtient la loi de réciprocité
  quadratique par une comparaison série-intégrale !


\newpage

\subsection{Théorème taubérien fort de Littlewood}
\label{tauber}

Référence : Gourdon, \emph{Analyse}. La preuve astucieuse du Gourdon a été
découverte par Jovan Karamata ; elle figure déjà telle quelle dans un livre de
1939, \emph{The Theory of Functions} de Titchmarsh. On propose ici une variante
de la méthode de Karamata avec moins de découpage d'$\varepsilon$, en utilisant
des sommes de Riemann ainsi qu'en sortant un peu du programme de prépa. (Sans
doute ne suis-je pas la première personne à découvrir cette astuce, mais je n'ai
pas de référence.)

Pour présenter ce développement, il faut un peu de culture sur les théorèmes
abéliens et taubériens, en particulier savoir énoncer le théorème d'Abel radial
ou angulaire, dont le résultat suivant est une réciproque partielle.

\begin{theorem}[Littlewood\footnote{À ne pas confondre avec le théorème
    taubérien de Hardy--Littlewood, qui parle de convergence au sens de Cesàro ! La
    méthode de Karamata pouvant aussi être appliquée pour démontrer ce théorème.}]
  Soit $(a_n) \in \R^n$ telle que $a_n = O(1/n)$ quand $n \to +\infty$. En
  particulier, la série entière $F(x) = \sum_{n \in \N} a_n x^n$ a un rayon de
  convergence au moins 1.

  Alors, si $F(x) \to c \in \R$ quand $x \to 1^-$, alors $\sum_{n \in \N} a_n$
  est convergente et vaut $c$.
\end{theorem}

\begin{example}
  $\displaystyle 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \ldots = \ln 2$.
\end{example}

Il suffit de montrer le théorème pour $c = 0$, quitte à soustraire $c$ à $a_0$.

\paragraph{Stratégie globale} Soit $\Theta$ l'ensemble des fonctions $\theta :
[0,1] \to \R$ telles que
\begin{itemize}
\item $\displaystyle \sum_{n \in \N} a_n \theta(x^n)$ converge pour $0 \leq x < 1$ ;
\item $\displaystyle \sum_{n \in \N} a_n \theta(x^n) \xrightarrow[x \to 1^{-}]{} 0$.
\end{itemize}
Remarquons que $\Theta$ est un espace vectoriel.

On va montrer que $g = \Indic_{[1/2, 1]} \in \Theta$, ce qui établira le
théorème : en effet, dans ce cas,
\[ \forall N \in \N,\; S_N =  \sum_{n = 0}^N a_n = \sum_{n = 0}^{\infty} a_n
  g(x_N^n) \quad \text{avec}\; x_N = 2^{-1/N} \xrightarrow[N \to +\infty]{} 1^- \]
et par composition de limites $S_N \rightarrow 0$ quand $N \to +\infty$.

\begin{lemma}
  Si $P$ est un polynôme s'annulant en $0$, alors $P \in \Theta$.
\end{lemma}
\begin{proof}
  Par linéarité, il suffit de le montrer pour les monômes. Si $\theta(x) = x^k$
  pour $k \geq 1$, alors comme $(x^n)^k = x^{nk} = (x^k)^n$, on a $\sum_{n \in
    \N} a_n f(x^n) = \theta(x^k)$, puis on conclut par composition de limites.
\end{proof}

\begin{lemma}
  Si $f : [0,1] \to \R$ est continue par morceaux (ou plus généralement bornée
  et Riemann-intégrable\footnote{Remarque culturelle : une fonction bornée est
    Riemann-intégrable si et seulement si son ensemble de points de
    discontinuités est de mesure nulle.}), alors
  \[ (1-x) \sum_{n=0}^\infty x^nf(x^n) \xrightarrow[x \to 1^{-}]{} \int_0^1
    f(t)\,dt\]
\end{lemma}
\begin{proof}
  La série se réécrit $\sum_{n=0}^\infty (x^n - x^{n+1})f(x^n)$ et on reconnaît
  donc une somme de Riemann infinie associée à la subdivision $]0,1] =
  \bigcup_{n \in \N} ]x^{n+1},x^n]$ ! Comme la finesse de cette subdivision est
  $1-x$, et tend vers $0$ quand $x \to 1^-$, la somme de Riemann converge vers
  l'intégrale.
  
  Ceci est légèrement une arnaque dans la mesure où le théorème habituel de
  convergence des sommes de Riemann est énoncé pour des subdivisions finies,
  mais on peut montrer qu'il est aussi valable pour des subdivisions
  dénombrables.
\end{proof}

Écrivons maintenant $g(x) = x + x(1-x)h(x)$ où, pour $x < 1/2$, $h(x) =
1/(x-1)$, et pour $x \geq 1/2$, $h(x) = 1/x$. 

Les fonctions polynomiales étant denses dans $L^1([0,1])$ (corollaire du
théorème de Weierstrass), il existe $Q \in \R[X]$ tel que $\|h-Q\|_1 <
\varepsilon$. Posons alors $P(X) = X + X(1-X)Q(X)$ : c'est une approximation de
$g$. (Au passage, tout polynôme $P$ avec $P(0) = 0$ et $P(1) = 1$ s'écrit sous
cette forme, ce qui motive l'introduction de $h$.)

On a alors :
\[ \left| \sum_{n \in \N} a_n g(x^n) - \sum_{n \in \N} a_n P(x^n) \right| \leq
  \sum_{n \in \N} |a_n| \cdot |g - P|(x^n) = \sum_{n \in \N} |a_n| \cdot
  x^n(1-x^n) \cdot |h - Q|(x^n) \]

Comme $1-x^n = (1-x)(1+ \ldots + x^{n-1}) \leq n(1-x)$, $|a_n|(1-x^n) \leq
n|a_n|(1-x)$. Or $n|a_n| = O(1)$ par hypothèse. Donc il existe $M > 0$ tel que
\[ \left| \sum_{n \in \N} a_n g(x^n) - \sum_{n \in \N} a_n P(x^n) \right| \leq
  M (1-x) \sum_{n \in \N} x^n|h - Q|(x^n) \]
Soit :
\[ \left| \sum_{n \in \N} a_n g(x^n) \right| \leq
  \left| \sum_{n \in \N} a_n P(x^n) \right| +
  M (1-x) \sum_{n \in \N} x^n|h - Q|(x^n) \]
En passant à la limite avec les lemmes précédents, sachant que $P \in \Theta$ et
que $|h-Q|$ est continue par morceaux :
\[ \limsup_{x \to 1^-} \left| \sum_{n \in \N} a_n g(x^n) \right| \leq
  0 + M \int_0^1 |h(t) - Q(t)|dt = M \|h-Q\|_1 < M\varepsilon \]
D'où, finalement,
\[ \sum_{n \in \N} a_n g(x^n) \xrightarrow[x \to 1^-]{} 0 \]

\newpage


\subsection{Théorème du point fixe de Brouwer $\Cf^1$}

Soit $n \geq 2$ un entier. On note $D^n$ la boule unité fermée de $\R^n$, et
$S^{n-1} = \partial D^n$ la sphère unité.

\begin{theorem}[Brouwer]
  Toute application $f \in \Cf^1(D^n, D^n)$ admet un point fixe.
\end{theorem}

\begin{remark}
  On en déduit le théorème pour $f \in \Cf^0(D^n, D^n)$.
\end{remark}
\begin{proof}[Preuve de la remarque]
  On approxime $f$ par une suite de fonctions $\Cf^1$ qui convergent
  uniformément ; chacune admet un point fixe, et on extrait une sous-suite
  convergente.

  Attention : il faut s'assurer que les approximations de $f$ soient bien à
  valeur dans $D^n$ et non dans une boule de rayon $1+\varepsilon$.
\end{proof}

S'il existait un contre-exemple $f$ au théorème, alors on pourrait définir la
rétraction
\[ r : x \mapsto \frac{f(x) - x}{\|f(x) - x\|}\]
qui contredirait le lemme suivant :

\begin{lemma}[de non-rétraction $\Cf^1$]
  Il n'existe pas de fonction $r \in \Cf^1(D^n, S^{n-1})$ telle que
  $r\restriction_{S^{n-1}} = \mathrm{id}$.
\end{lemma}
\begin{remark}
En topologie algébrique, on prouve que $D^n$ et $S^{n-1}$ n'ont pas le même type
d'homotopie ; une conséquence est qu'il n'existe pas non plus de rétraction
$\Cf^0$.
\end{remark}

\begin{proof}[Preuve du lemme]
  Par l'absurde, soit $r$ un contre-exemple.  
  Posons, pour $t \in [0,1]$, $f_t = (1-t)\mathrm{id} + tr$, et définissons
  \[ P(t) = \int_{D^n} \det J_{f_t}(x)\,dx = \int_{D^n} \det ((1-t)I +
    tJ_r(x))\,dx \]
  où $J_r(x)$ désigne la matrice jacobienne de $r$ au point $x$.

  La seconde expression montre que la fonction $P$ est \emph{polynomiale}, ce
  qui résulte de la polynomialité du déterminant en développant l'intégrande.
  Comme $r(D^n)$ est d'intérieur vide, $J_r$ s'annule partout (contraposée du
  théorème d'inversion locale) donc $P(1) = 0$.

  Soit maintenant $t \in [0,1/(1+M)[$ où $M = \sup |||J_r|||$. Alors pour tout
  $x \in D^n$, $1-t > tM \geq |||tJ_r|||$, donc $J_{f_t}$ est inversible
  (propriété classique des algèbres de Banach). De plus, si $f_t(x) = f_t(y)$,
  alors
  \[(1-t)(x-y) = t(r(y) - r(x)) \quad \text{d'où} \quad
    (1-t)\|x-y\| = t\|r(x) - r(y)\| \leq tM\|x-y\| \]
  par inégalité des accroissements finis. Ceci contredit $1-t > tM$
  à moins que $\|x-y\| = 0$ : $f$ est donc injective.

  Le théorème d'inversion globale nous dit donc que $f_t$ est un difféomorphisme
  pour des petites valeurs de $t$. Ainsi, la formule de changement de variable
  s'applique immédiatement à la définition de $P(t)$ (ou presque ! modulo une
  valeur absolue qu'on évacue en vérifiant que l'intégrande est toujours
  positive), et donne $P(t) = \Vol(f_t(D^n))$.

  Que peut-on dire sur l'image de $f_t$ ? Tout d'abord, comme $D^n$ est compact,
  $f_t(D^n)$ est compacte, donc fermée dans $D^n$. $f_t(D^n)\setminus S^{n-1}$
  est donc un fermé relatif de la boule ouverte. Souvenons-nous maintenant que
  $r$ est une rétraction : on a donc $f_t(S^{n-1}) = S^{n-1}$, d'où par
  injectivité $f_t(D^n)\setminus S^{n-1} = f_t(D^n \setminus S^{n-1})$. Le
  membre de droite est un ouvert, car $D^n \setminus S^{n-1}$ est un ouvert de
  $\R^n$ et $f_t$ un difféomorphisme local. $f_t(D^n\setminus S^{n-1})$ est donc
  à la fois ouvert et fermé relativement à $D^n \setminus S^{n-1}$, et non vide,
  donc par connexité, on a finalement $f_t(D^n) = D^n$.

  Mais alors, la fonction polynomiale $P$ est constante égale à $\Vol(D^n)$ sur
  $[0,1/(1+M)[$, donc l'est partout. Or $\Vol(D^n) \neq 0$ et $P(1) = 0$,
  contradiction.
\end{proof}

\newpage

\subsection{Théorème d'existence de Cauchy-Peano par méthode de point fixe}

\begin{theorem}[Schauder]
  Soit $K$ une partie compacte convexe non vide d'un espace vectoriel normé.
  Alors toute application continue $f : K \to K$ admet un point fixe.
\end{theorem}

En dimension finie, ce n'est autre que le théorème de point fixe de Brouwer. Le
théorème suivant donne un exemple d'application dans un espace de fonctions de
dimension infinie.

\begin{theorem}[Cauchy--Peano]
  Soit $f : I \times U, \R^d$ où $I$ est un intervalle ouvert contenant 0
  et $U \subseteq \R^d$ ouvert. Soit $y_0 \in U$.
  Si $f$ est \emph{continue}, alors le problème de Cauchy
  \[ y'(t) = f(t, y(t)) \quad y(0) = y_0\]
  admet au moins une solution locale au voisinage de 0.
\end{theorem}

\begin{proof}[Preuve du théorème de Cauchy--Peano]
  Le problème est équivalent à l'équation intégrale
  \[ y(t) = y_0 + \int_0^t f(u,y(u))\,du = \Phi(y)(t) \qquad
    \Phi : y \mapsto \left( t \mapsto y_0 + \int_0^t f(u,y(u))\,du \right) \]
  donc se formule comme recherche d'un point fixe de l'application $\Phi$. Reste
  à savoir sur quel espace cette application est définie…

  Fixons $a > 0$ tel que $[-a,a] \subset I$ et $\bar{B}(y_0,a) \subset U$. Sur
  le compact $[-a,a] \times \bar{B}(y_0,a)$, $|f|$ atteint un maximum $M$. Soit
  $b = \min(a,a/M)$. Posons
  \[ K = \left\{ y \in \Cf([-b,b], \bar{B}(y_0,a)) \; \middle| \; y \;
      \text{$M$-lipschitzienne} \right\}\]

  Il est clair que $K$ est non vide (il contient l'application $t \mapsto y_0$)
  et convexe. $K$ est compact en vertu du théorème d'Ascoli : les fonctions dans
  $K$ sont toutes à valeurs dans un même compact, et équicontinues car elles ont
  la même constante de Lipschitz.

  Pour appliquer le théorème de Schauder, il ne reste qu'à montrer que $\Phi$
  est bien définie et continue sur $K$ et que $\Phi(K) \subseteq K$. Soit $y \in
  K$. Puisque $y$ est à valeurs dans $\bar{B}(y_0,a) \subset U$, $f(t,y(t))$ est
  définie pour tout $t$, ce qui assure que $\Phi(y)$ est définie. Pour $-b \leq
  s < t \leq b$,
  \[ |\Phi(y)(s) - \Phi(y)(t)| \leq \int_s^t |f(u,y(u))|\,du \leq M(t-s)
    \quad \text{car} \quad (u,y(u)) \in [-a,a] \times \bar{B}(y_0,a)
  \]
  d'où le caractère $M$-lipschitzien. De plus, comme $\Phi(y)(0) = y_0$, on en
  déduit que $\Phi(y)$ est à valeurs dans $\bar{B}(y_0,Mb) \subseteq
  \bar{B}(y_0,a)$. Donc $\Phi(y) \in K$.

  Enfin, pour ce qui est de la continuité,
  \[ \|\Phi(y) - \Phi(z)\| \leq \int_{-b}^b |f(u,y(u)) - f(u,z(u))|\,du
    \xrightarrow[z \to y]{} 0
  \]
  par convergence dominée (domination sur $[-b,b]$ par $2M$) ou par un argument
  de convergence uniforme plus long à détailler.
\end{proof}

\begin{proof}[Preuve du théorème de Schauder]
  On va admettre le théorème de Brouwer (cf. développement \enquote{théorème de
    Brouwer $\Cf^1$})) et se ramener au cas de la dimension finie.

  Soit $\varepsilon > 0$. Par précompacité, $K$ peut être recouvert par un
  nombre fini de boules ouvertes de rayon $\varepsilon$ et de centres $x_1,
  \ldots, x_n$. Soit $C = \mathrm{Conv}(x_1, \ldots, x_n) \subseteq K$ ; c'est
  un compact convexe en dimension finie car $C \subset \Vect(x_1,\ldots,x_n)$.
  
  $C$ est ainsi une $\varepsilon$-approximation de $K$ par un convexe compact ;
  approximons maintenant $f$ en posant
  \[g_\varepsilon : x \in C \mapsto
    \frac{\sum_{i=1}^n h_i(f(x))x_i}{\sum_{i=1}^n h_i(x)}
    \quad \text{où} \quad
    h_i(x) = \min(0, \varepsilon - \|x-x_i\|) \geq 0
  \]
  Il est clair que si $g_\varepsilon$ est bien définie (i.e. son dénominateur ne
  s'annule jamais), alors elle est continue.
  
  Soit $x \in K$. Comme $h_i(f(x)) > 0 \Leftrightarrow d(f(x),x_i) <
  \varepsilon$, $g_\varepsilon(x)$ est un barycentre à poids strictement des
  points de $x_1, \ldots, x_n$ à distance $< \varepsilon$ de $f(x)$. De tels
  points existent par la condition de recouvrement. Ainsi :
  \begin{itemize}
  \item $g_\varepsilon(x)$ est bien défini ;
  \item c'est un barycentre des $x_1, \ldots, x_n$, donc $g_\varepsilon(x) \in
    C$ ; 
  \item $\|g_\varepsilon(x) - f(x)\| < \varepsilon$ par convexité de $B(f(x),
    \varepsilon)$.
  \end{itemize}
  Ainsi, $g_\varepsilon \in \Cf(C,C)$. Par le théorème de Brouwer,
  $g_\varepsilon$ admet un point fixe $x_\varepsilon$. La famille
  $(x_\varepsilon)_{\epsilon > 0}$ admet une valeur d'adhérence $x_0 \in K$.
  Montrons que $x_0$ est un point fixe de $f$.

  Pour tout $\varepsilon > 0$, $\|f(x_\varepsilon) - x_\varepsilon\| =
  \|f(x_\varepsilon) - g(x_\varepsilon)\| < \varepsilon$.
  En passant à la limite sur une suite $(\varepsilon_n)_{n \in \N}$ telle que
  $\varepsilon_n \to 0$ et $x_{\varepsilon_n} \to x_0$, on a $\|f(x_0) - x_0\| =
  0$, soit $f(x_0) = x_0$.
\end{proof}

Moralement, on a démontré et utilisé une version plus fine de la propriété
suivante :

\begin{proposition}
  Si $K$ est une partie compacte d'un espace vectoriel normé $E$, alors pour
  tout $\varepsilon > 0$, il existe un sous-espace $F \subset E$ de dimension
  finie tel que $K$ soit compris dans le voisinage d'épaisseur $\varepsilon$ de
  $F$.
\end{proposition}

\newpage

\subsection{Stabilité asymptotique d'un équilibre}
\label{stable}

On prouve ici que pour montrer qu'un point d'équilibre est asymptotiquement
stable, il suffit de linéariser à son voisinage et de vérifier que c'est le cas
du système linéarisé.

\begin{theorem}
  Considérons le système différentiel autonome
  \[ x'(t) = f(x(t)) \qquad f \in \Cf^1(R^n, R^n)  \]
  Supposons que 0 soit un point d'équilibre et que $Df(0)$ ait toutes ses
  valeurs propres de partie réelle strictement négatives. Alors il existe un
  voisinage $V$ de 0 tel que pour tout solution vérifiant $x(0) \in V$, $x(t)
  \to 0$ quand $t \to +\infty$.
\end{theorem}

Ce résultat est semble-t-il dû à Perron. C'est aussi un cas particulier du
\emph{théorème de stabilité de Lyapunov}. La démonstration par construction
d'une fonction de Lyapunov est présentée dans le Rouvière, qui renvoie vers
Coddington \& Levinson, \emph{Theory of Ordinary Differential Equations}, pour
une preuve plus expéditive ; c'est cette dernière qui est présentée ici.

On va utiliser le \emph{lemme de Grönwall} sous la forme intégrale simplifiée
suivante :
\begin{lemma}
  Soient $\alpha \in \Cf^0(I, \R)$ croissante, $\beta \in \Cf^0(I, \R_+)$ et $u
  \in \Cf^0(I)$ ($0 \in I$) vérifiant
  \[ \forall t \geq 0,\; u(t) \leq \alpha(t) + \int_0^t \beta(s)u(s)\,ds.  \]
  Alors pour tout $t \geq 0$,
  \[ u(t) \leq \alpha(t) \exp\left(\int_0^t \beta(s)\,ds\right) \]
\end{lemma}
\begin{proof}
  Admis. L'astuce est de multiplier par le facteur intégrant $e^{-\beta t}$ …
\end{proof}

\paragraph{Stabilité du système linéarisé}

Posons $A = Df(0)$, alors $f(x) = Ax + g(x)$ avec $g(x) = o(|x|)$.

Si $y$ est une solution du système $y'(t) = Ay(t)$, alors $y(t) = \exp(tA)y(0)$
pour tout $t$. On voudrait montrer que $\exp(tA) \to 0$ quand $t \to +\infty$.

En fixant $\mu < 0$ tel que $\mu > \Re(\lambda)$ pour toute valeur propre
$\lambda$ de $A$, on montre que :
\[ \exists M > 0 \mid \forall t \geq 0,\, \|\exp(tA)\| \leq M e^{\mu t} \]
pour une norme d'opérateur induite par une norme quelconque sur $\R^n$.

\paragraph{Extension au système original}

Soit $x$ une solution définie sur un intervalle ouvert $I$, contenant l'origine.
On a $(\exp(-tA)x(t))' = \exp(-tA)g(x(t))$ d'où en intégrant
\[ \exp(-tA)x(t) = x(0) + \int_0^t \exp(-sA)g(x(s))\,ds \]
\[ x(t) = \exp(tA)x(0) + \int_0^t \exp((t-s)A)g(x(s))\,ds \]
En prenant la norme et en appliquant la majoration de l'exponentielle,
\[ x(t) \leq M e^{\mu t}|x(0)| + \int_0^t M e^{\mu(t-s)}|g(x(s))|\,ds \]

Comme $g(x) = o(|x|)$ au voisinage de 0, on peut écrire $|g(x)| = |x|
h(x) / M$ avec $h(x) \geq 0$ et $h(x) = o(1)$, ce qui donne :
\[ \forall t \in I,\; e^{-\mu t}|x(t)| \leq M |x(0)| + 
   \int_0^t e^{-\mu s}|x(s)| \cdot h(x(s)) \,ds \]
Le lemme de Gronwall donne alors
\[ |x(t)| \leq M|x(0)| \exp\left(\int_0^t (h(x(s)) + \mu) \,ds\right) \]
Tant que la trajectoire de $x$ reste suffisamment proche de l'origine, $h(x(s))
+ \mu < 0$ et ainsi $x$ reste bornée… on voit d'où vient la stabilité.

Pour formaliser ça, considérons $U = B(0,r)$ un voisinage de $0$ tel que
$h(U) \subseteq\, ]\mu/2, -\mu/2[$, et $V = B(0,r/M)$. On va établir que les
trajectoires partant de $x(0) \in V$ sont asymptotiquement stables. Posons
\[ T = \inf\, \{ T > 0 \mid \forall t \in [0, T[,\; x(t)\,\text{définie},\;
  x(t) \in U \} \]
Si $x(0) \in V$, alors $T > 0$. Supposons maintenant $T < +\infty$. Pour $t \in
[0,T[$, on a alors $|x(t)| < M|x(0)|$ soit $x(t) \in U$. Par théorème de
sortie de tout compact, $x$ est définie en $T$, et même sur un voisinage à
droite de $T$. Il n'en faut pas beaucoup plus pour montrer que $x$ reste dans
$U$ à droite de $T$, d'où contradiction : par l'absurde, $T = +\infty$.

Ainsi, $x$ est définie sur $\R_+$, et décroit exponentiellement.

\newpage


\subsection{Méthode de Newton pour les polynômes}

Incontournable… Références : mix entre Rouvière (qu'on consultera pour une très
bonne explication des points fixes attractifs / superattractifs / répulsifs) et
Chambert-Loir--Fermigier (pour les polynômes).

Soit $P$ un polynôme unitaire scindé sur $\R$ (par commodité, on va supposer
$\deg P \geq 2$) :
\[ P(x) = (x - \xi_1)^{m_1} \ldots (x - \xi_r)^{m_r}
  \qquad \xi_1 < \ldots < \xi_r \]
On cherche une racine de $P$ par la \emph{méthode de Newton} : on part d'un
point $x_0$ et on calcule par récurrence
\[ x_{n+1} = f(x_n) \qquad f(x) = x - \frac{P(x)}{P'(x)} \]

Le cas particulier des polynômes présente deux intérêts :
\begin{itemize}
\item Si $x_0 > \xi_r$, on tombe toujours sur la racine $\xi_r$. Ainsi, la
  convergence n'est pas seulement locale. C'est vrai généralement pour des
  fonctions convexes.
\item Les hypothèses usuelles de la méthode de Newton comportent que $P'(\xi_r)
  \neq 0$, donc que $\xi_r$ est une racine simple. Pour une racine multiple, on
  va voir qu'on a quand même convergence, mais avec une vitesse plus lente.
\end{itemize}

\paragraph{La récurrence est bien définie} Par le théorème de Gauss--Lucas, $P'$
et $P''$ ont leurs racines dans $[\xi_1, \xi_r]$. Donc, sur $]\xi_r, +\infty[$,
$P' > 0$ et $P'' > 0$, $P$ est strictement croissante et strictement convexe, et
$f$ est bien définie.

Par stricte convexité, pour $x_n > \xi_r$, $x_{n+1} = f(x_n) > \xi_r$. Pour le
voir, il suffit de faire un dessin : la courbe de $P$ est au-dessus de la
tangente qui relie $(x_{n+1}, 0)$ et $(x_n, P(x_n))$. Formellement : $P(x_n) =
(x_n - x_{n+1})P'(x_n)$ d'une part ; d'autre part $P(x_n) = P'(y)(x_n - \xi_r)$
avec $y \in ]\xi_r, x_n[$ par accroissements finis, or $P'(y) < P'(x_n)$ par
convexité donc $x_n - x_{n+1} < x_n - \xi_r$.

Ainsi, $f : ]\xi_r, +\infty[ \to ]\xi_r, +\infty[$ est bien définie, il en va de
même de la suite $(x_n)$. Celle-ci est donc (strictement) minorée par $\xi_r$,
et de plus décroissante : elle converge.


\paragraph{Convergence vers un point fixe de $f$}

Montrons que $f$ peut être prolongée en $\xi_r$. $m = m_r \geq 1$ étant la
multiplicité de la racine $\xi_r$, on a
$P(\xi_r + h) = a_{m}h^{m} + O(h^{m+1})$
et $P'(\xi_r + h) = ma_{m}h^{m} + O(h^m)$ 
donc
\[  \frac{P(\xi_r + h)}{P'(\xi_r + h)} \sim \frac{h}{m}
  \qquad \text{d'où} \qquad
  f(\xi_r + h) = \xi_r + \left( 1 - \frac{1}{m} \right)h + o(h)
\]
$f$ se prolonge donc par continuité sur $[\xi_r, +\infty[$ par $f(\xi_r) =
\xi_r$ ; comme c'est une fraction rationnelle, $f \in \Cf^\infty([\xi_r,
+\infty[)$. De plus, $f'(\xi_r) = 1 - 1/m$. $\xi_r$ étant l'unique point fixe
sur cet intervalle, $x_n \to \xi_r$ quand $n \to +\infty$.

\paragraph{Cas d'une racine simple}

C'est le cas usuel : comme $f'(\xi_r) = 0$, le point fixe est superattractif.

Par la formule de Taylor--Lagrange à l'ordre 2 :
\[ \forall n \in \N,\; \exists z_n \in ]\xi_r, x_n[ \;/\;
  x_{n+1} - \xi_r = f(x_n) - f(\xi_r) = \frac{f''(z_n)}{2} (x_n - \xi_r)^2
\]
Donc la convergence est au moins \emph{quadratique} :
\[ \frac{x_{n+1} - \xi_r}{(x_n - \xi_r)^2} \xrightarrow[n \to +\infty]{}
  \frac{f''(\xi_r)}{2} \qquad \text{soit} \qquad
  x_{n+1} - \xi_r = O\left( (x_n - \xi_r)^2 \right)
\]
i.e. le nombre de chiffres significatifs de l'approximation double à peu près à
chaque itération.

\paragraph{Cas d'une racine multiple}

Maintenant, $f'(\xi_r) > 0$, le point fixe est attractif et la convergence sera
donc \emph{linéaire}. En effet, on s'y prend de la même façon qu'avant, mais à
l'ordre 1 :
\[ \forall n \in \N,\; \exists z_n \in ]\xi_r, x_n[ \;/\;
  x_{n+1} - \xi_r = f(x_n) - f(\xi_r) = f'(z_n)(x_n - \xi_r)
\]
\[ \frac{x_{n+1} - \xi_r}{x_n - \xi_r} \xrightarrow[n \to +\infty]{}
  f'(\xi_r) = 1 - \frac{1}{m} < 1
\]
En étudiant à l'ordre 2, on peut avoir plus de précisions :

\begin{proposition}
  Il existe $\lambda > 0$ tel que $x_n - \xi_r \sim \lambda (1 - 1/m)^n$.
\end{proposition}
\begin{proof}
  On écrit Taylor--Lagrange :
  \[ \forall n \in \N,\; \exists z_n \in ]\xi_r, x_n[ \;/\;
    x_{n+1} - \xi_r = f'(\xi_r)(x_n - \xi_r)
    + \frac{f''(z_n)}{2} (x_n - \xi_r)^2
  \]
  \[ \frac{x_{n+1} - \xi_r}{x_n - \xi_r} = f'(\xi_r)\left( 1 + O(x_n - \xi_r)
    \right)
  \]
  On montre, en s'aidant de la convergence linéaire précédemment établie, que
  $x_n - \xi_r = O(c^n)$ pour $1-1/m < c < 1$, puis que $\prod_n \left( 1 +
    O(x_n - \xi_r) \right)$ converge. On conclut par produit téléscopique.
\end{proof}

\newpage


\section{Idées exclues}
\label{exclu}

\subsection{Unicité de la topologie de $\R$-EVT séparé en dimension finie}

(EVT = \emph{espace vectoriel topologique}, c'est-à-dire espace vectoriel muni
d'une topologie rendant continues les lois de compositions interne et externe.)

Évidemment, $\R$ est considéré avec sa topologie usuelle, et ça marche aussi
pour les $\C$-EVT.

\begin{theorem}
  Le $\R$-espace vectoriel $\R^n$ n'admet qu'une seule topologie de $\R$-EVT
  séparé, qui est la topologie produit.
\end{theorem}

\begin{remark}
  Les topologies non séparées sont obtenues comme topologie initiale d'une
  projection sur un quotient séparé et sont donc en bijection avec les
  sous-espaces vectoriels (prendre l'adhérence de $\{0\}$).
\end{remark}

Un résultat qui généralise l'équivalence des normes et clôt la question. Fait
dans les premières pages de Bourbaki, \emph{Espaces vectoriels topologiques},
dans le cadre général des corps valués non discrets.

\subsection{Lemme de Hensel, ou méthode de Newton $p$-adique}

Violemment hors-programme, dommage, c'est plus original que la méthode de Newton
usuelle et c'est de la jolie algèbre en plus… Un PDF de Keith Conrad raconte ça
super bien.

\begin{definition}
  On appelle \emph{entier $p$-adique} une suite $(a_n)_{n \in \N^*}$
  avec $a_n \in \Z/p^n\Z$ et $\pi_n(a_{n+1}) = a_n$ pour $n \in \N^*$,
  où $\pi_n : \Z/p^{n+1}\Z \to \Z/p^n\Z$ est la projection canonique.
\end{definition}
\begin{proposition}
  Les entiers $p$-adiques forment un sous-anneau de
  $\prod_{n \in \N^*} \Z/p^n\Z$, de caractéristique nulle. Cet anneau
  est noté $\Z_p$.
\end{proposition}

\begin{definition}
  Le \emph{corps des nombres $p$-adiques} $\Q_p$ est le complété de
  $\Q$ pour la distance $d_p(x,y) = p^{-v_p(x-y)}$.
\end{definition}
\begin{proposition}
  La boule fermée de centre 0 et de rayon 1 dans $\Q_p$ est un
  sous-anneau isomorphe à $\Z_p$.
\end{proposition}

\begin{lemma}[Hensel]
  Soient $f \in \Z_p[X]$ et $a \in \Z/p\Z$ tels que dans $\Z/p\Z$, on
  ait $f(a) = 0$ et $f'(a) \neq 0$. Alors il existe un unique
  $\alpha \in \Z_p$ tel que $f(\alpha) = 0$ et dont la classe dans
  $\Z/p\Z$ soit $a$.
\end{lemma}

\begin{corollary}
  Soient $f \in \Z[X]$ et $a \in \Z$ tels que $f(a) \equiv 0 \mod p$
  et $f'(a) \not\equiv 0 \mod p$. Alors pour tout $n \in \N^*$, il
  existe $\alpha \in \Z$ tel que $f(\alpha) \equiv 0 \mod p^n$ et
  $\alpha \equiv a \mod p$.
\end{corollary}

On a deux procédés d'itération légèrement différents pour relever des solutions
dans un $\Z/p^n\Z$ plus grand : l'un est la méthode de Newton, l'autre ressemble
à la preuve du théorème d'inversion locale.

\newpage

\subsection{Fonctions invariantes d'une équation différentielle linéaire}

Un développement inspiré par une remarque dans \emph{Ten lessons I wish I had
  learned before I started teaching differential equations} (item 3) de
Gian-Carlo Rota. Voir la fin pour plus de remarques culturelles.

En vrai, c'est assez décevant comme truc.

On considère ici l'équation différentielle linéaire
homogène
\[ y''(t) + p(t)y'(t) + q(t) = 0 \qquad (p, q : \R \to \R) \]
dont on notera $S \subset \Cf^2(\R, \R)$ l'espace des solutions.

Si $f : \R^{2k} \to \R$ ($k \in \N^*$ quelconque), on abrégera
\[ f[y,z](t) = f \left(y(t), \ldots, y^{(k)}(t), z(t), \ldots,
    z^{(k)}(t)\right) \]
et on appellera $f$ une \emph{fonction invariante} si, pour toute
base de $S$ (i.e. système fondamental de solutions) $(y, z)$,
\[
  \forall L \in \GL(S),\, \exists \lambda(L) \in \R \,/\, \forall t \in \R,\;
  f[Ly,Lz](t) = \lambda(L) \cdot f[Ly, Lz](t)
\]
Autrement dit, une fonction invariante est indépendante du système fondamental
de solution choisi, à un facteur constant (par rapport au temps) près.

On peut remarquer que les coefficients de l'équation sont en fait des fonctions
invariantes (avec $\lambda(L) = 1$) puisque
\[ \]
Un autre exemple de fonction invariante est le \emph{wronskien}
\[  W[y,z](t) =  \]

L'invariance du wronskien découle immédiatement du lemme suivant :
\begin{lemma}
  Soit $(y, z)$ une base de $S$, $L \in \GL(V)$. Alors, pour tout $t \in \R$,
  \[ W[Ly,Lz](t) = (\det L) \cdot W[y,z](t) \]
\end{lemma}
Ici, donc $\lambda(L) = \det(L)$.
\begin{proof}
  Comme $(y,z)$ est une base, on peut y décomposer $Ly$ et $Lz$ :
  \[ Ly = ay + bz \quad Lz = cy + dz \]
  Dans la base $(y,z)$, la matrice de $L$ est donc
  \[ M = abcd \]
  donc $\det L = \det M$.

  Maintenant, soit $t \in \R$. Évaluons ces relations, ainsi que celles obtenues
  en dérivant, au point $t$. On obtient
  \[ plif = plaf \times plouf \]
  d'où, en prenant le déterminant,
  \[ tadaaa \]
\end{proof}

Nous en venons maintenant au théorème principal : en un certain sens, ces
fonctions invariantes suffisent à engendrer toutes les autres.

\begin{theorem}
  Soit $f$ une fonction invariante, alors il existe $g : \R \to \R$ et $h :
  \R^{2l} \to R$ tels que pour toute base $(y,z)$,
  \[ \forall t \in \R,\, f[y,z](t) = g(W[y,z](t))h[p,q](t) \]
\end{theorem}

Commençons par un résultat d'algèbre linéaire.

\begin{proposition}
  Soit $\phi : \GL_n(\R) \to \R^*$ un morphisme de groupes. Alors il existe
  $\psi : \R^* \to \R^*$ tel que $\phi = \psi \circ \det$.
\end{proposition}
\begin{proof}
  Soit $T$ une transvection, alors $T^2$ est aussi une transvection, donc $T$ est
  semblable à $T^2$. Comme $\phi$ est à valeurs dans un groupe abélien, on a
  donc $\phi(T)^2 = \phi(T)$, soit $\phi(T) = 1$ dans $\R^*$.

  Comme les transvections engendrent $\SL_n(\R)$, on a $\phi(\SL_n(\R)) =
  \{1\}$. $\phi$ passe donc au quotient comme morphisme $\GL_n(\R)/\SL_n(\R) \to
  \R^*$. Or le déterminant réalise un isomorphisme entre $\GL_n(\R)/\SL_n(\R)$
  et $\R^*$…
\end{proof}

Maintenant, fixons $f$ une fonction invariante et $(y,z)$ une base. On peut voir
que si $f[y,z](t) \neq 0$ pour un certain $t$, alors les $\lambda(L)$ sont
uniques, non nuls, et réalisent un morphisme de groupes vers $\R^*$. On a alors,
par le lemme précédent, $\lambda(L) = g(\det L)$ pour tout $L \in GL(S)$.

Soit $t \in \R$. Il existe un système fondamental $(u_t, v_t) \in S^2$ tel que
$u(0) = v'(0) = 1$, $u'(0) = v(0) = 0$, de sorte que $W[u,v](t) = 1$. Soit $L_t
\in \GL(S)$ telle que $L_tu_t = y$ et $L_tv_t = z$. Alors
\[ f[y,z](t) = \lambda(L) \cdot f[u_t,v_t](t) \quad \text{avec} \quad
  \lambda(L) = g(\det L_t) = g\left( \frac{W[y,z](t)}{W[u_t,v_t](t)} \right)
    = g(W[y,z](t))
\]
en utilisant le lemme sur le wronskien démontré plus haut.

On a donc notre facteur $g(W)$, reste à trouver $h$ telle que
\[ \forall t \in \R,\, h[p,q](t) = W[u_t, v_t](t) \]

Pour cela, remarquons qu'on a $y'' = -py' - qy$, suite à quoi $y''' = -py'' -
p'y' - qy' - q'y = p(py'+qy) - p'y' - qy' - q'y$, etc. Par récurrence, il existe
une suite de polynômes $P_n$ tels que…

ENFIN BREF VOILÀ

\begin{remark}
  Ce théorème est l'analogue du théorème fondamental sur les polynômes
  symétriques, qui dit qu'un polynôme symétrique en les solutions d'une équation
  polynomiale s'exprime comme polynôme en les coefficients de l'équation.
\end{remark}

\paragraph{Culture, biblio, etc.}

Publié dans les annales scientifiques de l'ENS par un matheux oublié par
l'Histoire. 





\end{document}
