ResearchCoding theoryGSI-R-0017 · Note · Existence

Five explicit binary linear codes of length 111 to 174 have minimum distance above the lower bounds listed at codetables.de on 16 November 2026.

A binary linear [n, k, d] code is a k-dimensional subspace of F2n whose nonzero vectors have Hamming weight (number of nonzero coordinates) at least d, with equality attained. For five pairs (n, k) we give a candidate code whose d exceeds, by 1, 2, 1, 1 and 1, the largest d for which codetables.de [1] lists a code.

Before this work
codetables.de [1] lists lower bounds 26, 40, 45, 34 and 36 and upper bounds 34, 53, 61, 49 and 54 for [111, 37], [152, 38], [172, 43], [159, 53] and [174, 58], as read on 16 November 2026.
Evidence
Candidate. Each distance was recomputed from the published matrix by programs of ours, written separately from one another and from the program that found the codes. The checks share the matrices; no one outside the lab has reviewed the result.
What you can check
All of it. A script confirms codewords of the stated weights in under a second. Published programs show no lighter word exists: under 2 minutes on a laptop for 4 codes, 344 s on a server for [174, 58].
Not established
That any of the five is new. Unread: MinT, Magma’s database, the codetables.de queue of unlisted codes. Chen’s database entry [112, 37, 32], if genuine, punctures to [111, 37, 31].
Method
Not published.

What was known

The codetables.de table has one cell for each (n, k), giving lower and upper bounds on d. Sources read for the five parameter sets and the 24 cells below:

SourceCoversCodes in the 24 cells
Chen, quasi-twisted codes [2]binary quasi-cyclic and quasi-twisted codes[111, 36, 26], [111, 37, 26], [172, 43, 45], [112, 37, 32] (see Limits)
Yu et al. [3]group codes, lengths up to 120none; at lengths 110 to 113 only dimension 21
Akre et al. [4]binary quasi-cyclic codesnone reaches a new value by puncturing, shortening or extension
Seddas et al. [5]seven codes of dimension 20 to 22none
Bayreuth list [6]one binary entry, [177, 10, 84]none
Chen’s database was queried by (n, k) for each of the 24 cells.

Web searches on these parameters, the last on 16 November 2026, found nothing.

The result

Each code is one-generator quasi-cyclic: its k = m generator rows are xi(1, a2, …, al) for 0 ≤ i < m, with l = n/m blocks, and each at is invertible in F2[x]/(xm − 1) and fixed by x ↦ xu, where u is a unit mod m. The code is invariant under the simultaneous cyclic shift of the blocks and the permutation j ↦ uj (mod m) of the coordinates of every block, which generate ℤm ⋊ ⟨u⟩, of order m · ordm(u). Codes with a prescribed automorphism group are a known class [7].

CodeListed boundsm, l, uGroup orderDistance computed byAd
[111, 37, 27]26–3437, 3, 10111all 237 codewords, 2 programs; Brouwer–Zimmermann4,292
[152, 38, 42]40–5338, 4, 7114all 238 codewords, 2 programs; Brouwer–Zimmermann6,460
[172, 43, 46]45–6143, 4, 6129all 243 codewords, 2 programs; Brouwer–Zimmermann6,536
[159, 53, 35]34–4953, 3, 10689Brouwer–Zimmermann; pigeon (below)not computed
[174, 58, 37]36–5458, 3, 7406Brouwer–Zimmermann; pigeon (below)not computed
Listed bounds: lower and upper bounds in the header of the codetables.de cell page, read 16 November 2026. Ad is the number of codewords of weight d; both enumerations agree. The enumeration (253, 258 words) was not run for the other two codes.
CODES = [
    (37, "1 852e20159 19ff6e6c3b", "604003"),
    (38, "1 1d03c75fa6 2798684cde 28eed6fba7", "ccc2a6043"),
    (43, "1 47821c7bedf 5f873abbff7 7b0f26c51ef", "2005c814944"),
    (53, "1 2d4101101a402 ff69fddfdf52e", "88254006c2309"),
    (58, "1 32f7d4f96ee7fff 3aab6ee1ec4b7f2", "d8420c9c004a9"),
]
Per code: m, the blocks 1, a_2, …, a_l of the generator row as hexadecimal integers (bit j is the coefficient of x^j), and the message polynomial of a codeword of weight d in the same encoding. The full matrices are the files below.

How to check it

1. Append this script to the data above: each output line is a nonzero codeword, so d is at most its weight.

