Ticket #28094: decomposition.tex

File decomposition.tex, 11.1 KB (added by gh-BrentBaccala, 3 years ago)

LaTex? source of decomposition.pdf

Line 
1
2\documentclass{article}
3
4\usepackage{nopageno}
5
6\usepackage{vmargin}
7\usepackage{times}
8\usepackage{graphics}
9\usepackage{amsmath, amscd, amsxtra, amsthm}
10\usepackage{amssymb}
11\usepackage{framed}
12\usepackage{mdframed}
13\usepackage[dvipsnames]{xcolor}
14\usepackage[retainorgcmds]{IEEEtrantools}
15
16\newtheorem*{lemma}{Lemma}
17
18%% Suggested by http://tex.stackexchange.com/questions/349580
19\usepackage{array}
20
21%% Define a new column declaration
22\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
23
24% These packages are used when embedding Maxima code
25
26\usepackage{breqn}      % auto-break long equations - has to come after pythontex
27\usepackage{listings}
28\usepackage{fancyvrb}
29
30\usepackage{comment}
31%% \usepackage{minted}
32
33% This package makes cut-and-paste of carets work right, so
34% we can cut-and-paste from the PDF document into Maxima.
35
36\usepackage[T1]{fontenc}
37
38
39
40\newcommand{\Bold}[1]{\mathbf{#1}}
41\newcommand{\FF}{\Bold{F}}
42\newcommand{\CC}{\Bold{C}}
43\newcommand{\QQ}{\Bold{Q}}
44\newcommand{\ZZ}{{\mathbb Z}}
45\newcommand{\PP}{{\mathbb P}}
46\newcommand{\Norm}{{\rm Norm}}
47\newcommand{\QQbar}{\overline{\QQ}}
48
49\parindent 0pt
50\parskip 12pt
51
52\begin{document}
53
54
55
56
57\title{Decomposition of ideals in function fields}
58\author{Brent Baccala}
59\date{October 9, 2019}
60\maketitle
61
62%\begin{abstract}
63%\end{abstract}
64
65The {\tt decomposition} method in Sage's {\tt
66  FunctionFieldMaximalOrder\_global} class uses the ``Buchman-Lenstra''
67algorithm described in \cite{cohen} section 6.2.  Buchman-Lenstra,
68however, depends on operations in prime characteristic, and is thus
69only suitable for number fields and function fields over $\FF_p$.
70
71To perform decomposition in characteristic zero, I've developed
72the alternate algorithm described in this paper, and implemented
73in the {\tt decomposition} method of Sage's {\tt FunctionFieldMaximalOrder\_rational} class.
74
75Given a function field $F$ with a maximal order $O$ and an
76algebraic field extension $F'/F$ with maximal order $O' \supset O$.
77We consider a prime ideal $P$ of $O$, and we wish to find the prime
78ideals $P'_1,...,P'_k$ of $O'$ that lie over $P$, in the sense that
79$P^e \subset P'_i$, in fact, $P^e = \cap_i P'_i$, i.e, we seek the
80primary decomposition of $P^e$.
81
82$P^e$ is the extension of $P$ in $O'$, i.e, the ideal of $O'$
83generated by the elements of $P$.  It is not necessarily prime, so the
84quotient ring $O' \bmod P^e$ is not necessarily either a field or an
85integral domain.  It is, however, an Artinian ring and a
86finite-dimensional algebra over the field $O \bmod P$.  Sage's
87finite-dimensional algebra subsystem implements\footnote{Johan Bosman,
88  personal email, June 19, 2019} the algorithm from Section 7 of
89\cite{khuri} to find all of the algebra's maximal ideals (all
90prime ideals of an Artinian ring are also maximal).
91
92$$O \stackrel{\phi}{\rightarrow} O' \stackrel{\psi}{\rightarrow} O'\bmod P^e$$
93
94Thus, we can easily find all maximal ideals of the ring $O' \bmod P^e$.  Since
95the contraction of a maximal ideal is maximal, the maximal ideals of
96$O'\bmod P^e$ are maximal in $O'$ (via contraction along $\psi$).  Since
97$\psi$ is surjective, any maximal ideal in $O'$ that contains $P^e$ maps
98to a maximal ideal in $O'\bmod P^e$ (wikipedia Ideal), so there is a one-to-one
99relationship between the maximal ideals in $O'\bmod P^e$ and the maximal ideals in $O'$
100that contain $P^e$ -- exactly what we're looking for.
101
102So, given a maximal ideal $P_1$ of $O'\bmod P^e$, how can we extract the
103pertinent information (generators, ramification index, relative
104degree, $\beta$) for its corresponding maximal ideal in $O'$?
105
106\begin{enumerate}
107\item {\bf Generators}
108
109The contraction of $P_1$ is its preimage
110under $\psi$, so a set of generators of the contraction can be formed
111just by lifting $P_1$'s generators from $O'\bmod P^e$ to $O'$ and
112appending the generators of $P^e$.
113
114\item {\bf Ramification Index}
115
116To see how to compute the ramification
117index, let's begin by studying how to characterize the ideals
118of $O'\bmod P^e$
119
120\begin{lemma}
121$P^e$ consists of all elements in $O'$ with valuation greater than or
122equal to the ramification index at {\it all} places lying over $P$.
123\end{lemma}
124\begin{proof}
125$O'$ consists of all elements with valuation greater than or equal to
126zero at every finite place.
127$P$ contains at least one element $u$ (any uniformizing variable will do) with valuation equal
128to the ramification index at {\it all} places lying over $P$.
129
130Therefore, given {\it any} element $e \in O'$ with valuation greater than or
131equal to the ramification index at {\it all} places lying over $P$,
132we can use the Strong Approximation Theorem to find an element in $f \in O'$
133such that $fu$ has the same valuation as $e$ at all places lying over $P$.
134Then $\frac{e}{fu} \in O'$ and $e = \frac{e}{fu} f u$ shows that $e \in P^e$.
135\end{proof}
136
137\begin{mdframed}
138{\bf\cite{stich} Theorem 1.6.5 (Strong Approximation Theorem).}
139Let $S \varsubsetneqq \PP_F$ be
140a proper subset of $\PP_F$ and $P_1 , ... , P_r \in S$. Suppose there are given elements
141$x_1 , ... , x_r \in F$ and integers $n_1 , ... , n_r \in \ZZ$. Then there exists an element
142$x \in F$ such that
143$$\nu_{P_i} (x - x_i ) = n_i \qquad (i=1,...,r), \quad{\rm and}$$
144$$\nu_P (x) \ge 0 \qquad \forall P \in S \backslash \{P_1 , ... , P_r\}.$$
145\end{mdframed}
146
147If a function $f$ has valuation greater than or equal to the
148ramification index at a place $P_1$, it can be reduced $\bmod P^e$ by
149using the Strong Approximation Theorem to construct a function in
150$P^e$ with valuation equal to the ramification index at $P_1$ and
151valuation greater than $f$'s valuation at all other places over $P$
152and adding it to $f$.  Thus $O' \bmod P^e$ contains no functions with
153valuations greater than the ramification indices.
154
155So, $O' \bmod P^e$ consists of equivalence classes of functions
156characterized by a tuple of valuations at each place over $P$, with
157each valuation no larger than the ramification index at that place.
158The functions with valuation equal to the ramification index
159at all places over $P$ are in $P^e$, and therefore correspond
160to the zero ideal.
161
162Each prime ideal in $O' \bmod P^e$ is characterized by a tuple like
163$(1,0,...,0)$ (i.e, a single one and the rest of its elements zero).
164Squaring it will produce an ideal characterized by $(2,0,...,0)$.
165Continue raising the prime ideal to higher and higher powers until
166we've obtained an ideal characterized by $(r,0,...,0)$ ($r$ being the
167ramification index).  Raising the ideal to higher powers will continue
168producing this same ideal, a manifestation of the Artinian condition
169guaranteeing that the descending chain of power ideals will stablize.
170
171Thus, we can find the ramification index by raising a prime ideal
172in $O'\bmod P^e$ to successively higher powers until it stabilizes.
173
174{\bf Ex:} $y^2=x$; $P=(x-1)$.
175
176$P^e = (y^2-x, x-1)$ decomposes into $P_1=(x-1,y-1)$
177and $P_2=(x-1,y+1)$ with ramification one at both places.
178Ideals in $O'\bmod P^e$ are characterized by tuples $(0,0)$, $(1,0)$, $(0,1)$, and $(1,1)$.
179$(0,0)$ corresponds to the unit ideal $(1)$, $(1,0)$ is $(y-1)$,
180$(0,1)$ is $(y+1)$, and $(1,1)$ is the zero ideal $(0)$.  Our theory
181suggests that squaring $(y-1)$ will stabilize it, and we verify
182that $(y-1)^2 \equiv -2(y-1) \bmod P^e$.
183
184{\bf Ex:} $y^2=x$; $P=(x)$.
185
186$P^e=(y^2-x,x)$ decomposes into a single ideal $P_1=(y)$
187with ramification two.
188Ideals in $O'\bmod P^e$ are characterized by tuples $(0)$, $(1)$, and $(2)$,
189with $(0)$ corresponding to the unit ideal $(1)$, $(1)$ corresponding to
190the ideal $(y)$, and $(2)$ corresponding to the zero ideal $(0)$.  Our
191theory leads us to believe that squaring $(y)$ will produce the zero
192ideal and, indeed, $y^2 \equiv 0 \bmod P^e$.
193
194\item {\bf Relative Degree}
195
196\cite{stich} Definition 3.1.5 defines the relative degree
197of $P'$ over $P$ as $[F'_{P'}:F_P]$, where $F_P$ (the {\it residue
198  class field} of P) is defined (\cite{stich} Definition 1.1.14) as
199$O_P/P$ where $O_P$ is the valuation ring associated with $P$.
200
201In our notation, $F_P$ is $O \bmod P$ and $F'_{P'}$ is $O' \bmod P_1$.
202Remember that $O' \bmod P^e$ is a finite-dimensional algebra over
203$F_P$.  Since
204
205$$F'_{P'} = O' \bmod P_1^c \cong O' \bmod P_e \bmod P_1$$
206
207and we have an $F_P$-basis for $P_1$ in $O' \bmod P_e$, we see that the
208dimension of $F'_{P'}$ over $F_P$ is simply the $F_P$-dimension of $O' \bmod P_e$
209minus the $F_P$-dimension of $P_1$.  Our finite dimensional algebra
210code gives us an $F_P$-basis for $P_1$, so its dimension is just
211the length of that basis.
212
213\item $\boldsymbol{\beta}$
214
215Finally, for computing valuations using \cite{cohen} Algorithm 4.8.17,
216we wish to compute $\beta$, an element in $O'$ but not in $P^e$, and
217with $\beta P_1 \subseteq P^e$.  Working again in $O' \bmod P^e$,
218we see that $\beta$'s image is not zero, but multiplying it
219by each of $P_1$'s generators produces zero.
220
221Since $\beta$ is in $O'$ (an $O$-module), we regard $\beta$ as
222a vector in k[x] w.r.t. the basis of $O'$.  As long as
223at least one element in this vector is not zero,
224$\beta$ will not be in $P^e$.  To ensure that
225$\beta P_1 \subseteq P^e$, multiplying $\beta$ by each of $P_1$'s
226generators must produce a vector whose elements are all zero.
227We can ensure that all this
228occurs by constructing a matrix in $O \bmod P^e$,
229and finding a non-zero vector in
230the matrix's kernel.
231
232\end{enumerate}
233
234\begin{comment}
235
236\vfill\eject
237\section*{Field Extensions}
238
239Constructing field extensions is currently somewhat problematic in Sage,
240which creates issues when the function field code builds residue fields.
241
242For example, consider the following sequence:
243
244\begin{sageblock}
245A.<a> = GF(5)[]
246B.<b> = GF(5).extension(modulus=a^2-2)
247b^2
248C.<c> = B[]
249D.<d> = B.extension(modulus=c^2-b)
250d^2
251d^4
252\end{sageblock}
253
254{\tt d} behaves the way we would expect, but {\tt D} isn't constructed
255as $\FF_{5^4}$, as we might expect.  Yet we can get $\FF_{5^4}$ in
256a more roundabout way, as follows:
257
258\begin{sageblock}
259E.<e> = B.extension(2)
260F.<f> = E[]
261r = (f^2-b).roots()
262d = r[0][0]
263d^2
264d^2 == b
265d^4
266\end{sageblock}
267
268This is the method used in {\tt FunctionFieldMaximalOrder\_rational}'s {\tt \_residue\_field\_global}.
269
270We can attempt to do something similar with number fields:
271
272\begin{sageblock}
273A.<a> = QQ[]
274B.<b> = QQ.extension(a^3 - 2)
275C.<c> = B[]
276D.<d> = B.extension(c^2-b)
277d^2
278E = D.absolute_field('e')
279e = E.0
280hom = E.structure()[1]
281hom(d) == e
282e^2
283d^2 == e^2
284e^2 == b
285\end{sageblock}
286
287\section*{}
288
289Why are a lot of the test cases failing?
290
291The basis calculation in {\tt FunctionFieldIdeal\_global}.
292
293When we ask for {\tt gens()}, the code checks for a cached result from
294{\tt \_gens\_two} and returns it if it exists, others it gives us
295(more or less) the generators it was created with.
296
297A problem with this is that the print representation of the ideal can
298change after you call {\tt gens\_two()} on it.
299
300\end{comment}
301
302\begin{thebibliography}{9}
303
304\bibitem[Coh1993]{cohen} Henri Cohen, {\it A Course in Computational
305  Algebraic Number Theory}. Graduate Texts in Mathematics
306  138. Springer, 1993.
307
308\bibitem[Stich2009]{stich} Stichtenoth, Henning, {\it Algebraic
309  function fields and codes}.  Vol. 254. Springer Science \& Business
310  Media, 2009.
311
312\bibitem[Khuri2004]{khuri} Khuri-Makdisi,
313{\it Asymptotically Fast Group Operations on
314Jacobians of General Curves}, 2004.
315
316{\tt https://arxiv.org/pdf/math/0409209v2.pdf}
317
318\end{thebibliography}
319
320\end{document}