af_code.tex (15894B)
1 \documentclass[10pt,a4paper]{report} 2 \usepackage[utf8]{inputenc} 3 \usepackage{amsmath} 4 \usepackage{amsthm} 5 \usepackage[all]{xy} 6 \usepackage{amsfonts} 7 \usepackage{color} 8 \usepackage{amssymb} 9 \usepackage{float} 10 \usepackage[a4paper, top=3cm, bottom=3cm, left=2.5cm, right=2.5cm]{geometry} 11 \usepackage{listings} 12 \usepackage{algorithm} 13 %\usepackage{algorithmic} 14 \usepackage{algpseudocode} 15 16 \DeclareMathOperator{\alg}{alg} 17 \DeclareMathOperator{\obj}{Obj} 18 \DeclareMathOperator{\Hom}{Hom} 19 \DeclareMathOperator{\End}{End} 20 \DeclareMathOperator{\hol}{Hol} 21 \DeclareMathOperator{\aut}{Aut} 22 \DeclareMathOperator{\gal}{Gal} 23 \DeclareMathOperator{\id}{id} 24 \DeclareMathOperator{\res}{res} 25 \DeclareMathOperator{\im}{Im} 26 \DeclareMathOperator{\Id}{Id} 27 \DeclareMathOperator{\fib}{Fib} 28 \DeclareMathOperator{\spec}{Spec} 29 \DeclareMathOperator{\proj}{Proj} 30 \DeclareMathOperator{\trdeg}{trdeg} 31 \DeclareMathOperator{\car}{char} 32 \DeclareMathOperator{\Frac}{Frac} 33 \DeclareMathOperator{\reduced}{red} 34 \DeclareMathOperator{\real}{Re} 35 \DeclareMathOperator{\imag}{Im} 36 \DeclareMathOperator{\vol}{vol} 37 \DeclareMathOperator{\den}{den} 38 \DeclareMathOperator{\rank}{rank} 39 \DeclareMathOperator{\lcm}{lcm} 40 \DeclareMathOperator{\rad}{rad} 41 \DeclareMathOperator{\ord}{ord} 42 \DeclareMathOperator{\Br}{Br} 43 \DeclareMathOperator{\inv}{inv} 44 \DeclareMathOperator{\Nm}{Nm} 45 \DeclareMathOperator{\Tr}{Tr} 46 \DeclareMathOperator{\an}{an} 47 \DeclareMathOperator{\op}{op} 48 \DeclareMathOperator{\sep}{sep} 49 \DeclareMathOperator{\unr}{unr} 50 \DeclareMathOperator{\et}{\acute et} 51 \DeclareMathOperator{\ev}{ev} 52 \DeclareMathOperator{\gl}{GL} 53 \DeclareMathOperator{\SL}{SL} 54 \DeclareMathOperator{\mat}{Mat} 55 \DeclareMathOperator{\ab}{ab} 56 \DeclareMathOperator{\tors}{tors} 57 \DeclareMathOperator{\ed}{ed} 58 59 \newcommand{\grp}{\textsc{Grp}} 60 \newcommand{\set}{\textsc{Set}} 61 \newcommand{\x}{\mathbf{x}} 62 \newcommand{\naturalto}{\overset{.}{\to}} 63 \newcommand{\qbar}{\overline{\mathbb{Q}}} 64 \newcommand{\zbar}{\overline{\mathbb{Z}}} 65 66 \newcommand{\pro}{\mathbb{P}} 67 \newcommand{\aff}{\mathbb{A}} 68 \newcommand{\quat}{\mathbb{H}} 69 \newcommand{\rea}{\mathbb{R}} 70 \newcommand{\kiu}{\mathbb{Q}} 71 \newcommand{\F}{\mathbb{F}} 72 \newcommand{\zee}{\mathbb{Z}} 73 \newcommand{\ow}{\mathcal{O}} 74 \newcommand{\mcx}{\mathcal{X}} 75 \newcommand{\mcy}{\mathcal{Y}} 76 \newcommand{\mcs}{\mathcal{S}} 77 \newcommand{\mca}{\mathcal{A}} 78 \newcommand{\mcb}{\mathcal{B}} 79 \newcommand{\mcf}{\mathcal{F}} 80 \newcommand{\mcg}{\mathcal{G}} 81 \newcommand{\mct}{\mathcal{T}} 82 \newcommand{\mcq}{\mathcal{Q}} 83 \newcommand{\mcr}{\mathcal{R}} 84 \newcommand{\adl}{\mathbf{A}} 85 \newcommand{\mbk}{\mathbf{k}} 86 \newcommand{\m}{\mathfrak{m}} 87 \newcommand{\p}{\mathfrak{p}} 88 89 \newcommand{\kbar}{\overline{K}} 90 91 \newtheorem{lemma}{Lemma} 92 \newtheorem{proposition}[lemma]{Proposition} 93 \newtheorem{conjecture}[lemma]{Conjecture} 94 \newtheorem{corollary}[lemma]{Corollary} 95 \newtheorem{definition}[lemma]{Definition} 96 \newtheorem{theorem}[lemma]{Theorem} 97 \newtheorem{cond-thm}[lemma]{Conditional Theorem} 98 \theoremstyle{definition} 99 \newtheorem{remark}[lemma]{Remark} 100 101 %\author{Sebastiano Tronto} 102 \title{Computation of the adelic failure} 103 104 105 \begin{document} 106 107 \chapter*{Computation of the adelic failure} 108 109 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. 110 111 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. 112 113 \section*{The SageMath code} 114 115 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: 116 \begin{itemize} 117 \item Each element of $B_i=\{B_{i,0},\dots,B_{i,t_i}\}$ has $2$-divisibility $i$, using the terminology of \cite{DebryPerucca}. 118 \item $\mathcal{B}=\bigcup_{i=1}^t B_i$ is a $2$-maximal basis for $G$. 119 \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$. 120 \end{itemize} 121 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 122 \begin{align*} 123 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]. 124 \end{align*} 125 126 %\lstset{language=Python} 127 %\begin{lstlisting} 128 %def adelic_failure_gb( B, d ): 129 % 130 % ad_fail = [] # The table to be returned at the end. 131 % 132 % if d == len(B)-1: 133 % N = max(3,len(B)+1) 134 % else: 135 % N = max(3,len(B)) 136 % 137 % # The shortlist grows at each step, so we build it incrementally. 138 % shortlist = [] 139 % # The "special element" is (n,b) = \zeta_{2^n}\sqrt{b}. 140 % special_element = (1,1) 141 % 142 % M = 1 # M also grows with n. 143 % 144 % for n in range( 1, N+1 ): # Read as: 1 \leq n \leq N 145 % 146 % # We add the new elements to the shortlist, modifying M if needed. 147 % # This is not done in case we are in the extra "fake" level. 148 % if n-1 < len(B): 149 % for g in B[n-1]: 150 % if g < 0 and n > 1: 151 % special_element = ( n+1, abs(g)^(1/(2^(n-1))) ) 152 % M = lcm( M, special_embed( special_element ) ) 153 % else: 154 % b = g^(1/(2^(n-1))) # b is 2-indivisible 155 % shortlist.append( b ) 156 % M = lcm( M, cyc_embed(b) ) 157 % 158 % # We add a root of an even power of the negative generator, as soon as 159 % # we are beyond its level. 160 % if d != -1 and n == d+2: 161 % b = abs(B[d][0])^(1/2^d) 162 % shortlist.append( b ) 163 % M = lcm( M, cyc_embed(b) ) 164 % 165 % M = lcm(M,2^n) 166 % 167 % if n <= d: 168 % M = lcm( M, 2^(n+1) ) 169 % 170 % if n == 1 and d >= 1: 171 % shortlist.append(-1) 172 % if n > 1 and -1 in shortlist: 173 % shortlist.remove(-1) 174 % 175 % aux = [] # Next line of ad_fail table 176 % 177 % for dM in divisors( M ): 178 % if dM % (2^n) != 0: 179 % continue 180 % 181 % S = [ product(s) for s in subsets( shortlist ) ] 182 % H = [ cyc_embed( s ) for s in S ] 183 % r = len( [ b for b in H if dM % b == 0 ] ) 184 % 185 % if n <= d and dM % (2^(n+1)) == 0 and n > 1: 186 % r *= 2 187 % 188 % if 8 in H and dM % 8 == 0 and (n >= 3 or (n == 2 and n <= d)): 189 % r = r/2 190 % 191 % if special_element != (1,1) and special_element[0] == n+1: 192 % nothing_to_do = False 193 % intersecting_QdM = False 194 % for s in S: 195 % new_special = ( n+1, special_element[1] * s ) 196 % m = special_embed( new_special ) 197 % if n == 2 and m == 4: # \zeta_8 times 2 times square 198 % nothing_to_do = True 199 % if dM % m == 0: 200 % intersecting_QdM = True 201 % if intersecting_QdM and not nothing_to_do: 202 % r *= 2 203 % 204 % aux.append( (dM,r) ) 205 % 206 % ad_fail.append(aux) 207 % 208 % return ad_fail 209 %\end{lstlisting} 210 % 211 %We have used the following auxiliary functions: 212 % 213 %\begin{lstlisting} 214 %# Computes the minimal cyclotomic field containing \sqrt(b) 215 %def cyc_embed( b ): 216 % m = squarefree_part(b) 217 % if m%4 != 1: 218 % m *= 4 219 % return abs(m) 220 % 221 %# Computes the minimal cyclotomic field containing \zeta_{2^n}\sqrt(b) 222 %def special_embed( (n,b) ): 223 % m = squarefree_part(b) 224 % if n == 3 and m % 2 == 0: 225 % return 4 * cyc_embed(m/2) 226 % else: 227 % return lcm( 2^n, cyc_embed(b) ) 228 %\end{lstlisting} 229 \pagebreak 230 231 \section*{The pseudo-code} 232 We translate the SageMath code into pseudocode for ease of readability. 233 234 \begin{algorithm} 235 \caption{Compute the adelic failure} 236 \begin{algorithmic} 237 \State Let $B$, $t$, $d$ and $N$ as described in the previous section 238 \State Let $M\leftarrow1$, $\texttt{special\_element}\leftarrow1$ and $\texttt{shortlist}\leftarrow[\,]$ 239 240 \State 241 242 \For {$n=1$ to $N$} 243 \If{$n-1<t$} 244 \For{$g\in B_{n-1}$} 245 \If{$g<0$ and $n>1$} 246 \State $\texttt{special\_element}\leftarrow(n+1,\sqrt[2^{n-1}]{|g|})$ 247 \State $M\leftarrow\lcm(M,\texttt{special\_embed}(\texttt{special\_element}))$ 248 \Else 249 \State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} 250 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ 251 \EndIf 252 \EndFor 253 \EndIf 254 255 \State 256 257 \If{$n=d+2$ and $d\neq -1$} 258 \State Add $\sqrt[2^{d}]{|B_{d,0}|}$ to \texttt{shortlist} 259 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(|B_{d,0}|))$ 260 \EndIf 261 262 \State 263 \If{$n\leq d$} 264 \State $M\leftarrow\lcm(M,2^{n+1})$ 265 \Else 266 \State $M\leftarrow\lcm(M,2^n)$ 267 \EndIf 268 \State 269 270 \If{$n=1$ and $d\geq 1$} 271 \State Add $-1$ to \texttt{shortlist} 272 \EndIf 273 \State 274 \If{$n>1$} 275 \State Remove $-1$ from \texttt{shortlist} (if present) 276 \EndIf 277 \State 278 \algstore{alg1} 279 \end{algorithmic} 280 \end{algorithm} 281 \pagebreak 282 283 \begin{algorithm} 284 \begin{algorithmic} 285 \algrestore{alg1} 286 \ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} 287 \State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ 288 \State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ 289 \State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ 290 \State 291 \If{$q<n\leq d$ and $2^{n+1}\,|\,{d_M}$} 292 \State $r\leftarrow 2r$ 293 \EndIf 294 \State 295 \If{$8\in H$ and $8\,|\,d_M$ and (either $n\geq 3$ or $n=2\leq d$)} 296 \State $r\leftarrow r/2$ 297 \EndIf 298 \State 299 300 \If{$\texttt{special\_element}=\zeta_{2^{n+1}}\sqrt{b}$ for some $b\in\mathbb{Q}$} 301 \State $\texttt{specials}\leftarrow\{\zeta_{2^{n+1}}\sqrt{bs}\,|\,s\in S\}$ 302 \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}$} 303 \State $r\leftarrow 2r$ 304 \EndIf 305 \EndIf 306 \State 307 \State Declare $\left[\mathbb{Q}_{2^n}\left(\sqrt[2^n]{G}\right)\cap \mathbb{Q}_{d_M}:\mathbb{Q}_{2^n}\right]=r$. 308 309 \EndFor 310 \EndFor 311 \end{algorithmic} 312 \end{algorithm} 313 314 \pagebreak 315 316 \section*{Pseudo-code, the sub-cases} 317 318 We divide the pseudocode in sub-cases. In each sub-case we apply the trivial simplifications to the pseudo-code above. 319 320 \subsection*{Case $G\leq \mathbb{Q}_+^\times$} 321 322 \begin{algorithm} 323 \caption{Adelic failure, case $G\leq \mathbb{Q}^\times$} 324 325 \begin{algorithmic} 326 \For {$n=1$ to $N$} 327 \For{$g\in B_{n-1}$} 328 \State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} 329 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ 330 \EndFor 331 \State 332 \State $M\leftarrow\lcm(M,2^n)$ 333 \State 334 \ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} 335 \State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ 336 \State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ 337 \State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ 338 %\State 339 \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} 340 r/2&\text{ if }8\in H\text{ and }n\geq 3,\\ 341 r&\text{ otherwise}. 342 \end{cases}$ 343 \EndFor 344 \EndFor 345 \end{algorithmic} 346 347 \end{algorithm} 348 \pagebreak 349 \subsection*{Case $d\neq -1$, $n\leq d$} 350 For this and the following cases, we assume we are already inside the main \texttt{for} cycle, since we have particular assumptions on $n$. 351 \begin{algorithm} 352 \caption{Adelic failure, case $d\neq -1$, $n\leq d$} 353 \begin{algorithmic} 354 \For{$g\in B_{n-1}$} 355 \State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} 356 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ 357 \EndFor 358 \State 359 \State $M\leftarrow\lcm(M,2^{n+1})$ 360 \State 361 \If{$n=1$ and $d\geq 1$} 362 \State Add $-1$ to \texttt{shortlist} 363 \EndIf 364 \State 365 \If{$n>1$} 366 \State Remove $-1$ from \texttt{shortlist} (if present) 367 \EndIf 368 \State 369 \ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} 370 \State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ 371 \State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ 372 \State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ 373 \State 374 \If{$n>1$ and $2^{n+1}\,|\,d_M$} 375 \State $r\leftarrow 2r$ 376 \EndIf 377 \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} 378 r/2&\text{ if }8\in H\text{ and }n\geq 3,\\ 379 r/2&\text{ if }8\in H\text{ and }n=2\text{ and }8\,|\,d_M\\ 380 r&\text{ otherwise}. 381 \end{cases}$ 382 \EndFor 383 \end{algorithmic} 384 385 \end{algorithm} 386 387 388 \pagebreak 389 \subsection*{Case $d\neq -1$, $n\geq d+2$} 390 391 \begin{algorithm} 392 \caption{Adelic failure, case $d\neq -1$, $n\geq d+2$} 393 \begin{algorithmic} 394 \If{$n-1<t$} 395 \For{$g\in B_{n-1}$} 396 \State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} 397 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ 398 \EndFor 399 \EndIf 400 \State 401 402 \If{$n=d+2$} 403 \State Add $\sqrt[2^{d}]{|B_{d,0}|}$ to \texttt{shortlist} 404 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(|B_{d,0}|))$ 405 \EndIf 406 407 \State 408 \State $M\leftarrow\lcm(M,2^{n})$ 409 \State 410 \ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} 411 \State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ 412 \State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ 413 \State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ 414 \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} 415 r/2&\text{ if }8\in H,\\ 416 r&\text{ otherwise}. 417 \end{cases}$ 418 \EndFor 419 \end{algorithmic} 420 421 \end{algorithm} 422 423 \pagebreak 424 425 \subsection*{Case $d\neq -1$, $n= d+1$} 426 427 \begin{algorithm} 428 \caption{Adelic failure, case $d\neq -1$, $n= d+1$} 429 \begin{algorithmic} 430 \For{$g\in B_{n-1}$} 431 \If{$g<0$} 432 \State $\texttt{special\_element}\leftarrow(n+1,\sqrt[2^{n-1}]{|g|})$ 433 \State $M\leftarrow\lcm(M,\texttt{special\_embed}(\texttt{special\_element}))$ 434 \Else 435 \State Add $\sqrt[2^{n-1}]{g}$ to \texttt{shortlist} 436 \State $M\leftarrow\lcm(M,\texttt{cyc\_embed}(g))$ 437 \EndIf 438 \EndFor 439 \State 440 \State $M\leftarrow\lcm(M,2^{n})$ 441 \State 442 \State Remove $-1$ from \texttt{shortlist} (if present) 443 444 445 \State 446 \ForAll{$d_M\in \texttt{divisors}(M)$ such that $2^n\,|\,M$} 447 \State $S\leftarrow\left\{\prod_{x\in T}x\,|\,T\subseteq\texttt{shortlist}\right\}$ 448 \State $H\leftarrow\left\{\min\left\{x\in\mathbb{Z}_{>0}\,|\sqrt{s}\in \mathbb{Q}_x\right\}\,|\,s\in S\right\}$ 449 \State $r\leftarrow\# \left\{s\in S\,|\, \sqrt{s}\in\mathbb{Q}_{d_M}\right\}$ 450 \State 451 %\State $\texttt{specials}\leftarrow\{\zeta_{2^{n+1}}\sqrt{bs}\,|\,s\in S\}$ 452 \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}$} 453 \State $r\leftarrow 2r$ 454 \EndIf 455 \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} 456 r/2&\text{ if }8\in H\text{ and }n\geq 3,\\ 457 r&\text{ otherwise}. 458 \end{cases}$ 459 \EndFor 460 \end{algorithmic} 461 462 \end{algorithm} 463 464 \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 465 466 \bibitem{DebryPerucca} 467 \textsc{Debry, C. - Perucca, A.}: \emph{Reductions of algebraic integers}, J. Number Theory, {\bf 167} (2016), 259--283. 468 469 \bibitem{PST1} 470 \textsc{Perucca, A. - Sgobba, P. - Tronto, S.}: \emph{Explicit Kummer Theory for the rational numbers}, preprint. 471 472 \end{thebibliography} 473 474 \end{document}