\documentclass{beamer}

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

%\usepackage[french]{babel} 
\usepackage[utf8]{inputenc}
%\usepackage[english]{babel}
%\usepackage[utf8x]{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}}
\renewcommand{\S}{\mathfrak{S}}
\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{\Gal}{\mathrm{Gal}}
\newcommand{\frob}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\val}{v}
%\renewcommand{\theorem}{}
\newtheorem{defi}{Définition}
\newtheorem{theorema}{Théorème}
\newtheorem{lemmaa}[theorem]{Lemme}
\newtheorem{remark}[theorem]{Remarque}
\newtheorem{princip}[theorem]{Principe}
\newtheorem{algorithm}[theorem]{Algorithme}
\renewcommand{\theorem}{\theorema}
\renewcommand{\lemma}{\lemmaa}
\newcommand{\kbd}[1]{\texttt{#1}}
\newcommand{\ida}{\mathfrak{a}}

\DeclareMathOperator{\Tr}{Tr}
%\DeclareMathOperator{\Cl}{Cl}

\title{Subfields and Abelian overfields}
%\subtitle{Un tutoriel}

\author{A.~Page}
\institute
{
  %IMB\\
  INRIA/Université de Bordeaux
}

\date{21/01/2020\\Institut Fourier}

\begin{document}

\begin{frame}
  \titlepage
$$\includegraphics[scale=0.3]{pari.png}$$
\end{frame}

\begin{frame}[fragile]{Plan}
%  \begin{itemize}
%    \item refcard-nf.pdf: list of functions with a short description.
%    \item users.pdf Section 3.13: introduction and detailed descriptions of the
%      functions.
%    \item in gp, \kbd{?10}: list of functions.
%    \item in gp, \kbd{?functionname}: short description of the function.
%    \item in gp, \kbd{??functionname}: long description of the function.
%  \end{itemize}

  This tutorial:
  \begin{itemize}
    \item construction of subfields of a number field
    \item construction of abelian extensions of a number field
  \end{itemize}
  These are old functionalities but we made a number of changes to them.

  \bigskip

  If you want to record the commands we will type during the tutorial:
\begin{verbatim}
? \l subsupfields.log
\end{verbatim}
  
\end{frame}

\begin{frame}[fragile]{Subfields}
  We compute the subfields of a number field with the function~\texttt{nfsubfields}.
\begin{verbatim}
? pol1 = y^8 - y^6 + 2*y^2 + 1;
? #nfsubfields(pol1)
% = 6
\end{verbatim}
This number field has~$6$ subfields.
\begin{verbatim}
? #nfsubfields(pol1,4)
% = 3
\end{verbatim}
Three of them have degree~$4$ over~$\QQ$.
\end{frame}

\begin{frame}[fragile]{Subfields and embeddings}
  For each subfield, the function gives a defining polynomial and an element of
  the large field defining the embedding.
\begin{verbatim}
? sub1 = nfsubfields(pol1,4)
% = [[y^4 - ... , 2*y^7 - ...], [y^4 - ...,
 -2*y^7 + ...], [y^4 - ..., -y^2 + 1]]
? a = y^2+y;
? minpoly(Mod(a,sub1[1][1]))
% = x^4 + 2*x^3 + 76*x^2 + 60*x + 12
\end{verbatim}
  We can compute the image of~$a$ in the large field with~\texttt{subst}.
\begin{verbatim}
? minpoly(Mod(subst(a,y,sub1[1][2]),pol1))
% = x^4 + 2*x^3 + 76*x^2 + 60*x + 12
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Subfields}
  We can also use an~\texttt{nfinit} structure as input.
\begin{verbatim}
? nf1 = nfinit(pol1);
? #nfsubfields(nf1,2)
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Algorithms for subfields}
  Depending on the situation, we use various algorithms to compute subfields
  of~$K = \QQ[X]/P(X)$.
  \begin{enumerate}
    \item Galois theory (Allombert);
    \item A combinatorial algorithm (Kl\"uners);
    \item A factorisation based algorithm (van Hoeij -- Kl\"uners -- Novocin).
  \end{enumerate}
  1. is always faster when available, 3. is polynomial-time, and 2. is
  exponential in the worst case but it is often fast.

  \medskip
  
  In~3., we need the factorisation of~$P$ over~$K$.
\end{frame}

\begin{frame}[fragile]{Subfields: providing the factorisation}
  We can provide the factorisation to the function.
  This forces the use of Algorithm 3. and saves the recomputation of the
  factorisation.
\begin{verbatim}
? fa1 = nffactor(pol1, subst(pol1,y,x));
? sub1b = nfsubfields([pol1,fa1],4)
% = [[y^4 + ..., -y^5 + ...], [y^4 + ..., -y^2],
 [y^4 + ..., -y^3 + y]]
\end{verbatim}

  We can check that we obtained the same subfields with~\texttt{nfisisom}.
\begin{verbatim}
? nfisisom(sub1[1][1],sub1b[1][1])
% = [-1/2*y^3 - 1/2*y^2 - 3/2*y - 1/2,
 1/2*y^3 - 1/2*y^2 + 3/2*y - 1/2]
\end{verbatim}

\end{frame}

\begin{frame}[fragile]{Subfields: providing the factorisation}
  There is no canonical ordering for the subfields, so they may end up being
  permuted.
\begin{verbatim}
? matrix(#sub1,#sub1b,i,j,
    nfisisom(sub1[i][1],sub1b[j][1])!=0)
% = 
[1 0 0]

[0 0 1]

[0 1 0]
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Maximal subfields}
  We can restrict to the enumeration of maximal subfields with the
  function~\texttt{nfsubfieldsmax}.
\begin{verbatim}
? {pol2 = x^16 - 4*x^15 + 34*x^14 - 102*x^13 + 
 620*x^12 - 1542*x^11 + 7436*x^10 - 14962*x^9 +
 67815*x^8 - 111634*x^7 + 409898*x^6 - 504000*x^5
 + 1459447*x^4 - 1224212*x^3 + 3769899*x^2 - 
 1828918*x + 6914293};
? sub2 = nfsubfieldsmax(pol2);
? apply(a -> poldegree(a[1]), sub2)
% = [4, 8, 8, 8]
\end{verbatim}
  They do not always have the same degree.
\end{frame}

\begin{frame}[fragile]{Maximal subfields: providing the factorisation}
  This uses a variant of Algorithm 3., and we can also provide the
  factorisation.
\begin{verbatim}
? fa2 = nffactor(pol2, subst(pol2,x,t));
  *** incorrect priority: variable t >= x
\end{verbatim}
  Watch out for the priority of variables!
\begin{verbatim}
? t = varhigher("t");
? fa2 = nffactor(pol2, subst(pol2,x,t));
? nfsubfieldsmax([pol2,fa2]) == sub2
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Descending further}
  We can then compute subfields of the maximal subfields, etc.
