# OK to post
# HW5, Robert Dougherty-Bliss, 2024-02-01

read "C5.txt":

# 1.

(*

2.1.

(6, 2, 6):

We need two codewords that have distance 6 apart. Up to equivalence, this is
{000000, 111111}.

(3, 8, 1):

There are only 2^3 = 8 possible codewords, and fortunately we can take all of
them.

(4, 8, 2):

This code exists iff a (3, 8, 1) exists, which is F_2^3. So, take all vectors
in F_2^3 and add a parity bit to the end.

(5, 3, 4):

This code exists iff a (4, 3, 3) exists.

WLOG, such a code contains the origin and something with three 1's in any order
we like:

    0000
    1110

Any new codeword must have at least three 1's, and thus must collide with 1110
at least twice, implying a distance of at most two. Not possible!

(8, 30, 3):

The sphere packing bound says that a code of length 8 with minimum distance 3
has no more than

    2^8 / (1 + 8) = 28.4

codewords, so an (8, 30, 3) is not possible.

2.2.

Say that we have a binary (n, M, d) code.

Look at the first bit of every word in our code. There will be some number X of
words which have a 0 there, and some number Y which have a 1. Since X + Y = M,
either X or Y is at least M / 2. Take whichever group has at least M / 2
members and throw away the rest. This produces a new code with at least M / 2
elements whose minimal distance is still d (because we didn't decrease the
distance between any of the remaining words).

For any (n, M, d), we have M / 2 <= A_2(n - 1, d), so A_2(n, d) <= 2 A_2(n - 1,
d).

2.3.

Take a q-ary (n, M, d), with d even. Find any two "bits" which disagree and
delete them from the code. This produces a new code. Could any vectors have
collapsed? To do so, they would need to agree in all but one place, which means
d = 1. That's not possible here, so we have an (n - 1, M, d - 1) code.

Specializing to our case, a (3, M, 2) exists only if a (2, M, 1) exists, and
that implies M <= q^2.

Thanks to Natasha, I know how to construct a q^2 code: (x, y, x + y mod q). The
code (x, y) has distance 1, so this new code has distance either 1 or 2. If it
differs in only the last bit, then one of the first two bits also differ. But
it also can't differ in just one of the first two bits, because x + y = x + y'
means y = y'.

2.4.

Take a vector from F_2^n with even weight. If its last bit is 1, then the first
n - 1 bits have odd weight. If its last bit is 0, then the first n - 1 bits
have even weight. So every vector in E_n is the result of adding a parity bit
to an F_2^(n - 1) vector. Since F_2^(n - 1) is (n - 1, 2^(n - 1), 1), it
follows (from an argument in the book) that E_n is (n, 2^(n - 1), 2).

*)

# 2.

# I rewrote GRC. Instead of computing the sphere many times, we compute it once
# at the origin then shift it wherever we need it. This is considerably faster.
GRCrdb:=proc(q,n,d) local S,A,v:
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:


make_table := proc(q, N)
    vals := table():
    for d in [3, 5, 7] do
    for n from 5 to N do
        spb := q^n / add(binomial(n, k) * (q - 1)^k, k=0..(d-1)/2):
        val := nops(GRCrdb(q, n, d)):
        print(val);
        vals[d, n] := [val, round(spb), evalf(val/spb)]:
    od;
    od;

    op(vals):
end:

# q = 2 in 2443 seconds
q2 := table([(5, 17)=[512, 851, .6015625000],(5, 6)=[2, 3, .6875000000],(7
, 16)=[32, 94, .3403320312],(3, 17)=[4096, 7282, .5625000000],(7, 5)
=[1, 1, .8125000000],(5, 11)=[16, 31, .5234375000],(5, 5)=[2, 2, 1.]
,(5, 16)=[256, 478, .5351562500],(3, 9)=[32, 51, .6250000000],(3, 18
)=[8192, 13797, .5937500000],(7, 11)=[4, 9, .4531250000],(3, 16)=[
2048, 3855, .5312500000],(7, 10)=[2, 6, .3437500000],(3, 19)=[16384,
26214, .6250000000],(7, 7)=[2, 2, 1.],(7, 14)=[16, 35, .4589843750],
(3, 13)=[512, 585, .8750000000],(7, 9)=[2, 4, .5078125000],(5, 12)=[
16, 52, .3085937500],(7, 19)=[256, 452, .5664062500],(7, 18)=[128, 
265, .4824218750],(7, 6)=[1, 2, .6562500000],(3, 15)=[2048, 2048, 1.
],(3, 7)=[16, 16, 1.],(3, 12)=[256, 315, .8125000000],(3, 10)=[64, 
93, .6875000000],(7, 8)=[2, 3, .7265625000],(3, 8)=[16, 28, .5625000\
000],(7, 12)=[4, 14, .2919921875],(3, 5)=[4, 5, .7500000000],(7, 17)
=[64, 157, .4072265625],(5, 7)=[2, 4, .4531250000],(5, 20)=[2048, 
4970, .4121093750],(3, 6)=[8, 9, .8750000000],(5, 9)=[4, 11, .359375\
0000],(7, 15)=[32, 57, .5625000000],(5, 14)=[64, 155, .4140625000],(
5, 18)=[512, 1524, .3359375000],(5, 15)=[128, 271, .4726562500],(3,
11)=[128, 171, .7500000000],(5, 19)=[1024, 2745, .3730468750],(7, 20
)=[512, 776, .6596679688],(7, 13)=[8, 22, .3691406250],(5, 13)=[32,
89, .3593750000],(3, 14)=[1024, 1092, .9375000000],(3, 20)=[32768, 
49932, .6562500000],(5, 10)=[8, 18, .4375000000],(5, 8)=[4, 7, .5781\
250000]]):

# q = 3 in 7.4 seconds
q3 := table([(5, 6)=[3, 10, .3004115226],(5, 8)=[18, 51, .3539094650],(7, 9)
=[3, 24, .1272671849],(3, 9)=[519, 1036, .5009907026],(7, 6)=[1, 3, .3\
196159122],(5, 7)=[8, 22, .3621399177],(7, 10)=[9, 51, .1769547325],(3
, 10)=[1390, 2812, .4943352131],(3, 6)=[24, 56, .4279835391],(3, 7)=[
72, 146, .4938271605],(3, 5)=[9, 22, .4074074074],(7, 8)=[3, 11, .2638\
317330],(3, 8)=[198, 386, .5130315501],(7, 5)=[1, 2, .5390946502],(5,
10)=[83, 294, .2825280699],(5, 9)=[39, 121, .3229690596],(5, 5)=[3, 5,
.6296296296],(7, 7)=[3, 6, .5198902606]]):


# q = 5 in 10.4 seconds
q5 := table([(3, 7)=[1113, 2694, .4131456000],(5, 5)=[5, 17, .2896000000],(7
, 7)=[5, 30, .1667200000],(5, 7)=[39, 214, .1822080000],(3, 6)=[265,
625, .4240000000],(7, 6)=[1, 10, .9888000000e-1],(3, 5)=[74, 149, .497\
2800000],(5, 6)=[13, 59, .2204800000],(7, 5)=[1, 4, .2627200000]]):

# 6.

ParaBD := proc(BD, v)
    local b, sizes, k, M, row_sums, i, block_index, r, dots, j, l:
    b := nops(BD):
    sizes := map(nops, BD):
    if nops(sizes) <> 1 then
        return FAIL:
    fi:
    k := sizes[1]:

    # There's just not a great way to figure out how many clubs each person is
    # in without essentially computing the incidence matrix.
    M := Matrix(v, b):
    for block_index from 1 to b do
        for i from 1 to v do
            if i in BD[block_index] then    
                M[i, block_index] := 1:
            fi:
        od:
    od:

    row_sums := convert(MTM[sum](M, 2), set):
    if nops(row_sums) <> 1 then
        return FAIL:
    fi:

    r := row_sums[1]:

    dots := {}:
    for i from 1 to v do
    for j from i + 1 to v do
        dots := dots union {M[i] . M[j]}:
    od:
    od:

    if nops(dots) <> 1 then
        return FAIL:
    fi:

    l := dots[1]:

    [b, v, r, k, l]:
end: