From 3062ce67bb0240a47841bfb954ca79a2d8d64768 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 19 Apr 2019 12:00:04 +0200 Subject: Added documentation --- docs/af_code.tex | 466 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 466 insertions(+) create mode 100644 docs/af_code.tex (limited to 'docs/af_code.tex') diff --git a/docs/af_code.tex b/docs/af_code.tex new file mode 100644 index 0000000..eefb98f --- /dev/null +++ b/docs/af_code.tex @@ -0,0 +1,466 @@ +\documentclass[10pt,a4paper]{article} +\usepackage[utf8]{inputenc} +\usepackage{amsmath} +\usepackage{amsthm} +\usepackage[all]{xy} +\usepackage{amsfonts} +\usepackage{color} +\usepackage{amssymb} +\usepackage{float} +\usepackage[a4paper, top=3cm, bottom=3cm, left=2.5cm, right=2.5cm]{geometry} +\usepackage{listings} +\usepackage{algorithm} +%\usepackage{algorithmic} +\usepackage{algpseudocode} + +\DeclareMathOperator{\alg}{alg} +\DeclareMathOperator{\obj}{Obj} +\DeclareMathOperator{\Hom}{Hom} +\DeclareMathOperator{\End}{End} +\DeclareMathOperator{\hol}{Hol} +\DeclareMathOperator{\aut}{Aut} +\DeclareMathOperator{\gal}{Gal} +\DeclareMathOperator{\id}{id} +\DeclareMathOperator{\res}{res} +\DeclareMathOperator{\im}{Im} +\DeclareMathOperator{\Id}{Id} +\DeclareMathOperator{\fib}{Fib} +\DeclareMathOperator{\spec}{Spec} +\DeclareMathOperator{\proj}{Proj} +\DeclareMathOperator{\trdeg}{trdeg} +\DeclareMathOperator{\car}{char} +\DeclareMathOperator{\Frac}{Frac} +\DeclareMathOperator{\reduced}{red} +\DeclareMathOperator{\real}{Re} +\DeclareMathOperator{\imag}{Im} +\DeclareMathOperator{\vol}{vol} +\DeclareMathOperator{\den}{den} +\DeclareMathOperator{\rank}{rank} +\DeclareMathOperator{\lcm}{lcm} +\DeclareMathOperator{\rad}{rad} +\DeclareMathOperator{\ord}{ord} +\DeclareMathOperator{\Br}{Br} +\DeclareMathOperator{\inv}{inv} +\DeclareMathOperator{\Nm}{Nm} +\DeclareMathOperator{\Tr}{Tr} +\DeclareMathOperator{\an}{an} +\DeclareMathOperator{\op}{op} +\DeclareMathOperator{\sep}{sep} +\DeclareMathOperator{\unr}{unr} +\DeclareMathOperator{\et}{\acute et} +\DeclareMathOperator{\ev}{ev} +\DeclareMathOperator{\gl}{GL} +\DeclareMathOperator{\SL}{SL} +\DeclareMathOperator{\mat}{Mat} +\DeclareMathOperator{\ab}{ab} +\DeclareMathOperator{\tors}{tors} +\DeclareMathOperator{\ed}{ed} + +\newcommand{\grp}{\textsc{Grp}} +\newcommand{\set}{\textsc{Set}} +\newcommand{\x}{\mathbf{x}} +\newcommand{\naturalto}{\overset{.}{\to}} +\newcommand{\qbar}{\overline{\mathbb{Q}}} +\newcommand{\zbar}{\overline{\mathbb{Z}}} + +\newcommand{\pro}{\mathbb{P}} +\newcommand{\aff}{\mathbb{A}} +\newcommand{\quat}{\mathbb{H}} +\newcommand{\rea}{\mathbb{R}} +\newcommand{\kiu}{\mathbb{Q}} +\newcommand{\F}{\mathbb{F}} +\newcommand{\zee}{\mathbb{Z}} +\newcommand{\ow}{\mathcal{O}} +\newcommand{\mcx}{\mathcal{X}} +\newcommand{\mcy}{\mathcal{Y}} +\newcommand{\mcs}{\mathcal{S}} +\newcommand{\mca}{\mathcal{A}} +\newcommand{\mcb}{\mathcal{B}} +\newcommand{\mcf}{\mathcal{F}} +\newcommand{\mcg}{\mathcal{G}} +\newcommand{\mct}{\mathcal{T}} +\newcommand{\mcq}{\mathcal{Q}} +\newcommand{\mcr}{\mathcal{R}} +\newcommand{\adl}{\mathbf{A}} +\newcommand{\mbk}{\mathbf{k}} +\newcommand{\m}{\mathfrak{m}} +\newcommand{\p}{\mathfrak{p}} + +\newcommand{\kbar}{\overline{K}} + +\newtheorem{lemma}{Lemma} +\newtheorem{proposition}[lemma]{Proposition} +\newtheorem{conjecture}[lemma]{Conjecture} +\newtheorem{corollary}[lemma]{Corollary} +\newtheorem{definition}[lemma]{Definition} +\newtheorem{theorem}[lemma]{Theorem} +\newtheorem{cond-thm}[lemma]{Conditional Theorem} +\theoremstyle{definition} +\newtheorem{remark}[lemma]{Remark} + +\author{Sebastiano Tronto} + + +\begin{document} + +We begin by giving the code for the function that computes the adelic failure, both in SageMath and in pseudocode. Then we procede to breaking it down into different subcases, in order to check that it computes the correct values. + +\section{The SageMath Code} + +The function \texttt{adelic\_failure\_gb} takes two parameters as input: a list $B=\{B_0,\dots, B_t\}$ and an integer $d$. Each $B_i$ is itself a list of elements of $G$, and we require the following: +\begin{itemize} +\item Each element of $B_i=\{B_{i,0},\dots,B_{i,t_i}\}$ has $2$-divisibility $i$, using the terminology of \cite{DebryPerucca}. +\item $\mathcal{B}=\bigcup_{i=1}^t B_i$ is a $2$-maximal basis for $G$. +\item The integer $d$ is either $-1$ or $1\leq d\leq t$. For $i\in\{1,\dots,t\}\setminus\{d\}$ we have $B_i\subseteq \mathbb{Q}_+$. If $d\neq -1$ we have $B_{d,0}<0$ and $B_{d,j}>0$ for $j\neq 0$. +\end{itemize} +The output is a list $A=\{A_1,\dots,A_{N_0}\}$, where each $A_n=\{A_{n,0},\dots,A_{n,r_n}\}$ is a list of pairs $A_{n,i}=(d_{n,i},f_{n,i})$. We have $N_0=\max(3,t+1)$ if $d=t$, while $N_0=\max(3,t)$ otherwise. For each $1\leq n\leq N_0$ and each $i\leq r_n$, the integer $d_{n,i}$ is a divisor of $M_0=d_{N_0,r_{N_0}}$ and a multiple of $2^i$, and $f_{n,i}$ is the ``adelic failure'' (old definition), i.e.: +\begin{align*} +f_{n,i}=\left[\mathbb{Q}_{2^i}\left(G^{1/2^i}\right)\cap \mathbb{Q}_{d_{i,n}}:\mathbb{Q}_{2^i}\right]. +\end{align*} + +\lstset{language=Python} +\begin{lstlisting} +def adelic_failure_gb( B, d ): + + ad_fail = [] # The table to be returned at the end. + + if d == len(B)-1: + N = max(3,len(B)+1) + else: + N = max(3,len(B)) + + # The shortlist grows at each step, so we build it incrementally. + shortlist = [] + # The "special element" is (n,b) = \zeta_{2^n}\sqrt{b}. + special_element = (1,1) + + M = 1 # M also grows with n. + + for n in range( 1, N+1 ): # Read as: 1 \leq n \leq N + + # We add the new elements to the shortlist, modifying M if needed. + # This is not done in case we are in the extra "fake" level. + if n-1 < len(B): + for g in B[n-1]: + if g < 0 and n > 1: + special_element = ( n+1, abs(g)^(1/(2^(n-1))) ) + M = lcm( M, special_embed( special_element ) ) + else: + b = g^(1/(2^(n-1))) # b is 2-indivisible + shortlist.append( b ) + M = lcm( M, cyc_embed(b) ) + + # We add a root of an even power of the negative generator, as soon as + # we are beyond its level. + if d != -1 and n == d+2: + b = abs(B[d][0])^(1/2^d) + shortlist.append( b ) + M = lcm( M, cyc_embed(b) ) + + M = lcm(M,2^n) + + if n <= d: + M = lcm( M, 2^(n+1) ) + + if n == 1 and d >= 1: + shortlist.append(-1) + if n > 1 and -1 in shortlist: + shortlist.remove(-1) + + aux = [] # Next line of ad_fail table + + for dM in divisors( M ): + if dM % (2^n) != 0: + continue + + S = [ product(s) for s in subsets( shortlist ) ] + H = [ cyc_embed( s ) for s in S ] + r = len( [ b for b in H if dM % b == 0 ] ) + + if n <= d and dM % (2^(n+1)) == 0 and n > 1: + r *= 2 + + if 8 in H and dM % 8 == 0 and (n >= 3 or (n == 2 and n <= d)): + r = r/2 + + if special_element != (1,1) and special_element[0] == n+1: + nothing_to_do = False + intersecting_QdM = False + for s in S: + new_special = ( n+1, special_element[1] * s ) + m = special_embed( new_special ) + if n == 2 and m == 4: # \zeta_8 times 2 times square + nothing_to_do = True + if dM % m == 0: + intersecting_QdM = True + if intersecting_QdM and not nothing_to_do: + r *= 2 + + aux.append( (dM,r) ) + + ad_fail.append(aux) + + return ad_fail +\end{lstlisting} + +We have used the following auxiliary functions: + +\begin{lstlisting} +# Computes the minimal cyclotomic field containing \sqrt(b) +def cyc_embed( b ): + m = squarefree_part(b) + if m%4 != 1: + m *= 4 + return abs(m) + +# Computes the minimal cyclotomic field containing \zeta_{2^n}\sqrt(b) +def special_embed( (n,b) ): + m = squarefree_part(b) + if n == 3 and m % 2 == 0: + return 4 * cyc_embed(m/2) + else: + return lcm( 2^n, cyc_embed(b) ) +\end{lstlisting} + +\section{The Pseudocode} +We translate the SageMath code into pseudocode for ease of readability. + +\begin{algorithm} +\caption{Compute the adelic failure} +\begin{algorithmic} +\State Let $B$, $t$, $d$ and $N$ as described in the previous section +\State Let $M\leftarrow1$, $\texttt{special\_element}\leftarrow1$ and $\texttt{shortlist}\leftarrow[\,]$ + +\State + +\For {$n=1$ to $N$} +\If{$n-11$} +\State $\texttt{special\_element}\leftarrow(n+1,\sqrt[2^{n-1}]{|g|})$ +\State $M\leftarrow\lcm(M,\texttt{special\_embed}(\texttt{special\_element}))$ +\Else +\State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} +\State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ +\EndIf +\EndFor +\EndIf + +\State + +\If{$n=d+2$ and $d\neq -1$} +\State Add $\sqrt[2^{d}]{|B_{d,0}|}$ to \texttt{shortlist} +\State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(|B_{d,0}|))$ +\EndIf + +\State +\If{$n\leq d$} +\State $M\leftarrow\lcm(M,2^{n+1})$ +\Else +\State $M\leftarrow\lcm(M,2^n)$ +\EndIf +\State + +\If{$n=1$ and $d\geq 1$} +\State Add $-1$ to \texttt{shortlist} +\EndIf +\State +\If{$n>1$} +\State Remove $-1$ from \texttt{shortlist} (if present) +\EndIf +\State +\algstore{alg1} +\end{algorithmic} +\end{algorithm} +\pagebreak + +\begin{algorithm} +\begin{algorithmic} +\algrestore{alg1} +\ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} +\State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ +\State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ +\State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ +\State +\If{$q0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ +\State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ +%\State +\State Declare $\left[\mathbb{Q}_{2^n}\left(\sqrt[2^n]{G}\right)\cap \mathbb{Q}_{d_M}:\mathbb{Q}_{2^n}\right]=\begin{cases} +r/2&\text{ if }8\in H\text{ and }n\geq 3,\\ +r&\text{ otherwise}. +\end{cases}$ +\EndFor +\EndFor +\end{algorithmic} + +\end{algorithm} +\pagebreak +\subsection{Case $d\neq -1$, $n\leq d$} +For this and the following cases, we assume we are already inside the main \texttt{for} cycle, since we have particular assumptions on $n$. +\begin{algorithm} +\caption{Adelic failure, case $d\neq -1$, $n\leq d$} +\begin{algorithmic} +\For{$g\in B_{n-1}$} +\State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} +\State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ +\EndFor +\State +\State $M\leftarrow\lcm(M,2^{n+1})$ +\State +\If{$n=1$ and $d\geq 1$} +\State Add $-1$ to \texttt{shortlist} +\EndIf +\State +\If{$n>1$} +\State Remove $-1$ from \texttt{shortlist} (if present) +\EndIf +\State +\ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} +\State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ +\State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ +\State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ +\State +\If{$n>1$ and $2^{n+1}\,|\,d_M$} +\State $r\leftarrow 2r$ +\EndIf +\State Declare $\left[\mathbb{Q}_{2^n}\left(\sqrt[2^n]{G}\right)\cap \mathbb{Q}_{d_M}:\mathbb{Q}_{2^n}\right]=\begin{cases} +r/2&\text{ if }8\in H\text{ and }n\geq 3,\\ +r/2&\text{ if }8\in H\text{ and }n=2\text{ and }8\,|\,d_M\\ +r&\text{ otherwise}. +\end{cases}$ +\EndFor +\end{algorithmic} + +\end{algorithm} + + +\pagebreak +\subsection{Case $d\neq -1$, $n\geq d+2$} + +\begin{algorithm} +\caption{Adelic failure, case $d\neq -1$, $n\geq d+2$} +\begin{algorithmic} +\If{$n-10}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ +\State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ +\State Declare $\left[\mathbb{Q}_{2^n}\left(\sqrt[2^n]{G}\right)\cap \mathbb{Q}_{d_M}:\mathbb{Q}_{2^n}\right]=\begin{cases} +r/2&\text{ if }8\in H,\\ +r&\text{ otherwise}. +\end{cases}$ +\EndFor +\end{algorithmic} + +\end{algorithm} + +\pagebreak + +\subsection{Case $d\neq -1$, $n= d+1$} + +\begin{algorithm} +\caption{Adelic failure, case $d\neq -1$, $n= d+1$} +\begin{algorithmic} +\For{$g\in B_{n-1}$} +\If{$g<0$} +\State $\texttt{special\_element}\leftarrow(n+1,\sqrt[2^{n-1}]{|g|})$ +\State $M\leftarrow\lcm(M,\texttt{special\_embed}(\texttt{special\_element}))$ +\Else +\State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} +\State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ +\EndIf +\EndFor +\State +\State $M\leftarrow\lcm(M,2^{n})$ +\State +\State Remove $-1$ from \texttt{shortlist} (if present) + + +\State +\ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} +\State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ +\State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ +\State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ +\State +%\State $\texttt{specials}\leftarrow\{\zeta_{2^{n+1}}\sqrt{bs}\,|\,s\in S\}$ +\If{$\exists x\in \{\zeta_{2^{n+1}}\sqrt{bs}\,|\,s\in S\}\cap\mathbb{Q}_{d_M}$ and $\texttt{special\_embed}(s)\neq 4\,\forall s\in\texttt{specials}$} +\State $r\leftarrow 2r$ +\EndIf +\State Declare $\left[\mathbb{Q}_{2^n}\left(\sqrt[2^n]{G}\right)\cap \mathbb{Q}_{d_M}:\mathbb{Q}_{2^n}\right]=\begin{cases} +r/2&\text{ if }8\in H\text{ and }n\geq 3,\\ +r&\text{ otherwise}. +\end{cases}$ +\EndFor +\end{algorithmic} + +\end{algorithm} + +\begin{thebibliography}{10} \expandafter\ifx\csname url\endcsname\relax \def\url#1{\texttt{#1}}\fi \expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi + +\bibitem{DebryPerucca} +\textsc{Debry, C. - Perucca, A.}: \emph{Reductions of algebraic integers}, J. Number Theory, {\bf 167} (2016), 259--283. + +%\bibitem{PeruccaSgobba} +%\textsc{Perucca, A. - Sgobba, P.}: \emph{Kummer Theory for Number Fields}, preprint. + +\end{thebibliography} + +\end{document} \ No newline at end of file -- cgit v1.3