#OK to post homework
#GLORIA LIU, Feb 4 2024, Assignment 5

#=====================================#
#1. Read and understand Chapter 2 of Hill's book. Do human exercises 2.1,2.2,2.3,2.4

#2.1
#(6,2,6) -> {(0 0 0 0 0 0), (1 1 1 1 1 1)}
#(3,8,1) -> {(0 0 0), (1 0 0), (0 1 0), (0 0 1), (0 1 1), (1 0 1), (1 1 0), (1 1 1)}
#(4,8,2) -> {(0 0 0 1), (0 0 1 0), (0 1 0 0), (0 1 1 1), (1 0 0 0), (1 0 1 1), (1 1 0 1), (1 1 1 0)}
#(5,3,4) -> Not possible, use the Plotkin bound from #7. 2*floor(4/(2*4-5)) = 2
#(8,30,3) -> Not possible, use the Sphere packing bound. The max number of codes with n=8 and d=3 is 28

#2.2
#We can isolate any of the n digits, and remove that digit from the code to form the new binary (n-1, M', d) code. 
#We can take all of the codes, which had its removed digit set to either 0 or 1 (either there are at least M/2 codes with the removed digit set to 0, or at least M/2 codes with the removed digit set to 1).
#In addition, the Hamming difference between the remaining codes have to be at least d, because the removed digit (which would have been the same value for all of them) would not have counted towards the Hamming distance calculated in the original code.
#A2(n,d) <= 2*A2(n-1,d) follows from the fact that we can always create a (n-1, M/2, d) code from a (n, M, d) code. 

#2.3
#Aq(3,2)=q^2.
#A q-ary (3, M, 2) code must have M <= q^2. Say one of the codes is (a,b,c). Then, no other code can have a code with a and b in the first two digits. So this eliminates q-1 possible codes. 
#We can repeat this for all q^2 pairs of possible values for the first two digits. So we can eliminate q^2(q-1) codes, and given that there are q^3 codes in total, we are left with q^2 codes. 
#In addition, we can be sure the codes we are eliminating in this way don't overlap because their first two digits will not be the same. 
#There exists a q-ary (3, M, 2) code with M = q^2, for example, the first two digits are all the possible pairs of values from 1 to q. So, the distance between the codes so far is at least 1. 
#Then, the third digit we can set to be 

#2.4
#En is the set of all vectors in (f2)^n that have even weight, and is obtained by adding an overall parity check to the code (F2)^(n-1).
#There are (|(f2)^n|)/2 = 2^(n-1) even weight vectors in (f2)^n. Adding a partiy check to any vector in (F2)^(n-1) creates an even weight vector in ((f2)^n)/2. So, doing this parity check to the code creates |(F2)^(n-1)| = 2^(n-1) even weight vectors in (f2)^n; the two sets are equal. 
#En is an (n, 2^(n-1), 2) code. Clearly, there are 2^(n-1) elements and each vector has length n.
#The distance between any two vectors is at least 2, as there is at least one digit difference in the non-parity check digits. In addition, if between two vectors there was only one digit of difference in the non-parity check digits, then the parity check digit would be different.

#=====================================#
#2. Read and understand Chapters 3 and 4 of Hill's book. Most people should be familar with this material from abstract algebra and linear algebra classes (note that the linear algebra is the same, but over a finite field)

#Done

#=====================================#
#3. Use GRC(q,n,d) with q=2, d=3,5,7, and 5 ≤ n ≤20, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

Fqn:=proc(q,n) local S,a,v:
option rembmer:
if n = 0 then
 RETURN({[]})
fi:
S:=Fqn(q,n-1):
{seq(seq([op(v),a], a=0..q-1), v in S)}
end:

Nei:=proc(q,c) local n,i,a:
n:=nops(c):
{seq(seq([op(1..i-1,c),a,op(i+1..n,c)], a=0..q-1), i=1..n)}:
end:

SP:=proc(q,c,t) local S,s,i:
S:={c}:
for i from 1 to t do
 S:=S union {seq(op(Nei(q,s)),s in S)}:
od:
S:
end:

GRC:=proc(q,n,d) local S,A,v:
A:=Fqn(q,n):
S:={}:
while A<>{} do:
 v:=A[1]:
 S:=S union {v}:
 A:=A minus SP(q,v,d-1):
od:
S:
end:

SPB:=proc(q,n,t) local i:
trunc(q^n/add(binomial(n,i)*(q-1)^i,i=0..t)):
end:

A2GRC := Array(1..3, 5..20, []):
A2SPB := Array(1..3, 5..20, []):
A2Diff := Array(1..3, 5..20, []):
for d from 1 to 3 do
 d1:=2*d+1:
 #Takes a long time
 for n from 5 to 20 do
  GRC(2,n,d1);
  A2GRC[d,n]:=nops(GRC(2,n,d1)):
  A2SPB[d,n]:=SPB(2,n,d):
  A2Diff[d,n]:=A2SPB[d,n]-A2GRC[d,n]:
 od:
od:

A2GRC;
A2SPB;
A2Diff;

#=====================================#
#4. Use GRC(q,n,d) with q=3, d=3,5,7, and 5 ≤ n ≤10, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

A3GRC := Array(1..3, 5..10, []):
A3SPB := Array(1..3, 5..10, []):
A3Diff := Array(1..3, 5..10, []):
for d from 1 to 3 do
 d1:=2*d+1:
 for n from 5 to 10 do
  A3GRC[d,n]:=nops(GRC(3,n,d1)):
  A3SPB[d,n]:=SPB(3,n,d):
  A3Diff[d,n]:=A3SPB[d,n]-A3GRC[d,n]:
 od:
od:

A3GRC;
A3SPB;
A3Diff;

#=====================================#
#5. USe GRC(q,n,d) with q=5, d=3,5,7, and 5 ≤ n ≤7, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

A5GRC := Array(1..3, 5..7, []):
A5SPB := Array(1..3, 5..7, []):
A5Diff := Array(1..3, 5..7, []):
for d from 1 to 3 do
 d1:=2*d+1:
 for n from 5 to 7 do
  A5GRC[d,n]:=nops(GRC(5,n,d1)):
  A5SPB[d,n]:=SPB(5,n,d):
  A5Diff[d,n]:=A5SPB[d,n]-A5GRC[d,n]:
 od:
od:

A5GRC;
A5SPB;
A5Diff;

#=====================================#
#6. Write a procedure ParaBD(BD,v), that inputs a potential block design with v varieties (or points) (i.e. the universal set is {1, ..., v}) and checks whether it is indeed a block design (if it is not it should return FAIL).

#I implemented this before seeing the hint so it is probably less efficient >. .<

ParaBD:=proc(BD,v) local points, pairs, size, c, k, m, smallerIndex, largerIndex:
points:=[0$v]:
pairs:=Array(1..v, 1..v, []):
size:=nops(BD[1]):
for c from 1 to nops(BD) do
 if nops(BD[c]) <> size then
  RETURN(FAIL):
 fi:
 for k from 1 to size do
  points[BD[c,k]]:=points[BD[c,k]] + 1:
  for m from k to size do
   smallerIndex:= min(BD[c,k], BD[c,m]):
   largerIndex:= max(BD[c,k], BD[c,m]):
   pairs[smallerIndex, largerIndex]:=pairs[smallerIndex, largerIndex] + 1:
  od:
 od:
od:
print(points);
print(pairs);
for k from 1 to v do
 if points[k] <> points[1] then
  RETURN(FAIL):
 fi:
od:
for k from 1 to v do
 for m from k+1 to v do
  if pairs[k,m] <> pairs[1,2] then
   RETURN(FAIL):
  fi:
 od:
od:
[nops(BD), v, size, points[1], pairs[1,2]]:
end:

BDfano:=proc():
{{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}:
end:

BDex212:=proc():
{{1,3,4,5,9},
{2,4,5,6,10},
{3,5,6,7,11},
{1,4,6,7,8},
{2,5,7,8,9},
{3,6,8,9,10},
{4,7,9,10,11},
{1,5,8,10,11},
{1,2,6,9,11},
{1,2,3,7,10},
{2,3,4,8,11}
}
end:

ParaBD(BDfano(),7);
ParaBD(BDex212(),11);

#=====================================#
#7. Using Ex. 2.21 (p. 29) write a procedure
#PlotkinBound(n,d)
#For binary codes. For all d from 2 to 20 and n from 2 to 2d find which is bigger, the Sphere-Packing bound or the Plotkin bound?

PlotkinBound:=proc(n,d) local a:
a:=2*floor(d/(2*d - n)):
a:
end:

#Table stores difference of sphere-packing bound and Plotkin bound, values are negative if Plotkin bound is larger
list1 := []:
for d from 2 to 20 do
 list1:=[op(list1), [0$(2*d)-2]]
od:

for d from 2 to 20 do
 for n from 2 to 2*d-1 do
  #print(PlotkinBound(n,d));
  list1[d-1,n-1]:=SPB(2,n,floor((d-1)/2)) - PlotkinBound(n,d):
 od:
od:

list1;

#=====================================#
#8. Search the internet for other examples of block designs (or the special case, projective plane) given explictly as a collection of subests of {1, ..., n} for some n (like BDfano() and BDex212()), and use BDtoC(BD,n) to come up with interesting codes.

#Skipped