path: root/tex/af_code.tex

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