\documentclass[english,notheo]{kbseminar}
\def\kbd#1{\texttt{#1}}
\def\q{\quad}
\def\p{\mathfrak{p}}
\def\U{{U}}
\Logo{\includegraphics[scale=0.15]{logoIMB.eps}\qquad\qquad\quad\includegraphics[scale=0.5]{pari.eps}}

\Place{Atelier PARI/GP 2020 (22/01/2020)}

\title{[Tutorial]\\ $S$-units and compact representations\\in number fields}
\author{Karim Belabas}

\slidesmag{4}

\begin{document}
\maketitle\Logo{}

\begin{slide}{Use case / motivation}
  \bprog
  ? T = x\pow6 + 2854*x\pow4 + 2036329*x\pow2 + 513996528;\\
  ? K = bnfinit(T);\com{$K=\mathbb{Q}[x]/(T)$, require class group and units}\\
  ? K.fu  \com{missing units}\\
  {\blue \% = 0}\\
  ? K = bnfinit(T, 1); \com{impose units computation}\\
  ? K.fu\\
  \com{\dots \emph{\blue huge} result deleted \dots}
  \eprog

  Huge algebraic numbers are problematic because
  \begin{itemize}
  \item computing with them algebraically is expensive;
  \item approximations via floating point embeddings into $\CM$
        require huge accuracy (cancellation);
  \item they are often intermediate results: we do not want a
  result in $K$ but in $K^*/(K^*)^2$, or in $\ZM_K/\p^k$, or a floating point
  approximation to complex embeddings, or \dots
  \item they may overflow the possibilities of the implementation:
  try $2^{2^{100}}$.
  \end{itemize}
\end{slide}

\begin{slide}{Number field structures}
  Let $K = \QM[x]/(T)$ be a number field of degree $[K:\QM] = n$; let
  \begin{itemize}
  \item $(r_1, r_2)$ be its signature, $S_\infty$ be the set of
  $r_1$ real places and $r_2$ complex places,
  \item $\ZM_K = \ZM\cdot b_1 \oplus \dots \oplus \ZM\cdot b_n$
        be its ring of integers and $d_K$ its absolute discriminant,
  \item $\Cl(K)$ be its ideal class group,
  \item $\U(K) = \ZM_K^* \sim (\ZM/w\ZM) \cdot \zeta_w
                \bigoplus \ZM\cdot u_1 \dots
                   \oplus \ZM\cdot u_{r_1 + r_2 - 1}$ be its unit group,
  \item For $S = S_0 \cup S_\infty$ a finite set of places, let 
  $$\U_S(K) = \set{x\in K^*, \text{$v(S) = 0$ for all $v\not\in S$} }$$
  be the $S$-unit group; i.e., $\U_{S_\infty}(K) = \U(K)$. The abelian group
  $\U_S(K)$ is generated by $\zeta_w$ and $\#S - 1$ elements of infinite order.
\end{itemize}
In PARI-speak
\begin{itemize}
% inexpensive, small output
\item \code{K = nfinit(T)} allows \code{K.pol}, \code{K.sign}, \code{K.zk},
\code{K.disc}, \code{K.p} (ramified primes), \dots
% expensive, large output
\item \code{K = bnfinit(T)} further allows \code{K.clgp}, \code{K.tu}
($w,\zeta_w$), \code{K.fu} (fundamental units), \dots 
\end{itemize}
\end{slide}

\begin{slide}{Number field elements}
Elements of $K$ are given as
  \begin{itemize}
    \item elements of $\QM$ (rational form): \code{2}, \code{1/3}, \dots
    \item polynomials (algebraic form): \code{Mod$(1 + x, T)$}, or simply
      $1 + x$ (implicitly modulo $T$), \dots
    \item vectors (basis form): \code{$[a_1,\dots,a_n]\til$} for
      $\sum_i a_i w_i$, \dots
  \end{itemize}
  These formats are recognized as inputs by all functions handling algebraic
  numbers as number field elements. The preferred output format are
  \emph{\blue rational} and \emph{\blue basis} form, in this order.

  \bprog
  ? K = nfinit(x\pow3 - 2);\\
  ? nfeltmul(K, x, x\pow2+1)\\
  ? nfelttrace(K, x+1)\\
  ? nfeltadd(K, x/2, [1,2,3]~)\\
  ? nfbasistoalg(K, \%)\\
  ? nfalgtobasis(K, \%)\\
  \eprog
