path: root/docs/af_code.tex

\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-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}

\section{Pseudocode, the sub-cases}

We divide the pseudocode in sub-cases.

\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{PeruccaSgobba}  
%\textsc{Perucca, A. - Sgobba, P.}: \emph{Kummer Theory for Number Fields}, preprint.

\end{thebibliography}

\end{document}