2024-02-28--dual-code.ipynb

Kernel: Python 3 (ipykernel)

k = GF(2)
V = VectorSpace(k,8)

C = V.subspace([V([1,0,0,0,1,1,1,0]),
                V([0,1,0,0,1,1,0,1]),
                V([0,0,1,0,1,0,1,1]),
                V([0,0,0,1,0,1,1,1])])

G = MatrixSpace(k,4,8).matrix(C.basis())

We see that $C \subset C^\perp$ since G * G.T == 0.

G * G.T

[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]

Equality holds because we know $4=\dim C = 8-4=\dim C^\perp$ in this case.

(Though really the point is that the weight of each vector in $C$ is even)

def weight(v):
    r = [x for x in v if x != 0]
    return len(r)


[ weight(c) for c in C ]

[0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8]

R.<T> = PolynomialRing(ZZ)

## compute the weight enumerator, as an element of R
def WE(C):
    return sum([ T^weight(c) for c in C ])

WE(C)

T^8 + 14*T^4 + 1

Now, let us suppose that $C$ is just some [8,4]_2 self-dual code with weight enumerator $$\displaystyle A(C) = 1 + \sum_{i=1}^8 a_i T^i$$ (not necessarily the one we specified above).

We are going to investigate what the McWilliams identities tell us about the coefficients $a_i$.

vars = var(' '.join([ f"a{n}" for n in range(1,9) ]))
S = PolynomialRing(R,vars)

#S.variable_names()
vars

(a1, a2, a3, a4, a5, a6, a7, a8)

A = 1 + sum([vars[n] * T^(n+1) for n in range(8) ])

# The McWilliams identity gives the following formula for the
# weigth enumerator for the dual code
Adual = 2^(-4) * (1+T)^8 * A(T = (1-T)/(1+T) )
Adual

-1/16*(T^8 + 8*T^7 + 28*T^6 + 56*T^5 + 70*T^4 + 56*T^3 + 28*T^2 + 8*T + 1)*((T - 1)*a1/(T + 1) - (T - 1)^2*a2/(T + 1)^2 + (T - 1)^3*a3/(T + 1)^3 - (T - 1)^4*a4/(T + 1)^4 + (T - 1)^5*a5/(T + 1)^5 - (T - 1)^6*a6/(T + 1)^6 + (T - 1)^7*a7/(T + 1)^7 - (T - 1)^8*a8/(T + 1)^8 - 1)

# we can get the constant term of a poly by evaluation at T=0
Adual(T=0)

1/16*a1 + 1/16*a2 + 1/16*a3 + 1/16*a4 + 1/16*a5 + 1/16*a6 + 1/16*a7 + 1/16*a8 + 1/16

# and we can get the coeff of T by evaluting the derivative at T=0
Adual.diff(T)(T=0)

3/8*a1 + 1/4*a2 + 1/8*a3 - 1/8*a5 - 1/4*a6 - 3/8*a7 - 1/2*a8 + 1/2

# More generally, we can get coefficients of T inductively by repeated differentiation:
def coeff(F,n):
    # return nth coefficient of polynomial F in variable T
    if n==0:
        return F(T=0)
    else:
        return (1/n)*coeff(F.diff(T),n-1)

# return the coefficients of F, as a list of length deg(F) + 1
def allCoeffs(F):
    return [ coeff(F,n) for n in range(F.degree(T)+1) ]

allCoeffs(A)

[1, a1, a2, a3, a4, a5, a6, a7, a8]

allCoeffs(Adual)

[1/16*a1 + 1/16*a2 + 1/16*a3 + 1/16*a4 + 1/16*a5 + 1/16*a6 + 1/16*a7 + 1/16*a8 + 1/16,
 3/8*a1 + 1/4*a2 + 1/8*a3 - 1/8*a5 - 1/4*a6 - 3/8*a7 - 1/2*a8 + 1/2,
 7/8*a1 + 1/4*a2 - 1/8*a3 - 1/4*a4 - 1/8*a5 + 1/4*a6 + 7/8*a7 + 7/4*a8 + 7/4,
 7/8*a1 - 1/4*a2 - 3/8*a3 + 3/8*a5 + 1/4*a6 - 7/8*a7 - 7/2*a8 + 7/2,
 -5/8*a2 + 3/8*a4 - 5/8*a6 + 35/8*a8 + 35/8,
 -7/8*a1 - 1/4*a2 + 3/8*a3 - 3/8*a5 + 1/4*a6 + 7/8*a7 - 7/2*a8 + 7/2,
 -7/8*a1 + 1/4*a2 + 1/8*a3 - 1/4*a4 + 1/8*a5 + 1/4*a6 - 7/8*a7 + 7/4*a8 + 7/4,
 -3/8*a1 + 1/4*a2 - 1/8*a3 + 1/8*a5 - 1/4*a6 + 3/8*a7 - 1/2*a8 + 1/2,
 -1/16*a1 + 1/16*a2 - 1/16*a3 + 1/16*a4 - 1/16*a5 + 1/16*a6 - 1/16*a7 + 1/16*a8 + 1/16]

So if $C$ is self-dual, we can compute the equations that the coefficients of $A(T)$ must satisfy, as follows:

# this gives coefficient equations required in order that `A == Adual`
#
eqs = [ A == B for (A,B) in zip(allCoeffs(A),allCoeffs(Adual)) ]
eqs

[1 == 1/16*a1 + 1/16*a2 + 1/16*a3 + 1/16*a4 + 1/16*a5 + 1/16*a6 + 1/16*a7 + 1/16*a8 + 1/16,
 a1 == 3/8*a1 + 1/4*a2 + 1/8*a3 - 1/8*a5 - 1/4*a6 - 3/8*a7 - 1/2*a8 + 1/2,
 a2 == 7/8*a1 + 1/4*a2 - 1/8*a3 - 1/4*a4 - 1/8*a5 + 1/4*a6 + 7/8*a7 + 7/4*a8 + 7/4,
 a3 == 7/8*a1 - 1/4*a2 - 3/8*a3 + 3/8*a5 + 1/4*a6 - 7/8*a7 - 7/2*a8 + 7/2,
 a4 == -5/8*a2 + 3/8*a4 - 5/8*a6 + 35/8*a8 + 35/8,
 a5 == -7/8*a1 - 1/4*a2 + 3/8*a3 - 3/8*a5 + 1/4*a6 + 7/8*a7 - 7/2*a8 + 7/2,
 a6 == -7/8*a1 + 1/4*a2 + 1/8*a3 - 1/4*a4 + 1/8*a5 + 1/4*a6 - 7/8*a7 + 7/4*a8 + 7/4,
 a7 == -3/8*a1 + 1/4*a2 - 1/8*a3 + 1/8*a5 - 1/4*a6 + 3/8*a7 - 1/2*a8 + 1/2,
 a8 == -1/16*a1 + 1/16*a2 - 1/16*a3 + 1/16*a4 - 1/16*a5 + 1/16*a6 - 1/16*a7 + 1/16*a8 + 1/16]

Since $C$ is self-dual and since we work over $\mathbb{F}_2$, it is easy to see that any codeword in $C$ must have even weight.

So we also need a1 == a3 == a5 == a7 == 0

# make the equality conditions for vanishing of a_odd
odd = [ v == 0 for v in [a1,a3,a5,a7]]

# finally, we can *solve* these equations'

sol = solve(eqs + odd,vars,solution_dict=True)
sol

[{a1: 0, a2: r2, a3: 0, a4: -2*r2 + 14, a5: 0, a6: r2, a7: 0, a8: 1}]

We get a parametrized solution. The parameterization tells us that the possible weight enumerators $A$ for a self-dual [8,4]_2 code are given by the formula

$$1 + r(T^2 - 2T^4 + T^6) + 14 T^4 + T^8$$

Since the coefficient $T^2$ is $r$ and the coeff of $T^4$ is $14 - 2r$, and since both must be non-negative, we must have $r \in \{0,1,..,7\}$.

The self-dual code described above corresponds to the case $r = 0$.

Note that in any event, the coefficient of $T^8$ is always 1; this shows that a self-dual $[8,4]_2$ code always contains the all-one vector

one = 8*[1]
one

[1, 1, 1, 1, 1, 1, 1, 1]

Question: We know there is a self-dual [8,4]_2 code with weight enumerator $1 + 14 T^4 + T^8$. What about the other possibilities?

E.g., is there one with weight enumerator $1 + (T^2 - 2T^4 + T^6) + 14 T^4 + T^8 = 1 + T^2 + 12 T^4 + T^6 + T^8$?