\documentclass{beamer}

\mode<presentation> {
  \usetheme{Montpellier}
  \setbeamercovered{transparent}
}

\usepackage[french]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\newcommand{\Cl}{\mathcal{C}\ell}
\newcommand{\N}{\mathcal{N}}
\renewcommand{\P}{\mathcal{P}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\f}{\mathfrak{f}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\FF}{\mathbb{F}}
\renewcommand{\d}{\mathrm{d}}
\newcommand{\Res}{\mathrm{Res}}
\newcommand{\Spec}{\mathrm{Spec}}
%\renewcommand{\theorem}{}
\newtheorem{theorema}{Théorème}
\newtheorem{lemmaa}[theorem]{Lemme}
\newtheorem{remark}[theorem]{Remarque}
\newtheorem{princip}[theorem]{Principe}
\renewcommand{\theorem}{\theorema}
\renewcommand{\lemma}{\lemmaa}

\title{Expérimentations avec le calcul du groupe des classes de corps de nombres de grand degré}

\author{B.~Allombert}
\institute
{
  Université Montpellier 2 (en lutte)
  LIRMM/I3M \\
  (avec Karim Belabas, Université Bordeaux 1)
}

\date{28/09/2009}

\subject{Exposé}
%\logo{\pgfimage[height=1cm]{um2.png}}
%\logo{\pgfuseimage{um2}}
%\logo{\includegraphics[height=1.5cm]{um2.png}}
\AtBeginSubsection[] {
  \begin{frame}<beamer>{Lignes directrices}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

%\beamerdefaultoverlayspecification{<+->}

\begin{document}
\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Lignes directrices}
  \tableofcontents
  % Vous pouvez, si vous le souhaiter ajouter l'option [pausesections]
\end{frame}


\section{Introduction}
\begin{frame}{Introduction}
Algorithme pour le calcul du groupe de classes et du groupe
des unités d'un corps de nombres.
\begin{itemize}
\item Inventé il y a 20 ans par J.Buchmann
\item Généralisation de l'algorithme de Haffner et McCurley pour les
corps quadratiques imaginaires.
\item Implanté par Cohen-Diaz-Olivier dans PARI/GP
\item Algorithme "Las Vegas", sous GRH, heuristiquement en temps
sous-exponentiel en la taille du discriminant, si le degré est fixé.
\item Autre implantation complète connue : Magma/KANT.
\end{itemize}
\end{frame}

\section{Groupe de classes et groupe des unités}

\subsection{Notations}

\begin{frame}{Notations}
Soit $K$ un corps de nombres on note:
\begin{itemize}
\item $n$ le degré de $K$.
\item $(r_1, r_2)$ la signature de $K$.
\item $(\sigma_1,\ldots,\sigma_{r_1+r_2})$ les plongements complexes de $K$.
\item $\O(K)$ l'anneau des entiers de $K$.
\item $\d(K)$ le discriminant de $\O(K)$.
\item $\mu(K)$ le groupe des racines de l'unité dans $K$.
\item $U(K)$ la partie libre de $\O(K)^{\times}$.
\item $R(K)$ le régulateur de $K$.
\item $\Cl(K)$ le groupe de classes de $\O(K)$.
\item $h(K)$ le nombre de classes de $\O(K)$.
\end{itemize}
\end{frame}

\subsection{Structure des groupes}

\begin{frame}{Structure des groupes}

\begin{theorem}[P.Dirichlet]
 $\O(K)^{\times}=\mu(K)\*U(K)$ et $U(K)\cong\ZZ^{r_1+r_2-1}$.
\end{theorem}
\begin{theorem}[E.Bach, sous GRH]
 Soit $C$ le plus petit nombre réel tel que l'ensemble des idéaux premiers
de norme au plus $C\*\log(d(K))^2$ engendre $\Cl(K)$, alors $C\leq 12$.
\end{theorem}
Conséquence:
\begin{itemize}
\item Les générateurs du groupe de classes sont connus, mais pas les relations.
\item Les relations du groupe des unités sont connues mais pas les générateurs.
\end{itemize}
\end{frame}

\subsection{Fonction zeta}
\begin{frame}{Fonction zeta}

\begin{theorem}[R.Dedekind]

Soit $$\zeta_K(s)=\prod_{\p}\frac{1}{1-\N(\p)^{-s}}$$
la fonction $\zeta$ du corps $K$, alors

$$\Res_1(\zeta_K)=2^{r_1}\*(2\*\pi)^{r_2}\frac{\*h(K)\*R(K)}{|\mu(K)|\sqrt{|d(K)|}}$$
\end{theorem}

\end{frame}