\begin{verbatim}
? {pol3 = y^12 + 6*y^10 - 10*y^9 + 36*y^8 - 60*y^7
+ 276*y^6 - 720*y^5 + 1776*y^4 - 2360*y^3 +
2160*y^2 - 1200*y + 400};
? sub3 = nfsubfieldsmax(pol3);
? apply(a -> poldegree(a[1]), sub3)
% = [4, 6]
? sub3b = nfsubfieldsmax(sub3[1][1])
% = [[y^2 - ...ugly...]
\end{verbatim}
  %The maximal subfields have degree $4$ and $6$, and the quartic one has a quadratic
  %subfield.
  We can simplify the models with~\texttt{polredbest}.
\begin{verbatim}
? polredbest(sub3b[1][1])
% = y^2 - y - 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{CM fields}
  Recall that a number field~$K$ is called~\emph{CM} (complex multiplication) if it
  is a totally imaginary quadratic extension of a totally real field.
  
  \bigskip 

  In this case, it admits an automorphism of order~$2$ which induces complex
  conjugation on every embedding of~$K$ into~$\CC$; this automorphism is called the
  CM involution or the complex conjugation on~$K$.
\end{frame}

\begin{frame}[fragile]{Maximal CM subfield}
  We can also compute the maximal CM subfield (if it exists).
\begin{verbatim}
? nfsubfieldscm(pol1)
% = [y^2 + 3, 2*y^6 - 4*y^4 + 2*y^2 + 3]
? sub2b = nfsubfieldscm([pol2,fa2])
% = [x^4 + ...*x^2 + ..., ...]
\end{verbatim}
  The computed model always satisfies that~$x\mapsto -x$ is the CM involution.

  \smallskip

  In~\texttt{polredbest}, we can keep track of the change of variable with an
  optional flag~$=1$.
\begin{verbatim}
? polredbest(sub2b[1],1)
% = [x^4 - 2*x^3 - 11*x^2 + 12*x + 57, ...]
? polredbest(substpol(sub2b[1],x^2,x))
% = x^2 - 7
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Abelian extensions of~$\QQ$}
  Recall that every Abelian extension of~$\QQ$ is contained in a cyclotomic
  field (Kronecker--Weber).

  \smallskip

  \texttt{polsubcyclo}$(n,d)$ computes every subfield of~$\QQ(\zeta_n)$ of degree~$d$.
