ゴーレイ符号がS(5,8,24)系であることを確認する

はじめに

吉荒聡『散在型有限単純群』を読みながら、手を動かして確認してみる(定義などの番号は同書による)。ゴーレイ符号(符号理論の文脈では「拡張2元ゴーレイ符号」と呼ぶようだ)は$S(5,8,24)$系と関係がある。

定義

(定義) $X$を有限集合、$t$を自然数とするとき、${X \choose t}$を大きさ$t$の$X$の部分集合と定義する。つまり、${X \choose t} := \lbrace Y \subseteq X : |Y|=t \rbrace$

(定義 2.28) $\Omega$を大きさ$v$の有限集合とし、$t,k$は$1\le t \le k < v$を満たす自然数とする。$\Omega$と$\mathcal{O} \subseteq {\Omega \choose k}$の対$(\Omega, \mathcal{O})$が$(t,k,v)$シュタイナー系(Steiner system)であるとは、任意の$X \in {\Omega \choose t}$について、$X \subseteq C$を満たす$C \in \mathcal{O}$がただ1つ存在することであり、$S(t,k,v)$系と書く。

確認

def bit_positions(n):
    positions = []
    index = 0
    while n > 0:
        if n & 1:
            positions.append(index)
        n >>= 1
        index += 1
    return positions

def positions_to_number(positions):
    number = 0
    for pos in positions:
        number |= (1 << pos)
    return number

from functools import reduce
from itertools import chain, combinations
from operator import xor

golay = [0b100000000000100111110001,
         0b010000000000010011111010,
         0b001000000000001001111101,
         0b000100000000100100111110,
         0b000010000000110010011101,
         0b000001000000111001001110,
         0b000000100000111100100101,
         0b000000010000111110010010,
         0b000000001000011111001001,
         0b000000000100001111100110,
         0b000000000010010101010111,
         0b000000000001101010101011]
elements = []
for gs in chain.from_iterable(combinations(golay, r) for r in range(1, len(golay) + 1)):
    g = reduce(xor, gs)
    if g.bit_count() == 8:
        elements.append(g)

$S(5,8,24)$系の$|\mathcal{O}|$は$759$だが、実際そうなっている。

len(elements)
# 759

任意の5点集合に対して、それを包含する$C$がただ1つ存在する。

for x in combinations(range(24), 5):
    x = positions_to_number(x)
    assert len([c for c in elements if c & x == x]) == 1

性質

(補題 3.1) (1) 任意の$A,B\in\mathcal{O}$について、$|A \cap B| = 0,2,4,8$

{(a & b).bit_count() for a in elements for b in elements}
# {0, 2, 4, 8}

(補題 3.1) (2) $m \in \lbrace 0,2,4,8\rbrace$に対して$X\in{A \choose m}$を固定する。$|\lbrace B \in \mathcal{O} : A \cap B = X\rbrace|$は、$m=0,2,4,8$に対してそれぞれ$30,16,4,1$となる。

for m, l in [(0, 30), (2, 16), (4, 4), (8, 1)]:
    for a in elements:
        for s in combinations(bit_positions(a), m):
            n = positions_to_number(s)
            assert len([b for b in elements if a & b == n]) == l

(補題 3.1) (3) $m \in \lbrace 0,2,4,8\rbrace$と任意の$A$について、$|\lbrace B \in \mathcal{O} : |A \cap B| = m\rbrace|$は、$m=0,2,4,8$に対してそれぞれ$30,448,280,1$となる。

for m, l in [(0, 30), (2, 448), (4, 280), (8, 1)]:
    for a in elements:
        assert len([b for b in elements if (a & b).bit_count() == m]) == l

(補題 3.2) (トッドの補題) $A, B \in \mathcal{O}$が$|A\cap B|=4$ならば、$A+B\in\mathcal{O}$

for a in elements:
    for b in elements:
        if (a & b).bit_count() == 4:
            assert (a ^ b) in elements