\begin{frame}
\begin{remark}
$$\Res_1(\zeta_K)=\lim_{s=1}\zeta_K(s)/\zeta(s)=\prod_{p}{\frac{1-p^{-1}}{\prod_{\p\mid p}{\left(1-\N(\p)^{-1}\right)}}}$$
\end{remark}
\begin{theorem}[sous GRH]
Soit $$z = 2^{-r_1}\*(2\*\pi)^{-r_2}\*|\mu(K)|\sqrt{|d(K)|}\*\prod_{p\leq M}{\frac{1-p^{-1}}{\prod_{\p\mid p, \N(\p)\leq M}{\left(1-\N(\p)^{-1}\right)}}}$$
alors il existe $M=O(\log(|d(K)|)^2)$ tel que
$z/\sqrt{2}<h(K)\*R(K)<z\*\sqrt{2}$.
\end{theorem}
\end{frame}

\subsection{Relations aléatoires}
\begin{frame}{Principe heuristique}
Soit $I$ un idéal entier de $\O_K$ supposé principal. 
\begin{itemize}
\item L'élément $\alpha$ engendre $I$ si et seulement si $|\N(\alpha)|=\N(I)$.
\item Il s'agit donc de minimiser la fonction $\N$ sur $I$.
\item Or on ne sait pas minimiser directement $\N$.
\item On majore $\N$ par une forme quadratique définie positive.
$$|\N(x)|=|\prod_{i=1}^n{\sigma_i(x)}|\leq q(x)^{\frac{n}{2}}$$
(par exemple, $q(x)=\sum_{i=1}^n{|\sigma_i(\alpha)|^2}$).
\item L'algorithme LLL nous donne un élément $\alpha\in I$ tel que 
$q(\alpha)\leq 2^{n-1}\*\min_I(q)$.
\item On espère que $\N(\alpha)$ est proche de $\N(I)$.
\end{itemize}
\end{frame}

\begin{frame}{Relations aléatoires}
Soit $$\P=\{\p;\N(\p)\le C\log(\d(K))^2\}$$ la "base de facteur".
\begin{itemize}
\item On choisit au hasard des entiers positifs $(a_{\p})_{\p\in\P}$.
\item On calcule $I=\prod_{\p\in\P}{\p^{a_{\p}}}$.
\item On choisit des entiers $v_i$ et l'on munit $I$ de la forme quadratique
$q(\alpha)=\sum_{i=1}^n{e^{v_i}\*|\sigma_i(\alpha)|^2}$.
\item LLL permet de trouver un élément $\alpha\in I$ petit pour $q$.
\item On espère que $\N(\alpha)$ est petit.
\end{itemize}
\end{frame}

\begin{frame}
On essaie de factoriser $\alpha\O_K$ dans la base
$\P$. En cas de succès on obtient la factorisation de $J=I/\alpha$.
On écrit $J=\prod_{\p\in\P}\p^{b_\p}$ et l'on a la relation
$$\prod_{\p\in\P}\p^{b_\p-a_\p}=\alpha\O_K\enspace.$$
Dans le groupe de classe nous avons:
$$\prod_{\p\in\P}\Cl(\p)^{b_\p-a_\p}=1$$
De plus si, en combinant des relations, nous trouvons une relation
$$\prod_{\p\in\P}\p^{0}=\beta\O_K$$
alors $\beta$ est une unité.
\end{frame}