\begin{verbatim}
? polsubcyclo(23,11)
% = x^11 + x^10 - 10*x^9 - 9*x^8 + 36*x^7 + 28*x^6
 - 56*x^5 - 35*x^4 + 35*x^3 + 15*x^2 - 6*x - 1
\end{verbatim}

  \texttt{galoissubcyclo} computes the subfield fixed by a given subgroup
  of~$(\ZZ/n\ZZ)^\times$.
\begin{verbatim}
? #polsubcyclo(60,8)
% = 7
? galoissubcyclo(60,-1)
% = x^8 - 7*x^6 + 14*x^4 - 8*x^2 + 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Abelian extensions of~$\QQ$}
  We compute the structure and generators of~$(\ZZ/n\ZZ)^\times$
  with~\texttt{znstar}.
\begin{verbatim}
? G = znstar(7*13*19)
% = [1296, [36, 6, 6], [Mod(743, 1729), Mod(248, 1729), Mod(407, 1729)]]
\end{verbatim}
  We can describe the subgroup in terms of those generators.
\begin{verbatim}
? H = mathnfmodid([1,0;-1,1;0,-1],3);
? galoissubcyclo(G,H)
% = x^3 + x^2 - 576*x - 64
? nfdiscfactors(%)
% = [2989441, [7, 2; 13, 2; 19, 2]]
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Abelian extensions of number fields}
  In general, the Abelian extensions of a number field~$K$ are the subfields of
  its ray class fields, whose Galois groups are canonically isomorphic to the ray class
  groups~$\Cl_K(\mathfrak{m})$.

  (Class field theory)

  \bigskip
   
  The special case~$\mathfrak{m}=(1)$ is the Hilbert class field.
\end{frame}

\begin{frame}[fragile]{Transcendental methods}
  In some cases we can use transcendental methods to compute ray class fields.
  \medskip

  Hilbert and ray class fields of quadratic fields:
\begin{verbatim}
? quadhilbert(-23)
% = x^3 - x^2 + 1
? quadray(-7,8)
% = x^8 + Mod(-4*y + 4, y^2 - y + 2)*x^7 + ...
\end{verbatim}
  Assuming Stark's conjectures, ray class fields of totally real fields:
\begin{verbatim}
? bnrstark(bnrinit(bnfinit(y^3-y^2-41*y+104),1))
% = x^9 + ...
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Kummer theory method}
  In all cases we can use Kummer theory. This can be costly since we need to
  compute the class group and units of~$K(\zeta_p)$ to compute extensions of
  degree~$p$ of~$K$, and towers of such for general Abelian extensions.

  \bigskip

  The function~\texttt{rnfkummer} is now obsolete; use the more
  general~\texttt{bnrclassfield} instead, which we will present now.
\end{frame}

\begin{frame}[fragile]{Hilbert class field}
\begin{verbatim}
? pol4 = y^2-y+1007
% = y^2 - y + 1007
? bnf = bnfinit(pol4); bnf.cyc
% = [3, 3]
\end{verbatim}
  The class group is isomorphic to~$\ZZ/3\ZZ\times\ZZ/3\ZZ$.
\begin{verbatim}
? ext4 = bnrclassfield(bnf)
% = [x^3 - 15*x + (-1204*y + 602), x^3 + ...]
\end{verbatim}
  By default, the class field is expressed as the compositum of two degree~$3$
  extensions. We can compute a single defining polynomial
  with~\texttt{nfcompositum}.
\begin{verbatim}
? nfcompositum(bnf,ext4[1],ext4[2],2)
% = x^9 + ...
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Hilbert class field}
  We can directly ask for a single relative defining polynomial with an optional
  flag~$=1$.
\begin{verbatim}
? bnrclassfield(bnf,,1)
% = x^9 + 18*x^7 + ...
\end{verbatim}
  We can also ask for a single absolute defining polynomial with an optional
  flag~$=2$.
\begin{verbatim}
? bnrclassfield(bnf,,2)
% = x^18 + 36*x^16 + 4860*x^14 + ...
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Ray class groups}
  We compute general ray class groups with~\texttt{bnrinit}.
\begin{verbatim}
? pr = idealprimedec(bnf,13)[1];
? bnr = bnrinit(bnf,pr); bnr.cyc
% = [18, 3]
\end{verbatim}
  This ray class group is isomorphic to~$\ZZ/18\ZZ\times\ZZ/3\ZZ$.
  We can compute the discriminant of the corresponding extension in advance
  with~\texttt{bnrdisc}.