def mul(a, b, m):  # product in F_2[x]/(x^m - 1); bit j is the coefficient of x^j
    r = 0
    for j in range(m):
        if b >> j & 1:
            r ^= ((a << j) | (a >> (m - j))) & ((1 << m) - 1)
    return r

for m, blocks, msg in CODES:
    word = [mul(int(msg, 16), int(b, 16), m) for b in blocks.split()]
    print(f"n = {m * len(word)}, k = {m}: codeword of weight", sum(bin(w).count("1") for w in word))
Output, in order: n = 111, k = 37: codeword of weight 27; then weights 42, 46, 35 and 37 for the other four codes.

2. Run the programs on the files below (shown for two codes; change the file names and, in mdcheck, the claimed d and m):

cc -O3 -fopenmp -o mdfull mdfull.c
cc -O3 -fopenmp -o pigeon pigeon.c
c++ -O3 -std=c++17 -pthread -o mdcheck mdcheck.cpp
python3 -I certcheck.py cert_111_37_u10.json 10
python3 -I certcheck.py cert_159_53_u10.json 10
./mdfull 28 10 < cert_111_37_u10.json.rows
./pigeon < cert_159_53_u10.json.blk
python3 -c "import json,sys; d=json.load(open(sys.argv[1])); print(d['n'], d['k'], d['claim_d']); print(*d['rows'], sep='\n')" cert_159_53_u10.json > c159.txt
./mdcheck bz c159.txt 10 35 blocks:53
On macOS with Apple clang 21 and Homebrew libomp, replace -fopenmp by -Xpreprocessor -fopenmp -I/opt/homebrew/opt/libomp/include -L/opt/homebrew/opt/libomp/lib -lomp. certcheck.py writes the .rows and .blk files into the current folder. mdfull takes the largest weight to count and the number of prefix bits.
$ ./mdfull 28 10 < cert_111_37_u10.json.rows
dmin=27 witness_weight=27
A_27=4292
A_28=17612
$ ./mdfull 44 10 < cert_152_38_u7.json.rows
dmin=42 witness_weight=42
A_42=6460
A_44=39387
$ ./pigeon < cert_159_53_u10.json.blk
ACCEPT_LOWER: d >= 35 (no word of weight <= D-1 in the covering set)
$ ./mdcheck bz c159.txt 10 35 blocks:53
VERDICT ACCEPT d=35 leaves=2.274e+11
Verdict lines of 4 of the runs timed below; the omitted lines give the parameters, search counts and a witness word. The covering set of pigeon is the set of words it tests.
Program[111, 37][152, 38][172, 43][159, 53][174, 58]
mdfull, enumeration21 s45 s411 s †––
mdcheck brute, enumeration23 s68 s862 s †––
mdcheck bz, Brouwer–Zimmermann< 1 s< 1 s8 s75 s344 s †
pigeon––8 s58 s3 min †
Wall time on an Apple M4 laptop with 10 cores, best of the runs; others took up to twice as long. † Recorded on a server, not re-run for this note: mdfull and pigeon on 32 threads, mdcheck on 12 threads.

Brouwer–Zimmermann [8]: the l blocks are l disjoint information sets (k coordinates that determine a codeword). For increasing w, all combinations of at most w rows of each set’s systematic generator matrix are listed; any other nonzero word has weight at least l(w + 1), and d is established when that bound, refined set by set, reaches the lightest weight found. pigeon: a nonzero word of weight below d has a block of weight at most ⌊(d − 1)/l⌋; that block is invertible, so it determines the word, and a cyclic shift puts a 1 in its first coordinate. pigeon tests every word so determined.

ProgramControlOutcome
mdcheck bzits enumeration mode, 462 random casessame d in every case
mdcheckweight counts of Golay, quadratic-residue, Reed–Muller and Hamming codesreproduced
mdfullweight counts of Golay and quadratic-residue codesreproduced
mdcheck30 altered inputs: for each code, claimed d ± 1, three single-bit flips, a repeated rowall rejected
pigeonenumeration, 150 random quasi-cyclic codessame verdict in every case
Controls on the programs, run by their authors; the inputs are not published.

A pass gives d for each published matrix if the programs are correct; pigeon also uses the shift invariance that certcheck.py confirms. A nonzero combination of rows of weight below d would refute a code.

What it changes

Puncturing, shortening, taking subcodes, appending a zero coordinate and parity extension (giving [112, 37, 28], [160, 53, 36] and [175, 58, 38]) raise the lower bound in 24 cells of the table of 16 November 2026, the five included: by 1 in 18 and by 2 in 6, none above a listed upper bound.

