Enumerating binary self-dual codes#
This module implements functions useful for studying binary self-dual codes.
The main function is self_dual_binary_codes
, 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 \([A_0,A_1,...,A_n]\)"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.
The following double
for
loop can be time-consuming but should be run once in a while for testing purposes. It should only printTrue
and have no trace-back errors:sage: for n in [4,6,8,10,12,14,16,18,20,22]: # not tested ....: C = self_dual_binary_codes(n); m = len(C.keys()) ....: for i in range(m): ....: C0 = C["%s"%n]["%s"%i]["code"] ....: print([n,i,C["%s"%n]["%s"%i]["spectrum"] == C0.spectrum()]) ....: print(C0 == C0.dual_code()) ....: G = C0.automorphism_group_binary_code() ....: print(C["%s" % n]["%s" % i]["order autgp"] == G.order())
To check if the “Riemann hypothesis” holds, run the following code:
sage: R = PolynomialRing(CC,"T") # not tested sage: T = R.gen() # not tested sage: for n in [4,6,8,10,12,14,16,18,20,22]: # not tested ....: C = self_dual_binary_codes(n); m = len(C["%s"%n].keys()) ....: for i in range(m): ....: C0 = C["%s"%n]["%s"%i]["code"] ....: 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 \(m\times m\) 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 matrices \(M_i\) 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 [HP2003], page 347).
AUTHORS:
David Joyner (2007-08-11)
REFERENCES:
[HP2003] 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.
- sage.coding.self_dual_codes.self_dual_binary_codes(n)#
Return the dictionary of inequivalent binary self dual 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 inequivalent “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 coefficient 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 [HP2003], 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://oeis.org/classic/A003179, the next 2 entries are: 3295, 24147.
EXAMPLES:
sage: C = codes.databases.self_dual_binary_codes(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 = codes.databases.self_dual_binary_codes(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