Fixed for python3

1 files changed, 474 insertions, 0 deletions

diff --git a/tex/af_code.tex b/tex/af_code.tex
new file mode 100644
index 0000000..96bd1e6
--- /dev/null
+++ b/tex/af_code.tex
@@ -0,0 +1,474 @@
+\documentclass[10pt,a4paper]{report}
+\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}
+\title{Computation of the adelic failure}
+
+
+\begin{document}
+
+\chapter*{Computation of the adelic failure}
+
+The aim of this document is bridge the gap between the theory developed in \cite{PST1} and the function \texttt{adelic\_failure\_gb} that computes the adelic failure. By reading \cite{PST1}, the pseudo-code in this file and the (commented) SageMath code, one can verify that the script produces the correct results.
+
+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.
+
+\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_n\mid n\text{ divides }N_0\}$, indexed by the positive divisors of $N_0$, where $N_0=\max(3,t+1)$ if $d=t$, while $N_0=\max(3,t)$ otherwise. 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})$. For each $n\mid 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 \emph{adelic failure}, that is the degree
+\begin{align*}
+f_{n,i}=\left[\mathbb{Q}_{2^i}\left(G^{1/2^i}\right)\cap \mathbb{Q}_{d_{n,i}}:\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}
+\pagebreak
+
+\section*{The pseudo-code}
+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-1<t$}
+\For{$g\in B_{n-1}$}
+\If{$g<0$ and $n>1$}
+\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{$q<n\leq d$ and $2^{n+1}\,|\,{d_M}$}
+\State $r\leftarrow 2r$
+\EndIf
+\State
+\If{$8\in H$ and $8\,|\,d_M$ and (either $n\geq 3$ or $n=2\leq d$)}
+\State $r\leftarrow r/2$
+\EndIf
+\State
+
+\If{$\texttt{special\_element}=\zeta_{2^{n+1}}\sqrt{b}$ for some $b\in\mathbb{Q}$}
+\State $\texttt{specials}\leftarrow\{\zeta_{2^{n+1}}\sqrt{bs}\,|\,s\in S\}$
+\If{$\exists x\in \texttt{specials}$ such that $x\in\mathbb{Q}_{d_M}$ and $\texttt{special\_embed}(s)\neq 4\,\forall s\in\texttt{specials}$}
+\State $r\leftarrow 2r$
+\EndIf
+\EndIf
+\State
+\State Declare $\left[\mathbb{Q}_{2^n}\left(\sqrt[2^n]{G}\right)\cap \mathbb{Q}_{d_M}:\mathbb{Q}_{2^n}\right]=r$.
+
+\EndFor
+\EndFor
+\end{algorithmic}
+\end{algorithm}
+
+\pagebreak
+
+\section*{Pseudo-code, the sub-cases}
+
+We divide the pseudocode in sub-cases. In each sub-case we apply the trivial simplifications to the pseudo-code above.
+
+\subsection*{Case $G\leq \mathbb{Q}_+^\times$}
+
+\begin{algorithm}
+\caption{Adelic failure, case $G\leq \mathbb{Q}^\times$}
+
+\begin{algorithmic}
+\For {$n=1$ to $N$}
+\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)$
+\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 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-1<t$}
+\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
+\EndIf
+\State
+
+\If{$n=d+2$}
+\State Add $\sqrt[2^{d}]{|B_{d,0}|}$ to \texttt{shortlist}
+\State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(|B_{d,0}|))$
+\EndIf
+
+\State
+\State $M\leftarrow\lcm(M,2^{n})$
+\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 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{PST1}
+\textsc{Perucca, A. - Sgobba, P. - Tronto, S.}: \emph{Explicit Kummer Theory for the rational numbers}, preprint.
+
+\end{thebibliography}
+
+\end{document}
\ No newline at end of file