1#############################################################################
2##
3##  This file is part of GAP, a system for computational discrete algebra.
4##  This file's authors include Thomas Breuer.
5##
6##  Copyright of GAP belongs to its developers, whose names are too numerous
7##  to list here. Please refer to the COPYRIGHT file for details.
8##
9##  SPDX-License-Identifier: GPL-2.0-or-later
10##
11##  This file contains methods for fields consisting of cyclotomics.
12##
13##  Note that we must distinguish abelian number fields and fields
14##  that consist of cyclotomics.
15##  (The image of the natural embedding of the rational number field
16##  into a field of rational functions is of course an abelian number field
17##  but its elements are not cyclotomics since this would be a property given
18##  by their family.)
19##
20
21
22#############################################################################
23##
24#F  AbelianNumberFieldByReducedGaloisStabilizerInfo( <F>, <N>, <stab> )
25##
26##  The constructor `FieldByGenerators' calls this function.
27##  Since `CyclotomicField' and `AbelianNumberField' generate first the
28##  information about conductor and Galois stabilizer, it is useful for them
29##  to call this function instead of constructing generators and calling
30##  `FieldByGenerators', which would mean to construct <N> and <stab> again.
31##
32InstallGlobalFunction( AbelianNumberFieldByReducedGaloisStabilizerInfo,
33    function( F, N, stab )
34
35    local D, d;
36
37    D:= Objectify( NewType( CollectionsFamily( CyclotomicsFamily ),
38                                IsField
39                            and IsFiniteDimensional
40                            and IsAbelianNumberField
41                            and IsAttributeStoringRep ),
42                   rec() );
43
44    d:= Phi(N) / Length( stab );
45
46    SetIsCyclotomicField( D, Length( stab ) = 1 );
47    SetLeftActingDomain( D, F );
48    SetDegreeOverPrimeField( D, d );
49    SetGaloisStabilizer( D, stab );
50    SetConductor( D, N );
51    SetIsFinite( D, false );
52    SetSize( D, infinity );
53    SetDimension( D, d / DegreeOverPrimeField( F ) );
54    SetPrimeField( D, Rationals );
55    SetIsWholeFamily( D, false );
56
57    return D;
58end );
59
60
61#############################################################################
62##
63#F  CyclotomicField( <n> )  . . . . . . .  create the <n>-th cyclotomic field
64#F  CyclotomicField( <gens> )
65#F  CyclotomicField( <subfield>, <n> )
66#F  CyclotomicField( <subfield>, <gens> )
67##
68InstallGlobalFunction( CyclotomicField, function ( arg )
69
70    local F, subfield, xtension;
71
72    # If necessary split the arguments.
73    if     Length( arg ) = 1
74       and ( ( IsInt( arg[1] ) and 0 < arg[1] ) or IsList( arg[1] ) ) then
75
76      # CF( <n> ) or CF( <gens> )
77      subfield:= Rationals;
78      xtension:= arg[1];
79
80    elif     Length( arg ) = 2
81         and IsField( arg[1] )
82         and ( ( IsInt( arg[2] ) and 0 < arg[2] ) or IsList( arg[2] ) ) then
83
84      # `CF( <subfield>, <n> )' or `CF( <subfield>, <gens> )'
85      subfield:= arg[1];
86      xtension:= arg[2];
87
88    else
89      Error("usage: CF( <n> ) or CF( <subfield>, <gens> )");
90    fi;
91
92    # Replace generators by their conductor.
93    if not IsInt( xtension ) then
94      xtension:= Conductor( xtension );
95    fi;
96    if xtension mod 2 = 0 and xtension mod 4 <> 0 then
97      xtension:= xtension / 2;
98    fi;
99
100    # The subfield is given by `Rationals' denoting the prime field.
101    if subfield = Rationals then
102
103      # The standard field is required.  Look whether it is already stored.
104      # If not, generate it and return it
105      return CYCLOTOMIC_FIELDS( xtension );
106
107    elif IsAbelianNumberField( subfield ) then
108
109      # CF( subfield, N )
110      if xtension mod Conductor( subfield ) <> 0 then
111        Error( "<subfield> is not contained in CF( <xtension> )" );
112      fi;
113
114    else
115      Error( "<subfield> must be `Rationals' or an abelian number field" );
116    fi;
117
118    F:= AbelianNumberFieldByReducedGaloisStabilizerInfo( subfield,
119            xtension, [ 1 ] );
120
121    # Return the field.
122    return F;
123end );
124
125
126#############################################################################
127##
128#F  ReducedStabilizerInfo( <N>, <stabilizer> )
129##
130##  is a record with components `N' and `stabilizer',
131##  which are minimal with the property that they describe the same abelian
132##  number field as the input parameters <N> and <stabilizer>.
133##
134BindGlobal( "ReducedGaloisStabilizerInfo", function( N, stabilizer )
135
136    local d,
137          gens,
138          NN,
139          aut,
140          pos,
141          i,
142          p;
143
144    if N mod 2 = 0 and N mod 4 <> 0 then
145      N:= N / 2;
146    fi;
147    if N <= 2 then
148      return rec( N:= 1, stabilizer:= [ 1 ] );
149    fi;
150
151    stabilizer:= Set( stabilizer );
152    AddSet( stabilizer, 1 );
153
154    # Compute the elements of the group generated by `stabilizer'.
155    for d in stabilizer do
156      UniteSet( stabilizer, List( stabilizer, x -> ( x * d ) mod N ) );
157    od;
158
159    # reduce the pair `( N, stabilizer )' such that afterwards `N'
160    # describes the conductor of the required field;
161
162    gens:= GeneratorsPrimeResidues( N );
163    NN:= 1;
164    if gens.primes[1] = 2 then
165
166      if gens.exponents[1] < 3 then
167        if not gens.generators[1] in stabilizer then
168          NN:= NN * 4;
169        fi;
170
171      else
172
173        # the only case where `gens.generators[i]' is a list;
174        # it contains the generators corresponding to `**' and `*5';
175        # the first one is irrelevant for the conductor,
176        # except if also the other generator is contained.
177        if gens.generators[1][2] in stabilizer then
178          if not gens.generators[1][1] in stabilizer then
179            NN:= NN * 4;
180          fi;
181        else
182          NN:= NN * 4;
183          aut:= gens.generators[1][2];
184          while not aut in stabilizer do
185            aut:= ( aut ^ 2 ) mod N;
186            NN:= NN * 2;
187          od;
188        fi;
189      fi;
190      pos:= 2;
191    else
192      pos:= 1;
193    fi;
194
195    for i in [ pos .. Length( gens.primes ) ] do
196      p:= gens.primes[i];
197      if not gens.generators[i] in stabilizer then
198        NN:= NN * p;
199        aut:= ( gens.generators[i] ^ ( p - 1 ) ) mod N;
200        while not aut in stabilizer do
201          aut:= ( aut ^ p ) mod N;
202          NN:= NN * p;
203        od;
204      fi;
205    od;
206
207    N:= NN;
208    if N <= 2 then
209      stabilizer:= [ 1 ];
210      N:= 1;
211    else
212      stabilizer:= Set( List( stabilizer, x -> x mod N ) );
213    fi;
214
215    return rec( N:= N, stabilizer:= stabilizer );
216end );
217
218
219#############################################################################
220##
221#F  AbelianNumberField( <N>, <stab> ) . . . .  create an abelian number field
222##
223##  fixed field of the group generated by <stab> (prime residues modulo <N>)
224##  in the cyclotomic field with conductor <N>.
225##
226InstallGlobalFunction( AbelianNumberField, function ( N, stabilizer )
227
228    local pos,     # position in a list
229          F;       # the field, result
230
231    # Check the arguments.
232    if not ( IsInt( N ) and 0 < N and IsList( stabilizer ) ) then
233      Error( "<N> must be a positive integer, <stabilizer> a list" );
234    fi;
235
236    # Compute the conductor and the reduced stabilizer.
237    # Thus the Galois stabilizer component of the field will be minimal.
238    stabilizer := ReducedGaloisStabilizerInfo( N, stabilizer );
239    N          := stabilizer.N;
240    stabilizer := stabilizer.stabilizer;
241
242    if stabilizer = [ 1 ] then
243      return CyclotomicField( N );
244    fi;
245
246    # The standard field is required.  Look whether it is already stored.
247    if not IsBound( ABELIAN_NUMBER_FIELDS[1][N] ) then
248      ABELIAN_NUMBER_FIELDS[1][N]:= [];
249      ABELIAN_NUMBER_FIELDS[2][N]:= [];
250    fi;
251    pos:= Position( ABELIAN_NUMBER_FIELDS[1][N], stabilizer );
252    if pos <> fail then
253      return ABELIAN_NUMBER_FIELDS[2][N][ pos ];
254    fi;
255
256    # Construct the field.
257    F:= AbelianNumberFieldByReducedGaloisStabilizerInfo( Rationals,
258            N, stabilizer );
259
260    # Store the field.
261    Add( ABELIAN_NUMBER_FIELDS[1][N], stabilizer );
262    Add( ABELIAN_NUMBER_FIELDS[2][N], F );
263
264    # Return the number field.
265    return F;
266end );
267
268
269#############################################################################
270##
271#M  ViewObj( <F> )  . . . . . . . . . . . . . .  view an abelian number field
272##
273InstallMethod( ViewObj,
274    "for abelian number field of cyclotomics",
275    [ IsAbelianNumberField and IsCyclotomicCollection ],
276    function( F )
277    if IsPrimeField( LeftActingDomain( F ) ) then
278      Print( "NF(", Conductor( F ), ",",
279              GaloisStabilizer( F ), ")" );
280    else
281      Print( "AsField( ", LeftActingDomain( F ),
282             ", NF(", Conductor( F ), ",", GaloisStabilizer( F ), ") )" );
283    fi;
284    end );
285
286InstallMethod( ViewObj,
287    "for cyclotomic field of cyclotomics",
288    [ IsCyclotomicField and IsCyclotomicCollection ],
289    function( F )
290    if IsPrimeField( LeftActingDomain( F ) ) then
291      Print( "CF(", Conductor( F ), ")" );
292    else
293      Print( "AsField( ", LeftActingDomain( F ),
294             ", CF(", Conductor( F ), ") )" );
295    fi;
296    end );
297
298
299#############################################################################
300##
301#M  PrintObj( <F> ) . . . . . . . . . . . . . . print an abelian number field
302##
303InstallMethod( PrintObj,
304    "for abelian number field of cyclotomics",
305    [ IsAbelianNumberField and IsCyclotomicCollection ],
306    function( F )
307    if IsPrimeField( LeftActingDomain( F ) ) then
308      Print( "NF(", Conductor( F ), ",",
309              GaloisStabilizer( F ), ")" );
310    else
311      Print( "AsField( ", LeftActingDomain( F ),
312             ", NF(", Conductor( F ), ",", GaloisStabilizer( F ), ") )" );
313    fi;
314    end );
315
316InstallMethod( PrintObj,
317    "for cyclotomic field of cyclotomics",
318    [ IsCyclotomicField and IsCyclotomicCollection ],
319    function( F )
320    if IsPrimeField( LeftActingDomain( F ) ) then
321      Print( "CF(", Conductor( F ), ")" );
322    else
323      Print( "AsField( ", LeftActingDomain( F ),
324             ", CF(", Conductor( F ), ") )" );
325    fi;
326    end );
327
328
329#############################################################################
330##
331#M  String( <F> ) . . . . . . . . . . . . . string of an abelian number field
332##
333InstallMethod( String,
334    "for abelian number field of cyclotomics",
335    [ IsAbelianNumberField and IsCyclotomicCollection ],
336    function( F )
337    if IsPrimeField( LeftActingDomain( F ) ) then
338      return Concatenation( "NF(", String( Conductor( F ) ), ",",
339                            String( GaloisStabilizer( F ) ), ")" );
340    else
341      return Concatenation( "AsField( ", String( LeftActingDomain( F ) ),
342                            ", NF(", String( Conductor( F ) ), ",",
343                            String( GaloisStabilizer( F ) ), ") )" );
344    fi;
345    end );
346
347InstallMethod( String,
348    "for cyclotomic field of cyclotomics",
349    [ IsCyclotomicField and IsCyclotomicCollection ],
350    function( F )
351
352    local n;
353
354    n:= Conductor( F );
355
356    if IsPrimeField( LeftActingDomain( F ) ) then
357      if   n = 1 then
358        return "Rationals";
359      elif n = 4 then
360        return "GaussianRationals";
361      else
362        return Concatenation( "CF(", String( n ), ")" );
363      fi;
364    elif n = 4 then
365      return Concatenation( "AsField( ", String( LeftActingDomain( F ) ),
366                            ", GaussianRationals )" );
367    else
368      return Concatenation( "AsField( ", String( LeftActingDomain( F ) ),
369                            ", CF(", String( n ), ") )" );
370    fi;
371    end );
372
373
374#############################################################################
375##
376#M  \=( <F1>, <F2> )  . . . . . . . . . . comparison of abelian number fields
377#M  \<( <F1>, <F2> )  . . . . . . . . . . comparison of abelian number fields
378##
379##  <F1> is smaller than <F2> if and only if <F1> has a smaller conductor,
380##  or it has the same conductor as <F2> but its Galois stabilizer component
381##  is smaller.
382##
383InstallMethod( \=,
384    "for two abelian number fields",
385    IsIdenticalObj,
386    [ IsAbelianNumberField, IsAbelianNumberField ],
387    function ( F1, F2 )
388    return     Conductor( F1 ) = Conductor( F2 )
389           and GaloisStabilizer( F1 ) = GaloisStabilizer( F2 );
390    end );
391
392InstallMethod( \<,
393    "for two abelian number fields",
394    IsIdenticalObj,
395    [ IsAbelianNumberField, IsAbelianNumberField ],
396    function ( F1, F2 )
397    return    Conductor( F1 ) < Conductor( F2 )
398           or (     Conductor( F1 ) = Conductor( F2 )
399                and GaloisStabilizer( F1 ) < GaloisStabilizer( F2 ) );
400    end );
401
402
403#############################################################################
404##
405#M  \in( <z>, <F> ) . . . .  test if <z> lies in the abelian number field <F>
406##
407##  check whether <z> is a cyclotomic with conductor contained in the
408##  conductor of <F>, and that <z> is fixed by `GaloisStabilizer( <F> )'.
409##
410InstallMethod( \in,
411    "for cyclotomic and abelian number field",
412    IsElmsColls,
413    [ IsCyc, IsAbelianNumberField and IsCyclotomicCollection ],
414    function ( z, F )
415    return     Conductor( F ) mod Conductor( z ) = 0
416           and ForAll( GaloisStabilizer( F ), x -> GaloisCyc( z, x ) = z );
417    end );
418
419InstallMethod( \in,
420    "for cyclotomic and cyclotomic field",
421    IsElmsColls,
422    [ IsCyc, IsCyclotomicField and IsCyclotomicCollection ],
423    function ( z, F )
424    return Conductor( F ) mod Conductor( z ) = 0;
425    end );
426
427
428#############################################################################
429##
430#M  Intersection2( <F>, <G> ) . . . . . intersection of abelian number fields
431##
432InstallMethod( Intersection2,
433    "for two cyclotomic fields of cyclotomics",
434    IsIdenticalObj,
435    [ IsCyclotomicField and IsCyclotomicCollection,
436      IsCyclotomicField and IsCyclotomicCollection ],
437    function ( F, G )
438    return CyclotomicField( GcdInt( Conductor( F ), Conductor( G ) ) );
439    end );
440
441InstallMethod( Intersection2,
442    "for cyclotomic field and abelian number field",
443    IsIdenticalObj,
444    [ IsCyclotomicField and IsCyclotomicCollection,
445      IsAbelianNumberField and IsCyclotomicCollection ],
446    function ( F, G )
447
448    # intersection of cyclotomic field `F = CF(N)' with number field `G';
449    # replace `N' by its g.c.d. with the conductor of `G',
450    # and then take the elements of `GaloisStabilizer( G )' modulo `N'.
451    # (If a reduction is necessary, `NF' will do.)
452
453    F:= Gcd( Conductor( F ), Conductor( G ) );
454    return AbelianNumberField( F, Set( List( GaloisStabilizer( G ),
455                                             x -> x mod F ) ) );
456    end );
457
458InstallMethod( Intersection2,
459    "for abelian number field and cyclotomic field",
460    IsIdenticalObj,
461    [ IsAbelianNumberField and IsCyclotomicCollection,
462      IsCyclotomicField and IsCyclotomicCollection ],
463    function ( G, F )
464
465    # intersection of cyclotomic field `F = CF(N)' with number field `G';
466    # replace `N' by its g.c.d. with the conductor of `G',
467    # and then take the elements of `GaloisStabilizer( G )' modulo `N'.
468    # (If a reduction is necessary, `NF' will do.)
469
470    F:= Gcd( Conductor( F ), Conductor( G ) );
471    return AbelianNumberField( F, Set( List( GaloisStabilizer( G ),
472                                             x -> x mod F ) ) );
473    end );
474
475InstallMethod( Intersection2,
476    "for two abelian number fields",
477    IsIdenticalObj,
478    [ IsAbelianNumberField and IsCyclotomicCollection,
479      IsAbelianNumberField and IsCyclotomicCollection ],
480    function ( F, G )
481
482    local i, j, N, stab, stabF, stabG;
483
484    # first compute `N' where `CF(N)' contains the intersection;
485    # reduce the elements of the stabilizers modulo `N', i.e. intersect
486    # `F' and `G' with `CF(N)';
487    # then compute the corresponding stabilizer, i.e. the product of
488    # stabilizers.
489    N:= GcdInt( Conductor( F ), Conductor( G ) );
490    stabF:= Set( List( GaloisStabilizer( F ), x -> x mod N ) );
491    stabG:= Set( List( GaloisStabilizer( G ), x -> x mod N ) );
492    stab:= [];
493    for i in stabF do
494      for j in stabG do
495        AddSet( stab, ( i * j ) mod N );
496      od;
497    od;
498
499    # (If a reduction is necessary, `NF' will do.)
500    return AbelianNumberField( N, stab );
501    end );
502
503
504#############################################################################
505##
506#M  GeneratorsOfDivisionRing( <F> ) .  field gens. of an abelian number field
507##
508InstallMethod( GeneratorsOfDivisionRing,
509    "for abelian number field of cyclotomics",
510    [ IsAbelianNumberField and IsCyclotomicCollection ],
511    function( F )
512    local e;
513    e:= E( Conductor( F ) );
514    return [ Sum( GaloisStabilizer( F ), y -> GaloisCyc( e, y ) ) ];
515    end );
516
517
518#############################################################################
519##
520#M  Conductor( <F> )  . . . . . . . . .  conductor of an abelian number field
521##
522InstallOtherMethod( Conductor,
523    "for abelian number field of cyclotomics",
524    [ IsAbelianNumberField and IsCyclotomicCollection ],
525    F -> Conductor( GeneratorsOfField( F ) ) );
526
527
528#############################################################################
529##
530#M  Subfields( <F> )  . . . . . . . . .  subfields of an abelian number field
531##
532##  The Galois group of an abelian number field is abelian,
533##  so the subfields are in bijection with the conjugacy classes of subgroups
534##  of the Galois group.
535##
536InstallMethod( Subfields,
537    "for abelian number field of cyclotomics",
538    [ IsAbelianNumberField and IsCyclotomicCollection ],
539    function( F )
540    local n, stab;
541    n:= Conductor( F );
542    stab:= GaloisStabilizer( F );
543    return Set( List( ConjugacyClassesSubgroups( GaloisGroup( F ) ),
544                      x -> AbelianNumberField( n, Union( stab,
545                             List( GeneratorsOfGroup( Representative( x ) ),
546                                   y -> ExponentOfPowering( y ) ) ) ) ) );
547    end );
548
549
550#############################################################################
551##
552#M  PrimeField( <F> ) . . . . . . . . . . . . . . for an abelian number field
553##
554InstallMethod( PrimeField,
555    "for abelian number field of cyclotomics",
556    [ IsAbelianNumberField and IsCyclotomicCollection ],
557    F -> Rationals );
558
559
560#############################################################################
561##
562#M  FieldExtension( <subfield>, <poly> )  . .  extend an abelian number field
563##
564InstallOtherMethod( FieldExtension,
565    "for field of cyclotomics, and univ. polynomial (degree <= 2)",
566#T CollPoly
567    [ IsAbelianNumberField and IsCyclotomicCollection,
568      IsLaurentPolynomial ],
569    function( F, poly )
570
571    local coeffs, root;
572
573    coeffs:= CoefficientsOfLaurentPolynomial( poly );
574    coeffs:= ShiftedCoeffs( coeffs[1], coeffs[2] );
575
576    if not IsSubset( F, coeffs ) then
577      Error( "all coefficients of <poly> must lie in <F>" );
578    elif 3 < Length( coeffs ) then
579      TryNextMethod();
580    elif Length( coeffs ) <= 1 then
581      Error( "<poly> must have degree at least 1" );
582    elif Length( coeffs ) = 2 then
583
584      # `poly' is a linear polynomial.
585      root:= - coeffs[1] / coeffs[2];
586      F:= AsField( F, F );
587
588    else
589
590      # `poly' has degree 2.
591      # The roots of `a*x^2 + b*x + c' are
592      # $\frac{ -b \pm \sqrt{ b^2 - 4ac } }{2a}$.
593      root:= coeffs[2]^2 - 4 * coeffs[1] * coeffs[3];
594      if not IsRat( root ) then
595        TryNextMethod();
596      fi;
597      root:= ( ER( root ) - coeffs[2] ) / ( 2 * coeffs[3] );
598      F:= AsField( F, FieldByGenerators(
599                       Concatenation( GeneratorsOfField( F ), [ root ] ) ) );
600
601    fi;
602
603    # Store the defining polynomial, and a root of it in the extension field.
604    SetDefiningPolynomial( F, poly );
605    SetRootOfDefiningPolynomial( F, root );
606
607    return F;
608    end );
609
610
611#############################################################################
612##
613#M  Conjugates( <L>, <K>, <z> )
614##
615InstallMethod( Conjugates,
616    "for two abelian number fields of cyclotomics, and cyclotomic",
617    IsCollsXElms,
618    [ IsAbelianNumberField and IsCyclotomicCollection,
619      IsAbelianNumberField and IsCyclotomicCollection, IsCyc ],
620    function( L, K, z )
621
622    local N, gal, gens, conj, pnt;
623
624    N:= Conductor( L );
625
626    # automorphisms of the conductor
627    gal:= PrimeResidues( N );
628
629    if not IsPrimeField( K ) then
630
631      # take only the subgroup of `gal' that fixes the subfield pointwise
632      gens:= GeneratorsOfField( K );
633      gal:= Filtered( gal,
634                      x -> ForAll( gens, y -> GaloisCyc( y, x ) = y ) );
635    fi;
636
637    # get representatives of cosets of the Galois stabilizer
638    conj:= [];
639    gens:= GaloisStabilizer( L );
640    while gal <> [] do
641      pnt:= gal[1];
642      Add( conj, GaloisCyc( z, pnt ) );
643      SubtractSet( gal, List( gens, x -> ( x * pnt ) mod N ) );
644    od;
645
646    return conj;
647    end );
648
649InstallMethod( Conjugates,
650    "for cycl. field of cyclotomics, ab. number field, and cyclotomic",
651    IsCollsXElms,
652    [ IsCyclotomicField and IsCyclotomicCollection,
653      IsAbelianNumberField and IsCyclotomicCollection, IsCyc ],
654    function( L, K, z )
655
656    local conj, Kgens, i;
657
658    if not z in L then
659      Error( "<z> must lie in <L>" );
660    fi;
661
662    if IsPrimeField( K ) then
663      conj:= List( PrimeResidues( Conductor( L ) ),
664                   i -> GaloisCyc( z, i ) );
665    else
666      conj:= [];
667      Kgens:= GeneratorsOfField( K );
668      for i in PrimeResidues( Conductor( L ) ) do
669        if ForAll( Kgens, x -> GaloisCyc( x, i ) = x ) then
670          Add( conj, GaloisCyc( z, i ) );
671        fi;
672      od;
673    fi;
674
675    return conj;
676    end );
677
678
679#############################################################################
680##
681#M  Norm( <L>, <K>, <z> )
682##
683InstallMethod( Norm,
684    "for two abelian number fields of cyclotomics, and cyclotomic",
685    IsCollsXElms,
686    [ IsAbelianNumberField and IsCyclotomicCollection,
687      IsAbelianNumberField and IsCyclotomicCollection, IsCyc ],
688    function( L, K, z )
689    local N, gal, gens, result, pnt;
690
691    N:= Conductor( L );
692
693    # automorphisms of the conductor
694    gal:= PrimeResidues( N );
695
696    if not IsPrimeField( K ) then
697
698      # take only the subgroup of `gal' that fixes the subfield pointwise
699      gens:= GeneratorsOfField( K );
700      gal:= Filtered( gal,
701                      x -> ForAll( gens, y -> GaloisCyc( y, x ) = y ) );
702    fi;
703
704    # get representatives of cosets of `GaloisStabilizer( L )'
705    result:= 1;
706    gens:= GaloisStabilizer( L );
707    while gal <> [] do
708      pnt:= gal[1];
709      result:= result * GaloisCyc( z, pnt );
710      SubtractSet( gal, List( gens, x -> ( x * pnt ) mod N ) );
711    od;
712
713    return result;
714    end );
715
716InstallMethod( Norm,
717    "for cycl. field of cyclotomics, ab. number field, and cyclotomic",
718    IsCollsXElms,
719    [ IsCyclotomicField and IsCyclotomicCollection,
720      IsAbelianNumberField and IsCyclotomicCollection, IsCyc ],
721    function( L, K, z )
722
723    local i, result, Kgens;
724
725    result:= 1;
726    if IsPrimeField( K ) then
727      for i in PrimeResidues( Conductor( L ) ) do
728        result:= result * GaloisCyc( z, i );
729      od;
730    else
731      Kgens:= GeneratorsOfField( K );
732      for i in PrimeResidues( Conductor( L ) ) do
733        if ForAll( Kgens, x -> GaloisCyc( x, i ) = x ) then
734          result:= result * GaloisCyc( z, i );
735        fi;
736      od;
737    fi;
738
739    return result;
740    end );
741
742
743#############################################################################
744##
745#M  Trace( <L>, K>, <z> )
746##
747InstallMethod( Trace,
748    "for two abelian number fields of cyclotomics, and cyclotomic",
749    IsCollsXElms,
750    [ IsAbelianNumberField and IsCyclotomicCollection,
751      IsAbelianNumberField and IsCyclotomicCollection, IsCyc ],
752    function( L, K, z )
753    local N, gal, gens, result, pnt;
754
755    N:= Conductor( L );
756
757    # automorphisms of the conductor
758    gens:= GeneratorsOfField( K );
759    gal:= PrimeResidues( N );
760
761    if not IsPrimeField( K ) then
762
763      # take only the subgroup of `gal' that fixes the subfield pointwise
764      gal:= Filtered( gal,
765                      x -> ForAll( gens, y -> GaloisCyc( y, x ) = y ) );
766    fi;
767
768    # get representatives of cosets of `GaloisStabilizer( L )'
769    result:= 0;
770    gens:= GaloisStabilizer( L );
771    while gal <> [] do
772      pnt:= gal[1];
773      result:= result + GaloisCyc( z, pnt );
774      SubtractSet( gal, List( gens, x -> ( x * pnt ) mod N ) );
775    od;
776
777    return result;
778    end );
779
780InstallMethod( Trace,
781    "for cycl. field of cyclotomics, ab. number field, and cyclotomic",
782    IsCollsXElms,
783    [ IsCyclotomicField and IsCyclotomicCollection,
784      IsAbelianNumberField and IsCyclotomicCollection, IsCyc ],
785    function( L, K, z )
786    local i, result, Kgens;
787    result:= 0;
788    if IsPrimeField( K ) then
789      for i in PrimeResidues( Conductor( L ) ) do
790        result:= result + GaloisCyc( z, i );
791      od;
792    else
793      Kgens:= GeneratorsOfField( K );
794      for i in PrimeResidues( Conductor( L ) ) do
795        if ForAll( Kgens, x -> GaloisCyc( x, i ) = x ) then
796          result:= result + GaloisCyc( z, i );
797        fi;
798      od;
799    fi;
800
801    return result;
802    end );
803
804
805#############################################################################
806##
807#F  ZumbroichBase( <n>, <m> )
808##
809##  returns the set of exponents `e' for which `E(n)^e' belongs to the
810##  (generalized) Zumbroich base of the cyclotomic field $Q_n$,
811##  viewed as vector space over $Q_m$.
812##
813##  *Note* that for $n \equiv 2 \bmod 4$ we have
814##  `ZumbroichBase( <n>, 1 ) = 2 * ZumbroichBase( <n>/2, 1 )' but
815##  `List( ZumbroichBase(  <n>, 1  ), x -> E(  <n>  )^x ) =
816##   List( ZumbroichBase( <n>/2, 1 ), x -> E( <n>/2 )^x )'.
817##
818InstallGlobalFunction( ZumbroichBase, function( n, m )
819
820    local nn, base, basefactor, factsn, exponsn, factsm, exponsm, primes,
821          p, pos, i, k;
822
823    if not n mod m = 0 then
824      Error( "<m> must be a divisor of <n>" );
825    fi;
826
827    factsn:= Factors(Integers, n );
828    primes:= Set( factsn );
829    exponsn:= List( primes, x -> 0 );   # Product(List( [1..Length(primes)],
830                                        #         x->primes[i]^exponsn[i]))=n
831    p:= factsn[1];
832    pos:= 1;
833    for i in factsn do
834      if i > p then
835        p:= i;
836        pos:= pos + 1;
837      fi;
838      exponsn[ pos ]:= exponsn[ pos ] + 1;
839    od;
840
841    factsm:= Factors(Integers, m );
842    exponsm:= List( primes, x -> 0 );    # Product(List( [1..Length(primes)],
843                                         #         x->primes[i]^exponsm[i]))=m
844    if m <> 1 then
845      p:= factsm[1];
846      pos:= Position( primes, p );
847      for i in factsm do
848        if i > p then
849          p:= i;
850          pos:= Position( primes, p );
851        fi;
852        exponsm[ pos ]:= exponsm[ pos ] + 1;
853      od;
854    fi;
855
856    base:= [ 0 ];
857    if n = 1 then
858      return base;
859    fi;
860
861    if primes[1] = 2 then
862
863      # special case: $J_{k,2} = \{ 0, 1 \}$
864      if exponsm[1] = 0 then exponsm[1]:= 1; fi;    # $J_{0,2} = \{ 0 \}$
865
866      nn:= n / 2^( exponsm[1] + 1 );
867
868      for k in [ exponsm[1] .. exponsn[1] - 1 ] do
869        Append( base, base + nn );
870        nn:= nn / 2;
871      od;
872      pos:= 2;
873    else
874      pos:= 1;
875    fi;
876
877    for i in [ pos .. Length( primes ) ] do
878
879      if m mod primes[i] <> 0 then
880        basefactor:= [ 1 .. primes[i] - 1 ] * ( n / primes[i] );
881        base:= Concatenation( List( base, x -> x + basefactor ) );
882        exponsm[i]:= 1;
883      fi;
884
885      basefactor:= [ - ( primes[i] - 1 ) / 2 .. ( primes[i] - 1 ) / 2 ]
886                     * n / primes[i]^exponsm[i];
887
888      for k in [ exponsm[i] .. exponsn[i] - 1 ] do
889        basefactor:= basefactor / primes[i];
890        base:= Concatenation( List( base, x -> x + basefactor ) );
891      od;
892    od;
893    return Set( List( base, x -> x mod n ) );
894end );
895
896
897#############################################################################
898##
899#F  LenstraBase( <n>, <stabilizer>, <super>, <m> )
900##
901##  returns a list of lists of integers; each list indexing the exponents of
902##  an orbit of a subgroup of <stabilizer> on <n>-th roots of unity.
903##
904##  <super> is a list representing a supergroup of <stabilizer> which
905##  shall act consistently with the action of <stabilizer>, i.e., each orbit
906##  of <supergroup> is a union of orbits of <stabilizer>.
907##
908##  ( Shall there be a test if this is possible ? )
909##
910##  <m> is a positive integer.  The basis described by the returned list is
911##  an integral basis over the cyclotomic field $\Q_m$.
912##
913##  *Note* that the elements are in general not sets, since the first element
914##  is always an element of `ZumbroichBase( <n>, <m> )';
915##  this property is used by `NF' and `Coefficients'.
916##
917##  *Note* that <stabilizer> must not contain the stabilizer of a proper
918##  cyclotomic subfield of the <n>-th cyclotomic field.
919##
920##  We proceed as follows.
921##
922##  Let $n'$ be the biggest divisor of $n$ coprime to $m$.
923##  First choose an integral basis $B$ for the extension $\Q_{n'} / \Q$
924##  (equivalently, for $\Q_{n} / \Q_{n/n'}$).
925##  For each element of $B$ choose an integral basis for $\Q_{n/n'} / \Q_m$,
926##  namely a transversal of $E_m$ in $E_{n/n'}$ where $E_n$ denotes the
927##  group of $n$-th roots of unity.
928##
929##  The products of elements in these bases form an integral $\Q_m$-basis
930##  of $\Q_n$.
931##  Now we choose the bases in such a way that ...
932##
933InstallGlobalFunction( LenstraBase, function( n, stabilizer, supergroup, m )
934
935    local i,
936          k,
937          factors,           # factors of `n'
938          primes,            # set of prime divisors of `n'
939          coprimes,          # set of prime divisors of `n' coprime to `m'
940          nprime,            # biggest divisor of `n' coprime to `m'
941          NN,                # squarefree part of `n'
942          zumb,              # exponents of roots in the basis of `CF(n)'
943          N2,                # 2-part of `n'
944          No,                # odd part of `n'
945          transversal,       # roots in basis of `CF(n/nprime) / CF(m)',
946                             # written as `n'-th roots
947          orbits,
948          pnt,
949          orb,
950          d,
951          ppnt,
952          ord,
953          a,
954          neworbits,
955          rep,
956          super,
957          H1;
958
959    # We may assume that either `m' is odd or $4$ divides `m'.
960    if m mod 4 = 2 then
961      m:= m / 2;
962    fi;
963
964    factors  := Factors(Integers, n );
965    primes   := Set( factors );
966    coprimes := Filtered( primes, x -> m mod x <> 0 );
967    nprime   := Product( Filtered( factors, x -> m mod x <> 0 ) );
968
969    NN:= Product( coprimes );
970    zumb:= List( ZumbroichBase( nprime, 1 ), x -> x * ( n / nprime ) );
971    transversal := List( ZumbroichBase( n / nprime, m ), x -> x * nprime );
972    stabilizer:= Set( stabilizer );
973    orbits:= [];
974
975    if nprime = NN then
976
977      # $n'$ is squarefree.
978      # We have a normal basis, `stabilizer' acts on `zumb',
979      # we do not consider equivalence classes since they are all trivial,
980      # and `supergroup' is obsolete since `zumb' describes a normal basis.
981
982      # *Note* that if $n'$ is even then `zumb' does not consist of
983      # at least `NN'-th roots!
984
985      while 0 < Length( zumb ) do
986
987        # Compute the orbit of `stabilizer' of a point in `zumb'.
988        pnt:= zumb[1];
989
990        # For each root in `transversal', compute the orbit of `n'-th roots
991        # under `stabilizer'.
992        neworbits:= List( transversal,
993                          root -> List( stabilizer,
994                                        x -> ( root + pnt ) * x mod n ) );
995        SubtractSet( zumb, neworbits[1] );
996        Append( orbits, neworbits );
997
998      od;
999
1000    else
1001
1002      # Let $d(i)$ be the largest squarefree number whose square divides the
1003      # order of $e_{n'}^i$, that is $n' / \gcd( n', i )$.
1004      # Define an equivalence relation on the set $S$ of at least `NN'-th
1005      # roots of unity.
1006      # $i$ and $j$ are equivalent iff $n'$ divides $( i - j ) d(i)$.  The
1007      # equivalence class $(i)$ of $i$ is
1008      # $\{ i + k n' / d(i) ; 0 \leq k \< d(i) \}$.
1009
1010      # For the case that `NN' is even, replace those roots in $S$ with order
1011      # not divisible by 4 by their negatives.
1012      # (Equivalently\: Replace *all* elements in $S$ by their negatives.)
1013
1014      # If 8 does not divide $n'$ and $n' \not= 4$, `zumb' is a subset of $S$,
1015      # the intersection of $(i)$ with `zumb' is of order $\varphi( d(i) )$,
1016      # it is a basis for the $Z$--submodule spanned by $(i)$.
1017      # Furthermore, the minimality of `n' yields that `stabilizer' acts fixed
1018      # point freely on the set of equivalence classes.
1019
1020      # More exactly, fixed points occur exactly if there is an element `s' in
1021      # `stabilizer' which is congruent $-1$ modulo `N2' and congruent $+1$
1022      # modulo `No'.
1023
1024      # The base is constructed as follows\:
1025      #
1026      # Until all classes are touched:
1027      # 1. Take a point `pnt' (in `zumb').
1028      # 2. Choose a maximal linear independent set `pnts' in the equivalence
1029      #    class of `pnt' (the intersection of the class with `zumb').
1030      # 3. Take the `stabilizer'--orbits of `pnts' as base elements;
1031      #    remove the touched equivalence classes.
1032      # 4. For the representatives `rep' in `supergroup'\:
1033      #    If `rep' maps `pnt' to an equivalence class that was not yet
1034      #    touched, take the `stabilizer'--orbits of the images of `pnts'
1035      #    under `rep' as base elements;
1036      #    remove the touched equivalence classes.
1037
1038      # Compute nontriv. representatives of `supergroup' over `stabilizer'.
1039      super:= Difference( supergroup, stabilizer );
1040      supergroup:= [];
1041      while 0 < Length( super ) do
1042        pnt:= super[1];
1043        Add( supergroup, pnt );
1044        SubtractSet( super, List( stabilizer, x -> ( x * pnt ) mod n ) );
1045      od;
1046
1047      # Compute 2-part and odd part of $n'$.
1048      N2 := 1;
1049      No := nprime;
1050      while No mod 2 = 0 do
1051        N2:= N2 * 2;
1052        No:= No / 2;
1053      od;
1054
1055      # Compute the subgroup `H1' of `stabilizer' that acts fixed point
1056      # freely on the set of equivalence classes,
1057      # and the element `a' that (if exists) fixes some classes pointwise.
1058      H1 := [];
1059      a  := 0;
1060      for k in stabilizer do
1061        if k mod 4 = 1 then
1062          Add( H1, k );
1063        elif ( k -1 ) mod No = 0
1064             and ( ( k + 1 ) mod N2 = 0 or ( k + 1 - N2/2 ) mod N2 = 0 ) then
1065          a:= k;
1066        fi;
1067      od;
1068      if a = 0 then
1069        H1:= stabilizer;
1070      fi;
1071
1072      while 0 < Length( zumb ) do
1073
1074        neworbits:= [];
1075        pnt:= zumb[1];
1076        d:= 1;
1077        ord:= n / GcdInt( n, pnt );
1078        for i in coprimes do
1079          if ord mod i^2 = 0 then d:= d * i; fi;
1080        od;
1081
1082        if ( a = 0 ) or ( ord mod 8 = 0 ) then
1083
1084          # No `H1'-orbit can be fixed by `a'.
1085
1086          for k in [ 0 .. d-1 ] do
1087
1088            # Loop over the equivalence class of `pnt',
1089            # consider only the points in `zumb'.
1090
1091            ppnt:= pnt + k * n / d;
1092            if ppnt in zumb then
1093
1094              orb:= List( stabilizer, x -> ( ppnt * x ) mod n );
1095              Append( neworbits,
1096                      List( transversal,
1097                            root -> List( stabilizer,
1098                                       x -> ( root + ppnt ) * x mod n ) ) );
1099
1100            fi;
1101          od;
1102
1103        elif ord mod 4 = 0 then
1104
1105          # `a' maps each point in the orbit of `H1' to its inverse,
1106          # we ignore all these points.
1107          orb:= List( stabilizer, x -> ( pnt * x ) mod n );
1108
1109        else
1110
1111          # The orbit of `H1' is pointwise fixed by `a'.
1112          for k in [ 0 .. d-1 ] do
1113            ppnt:= pnt + k * n / d;
1114            if ppnt in zumb then
1115
1116              orb:= List( H1, x -> ( ppnt * x ) mod n );
1117              Append( neworbits,
1118                      List( transversal,
1119                            root -> List( H1,
1120                                       x -> ( root + ppnt ) * x mod n ) ) );
1121
1122            fi;
1123          od;
1124
1125        fi;
1126
1127        # Remove the equivalence classes of all new points from `zumb'.
1128        for pnt in orb do
1129          SubtractSet( zumb, List( [ 0 .. d-1 ],
1130                                   k -> ( pnt + k * n / d ) mod n ) );
1131        od;
1132
1133        Append( orbits, neworbits );
1134
1135        # use `supergroup'\:
1136        # Is there a point in `zumb' that is not equivalent to
1137        # `( pnt * rep ) mod nprime' ?
1138        # (Note that the factor group `supergroup / stabilizer' acts on the
1139        # set of unions of orbits with equivalent elements.)
1140
1141        for rep in supergroup do
1142
1143          # is there an `x' in `zumb' that is equivalent to `pnt * rep' ?
1144          if ForAny( zumb, x -> ( ( x - pnt * rep ) * d ) mod n = 0 ) then
1145            Append( orbits, List( neworbits,
1146                              x -> List( x, y -> (y*rep) mod n ) ) );
1147            for ppnt in orbits[ Length( orbits ) ] do
1148              SubtractSet( zumb, List( [ 0..d-1 ],
1149                              k -> ( ppnt + k * n / d ) mod n ) );
1150            od;
1151          fi;
1152        od;
1153
1154      od;
1155    fi;
1156
1157    # Return the list of orbits.
1158    return orbits;
1159end );
1160
1161
1162#############################################################################
1163##
1164#R  IsCanonicalBasisAbelianNumberFieldRep( <B> )
1165##
1166##  The canonical basis of a number field is defined to be a Lenstra basis
1167##  in the case that the subfield is `Rationals'.
1168#T extend this to the case where the subfield is a cyclotomic field!
1169##  In all other cases a normal basis is chosen.
1170##
1171DeclareRepresentation( "IsCanonicalBasisAbelianNumberFieldRep",
1172    IsAttributeStoringRep,
1173    [ "coeffslist", "coeffsmat", "lenstrabase", "conductor" ] );
1174
1175
1176#############################################################################
1177##
1178#R  IsCanonicalBasisCyclotomicFieldRep( <B> )
1179##
1180##  The canonical basis of a field extension $F / K$ for a cyclotomic field
1181##  $F$ is the Zumbroich basis if $K$ is a cyclotomic field.
1182##  Otherwise it is a normal basis.
1183##
1184DeclareRepresentation( "IsCanonicalBasisCyclotomicFieldRep",
1185    IsCanonicalBasisAbelianNumberFieldRep,
1186    [ "zumbroichbase" ] );
1187
1188
1189#############################################################################
1190##
1191#M  CanonicalBasis( <F> )
1192##
1193##  The canonical basis of a number field is defined to be a Lenstra basis
1194##  in the case that the subfield is a cyclotomic field.
1195##
1196##  In all other cases a normal basis is chosen.
1197##
1198InstallMethod( CanonicalBasis,
1199    "for abelian number field of cyclotomics",
1200    [ IsAbelianNumberField and IsCyclotomicCollection ],
1201    function ( F )
1202
1203    local N,             # conductor of `F'
1204          k,
1205          lenst,
1206          i,
1207          B,
1208          BB,
1209          normalbase,
1210          subbase,
1211          m,
1212          j,
1213          C,
1214          coeffsmat,
1215          val,
1216          l;
1217
1218    # Make the basis object.
1219    B:= Objectify( NewType( FamilyObj( F ),
1220                                IsFiniteBasisDefault
1221                            and IsCanonicalBasis
1222                            and IsCanonicalBasisAbelianNumberFieldRep ),
1223                   rec() );
1224    SetUnderlyingLeftModule( B, F );
1225
1226    if IsCyclotomicField( LeftActingDomain( F ) ) then
1227
1228      # Compute the standard Lenstra basis and the `coeffslist' component.
1229      # If `GaloisStabilizer( F )' acts fixed point freely on the
1230      # equivalence classes we must change from the Zumbroich basis to a
1231      # `GaloisStabilizer( F )'-normal basis,
1232      # and afterwards choose coefficients with respect to that basis.
1233      # In the case of fixed points, only the subgroup `H1' of index 2 in
1234      # `GaloisStabilizer( F )' acts fixed point freely;
1235      # we change to a `H1'-normal basis, and afterwards choose coefficients.
1236
1237      # For this basis <B> we want a component `coeffslist' such that
1238      # in the special case of a field over the rationals we have
1239      # `CoeffsCyc( z, N ){ <B>!.coeffslist } = Coefficients( <B>, z )'.
1240
1241      N:= Conductor( F );
1242      lenst:= LenstraBase( N, GaloisStabilizer( F ), GaloisStabilizer( F ),
1243                           Conductor( LeftActingDomain( F ) ) );
1244
1245      # Fill in additional components.
1246      SetBasisVectors( B, List( lenst,
1247                                x -> Sum( List( x, y -> E(N)^y ) ) ) );
1248      B!.coeffslist  := List( lenst, x -> x[1] + 1 );
1249      B!.lenstrabase := lenst;
1250      B!.conductor   := N;
1251#T better compute basis vectors only if necessary
1252#T (in the case of a normal basis the vectors are of course known ...)
1253      SetIsIntegralBasis( B, true );
1254
1255    else
1256
1257      # A basis of an extension of a number field is a normal basis.
1258#T handle extensions of cycl. fields specially!!
1259      # Coefficients can be computed using a tensor form basis for that
1260      # the base change relative to the Lenstra basis (relative to the
1261      # rationals) is computed.
1262
1263      # Let $(v_1, \ldots, v_m)$ denote a basis of `subfield' and
1264      #     $(w_1, \ldots, w_k)$ denote a basis of `F';
1265      # Define $u_{i+m(j-1)} = v_i w_j$.  Then $(u_l; 1\leq l\leq mk)$
1266      # is a basis of `F' over the rationals.
1267      # First change from the Lenstra basis to this basis; the matrix is `C'.
1268
1269      normalbase:= NormalBase( F );
1270      subbase:= BasisVectors( CanonicalBasis( LeftActingDomain( F ) ) );
1271      BB:= CanonicalBasis( AbelianNumberField( Conductor( F ),
1272                                               GaloisStabilizer( F ) ) );
1273      m:= Length( subbase );
1274      k:= Length( normalbase );
1275      N:= Conductor( normalbase );
1276      C:= [];
1277      for j in normalbase do
1278
1279        # Compute the Lenstra basis coefficients.
1280        for i in subbase do
1281          Add( C, Coefficients( BB, i*j ) );
1282        od;
1283
1284      od;
1285      C:= C^(-1);
1286
1287      # Let $(c_1, \ldots, c_{mk})$ denote the coefficients with respect
1288      # to the new base.  To achieve `<coeffs> \* normalbase = <z>' we have
1289      # to take $\sum_{i=1}^m c_{i+m(j-1)} v_i$ as $j$--th coefficient:
1290
1291      coeffsmat:= [];
1292      for i in [ 1 .. Length( C ) ] do     # for all rows
1293        coeffsmat[i]:= [];
1294        for j in [ 1 .. k ] do
1295          val:= 0;
1296          for l in [ 1 .. m ] do
1297            val:= val + C[i][ m*(j-1)+l ] * subbase[l];
1298          od;
1299          coeffsmat[i][j]:= val;
1300        od;
1301      od;
1302
1303      # Multiplication of a Lenstra basis coefficient vector with
1304      # `coeffsmat' means first changing to the base of products
1305      # $v_i w_j$ and then summation over the parts of the $v_i$.
1306
1307      SetIsNormalBasis( B, true );
1308      SetBasisVectors( B, normalbase );
1309      B!.coeffslist := BB!.coeffslist;
1310      B!.coeffsmat  := coeffsmat;
1311      B!.conductor  := N;
1312
1313    fi;
1314
1315    # Return the canonical basis.
1316    return B;
1317    end );
1318
1319
1320#############################################################################
1321##
1322#M  Basis( <F> )
1323##
1324InstallMethod( Basis,
1325    "for abelian number field of cyclotomics (delegate to `CanonicalBasis')",
1326    [ IsAbelianNumberField and IsCyclotomicCollection ],
1327    CANONICAL_BASIS_FLAGS,
1328    CanonicalBasis );
1329
1330
1331#############################################################################
1332##
1333#M  Coefficients( <B>, <z> )  . . . . .  for canon. basis of ab. number field
1334##
1335InstallMethod( Coefficients,
1336    "for canonical basis of abelian number field, and cyclotomic",
1337    IsCollsElms,
1338    [ IsBasis and IsCanonicalBasis and IsCanonicalBasisAbelianNumberFieldRep,
1339      IsCyc ],
1340    function ( B, z )
1341    local V,
1342          F,
1343          coeffs,
1344          n,
1345          m,
1346          zumb,
1347          NN,
1348          Em;
1349
1350    if not z in UnderlyingLeftModule( B ) then
1351      return fail;
1352    fi;
1353
1354    V:= UnderlyingLeftModule( B );
1355    F:= LeftActingDomain( V );
1356
1357    # The information about the standard Lenstra basis coefficients
1358    # is stored in `B!.coeffslist'.
1359    if   IsPrimeField( F ) then
1360
1361      # Take the relevant sublist, this suffices for extensions
1362      # of the rationals.
1363      coeffs:= CoeffsCyc( z, B!.conductor ){ B!.coeffslist };
1364
1365    elif IsCyclotomicField( F ) then
1366
1367      # `B' is an integral basis of an extension of a cyclotomic field $\Q_m$,
1368      # the coefficient of the root $\zeta$ is
1369      # $\sum_{\eta\in\B_m} a_{\eta\zeta} \eta$.
1370
1371      coeffs:= CoeffsCyc( z, B!.conductor );
1372      n:= Conductor( V );
1373      m:= Conductor( F );
1374      zumb:= CanonicalBasis( F )!.zumbroichbase;
1375      NN:= n/m;
1376      Em:= E(m);
1377      coeffs:= List( B!.coeffslist,
1378                j->Sum( zumb, k->coeffs[ ((k*NN+j-1) mod n )+1 ]*Em^k ) );
1379
1380    fi;
1381
1382    if IsBound( B!.coeffsmat ) then
1383
1384      # Compute the coefficients with respect to the field extension.
1385      coeffs:= CoeffsCyc( z, B!.conductor ){ B!.coeffslist } * B!.coeffsmat;
1386
1387    fi;
1388
1389    # Return the coefficients list.
1390    return coeffs;
1391    end );
1392
1393
1394#############################################################################
1395##
1396#M  FieldByGenerators( <cycscoll> )
1397#M  FieldByGenerators( <F>, <cycscoll> )
1398##
1399InstallOtherMethod( FieldByGenerators,
1400    "for collection of cyclotomics",
1401    [ IsCyclotomicCollection ],
1402    function( gens )
1403
1404    local N, stab;
1405
1406    N:= Conductor( gens );
1407
1408    # Handle trivial cases.
1409    if   N = 1 then
1410      return Rationals;
1411    elif N = 4 then
1412      return GaussianRationals;
1413    fi;
1414
1415    # Compute the reduced stabilizer info.
1416    stab:= Filtered( PrimeResidues( N ),
1417                     x -> ForAll( gens,
1418                                  gen -> GaloisCyc( gen, x ) = gen ) );
1419
1420    # Construct and return the field.
1421    return AbelianNumberFieldByReducedGaloisStabilizerInfo( Rationals, N,
1422               stab );
1423    end );
1424
1425InstallMethod( FieldByGenerators,
1426    "for field and collection, both collections of cyclotomics",
1427    IsIdenticalObj,
1428    [ IsField and IsCyclotomicCollection, IsCyclotomicCollection ],
1429    function( F, gens )
1430
1431    local N, stab;
1432
1433    N:= Conductor( gens );
1434
1435    if F = Rationals then
1436
1437      # Handle trivial cases.
1438      if   N = 1 then
1439        return Rationals;
1440      elif N = 4 then
1441        return GaussianRationals;
1442      fi;
1443
1444    else
1445      N:= Lcm( N, Conductor( F ) );
1446      gens:= Concatenation( gens, GeneratorsOfField( F ) );
1447    fi;
1448
1449    # Compute the reduced stabilizer info.
1450    stab:= Filtered( PrimeResidues( N ),
1451                     x -> ForAll( gens,
1452                                  gen -> GaloisCyc( gen, x ) = gen ) );
1453
1454    # Construct and return the field.
1455    return AbelianNumberFieldByReducedGaloisStabilizerInfo( F, N, stab );
1456    end );
1457
1458
1459#############################################################################
1460##
1461#M  DefaultFieldByGenerators( <cycscoll> )
1462##
1463InstallMethod( DefaultFieldByGenerators,
1464    "for collection of cyclotomics",
1465    [ IsCyclotomicCollection ],
1466    gens -> CyclotomicField( Conductor( gens ) ) );
1467
1468
1469#############################################################################
1470##
1471#M  CanonicalBasis( <F> )
1472##
1473##  The canonical basis of a field extension $F / K$ for a cyclotomic field
1474##  $F$ is the Zumbroich basis if $K$ is a cyclotomic field.
1475##  Otherwise it is the first normal basis.
1476##
1477InstallMethod( CanonicalBasis,
1478    "for cyclotomic field of cyclotomics",
1479    [ IsCyclotomicField and IsCyclotomicCollection ],
1480    function( F )
1481
1482    local n,
1483          m,
1484          B,
1485          subfield,
1486          zumb,
1487          subvectors,
1488          vectors,
1489          i, j, k, l,
1490          C,
1491          coeffsmat,
1492          val;
1493
1494    n:= Conductor( F );
1495
1496    B:= Objectify( NewType( FamilyObj( F ),
1497                                IsFiniteBasisDefault
1498                            and IsCanonicalBasis
1499                            and IsCanonicalBasisCyclotomicFieldRep ),
1500                   rec() );
1501    SetUnderlyingLeftModule( B, F );
1502    B!.conductor:= n;
1503
1504    subfield:= LeftActingDomain( F );
1505
1506    if IsCyclotomicField( subfield ) then
1507
1508      SetIsIntegralBasis( B, true );
1509
1510      # Construct the Zumbroich basis.
1511      B!.zumbroichbase := ZumbroichBase( n, Conductor( subfield ) );
1512
1513    else
1514
1515      # Compute a normal basis.
1516
1517      # Let $(v_1, \ldots, v_m)$ denote `Basis( F.field ).vectors' and
1518      #     $(w_1, \ldots, w_k)$ denote `vectors'.
1519      # Define $u_{i+m(j-1)} = v_i w_j$.  Then $(u_l; 1\leq l\leq mk)$
1520      # is a $Q$-basis of `F'.  First change from the Zumbroich basis to
1521      # this basis; the matrix is `C'\:
1522
1523      zumb       := ZumbroichBase( n, 1 ) + 1;
1524      subvectors := BasisVectors( Basis( subfield ) );
1525      vectors    := NormalBase( F );
1526      m:= Length( subvectors );
1527      k:= Length( vectors );
1528      C:= [];
1529      for j in vectors do
1530        for i in subvectors do
1531          Add( C, CoeffsCyc( i*j, n ){ zumb } );
1532        od;
1533      od;
1534      C:= C^(-1);
1535
1536      # Let $(c_1, \ldots, c_{mk})$ denote the coefficients with respect
1537      # to the new basis.
1538      # To achieve `<coeffs> \* BasisVectors( <B> ) = <z>' we have
1539      # to take $\sum_{i=1}^m c_{i+m(j-1)} v_i$ as $j$--th coefficient\:
1540
1541      coeffsmat:= [];
1542      for i in [ 1 .. Length( C ) ] do     # for all rows
1543        coeffsmat[i]:= [];
1544        for j in [ 1 .. k ] do
1545          val:= 0;
1546          for l in [ 1 .. m ] do
1547            val:= val + C[i][ m*(j-1)+l ] * subvectors[l];
1548          od;
1549          coeffsmat[i][j]:= val;
1550        od;
1551      od;
1552
1553      SetBasisVectors( B, vectors );
1554      SetIsNormalBasis( B, true );
1555
1556      B!.zumbroichbase := zumb - 1;
1557      B!.coeffsmat     := coeffsmat;
1558
1559    fi;
1560
1561    # Return the basis.
1562    return B;
1563    end );
1564
1565
1566#############################################################################
1567##
1568#M  BasisVectors( <B> )
1569##
1570InstallMethod( BasisVectors,
1571    "for canon. basis of cyclotomic field of cyclotomics",
1572    [ IsBasis and IsCanonicalBasis and IsCanonicalBasisCyclotomicFieldRep ],
1573    function( B )
1574    local e;
1575    # Basis vectors are bound if the subfield is not a cycl. field.
1576#T ??
1577    e:= E( Conductor( UnderlyingLeftModule( B ) ) );
1578    return List( B!.zumbroichbase, x -> e^x );
1579    end );
1580
1581
1582#############################################################################
1583##
1584#M  Coefficients( <B>, <z> )  . . . . . . . . for canon. basis of cycl. field
1585##
1586InstallMethod( Coefficients,
1587    "for canonical basis of cyclotomic field, and cyclotomic",
1588    IsCollsElms,
1589    [ IsBasis and IsCanonicalBasis and IsCanonicalBasisCyclotomicFieldRep,
1590      IsCyc ],
1591    function( B, z )
1592    local N,
1593          coeffs,
1594          F,
1595          m,
1596          zumb,
1597          NN,
1598          Em;
1599
1600    F:= UnderlyingLeftModule( B );
1601    if not z in F then return fail; fi;
1602
1603    N:= B!.conductor;
1604
1605    # Get the Zumbroich basis representation of <z> in `N'-th roots.
1606    coeffs:= CoeffsCyc( z, N );
1607    if coeffs = fail then return fail; fi;
1608
1609    F:= LeftActingDomain( F );
1610
1611    if   IsPrimeField( F ) then
1612
1613      # Get the Zumbroich basis coefficients (basis $B_{n,1}$)
1614      coeffs:= coeffs{ B!.zumbroichbase + 1 };
1615
1616    elif IsCyclotomicField( F ) then
1617
1618      # Get the Zumbroich basis coefficients (basis $B_{n,m}$) directly.
1619      m:= Conductor( F );
1620      zumb:= CanonicalBasis( F )!.zumbroichbase;
1621      NN:= N/m;
1622      Em:= E(m);
1623      coeffs:= List( B!.zumbroichbase,
1624                     j->Sum( zumb, k->coeffs[ ((k*NN+j) mod N )+1 ]*Em^k ) );
1625
1626    else
1627
1628      # The subfield is not a cyclotomic field.
1629      # The necessary information is stored in `B!.coeffsmat'.
1630      coeffs:= coeffs{ B!.zumbroichbase + 1 } * B!.coeffsmat;
1631
1632    fi;
1633
1634    # Return the list of coefficients.
1635    return coeffs;
1636    end );
1637
1638
1639#############################################################################
1640##
1641#V  Cyclotomics . . . . . . . . . . . . . . . . . .  field of all cyclotomics
1642##
1643InstallValue( Cyclotomics, Objectify( NewType(
1644    CollectionsFamily( CyclotomicsFamily ),
1645    IsField and IsAttributeStoringRep ),
1646    rec() ) );
1647SetName( Cyclotomics, "Cyclotomics" );
1648SetLeftActingDomain( Cyclotomics, Rationals );
1649SetIsFiniteDimensional( Cyclotomics, false );
1650SetIsFinite( Cyclotomics, false );
1651SetIsWholeFamily( Cyclotomics, true );
1652SetDegreeOverPrimeField( Cyclotomics, infinity );
1653SetDimension( Cyclotomics, infinity );
1654SetRepresentative(Cyclotomics, 0);
1655
1656
1657#############################################################################
1658##
1659##  Automorphisms of abelian number fields
1660##
1661
1662
1663#############################################################################
1664##
1665#R  IsANFAutomorphismRep( <obj> )
1666##
1667DeclareRepresentation( "IsANFAutomorphismRep",
1668    IsAttributeStoringRep, [ "galois" ] );
1669
1670
1671#############################################################################
1672##
1673#P  IsANFAutomorphism( <obj> )
1674##
1675DeclareSynonym( "IsANFAutomorphism", IsANFAutomorphismRep
1676    and IsFieldHomomorphism
1677    and IsMapping
1678    and IsBijective );
1679
1680
1681#############################################################################
1682##
1683#M  ExponentOfPowering( <map> )
1684##
1685InstallMethod( ExponentOfPowering,
1686    "for an ANFAutomorphism",
1687    [ IsMapping and IsANFAutomorphismRep ],
1688    map -> map!.galois );
1689
1690InstallMethod( ExponentOfPowering,
1691    "for an identity mapping",
1692    [ IsMapping and IsOne ],
1693    map -> 1 );
1694
1695InstallMethod( ExponentOfPowering,
1696    "for a mapping (check whether it is the identity mapping)",
1697    [ IsMapping ],
1698    function( map )
1699    if IsOne( map ) then
1700      return 1;
1701    else
1702      TryNextMethod();
1703    fi;
1704    end );
1705
1706
1707#############################################################################
1708##
1709#F  ANFAutomorphism( <F>, <k> )  . .  automorphism of an abelian number field
1710##
1711InstallGlobalFunction( ANFAutomorphism, function ( F, k )
1712
1713    local galois, aut;
1714
1715    # check the arguments
1716    if not ( IsAbelianNumberField(F) and IsCyclotomicCollection(F) ) then
1717      Error("<F> must be an abelian number field consisting of cyclotomics");
1718    elif not IsRat( k ) then
1719      Error( "<k> must be an integer" );
1720    fi;
1721    if not IsInt( k ) then
1722#T this is a hack ...
1723      k:= k mod Conductor( F );
1724    fi;
1725    if Gcd( Conductor( F ), k ) <> 1 then
1726      Error( "<k> must be coprime to the conductor of <F>" );
1727    fi;
1728
1729    # Let $F / K$ be a field extension where $Q_n$ is the conductor of $F$;
1730    # let $S(F)$ be the group of those prime residues mod $n$ that fix $F$
1731    # pointwise.  The Galois group of $F / K$ is in natural correspondence
1732    # to $S(K) / S(F)$.  Thus each automorphism of $F / K$ corresponds to
1733    # a coset $c$ of $S(K)$, and it acts on $F$ like each element of $c$.
1734    # The automorphism `ANFAutomorphism( F/K, k )' maps $x\in F / K$ to
1735    # `GaloisCyc( <x>, k )'.
1736
1737    # Choose the smallest representative ...
1738    galois:= Set(List(GaloisStabilizer( F ), x->x*k mod Conductor( F )))[1];
1739    if galois = 1 then
1740      return IdentityMapping( F );
1741    fi;
1742
1743    # make the mapping
1744    aut:= Objectify( TypeOfDefaultGeneralMapping( F, F,
1745                             IsSPGeneralMapping
1746                         and IsANFAutomorphism ),
1747                     rec() );
1748
1749    aut!.galois:= galois;
1750
1751    return aut;
1752end );
1753
1754
1755#############################################################################
1756##
1757#M  \=( <aut1>, <aut2> )  . . . .  for automorphisms of abelian number fields
1758#M  \=( <id>, <aut> ) . . . . . .  for automorphisms of abelian number fields
1759#M  \=( <aut>, <id> ) . . . . . .  for automorphisms of abelian number fields
1760##
1761InstallMethod( \=,
1762    "for two ANF automorphisms",
1763    IsIdenticalObj,
1764    [ IsFieldHomomorphism and IsANFAutomorphismRep,
1765      IsFieldHomomorphism and IsANFAutomorphismRep ],
1766    function ( aut1, aut2 )
1767    return     Source( aut1 ) = Source( aut2 )
1768           and aut1!.galois = aut2!.galois;
1769    end );
1770
1771InstallMethod( \=,
1772    "for identity mapping and ANF automorphism",
1773    IsIdenticalObj,
1774    [ IsMapping and IsOne,
1775      IsFieldHomomorphism and IsANFAutomorphismRep ],
1776    function ( id, aut )
1777    return     Source( id ) = Source( aut )
1778           and aut!.galois = 1;
1779    end );
1780
1781InstallMethod( \=,
1782    "for ANF automorphism and identity mapping",
1783    IsIdenticalObj,
1784    [ IsFieldHomomorphism and IsANFAutomorphismRep,
1785      IsMapping and IsOne ],
1786    function ( aut, id )
1787    return     Source( id ) = Source( aut )
1788           and aut!.galois = 1;
1789    end );
1790
1791
1792#############################################################################
1793##
1794#M  \<( <aut1>, <aut2> )  . . . .  for automorphisms of abelian number fields
1795##
1796InstallMethod( \<,
1797    "for two ANF automorphisms",
1798    IsIdenticalObj,
1799    [ IsFieldHomomorphism and IsANFAutomorphismRep,
1800      IsFieldHomomorphism and IsANFAutomorphismRep ],
1801    function ( aut1, aut2 )
1802    return    Source( aut1 ) < Source( aut2 )
1803           or (     Source( aut1 ) = Source( aut2 )
1804                and aut1!.galois < aut2!.galois );
1805    end );
1806
1807InstallMethod( \<,
1808    "for identity mapping and ANF automorphism",
1809    IsIdenticalObj,
1810    [ IsMapping and IsOne,
1811      IsFieldHomomorphism and IsANFAutomorphismRep ],
1812    function ( id, aut )
1813    return    Source( id ) < Source( aut )
1814           or (     Source( id ) = Source( aut )
1815                and 1 < aut!.galois );
1816    end );
1817
1818InstallMethod( \<,
1819    "for ANF automorphism and identity mapping",
1820    IsIdenticalObj,
1821    [ IsFieldHomomorphism and IsANFAutomorphismRep,
1822      IsMapping and IsOne ],
1823    function ( aut, id )
1824    return Source( aut ) < Source( id );
1825    end );
1826
1827
1828#############################################################################
1829##
1830#M  ImageElm( <aut>, <cyc> )  . .  for automorphisms of abelian number fields
1831##
1832InstallMethod( ImageElm,
1833    "for ANF automorphism and scalar",
1834    FamSourceEqFamElm,
1835    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsCyc ],
1836    function ( aut, elm )
1837    return GaloisCyc( elm, aut!.galois );
1838    end );
1839
1840
1841#############################################################################
1842##
1843#M  ImagesElm( <aut>, <cyc> ) . .  for automorphisms of abelian number fields
1844##
1845InstallMethod( ImagesElm,
1846    "for ANF automorphism and scalar",
1847    FamSourceEqFamElm,
1848    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsScalar ],
1849    function ( aut, elm )
1850    return [ GaloisCyc( elm, aut!.galois ) ];
1851    end );
1852
1853
1854#############################################################################
1855##
1856#M  ImagesSet( <aut>, <field> ) .  for automorphisms of abelian number fields
1857##
1858InstallMethod( ImagesSet,
1859    "for ANF automorphism and field",
1860    CollFamSourceEqFamElms,
1861    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsField ],
1862    function ( aut, F )
1863    return F;
1864    end );
1865
1866
1867#############################################################################
1868##
1869#M  ImagesRepresentative( <aut>, <cyc> )  . . for autom. of ab. number fields
1870##
1871InstallMethod( ImagesRepresentative,
1872    "for ANF automorphism and scalar",
1873    FamSourceEqFamElm,
1874    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsScalar ],
1875    function ( aut, elm )
1876    return GaloisCyc( elm, aut!.galois );
1877    end );
1878
1879
1880#############################################################################
1881##
1882#M  PreImageElm( <aut>, <cyc> ) . . . . . . . for autom. of ab. number fields
1883##
1884InstallMethod( PreImageElm,
1885    "for ANF automorphism and scalar",
1886    FamRangeEqFamElm,
1887    [ IsFieldHomomorphism and IsBijective and IsANFAutomorphismRep,
1888      IsScalar ],
1889    function ( aut, elm )
1890    return GaloisCyc( elm, ( 1 / aut!.galois )
1891                           mod Conductor( Range( aut ) ) );
1892    end );
1893
1894
1895#############################################################################
1896##
1897#M  PreImagesElm( <aut>, <cyc> )  . . . . . . for autom. of ab. number fields
1898##
1899InstallMethod( PreImagesElm,
1900    "for ANF automorphism and scalar",
1901    FamRangeEqFamElm,
1902    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsScalar ],
1903    function ( aut, elm )
1904    return [ GaloisCyc( elm, ( 1 / aut!.galois )
1905                             mod Conductor( Range( aut ) ) ) ];
1906    end );
1907
1908
1909#############################################################################
1910##
1911#M  PreImagesSet( <aut>, <field> )  . . . . . for autom. of ab. number fields
1912##
1913InstallMethod( PreImagesSet,
1914    "for ANF automorphism and scalar",
1915    CollFamRangeEqFamElms,
1916    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsField ],
1917    function ( aut, F )
1918    return F;
1919    end );
1920
1921
1922#############################################################################
1923##
1924#M  PreImagesRepresentative( <aut>, <cyc> ) . for autom. of ab. number fields
1925##
1926InstallMethod( PreImagesRepresentative,
1927    "for ANF automorphism and scalar",
1928    FamRangeEqFamElm,
1929    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsScalar ],
1930    function ( aut, elm )
1931    return GaloisCyc( elm, ( 1 / aut!.galois )
1932                           mod Conductor( Range( aut ) ) );
1933    end );
1934
1935
1936#############################################################################
1937##
1938#M  CompositionMapping2( <aut2>, <aut1> ) . . for autom. of ab. number fields
1939##
1940InstallMethod( CompositionMapping2,
1941    "for two ANF automorphisms",
1942    FamSource1EqFamRange2,
1943    [ IsFieldHomomorphism and IsANFAutomorphismRep,
1944      IsFieldHomomorphism and IsANFAutomorphismRep ],
1945    function ( aut1, aut2 )
1946    return ANFAutomorphism( Source( aut1 ), aut1!.galois * aut2!.galois );
1947    end );
1948
1949
1950#############################################################################
1951##
1952#M  InverseGeneralMapping( <aut> )  . . . . . for autom. of ab. number fields
1953##
1954InstallOtherMethod( InverseGeneralMapping,
1955    "for ANF automorphism",
1956    [ IsFieldHomomorphism and IsANFAutomorphismRep ],
1957    aut -> ANFAutomorphism( Source( aut ), 1 / aut!.galois ) );
1958
1959
1960#############################################################################
1961##
1962#M  \^( <aut>, <n> )  . . . . . . . . . . . . for autom. of ab. number fields
1963##
1964InstallMethod( \^,
1965    "for ANF automorphism and integer",
1966    [ IsFieldHomomorphism and IsANFAutomorphismRep, IsInt ],
1967    function ( aut, i )
1968    return ANFAutomorphism( Source( aut ), aut!.galois^i );
1969    end );
1970
1971
1972#############################################################################
1973##
1974#M  PrintObj( <aut> ) . . . . . . . . . . . . for autom. of ab. number fields
1975##
1976InstallMethod( PrintObj,
1977    "for ANF automorphism",
1978    [ IsFieldHomomorphism and IsANFAutomorphismRep ],
1979    function ( aut )
1980    Print( "ANFAutomorphism( ", Source( aut ), ", ", aut!.galois, " )" );
1981    end );
1982
1983
1984#############################################################################
1985##
1986#M  GaloisGroup( <F> )  . . . . . . . Galois group of an abelian number field
1987##
1988##  The required group is a factor group of the Galois group $G$
1989##  of the enveloping cyclotomic field.
1990##  So the group $U$ generated by the actions of the generators of $G$ on <F>
1991##  is the Galois group of <F>, viewed as field over the rationals.
1992##
1993##  If <F> is a field over a proper extension of the rationals then we take
1994##  the pointwise stabilizer of the subfield in $U$.
1995##
1996InstallMethod( GaloisGroup,
1997    "for abelian number field ",
1998    [ IsAbelianNumberField ],
1999    function( F )
2000    local group;
2001
2002    group:= GroupByGenerators( List( Flat(
2003                    GeneratorsPrimeResidues( Conductor( F ) ).generators ),
2004                        x -> ANFAutomorphism( F, x ) ),
2005                IdentityMapping( F ) );
2006
2007    if not IsPrimeField( LeftActingDomain( F ) ) then
2008      group:= Stabilizer( group,
2009                  GeneratorsOfField( LeftActingDomain( F ) ), OnTuples );
2010    fi;
2011
2012    return group;
2013end );
2014
2015
2016InstallMethod( Representative, [IsCyclotomicField], f->0);
2017