2024-03-06--ternary-golay.ipynb

Kernel: Python 3 (ipykernel)

k = GF(3)
R.<T> = PolynomialRing(k)

F = T^11 -1

I = R.ideal([F])

A= R.quotient(I)

The smallest $j$ for which that $\mathbb{F}_{3^j}$ contains a root of $f$ is $j=5$:

[ (i,mod(3^i -1,11)) for i in range(6) ]

[(0, 0), (1, 2), (2, 8), (3, 4), (4, 3), (5, 0)]

Now, the field $\ell=\mathbb{F}_{3^5}$ has multiplicative group of order $3^5 - 1 = 242$:

3^5 - 1

242

Let's get a generator for the multiplicative group $\ell^\times = \mathbb{F}_{3^5}^\times$:

l.<z> = GF(3^5)

# let's make sure z is our desired generator:
multiplicative_order(z) == 3^5 - 1

True

Using z we can find a primitive 11th root of unity in $\ell$:

a = z^((3^5-1)/11)

# confirming...
multiplicative_order(a) == 11

True

Now, the minimal polynomial of a over $\mathbb{F}_3$ must have degree 5. What are its roots?

Well, if a is a root, also a^3 is a root since the mapping $\alpha \mapsto \alpha^3$ is in the Galois group of $\mathbb{F}_{3^5}$ over $\mathbb{F}_3$. Similary, a^(3^i) is a root for every natural number i.

But of course a^(3^5) = a since 11 divides 3^5 -1.

# let's display  the roots of the minimal polynomial of a:
[( f"a^(3^{i})=" , a^(3^i) ) for i in range(5) ]

[('a^(3^0)=', 2*z^3 + 2*z^2 + z + 1),
 ('a^(3^1)=', z^4 + z^3 + 2*z^2 + 2),
 ('a^(3^2)=', z^3 + 2*z + 1),
 ('a^(3^3)=', 2*z^4 + 2*z^3 + z),
 ('a^(3^4)=', 2*z^2 + 2*z + 1)]

# the monic minimal polynomial is the product of the linear factors corresponding to these roots. Namely

g = product([T - a^(3^i) for i in range(5)])
g

T^5 + T^4 + 2*T^3 + T^2 + 2

Note that this polynomial has coefficients in $\mathbb{F}_3$!

In addition to the trivial root $1$, there are still another 5 roots to $T^{11} - 1$ in $\ell = \mathbb{F}_{3^5}$ to account for.

Well, the roots of $T^{11} - 1$ in $\ell$ are precisely the elements of the multiplicative subgroup $\langle a \rangle$.

So what we really need is a good description of the roots of $f$.

So we need to describe the set of exponents $1,3,3^2,3^3,3^4$ modulo $11$.

S1 = [ mod(3^i,11) for i in range(5) ]
S1

[1, 3, 9, 5, 4]

This shows that the roots of $f$ are exactly $a^i$ for $i$ in S=[1, 3, 9, 5, 4]

The set S is called a cyclotomic coset.

Note that $a^2$ is a root of $T^{11} - 1$ but is not a root of $f$. So we need to consider the cyclotomic coset containing 2, namely:

S2 = [ mod(2*3^i,11) for i in range(5) ]
S2

[2, 6, 7, 10, 8]

The minimal polynomial $g$ of $a^2$ has roots $a^j$ for $j$ in [2, 6, 7, 10, 8].

h = product([T - a^j for j in S2])
h

T^5 + 2*T^3 + T^2 + 2*T + 2

Note that the S1 and S2 account for all but one of the roots of $T^{11} -1$:

set(S1 + S2) == set(range(1,11))

True

Since g and fh have no roots in common, their gcd is 1.

Let's check that we have factored $T^{11} - 1$

(T-1)*g*h == T^11 -1

True

## as constructed, sage believes g and h to have coefficients in F_3^5, even though they
## are really in F_3. We ask for versions of these polynomials whose coefficients are known to be in F_3:

## coerce g and h into elements gg and hh of R = F_3[T]
gg = R(g)  
hh = R(h)  

## note that g and h are reducible since they are in F_{3^5}[T], while gg and hh are irreducible

[ p.is_irreducible() for p in [g,h,gg,hh] ]

[False, False, True, True]

(T-1)*gg*hh == T^11 - 1

True

Now, we can notice that g and h are related by: $h(T) = -T^5 g(1/T)$.

h == -T^5*g(T = 1/T)

Since $\deg g = \deg h = 5$, the codes $C_1 = \langle g \rangle$ and $C_2 = \langle h \rangle$ are $[11,11-5]_3 = [11,6]_3$ codes.

Let's compute their minimum distance.

Using sage we can get the coefficients of a polynomial as follows:

gg.coefficients(sparse=False)

[2, 0, 1, 2, 1, 1]

We'll use these coefficients to build the code as a vector space.

V = VectorSpace(k,11)
#S = V.subspace([ (T^i * g).coefficients(sparse=False) for i in range(5) ])

def pad(ll,n):
    # pad the list ll with 0's to make it have length n
    x = len(ll)
    if x < n:
        return ll + (n-x)*[0]
    else:
        return ll[0:n]