\end{slide}

\begin{slide}{Other lossy representations}
  For the record, let us mention
  \begin{itemize}
    \item chinese remainders (\code{idealchinese}), including sign conditions
      at real embeddings;
    \item projection to residue fields at maximal ideals (\code{nfmodpr});
    \item complex embeddings (\code{nfeltembed}, floating point);
    \item projections to more general finite rings $(\ZM_K/\mathfrak{f})^*$,
      $\mathfrak{f} = \mathfrak{f_0} \mathfrak{f}_\infty$ (\code{ideallog});
    \item reduction in $K^*/(K^*)^n$ (\code{idealredmodpower}).
    \item factorization into maximal ideals (\code{idealfactor}), up to units;
  \end{itemize}
  These representations alleviate coefficient explosion: they reduce the size
of objects and/or the cost of handling them. But they all lose information.

\end{slide}

\begin{slide}{{\red NEW:} Compact / factored representation (1/2)}
  In multiplicative contexts, an element of the form
  $\prod_i g_i^{e_i}$, where $g_i \in K^*$ and $e_i \in \ZM$, can now be
represented by a factorization matrix.

We do not have a UFD: the $(g_i)$ need not be coprime! The goal is twofold:
\begin{itemize}
\item \emph{\blue avoid coefficient explosion}, measured by the size of the
internal representation: compare $2^{1000} \cdot 3^{-2000}$ with its expanded
form.

\item reduce costs of operations \emph{\blue in multiplicative contexts}:
it is easy to multiply or divide formally such objects, reduce modulo
squares or larger powers, compute valuations, etc. More generally apply group
morphisms $(K^*,\times) \to G$.
\end{itemize}
\end{slide}

\begin{slide}{{\red NEW:} Compact / factored representation (2/2)}
There are drawbacks:
\begin{itemize}
\item non-multiplicative operations remain expensive, for instance to perform
addition we must expand the products first;
\item some of them lose useful properties, for instant equality testing:
a fast probabilistic algorithm proves that $\prod g_i^{e_i} \neq 1$, but it
is hard to prove equality (the $g_i$ are not coprime); failing to disprove
equality, we may \emph{assume} equality but we lose guarantees for later
steps.

\item non-generic simplifications are not taken into account: when expanded
outputs \emph{are} small, factored representations are likely to be
\emph{larger};

\item backward compatibility !
\end{itemize}
\end{slide}

\begin{slide}{What does it change ? How to use it ? (1/2)}

High level functions transparently use the mechanism behind the scenes
(\kbd{bnrclassfield}, \kbd{bnrstark}, \kbd{bnflog}, \kbd{thue}\dots),
whenever units or class group computations arise.

\begin{itemize}
\item By default, when handling a \code{bnf = bnfinit$(T)$} provided by the
user, this strategy is {\blue less efficient} that it could be. It can fail
because \code{bnf} contains floating point data that may not always allow
exact algebraic reconstructions. It may also contain huge units in expanded
form that contaminate later constructions.

\item \code{bnf = bnfinit$(T, 1)$} makes the strategy foolproof for that
\code{bnf}, by computing all data in exact algebraic form, using factored
representations. {\blue Drawback:} uses much more memory, and is slower in
the worst case although this is not noticeable on average in our tests.

\end{itemize}
We advise to use \code{bnfinit(,1)} for all computations and only
disable it when it causes \kbd{bnfinit} to run into problems.
\end{slide}

