#OK to post homework 
#Natalya Ter-Saakov, Feb 4, 2024, Assignment 5
read "C5.txt":

#from Robert, a faster GRC

GRCrdb:=proc(q,n,d) local S,A,v,sp,sphere:
A:=MutableSet(Fqn(q,n)):
S:={}:
sphere := SP(q, [0 $ n], d - 1):
while not empty(A) do
 v:=A[1]:
 S:=S union {v}:
 sp := map(x -> (x + v) mod q, sphere):
 A &minus MutableSet(sp):
od:
S:
end:

#Problem 1
#2.1
#(6,2,6): {(0,0,0,0,0,0),(1,1,1,1,1,1)}
#(3,8,1): all of {0,1}^3
#(4,8,2): all of {0,1}^3 with a final parity bit
#(5,3,4): Impossible! There are 6 code words at distance at least 4 from (0,0,0,0,0) and all of them are within distance 2 of each other.
#(8,30,3): Impossible! To have a code of distance 3, every word must have a sphere of radius 1 surrounding it. Those spheres have 9 elements in them, so there must be at least 30*9 = 270 possible words on length 8. However, there are only 2^8=256 words. 

#2.2
#For a (n,M,d) code, consider the last element over all the words. WLOG assume there are more 1s than 0s. Take all the words that end in 1 and remove the last element. These will be words of length n and min distance d and there will be at least M/2 of them. 
#Thus A_2(n-1,d)<=2A_2(n,d).

#2.3 
#Let us first demonstrate that a code of q^2 words exists. Consider all words that sum to 0 mod q. There are q^2 of them. The better way to think about this is to imagine them as elements of F_q^2 with a last bit that makes the sum work out. As below, we know that two such words cannot be distance 1 apart because then one of the sums cannot be 0.
#Now we must show that there cannot be a larger code. Consider a maximal code and two words that disagree in the last bit (if no words disagree in the last bit, then we already have no more than q^2 words). Deleting the last bit from every word cannot create a collision since the minimum distance is 2. Thus, we get at most q^2 distinct words, so the maximal code is at most q^2 words.

#2.4
#Let E_n be the set of all vectors in F_2^n with even weight. This is a set of 2^(n-1) vectors. Note that adding a parity bit to the end of a vector in F_2^(n-1) ensures even weight. Thus, since this makes all 2^(n-1) vectors, that is what E_n is. 
#All that remains is to show that the vectors have distance at least 2. Suppose not. These vectors cannot differ in the last bit as the parity of the remainder would be the same. They also cannot differ in an earlier bit as the parity would then be different.

#Problem 3
#[seq(nops(GRCrdb(2,n,3)),n=5..20)];
#[4, 8, 16, 16, 32, 64, 128, 256, 512, 1024, 2048, 2048, 4096, 8192, 16384, 32768]
#Sphere Bounds:
#[5, 9, 16, 28, 51, 93, 170, 315, 585, 1092, 2048, 3855, 7281, 13797, 26214, 49932]

#[seq(nops(GRCrdb(2,n,5)),n=5..20)];
#[2, 2, 2, 4, 4, 8, 16, 16, 32, 64, 128, 256, 512, 512, 1024, 2048]
#Sphere Bounds: 
#[2, 2, 4, 6, 11, 18, 30, 51, 89, 154, 270, 478, 851, 1524, 2744, 4969]

#[seq(nops(GRCrdb(2,n,7)),n=5..20)];
#[1, 1, 2, 2, 2, 2, 4, 4, 8, 16, 32, 32, 64, 128, 256, 512]
#Sphere Bounds:
#[1, 1, 2, 2, 3, 5, 8, 13, 21, 34, 56, 94, 157, 265, 451, 776]

#Problem 4
#[seq(nops(GRCrdb(3,n,3)),n=5..10)];
#[9, 24, 72, 198, 519, 1390]
#Sphere Bounds:
#[22, 56, 145, 385, 1035, 2811]

#[seq(nops(GRCrdb(3,n,5)),n=5..10)];
#[3, 3, 8, 18, 39, 83]
#Sphere Bounds:
#[4, 9, 22, 50, 120, 293]

#[seq(nops(GRCrdb(3,n,7)),n=5..10)];
#[1, 1, 3, 3, 3, 9]
#Sphere Bounds:
#[1, 3, 5, 11, 23, 50]

