#Copyright 1998 by Aaron Robertson
#
lprint(``):
print(`This is RES, a Maple package written by`):
print(`Aaron Robertson.`):
print(`Available for download at www.math.temple.edu/~aaron.`):
lprint(``):
print(`Please report any bugs to aaron@math.temple.edu.`):
print(`These will be acknowledge in later versions.`):
lprint(``):
print(`The main procedures are diffcheck, diffcheck5,`):
print(`diffcheck6, diffcheck7, diffcheck8, GalField3,`):
print(`GalField4, GalField5, GalField6, GalField7, GalField8,`):
print(`pryme, and col.`):
print(`For help with a specific procedure type ezra(procedure name).`):
print(`For general help type ezra().`):
lprint(``):



ezra:=proc()
if args=NULL then
print(`RES`):
print(`A Maple package for finding lower bounds for `):
print(`classical Ramsey numbers by using finite field residues.`):
print(`For help with a specific procedure, type "ezra(procedure_name);"`):
print(`Contains procedures: `):
print(`diffcheck, diffcheck5, diffcheck6, diffcheck7, diffcheck8,`):
print(`GalField4, GalField5, GalField6, GalField7, GalField8,`):
print(`pryme, and col.`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`diffcheck` then
print(`The call is diffcheck(p,m,k) where p is the prime order`):
print(`of the field, m is from the residues = {x^m : x in {1..p-1}}`):
print(`and we are trying to avoid a k-clique.`):
print(`The output is the k-clique, if found, and 0 if no k-clique`):
print(`exists in the coloring.`):
fi:

if nops([args])=1 and op(1,[args])=`diffcheck5` then
print(`The call is diffcheck5(p,m).  It is the `):
print(`same as diffcheck, except we set k=5, so that we do`):
print(`not run out of memory.`):
fi:


if nops([args])=1 and op(1,[args])=`diffcheck6` then
print(`The call is diffcheck6(p,m).  It is the `):
print(`same as diffcheck, except we set k=6, so that we do`):
print(`not run out of memory.`):
fi:

if nops([args])=1 and op(1,[args])=`diffcheck7` then
print(`The call is diffcheck7(p,m).  It is the `):
print(`same as diffcheck, except we set k=7, so that we do`):
print(`not run out of memory.`):
fi:

if nops([args])=1 and op(1,[args])=`diffcheck8` then
print(`The call is diffcheck8(p,m).  It is the `):
print(`same as diffcheck, except we set k=8, so that we do`):
print(`not run out of memory.`):
fi:

if nops([args])=1 and op(1,[args])=`pryme` then
print(`The call is pryme(U,L,m).  U is an upperbound`):
print(`and L is the lowerbound for the range or primes we`):
print(`would like to search.  m is from the residue definition`):
print(`(see diffcheck).  The output is a list of primes,p, for`):
print(`which -1 is a residue, and m divides p-1.`):
fi:


if nops([args])=1 and op(1,[args])=`col` then
print(`The call is col(p,m).  It is assumed that`):
print(`m divides p-1.  This lists the m cosets which`):
print(`define the m coloring on K_p.`):
fi:

if nops([args])=1 and op(1,[args])=`GalField3` then
print(`The call is GalField3(p,m,resnum).  The order of the`):
print(`field we are searching is p^m, and resnum is from`):
print(`the residues = {x^resnum : x in {1..p^m - 1}}`):
print(`This searches for 3-cliques, if one is found the`):
print(`output is 0, if one is not found the output is 1.`):
fi:

if nops([args])=1 and op(1,[args])=`GalField4` then
print(`Same as GalField3(p,m,resnum) except we are`):
print(`trying to avoid 4-cliques.`):
fi:


if nops([args])=1 and op(1,[args])=`GalField5` then
print(`Same as GalField4(p,m,resnum) except we are`):
print(`trying to avoid 5-cliques.`):
fi:

if nops([args])=1 and op(1,[args])=`GalField6` then
print(`Same as GalField4(p,m,resnum) except we are`):
print(`trying to avoid 6-cliques.`):
fi:

if nops([args])=1 and op(1,[args])=`GalField7` then
print(`Same as GalField4(p,m,resnum) except we are`):
print(`trying to avoid 7-cliques.`):
fi:

if nops([args])=1 and op(1,[args])=`GalField8` then
print(`Same as GalField4(p,m,resnum) except we are`):
print(`trying to avoid 8-cliques.`):
fi:

end:


##############################################################
##############################################################


#this calculates the mth residues mod p
#for quadratic residues use m=2

#this orders the residues from res2
res:=proc(p,m)
local i,A,B,b:
B:=[]:
A:=res2(p,m):
for i from 1 to nops(A) do
b:=min(op({op(A)} minus {op(B)})):
B:=[op(B),b]:
od:
B:
end:

########################################

#finds the residues = {x^m:x from {1,2,...,p-1}}
#m is the number of colors, p is the prime order of the field
res2:=proc(p,m)
local i,S,T,Q:
S:=[]:
for i from 1 to p-1 do
S:=[op(S),i^m mod p]:
od:
T:=convert(S,set):
Q:=convert(T,list):
Q:
end:

########################################

#make sure p divided m-1
#let C=residues = {x^m:x in {1,2,...,p-1}}
#then this returns the m cosets, each of which is a list of
#differences of the same color

col:=proc(p,m)
local A,i,B,b,j,k;
A[1]:=res(p,m):
for i from 2 to gcd(m,p-1)  do
B:={seq(k,k=1..p)} minus {seq(op(A[k]),k=1..i-1)}:
b:=B[1]:
  A[i]:=[]:
  for j from 1 to (p-1)/gcd(m,p-1) do
  A[i]:=[op(A[i]),b*op(j,A[1]) mod p]:
  od:
od:
[seq(A[i],i=1..gcd(m,p-1))];
end:

##########################################

#m is the number of colors
#lists all primes,p, between U and L where m divides p - 1
#and such that -1 is a residue

pryme:=proc(U,L,m)
local A,i,B,C,c:
A:=[]:
for i from U to L do
if isprime(i) then A:=[op(A),i]:fi:
od:
B:=[]:
for i from 1 to nops(A) do
if type((A[i]-1)/m,integer) then
B:=[op(B), A[i]]:
fi:
od:
B: 
C:=[]:
for i from 1 to nops(B) do
c:=B[i]:
if member(c-1,res(c,m)) then C:=[op(C),c]: fi:
od:
C:
end:


###########################################


#p is the modulo of the residue class
#m is the power is the residues:  {x^m:x in {1..p-1}}

siv:=proc(M,p)
local i,T,R,P,A:
A:=M:
T:=[]:
for i from 1 to nops(A) do
if member(p+1-A[i],A) then
T:=[op(T),A[i]]:
fi:
od:
P:=convert(T,set):
R:=convert(P,list):
R:
end:


################################################


#k is the clique size we wish to avoid, k > 2
#p is the prime order of the field
#m is the power in the residues = {x^m:x in {1..p-1}}

diffcheck:=proc(p,m,k)
local M,i,T,temp,S,R,j,z:
M:=res(p,m): 
S:=siv(M,p): 
if k=3 and nops(S)>0 then RETURN(0,[1,S[1],S[1]-1]):
elif k=3 and nops(S)=0 then RETURN(1):
else
  with(combinat,choose,numbcomb):
  T:=choose(S,k-2):
  for i from 1 to nops(T) do
    R:=choose(T[i],2):
    z:=0:
    for j from 1 to nops(R) do
      temp:=abs(op(2,R[j])-op(1,R[j])):
      if member(temp,M) then z:=z+1: fi:
    od:
    if z=numbcomb(k-2,2) then RETURN(0,T[i]): fi:
  od:
1:
fi:
end:

##########################################


#this diffcheck for longer list, where maple will run out of memory 
#finding all combinations
#this one is for k=5

diffcheck5:=proc(p,m)
local M,temp,S,R,j,z,a,b,c,d,e,test,n:
M:=res(p,m):
S:=siv(M,p): 
n:=nops(S):
with(combinat,choose):
for a from 1 to n-2 do
 for b from a+1 to n-1 do
  for c from b+1 to n do
    test:=[S[a],S[b],S[c]]:
    R:=choose(test,2):
    z:=0:
      for j from 1 to 3 do
        temp:=abs(op(2,R[j])-op(1,R[j])):
        if member(temp,M) then z:=z+1:
        else j:=3:
        fi:
      od:
    if z=3 then RETURN(0,test): fi:
od:od:od:
1:
end:

###############################################

#this diffcheck for longer list, where maple will run out of memory 
#finding all combinations
#this one is for k=6

diffcheck6:=proc(p,m)
local M,temp,S,R,j,z,a,b,c,d,e,test,n:
M:=res(p,m):
S:=siv(M,p): 
n:=nops(S):
with(combinat,choose):
for a from 1 to n-3 do
 for b from a+1 to n-2 do
  for c from b+1 to n-1 do
   for d from c+1 to n do
    test:=[S[a],S[b],S[c],S[d]]:
    R:=choose(test,2):
    z:=0:
      for j from 1 to 6 do
        temp:=abs(op(2,R[j])-op(1,R[j])):
        if member(temp,M) then z:=z+1:
        else j:=6:
        fi:
      od:
    if z=6 then RETURN(0,test): fi:
od:od:od:od:
1:
end:

###############################################


diffcheck7:=proc(p,m)
local V,M,temp,a,b,c,n,d,e,f,test,R,z,j:
with(combinat,choose):
M:=res(p,m):
V:=siv(M,p):
n:=nops(V): 
for a from 1 to n-4 do
  for b from a+1 to n-3 do
    for c from b+1 to n-2 do
      for d from c+1 to n-1 do
        for e from d+1 to n do
     test:=[V[a],V[b],V[c],V[d],V[e]]:
     R:=choose(test,2):
     z:=0:
     for j from 1 to 10 do
     temp:=abs(op(2,R[j])-op(1,R[j])):
     if member(temp,M) then z:=z+1:  
     else j:=10:
     fi:
     od: 
       if z=10 then RETURN(test):fi:
od:od:od:od:od:
1:
end: 

################################################

diffcheck8:=proc(p,m)
local V,M,temp,a,b,c,n,d,e,f,test,R,z,j:
with(combinat,choose):
M:=res(p,m):
V:=siv(M,p):
n:=nops(V): 
for a from 1 to n-5 do
  for b from a+1 to n-4 do
    for c from b+1 to n-3 do
      for d from c+1 to n-2 do
        for e from d+1 to n-1 do
          for f from e+1 to n do
     test:=[V[a],V[b],V[c],V[d],V[e],V[f]]:
     R:=choose(test,2):
     z:=0:
     for j from 1 to 15 do
     temp:=abs(op(2,R[j])-op(1,R[j])):
     if member(temp,M) then z:=z+1:  
     else j:=15:
     fi:
     od: 
       if z=15 then RETURN(test):fi:
od:od:od:od:od:od:
1:
end:


################################################

#p must be prime, m is the exponent--->order of the field is p^m
#resnum is the power of the residue class we want, eg 3=cubic
#we are trying to avoid 3-cliques

GalField3:=proc(p,m,resnum)

local a,b,c,d,e,f,G,x,i,y,Q,C,r,d1,d2,d3,tmp,T,n,tmp2,R,z,test,j,temp:

readlib(GF):
G:=GF(p,m):

Q:={}:
for i from 1 to p^m do
  y[i]:=G[input](i):
  Q:=Q union {G[`^`](y[i],resnum)}:
od:

if not(member(G[`-`](0,1),Q)) then RETURN(`-1 must be a residue`):fi:

#we siv out to make sure if R is a residue, so is R-1 in the field
T:={}:
for i from 1 to nops(Q) do
  if member(G[`-`](Q[i],1),Q) then
  T:=T union {Q[i]}:
  fi:
od:
n:=nops(T):
if n=0 then RETURN(1):
else RETURN(0):
fi:

end: 

################################################

#p must be prime, m is the exponent--->order of the field is p^m
#resnum is the power of the residue class we want, eg 3=cubic
#we are trying to avoid 4-cliques

GalField4:=proc(p,m,resnum)

local a,b,c,d,e,f,G,x,i,y,Q,C,r,d1,d2,d3,tmp,T,n,tmp2,R,z,test,j,temp:

readlib(GF):
G:=GF(p,m):

Q:={}:
for i from 1 to p^m do
  y[i]:=G[input](i):
  Q:=Q union {G[`^`](y[i],resnum)}:
od:

if not(member(G[`-`](0,1),Q)) then RETURN(`-1 must be a residue`):fi:

#we siv out to make sure if R is a residue, so is R-1 in the field
T:={}:
for i from 1 to nops(Q) do
  if member(G[`-`](Q[i],1),Q) then
  T:=T union {Q[i]}:
  fi:
od:
n:=nops(T):
with(combinat,choose):
for a from 1 to n-1 do
 for b from a+1 to n do

    test:=[T[a],T[b]]:
        temp:=G[`-`](op(2,test),op(1,test)):
        if member(temp,Q) then  RETURN(0): fi:
od:od:
1:
end:


##########################################

#p must be prime, m is the exponent--->order of the field is p^m
#resnum is the power of the residue class we want, eg {x^resnum:x in {1..p^m}}
#5 is the clique size we wish to avoid

GalField5:=proc(p,m,resnum)

local a,b,c,d,e,f,G,x,i,y,Q,C,r,d1,d2,d3,tmp,T,n,tmp2,R,z,test,j,temp:

readlib(GF):
G:=GF(p,m,polie):

Q:={}:
for i from 1 to p^m do
  y[i]:=G[input](i):
  Q:=Q union {G[`^`](y[i],resnum)}:
od:

if not(member(G[`-`](0,1),Q)) then RETURN(`-1 must be a residue`):fi:

#we siv out to make sure if R is a residue, so is R-1 in the field
T:={}:
for i from 1 to nops(Q) do
  if member(G[`-`](Q[i],1),Q) then
  T:=T union {Q[i]}:
  fi:
od:
n:=nops(T):
with(combinat,choose):
for a from 1 to n-2 do
 for b from a+1 to n-1 do
  for c from b+1 to n do

    test:=[T[a],T[b],T[c]]:
    R:=choose(test,2):
    z:=0:
      for j from 1 to 3 do
        temp:=G[`-`](op(2,R[j]),op(1,R[j])):
        if member(temp,Q) then z:=z+1:
        else j:=3:
        fi:
      od:
    if z=3 then RETURN(0): fi:
od:od:od:  
1:
end:


#################################################


#p must be prime, m is the exponent--->order of the field is p^m
#resnum is the power of the residue class we want, eg {x^resnum:x in {1..p^m}}
#6 is the clique size we wish to avoid

GalField6:=proc(p,m,resnum)

local a,b,c,d,e,f,G,x,i,y,Q,C,r,d1,d2,d3,tmp,T,n,tmp2,R,z,test,j,temp:

readlib(GF):
G:=GF(p,m,polie):

Q:={}:
for i from 1 to p^m do
  y[i]:=G[input](i):
  Q:=Q union {G[`^`](y[i],resnum)}:
od:

if not(member(G[`-`](0,1),Q)) then RETURN(`-1 must be a residue`):fi:

#we siv out to make sure if R is a residue, so is R-1 in the field
T:={}:
for i from 1 to nops(Q) do
  if member(G[`-`](Q[i],1),Q) then
  T:=T union {Q[i]}:
  fi:
od:
n:=nops(T):
with(combinat,choose):
for a from 1 to n-3 do
 for b from a+1 to n-2 do
  for c from b+1 to n-1 do
   for d from c+1 to n do

    test:=[T[a],T[b],T[c],T[d]]:
    R:=choose(test,2):
    z:=0:
      for j from 1 to 6 do
        temp:=G[`-`](op(2,R[j]),op(1,R[j])):
        if member(temp,Q) then z:=z+1:
        else j:=6:
        fi:
      od:
    if z=6 then RETURN(0): fi:
od:od:od:od:  
1:
end:


#################################################

#p must be prime, m is the exponent
#Hence the field is of order p^m

#resnum is the power of the residue class we want, eg 3=cubic
#7 is the clique size we wish to avoid

GalField7:=proc(p,m,resnum)

local a,b,c,d,e,f,G,x,i,y,Q,C,r,d1,d2,d3,tmp,T,n,tmp2,R,z,test,j,temp:
readlib(GF):
G:=GF(p,m):

Q:={}:
for i from 1 to p^m do
  y[i]:=G[input](i):
  Q:=Q union {G[`^`](y[i],resnum)}:
od:

#we siv out to make sure if R is a residue, so is R-1 in the field
T:={}:
for i from 1 to nops(Q) do
  if member(G[`-`](Q[i],1),Q) then
  T:=T union {Q[i]}:
  fi:
od:
n:=nops(T):
with(combinat,choose):
for a from 1 to n-4 do
 for b from a+1 to n-3 do
  for c from b+1 to n-2 do
   for d from c+1 to n-1 do
     for e from d+1 to n do
    test:=[T[a],T[b],T[c],T[d],T[e]]:
    R:=choose(test,2):
    z:=0:
      for j from 1 to 10 do
        temp:=G[`-`](op(2,R[j]),op(1,R[j])):
        if member(temp,Q) then z:=z+1:
        else j:=10:
        fi:
      od:
    if z=10 then RETURN(0): fi:
od:od:od:od:od:   
1:
end:



#p must be prime, m is the exponent
#Hence the field is of order p^m

#resnum is the power of the residue class we want, eg 3=cubic
#8 is the clique size we wish to avoid

GalField8:=proc(p,m,resnum)

local a,b,c,d,e,f,G,x,i,y,Q,C,r,d1,d2,d3,tmp,T,n,tmp2,R,z,test,j,temp:
readlib(GF):
G:=GF(p,m):

Q:={}:
for i from 1 to p^m do
  y[i]:=G[input](i):
  Q:=Q union {G[`^`](y[i],resnum)}:
od:

#we siv out to make sure if R is a residue, so is R-1 in the field
T:={}:
for i from 1 to nops(Q) do
  if member(G[`-`](Q[i],1),Q) then
  T:=T union {Q[i]}:
  fi:
od:
n:=nops(T):
with(combinat,choose):
for a from 1 to n-5 do
 for b from a+1 to n-4 do
  for c from b+1 to n-3 do
   for d from c+1 to n-2 do
     for e from d+1 to n-1 do
       for f from e+1 to n do
    test:=[T[a],T[b],T[c],T[d],T[e],T[f]]:
    R:=choose(test,2):
    z:=0:
      for j from 1 to 15 do
        temp:=G[`-`](op(2,R[j]),op(1,R[j])):
        if member(temp,Q) then z:=z+1:
        else j:=15:
        fi:
      od:
    if z=15 then RETURN(0): fi:
od:od:od:od:od:od:   
1:
end:

#################################################