// 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;