#Problem 5
#[seq(nops(GRCrdb(5,n,3)),n=5..7)];
#[74, 265, 1113]
#Sphere Bounds:
#[148, 625, 2693]

#[seq(nops(GRCrdb(5,n,5)),n=5..7)]
#[5, 13, 39]
#Sphere Bounds:
#[17, 58, 214]

#[seq(nops(GRCrdb(5,n,7)),n=5..7)]
#[1, 1, 5]
#Sphere Bounds:
#[3, 10, 29]

#Problem 6
#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). If it is the output should be the 5-tuple [b,v,r,k,lambda].
ParaBD:=proc(BD,v) local b,r,k,lambda,block,i,j, rI,lambdaIJ:
b:=nops(BD):
k:=nops(BD[1]):
r:=0:
lambda:=0:
for block in BD do
	if not nops(block)=k then
		return FAIL:
	fi:
	if 1 in block then
		r+=1:
		if 2 in block then
			lambda+=1:
		fi:
	fi:
od:
for i from 1 to v do
	rI:=0:
	for block in BD do
		if i in block then
			rI+=1
		fi:
	od:
	if not rI=r then
		return FAIL:
	fi:
	for j from 1 to v do
		if not j=i then
			lambdaIJ:=0:
			for block in BD do
				if i in block and j in block then
					lambdaIJ+=1:
				fi:
			od:
			if not lambdaIJ=lambda then
				return FAIL:
			fi:
		fi:
	od:
od:
[b,v,r,k,lambda]:
end:

#Problem 7

PlotkinBound:=proc(n,d)
if evalb(0=d mod 2) then
	if n<2*d then
		return min(4*d,2*floor(d/(2*d-n))):
	fi:
	return 4*d:
fi:
if n<2*d+1 then
	return min(4*d+4,2*floor((d+1)/(2*d+1-n))):
fi:
return 4*d+4:
end:

ComparePlotkinSphere:=proc(n,d) local P,S:
P:=PlotkinBound(n,d):
#Note that the sphere packing bound does not work for even d. As such, we will just use the d one bigger.
if evalb(0=d mod 2) then
	S:=SPB(2,n,d/2):
else
	S:=SPB(2,n,(d-1)/2):
fi:
if P<S then return["Plotkin", P]: 
elif S<P then return["Sphere",S]:
else return["Same",S]:
fi:
end:

#Note that for n<d, M=1 and the Plotnik bound gives 0.
for d from 2 to 20 do
	for n from d to 2*d do
		print(n,d,ComparePlotkinSphere(n,d)):
	od:
od:

#[[[2, 2, ["Sphere", 1]], [3, 2, ["Sphere", 2]], [4, 2, ["Sphere", 3]]],
# [[3, 3, ["Same", 2]], [4, 3, ["Plotkin", 2]], [5, 3, ["Plotkin", 4]], [6, 3, ["Plotkin", 8]]],
# [[4, 4, ["Sphere", 1]], [5, 4, ["Same", 2]], [6, 4, ["Sphere", 2]], [7, 4, ["Sphere", 4]], [8, 4, ["Sphere", 6]]],
# [[5, 5, ["Same", 2]], [6, 5, ["Same", 2]], [7, 5, ["Plotkin", 2]], [8, 5, ["Plotkin", 4]], [9, 5, ["Plotkin", 6]], [10, 5, ["Plotkin", 12]]],
# [[6, 6, ["Sphere", 1]], [7, 6, ["Same", 2]], [8, 6, ["Same", 2]], [9, 6, ["Sphere", 3]], [10, 6, ["Sphere", 5]], [11, 6, ["Sphere", 8]], [12, 6, ["Sphere", 13]]],
# [[7, 7, ["Same", 2]], [8, 7, ["Same", 2]], [9, 7, ["Plotkin", 2]], [10, 7, ["Plotkin", 2]], [11, 7, ["Plotkin", 4]], [12, 7, ["Plotkin", 4]], [13, 7, ["Plotkin", 8]], [14, 7, ["Plotkin", 16]]],
# [[8, 8, ["Sphere", 1]], [9, 8, ["Same", 2]], [10, 8, ["Same", 2]], [11, 8, ["Plotkin", 2]], [12, 8, ["Plotkin", 4]], [13, 8, ["Plotkin", 4]], [14, 8, ["Plotkin", 8]], [15, 8, ["Same", 16]], [16, 8, ["Sphere", 26]]],
# [[9, 9, ["Same", 2]], [10, 9, ["Same", 2]], [11, 9, ["Plotkin", 2]], [12, 9, ["Plotkin", 2]], [13, 9, ["Plotkin", 2]], [14, 9, ["Plotkin", 4]], [15, 9, ["Plotkin", 4]], [16, 9, ["Plotkin", 6]], [17, 9, ["Plotkin", 10]], [18, 9, ["Plotkin", 20]]],
# [[10, 10, ["Sphere", 1]], [11, 10, ["Same", 2]], [12, 10, ["Same", 2]], [13, 10, ["Plotkin", 2]], [14, 10, ["Plotkin", 2]], [15, 10, ["Plotkin", 4]], [16, 10, ["Plotkin", 4]], [17, 10, ["Plotkin", 6]], [18, 10, ["Plotkin", 10]], [19, 10, ["Plotkin", 20]], [20, 10, ["Plotkin", 40]]],
# [[11, 11, ["Same", 2]], [12, 11, ["Same", 2]], [13, 11, ["Plotkin", 2]], [14, 11, ["Plotkin", 2]], [15, 11, ["Plotkin", 2]], [16, 11, ["Plotkin", 2]], [17, 11, ["Plotkin", 4]], [18, 11, ["Plotkin", 4]], [19, 11, ["Plotkin", 6]], [20, 11, ["Plotkin", 8]], [21, 11, ["Plotkin", 12]], [22, 11, ["Plotkin", 24]]],
# [[12, 12, ["Sphere", 1]], [13, 12, ["Same", 2]], [14, 12, ["Same", 2]], [15, 12, ["Plotkin", 2]], [16, 12, ["Plotkin", 2]], [17, 12, ["Plotkin", 2]], [18, 12, ["Plotkin", 4]], [19, 12, ["Plotkin", 4]], [20, 12, ["Plotkin", 6]], [21, 12, ["Plotkin", 8]], [22, 12, ["Plotkin", 12]], [23, 12, ["Plotkin", 24]], [24, 12, ["Plotkin", 48]]],
# [[13, 13, ["Same", 2]], [14, 13, ["Same", 2]], [15, 13, ["Plotkin", 2]], [16, 13, ["Plotkin", 2]], [17, 13, ["Plotkin", 2]], [18, 13, ["Plotkin", 2]], [19, 13, ["Plotkin", 2]], [20, 13, ["Plotkin", 4]], [21, 13, ["Plotkin", 4]], [22, 13, ["Plotkin", 4]], [23, 13, ["Plotkin", 6]], [24, 13, ["Plotkin", 8]], [25, 13, ["Plotkin", 14]], [26, 13, ["Plotkin", 28]]],
# [[14, 14, ["Sphere", 1]], [15, 14, ["Same", 2]], [16, 14, ["Same", 2]], [17, 14, ["Plotkin", 2]], [18, 14, ["Plotkin", 2]], [19, 14, ["Plotkin", 2]], [20, 14, ["Plotkin", 2]], [21, 14, ["Plotkin", 4]], [22, 14, ["Plotkin", 4]], [23, 14, ["Plotkin", 4]], [24, 14, ["Plotkin", 6]], [25, 14, ["Plotkin", 8]], [26, 14, ["Plotkin", 14]], [27, 14, ["Plotkin", 28]], [28, 14, ["Plotkin", 56]]],
# [[15, 15, ["Same", 2]], [16, 15, ["Same", 2]], [17, 15, ["Plotkin", 2]], [18, 15, ["Plotkin", 2]], [19, 15, ["Plotkin", 2]], [20, 15, ["Plotkin", 2]], [21, 15, ["Plotkin", 2]], [22, 15, ["Plotkin", 2]], [23, 15, ["Plotkin", 4]], [24, 15, ["Plotkin", 4]], [25, 15, ["Plotkin", 4]], [26, 15, ["Plotkin", 6]], [27, 15, ["Plotkin", 8]], [28, 15, ["Plotkin", 10]], [29, 15, ["Plotkin", 16]], [30, 15, ["Plotkin", 32]]],
# [[16, 16, ["Sphere", 1]], [17, 16, ["Same", 2]], [18, 16, ["Same", 2]], [19, 16, ["Plotkin", 2]], [20, 16, ["Plotkin", 2]], [21, 16, ["Plotkin", 2]], [22, 16, ["Plotkin", 2]], [23, 16, ["Plotkin", 2]], [24, 16, ["Plotkin", 4]], [25, 16, ["Plotkin", 4]], [26, 16, ["Plotkin", 4]], [27, 16, ["Plotkin", 6]], [28, 16, ["Plotkin", 8]], [29, 16, ["Plotkin", 10]], [30, 16, ["Plotkin", 16]], [31, 16, ["Plotkin", 32]], [32, 16, ["Plotkin", 64]]],
# [[17, 17, ["Same", 2]], [18, 17, ["Same", 2]], [19, 17, ["Plotkin", 2]], [20, 17, ["Plotkin", 2]], [21, 17, ["Plotkin", 2]], [22, 17, ["Plotkin", 2]], [23, 17, ["Plotkin", 2]], [24, 17, ["Plotkin", 2]], [25, 17, ["Plotkin", 2]], [26, 17, ["Plotkin", 4]], [27, 17, ["Plotkin", 4]], [28, 17, ["Plotkin", 4]], [29, 17, ["Plotkin", 6]], [30, 17, ["Plotkin", 6]], [31, 17, ["Plotkin", 8]], [32, 17, ["Plotkin", 12]], [33, 17, ["Plotkin", 18]], [34, 17, ["Plotkin", 36]]],
# [[18, 18, ["Sphere", 1]], [19, 18, ["Same", 2]], [20, 18, ["Same", 2]], [21, 18, ["Plotkin", 2]], [22, 18, ["Plotkin", 2]], [23, 18, ["Plotkin", 2]], [24, 18, ["Plotkin", 2]], [25, 18, ["Plotkin", 2]], [26, 18, ["Plotkin", 2]], [27, 18, ["Plotkin", 4]], [28, 18, ["Plotkin", 4]], [29, 18, ["Plotkin", 4]], [30, 18, ["Plotkin", 6]], [31, 18, ["Plotkin", 6]], [32, 18, ["Plotkin", 8]], [33, 18, ["Plotkin", 12]], [34, 18, ["Plotkin", 18]], [35, 18, ["Plotkin", 36]], [36, 18, ["Plotkin", 72]]],
# [[19, 19, ["Same", 2]], [20, 19, ["Same", 2]], [21, 19, ["Plotkin", 2]], [22, 19, ["Plotkin", 2]], [23, 19, ["Plotkin", 2]], [24, 19, ["Plotkin", 2]], [25, 19, ["Plotkin", 2]], [26, 19, ["Plotkin", 2]], [27, 19, ["Plotkin", 2]], [28, 19, ["Plotkin", 2]], [29, 19, ["Plotkin", 4]], [30, 19, ["Plotkin", 4]], [31, 19, ["Plotkin", 4]], [32, 19, ["Plotkin", 4]], [33, 19, ["Plotkin", 6]], [34, 19, ["Plotkin", 8]], [35, 19, ["Plotkin", 10]], [36, 19, ["Plotkin", 12]], [37, 19, ["Plotkin", 20]], [38, 19, ["Plotkin", 40]]],
# [[20, 20, ["Sphere", 1]], [21, 20, ["Same", 2]], [22, 20, ["Same", 2]], [23, 20, ["Same", 2]], [24, 20, ["Plotkin", 2]], [25, 20, ["Plotkin", 2]], [26, 20, ["Plotkin", 2]], [27, 20, ["Plotkin", 2]], [28, 20, ["Plotkin", 2]], [29, 20, ["Plotkin", 2]], [30, 20, ["Plotkin", 4]], [31, 20, ["Plotkin", 4]], [32, 20, ["Plotkin", 4]], [33, 20, ["Plotkin", 4]], [34, 20, ["Plotkin", 6]], [35, 20, ["Plotkin", 8]], [36, 20, ["Plotkin", 10]], [37, 20, ["Plotkin", 12]], [38, 20, ["Plotkin", 20]], [39, 20, ["Plotkin", 40]], [40, 20, ["Plotkin", 80]]]]

#Most of the time, the Plotkin bound wins.