Searching for incidence structures in certain nonAbelian groups with MAGMA

The following code searches for incidence structures in the nonAbelian groups \(\mathbb{F}_{p^{2}}\times H\) where \(H\) is the integers modulo \(p+1\). We first define several functions.

 Bin_op:=function(p,x,y)   //defines a binary operation on a cartesian product
    return <x[1]+y[1]^(p^(Integers() ! y[2])),x[2]+y[2]>;
end function;

Op_inv:=function(p,x)    //defines the inverse wrt above binary operation
    return <(-x[1])^(p^(Integers() ! -x[2])),-x[2]>;
end function;

nPow:=function(a,n,p)   //defines nth power wrt above binary operation
    i:=0;
    x:=a;
    while i lt n+1 do
        x:=Bin_op(p,x,a);
        i:=i+1;
    end while;
    return x;
end function;

Trans_bin:=function(A,p,x)  //creates translation by x of set of elements wrt above binary op
    X:={};
    for a in A do
        Include(~X,Bin_op(p,x,a));
    end for;
    return X;
end function;

Build_S:=function(G,p,s)   //builds set of elements of form <h,0> where h is in GF(p,s)
    H:=Set(GF(p,s));
    X:={G|};
    for h in H do
        Include(~X,<h,0>);
    end for;
    return X;
end function;

Build_splint:=function(p,W)  //builds set of 1-dim subgroups of W
    X:={@ @};
    for w in W diff {<0,0>} do
        Y:={w};
        for i in {0..p-1} do
            Include(~Y,nPow(w,i,p));
        end for;
        Include(~X,Y);
    end for;
    return X;
end function;

Build_flesh:=function(p,A)   //collects members of form x*y where x,y are in A and puts them in a set
    X:=A;
    for x,y in X do
        Include(~X,Bin_op(p,x,y));
    end for;
    return X;
end function;

fleshPow:=function(p,A,n)   //builds subgroup generated by members of A
    i:=0;
    X:=A;
    while i lt n+1 do
        X:=Build_flesh(p,X);
        i:=i+1;
    end while;
    return X;
end function;

Build_splint0:=function(p,W,k)  //builds set of subgroups of W of order p^k
    X:={@ @};
    for A in Subsets(W diff {<0,0<},k) do
        Y:=A;
        while # Y lt # Build_flesh(p,Y) do
            Y:=Build_flesh(p,Y);
        end while;
        if # Y eq p^k then
            Include(~X,Y);
        end if;
    end for;
    return X;
end function;

Build_cos_reps:=function(G,Subgrp,p)  //builds set of coset reps of a subgroup of G
    X:={};
    Y:={};
    for g in G do
        W:={};
        for g1 in Subgrp do
            Include(~W,Bin_op(p,g,g1));
        end for;
        if W notin X then
            Include(~X,W);
            Include(~Y,g);
        end if;
    end for;
    return SetToIndexedSet(Y);
end function;

