Magma V2.20-8 Mon Oct 6 2014 15:38:58 on mathcompprd07 [Seed = 3201886810] Type ? for help. Type -D to quit. Loading startup file "/home/eobr007/.magma.startup" > load "code.m"; Loading "code.m" > // SetVerbose ("Classes", 1); > // SetVerbose ("RandomSchreier", 1); > // load "z.m"; > // SetEchoInput (true); > > // is vector space large enough? > CanHaveRegularOrbit := function (G) > d := Degree (G); > F := BaseRing (G); > V := VectorSpace (F, d); > o := #G; > if #V lt #G then "Vector space too small -- no regular orbit"; > return false, true; > else > return true, true; > end if; > end function; > > // determine if G has regular orbit by covering vector space > HasRegularOrbit := function (G: Limit := 1000) > d := Degree (G); > F := BaseRing (G); > V := VectorSpace (F, d); > o := #G; > if #V lt #G then "Vector space too small -- no regular orbit"; > return false, true; > end if; > > O := {}; > nmr := 0; > "Order of G is ", #G; > repeat > repeat > v := Random (V); > until not (v in O); > o := Orbit (G, v); > if #o eq #G then "Found regular orbit"; return true, true; end if; > O join:= o; > "... #O is now ", #O; > nmr +:= 1; > decided := #V - #O lt #G; > until decided or nmr gt Limit; > if decided then > "Proved no regular orbit"; return false, true; > end if; > if nmr gt Limit then > "Could not decide about regular orbit"; return false, false; > end if; > end function; > > /* find space centralised by g */ > CentralisedSpace := function (g) > G := Parent (g); > F := CoefficientRing (G); > A := MatrixAlgebra (F, Degree (G)); > a := A!g; > N := NullSpace (a - Identity (A)); > // "Nullspace has dimension ", Dimension (N); > return N; > end function; > > RefinedBound := function (G, n) > C := LMGClasses (G); > order := #G; > index := [i : i in [1..#C] | IsPrime (C[i][1]) and order mod C[i][1] eq 0]; > reps := [C[i][3]: i in index]; > sizes := [C[i][2]: i in index]; > spaces := [#CentralisedSpace (reps[i]) : i in [1..#reps]]; > size := &+[sizes[i] * spaces[i]: i in [1..#spaces]]; > p := Characteristic (BaseRing (G)); > e := Ilog (p, size); > assert p^(e + 1) ge size; > if p^e eq size then return e; else return e + 1; end if; > end function; > > Scalars := function (d, q) > F := GF (q); > nu := PrimitiveElement (F); > M := MatrixAlgebra (F, d); > s := ScalarMatrix (M, nu); > return sub; > end function; > > // H defined over GF(q); construct G = H \circ scalars of F_q > AddScalar := function (H) > F := BaseRing (H); > if #F gt 2 then > S := Scalars (Degree (H), #F); > G := sub; > return G; > else > return H; > end if; > end function; > > // L list of reps; n degree; Scalar: add scalar > // decide if rep has regular orbit > ProcessReps := function (L, n: Scalar := true) > for i in [1..#L] do > "Consider the following repn", i; > H := L[i]; > G := Scalar select AddScalar (H) else H; > > F := BaseRing (G); > p := Characteristic (F); > > "Input degree = ", Degree (G), " Defining field size = ", #F; > > // replace by absolute representation > if not IsPrime (#F) and not IsAbsolutelyIrreducible (G) then > G := AbsoluteRepresentation (G); > "Replaced G by its absolute representation"; > "New degree = ", Degree (G), "New field size = ", #F; > end if; > > // is G conjugate to group defined over smaller field? > flag, H := IsOverSmallerField (G); > if flag then > G := H; > "Conjugated G to smaller field"; > "Degree = ", Degree (G), "New field size = ", #F; > end if; > > if not IsPrime (#F) then > G := WriteOverSmallerField (G, GF(p)); > "Rewrite G over prime field -- now degree = ", Degree (G); > end if; > > o := LMGOrder (G); > "Composition Factors of G is "; > LMGCompositionFactors (G); > > if CanHaveRegularOrbit (G) then > e := RefinedBound (G, n); > "Refined bound on degree is ", e; > if Degree (G) gt e then > "Over refined degree limit -- so G has regular orbit"; > regular := true; > else > regular := HasRegularOrbit (G); > // "Has regular orbit?", regular; > end if; > end if; > "========================================"; > end for; > return true; > end function; > > n := 8; > G := Sym (n); > RandomSchreier (G); > order := #G; > Dims := [[8,14,40,64], [13,21,28,35], [13,20,21], [14,19,21]]; > Primes := [2, 3, 5, 7]; > > for i in [1..#Primes] do for> p := Primes[i]; dims := Dims[i]; for> "\n\nProcess n = ", n, "p = ", p; for> I := IrreducibleModules (G, GF (p): MaxDegree := Maximum (dims)); for> J := [x : x in I | Dimension (x) in dims]; for> L := [ActionGroup (j): j in J]; for> O := [LMGOrder (l): l in L]; for> L := [L[i]: i in [1..#L] | O[i] eq #G]; for> "Faithful reps over GF(", p, ") have dimensions:", [Degree (l): l in L], "\n"; for> f := ProcessReps (L, n); for> end for; Process n = 8 p = 2 Faithful reps over GF( 2 ) have dimensions: [ 8, 14, 40, 64 ] Consider the following repn 1 Input degree = 8 Defining field size = 2 Composition Factors of G is G | Cyclic(2) * | Alternating(8) 1 Vector space too small -- no regular orbit ======================================== Consider the following repn 2 Input degree = 14 Defining field size = 2 Composition Factors of G is G | Cyclic(2) * | Alternating(8) 1 Vector space too small -- no regular orbit ======================================== Consider the following repn 3 Input degree = 40 Defining field size = 2 Composition Factors of G is G | Cyclic(2) * | Alternating(8) 1 Refined bound on degree is 31 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 4 Input degree = 64 Defining field size = 2 Composition Factors of G is G | Cyclic(2) * | Alternating(8) 1 Refined bound on degree is 45 Over refined degree limit -- so G has regular orbit ======================================== Process n = 8 p = 3 Faithful reps over GF( 3 ) have dimensions: [ 13, 13, 21, 21, 28, 28, 35, 35 ] Consider the following repn 1 Input degree = 13 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 15 Order of G is 80640 ... #O is now 40320 ... #O is now 80640 ... #O is now 87360 ... #O is now 107520 Found regular orbit ======================================== Consider the following repn 2 Input degree = 13 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 15 Order of G is 80640 ... #O is now 40320 ... #O is now 80640 ... #O is now 90720 ... #O is now 95760 ... #O is now 115920 ... #O is now 136080 ... #O is now 176400 ... #O is now 216720 ... #O is now 257040 ... #O is now 277200 ... #O is now 297360 ... #O is now 317520 ... #O is now 357840 ... #O is now 398160 ... #O is now 418320 Found regular orbit ======================================== Consider the following repn 3 Input degree = 21 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 19 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 4 Input degree = 21 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 19 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 5 Input degree = 28 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 23 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 6 Input degree = 28 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 23 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 7 Input degree = 35 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 26 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 8 Input degree = 35 Defining field size = 3 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) 1 Refined bound on degree is 26 Over refined degree limit -- so G has regular orbit ======================================== Process n = 8 p = 5 Faithful reps over GF( 5 ) have dimensions: [ 13, 13, 20, 20, 21, 21, 21, 21 ] Consider the following repn 1 Input degree = 13 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 13 Order of G is 161280 Found regular orbit ======================================== Consider the following repn 2 Input degree = 13 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 13 Order of G is 161280 Found regular orbit ======================================== Consider the following repn 3 Input degree = 20 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 18 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 4 Input degree = 20 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 18 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 5 Input degree = 21 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 18 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 6 Input degree = 21 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 18 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 7 Input degree = 21 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 16 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 8 Input degree = 21 Defining field size = 5 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(2) * | Cyclic(2) 1 Refined bound on degree is 16 Over refined degree limit -- so G has regular orbit ======================================== Process n = 8 p = 7 Faithful reps over GF( 7 ) have dimensions: [ 14, 14, 19, 19, 21, 21 ] Consider the following repn 1 Input degree = 14 Defining field size = 7 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(3) * | Cyclic(2) 1 Refined bound on degree is 13 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 2 Input degree = 14 Defining field size = 7 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(3) * | Cyclic(2) 1 Refined bound on degree is 13 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 3 Input degree = 19 Defining field size = 7 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(3) * | Cyclic(2) 1 Refined bound on degree is 16 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 4 Input degree = 19 Defining field size = 7 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(3) * | Cyclic(2) 1 Refined bound on degree is 16 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 5 Input degree = 21 Defining field size = 7 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(3) * | Cyclic(2) 1 Refined bound on degree is 17 Over refined degree limit -- so G has regular orbit ======================================== Consider the following repn 6 Input degree = 21 Defining field size = 7 Composition Factors of G is G | Cyclic(2) * | Alternating(8) * | Cyclic(3) * | Cyclic(2) 1 Refined bound on degree is 17 Over refined degree limit -- so G has regular orbit ======================================== Total time: 20.120 seconds, Total memory usage: 93.28MB