39.3 This module implements functions useful for studying binary self-dual codes

Module: sage.coding.sd_codes

This module implements functions useful for studying binary self-dual codes.

The main function is self_dual_codes_binary, which is a case-by-case list of entries, each represented by a Python dictionary.

* Format of each entry: a Python dictionary with keys "order autgp", "spectrum", "code", "Comment", "Type", where "code" - a sd code C of length n, dim n/2, over GF(2) "order autgp" - order of the permutation automorphism group of C "Type" - the type of C (which can be "I" or "II", in the binary case) "spectrum" - the spectrum [A0,A1,...,An] "Comment" - possibly an empty string.

Python dictionaries were used since they seemed to be both human-readable and allow others to update the database easiest.

(a) The following double for loop can be time-consuming but should be run once in awhile for testing purposes. It should only print True and have no trace-back errors.

for n in [4,6,8,10,12,14,16,18,20,22]: C = self_dual_codes_binary(n); m = len(C.keys()) for i in range(m): C0 = C["print n, ' ',i, ' ',C["print C0 == C0.dual_code() G = C0.automorphism_group_binary_code() print C["

(b) To check if the "Riemann hypothesis" holds, run the following code:

R = PolynomialRing(CC,"T") T = R.gen() for n in [4,6,8,10,12,14,16,18,20,22]: C = self_dual_codes_binary(n); m = len(C["for i in range(m): C0 = C["#print n,i,C0 if C0.minimum_distance()>2: f = R(C0.sd_zeta_polynomial()) print n,i,[z[0].abs() for z in f.roots()]

You should get lists of numbers equal to 0.707106781186548.

Here's a rather naive construction of self-dual codes in the binary case:

For even m, let A_m denote the mxm matrix over GF(2) given by adding the all 1's matrix to the identity matrix (in MatrixSpace(GF(2),m,m) of course). If M_1, ..., M_r are square matrices, let diag(M_1,M_2,...,M_r) denote the "block diagonal" matrix with the M_i's on the diagonal and 0's elsewhere. Let C(m_1,...,m_r,s) denote the linear code with generator matrix having block form G = (I, A), where A = diag(A_m_1,A_m_2,...,A_m_r,I_s), for some (even) m_i's and s, where m_1+m_2+...+m_r+s=n/2. Note: Such codes C(m_1,...,m_r,s) are sd.

SD codes not of this form will be called (for the purpose of documenting the code below) "exceptional". Except when n is "small", most sd codes are exceptional (based on a counting argument and table 9.1 in the Huffman+Pless [HP], page 347).

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Author: David Joyner, copyright 2007, wdjoyner@gmail.com. This is released under the GPL, version 2 or later (www.fsf.org). Created 11-8-2007. Last modified 3-3-2008.

REFERENCES: [HP] W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003. [P] V. Pless, "A classification of self-orthogonal codes over GF(2)", Discrete Math 3 (1972) 209-246.

Module-level Functions

I2( n)

MS( n)

MS2( n)

matA( n)

matId( n)

self_dual_codes_binary( n)

Returns the dictionary of inequivalent sd codes of length n.

For n>=4 even, returns the sd codes of a given length, up to (perm) equivalence, the (perm) aut gp, and the type.

The number of inequiv "diagonal" sd binary codes in the database of length n is ("diagonal" is defined by the conjecture above) is the same as the restricted partition number of n, where only integers from the set 1,4,6,8,... are allowed. This is the coeff of $ x^n$ in the series expansion $ (1-x)^{-1}\prod_{2^\infty (1-x^{2j})^{-1}}$ . Typing the command f = (1-x)(-1)*prod([(1-x(2*j))(-1) for j in range(2,18)]) into SAGE, we obtain for the coeffs of $ x^4$ , $ x^6$ , ... [1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 11, 11, 15, 15, 22, 22, 30, 30, 42, 42, 56, 56, 77, 77, 101, 101, 135, 135, 176, 176, 231] These numbers grow too slowly to account for all the sd codes (see Huffman+Pless' Table 9.1, referenced above). In fact, in Table 9.10 of [HP], the number B_n of inequivalent sd binary codes of length n is given:

n 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 B_n 1 1 1 2 2 3 4 7 9 16 25 55 103 261 731

According to http://www.research.att.com/ njas/sequences/A003179, the next 2 entries are: 3295, 24147.

sage: C = self_dual_codes_binary(10)
sage: C["10"]["0"]["code"] == C["10"]["0"]["code"].dual_code()
True
sage: C["10"]["1"]["code"] == C["10"]["1"]["code"].dual_code()
True
sage: len(C["10"].keys()) # number of inequiv sd codes of length 10
2
sage: C = self_dual_codes_binary(12) 
sage: C["12"]["0"]["code"] == C["12"]["0"]["code"].dual_code()
True
sage: C["12"]["1"]["code"] == C["12"]["1"]["code"].dual_code()
True
sage: C["12"]["2"]["code"] == C["12"]["2"]["code"].dual_code()
True

See About this document... for information on suggesting changes.