\begin{frame}{Critère d'arrêt}
Supposons que l'on ait trouvé un ensemble de relations et un ensemble d'unités.
Soit $\widetilde{U}$ le sous-groupe de $U(K)$ engendré, et $\widetilde{\Cl}$ le 
quotient obtenu, alors on peut calculer une valeur $\widetilde{h}$ et
$\widetilde{R}$.
On a
$$\widetilde{h}\*\widetilde{R}=[U(K):\widetilde{U}]\*[\widetilde{\Cl}:\Cl(K)]\*h(K)\*R(K)$$
donc si $$z/\sqrt{2}<\widetilde{h}\*\widetilde{R}<\sqrt{2}\*z$$
alors $U(K)=U$ et $\widetilde{\Cl}=\Cl(K)$.
\end{frame}

\subsection{L'algorithme}

\begin{frame}{Résumé de l'algorithme}
\begin{enumerate}
\item Calcul de $\d(K)$ et d'une base d'entiers de $\O(K)$.
\item Calcul de $\mu(K)$.
\item Calcul de $B=C\*\log(\d(K))^2$.
\item Calcul de tout les idéaux premiers de norme au plus $B$.
\item Calcul de $z$ tel que $z/\sqrt{2}<h(K)\*R(K)<z\*\sqrt{2}$.
\item Calcul des relations triviales $p\O_K=\prod_{\p\mid p}\p^{e_{\p}}$.
\item Calcul des relations dues aux éléments de petites normes.
\item\label{alea} Calcul de relations aléatoires.
\item Calcul de $\widetilde{h}$ et $\widetilde{R}$.
\item Si $z/\sqrt{2}<\widetilde{h}\*\widetilde{R}<z\*\sqrt{2}$, terminer
l'algorithme, sinon recommencer en~\ref{alea} \end{enumerate} \end{frame}

\section{Améliorations apportés}

\begin{frame}{Progrès}
\begin{enumerate}
\item Calcul de $\d(K)$ et d'une base d'entiers de $\O(K)$.
Implantation de l'algorithme Round4 de H.Zassenhaus/D.Ford par X.Roblot et
S.Pauli.
\pause
\item Calcul de $\mu(K)$.
Implantation d'un algorithme en temps polynomial (P.Molin)
\pause
\item Calcul de $B=C\*\log(\d(K))^2$.
L'algorithme de K.Belabas/F.Diaz Y Diaz/E.Friedmann permet de trouver une
constante $C$ adapté à un corps donné (souvent $C\leq\frac{2}{3}$).
\end{enumerate}
\end{frame}
\begin{frame}{Progrès}
\begin{enumerate}\setcounter{enumi}{3}
\item Calcul de $\P=\{\p;\N(\p)\le B\}$.
\item Calcul de $z$ tel que $z/\sqrt{2}<h(K)\*R(K)<z\*\sqrt{2}$.
\item Calcul des relations triviales $p\O_K=\prod_{\p\mid p}\p$.
\pause
\item Calcul des relations dues aux éléments de petites normes.\\
Amélioration de l'implantation de l'algorithme de Fincke-Pohst
pour éviter les cas où il y a un nombre exponentiel de vecteurs
minimaux.
\pause
\item Calcul de relations aléatoires.\\
Implantation de LLL$^2$ de P-Q.Nguyen et D.Stelhé pour la réduction de
réseau.  
Amélioration de la stratégie pour le choix des $(a_{\p})$.
\pause
\item Calcul de $\widetilde{h}$ et $\widetilde{R}$.\\
Amélioration de la stabilité numérique du calcul de $\widetilde{R}$.
\end{enumerate}
\end{frame}
\begin{frame}{Une nouvelle stratégie pour les relations}
\begin{princip}[1]
Pour que la matrice des relations soit de
rang maximal, il faut au moins que chaque idéal de la base appartienne
à au moins une relation.
\end{princip}
\begin{princip}[2]
Pour trouver des relations relativement vite, il faut que
$I$ soit relativement petit.
\end{princip}
\begin{itemize}
\item On choisit un ensemble fini $S\subset\P$ de petits idéaux premiers.
\item  On réduit la matrice des relations par HNF.
\item Pour chaque $\p$ qui n'est pas "éliminé", on essaie un vecteur $(a)$
avec $a_{\p}=1$ et $a_{\p'}=0$ si $\p'\not\in S\cup\{\p\}$.
\item Si l'on ne fait pas de progrès, on change $S$ et l'on recommence.
\end{itemize}
\end{frame}

\section{Expérimentation}
\subsection{Résultats expérimentaux}
\begin{frame}{Résultats expérimentaux}
\begin{tabular}{lrrcrr}
Corps & Deg. & Root & $\Cl$ & R & temps \\
$\QQ(\zeta_{23})^H$ & 66 & 19.9 & 1   & 1.98138718 E17& 3h, 51min \\
$\QQ(\zeta_{120})^h$ & 64 & 23.2 & 2  & 1.147710183 E19& 3h, 11min \\
$\QQ(\zeta_{29})^h$ & 56 & 25.7 & 2x2 & 3.29663170 E17& 3h, 21min \\
$\QQ(\zeta_{39})^H$ & 48 & 18.2 & 1   & 1.19342320 E12&       9min \\
%$\QQ(\zeta_{156})$  & 48 & 36.4 & 156 & 3.81112901 E17&       5min \\
$\QQ(\zeta_{109})^+$
                    & 54 & 99.9 & 1   & 9.79264019 E36&  1h, 17min \\
$\QQ(\zeta_{113})^+$
                    & 56 & 103.9 & 1  & 9.43984600 E38&  2h, 12min \\
$\QQ(\alpha_{59})$
                    & 59 & 59.0  & 1  & 5.60503440 E28&  7h, 48min \\
$\QQ(\alpha_{61})$
                    & 61 & 61.0 &  1  & 6.45543747 E29& 56h, 11min \\
$\QQ(\sqrt[53]{2})$ 
                    & 53 & 104.6 & 1  & 5.74645573 E32& 30h, 43min \\
$\QQ(\sqrt[54]{2})$ 
                    & 54 & 106.6 & 1  & 2.84366591 E33& 80h, 23min \\
$\QQ(\zeta_{36},\sqrt[6]{2})$ 
                    & 72 & 29.8 & 3 & 7.395320 E24 & 327h \\
$\QQ(\zeta_{16},\sqrt[16]{2})$ 
                    & 64 & 34.1  & 1  & 2.75018677 E24&  6h, 47min \\
$\QQ(\zeta_{9},\sqrt[9]{2})$ 
                    & 54 & 21.7  & 1  & 1.41057940 E15&       6min
\end{tabular}
$(\alpha_p)^p=\alpha_p+1$
\end{frame}
\subsection{Conclusion heuristique}
\begin{frame}{Conclusion heuristique}
Il semble que la présence de racines de l'unité dans le corps de nombres
rende le calcul plus facile. Nous proposons plusieurs justifications
heuristiques:
\begin{itemize}
\item Les corps cyclotomiques ont un root-discriminant relativement petits.
\item Les racines de l'unités implique l'existence d'unités cyclotomiques,
facile à calculer.
\item Les réseaux contenant les racines de l'unités semblent être plus faciles
à traiter par LLL qui retourne souvent le plus petit vecteur.
\end{itemize}
\end{frame}

\section{Applications}

\subsection{Extensions ramifiées en un seul premier}
\begin{frame}{Extensions ramifiées en un seul premier}
\begin{theorem}[D.Harbater (1994), 
théorème~2.6 in «Galois groups with prescribed ramification»]
\begin{enumerate}
\item Si $p<23$ est premier, alors
      $\pi_1^t(\Spec(\ZZ[\frac{1}{p}])) \cong \ZZ/(p-1)\ZZ$
\item Le groupe $\pi_1^t(\Spec(\ZZ[\frac{1}{23}]))$ n'est pas cyclique.
\end{enumerate}
\end{theorem}
\begin{theorem}[sous GRH+PARI]
$$\pi_1^t(\Spec(\ZZ[\frac{1}{23}]))^\mathrm{solv} \cong \ZZ/11\ZZ\times\mathrm{D}_6$$
\end{theorem}
\end{frame}

\subsection{Construction explicite de corps de classes.}
\begin{frame}{Construction explicite de corps de classes.}
Soit $K$ un corps de nombre, un conducteur $\f$ et un sous-groupe $C$ de
$\Cl_\f(K)$ d'indice $\ell$ premier. Il s'agit de calculer le sous-corps $L$
du corps de classe de rayon $\f$ de $K$ correspondant à $C$ ($[L:K]=\ell$).

Les algorithmes algébriques de constructions explicites de corps
de classes basés sur la théorie de Kummer requièrent le calcul
du groupe de classe et du groupe des unités du corps $K(\zeta_{\ell})$,
mais ont une complexité polynomial en le conducteur.
\end{frame}

\begin{frame}{Kronecker Jugendraum}
Les algorithmes basés sur une version effective du "Jugendraum" de Kronecker
ont une complexité exponentielle dans le conducteur et ne sont connus que
pour certaines classes de corps de bases.
\end{frame}

\begin{frame}{Réalisation explicite de groupe de Galois.}
En utilisant des constructions explicite de corps de classes, nous
avons pu calculer des polynômes réalisant explicitement certains groupe de
Galois comme extensions totalement réelles et totalement complexes sur $\QQ$.
\begin{center}
\begin{tabular}{lrrcrrr}
Groupe & sign. & $[K:\QQ]$ & $\ell$ & $[K(\zeta_{\ell}):\QQ]$ &  $[L:\QQ]$ & cond. \\
\hline \\
$C_{13}\rtimes C_8$
       & cplx & 4         & 13    &  48                    & 52  & 499   \\
$C_{13}\rtimes C_8$
       & réel  & 4        & 13    &  48                    & 52  & 155  \\
$C_{25}\rtimes C_4$ 
       & cplx & 20        & 5     &  20                    & 100  & 14   \\
$C_{25}\rtimes C_4$
       & réel & 20        & 5     &  40                    & 100 & 107  \\
$C_{31}\rtimes C_3$
       & réel & 3         & 31    &  31                    & 93  & 155  \\
$C_{17}\rtimes C_4$
       & réel & 4         & 17    &  17                    & 68   & 137   \\
\end{tabular}
\end{center}
\end{frame}

%\section{Améliorations possibles}
%\begin{frame}{Améliorations possibles}
%\begin{enumerate}
%\item Implantation de la variante "single large prime".
%\item Parallélisation du calcul des relations.
%\item Amélioration de l'implantation de l'algorithme de 
%calcul de la HNF.
%\end{enumerate}
%\end{frame}
\end{document}