Build_diff:=function(G,p,s)   //builds incidence structure which is union of differences of subgroups of G
    S:=Build_S(G,p,s);
    Spl:=Build_splint0(p,S,s-1);
    X:=Build_cos_reps(G,S,p);
    Y:={};
    for i in {1..# X} do
        Y:=Y join Trans_bin(S diff Spl[i],p,X[i]);
    end for;
    return Y;
end function;

Build_diff0:=function(G,p,s,W,m)  //variation of above union
    S:=Build_S(G,p,s);
    Spl:=W;
    X:=Build_cos_reps(G,S,p);
    Y:={};
    for i in {1..m} do
        Y:=Y join Trans_bin(S diff Spl[i],p,X[i]);
    end for;
    for i in {m+1..# X} do
        Y:=Y join Trans_bin(Spl[i],p,X[i]);
    end for;
    return Y;
end function;


Multi:=function(p,G,U)   //builds multiset {u1-u2 | u1,u2 are in U and u1 not equal to u2}
    X:={* *};
    for u1,u2 in U do
        if u1 ne u2 then
            Include(~X,Bin_op(p,u1,Op_inv(p,u2)));
        end if;
    end for;
    return X;
end function;

Check_multi:=function(p,G,U)  //checks multiplicites of members of multiset and puts them into a set
    X:={};
    for g in G diff {G ! <0,0<} do
        Include(~X,Multiplicity(Multi(p,G,U),g));
    end for;
    return X;
end function;

Check_multi0:=function(p,G,U)  //variation of above function that keeps track of whether the cayley graph is an srg
    X:={};
    Y:={};
    for u in U do
        Include(~X,Multiplicity(Multi(p,G,U),u));
    end for;
    for u in Set(G) diff (U join {<0,0<}) do
        Include(~Y,Multiplicity(Multi(p,G,U),u)); 
    end for;
    return [* X, Y *];
end function;

Here we check whether the set union obtained with \(p=7\) and \(s=2\) is a difference set.

 p:=7;   //finds almost differecne set in the nonabelian group G=GF(p,s)xC where C is integers modulo p+1
s:=2;
H1:=Set(GF(p,s));
r:=(p^s-1)/(p-1);
r:=Integers() ! r;
H2:=Set(Integers(r));
G:=Set(CartesianProduct(H1,H2));
S:=Build_S(G,p,s);
Spl:=Build_splint0(p,S,s-1);
X:=Build_cos_reps(G,S,p);
for m in {5..# X} do
U:=Build_diff0(G,p,s,Spl,m);
print "m=",m;
Check_multi(p,G,U);
end for;

Searching for 1 1/2 designs in cyclic codes with MAGMA

Here we try to find 1 1/2-designs in cyclic codes. 1 1/2-designs are interesting since they correspond to directed strongly regular graphs.

 D := function(d,p,n)        //creates set of dth power residues in GF(p,n)
    x := PrimitiveElement(GF(p,n))^d;
    DD := {GF(p,n)|};
    for i in {0..p^n-1} do
        Include(~DD,x^i);
    end for;
    return DD;
end function;
Di := function(d,p,n,i)     //creates ith class of dth power residues in GF(p,n)
    x := PrimitiveElement(GF(p,n))^i;
    return {GF(p,n)|x*a:a in D(d,p,n)};
end function;

C_union := function(A,d,p,n)  //creates union of cyclotomic classes over set A of indices
    X := {};
    for i in A do
        X := X join Di(d,p,n,i);
    end for;
    return X;
end function;

cTrans:=function(C,i)   //creates additive translate of union by i of dth power power residues
    X:={};
    for c in C do
        Include(~X,c+i);
    end for;
    return X;
end function;

CycBuild:=function(D,N,k,q)  //builds cyclic code of length N with D as defining set
    G:=ZeroMatrix(GF(q),k,N);
    for i in {1..k} do
        for j in {1..N} do
            if j-1 in cTrans(D,i-1,N) then
                G[i,j]:=1;
            else
                G[i,j]:=0;
            end if;
        end for;
    end for;
    return G;
end function;

ZeroCols:=function(G)   //creates set of zero columns of matrix
    X:={};
    for j in {1..NumberOfColumns(G)} do
        if Transpose(G)[j] eq ZeroMatrix(GF(2),1,NumberOfRows(G)) then
            Include(~X,j);
        end if;
    end for;
    return # X;
end function;

Build_supps:=function(C,l)   //collects supports of words in code into set
    X:={};
    for c in Words(C,l) do
        Include(~X,Support(c));
    end for;
    return X;
end function;

Check_ades:=function(b0,B,t); //check replication number of incidence structure
    X:={};
    for Y in Subsets(b0,t) do
        Z:={};
        for b in B do
            if Y subset b then
                Include(~Z,b);
            end if;
        end for;
        Include(~X,# Z);
    end for;
    return X;
end function;

Check_112:=function(F,B)  //checks whether incidence structure is a 1 1/2 design
    U:={};
    V:={};
    for x in F do
        for b in B do
            X:={};
            Y:={};
            for y in (b diff {x}) do
                for c in (B diff {b}) do
                    if y in c and x in c then
                        if x in b then
                            Include(~X,);
                        else
                            Include(~Y,);
                        end if;
                    end if;
                end for;
            end for;
            if x in b then
                Include(~U,# X);
            else
                Include(~V,# Y);
            end if;
        end for;
    end for;
    return [* U, V *];
end function;\

Here we carry out a search.

 d:=2;           //searches for 1 1/2 designs in codes
n:=1;
q:=2;
for p in {5..201} do
    if IsPrime(p) then
        if p^n mod d eq 1 then
            G:=Set(GF(p,n));
            for A in Subsets({0..d-1},1) do
                for k in {p} do
                    C:=LinearCode(CycBuild(C_union(A,d,p,n),p,k,q));
                    for l in {3..p} do
                        B:=Build_supps(C,l);
                        if B ne {} then
                            if # Check_112(G,B)[1] eq 1 and # Check_112(G,B)[2] eq 1 and {Check_112(G,B)[1],Check_112(G,B)[2]} ne {{0},{0}} then
                                print C,A,p,k,l,Check_112(G,B),Check_ades(G,B,1),Check_ades(G,B,2),ZeroCols(CycBuild(C_union(A,d,p,n),p,k,q));
                            end if;
                        end if;
                    end for;
                end for;
            end for;
        end if;
    end if;
end for;

Searching for symmetric incidence structures in finite fields with MAGMA

Here we write MAGMA code to search for difference sets and almost difference sets in finite fields. We begin by creating several functions.

 
D := function(d,p,n)                    //creates set of dth power residues in GF(p,n)
    x := PrimitiveElement(GF(p,n))^d;
    DD := {GF(p,n)|};
    for i in {0..p^n-1} do
        Include(~DD,x^i);
    end for;
    return DD;
end function;
Di := function(d,p,n,i)             //creates set ith class of dth power residues in GF(p,n)
    x := PrimitiveElement(GF(p,n))^i;
    return {GF(p,n)|x*a:a in D(d,p,n)};
end function;
C_union := function(A,d,p,n)            //creates union of cyclotomic classes over set A of indices
    X := {};
    for i in A do
        X := X join Di(d,p,n,i);
    end for;
    return X;
end function;
C_un_plus := function(A,d,p,n,w1)       //creates additive translate of union by w1 of dth power power residues
    X := {};
    for x in C_union(A,d,p,n) do
        Include(~X,x + w1);
    end for;
    return X;
end function;
C_C_un_plus := function(A,d,p,n,w1)   //returns intersection of union of classes with additive translate of union
    return C_union(A,d,p,n) meet C_un_plus(A,d,p,n,w1);
end function;
All_d_C := function(A,d,p,n)      //collects all intersection sizes into set and returns the set       
    Z := {};
    for w1 in GF(p,n) do
        Include(~Z,# C_C_un_plus(A,d,p,n,w1));
    end for;
    return Z;
end function;end function;

And here we carry out some searches.

 d:=6;
for n in {3} do   //searching in GF(7,3) for almost difference sets by taking unions of 6th power residues
for p in {7} do
    if IsPrime(p) then
        if p^n mod 6 eq 1 then    
            for A in Subsets({0..d-1}) do
                if # All_d_C(A,d,p,n) lt 10 then
                    print A,d,p,n,All_d_C(A,d,p,n);
                end if;
            end for;
        end if;
    end if;
end for;
end for;

d:=4;
n:=3;
for p in {5..101} do
    if IsPrime(p) then
        if p^n mod 4 eq 1 then    
            for A in Subsets({0,2},2) do
                if # All_d_C(A,d,p,n) eq 3 then
                    print A,d,p,n,All_d_C(A,d,p,n);
                end if;
            end for;
        end if;
    end if;
end for;