/************************************************************************* Input: K real quadratic field l small prime number ( l = 3, 5, 7 ) P all prime divisors of conductor(L/K) in K module conductor of L/K rcgp ray class group with conductor supported in P subgrp subgroup of rcgp corresponding to Kp Description: This is an implementation of the algorithm described in "Numerical evidence for a conjectural generalization of Hilbert's Theorem 132" Important hypothesis: h_K = 1 Author: Dimitrij Kusnezow Output: vector w = [flag, v] of length 2 flag = 1 iff the conjecture is valid v is a vector with the following components: v[1] Kp as output by bnfinit v[2] 2-component vector v[2][1] embedding K in Kp v[2][2] wildly ramify places of Kp v[3] representative of rcgp mod subgroup v[4] isomorphism iso: Kp ---> Kp so that Artin symbol of v[3] equals iso v[5] 2-component vector of Galois orbit representatives of the infinity places of Kp v[6] representation of iso on the ring of integers of Kp v[7] 2-component vector v[7][1] uniformizer of K korresponding to wp ( wildly ramify plasec of K ) v[7][2] uniformizer of Kp korresponding to WP ( wildly ramify places of Kp ) v[8] 2-component vector v[8][1] the HNF of a projectiv gitter L such that the localization of L at all places ( WP exclusive ) equals to the ring of integers of Kp v[8][2] the Z-basis of L v[9] LW ( the localization of the L at WP, respective the components of WP ) given by a Z-basis; each basis element an algebraic numbers (use settomatrix to convert to HNF) v[10] a "normal basis generator('s)" of the localization ( at WP ) of L. The "" means hier that the index of such generator is minimal in L v[11] generator('s) of the image of phi v[12] cokern( phi ) v[13] the representation of iso on the cokern( phi ) v[14] fitting ideal('s) of the cokern(phi) v[15] IvL v[16] DetL v[17] NormRes v[18] 2-component vector v[18][1] TauLK v[18][2] TauLKInv v[19] xiLKInv v[20] the HNF of the matrix A v[21] the minimal exponents m of the wildly ramify places of Kp/K such that P^m \in O_K[G]\teta_v. \teta_v is the corresponding NBE. v[22] the structure of (O_Kp/P^m)^\times v[23] the matrix A (article, page 16) v[24] the N from the exp-log condition v[25] exp-image of the (O_K[G]\teta_v/P^m) v[26] \lambda (article, page 17) v[27] DetL*InvId := I (article, page 17) v[28] \lambda*DetL = \lambda*I (article, page 17) v[29] SNF of B (article, page 17) v[30] not used v[31] not used *************************************************************************/ /* K = Grundkoerper, l = ord( G ), wp = Vektor mit wildverzweigten Stellen */ Hilbert( K, l, P, module, rcgp, subgrp )= { local( h, Kp, tmp, puffer ); local( allisos, vertreter, iso, embed, alpha, DS ); local( wp, WP, N ); local( nbe, lnbe, Gitter ); local( L, LW, expLW, testloc, testproj ); local( Phi, CokPhi, GRep, FittId ); local( IvL, DetL, b, NormRes, TauLK, TauLKInv, xiLK, UnChar ); local( Z, s, InvId, A ); local( dLK, DLK ); result = vector( 31, i, 0 ); /* globale Variablen sind uniformizerK, UniformiserKp, WPStar0, WPStar1, result */ print( " Berechne Kp \n" ); h = bnrstark( rcgp, subgrp, 2 ); Kp = bnfinit( h ); result[1] = Kp; print( " Kp ist berechnet \n" ); for( i = 1, 3, write( outfile, "/*********************************************************************/" ); ); write( outfile, " f = ", K.pol, ";" ); write( outfile, " l = ", l, ";" ); write( outfile, " P = ", P, ";" ); write( outfile, " module = ", idealfactor( K, module ), ";" ); write( outfile, " module = ", module, ";" ); write( outfile, " subgrp = ", subgrp, ";" ); write( outfile, " h = ", h, ";" ); /* Hier wird die richtige Einbettung ( K -> Kp ) berechnet */ print( " Vor FindEmbedGalCond \n" ); embed = FindEmbedGalCond( K, Kp, module, subgrp ); result[2] = vector( 2, i, 0 ); result[2][1] = embed; print( " Nach FindEmbedGalCond \n" ); /* wildverzweigte Stellen in K bzw. Kp */ wp = idealprimedec( K, l ); WP = findwildplace( K, Kp, embed, module ); result[2][2] = WP; /* Berechne den zum Frobenius korrespondierenden Automorphismus von Kp und die dazugehoerige Einbettung in die komplexen Zahlen */ print( " Berechne Frobenius und die archimedische Stelle \n" ); allisos = nfgaloisconj( Kp ); if( length( allisos ) == 2*l, print( " Kp/Q ist Galoissch mit Diedergruppe \n" ); write( outfile, " Kp/Q ist Galoissch mit Diedergruppe; " ); ); /* Wähle Automorphismen, die K festhalten */ puffer = List([x]); for( i = 2, length( allisos ), tmp = nfgaloispowapply( Kp, allisos[i], l, Mod( variable( Kp.pol ), Kp.pol ) ); if( tmp == Mod( variable( Kp.pol ), Kp.pol ), puffer = concat( puffer, List( [allisos[i]] ) ); ); ); vertreter = findvertreter( rcgp, subgrp, l ); result[3] = vertreter; iso = findisoquick( K, Kp, rcgp, l, vertreter, puffer, embed ); result[4] = iso; alpha = findplace( Kp, l, iso ); result[5] = alpha; print( " Frobenius und die archimedische Stelle sind ausgerechnet \n" ); /* Darstellung von iso auf O(Kp) */ DS = darstaddsigma( Kp, iso ); result[6] = DS; /* Vektor mit Uniformisierenden zu den wildverzweigten Stellen in K bzw in Kp */ uniformizerK = FindUniformizer( K, wp ); UniformizerKp = FindUniformizer( Kp, WP ); result[7] = vector(2, i, 0 ); result[7][1] = uniformizerK; result[7][2] = UniformizerKp; /* Bestimme tmp mit [O(Kp):O(K)G*nbe] minimal */ print( " Bestimme NBE \n" ); lnbe = vector( length( WP ), i, 0 ); /* Potenz respektive der exp-log-Bedungung */ N = vector( length( WP ), i, 0 ); for( i = 1, length( N ), tmp = idealval( Kp, l, WP[i] )/( l - 1 ); if( tmp == ceil( tmp ), N[i] = ceil( tmp ) + 1, N[i] = ceil( tmp ); ); ); result[24] = N; for( i = 1, length( lnbe ), Gitter = idealpow( Kp, WP[i], N[i] ); lnbe[i] = FindBestNB( K, Kp, Gitter, embed, DS, l ); ); result[10] = lnbe; print( " NBE ist bestimmt \n" ); /* Falls L/K schwachverzweigt ist, rechne mit der Wurzel der inversen Differente */ if( idealval( K, module, wp[1] ) == 2, print( " Rechne mit der inversen Differente \n" ); write( outfile, " Berechne L mit der inversen Differente " ); tmp = CompMitInvDiff( K, Kp, embed, module, wp, WP, N, l ); L = tmp[1]; LW = tmp[2], /* L ist projektiv und lokal gleich dem O(Kp), ausgenommen die wildverzweigten Stellen */ print( " Bestimme L \n" ); tmp = CompProj( K, Kp, embed, wp, WP, N, lnbe, l, DS ); L = tmp[1]; LW = tmp[2]; print( " L ist ausgerechnet \n" ); ); result[8] = vector( 2, i, 0 ); result[8][1] = L; result[8][2] = matrixtoset( Kp, L ); result[9] = LW; /***********************************************************************/ /************************ Teste: L ist projektiv ***********************/ /*********************** und local gleich dem O(K) *********************/ /***********************************************************************/ testloc = testloceq( K, Kp, embed, L, matid( poldegree( Kp.pol ) ), wp ); testproj = isprojectiv( L, DS ); if( testloc, write( outfile, "Gittern sind local gleich" ), write( outfile, "Gittern sind nicht local gleich" ); ); if( testproj, write( outfile, "Gitter ist projektiv" ), write( outfile, "Gitter ist nicht projektiv" ); ); /***********************************************************************/ /*************************** Ende der Teste ****************************/ /***********************************************************************/ print( " Bestimme Phi \n" ); /* Ein erzeuzender des Bildes von phi */ Phi = CompPhi( K, wp, module, rcgp, subgrp, vertreter, l ); result[11] = Phi; print( " Phi ist ausgerechnet \n" ); print( " Bestimme ExpLW \n" ); tmp = ExpRestLW( K, Kp, WP, N, LW ); /* Das Bild von LW in der Lokalisierung nach WP unter der Exponentenabbildung */ ExpLW = tmp[1]; result[25] = ExpLW; m = tmp[2]; /* enthaelt Potezen von wildverzweigten Stellen, die in Komponenten von LW liegen */ result[21] = m; print( " ExpLW ist ausgerechnet \n" ); /* Multiplikative Gruppe von O(Kp)/P^m */ WPStar0 = vector( length( lnbe ), i, idealstar( Kp, idealpow( Kp, WP[i], m[i] ), 0 ) ); WPStar1 = vector( length( lnbe ), i, idealstar( Kp, idealpow( Kp, WP[i], m[i] ), 1 ) ); result[22] = WPStar0; /* CompCokPhi */ print( " Bestimme CokPhi \n" ); /* Bestimmung der Factorgruppe ( coker( phi ) ). Liefert die Smithsche Normalform vom Quotienten ( UniformizerKp^Z + WPStar0 / Phi^Z + ExpLW ). */ CokPhi = CompCokPhi( K, Kp, embed, Phi, WP, ExpLW, m, l ); print( " CokPhi ist ausgerechnet \n" ); /* CompGRep */ print( " Bestimme GRep \n" ); /* Darstellung von iso auf CokPhi */ GRep = CompGRep( K, Kp, iso, WP, CokPhi ); result[13] = GRep; print( " GRep ist ausgerechnet \n" ); /* CalcFittIdeals */ print( " Bestimme FittId \n" ); /* HNF des Fittingideals ueber Z */ FittId = CalcFittIdeals( CokPhi, GRep, l ); result[14] = FittId; print( " FittId ist ausgerechnet \n" ); /* CompIvL */ print( " Bestimme IvL \n" ); IvL = CompIvL( K, Kp, embed, FittId, Phi, wp, WP, l ); result[15] = IvL; print( " IvL ist ausgerechnet \n" ); /* CompDetL */ print( " Bestimme DetL \n" ); b = vector( length( K.zk ), i, Mod( subst( K.zk[i], variable( K.zk[i] ), embed ), Kp.pol )*lnbe[1] ); DetL = CompDetL( K, Kp, embed, b, iso, L, l ); result[16] = DetL; print( " DetL ist ausgerechnet \n" ); /* NormRes */ print( " Bestimme NormRes \n" ); NormRes = NormResolvent( Kp, b, alpha, iso, l ); result[17] = NormRes; print( " NormRes ist ausgerechnet \n" ); /* detL ist nun eigentlich detL*NormResolvent */ /* CompTauLK */ print( " Bestimme TauLK und TauLKInv \n" ); tmp = CompTauLK( K, subgrp, vertreter, rcgp, module, l ); TauLK = tmp[1]; TauLKInv = tmp[2]; result[18] = vector(2, i, 0 ); result[18][1] = TauLK; result[18][2] = TauLKInv; print( " TauLK und TauLKInv sind ausgerechnet \n" ); UnChar = UnramChar( K, module, l ); xiLKInv = RGMult( TauLKInv, UnramChar( K, module, l ) ); result[19] = xiLKInv; print( " Verifiziere die Vermutung \n" ); A = VerifyConj( IvL, DetL, xiLKInv, NormRes ); if( A == matid( l ), print( " THE CONJECTURE IS VALID \n" ); result[20] = A; write( outfile, " A = ", A ); return( [ 1, result] ), print( " COUNTER EXAMPLE ( you should doubt the correctness of the computation ) \n" ); return( [ 0, result] ); ); } /***************************************************************************/ /********************************* END ***********************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /************FUNCTIONS RELATED TO THE SPECIFIC PROBLEM**********************/ /***************************************************************************/ /***************************************************************************/ /* Berechnet den Schnitt von lokalen Komponenten. wp = die wildverzweigten Stellen in bnf, WP = die in bnfext. */ CompProj( bnf, bnfext, embed, wp, WP, N, lnbe, l, DS )= { local( i, LW ); LW = LocalComp( bnf, bnfext, embed, wp, WP, N, lnbe, l, DS ); for( i = 1, length( LW ), LW[i] = mathnf( veclisttomatrix( LW[i] ) ); LW[i] = matrixtoset( bnfext, LW[i] ); ); L = bnfext.zk; for( i = 1, length( LW ), L = gitterintersect( bnfext, L, LW[i] ); ); L = mathnf( settomatrix( bnfext, L ) ); return( [L, LW] ); } /* Berechnet lokale Komponenten von LW, WP = wildverzweigte Stellen in bnfext */ LocalComp( bnf, bnfext, embed, wp, WP, N, lnbe, l, DS )= { local( i, OGSpan, /*N,*/ PP ); local( RS, RSV, RSValg, exponent ); local( RSU, LW, TMP, basis ); /* Hier wird O(bnf)[G]-Aufspann von einem Element in L berechnet */ OGSpan = vector( length( lnbe ), i, 0 ); for( i = 1, length( OGSpan ), OGSpan[i] = galoissubspandar( bnf, bnfext, embed, lnbe[i], DS ); ); PP = vector( length( WP ), i, idealpow( bnfext, WP[i], N[i] ) ); /* ACHTUNG: ACHTUNG: ACHTUNG: ACHTUNG: ACHTUNG: ACHTUNG: ACHTUNG: ACHTUNG: ACHTUNG: Das folgende ist zwar korrekt, aber umstaendlich: ist ist schneller gleich ein Vertretersystem von PP[i]^exponent[i] zu berechnen. Dann spart man sich die naechste doppelte for-Schleife */ RS = vector( length( lnbe ), i, gittermodgitter( idealhnf( bnfext, PP[i] ), OGSpan[i][1] ) ); RSV = vector( length( lnbe ), i, List([]) ); exponent = vector( length( lnbe ), i, idealval( bnfext, lnbe[i], WP[i] ) ); /* Filtriere Representanten mit genuegend grossem l-exponenten aus */ for( j = 1, length( RS ), for( i = 1, length( RS[j] ), if( idealval( bnfext, nfbasistoalg( bnfext, RS[j][i] ), WP[j] ) >= exponent[j], RSV[j] = concat( RSV[j], List( [RS[j][i]] ) ); ); ); ); /* Hier pruefe die p-Wert Bedingung der bnf-Koordinaten ( Erzeugnis ueber Lokalisierung von O(bnf)[G] nach wildverzweigter Stelle ). Die berechnete Elementenmenge zusammen mit den Galois-Konjugierten von vau erzeugt dann eine der L-"p-Komponenten" ueber O(bnf), folglich wird mit bnf.zk multipliziert ( Berechnung vom Schnitt erfordet Berechnung von Dualgittern, die hier ueber Z gemacht wird ) */ /* LW hat als Komponenten die zu den wildverzweigten Stellen korrespondierende Gitter */ basis = vector( length( lnbe ), i, vector( l, j, ( DS^j )*nfalgtobasis( bnfext, lnbe[i] ) ) ); for( i = 1, length( basis ), for( j = 1, length( basis[i] ), basis[i][j] = nfbasistoalg( bnfext, basis[i][j] ); ); ); RSValg = vector( length( lnbe ), i, vector( length( RSV[i] ), j, nfbasistoalg( bnfext, RSV[i][j] ) ) ); LW = vector( length( lnbe ), i, vector( length( RSValg[i] ), j, 0 ) ); for( i = 1, length( LW ), for( j = 1, length( LW[i] ), LW[i][j] = lift( findbasiskoeff( bnf, bnfext, basis[i], embed, RSValg[i][j] ) ); ); ); for( i = 1, length( LW ), LW[i] = subst( LW[i], variable( bnf.pol ), embed ); ); for( i = 1, length( LW ), tmp = CheckValue( bnfext, LW[i], WP[i] ); LW[i] = tmp[1]; ); RSU = vector( length( lnbe ), j, vector( length( bnf.zk )*length( LW[j] ), i, 0 ) ); TMP = vector( length( lnbe ), i, vector( length( LW[i] ), j, 0 ) ); for( i = 1, length( TMP ), for( j = 1, length( TMP[i] ), TMP[i][j] = basiskoefftoelt( bnf, bnfext, basis[i], LW[i][j], embed, 0 ); ); ); tmp = vector( length( bnf.zk ), i, subst( bnf.zk[i], variable( bnf.pol ), embed ) ); /* Multipliziere L-Komponenten mit O(bnf) */ for( i = 1, length( TMP ), for( j = 1, length( TMP[i] ), for( k = 1, length( tmp ), RSU[i][ (j - 1 )*length( tmp ) + k ] = TMP[i][j]*tmp[k]; ); ); ); for( i = 1, length( RSU ), for( j = 1, length( RSU[i] ), RSU[i][j] = nfalgtobasis( bnfext, RSU[i][j] ); ); ); /* Galois-Konjugierten von vau hinzunehmen */ for( i = 1, length( LW ), TMP = List([]); for( j = 1, length( RSU[i] ), TMP = concat( TMP, List( [RSU[i][j]] ) ); ); LW[i] = concat( TMP, OGSpan[i][2] ); LW[i] = complement( LW[i], vector( poldegree( bnfext.pol ), i, 0 ) ); ); return( LW ); } /* Berechnung des zu der inversen Differente isomorphen Gitters L, das lokal ueberall bis auf die wildverzweigten Stellen gleich dem O(bnfext) ist */ CompMitInvDiff( bnf, bnfext, embed, module, wp, WP, N, l )= { local( i, tmp, corr, val, /*N,*/ LL, LLW ); LL = 1; for( i = 1, length( WP ), LL = idealmul( bnfext, LL, idealpow( bnfext, WP[i], 1 - l ) ); ); corr = vector( length( wp ), i, 0 ); for( i = 1, length( corr ), tmp = bnfisprincipal( bnf, wp[i] )[1]; tmp = calcord( tmp, bnf.clgp[2] ); tmp = idealpow( bnf, wp[i], tmp ); tmp = bnfisprincipal( bnf, tmp )[2]; /* Ein Hauptideal nach Konstruktion */ corr[i] = nfbasistoalg( bnf, tmp ); corr[i] = lift( corr[i] ); corr[i] = subst( corr[i], variable( bnf.pol ), embed ); corr[i] = Mod( corr[i], bnfext.pol ); ); for( i = 1, length( WP ), val = idealval( bnfext, LL, WP[i] ); tmp = ( N[i] - val )/idealval( bnfext, corr[i], WP[i] ); if( tmp == ceil( tmp ), tmp += 1, tmp = ceil( tmp ); ); LL = idealmul( bnfext, LL, corr[i]^tmp ); ); LLW = vector( length( WP ), i, idealpow( bnfext, WP[i], idealval( bnfext, LL, WP[i] ) ) ); for( i = 1, length( LLW ), LLW[i] = matrixtoset( bnfext, LLW[i] ); ); return( [LL, LLW] ); } /* Berechne phi(1). wp = die wildverzweigten Stellen in bnf */ CompPhi( bnf, wp, module, rcgp, subgrp, vertreter, l )= { local( eps, len, AS, piexp, nonorm, korr, AST, piexpT ); len = length( uniformizerK ); eps = vector( len, i, uniformizerK[i] ); /* locale Artin-Symbole von unif[i] in den korresp. Lokalisierungen */ AS = vector( len, i, artinglobal( bnf, uniformizerK[i], wp[i], uniformizerK[i], module ) ); piexp = vector( len, i, findexp( AS[i], rcgp, subgrp, vertreter, l ) ); /* Korrektur des Artin-Symbols, falls noetig */ for( i = 1, len, if( piexp[i] != 1, nonorm = FindNoNorm( bnf, wp[i], uniformizerK[i], module, rcgp, subgrp, vertreter, l ); korr = lift( Mod( ( 1 - piexp[i] )*nonorm[2]^( -1 ), l ) ); eps[i] = eps[i]*nfbasistoalg( bnf, nonorm[1] )^korr; ); ); /* Teste ob Artin-Symbole nun korrekt */ AST = vector( len, i, artinglobal( bnf, eps[i], wp[i], uniformizerK[i], module ) ); piexpT = vector( len, i, findexp( AST[i], rcgp, subgrp, vertreter, l ) ); print( " AS-Test = ", piexpT, " \n " ); return( eps ); } /* Finde eine Nichtnorm in bnf, moeglichst eine Einheit. Falls nicht, so nehme eine Uniformisierende zu einem traege Ideal */ FindNoNorm( bnf, prim, unif, module, rcgp, subgrp, vertreter, l )= { local( as, asexp, s, IdStar ); s = idealval( bnf, module, prim ); /* Probiere Einheiten aus */ for( i = 1, length( bnf.fu ), as = artinglobal( bnf, Mod( bnf.fu[i], bnf.pol ), prim, unif, module ); asexp = findexp( as, rcgp, subgrp, vertreter, l ); if( asexp != 0, /* locale Nichtnorm gefunden */ return( [ nfalgtobasis( bnf, bnf.fu[i] ), asexp ] ); ); /* Erzeugende von ( O(bnf)/bnfprim^s )^* */ IdStar = idealstar( bnf, idealpow( bnf, prim, s ), 0 )[3]; for( i = 1, length( IdStar ), IdStar[i] = nfbasistoalg( bnf, IdStar[i] ); as = artinglobal( bnf, IdStar[i], prim, unif, module ); asexp = findexp( as, rcgp, subgrp, vertreter, l ); if( asexp != 0, /* locale Nichtnorm gefunden */ return( [ IdStar[i], asexp ] ); ); ); ); print( " In FindNoNorm: es kann keine lokale Nichtnorm gefunden werden \n " ); return( 0 ); } /* Exp-Entwicklung von LW[i] in den Lokalisierungen nach WP[i] */ ExpRestLW( bnf, bnfext, WP, N, LW )= { local( i, m, s, tmp, /*N,*/ expRestLW ); /* Konvertiere LW-Komponenten in Ideale */ for( i = 1, length( LW ), LW[i] = mathnf( settomatrix( Kp, LW[i] ) ); ); /* finde gnuegend grosse Potenzen von WP[i]: m, so dass WP[i]^m in Komponenten von LW enthalten ist */ m = vector( length( LW ), i, 0 ); for( i = 1, length( m ), tmp = idealhnf( bnfext, WP[i] ); s = 1; /* sichert Terminierung der Schleife */ while( s < 200 && !gittertestin( LW[i], tmp ), tmp = idealhnf( bnfext, idealmul( bnfext, tmp, WP[i] ) ); s++; ); m[i] = s; if( s >= 200, print( " In ExpLWModP: Keine Potenz von WP[", i, "] liegt in LW[" i, "] \n " ); print( " In ExpLWModP: s = ", s, " \n " ); ); ); /* Entwicklung der Repraesentanten in eine Exponentialreihe */ expRestLW = vector( length( LW ), i, vector( length( LW[i] ), j, 0 ) ); for( i = 1, length( expRestLW ), expRestLW[i] = expimage( bnfext, LW[i], WP[i], m[i], N[i] ); ); return( [expRestLW, m] ); } /* Berechnung von Kokern( phi ) */ CompCokPhi( bnf, bnfext, embed, Phi, WP, ExpLW, m, l )= { local( i, CokPhi ); /* Berechnung von coker( phi ) */ /* Lese Komponenten von Phi in bnfext */ for( i = 1, length( Phi ), Phi[i] = lift( Phi[i] ); Phi[i] = subst( Phi[i], variable( Phi[i] ), embed ); Phi[i] = Mod( Phi[i], bnfext.pol ); ); CokPhi = vector( length( Phi ), i, 0 ); for( i = 1, length( CokPhi ), CokPhi[i] = calcfactor( bnfext, UniformizerKp[i], Phi[i], ExpLW[i], WPStar0[i], WPStar1[i], WP[i] ); ); return( CokPhi ); } /* Berechnung der Darstellung von G aufdem Kokern( phi ) */ CompGRep( bnf, bnfext, iso, WP, CokPhi )= { local( i, len, DSF, DSCoker, DSRed ); len = length( WP ); /* Darstellung von iso auf der Gruppe uniformizer^Z + WPStar0 */ DSF = vector( len, i, 0 ); for( i = 1, len, DSF[i] = darstsigmafinite( bnfext, iso, UniformizerKp[i], WPStar0[i], WPStar1[i] ); ); result[23] = DSF; /* Darstellung von iso auf dem coker( phi ) */ DSCoker = vector( len, i, 0 ); for( i = 1, len, DSCoker[i] = CokPhi[i][1]*DSF[i]*CokPhi[i][1]^(-1); ); result[12] = DSCoker; /* Reduktion von Eintraegen in der Darstellung von iso auf dem Kokern mittels reduction( DSCoker[i], CokPhi[i][3] ) */ DSRed = vector( len, i, 0 ); for( i = 1, len, DSRed[i] = reduction( DSCoker[i], CokPhi[i][3] ); ); return( DSRed ); } /* Berechne Fittingideale non CokPhi */ CalcFittIdeals( CokPhi, GRep, l )= { local( i, Q, E, FittId ); Q = vector( length( GRep ), i, 0 ); for( i = 1, length( Q ), Q[i] = calcker( GRep[i], CokPhi[i][3], l ); print( " Nach calcker \n " ); ); E = bnfinit( ( x^l - 1 )/( x - 1 ) ); FittId = vector( length( Q ), i, 0 ); for( i = 1, length( FittId ), FittId[i] = calcfitt( E, Q[i] ); ); print(" FittId = ", FittId, " \n " ); /* Teste ob das Ergebnis ein ZG-Ideal ist */ for( i = 1, length( FittId ), if( !( iszgideal( FittId[i], l ) ), return( 0 ); ); ); return( FittId ); } CompIvL( bnf, bnfext, embed, FittId, Phi, wp, WP, l )= { local( i, j, tmp, place, e0, e1, gm1, lpdet, IvL, EpsLK, len ); len = length( FittId ); /* Darstellung von Elementen als Q-Tensoren */ for( place = 1, len, tmp = vector( l, i, 0 ); for( j = 1, matsize( FittId[place] )[2], tmp[j] = [ vector( matsize( FittId[place] )[1], i, FittId[place][i,j] ), 1 ]; ); FittId[place] = tmp; ); e0 = [ vector(l, i, 1), l]; e1 = [ vector(l, i, -1), l ]; e1[1][1] = l-1; gm1 = [ vector(l, i, 0), 1]; /* gm1 = g - 1 */ gm1[1][1] = -1; gm1[1][2] = 1; for( i = 1, len, Phi[i] = lift( Phi[i] ); Phi[i] = subst( Phi[i], variable( Phi[i] ), embed ); Phi[i] = Mod( Phi[i], bnfext.pol ); ); tmp = vector( len, i, idealval( bnfext, Phi[i], WP[i] ) ); /* Nach Konstruktion ist der Wert von Phi immer positiv */ lpdet = vector( len, i, Add( [e0[1]*tmp[i], e0[2]*l], GroupRingMult( e1, gm1 ) ) ); EpsLK = vector( len, i, Add( e1, [e0[1]*( 1 - idealnorm( bnf, wp[i] ) ), e0[2]*idealnorm( bnf, wp[i] )] ) ); IvL = vector( len, i, InvIdealScalarMult( EpsLK[i], InvIdealInv( FittId[i] ) ) ); IvL = vector( len, i, InvIdealScalarMult( lpdet[i], IvL[i] ) ); return( IvL ); } /* Berechnung von Det( L ) */ CompDetL( bnf, bnfext, embed, b, iso, L, l )= { local( i, j, k, d, v, lambda ); local( E, Subset, DetL, M, H, V ); V = matrix( 2*l, 2*l, i, j, 0 ); for( k = 1, 2, for( j = 1, l, v = nfalgtobasis( bnfext, nfgaloispowapply( bnfext, iso, j - 1, b[k] ) ); for( i = 1, 2*l, V[i,( k - 1 )*l + j] = v[i]; ); ); ); V = V^( -1 ) * L; lambda = vector( matsize( L )[2], i, [[vector( l, j, 0 ), 1], [vector( l, j, 0 ), 1]] ); for( j = 1, matsize( L )[2], d = 1; for( i = 1, l, d = lcm( d, denominator( V[i,j] ) ); lambda[j][1][1][i] = V[i, j]; ); lambda[j][1][1] = d*lambda[j][1][1]; lambda[j][1][2] = d; d = 1; for( i = 1, l, d = lcm(d, denominator( V[l + i,j] ) ); lambda[j][2][1][i] = V[l + i, j]; ); lambda[j][2][1] = d*lambda[j][2][1]; lambda[j][2][2] = d; ); Subset = InitSubset(2, length( lambda ) ); detL = []; E = bnfinit( ( x^l - 1 )/( x - 1 ) ); while( Subset, M = matrix( 2, 2, i, j, 0 ); for( i = 1, 2, for( j = 1, 2, M[i,j] = lambda[Subset[i]][j]; ); ); detL = concat( detL, [QGdet( M, E )] ); Subset = NextSubset( Subset, length( lambda ) ); ); d = 1; for( i = 1, length( detL ), d = lcm( d, detL[i][2] ); ); H = matrix( l, length( detL ), i, j, detL[j][1][i]*d / detL[j][2] ); H = mathnf( H ); detL = vector( matsize( H )[2], j, [vector( matsize( H )[1], i, H[i,j] ), d] ); return( detL ); } /* Hier wird schliesslich die Vermutung verifiziert */ VerifyConj( IvL, DetL, TauLKInv, NormRes )= { local( i, j, Z, A, s, InvId, prec, len ); Z = DetL; for( i = 1, length( IvL ), Z = InvIdealMult( Z, IvL[i] ); ); result[27] = Z; s = RGMult( xiLKInv, NormRes ); result[26] = s; InvId = InvIdealScalarMult( [s, 1], Z ); for( i = 1, length( InvId ), InvId[i] = InvId[i][1]/InvId[i][2]; ); result[28] = InvId; write( outfile, " s = ", s ); write( outfile, " InvId = ", InvId ); prec = precision( InvId ); len = length( InvId ); A = matrix( len, len, i, j, round( real( InvId[j][i] ) ) ); for( i = 1, len, for( j = 1, len, if( abs( A[i,j] - InvId[j][i] ) > 10^( -prec/2 ), print( " VerifyConj: A ist nicht ganz \n " ); write( outfile, " A ist nicht ganz " ); return( 0 ); ); ); ); if( mathnf( A ) == matid( matsize( A )[1] ), print( " VerifyConj: Die Vermutung ist bestaetigt \n " ); write( outfile, " VerifyConj: Die Vermutung ist bestaetigt " ), print( " A != ZG \n " ); write( outfile, " A != ZG " ); ); print( " A = ", A, " \n " ); print( " HNF( A ) = ", mathnf( A ), " \n " ); write( outfile, " A = ", A ); write( outfile, " HNF( A ) = ", mathnf( A ) ); return( mathnf( A ) ); } /* Berechne den Korrekturfaktor der unverzweigten Charakteristik */ UnramChar( bnf, id, l )= { local( i, j, e0, e1 ); i = matsize( idealfactor( bnf, id ) )[1]; e0 = vector( l, j, 1/l ); e1 = vector( l, j, ( j == 1 ) ) - e0; /* Das Element hat Ordnung 2 */ return( (-1)^i*e0 + e1 ); } /* Bestimmung der Factorgruppe ( coker( phi ) ). piext ist die Uniformisierende in bnfext. eps := phi(1). restLW berechnet mit expRestLW(). Liefert die Smithsche Normalform vom Quotienten ( piext^Z + IdStar0 / eps^Z + restLW ). IdStar0 bzw. IdStar1 sind mit der PARI-Funktion idealstar( , flag ) mit flag = 0 bzw. 1 berechnet und stellen die multip- likative Gruppe modulo einer Primidealpotenz P^m dar. ram ist der Verzweigungsindex von P ueber dem Grundkoerper. */ calcfactor( bnfext, piext, eps, subgrp, IdStar0, IdStar1, P /*, ram */)= { local( i, j, tmp, xi, ram ); local( U ); ram = idealval( bnfext, eps, P ); xi = eps/piext^ram; tmp = length( IdStar0[2] ); U = matrix( 1 + tmp, 1 + length( subgrp ) + tmp, i, j, 0 ); tmp = ideallog( bnfext, xi, IdStar1 ); /* Die erste Spalte von U korrespondiert zu piext-Komponente */ U[1,1] = ram; for( i = 2, matsize( U )[1], U[i,1] = tmp[i - 1] ); /* Die naechsten zu der subgrp */ for( j = 2, length( subgrp ) + 1, tmp = ideallog( bnfext, subgrp[j - 1], IdStar1 ); for( i = 2, matsize( U )[1], U[i,j] = tmp[i - 1]; ); ); /* Ergaenze mit Basiselementen hoch ihrer Ordnungen */ for( i = 1, length( IdStar0[2] ), U[1 + i, 1 + length( subgrp ) + i] = IdStar0[2][i]; ); U = mathnf( U ); result[29] = matsnf( U, 1 ); return( matsnf( U, 1 ) ); } /* Bestimmung der Galoisaktion von auf der Gruppe ( piext^Z + IdStar0 ). piext ist die Uniformisierende in bnfext. IdStar0 bzw. IdStar1 sind mit der PARI-Funktion idealstar( , flag ) mit flag = 0 bzw. 1 berechnet und stellen die multiplikative Gruppe modulo einer Primidealpotenz P^m dar. ram ist der Verzweigungsindex von P ueber dem Grundkoerper. */ darstsigmafinite( bnfext, iso, piext, IdStar0, IdStar1 )= { local( i, j, tmp, D ); tmp = 1 + length( IdStar0[2] ); D = matrix( tmp, tmp, i, j, 0 ); tmp = nfgaloisapply( bnfext, iso, piext )/piext; tmp = ideallog( bnfext, tmp, IdStar1 ); /* iso-Aktion auf der ersten Komponente */ D[1,1] = 1; for( i = 2, matsize( D )[1], D[i,1] = tmp[i-1] ); /* iso-Aktion auf IdStar0 */ for( j = 2, matsize( D )[2], tmp = nfbasistoalg( bnfext, IdStar0[3][j - 1] ); tmp = nfgaloisapply( bnfext, iso, tmp ); tmp = ideallog( bnfext, tmp, IdStar1 ); for( i = 2, matsize( D )[1], D[i, j] = tmp[i - 1]; ); ); return( D ); } /* Reduziere die Eintraege in D modulo der Diagonale in SNF ( zeilenweise ) */ reduction( D, SNF )= { local( i, j ); for( i = 1, matsize( D )[1], for( j = 1, matsize( D )[2], D[i,j] = D[i,j]%SNF[i,i]; ); ); return( D ); } /* Berechnung vom Kern( phi ). D ist die Darstellung von G auf dem Kookern( phi ). N die Matrix, die auf der Diagonale die Ord- nungen der nichttrivialen Erzeugenden vom Kokern( phi ) hat. ordG ist die Ordnung der Gruppe G. Ergebnis ist ein ZG-Modul. */ calcker( D, N, ordG )= { local( s, i, j, k, X, Q, M, tmp ); N = simpl( N, 1 ); tmp = matrix( matsize( N )[1], matsize( N )[2], i, j, D[i,j] ); D=tmp; s = matsize( N )[1]; /* Anzahl der Erzeugenden des Quotienten */ M = matid( s ); for( i = 1, ordG - 1, M = concat( M, D^i ); ); M = concat( M, N ); X = matkerint(M); Q = vector(matsize(X)[2], i, 0); for( j = 1, matsize( X )[2], Q[j] = vector(s, k, 0); for ( k = 1, s, Q[j][k] = vector( l, i, X[k + ( i - 1 )*s ,j] ); ); ); return( Q ); } /* Berechnung vom Fitting-Ideal von Q. E entspricht dem Koerper Q( zeta_|G| ). */ calcfitt( E, Q )= { local( s, i, j, Subset, Fitt, M, H ); s = length( Q[1] ); /* ZG-Rang von Q */ Subset = InitSubset( s, length( Q ) ); print( " Size(Q) = " s, " * ", length( Q ) ); Fitt = []; while( Subset, M = matrix( s, s, i, j, 0 ); for( i = 1, s, for( j = 1, s, M[i,j] = Q[Subset[i]][j]; ); ); Fitt = concat( Fitt, [ZGdet( M, E )] ); Subset = NextSubset( Subset, length( Q ) ); ); H = matrix( l, length( Fitt ), i, j, Fitt[j][i] ); /* Diese Ausgabe zeigt die Anzahl ( als Produkt der beiden Faktoren ) der ZG-Det-Berechnungen, die zum Berechnen des Fittingideals notwendig sind. */ print( " Size( H )= ", matsize( H )[1], " * ", matsize( H )[2], " \n " ); return( mathnf( H ) ); } /* Analysiere die reduzierte Matrix und werfe die ersten Zeilen und Spalten heraus, die die groessten Nummer haben und auf der Diagonale Eintrag = n haben. */ simpl( D, n )= { local( i, j, tmp, size ); size = matsize( D )[1]; if( size != matsize( D )[2], print( " In simpl ist keine quadratishce Matrix \n " ); return( 0 ); ); tmp = size; while( D[tmp,tmp] == n, tmp-- ); if( tmp == 0, print( " In simpl: Diagonale = 0 \n " ); return( [] ); ); return( matrix( tmp, tmp, i ,j, D[i, j] ) ); } /* elemvec ist gegeben bei konwertdown( ... ), stelle ist hier ein Primideal gegeben in bnf. Ergebnis: diejenigen elemvec[i]'s, deren jede Koordinate ( in bnf ) an der Primstelle stelle Werte >= 0 haben. */ CheckValue( bnf, elemvec, stelle ) = { local( i, j, flag, puffer, index ); puffer = List([]); index = List([]); /* merkt die Nummer des rausgeworfenes Elements */ for( i = 1, length( elemvec ), flag = 1; for( j = 1, length( elemvec[i] ), if( idealval( bnf, elemvec[i][j], stelle ) < 0, flag = 0; index = concat( index, List([i]) ); break; ); ); if( flag == 1, puffer = concat( puffer, List([elemvec[i]]) ); ); ); return( [puffer, index] ); } /* Bestimmung der Untergruppen im Strahl mit dem Index ordG */ findsubgroup( rcgp, ordG ) = { local( i, tmp, sgl ); tmp = subgrouplist( rcgp, ordG, 0 ); sgl = List( [] ); for( i = 1, length( tmp ), if( matdet( tmp[i] ) == ordG, sgl = concat( sgl, List( [ tmp[i] ] ) ); ); ); return( sgl ); } /* Bestimmung des richtigen Vertreters in der Strahklassengruppe */ findvertreter( rcgp, subgroup, ordG ) = { local( j ); j = 1; while( subgroup[j, j] != ordG, j = j + 1; ); return( rcgp.clgp[3][j] ); } /* Berechnung der Gausschen Summen, l ist eine ungerade Primzahl */ CompTauLK( bnf, subgrp, vertreter, rcgp, module, l )= { local( i, j, z, idem, char, tau, tauLK, tauLKInv ); /* Berechnung der Gauss'schen Summen */ char = vector( l - 1, i, 0 ); for( i = 1, length( char ), char[i] = findchar( subgrp, vertreter, rcgp, i, l ); ); print( " char = ", char, " \n " ); tau = vector( l, i, 0 ); tau[1] = sqrt( bnf.disc ); for( i = 2, length( tau ), tau[i] = sqrt( bnf.disc )*sqrt( idealnorm( bnf, module ) )*bnrrootnumber( rcgp, char[length( char ) - i + 2] ); ); idem = vector( l, i, 0 ); z = exp( 2*Pi*I / l ); for( i = 0, l - 1, idem[i + 1] = vector( l, j, z^( -i*( j - 1 ) ) / l ) ; ); tauLK = vector( l, i, 0 ); for( i = 1, l, tauLK += tau[i]*idem[i]; ); tauLKInv = vector( l, i, 0 ); for( i = 1, l, tauLKInv += tau[i]^(-1)*idem[i]; ); return( [tauLK, tauLKInv] ); } /* Berechne Darstellung von dem Charakter z -> z^j. z ist exp(2*Pi*I/l). rcgp ist die Strahlklassengruppe, vertreter korrespondiert zu dem Erzeugenden von ( rcgp/H ). l ( eine ungerade Primzahl ) ist die Ordnung der Faktorgruppe ( rcgp/H ). */ findchar( H, vertreter, rcgp, j, l )= { local( i, k, n, d, lstr, nstr ); local( len, upper, char, alpha ); G = rcgp[5][3]; n = rcgp[5][2]; len = length( G ); char = vector( len, i, 0 ); upper = matdet( H ) + 1; vertreter = bnrisprincipal( rcgp, vertreter )[1]; for( i = 1, len, tmp = bnrisprincipal( rcgp, G[i] )[1]; k = 0; while( !dtestin( H, k*vertreter - tmp ) && k < upper, k++; ); if( k >= upper, print( " In findchar: vertreter ist kein Erzeuger von der Faktorgruppe \n " ); return( 0 ); ); d = gcd( l, n[i] ); lstr = l/d; nstr = n[i]/d; alpha = j*k*nstr/lstr; if( denominator( alpha ) != 1, print( " In findchar: Der Charakter ist nicht ganz \n " ); return( 0 ), char[i] = lift( Mod( alpha, n[i] ) ); ); ); return( char ); } /* findisoquick ist eine Modifikation von findiso, module ist wie gen in findiso(), G ist zyklisch, ordG eine ungerade Primzahl */ findisoquick( bnf, bnfext, rnf, ordG, module, autbnfext, embed ) = { local( i, j, k, tmp, factorlist, puffer ); local( relnorm, q, Q, A, B, C, beta, Qlist ); factorlist = idealfactor( bnf, module ); puffer = vector( matsize( factorlist )[1], i, 0 ); for( k = 1, matsize( factorlist )[1], tmp = factorlist[k, 1]; relnorm = idealnorm( bnf, tmp ); q = factor( relnorm )[1, 1]; beta = nfbasistoalg(bnf, bnfisprincipal(bnf, tmp)[2]); beta = subst(lift(beta), y, x); beta = nfgaloisapply( bnfext, embed, beta ); Qlist = idealprimedec( bnfext, q ); i=1; while(idealval(bnfext, beta, Qlist[i]) == 0, i++); Q = idealhnf( bnfext, Qlist[i] ); i = 0; while( !( i == length(autbnfext) ), i = i + 1; j = 0; while( !( j == length( bnfext.zk ) ), j = j + 1; A = nfgaloisapply( bnfext, autbnfext[i], bnfext.zk[j] ); A = nfeltreduce( bnfext, A, Q ); A = nfbasistoalg( bnfext, A ); B = Mod( bnfext.zk[j], bnfext.pol ); B = power( bnfext, B, relnorm, Q ); C = nfeltreduce( bnfext, A - B, Q ); C = nfbasistoalg( bnfext, C ); if( !( C == 0 ), j = length( bnfext.zk ); ); ); if( C == 0, puffer[k] = Mod( autbnfext[i], bnfext.pol ); i = length(autbnfext); ); ); ); for( i = 1, length( puffer ), /* Berechne die Potenzen von Automorphismen */ upper = ( factorlist[i, 2]%ordG ); tmp = puffer[i]; puffer[i] = Mod( x, bnfext.pol ); for( j = 1, upper, puffer[i] = subst( lift( puffer[i] ), x, tmp ); ); ); tmp = puffer[1]; for( i = 2, length( puffer ), /* Berechne Produkt von Automorphismen */ tmp = subst( lift( tmp ), x, puffer[i] ); ); tmp = lift( tmp ); return(tmp); } /*END*/ /************************************************************************************/ /************************************************************************************/ /*FUNCTIONS RELATED TO THE GROUPALGEBRAS OVER THE NUMBER FIELDS WITH CYCLIC GROUP G */ /* THE ORDER OF G WILL BE AN ODD PRIME */ /************************************************************************************/ /************************************************************************************/ /* Gegeben eine Galoissche Erweiterung bnf/Q und eine zyklische Gruppe G = der Ordnung ordG. Ergebnis: Ein Vector von Listen in der jede Teilliste die Konjugationsklasse zu einem der irreduziblen bnf[G] Charaktere darstellt. Die Darstellung wie folgt: jede Teilliste enthaelt ganze Zahlen a[i], d.h. der zu a[i] gehoegige Charakter ist gegeben durch chi(g) = ( zeta_ordG )^( a[i] ). bnf.disc > 1 !!! */ findirrchar( bnf, ordG )= { local( bnfcycl, puffer, tmp, tmp1, group, char ); local( i, embed, embedcycl, comp, myconjvec ); tmp = factor( variable( bnf.pol )^ordG - 1 ); bnfcycl = bnfinit( tmp[matsize( tmp )[1], 1] ); comp = bnfinit( polcompositum( bnf.pol, bnfcycl.pol )[1] ); embedcycl = nfisincl( bnfcycl.pol, comp.pol )[1]; embed = nfisincl( bnf, comp )[1]; group = findgaloisgroup( bnf, comp, embed ); char = vector( ordG, i, i ); puffer = vector( length( char ), i, 0 ); for( i = 1, length( puffer ), puffer[i] = List([]); tmp = Mod( embedcycl, comp.pol ); tmp = tmp^char[i]; for( j = 1, length( group ), tmp1 = nfgaloisapply( comp, group[j], tmp ); tmp1 = embedinv( bnfcycl, comp, tmp1, embedcycl ); puffer[i] = concat( puffer[i], List( [tmp1] ) ); ); ); /* jede Komponente von puffer enthaelt die Bahn von einem der Charaktere der Gruppe G */ /* unter der Galoisgruppe( comp/bnf ). Die Werte sind gegeben als polmods in bnfcycl */ /* Mache alle Komponenten vom puffer zu den Vektoren, um die Kompatibilitaet mit Mengenfunktionen zu erreichen */ for( i = 1, length( puffer ), tmp = puffer[i]; puffer[i] = vector( length( tmp ), i, tmp[i] ); ); /* myconjvec ist eine Liste von Listen. Jede Teilliste enthaelt dann alle Konjugierten von einem Charakter */ myconjvec = List([]); tmp = length( puffer ); i = 1; while( tmp != 0, myconjvec = concat( myconjvec, List( [puffer[1]] ) ); puffer = minusconj( puffer, puffer[1] ); tmp = length( puffer ); i++; ); return( [myconjvec, bnfcycl, embedcycl, comp, embed] ); } /* menge enthaelt verschiedene Vektoren. Werfe raus alle Komponenten, die bis auf eine Permutation mit vec uebereinstimmen */ minusconj( menge, vec )= { local( i, j, puffer, tmp ); puffer = List([]); for( i = 1, length( menge ), if( isperm( menge[i], vec ), puffer = concat( puffer, List([menge[i]] ) ); ); ); /* Mache alle Komponenten vom puffer zu den Vektoren, um die Kompatibilitaet mit Mengenfunktionen zu erreichen */ tmp = puffer; puffer = vector( length( tmp ), i, tmp[i] ); return( complement( menge, puffer ) ); } /* Finde Idempotente von bnf[G], G zyklisch, ordG = |G| */ findidempotent( bnf, ordG )= { local( i, j, k, l, puffer, irrchar, tmp ); local( bnfcycl, embedcycl, comp, embed, tech ); tmp = findirrchar( bnf, ordG ); /* tech wird spaeter benoetigt fuer Wedderbuern-Zerlegung */ tech = [tmp[2], tmp[3], tmp[4], tmp[5]]; /*Rueckgabe: [myconjvec, bnfcycl, embedcycl, comp, embed] */ irrchar = tmp[1]; bnfcycl = tmp[2]; embedcycl = tmp[3]; comp = tmp[4]; embed = tmp[5]; /* Lese Charaktere in comp */ for( i = 1, length( irrchar ), for( j = 1, length( irrchar[i] ), tmp = lift( irrchar[i][j] ); tmp = subst( tmp, variable( bnfcycl.pol ), embedcycl ); tmp = Mod( tmp, comp.pol ); irrchar[i][j] = tmp; ); ); puffer = vector( length( irrchar ), i, 0 ); for( i = 1, length( puffer ), puffer[i] = [ vector( ordG, j, 0 ), ordG ]; for( k = 1, length( irrchar[i] ), if( lift( irrchar[i][1] ) != 1, /* der Charakter ist nichttrivial */ tmp = vector( length( puffer[i][1] ), l, 0 ); tmp[1] = Mod( 1, comp.pol ); for( l = 2, length( tmp ), tmp[l] = irrchar[i][k]^lift( Mod( -( l - 1 ), ordG ) ); ); puffer[i][1] += tmp, /* der Charakter ist trivial */ for( j = 1, length( puffer[i][1] ), puffer[i][1][j] = Mod( 1, comp.pol ); ); ); ); ); /* lese Idempotente in bnf */ for( i = 1, length( puffer ), for( j = 1, length( puffer[i][1] ), puffer[i][1][j] = embedinv( bnf, comp, puffer[i][1][j], embed ); ); ); /* tmp gibt den Charakter, tmp[i] korrespondiert zum i-ten Idempotenten ( Wedderburn ) */ tmp = vector( length( irrchar ), i, irrchar[i][1] ); return( [puffer, tmp, tech] ); } /* Berechne Wedderburn-Zelegung von lambda ( lambda ist ein Element in bnf[G], gegeben in unserer gewoenlichen Darstellung analog zum Fall Q[G] ). G ist zyklisch, ordG = |G|. tech ist geliefert von der Funktion findidempotent. */ nfwedderburn( bnf, lambda, ordG, tech )= { local( i, j, idemvec, tmp, wedcomp, akk ); local( bnfcycl, embedcycl, comp, embed, irrchar ); idemvec = tech[1]; irrchar = tech[2]; bnfcycl = tech[3][1]; embedcycl = tech[3][2]; comp = tech[3][3]; embed = tech[3][4]; wedcomp = vector( length( idemvec ), i, 0 ); for( i = 1, length( idemvec ), akk = 0; tmp = lambda; /* lese Komponenten von tmp in comp */ for( j = 1, length( tmp[1] ), tmp[1][j] = lift( tmp[1][j] ); tmp[1][j] = subst( tmp[1][j], variable( bnf.pol ), embed ); tmp[1][j] = Mod( tmp[1][j], comp.pol ); ); /* substituiere Gruppenelemente mit dem Charakterwert */ for( j = 1, length( tmp[1] ), akk += tmp[1][j]*( irrchar[i] )^( j - 1 ); ); akk /= tmp[2]; wedcomp[i] = akk; ); tmp = length( wedcomp ); wedcomp[tmp] = embedinv( bnf, comp, wedcomp[tmp], embed ); return( wedcomp ); } /* Inverse Funktion zu Wedderburn-Zerlegung der Algebra bnf[G]. wedcomp enthaelt Komponenten des Elements, das in bnf[G] wieder zu berechnen ist. Die Reihenfolge der Komponenten stimmt mit der bei der Berechnung von Idempotenten ueberein. tech ist geliefert von der Funktion findidempotent. */ nfwedderburninv( bnf, wedcomp, ordG, tech )= { local( i, j, k, x, lower, idemvec, irrchar, tmp, akk, tmpvec ); local( bnfcycl, embedcycl, comp, embed, basis, size ); idemvec = tech[1]; irrchar = tech[2]; bnfcycl = tech[3][1]; embedcycl = tech[3][2]; comp = tech[3][3]; embed = tech[3][4]; basis = vector( poldegree( comp.pol )/poldegree( bnf.pol ), i, 0 ); tmpvec = vector( length( wedcomp ), i, 0 ); for( i = 1, length( irrchar ) - 1, /* Die letzte Komponente gehoert zum trivialen Charakter */ tmpvec[i] = [vector( ordG, j, 0 ), 1]; for( j = 1, length( basis ), basis[j] = irrchar[i]^j; ); tmp = findbasiskoeff( bnf, comp, basis, embed, wedcomp[i] ); for( j = 1, length( tmp ), tmpvec[i][1][j + 1] = tmp[j]; ); ); tmpvec[length( irrchar )] = [vector( ordG, i, 0 ), ordG]; tmp = length( wedcomp ); if( wedcomp[tmp] != 0, for( i = 1, ordG, tmpvec[length( irrchar )][1][i] = wedcomp[tmp]; ); ); for( i = 1, length( tmpvec ), tmpvec[i] = GroupRingMult( tmpvec[i], idemvec[i] ); ); tmp = tmpvec[1]; for( i = 2, length( tmpvec ), tmp = Add( tmp, tmpvec[i] ); ); return( tmp ); } /* Invertiere ein Gruppenringelement. tech ist das Ergebnis von findidempotent. l ist die Ordnung von G ( eine ungerade Primzahl ) */ nfgroupringeltinv( bnf, lambda, l, tech )= { local( i, j, tmp ); tmp = nfwedderburn( bnf, lambda, l,tech ); for( i = 1, length( tmp ), if( tmp[i] != 0, tmp[i] = tmp[i]^( -1 ), print( " In nfgroupeltinv: lambda ist nicht invertierbar \n " ); return( 0 ); ); ); tmp = nfwedderburninv( bnf, tmp, l, tech ); return( tmp ); } /* lambda ist in der Algebra bnf[G]. Berechne Matrizendarstellung der Multiplikation mit lambda auf bnfext. BEMERKUNG: bnf[G] ist nach Voraussetzung ueber Ord(G) abelsch */ nfgroupringelttomat( bnf, bnfext, lambda, embed, DS )= { local( i, X, tmp ); X = mult_mit( bnfext, embed ); tmp = 0; for( j = 1, length( lambda[1] ), lambda[1][j] = lift( lambda[1][j] ); lambda[1][j] = subst( lambda[1][j], variable( bnf.pol ), X ); tmp += lambda[1][j]*DS^( j - 1 ); ); tmp /= lambda[2]; return( tmp ); } /*END*/ /************************************************************************************/ /************************************************************************************/ /* FUNCTIONS RELATED TO THE GROUPALGEBRA Q[G] WITH CYCLIC GROUP G */ /* THE ORDER OF G WILL BE AN ODD PRIME */ /************************************************************************************/ /************************************************************************************/ /* Teste ob M ein ZG-Ideal ist. M ist gegeben als eine Matrix mit Eintraegen in Z. G ist eine zyklische Gruppe von der Ordnung l ( eine ungerade Primzahl ) */ iszgideal( M, l )= { local( i, j, g, size, tmp ); M = mathnf( M ); size = matsize( M )[1]; if( size != l, print( " M ist kein ZG-Ideal \n " ); return( 0 ); ); tmp = [vector( size, i, 0 ), 1]; g = [ vector( size, i, 0 ), 1]; g[1][2] = 1; /* g repraesentiert den Erzeugenden von G */ for( i = 1, size, for( j = 1, size, tmp[1][j] = M[j, i]; ); tmp = GroupRingMult( tmp, g ); if( matsize( matinverseimage( M, mattranspose( tmp[1] ) ) )[1] == 0, print( " M ist kein ZG-Ideal \n " ); return( 0 ); ); ); print( " M ist ein ZG-Ideal \n " ); return( 1 ); } {VecGcd(v, n, d, i, j) = n = length(v); if ( n == 1, return(v[1]) ); d = v[1]; for (i=1, n, d = gcd(d, v[i])); return(d); } {IntegralGroupRingMult(a, b, c, i, j, l) = l = length(a); c = vector(l, i, 0); for (i=0, l-1, for (j=0, l-1, c[i+1] = c[i+1] + a[j+1]*b[(i-j)%l + 1]; ); ); return(c); } {RGMult(a, b, c, i, j, l) = l = length(a); c = vector(l, i, 0); for (i=0, l-1, for (j=0, l-1, c[i+1] = c[i+1] + a[j+1]*b[(i-j)%l + 1]; ); ); return(c); } {GroupRingMult(a, b, c, d, i, j, l) = l = length(a[1]); c = [0, 0]; c[1] = IntegralGroupRingMult(a[1], b[1]); c[2] = a[2] * b[2]; d = gcd(c[2], VecGcd(c[1])); for (i=1, l, c[1][i] = c[1][i] / d); c[2] = c[2] / d; return(c); } {IntegralGroupRingAction(a, t, y, i, l) = l = length(a); y = 1; /*y = prod(i=0, l-1, Sigmapow(t, Kp.pol, iso, i)^(a[i+1]));*/ /* Neue Zeile */ y = prod(i=0, l-1, nfgaloispowapply( Kp, iso, i, t )^(a[i+1])); return(y); } {GroupRingAction(a, t, b) = b = [IntegralGroupRingAction(a[1], t[1]), a[2]*t[2]]; return(b); } {Add(a, b, c, k, d, i, j) = c = [0, 0]; k = lcm(a[2], b[2]); if (type(a[1]) == "t_VEC", c[1] = k/a[2] * a[1] + k/b[2] * b[1]; c[2] = k; d = gcd(c[2], VecGcd(c[1])); for (i=1, length(a[1]), c[1][i] = c[1][i] / d); c[2] = c[2] / d; return(c); , c[1] = a[1]^(k/a[2]) * b[1]^(k/b[2]); c[2] = k; ); return(c); } {IntWedderburn(lambda, E, s1, s2, i) = s1 = sum(i=1, length(lambda), lambda[i]); s2 = sum(i=1, length(lambda), lambda[i] * Mod(variable(E.pol), E.pol)^(i-1)); return( [s1, s2] ); } {Wedderburn(lambda, E, s1, s2, i) = s1 = sum(i=1, length(lambda[1]), lambda[1][i]); s1 = s1 / lambda[2]; s2 = sum(i=1, length(lambda[1]), lambda[1][i] * Mod(variable(E.pol), E.pol)^(i-1)); s2 = s2 / lambda[2]; return( [s1, s2] ); } {IntWedderburnInv(v, E, l, e0, e1, a, b, w) = l = poldegree(E.pol)+1; e0 = [ vector(l, i, 1), l]; e1 = [ vector(l, i, -1), l ]; e1[1][1] = l-1; a = [vector(l, i, 0), 1]; a[1][1] = v[1]; b = [concat(nfalgtobasis(E, v[2])~, [0]), 1]; w = Add( GroupRingMult(a, e0), GroupRingMult(b, e1)); return(w[1]); } {WedderburnInv(v, E, d, l, e0, e1, a, b, w) = l = poldegree(E.pol)+1; e0 = [ vector(l, i, 1), l]; e1 = [ vector(l, i, -1), l ]; e1[1][1] = l-1; a = [vector(l, i, 0), denominator(v[1])]; a[1][1] = numerator(v[1]); d = 1; w = nfalgtobasis(E, v[2])~; for (i=1, length(w), d = lcm(d, denominator(w[i]))); b = [concat(w*d, [0]), d]; w = Add( GroupRingMult(a, e0), GroupRingMult(b, e1)); return(w); } {ZGdet(A, E, A1, A2, i, j, q, x) = A1 = matrix(matsize(A)[1], matsize(A)[2], i, j, 0); A2 = matrix(matsize(A)[1], matsize(A)[2], i, j, 0); for (i=1, matsize(A)[1], for (j=1, matsize(A)[2], q = IntWedderburn(A[i,j], E); A1[i,j] = q[1]; A2[i,j] = q[2]; ); ); x = [matdet(A1), matdet(A2)]; return (IntWedderburnInv(x, E)); } {QGdet(A, E, A1, A2, i, j, q, x) = A1 = matrix(matsize(A)[1], matsize(A)[2], i, j, 0); A2 = matrix(matsize(A)[1], matsize(A)[2], i, j, 0); for (i=1, matsize(A)[1], for (j=1, matsize(A)[2], q = Wedderburn(A[i,j], E); A1[i,j] = q[1]; A2[i,j] = q[2]; ); ); x = [matdet(A1), matdet(A2)]; return (WedderburnInv(x, E)); } {InvIdealMult(X, Y, l, denom, d, i, j, p, XY, M H, res, c) = XY = []; l = length(X[1][1]); denom = 1; for (i=1, length(X), for (j=1, length(Y), p = GroupRingMult(X[i], Y[j]); denom = gcd(d, p[2]); XY = concat(XY, [p]); ); ); M = matrix(length(X[1][1]), length(XY), i, j, XY[j][1][i] * denom/XY[j][2]); H = mathnf(M); res = vector(length(X), i, 0); for (j=1, length(X), c = [ vector(matsize(H)[2], i, H[i, j]), denom]; d = gcd(c[2], VecGcd(c[1])); for (i=1, l, c[1][i] = c[1][i] / d); c[2] = c[2] / d; res[j] = c; ); return(res); } {InvIdealScalarMult(s, X, i, Y) = Y = vector(length(X), i, GroupRingMult(s, X[i])); return(Y); } {InvIdealInv(X, l, M, i, j, t, Y, s, d) = l = length(X); M = matrix(l,l,i,j,0); /* Fehler: es muss heissen X[i][2]. Dies spielt bislang jedoch keine Rolle, da InvIdealInv nur fuer ZG-Ideale benutzt wurde, d.h. alle X[i][2] = 1 */ for (i=1, l, for (t=1, l, M[i, t] = X[i][1][(1-t)%l + 1] / X[1][2]); ); M = M^(-1); Y = vector(length(X), i, [vector(l,j,0) ,1]); for (s=1, l, d = 1; for (i=1, l, d = lcm(d, denominator(M[i,s])); Y[s][1][i] = M[i,s]; ); Y[s][1] = Y[s][1] * d; Y[s][2] = d; ); return(Y); } {Resolvent(Kp, b, embed, iso, l, res, i, a) = res = vector(l, i, 0); for (i=0, l-1, a = nfgaloispowapply( Kp, iso, i, b ); a = subst(lift(a), variable(a), embed); res[(-i%l)+1] = a; ); return(res); } {NormResolvent(Kp, b, alpha, iso, l, i, j) = M = matrix(2,2, i, j, Resolvent(Kp, b[i], alpha[j], iso, l)); return( RGMult(M[1,1], M[2,2]) - RGMult(M[2,1], M[1,2]) ); } /*END*/ /************************************************************************************/ /************************************************************************************/ /* FUNCTIONS RELATED TO THE EXTENSIONS OF NUMBER FIELDS */ /************************************************************************************/ /************************************************************************************/ /* Berechne die Galoisgruppe Gal( bnfext/bnf ), bnfext ist Galoissch ueber Q. embed ist eine Einbettung bnf -> bnfext. */ findgaloisgroup( bnf, bnfext, embed )= { local( i, puffer, tmp, group ); group = nfgaloisconj( bnfext.pol ); puffer = List([]); for( i = 1, length( group ), if( Mod( embed, bnfext.pol ) == Mod( subst( embed, variable( embed ), group[i] ), bnfext.pol ), puffer = concat( puffer, List([ group[i] ]) ); ); ); return( puffer ); } /* embed ist eine Einbettung bnf -> bnfext. alpha ein Element von bnfext im Bild( embed ). Finde das Urbild von alpha in bnf. */ embedinv( bnf, bnfext, alpha, embed )= { local( uralpha, Embed ); Embed = embedlinear( bnf, bnfext, embed ); alpha = nfalgtobasis( bnfext, alpha ); uralpha = matinverseimage( Embed, alpha ); return( nfbasistoalg( bnf, uralpha ) ); } /* embed ist eine Einbettung bnf -> bnfext. Finde die zu embed gehoerige lineare Abbildung bnf.zk -> bnfext.zk */ embedlinear( bnf, bnfext, embed )= { local( i, j, tmp, E ); E = matrix( length( bnfext.zk ), length( bnf.zk ), i, j, 0 ); for( i = 1, length( bnf.zk ), tmp = subst( bnf.zk[i], variable( bnf.pol ), embed ); tmp = nfalgtobasis( bnfext, tmp ); for( j = 1, length( tmp ), E[j, i] = tmp[j]; ); ); return( E ); } /* primvec ist ein Vektor der Primideale in bnf gegeben als primedec. Berechne einen Vektor der Uniformisierenden respektive der Reihenfolge. */ FindUniformizer( bnf, primvec )= { local( i, tmp, puffer ); puffer = vector( length( primvec ), i, 0 ); for( i = 1, length( primvec ), if( bnf.clgp[1] == 1, tmp = bnfisprincipal( bnf, primvec[i] )[2], tmp = idealtwoelt( bnf, primvec[i] )[2]; ); puffer[i] = nfbasistoalg( bnf, tmp ); ); return( puffer ); } /* fuehrer ist der Fuehrer von bnfext/bnf. Finde die wildverzweigten Stellen in bnfext. embed ist eine festgewaehlte Einbettung bnf -> bnfext. Bestimme die wildverzweigten Stellen der Erweiterung bnfext/bnf. */ findwildplace( bnf, bnfext, embed, fuehrer )= { local( i, j, id, ID, tmp, puffer ); puffer = List([]); fuehrer = idealfactor( bnf, fuehrer ); for( i = 1, matsize( fuehrer )[1], id = fuehrer[i, 1]; ID = ideallift( bnf, bnfext, embed, id ); ID = idealfactor( bnfext, ID ); for( j = 1, matsize( ID )[1], tmp = ID[j, 1][3]/id[3]; if( !( tmp%ID[j, 1][1] ), puffer = concat( puffer, List( [ID[j, 1]] ) ); ); ); ); return( puffer ); } /* Teste locale Gleichheit von zwei Gittern M und N in bnfext bis auf Primstellen von bnf ( gegeben in pvec in beliebiger Form ). embed ist eine festgewaehlte Einbettung ( bnf -> bnfext ). M und N gegeben in Hermiteschen Normalform ueber Z */ testloceq( bnf, bnfext, embed, M, N, pvec )= { local( i, j, PM, IV, MNF, NNF, indM, indN, reldeg ); local( tmp, myexp, basis ); M = matrixtoset( bnfext, M ); N = matrixtoset( bnfext, N ); reldeg = poldegree( bnfext.pol )/poldegree( bnf.pol ); /* Stelle M und N ueber O(bnf) dar */ basis = vector( reldeg, i, variable( Kp.pol )^( i - 1 ) ); for( i = 1, length( M ), M[i] = findbasisrepr( bnf, bnfext, basis, embed, M[i] ) ); for( i = 1, length( N ), N[i] = findbasisrepr( bnf, bnfext, basis, embed, N[i] ) ); /* Berechne Hermitesche Normalform von M ueber bnf */ PM = matrix( reldeg, length( M ), i, j, 0 ); IV = vector( length( M ), i, 1 ); /* 1 entspricht dem Ideal O(bnf)*/ for( i = 1, length( M ), for( j = 1, matsize( PM )[1], PM[j,i] = nfalgtobasis( bnf, polcoeff( M[i], j - 1 ) ); ); ); MNF = nfhnf( bnf, [PM, IV ] ); for( i = 1, matsize( MNF[1] )[1], for( j = 1, matsize( MNF[1] )[2], MNF[1][i,j] = nfbasistoalg( bnf, MNF[1][i,j] ); ); ); /* Berechne Discriminante von M ueber bnf */ indM = matdet( MNF[1] ); for( i = 1, length( MNF[2] ), indM = idealmul( bnf, indM, MNF[2][i] ) ); /* Berechne Hermitesche Normalform von N ueber bnf */ PM = matrix( reldeg, length( N ), i, j, 0 ); IV = vector( length( N ), i, 1 ); /* 1 entspricht dem Ideal O(bnf)*/ for( i = 1, length( N ), for( j = 1, matsize( PM )[1], PM[j,i] = nfalgtobasis( bnf, polcoeff( N[i], j - 1 ) ); ); ); NNF = nfhnf( bnf, [PM, IV ] ); for( i = 1, matsize( NNF[1] )[1], for( j = 1, matsize( NNF[1] )[2], NNF[1][i,j] = nfbasistoalg( bnf, NNF[1][i,j] ); ); ); /* Berechne Discriminante von M ueber bnf */ indN = matdet( NNF[1] ); for( i = 1, length( NNF[2] ), indN = idealmul( bnf, indN, NNF[2][i] ) ); tmp = idealmul( bnf, indM, idealinv( bnf, indN ) ); for( i = 1, length( pvec ), myexp = idealval( bnf, tmp, pvec[i] ); tmp = idealmul( bnf, tmp, idealpow( bnf, pvec[i], -myexp ) ); ); if( matsize( idealfactor( bnf, tmp ) )[1] != 0, /* Es kommt irgendein Primteiler vor */ print( " In testloqeq sind Gittern nicht local gleich \n " ); return( 0 ), print( " In testloqeq sind Gittern local gleich \n " ); return( 1 ); ); } /* lifte das Ideal id ( gegeben in idealhnf oder als idealprimedec ) von bnf in bnfext mit der Einbettung bnf -> bnfext. Ergebnis: HNF des gelifteten Ideals id*O(bnfext) */ ideallift( bnf, bnfext, embed, id )= { local( i, j, elemvec, liftid ); id = idealtwoelt( bnf, id ); elemvec = vector( 2, i, nfbasistoalg( bnf, id[i] ) ); for( i = 1, 2, elemvec[i] = lift( elemvec[i] ); elemvec[i] = subst( elemvec[i], variable( elemvec[i] ), embed ); elemvec[i] = Mod( elemvec[i], bnfext.pol ); elemvec[i] = mult_mit( bnfext, elemvec[i] ); ); liftid = concat( elemvec[1], elemvec[2] ); return( idealhnf( bnfext, liftid ) ); } /* embed: bnf -> bnfext=Q(x). Finde Min.Pol.(x) ueber bnf respektive embed */ findreleq( bnf, bnfext, embed )= { local( i, deg, tmp, var, basis, koeff ); var = variable( bnfext.pol ); deg = poldegree( bnfext.pol )/poldegree( bnf.pol ); basis = vector( deg, i, var^( i - 1 ) ); koeff = findbasiskoeff( bnf, bnfext, basis, embed, var^deg ); tmp = Mod( 1, bnf.pol )*var^deg; for( i = 1, length( basis ), tmp -= koeff[i]*var^( i - 1 ); ); return( tmp ); } /* Berechnet O(bnf)[G]-Aufspann von alpha. Galoisgruppe G ersetzt hier durch die Darstellung des Erzeugenden DS, berechnet bei darstaddsigma( bnfext, iso ), alpha ist polmod. Ergebnis: [Matrix A, Liste von Spalten von A]. ACHTUNG: G muss zyklisch sein. */ galoissubspandar( bnf, bnfext, embed, alpha, DS ) = { local( i, j, k, size, len ); local( A, L, tmp, galtmp, bnfbasis ); local( ordDS, tmpDS ); size = length( bnfext.zk ); A = matrix( size, size, i, j, 0 ); L = List([]); bnfbasis = bnf.zk; ordDS = 1; /* Berechnung der Ordnung von DS: Hier wird G zyklisch benoetigt */ tmpDS = DS; while( tmpDS != matid( size ), tmpDS = tmpDS*DS; ordDS++; ); for( i = 1, len = length( bnfbasis ), bnfbasis[i] = Mod( subst( bnfbasis[i], variable( bnf.pol ), embed ), bnfext.pol ); ); i = 1; k = 1; while( i <= len, galtmp = Mod( alpha*bnfbasis[i], bnfext.pol ); /* Multipliziere schon hier */ galtmp = nfalgtobasis( bnfext, galtmp ); /* denn DS lasst bnf fix */ for( f = 1, ordDS, galtmp = DS*galtmp; L = concat( L, List([galtmp]) ); for( j = 1, size, A[j,k] = galtmp[j]; ); k++; ); i++; ); return( [A, L] ); } /* basis ist irgendeine eine bnf-Basis von bnfext. Berechne bnf-Koeffizienten in der Darstellung von alpha bzgl. der basis. embed ist eine feste Einbettung bnf -> bnfext. Alle Elemente gegeben als Polmods. Ergebnis: Elemente in bnf. */ findbasiskoeff( bnf, bnfext, basis, embed, alpha )= { local( i, j, puffer, tmp, bnfbasis, span ); puffer = vector( length( basis ), i, 0 ); alpha = nfalgtobasis( bnfext, alpha ); /* lese bnf in bnfext */ bnfbasis = vector( length( bnf.zk ), i, 0 ); for( i = 1, length( bnf.zk ), bnfbasis[i] = Mod( subst( bnf.zk[i], variable( bnf.pol ), embed ), bnfext.pol ); ); /* Aufspann vom i-ten basis-Element ueber bnf in der Matrizendarstellung */ tmp = vector( length( bnf.zk ), j, bnfbasis[j]*basis[1] ); span = settomatrix( bnfext, tmp ); for( i = 2, length( basis ), tmp = vector( length( bnf.zk ), j, bnfbasis[j]*basis[i] ); span = concat( span, settomatrix( bnfext, tmp ) ); ); alpha = matinverseimage( span, alpha ); lower = 0; for( i = 1, length( alpha )/length( bnf.zk ), tmp = vecextract( alpha, sum( x = lower, i*length( bnf.zk ) - 1, 2^x ) ); puffer[i] = 0; for( j = 1, length( tmp ), puffer[i] += tmp[j]*bnf.zk[j]; ); puffer[i] = Mod( puffer[i], bnf.pol ); lower = i*length( bnf.zk ); ); return( puffer ); } /* Findet die alpha darstellende Linearkombination ueber bnf auf der basis */ findbasisrepr( bnf, bnfext, basis, embed, alpha )= { local( i, tmp, koeff ); tmp = 0; koeff = findbasiskoeff( bnf, bnfext, basis, embed, alpha ); tmp = sum( i = 1, length( koeff ), koeff[i]*basis[i] ); return( tmp ); } /* koeff kann Vector in bnf aber auch in bnfext sein, flag = 1 bedeutet, dass koeff elemnte aus bnf enthaelt, flag = 0: aus bnfext. */ basiskoefftoelt( bnf, bnfext, basis, koeff, embed, flag )= { local( i, tmp ); if( flag == 1, for( i = 1, length( koeff ), koeff[i] = subst( koeff[i], variable( koeff[i] ), embed ); ); ); tmp = 0; for( i = 1, length( basis ), tmp += basis[i]*koeff[i]; ); return( tmp ); } /* Darstellung des Vektors von polmods in der HNF ueber Z */ settomatrix( bnf, polvec ) = { local( i, j, dim, M, tmp ); dim = poldegree( bnf.pol ); M = matrix( dim, length( polvec ), i, j, 0 ); for( j = 1, length( polvec ), tmp = nfalgtobasis( bnf, polvec[j] ); for( i = 1, dim, M[i,j] = tmp[i]; ); ); return( M ); } /* Spalten der Matrix repraesentieren Z-Koordinaten, konvertiere Matrix in ein Vektor von polmods */ matrixtoset( bnf, M ) = { local( i, j, puffer, tmp ); puffer = vector( matsize( M )[2], i, 0 ); tmp = vector( matsize( M )[1], i, 0 )~; for( j = 1, matsize( M )[2], for( i = 1, matsize( M )[1], tmp[i] = M[i,j]; ); puffer[j] = nfbasistoalg( bnf, tmp ); ); return( puffer ); } /* Berechnung der Dualbasis ( bzgl. Spur ) zu basis in bnf. basis ist ein Vektor von polmods */ dualgitter( bnf, basis ) = { local( i, j, k, size, E, Tr, BVec, DVec, tmp ); size = length( basis ); DVec = vector( size, i, 0 ); Tr = matrix( size, size, i, j, 0 ); E = vector( size, i, matrix( size, size, j, k, 0 ) ); for( i = 1, size, E[i] = mult_mit( bnf, basis[i] ); ); for( i = 1, size, for( j = 1, i, Tr[i,j] = trace( E[i]*E[j] ); if( i != j, Tr[j,i] = Tr[i,j]; ); ); ); Tr = Tr^(-1); for( i = 1, size, tmpVec = mattranspose( vector( size, j, 0 ) ); tmpVec[i] = 1; tmpVec = Tr*tmpVec; for( j = 1, size, DVec[i] = DVec[i] + tmpVec[j]*basis[j]; ); ); return( DVec ); } /* Berechnung des Schnittes M mit N ( beide sind Z-Gitter in bnf ), gitterintersect( M, N ) = dual( dual(M) + dual(N) ), wobei dual ausgerechnet bzgl der Spur. M und N gegeben als Vektoren von Polmods. */ gitterintersect( bnf, M, N )= { local( d1, d2, tmp, den ); M = dualgitter( bnf, M ); N = dualgitter( bnf, N ); M = settomatrix( bnf, M ); N = settomatrix( bnf, N ); /* ACHTUNG: ist abgeaendert, denn hat Probleme mit HNF-Ausrechnen */ tmp = concat( M, N ); den = denominator( tmp ); tmp = mathnf( den*tmp, 1 )[1]; tmp /= den; tmp = matrixtoset( bnf, tmp ); tmp = dualgitter( bnf, tmp ); return( tmp ); } /* Darstellung von u -> iso(u) auf der bnf.zk, iso ist dabei ein Automorphismus von bnf, u ein ganzalgebraisches Element. */ darstaddsigma( bnf, iso ) = { local( i, j, A, tmp, size ); size = length( bnf.zk ); A = matrix( size, size, i, j, 0 ); for( i = 1, size, tmp = nfgaloisapply( bnf, iso, bnf.zk[i] ); tmp = nfalgtobasis( bnf, tmp ); for( j = 1, length( tmp ), A[j, i] = tmp[j]; ); ); return( A ); } FindEmbedGalCond( K, Kp, module, subgrp ) = { local( i, embeds, polrel, puffer, faktor, tmp ); /* Finde die Einbettungen K -> Kp, wobei Kp zu der subgrp (!!!) korrespondiert*/ /* In Wahrheit muss man 1) Kp.pol faktorisieren 2) feststellen, welcher Faktor F zu der subgrp gehoert ( mit Hilfe von abspol unten ) 3) Die Einbettung als die Nullstelle des F waehlen */ tmp = factornf( Kp.pol, K.pol ); faktor = vector( matsize( tmp )[1], i, tmp[i,1] ); for( i = 1, length( faktor ), tmp = rnfconductor( K, faktor[i] ); /* Die Untergruppe von rcgp */ if( tmp[3] == subgrp && tmp[1][1] == module, polrel = faktor[i]; break; ); ); polrel = lift( polrel ); puffer = List([]); embeds = nfisincl( K.pol, Kp.pol ); for( i = 1, length( embeds ), tmp = subst( polrel, variable( K.pol ), embeds[i] ); if( Mod( tmp, Kp.pol ) == 0, puffer = concat( puffer, List( [embeds[i]] ) ); ); ); print( " Geeignete Einbettungen: ", puffer, " \n " ); return( puffer[1] ); } nfgaloispowapply( bnf, iso, pow, x )= { local( i ); for( i = 1, pow, x = nfgaloisapply( bnf, iso, x ); ); return( x ); } /* ( x -> alpha*x ) bzgl. der Ganzheitsbasis beschreibende Matrix, alpha ist durch polmod gegeben */ mult_mit( bnf, alpha ) = { local( M, i, j, n, tmp, intbasis ); intbasis = bnf.zk; M = matrix( n = poldegree( bnf.pol ), n, i, j ); for( i = 1, n, tmp = nfalgtobasis( bnf, alpha*intbasis[i] ); for( j = 1, n, M[j, i] = tmp[j]; ); ); return( M ); } /* Potenzen einer Zahl modulo Ideal */ power( bnf, alpha, n, module ) = { local( pow, len ); module = idealhnf( bnf, module ); if( n == 0, return ( 1 ); ); pow = alpha; len = length( binary( n ) ) - 1; while( !( len == 0 ), len = len - 1; pow = pow*pow; /*pow = rest_mod( bnf, pow, module );*/ /* Neue Zeile */ pow = nfeltreduce( bnf, pow, module ); pow = nfbasistoalg( bnf, pow ); if( bittest( n, len ), pow = pow*alpha; /*pow = rest_mod( bnf, pow, module );*/ /* Neue Zeile */ pow = nfeltreduce( bnf, pow, module ); pow = nfbasistoalg( bnf, pow ); ); ); return( pow ); } /* Auswahl der unedlichen Stellen. "kandidat" nicht in der Bahn von "alpha" */ findplace( bnf, ordG, aut ) = { local( flag, tolerance, bahn, tmp, alpha, kandidat, i, j ); bahn = List( [] ); tolerance = 0.001; for ( i = 1, ordG, tmp = conjvec( nfgaloispowapply( bnf, aut, i, x ) ); bahn = concat( bahn, List( [ tmp[1] ] ) ); ); alpha = tmp[1]; for ( i = 1, length( tmp ), kandidat = tmp[i]; j = 1; flag = 0; while( j <= length( bahn ), if( abs( kandidat - bahn[j] ) < tolerance, flag = 1; ); j = j + 1; ); if( flag == 0, return( [alpha, kandidat] ); ); ); } /*END*/ /************************************************************************************/ /************************************************************************************/ /* FUNCTIONS RELATED TO THE GALOIS (G-)MODULE STRUCTURE */ /* THE ORDER OF G WILL BE AN ODD PRIME */ /************************************************************************************/ /************************************************************************************/ /* Teste ob Gitter M projektiv ist. DS ist die Darstellung des Erzeugenden von Galoisgruppe G. M gegeben als ganzzahlige Matrix vom vollen Rang oder als Vektor bzw. Liste von Spalten von M. */ isprojectiv( M, DS ) = { local( i, Mfix, NormM, kerTrM, deltaGM, mattmp ); local( tmp, Tr ); if( type( M ) == "t_LIST" || type( M ) == "t_VEC", mattmp = matrix( length( M[1] ), length( M ), i, j, 0 ); for( i = 1, length( M ), for( j = 1, length( M[1] ), mattmp[j, i] = M[i][j]; ); ); M = mattmp; ); if( matdet( M ) == 0, print( " In isprojectiv nicht vollrangige Matrix \n " ); return( 0 ); ); tmp = vector( matsize( M )[1], i, 0 ); Tr = dartrace( DS ); Mfix = matkerint( ( DS - matid( matsize( DS )[1] ) )*M ); Mfix = M*Mfix; NormM = Tr*M; kerTrM = matkerint( Tr*M ); kerTrM = M*kerTrM; deltaGM = ( DS - matid( matsize( DS )[1] ) )*M; Mfix = mathnf( Mfix, 1 )[1]; NormM = mathnf( NormM, 1 )[1]; kerTrM = mathnf( kerTrM, 1 )[1]; deltaGM = mathnf( deltaGM, 1 )[1]; tmp = ( Mfix == NormM ) && ( kerTrM == deltaGM ); if( tmp, print( " In isprojectiv: Gitter ist projektiv \n " ), print( " In isprojectiv: Gitter ist nicht projektiv \n " ); ); return( tmp ); } /* Berechnung der Ordnung einer Darstellung ( invertierbare Matrix ueber Z ), Ordnung klein */ ordsigma( DS ) = { local( ordDS, tmpDS, size ); if( matdet( DS ) != 1, print( " In ordsigma keine in Z invertierbare Matrix \n " ); return( 0 ); ); ordDS = 1; /* Berechnung der Ordnung von DS */ tmpDS = DS; while( tmpDS != matid( matsize( DS )[1] ) && ordDS < 100, tmpDS = tmpDS*DS; ordDS++; ); return( ordDS ); } /* Berechnung der HNF von Trace ( G^hat ). DS ist Darstellung des Erzeugenden von Galoisgruppe */ dartrace( DS ) = { local( i, ordDS, tmpDS, tmpTr ); ordDS = 1; /* Berechnung der Ordnung von DS */ tmpDS = DS; tmpTr = DS; while( tmpDS != matid( matsize( DS )[1] ), tmpDS = tmpDS*DS; tmpTr = tmpTr + tmpDS; ordDS++; ); return( tmpTr ); } /* Bestimmung von dem "Normalbasisrzeugenden" ( im Sinne der Indexminimalitaet ) von gitter^M ueber M, wobei M = Maximalordnung in bnf[G], G = , |G| = l, embed eine festgewaehlte Einbettung bnf -> bnfext, DS = Darstellung von G auf O(bnfext). */ FindBestNB( bnf, bnfext, gitter, embed, DS, l )= { local( lambda, idemvec, tech ); local( OM, Vau, IdealComp, ElemComp ); tech = findidempotent( bnf, l ); idemvec = tech[1]; if( !( bnf.disc%3 ) && ( l == 3 ), OM = findmaxordmodulunram( bnf, bnfext, gitter, embed, idemvec, DS, l, tech ), OM = findmaxordmodul( bnf, bnfext, gitter, embed, idemvec, DS, l, tech ); ); Vau = findnbe( bnf, bnfext, embed, OM, idemvec, DS ); IdealComp = findidealcomp( bnf, bnfext, tech, embed, Vau, OM, DS, l ); ElemComp = findprincideal( bnf, bnfext, tech, embed, IdealComp ); lambda = nfwedderburninv( bnf, ElemComp, l, tech ); lambda = nfgroupringelttomat( bnf, bnfext, lambda, embed, DS ); Vau = lambda*Vau; return( nfbasistoalg( bnfext, Vau ) ); } /* finde einen Normalbasiserzeuger in OM. idemvec ist der Vector mit Idempotenten des Gruppenringes bnf[G] */ findnbe( bnf, bnfext, embed, OM, idemvec, DS )= { local( i, j, len, idemvecmat, OMComp, Vau ); len = length( idemvec ); idemvecmat = vector( len, i, 0 ); OMComp = vector( len, i, 0 ); Vau = mattranspose( vector( matsize( OM )[1], i, 0 ) ); for( i = 1, len, idemvecmat[i] = nfgroupringelttomat( bnf, bnfext, idemvec[i], embed, DS ); OMComp[i] = mathnf( idemvecmat[i]*OM ); ); for( i = 1, length( Vau ), for( j = 1, length( OMComp ), Vau[i] += OMComp[j][i, 1]; ); ); return( Vau ); } /* Berechnet Index [ OM : O(bnf)[G]*Vau ] als Ideal in der Komponente KComp[compno] */ findidealcomp( bnf, bnfext, tech, embed, Vau, OM, DS, l )= { local( i, j, tmp, GRK, Basis, IdealComp ); Basis = vector( l, i, nfbasistoalg( bnfext, DS^(i - 1)*Vau ) ); GRK = vector( matsize( OM )[1], i, 0 ); IdealComp = vector( length( tech[1] ), i, 0 ); OM = matrixtoset( bnfext, OM ); for( i = 1, length( GRK ), /* Elemente in bnf[G], mit Nenner */ GRK[i] = [findbasiskoeff( bnf, bnfext, Basis, embed, OM[i] ), 1]; ); for( i = 1, length( IdealComp ), IdealComp[i] = vector( length( GRK ), j, 0 ); ); for( i = 1, length( GRK ), tmp = nfwedderburn( bnf, GRK[i], l, tech ); for( j = 1, length( tmp ), IdealComp[j][i] = tmp[j]; ); ); /* Uebersetze Idealcomponenten in die hnf in zugehoerigen Komponenten */ tmp = length( IdealComp ); for( i = 1, tmp - 1, /* Berechne das von Elementen in IdealComp[i] erzeugte Ideal */ /*IdealComp[i] = makeideal( tech[3][3], IdealComp[i] ); */ IdealComp[i] = settomatrix( tech[3][3], IdealComp[i] ); /*ACHTUNG: BERECHNUNG VON HNF !!!*/ /*IdealComp[i] = mathnf( IdealComp[i], 1 )[1];*/ if( !nfisideal( tech[3][3], IdealComp[i] ), print( " In der ", i, "-ten Komponente ist kein Ideal \n " ); return( 0 ), IdealComp[i] = idealhnf( tech[3][3], IdealComp[i] ); ); ); /*IdealComp[tmp] = makeideal( bnf, IdealComp[tmp] );*/ IdealComp[tmp] = settomatrix( bnf, IdealComp[tmp] ); /*IdealComp[tmp] = mathnf( IdealComp[tmp] );*/ if( !nfisideal( bnf, IdealComp[tmp] ), print( " In der letzten Komponente ist kein Ideal \n " ); return( 0 ), IdealComp[tmp] = idealhnf( bnf, IdealComp[tmp] ); ); return( IdealComp ); } /* Gegeben: Menge von Elementen in bnf (gensys). Berechne den davon erzeugten O(bnf)-Modul */ makeideal( bnf, gensys )= { local( i, j, puffer ); puffer = List([]); for( i = 1, length( gensys ), for( j = 1, length( bnf.zk ), puffer = concat( puffer, List( [gensys[i]*bnf.zk[j]] ) ); ); ); return( puffer ); } /* Suche zu jedem Ideal I in IdealComp ein Hauptideal, in dem I kleinstmoeglichen Index hat. */ findprincideal( bnf, bnfext, tech, embed, IdealComp )= { local( i, ElemComp, tmp, len ); len = length( IdealComp ); ElemComp = vector( len, i, 0 ); for( i = 1, len - 1, tmp = bnfisprincipal( tech[3][3], IdealComp[i] ); if( ( tmp[1] == []~ ) || ( tmp[1] == [0]~ ), ElemComp[i] = nfbasistoalg( tech[3][3], tmp[2] ), /* IdealComp sind hier die Inversen der Komponenten von [O(bnfext) : O(bnf)[G]*Vau] */ ElemComp[i] = findbestprincideal( tech[3][3], idealinv( tech[3][3], IdealComp[i] ) ); ElemComp[i] = nfbasistoalg( tech[3][3], ElemComp[i] ); ElemComp[i] = ElemComp[i]^( -1 ); ); ); tmp = bnfisprincipal( bnf, IdealComp[len] ); if( ( tmp[1] == []~ ) || ( tmp[1] == [0]~ ), ElemComp[len] = nfbasistoalg( bnf, tmp[2] ), /* IdealComp sind hier die Inversen der Komponenten von [O(bnfext) : O(bnf)[G]*Vau] */ ElemComp[len] = findbestprincideal( bnf, idealinv( bnf, IdealComp[len] ) ); ElemComp[len] = nfbasistoalg( bnf, ElemComp[len] ); ElemComp[len] = ElemComp[len]^( -1 ); ); return( ElemComp ); } /* Id ist ein ganzes Ideal in bnf, finde einen Hauptideal alpha, so dass der Index [alpha:Id] moeglichst klein ist */ findbestprincideal( bnf, Id )= { local( i, j, fact, tmp, expvec, puffer, alpha ); puffer = List([]); /* Teste Id ist ganz */ tmp = idealnorm( bnf, Id ); if( denominator( tmp ) > 1, print( " In findbestprincideal ist kein ganzes Ideal \n " ); return( 0 ); ); fact = idealfactor( bnf, Id ); tmp = vector( matsize( fact )[1], i, fact[i, 2] ); expvec = allunderdiag( tmp, 0 ); for( i = 1, length( expvec ), tmp = 1; for( j = 1, length( expvec[i] ), tmp = idealmul( bnf, tmp, idealpow( bnf, fact[j, 1], expvec[i][j] ) ); ); tmp = bnfisprincipal( bnf, tmp ); /* Speichere Hauptideale im puffer */ if( ( tmp[1] == []~ ) || ( tmp[1] == [0]~ ), puffer = concat( puffer, List( [tmp[2]] ) ); ); ); /* Falls kein passendes HI gefunden gib O(bnf) zurueck*/ if( length( puffer ) == 0, return( 1 ) ); /* finde HI mit [O(bnf):alpha] maximal */ tmp = idealnorm( bnf, puffer[1] ); alpha = puffer[1]; for( i = 2, length( puffer ), if( idealnorm( bnf, puffer[i] ) > tmp, alpha = puffer[i]; tmp = idealnorm( bnf, puffer[i] ); ); ); return( alpha ); } /* Bestimmung von O(bnfext)^M fuer die Funktion findminind( ... ); DS ist die Darstellung der Gruppe auf O( bnf ); idemvec ist ein Vektor der Idempotenten des Gruppenrings bnf[G] */ findmaxordmodul( bnf, bnfext, gitter, embed, idemvec, DS, l, tech )= { local( i, tmp, eins, chidemvec, OKomp ); eins = [vector( l, i, 0 ), 1]; eins[1][1] = Mod( 1, bnf.pol ); /* Mache Idempotente invertierbar und berechne Inverse */ chidemvec = vector( length( idemvec ), i, Add( idemvec[i], eins ) ); for( i = 1, length( chidemvec ), chidemvec[i] = nfgroupringeltinv( bnf, chidemvec[i], l, tech ); ); /* Uebersetze chidemvec in die Matrizen */ for( i = 1, length( chidemvec ), chidemvec[i] = nfgroupringelttomat( bnf, bnfext, chidemvec[i], embed, DS ); ); /* Multipliziere O( bnf ) mit Inversen */ OKomp = vector( length( idemvec ), i, 0 ); for( i = 1, length( chidemvec ), OKomp[i] = chidemvec[i]*gitter; /*matid( length( bnfext.zk ) )*/ OKomp[i] = matrixtoset( bnfext, OKomp[i] ); ); /* Berechne Schnitt von OKomp mit gitter ( nicht notwendig O(bnfext) )*/ /*tmp = vector( length( bnfext.zk ), i, Mod( bnfext.zk[i], bnfext.pol ) );*/ /* Neue Zeile */ tmp = matrixtoset( bnfext, gitter ); for( i = 1, length( OKomp ), tmp = gitterintersect( bnfext, tmp, OKomp[i] ); ); tmp = settomatrix( bnfext, tmp ); return( mathnf( tmp ) ); } findmaxordmodulunram( bnf, bnfext, gitter, embed, idemvec, DS, l, tech )= { local( i, tmp, len, chbasisvec, OKomp ); len = length( tech[3][3].zk ); chbasisvec = List([]); for( i = 1, len, tmp = [Mod( tech[3][3].zk[i] + 1, tech[3][3].pol )^(-1), Mod(1, bnf.pol)]; chbasisvec = concat( chbasisvec, List( [tmp] ) ); ); len = length( bnf.zk ); for( i = 1, len, tmp = [Mod( 1, tech[3][3].pol ), Mod( bnf.zk[i] + 1, bnf.pol)^(-1)]; chbasisvec = concat( chbasisvec, List( [tmp] ) ); ); len = length( chbasisvec ); for( i = 1, len, chbasisvec[i] = nfwedderburninv( bnf, chbasisvec[i], l, tech ); ); /* Uebersetze chbasisvec in die Matrizen */ for( i = 1, len, chbasisvec[i] = nfgroupringelttomat( bnf, bnfext, chbasisvec[i], embed, DS ); ); /* Multipliziere O( bnf ) mit Inversen */ OKomp = vector( len, i, 0 ); for( i = 1, len, OKomp[i] = chbasisvec[i]*gitter; /*matid( length( bnfext.zk ) )*/ OKomp[i] = matrixtoset( bnfext, OKomp[i] ); ); /* Berechne Schnitt von OKomp mit gitter ( nicht notwendig O(bnfext) )*/ /*tmp = vector( length( bnfext.zk ), i, Mod( bnfext.zk[i], bnfext.pol ) );*/ /* Neue Zeile */ tmp = matrixtoset( bnfext, gitter ); for( i = 1, length( OKomp ), tmp = gitterintersect( bnfext, tmp, OKomp[i] ); ); tmp = settomatrix( bnfext, tmp ); return( mathnf( tmp ) ); } /*END*/ /************************************************************************************/ /************************************************************************************/ /* FUNCTIONS RELATED TO THE LOCAL FIELDS */ /************************************************************************************/ /************************************************************************************/ /* Bestimmung von v in bnf, dessen globaler Artin-Symbol ( v*O(bnf), bnf/subbnf ) dem lokalen Artin-Symbol von teta in der Lokalisierung nach P geich ist. cond ist der Fuehrer von bnf/subbnf. P ist gegeben als idealprimedec. p ist der dem P zuge- hoeriges Primelement. */ artinglobal( bnf, teta, P, p, cond )= { local( xi, i, j, tmp, condred, fact, vec, e ); /* Datenvorbereitung fuer PARI-Funktion idealchinese() */ tmp = idealval( bnf, cond, P ); tmp = idealpow( bnf, P, -tmp ); condred = idealmul( bnf, cond, tmp ); tmp = idealfactor( bnf, condred ); fact = matrix( matsize( tmp )[1] + 1, matsize( tmp )[2], i, j, 0 ); fact[1,1] = P; fact[1,2] = idealval( bnf, cond, P ); /* Die Daten sind fertig */ for( i = 2, matsize( fact )[1], for( j = 1, matsize( fact )[2], fact[i, j] = tmp[i - 1, j]; ); ); tmp = p^( idealval( bnf, teta, P ) ); vec = vector( matsize( fact )[1], i, 0 ); for( i = 1, length( vec ), if( i == 1, vec[i] = tmp/teta, /* Achtung: ist moeglicherweise nicht ganz */ vec[i] = tmp; ); ); xi = idealchinese( bnf, fact, vec ); xi = nfbasistoalg( bnf, xi ); e = idealval(bnf, teta, P); tmp = idealpow(bnf, P, e); return( idealmul(bnf, tmp, xi/(p^e) )); } /* Bestimme exp in gen^(exp)=( vau*O(bnfext), bnfext/bnf ) ( globales Artin-Symbol, gegeben bei der Fkt-n artinglobal() ). gen entspricht dem ausgewaehlten Erzeuger der Galoisgruppe G = Gal( bnfext/bnf ). bnfext ist fix unter subgrp. */ findexp( artin, rcgp, subgrp, gen, ordG )= { local( k, tmp ); gen = bnrisprincipal( rcgp, gen )[1]; artin = bnrisprincipal( rcgp, artin )[1]; for( k = 0, ordG - 1, if( dtestin( subgrp, artin - k*gen ), return( k ); ); ); print( " findexp findet den Exponenten nicht \n " ); return( 0 ); } /* Sei alpha ein Element in bnf, P-Wert( alpha ) <= m. Diese Funktion berechnet exp-Reihenentwicklung von alpha( mod P^m ) bis zum s-ten Summanden in der Lokalisierung nach P. alpha ist gegeben als polmod, P als idealprimedec(). p ist die Primzahl, die unter P in Q liegt. */ expreihe( bnf, alpha, P, m, p, upper )= { local( i, j, tmp, tmpexp, tmpfac ); tmp = 1; tmpexp = 1; tmpfac = 1; for( j = 1, upper, tmpexp = tmpexp*alpha; tmpfac = tmpfac*j; tmp += tmpexp/tmpfac; ); return( tmp ); } /* Das Bild von L unter der exp-Abbildung in der Lokalisierung nach P modulo P^m. L ist ein Vektor von Polmods */ expimage( bnf, L, P, m, p )= { local( i, j, puffer, rest, Pm, s, tmp, pval, upper ); Pm = idealhnf( bnf, idealpow( bnf, P, m ) ); rest = gittermodgitter( L, Pm ); pval = idealval( bnf, p, P ); puffer = vector( length( rest ), i, 0 ); puffer[1] = Mod( 1, bnf.pol ); /* Es gilt immer: rest[1] = 0 nach implementierung der gittermodgitter() */ for( i = 1, length( rest ), rest[i] = nfbasistoalg( bnf, rest[i] ); ); for( i = 2, length( rest ), /* finde genuegend grosse p-Potenz, um die Reihe abzubrechen */ upper = ceil( m/( idealval( bnf, rest[i], P ) - 1/( p - 1 ) ) ); puffer[i] = expreihe( bnf, rest[i], P, m, p, upper ); ); return( puffer ); } /*END*/ /************************************************************************************/ /************************************************************************************/ /* FUNCTIONS RELATED TO THE LINEAR ALGEBRA, FINITE GROUPS AND SETS */ /************************************************************************************/ /************************************************************************************/ /* Bestimmung der Ordnung des Elements elem in einer endlichen Gruppe. elem gege- ben als Vektor, group als Vektor der Ordnungen der zyklischen Komponenten (SNF). */ calcord( elem, group )= { local( i, ordvec, len, tmp ); len = length( group ); /* ordvec enthaelt die Ordnungen der einzelnen Summanden von eps */ ordvec = vector( len, i, 0 ); for( i = 1, len, if( ( elem[i]%group[i] ) == 0, ordvec[i] = 1, tmp = gcd( elem[i], group[i] ); ordvec[i] = group[i]/tmp; ); ); tmp = 1; for( i = 1, len, tmp = lcm( tmp, ordvec[i] ); ); return( tmp ); } /* Liefert Vektor der Spaltenvektoren von M */ matrixtoveclist( M )= { local( i, j, veclist ); veclist = vector( matsize( M )[2], i, vector( matsize( M )[1], j, 0 )~ ); for( j = 1, matsize( M )[2], for( i = 1, matsize( M )[1], veclist[j][i] = M[i, j]; ); ); return( veclist ); } /* Zu der matrixtoveclist inverse Funktion */ veclisttomatrix( veclist )= { local( i, j, M ); M = matrix( length( veclist[1] ), length( veclist ), i, j, 0 ); for( i = 1, length( veclist ), for( j = 1, length( veclist[1] ), M[j, i] = veclist[i][j]; ); ); return( M ); } /* Berechnung des Repraesentantensystems M( mod N ), M, N gegeben in HNF Untermoduln von Z^n vom selben Rang. N ist ein Untermodul des M */ gittermodgitter( M, N ) = { local( i, j, A, tmp, RS, size ); if( matrank( M ) != matrank( N ), print( " In restmoduntergitter Gitter haben nicht gleichen Rang \n " ); return( 0 ); ); /* if( matsize( N )[1] != matsize( N )[2], print( " In restmoduntergitter Gitter haben nicht vollen Rang \n "); ); */ size = matsize( N )[2]; A = matrix( size, size, i, j, 0 ); M = mathnf( M ); N = mathnf( N ); for( j = 1, size, tmp = matinverseimage( M, vecextract( N, [j] ) ); if( matsize( tmp )[1] == 0, print( " N ist kein Untermodul von M \n " ); return( 0 ); ); for( i = 1, matsize( tmp )[1], A[i,j] = tmp[i,1]; ); ); A = mathnf( A ); RS = restmodgitter( A ); for( i = 1, length( RS ), RS[i] = M*RS[i]; ); return( RS ); } /* Berechet volles Representantensystem von Ganzheitsring in bnf modulo gitter. gitter gegeben durch eine Matrix mit Eintraegen in Z, Spalten sind Koordina- ten in der Ganzheitsbasis. Ergebnis ist Liste von polmod's. */ restmodgitter( gitter ) = { local( i, L, RS, ngitter, upper, diag ); ngitter = mathnf( gitter ); if( matsize( ngitter )[1] != matsize( ngitter )[2] || matdet( gitter ) == 0, print( " In restmodgitter rank ist nicht voll \n " ); return( 0 ); ); diag = vector( matsize( ngitter )[1], i, ngitter[i,i] ); RS = allunderdiag( diag, 1 ); for( i = 1, length( RS ), RS[i] = mattranspose( RS[i] ) ); return( RS ); } /* Test: Vector X in dem ganzzahligen Aufspann von Matrix M, M ist invertierbar. */ dtestin( M, X )= { local( i, tmp ); if( matsize( M )[1] != matsize( M )[2], print( " In testin() ist M keine quadratische Matrix \n " ); return( [] ); ); if( matdet( M ) == 0, print( " In dtestin() ist M nicht invertierbar \n " ); return( [] ); ); tmp = matinverseimage( M, X ); for( i = 1, length( tmp ), if( denominator( tmp[i] ) != 1, return( 0 ) ); ); return( 1 ); } /* Teste ob M ein Untergitter von N ist */ gittertestin( N, M )= { local( i, j, tmp ); tmp = vector( matsize(M)[1], j, 0 ); M = mathnf( M ); N = mathnf( N ); if( matsize(M)[2] > matsize(N)[2] || matsize(M)[1] != matsize(N)[1], print( " In gittersetin incompatible Dimensionen \n " ); return( 0 ); ); for( i = 1, matsize(M)[2], for( j = 1, length( tmp ), tmp[j] = M[j,i]; ); if( !dtestin( N, tmp~ ), return( 0 ); ); ); return(1); } /* Analog zu allunderupper, nur jede Komponente in einem Tupel ist restringiert durch die entsprechende Komponente in diag. L ist gegeben durch allunderupper, diag ist ein Vektor. */ allunderdiag( diag, flag ) = { local( i, L ); if( flag == 1, L = vector( diag[length( diag )], i, [i - 1] ), L = vector( diag[length( diag )] + 1, i, [i - 1] ); ); print( " L = ", L, " \n " ); for( j = 1, length( diag ) - 1, /* einer weniger, denn L ist bereits 1-dim */ L = concatelem( diag[length( diag ) - j] - flag, L ); ); return( L ); } /* Haenge eine Zahl zwischen 0 und upper vor jeder Komponente des Vektors L. Ergebnis: Vektor der Laenge ( upper + 1 ) [i, L], 0 <= i <= upper */ concatelem( upper, L ) = { local( i, j, puffer ); puffer = vector( ( upper + 1 )*length( L ), i, vector( length( L[1] ) + 1, j, 0 ) ); for( j = 1, length( L ), for( i = 1, upper + 1, puffer[(j - 1)*( upper + 1 ) + i][1] = i - 1; for( k = 2, length( L[j] ) + 1, puffer[( j - 1 )*( upper + 1) + i][k] = L[j][k - 1] ; ); ); ); return( puffer ); } /* Fuer zwei Mengen M, N, gegeben als Vektoren berechnet die mengentheoretische Differenz M\N */ complement( M, N ) = { local( puffer, i, j, mlen, nlen, tmp, flag ); puffer = List( [] ); mlen = length( M ); nlen = length( N ); for( j = 1, mlen, flag = 1; tmp = M[j]; i = 1; while( flag != 0 && i <= nlen, if( tmp == N[i], flag = 0, ); i = i + 1; ); if( flag == 1, puffer = concat( puffer, List( [tmp] ) ); ); ); return( puffer ); } /* fuer zwei Vektoren oder Listen finde ob diese bis auf Permutation von Eintraegen glech sind */ isperm( L, M )= { local( i, j, tmp ); tmp = M; if( length( L ) != length( M ), return( 0 ) ); for( i = 1, length( L ), M = complement( M, [L[i]] ); ); for( i = 1, length( tmp ), L = complement( L, [tmp[i]] ); ); if( length( M ) == 0 && length( L ) == 0, return( 1 ), return( 0 ); ); } {InitSubset(r, t, i) = return(vector(r, i, i)); } {NextSubset(s, t, i, r, s1, j, carry, false)= i = r = length(s); carry = true; false = 0; s1 = concat(s, [t+1]); while ( i > 0 && carry, if (s1[i] < s1[i+1]-1, s1[i]++; carry = false , i-- ); ); if (carry, return(false)); if (i < r, for (j = i+1, r, s1[j] = s1[j-1]+1) ); return(vector(r, i, s1[i])); } {EnumSubSets(PrimeSet, r, Subset, p, cnt) = cnt = 0; Subset = InitSubset(r, length(PrimeSet)); while (Subset, p = vector(r, i, PrimeSet[Subset[i]]); print( " p = ", p, " \n " ); cnt++: Subset = NextSubset(Subset, length(PrimeSet)); ); print( " Anzahl der Teilmengen: ", cnt, " \n " ); } EnumSubSetsRet(PrimeSet, r)= { local( Subset, p, cnt, puffer ); puffer = List( [] ); cnt = 0; Subset = InitSubset(r, length(PrimeSet)); while( Subset, p = vector(r, i, PrimeSet[Subset[i]]); puffer = concat( puffer, List( [p] ) ); cnt++: Subset = NextSubset(Subset, length(PrimeSet)); ); return( puffer ); } /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/