def vectorize(p,n):
    # make a vector of length n out of a polynomial
    coeffs = p.coefficients(sparse=False)
    return V(pad(coeffs,n))


def mkCode(p):
    # vectorize the polynomial T^i * p and use the  vectors as a basis for the code C
    # I'm assuming deg p = 5...
    return V.subspace([ vectorize( T^i * p, 11) for i in range(6) ])

C1 = mkCode(gg)
C2 = mkCode(hh)
C1

Vector space of degree 11 and dimension 6 over Finite Field of size 3
Basis matrix:
[1 0 0 0 0 0 2 0 1 2 1]
[0 1 0 0 0 0 1 2 2 2 1]
[0 0 1 0 0 0 1 1 1 0 1]
[0 0 0 1 0 0 1 1 0 2 2]
[0 0 0 0 1 0 2 1 2 2 0]
[0 0 0 0 0 1 0 2 1 2 2]

C2

Vector space of degree 11 and dimension 6 over Finite Field of size 3
Basis matrix:
[1 0 0 0 0 0 2 2 1 2 0]
[0 1 0 0 0 0 0 2 2 1 2]
[0 0 1 0 0 0 2 2 0 1 1]
[0 0 0 1 0 0 1 0 1 1 1]
[0 0 0 0 1 0 1 2 2 2 1]
[0 0 0 0 0 1 1 2 1 0 2]

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

def min_distance(D):
    # brute-force computation of minimal distance of D
    return min([ weight(v) for v in D if v != 0])

[min_distance(C) for C in [C1,C2]]

[5, 5]

Thus C is an [11,6,5]_3 code.

We are going to explain why C is a perfect code. Recall that perfect means that C meets the sphere-packing bound.

Recall that $$\delta(m) = \sum_{i=0}^m \dbinom{n}{i} (q-1)^i$$

The sphere-packing bound says that a [n,k,d]_q code satisfies

$$|C| \cdot \delta(t) \le q^n$$

where $t = \lfloor (d-1)/2 \rfloor$.

so that C is a perfect code provided that

$$|C| \cdot \delta(t) = q^n.$$

def delta(n,q,m):
    return sum([ binomial(n,i)*(q-1)^i for i in range(m+1) ])

t = floor((5-1)/2)

delta(11,3,t).factor()

3^5

# the codes defined by g and by h are perfect

3^6 * delta(11,3,t) == 3^11

True

The main unsatisfying part of the above account is that we found the minimal distance of the codes via a brute force computation (we just made a list of the weights of the non-zero vector, and found the minimum of this list).

A nicer is approach is as follows.

Let $G$ be the generator matrix for (say) $C_1$.

G = MatrixSpace(k,6,11).matrix([ vectorize( T^i * g, 11) for i in range(6) ])
G

[2 0 1 2 1 1 0 0 0 0 0]
[0 2 0 1 2 1 1 0 0 0 0]
[0 0 2 0 1 2 1 1 0 0 0]
[0 0 0 2 0 1 2 1 1 0 0]
[0 0 0 0 2 0 1 2 1 1 0]
[0 0 0 0 0 2 0 1 2 1 1]

Now, adding a column of 1's to G determines a [12,6]_3 code. which is self-dual.

GG = MatrixSpace(k,6,12).matrix( [ list(row )+ [1] for row in G] )
GG

[2 0 1 2 1 1 0 0 0 0 0 1]
[0 2 0 1 2 1 1 0 0 0 0 1]
[0 0 2 0 1 2 1 1 0 0 0 1]
[0 0 0 2 0 1 2 1 1 0 0 1]
[0 0 0 0 2 0 1 2 1 1 0 1]
[0 0 0 0 0 2 0 1 2 1 1 1]

GG * GG.T

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

If CC denotes the code with generator matrix GG, then the computation GG * GG.T shows that CC is contained in the dual code CC^perp; since the dimension of CC^perp is 12-6 = 6, we conclude CC = CC^perp.

Now we have

Lemma If $C$ is a self-dual code of length $n$ over the field $\mathbb{F}_3$, then the weight of any codeword is a multiple of $3$.

Proof We first note that $1$ is the only non-zero square in $\mathbb{F}_3$, since $1^2 = 2^2 = 1$.

Let $\mathbf{v} = (v_1,\cdots,v_n) \in V$ and let $J = \{j \mid v_j \ne 0\}$.

Then $\operatorname{weight}(\mathbf{v}) = |J|$.

Since $C$ is self-dual we have in particular $$\langle \mathbf{v} , \mathbf{v} \rangle = 0.$$

Now notice that $$\langle \mathbf{v}, \mathbf{v} \rangle = \sum_{j \in J} (v_j)^2 = \sum_{j \in J} 1 = |J| \pmod{3}.$$

Thus we indeed find that $\operatorname{weight}(\mathbf{v}) = |J| \equiv 0 \pmod{3}$.

(GG[5],weight(GG[5]))

((0, 0, 0, 0, 0, 2, 0, 1, 2, 1, 1, 1), 6)