|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Martin Schönert.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains generic methods for division rings.
##
#############################################################################
##
#M DivisionRingByGenerators( <gens> ) . . . . . . . . . . for a collection
#M DivisionRingByGenerators( <F>, <gens> ) . . for div.ring and collection
##
InstallOtherMethod( DivisionRingByGenerators,
"for a collection",
[ IsCollection ],
coll -> DivisionRingByGenerators(
FieldOverItselfByGenerators( [ One( Representative( coll ) ) ] ),
coll ) );
InstallMethod( DivisionRingByGenerators,
"for a division ring, and a collection",
IsIdenticalObj,
[ IsDivisionRing, IsCollection ],
function( F, gens )
local D;
D:= Objectify( NewType( FamilyObj( gens ),
IsField and IsAttributeStoringRep ),
rec() );
SetLeftActingDomain( D, F );
SetGeneratorsOfDivisionRing( D, AsList( gens ) );
return D;
end );
#############################################################################
##
#M FieldOverItselfByGenerators( <gens> )
##
InstallMethod( FieldOverItselfByGenerators,
"for a collection",
[ IsCollection ],
function( gens )
local F;
if IsEmpty( gens ) then
Error( "need at least one element" );
fi;
F:= Objectify( NewType( FamilyObj( gens ),
IsField and IsAttributeStoringRep ),
rec() );
SetLeftActingDomain( F, F );
SetGeneratorsOfDivisionRing( F, gens );
return F;
end );
#############################################################################
##
#M DefaultFieldByGenerators( <gens> ) . . . . . . . . . . for a collection
##
InstallMethod( DefaultFieldByGenerators,
"for a collection",
[ IsCollection ],
DivisionRingByGenerators );
#############################################################################
##
#F Field( <z>, ... ) . . . . . . . . . field generated by a list of elements
#F Field( [ <z>, ... ] )
#F Field( <F>, [ <z>, ... ] )
##
InstallGlobalFunction( Field, function ( arg )
local F; # field containing the elements of <arg>, result
# special case for one square matrix
if Length(arg) = 1
and IsMatrix( arg[1] ) and Length( arg[1] ) = Length( arg[1][1] )
then
F := FieldByGenerators( arg );
# special case for list of elements
elif Length(arg) = 1 and IsList(arg[1]) then
F := FieldByGenerators( arg[1] );
# special case for subfield and generators
elif Length(arg) = 2 and IsField(arg[1]) then
F := FieldByGenerators( arg[1], arg[2] );
# other cases
else
F := FieldByGenerators( arg );
fi;
# return the field
return F;
end );
#############################################################################
##
#F DefaultField( <z>, ... ) . . . . . default field containing a collection
##
InstallGlobalFunction( DefaultField, function ( arg )
local F; # field containing the elements of <arg>, result
# special case for one square matrix
if Length(arg) = 1
and IsMatrix( arg[1] ) and Length( arg[1] ) = Length( arg[1][1] )
then
F := DefaultFieldByGenerators( arg );
# special case for list of elements
elif Length(arg) = 1 and IsList(arg[1]) then
F := DefaultFieldByGenerators( arg[1] );
# other cases
else
F := DefaultFieldByGenerators( arg );
fi;
# return the default field
return F;
end );
#############################################################################
##
#F Subfield( <F>, <gens> ) . . . . . . . subfield of <F> generated by <gens>
#F SubfieldNC( <F>, <gens> )
##
InstallGlobalFunction( Subfield, function( F, gens )
local S;
if IsEmpty( gens ) then
return PrimeField( F );
elif IsHomogeneousList( gens )
and IsIdenticalObj( FamilyObj( F ), FamilyObj( gens ) )
and ForAll( gens, g -> g in F ) then
S:= FieldByGenerators( LeftActingDomain( F ), gens );
SetParent( S, F );
return S;
fi;
Error( "<gens> must be a list of elements in <F>" );
end );
InstallGlobalFunction( SubfieldNC, function( F, gens )
local S;
if IsEmpty( gens ) then
S:= Objectify( NewType( FamilyObj( F ),
IsDivisionRing and IsAttributeStoringRep ),
rec() );
SetLeftActingDomain( S, F );
SetGeneratorsOfDivisionRing( S, AsList( gens ) );
else
S:= DivisionRingByGenerators( LeftActingDomain( F ), gens );
fi;
SetParent( S, F );
return S;
end );
#############################################################################
##
#M ClosureDivisionRing( <D>, <d> ) . . . . . . . . . closure with an element
##
InstallMethod( ClosureDivisionRing,
"for a division ring and a scalar",
IsCollsElms,
[ IsDivisionRing, IsScalar ],
function( D, d )
# if possible test if the element lies in the division ring already,
if HasGeneratorsOfDivisionRing( D )
and d in GeneratorsOfDivisionRing( D ) then
return D;
# otherwise make a new division ring
else
return DivisionRingByGenerators( LeftActingDomain( D ),
Concatenation( GeneratorsOfDivisionRing( D ), [ d ] ) );
fi;
end );
InstallMethod( ClosureDivisionRing,
"for a division ring containing the whole family, and a scalar",
IsCollsElms,
[ IsDivisionRing and IsWholeFamily, IsScalar ],
SUM_FLAGS, # we can't be better than this
ReturnFirst);
#############################################################################
##
#M ClosureDivisionRing( <D>, <C> ) . . . . . . . . closure of division ring
##
InstallMethod( ClosureDivisionRing,
"for division ring and collection of elements",
IsIdenticalObj,
[ IsDivisionRing, IsCollection ],
function( D, C )
local d; # one generator
if IsDivisionRing( C ) then
if not IsSubset( LeftActingDomain( D ), LeftActingDomain( C ) ) then
C:= AsDivisionRing( Intersection( LeftActingDomain( C ),
LeftActingDomain( D ) ), C );
fi;
C:= GeneratorsOfDivisionRing( C );
elif not IsList( C ) then
TryNextMethod();
fi;
for d in C do
D:= ClosureDivisionRing( D, d );
od;
return D;
end );
InstallMethod( ClosureDivisionRing,
"for division ring and empty list",
[ IsDivisionRing, IsList and IsEmpty ],
ReturnFirst);
#############################################################################
##
#M ViewObj( <F> ) . . . . . . . . . . . . . . . . . . . . . . view a field
##
InstallMethod( ViewObj,
"for a field",
[ IsField ],
function( F )
if HasSize( F ) and IsInt( Size( F ) ) then
Print( "<field of size ", String(Size( F )), ">" );
else
Print( "<field in characteristic ", Characteristic( F ), ">" );
fi;
end );
#############################################################################
##
#M ViewString( <F> ) . . . . . . . . . . . . . . . . . . . . . view a field
##
InstallMethod( ViewString,
"for a field",
[ IsField ],
function( F )
if HasSize( F ) and IsInt( Size( F ) ) then
return Concatenation("<field of size ", String(Size( F )), ">" );
else
return Concatenation( "<field in characteristic ",
String(Characteristic( F )), ">" );
fi;
end );
#############################################################################
##
#M PrintObj( <F> ) . . . . . . . . . . . . . . . . . . . . . . print a field
##
InstallMethod( PrintObj,
"for a field with known generators",
[ IsField and HasGeneratorsOfField ],
function( F )
if IsIdenticalObj(F,LeftActingDomain(F)) or
IsPrimeField( LeftActingDomain( F ) ) then
Print( "Field( ", GeneratorsOfField( F ), " )" );
elif F = LeftActingDomain( F ) then
Print( "FieldOverItselfByGenerators( ",
GeneratorsOfField( F ), " )" );
else
Print( "AsField( ", LeftActingDomain( F ),
", Field( ", GeneratorsOfField( F ), " ) )" );
fi;
end );
InstallMethod( PrintObj,
"for a field",
[ IsField ],
function( F )
if IsPrimeField( LeftActingDomain( F ) ) then
Print( "Field( ... )" );
elif F = LeftActingDomain( F ) then
Print( "AsField( ~, ... )" );
else
Print( "AsField( ", LeftActingDomain( F ), ", ... )" );
fi;
end );
#############################################################################
##
#M IsTrivial( <F> ) . . . . . . . . . . . . . . . . . . for a division ring
##
InstallMethod( IsTrivial,
"for a division ring",
[ IsDivisionRing ],
ReturnFalse );
#############################################################################
##
#M PrimeField( <F> ) . . . . . . . . . . . . . . . . . . for a division ring
##
InstallMethod( PrimeField,
"for a division ring",
[ IsDivisionRing ],
function( F )
local P;
P:= Field( One( F ) );
UseSubsetRelation( F, P );
SetIsPrimeField( P, true );
return P;
end );
InstallMethod( PrimeField,
"for a prime field",
[ IsField and IsPrimeField ],
IdFunc );
#############################################################################
##
#M IsPrimeField( <F> ) . . . . . . . . . . . . . . . . . for a division ring
##
InstallMethod( IsPrimeField,
"for a division ring",
[ IsDivisionRing ],
F -> DegreeOverPrimeField( F ) = 1 );
#############################################################################
##
#M IsNumberField( <F> ) . . . . . . . . . . . . . . . . . . . . for a field
##
InstallMethod( IsNumberField,
"for a field",
[ IsField ],
F -> Characteristic( F ) = 0 and IsInt( DegreeOverPrimeField( F ) ) );
#############################################################################
##
#M IsAbelianNumberField( <F> ) . . . . . . . . . . . . . . . . . for a field
##
InstallMethod( IsAbelianNumberField,
"for a field",
[ IsField ],
F -> IsNumberField( F ) and IsCommutative( GaloisGroup(
AsField( PrimeField( F ), F ) ) ) );
#############################################################################
##
#M IsCyclotomicField( <F> ) . . . . . . . . . . . . . . . . . . for a field
##
InstallMethod( IsCyclotomicField,
"for a field",
[ IsField ],
F -> IsAbelianNumberField( F )
and Conductor( F ) = DegreeOverPrimeField( F ) );
#############################################################################
##
#M IsNormalBasis( <B> ) . . . . . . . . . . . . . for a basis (of a field)
##
InstallMethod( IsNormalBasis,
"for a basis of a field",
[ IsBasis ],
function( B )
local vectors;
if not IsField( UnderlyingLeftModule( B ) ) then
Error( "<B> must be a basis of a field" );
fi;
vectors:= BasisVectors( B );
return Set( vectors )
= Set( Conjugates( UnderlyingLeftModule( B ), vectors[1] ) );
end );
#############################################################################
##
#M GeneratorsOfDivisionRing( <F> ) . . . . . . . . . . . . for a prime field
##
InstallMethod( GeneratorsOfDivisionRing,
"for a prime field",
[ IsField and IsPrimeField ],
F -> [ One( F ) ] );
#############################################################################
##
#M DegreeOverPrimeField( <F> ) . . . . . . . . . . . . . . for a prime field
##
InstallImmediateMethod( DegreeOverPrimeField, IsPrimeField, 20, F -> 1 );
#############################################################################
##
#M NormalBase( <F> ) . . . . . . . . . . for a field in characteristic zero
#M NormalBase( <F>, <elm> ) . . . . . . for a field in characteristic zero
##
## For fields in characteristic zero, a normal basis is computed
## as described on p.~65~f.~in~\cite{Art68}.
## Let $\Phi$ denote the polynomial of the field extension $L/L^{\prime}$,
## $\Phi^{\prime}$ its derivative and $\alpha$ one of its roots;
## then for all except finitely many elements $z \in L^{\prime}$,
## the conjugates of $\frac{\Phi(z)}{(z-\alpha)\cdot\Phi^{\prime}(\alpha)}$
## form a normal basis of $L/L^{\prime}$.
##
## When `NormalBase' is called for a field <F> in characteristic zero and
## an element <elm>,
## $z$ is chosen as <elm>, $<elm> + 1$, $<elm> + 2$, \ldots,
## until a normal basis is found.
## The default of <elm> is the identity of <F>.
##
InstallMethod( NormalBase,
"for a field (in characteristic zero)",
[ IsField ],
F -> NormalBase( F, One( F ) ) );
InstallMethod( NormalBase,
"for a field (in characteristic zero), and a scalar",
[ IsField, IsScalar ],
function( F, z )
local alpha, poly, i, val, normal;
# Check the arguments.
if Characteristic( F ) <> 0 then
TryNextMethod();
elif not z in F then
Error( "<z> must be an element in <F>" );
fi;
# Get a primitive element `alpha'.
alpha:= PrimitiveElement( F );
# Construct the polynomial
# $\prod_{\sigma\in `Gal( alpha )'\setminus \{1\} } (x-\sigma(`alpha') )
# for the primitive element `alpha'.
poly:= [ 1 ];
for i in Difference( Conjugates( F, alpha ), [ alpha ] ) do
poly:= ProductCoeffs( poly, [ -i, 1 ] );
#T ?
od;
# For the denominator, evaluate `poly' at `a'.
val:= Inverse( ValuePol( poly, alpha ) );
# There are only finitely many values `x' in the subfield
# for which `poly(x) * val' is not an element of a normal basis.
repeat
normal:= Conjugates( F, ValuePol( poly, z ) * val );
z:= z + 1;
until RankMat( List( normal, COEFFS_CYC ) ) = Dimension( F );
# Return the result.
return normal;
end );
#############################################################################
##
#M PrimitiveElement( <D> ) . . . . . . . . . . . . . . . for a division ring
##
InstallMethod( PrimitiveElement,
"for a division ring",
[ IsDivisionRing ],
function( D )
D:= GeneratorsOfDivisionRing( D );
if Length( D ) = 1 then
return D[1];
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M Representative( <D> ) . . . . . for a division ring with known generators
##
InstallMethod( Representative,
"for a division ring with known generators",
[ IsDivisionRing and HasGeneratorsOfDivisionRing ],
RepresentativeFromGenerators( GeneratorsOfDivisionRing ) );
#############################################################################
##
#M Enumerator( <F> ) . . . . . . . . . . elements of a (finite) prime field
#M EnumeratorSorted( <F> ) . . . . . . . elements of a (finite) prime field
##
## We install a special method only for (finite) prime fields,
## since the other cases are handled by the vector space methods.
##
BindGlobal( "EnumeratorOfPrimeField", function( F )
local one;
one:= One( F );
if Size( F ) <= MAXSIZE_GF_INTERNAL then
return AsSSortedListList( List( [ 0 .. Size( F ) - 1 ], i -> i * one ) );
elif IsZmodnZObj( one ) then
return EnumeratorOfZmodnZ( F );
fi;
TryNextMethod();
end );
InstallMethod( Enumerator,
"for a finite prime field",
[ IsField and IsPrimeField and IsFinite ],
EnumeratorOfPrimeField );
InstallMethod( EnumeratorSorted,
"for a finite prime field",
[ IsField and IsPrimeField and IsFinite ],
EnumeratorOfPrimeField );
InstallMethod( AsList,
"for a finite prime field",
[ IsField and IsPrimeField and IsFinite ],
F -> AsList( Enumerator( F ) ) );
#############################################################################
##
#M IsSubset( <D>, <F> ) . . . . . . . . . . . . . . for two division rings
##
## We have to be careful not to run into an infinite recursion in the case
## that <F> is equal to its left acting domain.
## Also we must be aware of situations where the left acting domains are
## in a family different from that of the fields themselves,
## for example <D> could be given as a field over a field that is really
## a subset of <D>, whereas the left acting domain of <F> is not a subset
## of <F>.
##
BindGlobal( "DivisionRing_IsSubset", function( D, F )
local CF;
# Special case for when F equals the cyclotomics (and hence is infinite
# dimensional over its left acting domain).
if IsIdenticalObj(F, Cyclotomics) then
return IsIdenticalObj(D, Cyclotomics);
fi;
CF:= LeftActingDomain( F );
if not IsSubset( D, GeneratorsOfDivisionRing( F ) ) then
return false;
elif IsSubset( LeftActingDomain( D ), CF ) or IsPrimeField( CF ) then
return true;
elif FamilyObj( F ) = FamilyObj( CF ) then
return IsSubset( D, CF );
else
CF:= AsDivisionRing( PrimeField( CF ), CF );
return IsSubset( D, List( GeneratorsOfDivisionRing( CF ),
x -> x * One( F ) ) );
fi;
end );
InstallMethod( IsSubset,
"for two division rings",
IsIdenticalObj,
[ IsDivisionRing, IsDivisionRing ],
DivisionRing_IsSubset );
#############################################################################
##
#M \=( <D>, <F> ) . . . . . . . . . . . . . . . . . for two division rings
##
InstallMethod( \=,
"for two division rings",
IsIdenticalObj,
[ IsDivisionRing, IsDivisionRing ],
function( D, F )
return DivisionRing_IsSubset( D, F ) and DivisionRing_IsSubset( F, D );
end );
#############################################################################
##
#M AsDivisionRing( <C> ) . . . . . . . . . . . . . . . . . for a collection
##
InstallMethod( AsDivisionRing,
"for a collection",
[ IsCollection ],
function( C )
local one, F;
# A division ring contains at least two elements.
if IsEmpty( C ) or IsTrivial( C ) then
return fail;
fi;
# Construct the prime field.
one:= One( Representative( C ) );
if one = fail then
return fail;
fi;
F:= FieldOverItselfByGenerators( [ one ] );
# Delegate to the two-argument version.
return AsDivisionRing( F, C );
end );
#############################################################################
##
#M AsDivisionRing( <F>, <C> ) . . . . for a division ring, and a collection
##
InstallMethod( AsDivisionRing,
"for a division ring, and a collection",
IsIdenticalObj,
[ IsDivisionRing, IsCollection ],
function( F, C )
local D;
if not IsSubset( C, F ) then
return fail;
fi;
D:= DivisionRingByGenerators( F, C );
if D <> C then
return fail;
fi;
return D;
end );
#############################################################################
##
#M AsDivisionRing( <F>, <D> ) . . . . . . . . . . . for two division rings
##
InstallMethod( AsDivisionRing,
"for two division rings",
IsIdenticalObj,
[ IsDivisionRing, IsDivisionRing ],
function( F, D )
local E;
if F = LeftActingDomain( D ) then
return D;
elif not IsSubset( D, F ) then
return fail;
fi;
E:= DivisionRingByGenerators( F, GeneratorsOfDivisionRing( D ) );
UseIsomorphismRelation( D, E );
UseSubsetRelation( D, E );
return E;
end );
#############################################################################
##
#M AsLeftModule( <F1>, <F2> ) . . . . . . . . . . . for two division rings
##
## View the division ring <F2> as vector space over the division ring <F1>.
##
InstallMethod( AsLeftModule,
"for two division rings",
IsIdenticalObj,
[ IsDivisionRing, IsDivisionRing ],
AsDivisionRing );
#############################################################################
##
#M Conjugates( <F>, <z> ) . . . . . . . . . . conjugates of a field element
#M Conjugates( <z> ) . . . . . . . . . . . . . conjugates of a field element
##
InstallMethod( Conjugates,
"for a scalar (delegate to version with default field)",
[ IsScalar ],
z -> Conjugates( DefaultField( z ), z ) );
InstallMethod( Conjugates,
"for a field and a scalar (delegate to version with two fields)",
IsCollsElms,
[ IsField, IsScalar ],
function( F, z )
return Conjugates( F, LeftActingDomain( F ), z );
end );
#############################################################################
##
#M Conjugates( <L>, <K>, <z> ) . . for a field elm. (use `TracePolynomial')
##
InstallMethod( Conjugates,
"for two fields and a scalar (call `TracePolynomial')",
IsCollsXElms,
[ IsField, IsField, IsScalar ],
function( L, K, z )
local pol, lin, conj, mult, i;
# Check whether `Conjugates' is allowed to call `MinimalPolynomial'.
if IsFieldControlledByGaloisGroup( L ) then
TryNextMethod();
fi;
# Compute the roots in `L' of the minimal polynomial of `z' over `K'.
pol:= MinimalPolynomial( K, z );
lin:= List( Filtered( Factors( L, pol ),
x -> DegreeOfLaurentPolynomial( x ) = 1 ),
CoefficientsOfUnivariatePolynomial );
lin:= List( lin, x -> AdditiveInverse( lin[1] / lin[2] ) );
# Take the roots with the appropriate multiplicity.
conj:= [];
mult:= DegreeOverPrimeField( L ) / DegreeOverPrimeField( K );
mult:= mult / DegreeOfLaurentPolynomial( pol );
for i in [ 1 .. mult ] do
Append( conj, lin );
od;
return conj;
end );
#############################################################################
##
#M Conjugates( <L>, <K>, <z> ) . . . for a field element (use `GaloisGroup')
##
InstallMethod( Conjugates,
"for two fields and a scalar (call `GaloisGroup')",
IsCollsXElms,
[ IsFieldControlledByGaloisGroup, IsField, IsScalar ],
function( L, K, z )
local cnjs, # conjugates of <z> in <F>, result
aut; # automorphism of <F>
# Check the arguments.
if not z in L then
Error( "<z> must lie in <L>" );
fi;
# Compute the conjugates simply by applying all the automorphisms.
cnjs:= [];
for aut in GaloisGroup( AsField( L, K ) ) do
Add( cnjs, z ^ aut );
od;
# Return the conjugates.
return cnjs;
end );
#############################################################################
##
#M Norm( <F>, <z> ) . . . . . . . . . . . . . . . . norm of a field element
#M Norm( <z> ) . . . . . . . . . . . . . . . . . . . norm of a field element
##
InstallMethod( Norm,
"for a scalar (delegate to version with default field)",
[ IsScalar ],
z -> Norm( DefaultField( z ), z ) );
InstallMethod( Norm,
"for a field and a scalar (delegate to version with two fields)",
IsCollsElms,
[ IsField, IsScalar ],
function( F, z )
return Norm( F, LeftActingDomain( F ), z );
end );
#############################################################################
##
#M Norm( <L>, <K>, <z> ) . . . . norm of a field element (use `Conjugates')
##
InstallMethod( Norm,
"for two fields and a scalar (use `Conjugates')",
IsCollsXElms,
[ IsFieldControlledByGaloisGroup, IsField, IsScalar ],
function( L, K, z )
return Product( Conjugates( L, K, z ) );
end );
#############################################################################
##
#M Norm( <L>, <K>, <z> ) . . . norm of a field element (use the trace pol.)
##
InstallMethod( Norm,
"for two fields and a scalar (use the trace pol.)",
IsCollsXElms,
[ IsField, IsField, IsScalar ],
function( L, K, z )
local coeffs;
coeffs:= CoefficientsOfUnivariatePolynomial(
TracePolynomial( L, K, z, 1 ) );
return (-1)^(Length( coeffs )-1) * coeffs[1];
end );
#############################################################################
##
#M Trace( <z> ) . . . . . . . . . . . . . . . . . trace of a field element
#M Trace( <F>, <z> ) . . . . . . . . . . . . . . . trace of a field element
##
InstallMethod( Trace,
"for a scalar (delegate to version with default field)",
[ IsScalar ],
z -> Trace( DefaultField( z ), z ) );
InstallMethod( Trace,
"for a field and a scalar (delegate to version with two fields)",
IsCollsElms,
[ IsField, IsScalar ],
function( F, z )
return Trace( F, LeftActingDomain( F ), z );
end );
#############################################################################
##
#M Trace( <L>, <K>, <z> ) . . . trace of a field element (use `Conjugates')
##
InstallMethod( Trace,
"for two fields and a scalar (use `Conjugates')",
IsCollsXElms,
[ IsFieldControlledByGaloisGroup, IsField, IsScalar ],
function( L, K, z )
return Sum( Conjugates( L, K, z ) );
end );
#############################################################################
##
#M Trace( <L>, <K>, <z> ) . . trace of a field element (use the trace pol.)
##
InstallMethod( Trace,
"for two fields and a scalar (use the trace pol.)",
IsCollsXElms,
[ IsField, IsField, IsScalar ],
function( L, K, z )
local coeffs;
coeffs:= CoefficientsOfUnivariatePolynomial(
TracePolynomial( L, K, z, 1 ) );
return AdditiveInverse( coeffs[ Length( coeffs ) - 1 ] );
end );
#############################################################################
##
#M MinimalPolynomial( <F>, <z>, <nr> )
##
## If the default field of <z> knows how to get the Galois group then
## we compute the conjugates and from them the minimal polynomial.
## Otherwise we solve an equation system.
##
## Note that the family predicate `IsCollsElmsX' expresses that <z> may lie
## in an extension field of <F>;
## this guarantees that the method is *not* applicable for the case that <z>
## is a matrix.
##
InstallMethod( MinimalPolynomial,
"for field, scalar, and indet. number",
IsCollsElmsX,
[ IsField, IsScalar,IsPosInt ],
function( F, z, ind )
local L, coe, deg, zero, con, i, B, pow, mat, MB;
# Construct a basis of a field in which the computations happen.
# (This need not be the smallest such field.)
L:= DefaultField( z );
if IsFieldControlledByGaloisGroup( L ) then
# We may call `Conjugates'.
coe:= [ One( F ) ];
deg:= 0;
zero:= Zero( F );
for con in Conjugates( Field( F, [ z ] ), z ) do
coe[deg+2]:= coe[deg+1];
for i in [ deg+1, deg .. 2 ] do
coe[i]:= coe[i-1] - con * coe[i];
od;
coe[1]:= zero - con * coe[1];
deg:= deg + 1;
od;
else
# Solve an equation system.
B:= Basis( L );
# Compute coefficients of the powers of `z' until
# the rows are linearly dependent.
pow:= One( F );
coe:= Coefficients( B, pow );
mat:= [ coe ];
MB:= MutableBasis( F, [ coe ] );
repeat
CloseMutableBasis( MB, coe );
pow:= pow * z;
coe:= Coefficients( B, pow );
Add( mat, coe );
until IsContainedInSpan( MB, coe );
# The coefficients of the minimal polynomial
# are given by the linear relation.
coe:= NullspaceMat( mat )[1];
coe:= Inverse( Last(coe) ) * coe;
fi;
# Construct the polynomial.
return UnivariatePolynomial( F, coe, ind );
end );
#############################################################################
##
#M TracePolynomial( <L>, <K>, <z> )
#M TracePolynomial( <L>, <K>, <z>, <ind> )
##
InstallMethod( TracePolynomial,
"using minimal polynomial",
IsCollsXElmsX,
[ IsField, IsField, IsScalar, IsPosInt ],
function( L, K, z, ind )
local minpol, mult;
minpol:= MinimalPolynomial( K, z, ind );
mult:= DegreeOverPrimeField( L ) / DegreeOverPrimeField( K );
mult:= mult / DegreeOfLaurentPolynomial( minpol );
return minpol ^ mult;
end );
InstallMethod( TracePolynomial,
"add default indet. 1",
IsCollsXElms,
[ IsField, IsField, IsScalar ],
function( L, K, z )
return TracePolynomial( L, K, z, 1 );
end );
#############################################################################
##
#M CharacteristicPolynomial( <L>, <K>, <z> )
#M CharacteristicPolynomial( <L>, <K>, <z>, <ind> )
##
InstallOtherMethod( CharacteristicPolynomial,
"call `TracePolynomial'",
IsCollsXElms,
[ IsField, IsField, IsScalar ],
function( L, K, z )
return TracePolynomial( L, K, z, 1 );
end );
InstallOtherMethod( CharacteristicPolynomial,
"call `TracePolynomial'",
IsCollsXElmsX,
[ IsField, IsField, IsScalar, IsPosInt ],
TracePolynomial );
#############################################################################
##
#M NiceFreeLeftModuleInfo( <V> )
#M NiceVector( <V>, <v> )
#M UglyVector( <V>, <r> )
##
InstallHandlingByNiceBasis( "IsFieldElementsSpace", rec(
detect := function( F, gens, V, zero )
return IsScalarCollection( V )
and IsIdenticalObj( FamilyObj( F ), FamilyObj( V ) )
and IsDivisionRing( F );
end,
NiceFreeLeftModuleInfo := function( V )
local lad, gens;
# Compute the default field of the vector space generators,
# and a basis of this field (over the left acting domain of `V').
lad:= LeftActingDomain( V );
if not IsIdenticalObj( FamilyObj( V ), FamilyObj( lad ) ) then
TryNextMethod();
fi;
return Basis( AsField( lad,
ClosureField( lad, GeneratorsOfLeftModule( V ) ) ) );
end,
NiceVector := function( V, v )
return Coefficients( NiceFreeLeftModuleInfo( V ), v );
end,
UglyVector := function( V, r )
local B;
B:= NiceFreeLeftModuleInfo( V );
if Length( r ) <> Length( B ) then
return fail;
fi;
return LinearCombination( B, r );
end ) );
#############################################################################
##
#M Quotient( <F>, <r>, <s> ) . . . . . . . . quotient of elements in a field
##
InstallMethod( Quotient,
"for a division ring, and two ring elements",
IsCollsElmsElms,
[ IsDivisionRing, IsRingElement, IsRingElement ],
function ( F, r, s )
if IsZero(s) then
return fail;
fi;
return r/s;
end );
#############################################################################
##
#M IsUnit( <F>, <r> ) . . . . . . . . . . check for being a unit in a field
##
InstallMethod( IsUnit,
"for a division ring, and a ring element",
IsCollsElms,
[ IsDivisionRing, IsRingElement ],
function ( F, r )
return not IsZero( r ) and r in F;
end );
#############################################################################
##
#M Units( <F> )
##
InstallMethod( Units,
"for a division ring",
[ IsDivisionRing ],
function( D )
if IsFinite( D ) then
return Difference( AsList( D ), [ Zero( D ) ] );
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M PrimitiveRoot( <F> ) . . . . . . . . . . . . for finite prime field <F>
##
## For a fields of prime order $p$, the multiplicative group corresponds to
## the group of residues modulo $p$, via `Int'.
## A primitive root is obtained as `PrimitiveRootMod( $p$ )' times the
## identity of <F>.
##
InstallMethod( PrimitiveRoot,
"for a finite prime field",
[ IsField and IsFinite ],
function( F )
if not IsPrimeField( F ) then
TryNextMethod();
fi;
return PrimitiveRootMod( Size( F ) ) * One( F );
end );
#############################################################################
##
#M EuclideanDegree( Integers, <n> ) . . . . . . . . . . . . . absolute value
##
InstallMethod( EuclideanDegree,
"for a division ring and a ring element",
IsCollsElms,
[ IsDivisionRing, IsRingElement ],
function ( F, r )
if not r in F then
TryNextMethod(); # FIXME: or error?
fi;
return 0;
end );
#############################################################################
##
#M QuotientRemainder( Integers, <n>, <m> ) . . . . . . . . . . . quo and rem
##
InstallMethod( QuotientRemainder,
"for a division ring, and two ring elements",
IsCollsElmsElms,
[ IsDivisionRing, IsRingElement, IsRingElement ],
function ( F, r, s )
if not r in F then
TryNextMethod(); # FIXME: or error?
fi;
return [ r/s, Zero(F) ];
end );
#############################################################################
##
#M Factors( Integers, <n> ) . . . . . . . . . . factorization of an integer
##
InstallMethod( Factors,
"for a division ring and a ring element",
IsCollsElms,
[ IsDivisionRing, IsRingElement ],
function ( F, r )
if not r in F then
TryNextMethod(); # FIXME: or error?
fi;
return [ r ];
end );
#############################################################################
##
#M IsAssociated( <F>, <r>, <s> ) . . . . . . check associatedness in a field
##
InstallMethod( IsAssociated,
"for a division ring, and two ring elements",
IsCollsElmsElms,
[ IsDivisionRing, IsRingElement, IsRingElement ],
function ( F, r, s )
return IsZero( r ) = IsZero( s );
end );
#############################################################################
##
#M StandardAssociate( <F>, <x> ) . . . . . . . standard associate in a field
##
InstallMethod( StandardAssociate,
"for a division ring and a ring element",
IsCollsElms,
[ IsDivisionRing, IsScalar ],
function ( R, r )
if IsZero( r ) then
return Zero( R );
else
return One( R );
fi;
end );
#############################################################################
##
#M StandardAssociateUnit( <F>, <x> )
##
InstallMethod( StandardAssociateUnit,
"for a division ring and a ring element",
IsCollsElms,
[ IsDivisionRing, IsScalar ],
function ( R, r )
if IsZero( r ) then
return One( R );
else
return r^-1;
fi;
end );
#############################################################################
##
#M IsIrreducibleRingElement( <F>, <x> )
##
InstallMethod(IsIrreducibleRingElement,
"for a division ring and a ring element",
IsCollsElms,
[ IsDivisionRing, IsScalar ],
function ( F, r )
if not r in F then
TryNextMethod(); # FIXME: or error?
fi;
# field elements are either zero or a unit
return false;
end );
#############################################################################
##
#M IsPrime( <F>, <x> )
##
InstallMethod(IsPrime,
"for a division ring and a ring element",
IsCollsElms,
[ IsDivisionRing, IsScalar ],
function ( F, r )
if not r in F then
TryNextMethod(); # FIXME: or error?
fi;
# field elements are either zero or a unit
return false;
end );
#############################################################################
##
## Field homomorphisms
##
#############################################################################
##
#M IsFieldHomomorphism( <map> )
##
InstallMethod( IsFieldHomomorphism,
[ IsGeneralMapping ],
map -> IsRingHomomorphism( map ) and IsField( Source( map ) ) );
#############################################################################
##
#M KernelOfAdditiveGeneralMapping( <fldhom> ) . . for a field homomorphism
##
InstallMethod( KernelOfAdditiveGeneralMapping,
"for a field homomorphism",
[ IsFieldHomomorphism ],
#T higher rank?
#T (is this method ever used?)
function ( hom )
if ForAll( GeneratorsOfDivisionRing( Source( hom ) ),
x -> IsZero( ImagesRepresentative( hom, x ) ) ) then
return Source( hom );
else
return TrivialSubadditiveMagmaWithZero( Source( hom ) );
fi;
end );
#############################################################################
##
#M IsInjective( <fldhom> ) . . . . . . . . . . . . for a field homomorphism
##
InstallMethod( IsInjective,
"for a field homomorphism",
[ IsFieldHomomorphism ],
hom -> Size( KernelOfAdditiveGeneralMapping( hom ) ) = 1 );
#############################################################################
##
#M IsSurjective( <fldhom> ) . . . . . . . . . . . for a field homomorphism
##
InstallMethod( IsSurjective,
"for a field homomorphism",
[ IsFieldHomomorphism ],
function ( hom )
if IsFinite( Range( hom ) ) then
return Size( Range( hom ) ) = Size( Image( hom ) );
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M \=( <hom1>, <hom2> ) . . . . . . . . . comparison of field homomorphisms
##
InstallMethod( \=,
"for two field homomorphisms",
IsIdenticalObj,
[ IsFieldHomomorphism, IsFieldHomomorphism ],
function ( hom1, hom2 )
# maybe the properties we already know determine the result
if ( HasIsInjective( hom1 ) and HasIsInjective( hom2 )
and IsInjective( hom1 ) <> IsInjective( hom2 ) )
or ( HasIsSurjective( hom1 ) and HasIsSurjective( hom2 )
and IsSurjective( hom1 ) <> IsSurjective( hom2 ) ) then
return false;
# otherwise we must really test the equality
else
return Source( hom1 ) = Source( hom2 )
and Range( hom1 ) = Range( hom2 )
and ForAll( GeneratorsOfField( Source( hom1 ) ),
elm -> Image(hom1,elm) = Image(hom2,elm) );
fi;
end );
#############################################################################
##
#M ImagesSet( <hom>, <elms> ) . . images of a set under a field homomorphism
##
InstallMethod( ImagesSet,
"for field homomorphism and field",
CollFamSourceEqFamElms,
[ IsFieldHomomorphism, IsField ],
function ( hom, elms )
elms:= FieldByGenerators( List( GeneratorsOfField( elms ),
gen -> ImagesRepresentative( hom, gen ) ) );
UseSubsetRelation( Range( hom ), elms );
return elms;
end );
#############################################################################
##
#M PreImagesElm( <hom>, <elm> ) . . . . . . . . . . . . preimage of an elm
##
InstallMethod( PreImagesElm,
"for field homomorphism and element",
FamRangeEqFamElm,
[ IsFieldHomomorphism, IsObject ],
function ( hom, elm )
if IsInjective( hom ) = 1 then
return [ PreImagesRepresentative( hom, elm ) ];
elif IsZero( elm ) then
return Source( hom );
else
return [];
fi;
end );
#############################################################################
##
#M PreImagesSet( <hom>, <elm> ) . . . . . . . . . . . . . preimage of a set
##
InstallMethod( PreImagesSet,
"for field homomorphism and field",
CollFamRangeEqFamElms,
[ IsFieldHomomorphism, IsField ],
function ( hom, elms )
elms:= FieldByGenerators( List( GeneratorsOfField( elms ),
gen -> PreImagesRepresentative( hom, gen ) ) );
UseSubsetRelation( Source( hom ), elms );
return elms;
end );
[ Dauer der Verarbeitung: 0.44 Sekunden
(vorverarbeitet)
]
|