\begin{verbatim}
? [deg,r1,D] = bnrdisc(bnr);
? deg
%59 = 108
? D
% = 625833566280085268...18199167302475256851237
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Ray class fields}
\begin{verbatim}
? ext2 = bnrclassfield(bnr)
% = [x^2 + (y + 34), x^3 + ..., x^9 + ...]
\end{verbatim}
  Again, the ray class field is expressed as a compositum of several extensions.

  \medskip

  We can simplify the relative defining polynomials with~\texttt{rnfpolredbest}.
\begin{verbatim}
? apply(P -> lift(rnfpolredbest(bnf,P)), ext2)
% = [x^2 + (y + 34), x^3 - 24*x + (2*y - 1),
x^9 - x^8 + (-y - 5)*x^7 + ... + (-262*y + 10515)]
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Ray class fields}
  Again, we can ask for an absolute defining polynomial.
\begin{verbatim}
? ext2b = bnrclassfield(bnr,,2)
% = x^108 + 24*x^107 + 229*x^106 - 128*x^105 - ...
\end{verbatim}
  We can check that the discriminant is correct with~\texttt{nfdisc}.
\begin{verbatim}
? nfdisc([ext2b,1000]) == D
% = 1
\end{verbatim}
  Note that this is much more expensive than with~\texttt{bnrdisc}, and we
  needed to help~\texttt{nfdisc} by forcing it to use a lazy factorisation.
\end{frame}

\begin{frame}[fragile]{General class fields}
  In general we describe the desired Abelian extension as the subfield of a ray class
  field fixed by a subgroup of~$\Cl_K(\mathfrak{m})$.
\begin{verbatim}
? pr2 = idealprimedec(bnf,2)[1];
? bnr2 = bnrinit(bnf,[pr,1;pr2,3]); bnr2.cyc
% = [36, 12, 6]
? H2 = [2,1,1;0,2,0;0,0,1]
% = 
[2 1 1]
[0 2 0]
[0 0 1]
? bnrclassfield(bnr2,H2)
% = [x^4 + 78*x^2 + (-92*y + 1396)]
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Shortcut for describing the subgroup}
  We can use the shortcut~\texttt{bnrclassfield(bnr,n)} to denote the
  subgroup~$n\cdot\Cl_K(\mathfrak{m})$.
\begin{verbatim}
? ext3 = bnrclassfield(bnr2,3)
% = [x^3 - 15*x + ..., x^3 + ..., x^3 + ...]
\end{verbatim}
  This is the maximal elementary Abelian $3$-subextension.

\begin{verbatim}
? ext3 = bnrclassfield(bnr2,9)
% = [x^3 + ..., x^3 + ..., x^9 + ...]
\end{verbatim}
  This is the maximal Abelian subextension with exponent dividing~$9$.
\end{frame}

\begin{frame}[fragile]{Without the explicit field}
  Computing a defining polynomial with~\texttt{bnrclassfield} can be
  time-consuming, so it is better to compute the relevant information without
  constructing the field, if possible.
  
  \smallskip
  
  We already saw the use of \texttt{bnrdisc}; we can also compute splitting
  information without the explicit field.
\begin{verbatim}
? pr313 = idealprimedec(bnf,313)[1];
? bnrisprincipal(bnr2,pr313,0)
% = [0, 0, 0]~
\end{verbatim}
  The Frobenius at~$\p_{313}$ is trivial: this prime splits completely in the
  degree~$36\cdot 12\cdot 6 = 2592$ extension (which we did not compute).
\end{frame}

\begin{frame}[fragile]{Modulus with infinite places}
  If the base field has real places, we can specify the modulus at infinity by
  providing a list of~$0$ or~$1$ of length the number of real embeddings.
\begin{verbatim}
? bnf2 = bnfinit(y^2-217);
? bnf2.cyc
% = []
? bnrinit(bnf2,1).cyc
% = []
? bnr3 = bnrinit(bnf2,[1,[1,1]]); bnr3.cyc
% = [2]
\end{verbatim}
  The field~$\QQ(\sqrt{217})$ has narrow class number~$2$.
\end{frame}

\begin{frame}[fragile]{A narrow Hilbert class field}
  We check that the class field has the expected properties:
\begin{verbatim}
? [deg,r1,D] = bnrdisc(bnr3);
? [deg,r1]
% = [4, 0]
? D
% = 47089
? bnrclassfield(bnr3)
% = [x^2 + (-260952*y + 3844063)]
? pol5 = bnrclassfield(bnr3,,2)
% = x^4 + 7688126*x^2 + 1
? polsturm(pol5)
% = 0
? nfdisc(pol5) == D
% = 1
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Questions ?}
  \begin{center}
  {\Large Have fun!}
  \end{center}
\end{frame}

\end{document}

