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