\begin{slide}{What does it change ? How to use it ? (2/2)}

Caveats / compatibility:
\begin{itemize}
\item \code{bnf.fu} is specified to return units in {\blue expanded} form.
So use the new \code{bnfunits} instead, which returns units in {\blue
factored} form (and extra information for \kbd{bnfisunit}).

\item  \kbd{bnfisprincipal} is specified to return principal ideals in
{\blue expanded} form. So use the new \code{bnfisprincipal(,4)} flag.
\end{itemize}

Example: some random real quadratic field. Try these
snippets with \kbd{bnfinit} instead of \kbd{bnfinit(,1)}.\\
\bprog
D = 1000001273;\\
K = bnfinit(x\pow2 - D, 1);\\
bnfunits(K)\\
K.fu\\
\\ 
P = idealprimedec(K,2)[1];\\
bnfisprincipal(K, P)\\
bnfisprincipal(K, P, 4) \com{factored representation}\\
bnfisprincipal(K, P, 3) \com{expanded; no longer do this !}
\eprog
\end{slide}

\begin{slide}{Addendum: $S$-units}
\code{bnfunits} also allows to work with general $S$-units (together with 
\code{bnfisunit}). The functions \kbd{bnfsunit} and \kbd{bnfissunit} are now
deprecated.

\bprog
S = idealprimedec(K,2);\\
U = bnfunits(K, S)\\
bnfisunit(K, 2)  \q\com{not a unit}\\
bnfisunit(K, 2, U) \com{\dots but an S-unit}
\eprog
\end{slide}

\begin{slide}{Using compact / factored representation}

Functions in multiplicative context work ``out of the box'' with factored
representations.
\bprog
? K = nfinit(x\pow3 - 2);\\
? u = [x, 2; [1,2,3]\til,-1];\\
? v = [x+1, 1; [-1,2,3]\til,2];\\
? nffactorback(K, u)\\
{\blue \%4 = [32/89, 2/89, -11/89]\til}\\
? nfeltmul(K, u, v)\\
{\blue \%5 = \\
\begin{tabular}{lrr}
[&         x & 2]\\\relax
[& [1, 2, 3]~& -1]\\\relax
[&      x + 1 &  1]\\\relax
[&[-1, 2, 3]\til & 2]\\
\end{tabular}}\\
\eprog
\end{slide}

\begin{slide}{Using compact / factored representation}
\bprog
? nfeltpow(K, u, 2)\\
{\blue \%6 = \\
\begin{tabular}{lrr}
[&         x & 4]\\\relax
[&[1, 2, 3]\til & -2]\\
\end{tabular}}\\
? nfeltdiv(K, u, 2)\\
{\blue \%7 = \\
\begin{tabular}{lrr}
[&         x & 2]\\\relax
[&[1, 2, 3]\til & -1]\\\relax
[&         2 &-1]\\
\end{tabular}}\\
? nfeltnorm(K, u)\\
{\blue \%8 = 4/89}\\
\eprog
\end{slide}

\begin{slide}{Using compact / factored representation}
\bprog
? nffactorback(K, [u,v], [2,3]) \com{still factored}\\
{\blue \%9 = \\
\begin{tabular}{lrr}
[&          x & 4]\\\relax
[& [1, 2, 3]\til& -2]\\\relax
[&      x + 1 & 3]\\\relax
[&[-1, 2, 3]\til  & 6]\\
\end{tabular}}\\
? nffactorback(K, \%) \com{now expand completely}\\
{\blue \%10 = [93209292/7921, 57744198/7921, 25490430/7921]\til}\\
? nfelttrace(K, u) \com{not multiplicative ! Fails \dots}\\
? P = idealprimedec(K,5)[2]; nfmodpr(K, v, P) \\
{\blue \%11 = 3*x + 3}\\
? bid = idealstar(K, 5); ideallog(K, v, bid)\\
{\blue \%12 = [7, 0]\til}
\eprog
\end{slide}
\end{document}
