// MAGMA procedures for // Fourier analysis on finite groups and the Lovasz theta-number of Cayley graph // by Evan DeCorte, David de Laat, and Frank Vallentin // http://arxiv.org/abs/1307.5703 // // intersecting_permutations_gurobi(n, k) // intersecting_permutations_lrs(n, k) // intersecting_transformations_gurobi(q, n, k) // // // intersecting_permutations_gurobi := procedure(n, k) filename := "intersecting_permutations_" cat IntegerToString(n) cat "_" cat IntegerToString(k) cat ".lp"; file := Open(filename, "w"); PartitionToElt := function(G, p) x := []; s := 0; for d in p do x cat:= Rotate([s+1 .. s+d], -1); s +:= d; end for; return G!x; end function; NoOfOnes := function(p) noo := 0; for i := 1 to #p do if p[i] eq 1 then noo +:= 1; end if; end for; return noo; end function; C := Partitions(n); cons := [p : p in C | NoOfOnes(p) lt k]; G := Sym(n); fprintf file, "Maximize\n a1\nSubject To\n"; for chi := 1 to #C-1 do fprintf file, "%o a%o + ", SymmetricCharacterValue(C[chi],G!1)^2, chi; end for; fprintf file, "%o a%o = %o\n", SymmetricCharacterValue(C[#C],G!1)^2, #C, #G; for x in cons do for chi := 1 to #C do val := SymmetricCharacterValue(C[chi],G!1) * SymmetricCharacterValue(C[chi],PartitionToElt(G,x)); if val ge 0 then fprintf file, "+ %o a%o ", val, chi; else fprintf file, "- %o a%o ", AbsoluteValue(val), chi; end if; end for; fprintf file, " = 0\n"; end for; fprintf file, "End\n"; delete(file); end procedure; // // // intersecting_permutations_lrs := procedure(n, k) filename := "intersecting_permutations_" cat IntegerToString(n) cat "_" cat IntegerToString(k) cat ".ine"; file := Open(filename, "w"); PartitionToElt := function(G, p) x := []; s := 0; for d in p do x cat:= Rotate([s+1 .. s+d], -1); s +:= d; end for; return G!x; end function; NoOfOnes := function(p) noo := 0; for i := 1 to #p do if p[i] eq 1 then noo +:= 1; end if; end for; return noo; end function; C := Partitions(n); cons := [p : p in C | NoOfOnes(p) lt k]; G := Sym(n); fprintf file, "H-representation\n"; fprintf file, "linearity %o ", #cons + 1; for i := 1 to #cons + 1 do fprintf file, "%o ", i; end for; fprintf file, "\n"; fprintf file, "begin %o %o integer\n", #cons+1+#C, #C+1; fprintf file, "%o ", -#G; for chi := 1 to #C do fprintf file, "%o ", SymmetricCharacterValue(C[chi],G!1)^2; end for; fprintf file, "\n"; for x in cons do fprintf file, "0 "; for chi := 1 to #C do val := SymmetricCharacterValue(C[chi],G!1) * SymmetricCharacterValue(C[chi],PartitionToElt(G,x)); fprintf file, "%o ", val, chi; end for; fprintf file, "\n"; end for; for i := 1 to #C do fprintf file, "0 "; for j := 1 to #C do if i eq j then fprintf file, "1 "; else fprintf file, "0 "; end if; end for; fprintf file, "\n"; end for; fprintf file, "end\n"; fprintf file, "lponly\n"; fprintf file, "maximize 0 1 "; for i := 1 to #C-1 do fprintf file, " 0 "; end for; fprintf file, "\n"; delete(file); end procedure; // // // intersecting_transformations_gurobi := procedure(q,n,k) filename := "intersecting_transformations" cat IntegerToString(q) cat "_" cat IntegerToString(n) cat "_" cat IntegerToString(k) cat ".lp"; file := Open(filename, "w"); M := MatrixRing(GF(q), n); G := GL(n,q); C := Classes(G); CT := CharacterTable(G); cons := []; for i := 1 to #C do c := C[i][3]; if Rank(M!c - M!G!1) gt n - k then Append(~cons, i); end if; end for; fprintf file, "Maximize\n a1\nSubject To\n"; for chi := 1 to #CT-1 do fprintf file, "%o a%o + ", (CT[chi][1])^2, chi; end for; fprintf file, "%o a%o = %o\n", (CT[#CT][1])^2, #CT, #G; for x in cons do for chi := 1 to #CT do val := CT[chi][1] * Real(ComplexField()!CT[chi][x]); if val ge 0 then fprintf file, "+ %o a%o ", val, chi; else fprintf file, "- %o a%o ", AbsoluteValue(val), chi; end if; end for; fprintf file, " = 0\n"; for chi := 1 to #CT do val := CT[chi][1] * Imaginary(ComplexField()!CT[chi][x]); if val ge 0 then fprintf file, "+ %o a%o ", val, chi; else fprintf file, "- %o a%o ", AbsoluteValue(val), chi; end if; end for; fprintf file, " = 0;\n"; end for; fprintf file, "End\n"; delete(file); end procedure;