From 1437da00eeb4a7581df1b54ffc7680ffb491d690 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 15 Feb 2021 11:30:51 +0100 Subject: Fixed for python3 --- tex/af_code.tex | 474 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 474 insertions(+) create mode 100644 tex/af_code.tex (limited to 'tex/af_code.tex') 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-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{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 -- cgit v1.3