FromCells: listed lower bound → implied lower bound
[111, 37, 27], [112, 37, 28][110, 36] 26 → 27; [111, 36] 26 → 28; [111, 37] 26 → 27; [112, 36] 27 → 28; [112, 37] 26 → 28; [113, 37] 27 → 28
[152, 38, 42][151, 38] 40 → 41; [152, 38] 40 → 42; [153, 38] 40 → 42; [154, 38] 41 → 42
[172, 43, 46][171, 43] 44 → 45; [172, 43] 45 → 46
[159, 53, 35], [160, 53, 36][157, 51] 34 → 35; [158, 51] 35 → 36; [158, 52] 34 → 35; [159, 52] 35 → 36; [159, 53] 34 → 35; [160, 53] 34 → 36; [161, 53] 35 → 36
[174, 58, 37], [175, 58, 38][173, 57] 36 → 37; [174, 57] 37 → 38; [174, 58] 36 → 37; [175, 58] 36 → 38; [176, 58] 37 → 38
Listed values are those of the codetables.de table of 16 November 2026.

Limits

  • Novelty. MinT, Magma’s database and the codetables.de queue of unlisted codes were not read; reading them, or the maintainer’s response to a submission of the five codes, would narrow this, not close it. Seddas et al. [5] (29 September 2026) report seven codes accepted by the maintainer but not yet in the live tables. The 24 cells share this limit.
  • Chen’s database [2] lists a [112, 37, 32] code (N. Aydin, 2021). If genuine, it punctures to [111, 37, 31], exceeding the new values in 6 cells. As printed, its generator’s 56 cyclic shifts span dimension 56, not 37; the first 37 give a [112, 37] code with d = 22. A query to the database maintainer would resolve it.

Files

  • cert_111_37_u10.jsongenerator matrix of [111, 37, 27]: n, k, k rows as hexadecimal integers (bit i is coordinate i), claimed d
  • cert_152_38_u7.jsongenerator matrix of [152, 38, 42]
  • cert_172_43_u6.jsongenerator matrix of [172, 43, 46]
  • cert_159_53_u10.jsongenerator matrix of [159, 53, 35]
  • cert_174_58_u7.jsongenerator matrix of [174, 58, 37]
  • certcheck.pyPython 3: checks shift structure, invertible blocks and invariance under x ↦ x^u; writes the input files of mdfull and pigeon
  • mdfull.cC with OpenMP: minimum distance by Gray-code enumeration of all 2^k codewords, with weight counts
  • mdcheck.cppC++: enumeration with the full weight distribution (brute) and Brouwer–Zimmermann (bz); prints a witness word
  • pigeon.cC with OpenMP: lower bound d ≥ D for a one-generator quasi-cyclic code by the pigeonhole argument above

References

  1. [1]M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, codetables.de; cell pages, table and update log for binary codes, read 16 November 2026. Link
  2. [2]E. Z. Chen, Online database of quasi-twisted codes, read 16 November 2026 (5,070 codes, last modified 11 November 2026). Link
  3. [3]C. Yu, S. Zhu, H. Chen, Y. Li, X. Zhang, New record-breaking binary linear codes constructed from group codes, arXiv:2412.15551 (20 December 2024). Link
  4. [4]D. Akre, N. Aydin, M. J. Harrington, S. R. Pandey, New binary and ternary quasi-cyclic codes with good properties, arXiv:2108.06752 (v1 15 August 2021). Link
  5. [5]A. Seddas, V. Shashkov, M. Viazovska, E. Abbe, Evolving towards better codes: LLM-guided search for high-distance binary linear codes, arXiv:2609.37056 (29 September 2026). Link
  6. [6]List of new linear codes, University of Bayreuth (Braun, Kohnert, Wassermann; last update 10 October 2005), read 1 November 2026. Link
  7. [7]M. Braun, A. Kohnert, A. Wassermann, Optimal linear codes from matrix groups, IEEE Trans. Inf. Theory 51(12), 4247–4251 (2005), doi:10.1109/TIT.2005.859291. Link
  8. [8]F. Hernando, F. D. Igual, G. Quintana-Ortí, Algorithm 994: Fast implementations of the Brouwer–Zimmermann algorithm for the computation of the minimum distance of a random linear code, ACM Trans. Math. Softw. 45(2), article 23 (2019), doi:10.1145/3302389; preprint arXiv:1603.06757, which outlines the algorithm. Link

Cite asKishan Kumar, Candidate binary linear codes, GSI-R-0017, https://generalised.si/research/candidate-binary-codes, 2026.

Published16 November 2026. Revised 16 November 2026.

History
  • This account is published.
  • The 24 values are recomputed from the full codetables.de table.

All results