|
#############################################################################
##
#W dixon.gi Bettina Eick
##
## Determine Dixon's Bound for torsion free semisimple matrix groups.
##
#############################################################################
##
#F PadicValue( rat, p )
##
BindGlobal( "PadicValue", function( rat, p )
local a1, a2;
a1 := AbsInt( NumeratorRat(rat) );
a2 := DenominatorRat(rat);
a1 := Length( Filtered( FactorsInt(a1), x -> x = p ) );
a2 := Length( Filtered( FactorsInt(a2), x -> x = p ) );
return a1 - a2;
end );
#############################################################################
##
#F LogAbsValueBound( rat )
##
BindGlobal( "LogAbsValueBound", function( rat )
local a1, a2, a;
a1 := LogInt( AbsInt( NumeratorRat(rat) ), 2 );
a2 := LogInt( DenominatorRat(rat), 2 );
a := Maximum( AbsInt( a1 - a2 + 1 ), AbsInt( a1 - a2 - 1) );
return QuoInt( a * 3, 4 );
end );
#############################################################################
##
#F ConsideredPrimes( rats )
##
BindGlobal( "ConsideredPrimes", function( rats )
local pr, r, a1, a2, tmp;
pr := [];
for r in rats do
a1 := AbsInt( NumeratorRat(r) );
a2 := DenominatorRat(r);
if a1 <> 1 then
tmp := FactorsInt( a1: RhoTrials := 1000000 );
pr := Union( pr, tmp );
fi;
if a2 <> 1 then
tmp := FactorsInt( a2: RhoTrials := 1000000 );
pr := Union( pr, tmp );
fi;
od;
return pr;
end );
#############################################################################
##
#F CoefficientsByBase( base, vec )
##
BindGlobal( "CoefficientsByBase", function( base, vec )
local sol;
sol := MemberBySemiEchelonBase( vec, base.vectors );
if IsBool( sol ) then return fail; fi;
return sol * base.coeffs;
end );
#############################################################################
##
#F FullDixonBound( gens, prim )
##
BindGlobal( "FullDixonBound", function( gens, prim )
local c, f, j, n, d, minp, sub, max, cof, deg, base, cofs, dofs,
g, pr, t1, p, s, i, a, b, t2, t;
# set up
c := prim.elem;
f := prim.poly;
n := Length( gens );
d := Degree(f);
cof := CoefficientsOfUnivariatePolynomial( f );
if cof[1] <> 1 or cof[d+1] <> 1 then return fail; fi;
# get prim-basis
# Print("compute prim-base \n");
base := List([0..d-1], x -> Flat(c^x));
base := SemiEchelonMatTransformation( base );
# get coeffs of gens in prim-base
Print("compute coefficients \n");
cofs := [];
dofs := [];
for g in gens do
Add( cofs, CoefficientsByBase( base, Flat( g ) ) );
Add( dofs, CoefficientsByBase( base, Flat( g^-1 ) ) );
od;
Print("compute relevant primes \n");
pr := ConsideredPrimes( Flat( Concatenation( cofs, dofs ) ) );
# first consider p-adic case
Print("p-adic valuations \n");
t1 := 0;
for p in pr do
s := 0;
for i in [1..n] do
a := AbsInt( Minimum( List( cofs[i], x -> PadicValue(x,p) ) ) );
b := AbsInt( Minimum( List( dofs[i], x -> PadicValue(x,p) ) ) );
s := s + Maximum( a, b );
od;
t1 := Maximum( t1, s );
od;
t1 := d * t1;
Print("non-archimedian: ", t1,"\n");
# then the log-value
Print("logarithmic valuations \n");
t := Maximum( List( cof, x -> LogAbsValueBound( 1+AbsInt(x) ) ) );
t2 := 0;
for i in [1..n] do
if gens[i] = c then
t2 := t2 + t;
else
a := LogAbsValueBound( Sum( AbsInt( cofs[i] ) ) );
b := LogAbsValueBound( Sum( AbsInt( dofs[i] ) ) );
t2 := t2 + (d-1) * t + Maximum( a, b );
fi;
od;
t2 := QuoInt( 3 * 7 * d^2 * t2, 2 * LogInt(d,2) );
Print("archimedian: ", t2,"\n");
t := Maximum( t1, t2 );
return QuoInt( t^n + 1, t );
end );
#############################################################################
##
#F LogDixonBound( gens, prim )
##
BindGlobal( "LogDixonBound", function( gens, prim )
local c, f, d, base, cofs, dofs, g, t, s, i, a, b;
# set up
c := prim.elem;
f := CoefficientsOfUnivariatePolynomial( prim.poly );
d := Length( f ) - 1;
if f[1] <> 1 or f[d+1] <> 1 then return fail; fi;
# get prim-basis
# Print("compute prim-base \n");
base := List([0..d-1], x -> Flat(c^x));
base := SemiEchelonMatTransformation( base );
# get coeffs of gens in prim-base
# Print("compute coefficients \n");
cofs := [];
dofs := [];
for g in gens do
Add( cofs, CoefficientsByBase( base, Flat( g ) ) );
Add( dofs, CoefficientsByBase( base, Flat( g^-1 ) ) );
od;
# get log-value
# Print("logarithmic valuation \n");
t := Maximum( List( f, x -> LogAbsValueBound( 1+AbsInt(x) ) ) );
s := 0;
for i in [1..Length(gens)] do
if gens[i] = c then
s := s + t;
else
a := LogAbsValueBound( Sum( AbsInt( cofs[i] ) ) );
b := LogAbsValueBound( Sum( AbsInt( dofs[i] ) ) );
s := s + (d-1) * t + Maximum( a, b );
fi;
od;
# now determine final value
t := 7 * d^2 * s / QuoInt( 2 * LogInt(d,2), 3 );
return QuoInt( t^Length(gens) + 1, t );
end );
[ Dauer der Verarbeitung: 0.38 Sekunden
(vorverarbeitet)
]
|
