-- -*- coding: utf-8 -*-
-- cyclotomic.m2
--
-- Copyright (C) 2009-12 Thomas Kahle
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or (at
-- your option) any later version.
--
-- This program is distributed in the hope that it will be useful, but
-- WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-- General Public License for more details.
--
-- You should have received a copy of the GNU General Public License along
-- with this program; if not, write to the Free Software Foundation, Inc.,
-- 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
newPackage(
"Cyclotomic",
Version => "1.0",
Date => "February 2012",
Authors => {{Name => "Thomas Kahle",
Email => "thomas.kahle@jpberlin.de",
HomePage => "http://thomas-kahle.de"}},
Keywords => {"Algebraic Number Theory"},
Headline => "cyclotomic fields"
)
export {"cyclotomicField",
"cyclotomicPoly",
"findRootPower",
"joinCyclotomic"
}
ww := getSymbol "ww"
-- We use memoize to get physically the same cyclotomic field again and again!
cf = (i) -> (
Q := QQ(monoid [ww_i]);
toField ((Q) / cyclotomicPoly (i, Q_0)))
cyclotomicField = memoize cf
--- Here is an example of how to map coefficient rings to not forget it
-- restart
-- F = frac (QQ[a,b]/ideal(a^2-b))
-- G = frac (QQ[x,y]/ideal(x^2-y))
--
-- R = F[t]
-- S = G[t]
--
-- use R
-- I = ideal (t-a-b)
-- use S
-- J = ideal (t+x)
--
-- use S
-- f = map (S,R,{t,x,y^2})
-- f(I)
-- We apply this to join cyclotomic fields
joinCyclotomic = li -> (
-- This function joins a list of ideals in a polynomial ring over a smallest common cf. Input should consist of
-- ideals in polynomial rings over the same variables, but with possible different cyclotomic coefficient field
-- Find root powers:
lc := for l in li list findRootPower ring l;
leastcm := lcm for l in lc list if l>2 then l else 1;
--Check for QQ
if leastcm < 3 then return li;
F := cyclotomicField leastcm;
-- Here we use the assumptions that all rings have the same generators
-- This should contain the variables of polynomials
ge := gens ring li#0;
S := F(monoid [ge]);
li2 := {}; ww:=F_0; local f;
for i in 0..#li-1 do (
if lc#i == 2 then (
-- rational coefficients: just map
li2 = li2 | {sub (li#i,S)};
)
else (
-- Was cyclotomic: need to find image of ww in new ring!
f = map (S, ring li#i , (gens S) |{ww^(leastcm//lc#i)});
li2 = li2 | { f li#i };
);
);
li2)
cyclotomicPoly = (i,v) -> (
-- returns the i-th cyclotomic polynomial in variable v.
-- v must be a variable a priori
v = value v;
if i <= 0 then error "the input should be > 0.";
if i==1 then return v-1 ;
mini := v^i -1;
-- dividing out the first cyclotomic polynomial
-- (with result a polynomial)
mini = (flatten entries syz matrix {{mini ,(v-1)}})#1;
-- i is prime:
if isPrime i then return mini / (leadCoefficient mini);
-- i is not prime:
-- find the divisors:
for f in toList (2..i//2) do (
-- check for factor
if i%f == 0 then (
fac := cyclotomicPoly (f,v);
-- division with result in polynomial ring:
mini = (flatten entries syz matrix {{mini,fac}})#1;
)
);
--make sure the leading coefficient is one.
mini / leadCoefficient(mini))
findRootPower = R -> (
-- Finds the power of the adjoined root of unity in the
-- coefficient ring of R by just exponentiating.
-- Returns '2' if the input was a polynomial ring over QQ
r := 0;
F := coefficientRing R;
fieldgens := (K,F) -> if K === F then {} else for x in gens last F.baseRings list promote(x,F);
g := fieldgens (QQ,F);
if #g == 0 then return 2;
if #g > 1 then error "The coefficient field has more than one generator";
g = value (g#0);
gg := g; -- the generator
while not 1_F == gg do (
r = r+1;
gg = gg *g;
);
if r<2 then return 2
else r+1)
-- End of source code ---
beginDocumentation()
document {
Key => Cyclotomic,
Headline => "cyclotomic fields",
EM "Cyclotomic", " is a package for cyclotomic fields. It is used in
to construct extensions of the coefficient field during binomial
primary decomposition using the package ", TO "Binomials::Binomials", "."
}
document {
Key => {cyclotomicField},
Headline => "cyclotomic field construction",
Usage => "cyclotomicField (i)",
Inputs => {
"i" => { "an integer, the power of the root to be adjoined."}},
Outputs => {
"S" => {"A cyclotomic field with $1^(1/i)$ adjoined"} },
EXAMPLE {
"S = cyclotomicField (5)",
"isField S",
"r = S_0",
"(r^9, r^10, r^11)",
"T = S[x,y]",
"I = ideal (x-r)",
"dim I"
},
Caveat => {"Strange things can happen with the reduction of the coefficients.", " In M2 v <= 1.2 dimension is off by one."},
SeeAlso => cyclotomicPoly
}
document {
Key => {cyclotomicPoly},
Headline => "Cyclotomic Polynomial",
Usage => "cyclotomicPoly (i,v)",
Inputs => {
"i" => { "an integer, the power of a root of unity."},
"v" => { "a variable name in which the polynomial is returned."} },
Outputs => {
"f" => {"The minimal polynomial of the i-th root of unity."} },
EXAMPLE {
"R = QQ[ww]",
"f = cyclotomicPoly (6,ww)",
},
SeeAlso => cyclotomicField
}
document {
Key => {findRootPower},
Headline => "Find the order of the root in the coefficients of polynomial ring over a cyclotomic field",
Usage => "findRootPower R",
Inputs => {
"R" => { "a polynomial ring over a cyclotomic field"}},
Outputs => {
"i" => {"The order of the adjoined root of unity, or 2 if the coefficient field is QQ"} },
EXAMPLE {
"S = cyclotomicField 5",
"T = S[x,y]",
"findRootPower T"
},
SeeAlso => cyclotomicField
}
document {
Key => {joinCyclotomic},
Headline => "Join ideals in polynomial rings over different cyclotomic fields",
Usage => "joinCyclotomic l",
Inputs => {
"li" => { "a list of ideals in polynomial rings over cyclotomic fields"}},
Outputs => {
"li2" => {"The list of ideals in a common ring."} },
EXAMPLE {
"F = cyclotomicField 3; G = cyclotomicField 4;",
"R = F[t]; I = ideal (t-F_0^2)",
"S = G[t]; J = ideal (t^2-G_0)",
"joinCyclotomic {I,J}"
},
SeeAlso => cyclotomicField
}
TEST ///
F = cyclotomicField 3
G = cyclotomicField 4
R = F[t]
I = ideal (t-F_0^2)
S = G[t]
J = ideal (t^2-G_0)
assert (findRootPower coefficientRing ring (joinCyclotomic {I,J})#0 == 12)
///